RFC: Patch for switch elimination (PR 54742)

On Tue, 2014-08-12 at 14:40 -0600, Jeff Law wrote:
> On 08/12/14 14:23, Richard Biener wrote:
> > On August 12, 2014 8:31:16 PM CEST, Jeff Law <law@redhat.com> wrote:
> >> Try setting the header & latch fields for the loop structure to NULL,
> >> then call loops_set_state (LOOPS_NEED_FIXUP).
> >
> > But that is _not_ the appropriate way of keeping loops preserved!
> I think that's done when we've scrogged the loop beyond repair and want 
> the structures rebuilt.  IIRC, that's what you recommended we do.
> 
> jeff

Well, I don't know if it is the 'right' thing to do, but it does seem to
work.  Here is a new patch that seems to be working and that also
addresses the comments that Jakub Jelinek had.  I want to do more
testing before I officially submit it but I thought I would put it out
here for others to look over again while I do that.

Steve Ellcey
sellcey@mips.com

2014-08-12  Steve Ellcey  <sellcey@mips.com>

	PR tree-opt/54742
	* Makefile.in (OBJS): Add tree-switch-shortcut.o.
	* common.opt (ftree-switch-shortcut): New.
	* opts.c (default_options_table): Add OPT_ftree_switch_shortcut.
	* params.def (PARAM_MAX_SWITCH_INSNS): New.
	(PARAM_MAX_SWITCH_PATHS): New.
	* passes.def (pass_tree_switch_shortcut): New.
	* timevar.def (TV_TREE_SWITCH_SHORTCUT): New.
	* tree-pass.h (make_pass_tree_switch_shortcut): New.
	* tree-switch-shortcut.c: New.

Steve Ellcey wrote:
> +/* This file implements an optimization where, when a variable is set
> +   to a constant value and there is a path that leads from that definition
> +   to a switch statement that uses that variable as its controlling expression
> +   we duplicate the blocks on this path and change the jump to the switch
> +   statement with a direct jump to the label of the switch block that control
> +   would goto based on the value of the variable.  This can come up in
> +   loops/switch statements that implement state machines.

Can you explain why the jump-threading pass cannot do this?  Why do we need
another pass to handle a corner case that jump-thread does not catch yet?

> +
> +   Example (modified from PR 54742):
> +
> +   foo(char *str) {
> +     int sum=0;
> +     int state=0;
> +     char *s=str;
> +     for (; *s; s++) {
> +       char c=*s;
> +       <CODE BLOCK 1>

From what I understand, Jeff has fixed jump-threading to catch exactly the
pattern in this example.  What jump-threading doesn't do yet is duplicate the
path when <CODE BLOCK 1> is a condition, like in the example in comment 27:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=54742#c27
(see the if (c == '*') ):

int sum0, sum1, sum2, sum3;
int foo(char * s, char** ret)
{
  int state=0;
  char c;

  for (; *s && state != 4; s++)
    {
      c = *s;
      if (c == '*')
	{
	  s++;
	  break;
	}
      switch (state) {
	case 0:
	  if (c == '+') state = 1;
	  else if (c != '-') sum0+=c;
	  break;
	case 1:
	  if (c == '+') state = 2;
	  else if (c == '-') state = 0;
	  else sum1+=c;
	  break;
	case 2:
	  if (c == '+') state = 3;
	  else if (c == '-') state = 1;
	  else sum2+=c;
	  break;
	case 3:
	  if (c == '-') state = 2;
	  else if (c == 'x') state = 4;
	  break;
	default:
	  break;
      }
    }
  *ret = s;
  return state;
}


> +       switch (state) {
> +         case 0:
> +           if (c == '+')       { state = 1; sum += 9; }
> +           else if (c != '-')  { state = 2; sum += 3; }
> +           break;
> +         case 1:
> +           if (c == '+')       { state = 2; sum += 4; }
> +           else if (c == '-')  { state = 0; sum += 7; }
> +           break;
> +         case 2:
> +           if (c == '+')       { state = 0; sum += 8; }
> +           else if (c == '-')  { state = 1; sum += 2; }
> +           break;
> +       }
> +       <CODE BLOCK 2>
> +     }
> +     return state;
> +   }
> +
> +  This pass will convert the code inside 'case 0' to something like:
> +
> +    case 0:
> +      if (c == '+')      { state = 1; sum += 9;
> +                           <CODE BLOCK 2>
> +                           s++; if (!s) goto loop_exit;
> +                           <CODE BLOCK 1>
> +                           goto case_1; }
> +      else if (c != '-') { state = 2; sum += 3;
> +                           <CODE BLOCK 2>
> +                           s++; if (!s) goto loop_exit;
> +                           <CODE BLOCK 1>
> +                           goto case_2; }
> +      else               { <CODE BLOCK 2>
> +			   s++; if (!s) goto exit;
> +                           <CODE BLOCK 1>
> +                           goto case_0; }
> +
> +Similar transformations would apply to the other parts of the switch
> +statement.  This obviously can lead to a lot of code duplication but
> +it can also result in faster code since we are replacing two jumps
> +(one indirect) with a single direct jump.  */

