[llvm-dev] [RFC] Adding CPS call support

[Friedman, Eli via llvm-dev]

On 4/17/2017 3:52 PM, Kavon Farvardin wrote:
> (Sorry for the 2nd email Eli, I forgot to reply-all).
>
>> I'm not following how explicitly representing the return address of a call in the IR before isel actually solves any relevant issue. We already pass the return address implicitly as an argument to every call; you can retrieve it with llvm.returnaddress if you need it.
>
> Unfortunately the @llvm.returnaddress intrinsic does not solve the problem, as it only reads the return address pushed onto the LLVM stack by a call. We would then need a way to move the LLVM stack pointer back to where it was before the call, because a CPS call _must_ not grow the LLVM stack (it will never be popped!), so a 'call' instruction will not do.

Most architectures have a call instruction which does not push anything 
onto the stack; e.g. on ARM, the "BL" instruction saves the return 
address in LR.  On other architectures, you can emulate this (for 
example, you could lower an IR "call" to LEA+JMP on x86-64).

>> You can't branch across functions like you're proposing because the stack and callee-save registers won't be in the right state.  LLVM will inevitably save values to the stack for calls which are not tail calls.  Therefore, this proposal simply doesn't work.
> It might be helpful to think of the CPS transformation as turning the program into a form such that it always moves "forward", in the sense that the tail calls _never_ return. A "return" is simply another tail call (i.e., a jump) to a return address, which looks no different than a function call.
>
> Thus, we have no callee-saved registers to worry about since the tail calls never come back. In addition, there are no live values in the LLVM stack frame, since they are all passed in the CPS call (which uses a different stack). Thus, retpt receives all of its values from the struct it extracts from. While the 'cps' marked call appears to be non-tail, it will be lowered to a tail call.

The return address for the current function is fundamentally live across 
any non-tail call.  And LLVM will hoist other operations across non-tail 
calls, and in the process introduce values which are live across calls.  
You need to save those values somewhere.  The key question is where.  
Your proposal tries to address that by explicitly saving/restoring the 
return address onto the GHC stack, but you're working at the wrong 
level; you can't get a complete list of which values are live across 
calls until register allocation.

-Eli

-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project