Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- CoverageMapping.cpp - Code coverage mapping support ----------------===//
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 contains support for clang's and llvm's instrumentation based
10
// code coverage.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "llvm/ProfileData/Coverage/CoverageMapping.h"
15
#include "llvm/ADT/ArrayRef.h"
16
#include "llvm/ADT/DenseMap.h"
17
#include "llvm/ADT/None.h"
18
#include "llvm/ADT/Optional.h"
19
#include "llvm/ADT/SmallBitVector.h"
20
#include "llvm/ADT/SmallVector.h"
21
#include "llvm/ADT/StringRef.h"
22
#include "llvm/ProfileData/Coverage/CoverageMappingReader.h"
23
#include "llvm/ProfileData/InstrProfReader.h"
24
#include "llvm/Support/Debug.h"
25
#include "llvm/Support/Errc.h"
26
#include "llvm/Support/Error.h"
27
#include "llvm/Support/ErrorHandling.h"
28
#include "llvm/Support/ManagedStatic.h"
29
#include "llvm/Support/MemoryBuffer.h"
30
#include "llvm/Support/raw_ostream.h"
31
#include <algorithm>
32
#include <cassert>
33
#include <cstdint>
34
#include <iterator>
35
#include <map>
36
#include <memory>
37
#include <string>
38
#include <system_error>
39
#include <utility>
40
#include <vector>
41
42
using namespace llvm;
43
using namespace coverage;
44
45
#define DEBUG_TYPE "coverage-mapping"
46
47
1.17k
Counter CounterExpressionBuilder::get(const CounterExpression &E) {
48
1.17k
  auto It = ExpressionIndices.find(E);
49
1.17k
  if (It != ExpressionIndices.end())
50
559
    return Counter::getExpression(It->second);
51
614
  unsigned I = Expressions.size();
52
614
  Expressions.push_back(E);
53
614
  ExpressionIndices[E] = I;
54
614
  return Counter::getExpression(I);
55
614
}
56
57
void CounterExpressionBuilder::extractTerms(Counter C, int Factor,
58
2.83k
                                            SmallVectorImpl<Term> &Terms) {
59
2.83k
  switch (C.getKind()) {
60
2.83k
  case Counter::Zero:
61
342
    break;
62
2.83k
  case Counter::CounterValueReference:
63
1.40k
    Terms.emplace_back(C.getCounterID(), Factor);
64
1.40k
    break;
65
2.83k
  case Counter::Expression:
66
1.09k
    const auto &E = Expressions[C.getExpressionID()];
67
1.09k
    extractTerms(E.LHS, Factor, Terms);
68
1.09k
    extractTerms(
69
1.09k
        E.RHS, E.Kind == CounterExpression::Subtract ? 
-Factor440
:
Factor653
, Terms);
70
1.09k
    break;
71
2.83k
  }
72
2.83k
}
73
74
653
Counter CounterExpressionBuilder::simplify(Counter ExpressionTree) {
75
653
  // Gather constant terms.
76
653
  SmallVector<Term, 32> Terms;
77
653
  extractTerms(ExpressionTree, +1, Terms);
78
653
79
653
  // If there are no terms, this is just a zero. The algorithm below assumes at
80
653
  // least one term.
81
653
  if (Terms.size() == 0)
82
36
    return Counter::getZero();
83
617
84
617
  // Group the terms by counter ID.
85
906
  
llvm::sort(Terms, [](const Term &LHS, const Term &RHS) 617
{
86
906
    return LHS.CounterID < RHS.CounterID;
87
906
  });
88
617
89
617
  // Combine terms by counter ID to eliminate counters that sum to zero.
90
617
  auto Prev = Terms.begin();
91
1.40k
  for (auto I = Prev + 1, E = Terms.end(); I != E; 
++I787
) {
92
787
    if (I->CounterID == Prev->CounterID) {
93
140
      Prev->Factor += I->Factor;
94
140
      continue;
95
140
    }
96
647
    ++Prev;
97
647
    *Prev = *I;
98
647
  }
99
617
  Terms.erase(++Prev, Terms.end());
100
617
101
617
  Counter C;
102
617
  // Create additions. We do this before subtractions to avoid constructs like
103
617
  // ((0 - X) + Y), as opposed to (Y - X).
104
1.26k
  for (auto T : Terms) {
105
1.26k
    if (T.Factor <= 0)
106
438
      continue;
107
1.65k
    
for (int I = 0; 826
I < T.Factor;
++I830
)
108
830
      if (C.isZero())
109
616
        C = Counter::getCounter(T.CounterID);
110
214
      else
111
214
        C = get(CounterExpression(CounterExpression::Add, C,
112
214
                                  Counter::getCounter(T.CounterID)));
113
826
  }
114
617
115
617
  // Create subtractions.
116
1.26k
  for (auto T : Terms) {
117
1.26k
    if (T.Factor >= 0)
118
958
      continue;
119
612
    
for (int I = 0; 306
I < -T.Factor;
++I306
)
120
306
      C = get(CounterExpression(CounterExpression::Subtract, C,
121
306
                                Counter::getCounter(T.CounterID)));
122
306
  }
123
617
  return C;
124
617
}
125
126
459
Counter CounterExpressionBuilder::add(Counter LHS, Counter RHS) {
127
459
  return simplify(get(CounterExpression(CounterExpression::Add, LHS, RHS)));
128
459
}
129
130
194
Counter CounterExpressionBuilder::subtract(Counter LHS, Counter RHS) {
131
194
  return simplify(
132
194
      get(CounterExpression(CounterExpression::Subtract, LHS, RHS)));
133
194
}
134
135
1.82k
void CounterMappingContext::dump(const Counter &C, raw_ostream &OS) const {
136
1.82k
  switch (C.getKind()) {
137
1.82k
  case Counter::Zero:
138
56
    OS << '0';
139
56
    return;
140
1.82k
  case Counter::CounterValueReference:
141
1.44k
    OS << '#' << C.getCounterID();
142
1.44k
    break;
143
1.82k
  case Counter::Expression: {
144
318
    if (C.getExpressionID() >= Expressions.size())
145
0
      return;
146
318
    const auto &E = Expressions[C.getExpressionID()];
147
318
    OS << '(';
148
318
    dump(E.LHS, OS);
149
318
    OS << (E.Kind == CounterExpression::Subtract ? 
" - "216
:
" + "102
);
150
318
    dump(E.RHS, OS);
151
318
    OS << ')';
152
318
    break;
153
318
  }
154
1.76k
  }
155
1.76k
  if (CounterValues.empty())
156
1.76k
    return;
157
0
  Expected<int64_t> Value = evaluate(C);
158
0
  if (auto E = Value.takeError()) {
159
0
    consumeError(std::move(E));
160
0
    return;
161
0
  }
162
0
  OS << '[' << *Value << ']';
163
0
}
164
165
3.20k
Expected<int64_t> CounterMappingContext::evaluate(const Counter &C) const {
166
3.20k
  switch (C.getKind()) {
167
3.20k
  case Counter::Zero:
168
92
    return 0;
169
3.20k
  case Counter::CounterValueReference:
170
2.58k
    if (C.getCounterID() >= CounterValues.size())
171
0
      return errorCodeToError(errc::argument_out_of_domain);
172
2.58k
    return CounterValues[C.getCounterID()];
173
2.58k
  case Counter::Expression: {
174
524
    if (C.getExpressionID() >= Expressions.size())
175
0
      return errorCodeToError(errc::argument_out_of_domain);
176
524
    const auto &E = Expressions[C.getExpressionID()];
177
524
    Expected<int64_t> LHS = evaluate(E.LHS);
178
524
    if (!LHS)
179
0
      return LHS;
180
524
    Expected<int64_t> RHS = evaluate(E.RHS);
181
524
    if (!RHS)
182
0
      return RHS;
183
524
    return E.Kind == CounterExpression::Subtract ? 
*LHS - *RHS385
:
*LHS + *RHS139
;
184
524
  }
185
0
  }
186
0
  llvm_unreachable("Unhandled CounterKind");
187
0
}
188
189
1.24k
void FunctionRecordIterator::skipOtherFiles() {
190
1.30k
  while (Current != Records.end() && 
!Filename.empty()1.01k
&&
191
1.30k
         
Filename != Current->Filenames[0]140
)
192
58
    ++Current;
193
1.24k
  if (Current == Records.end())
194
293
    *this = FunctionRecordIterator();
195
1.24k
}
196
197
Error CoverageMapping::loadFunctionRecord(
198
    const CoverageMappingRecord &Record,
199
525
    IndexedInstrProfReader &ProfileReader) {
200
525
  StringRef OrigFuncName = Record.FunctionName;
201
525
  if (OrigFuncName.empty())
202
4
    return make_error<CoverageMapError>(coveragemap_error::malformed);
203
521
204
521
  if (Record.Filenames.empty())
205
4
    OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName);
