lib/Analysis/ModuleSummaryAnalysis.cpp

   1 //===- ModuleSummaryAnalysis.cpp - Module summary index builder -----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass builds a ModuleSummaryIndex object for the module, to be written
  11 // to bitcode or LLVM assembly.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Analysis/ModuleSummaryAnalysis.h"
  16 #include "llvm/ADT/ArrayRef.h"
  17 #include "llvm/ADT/DenseSet.h"
  18 #include "llvm/ADT/MapVector.h"
  19 #include "llvm/ADT/STLExtras.h"
  20 #include "llvm/ADT/SetVector.h"
  21 #include "llvm/ADT/SmallPtrSet.h"
  22 #include "llvm/ADT/SmallVector.h"
  23 #include "llvm/ADT/StringRef.h"
  24 #include "llvm/Analysis/BlockFrequencyInfo.h"
  25 #include "llvm/Analysis/BranchProbabilityInfo.h"
  26 #include "llvm/Analysis/IndirectCallPromotionAnalysis.h"
  27 #include "llvm/Analysis/LoopInfo.h"
  28 #include "llvm/Analysis/ProfileSummaryInfo.h"
  29 #include "llvm/Analysis/TypeMetadataUtils.h"
  30 #include "llvm/IR/Attributes.h"
  31 #include "llvm/IR/BasicBlock.h"
  32 #include "llvm/IR/CallSite.h"
  33 #include "llvm/IR/Constant.h"
  34 #include "llvm/IR/Constants.h"
  35 #include "llvm/IR/Dominators.h"
  36 #include "llvm/IR/Function.h"
  37 #include "llvm/IR/GlobalAlias.h"
  38 #include "llvm/IR/GlobalValue.h"
  39 #include "llvm/IR/GlobalVariable.h"
  40 #include "llvm/IR/Instructions.h"
  41 #include "llvm/IR/IntrinsicInst.h"
  42 #include "llvm/IR/Intrinsics.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/Object/ModuleSymbolTable.h"
  49 #include "llvm/Object/SymbolicFile.h"
  50 #include "llvm/Pass.h"
  51 #include "llvm/Support/Casting.h"
  52 #include "llvm/Support/CommandLine.h"
  53 #include <algorithm>
  54 #include <cassert>
  55 #include <cstdint>
  56 #include <vector>
  57
  58 using namespace llvm;
  59
  60 #define DEBUG_TYPE "module-summary-analysis"
  61
  62 // Option to force edges cold which will block importing when the
  63 // -import-cold-multiplier is set to 0. Useful for debugging.
  64 FunctionSummary::ForceSummaryHotnessType ForceSummaryEdgesCold =
  65     FunctionSummary::FSHT_None;
  66 cl::opt<FunctionSummary::ForceSummaryHotnessType, true> FSEC(
  67     "force-summary-edges-cold", cl::Hidden, cl::location(ForceSummaryEdgesCold),
  68     cl::desc("Force all edges in the function summary to cold"),
  69     cl::values(clEnumValN(FunctionSummary::FSHT_None, "none", "None."),
  70                clEnumValN(FunctionSummary::FSHT_AllNonCritical,
  71                           "all-non-critical", "All non-critical edges."),
  72                clEnumValN(FunctionSummary::FSHT_All, "all", "All edges.")));
  73
  74 // Walk through the operands of a given User via worklist iteration and populate
  75 // the set of GlobalValue references encountered. Invoked either on an
  76 // Instruction or a GlobalVariable (which walks its initializer).
  77 // Return true if any of the operands contains blockaddress. This is important
  78 // to know when computing summary for global var, because if global variable
  79 // references basic block address we can't import it separately from function
  80 // containing that basic block. For simplicity we currently don't import such
  81 // global vars at all. When importing function we aren't interested if any
  82 // instruction in it takes an address of any basic block, because instruction
  83 // can only take an address of basic block located in the same function.
  84 static bool findRefEdges(ModuleSummaryIndex &Index, const User *CurUser,
  85                          SetVector<ValueInfo> &RefEdges,
  86                          SmallPtrSet<const User *, 8> &Visited) {
  87   bool HasBlockAddress = false;
  88   SmallVector<const User *, 32> Worklist;
  89   Worklist.push_back(CurUser);
  90
  91   while (!Worklist.empty()) {
  92     const User *U = Worklist.pop_back_val();
  93
  94     if (!Visited.insert(U).second)
  95       continue;
  96
  97     ImmutableCallSite CS(U);
  98
  99     for (const auto &OI : U->operands()) {
 100       const User *Operand = dyn_cast<User>(OI);
 101       if (!Operand)
 102         continue;
 103       if (isa<BlockAddress>(Operand)) {
 104         HasBlockAddress = true;
 105         continue;
 106       }
 107       if (auto *GV = dyn_cast<GlobalValue>(Operand)) {
 108         // We have a reference to a global value. This should be added to
 109         // the reference set unless it is a callee. Callees are handled
 110         // specially by WriteFunction and are added to a separate list.
 111         if (!(CS && CS.isCallee(&OI)))
 112           RefEdges.insert(Index.getOrInsertValueInfo(GV));
 113         continue;
 114       }
 115       Worklist.push_back(Operand);
 116     }
 117   }
 118   return HasBlockAddress;
 119 }
 120
 121 static CalleeInfo::HotnessType getHotness(uint64_t ProfileCount,
 122                                           ProfileSummaryInfo *PSI) {
 123   if (!PSI)
 124     return CalleeInfo::HotnessType::Unknown;
 125   if (PSI->isHotCount(ProfileCount))
 126     return CalleeInfo::HotnessType::Hot;
 127   if (PSI->isColdCount(ProfileCount))
 128     return CalleeInfo::HotnessType::Cold;
 129   return CalleeInfo::HotnessType::None;
 130 }
 131
 132 static bool isNonRenamableLocal(const GlobalValue &GV) {
 133   return GV.hasSection() && GV.hasLocalLinkage();
 134 }
 135
 136 /// Determine whether this call has all constant integer arguments (excluding
 137 /// "this") and summarize it to VCalls or ConstVCalls as appropriate.
 138 static void addVCallToSet(DevirtCallSite Call, GlobalValue::GUID Guid,
 139                           SetVector<FunctionSummary::VFuncId> &VCalls,
 140                           SetVector<FunctionSummary::ConstVCall> &ConstVCalls) {
 141   std::vector<uint64_t> Args;
 142   // Start from the second argument to skip the "this" pointer.
 143   for (auto &Arg : make_range(Call.CS.arg_begin() + 1, Call.CS.arg_end())) {
 144     auto *CI = dyn_cast<ConstantInt>(Arg);
 145     if (!CI || CI->getBitWidth() > 64) {
 146       VCalls.insert({Guid, Call.Offset});
 147       return;
 148     }
 149     Args.push_back(CI->getZExtValue());
 150   }
 151   ConstVCalls.insert({{Guid, Call.Offset}, std::move(Args)});
 152 }
 153
 154 /// If this intrinsic call requires that we add information to the function
 155 /// summary, do so via the non-constant reference arguments.
 156 static void addIntrinsicToSummary(
 157     const CallInst *CI, SetVector<GlobalValue::GUID> &TypeTests,
 158     SetVector<FunctionSummary::VFuncId> &TypeTestAssumeVCalls,
 159     SetVector<FunctionSummary::VFuncId> &TypeCheckedLoadVCalls,
 160     SetVector<FunctionSummary::ConstVCall> &TypeTestAssumeConstVCalls,
 161     SetVector<FunctionSummary::ConstVCall> &TypeCheckedLoadConstVCalls,
 162     DominatorTree &DT) {
 163   switch (CI->getCalledFunction()->getIntrinsicID()) {
 164   case Intrinsic::type_test: {
 165     auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(1));
 166     auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata());
 167     if (!TypeId)
 168       break;
 169     GlobalValue::GUID Guid = GlobalValue::getGUID(TypeId->getString());
 170
 171     // Produce a summary from type.test intrinsics. We only summarize type.test
 172     // intrinsics that are used other than by an llvm.assume intrinsic.
 173     // Intrinsics that are assumed are relevant only to the devirtualization
 174     // pass, not the type test lowering pass.
 175     bool HasNonAssumeUses = llvm::any_of(CI->uses(), [](const Use &CIU) {
 176       auto *AssumeCI = dyn_cast<CallInst>(CIU.getUser());
 177       if (!AssumeCI)
 178         return true;
 179       Function *F = AssumeCI->getCalledFunction();
 180       return !F || F->getIntrinsicID() != Intrinsic::assume;
 181     });
 182     if (HasNonAssumeUses)
 183       TypeTests.insert(Guid);
 184
 185     SmallVector<DevirtCallSite, 4> DevirtCalls;
 186     SmallVector<CallInst *, 4> Assumes;
 187     findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI, DT);
 188     for (auto &Call : DevirtCalls)
 189       addVCallToSet(Call, Guid, TypeTestAssumeVCalls,
 190                     TypeTestAssumeConstVCalls);
 191
 192     break;
 193   }
 194
 195   case Intrinsic::type_checked_load: {
 196     auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(2));
 197     auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata());
 198     if (!TypeId)
 199       break;
 200     GlobalValue::GUID Guid = GlobalValue::getGUID(TypeId->getString());
 201
 202     SmallVector<DevirtCallSite, 4> DevirtCalls;
 203     SmallVector<Instruction *, 4> LoadedPtrs;
 204     SmallVector<Instruction *, 4> Preds;
 205     bool HasNonCallUses = false;
 206     findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds,
 207                                                HasNonCallUses, CI, DT);
 208     // Any non-call uses of the result of llvm.type.checked.load will
 209     // prevent us from optimizing away the llvm.type.test.
 210     if (HasNonCallUses)
 211       TypeTests.insert(Guid);
 212     for (auto &Call : DevirtCalls)
 213       addVCallToSet(Call, Guid, TypeCheckedLoadVCalls,
 214                     TypeCheckedLoadConstVCalls);
 215
 216     break;
 217   }
 218   default:
 219     break;
 220   }
 221 }
 222
 223 static void computeFunctionSummary(
 224     ModuleSummaryIndex &Index, const Module &M, const Function &F,
 225     BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, DominatorTree &DT,
 226     bool HasLocalsInUsedOrAsm, DenseSet<GlobalValue::GUID> &CantBePromoted) {
 227   // Summary not currently supported for anonymous functions, they should
 228   // have been named.
 229   assert(F.hasName());
 230
 231   unsigned NumInsts = 0;
 232   // Map from callee ValueId to profile count. Used to accumulate profile
 233   // counts for all static calls to a given callee.
 234   MapVector<ValueInfo, CalleeInfo> CallGraphEdges;
 235   SetVector<ValueInfo> RefEdges;
 236   SetVector<GlobalValue::GUID> TypeTests;
 237   SetVector<FunctionSummary::VFuncId> TypeTestAssumeVCalls,
 238       TypeCheckedLoadVCalls;
 239   SetVector<FunctionSummary::ConstVCall> TypeTestAssumeConstVCalls,
 240       TypeCheckedLoadConstVCalls;
 241   ICallPromotionAnalysis ICallAnalysis;
 242   SmallPtrSet<const User *, 8> Visited;
 243
 244   // Add personality function, prefix data and prologue data to function's ref
 245   // list.
 246   findRefEdges(Index, &F, RefEdges, Visited);
 247
 248   bool HasInlineAsmMaybeReferencingInternal = false;
 249   for (const BasicBlock &BB : F)
 250     for (const Instruction &I : BB) {
 251       if (isa<DbgInfoIntrinsic>(I))
 252         continue;
 253       ++NumInsts;
 254       findRefEdges(Index, &I, RefEdges, Visited);
 255       auto CS = ImmutableCallSite(&I);
 256       if (!CS)
 257         continue;
 258
 259       const auto *CI = dyn_cast<CallInst>(&I);
 260       // Since we don't know exactly which local values are referenced in inline
 261       // assembly, conservatively mark the function as possibly referencing
 262       // a local value from inline assembly to ensure we don't export a
 263       // reference (which would require renaming and promotion of the
 264       // referenced value).
 265       if (HasLocalsInUsedOrAsm && CI && CI->isInlineAsm())
 266         HasInlineAsmMaybeReferencingInternal = true;
 267
 268       auto *CalledValue = CS.getCalledValue();
 269       auto *CalledFunction = CS.getCalledFunction();
 270       if (CalledValue && !CalledFunction) {
 271         CalledValue = CalledValue->stripPointerCastsNoFollowAliases();
 272         // Stripping pointer casts can reveal a called function.
 273         CalledFunction = dyn_cast<Function>(CalledValue);
 274       }
 275       // Check if this is an alias to a function. If so, get the
 276       // called aliasee for the checks below.
 277       if (auto *GA = dyn_cast<GlobalAlias>(CalledValue)) {
 278         assert(!CalledFunction && "Expected null called function in callsite for alias");
 279         CalledFunction = dyn_cast<Function>(GA->getBaseObject());
 280       }
 281       // Check if this is a direct call to a known function or a known
 282       // intrinsic, or an indirect call with profile data.
 283       if (CalledFunction) {
 284         if (CI && CalledFunction->isIntrinsic()) {
 285           addIntrinsicToSummary(
 286               CI, TypeTests, TypeTestAssumeVCalls, TypeCheckedLoadVCalls,
 287               TypeTestAssumeConstVCalls, TypeCheckedLoadConstVCalls, DT);
 288           continue;
 289         }
 290         // We should have named any anonymous globals
 291         assert(CalledFunction->hasName());
 292         auto ScaledCount = PSI->getProfileCount(&I, BFI);
 293         auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI)
 294                                    : CalleeInfo::HotnessType::Unknown;
 295         if (ForceSummaryEdgesCold != FunctionSummary::FSHT_None)
 296           Hotness = CalleeInfo::HotnessType::Cold;
 297
 298         // Use the original CalledValue, in case it was an alias. We want
 299         // to record the call edge to the alias in that case. Eventually
 300         // an alias summary will be created to associate the alias and
 301         // aliasee.
 302         auto &ValueInfo = CallGraphEdges[Index.getOrInsertValueInfo(
 303             cast<GlobalValue>(CalledValue))];
 304         ValueInfo.updateHotness(Hotness);
 305         // Add the relative block frequency to CalleeInfo if there is no profile
 306         // information.
 307         if (BFI != nullptr && Hotness == CalleeInfo::HotnessType::Unknown) {
 308           uint64_t BBFreq = BFI->getBlockFreq(&BB).getFrequency();
 309           uint64_t EntryFreq = BFI->getEntryFreq();
 310           ValueInfo.updateRelBlockFreq(BBFreq, EntryFreq);
 311         }
 312       } else {
 313         // Skip inline assembly calls.
 314         if (CI && CI->isInlineAsm())
 315           continue;
 316         // Skip direct calls.
 317         if (!CalledValue || isa<Constant>(CalledValue))
 318           continue;
 319
 320         // Check if the instruction has a callees metadata. If so, add callees
 321         // to CallGraphEdges to reflect the references from the metadata, and
 322         // to enable importing for subsequent indirect call promotion and
 323         // inlining.
 324         if (auto *MD = I.getMetadata(LLVMContext::MD_callees)) {
 325           for (auto &Op : MD->operands()) {
 326             Function *Callee = mdconst::extract_or_null<Function>(Op);
 327             if (Callee)
 328               CallGraphEdges[Index.getOrInsertValueInfo(Callee)];
 329           }
 330         }
 331
 332         uint32_t NumVals, NumCandidates;
 333         uint64_t TotalCount;
 334         auto CandidateProfileData =
 335             ICallAnalysis.getPromotionCandidatesForInstruction(
 336                 &I, NumVals, TotalCount, NumCandidates);
 337         for (auto &Candidate : CandidateProfileData)
 338           CallGraphEdges[Index.getOrInsertValueInfo(Candidate.Value)]
 339               .updateHotness(getHotness(Candidate.Count, PSI));
 340       }
 341     }
 342
 343   // Explicit add hot edges to enforce importing for designated GUIDs for
 344   // sample PGO, to enable the same inlines as the profiled optimized binary.
 345   for (auto &I : F.getImportGUIDs())
 346     CallGraphEdges[Index.getOrInsertValueInfo(I)].updateHotness(
 347         ForceSummaryEdgesCold == FunctionSummary::FSHT_All
 348             ? CalleeInfo::HotnessType::Cold
 349             : CalleeInfo::HotnessType::Critical);
 350
 351   bool NonRenamableLocal = isNonRenamableLocal(F);
 352   bool NotEligibleForImport =
 353       NonRenamableLocal || HasInlineAsmMaybeReferencingInternal ||
 354       // Inliner doesn't handle variadic functions.
 355       // FIXME: refactor this to use the same code that inliner is using.
 356       F.isVarArg() ||
 357       // Don't try to import functions with noinline attribute.
 358       F.getAttributes().hasFnAttribute(Attribute::NoInline);
 359   GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport,
 360                                     /* Live = */ false, F.isDSOLocal());
 361   FunctionSummary::FFlags FunFlags{
 362       F.hasFnAttribute(Attribute::ReadNone),
 363       F.hasFnAttribute(Attribute::ReadOnly),
 364       F.hasFnAttribute(Attribute::NoRecurse),
 365       F.returnDoesNotAlias(),
 366   };
 367   auto FuncSummary = llvm::make_unique<FunctionSummary>(
 368       Flags, NumInsts, FunFlags, RefEdges.takeVector(),
 369       CallGraphEdges.takeVector(), TypeTests.takeVector(),
 370       TypeTestAssumeVCalls.takeVector(), TypeCheckedLoadVCalls.takeVector(),
 371       TypeTestAssumeConstVCalls.takeVector(),
 372       TypeCheckedLoadConstVCalls.takeVector());
 373   if (NonRenamableLocal)
 374     CantBePromoted.insert(F.getGUID());
 375   Index.addGlobalValueSummary(F, std::move(FuncSummary));
 376 }
 377
 378 static void
 379 computeVariableSummary(ModuleSummaryIndex &Index, const GlobalVariable &V,
 380                        DenseSet<GlobalValue::GUID> &CantBePromoted) {
 381   SetVector<ValueInfo> RefEdges;
 382   SmallPtrSet<const User *, 8> Visited;
 383   bool HasBlockAddress = findRefEdges(Index, &V, RefEdges, Visited);
 384   bool NonRenamableLocal = isNonRenamableLocal(V);
 385   GlobalValueSummary::GVFlags Flags(V.getLinkage(), NonRenamableLocal,
 386                                     /* Live = */ false, V.isDSOLocal());
 387   auto GVarSummary =
 388       llvm::make_unique<GlobalVarSummary>(Flags, RefEdges.takeVector());
 389   if (NonRenamableLocal)
 390     CantBePromoted.insert(V.getGUID());
 391   if (HasBlockAddress)
 392     GVarSummary->setNotEligibleToImport();
 393   Index.addGlobalValueSummary(V, std::move(GVarSummary));
 394 }
 395
 396 static void
 397 computeAliasSummary(ModuleSummaryIndex &Index, const GlobalAlias &A,
 398                     DenseSet<GlobalValue::GUID> &CantBePromoted) {
 399   bool NonRenamableLocal = isNonRenamableLocal(A);
 400   GlobalValueSummary::GVFlags Flags(A.getLinkage(), NonRenamableLocal,
 401                                     /* Live = */ false, A.isDSOLocal());
 402   auto AS = llvm::make_unique<AliasSummary>(Flags);
 403   auto *Aliasee = A.getBaseObject();
 404   auto *AliaseeSummary = Index.getGlobalValueSummary(*Aliasee);
 405   assert(AliaseeSummary && "Alias expects aliasee summary to be parsed");
 406   AS->setAliasee(AliaseeSummary);
 407   if (NonRenamableLocal)
 408     CantBePromoted.insert(A.getGUID());
 409   Index.addGlobalValueSummary(A, std::move(AS));
 410 }
 411
 412 // Set LiveRoot flag on entries matching the given value name.
 413 static void setLiveRoot(ModuleSummaryIndex &Index, StringRef Name) {
 414   if (ValueInfo VI = Index.getValueInfo(GlobalValue::getGUID(Name)))
 415     for (auto &Summary : VI.getSummaryList())
 416       Summary->setLive(true);
 417 }
 418
 419 ModuleSummaryIndex llvm::buildModuleSummaryIndex(
 420     const Module &M,
 421     std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback,
 422     ProfileSummaryInfo *PSI) {
 423   assert(PSI);
 424   ModuleSummaryIndex Index(/*HaveGVs=*/true);
 425
 426   // Identify the local values in the llvm.used and llvm.compiler.used sets,
 427   // which should not be exported as they would then require renaming and
 428   // promotion, but we may have opaque uses e.g. in inline asm. We collect them
 429   // here because we use this information to mark functions containing inline
 430   // assembly calls as not importable.
 431   SmallPtrSet<GlobalValue *, 8> LocalsUsed;
 432   SmallPtrSet<GlobalValue *, 8> Used;
 433   // First collect those in the llvm.used set.
 434   collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false);
 435   // Next collect those in the llvm.compiler.used set.
 436   collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ true);
 437   DenseSet<GlobalValue::GUID> CantBePromoted;
 438   for (auto *V : Used) {
 439     if (V->hasLocalLinkage()) {
 440       LocalsUsed.insert(V);
 441       CantBePromoted.insert(V->getGUID());
 442     }
 443   }
 444
 445   bool HasLocalInlineAsmSymbol = false;
 446   if (!M.getModuleInlineAsm().empty()) {
 447     // Collect the local values defined by module level asm, and set up
 448     // summaries for these symbols so that they can be marked as NoRename,
 449     // to prevent export of any use of them in regular IR that would require
 450     // renaming within the module level asm. Note we don't need to create a
 451     // summary for weak or global defs, as they don't need to be flagged as
 452     // NoRename, and defs in module level asm can't be imported anyway.
 453     // Also, any values used but not defined within module level asm should
 454     // be listed on the llvm.used or llvm.compiler.used global and marked as
 455     // referenced from there.
 456     ModuleSymbolTable::CollectAsmSymbols(
 457         M, [&](StringRef Name, object::BasicSymbolRef::Flags Flags) {
 458           // Symbols not marked as Weak or Global are local definitions.
 459           if (Flags & (object::BasicSymbolRef::SF_Weak |
 460                        object::BasicSymbolRef::SF_Global))
 461             return;
 462           HasLocalInlineAsmSymbol = true;
 463           GlobalValue *GV = M.getNamedValue(Name);
 464           if (!GV)
 465             return;
 466           assert(GV->isDeclaration() && "Def in module asm already has definition");
 467           GlobalValueSummary::GVFlags GVFlags(GlobalValue::InternalLinkage,
 468                                               /* NotEligibleToImport = */ true,
 469                                               /* Live = */ true,
 470                                               /* Local */ GV->isDSOLocal());
 471           CantBePromoted.insert(GV->getGUID());
 472           // Create the appropriate summary type.
 473           if (Function *F = dyn_cast<Function>(GV)) {
 474             std::unique_ptr<FunctionSummary> Summary =
 475                 llvm::make_unique<FunctionSummary>(
 476                     GVFlags, 0,
 477                     FunctionSummary::FFlags{
 478                         F->hasFnAttribute(Attribute::ReadNone),
 479                         F->hasFnAttribute(Attribute::ReadOnly),
 480                         F->hasFnAttribute(Attribute::NoRecurse),
 481                         F->returnDoesNotAlias()},
 482                     ArrayRef<ValueInfo>{}, ArrayRef<FunctionSummary::EdgeTy>{},
 483                     ArrayRef<GlobalValue::GUID>{},
 484                     ArrayRef<FunctionSummary::VFuncId>{},
 485                     ArrayRef<FunctionSummary::VFuncId>{},
 486                     ArrayRef<FunctionSummary::ConstVCall>{},
 487                     ArrayRef<FunctionSummary::ConstVCall>{});
 488             Index.addGlobalValueSummary(*GV, std::move(Summary));
 489           } else {
 490             std::unique_ptr<GlobalVarSummary> Summary =
 491                 llvm::make_unique<GlobalVarSummary>(GVFlags,
 492                                                     ArrayRef<ValueInfo>{});
 493             Index.addGlobalValueSummary(*GV, std::move(Summary));
 494           }
 495         });
 496   }
 497
 498   // Compute summaries for all functions defined in module, and save in the
 499   // index.
 500   for (auto &F : M) {
 501     if (F.isDeclaration())
 502       continue;
 503
 504     DominatorTree DT(const_cast<Function &>(F));
 505     BlockFrequencyInfo *BFI = nullptr;
 506     std::unique_ptr<BlockFrequencyInfo> BFIPtr;
 507     if (GetBFICallback)
 508       BFI = GetBFICallback(F);
 509     else if (F.hasProfileData()) {
 510       LoopInfo LI{DT};
 511       BranchProbabilityInfo BPI{F, LI};
 512       BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI);
 513       BFI = BFIPtr.get();
 514     }
 515
 516     computeFunctionSummary(Index, M, F, BFI, PSI, DT,
 517                            !LocalsUsed.empty() || HasLocalInlineAsmSymbol,
 518                            CantBePromoted);
 519   }
 520
 521   // Compute summaries for all variables defined in module, and save in the
 522   // index.
 523   for (const GlobalVariable &G : M.globals()) {
 524     if (G.isDeclaration())
 525       continue;
 526     computeVariableSummary(Index, G, CantBePromoted);
 527   }
 528
 529   // Compute summaries for all aliases defined in module, and save in the
 530   // index.
 531   for (const GlobalAlias &A : M.aliases())
 532     computeAliasSummary(Index, A, CantBePromoted);
 533
 534   for (auto *V : LocalsUsed) {
 535     auto *Summary = Index.getGlobalValueSummary(*V);
 536     assert(Summary && "Missing summary for global value");
 537     Summary->setNotEligibleToImport();
 538   }
 539
 540   // The linker doesn't know about these LLVM produced values, so we need
 541   // to flag them as live in the index to ensure index-based dead value
 542   // analysis treats them as live roots of the analysis.
 543   setLiveRoot(Index, "llvm.used");
 544   setLiveRoot(Index, "llvm.compiler.used");
 545   setLiveRoot(Index, "llvm.global_ctors");
 546   setLiveRoot(Index, "llvm.global_dtors");
 547   setLiveRoot(Index, "llvm.global.annotations");
 548
 549   bool IsThinLTO = true;
 550   if (auto *MD =
 551           mdconst::extract_or_null<ConstantInt>(M.getModuleFlag("ThinLTO")))
 552     IsThinLTO = MD->getZExtValue();
 553
 554   for (auto &GlobalList : Index) {
 555     // Ignore entries for references that are undefined in the current module.
 556     if (GlobalList.second.SummaryList.empty())
 557       continue;
 558
 559     assert(GlobalList.second.SummaryList.size() == 1 &&
 560            "Expected module's index to have one summary per GUID");
 561     auto &Summary = GlobalList.second.SummaryList[0];
 562     if (!IsThinLTO) {
 563       Summary->setNotEligibleToImport();
 564       continue;
 565     }
 566
 567     bool AllRefsCanBeExternallyReferenced =
 568         llvm::all_of(Summary->refs(), [&](const ValueInfo &VI) {
 569           return !CantBePromoted.count(VI.getGUID());
 570         });
 571     if (!AllRefsCanBeExternallyReferenced) {
 572       Summary->setNotEligibleToImport();
 573       continue;
 574     }
 575
 576     if (auto *FuncSummary = dyn_cast<FunctionSummary>(Summary.get())) {
 577       bool AllCallsCanBeExternallyReferenced = llvm::all_of(
 578           FuncSummary->calls(), [&](const FunctionSummary::EdgeTy &Edge) {
 579             return !CantBePromoted.count(Edge.first.getGUID());
 580           });
 581       if (!AllCallsCanBeExternallyReferenced)
 582         Summary->setNotEligibleToImport();
 583     }
 584   }
 585
 586   return Index;
 587 }
 588
 589 AnalysisKey ModuleSummaryIndexAnalysis::Key;
 590
 591 ModuleSummaryIndex
 592 ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
 593   ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(M);
 594   auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
 595   return buildModuleSummaryIndex(
 596       M,
 597       [&FAM](const Function &F) {
 598         return &FAM.getResult<BlockFrequencyAnalysis>(
 599             *const_cast<Function *>(&F));
 600       },
 601       &PSI);
 602 }
 603
 604 char ModuleSummaryIndexWrapperPass::ID = 0;
 605
 606 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
 607                       "Module Summary Analysis", false, true)
 608 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
 609 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
 610 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
 611                     "Module Summary Analysis", false, true)
 612
 613 ModulePass *llvm::createModuleSummaryIndexWrapperPass() {
 614   return new ModuleSummaryIndexWrapperPass();
 615 }
 616
 617 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass()
 618     : ModulePass(ID) {
 619   initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry());
 620 }
 621
 622 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) {
 623   auto &PSI = *getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
 624   Index.emplace(buildModuleSummaryIndex(
 625       M,
 626       [this](const Function &F) {
 627         return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>(
 628                          *const_cast<Function *>(&F))
 629                      .getBFI());
 630       },
 631       &PSI));
 632   return false;
 633 }
 634
 635 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) {
 636   Index.reset();
 637   return false;
 638 }
 639
 640 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
 641   AU.setPreservesAll();
 642   AU.addRequired<BlockFrequencyInfoWrapperPass>();
 643   AU.addRequired<ProfileSummaryInfoWrapperPass>();
 644 }