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/MachineModuleInfo.h"
30 #include "llvm/CodeGen/MachineRegisterInfo.h"
31 #include "llvm/CodeGen/Passes.h"
32 #include "llvm/IR/Function.h"
33 #include "llvm/Support/Debug.h"
34 #include "llvm/Support/raw_ostream.h"
35 #include "llvm/Target/TargetInstrInfo.h"
39 #define DEBUG_TYPE "x86-cf-opt"
42 NoX86CFOpt("no-x86-call-frame-opt",
43 cl::desc("Avoid optimizing x86 call frames for size"),
44 cl::init(false), cl::Hidden);
47 class X86CallFrameOptimization : public MachineFunctionPass {
49 X86CallFrameOptimization() : MachineFunctionPass(ID) {}
51 bool runOnMachineFunction(MachineFunction &MF) override;
54 // Information we know about a particular call site
57 : FrameSetup(nullptr), Call(nullptr), SPCopy(nullptr), ExpectedDist(0),
58 MovVector(4, nullptr), NoStackParams(false), UsePush(false){}
60 // Iterator referring to the frame setup instruction
61 MachineBasicBlock::iterator FrameSetup;
63 // Actual call instruction
66 // A copy of the stack pointer
69 // The total displacement of all passed parameters
72 // The sequence of movs used to pass the parameters
73 SmallVector<MachineInstr *, 4> MovVector;
75 // True if this call site has no stack parameters
78 // True of this callsite can use push instructions
82 typedef SmallVector<CallContext, 8> ContextVector;
84 bool isLegal(MachineFunction &MF);
86 bool isProfitable(MachineFunction &MF, ContextVector &CallSeqMap);
88 void collectCallInfo(MachineFunction &MF, MachineBasicBlock &MBB,
89 MachineBasicBlock::iterator I, CallContext &Context);
91 bool adjustCallSequence(MachineFunction &MF, const CallContext &Context);
93 MachineInstr *canFoldIntoRegPush(MachineBasicBlock::iterator FrameSetup,
96 enum InstClassification { Convert, Skip, Exit };
98 InstClassification classifyInstruction(MachineBasicBlock &MBB,
99 MachineBasicBlock::iterator MI,
100 const X86RegisterInfo &RegInfo,
101 DenseSet<unsigned int> &UsedRegs);
103 const char *getPassName() const override { return "X86 Optimize Call Frame"; }
105 const TargetInstrInfo *TII;
106 const TargetFrameLowering *TFL;
107 const MachineRegisterInfo *MRI;
111 char X86CallFrameOptimization::ID = 0;
114 FunctionPass *llvm::createX86CallFrameOptimization() {
115 return new X86CallFrameOptimization();
118 // This checks whether the transformation is legal.
119 // Also returns false in cases where it's potentially legal, but
120 // we don't even want to try.
121 bool X86CallFrameOptimization::isLegal(MachineFunction &MF) {
122 if (NoX86CFOpt.getValue())
125 // We currently only support call sequences where *all* parameters.
126 // are passed on the stack.
127 // No point in running this in 64-bit mode, since some arguments are
128 // passed in-register in all common calling conventions, so the pattern
129 // we're looking for will never match.
130 const X86Subtarget &STI = MF.getSubtarget<X86Subtarget>();
134 // We can't encode multiple DW_CFA_GNU_args_size in the compact
135 // unwind encoding that Darwin uses.
136 if (STI.isTargetDarwin() && !MF.getMMI().getLandingPads().empty())
139 // You would expect straight-line code between call-frame setup and
140 // call-frame destroy. You would be wrong. There are circumstances (e.g.
141 // CMOV_GR8 expansion of a select that feeds a function call!) where we can
142 // end up with the setup and the destroy in different basic blocks.
143 // This is bad, and breaks SP adjustment.
144 // So, check that all of the frames in the function are closed inside
145 // the same block, and, for good measure, that there are no nested frames.
146 unsigned FrameSetupOpcode = TII->getCallFrameSetupOpcode();
147 unsigned FrameDestroyOpcode = TII->getCallFrameDestroyOpcode();
148 for (MachineBasicBlock &BB : MF) {
149 bool InsideFrameSequence = false;
150 for (MachineInstr &MI : BB) {
151 if (MI.getOpcode() == FrameSetupOpcode) {
152 if (InsideFrameSequence)
154 InsideFrameSequence = true;
155 } else if (MI.getOpcode() == FrameDestroyOpcode) {
156 if (!InsideFrameSequence)
158 InsideFrameSequence = false;
162 if (InsideFrameSequence)
169 // Check whether this trasnformation is profitable for a particular
170 // function - in terms of code size.
171 bool X86CallFrameOptimization::isProfitable(MachineFunction &MF,
172 ContextVector &CallSeqVector) {
173 // This transformation is always a win when we do not expect to have
174 // a reserved call frame. Under other circumstances, it may be either
175 // a win or a loss, and requires a heuristic.
176 bool CannotReserveFrame = MF.getFrameInfo()->hasVarSizedObjects();
177 if (CannotReserveFrame)
180 // Don't do this when not optimizing for size.
181 if (!MF.getFunction()->optForSize())
184 unsigned StackAlign = TFL->getStackAlignment();
186 int64_t Advantage = 0;
187 for (auto CC : CallSeqVector) {
188 // Call sites where no parameters are passed on the stack
189 // do not affect the cost, since there needs to be no
191 if (CC.NoStackParams)
195 // If we don't use pushes for a particular call site,
196 // we pay for not having a reserved call frame with an
197 // additional sub/add esp pair. The cost is ~3 bytes per instruction,
198 // depending on the size of the constant.
199 // TODO: Callee-pop functions should have a smaller penalty, because
200 // an add is needed even with a reserved call frame.
203 // We can use pushes. First, account for the fixed costs.
204 // We'll need a add after the call.
206 // If we have to realign the stack, we'll also need and sub before
207 if (CC.ExpectedDist % StackAlign)
209 // Now, for each push, we save ~3 bytes. For small constants, we actually,
210 // save more (up to 5 bytes), but 3 should be a good approximation.
211 Advantage += (CC.ExpectedDist / 4) * 3;
215 return (Advantage >= 0);
218 bool X86CallFrameOptimization::runOnMachineFunction(MachineFunction &MF) {
219 TII = MF.getSubtarget().getInstrInfo();
220 TFL = MF.getSubtarget().getFrameLowering();
221 MRI = &MF.getRegInfo();
226 unsigned FrameSetupOpcode = TII->getCallFrameSetupOpcode();
228 bool Changed = false;
230 ContextVector CallSeqVector;
232 for (MachineFunction::iterator BB = MF.begin(), E = MF.end(); BB != E; ++BB)
233 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I)
234 if (I->getOpcode() == FrameSetupOpcode) {
236 collectCallInfo(MF, *BB, I, Context);
237 CallSeqVector.push_back(Context);
240 if (!isProfitable(MF, CallSeqVector))
243 for (auto CC : CallSeqVector)
245 Changed |= adjustCallSequence(MF, CC);
250 X86CallFrameOptimization::InstClassification
251 X86CallFrameOptimization::classifyInstruction(
252 MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
253 const X86RegisterInfo &RegInfo, DenseSet<unsigned int> &UsedRegs) {
257 // The instructions we actually care about are movs onto the stack
258 int Opcode = MI->getOpcode();
259 if (Opcode == X86::MOV32mi || Opcode == X86::MOV32mr)
262 // Not all calling conventions have only stack MOVs between the stack
263 // adjust and the call.
265 // We want to tolerate other instructions, to cover more cases.
267 // a) PCrel calls, where we expect an additional COPY of the basereg.
268 // b) Passing frame-index addresses.
269 // c) Calling conventions that have inreg parameters. These generate
270 // both copies and movs into registers.
271 // To avoid creating lots of special cases, allow any instruction
272 // that does not write into memory, does not def or use the stack
273 // pointer, and does not def any register that was used by a preceding
275 // (Reading from memory is allowed, even if referenced through a
276 // frame index, since these will get adjusted properly in PEI)
278 // The reason for the last condition is that the pushes can't replace
279 // the movs in place, because the order must be reversed.
280 // So if we have a MOV32mr that uses EDX, then an instruction that defs
281 // EDX, and then the call, after the transformation the push will use
282 // the modified version of EDX, and not the original one.
283 // Since we are still in SSA form at this point, we only need to
284 // make sure we don't clobber any *physical* registers that were
285 // used by an earlier mov that will become a push.
287 if (MI->isCall() || MI->mayStore())
290 for (const MachineOperand &MO : MI->operands()) {
293 unsigned int Reg = MO.getReg();
294 if (!RegInfo.isPhysicalRegister(Reg))
296 if (RegInfo.regsOverlap(Reg, RegInfo.getStackRegister()))
299 for (unsigned int U : UsedRegs)
300 if (RegInfo.regsOverlap(Reg, U))
308 void X86CallFrameOptimization::collectCallInfo(MachineFunction &MF,
309 MachineBasicBlock &MBB,
310 MachineBasicBlock::iterator I,
311 CallContext &Context) {
312 // Check that this particular call sequence is amenable to the
314 const X86RegisterInfo &RegInfo = *static_cast<const X86RegisterInfo *>(
315 MF.getSubtarget().getRegisterInfo());
316 unsigned FrameDestroyOpcode = TII->getCallFrameDestroyOpcode();
318 // We expect to enter this at the beginning of a call sequence
319 assert(I->getOpcode() == TII->getCallFrameSetupOpcode());
320 MachineBasicBlock::iterator FrameSetup = I++;
321 Context.FrameSetup = FrameSetup;
323 // How much do we adjust the stack? This puts an upper bound on
324 // the number of parameters actually passed on it.
325 unsigned int MaxAdjust = FrameSetup->getOperand(0).getImm() / 4;
327 // A zero adjustment means no stack parameters
329 Context.NoStackParams = true;
333 // For globals in PIC mode, we can have some LEAs here.
334 // Ignore them, they don't bother us.
335 // TODO: Extend this to something that covers more cases.
336 while (I->getOpcode() == X86::LEA32r)
339 // We expect a copy instruction here.
340 // TODO: The copy instruction is a lowering artifact.
341 // We should also support a copy-less version, where the stack
342 // pointer is used directly.
343 if (!I->isCopy() || !I->getOperand(0).isReg())
345 Context.SPCopy = I++;
347 unsigned StackPtr = Context.SPCopy->getOperand(0).getReg();
349 // Scan the call setup sequence for the pattern we're looking for.
350 // We only handle a simple case - a sequence of MOV32mi or MOV32mr
351 // instructions, that push a sequence of 32-bit values onto the stack, with
352 // no gaps between them.
354 Context.MovVector.resize(MaxAdjust, nullptr);
356 InstClassification Classification;
357 DenseSet<unsigned int> UsedRegs;
359 while ((Classification = classifyInstruction(MBB, I, RegInfo, UsedRegs)) !=
361 if (Classification == Skip) {
366 // We know the instruction is a MOV32mi/MOV32mr.
367 // We only want movs of the form:
368 // movl imm/r32, k(%esp)
369 // If we run into something else, bail.
370 // Note that AddrBaseReg may, counter to its name, not be a register,
371 // but rather a frame index.
372 // TODO: Support the fi case. This should probably work now that we
373 // have the infrastructure to track the stack pointer within a call
375 if (!I->getOperand(X86::AddrBaseReg).isReg() ||
376 (I->getOperand(X86::AddrBaseReg).getReg() != StackPtr) ||
377 !I->getOperand(X86::AddrScaleAmt).isImm() ||
378 (I->getOperand(X86::AddrScaleAmt).getImm() != 1) ||
379 (I->getOperand(X86::AddrIndexReg).getReg() != X86::NoRegister) ||
380 (I->getOperand(X86::AddrSegmentReg).getReg() != X86::NoRegister) ||
381 !I->getOperand(X86::AddrDisp).isImm())
384 int64_t StackDisp = I->getOperand(X86::AddrDisp).getImm();
385 assert(StackDisp >= 0 &&
386 "Negative stack displacement when passing parameters");
388 // We really don't want to consider the unaligned case.
393 assert((size_t)StackDisp < Context.MovVector.size() &&
394 "Function call has more parameters than the stack is adjusted for.");
396 // If the same stack slot is being filled twice, something's fishy.
397 if (Context.MovVector[StackDisp] != nullptr)
399 Context.MovVector[StackDisp] = I;
401 for (const MachineOperand &MO : I->uses()) {
404 unsigned int Reg = MO.getReg();
405 if (RegInfo.isPhysicalRegister(Reg))
406 UsedRegs.insert(Reg);
412 // We now expect the end of the sequence. If we stopped early,
413 // or reached the end of the block without finding a call, bail.
414 if (I == MBB.end() || !I->isCall())
418 if ((++I)->getOpcode() != FrameDestroyOpcode)
421 // Now, go through the vector, and see that we don't have any gaps,
422 // but only a series of 32-bit MOVs.
423 auto MMI = Context.MovVector.begin(), MME = Context.MovVector.end();
424 for (; MMI != MME; ++MMI, Context.ExpectedDist += 4)
428 // If the call had no parameters, do nothing
429 if (MMI == Context.MovVector.begin())
432 // We are either at the last parameter, or a gap.
433 // Make sure it's not a gap
434 for (; MMI != MME; ++MMI)
438 Context.UsePush = true;
442 bool X86CallFrameOptimization::adjustCallSequence(MachineFunction &MF,
443 const CallContext &Context) {
444 // Ok, we can in fact do the transformation for this call.
445 // Do not remove the FrameSetup instruction, but adjust the parameters.
446 // PEI will end up finalizing the handling of this.
447 MachineBasicBlock::iterator FrameSetup = Context.FrameSetup;
448 MachineBasicBlock &MBB = *(FrameSetup->getParent());
449 FrameSetup->getOperand(1).setImm(Context.ExpectedDist);
451 DebugLoc DL = FrameSetup->getDebugLoc();
452 // Now, iterate through the vector in reverse order, and replace the movs
453 // with pushes. MOVmi/MOVmr doesn't have any defs, so no need to
455 for (int Idx = (Context.ExpectedDist / 4) - 1; Idx >= 0; --Idx) {
456 MachineBasicBlock::iterator MOV = *Context.MovVector[Idx];
457 MachineOperand PushOp = MOV->getOperand(X86::AddrNumOperands);
458 if (MOV->getOpcode() == X86::MOV32mi) {
459 unsigned PushOpcode = X86::PUSHi32;
460 // If the operand is a small (8-bit) immediate, we can use a
461 // PUSH instruction with a shorter encoding.
462 // Note that isImm() may fail even though this is a MOVmi, because
463 // the operand can also be a symbol.
464 if (PushOp.isImm()) {
465 int64_t Val = PushOp.getImm();
467 PushOpcode = X86::PUSH32i8;
469 BuildMI(MBB, Context.Call, DL, TII->get(PushOpcode)).addOperand(PushOp);
471 unsigned int Reg = PushOp.getReg();
473 // If PUSHrmm is not slow on this target, try to fold the source of the
474 // push into the instruction.
475 const X86Subtarget &ST = MF.getSubtarget<X86Subtarget>();
476 bool SlowPUSHrmm = ST.isAtom() || ST.isSLM();
478 // Check that this is legal to fold. Right now, we're extremely
479 // conservative about that.
480 MachineInstr *DefMov = nullptr;
481 if (!SlowPUSHrmm && (DefMov = canFoldIntoRegPush(FrameSetup, Reg))) {
483 BuildMI(MBB, Context.Call, DL, TII->get(X86::PUSH32rmm));
485 unsigned NumOps = DefMov->getDesc().getNumOperands();
486 for (unsigned i = NumOps - X86::AddrNumOperands; i != NumOps; ++i)
487 Push->addOperand(DefMov->getOperand(i));
489 DefMov->eraseFromParent();
491 BuildMI(MBB, Context.Call, DL, TII->get(X86::PUSH32r))
500 // The stack-pointer copy is no longer used in the call sequences.
501 // There should not be any other users, but we can't commit to that, so:
502 if (MRI->use_empty(Context.SPCopy->getOperand(0).getReg()))
503 Context.SPCopy->eraseFromParent();
505 // Once we've done this, we need to make sure PEI doesn't assume a reserved
507 X86MachineFunctionInfo *FuncInfo = MF.getInfo<X86MachineFunctionInfo>();
508 FuncInfo->setHasPushSequences(true);
513 MachineInstr *X86CallFrameOptimization::canFoldIntoRegPush(
514 MachineBasicBlock::iterator FrameSetup, unsigned Reg) {
515 // Do an extremely restricted form of load folding.
516 // ISel will often create patterns like:
517 // movl 4(%edi), %eax
518 // movl 8(%edi), %ecx
519 // movl 12(%edi), %edx
520 // movl %edx, 8(%esp)
521 // movl %ecx, 4(%esp)
524 // Get rid of those with prejudice.
525 if (!TargetRegisterInfo::isVirtualRegister(Reg))
528 // Make sure this is the only use of Reg.
529 if (!MRI->hasOneNonDBGUse(Reg))
532 MachineBasicBlock::iterator DefMI = MRI->getVRegDef(Reg);
534 // Make sure the def is a MOV from memory.
535 // If the def is an another block, give up.
536 if (DefMI->getOpcode() != X86::MOV32rm ||
537 DefMI->getParent() != FrameSetup->getParent())
540 // Make sure we don't have any instructions between DefMI and the
541 // push that make folding the load illegal.
542 for (auto I = DefMI; I != FrameSetup; ++I)
543 if (I->isLoadFoldBarrier())