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