value_range and irange unification
diff mbox series

Message ID 684d495e-d931-ab7f-672e-1ccd13f1bc00@redhat.com
State New
Headers show
Series
  • value_range and irange unification
Related show

Commit Message

Aldy Hernandez June 21, 2019, 11:41 a.m. UTC
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 sub-ranges 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.

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.

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 drop-in 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 "tree-vrp.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 sub-ranges to work.  i.e. Not a regression from mainline-- just 
new functionality we can't get with the limited sub-ranges 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 
range-ops code which makes heavy use of the subrange interface, and 
allows for broader testing instead of dropping everything in one-go. 
These two patches stand on their own independently, and IMO provide 
useful functionality right now.

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 tree-vrp 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.

Thoughts?

Aldy (and Andrew)

Comments

Richard Biener June 24, 2019, 1:24 p.m. UTC | #1
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 sub-ranges 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 substitute-and-fold 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 anti-ranges 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 drop-in 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 "tree-vrp.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 sub-ranges to work.  i.e. Not a regression from mainline-- just
> new functionality we can't get with the limited sub-ranges 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
> range-ops code which makes heavy use of the subrange interface, and
> allows for broader testing instead of dropping everything in one-go.
> 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 tree-vrp 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)
Aldy Hernandez June 25, 2019, 8:05 a.m. UTC | #2
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 sub-ranges 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 substitute-and-fold 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 anti-ranges 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 anti-ranges, 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 drop-in 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 "tree-vrp.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 sub-ranges to work.  i.e. Not a regression from mainline-- just
>> new functionality we can't get with the limited sub-ranges 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
>> range-ops code which makes heavy use of the subrange interface, and
>> allows for broader testing instead of dropping everything in one-go.
>> 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 tree-vrp 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)
Richard Biener June 25, 2019, 2:14 p.m. UTC | #3
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 sub-ranges 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 substitute-and-fold 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 erorr-prone 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 anti-ranges 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 anti-ranges, 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 drop-in 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 "tree-vrp.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 sub-ranges to work.  i.e. Not a regression from mainline-- just
> >> new functionality we can't get with the limited sub-ranges 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
> >> range-ops code which makes heavy use of the subrange interface, and
> >> allows for broader testing instead of dropping everything in one-go.
> >> 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 tree-vrp 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)

Patch
diff mbox series

commit 1d7d379b3f8b23e5b378488f5dc1e8cc3225d350
Author: aldyh <aldyh@138bc75d-0d04-0410-961f-82ee72b054a4>
Date:   Tue Jun 18 22:44:57 2019 +0000

    irange on value_range implementation.
    
diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h
index 4af1bc99da9..80fcc4aee26 100644
--- a/gcc/tree-vrp.h
+++ b/gcc/tree-vrp.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/tree-vrp.c b/gcc/tree-vrp.c
index 8a3bd2599a5..b4d5698823e 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -71,6 +71,11 @@  along with GCC; see the file COPYING3.  If not see
 #include "wide-int-range.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 basic-blocks.  */
 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,
     }
 
   /* Anti-ranges that can be represented as ranges should be so.  */
+  tree type = TREE_TYPE (min);
   if (kind == VR_ANTI_RANGE)
     {
       /* For -fstrict-enums we may receive out-of-range 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 out-of-bound ranges for
      -fstrict-enums.  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 re-calculating
+     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/vr-values.c b/gcc/vr-values.c
index 6bc62f46d2a..def5a163e90 100644
--- a/gcc/vr-values.c
+++ b/gcc/vr-values.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 substitute-and-fold 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 value-ranges.  */
   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))