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