Coverage Report

Created: 2020-02-15 09:57

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/CodeGen/CoverageMappingGen.cpp
Line
Count
Source (jump to first uncovered line)
1
//===--- CoverageMappingGen.cpp - Coverage mapping generation ---*- C++ -*-===//
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
// Instrumentation-based code coverage mapping generator
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "CoverageMappingGen.h"
14
#include "CodeGenFunction.h"
15
#include "clang/AST/StmtVisitor.h"
16
#include "clang/Lex/Lexer.h"
17
#include "llvm/ADT/SmallSet.h"
18
#include "llvm/ADT/StringExtras.h"
19
#include "llvm/ADT/Optional.h"
20
#include "llvm/ProfileData/Coverage/CoverageMapping.h"
21
#include "llvm/ProfileData/Coverage/CoverageMappingReader.h"
22
#include "llvm/ProfileData/Coverage/CoverageMappingWriter.h"
23
#include "llvm/ProfileData/InstrProfReader.h"
24
#include "llvm/Support/FileSystem.h"
25
#include "llvm/Support/Path.h"
26
27
using namespace clang;
28
using namespace CodeGen;
29
using namespace llvm::coverage;
30
31
13
void CoverageSourceInfo::SourceRangeSkipped(SourceRange Range, SourceLocation) {
32
13
  SkippedRanges.push_back(Range);
33
13
}
34
35
namespace {
36
37
/// A region of source code that can be mapped to a counter.
38
class SourceMappingRegion {
39
  Counter Count;
40
41
  /// The region's starting location.
42
  Optional<SourceLocation> LocStart;
43
44
  /// The region's ending location.
45
  Optional<SourceLocation> LocEnd;
46
47
  /// Whether this region should be emitted after its parent is emitted.
48
  bool DeferRegion;
49
50
  /// Whether this region is a gap region. The count from a gap region is set
51
  /// as the line execution count if there are no other regions on the line.
52
  bool GapRegion;
53
54
public:
55
  SourceMappingRegion(Counter Count, Optional<SourceLocation> LocStart,
56
                      Optional<SourceLocation> LocEnd, bool DeferRegion = false,
57
                      bool GapRegion = false)
58
      : Count(Count), LocStart(LocStart), LocEnd(LocEnd),
59
1.34k
        DeferRegion(DeferRegion), GapRegion(GapRegion) {}
60
61
5.29k
  const Counter &getCounter() const { return Count; }
62
63
61
  void setCounter(Counter C) { Count = C; }
64
65
4.41k
  bool hasStartLoc() const { return LocStart.hasValue(); }
66
67
1.07k
  void setStartLoc(SourceLocation Loc) { LocStart = Loc; }
68
69
5.90k
  SourceLocation getBeginLoc() const {
70
5.90k
    assert(LocStart && "Region has no start location");
71
5.90k
    return *LocStart;
72
5.90k
  }
73
74
2.30k
  bool hasEndLoc() const { return LocEnd.hasValue(); }
75
76
1.03k
  void setEndLoc(SourceLocation Loc) {
77
1.03k
    assert(Loc.isValid() && "Setting an invalid end location");
78
1.03k
    LocEnd = Loc;
79
1.03k
  }
80
81
3.06k
  SourceLocation getEndLoc() const {
82
3.06k
    assert(LocEnd && "Region has no end location");
83
3.06k
    return *LocEnd;
84
3.06k
  }
85
86
161
  bool isDeferred() const { return DeferRegion; }
87
88
155
  void setDeferred(bool Deferred) { DeferRegion = Deferred; }
89
90
1.09k
  bool isGap() const { return GapRegion; }
91
92
198
  void setGap(bool Gap) { GapRegion = Gap; }
93
};
94
95
/// Spelling locations for the start and end of a source region.
96
struct SpellingRegion {
97
  /// The line where the region starts.
98
  unsigned LineStart;
99
100
  /// The column where the region starts.
101
  unsigned ColumnStart;
102
103
  /// The line where the region ends.
104
  unsigned LineEnd;
105
106
  /// The column where the region ends.
107
  unsigned ColumnEnd;
108
109
  SpellingRegion(SourceManager &SM, SourceLocation LocStart,
110
2.46k
                 SourceLocation LocEnd) {
111
2.46k
    LineStart = SM.getSpellingLineNumber(LocStart);
112
2.46k
    ColumnStart = SM.getSpellingColumnNumber(LocStart);
113
2.46k
    LineEnd = SM.getSpellingLineNumber(LocEnd);
114
2.46k
    ColumnEnd = SM.getSpellingColumnNumber(LocEnd);
115
2.46k
  }
116
117
  SpellingRegion(SourceManager &SM, SourceMappingRegion &R)
118
1.01k
      : SpellingRegion(SM, R.getBeginLoc(), R.getEndLoc()) {}
119
120
  /// Check if the start and end locations appear in source order, i.e
121
  /// top->bottom, left->right.
122
2.44k
  bool isInSourceOrder() const {
123
2.44k
    return (LineStart < LineEnd) ||
124
2.44k
           
(1.42k
LineStart == LineEnd1.42k
&&
ColumnStart <= ColumnEnd1.41k
);
125
2.44k
  }
126
};
127
128
/// Provides the common functionality for the different
129
/// coverage mapping region builders.
130
class CoverageMappingBuilder {
131
public:
132
  CoverageMappingModuleGen &CVM;
133
  SourceManager &SM;
134
  const LangOptions &LangOpts;
135
136
private:
137
  /// Map of clang's FileIDs to IDs used for coverage mapping.
138
  llvm::SmallDenseMap<FileID, std::pair<unsigned, SourceLocation>, 8>
139
      FileIDMapping;
140
141
public:
142
  /// The coverage mapping regions for this function
143
  llvm::SmallVector<CounterMappingRegion, 32> MappingRegions;
144
  /// The source mapping regions for this function.
145
  std::vector<SourceMappingRegion> SourceRegions;
146
147
  /// A set of regions which can be used as a filter.
148
  ///
149
  /// It is produced by emitExpansionRegions() and is used in
150
  /// emitSourceRegions() to suppress producing code regions if
151
  /// the same area is covered by expansion regions.
152
  typedef llvm::SmallSet<std::pair<SourceLocation, SourceLocation>, 8>
153
      SourceRegionFilter;
154
155
  CoverageMappingBuilder(CoverageMappingModuleGen &CVM, SourceManager &SM,
156
                         const LangOptions &LangOpts)
157
181
      : CVM(CVM), SM(SM), LangOpts(LangOpts) {}
158
159
  /// Return the precise end location for the given token.
160
3.70k
  SourceLocation getPreciseTokenLocEnd(SourceLocation Loc) {
161
3.70k
    // We avoid getLocForEndOfToken here, because it doesn't do what we want for
162
3.70k
    // macro locations, which we just treat as expanded files.
163
3.70k
    unsigned TokLen =
164
3.70k
        Lexer::MeasureTokenLength(SM.getSpellingLoc(Loc), SM, LangOpts);
165
3.70k
    return Loc.getLocWithOffset(TokLen);
166
3.70k
  }
167
168
  /// Return the start location of an included file or expanded macro.
169
1.08k
  SourceLocation getStartOfFileOrMacro(SourceLocation Loc) {
170
1.08k
    if (Loc.isMacroID())
171
234
      return Loc.getLocWithOffset(-SM.getFileOffset(Loc));
172
851
    return SM.getLocForStartOfFile(SM.getFileID(Loc));
173
851
  }
174
175
  /// Return the end location of an included file or expanded macro.
176
225
  SourceLocation getEndOfFileOrMacro(SourceLocation Loc) {
177
225
    if (Loc.isMacroID())
178
167
      return Loc.getLocWithOffset(SM.getFileIDSize(SM.getFileID(Loc)) -
179
167
                                  SM.getFileOffset(Loc));
180
58
    return SM.getLocForEndOfFile(SM.getFileID(Loc));
181
58
  }
182
183
  /// Find out where the current file is included or macro is expanded.
184
4.31k
  SourceLocation getIncludeOrExpansionLoc(SourceLocation Loc) {
185
4.31k
    return Loc.isMacroID() ? 
SM.getImmediateExpansionRange(Loc).getBegin()1.27k
186
4.31k
                           : 
SM.getIncludeLoc(SM.getFileID(Loc))3.04k
;
187
4.31k
  }
188
189
  /// Return true if \c Loc is a location in a built-in macro.
190
7.49k
  bool isInBuiltin(SourceLocation Loc) {
191
7.49k
    return SM.getBufferName(SM.getSpellingLoc(Loc)) == "<built-in>";
192
7.49k
  }
193
194
  /// Check whether \c Loc is included or expanded from \c Parent.
195
679
  bool isNestedIn(SourceLocation Loc, FileID Parent) {
196
810
    do {
197
810
      Loc = getIncludeOrExpansionLoc(Loc);
198
810
      if (Loc.isInvalid())
199
379
        return false;
200
431
    } while (!SM.isInFileID(Loc, Parent));
201
679
    
return true300
;
202
679
  }
203
204
  /// Get the start of \c S ignoring macro arguments and builtin macros.
205
4.22k
  SourceLocation getStart(const Stmt *S) {
206
4.22k
    SourceLocation Loc = S->getBeginLoc();
207
4.46k
    while (SM.isMacroArgExpansion(Loc) || 
isInBuiltin(Loc)4.22k
)
208
245
      Loc = SM.getImmediateExpansionRange(Loc).getBegin();
209
4.22k
    return Loc;
210
4.22k
  }
211
212
  /// Get the end of \c S ignoring macro arguments and builtin macros.
213
3.27k
  SourceLocation getEnd(const Stmt *S) {
214
3.27k
    SourceLocation Loc = S->getEndLoc();
215
3.47k
    while (SM.isMacroArgExpansion(Loc) || 
isInBuiltin(Loc)3.27k
)
216
193
      Loc = SM.getImmediateExpansionRange(Loc).getBegin();
217
3.27k
    return getPreciseTokenLocEnd(Loc);
218
3.27k
  }
219
220
  /// Find the set of files we have regions for and assign IDs
221
  ///
222
  /// Fills \c Mapping with the virtual file mapping needed to write out
223
  /// coverage and collects the necessary file information to emit source and
224
  /// expansion regions.
225
181
  void gatherFileIDs(SmallVectorImpl<unsigned> &Mapping) {
226
181
    FileIDMapping.clear();
227
181
228
181
    llvm::SmallSet<FileID, 8> Visited;
229
181
    SmallVector<std::pair<SourceLocation, unsigned>, 8> FileLocs;
230
1.11k
    for (const auto &Region : SourceRegions) {
231
1.11k
      SourceLocation Loc = Region.getBeginLoc();
232
1.11k
      FileID File = SM.getFileID(Loc);
233
1.11k
      if (!Visited.insert(File).second)
234
787
        continue;
235
331
236
331
      // Do not map FileID's associated with system headers.
237
331
      if (SM.isInSystemHeader(SM.getSpellingLoc(Loc)))
238
3
        continue;
239
328
240
328
      unsigned Depth = 0;
241
328
      for (SourceLocation Parent = getIncludeOrExpansionLoc(Loc);
242
531
           Parent.isValid(); 
Parent = getIncludeOrExpansionLoc(Parent)203
)
243
203
        ++Depth;
244
328
      FileLocs.push_back(std::make_pair(Loc, Depth));
245
328
    }
246
181
    llvm::stable_sort(FileLocs, llvm::less_second());
247
181
248
328
    for (const auto &FL : FileLocs) {
249
328
      SourceLocation Loc = FL.first;
250
328
      FileID SpellingFile = SM.getDecomposedSpellingLoc(Loc).first;
251
328
      auto Entry = SM.getFileEntryForID(SpellingFile);
252
328
      if (!Entry)
253
6
        continue;
254
322
255
322
      FileIDMapping[SM.getFileID(Loc)] = std::make_pair(Mapping.size(), Loc);
256
322
      Mapping.push_back(CVM.getFileID(Entry));
257
322
    }
258
181
  }
259
260
  /// Get the coverage mapping file ID for \c Loc.
261
  ///
262
  /// If such file id doesn't exist, return None.
263
1.41k
  Optional<unsigned> getCoverageFileID(SourceLocation Loc) {
264
1.41k
    auto Mapping = FileIDMapping.find(SM.getFileID(Loc));
265
1.41k
    if (Mapping != FileIDMapping.end())
266
1.40k
      return Mapping->second.first;
267
17
    return None;
268
17
  }
269
270
  /// Gather all the regions that were skipped by the preprocessor
271
  /// using the constructs like #if.
272
164
  void gatherSkippedRegions() {
273
164
    /// An array of the minimum lineStarts and the maximum lineEnds
274
164
    /// for mapping regions from the appropriate source files.
275
164
    llvm::SmallVector<std::pair<unsigned, unsigned>, 8> FileLineRanges;
276
164
    FileLineRanges.resize(
277
164
        FileIDMapping.size(),
278
164
        std::make_pair(std::numeric_limits<unsigned>::max(), 0));
279
1.22k
    for (const auto &R : MappingRegions) {
280
1.22k
      FileLineRanges[R.FileID].first =
281
1.22k
          std::min(FileLineRanges[R.FileID].first, R.LineStart);
282
1.22k
      FileLineRanges[R.FileID].second =
283
1.22k
          std::max(FileLineRanges[R.FileID].second, R.LineEnd);
284
1.22k
    }
285
164
286
164
    auto SkippedRanges = CVM.getSourceInfo().getSkippedRanges();
287
164
    for (const auto &I : SkippedRanges) {
288
18
      auto LocStart = I.getBegin();
289
18
      auto LocEnd = I.getEnd();
290
18
      assert(SM.isWrittenInSameFile(LocStart, LocEnd) &&
291
18
             "region spans multiple files");
292
18
293
18
      auto CovFileID = getCoverageFileID(LocStart);
294
18
      if (!CovFileID)
295
5
        continue;
296
13
      SpellingRegion SR{SM, LocStart, LocEnd};
297
13
      auto Region = CounterMappingRegion::makeSkipped(
298
13
          *CovFileID, SR.LineStart, SR.ColumnStart, SR.LineEnd, SR.ColumnEnd);
299
13
      // Make sure that we only collect the regions that are inside
300
13
      // the source code of this function.
301
13
      if (Region.LineStart >= FileLineRanges[*CovFileID].first &&
302
13
          
Region.LineEnd <= FileLineRanges[*CovFileID].second9
)
303
9
        MappingRegions.push_back(Region);
304
13
    }
305
164
  }
306
307
  /// Generate the coverage counter mapping regions from collected
308
  /// source regions.
309
181
  void emitSourceRegions(const SourceRegionFilter &Filter) {
310
1.11k
    for (const auto &Region : SourceRegions) {
311
1.11k
      assert(Region.hasEndLoc() && "incomplete region");
312
1.11k
313
1.11k
      SourceLocation LocStart = Region.getBeginLoc();
314
1.11k
      assert(SM.getFileID(LocStart).isValid() && "region in invalid file");
315
1.11k
316
1.11k
      // Ignore regions from system headers.
317
1.11k
      if (SM.isInSystemHeader(SM.getSpellingLoc(LocStart)))
318
7
        continue;
319
1.11k
320
1.11k
      auto CovFileID = getCoverageFileID(LocStart);
321
1.11k
      // Ignore regions that don't have a file, such as builtin macros.
322
1.11k
      if (!CovFileID)
323
7
        continue;
324
1.10k
325
1.10k
      SourceLocation LocEnd = Region.getEndLoc();
326
1.10k
      assert(SM.isWrittenInSameFile(LocStart, LocEnd) &&
327
1.10k
             "region spans multiple files");
328
1.10k
329
1.10k
      // Don't add code regions for the area covered by expansion regions.
330
1.10k
      // This not only suppresses redundant regions, but sometimes prevents
331
1.10k
      // creating regions with wrong counters if, for example, a statement's
332
1.10k
      // body ends at the end of a nested macro.
333
1.10k
      if (Filter.count(std::make_pair(LocStart, LocEnd)))
334
8
        continue;
335
1.09k
336
1.09k
      // Find the spelling locations for the mapping region.
337
1.09k
      SpellingRegion SR{SM, LocStart, LocEnd};
338
1.09k
      assert(SR.isInSourceOrder() && "region start and end out of order");
339
1.09k
340
1.09k
      if (Region.isGap()) {
341
198
        MappingRegions.push_back(CounterMappingRegion::makeGapRegion(
342
198
            Region.getCounter(), *CovFileID, SR.LineStart, SR.ColumnStart,
343
198
            SR.LineEnd, SR.ColumnEnd));
344
898
      } else {
345
898
        MappingRegions.push_back(CounterMappingRegion::makeRegion(
346
898
            Region.getCounter(), *CovFileID, SR.LineStart, SR.ColumnStart,
347
898
            SR.LineEnd, SR.ColumnEnd));
348
898
      }
349
1.09k
    }
350
181
  }
351
352
  /// Generate expansion regions for each virtual file we've seen.
353
164
  SourceRegionFilter emitExpansionRegions() {
354
164
    SourceRegionFilter Filter;
355
305
    for (const auto &FM : FileIDMapping) {
356
305
      SourceLocation ExpandedLoc = FM.second.second;
357
305
      SourceLocation ParentLoc = getIncludeOrExpansionLoc(ExpandedLoc);
358
305
      if (ParentLoc.isInvalid())
359
158
        continue;
360
147
361
147
      auto ParentFileID = getCoverageFileID(ParentLoc);
362
147
      if (!ParentFileID)
363
5
        continue;
364
142
      auto ExpandedFileID = getCoverageFileID(ExpandedLoc);
365
142
      assert(ExpandedFileID && "expansion in uncovered file");
366
142
367
142
      SourceLocation LocEnd = getPreciseTokenLocEnd(ParentLoc);
368
142
      assert(SM.isWrittenInSameFile(ParentLoc, LocEnd) &&
369
142
             "region spans multiple files");
370
142
      Filter.insert(std::make_pair(ParentLoc, LocEnd));
371
142
372
142
      SpellingRegion SR{SM, ParentLoc, LocEnd};
373
142
      assert(SR.isInSourceOrder() && "region start and end out of order");
374
142
      MappingRegions.push_back(CounterMappingRegion::makeExpansion(
375
142
          *ParentFileID, *ExpandedFileID, SR.LineStart, SR.ColumnStart,
376
142
          SR.LineEnd, SR.ColumnEnd));
377
142
    }
378
164
    return Filter;
379
164
  }
380
};
381
382
/// Creates unreachable coverage regions for the functions that
383
/// are not emitted.
384
struct EmptyCoverageMappingBuilder : public CoverageMappingBuilder {
385
  EmptyCoverageMappingBuilder(CoverageMappingModuleGen &CVM, SourceManager &SM,
386
                              const LangOptions &LangOpts)
387
17
      : CoverageMappingBuilder(CVM, SM, LangOpts) {}
388
389
17
  void VisitDecl(const Decl *D) {
390
17
    if (!D->hasBody())
391
0
      return;
392
17
    auto Body = D->getBody();
393
17
    SourceLocation Start = getStart(Body);
394
17
    SourceLocation End = getEnd(Body);
395
17
    if (!SM.isWrittenInSameFile(Start, End)) {
396
6
      // Walk up to find the common ancestor.
397
6
      // Correct the locations accordingly.
398
6
      FileID StartFileID = SM.getFileID(Start);
399
6
      FileID EndFileID = SM.getFileID(End);
400
10
      while (StartFileID != EndFileID && 
!isNestedIn(End, StartFileID)8
) {
401
4
        Start = getIncludeOrExpansionLoc(Start);
402
4
        assert(Start.isValid() &&
403
4
               "Declaration start location not nested within a known region");
404
4
        StartFileID = SM.getFileID(Start);
405
4
      }
406
10
      while (StartFileID != EndFileID) {
407
4
        End = getPreciseTokenLocEnd(getIncludeOrExpansionLoc(End));
408
4
        assert(End.isValid() &&
409
4
               "Declaration end location not nested within a known region");
410
4
        EndFileID = SM.getFileID(End);
411
4
      }
412
6
    }
413
17
    SourceRegions.emplace_back(Counter(), Start, End);
414
17
  }
415
416
  /// Write the mapping data to the output stream
417
17
  void write(llvm::raw_ostream &OS) {
418
17
    SmallVector<unsigned, 16> FileIDMapping;
419
17
    gatherFileIDs(FileIDMapping);
420
17
    emitSourceRegions(SourceRegionFilter());
421
17
422
17
    if (MappingRegions.empty())
423
0
      return;
424
17
425
17
    CoverageMappingWriter Writer(FileIDMapping, None, MappingRegions);
426
17
    Writer.write(OS);
427
17
  }
428
};
429
430
/// A StmtVisitor that creates coverage mapping regions which map
431
/// from the source code locations to the PGO counters.
432
struct CounterCoverageMappingBuilder
433
    : public CoverageMappingBuilder,
434
      public ConstStmtVisitor<CounterCoverageMappingBuilder> {
435
  /// The map of statements to count values.
436
  llvm::DenseMap<const Stmt *, unsigned> &CounterMap;
437
438
  /// A stack of currently live regions.
439
  std::vector<SourceMappingRegion> RegionStack;
440
441
  /// The currently deferred region: its end location and count can be set once
442
  /// its parent has been popped from the region stack.
443
  Optional<SourceMappingRegion> DeferredRegion;
444
445
  CounterExpressionBuilder Builder;
446
447
  /// A location in the most recently visited file or macro.
448
  ///
449
  /// This is used to adjust the active source regions appropriately when
450
  /// expressions cross file or macro boundaries.
451
  SourceLocation MostRecentLocation;
452
453
  /// Location of the last terminated region.
454
  Optional<std::pair<SourceLocation, size_t>> LastTerminatedRegion;
455
456
  /// Return a counter for the subtraction of \c RHS from \c LHS
457
195
  Counter subtractCounters(Counter LHS, Counter RHS) {
458
195
    return Builder.subtract(LHS, RHS);
459
195
  }
460
461
  /// Return a counter for the sum of \c LHS and \c RHS.
462
461
  Counter addCounters(Counter LHS, Counter RHS) {
463
461
    return Builder.add(LHS, RHS);
464
461
  }
465
466
91
  Counter addCounters(Counter C1, Counter C2, Counter C3) {
467
91
    return addCounters(addCounters(C1, C2), C3);
468
91
  }
469
470
  /// Return the region counter for the given statement.
471
  ///
472
  /// This should only be called on statements that have a dedicated counter.
473
446
  Counter getRegionCounter(const Stmt *S) {
474
446
    return Counter::getCounter(CounterMap[S]);
475
446
  }
476
477
  /// Push a region onto the stack.
478
  ///
479
  /// Returns the index on the stack where the region was pushed. This can be
480
  /// used with popRegions to exit a "scope", ending the region that was pushed.
481
  size_t pushRegion(Counter Count, Optional<SourceLocation> StartLoc = None,
482
1.04k
                    Optional<SourceLocation> EndLoc = None) {
483
1.04k
    if (StartLoc) {
484
802
      MostRecentLocation = *StartLoc;
485
802
      completeDeferred(Count, MostRecentLocation);
486
802
    }
487
1.04k
    RegionStack.emplace_back(Count, StartLoc, EndLoc);
488
1.04k
489
1.04k
    return RegionStack.size() - 1;
490
1.04k
  }
491
492
  /// Complete any pending deferred region by setting its end location and
493
  /// count, and then pushing it onto the region stack.
494
3.93k
  size_t completeDeferred(Counter Count, SourceLocation DeferredEndLoc) {
495
3.93k
    size_t Index = RegionStack.size();
496
3.93k
    if (!DeferredRegion)
497
3.87k
      return Index;
498
55
499
55
    // Consume the pending region.
500
55
    SourceMappingRegion DR = DeferredRegion.getValue();
501
55
    DeferredRegion = None;
502
55
503
55
    // If the region ends in an expansion, find the expansion site.
504
55
    FileID StartFile = SM.getFileID(DR.getBeginLoc());
505
55
    if (SM.getFileID(DeferredEndLoc) != StartFile) {
506
4
      if (isNestedIn(DeferredEndLoc, StartFile)) {
507
4
        do {
508
4
          DeferredEndLoc = getIncludeOrExpansionLoc(DeferredEndLoc);
509
4
        } while (StartFile != SM.getFileID(DeferredEndLoc));
510
4
      } else {
511
0
        return Index;
512
0
      }
513
55
    }
514
55
515
55
    // The parent of this deferred region ends where the containing decl ends,
516
55
    // so the region isn't useful.
517
55
    if (DR.getBeginLoc() == DeferredEndLoc)
518
1
      return Index;
519
54
520
54
    // If we're visiting statements in non-source order (e.g switch cases or
521
54
    // a loop condition) we can't construct a sensible deferred region.
522
54
    if (!SpellingRegion(SM, DR.getBeginLoc(), DeferredEndLoc).isInSourceOrder())
523
6
      return Index;
524
48
525
48
    DR.setGap(true);
526
48
    DR.setCounter(Count);
527
48
    DR.setEndLoc(DeferredEndLoc);
528
48
    handleFileExit(DeferredEndLoc);
529
48
    RegionStack.push_back(DR);
530
48
    return Index;
531
48
  }
532
533
  /// Complete a deferred region created after a terminated region at the
534
  /// top-level.
535
  void completeTopLevelDeferredRegion(Counter Count,
536
14
                                      SourceLocation DeferredEndLoc) {
537
14
    if (DeferredRegion || 
!LastTerminatedRegion12
)
538
6
      return;
539
8
540
8
    if (LastTerminatedRegion->second != RegionStack.size())
541
4
      return;
542
4
543
4
    SourceLocation Start = LastTerminatedRegion->first;
544
4
    if (SM.getFileID(Start) != SM.getMainFileID())
545
0
      return;
546
4
547
4
    SourceMappingRegion DR = RegionStack.back();
548
4
    DR.setStartLoc(Start);
549
4
    DR.setDeferred(false);
550
4
    DeferredRegion = DR;
551
4
    completeDeferred(Count, DeferredEndLoc);
552
4
  }
553
554
1.86k
  size_t locationDepth(SourceLocation Loc) {
555
1.86k
    size_t Depth = 0;
556
4.12k
    while (Loc.isValid()) {
557
2.26k
      Loc = getIncludeOrExpansionLoc(Loc);
558
2.26k
      Depth++;
559
2.26k
    }
560
1.86k
    return Depth;
561
1.86k
  }
562
563
  /// Pop regions from the stack into the function's list of regions.
564
  ///
565
  /// Adds all regions from \c ParentIndex to the top of the stack to the
566
  /// function's \c SourceRegions.
567
769
  void popRegions(size_t ParentIndex) {
568
769
    assert(RegionStack.size() >= ParentIndex && "parent not in stack");
569
769
    bool ParentOfDeferredRegion = false;
570
1.86k
    while (RegionStack.size() > ParentIndex) {
571
1.09k
      SourceMappingRegion &Region = RegionStack.back();
572
1.09k
      if (Region.hasStartLoc()) {
573
931
        SourceLocation StartLoc = Region.getBeginLoc();
574
931
        SourceLocation EndLoc = Region.hasEndLoc()
575
931
                                    ? 
Region.getEndLoc()855
576
931
                                    : 
RegionStack[ParentIndex].getEndLoc()76
;
577
931
        size_t StartDepth = locationDepth(StartLoc);
578
931
        size_t EndDepth = locationDepth(EndLoc);
579
958
        while (!SM.isWrittenInSameFile(StartLoc, EndLoc)) {
580
27
          bool UnnestStart = StartDepth >= EndDepth;
581
27
          bool UnnestEnd = EndDepth >= StartDepth;
582
27
          if (UnnestEnd) {
583
26
            // The region ends in a nested file or macro expansion. Create a
584
26
            // separate region for each expansion.
585
26
            SourceLocation NestedLoc = getStartOfFileOrMacro(EndLoc);
586
26
            assert(SM.isWrittenInSameFile(NestedLoc, EndLoc));
587
26
588
26
            if (!isRegionAlreadyAdded(NestedLoc, EndLoc))
589
24
              SourceRegions.emplace_back(Region.getCounter(), NestedLoc, EndLoc);
590
26
591
26
            EndLoc = getPreciseTokenLocEnd(getIncludeOrExpansionLoc(EndLoc));
592
26
            if (EndLoc.isInvalid())
593
0
              llvm::report_fatal_error("File exit not handled before popRegions");
594
26
            EndDepth--;
595
26
          }
596
27
          if (UnnestStart) {
597
1
            // The region begins in a nested file or macro expansion. Create a
598
1
            // separate region for each expansion.
599
1
            SourceLocation NestedLoc = getEndOfFileOrMacro(StartLoc);
600
1
            assert(SM.isWrittenInSameFile(StartLoc, NestedLoc));
601
1
602
1
            if (!isRegionAlreadyAdded(StartLoc, NestedLoc))
603
1
              SourceRegions.emplace_back(Region.getCounter(), StartLoc, NestedLoc);
604
1
605
1
            StartLoc = getIncludeOrExpansionLoc(StartLoc);
606
1
            if (StartLoc.isInvalid())
607
0
              llvm::report_fatal_error("File exit not handled before popRegions");
608
1
            StartDepth--;
609
1
          }
610
27
        }
611
931
        Region.setStartLoc(StartLoc);
612
931
        Region.setEndLoc(EndLoc);
613
931
614
931
        MostRecentLocation = EndLoc;
615
931
        // If this region happens to span an entire expansion, we need to make
616
931
        // sure we don't overlap the parent region with it.
617
931
        if (StartLoc == getStartOfFileOrMacro(StartLoc) &&
618
931
            
EndLoc == getEndOfFileOrMacro(EndLoc)34
)
619
34
          MostRecentLocation = getIncludeOrExpansionLoc(EndLoc);
620
931
621
931
        assert(SM.isWrittenInSameFile(Region.getBeginLoc(), EndLoc));
622
931
        assert(SpellingRegion(SM, Region).isInSourceOrder());
623
931
        SourceRegions.push_back(Region);
624
931
625
931
        if (ParentOfDeferredRegion) {
626
123
          ParentOfDeferredRegion = false;
627
123
628
123
          // If there's an existing deferred region, keep the old one, because
629
123
          // it means there are two consecutive returns (or a similar pattern).
630
123
          if (!DeferredRegion.hasValue() &&
631
123
              // File IDs aren't gathered within macro expansions, so it isn't
632
123
              // useful to try and create a deferred region inside of one.
633
123
              
!EndLoc.isMacroID()122
)
634
115
            DeferredRegion =
635
115
                SourceMappingRegion(Counter::getZero(), EndLoc, None);
636
123
        }
637
931
      } else 
if (161
Region.isDeferred()161
) {
638
123
        assert(!ParentOfDeferredRegion && "Consecutive deferred regions");
639
123
        ParentOfDeferredRegion = true;
640
123
      }
641
1.09k
      RegionStack.pop_back();
642
1.09k
643
1.09k
      // If the zero region pushed after the last terminated region no longer
644
1.09k
      // exists, clear its cached information.
645
1.09k
      if (LastTerminatedRegion &&
646
1.09k
          
RegionStack.size() < LastTerminatedRegion->second150
)
647
138
        LastTerminatedRegion = None;
648
1.09k
    }
649
769
    assert(!ParentOfDeferredRegion && "Deferred region with no parent");
650
769
  }
651
652
  /// Return the currently active region.
653
4.49k
  SourceMappingRegion &getRegion() {
654
4.49k
    assert(!RegionStack.empty() && "statement has no region");
655
4.49k
    return RegionStack.back();
656
4.49k
  }
657
658
  /// Propagate counts through the children of \p S if \p VisitChildren is true.
659
  /// Otherwise, only emit a count for \p S itself.
660
  Counter propagateCounts(Counter TopCount, const Stmt *S,
661
619
                          bool VisitChildren = true) {
662
619
    SourceLocation StartLoc = getStart(S);
663
619
    SourceLocation EndLoc = getEnd(S);
664
619
    size_t Index = pushRegion(TopCount, StartLoc, EndLoc);
665
619
    if (VisitChildren)
666
609
      Visit(S);
667
619
    Counter ExitCount = getRegion().getCounter();
668
619
    popRegions(Index);
669
619
670
619
    // The statement may be spanned by an expansion. Make sure we handle a file
671
619
    // exit out of this expansion before moving to the next statement.
672
619
    if (SM.isBeforeInTranslationUnit(StartLoc, S->getBeginLoc()))
673
35
      MostRecentLocation = EndLoc;
674
619
675
619
    return ExitCount;
676
619
  }
677
678
  /// Check whether a region with bounds \c StartLoc and \c EndLoc
679
  /// is already added to \c SourceRegions.
680
35
  bool isRegionAlreadyAdded(SourceLocation StartLoc, SourceLocation EndLoc) {
681
35
    return SourceRegions.rend() !=
682
35
           std::find_if(SourceRegions.rbegin(), SourceRegions.rend(),
683
427
                        [&](const SourceMappingRegion &Region) {
684
427
                          return Region.getBeginLoc() == StartLoc &&
685
427
                                 
Region.getEndLoc() == EndLoc13
;
686
427
                        });
687
35
  }
688
689
  /// Adjust the most recently visited location to \c EndLoc.
690
  ///
691
  /// This should be used after visiting any statements in non-source order.
692
46
  void adjustForOutOfOrderTraversal(SourceLocation EndLoc) {
693
46
    MostRecentLocation = EndLoc;
694
46
    // The code region for a whole macro is created in handleFileExit() when
695
46
    // it detects exiting of the virtual file of that macro. If we visited
696
46
    // statements in non-source order, we might already have such a region
697
46
    // added, for example, if a body of a loop is divided among multiple
698
46
    // macros. Avoid adding duplicate regions in such case.
699
46
    if (getRegion().hasEndLoc() &&
700
46
        
MostRecentLocation == getEndOfFileOrMacro(MostRecentLocation)45
&&
701
46
        isRegionAlreadyAdded(getStartOfFileOrMacro(MostRecentLocation),
702
8
                             MostRecentLocation))
703
6
      MostRecentLocation = getIncludeOrExpansionLoc(MostRecentLocation);
704
46
  }
705
706
  /// Adjust regions and state when \c NewLoc exits a file.
707
  ///
708
  /// If moving from our most recently tracked location to \c NewLoc exits any
709
  /// files, this adjusts our current region stack and creates the file regions
710
  /// for the exited file.
711
5.69k
  void handleFileExit(SourceLocation NewLoc) {
712
5.69k
    if (NewLoc.isInvalid() ||
713
5.69k
        
SM.isWrittenInSameFile(MostRecentLocation, NewLoc)5.68k
)
714
5.47k
      return;
715
220
716
220
    // If NewLoc is not in a file that contains MostRecentLocation, walk up to
717
220
    // find the common ancestor.
718
220
    SourceLocation LCA = NewLoc;
719
220
    FileID ParentFile = SM.getFileID(LCA);
720
267
    while (!isNestedIn(MostRecentLocation, ParentFile)) {
721
149
      LCA = getIncludeOrExpansionLoc(LCA);
722
149
      if (LCA.isInvalid() || SM.isWrittenInSameFile(LCA, MostRecentLocation)) {
723
102
        // Since there isn't a common ancestor, no file was exited. We just need
724
102
        // to adjust our location to the new file.
725
102
        MostRecentLocation = NewLoc;
726
102
        return;
727
102
      }
728
47
      ParentFile = SM.getFileID(LCA);
729
47
    }
730
220
731
220
    llvm::SmallSet<SourceLocation, 8> StartLocs;
732
118
    Optional<Counter> ParentCounter;
733
177
    for (SourceMappingRegion &I : llvm::reverse(RegionStack)) {
734
177
      if (!I.hasStartLoc())
735
10
        continue;
736
167
      SourceLocation Loc = I.getBeginLoc();
737
167
      if (!isNestedIn(Loc, ParentFile)) {
738
113
        ParentCounter = I.getCounter();
739
113
        break;
740
113
      }
741
54
742
114
      
while (54
!SM.isInFileID(Loc, ParentFile)) {
743
60
        // The most nested region for each start location is the one with the
744
60
        // correct count. We avoid creating redundant regions by stopping once
745
60
        // we've seen this region.
746
60
        if (StartLocs.insert(Loc).second)
747
57
          SourceRegions.emplace_back(I.getCounter(), Loc,
748
57
                                     getEndOfFileOrMacro(Loc));
749
60
        Loc = getIncludeOrExpansionLoc(Loc);
750
60
      }
751
54
      I.setStartLoc(getPreciseTokenLocEnd(Loc));
752
54
    }
753
118
754
118
    if (ParentCounter) {
755
113
      // If the file is contained completely by another region and doesn't
756
113
      // immediately start its own region, the whole file gets a region
757
113
      // corresponding to the parent.
758
113
      SourceLocation Loc = MostRecentLocation;
759
233
      while (isNestedIn(Loc, ParentFile)) {
760
120
        SourceLocation FileStart = getStartOfFileOrMacro(Loc);
761
120
        if (StartLocs.insert(FileStart).second) {
762
88
          SourceRegions.emplace_back(*ParentCounter, FileStart,
763
88
                                     getEndOfFileOrMacro(Loc));
764
88
          assert(SpellingRegion(SM, SourceRegions.back()).isInSourceOrder());
765
88
        }
766
120
        Loc = getIncludeOrExpansionLoc(Loc);
767
120
      }
768
113
    }
769
118
770
118
    MostRecentLocation = NewLoc;
771
118
  }
772
773
  /// Ensure that \c S is included in the current region.
774
3.11k
  void extendRegion(const Stmt *S) {
775
3.11k
    SourceMappingRegion &Region = getRegion();
776
3.11k
    SourceLocation StartLoc = getStart(S);
777
3.11k
778
3.11k
    handleFileExit(StartLoc);
779
3.11k
    if (!Region.hasStartLoc())
780
81
      Region.setStartLoc(StartLoc);
781
3.11k
782
3.11k
    completeDeferred(Region.getCounter(), StartLoc);
783
3.11k
  }
784
785
  /// Mark \c S as a terminator, starting a zero region.
786
151
  void terminateRegion(const Stmt *S) {
787
151
    extendRegion(S);
788
151
    SourceMappingRegion &Region = getRegion();
789
151
    SourceLocation EndLoc = getEnd(S);
790
151
    if (!Region.hasEndLoc())
791
25
      Region.setEndLoc(EndLoc);
792
151
    pushRegion(Counter::getZero());
793
151
    auto &ZeroRegion = getRegion();
794
151
    ZeroRegion.setDeferred(true);
795
151
    LastTerminatedRegion = {EndLoc, RegionStack.size()};
796
151
  }
797
798
  /// Find a valid gap range between \p AfterLoc and \p BeforeLoc.
799
  Optional<SourceRange> findGapAreaBetween(SourceLocation AfterLoc,
800
213
                                           SourceLocation BeforeLoc) {
801
213
    // If the start and end locations of the gap are both within the same macro
802
213
    // file, the range may not be in source order.
803
213
    if (AfterLoc.isMacroID() || 
BeforeLoc.isMacroID()162
)
804
71
      return None;
805
142
    if (!SM.isWrittenInSameFile(AfterLoc, BeforeLoc))
806
0
      return None;
807
142
    return {{AfterLoc, BeforeLoc}};
808
142
  }
809
810
  /// Find the source range after \p AfterStmt and before \p BeforeStmt.
811
  Optional<SourceRange> findGapAreaBetween(const Stmt *AfterStmt,
812
170
                                           const Stmt *BeforeStmt) {
813
170
    return findGapAreaBetween(getPreciseTokenLocEnd(getEnd(AfterStmt)),
814
170
                              getStart(BeforeStmt));
815
170
  }
816
817
  /// Emit a gap region between \p StartLoc and \p EndLoc with the given count.
818
  void fillGapAreaWithCount(SourceLocation StartLoc, SourceLocation EndLoc,
819
142
                            Counter Count) {
820
142
    if (StartLoc == EndLoc)
821
4
      return;
822
138
    assert(SpellingRegion(SM, StartLoc, EndLoc).isInSourceOrder());
823
138
    handleFileExit(StartLoc);
824
138
    size_t Index = pushRegion(Count, StartLoc, EndLoc);
825
138
    getRegion().setGap(true);
826
138
    handleFileExit(EndLoc);
827
138
    popRegions(Index);
828
138
  }
829
830
  /// Keep counts of breaks and continues inside loops.
831
  struct BreakContinue {
832
    Counter BreakCount;
833
    Counter ContinueCount;
834
  };
835
  SmallVector<BreakContinue, 8> BreakContinueStack;
836
837
  CounterCoverageMappingBuilder(
838
      CoverageMappingModuleGen &CVM,
839
      llvm::DenseMap<const Stmt *, unsigned> &CounterMap, SourceManager &SM,
840
      const LangOptions &LangOpts)
841
      : CoverageMappingBuilder(CVM, SM, LangOpts), CounterMap(CounterMap),
842
164
        DeferredRegion(None) {}
843
844
  /// Write the mapping data to the output stream
845
164
  void write(llvm::raw_ostream &OS) {
846
164
    llvm::SmallVector<unsigned, 8> VirtualFileMapping;
847
164
    gatherFileIDs(VirtualFileMapping);
848
164
    SourceRegionFilter Filter = emitExpansionRegions();
849
164
    assert(!DeferredRegion && "Deferred region never completed");
850
164
    emitSourceRegions(Filter);
851
164
    gatherSkippedRegions();
852
164
853
164
    if (MappingRegions.empty())
854
1
      return;
855
163
856
163
    CoverageMappingWriter Writer(VirtualFileMapping, Builder.getExpressions(),
857
163
                                 MappingRegions);
858
163
    Writer.write(OS);
859
163
  }
860
861
2.21k
  void VisitStmt(const Stmt *S) {
862
2.21k
    if (S->getBeginLoc().isValid())
863
2.21k
      extendRegion(S);
864
2.21k
    for (const Stmt *Child : S->children())
865
1.80k
      if (Child)
866
1.80k
        this->Visit(Child);
867
2.21k
    handleFileExit(getEnd(S));
868
2.21k
  }
869
870
164
  void VisitDecl(const Decl *D) {
871
164
    assert(!DeferredRegion && "Deferred region never completed");
872
164
873
164
    Stmt *Body = D->getBody();
874
164
875
164
    // Do not propagate region counts into system headers.
876
164
    if (Body && SM.isInSystemHeader(SM.getSpellingLoc(getStart(Body))))
877
1
      return;
878
163
879
163
    // Do not visit the artificial children nodes of defaulted methods. The
880
163
    // lexer may not be able to report back precise token end locations for
881
163
    // these children nodes (llvm.org/PR39822), and moreover users will not be
882
163
    // able to see coverage for them.
883
163
    bool Defaulted = false;
884
163
    if (auto *Method = dyn_cast<CXXMethodDecl>(D))
885
25
      Defaulted = Method->isDefaulted();
886
163
887
163
    propagateCounts(getRegionCounter(Body), Body,
888
163
                    /*VisitChildren=*/!Defaulted);
889
163
    assert(RegionStack.empty() && "Regions entered but never exited");
890
163
891
163
    // Discard the last uncompleted deferred region in a decl, if one exists.
892
163
    // This prevents lines at the end of a function containing only whitespace
893
163
    // or closing braces from being marked as uncovered.
894
163
    DeferredRegion = None;
895
163
  }
896
897
108
  void VisitReturnStmt(const ReturnStmt *S) {
898
108
    extendRegion(S);
899
108
    if (S->getRetValue())
900
61
      Visit(S->getRetValue());
901
108
    terminateRegion(S);
902
108
  }
903
904
3
  void VisitCXXThrowExpr(const CXXThrowExpr *E) {
905
3
    extendRegion(E);
906
3
    if (E->getSubExpr())
907
3
      Visit(E->getSubExpr());
908
3
    terminateRegion(E);
909
3
  }
910
911
11
  void VisitGotoStmt(const GotoStmt *S) { terminateRegion(S); }
912
913
14
  void VisitLabelStmt(const LabelStmt *S) {
914
14
    Counter LabelCount = getRegionCounter(S);
915
14
    SourceLocation Start = getStart(S);
916
14
    completeTopLevelDeferredRegion(LabelCount, Start);
917
14
    completeDeferred(LabelCount, Start);
918
14
    // We can't extendRegion here or we risk overlapping with our new region.
919
14
    handleFileExit(Start);
920
14
    pushRegion(LabelCount, Start);
921
14
    Visit(S->getSubStmt());
922
14
  }
923
924
20
  void VisitBreakStmt(const BreakStmt *S) {
925
20
    assert(!BreakContinueStack.empty() && "break not in a loop or switch!");
926
20
    BreakContinueStack.back().BreakCount = addCounters(
927
20
        BreakContinueStack.back().BreakCount, getRegion().getCounter());
928
20
    // FIXME: a break in a switch should terminate regions for all preceding
929
20
    // case statements, not just the most recent one.
930
20
    terminateRegion(S);
931
20
  }
932
933
6
  void VisitContinueStmt(const ContinueStmt *S) {
934
6
    assert(!BreakContinueStack.empty() && "continue stmt not in a loop!");
935
6
    BreakContinueStack.back().ContinueCount = addCounters(
936
6
        BreakContinueStack.back().ContinueCount, getRegion().getCounter());
937
6
    terminateRegion(S);
938
6
  }
939
940
98
  void VisitCallExpr(const CallExpr *E) {
941
98
    VisitStmt(E);
942
98
943
98
    // Terminate the region when we hit a noreturn function.
944
98
    // (This is helpful dealing with switch statements.)
945
98
    QualType CalleeType = E->getCallee()->getType();
946
98
    if (getFunctionExtInfo(*CalleeType).getNoReturn())
947
3
      terminateRegion(E);
948
98
  }
949
950
28
  void VisitWhileStmt(const WhileStmt *S) {
951
28
    extendRegion(S);
952
28
953
28
    Counter ParentCount = getRegion().getCounter();
954
28
    Counter BodyCount = getRegionCounter(S);
955
28
956
28
    // Handle the body first so that we can get the backedge count.
957
28
    BreakContinueStack.push_back(BreakContinue());
958
28
    extendRegion(S->getBody());
959
28
    Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
960
28
    BreakContinue BC = BreakContinueStack.pop_back_val();
961
28
962
28
    // Go back to handle the condition.
963
28
    Counter CondCount =
964
28
        addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
965
28
    propagateCounts(CondCount, S->getCond());
966
28
    adjustForOutOfOrderTraversal(getEnd(S));
967
28
968
28
    // The body count applies to the area immediately after the increment.
969
28
    auto Gap = findGapAreaBetween(S->getCond(), S->getBody());
970
28
    if (Gap)
971
15
      fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
972
28
973
28
    Counter OutCount =
974
28
        addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount));
975
28
    if (OutCount != ParentCount)
976
3
      pushRegion(OutCount);
977
28
  }
