Patchwork propagate anti-range to switch in tree-vrp

login
register
mail settings
Submitter Tom de Vries
Date July 21, 2012, 1:57 p.m.
Message ID <500AB52F.4050108@mentor.com>
Download mbox | patch
Permalink /patch/172432/
State New
Headers show

Comments

Tom de Vries - July 21, 2012, 1:57 p.m.
Jakub,

this patch adds propagation of anti-ranges to switches.

The test-case is this:
...
void
f3 (int s)
{
  if (s >> 3 == -2)
    /* s in range [ -16, -9].  */
    ;
  else
    {
      /* s in range ~[-16, -9], so none of the case labels can be taken.  */
      switch (s)
	{
	case -16:
	case -12:
	case -9:
	  link_error ();
	  break;
	default:
	  break;
	}
    }
}	
...

The call to link_error is unreachable but tree-vrp fails to analyze that.

Using the patch, the switch is replaced by the default case.

Bootstrapped and reg-tested (Ada inclusive) on x86_64.

OK for trunk?

Thanks,
- Tom

2012-07-21  Tom de Vries  <tom@codesourcery.com>

	* tree-vrp.c (find_case_label_ranges): New function.
	(vrp_visit_switch_stmt, simplify_switch_using_ranges): Use
	find_case_label_ranges instead of find_case_label_range.  Handle second
	range.

	* gcc.dg/tree-ssa/vrp72.c: New test.
Richard Guenther - Aug. 1, 2012, 12:42 p.m.
On Sat, Jul 21, 2012 at 3:57 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> Jakub,
>
> this patch adds propagation of anti-ranges to switches.
>
> The test-case is this:
> ...
> void
> f3 (int s)
> {
>   if (s >> 3 == -2)
>     /* s in range [ -16, -9].  */
>     ;
>   else
>     {
>       /* s in range ~[-16, -9], so none of the case labels can be taken.  */
>       switch (s)
>         {
>         case -16:
>         case -12:
>         case -9:
>           link_error ();
>           break;
>         default:
>           break;
>         }
>     }
> }
> ...
>
> The call to link_error is unreachable but tree-vrp fails to analyze that.
>
> Using the patch, the switch is replaced by the default case.
>
> Bootstrapped and reg-tested (Ada inclusive) on x86_64.
>
> OK for trunk?

Ok.

Thanks,
Richard.

> Thanks,
> - Tom
>
> 2012-07-21  Tom de Vries  <tom@codesourcery.com>
>
>         * tree-vrp.c (find_case_label_ranges): New function.
>         (vrp_visit_switch_stmt, simplify_switch_using_ranges): Use
>         find_case_label_ranges instead of find_case_label_range.  Handle second
>         range.
>
>         * gcc.dg/tree-ssa/vrp72.c: New test.

Patch

Index: gcc/tree-vrp.c
===================================================================
--- gcc/tree-vrp.c (revision 189508)
+++ gcc/tree-vrp.c (working copy)
@@ -6736,6 +6736,84 @@  find_case_label_range (gimple stmt, tree
     }
 }
 
+/* Searches the case label vector VEC for the ranges of CASE_LABELs that are
+   used in range VR.  The indices are placed in MIN_IDX1, MAX_IDX, MIN_IDX2 and
+   MAX_IDX2.  If the ranges of CASE_LABELs are empty then MAX_IDX1 < MIN_IDX1.
+   Returns true if the default label is not needed.  */
+
+static bool
+find_case_label_ranges (gimple stmt, value_range_t *vr, size_t *min_idx1,
+			size_t *max_idx1, size_t *min_idx2,
+			size_t *max_idx2)
+{
+  size_t i, j, k, l;
+  unsigned int n = gimple_switch_num_labels (stmt);
+  bool take_default;
+  tree case_low, case_high;
+  tree min = vr->min, max = vr->max;
+
+  gcc_checking_assert (vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE);
+
+  take_default = !find_case_label_range (stmt, min, max, &i, &j);
+
+  /* Set second range to emtpy.  */
+  *min_idx2 = 1;
+  *max_idx2 = 0;
+
+  if (vr->type == VR_RANGE)
+    {
+      *min_idx1 = i;
+      *max_idx1 = j;
+      return !take_default;
+    }
+
+  /* Set first range to all case labels.  */
+  *min_idx1 = 1;
+  *max_idx1 = n - 1;
+
+  if (i > j)
+    return false;
+
+  /* Make sure all the values of case labels [i , j] are contained in
+     range [MIN, MAX].  */
+  case_low = CASE_LOW (gimple_switch_label (stmt, i));
+  case_high = CASE_HIGH (gimple_switch_label (stmt, j));
+  if (tree_int_cst_compare (case_low, min) < 0)
+    i += 1;
+  if (case_high != NULL_TREE
+      && tree_int_cst_compare (max, case_high) < 0)
+    j -= 1;
+
+  if (i > j)
+    return false;
+
+  /* If the range spans case labels [i, j], the corresponding anti-range spans
+     the labels [1, i - 1] and [j + 1, n -  1].  */
+  k = j + 1;
+  l = n - 1;
+  if (k > l)
+    {
+      k = 1;
+      l = 0;
+    }
+
+  j = i - 1;
+  i = 1;
+  if (i > j)
+    {
+      i = k;
+      j = l;
+      k = 1;
+      l = 0;
+    }
+
+  *min_idx1 = i;
+  *max_idx1 = j;
+  *min_idx2 = k;
+  *max_idx2 = l;
+  return false;
+}
+
 /* Visit switch statement STMT.  If we can determine which edge
    will be taken out of STMT's basic block, record it in
    *TAKEN_EDGE_P and return SSA_PROP_INTERESTING.  Otherwise, return
@@ -6746,7 +6824,7 @@  vrp_visit_switch_stmt (gimple stmt, edge
 {
   tree op, val;
   value_range_t *vr;
-  size_t i = 0, j = 0;
+  size_t i = 0, j = 0, k, l;
   bool take_default;
 
   *taken_edge_p = NULL;
@@ -6764,12 +6842,13 @@  vrp_visit_switch_stmt (gimple stmt, edge
       fprintf (dump_file, "\n");
     }
 
-  if (vr->type != VR_RANGE
+  if ((vr->type != VR_RANGE
+       && vr->type != VR_ANTI_RANGE)
       || symbolic_range_p (vr))
     return SSA_PROP_VARYING;
 
   /* Find the single edge that is taken from the switch expression.  */
