Tail call optimization

In this recipe, we will see how tail call optimization is done in LLVM. Tail call optimization is a technique where the callee reuses the stack of the caller instead of adding a new stack frame to the call stack, hence saving stack space and the number of returns when dealing with mutually recursive functions.

Getting ready

We need to make sure of the following:

• The llc tool must be installed in $PATH

• The tailcallopt option must be enabled

• The test code must have a tail call

How to do it…

1. Write the test code for checking tail call optimization:

   $ cat tailcall.ll
   declare fastcc i32 @tailcallee(i32 inreg %a1, i32 inreg %a2, i32 %a3, i32 %a4)
   
   define fastcc i32 @tailcaller(i32 %in1, i32 %in2) {
     %l1 = add i32 %in1, %in2
     %tmp = tail call fastcc i32 @tailcallee(i32 inreg %in1, i32 inreg %in2, i32 %in1, i32 %l1)
     ret i32 %tmp
   }
   

2. Run the llc tool with the –tailcallopt option on the test code to generate the assembly file with the tailcall-optimized code:

   $ llc -tailcallopt...