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