llvm/lib/Analysis/ModuleSummaryAnalysis.cpp

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