[Bug middle-end/112733] New: [14 Regression] ICE: Segmentation fault in wide-int.cc during GIMPLE pass: sccp

[Bug middle-end/112733] New: [14 Regression] ICE: Segmentation fault in wide-int.cc during GIMPLE pass: sccp

[patrick at rivosinc dot com]

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

            Bug ID: 112733
           Summary: [14 Regression] ICE: Segmentation fault in wide-int.cc
                    during GIMPLE pass: sccp
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
          Assignee: unassigned at gcc dot gnu.org
          Reporter: patrick at rivosinc dot com
  Target Milestone: ---

Reconfirmed using r14-5889-gc9d691a7daa. This has not been bisected.

Using godbolt to check - this is broken on trunk x86, arm, riscv.
Regression from 13.2 where this compiles on x86, arm, riscv.

> cat red.c
char a, c;
short b;
void d() {
  signed char *e = &a;
  c = 0 != d;
  *e &= c;
  for (; b; --b)
    *e &= 128;
}

> /scratch/tc-testing/tc-nov-27-trunk/build-rv64gcv/bin/riscv64-unknown-linux-gnu-gcc red.c -S -O2 -freport-bug
during GIMPLE pass: sccp
red.c: In function 'd':
red.c:3:6: internal compiler error: Segmentation fault
    3 | void d() {
      |      ^
0x12884a3 crash_signal
        ../../../gcc/gcc/toplev.cc:316
0x7fb10de4251f ???
        ./signal/../sysdeps/unix/sysv/linux/x86_64/libc_sigaction.c:0
0x163ac0e wi_pack
        ../../../gcc/gcc/wide-int.cc:1303
0x1642d17 wi::divmod_internal(long*, unsigned int*, long*, long const*,
unsigned int, unsigned int, long const*, unsigned int, unsigned int, signop,
wi::overflow_type*)
        ../../../gcc/gcc/wide-int.cc:1988
0xecaf5c wi::binary_traits<generic_wide_int<wi::extended_tree<131072> >,
generic_wide_int<wi::extended_tree<131072> >,
wi::int_traits<generic_wide_int<wi::extended_tree<131072> > >::precision_type,
wi::int_traits<generic_wide_int<wi::extended_tree<131072> >
>::precision_type>::result_type
wi::mod_trunc<generic_wide_int<wi::extended_tree<131072> >,
generic_wide_int<wi::extended_tree<131072> >
>(generic_wide_int<wi::extended_tree<131072> > const&,
generic_wide_int<wi::extended_tree<131072> > const&, signop,
wi::overflow_type*)
        ../../../gcc/gcc/wide-int.h:3382
0xeac199 bool wi::multiple_of_p<generic_wide_int<wi::extended_tree<131072> >,
generic_wide_int<wi::extended_tree<131072> >
>(generic_wide_int<wi::extended_tree<131072> > const&,
generic_wide_int<wi::extended_tree<131072> > const&, signop)
        ../../../gcc/gcc/wide-int.h:3549
0xeac199 multiple_of_p(tree_node*, tree_node const*, tree_node const*, bool)
        ../../../gcc/gcc/fold-const.cc:14554
riscv64-unknown-linux-gnu-gcc: internal compiler error: Segmentation fault
signal terminated program cc1
Please submit a full bug report, with preprocessed source.
See <https://gcc.gnu.org/bugs/> for instructions.


-freport bug does not seem to be working for me so here's the -v output:

> /scratch/tc-testing/tc-nov-27-trunk/build-rv64gcv/bin/riscv64-unknown-linux-gnu-gcc -v
Using built-in specs.
COLLECT_GCC=/scratch/tc-testing/tc-nov-27-trunk/build-rv64gcv/bin/riscv64-unknown-linux-gnu-gcc
COLLECT_LTO_WRAPPER=/scratch/tc-testing/tc-nov-27-trunk/build-rv64gcv/libexec/gcc/riscv64-unknown-linux-gnu/14.0.0/lto-wrapper
Target: riscv64-unknown-linux-gnu
Configured with:
/scratch/tc-testing/tc-nov-27-trunk/build-rv64gcv/../gcc/configure
--target=riscv64-unknown-linux-gnu
--prefix=/scratch/tc-testing/tc-nov-27-trunk/build-rv64gcv
--with-sysroot=/scratch/tc-testing/tc-nov-27-trunk/build-rv64gcv/sysroot
--with-pkgversion=gc9d691a7daa --with-system-zlib --enable-shared --enable-tls
--enable-languages=c,c++,fortran --disable-libmudflap --disable-libssp
--disable-libquadmath --disable-libsanitizer --disable-nls --disable-bootstrap
--src=../../gcc --enable-multilib --with-abi=lp64d --with-arch=rv64imafdc
--with-tune=rocket --with-isa-spec=20191213 'CFLAGS_FOR_TARGET=-O2   
-mcmodel=medlow' 'CXXFLAGS_FOR_TARGET=-O2    -mcmodel=medlow'
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 14.0.0 20231127 (experimental) (gc9d691a7daa)

[Bug middle-end/112733] [14 Regression] ICE: Segmentation fault in wide-int.cc during GIMPLE pass: sccp

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |14.0
           Keywords|                            |ice-on-valid-code
                 CC|                            |pinskia at gcc dot gnu.org

[Bug middle-end/112733] [14 Regression] ICE: Segmentation fault in wide-int.cc during GIMPLE pass: sccp

[pinskia at gcc dot gnu.org]

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

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
multiple_of_p is one big source of bugs ...

[Bug middle-end/112733] [14 Regression] ICE: Segmentation fault in wide-int.cc during GIMPLE pass: sccp

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I linked PR 100499, not that it caused the issue here but talks about the
issues in multiple_of_p .

[Bug middle-end/112733] [14 Regression] ICE: Segmentation fault in wide-int.cc during GIMPLE pass: sccp

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2023-11-27
           Keywords|                            |needs-bisection

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

[Bug middle-end/112733] [14 Regression] ICE: Segmentation fault in wide-int.cc during GIMPLE pass: sccp

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Hmm, stack corruption.  Last good frame:

#0  wi::divmod_internal (quotient=0x0, remainder_len=0x7fffffffc8fc, 
    remainder=0x7fffffffc990, dividend_val=0x7ffff71c4e68, dividend_len=1, 
    dividend_prec=131072, divisor_val=0x7ffff702d010, divisor_len=1, 
    divisor_prec=131072, sgn=UNSIGNED, oflow=0x0)
    at /space/rguenther/src/gcc/gcc/wide-int.cc:1800
