LLVM 19.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/Constants.h"
20#include "llvm/IR/Dominators.h"
24#include <deque>
25
26using namespace llvm;
27
28namespace llvm {
30 "enable-detailed-function-properties", cl::Hidden, cl::init(false),
31 cl::desc("Whether or not to compute detailed function properties."));
32
34 "big-basic-block-instruction-threshold", cl::Hidden, cl::init(500),
35 cl::desc("The minimum number of instructions a basic block should contain "
36 "before being considered big."));
37
39 "medium-basic-block-instruction-threshold", cl::Hidden, cl::init(15),
40 cl::desc("The minimum number of instructions a basic block should contain "
41 "before being considered medium-sized."));
42}
43
45 "call-with-many-arguments-threshold", cl::Hidden, cl::init(4),
46 cl::desc("The minimum number of arguments a function call must have before "
47 "it is considered having many arguments."));
48
49namespace {
50int64_t getNrBlocksFromCond(const BasicBlock &BB) {
51 int64_t Ret = 0;
52 if (const auto *BI = dyn_cast<BranchInst>(BB.getTerminator())) {
53 if (BI->isConditional())
54 Ret += BI->getNumSuccessors();
55 } else if (const auto *SI = dyn_cast<SwitchInst>(BB.getTerminator())) {
56 Ret += (SI->getNumCases() + (nullptr != SI->getDefaultDest()));
57 }
58 return Ret;
59}
60
61int64_t getUses(const Function &F) {
62 return ((!F.hasLocalLinkage()) ? 1 : 0) + F.getNumUses();
63}
64} // namespace
65
66void FunctionPropertiesInfo::reIncludeBB(const BasicBlock &BB) {
67 updateForBB(BB, +1);
68}
69
70void FunctionPropertiesInfo::updateForBB(const BasicBlock &BB,
71 int64_t Direction) {
72 assert(Direction == 1 || Direction == -1);
75 (Direction * getNrBlocksFromCond(BB));
76 for (const auto &I : BB) {
77 if (auto *CS = dyn_cast<CallBase>(&I)) {
78 const auto *Callee = CS->getCalledFunction();
79 if (Callee && !Callee->isIntrinsic() && !Callee->isDeclaration())
81 }
82 if (I.getOpcode() == Instruction::Load) {
84 } else if (I.getOpcode() == Instruction::Store) {
86 }
87 }
88 TotalInstructionCount += Direction * BB.sizeWithoutDebug();
89
91 unsigned SuccessorCount = succ_size(&BB);
92 if (SuccessorCount == 1)
94 else if (SuccessorCount == 2)
96 else if (SuccessorCount > 2)
98
99 unsigned PredecessorCount = pred_size(&BB);
100 if (PredecessorCount == 1)
102 else if (PredecessorCount == 2)
104 else if (PredecessorCount > 2)
106
111 else
113
114 // Calculate critical edges by looking through all successors of a basic
115 // block that has multiple successors and finding ones that have multiple
116 // predecessors, which represent critical edges.
117 if (SuccessorCount > 1) {
118 for (const auto *Successor : successors(&BB)) {
119 if (pred_size(Successor) > 1)
121 }
122 }
123
124 ControlFlowEdgeCount += Direction * SuccessorCount;
125
126 if (const auto *BI = dyn_cast<BranchInst>(BB.getTerminator())) {
127 if (!BI->isConditional())
129 }
130
131 for (const Instruction &I : BB.instructionsWithoutDebug()) {
132 if (I.isCast())
134
135 if (I.getType()->isFloatTy())
137 else if (I.getType()->isIntegerTy())
139
140 if (isa<IntrinsicInst>(I))
142
143 if (const auto *Call = dyn_cast<CallInst>(&I)) {
144 if (Call->isIndirectCall())
146 else
148
149 if (Call->getType()->isIntegerTy())
151 else if (Call->getType()->isFloatingPointTy())
153 else if (Call->getType()->isPointerTy())
155 else if (Call->getType()->isVectorTy()) {
156 if (Call->getType()->getScalarType()->isIntegerTy())
158 else if (Call->getType()->getScalarType()->isFloatingPointTy())
160 else if (Call->getType()->getScalarType()->isPointerTy())
162 }
163
164 if (Call->arg_size() > CallWithManyArgumentsThreshold)
166
167 for (const auto &Arg : Call->args()) {
168 if (Arg->getType()->isPointerTy()) {
170 break;
171 }
172 }
173 }
174
175#define COUNT_OPERAND(OPTYPE) \
176 if (isa<OPTYPE>(Operand)) { \
177 OPTYPE##OperandCount += Direction; \
178 continue; \
179 }
180
181 for (unsigned int OperandIndex = 0; OperandIndex < I.getNumOperands();
182 ++OperandIndex) {
183 Value *Operand = I.getOperand(OperandIndex);
192
193 // We only get to this point if we haven't matched any of the other
194 // operand types.
196 }
197
198#undef CHECK_OPERAND
199 }
200 }
201}
202
203void FunctionPropertiesInfo::updateAggregateStats(const Function &F,
204 const LoopInfo &LI) {
205
206 Uses = getUses(F);
208 MaxLoopDepth = 0;
209 std::deque<const Loop *> Worklist;
210 llvm::append_range(Worklist, LI);
211 while (!Worklist.empty()) {
212 const auto *L = Worklist.front();
214 std::max(MaxLoopDepth, static_cast<int64_t>(L->getLoopDepth()));
215 Worklist.pop_front();
216 llvm::append_range(Worklist, L->getSubLoops());
217 }
218}
219
224}
225
227 const Function &F, const DominatorTree &DT, const LoopInfo &LI) {
228
230 for (const auto &BB : F)
231 if (DT.isReachableFromEntry(&BB))
232 FPI.reIncludeBB(BB);
233 FPI.updateAggregateStats(F, LI);
234 return FPI;
235}
236
238#define PRINT_PROPERTY(PROP_NAME) OS << #PROP_NAME ": " << PROP_NAME << "\n";
239
249
286 }
287
288#undef PRINT_PROPERTY
289
290 OS << "\n";
291}
292
294
298}
299
302 OS << "Printing analysis results of CFA for function "
303 << "'" << F.getName() << "':"
304 << "\n";
306 return PreservedAnalyses::all();
307}
308
311 : FPI(FPI), CallSiteBB(*CB.getParent()), Caller(*CallSiteBB.getParent()) {
312 assert(isa<CallInst>(CB) || isa<InvokeInst>(CB));
313 // For BBs that are likely to change, we subtract from feature totals their
314 // contribution. Some features, like max loop counts or depths, are left
315 // invalid, as they will be updated post-inlining.
316 SmallPtrSet<const BasicBlock *, 4> LikelyToChangeBBs;
317 // The CB BB will change - it'll either be split or the callee's body (single
318 // BB) will be pasted in.
319 LikelyToChangeBBs.insert(&CallSiteBB);
320
321 // The caller's entry BB may change due to new alloca instructions.
322 LikelyToChangeBBs.insert(&*Caller.begin());
323
324 // The successors may become unreachable in the case of `invoke` inlining.
325 // We track successors separately, too, because they form a boundary, together
326 // with the CB BB ('Entry') between which the inlined callee will be pasted.
327 Successors.insert(succ_begin(&CallSiteBB), succ_end(&CallSiteBB));
328
329 // Inlining only handles invoke and calls. If this is an invoke, and inlining
330 // it pulls another invoke, the original landing pad may get split, so as to
331 // share its content with other potential users. So the edge up to which we
332 // need to invalidate and then re-account BB data is the successors of the
333 // current landing pad. We can leave the current lp, too - if it doesn't get
334 // split, then it will be the place traversal stops. Either way, the
335 // discounted BBs will be checked if reachable and re-added.
336 if (const auto *II = dyn_cast<InvokeInst>(&CB)) {
337 const auto *UnwindDest = II->getUnwindDest();
338 Successors.insert(succ_begin(UnwindDest), succ_end(UnwindDest));
339 }
340
341 // Exclude the CallSiteBB, if it happens to be its own successor (1-BB loop).
342 // We are only interested in BBs the graph moves past the callsite BB to
343 // define the frontier past which we don't want to re-process BBs. Including
344 // the callsite BB in this case would prematurely stop the traversal in
345 // finish().
346 Successors.erase(&CallSiteBB);
347
348 for (const auto *BB : Successors)
349 LikelyToChangeBBs.insert(BB);
350
351 // Commit the change. While some of the BBs accounted for above may play dual
352 // role - e.g. caller's entry BB may be the same as the callsite BB - set
353 // insertion semantics make sure we account them once. This needs to be
354 // followed in `finish`, too.
355 for (const auto *BB : LikelyToChangeBBs)
356 FPI.updateForBB(*BB, -1);
357}
358
360 // Update feature values from the BBs that were copied from the callee, or
361 // might have been modified because of inlining. The latter have been
362 // subtracted in the FunctionPropertiesUpdater ctor.
363 // There could be successors that were reached before but now are only
364 // reachable from elsewhere in the CFG.
365 // One example is the following diamond CFG (lines are arrows pointing down):
366 // A
367 // / \
368 // B C
369 // | |
370 // | D
371 // | |
372 // | E
373 // \ /
374 // F
375 // There's a call site in C that is inlined. Upon doing that, it turns out
376 // it expands to
377 // call void @llvm.trap()
378 // unreachable
379 // F isn't reachable from C anymore, but we did discount it when we set up
380 // FunctionPropertiesUpdater, so we need to re-include it here.
381 // At the same time, D and E were reachable before, but now are not anymore,
382 // so we need to leave D out (we discounted it at setup), and explicitly
383 // remove E.
386 const auto &DT =
387 FAM.getResult<DominatorTreeAnalysis>(const_cast<Function &>(Caller));
388
389 if (&CallSiteBB != &*Caller.begin())
390 Reinclude.insert(&*Caller.begin());
391
392 // Distribute the successors to the 2 buckets.
393 for (const auto *Succ : Successors)
394 if (DT.isReachableFromEntry(Succ))
395 Reinclude.insert(Succ);
396 else
397 Unreachable.insert(Succ);
398
399 // For reinclusion, we want to stop at the reachable successors, who are at
400 // the beginning of the worklist; but, starting from the callsite bb and
401 // ending at those successors, we also want to perform a traversal.
402 // IncludeSuccessorsMark is the index after which we include successors.
403 const auto IncludeSuccessorsMark = Reinclude.size();
404 bool CSInsertion = Reinclude.insert(&CallSiteBB);
405 (void)CSInsertion;
406 assert(CSInsertion);
407 for (size_t I = 0; I < Reinclude.size(); ++I) {
408 const auto *BB = Reinclude[I];
409 FPI.reIncludeBB(*BB);
410 if (I >= IncludeSuccessorsMark)
411 Reinclude.insert(succ_begin(BB), succ_end(BB));
412 }
413
414 // For exclusion, we don't need to exclude the set of BBs that were successors
415 // before and are now unreachable, because we already did that at setup. For
416 // the rest, as long as a successor is unreachable, we want to explicitly
417 // exclude it.
418 const auto AlreadyExcludedMark = Unreachable.size();
419 for (size_t I = 0; I < Unreachable.size(); ++I) {
420 const auto *U = Unreachable[I];
421 if (I >= AlreadyExcludedMark)
422 FPI.updateForBB(*U, -1);
423 for (const auto *Succ : successors(U))
424 if (!DT.isReachableFromEntry(Succ))
425 Unreachable.insert(Succ);
426 }
427
428 const auto &LI = FAM.getResult<LoopAnalysis>(const_cast<Function &>(Caller));
429 FPI.updateAggregateStats(Caller, LI);
430}
431
432bool FunctionPropertiesUpdater::isUpdateValid(Function &F,
433 const FunctionPropertiesInfo &FPI,
435 DominatorTree DT(F);
436 LoopInfo LI(DT);
438 return FPI == Fresh;
439}
static const Function * getParent(const Value *V)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
#define PRINT_PROPERTY(PROP_NAME)
static cl::opt< unsigned > CallWithManyArgumentsThreshold("call-with-many-arguments-threshold", cl::Hidden, cl::init(4), cl::desc("The minimum number of arguments a function call must have before " "it is considered having many arguments."))
#define COUNT_OPERAND(OPTYPE)
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
uint64_t IntrinsicInst * II
FunctionAnalysisManager FAM
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:321
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:473
This class represents an incoming formal argument to a Function.
Definition: Argument.h:31
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
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:221
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1494
ConstantFP - Floating Point Values [float, double].
Definition: Constants.h:269
This is the shared class of boolean and integer constants.
Definition: Constants.h:81
This is an important base class in LLVM.
Definition: Constant.h:41
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:321
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, const DominatorTree &DT, const LoopInfo &LI)
int64_t DirectCallsToDefinedFunctions
Number of direct calls made from this function to other functions defined in this module.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
FunctionPropertiesUpdater(FunctionPropertiesInfo &FPI, CallBase &CB)
void finish(FunctionAnalysisManager &FAM) const
iterator begin()
Definition: Function.h:806
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:566
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
A vector that has set insertion semantics.
Definition: SetVector.h:57
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:98
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
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:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
LLVM Value Representation.
Definition: Value.h:74
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:1680
auto successors(const MachineBasicBlock *BB)
cl::opt< bool > EnableDetailedFunctionProperties("enable-detailed-function-properties", cl::Hidden, cl::init(false), cl::desc("Whether or not to compute detailed function properties."))
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition: STLExtras.h:2067
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
cl::opt< unsigned > BigBasicBlockInstructionThreshold("big-basic-block-instruction-threshold", cl::Hidden, cl::init(500), cl::desc("The minimum number of instructions a basic block should contain " "before being considered big."))
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
cl::opt< unsigned > MediumBasicBlockInstructionThreshold("medium-basic-block-instruction-threshold", cl::Hidden, cl::init(15), cl::desc("The minimum number of instructions a basic block should contain " "before being considered medium-sized."))
unsigned succ_size(const MachineBasicBlock *BB)
unsigned pred_size(const MachineBasicBlock *BB)
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:26
Direction
An enum for the direction of the loop.
Definition: LoopInfo.h:220