Final version I'm pushing. It has a few cleanups, especially nuking the update_global_ranges we had in the ranger code, since it's no longer needed. Now set_range_info does the same thing. Retested on x86-64 Linux and ppc64le Linux. Aldy On Wed, Jul 6, 2022 at 7:10 PM Aldy Hernandez wrote: > > Currently SSA_NAME_RANGE_INFO only handles integer ranges, and loses > half the precision in the process because its use of legacy > value_range's. This patch rewrites all the SSA_NAME_RANGE_INFO > (nonzero bits included) to use the recently contributed > vrange_storage. With it, we'll be able to efficiently save any ranges > supported by ranger in GC memory. Presently this will only be > irange's, but shortly we'll add floating ranges and others to the mix. > > As per the discussion with the trailing_wide_ints adjustments and > vrange_storage, we'll be able to save integer ranges with a maximum of > 5 sub-ranges. This could be adjusted later if more sub-ranges are > needed (unlikely). > > Since this is a behavior changing patch, I would like to take a few > days for discussion, and commit early next week if all goes well. > > A few notes. > > First, we get rid of the SSA_NAME_ANTI_RANGE_P bit in the SSA_NAME > since we store full resolution ranges. Perhaps it could be re-used > for something else. > > The range_info_def struct is gone in favor of an opaque type handled > by vrange_storage. It currently supports irange, but will support > frange, prange, etc, in due time. > > From the looks of it, set_range_info was an update operation despite > its name, as we improved the nonzero bits with each call, even though > we clobbered the ranges. Presumably this was because doing a proper > intersect of ranges lost information with the anti-range hack. We no > longer have this limitation so now we formalize both set_range_info > and set_nonzero_bits to an update operation. After all, we should > never be losing information, but enhancing it whenever possible. This > means, that if folks' finger-memory is not offended, as a follow-up, > I'd like to rename set_nonzero_bits and set_range_info to update_*. > > I have kept the same global API we had in tree-ssanames.h, with the > caveat that all set operations are now update as discussed above. > > There is a 2% performance penalty for evrp and a 3% penalty for VRP > that is coincidentally in line with a previous improvement of the same > amount in the vrange abstraction patchset. Interestingly, this > penalty is mostly due to the wide int to tree dance we keep doing with > irange and legacy. In a first draft of this patch where I was > streaming trees directly, there was actually a small improvement > instead. I hope to get some of the gain back when we move irange's to > wide-ints, though I'm not in a hurry ;-). > > Tested and benchmarked on x86-64 Linux. I will also test on ppc64le > before the final commit. > > Comments welcome. > > gcc/ChangeLog: > > * gimple-range.cc (gimple_ranger::export_global_ranges): Remove > verification against legacy value_range. > * tree-core.h (struct range_info_def): Remove. > (struct irange_storage_slot): New. > (struct tree_base): Remove SSA_NAME_ANTI_RANGE_P documentation. > (struct tree_ssa_name): Add vrange_storage support. > * tree-ssanames.cc (range_info_p): New. > (range_info_fits_p): New. > (range_info_alloc): New. > (range_info_free): New. > (range_info_get_range): New. > (range_info_set_range): New. > (set_range_info_raw): Remove. > (set_range_info): Adjust to use vrange_storage. > (set_nonzero_bits): Same. > (get_nonzero_bits): Same. > (duplicate_ssa_name_range_info): Remove overload taking > value_range_kind. > Rewrite tree overload to use vrange_storage. > (duplicate_ssa_name_fn): Adjust to use vrange_storage. > * tree-ssanames.h (struct range_info_def): Remove. > (set_range_info): Adjust prototype to take vrange. > * tree-vrp.cc (vrp_asserts::remove_range_assertions): Call > duplicate_ssa_name_range_info. > * tree.h (SSA_NAME_ANTI_RANGE_P): Remove. > (SSA_NAME_RANGE_TYPE): Remove. > * value-query.cc (get_ssa_name_range_info): Adjust to use > vrange_storage. > (update_global_range): Use int_range_max. > (get_range_global): Remove as_a. > --- > gcc/gimple-range.cc | 11 +-- > gcc/tree-core.h | 13 +-- > gcc/tree-ssanames.cc | 231 +++++++++++++++++++------------------------ > gcc/tree-ssanames.h | 12 +-- > gcc/tree-vrp.cc | 22 +++-- > gcc/tree.h | 8 -- > gcc/value-query.cc | 21 ++-- > 7 files changed, 135 insertions(+), 183 deletions(-) > > diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc > index 3a9f0b07e79..2a599ce870e 100644 > --- a/gcc/gimple-range.cc > +++ b/gcc/gimple-range.cc > @@ -525,19 +525,10 @@ gimple_ranger::export_global_ranges () > if (!irange::supports_p (TREE_TYPE (name))) > continue; > > - vrange &v = r; > - value_range vr = as_a (v); > print_generic_expr (dump_file, name , TDF_SLIM); > fprintf (dump_file, " : "); > - vr.dump (dump_file); > + r.dump (dump_file); > fprintf (dump_file, "\n"); > - int_range_max same = vr; > - if (same != as_a (v)) > - { > - fprintf (dump_file, " irange : "); > - r.dump (dump_file); > - fprintf (dump_file, "\n"); > - } > } > } > } > diff --git a/gcc/tree-core.h b/gcc/tree-core.h > index ab5fa01e5cb..ea9f281f1cc 100644 > --- a/gcc/tree-core.h > +++ b/gcc/tree-core.h > @@ -33,7 +33,7 @@ struct function; > struct real_value; > struct fixed_value; > struct ptr_info_def; > -struct range_info_def; > +struct irange_storage_slot; > struct die_struct; > > > @@ -1194,9 +1194,6 @@ struct GTY(()) tree_base { > TRANSACTION_EXPR_OUTER in > TRANSACTION_EXPR > > - SSA_NAME_ANTI_RANGE_P in > - SSA_NAME > - > MUST_TAIL_CALL in > CALL_EXPR > > @@ -1594,8 +1591,12 @@ struct GTY(()) tree_ssa_name { > union ssa_name_info_type { > /* Pointer attributes used for alias analysis. */ > struct GTY ((tag ("0"))) ptr_info_def *ptr_info; > - /* Value range attributes used for zero/sign extension elimination. */ > - struct GTY ((tag ("1"))) range_info_def *range_info; > + /* This holds any range info supported by ranger (except ptr_info > + above) and is managed by vrange_storage. */ > + void * GTY ((skip)) range_info; > + /* GTY tag when the range in the range_info slot above satisfies > + irange::supports_type_p. */ > + struct GTY ((tag ("1"))) irange_storage_slot *irange_info; > } GTY ((desc ("%1.typed.type ?" \ > "!POINTER_TYPE_P (TREE_TYPE ((tree)&%1)) : 2"))) info; > > diff --git a/gcc/tree-ssanames.cc b/gcc/tree-ssanames.cc > index bc22ece636a..0df500966ad 100644 > --- a/gcc/tree-ssanames.cc > +++ b/gcc/tree-ssanames.cc > @@ -32,6 +32,7 @@ along with GCC; see the file COPYING3. If not see > #include "cfgloop.h" > #include "tree-scalar-evolution.h" > #include "value-query.h" > +#include "value-range-storage.h" > > /* Rewriting a function into SSA form can create a huge number of SSA_NAMEs, > many of which may be thrown away shortly after their creation if jumps > @@ -71,6 +72,67 @@ unsigned int ssa_name_nodes_created; > #define FREE_SSANAMES(fun) (fun)->gimple_df->free_ssanames > #define FREE_SSANAMES_QUEUE(fun) (fun)->gimple_df->free_ssanames_queue > > +static ggc_vrange_allocator ggc_allocator; > +static vrange_storage vstore (&ggc_allocator); > + > +/* Return TRUE if NAME has global range info. */ > + > +inline bool > +range_info_p (const_tree name) > +{ > + return SSA_NAME_RANGE_INFO (name); > +} > + > +/* Return TRUE if R fits in the global range of NAME. */ > + > +inline bool > +range_info_fits_p (tree name, const vrange &r) > +{ > + gcc_checking_assert (range_info_p (name)); > + void *mem = SSA_NAME_RANGE_INFO (name); > + return vrange_storage::fits_p (mem, r); > +} > + > +/* Allocate a new global range for NAME and set it to R. */ > + > +inline void > +range_info_alloc (tree name, const vrange &r) > +{ > + SSA_NAME_RANGE_INFO (name) = vstore.alloc_slot (r); > +} > + > +/* Free storage allocated for the global range for NAME. */ > + > +inline void > +range_info_free (tree name) > +{ > + void *mem = SSA_NAME_RANGE_INFO (name); > + vstore.free (mem); > +} > + > +/* Return the global range for NAME in R. */ > + > +inline void > +range_info_get_range (tree name, vrange &r) > +{ > + vstore.get_vrange (SSA_NAME_RANGE_INFO (name), r, TREE_TYPE (name)); > +} > + > +/* Set the global range for NAME from R. */ > + > +inline void > +range_info_set_range (tree name, const vrange &r) > +{ > + if (!range_info_p (name) || !range_info_fits_p (name, r)) > + { > + if (range_info_p (name)) > + range_info_free (name); > + > + range_info_alloc (name, r); > + } > + else > + vstore.set_vrange (SSA_NAME_RANGE_INFO (name), r); > +} > > /* Initialize management of SSA_NAMEs to default SIZE. If SIZE is > zero use default. */ > @@ -343,94 +405,34 @@ make_ssa_name_fn (struct function *fn, tree var, gimple *stmt, > return t; > } > > -/* Helper function for set_range_info. > - > - Store range information RANGE_TYPE, MIN, and MAX to tree ssa_name > - NAME. */ > +/* Store range information for NAME, intersecting into an existing > + range if applicable. */ > > void > -set_range_info_raw (tree name, enum value_range_kind range_type, > - const wide_int_ref &min, const wide_int_ref &max) > -{ > - gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); > - gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE); > - range_info_def *ri = SSA_NAME_RANGE_INFO (name); > - unsigned int precision = TYPE_PRECISION (TREE_TYPE (name)); > - > - /* Allocate if not available. */ > - if (ri == NULL) > - { > - size_t size = (sizeof (range_info_def) > - + trailing_wide_ints <3>::extra_size (precision)); > - ri = static_cast (ggc_internal_alloc (size)); > - ri->ints.set_precision (precision); > - SSA_NAME_RANGE_INFO (name) = ri; > - ri->set_nonzero_bits (wi::shwi (-1, precision)); > - } > - > - /* Record the range type. */ > - if (SSA_NAME_RANGE_TYPE (name) != range_type) > - SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE); > - > - /* Set the values. */ > - ri->set_min (min); > - ri->set_max (max); > - > - /* If it is a range, try to improve nonzero_bits from the min/max. */ > - if (range_type == VR_RANGE) > - { > - wide_int xorv = ri->get_min () ^ ri->get_max (); > - if (xorv != 0) > - xorv = wi::mask (precision - wi::clz (xorv), false, precision); > - ri->set_nonzero_bits (ri->get_nonzero_bits () & (ri->get_min () | xorv)); > - } > -} > - > -/* Store range information RANGE_TYPE, MIN, and MAX to tree ssa_name > - NAME while making sure we don't store useless range info. */ > - > -static void > -set_range_info (tree name, enum value_range_kind range_type, > - const wide_int_ref &min, const wide_int_ref &max) > +set_range_info (tree name, const vrange &r) > { > - gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); > + gcc_checking_assert (!POINTER_TYPE_P (TREE_TYPE (name))); > + gcc_checking_assert (!r.undefined_p ()); > > - tree type = TREE_TYPE (name); > - if (range_type == VR_VARYING) > - { > - /* SSA_NAME_RANGE_TYPE can only hold a VR_RANGE or > - VR_ANTI_RANGE. Denormalize VR_VARYING to VR_RANGE. */ > - range_type = VR_RANGE; > - gcc_checking_assert (min == wi::min_value (type)); > - gcc_checking_assert (max == wi::max_value (type)); > - } > + /* If R provides no useful information, just return. We can > + determine this by comparing with a fresh varying node, which is > + guaranteed not to have any supplemental nonzero bits. */ > + if (r == int_range <2> (TREE_TYPE (name))) > + return; > > - /* A range of the entire domain is really no range at all. */ > - if (min == wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type)) > - && max == wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type))) > + if (range_info_p (name)) > { > - range_info_def *ri = SSA_NAME_RANGE_INFO (name); > - if (ri == NULL) > + Value_Range tmp (TREE_TYPE (name)); > + range_info_get_range (name, tmp); > + tmp.intersect (r); > + /* Like update_global_range(), avoid saving undefined. */ > + if (tmp.undefined_p ()) > return; > - if (ri->get_nonzero_bits () == -1) > - { > - ggc_free (ri); > - SSA_NAME_RANGE_INFO (name) = NULL; > - return; > - } > - } > - > - set_range_info_raw (name, range_type, min, max); > -} > > -/* Store range information for NAME from a value_range. */ > - > -void > -set_range_info (tree name, const value_range &vr) > -{ > - wide_int min = wi::to_wide (vr.min ()); > - wide_int max = wi::to_wide (vr.max ()); > - set_range_info (name, vr.kind (), min, max); > + range_info_set_range (name, tmp); > + } > + else > + range_info_set_range (name, r); > } > > /* Set nonnull attribute to pointer NAME. */ > @@ -449,16 +451,10 @@ void > set_nonzero_bits (tree name, const wide_int_ref &mask) > { > gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); > - if (SSA_NAME_RANGE_INFO (name) == NULL) > - { > - if (mask == -1) > - return; > - set_range_info_raw (name, VR_RANGE, > - wi::to_wide (TYPE_MIN_VALUE (TREE_TYPE (name))), > - wi::to_wide (TYPE_MAX_VALUE (TREE_TYPE (name)))); > - } > - range_info_def *ri = SSA_NAME_RANGE_INFO (name); > - ri->set_nonzero_bits (mask); > + > + int_range<2> r (TREE_TYPE (name)); > + r.set_nonzero_bits (mask); > + set_range_info (name, r); > } > > /* Return a widest_int with potentially non-zero bits in SSA_NAME > @@ -482,10 +478,15 @@ get_nonzero_bits (const_tree name) > return wi::shwi (-1, precision); > } > > - range_info_def *ri = SSA_NAME_RANGE_INFO (name); > - if (!ri) > + if (!range_info_p (name)) > return wi::shwi (-1, precision); > > + /* Optimization to get at the nonzero bits because we know the > + storage type. This saves us measurable time compare to going > + through vrange_storage. */ > + gcc_checking_assert (irange::supports_p (TREE_TYPE (name))); > + irange_storage_slot *ri > + = static_cast (SSA_NAME_RANGE_INFO (name)); > return ri->get_nonzero_bits (); > } > > @@ -727,38 +728,18 @@ duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info) > SSA_NAME_PTR_INFO (name) = new_ptr_info; > } > > -/* Creates a duplicate of the range_info_def at RANGE_INFO of type > - RANGE_TYPE for use by the SSA name NAME. */ > -static void > -duplicate_ssa_name_range_info (tree name, enum value_range_kind range_type, > - struct range_info_def *range_info) > -{ > - struct range_info_def *new_range_info; > - > - gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); > - gcc_assert (!SSA_NAME_RANGE_INFO (name)); > - > - if (!range_info) > - return; > - > - unsigned int precision = TYPE_PRECISION (TREE_TYPE (name)); > - size_t size = (sizeof (range_info_def) > - + trailing_wide_ints <3>::extra_size (precision)); > - new_range_info = static_cast (ggc_internal_alloc (size)); > - memcpy (new_range_info, range_info, size); > - > - gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE); > - SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE); > - SSA_NAME_RANGE_INFO (name) = new_range_info; > -} > - > void > duplicate_ssa_name_range_info (tree name, tree src) > { > gcc_checking_assert (!POINTER_TYPE_P (TREE_TYPE (src))); > - duplicate_ssa_name_range_info (name, > - SSA_NAME_RANGE_TYPE (src), > - SSA_NAME_RANGE_INFO (src)); > + gcc_checking_assert (!range_info_p (name)); > + > + if (range_info_p (src)) > + { > + Value_Range src_range (TREE_TYPE (src)); > + range_info_get_range (src, src_range); > + range_info_set_range (name, src_range); > + } > } > > > @@ -776,14 +757,8 @@ duplicate_ssa_name_fn (struct function *fn, tree name, gimple *stmt) > if (old_ptr_info) > duplicate_ssa_name_ptr_info (new_name, old_ptr_info); > } > - else > - { > - struct range_info_def *old_range_info = SSA_NAME_RANGE_INFO (name); > - > - if (old_range_info) > - duplicate_ssa_name_range_info (new_name, SSA_NAME_RANGE_TYPE (name), > - old_range_info); > - } > + else if (range_info_p (name)) > + duplicate_ssa_name_range_info (new_name, name); > > return new_name; > } > diff --git a/gcc/tree-ssanames.h b/gcc/tree-ssanames.h > index 8c419b13e6a..8985f75fc46 100644 > --- a/gcc/tree-ssanames.h > +++ b/gcc/tree-ssanames.h > @@ -45,16 +45,6 @@ struct GTY(()) ptr_info_def > unsigned int misalign; > }; > > -/* Value range information for SSA_NAMEs representing non-pointer variables. */ > - > -struct GTY ((variable_size)) range_info_def { > - /* Minimum, maximum and nonzero bits. */ > - TRAILING_WIDE_INT_ACCESSOR (min, ints, 0) > - TRAILING_WIDE_INT_ACCESSOR (max, ints, 1) > - TRAILING_WIDE_INT_ACCESSOR (nonzero_bits, ints, 2) > - trailing_wide_ints <3> ints; > -}; > - > > #define SSANAMES(fun) (fun)->gimple_df->ssa_names > #define DEFAULT_DEFS(fun) (fun)->gimple_df->default_defs > @@ -67,7 +57,7 @@ struct GTY ((variable_size)) range_info_def { > if (VAR) > > /* Sets the value range to SSA. */ > -extern void set_range_info (tree, const value_range &); > +extern void set_range_info (tree, const vrange &); > extern void set_nonzero_bits (tree, const wide_int_ref &); > extern wide_int get_nonzero_bits (const_tree); > extern bool ssa_name_has_boolean_range (tree); > diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc > index ed881be7e5f..78863ac30c2 100644 > --- a/gcc/tree-vrp.cc > +++ b/gcc/tree-vrp.cc > @@ -3739,16 +3739,18 @@ vrp_asserts::remove_range_assertions () > && all_imm_uses_in_stmt_or_feed_cond (var, stmt, > single_pred (bb))) > { > - /* We could use duplicate_ssa_name_range_info here > - instead of peeking inside SSA_NAME_RANGE_INFO, > - but the aforementioned asserts that the > - destination has no global range. This is > - slated for removal anyhow. */ > - value_range r (TREE_TYPE (lhs), > - SSA_NAME_RANGE_INFO (lhs)->get_min (), > - SSA_NAME_RANGE_INFO (lhs)->get_max (), > - SSA_NAME_RANGE_TYPE (lhs)); > - set_range_info (var, r); > + /* ?? This is a minor wart exposing the internals > + of SSA_NAME_RANGE_INFO in order to maintain > + existing behavior. This is because > + duplicate_ssa_name_range_info below needs a > + NULL destination range. This is all slated for > + removal... */ > + if (SSA_NAME_RANGE_INFO (var)) > + { > + ggc_free (SSA_NAME_RANGE_INFO (var)); > + SSA_NAME_RANGE_INFO (var) = NULL; > + } > + duplicate_ssa_name_range_info (var, lhs); > maybe_set_nonzero_bits (single_pred_edge (bb), var); > } > } > diff --git a/gcc/tree.h b/gcc/tree.h > index 6f6ad5a3a5f..e6564aaccb7 100644 > --- a/gcc/tree.h > +++ b/gcc/tree.h > @@ -2030,14 +2030,6 @@ class auto_suppress_location_wrappers > #define SSA_NAME_PTR_INFO(N) \ > SSA_NAME_CHECK (N)->ssa_name.info.ptr_info > > -/* True if SSA_NAME_RANGE_INFO describes an anti-range. */ > -#define SSA_NAME_ANTI_RANGE_P(N) \ > - SSA_NAME_CHECK (N)->base.static_flag > - > -/* The type of range described by SSA_NAME_RANGE_INFO. */ > -#define SSA_NAME_RANGE_TYPE(N) \ > - (SSA_NAME_ANTI_RANGE_P (N) ? VR_ANTI_RANGE : VR_RANGE) > - > /* Value range info attributes for SSA_NAMEs of non pointer-type variables. */ > #define SSA_NAME_RANGE_INFO(N) \ > SSA_NAME_CHECK (N)->ssa_name.info.range_info > diff --git a/gcc/value-query.cc b/gcc/value-query.cc > index 1d7541ce34f..dd9b6597c1a 100644 > --- a/gcc/value-query.cc > +++ b/gcc/value-query.cc > @@ -32,6 +32,7 @@ along with GCC; see the file COPYING3. If not see > #include "value-query.h" > #include "alloc-pool.h" > #include "gimple-range.h" > +#include "value-range-storage.h" > > // value_query default methods. > > @@ -271,13 +272,13 @@ range_query::get_tree_range (vrange &r, tree expr, gimple *stmt) > // Return the range for NAME from SSA_NAME_RANGE_INFO. > > static inline void > -get_ssa_name_range_info (irange &r, const_tree name) > +get_ssa_name_range_info (vrange &r, const_tree name) > { > tree type = TREE_TYPE (name); > gcc_checking_assert (!POINTER_TYPE_P (type)); > gcc_checking_assert (TREE_CODE (name) == SSA_NAME); > > - range_info_def *ri = SSA_NAME_RANGE_INFO (name); > + void *ri = SSA_NAME_RANGE_INFO (name); > > // Return VR_VARYING for SSA_NAMEs with NULL RANGE_INFO or SSA_NAMEs > // with integral types width > 2 * HOST_BITS_PER_WIDE_INT precision. > @@ -285,9 +286,10 @@ get_ssa_name_range_info (irange &r, const_tree name) > > 2 * HOST_BITS_PER_WIDE_INT)) > r.set_varying (type); > else > - r.set (wide_int_to_tree (type, ri->get_min ()), > - wide_int_to_tree (type, ri->get_max ()), > - SSA_NAME_RANGE_TYPE (name)); > + { > + vrange_storage vstore (NULL); > + vstore.get_vrange (SSA_NAME_RANGE_INFO (name), r, TREE_TYPE (name)); > + } > } > > // Return nonnull attribute of pointer NAME from SSA_NAME_PTR_INFO. > @@ -327,14 +329,14 @@ update_global_range (vrange &r, tree name) > // If a global range already exists, incorporate it. > if (SSA_NAME_RANGE_INFO (name)) > { > - value_range glob; > + int_range_max glob; > get_ssa_name_range_info (glob, name); > r.intersect (glob); > } > if (r.undefined_p ()) > return false; > > - set_range_info (name, as_a (r)); > + set_range_info (name, r); > return true; > } > else if (POINTER_TYPE_P (type)) > @@ -372,7 +374,7 @@ get_range_global (vrange &r, tree name) > r.set_nonzero (type); > else if (INTEGRAL_TYPE_P (type)) > { > - get_ssa_name_range_info (as_a (r), name); > + get_ssa_name_range_info (r, name); > if (r.undefined_p ()) > r.set_varying (type); > } > @@ -387,8 +389,7 @@ get_range_global (vrange &r, tree name) > } > else if (!POINTER_TYPE_P (type) && SSA_NAME_RANGE_INFO (name)) > { > - gcc_checking_assert (irange::supports_p (TREE_TYPE (name))); > - get_ssa_name_range_info (as_a (r), name); > + get_ssa_name_range_info (r, name); > if (r.undefined_p ()) > r.set_varying (type); > } > -- > 2.36.1 >