[Bug tree-optimization/99755] New: failure to fold a conditional that's a subset of another expression

[Bug tree-optimization/99755] New: failure to fold a conditional that's a subset of another expression

[msebor at gcc dot gnu.org]

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

            Bug ID: 99755
           Summary: failure to fold a conditional that's a subset of
                    another expression
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: msebor at gcc dot gnu.org
  Target Milestone: ---

GCC successfully folds to false the second conditional expression in f1() but
it fails to do the same in f2() and f3().  In addition (and likely as a
result), it triggers a bogus -Wmaybe-uninitialized in both functions. 

Clang and ICC fold all three expressions to false and emit optimal code for all
three functions.

Initializing the local variable to any value lets GCC fold the conditional and
avoid the warning.  But then, replacing  the test for x != i + 1 in f3() with x
!= 3 as shown at below the first test case, the conditional is again not folded
 (making the same change in f2() allows the folding to take place).

The bogus -Wmaybe-uninitialized first appeared in 4.9.  As far as I can tell
none of the failures to fold is a regression.

$ cat t.c && gcc -O2 -S -Wall t.c
void f1 (int i)
{ 
  int x;
  if (i > 1)
    x = i + 1;

  if (i == 2 && x != i + 1)   // folded to false
    __builtin_abort ();
}

void f2 (int i, int j)
{ 
  int x;
  if (i > 1 && j > 2)
    x = i + 1;

  if (i == 2 && j == 3 && x != i + 1)   // not folded
    __builtin_abort ();
}


void f3 (int i, int j, int k)
{
  int x;
  if (i > 1 && j > 2 && k > 3)
    x = i + 1;

  if (i == 2 && j == 3 && k == 4 && x != i + 1)   // not folded
    __builtin_abort ();
}


;; Function f1 (f1, funcdef_no=0, decl_uid=1943, cgraph_uid=1, symbol_order=0)

void f1 (int i)
{
  <bb 2> [local count: 1073741824]:
  return;

}
t.c: In function ‘f2’:
t.c:17:24: warning: ‘x’ may be used uninitialized in this function
[-Wmaybe-uninitialized]
   17 |   if (i == 2 && j == 3 && x != i + 1)
      |       ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
t.c: In function ‘f3’:
t.c:28:34: warning: ‘x’ may be used uninitialized in this function
[-Wmaybe-uninitialized]
   28 |   if (i == 2 && j == 3 && k == 4 && x != i + 1)
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~


The following is also not folded:

void f3 (int i, int j, int k)
{ 
  int x = 0;
  if (i > 1 && j > 2 && k > 3)
    x = i + 1;

  if (i == 2 && j == 3 && k == 4 && x != 3)   // not folded
    __builtin_abort ();
}

[Bug tree-optimization/99755] failure to fold a conditional that's a subset of another expression

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Blocks|                            |85316
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-03-25

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.  We have no good notion of predicate combinations, their "range" or
how other ranges depend on predicates.

It would be interesting to see how LLVM arrives at a folded f2().


Referenced Bugs:

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

[Bug tree-optimization/99755] failure to fold a conditional that's a subset of another expression

[amacleod at redhat dot com]

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

Andrew Macleod <amacleod at redhat dot com> changed:

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

--- Comment #2 from Andrew Macleod <amacleod at redhat dot com> ---
f2 and f4 are "similar" when I look at whats going on with these.

The interesting bits are  bb3 and bb4

=========== BB 3 ============
i_9(D)  int [2, +INF]
j_10(D) int [3, +INF]
Relational : (x_12 > i_9(D))
    <bb 3> :
    x_12 = i_9(D) + 1;

x_12 : int [3, +INF]


=========== BB 4 ============
Imports: i_9(D)  j_10(D)
Exports: _4  _5  _6  i_9(D)  j_10(D)
         _4 : i_9(D)(I)
         _5 : j_10(D)(I)
         _6 : _4  _5  i_9(D)(I)  j_10(D)(I)
