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