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