contrib/llvm-project/clang/lib/CodeGen/CoverageMappingGen.cpp

   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
  31 void CoverageSourceInfo::SourceRangeSkipped(SourceRange Range, SourceLocation) {
  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.
  45   Optional<SourceLocation> LocEnd;
  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:
 132   CoverageMappingModuleGen &CVM;
 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
 143   llvm::SmallVector<CounterMappingRegion, 32> MappingRegions;
 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;
 229     SmallVector<std::pair<SourceLocation, unsigned>, 8> FileLocs;
 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.
 275     llvm::SmallVector<std::pair<unsigned, unsigned>, 8> FileLineRanges;
 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(
 838       CoverageMappingModuleGen &CVM,
 839       llvm::DenseMap<const Stmt *, unsigned> &CounterMap, SourceManager &SM,
 840       const LangOptions &LangOpts)
 841       : CoverageMappingBuilder(CVM, SM, LangOpts), CounterMap(CounterMap),
 842         DeferredRegion(None) {}
 843
 844   /// Write the mapping data to the output stream
 845   void write(llvm::raw_ostream &OS) {
 846     llvm::SmallVector<unsigned, 8> VirtualFileMapping;
 847     gatherFileIDs(VirtualFileMapping);
 848     SourceRegionFilter Filter = emitExpansionRegions();
 849     assert(!DeferredRegion && "Deferred region never completed");
 850     emitSourceRegions(Filter);
 851     gatherSkippedRegions();
 852
 853     if (MappingRegions.empty())
 854       return;
 855
 856     CoverageMappingWriter Writer(VirtualFileMapping, Builder.getExpressions(),
 857                                  MappingRegions);
 858     Writer.write(OS);
 859   }
 860
 861   void VisitStmt(const Stmt *S) {
 862     if (S->getBeginLoc().isValid())
 863       extendRegion(S);
 864     for (const Stmt *Child : S->children())
 865       if (Child)
 866         this->Visit(Child);
 867     handleFileExit(getEnd(S));
 868   }
 869
 870   void VisitDecl(const Decl *D) {
 871     assert(!DeferredRegion && "Deferred region never completed");
 872
 873     Stmt *Body = D->getBody();
 874
 875     // Do not propagate region counts into system headers.
 876     if (Body && SM.isInSystemHeader(SM.getSpellingLoc(getStart(Body))))
 877       return;
 878
 879     // Do not visit the artificial children nodes of defaulted methods. The
 880     // lexer may not be able to report back precise token end locations for
 881     // these children nodes (llvm.org/PR39822), and moreover users will not be
 882     // able to see coverage for them.
 883     bool Defaulted = false;
 884     if (auto *Method = dyn_cast<CXXMethodDecl>(D))
 885       Defaulted = Method->isDefaulted();
 886
 887     propagateCounts(getRegionCounter(Body), Body,
 888                     /*VisitChildren=*/!Defaulted);
 889     assert(RegionStack.empty() && "Regions entered but never exited");
 890
 891     // Discard the last uncompleted deferred region in a decl, if one exists.
 892     // This prevents lines at the end of a function containing only whitespace
 893     // or closing braces from being marked as uncovered.
 894     DeferredRegion = None;
 895   }
 896
 897   void VisitReturnStmt(const ReturnStmt *S) {
 898     extendRegion(S);
 899     if (S->getRetValue())
 900       Visit(S->getRetValue());
 901     terminateRegion(S);
 902   }
 903
 904   void VisitCXXThrowExpr(const CXXThrowExpr *E) {
 905     extendRegion(E);
 906     if (E->getSubExpr())
 907       Visit(E->getSubExpr());
 908     terminateRegion(E);
 909   }
 910
 911   void VisitGotoStmt(const GotoStmt *S) { terminateRegion(S); }
 912
 913   void VisitLabelStmt(const LabelStmt *S) {
 914     Counter LabelCount = getRegionCounter(S);
 915     SourceLocation Start = getStart(S);
 916     completeTopLevelDeferredRegion(LabelCount, Start);
 917     completeDeferred(LabelCount, Start);
 918     // We can't extendRegion here or we risk overlapping with our new region.
 919     handleFileExit(Start);
 920     pushRegion(LabelCount, Start);
 921     Visit(S->getSubStmt());
 922   }
 923
 924   void VisitBreakStmt(const BreakStmt *S) {
 925     assert(!BreakContinueStack.empty() && "break not in a loop or switch!");
 926     BreakContinueStack.back().BreakCount = addCounters(
 927         BreakContinueStack.back().BreakCount, getRegion().getCounter());
 928     // FIXME: a break in a switch should terminate regions for all preceding
 929     // case statements, not just the most recent one.
 930     terminateRegion(S);
 931   }
 932
 933   void VisitContinueStmt(const ContinueStmt *S) {
 934     assert(!BreakContinueStack.empty() && "continue stmt not in a loop!");
 935     BreakContinueStack.back().ContinueCount = addCounters(
 936         BreakContinueStack.back().ContinueCount, getRegion().getCounter());
 937     terminateRegion(S);
 938   }
 939
 940   void VisitCallExpr(const CallExpr *E) {
 941     VisitStmt(E);
 942
 943     // Terminate the region when we hit a noreturn function.
 944     // (This is helpful dealing with switch statements.)
 945     QualType CalleeType = E->getCallee()->getType();
 946     if (getFunctionExtInfo(*CalleeType).getNoReturn())
 947       terminateRegion(E);
 948   }
 949
 950   void VisitWhileStmt(const WhileStmt *S) {
 951     extendRegion(S);
 952
 953     Counter ParentCount = getRegion().getCounter();
 954     Counter BodyCount = getRegionCounter(S);
 955
 956     // Handle the body first so that we can get the backedge count.
 957     BreakContinueStack.push_back(BreakContinue());
 958     extendRegion(S->getBody());
 959     Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
 960     BreakContinue BC = BreakContinueStack.pop_back_val();
 961
 962     // Go back to handle the condition.
 963     Counter CondCount =
 964         addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
 965     propagateCounts(CondCount, S->getCond());
 966     adjustForOutOfOrderTraversal(getEnd(S));
 967
 968     // The body count applies to the area immediately after the increment.
 969     auto Gap = findGapAreaBetween(S->getCond(), S->getBody());
 970     if (Gap)
 971       fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
 972
 973     Counter OutCount =
 974         addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount));
 975     if (OutCount != ParentCount)
 976       pushRegion(OutCount);
 977   }
 978
 979   void VisitDoStmt(const DoStmt *S) {
 980     extendRegion(S);
 981
 982     Counter ParentCount = getRegion().getCounter();
 983     Counter BodyCount = getRegionCounter(S);
 984
 985     BreakContinueStack.push_back(BreakContinue());
 986     extendRegion(S->getBody());
 987     Counter BackedgeCount =
 988         propagateCounts(addCounters(ParentCount, BodyCount), S->getBody());
 989     BreakContinue BC = BreakContinueStack.pop_back_val();
 990
 991     Counter CondCount = addCounters(BackedgeCount, BC.ContinueCount);
 992     propagateCounts(CondCount, S->getCond());
 993
 994     Counter OutCount =
 995         addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount));
 996     if (OutCount != ParentCount)
 997       pushRegion(OutCount);
 998   }
 999
