LLVM tail options optimization

Question

Here is my understanding of things:

Function "f" is tail recursive when the call itself is its last action. Tail recursion can be greatly optimized by looping instead of calling the function again; function parameters are updated in place, and the body starts again. This is called tail call recursive optimization.

LLVM implements recursive tail call optimization using fastcc, GHC, or the HiPE call convention. http://llvm.org/docs/CodeGenerator.html#tail-call-optimization

I have a few questions: Let's look at a stupid example:

int h(int x){ if (x <= 0) return x; else h(x-1); } 

1) In the example, the keyword "tail" precedes the call. Elsewhere, I read that this keyword is optional. Suppose the above function translates to LLVM accordingly, it is necessary that the last few lines be

 %x' = load *i32 %x %m = tail call fastcc i32 @h(i32 %x') ret %m 

2) What is the meaning of the inreg parameter in their example?

3) I would not want to perform tail call optimization everywhere, only for recursive functions. Is there a way to force LLVM to perform only optimization (when available) for recursive functions?

Answer 1

Apparently the answer is yes. You have to change the definition of h to see this (because the optimizer is too good! It finds out that h is either an identifier or returns 0).

Consider

 int factorial (int x, int y){ if (x==0) return y; else return factorial(x-1,y*x); } 

Compiled with clang -S -emit-llvm so that optimization is not performed. It can be seen that direct calls are not specified directly, which means that the default calling convention is sufficient to support tail recursion optimization (regardless of whether it supports tail call at all - this is another story - it would be interesting to know, but I think it really another question).

The file emitted by clang -S -emit-llvm is main.s (assuming the factorial definition is in main.c). If you run

 opt -O3 main.s -S -o mainOpt.s 

then you can see that tail recursion is eliminated. There is an optimization called tailcallelim that can be turned on as -O3. It's hard to say because the opt --help help file only says that -O3 is similar to gcc -O3.

The fact is that we can see that the call does not need to specify an agreement. Maybe fastcc is not needed, or maybe it is the default? So, (1) partially answered; however, I still do not know (2) or (3).

Answer 2

There are two different things here:

• You can optimize self-recursive tail calls in a loop. LLVM provides an optimization pass that does this. This does not require a special calling agreement.
• You can use a different calling convention to ensure that the tail call of all calls at the tail position is optimized (i.e. including calls to other functions). With LLVM, you need to specify the function call convention in the call command and mark the call as a tail call.

It looks like you want the first one.