[Bug tree-optimization/97315] New: [11 Regression] ICE in choose_value, at gimple-ssa-evrp.c:282 since r11-3690-gebc77ce3a4c70730b4e38d68f88693eadbdc8712

[Bug tree-optimization/97315] New: [11 Regression] ICE in choose_value, at gimple-ssa-evrp.c:282 since r11-3690-gebc77ce3a4c70730b4e38d68f88693eadbdc8712

[marxin at gcc dot gnu.org]

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

            Bug ID: 97315
           Summary: [11 Regression] ICE in choose_value, at
                    gimple-ssa-evrp.c:282 since
                    r11-3690-gebc77ce3a4c70730b4e38d68f88693eadbdc8712
           Product: gcc
           Version: 10.0
            Status: UNCONFIRMED
          Keywords: ice-on-valid-code
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: marxin at gcc dot gnu.org
                CC: aldyh at gcc dot gnu.org, amacleod at redhat dot com
  Target Milestone: ---

The following fails:

$ cat ipa-devirt.ii
typedef struct tree_node *tree;
enum tree_code { RECORD_TYPE, QUAL_UNION_TYPE };
enum tree_code_class {};
struct tree_base {
  tree_code code : 16;
};
struct tree_node {
  tree_base base;
};
extern tree_code_class tree_code_type[];
void tree_check_failed() __attribute__((__noreturn__));
tree tree_check3(tree __t, tree_code __c1, tree_code __c3) {
  if (__t->base.code != __c1 && __t->base.code != __c3)
    tree_check_failed();
  return __t;
}
tree add_type_duplicate_type;
void add_type_duplicate() {
  if (tree_code_type[add_type_duplicate_type->base.code])
    if (add_type_duplicate_type->base.code == RECORD_TYPE)
      for (;
           tree_check3(add_type_duplicate_type, RECORD_TYPE, QUAL_UNION_TYPE);)
        tree_check3(add_type_duplicate_type, RECORD_TYPE, QUAL_UNION_TYPE);
}

$ g++ -O3 -fno-exceptions ipa-devirt.ii -c
during GIMPLE pass: evrp
ipa-devirt.ii: In function ‘void add_type_duplicate()’:
ipa-devirt.ii:24:1: internal compiler error: in choose_value, at
gimple-ssa-evrp.c:282
   24 | }
      | ^
0x87dc65 hybrid_folder::choose_value(tree_node*, tree_node*)
        /home/marxin/Programming/gcc/gcc/gimple-ssa-evrp.c:282
0x11a4793 substitute_and_fold_engine::replace_uses_in(gimple*)
        /home/marxin/Programming/gcc/gcc/tree-ssa-propagate.c:871
0x11a4adc substitute_and_fold_dom_walker::before_dom_children(basic_block_def*)
        /home/marxin/Programming/gcc/gcc/tree-ssa-propagate.c:1141
0x194da67 dom_walker::walk(basic_block_def*)
        /home/marxin/Programming/gcc/gcc/domwalk.c:309
0x11a3f25 substitute_and_fold_engine::substitute_and_fold(basic_block_def*)
        /home/marxin/Programming/gcc/gcc/tree-ssa-propagate.c:1283
0x1973a06 execute_early_vrp
        /home/marxin/Programming/gcc/gcc/gimple-ssa-evrp.c:334
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <https://gcc.gnu.org/bugs/> for instructions.

[Bug tree-optimization/97315] [11 Regression] ICE in choose_value, at gimple-ssa-evrp.c:282 since r11-3690-gebc77ce3a4c70730b4e38d68f88693eadbdc8712

[marxin at gcc dot gnu.org]

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

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
      Known to work|                            |10.2.0
      Known to fail|                            |11.0
   Target Milestone|---                         |11.0
     Ever confirmed|0                           |1
           Priority|P3                          |P1
   Last reconfirmed|                            |2020-10-07

[Bug tree-optimization/97315] [11 Regression] ICE in choose_value, at gimple-ssa-evrp.c:282 since r11-3690-gebc77ce3a4c70730b4e38d68f88693eadbdc8712

[acoplan at gcc dot gnu.org]

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

Alex Coplan <acoplan at gcc dot gnu.org> changed:

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

--- Comment #1 from Alex Coplan <acoplan at gcc dot gnu.org> ---
Seeing a similar ICE with the following simple C testcase:

int a;
int b(signed char c, int d) { return c < 0 ? 0 : c >> d; }
void e(void)
{
  for (int i = 0; i <= 0; i++)
    while (a)
      b(-(i != 1), i);
}

