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