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" 22 #include "llvm/CodeGen/MachineFunctionPass.h" 23 #include "llvm/CodeGen/MachineInstrBuilder.h" 24 #include "llvm/CodeGen/MachineRegisterInfo.h" 25 #include "llvm/CodeGen/Passes.h" 26 #include "llvm/IR/Function.h" 27 #include "llvm/Support/Debug.h" 28 #include "llvm/Support/raw_ostream.h" 29 #include "llvm/Target/TargetInstrInfo.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 { 59 return MachineFunctionProperties().set( 60 MachineFunctionProperties::Property::AllVRegsAllocated); 61 } 62 63 const char *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, 75 MachineBasicBlock::iterator &MBBI, 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. 82 DenseMap<MachineBasicBlock*, unsigned int> ReturnBBs; 83 84 // VisitedBBs - Cache of previously visited BBs. 85 DenseMap<MachineBasicBlock*, VisitedBBInfo> VisitedBBs; 86 87 const X86Subtarget *STI; 88 const TargetInstrInfo *TII; 89 }; 90 91 char PadShortFunc::ID = 0; 92 } 93 94 FunctionPass *llvm::createX86PadShortFunctions() { 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 125 for (DenseMap<MachineBasicBlock*, unsigned int>::iterator I = ReturnBBs.begin(); 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 165 for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(); 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 180 DenseMap<MachineBasicBlock*, VisitedBBInfo>::iterator it 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, 211 MachineBasicBlock::iterator &MBBI, 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 } 220
