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 <patr...@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.
