[PATCH] Teach VRP to truncate the case ranges of a switch

Patrick Palka patrick@parcs.ath.cx
Thu Aug 4 02:30:00 GMT 2016


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.



More information about the Gcc-patches mailing list