RFC: ARM Strategy for adding tail call optimization to thumb1 targets


after a while of code-reading and analysis I have come up with a plan on how to add tail call optimizations to thumb1 targets. As a beginner within LLVM, I would very much appreciate feedback and advice before proceeding further.

I identified two main complexities rendering tail call optimization more difficult for thumb1 targets (this is also already stated in some very old comment within ARMTargetLowering::IsEligibleForTailCallOptimization that does not seem to mach current state of the code at some minor points):

1.) Unlike the BL instruction the B instruction only reaches targets in up to ~2k byte distance. This means that for true tail calls the jump target address needs to be placed in a register.
2.) We need a scratch register to restore LR contents in the epilogue if LR has previously been pushed on the stack.

My plan is to implement the following:

1.) When lowering tail calls during DAG generation, arrange for the call target adress always being loaded into a register. So that actually only ARM::TCRETURNri pseudo opcodes will be generated for tail calls. (Penalty of this is will be one additional mov r12,r3 in case of exactly 3 parameters being passed on the stack for constant addresses, see below).

2.) In case that r0 up to r3 are used for parameter passing. I noticed, that the thumb1 register allocator settings will not be able to allocate a suitable register. My plan is to somehow force the tail call jump target into hard reg r12 in this case before register allocation. If at least r3 is free, the register allocator will be able to find a register for the TCRETURNri pseudo instruction and we don't have a problem until epilogue generation.

QUESTION 1: How would be the "right" way to force the target address into the hard reg r12 in case that r0 up to r3 are used for params? Should this check and the "force to hard reg r12" code go to ARMTargetLowering::LowerCall or should this be done within the "legalize DAG" pass that seems to exist somewhere. Is there an example on how to force a value into a hard reg?

3.) After Steps 1.) and 2.), Thumb1FrameLowering::emitEpilogue will find TCRETURNri pseudo instructions for tail calls. We could detect this easily and probably handle this case within a new private member Thumb1FrameLowering::emitTailCallEpilogue ().

Thumb1FrameLowering::emitTailCallEpilogue () will have to arrange for
- updating the stack pointer,
- restoring GP registers pushed on the stack,
- restoring LR and
- jumping to the target address.

The problem is that restoring LR requires a scratch register because pop {lr} is not available. In any way, the target address will be available in a register.

Within Thumb1FrameLowering::emitTailCallEpilogue (), I plan to distinguish only 3 cases:

a) target address is in r12. This means, that we would have to generate *very* complicated code for restoring LR *before* poping the callee save-registers r4 ... r7, poping r4...r7, re-adjusting SP for the unused stack slot used for LR and then using BX r12. Instead of this very complicated code, I'd rather pop all callee-save-registers r4...r7 except LR and use a BLX r12; pop {pc} sequence instead. I.e. the stack frame would grow by 4 bytes for the LR not yet popped. Note that this would prevent tail call optimizations as soon as one parameter is passed on the stack. (see side-note below on this issue).

b) target address of TCRETURNri is in r3. I would use "mov r12,r3" for freeing r3 as scratch register, pop all registers except LR and issue a pop {r3}; mov LR,r3; BX r12 sequence.

c) target address of TCRETURNri is not in r3. Assert that r3 is not used for parameters. Use r3 as scratch register as in case b) and proceed.

This code would be slightly sub-optimal in the case b) handling exactly 3 parameters passed in registers if the target address is constant. In this case, loading the target address into r3 could have been done *after* restoring LR contents. However, the penalty in this case would be only the mov r12,r3 instruction and the complexity of handling constant and variable adresses differently and loading the operands to registers would not go into Thumb1FrameLowering::emitTailCallEpilogue ().

QUESTION 2: Is this a good idea or should I rather choose the *very* complicated code version or should the case a) be split into aa) for no parameters passed on the stack (using BLX r12; pop {pc} ) and ab) using the *very* complicated code version


I also would appreciate suggestions on the development enviroment to use. I so far build LLC from the command shell and use Eclipse for debugging and stepping through the code using the local gdb. I'm a bit unhappy of my environment because doing so is extremely slow on my machine. The Eclipse indexer is incredibly slow and frequently references are not correctly resolved in the editor :-(. Also spawning gdb with the llc executable from eclipse takes about 2 minutes for each run ... Waiting for a full build being finished (with clang and the other stuff) takes half a day on my machine. When running make opt and llc seem to be built first by make, so I'm currently canceling the build. But also when intterrupting make after linking llc each build of llc takes about 5 minutes on my machine ... Is there a way for speeding up builds for development? Is there an environment recommended for working on LLVM? (I did not find any hint in the documentation).


Björn Haase


It is my understanding that the code

extern void peter(int a,int b, int c, int d, int e);

hugo (int a,int b, int c, int d, int e)
    peter (a,b,c,d,e);

should in fact be eligible for tail call optimization. However, I notice, that within ARMTargetLowering::IsEligibleForTailCallOptimization
the check for matching stack offsets for parameter #5 fails so that the function is marked not to be eligible for tail call optimizations.

The relevant code portion within ARMTargetLowering::IsEligibleForTailCallOptimization is:

     } else if (!VA.isRegLoc()) {
           if (!MatchingStackOffset(Arg, VA.getLocMemOffset(), Flags,
                                    MFI, MRI, TII))
             return false;

MatchingStackOffset returns false for the 5th parameter. In my eyes this seems to be a bug and not intentional.? Should I file a bug ?