[Bug tree-optimization/101186] New: predictable comparison of integer variables not folded

[Bug tree-optimization/101186] New: predictable comparison of integer variables not folded

[dizhao at os dot amperecomputing.com]

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

            Bug ID: 101186
           Summary: predictable comparison of integer variables not folded
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: dizhao at os dot amperecomputing.com
  Target Milestone: ---

GCC fail to remove dead codes for following cases:

#include <stdio.h>

void f (unsigned int a, unsigned int b, unsigned int c)
// if a,b,c are signed, VRP can remove dead code
{
  if (a == b)
    {
      printf ("a");
      if (c < a)
        {
          printf ("b");
          if (c >= b)
            printf ("Unreachable!");
        }
    }
}

void g (int a, int b, int x, int y)
{
  int c = y;
  if (a != 0)
    c = x;
  while (b < 1000)
  // without this loop, jump thread & VRP can remove dead code
    {
      if (a != 0)
        {
          if (c > x)
            printf ("Unreachable!");
        }
      else
        printf ("a\n");
      b++;
    }
}

[Bug tree-optimization/101186] predictable comparison of integer variables not folded

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement
           Keywords|                            |missed-optimization

[Bug tree-optimization/101186] predictable comparison of integer variables not folded

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Blocks|                            |85316

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
The complication is that the a == b equivalence has to be taken into account to
relate the c < a and c >= b relations.

Maybe the new relation code can do sth here, but confirmed on trunk.

