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