value_range and irange unification

Tue Jun 25 14:15:00 GMT 2019

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)