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/ADT/Statistic.h"
18#include "llvm/Analysis/LoopInfo.h"
19#include "llvm/IR/CFG.h"
20#include "llvm/IR/Constants.h"
21#include "llvm/IR/Dominators.h"
22#include "llvm/IR/Instructions.h"
23#include "llvm/IR/IntrinsicInst.h"
24#include "llvm/Support/CommandLine.h"
25#include "llvm/Support/Compiler.h"
26#include <deque>
27
28using namespace llvm;
29
30#define DEBUG_TYPE "func-properties-stats"
31
32#define FUNCTION_PROPERTY(Name, Description) \
33 STATISTIC(Num##Name, Description); \
34 STATISTIC(Num##Name##PreOptimization, Description " (before " \
35 "optimizations)");
36#define DETAILED_FUNCTION_PROPERTY(Name, Description) \
37 STATISTIC(Num##Name, Description); \
38 STATISTIC(Num##Name##PreOptimization, Description " (before " \
39 "optimizations)");
40#include "llvm/IR/FunctionProperties.def"
41
42namespace llvm {
43LLVM_ABI cl::opt<bool> EnableDetailedFunctionProperties(
44 "enable-detailed-function-properties", cl::Hidden, cl::init(Val: false),
45 cl::desc("Whether or not to compute detailed function properties."));
46
47static cl::opt<unsigned> BigBasicBlockInstructionThreshold(
48 "big-basic-block-instruction-threshold", cl::Hidden, cl::init(Val: 500),
49 cl::desc("The minimum number of instructions a basic block should contain "
50 "before being considered big."));
51
52static cl::opt<unsigned> MediumBasicBlockInstructionThreshold(
53 "medium-basic-block-instruction-threshold", cl::Hidden, cl::init(Val: 15),
54 cl::desc("The minimum number of instructions a basic block should contain "
55 "before being considered medium-sized."));
56} // namespace llvm
57
58static cl::opt<unsigned> CallWithManyArgumentsThreshold(
59 "call-with-many-arguments-threshold", cl::Hidden, cl::init(Val: 4),
60 cl::desc("The minimum number of arguments a function call must have before "
61 "it is considered having many arguments."));
62
63namespace {
64int64_t getNumBlocksFromCond(const BasicBlock &BB) {
65 int64_t Ret = 0;
66 if (const auto *BI = dyn_cast<CondBrInst>(Val: BB.getTerminator())) {
67 Ret += BI->getNumSuccessors();
68 } else if (const auto *SI = dyn_cast<SwitchInst>(Val: BB.getTerminator())) {
69 Ret += (SI->getNumCases() + (nullptr != SI->getDefaultDest()));
70 }
71 return Ret;
72}
73
74int64_t getUses(const Function &F) {
75 return ((!F.hasLocalLinkage()) ? 1 : 0) + F.getNumUses();
76}
77} // namespace
78
79void FunctionPropertiesInfo::reIncludeBB(const BasicBlock &BB) {
80 updateForBB(BB, Direction: +1);
81}
82
83void FunctionPropertiesInfo::updateForBB(const BasicBlock &BB,
84 int64_t Direction) {
85 assert(Direction == 1 || Direction == -1);
86 BasicBlockCount += Direction;
87 BlocksReachedFromConditionalInstruction +=
88 (Direction * getNumBlocksFromCond(BB));
89 for (const auto &I : BB) {
90 if (auto *CS = dyn_cast<CallBase>(Val: &I)) {
91 const auto *Callee = CS->getCalledFunction();
92 if (Callee && !Callee->isIntrinsic() && !Callee->isDeclaration())
93 DirectCallsToDefinedFunctions += Direction;
94 }
95 if (I.getOpcode() == Instruction::Load) {
96 LoadInstCount += Direction;
97 } else if (I.getOpcode() == Instruction::Store) {
98 StoreInstCount += Direction;
99 }
100 }
101 TotalInstructionCount += Direction * BB.size();
102
103 if (EnableDetailedFunctionProperties) {
104 unsigned SuccessorCount = succ_size(BB: &BB);
105 if (SuccessorCount == 1)
106 BasicBlocksWithSingleSuccessor += Direction;
107 else if (SuccessorCount == 2)
108 BasicBlocksWithTwoSuccessors += Direction;
109 else if (SuccessorCount > 2)
110 BasicBlocksWithMoreThanTwoSuccessors += Direction;
111
112 if (BB.hasNPredecessors(N: 1))
113 BasicBlocksWithSinglePredecessor += Direction;
114 else if (BB.hasNPredecessors(N: 2))
115 BasicBlocksWithTwoPredecessors += Direction;
116 else if (BB.hasNPredecessorsOrMore(N: 3))
117 BasicBlocksWithMoreThanTwoPredecessors += Direction;
118
119 if (TotalInstructionCount > BigBasicBlockInstructionThreshold)
120 BigBasicBlocks += Direction;
121 else if (TotalInstructionCount > MediumBasicBlockInstructionThreshold)
122 MediumBasicBlocks += Direction;
123 else
124 SmallBasicBlocks += Direction;
125
126 // Calculate critical edges by looking through all successors of a basic
127 // block that has multiple successors and finding ones that have multiple
128 // predecessors, which represent critical edges.
129 if (SuccessorCount > 1) {
130 for (const auto *Successor : successors(BB: &BB)) {
131 if (Successor->hasNPredecessorsOrMore(N: 2))
132 CriticalEdgeCount += Direction;
133 }
134 }
135
136 ControlFlowEdgeCount += Direction * SuccessorCount;
137
138 const Instruction *TI = BB.getTerminator();
139 if (isa<UncondBrInst>(Val: TI)) {
140 BranchInstructionCount += Direction;
141 BranchSuccessorCount += Direction;
142 UnconditionalBranchCount += Direction;
143 } else if (isa<CondBrInst>(Val: TI)) {
144 BranchInstructionCount += Direction;
145 BranchSuccessorCount += Direction * 2;
146 ConditionalBranchCount += Direction;
147 } else if (const auto *SI = dyn_cast<SwitchInst>(Val: TI)) {
148 SwitchInstructionCount += Direction;
149 SwitchSuccessorCount += Direction * SI->getNumSuccessors();
150 }
151
152 for (const Instruction &I : BB) {
153 if (I.isCast())
154 CastInstructionCount += Direction;
155
156 if (I.getType()->isFloatTy())
157 FloatingPointInstructionCount += Direction;
158 else if (I.getType()->isIntegerTy())
159 IntegerInstructionCount += Direction;
160
161 if (isa<IntrinsicInst>(Val: I))
162 ++IntrinsicCount;
163
164 if (const auto *Call = dyn_cast<CallInst>(Val: &I)) {
165 if (Call->doesNotReturn())
166 NoReturnCallCount += Direction;
167
168 if (Call->isIndirectCall())
169 IndirectCallCount += Direction;
170 else
171 DirectCallCount += Direction;
172
173 if (Call->getType()->isIntegerTy())
174 CallReturnsIntegerCount += Direction;
175 else if (Call->getType()->isFloatingPointTy())
176 CallReturnsFloatCount += Direction;
177 else if (Call->getType()->isPointerTy())
178 CallReturnsPointerCount += Direction;
179 else if (Call->getType()->isVectorTy()) {
180 if (Call->getType()->getScalarType()->isIntegerTy())
181 CallReturnsVectorIntCount += Direction;
182 else if (Call->getType()->getScalarType()->isFloatingPointTy())
183 CallReturnsVectorFloatCount += Direction;
184 else if (Call->getType()->getScalarType()->isPointerTy())
185 CallReturnsVectorPointerCount += Direction;
186 }
187
188 if (Call->arg_size() > CallWithManyArgumentsThreshold)
189 CallWithManyArgumentsCount += Direction;
190
191 for (const auto &Arg : Call->args()) {
192 if (Arg->getType()->isPointerTy()) {
193 CallWithPointerArgumentCount += Direction;
194 break;
195 }
196 }
197 }
198
199#define COUNT_OPERAND(OPTYPE) \
200 if (isa<OPTYPE>(Operand)) { \
201 OPTYPE##OperandCount += Direction; \
202 continue; \
203 }
204
205 for (unsigned int OperandIndex = 0; OperandIndex < I.getNumOperands();
206 ++OperandIndex) {
207 Value *Operand = I.getOperand(i: OperandIndex);
208 COUNT_OPERAND(GlobalValue)
209 COUNT_OPERAND(ConstantInt)
210 COUNT_OPERAND(ConstantFP)
211 COUNT_OPERAND(Constant)
212 COUNT_OPERAND(Instruction)
213 COUNT_OPERAND(BasicBlock)
214 COUNT_OPERAND(InlineAsm)
215 COUNT_OPERAND(Argument)
216
217 // We only get to this point if we haven't matched any of the other
218 // operand types.
219 UnknownOperandCount += Direction;
220 }
221
222#undef CHECK_OPERAND
223 }
224 }
225
226 if (IR2VecVocab) {
227 // We instantiate the IR2Vec embedder each time, as having an unique
228 // pointer to the embedder as member of the class would make it
229 // non-copyable. Instantiating the embedder in itself is not costly.
230 auto Embedder = ir2vec::Embedder::create(Mode: IR2VecKind::Symbolic,
231 F: *BB.getParent(), Vocab: *IR2VecVocab);
232 if (!Embedder) {
233 BB.getContext().emitError(ErrorStr: "Error creating IR2Vec embeddings");
234 return;
235 }
236 const auto &BBEmbedding = Embedder->getBBVector(BB);
237 // Subtract BBEmbedding from Function embedding if the direction is -1,
238 // and add it if the direction is +1.
239 if (Direction == -1)
240 FunctionEmbedding -= BBEmbedding;
241 else
242 FunctionEmbedding += BBEmbedding;
243 }
244}
245
246void FunctionPropertiesInfo::updateAggregateStats(const Function &F,
247 const LoopInfo &LI) {
248
249 Uses = getUses(F);
250 TopLevelLoopCount = llvm::size(Range: LI);
251 MaxLoopDepth = 0;
252 std::deque<const Loop *> Worklist;
253 llvm::append_range(C&: Worklist, R: LI);
254 while (!Worklist.empty()) {
255 const auto *L = Worklist.front();
256 MaxLoopDepth =
257 std::max(a: MaxLoopDepth, b: static_cast<int64_t>(L->getLoopDepth()));
258 Worklist.pop_front();
259 llvm::append_range(C&: Worklist, R: L->getSubLoops());
260 }
261}
262
263FunctionPropertiesInfo FunctionPropertiesInfo::getFunctionPropertiesInfo(
264 Function &F, FunctionAnalysisManager &FAM) {
265 // We use the cached result of the IR2VecVocabAnalysis run by
266 // InlineAdvisorAnalysis. If the IR2VecVocabAnalysis is not run, we don't
267 // use IR2Vec embeddings.
268 auto Vocabulary = FAM.getResult<ModuleAnalysisManagerFunctionProxy>(IR&: F)
269 .getCachedResult<IR2VecVocabAnalysis>(IR&: *F.getParent());
270 return getFunctionPropertiesInfo(F, DT: FAM.getResult<DominatorTreeAnalysis>(IR&: F),
271 LI: FAM.getResult<LoopAnalysis>(IR&: F), Vocabulary);
272}
273
274FunctionPropertiesInfo FunctionPropertiesInfo::getFunctionPropertiesInfo(
275 const Function &F, const DominatorTree &DT, const LoopInfo &LI,
276 const ir2vec::Vocabulary *Vocabulary) {
277
278 FunctionPropertiesInfo FPI;
279 if (Vocabulary && Vocabulary->isValid()) {
280 FPI.IR2VecVocab = Vocabulary;
281 FPI.FunctionEmbedding = ir2vec::Embedding(Vocabulary->getDimension(), 0.0);
282 }
283 for (const auto &BB : F)
284 if (DT.isReachableFromEntry(A: &BB))
285 FPI.reIncludeBB(BB);
286 FPI.updateAggregateStats(F, LI);
287 return FPI;
288}
289
290bool FunctionPropertiesInfo::operator==(
291 const FunctionPropertiesInfo &FPI) const {
292 if (BasicBlockCount != FPI.BasicBlockCount ||
293 BlocksReachedFromConditionalInstruction !=
294 FPI.BlocksReachedFromConditionalInstruction ||
295 Uses != FPI.Uses ||
296 DirectCallsToDefinedFunctions != FPI.DirectCallsToDefinedFunctions ||
297 LoadInstCount != FPI.LoadInstCount ||
298 StoreInstCount != FPI.StoreInstCount ||
299 MaxLoopDepth != FPI.MaxLoopDepth ||
300 TopLevelLoopCount != FPI.TopLevelLoopCount ||
301 TotalInstructionCount != FPI.TotalInstructionCount ||
302 BasicBlocksWithSingleSuccessor != FPI.BasicBlocksWithSingleSuccessor ||
303 BasicBlocksWithTwoSuccessors != FPI.BasicBlocksWithTwoSuccessors ||
304 BasicBlocksWithMoreThanTwoSuccessors !=
305 FPI.BasicBlocksWithMoreThanTwoSuccessors ||
306 BasicBlocksWithSinglePredecessor !=
307 FPI.BasicBlocksWithSinglePredecessor ||
308 BasicBlocksWithTwoPredecessors != FPI.BasicBlocksWithTwoPredecessors ||
309 BasicBlocksWithMoreThanTwoPredecessors !=
310 FPI.BasicBlocksWithMoreThanTwoPredecessors ||
311 BigBasicBlocks != FPI.BigBasicBlocks ||
312 MediumBasicBlocks != FPI.MediumBasicBlocks ||
313 SmallBasicBlocks != FPI.SmallBasicBlocks ||
314 CastInstructionCount != FPI.CastInstructionCount ||
315 FloatingPointInstructionCount != FPI.FloatingPointInstructionCount ||
316 IntegerInstructionCount != FPI.IntegerInstructionCount ||
317 ConstantIntOperandCount != FPI.ConstantIntOperandCount ||
318 ConstantFPOperandCount != FPI.ConstantFPOperandCount ||
319 ConstantOperandCount != FPI.ConstantOperandCount ||
320 InstructionOperandCount != FPI.InstructionOperandCount ||
321 BasicBlockOperandCount != FPI.BasicBlockOperandCount ||
322 GlobalValueOperandCount != FPI.GlobalValueOperandCount ||
323 InlineAsmOperandCount != FPI.InlineAsmOperandCount ||
324 ArgumentOperandCount != FPI.ArgumentOperandCount ||
325 UnknownOperandCount != FPI.UnknownOperandCount ||
326 CriticalEdgeCount != FPI.CriticalEdgeCount ||
327 ControlFlowEdgeCount != FPI.ControlFlowEdgeCount ||
328 UnconditionalBranchCount != FPI.UnconditionalBranchCount ||
329 IntrinsicCount != FPI.IntrinsicCount ||
330 NoReturnCallCount != FPI.NoReturnCallCount ||
331 DirectCallCount != FPI.DirectCallCount ||
332 IndirectCallCount != FPI.IndirectCallCount ||
333 CallReturnsIntegerCount != FPI.CallReturnsIntegerCount ||
334 CallReturnsFloatCount != FPI.CallReturnsFloatCount ||
335 CallReturnsPointerCount != FPI.CallReturnsPointerCount ||
336 CallReturnsVectorIntCount != FPI.CallReturnsVectorIntCount ||
337 CallReturnsVectorFloatCount != FPI.CallReturnsVectorFloatCount ||
338 CallReturnsVectorPointerCount != FPI.CallReturnsVectorPointerCount ||
339 CallWithManyArgumentsCount != FPI.CallWithManyArgumentsCount ||
340 CallWithPointerArgumentCount != FPI.CallWithPointerArgumentCount) {
341 return false;
342 }
343 // Check the equality of the function embeddings. We don't check the equality
344 // of Vocabulary as it remains the same.
345 if (!FunctionEmbedding.approximatelyEquals(RHS: FPI.FunctionEmbedding))
346 return false;
347
348 return true;
349}
350
351void FunctionPropertiesInfo::print(raw_ostream &OS) const {
352#define FUNCTION_PROPERTY(Name, Description) OS << #Name ": " << Name << "\n";
353
354#define DETAILED_FUNCTION_PROPERTY(Name, Description) \
355 if (EnableDetailedFunctionProperties) { \
356 OS << #Name ": " << Name << "\n"; \
357 }
358
359#include "llvm/IR/FunctionProperties.def"
360
361#undef FUNCTION_PROPERTY
362#undef DETAILED_FUNCTION_PROPERTY
363
364 OS << "\n";
365}
366
367AnalysisKey FunctionPropertiesAnalysis::Key;
368
369FunctionPropertiesInfo
370FunctionPropertiesAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
371 return FunctionPropertiesInfo::getFunctionPropertiesInfo(F, FAM);
372}
373
374PreservedAnalyses
375FunctionPropertiesPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
376 OS << "Printing analysis results of CFA for function "
377 << "'" << F.getName() << "':"
378 << "\n";
379 AM.getResult<FunctionPropertiesAnalysis>(IR&: F).print(OS);
380 return PreservedAnalyses::all();
381}
382
383PreservedAnalyses
384FunctionPropertiesStatisticsPass::run(Function &F,
385 FunctionAnalysisManager &FAM) {
386 LLVM_DEBUG(dbgs() << "STATSCOUNT: running on function " << F.getName()
387 << "\n");
388 auto &AnalysisResults = FAM.getResult<FunctionPropertiesAnalysis>(IR&: F);
389 if (IsPreOptimization) {
390#define FUNCTION_PROPERTY(Name, Description) \
391 Num##Name##PreOptimization += AnalysisResults.Name;
392#define DETAILED_FUNCTION_PROPERTY(Name, Description) \
393 Num##Name##PreOptimization += AnalysisResults.Name;
394#include "llvm/IR/FunctionProperties.def"
395#undef FUNCTION_PROPERTY
396#undef DETAILED_FUNCTION_PROPERTY
397 } else {
398#define FUNCTION_PROPERTY(Name, Description) Num##Name += AnalysisResults.Name;
399#define DETAILED_FUNCTION_PROPERTY(Name, Description) \
400 Num##Name += AnalysisResults.Name;
401#include "llvm/IR/FunctionProperties.def"
402#undef FUNCTION_PROPERTY
403#undef DETAILED_FUNCTION_PROPERTY
404 }
405 return PreservedAnalyses::all();
406}
407
408FunctionPropertiesUpdater::FunctionPropertiesUpdater(
409 FunctionPropertiesInfo &FPI, CallBase &CB)
410 : FPI(FPI), CallSiteBB(*CB.getParent()), Caller(*CallSiteBB.getParent()) {
411 assert(isa<CallInst>(CB) || isa<InvokeInst>(CB));
412 // For BBs that are likely to change, we subtract from feature totals their
413 // contribution. Some features, like max loop counts or depths, are left
414 // invalid, as they will be updated post-inlining.
415 SmallPtrSet<const BasicBlock *, 4> LikelyToChangeBBs;
416 // The CB BB will change - it'll either be split or the callee's body (single
417 // BB) will be pasted in.
418 LikelyToChangeBBs.insert(Ptr: &CallSiteBB);
419
420 // The caller's entry BB may change due to new alloca instructions.
421 LikelyToChangeBBs.insert(Ptr: &*Caller.begin());
422
423 // The users of the value returned by call instruction can change
424 // leading to the change in embeddings being computed, when used.
425 // We conservatively add the BBs with such uses to LikelyToChangeBBs.
426 for (const auto *User : CB.users())
427 CallUsers.insert(V: dyn_cast<Instruction>(Val: User)->getParent());
428 // CallSiteBB can be removed from CallUsers if present, it's taken care
429 // separately.
430 CallUsers.erase(V: &CallSiteBB);
431 LikelyToChangeBBs.insert_range(R&: CallUsers);
432
433 // The successors may become unreachable in the case of `invoke` inlining.
434 // We track successors separately, too, because they form a boundary, together
435 // with the CB BB ('Entry') between which the inlined callee will be pasted.
436 Successors.insert_range(R: successors(BB: &CallSiteBB));
437
438 // the outcome of the inlining may be that some edges get lost (DCEd BBs
439 // because inlining brought some constant, for example). We don't know which
440 // edges will be removed, so we list all of them as potentially removable.
441 // Some BBs have (at this point) duplicate edges. Remove duplicates, otherwise
442 // the DT updater will not apply changes correctly.
443 DenseSet<const BasicBlock *> Inserted;
444 for (auto *Succ : successors(BB: &CallSiteBB))
445 if (Inserted.insert(V: Succ).second)
446 DomTreeUpdates.emplace_back(Args: DominatorTree::UpdateKind::Delete,
447 Args: const_cast<BasicBlock *>(&CallSiteBB),
448 Args: const_cast<BasicBlock *>(Succ));
449 // Reuse Inserted (which has some allocated capacity at this point) below, if
450 // we have an invoke.
451 Inserted.clear();
452 // Inlining only handles invoke and calls. If this is an invoke, and inlining
453 // it pulls another invoke, the original landing pad may get split, so as to
454 // share its content with other potential users. So the edge up to which we
455 // need to invalidate and then re-account BB data is the successors of the
456 // current landing pad. We can leave the current lp, too - if it doesn't get
457 // split, then it will be the place traversal stops. Either way, the
458 // discounted BBs will be checked if reachable and re-added.
459 if (const auto *II = dyn_cast<InvokeInst>(Val: &CB)) {
460 const auto *UnwindDest = II->getUnwindDest();
461 Successors.insert_range(R: successors(BB: UnwindDest));
462 // Same idea as above, we pretend we lose all these edges.
463 for (auto *Succ : successors(BB: UnwindDest))
464 if (Inserted.insert(V: Succ).second)
465 DomTreeUpdates.emplace_back(Args: DominatorTree::UpdateKind::Delete,
466 Args: const_cast<BasicBlock *>(UnwindDest),
467 Args: const_cast<BasicBlock *>(Succ));
468 }
469
470 // Exclude the CallSiteBB, if it happens to be its own successor (1-BB loop).
471 // We are only interested in BBs the graph moves past the callsite BB to
472 // define the frontier past which we don't want to re-process BBs. Including
473 // the callsite BB in this case would prematurely stop the traversal in
474 // finish().
475 Successors.erase(V: &CallSiteBB);
476
477 LikelyToChangeBBs.insert_range(R&: Successors);
478
479 // Commit the change. While some of the BBs accounted for above may play dual
480 // role - e.g. caller's entry BB may be the same as the callsite BB - set
481 // insertion semantics make sure we account them once. This needs to be
482 // followed in `finish`, too.
483 for (const auto *BB : LikelyToChangeBBs)
484 FPI.updateForBB(BB: *BB, Direction: -1);
485}
486
487DominatorTree &FunctionPropertiesUpdater::getUpdatedDominatorTree(
488 FunctionAnalysisManager &FAM) const {
489 auto &DT =
490 FAM.getResult<DominatorTreeAnalysis>(IR&: const_cast<Function &>(Caller));
491
492 SmallVector<DominatorTree::UpdateType, 2> FinalDomTreeUpdates;
493
494 DenseSet<const BasicBlock *> Inserted;
495 for (auto *Succ : successors(BB: &CallSiteBB))
496 if (Inserted.insert(V: Succ).second)
497 FinalDomTreeUpdates.push_back(Elt: {DominatorTree::UpdateKind::Insert,
498 const_cast<BasicBlock *>(&CallSiteBB),
499 const_cast<BasicBlock *>(Succ)});
500
501 // Perform the deletes last, so that any new nodes connected to nodes
502 // participating in the edge deletion are known to the DT.
503 for (auto &Upd : DomTreeUpdates)
504 if (!llvm::is_contained(Range: successors(BB: Upd.getFrom()), Element: Upd.getTo()))
505 FinalDomTreeUpdates.push_back(Elt: Upd);
506
507 DT.applyUpdates(Updates: FinalDomTreeUpdates);
508#ifdef EXPENSIVE_CHECKS
509 assert(DT.verify(DominatorTree::VerificationLevel::Full));
510#endif
511 return DT;
512}
513
514void FunctionPropertiesUpdater::finish(FunctionAnalysisManager &FAM) const {
515 // Update feature values from the BBs that were copied from the callee, or
516 // might have been modified because of inlining. The latter have been
517 // subtracted in the FunctionPropertiesUpdater ctor.
518 // There could be successors that were reached before but now are only
519 // reachable from elsewhere in the CFG.
520 // One example is the following diamond CFG (lines are arrows pointing down):
521 // A
522 // / \
523 // B C
524 // | |
525 // | D
526 // | |
527 // | E
528 // \ /
529 // F
530 // There's a call site in C that is inlined. Upon doing that, it turns out
531 // it expands to
532 // call void @llvm.trap()
533 // unreachable
534 // F isn't reachable from C anymore, but we did discount it when we set up
535 // FunctionPropertiesUpdater, so we need to re-include it here.
536 // At the same time, D and E were reachable before, but now are not anymore,
537 // so we need to leave D out (we discounted it at setup), and explicitly
538 // remove E.
539 SetVector<const BasicBlock *> Reinclude;
540 SetVector<const BasicBlock *> Unreachable;
541 auto &DT = getUpdatedDominatorTree(FAM);
542
543 if (&CallSiteBB != &*Caller.begin())
544 Reinclude.insert(X: &*Caller.begin());
545
546 // Reinclude the BBs which use the values returned by call instruction
547 Reinclude.insert_range(R: CallUsers);
548
549 // Distribute the successors to the 2 buckets.
550 for (const auto *Succ : Successors)
551 if (DT.isReachableFromEntry(A: Succ))
552 Reinclude.insert(X: Succ);
553 else
554 Unreachable.insert(X: Succ);
555
556 // For reinclusion, we want to stop at the reachable successors, who are at
557 // the beginning of the worklist; but, starting from the callsite bb and
558 // ending at those successors, we also want to perform a traversal.
559 // IncludeSuccessorsMark is the index after which we include successors.
560 const auto IncludeSuccessorsMark = Reinclude.size();
561 bool CSInsertion = Reinclude.insert(X: &CallSiteBB);
562 (void)CSInsertion;
563 assert(CSInsertion);
564 for (size_t I = 0; I < Reinclude.size(); ++I) {
565 const auto *BB = Reinclude[I];
566 FPI.reIncludeBB(BB: *BB);
567 if (I >= IncludeSuccessorsMark)
568 Reinclude.insert_range(R: successors(BB));
569 }
570
571 // For exclusion, we don't need to exclude the set of BBs that were successors
572 // before and are now unreachable, because we already did that at setup. For
573 // the rest, as long as a successor is unreachable, we want to explicitly
574 // exclude it.
575 const auto AlreadyExcludedMark = Unreachable.size();
576 for (size_t I = 0; I < Unreachable.size(); ++I) {
577 const auto *U = Unreachable[I];
578 if (I >= AlreadyExcludedMark)
579 FPI.updateForBB(BB: *U, Direction: -1);
580 for (const auto *Succ : successors(BB: U))
581 if (!DT.isReachableFromEntry(A: Succ))
582 Unreachable.insert(X: Succ);
583 }
584
585 const auto &LI = FAM.getResult<LoopAnalysis>(IR&: const_cast<Function &>(Caller));
586 FPI.updateAggregateStats(F: Caller, LI);
587#ifdef EXPENSIVE_CHECKS
588 assert(isUpdateValid(Caller, FPI, FAM));
589#endif
590}
591
592bool FunctionPropertiesUpdater::isUpdateValid(Function &F,
593 const FunctionPropertiesInfo &FPI,
594 FunctionAnalysisManager &FAM) {
595 if (!FAM.getResult<DominatorTreeAnalysis>(IR&: F).verify(
596 VL: DominatorTree::VerificationLevel::Full))
597 return false;
598 DominatorTree DT(F);
599 LoopInfo LI(DT);
600 auto Vocabulary = FAM.getResult<ModuleAnalysisManagerFunctionProxy>(IR&: F)
601 .getCachedResult<IR2VecVocabAnalysis>(IR&: *F.getParent());
602 auto Fresh =
603 FunctionPropertiesInfo::getFunctionPropertiesInfo(F, DT, LI, Vocabulary);
604 return FPI == Fresh;
605}
606