<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;}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;}
@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">I assume by “drop support”, you mean reject it in the bitcode reader/IR parser? We can’t reasonably support a complex feature like inalloca if nobody is testing it. If we can’t reasonably upgrade it, and we don’t think there are any users
other than clang targeting 32-bit Windows, probably dropping support is best.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">More details comments on the proposal:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">“llvm.call.setup must have exactly one corresponding call site”: Normal IR rules would allow cloning the call site (in jump threading), or erasing the call site (if there’s a noreturn call in an argument). What’s the benefit of enforcing
this rule, as opposed to just saying all the call sites must have the same signature?<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">The proposal doesn’t address what happens if llvm.call.setup is called while there’s another llvm.call.setup still active. Is it legal to call llvm.call.setup in a loop? Or should nested llvm.call.setup calls have the parent callsetup
token as an operand?<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Is there some way we can allow optimizations if we can’t modify the callee, but we can prove nothing captures the address of the preallocated region before the call? I guess under the current proposal we could transform preallocated->byval,
but that isn’t very exciting.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">How does this interact with other dynamic stack allocations? Should we switch VLAs to use a similar mechanism? (The problems with dynamic alloca in general aren’t as terrible, but it might still benefit: for example, it’s much easier
to transform a dynamic allocation into a static allocation.)<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">“If an exception is thrown and caught within the call setup region, the newly established SP must be saved into the EH record when a call is setup.” What makes this case special vs. what we currently implement? Is this currently broken?
Or is it related to supporting frame pointer elimination?<o:p></o:p></p>
<p class="MsoNormal"><o:p></o:p></p>
<p class="MsoNormal">-Eli<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4.0pt">
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b>From:</b> llvm-dev <llvm-dev-bounces@lists.llvm.org> <b>On Behalf Of
</b>Reid Kleckner via llvm-dev<br>
<b>Sent:</b> Sunday, January 26, 2020 3:12 PM<br>
<b>To:</b> llvm-dev <llvm-dev@lists.llvm.org><br>
<b>Subject:</b> [EXT] [llvm-dev] [RFC] Replacing inalloca with llvm.call.setup and preallocated<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal">Hello all,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">A few years ago, I added the inalloca feature to LLVM IR so that Clang could be C++ ABI compatible with MSVC on 32-bit x86. The feature works, but there is room for improvement. I recently took the time to write up a design using token
values that will hopefully be better named and easier to work with and around.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">For the technical details of the proposal, I've written up the RFC in Markdown here:<o:p></o:p></p>
</div>
<p class="MsoNormal"><a href="https://github.com/rnk/llvm-project/blob/call-setup-docs/llvm/docs/CallSetup.md">https://github.com/rnk/llvm-project/blob/call-setup-docs/llvm/docs/CallSetup.md</a><o:p></o:p></p>
<div>
<p class="MsoNormal">I've pasted the text below if you want to quote and reply on the list.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">The main question I have for the community is, given that it is infeasible to upgrade inalloca to llvm.call.setup, can we drop support for the old IR? So far as I am aware, Clang has been the only user of this attribute, and only for i*86-windows-msvc
targets. The main goal of adding llvm.call.setup is to get rid of inalloca, so if all LLVM IR transforms have to keep knowing about it, there is no reason to add a new way to do the same thing.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Thanks,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Reid<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">The last RFC: <a href="http://lists.llvm.org/pipermail/llvm-dev/2013-July/064218.html">http://lists.llvm.org/pipermail/llvm-dev/2013-July/064218.html</a> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Current inalloca docs: <a href="https://llvm.org/docs/InAlloca.html">https://llvm.org/docs/InAlloca.html</a> <o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">----------------<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal"># RFC: Replace inalloca with llvm.call.setup and preallocated<br>
<br>
In order to pass non-trivially copyable objects by value in a way that is<br>
compatible with the Visual C++ compiler on 32-bit x86, Clang has to be able to<br>
separate the allocation of call argument memory from the call site. The<br>
`inalloca` feature was added to LLVM for this purpose. However, this feature<br>
usually results in inefficient code, and is often incompatible with otherwise<br>
straightforward LLVM IR transforms. Therefore, I would like to get rid of it<br>
and replace it with `llvm.call.setup`, which I hope will be more maintainable<br>
in the long run.<br>
<br>
These are some of the drawbacks of inalloca that I want to fix with the new IR:<br>
- Blocks most interprocedural prototype changing transforms: dead argument<br>
elimination, argument promotion, application of fastcc, etc.<br>
- Blocks alias analysis: Unrelated args in memory are hard to analyze<br>
- Blocks function attribute inference for unrelated parameters<br>
- Hard for frontends to use because one argument can affect every other argument<br>
<br>
Since inalloca was added, the token type was added to LLVM. Transforms are not<br>
allowed to obscure the definition of a token value, and tokens can be used to<br>
create single-entry, multi-exit regions in LLVM IR. This allows the creation of<br>
a call setup operation that must remain paired with its call site throughout<br>
mid-level optimization. That guarantee allows the backend to look at the call<br>
site when emitting the call setup instructions. If the IR for a call setup<br>
forms a proper region, that can also help the backend perform frame pointer<br>
elimination in many cases.<br>
<br>
## New IR Features<br>
<br>
Here is the list of new IR features I think this requires:<br>
<br>
Intrinsics:<br>
- `token @llvm.call.setup(i32 %numArgs)`<br>
- `i8* @llvm.call.alloc(token %site, i32 %argIdx)`<br>
- `void @llvm.call.teardown(token)`<br>
<br>
Attributes:<br>
- `preallocated(<ty>)`, similar to byval, but no copy<br>
<br>
Bundles:<br>
- `[ "callsetup"(token %site) ]`<br>
<br>
Verifier rules:<br>
- `llvm.call.setup` must have exactly one corresponding call site<br>
- call site must have equal number of preallocated args to `llvm.call.setup`<br>
<br>
## Intended Usage<br>
<br>
Here is an example of LLVM IR for an unpacked call site:<br>
<br>
```llvm<br>
%cs = call token @llvm.call.setup(i32 3)<br>
%m0 = call i8* @llvm.call.alloc(token %cs, i32 0) ;; allocates {i32}<br>
call void @llvm.memset*(i8* %m0, i32 0, i32 4)<br>
%m1 = call i8* @llvm.call.alloc(token %cs, i32 1) ;; allocates {i32, i32}<br>
call void @llvm.memset*(i8* %m1, i32 0, i32 8)<br>
%m2 = call i8* @llvm.call.alloc(token %cs, i32 2) ;; allocates {i32, i32, i32}<br>
call void @llvm.memset*(i8* %m2, i32 0, i32 12)<br>
call void @use_callsetup(<br>
{i32}* preallocated({i32}) %m1,<br>
i32 13,<br>
{i32,i32}* preallocated({i32,i32}) %m2,<br>
i32 42,<br>
{i32,i32,i32}* preallocated({i32,i32,i32}) %m3)<br>
[ "callsetup"(token %cs) ]<br>
```<br>
<br>
Many transforms will need to be made aware of the new verifier guarantees, but<br>
they should only block optimizations on preallocated arguments. The goal is<br>
that unrelated arguments, such as the i32 arguments above, remain unaffected.<br>
DAE, for example, is free to eliminate the plain integers, but it cannot<br>
eliminate a preallocated argument without adjusting the call.setup.<br>
<br>
The next most important thing to keep in mind is how this interacts with<br>
exception handling. This is where `llvm.call.teardown` comes into play. The<br>
idea is that, in a call region, clang should push an exceptional cleanup onto<br>
the cleanup stack. Here is what the IR for the previous example would look<br>
like, assuming each argument has a constructor that may throw:<br>
<br>
```llvm<br>
%cs = call token @llvm.call.setup(i32 3)<br>
%m0 = call i8* @llvm.call.alloc(token %cs, i32 0)<br>
invoke void @ctor0(i8* %m0)<br>
to label %cont0 unwind label %cleanupCall<br>
<br>
cont0:<br>
%m1 = call i8* @llvm.call.alloc(token %cs, i32 1)<br>
invoke void @ctor1(i8* %m1)<br>
to label %cont1 unwind label %cleanup0<br>
<br>
cont1:<br>
%m2 = call i8* @llvm.call.alloc(token %cs, i32 2)<br>
invoke void @ctor2(i8* %m2)<br>
to label %cont2 unwind label %cleanup1<br>
<br>
cont2:<br>
call void @use_callsetup(i8* preallocated %m1,<br>
i32 13,<br>
i8* preallocated %m2,<br>
i32 42,<br>
i8* preallocated %m3)<br>
[ "callsetup"(token %cs) ]<br>
<br>
<br>
cleanup1:<br>
%cl1 = cleanuppad unwind to caller<br>
call void @dtor(i8* %m1) [ "funclet"(token %cl1) ]<br>
cleanupret %cl1 to label %cleanup0<br>
<br>
cleanup0:<br>
%cl0 = cleanuppad unwind to caller<br>
call void @dtor(i8% %m0) [ "funclet"(token %cl2) ]<br>
cleanupret %cl0 to label %cleanupCall<br>
<br>
cleanupCall:<br>
%clC = cleanuppad unwind to caller<br>
call void @llvm.call.teardown(token %cs) ;; Or llvm.call.cleanup?<br>
cleanupret %clC to caller<br>
```<br>
<br>
Generally, cleanups to tear down a call setup region are not needed if control<br>
cannot return to the current function. The cleanupCall block is an example of<br>
such an unnecessary cleanup. However, to make things easy for the inliner, the<br>
frontend is required to emit these cleanups. Prior to code generation, the<br>
WinEHPrepare pass can remove any unneeded argument memory cleanups.<br>
<br>
## Canonical Form<br>
<br>
`llvm.call.setup` is designed for compatibility, not for performance or<br>
analyzability. Mid-level optimization passes should generally try to remove<br>
these intrinsics and attributes when possible. When it is possible to change<br>
the prototype of a function using these attributes, call sites should be<br>
canonicalized in the following way:<br>
<br>
- Create a static alloca of appropriate type for each preallocated argument<br>
- Replace all uses of `llvm.call.alloc` with the corresponding new alloca<br>
- Insert `lifetime.start` for each static alloca at the original alloc site,<br>
and `llvm.lifetime.end` after the call and at `llvm.call.teardown`.<br>
- Remove all setup, alloc, teardown intrinsics, and remove the `preallocated`<br>
attributes from caller and callee.<br>
<br>
GlobalOpt seems like a logical place for this transform. This form should<br>
enable downstream optimizations, and reduce the number of transforms that need<br>
to be taught that `llvm.call.alloc` creates stack memory.<br>
<br>
## Inliner Considerations<br>
<br>
When inlining a call site that uses `llvm.call.setup`, the inliner should also<br>
make the transforms described above, only without adjusting the callee's<br>
prototype.<br>
<br>
## Corner cases<br>
<br>
### Catching an exception within a call region<br>
<br>
If an exception is thrown and caught within the call setup region, the newly<br>
established SP must be saved into the EH record when a call is setup. Consider<br>
the case below of inlining try / catch into a call region:<br>
<br>
```c++<br>
struct Foo {<br>
Foo(int x);<br>
Foo(const Foo &o);<br>
~Foo();<br>
int x, y, z;<br>
};<br>
void use_callsetup(int, Foo, Foo);<br>
int maythrow2();<br>
static inline int maythrow() {<br>
try { return maythrow2(); } catch (int) {}<br>
return 0;<br>
}<br>
Foo getf();<br>
int main() {<br>
use_callsetup(maythrow(), getf(), getf());<br>
}<br>
```<br>
<br>
The backend should be able to detect whether SP must be saved or not by<br>
checking if there are any invokes reachable along normal paths from the call<br>
setup that do not first reach the call itself, or a normal `llvm.call.teardown`.<br>
<br>
### Non-exceptional call region exit<br>
<br>
It is possible, using statement expressions, to exit a call setup region with<br>
normal control flow. In this case, the Clang should emit a normal cleanup to<br>
call `llvm.eh.teardown`. Consider:<br>
<br>
```c++<br>
#define RETURN_IF_ERR(maybeError) \<br>
({ \<br>
auto val = maybeError; \<br>
if (val.isError()) \<br>
return val.getError(); \<br>
val.getValue; \<br>
})<br>
ErrorOr<int> mayFail();<br>
void use_callsetup(int, Foo);<br>
void f(bool cond) {<br>
use_callsetup(RETURN_IF_ERR(mayFail()), Foo());<br>
}<br>
```<br>
<br>
### Inlining non-EH code into EH code<br>
<br>
If exceptions are disabled, the frontend should not emit exceptional cleanups<br>
to teardown the call region. However, this code could be inlined into a<br>
function that uses exceptions, and the caller could catch an exception thrown<br>
through the non-EH code. Generally this should be impossible, because the calls<br>
will be marked nounwind, and it is UB to throw an exception through a nounwind<br>
call site. However, SEH allows exceptions to be thrown through nounwind call<br>
sites. Consider:<br>
<br>
```c++<br>
int mayThrow();<br>
void use_callsetup(int, Foo);<br>
static inline void inlineMe() {<br>
void use_callsetup(mayThrow(), Foo());<br>
}<br>
void f(int numRetries) {<br>
for (int i = 0; i < numRetries; i++) {<br>
__try {<br>
inlineMe();<br>
} __except (1) {<br>
}<br>
}<br>
}<br>
```<br>
<br>
Unless the compiler inserts stack adjustments along the unwind path, this well<br>
setup call argument memory for every loop iteration, and never clean it up.<br>
This could result in code generation bugs or excessive stack memory use. The<br>
two options are:<br>
1. Refuse to inline functions containing call regions through invoke call sites<br>
1. Teach the inliner to synthesize llvm.call.teardown cleanups inside call<br>
regions<br>
1. Do nothing, the frontend already disables inlining into `__try`<br>
<br>
Given that this corner case seems specific to SEH, the third option seems most<br>
reasonable.<br>
<br>
## Implementation Steps<br>
<br>
In the spirit of incremental development, I think the implementation could be<br>
broken down into the following patch series:<br>
- IR: LLVM IR intrinsics and attributes<br>
- Clang: IRGen, under -cc1 flag<br>
- X86: backend implementation: inefficient, no EH<br>
- Transforms: Update inliner and globalopt, audit other transforms<br>
- X86: MSVC C++ EH SP management<br>
- ... test it on Chrome with -cc1 flag<br>
- Clang: Remove cc1 flag and inalloca IRGen logic<br>
- ... announce inalloca removal from LLVM IR<br>
- inalloca removal<br>
<br>
## Backwards compatibility<br>
<br>
It may be possible to upgrade some bitcode from `inalloca` to<br>
`llvm.call.setup`, but in cases with complex control flow where the allocation<br>
site does not dominate the call, it will not be straightforward. Therefore, I<br>
think we should make an exception to LLVM's usual policy of bitcode backwards<br>
compatibility, and drop support for `inalloca`. The `inalloca` attribute was<br>
generally a source of bugs, and was only used for code targetting<br>
`i*86-windows-msvc`. To the best of my knowledge, there are no users of LLVM<br>
who archive bitcode for that platform and expect to be able to upgrade it for<br>
use with future LLVM versions.<o:p></o:p></p>
</div>
</div>
</div>
</div>
</body>
</html>