<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
p.gmail-m2170728851161876468msoplaintext, li.gmail-m2170728851161876468msoplaintext, div.gmail-m2170728851161876468msoplaintext
{mso-style-name:gmail-m_2170728851161876468msoplaintext;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal">Reply inline.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><b>From:</b> Reid Kleckner <rnk@google.com>
<br>
<b>Sent:</b> Saturday, March 28, 2020 11:59 AM<br>
<b>To:</b> Eli Friedman <efriedma@quicinc.com>; Arthur Eubanks <aeubanks@google.com><br>
<b>Cc:</b> llvm-dev <llvm-dev@lists.llvm.org><br>
<b>Subject:</b> [EXT] Re: [llvm-dev] [RFC] Replacing inalloca with llvm.call.setup and preallocated<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal" style="margin-left:.5in">Sorry for the delay. Arthur Eubanks has started working on the design here:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><a href="https://reviews.llvm.org/D74651">https://reviews.llvm.org/D74651</a> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">I felt I should follow up here about that. <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">On Mon, Jan 27, 2020 at 6:47 PM Eli Friedman <<a href="mailto:efriedma@quicinc.com">efriedma@quicinc.com</a>> wrote:<o:p></o:p></p>
</div>
<div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="gmail-m2170728851161876468msoplaintext" style="margin-left:.5in">It doesn’t seem like multiple call sites should be a problem if they’re sufficiently similar? If the argument layout for each callsite is the same, it doesn’t matter which callsite
the backend chooses to compute the layout<o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal" style="margin-left:.5in">It's feasible, but it seems like asking for bugs. What should the backend do when it detects two preallocated calls with different layouts? Let's imagine LTO is promoting one indirect call that uses call.setup into
several direct calls. The IR would look like this:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">%cs = call.setup<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">switch i32 %callee ...<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">callee1:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"> call void @callee1(i32 %x, %struct.Foo* preallocated(%struct.Foo) %foo)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"> br label %rejoin<o:p></o:p></p>
</div>
<div>
<div>
<p class="MsoNormal" style="margin-left:.5in">callee2:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"> call void @callee2(i32 %x, %struct.Foo* preallocated(%struct.Foo) %foo)<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"> br label %rejoin<o:p></o:p></p>
</div>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">rejoin:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"> ...<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">A logical next step would be to run DAE. Suppose one callee does not use i32 %x above. Now the prototypes disagree, and we can't lower the call. We could teach DAE that all calls using callsetup tokens have to have
the same prototype, but a simple verifier rule earlier (one call per call setup) seems easier to enforce.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">This would specifically be for cases where we try to rewrite the signature? I would assume we should forbid rewriting the signature of a call with an operand bundle. And once some optimization drops the bundle and preallocated marking,
to allow such rewriting, the signature doesn’t need to match anymore.<o:p></o:p></p>
<p class="MsoNormal"><o:p></o:p></p>
<p class="MsoNormal">Ultimately, I think it’s worth some effort here to try to avoid blocking optimizations like jump threading. That said, if you want to make the calls “noduplicate”, it isn’t that terrible of an alternative.<o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="gmail-m2170728851161876468msoplaintext" style="margin-left:1.0in">> Nested setup is OK, but the verifier rule that there must be a paired call site should make it impossible to do in a loop. I guess we should have some rule to reject the following:<o:p></o:p></p>
<p class="gmail-m2170728851161876468msoplaintext" style="margin-left:1.0in">%cs1 = llvm.call.setup()<o:p></o:p></p>
<p class="gmail-m2170728851161876468msoplaintext" style="margin-left:1.0in">%cs2 = llvm.call.setup()<o:p></o:p></p>
<p class="gmail-m2170728851161876468msoplaintext" style="margin-left:1.0in">call void @cs1() [ "callsetup"(token %cs1) ]<o:p></o:p></p>
<p class="gmail-m2170728851161876468msoplaintext" style="margin-left:1.0in">call void @cs2() [ "callsetup"(token %cs2) ]<o:p></o:p></p>
<p class="gmail-m2170728851161876468msoplaintext" style="margin-left:.5in"> <o:p></o:p></p>
<p class="gmail-m2170728851161876468msoplaintext" style="margin-left:.5in">I think in general, there can be arbitrary control flow between a token and its uses, as long as the definition dominates the use. So you could call llvm.call.setup repeatedly in a
loop, then call some function using the callsetup token in a different loop, unless some rule specific to callsetup forbids it.<o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal" style="margin-left:.5in">I agree that the IR would validate according to the current rules, but I would interpret that IR as meaning: setup N call sites in a loop, then destroy just the last call site N times in a loop. For example, if
you replaced the call site token in this example with stacksave+alloca and teardown with stackrestore, the semantics would be: allocate lots of stack, then reset to the last saved stack pointer repeatedly.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">I think we can write some non-verifier rules that prohibit this kind of code pattern. Optimizations should already obey these rules since they don't reorder things that modify inaccessible state. Things like:<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">- It is UB to stacksave ; call.setup ; stackrestore ; call<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">- UB to call.setup 1 ; call.setup 2 ; call 1 ; call 2<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">- UB to call.setup ; alloca ; call<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in">etc<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I’m fine with having UB in certain cases, as long as the rules are clear.<o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="gmail-m2170728851161876468msoplaintext" style="margin-left:.5in">It would be nice to make the rules strong enough to ensure we can statically compute the size of the stack frame at any point (assuming no dynamic allocas). Code generated by clang
would be statically well-nested, I think; not sure how hard it would be to ensure optimizations maintain that invariant.<o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal" style="margin-left:.5in">I agree, that is definitely a goal of the redesign. <o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Good. It might be a good idea to try to write out an algorithm for this to ensure this works out. In particular, I’m concerned about cases where two predecessors of a basic block appear to have a different stack size (an if-then-else,
or a loop backedge). We need to make sure such cases are either invalid, or UB on entry to the block.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I spent a little time thinking, and I’m not sure what rules we need to make this work out. For example, should we forbid tail-merging multiple calls to abort()? IF we should, how would we write a rule which restricts that?
<o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="gmail-m2170728851161876468msoplaintext" style="margin-left:.5in">Connecting nested llvm.call.setups using tokens might make it easier for passes to reason about the nesting, since the region nest would be explicitly encoded.<o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal" style="margin-left:.5in">I agree, that could be useful, it would replicate what we did for exception handling. <o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<div>
<div>
<p class="gmail-m2170728851161876468msoplaintext" style="margin-left:1.0in">> VLAs could use something like this, but they are generally of unknown size while call sites have a known fixed size. I think that makes them pretty different.<o:p></o:p></p>
<p class="gmail-m2170728851161876468msoplaintext" style="margin-left:.5in">I don’t think we need to implement it at the same time, but the systems would interact, so it might be worth planning out.<o:p></o:p></p>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal" style="margin-left:.5in">I do recall that MSVC does some pretty squirrelly stuff when you insert `alloca` calls into a call sequence. In this example, arguments are evaluated in the order 2, 3, 1:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I’m not really concerned with funny usage of calls to alloca() in call arguments, or anything like that. I’m happy to pick whatever rule is easiest for us. I’m more concerned with ensuring nothing blows up if we inline a call to a function
that contains a VLA, or something like that.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p class="MsoNormal">-Eli<o:p></o:p></p>
</div>
</div>
</div>
</div>
</body>
</html>