[Bug tree-optimization/108639] New: ICE on valid code at -O1 and above: in decompose, at wide-int.h:984

[Bug tree-optimization/108639] New: ICE on valid code at -O1 and above: in decompose, at wide-int.h:984

[zhendong.su at inf dot ethz.ch]

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

            Bug ID: 108639
           Summary: ICE on valid code at -O1 and above: in decompose, at
                    wide-int.h:984
           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.

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

[538] % 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/13.0.1/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
--with-system-zlib
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 13.0.1 20230202 (experimental) [master r13-5642-g66d700af5bb] (GCC)
[539] %
[539] % gcctk -O1 small.c
small.c: In function ‘main’:
small.c:3:18: warning: division by zero [-Wdiv-by-zero]
    3 |   a = a ? 0 || 0 % 0 : 0;
      |                  ^
during GIMPLE pass: dom
small.c:2:5: internal compiler error: in decompose, at wide-int.h:984
    2 | int main() {
      |     ^~~~
0x7b6a92 wi::int_traits<generic_wide_int<wide_int_ref_storage<false, false> >
>::decompose(long*, unsigned int, generic_wide_int<wide_int_ref_storage<false,
false> > const&)
        ../../gcc-trunk/gcc/wide-int.h:984
0x7b7838 wi::int_traits<generic_wide_int<wide_int_storage> >::decompose(long*,
unsigned int, generic_wide_int<wide_int_storage> const&)
        ../../gcc-trunk/gcc/value-range.h:940
0x7b7838 wide_int_ref_storage<true,
false>::wide_int_ref_storage<generic_wide_int<wide_int_storage>
>(generic_wide_int<wide_int_storage> const&, unsigned int)
        ../../gcc-trunk/gcc/wide-int.h:1034
0x7b7838 generic_wide_int<wide_int_ref_storage<true, false>
>::generic_wide_int<generic_wide_int<wide_int_storage>
>(generic_wide_int<wide_int_storage> const&, unsigned int)
        ../../gcc-trunk/gcc/wide-int.h:790
0x7b7838 bool wi::eq_p<generic_wide_int<wide_int_storage>,
generic_wide_int<wide_int_storage> >(generic_wide_int<wide_int_storage> const&,
generic_wide_int<wide_int_storage> const&)
        ../../gcc-trunk/gcc/wide-int.h:1873
0x7b7838 wi::binary_traits<generic_wide_int<wide_int_storage>,
generic_wide_int<wide_int_storage>,
wi::int_traits<generic_wide_int<wide_int_storage> >::precision_type,
wi::int_traits<generic_wide_int<wide_int_storage>
>::precision_type>::predicate_result
operator==<generic_wide_int<wide_int_storage>,
generic_wide_int<wide_int_storage> >(generic_wide_int<wide_int_storage> const&,
generic_wide_int<wide_int_storage> const&)
        ../../gcc-trunk/gcc/wide-int.h:3307
0x7b7838 irange::operator==(irange const&) const
        ../../gcc-trunk/gcc/value-range.cc:1297
0x7b7838 irange::operator==(irange const&) const
        ../../gcc-trunk/gcc/value-range.cc:1266
0x1e4fc26 range_operator::fold_range(irange&, tree_node*, irange const&, irange
const&, relation_trio) const
        ../../gcc-trunk/gcc/range-op.cc:271
0x1e5030c operator_lshift::fold_range(irange&, tree_node*, irange const&,
irange const&, relation_trio) const
        ../../gcc-trunk/gcc/range-op.cc:2246
0x1d4db80 fold_using_range::range_of_range_op(vrange&,
gimple_range_op_handler&, fur_source&)
        ../../gcc-trunk/gcc/gimple-range-fold.cc:589
0x1d4f56a fold_using_range::fold_stmt(vrange&, gimple*, fur_source&,
tree_node*)
        ../../gcc-trunk/gcc/gimple-range-fold.cc:489
0x1d40d7c gimple_ranger::fold_range_internal(vrange&, gimple*, tree_node*)
        ../../gcc-trunk/gcc/gimple-range.cc:257
0x1d40d7c gimple_ranger::range_of_stmt(vrange&, gimple*, tree_node*)
        ../../gcc-trunk/gcc/gimple-range.cc:318
0x1d42ac0 gimple_ranger::range_of_expr(vrange&, tree_node*, gimple*)
        ../../gcc-trunk/gcc/gimple-range.cc:126
0x1028acf cprop_operand
        ../../gcc-trunk/gcc/tree-ssa-dom.cc:1972
0x102a969 cprop_into_stmt
        ../../gcc-trunk/gcc/tree-ssa-dom.cc:2049
0x102a969 dom_opt_dom_walker::optimize_stmt(basic_block_def*,
gimple_stmt_iterator*, bool*)
        ../../gcc-trunk/gcc/tree-ssa-dom.cc:2277
0x102bd13 dom_opt_dom_walker::before_dom_children(basic_block_def*)
        ../../gcc-trunk/gcc/tree-ssa-dom.cc:1682
0x1d0a0f7 dom_walker::walk(basic_block_def*)
        ../../gcc-trunk/gcc/domwalk.cc:311
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.
[540] %
[540] % cat small.c
long a;
int main() {
  a = a ? 0 || 0 % 0 : 0;
  a = a << a;
  return 0;
}

[Bug tree-optimization/108639] ]13 Regression] ICE on valid code at -O1 and above: in decompose, at wide-int.h:984 since r13-5578

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Version|unknown                     |13.0
     Ever confirmed|0                           |1
           Priority|P3                          |P1
                 CC|                            |jakub at gcc dot gnu.org
            Summary|ICE on valid code at -O1    |]13 Regression] ICE on
                   |and above: in decompose, at |valid code at -O1 and
                   |wide-int.h:984              |above: in decompose, at
                   |                            |wide-int.h:984 since
                   |                            |r13-5578
   Target Milestone|---                         |13.0
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2023-02-02

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Started with r13-5578-g809d661aff99ae0287baf4a52269425de62381e6

