Coverage Report

Created: 2019-07-24 05:18

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