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