On Wed, 1 Mar 2023, Aldy Hernandez wrote:

> 
> 
> On 2/28/23 10:41, Richard Biener wrote:
> > On Mon, 27 Feb 2023, Aldy Hernandez wrote:
> > 
> >>
> >>
> >> On 2/27/23 14:58, Richard Biener wrote:
> >>> After fixing PR107561 the following avoids looking at VR_ANTI_RANGE
> >>> ranges where it doesn't seem obvious the code does the correct
> >>> thing here (lower_bound and upper_bound do not work as expected).
> >>
> >> I do realize there's some confusion here, and some of it is my fault. This
> >> has
> >> become obvious in my upcoming work removing all of legacy.
> >>
> >> What's going on is that ultimately min/max are broken with (non-legacy)
> >> iranges.  Or at the very least inconsistent between legacy and non-legacy.
> >> These are left over from the legacy world, and have been marked DEPRECATED
> >> for
> >> a few releases, but the middle end warnings continued to use them and even
> >> added new uses after they were obsoleted.
> >>
> >> min/max have different meanings depending on kind(), which is also
> >> deprecated,
> >> btw.  They are the underlying min/max fields from the legacy
> >> implementation,
> >> and thus somewhat leak the implementation details. Unfortunately, they are
> >> being called from non-legacy code which is ignoring the kind() field.
> >>
> >> In retrospect I should've converted everything away from min/max/kind years
> >> ago, or at the very least converted min/max to work with non-legacy more
> >> consistently.
> >>
> >> For the record:
> >>
> >>    enum value_range_kind kind () const;            // DEPRECATED
> >>    tree min () const;                              // DEPRECATED
> >>    tree max () const;                              // DEPRECATED
> >>    bool symbolic_p () const;                       // DEPRECATED
> >>    bool constant_p () const;                       // DEPRECATED
> >>    void normalize_symbolics ();                    // DEPRECATED
> >>    void normalize_addresses ();                    // DEPRECATED
> >>    bool may_contain_p (tree) const;                // DEPRECATED
> >>    bool legacy_verbose_union_ (const class irange *);      // DEPRECATED
> >>    bool legacy_verbose_intersect (const irange *); // DEPRECATED
> >>
> >> In my local branch I tried converting all the middle-end legacy API uses to
> >> the new API, but a bunch of tests started failing, and lots more false
> >> positives started showing up in correct code.  I suspect that's part of the
> >> reason legacy continued to be used in these passes :-/.  As you point out
> >> in
> >> the PR, the tests seem designed to test the current (at times broken)
> >> implementation.
> >>
> >> That being said, the 5 fixes in your patch are not wrong to begin with,
> >> because all uses guard lower_bound() and upper_bound() which work
> >> correctly.
> >> They return the lowest and uppermost possible bound for the range (ignoring
> >> the underlying implementation).  So, the lower bound of a signed non-zero
> >> is
> >> -INF because ~[0,0] is really [-INF,-1][1,+INF]. In the min/max legacy
> >> code,
> >> min() of signed non-zero (~[0,0]) is 0.  The new implementation has no
> >> concept
> >> of anti-ranges, and we don't leak any of that out.
> >>
> >> Any uses of min/max without looking at kind() are definitely broken. OTOH
> >> uses
> >> of lower/upper_bound are fine and should work with both legacy and
> >> non-legacy.
> >>
> >> Unrelated, but one place where I haven't been able to convince myself that
> >> the
> >> use is correct is bounds_of_var_in_loop:
> >>
> >>> /* Check if init + nit * step overflows.  Though we checked
> >>>         scev {init, step}_loop doesn't wrap, it is not enough
> >>>         because the loop may exit immediately.  Overflow could
> >>>         happen in the plus expression in this case.  */
> >>>      if ((dir == EV_DIR_DECREASES
> >>>           && compare_values (maxvr.min (), initvr.min ()) != -1)
> >>>          || (dir == EV_DIR_GROWS
> >>>       && compare_values (maxvr.max (), initvr.max ()) != 1))
> >>
> >> Ughh...this is all slated to go away, and I have patches removing all of
> >> legacy and the old API.
> >>
> >> Does this help?  Do you still think lower and upper bound are not working
> >> as
> >> expected?
> > 
> > lower_bound/upper_bound work as expected,
> > tree_lower_bound/tree_upper_bound do not.  I've checked and all uses
> > I "fixed" use lower_bound/upper_boud.
> > 
> > tree_lower_bound & friends are 'protected', but in the above light the
> > comment
> > 
> >    // potential promotion to public?
> > 
> > looks dangerous (I was considering using them ...).
> 
> First of all, my apologies for the time you've spent on this.  This needed
> cleaning up a few releases ago, but with legacy in place, it kept getting
> pushed further away.  This is my first order of business once stage1 opens.
> That being said, thank you for spot checking this.
> 
> It looks like tree_lower_bound was just syntactic sugar for m_base[pair * 2].
> The comment is likely wrong.  It should've stayed protected, or nuked in favor
> of accessing m_base directly to avoid confusion.
> 
> > 
> > I'm dropping the patch, it's probably time to work on getting rid of
> > 'value_range' uses (aka legacy_mode_p ()) and/or replace raw accesses
> > to the min/max for that mode with m_base accesses?  At least
> > that there's tree_{upper,lower}_bound for pair != 0 suggests this
> > function is used with differing semantics internally which is a
> 
> My local tree has a few dozen patches removing legacy and converting the trees
> to wide_int.  In my work, legacy_mode_p, min, max, kind, tree_lower_bound, etc
> are all gone.  I can make the branch public if you like.
> 
> > source of confusion (to me at least).  tree_{lower,upper}_bound
> > should be able to assert it's not a legacy mode range and
> > min/max should be able to assert that it is.
> 
> Agreed.  One possible problem *may be* vr-values.cc which still uses min() and
> max() throughout can be called on legacy as well as non-legacy.
> 
> This unfortunately means that since kind/min/max will return different results
> for legacy/non-legacy (kind() never returns VR_ANTI_RANGE for non-legacy),
> simplify_using_ranges can theoretically give different results depending on
> how it's called.  In practice, only DOM/VRP call simplify_using_ranges and
> always with non-legacy.  However, simplify_using_ranges uses get_value_range()
> internally which uses legacy.  Sorry, I just realized this now while auditing
> the code.
> 
> I honestly have no idea if this matters in practice, and since this has been
> this way for a few releases, I'm afraid of touching it so late in the cycle.
> But I'm happy to help if you think it must be fixed in this release.
> 
> Hmmmm, it looks like there are just a few non-legacy uses in vr-values.cc
> (int_range<2> and int_range_max), and never in code paths checking
> min/max/kind.  So your suggestions about the asserts may be all we need,
> dunno.
> 
> > 
> > Btw, legacy_upper_bound looks wrong:
> > 
> >    if (m_kind == VR_ANTI_RANGE)
> >      {
> >        tree typ = type (), t;
> >        if (pair == 1 || vrp_val_is_min (min ()))
> >          t = vrp_val_max (typ);
> >        else
> >          t = wide_int_to_tree (typ, wi::to_wide (min ()) - 1);
> > 
> > not sure what the pair == 1 case is about, but the upper bound
> > of an anti-range is only special when max() is vrp_val_is_max,
> > aka ~[low, +INF] where it then is low - 1, but the above checks
> > for ~[-INF, high] and returns +INF in that case.  That's correct
> > unless high == +INF at least, but the else case is wrong for
> > all high != +INF?
> 
> An anti-range is really two pairs.  So, ~[6,9] is really:
> 
> [-MIN, 5][10, MAX]
> 
> Pair 0 is [-MIN, 5] and pair 1 is [10, MAX].  This means that the upper bound
> for the pair==1 case is just MAX.
> 
> > 
> > I think it should be
> > 
> >        if (pair == 1 || !vrp_val_is_max (max ()))
> >          t = vrp_val_max (typ);
> >        else
> >          t = wide_int_to_tree (typ, wi::to_wide (min ()) - 1);
> > 
> > no?
> 
> I think both of us are wrong.  The original vrp_val_is_min(min()) call will
> always return false.  And your !vrp_val_is_max(max()) is always true.  This is
> because irange::set() will normalize anti-ranges into a VR_RANGE when
> possible, in order to avoid multiple representations for the same range:
> 
>       else if (is_min)
>         {
>         tree one = build_int_cst (TREE_TYPE (max), 1);
>         min = int_const_binop (PLUS_EXPR, max, one);
>         max = vrp_val_max (TREE_TYPE (max));
>         kind = VR_RANGE;
>         }
>       else if (is_max)
>         {
>         tree one = build_int_cst (TREE_TYPE (min), 1);
>         max = int_const_binop (MINUS_EXPR, min, one);
>         min = vrp_val_min (TREE_TYPE (min));
>         kind = VR_RANGE;
>         }
> 
> So ~[-MIN,5] is represented as [6,MAX] and ~[5,+MAX] as [-MIN,4].
> 
> Ughhh... so it looks like legacy_upper_bound is correct, but the
> vrp_val_is_min() check is useless.
> 
> Am I missing something?

Well, you are missing that VR_ANTI_RANGE only has a single pair in
m_base[], so it's _not_ represented as [-MIN, 5][10, MAX].  So you
say that for VR_ANTI_RANGE we should never ask for legacy_upper_bound (0)
but always legaacy_upper_bound (1)?

Btw, I didn't see in ::verify where we verify proper normalization
so after some range ops it might be in non normalized form.

That said - as this is all going away tampering with it looks less
useful than ripping it out ...

Anyway, see the series I posted which I ended up with in understanding
the code.  Appearantly I misunderstood the intent of the current state,
mainly because of lack of documentation I guess :/

I do wonder if s/value_range/int_range<2>/ throughout most code is
the correct thing to do and what the actual hurdles are in the end.

Richard.

Reply via email to