Bug 25145 - missed VRP opportunity
Summary: missed VRP opportunity
Status: RESOLVED WORKSFORME
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.2.0
: P3 enhancement
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords: missed-optimization
Depends on: 25148
Blocks:
  Show dependency treegraph
 
Reported: 2005-11-28 19:00 UTC by Andrew Pinski
Modified: 2011-08-09 14:28 UTC (History)
2 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2007-07-01 00:54:04


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Andrew Pinski 2005-11-28 19:00:21 UTC
Take the following example:
int f(int i, int j)
{
  if (i <= j - 1)
    if (i >= 0)
    {
        return i >= j;
    }
  return 0;
}

Note this might show up somewhere but I don't know if it actually does (I made this up while looking into some missed optimizations due the patch which fixes PR 23666).

The problem if I am looking at this correctly is that:
Visiting statement:
D.1631_3 = j_2 - 1;

Found new range for D.1631_3: VARYING

we say the range for D.1631_3 is varying but shouldn't we say the range is [j_2 - 1, j_2 - 1] ?

That should fix the issue as we then we get the upper bound correctly as shown by:
int f(int i, int j)
{
  if (i < j)
    if (i >= 0)
    {
        return i >= j;
    }
  return 0;
}

Note as I said before, I don't know how many times this shows but I don't doubt that people would write i <= j -1 instead of i < j all the time to show what it really does for integers and loops.
Comment 1 Andrew Pinski 2005-11-28 22:56:48 UTC
Even the simple code like:
int f(int i, int j )
{
   int k;
   k = i+ - 1;
   return k < i;
}

Does not get VRP to optimize it which means we don't do that much symbolic ranges as we should.  From looking at things, the only time we get a symbolic range is from scev and never make it ourselves which seems wrong.
Comment 2 Andrew Pinski 2005-11-28 23:43:18 UTC
extract_range_from_binary_expr should do symbolic ranges for stuff like this (or at least it seems like it should).
Comment 3 Andrew Pinski 2005-11-29 00:21:21 UTC
This needs PR 25148 fixed to do the correct thing for comment #1 as we get the wrong answer for a + -1 < a, we get false when we should get true.
Comment 4 Andrew Pinski 2005-11-29 00:34:30 UTC
I run into a different regression if we try to compile the first example in comment #0.
Comment 5 Andrew Pinski 2005-11-29 00:38:09 UTC
Note this was the simple fix which exposes those latent bugs as far as I can see that should work, we get the correct range but the rest of VRP goes bonkers:
Index: tree-vrp.c
===================================================================
--- tree-vrp.c  (revision 107604)
+++ tree-vrp.c  (working copy)
@@ -1226,7 +1226,14 @@ extract_range_from_binary_expr (value_ra
       || symbolic_range_p (&vr0)
       || symbolic_range_p (&vr1))
     {
-      set_value_range_to_varying (vr);
+      if ((code != PLUS_EXPR
+           && code != MINUS_EXPR)
+          || !is_gimple_min_invariant (op1))
+       set_value_range_to_varying (vr);
+      else
+       {
+         set_value_range (vr, VR_RANGE, expr, expr, NULL);
+       }
       return;
     }
 
Comment 6 Andrew Pinski 2005-11-29 17:34:49 UTC
(In reply to comment #5)
> Note this was the simple fix which exposes those latent bugs as far as I can
> see that should work, we get the correct range but the rest of VRP goes
> bonkers:

I should also note it does not do the correct thing for -fwrapv either.
For the testcase in comment #1:
int f(int i, int j )
{
   int k;
   k = i+ - 1;
   return k < i;
}

i = INT_MIN
k will equal INT_MAX so the comparision will be wrong to return true as INT_MAX is not less than INT_MIN.

VRP does not like symbolic ranges at all.
Comment 7 Andrew Pinski 2005-12-12 21:01:16 UTC
Confirmed.
Comment 8 Richard Biener 2006-04-26 16:09:06 UTC
Now the patch for 25148 fixes the wrong answer for the testcase in comment #2 if the patch in comment #5 is applied.  It needs

Index: tree-ssa-propagate.c
===================================================================
*** tree-ssa-propagate.c        (revision 113273)
--- tree-ssa-propagate.c        (working copy)
*************** substitute_and_fold (prop_value_t *prop_
*** 1127,1133 ****
          if (use_ranges_p)
            did_replace = fold_predicate_in (stmt);
  
!         if (prop_value)
            {
              /* Only replace real uses if we couldn't fold the
                 statement using value range information (value range
--- 1127,1134 ----
          if (use_ranges_p)
            did_replace = fold_predicate_in (stmt);
  
!         if (prop_value
!             && is_gimple_val (prop_value))
            {
              /* Only replace real uses if we couldn't fold the
                 statement using value range information (value range

though to not ICE for -fwrapv.  Also the patches don't handle the testcase
in comment #1.
Comment 9 Richard Biener 2006-12-28 12:14:13 UTC
The testcase in comment #1 is fixed by comparison canonicalization of i <= j - 1
to i < j.  Of course it fails again if we use a temporary for j - 1 like in the
testcases in other comments.

Comment 10 Richard Biener 2008-01-12 13:05:26 UTC
The first testcase in the original report is fixed by comparison canonicalization,
even if a temporary is used (forwprop re-instantiates the canonicalized comparison).

The testcase in comment #1 is fixed by FRE simplifying binary expressions:
Value numbering D.1178_3 stmt = D.1178_3 = k_2 < i_1(D);
RHS k_2 < i_1(D) simplified to 1 has constants 0


So none of the testcases is useful to show missing optimizations in VRP anymore.
Comment 11 Richard Biener 2011-08-09 14:28:14 UTC
Thus, closing.  VRP isn't the best place to deal with symbolic ranges anyway.