<div dir="ltr"><div><div><div><div>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.<br><br></div>before;<br><br></div>void func(%arg1, ...) {<br></div><div>entry:<br> // ...<br><br></div><div>terminate:<br></div><div> // ...<br></div> ret;<br> <br></div><div>recursive_call:<br></div><div> // ...<br></div> call func(%arg1_tmp, ...)<br><div><div> // ...<br><br><div>end:<br></div><div> // ...<br></div> ret;<br>}<br><br><div><div><span class="">after;</span><br></div><div><br><div><div class="gmail_extra"><br>void func(%arg1_top, ...) {<br><div>entry:<br></div><div> push state_end<br></div><div> br recurse;<br><br></div><div>recurse:<br></div><div> %arg1 = phi %arg1_top, %arg1_tmp, ....<br></div><div> // ...<br><br></div><div>terminate:<br></div><div> // ...<br></div><div> br state_ret;<br></div> <br>recursive_call:<br> // ...<br></div><div class="gmail_extra"> push live values<br></div><div class="gmail_extra"> push state 1<br></div><div class="gmail_extra"> br recurse;<br><br></div><div class="gmail_extra">state1:<br></div><div class="gmail_extra"> pop live values<br></div><div class="gmail_extra"> // ...<br><br><div>end:<br></div><div> // ...<br><div><div> br state_ret;<br><br></div><div>state_ret:<br></div> %state = pop state</div><div> switch %state{<br> case state_end: br finish;<br></div> case 1: br state1;<br></div><div> .... other states ...<br></div><div> }<br><br></div><div>finish:<br></div><div> ret;<br></div>}<br><br><br><div class="gmail_quote">On Thu, Feb 5, 2015 at 10:53 PM, Jeremy Lakeman <span dir="ltr"><<a href="mailto:Jeremy.Lakeman@gmail.com" target="_blank">Jeremy.Lakeman@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><span class=""><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Feb 5, 2015 at 9:06 PM, James Molloy <span dir="ltr"><<a href="mailto:james@jamesmolloy.co.uk" target="_blank">james@jamesmolloy.co.uk</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Now what about a more complex case, like in the FFT butterfly algorithm:<div><br></div><div> void ex4(i) {</div><div> if (is_base(i)) {</div><div> f(i); return;</div><div> }</div><div> g(i);</div><div> ex4(i / 2);</div><div> ex4(i / 2 + 1);</div><div> h(i);</div><div> }</div><div><br></div><br></blockquote></div><br></div></span><div class="gmail_extra">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.<br></div><div class="gmail_extra">So essentially we just need to;<br>- replace call's with a stack push and jump to entry block<br>- replace return's with a stack pop and jump to the state following the call or return.<br></div><div class="gmail_extra">And try to avoid pushing any invariant values.<br></div><div class="gmail_extra"><br></div><div class="gmail_extra">Something along these lines?<br></div><div class="gmail_extra"><br></div><div class="gmail_extra">struct stack{<br></div><div class="gmail_extra"> state;<br></div><div class="gmail_extra"> i;<br></div><div class="gmail_extra">}<br><br></div><div class="gmail_extra">void ex4(i) {<br></div><div class="gmail_extra">entry:<br></div><div class="gmail_extra">struct stack *stack = intrinsic.stackptr() // ??<br></div>goto state_0;<br><div class="gmail_extra"><br></div><div class="gmail_extra">state_0:<br></div><div class="gmail_extra">i0 = phi [i, i1, i2]<br></div><div class="gmail_extra">stack0 = phi [stack, stack1, stack2]<br></div>if (is_base(i)){<br><div class="gmail_extra"> f(i);<br></div><div class="gmail_extra"> goto state_ret;<br></div>}<br><div class="gmail_extra">g(i);<br>i1 = i0 / 2; <br>stack0->state=1;<br></div><div class="gmail_extra">stack0->i = i0;<br></div><div class="gmail_extra">stack1 = stack0 + 1;<br></div>goto state_0;<br><div class="gmail_extra"><br></div><div class="gmail_extra">state_1:<br>i2 = i3 / 2 + 1;<br>stack0->state=2;<br><div class="gmail_extra">stack0->i = i;<br></div>stack2 = stack0 + 1;<br>goto state_0;<br><br>state_2:<br></div><div class="gmail_extra">h(i3);<br></div><div class="gmail_extra">goto state_ret;<br></div><div class="gmail_extra"><br>state_ret:<br>stack3 = phi [stack0, stack3]<br>if( stack3 == stack ) return;<br></div><div class="gmail_extra">stack4 = stack3 - 1;<br></div><div class="gmail_extra">i2 = stack4->i;<br></div><div class="gmail_extra"><div class="gmail_extra">switch(stack4->state){<br><div class="gmail_extra">case 1: goto state_1;<br></div></div><div class="gmail_extra">case 2: goto state_2;<br></div><div class="gmail_extra">default: unreachable;<br>}<br></div><br><br></div></div>
</blockquote></div><br></div></div></div></div></div></div></div>