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/MapVector.h" 17 #include "llvm/ADT/SetVector.h" 18 #include "llvm/ADT/Triple.h" 19 #include "llvm/Analysis/BlockFrequencyInfo.h" 20 #include "llvm/Analysis/BlockFrequencyInfoImpl.h" 21 #include "llvm/Analysis/BranchProbabilityInfo.h" 22 #include "llvm/Analysis/IndirectCallPromotionAnalysis.h" 23 #include "llvm/Analysis/LoopInfo.h" 24 #include "llvm/Analysis/ProfileSummaryInfo.h" 25 #include "llvm/Analysis/TypeMetadataUtils.h" 26 #include "llvm/IR/CallSite.h" 27 #include "llvm/IR/Dominators.h" 28 #include "llvm/IR/InstIterator.h" 29 #include "llvm/IR/IntrinsicInst.h" 30 #include "llvm/IR/ValueSymbolTable.h" 31 #include "llvm/Object/IRObjectFile.h" 32 #include "llvm/Pass.h" 33 using namespace llvm; 34 35 #define DEBUG_TYPE "module-summary-analysis" 36 37 // Walk through the operands of a given User via worklist iteration and populate 38 // the set of GlobalValue references encountered. Invoked either on an 39 // Instruction or a GlobalVariable (which walks its initializer). 40 static void findRefEdges(const User *CurUser, SetVector<ValueInfo> &RefEdges, 41 SmallPtrSet<const User *, 8> &Visited) { 42 SmallVector<const User *, 32> Worklist; 43 Worklist.push_back(CurUser); 44 45 while (!Worklist.empty()) { 46 const User *U = Worklist.pop_back_val(); 47 48 if (!Visited.insert(U).second) 49 continue; 50 51 ImmutableCallSite CS(U); 52 53 for (const auto &OI : U->operands()) { 54 const User *Operand = dyn_cast<User>(OI); 55 if (!Operand) 56 continue; 57 if (isa<BlockAddress>(Operand)) 58 continue; 59 if (auto *GV = dyn_cast<GlobalValue>(Operand)) { 60 // We have a reference to a global value. This should be added to 61 // the reference set unless it is a callee. Callees are handled 62 // specially by WriteFunction and are added to a separate list. 63 if (!(CS && CS.isCallee(&OI))) 64 RefEdges.insert(GV); 65 continue; 66 } 67 Worklist.push_back(Operand); 68 } 69 } 70 } 71 72 static CalleeInfo::HotnessType getHotness(uint64_t ProfileCount, 73 ProfileSummaryInfo *PSI) { 74 if (!PSI) 75 return CalleeInfo::HotnessType::Unknown; 76 if (PSI->isHotCount(ProfileCount)) 77 return CalleeInfo::HotnessType::Hot; 78 if (PSI->isColdCount(ProfileCount)) 79 return CalleeInfo::HotnessType::Cold; 80 return CalleeInfo::HotnessType::None; 81 } 82 83 static bool isNonRenamableLocal(const GlobalValue &GV) { 84 return GV.hasSection() && GV.hasLocalLinkage(); 85 } 86 87 static void 88 computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M, 89 const Function &F, BlockFrequencyInfo *BFI, 90 ProfileSummaryInfo *PSI, bool HasLocalsInUsed, 91 DenseSet<GlobalValue::GUID> &CantBePromoted) { 92 // Summary not currently supported for anonymous functions, they should 93 // have been named. 94 assert(F.hasName()); 95 96 unsigned NumInsts = 0; 97 // Map from callee ValueId to profile count. Used to accumulate profile 98 // counts for all static calls to a given callee. 99 MapVector<ValueInfo, CalleeInfo> CallGraphEdges; 100 SetVector<ValueInfo> RefEdges; 101 SetVector<GlobalValue::GUID> TypeTests; 102 ICallPromotionAnalysis ICallAnalysis; 103 104 bool HasInlineAsmMaybeReferencingInternal = false; 105 SmallPtrSet<const User *, 8> Visited; 106 for (const BasicBlock &BB : F) 107 for (const Instruction &I : BB) { 108 if (isa<DbgInfoIntrinsic>(I)) 109 continue; 110 ++NumInsts; 111 findRefEdges(&I, RefEdges, Visited); 112 auto CS = ImmutableCallSite(&I); 113 if (!CS) 114 continue; 115 116 const auto *CI = dyn_cast<CallInst>(&I); 117 // Since we don't know exactly which local values are referenced in inline 118 // assembly, conservatively mark the function as possibly referencing 119 // a local value from inline assembly to ensure we don't export a 120 // reference (which would require renaming and promotion of the 121 // referenced value). 122 if (HasLocalsInUsed && CI && CI->isInlineAsm()) 123 HasInlineAsmMaybeReferencingInternal = true; 124 125 auto *CalledValue = CS.getCalledValue(); 126 auto *CalledFunction = CS.getCalledFunction(); 127 // Check if this is an alias to a function. If so, get the 128 // called aliasee for the checks below. 129 if (auto *GA = dyn_cast<GlobalAlias>(CalledValue)) { 130 assert(!CalledFunction && "Expected null called function in callsite for alias"); 131 CalledFunction = dyn_cast<Function>(GA->getBaseObject()); 132 } 133 // Check if this is a direct call to a known function or a known 134 // intrinsic, or an indirect call with profile data. 135 if (CalledFunction) { 136 if (CalledFunction->isIntrinsic()) { 137 if (CalledFunction->getIntrinsicID() != Intrinsic::type_test) 138 continue; 139 // Produce a summary from type.test intrinsics. We only summarize 140 // type.test intrinsics that are used other than by an llvm.assume 141 // intrinsic. Intrinsics that are assumed are relevant only to the 142 // devirtualization pass, not the type test lowering pass. 143 bool HasNonAssumeUses = llvm::any_of(CI->uses(), [](const Use &CIU) { 144 auto *AssumeCI = dyn_cast<CallInst>(CIU.getUser()); 145 if (!AssumeCI) 146 return true; 147 Function *F = AssumeCI->getCalledFunction(); 148 return !F || F->getIntrinsicID() != Intrinsic::assume; 149 }); 150 if (HasNonAssumeUses) { 151 auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(1)); 152 if (auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata())) 153 TypeTests.insert(GlobalValue::getGUID(TypeId->getString())); 154 } 155 } 156 // We should have named any anonymous globals 157 assert(CalledFunction->hasName()); 158 auto ScaledCount = BFI ? BFI->getBlockProfileCount(&BB) : None; 159 auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI) 160 : CalleeInfo::HotnessType::Unknown; 161 162 // Use the original CalledValue, in case it was an alias. We want 163 // to record the call edge to the alias in that case. Eventually 164 // an alias summary will be created to associate the alias and 165 // aliasee. 166 CallGraphEdges[cast<GlobalValue>(CalledValue)].updateHotness(Hotness); 167 } else { 168 // Skip inline assembly calls. 169 if (CI && CI->isInlineAsm()) 170 continue; 171 // Skip direct calls. 172 if (!CS.getCalledValue() || isa<Constant>(CS.getCalledValue())) 173 continue; 174 175 uint32_t NumVals, NumCandidates; 176 uint64_t TotalCount; 177 auto CandidateProfileData = 178 ICallAnalysis.getPromotionCandidatesForInstruction( 179 &I, NumVals, TotalCount, NumCandidates); 180 for (auto &Candidate : CandidateProfileData) 181 CallGraphEdges[Candidate.Value].updateHotness( 182 getHotness(Candidate.Count, PSI)); 183 } 184 } 185 186 bool NonRenamableLocal = isNonRenamableLocal(F); 187 bool NotEligibleForImport = 188 NonRenamableLocal || HasInlineAsmMaybeReferencingInternal || 189 // Inliner doesn't handle variadic functions. 190 // FIXME: refactor this to use the same code that inliner is using. 191 F.isVarArg(); 192 GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport, 193 /* LiveRoot = */ false, 194 /* AutoHide */ false); 195 auto FuncSummary = llvm::make_unique<FunctionSummary>( 196 Flags, NumInsts, RefEdges.takeVector(), CallGraphEdges.takeVector(), 197 TypeTests.takeVector()); 198 if (NonRenamableLocal) 199 CantBePromoted.insert(F.getGUID()); 200 Index.addGlobalValueSummary(F.getName(), std::move(FuncSummary)); 201 } 202 203 static void 204 computeVariableSummary(ModuleSummaryIndex &Index, const GlobalVariable &V, 205 DenseSet<GlobalValue::GUID> &CantBePromoted) { 206 SetVector<ValueInfo> RefEdges; 207 SmallPtrSet<const User *, 8> Visited; 208 findRefEdges(&V, RefEdges, Visited); 209 bool NonRenamableLocal = isNonRenamableLocal(V); 210 GlobalValueSummary::GVFlags Flags(V.getLinkage(), NonRenamableLocal, 211 /* LiveRoot = */ false, 212 /* AutoHide */ false); 213 auto GVarSummary = 214 llvm::make_unique<GlobalVarSummary>(Flags, RefEdges.takeVector()); 215 if (NonRenamableLocal) 216 CantBePromoted.insert(V.getGUID()); 217 Index.addGlobalValueSummary(V.getName(), std::move(GVarSummary)); 218 } 219 220 static void 221 computeAliasSummary(ModuleSummaryIndex &Index, const GlobalAlias &A, 222 DenseSet<GlobalValue::GUID> &CantBePromoted) { 223 bool NonRenamableLocal = isNonRenamableLocal(A); 224 GlobalValueSummary::GVFlags Flags(A.getLinkage(), NonRenamableLocal, 225 /* LiveRoot = */ false, 226 /* AutoHide */ false); 227 auto AS = llvm::make_unique<AliasSummary>(Flags, ArrayRef<ValueInfo>{}); 228 auto *Aliasee = A.getBaseObject(); 229 auto *AliaseeSummary = Index.getGlobalValueSummary(*Aliasee); 230 assert(AliaseeSummary && "Alias expects aliasee summary to be parsed"); 231 AS->setAliasee(AliaseeSummary); 232 if (NonRenamableLocal) 233 CantBePromoted.insert(A.getGUID()); 234 Index.addGlobalValueSummary(A.getName(), std::move(AS)); 235 } 236 237 // Set LiveRoot flag on entries matching the given value name. 238 static void setLiveRoot(ModuleSummaryIndex &Index, StringRef Name) { 239 auto SummaryList = 240 Index.findGlobalValueSummaryList(GlobalValue::getGUID(Name)); 241 if (SummaryList == Index.end()) 242 return; 243 for (auto &Summary : SummaryList->second) 244 Summary->setLiveRoot(); 245 } 246 247 ModuleSummaryIndex llvm::buildModuleSummaryIndex( 248 const Module &M, 249 std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback, 250 ProfileSummaryInfo *PSI) { 251 ModuleSummaryIndex Index; 252 253 // Identify the local values in the llvm.used and llvm.compiler.used sets, 254 // which should not be exported as they would then require renaming and 255 // promotion, but we may have opaque uses e.g. in inline asm. We collect them 256 // here because we use this information to mark functions containing inline 257 // assembly calls as not importable. 258 SmallPtrSet<GlobalValue *, 8> LocalsUsed; 259 SmallPtrSet<GlobalValue *, 8> Used; 260 // First collect those in the llvm.used set. 261 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false); 262 // Next collect those in the llvm.compiler.used set. 263 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ true); 264 DenseSet<GlobalValue::GUID> CantBePromoted; 265 for (auto *V : Used) { 266 if (V->hasLocalLinkage()) { 267 LocalsUsed.insert(V); 268 CantBePromoted.insert(V->getGUID()); 269 } 270 } 271 272 // Compute summaries for all functions defined in module, and save in the 273 // index. 274 for (auto &F : M) { 275 if (F.isDeclaration()) 276 continue; 277 278 BlockFrequencyInfo *BFI = nullptr; 279 std::unique_ptr<BlockFrequencyInfo> BFIPtr; 280 if (GetBFICallback) 281 BFI = GetBFICallback(F); 282 else if (F.getEntryCount().hasValue()) { 283 LoopInfo LI{DominatorTree(const_cast<Function &>(F))}; 284 BranchProbabilityInfo BPI{F, LI}; 285 BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI); 286 BFI = BFIPtr.get(); 287 } 288 289 computeFunctionSummary(Index, M, F, BFI, PSI, !LocalsUsed.empty(), 290 CantBePromoted); 291 } 292 293 // Compute summaries for all variables defined in module, and save in the 294 // index. 295 for (const GlobalVariable &G : M.globals()) { 296 if (G.isDeclaration()) 297 continue; 298 computeVariableSummary(Index, G, CantBePromoted); 299 } 300 301 // Compute summaries for all aliases defined in module, and save in the 302 // index. 303 for (const GlobalAlias &A : M.aliases()) 304 computeAliasSummary(Index, A, CantBePromoted); 305 306 for (auto *V : LocalsUsed) { 307 auto *Summary = Index.getGlobalValueSummary(*V); 308 assert(Summary && "Missing summary for global value"); 309 Summary->setNotEligibleToImport(); 310 } 311 312 // The linker doesn't know about these LLVM produced values, so we need 313 // to flag them as live in the index to ensure index-based dead value 314 // analysis treats them as live roots of the analysis. 315 setLiveRoot(Index, "llvm.used"); 316 setLiveRoot(Index, "llvm.compiler.used"); 317 setLiveRoot(Index, "llvm.global_ctors"); 318 setLiveRoot(Index, "llvm.global_dtors"); 319 setLiveRoot(Index, "llvm.global.annotations"); 320 321 if (!M.getModuleInlineAsm().empty()) { 322 // Collect the local values defined by module level asm, and set up 323 // summaries for these symbols so that they can be marked as NoRename, 324 // to prevent export of any use of them in regular IR that would require 325 // renaming within the module level asm. Note we don't need to create a 326 // summary for weak or global defs, as they don't need to be flagged as 327 // NoRename, and defs in module level asm can't be imported anyway. 328 // Also, any values used but not defined within module level asm should 329 // be listed on the llvm.used or llvm.compiler.used global and marked as 330 // referenced from there. 331 ModuleSymbolTable::CollectAsmSymbols( 332 Triple(M.getTargetTriple()), M.getModuleInlineAsm(), 333 [&M, &Index, &CantBePromoted](StringRef Name, 334 object::BasicSymbolRef::Flags Flags) { 335 // Symbols not marked as Weak or Global are local definitions. 336 if (Flags & (object::BasicSymbolRef::SF_Weak | 337 object::BasicSymbolRef::SF_Global)) 338 return; 339 GlobalValue *GV = M.getNamedValue(Name); 340 if (!GV) 341 return; 342 assert(GV->isDeclaration() && "Def in module asm already has definition"); 343 GlobalValueSummary::GVFlags GVFlags(GlobalValue::InternalLinkage, 344 /* NotEligibleToImport */ true, 345 /* LiveRoot */ true, 346 /* AutoHide */ false); 347 CantBePromoted.insert(GlobalValue::getGUID(Name)); 348 // Create the appropriate summary type. 349 if (isa<Function>(GV)) { 350 std::unique_ptr<FunctionSummary> Summary = 351 llvm::make_unique<FunctionSummary>( 352 GVFlags, 0, ArrayRef<ValueInfo>{}, 353 ArrayRef<FunctionSummary::EdgeTy>{}, 354 ArrayRef<GlobalValue::GUID>{}); 355 Index.addGlobalValueSummary(Name, std::move(Summary)); 356 } else { 357 std::unique_ptr<GlobalVarSummary> Summary = 358 llvm::make_unique<GlobalVarSummary>(GVFlags, 359 ArrayRef<ValueInfo>{}); 360 Index.addGlobalValueSummary(Name, std::move(Summary)); 361 } 362 }); 363 } 364 365 for (auto &GlobalList : Index) { 366 assert(GlobalList.second.size() == 1 && 367 "Expected module's index to have one summary per GUID"); 368 auto &Summary = GlobalList.second[0]; 369 bool AllRefsCanBeExternallyReferenced = 370 llvm::all_of(Summary->refs(), [&](const ValueInfo &VI) { 371 return !CantBePromoted.count(VI.getValue()->getGUID()); 372 }); 373 if (!AllRefsCanBeExternallyReferenced) { 374 Summary->setNotEligibleToImport(); 375 continue; 376 } 377 378 if (auto *FuncSummary = dyn_cast<FunctionSummary>(Summary.get())) { 379 bool AllCallsCanBeExternallyReferenced = llvm::all_of( 380 FuncSummary->calls(), [&](const FunctionSummary::EdgeTy &Edge) { 381 auto GUID = Edge.first.isGUID() ? Edge.first.getGUID() 382 : Edge.first.getValue()->getGUID(); 383 return !CantBePromoted.count(GUID); 384 }); 385 if (!AllCallsCanBeExternallyReferenced) 386 Summary->setNotEligibleToImport(); 387 } 388 } 389 390 return Index; 391 } 392 393 AnalysisKey ModuleSummaryIndexAnalysis::Key; 394 395 ModuleSummaryIndex 396 ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) { 397 ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(M); 398 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); 399 return buildModuleSummaryIndex( 400 M, 401 [&FAM](const Function &F) { 402 return &FAM.getResult<BlockFrequencyAnalysis>( 403 *const_cast<Function *>(&F)); 404 }, 405 &PSI); 406 } 407 408 char ModuleSummaryIndexWrapperPass::ID = 0; 409 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis", 410 "Module Summary Analysis", false, true) 411 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) 412 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass) 413 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis", 414 "Module Summary Analysis", false, true) 415 416 ModulePass *llvm::createModuleSummaryIndexWrapperPass() { 417 return new ModuleSummaryIndexWrapperPass(); 418 } 419 420 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass() 421 : ModulePass(ID) { 422 initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry()); 423 } 424 425 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) { 426 auto &PSI = *getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); 427 Index = buildModuleSummaryIndex( 428 M, 429 [this](const Function &F) { 430 return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>( 431 *const_cast<Function *>(&F)) 432 .getBFI()); 433 }, 434 &PSI); 435 return false; 436 } 437 438 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) { 439 Index.reset(); 440 return false; 441 } 442 443 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 444 AU.setPreservesAll(); 445 AU.addRequired<BlockFrequencyInfoWrapperPass>(); 446 AU.addRequired<ProfileSummaryInfoWrapperPass>(); 447 } 448