[Bug tree-optimization/42117] New: VRP fails to get rid of compares

[Bug tree-optimization/42117] New: VRP fails to get rid of compares

[krebbel at gcc dot gnu dot org]

The vrp47 testcase currently fails on i386 and S/390.  The ssa code before vrp
looks different for both compared to x86_64 due to a different value
returned by BRANCH_COST. (Branches on S/390 are relatively cheap due
to a sophisticated branch prediction unit.)  Therefore during
gimplification fold_truthop (line 5866) uses more branches for
function h in vrp47.c than the x86_64 variant.
The problem can also be reproduced on x86 when compiling for a cpu with low
branch costs defined in i386.c as e.g. -march=i386.

int h(int x, int y)
{
  if ((x >= 0 && x <= 1) && (y >= 0 && y <= 1))
    return x && y;
  else
    return -1;
}

Compile the testcase above with:
cc1 -m32 -O2 vrp47.c -fdump-tree-vrp -march=i386

The vrp pass is not able to get rid of the comparisons in this case
(069t.vrp1 from i386):

h (int x, int y)
{
  int D.2021;
  unsigned int y.1;
  unsigned int x.0;

<bb 2>:
  x.0_4 = (unsigned int) x_3(D);
  if (x.0_4 <= 1)
    goto <bb 3>;
  else
    goto <bb 7>;

<bb 3>:
  y.1_6 = (unsigned int) y_5(D);
  if (y.1_6 <= 1)
    goto <bb 4>;
  else
    goto <bb 7>;

<bb 4>:
  if (x_3(D) != 0)
    goto <bb 5>;
  else
    goto <bb 6>;

<bb 5>:
  if (y_5(D) != 0)
    goto <bb 7>;
  else
    goto <bb 6>;

<bb 6>:

<bb 7>:
  # D.2021_1 = PHI <0(6), -1(3), -1(2), 1(5)>
  return D.2021_1;

}


-- 
           Summary: VRP fails to get rid of compares
           Product: gcc
           Version: 4.5.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: krebbel at gcc dot gnu dot org
 GCC build triplet: i386-gnu-linux, s390x-ibm-linux
  GCC host triplet: i386-gnu-linux, s390x-ibm-linux
GCC target triplet: i386-gnu-linux, s390x-ibm-linux


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42117

[Bug tree-optimization/42117] VRP should do if-conversion

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2009-11-20 13:12 -------
Confirmed.  We do see

x_2: [0, 1]  EQUIVALENCES: { x_3(D) } (1 elements)
y_11: [0, 1]  EQUIVALENCES: { y_5(D) } (1 elements)

but have no code that actually makes use of this information in

<bb 4>:
  if (x_3(D) != 0)
    goto <bb 5>;
  else
    goto <bb 6>;

<bb 5>:
  if (y_5(D) != 0)
    goto <bb 7>;
  else
    goto <bb 6>;

<bb 6>:

<bb 7>:
  # D.2047_1 = PHI <0(6), -1(3), -1(2), 1(5)>
  return D.2047_1;

which we want to if-convert to

<bb 4>:
  tmp = x_3 & y_5;

<bb 7>:
  # D.2047_1 = PHI <tmp(4), -1(3), -1(2)>

but there is no code in VRP that does if-conversion.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2009-11-20 13:12:34
               date|                            |
            Summary|VRP fails to get rid of     |VRP should do if-conversion
                   |compares                    |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42117

[Bug tree-optimization/42117] VRP should do if-conversion

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So I think VRP is almost there on the trunk, it just needs to know if you have
a range of a and that a is defined by b|c, then b and c ranges can be just the
same as a.
That is:
    _10 = x_5(D) | y_6(D);
    _11 = (unsigned int) _10;
    if (_11 <= 1)
      goto <bb 3>; [57.43%]
    else
      goto <bb 4>; [42.57%]

2->3  (T) _10 :         [irange] int [0, 1] NONZERO 0x1
2->3  (T) _11 :         [irange] unsigned int [0, 1] NONZERO 0x1
2->4  (F) _10 :         [irange] int [-INF, -1][2, +INF]
2->4  (F) _11 :         [irange] unsigned int [2, +INF]

We should have done:
2->3 (T) x_5(D) :       [irange] int [0, 1] NONZERO 0x1
2->3 (T) y_6(D) :       [irange] int [0, 1] NONZERO 0x1
...

This is only true for bit_ior.

[Bug tree-optimization/42117] VRP should do if-conversion

[pinskia at gcc dot gnu.org]

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

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

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

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I am not going to fix this.
But right now we get:
  _8 = x_5(D) | y_6(D);
  _4 = (unsigned int) _8;
  if (_4 <= 1)
    goto <bb 3>; [57.43%]
  else
    goto <bb 5>; [42.57%]

  <bb 3> [local count: 616649929]:
  if (x_5(D) != 0)
    goto <bb 4>; [50.00%]
  else
    goto <bb 5>; [50.00%]

  <bb 4> [local count: 126413234]:
  _9 = y_6(D) != 0;
  _1 = (int) _9;

  <bb 5> [local count: 1073741824]:
  # _3 = PHI <x_5(D)(3), _1(4), -1(2)>

Part of the problem is realizing y_6 is [0,1] range when looking at _9/_1.


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=42195
[Bug 42195] missed xnor optimization.

[Bug tree-optimization/42117] VRP should do if-conversion

[pinskia at gcc dot gnu.org]

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

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

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Mine, I will take a look.