1 //===--- CoverageMappingGen.cpp - Coverage mapping generation ---*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Instrumentation-based code coverage mapping generator
12 //===----------------------------------------------------------------------===//
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"
25 using namespace clang;
26 using namespace CodeGen;
27 using namespace llvm::coverage;
29 void CoverageSourceInfo::SourceRangeSkipped(SourceRange Range) {
30 SkippedRanges.push_back(Range);
35 /// \brief A region of source code that can be mapped to a counter.
36 class SourceMappingRegion {
39 /// \brief The region's starting location.
40 Optional<SourceLocation> LocStart;
42 /// \brief The region's ending location.
43 Optional<SourceLocation> LocEnd;
46 SourceMappingRegion(Counter Count, Optional<SourceLocation> LocStart,
47 Optional<SourceLocation> LocEnd)
48 : Count(Count), LocStart(LocStart), LocEnd(LocEnd) {}
50 SourceMappingRegion(SourceMappingRegion &&Region)
51 : Count(std::move(Region.Count)), LocStart(std::move(Region.LocStart)),
52 LocEnd(std::move(Region.LocEnd)) {}
54 SourceMappingRegion &operator=(SourceMappingRegion &&RHS) {
55 Count = std::move(RHS.Count);
56 LocStart = std::move(RHS.LocStart);
57 LocEnd = std::move(RHS.LocEnd);
61 const Counter &getCounter() const { return Count; }
63 void setCounter(Counter C) { Count = C; }
65 bool hasStartLoc() const { return LocStart.hasValue(); }
67 void setStartLoc(SourceLocation Loc) { LocStart = Loc; }
69 const SourceLocation &getStartLoc() const {
70 assert(LocStart && "Region has no start location");
74 bool hasEndLoc() const { return LocEnd.hasValue(); }
76 void setEndLoc(SourceLocation Loc) { LocEnd = Loc; }
78 const SourceLocation &getEndLoc() const {
79 assert(LocEnd && "Region has no end location");
84 /// \brief Provides the common functionality for the different
85 /// coverage mapping region builders.
86 class CoverageMappingBuilder {
88 CoverageMappingModuleGen &CVM;
90 const LangOptions &LangOpts;
93 /// \brief Map of clang's FileIDs to IDs used for coverage mapping.
94 llvm::SmallDenseMap<FileID, std::pair<unsigned, SourceLocation>, 8>
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;
103 CoverageMappingBuilder(CoverageMappingModuleGen &CVM, SourceManager &SM,
104 const LangOptions &LangOpts)
105 : CVM(CVM), SM(SM), LangOpts(LangOpts) {}
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.
112 Lexer::MeasureTokenLength(SM.getSpellingLoc(Loc), SM, LangOpts);
113 return Loc.getLocWithOffset(TokLen);
116 /// \brief Return the start location of an included file or expanded macro.
117 SourceLocation getStartOfFileOrMacro(SourceLocation Loc) {
119 return Loc.getLocWithOffset(-SM.getFileOffset(Loc));
120 return SM.getLocForStartOfFile(SM.getFileID(Loc));
123 /// \brief Return the end location of an included file or expanded macro.
124 SourceLocation getEndOfFileOrMacro(SourceLocation Loc) {
126 return Loc.getLocWithOffset(SM.getFileIDSize(SM.getFileID(Loc)) -
127 SM.getFileOffset(Loc));
128 return SM.getLocForEndOfFile(SM.getFileID(Loc));
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));
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;
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;
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);
158 /// \brief Find the set of files we have regions for and assign IDs
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();
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())
173 Visited.push_back(File);
176 for (SourceLocation Parent = getIncludeOrExpansionLoc(Loc);
177 !Parent.isInvalid(); Parent = getIncludeOrExpansionLoc(Parent))
179 FileLocs.push_back(std::make_pair(Loc, Depth));
181 std::stable_sort(FileLocs.begin(), FileLocs.end(), llvm::less_second());
183 for (const auto &FL : FileLocs) {
184 SourceLocation Loc = FL.first;
185 FileID SpellingFile = SM.getDecomposedSpellingLoc(Loc).first;
186 auto Entry = SM.getFileEntryForID(SpellingFile);
190 FileIDMapping[SM.getFileID(Loc)] = std::make_pair(Mapping.size(), Loc);
191 Mapping.push_back(CVM.getFileID(Entry));
195 /// \brief Get the coverage mapping file ID for \c Loc.
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;
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);
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);
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");
234 auto CovFileID = getCoverageFileID(LocStart);
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);
251 /// \brief Generate the coverage counter mapping regions from collected
253 void emitSourceRegions() {
254 for (const auto &Region : SourceRegions) {
255 assert(Region.hasEndLoc() && "incomplete region");
257 SourceLocation LocStart = Region.getStartLoc();
258 assert(!SM.getFileID(LocStart).isInvalid() && "region in invalid file");
260 auto CovFileID = getCoverageFileID(LocStart);
261 // Ignore regions that don't have a file, such as builtin macros.
265 SourceLocation LocEnd = Region.getEndLoc();
266 assert(SM.isWrittenInSameFile(LocStart, LocEnd) &&
267 "region spans multiple files");
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);
275 assert(LineStart <= LineEnd && "region start and end out of order");
276 MappingRegions.push_back(CounterMappingRegion::makeRegion(
277 Region.getCounter(), *CovFileID, LineStart, ColumnStart, LineEnd,
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())
290 auto ParentFileID = getCoverageFileID(ParentLoc);
293 auto ExpandedFileID = getCoverageFileID(ExpandedLoc);
294 assert(ExpandedFileID && "expansion in uncovered file");
296 SourceLocation LocEnd = getPreciseTokenLocEnd(ParentLoc);
297 assert(SM.isWrittenInSameFile(ParentLoc, LocEnd) &&
298 "region spans multiple files");
300 unsigned LineStart = SM.getSpellingLineNumber(ParentLoc);
301 unsigned ColumnStart = SM.getSpellingColumnNumber(ParentLoc);
302 unsigned LineEnd = SM.getSpellingLineNumber(LocEnd);
303 unsigned ColumnEnd = SM.getSpellingColumnNumber(LocEnd);
305 MappingRegions.push_back(CounterMappingRegion::makeExpansion(
306 *ParentFileID, *ExpandedFileID, LineStart, ColumnStart, LineEnd,
312 /// \brief Creates unreachable coverage regions for the functions that
314 struct EmptyCoverageMappingBuilder : public CoverageMappingBuilder {
315 EmptyCoverageMappingBuilder(CoverageMappingModuleGen &CVM, SourceManager &SM,
316 const LangOptions &LangOpts)
317 : CoverageMappingBuilder(CVM, SM, LangOpts) {}
319 void VisitDecl(const Decl *D) {
322 auto Body = D->getBody();
323 SourceRegions.emplace_back(Counter(), getStart(Body), getEnd(Body));
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);
332 CoverageMappingWriter Writer(FileIDMapping, None, MappingRegions);
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;
345 /// \brief A stack of currently live regions.
346 std::vector<SourceMappingRegion> RegionStack;
348 CounterExpressionBuilder Builder;
350 /// \brief A location in the most recently visited file or macro.
352 /// This is used to adjust the active source regions appropriately when
353 /// expressions cross file or macro boundaries.
354 SourceLocation MostRecentLocation;
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);
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);
366 Counter addCounters(Counter C1, Counter C2, Counter C3) {
367 return addCounters(addCounters(C1, C2), C3);
370 Counter addCounters(Counter C1, Counter C2, Counter C3, Counter C4) {
371 return addCounters(addCounters(C1, C2, C3), C4);
374 /// \brief Return the region counter for the given statement.
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]);
381 /// \brief Push a region onto the stack.
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) {
388 MostRecentLocation = *StartLoc;
389 RegionStack.emplace_back(Count, StartLoc, EndLoc);
391 return RegionStack.size() - 1;
394 /// \brief Pop regions from the stack into the function's list of regions.
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()
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));
413 SourceRegions.emplace_back(Region.getCounter(), NestedLoc, EndLoc);
415 EndLoc = getPreciseTokenLocEnd(getIncludeOrExpansionLoc(EndLoc));
416 assert(!EndLoc.isInvalid() &&
417 "File exit was not handled before popRegions");
419 Region.setEndLoc(EndLoc);
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);
428 assert(SM.isWrittenInSameFile(Region.getStartLoc(), EndLoc));
429 SourceRegions.push_back(std::move(Region));
431 RegionStack.pop_back();
435 /// \brief Return the currently active region.
436 SourceMappingRegion &getRegion() {
437 assert(!RegionStack.empty() && "statement has no region");
438 return RegionStack.back();
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));
445 Counter ExitCount = getRegion().getCounter();
450 /// \brief Adjust the most recently visited location to \c EndLoc.
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);
462 /// \brief Check whether \c Loc is included or expanded from \c Parent.
463 bool isNestedIn(SourceLocation Loc, FileID Parent) {
465 Loc = getIncludeOrExpansionLoc(Loc);
468 } while (!SM.isInFileID(Loc, Parent));
472 /// \brief Adjust regions and state when \c NewLoc exits a file.
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))
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;
494 ParentFile = SM.getFileID(LCA);
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())
502 SourceLocation Loc = I->getStartLoc();
503 if (!isNestedIn(Loc, ParentFile)) {
504 ParentCounter = I->getCounter();
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);
517 I->setStartLoc(getPreciseTokenLocEnd(Loc));
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);
534 MostRecentLocation = NewLoc;
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);
542 handleFileExit(StartLoc);
543 if (!Region.hasStartLoc())
544 Region.setStartLoc(StartLoc);
547 /// \brief Mark \c S as a terminator, starting a zero region.
548 void terminateRegion(const Stmt *S) {
550 SourceMappingRegion &Region = getRegion();
551 if (!Region.hasEndLoc())
552 Region.setEndLoc(getEnd(S));
553 pushRegion(Counter::getZero());
556 /// \brief Keep counts of breaks and continues inside loops.
557 struct BreakContinue {
559 Counter ContinueCount;
561 SmallVector<BreakContinue, 8> BreakContinueStack;
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) {}
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);
574 emitExpansionRegions();
575 gatherSkippedRegions();
577 CoverageMappingWriter Writer(VirtualFileMapping, Builder.getExpressions(),
582 void VisitStmt(const Stmt *S) {
583 if (!S->getLocStart().isInvalid())
585 for (const Stmt *Child : S->children())
588 handleFileExit(getEnd(S));
591 void VisitDecl(const Decl *D) {
592 Stmt *Body = D->getBody();
593 propagateCounts(getRegionCounter(Body), Body);
596 void VisitReturnStmt(const ReturnStmt *S) {
598 if (S->getRetValue())
599 Visit(S->getRetValue());
603 void VisitCXXThrowExpr(const CXXThrowExpr *E) {
606 Visit(E->getSubExpr());
610 void VisitGotoStmt(const GotoStmt *S) { terminateRegion(S); }
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());
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());
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());
634 void VisitWhileStmt(const WhileStmt *S) {
637 Counter ParentCount = getRegion().getCounter();
638 Counter BodyCount = getRegionCounter(S);
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();
646 // Go back to handle the condition.
648 addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
649 propagateCounts(CondCount, S->getCond());
650 adjustForOutOfOrderTraversal(getEnd(S));
653 addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount));
654 if (OutCount != ParentCount)
655 pushRegion(OutCount);
658 void VisitDoStmt(const DoStmt *S) {
661 Counter ParentCount = getRegion().getCounter();
662 Counter BodyCount = getRegionCounter(S);
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();
670 Counter CondCount = addCounters(BackedgeCount, BC.ContinueCount);
671 propagateCounts(CondCount, S->getCond());
674 addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount));
675 if (OutCount != ParentCount)
676 pushRegion(OutCount);
679 void VisitForStmt(const ForStmt *S) {
684 Counter ParentCount = getRegion().getCounter();
685 Counter BodyCount = getRegionCounter(S);
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();
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);
698 // Go back to handle the condition.
700 addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
701 if (const Expr *Cond = S->getCond()) {
702 propagateCounts(CondCount, Cond);
703 adjustForOutOfOrderTraversal(getEnd(S));
707 addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount));
708 if (OutCount != ParentCount)
709 pushRegion(OutCount);
712 void VisitCXXForRangeStmt(const CXXForRangeStmt *S) {
714 Visit(S->getLoopVarStmt());
715 Visit(S->getRangeStmt());
717 Counter ParentCount = getRegion().getCounter();
718 Counter BodyCount = getRegionCounter(S);
720 BreakContinueStack.push_back(BreakContinue());
721 extendRegion(S->getBody());
722 Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
723 BreakContinue BC = BreakContinueStack.pop_back_val();
726 addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
728 addCounters(BC.BreakCount, subtractCounters(LoopCount, BodyCount));
729 if (OutCount != ParentCount)
730 pushRegion(OutCount);
733 void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S) {
735 Visit(S->getElement());
737 Counter ParentCount = getRegion().getCounter();
738 Counter BodyCount = getRegionCounter(S);
740 BreakContinueStack.push_back(BreakContinue());
741 extendRegion(S->getBody());
742 Counter BackedgeCount = propagateCounts(BodyCount, S->getBody());
743 BreakContinue BC = BreakContinueStack.pop_back_val();
746 addCounters(ParentCount, BackedgeCount, BC.ContinueCount);
748 addCounters(BC.BreakCount, subtractCounters(LoopCount, BodyCount));
749 if (OutCount != ParentCount)
750 pushRegion(OutCount);
753 void VisitSwitchStmt(const SwitchStmt *S) {
757 BreakContinueStack.push_back(BreakContinue());
759 const Stmt *Body = S->getBody();
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
768 pushRegion(Counter::getZero(), getStart(CS->body_front()),
769 getEnd(CS->body_back()));
770 for (const auto *Child : CS->children())
775 propagateCounts(Counter::getZero(), Body);
776 BreakContinue BC = BreakContinueStack.pop_back_val();
778 if (!BreakContinueStack.empty())
779 BreakContinueStack.back().ContinueCount = addCounters(
780 BreakContinueStack.back().ContinueCount, BC.ContinueCount);
782 Counter ExitCount = getRegionCounter(S);
783 pushRegion(ExitCount);
786 void VisitSwitchCase(const SwitchCase *S) {
789 SourceMappingRegion &Parent = getRegion();
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);
797 pushRegion(Count, getStart(S));
799 if (const CaseStmt *CS = dyn_cast<CaseStmt>(S)) {
801 if (const Expr *RHS = CS->getRHS())
804 Visit(S->getSubStmt());
807 void VisitIfStmt(const IfStmt *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());
813 Counter ParentCount = getRegion().getCounter();
814 Counter ThenCount = getRegionCounter(S);
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());
820 extendRegion(S->getThen());
821 Counter OutCount = propagateCounts(ThenCount, S->getThen());
823 Counter ElseCount = subtractCounters(ParentCount, ThenCount);
824 if (const Stmt *Else = S->getElse()) {
825 extendRegion(S->getElse());
826 OutCount = addCounters(OutCount, propagateCounts(ElseCount, Else));
828 OutCount = addCounters(OutCount, ElseCount);
830 if (OutCount != ParentCount)
831 pushRegion(OutCount);
834 void VisitCXXTryStmt(const CXXTryStmt *S) {
836 Visit(S->getTryBlock());
837 for (unsigned I = 0, E = S->getNumHandlers(); I < E; ++I)
838 Visit(S->getHandler(I));
840 Counter ExitCount = getRegionCounter(S);
841 pushRegion(ExitCount);
844 void VisitCXXCatchStmt(const CXXCatchStmt *S) {
846 propagateCounts(getRegionCounter(S), S->getHandlerBlock());
849 void VisitAbstractConditionalOperator(const AbstractConditionalOperator *E) {
852 Counter ParentCount = getRegion().getCounter();
853 Counter TrueCount = getRegionCounter(E);
857 if (!isa<BinaryConditionalOperator>(E)) {
858 extendRegion(E->getTrueExpr());
859 propagateCounts(TrueCount, E->getTrueExpr());
861 extendRegion(E->getFalseExpr());
862 propagateCounts(subtractCounters(ParentCount, TrueCount),
866 void VisitBinLAnd(const BinaryOperator *E) {
870 extendRegion(E->getRHS());
871 propagateCounts(getRegionCounter(E), E->getRHS());
874 void VisitBinLOr(const BinaryOperator *E) {
878 extendRegion(E->getRHS());
879 propagateCounts(getRegionCounter(E), E->getRHS());
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.
889 static bool isMachO(const CodeGenModule &CGM) {
890 return CGM.getTarget().getTriple().isOSBinFormatMachO();
893 static StringRef getCoverageSection(const CodeGenModule &CGM) {
894 return isMachO(CGM) ? "__DATA,__llvm_covmap" : "__llvm_covmap";
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) {
905 case CounterMappingRegion::CodeRegion:
907 case CounterMappingRegion::ExpansionRegion:
910 case CounterMappingRegion::SkippedRegion:
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 << ")";
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};
934 llvm::StructType::get(Ctx, makeArrayRef(FunctionRecordTypes),
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;
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
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);
964 dump(llvm::outs(), FunctionNameValue, Expressions, Regions);
968 void CoverageMappingModuleGen::emit() {
969 if (FunctionRecords.empty())
971 llvm::LLVMContext &Ctx = CGM.getLLVMContext();
972 auto *Int32Ty = llvm::Type::getInt32Ty(Ctx);
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);
983 auto I = Entry.second;
984 FilenameStrs[I] = std::string(Path.begin(), Path.end());
985 FilenameRefs[I] = FilenameStrs[I];
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)
1001 auto *FilenamesAndMappingsVal =
1002 llvm::ConstantDataArray::getString(Ctx, OS.str(), false);
1004 // Create the deferred function records array
1006 llvm::ArrayType::get(FunctionRecordTy, FunctionRecords.size());
1007 auto RecordsVal = llvm::ConstantArray::get(RecordsTy, FunctionRecords);
1009 // Create the coverage data record
1010 llvm::Type *CovDataTypes[] = {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};
1022 llvm::ConstantStruct::get(CovDataTy, makeArrayRef(TUDataVals));
1023 auto CovData = new llvm::GlobalVariable(CGM.getModule(), CovDataTy, true,
1024 llvm::GlobalValue::InternalLinkage,
1026 "__llvm_coverage_mapping");
1028 CovData->setSection(getCoverageSection(CGM));
1029 CovData->setAlignment(8);
1031 // Make sure the data doesn't get deleted.
1032 CGM.addUsedGlobal(CovData);
1035 unsigned CoverageMappingModuleGen::getFileID(const FileEntry *File) {
1036 auto It = FileEntries.find(File);
1037 if (It != FileEntries.end())
1039 unsigned FileID = FileEntries.size();
1040 FileEntries.insert(std::make_pair(File, FileID));
1044 void CoverageMappingGen::emitCounterMapping(const Decl *D,
1045 llvm::raw_ostream &OS) {
1047 CounterCoverageMappingBuilder Walker(CVM, *CounterMap, SM, LangOpts);
1048 Walker.VisitDecl(D);
1052 void CoverageMappingGen::emitEmptyMapping(const Decl *D,
1053 llvm::raw_ostream &OS) {
1054 EmptyCoverageMappingBuilder Walker(CVM, SM, LangOpts);
1055 Walker.VisitDecl(D);