| Message ID | 20160803040021.11430-1-patrick@parcs.ath.cx |
|---|---|
| State | New |
| Headers | show |
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 >
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
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 > >
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
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.
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.
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
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