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  Visit(S->getLoopVarStmt());
1008  Visit(S->getRangeStmt());
1009 
1010  Counter ParentCount = getRegion().getCounter();
1011  Counter BodyCount = getRegionCounter(S);
1012 
1013  BreakContinueStack.push_back(BreakContinue());
1014  extendRegion(S->getBody());
1015  Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
1016  BreakContinue BC = BreakContinueStack.pop_back_val();
1017 
1018  // The body count applies to the area immediately after the range.
1019  auto Gap = findGapAreaBetween(getPreciseTokenLocEnd(S->getRParenLoc()),
1020  getStart(S->getBody()));
1021  if (Gap)
1022  fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
1023 
1024  Counter LoopCount =
1025  addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
1026  Counter OutCount =
1027  addCounters(BC.BreakCount, subtractCounters(LoopCount, BodyCount));
1028  if (OutCount != ParentCount)
1029  pushRegion(OutCount);
1030  }
1031 
1032  void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S) {
1033  extendRegion(S);
1034  Visit(S->getElement());
1035 
1036  Counter ParentCount = getRegion().getCounter();
1037  Counter BodyCount = getRegionCounter(S);
1038 
1039  BreakContinueStack.push_back(BreakContinue());
1040  extendRegion(S->getBody());
1041  Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
1042  BreakContinue BC = BreakContinueStack.pop_back_val();
1043 
1044  // The body count applies to the area immediately after the collection.
1045  auto Gap = findGapAreaBetween(getPreciseTokenLocEnd(S->getRParenLoc()),
1046  getStart(S->getBody()));
1047  if (Gap)
1048  fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
1049 
1050  Counter LoopCount =
1051  addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
1052  Counter OutCount =
1053  addCounters(BC.BreakCount, subtractCounters(LoopCount, BodyCount));
1054  if (OutCount != ParentCount)
1055  pushRegion(OutCount);
1056  }
1057 
1058  void VisitSwitchStmt(const SwitchStmt *S) {
1059  extendRegion(S);
1060  if (S->getInit())
1061  Visit(S->getInit());
1062  Visit(S->getCond());
1063 
1064  BreakContinueStack.push_back(BreakContinue());
1065 
1066  const Stmt *Body = S->getBody();
1067  extendRegion(Body);
1068  if (const auto *CS = dyn_cast<CompoundStmt>(Body)) {
1069  if (!CS->body_empty()) {
1070  // Make a region for the body of the switch. If the body starts with
1071  // a case, that case will reuse this region; otherwise, this covers
1072  // the unreachable code at the beginning of the switch body.
1073  size_t Index =
1074  pushRegion(Counter::getZero(), getStart(CS->body_front()));
1075  for (const auto *Child : CS->children())
1076  Visit(Child);
1077 
1078  // Set the end for the body of the switch, if it isn't already set.
1079  for (size_t i = RegionStack.size(); i != Index; --i) {
1080  if (!RegionStack[i - 1].hasEndLoc())
1081  RegionStack[i - 1].setEndLoc(getEnd(CS->body_back()));
1082  }
1083 
1084  popRegions(Index);
1085  }
1086  } else
1087  propagateCounts(Counter::getZero(), Body);
1088  BreakContinue BC = BreakContinueStack.pop_back_val();
1089 
1090  if (!BreakContinueStack.empty())
1091  BreakContinueStack.back().ContinueCount = addCounters(
1092  BreakContinueStack.back().ContinueCount, BC.ContinueCount);
1093 
1094  Counter ExitCount = getRegionCounter(S);
1095  SourceLocation ExitLoc = getEnd(S);
1096  pushRegion(ExitCount);
1097 
1098  // Ensure that handleFileExit recognizes when the end location is located
1099  // in a different file.
1100  MostRecentLocation = getStart(S);
1101  handleFileExit(ExitLoc);
1102  }
1103 
1104  void VisitSwitchCase(const SwitchCase *S) {
1105  extendRegion(S);
1106 
1107  SourceMappingRegion &Parent = getRegion();
1108 
1109  Counter Count = addCounters(Parent.getCounter(), getRegionCounter(S));
1110  // Reuse the existing region if it starts at our label. This is typical of
1111  // the first case in a switch.
1112  if (Parent.hasStartLoc() && Parent.getBeginLoc() == getStart(S))
1113  Parent.setCounter(Count);
1114  else
1115  pushRegion(Count, getStart(S));
1116 
1117  if (const auto *CS = dyn_cast<CaseStmt>(S)) {
1118  Visit(CS->getLHS());
1119  if (const Expr *RHS = CS->getRHS())
1120  Visit(RHS);
1121  }
1122  Visit(S->getSubStmt());
1123  }
1124 
1125  void VisitIfStmt(const IfStmt *S) {
1126  extendRegion(S);
1127  if (S->getInit())
1128  Visit(S->getInit());
1129 
1130  // Extend into the condition before we propagate through it below - this is
1131  // needed to handle macros that generate the "if" but not the condition.
1132  extendRegion(S->getCond());
1133 
1134  Counter ParentCount = getRegion().getCounter();
1135  Counter ThenCount = getRegionCounter(S);
1136 
1137  // Emitting a counter for the condition makes it easier to interpret the
1138  // counter for the body when looking at the coverage.
1139  propagateCounts(ParentCount, S->getCond());
1140 
1141  // The 'then' count applies to the area immediately after the condition.
1142  auto Gap = findGapAreaBetween(S->getCond(), S->getThen());
1143  if (Gap)
1144  fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), ThenCount);
1145 
1146  extendRegion(S->getThen());
1147  Counter OutCount = propagateCounts(ThenCount, S->getThen());
1148 
1149  Counter ElseCount = subtractCounters(ParentCount, ThenCount);
1150  if (const Stmt *Else = S->getElse()) {
1151  // The 'else' count applies to the area immediately after the 'then'.
1152  Gap = findGapAreaBetween(S->getThen(), Else);
1153  if (Gap)
1154  fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), ElseCount);
1155  extendRegion(Else);
1156  OutCount = addCounters(OutCount, propagateCounts(ElseCount, Else));
1157  } else
1158  OutCount = addCounters(OutCount, ElseCount);
1159 
1160  if (OutCount != ParentCount)
1161  pushRegion(OutCount);
1162  }
1163 
1164  void VisitCXXTryStmt(const CXXTryStmt *S) {
1165  extendRegion(S);
1166  // Handle macros that generate the "try" but not the rest.
1167  extendRegion(S->getTryBlock());
1168 
1169  Counter ParentCount = getRegion().getCounter();
1170  propagateCounts(ParentCount, S->getTryBlock());
1171 
1172  for (unsigned I = 0, E = S->getNumHandlers(); I < E; ++I)
1173  Visit(S->getHandler(I));
1174 
1175  Counter ExitCount = getRegionCounter(S);
1176  pushRegion(ExitCount);
1177  }
1178 
1179  void VisitCXXCatchStmt(const CXXCatchStmt *S) {
1180  propagateCounts(getRegionCounter(S), S->getHandlerBlock());
1181  }
1182 
1183  void VisitAbstractConditionalOperator(const AbstractConditionalOperator *E) {
1184  extendRegion(E);
1185 
1186  Counter ParentCount = getRegion().getCounter();
1187  Counter TrueCount = getRegionCounter(E);
1188 
1189  Visit(E->getCond());
1190 
1191  if (!isa<BinaryConditionalOperator>(E)) {
1192  // The 'then' count applies to the area immediately after the condition.
1193  auto Gap =
1194  findGapAreaBetween(E->getQuestionLoc(), getStart(E->getTrueExpr()));
1195  if (Gap)
1196  fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), TrueCount);
1197 
1198  extendRegion(E->getTrueExpr());
1199  propagateCounts(TrueCount, E->getTrueExpr());
1200  }
1201 
1202  extendRegion(E->getFalseExpr());
1203  propagateCounts(subtractCounters(ParentCount, TrueCount),
1204  E->getFalseExpr());
1205  }
1206 
1207  void VisitBinLAnd(const BinaryOperator *E) {
1208  extendRegion(E->getLHS());
1209  propagateCounts(getRegion().getCounter(), E->getLHS());
1210  handleFileExit(getEnd(E->getLHS()));
1211 
1212  extendRegion(E->getRHS());
1213  propagateCounts(getRegionCounter(E), E->getRHS());
1214  }
1215 
1216  void VisitBinLOr(const BinaryOperator *E) {
1217  extendRegion(E->getLHS());
1218  propagateCounts(getRegion().getCounter(), E->getLHS());
1219  handleFileExit(getEnd(E->getLHS()));
1220 
1221  extendRegion(E->getRHS());
1222  propagateCounts(getRegionCounter(E), E->getRHS());
1223  }
1224 
1225  void VisitLambdaExpr(const LambdaExpr *LE) {
1226  // Lambdas are treated as their own functions for now, so we shouldn't
1227  // propagate counts into them.
1228  }
1229 };
1230 
1231 std::string getCoverageSection(const CodeGenModule &CGM) {
1232  return llvm::getInstrProfSectionName(
1233  llvm::IPSK_covmap,
1234  CGM.getContext().getTargetInfo().getTriple().getObjectFormat());
1235 }
1236 
1237 std::string normalizeFilename(StringRef Filename) {
1238  llvm::SmallString<256> Path(Filename);
1239  llvm::sys::fs::make_absolute(Path);
1240  llvm::sys::path::remove_dots(Path, /*remove_dot_dots=*/true);
1241  return Path.str().str();
1242 }
1243 
1244 } // end anonymous namespace
1245 
1246 static void dump(llvm::raw_ostream &OS, StringRef FunctionName,
1247  ArrayRef<CounterExpression> Expressions,
1249  OS << FunctionName << ":\n";
1250  CounterMappingContext Ctx(Expressions);
1251  for (const auto &R : Regions) {
1252  OS.indent(2);
1253  switch (R.Kind) {
1254  case CounterMappingRegion::CodeRegion:
1255  break;
1256  case CounterMappingRegion::ExpansionRegion:
1257  OS << "Expansion,";
1258  break;
1259  case CounterMappingRegion::SkippedRegion:
1260  OS << "Skipped,";
1261  break;
1262  case CounterMappingRegion::GapRegion:
1263  OS << "Gap,";
1264  break;
1265  }
1266 
1267  OS << "File " << R.FileID << ", " << R.LineStart << ":" << R.ColumnStart
1268  << " -> " << R.LineEnd << ":" << R.ColumnEnd << " = ";
1269  Ctx.dump(R.Count, OS);
1270  if (R.Kind == CounterMappingRegion::ExpansionRegion)
1271  OS << " (Expanded file = " << R.ExpandedFileID << ")";
1272  OS << "\n";
1273  }
1274 }
1275 
1277  llvm::GlobalVariable *NamePtr, StringRef NameValue, uint64_t FuncHash,
1278  const std::string &CoverageMapping, bool IsUsed) {
1279  llvm::LLVMContext &Ctx = CGM.getLLVMContext();
1280  if (!FunctionRecordTy) {
1281 #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) LLVMType,
1282  llvm::Type *FunctionRecordTypes[] = {
1283  #include "llvm/ProfileData/InstrProfData.inc"
1284  };
1285  FunctionRecordTy =
1286  llvm::StructType::get(Ctx, makeArrayRef(FunctionRecordTypes),
1287  /*isPacked=*/true);
1288  }
1289 
1290  #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Init,
1291  llvm::Constant *FunctionRecordVals[] = {
1292  #include "llvm/ProfileData/InstrProfData.inc"
1293  };
1294  FunctionRecords.push_back(llvm::ConstantStruct::get(
1295  FunctionRecordTy, makeArrayRef(FunctionRecordVals)));
1296  if (!IsUsed)
1297  FunctionNames.push_back(
1298  llvm::ConstantExpr::getBitCast(NamePtr, llvm::Type::getInt8PtrTy(Ctx)));
1299  CoverageMappings.push_back(CoverageMapping);
1300 
1301  if (CGM.getCodeGenOpts().DumpCoverageMapping) {
1302  // Dump the coverage mapping data for this function by decoding the
1303  // encoded data. This allows us to dump the mapping regions which were
1304  // also processed by the CoverageMappingWriter which performs
1305  // additional minimization operations such as reducing the number of
1306  // expressions.
1307  std::vector<StringRef> Filenames;
1308  std::vector<CounterExpression> Expressions;
1309  std::vector<CounterMappingRegion> Regions;
1311  llvm::SmallVector<StringRef, 16> FilenameRefs;
1312  FilenameStrs.resize(FileEntries.size());
1313  FilenameRefs.resize(FileEntries.size());
1314  for (const auto &Entry : FileEntries) {
1315  auto I = Entry.second;
1316  FilenameStrs[I] = normalizeFilename(Entry.first->getName());
1317  FilenameRefs[I] = FilenameStrs[I];
1318  }
1319  RawCoverageMappingReader Reader(CoverageMapping, FilenameRefs, Filenames,
1320  Expressions, Regions);
1321  if (Reader.read())
1322  return;
1323  dump(llvm::outs(), NameValue, Expressions, Regions);
1324  }
1325 }
1326 
1328  if (FunctionRecords.empty())
1329  return;
1330  llvm::LLVMContext &Ctx = CGM.getLLVMContext();
1331  auto *Int32Ty = llvm::Type::getInt32Ty(Ctx);
1332 
1333  // Create the filenames and merge them with coverage mappings
1335  llvm::SmallVector<StringRef, 16> FilenameRefs;
1336  FilenameStrs.resize(FileEntries.size());
1337  FilenameRefs.resize(FileEntries.size());
1338  for (const auto &Entry : FileEntries) {
1339  auto I = Entry.second;
1340  FilenameStrs[I] = normalizeFilename(Entry.first->getName());
1341  FilenameRefs[I] = FilenameStrs[I];
1342  }
1343 
1344  std::string FilenamesAndCoverageMappings;
1345  llvm::raw_string_ostream OS(FilenamesAndCoverageMappings);
1346  CoverageFilenamesSectionWriter(FilenameRefs).write(OS);
1347  std::string RawCoverageMappings =
1348  llvm::join(CoverageMappings.begin(), CoverageMappings.end(), "");
1349  OS << RawCoverageMappings;
1350  size_t CoverageMappingSize = RawCoverageMappings.size();
1351  size_t FilenamesSize = OS.str().size() - CoverageMappingSize;
1352  // Append extra zeroes if necessary to ensure that the size of the filenames
1353  // and coverage mappings is a multiple of 8.
1354  if (size_t Rem = OS.str().size() % 8) {
1355  CoverageMappingSize += 8 - Rem;
1356  OS.write_zeros(8 - Rem);
1357  }
1358  auto *FilenamesAndMappingsVal =
1359  llvm::ConstantDataArray::getString(Ctx, OS.str(), false);
1360 
1361  // Create the deferred function records array
1362  auto RecordsTy =
1363  llvm::ArrayType::get(FunctionRecordTy, FunctionRecords.size());
1364  auto RecordsVal = llvm::ConstantArray::get(RecordsTy, FunctionRecords);
1365 
1366  llvm::Type *CovDataHeaderTypes[] = {
1367 #define COVMAP_HEADER(Type, LLVMType, Name, Init) LLVMType,
1368 #include "llvm/ProfileData/InstrProfData.inc"
1369  };
1370  auto CovDataHeaderTy =
1371  llvm::StructType::get(Ctx, makeArrayRef(CovDataHeaderTypes));
1372  llvm::Constant *CovDataHeaderVals[] = {
1373 #define COVMAP_HEADER(Type, LLVMType, Name, Init) Init,
1374 #include "llvm/ProfileData/InstrProfData.inc"
1375  };
1376  auto CovDataHeaderVal = llvm::ConstantStruct::get(
1377  CovDataHeaderTy, makeArrayRef(CovDataHeaderVals));
1378 
1379  // Create the coverage data record
1380  llvm::Type *CovDataTypes[] = {CovDataHeaderTy, RecordsTy,
1381  FilenamesAndMappingsVal->getType()};
1382  auto CovDataTy = llvm::StructType::get(Ctx, makeArrayRef(CovDataTypes));
1383  llvm::Constant *TUDataVals[] = {CovDataHeaderVal, RecordsVal,
1384  FilenamesAndMappingsVal};
1385  auto CovDataVal =
1386  llvm::ConstantStruct::get(CovDataTy, makeArrayRef(TUDataVals));
1387  auto CovData = new llvm::GlobalVariable(
1388  CGM.getModule(), CovDataTy, true, llvm::GlobalValue::InternalLinkage,
1389  CovDataVal, llvm::getCoverageMappingVarName());
1390 
1391  CovData->setSection(getCoverageSection(CGM));
1392  CovData->setAlignment(8);
1393 
1394  // Make sure the data doesn't get deleted.
1395  CGM.addUsedGlobal(CovData);
1396  // Create the deferred function records array
1397  if (!FunctionNames.empty()) {
1398  auto NamesArrTy = llvm::ArrayType::get(llvm::Type::getInt8PtrTy(Ctx),
1399  FunctionNames.size());
1400  auto NamesArrVal = llvm::ConstantArray::get(NamesArrTy, FunctionNames);
1401  // This variable will *NOT* be emitted to the object file. It is used
1402  // to pass the list of names referenced to codegen.
1403  new llvm::GlobalVariable(CGM.getModule(), NamesArrTy, true,
1405  llvm::getCoverageUnusedNamesVarName());
1406  }
1407 }
1408 
1410  auto It = FileEntries.find(File);
1411  if (It != FileEntries.end())
1412  return It->second;
1413  unsigned FileID = FileEntries.size();
1414  FileEntries.insert(std::make_pair(File, FileID));
1415  return FileID;
1416 }
1417 
1419  llvm::raw_ostream &OS) {
1420  assert(CounterMap);
1421  CounterCoverageMappingBuilder Walker(CVM, *CounterMap, SM, LangOpts);
1422  Walker.VisitDecl(D);
1423  Walker.write(OS);
1424 }
1425 
1427  llvm::raw_ostream &OS) {
1428  EmptyCoverageMappingBuilder Walker(CVM, SM, LangOpts);
1429  Walker.VisitDecl(D);
1430  Walker.write(OS);
1431 }
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:985
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:3381
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:194
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:3102
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:126
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:3400
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:1602
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:2325
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:1472
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:991
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:59
CoverageSourceInfo & getSourceInfo() const
Expr * getLHS() const
Definition: Expr.h:3146
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:6078
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:3350
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:152
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:2285
__DEVICE__ int max(int __a, int __b)
Expr * getRHS() const
Definition: Expr.h:3148
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:159
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.