978
979
9
  void VisitDoStmt(const DoStmt *S) {
980
9
    extendRegion(S);
981
9
982
9
    Counter ParentCount = getRegion().getCounter();
983
9
    Counter BodyCount = getRegionCounter(S);
984
9
985
9
    BreakContinueStack.push_back(BreakContinue());
986
9
    extendRegion(S->getBody());
987
9
    Counter BackedgeCount =
988
9
        propagateCounts(addCounters(ParentCount, BodyCount), S->getBody());
989
9
    BreakContinue BC = BreakContinueStack.pop_back_val();
990
9
991
9
    Counter CondCount = addCounters(BackedgeCount, BC.ContinueCount);
992
9
    propagateCounts(CondCount, S->getCond());
993
9
994
9
    Counter OutCount =
995
9
        addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount));
996
9
    if (OutCount != ParentCount)
997
0
      pushRegion(OutCount);
998
9
  }
999
1000
30
  void VisitForStmt(const ForStmt *S) {
1001
30
    extendRegion(S);
1002
30
    if (S->getInit())
1003
17
      Visit(S->getInit());
1004
30
1005
30
    Counter ParentCount = getRegion().getCounter();
1006
30
    Counter BodyCount = getRegionCounter(S);
1007
30
1008
30
    // The loop increment may contain a break or continue.
1009
30
    if (S->getInc())
1010
18
      BreakContinueStack.emplace_back();
1011
30
1012
30
    // Handle the body first so that we can get the backedge count.
1013
30
    BreakContinueStack.emplace_back();
1014
30
    extendRegion(S->getBody());
1015
30
    Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
1016
30
    BreakContinue BodyBC = BreakContinueStack.pop_back_val();
1017
30
1018
30
    // The increment is essentially part of the body but it needs to include
1019
30
    // the count for all the continue statements.
1020
30
    BreakContinue IncrementBC;
1021
30
    if (const Stmt *Inc = S->getInc()) {
1022
18
      propagateCounts(addCounters(BackedgeCount, BodyBC.ContinueCount), Inc);
1023
18
      IncrementBC = BreakContinueStack.pop_back_val();
1024
18
    }
1025
30
1026
30
    // Go back to handle the condition.
1027
30
    Counter CondCount = addCounters(
1028
30
        addCounters(ParentCount, BackedgeCount, BodyBC.ContinueCount),
1029
30
        IncrementBC.ContinueCount);
1030
30
    if (const Expr *Cond = S->getCond()) {
1031
18
      propagateCounts(CondCount, Cond);
1032
18
      adjustForOutOfOrderTraversal(getEnd(S));
1033
18
    }
1034
30
1035
30
    // The body count applies to the area immediately after the increment.
1036
30
    auto Gap = findGapAreaBetween(getPreciseTokenLocEnd(S->getRParenLoc()),
1037
30
                                  getStart(S->getBody()));
1038
30
    if (Gap)
1039
18
      fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
1040
30
1041
30
    Counter OutCount = addCounters(BodyBC.BreakCount, IncrementBC.BreakCount,
1042
30
                                   subtractCounters(CondCount, BodyCount));
1043
30
    if (OutCount != ParentCount)
1044
8
      pushRegion(OutCount);
1045
30
  }
