lib/CodeGen/CoverageMappingGen.cpp

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