-  take_default = !find_case_label_range (stmt, vr->min, vr->max, &i, &j);
+  take_default = !find_case_label_ranges (stmt, vr, &i, &j, &k, &l);
 
   /* Check if the range spans no CASE_LABEL. If so, we only reach the default
      label */
@@ -6803,6 +6882,16 @@  vrp_visit_switch_stmt (gimple stmt, edge
 	      return SSA_PROP_VARYING;
 	    }
         }
+      for (; k <= l; ++k)
+        {
+          if (CASE_LABEL (gimple_switch_label (stmt, k)) != CASE_LABEL (val))
+	    {
+	      if (dump_file && (dump_flags & TDF_DETAILS))
+		fprintf (dump_file, "  not a single destination for this "
+			 "range\n");
+	      return SSA_PROP_VARYING;
+	    }
+        }
     }
 
   *taken_edge_p = find_edge (gimple_bb (stmt),
@@ -8195,18 +8284,20 @@  simplify_switch_using_ranges (gimple stm
   size_t i = 0, j = 0, n, n2;
   tree vec2;
   switch_update su;
+  size_t k = 1, l = 0;
 
   if (TREE_CODE (op) == SSA_NAME)
     {
       vr = get_value_range (op);
 
       /* We can only handle integer ranges.  */
-      if (vr->type != VR_RANGE
+      if ((vr->type != VR_RANGE
+	   && vr->type != VR_ANTI_RANGE)
 	  || symbolic_range_p (vr))
 	return false;
 
       /* Find case label for min/max of the value range.  */
-      take_default = !find_case_label_range (stmt, vr->min, vr->max, &i, &j);
+      take_default = !find_case_label_ranges (stmt, vr, &i, &j, &k, &l);
     }
   else if (TREE_CODE (op) == INTEGER_CST)
     {
@@ -8233,7 +8324,7 @@  simplify_switch_using_ranges (gimple stm
     return false;
 
   /* Build a new vector of taken case labels.  */
-  vec2 = make_tree_vec (j - i + 1 + (int)take_default);
+  vec2 = make_tree_vec (j - i + 1 + l - k + 1 + (int)take_default);
   n2 = 0;
 
   /* Add the default edge, if necessary.  */
@@ -8243,6 +8334,9 @@  simplify_switch_using_ranges (gimple stm
   for (; i <= j; ++i, ++n2)
     TREE_VEC_ELT (vec2, n2) = gimple_switch_label (stmt, i);
 
+  for (; k <= l; ++k, ++n2)
+    TREE_VEC_ELT (vec2, n2) = gimple_switch_label (stmt, k);
+
   /* Mark needed edges.  */
   for (i = 0; i < n2; ++i)
     {
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp72.c
===================================================================
--- /dev/null (new file)
+++ gcc/testsuite/gcc.dg/tree-ssa/vrp72.c (revision 0)
@@ -0,0 +1,35 @@ 
+/* { dg-do link } */
+/* { dg-options "-O2 -fno-tree-switch-conversion" } */
+
+/* Based on f3 from vrp63.c, but with switch instead of if-chain.  This test
+   tests the propagation of an anti-range in a switch statement.  */
+
+extern void link_error (void);
+
+void
+f3 (int s)
+{
+  if (s >> 3 == -2)
+    /* s in range [ -16, -9].  */
+    ;
+  else
+    {
+      /* s in range ~[-16, -9], so none of the case labels can be taken.  */
+      switch (s)
+	{
+	case -16:
+	case -12:
+	case -9:
+	  link_error ();
+	  break;
+	default:
+	  break;
+	}
+    }
+}
+
+int
+main ()
+{
+  return 0;
+}