[Bug tree-optimization/108639] ]13 Regression] ICE on valid code at -O1 and above: in decompose, at wide-int.h:984 since r13-5578

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amacleod at redhat dot com

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
The problem is in
271       if (relation_equiv_p (rel) && lh == rh)
We see
  # RANGE [irange] int [0, 1] NONZERO 0x1
  # iftmp.0_6 = PHI <_10(3), 0(2)>
  # RANGE [irange] long int [0, 1] NONZERO 0x1
  _3 = (long int) iftmp.0_6;
  # RANGE [irange] unsigned int [0, 1] NONZERO 0x1
  _4 = (unsigned int) iftmp.0_6;
  # RANGE [irange] long int [-INF, +INF] NONZERO 0x3
  _5 = _3 << _4;
so lhs and rhs indeed have the same range, but unlike most binary operations,
shifts/rotates have the same type between lhs and rhs1, but rhs2 can have
different type.
So, the lh == rh comparison ICEs because the wide_ints have different precision
(but same values).

[Bug tree-optimization/108639] ]13 Regression] ICE on valid code at -O1 and above: in decompose, at wide-int.h:984 since r13-5578

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 54391
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54391&action=edit
gcc13-pr108639.patch

Untested fix.

[Bug tree-optimization/108639] ]13 Regression] ICE on valid code at -O1 and above: in decompose, at wide-int.h:984 since r13-5578

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dcb314 at hotmail dot com

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
*** Bug 108638 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/108639] [13 Regression] ICE on valid code at -O1 and above: in decompose, at wide-int.h:984 since r13-5578

[aldyh at gcc dot gnu.org]

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

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

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

