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