clang  7.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 /// \brief A region of source code that can be mapped to a counter.
39 class SourceMappingRegion {
40  Counter Count;
41 
42  /// \brief The region's starting location.
43  Optional<SourceLocation> LocStart;
44 
45  /// \brief 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 getStartLoc() 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.getStartLoc(), 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 /// \brief 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  /// \brief 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  /// \brief The coverage mapping regions for this function
145  /// \brief The source mapping regions for this function.
146  std::vector<SourceMappingRegion> SourceRegions;
147 
148  /// \brief 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  /// \brief 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  /// \brief 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  /// \brief 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  /// \brief Find out where the current file is included or macro is expanded.
185  SourceLocation getIncludeOrExpansionLoc(SourceLocation Loc) {
186  return Loc.isMacroID() ? SM.getImmediateExpansionRange(Loc).first
187  : SM.getIncludeLoc(SM.getFileID(Loc));
188  }
189 
190  /// \brief 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  /// \brief 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  /// \brief Get the start of \c S ignoring macro arguments and builtin macros.
206  SourceLocation getStart(const Stmt *S) {
207  SourceLocation Loc = S->getLocStart();
208  while (SM.isMacroArgExpansion(Loc) || isInBuiltin(Loc))
209  Loc = SM.getImmediateExpansionRange(Loc).first;
210  return Loc;
211  }
212 
213  /// \brief Get the end of \c S ignoring macro arguments and builtin macros.
214  SourceLocation getEnd(const Stmt *S) {
215  SourceLocation Loc = S->getLocEnd();
216  while (SM.isMacroArgExpansion(Loc) || isInBuiltin(Loc))
217  Loc = SM.getImmediateExpansionRange(Loc).first;
218  return getPreciseTokenLocEnd(Loc);
219  }
220 
221  /// \brief 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.getStartLoc();
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  /// \brief 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  /// \brief 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 souce 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  /// \brief 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.getStartLoc();
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  /// \brief 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 /// \brief 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  /// \brief 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 /// \brief 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  /// \brief The map of statements to count values.
437  llvm::DenseMap<const Stmt *, unsigned> &CounterMap;
438 
439  /// \brief 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  /// \brief 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  /// \brief 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  /// \brief 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  /// \brief 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  /// \brief 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.getStartLoc());
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.getStartLoc() == 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.getStartLoc(), 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  /// \brief 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.getStartLoc();
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.getStartLoc(), 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  /// \brief Return the currently active region.
623  SourceMappingRegion &getRegion() {
624  assert(!RegionStack.empty() && "statement has no region");
625  return RegionStack.back();
626  }
627 
628  /// \brief 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->getLocStart()))
640  MostRecentLocation = EndLoc;
641 
642  return ExitCount;
643  }
644 
645  /// \brief 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.getStartLoc() == StartLoc &&
652  Region.getEndLoc() == EndLoc;
653  });
654  }
655 
656  /// \brief 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  /// \brief 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.getStartLoc();
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  /// \brief 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  /// \brief 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  /// \brief 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  /// \brief 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->getLocStart().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  /// Determine whether the final deferred region emitted in \p Body should be
838  /// discarded.
839  static bool discardFinalDeferredRegionInDecl(Stmt *Body) {
840  if (auto *CS = dyn_cast<CompoundStmt>(Body)) {
841  Stmt *LastStmt = CS->body_back();
842  if (auto *IfElse = dyn_cast<IfStmt>(LastStmt)) {
843  if (auto *Else = dyn_cast_or_null<CompoundStmt>(IfElse->getElse()))
844  LastStmt = Else->body_back();
845  else
846  LastStmt = IfElse->getElse();
847  }
848  return dyn_cast_or_null<ReturnStmt>(LastStmt);
849  }
850  return false;
851  }
852 
853  void VisitDecl(const Decl *D) {
854  assert(!DeferredRegion && "Deferred region never completed");
855 
856  Stmt *Body = D->getBody();
857 
858  // Do not propagate region counts into system headers.
859  if (Body && SM.isInSystemHeader(SM.getSpellingLoc(getStart(Body))))
860  return;
861 
862  Counter ExitCount = propagateCounts(getRegionCounter(Body), Body);
863  assert(RegionStack.empty() && "Regions entered but never exited");
864 
865  if (DeferredRegion) {
866  // Complete (or discard) any deferred regions introduced by the last
867  // statement.
868  if (discardFinalDeferredRegionInDecl(Body))
869  DeferredRegion = None;
870  else
871  popRegions(completeDeferred(ExitCount, getEnd(Body)));
872  }
873  }
874 
875  void VisitReturnStmt(const ReturnStmt *S) {
876  extendRegion(S);
877  if (S->getRetValue())
878  Visit(S->getRetValue());
879  terminateRegion(S);
880  }
881 
882  void VisitCXXThrowExpr(const CXXThrowExpr *E) {
883  extendRegion(E);
884  if (E->getSubExpr())
885  Visit(E->getSubExpr());
886  terminateRegion(E);
887  }
888 
889  void VisitGotoStmt(const GotoStmt *S) { terminateRegion(S); }
890 
891  void VisitLabelStmt(const LabelStmt *S) {
892  Counter LabelCount = getRegionCounter(S);
893  SourceLocation Start = getStart(S);
894  completeTopLevelDeferredRegion(LabelCount, Start);
895  // We can't extendRegion here or we risk overlapping with our new region.
896  handleFileExit(Start);
897  pushRegion(LabelCount, Start);
898  Visit(S->getSubStmt());
899  }
900 
901  void VisitBreakStmt(const BreakStmt *S) {
902  assert(!BreakContinueStack.empty() && "break not in a loop or switch!");
903  BreakContinueStack.back().BreakCount = addCounters(
904  BreakContinueStack.back().BreakCount, getRegion().getCounter());
905  // FIXME: a break in a switch should terminate regions for all preceding
906  // case statements, not just the most recent one.
907  terminateRegion(S);
908  }
909 
910  void VisitContinueStmt(const ContinueStmt *S) {
911  assert(!BreakContinueStack.empty() && "continue stmt not in a loop!");
912  BreakContinueStack.back().ContinueCount = addCounters(
913  BreakContinueStack.back().ContinueCount, getRegion().getCounter());
914  terminateRegion(S);
915  }
916 
917  void VisitCallExpr(const CallExpr *E) {
918  VisitStmt(E);
919 
920  // Terminate the region when we hit a noreturn function.
921  // (This is helpful dealing with switch statements.)
922  QualType CalleeType = E->getCallee()->getType();
923  if (getFunctionExtInfo(*CalleeType).getNoReturn())
924  terminateRegion(E);
925  }
926 
927  void VisitWhileStmt(const WhileStmt *S) {
928  extendRegion(S);
929 
930  Counter ParentCount = getRegion().getCounter();
931  Counter BodyCount = getRegionCounter(S);
932 
933  // Handle the body first so that we can get the backedge count.
934  BreakContinueStack.push_back(BreakContinue());
935  extendRegion(S->getBody());
936  Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
937  BreakContinue BC = BreakContinueStack.pop_back_val();
938 
939  // Go back to handle the condition.
940  Counter CondCount =
941  addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
942  propagateCounts(CondCount, S->getCond());
943  adjustForOutOfOrderTraversal(getEnd(S));
944 
945  // The body count applies to the area immediately after the increment.
946  auto Gap = findGapAreaBetween(S->getCond(), S->getBody());
947  if (Gap)
948  fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
949 
950  Counter OutCount =
951  addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount));
952  if (OutCount != ParentCount)
953  pushRegion(OutCount);
954  }
955 
956  void VisitDoStmt(const DoStmt *S) {
957  extendRegion(S);
958 
959  Counter ParentCount = getRegion().getCounter();
960  Counter BodyCount = getRegionCounter(S);
961 
962  BreakContinueStack.push_back(BreakContinue());
963  extendRegion(S->getBody());
964  Counter BackedgeCount =
965  propagateCounts(addCounters(ParentCount, BodyCount), S->getBody());
966  BreakContinue BC = BreakContinueStack.pop_back_val();
967 
968  Counter CondCount = addCounters(BackedgeCount, BC.ContinueCount);
969  propagateCounts(CondCount, S->getCond());
970 
971  Counter OutCount =
972  addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount));
973  if (OutCount != ParentCount)
974  pushRegion(OutCount);
975  }
976 
977  void VisitForStmt(const ForStmt *S) {
978  extendRegion(S);
979  if (S->getInit())
980  Visit(S->getInit());
981 
982  Counter ParentCount = getRegion().getCounter();
983  Counter BodyCount = getRegionCounter(S);
984 
985  // The loop increment may contain a break or continue.
986  if (S->getInc())
987  BreakContinueStack.emplace_back();
988 
989  // Handle the body first so that we can get the backedge count.
990  BreakContinueStack.emplace_back();
991  extendRegion(S->getBody());
992  Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
993  BreakContinue BodyBC = BreakContinueStack.pop_back_val();
994 
995  // The increment is essentially part of the body but it needs to include
996  // the count for all the continue statements.
997  BreakContinue IncrementBC;
998  if (const Stmt *Inc = S->getInc()) {
999  propagateCounts(addCounters(BackedgeCount, BodyBC.ContinueCount), Inc);
1000  IncrementBC = BreakContinueStack.pop_back_val();
1001  }
1002 
1003  // Go back to handle the condition.
1004  Counter CondCount = addCounters(
1005  addCounters(ParentCount, BackedgeCount, BodyBC.ContinueCount),
1006  IncrementBC.ContinueCount);
1007  if (const Expr *Cond = S->getCond()) {
1008  propagateCounts(CondCount, Cond);
1009  adjustForOutOfOrderTraversal(getEnd(S));
1010  }
1011 
1012  // The body count applies to the area immediately after the increment.
1013  auto Gap = findGapAreaBetween(getPreciseTokenLocEnd(S->getRParenLoc()),
1014  getStart(S->getBody()));
1015  if (Gap)
1016  fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
1017 
1018  Counter OutCount = addCounters(BodyBC.BreakCount, IncrementBC.BreakCount,
1019  subtractCounters(CondCount, BodyCount));
1020  if (OutCount != ParentCount)
1021  pushRegion(OutCount);
1022  }
1023 
1024  void VisitCXXForRangeStmt(const CXXForRangeStmt *S) {
1025  extendRegion(S);
1026  Visit(S->getLoopVarStmt());
1027  Visit(S->getRangeStmt());
1028 
1029  Counter ParentCount = getRegion().getCounter();
1030  Counter BodyCount = getRegionCounter(S);
1031 
1032  BreakContinueStack.push_back(BreakContinue());
1033  extendRegion(S->getBody());
1034  Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
1035  BreakContinue BC = BreakContinueStack.pop_back_val();
1036 
1037  // The body count applies to the area immediately after the range.
1038  auto Gap = findGapAreaBetween(getPreciseTokenLocEnd(S->getRParenLoc()),
1039  getStart(S->getBody()));
1040  if (Gap)
1041  fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
1042 
1043  Counter LoopCount =
1044  addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
1045  Counter OutCount =
1046  addCounters(BC.BreakCount, subtractCounters(LoopCount, BodyCount));
1047  if (OutCount != ParentCount)
1048  pushRegion(OutCount);
1049  }
1050 
1051  void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S) {
1052  extendRegion(S);
1053  Visit(S->getElement());
1054 
1055  Counter ParentCount = getRegion().getCounter();
1056  Counter BodyCount = getRegionCounter(S);
1057 
1058  BreakContinueStack.push_back(BreakContinue());
1059  extendRegion(S->getBody());
1060  Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
1061  BreakContinue BC = BreakContinueStack.pop_back_val();
1062 
1063  // The body count applies to the area immediately after the collection.
1064  auto Gap = findGapAreaBetween(getPreciseTokenLocEnd(S->getRParenLoc()),
1065  getStart(S->getBody()));
1066  if (Gap)
1067  fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
1068 
1069  Counter LoopCount =
1070  addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
1071  Counter OutCount =
1072  addCounters(BC.BreakCount, subtractCounters(LoopCount, BodyCount));
1073  if (OutCount != ParentCount)
1074  pushRegion(OutCount);
1075  }
1076 
1077  void VisitSwitchStmt(const SwitchStmt *S) {
1078  extendRegion(S);
1079  if (S->getInit())
1080  Visit(S->getInit());
1081  Visit(S->getCond());
1082 
1083  BreakContinueStack.push_back(BreakContinue());
1084 
1085  const Stmt *Body = S->getBody();
1086  extendRegion(Body);
1087  if (const auto *CS = dyn_cast<CompoundStmt>(Body)) {
1088  if (!CS->body_empty()) {
1089  // Make a region for the body of the switch. If the body starts with
1090  // a case, that case will reuse this region; otherwise, this covers
1091  // the unreachable code at the beginning of the switch body.
1092  size_t Index =
1093  pushRegion(Counter::getZero(), getStart(CS->body_front()));
1094  for (const auto *Child : CS->children())
1095  Visit(Child);
1096 
1097  // Set the end for the body of the switch, if it isn't already set.
1098  for (size_t i = RegionStack.size(); i != Index; --i) {
1099  if (!RegionStack[i - 1].hasEndLoc())
1100  RegionStack[i - 1].setEndLoc(getEnd(CS->body_back()));
1101  }
1102 
1103  popRegions(Index);
1104  }
1105  } else
1106  propagateCounts(Counter::getZero(), Body);
1107  BreakContinue BC = BreakContinueStack.pop_back_val();
1108 
1109  if (!BreakContinueStack.empty())
1110  BreakContinueStack.back().ContinueCount = addCounters(
1111  BreakContinueStack.back().ContinueCount, BC.ContinueCount);
1112 
1113  Counter ExitCount = getRegionCounter(S);
1114  SourceLocation ExitLoc = getEnd(S);
1115  pushRegion(ExitCount);
1116 
1117  // Ensure that handleFileExit recognizes when the end location is located
1118  // in a different file.
1119  MostRecentLocation = getStart(S);
1120  handleFileExit(ExitLoc);
1121  }
1122 
1123  void VisitSwitchCase(const SwitchCase *S) {
1124  extendRegion(S);
1125 
1126  SourceMappingRegion &Parent = getRegion();
1127 
1128  Counter Count = addCounters(Parent.getCounter(), getRegionCounter(S));
1129  // Reuse the existing region if it starts at our label. This is typical of
1130  // the first case in a switch.
1131  if (Parent.hasStartLoc() && Parent.getStartLoc() == getStart(S))
1132  Parent.setCounter(Count);
1133  else
1134  pushRegion(Count, getStart(S));
1135 
1136  if (const auto *CS = dyn_cast<CaseStmt>(S)) {
1137  Visit(CS->getLHS());
1138  if (const Expr *RHS = CS->getRHS())
1139  Visit(RHS);
1140  }
1141  Visit(S->getSubStmt());
1142  }
1143 
1144  void VisitIfStmt(const IfStmt *S) {
1145  extendRegion(S);
1146  if (S->getInit())
1147  Visit(S->getInit());
1148 
1149  // Extend into the condition before we propagate through it below - this is
1150  // needed to handle macros that generate the "if" but not the condition.
1151  extendRegion(S->getCond());
1152 
1153  Counter ParentCount = getRegion().getCounter();
1154  Counter ThenCount = getRegionCounter(S);
1155 
1156  // Emitting a counter for the condition makes it easier to interpret the
1157  // counter for the body when looking at the coverage.
1158  propagateCounts(ParentCount, S->getCond());
1159 
1160  // The 'then' count applies to the area immediately after the condition.
1161  auto Gap = findGapAreaBetween(S->getCond(), S->getThen());
1162  if (Gap)
1163  fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), ThenCount);
1164 
1165  extendRegion(S->getThen());
1166  Counter OutCount = propagateCounts(ThenCount, S->getThen());
1167 
1168  Counter ElseCount = subtractCounters(ParentCount, ThenCount);
1169  if (const Stmt *Else = S->getElse()) {
1170  // The 'else' count applies to the area immediately after the 'then'.
1171  Gap = findGapAreaBetween(S->getThen(), Else);
1172  if (Gap)
1173  fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), ElseCount);
1174  extendRegion(Else);
1175  OutCount = addCounters(OutCount, propagateCounts(ElseCount, Else));
1176  } else
1177  OutCount = addCounters(OutCount, ElseCount);
1178 
1179  if (OutCount != ParentCount)
1180  pushRegion(OutCount);
1181  }
1182 
1183  void VisitCXXTryStmt(const CXXTryStmt *S) {
1184  extendRegion(S);
1185  // Handle macros that generate the "try" but not the rest.
1186  extendRegion(S->getTryBlock());
1187 
1188  Counter ParentCount = getRegion().getCounter();
1189  propagateCounts(ParentCount, S->getTryBlock());
1190 
1191  for (unsigned I = 0, E = S->getNumHandlers(); I < E; ++I)
1192  Visit(S->getHandler(I));
1193 
1194  Counter ExitCount = getRegionCounter(S);
1195  pushRegion(ExitCount);
1196  }
1197 
1198  void VisitCXXCatchStmt(const CXXCatchStmt *S) {
1199  propagateCounts(getRegionCounter(S), S->getHandlerBlock());
1200  }
1201 
1202  void VisitAbstractConditionalOperator(const AbstractConditionalOperator *E) {
1203  extendRegion(E);
1204 
1205  Counter ParentCount = getRegion().getCounter();
1206  Counter TrueCount = getRegionCounter(E);
1207 
1208  Visit(E->getCond());
1209 
1210  if (!isa<BinaryConditionalOperator>(E)) {
1211  // The 'then' count applies to the area immediately after the condition.
1212  auto Gap =
1213  findGapAreaBetween(E->getQuestionLoc(), getStart(E->getTrueExpr()));
1214  if (Gap)
1215  fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), TrueCount);
1216 
1217  extendRegion(E->getTrueExpr());
1218  propagateCounts(TrueCount, E->getTrueExpr());
1219  }
1220 
1221  extendRegion(E->getFalseExpr());
1222  propagateCounts(subtractCounters(ParentCount, TrueCount),
1223  E->getFalseExpr());
1224  }
1225 
1226  void VisitBinLAnd(const BinaryOperator *E) {
1227  extendRegion(E->getLHS());
1228  propagateCounts(getRegion().getCounter(), E->getLHS());
1229  handleFileExit(getEnd(E->getLHS()));
1230 
1231  extendRegion(E->getRHS());
1232  propagateCounts(getRegionCounter(E), E->getRHS());
1233  }
1234 
1235  void VisitBinLOr(const BinaryOperator *E) {
1236  extendRegion(E->getLHS());
1237  propagateCounts(getRegion().getCounter(), E->getLHS());
1238  handleFileExit(getEnd(E->getLHS()));
1239 
1240  extendRegion(E->getRHS());
1241  propagateCounts(getRegionCounter(E), E->getRHS());
1242  }
1243 
1244  void VisitLambdaExpr(const LambdaExpr *LE) {
1245  // Lambdas are treated as their own functions for now, so we shouldn't
1246  // propagate counts into them.
1247  }
1248 };
1249 
1250 std::string getCoverageSection(const CodeGenModule &CGM) {
1251  return llvm::getInstrProfSectionName(
1252  llvm::IPSK_covmap,
1253  CGM.getContext().getTargetInfo().getTriple().getObjectFormat());
1254 }
1255 
1256 std::string normalizeFilename(StringRef Filename) {
1257  llvm::SmallString<256> Path(Filename);
1258  llvm::sys::fs::make_absolute(Path);
1259  llvm::sys::path::remove_dots(Path, /*remove_dot_dots=*/true);
1260  return Path.str().str();
1261 }
1262 
1263 } // end anonymous namespace
1264 
1265 static void dump(llvm::raw_ostream &OS, StringRef FunctionName,
1266  ArrayRef<CounterExpression> Expressions,
1268  OS << FunctionName << ":\n";
1269  CounterMappingContext Ctx(Expressions);
1270  for (const auto &R : Regions) {
1271  OS.indent(2);
1272  switch (R.Kind) {
1273  case CounterMappingRegion::CodeRegion:
1274  break;
1275  case CounterMappingRegion::ExpansionRegion:
1276  OS << "Expansion,";
1277  break;
1278  case CounterMappingRegion::SkippedRegion:
1279  OS << "Skipped,";
1280  break;
1281  case CounterMappingRegion::GapRegion:
1282  OS << "Gap,";
1283  break;
1284  }
1285 
1286  OS << "File " << R.FileID << ", " << R.LineStart << ":" << R.ColumnStart
1287  << " -> " << R.LineEnd << ":" << R.ColumnEnd << " = ";
1288  Ctx.dump(R.Count, OS);
1289  if (R.Kind == CounterMappingRegion::ExpansionRegion)
1290  OS << " (Expanded file = " << R.ExpandedFileID << ")";
1291  OS << "\n";
1292  }
1293 }
1294 
1296  llvm::GlobalVariable *NamePtr, StringRef NameValue, uint64_t FuncHash,
1297  const std::string &CoverageMapping, bool IsUsed) {
1298  llvm::LLVMContext &Ctx = CGM.getLLVMContext();
1299  if (!FunctionRecordTy) {
1300 #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) LLVMType,
1301  llvm::Type *FunctionRecordTypes[] = {
1302  #include "llvm/ProfileData/InstrProfData.inc"
1303  };
1304  FunctionRecordTy =
1305  llvm::StructType::get(Ctx, makeArrayRef(FunctionRecordTypes),
1306  /*isPacked=*/true);
1307  }
1308 
1309  #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Init,
1310  llvm::Constant *FunctionRecordVals[] = {
1311  #include "llvm/ProfileData/InstrProfData.inc"
1312  };
1313  FunctionRecords.push_back(llvm::ConstantStruct::get(
1314  FunctionRecordTy, makeArrayRef(FunctionRecordVals)));
1315  if (!IsUsed)
1316  FunctionNames.push_back(
1317  llvm::ConstantExpr::getBitCast(NamePtr, llvm::Type::getInt8PtrTy(Ctx)));
1318  CoverageMappings.push_back(CoverageMapping);
1319 
1320  if (CGM.getCodeGenOpts().DumpCoverageMapping) {
1321  // Dump the coverage mapping data for this function by decoding the
1322  // encoded data. This allows us to dump the mapping regions which were
1323  // also processed by the CoverageMappingWriter which performs
1324  // additional minimization operations such as reducing the number of
1325  // expressions.
1326  std::vector<StringRef> Filenames;
1327  std::vector<CounterExpression> Expressions;
1328  std::vector<CounterMappingRegion> Regions;
1330  llvm::SmallVector<StringRef, 16> FilenameRefs;
1331  FilenameStrs.resize(FileEntries.size());
1332  FilenameRefs.resize(FileEntries.size());
1333  for (const auto &Entry : FileEntries) {
1334  auto I = Entry.second;
1335  FilenameStrs[I] = normalizeFilename(Entry.first->getName());
1336  FilenameRefs[I] = FilenameStrs[I];
1337  }
1338  RawCoverageMappingReader Reader(CoverageMapping, FilenameRefs, Filenames,
1339  Expressions, Regions);
1340  if (Reader.read())
1341  return;
1342  dump(llvm::outs(), NameValue, Expressions, Regions);
1343  }
1344 }
1345 
1347  if (FunctionRecords.empty())
1348  return;
1349  llvm::LLVMContext &Ctx = CGM.getLLVMContext();
1350  auto *Int32Ty = llvm::Type::getInt32Ty(Ctx);
1351 
1352  // Create the filenames and merge them with coverage mappings
1354  llvm::SmallVector<StringRef, 16> FilenameRefs;
1355  FilenameStrs.resize(FileEntries.size());
1356  FilenameRefs.resize(FileEntries.size());
1357  for (const auto &Entry : FileEntries) {
1358  auto I = Entry.second;
1359  FilenameStrs[I] = normalizeFilename(Entry.first->getName());
1360  FilenameRefs[I] = FilenameStrs[I];
1361  }
1362 
1363  std::string FilenamesAndCoverageMappings;
1364  llvm::raw_string_ostream OS(FilenamesAndCoverageMappings);
1365  CoverageFilenamesSectionWriter(FilenameRefs).write(OS);
1366  std::string RawCoverageMappings =
1367  llvm::join(CoverageMappings.begin(), CoverageMappings.end(), "");
1368  OS << RawCoverageMappings;
1369  size_t CoverageMappingSize = RawCoverageMappings.size();
1370  size_t FilenamesSize = OS.str().size() - CoverageMappingSize;
1371  // Append extra zeroes if necessary to ensure that the size of the filenames
1372  // and coverage mappings is a multiple of 8.
1373  if (size_t Rem = OS.str().size() % 8) {
1374  CoverageMappingSize += 8 - Rem;
1375  for (size_t I = 0, S = 8 - Rem; I < S; ++I)
1376  OS << '\0';
1377  }
1378  auto *FilenamesAndMappingsVal =
1379  llvm::ConstantDataArray::getString(Ctx, OS.str(), false);
1380 
1381  // Create the deferred function records array
1382  auto RecordsTy =
1383  llvm::ArrayType::get(FunctionRecordTy, FunctionRecords.size());
1384  auto RecordsVal = llvm::ConstantArray::get(RecordsTy, FunctionRecords);
1385 
1386  llvm::Type *CovDataHeaderTypes[] = {
1387 #define COVMAP_HEADER(Type, LLVMType, Name, Init) LLVMType,
1388 #include "llvm/ProfileData/InstrProfData.inc"
1389  };
1390  auto CovDataHeaderTy =
1391  llvm::StructType::get(Ctx, makeArrayRef(CovDataHeaderTypes));
1392  llvm::Constant *CovDataHeaderVals[] = {
1393 #define COVMAP_HEADER(Type, LLVMType, Name, Init) Init,
1394 #include "llvm/ProfileData/InstrProfData.inc"
1395  };
1396  auto CovDataHeaderVal = llvm::ConstantStruct::get(
1397  CovDataHeaderTy, makeArrayRef(CovDataHeaderVals));
1398 
1399  // Create the coverage data record
1400  llvm::Type *CovDataTypes[] = {CovDataHeaderTy, RecordsTy,
1401  FilenamesAndMappingsVal->getType()};
1402  auto CovDataTy = llvm::StructType::get(Ctx, makeArrayRef(CovDataTypes));
1403  llvm::Constant *TUDataVals[] = {CovDataHeaderVal, RecordsVal,
1404  FilenamesAndMappingsVal};
1405  auto CovDataVal =
1406  llvm::ConstantStruct::get(CovDataTy, makeArrayRef(TUDataVals));
1407  auto CovData = new llvm::GlobalVariable(
1408  CGM.getModule(), CovDataTy, true, llvm::GlobalValue::InternalLinkage,
1409  CovDataVal, llvm::getCoverageMappingVarName());
1410 
1411  CovData->setSection(getCoverageSection(CGM));
1412  CovData->setAlignment(8);
1413 
1414  // Make sure the data doesn't get deleted.
1415  CGM.addUsedGlobal(CovData);
1416  // Create the deferred function records array
1417  if (!FunctionNames.empty()) {
1418  auto NamesArrTy = llvm::ArrayType::get(llvm::Type::getInt8PtrTy(Ctx),
1419  FunctionNames.size());
1420  auto NamesArrVal = llvm::ConstantArray::get(NamesArrTy, FunctionNames);
1421  // This variable will *NOT* be emitted to the object file. It is used
1422  // to pass the list of names referenced to codegen.
1423  new llvm::GlobalVariable(CGM.getModule(), NamesArrTy, true,
1425  llvm::getCoverageUnusedNamesVarName());
1426  }
1427 }
1428 
1430  auto It = FileEntries.find(File);
1431  if (It != FileEntries.end())
1432  return It->second;
1433  unsigned FileID = FileEntries.size();
1434  FileEntries.insert(std::make_pair(File, FileID));
1435  return FileID;
1436 }
1437 
1439  llvm::raw_ostream &OS) {
1440  assert(CounterMap);
1441  CounterCoverageMappingBuilder Walker(CVM, *CounterMap, SM, LangOpts);
1442  Walker.VisitDecl(D);
1443  Walker.write(OS);
1444 }
1445 
1447  llvm::raw_ostream &OS) {
1448  EmptyCoverageMappingBuilder Walker(CVM, SM, LangOpts);
1449  Walker.VisitDecl(D);
1450  Walker.write(OS);
1451 }
Expr * getInc()
Definition: Stmt.h:1241
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:973
SourceLocation getLocWithOffset(int Offset) const
Return a source location with the specified offset from this SourceLocation.
A (possibly-)qualified type.
Definition: Type.h:653
const Expr * getSubExpr() const
Definition: ExprCXX.h:1007
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:1131
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:978
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:933
const llvm::Triple & getTriple() const
Returns the target triple of the primary target.
Definition: TargetInfo.h:790
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: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:671
A C++ throw-expression (C++ [except.throw]).
Definition: ExprCXX.h:985
void emit()
Emit the coverage mapping data for a translation unit.
LabelStmt - Represents a label, which has a substatement.
Definition: Stmt.h:842
Stmt * getBody()
Definition: Stmt.h:1179
const Expr * getRetValue() const
Definition: Stmt.cpp:928
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:3271
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:1207
static void dump(llvm::raw_ostream &OS, StringRef FunctionName, ArrayRef< CounterExpression > Expressions, ArrayRef< CounterMappingRegion > Regions)
SourceLocation getRParenLoc() const
Definition: StmtCXX.h:196
Stmt * getBody()
Definition: Stmt.h:1242
child_range children()
Definition: Stmt.cpp:226
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:2998
Stmt * getInit()
Definition: Stmt.h:1221
CXXForRangeStmt - This represents C++0x [stmt.ranged]&#39;s ranged for statement, represented as &#39;for (ra...
Definition: StmtCXX.h:128
unsigned getSpellingLineNumber(SourceLocation Loc, bool *Invalid=nullptr) const
Expr * getCond()
Definition: Stmt.h:1240
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:1583
bool getNoReturn() const
Definition: Type.h:3132
unsigned getFileIDSize(FileID FID) const
The size of the SLocEntry that FID represents.
Stmt * getInit()
Definition: Stmt.h:966
NodeId Parent
Definition: ASTDiff.cpp:192
SourceLocation getLocEnd() const LLVM_READONLY
Definition: Stmt.cpp:290
StringRef Filename
Definition: Format.cpp:1522
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:971
const Expr * getCallee() const
Definition: Expr.h:2258
Stmt * getBody()
Definition: Stmt.h:1134
CXXTryStmt - A C++ try block, including all handlers.
Definition: StmtCXX.h:65
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.
ReturnStmt - This represents a return, optionally of an expression: return; return 4;...
Definition: Stmt.h:1417
ASTContext & getContext() const
const SourceManager & SM
Definition: Format.cpp:1412
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:1158
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:984
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.
std::pair< SourceLocation, SourceLocation > getImmediateExpansionRange(SourceLocation Loc) const
Return the start/end of the expansion information for an expansion location.
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:3042
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:5849
const Stmt * getBody() const
Definition: Stmt.h:1050
SwitchStmt - This represents a &#39;switch&#39; stmt.
Definition: Stmt.h:1011
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:3240
Stmt * getInit()
Definition: Stmt.h:1046
Internal linkage, which indicates that the entity can be referred to from within the translation unit...
Definition: Linkage.h:33
Stmt * getSubStmt()
Definition: Stmt.cpp:885
SourceLocation getRParenLoc() const
Definition: Stmt.h:1258
DeclStmt * getRangeStmt()
Definition: StmtCXX.h:154
GotoStmt - This represents a direct goto.
Definition: Stmt.h:1278
Expr * getCond()
Definition: Stmt.h:1176
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:1355
CXXCatchStmt - This represents a C++ catch block.
Definition: StmtCXX.h:29
WhileStmt - This represents a &#39;while&#39; stmt.
Definition: Stmt.h:1102
CompoundStmt * getTryBlock()
Definition: StmtCXX.h:96
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2218
__DEVICE__ int max(int __a, int __b)
Expr * getRHS() const
Definition: Expr.h:3044
BreakStmt - This represents a break.
Definition: Stmt.h:1381
__DEVICE__ int min(int __a, int __b)
Stmt * getSubStmt()
Definition: Stmt.h:862
DeclStmt * getLoopVarStmt()
Definition: StmtCXX.h:161
const Expr * getCond() const
Definition: Stmt.h:969
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:1049
SourceLocation getLocStart() const LLVM_READONLY
Definition: Stmt.cpp:277
This class handles loading and caching of source files into memory.