[PATCH] Teach VRP to truncate the case ranges of a switch
Patrick Palka
patrick@parcs.ath.cx
Wed Aug 3 04:00:00 GMT 2016
VRP currently has functionality to eliminate case labels that lie
completely outside of the switch operand's value range. This patch
complements this functionality by teaching VRP to also truncate the case
label ranges that partially overlap with the operand's value range.
Bootstrapped and regtested on x86_64-pc-linux-gnu. Does this look like
a reasonable optimization? Admittedly, its effect will almost always be
negligible except in cases where a case label range spans a large number
of values which is a pretty rare thing. The optimization triggered
about 250 times during bootstrap.
gcc/ChangeLog:
* tree-vrp.c (simplify_switch_using_ranges): Try to truncate
the case label ranges that partially overlap with OP's value
range.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/vrp107.c: New test.
* gcc.dg/tree-ssa/vrp108.c: New test.
* gcc.dg/tree-ssa/vrp109.c: New test.
---
gcc/testsuite/gcc.dg/tree-ssa/vrp107.c | 25 +++++++++++
gcc/testsuite/gcc.dg/tree-ssa/vrp108.c | 25 +++++++++++
gcc/testsuite/gcc.dg/tree-ssa/vrp109.c | 65 +++++++++++++++++++++++++++
gcc/tree-vrp.c | 80 +++++++++++++++++++++++++++++++++-
4 files changed, 194 insertions(+), 1 deletion(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp107.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp108.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp109.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp107.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp107.c
new file mode 100644
index 0000000..b74f031
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp107.c
@@ -0,0 +1,25 @@
+/* { dg-options "-O2 -fdump-tree-vrp1" } */
+/* { dg-final { scan-tree-dump "case 2:" "vrp1" } } */
+/* { dg-final { scan-tree-dump "case 7 ... 8:" "vrp1" } } */
+
+extern void foo (void);
+extern void bar (void);
+extern void baz (void);
+
+void
+test (int i)
+{
+ if (i >= 2 && i <= 8)
+ switch (i)
+ {
+ case 1: /* Redundant label. */
+ case 2:
+ bar ();
+ break;
+ case 7:
+ case 8:
+ case 9: /* Redundant label. */
+ baz ();
+ break;
+ }
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp108.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp108.c
new file mode 100644
index 0000000..49dbfb5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp108.c
@@ -0,0 +1,25 @@
+/* { dg-options "-O2 -fdump-tree-vrp1" } */
+/* { dg-final { scan-tree-dump "case 1:" "vrp1" } } */
+/* { dg-final { scan-tree-dump "case 9:" "vrp1" } } */
+
+extern void foo (void);
+extern void bar (void);
+extern void baz (void);
+
+void
+test (int i)
+{
+ if (i < 2 || i > 8)
+ switch (i)
+ {
+ case 1:
+ case 2: /* Redundant label. */
+ bar ();
+ break;
+ case 7: /* Redundant label. */
+ case 8: /* Redundant label. */
+ case 9:
+ baz ();
+ break;
+ }
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp109.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp109.c
new file mode 100644
index 0000000..86299a9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp109.c
@@ -0,0 +1,65 @@
+/* { dg-options "-O2 -fdump-tree-vrp1" } */
+/* { dg-final { scan-tree-dump "case 9 ... 10:" "vrp1" } } */
+/* { dg-final { scan-tree-dump "case 17 ... 18:" "vrp1" } } */
+/* { dg-final { scan-tree-dump "case 27 ... 30:" "vrp1" } } */
+
+extern void foo (void);
+extern void bar (void);
+
+void
+test1 (int i)
+{
+ if (i != 7 && i != 8)
+ switch (i)
+ {
+ case 1:
+ case 2:
+ foo ();
+ break;
+ case 7: /* Redundant label. */
+ case 8: /* Redundant label. */
+ case 9:
+ case 10:
+ bar ();
+ break;
+ }
+}
+
+void
+test3 (int i)
+{
+ if (i != 19 && i != 20)
+ switch (i)
+ {
+ case 1:
+ case 2:
+ foo ();
+ break;
+ case 17:
+ case 18:
+ case 19: /* Redundant label. */
+ case 20: /* Redundant label. */
+ bar ();
+ break;
+ }
+}
+
+void
+test2 (int i)
+{
+ if (i != 28 && i != 29)
+ switch (i)
+ {
+ case 1:
+ case 2:
+ foo ();
+ break;
+ /* No redundancy. */
+ case 27:
+ case 28:
+ case 29:
+ case 30:
+ bar ();
+ break;
+ }
+}
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index cb316b0..b654b1b 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -9586,7 +9586,7 @@ static bool
simplify_switch_using_ranges (gswitch *stmt)
{
tree op = gimple_switch_index (stmt);
- value_range *vr;
+ value_range *vr = NULL;
bool take_default;
edge e;
edge_iterator ei;
@@ -9626,6 +9626,84 @@ simplify_switch_using_ranges (gswitch *stmt)
n = gimple_switch_num_labels (stmt);
+ /* We can truncate the case label ranges that partially overlap with OP's
+ value range. */
+ size_t min_idx = 1, max_idx = 0;
+ if (vr != NULL)
+ find_case_label_range (stmt, vr->min, vr->max, &min_idx, &max_idx);
+ if (min_idx <= max_idx)
+ {
+ tree min_label = gimple_switch_label (stmt, min_idx);
+ tree max_label = gimple_switch_label (stmt, max_idx);
+
+ if (vr->type == VR_RANGE)
+ {
+ /* If OP's value range is [2,8] and the low label range is
+ 0 ... 3, truncate the label's range to 2 .. 3. */
+ if (tree_int_cst_compare (CASE_LOW (min_label), vr->min) < 0
+ && CASE_HIGH (min_label) != NULL_TREE
+ && tree_int_cst_compare (CASE_HIGH (min_label), vr->min) >= 0)
+ CASE_LOW (min_label) = vr->min;
+
+ /* If OP's value range is [2,8] and the high label range is
+ 7 ... 10, truncate the label's range to 7 .. 8. */
+ if (tree_int_cst_compare (CASE_LOW (max_label), vr->max) <= 0
+ && CASE_HIGH (max_label) != NULL_TREE
+ && tree_int_cst_compare (CASE_HIGH (max_label), vr->max) > 0)
+ CASE_HIGH (max_label) = vr->max;
+ }
+ else if (vr->type == VR_ANTI_RANGE)
+ {
+ tree one_cst = build_one_cst (TREE_TYPE (op));
+
+ if (min_label == max_label)
+ {
+ /* If OP's value range is ~[7,8] and the label's range is
+ 7 ... 10, truncate the label's range to 9 ... 10. */
+ if (tree_int_cst_compare (CASE_LOW (min_label), vr->min) == 0
+ && CASE_HIGH (min_label) != NULL_TREE
+ && tree_int_cst_compare (CASE_HIGH (min_label), vr->max) > 0)
+ CASE_LOW (min_label)
+ = int_const_binop (PLUS_EXPR, vr->max, one_cst);
+
+ /* If OP's value range is ~[7,8] and the label's range is
+ 5 ... 8, truncate the label's range to 5 ... 6. */
+ if (tree_int_cst_compare (CASE_LOW (min_label), vr->min) < 0
+ && CASE_HIGH (min_label) != NULL_TREE
+ && tree_int_cst_compare (CASE_HIGH (min_label), vr->max) == 0)
+ CASE_HIGH (min_label)
+ = int_const_binop (MINUS_EXPR, vr->min, one_cst);
+ }
+ else
+ {
+ /* If OP's value range is ~[2,8] and the low label range is
+ 0 ... 3, truncate the label's range to 0 ... 1. */
+ if (tree_int_cst_compare (CASE_LOW (min_label), vr->min) < 0
+ && CASE_HIGH (min_label) != NULL_TREE
+ && tree_int_cst_compare (CASE_HIGH (min_label), vr->min) >= 0)
+ CASE_HIGH (min_label)
+ = int_const_binop (MINUS_EXPR, vr->min, one_cst);
+
+ /* If OP's value range is ~[2,8] and the high label range is
+ 7 ... 10, truncate the label's range to 9 ... 10. */
+ if (tree_int_cst_compare (CASE_LOW (max_label), vr->max) <= 0
+ && CASE_HIGH (max_label) != NULL_TREE
+ && tree_int_cst_compare (CASE_HIGH (max_label), vr->max) > 0)
+ CASE_LOW (max_label)
+ = int_const_binop (PLUS_EXPR, vr->max, one_cst);
+ }
+ }
+
+ /* Canonicalize singleton case ranges. */
+ if (tree_int_cst_equal (CASE_LOW (min_label), CASE_HIGH (min_label)))
+ CASE_HIGH (min_label) = NULL_TREE;
+ if (tree_int_cst_equal (CASE_LOW (max_label), CASE_HIGH (max_label)))
+ CASE_HIGH (max_label) = NULL_TREE;
+ }
+
+ /* We can also eliminate case labels that lie completely outside OP's value
+ range. */
+
/* Bail out if this is just all edges taken. */
if (i == 1
&& j == n - 1
--
2.9.2.564.g4d4f0b7
More information about the Gcc-patches
mailing list