lib/Target/X86/X86PadShortFunction.cpp

   1 //===-------- X86PadShortFunction.cpp - pad short functions -----------===//
   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 the pass which will pad short functions to prevent
  11 // a stall if a function returns before the return address is ready. This
  12 // is needed for some Intel Atom processors.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include <map>
  17 #include <algorithm>
  18
  19 #define DEBUG_TYPE "x86-pad-short-functions"
  20 #include "X86.h"
  21 #include "X86InstrInfo.h"
  22 #include "llvm/ADT/Statistic.h"
  23 #include "llvm/CodeGen/MachineFunctionPass.h"
  24 #include "llvm/CodeGen/MachineInstrBuilder.h"
  25 #include "llvm/CodeGen/MachineRegisterInfo.h"
  26 #include "llvm/CodeGen/Passes.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/raw_ostream.h"
  29 #include "llvm/Target/TargetInstrInfo.h"
  30 using namespace llvm;
  31
  32 STATISTIC(NumBBsPadded, "Number of basic blocks padded");
  33
  34 namespace {
  35   struct PadShortFunc : public MachineFunctionPass {
  36     static char ID;
  37     PadShortFunc() : MachineFunctionPass(ID)
  38                    , Threshold(4)
  39     {}
  40
  41     virtual bool runOnMachineFunction(MachineFunction &MF);
  42
  43     virtual const char *getPassName() const
  44     {
  45       return "X86 Atom pad short functions";
  46     }
  47
  48   private:
  49     bool addPadding(MachineFunction &MF,
  50                     MachineBasicBlock &MBB,
  51                     MachineBasicBlock::iterator &MBBI,
  52                     unsigned int NOOPsToAdd);
  53
  54     void findReturn(MachineFunction &MF,
  55                     MachineBasicBlock &MBB,
  56                     unsigned int Cycles);
  57
  58     bool cyclesUntilReturn(MachineFunction &MF,
  59                         MachineBasicBlock &MBB,
  60                         unsigned int &Cycles,
  61                         MachineBasicBlock::iterator *Location = 0);
  62
  63     const unsigned int Threshold;
  64     std::map<int, unsigned int> ReturnBBs;
  65   };
  66
  67   char PadShortFunc::ID = 0;
  68 }
  69
  70 FunctionPass *llvm::createX86PadShortFunctions() {
  71   return new PadShortFunc();
  72 }
  73
  74 /// runOnMachineFunction - Loop over all of the basic blocks, inserting
  75 /// NOOP instructions before early exits.
  76 bool PadShortFunc::runOnMachineFunction(MachineFunction &MF) {
  77   // Process all basic blocks.
  78   ReturnBBs.clear();
  79
  80   // Search through basic blocks and mark the ones that have early returns
  81   findReturn(MF, *MF.begin(), 0);
  82
  83   int BBNum;
  84   MachineBasicBlock::iterator ReturnLoc;
  85   MachineBasicBlock *MBB;
  86
  87   unsigned int Cycles = 0;
  88   unsigned int BBCycles;
  89
  90   // Pad the identified basic blocks with NOOPs
  91   for (std::map<int, unsigned int>::iterator I = ReturnBBs.begin();
  92        I != ReturnBBs.end(); ++I) {
  93     BBNum = I->first;
  94     Cycles = I->second;
  95
  96     if (Cycles < Threshold) {
  97       MBB = MF.getBlockNumbered(BBNum);
  98       if (!cyclesUntilReturn(MF, *MBB, BBCycles, &ReturnLoc))
  99         continue;
 100
 101       addPadding(MF, *MBB, ReturnLoc, Threshold - Cycles);
 102       NumBBsPadded++;
 103     }
 104   }
 105
 106   return false;
 107 }
 108
 109 /// findReturn - Starting at MBB, follow control flow and add all
 110 /// basic blocks that contain a return to ReturnBBs.
 111 void PadShortFunc::findReturn(MachineFunction &MF,
 112                               MachineBasicBlock &MBB,
 113                               unsigned int Cycles)
 114 {
 115   // If this BB has a return, note how many cycles it takes to get there.
 116   bool hasReturn = cyclesUntilReturn(MF, MBB, Cycles);
 117   if (Cycles >= Threshold)
 118     return;
 119
 120   if (hasReturn) {
 121     int BBNum = MBB.getNumber();
 122     ReturnBBs[BBNum] = std::max(ReturnBBs[BBNum], Cycles);
 123
 124     return;
 125   }
 126
 127   // Follow branches in BB and look for returns
 128   for (MachineBasicBlock::succ_iterator I = MBB.succ_begin();
 129        I != MBB.succ_end(); ++I) {
 130     findReturn(MF, **I, Cycles);
 131   }
 132 }
 133
 134 /// cyclesUntilReturn - if the MBB has a return instruction, set Location to
 135 /// to the instruction and return true. Return false otherwise.
 136 /// Cycles will be incremented by the number of cycles taken to reach the
 137 /// return or the end of the BB, whichever occurs first.
 138 bool PadShortFunc::cyclesUntilReturn(MachineFunction &MF,
 139                                   MachineBasicBlock &MBB,
 140                                   unsigned int &Cycles,
 141                                   MachineBasicBlock::iterator *Location)
 142 {
 143   const TargetInstrInfo &TII = *MF.getTarget().getInstrInfo();
 144   const TargetMachine &Target = MF.getTarget();
 145
 146   for (MachineBasicBlock::iterator MBBI = MBB.begin(); MBBI != MBB.end();
 147        ++MBBI) {
 148     MachineInstr *MI = MBBI;
 149     // Mark basic blocks with a return instruction. Calls to other functions
 150     // do not count because the called function will be padded, if necessary
 151     if (MI->isReturn() && !MI->isCall()) {
 152       if (Location)
 153         *Location = MBBI;
 154       return true;
 155     }
 156
 157     Cycles += TII.getInstrLatency(Target.getInstrItineraryData(), MI);
 158   }
 159
 160   return false;
 161 }
 162
 163 /// addPadding - Add the given number of NOOP instructions to the function
 164 /// right before the return at MBBI
 165 bool PadShortFunc::addPadding(MachineFunction &MF,
 166                               MachineBasicBlock &MBB,
 167                               MachineBasicBlock::iterator &MBBI,
 168                               unsigned int NOOPsToAdd)
 169 {
 170   const TargetInstrInfo &TII = *MF.getTarget().getInstrInfo();
 171
 172   DebugLoc DL = MBBI->getDebugLoc();
 173
 174   while (NOOPsToAdd-- > 0) {
 175     // Since Atom has two instruction execution ports,
 176     // the code emits two noops, which will be executed in parallell
 177     // during one cycle.
 178     BuildMI(MBB, MBBI, DL, TII.get(X86::NOOP));
 179     BuildMI(MBB, MBBI, DL, TII.get(X86::NOOP));
 180   }
 181
 182   return true;
 183 }
 184