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