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