[patch] new API for value_range

[Richard Biener]

On Thu, Oct 11, 2018 at 10:19 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> Hi Richard.  Thanks for reviewing.
>
> On 10/10/18 6:27 AM, Richard Biener wrote:
> > On Tue, Oct 9, 2018 at 6:23 PM Aldy Hernandez <aldyh@redhat.com> wrote:
> >>
> >> I'm assuming the silence on the RFC means nobody is viscerally opposed
> >> to it, so here goes the actual implementation ;-).
> >>
> >>          FWI: https://gcc.gnu.org/ml/gcc-patches/2018-10/msg00157.html
> >>
> >> My aim is no change to the current functionality, but there are some
> >> things that changed slightly (with no appreciable change in
> >> bootstrapability or tests).
> >>
> >> 1.  Primarily, we were building value_ranges by modifying them in-flight
> >> with no regards to the validity of the resulting range.  By enforcing
> >> the API, I noticed we periodically built VR_VARYING / VR_UNDEFINED, but
> >> left the equivalence bits uncleared.  This comment in the original
> >> header file indicates that this is invalid behavior:
> >>
> >>     /* Set of SSA names whose value ranges are equivalent to this one.
> >>        This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE.  */
> >>
> >> The API now enforces this upon construction.
> >>
> >> 2. I also saw us setting min/max when VARYING or UNDEFINED was set.
> >> This is invalid.  Although these values were being ignored, the API now
> >> enforces this.
> >>
> >> 3. I saw one case in set_value_range_with_overflow() were we were
> >> building an invalid range with swapped ranges, where we were silently
> >> depending on somebody further up the call chain to swap them for us.
> >> I've fixed this at creation.
> >>
> >> 4. There is one assert in ipcp_vr_lattice which I hope to remove, but
> >> left as proof that the original VR_UNDEFINED set was not necessary, as
> >> it is now done by default on an empty constructor:
> >>
> >> -  void init () { m_vr.type = VR_UNDEFINED; }
> >> +  void init () { gcc_assert (m_vr.undefined_p ()); }
> >>
> >> One last note.  The file tree-vrp.c already has a cripple API of sorts
> >> in the form of functions (set_value_range_to_varying, etc).  I have
> >> tried to keep those functions available, by calling the API under the
> >> covers, but would be okay in removing them altogether as a follow-up.
> >>
> >> Please refer to the RFC wrt the min/max/vrtype accessors, as well as the
> >> new tree type field.
> >>
> >> I am quoting the class declaration below to make it easy to review at a
> >> high level.
> >>
> >> Tested on x86-64 Linux.  All languages, including Ada and Go.
> >>
> >> OK for trunk?
> >
> > Reviewing in patch order.
> >
> >> Aldy
> >>
> >> class GTY((for_user)) value_range
> >> {
> >>    public:
> >>     value_range ();
> >>     value_range (tree type);
> >>     value_range (value_range_type, tree type, tree, tree, bitmap = NULL);
> >>     bool operator== (const value_range &) const;
> >>     bool operator!= (const value_range &) const;
> >>     void intersect (const value_range *);
> >>     void union_ (const value_range *);
> >
> > with trailing underscore?  seriously?
>
> Hey!  You complained about Union() last year, at which point the
> consensus was that trailing underscores would be ok for symbol names
> that clashed with keywords.

;)

I also thought about union_into / union_with.  As opposed to a hypothetical

  value_range union (const value_range& a, const value_range& b)

function.

