1 //===-------- X86PadShortFunction.cpp - pad short functions -----------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines the pass which will pad short functions to prevent 10 // a stall if a function returns before the return address is ready. This 11 // is needed for some Intel Atom processors. 12 // 13 //===----------------------------------------------------------------------===// 14 15 16 #include "X86.h" 17 #include "X86InstrInfo.h" 18 #include "X86Subtarget.h" 19 #include "llvm/ADT/Statistic.h" 20 #include "llvm/Analysis/ProfileSummaryInfo.h" 21 #include "llvm/CodeGen/LazyMachineBlockFrequencyInfo.h" 22 #include "llvm/CodeGen/MachineFunctionPass.h" 23 #include "llvm/CodeGen/MachineInstrBuilder.h" 24 #include "llvm/CodeGen/MachineSizeOpts.h" 25 #include "llvm/CodeGen/Passes.h" 26 #include "llvm/CodeGen/TargetSchedule.h" 27 #include "llvm/IR/Function.h" 28 29 using namespace llvm; 30 31 #define DEBUG_TYPE "x86-pad-short-functions" 32 33 STATISTIC(NumBBsPadded, "Number of basic blocks padded"); 34 35 namespace { 36 struct VisitedBBInfo { 37 // HasReturn - Whether the BB contains a return instruction 38 bool HasReturn = false; 39 40 // Cycles - Number of cycles until return if HasReturn is true, otherwise 41 // number of cycles until end of the BB 42 unsigned int Cycles = 0; 43 44 VisitedBBInfo() = default; 45 VisitedBBInfo(bool HasReturn, unsigned int Cycles) 46 : HasReturn(HasReturn), Cycles(Cycles) {} 47 }; 48 49 struct PadShortFunc : public MachineFunctionPass { 50 static char ID; 51 PadShortFunc() : MachineFunctionPass(ID) {} 52 53 bool runOnMachineFunction(MachineFunction &MF) override; 54 55 void getAnalysisUsage(AnalysisUsage &AU) const override { 56 AU.addRequired<ProfileSummaryInfoWrapperPass>(); 57 AU.addRequired<LazyMachineBlockFrequencyInfoPass>(); 58 AU.addPreserved<LazyMachineBlockFrequencyInfoPass>(); 59 MachineFunctionPass::getAnalysisUsage(AU); 60 } 61 62 MachineFunctionProperties getRequiredProperties() const override { 63 return MachineFunctionProperties().set( 64 MachineFunctionProperties::Property::NoVRegs); 65 } 66 67 StringRef getPassName() const override { 68 return "X86 Atom pad short functions"; 69 } 70 71 private: 72 void findReturns(MachineBasicBlock *MBB, 73 unsigned int Cycles = 0); 74 75 bool cyclesUntilReturn(MachineBasicBlock *MBB, 76 unsigned int &Cycles); 77 78 void addPadding(MachineBasicBlock *MBB, 79 MachineBasicBlock::iterator &MBBI, 80 unsigned int NOOPsToAdd); 81 82 const unsigned int Threshold = 4; 83 84 // ReturnBBs - Maps basic blocks that return to the minimum number of 85 // cycles until the return, starting from the entry block. 86 DenseMap<MachineBasicBlock*, unsigned int> ReturnBBs; 87 88 // VisitedBBs - Cache of previously visited BBs. 89 DenseMap<MachineBasicBlock*, VisitedBBInfo> VisitedBBs; 90 91 TargetSchedModel TSM; 92 }; 93 94 char PadShortFunc::ID = 0; 95 } 96 97 FunctionPass *llvm::createX86PadShortFunctions() { 98 return new PadShortFunc(); 99 } 100 101 /// runOnMachineFunction - Loop over all of the basic blocks, inserting 102 /// NOOP instructions before early exits. 103 bool PadShortFunc::runOnMachineFunction(MachineFunction &MF) { 104 if (skipFunction(MF.getFunction())) 105 return false; 106 107 if (MF.getFunction().hasOptSize()) 108 return false; 109 110 if (!MF.getSubtarget<X86Subtarget>().padShortFunctions()) 111 return false; 112 113 TSM.init(&MF.getSubtarget()); 114 115 auto *PSI = 116 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); 117 auto *MBFI = (PSI && PSI->hasProfileSummary()) ? 118 &getAnalysis<LazyMachineBlockFrequencyInfoPass>().getBFI() : 119 nullptr; 120 121 // Search through basic blocks and mark the ones that have early returns 122 ReturnBBs.clear(); 123 VisitedBBs.clear(); 124 findReturns(&MF.front()); 125 126 bool MadeChange = false; 127 128 // Pad the identified basic blocks with NOOPs 129 for (const auto &ReturnBB : ReturnBBs) { 130 MachineBasicBlock *MBB = ReturnBB.first; 131 unsigned Cycles = ReturnBB.second; 132 133 if (llvm::shouldOptimizeForSize(MBB, PSI, MBFI)) 134 continue; 135 136 if (Cycles < Threshold) { 137 // BB ends in a return. Skip over any DBG_VALUE instructions 138 // trailing the terminator. 139 assert(MBB->size() > 0 && 140 "Basic block should contain at least a RET but is empty"); 141 MachineBasicBlock::iterator ReturnLoc = --MBB->end(); 142 143 while (ReturnLoc->isDebugInstr()) 144 --ReturnLoc; 145 assert(ReturnLoc->isReturn() && !ReturnLoc->isCall() && 146 "Basic block does not end with RET"); 147 148 addPadding(MBB, ReturnLoc, Threshold - Cycles); 149 NumBBsPadded++; 150 MadeChange = true; 151 } 152 } 153 154 return MadeChange; 155 } 156 157 /// findReturn - Starting at MBB, follow control flow and add all 158 /// basic blocks that contain a return to ReturnBBs. 159 void PadShortFunc::findReturns(MachineBasicBlock *MBB, unsigned int Cycles) { 160 // If this BB has a return, note how many cycles it takes to get there. 161 bool hasReturn = cyclesUntilReturn(MBB, Cycles); 162 if (Cycles >= Threshold) 163 return; 164 165 if (hasReturn) { 166 ReturnBBs[MBB] = std::max(ReturnBBs[MBB], Cycles); 167 return; 168 } 169 170 // Follow branches in BB and look for returns 171 for (MachineBasicBlock *Succ : MBB->successors()) 172 if (Succ != MBB) 173 findReturns(Succ, Cycles); 174 } 175 176 /// cyclesUntilReturn - return true if the MBB has a return instruction, 177 /// and return false otherwise. 178 /// Cycles will be incremented by the number of cycles taken to reach the 179 /// return or the end of the BB, whichever occurs first. 180 bool PadShortFunc::cyclesUntilReturn(MachineBasicBlock *MBB, 181 unsigned int &Cycles) { 182 // Return cached result if BB was previously visited 183 DenseMap<MachineBasicBlock*, VisitedBBInfo>::iterator it 184 = VisitedBBs.find(MBB); 185 if (it != VisitedBBs.end()) { 186 VisitedBBInfo BBInfo = it->second; 187 Cycles += BBInfo.Cycles; 188 return BBInfo.HasReturn; 189 } 190 191 unsigned int CyclesToEnd = 0; 192 193 for (MachineInstr &MI : *MBB) { 194 // Mark basic blocks with a return instruction. Calls to other 195 // functions do not count because the called function will be padded, 196 // if necessary. 197 if (MI.isReturn() && !MI.isCall()) { 198 VisitedBBs[MBB] = VisitedBBInfo(true, CyclesToEnd); 199 Cycles += CyclesToEnd; 200 return true; 201 } 202 203 CyclesToEnd += TSM.computeInstrLatency(&MI); 204 } 205 206 VisitedBBs[MBB] = VisitedBBInfo(false, CyclesToEnd); 207 Cycles += CyclesToEnd; 208 return false; 209 } 210 211 /// addPadding - Add the given number of NOOP instructions to the function 212 /// just prior to the return at MBBI 213 void PadShortFunc::addPadding(MachineBasicBlock *MBB, 214 MachineBasicBlock::iterator &MBBI, 215 unsigned int NOOPsToAdd) { 216 const DebugLoc &DL = MBBI->getDebugLoc(); 217 unsigned IssueWidth = TSM.getIssueWidth(); 218 219 for (unsigned i = 0, e = IssueWidth * NOOPsToAdd; i != e; ++i) 220 BuildMI(*MBB, MBBI, DL, TSM.getInstrInfo()->get(X86::NOOP)); 221 } 222