void g (int a, int b, int x, int y)
{
  int c = y;
  if (a != 0)
    c = x;
  while (b < 1000)
  // without this loop, jump thread & VRP can remove dead code
    {
      if (a != 0)
        {
          if (c > x)
            printf ("Unreachable!");
        }

that's also a classical example for predicated value-numbering (which we
don't implement).


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85316
[Bug 85316] [meta-bug] VRP range propagation missed cases

[Bug tree-optimization/101186] predictable comparison of integer variables not folded

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2021-06-24

[Bug tree-optimization/101186] predictable comparison of integer variables not folded

[dizhao at os dot amperecomputing.com]

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

--- Comment #2 from Di Zhao <dizhao at os dot amperecomputing.com> ---
(In reply to Richard Biener from comment #1)
> The complication is that the a == b equivalence has to be taken into account
> to relate the c < a and c >= b relations.
> 
> Maybe the new relation code can do sth here, but confirmed on trunk.
> 
> void g (int a, int b, int x, int y)
> {
>   int c = y;
>   if (a != 0)
>     c = x;
>   while (b < 1000)
>   // without this loop, jump thread & VRP can remove dead code
>     {
>       if (a != 0)
> 	{
> 	  if (c > x)
> 	    printf ("Unreachable!");
> 	}
> 
> that's also a classical example for predicated value-numbering (which we
> don't implement).

I've implemented a patch on FRE regarding this and will send it to patches
mailing list soon. 

Thanks

[Bug tree-optimization/101186] predictable comparison of integer variables not folded

[amacleod at redhat dot com]

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

Andrew Macleod <amacleod at redhat dot com> changed:

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

--- Comment #3 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Di Zhao from comment #0)
> GCC fail to remove dead codes for following cases:
> 
> #include <stdio.h>
> 
> void f (unsigned int a, unsigned int b, unsigned int c)
> // if a,b,c are signed, VRP can remove dead code
> {
>   if (a == b)
>     {
>       printf ("a");
>       if (c < a)
> 	{
> 	  printf ("b");
> 	  if (c >= b)
> 	    printf ("Unreachable!");
> 	}
>     }
> }
> 
I believe this commit fixes the first case, EVRP now eliminates the unreachable
print.


commit ce0b409f562cd09c67cc2dce74143a0f0647cde5 (origin/master, origin/HEAD)
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Thu Jun 24 11:13:47 2021 -0400

    Fix relation query of equivalences.

the second one requires some form of predication, or the desire to thread thru
the top of the block.. It touches on some stuff Aldy is looking at (which isn't
finished yet) .


<bb 2> :
  if (a_7(D) != 0)
    goto <bb 3>; [INV]
  else
    goto <bb 9>; [INV]

  <bb 3> :
  goto <bb 9>; [INV]

  <bb 9> :
  # c_16 = PHI <x_10(D)(3), y_5(D)(2)>

  <bb 10> :
  # b_1 = PHI <b_8(D)(9), b_14(8)>
  if (b_1 <= 999)
    goto <bb 4>; [INV]
  else
    goto <bb 11>; [INV]

  <bb 4> :
  if (a_7(D) != 0)
    goto <bb 5>; [INV]
  else
    goto <bb 7>; [INV]

  <bb 5> :
  if (x_10(D) < c_16)
    goto <bb 6>; [INV]
  else
    goto <bb 8>; [INV]

 I dont know what rules there are, but the path 2->3->9->10->4  would result in
bb4 becoming "goto bb5", and then BB5 could fold to "goto bb8" as c_16 == x_10
on that path in BB9.

[Bug tree-optimization/101186] predictable comparison of integer variables not folded

[aldyh at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |jeffreyalaw at gmail dot com

--- Comment #4 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
To give a little more context, the IL at thread1 looks like this:

  <bb 3> [local count: 59055800]:
  goto <bb 9>; [100.00%]

  <bb 4> [local count: 955630225]:
  if (a_5(D) != 0)
    goto <bb 5>; [67.00%]
  else
    goto <bb 7>; [33.00%]

  <bb 5> [local count: 640272253]:
  if (x_8(D) < c_12)
    goto <bb 6>; [33.00%]
  else
    goto <bb 8>; [67.00%]

  <bb 6> [local count: 211289842]:
  unreachable ();
  goto <bb 8>; [100.00%]

  <bb 7> [local count: 315357972]:
  blah ();

  <bb 8> [local count: 955630227]:
  b_11 = b_1 + 1;
  goto <bb 10>; [100.00%]

  <bb 9> [local count: 118111600]:
  # c_12 = PHI <x_8(D)(3), y_4(D)(2)>

  <bb 10> [local count: 1073741824]:
  # b_1 = PHI <b_6(D)(9), b_11(8)>
  if (b_1 <= 999)
    goto <bb 4>; [89.00%]
  else
    goto <bb 11>; [11.00%]

The path from 3->9->10->4->5 could *theoretically* resolve the conditional in
BB5.  If this were a permissible jump threading path, the threader would
replace the conditional in BB5 into a jump to BB8, thus eliding the
unreachable.

However, BB9->BB10 would cross loop boundaries which is not permitted in the
backwards threader.  Specifically, the threading candidate conditional is BB5,
which is in a loop:

;; Loop 1
;;  header 10, latch 8
;;  depth 1, outer 0
;;  nodes: 10 8 6 7 5 4 (<-- note BB5 & BB10 in here)

And BB9 is outside said loop.

See path_crosses_loops in tree-ssa-threadbackward.c as well as handle_phi()
where we specifically skip PHI edges pointing outside the current loop.

Note that even though my upcoming rewrite of the backward threader does not use
the relational oracle, Andrew says it would be trivial to do so.  In which
case, we *could* resolve the above path, but would still fail to thread it
because it crosses a loop boundary.

Perhaps Jeff can opine on whether the path duplicator in the threader back-end,
could be taught to thread through loops.

[Bug tree-optimization/101186] predictable comparison of integer variables not folded

[aldyh at gcc dot gnu.org]

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

--- Comment #5 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
Sorry for the slightly different IL.  I had altered g() to avoid depending on
stdio.h:

void g (int a, int b, int x, int y)
{
  int c = y;
  if (a != 0)
    c = x;
  while (b < 1000)
  // without this loop, jump thread & VRP can remove dead code
    {
      if (a != 0)
        {
          if (c > x)
            unreachable();
        }
      else
        blah();
      b++;
    }
}

[Bug tree-optimization/101186] predictable comparison of integer variables not folded

[law at gcc dot gnu.org]

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

Jeffrey A. Law <law at gcc dot gnu.org> changed:

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

--- Comment #6 from Jeffrey A. Law <law at gcc dot gnu.org> ---
I wonder why we don't unswitch the loop twice to pull both conditionals out. 
If we were to do that, the a != 0 loop versions can be removed because they'll
do nothing other than increase the loop counter.

The a==0 variant will just have the printf and increment of b.

[Bug tree-optimization/101186] predictable comparison of integer variables not folded

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=100063

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I suspect https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100063 is very similar
to this one.