On Wed, Aug 3, 2016 at 6:00 AM, Patrick Palka <patr...@parcs.ath.cx> wrote:
> 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.
I think it's most useful when the range collapses to a single value.
Ok.
Thanks,
Richard.
> 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
>