$ aarch64-elf-gcc -O2 test.c
during GIMPLE pass: evrp
test.c: In function 'e':
test.c:8:1: internal compiler error: in choose_value, at gimple-ssa-evrp.c:282
    8 | }
      | ^
0x18d93f0 hybrid_folder::choose_value(tree_node*, tree_node*)
        /home/alecop01/toolchain/src/gcc/gcc/gimple-ssa-evrp.c:282
0x18d94e4 hybrid_folder::value_of_expr(tree_node*, gimple*)
        /home/alecop01/toolchain/src/gcc/gcc/gimple-ssa-evrp.c:236
0xf8e112 substitute_and_fold_engine::replace_uses_in(gimple*)
        /home/alecop01/toolchain/src/gcc/gcc/tree-ssa-propagate.c:871
0xf8e912 substitute_and_fold_dom_walker::before_dom_children(basic_block_def*)
        /home/alecop01/toolchain/src/gcc/gcc/tree-ssa-propagate.c:1141
0x18a5d5b dom_walker::walk(basic_block_def*)
        /home/alecop01/toolchain/src/gcc/gcc/domwalk.c:309
0xf8f885 substitute_and_fold_engine::substitute_and_fold(basic_block_def*)
        /home/alecop01/toolchain/src/gcc/gcc/tree-ssa-propagate.c:1283
0x18d9828 execute_early_vrp
        /home/alecop01/toolchain/src/gcc/gcc/gimple-ssa-evrp.c:328
0x18d9bf8 execute
        /home/alecop01/toolchain/src/gcc/gcc/gimple-ssa-evrp.c:375
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <https://gcc.gnu.org/bugs/> for instructions.

[Bug tree-optimization/97315] [11 Regression] ICE in choose_value, at gimple-ssa-evrp.c:282 since r11-3690-gebc77ce3a4c70730b4e38d68f88693eadbdc8712

[aldyh at gcc dot gnu.org]

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

--- Comment #2 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
evrp and ranger disagree on the singleton range for _3 in the following stmt:

 <bb 5> :
  if (_3 != 1)

(gdb) ptg evrp_ret
0

(gdb) ptg ranger_ret
1

Which is interesting because BB5 is actually unreachable:

add_type_duplicate ()
{
  struct tree_node * D.2384;
  struct tree_node * add_type_duplicate_type.2_1;
  short unsigned int _2;
  int _3;
  tree_code_class _4;

  <bb 2> :
  add_type_duplicate_type.2_1 = add_type_duplicate_type;
  _2 = add_type_duplicate_type.2_1->base.code;
  _3 = (int) _2;
  _4 = tree_code_type[_3];
  if (_4 != 0)
    goto <bb 3>; [INV]
  else
    goto <bb 11>; [INV]

  <bb 3> :
  if (_2 == 0)
    goto <bb 13>; [INV]
  else
    goto <bb 11>; [INV]

  <bb 4> :
  if (0 != 0)
    goto <bb 5>; [66.00%]
  else
    goto <bb 15>; [34.00%]

  <bb 15> :
  goto <bb 12>; [100.00%]

  <bb 5> :
  if (_3 != 1)
    goto <bb 6>; [0.04%]
  else
    goto <bb 14>; [99.96%]

  <bb 14> :
  goto <bb 7>; [100.00%]

  <bb 6> :
  tree_check_failed ();

  <bb 13> :

  <bb 7> :

  <bb 12> :
  if (0 != 0)
    goto <bb 8>; [66.00%]
  else
    goto <bb 10>; [34.00%]

  <bb 8> :
  if (1 != 0)
    goto <bb 9>; [0.04%]
  else
    goto <bb 10>; [99.96%]

  <bb 9> :
  tree_check_failed ();

  <bb 10> :
  if (1 != 0)
    goto <bb 4>; [INV]
  else
    goto <bb 11>; [INV]

  <bb 11> :
  return;

}

I'm guessing evrp

[Bug tree-optimization/97315] [11 Regression] ICE in choose_value, at gimple-ssa-evrp.c:282 since r11-3690-gebc77ce3a4c70730b4e38d68f88693eadbdc8712

[aldyh at gcc dot gnu.org]

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

