Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/IR/ModuleSummaryIndex.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- ModuleSummaryIndex.cpp - Module Summary Index ---------------------===//
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 file implements the module index and summary classes for the
10
// IR library.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "llvm/IR/ModuleSummaryIndex.h"
15
#include "llvm/ADT/SCCIterator.h"
16
#include "llvm/ADT/Statistic.h"
17
#include "llvm/ADT/StringMap.h"
18
#include "llvm/Support/Path.h"
19
#include "llvm/Support/raw_ostream.h"
20
using namespace llvm;
21
22
#define DEBUG_TYPE "module-summary-index"
23
24
STATISTIC(ReadOnlyLiveGVars,
25
          "Number of live global variables marked read only");
26
STATISTIC(WriteOnlyLiveGVars,
27
          "Number of live global variables marked write only");
28
29
FunctionSummary FunctionSummary::ExternalNode =
30
    FunctionSummary::makeDummyFunctionSummary({});
31
32
2.13k
bool ValueInfo::isDSOLocal() const {
33
2.13k
  // Need to check all summaries are local in case of hash collisions.
34
2.13k
  return getSummaryList().size() &&
35
2.13k
         llvm::all_of(getSummaryList(),
36
1.99k
                      [](const std::unique_ptr<GlobalValueSummary> &Summary) {
37
1.99k
                        return Summary->isDSOLocal();
38
1.99k
                      });
39
2.13k
}
40
41
100
bool ValueInfo::canAutoHide() const {
42
100
  // Can only auto hide if all copies are eligible to auto hide.
43
100
  return getSummaryList().size() &&
44
100
         llvm::all_of(getSummaryList(),
45
105
                      [](const std::unique_ptr<GlobalValueSummary> &Summary) {
46
105
                        return Summary->canAutoHide();
47
105
                      });
48
100
}
49
50
// Gets the number of readonly and writeonly refs in RefEdgeList
51
644
std::pair<unsigned, unsigned> FunctionSummary::specialRefCounts() const {
52
644
  // Here we take advantage of having all readonly and writeonly references
53
644
  // located in the end of the RefEdgeList.
54
644
  auto Refs = refs();
55
644
  unsigned RORefCnt = 0, WORefCnt = 0;
56
644
  int I;
57
661
  for (I = Refs.size() - 1; I >= 0 && 
Refs[I].isWriteOnly()135
;
--I17
)
58
17
    WORefCnt++;
59
704
  for (; I >= 0 && 
Refs[I].isReadOnly()129
;
--I60
)
60
60
    RORefCnt++;
61
644
  return {RORefCnt, WORefCnt};
62
644
}
63
64
// Collect for the given module the list of function it defines
65
// (GUID -> Summary).
66
void ModuleSummaryIndex::collectDefinedFunctionsForModule(
67
17
    StringRef ModulePath, GVSummaryMapTy &GVSummaryMap) const {
68
148
  for (auto &GlobalList : *this) {
69
148
    auto GUID = GlobalList.first;
70
148
    for (auto &GlobSummary : GlobalList.second.SummaryList) {
71
148
      auto *Summary = dyn_cast_or_null<FunctionSummary>(GlobSummary.get());
72
148
      if (!Summary)
73
4
        // Ignore global variable, focus on functions
74
4
        continue;
75
144
      // Ignore summaries from other modules.
76
144
      if (Summary->modulePath() != ModulePath)
77
126
        continue;
78
18
      GVSummaryMap[GUID] = Summary;
79
18
    }
80
148
  }
81
17
}
82
83
GlobalValueSummary *
84
ModuleSummaryIndex::getGlobalValueSummary(uint64_t ValueGUID,
85
141
                                          bool PerModuleIndex) const {
86
141
  auto VI = getValueInfo(ValueGUID);
87
141
  assert(VI && "GlobalValue not found in index");
88
141
  assert((!PerModuleIndex || VI.getSummaryList().size() == 1) &&
89
141
         "Expected a single entry per global value in per-module index");
90
141
  auto &Summary = VI.getSummaryList()[0];
91
141
  return Summary.get();
92
141
}
93
94
519
bool ModuleSummaryIndex::isGUIDLive(GlobalValue::GUID GUID) const {
95
519
  auto VI = getValueInfo(GUID);
96
519
  if (!VI)
97
6
    return true;
98
513
  const auto &SummaryList = VI.getSummaryList();
99
513
  if (SummaryList.empty())
100
25
    return true;
101
488
  for (auto &I : SummaryList)
102
489
    if (isGlobalValueLive(I.get()))
103
475
      return true;
104
488
  
return false13
;
105
488
}
106
107
1.00k
static void propagateAttributesToRefs(GlobalValueSummary *S) {
108
1.00k
  // If reference is not readonly or writeonly then referenced summary is not
109
1.00k
  // read/writeonly either. Note that:
110
1.00k
  // - All references from GlobalVarSummary are conservatively considered as
111
1.00k
  //   not readonly or writeonly. Tracking them properly requires more complex
112
1.00k
  //   analysis then we have now.
113
1.00k
  //
114
1.00k
  // - AliasSummary objects have no refs at all so this function is a no-op
115
1.00k
  //   for them.
116
1.00k
  for (auto &VI : S->refs()) {
117
215
    assert(VI.getAccessSpecifier() == 0 || isa<FunctionSummary>(S));
118
215
    for (auto &Ref : VI.getSummaryList())
119
187
      // If references to alias is not read/writeonly then aliasee
120
187
      // is not read/writeonly
121
187
      if (auto *GVS = dyn_cast<GlobalVarSummary>(Ref->getBaseObject())) {
122
153
        if (!VI.isReadOnly())
123
67
          GVS->setReadOnly(false);
124
153
        if (!VI.isWriteOnly())
125
137
          GVS->setWriteOnly(false);
126
153
      }
127
215
  }
128
1.00k
}
129
130
// Do the access attribute propagation in combined index.
131
// The goal of attribute propagation is internalization of readonly (RO)
132
// or writeonly (WO) variables. To determine which variables are RO or WO
133
// and which are not we take following steps:
134
// - During analysis we speculatively assign readonly and writeonly
135
//   attribute to all variables which can be internalized. When computing
136
//   function summary we also assign readonly or writeonly attribute to a
137
//   reference if function doesn't modify referenced variable (readonly)
138
//   or doesn't read it (writeonly).
139
//
140
// - After computing dead symbols in combined index we do the attribute
141
//   propagation. During this step we:
142
//   a. clear RO and WO attributes from variables which are preserved or
143
//      can't be imported
144
//   b. clear RO and WO attributes from variables referenced by any global
145
//      variable initializer
146
//   c. clear RO attribute from variable referenced by a function when
147
//      reference is not readonly
148
//   d. clear WO attribute from variable referenced by a function when
149
//      reference is not writeonly
150
//
151
//   Because of (c, d) we don't internalize variables read by function A
152
//   and modified by function B.
153
//
154
// Internalization itself happens in the backend after import is finished
155
// See internalizeGVsAfterImport.
156
void ModuleSummaryIndex::propagateAttributes(
157
520
    const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) {
158
520
  for (auto &P : *this)
159
1.13k
    for (auto &S : P.second.SummaryList) {
160
1.11k
      if (!isGlobalValueLive(S.get()))
161
106
        // We don't examine references from dead objects
162
106
        continue;
163
1.00k
164
1.00k
      // Global variable can't be marked read/writeonly if it is not eligible
165
1.00k
      // to import since we need to ensure that all external references get
166
1.00k
      // a local (imported) copy. It also can't be marked read/writeonly if
167
1.00k
      // it or any alias (since alias points to the same memory) are preserved
168
1.00k
      // or notEligibleToImport, since either of those means there could be
169
1.00k
      // writes (or reads in case of writeonly) that are not visible (because
170
1.00k
      // preserved means it could have external to DSO writes or reads, and
171
1.00k
      // notEligibleToImport means it could have writes or reads via inline
172
1.00k
      // assembly leading it to be in the @llvm.*used).
173
1.00k
      if (auto *GVS = dyn_cast<GlobalVarSummary>(S->getBaseObject()))
174
180
        // Here we intentionally pass S.get() not GVS, because S could be
175
180
        // an alias.
176
180
        if (!canImportGlobalVar(S.get()) ||
177
180
            
GUIDPreservedSymbols.count(P.first)107
) {
178
93
          GVS->setReadOnly(false);
179
93
          GVS->setWriteOnly(false);
180
93
        }
181
1.00k
      propagateAttributesToRefs(S.get());
182
1.00k
    }
183
520
  if (llvm::AreStatisticsEnabled())
184
0
    for (auto &P : *this)
185
0
      if (P.second.SummaryList.size())
186
0
        if (auto *GVS = dyn_cast<GlobalVarSummary>(
187
0
                P.second.SummaryList[0]->getBaseObject()))
188
0
          if (isGlobalValueLive(GVS)) {
189
0
            if (GVS->maybeReadOnly())
190
0
              ReadOnlyLiveGVars++;
191
0
            if (GVS->maybeWriteOnly())
192
0
              WriteOnlyLiveGVars++;
193
0
          }
194
520
}
195
196
// TODO: write a graphviz dumper for SCCs (see ModuleSummaryIndex::exportToDot)
197
// then delete this function and update its tests
198
LLVM_DUMP_METHOD
199
1
void ModuleSummaryIndex::dumpSCCs(raw_ostream &O) {
200
1
  for (scc_iterator<ModuleSummaryIndex *> I =
201
1
           scc_begin<ModuleSummaryIndex *>(this);
202
6
       !I.isAtEnd(); 
++I5
) {
203
5
    O << "SCC (" << utostr(I->size()) << " node" << (I->size() == 1 ? 
""4
:
"s"1
)
204
5
      << ") {\n";
205
6
    for (const ValueInfo V : *I) {
206
6
      FunctionSummary *F = nullptr;
207
6
      if (V.getSummaryList().size())
208
5
        F = cast<FunctionSummary>(V.getSummaryList().front().get());
209
6
      O << " " << (F == nullptr ? 
"External"1
:
""5
) << " " << utostr(V.getGUID())
210
6
        << (I.hasLoop() ? 
" (has loop)"2
:
""4
) << "\n";
211
6
    }
212
5
    O << "}\n";
213
5
  }
214
1
}
215
216
namespace {
217
struct Attributes {
218
  void add(const Twine &Name, const Twine &Value,
219
           const Twine &Comment = Twine());
220
  void addComment(const Twine &Comment);
221
  std::string getAsString() const;
222
223
  std::vector<std::string> Attrs;
224
  std::string Comments;
225
};
226
227
struct Edge {
228
  uint64_t SrcMod;
229
  int Hotness;
230
  GlobalValue::GUID Src;
231
  GlobalValue::GUID Dst;
232
};
233
}
234
235
void Attributes::add(const Twine &Name, const Twine &Value,
236
746
                     const Twine &Comment) {
237
746
  std::string A = Name.str();
238
746
  A += "=\"";
239
746
  A += Value.str();
240
746
  A += "\"";
241
746
  Attrs.push_back(A);
242
746
  addComment(Comment);
243
746
}
244
245
956
void Attributes::addComment(const Twine &Comment) {
246
956
  if (!Comment.isTriviallyEmpty()) {
247
627
    if (Comments.empty())
248
314
      Comments = " // ";
249
313
    else
250
313
      Comments += ", ";
251
627
    Comments += Comment.str();
252
627
  }
253
956
}
254
255
314
std::string Attributes::getAsString() const {
256
314
  if (Attrs.empty())
257
0
    return "";
258
314
259
314
  std::string Ret = "[";
260
314
  for (auto &A : Attrs)
261
746
    Ret += A + ",";
262
314
  Ret.pop_back();
263
314
  Ret += "];";
264
314
  Ret += Comments;
265
314
  return Ret;
266
314
}
267
268
299
static std::string linkageToString(GlobalValue::LinkageTypes LT) {
269
299
  switch (LT) {
270
299
  case GlobalValue::ExternalLinkage:
271
237
    return "extern";
272
299
  case GlobalValue::AvailableExternallyLinkage:
273
2
    return "av_ext";
274
299
  case GlobalValue::LinkOnceAnyLinkage:
275
2
    return "linkonce";
276
299
  case GlobalValue::LinkOnceODRLinkage:
277
13
    return "linkonce_odr";
278
299
  case GlobalValue::WeakAnyLinkage:
279
2
    return "weak";
280
299
  case GlobalValue::WeakODRLinkage:
281
2
    return "weak_odr";
282
299
  case GlobalValue::AppendingLinkage:
283
4
    return "appending";
284
299
  case GlobalValue::InternalLinkage:
285
30
    return "internal";
286
299
  case GlobalValue::PrivateLinkage:
287
2
    return "private";
288
299
  case GlobalValue::ExternalWeakLinkage:
289
0
    return "extern_weak";
290
299
  case GlobalValue::CommonLinkage:
291
5
    return "common";
292
0
  }
293
0
294
0
  return "<unknown>";
295
0
}
296
297
214
static std::string fflagsToString(FunctionSummary::FFlags F) {
298
1.07k
  auto FlagValue = [](unsigned V) { return V ? 
'1'22
:
'0'1.04k
; };
299
214
  char FlagRep[] = {FlagValue(F.ReadNone),     FlagValue(F.ReadOnly),
300
214
                    FlagValue(F.NoRecurse),    FlagValue(F.ReturnDoesNotAlias),
301
214
                    FlagValue(F.NoInline), 0};
302
214
303
214
  return FlagRep;
304
214
}
305
306
// Get string representation of function instruction count and flags.
307
299
static std::string getSummaryAttributes(GlobalValueSummary* GVS) {
308
299
  auto *FS = dyn_cast_or_null<FunctionSummary>(GVS);
309
299
  if (!FS)
310
85
    return "";
311
214
312
214
  return std::string("inst: ") + std::to_string(FS->instCount()) +
313
214
         ", ffl: " + fflagsToString(FS->fflags());
314
214
}
315
316
2
static std::string getNodeVisualName(GlobalValue::GUID Id) {
317
2
  return std::string("@") + std::to_string(Id);
318
2
}
319
320
352
static std::string getNodeVisualName(const ValueInfo &VI) {
321
352
  return VI.name().empty() ? 
getNodeVisualName(VI.getGUID())2
:
VI.name().str()350
;
322
352
}
323
324
314
static std::string getNodeLabel(const ValueInfo &VI, GlobalValueSummary *GVS) {
325
314
  if (isa<AliasSummary>(GVS))
326
15
    return getNodeVisualName(VI);
327
299
328
299
  std::string Attrs = getSummaryAttributes(GVS);
329
299
  std::string Label =
330
299
      getNodeVisualName(VI) + "|" + linkageToString(GVS->linkage());
331
299
  if (!Attrs.empty())
332
214
    Label += std::string(" (") + Attrs + ")";
333
299
  Label += "}";
334
299
335
299
  return Label;
336
299
}
337
338
// Write definition of external node, which doesn't have any
339
// specific module associated with it. Typically this is function
340
// or variable defined in native object or library.
341
static void defineExternalNode(raw_ostream &OS, const char *Pfx,
342
38
                               const ValueInfo &VI, GlobalValue::GUID Id) {
343
38
  auto StrId = std::to_string(Id);
344
38
  OS << "  " << StrId << " [label=\"";
345
38
346
38
  if (VI) {
347
38
    OS << getNodeVisualName(VI);
348
38
  } else {
349
0
    OS << getNodeVisualName(Id);
350
0
  }
351
38
  OS << "\"]; // defined externally\n";
352
38
}
353
354
72
static bool hasReadOnlyFlag(const GlobalValueSummary *S) {
355
72
  if (auto *GVS = dyn_cast<GlobalVarSummary>(S))
356
72
    return GVS->maybeReadOnly();
357
0
  return false;
358
0
}
359
360
72
static bool hasWriteOnlyFlag(const GlobalValueSummary *S) {
361
72
  if (auto *GVS = dyn_cast<GlobalVarSummary>(S))
362
72
    return GVS->maybeWriteOnly();
363
0
  return false;
364
0
}
365
366
86
void ModuleSummaryIndex::exportToDot(raw_ostream &OS) const {
367
86
  std::vector<Edge> CrossModuleEdges;
368
86
  DenseMap<GlobalValue::GUID, std::vector<uint64_t>> NodeMap;
369
86
  using GVSOrderedMapTy = std::map<GlobalValue::GUID, GlobalValueSummary *>;
370
86
  std::map<StringRef, GVSOrderedMapTy> ModuleToDefinedGVS;
371
86
  collectDefinedGVSummariesPerModule(ModuleToDefinedGVS);
372
86
373
86
  // Get node identifier in form MXXX_<GUID>. The MXXX prefix is required,
374
86
  // because we may have multiple linkonce functions summaries.
375
810
  auto NodeId = [](uint64_t ModId, GlobalValue::GUID Id) {
376
810
    return ModId == (uint64_t)-1 ? 
std::to_string(Id)45
377
810
                                 : std::string("M") + std::to_string(ModId) +
378
765
                                       "_" + std::to_string(Id);
379
810
  };
380
86
381
86
  auto DrawEdge = [&](const char *Pfx, uint64_t SrcMod, GlobalValue::GUID SrcId,
382
86
                      uint64_t DstMod, GlobalValue::GUID DstId,
383
248
                      int TypeOrHotness) {
384
248
    // 0 - alias
385
248
    // 1 - reference
386
248
    // 2 - constant reference
387
248
    // 3 - writeonly reference
388
248
    // Other value: (hotness - 4).
389
248
    TypeOrHotness += 4;
390
248
    static const char *EdgeAttrs[] = {
391
248
        " [style=dotted]; // alias",
392
248
        " [style=dashed]; // ref",
393
248
        " [style=dashed,color=forestgreen]; // const-ref",
394
248
        " [style=dashed,color=violetred]; // writeOnly-ref",
395
248
        " // call (hotness : Unknown)",
396
248
        " [color=blue]; // call (hotness : Cold)",
397
248
        " // call (hotness : None)",
398
248
        " [color=brown]; // call (hotness : Hot)",
399
248
        " [style=bold,color=red]; // call (hotness : Critical)"};
400
248
401
248
    assert(static_cast<size_t>(TypeOrHotness) <
402
248
           sizeof(EdgeAttrs) / sizeof(EdgeAttrs[0]));
403
248
    OS << Pfx << NodeId(SrcMod, SrcId) << " -> " << NodeId(DstMod, DstId)
404
248
       << EdgeAttrs[TypeOrHotness] << "\n";
405
248
  };
406
86
407
86
  OS << "digraph Summary {\n";
408
158
  for (auto &ModIt : ModuleToDefinedGVS) {
409
158
    auto ModId = getModuleId(ModIt.first);
410
158
    OS << "  // Module: " << ModIt.first << "\n";
411
158
    OS << "  subgraph cluster_" << std::to_string(ModId) << " {\n";
412
158
    OS << "    style = filled;\n";
413
158
    OS << "    color = lightgrey;\n";
414
158
    OS << "    label = \"" << sys::path::filename(ModIt.first) << "\";\n";
415
158
    OS << "    node [style=filled,fillcolor=lightblue];\n";
416
158
417
158
    auto &GVSMap = ModIt.second;
418
248
    auto Draw = [&](GlobalValue::GUID IdFrom, GlobalValue::GUID IdTo, int Hotness) {
419
248
      if (!GVSMap.count(IdTo)) {
420
144
        CrossModuleEdges.push_back({ModId, Hotness, IdFrom, IdTo});
421
144
        return;
422
144
      }
423
104
      DrawEdge("    ", ModId, IdFrom, ModId, IdTo, Hotness);
424
104
    };
425
158
426
314
    for (auto &SummaryIt : GVSMap) {
427
314
      NodeMap[SummaryIt.first].push_back(ModId);
428
314
      auto Flags = SummaryIt.second->flags();
429
314
      Attributes A;
430
314
      if (isa<FunctionSummary>(SummaryIt.second)) {
431
214
        A.add("shape", "record", "function");
432
214
      } else 
if (100
isa<AliasSummary>(SummaryIt.second)100
) {
433
15
        A.add("style", "dotted,filled", "alias");
434
15
        A.add("shape", "box");
435
85
      } else {
436
85
        A.add("shape", "Mrecord", "variable");
437
85
        if (Flags.Live && 
hasReadOnlyFlag(SummaryIt.second)72
)
438
9
          A.addComment("immutable");
439
85
        if (Flags.Live && 
hasWriteOnlyFlag(SummaryIt.second)72
)
440
5
          A.addComment("writeOnly");
441
85
      }
442
314
      if (Flags.DSOLocal)
443
189
        A.addComment("dsoLocal");
444
314
      if (Flags.CanAutoHide)
445
7
        A.addComment("canAutoHide");
446
314
447
314
      auto VI = getValueInfo(SummaryIt.first);
448
314
      A.add("label", getNodeLabel(VI, SummaryIt.second));
449
314
      if (!Flags.Live)
450
69
        A.add("fillcolor", "red", "dead");
451
245
      else if (Flags.NotEligibleToImport)
452
34
        A.add("fillcolor", "yellow", "not eligible to import");
453
314
454
314
      OS << "    " << NodeId(ModId, SummaryIt.first) << " " << A.getAsString()
455
314
         << "\n";
456
314
    }
457
158
    OS << "    // Edges:\n";
458
158
459
314
    for (auto &SummaryIt : GVSMap) {
460
314
      auto *GVS = SummaryIt.second;
461
314
      for (auto &R : GVS->refs())
462
128
        Draw(SummaryIt.first, R.getGUID(),
463
128
             R.isWriteOnly() ? 
-112
:
(R.isReadOnly() 116
?
-240
:
-376
));
464
314
465
314
      if (auto *AS = dyn_cast_or_null<AliasSummary>(SummaryIt.second)) {
466
15
        Draw(SummaryIt.first, AS->getAliaseeGUID(), -4);
467
15
        continue;
468
15
      }
469
299
470
299
      if (auto *FS = dyn_cast_or_null<FunctionSummary>(SummaryIt.second))
471
214
        for (auto &CGEdge : FS->calls())
472
105
          Draw(SummaryIt.first, CGEdge.first.getGUID(),
473
105
               static_cast<int>(CGEdge.second.Hotness));
474
299
    }
475
158
    OS << "  }\n";
476
158
  }
477
86
478
86
  OS << "  // Cross-module edges:\n";
479
144
  for (auto &E : CrossModuleEdges) {
480
144
    auto &ModList = NodeMap[E.Dst];
481
144
    if (ModList.empty()) {
482
38
      defineExternalNode(OS, "  ", getValueInfo(E.Dst), E.Dst);
483
38
      // Add fake module to the list to draw an edge to an external node
484
38
      // in the loop below.
485
38
      ModList.push_back(-1);
486
38
    }
487
144
    for (auto DstMod : ModList)
488
144
      // The edge representing call or ref is drawn to every module where target
489
144
      // symbol is defined. When target is a linkonce symbol there can be
490
144
      // multiple edges representing a single call or ref, both intra-module and
491
144
      // cross-module. As we've already drawn all intra-module edges before we
492
144
      // skip it here.
493
144
      if (DstMod != E.SrcMod)
494
144
        DrawEdge("  ", E.SrcMod, E.Src, DstMod, E.Dst, E.Hotness);
495
144
  }
496
86
497
86
  OS << "}";
498
86
}