LLVM 17.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"
18#include "llvm/IR/CFG.h"
19#include "llvm/IR/Dominators.h"
21#include <deque>
22
23using namespace llvm;
24
25namespace {
26int64_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
37int64_t getUses(const Function &F) {
38 return ((!F.hasLocalLinkage()) ? 1 : 0) + F.getNumUses();
39}
40} // namespace
41
42void FunctionPropertiesInfo::reIncludeBB(const BasicBlock &BB) {
43 updateForBB(BB, +1);
44}
45
46void 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
67void 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();
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 =
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.
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}
amdgpu Simplify well known AMD library false FunctionCallee Callee
static const Function * getParent(const Value *V)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Loop::LoopBounds::Direction Direction
Definition: LoopInfo.cpp:230
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
FunctionAnalysisManager FAM
@ SI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
This file implements a set that has insertion order iteration characteristics.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
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
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1186
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
FunctionPropertiesInfo run(Function &F, FunctionAnalysisManager &FAM)
int64_t BasicBlockCount
Number of basic blocks.
int64_t Uses
Number of uses of this function, plus 1 if the function is callable outside the module.
int64_t BlocksReachedFromConditionalInstruction
Number of blocks reached from a conditional instruction, or that are 'cases' of a SwitchInstr.
static FunctionPropertiesInfo getFunctionPropertiesInfo(const Function &F, FunctionAnalysisManager &FAM)
int64_t DirectCallsToDefinedFunctions
Number of direct calls made from this function to other functions defined in this module.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
void finish(FunctionAnalysisManager &FAM) const
FunctionPropertiesUpdater(FunctionPropertiesInfo &FPI, const CallBase &CB)
iterator begin()
Definition: Function.h:756
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1268
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
A vector that has set insertion semantics.
Definition: SetVector.h:51
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:88
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:152
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
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
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
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:1777
auto successors(const MachineBasicBlock *BB)
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
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2129
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
Direction
An enum for the direction of the loop.
Definition: LoopInfo.h:723