--- Comment #3 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
(In reply to Alex Coplan from comment #1)
> Seeing a similar ICE with the following simple C testcase:
> 
> int a;
> int b(signed char c, int d) { return c < 0 ? 0 : c >> d; }
> void e(void)
> {
>   for (int i = 0; i <= 0; i++)
>     while (a)
>       b(-(i != 1), i);
> }
> 
> $ aarch64-elf-gcc -O2 test.c

evrp and ranger disagree on the singleton for i_6.

(gdb) ptg ranger_val
1

(gdb) ptg evrp_val
0

(gdb) ptgs stmt
iftmp.0_13 = _12 >> i_6;

This is the same issue.  stmt is in BB4, which is unreachable.

[Bug tree-optimization/97315] [11 Regression] ICE in choose_value, at gimple-ssa-evrp.c:282 since r11-3690-gebc77ce3a4c70730b4e38d68f88693eadbdc8712

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
EVRP knows to "skip" unreachable edges.  Not sure how you even "ask" EVRP for
values in unreachable blocks?  It's lattice does never reflect its state?

[Bug tree-optimization/97315] [11 Regression] ICE in choose_value, at gimple-ssa-evrp.c:282 since r11-3690-gebc77ce3a4c70730b4e38d68f88693eadbdc8712

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #4)
> EVRP knows to "skip" unreachable edges.  Not sure how you even "ask" EVRP
> for values in unreachable blocks?  It's lattice does never reflect its state?

Also the substitute-and-fold stage avoided to even look at unreachable regions
(for compile-time reasons and to avoid using "inconsistent" state)

[Bug tree-optimization/97315] [11 Regression] ICE in choose_value, at gimple-ssa-evrp.c:282 since r11-3690-gebc77ce3a4c70730b4e38d68f88693eadbdc8712

[dcb314 at hotmail dot com]

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

--- Comment #6 from David Binderman <dcb314 at hotmail dot com> ---

I get something similar with this test case:

int a;
void b() {
  if (a >= 2147483647)
    c(a + 1);
}

[Bug tree-optimization/97315] [11 Regression] ICE in choose_value, at gimple-ssa-evrp.c:282 since r11-3690-gebc77ce3a4c70730b4e38d68f88693eadbdc8712

[amacleod at redhat dot com]

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

--- Comment #7 from Andrew Macleod <amacleod at redhat dot com> ---
OK, there are a couple of things at play in this PR.

The original problem isn't actually unreachable code.  well, sort of.  

The pass determines something is unreachable and changes the condition, which
means it will be unreachable when its done.. but the dom walk will continue.

The issue is that this triggers a case where EVRP gets a singleton that we
miss, and thats what triggers the stmt rewrite., 

 _2 = add_type_duplicate_type.2_1->base.code;
 _3 = (int) _2;

Theres a chaining of conditions with _3 and _2
<bb 3> :
  if (_2 == 0)
    goto <bb 7>; [INV]
<bb 7> :
  if (_3 != 0)
    goto <bb 8>; [66.00%]
if (_3 != 1)
    goto <bb 9>; [0.04%]
 else
    goto <bb 10>; [99.96%]

<bb 10> :
  if (add_type_duplicate_type.2_1 != 0B)
    goto <bb 4>; [INV]
<bb 4> :
  if (_3 != 0)
    goto <bb 5>; [66.00%]

And at some point (and I know where and why, the cast chain being in a
different block than the condition... its on my list)  ranger loses track that
_3 is actually [0,0], and instead thinks its still [0,1]

so EVRP finds the singlton [0,0] and turns 

vrp visiting stmt if (_3 != 0)
Folding statement: if (_3 != 0)

into if (0 != 0)


Which of course makes some code look unreachable (and it will be when the CFG
is updated.)
Meanwhile we plug along, and since the ranger is dynamic, that condition now
factors into any calculations, and when we get to a later statement, 

evrp visiting stmt if (_3 != 1)

using this new found information, ranger says, aha, I can refine [0,1] for _3, 
is actually [1,1] on one edge, whereas evrp simply reports the [0,0] it already
had.


bottom line, its triggered by ranger missing something...


I wasn't expecting this to trigger due to shortcomings... I was expecting it to
be just bugs.

given that, I think I will change this to  again, flag the difference like I do
with ranges, and use the value produced by whichever pass is going first.

That way we wont be stopped by this sort of issue when  its really just a
shortcoming.

[Bug tree-optimization/97315] [11 Regression] ICE in choose_value, at gimple-ssa-evrp.c:282 since r11-3690-gebc77ce3a4c70730b4e38d68f88693eadbdc8712

[amacleod at redhat dot com]

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

--- Comment #8 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to David Binderman from comment #6)
> I get something similar with this test case:
> 
> int a;
> void b() {
>   if (a >= 2147483647)
>     c(a + 1);
> }

This one is slightly different.

Still triggering in the same place, but the difference in the singleton is the
result of the calculation of:

   [+INF, +INF] + 1

EVRP is reporting  [-INF, -INF], and range-ops is calculating  [+INF, +INF]

Is there a correct answer, or does it matter?   

The code we imported for handling overflow always sets the bound to +INF if an
overflow happens, and it happens on both bounds, so we get  [+INF, +INF].  I'm
guessing because its a single value EVRP actually folded the value regardless
of overflow?   

Or maybe it should be  UNDEFINED? 

Andrew

[Bug tree-optimization/97315] [11 Regression] ICE in choose_value, at gimple-ssa-evrp.c:282 since r11-3690-gebc77ce3a4c70730b4e38d68f88693eadbdc8712

[rguenther at suse dot de]

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

--- Comment #9 from rguenther at suse dot de <rguenther at suse dot de> ---
On October 7, 2020 5:35:02 PM GMT+02:00, amacleod at redhat dot com
<gcc-bugzilla@gcc.gnu.org> wrote:
>https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97315
>
>--- Comment #8 from Andrew Macleod <amacleod at redhat dot com> ---
>(In reply to David Binderman from comment #6)
>> I get something similar with this test case:
>> 
>> int a;
>> void b() {
>>   if (a >= 2147483647)
>>     c(a + 1);
>> }
>
>This one is slightly different.
>
>Still triggering in the same place, but the difference in the singleton
>is the
>result of the calculation of:
>
>   [+INF, +INF] + 1
>
>EVRP is reporting  [-INF, -INF], and range-ops is calculating  [+INF,
>+INF]
>
>Is there a correct answer, or does it matter?   

While we print +inf it's just a value we can apply +1 to in the "do what I
mean" sense. So I think for arithmetic we shouldn't saturate, even when
overflow is undefined (instead as, you say, UNDEFINED would be the correct
optimistic result).

>The code we imported for handling overflow always sets the bound to
>+INF if an
>overflow happens, and it happens on both bounds, so we get  [+INF,
>+INF].  I'm
>guessing because its a single value EVRP actually folded the value
>regardless
>of overflow?   
>
>Or maybe it should be  UNDEFINED? 
>
>Andrew

[Bug tree-optimization/97315] [11 Regression] ICE in choose_value, at gimple-ssa-evrp.c:282 since r11-3690-gebc77ce3a4c70730b4e38d68f88693eadbdc8712

[amacleod at redhat dot com]

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

Andrew Macleod <amacleod at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |amacleod at redhat dot com

--- Comment #10 from Andrew Macleod <amacleod at redhat dot com> ---
Created attachment 49324
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49324&action=edit
Patch to fix the problem

Running the following patch thru bootstrap and testing.  

a) removes the trap and instead annotates the listing.
b) Changes any non-overflow calculation in which both bounds are
overflow/underflow to be undefined.

