On Mon, Jul 25, 2016 at 5:38 AM, Patrick Palka <[email protected]> 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
