[LLVMdev] tail call optimization question
Nicolas Ojeda Bar
nojb at math.harvard.edu
Thu Dec 22 13:54:48 PST 2011
Hello,
Is tail call optimization performed if the ret instruction does not actually
follow the tail call? Not according to the documentation, but in examples it seems
to work. For example, consider the following definition of Ackerman's
function in ML (it has two tail calls):
let rec ack x y =
if x <= 0 then y + 1 else
if y <= 0 then ack (x - 1) 1 else
ack (x - 1) (ack x (y - 1))
My compiler is generating the following code for it:
define internal fastcc i64 @ack.15(i64 %x.16, i64 %y.17) {
entry:
%0 = icmp sle i64 %x.16, 0
br i1 %0, label %if.yes, label %if.no
if.yes: ; preds = %entry
%1 = add i64 %y.17, 1
br label %if.after
if.no: ; preds = %entry
%2 = icmp sle i64 %y.17, 0
br i1 %2, label %if.yes1, label %if.no2
if.after: ; preds = %if.after3, %if.yes
%3 = phi i64 [ %1, %if.yes ], [ %10, %if.after3 ]
ret i64 %3
if.yes1: ; preds = %if.no
%4 = sub i64 %x.16, 1
%5 = tail call fastcc i64 @ack.15(i64 %4, i64 1)
br label %if.after3
if.no2: ; preds = %if.no
%6 = sub i64 %x.16, 1
%7 = sub i64 %y.17, 1
%8 = call fastcc i64 @ack.15(i64 %x.16, i64 %7)
%9 = tail call fastcc i64 @ack.15(i64 %6, i64 %8)
br label %if.after3
if.after3: ; preds = %if.no2, %if.yes1
%10 = phi i64 [ %5, %if.yes1 ], [ %9, %if.no2 ]
br label %if.after
}
LLVM generates the following assembly, seemingly applying tail call optimization
even though the ret instruction does not follow the tail call instruction:
<snip>
_ack.15: ## @ack.15
Leh_func_begin1:
## BB#0: ## %entry
pushq %rbx
Ltmp1:
Ltmp2:
testq %rdi, %rdi
jle LBB1_3
## BB#1: ## %if.no
movq %rdi, %rbx
testq %rsi, %rsi
jle LBB1_4
## BB#2: ## %if.no2
decq %rsi
movq %rbx, %rdi
callq _ack.15
movq %rbx, %rdi
decq %rdi
movq %rax, %rsi
popq %rbx
jmp _ack.15 ## TAILCALL
LBB1_3: ## %if.yes
incq %rsi
movq %rsi, %rax
popq %rbx
ret
LBB1_4: ## %if.yes1
movq %rbx, %rdi
decq %rdi
movl $1, %esi
popq %rbx
jmp _ack.15 ## TAILCALL
Leh_func_end1:
<snip>
Thanks very much,
N
More information about the llvm-dev
mailing list