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/Analysis/LoopInfo.h" 17 #include "llvm/IR/CFG.h" 18 #include "llvm/IR/Instructions.h" 19 #include <deque> 20 21 using namespace llvm; 22 23 namespace { 24 int64_t getNrBlocksFromCond(const BasicBlock &BB) { 25 int64_t Ret = 0; 26 if (const auto *BI = dyn_cast<BranchInst>(BB.getTerminator())) { 27 if (BI->isConditional()) 28 Ret += BI->getNumSuccessors(); 29 } else if (const auto *SI = dyn_cast<SwitchInst>(BB.getTerminator())) { 30 Ret += (SI->getNumCases() + (nullptr != SI->getDefaultDest())); 31 } 32 return Ret; 33 } 34 35 int64_t getUses(const Function &F) { 36 return ((!F.hasLocalLinkage()) ? 1 : 0) + F.getNumUses(); 37 } 38 } // namespace 39 40 void FunctionPropertiesInfo::reIncludeBB(const BasicBlock &BB, 41 const LoopInfo &LI) { 42 updateForBB(BB, +1); 43 MaxLoopDepth = 44 std::max(MaxLoopDepth, static_cast<int64_t>(LI.getLoopDepth(&BB))); 45 } 46 47 void FunctionPropertiesInfo::updateForBB(const BasicBlock &BB, 48 int64_t Direction) { 49 assert(Direction == 1 || Direction == -1); 50 BasicBlockCount += Direction; 51 BlocksReachedFromConditionalInstruction += 52 (Direction * getNrBlocksFromCond(BB)); 53 for (const auto &I : BB) { 54 if (auto *CS = dyn_cast<CallBase>(&I)) { 55 const auto *Callee = CS->getCalledFunction(); 56 if (Callee && !Callee->isIntrinsic() && !Callee->isDeclaration()) 57 DirectCallsToDefinedFunctions += Direction; 58 } 59 if (I.getOpcode() == Instruction::Load) { 60 LoadInstCount += Direction; 61 } else if (I.getOpcode() == Instruction::Store) { 62 StoreInstCount += Direction; 63 } 64 } 65 TotalInstructionCount += Direction * BB.sizeWithoutDebug(); 66 } 67 68 void FunctionPropertiesInfo::updateAggregateStats(const Function &F, 69 const LoopInfo &LI) { 70 71 Uses = getUses(F); 72 TopLevelLoopCount = llvm::size(LI); 73 } 74 75 FunctionPropertiesInfo 76 FunctionPropertiesInfo::getFunctionPropertiesInfo(const Function &F, 77 const LoopInfo &LI) { 78 79 FunctionPropertiesInfo FPI; 80 for (const auto &BB : F) 81 if (!pred_empty(&BB) || BB.isEntryBlock()) 82 FPI.reIncludeBB(BB, LI); 83 FPI.updateAggregateStats(F, LI); 84 return FPI; 85 } 86 87 void FunctionPropertiesInfo::print(raw_ostream &OS) const { 88 OS << "BasicBlockCount: " << BasicBlockCount << "\n" 89 << "BlocksReachedFromConditionalInstruction: " 90 << BlocksReachedFromConditionalInstruction << "\n" 91 << "Uses: " << Uses << "\n" 92 << "DirectCallsToDefinedFunctions: " << DirectCallsToDefinedFunctions 93 << "\n" 94 << "LoadInstCount: " << LoadInstCount << "\n" 95 << "StoreInstCount: " << StoreInstCount << "\n" 96 << "MaxLoopDepth: " << MaxLoopDepth << "\n" 97 << "TopLevelLoopCount: " << TopLevelLoopCount << "\n" 98 << "TotalInstructionCount: " << TotalInstructionCount << "\n\n"; 99 } 100 101 AnalysisKey FunctionPropertiesAnalysis::Key; 102 103 FunctionPropertiesInfo 104 FunctionPropertiesAnalysis::run(Function &F, FunctionAnalysisManager &FAM) { 105 return FunctionPropertiesInfo::getFunctionPropertiesInfo( 106 F, FAM.getResult<LoopAnalysis>(F)); 107 } 108 109 PreservedAnalyses 110 FunctionPropertiesPrinterPass::run(Function &F, FunctionAnalysisManager &AM) { 111 OS << "Printing analysis results of CFA for function " 112 << "'" << F.getName() << "':" 113 << "\n"; 114 AM.getResult<FunctionPropertiesAnalysis>(F).print(OS); 115 return PreservedAnalyses::all(); 116 } 117 118 FunctionPropertiesUpdater::FunctionPropertiesUpdater( 119 FunctionPropertiesInfo &FPI, const CallBase &CB) 120 : FPI(FPI), CallSiteBB(*CB.getParent()), Caller(*CallSiteBB.getParent()) { 121 122 // For BBs that are likely to change, we subtract from feature totals their 123 // contribution. Some features, like max loop counts or depths, are left 124 // invalid, as they will be updated post-inlining. 125 SmallPtrSet<const BasicBlock *, 4> LikelyToChangeBBs; 126 // The CB BB will change - it'll either be split or the callee's body (single 127 // BB) will be pasted in. 128 LikelyToChangeBBs.insert(&CallSiteBB); 129 130 // The caller's entry BB may change due to new alloca instructions. 131 LikelyToChangeBBs.insert(&*Caller.begin()); 132 133 // The successors may become unreachable in the case of `invoke` inlining. 134 // We track successors separately, too, because they form a boundary, together 135 // with the CB BB ('Entry') between which the inlined callee will be pasted. 136 Successors.insert(succ_begin(&CallSiteBB), succ_end(&CallSiteBB)); 137 138 // Exclude the CallSiteBB, if it happens to be its own successor (1-BB loop). 139 // We are only interested in BBs the graph moves past the callsite BB to 140 // define the frontier past which we don't want to re-process BBs. Including 141 // the callsite BB in this case would prematurely stop the traversal in 142 // finish(). 143 Successors.erase(&CallSiteBB); 144 145 for (const auto *BB : Successors) 146 LikelyToChangeBBs.insert(BB); 147 148 // Commit the change. While some of the BBs accounted for above may play dual 149 // role - e.g. caller's entry BB may be the same as the callsite BB - set 150 // insertion semantics make sure we account them once. This needs to be 151 // followed in `finish`, too. 152 for (const auto *BB : LikelyToChangeBBs) 153 FPI.updateForBB(*BB, -1); 154 } 155 156 void FunctionPropertiesUpdater::finish(const LoopInfo &LI) const { 157 DenseSet<const BasicBlock *> ReIncluded; 158 std::deque<const BasicBlock *> Worklist; 159 160 if (&CallSiteBB != &*Caller.begin()) { 161 FPI.reIncludeBB(*Caller.begin(), LI); 162 ReIncluded.insert(&*Caller.begin()); 163 } 164 165 // Update feature values from the BBs that were copied from the callee, or 166 // might have been modified because of inlining. The latter have been 167 // subtracted in the FunctionPropertiesUpdater ctor. 168 Worklist.push_back(&CallSiteBB); 169 while (!Worklist.empty()) { 170 const auto *BB = Worklist.front(); 171 Worklist.pop_front(); 172 if (!ReIncluded.insert(BB).second) 173 continue; 174 FPI.reIncludeBB(*BB, LI); 175 if (!Successors.contains(BB)) 176 for (const auto *Succ : successors(BB)) 177 Worklist.push_back(Succ); 178 } 179 FPI.updateAggregateStats(Caller, LI); 180 assert(FPI == FunctionPropertiesInfo::getFunctionPropertiesInfo(Caller, LI)); 181 } 182