llvm dev - Aug 2007 - [LLVMdev] Tail call optimization thoughts

Implementing tail call opt could look like the following:

0.)a fast calling convention (maybe use the current  
CallingConv::Fast, or create a CallingConv::TailCall)
1.) lowering of formal arguments
   like for example x86_LowerCCCArguments in  stdcall mode
   we need to make sure that later mentioned CALL_CLOBBERED_REG is  
not used (remove it from available
   registers in callingconvention for argument passing?)
2.)lowering of the call:
   *if it can be shown that call really is tail call (next  
instruction is a return):
      -move the arguments to the correct position on the stack
      -create a REALTAILCALL SelDAG node holding
        tailcallee : if the tailcallee is dynamic, not a  
TargetGlobalAddress or the like,
        lower a move CALL_CLOBBERED_REG tailcallee instruction else  
attach a
        TargetGlobalAddress or the like
      -the size of the stack adjustment
      the realtailcall would be a no op operation that makes sure  
that epilogue is
      lowered before it (looks like a call), remember that we have a  
real tail call
      (like setBytesToPopOnReturn() , a setIsRealTailCall()) in the  
targetlowering())
   *else emit regular function call with same calling conventions
3.)lower of the return:
   *if we are dealing with a realtailcall (getIsRealTailCall)
       look for REALTAILCALL use its operands to
       emit a TC_RETURN node holding stacksize, tailcallee
       the tc_return node would again be a pseudoop
   *else lower normal return


When generating the epilog the two operands of the the tc_return  
machine instruction are used to emit code that adjust the  
stackpointer and jumps to the tailcallee (either label or register).  
Like it is done for EH_RETURN.

in X86RegisterInfo.cpp we would then have
TargetRegisterInfo::emitEpilogue() {
   ...
   if (RetOpcode== X86::TC_RETURN){
     if (isDynamicCallee(RetOpCode))
       add esp  {stack adjustment from tc_return}
       jmp {register operand of tc_return}
     } else
       add esp  {stack adjustment from tc_return}
       jmp {targetfunction operand}
     }
}

resulting code for dynamic function
	
   mov  ecx  esi  #load callee, say esi holds the address of the  
tailcalled
   epilogue
   #TAILCALL
   add esp 8  #caller has 2 more arg
   jmp ecx

if the targetfunction is known

   epilogue
   #TAILCALL
   add esp 8 #caller has 2 more arg
   jmp _targetfunction

Should also work for architectures other than x86.

any critique, comments welcome
regards arnold

> Sorry for the misformating! try again with 66 chars
Implementing tail call opt could look like the following:

0.)a fast calling convention (maybe use the current
    CallingConv::Fast, or create a CallingConv::TailCall)
1.) lowering of formal arguments
    like for example x86_LowerCCCArguments in  stdcall mode
    we need to make sure that later mentioned CALL_CLOBBERED_REG is
    not used (remove it from availableregisters in callingconv
    for argument passing?)
2.)lowering of the call:
    *if it can be shown that call really is tail call (next
     instruction is a return):
       -move the arguments to the correct position on the stack
       -create a REALTAILCALL SelDAG node holding
         #tailcallee : if the tailcallee is dynamic, not a
           TargetGlobalAddress or the like, lower a move
           CALL_CLOBBERED_REG tailcallee instruction else attach
            a TargetGlobalAddress or the like
         #the size of the stack adjustment
       the realtailcall would be a no op operation that makes sure
       that epilogue is lowered before it (looks like a call),
       remember that we have a real tail call
       (like setBytesToPopOnReturn() , a setIsRealTailCall()) in the
       targetlowering())
    *else emit regular function call with same calling conventions
3.)lower of the return:
    *if we are dealing with a realtailcall (getIsRealTailCall)
        look for REALTAILCALL use its operands to
        emit a TC_RETURN node holding stacksize, tailcallee
        the tc_return node would again be a pseudoop
    *else lower normal return


When generating the epilog the two operands of the the tc_return
machine instruction are used to emit code that adjust the
stackpointer and jumps to the tailcallee (either label or register).
Like it is done for EH_RETURN.

in X86RegisterInfo.cpp we would then have
TargetRegisterInfo::emitEpilogue() {
    ...
    if (RetOpcode== X86::TC_RETURN){
      if (isDynamicCallee(RetOpCode))
        add esp  {stack adjustment from tc_return}
        jmp {register operand of tc_return}
      } else
        add esp  {stack adjustment from tc_return}
        jmp {targetfunction operand}
      }
}

resulting code for dynamic function
	
    mov  ecx  esi  #load callee, say esi holds the address of the
                   # tailcalled
    epilogue
    #TAILCALL
    add esp 8  #caller has 2 more arg
    jmp ecx

if the targetfunction is known

    epilogue
    #TAILCALL
    add esp 8 #caller has 2 more arg
    jmp _targetfunction

Should also work for architectures other than x86.

any critique, comments welcome
regards arnold