On Thu, 4 Aug 2016, Richard Biener wrote:
> On Thu, Aug 4, 2016 at 4:30 AM, Patrick Palka <patr...@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 <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.
>
> 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
