[Bug c/106892] New: Wrong code at -O3 on x86_64-linux-gnu

[Bug c/106892] New: Wrong code at -O3 on x86_64-linux-gnu

[shaohua.li at inf dot ethz.ch]

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

            Bug ID: 106892
           Summary: Wrong code at -O3 on x86_64-linux-gnu
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: shaohua.li at inf dot ethz.ch
  Target Milestone: ---

$ gcc-tk -v
Using built-in specs.
COLLECT_GCC=gcc-tk
COLLECT_LTO_WRAPPER=/zdata/shaoli/compilers/ccbuilder-compilers/gcc-75f59441cd63a1d07e86d70d59c518049f53904f/libexec/gcc/x86_64-pc-linux-gnu/13.0.0/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: ../configure --disable-multilib --disable-bootstrap
--enable-languages=c,c++
--prefix=/zdata/shaoli/compilers/ccbuilder-compilers/gcc-75f59441cd63a1d07e86d70d59c518049f53904f
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 13.0.0 20220830 (experimental) (GCC)
$
$ gcc-tk -w -O0 simple.c && ./a.out
0
$ gcc-tk -w -O0 simple.c && ./a.out
3
$ 
$ cat simple.c
a, b, c, d, e;
f[8];
g() {
  while (a)
    a >>= 4;
}
h(i) {
  if (i >= '0')
    return i - '0';
}
j(i) {
  b = 2;
  for (; g() <= 7; b++)
    if (i) {
      for (; e <= 7; e++) {
        c = 1;
        for (; c <= 7; c++) {
          d = h(b + 48);
          f[-d + 4] ^= 3;
        }
      }
      return;
    }
}
main() {
  j(1);
  printf("%d\n", f[2]);
}
$

[Bug c/106892] Wrong code at -O3 on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
This is UB, isn't it?
g() <= 7 when g implicitly returns int, but doesn't return anything, falls
through to the end instead.

[Bug c/106892] Wrong code at -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2022-09-09
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |WAITING

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
possibly too much reduced?

[Bug c/106892] Wrong code at -O3 on x86_64-linux-gnu

[shaohua.li at inf dot ethz.ch]

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

--- Comment #3 from Li Shaohua <shaohua.li at inf dot ethz.ch> ---
Yes, I reduced it too much. Here is the new one with return value in g()
function.

a, b, c, d, e;
f[8];
g() {
  while (a)
    a >>= 4;
  return 0;
}
h(i) {
  if (i >= '0')
    return i - '0';
}
j(i) {
  b = 2;
  for (; g() <= 7; b++)
    if (i) {
      for (; e <= 7; e++) {
        c = 1;
        for (; c <= 7; c++) {
          d = h(b + 48);
          f[-d + 4] ^= 3;
        }
      }
      return;
    }
}
main() {
  j(1);
  printf("%d\n", f[2]);
}

[Bug c/106892] Wrong code at -O3 on x86_64-linux-gnu

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |NEW
                 CC|                            |rguenth at gcc dot gnu.org
           Keywords|                            |wrong-code

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Li Shaohua from comment #3)
> Yes, I reduced it too much. Here is the new one with return value in g()
> function.
> 
> a, b, c, d, e;
> f[8];
> g() {
>   while (a)
>     a >>= 4;
>   return 0;
> }
> h(i) {
>   if (i >= '0')
>     return i - '0';
> }
> j(i) {
>   b = 2;
>   for (; g() <= 7; b++)
>     if (i) {
>       for (; e <= 7; e++) {
>         c = 1;
>         for (; c <= 7; c++) {
>           d = h(b + 48);
>           f[-d + 4] ^= 3;
>         }
>       }
>       return;
>     }
> }
> main() {
>   j(1);
>   printf("%d\n", f[2]);
> }

When I apply the same "fix" to h() (add a return 0 or __builtin_unreachable ())
the code works again.

Note I think the missing return stmt isn't reached at runtime.

Disabling either unswitching or loop splitting makes the issue go away,
enabling both ontop of -O2 doesn't trigger it.

We early inline h into j where h looks like

int h (int i)
{
  int _3;

  <bb 2> :
  if (i_1(D) > 47)
    goto <bb 3>; [INV]
  else
    goto <bb 4>; [INV]

  <bb 3> :
  _3 = i_1(D) + -48;
  // predicted unlikely by early return (on trees) predictor.
  return _3;

  <bb 4> :
  return;

}

which results in

  b.2_1 = b;
  _2 = b.2_1 + 48;
  _3 = h (_2);
  d = _3;