1046
1047
2
  void VisitCXXForRangeStmt(const CXXForRangeStmt *S) {
1048
2
    extendRegion(S);
1049
2
    if (S->getInit())
1050
0
      Visit(S->getInit());
1051
2
    Visit(S->getLoopVarStmt());
1052
2
    Visit(S->getRangeStmt());
1053
2
1054
2
    Counter ParentCount = getRegion().getCounter();
1055
2
    Counter BodyCount = getRegionCounter(S);
1056
2
1057
2
    BreakContinueStack.push_back(BreakContinue());
1058
2
    extendRegion(S->getBody());
1059
2
    Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
1060
2
    BreakContinue BC = BreakContinueStack.pop_back_val();
1061
2
1062
2
    // The body count applies to the area immediately after the range.
1063
2
    auto Gap = findGapAreaBetween(getPreciseTokenLocEnd(S->getRParenLoc()),
1064
2
                                  getStart(S->getBody()));
1065
2
    if (Gap)
1066
2
      fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
1067
2
1068
2
    Counter LoopCount =
1069
2
        addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
1070
2
    Counter OutCount =
1071
2
        addCounters(BC.BreakCount, subtractCounters(LoopCount, BodyCount));
1072
2
    if (OutCount != ParentCount)
1073
0
      pushRegion(OutCount);
1074
2
  }
