Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/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.31k
        DeferRegion(DeferRegion), GapRegion(GapRegion) {}
60
61
5.19k
  const Counter &getCounter() const { return Count; }
62
63
70
  void setCounter(Counter C) { Count = C; }
64
65
4.33k
  bool hasStartLoc() const { return LocStart.hasValue(); }
66
67
1.04k
  void setStartLoc(SourceLocation Loc) { LocStart = Loc; }
68
69
3.85k
  SourceLocation getBeginLoc() const {
70
3.85k
    assert(LocStart && "Region has no start location");
71
3.85k
    return *LocStart;
72
3.85k
  }
73
74
1.14k
  bool hasEndLoc() const { return LocEnd.hasValue(); }
75
76
1.00k
  void setEndLoc(SourceLocation Loc) {
77
1.00k
    assert(Loc.isValid() && "Setting an invalid end location");
78
1.00k
    LocEnd = Loc;
79
1.00k
  }
80
81
2.00k
  SourceLocation getEndLoc() const {
82
2.00k
    assert(LocEnd && "Region has no end location");
83
2.00k
    return *LocEnd;
84
2.00k
  }
85
86
159
  bool isDeferred() const { return DeferRegion; }
87
88
152
  void setDeferred(bool Deferred) { DeferRegion = Deferred; }
89
90
1.07k
  bool isGap() const { return GapRegion; }
91
92
186
  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
1.27k
                 SourceLocation LocEnd) {
111
1.27k
    LineStart = SM.getSpellingLineNumber(LocStart);
112
1.27k
    ColumnStart = SM.getSpellingColumnNumber(LocStart);
113
1.27k
    LineEnd = SM.getSpellingLineNumber(LocEnd);
114
1.27k
    ColumnEnd = SM.getSpellingColumnNumber(LocEnd);
115
1.27k
  }
116
117
  SpellingRegion(SourceManager &SM, SourceMappingRegion &R)
118
0
      : 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
54
  bool isInSourceOrder() const {
123
54
    return (LineStart < LineEnd) ||
124
54
           
(12
LineStart == LineEnd12
&&
ColumnStart <= ColumnEnd6
);
125
54
  }
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
179
      : CVM(CVM), SM(SM), LangOpts(LangOpts) {}
158
159
  /// Return the precise end location for the given token.
160
3.64k
  SourceLocation getPreciseTokenLocEnd(SourceLocation Loc) {
161
3.64k
    // We avoid getLocForEndOfToken here, because it doesn't do what we want for
162
3.64k
    // macro locations, which we just treat as expanded files.
163
3.64k
    unsigned TokLen =
164
3.64k
        Lexer::MeasureTokenLength(SM.getSpellingLoc(Loc), SM, LangOpts);
165
3.64k
    return Loc.getLocWithOffset(TokLen);
166
3.64k
  }
167
168
  /// Return the start location of an included file or expanded macro.
169
1.05k
  SourceLocation getStartOfFileOrMacro(SourceLocation Loc) {
170
1.05k
    if (Loc.isMacroID())
171
222
      return Loc.getLocWithOffset(-SM.getFileOffset(Loc));
172
835
    return SM.getLocForStartOfFile(SM.getFileID(Loc));
173
835
  }
174
175
  /// Return the end location of an included file or expanded macro.
