[LLVMdev] RFC: Recursive inlining (original) (raw)
Jeremy Lakeman Jeremy.Lakeman at gmail.com
Thu Feb 5 04:23:34 PST 2015
- Previous message: [LLVMdev] RFC: Recursive inlining
- Next message: [LLVMdev] RFC: Recursive inlining
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
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 (isbase(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>
- Previous message: [LLVMdev] RFC: Recursive inlining
- Next message: [LLVMdev] RFC: Recursive inlining
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]