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