222 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file defines the pass which will pad short functions to prevent10// a stall if a function returns before the return address is ready. This11// 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 29using namespace llvm;30 31#define DEBUG_TYPE "x86-pad-short-functions"32 33STATISTIC(NumBBsPadded, "Number of basic blocks padded");34 35namespace {36 struct VisitedBBInfo {37 // HasReturn - Whether the BB contains a return instruction38 bool HasReturn = false;39 40 // Cycles - Number of cycles until return if HasReturn is true, otherwise41 // number of cycles until end of the BB42 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().setNoVRegs();64 }65 66 StringRef getPassName() const override {67 return "X86 Atom pad short functions";68 }69 70 private:71 void findReturns(MachineBasicBlock *MBB,72 unsigned int Cycles = 0);73 74 bool cyclesUntilReturn(MachineBasicBlock *MBB,75 unsigned int &Cycles);76 77 void addPadding(MachineBasicBlock *MBB,78 MachineBasicBlock::iterator &MBBI,79 unsigned int NOOPsToAdd);80 81 const unsigned int Threshold = 4;82 83 // ReturnBBs - Maps basic blocks that return to the minimum number of84 // cycles until the return, starting from the entry block.85 DenseMap<MachineBasicBlock*, unsigned int> ReturnBBs;86 87 // VisitedBBs - Cache of previously visited BBs.88 DenseMap<MachineBasicBlock*, VisitedBBInfo> VisitedBBs;89 90 TargetSchedModel TSM;91 };92 93 char PadShortFunc::ID = 0;94}95 96FunctionPass *llvm::createX86PadShortFunctions() {97 return new PadShortFunc();98}99 100/// runOnMachineFunction - Loop over all of the basic blocks, inserting101/// NOOP instructions before early exits.102bool PadShortFunc::runOnMachineFunction(MachineFunction &MF) {103 LLVM_DEBUG(dbgs() << "Start X86PadShortFunctionPass\n";);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 returns122 ReturnBBs.clear();123 VisitedBBs.clear();124 findReturns(&MF.front());125 126 bool MadeChange = false;127 128 // Pad the identified basic blocks with NOOPs129 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 instructions138 // 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 LLVM_DEBUG(dbgs() << "End X86PadShortFunctionPass\n";);154 return MadeChange;155}156 157/// findReturn - Starting at MBB, follow control flow and add all158/// basic blocks that contain a return to ReturnBBs.159void 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 unsigned int &NumCycles = ReturnBBs[MBB];167 NumCycles = std::max(NumCycles, Cycles);168 return;169 }170 171 // Follow branches in BB and look for returns172 for (MachineBasicBlock *Succ : MBB->successors())173 if (Succ != MBB)174 findReturns(Succ, Cycles);175}176 177/// cyclesUntilReturn - return true if the MBB has a return instruction,178/// and return false otherwise.179/// Cycles will be incremented by the number of cycles taken to reach the180/// return or the end of the BB, whichever occurs first.181bool PadShortFunc::cyclesUntilReturn(MachineBasicBlock *MBB,182 unsigned int &Cycles) {183 // Return cached result if BB was previously visited184 auto [It, Inserted] = VisitedBBs.try_emplace(MBB);185 if (!Inserted) {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 other195 // functions do not count because the called function will be padded,196 // if necessary.197 if (MI.isReturn() && !MI.isCall()) {198 It->second = VisitedBBInfo(true, CyclesToEnd);199 Cycles += CyclesToEnd;200 return true;201 }202 203 CyclesToEnd += TSM.computeInstrLatency(&MI);204 }205 206 It->second = VisitedBBInfo(false, CyclesToEnd);207 Cycles += CyclesToEnd;208 return false;209}210 211/// addPadding - Add the given number of NOOP instructions to the function212/// just prior to the return at MBBI213void 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