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