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
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 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().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 of
84 // 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, inserting
101/// NOOP instructions before early exits.
102bool PadShortFunc::runOnMachineFunction(MachineFunction &MF) {
103 LLVM_DEBUG(dbgs() << "Start X86PadShortFunctionPass\n";);
104 if (skipFunction(F: 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(TSInfo: &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(MBB: &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, MBBI&: ReturnLoc, NOOPsToAdd: 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 all
158/// 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(a: NumCycles, b: Cycles);
168 return;
169 }
170
171 // Follow branches in BB and look for returns
172 for (MachineBasicBlock *Succ : MBB->successors())
173 if (Succ != MBB)
174 findReturns(MBB: 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 the
180/// 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 visited
184 auto [It, Inserted] = VisitedBBs.try_emplace(Key: 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 other
195 // 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: &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 function
212/// just prior to the return at MBBI
213void 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(BB&: *MBB, I: MBBI, MIMD: DL, MCID: TSM.getInstrInfo()->get(Opcode: X86::NOOP));
221}
222