1 //===- ModuleSummaryAnalysis.cpp - Module summary index builder -----------===// 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 pass builds a ModuleSummaryIndex object for the module, to be written 10 // to bitcode or LLVM assembly. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Analysis/ModuleSummaryAnalysis.h" 15 #include "llvm/ADT/ArrayRef.h" 16 #include "llvm/ADT/DenseSet.h" 17 #include "llvm/ADT/MapVector.h" 18 #include "llvm/ADT/STLExtras.h" 19 #include "llvm/ADT/SetVector.h" 20 #include "llvm/ADT/SmallPtrSet.h" 21 #include "llvm/ADT/SmallVector.h" 22 #include "llvm/ADT/StringRef.h" 23 #include "llvm/Analysis/BlockFrequencyInfo.h" 24 #include "llvm/Analysis/BranchProbabilityInfo.h" 25 #include "llvm/Analysis/IndirectCallPromotionAnalysis.h" 26 #include "llvm/Analysis/LoopInfo.h" 27 #include "llvm/Analysis/MemoryProfileInfo.h" 28 #include "llvm/Analysis/ProfileSummaryInfo.h" 29 #include "llvm/Analysis/StackSafetyAnalysis.h" 30 #include "llvm/Analysis/TypeMetadataUtils.h" 31 #include "llvm/IR/Attributes.h" 32 #include "llvm/IR/BasicBlock.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/Metadata.h" 43 #include "llvm/IR/Module.h" 44 #include "llvm/IR/ModuleSummaryIndex.h" 45 #include "llvm/IR/Use.h" 46 #include "llvm/IR/User.h" 47 #include "llvm/InitializePasses.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 "llvm/Support/FileSystem.h" 54 #include <algorithm> 55 #include <cassert> 56 #include <cstdint> 57 #include <vector> 58 59 using namespace llvm; 60 using namespace llvm::memprof; 61 62 #define DEBUG_TYPE "module-summary-analysis" 63 64 // Option to force edges cold which will block importing when the 65 // -import-cold-multiplier is set to 0. Useful for debugging. 66 FunctionSummary::ForceSummaryHotnessType ForceSummaryEdgesCold = 67 FunctionSummary::FSHT_None; 68 cl::opt<FunctionSummary::ForceSummaryHotnessType, true> FSEC( 69 "force-summary-edges-cold", cl::Hidden, cl::location(ForceSummaryEdgesCold), 70 cl::desc("Force all edges in the function summary to cold"), 71 cl::values(clEnumValN(FunctionSummary::FSHT_None, "none", "None."), 72 clEnumValN(FunctionSummary::FSHT_AllNonCritical, 73 "all-non-critical", "All non-critical edges."), 74 clEnumValN(FunctionSummary::FSHT_All, "all", "All edges."))); 75 76 cl::opt<std::string> ModuleSummaryDotFile( 77 "module-summary-dot-file", cl::init(""), cl::Hidden, 78 cl::value_desc("filename"), 79 cl::desc("File to emit dot graph of new summary into.")); 80 81 // Walk through the operands of a given User via worklist iteration and populate 82 // the set of GlobalValue references encountered. Invoked either on an 83 // Instruction or a GlobalVariable (which walks its initializer). 84 // Return true if any of the operands contains blockaddress. This is important 85 // to know when computing summary for global var, because if global variable 86 // references basic block address we can't import it separately from function 87 // containing that basic block. For simplicity we currently don't import such 88 // global vars at all. When importing function we aren't interested if any 89 // instruction in it takes an address of any basic block, because instruction 90 // can only take an address of basic block located in the same function. 91 static bool findRefEdges(ModuleSummaryIndex &Index, const User *CurUser, 92 SetVector<ValueInfo> &RefEdges, 93 SmallPtrSet<const User *, 8> &Visited) { 94 bool HasBlockAddress = false; 95 SmallVector<const User *, 32> Worklist; 96 if (Visited.insert(CurUser).second) 97 Worklist.push_back(CurUser); 98 99 while (!Worklist.empty()) { 100 const User *U = Worklist.pop_back_val(); 101 const auto *CB = dyn_cast<CallBase>(U); 102 103 for (const auto &OI : U->operands()) { 104 const User *Operand = dyn_cast<User>(OI); 105 if (!Operand) 106 continue; 107 if (isa<BlockAddress>(Operand)) { 108 HasBlockAddress = true; 109 continue; 110 } 111 if (auto *GV = dyn_cast<GlobalValue>(Operand)) { 112 // We have a reference to a global value. This should be added to 113 // the reference set unless it is a callee. Callees are handled 114 // specially by WriteFunction and are added to a separate list. 115 if (!(CB && CB->isCallee(&OI))) 116 RefEdges.insert(Index.getOrInsertValueInfo(GV)); 117 continue; 118 } 119 if (Visited.insert(Operand).second) 120 Worklist.push_back(Operand); 121 } 122 } 123 return HasBlockAddress; 124 } 125 126 static CalleeInfo::HotnessType getHotness(uint64_t ProfileCount, 127 ProfileSummaryInfo *PSI) { 128 if (!PSI) 129 return CalleeInfo::HotnessType::Unknown; 130 if (PSI->isHotCount(ProfileCount)) 131 return CalleeInfo::HotnessType::Hot; 132 if (PSI->isColdCount(ProfileCount)) 133 return CalleeInfo::HotnessType::Cold; 134 return CalleeInfo::HotnessType::None; 135 } 136 137 static bool isNonRenamableLocal(const GlobalValue &GV) { 138 return GV.hasSection() && GV.hasLocalLinkage(); 139 } 140 141 /// Determine whether this call has all constant integer arguments (excluding 142 /// "this") and summarize it to VCalls or ConstVCalls as appropriate. 143 static void addVCallToSet(DevirtCallSite Call, GlobalValue::GUID Guid, 144 SetVector<FunctionSummary::VFuncId> &VCalls, 145 SetVector<FunctionSummary::ConstVCall> &ConstVCalls) { 146 std::vector<uint64_t> Args; 147 // Start from the second argument to skip the "this" pointer. 148 for (auto &Arg : drop_begin(Call.CB.args())) { 149 auto *CI = dyn_cast<ConstantInt>(Arg); 150 if (!CI || CI->getBitWidth() > 64) { 151 VCalls.insert({Guid, Call.Offset}); 152 return; 153 } 154 Args.push_back(CI->getZExtValue()); 155 } 156 ConstVCalls.insert({{Guid, Call.Offset}, std::move(Args)}); 157 } 158 159 /// If this intrinsic call requires that we add information to the function 160 /// summary, do so via the non-constant reference arguments. 161 static void addIntrinsicToSummary( 162 const CallInst *CI, SetVector<GlobalValue::GUID> &TypeTests, 163 SetVector<FunctionSummary::VFuncId> &TypeTestAssumeVCalls, 164 SetVector<FunctionSummary::VFuncId> &TypeCheckedLoadVCalls, 165 SetVector<FunctionSummary::ConstVCall> &TypeTestAssumeConstVCalls, 166 SetVector<FunctionSummary::ConstVCall> &TypeCheckedLoadConstVCalls, 167 DominatorTree &DT) { 168 switch (CI->getCalledFunction()->getIntrinsicID()) { 169 case Intrinsic::type_test: 170 case Intrinsic::public_type_test: { 171 auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(1)); 172 auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata()); 173 if (!TypeId) 174 break; 175 GlobalValue::GUID Guid = GlobalValue::getGUID(TypeId->getString()); 176 177 // Produce a summary from type.test intrinsics. We only summarize type.test 178 // intrinsics that are used other than by an llvm.assume intrinsic. 179 // Intrinsics that are assumed are relevant only to the devirtualization 180 // pass, not the type test lowering pass. 181 bool HasNonAssumeUses = llvm::any_of(CI->uses(), [](const Use &CIU) { 182 return !isa<AssumeInst>(CIU.getUser()); 183 }); 184 if (HasNonAssumeUses) 185 TypeTests.insert(Guid); 186 187 SmallVector<DevirtCallSite, 4> DevirtCalls; 188 SmallVector<CallInst *, 4> Assumes; 189 findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI, DT); 190 for (auto &Call : DevirtCalls) 191 addVCallToSet(Call, Guid, TypeTestAssumeVCalls, 192 TypeTestAssumeConstVCalls); 193 194 break; 195 } 196 197 case Intrinsic::type_checked_load: { 198 auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(2)); 199 auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata()); 200 if (!TypeId) 201 break; 202 GlobalValue::GUID Guid = GlobalValue::getGUID(TypeId->getString()); 203 204 SmallVector<DevirtCallSite, 4> DevirtCalls; 205 SmallVector<Instruction *, 4> LoadedPtrs; 206 SmallVector<Instruction *, 4> Preds; 207 bool HasNonCallUses = false; 208 findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds, 209 HasNonCallUses, CI, DT); 210 // Any non-call uses of the result of llvm.type.checked.load will 211 // prevent us from optimizing away the llvm.type.test. 212 if (HasNonCallUses) 213 TypeTests.insert(Guid); 214 for (auto &Call : DevirtCalls) 215 addVCallToSet(Call, Guid, TypeCheckedLoadVCalls, 216 TypeCheckedLoadConstVCalls); 217 218 break; 219 } 220 default: 221 break; 222 } 223 } 224 225 static bool isNonVolatileLoad(const Instruction *I) { 226 if (const auto *LI = dyn_cast<LoadInst>(I)) 227 return !LI->isVolatile(); 228 229 return false; 230 } 231 232 static bool isNonVolatileStore(const Instruction *I) { 233 if (const auto *SI = dyn_cast<StoreInst>(I)) 234 return !SI->isVolatile(); 235 236 return false; 237 } 238 239 // Returns true if the function definition must be unreachable. 240 // 241 // Note if this helper function returns true, `F` is guaranteed 242 // to be unreachable; if it returns false, `F` might still 243 // be unreachable but not covered by this helper function. 244 static bool mustBeUnreachableFunction(const Function &F) { 245 // A function must be unreachable if its entry block ends with an 246 // 'unreachable'. 247 assert(!F.isDeclaration()); 248 return isa<UnreachableInst>(F.getEntryBlock().getTerminator()); 249 } 250 251 static void computeFunctionSummary( 252 ModuleSummaryIndex &Index, const Module &M, const Function &F, 253 BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, DominatorTree &DT, 254 bool HasLocalsInUsedOrAsm, DenseSet<GlobalValue::GUID> &CantBePromoted, 255 bool IsThinLTO, 256 std::function<const StackSafetyInfo *(const Function &F)> GetSSICallback) { 257 // Summary not currently supported for anonymous functions, they should 258 // have been named. 259 assert(F.hasName()); 260 261 unsigned NumInsts = 0; 262 // Map from callee ValueId to profile count. Used to accumulate profile 263 // counts for all static calls to a given callee. 264 MapVector<ValueInfo, CalleeInfo> CallGraphEdges; 265 SetVector<ValueInfo> RefEdges, LoadRefEdges, StoreRefEdges; 266 SetVector<GlobalValue::GUID> TypeTests; 267 SetVector<FunctionSummary::VFuncId> TypeTestAssumeVCalls, 268 TypeCheckedLoadVCalls; 269 SetVector<FunctionSummary::ConstVCall> TypeTestAssumeConstVCalls, 270 TypeCheckedLoadConstVCalls; 271 ICallPromotionAnalysis ICallAnalysis; 272 SmallPtrSet<const User *, 8> Visited; 273 274 // Add personality function, prefix data and prologue data to function's ref 275 // list. 276 findRefEdges(Index, &F, RefEdges, Visited); 277 std::vector<const Instruction *> NonVolatileLoads; 278 std::vector<const Instruction *> NonVolatileStores; 279 280 std::vector<CallsiteInfo> Callsites; 281 std::vector<AllocInfo> Allocs; 282 283 bool HasInlineAsmMaybeReferencingInternal = false; 284 bool HasIndirBranchToBlockAddress = false; 285 bool HasUnknownCall = false; 286 bool MayThrow = false; 287 for (const BasicBlock &BB : F) { 288 // We don't allow inlining of function with indirect branch to blockaddress. 289 // If the blockaddress escapes the function, e.g., via a global variable, 290 // inlining may lead to an invalid cross-function reference. So we shouldn't 291 // import such function either. 292 if (BB.hasAddressTaken()) { 293 for (User *U : BlockAddress::get(const_cast<BasicBlock *>(&BB))->users()) 294 if (!isa<CallBrInst>(*U)) { 295 HasIndirBranchToBlockAddress = true; 296 break; 297 } 298 } 299 300 for (const Instruction &I : BB) { 301 if (I.isDebugOrPseudoInst()) 302 continue; 303 ++NumInsts; 304 305 // Regular LTO module doesn't participate in ThinLTO import, 306 // so no reference from it can be read/writeonly, since this 307 // would require importing variable as local copy 308 if (IsThinLTO) { 309 if (isNonVolatileLoad(&I)) { 310 // Postpone processing of non-volatile load instructions 311 // See comments below 312 Visited.insert(&I); 313 NonVolatileLoads.push_back(&I); 314 continue; 315 } else if (isNonVolatileStore(&I)) { 316 Visited.insert(&I); 317 NonVolatileStores.push_back(&I); 318 // All references from second operand of store (destination address) 319 // can be considered write-only if they're not referenced by any 320 // non-store instruction. References from first operand of store 321 // (stored value) can't be treated either as read- or as write-only 322 // so we add them to RefEdges as we do with all other instructions 323 // except non-volatile load. 324 Value *Stored = I.getOperand(0); 325 if (auto *GV = dyn_cast<GlobalValue>(Stored)) 326 // findRefEdges will try to examine GV operands, so instead 327 // of calling it we should add GV to RefEdges directly. 328 RefEdges.insert(Index.getOrInsertValueInfo(GV)); 329 else if (auto *U = dyn_cast<User>(Stored)) 330 findRefEdges(Index, U, RefEdges, Visited); 331 continue; 332 } 333 } 334 findRefEdges(Index, &I, RefEdges, Visited); 335 const auto *CB = dyn_cast<CallBase>(&I); 336 if (!CB) { 337 if (I.mayThrow()) 338 MayThrow = true; 339 continue; 340 } 341 342 const auto *CI = dyn_cast<CallInst>(&I); 343 // Since we don't know exactly which local values are referenced in inline 344 // assembly, conservatively mark the function as possibly referencing 345 // a local value from inline assembly to ensure we don't export a 346 // reference (which would require renaming and promotion of the 347 // referenced value). 348 if (HasLocalsInUsedOrAsm && CI && CI->isInlineAsm()) 349 HasInlineAsmMaybeReferencingInternal = true; 350 351 auto *CalledValue = CB->getCalledOperand(); 352 auto *CalledFunction = CB->getCalledFunction(); 353 if (CalledValue && !CalledFunction) { 354 CalledValue = CalledValue->stripPointerCasts(); 355 // Stripping pointer casts can reveal a called function. 356 CalledFunction = dyn_cast<Function>(CalledValue); 357 } 358 // Check if this is an alias to a function. If so, get the 359 // called aliasee for the checks below. 360 if (auto *GA = dyn_cast<GlobalAlias>(CalledValue)) { 361 assert(!CalledFunction && "Expected null called function in callsite for alias"); 362 CalledFunction = dyn_cast<Function>(GA->getAliaseeObject()); 363 } 364 // Check if this is a direct call to a known function or a known 365 // intrinsic, or an indirect call with profile data. 366 if (CalledFunction) { 367 if (CI && CalledFunction->isIntrinsic()) { 368 addIntrinsicToSummary( 369 CI, TypeTests, TypeTestAssumeVCalls, TypeCheckedLoadVCalls, 370 TypeTestAssumeConstVCalls, TypeCheckedLoadConstVCalls, DT); 371 continue; 372 } 373 // We should have named any anonymous globals 374 assert(CalledFunction->hasName()); 375 auto ScaledCount = PSI->getProfileCount(*CB, BFI); 376 auto Hotness = ScaledCount ? getHotness(*ScaledCount, PSI) 377 : CalleeInfo::HotnessType::Unknown; 378 if (ForceSummaryEdgesCold != FunctionSummary::FSHT_None) 379 Hotness = CalleeInfo::HotnessType::Cold; 380 381 // Use the original CalledValue, in case it was an alias. We want 382 // to record the call edge to the alias in that case. Eventually 383 // an alias summary will be created to associate the alias and 384 // aliasee. 385 auto &ValueInfo = CallGraphEdges[Index.getOrInsertValueInfo( 386 cast<GlobalValue>(CalledValue))]; 387 ValueInfo.updateHotness(Hotness); 388 // Add the relative block frequency to CalleeInfo if there is no profile 389 // information. 390 if (BFI != nullptr && Hotness == CalleeInfo::HotnessType::Unknown) { 391 uint64_t BBFreq = BFI->getBlockFreq(&BB).getFrequency(); 392 uint64_t EntryFreq = BFI->getEntryFreq(); 393 ValueInfo.updateRelBlockFreq(BBFreq, EntryFreq); 394 } 395 } else { 396 HasUnknownCall = true; 397 // Skip inline assembly calls. 398 if (CI && CI->isInlineAsm()) 399 continue; 400 // Skip direct calls. 401 if (!CalledValue || isa<Constant>(CalledValue)) 402 continue; 403 404 // Check if the instruction has a callees metadata. If so, add callees 405 // to CallGraphEdges to reflect the references from the metadata, and 406 // to enable importing for subsequent indirect call promotion and 407 // inlining. 408 if (auto *MD = I.getMetadata(LLVMContext::MD_callees)) { 409 for (const auto &Op : MD->operands()) { 410 Function *Callee = mdconst::extract_or_null<Function>(Op); 411 if (Callee) 412 CallGraphEdges[Index.getOrInsertValueInfo(Callee)]; 413 } 414 } 415 416 uint32_t NumVals, NumCandidates; 417 uint64_t TotalCount; 418 auto CandidateProfileData = 419 ICallAnalysis.getPromotionCandidatesForInstruction( 420 &I, NumVals, TotalCount, NumCandidates); 421 for (const auto &Candidate : CandidateProfileData) 422 CallGraphEdges[Index.getOrInsertValueInfo(Candidate.Value)] 423 .updateHotness(getHotness(Candidate.Count, PSI)); 424 } 425 426 // TODO: Skip indirect calls for now. Need to handle these better, likely 427 // by creating multiple Callsites, one per target, then speculatively 428 // devirtualize while applying clone info in the ThinLTO backends. This 429 // will also be important because we will have a different set of clone 430 // versions per target. This handling needs to match that in the ThinLTO 431 // backend so we handle things consistently for matching of callsite 432 // summaries to instructions. 433 if (!CalledFunction) 434 continue; 435 436 // Compute the list of stack ids first (so we can trim them from the stack 437 // ids on any MIBs). 438 CallStack<MDNode, MDNode::op_iterator> InstCallsite( 439 I.getMetadata(LLVMContext::MD_callsite)); 440 auto *MemProfMD = I.getMetadata(LLVMContext::MD_memprof); 441 if (MemProfMD) { 442 std::vector<MIBInfo> MIBs; 443 for (auto &MDOp : MemProfMD->operands()) { 444 auto *MIBMD = cast<const MDNode>(MDOp); 445 MDNode *StackNode = getMIBStackNode(MIBMD); 446 assert(StackNode); 447 SmallVector<unsigned> StackIdIndices; 448 CallStack<MDNode, MDNode::op_iterator> StackContext(StackNode); 449 // Collapse out any on the allocation call (inlining). 450 for (auto ContextIter = 451 StackContext.beginAfterSharedPrefix(InstCallsite); 452 ContextIter != StackContext.end(); ++ContextIter) { 453 unsigned StackIdIdx = Index.addOrGetStackIdIndex(*ContextIter); 454 // If this is a direct recursion, simply skip the duplicate 455 // entries. If this is mutual recursion, handling is left to 456 // the LTO link analysis client. 457 if (StackIdIndices.empty() || StackIdIndices.back() != StackIdIdx) 458 StackIdIndices.push_back(StackIdIdx); 459 } 460 MIBs.push_back( 461 MIBInfo(getMIBAllocType(MIBMD), std::move(StackIdIndices))); 462 } 463 Allocs.push_back(AllocInfo(std::move(MIBs))); 464 } else if (!InstCallsite.empty()) { 465 SmallVector<unsigned> StackIdIndices; 466 for (auto StackId : InstCallsite) 467 StackIdIndices.push_back(Index.addOrGetStackIdIndex(StackId)); 468 // Use the original CalledValue, in case it was an alias. We want 469 // to record the call edge to the alias in that case. Eventually 470 // an alias summary will be created to associate the alias and 471 // aliasee. 472 auto CalleeValueInfo = 473 Index.getOrInsertValueInfo(cast<GlobalValue>(CalledValue)); 474 Callsites.push_back({CalleeValueInfo, StackIdIndices}); 475 } 476 } 477 } 478 Index.addBlockCount(F.size()); 479 480 std::vector<ValueInfo> Refs; 481 if (IsThinLTO) { 482 auto AddRefEdges = [&](const std::vector<const Instruction *> &Instrs, 483 SetVector<ValueInfo> &Edges, 484 SmallPtrSet<const User *, 8> &Cache) { 485 for (const auto *I : Instrs) { 486 Cache.erase(I); 487 findRefEdges(Index, I, Edges, Cache); 488 } 489 }; 490 491 // By now we processed all instructions in a function, except 492 // non-volatile loads and non-volatile value stores. Let's find 493 // ref edges for both of instruction sets 494 AddRefEdges(NonVolatileLoads, LoadRefEdges, Visited); 495 // We can add some values to the Visited set when processing load 496 // instructions which are also used by stores in NonVolatileStores. 497 // For example this can happen if we have following code: 498 // 499 // store %Derived* @foo, %Derived** bitcast (%Base** @bar to %Derived**) 500 // %42 = load %Derived*, %Derived** bitcast (%Base** @bar to %Derived**) 501 // 502 // After processing loads we'll add bitcast to the Visited set, and if 503 // we use the same set while processing stores, we'll never see store 504 // to @bar and @bar will be mistakenly treated as readonly. 505 SmallPtrSet<const llvm::User *, 8> StoreCache; 506 AddRefEdges(NonVolatileStores, StoreRefEdges, StoreCache); 507 508 // If both load and store instruction reference the same variable 509 // we won't be able to optimize it. Add all such reference edges 510 // to RefEdges set. 511 for (const auto &VI : StoreRefEdges) 512 if (LoadRefEdges.remove(VI)) 513 RefEdges.insert(VI); 514 515 unsigned RefCnt = RefEdges.size(); 516 // All new reference edges inserted in two loops below are either 517 // read or write only. They will be grouped in the end of RefEdges 518 // vector, so we can use a single integer value to identify them. 519 for (const auto &VI : LoadRefEdges) 520 RefEdges.insert(VI); 521 522 unsigned FirstWORef = RefEdges.size(); 523 for (const auto &VI : StoreRefEdges) 524 RefEdges.insert(VI); 525 526 Refs = RefEdges.takeVector(); 527 for (; RefCnt < FirstWORef; ++RefCnt) 528 Refs[RefCnt].setReadOnly(); 529 530 for (; RefCnt < Refs.size(); ++RefCnt) 531 Refs[RefCnt].setWriteOnly(); 532 } else { 533 Refs = RefEdges.takeVector(); 534 } 535 // Explicit add hot edges to enforce importing for designated GUIDs for 536 // sample PGO, to enable the same inlines as the profiled optimized binary. 537 for (auto &I : F.getImportGUIDs()) 538 CallGraphEdges[Index.getOrInsertValueInfo(I)].updateHotness( 539 ForceSummaryEdgesCold == FunctionSummary::FSHT_All 540 ? CalleeInfo::HotnessType::Cold 541 : CalleeInfo::HotnessType::Critical); 542 543 bool NonRenamableLocal = isNonRenamableLocal(F); 544 bool NotEligibleForImport = NonRenamableLocal || 545 HasInlineAsmMaybeReferencingInternal || 546 HasIndirBranchToBlockAddress; 547 GlobalValueSummary::GVFlags Flags( 548 F.getLinkage(), F.getVisibility(), NotEligibleForImport, 549 /* Live = */ false, F.isDSOLocal(), F.canBeOmittedFromSymbolTable()); 550 FunctionSummary::FFlags FunFlags{ 551 F.doesNotAccessMemory(), F.onlyReadsMemory() && !F.doesNotAccessMemory(), 552 F.hasFnAttribute(Attribute::NoRecurse), F.returnDoesNotAlias(), 553 // FIXME: refactor this to use the same code that inliner is using. 554 // Don't try to import functions with noinline attribute. 555 F.getAttributes().hasFnAttr(Attribute::NoInline), 556 F.hasFnAttribute(Attribute::AlwaysInline), 557 F.hasFnAttribute(Attribute::NoUnwind), MayThrow, HasUnknownCall, 558 mustBeUnreachableFunction(F)}; 559 std::vector<FunctionSummary::ParamAccess> ParamAccesses; 560 if (auto *SSI = GetSSICallback(F)) 561 ParamAccesses = SSI->getParamAccesses(Index); 562 auto FuncSummary = std::make_unique<FunctionSummary>( 563 Flags, NumInsts, FunFlags, /*EntryCount=*/0, std::move(Refs), 564 CallGraphEdges.takeVector(), TypeTests.takeVector(), 565 TypeTestAssumeVCalls.takeVector(), TypeCheckedLoadVCalls.takeVector(), 566 TypeTestAssumeConstVCalls.takeVector(), 567 TypeCheckedLoadConstVCalls.takeVector(), std::move(ParamAccesses), 568 std::move(Callsites), std::move(Allocs)); 569 if (NonRenamableLocal) 570 CantBePromoted.insert(F.getGUID()); 571 Index.addGlobalValueSummary(F, std::move(FuncSummary)); 572 } 573 574 /// Find function pointers referenced within the given vtable initializer 575 /// (or subset of an initializer) \p I. The starting offset of \p I within 576 /// the vtable initializer is \p StartingOffset. Any discovered function 577 /// pointers are added to \p VTableFuncs along with their cumulative offset 578 /// within the initializer. 579 static void findFuncPointers(const Constant *I, uint64_t StartingOffset, 580 const Module &M, ModuleSummaryIndex &Index, 581 VTableFuncList &VTableFuncs) { 582 // First check if this is a function pointer. 583 if (I->getType()->isPointerTy()) { 584 auto Fn = dyn_cast<Function>(I->stripPointerCasts()); 585 // We can disregard __cxa_pure_virtual as a possible call target, as 586 // calls to pure virtuals are UB. 587 if (Fn && Fn->getName() != "__cxa_pure_virtual") 588 VTableFuncs.push_back({Index.getOrInsertValueInfo(Fn), StartingOffset}); 589 return; 590 } 591 592 // Walk through the elements in the constant struct or array and recursively 593 // look for virtual function pointers. 594 const DataLayout &DL = M.getDataLayout(); 595 if (auto *C = dyn_cast<ConstantStruct>(I)) { 596 StructType *STy = dyn_cast<StructType>(C->getType()); 597 assert(STy); 598 const StructLayout *SL = DL.getStructLayout(C->getType()); 599 600 for (auto EI : llvm::enumerate(STy->elements())) { 601 auto Offset = SL->getElementOffset(EI.index()); 602 unsigned Op = SL->getElementContainingOffset(Offset); 603 findFuncPointers(cast<Constant>(I->getOperand(Op)), 604 StartingOffset + Offset, M, Index, VTableFuncs); 605 } 606 } else if (auto *C = dyn_cast<ConstantArray>(I)) { 607 ArrayType *ATy = C->getType(); 608 Type *EltTy = ATy->getElementType(); 609 uint64_t EltSize = DL.getTypeAllocSize(EltTy); 610 for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) { 611 findFuncPointers(cast<Constant>(I->getOperand(i)), 612 StartingOffset + i * EltSize, M, Index, VTableFuncs); 613 } 614 } 615 } 616 617 // Identify the function pointers referenced by vtable definition \p V. 618 static void computeVTableFuncs(ModuleSummaryIndex &Index, 619 const GlobalVariable &V, const Module &M, 620 VTableFuncList &VTableFuncs) { 621 if (!V.isConstant()) 622 return; 623 624 findFuncPointers(V.getInitializer(), /*StartingOffset=*/0, M, Index, 625 VTableFuncs); 626 627 #ifndef NDEBUG 628 // Validate that the VTableFuncs list is ordered by offset. 629 uint64_t PrevOffset = 0; 630 for (auto &P : VTableFuncs) { 631 // The findVFuncPointers traversal should have encountered the 632 // functions in offset order. We need to use ">=" since PrevOffset 633 // starts at 0. 634 assert(P.VTableOffset >= PrevOffset); 635 PrevOffset = P.VTableOffset; 636 } 637 #endif 638 } 639 640 /// Record vtable definition \p V for each type metadata it references. 641 static void 642 recordTypeIdCompatibleVtableReferences(ModuleSummaryIndex &Index, 643 const GlobalVariable &V, 644 SmallVectorImpl<MDNode *> &Types) { 645 for (MDNode *Type : Types) { 646 auto TypeID = Type->getOperand(1).get(); 647 648 uint64_t Offset = 649 cast<ConstantInt>( 650 cast<ConstantAsMetadata>(Type->getOperand(0))->getValue()) 651 ->getZExtValue(); 652 653 if (auto *TypeId = dyn_cast<MDString>(TypeID)) 654 Index.getOrInsertTypeIdCompatibleVtableSummary(TypeId->getString()) 655 .push_back({Offset, Index.getOrInsertValueInfo(&V)}); 656 } 657 } 658 659 static void computeVariableSummary(ModuleSummaryIndex &Index, 660 const GlobalVariable &V, 661 DenseSet<GlobalValue::GUID> &CantBePromoted, 662 const Module &M, 663 SmallVectorImpl<MDNode *> &Types) { 664 SetVector<ValueInfo> RefEdges; 665 SmallPtrSet<const User *, 8> Visited; 666 bool HasBlockAddress = findRefEdges(Index, &V, RefEdges, Visited); 667 bool NonRenamableLocal = isNonRenamableLocal(V); 668 GlobalValueSummary::GVFlags Flags( 669 V.getLinkage(), V.getVisibility(), NonRenamableLocal, 670 /* Live = */ false, V.isDSOLocal(), V.canBeOmittedFromSymbolTable()); 671 672 VTableFuncList VTableFuncs; 673 // If splitting is not enabled, then we compute the summary information 674 // necessary for index-based whole program devirtualization. 675 if (!Index.enableSplitLTOUnit()) { 676 Types.clear(); 677 V.getMetadata(LLVMContext::MD_type, Types); 678 if (!Types.empty()) { 679 // Identify the function pointers referenced by this vtable definition. 680 computeVTableFuncs(Index, V, M, VTableFuncs); 681 682 // Record this vtable definition for each type metadata it references. 683 recordTypeIdCompatibleVtableReferences(Index, V, Types); 684 } 685 } 686 687 // Don't mark variables we won't be able to internalize as read/write-only. 688 bool CanBeInternalized = 689 !V.hasComdat() && !V.hasAppendingLinkage() && !V.isInterposable() && 690 !V.hasAvailableExternallyLinkage() && !V.hasDLLExportStorageClass(); 691 bool Constant = V.isConstant(); 692 GlobalVarSummary::GVarFlags VarFlags(CanBeInternalized, 693 Constant ? false : CanBeInternalized, 694 Constant, V.getVCallVisibility()); 695 auto GVarSummary = std::make_unique<GlobalVarSummary>(Flags, VarFlags, 696 RefEdges.takeVector()); 697 if (NonRenamableLocal) 698 CantBePromoted.insert(V.getGUID()); 699 if (HasBlockAddress) 700 GVarSummary->setNotEligibleToImport(); 701 if (!VTableFuncs.empty()) 702 GVarSummary->setVTableFuncs(VTableFuncs); 703 Index.addGlobalValueSummary(V, std::move(GVarSummary)); 704 } 705 706 static void computeAliasSummary(ModuleSummaryIndex &Index, const GlobalAlias &A, 707 DenseSet<GlobalValue::GUID> &CantBePromoted) { 708 // Skip summary for indirect function aliases as summary for aliasee will not 709 // be emitted. 710 const GlobalObject *Aliasee = A.getAliaseeObject(); 711 if (isa<GlobalIFunc>(Aliasee)) 712 return; 713 bool NonRenamableLocal = isNonRenamableLocal(A); 714 GlobalValueSummary::GVFlags Flags( 715 A.getLinkage(), A.getVisibility(), NonRenamableLocal, 716 /* Live = */ false, A.isDSOLocal(), A.canBeOmittedFromSymbolTable()); 717 auto AS = std::make_unique<AliasSummary>(Flags); 718 auto AliaseeVI = Index.getValueInfo(Aliasee->getGUID()); 719 assert(AliaseeVI && "Alias expects aliasee summary to be available"); 720 assert(AliaseeVI.getSummaryList().size() == 1 && 721 "Expected a single entry per aliasee in per-module index"); 722 AS->setAliasee(AliaseeVI, AliaseeVI.getSummaryList()[0].get()); 723 if (NonRenamableLocal) 724 CantBePromoted.insert(A.getGUID()); 725 Index.addGlobalValueSummary(A, std::move(AS)); 726 } 727 728 // Set LiveRoot flag on entries matching the given value name. 729 static void setLiveRoot(ModuleSummaryIndex &Index, StringRef Name) { 730 if (ValueInfo VI = Index.getValueInfo(GlobalValue::getGUID(Name))) 731 for (const auto &Summary : VI.getSummaryList()) 732 Summary->setLive(true); 733 } 734 735 ModuleSummaryIndex llvm::buildModuleSummaryIndex( 736 const Module &M, 737 std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback, 738 ProfileSummaryInfo *PSI, 739 std::function<const StackSafetyInfo *(const Function &F)> GetSSICallback) { 740 assert(PSI); 741 bool EnableSplitLTOUnit = false; 742 if (auto *MD = mdconst::extract_or_null<ConstantInt>( 743 M.getModuleFlag("EnableSplitLTOUnit"))) 744 EnableSplitLTOUnit = MD->getZExtValue(); 745 ModuleSummaryIndex Index(/*HaveGVs=*/true, EnableSplitLTOUnit); 746 747 // Identify the local values in the llvm.used and llvm.compiler.used sets, 748 // which should not be exported as they would then require renaming and 749 // promotion, but we may have opaque uses e.g. in inline asm. We collect them 750 // here because we use this information to mark functions containing inline 751 // assembly calls as not importable. 752 SmallPtrSet<GlobalValue *, 4> LocalsUsed; 753 SmallVector<GlobalValue *, 4> Used; 754 // First collect those in the llvm.used set. 755 collectUsedGlobalVariables(M, Used, /*CompilerUsed=*/false); 756 // Next collect those in the llvm.compiler.used set. 757 collectUsedGlobalVariables(M, Used, /*CompilerUsed=*/true); 758 DenseSet<GlobalValue::GUID> CantBePromoted; 759 for (auto *V : Used) { 760 if (V->hasLocalLinkage()) { 761 LocalsUsed.insert(V); 762 CantBePromoted.insert(V->getGUID()); 763 } 764 } 765 766 bool HasLocalInlineAsmSymbol = false; 767 if (!M.getModuleInlineAsm().empty()) { 768 // Collect the local values defined by module level asm, and set up 769 // summaries for these symbols so that they can be marked as NoRename, 770 // to prevent export of any use of them in regular IR that would require 771 // renaming within the module level asm. Note we don't need to create a 772 // summary for weak or global defs, as they don't need to be flagged as 773 // NoRename, and defs in module level asm can't be imported anyway. 774 // Also, any values used but not defined within module level asm should 775 // be listed on the llvm.used or llvm.compiler.used global and marked as 776 // referenced from there. 777 ModuleSymbolTable::CollectAsmSymbols( 778 M, [&](StringRef Name, object::BasicSymbolRef::Flags Flags) { 779 // Symbols not marked as Weak or Global are local definitions. 780 if (Flags & (object::BasicSymbolRef::SF_Weak | 781 object::BasicSymbolRef::SF_Global)) 782 return; 783 HasLocalInlineAsmSymbol = true; 784 GlobalValue *GV = M.getNamedValue(Name); 785 if (!GV) 786 return; 787 assert(GV->isDeclaration() && "Def in module asm already has definition"); 788 GlobalValueSummary::GVFlags GVFlags( 789 GlobalValue::InternalLinkage, GlobalValue::DefaultVisibility, 790 /* NotEligibleToImport = */ true, 791 /* Live = */ true, 792 /* Local */ GV->isDSOLocal(), GV->canBeOmittedFromSymbolTable()); 793 CantBePromoted.insert(GV->getGUID()); 794 // Create the appropriate summary type. 795 if (Function *F = dyn_cast<Function>(GV)) { 796 std::unique_ptr<FunctionSummary> Summary = 797 std::make_unique<FunctionSummary>( 798 GVFlags, /*InstCount=*/0, 799 FunctionSummary::FFlags{ 800 F->hasFnAttribute(Attribute::ReadNone), 801 F->hasFnAttribute(Attribute::ReadOnly), 802 F->hasFnAttribute(Attribute::NoRecurse), 803 F->returnDoesNotAlias(), 804 /* NoInline = */ false, 805 F->hasFnAttribute(Attribute::AlwaysInline), 806 F->hasFnAttribute(Attribute::NoUnwind), 807 /* MayThrow */ true, 808 /* HasUnknownCall */ true, 809 /* MustBeUnreachable */ false}, 810 /*EntryCount=*/0, ArrayRef<ValueInfo>{}, 811 ArrayRef<FunctionSummary::EdgeTy>{}, 812 ArrayRef<GlobalValue::GUID>{}, 813 ArrayRef<FunctionSummary::VFuncId>{}, 814 ArrayRef<FunctionSummary::VFuncId>{}, 815 ArrayRef<FunctionSummary::ConstVCall>{}, 816 ArrayRef<FunctionSummary::ConstVCall>{}, 817 ArrayRef<FunctionSummary::ParamAccess>{}, 818 ArrayRef<CallsiteInfo>{}, ArrayRef<AllocInfo>{}); 819 Index.addGlobalValueSummary(*GV, std::move(Summary)); 820 } else { 821 std::unique_ptr<GlobalVarSummary> Summary = 822 std::make_unique<GlobalVarSummary>( 823 GVFlags, 824 GlobalVarSummary::GVarFlags( 825 false, false, cast<GlobalVariable>(GV)->isConstant(), 826 GlobalObject::VCallVisibilityPublic), 827 ArrayRef<ValueInfo>{}); 828 Index.addGlobalValueSummary(*GV, std::move(Summary)); 829 } 830 }); 831 } 832 833 bool IsThinLTO = true; 834 if (auto *MD = 835 mdconst::extract_or_null<ConstantInt>(M.getModuleFlag("ThinLTO"))) 836 IsThinLTO = MD->getZExtValue(); 837 838 // Compute summaries for all functions defined in module, and save in the 839 // index. 840 for (const auto &F : M) { 841 if (F.isDeclaration()) 842 continue; 843 844 DominatorTree DT(const_cast<Function &>(F)); 845 BlockFrequencyInfo *BFI = nullptr; 846 std::unique_ptr<BlockFrequencyInfo> BFIPtr; 847 if (GetBFICallback) 848 BFI = GetBFICallback(F); 849 else if (F.hasProfileData()) { 850 LoopInfo LI{DT}; 851 BranchProbabilityInfo BPI{F, LI}; 852 BFIPtr = std::make_unique<BlockFrequencyInfo>(F, BPI, LI); 853 BFI = BFIPtr.get(); 854 } 855 856 computeFunctionSummary(Index, M, F, BFI, PSI, DT, 857 !LocalsUsed.empty() || HasLocalInlineAsmSymbol, 858 CantBePromoted, IsThinLTO, GetSSICallback); 859 } 860 861 // Compute summaries for all variables defined in module, and save in the 862 // index. 863 SmallVector<MDNode *, 2> Types; 864 for (const GlobalVariable &G : M.globals()) { 865 if (G.isDeclaration()) 866 continue; 867 computeVariableSummary(Index, G, CantBePromoted, M, Types); 868 } 869 870 // Compute summaries for all aliases defined in module, and save in the 871 // index. 872 for (const GlobalAlias &A : M.aliases()) 873 computeAliasSummary(Index, A, CantBePromoted); 874 875 // Iterate through ifuncs, set their resolvers all alive. 876 for (const GlobalIFunc &I : M.ifuncs()) { 877 I.applyAlongResolverPath([&Index](const GlobalValue &GV) { 878 Index.getGlobalValueSummary(GV)->setLive(true); 879 }); 880 } 881 882 for (auto *V : LocalsUsed) { 883 auto *Summary = Index.getGlobalValueSummary(*V); 884 assert(Summary && "Missing summary for global value"); 885 Summary->setNotEligibleToImport(); 886 } 887 888 // The linker doesn't know about these LLVM produced values, so we need 889 // to flag them as live in the index to ensure index-based dead value 890 // analysis treats them as live roots of the analysis. 891 setLiveRoot(Index, "llvm.used"); 892 setLiveRoot(Index, "llvm.compiler.used"); 893 setLiveRoot(Index, "llvm.global_ctors"); 894 setLiveRoot(Index, "llvm.global_dtors"); 895 setLiveRoot(Index, "llvm.global.annotations"); 896 897 for (auto &GlobalList : Index) { 898 // Ignore entries for references that are undefined in the current module. 899 if (GlobalList.second.SummaryList.empty()) 900 continue; 901 902 assert(GlobalList.second.SummaryList.size() == 1 && 903 "Expected module's index to have one summary per GUID"); 904 auto &Summary = GlobalList.second.SummaryList[0]; 905 if (!IsThinLTO) { 906 Summary->setNotEligibleToImport(); 907 continue; 908 } 909 910 bool AllRefsCanBeExternallyReferenced = 911 llvm::all_of(Summary->refs(), [&](const ValueInfo &VI) { 912 return !CantBePromoted.count(VI.getGUID()); 913 }); 914 if (!AllRefsCanBeExternallyReferenced) { 915 Summary->setNotEligibleToImport(); 916 continue; 917 } 918 919 if (auto *FuncSummary = dyn_cast<FunctionSummary>(Summary.get())) { 920 bool AllCallsCanBeExternallyReferenced = llvm::all_of( 921 FuncSummary->calls(), [&](const FunctionSummary::EdgeTy &Edge) { 922 return !CantBePromoted.count(Edge.first.getGUID()); 923 }); 924 if (!AllCallsCanBeExternallyReferenced) 925 Summary->setNotEligibleToImport(); 926 } 927 } 928 929 if (!ModuleSummaryDotFile.empty()) { 930 std::error_code EC; 931 raw_fd_ostream OSDot(ModuleSummaryDotFile, EC, sys::fs::OpenFlags::OF_None); 932 if (EC) 933 report_fatal_error(Twine("Failed to open dot file ") + 934 ModuleSummaryDotFile + ": " + EC.message() + "\n"); 935 Index.exportToDot(OSDot, {}); 936 } 937 938 return Index; 939 } 940 941 AnalysisKey ModuleSummaryIndexAnalysis::Key; 942 943 ModuleSummaryIndex 944 ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) { 945 ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(M); 946 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); 947 bool NeedSSI = needsParamAccessSummary(M); 948 return buildModuleSummaryIndex( 949 M, 950 [&FAM](const Function &F) { 951 return &FAM.getResult<BlockFrequencyAnalysis>( 952 *const_cast<Function *>(&F)); 953 }, 954 &PSI, 955 [&FAM, NeedSSI](const Function &F) -> const StackSafetyInfo * { 956 return NeedSSI ? &FAM.getResult<StackSafetyAnalysis>( 957 const_cast<Function &>(F)) 958 : nullptr; 959 }); 960 } 961 962 char ModuleSummaryIndexWrapperPass::ID = 0; 963 964 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis", 965 "Module Summary Analysis", false, true) 966 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass) 967 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass) 968 INITIALIZE_PASS_DEPENDENCY(StackSafetyInfoWrapperPass) 969 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis", 970 "Module Summary Analysis", false, true) 971 972 ModulePass *llvm::createModuleSummaryIndexWrapperPass() { 973 return new ModuleSummaryIndexWrapperPass(); 974 } 975 976 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass() 977 : ModulePass(ID) { 978 initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry()); 979 } 980 981 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) { 982 auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); 983 bool NeedSSI = needsParamAccessSummary(M); 984 Index.emplace(buildModuleSummaryIndex( 985 M, 986 [this](const Function &F) { 987 return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>( 988 *const_cast<Function *>(&F)) 989 .getBFI()); 990 }, 991 PSI, 992 [&](const Function &F) -> const StackSafetyInfo * { 993 return NeedSSI ? &getAnalysis<StackSafetyInfoWrapperPass>( 994 const_cast<Function &>(F)) 995 .getResult() 996 : nullptr; 997 })); 998 return false; 999 } 1000 1001 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) { 1002 Index.reset(); 1003 return false; 1004 } 1005 1006 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 1007 AU.setPreservesAll(); 1008 AU.addRequired<BlockFrequencyInfoWrapperPass>(); 1009 AU.addRequired<ProfileSummaryInfoWrapperPass>(); 1010 AU.addRequired<StackSafetyInfoWrapperPass>(); 1011 } 1012 1013 char ImmutableModuleSummaryIndexWrapperPass::ID = 0; 1014 1015 ImmutableModuleSummaryIndexWrapperPass::ImmutableModuleSummaryIndexWrapperPass( 1016 const ModuleSummaryIndex *Index) 1017 : ImmutablePass(ID), Index(Index) { 1018 initializeImmutableModuleSummaryIndexWrapperPassPass( 1019 *PassRegistry::getPassRegistry()); 1020 } 1021 1022 void ImmutableModuleSummaryIndexWrapperPass::getAnalysisUsage( 1023 AnalysisUsage &AU) const { 1024 AU.setPreservesAll(); 1025 } 1026 1027 ImmutablePass *llvm::createImmutableModuleSummaryIndexWrapperPass( 1028 const ModuleSummaryIndex *Index) { 1029 return new ImmutableModuleSummaryIndexWrapperPass(Index); 1030 } 1031 1032 INITIALIZE_PASS(ImmutableModuleSummaryIndexWrapperPass, "module-summary-info", 1033 "Module summary info", false, true) 1034