[LLVMdev] bug of tail call optimization on x86 target

[Katsuhiro Ueno]

Dear LLVM developers,

I am a developer of SML#, an ML-style functional programming language
developed at Tohoku University.  Currently we are intending to use
LLVM as the backend of our SML# compiler in our upcoming release, and
have rewritten our frontend and runtime so that they can cooperate
with LLVM.  LLVM works extremely fine with our SML# compiler.  We are
grateful to LLVM community for providing such an excellent software.

However, when generating x86 code with enabling tail call optimization,
unfortunately I found a bug that destroys callee-save registers.
The following is the bug I found and the attached file is the fix of
this bug.

The following is the LLVM IR code that causes the bug:

; bug.ll
target triple = "i686-apple-darwin12.4.0"
declare fastcc void @foo(i32, i32, i32, i32, i32, i32)
declare i32* @bar(i32*)
define fastcc void @hoge(i32 %b) nounwind {
  %a = alloca i32
  store i32 0, i32* %a
  %d = tail call i32* @bar(i32* %a) nounwind
  store i32 %b, i32* %d
  tail call fastcc void @foo(i32 1, i32 2, i32 3, i32 4, i32 5, i32 6) nounwind
  ret void
}

LLVM produces the following x86 code against the above source:

% llc -tailcallopt -filetype=asm -disable-cfi -o - bug.ll
...
_hoge:                                  ## @hoge
## BB#0:
        subl    $16, %esp
        pushl   %esi            ;;;; this preserves %esi, but
        subl    $40, %esp
        movl    %ecx, %esi
        movl    $0, 40(%esp)    ;;;; this overwrites preserved %esi
        leal    40(%esp), %eax
        movl    %eax, (%esp)
        calll   _bar
        movl    %esi, (%eax)
        movl    60(%esp), %eax
        movl    $6, 60(%esp)
        movl    $5, 56(%esp)
        movl    $4, 52(%esp)
        movl    $3, 48(%esp)
        movl    %eax, 44(%esp)
        movl    $1, %ecx
        movl    $2, %edx
        addl    $40, %esp
        popl    %esi            ;;;; this always fails to restore %esi
        jmp     _foo                    ## TAILCALL

In the above code, 2nd instruction "pushl %esi" saves a callee-save
register %esi to the stack, but 5th instruction "movl $0, 40(%esp)"
overwrites the saved %esi.  Eventually at the epilogue "popl %esi"
fails to restore the previous %esi.

This bug is due to wrong computation of stack object indices by the
x86 backend.  The attached patch indicates the wrong points.  Due to
integral promotion, explicit conversion to signed integer is needed
at those points.

Eliminating tail calls (with arbitrary number of arguments) is mandatory
for practical functional languages.  I would appreciate it if this bug
would be fixed in the next release.

Best regards,

Katsuhiro Ueno
-------------- next part --------------
A non-text attachment was scrubbed...
Name: x86-tailcallopt-fix.diff
Type: application/octet-stream
Size: 1790 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130803/b8ef92ae/attachment.obj>