> And yes, it was also discussed whether we should overload | and ^ for
> union and intersection, but was denied for readability and what have yous.
>
> >
> >>     /* Like operator== but ignore equivalence bitmap.  */
> >>     bool ignore_equivs_equal_p (const value_range &) const;
> >>     /* Like a operator= but update equivalence bitmap efficiently.  */
> >>     void copy_with_equiv_update (const value_range *);
> >>
> >>     /* Types of value ranges.  */
> >>     bool undefined_p () const;
> >>     bool varying_p () const;
> >>     bool symbolic_p () const;
> >>     bool numeric_p () const;
> >>     void set_undefined (tree = NULL);
> >>     void set_varying (tree = NULL);
> >
> > I'd appreciate comments on those predicates, esp. as you
> > replace positive tests by negative ones like in
>
> Done.
>
> >
> >     /* If we found any usable VR, set the VR to ssa_name and create a
> >        PUSH old value in the stack with the old VR.  */
> > -  if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
> > +  if (!vr.undefined_p () && !vr.varying_p ())
> >       {
> >
> > I'd also spell numeric_p as constant_p or drop it alltogether
> > since !symbolic_p should imply it given varying_p and undefined_p
> > are just some special-cases of "numeric_p" (full and empty range).
>
> Done.
>
> >
> > That said, for the time being I'd use non_symbolic_range_or_anti_range_p
> > instead of numeric_p () (seeing that you maybe want to hide the fact
> > that we have anti-ranges?)
>
> Errr... No.
>
> >
> > -  value_range vr = VR_INITIALIZER;
> > +  value_range vr (TREE_TYPE (name));
> >
> > so you basically forgo with the fact that empty ranges are universal?
> > I don't like it too much that we have to invent a type here.  Why enforce this
> > and not allow/force type == NULL_TREE for empty ranges?
> >
> > One could argue VARYING is also universal to some extent and useful
> > only with context, so similar argument applies to your change forcing
> > a type for set_value_range_to_varying.
> >
> > -      value_range vr = VR_INITIALIZER;
> > +      value_range vr;
> >
> > oh, so you do have a default constructor.
> >
> >>
> >>     /* Equivalence bitmap methods.  */
> >>     bitmap equiv () const;
> >>     void set_equiv (bitmap);
> >
> > Err, I think we've settled on _not_ wrapping all member accesses
> > with get/set methods, didn't we?  I personally dislike that very much.
> >
> >>     void equiv_free ();
> >>     void equiv_copy (const value_range *);
> >>     void equiv_clear ();
> >>     void equiv_and (const value_range *);
> >>     void equiv_ior (const value_range *);
> >
> > Likewise I find this useless abstraction.  It's even questionable
> > if _free/_clear/_copy are good APIs here.  This should be all
> > hidden in intersect/union which I do not find in the API at all...
>
> I missed that discussion.  We did?  I dislike exposing the internals.
> Abstracting things out makes it easier to change things in the future--
> or insert instrumenting code, or whatever.

OK, I might misremember and it's eventually just my personal taste
against slapping a setFoo/getFoo method in a class as the first
thing to do after adding a m_Foo member...

> That said, I have removed copy/free/and/or.  As you said, it was much
> easier to make the details internal to the intersect/union member functions.
>
> However, I have kept:
>
>    bitmap equiv () const;
>    void set_equiv (bitmap);
>    void equiv_clear ();
>
> I think we can get away with just having a clear, instead of a free, as
> it's all in an obstack and there doesn't seem to be any consistent use
> of free vs. clear throughout (except one or two, which I've kept).

Yeah.

> Also, we don't really need to expose set_equiv(), but for its one use in
> vr_values::add_equivalence().  One option could be to make vr_values and
> value_ranges friends and let add_equivalence touch m_equiv.  But that's
> a bit heavy handed.
>
> Or we could add this to the API instead of set_equiv():
>
> void
> value_range::add_equivalence (bitmap_obstack obstack, tree var)
> {
> }
>
> I don't know how I feel about passing the obtack, or including
> "bitmap.h" from everywhere tree-vrp.h is used (that is, everywhere).

Equivalences are evil ;)  But I guess passing in the obstack works
for me.  Maybe as trailing argument, defaulted to NULL in which
case we use the default bitmap obstack?

> For equiv(), we could remove virtually all of its uses, since 99% of
> them are in the form:
>
>         set_value_range (vr, VR_SOMETHING, min, max, vr->equiv ())
>
> Instead we could We could provide:
>
>         vr->update (VR_SOMETHING, min, max);
>
> ...which is just like set_value_range, but keeping the equivalences intact.

Yep, sounds good.

>  > hidden in intersect/union which I do not find in the API at all...
>
> How could you, it was front and center ;-):
>
>    void intersect (const value_range *);
>    void union_ (const value_range *);

