Am 03.09.24 um 18:12 schrieb Andrew MacLeod:
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.
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?
Andrew
Thank you for the explanations and details.
Johann
