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