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;
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
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 
69 bool SpeculateQuery::isStraightLine(const Function &F) {
70   return llvm::all_of(F.getBasicBlockList(), [](const BasicBlock &BB) {
71     return BB.getSingleSuccessor() != nullptr;
72   });
73 }
74 
75 // BlockFreqQuery Implementations
76 
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 
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 None;
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
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
136 SequenceBBQuery::rearrangeBB(const Function &F, const BlockListTy &BBList) {
137   BlockListTy RearrangedBBSet;
138 
139   for (auto &Block : F.getBasicBlockList())
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 
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 
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
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 
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 None;
292 
293   if (isStraightLine(F))
294     SequencedBlocks = rearrangeBB(F, CallerBlocks);
295   else
296     SequencedBlocks = queryCFG(F, CallerBlocks);
297 
298   for (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