1075
1076
1
  void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S) {
1077
1
    extendRegion(S);
1078
1
    Visit(S->getElement());
1079
1
1080
1
    Counter ParentCount = getRegion().getCounter();
1081
1
    Counter BodyCount = getRegionCounter(S);
1082
1
1083
1
    BreakContinueStack.push_back(BreakContinue());
1084
1
    extendRegion(S->getBody());
1085
1
    Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
1086
1
    BreakContinue BC = BreakContinueStack.pop_back_val();
1087
1
1088
1
    // The body count applies to the area immediately after the collection.
1089
1
    auto Gap = findGapAreaBetween(getPreciseTokenLocEnd(S->getRParenLoc()),
1090
1
                                  getStart(S->getBody()));
1091
1
    if (Gap)
1092
1
      fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
1093
1
1094
1
    Counter LoopCount =
1095
1
        addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
1096
1
    Counter OutCount =
1097
1
        addCounters(BC.BreakCount, subtractCounters(LoopCount, BodyCount));
1098
1
    if (OutCount != ParentCount)
1099
0
      pushRegion(OutCount);
1100
1
  }
1101
1102
18
  void VisitSwitchStmt(const SwitchStmt *S) {
1103
18
    extendRegion(S);
1104
18
    if (S->getInit())
1105
1
      Visit(S->getInit());
1106
18
    Visit(S->getCond());
1107
18
1108
18
    BreakContinueStack.push_back(BreakContinue());
1109
18
1110
18
    const Stmt *Body = S->getBody();
1111
18
    extendRegion(Body);
1112
18
    if (const auto *CS = dyn_cast<CompoundStmt>(Body)) {
1113
14
      if (!CS->body_empty()) {
1114
12
        // Make a region for the body of the switch.  If the body starts with
1115
12
        // a case, that case will reuse this region; otherwise, this covers
1116
12
        // the unreachable code at the beginning of the switch body.
1117
12
        size_t Index = pushRegion(Counter::getZero(), getStart(CS));
1118
12
        getRegion().setGap(true);
1119
12
        for (const auto *Child : CS->children())
1120
36
          Visit(Child);
1121
12
1122
12
        // Set the end for the body of the switch, if it isn't already set.
1123
67
        for (size_t i = RegionStack.size(); i != Index; 
--i55
) {
1124
55
          if (!RegionStack[i - 1].hasEndLoc())
1125
33
            RegionStack[i - 1].setEndLoc(getEnd(CS->body_back()));
1126
55
        }
1127
12
1128
12
        popRegions(Index);
1129
12
      }
1130
14
    } else
1131
4
      propagateCounts(Counter::getZero(), Body);
1132
18
    BreakContinue BC = BreakContinueStack.pop_back_val();
1133
18
1134
18
    if (!BreakContinueStack.empty())
1135
2
      BreakContinueStack.back().ContinueCount = addCounters(
1136
2
          BreakContinueStack.back().ContinueCount, BC.ContinueCount);
1137
18
1138
18
    Counter ExitCount = getRegionCounter(S);
1139
18
    SourceLocation ExitLoc = getEnd(S);
1140
18
    pushRegion(ExitCount);
1141
18
1142
18
    // Ensure that handleFileExit recognizes when the end location is located
1143
18
    // in a different file.
1144
18
    MostRecentLocation = getStart(S);
1145
18
    handleFileExit(ExitLoc);
1146
18
  }
