[PATCH] Fix assertions along default switch labels (PR tree-optimization/78819)

[PATCH] Fix assertions along default switch labels (PR tree-optimization/78819)

[Marek Polacek]

Starting with r238761, we register assertions for default switch labels;
these assertions correspond to the anti-range of each case label.  It
means that we can optimize this better:

  switch (i) {
    case 1: case 2: case 3:
      ...
      break;
    default:
      // i is ~[1, 3]
      if (i == 2) // fold to 0
	...
  }

But as this testcase shows, this breaks when the default label shares a label
with another case.  On this testcase, when we reach the switch, we know that
argc is either 1, 2, or 3.  So by the time we reach vrp2, the IR will have
been optimized to

  switch (argc) {
    default:
    case 3:
      // argc will be considered 1 despite the case 3
      break;
    case 2:
      ...
   }

Now, the assertion for argc in default: is that it's ~[2,3].  Since argc had
been proved to be either 1, 2, or 3, we optimized it to 1.  Given the
consecutive case 3: this is incorrect.

So ignore the range when a case label is "shared" with the default case.

Another bug: --param max-vrp-switch-assertions=0 didn't work -- we register
the assertion and then there's this check

  if (--insertion_limit == 0)
    break;

but given the decrement this isn't true so we'd kept going.

Bootstrapped/regtested on x86_64-linux, ok for trunk?

2016-12-16  Marek Polacek  <polacek@redhat.com>

	PR tree-optimization/78819
	* tree-vrp.c (find_switch_asserts): Return if the insertion limit is 0.
	Don't register an assertion if the default case shares a label with
	another case.

	* gcc.dg/tree-ssa/vrp112.c: New test.

diff --git gcc/testsuite/gcc.dg/tree-ssa/vrp112.c gcc/testsuite/gcc.dg/tree-ssa/vrp112.c
index e69de29..fdc6711 100644
--- gcc/testsuite/gcc.dg/tree-ssa/vrp112.c
+++ gcc/testsuite/gcc.dg/tree-ssa/vrp112.c
@@ -0,0 +1,31 @@
+/* PR tree-optimization/78819 */
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+__attribute__((noinline, noclone)) void
+foo (int argc)
+{
+  if (argc <= 0 || argc > 3)
+    return;
+
+  switch (argc)
+    {
+    case 1:
+    case 3:
+      if (argc != 3)
+	__builtin_abort ();
+      break;
+    case 2:
+      asm ("");
+      break;
+    default:
+      __builtin_abort ();
+    }
+}
+
+int
+main (void)
+{
+  foo (3);
+  return 0;
+}
diff --git gcc/tree-vrp.c gcc/tree-vrp.c
index 97e9953..405469a 100644
--- gcc/tree-vrp.c
+++ gcc/tree-vrp.c
@@ -6051,10 +6051,17 @@ find_switch_asserts (basic_block bb, gswitch *last)
   /* Now register along the default label assertions that correspond to the
      anti-range of each label.  */
   int insertion_limit = PARAM_VALUE (PARAM_MAX_VRP_SWITCH_ASSERTIONS);
