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

It isn't "guaranteed", but yes, the optimizer is able to make it happen in some cases.

-Chris