lib/Target/X86/X86CallFrameOptimization.cpp

   1 //===----- X86CallFrameOptimization.cpp - Optimize x86 call sequences -----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  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
  16 //    register pressure.
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #include <algorithm>
  21
  22 #include "X86.h"
  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"
  36
  37 using namespace llvm;
  38
  39 #define DEBUG_TYPE "x86-cf-opt"
  40
  41 static cl::opt<bool>
  42     NoX86CFOpt("no-x86-call-frame-opt",
  43                cl::desc("Avoid optimizing x86 call frames for size"),
  44                cl::init(false), cl::Hidden);
  45
  46 namespace {
  47 class X86CallFrameOptimization : public MachineFunctionPass {
  48 public:
  49   X86CallFrameOptimization() : MachineFunctionPass(ID) {}
  50
  51   bool runOnMachineFunction(MachineFunction &MF) override;
  52
  53 private:
  54   // Information we know about a particular call site
  55   struct CallContext {
  56     CallContext()
  57         : FrameSetup(nullptr), Call(nullptr), SPCopy(nullptr), ExpectedDist(0),
  58           MovVector(4, nullptr), NoStackParams(false), UsePush(false){}
  59
  60     // Iterator referring to the frame setup instruction
  61     MachineBasicBlock::iterator FrameSetup;
  62
  63     // Actual call instruction
  64     MachineInstr *Call;
  65
  66     // A copy of the stack pointer
  67     MachineInstr *SPCopy;
  68
  69     // The total displacement of all passed parameters
  70     int64_t ExpectedDist;
  71
  72     // The sequence of movs used to pass the parameters
  73     SmallVector<MachineInstr *, 4> MovVector;
  74
  75     // True if this call site has no stack parameters
  76     bool NoStackParams;
  77
  78     // True of this callsite can use push instructions
  79     bool UsePush;
  80   };
  81
  82   typedef SmallVector<CallContext, 8> ContextVector;
  83
  84   bool isLegal(MachineFunction &MF);
  85
  86   bool isProfitable(MachineFunction &MF, ContextVector &CallSeqMap);
  87
  88   void collectCallInfo(MachineFunction &MF, MachineBasicBlock &MBB,
  89                        MachineBasicBlock::iterator I, CallContext &Context);
  90
  91   bool adjustCallSequence(MachineFunction &MF, const CallContext &Context);
  92
  93   MachineInstr *canFoldIntoRegPush(MachineBasicBlock::iterator FrameSetup,
  94                                    unsigned Reg);
  95
  96   enum InstClassification { Convert, Skip, Exit };
  97
  98   InstClassification classifyInstruction(MachineBasicBlock &MBB,
  99                                          MachineBasicBlock::iterator MI,
 100                                          const X86RegisterInfo &RegInfo,
 101                                          DenseSet<unsigned int> &UsedRegs);
 102
 103   const char *getPassName() const override { return "X86 Optimize Call Frame"; }
 104
 105   const TargetInstrInfo *TII;
 106   const TargetFrameLowering *TFL;
 107   const MachineRegisterInfo *MRI;
 108   static char ID;
 109 };
 110
 111 char X86CallFrameOptimization::ID = 0;
 112 }
 113
 114 FunctionPass *llvm::createX86CallFrameOptimization() {
 115   return new X86CallFrameOptimization();
 116 }
 117
 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())
 123     return false;
 124
 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>();
 131   if (STI.is64Bit())
 132     return false;
 133
 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())
 137     return false;
 138
 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)
 153           return false;
 154         InsideFrameSequence = true;
 155       } else if (MI.getOpcode() == FrameDestroyOpcode) {
 156         if (!InsideFrameSequence)
 157           return false;
 158         InsideFrameSequence = false;
 159       }
 160     }
 161
 162     if (InsideFrameSequence)
 163       return false;
 164   }
 165
 166   return true;
 167 }
 168
 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)
 178     return true;
 179
 180   // Don't do this when not optimizing for size.
 181   if (!MF.getFunction()->optForSize())
 182     return false;
 183
 184   unsigned StackAlign = TFL->getStackAlignment();
 185
 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
 190     // stack adjustment.
 191     if (CC.NoStackParams)
 192       continue;
 193
 194     if (!CC.UsePush) {
 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.
 201       Advantage -= 6;
 202     } else {
 203       // We can use pushes. First, account for the fixed costs.
 204       // We'll need a add after the call.
 205       Advantage -= 3;
 206       // If we have to realign the stack, we'll also need and sub before
 207       if (CC.ExpectedDist % StackAlign)
 208         Advantage -= 3;
 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;
 212     }
 213   }
 214
 215   return (Advantage >= 0);
 216 }
 217
 218 bool X86CallFrameOptimization::runOnMachineFunction(MachineFunction &MF) {
 219   TII = MF.getSubtarget().getInstrInfo();
 220   TFL = MF.getSubtarget().getFrameLowering();
 221   MRI = &MF.getRegInfo();
 222
 223   if (!isLegal(MF))
 224     return false;
 225
 226   unsigned FrameSetupOpcode = TII->getCallFrameSetupOpcode();
 227
 228   bool Changed = false;
 229
 230   ContextVector CallSeqVector;
 231
 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) {
 235         CallContext Context;
 236         collectCallInfo(MF, *BB, I, Context);
 237         CallSeqVector.push_back(Context);
 238       }
 239
 240   if (!isProfitable(MF, CallSeqVector))
 241     return false;
 242
 243   for (auto CC : CallSeqVector)
 244     if (CC.UsePush)
 245       Changed |= adjustCallSequence(MF, CC);
 246
 247   return Changed;
 248 }
 249
 250 X86CallFrameOptimization::InstClassification
 251 X86CallFrameOptimization::classifyInstruction(
 252     MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
 253     const X86RegisterInfo &RegInfo, DenseSet<unsigned int> &UsedRegs) {
 254   if (MI == MBB.end())
 255     return Exit;
 256
 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)
 260     return Convert;
 261
 262   // Not all calling conventions have only stack MOVs between the stack
 263   // adjust and the call.
 264
 265   // We want to tolerate other instructions, to cover more cases.
 266   // In particular:
 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
 274   // push.
 275   // (Reading from memory is allowed, even if referenced through a
 276   // frame index, since these will get adjusted properly in PEI)
 277
 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.
 286
 287   if (MI->isCall() || MI->mayStore())
 288     return Exit;
 289
 290   for (const MachineOperand &MO : MI->operands()) {
 291     if (!MO.isReg())
 292       continue;
 293     unsigned int Reg = MO.getReg();
 294     if (!RegInfo.isPhysicalRegister(Reg))
 295       continue;
 296     if (RegInfo.regsOverlap(Reg, RegInfo.getStackRegister()))
 297       return Exit;
 298     if (MO.isDef()) {
 299       for (unsigned int U : UsedRegs)
 300         if (RegInfo.regsOverlap(Reg, U))
 301           return Exit;
 302     }
 303   }
 304
 305   return Skip;
 306 }
 307
 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
 313   // transformation.
 314   const X86RegisterInfo &RegInfo = *static_cast<const X86RegisterInfo *>(
 315                                        MF.getSubtarget().getRegisterInfo());
 316   unsigned FrameDestroyOpcode = TII->getCallFrameDestroyOpcode();
 317
 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;
 322
 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;
 326
 327   // A zero adjustment means no stack parameters
 328   if (!MaxAdjust) {
 329     Context.NoStackParams = true;
 330     return;
 331   }
 332
 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)
 337     ++I;
 338
 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())
 344     return;
 345   Context.SPCopy = I++;
 346
 347   unsigned StackPtr = Context.SPCopy->getOperand(0).getReg();
 348
 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.
 353   if (MaxAdjust > 4)
 354     Context.MovVector.resize(MaxAdjust, nullptr);
 355
 356   InstClassification Classification;
 357   DenseSet<unsigned int> UsedRegs;
 358
 359   while ((Classification = classifyInstruction(MBB, I, RegInfo, UsedRegs)) !=
 360          Exit) {
 361     if (Classification == Skip) {
 362       ++I;
 363       continue;
 364     }
 365
 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
 374     // sequence.
 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())
 382       return;
 383
 384     int64_t StackDisp = I->getOperand(X86::AddrDisp).getImm();
 385     assert(StackDisp >= 0 &&
 386            "Negative stack displacement when passing parameters");
 387
 388     // We really don't want to consider the unaligned case.
 389     if (StackDisp % 4)
 390       return;
 391     StackDisp /= 4;
 392
 393     assert((size_t)StackDisp < Context.MovVector.size() &&
 394            "Function call has more parameters than the stack is adjusted for.");
 395
 396     // If the same stack slot is being filled twice, something's fishy.
 397     if (Context.MovVector[StackDisp] != nullptr)
 398       return;
 399     Context.MovVector[StackDisp] = I;
 400
 401     for (const MachineOperand &MO : I->uses()) {
 402       if (!MO.isReg())
 403         continue;
 404       unsigned int Reg = MO.getReg();
 405       if (RegInfo.isPhysicalRegister(Reg))
 406         UsedRegs.insert(Reg);
 407     }
 408
 409     ++I;
 410   }
 411
 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())
 415     return;
 416
 417   Context.Call = I;
 418   if ((++I)->getOpcode() != FrameDestroyOpcode)
 419     return;
 420
 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)
 425     if (*MMI == nullptr)
 426       break;
 427
 428   // If the call had no parameters, do nothing
 429   if (MMI == Context.MovVector.begin())
 430     return;
 431
 432   // We are either at the last parameter, or a gap.
 433   // Make sure it's not a gap
 434   for (; MMI != MME; ++MMI)
 435     if (*MMI != nullptr)
 436       return;
 437
 438   Context.UsePush = true;
 439   return;
 440 }
 441
 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);
 450
 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
 454   // replace uses.
 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();
 466         if (isInt<8>(Val))
 467           PushOpcode = X86::PUSH32i8;
 468       }
 469       BuildMI(MBB, Context.Call, DL, TII->get(PushOpcode)).addOperand(PushOp);
 470     } else {
 471       unsigned int Reg = PushOp.getReg();
 472
 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();
 477
 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))) {
 482         MachineInstr *Push =
 483             BuildMI(MBB, Context.Call, DL, TII->get(X86::PUSH32rmm));
 484
 485         unsigned NumOps = DefMov->getDesc().getNumOperands();
 486         for (unsigned i = NumOps - X86::AddrNumOperands; i != NumOps; ++i)
 487           Push->addOperand(DefMov->getOperand(i));
 488
 489         DefMov->eraseFromParent();
 490       } else {
 491         BuildMI(MBB, Context.Call, DL, TII->get(X86::PUSH32r))
 492             .addReg(Reg)
 493             .getInstr();
 494       }
 495     }
 496
 497     MBB.erase(MOV);
 498   }
 499
 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();
 504
 505   // Once we've done this, we need to make sure PEI doesn't assume a reserved
 506   // frame.
 507   X86MachineFunctionInfo *FuncInfo = MF.getInfo<X86MachineFunctionInfo>();
 508   FuncInfo->setHasPushSequences(true);
 509
 510   return true;
 511 }
 512
 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)
 522   // movl    %eax, (%esp)
 523   // call
 524   // Get rid of those with prejudice.
 525   if (!TargetRegisterInfo::isVirtualRegister(Reg))
 526     return nullptr;
 527
 528   // Make sure this is the only use of Reg.
 529   if (!MRI->hasOneNonDBGUse(Reg))
 530     return nullptr;
 531
 532   MachineBasicBlock::iterator DefMI = MRI->getVRegDef(Reg);
 533
 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())
 538     return nullptr;
 539
 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())
 544       return nullptr;
 545
 546   return DefMI;
 547 }