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