===================================================================
@@ -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)
{
===================================================================
@@ -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;
+}
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.