--- Comment #5 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
(In reply to Jakub Jelinek from comment #3)
> Created attachment 54391 [details]
> gcc13-pr108639.patch
> 
> Untested fix.

I think the problem is more fundamental than that.  The equality operator for
irange is not ICEing for the sub-range comparison (which also have different
precision), but is dying in the nonzero mask comparison.

[Bug tree-optimization/108639] [13 Regression] ICE on valid code at -O1 and above: in decompose, at wide-int.h:984 since r13-5578

[aldyh at gcc dot gnu.org]

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

--- Comment #6 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
Created attachment 54393
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54393&action=edit
untested patch for irange::operator==

[Bug tree-optimization/108639] [13 Regression] ICE on valid code at -O1 and above: in decompose, at wide-int.h:984 since r13-5578

[aldyh at gcc dot gnu.org]

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

--- Comment #7 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
Jakub, take a look and see if you agree.  I've fired off some tests.

[Bug tree-optimization/108639] [13 Regression] ICE on valid code at -O1 and above: in decompose, at wide-int.h:984 since r13-5578

[jakub at gcc dot gnu.org]

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

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Aldy Hernandez from comment #5)
> (In reply to Jakub Jelinek from comment #3)
> > Created attachment 54391 [details]
> > gcc13-pr108639.patch
> > 
> > Untested fix.
> 
> I think the problem is more fundamental than that.  The equality operator
> for irange is not ICEing for the sub-range comparison (which also have
> different precision), but is dying in the nonzero mask comparison.

Well, that is obvious, because for the actual range boundaries you compare
trees, not wide_ints.  And operand_equal_p does allow comparing of trees with
different types.
It in that case calls tree_int_cst_equal.  But when you switch the boundaries
from trees to wide_ints, they will ICE again as well.

I think for the operator==, the important question is, shall ranges with same
values but non-compatible types compare
1) equal
2) non-equal
3) be an ICE (e.g. gcc_checking_assert)
The current state is 3) without the assert and my patch was trying to fix the
caller.
Your patch is changing it to 1), in that case no change would be needed in the
particular lh == rh user, but are we sure that everywhere where non-compatible
types could appear we don't imply from operator== returning true that the types
are actually the same?
If we did 2) e.g. by adding a types_compatible_p (type (), b.type ()) check,
then we'd
need to change this lh == rh user too, because for the shifts we really just
care about values and not the exact types which can differ.

[Bug tree-optimization/108639] [13 Regression] ICE on valid code at -O1 and above: in decompose, at wide-int.h:984 since r13-5578

[amacleod at redhat dot com]

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

--- Comment #9 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Jakub Jelinek from comment #8)
> (In reply to Aldy Hernandez from comment #5)
> > (In reply to Jakub Jelinek from comment #3)
> > > Created attachment 54391 [details]
> > > gcc13-pr108639.patch
> > > 
> > > Untested fix.
> > 
> > I think the problem is more fundamental than that.  The equality operator
> > for irange is not ICEing for the sub-range comparison (which also have
> > different precision), but is dying in the nonzero mask comparison.
> 
> Well, that is obvious, because for the actual range boundaries you compare
> trees, not wide_ints.  And operand_equal_p does allow comparing of trees
> with different types.
> It in that case calls tree_int_cst_equal.  But when you switch the
> boundaries from trees to wide_ints, they will ICE again as well.
> 
> I think for the operator==, the important question is, shall ranges with
> same values but non-compatible types compare
> 1) equal
> 2) non-equal
> 3) be an ICE (e.g. gcc_checking_assert)
> The current state is 3) without the assert and my patch was trying to fix
> the caller.

3) is not a desired result for sure.

I think 1) is our desired outcome... I initially considered 2) as desirable as
we could simply check the types before doing any other work.   As I thought
about it tho, I can't think of any good reason why we would want them to be
unequal.

If they compare equal this way (ignoring type), then performing a cast on
either of them to the same type as the other would also compare equal... its
symmetrical so that actually makes them equal in my book.

[Bug tree-optimization/108639] [13 Regression] ICE on valid code at -O1 and above: in decompose, at wide-int.h:984 since r13-5578

[jakub at gcc dot gnu.org]

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

