X86PadShortFunction.cpp revision 302408
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 31using namespace llvm; 32 33#define DEBUG_TYPE "x86-pad-short-functions" 34 35STATISTIC(NumBBsPadded, "Number of basic blocks padded"); 36 37namespace { 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 const char *getPassName() const override { 59 return "X86 Atom pad short functions"; 60 } 61 62 private: 63 void findReturns(MachineBasicBlock *MBB, 64 unsigned int Cycles = 0); 65 66 bool cyclesUntilReturn(MachineBasicBlock *MBB, 67 unsigned int &Cycles); 68 69 void addPadding(MachineBasicBlock *MBB, 70 MachineBasicBlock::iterator &MBBI, 71 unsigned int NOOPsToAdd); 72 73 const unsigned int Threshold; 74 75 // ReturnBBs - Maps basic blocks that return to the minimum number of 76 // cycles until the return, starting from the entry block. 77 DenseMap<MachineBasicBlock*, unsigned int> ReturnBBs; 78 79 // VisitedBBs - Cache of previously visited BBs. 80 DenseMap<MachineBasicBlock*, VisitedBBInfo> VisitedBBs; 81 82 const X86Subtarget *STI; 83 const TargetInstrInfo *TII; 84 }; 85 86 char PadShortFunc::ID = 0; 87} 88 89FunctionPass *llvm::createX86PadShortFunctions() { 90 return new PadShortFunc(); 91} 92 93/// runOnMachineFunction - Loop over all of the basic blocks, inserting 94/// NOOP instructions before early exits. 95bool PadShortFunc::runOnMachineFunction(MachineFunction &MF) { 96 if (MF.getFunction()->optForSize()) { 97 return false; 98 } 99 100 STI = &MF.getSubtarget<X86Subtarget>(); 101 if (!STI->padShortFunctions()) 102 return false; 103 104 TII = STI->getInstrInfo(); 105 106 // Search through basic blocks and mark the ones that have early returns 107 ReturnBBs.clear(); 108 VisitedBBs.clear(); 109 findReturns(&MF.front()); 110 111 bool MadeChange = false; 112 113 MachineBasicBlock *MBB; 114 unsigned int Cycles = 0; 115 116 // Pad the identified basic blocks with NOOPs 117 for (DenseMap<MachineBasicBlock*, unsigned int>::iterator I = ReturnBBs.begin(); 118 I != ReturnBBs.end(); ++I) { 119 MBB = I->first; 120 Cycles = I->second; 121 122 if (Cycles < Threshold) { 123 // BB ends in a return. Skip over any DBG_VALUE instructions 124 // trailing the terminator. 125 assert(MBB->size() > 0 && 126 "Basic block should contain at least a RET but is empty"); 127 MachineBasicBlock::iterator ReturnLoc = --MBB->end(); 128 129 while (ReturnLoc->isDebugValue()) 130 --ReturnLoc; 131 assert(ReturnLoc->isReturn() && !ReturnLoc->isCall() && 132 "Basic block does not end with RET"); 133 134 addPadding(MBB, ReturnLoc, Threshold - Cycles); 135 NumBBsPadded++; 136 MadeChange = true; 137 } 138 } 139 140 return MadeChange; 141} 142 143/// findReturn - Starting at MBB, follow control flow and add all 144/// basic blocks that contain a return to ReturnBBs. 145void PadShortFunc::findReturns(MachineBasicBlock *MBB, unsigned int Cycles) { 146 // If this BB has a return, note how many cycles it takes to get there. 147 bool hasReturn = cyclesUntilReturn(MBB, Cycles); 148 if (Cycles >= Threshold) 149 return; 150 151 if (hasReturn) { 152 ReturnBBs[MBB] = std::max(ReturnBBs[MBB], Cycles); 153 return; 154 } 155 156 // Follow branches in BB and look for returns 157 for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(); 158 I != MBB->succ_end(); ++I) { 159 if (*I == MBB) 160 continue; 161 findReturns(*I, Cycles); 162 } 163} 164 165/// cyclesUntilReturn - return true if the MBB has a return instruction, 166/// and return false otherwise. 167/// Cycles will be incremented by the number of cycles taken to reach the 168/// return or the end of the BB, whichever occurs first. 169bool PadShortFunc::cyclesUntilReturn(MachineBasicBlock *MBB, 170 unsigned int &Cycles) { 171 // Return cached result if BB was previously visited 172 DenseMap<MachineBasicBlock*, VisitedBBInfo>::iterator it 173 = VisitedBBs.find(MBB); 174 if (it != VisitedBBs.end()) { 175 VisitedBBInfo BBInfo = it->second; 176 Cycles += BBInfo.Cycles; 177 return BBInfo.HasReturn; 178 } 179 180 unsigned int CyclesToEnd = 0; 181 182 for (MachineBasicBlock::iterator MBBI = MBB->begin(); 183 MBBI != MBB->end(); ++MBBI) { 184 MachineInstr *MI = MBBI; 185 // Mark basic blocks with a return instruction. Calls to other 186 // functions do not count because the called function will be padded, 187 // if necessary. 188 if (MI->isReturn() && !MI->isCall()) { 189 VisitedBBs[MBB] = VisitedBBInfo(true, CyclesToEnd); 190 Cycles += CyclesToEnd; 191 return true; 192 } 193 194 CyclesToEnd += TII->getInstrLatency(STI->getInstrItineraryData(), MI); 195 } 196 197 VisitedBBs[MBB] = VisitedBBInfo(false, CyclesToEnd); 198 Cycles += CyclesToEnd; 199 return false; 200} 201 202/// addPadding - Add the given number of NOOP instructions to the function 203/// just prior to the return at MBBI 204void PadShortFunc::addPadding(MachineBasicBlock *MBB, 205 MachineBasicBlock::iterator &MBBI, 206 unsigned int NOOPsToAdd) { 207 DebugLoc DL = MBBI->getDebugLoc(); 208 209 while (NOOPsToAdd-- > 0) { 210 BuildMI(*MBB, MBBI, DL, TII->get(X86::NOOP)); 211 BuildMI(*MBB, MBBI, DL, TII->get(X86::NOOP)); 212 } 213} 214