1//===- llvm/CodeGen/BasicBlockMatchingAndInference.cpp ----------*- C++ -*-===//
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// In Propeller's profile, we have already read the hash values of basic blocks,
10// as well as the weights of basic blocks and edges in the CFG. In this file,
11// we first match the basic blocks in the profile with those in the current
12// MachineFunction using the basic block hash, thereby obtaining the weights of
13// some basic blocks and edges. Subsequently, we infer the weights of all basic
14// blocks using an inference algorithm.
15//
16// TODO: Integrate part of the code in this file with BOLT's implementation into
17// the LLVM infrastructure, enabling both BOLT and Propeller to reuse it.
18//
19//===----------------------------------------------------------------------===//
20
21#include "llvm/CodeGen/BasicBlockMatchingAndInference.h"
22#include "llvm/ADT/DenseMap.h"
23#include "llvm/ADT/DenseSet.h"
24#include "llvm/CodeGen/BasicBlockSectionsProfileReader.h"
25#include "llvm/CodeGen/MachineBlockHashInfo.h"
26#include "llvm/CodeGen/Passes.h"
27#include "llvm/InitializePasses.h"
28#include "llvm/Support/Debug.h"
29#include <llvm/Support/CommandLine.h>
30
31using namespace llvm;
32
33#define DEBUG_TYPE "machine-block-match-infer"
34
35static cl::opt<float>
36 PropellerInferThreshold("propeller-infer-threshold",
37 cl::desc("Threshold for infer stale profile"),
38 cl::init(Val: 0.6));
39
40static cl::opt<bool>
41 PropellerMatchBBID("propeller-match-bbid",
42 cl::desc("Match basic blocks using BBIDs instead of "
43 "hashes for Propeller inference"),
44 cl::init(Val: false), cl::Optional);
45
46/// The object is used to identify and match basic blocks given their hashes.
47class StaleMatcher {
48public:
49 /// Initialize stale matcher.
50 void init(const std::vector<MachineBasicBlock *> &Blocks,
51 const std::vector<BlendedBlockHash> &Hashes) {
52 assert(Blocks.size() == Hashes.size() &&
53 "incorrect matcher initialization");
54 for (size_t I = 0; I < Blocks.size(); I++) {
55 MachineBasicBlock *Block = Blocks[I];
56 uint16_t OpHash = Hashes[I].getOpcodeHash();
57 OpHashToBlocks[OpHash].push_back(x: std::make_pair(x: Hashes[I], y&: Block));
58 }
59 }
60
61 /// Find the most similar block for a given hash.
62 MachineBasicBlock *matchBlock(BlendedBlockHash BlendedHash) const {
63 auto BlockIt = OpHashToBlocks.find(Val: BlendedHash.getOpcodeHash());
64 if (BlockIt == OpHashToBlocks.end()) {
65 return nullptr;
66 }
67 MachineBasicBlock *BestBlock = nullptr;
68 uint64_t BestDist = std::numeric_limits<uint64_t>::max();
69 for (auto It : BlockIt->second) {
70 MachineBasicBlock *Block = It.second;
71 BlendedBlockHash Hash = It.first;
72 uint64_t Dist = Hash.distance(BBH: BlendedHash);
73 if (BestBlock == nullptr || Dist < BestDist) {
74 BestDist = Dist;
75 BestBlock = Block;
76 }
77 }
78 return BestBlock;
79 }
80
81private:
82 using HashBlockPairType = std::pair<BlendedBlockHash, MachineBasicBlock *>;
83 DenseMap<uint16_t, std::vector<HashBlockPairType>> OpHashToBlocks;
84};
85
86INITIALIZE_PASS_BEGIN(BasicBlockMatchingAndInference,
87 "machine-block-match-infer",
88 "Machine Block Matching and Inference Analysis", true,
89 true)
90INITIALIZE_PASS_DEPENDENCY(MachineBlockHashInfo)
91INITIALIZE_PASS_DEPENDENCY(BasicBlockSectionsProfileReaderWrapperPass)
92INITIALIZE_PASS_END(BasicBlockMatchingAndInference, "machine-block-match-infer",
93 "Machine Block Matching and Inference Analysis", true, true)
94
95char BasicBlockMatchingAndInference::ID = 0;
96
97BasicBlockMatchingAndInference::BasicBlockMatchingAndInference()
98 : MachineFunctionPass(ID) {}
99
100void BasicBlockMatchingAndInference::getAnalysisUsage(AnalysisUsage &AU) const {
101 AU.addRequired<MachineBlockHashInfo>();
102 AU.addRequired<BasicBlockSectionsProfileReaderWrapperPass>();
103 AU.setPreservesAll();
104 MachineFunctionPass::getAnalysisUsage(AU);
105}
106
107std::optional<BasicBlockMatchingAndInference::WeightInfo>
108BasicBlockMatchingAndInference::getWeightInfo(StringRef FuncName) const {
109 auto It = ProgramWeightInfo.find(Key: FuncName);
110 if (It == ProgramWeightInfo.end()) {
111 return std::nullopt;
112 }
113 return It->second;
114}
115
116BasicBlockMatchingAndInference::WeightInfo
117BasicBlockMatchingAndInference::initWeightInfoByMatching(MachineFunction &MF) {
118 std::vector<MachineBasicBlock *> Blocks;
119 std::vector<BlendedBlockHash> Hashes;
120 auto BSPR = &getAnalysis<BasicBlockSectionsProfileReaderWrapperPass>();
121 auto MBHI = &getAnalysis<MachineBlockHashInfo>();
122 for (auto &Block : MF) {
123 Blocks.push_back(x: &Block);
124 Hashes.push_back(x: BlendedBlockHash(MBHI->getMBBHash(MBB: Block)));
125 }
126 StaleMatcher Matcher;
127 Matcher.init(Blocks, Hashes);
128 BasicBlockMatchingAndInference::WeightInfo MatchWeight;
129 const CFGProfile *CFG = BSPR->getFunctionCFGProfile(FuncName: MF.getName());
130 if (CFG == nullptr)
131 return MatchWeight;
132 for (auto &BlockCount : CFG->NodeCounts) {
133 if (CFG->BBHashes.count(Val: BlockCount.first.BaseID)) {
134 auto Hash = CFG->BBHashes.lookup(Val: BlockCount.first.BaseID);
135 MachineBasicBlock *Block = Matcher.matchBlock(BlendedHash: BlendedBlockHash(Hash));
136 // When a basic block has clone copies, sum their counts.
137 if (Block != nullptr)
138 MatchWeight.BlockWeights[Block] += BlockCount.second;
139 }
140 }
141 for (auto &PredItem : CFG->EdgeCounts) {
142 auto PredID = PredItem.first.BaseID;
143 if (!CFG->BBHashes.count(Val: PredID))
144 continue;
145 auto PredHash = CFG->BBHashes.lookup(Val: PredID);
146 MachineBasicBlock *PredBlock =
147 Matcher.matchBlock(BlendedHash: BlendedBlockHash(PredHash));
148 if (PredBlock == nullptr)
149 continue;
150 for (auto &SuccItem : PredItem.second) {
151 auto SuccID = SuccItem.first.BaseID;
152 auto EdgeWeight = SuccItem.second;
153 if (CFG->BBHashes.count(Val: SuccID)) {
154 auto SuccHash = CFG->BBHashes.lookup(Val: SuccID);
155 MachineBasicBlock *SuccBlock =
156 Matcher.matchBlock(BlendedHash: BlendedBlockHash(SuccHash));
157 // When an edge has clone copies, sum their counts.
158 if (SuccBlock != nullptr)
159 MatchWeight.EdgeWeights[std::make_pair(x&: PredBlock, y&: SuccBlock)] +=
160 EdgeWeight;
161 }
162 }
163 }
164 return MatchWeight;
165}
166
167BasicBlockMatchingAndInference::WeightInfo
168BasicBlockMatchingAndInference::initWeightInfoByBBID(MachineFunction &MF,
169 const CFGProfile &CFG) {
170 // Path cloning does not run before matching and inference, so blocks are
171 // identified by their base IDs. The counts of clones in the profile are
172 // attributed to the original block.
173 DenseMap<unsigned, MachineBasicBlock *> BaseIDToMBB;
174 for (auto &MBB : MF) {
175 unsigned BaseID = MBB.getBBID() ? MBB.getBBID()->BaseID
176 : static_cast<unsigned>(MBB.getNumber());
177 BaseIDToMBB[BaseID] = &MBB;
178 }
179 auto FindMBB = [&](const UniqueBBID &BBID) {
180 return BaseIDToMBB.lookup(Val: BBID.BaseID);
181 };
182
183 // A basic block is matched only if it exists in CFG.NodeCounts and all of its
184 // edges in the CFG profile are also edges in the MIR. The profile may omit
185 // edges without samples, so MIR edges missing from the profile are allowed.
186 // Both ends of a profile edge that is not in the MIR are kept as unknown.
187 DenseSet<const MachineBasicBlock *> MismatchedMBBs;
188 for (const auto &[PredID, Succs] : CFG.EdgeCounts) {
189 MachineBasicBlock *PredMBB = FindMBB(PredID);
190 for (const auto &[SuccID, EdgeCount] : Succs) {
191 MachineBasicBlock *SuccMBB = FindMBB(SuccID);
192 if (PredMBB && SuccMBB && PredMBB->isSuccessor(MBB: SuccMBB))
193 continue;
194 if (PredMBB)
195 MismatchedMBBs.insert(V: PredMBB);
196 if (SuccMBB)
197 MismatchedMBBs.insert(V: SuccMBB);
198 }
199 }
200 DenseSet<const MachineBasicBlock *> ProfiledMBBs;
201 for (const auto &[BBID, BlockCount] : CFG.NodeCounts)
202 if (MachineBasicBlock *MBB = FindMBB(BBID))
203 ProfiledMBBs.insert(V: MBB);
204 DenseSet<const MachineBasicBlock *> MatchedMBBs;
205 for (auto &MBB : MF) {
206 if (!ProfiledMBBs.contains(V: &MBB))
207 continue;
208 if (MismatchedMBBs.contains(V: &MBB))
209 LLVM_DEBUG(dbgs() << MF.getName() << ": bb." << MBB.getNumber()
210 << " has profile edges that are not in the CFG\n");
211 else
212 MatchedMBBs.insert(V: &MBB);
213 }
214
215 BasicBlockMatchingAndInference::WeightInfo MatchWeight;
216 for (const auto &[BBID, BlockCount] : CFG.NodeCounts) {
217 MachineBasicBlock *MBB = FindMBB(BBID);
218 if (MBB && MatchedMBBs.count(V: MBB))
219 MatchWeight.BlockWeights[MBB] += BlockCount;
220 }
221 for (const auto &[PredID, Succs] : CFG.EdgeCounts) {
222 MachineBasicBlock *PredMBB = FindMBB(PredID);
223 if (!PredMBB || !MatchedMBBs.count(V: PredMBB))
224 continue;
225 for (const auto &[SuccID, EdgeCount] : Succs) {
226 MachineBasicBlock *SuccMBB = FindMBB(SuccID);
227 if (!SuccMBB || !MatchedMBBs.count(V: SuccMBB))
228 continue;
229 MatchWeight.EdgeWeights[std::make_pair(x&: PredMBB, y&: SuccMBB)] += EdgeCount;
230 }
231 }
232 return MatchWeight;
233}
234
235void BasicBlockMatchingAndInference::generateWeightInfoByInference(
236 MachineFunction &MF,
237 BasicBlockMatchingAndInference::WeightInfo &MatchWeight) {
238 BlockEdgeMap Successors;
239 for (auto &Block : MF) {
240 for (auto *Succ : Block.successors())
241 Successors[&Block].push_back(Elt: Succ);
242 }
243 SampleProfileInference<MachineFunction> SPI(
244 MF, Successors, MatchWeight.BlockWeights, MatchWeight.EdgeWeights);
245 BlockWeightMap BlockWeights;
246 EdgeWeightMap EdgeWeights;
247 SPI.apply(BlockWeights, EdgeWeights);
248 ProgramWeightInfo.try_emplace(
249 Key: MF.getName(), Args: BasicBlockMatchingAndInference::WeightInfo{
250 .BlockWeights: std::move(BlockWeights), .EdgeWeights: std::move(EdgeWeights)});
251}
252
253bool BasicBlockMatchingAndInference::runOnMachineFunction(MachineFunction &MF) {
254 if (MF.empty())
255 return false;
256 auto *BSPR = &getAnalysis<BasicBlockSectionsProfileReaderWrapperPass>();
257 const CFGProfile *CFG = BSPR->getFunctionCFGProfile(FuncName: MF.getName());
258 if (CFG == nullptr || (CFG->NodeCounts.empty() && CFG->EdgeCounts.empty()))
259 return false;
260
261 BasicBlockMatchingAndInference::WeightInfo MatchWeight;
262 if (PropellerMatchBBID) {
263 MatchWeight = initWeightInfoByBBID(MF, CFG: *CFG);
264 } else {
265 MatchWeight = initWeightInfoByMatching(MF);
266 // If the ratio of the number of MBBs in matching to the total number of
267 // MBBs in the function is less than the threshold value, the processing
268 // should be abandoned.
269 if (static_cast<float>(MatchWeight.BlockWeights.size()) / MF.size() <
270 PropellerInferThreshold) {
271 return false;
272 }
273 }
274 generateWeightInfoByInference(MF, MatchWeight);
275 return false;
276}
277
278MachineFunctionPass *llvm::createBasicBlockMatchingAndInferencePass() {
279 return new BasicBlockMatchingAndInference();
280}
281