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