+  if (insertion_limit == 0)
+    return;
+
+  /* We can't do this if the default case shares a label with another case.  */
+  tree default_cl = gimple_switch_default_label (last);
   for (idx = 1; idx < n; idx++)
     {
       tree min, max;
       tree cl = gimple_switch_label (last, idx);
+      if (CASE_LABEL (cl) == CASE_LABEL (default_cl))
+	break;
 
       min = CASE_LOW (cl);
       max = CASE_HIGH (cl);
@@ -6065,6 +6072,8 @@ find_switch_asserts (basic_block bb, gswitch *last)
 	{
 	  tree next_min, next_max;
 	  tree next_cl = gimple_switch_label (last, idx);
+	  if (CASE_LABEL (next_cl) == CASE_LABEL (default_cl))
+	    break;
 
 	  next_min = CASE_LOW (next_cl);
 	  next_max = CASE_HIGH (next_cl);

	Marek

Re: [PATCH] Fix assertions along default switch labels (PR tree-optimization/78819)

[Richard Biener]

On Fri, Dec 16, 2016 at 12:49 PM, Marek Polacek <polacek@redhat.com> wrote:
> Starting with r238761, we register assertions for default switch labels;
> these assertions correspond to the anti-range of each case label.  It
> means that we can optimize this better:
>
>   switch (i) {
>     case 1: case 2: case 3:
>       ...
>       break;
>     default:
>       // i is ~[1, 3]
>       if (i == 2) // fold to 0
>         ...
>   }
>
> But as this testcase shows, this breaks when the default label shares a label
> with another case.  On this testcase, when we reach the switch, we know that
> argc is either 1, 2, or 3.  So by the time we reach vrp2, the IR will have
> been optimized to
>
>   switch (argc) {
>     default:
>     case 3:
>       // argc will be considered 1 despite the case 3
>       break;
>     case 2:
>       ...
>    }
>
> Now, the assertion for argc in default: is that it's ~[2,3].  Since argc had
> been proved to be either 1, 2, or 3, we optimized it to 1.  Given the
> consecutive case 3: this is incorrect.
>
> So ignore the range when a case label is "shared" with the default case.
>
> Another bug: --param max-vrp-switch-assertions=0 didn't work -- we register
> the assertion and then there's this check
>
>   if (--insertion_limit == 0)
>     break;
>
> but given the decrement this isn't true so we'd kept going.
>
> Bootstrapped/regtested on x86_64-linux, ok for trunk?
>
> 2016-12-16  Marek Polacek  <polacek@redhat.com>
>
>         PR tree-optimization/78819
>         * tree-vrp.c (find_switch_asserts): Return if the insertion limit is 0.
>         Don't register an assertion if the default case shares a label with
>         another case.
>
>         * gcc.dg/tree-ssa/vrp112.c: New test.
>
> diff --git gcc/testsuite/gcc.dg/tree-ssa/vrp112.c gcc/testsuite/gcc.dg/tree-ssa/vrp112.c
> index e69de29..fdc6711 100644
> --- gcc/testsuite/gcc.dg/tree-ssa/vrp112.c
> +++ gcc/testsuite/gcc.dg/tree-ssa/vrp112.c
> @@ -0,0 +1,31 @@
> +/* PR tree-optimization/78819 */
> +/* { dg-do run } */
> +/* { dg-options "-O2" } */
> +
> +__attribute__((noinline, noclone)) void
> +foo (int argc)
> +{
> +  if (argc <= 0 || argc > 3)
> +    return;
> +
> +  switch (argc)
> +    {
> +    case 1:
> +    case 3:
> +      if (argc != 3)
> +       __builtin_abort ();
> +      break;
> +    case 2:
> +      asm ("");
> +      break;
> +    default:
> +      __builtin_abort ();
> +    }
> +}
> +
> +int
> +main (void)
> +{
> +  foo (3);
> +  return 0;
> +}
> diff --git gcc/tree-vrp.c gcc/tree-vrp.c
> index 97e9953..405469a 100644
> --- gcc/tree-vrp.c
> +++ gcc/tree-vrp.c
> @@ -6051,10 +6051,17 @@ find_switch_asserts (basic_block bb, gswitch *last)
>    /* Now register along the default label assertions that correspond to the
>       anti-range of each label.  */
>    int insertion_limit = PARAM_VALUE (PARAM_MAX_VRP_SWITCH_ASSERTIONS);
> +  if (insertion_limit == 0)
> +    return;
> +
> +  /* We can't do this if the default case shares a label with another case.  */
> +  tree default_cl = gimple_switch_default_label (last);
>    for (idx = 1; idx < n; idx++)
>      {
>        tree min, max;
>        tree cl = gimple_switch_label (last, idx);
> +      if (CASE_LABEL (cl) == CASE_LABEL (default_cl))
> +       break;

It's conservative to break here but don't you actually want to continue instead?

>        min = CASE_LOW (cl);
>        max = CASE_HIGH (cl);
> @@ -6065,6 +6072,8 @@ find_switch_asserts (basic_block bb, gswitch *last)
>         {
>           tree next_min, next_max;
>           tree next_cl = gimple_switch_label (last, idx);
> +         if (CASE_LABEL (next_cl) == CASE_LABEL (default_cl))
> +           break;

here the break is of course correct.

Ok with that change.

Thanks,
Richard.

>           next_min = CASE_LOW (next_cl);
>           next_max = CASE_HIGH (next_cl);
>
>         Marek

Re: [PATCH] Fix assertions along default switch labels (PR tree-optimization/78819)

[Marek Polacek]

On Fri, Dec 16, 2016 at 02:00:56PM +0100, Richard Biener wrote:
> On Fri, Dec 16, 2016 at 12:49 PM, Marek Polacek <polacek@redhat.com> wrote:
> > --- gcc/tree-vrp.c
> > +++ gcc/tree-vrp.c
> > @@ -6051,10 +6051,17 @@ find_switch_asserts (basic_block bb, gswitch *last)
> >    /* Now register along the default label assertions that correspond to the
> >       anti-range of each label.  */
> >    int insertion_limit = PARAM_VALUE (PARAM_MAX_VRP_SWITCH_ASSERTIONS);
> > +  if (insertion_limit == 0)
> > +    return;
> > +
> > +  /* We can't do this if the default case shares a label with another case.  */
> > +  tree default_cl = gimple_switch_default_label (last);
> >    for (idx = 1; idx < n; idx++)
> >      {
> >        tree min, max;
> >        tree cl = gimple_switch_label (last, idx);
> > +      if (CASE_LABEL (cl) == CASE_LABEL (default_cl))
> > +       break;
> 
> It's conservative to break here but don't you actually want to continue instead?
 
Right, that should be safe and generate better range info for the default
label.

> >        min = CASE_LOW (cl);
> >        max = CASE_HIGH (cl);
> > @@ -6065,6 +6072,8 @@ find_switch_asserts (basic_block bb, gswitch *last)
> >         {
> >           tree next_min, next_max;
> >           tree next_cl = gimple_switch_label (last, idx);
> > +         if (CASE_LABEL (next_cl) == CASE_LABEL (default_cl))
> > +           break;
> 
> here the break is of course correct.
> 
> Ok with that change.

Thanks,

	Marek

Re: [PATCH] Fix assertions along default switch labels (PR tree-optimization/78819)

[Bernd Schmidt]

On 12/16/2016 12:49 PM, Marek Polacek wrote:

> But as this testcase shows, this breaks when the default label shares a label
> with another case.  On this testcase, when we reach the switch, we know that
> argc is either 1, 2, or 3.  So by the time we reach vrp2, the IR will have
> been optimized to
>
>   switch (argc) {
>     default:
>     case 3:
>       // argc will be considered 1 despite the case 3
>       break;
>     case 2:
>       ...
>    }

Shouldn't we just remove the "case 3:" from the switch in this case? 
Would that fix things?


Bernd

Re: [PATCH] Fix assertions along default switch labels (PR tree-optimization/78819)

[Richard Biener]

On Fri, Dec 16, 2016 at 2:03 PM, Bernd Schmidt <bschmidt@redhat.com> wrote:
> On 12/16/2016 12:49 PM, Marek Polacek wrote:
>
>> But as this testcase shows, this breaks when the default label shares a
>> label
>> with another case.  On this testcase, when we reach the switch, we know
>> that
>> argc is either 1, 2, or 3.  So by the time we reach vrp2, the IR will have
>> been optimized to
>>
>>   switch (argc) {
>>     default:
>>     case 3:
>>       // argc will be considered 1 despite the case 3
>>       break;
>>     case 2:
>>       ...
>>    }
>
>
> Shouldn't we just remove the "case 3:" from the switch in this case? Would
> that fix things?

We probably should indeed.  But can we rely on this?

Richard.

>
> Bernd

Re: [PATCH] Fix assertions along default switch labels (PR tree-optimization/78819)

[Marek Polacek]

On Fri, Dec 16, 2016 at 02:58:59PM +0100, Richard Biener wrote:
> On Fri, Dec 16, 2016 at 2:03 PM, Bernd Schmidt <bschmidt@redhat.com> wrote:
> > On 12/16/2016 12:49 PM, Marek Polacek wrote:
> >
> >> But as this testcase shows, this breaks when the default label shares a
> >> label
> >> with another case.  On this testcase, when we reach the switch, we know
> >> that
> >> argc is either 1, 2, or 3.  So by the time we reach vrp2, the IR will have
> >> been optimized to
> >>
> >>   switch (argc) {
> >>     default:
> >>     case 3:
> >>       // argc will be considered 1 despite the case 3
> >>       break;
> >>     case 2:
> >>       ...
> >>    }
> >
> >
> > Shouldn't we just remove the "case 3:" from the switch in this case? Would
> > that fix things?
> 
> We probably should indeed.  But can we rely on this?

I think we should do both -- apply my fix + investigated why we kept case 3
around.  I'm willing to look into this.

	Marek

Re: [PATCH] Fix assertions along default switch labels (PR tree-optimization/78819)

[Richard Biener]

On Fri, Dec 16, 2016 at 3:16 PM, Marek Polacek <polacek@redhat.com> wrote:
> On Fri, Dec 16, 2016 at 02:58:59PM +0100, Richard Biener wrote:
>> On Fri, Dec 16, 2016 at 2:03 PM, Bernd Schmidt <bschmidt@redhat.com> wrote:
>> > On 12/16/2016 12:49 PM, Marek Polacek wrote:
>> >
>> >> But as this testcase shows, this breaks when the default label shares a
>> >> label
>> >> with another case.  On this testcase, when we reach the switch, we know
>> >> that
>> >> argc is either 1, 2, or 3.  So by the time we reach vrp2, the IR will have
>> >> been optimized to
>> >>
>> >>   switch (argc) {
>> >>     default:
>> >>     case 3:
>> >>       // argc will be considered 1 despite the case 3
>> >>       break;
>> >>     case 2:
>> >>       ...
>> >>    }
>> >
>> >
>> > Shouldn't we just remove the "case 3:" from the switch in this case? Would
>> > that fix things?
>>
>> We probably should indeed.  But can we rely on this?
>
> I think we should do both -- apply my fix + investigated why we kept case 3
> around.  I'm willing to look into this.

Agreed.  (my original approval still holds)

Richard.

>         Marek

Re: [PATCH] Fix assertions along default switch labels (PR tree-optimization/78819)

[Marek Polacek]

On Fri, Dec 16, 2016 at 03:16:14PM +0100, Marek Polacek wrote:
> On Fri, Dec 16, 2016 at 02:58:59PM +0100, Richard Biener wrote:
> > On Fri, Dec 16, 2016 at 2:03 PM, Bernd Schmidt <bschmidt@redhat.com> wrote:
> > > On 12/16/2016 12:49 PM, Marek Polacek wrote:
> > >
> > >> But as this testcase shows, this breaks when the default label shares a
> > >> label
> > >> with another case.  On this testcase, when we reach the switch, we know
> > >> that
> > >> argc is either 1, 2, or 3.  So by the time we reach vrp2, the IR will have
> > >> been optimized to
> > >>
> > >>   switch (argc) {
> > >>     default:
> > >>     case 3:
> > >>       // argc will be considered 1 despite the case 3
> > >>       break;
> > >>     case 2:
> > >>       ...
> > >>    }
> > >
> > >
> > > Shouldn't we just remove the "case 3:" from the switch in this case? Would
> > > that fix things?
> > 
> > We probably should indeed.  But can we rely on this?
> 
> I think we should do both -- apply my fix + investigated why we kept case 3
> around.  I'm willing to look into this.

This is work of simplify_switch_using_ranges and then
11293   /* Update SWITCH_EXPR case label vector.  */
11294   FOR_EACH_VEC_ELT (to_update_switch_stmts, i, su)
11295     {
11296       size_t j;
11297       size_t n = TREE_VEC_LENGTH (su->vec);
11298       tree label;
11299       gimple_switch_set_num_labels (su->stmt, n);
11300       for (j = 0; j < n; j++)
11301         gimple_switch_set_label (su->stmt, j, TREE_VEC_ELT (su->vec, j));
11302       /* As we may have replaced the default label with a regular one
11303          make sure to make it a real default label again.  This ensures
11304          optimal expansion.  */
11305       label = gimple_switch_label (su->stmt, 0);
11306       CASE_LOW (label) = NULL_TREE;
11307       CASE_HIGH (label) = NULL_TREE;
	    ^^^^^^ this

But only after I wrote a patch I noticed that cfgcleanup merges default: and
case 3: before we reach .optimized, so I think there's nothing to do here.

	Marek