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   // Information we know about a particular call site
  54   struct CallContext {
  55     CallContext()
  56         : Call(nullptr), SPCopy(nullptr), ExpectedDist(0),
  57           MovVector(4, nullptr), NoStackParams(false), UsePush(false){};
  58
  59     // Actuall call instruction
  60     MachineInstr *Call;
  61
  62     // A copy of the stack pointer
  63     MachineInstr *SPCopy;
  64
  65     // The total displacement of all passed parameters
  66     int64_t ExpectedDist;
  67
  68     // The sequence of movs used to pass the parameters
  69     SmallVector<MachineInstr *, 4> MovVector;
  70
  71     // True if this call site has no stack parameters
  72     bool NoStackParams;
  73
  74     // True of this callsite can use push instructions
  75     bool UsePush;
  76   };
  77
  78   typedef DenseMap<MachineInstr *, CallContext> ContextMap;
  79
  80   bool isLegal(MachineFunction &MF);
  81
  82   bool isProfitable(MachineFunction &MF, ContextMap &CallSeqMap);
  83
  84   void collectCallInfo(MachineFunction &MF, MachineBasicBlock &MBB,
  85                        MachineBasicBlock::iterator I, CallContext &Context);
  86
  87   bool adjustCallSequence(MachineFunction &MF, MachineBasicBlock::iterator I,
  88                           const CallContext &Context);
  89
  90   MachineInstr *canFoldIntoRegPush(MachineBasicBlock::iterator FrameSetup,
  91                                    unsigned Reg);
  92
  93   const char *getPassName() const override { return "X86 Optimize Call Frame"; }
  94
  95   const TargetInstrInfo *TII;
  96   const TargetFrameLowering *TFL;
  97   const MachineRegisterInfo *MRI;
  98   static char ID;
  99 };
 100
 101 char X86CallFrameOptimization::ID = 0;
 102 }
 103
 104 FunctionPass *llvm::createX86CallFrameOptimization() {
 105   return new X86CallFrameOptimization();
 106 }
 107
 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())
 113     return false;
 114
 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.getTarget().getSubtarget<X86Subtarget>();
 121   if (STI.is64Bit())
 122     return false;
 123
 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)
 138           return false;
 139         InsideFrameSequence = true;
 140       } else if (MI.getOpcode() == FrameDestroyOpcode) {
 141         if (!InsideFrameSequence)
 142           return false;
 143         InsideFrameSequence = false;
 144       }
 145     }
 146
 147     if (InsideFrameSequence)
 148       return false;
 149   }
 150
 151   return true;
 152 }
 153
 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)
 163     return true;
 164
 165   // Don't do this when not optimizing for size.
 166   AttributeSet FnAttrs = MF.getFunction()->getAttributes();
 167   bool OptForSize =
 168       FnAttrs.hasAttribute(AttributeSet::FunctionIndex,
 169                            Attribute::OptimizeForSize) ||
 170       FnAttrs.hasAttribute(AttributeSet::FunctionIndex, Attribute::MinSize);
 171
 172   if (!OptForSize)
 173     return false;
 174
 175
 176   unsigned StackAlign = TFL->getStackAlignment();
 177
 178   int64_t Advantage = 0;
 179   for (auto CC : CallSeqMap) {
 180     // Call sites where no parameters are passed on the stack
 181     // do not affect the cost, since there needs to be no
 182     // stack adjustment.
 183     if (CC.second.NoStackParams)
 184       continue;
 185
 186     if (!CC.second.UsePush) {
 187       // If we don't use pushes for a particular call site,
 188       // we pay for not having a reserved call frame with an
 189       // additional sub/add esp pair. The cost is ~3 bytes per instruction,
 190       // depending on the size of the constant.
 191       // TODO: Callee-pop functions should have a smaller penalty, because
 192       // an add is needed even with a reserved call frame.
 193       Advantage -= 6;
 194     } else {
 195       // We can use pushes. First, account for the fixed costs.
 196       // We'll need a add after the call.
 197       Advantage -= 3;
 198       // If we have to realign the stack, we'll also need and sub before
 199       if (CC.second.ExpectedDist % StackAlign)
 200         Advantage -= 3;
 201       // Now, for each push, we save ~3 bytes. For small constants, we actually,
 202       // save more (up to 5 bytes), but 3 should be a good approximation.
 203       Advantage += (CC.second.ExpectedDist / 4) * 3;
 204     }
 205   }
 206
 207   return (Advantage >= 0);
 208 }
 209
 210
 211 bool X86CallFrameOptimization::runOnMachineFunction(MachineFunction &MF) {
 212   TII = MF.getSubtarget().getInstrInfo();
 213   TFL = MF.getSubtarget().getFrameLowering();
 214   MRI = &MF.getRegInfo();
 215
 216   if (!isLegal(MF))
 217     return false;
 218
 219   int FrameSetupOpcode = TII->getCallFrameSetupOpcode();
 220
 221   bool Changed = false;
 222
 223   ContextMap CallSeqMap;
 224
 225   for (MachineFunction::iterator BB = MF.begin(), E = MF.end(); BB != E; ++BB)
 226     for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I)
 227       if (I->getOpcode() == FrameSetupOpcode) {
 228         CallContext &Context = CallSeqMap[I];
 229         collectCallInfo(MF, *BB, I, Context);
 230       }
 231
 232   if (!isProfitable(MF, CallSeqMap))
 233     return false;
 234
 235   for (auto CC : CallSeqMap)
 236     if (CC.second.UsePush)
 237       Changed |= adjustCallSequence(MF, CC.first, CC.second);
 238
 239   return Changed;
 240 }
 241
 242 void X86CallFrameOptimization::collectCallInfo(MachineFunction &MF,
 243                                                MachineBasicBlock &MBB,
 244                                                MachineBasicBlock::iterator I,
 245                                                CallContext &Context) {
 246   // Check that this particular call sequence is amenable to the
 247   // transformation.
 248   const X86RegisterInfo &RegInfo = *static_cast<const X86RegisterInfo *>(
 249                                        MF.getSubtarget().getRegisterInfo());
 250   unsigned StackPtr = RegInfo.getStackRegister();
 251   int FrameDestroyOpcode = TII->getCallFrameDestroyOpcode();
 252
 253   // We expect to enter this at the beginning of a call sequence
 254   assert(I->getOpcode() == TII->getCallFrameSetupOpcode());
 255   MachineBasicBlock::iterator FrameSetup = I++;
 256
 257   // How much do we adjust the stack? This puts an upper bound on
 258   // the number of parameters actually passed on it.
 259   unsigned int MaxAdjust = FrameSetup->getOperand(0).getImm() / 4;
 260
 261   // A zero adjustment means no stack parameters
 262   if (!MaxAdjust) {
 263     Context.NoStackParams = true;
 264     return;
 265   }
 266
 267   // For globals in PIC mode, we can have some LEAs here.
 268   // Ignore them, they don't bother us.
 269   // TODO: Extend this to something that covers more cases.
 270   while (I->getOpcode() == X86::LEA32r)
 271     ++I;
 272
 273   // We expect a copy instruction here.
 274   // TODO: The copy instruction is a lowering artifact.
 275   //       We should also support a copy-less version, where the stack
 276   //       pointer is used directly.
 277   if (!I->isCopy() || !I->getOperand(0).isReg())
 278     return;
 279   Context.SPCopy = I++;
 280   StackPtr = Context.SPCopy->getOperand(0).getReg();
 281
 282   // Scan the call setup sequence for the pattern we're looking for.
 283   // We only handle a simple case - a sequence of MOV32mi or MOV32mr
 284   // instructions, that push a sequence of 32-bit values onto the stack, with
 285   // no gaps between them.
 286   if (MaxAdjust > 4)
 287     Context.MovVector.resize(MaxAdjust, nullptr);
 288
 289   do {
 290     int Opcode = I->getOpcode();
 291     if (Opcode != X86::MOV32mi && Opcode != X86::MOV32mr)
 292       break;
 293
 294     // We only want movs of the form:
 295     // movl imm/r32, k(%esp)
 296     // If we run into something else, bail.
 297     // Note that AddrBaseReg may, counter to its name, not be a register,
 298     // but rather a frame index.
 299     // TODO: Support the fi case. This should probably work now that we
 300     // have the infrastructure to track the stack pointer within a call
 301     // sequence.
 302     if (!I->getOperand(X86::AddrBaseReg).isReg() ||
 303         (I->getOperand(X86::AddrBaseReg).getReg() != StackPtr) ||
 304         !I->getOperand(X86::AddrScaleAmt).isImm() ||
 305         (I->getOperand(X86::AddrScaleAmt).getImm() != 1) ||
 306         (I->getOperand(X86::AddrIndexReg).getReg() != X86::NoRegister) ||
 307         (I->getOperand(X86::AddrSegmentReg).getReg() != X86::NoRegister) ||
 308         !I->getOperand(X86::AddrDisp).isImm())
 309       return;
 310
 311     int64_t StackDisp = I->getOperand(X86::AddrDisp).getImm();
 312     assert(StackDisp >= 0 &&
 313            "Negative stack displacement when passing parameters");
 314
 315     // We really don't want to consider the unaligned case.
 316     if (StackDisp % 4)
 317       return;
 318     StackDisp /= 4;
 319
 320     assert((size_t)StackDisp < Context.MovVector.size() &&
 321            "Function call has more parameters than the stack is adjusted for.");
 322
 323     // If the same stack slot is being filled twice, something's fishy.
 324     if (Context.MovVector[StackDisp] != nullptr)
 325       return;
 326     Context.MovVector[StackDisp] = I;
 327
 328     ++I;
 329   } while (I != MBB.end());
 330
 331   // We now expect the end of the sequence - a call and a stack adjust.
 332   if (I == MBB.end())
 333     return;
 334
 335   // For PCrel calls, we expect an additional COPY of the basereg.
 336   // If we find one, skip it.
 337   if (I->isCopy()) {
 338     if (I->getOperand(1).getReg() ==
 339         MF.getInfo<X86MachineFunctionInfo>()->getGlobalBaseReg())
 340       ++I;
 341     else
 342       return;
 343   }
 344
 345   if (!I->isCall())
 346     return;
 347
 348   Context.Call = I;
 349   if ((++I)->getOpcode() != FrameDestroyOpcode)
 350     return;
 351
 352   // Now, go through the vector, and see that we don't have any gaps,
 353   // but only a series of 32-bit MOVs.
 354   auto MMI = Context.MovVector.begin(), MME = Context.MovVector.end();
 355   for (; MMI != MME; ++MMI, Context.ExpectedDist += 4)
 356     if (*MMI == nullptr)
 357       break;
 358
 359   // If the call had no parameters, do nothing
 360   if (MMI == Context.MovVector.begin())
 361     return;
 362
 363   // We are either at the last parameter, or a gap.
 364   // Make sure it's not a gap
 365   for (; MMI != MME; ++MMI)
 366     if (*MMI != nullptr)
 367       return;
 368
 369   Context.UsePush = true;
 370   return;
 371 }
 372
 373 bool X86CallFrameOptimization::adjustCallSequence(MachineFunction &MF,
 374                                                   MachineBasicBlock::iterator I,
 375                                                   const CallContext &Context) {
 376   // Ok, we can in fact do the transformation for this call.
 377   // Do not remove the FrameSetup instruction, but adjust the parameters.
 378   // PEI will end up finalizing the handling of this.
 379   MachineBasicBlock::iterator FrameSetup = I;
 380   MachineBasicBlock &MBB = *(I->getParent());
 381   FrameSetup->getOperand(1).setImm(Context.ExpectedDist);
 382
 383   DebugLoc DL = I->getDebugLoc();
 384   // Now, iterate through the vector in reverse order, and replace the movs
 385   // with pushes. MOVmi/MOVmr doesn't have any defs, so no need to
 386   // replace uses.
 387   for (int Idx = (Context.ExpectedDist / 4) - 1; Idx >= 0; --Idx) {
 388     MachineBasicBlock::iterator MOV = *Context.MovVector[Idx];
 389     MachineOperand PushOp = MOV->getOperand(X86::AddrNumOperands);
 390     if (MOV->getOpcode() == X86::MOV32mi) {
 391       unsigned PushOpcode = X86::PUSHi32;
 392       // If the operand is a small (8-bit) immediate, we can use a
 393       // PUSH instruction with a shorter encoding.
 394       // Note that isImm() may fail even though this is a MOVmi, because
 395       // the operand can also be a symbol.
 396       if (PushOp.isImm()) {
 397         int64_t Val = PushOp.getImm();
 398         if (isInt<8>(Val))
 399           PushOpcode = X86::PUSH32i8;
 400       }
 401       BuildMI(MBB, Context.Call, DL, TII->get(PushOpcode)).addOperand(PushOp);
 402     } else {
 403       unsigned int Reg = PushOp.getReg();
 404
 405       // If PUSHrmm is not slow on this target, try to fold the source of the
 406       // push into the instruction.
 407       const X86Subtarget &ST = MF.getTarget().getSubtarget<X86Subtarget>();
 408       bool SlowPUSHrmm = ST.isAtom() || ST.isSLM();
 409
 410       // Check that this is legal to fold. Right now, we're extremely
 411       // conservative about that.
 412       MachineInstr *DefMov = nullptr;
 413       if (!SlowPUSHrmm && (DefMov = canFoldIntoRegPush(FrameSetup, Reg))) {
 414         MachineInstr *Push =
 415             BuildMI(MBB, Context.Call, DL, TII->get(X86::PUSH32rmm));
 416
 417         unsigned NumOps = DefMov->getDesc().getNumOperands();
 418         for (unsigned i = NumOps - X86::AddrNumOperands; i != NumOps; ++i)
 419           Push->addOperand(DefMov->getOperand(i));
 420
 421         DefMov->eraseFromParent();
 422       } else {
 423         BuildMI(MBB, Context.Call, DL, TII->get(X86::PUSH32r))
 424             .addReg(Reg)
 425             .getInstr();
 426       }
 427     }
 428
 429     MBB.erase(MOV);
 430   }
 431
 432   // The stack-pointer copy is no longer used in the call sequences.
 433   // There should not be any other users, but we can't commit to that, so:
 434   if (MRI->use_empty(Context.SPCopy->getOperand(0).getReg()))
 435     Context.SPCopy->eraseFromParent();
 436
 437   // Once we've done this, we need to make sure PEI doesn't assume a reserved
 438   // frame.
 439   X86MachineFunctionInfo *FuncInfo = MF.getInfo<X86MachineFunctionInfo>();
 440   FuncInfo->setHasPushSequences(true);
 441
 442   return true;
 443 }
 444
 445 MachineInstr *X86CallFrameOptimization::canFoldIntoRegPush(
 446     MachineBasicBlock::iterator FrameSetup, unsigned Reg) {
 447   // Do an extremely restricted form of load folding.
 448   // ISel will often create patterns like:
 449   // movl    4(%edi), %eax
 450   // movl    8(%edi), %ecx
 451   // movl    12(%edi), %edx
 452   // movl    %edx, 8(%esp)
 453   // movl    %ecx, 4(%esp)
 454   // movl    %eax, (%esp)
 455   // call
 456   // Get rid of those with prejudice.
 457   if (!TargetRegisterInfo::isVirtualRegister(Reg))
 458     return nullptr;
 459
 460   // Make sure this is the only use of Reg.
 461   if (!MRI->hasOneNonDBGUse(Reg))
 462     return nullptr;
 463
 464   MachineBasicBlock::iterator DefMI = MRI->getVRegDef(Reg);
 465
 466   // Make sure the def is a MOV from memory.
 467   // If the def is an another block, give up.
 468   if (DefMI->getOpcode() != X86::MOV32rm ||
 469       DefMI->getParent() != FrameSetup->getParent())
 470     return nullptr;
 471
 472   // Now, make sure everything else up until the ADJCALLSTACK is a sequence
 473   // of MOVs. To be less conservative would require duplicating a lot of the
 474   // logic from PeepholeOptimizer.
 475   // FIXME: A possibly better approach would be to teach the PeepholeOptimizer
 476   // to be smarter about folding into pushes.
 477   for (auto I = DefMI; I != FrameSetup; ++I)
 478     if (I->getOpcode() != X86::MOV32rm)
 479       return nullptr;
 480
 481   return DefMI;
 482 }