[PATCH] Teach VRP to truncate the case ranges of a switch
Richard Biener
richard.guenther@gmail.com
Thu Aug 4 13:41:00 GMT 2016
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
>
>
More information about the Gcc-patches
mailing list