Differential D74651
Add IR constructs for inalloca replacement preallocated call setup Authored by aeubanks on Feb 14 2020, 2:18 PM.
Details Add llvm.call.setup and llvm.call.alloc instrinsics. Verifier changes for these IR constructs. See https://github.com/rnk/llvm-project/blob/call-setup-docs/llvm/docs/CallSetup.md
Diff Detail
Event TimelineComment Actions Nice, that's the essence of the verifier checks, and the tests look pretty good. LLVM has an 80 character limit, and the easiest way to handle that is to use clang-format. I recommend setting up an editor integration so you can use it interactively as you edit code, or running git-clang-format before uploading.
Comment Actions Simplify some code, add more tests, check operand bundle type instead of checking that the value is a ConstantTokenNone
Comment Actions Add preallocated attribute, major cleanups
Comment Actions I would add a test to llvm/test/Bitcode/attributes.ll for preallocated. Other than that, I think we can assume that the attribute machinery works, and we don't need dedicated round-trip testing like we did for inalloca (llvm/test/(Assembler|Bitcode)/inalloca.ll). I basically think this looks good, but I think we need rules in llvm/docs/LangRef.rst before landing this, which means we need to wrap up the discussion on llvm-dev with Eli.
Comment Actions
Comment Actions
Comment Actions I looked through this again, and basically think all the code looks good, but I want to get input from Eli, so I added him as a reviewer. Eli, any concerns with the design or naming before landing this? I was surprised we didn't get more name suggestions upstream. Arthur, now that you've worked with the names a bit, do you feel like they make sense? Would you change them? Comment Actions We still need a LangRef patch at some point. I suspect we might end up tweaking the signature of llvm.call.setup, based on the llvm-dev discussion, but we can experiment in-tree, I guess.
Comment Actions @llvm.call.alloc is weird because it's not allocating anything, the allocation happens in @llvm.call.setup. Maybe @llvm.call.arg is better?
Comment Actions I think when I came up with this terminology, I was thinking that alloc would actually do the allocation, so there would be a staircase of ESP adjustments. However, it's true, in the current implementation, alloc is a misnomer, and we might never implement SP staircasing (I don't have a better name for this code pattern...). Consider the code MSVC generates for a call like this: struct Foo { Foo(int x); Foo(const Foo &o); ~Foo(); int x, y; };
void callee(int, Foo, int, Foo, int, Foo);
void bar() {
callee(1, Foo(2), 3, Foo(4), 5, Foo(6));
}Each ESP adjustment happens immediately before the argument is evaluated. It lets the compiler pass scalar memory arguments with the PUSH instruction, which is good for code size, and I hear performance, although I have no first hand evidence of this. In any case, I think we should use a name that makes sense for either implementation strategy. Should we double down on the preallocated terminology? llvm.call.preallocated.arg? The number arguments make more sense this way, they refer to the N'th "preallocated" argument. The pattern would be: %cs = call token @llvm.call.setup(i32 3) %x = call i8* @llvm.call.preallocated.arg(token %cs, i32 0) %y = call i8* @llvm.call.preallocated.arg(token %cs, i32 1) %z = call i8* @llvm.call.preallocated.arg(token %cs, i32 2) ... (I suppose that if we ever wanted to do staircasing, we would have to require that the calls be evaluated right to left.) Comment Actions
I like adding preallocated to the intrinsic name, but I think we should do it for all the intrinsics, especially since the @llvm.call prefix seems fairly generic. Does the LangRef patch typically come before, after, or in the same commit? After doing some experimenting? Comment Actions I like that nomenclature. The the whole feature can be referred to as "calls with preallocated argument memory" or "preallocated call sites", and it sounds like grammatically correct English.
I guess in this case it would be best to put together a LangRef patch to land before this one, in case anyone wants to look at it alone, without the boilerplate. The main thing we need in LangRef is to document the verifier rules that were added, and the rules for how to use the intrinsics without causing UB. The intrinsics depend on some unobservable state (ESP), and have to be called in a particular order to work at runtime. Comment Actions A nice feature of landing LangRef changes coincidentally with IR changes is having the documentation at https://www.llvm.org/docs/LangRef.html match the code in https://github.com/llvm/llvm-project. But if there's a good reason to split them up I agree with @rnk that "docs before" is the right order. Comment Actions Add LangRef Comment Actions I added the LangRef change to this change, it shouldn't be too hard to just look at the LangRef changes. Comment Actions I renamed the "callsetup" operand bundle to "preallocated" because of this, lmk if that's too confusing since the attribute is also called "preallocated".
Comment Actions LGTM. Please give Reid a chance to comment before you merge, though.
Comment Actions Reid and I talked a bit and decided that this hadn't handled the case of when there's a setup without a call (e.g. via DCE). The stack adjustment will happen, but without the call the stack won't be cleaned up. One solution is turn the calls to llvm.call.preallocated.arg into allocas. But we need to know the type of the argument, and without the call we don't have that info. One solution is to add a call site attribute to llvm.call.preallocated.arg with the type. I reused the preallocated attribute for this purpose. Thoughts on this approach? Comment Actions Your proposed solution to finding the correct type of an allocation with a corresponding call seems fine. Not sure about rewrite llvm.call.preallocated.arg to an alloca. Not sure you'd actually want to explicitly rewrite it; probably simpler to come up with some fake stack layout and go through the normal lowering. On a related note, I just realized there isn't any discussion of alignment in the documentation. Have you thought about how the alignment of preallocated arguments is specified? Comment Actions Thanks for reviewing Eli! I had some wording suggestions and syntax nits worth reuploading for.
Comment Actions Based on what I know of the codegen design, that is feasible, but it will be discovered post-isel, which is pretty late. During instruction finalizations, the DenseMap entry for the call site will be missing. We can make a stack object of appropriate size and alignment at that point, but it's much less convenient than assuming we've taken care of it by CGP. We already have to write an IR transform utility to rewrite these intrinsics to allocas, at the very least for the inliner. Functionattrs (or the new Attributor) should remove this preallocated attributes when possible, so that pass will want this utility. And, if a call site gets eliminated because it is unreachable, we'll want to call this utility from standard cleanup passes like instcombine. Once we have the utility, we might as well just call it from CGP and rely on it later, instead of implementing it a second time.
The alignment can be surprising. For example, MSVC does not align double arguments or argument structs containing double, despite alignof(double) == 8. MSVC will align vectors and structs that carry __declspec(align) or alignas attributes, but in those cases, it passes the argument by address using a regular alloca. Is it possible to put an align attribute on a return value? If so, we could put it on the return value at the call site. However, for our purposes, it would always be 4. That's never enough to do any interesting transforms, so it's almost as good as leaving it unspecified.
Comment Actions Overlooked a comment about wording the reasoning behind adding the call site attribute Comment Actions lgtm, I think this is ready to land.
Comment Actions
I edited my comment a couple of times and I think I dropped one important bit. I'm not sure it's safe to rewrite an call_preallocated_setup to an alloca in the entry block, in general. There is no rule which prevents multiple calls to the same call_preallocated_setup in a loop, without deallocating the memory in between. Because of that, reusing the memory could lead to a miscompile. There wouldn't be any way to deallocate the result, but that isn't necessarily a problem. You could prove this doesn't happen in common cases, and clang wouldn't generate code like that. But LLVM optimizations could introduce it, I think, if there isn't a rule specifically preventing it.
Saying that the alignment of preallocated arguments is always 4 without any way to tweak it seems a little obnoxious, if we ever want to use the intrinsics for any other purpose. I guess it works, though.
Yes, you can put align on a return value. Probably more important would be putting align on the call arguments itself. Comment Actions I copied the blurb from byval about align to preallocated, since they should share the same codepath. Comment Actions I think if we model calls with preallocated bundles as modifying inaccessible state (i.e. the stack pointer), LLVM transforms won't do this. I'm imagining some kind of loop result code sinking transform that wants to sink a readonly function call out of a loop, because the result is only used after the last iteration. Comment Actions
I don't think that's enough in general. Well, maybe it's enough for the transforms we actually implement... LLVM currently has very few transforms that fold code together. But a simple example, suppose we had a transform that took void g(); void f() { g();g();g();g();g(); } and transformed it into something like void g(); void f() { for (int i =0; i < n; ++i) g(); }. Looks fine generally. If the loop body is a sequence containing calls to llvm.call.preallocated.setup()/llvm.call.preallocated.arg(), maybe not so fine. (I think this is only an issue if there is no call actually consuming the stack; if there were, the token would block the transform.) Comment Actions What about if we directly replace the llvm.call.preallocated.arg() with an alloca (as opposed to an alloca in the entry block)? Comment Actions
There can be more than one llvm.call.preallocated.arg referring to the same argument, so probably you'd want to insert the alloca at the point of the llvm.call.preallocated.setup. But yes, that should work. Comment Actions Update LangRef about replacing setup/arg with alloca/gep Comment Actions We could go down the route of doing something similar to inalloca where the llvm.call.preallocated.setup becomes an alloca of a structure containing all the arguments, and the llvm.call.preallocated.arg becomes a gep of the alloca. I've changed the LangRef to say that. I'm not sure if I'm overspecifying in the LangRef though, maybe that should be an implementation detail? Comment Actions
LangRef can't require that lowering be implemented some specific way; that would break the as-if rule. The important bit is that it can be implemented that way, and that might be the simplest way to explain the point. But maybe we don't actually need to include that sentence in LangRef at all; the fact that it's legal to lower that way should be implied from the other rules. And if it isn't implied, it's probably better to clarify the other rules. Comment Actions I think it is derivable from the other rules. I've removed those lines (and we can experiment later with where to put the alloca). Thanks for the reviews! Comment Actions I think in the end, the description of how this is lowered was left out, so this looks good and we can commit it as is. However, I'd like to ensure that it is valid to replace preallocated call sites with static allocas (allocas in the entry block). I don't think I understand this example. This looks like loop re-rolling to me, though, to give the transform a name. If g() uses a preallocated call site, the loop re-roller would have to execute the exact same sequence of preallocated call intrinsics as it would in the unrolled form. That seems like it's all fine. What about this transform rearranges the call site intrinsics to make them overlap, so that we would need two argument memory locations alive at the same time? Comment Actions
Yes, that's the idea. (LLVM has a reroll pass, but it only handles rerolling loops.) I guess I'll try to construct an actual C++ example. Suppose you have something like this: extern "C" int printf(const char*, ...);
extern "C" void abort(void) __attribute((noreturn));
struct A;
A* ptrs[10];
struct A {
int z;
__attribute((noinline))
A(int x) { z = 1; ptrs[z] = this; }
A(const A&);
};
__attribute((noinline))
void sum() { int sum = 0; for(A* p : ptrs) sum += p->z; printf("%d\n", sum); }
int g(int, A);
void f() { g(g(g(g(g((sum(), abort(), 6), A(0)), A(1)), A(2)), A(3)), A(4)); }On 32-bit Windows, the IR looks something like this: %1 = alloca inalloca <{ i32, %struct.A }>, align 4
%2 = getelementptr inbounds <{ i32, %struct.A }>, <{ i32, %struct.A }>* %1, i32 0, i32 1
%3 = call x86_thiscallcc %struct.A* @"??0A@@QAE@H@Z"(%struct.A* nonnull %2, i32 4)
%4 = alloca inalloca <{ i32, %struct.A }>, align 4
%5 = getelementptr inbounds <{ i32, %struct.A }>, <{ i32, %struct.A }>* %4, i32 0, i32 1
%6 = call x86_thiscallcc %struct.A* @"??0A@@QAE@H@Z"(%struct.A* nonnull %5, i32 3)
%7 = alloca inalloca <{ i32, %struct.A }>, align 4
%8 = getelementptr inbounds <{ i32, %struct.A }>, <{ i32, %struct.A }>* %7, i32 0, i32 1
%9 = call x86_thiscallcc %struct.A* @"??0A@@QAE@H@Z"(%struct.A* nonnull %8, i32 2)
%10 = alloca inalloca <{ i32, %struct.A }>, align 4
%11 = getelementptr inbounds <{ i32, %struct.A }>, <{ i32, %struct.A }>* %10, i32 0, i32 1
%12 = call x86_thiscallcc %struct.A* @"??0A@@QAE@H@Z"(%struct.A* nonnull %11, i32 1)
%13 = alloca inalloca <{ i32, %struct.A }>, align 4
%14 = getelementptr inbounds <{ i32, %struct.A }>, <{ i32, %struct.A }>* %13, i32 0, i32 1
%15 = call x86_thiscallcc %struct.A* @"??0A@@QAE@H@Z"(%struct.A* nonnull %14, i32 0)
call void @"?sum@@YAXXZ"()
call void @abort() #5
unreachableNotice the repeated alloca/gep/call pattern. In the new world, the "alloca" will be replaced with preallocated.setup/preallocated.arg. Now say your reroller decides to reroll that. What's the result of "sum()"? Comment Actions I see, the noreturn part of this is key here. I guess we solved this problem for Windows exception handling by threading the token through all the call instructions, so we can still color EH funclet regions in cases like this: void maythrow();
void f() {
try {
maythrow();
} catch(...) {
throw;
}
}Funclet bundles have been an ongoing maintenance burden that I would like to ease at some point, so I don't want to use that solution here. So far we've identified two kinds of transforms that should be semantics preserving according to the rules in LangRef, but present problems with our planned lowering. Neither transform exists in LLVM today:
Similar to the case of SEH try, I think we can really only solve this with a first class scope/region concept. In the meantime, I think we should move ahead with the implementation, and try to come up with a scope/region design that works for EH, call setup, SEH __try, and perhaps stack variable lifetime. I have a draft doc with a problem statement, but I don't have a good solution yet. Comment Actions
Okay, that makes sense. (I still don't really see why we'd want this for variable lifetimes. It isn't fundamentally problematic if variable lifetimes don't properly nest.) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
clang-format: please reformat the code
- enum NodeType { - /// DELETED_NODE - This is an illegal value that is used to catch - /// errors. This opcode is not a legal opcode for any node. - DELETED_NODE, - - /// EntryToken - This is the marker used to indicate the start of a region. - EntryToken, - - /// TokenFactor - This node takes multiple tokens as input and produces a - /// single token result. This is used to represent the fact that the operand1291 diff lines are omitted. See full diff.