176
215
  SourceLocation getEndOfFileOrMacro(SourceLocation Loc) {
177
215
    if (Loc.isMacroID())
178
157
      return Loc.getLocWithOffset(SM.getFileIDSize(SM.getFileID(Loc)) -
179
157
                                  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.16k
  SourceLocation getIncludeOrExpansionLoc(SourceLocation Loc) {
185
4.16k
    return Loc.isMacroID() ? 
SM.getImmediateExpansionRange(Loc).getBegin()1.19k
186
4.16k
                           : 
SM.getIncludeLoc(SM.getFileID(Loc))2.97k
;
187
4.16k
  }
188
189
  /// Return true if \c Loc is a location in a built-in macro.
190
7.36k
  bool isInBuiltin(SourceLocation Loc) {
191
7.36k
    return SM.getBufferName(SM.getSpellingLoc(Loc)) == "<built-in>";
192
7.36k
  }
193
194
  /// Check whether \c Loc is included or expanded from \c Parent.
195
641
  bool isNestedIn(SourceLocation Loc, FileID Parent) {
196
753
    do {
197
753
      Loc = getIncludeOrExpansionLoc(Loc);
198
753
      if (Loc.isInvalid())
199
357
        return false;
200
396
    } while (!SM.isInFileID(Loc, Parent));
201
641
    
return true284
;
202
641
  }
203
204
  /// Get the start of \c S ignoring macro arguments and builtin macros.
205
4.14k
  SourceLocation getStart(const Stmt *S) {
206
4.14k
    SourceLocation Loc = S->getBeginLoc();
207
4.37k
    while (SM.isMacroArgExpansion(Loc) || 
isInBuiltin(Loc)4.14k
)
208
231
      Loc = SM.getImmediateExpansionRange(Loc).getBegin();
209
4.14k
    return Loc;
210
4.14k
  }
211
212
  /// Get the end of \c S ignoring macro arguments and builtin macros.
213
3.21k
  SourceLocation getEnd(const Stmt *S) {
214
3.21k
    SourceLocation Loc = S->getEndLoc();
215
3.40k
    while (SM.isMacroArgExpansion(Loc) || 
isInBuiltin(Loc)3.21k
)
216
182
      Loc = SM.getImmediateExpansionRange(Loc).getBegin();
217
3.21k
    return getPreciseTokenLocEnd(Loc);
218
3.21k
  }
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
179
  void gatherFileIDs(SmallVectorImpl<unsigned> &Mapping) {
226
179
    FileIDMapping.clear();
227
179
228
179
    llvm::SmallSet<FileID, 8> Visited;
229
179
    SmallVector<std::pair<SourceLocation, unsigned>, 8> FileLocs;
230
1.08k
    for (const auto &Region : SourceRegions) {
231
1.08k
      SourceLocation Loc = Region.getBeginLoc();
232
1.08k
      FileID File = SM.getFileID(Loc);
233
1.08k
      if (!Visited.insert(File).second)
234
765
        continue;
235
324
236
324
      // Do not map FileID's associated with system headers.
237
324
      if (SM.isInSystemHeader(SM.getSpellingLoc(Loc)))
238
3
        continue;
239
321
240
321
      unsigned Depth = 0;
241
321
      for (SourceLocation Parent = getIncludeOrExpansionLoc(Loc);
242
514
           Parent.isValid(); 
Parent = getIncludeOrExpansionLoc(Parent)193
)
243
193
        ++Depth;
244
321
      FileLocs.push_back(std::make_pair(Loc, Depth));
245
321
    }
246
179
    llvm::stable_sort(FileLocs, llvm::less_second());
247
179
248
321
    for (const auto &FL : FileLocs) {
249
321
      SourceLocation Loc = FL.first;
250
321
      FileID SpellingFile = SM.getDecomposedSpellingLoc(Loc).first;
251
321
      auto Entry = SM.getFileEntryForID(SpellingFile);
252
321
      if (!Entry)
253
4
        continue;
254
317
255
317
      FileIDMapping[SM.getFileID(Loc)] = std::make_pair(Mapping.size(), Loc);
256
317
      Mapping.push_back(CVM.getFileID(Entry));
257
317
    }
258
179
  }
259
260
  /// Get the coverage mapping file ID for \c Loc.
261
  ///
262
  /// If such file id doesn't exist, return None.
263
1.38k
  Optional<unsigned> getCoverageFileID(SourceLocation Loc) {
264
1.38k
    auto Mapping = FileIDMapping.find(SM.getFileID(Loc));
265
1.38k
    if (Mapping != FileIDMapping.end())
266
1.36k
      return Mapping->second.first;
267
14
    return None;
268
14
  }
269
270
  /// Gather all the regions that were skipped by the preprocessor
271
  /// using the constructs like #if.
272
162
  void gatherSkippedRegions() {
273
162
    /// An array of the minimum lineStarts and the maximum lineEnds
274
162
    /// for mapping regions from the appropriate source files.
275
162
    llvm::SmallVector<std::pair<unsigned, unsigned>, 8> FileLineRanges;
276
162
    FileLineRanges.resize(
277
162
        FileIDMapping.size(),
278
162
        std::make_pair(std::numeric_limits<unsigned>::max(), 0));
279
1.19k
    for (const auto &R : MappingRegions) {
280
1.19k
      FileLineRanges[R.FileID].first =
281
1.19k
          std::min(FileLineRanges[R.FileID].first, R.LineStart);
282
1.19k
      FileLineRanges[R.FileID].second =
283
1.19k
          std::max(FileLineRanges[R.FileID].second, R.LineEnd);
284
1.19k
    }
285
162
286
162
    auto SkippedRanges = CVM.getSourceInfo().getSkippedRanges();
287
162
    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
162
  }
306
307
  /// Generate the coverage counter mapping regions from collected
308
  /// source regions.
309
179
  void emitSourceRegions(const SourceRegionFilter &Filter) {
310
1.08k
    for (const auto &Region : SourceRegions) {
311
1.08k
      assert(Region.hasEndLoc() && "incomplete region");
312
1.08k
313
1.08k
      SourceLocation LocStart = Region.getBeginLoc();
314
1.08k
      assert(SM.getFileID(LocStart).isValid() && "region in invalid file");
315
1.08k
316
1.08k
      // Ignore regions from system headers.
317
1.08k
      if (SM.isInSystemHeader(SM.getSpellingLoc(LocStart)))
318
7
        continue;
319
1.08k
320
1.08k
      auto CovFileID = getCoverageFileID(LocStart);
321
1.08k
      // Ignore regions that don't have a file, such as builtin macros.
322
1.08k
      if (!CovFileID)
323
4
        continue;
324
1.07k
325
1.07k
      SourceLocation LocEnd = Region.getEndLoc();
326
1.07k
      assert(SM.isWrittenInSameFile(LocStart, LocEnd) &&
327
1.07k
             "region spans multiple files");
328
1.07k
329
1.07k
      // Don't add code regions for the area covered by expansion regions.
330
1.07k
      // This not only suppresses redundant regions, but sometimes prevents
331
1.07k
      // creating regions with wrong counters if, for example, a statement's
332
1.07k
      // body ends at the end of a nested macro.
333
1.07k
      if (Filter.count(std::make_pair(LocStart, LocEnd)))
334
8
        continue;
335
1.07k
336
1.07k
      // Find the spelling locations for the mapping region.
337
1.07k
      SpellingRegion SR{SM, LocStart, LocEnd};
338
1.07k
      assert(SR.isInSourceOrder() && "region start and end out of order");
339
1.07k
340
1.07k
      if (Region.isGap()) {
341
186
        MappingRegions.push_back(CounterMappingRegion::makeGapRegion(
342
186
            Region.getCounter(), *CovFileID, SR.LineStart, SR.ColumnStart,
343
186
            SR.LineEnd, SR.ColumnEnd));
344
884
      } else {
345
884
        MappingRegions.push_back(CounterMappingRegion::makeRegion(
346
884
            Region.getCounter(), *CovFileID, SR.LineStart, SR.ColumnStart,
347
884
            SR.LineEnd, SR.ColumnEnd));
348
884
      }
349
1.07k
    }
350
179
  }
351
352
  /// Generate expansion regions for each virtual file we've seen.
353
162
  SourceRegionFilter emitExpansionRegions() {
354
162
    SourceRegionFilter Filter;
355
300
    for (const auto &FM : FileIDMapping) {
356
300
      SourceLocation ExpandedLoc = FM.second.second;
357
300
      SourceLocation ParentLoc = getIncludeOrExpansionLoc(ExpandedLoc);
358
300
      if (ParentLoc.isInvalid())
359
156
        continue;
360
144
361
144
      auto ParentFileID = getCoverageFileID(ParentLoc);
362
144
      if (!ParentFileID)
363
5
        continue;
364
139
      auto ExpandedFileID = getCoverageFileID(ExpandedLoc);
365
139
      assert(ExpandedFileID && "expansion in uncovered file");
366
139
367
139
      SourceLocation LocEnd = getPreciseTokenLocEnd(ParentLoc);
368
139
      assert(SM.isWrittenInSameFile(ParentLoc, LocEnd) &&
369
139
             "region spans multiple files");
370
139
      Filter.insert(std::make_pair(ParentLoc, LocEnd));
371
139
372
139
      SpellingRegion SR{SM, ParentLoc, LocEnd};
373
139
      assert(SR.isInSourceOrder() && "region start and end out of order");
374
139
      MappingRegions.push_back(CounterMappingRegion::makeExpansion(
375
139
          *ParentFileID, *ExpandedFileID, SR.LineStart, SR.ColumnStart,
376
139
          SR.LineEnd, SR.ColumnEnd));
377
139
    }
378
162
    return Filter;
379
162
  }
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
194
  Counter subtractCounters(Counter LHS, Counter RHS) {
458
194
    return Builder.subtract(LHS, RHS);
459
194
  }
460
461
  /// Return a counter for the sum of \c LHS and \c RHS.
462
459
  Counter addCounters(Counter LHS, Counter RHS) {
463
459
    return Builder.add(LHS, RHS);
464
459
  }
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
440
  Counter getRegionCounter(const Stmt *S) {
474
440
    return Counter::getCounter(CounterMap[S]);
475
440
  }
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.02k
                    Optional<SourceLocation> EndLoc = None) {
483
1.02k
    if (StartLoc) {
484
786
      MostRecentLocation = *StartLoc;
485
786
      completeDeferred(Count, MostRecentLocation);
486
786
    }
487
1.02k
    RegionStack.emplace_back(Count, StartLoc, EndLoc);
488
1.02k
489
1.02k
    return RegionStack.size() - 1;
490
1.02k
  }
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.86k
  size_t completeDeferred(Counter Count, SourceLocation DeferredEndLoc) {
495
3.86k
    size_t Index = RegionStack.size();
496
3.86k
    if (!DeferredRegion)
497
3.81k
      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.82k
  size_t locationDepth(SourceLocation Loc) {
555
1.82k
    size_t Depth = 0;
556
4.04k
    while (Loc.isValid()) {
557
2.21k
      Loc = getIncludeOrExpansionLoc(Loc);
558
2.21k
      Depth++;
559
2.21k
    }
560
1.82k
    return Depth;
561
1.82k
  }
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
764
  void popRegions(size_t ParentIndex) {
568
764
    assert(RegionStack.size() >= ParentIndex && "parent not in stack");
569
764
    bool ParentOfDeferredRegion = false;
570
1.83k
    while (RegionStack.size() > ParentIndex) {
571
1.07k
      SourceMappingRegion &Region = RegionStack.back();
572
1.07k
      if (Region.hasStartLoc()) {
573
913
        SourceLocation StartLoc = Region.getBeginLoc();
574
913
        SourceLocation EndLoc = Region.hasEndLoc()
575
913
                                    ? 
Region.getEndLoc()838
576
913
                                    : 
RegionStack[ParentIndex].getEndLoc()75
;
577
913
        size_t StartDepth = locationDepth(StartLoc);
578
913
        size_t EndDepth = locationDepth(EndLoc);
579
938
        while (!SM.isWrittenInSameFile(StartLoc, EndLoc)) {
580
25
          bool UnnestStart = StartDepth >= EndDepth;
581
25
          bool UnnestEnd = EndDepth >= StartDepth;
582
25
          if (UnnestEnd) {
583
24
            // The region ends in a nested file or macro expansion. Create a
584
24
            // separate region for each expansion.
585
24
            SourceLocation NestedLoc = getStartOfFileOrMacro(EndLoc);
586
24
            assert(SM.isWrittenInSameFile(NestedLoc, EndLoc));
587
24
588
24
            if (!isRegionAlreadyAdded(NestedLoc, EndLoc))
589
23
              SourceRegions.emplace_back(Region.getCounter(), NestedLoc, EndLoc);
590
24
591
24
            EndLoc = getPreciseTokenLocEnd(getIncludeOrExpansionLoc(EndLoc));
592
24
            if (EndLoc.isInvalid())
593
0
              llvm::report_fatal_error("File exit not handled before popRegions");
594
24
            EndDepth--;
595
24
          }
596
25
          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
25
        }
611
913
        Region.setStartLoc(StartLoc);
612
913
        Region.setEndLoc(EndLoc);
613
913
614
913
        MostRecentLocation = EndLoc;
615
913
        // If this region happens to span an entire expansion, we need to make
616
913
        // sure we don't overlap the parent region with it.
617
913
        if (StartLoc == getStartOfFileOrMacro(StartLoc) &&
618
913
            
EndLoc == getEndOfFileOrMacro(EndLoc)34
)
619
34
          MostRecentLocation = getIncludeOrExpansionLoc(EndLoc);
620
913
621
913
        assert(SM.isWrittenInSameFile(Region.getBeginLoc(), EndLoc));
622
913
        assert(SpellingRegion(SM, Region).isInSourceOrder());
623
913
        SourceRegions.push_back(Region);
624
913
625
913
        if (ParentOfDeferredRegion) {
626
122
          ParentOfDeferredRegion = false;
627
122
628
122
          // If there's an existing deferred region, keep the old one, because
629
122
          // it means there are two consecutive returns (or a similar pattern).
630
122
          if (!DeferredRegion.hasValue() &&
631
122
              // File IDs aren't gathered within macro expansions, so it isn't
632
122
              // useful to try and create a deferred region inside of one.
633
122
              
!EndLoc.isMacroID()121
)
634
114
            DeferredRegion =
635
114
                SourceMappingRegion(Counter::getZero(), EndLoc, None);
636
122
        }
637
913
      } else 
if (159
Region.isDeferred()159
) {
638
122
        assert(!ParentOfDeferredRegion && "Consecutive deferred regions");
639
122
        ParentOfDeferredRegion = true;
640
122
      }
641
1.07k
      RegionStack.pop_back();
642
1.07k
643
1.07k
      // If the zero region pushed after the last terminated region no longer
644
1.07k
      // exists, clear its cached information.
645
1.07k
      if (LastTerminatedRegion &&
646
1.07k
          
RegionStack.size() < LastTerminatedRegion->second148
)
647
136
        LastTerminatedRegion = None;
648
1.07k
    }
649
764
    assert(!ParentOfDeferredRegion && "Deferred region with no parent");
650
764
  }
651
652
  /// Return the currently active region.
653
4.42k
  SourceMappingRegion &getRegion() {
654
4.42k
    assert(!RegionStack.empty() && "statement has no region");
655
4.42k
    return RegionStack.back();
656
4.42k
  }
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
615
                          bool VisitChildren = true) {
662
615
    SourceLocation StartLoc = getStart(S);
663
615
    SourceLocation EndLoc = getEnd(S);
664
615
    size_t Index = pushRegion(TopCount, StartLoc, EndLoc);
665
615
    if (VisitChildren)
666
605
      Visit(S);
667
615
    Counter ExitCount = getRegion().getCounter();
668
615
    popRegions(Index);
669
615
670
615
    // The statement may be spanned by an expansion. Make sure we handle a file
671
615
    // exit out of this expansion before moving to the next statement.
672
615
    if (SM.isBeforeInTranslationUnit(StartLoc, S->getBeginLoc()))
673
35
      MostRecentLocation = EndLoc;
674
615
675
615
    return ExitCount;
676
615
  }
677
678
  /// Check whether a region with bounds \c StartLoc and \c EndLoc
679
  /// is already added to \c SourceRegions.
680
33
  bool isRegionAlreadyAdded(SourceLocation StartLoc, SourceLocation EndLoc) {
681
33
    return SourceRegions.rend() !=
682
33
           std::find_if(SourceRegions.rbegin(), SourceRegions.rend(),
683
408
                        [&](const SourceMappingRegion &Region) {
684
408
                          return Region.getBeginLoc() == StartLoc &&
685
408
                                 
Region.getEndLoc() == EndLoc12
;
686
408
                        });
687
33
  }
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.60k
  void handleFileExit(SourceLocation NewLoc) {
712
5.60k
    if (NewLoc.isInvalid() ||
713
5.60k
        
SM.isWrittenInSameFile(MostRecentLocation, NewLoc)5.59k
)
714
5.39k
      return;
715
208
716
208
    // If NewLoc is not in a file that contains MostRecentLocation, walk up to
717
208
    // find the common ancestor.
718
208
    SourceLocation LCA = NewLoc;
719
208
    FileID ParentFile = SM.getFileID(LCA);
720
251
    while (!isNestedIn(MostRecentLocation, ParentFile)) {
721
139
      LCA = getIncludeOrExpansionLoc(LCA);
722
139
      if (LCA.isInvalid() || SM.isWrittenInSameFile(LCA, MostRecentLocation)) {
723
96
        // Since there isn't a common ancestor, no file was exited. We just need
724
96
        // to adjust our location to the new file.
725
96
        MostRecentLocation = NewLoc;
726
96
        return;
727
96
      }
728
43
      ParentFile = SM.getFileID(LCA);
729
43
    }
730
208
731
208
    llvm::SmallSet<SourceLocation, 8> StartLocs;
732
112
    Optional<Counter> ParentCounter;
733
168
    for (SourceMappingRegion &I : llvm::reverse(RegionStack)) {
734
168
      if (!I.hasStartLoc())
735
9
        continue;
736
159
      SourceLocation Loc = I.getBeginLoc();
737
159
      if (!isNestedIn(Loc, ParentFile)) {
738
107
        ParentCounter = I.getCounter();
739
107
        break;
740
107
      }
741
52
742
109
      
while (52
!SM.isInFileID(Loc, ParentFile)) {
743
57
        // The most nested region for each start location is the one with the
744
57
        // correct count. We avoid creating redundant regions by stopping once
745
57
        // we've seen this region.
746
57
        if (StartLocs.insert(Loc).second)
747
54
          SourceRegions.emplace_back(I.getCounter(), Loc,
748
54
                                     getEndOfFileOrMacro(Loc));
749
57
        Loc = getIncludeOrExpansionLoc(Loc);
750
57
      }
751
52
      I.setStartLoc(getPreciseTokenLocEnd(Loc));
752
52
    }
753
112
754
112
    if (ParentCounter) {
755
107
      // If the file is contained completely by another region and doesn't
756
107
      // immediately start its own region, the whole file gets a region
757
107
      // corresponding to the parent.
758
107
      SourceLocation Loc = MostRecentLocation;
759
219
      while (isNestedIn(Loc, ParentFile)) {
760
112
        SourceLocation FileStart = getStartOfFileOrMacro(Loc);
761
112
        if (StartLocs.insert(FileStart).second) {
762
81
          SourceRegions.emplace_back(*ParentCounter, FileStart,
763
81
                                     getEndOfFileOrMacro(Loc));
764
81
          assert(SpellingRegion(SM, SourceRegions.back()).isInSourceOrder());
765
81
        }
766
112
        Loc = getIncludeOrExpansionLoc(Loc);
767
112
      }
768
107
    }
769
112
770
112
    MostRecentLocation = NewLoc;
771
112
  }
772
773
  /// Ensure that \c S is included in the current region.
774
3.06k
  void extendRegion(const Stmt *S) {
775
3.06k
    SourceMappingRegion &Region = getRegion();
776
3.06k
    SourceLocation StartLoc = getStart(S);
777
3.06k
778
3.06k
    handleFileExit(StartLoc);
779
3.06k
    if (!Region.hasStartLoc())
780
79
      Region.setStartLoc(StartLoc);
781
3.06k
782
3.06k
    completeDeferred(Region.getCounter(), StartLoc);
783
3.06k
  }
784
785
  /// Mark \c S as a terminator, starting a zero region.
786
148
  void terminateRegion(const Stmt *S) {
787
148
    extendRegion(S);
788
148
    SourceMappingRegion &Region = getRegion();
789
148
    SourceLocation EndLoc = getEnd(S);
790
148
    if (!Region.hasEndLoc())
791
23
      Region.setEndLoc(EndLoc);
792
148
    pushRegion(Counter::getZero());
793
148
    auto &ZeroRegion = getRegion();
794
148
    ZeroRegion.setDeferred(true);
795
148
    LastTerminatedRegion = {EndLoc, RegionStack.size()};
796
148
  }
797
798
  /// Find a valid gap range between \p AfterLoc and \p BeforeLoc.
799
  Optional<SourceRange> findGapAreaBetween(SourceLocation AfterLoc,
800
212
                                           SourceLocation BeforeLoc) {
801
212
    // If the start and end locations of the gap are both within the same macro
802
212
    // file, the range may not be in source order.
803
212
    if (AfterLoc.isMacroID() || 
BeforeLoc.isMacroID()162
)
804
70
      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
162
        DeferredRegion(None) {}
843
844
  /// Write the mapping data to the output stream
845
162
  void write(llvm::raw_ostream &OS) {
846
162
    llvm::SmallVector<unsigned, 8> VirtualFileMapping;
847
162
    gatherFileIDs(VirtualFileMapping);
848
162
    SourceRegionFilter Filter = emitExpansionRegions();
849
162
    assert(!DeferredRegion && "Deferred region never completed");
850
162
    emitSourceRegions(Filter);
851
162
    gatherSkippedRegions();
852
162
853
162
    if (MappingRegions.empty())
854
1
      return;
855
161
856
161
    CoverageMappingWriter Writer(VirtualFileMapping, Builder.getExpressions(),
857
161
                                 MappingRegions);
858
161
    Writer.write(OS);
859
161
  }
860
861
2.17k
  void VisitStmt(const Stmt *S) {
862
2.17k
    if (S->getBeginLoc().isValid())
863
2.17k
      extendRegion(S);
864
2.17k
    for (const Stmt *Child : S->children())
865
1.77k
      if (Child)
866
1.77k
        this->Visit(Child);
867
2.17k
    handleFileExit(getEnd(S));
868
2.17k
  }
869
870
162
  void VisitDecl(const Decl *D) {
871
162
    assert(!DeferredRegion && "Deferred region never completed");
872
162
873
162
    Stmt *Body = D->getBody();
874
162
875
162
    // Do not propagate region counts into system headers.
876
162
    if (Body && SM.isInSystemHeader(SM.getSpellingLoc(getStart(Body))))
877
1
      return;
878
161
879
161
    // Do not visit the artificial children nodes of defaulted methods. The
880
161
    // lexer may not be able to report back precise token end locations for
881
161
    // these children nodes (llvm.org/PR39822), and moreover users will not be
882
161
    // able to see coverage for them.
883
161
    bool Defaulted = false;
884
161
    if (auto *Method = dyn_cast<CXXMethodDecl>(D))
885
25
      Defaulted = Method->isDefaulted();
886
161
887
161
    propagateCounts(getRegionCounter(Body), Body,
888
161
                    /*VisitChildren=*/!Defaulted);
889
161
    assert(RegionStack.empty() && "Regions entered but never exited");
890
161
891
161
    // Discard the last uncompleted deferred region in a decl, if one exists.
892
161
    // This prevents lines at the end of a function containing only whitespace
893
161
    // or closing braces from being marked as uncovered.
894
161
    DeferredRegion = None;
895
161
  }
896
897
105
  void VisitReturnStmt(const ReturnStmt *S) {
898
105
    extendRegion(S);
899
105
    if (S->getRetValue())
900
58
      Visit(S->getRetValue());
901
105
    terminateRegion(S);
902
105
  }
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
94
  void VisitCallExpr(const CallExpr *E) {
941
94
    VisitStmt(E);
942
94
943
94
    // Terminate the region when we hit a noreturn function.
944
94
    // (This is helpful dealing with switch statements.)
945
94
    QualType CalleeType = E->getCallee()->getType();
946
94
    if (getFunctionExtInfo(*CalleeType).getNoReturn())
947
3
      terminateRegion(E);
948
94
  }
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
17
  void VisitSwitchStmt(const SwitchStmt *S) {
1103
17
    extendRegion(S);
1104
17
    if (S->getInit())
1105
1
      Visit(S->getInit());
1106
17
    Visit(S->getCond());
1107
17
1108
17
    BreakContinueStack.push_back(BreakContinue());
1109
17
1110
17
    const Stmt *Body = S->getBody();
1111
17
    extendRegion(Body);
1112
17
    if (const auto *CS = dyn_cast<CompoundStmt>(Body)) {
1113
13
      if (!CS->body_empty()) {
1114
11
        // Make a region for the body of the switch.  If the body starts with
1115
11
        // a case, that case will reuse this region; otherwise, this covers
1116
11
        // the unreachable code at the beginning of the switch body.
1117
11
        size_t Index =
1118
11
            pushRegion(Counter::getZero(), getStart(CS->body_front()));
1119
11
        for (const auto *Child : CS->children())
1120
34
          Visit(Child);
1121
11
1122
11
        // Set the end for the body of the switch, if it isn't already set.
1123
52
        for (size_t i = RegionStack.size(); i != Index; 
--i41
) {
1124
41
          if (!RegionStack[i - 1].hasEndLoc())
1125
21
            RegionStack[i - 1].setEndLoc(getEnd(CS->body_back()));
1126
41
        }
1127
11
1128
11
        popRegions(Index);
1129
11
      }
1130
13
    } else
1131
4
      propagateCounts(Counter::getZero(), Body);
1132
17
    BreakContinue BC = BreakContinueStack.pop_back_val();
1133
17
1134
17
    if (!BreakContinueStack.empty())
1135
2
      BreakContinueStack.back().ContinueCount = addCounters(
1136
2
          BreakContinueStack.back().ContinueCount, BC.ContinueCount);
1137
17
1138
17
    Counter ExitCount = getRegionCounter(S);
1139
17
    SourceLocation ExitLoc = getEnd(S);
1140
17
    pushRegion(ExitCount);
1141
17
1142
17
    // Ensure that handleFileExit recognizes when the end location is located
1143
17
    // in a different file.
1144
17
    MostRecentLocation = getStart(S);
1145
17
    handleFileExit(ExitLoc);
1146
17
  }
1147
1148
30
  void VisitSwitchCase(const SwitchCase *S) {
1149
30
    extendRegion(S);
1150
30
1151
30
    SourceMappingRegion &Parent = getRegion();
1152
30
1153
30
    Counter Count = addCounters(Parent.getCounter(), getRegionCounter(S));
1154
30
    // Reuse the existing region if it starts at our label. This is typical of
1155
30
    // the first case in a switch.
1156
30
    if (Parent.hasStartLoc() && Parent.getBeginLoc() == getStart(S))
1157
22
      Parent.setCounter(Count);
1158
8
    else
1159
8
      pushRegion(Count, getStart(S));
1160
30
1161
30
    if (const auto *CS = dyn_cast<CaseStmt>(S)) {
1162
22
      Visit(CS->getLHS());
1163
22
      if (const Expr *RHS = CS->getRHS())
1164
0
        Visit(RHS);
1165
22
    }
1166
30
    Visit(S->getSubStmt());
1167
30
  }
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
11
  void VisitAbstractConditionalOperator(const AbstractConditionalOperator *E) {
1228
11
    extendRegion(E);
1229
11
1230
11
    Counter ParentCount = getRegion().getCounter();
1231
11
    Counter TrueCount = getRegionCounter(E);
1232
11
1233
11
    Visit(E->getCond());
1234
11
1235
11
    if (!isa<BinaryConditionalOperator>(E)) {
1236
9
      // The 'then' count applies to the area immediately after the condition.
1237
9
      auto Gap =
1238
9
          findGapAreaBetween(E->getQuestionLoc(), getStart(E->getTrueExpr()));
1239
9
      if (Gap)
1240
7
        fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), TrueCount);
1241
9
1242
9
      extendRegion(E->getTrueExpr());
1243
9
      propagateCounts(TrueCount, E->getTrueExpr());
1244
9
    }
1245
11
1246
11
    extendRegion(E->getFalseExpr());
1247
11
    propagateCounts(subtractCounters(ParentCount, TrueCount),
1248
11
                    E->getFalseExpr());
1249
11
  }
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
58
std::string getCoverageSection(const CodeGenModule &CGM) {
1276
58
  return llvm::getInstrProfSectionName(
1277
58
      llvm::IPSK_covmap,
1278
58
      CGM.getContext().getTargetInfo().getTriple().getObjectFormat());
1279
58
}
1280
1281
231
std::string normalizeFilename(StringRef Filename) {
1282
231
  llvm::SmallString<256> Path(Filename);
1283
231
  llvm::sys::fs::make_absolute(Path);
1284
231
  llvm::sys::path::remove_dots(Path, /*remove_dot_dot=*/true);
1285
231
  return Path.str().str();
1286
231
}
1287
1288
} // end anonymous namespace
1289
1290
static void dump(llvm::raw_ostream &OS, StringRef FunctionName,
1291
                 ArrayRef<CounterExpression> Expressions,
1292
150
                 ArrayRef<CounterMappingRegion> Regions) {
1293
150
  OS << FunctionName << ":\n";
1294
150
  CounterMappingContext Ctx(Expressions);
1295
1.18k
  for (const auto &R : Regions) {
1296
1.18k
    OS.indent(2);
1297
1.18k
    switch (R.Kind) {
1298
1.18k
    case CounterMappingRegion::CodeRegion:
1299
853
      break;
1300
1.18k
    case CounterMappingRegion::ExpansionRegion:
1301
139
      OS << "Expansion,";
1302
139
      break;
1303
1.18k
    case CounterMappingRegion::SkippedRegion:
1304
9
      OS << "Skipped,";
1305
9
      break;
1306
1.18k
    case CounterMappingRegion::GapRegion:
1307
184
      OS << "Gap,";
1308
184
      break;
1309
1.18k
    }
1310
1.18k
1311
1.18k
    OS << "File " << R.FileID << ", " << R.LineStart << ":" << R.ColumnStart
1312
1.18k
       << " -> " << R.LineEnd << ":" << R.ColumnEnd << " = ";
1313
1.18k
    Ctx.dump(R.Count, OS);
1314
1.18k
    if (R.Kind == CounterMappingRegion::ExpansionRegion)
1315
139
      OS << " (Expanded file = " << R.ExpandedFileID << ")";
1316
1.18k
    OS << "\n";
1317
1.18k
  }
1318
150
}
1319
1320
void CoverageMappingModuleGen::addFunctionMappingRecord(
1321
    llvm::GlobalVariable *NamePtr, StringRef NameValue, uint64_t FuncHash,
1322
178
    const std::string &CoverageMapping, bool IsUsed) {
1323
178
  llvm::LLVMContext &Ctx = CGM.getLLVMContext();
1324
178
  if (!FunctionRecordTy) {
1325
174
#define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) LLVMType,
1326
58
    llvm::Type *FunctionRecordTypes[] = {
1327
58
      #include "llvm/ProfileData/InstrProfData.inc"
1328
58
    };
1329
58
    FunctionRecordTy =
1330
58
        llvm::StructType::get(Ctx, makeArrayRef(FunctionRecordTypes),
1331
58
                              /*isPacked=*/true);
1332
58
  }
1333
178
1334
534
  #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Init,
1335
178
  llvm::Constant *FunctionRecordVals[] = {
1336
178
      #include "llvm/ProfileData/InstrProfData.inc"
1337
178
  };
1338
178
  FunctionRecords.push_back(llvm::ConstantStruct::get(
1339
178
      FunctionRecordTy, makeArrayRef(FunctionRecordVals)));
1340
178
  if (!IsUsed)
1341
17
    FunctionNames.push_back(
1342
17
        llvm::ConstantExpr::getBitCast(NamePtr, llvm::Type::getInt8PtrTy(Ctx)));
1343
178
  CoverageMappings.push_back(CoverageMapping);
1344
178
1345
178
  if (CGM.getCodeGenOpts().DumpCoverageMapping) {
1346
150
    // Dump the coverage mapping data for this function by decoding the
1347
150
    // encoded data. This allows us to dump the mapping regions which were
1348
150
    // also processed by the CoverageMappingWriter which performs
1349
150
    // additional minimization operations such as reducing the number of
1350
150
    // expressions.
1351
150
    std::vector<StringRef> Filenames;
1352
150
    std::vector<CounterExpression> Expressions;
1353
150
    std::vector<CounterMappingRegion> Regions;
1354
150
    llvm::SmallVector<std::string, 16> FilenameStrs;
1355
150
    llvm::SmallVector<StringRef, 16> FilenameRefs;
1356
150
    FilenameStrs.resize(FileEntries.size());
1357
150
    FilenameRefs.resize(FileEntries.size());
1358
165
    for (const auto &Entry : FileEntries) {
1359
165
      auto I = Entry.second;
1360
165
      FilenameStrs[I] = normalizeFilename(Entry.first->getName());
1361
165
      FilenameRefs[I] = FilenameStrs[I];
1362
165
    }
1363
150
    RawCoverageMappingReader Reader(CoverageMapping, FilenameRefs, Filenames,
1364
150
                                    Expressions, Regions);
1365
150
    if (Reader.read())
1366
0
      return;
1367
150
    dump(llvm::outs(), NameValue, Expressions, Regions);
1368
150
  }
1369
178
}
1370
1371
58
void CoverageMappingModuleGen::emit() {
1372
58
  if (FunctionRecords.empty())
1373
0
    return;
1374
58
  llvm::LLVMContext &Ctx = CGM.getLLVMContext();
1375
58
  auto *Int32Ty = llvm::Type::getInt32Ty(Ctx);
1376
58
1377
58
  // Create the filenames and merge them with coverage mappings
1378
58
  llvm::SmallVector<std::string, 16> FilenameStrs;
1379
58
  llvm::SmallVector<StringRef, 16> FilenameRefs;
1380
58
  FilenameStrs.resize(FileEntries.size());
1381
58
  FilenameRefs.resize(FileEntries.size());
1382
66
  for (const auto &Entry : FileEntries) {
1383
66
    auto I = Entry.second;
1384
66
    FilenameStrs[I] = normalizeFilename(Entry.first->getName());
1385
66
    FilenameRefs[I] = FilenameStrs[I];
1386
66
  }
1387
58
1388
58
  std::string FilenamesAndCoverageMappings;
1389
58
  llvm::raw_string_ostream OS(FilenamesAndCoverageMappings);
1390
58
  CoverageFilenamesSectionWriter(FilenameRefs).write(OS);
1391
58
1392
58
  // Stream the content of CoverageMappings to OS while keeping
1393
58
  // memory consumption under control.
1394
58
  size_t CoverageMappingSize = 0;
1395
178
  for (auto &S : CoverageMappings) {
1396
178
    CoverageMappingSize += S.size();
1397
178
    OS << S;
1398
178
    S.clear();
1399
178
    S.shrink_to_fit();
1400
178
  }
1401
58
  CoverageMappings.clear();
1402
58
  CoverageMappings.shrink_to_fit();
1403
58
1404
58
  size_t FilenamesSize = OS.str().size() - CoverageMappingSize;
1405
58
  // Append extra zeroes if necessary to ensure that the size of the filenames
1406
58
  // and coverage mappings is a multiple of 8.
1407
58
  if (size_t Rem = OS.str().size() % 8) {
1408
48
    CoverageMappingSize += 8 - Rem;
1409
48
    OS.write_zeros(8 - Rem);
1410
48
  }
1411
58
  auto *FilenamesAndMappingsVal =
1412
58
      llvm::ConstantDataArray::getString(Ctx, OS.str(), false);
1413
58
1414
58
  // Create the deferred function records array
1415
58
  auto RecordsTy =
1416
58
      llvm::ArrayType::get(FunctionRecordTy, FunctionRecords.size());
1417
58
  auto RecordsVal = llvm::ConstantArray::get(RecordsTy, FunctionRecords);
1418
58
1419
58
  llvm::Type *CovDataHeaderTypes[] = {
1420
232
#define COVMAP_HEADER(Type, LLVMType, Name, Init) LLVMType,
1421
58
#include "llvm/ProfileData/InstrProfData.inc"
1422
58
  };
1423
58
  auto CovDataHeaderTy =
1424
58
      llvm::StructType::get(Ctx, makeArrayRef(CovDataHeaderTypes));
1425
58
  llvm::Constant *CovDataHeaderVals[] = {
1426
232
#define COVMAP_HEADER(Type, LLVMType, Name, Init) Init,
1427
58
#include "llvm/ProfileData/InstrProfData.inc"
1428
58
  };
1429
58
  auto CovDataHeaderVal = llvm::ConstantStruct::get(
1430
58
      CovDataHeaderTy, makeArrayRef(CovDataHeaderVals));
1431
58
1432
58
  // Create the coverage data record
1433
58
  llvm::Type *CovDataTypes[] = {CovDataHeaderTy, RecordsTy,
1434
58
                                FilenamesAndMappingsVal->getType()};
1435
58
  auto CovDataTy = llvm::StructType::get(Ctx, makeArrayRef(CovDataTypes));
1436
58
  llvm::Constant *TUDataVals[] = {CovDataHeaderVal, RecordsVal,
1437
58
                                  FilenamesAndMappingsVal};
1438
58
  auto CovDataVal =
1439
58
      llvm::ConstantStruct::get(CovDataTy, makeArrayRef(TUDataVals));
1440
58
  auto CovData = new llvm::GlobalVariable(
1441
58
      CGM.getModule(), CovDataTy, true, llvm::GlobalValue::InternalLinkage,
1442
58
      CovDataVal, llvm::getCoverageMappingVarName());
1443
58
1444
58
  CovData->setSection(getCoverageSection(CGM));
1445
58
  CovData->setAlignment(8);
1446
58
1447
58
  // Make sure the data doesn't get deleted.
1448
58
  CGM.addUsedGlobal(CovData);
1449
58
  // Create the deferred function records array
1450
58
  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
58
}
1461
1462
317
unsigned CoverageMappingModuleGen::getFileID(const FileEntry *File) {
1463
317
  auto It = FileEntries.find(File);
1464
317
  if (It != FileEntries.end())
1465
251
    return It->second;
1466
66
  unsigned FileID = FileEntries.size();
1467
66
  FileEntries.insert(std::make_pair(File, FileID));
1468
66
  return FileID;
1469
66
}
1470
1471
void CoverageMappingGen::emitCounterMapping(const Decl *D,
1472
162
                                            llvm::raw_ostream &OS) {
1473
162
  assert(CounterMap);
1474
162
  CounterCoverageMappingBuilder Walker(CVM, *CounterMap, SM, LangOpts);
1475
162
  Walker.VisitDecl(D);
1476
162
  Walker.write(OS);
1477
162
}
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
}