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/ArrayRef.h" 17 #include "llvm/ADT/DenseSet.h" 18 #include "llvm/ADT/MapVector.h" 19 #include "llvm/ADT/STLExtras.h" 20 #include "llvm/ADT/SetVector.h" 21 #include "llvm/ADT/SmallPtrSet.h" 22 #include "llvm/ADT/SmallVector.h" 23 #include "llvm/ADT/StringRef.h" 24 #include "llvm/Analysis/BlockFrequencyInfo.h" 25 #include "llvm/Analysis/BranchProbabilityInfo.h" 26 #include "llvm/Analysis/IndirectCallPromotionAnalysis.h" 27 #include "llvm/Analysis/LoopInfo.h" 28 #include "llvm/Analysis/ProfileSummaryInfo.h" 29 #include "llvm/Analysis/TypeMetadataUtils.h" 30 #include "llvm/IR/Attributes.h" 31 #include "llvm/IR/BasicBlock.h" 32 #include "llvm/IR/CallSite.h" 33 #include "llvm/IR/Constant.h" 34 #include "llvm/IR/Constants.h" 35 #include "llvm/IR/Dominators.h" 36 #include "llvm/IR/Function.h" 37 #include "llvm/IR/GlobalAlias.h" 38 #include "llvm/IR/GlobalValue.h" 39 #include "llvm/IR/GlobalVariable.h" 40 #include "llvm/IR/Instructions.h" 41 #include "llvm/IR/IntrinsicInst.h" 42 #include "llvm/IR/Intrinsics.h" 43 #include "llvm/IR/Metadata.h" 44 #include "llvm/IR/Module.h" 45 #include "llvm/IR/ModuleSummaryIndex.h" 46 #include "llvm/IR/Use.h" 47 #include "llvm/IR/User.h" 48 #include "llvm/Object/ModuleSymbolTable.h" 49 #include "llvm/Object/SymbolicFile.h" 50 #include "llvm/Pass.h" 51 #include "llvm/Support/Casting.h" 52 #include "llvm/Support/CommandLine.h" 53 #include <algorithm> 54 #include <cassert> 55 #include <cstdint> 56 #include <vector> 57 58 using namespace llvm; 59 60 #define DEBUG_TYPE "module-summary-analysis" 61 62 // Option to force edges cold which will block importing when the 63 // -import-cold-multiplier is set to 0. Useful for debugging. 64 FunctionSummary::ForceSummaryHotnessType ForceSummaryEdgesCold = 65 FunctionSummary::FSHT_None; 66 cl::opt<FunctionSummary::ForceSummaryHotnessType, true> FSEC( 67 "force-summary-edges-cold", cl::Hidden, cl::location(ForceSummaryEdgesCold), 68 cl::desc("Force all edges in the function summary to cold"), 69 cl::values(clEnumValN(FunctionSummary::FSHT_None, "none", "None."), 70 clEnumValN(FunctionSummary::FSHT_AllNonCritical, 71 "all-non-critical", "All non-critical edges."), 72 clEnumValN(FunctionSummary::FSHT_All, "all", "All edges."))); 73 74 // Walk through the operands of a given User via worklist iteration and populate 75 // the set of GlobalValue references encountered. Invoked either on an 76 // Instruction or a GlobalVariable (which walks its initializer). 77 // Return true if any of the operands contains blockaddress. This is important 78 // to know when computing summary for global var, because if global variable 79 // references basic block address we can't import it separately from function 80 // containing that basic block. For simplicity we currently don't import such 81 // global vars at all. When importing function we aren't interested if any 82 // instruction in it takes an address of any basic block, because instruction 83 // can only take an address of basic block located in the same function. 84 static bool findRefEdges(ModuleSummaryIndex &Index, const User *CurUser, 85 SetVector<ValueInfo> &RefEdges, 86 SmallPtrSet<const User *, 8> &Visited) { 87 bool HasBlockAddress = false; 88 SmallVector<const User *, 32> Worklist; 89 Worklist.push_back(CurUser); 90 91 while (!Worklist.empty()) { 92 const User *U = Worklist.pop_back_val(); 93 94 if (!Visited.insert(U).second) 95 continue; 96 97 ImmutableCallSite CS(U); 98 99 for (const auto &OI : U->operands()) { 100 const User *Operand = dyn_cast<User>(OI); 101 if (!Operand) 102 continue; 103 if (isa<BlockAddress>(Operand)) { 104 HasBlockAddress = true; 105 continue; 106 } 107 if (auto *GV = dyn_cast<GlobalValue>(Operand)) { 108 // We have a reference to a global value. This should be added to 109 // the reference set unless it is a callee. Callees are handled 110 // specially by WriteFunction and are added to a separate list. 111 if (!(CS && CS.isCallee(&OI))) 112 RefEdges.insert(Index.getOrInsertValueInfo(GV)); 113 continue; 114 } 115 Worklist.push_back(Operand); 116 } 117 } 118 return HasBlockAddress; 119 } 120 121 static CalleeInfo::HotnessType getHotness(uint64_t ProfileCount, 122 ProfileSummaryInfo *PSI) { 123 if (!PSI) 124 return CalleeInfo::HotnessType::Unknown; 125 if (PSI->isHotCount(ProfileCount)) 126 return CalleeInfo::HotnessType::Hot; 127 if (PSI->isColdCount(ProfileCount)) 128 return CalleeInfo::HotnessType::Cold; 129 return CalleeInfo::HotnessType::None; 130 } 131 132 static bool isNonRenamableLocal(const GlobalValue &GV) { 133 return GV.hasSection() && GV.hasLocalLinkage(); 134 } 135 136 /// Determine whether this call has all constant integer arguments (excluding 137 /// "this") and summarize it to VCalls or ConstVCalls as appropriate. 138 static void addVCallToSet(DevirtCallSite Call, GlobalValue::GUID Guid, 139 SetVector<FunctionSummary::VFuncId> &VCalls, 140 SetVector<FunctionSummary::ConstVCall> &ConstVCalls) { 141 std::vector<uint64_t> Args; 142 // Start from the second argument to skip the "this" pointer. 143 for (auto &Arg : make_range(Call.CS.arg_begin() + 1, Call.CS.arg_end())) { 144 auto *CI = dyn_cast<ConstantInt>(Arg); 145 if (!CI || CI->getBitWidth() > 64) { 146 VCalls.insert({Guid, Call.Offset}); 147 return; 148 } 149 Args.push_back(CI->getZExtValue()); 150 } 151 ConstVCalls.insert({{Guid, Call.Offset}, std::move(Args)}); 152 } 153 154 /// If this intrinsic call requires that we add information to the function 155 /// summary, do so via the non-constant reference arguments. 156 static void addIntrinsicToSummary( 157 const CallInst *CI, SetVector<GlobalValue::GUID> &TypeTests, 158 SetVector<FunctionSummary::VFuncId> &TypeTestAssumeVCalls, 159 SetVector<FunctionSummary::VFuncId> &TypeCheckedLoadVCalls, 160 SetVector<FunctionSummary::ConstVCall> &TypeTestAssumeConstVCalls, 161 SetVector<FunctionSummary::ConstVCall> &TypeCheckedLoadConstVCalls, 162 DominatorTree &DT) { 163 switch (CI->getCalledFunction()->getIntrinsicID()) { 164 case Intrinsic::type_test: { 165 auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(1)); 166 auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata()); 167 if (!TypeId) 168 break; 169 GlobalValue::GUID Guid = GlobalValue::getGUID(TypeId->getString()); 170 171 // Produce a summary from type.test intrinsics. We only summarize type.test 172 // intrinsics that are used other than by an llvm.assume intrinsic. 173 // Intrinsics that are assumed are relevant only to the devirtualization 174 // pass, not the type test lowering pass. 175 bool HasNonAssumeUses = llvm::any_of(CI->uses(), [](const Use &CIU) { 176 auto *AssumeCI = dyn_cast<CallInst>(CIU.getUser()); 177 if (!AssumeCI) 178 return true; 179 Function *F = AssumeCI->getCalledFunction(); 180 return !F || F->getIntrinsicID() != Intrinsic::assume; 181 }); 182 if (HasNonAssumeUses) 183 TypeTests.insert(Guid); 184 185 SmallVector<DevirtCallSite, 4> DevirtCalls; 186 SmallVector<CallInst *, 4> Assumes; 187 findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI, DT); 188 for (auto &Call : DevirtCalls) 189 addVCallToSet(Call, Guid, TypeTestAssumeVCalls, 190 TypeTestAssumeConstVCalls); 191 192 break; 193 } 194 195 case Intrinsic::type_checked_load: { 196 auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(2)); 197 auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata()); 198 if (!TypeId) 199 break; 200 GlobalValue::GUID Guid = GlobalValue::getGUID(TypeId->getString()); 201 202 SmallVector<DevirtCallSite, 4> DevirtCalls; 203 SmallVector<Instruction *, 4> LoadedPtrs; 204 SmallVector<Instruction *, 4> Preds; 205 bool HasNonCallUses = false; 206 findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds, 207 HasNonCallUses, CI, DT); 208 // Any non-call uses of the result of llvm.type.checked.load will 209 // prevent us from optimizing away the llvm.type.test. 210 if (HasNonCallUses) 211 TypeTests.insert(Guid); 212 for (auto &Call : DevirtCalls) 213 addVCallToSet(Call, Guid, TypeCheckedLoadVCalls, 214 TypeCheckedLoadConstVCalls); 215 216 break; 217 } 218 default: 219 break; 220 } 221 } 222 223 static bool isNonVolatileLoad(const Instruction *I) { 224 if (const auto *LI = dyn_cast<LoadInst>(I)) 225 return !LI->isVolatile(); 226 227 return false; 228 } 229 230 static void computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M, 231 const Function &F, BlockFrequencyInfo *BFI, 232 ProfileSummaryInfo *PSI, DominatorTree &DT, 233 bool HasLocalsInUsedOrAsm, 234 DenseSet<GlobalValue::GUID> &CantBePromoted, 235 bool IsThinLTO) { 236 // Summary not currently supported for anonymous functions, they should 237 // have been named. 238 assert(F.hasName()); 239 240 unsigned NumInsts = 0; 241 // Map from callee ValueId to profile count. Used to accumulate profile 242 // counts for all static calls to a given callee. 243 MapVector<ValueInfo, CalleeInfo> CallGraphEdges; 244 SetVector<ValueInfo> RefEdges; 245 SetVector<GlobalValue::GUID> TypeTests; 246 SetVector<FunctionSummary::VFuncId> TypeTestAssumeVCalls, 247 TypeCheckedLoadVCalls; 248 SetVector<FunctionSummary::ConstVCall> TypeTestAssumeConstVCalls, 249 TypeCheckedLoadConstVCalls; 250 ICallPromotionAnalysis ICallAnalysis; 251 SmallPtrSet<const User *, 8> Visited; 252 253 // Add personality function, prefix data and prologue data to function's ref 254 // list. 255 findRefEdges(Index, &F, RefEdges, Visited); 256 std::vector<const Instruction *> NonVolatileLoads; 257 258 bool HasInlineAsmMaybeReferencingInternal = false; 259 for (const BasicBlock &BB : F) 260 for (const Instruction &I : BB) { 261 if (isa<DbgInfoIntrinsic>(I)) 262 continue; 263 ++NumInsts; 264 if (isNonVolatileLoad(&I)) { 265 // Postpone processing of non-volatile load instructions 266 // See comments below 267 Visited.insert(&I); 268 NonVolatileLoads.push_back(&I); 269 continue; 270 } 271 findRefEdges(Index, &I, RefEdges, Visited); 272 auto CS = ImmutableCallSite(&I); 273 if (!CS) 274 continue; 275 276 const auto *CI = dyn_cast<CallInst>(&I); 277 // Since we don't know exactly which local values are referenced in inline 278 // assembly, conservatively mark the function as possibly referencing 279 // a local value from inline assembly to ensure we don't export a 280 // reference (which would require renaming and promotion of the 281 // referenced value). 282 if (HasLocalsInUsedOrAsm && CI && CI->isInlineAsm()) 283 HasInlineAsmMaybeReferencingInternal = true; 284 285 auto *CalledValue = CS.getCalledValue(); 286 auto *CalledFunction = CS.getCalledFunction(); 287 if (CalledValue && !CalledFunction) { 288 CalledValue = CalledValue->stripPointerCastsNoFollowAliases(); 289 // Stripping pointer casts can reveal a called function. 290 CalledFunction = dyn_cast<Function>(CalledValue); 291 } 292 // Check if this is an alias to a function. If so, get the 293 // called aliasee for the checks below. 294 if (auto *GA = dyn_cast<GlobalAlias>(CalledValue)) { 295 assert(!CalledFunction && "Expected null called function in callsite for alias"); 296 CalledFunction = dyn_cast<Function>(GA->getBaseObject()); 297 } 298 // Check if this is a direct call to a known function or a known 299 // intrinsic, or an indirect call with profile data. 300 if (CalledFunction) { 301 if (CI && CalledFunction->isIntrinsic()) { 302 addIntrinsicToSummary( 303 CI, TypeTests, TypeTestAssumeVCalls, TypeCheckedLoadVCalls, 304 TypeTestAssumeConstVCalls, TypeCheckedLoadConstVCalls, DT); 305 continue; 306 } 307 // We should have named any anonymous globals 308 assert(CalledFunction->hasName()); 309 auto ScaledCount = PSI->getProfileCount(&I, BFI); 310 auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI) 311 : CalleeInfo::HotnessType::Unknown; 312 if (ForceSummaryEdgesCold != FunctionSummary::FSHT_None) 313 Hotness = CalleeInfo::HotnessType::Cold; 314 315 // Use the original CalledValue, in case it was an alias. We want 316 // to record the call edge to the alias in that case. Eventually 317 // an alias summary will be created to associate the alias and 318 // aliasee. 319 auto &ValueInfo = CallGraphEdges[Index.getOrInsertValueInfo( 320 cast<GlobalValue>(CalledValue))]; 321 ValueInfo.updateHotness(Hotness); 322 // Add the relative block frequency to CalleeInfo if there is no profile 323 // information. 324 if (BFI != nullptr && Hotness == CalleeInfo::HotnessType::Unknown) { 325 uint64_t BBFreq = BFI->getBlockFreq(&BB).getFrequency(); 326 uint64_t EntryFreq = BFI->getEntryFreq(); 327 ValueInfo.updateRelBlockFreq(BBFreq, EntryFreq); 328 } 329 } else { 330 // Skip inline assembly calls. 331 if (CI && CI->isInlineAsm()) 332 continue; 333 // Skip direct calls. 334 if (!CalledValue || isa<Constant>(CalledValue)) 335 continue; 336 337 // Check if the instruction has a callees metadata. If so, add callees 338 // to CallGraphEdges to reflect the references from the metadata, and 339 // to enable importing for subsequent indirect call promotion and 340 // inlining. 341 if (auto *MD = I.getMetadata(LLVMContext::MD_callees)) { 342 for (auto &Op : MD->operands()) { 343 Function *Callee = mdconst::extract_or_null<Function>(Op); 344 if (Callee) 345 CallGraphEdges[Index.getOrInsertValueInfo(Callee)]; 346 } 347 } 348 349 uint32_t NumVals, NumCandidates; 350 uint64_t TotalCount; 351 auto CandidateProfileData = 352 ICallAnalysis.getPromotionCandidatesForInstruction( 353 &I, NumVals, TotalCount, NumCandidates); 354 for (auto &Candidate : CandidateProfileData) 355 CallGraphEdges[Index.getOrInsertValueInfo(Candidate.Value)] 356 .updateHotness(getHotness(Candidate.Count, PSI)); 357 } 358 } 359 360 // By now we processed all instructions in a function, except 361 // non-volatile loads. All new refs we add in a loop below 362 // are obviously constant. All constant refs are grouped in the 363 // end of RefEdges vector, so we can use a single integer value 364 // to identify them. 365 unsigned RefCnt = RefEdges.size(); 366 for (const Instruction *I : NonVolatileLoads) { 367 Visited.erase(I); 368 findRefEdges(Index, I, RefEdges, Visited); 369 } 370 std::vector<ValueInfo> Refs = RefEdges.takeVector(); 371 // Regular LTO module doesn't participate in ThinLTO import, 372 // so no reference from it can be readonly, since this would 373 // require importing variable as local copy 374 if (IsThinLTO) 375 for (; RefCnt < Refs.size(); ++RefCnt) 376 Refs[RefCnt].setReadOnly(); 377 378 // Explicit add hot edges to enforce importing for designated GUIDs for 379 // sample PGO, to enable the same inlines as the profiled optimized binary. 380 for (auto &I : F.getImportGUIDs()) 381 CallGraphEdges[Index.getOrInsertValueInfo(I)].updateHotness( 382 ForceSummaryEdgesCold == FunctionSummary::FSHT_All 383 ? CalleeInfo::HotnessType::Cold 384 : CalleeInfo::HotnessType::Critical); 385 386 bool NonRenamableLocal = isNonRenamableLocal(F); 387 bool NotEligibleForImport = 388 NonRenamableLocal || HasInlineAsmMaybeReferencingInternal; 389 GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport, 390 /* Live = */ false, F.isDSOLocal()); 391 FunctionSummary::FFlags FunFlags{ 392 F.hasFnAttribute(Attribute::ReadNone), 393 F.hasFnAttribute(Attribute::ReadOnly), 394 F.hasFnAttribute(Attribute::NoRecurse), F.returnDoesNotAlias(), 395 // FIXME: refactor this to use the same code that inliner is using. 396 // Don't try to import functions with noinline attribute. 397 F.getAttributes().hasFnAttribute(Attribute::NoInline)}; 398 auto FuncSummary = llvm::make_unique<FunctionSummary>( 399 Flags, NumInsts, FunFlags, /*EntryCount=*/0, std::move(Refs), 400 CallGraphEdges.takeVector(), TypeTests.takeVector(), 401 TypeTestAssumeVCalls.takeVector(), TypeCheckedLoadVCalls.takeVector(), 402 TypeTestAssumeConstVCalls.takeVector(), 403 TypeCheckedLoadConstVCalls.takeVector()); 404 if (NonRenamableLocal) 405 CantBePromoted.insert(F.getGUID()); 406 Index.addGlobalValueSummary(F, std::move(FuncSummary)); 407 } 408 409 /// Find function pointers referenced within the given vtable initializer 410 /// (or subset of an initializer) \p I. The starting offset of \p I within 411 /// the vtable initializer is \p StartingOffset. Any discovered function 412 /// pointers are added to \p VTableFuncs along with their cumulative offset 413 /// within the initializer. 414 static void findFuncPointers(const Constant *I, uint64_t StartingOffset, 415 const Module &M, ModuleSummaryIndex &Index, 416 VTableFuncList &VTableFuncs) { 417 // First check if this is a function pointer. 418 if (I->getType()->isPointerTy()) { 419 auto Fn = dyn_cast<Function>(I->stripPointerCasts()); 420 // We can disregard __cxa_pure_virtual as a possible call target, as 421 // calls to pure virtuals are UB. 422 if (Fn && Fn->getName() != "__cxa_pure_virtual") 423 VTableFuncs.push_back( 424 std::make_pair(Index.getOrInsertValueInfo(Fn), StartingOffset)); 425 return; 426 } 427 428 // Walk through the elements in the constant struct or array and recursively 429 // look for virtual function pointers. 430 const DataLayout &DL = M.getDataLayout(); 431 if (auto *C = dyn_cast<ConstantStruct>(I)) { 432 StructType *STy = dyn_cast<StructType>(C->getType()); 433 assert(STy); 434 const StructLayout *SL = DL.getStructLayout(C->getType()); 435 436 for (StructType::element_iterator EB = STy->element_begin(), EI = EB, 437 EE = STy->element_end(); 438 EI != EE; ++EI) { 439 auto Offset = SL->getElementOffset(EI - EB); 440 unsigned Op = SL->getElementContainingOffset(Offset); 441 findFuncPointers(cast<Constant>(I->getOperand(Op)), 442 StartingOffset + Offset, M, Index, VTableFuncs); 443 } 444 } else if (auto *C = dyn_cast<ConstantArray>(I)) { 445 ArrayType *ATy = C->getType(); 446 Type *EltTy = ATy->getElementType(); 447 uint64_t EltSize = DL.getTypeAllocSize(EltTy); 448 for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) { 449 findFuncPointers(cast<Constant>(I->getOperand(i)), 450 StartingOffset + i * EltSize, M, Index, VTableFuncs); 451 } 452 } 453 } 454 455 // Identify the function pointers referenced by vtable definition \p V. 456 static void computeVTableFuncs(ModuleSummaryIndex &Index, 457 const GlobalVariable &V, const Module &M, 458 VTableFuncList &VTableFuncs) { 459 if (!V.isConstant()) 460 return; 461 462 findFuncPointers(V.getInitializer(), /*StartingOffset=*/0, M, Index, 463 VTableFuncs); 464 465 #ifndef NDEBUG 466 // Validate that the VTableFuncs list is ordered by offset. 467 uint64_t PrevOffset = 0; 468 for (auto &P : VTableFuncs) { 469 // The findVFuncPointers traversal should have encountered the 470 // functions in offset order. We need to use ">=" since PrevOffset 471 // starts at 0. 472 assert(P.second >= PrevOffset); 473 PrevOffset = P.second; 474 } 475 #endif 476 } 477 478 /// Record vtable definition \p V for each type metadata it references. 479 static void recordTypeIdMetadataReferences(ModuleSummaryIndex &Index, 480 const GlobalVariable &V, 481 SmallVectorImpl<MDNode *> &Types) { 482 for (MDNode *Type : Types) { 483 auto TypeID = Type->getOperand(1).get(); 484 485 uint64_t Offset = 486 cast<ConstantInt>( 487 cast<ConstantAsMetadata>(Type->getOperand(0))->getValue()) 488 ->getZExtValue(); 489 490 if (auto *TypeId = dyn_cast<MDString>(TypeID)) 491 Index.getOrInsertTypeIdMetadataSummary(TypeId->getString()) 492 .push_back({Offset, Index.getOrInsertValueInfo(&V)}); 493 } 494 } 495 496 static void computeVariableSummary(ModuleSummaryIndex &Index, 497 const GlobalVariable &V, 498 DenseSet<GlobalValue::GUID> &CantBePromoted, 499 const Module &M, 500 SmallVectorImpl<MDNode *> &Types) { 501 SetVector<ValueInfo> RefEdges; 502 SmallPtrSet<const User *, 8> Visited; 503 bool HasBlockAddress = findRefEdges(Index, &V, RefEdges, Visited); 504 bool NonRenamableLocal = isNonRenamableLocal(V); 505 GlobalValueSummary::GVFlags Flags(V.getLinkage(), NonRenamableLocal, 506 /* Live = */ false, V.isDSOLocal()); 507 508 VTableFuncList VTableFuncs; 509 // If splitting is not enabled, then we compute the summary information 510 // necessary for index-based whole program devirtualization. 511 if (!Index.enableSplitLTOUnit()) { 512 Types.clear(); 513 V.getMetadata(LLVMContext::MD_type, Types); 514 if (!Types.empty()) { 515 // Identify the function pointers referenced by this vtable definition. 516 computeVTableFuncs(Index, V, M, VTableFuncs); 517 518 // Record this vtable definition for each type metadata it references. 519 recordTypeIdMetadataReferences(Index, V, Types); 520 } 521 } 522 523 // Don't mark variables we won't be able to internalize as read-only. 524 GlobalVarSummary::GVarFlags VarFlags( 525 !V.hasComdat() && !V.hasAppendingLinkage() && !V.isInterposable() && 526 !V.hasAvailableExternallyLinkage() && !V.hasDLLExportStorageClass()); 527 auto GVarSummary = llvm::make_unique<GlobalVarSummary>(Flags, VarFlags, 528 RefEdges.takeVector()); 529 if (NonRenamableLocal) 530 CantBePromoted.insert(V.getGUID()); 531 if (HasBlockAddress) 532 GVarSummary->setNotEligibleToImport(); 533 if (!VTableFuncs.empty()) 534 GVarSummary->setVTableFuncs(VTableFuncs); 535 Index.addGlobalValueSummary(V, std::move(GVarSummary)); 536 } 537 538 static void 539 computeAliasSummary(ModuleSummaryIndex &Index, const GlobalAlias &A, 540 DenseSet<GlobalValue::GUID> &CantBePromoted) { 541 bool NonRenamableLocal = isNonRenamableLocal(A); 542 GlobalValueSummary::GVFlags Flags(A.getLinkage(), NonRenamableLocal, 543 /* Live = */ false, A.isDSOLocal()); 544 auto AS = llvm::make_unique<AliasSummary>(Flags); 545 auto *Aliasee = A.getBaseObject(); 546 auto *AliaseeSummary = Index.getGlobalValueSummary(*Aliasee); 547 assert(AliaseeSummary && "Alias expects aliasee summary to be parsed"); 548 AS->setAliasee(AliaseeSummary); 549 if (NonRenamableLocal) 550 CantBePromoted.insert(A.getGUID()); 551 Index.addGlobalValueSummary(A, std::move(AS)); 552 } 553 554 // Set LiveRoot flag on entries matching the given value name. 555 static void setLiveRoot(ModuleSummaryIndex &Index, StringRef Name) { 556 if (ValueInfo VI = Index.getValueInfo(GlobalValue::getGUID(Name))) 557 for (auto &Summary : VI.getSummaryList()) 558 Summary->setLive(true); 559 } 560 561 ModuleSummaryIndex llvm::buildModuleSummaryIndex( 562 const Module &M, 563 std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback, 564 ProfileSummaryInfo *PSI) { 565 assert(PSI); 566 bool EnableSplitLTOUnit = false; 567 if (auto *MD = mdconst::extract_or_null<ConstantInt>( 568 M.getModuleFlag("EnableSplitLTOUnit"))) 569 EnableSplitLTOUnit = MD->getZExtValue(); 570 ModuleSummaryIndex Index(/*HaveGVs=*/true, EnableSplitLTOUnit); 571 572 // Identify the local values in the llvm.used and llvm.compiler.used sets, 573 // which should not be exported as they would then require renaming and 574 // promotion, but we may have opaque uses e.g. in inline asm. We collect them 575 // here because we use this information to mark functions containing inline 576 // assembly calls as not importable. 577 SmallPtrSet<GlobalValue *, 8> LocalsUsed; 578 SmallPtrSet<GlobalValue *, 8> Used; 579 // First collect those in the llvm.used set. 580 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false); 581 // Next collect those in the llvm.compiler.used set. 582 collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ true); 583 DenseSet<GlobalValue::GUID> CantBePromoted; 584 for (auto *V : Used) { 585 if (V->hasLocalLinkage()) { 586 LocalsUsed.insert(V); 587 CantBePromoted.insert(V->getGUID()); 588 } 589 } 590 591 bool HasLocalInlineAsmSymbol = false; 592 if (!M.getModuleInlineAsm().empty()) { 593 // Collect the local values defined by module level asm, and set up 594 // summaries for these symbols so that they can be marked as NoRename, 595 // to prevent export of any use of them in regular IR that would require 596 // renaming within the module level asm. Note we don't need to create a 597 // summary for weak or global defs, as they don't need to be flagged as 598 // NoRename, and defs in module level asm can't be imported anyway. 599 // Also, any values used but not defined within module level asm should 600 // be listed on the llvm.used or llvm.compiler.used global and marked as 601 // referenced from there. 602 ModuleSymbolTable::CollectAsmSymbols( 603 M, [&](StringRef Name, object::BasicSymbolRef::Flags Flags) { 604 // Symbols not marked as Weak or Global are local definitions. 605 if (Flags & (object::BasicSymbolRef::SF_Weak | 606 object::BasicSymbolRef::SF_Global)) 607 return; 608 HasLocalInlineAsmSymbol = true; 609 GlobalValue *GV = M.getNamedValue(Name); 610 if (!GV) 611 return; 612 assert(GV->isDeclaration() && "Def in module asm already has definition"); 613 GlobalValueSummary::GVFlags GVFlags(GlobalValue::InternalLinkage, 614 /* NotEligibleToImport = */ true, 615 /* Live = */ true, 616 /* Local */ GV->isDSOLocal()); 617 CantBePromoted.insert(GV->getGUID()); 618 // Create the appropriate summary type. 619 if (Function *F = dyn_cast<Function>(GV)) { 620 std::unique_ptr<FunctionSummary> Summary = 621 llvm::make_unique<FunctionSummary>( 622 GVFlags, /*InstCount=*/0, 623 FunctionSummary::FFlags{ 624 F->hasFnAttribute(Attribute::ReadNone), 625 F->hasFnAttribute(Attribute::ReadOnly), 626 F->hasFnAttribute(Attribute::NoRecurse), 627 F->returnDoesNotAlias(), 628 /* NoInline = */ false}, 629 /*EntryCount=*/0, ArrayRef<ValueInfo>{}, 630 ArrayRef<FunctionSummary::EdgeTy>{}, 631 ArrayRef<GlobalValue::GUID>{}, 632 ArrayRef<FunctionSummary::VFuncId>{}, 633 ArrayRef<FunctionSummary::VFuncId>{}, 634 ArrayRef<FunctionSummary::ConstVCall>{}, 635 ArrayRef<FunctionSummary::ConstVCall>{}); 636 Index.addGlobalValueSummary(*GV, std::move(Summary)); 637 } else { 638 std::unique_ptr<GlobalVarSummary> Summary = 639 llvm::make_unique<GlobalVarSummary>( 640 GVFlags, GlobalVarSummary::GVarFlags(), 641 ArrayRef<ValueInfo>{}); 642 Index.addGlobalValueSummary(*GV, std::move(Summary)); 643 } 644 }); 645 } 646 647 bool IsThinLTO = true; 648 if (auto *MD = 649 mdconst::extract_or_null<ConstantInt>(M.getModuleFlag("ThinLTO"))) 650 IsThinLTO = MD->getZExtValue(); 651 652 // Compute summaries for all functions defined in module, and save in the 653 // index. 654 for (auto &F : M) { 655 if (F.isDeclaration()) 656 continue; 657 658 DominatorTree DT(const_cast<Function &>(F)); 659 BlockFrequencyInfo *BFI = nullptr; 660 std::unique_ptr<BlockFrequencyInfo> BFIPtr; 661 if (GetBFICallback) 662 BFI = GetBFICallback(F); 663 else if (F.hasProfileData()) { 664 LoopInfo LI{DT}; 665 BranchProbabilityInfo BPI{F, LI}; 666 BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI); 667 BFI = BFIPtr.get(); 668 } 669 670 computeFunctionSummary(Index, M, F, BFI, PSI, DT, 671 !LocalsUsed.empty() || HasLocalInlineAsmSymbol, 672 CantBePromoted, IsThinLTO); 673 } 674 675 // Compute summaries for all variables defined in module, and save in the 676 // index. 677 SmallVector<MDNode *, 2> Types; 678 for (const GlobalVariable &G : M.globals()) { 679 if (G.isDeclaration()) 680 continue; 681 computeVariableSummary(Index, G, CantBePromoted, M, Types); 682 } 683 684 // Compute summaries for all aliases defined in module, and save in the 685 // index. 686 for (const GlobalAlias &A : M.aliases()) 687 computeAliasSummary(Index, A, CantBePromoted); 688 689 for (auto *V : LocalsUsed) { 690 auto *Summary = Index.getGlobalValueSummary(*V); 691 assert(Summary && "Missing summary for global value"); 692 Summary->setNotEligibleToImport(); 693 } 694 695 // The linker doesn't know about these LLVM produced values, so we need 696 // to flag them as live in the index to ensure index-based dead value 697 // analysis treats them as live roots of the analysis. 698 setLiveRoot(Index, "llvm.used"); 699 setLiveRoot(Index, "llvm.compiler.used"); 700 setLiveRoot(Index, "llvm.global_ctors"); 701 setLiveRoot(Index, "llvm.global_dtors"); 702 setLiveRoot(Index, "llvm.global.annotations"); 703 704 for (auto &GlobalList : Index) { 705 // Ignore entries for references that are undefined in the current module. 706 if (GlobalList.second.SummaryList.empty()) 707 continue; 708 709 assert(GlobalList.second.SummaryList.size() == 1 && 710 "Expected module's index to have one summary per GUID"); 711 auto &Summary = GlobalList.second.SummaryList[0]; 712 if (!IsThinLTO) { 713 Summary->setNotEligibleToImport(); 714 continue; 715 } 716 717 bool AllRefsCanBeExternallyReferenced = 718 llvm::all_of(Summary->refs(), [&](const ValueInfo &VI) { 719 return !CantBePromoted.count(VI.getGUID()); 720 }); 721 if (!AllRefsCanBeExternallyReferenced) { 722 Summary->setNotEligibleToImport(); 723 continue; 724 } 725 726 if (auto *FuncSummary = dyn_cast<FunctionSummary>(Summary.get())) { 727 bool AllCallsCanBeExternallyReferenced = llvm::all_of( 728 FuncSummary->calls(), [&](const FunctionSummary::EdgeTy &Edge) { 729 return !CantBePromoted.count(Edge.first.getGUID()); 730 }); 731 if (!AllCallsCanBeExternallyReferenced) 732 Summary->setNotEligibleToImport(); 733 } 734 } 735 736 return Index; 737 } 738 739 AnalysisKey ModuleSummaryIndexAnalysis::Key; 740 741 ModuleSummaryIndex 742 ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) { 743 ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(M); 744 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); 745 return buildModuleSummaryIndex( 746 M, 747 [&FAM](const Function &F) { 748 return &FAM.getResult<BlockFrequencyAnalysis>( 749 *const_cast<Function *>(&F)); 750 }, 751 &PSI); 752 } 753 754 char ModuleSummaryIndexWrapperPass::ID = 0; 755 756 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis", 757 "Module Summary Analysis", false, true) 758 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) 759 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass) 760 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis", 761 "Module Summary Analysis", false, true) 762 763 ModulePass *llvm::createModuleSummaryIndexWrapperPass() { 764 return new ModuleSummaryIndexWrapperPass(); 765 } 766 767 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass() 768 : ModulePass(ID) { 769 initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry()); 770 } 771 772 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) { 773 auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); 774 Index.emplace(buildModuleSummaryIndex( 775 M, 776 [this](const Function &F) { 777 return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>( 778 *const_cast<Function *>(&F)) 779 .getBFI()); 780 }, 781 PSI)); 782 return false; 783 } 784 785 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) { 786 Index.reset(); 787 return false; 788 } 789 790 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 791 AU.setPreservesAll(); 792 AU.addRequired<BlockFrequencyInfoWrapperPass>(); 793 AU.addRequired<ProfileSummaryInfoWrapperPass>(); 794 } 795