clang  10.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  llvm::stable_sort(FileLocs, 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 } // end anonymous namespace
1282 
1283 static void dump(llvm::raw_ostream &OS, StringRef FunctionName,
1284  ArrayRef<CounterExpression> Expressions,
1286  OS << FunctionName << ":\n";
1287  CounterMappingContext Ctx(Expressions);
1288  for (const auto &R : Regions) {
1289  OS.indent(2);
1290  switch (R.Kind) {
1291  case CounterMappingRegion::CodeRegion:
1292  break;
1293  case CounterMappingRegion::ExpansionRegion:
1294  OS << "Expansion,";
1295  break;
1296  case CounterMappingRegion::SkippedRegion:
1297  OS << "Skipped,";
1298  break;
1299  case CounterMappingRegion::GapRegion:
1300  OS << "Gap,";
1301  break;
1302  }
1303 
1304  OS << "File " << R.FileID << ", " << R.LineStart << ":" << R.ColumnStart
1305  << " -> " << R.LineEnd << ":" << R.ColumnEnd << " = ";
1306  Ctx.dump(R.Count, OS);
1307  if (R.Kind == CounterMappingRegion::ExpansionRegion)
1308  OS << " (Expanded file = " << R.ExpandedFileID << ")";
1309  OS << "\n";
1310  }
1311 }
1312 
1314  CodeGenModule &CGM, CoverageSourceInfo &SourceInfo)
1315  : CGM(CGM), SourceInfo(SourceInfo), FunctionRecordTy(nullptr) {
1316  // Honor -fdebug-compilation-dir in paths in coverage data. Otherwise, use the
1317  // regular working directory when normalizing paths.
1318  if (!CGM.getCodeGenOpts().DebugCompilationDir.empty())
1319  CWD = CGM.getCodeGenOpts().DebugCompilationDir;
1320  else
1321  llvm::sys::fs::current_path(CWD);
1322 }
1323 
1324 std::string CoverageMappingModuleGen::normalizeFilename(StringRef Filename) {
1325  llvm::SmallString<256> Path(Filename);
1326  llvm::sys::fs::make_absolute(CWD, Path);
1327  llvm::sys::path::remove_dots(Path, /*remove_dot_dot=*/true);
1328  return Path.str().str();
1329 }
1330 
1332  llvm::GlobalVariable *NamePtr, StringRef NameValue, uint64_t FuncHash,
1333  const std::string &CoverageMapping, bool IsUsed) {
1334  llvm::LLVMContext &Ctx = CGM.getLLVMContext();
1335  if (!FunctionRecordTy) {
1336 #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) LLVMType,
1337  llvm::Type *FunctionRecordTypes[] = {
1338  #include "llvm/ProfileData/InstrProfData.inc"
1339  };
1340  FunctionRecordTy =
1341  llvm::StructType::get(Ctx, makeArrayRef(FunctionRecordTypes),
1342  /*isPacked=*/true);
1343  }
1344 
1345  #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Init,
1346  llvm::Constant *FunctionRecordVals[] = {
1347  #include "llvm/ProfileData/InstrProfData.inc"
1348  };
1349  FunctionRecords.push_back(llvm::ConstantStruct::get(
1350  FunctionRecordTy, makeArrayRef(FunctionRecordVals)));
1351  if (!IsUsed)
1352  FunctionNames.push_back(
1353  llvm::ConstantExpr::getBitCast(NamePtr, llvm::Type::getInt8PtrTy(Ctx)));
1354  CoverageMappings.push_back(CoverageMapping);
1355 
1356  if (CGM.getCodeGenOpts().DumpCoverageMapping) {
1357  // Dump the coverage mapping data for this function by decoding the
1358  // encoded data. This allows us to dump the mapping regions which were
1359  // also processed by the CoverageMappingWriter which performs
1360  // additional minimization operations such as reducing the number of
1361  // expressions.
1362  std::vector<StringRef> Filenames;
1363  std::vector<CounterExpression> Expressions;
1364  std::vector<CounterMappingRegion> Regions;
1366  llvm::SmallVector<StringRef, 16> FilenameRefs;
1367  FilenameStrs.resize(FileEntries.size());
1368  FilenameRefs.resize(FileEntries.size());
1369  for (const auto &Entry : FileEntries) {
1370  auto I = Entry.second;
1371  FilenameStrs[I] = normalizeFilename(Entry.first->getName());
1372  FilenameRefs[I] = FilenameStrs[I];
1373  }
1374  RawCoverageMappingReader Reader(CoverageMapping, FilenameRefs, Filenames,
1375  Expressions, Regions);
1376  if (Reader.read())
1377  return;
1378  dump(llvm::outs(), NameValue, Expressions, Regions);
1379  }
1380 }
1381 
1383  if (FunctionRecords.empty())
1384  return;
1385  llvm::LLVMContext &Ctx = CGM.getLLVMContext();
1386  auto *Int32Ty = llvm::Type::getInt32Ty(Ctx);
1387 
1388  // Create the filenames and merge them with coverage mappings
1390  llvm::SmallVector<StringRef, 16> FilenameRefs;
1391  FilenameStrs.resize(FileEntries.size());
1392  FilenameRefs.resize(FileEntries.size());
1393  for (const auto &Entry : FileEntries) {
1394  auto I = Entry.second;
1395  FilenameStrs[I] = normalizeFilename(Entry.first->getName());
1396  FilenameRefs[I] = FilenameStrs[I];
1397  }
1398 
1399  std::string FilenamesAndCoverageMappings;
1400  llvm::raw_string_ostream OS(FilenamesAndCoverageMappings);
1401  CoverageFilenamesSectionWriter(FilenameRefs).write(OS);
1402 
1403  // Stream the content of CoverageMappings to OS while keeping
1404  // memory consumption under control.
1405  size_t CoverageMappingSize = 0;
1406  for (auto &S : CoverageMappings) {
1407  CoverageMappingSize += S.size();
1408  OS << S;
1409  S.clear();
1410  S.shrink_to_fit();
1411  }
1412  CoverageMappings.clear();
1413  CoverageMappings.shrink_to_fit();
1414 
1415  size_t FilenamesSize = OS.str().size() - CoverageMappingSize;
1416  // Append extra zeroes if necessary to ensure that the size of the filenames
1417  // and coverage mappings is a multiple of 8.
1418  if (size_t Rem = OS.str().size() % 8) {
1419  CoverageMappingSize += 8 - Rem;
1420  OS.write_zeros(8 - Rem);
1421  }
1422  auto *FilenamesAndMappingsVal =
1423  llvm::ConstantDataArray::getString(Ctx, OS.str(), false);
1424 
1425  // Create the deferred function records array
1426  auto RecordsTy =
1427  llvm::ArrayType::get(FunctionRecordTy, FunctionRecords.size());
1428  auto RecordsVal = llvm::ConstantArray::get(RecordsTy, FunctionRecords);
1429 
1430  llvm::Type *CovDataHeaderTypes[] = {
1431 #define COVMAP_HEADER(Type, LLVMType, Name, Init) LLVMType,
1432 #include "llvm/ProfileData/InstrProfData.inc"
1433  };
1434  auto CovDataHeaderTy =
1435  llvm::StructType::get(Ctx, makeArrayRef(CovDataHeaderTypes));
1436  llvm::Constant *CovDataHeaderVals[] = {
1437 #define COVMAP_HEADER(Type, LLVMType, Name, Init) Init,
1438 #include "llvm/ProfileData/InstrProfData.inc"
1439  };
1440  auto CovDataHeaderVal = llvm::ConstantStruct::get(
1441  CovDataHeaderTy, makeArrayRef(CovDataHeaderVals));
1442 
1443  // Create the coverage data record
1444  llvm::Type *CovDataTypes[] = {CovDataHeaderTy, RecordsTy,
1445  FilenamesAndMappingsVal->getType()};
1446  auto CovDataTy = llvm::StructType::get(Ctx, makeArrayRef(CovDataTypes));
1447  llvm::Constant *TUDataVals[] = {CovDataHeaderVal, RecordsVal,
1448  FilenamesAndMappingsVal};
1449  auto CovDataVal =
1450  llvm::ConstantStruct::get(CovDataTy, makeArrayRef(TUDataVals));
1451  auto CovData = new llvm::GlobalVariable(
1452  CGM.getModule(), CovDataTy, true, llvm::GlobalValue::InternalLinkage,
1453  CovDataVal, llvm::getCoverageMappingVarName());
1454 
1455  CovData->setSection(getCoverageSection(CGM));
1456  CovData->setAlignment(llvm::Align(8));
1457 
1458  // Make sure the data doesn't get deleted.
1459  CGM.addUsedGlobal(CovData);
1460  // Create the deferred function records array
1461  if (!FunctionNames.empty()) {
1462  auto NamesArrTy = llvm::ArrayType::get(llvm::Type::getInt8PtrTy(Ctx),
1463  FunctionNames.size());
1464  auto NamesArrVal = llvm::ConstantArray::get(NamesArrTy, FunctionNames);
1465  // This variable will *NOT* be emitted to the object file. It is used
1466  // to pass the list of names referenced to codegen.
1467  new llvm::GlobalVariable(CGM.getModule(), NamesArrTy, true,
1469  llvm::getCoverageUnusedNamesVarName());
1470  }
1471 }
1472 
1474  auto It = FileEntries.find(File);
1475  if (It != FileEntries.end())
1476  return It->second;
1477  unsigned FileID = FileEntries.size();
1478  FileEntries.insert(std::make_pair(File, FileID));
1479  return FileID;
1480 }
1481 
1483  llvm::raw_ostream &OS) {
1484  assert(CounterMap);
1485  CounterCoverageMappingBuilder Walker(CVM, *CounterMap, SM, LangOpts);
1486  Walker.VisitDecl(D);
1487  Walker.write(OS);
1488 }
1489 
1491  llvm::raw_ostream &OS) {
1492  EmptyCoverageMappingBuilder Walker(CVM, SM, LangOpts);
1493  Walker.VisitDecl(D);
1494  Walker.write(OS);
1495 }
Expr * getInc()
Definition: Stmt.h:2427
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:643
const CodeGenOptions & getCodeGenOpts() const
const Expr * getSubExpr() const
Definition: ExprCXX.h:1162
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:2259
llvm::LLVMContext & getLLVMContext()
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:986
Stmt - This represents one statement.
Definition: Stmt.h:66
CXXCatchStmt * getHandler(unsigned i)
Definition: StmtCXX.h:107
IfStmt - This represents an if/then/else.
Definition: Stmt.h:1822
const llvm::Triple & getTriple() const
Returns the target triple of the primary target.
Definition: TargetInfo.h:991
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:88
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.
Stores additional source code information like skipped ranges which is required by the coverage mappi...
const TargetInfo & getTargetInfo() const
Definition: ASTContext.h:706
Stmt * getThen()
Definition: Stmt.h:1909
A C++ throw-expression (C++ [except.throw]).
Definition: ExprCXX.h:1140
void emit()
Emit the coverage mapping data for a translation unit.
LabelStmt - Represents a label, which has a substatement.
Definition: Stmt.h:1720
Stmt * getBody()
Definition: Stmt.h:2363
SourceLocation getBegin() const
SourceLocation getBeginLoc() const LLVM_READONLY
Definition: Stmt.cpp:274
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...
__DEVICE__ int max(int __a, int __b)
SourceLocation getQuestionLoc() const
Definition: Expr.h:3696
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:2394
static void dump(llvm::raw_ostream &OS, StringRef FunctionName, ArrayRef< CounterExpression > Expressions, ArrayRef< CounterMappingRegion > Regions)
SourceLocation getRParenLoc() const
Definition: StmtCXX.h:204
Stmt * getBody()
Definition: Stmt.h:2428
child_range children()
Definition: Stmt.cpp:223
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3409
Stmt * getInit()
Definition: Stmt.h:2407
CXXForRangeStmt - This represents C++0x [stmt.ranged]&#39;s ranged for statement, represented as &#39;for (ra...
Definition: StmtCXX.h:134
unsigned getSpellingLineNumber(SourceLocation Loc, bool *Invalid=nullptr) const
Expr * getCond()
Definition: Stmt.h:2426
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:1818
bool getNoReturn() const
Definition: Type.h:3550
unsigned getFileIDSize(FileID FID) const
The size of the SLocEntry that FID represents.
Stmt * getBody()
Definition: Stmt.h:2099
Stmt * getInit()
Definition: Stmt.h:1965
NodeId Parent
Definition: ASTDiff.cpp:191
StringRef Filename
Definition: Format.cpp:1807
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:444
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:2638
Stmt * getBody()
Definition: Stmt.h:2271
CXXTryStmt - A C++ try block, including all handlers.
Definition: StmtCXX.h:68
int Depth
Definition: ASTDiff.cpp:190
QualType getType() const
Definition: Expr.h:137
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:2620
Expr * getCond()
Definition: Stmt.h:1897
ASTContext & getContext() const
const SourceManager & SM
Definition: Format.cpp:1667
SourceLocation getEndLoc() const LLVM_READONLY
Definition: Stmt.cpp:287
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:2338
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:992
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:2653
unsigned getNumHandlers() const
Definition: StmtCXX.h:106
ArrayRef< SourceRange > getSkippedRanges() const
Stmt * getElse()
Definition: Stmt.h:1918
Cached information about one file (either on disk or in the virtual file system). ...
Definition: FileManager.h:78
Expr * getCond()
Definition: Stmt.h:2087
CoverageSourceInfo & getSourceInfo() const
Stmt * getSubStmt()
Definition: Stmt.h:1687
Expr * getLHS() const
Definition: Expr.h:3449
void addUsedGlobal(llvm::GlobalValue *GV)
Add a global to a list to be added to the llvm.used metadata.
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.
std::string DebugCompilationDir
The string to embed in debug information as the current working directory.
FunctionType::ExtInfo getFunctionExtInfo(const Type &t)
Definition: Type.h:6291
llvm::Module & getModule() const
CoverageMappingModuleGen(CodeGenModule &CGM, CoverageSourceInfo &SourceInfo)
bool isMacroID() const
SwitchStmt - This represents a &#39;switch&#39; stmt.
Definition: Stmt.h:2027
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:3665
Stmt * getInit()
Definition: Stmt.h:2108
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:2444
DeclStmt * getRangeStmt()
Definition: StmtCXX.h:161
GotoStmt - This represents a direct goto.
Definition: Stmt.h:2465
Expr * getCond()
Definition: Stmt.h:2356
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:2553
CXXCatchStmt - This represents a C++ catch block.
Definition: StmtCXX.h:28
bool LE(InterpState &S, CodePtr OpPC)
Definition: Interp.h:240
WhileStmt - This represents a &#39;while&#39; stmt.
Definition: Stmt.h:2210
CompoundStmt * getTryBlock()
Definition: StmtCXX.h:99
__DEVICE__ int min(int __a, int __b)
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2521
Expr * getRHS() const
Definition: Expr.h:3451
BreakStmt - This represents a break.
Definition: Stmt.h:2583
Stmt * getSubStmt()
Definition: Stmt.h:1741
DeclStmt * getLoopVarStmt()
Definition: StmtCXX.h:168
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.