--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Ok then.
I won't test my patch then, the testcases from it were:
--- gcc/testsuite/gcc.c-torture/compile/pr108638.c.jj   2022-11-21
10:04:00.210677046 +0100
+++ gcc/testsuite/gcc.c-torture/compile/pr108638.c      2023-02-02
16:51:06.082371450 +0100
@@ -0,0 +1,12 @@
+/* PR tree-optimization/108638 */
+
+long long a;
+int b;
+
+void
+foo (void)
+{
+  for (a = 0; a < __SIZEOF_LONG_LONG__ * __CHAR_BIT__; a++)
+    if (b)
+      b |= a << a;
+}
--- gcc/testsuite/gcc.c-torture/compile/pr108639.c.jj   2023-02-02
16:26:44.113600462 +0100
+++ gcc/testsuite/gcc.c-torture/compile/pr108639.c      2023-02-02
16:26:23.309902211 +0100
@@ -0,0 +1,11 @@
+/* PR tree-optimization/108639 */
+
+long long a;
+
+int
+main ()
+{
+  a = a ? 0 || 0 % 0 : 0;
+  a = a << a;
+  return 0;
+}

[Bug tree-optimization/108639] [13 Regression] ICE on valid code at -O1 and above: in decompose, at wide-int.h:984 since r13-5578

[rguenth at gcc dot gnu.org]

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

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
Yes, they should compare equal.  Integer constant ranges do not need a type.
Not even FP constant ranges.  Symbolic ranges need a type, but then the
endpoints in their symbolic form have one (and those might even differ).

[Bug tree-optimization/108639] [13 Regression] ICE on valid code at -O1 and above: in decompose, at wide-int.h:984 since r13-5578

[aldyh at gcc dot gnu.org]

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

--- Comment #12 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
Yeah, I've been mulling around the idea of removing the type from storage of
both irange and frange.  It seems we need it for setting a type (setting the
endpoints for varying, querying HONOR_NANS, HONOR_INFINITIES,e tc), but not in
the storage itself.  Something to keep in mind when moving to wide_ints.

It does seem we need to keep the sign and precision somewhere.  The precision
lives in the wide-int, but the sign bit still needs storage??

[Bug tree-optimization/108639] [13 Regression] ICE on valid code at -O1 and above: in decompose, at wide-int.h:984 since r13-5578

[cvs-commit at gcc dot gnu.org]

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

--- Comment #13 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Aldy Hernandez <aldyh@gcc.gnu.org>:

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

commit r13-5696-ge261fcefb71e1270673f0457fcc73711f13d3079
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Thu Feb 2 18:08:44 2023 +0100

    irange: Compare nonzero bits in irange with widest_int [PR108639]

    The problem here is we are trying to compare two ranges with different
    precisions and the == operator in wide_int is complaining.

    Interestingly, the problem is not the nonzero bits, but the fact that
    the entire ranges have different precisions.  The reason we don't ICE
    when comparing the sub-ranges, is because the code in
    irange::operator== works on trees, and tree_int_cst_equal is
    promoting the comparison to a widest int:

      if (TREE_CODE (t1) == INTEGER_CST
          && TREE_CODE (t2) == INTEGER_CST
          && wi::to_widest (t1) == wi::to_widest (t2))
        return 1;

    This is why we don't see the ICE until the nonzero bits comparison is
    done on wide ints.  I think we should maintain the current equality
    behavior, and follow suit in the nonzero bit comparison.

    I have also fixed the legacy equality code, even though technically
    nonzero bits shouldn't appear in legacy.  But better safe than sorry.

            PR tree-optimization/108639

    gcc/ChangeLog:

            * value-range.cc (irange::legacy_equal_p): Compare nonzero bits as
            widest_int.
            (irange::operator==): Same.

[Bug tree-optimization/108639] [13 Regression] ICE on valid code at -O1 and above: in decompose, at wide-int.h:984 since r13-5578

[jakub at gcc dot gnu.org]

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

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

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

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

[Bug tree-optimization/108639] [13 Regression] ICE on valid code at -O1 and above: in decompose, at wide-int.h:984 since r13-5578

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |vsevolod.livinskiy at gmail dot co
                   |                            |m

--- Comment #15 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 108668 has been marked as a duplicate of this bug. ***