LLVM 17.0.0git
SpeculateAnalyses.cpp
Go to the documentation of this file.
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
10#include "llvm/ADT/ArrayRef.h"
11#include "llvm/ADT/DenseMap.h"
12#include "llvm/ADT/STLExtras.h"
17#include "llvm/Analysis/CFG.h"
18#include "llvm/IR/PassManager.h"
21
22#include <algorithm>
23
24namespace {
25using namespace llvm;
26SmallVector<const BasicBlock *, 8> findBBwithCalls(const Function &F,
27 bool IndirectCall = false) {
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.
48namespace llvm {
49namespace orc {
50
51// Collect direct calls only
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))
64
65 if (auto II = dyn_cast<InvokeInst>(BB->getTerminator()))
67}
68
70 return llvm::all_of(F, [](const BasicBlock &BB) {
71 return BB.getSingleSuccessor() != nullptr;
72 });
73}
74
75// BlockFreqQuery Implementations
76
77size_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
92
96
97 auto IBBs = findBBwithCalls(F);
98
99 if (IBBs.empty())
100 return std::nullopt;
101
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
128std::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.
136SequenceBBQuery::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
148void 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
191void 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.
234SequenceBBQuery::queryCFG(Function &F, const BlockListTy &CallerBlocks) {
235
236 BlockFreqInfoTy BBFreqs;
237 VisitedBlocksInfoTy VisitedBlocks;
238 BackEdgesInfoTy BackEdgesInfo;
239
243
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
257 HotBlocksRef =
258 HotBlocksRef.drop_back(BBFreqs.size() - getHottestBlocks(BBFreqs.size()));
259
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
283 // reduce the number of lists!
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
basic Basic Alias true
This file defines the DenseMap class.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
static const Function * getCalledFunction(const Value *V, bool &IsNoBuiltin)
FunctionAnalysisManager FAM
PassBuilder PB(Machine, PassOpts->PTO, std::nullopt, &PIC)
This header defines various interfaces for pass management in LLVM.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Contains the Analyses and Result Interpretation to select likely functions to Speculatively compile b...
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:793
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=true) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
Definition: BasicBlock.cpp:103
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:314
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:127
Analysis pass which computes BlockFrequencyInfo.
Analysis pass which computes BranchProbabilityInfo.
Analysis providing branch probability information.
bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const
Test if an edge is hot relative to other out-edges of the Src.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1184
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
This class provides access to building LLVM's passes.
Definition: PassBuilder.h:100
void registerFunctionAnalyses(FunctionAnalysisManager &FAM)
Registers all available function analysis passes.
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:941
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
ResultTy operator()(Function &F)
ResultTy operator()(Function &F)
SmallVector< std::pair< const BasicBlock *, uint64_t >, 8 > BlockFreqInfoTy
DenseMap< const BasicBlock *, WalkDirection > VisitedBlocksInfoTy
SmallVector< std::pair< const BasicBlock *, const BasicBlock * >, 8 > BackEdgesInfoTy
SmallVector< const BasicBlock *, 8 > BlockListTy
std::optional< DenseMap< StringRef, DenseSet< StringRef > > > ResultTy
bool isStraightLine(const Function &F)
void findCalles(const BasicBlock *, DenseSet< StringRef > &)
Interfaces for registering analysis passes, producing common pass manager configurations,...
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1735
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1742
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1683
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:109
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1869
void FindFunctionBackedges(const Function &F, SmallVectorImpl< std::pair< const BasicBlock *, const BasicBlock * > > &Result)
Analyze the specified function to find all of the loop backedges in the function and return them.
Definition: CFG.cpp:34