[Bug tree-optimization/114084] New: ICE: SIGSEGV: infinite recursion in fold_build2_loc / fold_binary_loc with _BitInt(127)

[Bug tree-optimization/114084] New: ICE: SIGSEGV: infinite recursion in fold_build2_loc / fold_binary_loc with _BitInt(127)

[zsojka at seznam dot cz]

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

            Bug ID: 114084
           Summary: ICE: SIGSEGV: infinite recursion in fold_build2_loc /
                    fold_binary_loc with _BitInt(127)
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Keywords: ice-on-valid-code
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: zsojka at seznam dot cz
                CC: jakub at gcc dot gnu.org
  Target Milestone: ---
              Host: x86_64-pc-linux-gnu
            Target: x86_64-pc-linux-gnu

Created attachment 57518
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=57518&action=edit
reduced testcase

Compiler output:
$ x86_64-pc-linux-gnu-gcc testcase.c -wrapper gdb,-q,--args
Reading symbols from
/repo/gcc-trunk/binary-trunk-r14-9151-20240223113818-g22121546e03-checking-yes-rtl-df-extra-amd64/bin/../libexec/gcc/x86_64-pc-linux-gnu/14.0.1/cc1...
(gdb) r
Starting program:
/repo/gcc-trunk/binary-trunk-r14-9151-20240223113818-g22121546e03-checking-yes-rtl-df-extra-amd64/libexec/gcc/x86_64-pc-linux-gnu/14.0.1/cc1
-quiet -iprefix
/repo/gcc-trunk/binary-trunk-r14-9151-20240223113818-g22121546e03-checking-yes-rtl-df-extra-amd64/bin/../lib/gcc/x86_64-pc-linux-gnu/14.0.1/
testcase.c -quiet -dumpdir a- -dumpbase testcase.c -dumpbase-ext .c
-mtune=generic -march=x86-64 -o /tmp/ccRiFgDu.s
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib64/libthread_db.so.1".

Program received signal SIGSEGV, Segmentation fault.
wi::fits_to_tree_p<poly_int<1u, generic_wide_int<wide_int_ref_storage<false,
true> > > > (x=..., type=type@entry=0x7ffff75b15e8) at
/repo/gcc-trunk/gcc/tree.h:6620
6620        return known_eq (x, zext (x, TYPE_PRECISION (type)));
(gdb) bt
#0  wi::fits_to_tree_p<poly_int<1u,
generic_wide_int<wide_int_ref_storage<false, true> > > > (x=...,
type=type@entry=0x7ffff75b15e8) at /repo/gcc-trunk/gcc/tree.h:6620
#1  0x0000000001846c63 in force_fit_type (type=0x7ffff75b15e8, cst=...,
overflowable=1, overflowed=<optimized out>) at /repo/gcc-trunk/gcc/tree.cc:1563
#2  0x00000000010f2f3a in fold_convert_const_int_from_int (type=0x7ffff75b15e8,
arg1=0x7ffff75ad7c0) at /repo/gcc-trunk/gcc/fold-const.cc:2173
#3  fold_convert_const (code=<optimized out>, type=0x7ffff75b15e8,
arg1=0x7ffff75ad7c0) at /repo/gcc-trunk/gcc/fold-const.cc:2467
#4  0x0000000001109095 in fold_unary_loc (loc=2147483656, code=NOP_EXPR,
type=0x7ffff75b15e8, op0=0x7ffff75ad7c0) at
/repo/gcc-trunk/gcc/fold-const.cc:9489
#5  0x000000000110b80a in fold_build1_loc (loc=loc@entry=2147483656,
code=code@entry=NOP_EXPR, type=0x7ffff75b15e8, op0=0x7ffff75ad7c0) at
/repo/gcc-trunk/gcc/fold-const.cc:14110
#6  0x0000000001d76ec2 in generic_simplify_93 (loc=loc@entry=2147483656,
type=type@entry=0x7ffff75b1540, _p0=_p0@entry=0x7ffff656d900,
_p1=_p1@entry=0x7ffff75ad7c0, 
    captures=captures@entry=0x7ffffbfff670, bitop=bitop@entry=BIT_IOR_EXPR) at
