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