On 08/13/14 14:55, Sebastian Pop wrote:
> Steve Ellcey wrote:
>> +/* This file implements an optimization where, when a variable is set
>> +   to a constant value and there is a path that leads from that definition
>> +   to a switch statement that uses that variable as its controlling expression
>> +   we duplicate the blocks on this path and change the jump to the switch
>> +   statement with a direct jump to the label of the switch block that control
>> +   would goto based on the value of the variable.  This can come up in
>> +   loops/switch statements that implement state machines.
>
> Can you explain why the jump-threading pass cannot do this?  Why do we need
> another pass to handle a corner case that jump-thread does not catch yet?
I'm pretty sure jump threading *could* handle it, but after looking at 
the full testcase when it was posted, I'm not sure it's *wise* to handle 
this in jump threading.

The core issue is we have to look even deeper into the CFG than was 
originally envisioned and do quite a bit more block duplication than was 
originally envisioned.  That's going to have a notable compile-time cost 
(and to a lesser extent issues around codesize).

It's unfortunate that the testcase when we first looked at this was 
over-simplified and not actually representative of what happens in 
Coremark.  Had I seen the Coremark testcase, I probably wouldn't have 
suggested we tackle the problem in jump threading and the extensions I 
made to jump threading would _not_ have included aggressively following 
backedges in the CFG.

You'll note in a separate thread Steve and I discussed this during 
Cauldron and it was at my recommendation Steve resurrected his proof of 
concept plugin and started beating it into shape.

jeff

Jeff Law wrote:
> I'm pretty sure jump threading *could* handle it, but after looking
> at the full testcase when it was posted, I'm not sure it's *wise* to
> handle this in jump threading.

Thanks for clearing my doubts.

Sebastian

On Wed, Aug 13, 2014 at 11:06 PM, Jeff Law <law@redhat.com> wrote:
> On 08/13/14 14:55, Sebastian Pop wrote:
>>
>> Steve Ellcey wrote:
>>>
>>> +/* This file implements an optimization where, when a variable is set
>>> +   to a constant value and there is a path that leads from that
>>> definition
>>> +   to a switch statement that uses that variable as its controlling
>>> expression
>>> +   we duplicate the blocks on this path and change the jump to the
>>> switch
>>> +   statement with a direct jump to the label of the switch block that
>>> control
>>> +   would goto based on the value of the variable.  This can come up in
>>> +   loops/switch statements that implement state machines.
>>
>>
>> Can you explain why the jump-threading pass cannot do this?  Why do we
>> need
>> another pass to handle a corner case that jump-thread does not catch yet?
>
> I'm pretty sure jump threading *could* handle it, but after looking at the
> full testcase when it was posted, I'm not sure it's *wise* to handle this in
> jump threading.
>
> The core issue is we have to look even deeper into the CFG than was
> originally envisioned and do quite a bit more block duplication than was
> originally envisioned.  That's going to have a notable compile-time cost
> (and to a lesser extent issues around codesize).
>
> It's unfortunate that the testcase when we first looked at this was
> over-simplified and not actually representative of what happens in Coremark.
> Had I seen the Coremark testcase, I probably wouldn't have suggested we
> tackle the problem in jump threading and the extensions I made to jump
> threading would _not_ have included aggressively following backedges in the
> CFG.
>
> You'll note in a separate thread Steve and I discussed this during Cauldron
> and it was at my recommendation Steve resurrected his proof of concept
> plugin and started beating it into shape.

But do we really want a pass just to help coremark?

Richard.

> jeff
>
>

On 08/14/14 04:32, Richard Biener wrote:
>> You'll note in a separate thread Steve and I discussed this during Cauldron
>> and it was at my recommendation Steve resurrected his proof of concept
>> plugin and started beating it into shape.
>
> But do we really want a pass just to help coremark?
And that's the biggest argument against Steve's work.  In theory it 
should be applicable to other FSMs, but nobody's come forth with 
additional testcases from real world applications.

jeff

On Thu, 2014-08-14 at 09:56 -0600, Jeff Law wrote:
> On 08/14/14 04:32, Richard Biener wrote:
> >> You'll note in a separate thread Steve and I discussed this during Cauldron
> >> and it was at my recommendation Steve resurrected his proof of concept
> >> plugin and started beating it into shape.
> >
> > But do we really want a pass just to help coremark?
> And that's the biggest argument against Steve's work.  In theory it 
> should be applicable to other FSMs, but nobody's come forth with 
> additional testcases from real world applications.

Maybe a regex library?  Perhaps:
http://vcs.pcre.org/viewvc/code/trunk/pcre_dfa_exec.c?revision=1477 ?


Dave

On 08/14/14 10:12, David Malcolm wrote:
> On Thu, 2014-08-14 at 09:56 -0600, Jeff Law wrote:
>> On 08/14/14 04:32, Richard Biener wrote:
>>>> You'll note in a separate thread Steve and I discussed this during Cauldron
>>>> and it was at my recommendation Steve resurrected his proof of concept
>>>> plugin and started beating it into shape.
>>>
>>> But do we really want a pass just to help coremark?
>> And that's the biggest argument against Steve's work.  In theory it
>> should be applicable to other FSMs, but nobody's come forth with
>> additional testcases from real world applications.
>
> Maybe a regex library?  Perhaps:
> http://vcs.pcre.org/viewvc/code/trunk/pcre_dfa_exec.c?revision=1477 ?
The key is that at least some states tell you at compile time what state 
you'll be in during the next loop iteration.  Thus instead of coming 
around the loop, evaluating the switch condition, then doing the 
multi-way branch, we just directly jump to the case for the next iteration.

I've never looked at the PCRE code to know if it's got cases like that.

jeff

On Thu, 2014-08-14 at 10:21 -0600, Jeff Law wrote:
> On 08/14/14 10:12, David Malcolm wrote:
> > On Thu, 2014-08-14 at 09:56 -0600, Jeff Law wrote:
> >> On 08/14/14 04:32, Richard Biener wrote:
> >>>> You'll note in a separate thread Steve and I discussed this during Cauldron
> >>>> and it was at my recommendation Steve resurrected his proof of concept
> >>>> plugin and started beating it into shape.
> >>>
> >>> But do we really want a pass just to help coremark?
> >> And that's the biggest argument against Steve's work.  In theory it
> >> should be applicable to other FSMs, but nobody's come forth with
> >> additional testcases from real world applications.
> >
> > Maybe a regex library?  Perhaps:
> > http://vcs.pcre.org/viewvc/code/trunk/pcre_dfa_exec.c?revision=1477 ?
> The key is that at least some states tell you at compile time what state 
> you'll be in during the next loop iteration.  Thus instead of coming 
> around the loop, evaluating the switch condition, then doing the 
> multi-way branch, we just directly jump to the case for the next iteration.
> 
> I've never looked at the PCRE code to know if it's got cases like that.
> 
> jeff

I compiled PCRE but it never triggered this optimization (even if I
bumped up the parameters for instruction counts and paths).

I understand the desire not to add optimizations just for benchmarks but
we do know other compilers have added this optimization for coremark
(See
http://community.arm.com/groups/embedded/blog/2013/02/21/coremark-and-compiler-performance) and the 13 people on the CC list for this bug certainly shows interest in having it even if it is just for a benchmark.  Does 'competing against other compilers' sound better then 'optimizing for a benchmark'?

Steve Ellcey
sellcey@mips.com

Steve Ellcey wrote:
> I understand the desire not to add optimizations just for benchmarks but
> we do know other compilers have added this optimization for coremark
> (See
> http://community.arm.com/groups/embedded/blog/2013/02/21/coremark-and-compiler-performance)
> and the 13 people on the CC list for this bug certainly shows interest in
> having it even if it is just for a benchmark.  Does 'competing against other
> compilers' sound better then 'optimizing for a benchmark'?

I definitely would like to see GCC trunk do this transform.  What about we
integrate the new pass, and then when jump-threading manages to catch the
coremark loop, we remove the pass?

Thanks,
Sebastian

On Thu, Aug 14, 2014 at 8:45 PM, Sebastian Pop <sebpop@gmail.com> wrote:
> Steve Ellcey wrote:
>> I understand the desire not to add optimizations just for benchmarks but
>> we do know other compilers have added this optimization for coremark
>> (See
>> http://community.arm.com/groups/embedded/blog/2013/02/21/coremark-and-compiler-performance)
>> and the 13 people on the CC list for this bug certainly shows interest in
>> having it even if it is just for a benchmark.  Does 'competing against other
>> compilers' sound better then 'optimizing for a benchmark'?
>
> I definitely would like to see GCC trunk do this transform.  What about we
> integrate the new pass, and then when jump-threading manages to catch the
> coremark loop, we remove the pass?

It never worked that way.

A new pass takes compile-time, if we disable it by default it won't help
coremark (and it will bitrot quickly).

So - please fix DOM instead.

Richard.

> Thanks,
> Sebastian

On Thu, Aug 14, 2014 at 8:25 PM, Steve Ellcey <sellcey@mips.com> wrote:
> On Thu, 2014-08-14 at 10:21 -0600, Jeff Law wrote:
>> On 08/14/14 10:12, David Malcolm wrote:
>> > On Thu, 2014-08-14 at 09:56 -0600, Jeff Law wrote:
>> >> On 08/14/14 04:32, Richard Biener wrote:
>> >>>> You'll note in a separate thread Steve and I discussed this during Cauldron
>> >>>> and it was at my recommendation Steve resurrected his proof of concept
>> >>>> plugin and started beating it into shape.
>> >>>
>> >>> But do we really want a pass just to help coremark?
>> >> And that's the biggest argument against Steve's work.  In theory it
>> >> should be applicable to other FSMs, but nobody's come forth with
>> >> additional testcases from real world applications.
>> >
>> > Maybe a regex library?  Perhaps:
>> > http://vcs.pcre.org/viewvc/code/trunk/pcre_dfa_exec.c?revision=1477 ?
>> The key is that at least some states tell you at compile time what state
>> you'll be in during the next loop iteration.  Thus instead of coming
>> around the loop, evaluating the switch condition, then doing the
>> multi-way branch, we just directly jump to the case for the next iteration.
>>
>> I've never looked at the PCRE code to know if it's got cases like that.
>>
>> jeff
>
> I compiled PCRE but it never triggered this optimization (even if I
> bumped up the parameters for instruction counts and paths).
>
> I understand the desire not to add optimizations just for benchmarks but
> we do know other compilers have added this optimization for coremark
> (See
> http://community.arm.com/groups/embedded/blog/2013/02/21/coremark-and-compiler-performance) and the 13 people on the CC list for this bug certainly shows interest in having it even if it is just for a benchmark.  Does 'competing against other compilers' sound better then 'optimizing for a benchmark'?

Well - as an open-source compiler we have the luxury to not care
about "benchmark compilers" ;)  At least that's what our non-existant
sales-team told me.

There are plenty "real" interpreters around which may have states
that deterministically forward to another state.  If you optimize
those as well, fine.

Btw - the patch doesn't contain a single testcase ....

With coremark being "secret" what's the real-world testcase this
optimizes?  Note that the benchmarks used in SPEC are usually
available and taken from real-world apps.  I don't know coremark
at all, but from its name it sounds like sth like nullstone?

Richard.

> Steve Ellcey
> sellcey@mips.com
>

On Fri, Aug 15, 2014 at 12:13 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Thu, Aug 14, 2014 at 8:25 PM, Steve Ellcey <sellcey@mips.com> wrote:
>> On Thu, 2014-08-14 at 10:21 -0600, Jeff Law wrote:
>>> On 08/14/14 10:12, David Malcolm wrote:
>>> > On Thu, 2014-08-14 at 09:56 -0600, Jeff Law wrote:
>>> >> On 08/14/14 04:32, Richard Biener wrote:
>>> >>>> You'll note in a separate thread Steve and I discussed this during Cauldron
>>> >>>> and it was at my recommendation Steve resurrected his proof of concept
>>> >>>> plugin and started beating it into shape.
>>> >>>
>>> >>> But do we really want a pass just to help coremark?
>>> >> And that's the biggest argument against Steve's work.  In theory it
>>> >> should be applicable to other FSMs, but nobody's come forth with
>>> >> additional testcases from real world applications.
>>> >
>>> > Maybe a regex library?  Perhaps:
>>> > http://vcs.pcre.org/viewvc/code/trunk/pcre_dfa_exec.c?revision=1477 ?
>>> The key is that at least some states tell you at compile time what state
>>> you'll be in during the next loop iteration.  Thus instead of coming
>>> around the loop, evaluating the switch condition, then doing the
>>> multi-way branch, we just directly jump to the case for the next iteration.
>>>
>>> I've never looked at the PCRE code to know if it's got cases like that.
>>>
>>> jeff
>>
>> I compiled PCRE but it never triggered this optimization (even if I
>> bumped up the parameters for instruction counts and paths).
>>
>> I understand the desire not to add optimizations just for benchmarks but
>> we do know other compilers have added this optimization for coremark
>> (See
>> http://community.arm.com/groups/embedded/blog/2013/02/21/coremark-and-compiler-performance) and the 13 people on the CC list for this bug certainly shows interest in having it even if it is just for a benchmark.  Does 'competing against other compilers' sound better then 'optimizing for a benchmark'?
>
> Well - as an open-source compiler we have the luxury to not care
> about "benchmark compilers" ;)  At least that's what our non-existant
> sales-team told me.
>
> There are plenty "real" interpreters around which may have states
> that deterministically forward to another state.  If you optimize
> those as well, fine.
>
> Btw - the patch doesn't contain a single testcase ....
>
> With coremark being "secret" what's the real-world testcase this
> optimizes?  Note that the benchmarks used in SPEC are usually
> available and taken from real-world apps.  I don't know coremark
> at all, but from its name it sounds like sth like nullstone?

Ok, seems you can download coremark so I did that.  The benchmark
doesn't resemble any reasonable state machine as the "state"
is simply compiler-visibly looping 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5...
in a real state machine the next state would come from input
(uninteresting) or be determined by a previous state (well - it is in
the artificial case, but for all states which makes the switch moot).
Thus this benchmark is so artificial that it isn't worth a special
pass.

I suppose the "expected" optimizaton is to un-obfuscate this into
the non-state-machine this really is after peeling the first
iterations to make 'seed' compile-time determinable (here I note
the function comment that says it's important that 'seed' is
_not_ compile-time known - hah, peeling is such a nice tool
to "workaround" that idea).

Stupid benchmarks.

Richard.

> Richard.
>
>> Steve Ellcey
>> sellcey@mips.com
>>

On 08/15/14 04:07, Richard Biener wrote:
> On Thu, Aug 14, 2014 at 8:45 PM, Sebastian Pop <sebpop@gmail.com> wrote:
>> Steve Ellcey wrote:
>>> I understand the desire not to add optimizations just for benchmarks but
>>> we do know other compilers have added this optimization for coremark
>>> (See
>>> http://community.arm.com/groups/embedded/blog/2013/02/21/coremark-and-compiler-performance)
>>> and the 13 people on the CC list for this bug certainly shows interest in
>>> having it even if it is just for a benchmark.  Does 'competing against other
>>> compilers' sound better then 'optimizing for a benchmark'?
>>
>> I definitely would like to see GCC trunk do this transform.  What about we
>> integrate the new pass, and then when jump-threading manages to catch the
>> coremark loop, we remove the pass?
>
> It never worked that way.
>
> A new pass takes compile-time, if we disable it by default it won't help
> coremark (and it will bitrot quickly).
>
> So - please fix DOM instead.
Steve's work is highly likely to be faster than further extending the 
threading code -- that's one of the primary reasons I suggested Steve 
resurrect his work.



Jeff

On 14/08/14 19:25, Steve Ellcey wrote:
> On Thu, 2014-08-14 at 10:21 -0600, Jeff Law wrote:
>> On 08/14/14 10:12, David Malcolm wrote:
>>> On Thu, 2014-08-14 at 09:56 -0600, Jeff Law wrote:
>>>> On 08/14/14 04:32, Richard Biener wrote:
>>>>>> You'll note in a separate thread Steve and I discussed this during Cauldron
>>>>>> and it was at my recommendation Steve resurrected his proof of concept
>>>>>> plugin and started beating it into shape.
>>>>>
>>>>> But do we really want a pass just to help coremark?
>>>> And that's the biggest argument against Steve's work.  In theory it
>>>> should be applicable to other FSMs, but nobody's come forth with
>>>> additional testcases from real world applications.
>>>
>>> Maybe a regex library?  Perhaps:
>>> http://vcs.pcre.org/viewvc/code/trunk/pcre_dfa_exec.c?revision=1477 ?
>> The key is that at least some states tell you at compile time what state
>> you'll be in during the next loop iteration.  Thus instead of coming
>> around the loop, evaluating the switch condition, then doing the
>> multi-way branch, we just directly jump to the case for the next iteration.
>>
>> I've never looked at the PCRE code to know if it's got cases like that.
>>
>> jeff
>
> I compiled PCRE but it never triggered this optimization (even if I
> bumped up the parameters for instruction counts and paths).
>
> I understand the desire not to add optimizations just for benchmarks but
> we do know other compilers have added this optimization for coremark
> (See
> http://community.arm.com/groups/embedded/blog/2013/02/21/coremark-and-compiler-performance) and the 13 people on the CC list for this bug certainly shows interest in having it even if it is just for a benchmark.  Does 'competing against other compilers' sound better then 'optimizing for a benchmark'?
>
> Steve Ellcey
> sellcey@mips.com
>
>

I've been told and have seen empirical evidence of this triggering in 
another well-known popular embedded benchmark suite.

Why not try this on SPEC2k(6) and see if it triggers with bumped up 
parameters to see if it applies elsewhere ?


regards
Ramana