generic-match-5.cc:561
#7  0x0000000001da2de5 in generic_simplify_BIT_IOR_EXPR (loc=2147483656,
code=<optimized out>, type=0x7ffff75b1540, _p0=0x7ffff656d900,
_p1=0x7ffff75ad7c0) at generic-match-6.cc:5599
#8  0x0000000001100576 in fold_binary_loc (loc=2147483656, code=BIT_IOR_EXPR,
type=0x7ffff75b1540, op0=0x7ffff656d900, op1=0x7ffff75ad7c0) at
/repo/gcc-trunk/gcc/fold-const.cc:11292
#9  0x000000000110810b in fold_build2_loc (loc=2147483656, code=BIT_IOR_EXPR,
type=0x7ffff75b1540, op0=0x7ffff656d900, op1=0x7ffff75ad7c0) at
/repo/gcc-trunk/gcc/fold-const.cc:14156
#10 0x000000000110157d in fold_binary_loc (loc=<optimized out>,
code=BIT_IOR_EXPR, type=0x7ffff75b1540, op0=<optimized out>, op1=<optimized
out>) at /repo/gcc-trunk/gcc/fold-const.cc:11836
#11 0x000000000110810b in fold_build2_loc (loc=2147483656, code=BIT_IOR_EXPR,
type=0x7ffff75b1540, op0=0x7ffff75afc58, op1=0x7ffff656d8c0) at
/repo/gcc-trunk/gcc/fold-const.cc:14156
#12 0x0000000001101626 in fold_binary_loc (loc=<optimized out>, code=<optimized
out>, type=0x7ffff75b1540, op0=<optimized out>, op1=<optimized out>)
    at /repo/gcc-trunk/gcc/fold-const.cc:11868
#13 0x000000000110810b in fold_build2_loc (loc=2147483656, code=BIT_IOR_EXPR,
type=0x7ffff75b1540, op0=0x7ffff75afc58, op1=0x7ffff656d840) at
/repo/gcc-trunk/gcc/fold-const.cc:14156
#14 0x0000000001101626 in fold_binary_loc (loc=<optimized out>, code=<optimized
out>, type=0x7ffff75b1540, op0=<optimized out>, op1=<optimized out>)
    at /repo/gcc-trunk/gcc/fold-const.cc:11868
...


$ x86_64-pc-linux-gnu-gcc -v
Using built-in specs.
COLLECT_GCC=/repo/gcc-trunk/binary-latest-amd64/bin/x86_64-pc-linux-gnu-gcc
COLLECT_LTO_WRAPPER=/repo/gcc-trunk/binary-trunk-r14-9151-20240223113818-g22121546e03-checking-yes-rtl-df-extra-amd64/bin/../libexec/gcc/x86_64-pc-linux-gnu/14.0.1/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: /repo/gcc-trunk//configure --enable-languages=c,c++
--enable-valgrind-annotations --disable-nls --enable-checking=yes,rtl,df,extra
--with-cloog --with-ppl --with-isl --build=x86_64-pc-linux-gnu
--host=x86_64-pc-linux-gnu --target=x86_64-pc-linux-gnu
--with-ld=/usr/bin/x86_64-pc-linux-gnu-ld
--with-as=/usr/bin/x86_64-pc-linux-gnu-as --disable-libstdcxx-pch
--prefix=/repo/gcc-trunk//binary-trunk-r14-9151-20240223113818-g22121546e03-checking-yes-rtl-df-extra-amd64
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 14.0.1 20240223 (experimental) (GCC)

[Bug middle-end/114084] ICE: SIGSEGV: infinite recursion in fold_build2_loc / fold_binary_loc with _BitInt(127)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2024-02-24

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed, here is a testcase which should be generic for even 16bit int
targets.

```
typedef unsigned _BitInt(sizeof(int)*8-1) ub63;
ub63 ub63_0, ub63_1;

void
foo (void)
{
   ub63_1 = (ub63)
   ((ub63_0 |  (-1u>>1) ) >> 1 | (ub63_0 | 5) <<  4);
}
```

Note I tried to reproduce this using bitfields but that works. Also note the
cast is important here ...

[Bug middle-end/114084] ICE: SIGSEGV: infinite recursion in fold_build2_loc / fold_binary_loc with _BitInt(127)

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Here is another testcase, the only use of _BitInt is in the cast, everything
else is a bitfield:
```
struct a
{
  unsigned t:(sizeof(int)*8-1);
};

typedef unsigned _BitInt(sizeof(int)*8-1) ub31;
struct a ub63_0;
struct a ub63_1;

void
foo (void)
{
   ub63_1.t = (ub31)
   ((ub63_0.t |  (-1u>>1) ) >> 1 | (ub63_0.t | 1u) <<  4);
}
```

