* [PATCH] Teach VRP to truncate the case ranges of a switch
@ 2016-08-03 4:00 Patrick Palka
2016-08-03 13:48 ` Richard Biener
0 siblings, 1 reply; 10+ messages in thread
From: Patrick Palka @ 2016-08-03 4:00 UTC (permalink / raw)
To: gcc-patches; +Cc: Patrick Palka
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] Teach VRP to truncate the case ranges of a switch
2016-08-03 4:00 [PATCH] Teach VRP to truncate the case ranges of a switch Patrick Palka
@ 2016-08-03 13:48 ` Richard Biener
2016-08-03 15:17 ` Jeff Law
` (2 more replies)
0 siblings, 3 replies; 10+ messages in thread
From: Richard Biener @ 2016-08-03 13:48 UTC (permalink / raw)
To: Patrick Palka; +Cc: GCC Patches
On Wed, Aug 3, 2016 at 6:00 AM, Patrick Palka <patrick@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
>
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] Teach VRP to truncate the case ranges of a switch
2016-08-03 13:48 ` Richard Biener
@ 2016-08-03 15:17 ` Jeff Law
2016-08-03 15:30 ` David Malcolm
2016-08-05 10:19 ` Markus Trippelsdorf
2 siblings, 0 replies; 10+ messages in thread
From: Jeff Law @ 2016-08-03 15:17 UTC (permalink / raw)
To: Richard Biener, Patrick Palka; +Cc: GCC Patches
On 08/03/2016 07:47 AM, Richard Biener wrote:
> On Wed, Aug 3, 2016 at 6:00 AM, Patrick Palka <patrick@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.
It's mostly a code/rodata savings. It's something I've wanted for a
long time, though the priority dropped considerably once the PA died as
an architecture :-)
Jeff
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] Teach VRP to truncate the case ranges of a switch
2016-08-03 13:48 ` Richard Biener
2016-08-03 15:17 ` Jeff Law
@ 2016-08-03 15:30 ` David Malcolm
2016-08-03 16:03 ` Jeff Law
2016-08-04 2:30 ` Patrick Palka
2016-08-05 10:19 ` Markus Trippelsdorf
2 siblings, 2 replies; 10+ messages in thread
From: David Malcolm @ 2016-08-03 15:30 UTC (permalink / raw)
To: Richard Biener, Patrick Palka; +Cc: GCC Patches
On Wed, 2016-08-03 at 15:47 +0200, Richard Biener wrote:
> On Wed, Aug 3, 2016 at 6:00 AM, Patrick Palka <patrick@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.
Is this always an improvement? I can see that it can simplify things,
eliminate dead code etc, but could it make evaluating the switch less
efficient?
Consider e.g.
void
test (char ch)
{
if (ch > 17)
return;
switch (ch)
{
case 0:
foo (); break;
case 1 .. 255:
bar (); break;
}
}
which (assuming this could survive this far in this form) previously
could be implemented as a simple "if (ch == 0)" but with this would get
simplified to:
void
test (char ch)
{
if (ch > 17)
return;
switch (ch)
{
case 0:
foo (); break;
case 1 .. 17:
bar (); break;
}
}
which presumably introduces a compare against 17 in the implementation of the switch; does the new compare get optimized away by jump threading?
Sorry if this is a silly qn.
Dave
> 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
> >
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] Teach VRP to truncate the case ranges of a switch
2016-08-03 15:30 ` David Malcolm
@ 2016-08-03 16:03 ` Jeff Law
2016-08-04 2:30 ` Patrick Palka
1 sibling, 0 replies; 10+ messages in thread
From: Jeff Law @ 2016-08-03 16:03 UTC (permalink / raw)
To: David Malcolm, Richard Biener, Patrick Palka; +Cc: GCC Patches
On 08/03/2016 09:29 AM, David Malcolm wrote:
> On Wed, 2016-08-03 at 15:47 +0200, Richard Biener wrote:
>> On Wed, Aug 3, 2016 at 6:00 AM, Patrick Palka <patrick@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.
>
> Is this always an improvement? I can see that it can simplify things,
> eliminate dead code etc, but could it make evaluating the switch less
> efficient?
I don't think so. We should recognize that the default fall-thru
doesn't happen because of the range associated with CH as we enter the
switch.
So, in theory we'd still be able to collapse down to
if (ch > 17)
return
if (ch == 0)
foo ();
else
bar ();
I haven't actually checked though.
Jeff
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] Teach VRP to truncate the case ranges of a switch
2016-08-03 15:30 ` David Malcolm
2016-08-03 16:03 ` Jeff Law
@ 2016-08-04 2:30 ` Patrick Palka
2016-08-04 8:11 ` Richard Biener
1 sibling, 1 reply; 10+ messages in thread
From: Patrick Palka @ 2016-08-04 2:30 UTC (permalink / raw)
To: David Malcolm; +Cc: Richard Biener, Patrick Palka, GCC Patches
On Wed, 3 Aug 2016, David Malcolm wrote:
> On Wed, 2016-08-03 at 15:47 +0200, Richard Biener wrote:
> > On Wed, Aug 3, 2016 at 6:00 AM, Patrick Palka <patrick@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.
>
> Is this always an improvement? I can see that it can simplify things,
> eliminate dead code etc, but could it make evaluating the switch less
> efficient?
>
> Consider e.g.
>
> void
> test (char ch)
> {
> if (ch > 17)
> return;
>
> switch (ch)
> {
> case 0:
> foo (); break;
>
> case 1 .. 255:
> bar (); break;
> }
> }
>
> which (assuming this could survive this far in this form) previously
> could be implemented as a simple "if (ch == 0)" but with this would get
> simplified to:
>
> void
> test (char ch)
> {
> if (ch > 17)
> return;
>
> switch (ch)
> {
> case 0:
> foo (); break;
>
> case 1 .. 17:
> bar (); break;
> }
> }
>
> which presumably introduces a compare against 17 in the implementation of the switch; does the new compare get optimized away by jump threading?
In this particular example the final code does get worse with the patch
for the reason you mentioned:
Before: After:
test: test:
.LFB0: .LFB0:
.cfi_startproc .cfi_startproc
cmpb $17, %dil cmpb $17, %dil
ja .L1 ja .L1
xorl %eax, %eax subl $1, %edi
cmpb $1, %dil xorl %eax, %eax
jb .L7 cmpb $16, %dil
jmp bar ja .L7
.p2align 4,,10 jmp bar
.p2align 3 .p2align 4,,10
.L7: .p2align 3
jmp foo .L7:
.p2align 4,,10 jmp foo
.p2align 3 .p2align 4,,10
.L1: .p2align 3
rep ret .L1:
.cfi_endproc rep ret
.cfi_endproc
What's weird is that during gimplification the switch gets simplified to
switch (ch)
{
default: foo (); break;
case 1 ... 255: bar (); break;
}
but if anything I would have expected it to get simplified to
switch (ch)
{
case 0: foo (); break;
default: bar (); break;
}
In general, when case labels are exhaustive, maybe it would be better to
designate the case label that has the widest range as the default label?
(Currently preprocess_case_label_vec_for_gimple() just designates the
very first label to be the default label.) That would fix this
particular regression at least.
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] Teach VRP to truncate the case ranges of a switch
2016-08-04 2:30 ` Patrick Palka
@ 2016-08-04 8:11 ` Richard Biener
2016-08-04 12:14 ` Patrick Palka
0 siblings, 1 reply; 10+ messages in thread
From: Richard Biener @ 2016-08-04 8:11 UTC (permalink / raw)
To: Patrick Palka; +Cc: David Malcolm, GCC Patches
On Thu, Aug 4, 2016 at 4:30 AM, Patrick Palka <patrick@parcs.ath.cx> wrote:
> On Wed, 3 Aug 2016, David Malcolm wrote:
>
>> On Wed, 2016-08-03 at 15:47 +0200, Richard Biener wrote:
>> > On Wed, Aug 3, 2016 at 6:00 AM, Patrick Palka <patrick@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.
>>
>> Is this always an improvement? I can see that it can simplify things,
>> eliminate dead code etc, but could it make evaluating the switch less
>> efficient?
>>
>> Consider e.g.
>>
>> void
>> test (char ch)
>> {
>> if (ch > 17)
>> return;
>>
>> switch (ch)
>> {
>> case 0:
>> foo (); break;
>>
>> case 1 .. 255:
>> bar (); break;
>> }
>> }
>>
>> which (assuming this could survive this far in this form) previously
>> could be implemented as a simple "if (ch == 0)" but with this would get
>> simplified to:
>>
>> void
>> test (char ch)
>> {
>> if (ch > 17)
>> return;
>>
>> switch (ch)
>> {
>> case 0:
>> foo (); break;
>>
>> case 1 .. 17:
>> bar (); break;
>> }
>> }
>>
>> which presumably introduces a compare against 17 in the implementation of the switch; does the new compare get optimized away by jump threading?
>
> In this particular example the final code does get worse with the patch
> for the reason you mentioned:
>
> Before: After:
> test: test:
> .LFB0: .LFB0:
> .cfi_startproc .cfi_startproc
> cmpb $17, %dil cmpb $17, %dil
> ja .L1 ja .L1
> xorl %eax, %eax subl $1, %edi
> cmpb $1, %dil xorl %eax, %eax
> jb .L7 cmpb $16, %dil
> jmp bar ja .L7
> .p2align 4,,10 jmp bar
> .p2align 3 .p2align 4,,10
> .L7: .p2align 3
> jmp foo .L7:
> .p2align 4,,10 jmp foo
> .p2align 3 .p2align 4,,10
> .L1: .p2align 3
> rep ret .L1:
> .cfi_endproc rep ret
> .cfi_endproc
>
> What's weird is that during gimplification the switch gets simplified to
>
> switch (ch)
> {
> default: foo (); break;
> case 1 ... 255: bar (); break;
> }
>
> but if anything I would have expected it to get simplified to
>
> switch (ch)
> {
> case 0: foo (); break;
> default: bar (); break;
> }
>
> In general, when case labels are exhaustive, maybe it would be better to
> designate the case label that has the widest range as the default label?
> (Currently preprocess_case_label_vec_for_gimple() just designates the
> very first label to be the default label.) That would fix this
> particular regression at least.
Yes, that looks useful - though I wonder how easy it is to detect for the
cases where there are more than one case/default.
Richard.
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] Teach VRP to truncate the case ranges of a switch
2016-08-04 8:11 ` Richard Biener
@ 2016-08-04 12:14 ` Patrick Palka
2016-08-04 13:41 ` Richard Biener
0 siblings, 1 reply; 10+ messages in thread
From: Patrick Palka @ 2016-08-04 12:14 UTC (permalink / raw)
To: Richard Biener; +Cc: Patrick Palka, David Malcolm, GCC Patches
On Thu, 4 Aug 2016, Richard Biener wrote:
> On Thu, Aug 4, 2016 at 4:30 AM, Patrick Palka <patrick@parcs.ath.cx> wrote:
> > On Wed, 3 Aug 2016, David Malcolm wrote:
> >
> >> On Wed, 2016-08-03 at 15:47 +0200, Richard Biener wrote:
> >> > On Wed, Aug 3, 2016 at 6:00 AM, Patrick Palka <patrick@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.
> >>
> >> Is this always an improvement? I can see that it can simplify things,
> >> eliminate dead code etc, but could it make evaluating the switch less
> >> efficient?
> >>
> >> Consider e.g.
> >>
> >> void
> >> test (char ch)
> >> {
> >> if (ch > 17)
> >> return;
> >>
> >> switch (ch)
> >> {
> >> case 0:
> >> foo (); break;
> >>
> >> case 1 .. 255:
> >> bar (); break;
> >> }
> >> }
> >>
> >> which (assuming this could survive this far in this form) previously
> >> could be implemented as a simple "if (ch == 0)" but with this would get
> >> simplified to:
> >>
> >> void
> >> test (char ch)
> >> {
> >> if (ch > 17)
> >> return;
> >>
> >> switch (ch)
> >> {
> >> case 0:
> >> foo (); break;
> >>
> >> case 1 .. 17:
> >> bar (); break;
> >> }
> >> }
> >>
> >> which presumably introduces a compare against 17 in the implementation of the switch; does the new compare get optimized away by jump threading?
> >
> > In this particular example the final code does get worse with the patch
> > for the reason you mentioned:
> >
> > Before: After:
> > test: test:
> > .LFB0: .LFB0:
> > .cfi_startproc .cfi_startproc
> > cmpb $17, %dil cmpb $17, %dil
> > ja .L1 ja .L1
> > xorl %eax, %eax subl $1, %edi
> > cmpb $1, %dil xorl %eax, %eax
> > jb .L7 cmpb $16, %dil
> > jmp bar ja .L7
> > .p2align 4,,10 jmp bar
> > .p2align 3 .p2align 4,,10
> > .L7: .p2align 3
> > jmp foo .L7:
> > .p2align 4,,10 jmp foo
> > .p2align 3 .p2align 4,,10
> > .L1: .p2align 3
> > rep ret .L1:
> > .cfi_endproc rep ret
> > .cfi_endproc
> >
> > What's weird is that during gimplification the switch gets simplified to
> >
> > switch (ch)
> > {
> > default: foo (); break;
> > case 1 ... 255: bar (); break;
> > }
> >
> > but if anything I would have expected it to get simplified to
> >
> > switch (ch)
> > {
> > case 0: foo (); break;
> > default: bar (); break;
> > }
> >
> > In general, when case labels are exhaustive, maybe it would be better to
> > designate the case label that has the widest range as the default label?
> > (Currently preprocess_case_label_vec_for_gimple() just designates the
> > very first label to be the default label.) That would fix this
> > particular regression at least.
>
> Yes, that looks useful - though I wonder how easy it is to detect for the
> cases where there are more than one case/default.
>
> Richard.
>
Here's a patch that does this. Does it look OK to commit after
bootstrap + regtesting?
-- >8 --
gcc/ChangeLog:
* gimple.c (preprocess_case_label_vec_for_gimple): When the case
labels are exhaustive, designate the label with the widest
range to be the default label.
gcc/testsuite/ChangeLog:
* gcc.dg/switch-11.c: New test.
---
gcc/gimple.c | 14 +++++++++++++-
gcc/testsuite/gcc.dg/switch-11.c | 22 ++++++++++++++++++++++
2 files changed, 35 insertions(+), 1 deletion(-)
create mode 100644 gcc/testsuite/gcc.dg/switch-11.c
diff --git a/gcc/gimple.c b/gcc/gimple.c
index e275dfc..fc81e52 100644
--- a/gcc/gimple.c
+++ b/gcc/gimple.c
@@ -2946,18 +2946,30 @@ preprocess_case_label_vec_for_gimple (vec<tree> labels,
high = CASE_LOW (labels[len - 1]);
if (tree_int_cst_equal (high, TYPE_MAX_VALUE (index_type)))
{
+ tree widest_label = labels[0];
for (i = 1; i < len; i++)
{
high = CASE_LOW (labels[i]);
low = CASE_HIGH (labels[i - 1]);
if (!low)
low = CASE_LOW (labels[i - 1]);
+
+ if (CASE_HIGH (labels[i]) != NULL_TREE
+ && (CASE_HIGH (widest_label) == NULL_TREE
+ || wi::gtu_p (wi::sub (CASE_HIGH (labels[i]),
+ CASE_LOW (labels[i])),
+ wi::sub (CASE_HIGH (widest_label),
+ CASE_LOW (widest_label)))))
+ widest_label = labels[i];
+
if (wi::add (low, 1) != high)
break;
}
if (i == len)
{
- tree label = CASE_LABEL (labels[0]);
+ /* Designate the label with the widest range to be the
+ default label. */
+ tree label = CASE_LABEL (widest_label);
default_case = build_case_label (NULL_TREE, NULL_TREE,
label);
}
diff --git a/gcc/testsuite/gcc.dg/switch-11.c b/gcc/testsuite/gcc.dg/switch-11.c
new file mode 100644
index 0000000..0ffc9eb
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/switch-11.c
@@ -0,0 +1,22 @@
+/* { dg-options "-O2 -fdump-tree-cfg" } */
+/* { dg-final { scan-tree-dump "case 0:" "cfg" } } */
+/* { dg-final { scan-tree-dump-not "case 1 ... 255:" "cfg" } } */
+#include <stdint.h>
+
+void foo (void);
+void bar (void);
+
+void
+test (uint8_t ch)
+{
+ switch (ch)
+ {
+ case 0:
+ foo ();
+ break;
+
+ case 1 ... 255:
+ bar ();
+ break;
+ }
+}
--
2.9.2.614.g990027a
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] Teach VRP to truncate the case ranges of a switch
2016-08-04 12:14 ` Patrick Palka
@ 2016-08-04 13:41 ` Richard Biener
0 siblings, 0 replies; 10+ messages in thread
From: Richard Biener @ 2016-08-04 13:41 UTC (permalink / raw)
To: Patrick Palka; +Cc: David Malcolm, GCC Patches
On Thu, Aug 4, 2016 at 2:14 PM, Patrick Palka <patrick@parcs.ath.cx> wrote:
> On Thu, 4 Aug 2016, Richard Biener wrote:
>
>> On Thu, Aug 4, 2016 at 4:30 AM, Patrick Palka <patrick@parcs.ath.cx> wrote:
>> > On Wed, 3 Aug 2016, David Malcolm wrote:
>> >
>> >> On Wed, 2016-08-03 at 15:47 +0200, Richard Biener wrote:
>> >> > On Wed, Aug 3, 2016 at 6:00 AM, Patrick Palka <patrick@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.
>> >>
>> >> Is this always an improvement? I can see that it can simplify things,
>> >> eliminate dead code etc, but could it make evaluating the switch less
>> >> efficient?
>> >>
>> >> Consider e.g.
>> >>
>> >> void
>> >> test (char ch)
>> >> {
>> >> if (ch > 17)
>> >> return;
>> >>
>> >> switch (ch)
>> >> {
>> >> case 0:
>> >> foo (); break;
>> >>
>> >> case 1 .. 255:
>> >> bar (); break;
>> >> }
>> >> }
>> >>
>> >> which (assuming this could survive this far in this form) previously
>> >> could be implemented as a simple "if (ch == 0)" but with this would get
>> >> simplified to:
>> >>
>> >> void
>> >> test (char ch)
>> >> {
>> >> if (ch > 17)
>> >> return;
>> >>
>> >> switch (ch)
>> >> {
>> >> case 0:
>> >> foo (); break;
>> >>
>> >> case 1 .. 17:
>> >> bar (); break;
>> >> }
>> >> }
>> >>
>> >> which presumably introduces a compare against 17 in the implementation of the switch; does the new compare get optimized away by jump threading?
>> >
>> > In this particular example the final code does get worse with the patch
>> > for the reason you mentioned:
>> >
>> > Before: After:
>> > test: test:
>> > .LFB0: .LFB0:
>> > .cfi_startproc .cfi_startproc
>> > cmpb $17, %dil cmpb $17, %dil
>> > ja .L1 ja .L1
>> > xorl %eax, %eax subl $1, %edi
>> > cmpb $1, %dil xorl %eax, %eax
>> > jb .L7 cmpb $16, %dil
>> > jmp bar ja .L7
>> > .p2align 4,,10 jmp bar
>> > .p2align 3 .p2align 4,,10
>> > .L7: .p2align 3
>> > jmp foo .L7:
>> > .p2align 4,,10 jmp foo
>> > .p2align 3 .p2align 4,,10
>> > .L1: .p2align 3
>> > rep ret .L1:
>> > .cfi_endproc rep ret
>> > .cfi_endproc
>> >
>> > What's weird is that during gimplification the switch gets simplified to
>> >
>> > switch (ch)
>> > {
>> > default: foo (); break;
>> > case 1 ... 255: bar (); break;
>> > }
>> >
>> > but if anything I would have expected it to get simplified to
>> >
>> > switch (ch)
>> > {
>> > case 0: foo (); break;
>> > default: bar (); break;
>> > }
>> >
>> > In general, when case labels are exhaustive, maybe it would be better to
>> > designate the case label that has the widest range as the default label?
>> > (Currently preprocess_case_label_vec_for_gimple() just designates the
>> > very first label to be the default label.) That would fix this
>> > particular regression at least.
>>
>> Yes, that looks useful - though I wonder how easy it is to detect for the
>> cases where there are more than one case/default.
>>
>> Richard.
>>
>
> Here's a patch that does this. Does it look OK to commit after
> bootstrap + regtesting?
Ok.
Thanks,
Richard.
> -- >8 --
>
> gcc/ChangeLog:
>
> * gimple.c (preprocess_case_label_vec_for_gimple): When the case
> labels are exhaustive, designate the label with the widest
> range to be the default label.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.dg/switch-11.c: New test.
>
> ---
> gcc/gimple.c | 14 +++++++++++++-
> gcc/testsuite/gcc.dg/switch-11.c | 22 ++++++++++++++++++++++
> 2 files changed, 35 insertions(+), 1 deletion(-)
> create mode 100644 gcc/testsuite/gcc.dg/switch-11.c
>
> diff --git a/gcc/gimple.c b/gcc/gimple.c
> index e275dfc..fc81e52 100644
> --- a/gcc/gimple.c
> +++ b/gcc/gimple.c
> @@ -2946,18 +2946,30 @@ preprocess_case_label_vec_for_gimple (vec<tree> labels,
> high = CASE_LOW (labels[len - 1]);
> if (tree_int_cst_equal (high, TYPE_MAX_VALUE (index_type)))
> {
> + tree widest_label = labels[0];
> for (i = 1; i < len; i++)
> {
> high = CASE_LOW (labels[i]);
> low = CASE_HIGH (labels[i - 1]);
> if (!low)
> low = CASE_LOW (labels[i - 1]);
> +
> + if (CASE_HIGH (labels[i]) != NULL_TREE
> + && (CASE_HIGH (widest_label) == NULL_TREE
> + || wi::gtu_p (wi::sub (CASE_HIGH (labels[i]),
> + CASE_LOW (labels[i])),
> + wi::sub (CASE_HIGH (widest_label),
> + CASE_LOW (widest_label)))))
> + widest_label = labels[i];
> +
> if (wi::add (low, 1) != high)
> break;
> }
> if (i == len)
> {
> - tree label = CASE_LABEL (labels[0]);
> + /* Designate the label with the widest range to be the
> + default label. */
> + tree label = CASE_LABEL (widest_label);
> default_case = build_case_label (NULL_TREE, NULL_TREE,
> label);
> }
> diff --git a/gcc/testsuite/gcc.dg/switch-11.c b/gcc/testsuite/gcc.dg/switch-11.c
> new file mode 100644
> index 0000000..0ffc9eb
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/switch-11.c
> @@ -0,0 +1,22 @@
> +/* { dg-options "-O2 -fdump-tree-cfg" } */
> +/* { dg-final { scan-tree-dump "case 0:" "cfg" } } */
> +/* { dg-final { scan-tree-dump-not "case 1 ... 255:" "cfg" } } */
> +#include <stdint.h>
> +
> +void foo (void);
> +void bar (void);
> +
> +void
> +test (uint8_t ch)
> +{
> + switch (ch)
> + {
> + case 0:
> + foo ();
> + break;
> +
> + case 1 ... 255:
> + bar ();
> + break;
> + }
> +}
> --
> 2.9.2.614.g990027a
>
>
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH] Teach VRP to truncate the case ranges of a switch
2016-08-03 13:48 ` Richard Biener
2016-08-03 15:17 ` Jeff Law
2016-08-03 15:30 ` David Malcolm
@ 2016-08-05 10:19 ` Markus Trippelsdorf
2 siblings, 0 replies; 10+ messages in thread
From: Markus Trippelsdorf @ 2016-08-05 10:19 UTC (permalink / raw)
To: Richard Biener; +Cc: Patrick Palka, GCC Patches
On 2016.08.03 at 15:47 +0200, Richard Biener wrote:
> On Wed, Aug 3, 2016 at 6:00 AM, Patrick Palka <patrick@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.
Apparently typedefs aren't handled correctly, see:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=72810
--
Markus
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2016-08-05 10:19 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-08-03 4:00 [PATCH] Teach VRP to truncate the case ranges of a switch Patrick Palka
2016-08-03 13:48 ` Richard Biener
2016-08-03 15:17 ` Jeff Law
2016-08-03 15:30 ` David Malcolm
2016-08-03 16:03 ` Jeff Law
2016-08-04 2:30 ` Patrick Palka
2016-08-04 8:11 ` Richard Biener
2016-08-04 12:14 ` Patrick Palka
2016-08-04 13:41 ` Richard Biener
2016-08-05 10:19 ` Markus Trippelsdorf
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).