[Bug c/104196] New: wrong code at -O2 and above on x86_64-linux-gnu

[Bug c/104196] New: wrong code at -O2 and above on x86_64-linux-gnu

[cnsun at uwaterloo dot ca]

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

            Bug ID: 104196
           Summary: wrong code at -O2 and above on x86_64-linux-gnu
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: cnsun at uwaterloo dot ca
  Target Milestone: ---

$ gcc-trunk small.c -w -O2 ; ./a.out
g_1600=6
$ gcc-trunk small.c -w -O3 ; ./a.out
g_1600=6
$ gcc-trunk small.c -w -O1 ; ./a.out
$ gcc-trunk small.c -w -O0 ; ./a.out
$ cat small.c
int a = 6;
int main() {
  int b;
  for (;;) {
    b = a < 0 && 0 < -2147483647 - a ? 0 : a;
    if (b != 0x8C65C01D) {
      if (a < 6)
        printf("g_1600=%llu\n", (long long)a);
      goto c;
    }
  }
c:;
}
$ gcc-trunk -v
Using built-in specs.
COLLECT_GCC=gcc-trunk
COLLECT_LTO_WRAPPER=/scratch/software/gcc-trunk/libexec/gcc/x86_64-pc-linux-gnu/12.0.1/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: /tmp/tmp.8MPqhHrPX1-gcc-builder/gcc/configure
--enable-languages=c,c++,lto --enable-checking-yes --enable-multiarch
--prefix=/scratch/software/gcc-trunk --disable-bootstrap
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 12.0.1 20220123 (experimental) [master -g9718bc4b0] (GCC) 
$

[Bug middle-end/104196] wrong code at -O2 and above on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

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

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r12-4790-g4b3a325f07acebf47e82de227ce1d5ba62f5bcae
Slightly adjusted testcase:
int a = 6;

int
main ()
{
  while (1)
    {
      int b = a < 0 && 0 < -__INT_MAX__ - a ? 0 : a;
      if (b != 4096 - __INT_MAX__)
        {
          if (a < 6)
            __builtin_abort ();
          break;
        }
    }
  return 0;
}

[Bug tree-optimization/104196] [12 Regression] wrong code at -O2 and above on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2022-01-24
   Target Milestone|---                         |12.0
          Component|middle-end                  |tree-optimization
            Version|unknown                     |12.0
            Summary|wrong code at -O2 and above |[12 Regression] wrong code
                   |on x86_64-linux-gnu         |at -O2 and above on
                   |                            |x86_64-linux-gnu
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |jakub at gcc dot gnu.org
           Priority|P3                          |P1
             Status|UNCONFIRMED                 |NEW

[Bug tree-optimization/104196] [12 Regression] wrong code at -O2 and above on x86_64-linux-gnu

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Here is one which shows the issue just in case fold gets in the way:
int a = 6;
int main() {
    for (;;)
    {
        int c = 111;
        if (a < 0)
            c = -__INT_MAX__ - a;
        int b = a;
        if (a >= 0 || c > 0)
            b = 0;
        if (b != 4096 - __INT_MAX__) {
            if (a < 6)
                __builtin_abort ();
            return 0;
        }
    }
}

The main point is the undefined behavior of -__INT_MAX__ - a when a is not less
than 0 which is not true here as a is always 6.

