| 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/MachineBlockFrequencyInfo.h" |
| 23 | #include "llvm/CodeGen/MachineFunctionAnalysisManager.h" |
| 24 | #include "llvm/CodeGen/MachineFunctionPass.h" |
| 25 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
| 26 | #include "llvm/CodeGen/MachinePassManager.h" |
| 27 | #include "llvm/CodeGen/MachineSizeOpts.h" |
| 28 | #include "llvm/CodeGen/Passes.h" |
| 29 | #include "llvm/CodeGen/TargetSchedule.h" |
| 30 | #include "llvm/IR/Analysis.h" |
| 31 | #include "llvm/IR/Function.h" |
| 32 | |
| 33 | using namespace llvm; |
| 34 | |
| 35 | #define DEBUG_TYPE "x86-pad-short-functions" |
| 36 | |
| 37 | STATISTIC(NumBBsPadded, "Number of basic blocks padded" ); |
| 38 | |
| 39 | namespace { |
| 40 | struct VisitedBBInfo { |
| 41 | // HasReturn - Whether the BB contains a return instruction |
| 42 | bool HasReturn = false; |
| 43 | |
| 44 | // Cycles - Number of cycles until return if HasReturn is true, otherwise |
| 45 | // number of cycles until end of the BB |
| 46 | unsigned int Cycles = 0; |
| 47 | |
| 48 | VisitedBBInfo() = default; |
| 49 | VisitedBBInfo(bool HasReturn, unsigned int Cycles) |
| 50 | : HasReturn(HasReturn), Cycles(Cycles) {} |
| 51 | }; |
| 52 | |
| 53 | struct X86PadShortFunctionsLegacy : public MachineFunctionPass { |
| 54 | static char ID; |
| 55 | X86PadShortFunctionsLegacy() : MachineFunctionPass(ID) {} |
| 56 | |
| 57 | bool runOnMachineFunction(MachineFunction &MF) override; |
| 58 | |
| 59 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
| 60 | AU.addRequired<ProfileSummaryInfoWrapperPass>(); |
| 61 | AU.addRequired<LazyMachineBlockFrequencyInfoPass>(); |
| 62 | AU.addPreserved<LazyMachineBlockFrequencyInfoPass>(); |
| 63 | MachineFunctionPass::getAnalysisUsage(AU); |
| 64 | } |
| 65 | |
| 66 | MachineFunctionProperties getRequiredProperties() const override { |
| 67 | return MachineFunctionProperties().setNoVRegs(); |
| 68 | } |
| 69 | |
| 70 | StringRef getPassName() const override { |
| 71 | return "X86 Atom pad short functions" ; |
| 72 | } |
| 73 | }; |
| 74 | |
| 75 | class X86PadShortFunctionsImpl { |
| 76 | public: |
| 77 | bool runOnMachineFunction( |
| 78 | MachineFunction &MF, llvm::function_ref<ProfileSummaryInfo *()> GetPSI, |
| 79 | llvm::function_ref<MachineBlockFrequencyInfo *()> GetMBFI); |
| 80 | |
| 81 | private: |
| 82 | void findReturns(MachineBasicBlock *MBB, |
| 83 | unsigned int Cycles = 0); |
| 84 | |
| 85 | bool cyclesUntilReturn(MachineBasicBlock *MBB, |
| 86 | unsigned int &Cycles); |
| 87 | |
| 88 | void addPadding(MachineBasicBlock *MBB, |
| 89 | MachineBasicBlock::iterator &MBBI, |
| 90 | unsigned int NOOPsToAdd); |
| 91 | |
| 92 | const unsigned int Threshold = 4; |
| 93 | |
| 94 | // ReturnBBs - Maps basic blocks that return to the minimum number of |
| 95 | // cycles until the return, starting from the entry block. |
| 96 | DenseMap<MachineBasicBlock*, unsigned int> ReturnBBs; |
| 97 | |
| 98 | // VisitedBBs - Cache of previously visited BBs. |
| 99 | DenseMap<MachineBasicBlock*, VisitedBBInfo> VisitedBBs; |
| 100 | |
| 101 | TargetSchedModel TSM; |
| 102 | }; |
| 103 | |
| 104 | char X86PadShortFunctionsLegacy::ID = 0; |
| 105 | } |
| 106 | |
| 107 | FunctionPass *llvm::createX86PadShortFunctionsLegacyPass() { |
| 108 | return new X86PadShortFunctionsLegacy(); |
| 109 | } |
| 110 | |
| 111 | bool X86PadShortFunctionsLegacy::runOnMachineFunction(MachineFunction &MF) { |
| 112 | if (skipFunction(F: MF.getFunction())) |
| 113 | return false; |
| 114 | |
| 115 | X86PadShortFunctionsImpl Impl; |
| 116 | return Impl.runOnMachineFunction( |
| 117 | MF, |
| 118 | GetPSI: [&]() { return &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); }, |
| 119 | GetMBFI: [&]() { |
| 120 | return &getAnalysis<LazyMachineBlockFrequencyInfoPass>().getBFI(); |
| 121 | }); |
| 122 | } |
| 123 | |
| 124 | PreservedAnalyses |
| 125 | X86PadShortFunctionsPass::run(MachineFunction &MF, |
| 126 | MachineFunctionAnalysisManager &MFAM) { |
| 127 | X86PadShortFunctionsImpl Impl; |
| 128 | bool Changed = Impl.runOnMachineFunction( |
| 129 | MF, |
| 130 | GetPSI: [&]() { |
| 131 | return MFAM.getResult<ModuleAnalysisManagerMachineFunctionProxy>(IR&: MF) |
| 132 | .getCachedResult<ProfileSummaryAnalysis>( |
| 133 | IR&: *MF.getFunction().getParent()); |
| 134 | }, |
| 135 | GetMBFI: [&]() { return &MFAM.getResult<MachineBlockFrequencyAnalysis>(IR&: MF); }); |
| 136 | return Changed ? getMachineFunctionPassPreservedAnalyses() |
| 137 | .preserveSet<CFGAnalyses>() |
| 138 | : PreservedAnalyses::all(); |
| 139 | ; |
| 140 | } |
| 141 | |
| 142 | /// runOnMachineFunction - Loop over all of the basic blocks, inserting |
| 143 | /// NOOP instructions before early exits. |
| 144 | bool X86PadShortFunctionsImpl::runOnMachineFunction( |
| 145 | MachineFunction &MF, llvm::function_ref<ProfileSummaryInfo *()> GetPSI, |
| 146 | llvm::function_ref<MachineBlockFrequencyInfo *()> GetMBFI) { |
| 147 | LLVM_DEBUG(dbgs() << "Start X86PadShortFunctionPass\n" ;); |
| 148 | |
| 149 | if (MF.getFunction().hasOptSize()) |
| 150 | return false; |
| 151 | |
| 152 | if (!MF.getSubtarget<X86Subtarget>().padShortFunctions()) |
| 153 | return false; |
| 154 | |
| 155 | TSM.init(TSInfo: &MF.getSubtarget()); |
| 156 | |
| 157 | ProfileSummaryInfo *PSI = GetPSI(); |
| 158 | MachineBlockFrequencyInfo *MBFI = nullptr; |
| 159 | if (PSI && PSI->hasProfileSummary()) |
| 160 | MBFI = GetMBFI(); |
| 161 | |
| 162 | // Search through basic blocks and mark the ones that have early returns |
| 163 | ReturnBBs.clear(); |
| 164 | VisitedBBs.clear(); |
| 165 | findReturns(MBB: &MF.front()); |
| 166 | |
| 167 | bool MadeChange = false; |
| 168 | |
| 169 | // Pad the identified basic blocks with NOOPs |
| 170 | for (const auto &ReturnBB : ReturnBBs) { |
| 171 | MachineBasicBlock *MBB = ReturnBB.first; |
| 172 | unsigned Cycles = ReturnBB.second; |
| 173 | |
| 174 | if (llvm::shouldOptimizeForSize(MBB, PSI, MBFI)) |
| 175 | continue; |
| 176 | |
| 177 | if (Cycles < Threshold) { |
| 178 | // BB ends in a return. Skip over any DBG_VALUE instructions |
| 179 | // trailing the terminator. |
| 180 | assert(MBB->size() > 0 && |
| 181 | "Basic block should contain at least a RET but is empty" ); |
| 182 | MachineBasicBlock::iterator ReturnLoc = --MBB->end(); |
| 183 | |
| 184 | while (ReturnLoc->isDebugInstr()) |
| 185 | --ReturnLoc; |
| 186 | assert(ReturnLoc->isReturn() && !ReturnLoc->isCall() && |
| 187 | "Basic block does not end with RET" ); |
| 188 | |
| 189 | addPadding(MBB, MBBI&: ReturnLoc, NOOPsToAdd: Threshold - Cycles); |
| 190 | NumBBsPadded++; |
| 191 | MadeChange = true; |
| 192 | } |
| 193 | } |
| 194 | LLVM_DEBUG(dbgs() << "End X86PadShortFunctionPass\n" ;); |
| 195 | return MadeChange; |
| 196 | } |
| 197 | |
| 198 | /// findReturn - Starting at MBB, follow control flow and add all |
| 199 | /// basic blocks that contain a return to ReturnBBs. |
| 200 | void X86PadShortFunctionsImpl::findReturns(MachineBasicBlock *MBB, |
| 201 | unsigned int Cycles) { |
| 202 | // If this BB has a return, note how many cycles it takes to get there. |
| 203 | bool hasReturn = cyclesUntilReturn(MBB, Cycles); |
| 204 | if (Cycles >= Threshold) |
| 205 | return; |
| 206 | |
| 207 | if (hasReturn) { |
| 208 | unsigned int &NumCycles = ReturnBBs[MBB]; |
| 209 | NumCycles = std::max(a: NumCycles, b: Cycles); |
| 210 | return; |
| 211 | } |
| 212 | |
| 213 | // Follow branches in BB and look for returns |
| 214 | for (MachineBasicBlock *Succ : MBB->successors()) |
| 215 | if (Succ != MBB) |
| 216 | findReturns(MBB: Succ, Cycles); |
| 217 | } |
| 218 | |
| 219 | /// cyclesUntilReturn - return true if the MBB has a return instruction, |
| 220 | /// and return false otherwise. |
| 221 | /// Cycles will be incremented by the number of cycles taken to reach the |
| 222 | /// return or the end of the BB, whichever occurs first. |
| 223 | bool X86PadShortFunctionsImpl::cyclesUntilReturn(MachineBasicBlock *MBB, |
| 224 | unsigned int &Cycles) { |
| 225 | // Return cached result if BB was previously visited |
| 226 | auto [It, Inserted] = VisitedBBs.try_emplace(Key: MBB); |
| 227 | if (!Inserted) { |
| 228 | VisitedBBInfo BBInfo = It->second; |
| 229 | Cycles += BBInfo.Cycles; |
| 230 | return BBInfo.HasReturn; |
| 231 | } |
| 232 | |
| 233 | unsigned int CyclesToEnd = 0; |
| 234 | |
| 235 | for (MachineInstr &MI : *MBB) { |
| 236 | // Mark basic blocks with a return instruction. Calls to other |
| 237 | // functions do not count because the called function will be padded, |
| 238 | // if necessary. |
| 239 | if (MI.isReturn() && !MI.isCall()) { |
| 240 | It->second = VisitedBBInfo(true, CyclesToEnd); |
| 241 | Cycles += CyclesToEnd; |
| 242 | return true; |
| 243 | } |
| 244 | |
| 245 | CyclesToEnd += TSM.computeInstrLatency(MI: &MI); |
| 246 | } |
| 247 | |
| 248 | It->second = VisitedBBInfo(false, CyclesToEnd); |
| 249 | Cycles += CyclesToEnd; |
| 250 | return false; |
| 251 | } |
| 252 | |
| 253 | /// addPadding - Add the given number of NOOP instructions to the function |
| 254 | /// just prior to the return at MBBI |
| 255 | void X86PadShortFunctionsImpl::addPadding(MachineBasicBlock *MBB, |
| 256 | MachineBasicBlock::iterator &MBBI, |
| 257 | unsigned int NOOPsToAdd) { |
| 258 | const DebugLoc &DL = MBBI->getDebugLoc(); |
| 259 | unsigned IssueWidth = TSM.getIssueWidth(); |
| 260 | |
| 261 | for (unsigned i = 0, e = IssueWidth * NOOPsToAdd; i != e; ++i) |
| 262 | BuildMI(BB&: *MBB, I: MBBI, MIMD: DL, MCID: TSM.getInstrInfo()->get(Opcode: X86::NOOP)); |
| 263 | } |
| 264 | |