[Bug tree-optimization/98026] New: optimization dependant on condition order

[Bug tree-optimization/98026] New: optimization dependant on condition order

[denis.campredon at gmail dot com]

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

            Bug ID: 98026
           Summary: optimization dependant on condition order
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: denis.campredon at gmail dot com
  Target Milestone: ---

In all the following functions gcc should recognize that j can't be greater
than 100, and link_error should not appear in assembly. Currently only f3 is
optimized.


-------------------
void link_error();

void f1(int i, int j) {
  if (j > i || i > 100) return;

  if (j > 100) link_error();
}

void f2(int i, int j) {
  if (i > 100 || j > i) return;

  if (j > 100) link_error();
}

void f3(int i, int j) {
  if (i > 100) return;
  if (j > i) return;

  if (j > 100) link_error();
}

void f4(signed int i,unsigned int j) {
  if (i > 100) return;
  if (j > i) return;

  if (j > 100) link_error();
}
------------------

[Bug tree-optimization/98026] optimization dependant on condition order

[rguenth at gcc dot gnu.org]

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

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> ---
This is because symbolic range handling sometimes throws away the symbolic
equivalence I think.  OTOH we have equivalences for this (but they are not
always used, and with ranger all but the symbolic cases can be handled with
multi-entry ranges)


Referenced Bugs:

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

[Bug tree-optimization/98026] optimization dependant on condition order

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
     Ever confirmed|0                           |1
           Severity|normal                      |enhancement
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-07-19

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed. I Noticed that LLVM does not even optimize f3.

[Bug tree-optimization/98026] optimization dependant on condition order

[amacleod at redhat dot com]

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

Andrew Macleod <amacleod at redhat dot com> changed:

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

--- Comment #3 from Andrew Macleod <amacleod at redhat dot com> ---
Although we are now adding relations for these expressions, onc extension we
have not gotten to apply ranges of relations. ie:


    <bb 2> :
    _1 = j_5(D) > i_6(D);
    _2 = i_6(D) > 100;
    _3 = _1 | _2;
    if (_3 != 0)
      goto <bb 3>; [INV]
    else
      goto <bb 4>; [INV]

2->3  (T) _3 :  bool [1, 1]
2->4  (F) _1 :  bool [0, 0]
2->4  (F) _2 :  bool [0, 0]
2->4  (F) _3 :  bool [0, 0]
2->4  (F) i_6(D) :      int [-INF, 100]

Relational : (j_5(D) <= i_6(D))
    <bb 4> :
    if (j_5(D) > 100)
      goto <bb 5>; [INV]
    else
      goto <bb 6>; [INV]

4->5  (T) j_5(D) :      int [101, +INF]
4->6  (F) j_5(D) :      int [-INF, 100]

We know that j_5 is <= i_6 on the edge 2->4, but we do not apply any known
range of i_6 to j_5.

We do transitive between symbolics, ie (j < x &&  x < y means j < y)
We do not yet do that with a range as this requires. ie:
  j_5 <= i_6,  i_6 <= 100  means j <= 100

This will be an enhancement for the next release.

[Bug tree-optimization/98026] optimization dependant on condition order

[amacleod at redhat dot com]

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

--- Comment #4 from Andrew Macleod <amacleod at redhat dot com> ---

> void f4(signed int i,unsigned int j) {
>   if (i > 100) return;
>   if (j > i) return;
> 
>   if (j > 100) link_error();

if i is -2 (0xfffffffe) and j is 0xffffffffff (-1)

then link error cant be removed.. ?

[Bug tree-optimization/98026] optimization dependant on condition order

[amacleod at redhat dot com]

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

--- Comment #5 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Andrew Macleod from comment #4)
> > void f4(signed int i,unsigned int j) {
> >   if (i > 100) return;
> >   if (j > i) return;
> > 
> >   if (j > 100) link_error();
> 
> if i is -2 (0xfffffffe) and j is 0xffffffffff (-1)
> 
> then link error cant be removed.. ?

err, j is 0xfffffffd (-3) you get the idea :-)

Friday evenings are killer for logic and bit patterns...