Also for some reason using the C++ front-end also works around the issue ...
(but I don't see how though).

[Bug tree-optimization/104196] [12 Regression] wrong code at -O2 and above on x86_64-linux-gnu

[pinskia at gcc dot gnu.org]

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

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #2)
> Also for some reason using the C++ front-end also works around the issue ...
> (but I don't see how though).

-ffinite-loops is the difference there.

[Bug tree-optimization/104196] [12 Regression] wrong code at -O2 and above on x86_64-linux-gnu

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
The problem looks like a latent bug in reassoc1.
Before:
if (a.0_1 < 0)
    goto <bb 4>; [41.00%]
  else
    goto <bb 5>; [59.00%]

  <bb 4> [local count: 440234144]:
  # RANGE [-2147483646, 1]
  c_6 = -2147483647 - a.0_1;
  _9 = a.0_1 != -2147479551;
  _4 = c_6 == 1;
  _3 = _4 | _9;
  if (_3 != 0)
    goto <bb 5>; [60.23%]
  else
    goto <bb 3>; [39.77%]

  <bb 5> [local count: 118111600]:
  if (a.0_1 <= 5)
    goto <bb 6>; [0.00%]
  else
    goto <bb 7>; [100.00%]

Which is correct and the overflow only happens in bb 4 which is never reached
here as a == 6.

After reassoc1 we have:
  c_6 = -2147483647 - a.0_1;
  _10 = a.0_1 != -2147479551;
  _9 = a.0_1 != -2147479551;
  _4 = c_6 == 1;
  _12 = _4 | _10;
  if (_12 != 0)
    goto <bb 4>; [60.23%]
  else
    goto <bb 3>; [39.77%]

  <bb 4> [local count: 118111600]:
  if (a.0_1 <= 5)
    goto <bb 5>; [0.00%]
  else
    goto <bb 6>; [100.00%]

Which is totally bogus and I suspect it is because we had that range on c_6
assignment.


>From -fdump-tree-reassoc1-all:

Matching expression match.pd:2080, generic-match.cc:693
Matching expression match.pd:2083, generic-match.cc:753
Matching expression match.pd:2090, generic-match.cc:776
Optimizing range tests a.0_1 +[-2147479551, -2147479551] and -[0, ]
 into a.0_1 == -2147479551
Matching expression match.pd:2080, gimple-match.cc:819
Matching expression match.pd:2083, gimple-match.cc:892
Matching expression match.pd:2090, gimple-match.cc:952

[Bug tree-optimization/104196] [12 Regression] wrong code at -O2 and above on x86_64-linux-gnu

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #4)
> The problem looks like a latent bug in reassoc1.

So it looks like it is a new bug in reassoc1.

[Bug tree-optimization/104196] [12 Regression] wrong code at -O2 and above on x86_64-linux-gnu

[pinskia at gcc dot gnu.org]

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Here is a new testcase where we have the same IR (including the range) in GCC
11.2.0 and the trunk:
int a = 6;
int main() {
     for (;;)
    {
        int c = 111;
        if (a < 0)
            c = 1;
        else
          goto t;
        c = -__INT_MAX__ - a;
        int b = a;
        int tt, ttt;

        tt = a != -2147479551;
        ttt = c == 1;
        tt = tt | ttt;
        if (!tt)
          continue;
        {
            t:
            if (a < 6)
                __builtin_abort ();
            ty:
            return 0;
        }
    }
}

It would be useful to run a bisect on this new one.

[Bug tree-optimization/104196] [12 Regression] wrong code at -O2 and above on x86_64-linux-gnu

[belyshev at depni dot sinp.msu.ru]

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

Serge Belyshev <belyshev at depni dot sinp.msu.ru> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |belyshev at depni dot sinp.msu.ru

--- Comment #7 from Serge Belyshev <belyshev at depni dot sinp.msu.ru> ---
(In reply to Andrew Pinski from comment #6)
> Here is a new testcase where we have the same IR (including the range) in
> GCC 11.2.0 and the trunk:
> ...
> 
> It would be useful to run a bisect on this new one.

Fails since r12-4526-gd8edfadfc7a9795b65177a50ce44fd348858e844

[Bug tree-optimization/104196] [12 Regression] wrong code at -O2 and above on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

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

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
So, to me this doesn't look like a recent reassoc1 regression, but rather
something that been there since
~ r0-119920-gd578e863b08e64789f767c95f85acd10dc477bdf

The inter-bb range optimization pass uses no_side_effect_bb as a test for the
bbs in between, which makes sure that no statements have side-effects, there
are only gimple assignments except for the last GIMPLE_COND and those
statements can't trap and their lhs is consumed within the same bb.

  if (a.1_1 >= 0)
    goto <bb 5>; [59.00%]
  else
    goto <bb 4>; [41.00%]

  <bb 4> [local count: 440234144]:
  _3 = -2147483647 - a.1_1;
  _9 = a.1_1 != -2147479551;
  _4 = _3 == 1;
  _8 = _4 | _9;
  if (_8 != 0)
    goto <bb 5>; [34.51%]
  else
    goto <bb 3>; [65.49%]

is then treated as if ((a.1_1 >= 0) | (-2147483647 - a.1_1 == 1) | (a.1_1 !=
-2147479551)) goto bb5; else goto bb3;
and in there we optimize from there the (a.1_1 >= 0) | (a.1_1 != -2147479551)
part of it into (a.1_1 != -2147479551).  That is all fine, but we have chosen
to put the merged condition into the place of the old _9 test and make the
the a.1_1 >= 0 test (which has been replaced by false).  Usually that doesn't
really matter where we stick it, when merging multiple "ops" into one, one
simply wins (that is the range in update_range_test) and the other(s) are
marked
as true/false (otherrange ... otherrange + count - 1).
The problem above is that the _3 = -2147483647 - a.1_1; stmt is done in
undefined overflow type and thus can trigger UB where there wasn't one before
for certain values.

One possibility to fix this would be to punt on statements like that in
no_side_effect_bb (e.g. the normal way to encode a range is using unsigned
arithmetics).  But I'd be afraid we could easily regress on what the
optimization can handle.

Another possibility is try to be smarter in update_range_test.  Instead of
always picking range->idx as the winner and otherrange*->idx as the stmts
replaced by false or true, perhaps we should try to be smarter, go through them
all first and pick the one from the first bb (one dominating all the other ops)
and if the merge is successful, swap range->idx with the most dominating
otherrange->idx.

So, instead of the problematic
  <bb 2> [local count: 118111598]:

  <bb 3> [local count: 1073741824]:
  a.1_1 = a;
  _3 = -2147483647 - a.1_1;
  _10 = a.1_1 != -2147479551;
  _9 = a.1_1 != -2147479551;
  _4 = _3 == 1;
  _2 = _4 | _10;
  if (_2 != 0)
    goto <bb 4>; [34.51%]
  else
    goto <bb 3>; [65.49%]
we'd get
  a.1_1 = a;
  if (a.1_1 != -2147479551)
    goto <bb 5>; [59.00%]
  else
    goto <bb 4>; [41.00%]

  <bb 4> [local count: 440234144]:
  _3 = -2147483647 - a.1_1;
  _9 = 0;
  _4 = _3 == 1;
  _8 = _4 | _9;
  if (_8 != 0)
    goto <bb 5>; [34.51%]
  else
    goto <bb 3>; [65.49%]


Another question but that is GCC 13 material is why we don't optimize
int
foo (int x)
{
  return -2147483647 - x <= 0;
}
into:
  return x >= -2147483647
during GIMPLE (we optimize it during expansion it seems).

[Bug tree-optimization/104196] [12 Regression] wrong code at -O2 and above on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 52290
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=52290&action=edit
gcc12-pr104196.patch

Untested fix.

[Bug tree-optimization/104196] [12 Regression] wrong code at -O2 and above on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

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

--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The above patch unfortunately causes ICE on -O2:
int a, b, c;

void
foo (void)
{
  if (!c && !b)
    a |= 1;
}

optimize_range_tests_cmp_bitwise in that case wants to optimize the:
  <bb 2> [local count: 1073741824]:
  c.0_1 = c;
  if (c.0_1 == 0)
    goto <bb 3>; [50.00%]
  else
    goto <bb 5>; [50.00%]

  <bb 3> [local count: 536870913]:
  b.1_2 = b;
  if (b.1_2 == 0)
    goto <bb 4>; [50.00%]
  else
    goto <bb 5>; [50.00%]

  <bb 4> [local count: 268435456]:

into
  c.0_1 = c;
  b.1_2 = b;
  _8 = b.1_2 | c.0_1;
  _9 = _8 == 0;
  if (_9 != 0)
and has a seq argument with that
_8 = c.0_1 | b.1_2;
in it.  But it depends on b.1_2 so has to be done only in the spot of the
second comparison and not the first one.
So, I think we need to check if exp's SSA_NAME_DEF_STMT if any or any
SSA_NAME's SSA_NAME_DEF_STMT for SSA_NAMEs mentioned in seq isn't
reassoc_stmt_dominates_stmt_p by the stmt we are considering doing it at.
If it isn't, we can do what the patch does, otherwise should do what we were
doing before but with extra verification if there could be any UB in between.

[Bug tree-optimization/104196] [12 Regression] wrong code at -O2 and above on x86_64-linux-gnu

[cvs-commit at gcc dot gnu.org]

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

--- Comment #11 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:82c8ff79d06cc7d389c72f94d4443c509cf85313

commit r12-6888-g82c8ff79d06cc7d389c72f94d4443c509cf85313
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Thu Jan 27 10:47:00 2022 +0100

    reassoc: Fix up inter-bb range optimization [PR104196]

    As mentioned in the PR, reassoc1 miscompiles following testcase.
    We have:
      if (a.1_1 >= 0)
        goto <bb 5>; [59.00%]
      else
        goto <bb 4>; [41.00%]

      <bb 4> [local count: 440234144]:
      _3 = -2147483647 - a.1_1;
      _9 = a.1_1 != -2147479551;
      _4 = _3 == 1;
      _8 = _4 | _9;
      if (_8 != 0)
        goto <bb 5>; [34.51%]
      else
        goto <bb 3>; [65.49%]

    and the inter-bb range test optimization treats it as:
      if ((a.1_1 >= 0)
          | (-2147483647 - a.1_1 == 1)
          | (a.1_1 != -2147479551))
        goto bb5;
      else
        goto bb3;
    and recognizes that a.1_1 >= 0 is redundant with a.1_1 != -2147479551
    and so will optimize it into:
      if (0
          | (-2147483647 - a.1_1 == 1)
          | (a.1_1 != -2147479551))
        goto bb5;
      else
        goto bb3;
    When merging 2 comparisons, we use update_range_test which picks one
    of the comparisons as the one holding the result (currently always
    the RANGE one rather than all the OTHERRANGE* ones) and adjusts the
    others to be true or false.
    The problem with doing that is that means the
      _3 = -2147483647 - a.1_1;
    stmt with undefined behavior on overflow used to be conditional before
    but now is unconditional.  reassoc performs a no_side_effect_bb check
    which among other checks punts on gimple_has_side_effects and
    gimple_assign_rhs_could_trap_p stmts as well as ones that have uses of
    their lhs outside of the same bb, but it doesn't punt for this potential
    signed overflow case.

    Now, for this testcase, it can be fixed in update_range_test by being
    smarter and choosing the other comparison to modify.  This is achieved
    by storing into oe->id index of the bb with GIMPLE_COND the
    comparison feeds into not just for the cases where the comparison is
    the GIMPLE_COND itself, but in all cases, and then finding oe->id that
    isn't dominated by others.  If we find such, use that oe for the merge
    test and if successful, swap range->idx and swap_with->idx.
    So for the above case we optimize it into:
      if ((a.1_1 != -2147479551)
          | (-2147483647 - a.1_1 == 1)
          | 0)
        goto bb5;
      else
        goto bb3;
    instead.

    Unfortunately, this doesn't work in all cases,
    optimize_range_tests_to_bit_test and
    optimize_range_tests_cmp_bitwise optimizations use non-NULL seq
    to update_range_test and they carefully choose a particular comparison
    because the sequence then uses SSA_NAMEs that may be defined only in
    their blocks.  For that case, the patch keeps using the chosen comparison
    but if the merge is successful, rewrites stmts with signed overflow
behavior
    into defined overflow.
    For this I ran into a problem, rewrite_to_defined_overflow returns a
    sequence that includes the original stmt with modified arguments, this
means
    it needs to be gsi_remove first.  Unfortunately, gsi_remove regardless of
    the remove_permanently argument creates debug temps for the lhs, which I
    think is quite undesirable here.  So I've added an argument (default to
    false) to rewrite_to_defined_overflow to do the modification in place
    without the need to remove the stmt.

    2022-01-27  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/104196
            * gimple-fold.h (rewrite_to_defined_overflow): Add IN_PLACE
argument.
            * gimple-fold.cc (rewrite_to_defined_overflow): Likewise.  If true,
            return NULL and emit needed stmts before and after stmt.
            * tree-ssa-reassoc.cc (update_range_test): For inter-bb range opt
            pick as operand_entry that will hold the merged test the one
feeding
            earliest condition, ensure that by swapping range->idx with some
            other range's idx if needed.  If seq is non-NULL, don't actually
swap
            it but instead rewrite stmts with undefined overflow in between
            the two locations.
            (maybe_optimize_range_tests): Set ops[]->id to bb->index with the
            corresponding condition even if they have non-NULL ops[]->op.
            Formatting fix.

            * gcc.c-torture/execute/pr104196.c: New test.

[Bug tree-optimization/104196] [12 Regression] wrong code at -O2 and above on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed.