[Bug tree-optimization/116747] New: ICE on valid code at -O3 on x86_64-linux-gnu: Segmentation fault

[Bug tree-optimization/116747] New: ICE on valid code at -O3 on x86_64-linux-gnu: Segmentation fault

[zhendong.su at inf dot ethz.ch]

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

            Bug ID: 116747
           Summary: ICE on valid code at -O3 on x86_64-linux-gnu:
                    Segmentation fault
           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 14.2 and
earlier.

Compiler Explorer: https://godbolt.org/z/rsP3bWqTn

[511] % 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 20240917 (experimental) (GCC) 
[512] % 
[512] % gcctk -O3 small.c
during GIMPLE pass: cselim
small.c: In function ‘main’:
small.c:2:5: internal compiler error: Segmentation fault
    2 | int main() {
      |     ^~~~
0x25acc85 internal_error(char const*, ...)
        ../../gcc-trunk/gcc/diagnostic-global-context.cc:517
0x11bd043 crash_signal
        ../../gcc-trunk/gcc/toplev.cc:321
0x7f49c67ed08f ???
       
/build/glibc-LcI20x/glibc-2.31/signal/../sysdeps/unix/sysv/linux/x86_64/sigaction.c:0
0xdf141b gsi_for_stmt(gimple*)
        ../../gcc-trunk/gcc/gimple-iterator.cc:616
0x139e6a1 cond_if_else_store_replacement_1
        ../../gcc-trunk/gcc/tree-ssa-phiopt.cc:3479
0x13a512c cond_if_else_store_replacement
        ../../gcc-trunk/gcc/tree-ssa-phiopt.cc:3734
0x13a512c operator()
        ../../gcc-trunk/gcc/tree-ssa-phiopt.cc:4463
0x13a512c execute_over_cond_phis<(anonymous
namespace)::pass_cselim::execute(function*)::<lambda(basic_block, basic_block,
basic_block, edge, edge, bool, gcond*)> >
        ../../gcc-trunk/gcc/tree-ssa-phiopt.cc:4016
0x13a512c execute
        ../../gcc-trunk/gcc/tree-ssa-phiopt.cc:4483
Please submit a full bug report, with preprocessed source (by using
-freport-bug).
Please include the complete backtrace with any bug report.
See <https://gcc.gnu.org/bugs/> for instructions.
[513] % 
[513] % cat small.c
int a, b, c, d[1], e, f[8], g, h;
int main() {
  int j, k[8], i = 0;
  for (; i < 1; i++)
    g = 1;
  while (c) {
    while (e < 1)
      ;
    j = 1;
    for (; j < 8; j++) {
      h = a ? a : b;
      c = h || (k[8] = g || (f[e] = k[8])) < 0;
      d[e] = 1 & f[e + 1];
    }
  }
  return 0;
}

[Bug tree-optimization/116747] [15 Regression] ICE on valid code at -O3 on x86_64-linux-gnu: Segmentation fault

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |ice-on-valid-code
   Target Milestone|---                         |15.0
            Summary|ICE on valid code at -O3 on |[15 Regression] ICE on
                   |x86_64-linux-gnu:           |valid code at -O3 on
                   |Segmentation fault          |x86_64-linux-gnu:
                   |                            |Segmentation fault

[Bug tree-optimization/116747] [15 Regression] ICE on valid code at -O3 on x86_64-linux-gnu: Segmentation fault

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2024-09-17

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

Looks like this is a latent bug in cselim.


Before cselim we have:
```
  if (iftmp.1_29 != 0)
    goto <bb 12>; [66.67%]
  else
    goto <bb 11>; [33.33%]

  <bb 11> [local count: 59055800]:
  # _51 = PHI <_50(10)>
  _94 = f[_51];
  _73 = _94 & 1;
  d[e.0_43] = _73;
  _57 = f[_51];
  _58 = _57 & 1;
  d[e.0_43] = _58;
  _101 = f[_51];
  _80 = _101 & 1;
  d[e.0_43] = _80;
  goto <bb 13>; [100.00%]

  <bb 12> [local count: 59055800]:
  # _55 = PHI <_50(10)>
  _10 = f[_55];
  _17 = _10 & 1;
  d[e.0_43] = _17;
  _63 = f[_55];
  _41 = _63 & 1;
  d[e.0_43] = _41;

  <bb 13> [local count: 118111600]:
  # _53 = PHI <_55(12), _51(11)>
```

Notice how there are uneven # of stores on one side of the if.
so we match up the pairs and for one of them we double up.

[Bug tree-optimization/116747] [15 Regression] ICE on valid code at -O3 on x86_64-linux-gnu: Segmentation fault

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|                            |x86_64

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Later today I will try to create a gimple testcase as the code has been broken
since it was added in r0-107409-gbfe068c3d311b0 (for GCC 4.7.0).


Note I think it was exposed starting wth r15-571-g1e0ae1f52741f7 .

[Bug tree-optimization/116747] [15 Regression] ICE on valid code at -O3 on x86_64-linux-gnu: Segmentation fault

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Actually started with r15-1163-g818e760528d436ea8f6c28ef620e2bb82d456ea1

[Bug tree-optimization/116747] [15 Regression] ICE on valid code at -O3 on x86_64-linux-gnu: Segmentation fault

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #3)
> Actually started with r15-1163-g818e760528d436ea8f6c28ef620e2bb82d456ea1

Oh ok, I figured it was a DSE change which exposed it.
I am still trying to figure out how to get a gimple testcase, a C testcase with
`-fno-tree-dse -fno-tree-fre -O3` does not reproduce the issue though. But
maybe I am testing it incorrectly. Maybe I need -fno-tree-vectorizer too.

[Bug tree-optimization/116747] [15 Regression] ICE on valid code at -O3 on x86_64-linux-gnu: Segmentation fault

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So a gimple testcase does not fail.

[Bug tree-optimization/116747] [15 Regression] ICE on valid code at -O3 on x86_64-linux-gnu: Segmentation fault

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I am going to fix this. I am still trying to understand datarefs code part and
why it just happens to work with the gimple testcase.

[Bug tree-optimization/116747] [15 Regression] ICE on valid code at -O3 on x86_64-linux-gnu: Segmentation fault

[pinskia at gcc dot gnu.org]

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

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So reading the code:
Check that there are no read-after-write or write-after-write dependencies
     in THEN_BB.

  /* Check that there are no read-after-write or write-after-write dependencies
     in ELSE_BB.  */

Should have caught this case but for some reason it is not.

[Bug tree-optimization/116747] [15 Regression] ICE on valid code at -O3 on x86_64-linux-gnu: Segmentation fault

[pinskia at gcc dot gnu.org]

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

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
1: dump_data_dependence_relation(stdout, ddr) = (Data Dep:
#(Data Ref:
#  bb: 12
#  stmt: d[e.0_43] = _17;
#  ref: d[e.0_43];
#  base_object: d[e.0_43];
#)
#(Data Ref:
#  bb: 12
#  stmt: d[e.0_43] = _41;
#  ref: d[e.0_43];
#  base_object: d[e.0_43];
#)
    (no dependence)
)


That is wrong. This is a write after write dependency.

The question now becomes why DDR_ARE_DEPENDENT is chrec_known.
Even though it is obvious. So the bug is not in phiopt at all it seems but
tree-data-ref.cc.

[Bug tree-optimization/116747] [15 Regression] ICE on valid code at -O3 on x86_64-linux-gnu: Segmentation fault

[pinskia at gcc dot gnu.org]

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

--- Comment #9 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Looks like dr_may_alias_p is returning the wrong result.

[Bug tree-optimization/116747] [15 Regression] ICE on valid code at -O3 on x86_64-linux-gnu: Segmentation fault

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |alias
             Status|ASSIGNED                    |NEW

--- Comment #10 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Since it is an aliasing over to richi I think.

phiopt/cselim looks to be doing the correct thing and asking the correct
questions too.

[Bug tree-optimization/116747] [15 Regression] ICE on valid code at -O3 on x86_64-linux-gnu: Segmentation fault

[pinskia at gcc dot gnu.org]

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

--- Comment #11 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Note if I have refs_may_alias_p return true always, the code to check to see if
there was a write after write dependent store happening works and cselim does
nothing here.

[Bug tree-optimization/116747] [12/13/14/15 Regression] ICE on valid code at -O3 on x86_64-linux-gnu: Segmentation fault

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[15 Regression] ICE on      |[12/13/14/15 Regression]
                   |valid code at -O3 on        |ICE on valid code at -O3 on
                   |x86_64-linux-gnu:           |x86_64-linux-gnu:
                   |Segmentation fault          |Segmentation fault
      Known to work|                            |8.5.0
           Assignee|pinskia at gcc dot gnu.org         |unassigned at gcc dot gnu.org
      Known to fail|                            |9.1.0

--- Comment #12 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
decl_refs_may_alias_p (ref1=0x7ffff79edf88, base1=0x7ffff7810e10, offset1=...,
max_size1=..., size1=..., ref2=0x7ffff79eddc8, base2=0x7ffff7810e10,
offset2=..., max_size2=..., size2=...) at
/home/apinski/src/upstream-gcc-isel/gcc/gcc/tree-ssa-alias.cc:2051
2051      gcc_checking_assert (DECL_P (base1) && DECL_P (base2));
(gdb) next
2054      if (compare_base_decls (base1, base2) == 0)
(gdb)
2059      if (!ranges_maybe_overlap_p (offset1, max_size1, offset2, max_size2))
(gdb)
2060        return false;
(gdb) p offset1
$11 = {coeffs = {32}}
(gdb) p max_size1
$12 = {coeffs = {0}}
(gdb) p offset2
$13 = {coeffs = {32}}
(gdb) p max_size2
$14 = {coeffs = {0}}

Reduced testcase that fails in GCC 14 and the way back to GCC 9.1.0 even.
Compile with `-fno-tree-fre -fno-tree-dse -O3` .


```
int array1[1];
int array2[1];
int f(int a, int b, int c)
{
        if (b < 1)  __builtin_unreachable();

        if (a)
        {
                array1[b] = c;
                array1[b] = c;
        }
        else
        {
                array1[b] = c;
        }
}
int f1(int a, unsigned short b1, int c)
{
        int b = b1;
        b++;

        if (a)
        {
                array1[b] = c;
                array1[b] = c;
        }
        else
        {
                array1[b] = c;
        }
}
```

This code (and the original one) is undefined due to accessing out side of the
array bounds.

[Bug tree-optimization/116747] [12/13/14/15 Regression] ICE on valid code at -O3 on x86_64-linux-gnu: Segmentation fault

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|15.0                        |12.5

--- Comment #13 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
This fixes the ICE but I am not 100% sure if this is the right approach or
should we change how write after write checks are done.

diff --git a/gcc/tree-ssa-phiopt.cc b/gcc/tree-ssa-phiopt.cc
index d43832b390b..6da60771702 100644
--- a/gcc/tree-ssa-phiopt.cc
+++ b/gcc/tree-ssa-phiopt.cc
@@ -3451,7 +3451,10 @@ cond_if_else_store_replacement_1 (basic_block then_bb,
basic_block else_bb,
       || else_assign == NULL
       || !gimple_assign_single_p (else_assign)
       || gimple_clobber_p (else_assign)
-      || gimple_has_volatile_ops (else_assign))
+      || gimple_has_volatile_ops (else_assign)
+      /* If there was undefined behavior, else_assign might
+        have been removed already. */
+      || !gimple_bb (else_assign))
     return false;

   lhs = gimple_assign_lhs (then_assign);

