[LLVMdev] RFC: Recursive inlining

[Jeremy Lakeman]

On Thu, Feb 5, 2015 at 9:06 PM, James Molloy <james at jamesmolloy.co.uk>
wrote:

> Now what about a more complex case, like in the FFT butterfly algorithm:
>
>     void ex4(i) {
>       if (is_base(i)) {
>         f(i); return;
>       }
>       g(i);
>       ex4(i / 2);
>       ex4(i / 2 + 1);
>       h(i);
>     }
>
>
>
This sounds like a very similar process to transforming a C# IEnumerable's
"yield" into a state machine. There might be some relevant literature in
this area.
So essentially we just need to;
- replace call's with a stack push and jump to entry block
- replace return's with a stack pop and jump to the state following the
call or return.
And try to avoid pushing any invariant values.

Something along these lines?

struct stack{
  state;
  i;
}

void ex4(i) {
entry:
struct stack *stack = intrinsic.stackptr() // ??
goto state_0;

state_0:
i0 = phi [i, i1, i2]
stack0 = phi [stack, stack1, stack2]
if (is_base(i)){
  f(i);
  goto state_ret;
}
g(i);
i1 = i0 / 2;
stack0->state=1;
stack0->i = i0;
stack1 = stack0 + 1;
goto state_0;

state_1:
i2 = i3 / 2 + 1;
stack0->state=2;
stack0->i = i;
stack2 = stack0 + 1;
goto state_0;

state_2:
h(i3);
goto state_ret;

state_ret:
stack3 = phi [stack0, stack3]
if( stack3 == stack ) return;
stack4 = stack3 - 1;
i2 = stack4->i;
switch(stack4->state){
case 1: goto state_1;
case 2: goto state_2;
default: unreachable;
}
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150205/37c66597/attachment.html>