[Bug tree-optimization/55936] New: Missed VRP optimization

[Bug tree-optimization/55936] New: Missed VRP optimization

[law at redhat dot com]

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

             Bug #: 55936
           Summary: Missed VRP optimization
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: law@redhat.com


gcc.dg/tree-ssa/vrp06.c looks like:

foo (int i, int j, int a)
{
  if (i >= 10)
    if (i <= 30)
      if (i == j)
        {
          a--;

          /* This should fold to 'if (0)'.  */
          if (i < 0)
            i = baz ();

          /* This should fold to 'if (1)'.  */
          if (j > 0)
            a--;

          /* This should fold to 'if (0)'.  */
          if (i != j)
            return 0;
        }

  return i + a + j;
}


VRP is supposed to optimize away the 3 innermost conditions in a single pass;
the key being to realize that the test i < 0 is always false and thus i does
not vary (nor does j vary).  Once i & j are determined to have non-varying
values, we should be able to optimize away the i != j test because we're in the
true clause if the i == j test.

Unfortunately, VRP drops i to varying and it's unable to optimize away the last
test during the first VRP pass.  It does get optimized later.

[Bug tree-optimization/55936] Missed VRP optimization

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2013-01-11
         AssignedTo|unassigned at gcc dot       |rguenth at gcc dot gnu.org
                   |gnu.org                     |
     Ever Confirmed|0                           |1
      Known to fail|                            |4.6.4, 4.7.2, 4.8.0

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> 2013-01-11 10:48:08 UTC ---
Confirmed.  We should see that i = baz () is not executed.

Visiting conditional with predicate: if (i_22 < 0)

With known ranges
        i_22: [j_12(D), j_12(D)]  EQUIVALENCES: { i_9(D) j_12(D) i_24 i_26 } (4
elements)

Predicate evaluates to: DON'T KNOW

that result happens because i_22 was computed as

Visiting statement:
i_22 = ASSERT_EXPR <i_24, i_24 == j_12(D)>;

Intersecting
  [j_12(D), j_12(D)]  EQUIVALENCES: { i_9(D) j_12(D) i_24 i_26 } (4 elements)
and
  [10, 30]  EQUIVALENCES: { i_9(D) i_26 } (2 elements)
to
  [j_12(D), j_12(D)]  EQUIVALENCES: { i_9(D) j_12(D) i_24 i_26 } (4 elements)
Found new range for i_22: [j_12(D), j_12(D)]

that's correct (equivalences have the [10, 30] range but they are not
checked during predicate evaluation it seems, we could also have
arbitrarily chosen [10, 30] instead of [j_12(D), j_12(D)] here)

This means we compute i as VARYING.

[Bug tree-optimization/55936] [4.6/4.7/4.8 Regression] Missed VRP optimization

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
      Known to work|                            |4.1.2
   Target Milestone|---                         |4.6.4
            Summary|Missed VRP optimization     |[4.6/4.7/4.8 Regression]
                   |                            |Missed VRP optimization

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> 2013-01-11 10:55:19 UTC ---
Worked with at least 4.1.2, thus a regression for which I have a patch.

[Bug tree-optimization/55936] [4.6/4.7/4.8 Regression] Missed VRP optimization

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> 2013-01-11 13:36:29 UTC ---
Patch at http://gcc.gnu.org/ml/gcc-patches/2013-01/msg00592.html even though
it produces way more useful ranges regresses

FAIL: g++.dg/tree-ssa/pr18178.C -std=gnu++98  scan-tree-dump-times vrp1 "if " 1
FAIL: g++.dg/tree-ssa/pr18178.C -std=gnu++11  scan-tree-dump-times vrp1 "if " 1

because for asserts:

Visiting statement:
i_18 = ASSERT_EXPR <i_1, i_1 < _5>;

Intersecting
  [-INF, _5 + -1]  EQUIVALENCES: { i_1 } (1 elements)
and
  [0, 1]
to
  [0, 1]  EQUIVALENCES: { i_1 } (1 elements)
Found new range for i_18: [0, 1]

when we do not choose the range 0 as fallback we lose it completely
(there is no equivalence SSA name we can add to the set of equivalences).

Later this causes

 i_19: [0, +INF]  EQUIVALENCES: { i_1 i_18 } (2 elements)
...
-_21: [i_18 + 1, +INF]  EQUIVALENCES: { _5 } (1 elements)
+_21: [1, +INF]  EQUIVALENCES: { _5 } (1 elements)
...
 Folding statement: if (i_19 >= _21)
-Folding predicate i_19 >= _21 to 0
-Folded into: if (0 != 0)
-
+Not folded

as we can fold i_18 >= i_18 + 1 orginally.

Leaving for 4.9, as fixing this requires equivalence reorg or use of
one of the equivalences when propagating (which is problematic as
the comment in vrp_visit_cond_stmt suggests).

[Bug tree-optimization/55936] [4.6/4.7/4.8/4.9 Regression] Missed VRP optimization

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org
   Target Milestone|4.6.4                       |4.9.0
            Summary|[4.6/4.7/4.8 Regression]    |[4.6/4.7/4.8/4.9
                   |Missed VRP optimization     |Regression] Missed VRP
                   |                            |optimization

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-01-15 19:42:10 UTC ---
Deferring for 4.9 then.

[Bug tree-optimization/55936] [4.7/4.8/4.9 Regression] Missed VRP optimization

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Equivalences should instead of refering to SSA names (and their current
value-range) refer to value-ranges (have a hashtable of value-ranges and an
array
we can record indexes of).  Equivalences should be added exclusively by
intersect_ranges when that doesn't produce a precise result.

Alternatively as a hack to preserve the assert range we could add an
SSA name temporarily to hold it and equivalence to that.

[Bug tree-optimization/55936] [4.7/4.8/4.9 Regression] Missed VRP optimization

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2

[Bug tree-optimization/55936] [4.7/4.8/4.9/4.10 Regression] Missed VRP optimization

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.9.0                       |4.9.1

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.0 has been released

[Bug tree-optimization/55936] [4.8/4.9/4.10 Regression] Missed VRP optimization

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.9.1                       |4.9.2

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.1 has been released.

[Bug tree-optimization/55936] [4.8/4.9/5 Regression] Missed VRP optimization

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.9.2                       |4.9.3

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.2 has been released.

[Bug tree-optimization/55936] [4.9/5/6 Regression] Missed VRP optimization

[jakub at gcc dot gnu.org]

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

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.3 has been released.

[Bug tree-optimization/55936] [4.9/5/6 Regression] Missed VRP optimization

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.9.3                       |4.9.4