<div dir="ltr"><p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif">It
does look similar to LLVM Coroutines. I was considering adding a few more intrinsics to support
CPS case, but, decided to defer until we have use cases and people willing to
do the work </span><span style="font-size:11pt;font-family:wingdings">J</span><span style="font-size:11pt;font-family:calibri,sans-serif">.<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif">Coroutine
passes chop up the function into smaller pieces at suspend points, a CPS call
can be represented as a suspend point.<span></span></span></p>
<p class="MsoNormal"><a name="_MailEndCompose"><span style="font-size:11pt;font-family:calibri,sans-serif"><span> </span></span></a></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif">Currently a suspend
point looks like this:<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif"><span> </span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif"> %sp1 = call
token @llvm.coro.save()<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif"> <some code
may go here> ; if this is a call, it will be replaced with tail call where
calling convention allows<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif"> call i8
@llvm.coro.suspend(token %sp1) ; <span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif"><span> </span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif">Two extra intrinsics
I was considering were:<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif"><span> </span></span></p>
<p style="margin:0in 0in 0.0001pt"><span style="font-size:11pt;font-family:calibri,sans-serif">%addr = i8*
@llvm.resume.addr(tok) ; gives an address of an extracted continuation
function.<span></span></span></p>
<p style="margin:0in 0in 0.0001pt"><span style="font-size:11pt;font-family:calibri,sans-serif"><type>
@llvm.resume.value.<type>(tok) ; gives a return value on resume<span></span></span></p>
<p style="margin:0in 0in 0.0001pt"><span style="font-size:11pt;font-family:calibri,sans-serif"><span> </span></span></p>
<p style="margin:0in 0in 0.0001pt"><span style="font-size:11pt;font-family:calibri,sans-serif">Int foo() {<span></span></span></p>
<p style="margin:0in 0in 0.0001pt"><span style="font-size:11pt;font-family:calibri,sans-serif"> PartA…<span></span></span></p>
<p style="margin:0in 0in 0.0001pt"><span style="font-size:11pt;font-family:calibri,sans-serif"> Int r =
bar(args);<span></span></span></p>
<p style="margin:0in 0in 0.0001pt"><span style="font-size:11pt;font-family:calibri,sans-serif"> PartB …<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif">}<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif"><span> </span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif">It can get
represented as:<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif"><span> </span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif">Int foo() {<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif"> PartA<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif"> %sp1 = call
token %llvm.coro.save()<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif"> %resume_addr =
call @llvm.coro.resume.addr(%sp1)<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif"> call
bar(args, %resume_addr)<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif"> call
@llvm.coro.suspend(%sp1)<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif"> %r = call
%llvm.coro.resume.value<int>(%sp1)<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif"> PartB<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif">}<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif"><span> </span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif">Coroutine passes
after foo() is optimized will extract the continuation into a separate
function:<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif"><span> </span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif">foo$resume1(int r) {<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif"> PartB<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif">}<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif"><span> </span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif">And suspend point
will be replaced with a jump to bar()<span></span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif"><span> </span></span></p>
<p class="MsoNormal"><span style="font-size:11pt;font-family:calibri,sans-serif"><span> </span></span></p>
<p class="MsoNormal"><b><span style="font-size:11pt;font-family:calibri,sans-serif">From:</span></b><span style="font-size:11pt;font-family:calibri,sans-serif"> Reid Kleckner [<a href="mailto:rnk@google.com">mailto:rnk@google.com</a>] <br>
<b>Sent:</b> Tuesday, April 18, 2017 3:00 PM<br>
<b>To:</b> Kavon Farvardin <<a href="mailto:kavon@farvard.in">kavon@farvard.in</a>>;
Gor Nishanov <<a href="mailto:gorn@microsoft.com">gorn@microsoft.com</a>><br>
<b>Cc:</b> llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><br>
<b>Subject:</b> Re: [llvm-dev] [RFC] Adding CPS call support<span></span></span></p>
<p class="MsoNormal"><span> </span></p>
<p class="MsoNormal">This seems to be solving a problem very similar to C++
coroutines. You might find it helpful to read the past discussion of their
design in LLVM.<span></span></p>
<p class="MsoNormal"><span> </span></p>
<p class="MsoNormal">What do you think is more important for GHC: getting good or
highly tunable low-level code, or enabling mid-level optimizations such as GVN
across calls? Is GHC using LLVM more as an optimizer or as a code generator?<span></span></p>
<p class="MsoNormal"><span> </span></p>
<p class="MsoNormal">If GHC's code generation pipeline leaves opportunities for
LLVM mid-level optimization, then I think you want to pursue a design similar
to C++ coroutines, where we leave the control flow graph "uninverted"
until code generation. I might be making up terminology here, but I think of
transforming a program representation to continuation-passing style as
"inverting" the CFG. I'm not suggesting that you use the native stack
to store VM data, I'm just suggesting that you hide the fact that CPS calls
will really be tail calls and returns from LLVM until code generation.<span></span></p>
<p class="MsoNormal"><span> </span></p>
<p class="MsoNormal">On Mon, Apr 17, 2017 at 8:30 AM, Kavon Farvardin via
llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>>
wrote:<span></span></p>
<p class="MsoNormal">Summary<br>
=======<br>
<br>
There is a need for dedicated continuation-passing style (CPS) calls in LLVM to<br>
support functional languages. Herein I describe the problem and propose a<br>
solution. Feedback and/or tips are greatly appreciated, as our goal is to<br>
implement these changes so they can be merged into LLVM trunk.<br>
<br>
<br>
Problem<br>
=======<br>
<br>
Implementations of functional languages like Haskell and ML (e.g., GHC and<br>
Manticore) use a continuation-passing style (CPS) transformation in order to<br>
manage the call stack explicitly. This is done prior to generating LLVM IR, so<br>
the implicit call stack within LLVM is not used for call and return.<br>
<br>
When making a non-tail call while in CPS, we initialize a stack frame for the<br>
return through our own stack pointer, and then pass that stack pointer to the<br>
callee when we jump to it. It is here when we run into a problem in LLVM.<br>
<br>
Consider the following CPS call to @bar and how it will return:<br>
<br>
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;<br>
<br>
define void @foo (i8** %sp, ...) {<br>
someBlk:<br>
; ...<br>
; finish stack frame by writing return address<br>
%retAddr = blockaddress(@foo, %retpt)<br>
store i8* %retAddr, i8** %sp<br>
; jump to @bar<br>
tail call void @bar(i8** %sp, ...)<br>
<br>
retpt:
; <- how can @bar
"call" %retpt?<br>
%sp2 = ???<br>
%val = ???<br>
; ...<br>
<br>
}<br>
<br>
define void @bar (i8** %sp, ...) {<br>
; perform a return<br>
%retAddr0 = load i8*, i8** %sp<br>
%retAddr1 = bitcast i8* %retAddr0 to void (i8**,
i64)*<br>
%val = bitcast i64 1 to i64<br>
; jump back to %retpt in @foo, passing %sp
and %val<br>
tail call void %retAddr1(i8** %sp, i64 %val)<br>
}<br>
<br>
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;<br>
<br>
There is currently no way to jump back to %retpt from another function, as
block<br>
addresses have restricted usage in LLVM [1]. Our main difficulty is that we<br>
cannot jump to a block address without knowing its calling convention, i.e.,
the<br>
particular machine registers (or memory locations) that the block expects<br>
incoming values to be passed in.<br>
<br>
The workaround we have been using in GHC for LLVM is to break apart every<br>
function, placing the code for the continuation of each call into a new<br>
function. We do this only so that we can store a function pointer instead of a<br>
block address to our stack. This particularly gross transformation inhibits<br>
optimizations in both GHC and LLVM, and we would like to remove the need for
it.<br>
<br>
<br>
Proposal<br>
========<br>
<br>
I believe the lowest-impact method of fixing this problem with LLVM is the<br>
following:<br>
<br>
First, we add a special 'cps' call instruction marker to be used on non-tail<br>
calls. Then, we use a specialized calling convention for these non-tail calls,<br>
which fix the returned values to specific locations in the machine code [2].<br>
<br>
To help illustrate what's going on, let's rewrite the above example using the<br>
proposed 'cps' call:<br>
<br>
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;<br>
<br>
define { ... } @foo (i8** %sp, ...) {<br>
someBlk:<br>
; ...<br>
; finish stack frame by writing return address<br>
%retAddr = blockaddress(@foo, %retpt)<br>
store i8* %retAddr, i8** %sp<br>
; jump to @bar<br>
%retVals = cps call ghccc {i8**, i64} @bar (i8** %sp, ...)<br>
br label %retpt<br>
<br>
retpt:<br>
%sp2 = extractvalue {i8**, i64} %retVals, 0<br>
%val = extractvalue {i8**, i64} %retVals, 1<br>
; ...<br>
<br>
}<br>
<br>
define {i8**, i64} @bar (i8** %sp, ...) {<br>
; perform a return<br>
%retAddr0 = load i8*, i8** %sp<br>
%retAddr1 = bitcast i8* %retAddr0 to {i8**, i64}
(i8**, i64)*<br>
%val = bitcast i64 1 to i64<br>
; jump back to %retpt in @foo, passing %sp
and %val<br>
tail call ghccc void %retAddr1(i8** %sp, i64 %val)<br>
<br>
unreachable ; <- ideally this would
be our terminator,<br>
;
but 'unreachable' breaks TCO, so we will<br>
;
emit a ret of the struct "returned" by the call.<br>
}<br>
<br>
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;<br>
<br>
The important point here is that the 'cps' marked call will lower to a jump.
The<br>
'cps' call marker means that the callee knows how to return using the arguments<br>
explicitly passed to it, i.e., the stack pointer %sp. The callee cannot use a<br>
'ret' instruction if it is 'cps' called.<br>
<br>
Either before or during 'cps' call lowering, any instructions following the<br>
'cps' call to @bar are sunk into the the block %retpt, and the unconditional<br>
branch to %retpt is deleted/ignored. We include that branch to preserve<br>
control-flow information for LLVM IR optimization passes.<br>
<br>
The 'extractvalue' instructions are what ensure the calling convention of<br>
%retpt, since the fields of the struct %retVals are returned in physical<br>
registers dictated by the (modified) ghccc convention. Those same physical<br>
registers are used by the ghccc tail call in @bar when it jumps back to %retpt.<br>
So, the call & return convention of ghccc ensures that everything matches
up.<br>
<br>
<br>
Interaction with LLVM<br>
=====================<br>
<br>
(1) Caller-saved Values<br>
<br>
One may wonder how this would work if there are caller-saved values of the
'cps'<br>
call. But, in our first example, which closely matches what CPS code looks
like,<br>
the call to @bar was in tail position. Thus, in the second example, there are
no<br>
caller-saved values for the 'cps' call to @bar, as all live values were passed<br>
as arguments in the call.<br>
<br>
This caller-saved part is a bit subtle. It works fine in my experience [2] when<br>
@bar is a function not visible to LLVM. My impression is that even if @bar is<br>
visible to LLVM, there is still no issue, but if you can think of any corner<br>
cases that would be great!<br>
<br>
(2) Inlining<br>
<br>
My gut feeling is that we cannot inline a 'cps' marked call-site without more<br>
effort. This is because we might end up with something odd like this once the<br>
dust settles:<br>
<br>
%retAddr = blockaddress(@foo, %retpt)<br>
%retAddr1 = bitcast i8* %retAddr to {i8**, i64} (i8**, i64)*<br>
tail call ghccc %retAddr1 ( %sp, ... )<br>
<br>
We could add a pass that turns the above sequence into just an unconditional<br>
branch to %retpt, using a phi-node to replace each 'extractvalue' instruction
in<br>
that block.<br>
<br>
I'm not sure whether inlining in LLVM is important for us yet, as we tend to<br>
inline quite a lot before generating LLVM IR. I don't think this additional
fix-<br>
up pass would be too difficult to implement if it's desired.<br>
<br>
<br>
Implementation Sketch and Conclusion<br>
====================================<br>
<br>
My current plan is to add this special lowering of 'cps' calls during the<br>
translation from LLVM IR to the SelectionDAG. I welcome any suggestions or tips<br>
on the best way to approach this. An important goal for us is to merge this
into<br>
trunk since we do not want to bundle a special version of LLVM with GHC.<br>
<br>
Please let me know soon if you have any objections to this feature.<br>
<br>
Thanks for reading,<br>
Kavon<br>
<br>
<br>
References<br>
==========<br>
<br>
[1] <a href="https://na01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fllvm.org%2Fdocs%2FLangRef.html%23blockaddress&data=02%7C01%7Cgorn%40microsoft.com%7C27c084b10ef140f65ed708d486a64e30%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C636281496211718883&sdata=zSkPdTTe2DsfZPoNCiWJGYU%2Byi%2BVyJZIECqpffATfhU%3D&reserved=0" target="_blank">http://llvm.org/docs/LangRef.html#blockaddress</a><br>
[2] <a href="https://na01.safelinks.protection.outlook.com/?url=http%3A%2F%2Fkavon.farvard.in%2Fpapers%2Fml16-cwc-llvm.pdf&data=02%7C01%7Cgorn%40microsoft.com%7C27c084b10ef140f65ed708d486a64e30%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C1%7C636281496211718883&sdata=1xT8khSGaDvreysDiINp9Kss65o492horkNqMTCsYRs%3D&reserved=0" target="_blank">http://kavon.farvard.in/papers/ml16-cwc-llvm.pdf</a><br>
<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="https://na01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flists.llvm.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fllvm-dev&data=02%7C01%7Cgorn%40microsoft.com%7C27c084b10ef140f65ed708d486a64e30%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C636281496211718883&sdata=XWL4PwGJXuL3kbRueMFl7o0v6GeupHRu8L2mWD9h350%3D&reserved=0" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><span></span></p>
<p class="MsoNormal"><span> </span></p></div>