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