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 Function &F, FunctionAnalysisManager &FAM) { 86 return getFunctionPropertiesInfo(F, FAM.getResult<DominatorTreeAnalysis>(F), 87 FAM.getResult<LoopAnalysis>(F)); 88 } 89 90 FunctionPropertiesInfo FunctionPropertiesInfo::getFunctionPropertiesInfo( 91 const Function &F, const DominatorTree &DT, const LoopInfo &LI) { 92 93 FunctionPropertiesInfo FPI; 94 for (const auto &BB : F) 95 if (DT.isReachableFromEntry(&BB)) 96 FPI.reIncludeBB(BB); 97 FPI.updateAggregateStats(F, LI); 98 return FPI; 99 } 100 101 void FunctionPropertiesInfo::print(raw_ostream &OS) const { 102 OS << "BasicBlockCount: " << BasicBlockCount << "\n" 103 << "BlocksReachedFromConditionalInstruction: " 104 << BlocksReachedFromConditionalInstruction << "\n" 105 << "Uses: " << Uses << "\n" 106 << "DirectCallsToDefinedFunctions: " << DirectCallsToDefinedFunctions 107 << "\n" 108 << "LoadInstCount: " << LoadInstCount << "\n" 109 << "StoreInstCount: " << StoreInstCount << "\n" 110 << "MaxLoopDepth: " << MaxLoopDepth << "\n" 111 << "TopLevelLoopCount: " << TopLevelLoopCount << "\n" 112 << "TotalInstructionCount: " << TotalInstructionCount << "\n\n"; 113 } 114 115 AnalysisKey FunctionPropertiesAnalysis::Key; 116 117 FunctionPropertiesInfo 118 FunctionPropertiesAnalysis::run(Function &F, FunctionAnalysisManager &FAM) { 119 return FunctionPropertiesInfo::getFunctionPropertiesInfo(F, FAM); 120 } 121 122 PreservedAnalyses 123 FunctionPropertiesPrinterPass::run(Function &F, FunctionAnalysisManager &AM) { 124 OS << "Printing analysis results of CFA for function " 125 << "'" << F.getName() << "':" 126 << "\n"; 127 AM.getResult<FunctionPropertiesAnalysis>(F).print(OS); 128 return PreservedAnalyses::all(); 129 } 130 131 FunctionPropertiesUpdater::FunctionPropertiesUpdater( 132 FunctionPropertiesInfo &FPI, CallBase &CB) 133 : FPI(FPI), CallSiteBB(*CB.getParent()), Caller(*CallSiteBB.getParent()) { 134 assert(isa<CallInst>(CB) || isa<InvokeInst>(CB)); 135 // For BBs that are likely to change, we subtract from feature totals their 136 // contribution. Some features, like max loop counts or depths, are left 137 // invalid, as they will be updated post-inlining. 138 SmallPtrSet<const BasicBlock *, 4> LikelyToChangeBBs; 139 // The CB BB will change - it'll either be split or the callee's body (single 140 // BB) will be pasted in. 141 LikelyToChangeBBs.insert(&CallSiteBB); 142 143 // The caller's entry BB may change due to new alloca instructions. 144 LikelyToChangeBBs.insert(&*Caller.begin()); 145 146 // The successors may become unreachable in the case of `invoke` inlining. 147 // We track successors separately, too, because they form a boundary, together 148 // with the CB BB ('Entry') between which the inlined callee will be pasted. 149 Successors.insert(succ_begin(&CallSiteBB), succ_end(&CallSiteBB)); 150 151 // Inlining only handles invoke and calls. If this is an invoke, and inlining 152 // it pulls another invoke, the original landing pad may get split, so as to 153 // share its content with other potential users. So the edge up to which we 154 // need to invalidate and then re-account BB data is the successors of the 155 // current landing pad. We can leave the current lp, too - if it doesn't get 156 // split, then it will be the place traversal stops. Either way, the 157 // discounted BBs will be checked if reachable and re-added. 158 if (const auto *II = dyn_cast<InvokeInst>(&CB)) { 159 const auto *UnwindDest = II->getUnwindDest(); 160 Successors.insert(succ_begin(UnwindDest), succ_end(UnwindDest)); 161 } 162 163 // Exclude the CallSiteBB, if it happens to be its own successor (1-BB loop). 164 // We are only interested in BBs the graph moves past the callsite BB to 165 // define the frontier past which we don't want to re-process BBs. Including 166 // the callsite BB in this case would prematurely stop the traversal in 167 // finish(). 168 Successors.erase(&CallSiteBB); 169 170 for (const auto *BB : Successors) 171 LikelyToChangeBBs.insert(BB); 172 173 // Commit the change. While some of the BBs accounted for above may play dual 174 // role - e.g. caller's entry BB may be the same as the callsite BB - set 175 // insertion semantics make sure we account them once. This needs to be 176 // followed in `finish`, too. 177 for (const auto *BB : LikelyToChangeBBs) 178 FPI.updateForBB(*BB, -1); 179 } 180 181 void FunctionPropertiesUpdater::finish(FunctionAnalysisManager &FAM) const { 182 // Update feature values from the BBs that were copied from the callee, or 183 // might have been modified because of inlining. The latter have been 184 // subtracted in the FunctionPropertiesUpdater ctor. 185 // There could be successors that were reached before but now are only 186 // reachable from elsewhere in the CFG. 187 // One example is the following diamond CFG (lines are arrows pointing down): 188 // A 189 // / \ 190 // B C 191 // | | 192 // | D 193 // | | 194 // | E 195 // \ / 196 // F 197 // There's a call site in C that is inlined. Upon doing that, it turns out 198 // it expands to 199 // call void @llvm.trap() 200 // unreachable 201 // F isn't reachable from C anymore, but we did discount it when we set up 202 // FunctionPropertiesUpdater, so we need to re-include it here. 203 // At the same time, D and E were reachable before, but now are not anymore, 204 // so we need to leave D out (we discounted it at setup), and explicitly 205 // remove E. 206 SetVector<const BasicBlock *> Reinclude; 207 SetVector<const BasicBlock *> Unreachable; 208 const auto &DT = 209 FAM.getResult<DominatorTreeAnalysis>(const_cast<Function &>(Caller)); 210 211 if (&CallSiteBB != &*Caller.begin()) 212 Reinclude.insert(&*Caller.begin()); 213 214 // Distribute the successors to the 2 buckets. 215 for (const auto *Succ : Successors) 216 if (DT.isReachableFromEntry(Succ)) 217 Reinclude.insert(Succ); 218 else 219 Unreachable.insert(Succ); 220 221 // For reinclusion, we want to stop at the reachable successors, who are at 222 // the beginning of the worklist; but, starting from the callsite bb and 223 // ending at those successors, we also want to perform a traversal. 224 // IncludeSuccessorsMark is the index after which we include successors. 225 const auto IncludeSuccessorsMark = Reinclude.size(); 226 bool CSInsertion = Reinclude.insert(&CallSiteBB); 227 (void)CSInsertion; 228 assert(CSInsertion); 229 for (size_t I = 0; I < Reinclude.size(); ++I) { 230 const auto *BB = Reinclude[I]; 231 FPI.reIncludeBB(*BB); 232 if (I >= IncludeSuccessorsMark) 233 Reinclude.insert(succ_begin(BB), succ_end(BB)); 234 } 235 236 // For exclusion, we don't need to exclude the set of BBs that were successors 237 // before and are now unreachable, because we already did that at setup. For 238 // the rest, as long as a successor is unreachable, we want to explicitly 239 // exclude it. 240 const auto AlreadyExcludedMark = Unreachable.size(); 241 for (size_t I = 0; I < Unreachable.size(); ++I) { 242 const auto *U = Unreachable[I]; 243 if (I >= AlreadyExcludedMark) 244 FPI.updateForBB(*U, -1); 245 for (const auto *Succ : successors(U)) 246 if (!DT.isReachableFromEntry(Succ)) 247 Unreachable.insert(Succ); 248 } 249 250 const auto &LI = FAM.getResult<LoopAnalysis>(const_cast<Function &>(Caller)); 251 FPI.updateAggregateStats(Caller, LI); 252 } 253 254 bool FunctionPropertiesUpdater::isUpdateValid(Function &F, 255 const FunctionPropertiesInfo &FPI, 256 FunctionAnalysisManager &FAM) { 257 DominatorTree DT(F); 258 LoopInfo LI(DT); 259 auto Fresh = FunctionPropertiesInfo::getFunctionPropertiesInfo(F, DT, LI); 260 return FPI == Fresh; 261 }