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/Dominators.h"
20 #include "llvm/IR/Instructions.h"
21 #include <deque>
22 
23 using namespace llvm;
24 
25 namespace {
26 int64_t getNrBlocksFromCond(const BasicBlock &BB) {
27   int64_t Ret = 0;
28   if (const auto *BI = dyn_cast<BranchInst>(BB.getTerminator())) {
29     if (BI->isConditional())
30       Ret += BI->getNumSuccessors();
31   } else if (const auto *SI = dyn_cast<SwitchInst>(BB.getTerminator())) {
32     Ret += (SI->getNumCases() + (nullptr != SI->getDefaultDest()));
33   }
34   return Ret;
35 }
36 
37 int64_t getUses(const Function &F) {
38   return ((!F.hasLocalLinkage()) ? 1 : 0) + F.getNumUses();
39 }
40 } // namespace
41 
42 void FunctionPropertiesInfo::reIncludeBB(const BasicBlock &BB) {
43   updateForBB(BB, +1);
44 }
45 
46 void FunctionPropertiesInfo::updateForBB(const BasicBlock &BB,
47                                          int64_t Direction) {
48   assert(Direction == 1 || Direction == -1);
49   BasicBlockCount += Direction;
50   BlocksReachedFromConditionalInstruction +=
51       (Direction * getNrBlocksFromCond(BB));
52   for (const auto &I : BB) {
53     if (auto *CS = dyn_cast<CallBase>(&I)) {
54       const auto *Callee = CS->getCalledFunction();
55       if (Callee && !Callee->isIntrinsic() && !Callee->isDeclaration())
56         DirectCallsToDefinedFunctions += Direction;
57     }
58     if (I.getOpcode() == Instruction::Load) {
59       LoadInstCount += Direction;
60     } else if (I.getOpcode() == Instruction::Store) {
61       StoreInstCount += Direction;
62     }
63   }
64   TotalInstructionCount += Direction * BB.sizeWithoutDebug();
65 }
66 
67 void FunctionPropertiesInfo::updateAggregateStats(const Function &F,
68                                                   const LoopInfo &LI) {
69 
70   Uses = getUses(F);
71   TopLevelLoopCount = llvm::size(LI);
72   MaxLoopDepth = 0;
73   std::deque<const Loop *> Worklist;
74   llvm::append_range(Worklist, LI);
75   while (!Worklist.empty()) {
76     const auto *L = Worklist.front();
77     MaxLoopDepth =
78         std::max(MaxLoopDepth, static_cast<int64_t>(L->getLoopDepth()));
79     Worklist.pop_front();
80     llvm::append_range(Worklist, L->getSubLoops());
81   }
82 }
83 
84 FunctionPropertiesInfo FunctionPropertiesInfo::getFunctionPropertiesInfo(
85     const Function &F, FunctionAnalysisManager &FAM) {
86 
87   FunctionPropertiesInfo FPI;
88   // The const casts are due to the getResult API - there's no mutation of F.
89   const auto &LI = FAM.getResult<LoopAnalysis>(const_cast<Function &>(F));
90   const auto &DT =
91       FAM.getResult<DominatorTreeAnalysis>(const_cast<Function &>(F));
92   for (const auto &BB : F)
93     if (DT.isReachableFromEntry(&BB))
94       FPI.reIncludeBB(BB);
95   FPI.updateAggregateStats(F, LI);
96   return FPI;
97 }
98 
99 void FunctionPropertiesInfo::print(raw_ostream &OS) const {
100   OS << "BasicBlockCount: " << BasicBlockCount << "\n"
101      << "BlocksReachedFromConditionalInstruction: "
102      << BlocksReachedFromConditionalInstruction << "\n"
103      << "Uses: " << Uses << "\n"
104      << "DirectCallsToDefinedFunctions: " << DirectCallsToDefinedFunctions
105      << "\n"
106      << "LoadInstCount: " << LoadInstCount << "\n"
107      << "StoreInstCount: " << StoreInstCount << "\n"
108      << "MaxLoopDepth: " << MaxLoopDepth << "\n"
109      << "TopLevelLoopCount: " << TopLevelLoopCount << "\n"
110      << "TotalInstructionCount: " << TotalInstructionCount << "\n\n";
111 }
112 
113 AnalysisKey FunctionPropertiesAnalysis::Key;
114 
115 FunctionPropertiesInfo
116 FunctionPropertiesAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
117   return FunctionPropertiesInfo::getFunctionPropertiesInfo(F, FAM);
118 }
119 
120 PreservedAnalyses
121 FunctionPropertiesPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
122   OS << "Printing analysis results of CFA for function "
123      << "'" << F.getName() << "':"
124      << "\n";
125   AM.getResult<FunctionPropertiesAnalysis>(F).print(OS);
126   return PreservedAnalyses::all();
127 }
128 
129 FunctionPropertiesUpdater::FunctionPropertiesUpdater(
130     FunctionPropertiesInfo &FPI, const CallBase &CB)
131     : FPI(FPI), CallSiteBB(*CB.getParent()), Caller(*CallSiteBB.getParent()) {
132   assert(isa<CallInst>(CB) || isa<InvokeInst>(CB));
133   // For BBs that are likely to change, we subtract from feature totals their
134   // contribution. Some features, like max loop counts or depths, are left
135   // invalid, as they will be updated post-inlining.
136   SmallPtrSet<const BasicBlock *, 4> LikelyToChangeBBs;
137   // The CB BB will change - it'll either be split or the callee's body (single
138   // BB) will be pasted in.
139   LikelyToChangeBBs.insert(&CallSiteBB);
140 
141   // The caller's entry BB may change due to new alloca instructions.
142   LikelyToChangeBBs.insert(&*Caller.begin());
143 
144   // The successors may become unreachable in the case of `invoke` inlining.
145   // We track successors separately, too, because they form a boundary, together
146   // with the CB BB ('Entry') between which the inlined callee will be pasted.
147   Successors.insert(succ_begin(&CallSiteBB), succ_end(&CallSiteBB));
148 
149   // Inlining only handles invoke and calls. If this is an invoke, and inlining
150   // it pulls another invoke, the original landing pad may get split, so as to
151   // share its content with other potential users. So the edge up to which we
152   // need to invalidate and then re-account BB data is the successors of the
153   // current landing pad. We can leave the current lp, too - if it doesn't get
154   // split, then it will be the place traversal stops. Either way, the
155   // discounted BBs will be checked if reachable and re-added.
156   if (const auto *II = dyn_cast<InvokeInst>(&CB)) {
157     const auto *UnwindDest = II->getUnwindDest();
158     Successors.insert(succ_begin(UnwindDest), succ_end(UnwindDest));
159   }
160 
161   // Exclude the CallSiteBB, if it happens to be its own successor (1-BB loop).
162   // We are only interested in BBs the graph moves past the callsite BB to
163   // define the frontier past which we don't want to re-process BBs. Including
164   // the callsite BB in this case would prematurely stop the traversal in
165   // finish().
166   Successors.erase(&CallSiteBB);
167 
168   for (const auto *BB : Successors)
169     LikelyToChangeBBs.insert(BB);
170 
171   // Commit the change. While some of the BBs accounted for above may play dual
172   // role - e.g. caller's entry BB may be the same as the callsite BB - set
173   // insertion semantics make sure we account them once. This needs to be
174   // followed in `finish`, too.
175   for (const auto *BB : LikelyToChangeBBs)
176     FPI.updateForBB(*BB, -1);
177 }
178 
179 void FunctionPropertiesUpdater::finish(FunctionAnalysisManager &FAM) const {
180   // Update feature values from the BBs that were copied from the callee, or
181   // might have been modified because of inlining. The latter have been
182   // subtracted in the FunctionPropertiesUpdater ctor.
183   // There could be successors that were reached before but now are only
184   // reachable from elsewhere in the CFG.
185   // One example is the following diamond CFG (lines are arrows pointing down):
186   //    A
187   //  /   \
188   // B     C
189   // |     |
190   // |     D
191   // |     |
192   // |     E
193   //  \   /
194   //    F
195   // There's a call site in C that is inlined. Upon doing that, it turns out
196   // it expands to
197   //   call void @llvm.trap()
198   //   unreachable
199   // F isn't reachable from C anymore, but we did discount it when we set up
200   // FunctionPropertiesUpdater, so we need to re-include it here.
201   // At the same time, D and E were reachable before, but now are not anymore,
202   // so we need to leave D out (we discounted it at setup), and explicitly
203   // remove E.
204   SetVector<const BasicBlock *> Reinclude;
205   SetVector<const BasicBlock *> Unreachable;
206   const auto &DT =
207       FAM.getResult<DominatorTreeAnalysis>(const_cast<Function &>(Caller));
208 
209   if (&CallSiteBB != &*Caller.begin())
210     Reinclude.insert(&*Caller.begin());
211 
212   // Distribute the successors to the 2 buckets.
213   for (const auto *Succ : Successors)
214     if (DT.isReachableFromEntry(Succ))
215       Reinclude.insert(Succ);
216     else
217       Unreachable.insert(Succ);
218 
219   // For reinclusion, we want to stop at the reachable successors, who are at
220   // the beginning of the worklist; but, starting from the callsite bb and
221   // ending at those successors, we also want to perform a traversal.
222   // IncludeSuccessorsMark is the index after which we include successors.
223   const auto IncludeSuccessorsMark = Reinclude.size();
224   bool CSInsertion = Reinclude.insert(&CallSiteBB);
225   (void)CSInsertion;
226   assert(CSInsertion);
227   for (size_t I = 0; I < Reinclude.size(); ++I) {
228     const auto *BB = Reinclude[I];
229     FPI.reIncludeBB(*BB);
230     if (I >= IncludeSuccessorsMark)
231       Reinclude.insert(succ_begin(BB), succ_end(BB));
232   }
233 
234   // For exclusion, we don't need to exclude the set of BBs that were successors
235   // before and are now unreachable, because we already did that at setup. For
236   // the rest, as long as a successor is unreachable, we want to explicitly
237   // exclude it.
238   const auto AlreadyExcludedMark = Unreachable.size();
239   for (size_t I = 0; I < Unreachable.size(); ++I) {
240     const auto *U = Unreachable[I];
241     if (I >= AlreadyExcludedMark)
242       FPI.updateForBB(*U, -1);
243     for (const auto *Succ : successors(U))
244       if (!DT.isReachableFromEntry(Succ))
245         Unreachable.insert(Succ);
246   }
247 
248   const auto &LI = FAM.getResult<LoopAnalysis>(const_cast<Function &>(Caller));
249   FPI.updateAggregateStats(Caller, LI);
250   assert(FPI == FunctionPropertiesInfo::getFunctionPropertiesInfo(Caller, FAM));
251 }
252