From 48abe922252d8831e7a3724173a22361d900da0b Mon Sep 17 00:00:00 2001 From: Patrick Palka Date: Fri, 5 Aug 2016 00:07:16 +0000 Subject: [PATCH] Teach VRP to truncate the case ranges of a switch 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. From-SVN: r239157 --- gcc/ChangeLog | 6 ++ gcc/testsuite/ChangeLog | 6 ++ 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 +++++++++++++++++++++++++- 6 files changed, 206 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/ChangeLog b/gcc/ChangeLog index fd6fa781277..83bdb1af708 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,9 @@ +2016-08-04 Patrick Palka + + * tree-vrp.c (simplify_switch_using_ranges): Try to truncate + the case label ranges that partially overlap with OP's value + range. + 2016-08-04 Uros Bizjak PR target/72805 diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 52e8f2e601c..6f057a416ef 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,9 @@ +2016-08-04 Patrick Palka + + * gcc.dg/tree-ssa/vrp107.c: New test. + * gcc.dg/tree-ssa/vrp108.c: New test. + * gcc.dg/tree-ssa/vrp109.c: New test. + 2016-08-04 Prathamesh Kulkarni * gcc.dg/pr70920-4.c: Move dg-require-effective-target before 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 00000000000..b74f031b1c8 --- /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 00000000000..49dbfb5447b --- /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 00000000000..86299a9c597 --- /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 c0e25cfdf22..cee6424b009 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -9593,7 +9593,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; @@ -9633,6 +9633,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.30.2