becoming

  b.2_1 = b;
  _2 = b.2_1 + 48;
  if (_2 > 47)
    goto <bb 6>; [34.00%]
  else
    goto <bb 7>; [66.00%]

  <bb 6> :
  _30 = _2 + -48;
  _43 = _30;

  <bb 7> :
  # _39 = PHI <_43(6), _37(5)>
  _3 = _39;
  d = _3;

note that the return; case results in _37 to be used which is completely
random.

That said, our handling of an unreachable missing return in the IL is
likely counter productive.

Cleaned up testcase:

int a, b, c, d, e;
int f[8];
int g() {
  while (a)
    a >>= 4;
  return 0;
}
int h(int i) {
  if (i >= '0')
    return i - '0';
  //__builtin_unreachable ();
}
void j(int i) {
  b = 2;
  for (; g() <= 7; b++)
    if (i) {
      for (; e <= 7; e++) {
        c = 1;
        for (; c <= 7; c++) {
          d = h(b + 48);
          f[-d + 4] ^= 3;
        }
      }
      return;
    }
}
int main() {
  j(1);
  if (f[2] != 0)
    __builtin_abort ();
}

[Bug c/106892] Wrong code at -O3 on x86_64-linux-gnu

[marxin at gcc dot gnu.org]

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

--- Comment #5 from Martin Liška <marxin at gcc dot gnu.org> ---
Clean up test-case:

$ cat pr106892.c
int a, b, c, d, e;
int f[8];

int
g() {
  while (a)
    a >>= 4;
  return 0;
}

int
h(int i) {
  if (i >= '0')
    return i - '0';
}

void
j(int i) {
  b = 2;
  for (; g() <= 7; b++)
    if (i) {
      for (; e <= 7; e++) {
        c = 1;
        for (; c <= 7; c++) {
          d = h(b + 48);
          f[-d + 4] ^= 3;
        }
      }
      return;
    }
}

int
main() {
  j(1);
  __builtin_printf("%d\n", f[2]);
  if (f[2] != 0)
    __builtin_abort ();
  return 0;
}

Started to print '3' since r11-963-g80d6f89e78fc3b77.

[Bug c/106892] Wrong code at -O3 on x86_64-linux-gnu

[jakub at gcc dot gnu.org]

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

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
I would clean it even more:
int a, b, c, d, e;
int f[8];
int g() {
  while (a)
    a >>= 4;
  return 0;
}
int h(int i) {
  if (i >= '0')
    return i - '0';
  //__builtin_unreachable ();
}
void j(int i) {
  for (b = 2; g() <= 7; b++)
    if (i) {
      for (; e <= 7; e++)
        for (c = 1; c <= 7; c++) {
          d = h(b + '0');
          f[-d + 4] ^= 3;
        }
      return;
    }
}
int main() {
  j(1);
  if (f[2] != 0)
    __builtin_abort ();
}
so that a) it isn't ASCII specific and misbehaves for EBCDIC etc., and b)
undoes what creduce/cvise likes to do, moving expressions from for init
expression before the loop

[Bug c/106892] [11/12/13 Regression] Wrong code at -O3 on x86_64-linux-gnu since r11-963-g80d6f89e78fc3b77

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
So the inline just has the return undefined in the unreachable path.  We can
make the inlined functions static (cleans up post-IPA dumps) and disable IPA
for j:

int a, b, c, d, e;
int f[8];
static int g() {
  while (a)
    a >>= 4;
  return 0;
}
static int h(int i) {
  if (i >= '0')
    return i - '0';
  //__builtin_unreachable ();
}
void __attribute__((noipa)) j(int i) {
  for (b = 2; g() <= 7; b++)
    if (i) {
      for (; e <= 7; e++)
        for (c = 1; c <= 7; c++) {
          d = h(b + '0');
          f[-d + 4] ^= 3;
        }
      return;
    }
}
int main() {
  j(1);
  if (f[2] != 0)
    __builtin_abort ();
}

[Bug middle-end/106892] [11/12/13 Regression] Wrong code at -O3 on x86_64-linux-gnu since r11-963-g80d6f89e78fc3b77

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|c                           |middle-end
   Target Milestone|---                         |11.4

[Bug middle-end/106892] [11/12/13 Regression] Wrong code at -O3 on x86_64-linux-gnu since r11-963-g80d6f89e78fc3b77

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
-fno-gcse-lm fixes the testcase.  The only difference from the bisected
revision is

 (insn 56 55 57 15 (set (mem:SI (plus:DI (mult:DI (reg:DI 102)
                     (const_int 4 [0x4]))
-                (reg/f:DI 99)) [1 f S4 A32])
+                (reg/f:DI 99)) [1 f[_137]+0 S4 A32])
         (reg:SI 105)) "t.c":19:21 -1
      (nil))