1147
1148
32
  void VisitSwitchCase(const SwitchCase *S) {
1149
32
    extendRegion(S);
1150
32
1151
32
    SourceMappingRegion &Parent = getRegion();
1152
32
1153
32
    Counter Count = addCounters(Parent.getCounter(), getRegionCounter(S));
1154
32
    // Reuse the existing region if it starts at our label. This is typical of
1155
32
    // the first case in a switch.
1156
32
    if (Parent.hasStartLoc() && Parent.getBeginLoc() == getStart(S))
1157
13
      Parent.setCounter(Count);
1158
19
    else
1159
19
      pushRegion(Count, getStart(S));
1160
32
1161
32
    if (const auto *CS = dyn_cast<CaseStmt>(S)) {
1162
23
      Visit(CS->getLHS());
1163
23
      if (const Expr *RHS = CS->getRHS())
1164
0
        Visit(RHS);
1165
23
    }
1166
32
    Visit(S->getSubStmt());
1167
32
  }
1168
1169
113
  void VisitIfStmt(const IfStmt *S) {
1170
113
    extendRegion(S);
1171
113
    if (S->getInit())
1172
1
      Visit(S->getInit());
1173
113
1174
113
    // Extend into the condition before we propagate through it below - this is
1175
113
    // needed to handle macros that generate the "if" but not the condition.
1176
113
    extendRegion(S->getCond());
1177
113
1178
113
    Counter ParentCount = getRegion().getCounter();
1179
113
    Counter ThenCount = getRegionCounter(S);
1180
113
1181
113
    // Emitting a counter for the condition makes it easier to interpret the
1182
113
    // counter for the body when looking at the coverage.
1183
113
    propagateCounts(ParentCount, S->getCond());
1184
113
1185
113
    // The 'then' count applies to the area immediately after the condition.
1186
113
    auto Gap = findGapAreaBetween(S->getCond(), S->getThen());
1187
113
    if (Gap)
1188
76
      fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), ThenCount);
