[Bug tree-optimization/115494] New: wrong code at -O{2,3} with "-fno-ssa-phiopt" on x86_64-linux-gnu (the generated code hangs)

[Bug tree-optimization/115494] New: wrong code at -O{2,3} with "-fno-ssa-phiopt" on x86_64-linux-gnu (the generated code hangs)

[zhendong.su at inf dot ethz.ch]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115494

            Bug ID: 115494
           Summary: wrong code at -O{2,3} with "-fno-ssa-phiopt" on
                    x86_64-linux-gnu (the generated code hangs)
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: zhendong.su at inf dot ethz.ch
  Target Milestone: ---

It appears to be a recent regression as it doesn't reproduce with 13.* and
earlier. 

Compiler Explorer: https://godbolt.org/z/889EdEeE9

[627] % gcctk -v
Using built-in specs.
COLLECT_GCC=gcctk
COLLECT_LTO_WRAPPER=/local/suz-local/software/local/gcc-trunk/libexec/gcc/x86_64-pc-linux-gnu/15.0.0/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: ../gcc-trunk/configure --disable-bootstrap
--enable-checking=yes --prefix=/local/suz-local/software/local/gcc-trunk
--enable-sanitizers --enable-languages=c,c++ --disable-werror --enable-multilib
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 15.0.0 20240614 (experimental) (GCC) 
[628] % 
[628] % gcctk -O2 small.c; ./a.out; echo $?
0
[629] % gcctk -O2 -fno-ssa-phiopt small.c; ./a.out; echo $?
1
[630] % cat small.c
unsigned char a;
int b = 1, c, d;
int main() {
  char e;
  c = b - c;
  a = ~(c || a);
  e = -(b ^ a);
  d = e && b;
  a = ~(b & a);
  if (a < 2)
    return 1;
  return 0;
}

[Bug tree-optimization/115494] wrong code at -O{2,3} with "-fno-ssa-phiopt" on x86_64-linux-gnu

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115494

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 58433
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58433&action=edit
Testcase that uses abort

[Bug tree-optimization/115494] wrong code at -O{2,3} with "-fno-ssa-phiopt" on x86_64-linux-gnu

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115494

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Note changing main to f and you get the failure even without `-fno-ssa-phiopt`.

[Bug tree-optimization/115494] [14/15 Regression] wrong code at -O{2,3} on x86_64-linux-gnu

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115494

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2024-06-14
     Ever confirmed|0                           |1
   Target Milestone|---                         |14.2
             Status|UNCONFIRMED                 |NEW
            Summary|wrong code at -O{2,3} with  |[14/15 Regression] wrong
                   |"-fno-ssa-phiopt" on        |code at -O{2,3} on
                   |x86_64-linux-gnu            |x86_64-linux-gnu

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
.

[Bug tree-optimization/115494] [14/15 Regression] wrong code at -O{2,3} on x86_64-linux-gnu

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115494

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu.org
           Keywords|needs-bisection             |

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Hmm. disabling:

/* x | C -> C if we know that x & ~C == 0.  */
(simplify
 (bit_ior SSA_NAME@0 INTEGER_CST@1)
 (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
      && wi::bit_and_not (get_nonzero_bits (@0), wi::to_wide (@1)) == 0)
  @1))

Fixes it.

So this was caused/exposed by r14-3485-g6df8dcec7196e4 .

Note that above pattern is hitting during PRE. I have to double check to make
sure that is correct.

[Bug tree-optimization/115494] [14/15 Regression] wrong code at -O{2,3} on x86_64-linux-gnu since r14-3485

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115494

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #4)
> Hmm. disabling:
> 
> /* x | C -> C if we know that x & ~C == 0.  */
> (simplify
>  (bit_ior SSA_NAME@0 INTEGER_CST@1)
>  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
>       && wi::bit_and_not (get_nonzero_bits (@0), wi::to_wide (@1)) == 0)
>   @1))
> 
> Fixes it.
> 
> So this was caused/exposed by r14-3485-g6df8dcec7196e4 .
> 
> Note that above pattern is hitting during PRE. I have to double check to
> make sure that is correct.

The match pattern is correct what we get through PRE is:
_17 | 1
Where _17's range is [0,1]
so obvious this is just 1.

So either what pre is sending off to match-and-simplify is wrong or the way pre
uses match-and-simplify is wrong. What the match does is correct for what it is
given..

[Bug tree-optimization/115494] [14/15 Regression] wrong code at -O{2,3} on x86_64-linux-gnu since r14-3485

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115494

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu.org

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
hmm,  I think I see what is happening.