206
517
  else
207
517
    OrigFuncName = getFuncNameWithoutPrefix(OrigFuncName, Record.Filenames[0]);
208
521
209
521
  CounterMappingContext Ctx(Record.Expressions);
210
521
211
521
  std::vector<uint64_t> Counts;
212
521
  if (Error E = ProfileReader.getFunctionCounts(Record.FunctionName,
213
45
                                                Record.FunctionHash, Counts)) {
214
45
    instrprof_error IPE = InstrProfError::take(std::move(E));
215
45
    if (IPE == instrprof_error::hash_mismatch) {
216
1
      FuncHashMismatches.emplace_back(Record.FunctionName, Record.FunctionHash);
217
1
      return Error::success();
218
44
    } else if (IPE != instrprof_error::unknown_function)
219
0
      return make_error<InstrProfError>(IPE);
220
44
    Counts.assign(Record.MappingRegions.size(), 0);
221
44
  }
222
521
  Ctx.setCounts(Counts);
223
520
224
520
  assert(!Record.MappingRegions.empty() && "Function has no regions");
225
520
226
520
  // This coverage record is a zero region for a function that's unused in
227
520
  // some TU, but used in a different TU. Ignore it. The coverage maps from the
228
520
  // the other TU will either be loaded (providing full region counts) or they