#1  0x00000000011ec195 in
wi::mod_trunc<generic_wide_int<wi::extended_tree<131072> >,
generic_wide_int<wi::extended_tree<131072> > > (x=..., y=..., 
    sgn=UNSIGNED, overflow=0x0) at /space/rguenther/src/gcc/gcc/wide-int.h:3382
#2  0x00000000011e90ee in
wi::multiple_of_p<generic_wide_int<wi::extended_tree<131072> >,
generic_wide_int<wi::extended_tree<131072> > > (x=..., y=..., 
    sgn=UNSIGNED) at /space/rguenther/src/gcc/gcc/wide-int.h:3549
#3  0x00000000011d564d in multiple_of_p (
    type=<integer_type 0x7ffff702b2a0 signed char>, 
    top=<ssa_name 0x7ffff7016f30 2>, bottom=<integer_cst 0x7ffff702d000>, 
    nowrap=true) at /space/rguenther/src/gcc/gcc/fold-const.cc:14554
#4  0x00000000011caa58 in fold_binary_loc (loc=0, code=BIT_AND_EXPR, 
    type=<integer_type 0x7ffff702b2a0 signed char>, 
    op0=<ssa_name 0x7ffff7016f30 2>, op1=<integer_cst 0x7ffff702d000>)
    at /space/rguenther/src/gcc/gcc/fold-const.cc:12112
#5  0x00000000011d4356 in fold_build2_loc (loc=0, code=BIT_AND_EXPR, 
    type=<integer_type 0x7ffff702b2a0 signed char>, 
    op0=<ssa_name 0x7ffff7016f30 2>, op1=<integer_cst 0x7ffff702d000>)
    at /space/rguenther/src/gcc/gcc/fold-const.cc:14128
#6  0x0000000001848eba in analyze_and_compute_bitop_with_inv_effect (
    loop=0x7ffff700e4b0, phidef=<ssa_name 0x7ffff71e5000 4>, 
    niter=<plus_expr 0x7ffff71f2230>)
    at /space/rguenther/src/gcc/gcc/tree-scalar-evolution.cc:3719

and we end up with

