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