LLVM  14.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"
13 #include "llvm/ADT/SmallPtrSet.h"
14 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/Analysis/CFG.h"
18 #include "llvm/IR/PassManager.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) {
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
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.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 
90  DenseSet<StringRef> Calles;
92 
96 
97  auto IBBs = findBBwithCalls(F);
98 
99  if (IBBs.empty())
100  return None;
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
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.
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.
234 SequenceBBQuery::queryCFG(Function &F, const BlockListTy &CallerBlocks) {
235 
236  BlockFreqInfoTy BBFreqs;
237  VisitedBlocksInfoTy VisitedBlocks;
238  BackEdgesInfoTy BackEdgesInfo;
239 
240  PassBuilder PB;
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 
260  BranchProbabilityInfo *BPI =
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 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
llvm::SuccIterator
Definition: CFG.h:139
i
i
Definition: README.txt:29
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
PassBuilder.h
llvm::FindFunctionBackedges
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
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:779
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
llvm::Function
Definition: Function.h:61
llvm::orc::BlockFreqQuery::operator()
ResultTy operator()(Function &F)
Definition: SpeculateAnalyses.cpp:88
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
ErrorHandling.h
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
llvm::orc::SequenceBBQuery::VisitedBlocksInfoTy
DenseMap< const BasicBlock *, WalkDirection > VisitedBlocksInfoTy
Definition: SpeculateAnalyses.h:57
DenseMap.h
llvm::Optional
Definition: APInt.h:33
STLExtras.h
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::detail::DenseSetImpl::count
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
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::PseudoProbeType::IndirectCall
@ IndirectCall
llvm::BranchProbabilityAnalysis
Analysis pass which computes BranchProbabilityInfo.
Definition: BranchProbabilityInfo.h:414
llvm::all_of
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:1551
llvm::orc::SpeculateQuery::findCalles
void findCalles(const BasicBlock *, DenseSet< StringRef > &)
Definition: SpeculateAnalyses.cpp:52
llvm::BranchProbabilityInfo
Analysis providing branch probability information.
Definition: BranchProbabilityInfo.h:115
llvm::PassBuilder
This class provides access to building LLVM's passes.
Definition: PassBuilder.h:84
llvm::Instruction
Definition: Instruction.h:45
SmallPtrSet.h
SpeculateAnalyses.h
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:153
llvm::orc::SequenceBBQuery::BlockFreqInfoTy
SmallVector< std::pair< const BasicBlock *, uint64_t >, 8 > BlockFreqInfoTy
Definition: SpeculateAnalyses.h:62
llvm::BlockFrequencyAnalysis
Analysis pass which computes BlockFrequencyInfo.
Definition: BlockFrequencyInfo.h:112
llvm::None
const NoneType None
Definition: None.h:23
llvm::orc::SequenceBBQuery::BlockListTy
SmallVector< const BasicBlock *, 8 > BlockListTy
Definition: SpeculateAnalyses.h:58
getCalledFunction
static const Function * getCalledFunction(const Value *V, bool LookThroughBitCast, bool &IsNoBuiltin)
Definition: MemoryBuiltins.cpp:118
PB
PassBuilder PB(Machine, PassOpts->PTO, None, &PIC)
llvm::orc::SpeculateQuery::isStraightLine
bool isStraightLine(const Function &F)
Definition: SpeculateAnalyses.cpp:69
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::orc::SequenceBBQuery::BackEdgesInfoTy
SmallVector< std::pair< const BasicBlock *, const BasicBlock * >, 8 > BackEdgesInfoTy
Definition: SpeculateAnalyses.h:60
llvm::PassBuilder::registerFunctionAnalyses
void registerFunctionAnalyses(FunctionAnalysisManager &FAM)
Registers all available function analysis passes.
Definition: PassBuilder.cpp:415
BranchProbabilityInfo.h
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::succ_begin
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
llvm::detail::DenseSetImpl< ValueT, DenseMap< ValueT, detail::DenseSetEmpty, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::empty
bool empty() const
Definition: DenseSet.h:80
llvm::is_contained
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:1616
ArrayRef.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
CFG.h
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::any_of
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:1558
BlockFrequencyInfo.h
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:421
llvm::PredIterator
Definition: CFG.h:43
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::orc::SequenceBBQuery::operator()
ResultTy operator()(Function &F)
Definition: SpeculateAnalyses.cpp:282
llvm::pred_end
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:112
llvm::AnalysisManager::getCachedResult
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:798
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1492
PassManager.h
llvm::pred_begin
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
llvm::BranchProbabilityInfo::isEdgeHot
bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const
Test if an edge is hot relative to other out-edges of the Src.
Definition: BranchProbabilityInfo.cpp:1102
SmallVector.h
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1161
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1815
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:908
llvm::PseudoProbeType::DirectCall
@ DirectCall