(gdb) p divisor_blocks_needed
$36 = 4096

  if (remainder)
    {
      *remainder_len = wi_pack (remainder, b_remainder, n, dividend_prec);

(gdb) p n
$50 = 4096
(gdb) p dividend_prec
$51 = 128
(gdb) p remainder
$52 = (long *) 0x7fffffffc990
(gdb) p b_remainder
$53 = (unsigned int *) 0x7ffffffec0f0

and that wi_pack faults.

[Bug middle-end/112733] [14 Regression] ICE: Segmentation fault in wide-int.cc during GIMPLE pass: sccp

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|needs-bisection             |

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r14-5428-gfd1596f9962569afff6c9298a7c79686c6950bef
But most likely my fault with the wide-int.* changes.

[Bug middle-end/112733] [14 Regression] ICE: Segmentation fault in wide-int.cc during GIMPLE pass: sccp

[jakub at gcc dot gnu.org]

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

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
One thing is obviously we shouldn't crash on it and will debug that.
But, what multiple_of_p does (or its callers) is weird:
14552             /* Check for special cases to see if top is defined as
multiple
14553                of bottom:
14554   
14555                  top = (X & ~(bottom - 1) ; bottom is power of 2
14556   
14557                or
14558   
14559                  Y = X % bottom
14560                  top = X - Y.  */
14561             if (code == BIT_AND_EXPR
14562                 && (op2 = gimple_assign_rhs2 (stmt)) != NULL_TREE
14563                 && TREE_CODE (op2) == INTEGER_CST
14564                 && integer_pow2p (bottom)
14565                 && wi::multiple_of_p (wi::to_widest (op2),
14566                                       wi::to_widest (bottom), UNSIGNED))
14567               return true;
It uses UNSIGNED, but both op2 and bottom are signed:
(gdb) p debug_tree (op2)
 <integer_cst 0x7fffea2e5e70 type <integer_type 0x7fffea14c2a0 signed char>
constant 1>
$17 = void
(gdb) p debug_tree (bottom)
 <integer_cst 0x7fffea14e000 type <integer_type 0x7fffea14c2a0 signed char>
constant -128>
so it is in the end multiple_of_p 1,
0xffffff................fffffffffffffffffffffffff80 where the latter has 131072
bits precision.
That definitely doesn't have anything to do with what the source does (and
didn't even when the precision was just 576 bits before).

[Bug middle-end/112733] [14 Regression] ICE: Segmentation fault in wide-int.cc during GIMPLE pass: sccp

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
On the fold-const.cc side, we IMHO should either do:
--- gcc/fold-const.cc.jj        2023-11-28 08:46:28.345803059 +0100
+++ gcc/fold-const.cc   2023-11-28 15:37:28.252327265 +0100
@@ -14563,7 +14563,7 @@ multiple_of_p (tree type, const_tree top
              && TREE_CODE (op2) == INTEGER_CST
              && integer_pow2p (bottom)
              && wi::multiple_of_p (wi::to_widest (op2),
-                                   wi::to_widest (bottom), UNSIGNED))
+                                   wi::to_widest (bottom), SIGNED))
            return true;

          op1 = gimple_assign_rhs1 (stmt);
because widest_ints are always signed by definition, or
--- gcc/fold-const.cc.jj        2023-11-28 08:46:28.345803059 +0100
+++ gcc/fold-const.cc   2023-11-28 15:43:46.730985893 +0100
@@ -14562,8 +14562,11 @@ multiple_of_p (tree type, const_tree top
              && (op2 = gimple_assign_rhs2 (stmt)) != NULL_TREE
              && TREE_CODE (op2) == INTEGER_CST
              && integer_pow2p (bottom)
-             && wi::multiple_of_p (wi::to_widest (op2),
-                                   wi::to_widest (bottom), UNSIGNED))
+             && wi::multiple_of_p (widest_int::from (wi::to_wide (op2),
+                                                     UNSIGNED),
+                                   widest_int::from (wi::to_wide (bottom),
+                                                     UNSIGNED),
+                                   UNSIGNED))
            return true;

          op1 = gimple_assign_rhs1 (stmt);
to use widest_int but zero extend there everything, or
--- gcc/fold-const.cc.jj        2023-11-28 08:46:28.345803059 +0100
+++ gcc/fold-const.cc   2023-11-28 15:45:35.867445679 +0100
@@ -14562,8 +14562,8 @@ multiple_of_p (tree type, const_tree top
              && (op2 = gimple_assign_rhs2 (stmt)) != NULL_TREE
              && TREE_CODE (op2) == INTEGER_CST
              && integer_pow2p (bottom)
-             && wi::multiple_of_p (wi::to_widest (op2),
-                                   wi::to_widest (bottom), UNSIGNED))
+             && wi::multiple_of_p (wi::to_wide (op2), wi::to_wide (bottom),
+                                   TYPE_SIGN (TREE_TYPE (bottom))))
            return true;

          op1 = gimple_assign_rhs1 (stmt);
The last one has the disadvantage that it would ICE if op2 and bottom don't
have same precision (but I'd think it would be caller's screw up if that was
the case).

Given
      return wi::multiple_of_p (wi::to_widest (top), wi::to_widest (bottom),
                                SIGNED);
a few lines earlier in the same patch, I think my preference is the first
patch.
Thoughts on this?

[Bug middle-end/112733] [14 Regression] ICE: Segmentation fault in wide-int.cc during GIMPLE pass: sccp