and PRE then does

-PRE GCSE of j, 23 basic blocks, 3800 bytes needed, 0 substs, 0 insns created
+scanning new insn with uid = 106.
+deleting insn with uid = 54.
+PRE: redundant insn 54 (expression 5) in bb 15, reaching reg is 107
+PRE: edge (14,15), copy expression 5
+scanning new insn with uid = 107.
+PRE GCSE of j, 23 basic blocks, 3848 bytes needed, 1 substs, 1 insns created

it looks like RTL PRE hoists

(insn 54 50 55 15 (set (reg:SI 106 [ MEM[(int *)_20 + 16B] ])
        (mem:SI (plus:DI (reg/f:DI 86 [ _20 ])
                (const_int 16 [0x10])) [1 MEM[(int *)_20 + 16B]+0 S4 A32]))
"t.c":19:21 67 {*movsi_internal}
     (nil))

out of the loop, across

(insn 56 55 57 15 (set (mem:SI (plus:DI (mult:DI (reg:DI 102)
                    (const_int 4 [0x4]))
                (symbol_ref:DI ("f") [flags 0x2]  <var_decl 0x7fb59de26e10 f>))
[1 f[_137]+0 S4 A32])
        (reg:SI 105)) "t.c":19:21 67 {*movsi_internal}
     (expr_list:REG_DEAD (reg:SI 105)
        (expr_list:REG_DEAD (reg:DI 102)
            (expr_list:REG_DEAD (reg/f:DI 99)
                (nil)))))

I will see why exactly.

[Bug middle-end/106892] [11/12/13 Regression] Wrong code at -O3 on x86_64-linux-gnu since r11-963-g80d6f89e78fc3b77

[rguenth at gcc dot gnu.org]

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

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
So the reason is that we have

  # RANGE [-2147483643, 2]
  _137 = 4 - prephitmp_80;
 f[_137] = _139;

which makes us conclude the f[_137] access is constrained to f[0..2].  When
we see

  _75 = MEM[(int *)_20 + 16B];

we then disambiguate because iff _20 points into 'f' then with offset 16
it's beyond that constrained access.  _But_!

  # RANGE [18446744065119617028, 18446744073709551608]
  _5 = _39 * -4U;
  # PT = anything
  _20 = &f + _5;

_20 is actually _before_ 'f' which we consider invalid.

Now here's what the frontend presents us with:

      f[4 - d] = f[4 - d] ^ 3;

which we eventually gimplify to

  _5 = 4 - d.1_4;
  _6 = f[_5];

but then predictive commoning comes along:

Load motion chain 0x43bb3d0
  inits MEM[(int *)_20 + 16B]
  references:
    f[_2] (id 0)
      offset 0
      distance 0
    f[_2] (id 1, write)
      offset 0
      distance 0

Executing predictive commoning without unrolling

   <bb 36> [local count: 35740571]:
+  _39 = (sizetype) prephitmp_80;
+  _5 = _39 * 18446744073709551612;
+  _20 = &f + _5;
+  _75 = MEM[(int *)_20 + 16B];

   <bb 11> [local count: 289173710]:
   # ivtmp_48 = PHI <ivtmp_68(22), 7(36)>
+  # f_I_lsm0.27_12 = PHI <f_I_lsm0.27_1(22), _75(36)>
   _2 = 4 - prephitmp_80;
-  _3 = f[_2];
+  _3 = f_I_lsm0.27_12;

introducing this kind of problem.  We have a "opt-out" with using
TARGET_MEM_REF which is exempt from this rule because IVOPTs also likes to
break it.

[Bug middle-end/106892] [11/12/13 Regression] Wrong code at -O3 on x86_64-linux-gnu since r11-963-g80d6f89e78fc3b77

[rguenth at gcc dot gnu.org]

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

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
So it's aready dataref analysis that tears apart the constant offset for
dr.innermost, here as

DR_BASE_ADDRESS &f
DR_OFFSET (ssizetype) ((sizetype) prephitmp_80 * 18446744073709551612)
DR_INIT 16

but ref_at_iteration associates that in an invalid way.

I'm testing a patch.

[Bug middle-end/106892] [11/12/13 Regression] Wrong code at -O3 on x86_64-linux-gnu since r11-963-g80d6f89e78fc3b77

