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