1189
113
1190
113
    extendRegion(S->getThen());
1191
113
    Counter OutCount = propagateCounts(ThenCount, S->getThen());
1192
113
1193
113
    Counter ElseCount = subtractCounters(ParentCount, ThenCount);
1194
113
    if (const Stmt *Else = S->getElse()) {
1195
29
      // The 'else' count applies to the area immediately after the 'then'.
1196
29
      Gap = findGapAreaBetween(S->getThen(), Else);
1197
29
      if (Gap)
1198
23
        fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), ElseCount);
1199
29
      extendRegion(Else);
1200
29
      OutCount = addCounters(OutCount, propagateCounts(ElseCount, Else));
1201
29
    } else
1202
84
      OutCount = addCounters(OutCount, ElseCount);
1203
113
1204
113
    if (OutCount != ParentCount)
1205
55
      pushRegion(OutCount);
1206
113
  }
1207
1208
7
  void VisitCXXTryStmt(const CXXTryStmt *S) {
1209
7
    extendRegion(S);
1210
7
    // Handle macros that generate the "try" but not the rest.
1211
7
    extendRegion(S->getTryBlock());
1212
7
1213
7
    Counter ParentCount = getRegion().getCounter();
1214
7
    propagateCounts(ParentCount, S->getTryBlock());
1215
7
1216
16
    for (unsigned I = 0, E = S->getNumHandlers(); I < E; 
++I9
)
1217
9
      Visit(S->getHandler(I));
1218
7
1219
7
    Counter ExitCount = getRegionCounter(S);
1220
7
    pushRegion(ExitCount);
1221
7
  }
