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
14#include "llvm/Analysis/FunctionPropertiesAnalysis.h"
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/Constants.h"
20#include "llvm/IR/Dominators.h"
21#include "llvm/IR/Instructions.h"
22#include "llvm/IR/IntrinsicInst.h"
23#include "llvm/Support/CommandLine.h"
24#include <deque>
25
26using namespace llvm;
27
28namespace llvm {
29cl::opt<bool> EnableDetailedFunctionProperties(
30 "enable-detailed-function-properties", cl::Hidden, cl::init(Val: false),
31 cl::desc("Whether or not to compute detailed function properties."));
32
33cl::opt<unsigned> BigBasicBlockInstructionThreshold(
34 "big-basic-block-instruction-threshold", cl::Hidden, cl::init(Val: 500),
35 cl::desc("The minimum number of instructions a basic block should contain "
36 "before being considered big."));
37
38cl::opt<unsigned> MediumBasicBlockInstructionThreshold(
39 "medium-basic-block-instruction-threshold", cl::Hidden, cl::init(Val: 15),
40 cl::desc("The minimum number of instructions a basic block should contain "
41 "before being considered medium-sized."));
42} // namespace llvm
43
44static cl::opt<unsigned> CallWithManyArgumentsThreshold(
45 "call-with-many-arguments-threshold", cl::Hidden, cl::init(Val: 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>(Val: BB.getTerminator())) {
53 if (BI->isConditional())
54 Ret += BI->getNumSuccessors();
55 } else if (const auto *SI = dyn_cast<SwitchInst>(Val: 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, Direction: +1);
68}
69
70void FunctionPropertiesInfo::updateForBB(const BasicBlock &BB,
71 int64_t Direction) {
72 assert(Direction == 1 || Direction == -1);
73 BasicBlockCount += Direction;
74 BlocksReachedFromConditionalInstruction +=
75 (Direction * getNrBlocksFromCond(BB));
76 for (const auto &I : BB) {
77 if (auto *CS = dyn_cast<CallBase>(Val: &I)) {
78 const auto *Callee = CS->getCalledFunction();
79 if (Callee && !Callee->isIntrinsic() && !Callee->isDeclaration())
80 DirectCallsToDefinedFunctions += Direction;
81 }
82 if (I.getOpcode() == Instruction::Load) {
83 LoadInstCount += Direction;
84 } else if (I.getOpcode() == Instruction::Store) {
85 StoreInstCount += Direction;
86 }
87 }
88 TotalInstructionCount += Direction * BB.sizeWithoutDebug();
89
90 if (EnableDetailedFunctionProperties) {
91 unsigned SuccessorCount = succ_size(BB: &BB);
92 if (SuccessorCount == 1)
93 BasicBlocksWithSingleSuccessor += Direction;
94 else if (SuccessorCount == 2)
95 BasicBlocksWithTwoSuccessors += Direction;
96 else if (SuccessorCount > 2)
97 BasicBlocksWithMoreThanTwoSuccessors += Direction;
98
99 unsigned PredecessorCount = pred_size(BB: &BB);
100 if (PredecessorCount == 1)
101 BasicBlocksWithSinglePredecessor += Direction;
102 else if (PredecessorCount == 2)
103 BasicBlocksWithTwoPredecessors += Direction;
104 else if (PredecessorCount > 2)
105 BasicBlocksWithMoreThanTwoPredecessors += Direction;
106
107 if (TotalInstructionCount > BigBasicBlockInstructionThreshold)
108 BigBasicBlocks += Direction;
109 else if (TotalInstructionCount > MediumBasicBlockInstructionThreshold)
110 MediumBasicBlocks += Direction;
111 else
112 SmallBasicBlocks += Direction;
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: &BB)) {
119 if (pred_size(BB: Successor) > 1)
120 CriticalEdgeCount += Direction;
121 }
122 }
123
124 ControlFlowEdgeCount += Direction * SuccessorCount;
125
126 if (const auto *BI = dyn_cast<BranchInst>(Val: BB.getTerminator())) {
127 if (!BI->isConditional())
128 UnconditionalBranchCount += Direction;
129 }
130
131 for (const Instruction &I : BB.instructionsWithoutDebug()) {
132 if (I.isCast())
133 CastInstructionCount += Direction;
134
135 if (I.getType()->isFloatTy())
136 FloatingPointInstructionCount += Direction;
137 else if (I.getType()->isIntegerTy())
138 IntegerInstructionCount += Direction;
139
140 if (isa<IntrinsicInst>(Val: I))
141 ++IntrinsicCount;
142
143 if (const auto *Call = dyn_cast<CallInst>(Val: &I)) {
144 if (Call->isIndirectCall())
145 IndirectCallCount += Direction;
146 else
147 DirectCallCount += Direction;
148
149 if (Call->getType()->isIntegerTy())
150 CallReturnsIntegerCount += Direction;
151 else if (Call->getType()->isFloatingPointTy())
152 CallReturnsFloatCount += Direction;
153 else if (Call->getType()->isPointerTy())
154 CallReturnsPointerCount += Direction;
155 else if (Call->getType()->isVectorTy()) {
156 if (Call->getType()->getScalarType()->isIntegerTy())
157 CallReturnsVectorIntCount += Direction;
158 else if (Call->getType()->getScalarType()->isFloatingPointTy())
159 CallReturnsVectorFloatCount += Direction;
160 else if (Call->getType()->getScalarType()->isPointerTy())
161 CallReturnsVectorPointerCount += Direction;
162 }
163
164 if (Call->arg_size() > CallWithManyArgumentsThreshold)
165 CallWithManyArgumentsCount += Direction;
166
167 for (const auto &Arg : Call->args()) {
168 if (Arg->getType()->isPointerTy()) {
169 CallWithPointerArgumentCount += Direction;
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(i: OperandIndex);
184 COUNT_OPERAND(GlobalValue)
185 COUNT_OPERAND(ConstantInt)
186 COUNT_OPERAND(ConstantFP)
187 COUNT_OPERAND(Constant)
188 COUNT_OPERAND(Instruction)
189 COUNT_OPERAND(BasicBlock)
190 COUNT_OPERAND(InlineAsm)
191 COUNT_OPERAND(Argument)
192
193 // We only get to this point if we haven't matched any of the other
194 // operand types.
195 UnknownOperandCount += Direction;
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);
207 TopLevelLoopCount = llvm::size(Range: LI);
208 MaxLoopDepth = 0;
209 std::deque<const Loop *> Worklist;
210 llvm::append_range(C&: Worklist, R: LI);
211 while (!Worklist.empty()) {
212 const auto *L = Worklist.front();
213 MaxLoopDepth =
214 std::max(a: MaxLoopDepth, b: static_cast<int64_t>(L->getLoopDepth()));
215 Worklist.pop_front();
216 llvm::append_range(C&: Worklist, R: L->getSubLoops());
217 }
218}
219
220FunctionPropertiesInfo FunctionPropertiesInfo::getFunctionPropertiesInfo(
221 Function &F, FunctionAnalysisManager &FAM) {
222 return getFunctionPropertiesInfo(F, DT: FAM.getResult<DominatorTreeAnalysis>(IR&: F),
223 LI: FAM.getResult<LoopAnalysis>(IR&: F));
224}
225
226FunctionPropertiesInfo FunctionPropertiesInfo::getFunctionPropertiesInfo(
227 const Function &F, const DominatorTree &DT, const LoopInfo &LI) {
228
229 FunctionPropertiesInfo FPI;
230 for (const auto &BB : F)
231 if (DT.isReachableFromEntry(A: &BB))
232 FPI.reIncludeBB(BB);
233 FPI.updateAggregateStats(F, LI);
234 return FPI;
235}
236
237void FunctionPropertiesInfo::print(raw_ostream &OS) const {
238#define PRINT_PROPERTY(PROP_NAME) OS << #PROP_NAME ": " << PROP_NAME << "\n";
239
240 PRINT_PROPERTY(BasicBlockCount)
241 PRINT_PROPERTY(BlocksReachedFromConditionalInstruction)
242 PRINT_PROPERTY(Uses)
243 PRINT_PROPERTY(DirectCallsToDefinedFunctions)
244 PRINT_PROPERTY(LoadInstCount)
245 PRINT_PROPERTY(StoreInstCount)
246 PRINT_PROPERTY(MaxLoopDepth)
247 PRINT_PROPERTY(TopLevelLoopCount)
248 PRINT_PROPERTY(TotalInstructionCount)
249
250 if (EnableDetailedFunctionProperties) {
251 PRINT_PROPERTY(BasicBlocksWithSingleSuccessor)
252 PRINT_PROPERTY(BasicBlocksWithTwoSuccessors)
253 PRINT_PROPERTY(BasicBlocksWithMoreThanTwoSuccessors)
254 PRINT_PROPERTY(BasicBlocksWithSinglePredecessor)
255 PRINT_PROPERTY(BasicBlocksWithTwoPredecessors)
256 PRINT_PROPERTY(BasicBlocksWithMoreThanTwoPredecessors)
257 PRINT_PROPERTY(BigBasicBlocks)
258 PRINT_PROPERTY(MediumBasicBlocks)
259 PRINT_PROPERTY(SmallBasicBlocks)
260 PRINT_PROPERTY(CastInstructionCount)
261 PRINT_PROPERTY(FloatingPointInstructionCount)
262 PRINT_PROPERTY(IntegerInstructionCount)
263 PRINT_PROPERTY(ConstantIntOperandCount)
264 PRINT_PROPERTY(ConstantFPOperandCount)
265 PRINT_PROPERTY(ConstantOperandCount)
266 PRINT_PROPERTY(InstructionOperandCount)
267 PRINT_PROPERTY(BasicBlockOperandCount)
268 PRINT_PROPERTY(GlobalValueOperandCount)
269 PRINT_PROPERTY(InlineAsmOperandCount)
270 PRINT_PROPERTY(ArgumentOperandCount)
271 PRINT_PROPERTY(UnknownOperandCount)
272 PRINT_PROPERTY(CriticalEdgeCount)
273 PRINT_PROPERTY(ControlFlowEdgeCount)
274 PRINT_PROPERTY(UnconditionalBranchCount)
275 PRINT_PROPERTY(IntrinsicCount)
276 PRINT_PROPERTY(DirectCallCount)
277 PRINT_PROPERTY(IndirectCallCount)
278 PRINT_PROPERTY(CallReturnsIntegerCount)
279 PRINT_PROPERTY(CallReturnsFloatCount)
280 PRINT_PROPERTY(CallReturnsPointerCount)
281 PRINT_PROPERTY(CallReturnsVectorIntCount)
282 PRINT_PROPERTY(CallReturnsVectorFloatCount)
283 PRINT_PROPERTY(CallReturnsVectorPointerCount)
284 PRINT_PROPERTY(CallWithManyArgumentsCount)
285 PRINT_PROPERTY(CallWithPointerArgumentCount)
286 }
287
288#undef PRINT_PROPERTY
289
290 OS << "\n";
291}
292
293AnalysisKey FunctionPropertiesAnalysis::Key;
294
295FunctionPropertiesInfo
296FunctionPropertiesAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
297 return FunctionPropertiesInfo::getFunctionPropertiesInfo(F, FAM);
298}
299
300PreservedAnalyses
301FunctionPropertiesPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
302 OS << "Printing analysis results of CFA for function "
303 << "'" << F.getName() << "':"
304 << "\n";
305 AM.getResult<FunctionPropertiesAnalysis>(IR&: F).print(OS);
306 return PreservedAnalyses::all();
307}
308
309FunctionPropertiesUpdater::FunctionPropertiesUpdater(
310 FunctionPropertiesInfo &FPI, CallBase &CB)
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(Ptr: &CallSiteBB);
320
321 // The caller's entry BB may change due to new alloca instructions.
322 LikelyToChangeBBs.insert(Ptr: &*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(I: succ_begin(BB: &CallSiteBB), E: succ_end(BB: &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>(Val: &CB)) {
337 const auto *UnwindDest = II->getUnwindDest();
338 Successors.insert(I: succ_begin(BB: UnwindDest), E: succ_end(BB: 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(V: &CallSiteBB);
347
348 for (const auto *BB : Successors)
349 LikelyToChangeBBs.insert(Ptr: 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: *BB, Direction: -1);
357}
358
359void FunctionPropertiesUpdater::finish(FunctionAnalysisManager &FAM) const {
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.
384 SetVector<const BasicBlock *> Reinclude;
385 SetVector<const BasicBlock *> Unreachable;
386 const auto &DT =
387 FAM.getResult<DominatorTreeAnalysis>(IR&: const_cast<Function &>(Caller));
388
389 if (&CallSiteBB != &*Caller.begin())
390 Reinclude.insert(X: &*Caller.begin());
391
392 // Distribute the successors to the 2 buckets.
393 for (const auto *Succ : Successors)
394 if (DT.isReachableFromEntry(A: Succ))
395 Reinclude.insert(X: Succ);
396 else
397 Unreachable.insert(X: 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(X: &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: *BB);
410 if (I >= IncludeSuccessorsMark)
411 Reinclude.insert(Start: succ_begin(BB), End: 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(BB: *U, Direction: -1);
423 for (const auto *Succ : successors(BB: U))
424 if (!DT.isReachableFromEntry(A: Succ))
425 Unreachable.insert(X: Succ);
426 }
427
428 const auto &LI = FAM.getResult<LoopAnalysis>(IR&: const_cast<Function &>(Caller));
429 FPI.updateAggregateStats(F: Caller, LI);
430}
431
432bool FunctionPropertiesUpdater::isUpdateValid(Function &F,
433 const FunctionPropertiesInfo &FPI,
434 FunctionAnalysisManager &FAM) {
435 DominatorTree DT(F);
436 LoopInfo LI(DT);
437 auto Fresh = FunctionPropertiesInfo::getFunctionPropertiesInfo(F, DT, LI);
438 return FPI == Fresh;
439}
440