1 //===- ModuleSummaryAnalysis.cpp - Module summary index builder -----------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This pass builds a ModuleSummaryIndex object for the module, to be written 11 // to bitcode or LLVM assembly. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/Analysis/ModuleSummaryAnalysis.h" 16 #include "llvm/ADT/Triple.h" 17 #include "llvm/Analysis/BlockFrequencyInfo.h" 18 #include "llvm/Analysis/BlockFrequencyInfoImpl.h" 19 #include "llvm/Analysis/BranchProbabilityInfo.h" 20 #include "llvm/Analysis/IndirectCallPromotionAnalysis.h" 21 #include "llvm/Analysis/LoopInfo.h" 22 #include "llvm/Analysis/ProfileSummaryInfo.h" 23 #include "llvm/IR/CallSite.h" 24 #include "llvm/IR/Dominators.h" 25 #include "llvm/IR/InstIterator.h" 26 #include "llvm/IR/IntrinsicInst.h" 27 #include "llvm/IR/ValueSymbolTable.h" 28 #include "llvm/Object/IRObjectFile.h" 29 #include "llvm/Pass.h" 30 using namespace llvm; 31 32 #define DEBUG_TYPE "module-summary-analysis" 33 34 // Walk through the operands of a given User via worklist iteration and populate 35 // the set of GlobalValue references encountered. Invoked either on an 36 // Instruction or a GlobalVariable (which walks its initializer). 37 static void findRefEdges(const User *CurUser, DenseSet<const Value *> &RefEdges, 38 SmallPtrSet<const User *, 8> &Visited) { 39 SmallVector<const User *, 32> Worklist; 40 Worklist.push_back(CurUser); 41 42 while (!Worklist.empty()) { 43 const User *U = Worklist.pop_back_val(); 44 45 if (!Visited.insert(U).second) 46 continue; 47 48 ImmutableCallSite CS(U); 49 50 for (const auto &OI : U->operands()) { 51 const User *Operand = dyn_cast<User>(OI); 52 if (!Operand) 53 continue; 54 if (isa<BlockAddress>(Operand)) 55 continue; 56 if (isa<GlobalValue>(Operand)) { 57 // We have a reference to a global value. This should be added to 58 // the reference set unless it is a callee. Callees are handled 59 // specially by WriteFunction and are added to a separate list. 60 if (!(CS && CS.isCallee(&OI))) 61 RefEdges.insert(Operand); 62 continue; 63 } 64 Worklist.push_back(Operand); 65 } 66 } 67 } 68 69 static CalleeInfo::HotnessType getHotness(uint64_t ProfileCount, 70 ProfileSummaryInfo *PSI) { 71 if (!PSI) 72 return CalleeInfo::HotnessType::Unknown; 73 if (PSI->isHotCount(ProfileCount)) 74 return CalleeInfo::HotnessType::Hot; 75 if (PSI->isColdCount(ProfileCount)) 76 return CalleeInfo::HotnessType::Cold; 77 return CalleeInfo::HotnessType::None; 78 } 79 80 static void computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M, 81 const Function &F, BlockFrequencyInfo *BFI, 82 ProfileSummaryInfo *PSI, 83 bool HasLocalsInUsed) { 84 // Summary not currently supported for anonymous functions, they should 85 // have been named. 86 assert(F.hasName()); 87 88 unsigned NumInsts = 0; 89 // Map from callee ValueId to profile count. Used to accumulate profile 90 // counts for all static calls to a given callee. 91 DenseMap<const Value *, CalleeInfo> CallGraphEdges; 92 DenseMap<GlobalValue::GUID, CalleeInfo> IndirectCallEdges; 93 DenseSet<const Value *> RefEdges; 94 ICallPromotionAnalysis ICallAnalysis; 95 96 bool HasInlineAsmMaybeReferencingInternal = false; 97 SmallPtrSet<const User *, 8> Visited; 98 for (const BasicBlock &BB : F) 99 for (const Instruction &I : BB) { 100 if (isa<DbgInfoIntrinsic>(I)) 101 continue; 102 ++NumInsts; 103 findRefEdges(&I, RefEdges, Visited); 104 auto CS = ImmutableCallSite(&I); 105 if (!CS) 106 continue; 107 108 const auto *CI = dyn_cast<CallInst>(&I); 109 // Since we don't know exactly which local values are referenced in inline 110 // assembly, conservatively mark the function as possibly referencing 111 // a local value from inline assembly to ensure we don't export a 112 // reference (which would require renaming and promotion of the 113 // referenced value). 114 if (HasLocalsInUsed && CI && CI->isInlineAsm()) 115 HasInlineAsmMaybeReferencingInternal = true; 116 117 auto *CalledValue = CS.getCalledValue(); 118 auto *CalledFunction = CS.getCalledFunction(); 119 // Check if this is an alias to a function. If so, get the 120 // called aliasee for the checks below. 121 if (auto *GA = dyn_cast<GlobalAlias>(CalledValue)) { 122 assert(!CalledFunction && "Expected null called function in callsite for alias"); 123 CalledFunction = dyn_cast<Function>(GA->getBaseObject()); 124 } 125 // Check if this is a direct call to a known function. 126 if (CalledFunction) { 127 // Skip intrinsics. 128 if (CalledFunction->isIntrinsic()) 129 continue; 130 // We should have named any anonymous globals 131 assert(CalledFunction->hasName()); 132 auto ScaledCount = BFI ? BFI->getBlockProfileCount(&BB) : None; 133 // Use the original CalledValue, in case it was an alias. We want 134 // to record the call edge to the alias in that case. Eventually 135 // an alias summary will be created to associate the alias and 136 // aliasee. 137 auto *CalleeId = 138 M.getValueSymbolTable().lookup(CalledValue->getName()); 139 140 auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI) 141 : CalleeInfo::HotnessType::Unknown; 142 CallGraphEdges[CalleeId].updateHotness(Hotness); 143 } else { 144 // Skip inline assembly calls. 145 if (CI && CI->isInlineAsm()) 146 continue; 147 // Skip direct calls. 148 if (!CS.getCalledValue() || isa<Constant>(CS.getCalledValue())) 149 continue; 150 151 uint32_t NumVals, NumCandidates; 152 uint64_t TotalCount; 153 auto CandidateProfileData = 154 ICallAnalysis.getPromotionCandidatesForInstruction( 155 &I, NumVals, TotalCount, NumCandidates); 156 for (auto &Candidate : CandidateProfileData) 157 IndirectCallEdges[Candidate.Value].updateHotness( 158 getHotness(Candidate.Count, PSI)); 159 } 160 } 161 162 GlobalValueSummary::GVFlags Flags(F); 163 std::unique_ptr<FunctionSummary> FuncSummary = 164 llvm::make_unique<FunctionSummary>(Flags, NumInsts); 165 FuncSummary->addCallGraphEdges(CallGraphEdges); 166 FuncSummary->addCallGraphEdges(IndirectCallEdges); 167 FuncSummary->addRefEdges(RefEdges); 168 if (HasInlineAsmMaybeReferencingInternal) 169 FuncSummary->setHasInlineAsmMaybeReferencingInternal(); 170 Index.addGlobalValueSummary(F.getName(), std::move(FuncSummary)); 171 } 172 173 static void computeVariableSummary(ModuleSummaryIndex &Index, 174 const GlobalVariable &V) { 175 DenseSet<const Value *> RefEdges; 176 SmallPtrSet<const User *, 8> Visited; 177 findRefEdges(&V, RefEdges, Visited); 178 GlobalValueSummary::GVFlags Flags(V); 179 std::unique_ptr<GlobalVarSummary> GVarSummary = 180 llvm::make_unique<GlobalVarSummary>(Flags); 181 GVarSummary->addRefEdges(RefEdges); 182 Index.addGlobalValueSummary(V.getName(), std::move(GVarSummary)); 183 } 184 185 static void computeAliasSummary(ModuleSummaryIndex &Index, 186 const GlobalAlias &A) { 187 GlobalValueSummary::GVFlags Flags(A); 188 std::unique_ptr<AliasSummary> AS = llvm::make_unique<AliasSummary>(Flags); 189 auto *Aliasee = A.getBaseObject(); 190 auto *AliaseeSummary = Index.getGlobalValueSummary(*Aliasee); 191 assert(AliaseeSummary && "Alias expects aliasee summary to be parsed"); 192 AS->setAliasee(AliaseeSummary); 193 Index.addGlobalValueSummary(A.getName(), std::move(AS)); 194 } 195 196 ModuleSummaryIndex llvm::buildModuleSummaryIndex( 197 const Module &M, 198 std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback, 199 ProfileSummaryInfo *PSI) { 200 ModuleSummaryIndex Index; 201 202 // Identify the local values in the llvm.used and llvm.compiler.used sets, 203 // which should not be exported as they would then require renaming and 204 // promotion, but we may have opaque uses e.g. in inline asm. We collect them 205 // here because we use this information to mark functions containing inline 206 // assembly calls as not importable. 207 SmallPtrSet<GlobalValue *, 8> LocalsUsed; 208 SmallPtrSet<GlobalValue *, 8> Used; 209 // First collect those in the llvm.used set. 210 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false); 211 for (auto *V : Used) { 212 if (V->hasLocalLinkage()) 213 LocalsUsed.insert(V); 214 } 215 Used.clear(); 216 // Next collect those in the llvm.compiler.used set. 217 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ true); 218 for (auto *V : Used) { 219 if (V->hasLocalLinkage()) 220 LocalsUsed.insert(V); 221 } 222 223 // Compute summaries for all functions defined in module, and save in the 224 // index. 225 for (auto &F : M) { 226 if (F.isDeclaration()) 227 continue; 228 229 BlockFrequencyInfo *BFI = nullptr; 230 std::unique_ptr<BlockFrequencyInfo> BFIPtr; 231 if (GetBFICallback) 232 BFI = GetBFICallback(F); 233 else if (F.getEntryCount().hasValue()) { 234 LoopInfo LI{DominatorTree(const_cast<Function &>(F))}; 235 BranchProbabilityInfo BPI{F, LI}; 236 BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI); 237 BFI = BFIPtr.get(); 238 } 239 240 computeFunctionSummary(Index, M, F, BFI, PSI, !LocalsUsed.empty()); 241 } 242 243 // Compute summaries for all variables defined in module, and save in the 244 // index. 245 for (const GlobalVariable &G : M.globals()) { 246 if (G.isDeclaration()) 247 continue; 248 computeVariableSummary(Index, G); 249 } 250 251 // Compute summaries for all aliases defined in module, and save in the 252 // index. 253 for (const GlobalAlias &A : M.aliases()) 254 computeAliasSummary(Index, A); 255 256 for (auto *V : LocalsUsed) { 257 auto *Summary = Index.getGlobalValueSummary(*V); 258 assert(Summary && "Missing summary for global value"); 259 Summary->setNoRename(); 260 } 261 262 if (!M.getModuleInlineAsm().empty()) { 263 // Collect the local values defined by module level asm, and set up 264 // summaries for these symbols so that they can be marked as NoRename, 265 // to prevent export of any use of them in regular IR that would require 266 // renaming within the module level asm. Note we don't need to create a 267 // summary for weak or global defs, as they don't need to be flagged as 268 // NoRename, and defs in module level asm can't be imported anyway. 269 // Also, any values used but not defined within module level asm should 270 // be listed on the llvm.used or llvm.compiler.used global and marked as 271 // referenced from there. 272 // FIXME: Rename CollectAsmUndefinedRefs to something more general, as we 273 // are also using it to find the file-scope locals defined in module asm. 274 object::IRObjectFile::CollectAsmUndefinedRefs( 275 Triple(M.getTargetTriple()), M.getModuleInlineAsm(), 276 [&M, &Index](StringRef Name, object::BasicSymbolRef::Flags Flags) { 277 // Symbols not marked as Weak or Global are local definitions. 278 if (Flags & (object::BasicSymbolRef::SF_Weak || 279 object::BasicSymbolRef::SF_Global)) 280 return; 281 GlobalValue *GV = M.getNamedValue(Name); 282 if (!GV) 283 return; 284 assert(GV->isDeclaration() && "Def in module asm already has definition"); 285 GlobalValueSummary::GVFlags GVFlags( 286 GlobalValue::InternalLinkage, 287 /* NoRename */ true, 288 /* HasInlineAsmMaybeReferencingInternal */ false, 289 /* IsNotViableToInline */ true); 290 // Create the appropriate summary type. 291 if (isa<Function>(GV)) { 292 std::unique_ptr<FunctionSummary> Summary = 293 llvm::make_unique<FunctionSummary>(GVFlags, 0); 294 Summary->setNoRename(); 295 Index.addGlobalValueSummary(Name, std::move(Summary)); 296 } else { 297 std::unique_ptr<GlobalVarSummary> Summary = 298 llvm::make_unique<GlobalVarSummary>(GVFlags); 299 Summary->setNoRename(); 300 Index.addGlobalValueSummary(Name, std::move(Summary)); 301 } 302 }); 303 } 304 305 return Index; 306 } 307 308 AnalysisKey ModuleSummaryIndexAnalysis::Key; 309 310 ModuleSummaryIndex 311 ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) { 312 ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(M); 313 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); 314 return buildModuleSummaryIndex( 315 M, 316 [&FAM](const Function &F) { 317 return &FAM.getResult<BlockFrequencyAnalysis>( 318 *const_cast<Function *>(&F)); 319 }, 320 &PSI); 321 } 322 323 char ModuleSummaryIndexWrapperPass::ID = 0; 324 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis", 325 "Module Summary Analysis", false, true) 326 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) 327 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis", 328 "Module Summary Analysis", false, true) 329 330 ModulePass *llvm::createModuleSummaryIndexWrapperPass() { 331 return new ModuleSummaryIndexWrapperPass(); 332 } 333 334 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass() 335 : ModulePass(ID) { 336 initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry()); 337 } 338 339 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) { 340 auto &PSI = *getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); 341 Index = buildModuleSummaryIndex( 342 M, 343 [this](const Function &F) { 344 return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>( 345 *const_cast<Function *>(&F)) 346 .getBFI()); 347 }, 348 &PSI); 349 return false; 350 } 351 352 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) { 353 Index.reset(); 354 return false; 355 } 356 357 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 358 AU.setPreservesAll(); 359 AU.addRequired<BlockFrequencyInfoWrapperPass>(); 360 AU.addRequired<ProfileSummaryInfoWrapperPass>(); 361 } 362