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

[Patrick Palka <patrick@parcs.ath.cx>]

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?

-- >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