| Message ID | 20160722192630.23771-1-patrick@parcs.ath.cx |
|---|---|
| State | New |
| Headers | show |
On Fri, 22 Jul 2016, Patrick Palka wrote: > This patch teaches VRP to register along a default switch label > assertions that corresponds to the anti range of each case label. > > Does this look OK to commit after bootstrap + regtest on > x86_64-pc-linux-gnu? Forgot the changelog: gcc/ChangeLog: PR tree-optimization/18046 * tree-vrp.c (find_switch_asserts): Register edge assertions for the default label which correspond to the anti-ranges of each non-case label. gcc/testsuite/ChangeLog: PR tree-optimization/18046 * gcc.dg/tree-ssa/ssa-dom-thread-6.c: Bump FSM count to 5. * gcc.dg/tree-ssa/vrp103.c: New test. * gcc.dg/tree-ssa/vrp104.c: New test. > --- > gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c | 2 +- > gcc/testsuite/gcc.dg/tree-ssa/vrp103.c | 30 ++++++++++++++++++ > gcc/testsuite/gcc.dg/tree-ssa/vrp104.c | 32 +++++++++++++++++++ > gcc/tree-vrp.c | 39 ++++++++++++++++++++++-- > 4 files changed, 100 insertions(+), 3 deletions(-) > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp103.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp104.c > > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c > index 5ec4687..551fbac 100644 > --- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c > +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c > @@ -1,7 +1,7 @@ > /* { dg-do compile } */ > /* { dg-options "-O2 -fdump-tree-thread1-details -fdump-tree-thread2-details" } */ > /* { dg-final { scan-tree-dump-times "FSM" 3 "thread1" } } */ > -/* { dg-final { scan-tree-dump-times "FSM" 4 "thread2" } } */ > +/* { dg-final { scan-tree-dump-times "FSM" 5 "thread2" } } */ > > int sum0, sum1, sum2, sum3; > int foo (char *s, char **ret) > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp103.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp103.c > new file mode 100644 > index 0000000..eea98bb > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp103.c > @@ -0,0 +1,30 @@ > +/* PR tree-optimization/18046 */ > +/* { dg-options "-O2 -fdump-tree-vrp" } */ > +/* { dg-final { scan-tree-dump-times "baz \\(0\\);" 4 "vrp1" } } */ > + > +void foo (); > +void bar (); > +void baz (int); > + > +void > +test (int i) > +{ > + switch (i) > + { > + case 1: > + case 2: > + case 3: > + foo (); > + break; > + case 5: > + bar (); > + break; > + default: > + /* These tests should be folded to 0, resulting in 4 calls to bar (0). */ > + baz (i == 1); > + baz (i == 2); > + baz (i == 3); > + baz (i == 5); > + break; > + } > +} > diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c > new file mode 100644 > index 0000000..6410847 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c > @@ -0,0 +1,32 @@ > +/* PR tree-optimization/18046 */ > +/* { dg-options "-O2 -fdump-tree-optimized" } */ > +/* { dg-final { scan-tree-dump-times "switch" 1 "optimized" } } */ > + > +void foo (); > +void bar (); > + > +void > +test (int i) > +{ > + switch (i) > + { > + case 1: > + foo (); > + break; > + case 2: > + bar (); > + break; > + default: > + break; > + } > + > + /* This switch should be gone after threading/VRP. */ > + switch (i) > + { > + case 1: > + foo (); > + break; > + default: > + break; > + } > +} > diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c > index 06364b7..32a4de3 100644 > --- a/gcc/tree-vrp.c > +++ b/gcc/tree-vrp.c > @@ -5917,6 +5917,7 @@ find_switch_asserts (basic_block bb, gswitch *last) > ci[idx].expr = gimple_switch_label (last, idx); > ci[idx].bb = label_to_block (CASE_LABEL (ci[idx].expr)); > } > + edge default_edge = find_edge (bb, ci[0].bb); > qsort (ci, n, sizeof (struct case_info), compare_case_labels); > > for (idx = 0; idx < n; ++idx) > @@ -5945,8 +5946,8 @@ find_switch_asserts (basic_block bb, gswitch *last) > max = CASE_LOW (ci[idx].expr); > } > > - /* Nothing to do if the range includes the default label until we > - can register anti-ranges. */ > + /* Can't extract a useful assertion out of a range that includes the > + default label. */ > if (min == NULL_TREE) > continue; > > @@ -5963,6 +5964,40 @@ find_switch_asserts (basic_block bb, gswitch *last) > fold_convert (TREE_TYPE (op), max)); > } > > + /* For each case label, register along the default label an assertion that > + corresponds to the anti-range of that label. */ > + for (idx = 0; idx < n; ++idx) > + { > + tree min, max; > + tree cl = ci[idx].expr; > + > + min = CASE_LOW (cl); > + max = CASE_HIGH (cl); > + > + if (min == NULL_TREE) > + continue; > + > + if (max == NULL_TREE) > + { > + /* Register the assertion OP != MIN. */ > + min = fold_convert (TREE_TYPE (op), min); > + register_edge_assert_for (op, default_edge, bsi, NE_EXPR, op, min); > + } > + else > + { > + /* Register the assertion (unsigned)OP - MIN > (MAX - MIN), > + which will give OP the anti-range ~[MIN,MAX]. */ > + tree uop = fold_convert (unsigned_type_for (TREE_TYPE (op)), op); > + min = fold_convert (TREE_TYPE (uop), min); > + max = fold_convert (TREE_TYPE (uop), max); > + > + tree lhs = fold_build2 (MINUS_EXPR, TREE_TYPE (uop), uop, min); > + tree rhs = int_const_binop (MINUS_EXPR, max, min); > + register_new_assert_for (op, lhs, GT_EXPR, rhs, > + NULL, default_edge, bsi); > + } > + } > + > XDELETEVEC (ci); > } > > -- > 2.9.2.413.g76d2a70 > >
On 23/07/16 05:26, Patrick Palka wrote: > This patch teaches VRP to register along a default switch label > assertions that corresponds to the anti range of each case label. Hi Patrick, In case of a larger switch statement with case values that cannot be combined, you could end up with very large number of ASSERT_EXPRs in the default basic block. I am not sure if this would have any impact on compile time/memory usage? If that is the case you might want to punt at some length? Thanks, Kugan
On Sat, Jul 23, 2016 at 9:13 PM, kugan <kugan.vivekanandarajah@linaro.org> wrote: > > > On 23/07/16 05:26, Patrick Palka wrote: >> >> This patch teaches VRP to register along a default switch label >> assertions that corresponds to the anti range of each case label. > > > Hi Patrick, > > In case of a larger switch statement with case values that cannot be > combined, you could end up with very large number of ASSERT_EXPRs in the > default basic block. I am not sure if this would have any impact on compile > time/memory usage? If that is the case you might want to punt at some > length? Hi Kugan, That sounds like a good idea to me. So I gathered some info about the number of assert_exprs inserted in the default bb during GCC bootstrap with this patch: Max # of asserts inserted in a default BB: 59 Median #: 2 Average #: 3.33817 Std. dev: 4.76926 95% percentile: 10 Based on the last point I guess 10 would be a good limit? > > Thanks, > Kugan
On Sun, Jul 24, 2016 at 9:49 AM, Patrick Palka <patrick@parcs.ath.cx> wrote: > On Sat, Jul 23, 2016 at 9:13 PM, kugan > <kugan.vivekanandarajah@linaro.org> wrote: >> >> >> On 23/07/16 05:26, Patrick Palka wrote: >>> >>> This patch teaches VRP to register along a default switch label >>> assertions that corresponds to the anti range of each case label. >> >> >> Hi Patrick, >> >> In case of a larger switch statement with case values that cannot be >> combined, you could end up with very large number of ASSERT_EXPRs in the >> default basic block. I am not sure if this would have any impact on compile >> time/memory usage? If that is the case you might want to punt at some >> length? > > Hi Kugan, > > That sounds like a good idea to me. So I gathered some info about the > number of assert_exprs inserted in the default bb during GCC bootstrap > with this patch: > > Max # of asserts inserted in a default BB: 59 > Median #: 2 > Average #: 3.33817 > Std. dev: 4.76926 > 95% percentile: 10 > > Based on the last point I guess 10 would be a good limit? > Make sure this is a parameter so someone can increase it if they want. But 10 seems like a good default. Thanks, Andrew Pinski >> >> Thanks, >> Kugan
On 07/24/2016 11:56 AM, Andrew Pinski wrote: > On Sun, Jul 24, 2016 at 9:49 AM, Patrick Palka <patrick@parcs.ath.cx> wrote: >> On Sat, Jul 23, 2016 at 9:13 PM, kugan >> <kugan.vivekanandarajah@linaro.org> wrote: >>> >>> >>> On 23/07/16 05:26, Patrick Palka wrote: >>>> >>>> This patch teaches VRP to register along a default switch label >>>> assertions that corresponds to the anti range of each case label. >>> >>> >>> Hi Patrick, >>> >>> In case of a larger switch statement with case values that cannot be >>> combined, you could end up with very large number of ASSERT_EXPRs in the >>> default basic block. I am not sure if this would have any impact on compile >>> time/memory usage? If that is the case you might want to punt at some >>> length? >> >> Hi Kugan, >> >> That sounds like a good idea to me. So I gathered some info about the >> number of assert_exprs inserted in the default bb during GCC bootstrap >> with this patch: >> >> Max # of asserts inserted in a default BB: 59 >> Median #: 2 >> Average #: 3.33817 >> Std. dev: 4.76926 >> 95% percentile: 10 >> >> Based on the last point I guess 10 would be a good limit? >> > > Make sure this is a parameter so someone can increase it if they want. > But 10 seems like a good default. Agreed on both points. jeff
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c index 5ec4687..551fbac 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-6.c @@ -1,7 +1,7 @@ /* { dg-do compile } */ /* { dg-options "-O2 -fdump-tree-thread1-details -fdump-tree-thread2-details" } */ /* { dg-final { scan-tree-dump-times "FSM" 3 "thread1" } } */ -/* { dg-final { scan-tree-dump-times "FSM" 4 "thread2" } } */ +/* { dg-final { scan-tree-dump-times "FSM" 5 "thread2" } } */ int sum0, sum1, sum2, sum3; int foo (char *s, char **ret) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp103.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp103.c new file mode 100644 index 0000000..eea98bb --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp103.c @@ -0,0 +1,30 @@ +/* PR tree-optimization/18046 */ +/* { dg-options "-O2 -fdump-tree-vrp" } */ +/* { dg-final { scan-tree-dump-times "baz \\(0\\);" 4 "vrp1" } } */ + +void foo (); +void bar (); +void baz (int); + +void +test (int i) +{ + switch (i) + { + case 1: + case 2: + case 3: + foo (); + break; + case 5: + bar (); + break; + default: + /* These tests should be folded to 0, resulting in 4 calls to bar (0). */ + baz (i == 1); + baz (i == 2); + baz (i == 3); + baz (i == 5); + break; + } +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c new file mode 100644 index 0000000..6410847 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c @@ -0,0 +1,32 @@ +/* PR tree-optimization/18046 */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* { dg-final { scan-tree-dump-times "switch" 1 "optimized" } } */ + +void foo (); +void bar (); + +void +test (int i) +{ + switch (i) + { + case 1: + foo (); + break; + case 2: + bar (); + break; + default: + break; + } + + /* This switch should be gone after threading/VRP. */ + switch (i) + { + case 1: + foo (); + break; + default: + break; + } +} diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 06364b7..32a4de3 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -5917,6 +5917,7 @@ find_switch_asserts (basic_block bb, gswitch *last) ci[idx].expr = gimple_switch_label (last, idx); ci[idx].bb = label_to_block (CASE_LABEL (ci[idx].expr)); } + edge default_edge = find_edge (bb, ci[0].bb); qsort (ci, n, sizeof (struct case_info), compare_case_labels); for (idx = 0; idx < n; ++idx) @@ -5945,8 +5946,8 @@ find_switch_asserts (basic_block bb, gswitch *last) max = CASE_LOW (ci[idx].expr); } - /* Nothing to do if the range includes the default label until we - can register anti-ranges. */ + /* Can't extract a useful assertion out of a range that includes the + default label. */ if (min == NULL_TREE) continue; @@ -5963,6 +5964,40 @@ find_switch_asserts (basic_block bb, gswitch *last) fold_convert (TREE_TYPE (op), max)); } + /* For each case label, register along the default label an assertion that + corresponds to the anti-range of that label. */ + for (idx = 0; idx < n; ++idx) + { + tree min, max; + tree cl = ci[idx].expr; + + min = CASE_LOW (cl); + max = CASE_HIGH (cl); + + if (min == NULL_TREE) + continue; + + if (max == NULL_TREE) + { + /* Register the assertion OP != MIN. */ + min = fold_convert (TREE_TYPE (op), min); + register_edge_assert_for (op, default_edge, bsi, NE_EXPR, op, min); + } + else + { + /* Register the assertion (unsigned)OP - MIN > (MAX - MIN), + which will give OP the anti-range ~[MIN,MAX]. */ + tree uop = fold_convert (unsigned_type_for (TREE_TYPE (op)), op); + min = fold_convert (TREE_TYPE (uop), min); + max = fold_convert (TREE_TYPE (uop), max); + + tree lhs = fold_build2 (MINUS_EXPR, TREE_TYPE (uop), uop, min); + tree rhs = int_const_binop (MINUS_EXPR, max, min); + register_new_assert_for (op, lhs, GT_EXPR, rhs, + NULL, default_edge, bsi); + } + } + XDELETEVEC (ci); }