Message ID  684d495ed931ab7f672e1ccd13f1bc00@redhat.com 

State  New 
Headers  show 
Series 

Related  show 
On Fri, Jun 21, 2019 at 1:41 PM Aldy Hernandez <aldyh@redhat.com> wrote: > > Hi Richard. Hi folks. > > In order to unify the APIs for value_range and irange, we'd like to make > some minor changes to value_range. We believe most of these changes > could go in now, and would prefer so, to get broader testing and > minimize the plethora of changes we drag around on our branch. > > First, introduce a type for VR_VARYING and VR_UNDEFINED. >  > > irange utilizes 0 or more subranges to represent a range, and VARYING > is simply one subrange [MIN, MAX]. value_range represents this with > VR_VARYING, and since there is no type associated with it, we cannot > calculate the lower and upper bounds for the range. There is also a > lack of canonicalness in value range in that VR_VARYING and [MIN, MAX] > are two different representations of the same value. > > We tried to adjust irange to not associate a type with the empty range > [] (representing undefined), but found we were unable to perform all > operations properly. In particular, we cannot invert an empty range. > i.e. invert ( [] ) should produce [MIN, MAX]. Again, we need to have a > type associated with this empty range. > > We'd like to tweak value_range so that set_varying() and set_undefined() > both take a type, and then always set the min/max fields based on that > type. This takes no additional memory in the structure, and is > virtually transparent to all the existing uses of value_range. > > This allows: > 1) invert to be implemented properly for both VARYING and UNDEFINED > by simply changing one to the other. > 2) the type() method to always work without any special casing by > simply returning TREE_TYPE(min) > 3) the new incoming bounds() routines to work trivially for these > cases as well (lbound/ubound, num_pairs(), etc). > > This functionality is provided in the first attached patch. > > Note, the current implementation sets min/max to TREE_TYPE, not to > TYPE_MIN/MAX_VALUE. We can fix this if preferred. How does this work with value_range * vr_values::get_value_range (const_tree var) { static const value_range vr_const_varying (VR_VARYING, NULL, NULL); ... /* If we query the range for a new SSA name return an unmodifiable VARYING. We should get here at most from the substituteandfold stage which will never try to change values. */ if (ver >= num_vr_values) return CONST_CAST (value_range *, &vr_const_varying); ? > Second, enforce canonicalization at value_range build time. >  > > As discussed above, value_range has multiple representations for the > same range. For instance, ~[0,0] is the same as [1,MAX] in unsigned and > [MIN, MAX] is really varying, among others. We found it quite difficult > to make things work, with multiple representations for a given range. > Canonicalizing at build time solves this, as well as removing explicit > set_and_canonicalize() calls throughout. Furthermore, it avoids some > special casing in VRP. > > Along with canonicalizing, we also enforce the existing value_range API > more strongly. For instance, we don't allow setting equivalences for > either VR_VARYING or VR_UNDEFINED. > > This functionality is provided in the second patch. Fair enough. Didn't look at the patch yet, sending separate mails would have been prefered  or are the patches not independent of each other? Note canonicalization performs quite some work so a shortcut set () with just checking the input is already canonicalized would be nice? I wonder you still have antiranges since you can handle > 1 subranges in ranger? > Third, irange on value_range implementation. >  > > The third attached patch shows how we use the above two to implement > irange using value_ranges. value_range would be a dropin replacement > for irange, by just doing the following in range.h: > > +// Enable this to implement irange piggybacking on value_range. > +#define IRANGE_WITH_VALUE_RANGE 1 > + > +#if IRANGE_WITH_VALUE_RANGE > +#include "treevrp.h" > +typedef value_range_base irange; > +typedef value_range_storage irange_storage; > +#define IRANGE_PLAIN VR_RANGE > +#define IRANGE_INVERSE VR_ANTI_RANGE > +#else > ... > > The additions to the value_range API would be mostly the following (full > details in the third attached patch): > > + value_range_base (tree, tree); > + value_range_base (value_range_kind, > + tree type, const wide_int &, const wide_int &); > + value_range_base (tree type, const wide_int &, const wide_int &); > + value_range_base (tree type, const value_range_storage *); > + value_range_base (tree type); > > void set (value_range_kind, tree, tree); > void set (tree); > @@ 77,7 +86,25 @@ public: > bool singleton_p (tree *result = NULL) const; > void dump (FILE *) const; > > + /* Support machinery for irange. */ > + static const unsigned int m_max_pairs = 2; > + static bool supports_type_p (tree type); > + static bool supports_ssa_p (tree ssa); > + static bool supports_p (tree expr); > + void cast (tree); > + bool contains_p (tree) const; > + unsigned num_pairs () const; > + wide_int lower_bound (unsigned = 0) const; > + wide_int upper_bound (unsigned) const; > + wide_int upper_bound () const; > + void invert (); > + void dump () const { dump (stderr); } > + // FIXME: Perhaps rewrite the irange versions to use pointers instead. > + void union_ (const value_range_base &); > + void intersect (const value_range_base &); > + > protected: > + value_range_base normalize_symbolics () const; > > There are no regressions from mainline, and we are catching every one of > our internal ranger tests, with the exception of two that require more > than 2 subranges to work. i.e. Not a regression from mainline just > new functionality we can't get with the limited subranges in value_range. > > Note: Please ignore the value_range_base::normalize_symbolics stuff. > It's likely to go through multiple revisions as Andrew gets the ranger > to deal with symbolics. > > Finally >  > > All these patches are already in our branch, and irange with value_range > can be enabled by #define IRANGE_WITH_VALUE_RANGE 1. > > With these changes, we can successfully build and run the ranger branch > using value_range in place of irange, which indicates a successful API > merge. > > After some minor cleanups, I would like to contribute at least the first > two patches to trunk (VARYING types and the enforced canonicalization). > This will enable us to move forward with trying to integrate the > rangeops code which makes heavy use of the subrange interface, and > allows for broader testing instead of dropping everything in onego. > These two patches stand on their own independently, and IMO provide > useful functionality right now. Works for me. Please send any such patches separately (after cleanup) > I would ideally like to contribute the third patch to mainline, but I do > understand that it currently has no users... although I could rewrite > bits of treevrp to use these new functions (lower_bound, upper_bound, > etc), thus providing a use case ??. However, I do understand if you'd > prefer to keep this last patch on the branch. I'd prefer to keep the last one on the branch indeed. Richard. > Thoughts? > > Aldy (and Andrew)
On 6/24/19 9:24 AM, Richard Biener wrote: > On Fri, Jun 21, 2019 at 1:41 PM Aldy Hernandez <aldyh@redhat.com> wrote: >> >> Hi Richard. Hi folks. >> >> In order to unify the APIs for value_range and irange, we'd like to make >> some minor changes to value_range. We believe most of these changes >> could go in now, and would prefer so, to get broader testing and >> minimize the plethora of changes we drag around on our branch. >> >> First, introduce a type for VR_VARYING and VR_UNDEFINED. >>  >> >> irange utilizes 0 or more subranges to represent a range, and VARYING >> is simply one subrange [MIN, MAX]. value_range represents this with >> VR_VARYING, and since there is no type associated with it, we cannot >> calculate the lower and upper bounds for the range. There is also a >> lack of canonicalness in value range in that VR_VARYING and [MIN, MAX] >> are two different representations of the same value. >> >> We tried to adjust irange to not associate a type with the empty range >> [] (representing undefined), but found we were unable to perform all >> operations properly. In particular, we cannot invert an empty range. >> i.e. invert ( [] ) should produce [MIN, MAX]. Again, we need to have a >> type associated with this empty range. >> >> We'd like to tweak value_range so that set_varying() and set_undefined() >> both take a type, and then always set the min/max fields based on that >> type. This takes no additional memory in the structure, and is >> virtually transparent to all the existing uses of value_range. >> >> This allows: >> 1) invert to be implemented properly for both VARYING and UNDEFINED >> by simply changing one to the other. >> 2) the type() method to always work without any special casing by >> simply returning TREE_TYPE(min) >> 3) the new incoming bounds() routines to work trivially for these >> cases as well (lbound/ubound, num_pairs(), etc). >> >> This functionality is provided in the first attached patch. >> >> Note, the current implementation sets min/max to TREE_TYPE, not to >> TYPE_MIN/MAX_VALUE. We can fix this if preferred. > > How does this work with > > value_range * > vr_values::get_value_range (const_tree var) > { > static const value_range vr_const_varying (VR_VARYING, NULL, NULL); > ... > /* If we query the range for a new SSA name return an unmodifiable VARYING. > We should get here at most from the substituteandfold stage which > will never try to change values. */ > if (ver >= num_vr_values) > return CONST_CAST (value_range *, &vr_const_varying); > > ? Good question. This glaring omission came about after a full round of tests on our branch immediately after posting :). I am currently just allocating a new one each time: > if (ver >= num_vr_values) >  return CONST_CAST (value_range *, &vr_const_varying); > + { > + /* ?? At some point we should find a way to cache varying ranges > + by type. In the tree type itself? */ > + vr = vrp_value_range_pool.allocate (); > + vr>set_varying (type); > + return vr; > + } but we should discuss alternatives. Ideally, we had batted around the idea of keeping the range for varying, cached in the type itself, because of its prevalence. I think Andrew mentioned it would increase the size of type nodes by 4%. Are there that many types that this would incur a significant penalty? Another alternative would be a cache on the side. What are your thoughts? > >> Second, enforce canonicalization at value_range build time. >>  >> >> As discussed above, value_range has multiple representations for the >> same range. For instance, ~[0,0] is the same as [1,MAX] in unsigned and >> [MIN, MAX] is really varying, among others. We found it quite difficult >> to make things work, with multiple representations for a given range. >> Canonicalizing at build time solves this, as well as removing explicit >> set_and_canonicalize() calls throughout. Furthermore, it avoids some >> special casing in VRP. >> >> Along with canonicalizing, we also enforce the existing value_range API >> more strongly. For instance, we don't allow setting equivalences for >> either VR_VARYING or VR_UNDEFINED. >> >> This functionality is provided in the second patch. > > Fair enough. Didn't look at the patch yet, sending separate mails would have > been prefered  or are the patches not independent of each other? Note Well, the varying/undefined patch goes first, but the patches are conceptually independent of each other. I posted all so you could see how everything fit together. > canonicalization performs quite some work so a shortcut > set () with just checking the input is already canonicalized would be nice? > > I wonder you still have antiranges since you can handle > 1 subranges > in ranger? The ranger uses the more abstract API of looking at upper_bound(), lower_bound() and num_pairs(). It has not knowledge of antiranges, or the internal representation. So you can have your cake and eat it too :). value_range can have its anti ranges, and the ranger can work with either or, while looking at things from a higher level. > >> Third, irange on value_range implementation. >>  >> >> The third attached patch shows how we use the above two to implement >> irange using value_ranges. value_range would be a dropin replacement >> for irange, by just doing the following in range.h: >> >> +// Enable this to implement irange piggybacking on value_range. >> +#define IRANGE_WITH_VALUE_RANGE 1 >> + >> +#if IRANGE_WITH_VALUE_RANGE >> +#include "treevrp.h" >> +typedef value_range_base irange; >> +typedef value_range_storage irange_storage; >> +#define IRANGE_PLAIN VR_RANGE >> +#define IRANGE_INVERSE VR_ANTI_RANGE >> +#else >> ... >> >> The additions to the value_range API would be mostly the following (full >> details in the third attached patch): >> >> + value_range_base (tree, tree); >> + value_range_base (value_range_kind, >> + tree type, const wide_int &, const wide_int &); >> + value_range_base (tree type, const wide_int &, const wide_int &); >> + value_range_base (tree type, const value_range_storage *); >> + value_range_base (tree type); >> >> void set (value_range_kind, tree, tree); >> void set (tree); >> @@ 77,7 +86,25 @@ public: >> bool singleton_p (tree *result = NULL) const; >> void dump (FILE *) const; >> >> + /* Support machinery for irange. */ >> + static const unsigned int m_max_pairs = 2; >> + static bool supports_type_p (tree type); >> + static bool supports_ssa_p (tree ssa); >> + static bool supports_p (tree expr); >> + void cast (tree); >> + bool contains_p (tree) const; >> + unsigned num_pairs () const; >> + wide_int lower_bound (unsigned = 0) const; >> + wide_int upper_bound (unsigned) const; >> + wide_int upper_bound () const; >> + void invert (); >> + void dump () const { dump (stderr); } >> + // FIXME: Perhaps rewrite the irange versions to use pointers instead. >> + void union_ (const value_range_base &); >> + void intersect (const value_range_base &); >> + >> protected: >> + value_range_base normalize_symbolics () const; >> >> There are no regressions from mainline, and we are catching every one of >> our internal ranger tests, with the exception of two that require more >> than 2 subranges to work. i.e. Not a regression from mainline just >> new functionality we can't get with the limited subranges in value_range. >> >> Note: Please ignore the value_range_base::normalize_symbolics stuff. >> It's likely to go through multiple revisions as Andrew gets the ranger >> to deal with symbolics. >> >> Finally >>  >> >> All these patches are already in our branch, and irange with value_range >> can be enabled by #define IRANGE_WITH_VALUE_RANGE 1. >> >> With these changes, we can successfully build and run the ranger branch >> using value_range in place of irange, which indicates a successful API >> merge. >> >> After some minor cleanups, I would like to contribute at least the first >> two patches to trunk (VARYING types and the enforced canonicalization). >> This will enable us to move forward with trying to integrate the >> rangeops code which makes heavy use of the subrange interface, and >> allows for broader testing instead of dropping everything in onego. >> These two patches stand on their own independently, and IMO provide >> useful functionality right now. > > Works for me. Please send any such patches separately (after cleanup) Ok, I am shuffling even more things in our branch in preparation for future work. When I'm done with that and can verify that things work with value_range, irange, VRP, and the ranger, I will start posting pieces independently. I just wanted to make sure we all agreed on the general approach. > >> I would ideally like to contribute the third patch to mainline, but I do >> understand that it currently has no users... although I could rewrite >> bits of treevrp to use these new functions (lower_bound, upper_bound, >> etc), thus providing a use case ??. However, I do understand if you'd >> prefer to keep this last patch on the branch. > > I'd prefer to keep the last one on the branch indeed. Alrighty. Thanks. Aldy > > Richard. > >> Thoughts? >> >> Aldy (and Andrew)
On Tue, Jun 25, 2019 at 10:05 AM Aldy Hernandez <aldyh@redhat.com> wrote: > > > > On 6/24/19 9:24 AM, Richard Biener wrote: > > On Fri, Jun 21, 2019 at 1:41 PM Aldy Hernandez <aldyh@redhat.com> wrote: > >> > >> Hi Richard. Hi folks. > >> > >> In order to unify the APIs for value_range and irange, we'd like to make > >> some minor changes to value_range. We believe most of these changes > >> could go in now, and would prefer so, to get broader testing and > >> minimize the plethora of changes we drag around on our branch. > >> > >> First, introduce a type for VR_VARYING and VR_UNDEFINED. > >>  > >> > >> irange utilizes 0 or more subranges to represent a range, and VARYING > >> is simply one subrange [MIN, MAX]. value_range represents this with > >> VR_VARYING, and since there is no type associated with it, we cannot > >> calculate the lower and upper bounds for the range. There is also a > >> lack of canonicalness in value range in that VR_VARYING and [MIN, MAX] > >> are two different representations of the same value. > >> > >> We tried to adjust irange to not associate a type with the empty range > >> [] (representing undefined), but found we were unable to perform all > >> operations properly. In particular, we cannot invert an empty range. > >> i.e. invert ( [] ) should produce [MIN, MAX]. Again, we need to have a > >> type associated with this empty range. > >> > >> We'd like to tweak value_range so that set_varying() and set_undefined() > >> both take a type, and then always set the min/max fields based on that > >> type. This takes no additional memory in the structure, and is > >> virtually transparent to all the existing uses of value_range. > >> > >> This allows: > >> 1) invert to be implemented properly for both VARYING and UNDEFINED > >> by simply changing one to the other. > >> 2) the type() method to always work without any special casing by > >> simply returning TREE_TYPE(min) > >> 3) the new incoming bounds() routines to work trivially for these > >> cases as well (lbound/ubound, num_pairs(), etc). > >> > >> This functionality is provided in the first attached patch. > >> > >> Note, the current implementation sets min/max to TREE_TYPE, not to > >> TYPE_MIN/MAX_VALUE. We can fix this if preferred. > > > > How does this work with > > > > value_range * > > vr_values::get_value_range (const_tree var) > > { > > static const value_range vr_const_varying (VR_VARYING, NULL, NULL); > > ... > > /* If we query the range for a new SSA name return an unmodifiable VARYING. > > We should get here at most from the substituteandfold stage which > > will never try to change values. */ > > if (ver >= num_vr_values) > > return CONST_CAST (value_range *, &vr_const_varying); > > > > ? > > Good question. This glaring omission came about after a full round of > tests on our branch immediately after posting :). > > I am currently just allocating a new one each time: > > > if (ver >= num_vr_values) > >  return CONST_CAST (value_range *, &vr_const_varying); > > + { > > + /* ?? At some point we should find a way to cache varying ranges > > + by type. In the tree type itself? */ > > + vr = vrp_value_range_pool.allocate (); > > + vr>set_varying (type); > > + return vr; > > + } > > but we should discuss alternatives. Ideally, we had batted around the > idea of keeping the range for varying, cached in the type itself, > because of its prevalence. I think Andrew mentioned it would increase > the size of type nodes by 4%. Are there that many types that this would > incur a significant penalty? Another alternative would be a cache on > the side. What are your thoughts? It's not that the static const varying isn't a hack  it's done to avoid growing the lattice dynamically as substitution / folding allocates new SSA names (because it's a waste of time at that point). One possibility is to simply return NULL from ::get_value_range and treat that as VARYING in all callers. But back in time that was erorrprone so I settled with the convenient global VARYING. I don't like any kind of "caching" of VARYINGs per type too much. If necessary then it should be done on the side, definitely _not_ in tree_type. > > > >> Second, enforce canonicalization at value_range build time. > >>  > >> > >> As discussed above, value_range has multiple representations for the > >> same range. For instance, ~[0,0] is the same as [1,MAX] in unsigned and > >> [MIN, MAX] is really varying, among others. We found it quite difficult > >> to make things work, with multiple representations for a given range. > >> Canonicalizing at build time solves this, as well as removing explicit > >> set_and_canonicalize() calls throughout. Furthermore, it avoids some > >> special casing in VRP. > >> > >> Along with canonicalizing, we also enforce the existing value_range API > >> more strongly. For instance, we don't allow setting equivalences for > >> either VR_VARYING or VR_UNDEFINED. > >> > >> This functionality is provided in the second patch. > > > > Fair enough. Didn't look at the patch yet, sending separate mails would have > > been prefered  or are the patches not independent of each other? Note > > Well, the varying/undefined patch goes first, but the patches are > conceptually independent of each other. I posted all so you could see > how everything fit together. > > > canonicalization performs quite some work so a shortcut > > set () with just checking the input is already canonicalized would be nice? > > > > I wonder you still have antiranges since you can handle > 1 subranges > > in ranger? > > The ranger uses the more abstract API of looking at upper_bound(), > lower_bound() and num_pairs(). It has not knowledge of antiranges, or > the internal representation. So you can have your cake and eat it too > :). value_range can have its anti ranges, and the ranger can work with > either or, while looking at things from a higher level. OK. > > > >> Third, irange on value_range implementation. > >>  > >> > >> The third attached patch shows how we use the above two to implement > >> irange using value_ranges. value_range would be a dropin replacement > >> for irange, by just doing the following in range.h: > >> > >> +// Enable this to implement irange piggybacking on value_range. > >> +#define IRANGE_WITH_VALUE_RANGE 1 > >> + > >> +#if IRANGE_WITH_VALUE_RANGE > >> +#include "treevrp.h" > >> +typedef value_range_base irange; > >> +typedef value_range_storage irange_storage; > >> +#define IRANGE_PLAIN VR_RANGE > >> +#define IRANGE_INVERSE VR_ANTI_RANGE > >> +#else > >> ... > >> > >> The additions to the value_range API would be mostly the following (full > >> details in the third attached patch): > >> > >> + value_range_base (tree, tree); > >> + value_range_base (value_range_kind, > >> + tree type, const wide_int &, const wide_int &); > >> + value_range_base (tree type, const wide_int &, const wide_int &); > >> + value_range_base (tree type, const value_range_storage *); > >> + value_range_base (tree type); > >> > >> void set (value_range_kind, tree, tree); > >> void set (tree); > >> @@ 77,7 +86,25 @@ public: > >> bool singleton_p (tree *result = NULL) const; > >> void dump (FILE *) const; > >> > >> + /* Support machinery for irange. */ > >> + static const unsigned int m_max_pairs = 2; > >> + static bool supports_type_p (tree type); > >> + static bool supports_ssa_p (tree ssa); > >> + static bool supports_p (tree expr); > >> + void cast (tree); > >> + bool contains_p (tree) const; > >> + unsigned num_pairs () const; > >> + wide_int lower_bound (unsigned = 0) const; > >> + wide_int upper_bound (unsigned) const; > >> + wide_int upper_bound () const; > >> + void invert (); > >> + void dump () const { dump (stderr); } > >> + // FIXME: Perhaps rewrite the irange versions to use pointers instead. > >> + void union_ (const value_range_base &); > >> + void intersect (const value_range_base &); > >> + > >> protected: > >> + value_range_base normalize_symbolics () const; > >> > >> There are no regressions from mainline, and we are catching every one of > >> our internal ranger tests, with the exception of two that require more > >> than 2 subranges to work. i.e. Not a regression from mainline just > >> new functionality we can't get with the limited subranges in value_range. > >> > >> Note: Please ignore the value_range_base::normalize_symbolics stuff. > >> It's likely to go through multiple revisions as Andrew gets the ranger > >> to deal with symbolics. > >> > >> Finally > >>  > >> > >> All these patches are already in our branch, and irange with value_range > >> can be enabled by #define IRANGE_WITH_VALUE_RANGE 1. > >> > >> With these changes, we can successfully build and run the ranger branch > >> using value_range in place of irange, which indicates a successful API > >> merge. > >> > >> After some minor cleanups, I would like to contribute at least the first > >> two patches to trunk (VARYING types and the enforced canonicalization). > >> This will enable us to move forward with trying to integrate the > >> rangeops code which makes heavy use of the subrange interface, and > >> allows for broader testing instead of dropping everything in onego. > >> These two patches stand on their own independently, and IMO provide > >> useful functionality right now. > > > > Works for me. Please send any such patches separately (after cleanup) > > Ok, I am shuffling even more things in our branch in preparation for > future work. When I'm done with that and can verify that things work > with value_range, irange, VRP, and the ranger, I will start posting > pieces independently. I just wanted to make sure we all agreed on the > general approach. Sure. Thanks, Richard. > > > >> I would ideally like to contribute the third patch to mainline, but I do > >> understand that it currently has no users... although I could rewrite > >> bits of treevrp to use these new functions (lower_bound, upper_bound, > >> etc), thus providing a use case ??. However, I do understand if you'd > >> prefer to keep this last patch on the branch. > > > > I'd prefer to keep the last one on the branch indeed. > > Alrighty. > > Thanks. > Aldy > > > > > Richard. > > > >> Thoughts? > >> > >> Aldy (and Andrew)
commit 1d7d379b3f8b23e5b378488f5dc1e8cc3225d350 Author: aldyh <aldyh@138bc75d0d040410961f82ee72b054a4> Date: Tue Jun 18 22:44:57 2019 +0000 irange on value_range implementation. diff git a/gcc/treevrp.h b/gcc/treevrp.h index 4af1bc99da9..80fcc4aee26 100644  a/gcc/treevrp.h +++ b/gcc/treevrp.h @@ 35,14 +35,23 @@ enum value_range_kind VR_LAST }; +class value_range_storage; /* Range of values that can be associated with an SSA_NAME after VRP has executed. */ class GTY((for_user)) value_range_base { + friend value_range_storage; + friend void irange_tests (); public: value_range_base (); value_range_base (value_range_kind, tree, tree); + value_range_base (tree, tree); + value_range_base (value_range_kind, + tree type, const wide_int &, const wide_int &); + value_range_base (tree type, const wide_int &, const wide_int &); + value_range_base (tree type, const value_range_storage *); + value_range_base (tree type); void set (value_range_kind, tree, tree); void set (tree); @@ 77,7 +86,25 @@ public: bool singleton_p (tree *result = NULL) const; void dump (FILE *) const; + /* Support machinery for irange. */ + static const unsigned int m_max_pairs = 2; + static bool supports_type_p (tree type); + static bool supports_ssa_p (tree ssa); + static bool supports_p (tree expr); + void cast (tree); + bool contains_p (tree) const; + unsigned num_pairs () const; + wide_int lower_bound (unsigned = 0) const; + wide_int upper_bound (unsigned) const; + wide_int upper_bound () const; + void invert (); + void dump () const { dump (stderr); } + // FIXME: Perhaps rewrite the irange versions to use pointers instead. + void union_ (const value_range_base &); + void intersect (const value_range_base &); + protected: + value_range_base normalize_symbolics () const; void check (); static value_range_base union_helper (const value_range_base *, const value_range_base *); @@ 156,6 +183,29 @@ class GTY((user)) value_range : public value_range_base bitmap m_equiv; }; +class value_range_storage +{ + friend class value_range_base; +public: + static value_range_storage *alloc (const value_range_base &r) + { + value_range_storage *p = ggc_alloc<value_range_storage> (); + p>set (r); + return p; + } + bool update (const value_range_base &r) + { + set (r); + return true; + } +private: + void set (const value_range_base &r) + { + m_vr = r; + } + value_range_base m_vr; +}; + inline value_range_base::value_range_base () { @@ 267,11 +317,11 @@ extern bool range_int_cst_singleton_p (const value_range_base *); extern int compare_values (tree, tree); extern int compare_values_warnv (tree, tree, bool *); extern int operand_less_p (tree, tree); extern bool vrp_val_is_min (const_tree); extern bool vrp_val_is_max (const_tree); +extern bool vrp_val_is_min (const_tree, bool handle_pointers = false); +extern bool vrp_val_is_max (const_tree, bool handle_pointers = false); extern tree vrp_val_min (const_tree); extern tree vrp_val_max (const_tree); +extern tree vrp_val_min (const_tree, bool handle_pointers = false); +extern tree vrp_val_max (const_tree, bool handle_pointers = false); extern void extract_range_from_unary_expr (value_range_base *vr, enum tree_code code, diff git a/gcc/treevrp.c b/gcc/treevrp.c index 8a3bd2599a5..b4d5698823e 100644  a/gcc/treevrp.c +++ b/gcc/treevrp.c @@ 71,6 +71,11 @@ along with GCC; see the file COPYING3. If not see #include "wideintrange.h" #include "grange.h" +static bool +ranges_from_anti_range (const value_range_base *ar, + value_range_base *vr0, value_range_base *vr1, + bool handle_pointers = false); + /* Set of SSA names found live during the RPO traversal of the function for still active basicblocks. */ static sbitmap *live; @@ 136,6 +141,42 @@ value_range::value_range (const value_range_base &other) set (other.kind (), other.min(), other.max (), NULL); } +value_range_base::value_range_base (tree type) +{ + set_varying (type); +} + +value_range_base::value_range_base (enum value_range_kind kind, + tree type, + const wide_int &wmin, + const wide_int &wmax) +{ + tree min = wide_int_to_tree (type, wmin); + tree max = wide_int_to_tree (type, wmax); + gcc_assert (kind == VR_RANGE  kind == VR_ANTI_RANGE); + set_and_canonicalize (kind, min, max); +} + +value_range_base::value_range_base (tree type, + const wide_int &wmin, + const wide_int &wmax) +{ + tree min = wide_int_to_tree (type, wmin); + tree max = wide_int_to_tree (type, wmax); + set_and_canonicalize (VR_RANGE, min, max); +} + +value_range_base::value_range_base (tree min, tree max) +{ + set (VR_RANGE, min, max); +} + +value_range_base::value_range_base (tree type ATTRIBUTE_UNUSED, + const value_range_storage *stow) +{ + *this = stow>m_vr; +} + /* Like set, but keep the equivalences in place. */ void @@ 334,6 +375,13 @@ value_range::equiv_add (const_tree var, bool value_range_base::singleton_p (tree *result) const { + if (m_kind == VR_ANTI_RANGE) + { + value_range_base vr0, vr1; + return (ranges_from_anti_range (this, &vr0, &vr1, true) + && vr1.undefined_p () + && vr0.singleton_p (result)); + } if (m_kind == VR_RANGE && vrp_operand_equal_p (min (), max ()) && is_gimple_min_invariant (min ())) @@ 520,10 +568,18 @@ static assert_locus **asserts_for; /* Return the maximum value for TYPE. */ tree vrp_val_max (const_tree type) +vrp_val_max (const_tree type, bool handle_pointers) { if (!INTEGRAL_TYPE_P (type))  return NULL_TREE; + { + if (POINTER_TYPE_P (type) && handle_pointers) + { + wide_int max = wi::max_value (TYPE_PRECISION (type), + TYPE_SIGN (type)); + return wide_int_to_tree (const_cast<tree> (type), max); + } + return NULL_TREE; + } return TYPE_MAX_VALUE (type); } @@ 531,10 +587,14 @@ vrp_val_max (const_tree type) /* Return the minimum value for TYPE. */ tree vrp_val_min (const_tree type) +vrp_val_min (const_tree type, bool handle_pointers) { if (!INTEGRAL_TYPE_P (type))  return NULL_TREE; + { + if (POINTER_TYPE_P (type) && handle_pointers) + return build_zero_cst (const_cast<tree> (type)); + return NULL_TREE; + } return TYPE_MIN_VALUE (type); } @@ 545,9 +605,9 @@ vrp_val_min (const_tree type) is not == to the integer constant with the same value in the type. */ bool vrp_val_is_max (const_tree val) +vrp_val_is_max (const_tree val, bool handle_pointers) {  tree type_max = vrp_val_max (TREE_TYPE (val)); + tree type_max = vrp_val_max (TREE_TYPE (val), handle_pointers); return (val == type_max  (type_max != NULL_TREE && operand_equal_p (val, type_max, 0))); @@ 556,9 +616,9 @@ vrp_val_is_max (const_tree val) /* Return whether VAL is equal to the minimum value of its type. */ bool vrp_val_is_min (const_tree val) +vrp_val_is_min (const_tree val, bool handle_pointers) {  tree type_min = vrp_val_min (TREE_TYPE (val)); + tree type_min = vrp_val_min (TREE_TYPE (val), handle_pointers); return (val == type_min  (type_min != NULL_TREE && operand_equal_p (val, type_min, 0))); @@ 652,7 +712,7 @@ value_range_base::set_and_canonicalize (enum value_range_kind kind, { if (kind == VR_UNDEFINED) {  gcc_assert (TYPE_P (min)); + gcc_assert (!min  TYPE_P (min)); set_undefined (min); return; } @@ 704,11 +764,11 @@ value_range_base::set_and_canonicalize (enum value_range_kind kind, } /* Antiranges that can be represented as ranges should be so. */ + tree type = TREE_TYPE (min); if (kind == VR_ANTI_RANGE) { /* For fstrictenums we may receive outofrange ranges so consider values < INF and values > INF as INF/INF as well. */  tree type = TREE_TYPE (min); bool is_min = (INTEGRAL_TYPE_P (type) && tree_int_cst_compare (min, TYPE_MIN_VALUE (type)) <= 0); bool is_max = (INTEGRAL_TYPE_P (type) @@ 754,7 +814,6 @@ value_range_base::set_and_canonicalize (enum value_range_kind kind, /* FIXME: The ranger chops off outofbound ranges for fstrictenums. Do the same here. This is only here to make sure the ranger and VRP compare correctly. */  tree type = TREE_TYPE (min); if (TREE_CODE (type) == ENUMERAL_TYPE && kind == VR_RANGE) { @@ 1209,8 +1279,14 @@ vrp_set_zero_nonzero_bits (const tree expr_type, static bool ranges_from_anti_range (const value_range_base *ar,  value_range_base *vr0, value_range_base *vr1) + value_range_base *vr0, value_range_base *vr1, + bool handle_pointers) { + /* ?? This function is called multiple times from num_pairs, + lower_bound, and upper_bound. We should either memoize this, or + rewrite the callers in such a way that we're not recalculating + this constantly. */ + tree type = ar>type (); vr0>set_undefined (type); @@ 1222,18 +1298,18 @@ ranges_from_anti_range (const value_range_base *ar, if (ar>kind () != VR_ANTI_RANGE  TREE_CODE (ar>min ()) != INTEGER_CST  TREE_CODE (ar>max ()) != INTEGER_CST   !vrp_val_min (type)   !vrp_val_max (type)) +  !vrp_val_min (type, handle_pointers) +  !vrp_val_max (type, handle_pointers)) return false;  if (tree_int_cst_lt (vrp_val_min (type), ar>min ())) + if (tree_int_cst_lt (vrp_val_min (type, handle_pointers), ar>min ())) vr0>set (VR_RANGE,  vrp_val_min (type), + vrp_val_min (type, handle_pointers), wide_int_to_tree (type, wi::to_wide (ar>min ())  1));  if (tree_int_cst_lt (ar>max (), vrp_val_max (type))) + if (tree_int_cst_lt (ar>max (), vrp_val_max (type, handle_pointers))) vr1>set (VR_RANGE, wide_int_to_tree (type, wi::to_wide (ar>max ()) + 1),  vrp_val_max (type)); + vrp_val_max (type, handle_pointers)); if (vr0>undefined_p ()) { *vr0 = *vr1; @@ 6547,6 +6623,197 @@ value_range::union_ (const value_range *other) } } +value_range_base +value_range_base::normalize_symbolics () const +{ + tree ttype = type (); + bool min_symbolic = is_gimple_min_invariant (min ()); + bool max_symbolic = is_gimple_min_invariant (max ()); + if (varying_p ()  undefined_p ()  (!min_symbolic && !max_symbolic)) + return *this; + + // [SYM, SYM] > VARYING + if (min_symbolic && max_symbolic) + goto varying; + if (kind () == VR_RANGE) + { + // [SYM, NUM] > [MIN, NUM] + if (min_symbolic) + return value_range_base (VR_RANGE, vrp_val_min (ttype), max ()); + // [NUM, SYM] > [NUM, +MAX] + return value_range_base (VR_RANGE, min (), vrp_val_max (ttype)); + } + gcc_assert (kind () == VR_ANTI_RANGE); + // ~[SYM, NUM] > [NUM + 1, +MAX] + if (min_symbolic) + { + if (!vrp_val_is_max (max ())) + { + tree n = wide_int_to_tree (ttype, wi::to_wide (max ()) + 1); + return value_range_base (VR_RANGE, n, vrp_val_max (ttype)); + } + goto varying; + } + // ~[NUM, SYM] > [MIN, NUM  1] + if (!vrp_val_is_min (min ())) + { + tree n = wide_int_to_tree (ttype, wi::to_wide (min ())  1); + return value_range_base (VR_RANGE, vrp_val_min (ttype), n); + } + varying: + value_range_base tmp; + tmp.set_varying (ttype); + return tmp; +} + +unsigned +value_range_base::num_pairs () const +{ + if (undefined_p ()) + return 0; + if (varying_p ()) + return 1; + if (symbolic_p ()) + return normalize_symbolics ().num_pairs (); + if (m_kind == VR_ANTI_RANGE) + { + value_range_base vr0, vr1; + gcc_assert (ranges_from_anti_range (this, &vr0, &vr1, true)); + if (vr1.undefined_p ()) + return 1; + return 2; + } + return 1; +} + +wide_int +value_range_base::lower_bound (unsigned pair) const +{ + if (symbolic_p ()) + return normalize_symbolics ().lower_bound (pair); + + gcc_assert (!undefined_p ()); + gcc_assert (pair + 1 <= num_pairs ()); + tree t = NULL; + if (varying_p ()) + t = vrp_val_min (type (), true); + else if (m_kind == VR_RANGE) + t = m_min; + else if (m_kind == VR_ANTI_RANGE) + { + value_range_base vr0, vr1; + gcc_assert (ranges_from_anti_range (this, &vr0, &vr1, true)); + if (pair == 0) + t = vr0.min (); + else if (pair == 1) + t = vr1.min (); + else + gcc_unreachable (); + } + return wi::to_wide (t); +} + +wide_int +value_range_base::upper_bound (unsigned pair) const +{ + if (symbolic_p ()) + return normalize_symbolics ().upper_bound (pair); + + gcc_assert (!undefined_p ()); + gcc_assert (pair + 1 <= num_pairs ()); + tree t = NULL; + if (varying_p ()) + t = vrp_val_max (type (), true); + else if (m_kind == VR_RANGE) + t = m_max; + else if (m_kind == VR_ANTI_RANGE) + { + value_range_base vr0, vr1; + gcc_assert (ranges_from_anti_range (this, &vr0, &vr1, true)); + if (pair == 0) + t = vr0.max (); + else if (pair == 1) + t = vr1.max (); + else + gcc_unreachable (); + } + return wi::to_wide (t); +} + +wide_int +value_range_base::upper_bound () const +{ + unsigned pairs = num_pairs (); + gcc_assert (pairs > 0); + return upper_bound (pairs  1); +} + +void +value_range_base::cast (tree typ) +{ + value_range_base tem; + enum ranges_mode save = flag_ranges_mode; + /* Avoid infinite recursion in the ranger vs vrp checking code. */ + flag_ranges_mode = RANGES_VRP; + /* At some point we should inline all of the CONVERT_EXPR code from + extract_range_from_unary_expr here. */ + extract_range_from_unary_expr (&tem, CONVERT_EXPR, typ, this, type ()); + flag_ranges_mode = save; + *this = tem; +} + +/* Return TRUE if range contains INTEGER_CST. */ + +bool +value_range_base::contains_p (tree cst) const +{ + gcc_assert (TREE_CODE (cst) == INTEGER_CST); + if (symbolic_p ()) + return normalize_symbolics ().contains_p (cst); + return value_inside_range (cst) == 1; +} + +void +value_range_base::invert () +{ + if (undefined_p ()) + set_varying (type ()); + else if (varying_p ()) + set_undefined (type ()); + else if (m_kind == VR_RANGE) + m_kind = VR_ANTI_RANGE; + else if (m_kind == VR_ANTI_RANGE) + m_kind = VR_RANGE; + else + gcc_unreachable (); +} + +void +value_range_base::union_ (const value_range_base &r) +{ + /* Disable details for now, because it makes the ranger dump + unnecessarily verbose. */ + bool details = dump_flags & TDF_DETAILS; + if (details) + dump_flags &= ~TDF_DETAILS; + union_ (&r); + if (details) + dump_flags = TDF_DETAILS; +} + +void +value_range_base::intersect (const value_range_base &r) +{ + /* Disable details for now, because it makes the ranger dump + unnecessarily verbose. */ + bool details = dump_flags & TDF_DETAILS; + if (details) + dump_flags &= ~TDF_DETAILS; + intersect (&r); + if (details) + dump_flags = TDF_DETAILS; +} + /* Visit all arguments for PHI node PHI that flow through executable edges. If a valid value range can be derived from all the incoming value ranges, set a new range for the LHS of PHI. */ @@ 7241,3 +7512,24 @@ determine_value_range (tree expr, wide_int *min, wide_int *max) return VR_VARYING; } + +#if IRANGE_WITH_VALUE_RANGE +irange +value_range_to_irange (tree type ATTRIBUTE_UNUSED, const value_range_base &vr) +{ + return vr; +} + +irange +value_range_to_irange (tree type, enum value_range_kind kind, + const wide_int &min, const wide_int &max) +{ + return irange (kind, type, min, max); +} + +value_range_base +irange_to_value_range (const irange &ir) +{ + return ir; +} +#endif // IRANGE_TO_VALUE_RANGE diff git a/gcc/vrvalues.c b/gcc/vrvalues.c index 6bc62f46d2a..def5a163e90 100644  a/gcc/vrvalues.c +++ b/gcc/vrvalues.c @@ 105,7 +105,7 @@ set_value_range_to_truthvalue (value_range *vr, tree type) value_range * vr_values::get_value_range (const_tree var) {  static const value_range vr_const_varying (VR_VARYING, NULL, NULL); + tree type = TREE_TYPE (var); value_range *vr; tree sym; unsigned ver = SSA_NAME_VERSION (var); @@ 118,7 +118,13 @@ vr_values::get_value_range (const_tree var) We should get here at most from the substituteandfold stage which will never try to change values. */ if (ver >= num_vr_values)  return CONST_CAST (value_range *, &vr_const_varying); + { + /* ?? At some point we should find a way to cache varying ranges + by type. In the tree type itself? */ + vr = vrp_value_range_pool.allocate (); + vr>set_varying (type); + return vr; + } vr = vr_value[ver]; if (vr) @@ 126,11 +132,16 @@ vr_values::get_value_range (const_tree var) /* After propagation finished do not allocate new valueranges. */ if (values_propagated)  return CONST_CAST (value_range *, &vr_const_varying); + { + /* See note about caching varying above. */ + vr = vrp_value_range_pool.allocate (); + vr>set_varying (type); + return vr; + } /* Create a default value range. */ vr_value[ver] = vr = vrp_value_range_pool.allocate ();  vr>set_undefined (); + vr>set_undefined (type); /* If VAR is a default definition of a parameter, the variable can take any value in VAR's type. */ @@ 179,9 +190,7 @@ vr_values::set_defs_to_varying (gimple *stmt) FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF) { value_range *vr = get_value_range (def);  /* Avoid writing to vr_const_varying get_value_range may return. */  if (!vr>varying_p ())  vr>set_varying (TREE_TYPE (def)); + vr>set_varying (TREE_TYPE (def)); } } @@ 995,6 +1004,9 @@ check_for_binary_op_overflow (enum tree_code subcode, tree type, tree op1, irange &ir1, bool *ovf) { + if (ir0.undefined_p ()  ir1.undefined_p ()) + return false; + tree vr0min = wide_int_to_tree (TREE_TYPE (op0), ir0.lower_bound ()); tree vr0max = wide_int_to_tree (TREE_TYPE (op0), ir0.upper_bound ()); tree vr1min = wide_int_to_tree (TREE_TYPE (op1), ir1.lower_bound ()); @@ 3948,6 +3960,12 @@ range_misc::simplify_float_conversion_using_ranges (gimple_stmt_iterator *gsi, tree tem; gassign *conv; + /* An undefined means this statement is unreachable. Bail to avoid + calculating anything in range_fits_type_p below. Perhaps we + should generically bail from simplify_stmt_using_ranges. */ + if (ir.undefined_p ()) + return false; + /* First check if we can use a signed type in place of an unsigned. */ scalar_int_mode rhs_mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (rhs1)); if (TYPE_UNSIGNED (TREE_TYPE (rhs1))