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