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