Missed that in the first review and then failed to delete that comment ;)

> >
> >>
> >>     /* Misc methods.  */
> >>     tree type () const;
> >
> > type() and vrtype() is confusing - value_type() and range_kind() maybe?
>
> How about we keep type(), since 99% of all uses of "type" in the
> compiler are "tree type", so it's easy to figure out.  And instead of
> range_kind() we use kind().  It's already obvious it's a range, so
> vr->kind() reads fine IMO.

Works for me.

> >
> >>     bool null_p () const;
> >>     bool may_contain_p (tree) const;
> >>     tree singleton () const;
> >
> > No documentation? :/   Why null_p but singleton (instead of singleton_p)?
>
> Documented.
>
> Singleton returns the singleton if found, otherwise returns NULL.
> NULL_P returns true/or false.  I thought the preferred way was for _p to
> always return booleans.

Ah, missed that "detail"...

> I don't feel strongly, so I've renamed it to singleton_p() since a
> NULL_TREE is as good as false.  Another option is:
>
>         bool singleton_p (tree *result = NULL)
>
> Hmmm...I like this last one.  What do you think?

Like it as well.

> >
> >>     void set_and_canonicalize (enum value_range_type, tree, tree, tree,
> >> bitmap);
> >
> > Why's that necessary if you enforce sanity?
>
> Canonicalize also does some optimizations like converting anti-ranges
> into ranges if possible.  Although I would be OK with putting that
> functionality in value_range::set() to be done on creation, I don't know
> how I feel about polluting the creation code with fixing swapped min/max:
>
>    /* Wrong order for min and max, to swap them and the VR type we need
>       to adjust them.  */
>
> It feels wrong to construct a range with swapped end-points, and hope
> things turn out ok.  ISTM that canonicalize() clearly specifies intent:
> I'm giving you a shitty range, fix it.
>
> Thoughts?

OK, let's keep it the way you had it.  I never liked this part very much
(even though I added it!).

> >
> >>     void dump () const;
> >>
> >>     /* Temporary accessors that should eventually be removed.  */
> >>     enum value_range_type vrtype () const;
> >>     tree min () const;
> >>     tree max () const;
> >>
> >>    private:
> >>     void set (value_range_type, tree type, tree, tree, bitmap);
> >>     void check ();
> >>     bool equal_p (const value_range &, bool ignore_equivs) const;
> >>
> >>     enum value_range_type m_vrtype;
> >>    public:
> >>     /* These should be private, but GTY is a piece of crap.  */
> >>     tree m_min;
> >>     tree m_max;
> >>     tree m_type;
> >
> > m_type is redundant (see above).
>
> Removed.
>
> Tested on x86-64 Linux.
>
> Aldy
>
> p.s. Oh yeah, it wouldn't be an Aldy patch without an irrelevant bit
> added for good measure:
>
> +void
> +bitmap_head::dump ()
> +{
> +  debug (this);
> +}
>
> I find having ->dump() available for each and every structure in GCC
> helpful in debugging.  At some point we should standardize on dump(FILE
> *) and debug() to dump to stderr.  But alas, there are too many dump()'s
> that already dump to stderr :-/.

FWIW I like

void dump (const bitmap_head&);

more since it doesn't clutter the APIs and can theoretically be very
easily not built into a release compiler.  And IIRC we already have
global overloads of debug () for exactly the reason you cite.  Having
both styles is IMHO not good.  (and I've stated my preference - feel
free to provide statistics for in-tree uses ;))

Richard.