1222
1223
9
  void VisitCXXCatchStmt(const CXXCatchStmt *S) {
1224
9
    propagateCounts(getRegionCounter(S), S->getHandlerBlock());
1225
9
  }
1226
1227
12
  void VisitAbstractConditionalOperator(const AbstractConditionalOperator *E) {
1228
12
    extendRegion(E);
1229
12
1230
12
    Counter ParentCount = getRegion().getCounter();
1231
12
    Counter TrueCount = getRegionCounter(E);
1232
12
1233
12
    Visit(E->getCond());
1234
12
1235
12
    if (!isa<BinaryConditionalOperator>(E)) {
1236
10
      // The 'then' count applies to the area immediately after the condition.
1237
10
      auto Gap =
1238
10
          findGapAreaBetween(E->getQuestionLoc(), getStart(E->getTrueExpr()));
1239
10
      if (Gap)
1240
7
        fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), TrueCount);
1241
10
1242
10
      extendRegion(E->getTrueExpr());
1243
10
      propagateCounts(TrueCount, E->getTrueExpr());
1244
10
    }
1245
12
1246
12
    extendRegion(E->getFalseExpr());
1247
12
    propagateCounts(subtractCounters(ParentCount, TrueCount),
1248
12
                    E->getFalseExpr());
1249
12
  }
1250
1251
3
  void VisitBinLAnd(const BinaryOperator *E) {
1252
3
    extendRegion(E->getLHS());
1253
3
    propagateCounts(getRegion().getCounter(), E->getLHS());
1254
3
    handleFileExit(getEnd(E->getLHS()));
1255
3
1256
3
    extendRegion(E->getRHS());
1257
3
    propagateCounts(getRegionCounter(E), E->getRHS());
1258
3
  }
1259
1260
5
  void VisitBinLOr(const BinaryOperator *E) {
1261
5
    extendRegion(E->getLHS());
1262
5
    propagateCounts(getRegion().getCounter(), E->getLHS());
1263
5
    handleFileExit(getEnd(E->getLHS()));
1264
5
1265
5
    extendRegion(E->getRHS());
1266
5
    propagateCounts(getRegionCounter(E), E->getRHS());
1267
5
  }
1268
1269
2
  void VisitLambdaExpr(const LambdaExpr *LE) {
1270
2
    // Lambdas are treated as their own functions for now, so we shouldn't
1271
2
    // propagate counts into them.
1272
2
  }
