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