On Tue, Sep 3, 2024 at 6:12 PM Andrew MacLeod <amacl...@redhat.com> wrote:
>
>
> On 8/25/24 03:48, Richard Biener wrote:
> > On Sat, Aug 24, 2024 at 6:19 PM Georg-Johann Lay <a...@gjlay.de> wrote:
> >> Trying to use the value-range interface and functions I am running
> >> into that ICE when using invert().
> >>
> >> From what the sources suggest, invert() computes the complement of
> >> the current set (the union of finitely many intervals).
> >>
> >> For example, when I have a range of [-128, -1] for int8_t, invert()
> >> runs into that ICE because that interval is undefined or varying.
> >>
> >> Take for example, this code that wants to take the complement of
> >> the complete interval (with respect to the complete interval given
> >> by uint8_t):
> >>
> >> tree t = unsigned_intQI_type_node;
> >> int n_bits = TYPE_PRECISION (t);
> >>
> >> int_range<2, false /*resizable*/ > j(t);
> This creates j as up to 2 subranges, and initializes it to VARYING...
> the maximal range
> >>
> >> // j is undefined(?), thus set its bounds to the entire range.
> >> j.set (t, wi::to_wide (j.lbound()), wi::to_wide (j.ubound()));
>
> If j were UNDEFINED, j.lbound() and j.ubound () would trap because
> UNDEFINED has no known bounds. It is the empty set.
> as it was initialized to VARYING, this j.set statement is a no-op
> because you are setting to the same lower and upper bounds.
>
>
> >> j.invert();
> >> <built-in>: internal compiler error: in invert, at value-range.cc:2165
> And you cannot use invert () on UNDEFINED or VARYING values, for reasons
> I will explain below.
> >> 0
> >>
> >> This should just return the empty set; no? And vice versa, the
> >> complement of the empty set (with respect to the whole interval)
> >> should be the whole interval provided by t, no?
> >>
> >> If I understand correctly, the int_range<> implementation does not
> >> implement a semi-group, and there are sets / intervals that are not
> >> allowed, like the empty set or intervals that touch a boundary.
> >>
> >> Does this mean that I have to test and special-case all these cases
> >> and do them by hand? Are there more invalid / disallowed intervals?
> > A lot of functions do not allow undefined_p () ranges, but it's odd
> > that invert doesn't handle varying_p (). But yes, the range API
> > (unfortunately) requires you to check for certain exceptional cases
> > beforehand even though they are not really exceptional for
> > range arithmetic in general.
> >
> >> So I guess it is simpler when I write my own interval arithmetic
> >> that handles these cases and behaves like a semi group. As there
> >> will be at most 3 sub-intervals, that's the way to go...?
> >>
> >> Isn't there a knob to tell that complement is with respect to the
> >> range as provided by type(), and not w.r.t. the integers?
> > Andrew would have to answer that but I think that's how ranges
> > behave. They just have those API requirements that are
> > sometimes annoying.
> >
> > Richard.
> >
>
> Special casing of UNDEFINED dates back to concessions that were made
> when irange was introduced. UNDEFINED does not have a type, and
> therefore, we have no way to invert it because we do not know what type
> the resulting VARYING should be.
>
> Thats the practical answer. UNDEFINED can also be interpreted
> differently in different contexts. From an arithmetic point of view, it
> is the opposite of VARYING. How we interpret it when we use it varies
> on a case by case basis. For instance, an uninitialized value is
> treated as UNDEFINED for some purposes, but VARYING for others. An
> outgoing edge from a conditional that results in UNDEFINED points to
> unreachable code, but if that code remains in the IL, we have to
> interpret it sometimes as VARYING and produce results. There are also
> times when we take UNDEFINED and the optimizer chooses a convenient
> value for it. Therefore it is safer for the caller to handle
> manipulations of UNDEFINED, then we get no surprises.
>
> As for VARYING, we make the caller handle that case for invert ()
> because by definition:
>
> range.invert ().invert ()
>
> should result in no change to 'range'. If range was VARYING, producing
> UNDEFINED would then cause the second call to invert() to fail because
> there is no type associated with range any more. In addition, give the
> lack of clarity on how the consumer will treat the resulting UNDEFINED,
> it was not clear that it would always be the expected value. There are
> not many uses in invert() in our code, and all of them are in well
> defined circumstances that are not VARYING nor UNDEFINED.
>
> If your code consistently handles things this way, you can create your
> own functional definition of invert that also takes the type
>
> void
> my_invert (irange &r, type t)
> {
> if (r.undefined_p ())
> r.set_varying (t);
> else if (r.varying_p ())
> r.set_undefined ();
> else
> r.invert ();
> }
>
>
> invert() and all other range operations are always relative to the
> values of range.type (). IIRC there was a lot of pain related to enums
> and bitranges for this, but for normal types that have well defined
> endpoints, there shouldn't be any other surprises. There are no knobs.
>
> Many of the other routines do not need special cases for UNDEFINED (
> like union_ () and intersect ()), because they do not need a type
> associated with undefined to perform all possible actions. invert was
> kind of unique.
>
> Does that answer the questions?
Can we put that logic for invert() behavior in a comment in the
source?
Note that I agree that UNDEFINED does not _need_ a type - but there's
no reason it couldn't have one so that varying.invert () yields undefined
without "clearing" the type so it can be inverted back to the correct VARYING.
Given that adding a (defaulted to nullptr) type argument to invert () would
also "solve" the issue and lessen the pain for callers who want that
VARYING <-> UNDEFINED in type X behavior of invert.
Thanks,
Richard.
>
> Andrew
>
