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