aboutsummaryrefslogtreecommitdiff
path: root/gcc/gimple-range-edge.cc
diff options
context:
space:
mode:
authorAldy Hernandez <aldyh@redhat.com>2023-01-24 13:01:39 +0100
committerAldy Hernandez <aldyh@redhat.com>2023-05-01 08:29:24 +0200
commite1366a7e4ce1d4dfe43dfa50d451ac45da00975f (patch)
tree299ed836d400d17453a6a82e2ed6f28b614f6980 /gcc/gimple-range-edge.cc
parent4d68c7f7b5aea5e95f44c3af13a24aa3daae9cf5 (diff)
downloadgcc-e1366a7e4ce1d4dfe43dfa50d451ac45da00975f.zip
gcc-e1366a7e4ce1d4dfe43dfa50d451ac45da00975f.tar.gz
gcc-e1366a7e4ce1d4dfe43dfa50d451ac45da00975f.tar.bz2
vrange_storage overhaul
[tl;dr: This is a rewrite of value-range-storage.* such that global ranges and the internal ranger cache can use the same efficient storage mechanism. It is optimized such that when wide_ints are dropped into irange, the copying back and forth from storage will be very fast, while being able to hold any number of sub-ranges dynamically allocated at run-time. This replaces the global storage mechanism which was limited to 6-subranges.] Previously we had a vrange allocator for use in the ranger cache. It worked with trees and could be used in place (fast), but it was not memory efficient. With the upcoming switch to wide_ints for irange, we can't afford to allocate ranges that can be used in place, because an irange will be significantly larger, as it will hold full wide_ints. We need a trailing_wide_int mechanism similar to what we use for global ranges, but fast enough to use in the ranger's cache. The global ranges had another allocation mechanism that was trailing_wide_int based. It was memory efficient but slow given the constant conversions from trees to wide_ints. This patch gets us the best of both worlds by providing a storage mechanism with a custom trailing wide int interface, while at the same time being fast enough to use in the ranger cache. We use a custom trailing wide_int mechanism but more flexible than trailing_wide_int, since the latter has compile-time fixed-sized wide_ints. The original TWI structure has the current length of each wide_int in a static portion preceeding the variable length: template <int N> struct GTY((user)) trailing_wide_ints { ... ... /* The current length of each number. that will, in turn, turn off TBAA on gimple, trees and RTL. */ struct {unsigned char len;} m_len[N]; /* The variable-length part of the structure, which always contains at least one HWI. Element I starts at index I * M_MAX_LEN. */ HOST_WIDE_INT m_val[1]; }; We need both m_len[] and m_val[] to be variable-length at run-time. In the previous incarnation of the storage mechanism the limitation of m_len[] being static meant that we were limited to whatever [N] could use up the unused bits in the TWI control world. In practice this meant we were limited to 6 sub-ranges. This worked fine for global ranges, but is a no go for our internal cache, where we must represent things exactly (ranges for switches, etc). The new implementation removes this restriction by making both m_len[] and m_val[] variable length. Also, rolling our own allows future optimization be using some of the leftover bits in the control world. Also, in preparation for the wide_int conversion, vrange_storage is now optimized to blast the bits directly into the ultimate irange instead of going through the irange API. So ultimately copying back and forth between the ranger cache and the storage mechanism is just a matter of copying a few bits for the control word, and copying an array of HOST_WIDE_INTs. These changes were heavily profiled, and yielded a good chunk of the overall speedup for the wide_int conversion. Finally, vrange_storage is now a first class structure with GTY markers and all, thus alleviating the void * hack in struct tree_ssa_name and friends. This removes a few warts in the API and looks cleaner overall. gcc/ChangeLog: * gimple-fold.cc (maybe_fold_comparisons_from_match_pd): Adjust for vrange_storage. * gimple-range-cache.cc (sbr_vector::sbr_vector): Same. (sbr_vector::grow): Same. (sbr_vector::set_bb_range): Same. (sbr_vector::get_bb_range): Same. (sbr_sparse_bitmap::sbr_sparse_bitmap): Same. (sbr_sparse_bitmap::set_bb_range): Same. (sbr_sparse_bitmap::get_bb_range): Same. (block_range_cache::block_range_cache): Same. (ssa_global_cache::ssa_global_cache): Same. (ssa_global_cache::get_global_range): Same. (ssa_global_cache::set_global_range): Same. * gimple-range-cache.h: Same. * gimple-range-edge.cc (gimple_outgoing_range::gimple_outgoing_range): Same. (gimple_outgoing_range::switch_edge_range): Same. (gimple_outgoing_range::calc_switch_ranges): Same. * gimple-range-edge.h: Same. * gimple-range-infer.cc (infer_range_manager::infer_range_manager): Same. (infer_range_manager::get_nonzero): Same. (infer_range_manager::maybe_adjust_range): Same. (infer_range_manager::add_range): Same. * gimple-range-infer.h: Rename obstack_vrange_allocator to vrange_allocator. * tree-core.h (struct irange_storage_slot): Remove. (struct tree_ssa_name): Remove irange_info and frange_info. Make range_info a pointer to vrange_storage. * tree-ssanames.cc (range_info_fits_p): Adjust for vrange_storage. (range_info_alloc): Same. (range_info_free): Same. (range_info_get_range): Same. (range_info_set_range): Same. (get_nonzero_bits): Same. * value-query.cc (get_ssa_name_range_info): Same. * value-range-storage.cc (class vrange_internal_alloc): New. (class vrange_obstack_alloc): New. (class vrange_ggc_alloc): New. (vrange_allocator::vrange_allocator): New. (vrange_allocator::~vrange_allocator): New. (vrange_storage::alloc_slot): New. (vrange_allocator::alloc): New. (vrange_allocator::free): New. (vrange_allocator::clone): New. (vrange_allocator::clone_varying): New. (vrange_allocator::clone_undefined): New. (vrange_storage::alloc): New. (vrange_storage::set_vrange): Remove slot argument. (vrange_storage::get_vrange): Same. (vrange_storage::fits_p): Same. (vrange_storage::equal_p): New. (irange_storage::write_lengths_address): New. (irange_storage::lengths_address): New. (irange_storage_slot::alloc_slot): Remove. (irange_storage::alloc): New. (irange_storage_slot::irange_storage_slot): Remove. (irange_storage::irange_storage): New. (write_wide_int): New. (irange_storage_slot::set_irange): Remove. (irange_storage::set_irange): New. (read_wide_int): New. (irange_storage_slot::get_irange): Remove. (irange_storage::get_irange): New. (irange_storage_slot::size): Remove. (irange_storage::equal_p): New. (irange_storage_slot::num_wide_ints_needed): Remove. (irange_storage::size): New. (irange_storage_slot::fits_p): Remove. (irange_storage::fits_p): New. (irange_storage_slot::dump): Remove. (irange_storage::dump): New. (frange_storage_slot::alloc_slot): Remove. (frange_storage::alloc): New. (frange_storage_slot::set_frange): Remove. (frange_storage::set_frange): New. (frange_storage_slot::get_frange): Remove. (frange_storage::get_frange): New. (frange_storage_slot::fits_p): Remove. (frange_storage::equal_p): New. (frange_storage::fits_p): New. (ggc_vrange_allocator): New. (ggc_alloc_vrange_storage): New. * value-range-storage.h (class vrange_storage): Rewrite. (class irange_storage): Rewrite. (class frange_storage): Rewrite. (class obstack_vrange_allocator): Remove. (class ggc_vrange_allocator): Remove. (vrange_allocator::alloc_vrange): Remove. (vrange_allocator::alloc_irange): Remove. (vrange_allocator::alloc_frange): Remove. (ggc_alloc_vrange_storage): New. * value-range.h (class irange): Rename vrange_allocator to irange_storage. (class frange): Same.
Diffstat (limited to 'gcc/gimple-range-edge.cc')
-rw-r--r--gcc/gimple-range-edge.cc23
1 files changed, 12 insertions, 11 deletions
diff --git a/gcc/gimple-range-edge.cc b/gcc/gimple-range-edge.cc
index 8fedac5..22fb709 100644
--- a/gcc/gimple-range-edge.cc
+++ b/gcc/gimple-range-edge.cc
@@ -69,7 +69,7 @@ gimple_outgoing_range::gimple_outgoing_range (int max_sw_edges)
{
m_edge_table = NULL;
m_max_edges = max_sw_edges;
- m_range_allocator = new obstack_vrange_allocator;
+ m_range_allocator = new vrange_allocator;
}
@@ -97,16 +97,16 @@ gimple_outgoing_range::switch_edge_range (irange &r, gswitch *sw, edge e)
return false;
if (!m_edge_table)
- m_edge_table = new hash_map<edge, irange *> (n_edges_for_fn (cfun));
+ m_edge_table = new hash_map<edge, vrange_storage *> (n_edges_for_fn (cfun));
- irange **val = m_edge_table->get (e);
+ vrange_storage **val = m_edge_table->get (e);
if (!val)
{
calc_switch_ranges (sw);
val = m_edge_table->get (e);
gcc_checking_assert (val);
}
- r = **val;
+ (*val)->get_vrange (r, TREE_TYPE (gimple_switch_index (sw)));
return true;
}
@@ -150,29 +150,30 @@ gimple_outgoing_range::calc_switch_ranges (gswitch *sw)
// Create/union this case with anything on else on the edge.
int_range_max case_range (low, high);
range_cast (case_range, type);
- irange *&slot = m_edge_table->get_or_insert (e, &existed);
+ vrange_storage *&slot = m_edge_table->get_or_insert (e, &existed);
if (existed)
{
// If this doesn't change the value, move on.
- if (!case_range.union_ (*slot))
+ int_range_max tmp;
+ slot->get_vrange (tmp, type);
+ if (!case_range.union_ (tmp))
continue;
if (slot->fits_p (case_range))
{
- *slot = case_range;
+ slot->set_vrange (case_range);
continue;
}
}
// If there was an existing range and it doesn't fit, we lose the memory.
// It'll get reclaimed when the obstack is freed. This seems less
// intrusive than allocating max ranges for each case.
- slot = m_range_allocator->clone <irange> (case_range);
+ slot = m_range_allocator->clone (case_range);
}
- irange *&slot = m_edge_table->get_or_insert (default_edge, &existed);
+ vrange_storage *&slot = m_edge_table->get_or_insert (default_edge, &existed);
// This should be the first call into this switch.
gcc_checking_assert (!existed);
- irange *dr = m_range_allocator->clone <irange> (default_range);
- slot = dr;
+ slot = m_range_allocator->clone (default_range);
}