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/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/CallSite.h"
  32 #include "llvm/IR/Constant.h"
  33 #include "llvm/IR/Constants.h"
  34 #include "llvm/IR/Dominators.h"
  35 #include "llvm/IR/Function.h"
  36 #include "llvm/IR/GlobalAlias.h"
  37 #include "llvm/IR/GlobalValue.h"
  38 #include "llvm/IR/GlobalVariable.h"
  39 #include "llvm/IR/Instructions.h"
  40 #include "llvm/IR/IntrinsicInst.h"
  41 #include "llvm/IR/Intrinsics.h"
  42 #include "llvm/IR/Metadata.h"
  43 #include "llvm/IR/Module.h"
  44 #include "llvm/IR/ModuleSummaryIndex.h"
  45 #include "llvm/IR/Use.h"
  46 #include "llvm/IR/User.h"
  47 #include "llvm/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     ImmutableCallSite CS(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 (!(CS && CS.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.CS.arg_begin() + 1, Call.CS.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       auto CS = ImmutableCallSite(&I);
 307       if (!CS)
 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 = CS.getCalledValue();
 320       auto *CalledFunction = CS.getCalledFunction();
 321       if (CalledValue && !CalledFunction) {
 322         CalledValue = CalledValue->stripPointerCastsNoFollowAliases();
 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   auto FuncSummary = llvm::make_unique<FunctionSummary>(
 471       Flags, NumInsts, FunFlags, /*EntryCount=*/0, std::move(Refs),
 472       CallGraphEdges.takeVector(), TypeTests.takeVector(),
 473       TypeTestAssumeVCalls.takeVector(), TypeCheckedLoadVCalls.takeVector(),
 474       TypeTestAssumeConstVCalls.takeVector(),
 475       TypeCheckedLoadConstVCalls.takeVector());
 476   if (NonRenamableLocal)
 477     CantBePromoted.insert(F.getGUID());
 478   Index.addGlobalValueSummary(F, std::move(FuncSummary));
 479 }
 480
 481 /// Find function pointers referenced within the given vtable initializer
 482 /// (or subset of an initializer) \p I. The starting offset of \p I within
 483 /// the vtable initializer is \p StartingOffset. Any discovered function
 484 /// pointers are added to \p VTableFuncs along with their cumulative offset
 485 /// within the initializer.
 486 static void findFuncPointers(const Constant *I, uint64_t StartingOffset,
 487                              const Module &M, ModuleSummaryIndex &Index,
 488                              VTableFuncList &VTableFuncs) {
 489   // First check if this is a function pointer.
 490   if (I->getType()->isPointerTy()) {
 491     auto Fn = dyn_cast<Function>(I->stripPointerCasts());
 492     // We can disregard __cxa_pure_virtual as a possible call target, as
 493     // calls to pure virtuals are UB.
 494     if (Fn && Fn->getName() != "__cxa_pure_virtual")
 495       VTableFuncs.push_back({Index.getOrInsertValueInfo(Fn), StartingOffset});
 496     return;
 497   }
 498
 499   // Walk through the elements in the constant struct or array and recursively
 500   // look for virtual function pointers.
 501   const DataLayout &DL = M.getDataLayout();
 502   if (auto *C = dyn_cast<ConstantStruct>(I)) {
 503     StructType *STy = dyn_cast<StructType>(C->getType());
 504     assert(STy);
 505     const StructLayout *SL = DL.getStructLayout(C->getType());
 506
 507     for (StructType::element_iterator EB = STy->element_begin(), EI = EB,
 508                                       EE = STy->element_end();
 509          EI != EE; ++EI) {
 510       auto Offset = SL->getElementOffset(EI - EB);
 511       unsigned Op = SL->getElementContainingOffset(Offset);
 512       findFuncPointers(cast<Constant>(I->getOperand(Op)),
 513                        StartingOffset + Offset, M, Index, VTableFuncs);
 514     }
 515   } else if (auto *C = dyn_cast<ConstantArray>(I)) {
 516     ArrayType *ATy = C->getType();
 517     Type *EltTy = ATy->getElementType();
 518     uint64_t EltSize = DL.getTypeAllocSize(EltTy);
 519     for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) {
 520       findFuncPointers(cast<Constant>(I->getOperand(i)),
 521                        StartingOffset + i * EltSize, M, Index, VTableFuncs);
 522     }
 523   }
 524 }
 525
 526 // Identify the function pointers referenced by vtable definition \p V.
 527 static void computeVTableFuncs(ModuleSummaryIndex &Index,
 528                                const GlobalVariable &V, const Module &M,
 529                                VTableFuncList &VTableFuncs) {
 530   if (!V.isConstant())
 531     return;
 532
 533   findFuncPointers(V.getInitializer(), /*StartingOffset=*/0, M, Index,
 534                    VTableFuncs);
 535
 536 #ifndef NDEBUG
 537   // Validate that the VTableFuncs list is ordered by offset.
 538   uint64_t PrevOffset = 0;
 539   for (auto &P : VTableFuncs) {
 540     // The findVFuncPointers traversal should have encountered the
 541     // functions in offset order. We need to use ">=" since PrevOffset
 542     // starts at 0.
 543     assert(P.VTableOffset >= PrevOffset);
 544     PrevOffset = P.VTableOffset;
 545   }
 546 #endif
 547 }
 548
 549 /// Record vtable definition \p V for each type metadata it references.
 550 static void
 551 recordTypeIdCompatibleVtableReferences(ModuleSummaryIndex &Index,
 552                                        const GlobalVariable &V,
 553                                        SmallVectorImpl<MDNode *> &Types) {
 554   for (MDNode *Type : Types) {
 555     auto TypeID = Type->getOperand(1).get();
 556
 557     uint64_t Offset =
 558         cast<ConstantInt>(
 559             cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
 560             ->getZExtValue();
 561
 562     if (auto *TypeId = dyn_cast<MDString>(TypeID))
 563       Index.getOrInsertTypeIdCompatibleVtableSummary(TypeId->getString())
 564           .push_back({Offset, Index.getOrInsertValueInfo(&V)});
 565   }
 566 }
 567
 568 static void computeVariableSummary(ModuleSummaryIndex &Index,
 569                                    const GlobalVariable &V,
 570                                    DenseSet<GlobalValue::GUID> &CantBePromoted,
 571                                    const Module &M,
 572                                    SmallVectorImpl<MDNode *> &Types) {
 573   SetVector<ValueInfo> RefEdges;
 574   SmallPtrSet<const User *, 8> Visited;
 575   bool HasBlockAddress = findRefEdges(Index, &V, RefEdges, Visited);
 576   bool NonRenamableLocal = isNonRenamableLocal(V);
 577   GlobalValueSummary::GVFlags Flags(V.getLinkage(), NonRenamableLocal,
 578                                     /* Live = */ false, V.isDSOLocal(),
 579                                     V.hasLinkOnceODRLinkage() && V.hasGlobalUnnamedAddr());
 580
 581   VTableFuncList VTableFuncs;
 582   // If splitting is not enabled, then we compute the summary information
 583   // necessary for index-based whole program devirtualization.
 584   if (!Index.enableSplitLTOUnit()) {
 585     Types.clear();
 586     V.getMetadata(LLVMContext::MD_type, Types);
 587     if (!Types.empty()) {
 588       // Identify the function pointers referenced by this vtable definition.
 589       computeVTableFuncs(Index, V, M, VTableFuncs);
 590
 591       // Record this vtable definition for each type metadata it references.
 592       recordTypeIdCompatibleVtableReferences(Index, V, Types);
 593     }
 594   }
 595
 596   // Don't mark variables we won't be able to internalize as read/write-only.
 597   bool CanBeInternalized =
 598       !V.hasComdat() && !V.hasAppendingLinkage() && !V.isInterposable() &&
 599       !V.hasAvailableExternallyLinkage() && !V.hasDLLExportStorageClass();
 600   GlobalVarSummary::GVarFlags VarFlags(CanBeInternalized, CanBeInternalized);
 601   auto GVarSummary = llvm::make_unique<GlobalVarSummary>(Flags, VarFlags,
 602                                                          RefEdges.takeVector());
 603   if (NonRenamableLocal)
 604     CantBePromoted.insert(V.getGUID());
 605   if (HasBlockAddress)
 606     GVarSummary->setNotEligibleToImport();
 607   if (!VTableFuncs.empty())
 608     GVarSummary->setVTableFuncs(VTableFuncs);
 609   Index.addGlobalValueSummary(V, std::move(GVarSummary));
 610 }
 611
 612 static void
 613 computeAliasSummary(ModuleSummaryIndex &Index, const GlobalAlias &A,
 614                     DenseSet<GlobalValue::GUID> &CantBePromoted) {
 615   bool NonRenamableLocal = isNonRenamableLocal(A);
 616   GlobalValueSummary::GVFlags Flags(A.getLinkage(), NonRenamableLocal,
 617                                     /* Live = */ false, A.isDSOLocal(),
 618                                     A.hasLinkOnceODRLinkage() && A.hasGlobalUnnamedAddr());
 619   auto AS = llvm::make_unique<AliasSummary>(Flags);
 620   auto *Aliasee = A.getBaseObject();
 621   auto AliaseeVI = Index.getValueInfo(Aliasee->getGUID());
 622   assert(AliaseeVI && "Alias expects aliasee summary to be available");
 623   assert(AliaseeVI.getSummaryList().size() == 1 &&
 624          "Expected a single entry per aliasee in per-module index");
 625   AS->setAliasee(AliaseeVI, AliaseeVI.getSummaryList()[0].get());
 626   if (NonRenamableLocal)
 627     CantBePromoted.insert(A.getGUID());
 628   Index.addGlobalValueSummary(A, std::move(AS));
 629 }
 630
 631 // Set LiveRoot flag on entries matching the given value name.
 632 static void setLiveRoot(ModuleSummaryIndex &Index, StringRef Name) {
 633   if (ValueInfo VI = Index.getValueInfo(GlobalValue::getGUID(Name)))
 634     for (auto &Summary : VI.getSummaryList())
 635       Summary->setLive(true);
 636 }
 637
 638 ModuleSummaryIndex llvm::buildModuleSummaryIndex(
 639     const Module &M,
 640     std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback,
 641     ProfileSummaryInfo *PSI) {
 642   assert(PSI);
 643   bool EnableSplitLTOUnit = false;
 644   if (auto *MD = mdconst::extract_or_null<ConstantInt>(
 645           M.getModuleFlag("EnableSplitLTOUnit")))
 646     EnableSplitLTOUnit = MD->getZExtValue();
 647   ModuleSummaryIndex Index(/*HaveGVs=*/true, EnableSplitLTOUnit);
 648
 649   // Identify the local values in the llvm.used and llvm.compiler.used sets,
 650   // which should not be exported as they would then require renaming and
 651   // promotion, but we may have opaque uses e.g. in inline asm. We collect them
 652   // here because we use this information to mark functions containing inline
 653   // assembly calls as not importable.
 654   SmallPtrSet<GlobalValue *, 8> LocalsUsed;
 655   SmallPtrSet<GlobalValue *, 8> Used;
 656   // First collect those in the llvm.used set.
 657   collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ false);
 658   // Next collect those in the llvm.compiler.used set.
 659   collectUsedGlobalVariables(M, Used, /*CompilerUsed*/ true);
 660   DenseSet<GlobalValue::GUID> CantBePromoted;
 661   for (auto *V : Used) {
 662     if (V->hasLocalLinkage()) {
 663       LocalsUsed.insert(V);
 664       CantBePromoted.insert(V->getGUID());
 665     }
 666   }
 667
 668   bool HasLocalInlineAsmSymbol = false;
 669   if (!M.getModuleInlineAsm().empty()) {
 670     // Collect the local values defined by module level asm, and set up
 671     // summaries for these symbols so that they can be marked as NoRename,
 672     // to prevent export of any use of them in regular IR that would require
 673     // renaming within the module level asm. Note we don't need to create a
 674     // summary for weak or global defs, as they don't need to be flagged as
 675     // NoRename, and defs in module level asm can't be imported anyway.
 676     // Also, any values used but not defined within module level asm should
 677     // be listed on the llvm.used or llvm.compiler.used global and marked as
 678     // referenced from there.
 679     ModuleSymbolTable::CollectAsmSymbols(
 680         M, [&](StringRef Name, object::BasicSymbolRef::Flags Flags) {
 681           // Symbols not marked as Weak or Global are local definitions.
 682           if (Flags & (object::BasicSymbolRef::SF_Weak |
 683                        object::BasicSymbolRef::SF_Global))
 684             return;
 685           HasLocalInlineAsmSymbol = true;
 686           GlobalValue *GV = M.getNamedValue(Name);
 687           if (!GV)
 688             return;
 689           assert(GV->isDeclaration() && "Def in module asm already has definition");
 690           GlobalValueSummary::GVFlags GVFlags(GlobalValue::InternalLinkage,
 691                                               /* NotEligibleToImport = */ true,
 692                                               /* Live = */ true,
 693                                               /* Local */ GV->isDSOLocal(),
 694                                               GV->hasLinkOnceODRLinkage() && GV->hasGlobalUnnamedAddr());
 695           CantBePromoted.insert(GV->getGUID());
 696           // Create the appropriate summary type.
 697           if (Function *F = dyn_cast<Function>(GV)) {
 698             std::unique_ptr<FunctionSummary> Summary =
 699                 llvm::make_unique<FunctionSummary>(
 700                     GVFlags, /*InstCount=*/0,
 701                     FunctionSummary::FFlags{
 702                         F->hasFnAttribute(Attribute::ReadNone),
 703                         F->hasFnAttribute(Attribute::ReadOnly),
 704                         F->hasFnAttribute(Attribute::NoRecurse),
 705                         F->returnDoesNotAlias(),
 706                         /* NoInline = */ false},
 707                     /*EntryCount=*/0, ArrayRef<ValueInfo>{},
 708                     ArrayRef<FunctionSummary::EdgeTy>{},
 709                     ArrayRef<GlobalValue::GUID>{},
 710                     ArrayRef<FunctionSummary::VFuncId>{},
 711                     ArrayRef<FunctionSummary::VFuncId>{},
 712                     ArrayRef<FunctionSummary::ConstVCall>{},
 713                     ArrayRef<FunctionSummary::ConstVCall>{});
 714             Index.addGlobalValueSummary(*GV, std::move(Summary));
 715           } else {
 716             std::unique_ptr<GlobalVarSummary> Summary =
 717                 llvm::make_unique<GlobalVarSummary>(
 718                     GVFlags, GlobalVarSummary::GVarFlags(false, false),
 719                     ArrayRef<ValueInfo>{});
 720             Index.addGlobalValueSummary(*GV, std::move(Summary));
 721           }
 722         });
 723   }
 724
 725   bool IsThinLTO = true;
 726   if (auto *MD =
 727           mdconst::extract_or_null<ConstantInt>(M.getModuleFlag("ThinLTO")))
 728     IsThinLTO = MD->getZExtValue();
 729
 730   // Compute summaries for all functions defined in module, and save in the
 731   // index.
 732   for (auto &F : M) {
 733     if (F.isDeclaration())
 734       continue;
 735
 736     DominatorTree DT(const_cast<Function &>(F));
 737     BlockFrequencyInfo *BFI = nullptr;
 738     std::unique_ptr<BlockFrequencyInfo> BFIPtr;
 739     if (GetBFICallback)
 740       BFI = GetBFICallback(F);
 741     else if (F.hasProfileData()) {
 742       LoopInfo LI{DT};
 743       BranchProbabilityInfo BPI{F, LI};
 744       BFIPtr = llvm::make_unique<BlockFrequencyInfo>(F, BPI, LI);
 745       BFI = BFIPtr.get();
 746     }
 747
 748     computeFunctionSummary(Index, M, F, BFI, PSI, DT,
 749                            !LocalsUsed.empty() || HasLocalInlineAsmSymbol,
 750                            CantBePromoted, IsThinLTO);
 751   }
 752
 753   // Compute summaries for all variables defined in module, and save in the
 754   // index.
 755   SmallVector<MDNode *, 2> Types;
 756   for (const GlobalVariable &G : M.globals()) {
 757     if (G.isDeclaration())
 758       continue;
 759     computeVariableSummary(Index, G, CantBePromoted, M, Types);
 760   }
 761
 762   // Compute summaries for all aliases defined in module, and save in the
 763   // index.
 764   for (const GlobalAlias &A : M.aliases())
 765     computeAliasSummary(Index, A, CantBePromoted);
 766
 767   for (auto *V : LocalsUsed) {
 768     auto *Summary = Index.getGlobalValueSummary(*V);
 769     assert(Summary && "Missing summary for global value");
 770     Summary->setNotEligibleToImport();
 771   }
 772
 773   // The linker doesn't know about these LLVM produced values, so we need
 774   // to flag them as live in the index to ensure index-based dead value
 775   // analysis treats them as live roots of the analysis.
 776   setLiveRoot(Index, "llvm.used");
 777   setLiveRoot(Index, "llvm.compiler.used");
 778   setLiveRoot(Index, "llvm.global_ctors");
 779   setLiveRoot(Index, "llvm.global_dtors");
 780   setLiveRoot(Index, "llvm.global.annotations");
 781
 782   for (auto &GlobalList : Index) {
 783     // Ignore entries for references that are undefined in the current module.
 784     if (GlobalList.second.SummaryList.empty())
 785       continue;
 786
 787     assert(GlobalList.second.SummaryList.size() == 1 &&
 788            "Expected module's index to have one summary per GUID");
 789     auto &Summary = GlobalList.second.SummaryList[0];
 790     if (!IsThinLTO) {
 791       Summary->setNotEligibleToImport();
 792       continue;
 793     }
 794
 795     bool AllRefsCanBeExternallyReferenced =
 796         llvm::all_of(Summary->refs(), [&](const ValueInfo &VI) {
 797           return !CantBePromoted.count(VI.getGUID());
 798         });
 799     if (!AllRefsCanBeExternallyReferenced) {
 800       Summary->setNotEligibleToImport();
 801       continue;
 802     }
 803
 804     if (auto *FuncSummary = dyn_cast<FunctionSummary>(Summary.get())) {
 805       bool AllCallsCanBeExternallyReferenced = llvm::all_of(
 806           FuncSummary->calls(), [&](const FunctionSummary::EdgeTy &Edge) {
 807             return !CantBePromoted.count(Edge.first.getGUID());
 808           });
 809       if (!AllCallsCanBeExternallyReferenced)
 810         Summary->setNotEligibleToImport();
 811     }
 812   }
 813
 814   if (!ModuleSummaryDotFile.empty()) {
 815     std::error_code EC;
 816     raw_fd_ostream OSDot(ModuleSummaryDotFile, EC, sys::fs::OpenFlags::F_None);
 817     if (EC)
 818       report_fatal_error(Twine("Failed to open dot file ") +
 819                          ModuleSummaryDotFile + ": " + EC.message() + "\n");
 820     Index.exportToDot(OSDot);
 821   }
 822
 823   return Index;
 824 }
 825
 826 AnalysisKey ModuleSummaryIndexAnalysis::Key;
 827
 828 ModuleSummaryIndex
 829 ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
 830   ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(M);
 831   auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
 832   return buildModuleSummaryIndex(
 833       M,
 834       [&FAM](const Function &F) {
 835         return &FAM.getResult<BlockFrequencyAnalysis>(
 836             *const_cast<Function *>(&F));
 837       },
 838       &PSI);
 839 }
 840
 841 char ModuleSummaryIndexWrapperPass::ID = 0;
 842
 843 INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
 844                       "Module Summary Analysis", false, true)
 845 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
 846 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
 847 INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis",
 848                     "Module Summary Analysis", false, true)
 849
 850 ModulePass *llvm::createModuleSummaryIndexWrapperPass() {
 851   return new ModuleSummaryIndexWrapperPass();
 852 }
 853
 854 ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass()
 855     : ModulePass(ID) {
 856   initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry());
 857 }
 858
 859 bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) {
 860   auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
 861   Index.emplace(buildModuleSummaryIndex(
 862       M,
 863       [this](const Function &F) {
 864         return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>(
 865                          *const_cast<Function *>(&F))
 866                      .getBFI());
 867       },
 868       PSI));
 869   return false;
 870 }
 871
 872 bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) {
 873   Index.reset();
 874   return false;
 875 }
 876
 877 void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
 878   AU.setPreservesAll();
 879   AU.addRequired<BlockFrequencyInfoWrapperPass>();
 880   AU.addRequired<ProfileSummaryInfoWrapperPass>();
 881 }