Hi!
The following testcase is miscompiled during evrp.
Before vrp, we have (from ccp):
# RANGE [irange] long long unsigned int [0, +INF] MASK 0xffffffffffffc000
VALUE 0x2d
_3 = _2 + 18446744073708503085;
...
# RANGE [irange] long long unsigned int [0, +INF] MASK 0xffffffffffffc000
VALUE 0x59
_6 = (long long unsigned int) _5;
# RANGE [irange] int [-INF, +INF] MASK 0xffffc000 VALUE 0x34
_7 = k_11 + -1048524;
switch (_7) <default: <L5> [33.33%], case 8: <L7> [33.33%], case 24: <L6>
[33.33%], case 32: <L6> [33.33%]>
...
# RANGE [irange] long long unsigned int [0, +INF] MASK 0xffffffffffffc07d
VALUE 0x0
# i_20 = PHI <_3(4), 0(3), _6(2)>
and evrp is now trying to figure out range for i_20 in range_of_phi.
All the ranges and MASK/VALUE pairs above are correct for the testcase,
k_11 and _2 based on it is a result of multiplication by a constant with low
14 bits cleared and then some numbers are added to it.
There is an obvious missed optimization for which I've filed PR119039,
simplify_switch_using_ranges could see that all the labels but default
are unreachable because the controlling expression has
MASK 0xffffc000 VALUE 0x34 and none of 8, 24 and 32 satisfy that.
Anyway, during range_of_phi for i_20, we process the PHI arguments
in order. For the _3(4) case, we figure out that it is reachable
through the case 24: case 32: labels only of the switch and that
0x34 - 0x2d is 7, so derive
[irange] long long unsigned int [17, 17][25, 25] MASK 0xffffffffffffc000 VALUE
0x2d
(the MASK/VALUE just got inherited from the _3 earlier range).
Now (not suprisingly because those labels aren't actually reachable),
that range is inconsistent, 0x2d is 45, so there is conflict between the
values and the irange_bitmask.
value-range.{h,cc} code differentiates between actually stored
irange_bitmask, which is that MASK 0xffffffffffffc000 VALUE 0x2d, and
semantic bitmask, which is what get_bitmask returns. That is
// The mask inherent in the range is calculated on-demand. For
// example, [0,255] does not have known bits set by default. This
// saves us considerable time, because setting it at creation incurs
// a large penalty for irange::set. At the time of writing there
// was a 5% slowdown in VRP if we kept the mask precisely up to date
// at all times. Instead, we default to -1 and set it when
// explicitly requested. However, this function will always return
// the correct mask.
//
// This also means that the mask may have a finer granularity than
// the range and thus contradict it. Think of the mask as an
// enhancement to the range. For example:
//
// [3, 1000] MASK 0xfffffffe VALUE 0x0
//
// 3 is in the range endpoints, but is excluded per the known 0 bits
// in the mask.
//
// See also the note in irange_bitmask::intersect.
irange_bitmask bm
= get_bitmask_from_range (type (), lower_bound (), upper_bound ());
if (!m_bitmask.unknown_p ())
bm.intersect (m_bitmask);
Now, get_bitmask_from_range here is MASK 0x1f VALUE 0x0 and it intersects
that with that MASK 0xffffffffffffc000 VALUE 0x2d.
Which triggers the ugly special case in irange_bitmask::intersect:
// If we have two known bits that are incompatible, the resulting
// bit is undefined. It is unclear whether we should set the entire
// range to UNDEFINED, or just a subset of it. For now, set the
// entire bitmask to unknown (VARYING).
if (wi::bit_and (~(m_mask | src.m_mask),
m_value ^ src.m_value) != 0)
{
unsigned prec = m_mask.get_precision ();
m_mask = wi::minus_one (prec);
m_value = wi::zero (prec);
}
so the semantic bitmask is actually MASK 0xffffffffffffffff VALUE 0x0.
Next, range_of_phi attempts to union it with the 0(3) PHI argument,
and during irange::union_ first adds the [0,0] to the subranges, so
[irange] long long unsigned int [0, 0][17, 17][25, 25] MASK 0xffffffffffffc000
VALUE 0x2d
and then goes on to irange::union_bitmask which does
if (m_bitmask == r.m_bitmask)
return false;
irange_bitmask bm = get_bitmask ();
irange_bitmask save = bm;
bm.union_ (r.get_bitmask ());
if (save == bm)
return false;
m_bitmask = bm;
if (save == get_bitmask ())
return false;
m_bitmask MASK 0xffffffffffffc000 VALUE 0x2d isn't the same as
r.m_bitmask MASK 0x0 VALUE 0x0, so we compute the semantic bitmask
(but note, not from the original range before union, but the modified one,
dunno if that isn't a problem as well), which is still the VARYING/unknown_p
one, union_ that with MASK 0x0 VALUE 0x0 and get still
MASK 0xffffffffffffffff VALUE 0x0, so don't update anything, the semantic
bitmask didn't change, so we are fine (not!, see later).
Except then we try to union with the third PHI argument. And, because the
edge to that comes only from case 8: label and there is a known difference
between the two, the argument is actually already from earlier replaced by
45(2) constant. So, irange::union_ adds the [45, 45] range to the list
of subranges, but voila, 45 is 0x2d and satisfies the stored
MASK 0xffffffffffffc000 VALUE 0x2d and so the semantic bitmask changed to
from MASK 0xffffffffffffffff VALUE 0x0 to MASK 0xffffffffffffc000 VALUE 0x2d
by that addition. Eventually, we just optimize this to
[irange] long long unsigned int [45, 45] because that is the only range
which satisfies the bitmask. And that is wrong, at runtime i_20 has
value 0.
The following patch attempts to detect this case where get_bitmask
turns some non-VARYING m_bitmask into VARYING one because of a conflict
and in that case makes sure m_bitmask is actually updated rather than
unmodified, so that later union_ doesn't cause problems.
I also wonder whether e.g. get_bitmask couldn't have special case for this
and if bm.intersect (m_bitmask); yields unknown_p from something not
originally unknown_p, perhaps chooses to just use get_bitmask_from_range
value and ignore the stored m_bitmask. Though, dunno how union_bitmask
in that case would figure out it needs to update m_bitmask.
Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk
and 14.3 (after a while)?
2025-02-27 Jakub Jelinek <ja...@redhat.com>
PR tree-optimization/118953
* value-range.cc (irange::union_bitmask): Update m_bitmask if
get_bitmask () is unknown_p and m_bitmask is not even when the
semantic bitmask didn't change and returning false.
* gcc.dg/torture/pr118953.c: New test.
--- gcc/value-range.cc.jj 2025-01-02 11:23:25.118396777 +0100
+++ gcc/value-range.cc 2025-02-26 18:49:10.713107905 +0100
@@ -2447,7 +2447,7 @@ irange::union_bitmask (const irange &r)
irange_bitmask bm = get_bitmask ();
irange_bitmask save = bm;
bm.union_ (r.get_bitmask ());
- if (save == bm)
+ if (save == bm && (!bm.unknown_p () || m_bitmask.unknown_p ()))
return false;
m_bitmask = bm;
--- gcc/testsuite/gcc.dg/torture/pr118953.c.jj 2025-02-26 18:51:47.139936059
+0100
+++ gcc/testsuite/gcc.dg/torture/pr118953.c 2025-02-26 18:52:33.078298359
+0100
@@ -0,0 +1,42 @@
+/* PR tree-optimization/118953 */
+/* { dg-do run { target int32plus } } */
+
+int a, d;
+long long b, c;
+
+int
+foo (int f, int g, unsigned long long h, long long j)
+{
+ unsigned long long i = 0;
+ if (g)
+ switch (f)
+ {
+ case 8:
+ i = b;
+ break;
+ case 6:
+ i = c;
+ break;
+ }
+ else
+ switch (f)
+ {
+ case 8:
+ i = h;
+ break;
+ case 24:
+ case 32:
+ i = j;
+ break;
+ }
+ return i;
+}
+
+int
+main ()
+{
+ int k = a * (409628 - 28);
+ d = foo (k - 1048524, 0, k - 1048487, k - 1048531ULL);
+ if (d)
+ __builtin_abort ();
+}
Jakub