229
520
  // won't (in which case we don't unintuitively report functions as uncovered
230
520
  // when they have non-zero counts in the profile).
231
520
  if (Record.MappingRegions.size() == 1 &&
232
520
      
Record.MappingRegions[0].Count.isZero()220
&&
Counts[0] > 017
)
233
0
    return Error::success();
234
520
235
520
  FunctionRecord Function(OrigFuncName, Record.Filenames);
236
2.15k
  for (const auto &Region : Record.MappingRegions) {
237
2.15k
    Expected<int64_t> ExecutionCount = Ctx.evaluate(Region.Count);
238
2.15k
    if (auto E = ExecutionCount.takeError()) {
239
0
      consumeError(std::move(E));
240
0
      return Error::success();
241
0
    }
242
2.15k
    Function.pushRegion(Region, *ExecutionCount);
243
2.15k
  }
244
520
245
520
  // Don't create records for (filenames, function) pairs we've already seen.
246
520
  auto FilenamesHash = hash_combine_range(Record.Filenames.begin(),
247
520
                                          Record.Filenames.end());
248
520
  if (!RecordProvenance[FilenamesHash].insert(hash_value(OrigFuncName)).second)
249
8
    return Error::success();
250
512
251
512
  Functions.push_back(std::move(Function));
252
512
  return Error::success();