Which seems to resolve everything I am seeing in this PR.

[Bug tree-optimization/97315] [11 Regression] ICE in choose_value, at gimple-ssa-evrp.c:282 since r11-3690-gebc77ce3a4c70730b4e38d68f88693eadbdc8712

[cvs-commit at gcc dot gnu.org]

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

--- Comment #11 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:214d514fafcd78cd54e4a4aa9ae08c89abf9cc57

commit r11-3717-g214d514fafcd78cd54e4a4aa9ae08c89abf9cc57
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Thu Oct 8 11:15:23 2020 +0200

    Fix PR97315 (part 1 of 2)

    gcc/ChangeLog:

            PR tree-optimization/97315
            * gimple-ssa-evrp.c (hybrid_folder::choose_value): Removes the
            trap and instead annotates the listing.

    gcc/testsuite/ChangeLog:

            * gcc.dg/pr97315-1.c: New test.

[Bug tree-optimization/97315] [11 Regression] ICE in choose_value, at gimple-ssa-evrp.c:282 since r11-3690-gebc77ce3a4c70730b4e38d68f88693eadbdc8712

[cvs-commit at gcc dot gnu.org]

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

--- Comment #12 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:91ae6930ed4a87d7b8e25e10378388b3f0dc1729

commit r11-3718-g91ae6930ed4a87d7b8e25e10378388b3f0dc1729
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Thu Oct 8 11:33:30 2020 +0200

    Fix PR97315 (part 2 of 2)

    gcc/ChangeLog:

            PR tree-optimization/97315
            * range-op.cc (value_range_with_overflow): Change any
            non-overflow calculation in which both bounds are
            overflow/underflow to be undefined.

    gcc/testsuite/ChangeLog:

            * gcc.dg/pr97315-2.c: New test.

[Bug tree-optimization/97315] [11 Regression] ICE in choose_value, at gimple-ssa-evrp.c:282 since r11-3690-gebc77ce3a4c70730b4e38d68f88693eadbdc8712

[aldyh at gcc dot gnu.org]

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

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

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

--- Comment #13 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
Fixed.