1000   void VisitForStmt(const ForStmt *S) {
1001     extendRegion(S);
1002     if (S->getInit())
1003       Visit(S->getInit());
1004
1005     Counter ParentCount = getRegion().getCounter();
1006     Counter BodyCount = getRegionCounter(S);
1007
1008     // The loop increment may contain a break or continue.
1009     if (S->getInc())
1010       BreakContinueStack.emplace_back();
1011
1012     // Handle the body first so that we can get the backedge count.
1013     BreakContinueStack.emplace_back();
1014     extendRegion(S->getBody());
1015     Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
1016     BreakContinue BodyBC = BreakContinueStack.pop_back_val();
1017
1018     // The increment is essentially part of the body but it needs to include
1019     // the count for all the continue statements.
1020     BreakContinue IncrementBC;
1021     if (const Stmt *Inc = S->getInc()) {
1022       propagateCounts(addCounters(BackedgeCount, BodyBC.ContinueCount), Inc);
1023       IncrementBC = BreakContinueStack.pop_back_val();
1024     }
1025
1026     // Go back to handle the condition.
1027     Counter CondCount = addCounters(
1028         addCounters(ParentCount, BackedgeCount, BodyBC.ContinueCount),
1029         IncrementBC.ContinueCount);
1030     if (const Expr *Cond = S->getCond()) {
1031       propagateCounts(CondCount, Cond);
1032       adjustForOutOfOrderTraversal(getEnd(S));
1033     }
1034
1035     // The body count applies to the area immediately after the increment.
1036     auto Gap = findGapAreaBetween(getPreciseTokenLocEnd(S->getRParenLoc()),
1037                                   getStart(S->getBody()));
1038     if (Gap)
1039       fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
1040
1041     Counter OutCount = addCounters(BodyBC.BreakCount, IncrementBC.BreakCount,
1042                                    subtractCounters(CondCount, BodyCount));
1043     if (OutCount != ParentCount)
1044       pushRegion(OutCount);
1045   }
1046
1047   void VisitCXXForRangeStmt(const CXXForRangeStmt *S) {
1048     extendRegion(S);
1049     if (S->getInit())
1050       Visit(S->getInit());
1051     Visit(S->getLoopVarStmt());
1052     Visit(S->getRangeStmt());
1053
1054     Counter ParentCount = getRegion().getCounter();
1055     Counter BodyCount = getRegionCounter(S);
1056
1057     BreakContinueStack.push_back(BreakContinue());
1058     extendRegion(S->getBody());
1059     Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
1060     BreakContinue BC = BreakContinueStack.pop_back_val();
1061
1062     // The body count applies to the area immediately after the range.
1063     auto Gap = findGapAreaBetween(getPreciseTokenLocEnd(S->getRParenLoc()),
1064                                   getStart(S->getBody()));
1065     if (Gap)
1066       fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
1067
1068     Counter LoopCount =
1069         addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
1070     Counter OutCount =
1071         addCounters(BC.BreakCount, subtractCounters(LoopCount, BodyCount));
1072     if (OutCount != ParentCount)
1073       pushRegion(OutCount);
1074   }
1075
1076   void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S) {
1077     extendRegion(S);
1078     Visit(S->getElement());
1079
1080     Counter ParentCount = getRegion().getCounter();
1081     Counter BodyCount = getRegionCounter(S);
1082
1083     BreakContinueStack.push_back(BreakContinue());
1084     extendRegion(S->getBody());
1085     Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
1086     BreakContinue BC = BreakContinueStack.pop_back_val();
1087
1088     // The body count applies to the area immediately after the collection.
1089     auto Gap = findGapAreaBetween(getPreciseTokenLocEnd(S->getRParenLoc()),
1090                                   getStart(S->getBody()));
1091     if (Gap)
1092       fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount);
1093
1094     Counter LoopCount =
1095         addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
1096     Counter OutCount =
1097         addCounters(BC.BreakCount, subtractCounters(LoopCount, BodyCount));
1098     if (OutCount != ParentCount)
1099       pushRegion(OutCount);
1100   }
1101
1102   void VisitSwitchStmt(const SwitchStmt *S) {
1103     extendRegion(S);
1104     if (S->getInit())
1105       Visit(S->getInit());
1106     Visit(S->getCond());
1107
1108     BreakContinueStack.push_back(BreakContinue());
1109
1110     const Stmt *Body = S->getBody();
1111     extendRegion(Body);
1112     if (const auto *CS = dyn_cast<CompoundStmt>(Body)) {
1113       if (!CS->body_empty()) {
1114         // Make a region for the body of the switch.  If the body starts with
1115         // a case, that case will reuse this region; otherwise, this covers
1116         // the unreachable code at the beginning of the switch body.
1117         size_t Index =
1118             pushRegion(Counter::getZero(), getStart(CS->body_front()));
1119         for (const auto *Child : CS->children())
1120           Visit(Child);
1121
1122         // Set the end for the body of the switch, if it isn't already set.
1123         for (size_t i = RegionStack.size(); i != Index; --i) {
1124           if (!RegionStack[i - 1].hasEndLoc())
1125             RegionStack[i - 1].setEndLoc(getEnd(CS->body_back()));
1126         }
1127
1128         popRegions(Index);
1129       }
1130     } else
1131       propagateCounts(Counter::getZero(), Body);
1132     BreakContinue BC = BreakContinueStack.pop_back_val();
1133
1134     if (!BreakContinueStack.empty())
1135       BreakContinueStack.back().ContinueCount = addCounters(
1136           BreakContinueStack.back().ContinueCount, BC.ContinueCount);
1137
1138     Counter ExitCount = getRegionCounter(S);
1139     SourceLocation ExitLoc = getEnd(S);
1140     pushRegion(ExitCount);
1141
1142     // Ensure that handleFileExit recognizes when the end location is located
1143     // in a different file.
1144     MostRecentLocation = getStart(S);
1145     handleFileExit(ExitLoc);
1146   }
1147
1148   void VisitSwitchCase(const SwitchCase *S) {
1149     extendRegion(S);
1150
1151     SourceMappingRegion &Parent = getRegion();
1152
1153     Counter Count = addCounters(Parent.getCounter(), getRegionCounter(S));
1154     // Reuse the existing region if it starts at our label. This is typical of
1155     // the first case in a switch.
1156     if (Parent.hasStartLoc() && Parent.getBeginLoc() == getStart(S))
1157       Parent.setCounter(Count);
1158     else
1159       pushRegion(Count, getStart(S));
1160
1161     if (const auto *CS = dyn_cast<CaseStmt>(S)) {
1162       Visit(CS->getLHS());
1163       if (const Expr *RHS = CS->getRHS())
1164         Visit(RHS);
1165     }
1166     Visit(S->getSubStmt());
1167   }
1168
1169   void VisitIfStmt(const IfStmt *S) {
1170     extendRegion(S);
1171     if (S->getInit())
1172       Visit(S->getInit());
1173
1174     // Extend into the condition before we propagate through it below - this is
1175     // needed to handle macros that generate the "if" but not the condition.
1176     extendRegion(S->getCond());
1177
1178     Counter ParentCount = getRegion().getCounter();
1179     Counter ThenCount = getRegionCounter(S);
1180
1181     // Emitting a counter for the condition makes it easier to interpret the
1182     // counter for the body when looking at the coverage.
1183     propagateCounts(ParentCount, S->getCond());
1184
1185     // The 'then' count applies to the area immediately after the condition.
1186     auto Gap = findGapAreaBetween(S->getCond(), S->getThen());
1187     if (Gap)
1188       fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), ThenCount);
1189
1190     extendRegion(S->getThen());
1191     Counter OutCount = propagateCounts(ThenCount, S->getThen());
1192
1193     Counter ElseCount = subtractCounters(ParentCount, ThenCount);
1194     if (const Stmt *Else = S->getElse()) {
1195       // The 'else' count applies to the area immediately after the 'then'.
1196       Gap = findGapAreaBetween(S->getThen(), Else);
1197       if (Gap)
1198         fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), ElseCount);
1199       extendRegion(Else);
1200       OutCount = addCounters(OutCount, propagateCounts(ElseCount, Else));
1201     } else
1202       OutCount = addCounters(OutCount, ElseCount);
1203
1204     if (OutCount != ParentCount)
1205       pushRegion(OutCount);
1206   }
1207
1208   void VisitCXXTryStmt(const CXXTryStmt *S) {
1209     extendRegion(S);
1210     // Handle macros that generate the "try" but not the rest.
1211     extendRegion(S->getTryBlock());
1212
1213     Counter ParentCount = getRegion().getCounter();
1214     propagateCounts(ParentCount, S->getTryBlock());
1215
1216     for (unsigned I = 0, E = S->getNumHandlers(); I < E; ++I)
1217       Visit(S->getHandler(I));
1218
1219     Counter ExitCount = getRegionCounter(S);
1220     pushRegion(ExitCount);
1221   }
1222
1223   void VisitCXXCatchStmt(const CXXCatchStmt *S) {
1224     propagateCounts(getRegionCounter(S), S->getHandlerBlock());
1225   }
1226
1227   void VisitAbstractConditionalOperator(const AbstractConditionalOperator *E) {
1228     extendRegion(E);
1229
1230     Counter ParentCount = getRegion().getCounter();
1231     Counter TrueCount = getRegionCounter(E);
1232
1233     Visit(E->getCond());
1234
1235     if (!isa<BinaryConditionalOperator>(E)) {
1236       // The 'then' count applies to the area immediately after the condition.
1237       auto Gap =
1238           findGapAreaBetween(E->getQuestionLoc(), getStart(E->getTrueExpr()));
1239       if (Gap)
1240         fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), TrueCount);
1241
1242       extendRegion(E->getTrueExpr());
1243       propagateCounts(TrueCount, E->getTrueExpr());
1244     }
1245
1246     extendRegion(E->getFalseExpr());
1247     propagateCounts(subtractCounters(ParentCount, TrueCount),
1248                     E->getFalseExpr());
1249   }
1250
1251   void VisitBinLAnd(const BinaryOperator *E) {
1252     extendRegion(E->getLHS());
1253     propagateCounts(getRegion().getCounter(), E->getLHS());
1254     handleFileExit(getEnd(E->getLHS()));
1255
1256     extendRegion(E->getRHS());
1257     propagateCounts(getRegionCounter(E), E->getRHS());
1258   }
1259
1260   void VisitBinLOr(const BinaryOperator *E) {
1261     extendRegion(E->getLHS());
1262     propagateCounts(getRegion().getCounter(), E->getLHS());
1263     handleFileExit(getEnd(E->getLHS()));
1264
1265     extendRegion(E->getRHS());
1266     propagateCounts(getRegionCounter(E), E->getRHS());
1267   }
1268
1269   void VisitLambdaExpr(const LambdaExpr *LE) {
1270     // Lambdas are treated as their own functions for now, so we shouldn't
1271     // propagate counts into them.
1272   }
1273 };
1274
1275 std::string getCoverageSection(const CodeGenModule &CGM) {
1276   return llvm::getInstrProfSectionName(
1277       llvm::IPSK_covmap,
1278       CGM.getContext().getTargetInfo().getTriple().getObjectFormat());
1279 }
1280
1281 std::string normalizeFilename(StringRef Filename) {
1282   llvm::SmallString<256> Path(Filename);
1283   llvm::sys::fs::make_absolute(Path);
1284   llvm::sys::path::remove_dots(Path, /*remove_dot_dot=*/true);
1285   return Path.str().str();
1286 }
1287
1288 } // end anonymous namespace
1289
1290 static void dump(llvm::raw_ostream &OS, StringRef FunctionName,
1291                  ArrayRef<CounterExpression> Expressions,
1292                  ArrayRef<CounterMappingRegion> Regions) {
1293   OS << FunctionName << ":\n";
1294   CounterMappingContext Ctx(Expressions);
1295   for (const auto &R : Regions) {
1296     OS.indent(2);
1297     switch (R.Kind) {
1298     case CounterMappingRegion::CodeRegion:
1299       break;
1300     case CounterMappingRegion::ExpansionRegion:
1301       OS << "Expansion,";
1302       break;
1303     case CounterMappingRegion::SkippedRegion:
1304       OS << "Skipped,";
1305       break;
1306     case CounterMappingRegion::GapRegion:
1307       OS << "Gap,";
1308       break;
1309     }
1310
1311     OS << "File " << R.FileID << ", " << R.LineStart << ":" << R.ColumnStart
1312        << " -> " << R.LineEnd << ":" << R.ColumnEnd << " = ";
1313     Ctx.dump(R.Count, OS);
1314     if (R.Kind == CounterMappingRegion::ExpansionRegion)
1315       OS << " (Expanded file = " << R.ExpandedFileID << ")";
1316     OS << "\n";
1317   }
1318 }
1319
1320 void CoverageMappingModuleGen::addFunctionMappingRecord(
1321     llvm::GlobalVariable *NamePtr, StringRef NameValue, uint64_t FuncHash,
1322     const std::string &CoverageMapping, bool IsUsed) {
1323   llvm::LLVMContext &Ctx = CGM.getLLVMContext();
1324   if (!FunctionRecordTy) {
1325 #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) LLVMType,
1326     llvm::Type *FunctionRecordTypes[] = {
1327       #include "llvm/ProfileData/InstrProfData.inc"
1328     };
1329     FunctionRecordTy =
1330         llvm::StructType::get(Ctx, makeArrayRef(FunctionRecordTypes),
1331                               /*isPacked=*/true);
1332   }
1333
1334   #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Init,
1335   llvm::Constant *FunctionRecordVals[] = {
1336       #include "llvm/ProfileData/InstrProfData.inc"
1337   };
1338   FunctionRecords.push_back(llvm::ConstantStruct::get(
1339       FunctionRecordTy, makeArrayRef(FunctionRecordVals)));
1340   if (!IsUsed)
1341     FunctionNames.push_back(
1342         llvm::ConstantExpr::getBitCast(NamePtr, llvm::Type::getInt8PtrTy(Ctx)));
1343   CoverageMappings.push_back(CoverageMapping);
1344
1345   if (CGM.getCodeGenOpts().DumpCoverageMapping) {
1346     // Dump the coverage mapping data for this function by decoding the
1347     // encoded data. This allows us to dump the mapping regions which were
1348     // also processed by the CoverageMappingWriter which performs
1349     // additional minimization operations such as reducing the number of
1350     // expressions.
1351     std::vector<StringRef> Filenames;
1352     std::vector<CounterExpression> Expressions;
1353     std::vector<CounterMappingRegion> Regions;
1354     llvm::SmallVector<std::string, 16> FilenameStrs;
1355     llvm::SmallVector<StringRef, 16> FilenameRefs;
1356     FilenameStrs.resize(FileEntries.size());
1357     FilenameRefs.resize(FileEntries.size());
1358     for (const auto &Entry : FileEntries) {
1359       auto I = Entry.second;
1360       FilenameStrs[I] = normalizeFilename(Entry.first->getName());
1361       FilenameRefs[I] = FilenameStrs[I];
1362     }
1363     RawCoverageMappingReader Reader(CoverageMapping, FilenameRefs, Filenames,
1364                                     Expressions, Regions);
1365     if (Reader.read())
1366       return;
1367     dump(llvm::outs(), NameValue, Expressions, Regions);
1368   }
1369 }
1370
1371 void CoverageMappingModuleGen::emit() {
1372   if (FunctionRecords.empty())
1373     return;
1374   llvm::LLVMContext &Ctx = CGM.getLLVMContext();
1375   auto *Int32Ty = llvm::Type::getInt32Ty(Ctx);
1376
1377   // Create the filenames and merge them with coverage mappings
1378   llvm::SmallVector<std::string, 16> FilenameStrs;
1379   llvm::SmallVector<StringRef, 16> FilenameRefs;
1380   FilenameStrs.resize(FileEntries.size());
1381   FilenameRefs.resize(FileEntries.size());
1382   for (const auto &Entry : FileEntries) {
1383     auto I = Entry.second;
1384     FilenameStrs[I] = normalizeFilename(Entry.first->getName());
1385     FilenameRefs[I] = FilenameStrs[I];
1386   }
1387
1388   std::string FilenamesAndCoverageMappings;
1389   llvm::raw_string_ostream OS(FilenamesAndCoverageMappings);
1390   CoverageFilenamesSectionWriter(FilenameRefs).write(OS);
1391
1392   // Stream the content of CoverageMappings to OS while keeping
1393   // memory consumption under control.
1394   size_t CoverageMappingSize = 0;
1395   for (auto &S : CoverageMappings) {
1396     CoverageMappingSize += S.size();
1397     OS << S;
1398     S.clear();
1399     S.shrink_to_fit();
1400   }
1401   CoverageMappings.clear();
1402   CoverageMappings.shrink_to_fit();
1403
1404   size_t FilenamesSize = OS.str().size() - CoverageMappingSize;
1405   // Append extra zeroes if necessary to ensure that the size of the filenames
1406   // and coverage mappings is a multiple of 8.
1407   if (size_t Rem = OS.str().size() % 8) {
1408     CoverageMappingSize += 8 - Rem;
1409     OS.write_zeros(8 - Rem);
1410   }
1411   auto *FilenamesAndMappingsVal =
1412       llvm::ConstantDataArray::getString(Ctx, OS.str(), false);
1413
1414   // Create the deferred function records array
1415   auto RecordsTy =
1416       llvm::ArrayType::get(FunctionRecordTy, FunctionRecords.size());
1417   auto RecordsVal = llvm::ConstantArray::get(RecordsTy, FunctionRecords);
1418
1419   llvm::Type *CovDataHeaderTypes[] = {
1420 #define COVMAP_HEADER(Type, LLVMType, Name, Init) LLVMType,
1421 #include "llvm/ProfileData/InstrProfData.inc"
1422   };
1423   auto CovDataHeaderTy =
1424       llvm::StructType::get(Ctx, makeArrayRef(CovDataHeaderTypes));
1425   llvm::Constant *CovDataHeaderVals[] = {
1426 #define COVMAP_HEADER(Type, LLVMType, Name, Init) Init,
1427 #include "llvm/ProfileData/InstrProfData.inc"
1428   };
1429   auto CovDataHeaderVal = llvm::ConstantStruct::get(
1430       CovDataHeaderTy, makeArrayRef(CovDataHeaderVals));
1431
1432   // Create the coverage data record
1433   llvm::Type *CovDataTypes[] = {CovDataHeaderTy, RecordsTy,
1434                                 FilenamesAndMappingsVal->getType()};
1435   auto CovDataTy = llvm::StructType::get(Ctx, makeArrayRef(CovDataTypes));
1436   llvm::Constant *TUDataVals[] = {CovDataHeaderVal, RecordsVal,
1437                                   FilenamesAndMappingsVal};
1438   auto CovDataVal =
1439       llvm::ConstantStruct::get(CovDataTy, makeArrayRef(TUDataVals));
1440   auto CovData = new llvm::GlobalVariable(
1441       CGM.getModule(), CovDataTy, true, llvm::GlobalValue::InternalLinkage,
1442       CovDataVal, llvm::getCoverageMappingVarName());
1443
1444   CovData->setSection(getCoverageSection(CGM));
1445   CovData->setAlignment(8);
1446
1447   // Make sure the data doesn't get deleted.
1448   CGM.addUsedGlobal(CovData);
1449   // Create the deferred function records array
1450   if (!FunctionNames.empty()) {
1451     auto NamesArrTy = llvm::ArrayType::get(llvm::Type::getInt8PtrTy(Ctx),
1452                                            FunctionNames.size());
1453     auto NamesArrVal = llvm::ConstantArray::get(NamesArrTy, FunctionNames);
1454     // This variable will *NOT* be emitted to the object file. It is used
1455     // to pass the list of names referenced to codegen.
1456     new llvm::GlobalVariable(CGM.getModule(), NamesArrTy, true,
1457                              llvm::GlobalValue::InternalLinkage, NamesArrVal,
1458                              llvm::getCoverageUnusedNamesVarName());
1459   }
1460 }
1461
1462 unsigned CoverageMappingModuleGen::getFileID(const FileEntry *File) {
1463   auto It = FileEntries.find(File);
1464   if (It != FileEntries.end())
1465     return It->second;
1466   unsigned FileID = FileEntries.size();
1467   FileEntries.insert(std::make_pair(File, FileID));
1468   return FileID;
1469 }
1470
1471 void CoverageMappingGen::emitCounterMapping(const Decl *D,
1472                                             llvm::raw_ostream &OS) {
1473   assert(CounterMap);
1474   CounterCoverageMappingBuilder Walker(CVM, *CounterMap, SM, LangOpts);
1475   Walker.VisitDecl(D);
1476   Walker.write(OS);
1477 }
1478
1479 void CoverageMappingGen::emitEmptyMapping(const Decl *D,
1480                                           llvm::raw_ostream &OS) {
1481   EmptyCoverageMappingBuilder Walker(CVM, SM, LangOpts);
1482   Walker.VisitDecl(D);
1483   Walker.write(OS);
1484 }