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