253
512
}
254
255
Expected<std::unique_ptr<CoverageMapping>> CoverageMapping::load(
256
    ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders,
257
215
    IndexedInstrProfReader &ProfileReader) {
258
215
  auto Coverage = std::unique_ptr<CoverageMapping>(new CoverageMapping());
259
215
260
235
  for (const auto &CoverageReader : CoverageReaders) {
261
526
    for (auto RecordOrErr : *CoverageReader) {
262
526
      if (Error E = RecordOrErr.takeError())
263
1
        return std::move(E);
264
525
      const auto &Record = *RecordOrErr;
265
525
      if (Error E = Coverage->loadFunctionRecord(Record, ProfileReader))
266
4
        return std::move(E);
267
525
    }
268
235
  }
269
215
270
215
  
return std::move(Coverage)210
;
271
215
}
272
273
Expected<std::unique_ptr<CoverageMapping>>
274
CoverageMapping::load(ArrayRef<StringRef> ObjectFilenames,
275
116
                      StringRef ProfileFilename, ArrayRef<StringRef> Arches) {
276
116
  auto ProfileReaderOrErr = IndexedInstrProfReader::create(ProfileFilename);
277
116
  if (Error E = ProfileReaderOrErr.takeError())
278
0
    return std::move(E);
279
116
  auto ProfileReader = std::move(ProfileReaderOrErr.get());
280
116
281
116
  SmallVector<std::unique_ptr<CoverageMappingReader>, 4> Readers;
282
116
  SmallVector<std::unique_ptr<MemoryBuffer>, 4> Buffers;
283
119
  for (const auto &File : llvm::enumerate(ObjectFilenames)) {
284
119
    auto CovMappingBufOrErr = MemoryBuffer::getFileOrSTDIN(File.value());
285
119
    if (std::error_code EC = CovMappingBufOrErr.getError())
286
0
      return errorCodeToError(EC);
287
119
    StringRef Arch = Arches.empty() ? 
StringRef()111
:
Arches[File.index()]8
;
288
119
    MemoryBufferRef CovMappingBufRef =
289
119
        CovMappingBufOrErr.get()->getMemBufferRef();
290
119
    auto CoverageReadersOrErr =
291
119
        BinaryCoverageReader::create(CovMappingBufRef, Arch, Buffers);
292
119
    if (Error E = CoverageReadersOrErr.takeError())
293
1
      return std::move(E);
294
118
    for (auto &Reader : CoverageReadersOrErr.get())
295
123
      Readers.push_back(std::move(Reader));
296
118
    Buffers.push_back(std::move(CovMappingBufOrErr.get()));
297
118
  }
298
116
  
return load(Readers, *ProfileReader)115
;
299
116
}
300
301
namespace {
302
303
/// Distributes functions into instantiation sets.
304
///
305
/// An instantiation set is a collection of functions that have the same source
306
/// code, ie, template functions specializations.
307
class FunctionInstantiationSetCollector {
308
  using MapT = std::map<LineColPair, std::vector<const FunctionRecord *>>;
309
  MapT InstantiatedFunctions;
310
311
public:
312
380
  void insert(const FunctionRecord &Function, unsigned FileID) {
313
380
    auto I = Function.CountedRegions.begin(), E = Function.CountedRegions.end();
314
380
    while (I != E && I->FileID != FileID)
315
0
      ++I;
316
380
    assert(I != E && "function does not cover the given file");
317
380
    auto &Functions = InstantiatedFunctions[I->startLoc()];
318
380
    Functions.push_back(&Function);
319
380
  }
320
321
255
  MapT::iterator begin() { return InstantiatedFunctions.begin(); }
322
255
  MapT::iterator end() { return InstantiatedFunctions.end(); }
323
};
324
325
class SegmentBuilder {
326
  std::vector<CoverageSegment> &Segments;
327
  SmallVector<const CountedRegion *, 8> ActiveRegions;
328
329
524
  SegmentBuilder(std::vector<CoverageSegment> &Segments) : Segments(Segments) {}
330
331
  /// Emit a segment with the count from \p Region starting at \p StartLoc.
332
  //
333
  /// \p IsRegionEntry: The segment is at the start of a new non-gap region.
334
  /// \p EmitSkippedRegion: The segment must be emitted as a skipped region.
335
  void startSegment(const CountedRegion &Region, LineColPair StartLoc,
336
4.13k
                    bool IsRegionEntry, bool EmitSkippedRegion = false) {
337
4.13k
    bool HasCount = !EmitSkippedRegion &&
338
4.13k
                    
(Region.Kind != CounterMappingRegion::SkippedRegion)3.55k
;
339
4.13k
340
4.13k
    // If the new segment wouldn't affect coverage rendering, skip it.
341
4.13k
    if (!Segments.empty() && 
!IsRegionEntry3.61k
&&
!EmitSkippedRegion2.15k
) {
342
1.59k
      const auto &Last = Segments.back();
343
1.59k
      if (Last.HasCount == HasCount && 
Last.Count == Region.ExecutionCount1.59k
&&
344
1.59k
          
!Last.IsRegionEntry544
)
345
101
        return;
346
4.03k
    }
347
4.03k
348
4.03k
    if (HasCount)
349
3.45k
      Segments.emplace_back(StartLoc.first, StartLoc.second,
350
3.45k
                            Region.ExecutionCount, IsRegionEntry,
351
3.45k
                            Region.Kind == CounterMappingRegion::GapRegion);
352
580
    else
353
580
      Segments.emplace_back(StartLoc.first, StartLoc.second, IsRegionEntry);
354
4.03k
355
4.03k
    LLVM_DEBUG({
356
4.03k
      const auto &Last = Segments.back();
357
4.03k
      dbgs() << "Segment at " << Last.Line << ":" << Last.Col
358
4.03k
             << " (count = " << Last.Count << ")"
359
4.03k
             << (Last.IsRegionEntry ? ", RegionEntry" : "")
360
4.03k
             << (!Last.HasCount ? ", Skipped" : "")
361
4.03k
             << (Last.IsGapRegion ? ", Gap" : "") << "\n";
362
4.03k
    });
363
4.03k
  }
364
365
  /// Emit segments for active regions which end before \p Loc.
366
  ///
367
  /// \p Loc: The start location of the next region. If None, all active
368
  /// regions are completed.
369
  /// \p FirstCompletedRegion: Index of the first completed region.
370
  void completeRegionsUntil(Optional<LineColPair> Loc,
371
2.12k
                            unsigned FirstCompletedRegion) {
372
2.12k
    // Sort the completed regions by end location. This makes it simple to
373
2.12k
    // emit closing segments in sorted order.
374
2.12k
    auto CompletedRegionsIt = ActiveRegions.begin() + FirstCompletedRegion;
375
2.12k
    std::stable_sort(CompletedRegionsIt, ActiveRegions.end(),
376
2.12k
                      [](const CountedRegion *L, const CountedRegion *R) {
377
551
                        return L->endLoc() < R->endLoc();
378
551
                      });
379
2.12k
380
2.12k
    // Emit segments for all completed regions.
381
2.57k
    for (unsigned I = FirstCompletedRegion + 1, E = ActiveRegions.size(); I < E;
382
2.12k
         
++I447
) {
383
451
      const auto *CompletedRegion = ActiveRegions[I];
384
451
      assert((!Loc || CompletedRegion->endLoc() <= *Loc) &&
385
451
             "Completed region ends after start of new region");
386
451
387
451
      const auto *PrevCompletedRegion = ActiveRegions[I - 1];
388
451
      auto CompletedSegmentLoc = PrevCompletedRegion->endLoc();
389
451
390
451
      // Don't emit any more segments if they start where the new region begins.
391
451
      if (Loc && 
CompletedSegmentLoc == *Loc86
)
392
4
        break;
393
447
394
447
      // Don't emit a segment if the next completed region ends at the same
395
447
      // location as this one.
396
447
      if (CompletedSegmentLoc == CompletedRegion->endLoc())
397
197
        continue;
398
250
399
250
      // Use the count from the last completed region which ends at this loc.
400
331
      
for (unsigned J = I + 1; 250
J < E;
++J81
)
401
81
        if (CompletedRegion->endLoc() == ActiveRegions[J]->endLoc())
402
57
          CompletedRegion = ActiveRegions[J];
403
250
404
250
      startSegment(*CompletedRegion, CompletedSegmentLoc, false);
405
250
    }
406
2.12k
407
2.12k
    auto Last = ActiveRegions.back();
408
2.12k
    if (FirstCompletedRegion && 
Last->endLoc() != *Loc1.55k
) {
409
747
      // If there's a gap after the end of the last completed region and the
410
747
      // start of the new region, use the last active region to fill the gap.
411
747
      startSegment(*ActiveRegions[FirstCompletedRegion - 1], Last->endLoc(),
412
747
                   false);
413
1.37k
    } else if (!FirstCompletedRegion && 
(566
!Loc566
||
*Loc != Last->endLoc()58
)) {
414
561
      // Emit a skipped segment if there are no more active regions. This
415
561
      // ensures that gaps between functions are marked correctly.
416
561
      startSegment(*Last, Last->endLoc(), false, true);
417
561
    }
418
2.12k
419
2.12k
    // Pop the completed regions.
420
2.12k
    ActiveRegions.erase(CompletedRegionsIt, ActiveRegions.end());
421
2.12k
  }
422
423
522
  void buildSegmentsImpl(ArrayRef<CountedRegion> Regions) {
424
2.59k
    for (const auto &CR : enumerate(Regions)) {
425
2.59k
      auto CurStartLoc = CR.value().startLoc();
426
2.59k
427
2.59k
      // Active regions which end before the current region need to be popped.
428
2.59k
      auto CompletedRegions =
429
2.59k
          std::stable_partition(ActiveRegions.begin(), ActiveRegions.end(),
430
4.07k
                                [&](const CountedRegion *Region) {
431
4.07k
                                  return !(Region->endLoc() <= CurStartLoc);
432
4.07k
                                });
433
2.59k
      if (CompletedRegions != ActiveRegions.end()) {
434
1.61k
        unsigned FirstCompletedRegion =
435
1.61k
            std::distance(ActiveRegions.begin(), CompletedRegions);
436
1.61k
        completeRegionsUntil(CurStartLoc, FirstCompletedRegion);
437
1.61k
      }
438
2.59k
439
2.59k
      bool GapRegion = CR.value().Kind == CounterMappingRegion::GapRegion;
440
2.59k
441
2.59k
      // Try to emit a segment for the current region.
442
2.59k
      if (CurStartLoc == CR.value().endLoc()) {
443
20
        // Avoid making zero-length regions active. If it's the last region,
444
20
        // emit a skipped segment. Otherwise use its predecessor's count.
445
20
        const bool Skipped = (CR.index() + 1) == Regions.size();
446
20
        startSegment(ActiveRegions.empty() ? 
CR.value()16
:
*ActiveRegions.back()4
,
447
20
                     CurStartLoc, !GapRegion, Skipped);
448
20
        continue;
449
20
      }
450
2.57k
      if (CR.index() + 1 == Regions.size() ||
451
2.57k
          
CurStartLoc != Regions[CR.index() + 1].startLoc()2.07k
) {
452
2.55k
        // Emit a segment if the next region doesn't start at the same location
453
2.55k
        // as this one.
454
2.55k
        startSegment(CR.value(), CurStartLoc, !GapRegion);
455
2.55k
      }
456
2.57k
457
2.57k
      // This region is active (i.e not completed).
458
2.57k
      ActiveRegions.push_back(&CR.value());
459
2.57k
    }
460
522
461
522
    // Complete any remaining active regions.
462
522
    if (!ActiveRegions.empty())
463
509
      completeRegionsUntil(None, 0);
464
522
  }
465
466
  /// Sort a nested sequence of regions from a single file.
467
524
  static void sortNestedRegions(MutableArrayRef<CountedRegion> Regions) {
468
4.07k
    llvm::sort(Regions, [](const CountedRegion &LHS, const CountedRegion &RHS) {
469
4.07k
      if (LHS.startLoc() != RHS.startLoc())
470
3.70k
        return LHS.startLoc() < RHS.startLoc();
471
363
      if (LHS.endLoc() != RHS.endLoc())
472
20
        // When LHS completely contains RHS, we sort LHS first.
473
20
        return RHS.endLoc() < LHS.endLoc();
474
343
      // If LHS and RHS cover the same area, we need to sort them according
475
343
      // to their kinds so that the most suitable region will become "active"
476
343
      // in combineRegions(). Because we accumulate counter values only from
477
343
      // regions of the same kind as the first region of the area, prefer
478
343
      // CodeRegion to ExpansionRegion and ExpansionRegion to SkippedRegion.
479
343
      static_assert(CounterMappingRegion::CodeRegion <
480
343
                            CounterMappingRegion::ExpansionRegion &&
481
343
                        CounterMappingRegion::ExpansionRegion <
482
343
                            CounterMappingRegion::SkippedRegion,
483
343
                    "Unexpected order of region kind values");
484
343
      return LHS.Kind < RHS.Kind;
485
343
    });
486
524
  }
487
488
  /// Combine counts of regions which cover the same area.
489
  static ArrayRef<CountedRegion>
490
523
  combineRegions(MutableArrayRef<CountedRegion> Regions) {
491
523
    if (Regions.empty())
492
0
      return Regions;
493
523
    auto Active = Regions.begin();
494
523
    auto End = Regions.end();
495
2.93k
    for (auto I = Regions.begin() + 1; I != End; 
++I2.41k
) {
496
2.41k
      if (Active->startLoc() != I->startLoc() ||
497
2.41k
          
Active->endLoc() != I->endLoc()364
) {
498
2.07k
        // Shift to the next region.
499
2.07k
        ++Active;
500
2.07k
        if (Active != I)
501
228
          *Active = *I;
502
2.07k
        continue;
503
2.07k
      }
504
345
      // Merge duplicate region.
505
345
      // If CodeRegions and ExpansionRegions cover the same area, it's probably
506
345
      // a macro which is fully expanded to another macro. In that case, we need
507
345
      // to accumulate counts only from CodeRegions, or else the area will be
508
345
      // counted twice.
509
345
      // On the other hand, a macro may have a nested macro in its body. If the
510
345
      // outer macro is used several times, the ExpansionRegion for the nested
511
345
      // macro will also be added several times. These ExpansionRegions cover
512
345
      // the same source locations and have to be combined to reach the correct
513
345
      // value for that area.
514
345
      // We add counts of the regions of the same kind as the active region
515
345
      // to handle the both situations.
516
345
      if (I->Kind == Active->Kind)
517
340
        Active->ExecutionCount += I->ExecutionCount;
518
345
    }
519
523
    return Regions.drop_back(std::distance(++Active, End));
520
523
  }
521
522
public:
523
  /// Build a sorted list of CoverageSegments from a list of Regions.
524
  static std::vector<CoverageSegment>
525
523
  buildSegments(MutableArrayRef<CountedRegion> Regions) {
526
523
    std::vector<CoverageSegment> Segments;
527
523
    SegmentBuilder Builder(Segments);
528
523
529
523
    sortNestedRegions(Regions);
530
523
    ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions);
531
523
532
523
    LLVM_DEBUG({
533
523
      dbgs() << "Combined regions:\n";
534
523
      for (const auto &CR : CombinedRegions)
535
523
        dbgs() << "  " << CR.LineStart << ":" << CR.ColumnStart << " -> "
536
523
               << CR.LineEnd << ":" << CR.ColumnEnd
537
523
               << " (count=" << CR.ExecutionCount << ")\n";
538
523
    });
539
523
540
523
    Builder.buildSegmentsImpl(CombinedRegions);
541
523
542
#ifndef NDEBUG
543
    for (unsigned I = 1, E = Segments.size(); I < E; ++I) {
544
      const auto &L = Segments[I - 1];
545
      const auto &R = Segments[I];
546
      if (!(L.Line < R.Line) && !(L.Line == R.Line && L.Col < R.Col)) {
547
        LLVM_DEBUG(dbgs() << " ! Segment " << L.Line << ":" << L.Col
548
                          << " followed by " << R.Line << ":" << R.Col << "\n");
549
        assert(false && "Coverage segments not unique or sorted");
550
      }
551
    }
552
#endif
553
554
523
    return Segments;
555
523
  }
556
};
557
558
} // end anonymous namespace
559
560
215
std::vector<StringRef> CoverageMapping::getUniqueSourceFiles() const {
561
215
  std::vector<StringRef> Filenames;
562
215
  for (const auto &Function : getCoveredFunctions())
563
751
    Filenames.insert(Filenames.end(), Function.Filenames.begin(),
564
751
                     Function.Filenames.end());
565
215
  llvm::sort(Filenames);
566
215
  auto Last = std::unique(Filenames.begin(), Filenames.end());
567
215
  Filenames.erase(Last, Filenames.end());
568
215
  return Filenames;
569
215
}
570
571
static SmallBitVector gatherFileIDs(StringRef SourceFile,
572
915
                                    const FunctionRecord &Function) {
573
915
  SmallBitVector FilenameEquivalence(Function.Filenames.size(), false);
574
1.88k
  for (unsigned I = 0, E = Function.Filenames.size(); I < E; 
++I970
)
575
970
    if (SourceFile == Function.Filenames[I])
576
269
      FilenameEquivalence[I] = true;
577
915
  return FilenameEquivalence;
578
915
}
579
580
/// Return the ID of the file where the definition of the function is located.
581
2.82k
static Optional<unsigned> findMainViewFileID(const FunctionRecord &Function) {
582
2.82k
  SmallBitVector IsNotExpandedFile(Function.Filenames.size(), true);
583
2.82k
  for (const auto &CR : Function.CountedRegions)
584
14.9k
    if (CR.Kind == CounterMappingRegion::ExpansionRegion)
585
74
      IsNotExpandedFile[CR.ExpandedFileID] = false;
586
2.82k
  int I = IsNotExpandedFile.find_first();
587
2.82k
  if (I == -1)
588
0
    return None;
589
2.82k
  return I;
590
2.82k
}
591
592
/// Check if SourceFile is the file that contains the definition of
593
/// the Function. Return the ID of the file in that case or None otherwise.
594
static Optional<unsigned> findMainViewFileID(StringRef SourceFile,
595
2.49k
                                             const FunctionRecord &Function) {
596
2.49k
  Optional<unsigned> I = findMainViewFileID(Function);
597
2.49k
  if (I && 
SourceFile == Function.Filenames[*I]2.48k
)
598
622
    return I;
599
1.86k
  return None;
600
1.86k
}
601
602
2.92k
static bool isExpansion(const CountedRegion &R, unsigned FileID) {
603
2.92k
  return R.Kind == CounterMappingRegion::ExpansionRegion && 
R.FileID == FileID35
;
604
2.92k
}
605
606
183
CoverageData CoverageMapping::getCoverageForFile(StringRef Filename) const {
607
183
  CoverageData FileCoverage(Filename);
608
183
  std::vector<CountedRegion> Regions;
609
183
610
915
  for (const auto &Function : Functions) {
611
915
    auto MainFileID = findMainViewFileID(Filename, Function);
612
915
    auto FileIDs = gatherFileIDs(Filename, Function);
613
915
    for (const auto &CR : Function.CountedRegions)
614
5.03k
      if (FileIDs.test(CR.FileID)) {
615
1.30k
        Regions.push_back(CR);
616
1.30k
        if (MainFileID && 
isExpansion(CR, *MainFileID)1.28k
)
617
17
          FileCoverage.Expansions.emplace_back(CR, Function);
618
1.30k
      }
619
915
  }
620
183
621
183
  LLVM_DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n");
622
183
  FileCoverage.Segments = SegmentBuilder::buildSegments(Regions);
623
183
624
183
  return FileCoverage;
625
183
}
626
627
std::vector<InstantiationGroup>
628
254
CoverageMapping::getInstantiationGroups(StringRef Filename) const {
629
254
  FunctionInstantiationSetCollector InstantiationSetCollector;
630
1.57k
  for (const auto &Function : Functions) {
631
1.57k
    auto MainFileID = findMainViewFileID(Filename, Function);
632
1.57k
    if (!MainFileID)
633
1.19k
      continue;
634
379
    InstantiationSetCollector.insert(Function, *MainFileID);
635
379
  }
636
254
637
254
  std::vector<InstantiationGroup> Result;
638
310
  for (auto &InstantiationSet : InstantiationSetCollector) {
639
310
    InstantiationGroup IG{InstantiationSet.first.first,
640
310
                          InstantiationSet.first.second,
641
310
                          std::move(InstantiationSet.second)};
642
310
    Result.emplace_back(std::move(IG));
643
310
  }
644
254
  return Result;
645
254
}
646
647
CoverageData
648
336
CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) const {
649
336
  auto MainFileID = findMainViewFileID(Function);
650
336
  if (!MainFileID)
651
0
    return CoverageData();
652
336
653
336
  CoverageData FunctionCoverage(Function.Filenames[*MainFileID]);
654
336
  std::vector<CountedRegion> Regions;
655
336
  for (const auto &CR : Function.CountedRegions)
656
1.66k
    if (CR.FileID == *MainFileID) {
657
1.62k
      Regions.push_back(CR);
658
1.62k
      if (isExpansion(CR, *MainFileID))
659
8
        FunctionCoverage.Expansions.emplace_back(CR, Function);
660
1.62k
    }
661
336
662
336
  LLVM_DEBUG(dbgs() << "Emitting segments for function: " << Function.Name
663
336
                    << "\n");
664
336
  FunctionCoverage.Segments = SegmentBuilder::buildSegments(Regions);
665
336
666
336
  return FunctionCoverage;
667
336
}
668
669
CoverageData CoverageMapping::getCoverageForExpansion(
670
3
    const ExpansionRecord &Expansion) const {
671
3
  CoverageData ExpansionCoverage(
672
3
      Expansion.Function.Filenames[Expansion.FileID]);
673
3
  std::vector<CountedRegion> Regions;
674
3
  for (const auto &CR : Expansion.Function.CountedRegions)
675
48
    if (CR.FileID == Expansion.FileID) {
676
12
      Regions.push_back(CR);
677
12
      if (isExpansion(CR, Expansion.FileID))
678
2
        ExpansionCoverage.Expansions.emplace_back(CR, Expansion.Function);
679
12
    }
680
3
681
3
  LLVM_DEBUG(dbgs() << "Emitting segments for expansion of file "
682
3
                    << Expansion.FileID << "\n");
683
3
  ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions);
