<div dir="ltr"><div class="gmail_extra">First off, thanks for the examples. They are very nice.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Breaking it down into an explicit state machine is I think exactly the right way to model this.</div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Feb 5, 2015 at 2:36 AM, 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:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div>This solution can be generalised for if there is code in between the recursive calls (just add more states). It's getting more complex in terms of control flow though - the question is, is it worth it?</div><div><br></div><div>Unrolling this loop is probably not going to usefully create larger basic blocks due to how complex the control flow is. I suppose we have the opportunity, if we unroll, of CSE and jump threading values through equivalent blocks that may gain us time. However, we can still do LICM which is probably a major improvement, and there are no calls/returns to speculate.</div><div><br></div><div>This approach would have to be extended if the recursive calls didn't return void (for example it was a recursive reduction), but it's not impossible.</div><div><br></div><div>Sorry for the long post. What do people think?</div></blockquote></div><br>Personally, I think this would be an amazing transformation for LLVM to do. But I agree that it gets very complex in the limit. I suspect there will need to be some complexity bound on doing this transformation, but as of yet I'm not sure what it would be. Here is what is in my head.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Let's imagine we do this transform. Let's imagine that *no other optimizations fire*. How close can we make the generated code resemble what would be executed by actually calling the function recursively? Can we use the actual stack and lower the adjustments much like we would were we to imagine the dynamic trace of instructions in the recursive variant?</div><div class="gmail_extra"><br></div><div class="gmail_extra">My suspicion is that for a decent chunk of real world recursion, we can transform it into a loop that is not significantly lower to execute. We can use the same stack adjustment code that would be executed in a recursive call, etc. My further suspicion is that the complexity of control flow is not the critical concern here, but the amount of stack usage, and how much work we have to do to use a minimal amount of the stack. I could be completely wrong about this, however, looking at your state machine code my first impression is that the code is actually not bad... except for the stack manipulation. I think we'll actually generate very reasonable code for the CFGs here.</div><div class="gmail_extra"><br></div><div class="gmail_extra">So, if we can do this transform in a way that produces generated code that essentially executes the same dynamic trace of instructions that the recursive code would execute, I think we're in *very* safe territory. The primary code size will be switching from the call-stack approach to this manual stack approach. It'll be like the cost of peeling the outer iteration. Unless the code size is of extreme concern, I don't think there is much downside.</div><div class="gmail_extra"><br></div><div class="gmail_extra">As for the upside, I think it is huge. LICM alone is a game-changer. GVN starts to work. PRE can be applied. Will SCEV be able to reason about the trip count? probably not. But the entire rest of the optimizer essentially gets turned *on* by this change.</div></div>