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