So we start with:
  # RANGE [irange] unsigned char [0, 1] MASK 0x1 VALUE 0x0
  _4 = (unsigned charD.20) iftmp.2_8;
  # RANGE [irange] unsigned char [254, +INF] MASK 0x1 VALUE 0xfe
  _5 = ~_4;

  if (_5 != _14)
    goto <bb 6>; [66.00%]
  else
    goto <bb 5>; [34.00%]

bb5:
  # RANGE [irange] unsigned char [0, 1] MASK 0x1 VALUE 0x0
  _17 = ~_14;
  # RANGE [irange] unsigned char [0, 1] MASK 0x1 VALUE 0x0
  _18 = _4 | _17;

...

bb6:
...
  _15 = ~_14;
  _7 = _4 | _15;


So PRE is consolidating _17 and _15 as being the same and using _17 as the
leader.
And when it realizes _4 is 1 on the bb6 and goes to do the simplify, does 1 |
_17 but gets simplified to 1 but `~_14` range in bb6 is not [0,1].

So the issue is PRE is not removing the range from _17 before doing the
simplification while consolidating the two ssa names.

Richi,
  can you look into this further? match is doing exactly what it is being asked
of it but it looks like PRE is messing up due to conditional ranges.

[Bug tree-optimization/115494] [14/15 Regression] wrong code at -O{2,3} on x86_64-linux-gnu since r14-3485

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115494

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|unknown                     |14.1.1
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
I will have a look.  Note PRE expression simplification should _only_ work
based on avails by design.

[Bug tree-optimization/115494] [14/15 Regression] wrong code at -O{2,3} on x86_64-linux-gnu since r14-3485

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115494

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
ANTIC_IN[6] := { _5 (0005), _16 (0014), {bit_not_expr,_16} (0016),
{bit_ior_expr,_5,_19} (0017) }
ANTIC_IN[8] := { _5 (0005), _16 (0014), {bit_not_expr,_16} (0016),
{bit_ior_expr,_5,_17} (0017) }
ANTIC_IN[11] := { _5 (0005), _16 (0014), {bit_not_expr,_16} (0016),
{bit_ior_expr,_5,_24} (0017) }

merge 8 + 11:
ANTIC_IN[7] := { b.0_1 (0001), _5 (0005), _16 (0014), {bit_not_expr,_16}
(0016), {bit_ior_expr,_5,_17} (0017), {bit_ior_expr,_5,_24} (0017) }

merge 7 + 6:
ANTIC_IN[5] := { b.0_1 (0001), iftmp.2_9 (0008), {nop_expr,iftmp.2_9} (0005),
{bit_not_expr,_5} (0006), {nop_expr,b.0_1} (0014), {bit_not_expr,_16} (0016),
{bit_ior_expr,_5,_19} (0017), {bit_ior_expr,_5,_17} (0017),
{bit_ior_expr,_5,_24} (0017) 

that's all OK.  Note all exprs have the same value (0017) here.  Then
we PHI-translate to where _5 == 0:
ANTIC_IN[14] := { b.0_1 (0001), {nop_expr,b.0_1} (0014), {bit_not_expr,_16}
(0016) }
which is OK, 0 | .. gets simplified to ~16

Then we PHI-translate to where _5 == 1:
ANTIC_IN[4] := { b.0_1 (0001), {nop_expr,b.0_1} (0014), {bit_not_expr,_16}
(0016), {bit_ior_expr,_17,1} (0027), {bit_ior_expr,_24,1} (0028) }
even that's OK, you see that we simplified just _5 | _19 to 1 (constants
are not tracked in the set, the translated _17 | _5 and _24 | _5 got
different value numbers).

But then:

Found partial redundancy for expression {bit_ior_expr,_5,_19} (0017)
...
Created phi prephitmp_29 = PHI <1(4), _28(14)>
 in block 5 (0017)

see how we figured the redundancy for value 0017 (because _5 | _19
simplified to 1) and we use the same value for the PHI as for all of
the expressions.

That we now keep all PRE exprs didn't save us here.  _19 _is_ the leader
for the expression as we translate it.  The problem is the other
expressions for the same value do not translate the same.

This is probably a longer latent issue since we scrapped resetting
ranges which likely means since RPO VN.  It's always a bit of luck
but I guess since we now track all expressions we have for a value
this got more robust in triggering.  It of course also needs a suitable
simplification to manifest.

I have to think about this.  Simplifying to sth like

  if (flag)
    a = 1;
  if (b & 1 == b) // b [0,1]
    x = a | b;
  else
    x = a | b;
  return x;

should be possible.