lib/Target/X86/X86CallFrameOptimization.cpp

   1 //===----- X86CallFrameOptimization.cpp - Optimize x86 call sequences -----===//\r
   2 //\r
   3 //                     The LLVM Compiler Infrastructure\r
   4 //\r
   5 // This file is distributed under the University of Illinois Open Source\r
   6 // License. See LICENSE.TXT for details.\r
   7 //\r
   8 //===----------------------------------------------------------------------===//\r
   9 //\r
  10 // This file defines a pass that optimizes call sequences on x86.\r
  11 // Currently, it converts movs of function parameters onto the stack into \r
  12 // pushes. This is beneficial for two main reasons:\r
  13 // 1) The push instruction encoding is much smaller than an esp-relative mov\r
  14 // 2) It is possible to push memory arguments directly. So, if the\r
  15 //    the transformation is preformed pre-reg-alloc, it can help relieve\r
  16 //    register pressure.\r
  17 //\r
  18 //===----------------------------------------------------------------------===//\r
  19 \r
  20 #include <algorithm>\r
  21 \r
  22 #include "X86.h"\r
  23 #include "X86InstrInfo.h"\r
  24 #include "X86Subtarget.h"\r
  25 #include "X86MachineFunctionInfo.h"\r
  26 #include "llvm/ADT/Statistic.h"\r
  27 #include "llvm/CodeGen/MachineFunctionPass.h"\r
  28 #include "llvm/CodeGen/MachineInstrBuilder.h"\r
  29 #include "llvm/CodeGen/MachineRegisterInfo.h"\r
  30 #include "llvm/CodeGen/Passes.h"\r
  31 #include "llvm/IR/Function.h"\r
  32 #include "llvm/Support/Debug.h"\r
  33 #include "llvm/Support/raw_ostream.h"\r
  34 #include "llvm/Target/TargetInstrInfo.h"\r
  35 \r
  36 using namespace llvm;\r
  37 \r
  38 #define DEBUG_TYPE "x86-cf-opt"\r
  39 \r
  40 cl::opt<bool> NoX86CFOpt("no-x86-call-frame-opt",\r
  41               cl::desc("Avoid optimizing x86 call frames for size"),\r
  42               cl::init(false), cl::Hidden);\r
  43 \r
  44 namespace {\r
  45 class X86CallFrameOptimization : public MachineFunctionPass {\r
  46 public:\r
  47   X86CallFrameOptimization() : MachineFunctionPass(ID) {}\r
  48 \r
  49   bool runOnMachineFunction(MachineFunction &MF) override;\r
  50 \r
  51 private:\r
  52   bool shouldPerformTransformation(MachineFunction &MF);\r
  53 \r
  54   bool adjustCallSequence(MachineFunction &MF, MachineBasicBlock &MBB,\r
  55                           MachineBasicBlock::iterator I);\r
  56 \r
  57   MachineInstr *canFoldIntoRegPush(MachineBasicBlock::iterator FrameSetup,\r
  58                                    unsigned Reg);\r
  59 \r
  60   const char *getPassName() const override {\r
  61     return "X86 Optimize Call Frame";\r
  62   }\r
  63 \r
  64   const TargetInstrInfo *TII;\r
  65   const TargetFrameLowering *TFL;\r
  66   const MachineRegisterInfo *MRI;\r
  67   static char ID;\r
  68 };\r
  69 \r
  70 char X86CallFrameOptimization::ID = 0;\r
  71 }\r
  72 \r
  73 FunctionPass *llvm::createX86CallFrameOptimization() {\r
  74   return new X86CallFrameOptimization();\r
  75 }\r
  76 \r
  77 // This checks whether the transformation is legal and profitable\r
  78 bool X86CallFrameOptimization::shouldPerformTransformation(MachineFunction &MF) {\r
  79   if (NoX86CFOpt.getValue())\r
  80     return false;\r
  81 \r
  82   // We currently only support call sequences where *all* parameters.\r
  83   // are passed on the stack.\r
  84   // No point in running this in 64-bit mode, since some arguments are\r
  85   // passed in-register in all common calling conventions, so the pattern\r
  86   // we're looking for will never match.\r
  87   const X86Subtarget &STI = MF.getTarget().getSubtarget<X86Subtarget>();\r
  88   if (STI.is64Bit())\r
  89     return false;\r
  90 \r
  91   // You would expect straight-line code between call-frame setup and\r
  92   // call-frame destroy. You would be wrong. There are circumstances (e.g.\r
  93   // CMOV_GR8 expansion of a select that feeds a function call!) where we can\r
  94   // end up with the setup and the destroy in different basic blocks.\r
  95   // This is bad, and breaks SP adjustment.\r
  96   // So, check that all of the frames in the function are closed inside\r
  97   // the same block, and, for good measure, that there are no nested frames.\r
  98   int FrameSetupOpcode = TII->getCallFrameSetupOpcode();\r
  99   int FrameDestroyOpcode = TII->getCallFrameDestroyOpcode();\r
 100   for (MachineBasicBlock &BB : MF) {\r
 101     bool InsideFrameSequence = false;\r
 102     for (MachineInstr &MI : BB) {\r
 103       if (MI.getOpcode() == FrameSetupOpcode) {\r
 104         if (InsideFrameSequence)\r
 105           return false;\r
 106         InsideFrameSequence = true;\r
 107       }\r
 108       else if (MI.getOpcode() == FrameDestroyOpcode) {\r
 109         if (!InsideFrameSequence)\r
 110           return false;\r
 111         InsideFrameSequence = false;\r
 112       }\r
 113     }\r
 114 \r
 115     if (InsideFrameSequence)\r
 116       return false;\r
 117   }\r
 118 \r
 119   // Now that we know the transformation is legal, check if it is\r
 120   // profitable.\r
 121   // TODO: Add a heuristic that actually looks at the function,\r
 122   //       and enable this for more cases.\r
 123 \r
 124   // This transformation is always a win when we expected to have\r
 125   // a reserved call frame. Under other circumstances, it may be either \r
 126   // a win or a loss, and requires a heuristic.\r
 127   // For now, enable it only for the relatively clear win cases.\r
 128   bool CannotReserveFrame = MF.getFrameInfo()->hasVarSizedObjects();\r
 129   if (CannotReserveFrame)\r
 130     return true;\r
 131 \r
 132   // For now, don't even try to evaluate the profitability when\r
 133   // not optimizing for size.\r
 134   AttributeSet FnAttrs = MF.getFunction()->getAttributes();\r
 135   bool OptForSize =\r
 136     FnAttrs.hasAttribute(AttributeSet::FunctionIndex,\r
 137     Attribute::OptimizeForSize) ||\r
 138     FnAttrs.hasAttribute(AttributeSet::FunctionIndex, Attribute::MinSize);\r
 139 \r
 140   if (!OptForSize)\r
 141     return false;\r
 142 \r
 143   // Stack re-alignment can make this unprofitable even in terms of size.\r
 144   // As mentioned above, a better heuristic is needed. For now, don't do this\r
 145   // when the required alignment is above 8. (4 would be the safe choice, but\r
 146   // some experimentation showed 8 is generally good).\r
 147   if (TFL->getStackAlignment() > 8)\r
 148     return false;\r
 149 \r
 150   return true;\r
 151 }\r
 152 \r
 153 bool X86CallFrameOptimization::runOnMachineFunction(MachineFunction &MF) {\r
 154   TII = MF.getSubtarget().getInstrInfo();\r
 155   TFL = MF.getSubtarget().getFrameLowering();\r
 156   MRI = &MF.getRegInfo();\r
 157 \r
 158   if (!shouldPerformTransformation(MF))\r
 159     return false;\r
 160 \r
 161   int FrameSetupOpcode = TII->getCallFrameSetupOpcode();\r
 162 \r
 163   bool Changed = false;\r
 164 \r
 165   for (MachineFunction::iterator BB = MF.begin(), E = MF.end(); BB != E; ++BB)\r
 166     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I)\r
 167       if (I->getOpcode() == FrameSetupOpcode)\r
 168         Changed |= adjustCallSequence(MF, *BB, I);\r
 169 \r
 170   return Changed;\r
 171 }\r
 172 \r
 173 bool X86CallFrameOptimization::adjustCallSequence(MachineFunction &MF,\r
 174                                                 MachineBasicBlock &MBB,\r
 175                                                 MachineBasicBlock::iterator I) {\r
 176 \r
 177   // Check that this particular call sequence is amenable to the\r
 178   // transformation.\r
 179   const X86RegisterInfo &RegInfo = *static_cast<const X86RegisterInfo *>(\r
 180                                        MF.getSubtarget().getRegisterInfo());\r
 181   unsigned StackPtr = RegInfo.getStackRegister();\r
 182   int FrameDestroyOpcode = TII->getCallFrameDestroyOpcode();\r
 183 \r
 184   // We expect to enter this at the beginning of a call sequence\r
 185   assert(I->getOpcode() == TII->getCallFrameSetupOpcode());\r
 186   MachineBasicBlock::iterator FrameSetup = I++;\r
 187 \r
 188   \r
 189   // For globals in PIC mode, we can have some LEAs here.\r
 190   // Ignore them, they don't bother us.\r
 191   // TODO: Extend this to something that covers more cases.\r
 192   while (I->getOpcode() == X86::LEA32r)\r
 193     ++I;\r
 194   \r
 195   // We expect a copy instruction here.\r
 196   // TODO: The copy instruction is a lowering artifact.\r
 197   //       We should also support a copy-less version, where the stack\r
 198   //       pointer is used directly.\r
 199   if (!I->isCopy() || !I->getOperand(0).isReg())\r
 200     return false;\r
 201   MachineBasicBlock::iterator SPCopy = I++;\r
 202   StackPtr = SPCopy->getOperand(0).getReg();\r
 203 \r
 204   // Scan the call setup sequence for the pattern we're looking for.\r
 205   // We only handle a simple case - a sequence of MOV32mi or MOV32mr\r
 206   // instructions, that push a sequence of 32-bit values onto the stack, with\r
 207   // no gaps between them.\r
 208   SmallVector<MachineInstr*, 4> MovVector(4, nullptr);\r
 209   unsigned int MaxAdjust = FrameSetup->getOperand(0).getImm() / 4;\r
 210   if (MaxAdjust > 4)\r
 211     MovVector.resize(MaxAdjust, nullptr);\r
 212 \r
 213   do {\r
 214     int Opcode = I->getOpcode();\r
 215     if (Opcode != X86::MOV32mi && Opcode != X86::MOV32mr)\r
 216       break;\r
 217 \r
 218     // We only want movs of the form:\r
 219     // movl imm/r32, k(%esp)\r
 220     // If we run into something else, bail.\r
 221     // Note that AddrBaseReg may, counter to its name, not be a register,\r
 222     // but rather a frame index.\r
 223     // TODO: Support the fi case. This should probably work now that we\r
 224     // have the infrastructure to track the stack pointer within a call\r
 225     // sequence.\r
 226     if (!I->getOperand(X86::AddrBaseReg).isReg() ||\r
 227         (I->getOperand(X86::AddrBaseReg).getReg() != StackPtr) ||\r
 228         !I->getOperand(X86::AddrScaleAmt).isImm() ||\r
 229         (I->getOperand(X86::AddrScaleAmt).getImm() != 1) ||\r
 230         (I->getOperand(X86::AddrIndexReg).getReg() != X86::NoRegister) ||\r
 231         (I->getOperand(X86::AddrSegmentReg).getReg() != X86::NoRegister) ||\r
 232         !I->getOperand(X86::AddrDisp).isImm())\r
 233       return false;\r
 234 \r
 235     int64_t StackDisp = I->getOperand(X86::AddrDisp).getImm();\r
 236     assert(StackDisp >= 0 && "Negative stack displacement when passing parameters");\r
 237 \r
 238     // We really don't want to consider the unaligned case.\r
 239     if (StackDisp % 4)\r
 240       return false;\r
 241     StackDisp /= 4;\r
 242 \r
 243     assert((size_t)StackDisp < MovVector.size() &&\r
 244       "Function call has more parameters than the stack is adjusted for.");\r
 245 \r
 246     // If the same stack slot is being filled twice, something's fishy.\r
 247     if (MovVector[StackDisp] != nullptr)\r
 248       return false;\r
 249     MovVector[StackDisp] = I;\r
 250 \r
 251     ++I;\r
 252   } while (I != MBB.end());\r
 253 \r
 254   // We now expect the end of the sequence - a call and a stack adjust.\r
 255   if (I == MBB.end())\r
 256     return false;\r
 257 \r
 258   // For PCrel calls, we expect an additional COPY of the basereg.\r
 259   // If we find one, skip it.\r
 260   if (I->isCopy()) {\r
 261     if (I->getOperand(1).getReg() ==\r
 262       MF.getInfo<X86MachineFunctionInfo>()->getGlobalBaseReg())\r
 263       ++I;\r
 264     else\r
 265       return false;\r
 266   }\r
 267 \r
 268   if (!I->isCall())\r
 269     return false;\r
 270   MachineBasicBlock::iterator Call = I;\r
 271   if ((++I)->getOpcode() != FrameDestroyOpcode)\r
 272     return false;\r
 273 \r
 274   // Now, go through the vector, and see that we don't have any gaps,\r
 275   // but only a series of 32-bit MOVs.\r
 276   \r
 277   int64_t ExpectedDist = 0;\r
 278   auto MMI = MovVector.begin(), MME = MovVector.end();\r
 279   for (; MMI != MME; ++MMI, ExpectedDist += 4)\r
 280     if (*MMI == nullptr)\r
 281       break;\r
 282   \r
 283   // If the call had no parameters, do nothing\r
 284   if (!ExpectedDist)\r
 285     return false;\r
 286 \r
 287   // We are either at the last parameter, or a gap. \r
 288   // Make sure it's not a gap\r
 289   for (; MMI != MME; ++MMI)\r
 290     if (*MMI != nullptr)\r
 291       return false;\r
 292 \r
 293   // Ok, we can in fact do the transformation for this call.\r
 294   // Do not remove the FrameSetup instruction, but adjust the parameters.\r
 295   // PEI will end up finalizing the handling of this.\r
 296   FrameSetup->getOperand(1).setImm(ExpectedDist);\r
 297 \r
 298   DebugLoc DL = I->getDebugLoc();\r
 299   // Now, iterate through the vector in reverse order, and replace the movs\r
 300   // with pushes. MOVmi/MOVmr doesn't have any defs, so no need to \r
 301   // replace uses.\r
 302   for (int Idx = (ExpectedDist / 4) - 1; Idx >= 0; --Idx) {\r
 303     MachineBasicBlock::iterator MOV = *MovVector[Idx];\r
 304     MachineOperand PushOp = MOV->getOperand(X86::AddrNumOperands);\r
 305     if (MOV->getOpcode() == X86::MOV32mi) {\r
 306       unsigned PushOpcode = X86::PUSHi32;\r
 307       // If the operand is a small (8-bit) immediate, we can use a\r
 308       // PUSH instruction with a shorter encoding.\r
 309       // Note that isImm() may fail even though this is a MOVmi, because\r
 310       // the operand can also be a symbol.\r
 311       if (PushOp.isImm()) {\r
 312         int64_t Val = PushOp.getImm();\r
 313         if (isInt<8>(Val))\r
 314           PushOpcode = X86::PUSH32i8;\r
 315       }\r
 316       BuildMI(MBB, Call, DL, TII->get(PushOpcode)).addOperand(PushOp);\r
 317     } else {\r
 318       unsigned int Reg = PushOp.getReg();\r
 319 \r
 320       // If PUSHrmm is not slow on this target, try to fold the source of the\r
 321       // push into the instruction.\r
 322       const X86Subtarget &ST = MF.getTarget().getSubtarget<X86Subtarget>();\r
 323       bool SlowPUSHrmm = ST.isAtom() || ST.isSLM();\r
 324 \r
 325       // Check that this is legal to fold. Right now, we're extremely\r
 326       // conservative about that.\r
 327       MachineInstr *DefMov = nullptr;\r
 328       if (!SlowPUSHrmm && (DefMov = canFoldIntoRegPush(FrameSetup, Reg))) {\r
 329         MachineInstr *Push = BuildMI(MBB, Call, DL, TII->get(X86::PUSH32rmm));\r
 330 \r
 331         unsigned NumOps = DefMov->getDesc().getNumOperands();\r
 332         for (unsigned i = NumOps - X86::AddrNumOperands; i != NumOps; ++i)\r
 333           Push->addOperand(DefMov->getOperand(i));\r
 334 \r
 335         DefMov->eraseFromParent();\r
 336       } else {\r
 337         BuildMI(MBB, Call, DL, TII->get(X86::PUSH32r)).addReg(Reg).getInstr();\r
 338       }\r
 339     }\r
 340 \r
 341     MBB.erase(MOV);\r
 342   }\r
 343 \r
 344   // The stack-pointer copy is no longer used in the call sequences.\r
 345   // There should not be any other users, but we can't commit to that, so:\r
 346   if (MRI->use_empty(SPCopy->getOperand(0).getReg()))\r
 347     SPCopy->eraseFromParent();\r
 348 \r
 349   // Once we've done this, we need to make sure PEI doesn't assume a reserved\r
 350   // frame.\r
 351   X86MachineFunctionInfo *FuncInfo = MF.getInfo<X86MachineFunctionInfo>();\r
 352   FuncInfo->setHasPushSequences(true);\r
 353 \r
 354   return true;\r
 355 }\r
 356 \r
 357 MachineInstr *X86CallFrameOptimization::canFoldIntoRegPush(\r
 358     MachineBasicBlock::iterator FrameSetup, unsigned Reg) {\r
 359   // Do an extremely restricted form of load folding.\r
 360   // ISel will often create patterns like:\r
 361   // movl    4(%edi), %eax\r
 362   // movl    8(%edi), %ecx\r
 363   // movl    12(%edi), %edx\r
 364   // movl    %edx, 8(%esp)\r
 365   // movl    %ecx, 4(%esp)\r
 366   // movl    %eax, (%esp)\r
 367   // call\r
 368   // Get rid of those with prejudice.\r
 369   if (!TargetRegisterInfo::isVirtualRegister(Reg))\r
 370     return nullptr;\r
 371 \r
 372   // Make sure this is the only use of Reg.\r
 373   if (!MRI->hasOneNonDBGUse(Reg))\r
 374     return nullptr;\r
 375 \r
 376   MachineBasicBlock::iterator DefMI = MRI->getVRegDef(Reg);\r
 377 \r
 378   // Make sure the def is a MOV from memory.\r
 379   // If the def is an another block, give up.\r
 380   if (DefMI->getOpcode() != X86::MOV32rm ||\r
 381       DefMI->getParent() != FrameSetup->getParent())\r
 382     return nullptr;\r
 383 \r
 384   // Be careful with movs that load from a stack slot, since it may get\r
 385   // resolved incorrectly.\r
 386   // TODO: Again, we already have the infrastructure, so this should work.\r
 387   if (!DefMI->getOperand(1).isReg())\r
 388     return nullptr;\r
 389 \r
 390   // Now, make sure everything else up until the ADJCALLSTACK is a sequence\r
 391   // of MOVs. To be less conservative would require duplicating a lot of the\r
 392   // logic from PeepholeOptimizer.\r
 393   // FIXME: A possibly better approach would be to teach the PeepholeOptimizer\r
 394   // to be smarter about folding into pushes. \r
 395   for (auto I = DefMI; I != FrameSetup; ++I)\r
 396     if (I->getOpcode() != X86::MOV32rm)\r
 397       return nullptr;\r
 398 \r
 399   return DefMI;\r
 400 }\r