1 //===--- CoverageMappingGen.cpp - Coverage mapping generation ---*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // Instrumentation-based code coverage mapping generator 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "CoverageMappingGen.h" 14 #include "CodeGenFunction.h" 15 #include "clang/AST/StmtVisitor.h" 16 #include "clang/Basic/Diagnostic.h" 17 #include "clang/Basic/FileManager.h" 18 #include "clang/Frontend/FrontendDiagnostic.h" 19 #include "clang/Lex/Lexer.h" 20 #include "llvm/ADT/Optional.h" 21 #include "llvm/ADT/SmallSet.h" 22 #include "llvm/ADT/StringExtras.h" 23 #include "llvm/ProfileData/Coverage/CoverageMapping.h" 24 #include "llvm/ProfileData/Coverage/CoverageMappingReader.h" 25 #include "llvm/ProfileData/Coverage/CoverageMappingWriter.h" 26 #include "llvm/ProfileData/InstrProfReader.h" 27 #include "llvm/Support/FileSystem.h" 28 #include "llvm/Support/Path.h" 29 30 // This selects the coverage mapping format defined when `InstrProfData.inc` 31 // is textually included. 32 #define COVMAP_V3 33 34 using namespace clang; 35 using namespace CodeGen; 36 using namespace llvm::coverage; 37 38 void CoverageSourceInfo::SourceRangeSkipped(SourceRange Range, SourceLocation) { 39 SkippedRanges.push_back(Range); 40 } 41 42 namespace { 43 44 /// A region of source code that can be mapped to a counter. 45 class SourceMappingRegion { 46 Counter Count; 47 48 /// The region's starting location. 49 Optional<SourceLocation> LocStart; 50 51 /// The region's ending location. 52 Optional<SourceLocation> LocEnd; 53 54 /// Whether this region should be emitted after its parent is emitted. 55 bool DeferRegion; 56 57 /// Whether this region is a gap region. The count from a gap region is set 58 /// as the line execution count if there are no other regions on the line. 59 bool GapRegion; 60 61 public: 62 SourceMappingRegion(Counter Count, Optional<SourceLocation> LocStart, 63 Optional<SourceLocation> LocEnd, bool DeferRegion = false, 64 bool GapRegion = false) 65 : Count(Count), LocStart(LocStart), LocEnd(LocEnd), 66 DeferRegion(DeferRegion), GapRegion(GapRegion) {} 67 68 const Counter &getCounter() const { return Count; } 69 70 void setCounter(Counter C) { Count = C; } 71 72 bool hasStartLoc() const { return LocStart.hasValue(); } 73 74 void setStartLoc(SourceLocation Loc) { LocStart = Loc; } 75 76 SourceLocation getBeginLoc() const { 77 assert(LocStart && "Region has no start location"); 78 return *LocStart; 79 } 80 81 bool hasEndLoc() const { return LocEnd.hasValue(); } 82 83 void setEndLoc(SourceLocation Loc) { 84 assert(Loc.isValid() && "Setting an invalid end location"); 85 LocEnd = Loc; 86 } 87 88 SourceLocation getEndLoc() const { 89 assert(LocEnd && "Region has no end location"); 90 return *LocEnd; 91 } 92 93 bool isDeferred() const { return DeferRegion; } 94 95 void setDeferred(bool Deferred) { DeferRegion = Deferred; } 96 97 bool isGap() const { return GapRegion; } 98 99 void setGap(bool Gap) { GapRegion = Gap; } 100 }; 101 102 /// Spelling locations for the start and end of a source region. 103 struct SpellingRegion { 104 /// The line where the region starts. 105 unsigned LineStart; 106 107 /// The column where the region starts. 108 unsigned ColumnStart; 109 110 /// The line where the region ends. 111 unsigned LineEnd; 112 113 /// The column where the region ends. 114 unsigned ColumnEnd; 115 116 SpellingRegion(SourceManager &SM, SourceLocation LocStart, 117 SourceLocation LocEnd) { 118 LineStart = SM.getSpellingLineNumber(LocStart); 119 ColumnStart = SM.getSpellingColumnNumber(LocStart); 120 LineEnd = SM.getSpellingLineNumber(LocEnd); 121 ColumnEnd = SM.getSpellingColumnNumber(LocEnd); 122 } 123 124 SpellingRegion(SourceManager &SM, SourceMappingRegion &R) 125 : SpellingRegion(SM, R.getBeginLoc(), R.getEndLoc()) {} 126 127 /// Check if the start and end locations appear in source order, i.e 128 /// top->bottom, left->right. 129 bool isInSourceOrder() const { 130 return (LineStart < LineEnd) || 131 (LineStart == LineEnd && ColumnStart <= ColumnEnd); 132 } 133 }; 134 135 /// Provides the common functionality for the different 136 /// coverage mapping region builders. 137 class CoverageMappingBuilder { 138 public: 139 CoverageMappingModuleGen &CVM; 140 SourceManager &SM; 141 const LangOptions &LangOpts; 142 143 private: 144 /// Map of clang's FileIDs to IDs used for coverage mapping. 145 llvm::SmallDenseMap<FileID, std::pair<unsigned, SourceLocation>, 8> 146 FileIDMapping; 147 148 public: 149 /// The coverage mapping regions for this function 150 llvm::SmallVector<CounterMappingRegion, 32> MappingRegions; 151 /// The source mapping regions for this function. 152 std::vector<SourceMappingRegion> SourceRegions; 153 154 /// A set of regions which can be used as a filter. 155 /// 156 /// It is produced by emitExpansionRegions() and is used in 157 /// emitSourceRegions() to suppress producing code regions if 158 /// the same area is covered by expansion regions. 159 typedef llvm::SmallSet<std::pair<SourceLocation, SourceLocation>, 8> 160 SourceRegionFilter; 161 162 CoverageMappingBuilder(CoverageMappingModuleGen &CVM, SourceManager &SM, 163 const LangOptions &LangOpts) 164 : CVM(CVM), SM(SM), LangOpts(LangOpts) {} 165 166 /// Return the precise end location for the given token. 167 SourceLocation getPreciseTokenLocEnd(SourceLocation Loc) { 168 // We avoid getLocForEndOfToken here, because it doesn't do what we want for 169 // macro locations, which we just treat as expanded files. 170 unsigned TokLen = 171 Lexer::MeasureTokenLength(SM.getSpellingLoc(Loc), SM, LangOpts); 172 return Loc.getLocWithOffset(TokLen); 173 } 174 175 /// Return the start location of an included file or expanded macro. 176 SourceLocation getStartOfFileOrMacro(SourceLocation Loc) { 177 if (Loc.isMacroID()) 178 return Loc.getLocWithOffset(-SM.getFileOffset(Loc)); 179 return SM.getLocForStartOfFile(SM.getFileID(Loc)); 180 } 181 182 /// Return the end location of an included file or expanded macro. 183 SourceLocation getEndOfFileOrMacro(SourceLocation Loc) { 184 if (Loc.isMacroID()) 185 return Loc.getLocWithOffset(SM.getFileIDSize(SM.getFileID(Loc)) - 186 SM.getFileOffset(Loc)); 187 return SM.getLocForEndOfFile(SM.getFileID(Loc)); 188 } 189 190 /// Find out where the current file is included or macro is expanded. 191 SourceLocation getIncludeOrExpansionLoc(SourceLocation Loc) { 192 return Loc.isMacroID() ? SM.getImmediateExpansionRange(Loc).getBegin() 193 : SM.getIncludeLoc(SM.getFileID(Loc)); 194 } 195 196 /// Return true if \c Loc is a location in a built-in macro. 197 bool isInBuiltin(SourceLocation Loc) { 198 return SM.getBufferName(SM.getSpellingLoc(Loc)) == "<built-in>"; 199 } 200 201 /// Check whether \c Loc is included or expanded from \c Parent. 202 bool isNestedIn(SourceLocation Loc, FileID Parent) { 203 do { 204 Loc = getIncludeOrExpansionLoc(Loc); 205 if (Loc.isInvalid()) 206 return false; 207 } while (!SM.isInFileID(Loc, Parent)); 208 return true; 209 } 210 211 /// Get the start of \c S ignoring macro arguments and builtin macros. 212 SourceLocation getStart(const Stmt *S) { 213 SourceLocation Loc = S->getBeginLoc(); 214 while (SM.isMacroArgExpansion(Loc) || isInBuiltin(Loc)) 215 Loc = SM.getImmediateExpansionRange(Loc).getBegin(); 216 return Loc; 217 } 218 219 /// Get the end of \c S ignoring macro arguments and builtin macros. 220 SourceLocation getEnd(const Stmt *S) { 221 SourceLocation Loc = S->getEndLoc(); 222 while (SM.isMacroArgExpansion(Loc) || isInBuiltin(Loc)) 223 Loc = SM.getImmediateExpansionRange(Loc).getBegin(); 224 return getPreciseTokenLocEnd(Loc); 225 } 226 227 /// Find the set of files we have regions for and assign IDs 228 /// 229 /// Fills \c Mapping with the virtual file mapping needed to write out 230 /// coverage and collects the necessary file information to emit source and 231 /// expansion regions. 232 void gatherFileIDs(SmallVectorImpl<unsigned> &Mapping) { 233 FileIDMapping.clear(); 234 235 llvm::SmallSet<FileID, 8> Visited; 236 SmallVector<std::pair<SourceLocation, unsigned>, 8> FileLocs; 237 for (const auto &Region : SourceRegions) { 238 SourceLocation Loc = Region.getBeginLoc(); 239 FileID File = SM.getFileID(Loc); 240 if (!Visited.insert(File).second) 241 continue; 242 243 // Do not map FileID's associated with system headers. 244 if (SM.isInSystemHeader(SM.getSpellingLoc(Loc))) 245 continue; 246 247 unsigned Depth = 0; 248 for (SourceLocation Parent = getIncludeOrExpansionLoc(Loc); 249 Parent.isValid(); Parent = getIncludeOrExpansionLoc(Parent)) 250 ++Depth; 251 FileLocs.push_back(std::make_pair(Loc, Depth)); 252 } 253 llvm::stable_sort(FileLocs, llvm::less_second()); 254 255 for (const auto &FL : FileLocs) { 256 SourceLocation Loc = FL.first; 257 FileID SpellingFile = SM.getDecomposedSpellingLoc(Loc).first; 258 auto Entry = SM.getFileEntryForID(SpellingFile); 259 if (!Entry) 260 continue; 261 262 FileIDMapping[SM.getFileID(Loc)] = std::make_pair(Mapping.size(), Loc); 263 Mapping.push_back(CVM.getFileID(Entry)); 264 } 265 } 266 267 /// Get the coverage mapping file ID for \c Loc. 268 /// 269 /// If such file id doesn't exist, return None. 270 Optional<unsigned> getCoverageFileID(SourceLocation Loc) { 271 auto Mapping = FileIDMapping.find(SM.getFileID(Loc)); 272 if (Mapping != FileIDMapping.end()) 273 return Mapping->second.first; 274 return None; 275 } 276 277 /// Gather all the regions that were skipped by the preprocessor 278 /// using the constructs like #if. 279 void gatherSkippedRegions() { 280 /// An array of the minimum lineStarts and the maximum lineEnds 281 /// for mapping regions from the appropriate source files. 282 llvm::SmallVector<std::pair<unsigned, unsigned>, 8> FileLineRanges; 283 FileLineRanges.resize( 284 FileIDMapping.size(), 285 std::make_pair(std::numeric_limits<unsigned>::max(), 0)); 286 for (const auto &R : MappingRegions) { 287 FileLineRanges[R.FileID].first = 288 std::min(FileLineRanges[R.FileID].first, R.LineStart); 289 FileLineRanges[R.FileID].second = 290 std::max(FileLineRanges[R.FileID].second, R.LineEnd); 291 } 292 293 auto SkippedRanges = CVM.getSourceInfo().getSkippedRanges(); 294 for (const auto &I : SkippedRanges) { 295 auto LocStart = I.getBegin(); 296 auto LocEnd = I.getEnd(); 297 assert(SM.isWrittenInSameFile(LocStart, LocEnd) && 298 "region spans multiple files"); 299 300 auto CovFileID = getCoverageFileID(LocStart); 301 if (!CovFileID) 302 continue; 303 SpellingRegion SR{SM, LocStart, LocEnd}; 304 auto Region = CounterMappingRegion::makeSkipped( 305 *CovFileID, SR.LineStart, SR.ColumnStart, SR.LineEnd, SR.ColumnEnd); 306 // Make sure that we only collect the regions that are inside 307 // the source code of this function. 308 if (Region.LineStart >= FileLineRanges[*CovFileID].first && 309 Region.LineEnd <= FileLineRanges[*CovFileID].second) 310 MappingRegions.push_back(Region); 311 } 312 } 313 314 /// Generate the coverage counter mapping regions from collected 315 /// source regions. 316 void emitSourceRegions(const SourceRegionFilter &Filter) { 317 for (const auto &Region : SourceRegions) { 318 assert(Region.hasEndLoc() && "incomplete region"); 319 320 SourceLocation LocStart = Region.getBeginLoc(); 321 assert(SM.getFileID(LocStart).isValid() && "region in invalid file"); 322 323 // Ignore regions from system headers. 324 if (SM.isInSystemHeader(SM.getSpellingLoc(LocStart))) 325 continue; 326 327 auto CovFileID = getCoverageFileID(LocStart); 328 // Ignore regions that don't have a file, such as builtin macros. 329 if (!CovFileID) 330 continue; 331 332 SourceLocation LocEnd = Region.getEndLoc(); 333 assert(SM.isWrittenInSameFile(LocStart, LocEnd) && 334 "region spans multiple files"); 335 336 // Don't add code regions for the area covered by expansion regions. 337 // This not only suppresses redundant regions, but sometimes prevents 338 // creating regions with wrong counters if, for example, a statement's 339 // body ends at the end of a nested macro. 340 if (Filter.count(std::make_pair(LocStart, LocEnd))) 341 continue; 342 343 // Find the spelling locations for the mapping region. 344 SpellingRegion SR{SM, LocStart, LocEnd}; 345 assert(SR.isInSourceOrder() && "region start and end out of order"); 346 347 if (Region.isGap()) { 348 MappingRegions.push_back(CounterMappingRegion::makeGapRegion( 349 Region.getCounter(), *CovFileID, SR.LineStart, SR.ColumnStart, 350 SR.LineEnd, SR.ColumnEnd)); 351 } else { 352 MappingRegions.push_back(CounterMappingRegion::makeRegion( 353 Region.getCounter(), *CovFileID, SR.LineStart, SR.ColumnStart, 354 SR.LineEnd, SR.ColumnEnd)); 355 } 356 } 357 } 358 359 /// Generate expansion regions for each virtual file we've seen. 360 SourceRegionFilter emitExpansionRegions() { 361 SourceRegionFilter Filter; 362 for (const auto &FM : FileIDMapping) { 363 SourceLocation ExpandedLoc = FM.second.second; 364 SourceLocation ParentLoc = getIncludeOrExpansionLoc(ExpandedLoc); 365 if (ParentLoc.isInvalid()) 366 continue; 367 368 auto ParentFileID = getCoverageFileID(ParentLoc); 369 if (!ParentFileID) 370 continue; 371 auto ExpandedFileID = getCoverageFileID(ExpandedLoc); 372 assert(ExpandedFileID && "expansion in uncovered file"); 373 374 SourceLocation LocEnd = getPreciseTokenLocEnd(ParentLoc); 375 assert(SM.isWrittenInSameFile(ParentLoc, LocEnd) && 376 "region spans multiple files"); 377 Filter.insert(std::make_pair(ParentLoc, LocEnd)); 378 379 SpellingRegion SR{SM, ParentLoc, LocEnd}; 380 assert(SR.isInSourceOrder() && "region start and end out of order"); 381 MappingRegions.push_back(CounterMappingRegion::makeExpansion( 382 *ParentFileID, *ExpandedFileID, SR.LineStart, SR.ColumnStart, 383 SR.LineEnd, SR.ColumnEnd)); 384 } 385 return Filter; 386 } 387 }; 388 389 /// Creates unreachable coverage regions for the functions that 390 /// are not emitted. 391 struct EmptyCoverageMappingBuilder : public CoverageMappingBuilder { 392 EmptyCoverageMappingBuilder(CoverageMappingModuleGen &CVM, SourceManager &SM, 393 const LangOptions &LangOpts) 394 : CoverageMappingBuilder(CVM, SM, LangOpts) {} 395 396 void VisitDecl(const Decl *D) { 397 if (!D->hasBody()) 398 return; 399 auto Body = D->getBody(); 400 SourceLocation Start = getStart(Body); 401 SourceLocation End = getEnd(Body); 402 if (!SM.isWrittenInSameFile(Start, End)) { 403 // Walk up to find the common ancestor. 404 // Correct the locations accordingly. 405 FileID StartFileID = SM.getFileID(Start); 406 FileID EndFileID = SM.getFileID(End); 407 while (StartFileID != EndFileID && !isNestedIn(End, StartFileID)) { 408 Start = getIncludeOrExpansionLoc(Start); 409 assert(Start.isValid() && 410 "Declaration start location not nested within a known region"); 411 StartFileID = SM.getFileID(Start); 412 } 413 while (StartFileID != EndFileID) { 414 End = getPreciseTokenLocEnd(getIncludeOrExpansionLoc(End)); 415 assert(End.isValid() && 416 "Declaration end location not nested within a known region"); 417 EndFileID = SM.getFileID(End); 418 } 419 } 420 SourceRegions.emplace_back(Counter(), Start, End); 421 } 422 423 /// Write the mapping data to the output stream 424 void write(llvm::raw_ostream &OS) { 425 SmallVector<unsigned, 16> FileIDMapping; 426 gatherFileIDs(FileIDMapping); 427 emitSourceRegions(SourceRegionFilter()); 428 429 if (MappingRegions.empty()) 430 return; 431 432 CoverageMappingWriter Writer(FileIDMapping, None, MappingRegions); 433 Writer.write(OS); 434 } 435 }; 436 437 /// A StmtVisitor that creates coverage mapping regions which map 438 /// from the source code locations to the PGO counters. 439 struct CounterCoverageMappingBuilder 440 : public CoverageMappingBuilder, 441 public ConstStmtVisitor<CounterCoverageMappingBuilder> { 442 /// The map of statements to count values. 443 llvm::DenseMap<const Stmt *, unsigned> &CounterMap; 444 445 /// A stack of currently live regions. 446 std::vector<SourceMappingRegion> RegionStack; 447 448 /// The currently deferred region: its end location and count can be set once 449 /// its parent has been popped from the region stack. 450 Optional<SourceMappingRegion> DeferredRegion; 451 452 CounterExpressionBuilder Builder; 453 454 /// A location in the most recently visited file or macro. 455 /// 456 /// This is used to adjust the active source regions appropriately when 457 /// expressions cross file or macro boundaries. 458 SourceLocation MostRecentLocation; 459 460 /// Location of the last terminated region. 461 Optional<std::pair<SourceLocation, size_t>> LastTerminatedRegion; 462 463 /// Return a counter for the subtraction of \c RHS from \c LHS 464 Counter subtractCounters(Counter LHS, Counter RHS) { 465 return Builder.subtract(LHS, RHS); 466 } 467 468 /// Return a counter for the sum of \c LHS and \c RHS. 469 Counter addCounters(Counter LHS, Counter RHS) { 470 return Builder.add(LHS, RHS); 471 } 472 473 Counter addCounters(Counter C1, Counter C2, Counter C3) { 474 return addCounters(addCounters(C1, C2), C3); 475 } 476 477 /// Return the region counter for the given statement. 478 /// 479 /// This should only be called on statements that have a dedicated counter. 480 Counter getRegionCounter(const Stmt *S) { 481 return Counter::getCounter(CounterMap[S]); 482 } 483 484 /// Push a region onto the stack. 485 /// 486 /// Returns the index on the stack where the region was pushed. This can be 487 /// used with popRegions to exit a "scope", ending the region that was pushed. 488 size_t pushRegion(Counter Count, Optional<SourceLocation> StartLoc = None, 489 Optional<SourceLocation> EndLoc = None) { 490 if (StartLoc) { 491 MostRecentLocation = *StartLoc; 492 completeDeferred(Count, MostRecentLocation); 493 } 494 RegionStack.emplace_back(Count, StartLoc, EndLoc); 495 496 return RegionStack.size() - 1; 497 } 498 499 /// Complete any pending deferred region by setting its end location and 500 /// count, and then pushing it onto the region stack. 501 size_t completeDeferred(Counter Count, SourceLocation DeferredEndLoc) { 502 size_t Index = RegionStack.size(); 503 if (!DeferredRegion) 504 return Index; 505 506 // Consume the pending region. 507 SourceMappingRegion DR = DeferredRegion.getValue(); 508 DeferredRegion = None; 509 510 // If the region ends in an expansion, find the expansion site. 511 FileID StartFile = SM.getFileID(DR.getBeginLoc()); 512 if (SM.getFileID(DeferredEndLoc) != StartFile) { 513 if (isNestedIn(DeferredEndLoc, StartFile)) { 514 do { 515 DeferredEndLoc = getIncludeOrExpansionLoc(DeferredEndLoc); 516 } while (StartFile != SM.getFileID(DeferredEndLoc)); 517 } else { 518 return Index; 519 } 520 } 521 522 // The parent of this deferred region ends where the containing decl ends, 523 // so the region isn't useful. 524 if (DR.getBeginLoc() == DeferredEndLoc) 525 return Index; 526 527 // If we're visiting statements in non-source order (e.g switch cases or 528 // a loop condition) we can't construct a sensible deferred region. 529 if (!SpellingRegion(SM, DR.getBeginLoc(), DeferredEndLoc).isInSourceOrder()) 530 return Index; 531 532 DR.setGap(true); 533 DR.setCounter(Count); 534 DR.setEndLoc(DeferredEndLoc); 535 handleFileExit(DeferredEndLoc); 536 RegionStack.push_back(DR); 537 return Index; 538 } 539 540 /// Complete a deferred region created after a terminated region at the 541 /// top-level. 542 void completeTopLevelDeferredRegion(Counter Count, 543 SourceLocation DeferredEndLoc) { 544 if (DeferredRegion || !LastTerminatedRegion) 545 return; 546 547 if (LastTerminatedRegion->second != RegionStack.size()) 548 return; 549 550 SourceLocation Start = LastTerminatedRegion->first; 551 if (SM.getFileID(Start) != SM.getMainFileID()) 552 return; 553 554 SourceMappingRegion DR = RegionStack.back(); 555 DR.setStartLoc(Start); 556 DR.setDeferred(false); 557 DeferredRegion = DR; 558 completeDeferred(Count, DeferredEndLoc); 559 } 560 561 size_t locationDepth(SourceLocation Loc) { 562 size_t Depth = 0; 563 while (Loc.isValid()) { 564 Loc = getIncludeOrExpansionLoc(Loc); 565 Depth++; 566 } 567 return Depth; 568 } 569 570 /// Pop regions from the stack into the function's list of regions. 571 /// 572 /// Adds all regions from \c ParentIndex to the top of the stack to the 573 /// function's \c SourceRegions. 574 void popRegions(size_t ParentIndex) { 575 assert(RegionStack.size() >= ParentIndex && "parent not in stack"); 576 bool ParentOfDeferredRegion = false; 577 while (RegionStack.size() > ParentIndex) { 578 SourceMappingRegion &Region = RegionStack.back(); 579 if (Region.hasStartLoc()) { 580 SourceLocation StartLoc = Region.getBeginLoc(); 581 SourceLocation EndLoc = Region.hasEndLoc() 582 ? Region.getEndLoc() 583 : RegionStack[ParentIndex].getEndLoc(); 584 size_t StartDepth = locationDepth(StartLoc); 585 size_t EndDepth = locationDepth(EndLoc); 586 while (!SM.isWrittenInSameFile(StartLoc, EndLoc)) { 587 bool UnnestStart = StartDepth >= EndDepth; 588 bool UnnestEnd = EndDepth >= StartDepth; 589 if (UnnestEnd) { 590 // The region ends in a nested file or macro expansion. Create a 591 // separate region for each expansion. 592 SourceLocation NestedLoc = getStartOfFileOrMacro(EndLoc); 593 assert(SM.isWrittenInSameFile(NestedLoc, EndLoc)); 594 595 if (!isRegionAlreadyAdded(NestedLoc, EndLoc)) 596 SourceRegions.emplace_back(Region.getCounter(), NestedLoc, EndLoc); 597 598 EndLoc = getPreciseTokenLocEnd(getIncludeOrExpansionLoc(EndLoc)); 599 if (EndLoc.isInvalid()) 600 llvm::report_fatal_error("File exit not handled before popRegions"); 601 EndDepth--; 602 } 603 if (UnnestStart) { 604 // The region begins in a nested file or macro expansion. Create a 605 // separate region for each expansion. 606 SourceLocation NestedLoc = getEndOfFileOrMacro(StartLoc); 607 assert(SM.isWrittenInSameFile(StartLoc, NestedLoc)); 608 609 if (!isRegionAlreadyAdded(StartLoc, NestedLoc)) 610 SourceRegions.emplace_back(Region.getCounter(), StartLoc, NestedLoc); 611 612 StartLoc = getIncludeOrExpansionLoc(StartLoc); 613 if (StartLoc.isInvalid()) 614 llvm::report_fatal_error("File exit not handled before popRegions"); 615 StartDepth--; 616 } 617 } 618 Region.setStartLoc(StartLoc); 619 Region.setEndLoc(EndLoc); 620 621 MostRecentLocation = EndLoc; 622 // If this region happens to span an entire expansion, we need to make 623 // sure we don't overlap the parent region with it. 624 if (StartLoc == getStartOfFileOrMacro(StartLoc) && 625 EndLoc == getEndOfFileOrMacro(EndLoc)) 626 MostRecentLocation = getIncludeOrExpansionLoc(EndLoc); 627 628 assert(SM.isWrittenInSameFile(Region.getBeginLoc(), EndLoc)); 629 assert(SpellingRegion(SM, Region).isInSourceOrder()); 630 SourceRegions.push_back(Region); 631 632 if (ParentOfDeferredRegion) { 633 ParentOfDeferredRegion = false; 634 635 // If there's an existing deferred region, keep the old one, because 636 // it means there are two consecutive returns (or a similar pattern). 637 if (!DeferredRegion.hasValue() && 638 // File IDs aren't gathered within macro expansions, so it isn't 639 // useful to try and create a deferred region inside of one. 640 !EndLoc.isMacroID()) 641 DeferredRegion = 642 SourceMappingRegion(Counter::getZero(), EndLoc, None); 643 } 644 } else if (Region.isDeferred()) { 645 assert(!ParentOfDeferredRegion && "Consecutive deferred regions"); 646 ParentOfDeferredRegion = true; 647 } 648 RegionStack.pop_back(); 649 650 // If the zero region pushed after the last terminated region no longer 651 // exists, clear its cached information. 652 if (LastTerminatedRegion && 653 RegionStack.size() < LastTerminatedRegion->second) 654 LastTerminatedRegion = None; 655 } 656 assert(!ParentOfDeferredRegion && "Deferred region with no parent"); 657 } 658 659 /// Return the currently active region. 660 SourceMappingRegion &getRegion() { 661 assert(!RegionStack.empty() && "statement has no region"); 662 return RegionStack.back(); 663 } 664 665 /// Propagate counts through the children of \p S if \p VisitChildren is true. 666 /// Otherwise, only emit a count for \p S itself. 667 Counter propagateCounts(Counter TopCount, const Stmt *S, 668 bool VisitChildren = true) { 669 SourceLocation StartLoc = getStart(S); 670 SourceLocation EndLoc = getEnd(S); 671 size_t Index = pushRegion(TopCount, StartLoc, EndLoc); 672 if (VisitChildren) 673 Visit(S); 674 Counter ExitCount = getRegion().getCounter(); 675 popRegions(Index); 676 677 // The statement may be spanned by an expansion. Make sure we handle a file 678 // exit out of this expansion before moving to the next statement. 679 if (SM.isBeforeInTranslationUnit(StartLoc, S->getBeginLoc())) 680 MostRecentLocation = EndLoc; 681 682 return ExitCount; 683 } 684 685 /// Check whether a region with bounds \c StartLoc and \c EndLoc 686 /// is already added to \c SourceRegions. 687 bool isRegionAlreadyAdded(SourceLocation StartLoc, SourceLocation EndLoc) { 688 return SourceRegions.rend() != 689 std::find_if(SourceRegions.rbegin(), SourceRegions.rend(), 690 [&](const SourceMappingRegion &Region) { 691 return Region.getBeginLoc() == StartLoc && 692 Region.getEndLoc() == EndLoc; 693 }); 694 } 695 696 /// Adjust the most recently visited location to \c EndLoc. 697 /// 698 /// This should be used after visiting any statements in non-source order. 699 void adjustForOutOfOrderTraversal(SourceLocation EndLoc) { 700 MostRecentLocation = EndLoc; 701 // The code region for a whole macro is created in handleFileExit() when 702 // it detects exiting of the virtual file of that macro. If we visited 703 // statements in non-source order, we might already have such a region 704 // added, for example, if a body of a loop is divided among multiple 705 // macros. Avoid adding duplicate regions in such case. 706 if (getRegion().hasEndLoc() && 707 MostRecentLocation == getEndOfFileOrMacro(MostRecentLocation) && 708 isRegionAlreadyAdded(getStartOfFileOrMacro(MostRecentLocation), 709 MostRecentLocation)) 710 MostRecentLocation = getIncludeOrExpansionLoc(MostRecentLocation); 711 } 712 713 /// Adjust regions and state when \c NewLoc exits a file. 714 /// 715 /// If moving from our most recently tracked location to \c NewLoc exits any 716 /// files, this adjusts our current region stack and creates the file regions 717 /// for the exited file. 718 void handleFileExit(SourceLocation NewLoc) { 719 if (NewLoc.isInvalid() || 720 SM.isWrittenInSameFile(MostRecentLocation, NewLoc)) 721 return; 722 723 // If NewLoc is not in a file that contains MostRecentLocation, walk up to 724 // find the common ancestor. 725 SourceLocation LCA = NewLoc; 726 FileID ParentFile = SM.getFileID(LCA); 727 while (!isNestedIn(MostRecentLocation, ParentFile)) { 728 LCA = getIncludeOrExpansionLoc(LCA); 729 if (LCA.isInvalid() || SM.isWrittenInSameFile(LCA, MostRecentLocation)) { 730 // Since there isn't a common ancestor, no file was exited. We just need 731 // to adjust our location to the new file. 732 MostRecentLocation = NewLoc; 733 return; 734 } 735 ParentFile = SM.getFileID(LCA); 736 } 737 738 llvm::SmallSet<SourceLocation, 8> StartLocs; 739 Optional<Counter> ParentCounter; 740 for (SourceMappingRegion &I : llvm::reverse(RegionStack)) { 741 if (!I.hasStartLoc()) 742 continue; 743 SourceLocation Loc = I.getBeginLoc(); 744 if (!isNestedIn(Loc, ParentFile)) { 745 ParentCounter = I.getCounter(); 746 break; 747 } 748 749 while (!SM.isInFileID(Loc, ParentFile)) { 750 // The most nested region for each start location is the one with the 751 // correct count. We avoid creating redundant regions by stopping once 752 // we've seen this region. 753 if (StartLocs.insert(Loc).second) 754 SourceRegions.emplace_back(I.getCounter(), Loc, 755 getEndOfFileOrMacro(Loc)); 756 Loc = getIncludeOrExpansionLoc(Loc); 757 } 758 I.setStartLoc(getPreciseTokenLocEnd(Loc)); 759 } 760 761 if (ParentCounter) { 762 // If the file is contained completely by another region and doesn't 763 // immediately start its own region, the whole file gets a region 764 // corresponding to the parent. 765 SourceLocation Loc = MostRecentLocation; 766 while (isNestedIn(Loc, ParentFile)) { 767 SourceLocation FileStart = getStartOfFileOrMacro(Loc); 768 if (StartLocs.insert(FileStart).second) { 769 SourceRegions.emplace_back(*ParentCounter, FileStart, 770 getEndOfFileOrMacro(Loc)); 771 assert(SpellingRegion(SM, SourceRegions.back()).isInSourceOrder()); 772 } 773 Loc = getIncludeOrExpansionLoc(Loc); 774 } 775 } 776 777 MostRecentLocation = NewLoc; 778 } 779 780 /// Ensure that \c S is included in the current region. 781 void extendRegion(const Stmt *S) { 782 SourceMappingRegion &Region = getRegion(); 783 SourceLocation StartLoc = getStart(S); 784 785 handleFileExit(StartLoc); 786 if (!Region.hasStartLoc()) 787 Region.setStartLoc(StartLoc); 788 789 completeDeferred(Region.getCounter(), StartLoc); 790 } 791 792 /// Mark \c S as a terminator, starting a zero region. 793 void terminateRegion(const Stmt *S) { 794 extendRegion(S); 795 SourceMappingRegion &Region = getRegion(); 796 SourceLocation EndLoc = getEnd(S); 797 if (!Region.hasEndLoc()) 798 Region.setEndLoc(EndLoc); 799 pushRegion(Counter::getZero()); 800 auto &ZeroRegion = getRegion(); 801 ZeroRegion.setDeferred(true); 802 LastTerminatedRegion = {EndLoc, RegionStack.size()}; 803 } 804 805 /// Find a valid gap range between \p AfterLoc and \p BeforeLoc. 806 Optional<SourceRange> findGapAreaBetween(SourceLocation AfterLoc, 807 SourceLocation BeforeLoc) { 808 // If the start and end locations of the gap are both within the same macro 809 // file, the range may not be in source order. 810 if (AfterLoc.isMacroID() || BeforeLoc.isMacroID()) 811 return None; 812 if (!SM.isWrittenInSameFile(AfterLoc, BeforeLoc)) 813 return None; 814 return {{AfterLoc, BeforeLoc}}; 815 } 816 817 /// Find the source range after \p AfterStmt and before \p BeforeStmt. 818 Optional<SourceRange> findGapAreaBetween(const Stmt *AfterStmt, 819 const Stmt *BeforeStmt) { 820 return findGapAreaBetween(getPreciseTokenLocEnd(getEnd(AfterStmt)), 821 getStart(BeforeStmt)); 822 } 823 824 /// Emit a gap region between \p StartLoc and \p EndLoc with the given count. 825 void fillGapAreaWithCount(SourceLocation StartLoc, SourceLocation EndLoc, 826 Counter Count) { 827 if (StartLoc == EndLoc) 828 return; 829 assert(SpellingRegion(SM, StartLoc, EndLoc).isInSourceOrder()); 830 handleFileExit(StartLoc); 831 size_t Index = pushRegion(Count, StartLoc, EndLoc); 832 getRegion().setGap(true); 833 handleFileExit(EndLoc); 834 popRegions(Index); 835 } 836 837 /// Keep counts of breaks and continues inside loops. 838 struct BreakContinue { 839 Counter BreakCount; 840 Counter ContinueCount; 841 }; 842 SmallVector<BreakContinue, 8> BreakContinueStack; 843 844 CounterCoverageMappingBuilder( 845 CoverageMappingModuleGen &CVM, 846 llvm::DenseMap<const Stmt *, unsigned> &CounterMap, SourceManager &SM, 847 const LangOptions &LangOpts) 848 : CoverageMappingBuilder(CVM, SM, LangOpts), CounterMap(CounterMap), 849 DeferredRegion(None) {} 850 851 /// Write the mapping data to the output stream 852 void write(llvm::raw_ostream &OS) { 853 llvm::SmallVector<unsigned, 8> VirtualFileMapping; 854 gatherFileIDs(VirtualFileMapping); 855 SourceRegionFilter Filter = emitExpansionRegions(); 856 assert(!DeferredRegion && "Deferred region never completed"); 857 emitSourceRegions(Filter); 858 gatherSkippedRegions(); 859 860 if (MappingRegions.empty()) 861 return; 862 863 CoverageMappingWriter Writer(VirtualFileMapping, Builder.getExpressions(), 864 MappingRegions); 865 Writer.write(OS); 866 } 867 868 void VisitStmt(const Stmt *S) { 869 if (S->getBeginLoc().isValid()) 870 extendRegion(S); 871 for (const Stmt *Child : S->children()) 872 if (Child) 873 this->Visit(Child); 874 handleFileExit(getEnd(S)); 875 } 876 877 void VisitDecl(const Decl *D) { 878 assert(!DeferredRegion && "Deferred region never completed"); 879 880 Stmt *Body = D->getBody(); 881 882 // Do not propagate region counts into system headers. 883 if (Body && SM.isInSystemHeader(SM.getSpellingLoc(getStart(Body)))) 884 return; 885 886 // Do not visit the artificial children nodes of defaulted methods. The 887 // lexer may not be able to report back precise token end locations for 888 // these children nodes (llvm.org/PR39822), and moreover users will not be 889 // able to see coverage for them. 890 bool Defaulted = false; 891 if (auto *Method = dyn_cast<CXXMethodDecl>(D)) 892 Defaulted = Method->isDefaulted(); 893 894 propagateCounts(getRegionCounter(Body), Body, 895 /*VisitChildren=*/!Defaulted); 896 assert(RegionStack.empty() && "Regions entered but never exited"); 897 898 // Discard the last uncompleted deferred region in a decl, if one exists. 899 // This prevents lines at the end of a function containing only whitespace 900 // or closing braces from being marked as uncovered. 901 DeferredRegion = None; 902 } 903 904 void VisitReturnStmt(const ReturnStmt *S) { 905 extendRegion(S); 906 if (S->getRetValue()) 907 Visit(S->getRetValue()); 908 terminateRegion(S); 909 } 910 911 void VisitCoroutineBodyStmt(const CoroutineBodyStmt *S) { 912 extendRegion(S); 913 Visit(S->getBody()); 914 } 915 916 void VisitCoreturnStmt(const CoreturnStmt *S) { 917 extendRegion(S); 918 if (S->getOperand()) 919 Visit(S->getOperand()); 920 terminateRegion(S); 921 } 922 923 void VisitCXXThrowExpr(const CXXThrowExpr *E) { 924 extendRegion(E); 925 if (E->getSubExpr()) 926 Visit(E->getSubExpr()); 927 terminateRegion(E); 928 } 929 930 void VisitGotoStmt(const GotoStmt *S) { terminateRegion(S); } 931 932 void VisitLabelStmt(const LabelStmt *S) { 933 Counter LabelCount = getRegionCounter(S); 934 SourceLocation Start = getStart(S); 935 completeTopLevelDeferredRegion(LabelCount, Start); 936 completeDeferred(LabelCount, Start); 937 // We can't extendRegion here or we risk overlapping with our new region. 938 handleFileExit(Start); 939 pushRegion(LabelCount, Start); 940 Visit(S->getSubStmt()); 941 } 942 943 void VisitBreakStmt(const BreakStmt *S) { 944 assert(!BreakContinueStack.empty() && "break not in a loop or switch!"); 945 BreakContinueStack.back().BreakCount = addCounters( 946 BreakContinueStack.back().BreakCount, getRegion().getCounter()); 947 // FIXME: a break in a switch should terminate regions for all preceding 948 // case statements, not just the most recent one. 949 terminateRegion(S); 950 } 951 952 void VisitContinueStmt(const ContinueStmt *S) { 953 assert(!BreakContinueStack.empty() && "continue stmt not in a loop!"); 954 BreakContinueStack.back().ContinueCount = addCounters( 955 BreakContinueStack.back().ContinueCount, getRegion().getCounter()); 956 terminateRegion(S); 957 } 958 959 void VisitCallExpr(const CallExpr *E) { 960 VisitStmt(E); 961 962 // Terminate the region when we hit a noreturn function. 963 // (This is helpful dealing with switch statements.) 964 QualType CalleeType = E->getCallee()->getType(); 965 if (getFunctionExtInfo(*CalleeType).getNoReturn()) 966 terminateRegion(E); 967 } 968 969 void VisitWhileStmt(const WhileStmt *S) { 970 extendRegion(S); 971 972 Counter ParentCount = getRegion().getCounter(); 973 Counter BodyCount = getRegionCounter(S); 974 975 // Handle the body first so that we can get the backedge count. 976 BreakContinueStack.push_back(BreakContinue()); 977 extendRegion(S->getBody()); 978 Counter BackedgeCount = propagateCounts(BodyCount, S->getBody()); 979 BreakContinue BC = BreakContinueStack.pop_back_val(); 980 981 // Go back to handle the condition. 982 Counter CondCount = 983 addCounters(ParentCount, BackedgeCount, BC.ContinueCount); 984 propagateCounts(CondCount, S->getCond()); 985 adjustForOutOfOrderTraversal(getEnd(S)); 986 987 // The body count applies to the area immediately after the increment. 988 auto Gap = findGapAreaBetween(S->getCond(), S->getBody()); 989 if (Gap) 990 fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount); 991 992 Counter OutCount = 993 addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount)); 994 if (OutCount != ParentCount) 995 pushRegion(OutCount); 996 } 997 998 void VisitDoStmt(const DoStmt *S) { 999 extendRegion(S); 1000 1001 Counter ParentCount = getRegion().getCounter(); 1002 Counter BodyCount = getRegionCounter(S); 1003 1004 BreakContinueStack.push_back(BreakContinue()); 1005 extendRegion(S->getBody()); 1006 Counter BackedgeCount = 1007 propagateCounts(addCounters(ParentCount, BodyCount), S->getBody()); 1008 BreakContinue BC = BreakContinueStack.pop_back_val(); 1009 1010 Counter CondCount = addCounters(BackedgeCount, BC.ContinueCount); 1011 propagateCounts(CondCount, S->getCond()); 1012 1013 Counter OutCount = 1014 addCounters(BC.BreakCount, subtractCounters(CondCount, BodyCount)); 1015 if (OutCount != ParentCount) 1016 pushRegion(OutCount); 1017 } 1018 1019 void VisitForStmt(const ForStmt *S) { 1020 extendRegion(S); 1021 if (S->getInit()) 1022 Visit(S->getInit()); 1023 1024 Counter ParentCount = getRegion().getCounter(); 1025 Counter BodyCount = getRegionCounter(S); 1026 1027 // The loop increment may contain a break or continue. 1028 if (S->getInc()) 1029 BreakContinueStack.emplace_back(); 1030 1031 // Handle the body first so that we can get the backedge count. 1032 BreakContinueStack.emplace_back(); 1033 extendRegion(S->getBody()); 1034 Counter BackedgeCount = propagateCounts(BodyCount, S->getBody()); 1035 BreakContinue BodyBC = BreakContinueStack.pop_back_val(); 1036 1037 // The increment is essentially part of the body but it needs to include 1038 // the count for all the continue statements. 1039 BreakContinue IncrementBC; 1040 if (const Stmt *Inc = S->getInc()) { 1041 propagateCounts(addCounters(BackedgeCount, BodyBC.ContinueCount), Inc); 1042 IncrementBC = BreakContinueStack.pop_back_val(); 1043 } 1044 1045 // Go back to handle the condition. 1046 Counter CondCount = addCounters( 1047 addCounters(ParentCount, BackedgeCount, BodyBC.ContinueCount), 1048 IncrementBC.ContinueCount); 1049 if (const Expr *Cond = S->getCond()) { 1050 propagateCounts(CondCount, Cond); 1051 adjustForOutOfOrderTraversal(getEnd(S)); 1052 } 1053 1054 // The body count applies to the area immediately after the increment. 1055 auto Gap = findGapAreaBetween(getPreciseTokenLocEnd(S->getRParenLoc()), 1056 getStart(S->getBody())); 1057 if (Gap) 1058 fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount); 1059 1060 Counter OutCount = addCounters(BodyBC.BreakCount, IncrementBC.BreakCount, 1061 subtractCounters(CondCount, BodyCount)); 1062 if (OutCount != ParentCount) 1063 pushRegion(OutCount); 1064 } 1065 1066 void VisitCXXForRangeStmt(const CXXForRangeStmt *S) { 1067 extendRegion(S); 1068 if (S->getInit()) 1069 Visit(S->getInit()); 1070 Visit(S->getLoopVarStmt()); 1071 Visit(S->getRangeStmt()); 1072 1073 Counter ParentCount = getRegion().getCounter(); 1074 Counter BodyCount = getRegionCounter(S); 1075 1076 BreakContinueStack.push_back(BreakContinue()); 1077 extendRegion(S->getBody()); 1078 Counter BackedgeCount = propagateCounts(BodyCount, S->getBody()); 1079 BreakContinue BC = BreakContinueStack.pop_back_val(); 1080 1081 // The body count applies to the area immediately after the range. 1082 auto Gap = findGapAreaBetween(getPreciseTokenLocEnd(S->getRParenLoc()), 1083 getStart(S->getBody())); 1084 if (Gap) 1085 fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount); 1086 1087 Counter LoopCount = 1088 addCounters(ParentCount, BackedgeCount, BC.ContinueCount); 1089 Counter OutCount = 1090 addCounters(BC.BreakCount, subtractCounters(LoopCount, BodyCount)); 1091 if (OutCount != ParentCount) 1092 pushRegion(OutCount); 1093 } 1094 1095 void VisitObjCForCollectionStmt(const ObjCForCollectionStmt *S) { 1096 extendRegion(S); 1097 Visit(S->getElement()); 1098 1099 Counter ParentCount = getRegion().getCounter(); 1100 Counter BodyCount = getRegionCounter(S); 1101 1102 BreakContinueStack.push_back(BreakContinue()); 1103 extendRegion(S->getBody()); 1104 Counter BackedgeCount = propagateCounts(BodyCount, S->getBody()); 1105 BreakContinue BC = BreakContinueStack.pop_back_val(); 1106 1107 // The body count applies to the area immediately after the collection. 1108 auto Gap = findGapAreaBetween(getPreciseTokenLocEnd(S->getRParenLoc()), 1109 getStart(S->getBody())); 1110 if (Gap) 1111 fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), BodyCount); 1112 1113 Counter LoopCount = 1114 addCounters(ParentCount, BackedgeCount, BC.ContinueCount); 1115 Counter OutCount = 1116 addCounters(BC.BreakCount, subtractCounters(LoopCount, BodyCount)); 1117 if (OutCount != ParentCount) 1118 pushRegion(OutCount); 1119 } 1120 1121 void VisitSwitchStmt(const SwitchStmt *S) { 1122 extendRegion(S); 1123 if (S->getInit()) 1124 Visit(S->getInit()); 1125 Visit(S->getCond()); 1126 1127 BreakContinueStack.push_back(BreakContinue()); 1128 1129 const Stmt *Body = S->getBody(); 1130 extendRegion(Body); 1131 if (const auto *CS = dyn_cast<CompoundStmt>(Body)) { 1132 if (!CS->body_empty()) { 1133 // Make a region for the body of the switch. If the body starts with 1134 // a case, that case will reuse this region; otherwise, this covers 1135 // the unreachable code at the beginning of the switch body. 1136 size_t Index = pushRegion(Counter::getZero(), getStart(CS)); 1137 getRegion().setGap(true); 1138 for (const auto *Child : CS->children()) 1139 Visit(Child); 1140 1141 // Set the end for the body of the switch, if it isn't already set. 1142 for (size_t i = RegionStack.size(); i != Index; --i) { 1143 if (!RegionStack[i - 1].hasEndLoc()) 1144 RegionStack[i - 1].setEndLoc(getEnd(CS->body_back())); 1145 } 1146 1147 popRegions(Index); 1148 } 1149 } else 1150 propagateCounts(Counter::getZero(), Body); 1151 BreakContinue BC = BreakContinueStack.pop_back_val(); 1152 1153 if (!BreakContinueStack.empty()) 1154 BreakContinueStack.back().ContinueCount = addCounters( 1155 BreakContinueStack.back().ContinueCount, BC.ContinueCount); 1156 1157 Counter ExitCount = getRegionCounter(S); 1158 SourceLocation ExitLoc = getEnd(S); 1159 pushRegion(ExitCount); 1160 1161 // Ensure that handleFileExit recognizes when the end location is located 1162 // in a different file. 1163 MostRecentLocation = getStart(S); 1164 handleFileExit(ExitLoc); 1165 } 1166 1167 void VisitSwitchCase(const SwitchCase *S) { 1168 extendRegion(S); 1169 1170 SourceMappingRegion &Parent = getRegion(); 1171 1172 Counter Count = addCounters(Parent.getCounter(), getRegionCounter(S)); 1173 // Reuse the existing region if it starts at our label. This is typical of 1174 // the first case in a switch. 1175 if (Parent.hasStartLoc() && Parent.getBeginLoc() == getStart(S)) 1176 Parent.setCounter(Count); 1177 else 1178 pushRegion(Count, getStart(S)); 1179 1180 if (const auto *CS = dyn_cast<CaseStmt>(S)) { 1181 Visit(CS->getLHS()); 1182 if (const Expr *RHS = CS->getRHS()) 1183 Visit(RHS); 1184 } 1185 Visit(S->getSubStmt()); 1186 } 1187 1188 void VisitIfStmt(const IfStmt *S) { 1189 extendRegion(S); 1190 if (S->getInit()) 1191 Visit(S->getInit()); 1192 1193 // Extend into the condition before we propagate through it below - this is 1194 // needed to handle macros that generate the "if" but not the condition. 1195 extendRegion(S->getCond()); 1196 1197 Counter ParentCount = getRegion().getCounter(); 1198 Counter ThenCount = getRegionCounter(S); 1199 1200 // Emitting a counter for the condition makes it easier to interpret the 1201 // counter for the body when looking at the coverage. 1202 propagateCounts(ParentCount, S->getCond()); 1203 1204 // The 'then' count applies to the area immediately after the condition. 1205 auto Gap = findGapAreaBetween(S->getCond(), S->getThen()); 1206 if (Gap) 1207 fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), ThenCount); 1208 1209 extendRegion(S->getThen()); 1210 Counter OutCount = propagateCounts(ThenCount, S->getThen()); 1211 1212 Counter ElseCount = subtractCounters(ParentCount, ThenCount); 1213 if (const Stmt *Else = S->getElse()) { 1214 // The 'else' count applies to the area immediately after the 'then'. 1215 Gap = findGapAreaBetween(S->getThen(), Else); 1216 if (Gap) 1217 fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), ElseCount); 1218 extendRegion(Else); 1219 OutCount = addCounters(OutCount, propagateCounts(ElseCount, Else)); 1220 } else 1221 OutCount = addCounters(OutCount, ElseCount); 1222 1223 if (OutCount != ParentCount) 1224 pushRegion(OutCount); 1225 } 1226 1227 void VisitCXXTryStmt(const CXXTryStmt *S) { 1228 extendRegion(S); 1229 // Handle macros that generate the "try" but not the rest. 1230 extendRegion(S->getTryBlock()); 1231 1232 Counter ParentCount = getRegion().getCounter(); 1233 propagateCounts(ParentCount, S->getTryBlock()); 1234 1235 for (unsigned I = 0, E = S->getNumHandlers(); I < E; ++I) 1236 Visit(S->getHandler(I)); 1237 1238 Counter ExitCount = getRegionCounter(S); 1239 pushRegion(ExitCount); 1240 } 1241 1242 void VisitCXXCatchStmt(const CXXCatchStmt *S) { 1243 propagateCounts(getRegionCounter(S), S->getHandlerBlock()); 1244 } 1245 1246 void VisitAbstractConditionalOperator(const AbstractConditionalOperator *E) { 1247 extendRegion(E); 1248 1249 Counter ParentCount = getRegion().getCounter(); 1250 Counter TrueCount = getRegionCounter(E); 1251 1252 Visit(E->getCond()); 1253 1254 if (!isa<BinaryConditionalOperator>(E)) { 1255 // The 'then' count applies to the area immediately after the condition. 1256 auto Gap = 1257 findGapAreaBetween(E->getQuestionLoc(), getStart(E->getTrueExpr())); 1258 if (Gap) 1259 fillGapAreaWithCount(Gap->getBegin(), Gap->getEnd(), TrueCount); 1260 1261 extendRegion(E->getTrueExpr()); 1262 propagateCounts(TrueCount, E->getTrueExpr()); 1263 } 1264 1265 extendRegion(E->getFalseExpr()); 1266 propagateCounts(subtractCounters(ParentCount, TrueCount), 1267 E->getFalseExpr()); 1268 } 1269 1270 void VisitBinLAnd(const BinaryOperator *E) { 1271 extendRegion(E->getLHS()); 1272 propagateCounts(getRegion().getCounter(), E->getLHS()); 1273 handleFileExit(getEnd(E->getLHS())); 1274 1275 extendRegion(E->getRHS()); 1276 propagateCounts(getRegionCounter(E), E->getRHS()); 1277 } 1278 1279 void VisitBinLOr(const BinaryOperator *E) { 1280 extendRegion(E->getLHS()); 1281 propagateCounts(getRegion().getCounter(), E->getLHS()); 1282 handleFileExit(getEnd(E->getLHS())); 1283 1284 extendRegion(E->getRHS()); 1285 propagateCounts(getRegionCounter(E), E->getRHS()); 1286 } 1287 1288 void VisitLambdaExpr(const LambdaExpr *LE) { 1289 // Lambdas are treated as their own functions for now, so we shouldn't 1290 // propagate counts into them. 1291 } 1292 }; 1293 1294 std::string normalizeFilename(StringRef Filename) { 1295 llvm::SmallString<256> Path(Filename); 1296 llvm::sys::fs::make_absolute(Path); 1297 llvm::sys::path::remove_dots(Path, /*remove_dot_dot=*/true); 1298 return std::string(Path); 1299 } 1300 1301 } // end anonymous namespace 1302 1303 static void dump(llvm::raw_ostream &OS, StringRef FunctionName, 1304 ArrayRef<CounterExpression> Expressions, 1305 ArrayRef<CounterMappingRegion> Regions) { 1306 OS << FunctionName << ":\n"; 1307 CounterMappingContext Ctx(Expressions); 1308 for (const auto &R : Regions) { 1309 OS.indent(2); 1310 switch (R.Kind) { 1311 case CounterMappingRegion::CodeRegion: 1312 break; 1313 case CounterMappingRegion::ExpansionRegion: 1314 OS << "Expansion,"; 1315 break; 1316 case CounterMappingRegion::SkippedRegion: 1317 OS << "Skipped,"; 1318 break; 1319 case CounterMappingRegion::GapRegion: 1320 OS << "Gap,"; 1321 break; 1322 } 1323 1324 OS << "File " << R.FileID << ", " << R.LineStart << ":" << R.ColumnStart 1325 << " -> " << R.LineEnd << ":" << R.ColumnEnd << " = "; 1326 Ctx.dump(R.Count, OS); 1327 if (R.Kind == CounterMappingRegion::ExpansionRegion) 1328 OS << " (Expanded file = " << R.ExpandedFileID << ")"; 1329 OS << "\n"; 1330 } 1331 } 1332 1333 static std::string getInstrProfSection(const CodeGenModule &CGM, 1334 llvm::InstrProfSectKind SK) { 1335 return llvm::getInstrProfSectionName( 1336 SK, CGM.getContext().getTargetInfo().getTriple().getObjectFormat()); 1337 } 1338 1339 void CoverageMappingModuleGen::emitFunctionMappingRecord( 1340 const FunctionInfo &Info, uint64_t FilenamesRef) { 1341 llvm::LLVMContext &Ctx = CGM.getLLVMContext(); 1342 1343 // Assign a name to the function record. This is used to merge duplicates. 1344 std::string FuncRecordName = "__covrec_" + llvm::utohexstr(Info.NameHash); 1345 1346 // A dummy description for a function included-but-not-used in a TU can be 1347 // replaced by full description provided by a different TU. The two kinds of 1348 // descriptions play distinct roles: therefore, assign them different names 1349 // to prevent `linkonce_odr` merging. 1350 if (Info.IsUsed) 1351 FuncRecordName += "u"; 1352 1353 // Create the function record type. 1354 const uint64_t NameHash = Info.NameHash; 1355 const uint64_t FuncHash = Info.FuncHash; 1356 const std::string &CoverageMapping = Info.CoverageMapping; 1357 #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) LLVMType, 1358 llvm::Type *FunctionRecordTypes[] = { 1359 #include "llvm/ProfileData/InstrProfData.inc" 1360 }; 1361 auto *FunctionRecordTy = 1362 llvm::StructType::get(Ctx, makeArrayRef(FunctionRecordTypes), 1363 /*isPacked=*/true); 1364 1365 // Create the function record constant. 1366 #define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Init, 1367 llvm::Constant *FunctionRecordVals[] = { 1368 #include "llvm/ProfileData/InstrProfData.inc" 1369 }; 1370 auto *FuncRecordConstant = llvm::ConstantStruct::get( 1371 FunctionRecordTy, makeArrayRef(FunctionRecordVals)); 1372 1373 // Create the function record global. 1374 auto *FuncRecord = new llvm::GlobalVariable( 1375 CGM.getModule(), FunctionRecordTy, /*isConstant=*/true, 1376 llvm::GlobalValue::LinkOnceODRLinkage, FuncRecordConstant, 1377 FuncRecordName); 1378 FuncRecord->setVisibility(llvm::GlobalValue::HiddenVisibility); 1379 FuncRecord->setSection(getInstrProfSection(CGM, llvm::IPSK_covfun)); 1380 FuncRecord->setAlignment(llvm::Align(8)); 1381 if (CGM.supportsCOMDAT()) 1382 FuncRecord->setComdat(CGM.getModule().getOrInsertComdat(FuncRecordName)); 1383 1384 // Make sure the data doesn't get deleted. 1385 CGM.addUsedGlobal(FuncRecord); 1386 } 1387 1388 void CoverageMappingModuleGen::addFunctionMappingRecord( 1389 llvm::GlobalVariable *NamePtr, StringRef NameValue, uint64_t FuncHash, 1390 const std::string &CoverageMapping, bool IsUsed) { 1391 llvm::LLVMContext &Ctx = CGM.getLLVMContext(); 1392 const uint64_t NameHash = llvm::IndexedInstrProf::ComputeHash(NameValue); 1393 FunctionRecords.push_back({NameHash, FuncHash, CoverageMapping, IsUsed}); 1394 1395 if (!IsUsed) 1396 FunctionNames.push_back( 1397 llvm::ConstantExpr::getBitCast(NamePtr, llvm::Type::getInt8PtrTy(Ctx))); 1398 1399 if (CGM.getCodeGenOpts().DumpCoverageMapping) { 1400 // Dump the coverage mapping data for this function by decoding the 1401 // encoded data. This allows us to dump the mapping regions which were 1402 // also processed by the CoverageMappingWriter which performs 1403 // additional minimization operations such as reducing the number of 1404 // expressions. 1405 std::vector<StringRef> Filenames; 1406 std::vector<CounterExpression> Expressions; 1407 std::vector<CounterMappingRegion> Regions; 1408 llvm::SmallVector<std::string, 16> FilenameStrs; 1409 llvm::SmallVector<StringRef, 16> FilenameRefs; 1410 FilenameStrs.resize(FileEntries.size()); 1411 FilenameRefs.resize(FileEntries.size()); 1412 for (const auto &Entry : FileEntries) { 1413 auto I = Entry.second; 1414 FilenameStrs[I] = normalizeFilename(Entry.first->getName()); 1415 FilenameRefs[I] = FilenameStrs[I]; 1416 } 1417 RawCoverageMappingReader Reader(CoverageMapping, FilenameRefs, Filenames, 1418 Expressions, Regions); 1419 if (Reader.read()) 1420 return; 1421 dump(llvm::outs(), NameValue, Expressions, Regions); 1422 } 1423 } 1424 1425 void CoverageMappingModuleGen::emit() { 1426 if (FunctionRecords.empty()) 1427 return; 1428 llvm::LLVMContext &Ctx = CGM.getLLVMContext(); 1429 auto *Int32Ty = llvm::Type::getInt32Ty(Ctx); 1430 1431 // Create the filenames and merge them with coverage mappings 1432 llvm::SmallVector<std::string, 16> FilenameStrs; 1433 llvm::SmallVector<StringRef, 16> FilenameRefs; 1434 FilenameStrs.resize(FileEntries.size()); 1435 FilenameRefs.resize(FileEntries.size()); 1436 for (const auto &Entry : FileEntries) { 1437 auto I = Entry.second; 1438 FilenameStrs[I] = normalizeFilename(Entry.first->getName()); 1439 FilenameRefs[I] = FilenameStrs[I]; 1440 } 1441 1442 std::string Filenames; 1443 { 1444 llvm::raw_string_ostream OS(Filenames); 1445 CoverageFilenamesSectionWriter(FilenameRefs).write(OS); 1446 } 1447 auto *FilenamesVal = 1448 llvm::ConstantDataArray::getString(Ctx, Filenames, false); 1449 const int64_t FilenamesRef = llvm::IndexedInstrProf::ComputeHash(Filenames); 1450 1451 // Emit the function records. 1452 for (const FunctionInfo &Info : FunctionRecords) 1453 emitFunctionMappingRecord(Info, FilenamesRef); 1454 1455 const unsigned NRecords = 0; 1456 const size_t FilenamesSize = Filenames.size(); 1457 const unsigned CoverageMappingSize = 0; 1458 llvm::Type *CovDataHeaderTypes[] = { 1459 #define COVMAP_HEADER(Type, LLVMType, Name, Init) LLVMType, 1460 #include "llvm/ProfileData/InstrProfData.inc" 1461 }; 1462 auto CovDataHeaderTy = 1463 llvm::StructType::get(Ctx, makeArrayRef(CovDataHeaderTypes)); 1464 llvm::Constant *CovDataHeaderVals[] = { 1465 #define COVMAP_HEADER(Type, LLVMType, Name, Init) Init, 1466 #include "llvm/ProfileData/InstrProfData.inc" 1467 }; 1468 auto CovDataHeaderVal = llvm::ConstantStruct::get( 1469 CovDataHeaderTy, makeArrayRef(CovDataHeaderVals)); 1470 1471 // Create the coverage data record 1472 llvm::Type *CovDataTypes[] = {CovDataHeaderTy, FilenamesVal->getType()}; 1473 auto CovDataTy = llvm::StructType::get(Ctx, makeArrayRef(CovDataTypes)); 1474 llvm::Constant *TUDataVals[] = {CovDataHeaderVal, FilenamesVal}; 1475 auto CovDataVal = 1476 llvm::ConstantStruct::get(CovDataTy, makeArrayRef(TUDataVals)); 1477 auto CovData = new llvm::GlobalVariable( 1478 CGM.getModule(), CovDataTy, true, llvm::GlobalValue::PrivateLinkage, 1479 CovDataVal, llvm::getCoverageMappingVarName()); 1480 1481 CovData->setSection(getInstrProfSection(CGM, llvm::IPSK_covmap)); 1482 CovData->setAlignment(llvm::Align(8)); 1483 1484 // Make sure the data doesn't get deleted. 1485 CGM.addUsedGlobal(CovData); 1486 // Create the deferred function records array 1487 if (!FunctionNames.empty()) { 1488 auto NamesArrTy = llvm::ArrayType::get(llvm::Type::getInt8PtrTy(Ctx), 1489 FunctionNames.size()); 1490 auto NamesArrVal = llvm::ConstantArray::get(NamesArrTy, FunctionNames); 1491 // This variable will *NOT* be emitted to the object file. It is used 1492 // to pass the list of names referenced to codegen. 1493 new llvm::GlobalVariable(CGM.getModule(), NamesArrTy, true, 1494 llvm::GlobalValue::InternalLinkage, NamesArrVal, 1495 llvm::getCoverageUnusedNamesVarName()); 1496 } 1497 } 1498 1499 unsigned CoverageMappingModuleGen::getFileID(const FileEntry *File) { 1500 auto It = FileEntries.find(File); 1501 if (It != FileEntries.end()) 1502 return It->second; 1503 unsigned FileID = FileEntries.size(); 1504 FileEntries.insert(std::make_pair(File, FileID)); 1505 return FileID; 1506 } 1507 1508 void CoverageMappingGen::emitCounterMapping(const Decl *D, 1509 llvm::raw_ostream &OS) { 1510 assert(CounterMap); 1511 CounterCoverageMappingBuilder Walker(CVM, *CounterMap, SM, LangOpts); 1512 Walker.VisitDecl(D); 1513 Walker.write(OS); 1514 } 1515 1516 void CoverageMappingGen::emitEmptyMapping(const Decl *D, 1517 llvm::raw_ostream &OS) { 1518 EmptyCoverageMappingBuilder Walker(CVM, SM, LangOpts); 1519 Walker.VisitDecl(D); 1520 Walker.write(OS); 1521 } 1522