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 "llvm/Support/CommandLine.h" 22 #include <deque> 23 24 using namespace llvm; 25 26 cl::opt<bool> EnableDetailedFunctionProperties( 27 "enable-detailed-function-properties", cl::Hidden, cl::init(false), 28 cl::desc("Whether or not to compute detailed function properties.")); 29 30 cl::opt<unsigned> BigBasicBlockInstructionThreshold( 31 "big-basic-block-instruction-threshold", cl::Hidden, cl::init(500), 32 cl::desc("The minimum number of instructions a basic block should contain " 33 "before being considered big.")); 34 35 cl::opt<unsigned> MediumBasicBlockInstructionThreshold( 36 "medium-basic-block-instruction-threshold", cl::Hidden, cl::init(15), 37 cl::desc("The minimum number of instructions a basic block should contain " 38 "before being considered medium-sized.")); 39 40 namespace { 41 int64_t getNrBlocksFromCond(const BasicBlock &BB) { 42 int64_t Ret = 0; 43 if (const auto *BI = dyn_cast<BranchInst>(BB.getTerminator())) { 44 if (BI->isConditional()) 45 Ret += BI->getNumSuccessors(); 46 } else if (const auto *SI = dyn_cast<SwitchInst>(BB.getTerminator())) { 47 Ret += (SI->getNumCases() + (nullptr != SI->getDefaultDest())); 48 } 49 return Ret; 50 } 51 52 int64_t getUses(const Function &F) { 53 return ((!F.hasLocalLinkage()) ? 1 : 0) + F.getNumUses(); 54 } 55 } // namespace 56 57 void FunctionPropertiesInfo::reIncludeBB(const BasicBlock &BB) { 58 updateForBB(BB, +1); 59 } 60 61 void FunctionPropertiesInfo::updateForBB(const BasicBlock &BB, 62 int64_t Direction) { 63 assert(Direction == 1 || Direction == -1); 64 BasicBlockCount += Direction; 65 BlocksReachedFromConditionalInstruction += 66 (Direction * getNrBlocksFromCond(BB)); 67 for (const auto &I : BB) { 68 if (auto *CS = dyn_cast<CallBase>(&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.sizeWithoutDebug(); 80 81 if (EnableDetailedFunctionProperties) { 82 unsigned SuccessorCount = succ_size(&BB); 83 if (SuccessorCount == 1) 84 BasicBlocksWithSingleSuccessor += Direction; 85 else if (SuccessorCount == 2) 86 BasicBlocksWithTwoSuccessors += Direction; 87 else if (SuccessorCount > 2) 88 BasicBlocksWithMoreThanTwoSuccessors += Direction; 89 90 unsigned PredecessorCount = pred_size(&BB); 91 if (PredecessorCount == 1) 92 BasicBlocksWithSinglePredecessor += Direction; 93 else if (PredecessorCount == 2) 94 BasicBlocksWithTwoPredecessors += Direction; 95 else if (PredecessorCount > 2) 96 BasicBlocksWithMoreThanTwoPredecessors += Direction; 97 98 if (TotalInstructionCount > BigBasicBlockInstructionThreshold) 99 BigBasicBlocks += Direction; 100 else if (TotalInstructionCount > MediumBasicBlockInstructionThreshold) 101 MediumBasicBlocks += Direction; 102 else 103 SmallBasicBlocks += Direction; 104 105 for (const Instruction &I : BB.instructionsWithoutDebug()) { 106 if (I.isCast()) 107 CastInstructionCount += Direction; 108 109 if (I.getType()->isFloatTy()) 110 FloatingPointInstructionCount += Direction; 111 else if (I.getType()->isIntegerTy()) 112 IntegerInstructionCount += Direction; 113 114 for (unsigned int OperandIndex = 0; OperandIndex < I.getNumOperands(); 115 ++OperandIndex) { 116 if (const Constant *C = 117 dyn_cast<Constant>(I.getOperand(OperandIndex))) { 118 if (C->getType()->isIntegerTy()) 119 IntegerConstantCount += Direction; 120 else if (C->getType()->isFloatTy()) 121 FloatingPointConstantCount += Direction; 122 } 123 } 124 } 125 } 126 } 127 128 void FunctionPropertiesInfo::updateAggregateStats(const Function &F, 129 const LoopInfo &LI) { 130 131 Uses = getUses(F); 132 TopLevelLoopCount = llvm::size(LI); 133 MaxLoopDepth = 0; 134 std::deque<const Loop *> Worklist; 135 llvm::append_range(Worklist, LI); 136 while (!Worklist.empty()) { 137 const auto *L = Worklist.front(); 138 MaxLoopDepth = 139 std::max(MaxLoopDepth, static_cast<int64_t>(L->getLoopDepth())); 140 Worklist.pop_front(); 141 llvm::append_range(Worklist, L->getSubLoops()); 142 } 143 } 144 145 FunctionPropertiesInfo FunctionPropertiesInfo::getFunctionPropertiesInfo( 146 Function &F, FunctionAnalysisManager &FAM) { 147 return getFunctionPropertiesInfo(F, FAM.getResult<DominatorTreeAnalysis>(F), 148 FAM.getResult<LoopAnalysis>(F)); 149 } 150 151 FunctionPropertiesInfo FunctionPropertiesInfo::getFunctionPropertiesInfo( 152 const Function &F, const DominatorTree &DT, const LoopInfo &LI) { 153 154 FunctionPropertiesInfo FPI; 155 for (const auto &BB : F) 156 if (DT.isReachableFromEntry(&BB)) 157 FPI.reIncludeBB(BB); 158 FPI.updateAggregateStats(F, LI); 159 return FPI; 160 } 161 162 void FunctionPropertiesInfo::print(raw_ostream &OS) const { 163 OS << "BasicBlockCount: " << BasicBlockCount << "\n" 164 << "BlocksReachedFromConditionalInstruction: " 165 << BlocksReachedFromConditionalInstruction << "\n" 166 << "Uses: " << Uses << "\n" 167 << "DirectCallsToDefinedFunctions: " << DirectCallsToDefinedFunctions 168 << "\n" 169 << "LoadInstCount: " << LoadInstCount << "\n" 170 << "StoreInstCount: " << StoreInstCount << "\n" 171 << "MaxLoopDepth: " << MaxLoopDepth << "\n" 172 << "TopLevelLoopCount: " << TopLevelLoopCount << "\n" 173 << "TotalInstructionCount: " << TotalInstructionCount << "\n"; 174 if (EnableDetailedFunctionProperties) { 175 OS << "BasicBlocksWithSingleSuccessor: " << BasicBlocksWithSingleSuccessor 176 << "\n" 177 << "BasicBlocksWithTwoSuccessors: " << BasicBlocksWithTwoSuccessors 178 << "\n" 179 << "BasicBlocksWithMoreThanTwoSuccessors: " 180 << BasicBlocksWithMoreThanTwoSuccessors << "\n" 181 << "BasicBlocksWithSinglePredecessor: " 182 << BasicBlocksWithSinglePredecessor << "\n" 183 << "BasicBlocksWithTwoPredecessors: " << BasicBlocksWithTwoPredecessors 184 << "\n" 185 << "BasicBlocksWithMoreThanTwoPredecessors: " 186 << BasicBlocksWithMoreThanTwoPredecessors << "\n" 187 << "BigBasicBlocks: " << BigBasicBlocks << "\n" 188 << "MediumBasicBlocks: " << MediumBasicBlocks << "\n" 189 << "SmallBasicBlocks: " << SmallBasicBlocks << "\n" 190 << "CastInstructionCount: " << CastInstructionCount << "\n" 191 << "FloatingPointInstructionCount: " << FloatingPointInstructionCount 192 << "\n" 193 << "IntegerInstructionCount: " << IntegerInstructionCount << "\n" 194 << "IntegerConstantCount: " << IntegerConstantCount << "\n" 195 << "FloatingPointConstantCount: " << FloatingPointConstantCount << "\n"; 196 } 197 OS << "\n"; 198 } 199 200 AnalysisKey FunctionPropertiesAnalysis::Key; 201 202 FunctionPropertiesInfo 203 FunctionPropertiesAnalysis::run(Function &F, FunctionAnalysisManager &FAM) { 204 return FunctionPropertiesInfo::getFunctionPropertiesInfo(F, FAM); 205 } 206 207 PreservedAnalyses 208 FunctionPropertiesPrinterPass::run(Function &F, FunctionAnalysisManager &AM) { 209 OS << "Printing analysis results of CFA for function " 210 << "'" << F.getName() << "':" 211 << "\n"; 212 AM.getResult<FunctionPropertiesAnalysis>(F).print(OS); 213 return PreservedAnalyses::all(); 214 } 215 216 FunctionPropertiesUpdater::FunctionPropertiesUpdater( 217 FunctionPropertiesInfo &FPI, CallBase &CB) 218 : FPI(FPI), CallSiteBB(*CB.getParent()), Caller(*CallSiteBB.getParent()) { 219 assert(isa<CallInst>(CB) || isa<InvokeInst>(CB)); 220 // For BBs that are likely to change, we subtract from feature totals their 221 // contribution. Some features, like max loop counts or depths, are left 222 // invalid, as they will be updated post-inlining. 223 SmallPtrSet<const BasicBlock *, 4> LikelyToChangeBBs; 224 // The CB BB will change - it'll either be split or the callee's body (single 225 // BB) will be pasted in. 226 LikelyToChangeBBs.insert(&CallSiteBB); 227 228 // The caller's entry BB may change due to new alloca instructions. 229 LikelyToChangeBBs.insert(&*Caller.begin()); 230 231 // The successors may become unreachable in the case of `invoke` inlining. 232 // We track successors separately, too, because they form a boundary, together 233 // with the CB BB ('Entry') between which the inlined callee will be pasted. 234 Successors.insert(succ_begin(&CallSiteBB), succ_end(&CallSiteBB)); 235 236 // Inlining only handles invoke and calls. If this is an invoke, and inlining 237 // it pulls another invoke, the original landing pad may get split, so as to 238 // share its content with other potential users. So the edge up to which we 239 // need to invalidate and then re-account BB data is the successors of the 240 // current landing pad. We can leave the current lp, too - if it doesn't get 241 // split, then it will be the place traversal stops. Either way, the 242 // discounted BBs will be checked if reachable and re-added. 243 if (const auto *II = dyn_cast<InvokeInst>(&CB)) { 244 const auto *UnwindDest = II->getUnwindDest(); 245 Successors.insert(succ_begin(UnwindDest), succ_end(UnwindDest)); 246 } 247 248 // Exclude the CallSiteBB, if it happens to be its own successor (1-BB loop). 249 // We are only interested in BBs the graph moves past the callsite BB to 250 // define the frontier past which we don't want to re-process BBs. Including 251 // the callsite BB in this case would prematurely stop the traversal in 252 // finish(). 253 Successors.erase(&CallSiteBB); 254 255 for (const auto *BB : Successors) 256 LikelyToChangeBBs.insert(BB); 257 258 // Commit the change. While some of the BBs accounted for above may play dual 259 // role - e.g. caller's entry BB may be the same as the callsite BB - set 260 // insertion semantics make sure we account them once. This needs to be 261 // followed in `finish`, too. 262 for (const auto *BB : LikelyToChangeBBs) 263 FPI.updateForBB(*BB, -1); 264 } 265 266 void FunctionPropertiesUpdater::finish(FunctionAnalysisManager &FAM) const { 267 // Update feature values from the BBs that were copied from the callee, or 268 // might have been modified because of inlining. The latter have been 269 // subtracted in the FunctionPropertiesUpdater ctor. 270 // There could be successors that were reached before but now are only 271 // reachable from elsewhere in the CFG. 272 // One example is the following diamond CFG (lines are arrows pointing down): 273 // A 274 // / \ 275 // B C 276 // | | 277 // | D 278 // | | 279 // | E 280 // \ / 281 // F 282 // There's a call site in C that is inlined. Upon doing that, it turns out 283 // it expands to 284 // call void @llvm.trap() 285 // unreachable 286 // F isn't reachable from C anymore, but we did discount it when we set up 287 // FunctionPropertiesUpdater, so we need to re-include it here. 288 // At the same time, D and E were reachable before, but now are not anymore, 289 // so we need to leave D out (we discounted it at setup), and explicitly 290 // remove E. 291 SetVector<const BasicBlock *> Reinclude; 292 SetVector<const BasicBlock *> Unreachable; 293 const auto &DT = 294 FAM.getResult<DominatorTreeAnalysis>(const_cast<Function &>(Caller)); 295 296 if (&CallSiteBB != &*Caller.begin()) 297 Reinclude.insert(&*Caller.begin()); 298 299 // Distribute the successors to the 2 buckets. 300 for (const auto *Succ : Successors) 301 if (DT.isReachableFromEntry(Succ)) 302 Reinclude.insert(Succ); 303 else 304 Unreachable.insert(Succ); 305 306 // For reinclusion, we want to stop at the reachable successors, who are at 307 // the beginning of the worklist; but, starting from the callsite bb and 308 // ending at those successors, we also want to perform a traversal. 309 // IncludeSuccessorsMark is the index after which we include successors. 310 const auto IncludeSuccessorsMark = Reinclude.size(); 311 bool CSInsertion = Reinclude.insert(&CallSiteBB); 312 (void)CSInsertion; 313 assert(CSInsertion); 314 for (size_t I = 0; I < Reinclude.size(); ++I) { 315 const auto *BB = Reinclude[I]; 316 FPI.reIncludeBB(*BB); 317 if (I >= IncludeSuccessorsMark) 318 Reinclude.insert(succ_begin(BB), succ_end(BB)); 319 } 320 321 // For exclusion, we don't need to exclude the set of BBs that were successors 322 // before and are now unreachable, because we already did that at setup. For 323 // the rest, as long as a successor is unreachable, we want to explicitly 324 // exclude it. 325 const auto AlreadyExcludedMark = Unreachable.size(); 326 for (size_t I = 0; I < Unreachable.size(); ++I) { 327 const auto *U = Unreachable[I]; 328 if (I >= AlreadyExcludedMark) 329 FPI.updateForBB(*U, -1); 330 for (const auto *Succ : successors(U)) 331 if (!DT.isReachableFromEntry(Succ)) 332 Unreachable.insert(Succ); 333 } 334 335 const auto &LI = FAM.getResult<LoopAnalysis>(const_cast<Function &>(Caller)); 336 FPI.updateAggregateStats(Caller, LI); 337 } 338 339 bool FunctionPropertiesUpdater::isUpdateValid(Function &F, 340 const FunctionPropertiesInfo &FPI, 341 FunctionAnalysisManager &FAM) { 342 DominatorTree DT(F); 343 LoopInfo LI(DT); 344 auto Fresh = FunctionPropertiesInfo::getFunctionPropertiesInfo(F, DT, LI); 345 return FPI == Fresh; 346 } 347