LLVM  16.0.0git
FunctionPropertiesAnalysis.cpp
Go to the documentation of this file.
1 //===- FunctionPropertiesAnalysis.cpp - Function Properties Analysis ------===//
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 // This file defines the FunctionPropertiesInfo and FunctionPropertiesAnalysis
10 // classes used to extract function properties.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/SetVector.h"
17 #include "llvm/Analysis/LoopInfo.h"
18 #include "llvm/IR/CFG.h"
19 #include "llvm/IR/Dominators.h"
20 #include "llvm/IR/Instructions.h"
21 #include <deque>
22 
23 using namespace llvm;
24 
25 namespace {
26 int64_t getNrBlocksFromCond(const BasicBlock &BB) {
27  int64_t Ret = 0;
28  if (const auto *BI = dyn_cast<BranchInst>(BB.getTerminator())) {
29  if (BI->isConditional())
30  Ret += BI->getNumSuccessors();
31  } else if (const auto *SI = dyn_cast<SwitchInst>(BB.getTerminator())) {
32  Ret += (SI->getNumCases() + (nullptr != SI->getDefaultDest()));
33  }
34  return Ret;
35 }
36 
37 int64_t getUses(const Function &F) {
38  return ((!F.hasLocalLinkage()) ? 1 : 0) + F.getNumUses();
39 }
40 } // namespace
41 
42 void FunctionPropertiesInfo::reIncludeBB(const BasicBlock &BB) {
43  updateForBB(BB, +1);
44 }
45 
46 void FunctionPropertiesInfo::updateForBB(const BasicBlock &BB,
47  int64_t Direction) {
48  assert(Direction == 1 || Direction == -1);
51  (Direction * getNrBlocksFromCond(BB));
52  for (const auto &I : BB) {
53  if (auto *CS = dyn_cast<CallBase>(&I)) {
54  const auto *Callee = CS->getCalledFunction();
55  if (Callee && !Callee->isIntrinsic() && !Callee->isDeclaration())
57  }
58  if (I.getOpcode() == Instruction::Load) {
60  } else if (I.getOpcode() == Instruction::Store) {
62  }
63  }
64  TotalInstructionCount += Direction * BB.sizeWithoutDebug();
65 }
66 
67 void FunctionPropertiesInfo::updateAggregateStats(const Function &F,
68  const LoopInfo &LI) {
69 
70  Uses = getUses(F);
72  MaxLoopDepth = 0;
73  std::deque<const Loop *> Worklist;
74  llvm::append_range(Worklist, LI);
75  while (!Worklist.empty()) {
76  const auto *L = Worklist.front();
77  MaxLoopDepth =
78  std::max(MaxLoopDepth, static_cast<int64_t>(L->getLoopDepth()));
79  Worklist.pop_front();
80  llvm::append_range(Worklist, L->getSubLoops());
81  }
82 }
83 
86 
88  // The const casts are due to the getResult API - there's no mutation of F.
89  const auto &LI = FAM.getResult<LoopAnalysis>(const_cast<Function &>(F));
90  const auto &DT =
91  FAM.getResult<DominatorTreeAnalysis>(const_cast<Function &>(F));
92  for (const auto &BB : F)
93  if (DT.isReachableFromEntry(&BB))
94  FPI.reIncludeBB(BB);
95  FPI.updateAggregateStats(F, LI);
96  return FPI;
97 }
98 
100  OS << "BasicBlockCount: " << BasicBlockCount << "\n"
101  << "BlocksReachedFromConditionalInstruction: "
103  << "Uses: " << Uses << "\n"
104  << "DirectCallsToDefinedFunctions: " << DirectCallsToDefinedFunctions
105  << "\n"
106  << "LoadInstCount: " << LoadInstCount << "\n"
107  << "StoreInstCount: " << StoreInstCount << "\n"
108  << "MaxLoopDepth: " << MaxLoopDepth << "\n"
109  << "TopLevelLoopCount: " << TopLevelLoopCount << "\n"
110  << "TotalInstructionCount: " << TotalInstructionCount << "\n\n";
111 }
112 
114 
118 }
119 
122  OS << "Printing analysis results of CFA for function "
123  << "'" << F.getName() << "':"
124  << "\n";
126  return PreservedAnalyses::all();
127 }
128 
130  FunctionPropertiesInfo &FPI, const CallBase &CB)
131  : FPI(FPI), CallSiteBB(*CB.getParent()), Caller(*CallSiteBB.getParent()) {
132  assert(isa<CallInst>(CB) || isa<InvokeInst>(CB));
133  // For BBs that are likely to change, we subtract from feature totals their
134  // contribution. Some features, like max loop counts or depths, are left
135  // invalid, as they will be updated post-inlining.
136  SmallPtrSet<const BasicBlock *, 4> LikelyToChangeBBs;
137  // The CB BB will change - it'll either be split or the callee's body (single
138  // BB) will be pasted in.
139  LikelyToChangeBBs.insert(&CallSiteBB);
140 
141  // The caller's entry BB may change due to new alloca instructions.
142  LikelyToChangeBBs.insert(&*Caller.begin());
143 
144  // The successors may become unreachable in the case of `invoke` inlining.
145  // We track successors separately, too, because they form a boundary, together
146  // with the CB BB ('Entry') between which the inlined callee will be pasted.
147  Successors.insert(succ_begin(&CallSiteBB), succ_end(&CallSiteBB));
148 
149  // Inlining only handles invoke and calls. If this is an invoke, and inlining
150  // it pulls another invoke, the original landing pad may get split, so as to
151  // share its content with other potential users. So the edge up to which we
152  // need to invalidate and then re-account BB data is the successors of the
153  // current landing pad. We can leave the current lp, too - if it doesn't get
154  // split, then it will be the place traversal stops. Either way, the
155  // discounted BBs will be checked if reachable and re-added.
156  if (const auto *II = dyn_cast<InvokeInst>(&CB)) {
157  const auto *UnwindDest = II->getUnwindDest();
158  Successors.insert(succ_begin(UnwindDest), succ_end(UnwindDest));
159  }
160 
161  // Exclude the CallSiteBB, if it happens to be its own successor (1-BB loop).
162  // We are only interested in BBs the graph moves past the callsite BB to
163  // define the frontier past which we don't want to re-process BBs. Including
164  // the callsite BB in this case would prematurely stop the traversal in
165  // finish().
166  Successors.erase(&CallSiteBB);
167 
168  for (const auto *BB : Successors)
169  LikelyToChangeBBs.insert(BB);
170 
171  // Commit the change. While some of the BBs accounted for above may play dual
172  // role - e.g. caller's entry BB may be the same as the callsite BB - set
173  // insertion semantics make sure we account them once. This needs to be
174  // followed in `finish`, too.
175  for (const auto *BB : LikelyToChangeBBs)
176  FPI.updateForBB(*BB, -1);
177 }
178 
180  // Update feature values from the BBs that were copied from the callee, or
181  // might have been modified because of inlining. The latter have been
182  // subtracted in the FunctionPropertiesUpdater ctor.
183  // There could be successors that were reached before but now are only
184  // reachable from elsewhere in the CFG.
185  // One example is the following diamond CFG (lines are arrows pointing down):
186  // A
187  // / \
188  // B C
189  // | |
190  // | D
191  // | |
192  // | E
193  // \ /
194  // F
195  // There's a call site in C that is inlined. Upon doing that, it turns out
196  // it expands to
197  // call void @llvm.trap()
198  // unreachable
199  // F isn't reachable from C anymore, but we did discount it when we set up
200  // FunctionPropertiesUpdater, so we need to re-include it here.
201  // At the same time, D and E were reachable before, but now are not anymore,
202  // so we need to leave D out (we discounted it at setup), and explicitly
203  // remove E.
205  SetVector<const BasicBlock *> Unreachable;
206  const auto &DT =
207  FAM.getResult<DominatorTreeAnalysis>(const_cast<Function &>(Caller));
208 
209  if (&CallSiteBB != &*Caller.begin())
210  Reinclude.insert(&*Caller.begin());
211 
212  // Distribute the successors to the 2 buckets.
213  for (const auto *Succ : Successors)
214  if (DT.isReachableFromEntry(Succ))
215  Reinclude.insert(Succ);
216  else
217  Unreachable.insert(Succ);
218 
219  // For reinclusion, we want to stop at the reachable successors, who are at
220  // the beginning of the worklist; but, starting from the callsite bb and
221  // ending at those successors, we also want to perform a traversal.
222  // IncludeSuccessorsMark is the index after which we include successors.
223  const auto IncludeSuccessorsMark = Reinclude.size();
224  bool CSInsertion = Reinclude.insert(&CallSiteBB);
225  (void)CSInsertion;
226  assert(CSInsertion);
227  for (size_t I = 0; I < Reinclude.size(); ++I) {
228  const auto *BB = Reinclude[I];
229  FPI.reIncludeBB(*BB);
230  if (I >= IncludeSuccessorsMark)
231  Reinclude.insert(succ_begin(BB), succ_end(BB));
232  }
233 
234  // For exclusion, we don't need to exclude the set of BBs that were successors
235  // before and are now unreachable, because we already did that at setup. For
236  // the rest, as long as a successor is unreachable, we want to explicitly
237  // exclude it.
238  const auto AlreadyExcludedMark = Unreachable.size();
239  for (size_t I = 0; I < Unreachable.size(); ++I) {
240  const auto *U = Unreachable[I];
241  if (I >= AlreadyExcludedMark)
242  FPI.updateForBB(*U, -1);
243  for (const auto *Succ : successors(U))
244  if (!DT.isReachableFromEntry(Succ))
245  Unreachable.insert(Succ);
246  }
247 
248  const auto &LI = FAM.getResult<LoopAnalysis>(const_cast<Function &>(Caller));
249  FPI.updateAggregateStats(Caller, LI);
251 }
llvm::FunctionPropertiesInfo::getFunctionPropertiesInfo
static FunctionPropertiesInfo getFunctionPropertiesInfo(const Function &F, FunctionAnalysisManager &FAM)
Definition: FunctionPropertiesAnalysis.cpp:84
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:774
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
llvm::Function
Definition: Function.h:60
llvm::SetVector::size
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
llvm::FunctionPropertiesPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: FunctionPropertiesAnalysis.cpp:121
llvm::FunctionPropertiesInfo::TopLevelLoopCount
int64_t TopLevelLoopCount
Definition: FunctionPropertiesAnalysis.h:75
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
llvm::SmallPtrSet< const BasicBlock *, 4 >
llvm::FunctionPropertiesAnalysis::run
FunctionPropertiesInfo run(Function &F, FunctionAnalysisManager &FAM)
Definition: FunctionPropertiesAnalysis.cpp:116
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::successors
auto successors(MachineBasicBlock *BB)
Definition: MachineSSAContext.h:29
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:119
STLExtras.h
llvm::FunctionPropertiesInfo::LoadInstCount
int64_t LoadInstCount
Definition: FunctionPropertiesAnalysis.h:66
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::FunctionPropertiesAnalysis::Key
static AnalysisKey Key
Definition: FunctionPropertiesAnalysis.h:86
SI
@ SI
Definition: SIInstrInfo.cpp:7966
llvm::FunctionPropertiesUpdater::finish
void finish(FunctionAnalysisManager &FAM) const
Definition: FunctionPropertiesAnalysis.cpp:179
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::Loop::LoopBounds::Direction
Direction
An enum for the direction of the loop.
Definition: LoopInfo.h:723
CFG.h
LoopInfo.h
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
I
#define I(x, y, z)
Definition: MD5.cpp:58
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
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::FunctionPropertiesInfo::print
void print(raw_ostream &OS) const
Definition: FunctionPropertiesAnalysis.cpp:99
llvm::SetVector::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::print
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
Definition: GCNRegPressure.cpp:138
llvm::size
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1715
llvm::FunctionPropertiesInfo::Uses
int64_t Uses
Number of uses of this function, plus 1 if the function is callable outside the module.
Definition: FunctionPropertiesAnalysis.h:59
llvm::FunctionPropertiesAnalysis
Definition: FunctionPropertiesAnalysis.h:82
llvm::LoopInfo
Definition: LoopInfo.h:1108
llvm::FunctionPropertiesInfo::MaxLoopDepth
int64_t MaxLoopDepth
Definition: FunctionPropertiesAnalysis.h:72
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:805
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2013
llvm::Function::begin
iterator begin()
Definition: Function.h:707
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:187
FunctionPropertiesAnalysis.h
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
Direction
Loop::LoopBounds::Direction Direction
Definition: LoopInfo.cpp:230
llvm::FunctionPropertiesInfo::BlocksReachedFromConditionalInstruction
int64_t BlocksReachedFromConditionalInstruction
Number of blocks reached from a conditional instruction, or that are 'cases' of a SwitchInstr.
Definition: FunctionPropertiesAnalysis.h:55
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
Instructions.h
llvm::FunctionPropertiesInfo::TotalInstructionCount
int64_t TotalInstructionCount
Definition: FunctionPropertiesAnalysis.h:78
Dominators.h
llvm::FunctionPropertiesInfo::BasicBlockCount
int64_t BasicBlockCount
Number of basic blocks.
Definition: FunctionPropertiesAnalysis.h:47
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1175
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPropertiesUpdater::FunctionPropertiesUpdater
FunctionPropertiesUpdater(FunctionPropertiesInfo &FPI, const CallBase &CB)
Definition: FunctionPropertiesAnalysis.cpp:129
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
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
llvm::FunctionPropertiesInfo
Definition: FunctionPropertiesAnalysis.h:26
llvm::FunctionPropertiesInfo::StoreInstCount
int64_t StoreInstCount
Definition: FunctionPropertiesAnalysis.h:69
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1268
SetVector.h
llvm::FunctionPropertiesInfo::DirectCallsToDefinedFunctions
int64_t DirectCallsToDefinedFunctions
Number of direct calls made from this function to other functions defined in this module.
Definition: FunctionPropertiesAnalysis.h:63
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365