[LLVMdev] RFC: Recursive inlining

[Jeremy Lakeman]

Thinking about this some more I realise I could explain this more clearly.
I think we can manipulate the bitcode fairly easily, and in the same way
for all recursive functions.

before;

void func(%arg1, ...) {
entry:
  // ...

terminate:
  // ...
  ret;

recursive_call:
  // ...
  call func(%arg1_tmp, ...)
  // ...

end:
  // ...
  ret;
}

after;


void func(%arg1_top, ...) {
entry:
  push state_end
  br recurse;

recurse:
  %arg1 = phi %arg1_top, %arg1_tmp, ....
  // ...

terminate:
  // ...
  br state_ret;

recursive_call:
  // ...
  push live values
  push state 1
  br recurse;

state1:
  pop live values
  // ...

end:
  // ...
  br state_ret;

state_ret:
  %state = pop state
  switch %state{
    case state_end: br finish;
    case 1: br state1;
    .... other states ...
  }

finish:
  ret;
}


On Thu, Feb 5, 2015 at 10:53 PM, Jeremy Lakeman <Jeremy.Lakeman at gmail.com>
wrote:

>
>
> 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/20150206/8e048daa/attachment.html>