LLVM  6.0.0svn
X86PadShortFunction.cpp
Go to the documentation of this file.
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 <algorithm>
17 
18 #include "X86.h"
19 #include "X86InstrInfo.h"
20 #include "X86Subtarget.h"
21 #include "llvm/ADT/Statistic.h"
25 #include "llvm/CodeGen/Passes.h"
27 #include "llvm/IR/Function.h"
28 #include "llvm/Support/Debug.h"
30 
31 using namespace llvm;
32 
33 #define DEBUG_TYPE "x86-pad-short-functions"
34 
35 STATISTIC(NumBBsPadded, "Number of basic blocks padded");
36 
37 namespace {
38  struct VisitedBBInfo {
39  // HasReturn - Whether the BB contains a return instruction
40  bool HasReturn;
41 
42  // Cycles - Number of cycles until return if HasReturn is true, otherwise
43  // number of cycles until end of the BB
44  unsigned int Cycles;
45 
46  VisitedBBInfo() : HasReturn(false), Cycles(0) {}
47  VisitedBBInfo(bool HasReturn, unsigned int Cycles)
48  : HasReturn(HasReturn), Cycles(Cycles) {}
49  };
50 
51  struct PadShortFunc : public MachineFunctionPass {
52  static char ID;
53  PadShortFunc() : MachineFunctionPass(ID)
54  , Threshold(4), STI(nullptr), TII(nullptr) {}
55 
56  bool runOnMachineFunction(MachineFunction &MF) override;
57 
58  MachineFunctionProperties getRequiredProperties() const override {
61  }
62 
63  StringRef getPassName() const override {
64  return "X86 Atom pad short functions";
65  }
66 
67  private:
68  void findReturns(MachineBasicBlock *MBB,
69  unsigned int Cycles = 0);
70 
71  bool cyclesUntilReturn(MachineBasicBlock *MBB,
72  unsigned int &Cycles);
73 
74  void addPadding(MachineBasicBlock *MBB,
76  unsigned int NOOPsToAdd);
77 
78  const unsigned int Threshold;
79 
80  // ReturnBBs - Maps basic blocks that return to the minimum number of
81  // cycles until the return, starting from the entry block.
83 
84  // VisitedBBs - Cache of previously visited BBs.
86 
87  const X86Subtarget *STI;
88  const TargetInstrInfo *TII;
89  };
90 
91  char PadShortFunc::ID = 0;
92 }
93 
95  return new PadShortFunc();
96 }
97 
98 /// runOnMachineFunction - Loop over all of the basic blocks, inserting
99 /// NOOP instructions before early exits.
100 bool PadShortFunc::runOnMachineFunction(MachineFunction &MF) {
101  if (skipFunction(*MF.getFunction()))
102  return false;
103 
104  if (MF.getFunction()->optForSize()) {
105  return false;
106  }
107 
108  STI = &MF.getSubtarget<X86Subtarget>();
109  if (!STI->padShortFunctions())
110  return false;
111 
112  TII = STI->getInstrInfo();
113 
114  // Search through basic blocks and mark the ones that have early returns
115  ReturnBBs.clear();
116  VisitedBBs.clear();
117  findReturns(&MF.front());
118 
119  bool MadeChange = false;
120 
121  MachineBasicBlock *MBB;
122  unsigned int Cycles = 0;
123 
124  // Pad the identified basic blocks with NOOPs
126  I != ReturnBBs.end(); ++I) {
127  MBB = I->first;
128  Cycles = I->second;
129 
130  if (Cycles < Threshold) {
131  // BB ends in a return. Skip over any DBG_VALUE instructions
132  // trailing the terminator.
133  assert(MBB->size() > 0 &&
134  "Basic block should contain at least a RET but is empty");
135  MachineBasicBlock::iterator ReturnLoc = --MBB->end();
136 
137  while (ReturnLoc->isDebugValue())
138  --ReturnLoc;
139  assert(ReturnLoc->isReturn() && !ReturnLoc->isCall() &&
140  "Basic block does not end with RET");
141 
142  addPadding(MBB, ReturnLoc, Threshold - Cycles);
143  NumBBsPadded++;
144  MadeChange = true;
145  }
146  }
147 
148  return MadeChange;
149 }
150 
151 /// findReturn - Starting at MBB, follow control flow and add all
152 /// basic blocks that contain a return to ReturnBBs.
153 void PadShortFunc::findReturns(MachineBasicBlock *MBB, unsigned int Cycles) {
154  // If this BB has a return, note how many cycles it takes to get there.
155  bool hasReturn = cyclesUntilReturn(MBB, Cycles);
156  if (Cycles >= Threshold)
157  return;
158 
159  if (hasReturn) {
160  ReturnBBs[MBB] = std::max(ReturnBBs[MBB], Cycles);
161  return;
162  }
163 
164  // Follow branches in BB and look for returns
166  I != MBB->succ_end(); ++I) {
167  if (*I == MBB)
168  continue;
169  findReturns(*I, Cycles);
170  }
171 }
172 
173 /// cyclesUntilReturn - return true if the MBB has a return instruction,
174 /// and return false otherwise.
175 /// Cycles will be incremented by the number of cycles taken to reach the
176 /// return or the end of the BB, whichever occurs first.
177 bool PadShortFunc::cyclesUntilReturn(MachineBasicBlock *MBB,
178  unsigned int &Cycles) {
179  // Return cached result if BB was previously visited
181  = VisitedBBs.find(MBB);
182  if (it != VisitedBBs.end()) {
183  VisitedBBInfo BBInfo = it->second;
184  Cycles += BBInfo.Cycles;
185  return BBInfo.HasReturn;
186  }
187 
188  unsigned int CyclesToEnd = 0;
189 
190  for (MachineInstr &MI : *MBB) {
191  // Mark basic blocks with a return instruction. Calls to other
192  // functions do not count because the called function will be padded,
193  // if necessary.
194  if (MI.isReturn() && !MI.isCall()) {
195  VisitedBBs[MBB] = VisitedBBInfo(true, CyclesToEnd);
196  Cycles += CyclesToEnd;
197  return true;
198  }
199 
200  CyclesToEnd += TII->getInstrLatency(STI->getInstrItineraryData(), MI);
201  }
202 
203  VisitedBBs[MBB] = VisitedBBInfo(false, CyclesToEnd);
204  Cycles += CyclesToEnd;
205  return false;
206 }
207 
208 /// addPadding - Add the given number of NOOP instructions to the function
209 /// just prior to the return at MBBI
210 void PadShortFunc::addPadding(MachineBasicBlock *MBB,
212  unsigned int NOOPsToAdd) {
213  DebugLoc DL = MBBI->getDebugLoc();
214 
215  while (NOOPsToAdd-- > 0) {
216  BuildMI(*MBB, MBBI, DL, TII->get(X86::NOOP));
217  BuildMI(*MBB, MBBI, DL, TII->get(X86::NOOP));
218  }
219 }
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
STATISTIC(NumFunctions, "Total number of functions")
A debug info location.
Definition: DebugLoc.h:34
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
FunctionPass * createX86PadShortFunctions()
Return a pass that pads short functions with NOOPs.
unsigned getInstrLatency(const InstrItineraryData *ItinData, const MachineInstr &MI, unsigned *PredCost=nullptr) const override
Compute the instruction latency of a given instruction.
TargetInstrInfo - Interface to description of machine instruction set.
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
bool optForSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
Definition: Function.h:530
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
const MachineBasicBlock & front() const
static bool hasReturn(const MachineBasicBlock &MBB)
Returns true if MBB contains an instruction that returns.
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:59
#define I(x, y, z)
Definition: MD5.cpp:58
const Function * getFunction() const
getFunction - Return the LLVM function that this machine code represents
static int const Threshold
TODO: Write a new FunctionPass AliasAnalysis so that it can keep a cache.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
std::vector< MachineBasicBlock * >::iterator succ_iterator
Properties which a MachineFunction may have at a given point in time.