This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: missed optimization: transforming while(n>=1) into if(n>=1)


On 05/21/2011 08:07 AM, Matt Turner wrote:
I suppose this is a missed optimization. Is this known, or should I
make a new bug report?

It's always better to do that. In this case, the bug is that when we compute a range from an ASSERT_EXPR, and the base variable has a known but symbolic range, we do not try replacing the known range of the symbolic operands:


n_28 = ASSERT_EXPR <n_3, n_3 <= 1>;

Found new range for n_28: [-INF, 1]

...

Visiting PHI node: n_7 = PHI <n_28(10)>

n_7: [-INF, 1]

...

Visiting PHI node: n_4 = PHI <n_7(7), n_20(6)>

Found new range for n_4: [-INF, n_7]

...

And then in the body of the loop:

n_29 = ASSERT_EXPR <n_4, n_4 > 0>;

Found new range for n_29: [1, +INF]

This should have been the intersection of [-INF, 1] and [1, +INF], i.e. 1. Note that this has a chain effect: n_20 is n_29 - 1, so it will get a range of [0, 0]. Then, n_4 will get a range of [-INF, 1] too instead of the symbolic range.

Something like the attached untested patch should fix it...

Paolo
Index: tree-vrp.c
===================================================================
--- tree-vrp.c	(revision 169877)
+++ tree-vrp.c	(working copy)
@@ -718,6 +718,34 @@ vrp_bitmap_equal_p (const_bitmap b1, con
 	      && bitmap_equal_p (b1, b2)));
 }
 
+
+/* Try to replace the extreme values of the symbolic range VR with numeric
+   values from the ranges of the symbol referenced therein.  Place the
+   new range in NEW_VR, and return whether it is still symbolic.  */
+
+static bool
+resolve_symbolic_range (value_range_t *new_vr, value_range_t *vr)
+{
+  new_vr = *vr;
+  if (vr->type != VR_RANGE)
+    return false;
+
+  while (!is_gimple_min_invariant (new_vr->min))
+    {
+      value_range_t *min_vr = get_value_range (new_vr->min);
+      if (min_vr->type == VR_RANGE)
+        new_vr->min = min_vr->min;
+    }
+  while (!is_gimple_min_invariant (new_vr->max))
+    {
+      value_range_t *max_vr = get_value_range (new_vr->max);
+      if (max_vr->type == VR_RANGE)
+        new_vr->max = max_vr->max;
+    }
+
+  return symbolic_range_p (new_vr);
+}
+
 /* Update the value range and equivalence set for variable VAR to
    NEW_VR.  Return true if NEW_VR is different from VAR's previous
    value.
@@ -1444,6 +1472,7 @@ extract_range_from_assert (value_range_t
 {
   tree var, cond, limit, min, max, type;
   value_range_t *var_vr, *limit_vr;
+  value_range_t var_tmp_vr, limit_tmp_vr;
   enum tree_code cond_code;
 
   var = ASSERT_EXPR_VAR (expr);
@@ -1492,10 +1521,15 @@ extract_range_from_assert (value_range_t
 
   /* LIMIT's range is only interesting if it has any useful information.  */
   if (limit_vr
-      && (limit_vr->type == VR_UNDEFINED
-	  || limit_vr->type == VR_VARYING
-	  || symbolic_range_p (limit_vr)))
+      && (limit_vr->type == VR_UNDEFINED || limit_vr->type == VR_VARYING))
     limit_vr = NULL;
+  else if (limit_vr && symbolic_range_p (limit_vr))
+    {
+      if (resolve_symbolic_range (&limit_tmp_vr, limit_vr))
+        limit_vr = &limit_tmp_vr;
+      else
+        limit_vr = NULL;
+    }
 
   /* Initially, the new range has the same set of equivalences of
      VAR's range.  This will be revised before returning the final
@@ -1737,9 +1771,15 @@ extract_range_from_assert (value_range_t
       || vr_p->type == VR_UNDEFINED
       || var_vr->type == VR_VARYING
       || var_vr->type == VR_UNDEFINED
-      || symbolic_range_p (vr_p)
-      || symbolic_range_p (var_vr))
-    return;
+      || symbolic_range_p (vr_p))
+     return;
+  if (symbolic_range_p (var_vr))
+    {
+      if (resolve_symbolic_range (&var_tmp_vr, var_vr))
+        var_vr = &var_tmp_vr;
+      else
+        return;
+    }
 
   if (var_vr->type == VR_RANGE && vr_p->type == VR_RANGE)
     {

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]