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