# HG changeset patch # User Kaito Tokumori # Date 1435760981 -32400 # Node ID ac2ec4334d49a7bb49b6a5e1c34e1c52441c0cbe # Parent 20257f618ddd8b83d073dbe33bd20aa0b67207e0 implementation diff -r 20257f618ddd -r ac2ec4334d49 presentation/presen.html --- a/presentation/presen.html Wed Jul 01 22:18:59 2015 +0900 +++ b/presentation/presen.html Wed Jul 01 23:29:41 2015 +0900 @@ -426,7 +426,7 @@
  • TCE is one of the optimization.
  • If the function call is immediately followed by return, it is tail call.
  • TCE replace tail call's call instructions with jmp instructions. -
  • Code segments' transition is implemented by forced tail call elimination. +
  • Code segments transition is implemented by forced tail call elimination.
    @@ -440,7 +440,29 @@

    Forcing Tail Call Elimination

    -

    LLVM IR has function call flags. We can give LLVM some information for function call by them. We use them for force to tail call elimination. +

      +
    • LLVM IR has function call flags. +
    • tail mean it is tail call. +
    • Calling convention tell compiler how callee functions receive parameters from their caller. +
    + + + + +
    + 
    +define fastcc void @factorial(i32 %x) #0 {
+  entry:
+  tail call fastcc void @factorial0(i32 1, i32 %x)
+  ret void
+}
+
    +
    +

    Use them for force to tail call elimination.

    +
    + +
    +

    Forcing Tail Call Elimination

    We have to meet the following requirements.

    • set tail flag at the code segments call. @@ -448,7 +470,10 @@
    • the caller and calle's calling conventions must be the same and their types should be cc10, cc11 or fastcc.
    • return value type has to be the same as the caller's.
    -
    +
    + +
    +

    Forcing Tail Call Elimination

    We met them by following ways.

    • Always add tail call elimination pass and set flag at the code segments call. @@ -576,10 +601,50 @@
    +

    Compiling result

    +

    Tail Call Elimination が強制されているかどうかをアセンブリコードから判断する.

    + + + +
    + 
    +
+__code caller(int x)
+{
+  goto code1(1, x); // should be jmp
+}
+
    +     		+ 
    +_caller:                             ## @factorial
+        .cfi_startproc
+## BB#0:                                ## %entry
+        subq    $24, %rsp
+Ltmp5:
+        .cfi_def_cfa_offset 32
+        movl    $1, %eax
+        movl    %edi, 20(%rsp)          ## 4-byte Spill
+        movl    %eax, %edi
+        movl    20(%rsp), %esi          ## 4-byte Reload
+        addq    $24, %rsp
+        jmp     _code1             ## TAILCALL
+        .cfi_endproc
+
    +
    +
      +
    • Code1 should called by jmp instruction. +
    • In assembly code, code1 called by jmp instruction. +
    • Tail call elimination was forced. +
    • If tail call elimination was failed, compiler output error messages. +
    +
    + +

    Conclusion

    • CbC compiler on LLVM and Clang was implemented.
    • LLVM IR was not modified. +