LLVM 20.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"
16#include "llvm/Analysis/CFG.h"
17#include "llvm/IR/PassManager.h"
20
21namespace {
22using namespace llvm;
23SmallVector<const BasicBlock *, 8> findBBwithCalls(const Function &F,
24 bool IndirectCall = false) {
26
27 auto findCallInst = [&IndirectCall](const Instruction &I) {
28 if (auto Call = dyn_cast<CallBase>(&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(BB.instructionsWithoutDebug(), findCallInst))
36 BBs.emplace_back(&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
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>(CalledValue))
56 CallesNames.insert(DirectCall->getName());
57 };
58 for (auto &I : BB->instructionsWithoutDebug())
59 if (auto CI = dyn_cast<CallInst>(&I))
61
62 if (auto II = dyn_cast<InvokeInst>(BB->getTerminator()))
64}
65
67 return llvm::all_of(F, [](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
89
93
94 auto IBBs = findBBwithCalls(F);
95
96 if (IBBs.empty())
97 return std::nullopt;
98
100
101 for (const auto I : IBBs)
102 BBFreqs.push_back({I, BFI.getBlockFreq(I).getFrequency()});
103
104 assert(IBBs.size() == BBFreqs.size() && "BB Count Mismatch");
105
106 llvm::sort(BBFreqs, [](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(BBFreqs.size());
113
114 for (size_t i = 0; i < Topk; i++)
115 findCalles(BBFreqs[i].first, Calles);
116
117 assert(!Calles.empty() && "Running Analysis on Function with no calls?");
118
119 CallerAndCalles.insert({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.
133SequenceBBQuery::rearrangeBB(const Function &F, const BlockListTy &BBList) {
134 BlockListTy RearrangedBBSet;
135
136 for (auto &Block : F)
137 if (llvm::is_contained(BBList, &Block))
138 RearrangedBBSet.push_back(&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(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(CallerBlocks, AtBB))
161 BlockHint.CallerBlock = true;
162 VisitedBlocks.insert(std::make_pair(AtBB, BlockHint));
163 }
164
165 const_pred_iterator PIt = pred_begin(AtBB), EIt = pred_end(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(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(*PIt, AtBB) && !PredSkipNodes.count(*PIt))
184 traverseToEntryBlock(*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(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(CallerBlocks, AtBB))
204 BlockHint.CallerBlock = true;
205 VisitedBlocks.insert(std::make_pair(AtBB, BlockHint));
206 }
207
208 const_succ_iterator PIt = succ_begin(AtBB), EIt = succ_end(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(I.second);
220
221 for (; PIt != EIt; ++PIt)
222 if (BPI->isEdgeHot(AtBB, *PIt) && !SuccSkipNodes.count(*PIt))
223 traverseToExitBlock(*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.
231SequenceBBQuery::queryCFG(Function &F, const BlockListTy &CallerBlocks) {
232
233 BlockFreqInfoTy BBFreqs;
234 VisitedBlocksInfoTy VisitedBlocks;
235 BackEdgesInfoTy BackEdgesInfo;
236
240
242
243 llvm::FindFunctionBackedges(F, BackEdgesInfo);
244
245 for (const auto I : CallerBlocks)
246 BBFreqs.push_back({I, BFI.getBlockFreq(I).getFrequency()});
247
248 llvm::sort(BBFreqs, [](decltype(BBFreqs)::const_reference Bbf,
249 decltype(BBFreqs)::const_reference Bbs) {
250 return Bbf.second > Bbs.second;
251 });
252
254 HotBlocksRef =
255 HotBlocksRef.drop_back(BBFreqs.size() - getHottestBlocks(BBFreqs.size()));
256
259
260 // visit NHotBlocks,
261 // traverse upwards to entry
262 // traverse downwards to end.
263
264 for (auto I : HotBlocksRef) {
265 traverseToEntryBlock(I.first, CallerBlocks, BackEdgesInfo, BPI,
266 VisitedBlocks);
267 traverseToExitBlock(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(std::move(I.first));
275
276 return rearrangeBB(F, MinCallerBlocks);
277}
278
280 // reduce the number of lists!
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, CallerBlocks);
292 else
293 SequencedBlocks = queryCFG(F, CallerBlocks);
294
295 for (const auto *BB : SequencedBlocks)
296 findCalles(BB, Calles);
297
298 CallerAndCalles.insert({F.getName(), std::move(Calles)});
299 return CallerAndCalles;
300}
301
302} // namespace orc
303} // namespace llvm
basic Basic Alias true
This file defines the DenseMap class.
This header defines various interfaces for pass management in LLVM.
#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)
uint64_t IntrinsicInst * II
FunctionAnalysisManager FAM
PassBuilder PB(Machine, PassOpts->PTO, std::nullopt, &PIC)
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 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:253
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:429
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:410
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:61
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:250
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:489
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:239
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:1120
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:211
Implements a dense probed hash-table based set.
Definition: DenseSet.h:278
This class provides access to building LLVM's passes.
Definition: PassBuilder.h:105
void registerFunctionAnalyses(FunctionAnalysisManager &FAM)
Registers all available function analysis passes.
bool empty() const
Definition: SmallVector.h:81
size_t size() const
Definition: SmallVector.h:78
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:937
void push_back(const T &Elt)
Definition: SmallVector.h:413
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1196
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:213
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:95
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
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:1739
auto pred_end(const MachineBasicBlock *BB)
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:1746
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1664
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
auto pred_begin(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1903
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