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 
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   // Exclude the CallSiteBB, if it happens to be its own successor (1-BB loop).
150   // We are only interested in BBs the graph moves past the callsite BB to
151   // define the frontier past which we don't want to re-process BBs. Including
152   // the callsite BB in this case would prematurely stop the traversal in
153   // finish().
154   Successors.erase(&CallSiteBB);
155 
156   for (const auto *BB : Successors)
157     LikelyToChangeBBs.insert(BB);
158 
159   // Commit the change. While some of the BBs accounted for above may play dual
160   // role - e.g. caller's entry BB may be the same as the callsite BB - set
161   // insertion semantics make sure we account them once. This needs to be
162   // followed in `finish`, too.
163   for (const auto *BB : LikelyToChangeBBs)
164     FPI.updateForBB(*BB, -1);
165 }
166 
167 void FunctionPropertiesUpdater::finish(FunctionAnalysisManager &FAM) const {
168   SetVector<const BasicBlock *> Worklist;
169 
170   if (&CallSiteBB != &*Caller.begin()) {
171     FPI.reIncludeBB(*Caller.begin());
172     Worklist.insert(&*Caller.begin());
173   }
174 
175   // Update feature values from the BBs that were copied from the callee, or
176   // might have been modified because of inlining. The latter have been
177   // subtracted in the FunctionPropertiesUpdater ctor.
178   // There could be successors that were reached before but now are only
179   // reachable from elsewhere in the CFG.
180   // Suppose the following diamond CFG (lines are arrows pointing down):
181   //    A
182   //  /   \
183   // B     C
184   //  \   /
185   //    D
186   // There's a call site in C that is inlined. Upon doing that, it turns out
187   // it expands to
188   //   call void @llvm.trap()
189   //   unreachable
190   // D isn't reachable from C anymore, but we did discount it when we set up
191   // FunctionPropertiesUpdater, so we need to re-include it here.
192 
193   const auto &DT =
194       FAM.getResult<DominatorTreeAnalysis>(const_cast<Function &>(Caller));
195   for (const auto *Succ : Successors)
196     if (DT.isReachableFromEntry(Succ) && Worklist.insert(Succ))
197       FPI.reIncludeBB(*Succ);
198 
199   auto I = Worklist.size();
200   bool CSInsertion = Worklist.insert(&CallSiteBB);
201   (void)CSInsertion;
202   assert(CSInsertion);
203   for (; I < Worklist.size(); ++I) {
204     const auto *BB = Worklist[I];
205     FPI.reIncludeBB(*BB);
206     for (const auto *Succ : successors(BB))
207       Worklist.insert(Succ);
208   }
209 
210   const auto &LI = FAM.getResult<LoopAnalysis>(const_cast<Function &>(Caller));
211   FPI.updateAggregateStats(Caller, LI);
212   assert(FPI == FunctionPropertiesInfo::getFunctionPropertiesInfo(Caller, FAM));
213 }
214