| Message ID | alpine.DEB.2.20.13.1607242336400.3152@idea |
|---|---|
| State | New |
| Headers | show |
On Mon, Jul 25, 2016 at 5:38 AM, Patrick Palka <patrick@parcs.ath.cx> wrote: > On Fri, 22 Jul 2016, Patrick Palka wrote: > >> On Fri, 22 Jul 2016, Patrick Palka wrote: >> >> > 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. >> > >> >> The patch failed to bootstrap due to a number -Warray-bounds warnings >> getting emitted for the autogenerated header file insn-modes.h: >> >> In file included from /home/patrick/code/gcc/gcc/machmode.h:24:0, >> from /home/patrick/code/gcc/gcc/coretypes.h:391, >> from /home/patrick/code/gcc/gcc/lto-streamer-out.c:25: >> ./insn-modes.h: In function ‘void produce_asm_for_decls()’: >> ./insn-modes.h:638:36: warning: array subscript is outside array bounds [-Warray-bounds] >> default: return mode_inner[mode]; >> ~~~~~~~~~~~~~~~^ >> >> These new warnings seem legitimate. From what I can tell, this array >> access along the default switch label will always be out of bounds. The >> code it's warning about basically looks like this: >> >> enum A { a, b, c }; >> int foo (A i) >> { >> int array[3]; >> switch (i) >> { >> case a: return x; >> case b: return y; >> case c: return z; >> default: return array[i]; >> } >> } >> >> and while the switch does exhaust every possible enumeration value of A, >> there's nothing stopping the user from passing an arbitrary int to >> foo() thus triggering the default case. So this patch suppresses these >> warnings by making genemit emit an assertion that verifies that mode is >> within the bounds of the array. This assertion won't affect performance >> because the mode_*_inline functions are always called with constant >> arguments. >> >> This version of the patch has the following changes: >> >> 1. Fixes the bootstrap failure as mentioned above. >> 2. Checks if the switch operand is live along the default edge before >> registering assertions. >> 3. Combines contiguous case ranges to reduce the number of assert >> expressions to insert. >> >> Bootstrap + regtesting in progress on x86_64-pc-linux-gnu. >> >> gcc/ChangeLog: >> >> PR tree-optimization/18046 >> * genmodes.c (emit_mode_size_inline): Emit an assert that >> verifies that mode is a valid array index. >> (emit_mode_nuinits_inline): Likewise. >> (emit_mode_inner_inline): Likewise. >> (emit_mode_unit_size_inline): Likewise. >> (emit_mode_unit_precision_inline): Likewise. >> * tree-vrp.c (compare_case_label_values): New qsort callback. >> (find_switch_asserts): Register edge assertions for >> the default label, which correspond to the anti-range 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. > > Here's another version of the patch, which has the following changes: > > 1. Use wide-int arithmetic directly instead of tree arithmetic. > 2. Don't bother re-sorting and re-using the ci vector. Instead just > inspect gimple_switch_label() directly since cases are already sorted > there by CASE_LOW. > 3. Add an insertion limit of 10 and a tunable param. > > Bootstrapped + regtested on x86_64-pc-linux-gnu. Ok. The only thing I wonder is whether VRP does a good job combining non-adjacent anti-ranges or if the result is sth non-sensible. ISTR VRP simply chooses A when combining A and B which would mean inserting asserts will only provide better ranges for more than one asserts via equivalences (which might be good enough, of course). I think the anti-range merge behavior is good but I for example wonder about the behavior for ~[0, n] which will end up as [n, +INF] for unsigned. Also the combining limitation will make ranges derived from the switch parameter less useful, like switch (x) { .... default: x++; .... where x++ will only be derived from the merged anti-range. All these are existing VRP range representation limitations of course. Thanks, Richard. > gcc/ChangeLog: > > PR tree-optimization/18046 > * genmodes.c (emit_mode_size_inline): Emit an assert that > verifies that mode is a valid array index. > (emit_mode_nuinits_inline): Likewise. > (emit_mode_inner_inline): Likewise. > (emit_mode_unit_size_inline): Likewise. > (emit_mode_unit_precision_inline): Likewise. > * tree-vrp.c: Include params.h. > (find_switch_asserts): Register edge assertions for the default > label which correspond to the anti-ranges of each non-case > label. > * params.def (PARAM_MAX_VRP_SWITCH_ASSERTIONS): New. > * doc/invoke.texi: Document it. > > 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/doc/invoke.texi | 4 ++ > gcc/genmodes.c | 5 ++ > gcc/params.def | 6 +++ > 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 | 36 ++++++++++++++ > gcc/tree-vrp.c | 62 +++++++++++++++++++++++- > 7 files changed, 142 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/doc/invoke.texi b/gcc/doc/invoke.texi > index 9e0f07e..6eeecc4 100644 > --- a/gcc/doc/invoke.texi > +++ b/gcc/doc/invoke.texi > @@ -9774,6 +9774,10 @@ enable it. > The maximum number of may-defs we analyze when looking for a must-def > specifying the dynamic type of an object that invokes a virtual call > we may be able to devirtualize speculatively. > + > +@item max-vrp-switch-assertions > +The maximum number of assertions to add along the default edge of a switch > +statement during VRP. The default is 10. > @end table > @end table > > diff --git a/gcc/genmodes.c b/gcc/genmodes.c > index 097cc80..1170d4f 100644 > --- a/gcc/genmodes.c > +++ b/gcc/genmodes.c > @@ -976,6 +976,7 @@ unsigned char\n\ > mode_size_inline (machine_mode mode)\n\ > {\n\ > extern %sunsigned char mode_size[NUM_MACHINE_MODES];\n\ > + gcc_assert (mode >= 0 && mode < NUM_MACHINE_MODES);\n\ > switch (mode)\n\ > {\n", adj_bytesize ? "" : "const "); > > @@ -1006,6 +1007,7 @@ unsigned char\n\ > mode_nunits_inline (machine_mode mode)\n\ > {\n\ > extern const unsigned char mode_nunits[NUM_MACHINE_MODES];\n\ > + gcc_assert (mode >= 0 && mode < NUM_MACHINE_MODES);\n\ > switch (mode)\n\ > {"); > > @@ -1035,6 +1037,7 @@ unsigned char\n\ > mode_inner_inline (machine_mode mode)\n\ > {\n\ > extern const unsigned char mode_inner[NUM_MACHINE_MODES];\n\ > + gcc_assert (mode >= 0 && mode < NUM_MACHINE_MODES);\n\ > switch (mode)\n\ > {"); > > @@ -1067,6 +1070,7 @@ mode_unit_size_inline (machine_mode mode)\n\ > {\n\ > extern CONST_MODE_UNIT_SIZE unsigned char mode_unit_size[NUM_MACHINE_MODES];\ > \n\ > + gcc_assert (mode >= 0 && mode < NUM_MACHINE_MODES);\n\ > switch (mode)\n\ > {"); > > @@ -1103,6 +1107,7 @@ unsigned short\n\ > mode_unit_precision_inline (machine_mode mode)\n\ > {\n\ > extern const unsigned short mode_unit_precision[NUM_MACHINE_MODES];\n\ > + gcc_assert (mode >= 0 && mode < NUM_MACHINE_MODES);\n\ > switch (mode)\n\ > {"); > > diff --git a/gcc/params.def b/gcc/params.def > index 166032e..79b7dd4 100644 > --- a/gcc/params.def > +++ b/gcc/params.def > @@ -1246,6 +1246,12 @@ DEFPARAM (PARAM_MAX_SPECULATIVE_DEVIRT_MAYDEFS, > "Maximum number of may-defs visited when devirtualizing " > "speculatively", 50, 0, 0) > > +DEFPARAM (PARAM_MAX_VRP_SWITCH_ASSERTIONS, > + "max-vrp-switch-assertions", > + "Maximum number of assertions to add along the default " > + "edge of a switch statement during VRP", > + 10, 0, 0) > + > /* > > Local variables: > 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..73dac36 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c > @@ -0,0 +1,36 @@ > +/* PR tree-optimization/18046 */ > +/* { dg-options "-O2 -fdump-tree-optimized" } */ > +/* { dg-final { scan-tree-dump-times "switch" 1 "optimized" } } */ > + > +void foo (); > +void bar (); > +void baz (); > + > +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; > + case 2: > + baz (); > + break; > + default: > + break; > + } > +} > diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c > index 1abc99a..77c3014 100644 > --- a/gcc/tree-vrp.c > +++ b/gcc/tree-vrp.c > @@ -58,6 +58,7 @@ along with GCC; see the file COPYING3. If not see > #include "omp-low.h" > #include "target.h" > #include "case-cfn-macros.h" > +#include "params.h" > > /* Range of values that can be associated with an SSA_NAME after VRP > has executed. */ > @@ -5919,6 +5920,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) > @@ -5947,8 +5949,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; > > @@ -5966,6 +5968,62 @@ find_switch_asserts (basic_block bb, gswitch *last) > } > > XDELETEVEC (ci); > + > + if (!live_on_edge (default_edge, op)) > + return; > + > + /* Now register along the default label assertions that correspond to the > + anti-range of each label. */ > + int insertion_limit = PARAM_VALUE (PARAM_MAX_VRP_SWITCH_ASSERTIONS); > + for (idx = 1; idx < n; idx++) > + { > + tree min, max; > + tree cl = gimple_switch_label (last, idx); > + > + min = CASE_LOW (cl); > + max = CASE_HIGH (cl); > + > + /* Combine contiguous case ranges to reduce the number of assertions > + to insert. */ > + for (idx = idx + 1; idx < n; idx++) > + { > + tree next_min, next_max; > + tree next_cl = gimple_switch_label (last, idx); > + > + next_min = CASE_LOW (next_cl); > + next_max = CASE_HIGH (next_cl); > + > + wide_int difference = wi::sub (next_min, max ? max : min); > + if (wi::eq_p (difference, 1)) > + max = next_max ? next_max : next_min; > + else > + break; > + } > + idx--; > + > + 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); > + } > + > + if (--insertion_limit == 0) > + break; > + } > } > > > -- > 2.9.2.413.g76d2a70
On Mon, Jul 25, 2016 at 6:00 AM, Richard Biener <richard.guenther@gmail.com> wrote: > On Mon, Jul 25, 2016 at 5:38 AM, Patrick Palka <patrick@parcs.ath.cx> wrote: >> On Fri, 22 Jul 2016, Patrick Palka wrote: >> >>> On Fri, 22 Jul 2016, Patrick Palka wrote: >>> >>> > 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. >>> > >>> >>> The patch failed to bootstrap due to a number -Warray-bounds warnings >>> getting emitted for the autogenerated header file insn-modes.h: >>> >>> In file included from /home/patrick/code/gcc/gcc/machmode.h:24:0, >>> from /home/patrick/code/gcc/gcc/coretypes.h:391, >>> from /home/patrick/code/gcc/gcc/lto-streamer-out.c:25: >>> ./insn-modes.h: In function ‘void produce_asm_for_decls()’: >>> ./insn-modes.h:638:36: warning: array subscript is outside array bounds [-Warray-bounds] >>> default: return mode_inner[mode]; >>> ~~~~~~~~~~~~~~~^ >>> >>> These new warnings seem legitimate. From what I can tell, this array >>> access along the default switch label will always be out of bounds. The >>> code it's warning about basically looks like this: >>> >>> enum A { a, b, c }; >>> int foo (A i) >>> { >>> int array[3]; >>> switch (i) >>> { >>> case a: return x; >>> case b: return y; >>> case c: return z; >>> default: return array[i]; >>> } >>> } >>> >>> and while the switch does exhaust every possible enumeration value of A, >>> there's nothing stopping the user from passing an arbitrary int to >>> foo() thus triggering the default case. So this patch suppresses these >>> warnings by making genemit emit an assertion that verifies that mode is >>> within the bounds of the array. This assertion won't affect performance >>> because the mode_*_inline functions are always called with constant >>> arguments. >>> >>> This version of the patch has the following changes: >>> >>> 1. Fixes the bootstrap failure as mentioned above. >>> 2. Checks if the switch operand is live along the default edge before >>> registering assertions. >>> 3. Combines contiguous case ranges to reduce the number of assert >>> expressions to insert. >>> >>> Bootstrap + regtesting in progress on x86_64-pc-linux-gnu. >>> >>> gcc/ChangeLog: >>> >>> PR tree-optimization/18046 >>> * genmodes.c (emit_mode_size_inline): Emit an assert that >>> verifies that mode is a valid array index. >>> (emit_mode_nuinits_inline): Likewise. >>> (emit_mode_inner_inline): Likewise. >>> (emit_mode_unit_size_inline): Likewise. >>> (emit_mode_unit_precision_inline): Likewise. >>> * tree-vrp.c (compare_case_label_values): New qsort callback. >>> (find_switch_asserts): Register edge assertions for >>> the default label, which correspond to the anti-range 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. >> >> Here's another version of the patch, which has the following changes: >> >> 1. Use wide-int arithmetic directly instead of tree arithmetic. >> 2. Don't bother re-sorting and re-using the ci vector. Instead just >> inspect gimple_switch_label() directly since cases are already sorted >> there by CASE_LOW. >> 3. Add an insertion limit of 10 and a tunable param. >> >> Bootstrapped + regtested on x86_64-pc-linux-gnu. > > Ok. > > The only thing I wonder is whether VRP does a good job combining > non-adjacent anti-ranges or if the result is sth non-sensible. ISTR > VRP simply chooses A when combining A and B which would mean > inserting asserts will only provide better ranges for more than one > asserts via equivalences (which might be good enough, of course). Yeah, the shadowed asserts remain useful via equivalences. > I think the anti-range merge behavior is good but I for example wonder > about the behavior for ~[0, n] which will end up as [n, +INF] for > unsigned. Yes but that's fine right? (If you meant [n+1, +INF]) > Also the combining limitation will make ranges derived > from the switch parameter less useful, like > > switch (x) > { > .... > default: > x++; > .... > > where x++ will only be derived from the merged anti-range. Yeah that's pretty unfortunate.. BTW, when looking at what VRP does with such code I noticed another deficiency for which I filed PR 72443. Thanks for reviewing!
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 9e0f07e..6eeecc4 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -9774,6 +9774,10 @@ enable it. The maximum number of may-defs we analyze when looking for a must-def specifying the dynamic type of an object that invokes a virtual call we may be able to devirtualize speculatively. + +@item max-vrp-switch-assertions +The maximum number of assertions to add along the default edge of a switch +statement during VRP. The default is 10. @end table @end table diff --git a/gcc/genmodes.c b/gcc/genmodes.c index 097cc80..1170d4f 100644 --- a/gcc/genmodes.c +++ b/gcc/genmodes.c @@ -976,6 +976,7 @@ unsigned char\n\ mode_size_inline (machine_mode mode)\n\ {\n\ extern %sunsigned char mode_size[NUM_MACHINE_MODES];\n\ + gcc_assert (mode >= 0 && mode < NUM_MACHINE_MODES);\n\ switch (mode)\n\ {\n", adj_bytesize ? "" : "const "); @@ -1006,6 +1007,7 @@ unsigned char\n\ mode_nunits_inline (machine_mode mode)\n\ {\n\ extern const unsigned char mode_nunits[NUM_MACHINE_MODES];\n\ + gcc_assert (mode >= 0 && mode < NUM_MACHINE_MODES);\n\ switch (mode)\n\ {"); @@ -1035,6 +1037,7 @@ unsigned char\n\ mode_inner_inline (machine_mode mode)\n\ {\n\ extern const unsigned char mode_inner[NUM_MACHINE_MODES];\n\ + gcc_assert (mode >= 0 && mode < NUM_MACHINE_MODES);\n\ switch (mode)\n\ {"); @@ -1067,6 +1070,7 @@ mode_unit_size_inline (machine_mode mode)\n\ {\n\ extern CONST_MODE_UNIT_SIZE unsigned char mode_unit_size[NUM_MACHINE_MODES];\ \n\ + gcc_assert (mode >= 0 && mode < NUM_MACHINE_MODES);\n\ switch (mode)\n\ {"); @@ -1103,6 +1107,7 @@ unsigned short\n\ mode_unit_precision_inline (machine_mode mode)\n\ {\n\ extern const unsigned short mode_unit_precision[NUM_MACHINE_MODES];\n\ + gcc_assert (mode >= 0 && mode < NUM_MACHINE_MODES);\n\ switch (mode)\n\ {"); diff --git a/gcc/params.def b/gcc/params.def index 166032e..79b7dd4 100644 --- a/gcc/params.def +++ b/gcc/params.def @@ -1246,6 +1246,12 @@ DEFPARAM (PARAM_MAX_SPECULATIVE_DEVIRT_MAYDEFS, "Maximum number of may-defs visited when devirtualizing " "speculatively", 50, 0, 0) +DEFPARAM (PARAM_MAX_VRP_SWITCH_ASSERTIONS, + "max-vrp-switch-assertions", + "Maximum number of assertions to add along the default " + "edge of a switch statement during VRP", + 10, 0, 0) + /* Local variables: 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..73dac36 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c @@ -0,0 +1,36 @@ +/* PR tree-optimization/18046 */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* { dg-final { scan-tree-dump-times "switch" 1 "optimized" } } */ + +void foo (); +void bar (); +void baz (); + +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; + case 2: + baz (); + break; + default: + break; + } +} diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 1abc99a..77c3014 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -58,6 +58,7 @@ along with GCC; see the file COPYING3. If not see #include "omp-low.h" #include "target.h" #include "case-cfn-macros.h" +#include "params.h" /* Range of values that can be associated with an SSA_NAME after VRP has executed. */ @@ -5919,6 +5920,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) @@ -5947,8 +5949,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; @@ -5966,6 +5968,62 @@ find_switch_asserts (basic_block bb, gswitch *last) } XDELETEVEC (ci); + + if (!live_on_edge (default_edge, op)) + return; + + /* Now register along the default label assertions that correspond to the + anti-range of each label. */ + int insertion_limit = PARAM_VALUE (PARAM_MAX_VRP_SWITCH_ASSERTIONS); + for (idx = 1; idx < n; idx++) + { + tree min, max; + tree cl = gimple_switch_label (last, idx); + + min = CASE_LOW (cl); + max = CASE_HIGH (cl); + + /* Combine contiguous case ranges to reduce the number of assertions + to insert. */ + for (idx = idx + 1; idx < n; idx++) + { + tree next_min, next_max; + tree next_cl = gimple_switch_label (last, idx); + + next_min = CASE_LOW (next_cl); + next_max = CASE_HIGH (next_cl); + + wide_int difference = wi::sub (next_min, max ? max : min); + if (wi::eq_p (difference, 1)) + max = next_max ? next_max : next_min; + else + break; + } + idx--; + + 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); + } + + if (--insertion_limit == 0) + break; + } }