I still can't figure out why the cast is needed though.

[Bug middle-end/114084] ICE: SIGSEGV: infinite recursion in fold_build2_loc / fold_binary_loc with _BitInt(127)

[jakub at gcc dot gnu.org]

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

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Bet the associate code is really unprepared to have unfolded trees around,
which hasn't been the case before delayed folding has been introduced to C and
C++ FEs.
Unfortunately it isn't complete, because e.g. convert_to_integer_1 -> do_narrow
-> fold_build2_loc happily folds.

Anyway, quick fix could be not trying to reassociate TREE_CONSTANT parts:
--- gcc/fold-const.cc.jj        2024-01-26 00:07:58.000000000 +0100
+++ gcc/fold-const.cc   2024-02-24 09:38:40.150808529 +0100
@@ -908,6 +908,8 @@ split_tree (tree in, tree type, enum tre
   if (TREE_CODE (in) == INTEGER_CST || TREE_CODE (in) == REAL_CST
       || TREE_CODE (in) == FIXED_CST)
     *litp = in;
+  else if (TREE_CONSTANT (in))
+    *conp = in;
   else if (TREE_CODE (in) == code
           || ((! FLOAT_TYPE_P (TREE_TYPE (in)) || flag_associative_math)
               && ! SAT_FIXED_POINT_TYPE_P (TREE_TYPE (in))
@@ -956,8 +958,6 @@ split_tree (tree in, tree type, enum tre
       if (neg_var_p && var)
        *minus_varp = var, var = 0;
     }
-  else if (TREE_CONSTANT (in))
-    *conp = in;
   else if (TREE_CODE (in) == BIT_NOT_EXPR
           && code == PLUS_EXPR)
     {

So, the problem happens on
typedef unsigned _BitInt (__SIZEOF_INT__ * __CHAR_BIT__ - 1) T;
T a, b;

void
foo (void)
{
  b = (T) ((a | (-1U >> 1)) >> 1 | (a | 5) << 4);
}
when fold_binary_loc is called on (unsigned _BitInt(31)) a << 4 | 80 and
(unsigned _BitInt(31)) (2147483647 >> 1), but the important part is that
the op0 has the unsigned _BitInt(31) type, while op1 is NOP_EXPR to that type
from
RSHIFT_EXPR done on T type (the typedef).
Soon BIT_IOR_EXPR folding is called on
(unsigned _BitInt(31)) a << 4 and 2147483647 >> 1 | 80 where the latter is all
in T type (fold_binary_loc does STRIP_NOPS).  Because split_tree prefers same
code over TREE_CONSTANT, this splits it into the LSHIFT_EXPR var0, RSHIFT_EXPR
con1 (because it is TREE_CONSTANT) and the T type 80 literal in lit1,
everything else is NULL.  As there are 3 objects, it reassociates.  We first
associate_tree the 0 vs. 1 cases, but that just moves the *1 into *0 because
their counterparts are NULL.
Both the RSHIFT_EXPR and INTEGER_CST 80 have T type but atype is the
build_bitint_type
non-typedef type, so
11835                 /* Eliminate lit0 and minus_lit0 to con0 and minus_con0.
*/
11836                 con0 = associate_trees (loc, con0, lit0, code, atype);
returns NOP_EXPR of the RSHIFT_EXPR | INTEGER_CST.
And then we associate_trees the LSHIFT_EXPR with this result and so it recurses
infinitely.

Perhaps my above patch is an improvement, if we know some subtree is
TREE_CONSTANT, all we need is just wait for it to be constant folded (not sure
it would always do e.g. because of division by zero or similar) trying to
reassociate its parts with other expressions might just split the constants to
other spots instead of keeping it together.

[Bug middle-end/114084] ICE: SIGSEGV: infinite recursion in fold_build2_loc / fold_binary_loc with _BitInt(127)

[jakub at gcc dot gnu.org]

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

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Though, I must say not really sure why this wouldn't recurse infinitely even
without the casts.

[Bug middle-end/114084] ICE: SIGSEGV: infinite recursion in fold_build2_loc / fold_binary_loc with _BitInt(127)

[jakub at gcc dot gnu.org]

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

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Or perhaps the
          if (ok
              && ((var0 != 0) + (var1 != 0)
                  + (minus_var0 != 0) + (minus_var1 != 0)
                  + (con0 != 0) + (con1 != 0)
                  + (minus_con0 != 0) + (minus_con1 != 0)
                  + (lit0 != 0) + (lit1 != 0)
                  + (minus_lit0 != 0) + (minus_lit1 != 0)) > 2)
condition should be amended to avoid the reassociation in cases where clearly
nothing good can come out of that.  Which is if the association actually
doesn't reshuffle anything.  (var0 == 0) || (var1 == 0) && (and similarly for
the other 5 pairs) and
(ignoring the minus_* stuff that would need more thoughts on it)
(con0 != 0 && lit0 != 0) || (con1 != 0 && lit1 != 0),
then it reassociates to the original stuff in op0 and original stuff in op1,
no change.  But how the minus_* plays together with this is harder.
Perhaps if lazy we could have a bool var whether there has been any association
between subtrees from original op0 and op1, initially set to false and set if
we associate_trees between something that comes from op0 and op1, and only do
the final
associate_trees if that is the case, because if not, it should be folding of
the individual suboperands, not reassociation.

[Bug middle-end/114084] ICE: SIGSEGV: infinite recursion in fold_build2_loc / fold_binary_loc with _BitInt(127)

[jakub at gcc dot gnu.org]

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

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
As in the following patch, which is supposed to track the origin of the 6
something0
variables in bitmasks, bit 1 means it comes (partly) from op0, bit 2 means it
comes (partly) from op1.
--- gcc/fold-const.cc.jj        2024-02-24 09:49:09.098815803 +0100
+++ gcc/fold-const.cc   2024-02-24 11:01:34.266513041 +0100
@@ -11779,6 +11779,15 @@ fold_binary_loc (location_t loc, enum tr
                  + (lit0 != 0) + (lit1 != 0)
                  + (minus_lit0 != 0) + (minus_lit1 != 0)) > 2)
            {
+             int var0_origin = (var0 != 0) + 2 * (var1 != 0);
+             int minus_var0_origin
+               = (minus_var0 != 0) + 2 * (minus_var1 != 0);
+             int con0_origin = (con0 != 0) + 2 * (con1 != 0);
+             int minus_con0_origin
+               = (minus_con0 != 0) + 2 * (minus_con1 != 0);
+             int lit0_origin = (lit0 != 0) + 2 * (lit1 != 0);
+             int minus_lit0_origin
+               = (minus_lit0 != 0) + 2 * (minus_lit1 != 0);
              var0 = associate_trees (loc, var0, var1, code, atype);
              minus_var0 = associate_trees (loc, minus_var0, minus_var1,
                                            code, atype);
@@ -11791,15 +11800,19 @@ fold_binary_loc (location_t loc, enum tr

              if (minus_var0 && var0)
                {
+                 var0_origin |= minus_var0_origin;
                  var0 = associate_trees (loc, var0, minus_var0,
                                          MINUS_EXPR, atype);
                  minus_var0 = 0;
+                 minus_var0_origin = 0;
                }
              if (minus_con0 && con0)
                {
+                 con0_origin |= minus_con0_origin;
                  con0 = associate_trees (loc, con0, minus_con0,
                                          MINUS_EXPR, atype);
                  minus_con0 = 0;
+                 minus_con0_origin = 0;
                }

              /* Preserve the MINUS_EXPR if the negative part of the literal is
@@ -11815,15 +11828,19 @@ fold_binary_loc (location_t loc, enum tr
                      /* But avoid ending up with only negated parts.  */
                      && (var0 || con0))
                    {
+                     minus_lit0_origin |= lit0_origin;
                      minus_lit0 = associate_trees (loc, minus_lit0, lit0,
                                                    MINUS_EXPR, atype);
                      lit0 = 0;
+                     lit0_origin = 0;
                    }
                  else
                    {
+                     lit0_origin |= minus_lit0_origin;
                      lit0 = associate_trees (loc, lit0, minus_lit0,
                                              MINUS_EXPR, atype);
                      minus_lit0 = 0;
+                     minus_lit0_origin = 0;
                    }
                }

@@ -11833,37 +11850,51 @@ fold_binary_loc (location_t loc, enum tr
                return NULL_TREE;

              /* Eliminate lit0 and minus_lit0 to con0 and minus_con0. */
+             con0_origin |= lit0_origin;
              con0 = associate_trees (loc, con0, lit0, code, atype);
-             lit0 = 0;
+             minus_con0_origin |= minus_lit0_origin;
              minus_con0 = associate_trees (loc, minus_con0, minus_lit0,
                                            code, atype);
-             minus_lit0 = 0;

              /* Eliminate minus_con0.  */
              if (minus_con0)
                {
                  if (con0)
-                   con0 = associate_trees (loc, con0, minus_con0,
-                                           MINUS_EXPR, atype);
+                   {
+                     con0_origin |= minus_con0_origin;
+                     con0 = associate_trees (loc, con0, minus_con0,
+                                             MINUS_EXPR, atype);
+                   }
                  else if (var0)
-                   var0 = associate_trees (loc, var0, minus_con0,
-                                           MINUS_EXPR, atype);
+                   {
+                     var0_origin |= minus_con0_origin;
+                     var0 = associate_trees (loc, var0, minus_con0,
+                                             MINUS_EXPR, atype);
+                   }
                  else
                    gcc_unreachable ();
-                 minus_con0 = 0;
                }

              /* Eliminate minus_var0.  */
              if (minus_var0)
                {
                  if (con0)
-                   con0 = associate_trees (loc, con0, minus_var0,
-                                           MINUS_EXPR, atype);
+                   {
+                     con0_origin |= minus_var0_origin;
+                     con0 = associate_trees (loc, con0, minus_var0,
+                                             MINUS_EXPR, atype);
+                   }
                  else
                    gcc_unreachable ();
-                 minus_var0 = 0;
                }

+             /* Reassociate only if there has been any actual association
+                between subtrees from op0 and subtrees from op1 in at
+                least one of the operands, otherwise we risk infinite
+                recursion.  See PR114084.  */
+             if (var0_origin != 3 && con0_origin != 3)
+               return NULL_TREE;
+
              return
                fold_convert_loc (loc, type, associate_trees (loc, var0, con0,
                                                              code, atype));

[Bug middle-end/114084] ICE: SIGSEGV: infinite recursion in fold_build2_loc / fold_binary_loc with _BitInt(127)

[cvs-commit at gcc dot gnu.org]

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

--- Comment #7 from GCC 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:f9d2a95be5680e04f53141c2675798b06d23f409

commit r14-9174-gf9d2a95be5680e04f53141c2675798b06d23f409
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Mon Feb 26 10:07:39 2024 +0100

    fold-const: Avoid infinite recursion in +-*&|^minmax reassociation
[PR114084]

    In the following testcase we infinitely recurse during BIT_IOR_EXPR
    reassociation.
    One operand is (unsigned _BitInt(31)) a << 4 and another operand
    2147483647 >> 1 | 80 where both the right shift and the | 80
    trees have TREE_CONSTANT set, but weren't folded because of delayed
    folding, where some foldings are apparently done even in that case
    unfortunately.
    Now, the fold_binary_loc reassocation code splits both operands into
    variable part, minus variable part, constant part, minus constant part,
    literal part and minus literal parts, to prevent infinite recursion
    punts if there are just 2 parts altogether from the 2 operands and then
goes
    on with reassociation, merges first the corresponding parts from both
    operands and then some further merges.
    The problem with the above expressions is that we get 3 different objects,
    var0 (the left shift), con1 (the right shift) and lit1 (80), so the
infinite
    recursion prevention doesn't trigger, and we eventually merge con1 with
    lit1, which effectively reconstructs the original op1 and then associate
    that with var0 which is original op0, and associate_trees for that case
    calls fold_binary.  There are some casts involved there too (the T typedef
    type and the underlying _BitInt type which are stripped with STRIP_NOPS).

    The following patch attempts to prevent this infinite recursion by tracking
    the origin (if certain var comes from nothing - 0, op0 - 1, op1 - 2 or both
- 3)
    and propagates it through all the associate_tree calls which merge the
vars.
    If near the end we'd try to merge what comes solely from op0 with what
comes
    solely from op1 (or vice versa), the patch punts, because then it isn't any
    kind of reassociation between the two operands, if anything it should be
    handled when folding the suboperands.

    2024-02-26  Jakub Jelinek  <jakub@redhat.com>

            PR middle-end/114084
            * fold-const.cc (fold_binary_loc): Avoid the final associate_trees
            if all subtrees of var0 come from one of the op0 or op1 operands
            and all subtrees of con0 come from the other one.  Don't clear
            variables which are never used afterwards.

            * gcc.dg/bitint-94.c: New test.

[Bug middle-end/114084] ICE: SIGSEGV: infinite recursion in fold_build2_loc / fold_binary_loc with _BitInt(127)

[jakub at gcc dot gnu.org]

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

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

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

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