1 //===----- X86CallFrameOptimization.cpp - Optimize x86 call sequences -----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines a pass that optimizes call sequences on x86.
11 // Currently, it converts movs of function parameters onto the stack into
12 // pushes. This is beneficial for two main reasons:
13 // 1) The push instruction encoding is much smaller than an esp-relative mov
14 // 2) It is possible to push memory arguments directly. So, if the
15 // the transformation is preformed pre-reg-alloc, it can help relieve
18 //===----------------------------------------------------------------------===//
23 #include "X86InstrInfo.h"
24 #include "X86Subtarget.h"
25 #include "X86MachineFunctionInfo.h"
26 #include "llvm/ADT/Statistic.h"
27 #include "llvm/CodeGen/MachineFunctionPass.h"
28 #include "llvm/CodeGen/MachineInstrBuilder.h"
29 #include "llvm/CodeGen/MachineRegisterInfo.h"
30 #include "llvm/CodeGen/Passes.h"
31 #include "llvm/IR/Function.h"
32 #include "llvm/Support/Debug.h"
33 #include "llvm/Support/raw_ostream.h"
34 #include "llvm/Target/TargetInstrInfo.h"
38 #define DEBUG_TYPE "x86-cf-opt"
41 NoX86CFOpt("no-x86-call-frame-opt",
42 cl::desc("Avoid optimizing x86 call frames for size"),
43 cl::init(false), cl::Hidden);
46 class X86CallFrameOptimization : public MachineFunctionPass {
48 X86CallFrameOptimization() : MachineFunctionPass(ID) {}
50 bool runOnMachineFunction(MachineFunction &MF) override;
53 // Information we know about a particular call site
56 : Call(nullptr), SPCopy(nullptr), ExpectedDist(0),
57 MovVector(4, nullptr), NoStackParams(false), UsePush(false){};
59 // Actuall call instruction
62 // A copy of the stack pointer
65 // The total displacement of all passed parameters
68 // The sequence of movs used to pass the parameters
69 SmallVector<MachineInstr *, 4> MovVector;
71 // True if this call site has no stack parameters
74 // True of this callsite can use push instructions
78 typedef DenseMap<MachineInstr *, CallContext> ContextMap;
80 bool isLegal(MachineFunction &MF);
82 bool isProfitable(MachineFunction &MF, ContextMap &CallSeqMap);
84 void collectCallInfo(MachineFunction &MF, MachineBasicBlock &MBB,
85 MachineBasicBlock::iterator I, CallContext &Context);
87 bool adjustCallSequence(MachineFunction &MF, MachineBasicBlock::iterator I,
88 const CallContext &Context);
90 MachineInstr *canFoldIntoRegPush(MachineBasicBlock::iterator FrameSetup,
93 const char *getPassName() const override { return "X86 Optimize Call Frame"; }
95 const TargetInstrInfo *TII;
96 const TargetFrameLowering *TFL;
97 const MachineRegisterInfo *MRI;
101 char X86CallFrameOptimization::ID = 0;
104 FunctionPass *llvm::createX86CallFrameOptimization() {
105 return new X86CallFrameOptimization();
108 // This checks whether the transformation is legal.
109 // Also returns false in cases where it's potentially legal, but
110 // we don't even want to try.
111 bool X86CallFrameOptimization::isLegal(MachineFunction &MF) {
112 if (NoX86CFOpt.getValue())
115 // We currently only support call sequences where *all* parameters.
116 // are passed on the stack.
117 // No point in running this in 64-bit mode, since some arguments are
118 // passed in-register in all common calling conventions, so the pattern
119 // we're looking for will never match.
120 const X86Subtarget &STI = MF.getSubtarget<X86Subtarget>();
124 // You would expect straight-line code between call-frame setup and
125 // call-frame destroy. You would be wrong. There are circumstances (e.g.
126 // CMOV_GR8 expansion of a select that feeds a function call!) where we can
127 // end up with the setup and the destroy in different basic blocks.
128 // This is bad, and breaks SP adjustment.
129 // So, check that all of the frames in the function are closed inside
130 // the same block, and, for good measure, that there are no nested frames.
131 int FrameSetupOpcode = TII->getCallFrameSetupOpcode();
132 int FrameDestroyOpcode = TII->getCallFrameDestroyOpcode();
133 for (MachineBasicBlock &BB : MF) {
134 bool InsideFrameSequence = false;
135 for (MachineInstr &MI : BB) {
136 if (MI.getOpcode() == FrameSetupOpcode) {
137 if (InsideFrameSequence)
139 InsideFrameSequence = true;
140 } else if (MI.getOpcode() == FrameDestroyOpcode) {
141 if (!InsideFrameSequence)
143 InsideFrameSequence = false;
147 if (InsideFrameSequence)
154 // Check whether this trasnformation is profitable for a particular
155 // function - in terms of code size.
156 bool X86CallFrameOptimization::isProfitable(MachineFunction &MF,
157 ContextMap &CallSeqMap) {
158 // This transformation is always a win when we do not expect to have
159 // a reserved call frame. Under other circumstances, it may be either
160 // a win or a loss, and requires a heuristic.
161 bool CannotReserveFrame = MF.getFrameInfo()->hasVarSizedObjects();
162 if (CannotReserveFrame)
165 // Don't do this when not optimizing for size.
167 MF.getFunction()->hasFnAttribute(Attribute::OptimizeForSize) ||
168 MF.getFunction()->hasFnAttribute(Attribute::MinSize);
174 unsigned StackAlign = TFL->getStackAlignment();
176 int64_t Advantage = 0;
177 for (auto CC : CallSeqMap) {
178 // Call sites where no parameters are passed on the stack
179 // do not affect the cost, since there needs to be no
181 if (CC.second.NoStackParams)
184 if (!CC.second.UsePush) {
185 // If we don't use pushes for a particular call site,
186 // we pay for not having a reserved call frame with an
187 // additional sub/add esp pair. The cost is ~3 bytes per instruction,
188 // depending on the size of the constant.
189 // TODO: Callee-pop functions should have a smaller penalty, because
190 // an add is needed even with a reserved call frame.
193 // We can use pushes. First, account for the fixed costs.
194 // We'll need a add after the call.
196 // If we have to realign the stack, we'll also need and sub before
197 if (CC.second.ExpectedDist % StackAlign)
199 // Now, for each push, we save ~3 bytes. For small constants, we actually,
200 // save more (up to 5 bytes), but 3 should be a good approximation.
201 Advantage += (CC.second.ExpectedDist / 4) * 3;
205 return (Advantage >= 0);
209 bool X86CallFrameOptimization::runOnMachineFunction(MachineFunction &MF) {
210 TII = MF.getSubtarget().getInstrInfo();
211 TFL = MF.getSubtarget().getFrameLowering();
212 MRI = &MF.getRegInfo();
217 int FrameSetupOpcode = TII->getCallFrameSetupOpcode();
219 bool Changed = false;
221 ContextMap CallSeqMap;
223 for (MachineFunction::iterator BB = MF.begin(), E = MF.end(); BB != E; ++BB)
224 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I)
225 if (I->getOpcode() == FrameSetupOpcode) {
226 CallContext &Context = CallSeqMap[I];
227 collectCallInfo(MF, *BB, I, Context);
230 if (!isProfitable(MF, CallSeqMap))
233 for (auto CC : CallSeqMap)
234 if (CC.second.UsePush)
235 Changed |= adjustCallSequence(MF, CC.first, CC.second);
240 void X86CallFrameOptimization::collectCallInfo(MachineFunction &MF,
241 MachineBasicBlock &MBB,
242 MachineBasicBlock::iterator I,
243 CallContext &Context) {
244 // Check that this particular call sequence is amenable to the
246 const X86RegisterInfo &RegInfo = *static_cast<const X86RegisterInfo *>(
247 MF.getSubtarget().getRegisterInfo());
248 unsigned StackPtr = RegInfo.getStackRegister();
249 int FrameDestroyOpcode = TII->getCallFrameDestroyOpcode();
251 // We expect to enter this at the beginning of a call sequence
252 assert(I->getOpcode() == TII->getCallFrameSetupOpcode());
253 MachineBasicBlock::iterator FrameSetup = I++;
255 // How much do we adjust the stack? This puts an upper bound on
256 // the number of parameters actually passed on it.
257 unsigned int MaxAdjust = FrameSetup->getOperand(0).getImm() / 4;
259 // A zero adjustment means no stack parameters
261 Context.NoStackParams = true;
265 // For globals in PIC mode, we can have some LEAs here.
266 // Ignore them, they don't bother us.
267 // TODO: Extend this to something that covers more cases.
268 while (I->getOpcode() == X86::LEA32r)
271 // We expect a copy instruction here.
272 // TODO: The copy instruction is a lowering artifact.
273 // We should also support a copy-less version, where the stack
274 // pointer is used directly.
275 if (!I->isCopy() || !I->getOperand(0).isReg())
277 Context.SPCopy = I++;
278 StackPtr = Context.SPCopy->getOperand(0).getReg();
280 // Scan the call setup sequence for the pattern we're looking for.
281 // We only handle a simple case - a sequence of MOV32mi or MOV32mr
282 // instructions, that push a sequence of 32-bit values onto the stack, with
283 // no gaps between them.
285 Context.MovVector.resize(MaxAdjust, nullptr);
288 int Opcode = I->getOpcode();
289 if (Opcode != X86::MOV32mi && Opcode != X86::MOV32mr)
292 // We only want movs of the form:
293 // movl imm/r32, k(%esp)
294 // If we run into something else, bail.
295 // Note that AddrBaseReg may, counter to its name, not be a register,
296 // but rather a frame index.
297 // TODO: Support the fi case. This should probably work now that we
298 // have the infrastructure to track the stack pointer within a call
300 if (!I->getOperand(X86::AddrBaseReg).isReg() ||
301 (I->getOperand(X86::AddrBaseReg).getReg() != StackPtr) ||
302 !I->getOperand(X86::AddrScaleAmt).isImm() ||
303 (I->getOperand(X86::AddrScaleAmt).getImm() != 1) ||
304 (I->getOperand(X86::AddrIndexReg).getReg() != X86::NoRegister) ||
305 (I->getOperand(X86::AddrSegmentReg).getReg() != X86::NoRegister) ||
306 !I->getOperand(X86::AddrDisp).isImm())
309 int64_t StackDisp = I->getOperand(X86::AddrDisp).getImm();
310 assert(StackDisp >= 0 &&
311 "Negative stack displacement when passing parameters");
313 // We really don't want to consider the unaligned case.
318 assert((size_t)StackDisp < Context.MovVector.size() &&
319 "Function call has more parameters than the stack is adjusted for.");
321 // If the same stack slot is being filled twice, something's fishy.
322 if (Context.MovVector[StackDisp] != nullptr)
324 Context.MovVector[StackDisp] = I;
327 } while (I != MBB.end());
329 // We now expect the end of the sequence - a call and a stack adjust.
333 // For PCrel calls, we expect an additional COPY of the basereg.
334 // If we find one, skip it.
336 if (I->getOperand(1).getReg() ==
337 MF.getInfo<X86MachineFunctionInfo>()->getGlobalBaseReg())
347 if ((++I)->getOpcode() != FrameDestroyOpcode)
350 // Now, go through the vector, and see that we don't have any gaps,
351 // but only a series of 32-bit MOVs.
352 auto MMI = Context.MovVector.begin(), MME = Context.MovVector.end();
353 for (; MMI != MME; ++MMI, Context.ExpectedDist += 4)
357 // If the call had no parameters, do nothing
358 if (MMI == Context.MovVector.begin())
361 // We are either at the last parameter, or a gap.
362 // Make sure it's not a gap
363 for (; MMI != MME; ++MMI)
367 Context.UsePush = true;
371 bool X86CallFrameOptimization::adjustCallSequence(MachineFunction &MF,
372 MachineBasicBlock::iterator I,
373 const CallContext &Context) {
374 // Ok, we can in fact do the transformation for this call.
375 // Do not remove the FrameSetup instruction, but adjust the parameters.
376 // PEI will end up finalizing the handling of this.
377 MachineBasicBlock::iterator FrameSetup = I;
378 MachineBasicBlock &MBB = *(I->getParent());
379 FrameSetup->getOperand(1).setImm(Context.ExpectedDist);
381 DebugLoc DL = I->getDebugLoc();
382 // Now, iterate through the vector in reverse order, and replace the movs
383 // with pushes. MOVmi/MOVmr doesn't have any defs, so no need to
385 for (int Idx = (Context.ExpectedDist / 4) - 1; Idx >= 0; --Idx) {
386 MachineBasicBlock::iterator MOV = *Context.MovVector[Idx];
387 MachineOperand PushOp = MOV->getOperand(X86::AddrNumOperands);
388 if (MOV->getOpcode() == X86::MOV32mi) {
389 unsigned PushOpcode = X86::PUSHi32;
390 // If the operand is a small (8-bit) immediate, we can use a
391 // PUSH instruction with a shorter encoding.
392 // Note that isImm() may fail even though this is a MOVmi, because
393 // the operand can also be a symbol.
394 if (PushOp.isImm()) {
395 int64_t Val = PushOp.getImm();
397 PushOpcode = X86::PUSH32i8;
399 BuildMI(MBB, Context.Call, DL, TII->get(PushOpcode)).addOperand(PushOp);
401 unsigned int Reg = PushOp.getReg();
403 // If PUSHrmm is not slow on this target, try to fold the source of the
404 // push into the instruction.
405 const X86Subtarget &ST = MF.getSubtarget<X86Subtarget>();
406 bool SlowPUSHrmm = ST.isAtom() || ST.isSLM();
408 // Check that this is legal to fold. Right now, we're extremely
409 // conservative about that.
410 MachineInstr *DefMov = nullptr;
411 if (!SlowPUSHrmm && (DefMov = canFoldIntoRegPush(FrameSetup, Reg))) {
413 BuildMI(MBB, Context.Call, DL, TII->get(X86::PUSH32rmm));
415 unsigned NumOps = DefMov->getDesc().getNumOperands();
416 for (unsigned i = NumOps - X86::AddrNumOperands; i != NumOps; ++i)
417 Push->addOperand(DefMov->getOperand(i));
419 DefMov->eraseFromParent();
421 BuildMI(MBB, Context.Call, DL, TII->get(X86::PUSH32r))
430 // The stack-pointer copy is no longer used in the call sequences.
431 // There should not be any other users, but we can't commit to that, so:
432 if (MRI->use_empty(Context.SPCopy->getOperand(0).getReg()))
433 Context.SPCopy->eraseFromParent();
435 // Once we've done this, we need to make sure PEI doesn't assume a reserved
437 X86MachineFunctionInfo *FuncInfo = MF.getInfo<X86MachineFunctionInfo>();
438 FuncInfo->setHasPushSequences(true);
443 MachineInstr *X86CallFrameOptimization::canFoldIntoRegPush(
444 MachineBasicBlock::iterator FrameSetup, unsigned Reg) {
445 // Do an extremely restricted form of load folding.
446 // ISel will often create patterns like:
447 // movl 4(%edi), %eax
448 // movl 8(%edi), %ecx
449 // movl 12(%edi), %edx
450 // movl %edx, 8(%esp)
451 // movl %ecx, 4(%esp)
454 // Get rid of those with prejudice.
455 if (!TargetRegisterInfo::isVirtualRegister(Reg))
458 // Make sure this is the only use of Reg.
459 if (!MRI->hasOneNonDBGUse(Reg))
462 MachineBasicBlock::iterator DefMI = MRI->getVRegDef(Reg);
464 // Make sure the def is a MOV from memory.
465 // If the def is an another block, give up.
466 if (DefMI->getOpcode() != X86::MOV32rm ||
467 DefMI->getParent() != FrameSetup->getParent())
470 // Now, make sure everything else up until the ADJCALLSTACK is a sequence
471 // of MOVs. To be less conservative would require duplicating a lot of the
472 // logic from PeepholeOptimizer.
473 // FIXME: A possibly better approach would be to teach the PeepholeOptimizer
474 // to be smarter about folding into pushes.
475 for (auto I = DefMI; I != FrameSetup; ++I)
476 if (I->getOpcode() != X86::MOV32rm)