Differential D20263
X86: Avoid using _chkstk when lowering WIN_ALLOCA instructions Authored by hans on May 13 2016, 4:40 PM.
Details This patch moves the expansion of WIN_ALLOCA pseudo-instructions into a separate pass that walks the CFG and lowers the instructions based on a conservative estimate of the offset between the stack pointer and the lowest accessed stack address. The goal is to reduce binary size and run-time costs by removing calls to _chkstk.
Diff Detail
Event Timeline
Comment Actions Hi Hans, I made a few detailed comments, but I have higher level concerns about the approach. This new pass will eliminate most of the _chkstk calls, which is great. But we'll still be leaving some performance on the table. We'd really like calls that take inalloca arguments to be optimized in all the same ways as other calls. In particular, we'd like to be able to reserve the outgoing argument block & do the store-to-push optimization for outgoing arguments. I think the "inalloca" name is unfortunate, because these "WIN_ALLOCA" stack allocations have more in common with ADJCALLSTACKDOWN than they do with alloca. For one thing, they always allocate a fixed amount of space. Additionally, there is an implicit requirement that the stack pointer value immediately following the WIN_ALLOCA matches the stack pointer value at the time of the call to the inalloca function. This requirement is not currently enforced correctly in some cases. You'll find that this program doesn't work with clang on Win32, because the stack space for the _alloca call is allocated *after* the stack space for the "WIN_ALLOCA": #include <stdio.h>
#include <malloc.h>
struct X
{
int x;
X() {x = 42;}
X(const X&v) { x = v.x; }
};
X x;
void f2(X v, void*p) { printf("v.x = %d (should be 42)\n", v.x); }
void f(int n)
{
f2(x, _alloca(n));
}
int main()
{
f(1000);
return 0;
}Fixing that bug may be orthogonal to how we model & implement inalloca calls in the back end. But that illustrates why I think a more accurate modeling would be to move the ADJCALLSTACKDOWN instruction that precedes the inalloca call (i.e. the ADJCALLSTACKDOWN instruction that is hacked to always use an allocation size of 0) to the current location of the WIN_ALLOCA, use an accurate allocation size rather than 0, and get rid of the WIN_ALLOCA altogether. That would have the effect of introducing nested ADJCALLSTACKDOWN/ADJCALLSTACKUP structures, which I'm sure is going to cause some implementation problems. But I think it will allow us to more naturally handle & optimize these calls during FrameLowering. It's kind of mess, but I think it is just a natural consequence of Microsoft's choice to construct inalloca arguments in the outgoing argument block rather than in an arbitrary location on the stack and passing a pointer to that location as is done on Linux. I'll try to put together a prototype. That might make it easier to see what I have in mind. Meanwhile, I have no objection to using this new pass as a shorter term performance fix. :) Thanks, BTW, any thoughts on how to fix the above bug? This is another thing that I think ought to be handled by clang.
Comment Actions Thanks for the great comments everyone! David, I agree this only addresses a small part of the problem and leaves a lot of performance on the table. The way I think about it is as an incremental improvement, easier than tackling the full inalloca problem all at once, and also helpful for dynamic allocas in general. Having the WIN_ALLOCA pseudos expanded late might also help getting better code for these calls eventually, as it should remove the need for some of the pattern matching I tried in D20003 (unless we manage to fix them with some higher-level approach).
Comment Actions Any more comments, or are you all OK with this going in?
Comment Actions We did notice this, it's https://llvm.org/bugs/show_bug.cgi?id=26776. We can leverage the fact that argument evaluation order is currently unsequenced, and evaluate the argument containing the alloca call first. However, if C++17 defines argument evaluation order, then it will become impossible to satisfy the copy elision requirement and the evaluation order requirement in this old and busted 32-bit ABI. =/ I think we can transform WIN_ALLOCA to ADJCALLSTACK today in certain limited cases, and if we can, it would definitely be a win. I doubt we can tolerate nested ADJCALLSTACK frames, though, and inalloca typically happens precisely when there is a nested call sequence. Obviously, stack frame reservation conflicts with nested call stack adjustments, but we should already be protected from that by the hasVarSizedObjects flag, which is set earlier in FunctionLoweringInfo. Do you intend to pursue store-to-push conversion for calls where an argument is still address-taken by the time we reach codegen? Consider this kind of code: struct S { S(const S &); ~S(); int s; };
S makeS(); // cannot inline away
void takeS(int, S, int);
void passS() { takeS(1, makeS(), 3); }MSVC can make this into "push 1, sub 4, call makeS, push 3", but by the time we reach LLVM codegen, we have no ability to reason about what memory makeS writes. I'm happy if LLVM can turn this into "sub, call makeS, store 1, store 3, call takeS, add". This is what we used to get before push conversion, and I think we can achieve it with our current approach. If we want to do full push conversion, then we need to revisit the IR. Comment Actions I just have a couple other minor suggestions. Otherwise, LGTM.
Comment Actions LGTM
Comment Actions Thanks for the pointer to https://llvm.org/bugs/show_bug.cgi?id=26776, Reid.
I'm sure you are right. I'd still like to give it a try and see how badly things break.
We can still do stack frame reservation with nested call stack adjustments. It's just that the reserved call frame is only available to the top-level calls. Nested calls would have to do their own stack adjusts. I'm sure making that distinction would create some implementation challenges, and it isn't likely to be high impact, but it seems theoretically possible. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||