1//===-- SpeculateAnalyses.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#include "llvm/ExecutionEngine/Orc/SpeculateAnalyses.h"
10#include "llvm/ADT/ArrayRef.h"
11#include "llvm/ADT/DenseMap.h"
12#include "llvm/ADT/STLExtras.h"
13#include "llvm/ADT/SmallVector.h"
14#include "llvm/Analysis/BlockFrequencyInfo.h"
15#include "llvm/Analysis/BranchProbabilityInfo.h"
16#include "llvm/Analysis/CFG.h"
17#include "llvm/IR/PassManager.h"
18#include "llvm/Passes/PassBuilder.h"
19#include "llvm/Support/ErrorHandling.h"
20
21namespace {
22using namespace llvm;
23SmallVector<const BasicBlock *, 8> findBBwithCalls(const Function &F,
24 bool IndirectCall = false) {
25 SmallVector<const BasicBlock *, 8> BBs;
26
27 auto findCallInst = [&IndirectCall](const Instruction &I) {
28 if (auto Call = dyn_cast<CallBase>(Val: &I))
29 if (!isa<PseudoProbeInst>(Val: Call))
30 return Call->isIndirectCall() ? IndirectCall : true;
31 return false;
32 };
33 for (auto &BB : F)
34 if (findCallInst(*BB.getTerminator()) || llvm::any_of(Range: BB, P: findCallInst))
35 BBs.emplace_back(Args: &BB);
36
37 return BBs;
38}
39} // namespace
40
41// Implementations of Queries shouldn't need to lock the resources
42// such as LLVMContext, each argument (function) has a non-shared LLVMContext
43// Plus, if Queries contain states necessary locking scheme should be provided.
44namespace llvm {
45namespace orc {
46
47// Collect direct calls only
48void SpeculateQuery::findCalles(const BasicBlock *BB,
49 DenseSet<StringRef> &CallesNames) {
50 assert(BB != nullptr && "Traversing Null BB to find calls?");
51
52 auto getCalledFunction = [&CallesNames](const CallBase *Call) {
53 auto CalledValue = Call->getCalledOperand()->stripPointerCasts();
54 if (auto DirectCall = dyn_cast<Function>(Val: CalledValue))
55 CallesNames.insert(V: DirectCall->getName());
56 };
57 for (auto &I : *BB)
58 if (auto CI = dyn_cast<CallInst>(Val: &I))
59 getCalledFunction(CI);
60
61 if (auto II = dyn_cast<InvokeInst>(Val: BB->getTerminator()))
62 getCalledFunction(II);
63}
64
65bool SpeculateQuery::isStraightLine(const Function &F) {
66 return llvm::all_of(Range: F, P: [](const BasicBlock &BB) {
67 return BB.getSingleSuccessor() != nullptr;
68 });
69}
70
71// BlockFreqQuery Implementations
72
73size_t BlockFreqQuery::numBBToGet(size_t numBB) {
74 // small CFG
75 if (numBB < 4)
76 return numBB;
77 // mid-size CFG
78 else if (numBB < 20)
79 return (numBB / 2);
80 else
81 return (numBB / 2) + (numBB / 4);
82}
83
84BlockFreqQuery::ResultTy BlockFreqQuery::operator()(Function &F) {
85 DenseMap<StringRef, DenseSet<StringRef>> CallerAndCalles;
86 DenseSet<StringRef> Calles;
87 SmallVector<std::pair<const BasicBlock *, uint64_t>, 8> BBFreqs;
88
89 PassBuilder PB;
90 FunctionAnalysisManager FAM;
91 PB.registerFunctionAnalyses(FAM);
92
93 auto IBBs = findBBwithCalls(F);
94
95 if (IBBs.empty())
96 return std::nullopt;
97
98 auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(IR&: F);
99
100 for (const auto I : IBBs)
101 BBFreqs.push_back(Elt: {I, BFI.getBlockFreq(BB: I).getFrequency()});
102
103 assert(IBBs.size() == BBFreqs.size() && "BB Count Mismatch");
104
105 llvm::sort(C&: BBFreqs, Comp: [](decltype(BBFreqs)::const_reference BBF,
106 decltype(BBFreqs)::const_reference BBS) {
107 return BBF.second > BBS.second ? true : false;
108 });
109
110 // ignoring number of direct calls in a BB
111 auto Topk = numBBToGet(numBB: BBFreqs.size());
112
113 for (size_t i = 0; i < Topk; i++)
114 findCalles(BB: BBFreqs[i].first, CallesNames&: Calles);
115
116 assert(!Calles.empty() && "Running Analysis on Function with no calls?");
117
118 CallerAndCalles.insert(KV: {F.getName(), std::move(Calles)});
119
120 return CallerAndCalles;
121}
122
123// SequenceBBQuery Implementation
124std::size_t SequenceBBQuery::getHottestBlocks(std::size_t TotalBlocks) {
125 if (TotalBlocks == 1)
126 return TotalBlocks;
127 return TotalBlocks / 2;
128}
129
130// FIXME : find good implementation.
131SequenceBBQuery::BlockListTy
132SequenceBBQuery::rearrangeBB(const Function &F, const BlockListTy &BBList) {
133 BlockListTy RearrangedBBSet;
134
135 for (auto &Block : F)
136 if (llvm::is_contained(Range: BBList, Element: &Block))
137 RearrangedBBSet.push_back(Elt: &Block);
138
139 assert(RearrangedBBSet.size() == BBList.size() &&
140 "BasicBlock missing while rearranging?");
141 return RearrangedBBSet;
142}
143
144void SequenceBBQuery::traverseToEntryBlock(const BasicBlock *AtBB,
145 const BlockListTy &CallerBlocks,
146 const BackEdgesInfoTy &BackEdgesInfo,
147 const BranchProbabilityInfo *BPI,
148 VisitedBlocksInfoTy &VisitedBlocks) {
149 auto Itr = VisitedBlocks.find(Val: AtBB);
150 if (Itr != VisitedBlocks.end()) { // already visited.
151 if (!Itr->second.Upward)
152 return;
153 Itr->second.Upward = false;
154 } else {
155 // Create hint for newly discoverd blocks.
156 WalkDirection BlockHint;
157 BlockHint.Upward = false;
158 // FIXME: Expensive Check
159 if (llvm::is_contained(Range: CallerBlocks, Element: AtBB))
160 BlockHint.CallerBlock = true;
161 VisitedBlocks.insert(KV: std::make_pair(x&: AtBB, y&: BlockHint));
162 }
163
164 const_pred_iterator PIt = pred_begin(BB: AtBB), EIt = pred_end(BB: AtBB);
165 // Move this check to top, when we have code setup to launch speculative
166 // compiles for function in entry BB, this triggers the speculative compiles
167 // before running the program.
168 if (PIt == EIt) // No Preds.
169 return;
170
171 DenseSet<const BasicBlock *> PredSkipNodes;
172
173 // Since we are checking for predecessor's backedges, this Block
174 // occurs in second position.
175 for (auto &I : BackEdgesInfo)
176 if (I.second == AtBB)
177 PredSkipNodes.insert(V: I.first);
178
179 // Skip predecessors which source of back-edges.
180 for (; PIt != EIt; ++PIt)
181 // checking EdgeHotness is cheaper
182 if (BPI->isEdgeHot(Src: *PIt, Dst: AtBB) && !PredSkipNodes.count(V: *PIt))
183 traverseToEntryBlock(AtBB: *PIt, CallerBlocks, BackEdgesInfo, BPI,
184 VisitedBlocks);
185}
186
187void SequenceBBQuery::traverseToExitBlock(const BasicBlock *AtBB,
188 const BlockListTy &CallerBlocks,
189 const BackEdgesInfoTy &BackEdgesInfo,
190 const BranchProbabilityInfo *BPI,
191 VisitedBlocksInfoTy &VisitedBlocks) {
192 auto Itr = VisitedBlocks.find(Val: AtBB);
193 if (Itr != VisitedBlocks.end()) { // already visited.
194 if (!Itr->second.Downward)
195 return;
196 Itr->second.Downward = false;
197 } else {
198 // Create hint for newly discoverd blocks.
199 WalkDirection BlockHint;
200 BlockHint.Downward = false;
201 // FIXME: Expensive Check
202 if (llvm::is_contained(Range: CallerBlocks, Element: AtBB))
203 BlockHint.CallerBlock = true;
204 VisitedBlocks.insert(KV: std::make_pair(x&: AtBB, y&: BlockHint));
205 }
206
207 const_succ_iterator PIt = succ_begin(BB: AtBB), EIt = succ_end(BB: AtBB);
208 if (PIt == EIt) // No succs.
209 return;
210
211 // If there are hot edges, then compute SuccSkipNodes.
212 DenseSet<const BasicBlock *> SuccSkipNodes;
213
214 // Since we are checking for successor's backedges, this Block
215 // occurs in first position.
216 for (auto &I : BackEdgesInfo)
217 if (I.first == AtBB)
218 SuccSkipNodes.insert(V: I.second);
219
220 for (; PIt != EIt; ++PIt)
221 if (BPI->isEdgeHot(Src: AtBB, Dst: *PIt) && !SuccSkipNodes.count(V: *PIt))
222 traverseToExitBlock(AtBB: *PIt, CallerBlocks, BackEdgesInfo, BPI,
223 VisitedBlocks);
224}
225
226// Get Block frequencies for blocks and take most frequently executed block,
227// walk towards the entry block from those blocks and discover the basic blocks
228// with call.
229SequenceBBQuery::BlockListTy
230SequenceBBQuery::queryCFG(Function &F, const BlockListTy &CallerBlocks) {
231
232 BlockFreqInfoTy BBFreqs;
233 VisitedBlocksInfoTy VisitedBlocks;
234 BackEdgesInfoTy BackEdgesInfo;
235
236 PassBuilder PB;
237 FunctionAnalysisManager FAM;
238 PB.registerFunctionAnalyses(FAM);
239
240 auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(IR&: F);
241
242 llvm::FindFunctionBackedges(F, Result&: BackEdgesInfo);
243
244 for (const auto I : CallerBlocks)
245 BBFreqs.push_back(Elt: {I, BFI.getBlockFreq(BB: I).getFrequency()});
246
247 llvm::sort(C&: BBFreqs, Comp: [](decltype(BBFreqs)::const_reference Bbf,
248 decltype(BBFreqs)::const_reference Bbs) {
249 return Bbf.second > Bbs.second;
250 });
251
252 ArrayRef<std::pair<const BasicBlock *, uint64_t>> HotBlocksRef(BBFreqs);
253 HotBlocksRef =
254 HotBlocksRef.drop_back(N: BBFreqs.size() - getHottestBlocks(TotalBlocks: BBFreqs.size()));
255
256 BranchProbabilityInfo *BPI =
257 FAM.getCachedResult<BranchProbabilityAnalysis>(IR&: F);
258
259 // visit NHotBlocks,
260 // traverse upwards to entry
261 // traverse downwards to end.
262
263 for (auto I : HotBlocksRef) {
264 traverseToEntryBlock(AtBB: I.first, CallerBlocks, BackEdgesInfo, BPI,
265 VisitedBlocks);
266 traverseToExitBlock(AtBB: I.first, CallerBlocks, BackEdgesInfo, BPI,
267 VisitedBlocks);
268 }
269
270 BlockListTy MinCallerBlocks;
271 for (auto &I : VisitedBlocks)
272 if (I.second.CallerBlock)
273 MinCallerBlocks.push_back(Elt: std::move(I.first));
274
275 return rearrangeBB(F, BBList: MinCallerBlocks);
276}
277
278SpeculateQuery::ResultTy SequenceBBQuery::operator()(Function &F) {
279 // reduce the number of lists!
280 DenseMap<StringRef, DenseSet<StringRef>> CallerAndCalles;
281 DenseSet<StringRef> Calles;
282 BlockListTy SequencedBlocks;
283 BlockListTy CallerBlocks;
284
285 CallerBlocks = findBBwithCalls(F);
286 if (CallerBlocks.empty())
287 return std::nullopt;
288
289 if (isStraightLine(F))
290 SequencedBlocks = rearrangeBB(F, BBList: CallerBlocks);
291 else
292 SequencedBlocks = queryCFG(F, CallerBlocks);
293
294 for (const auto *BB : SequencedBlocks)
295 findCalles(BB, CallesNames&: Calles);
296
297 CallerAndCalles.insert(KV: {F.getName(), std::move(Calles)});
298 return CallerAndCalles;
299}
300
301} // namespace orc
302} // namespace llvm
303