[jakub at gcc dot gnu.org]

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

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
As for the actual crash, I have again multiple possible fixes:
--- gcc/wide-int.cc.jj  2023-10-16 14:24:46.360204472 +0200
+++ gcc/wide-int.cc     2023-11-28 16:33:35.737394223 +0100
@@ -1297,6 +1297,8 @@ wi_pack (HOST_WIDE_INT *result,
   unsigned int j = 0;
   unsigned int blocks_needed = BLOCKS_NEEDED (precision);

+  if (in_len > blocks_needed * 2)
+    in_len = blocks_needed * 2;
   while (i + 1 < in_len)
     {
       result[j++] = ((unsigned HOST_WIDE_INT) input[i]
Or another option is ensure that in_len is never larger than blocks_needed * 2.
The problem with the wide-int.cc wi_pack calls for remainder is that
the in_len argument in that case is n (which is:
  n = divisor_blocks_needed;
  while (n > 1 && b_divisor[n - 1] == 0)
    n--;
i.e. at most 2 * BLOCKS_NEEDED (divisor_prec), but the last
argument is dividend_prec rather than divisor_prec.
In reality, I think the remainder is bound by both minimum precision
of dividend and divisor, because it can't be in absolute value larger
than the divisor and can't be in absolute value larger than dividend.
--- gcc/wide-int.h.jj   2023-10-14 11:08:20.790471175 +0200
+++ gcc/wide-int.h      2023-11-28 16:44:26.576265870 +0100
@@ -3179,6 +3179,10 @@ wi::div_floor (const T1 &x, const T2 &y,
       else
        est_len = xi.len + 1;
       quotient_val = quotient.write_val (est_len);
+      if (sgn == UNSIGNED && yi.val[yi.len - 1] < 0)
+       est_len = CEIL (precision, HOST_BITS_PER_WIDE_INT) + 1;
+      else
+       est_len = yi.len + 1;
       remainder_val = remainder.write_val (est_len);
     }
   quotient.set_len (divmod_internal (quotient_val,
@@ -3231,6 +3235,10 @@ wi::div_ceil (const T1 &x, const T2 &y,
       else
        est_len = xi.len + 1;
       quotient_val = quotient.write_val (est_len);
+      if (sgn == UNSIGNED && yi.val[yi.len - 1] < 0)
+       est_len = CEIL (precision, HOST_BITS_PER_WIDE_INT) + 1;
+      else
+       est_len = yi.len + 1;
       remainder_val = remainder.write_val (est_len);
     }
   quotient.set_len (divmod_internal (quotient_val,
@@ -3274,6 +3282,10 @@ wi::div_round (const T1 &x, const T2 &y,
       else
        est_len = xi.len + 1;
       quotient_val = quotient.write_val (est_len);
+      if (sgn == UNSIGNED && yi.val[yi.len - 1] < 0)
+       est_len = CEIL (precision, HOST_BITS_PER_WIDE_INT) + 1;
+      else
+       est_len = yi.len + 1;
       remainder_val = remainder.write_val (est_len);
     }
   quotient.set_len (divmod_internal (quotient_val,
@@ -3327,6 +3339,10 @@ wi::divmod_trunc (const T1 &x, const T2
       else
        est_len = xi.len + 1;
       quotient_val = quotient.write_val (est_len);
+      if (sgn == UNSIGNED && yi.val[yi.len - 1] < 0)
+       est_len = CEIL (precision, HOST_BITS_PER_WIDE_INT) + 1;
+      else
+       est_len = yi.len + 1;
       remainder_val = remainder.write_val (est_len);
     }
   quotient.set_len (divmod_internal (quotient_val,
@@ -3375,10 +3391,10 @@ wi::mod_trunc (const T1 &x, const T2 &y,
   unsigned int remainder_len;
   if (remainder.needs_write_val_arg)
     remainder_val = remainder.write_val ((sgn == UNSIGNED
-                                         && xi.val[xi.len - 1] < 0)
+                                         && yi.val[yi.len - 1] < 0)
                                         ? CEIL (precision,
                                                 HOST_BITS_PER_WIDE_INT) + 1
-                                        : xi.len + 1);
+                                        : yi.len + 1);
   divmod_internal (0, &remainder_len, remainder_val,
                   xi.val, xi.len, precision,
                   yi.val, yi.len, yi.precision, sgn, overflow);
@@ -3427,6 +3443,10 @@ wi::mod_floor (const T1 &x, const T2 &y,
       else
        est_len = xi.len + 1;
       quotient_val = quotient.write_val (est_len);
+      if (sgn == UNSIGNED && yi.val[yi.len - 1] < 0)
+       est_len = CEIL (precision, HOST_BITS_PER_WIDE_INT) + 1;
+      else
+       est_len = yi.len + 1;
       remainder_val = remainder.write_val (est_len);
     }
   quotient.set_len (divmod_internal (quotient_val,
@@ -3473,6 +3493,10 @@ wi::mod_ceil (const T1 &x, const T2 &y,
       else
        est_len = xi.len + 1;
       quotient_val = quotient.write_val (est_len);
+      if (sgn == UNSIGNED && yi.val[yi.len - 1] < 0)
+       est_len = CEIL (precision, HOST_BITS_PER_WIDE_INT) + 1;
+      else
+       est_len = yi.len + 1;
       remainder_val = remainder.write_val (est_len);
     }
   quotient.set_len (divmod_internal (quotient_val,
@@ -3509,6 +3533,10 @@ wi::mod_round (const T1 &x, const T2 &y,
       else
        est_len = xi.len + 1;
       quotient_val = quotient.write_val (est_len);
+      if (sgn == UNSIGNED && yi.val[yi.len - 1] < 0)
+       est_len = CEIL (precision, HOST_BITS_PER_WIDE_INT) + 1;
+      else
+       est_len = yi.len + 1;
       remainder_val = remainder.write_val (est_len);
     }
   quotient.set_len (divmod_internal (quotient_val,
--- gcc/wide-int.cc.jj  2023-10-16 14:24:46.360204472 +0200
+++ gcc/wide-int.cc     2023-11-28 16:36:09.227244087 +0100
@@ -1985,11 +1985,11 @@ wi::divmod_internal (HOST_WIDE_INT *quot

   if (remainder)
     {
-      *remainder_len = wi_pack (remainder, b_remainder, n, dividend_prec);
+      *remainder_len = wi_pack (remainder, b_remainder, n, divisor_prec);
       /* The remainder is always the same sign as the dividend.  */
       if (dividend_neg)
        *remainder_len = wi::sub_large (remainder, zeros, 1, remainder,
-                                       *remainder_len, dividend_prec,
+                                       *remainder_len, divisor_prec,
                                        UNSIGNED, 0);
     }

The advantage of the first patch is that it doesn't increase the code needed
to be emitted in widest_int wi::div_{floor,ceil,round} and wi::divmod_trunc,
wi::mod_{floor,ceil,round}, at the expense of one comparison in wide-int.cc
(done for all large multiplications, divisions, modulo).

[Bug middle-end/112733] [14 Regression] ICE: Segmentation fault in wide-int.cc during GIMPLE pass: sccp

[jakub at gcc dot gnu.org]

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

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Actually, maybe better variant of the first fix in the above comment would be:
--- gcc/wide-int.cc.jj  2023-11-28 16:56:50.000000000 +0100
+++ gcc/wide-int.cc     2023-11-28 16:58:02.268776755 +0100
@@ -1985,6 +1985,8 @@ wi::divmod_internal (HOST_WIDE_INT *quot

   if (remainder)
     {
+      if (n > dividend_blocks_needed)
+       n = dividend_blocks_needed;
       *remainder_len = wi_pack (remainder, b_remainder, n, dividend_prec);
       /* The remainder is always the same sign as the dividend.  */
       if (dividend_neg)
where the check which is useless for multiplication and quotient is done only
in the problematic spot - remainder.

[Bug middle-end/112733] [14 Regression] ICE: Segmentation fault in wide-int.cc during GIMPLE pass: sccp

[jakub at gcc dot gnu.org]

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

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 #10 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 56706
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=56706&action=edit
gcc14-pr112733.patch

First patch to be tested.

[Bug middle-end/112733] [14 Regression] ICE: Segmentation fault in wide-int.cc during GIMPLE pass: sccp

[jakub at gcc dot gnu.org]

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

--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 56707
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=56707&action=edit
gcc14-pr112733-2.patch

Second patch to be tested.  Turned out it is more complicated than that.
If n > m, i.e. when divisor in absolute value is larger than dividend, we want
divmod_internal_2 to know that, such that e.g. it skips the main loop and looks
at correct most significant half limb of the divisor, but the
  if (s)
    for (i = 0; i < n; i++)
      b_remainder[i] = (b_dividend[i] >> s)
        | (b_dividend[i+1] << (HOST_BITS_PER_HALF_WIDE_INT - s));
  else
    for (i = 0; i < n; i++)
      b_remainder[i] = b_dividend[i];
loops in such case already may invoke UB, because they copy stuff from
b_dividend which just isn't there, at best some random upper bits, at worst
crash.  We can't copy more than there is in the array and need to tell the
caller how much we've initialized, so that wi_pack can take it into account.

While looking into this, I've noticed that I've allocated in case of XALLOCAVEC
multiplication and division/remainder calculations twice or 4 times as much
as really needed, so this patch fixes that too.

[Bug middle-end/112733] [14 Regression] ICE: Segmentation fault in wide-int.cc during GIMPLE pass: sccp

[jakub at gcc dot gnu.org]

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

--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The #c11 patch regresses gcc.dg/bitint-3{8,9}.c tests (and apparently it is
just the 1st and/or 6th hunk where I've tried to make the XALLOCAVEC
allocations smaller; the rest of the changes seem to work ok.

[Bug middle-end/112733] [14 Regression] ICE: Segmentation fault in wide-int.cc during GIMPLE pass: sccp

[cvs-commit at gcc dot gnu.org]

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

--- Comment #13 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:5c95bf945c632925efba86dd5dceccdb9da8884c

commit r14-5963-g5c95bf945c632925efba86dd5dceccdb9da8884c
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Wed Nov 29 12:26:50 2023 +0100

    fold-const: Fix up multiple_of_p [PR112733]

    We ICE on the following testcase when wi::multiple_of_p is called on
    widest_int 1 and -128 with UNSIGNED.  I still need to work on the
    actual wide-int.cc issue, the latest patch attached to the PR regressed
    bitint-{38,39}.c, so will need to debug that, but there is a clear bug
    on the fold-const.cc side as well - widest_int is a signed representation
    by definition, using UNSIGNED with it certainly doesn't match what was
    intended, because -128 as the second operand effectively means unsigned
    131072 bit 0xfffff............ffff80 integer, not the signed char -128
    that appeared in the source.

    In the INTEGER_CST case a few lines above this we already use
        case INTEGER_CST:
          if (TREE_CODE (bottom) != INTEGER_CST || integer_zerop (bottom))
            return false;
          return wi::multiple_of_p (wi::to_widest (top), wi::to_widest
(bottom),
                                    SIGNED);
    so I think using SIGNED with widest_int is best there (compared to the
    other choices in the PR).

    2023-11-29  Jakub Jelinek  <jakub@redhat.com>

            PR middle-end/112733
            * fold-const.cc (multiple_of_p): Pass SIGNED rather than
            UNSIGNED for wi::multiple_of_p on widest_int arguments.

            * gcc.dg/pr112733.c: New test.

[Bug middle-end/112733] [14 Regression] ICE: Segmentation fault in wide-int.cc during GIMPLE pass: sccp

[cvs-commit at gcc dot gnu.org]

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

--- Comment #14 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:248bf197148451a3fb950b54fa313d1d252864b5

commit r14-5992-g248bf197148451a3fb950b54fa313d1d252864b5
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Thu Nov 30 09:13:00 2023 +0100

    wide-int: Fix wide_int division/remainder [PR112733]

    This patch fixes the other half of the PR, where we were crashing on the
    UNSIGNED widest_int modulo of 1 % -128 (where the -128 in UNSIGNED is
    131072 bit 0xfffff...fffff80).
    The patch actually has 2 independent parts.
    The fix for the divmod buffer overflow is in the 2nd-5th and 7th-8th hunks
of
    the patch.  abs (remainder) <= min (abs (dividend), abs (divisor)) and the
    wide-int.h callers estimate the remainder size to be the same as the
    quotient size, i.e. for UNSIGNED dividend with msb set quotient (same as
    remainder) precision based estimation, for SIGNED or dividend with msb
    clear estimate based on divident len (+ 1).
    For quotient (if any), wi_pack is called as
      quotient_len = wi_pack (quotient, b_quotient, m, dividend_prec);
    where m is
      m = dividend_blocks_needed;
      while (m > 1 && b_dividend[m - 1] == 0)
        m--;
    and
      dividend_blocks_needed = 2 * BLOCKS_NEEDED (dividend_prec);
    where wi_pack stores to result (in_len + 1) / 2 limbs (or one more
    if (in_len & 1) == 0 and in_len / 2 < BLOCKS_NEEDED (dividend_prec)).
    In any case, that is never more than BLOCKS_NEEDED (dividend_prec) and
    matches caller's estimations (then it is canonicalized and perhaps shrunk
    that way).

    The problematic case is the remainder, where wi_pack is called as
      *remainder_len = wi_pack (remainder, b_remainder, n, dividend_prec);
    The last argument is again based on the dividend precision like for
    quotient, but n is instead:
      n = divisor_blocks_needed;
      while (n > 1 && b_divisor[n - 1] == 0)
        n--;
    so based on the divisor rather than dividend.  Now, in the
    wi::multiple_of_p (1, -128, UNSIGNED) widest_int precision case,
    dividend_prec is very small, the dividend is 1 and while the official
    precision is 131072 bits, dividend_len is 1 and
      if (sgn == SIGNED || dividend_val[dividend_len - 1] >= 0)
        dividend_prec = MIN ((dividend_len + 1) * HOST_BITS_PER_WIDE_INT,
                             dividend_prec);
    shrinks the estimate to 128 bits in this case; but divisor_prec
    is huge, because the divisor is negative UNSIGNED, so 131072 bits,
    2048 limbs, 4096 half-limbs (so divisor_blocks_needed and n are 4096).
    Now, wi_pack relies on the penultimate argument to be smaller or equal
    to 2 * BLOCKS_NEEDED of the last argument and that is not the case here,
    4096 is certainly larger than 2 * BLOCKS_NEEDED (128) aka 4 and so
    wi_pack overflows the array.
    Unfortunately looking around, this isn't the only overflow, already
    in divmod_internal_2 we have an overflow, though there not overflowing
    a buffer during writing, but during reading.  When divmod_internal_2
    is called with the last 2 arguments like m=1, n=4096 as in this case
    (but generally any where m < n), it has a special case for n == 1 (which
    won't be the problem, we never have m or n 0), then decides based on
    msb of divisor whether there should be some shift canonicalization, then
    performs a
      for (j = m - n; j >= 0; j--)
    main loop and finally initializes b_remainder:
      if (s)
        for (i = 0; i < n; i++)
          b_remainder[i] = (b_dividend[i] >> s)
            | (b_dividend[i+1] << (HOST_BITS_PER_HALF_WIDE_INT - s));
      else
        for (i = 0; i < n; i++)
          b_remainder[i] = b_dividend[i];
    In the usual case of m >= n, the main loop will iterate at least once,
    b_dividend has m + 1 valid elements and the copying to b_remainder
    is correct.  But for the m < n unusual case, the main loop never iterates
    and we want to copy the b_dividend right into b_remainder (possibly with
    shifts).  Except when it copies n elements, it copies garbage which isn't
    there at all for the last n - m elements.
    Because the decision whether the main loop should iterate at all or not
    and the s computation should be based on the original n, the following
    patch sets n to MIN (n, m) only after the main loop, such that we copy
    to b_remainder at most what is initialized in b_dividend, and returns
    that adjusted value to the caller which then passes it to wi_pack and
    so satisfies again the requirement there, rather than trying to
    do the n = MIN (n, m) before calling divmod_internal_2 or after it.

    I believe the bug is mostly something I've only introduced myself in the
    > 576 bit wide_int/widest_int support changes, before that there was
    no attempt to decrease the precisions and so I think dividend_prec
    and divisor_prec were pretty much always the same (or always?),
    and even the copying of garbage wasn't the case because the only time
    m or n was decreased from the same precision was if there were 0s in the
    upper half-limbs.

    The 1st and 6th hunks in the patch is just that while looking at the
    code, I've noticed I computed wrong the sizes in the XALLOCAVEC case,
    somehow the 4 * in the static arrays led me believe I need to make the
    alloced buffers twice (in the multiplication) or 4 times (in the
    division/modulo cases) larger than needed.

    2023-11-30  Jakub Jelinek  <jakub@redhat.com>

            PR middle-end/112733
            * wide-int.cc (wi::mul_internal): Don't allocate twice as much
            space for u, v and r as needed.
            (divmod_internal_2): Change return type from void to int, for n ==
1
            return 1, otherwise before writing b_dividend into b_remainder set
            n to MIN (n, m) and at the end return it.
            (wi::divmod_internal): Don't allocate 4 times as much space for
            b_quotient, b_remainder, b_dividend and b_divisor.  Set n to
            result of divmod_internal_2.
            (wide_int_cc_tests): Add test for unsigned widest_int
            wi::multiple_of_p of 1 and -128.

[Bug middle-end/112733] [14 Regression] ICE: Segmentation fault in wide-int.cc during GIMPLE pass: sccp

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #15 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Should be fixed now.

[Bug middle-end/112733] [14 Regression] ICE: Segmentation fault in wide-int.cc during GIMPLE pass: sccp

[cvs-commit at gcc dot gnu.org]

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

--- Comment #16 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-13 branch has been updated by Jakub Jelinek
<jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:8c0ea9320ce4d2381ebf043cd20a0afce88da880

commit r13-8159-g8c0ea9320ce4d2381ebf043cd20a0afce88da880
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Wed Nov 29 12:26:50 2023 +0100

    fold-const: Fix up multiple_of_p [PR112733]

    We ICE on the following testcase when wi::multiple_of_p is called on
    widest_int 1 and -128 with UNSIGNED.  I still need to work on the
    actual wide-int.cc issue, the latest patch attached to the PR regressed
    bitint-{38,39}.c, so will need to debug that, but there is a clear bug
    on the fold-const.cc side as well - widest_int is a signed representation
    by definition, using UNSIGNED with it certainly doesn't match what was
    intended, because -128 as the second operand effectively means unsigned
    131072 bit 0xfffff............ffff80 integer, not the signed char -128
    that appeared in the source.

    In the INTEGER_CST case a few lines above this we already use
        case INTEGER_CST:
          if (TREE_CODE (bottom) != INTEGER_CST || integer_zerop (bottom))
            return false;
          return wi::multiple_of_p (wi::to_widest (top), wi::to_widest
(bottom),
                                    SIGNED);
    so I think using SIGNED with widest_int is best there (compared to the
    other choices in the PR).

    2023-11-29  Jakub Jelinek  <jakub@redhat.com>

            PR middle-end/112733
            * fold-const.cc (multiple_of_p): Pass SIGNED rather than
            UNSIGNED for wi::multiple_of_p on widest_int arguments.

            * gcc.dg/pr112733.c: New test.

    (cherry picked from commit 5c95bf945c632925efba86dd5dceccdb9da8884c)

[Bug middle-end/112733] [14 Regression] ICE: Segmentation fault in wide-int.cc during GIMPLE pass: sccp

[cvs-commit at gcc dot gnu.org]

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

--- Comment #17 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-12 branch has been updated by Jakub Jelinek
<jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:4bf040fcd23aaa7d8c4873d1170776ab117bc213

commit r12-10055-g4bf040fcd23aaa7d8c4873d1170776ab117bc213
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Wed Nov 29 12:26:50 2023 +0100

    fold-const: Fix up multiple_of_p [PR112733]

    We ICE on the following testcase when wi::multiple_of_p is called on
    widest_int 1 and -128 with UNSIGNED.  I still need to work on the
    actual wide-int.cc issue, the latest patch attached to the PR regressed
    bitint-{38,39}.c, so will need to debug that, but there is a clear bug
    on the fold-const.cc side as well - widest_int is a signed representation
    by definition, using UNSIGNED with it certainly doesn't match what was
    intended, because -128 as the second operand effectively means unsigned
    131072 bit 0xfffff............ffff80 integer, not the signed char -128
    that appeared in the source.

    In the INTEGER_CST case a few lines above this we already use
        case INTEGER_CST:
          if (TREE_CODE (bottom) != INTEGER_CST || integer_zerop (bottom))
            return false;
          return wi::multiple_of_p (wi::to_widest (top), wi::to_widest
(bottom),
                                    SIGNED);
    so I think using SIGNED with widest_int is best there (compared to the
    other choices in the PR).

    2023-11-29  Jakub Jelinek  <jakub@redhat.com>

            PR middle-end/112733
            * fold-const.cc (multiple_of_p): Pass SIGNED rather than
            UNSIGNED for wi::multiple_of_p on widest_int arguments.

            * gcc.dg/pr112733.c: New test.

    (cherry picked from commit 5c95bf945c632925efba86dd5dceccdb9da8884c)

[Bug middle-end/112733] [14 Regression] ICE: Segmentation fault in wide-int.cc during GIMPLE pass: sccp

[cvs-commit at gcc dot gnu.org]

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

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

https://gcc.gnu.org/g:124a2110a1f5bbfe7274251b25b3944910296887

commit r11-11155-g124a2110a1f5bbfe7274251b25b3944910296887
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Wed Nov 29 12:26:50 2023 +0100

    fold-const: Fix up multiple_of_p [PR112733]

    We ICE on the following testcase when wi::multiple_of_p is called on
    widest_int 1 and -128 with UNSIGNED.  I still need to work on the
    actual wide-int.cc issue, the latest patch attached to the PR regressed
    bitint-{38,39}.c, so will need to debug that, but there is a clear bug
    on the fold-const.cc side as well - widest_int is a signed representation
    by definition, using UNSIGNED with it certainly doesn't match what was
    intended, because -128 as the second operand effectively means unsigned
    131072 bit 0xfffff............ffff80 integer, not the signed char -128
    that appeared in the source.

    In the INTEGER_CST case a few lines above this we already use
        case INTEGER_CST:
          if (TREE_CODE (bottom) != INTEGER_CST || integer_zerop (bottom))
            return false;
          return wi::multiple_of_p (wi::to_widest (top), wi::to_widest
(bottom),
                                    SIGNED);
    so I think using SIGNED with widest_int is best there (compared to the
    other choices in the PR).

    2023-11-29  Jakub Jelinek  <jakub@redhat.com>

            PR middle-end/112733
            * fold-const.c (multiple_of_p): Pass SIGNED rather than
            UNSIGNED for wi::multiple_of_p on widest_int arguments.

            * gcc.dg/pr112733.c: New test.

    (cherry picked from commit 5c95bf945c632925efba86dd5dceccdb9da8884c)