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