i_9(D)  int VARYING
j_10(D) int VARYING
    <bb 4> :
    # x_8 = PHI <x_11(D)(2), x_12(3)>
    _4 = i_9(D) == 2;
    _5 = j_10(D) == 3;
    _6 = _4 & _5;
    if (_6 != 0)
      goto <bb 5>; [INV]
    else
      goto <bb 7>; [INV]

x_8 : int [3, +INF]
4->5  (T) _4 :  _Bool [1, 1]
4->5  (T) _5 :  _Bool [1, 1]
4->5  (T) _6 :  _Bool [1, 1]
4->5  (T) i_9(D) :      int [2, 2]
4->5  (T) j_10(D) :     int [3, 3]
4->7  (F) _6 :  _Bool [0, 0]

we have the ability to recompute stmts on edges when the dependencies change.
This currently applies only to range-ops enabled stmts.  An extension to PHIS
and other non-range-ops is in the works.


The gist being x_8 is directly dependant on x_11 and x_12.  x_11 is undefined,
so it boils down to a dependency on x_12.

x_12 in turn is dependant on i_9 which is a modified export from this block. 
So when recomputation is extended to PHIS, we should be able to see that i_9
has changed on this edge, and reevaluate x_12 for that edge,
   x_12 = i_9 + 1 -->  [2,2] + 1 == [3,3] 
and feeding that into a PHI recalculation for the edge producing
 x_8 = PHI <x_11(D), [3,3]>
and then we'd resolve x_8 = [3,3] on the true edge, and the desired fold should
happen. 

The other issue is that when we do recalculations, we currently only go back
one degree of dependency for the sake of compilation speed...  x_8's direct
dependencies are that one degree..  I have not done experiments on more than
one degree, but it may make sense to look back one degree for phi arguemnts as
well,  which would then get cases like this. 

It may also make sense instead to adjust the phi optimization pass to utilize
ranger to do a more in-depth analysis of argument ranges and their dependencies
and get it there. 

I'll update this once I have enabled recomputation for phis, and have something
more concrete.

[Bug tree-optimization/99755] failure to fold a conditional that's a subset of another expression

[amacleod at redhat dot com]

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

--- Comment #3 from Andrew Macleod <amacleod at redhat dot com> ---
we now know the PHI is an equivalence when the other argument is UNDEFINED.:
    <bb 4> [local count: 268435456]:
    x_12 = i_8(D) + 1;

x_12 : int [3, +INF]

Equivalence set : [x_7, x_12]                <<--Equivalence marked   
    <bb 5> [local count: 805306367]:
    # x_7 = PHI <x_10(D)(2), x_12(4)>
    _4 = i_8(D) == 2;
    _5 = j_9(D) == 3;
    _15 = k_11(D) == 4;
    _21 = _5 & _15;
    _16 = _4 & _21;
    _17 = x_7 != 3;
    _18 = _16 & _17;
    if (_18 != 0)
      goto <bb 6>; [0.00%]
    else
      goto <bb 7>; [100.00%]

x_7 : int [3, +INF]
5->6  (T) _4 :  _Bool [1, 1]
5->6  (T) _5 :  _Bool [1, 1]
5->6  (T) x_7 :         int [4, +INF]
5->6  (T) i_8(D) :      int [2, 2]
5->6  (T) j_9(D) :      int [3, 3]

Whats missing is potentially recalculating equivalences on outgoing edges.
we know 
  1) i_8 has a range of [2,2] on the edge 5->6
  2) we know that x_7 and x_12 are equivalences
  3) we know that x_12 = i_8(D) + 1;
  4) We have the ability to recompute x_12 using i_8 on that edge, which would 
conclude x_12 = [3,3] on that edge.  We just don't know to ask that question
(yet).
  5) the equivalence set of x_12=[3, 3] and x_7=[4, +INF] are incompatible.
their intersection is EMPTY, which in turns means the edge is unexecutable.

This is demonstrated by the requirement that x_7 != 3 be true, as well as (x_7
== x_12 == [3,3]) at the same time.

The information is all there, we just need to figure out how best to use it.