[LLVMdev] RFC: Recursive inlining

[mats petersson]

Pablo, Most of the time the ABI only requires saving of registers that
are actually used in the function. So there may be cases where those
will not need saving, but at the same time, chances are that the loop
version will have to save/restore approximately the same amount of
context - and the caller-save registers [including return address] are
part of the callee context in recursion.

But yes, there is a small chance that the loop version saves on
"save/restore register on stack".

If the stack grows more than in actual recursion, then it's probably
questionable if the inlining/unwinding of the recursion is worth doing
- since most of the purpose here is to avoid the call/return and
argument passing - but if the code ends up saving/restoring MORE data,
it's unlikely to be of benefit [in my limited understanding of the
problem].

--
Mats

On 5 February 2015 at 16:18, Pablo Barrio <pablo.barrio at arm.com> wrote:
> Hi all,
>
>
>
> This thread is really interesting. I’m just trying to understand here, so
> please correct me if I’m wrong.
>
>
>
> Wouldn’t we potentially save stack usage just by turning the recursion into
> loops? For example, at the assembly level, the ABI often requires to
> preserve some registers between calls which translate into stack pushes, and
> we will get rid of that. My understanding is that this transform does the
> same thing as the lowering to assembly does for function calls, with the
> exception that all the architecture-independent passes will have a broader
> context for analysis. So I would expect to even improve the stack usage.
>
>
>
> Otherwise, we could analyze the expected stack usage for a single recursive
> call. Then, compare it to the expected usage after the transformation for
> each loop iteration. This could be used as a heuristic to decide whether to
> do the conversion or not? E.g. we only allow to increase the stack growth by
> 1.2x.
>
>
>
> Thanks,
>
> Pablo
>
>
>
> From: James Molloy [mailto:james at jamesmolloy.co.uk]
> Sent: 05 February 2015 15:19
> To: Hal Finkel
> Cc: llvmdev at cs.uiuc.edu; Chandler Carruth; Pablo Barrio
> Subject: Re: RFC: Recursive inlining
>
>
>
> Hi Hal,
>
>
>
>> As we had briefly mentioned on IRC, one way of forming this 'stack', and
>> its associated 'cnt' variable, is to use dynamic stack allocation.
>
>
>
> I hadn't really reached a decision on the mechanics yet. However, your
> suggestion while it can work within the current abilities of the IR, has the
> disadvantage that it is using an extra stack slot for the link pointer. I
> think if we are going to apply this optimization, we must make sure we
> aren't going to blow the stack.
>
>
>
> As users may already be just close enough to the max-stack boundary that
> their applications don't crash, I think we should aim as much as possible to
> keep the stack usage no higher than the recursive equivalent. Holding the
> "state" is the equivalent of a return address, so adding a stack link
> pointer would be the equivalent of a frame address I suppose... That could
> be acceptable?
>
>
>
> As I say, I haven't thought about the deep mechanics just yet.
>
>
>
> James
>
>
>
> On Thu Feb 05 2015 at 2:48:48 PM Hal Finkel <hfinkel at anl.gov> wrote:
>
> ----- Original Message -----
>> From: "James Molloy" <james at jamesmolloy.co.uk>
>> To: llvmdev at cs.uiuc.edu, "Chandler Carruth" <chandlerc at google.com>, "Hal
>> Finkel" <hfinkel at anl.gov>, "pablo barrio"
>> <pablo.barrio at arm.com>
>> Sent: Thursday, February 5, 2015 4:36:16 AM
>> Subject: RFC: Recursive inlining
>>
>>
>> Hi,
>>
>>
>> The other day on IRC myself, Chandler, Hal and Pablo discussed
>> recursive inlining. I've pondered a bit since then, and thought I'd
>> get some background on the list with the aim of stimulating
>> discussion.
>>
>>
>> Our goal is to inline recursive functions. We have several workloads
>> with recursive calls, and inlining them to a certain degree can
>> improve performance by up to 30%.
>>
>>
>> Inlining recursive functions is a slightly different problem to
>> inlining non-recursive functions in that the inlining can never
>> terminate, so you need to choose a factor (number of times) to
>> inline. In this respect it is similar to loop unrolling, and
>> Chandler suggested we should model it as such.
>>
>>
>> We originally thought he meant by this that the mechanics of inlining
>> would stay the same, but the heuristics would have to be changed.
>> This is the approach taken by Rugina & Rinard [1], which is almost
>> the sum of the literature on this topic I could find, which
>> surprised me. However, the actual suggestion was to remove the
>> recursion entirely, and replace it with a loop.
>>
>>
>> Before I get into the mechanics of this, I'd like to explain what the
>> possible optimization opportunities are for recursive functions
>> turned into a loop.
>>
>>
>> 1. Unrolling
>> - This leads to bigger basic blocks (if they can be merged) and
>> exposes more pipeline-level parallelism.
>> - CSE between iterations.
>> - Reduces backbranch overhead (generally negligible impact).
>> 2. Commoning / LICM
>> - Recursion doesn't have a vehicle for moving common code out into a
>> dominating block (compare with LICM for loops).
>>
>>
>> OK, first example:
>>
>>
>> void ex1(i) {
>> if (i == 0) return;
>> a[i] = i+1;
>> ex1(i-1);
>> }
>>
>>
>> gets converted to:
>>
>>
>> while (1) {
>> if (i == 0) break;
>> a[i] = i+1;
>> i = i-1;
>> }
>>
>>
>> Now, the above is the simplest case and is pure tail recursion. We
>> can eliminate this currently with the TailRecursionElimination pass.
>> The more complex case is where we have non-tail recusion and live
>> variables.
>>
>>
>> void ex2(i) {
>> if (i == 0) return;
>> j = a[i];
>> ex2(i-1)
>> b[j] = i;
>> }
>>
>>
>> This requires a stack being modelled and could be converted to:
>>
>>
>> cnt = 0;
>> while (1) {
>> if (i == 0) break;
>> j = a[i];
>> stack[cnt++] = j;
>> stack[cnt++] = i;
>> ++cnt;
>> --i;
>> }
>> while (cnt) {
>> i = stack[--cnt];
>> j = stack[--cnt];
>> b[j] = i;
>> }
>>
>>
>> The above is as far as the discussion got on IRC. The following are
>> my half-baked thoughts.
>>
>>
>> The above transform works because the access pattern to the stack is
>> strictly linear. Pushes are followed by pops. But I don't think this
>> is the most interesting case for recursion in real programs. I see
>> (qualitatively, poorly) 3 reasons for recursion in code that should
>> go fast:
>>
>>
>> 1. A fibonnacci function in a microbenchmark or compiler shootout. I
>> think we can safely ignore this usecase...
>> 2. Divide and conquer algorithms. Quicksort, FFT butterflies, etc.
>> 3. Traversing a data structure, where the recursion is simply to get
>> to the leaves which is where all the fun stuff happens.
>>
>>
>> Points 2 and 3 both share a trait that they're dividing/fanning out
>> at each step:
>>
>>
>> void ex3(i) {
>> if (is_base(i)) {
>> f();
>> return;
>> }
>> g(i);
>> ex3(i / 2);
>> ex3(i / 2 + 1);
>> }
>>
>>
>> The access pattern of such a function is not linear. It is a
>> pre-order walk of a (binary, in this case) tree. As such we can't
>> use the two-loop transform above, but would have to form one loop
>> and just manually implement the stack operations:
>>
>>
>> cnt = 0
>> stack[cnt++] = i;
>> while (1) {
>> i = stack[--cnt];
>> if (is_base(i)) {
>> f(); continue;
>> }
>> g(i);
>> stack[cnt++] = i / 2 + 1;
>> stack[cnt++] = i / 2;
>> }
>>
>>
>> OK, it's still a well-formed loop, we can still do useful operations
>> on it like LICM or, if it's profitable, unrolling.
>>
>>
>> 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);
>> }
>>
>>
>> Here, we have to do work after the last recursive call. This presents
>> a problem, because we don't have any of the caller's context when
>> dealing with a node. Is a node N the first recursive call? or the
>> second? Call-stack recursion can save two things: the state of
>> variables and the return address which serves as another kind of
>> state. The obvious answer is to turn this into a sort of state
>> machine:
>>
>>
>> cnt = 0
>> stack[cnt++] = i;
>> stack[cnt++] = STATE_1;
>> while (1) {
>> state = stack[--cnt];
>> i = stack[--cnt];
>>
>>
>> if (state == STATE_FINISH) {
>> h(i);
>> continue;
>> }
>>
>>
>> if (is_base(i)) {
>> f(); continue;
>> }
>>
>>
>> g(i);
>> stack[cnt++] = i; // Push ourself again, in the final state this time
>> stack[cnt++] = STATE_FINISH;
>> stack[cnt++] = i / 2 + 1;
>> stack[cnt++] = STATE_1;
>> stack[cnt++] = i / 2;
>> stack[cnt++] = STATE_1;
>> }
>
> As we had briefly mentioned on IRC, one way of forming this 'stack', and its
> associated 'cnt' variable, is to use dynamic stack allocation. You can do
> this in general at the IR level (using allocas that just happen not to be in
> the entry block). If each stack block holds a pointer to the previous one
> (as a linked list), then you just need to maintain a pointer to the current
> block, and you don't need a separate 'cnt' variable (you might also keep a
> pointer to the next block for allocation reuse). Is that what you had in
> mind?
>
>  -Hal
>
>>
>>
>> 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?
>>
>>
>> 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.
>>
>>
>> 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.
>>
>>
>> Sorry for the long post. What do people think?
>>
>>
>> Cheers,
>>
>>
>> James
>>
>>
>> [1]: http://link.springer.com/chapter/10.1007/3-540-45574-4_3
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>