llvm dev - Dec 2011 - [LLVMdev] tail call optimization question

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

On Dec 22, 2011, at 1:54 PM, Nicolas Ojeda Bar wrote:
> 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):
It isn't "guaranteed", but yes, the optimizer is able to make it
happen in some cases.

-Chris