684
3
685
3
  return ExpansionCoverage;
686
3
}
687
688
LineCoverageStats::LineCoverageStats(
689
    ArrayRef<const CoverageSegment *> LineSegments,
690
    const CoverageSegment *WrappedSegment, unsigned Line)
691
    : ExecutionCount(0), HasMultipleRegions(false), Mapped(false), Line(Line),
692
3.93k
      LineSegments(LineSegments), WrappedSegment(WrappedSegment) {
693
3.93k
  // Find the minimum number of regions which start in this line.
694
3.93k
  unsigned MinRegionCount = 0;
695
5.93k
  auto isStartOfRegion = [](const CoverageSegment *S) {
696
5.93k
    return !S->IsGapRegion && 
S->HasCount5.10k
&&
S->IsRegionEntry4.60k
;
697
5.93k
  };
698
7.05k
  for (unsigned I = 0; I < LineSegments.size() && 
MinRegionCount < 23.26k
;
++I3.11k
)
699
3.11k
    if (isStartOfRegion(LineSegments[I]))
700
1.55k
      ++MinRegionCount;
701
3.93k
702
3.93k
  bool StartOfSkippedRegion = !LineSegments.empty() &&
703
3.93k
                              
!LineSegments.front()->HasCount1.92k
&&
704
3.93k
                              
LineSegments.front()->IsRegionEntry382
;
705
3.93k
706
3.93k
  HasMultipleRegions = MinRegionCount > 1;
707
3.93k
  Mapped =
708
3.93k
      !StartOfSkippedRegion &&
709
3.93k
      
(3.92k
(3.92k
WrappedSegment3.92k
&&
WrappedSegment->HasCount2.86k
) ||
(MinRegionCount > 0)1.36k
);
710
3.93k
711
3.93k
  if (!Mapped)
712
932
    return;
713
3.00k
714
3.00k
  // Pick the max count from the non-gap, region entry segments and the
715
3.00k
  // wrapped count.
716
3.00k
  if (WrappedSegment)
717
2.59k
    ExecutionCount = WrappedSegment->Count;
718
3.00k
  if (!MinRegionCount)
719
1.70k
    return;
720
1.29k
  for (const auto *LS : LineSegments)
721
2.82k
    if (isStartOfRegion(LS))
722
1.66k
      ExecutionCount = std::max(ExecutionCount, LS->Count);
723
1.29k
}
724
725
5.13k
LineCoverageIterator &LineCoverageIterator::operator++() {
726
5.13k
  if (Next == CD.end()) {
727
1.19k
    Stats = LineCoverageStats();
728
1.19k
    Ended = true;
729
1.19k
    return *this;
730
1.19k
  }
731
3.93k
  if (Segments.size())
732
1.51k
    WrappedSegment = Segments.back();
733
3.93k
  Segments.clear();
734
7.39k
  while (Next != CD.end() && 
Next->Line == Line6.96k
)
735
3.45k
    Segments.push_back(&*Next++);
736
3.93k
  Stats = LineCoverageStats(Segments, WrappedSegment, Line);
737
3.93k
  ++Line;
738
3.93k
  return *this;
739
3.93k
}
740
741
5
static std::string getCoverageMapErrString(coveragemap_error Err) {
742
5
  switch (Err) {
743
5
  case coveragemap_error::success:
744
0
    return "Success";
745
5
  case coveragemap_error::eof:
746
0
    return "End of File";
747
5
  case coveragemap_error::no_data_found:
748
0
    return "No coverage data found";
749
5
  case coveragemap_error::unsupported_version:
750
0
    return "Unsupported coverage format version";
751
5
  case coveragemap_error::truncated:
752
0
    return "Truncated coverage data";
753
5
  case coveragemap_error::malformed:
754
5
    return "Malformed coverage data";
755
0
  }
756
0
  llvm_unreachable("A value of coveragemap_error has no message.");
757
0
}
758
759
namespace {
760
761
// FIXME: This class is only here to support the transition to llvm::Error. It
762
// will be removed once this transition is complete. Clients should prefer to
763
// deal with the Error value directly, rather than converting to error_code.
764
class CoverageMappingErrorCategoryType : public std::error_category {
765
0
  const char *name() const noexcept override { return "llvm.coveragemap"; }
766
0
  std::string message(int IE) const override {
767
0
    return getCoverageMapErrString(static_cast<coveragemap_error>(IE));
768
0
  }
769
};
770
771
} // end anonymous namespace
772
773
5
std::string CoverageMapError::message() const {
774
5
  return getCoverageMapErrString(Err);
775
5
}
776
777
static ManagedStatic<CoverageMappingErrorCategoryType> ErrorCategory;
778
779
0
const std::error_category &llvm::coverage::coveragemap_category() {
780
0
  return *ErrorCategory;
781
0
}
782
783
char CoverageMapError::ID = 0;