[Bug tree-optimization/116747] [12/13/14/15 Regression] ICE on valid code at -O3 on x86_64-linux-gnu: Segmentation fault

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #14 from Richard Biener <rguenth at gcc dot gnu.org> ---
I think the issue is that we somehow recognize two then_stores (OK) but also
two else_stores (not OK, there's just one store there).  That is, the loop

  /* Find pairs of stores with equal LHS.  */
  auto_vec<gimple *, 1> then_stores, else_stores;
  FOR_EACH_VEC_ELT (then_datarefs, i, then_dr)
    {
      if (DR_IS_READ (then_dr))
        continue;

      then_store = DR_STMT (then_dr);
      then_lhs = gimple_get_lhs (then_store);
      if (then_lhs == NULL_TREE)
        continue;
      found = false;

      FOR_EACH_VEC_ELT (else_datarefs, j, else_dr)
        {

happily picks stmts from else_datarefs twice.

I'll note that we check dependences for all stores but limit ourselves with
param_max_stores_to_sink only with the candidates to sink which doesn't
avoid possible quadraticness nicely.  Instead limiting the size of
then_datarefs/else_datarefs would be more appropriate.

Also we only need dependences of a subset of stmts (below the earliest
candidates found).

[Bug tree-optimization/116747] [12/13/14/15 Regression] ICE on valid code at -O3 on x86_64-linux-gnu: Segmentation fault

[cvs-commit at gcc dot gnu.org]

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

--- Comment #15 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Andrew Pinski <pinskia@gcc.gnu.org>:

https://gcc.gnu.org/g:8590dcd318151336261f8381e1a24caece9e2375

commit r15-3678-g8590dcd318151336261f8381e1a24caece9e2375
Author: Andrew Pinski <quic_apinski@quicinc.com>
Date:   Tue Sep 17 14:26:54 2024 -0700

    phiopt: Add some details dump to cselim

    While trying to debug PR 116747, I noticed there was no dump
    saying what was done. So this adds the debug dump and it helps
    debug what is going on in PR 116747 too.

    Bootstrapped and tested on x86_64-linux-gnu.

    gcc/ChangeLog:

            * tree-ssa-phiopt.cc (cond_if_else_store_replacement_1): Add debug
dump.

    Signed-off-by: Andrew Pinski <quic_apinski@quicinc.com>

[Bug tree-optimization/116747] [12/13/14/15 Regression] ICE on valid code at -O3 on x86_64-linux-gnu: Segmentation fault

[rguenth at gcc dot gnu.org]

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

--- Comment #16 from Richard Biener <rguenth at gcc dot gnu.org> ---
Btw, the "missing" write-after-write dependence is because the ref is outside
of  array bounds so the alias oracle computes a max_size for the access of zero
and thus no aliasing.  I guess thats OK (while unexpected but UB).

Note sinking doesn't really need to compute all-all dependences but computing
dependences with the refs we sink through would be enough, also noting that
we do (should) not re-order ref pairs we sink and thus dependences between
the ref pair refs should be OK.

So much to improve in this code ;)