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/Optional.h"
  19 #include "llvm/ProfileData/CoverageMapping.h"
  20 #include "llvm/ProfileData/CoverageMappingReader.h"
  21 #include "llvm/ProfileData/CoverageMappingWriter.h"
  22 #include "llvm/ProfileData/InstrProfReader.h"
  23 #include "llvm/Support/FileSystem.h"
  24
  25 using namespace clang;
  26 using namespace CodeGen;
  27 using namespace llvm::coverage;
  28
  29 void CoverageSourceInfo::SourceRangeSkipped(SourceRange Range) {
  30   SkippedRanges.push_back(Range);
  31 }
  32
  33 namespace {
  34
  35 /// \brief A region of source code that can be mapped to a counter.
  36 class SourceMappingRegion {
  37   Counter Count;
  38
  39   /// \brief The region's starting location.
  40   Optional<SourceLocation> LocStart;
  41
  42   /// \brief The region's ending location.
  43   Optional<SourceLocation> LocEnd;
  44
  45 public:
  46   SourceMappingRegion(Counter Count, Optional<SourceLocation> LocStart,
  47                       Optional<SourceLocation> LocEnd)
  48       : Count(Count), LocStart(LocStart), LocEnd(LocEnd) {}
  49
  50   SourceMappingRegion(SourceMappingRegion &&Region)
  51       : Count(std::move(Region.Count)), LocStart(std::move(Region.LocStart)),
  52         LocEnd(std::move(Region.LocEnd)) {}
  53
  54   SourceMappingRegion &operator=(SourceMappingRegion &&RHS) {
  55     Count = std::move(RHS.Count);
  56     LocStart = std::move(RHS.LocStart);
  57     LocEnd = std::move(RHS.LocEnd);
  58     return *this;
  59   }
  60
  61   const Counter &getCounter() const { return Count; }
  62
  63   void setCounter(Counter C) { Count = C; }
  64
  65   bool hasStartLoc() const { return LocStart.hasValue(); }
  66
  67   void setStartLoc(SourceLocation Loc) { LocStart = Loc; }
  68
  69   const SourceLocation &getStartLoc() const {
  70     assert(LocStart && "Region has no start location");
  71     return *LocStart;
  72   }
  73
  74   bool hasEndLoc() const { return LocEnd.hasValue(); }
  75
  76   void setEndLoc(SourceLocation Loc) { LocEnd = Loc; }
  77
  78   const SourceLocation &getEndLoc() const {
  79     assert(LocEnd && "Region has no end location");
  80     return *LocEnd;
  81   }
  82 };
  83
  84 /// \brief Provides the common functionality for the different
  85 /// coverage mapping region builders.
  86 class CoverageMappingBuilder {
  87 public:
  88   CoverageMappingModuleGen &CVM;
  89   SourceManager &SM;
  90   const LangOptions &LangOpts;
  91
  92 private:
  93   /// \brief Map of clang's FileIDs to IDs used for coverage mapping.
  94   llvm::SmallDenseMap<FileID, std::pair<unsigned, SourceLocation>, 8>
  95       FileIDMapping;
  96
  97 public:
  98   /// \brief The coverage mapping regions for this function
  99   llvm::SmallVector<CounterMappingRegion, 32> MappingRegions;
 100   /// \brief The source mapping regions for this function.
 101   std::vector<SourceMappingRegion> SourceRegions;
 102
 103   CoverageMappingBuilder(CoverageMappingModuleGen &CVM, SourceManager &SM,
 104                          const LangOptions &LangOpts)
 105       : CVM(CVM), SM(SM), LangOpts(LangOpts) {}
 106
 107   /// \brief Return the precise end location for the given token.
 108   SourceLocation getPreciseTokenLocEnd(SourceLocation Loc) {
 109     // We avoid getLocForEndOfToken here, because it doesn't do what we want for
 110     // macro locations, which we just treat as expanded files.
 111     unsigned TokLen =
 112         Lexer::MeasureTokenLength(SM.getSpellingLoc(Loc), SM, LangOpts);
 113     return Loc.getLocWithOffset(TokLen);
 114   }
 115
 116   /// \brief Return the start location of an included file or expanded macro.
 117   SourceLocation getStartOfFileOrMacro(SourceLocation Loc) {
 118     if (Loc.isMacroID())
 119       return Loc.getLocWithOffset(-SM.getFileOffset(Loc));
 120     return SM.getLocForStartOfFile(SM.getFileID(Loc));
 121   }
 122
 123   /// \brief Return the end location of an included file or expanded macro.
 124   SourceLocation getEndOfFileOrMacro(SourceLocation Loc) {
 125     if (Loc.isMacroID())
 126       return Loc.getLocWithOffset(SM.getFileIDSize(SM.getFileID(Loc)) -
 127                                   SM.getFileOffset(Loc));
 128     return SM.getLocForEndOfFile(SM.getFileID(Loc));
 129   }
 130
 131   /// \brief Find out where the current file is included or macro is expanded.
 132   SourceLocation getIncludeOrExpansionLoc(SourceLocation Loc) {
 133     return Loc.isMacroID() ? SM.getImmediateExpansionRange(Loc).first
 134                            : SM.getIncludeLoc(SM.getFileID(Loc));
 135   }
 136
 137   /// \brief Return true if \c Loc is a location in a built-in macro.
 138   bool isInBuiltin(SourceLocation Loc) {
 139     return strcmp(SM.getBufferName(SM.getSpellingLoc(Loc)), "<built-in>") == 0;
 140   }
 141
 142   /// \brief Get the start of \c S ignoring macro arguments and builtin macros.
 143   SourceLocation getStart(const Stmt *S) {
 144     SourceLocation Loc = S->getLocStart();
 145     while (SM.isMacroArgExpansion(Loc) || isInBuiltin(Loc))
 146       Loc = SM.getImmediateExpansionRange(Loc).first;
 147     return Loc;
 148   }
 149
 150   /// \brief Get the end of \c S ignoring macro arguments and builtin macros.
 151   SourceLocation getEnd(const Stmt *S) {
 152     SourceLocation Loc = S->getLocEnd();
 153     while (SM.isMacroArgExpansion(Loc) || isInBuiltin(Loc))
 154       Loc = SM.getImmediateExpansionRange(Loc).first;
 155     return getPreciseTokenLocEnd(Loc);
 156   }
 157
 158   /// \brief Find the set of files we have regions for and assign IDs
 159   ///
 160   /// Fills \c Mapping with the virtual file mapping needed to write out
 161   /// coverage and collects the necessary file information to emit source and
 162   /// expansion regions.
 163   void gatherFileIDs(SmallVectorImpl<unsigned> &Mapping) {
 164     FileIDMapping.clear();
 165
 166     SmallVector<FileID, 8> Visited;
 167     SmallVector<std::pair<SourceLocation, unsigned>, 8> FileLocs;
 168     for (const auto &Region : SourceRegions) {
 169       SourceLocation Loc = Region.getStartLoc();
 170       FileID File = SM.getFileID(Loc);
 171       if (std::find(Visited.begin(), Visited.end(), File) != Visited.end())
 172         continue;
 173       Visited.push_back(File);
 174
 175       unsigned Depth = 0;
 176       for (SourceLocation Parent = getIncludeOrExpansionLoc(Loc);
 177            !Parent.isInvalid(); Parent = getIncludeOrExpansionLoc(Parent))
 178         ++Depth;
 179       FileLocs.push_back(std::make_pair(Loc, Depth));
 180     }
 181     std::stable_sort(FileLocs.begin(), FileLocs.end(), llvm::less_second());
 182
 183     for (const auto &FL : FileLocs) {
 184       SourceLocation Loc = FL.first;
 185       FileID SpellingFile = SM.getDecomposedSpellingLoc(Loc).first;
 186       auto Entry = SM.getFileEntryForID(SpellingFile);
 187       if (!Entry)
 188         continue;
 189
 190       FileIDMapping[SM.getFileID(Loc)] = std::make_pair(Mapping.size(), Loc);
 191       Mapping.push_back(CVM.getFileID(Entry));
 192     }
 193   }
 194
 195   /// \brief Get the coverage mapping file ID for \c Loc.
 196   ///
 197   /// If such file id doesn't exist, return None.
 198   Optional<unsigned> getCoverageFileID(SourceLocation Loc) {
 199     auto Mapping = FileIDMapping.find(SM.getFileID(Loc));
 200     if (Mapping != FileIDMapping.end())
 201       return Mapping->second.first;
 202     return None;
 203   }
 204
 205   /// \brief Return true if the given clang's file id has a corresponding
 206   /// coverage file id.
 207   bool hasExistingCoverageFileID(FileID File) const {
 208     return FileIDMapping.count(File);
 209   }
 210
 211   /// \brief Gather all the regions that were skipped by the preprocessor
 212   /// using the constructs like #if.
 213   void gatherSkippedRegions() {
 214     /// An array of the minimum lineStarts and the maximum lineEnds
 215     /// for mapping regions from the appropriate source files.
 216     llvm::SmallVector<std::pair<unsigned, unsigned>, 8> FileLineRanges;
 217     FileLineRanges.resize(
 218         FileIDMapping.size(),
 219         std::make_pair(std::numeric_limits<unsigned>::max(), 0));
 220     for (const auto &R : MappingRegions) {
 221       FileLineRanges[R.FileID].first =
 222           std::min(FileLineRanges[R.FileID].first, R.LineStart);
 223       FileLineRanges[R.FileID].second =
 224           std::max(FileLineRanges[R.FileID].second, R.LineEnd);
 225     }
 226
 227     auto SkippedRanges = CVM.getSourceInfo().getSkippedRanges();
 228     for (const auto &I : SkippedRanges) {
 229       auto LocStart = I.getBegin();
 230       auto LocEnd = I.getEnd();
 231       assert(SM.isWrittenInSameFile(LocStart, LocEnd) &&
 232              "region spans multiple files");
 233
 234       auto CovFileID = getCoverageFileID(LocStart);
 235       if (!CovFileID)
 236         continue;
 237       unsigned LineStart = SM.getSpellingLineNumber(LocStart);
 238       unsigned ColumnStart = SM.getSpellingColumnNumber(LocStart);
 239       unsigned LineEnd = SM.getSpellingLineNumber(LocEnd);
 240       unsigned ColumnEnd = SM.getSpellingColumnNumber(LocEnd);
 241       auto Region = CounterMappingRegion::makeSkipped(
 242           *CovFileID, LineStart, ColumnStart, LineEnd, ColumnEnd);
 243       // Make sure that we only collect the regions that are inside
 244       // the souce code of this function.
 245       if (Region.LineStart >= FileLineRanges[*CovFileID].first &&
 246           Region.LineEnd <= FileLineRanges[*CovFileID].second)
 247         MappingRegions.push_back(Region);
 248     }
 249   }
 250
 251   /// \brief Generate the coverage counter mapping regions from collected
 252   /// source regions.
 253   void emitSourceRegions() {
 254     for (const auto &Region : SourceRegions) {
 255       assert(Region.hasEndLoc() && "incomplete region");
 256
 257       SourceLocation LocStart = Region.getStartLoc();
 258       assert(!SM.getFileID(LocStart).isInvalid() && "region in invalid file");
 259
 260       auto CovFileID = getCoverageFileID(LocStart);
 261       // Ignore regions that don't have a file, such as builtin macros.
 262       if (!CovFileID)
 263         continue;
 264
 265       SourceLocation LocEnd = Region.getEndLoc();
 266       assert(SM.isWrittenInSameFile(LocStart, LocEnd) &&
 267              "region spans multiple files");
 268
 269       // Find the spilling locations for the mapping region.
 270       unsigned LineStart = SM.getSpellingLineNumber(LocStart);
 271       unsigned ColumnStart = SM.getSpellingColumnNumber(LocStart);
 272       unsigned LineEnd = SM.getSpellingLineNumber(LocEnd);
 273       unsigned ColumnEnd = SM.getSpellingColumnNumber(LocEnd);
 274
 275       assert(LineStart <= LineEnd && "region start and end out of order");
 276       MappingRegions.push_back(CounterMappingRegion::makeRegion(
 277           Region.getCounter(), *CovFileID, LineStart, ColumnStart, LineEnd,
 278           ColumnEnd));
 279     }
 280   }
 281
 282   /// \brief Generate expansion regions for each virtual file we've seen.
 283   void emitExpansionRegions() {
 284     for (const auto &FM : FileIDMapping) {
 285       SourceLocation ExpandedLoc = FM.second.second;
 286       SourceLocation ParentLoc = getIncludeOrExpansionLoc(ExpandedLoc);
 287       if (ParentLoc.isInvalid())
 288         continue;
 289
 290       auto ParentFileID = getCoverageFileID(ParentLoc);
 291       if (!ParentFileID)
 292         continue;
 293       auto ExpandedFileID = getCoverageFileID(ExpandedLoc);
 294       assert(ExpandedFileID && "expansion in uncovered file");
 295
 296       SourceLocation LocEnd = getPreciseTokenLocEnd(ParentLoc);
 297       assert(SM.isWrittenInSameFile(ParentLoc, LocEnd) &&
 298              "region spans multiple files");
 299
 300       unsigned LineStart = SM.getSpellingLineNumber(ParentLoc);
 301       unsigned ColumnStart = SM.getSpellingColumnNumber(ParentLoc);
 302       unsigned LineEnd = SM.getSpellingLineNumber(LocEnd);
 303       unsigned ColumnEnd = SM.getSpellingColumnNumber(LocEnd);
 304
 305       MappingRegions.push_back(CounterMappingRegion::makeExpansion(
 306           *ParentFileID, *ExpandedFileID, LineStart, ColumnStart, LineEnd,
 307           ColumnEnd));
 308     }
 309   }
 310 };
 311
 312 /// \brief Creates unreachable coverage regions for the functions that
 313 /// are not emitted.
 314 struct EmptyCoverageMappingBuilder : public CoverageMappingBuilder {
 315   EmptyCoverageMappingBuilder(CoverageMappingModuleGen &CVM, SourceManager &SM,
 316                               const LangOptions &LangOpts)
 317       : CoverageMappingBuilder(CVM, SM, LangOpts) {}
 318
 319   void VisitDecl(const Decl *D) {
 320     if (!D->hasBody())
 321       return;
 322     auto Body = D->getBody();
 323     SourceRegions.emplace_back(Counter(), getStart(Body), getEnd(Body));
 324   }
 325
 326   /// \brief Write the mapping data to the output stream
 327   void write(llvm::raw_ostream &OS) {
 328     SmallVector<unsigned, 16> FileIDMapping;
 329     gatherFileIDs(FileIDMapping);
 330     emitSourceRegions();
 331
 332     CoverageMappingWriter Writer(FileIDMapping, None, MappingRegions);
 333     Writer.write(OS);
 334   }
 335 };
 336
 337 /// \brief A StmtVisitor that creates coverage mapping regions which map
 338 /// from the source code locations to the PGO counters.
 339 struct CounterCoverageMappingBuilder
 340     : public CoverageMappingBuilder,
 341       public ConstStmtVisitor<CounterCoverageMappingBuilder> {
 342   /// \brief The map of statements to count values.
 343   llvm::DenseMap<const Stmt *, unsigned> &CounterMap;
 344
 345   /// \brief A stack of currently live regions.
 346   std::vector<SourceMappingRegion> RegionStack;
 347
 348   CounterExpressionBuilder Builder;
 349
 350   /// \brief A location in the most recently visited file or macro.
 351   ///
 352   /// This is used to adjust the active source regions appropriately when
 353   /// expressions cross file or macro boundaries.
 354   SourceLocation MostRecentLocation;
 355
 356   /// \brief Return a counter for the subtraction of \c RHS from \c LHS
 357   Counter subtractCounters(Counter LHS, Counter RHS) {
 358     return Builder.subtract(LHS, RHS);
 359   }
 360
 361   /// \brief Return a counter for the sum of \c LHS and \c RHS.
 362   Counter addCounters(Counter LHS, Counter RHS) {
 363     return Builder.add(LHS, RHS);
 364   }
 365
 366   Counter addCounters(Counter C1, Counter C2, Counter C3) {
 367     return addCounters(addCounters(C1, C2), C3);
 368   }
 369
 370   Counter addCounters(Counter C1, Counter C2, Counter C3, Counter C4) {
 371     return addCounters(addCounters(C1, C2, C3), C4);
 372   }
 373
 374   /// \brief Return the region counter for the given statement.
 375   ///
 376   /// This should only be called on statements that have a dedicated counter.
 377   Counter getRegionCounter(const Stmt *S) {
 378     return Counter::getCounter(CounterMap[S]);
 379   }
 380
 381   /// \brief Push a region onto the stack.
 382   ///
 383   /// Returns the index on the stack where the region was pushed. This can be
 384   /// used with popRegions to exit a "scope", ending the region that was pushed.
 385   size_t pushRegion(Counter Count, Optional<SourceLocation> StartLoc = None,
 386                     Optional<SourceLocation> EndLoc = None) {
 387     if (StartLoc)
 388       MostRecentLocation = *StartLoc;
 389     RegionStack.emplace_back(Count, StartLoc, EndLoc);
 390
 391     return RegionStack.size() - 1;
 392   }
 393
 394   /// \brief Pop regions from the stack into the function's list of regions.
 395   ///
 396   /// Adds all regions from \c ParentIndex to the top of the stack to the
 397   /// function's \c SourceRegions.
 398   void popRegions(size_t ParentIndex) {
 399     assert(RegionStack.size() >= ParentIndex && "parent not in stack");
 400     while (RegionStack.size() > ParentIndex) {
 401       SourceMappingRegion &Region = RegionStack.back();
 402       if (Region.hasStartLoc()) {
 403         SourceLocation StartLoc = Region.getStartLoc();
 404         SourceLocation EndLoc = Region.hasEndLoc()
 405                                     ? Region.getEndLoc()
 406                                     : RegionStack[ParentIndex].getEndLoc();
 407         while (!SM.isWrittenInSameFile(StartLoc, EndLoc)) {
 408           // The region ends in a nested file or macro expansion. Create a
 409           // separate region for each expansion.
 410           SourceLocation NestedLoc = getStartOfFileOrMacro(EndLoc);
 411           assert(SM.isWrittenInSameFile(NestedLoc, EndLoc));
 412
 413           SourceRegions.emplace_back(Region.getCounter(), NestedLoc, EndLoc);
 414
 415           EndLoc = getPreciseTokenLocEnd(getIncludeOrExpansionLoc(EndLoc));
 416           assert(!EndLoc.isInvalid() &&
 417                  "File exit was not handled before popRegions");
 418         }
 419         Region.setEndLoc(EndLoc);
 420
 421         MostRecentLocation = EndLoc;
 422         // If this region happens to span an entire expansion, we need to make
 423         // sure we don't overlap the parent region with it.
 424         if (StartLoc == getStartOfFileOrMacro(StartLoc) &&
 425             EndLoc == getEndOfFileOrMacro(EndLoc))
 426           MostRecentLocation = getIncludeOrExpansionLoc(EndLoc);
 427
 428         assert(SM.isWrittenInSameFile(Region.getStartLoc(), EndLoc));
 429         SourceRegions.push_back(std::move(Region));
 430       }
 431       RegionStack.pop_back();
 432     }
 433   }
 434
 435   /// \brief Return the currently active region.
 436   SourceMappingRegion &getRegion() {
 437     assert(!RegionStack.empty() && "statement has no region");
 438     return RegionStack.back();
 439   }
 440
 441   /// \brief Propagate counts through the children of \c S.
 442   Counter propagateCounts(Counter TopCount, const Stmt *S) {
 443     size_t Index = pushRegion(TopCount, getStart(S), getEnd(S));
 444     Visit(S);
 445     Counter ExitCount = getRegion().getCounter();
 446     popRegions(Index);
 447     return ExitCount;
 448   }
 449
 450   /// \brief Adjust the most recently visited location to \c EndLoc.
 451   ///
 452   /// This should be used after visiting any statements in non-source order.
 453   void adjustForOutOfOrderTraversal(SourceLocation EndLoc) {
 454     MostRecentLocation = EndLoc;
 455     // Avoid adding duplicate regions if we have a completed region on the top
 456     // of the stack and are adjusting to the end of a virtual file.
 457     if (getRegion().hasEndLoc() &&
 458         MostRecentLocation == getEndOfFileOrMacro(MostRecentLocation))
 459       MostRecentLocation = getIncludeOrExpansionLoc(MostRecentLocation);
 460   }
 461
 462   /// \brief Check whether \c Loc is included or expanded from \c Parent.
 463   bool isNestedIn(SourceLocation Loc, FileID Parent) {
 464     do {
 465       Loc = getIncludeOrExpansionLoc(Loc);
 466       if (Loc.isInvalid())
 467         return false;
 468     } while (!SM.isInFileID(Loc, Parent));
 469     return true;
 470   }
 471
 472   /// \brief Adjust regions and state when \c NewLoc exits a file.
 473   ///
 474   /// If moving from our most recently tracked location to \c NewLoc exits any
 475   /// files, this adjusts our current region stack and creates the file regions
 476   /// for the exited file.
 477   void handleFileExit(SourceLocation NewLoc) {
 478     if (SM.isWrittenInSameFile(MostRecentLocation, NewLoc))
 479       return;
 480
 481     // If NewLoc is not in a file that contains MostRecentLocation, walk up to
 482     // find the common ancestor.
 483     SourceLocation LCA = NewLoc;
 484     FileID ParentFile = SM.getFileID(LCA);
 485     while (!isNestedIn(MostRecentLocation, ParentFile)) {
 486       LCA = getIncludeOrExpansionLoc(LCA);
 487       if (LCA.isInvalid() || SM.isWrittenInSameFile(LCA, MostRecentLocation)) {
 488         // Since there isn't a common ancestor, no file was exited. We just need
 489         // to adjust our location to the new file.
 490         MostRecentLocation = NewLoc;
 491         return;
 492       }
 493       ParentFile = SM.getFileID(LCA);
 494     }
 495
 496     llvm::SmallSet<SourceLocation, 8> StartLocs;
 497     Optional<Counter> ParentCounter;
 498     for (auto I = RegionStack.rbegin(), E = RegionStack.rend(); I != E; ++I) {
 499       if (!I->hasStartLoc())
 500         continue;
 501       SourceLocation Loc = I->getStartLoc();
 502       if (!isNestedIn(Loc, ParentFile)) {
 503         ParentCounter = I->getCounter();
 504         break;
 505       }
 506
 507       while (!SM.isInFileID(Loc, ParentFile)) {
 508         // The most nested region for each start location is the one with the
 509         // correct count. We avoid creating redundant regions by stopping once
 510         // we've seen this region.
 511         if (StartLocs.insert(Loc).second)
 512           SourceRegions.emplace_back(I->getCounter(), Loc,
 513                                      getEndOfFileOrMacro(Loc));
 514         Loc = getIncludeOrExpansionLoc(Loc);
 515       }
 516       I->setStartLoc(getPreciseTokenLocEnd(Loc));
 517     }
 518
 519     if (ParentCounter) {
 520       // If the file is contained completely by another region and doesn't
 521       // immediately start its own region, the whole file gets a region
 522       // corresponding to the parent.
 523       SourceLocation Loc = MostRecentLocation;
 524       while (isNestedIn(Loc, ParentFile)) {
 525         SourceLocation FileStart = getStartOfFileOrMacro(Loc);
 526         if (StartLocs.insert(FileStart).second)
 527           SourceRegions.emplace_back(*ParentCounter, FileStart,
 528                                      getEndOfFileOrMacro(Loc));
 529         Loc = getIncludeOrExpansionLoc(Loc);
 530       }
 531     }
 532
 533     MostRecentLocation = NewLoc;
 534   }
 535
 536   /// \brief Ensure that \c S is included in the current region.
 537   void extendRegion(const Stmt *S) {
 538     SourceMappingRegion &Region = getRegion();
 539     SourceLocation StartLoc = getStart(S);
 540
 541     handleFileExit(StartLoc);
 542     if (!Region.hasStartLoc())
 543       Region.setStartLoc(StartLoc);
 544   }
 545
 546   /// \brief Mark \c S as a terminator, starting a zero region.
 547   void terminateRegion(const Stmt *S) {
 548     extendRegion(S);
 549     SourceMappingRegion &Region = getRegion();
 550     if (!Region.hasEndLoc())
 551       Region.setEndLoc(getEnd(S));
 552     pushRegion(Counter::getZero());
 553   }
 554
 555   /// \brief Keep counts of breaks and continues inside loops.
 556   struct BreakContinue {
 557     Counter BreakCount;
 558     Counter ContinueCount;
 559   };
 560   SmallVector<BreakContinue, 8> BreakContinueStack;
 561
 562   CounterCoverageMappingBuilder(
 563       CoverageMappingModuleGen &CVM,
 564       llvm::DenseMap<const Stmt *, unsigned> &CounterMap, SourceManager &SM,
 565       const LangOptions &LangOpts)
 566       : CoverageMappingBuilder(CVM, SM, LangOpts), CounterMap(CounterMap) {}
 567
 568   /// \brief Write the mapping data to the output stream
 569   void write(llvm::raw_ostream &OS) {
 570     llvm::SmallVector<unsigned, 8> VirtualFileMapping;
 571     gatherFileIDs(VirtualFileMapping);
 572     emitSourceRegions();
 573     emitExpansionRegions();
 574     gatherSkippedRegions();
 575
 576     CoverageMappingWriter Writer(VirtualFileMapping, Builder.getExpressions(),
 577                                  MappingRegions);
 578     Writer.write(OS);
 579   }
 580
 581   void VisitStmt(const Stmt *S) {
 582     if (!S->getLocStart().isInvalid())
 583       extendRegion(S);
 584     for (Stmt::const_child_range I = S->children(); I; ++I) {
 585       if (*I)
 586         this->Visit(*I);
 587     }
 588     handleFileExit(getEnd(S));
 589   }
 590
 591   void VisitDecl(const Decl *D) {
 592     Stmt *Body = D->getBody();
 593     propagateCounts(getRegionCounter(Body), Body);
 594   }
 595
 596   void VisitReturnStmt(const ReturnStmt *S) {
 597     extendRegion(S);
 598     if (S->getRetValue())
 599       Visit(S->getRetValue());
 600     terminateRegion(S);
 601   }
 602
 603   void VisitCXXThrowExpr(const CXXThrowExpr *E) {
 604     extendRegion(E);
 605     if (E->getSubExpr())
 606       Visit(E->getSubExpr());
 607     terminateRegion(E);
 608   }
 609
 610   void VisitGotoStmt(const GotoStmt *S) { terminateRegion(S); }
 611
 612   void VisitLabelStmt(const LabelStmt *S) {
 613     SourceLocation Start = getStart(S);
 614     // We can't extendRegion here or we risk overlapping with our new region.
 615     handleFileExit(Start);
 616     pushRegion(getRegionCounter(S), Start);
 617     Visit(S->getSubStmt());
 618   }
 619
 620   void VisitBreakStmt(const BreakStmt *S) {
 621     assert(!BreakContinueStack.empty() && "break not in a loop or switch!");
 622     BreakContinueStack.back().BreakCount = addCounters(
 623         BreakContinueStack.back().BreakCount, getRegion().getCounter());
 624     terminateRegion(S);
 625   }
 626
 627   void VisitContinueStmt(const ContinueStmt *S) {
 628     assert(!BreakContinueStack.empty() && "continue stmt not in a loop!");
 629     BreakContinueStack.back().ContinueCount = addCounters(
 630         BreakContinueStack.back().ContinueCount, getRegion().getCounter());
 631     terminateRegion(S);
 632   }
 633
 634   void VisitWhileStmt(const WhileStmt *S) {
 635     extendRegion(S);
 636
 637     Counter ParentCount = getRegion().getCounter();
 638     Counter BodyCount = getRegionCounter(S);
 639
 640     // Handle the body first so that we can get the backedge count.
 641     BreakContinueStack.push_back(BreakContinue());
 642     extendRegion(S->getBody());
 643     Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
 644     BreakContinue BC = BreakContinueStack.pop_back_val();
 645
 646     // Go back to handle the condition.
 647     Counter CondCount =
 648         addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
 649     propagateCounts(CondCount, S->getCond());
 650     adjustForOutOfOrderTraversal(getEnd(S));
 651
 652     Counter OutCount =
 653         addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount));
 654     if (OutCount != ParentCount)
 655       pushRegion(OutCount);
 656   }
 657
 658   void VisitDoStmt(const DoStmt *S) {
 659     extendRegion(S);
 660
 661     Counter ParentCount = getRegion().getCounter();
 662     Counter BodyCount = getRegionCounter(S);
 663
 664     BreakContinueStack.push_back(BreakContinue());
 665     extendRegion(S->getBody());
 666     Counter BackedgeCount =
 667         propagateCounts(addCounters(ParentCount, BodyCount), S->getBody());
 668     BreakContinue BC = BreakContinueStack.pop_back_val();
 669
 670     Counter CondCount = addCounters(BackedgeCount, BC.ContinueCount);
 671     propagateCounts(CondCount, S->getCond());
 672
 673     Counter OutCount =
 674         addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount));
 675     if (OutCount != ParentCount)
 676       pushRegion(OutCount);
 677   }
 678
 679   void VisitForStmt(const ForStmt *S) {
 680     extendRegion(S);
 681     if (S->getInit())
 682       Visit(S->getInit());
 683
 684     Counter ParentCount = getRegion().getCounter();
 685     Counter BodyCount = getRegionCounter(S);
 686
 687     // Handle the body first so that we can get the backedge count.
 688     BreakContinueStack.push_back(BreakContinue());
 689     extendRegion(S->getBody());
 690     Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
 691     BreakContinue BC = BreakContinueStack.pop_back_val();
 692
 693     // The increment is essentially part of the body but it needs to include
 694     // the count for all the continue statements.
 695     if (const Stmt *Inc = S->getInc())
 696       propagateCounts(addCounters(BackedgeCount, BC.ContinueCount), Inc);
 697
 698     // Go back to handle the condition.
 699     Counter CondCount =
 700         addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
 701     if (const Expr *Cond = S->getCond()) {
 702       propagateCounts(CondCount, Cond);
 703       adjustForOutOfOrderTraversal(getEnd(S));
 704     }
 705
 706     Counter OutCount =
 707         addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount));
 708     if (OutCount != ParentCount)
 709       pushRegion(OutCount);
 710   }
 711
 712   void VisitCXXForRangeStmt(const CXXForRangeStmt *S) {
 713     extendRegion(S);
 714     Visit(S->getLoopVarStmt());
 715     Visit(S->getRangeStmt());
 716
 717     Counter ParentCount = getRegion().getCounter();
 718     Counter BodyCount = getRegionCounter(S);
 719
 720     BreakContinueStack.push_back(BreakContinue());
 721     extendRegion(S->getBody());
 722     Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
 723     BreakContinue BC = BreakContinueStack.pop_back_val();
 724
 725     Counter LoopCount =
 726         addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
 727     Counter OutCount =
 728         addCounters(BC.BreakCount, subtractCounters(LoopCount, BodyCount));
 729     if (OutCount != ParentCount)
 730       pushRegion(OutCount);
 731   }
 732
 733   void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S) {
 734     extendRegion(S);
 735     Visit(S->getElement());
 736
 737     Counter ParentCount = getRegion().getCounter();
 738     Counter BodyCount = getRegionCounter(S);
 739
 740     BreakContinueStack.push_back(BreakContinue());
 741     extendRegion(S->getBody());
 742     Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
 743     BreakContinue BC = BreakContinueStack.pop_back_val();
 744
 745     Counter LoopCount =
 746         addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
 747     Counter OutCount =
 748         addCounters(BC.BreakCount, subtractCounters(LoopCount, BodyCount));
 749     if (OutCount != ParentCount)
 750       pushRegion(OutCount);
 751   }
 752
 753   void VisitSwitchStmt(const SwitchStmt *S) {
 754     extendRegion(S);
 755     Visit(S->getCond());
 756
 757     BreakContinueStack.push_back(BreakContinue());
 758
 759     const Stmt *Body = S->getBody();
 760     extendRegion(Body);
 761     if (const auto *CS = dyn_cast<CompoundStmt>(Body)) {
 762       if (!CS->body_empty()) {
 763         // The body of the switch needs a zero region so that fallthrough counts
 764         // behave correctly, but it would be misleading to include the braces of
 765         // the compound statement in the zeroed area, so we need to handle this
 766         // specially.
 767         size_t Index =
 768             pushRegion(Counter::getZero(), getStart(CS->body_front()),
 769                        getEnd(CS->body_back()));
 770         for (const auto *Child : CS->children())
 771           Visit(Child);
 772         popRegions(Index);
 773       }
 774     } else
 775       propagateCounts(Counter::getZero(), Body);
 776     BreakContinue BC = BreakContinueStack.pop_back_val();
 777
 778     if (!BreakContinueStack.empty())
 779       BreakContinueStack.back().ContinueCount = addCounters(
 780           BreakContinueStack.back().ContinueCount, BC.ContinueCount);
 781
 782     Counter ExitCount = getRegionCounter(S);
 783     pushRegion(ExitCount);
 784   }
 785
 786   void VisitSwitchCase(const SwitchCase *S) {
 787     extendRegion(S);
 788
 789     SourceMappingRegion &Parent = getRegion();
 790
 791     Counter Count = addCounters(Parent.getCounter(), getRegionCounter(S));
 792     // Reuse the existing region if it starts at our label. This is typical of
 793     // the first case in a switch.
 794     if (Parent.hasStartLoc() && Parent.getStartLoc() == getStart(S))
 795       Parent.setCounter(Count);
 796     else
 797       pushRegion(Count, getStart(S));
 798
 799     if (const CaseStmt *CS = dyn_cast<CaseStmt>(S)) {
 800       Visit(CS->getLHS());
 801       if (const Expr *RHS = CS->getRHS())
 802         Visit(RHS);
 803     }
 804     Visit(S->getSubStmt());
 805   }
 806
 807   void VisitIfStmt(const IfStmt *S) {
 808     extendRegion(S);
 809
 810     Counter ParentCount = getRegion().getCounter();
 811     Counter ThenCount = getRegionCounter(S);
 812
 813     // Emitting a counter for the condition makes it easier to interpret the
 814     // counter for the body when looking at the coverage.
 815     propagateCounts(ParentCount, S->getCond());
 816
 817     extendRegion(S->getThen());
 818     Counter OutCount = propagateCounts(ThenCount, S->getThen());
 819
 820     Counter ElseCount = subtractCounters(ParentCount, ThenCount);
 821     if (const Stmt *Else = S->getElse()) {
 822       extendRegion(S->getElse());
 823       OutCount = addCounters(OutCount, propagateCounts(ElseCount, Else));
 824     } else
 825       OutCount = addCounters(OutCount, ElseCount);
 826
 827     if (OutCount != ParentCount)
 828       pushRegion(OutCount);
 829   }
 830
 831   void VisitCXXTryStmt(const CXXTryStmt *S) {
 832     extendRegion(S);
 833     Visit(S->getTryBlock());
 834     for (unsigned I = 0, E = S->getNumHandlers(); I < E; ++I)
 835       Visit(S->getHandler(I));
 836
 837     Counter ExitCount = getRegionCounter(S);
 838     pushRegion(ExitCount);
 839   }
 840
 841   void VisitCXXCatchStmt(const CXXCatchStmt *S) {
 842     extendRegion(S);
 843     propagateCounts(getRegionCounter(S), S->getHandlerBlock());
 844   }
 845
 846   void VisitAbstractConditionalOperator(const AbstractConditionalOperator *E) {
 847     extendRegion(E);
 848
 849     Counter ParentCount = getRegion().getCounter();
 850     Counter TrueCount = getRegionCounter(E);
 851
 852     Visit(E->getCond());
 853
 854     if (!isa<BinaryConditionalOperator>(E)) {
 855       extendRegion(E->getTrueExpr());
 856       propagateCounts(TrueCount, E->getTrueExpr());
 857     }
 858     extendRegion(E->getFalseExpr());
 859     propagateCounts(subtractCounters(ParentCount, TrueCount),
 860                     E->getFalseExpr());
 861   }
 862
 863   void VisitBinLAnd(const BinaryOperator *E) {
 864     extendRegion(E);
 865     Visit(E->getLHS());
 866
 867     extendRegion(E->getRHS());
 868     propagateCounts(getRegionCounter(E), E->getRHS());
 869   }
 870
 871   void VisitBinLOr(const BinaryOperator *E) {
 872     extendRegion(E);
 873     Visit(E->getLHS());
 874
 875     extendRegion(E->getRHS());
 876     propagateCounts(getRegionCounter(E), E->getRHS());
 877   }
 878
 879   void VisitLambdaExpr(const LambdaExpr *LE) {
 880     // Lambdas are treated as their own functions for now, so we shouldn't
 881     // propagate counts into them.
 882   }
 883 };
 884 }
 885
 886 static bool isMachO(const CodeGenModule &CGM) {
 887   return CGM.getTarget().getTriple().isOSBinFormatMachO();
 888 }
 889
 890 static StringRef getCoverageSection(const CodeGenModule &CGM) {
 891   return isMachO(CGM) ? "__DATA,__llvm_covmap" : "__llvm_covmap";
 892 }
 893
 894 static void dump(llvm::raw_ostream &OS, StringRef FunctionName,
 895                  ArrayRef<CounterExpression> Expressions,
 896                  ArrayRef<CounterMappingRegion> Regions) {
 897   OS << FunctionName << ":\n";
 898   CounterMappingContext Ctx(Expressions);
 899   for (const auto &R : Regions) {
 900     OS.indent(2);
 901     switch (R.Kind) {
 902     case CounterMappingRegion::CodeRegion:
 903       break;
 904     case CounterMappingRegion::ExpansionRegion:
 905       OS << "Expansion,";
 906       break;
 907     case CounterMappingRegion::SkippedRegion:
 908       OS << "Skipped,";
 909       break;
 910     }
 911
 912     OS << "File " << R.FileID << ", " << R.LineStart << ":" << R.ColumnStart
 913        << " -> " << R.LineEnd << ":" << R.ColumnEnd << " = ";
 914     Ctx.dump(R.Count, OS);
 915     if (R.Kind == CounterMappingRegion::ExpansionRegion)
 916       OS << " (Expanded file = " << R.ExpandedFileID << ")";
 917     OS << "\n";
 918   }
 919 }
 920
 921 void CoverageMappingModuleGen::addFunctionMappingRecord(
 922     llvm::GlobalVariable *FunctionName, StringRef FunctionNameValue,
 923     uint64_t FunctionHash, const std::string &CoverageMapping) {
 924   llvm::LLVMContext &Ctx = CGM.getLLVMContext();
 925   auto *Int32Ty = llvm::Type::getInt32Ty(Ctx);
 926   auto *Int64Ty = llvm::Type::getInt64Ty(Ctx);
 927   auto *Int8PtrTy = llvm::Type::getInt8PtrTy(Ctx);
 928   if (!FunctionRecordTy) {
 929     llvm::Type *FunctionRecordTypes[] = {Int8PtrTy, Int32Ty, Int32Ty, Int64Ty};
 930     FunctionRecordTy =
 931         llvm::StructType::get(Ctx, makeArrayRef(FunctionRecordTypes));
 932   }
 933
 934   llvm::Constant *FunctionRecordVals[] = {
 935       llvm::ConstantExpr::getBitCast(FunctionName, Int8PtrTy),
 936       llvm::ConstantInt::get(Int32Ty, FunctionNameValue.size()),
 937       llvm::ConstantInt::get(Int32Ty, CoverageMapping.size()),
 938       llvm::ConstantInt::get(Int64Ty, FunctionHash)};
 939   FunctionRecords.push_back(llvm::ConstantStruct::get(
 940       FunctionRecordTy, makeArrayRef(FunctionRecordVals)));
 941   CoverageMappings += CoverageMapping;
 942
 943   if (CGM.getCodeGenOpts().DumpCoverageMapping) {
 944     // Dump the coverage mapping data for this function by decoding the
 945     // encoded data. This allows us to dump the mapping regions which were
 946     // also processed by the CoverageMappingWriter which performs
 947     // additional minimization operations such as reducing the number of
 948     // expressions.
 949     std::vector<StringRef> Filenames;
 950     std::vector<CounterExpression> Expressions;
 951     std::vector<CounterMappingRegion> Regions;
 952     llvm::SmallVector<StringRef, 16> FilenameRefs;
 953     FilenameRefs.resize(FileEntries.size());
 954     for (const auto &Entry : FileEntries)
 955       FilenameRefs[Entry.second] = Entry.first->getName();
 956     RawCoverageMappingReader Reader(CoverageMapping, FilenameRefs, Filenames,
 957                                     Expressions, Regions);
 958     if (Reader.read())
 959       return;
 960     dump(llvm::outs(), FunctionNameValue, Expressions, Regions);
 961   }
 962 }
 963
 964 void CoverageMappingModuleGen::emit() {
 965   if (FunctionRecords.empty())
 966     return;
 967   llvm::LLVMContext &Ctx = CGM.getLLVMContext();
 968   auto *Int32Ty = llvm::Type::getInt32Ty(Ctx);
 969
 970   // Create the filenames and merge them with coverage mappings
 971   llvm::SmallVector<std::string, 16> FilenameStrs;
 972   llvm::SmallVector<StringRef, 16> FilenameRefs;
 973   FilenameStrs.resize(FileEntries.size());
 974   FilenameRefs.resize(FileEntries.size());
 975   for (const auto &Entry : FileEntries) {
 976     llvm::SmallString<256> Path(Entry.first->getName());
 977     llvm::sys::fs::make_absolute(Path);
 978
 979     auto I = Entry.second;
 980     FilenameStrs[I] = std::string(Path.begin(), Path.end());
 981     FilenameRefs[I] = FilenameStrs[I];
 982   }
 983
 984   std::string FilenamesAndCoverageMappings;
 985   llvm::raw_string_ostream OS(FilenamesAndCoverageMappings);
 986   CoverageFilenamesSectionWriter(FilenameRefs).write(OS);
 987   OS << CoverageMappings;
 988   size_t CoverageMappingSize = CoverageMappings.size();
 989   size_t FilenamesSize = OS.str().size() - CoverageMappingSize;
 990   // Append extra zeroes if necessary to ensure that the size of the filenames
 991   // and coverage mappings is a multiple of 8.
 992   if (size_t Rem = OS.str().size() % 8) {
 993     CoverageMappingSize += 8 - Rem;
 994     for (size_t I = 0, S = 8 - Rem; I < S; ++I)
 995       OS << '\0';
 996   }
 997   auto *FilenamesAndMappingsVal =
 998       llvm::ConstantDataArray::getString(Ctx, OS.str(), false);
 999
1000   // Create the deferred function records array
1001   auto RecordsTy =
1002       llvm::ArrayType::get(FunctionRecordTy, FunctionRecords.size());
1003   auto RecordsVal = llvm::ConstantArray::get(RecordsTy, FunctionRecords);
1004
1005   // Create the coverage data record
1006   llvm::Type *CovDataTypes[] = {Int32Ty,   Int32Ty,
1007                                 Int32Ty,   Int32Ty,
1008                                 RecordsTy, FilenamesAndMappingsVal->getType()};
1009   auto CovDataTy = llvm::StructType::get(Ctx, makeArrayRef(CovDataTypes));
1010   llvm::Constant *TUDataVals[] = {
1011       llvm::ConstantInt::get(Int32Ty, FunctionRecords.size()),
1012       llvm::ConstantInt::get(Int32Ty, FilenamesSize),
1013       llvm::ConstantInt::get(Int32Ty, CoverageMappingSize),
1014       llvm::ConstantInt::get(Int32Ty,
1015                              /*Version=*/CoverageMappingVersion1),
1016       RecordsVal, FilenamesAndMappingsVal};
1017   auto CovDataVal =
1018       llvm::ConstantStruct::get(CovDataTy, makeArrayRef(TUDataVals));
1019   auto CovData = new llvm::GlobalVariable(CGM.getModule(), CovDataTy, true,
1020                                           llvm::GlobalValue::InternalLinkage,
1021                                           CovDataVal,
1022                                           "__llvm_coverage_mapping");
1023
1024   CovData->setSection(getCoverageSection(CGM));
1025   CovData->setAlignment(8);
1026
1027   // Make sure the data doesn't get deleted.
1028   CGM.addUsedGlobal(CovData);
1029 }
1030
1031 unsigned CoverageMappingModuleGen::getFileID(const FileEntry *File) {
1032   auto It = FileEntries.find(File);
1033   if (It != FileEntries.end())
1034     return It->second;
1035   unsigned FileID = FileEntries.size();
1036   FileEntries.insert(std::make_pair(File, FileID));
1037   return FileID;
1038 }
1039
1040 void CoverageMappingGen::emitCounterMapping(const Decl *D,
1041                                             llvm::raw_ostream &OS) {
1042   assert(CounterMap);
1043   CounterCoverageMappingBuilder Walker(CVM, *CounterMap, SM, LangOpts);
1044   Walker.VisitDecl(D);
1045   Walker.write(OS);
1046 }
1047
1048 void CoverageMappingGen::emitEmptyMapping(const Decl *D,
1049                                           llvm::raw_ostream &OS) {
1050   EmptyCoverageMappingBuilder Walker(CVM, SM, LangOpts);
1051   Walker.VisitDecl(D);
1052   Walker.write(OS);
1053 }