[rguenth at gcc dot gnu.org]

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

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
The master branch has been updated by Richard Biener <rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:a8b0b13da7379feb31950a9d2ad74b98a29c547f

commit r13-2560-ga8b0b13da7379feb31950a9d2ad74b98a29c547f
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Sep 9 12:06:38 2022 +0200

    tree-optimization/106722 - avoid invalid pointer association in predcom

    When predictive commoning builds a reference for iteration N it
    prematurely associates a constant offset into the MEM_REF offset
    operand which can be invalid if the base pointer then points
    outside of an object which alias-analysis does not consider valid.

            PR tree-optimization/106722
            * tree-predcom.cc (ref_at_iteration): Do not associate the
            constant part of the offset into the MEM_REF offset
            operand, across a non-zero offset.

            * gcc.dg/torture/pr106892.c: New testcase.

[Bug middle-end/106892] [11/12 Regression] Wrong code at -O3 on x86_64-linux-gnu since r11-963-g80d6f89e78fc3b77

[mikpelinux at gmail dot com]

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

Mikael Pettersson <mikpelinux at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mikpelinux at gmail dot com

--- Comment #12 from Mikael Pettersson <mikpelinux at gmail dot com> ---
(In reply to Richard Biener from comment #11)
>             PR tree-optimization/106722

Shouldn't that be 106892?

>             * tree-predcom.cc (ref_at_iteration): Do not associate the
>             constant part of the offset into the MEM_REF offset
>             operand, across a non-zero offset.
>     
>             * gcc.dg/torture/pr106892.c: New testcase.

[Bug middle-end/106892] [11/12 Regression] Wrong code at -O3 on x86_64-linux-gnu since r11-963-g80d6f89e78fc3b77

[marxin at gcc dot gnu.org]

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

--- Comment #13 from Martin Liška <marxin at gcc dot gnu.org> ---
> Shouldn't that be 106892?

Right, I at least fixed ChangeLog entry in
g:3fa66b95570a125fd35d5721c9eb08d975f73e82.

[Bug middle-end/106892] [11/12 Regression] Wrong code at -O3 on x86_64-linux-gnu since r11-963-g80d6f89e78fc3b77

[cvs-commit at gcc dot gnu.org]

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

--- Comment #14 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-12 branch has been updated by Richard Biener
<rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:2b9e1f7ff476059724cca4b11d39972655d4468f

commit r12-8819-g2b9e1f7ff476059724cca4b11d39972655d4468f
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Sep 9 12:06:38 2022 +0200

    tree-optimization/106892 - avoid invalid pointer association in predcom

    When predictive commoning builds a reference for iteration N it
    prematurely associates a constant offset into the MEM_REF offset
    operand which can be invalid if the base pointer then points
    outside of an object which alias-analysis does not consider valid.

            PR tree-optimization/106892
            * tree-predcom.cc (ref_at_iteration): Do not associate the
            constant part of the offset into the MEM_REF offset
            operand, across a non-zero offset.

            * gcc.dg/torture/pr106892.c: New testcase.

    (cherry picked from commit a8b0b13da7379feb31950a9d2ad74b98a29c547f)

[Bug middle-end/106892] [11 Regression] Wrong code at -O3 on x86_64-linux-gnu since r11-963-g80d6f89e78fc3b77

[cvs-commit at gcc dot gnu.org]

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

--- Comment #15 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-11 branch has been updated by Richard Biener
<rguenth@gcc.gnu.org>:

https://gcc.gnu.org/g:d4bcab0b622cf8f2b6aadd982155c7e2d37d5887

commit r11-10317-gd4bcab0b622cf8f2b6aadd982155c7e2d37d5887
Author: Richard Biener <rguenther@suse.de>
Date:   Fri Sep 9 12:06:38 2022 +0200

    tree-optimization/106892 - avoid invalid pointer association in predcom

    When predictive commoning builds a reference for iteration N it
    prematurely associates a constant offset into the MEM_REF offset
    operand which can be invalid if the base pointer then points
    outside of an object which alias-analysis does not consider valid.

            PR tree-optimization/106892
            * tree-predcom.c (ref_at_iteration): Do not associate the
            constant part of the offset into the MEM_REF offset
            operand, across a non-zero offset.

            * gcc.dg/torture/pr106892.c: New testcase.

    (cherry picked from commit a8b0b13da7379feb31950a9d2ad74b98a29c547f)

[Bug middle-end/106892] [11 Regression] Wrong code at -O3 on x86_64-linux-gnu since r11-963-g80d6f89e78fc3b77

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |11.3.0
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED
      Known to work|                            |11.3.1

--- Comment #16 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed.