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