1273
};
1274
1275
59
std::string getCoverageSection(const CodeGenModule &CGM) {
1276
59
  return llvm::getInstrProfSectionName(
1277
59
      llvm::IPSK_covmap,
1278
59
      CGM.getContext().getTargetInfo().getTriple().getObjectFormat());
1279
59
}
1280
1281
234
std::string normalizeFilename(StringRef Filename) {
1282
234
  llvm::SmallString<256> Path(Filename);
1283
234
  llvm::sys::fs::make_absolute(Path);
1284
234
  llvm::sys::path::remove_dots(Path, /*remove_dot_dot=*/true);
1285
234
  return std::string(Path);
1286
234
}
1287
1288
} // end anonymous namespace
1289
1290
static void dump(llvm::raw_ostream &OS, StringRef FunctionName,
1291
                 ArrayRef<CounterExpression> Expressions,
1292
152
                 ArrayRef<CounterMappingRegion> Regions) {
1293
152
  OS << FunctionName << ":\n";
1294
152
  CounterMappingContext Ctx(Expressions);
1295
1.21k
  for (const auto &R : Regions) {
1296
1.21k
    OS.indent(2);
1297
1.21k
    switch (R.Kind) {
1298
867
    case CounterMappingRegion::CodeRegion:
1299
867
      break;
1300
142
    case CounterMappingRegion::ExpansionRegion:
1301
142
      OS << "Expansion,";
1302
142
      break;
1303
9
    case CounterMappingRegion::SkippedRegion:
1304
9
      OS << "Skipped,";
1305
9
      break;
1306
196
    case CounterMappingRegion::GapRegion:
1307
196
      OS << "Gap,";
1308
196
      break;
1309
1.21k
    }
1310
1.21k
1311
1.21k
    OS << "File " << R.FileID << ", " << R.LineStart << ":" << R.ColumnStart
1312
1.21k
       << " -> " << R.LineEnd << ":" << R.ColumnEnd << " = ";
1313
1.21k
    Ctx.dump(R.Count, OS);
1314
1.21k
    if (R.Kind == CounterMappingRegion::ExpansionRegion)
1315
142
      OS << " (Expanded file = " << R.ExpandedFileID << ")";
1316
1.21k
    OS << "\n";
1317
1.21k
  }
1318
152
}
1319
1320
void CoverageMappingModuleGen::addFunctionMappingRecord(
1321
    llvm::GlobalVariable *NamePtr, StringRef NameValue, uint64_t FuncHash,
1322
180
    const std::string &CoverageMapping, bool IsUsed) {
1323
180
  llvm::LLVMContext &Ctx = CGM.getLLVMContext();
1324
180
  if (!FunctionRecordTy) {
1325
177
#define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) LLVMType,
1326
59
    llvm::Type *FunctionRecordTypes[] = {
1327
59
      #include "llvm/ProfileData/InstrProfData.inc"
1328
59
    };
1329
59
    FunctionRecordTy =
1330
59
        llvm::StructType::get(Ctx, makeArrayRef(FunctionRecordTypes),
1331
59
                              /*isPacked=*/true);
1332
59
  }
1333
180
1334
540
  #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Init,
1335
180
  llvm::Constant *FunctionRecordVals[] = {
1336
180
      #include "llvm/ProfileData/InstrProfData.inc"
1337
180
  };
1338
180
  FunctionRecords.push_back(llvm::ConstantStruct::get(
1339
180
      FunctionRecordTy, makeArrayRef(FunctionRecordVals)));
1340
180
  if (!IsUsed)
1341
17
    FunctionNames.push_back(
1342
17
        llvm::ConstantExpr::getBitCast(NamePtr, llvm::Type::getInt8PtrTy(Ctx)));
1343
180
  CoverageMappings.push_back(CoverageMapping);
1344
180
1345
180
  if (CGM.getCodeGenOpts().DumpCoverageMapping) {
1346
152
    // Dump the coverage mapping data for this function by decoding the
1347
152
    // encoded data. This allows us to dump the mapping regions which were
1348
152
    // also processed by the CoverageMappingWriter which performs
1349
152
    // additional minimization operations such as reducing the number of
1350
152
    // expressions.
1351
152
    std::vector<StringRef> Filenames;
1352
152
    std::vector<CounterExpression> Expressions;
1353
152
    std::vector<CounterMappingRegion> Regions;
1354
152
    llvm::SmallVector<std::string, 16> FilenameStrs;
1355
152
    llvm::SmallVector<StringRef, 16> FilenameRefs;
1356
152
    FilenameStrs.resize(FileEntries.size());
1357
152
    FilenameRefs.resize(FileEntries.size());
1358
167
    for (const auto &Entry : FileEntries) {
1359
167
      auto I = Entry.second;
1360
167
      FilenameStrs[I] = normalizeFilename(Entry.first->getName());
1361
167
      FilenameRefs[I] = FilenameStrs[I];
1362
167
    }
1363
152
    RawCoverageMappingReader Reader(CoverageMapping, FilenameRefs, Filenames,
1364
152
                                    Expressions, Regions);
1365
152
    if (Reader.read())
1366
0
      return;
1367
152
    dump(llvm::outs(), NameValue, Expressions, Regions);
1368
152
  }
1369
180
}
1370
1371
59
void CoverageMappingModuleGen::emit() {
1372
59
  if (FunctionRecords.empty())
1373
0
    return;
1374
59
  llvm::LLVMContext &Ctx = CGM.getLLVMContext();
1375
59
  auto *Int32Ty = llvm::Type::getInt32Ty(Ctx);
1376
59
1377
59
  // Create the filenames and merge them with coverage mappings
1378
59
  llvm::SmallVector<std::string, 16> FilenameStrs;
1379
59
  llvm::SmallVector<StringRef, 16> FilenameRefs;
1380
59
  FilenameStrs.resize(FileEntries.size());
1381
59
  FilenameRefs.resize(FileEntries.size());
1382
67
  for (const auto &Entry : FileEntries) {
1383
67
    auto I = Entry.second;
1384
67
    FilenameStrs[I] = normalizeFilename(Entry.first->getName());
1385
67
    FilenameRefs[I] = FilenameStrs[I];
1386
67
  }
1387
59
1388
59
  std::string FilenamesAndCoverageMappings;
1389
59
  llvm::raw_string_ostream OS(FilenamesAndCoverageMappings);
1390
59
  CoverageFilenamesSectionWriter(FilenameRefs).write(OS);
1391
59
1392
59
  // Stream the content of CoverageMappings to OS while keeping
1393
59
  // memory consumption under control.
1394
59
  size_t CoverageMappingSize = 0;
1395
180
  for (auto &S : CoverageMappings) {
1396
180
    CoverageMappingSize += S.size();
1397
180
    OS << S;
1398
180
    S.clear();
1399
180
    S.shrink_to_fit();
1400
180
  }
1401
59
  CoverageMappings.clear();
1402
59
  CoverageMappings.shrink_to_fit();
1403
59
1404
59
  size_t FilenamesSize = OS.str().size() - CoverageMappingSize;
1405
59
  // Append extra zeroes if necessary to ensure that the size of the filenames
1406
59
  // and coverage mappings is a multiple of 8.
1407
59
  if (size_t Rem = OS.str().size() % 8) {
1408
54
    CoverageMappingSize += 8 - Rem;
1409
54
    OS.write_zeros(8 - Rem);
1410
54
  }
1411
59
  auto *FilenamesAndMappingsVal =
1412
59
      llvm::ConstantDataArray::getString(Ctx, OS.str(), false);
1413
59
1414
59
  // Create the deferred function records array
1415
59
  auto RecordsTy =
1416
59
      llvm::ArrayType::get(FunctionRecordTy, FunctionRecords.size());
1417
59
  auto RecordsVal = llvm::ConstantArray::get(RecordsTy, FunctionRecords);
1418
59
1419
59
  llvm::Type *CovDataHeaderTypes[] = {
1420
236
#define COVMAP_HEADER(Type, LLVMType, Name, Init) LLVMType,
1421
59
#include "llvm/ProfileData/InstrProfData.inc"
1422
59
  };
1423
59
  auto CovDataHeaderTy =
1424
59
      llvm::StructType::get(Ctx, makeArrayRef(CovDataHeaderTypes));
1425
59
  llvm::Constant *CovDataHeaderVals[] = {
1426
236
#define COVMAP_HEADER(Type, LLVMType, Name, Init) Init,
1427
59
#include "llvm/ProfileData/InstrProfData.inc"
1428
59
  };
1429
59
  auto CovDataHeaderVal = llvm::ConstantStruct::get(
1430
59
      CovDataHeaderTy, makeArrayRef(CovDataHeaderVals));
1431
59
1432
59
  // Create the coverage data record
1433
59
  llvm::Type *CovDataTypes[] = {CovDataHeaderTy, RecordsTy,
1434
59
                                FilenamesAndMappingsVal->getType()};
1435
59
  auto CovDataTy = llvm::StructType::get(Ctx, makeArrayRef(CovDataTypes));
1436
59
  llvm::Constant *TUDataVals[] = {CovDataHeaderVal, RecordsVal,
1437
59
                                  FilenamesAndMappingsVal};
1438
59
  auto CovDataVal =
1439
59
      llvm::ConstantStruct::get(CovDataTy, makeArrayRef(TUDataVals));
1440
59
  auto CovData = new llvm::GlobalVariable(
1441
59
      CGM.getModule(), CovDataTy, true, llvm::GlobalValue::InternalLinkage,
1442
59
      CovDataVal, llvm::getCoverageMappingVarName());
1443
59
1444
59
  CovData->setSection(getCoverageSection(CGM));
1445
59
  CovData->setAlignment(llvm::Align(8));
1446
59
1447
59
  // Make sure the data doesn't get deleted.
1448
59
  CGM.addUsedGlobal(CovData);
1449
59
  // Create the deferred function records array
1450
59
  if (!FunctionNames.empty()) {
1451
6
    auto NamesArrTy = llvm::ArrayType::get(llvm::Type::getInt8PtrTy(Ctx),
1452
6
                                           FunctionNames.size());
1453
6
    auto NamesArrVal = llvm::ConstantArray::get(NamesArrTy, FunctionNames);
1454
6
    // This variable will *NOT* be emitted to the object file. It is used
1455
6
    // to pass the list of names referenced to codegen.
1456
6
    new llvm::GlobalVariable(CGM.getModule(), NamesArrTy, true,
1457
6
                             llvm::GlobalValue::InternalLinkage, NamesArrVal,
1458
6
                             llvm::getCoverageUnusedNamesVarName());
1459
6
  }
1460
59
}
1461
1462
322
unsigned CoverageMappingModuleGen::getFileID(const FileEntry *File) {
1463
322
  auto It = FileEntries.find(File);
1464
322
  if (It != FileEntries.end())
1465
255
    return It->second;
1466
67
  unsigned FileID = FileEntries.size();
1467
67
  FileEntries.insert(std::make_pair(File, FileID));
1468
67
  return FileID;
1469
67
}
1470
1471
void CoverageMappingGen::emitCounterMapping(const Decl *D,
1472
164
                                            llvm::raw_ostream &OS) {
1473
164
  assert(CounterMap);
1474
164
  CounterCoverageMappingBuilder Walker(CVM, *CounterMap, SM, LangOpts);
1475
164
  Walker.VisitDecl(D);
1476
164
  Walker.write(OS);
1477
164
}
1478
1479
void CoverageMappingGen::emitEmptyMapping(const Decl *D,
1480
17
                                          llvm::raw_ostream &OS) {
1481
17
  EmptyCoverageMappingBuilder Walker(CVM, SM, LangOpts);
1482
17
  Walker.VisitDecl(D);
1483
17
  Walker.write(OS);
1484
17
}