1//=-- CoverageMapping.h - Code coverage mapping support ---------*- 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// Code coverage mapping data is generated by clang and read by 11// llvm-cov to show code coverage statistics for a file. 12// 13//===----------------------------------------------------------------------===// 14 15#ifndef LLVM_PROFILEDATA_COVERAGEMAPPING_H_ 16#define LLVM_PROFILEDATA_COVERAGEMAPPING_H_ 17 18#include "llvm/ADT/ArrayRef.h" 19#include "llvm/ADT/DenseMap.h" 20#include "llvm/ADT/Hashing.h" 21#include "llvm/ADT/Triple.h" 22#include "llvm/ADT/iterator.h" 23#include "llvm/ProfileData/InstrProf.h" 24#include "llvm/Support/Debug.h" 25#include "llvm/Support/Endian.h" 26#include "llvm/Support/raw_ostream.h" 27#include <system_error> 28#include <tuple> 29 30namespace llvm { 31namespace coverage { 32 33enum class coveragemap_error { 34 success = 0, 35 eof, 36 no_data_found, 37 unsupported_version, 38 truncated, 39 malformed 40}; 41 42const std::error_category &coveragemap_category(); 43 44inline std::error_code make_error_code(coveragemap_error E) { 45 return std::error_code(static_cast<int>(E), coveragemap_category()); 46} 47 48class CoverageMapError : public ErrorInfo<CoverageMapError> { 49public: 50 CoverageMapError(coveragemap_error Err) : Err(Err) { 51 assert(Err != coveragemap_error::success && "Not an error"); 52 } 53 54 std::string message() const override; 55 56 void log(raw_ostream &OS) const override { OS << message(); } 57 58 std::error_code convertToErrorCode() const override { 59 return make_error_code(Err); 60 } 61 62 coveragemap_error get() const { return Err; } 63 64 static char ID; 65 66private: 67 coveragemap_error Err; 68}; 69 70} // end of coverage namespace. 71} // end of llvm namespace 72 73namespace llvm { 74class IndexedInstrProfReader; 75namespace coverage { 76 77class CoverageMappingReader; 78 79class CoverageMapping; 80struct CounterExpressions; 81 82/// \brief A Counter is an abstract value that describes how to compute the 83/// execution count for a region of code using the collected profile count data. 84struct Counter { 85 enum CounterKind { Zero, CounterValueReference, Expression }; 86 static const unsigned EncodingTagBits = 2; 87 static const unsigned EncodingTagMask = 0x3; 88 static const unsigned EncodingCounterTagAndExpansionRegionTagBits = 89 EncodingTagBits + 1; 90 91private: 92 CounterKind Kind; 93 unsigned ID; 94 95 Counter(CounterKind Kind, unsigned ID) : Kind(Kind), ID(ID) {} 96 97public: 98 Counter() : Kind(Zero), ID(0) {} 99 100 CounterKind getKind() const { return Kind; } 101 102 bool isZero() const { return Kind == Zero; } 103 104 bool isExpression() const { return Kind == Expression; } 105 106 unsigned getCounterID() const { return ID; } 107 108 unsigned getExpressionID() const { return ID; } 109 110 friend bool operator==(const Counter &LHS, const Counter &RHS) { 111 return LHS.Kind == RHS.Kind && LHS.ID == RHS.ID; 112 } 113 114 friend bool operator!=(const Counter &LHS, const Counter &RHS) { 115 return !(LHS == RHS); 116 } 117 118 friend bool operator<(const Counter &LHS, const Counter &RHS) { 119 return std::tie(LHS.Kind, LHS.ID) < std::tie(RHS.Kind, RHS.ID); 120 } 121 122 /// \brief Return the counter that represents the number zero. 123 static Counter getZero() { return Counter(); } 124 125 /// \brief Return the counter that corresponds to a specific profile counter. 126 static Counter getCounter(unsigned CounterId) { 127 return Counter(CounterValueReference, CounterId); 128 } 129 130 /// \brief Return the counter that corresponds to a specific 131 /// addition counter expression. 132 static Counter getExpression(unsigned ExpressionId) { 133 return Counter(Expression, ExpressionId); 134 } 135}; 136 137/// \brief A Counter expression is a value that represents an arithmetic 138/// operation with two counters. 139struct CounterExpression { 140 enum ExprKind { Subtract, Add }; 141 ExprKind Kind; 142 Counter LHS, RHS; 143 144 CounterExpression(ExprKind Kind, Counter LHS, Counter RHS) 145 : Kind(Kind), LHS(LHS), RHS(RHS) {} 146}; 147 148/// \brief A Counter expression builder is used to construct the 149/// counter expressions. It avoids unnecessary duplication 150/// and simplifies algebraic expressions. 151class CounterExpressionBuilder { 152 /// \brief A list of all the counter expressions 153 std::vector<CounterExpression> Expressions; 154 /// \brief A lookup table for the index of a given expression. 155 llvm::DenseMap<CounterExpression, unsigned> ExpressionIndices; 156 157 /// \brief Return the counter which corresponds to the given expression. 158 /// 159 /// If the given expression is already stored in the builder, a counter 160 /// that references that expression is returned. Otherwise, the given 161 /// expression is added to the builder's collection of expressions. 162 Counter get(const CounterExpression &E); 163 164 /// \brief Gather the terms of the expression tree for processing. 165 /// 166 /// This collects each addition and subtraction referenced by the counter into 167 /// a sequence that can be sorted and combined to build a simplified counter 168 /// expression. 169 void extractTerms(Counter C, int Sign, 170 SmallVectorImpl<std::pair<unsigned, int>> &Terms); 171 172 /// \brief Simplifies the given expression tree 173 /// by getting rid of algebraically redundant operations. 174 Counter simplify(Counter ExpressionTree); 175 176public: 177 ArrayRef<CounterExpression> getExpressions() const { return Expressions; } 178 179 /// \brief Return a counter that represents the expression 180 /// that adds LHS and RHS. 181 Counter add(Counter LHS, Counter RHS); 182 183 /// \brief Return a counter that represents the expression 184 /// that subtracts RHS from LHS. 185 Counter subtract(Counter LHS, Counter RHS); 186}; 187 188/// \brief A Counter mapping region associates a source range with 189/// a specific counter. 190struct CounterMappingRegion { 191 enum RegionKind { 192 /// \brief A CodeRegion associates some code with a counter 193 CodeRegion, 194 195 /// \brief An ExpansionRegion represents a file expansion region that 196 /// associates a source range with the expansion of a virtual source file, 197 /// such as for a macro instantiation or #include file. 198 ExpansionRegion, 199 200 /// \brief A SkippedRegion represents a source range with code that 201 /// was skipped by a preprocessor or similar means. 202 SkippedRegion 203 }; 204 205 Counter Count; 206 unsigned FileID, ExpandedFileID; 207 unsigned LineStart, ColumnStart, LineEnd, ColumnEnd; 208 RegionKind Kind; 209 210 CounterMappingRegion(Counter Count, unsigned FileID, unsigned ExpandedFileID, 211 unsigned LineStart, unsigned ColumnStart, 212 unsigned LineEnd, unsigned ColumnEnd, RegionKind Kind) 213 : Count(Count), FileID(FileID), ExpandedFileID(ExpandedFileID), 214 LineStart(LineStart), ColumnStart(ColumnStart), LineEnd(LineEnd), 215 ColumnEnd(ColumnEnd), Kind(Kind) {} 216 217 static CounterMappingRegion 218 makeRegion(Counter Count, unsigned FileID, unsigned LineStart, 219 unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) { 220 return CounterMappingRegion(Count, FileID, 0, LineStart, ColumnStart, 221 LineEnd, ColumnEnd, CodeRegion); 222 } 223 224 static CounterMappingRegion 225 makeExpansion(unsigned FileID, unsigned ExpandedFileID, unsigned LineStart, 226 unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) { 227 return CounterMappingRegion(Counter(), FileID, ExpandedFileID, LineStart, 228 ColumnStart, LineEnd, ColumnEnd, 229 ExpansionRegion); 230 } 231 232 static CounterMappingRegion 233 makeSkipped(unsigned FileID, unsigned LineStart, unsigned ColumnStart, 234 unsigned LineEnd, unsigned ColumnEnd) { 235 return CounterMappingRegion(Counter(), FileID, 0, LineStart, ColumnStart, 236 LineEnd, ColumnEnd, SkippedRegion); 237 } 238 239 240 inline std::pair<unsigned, unsigned> startLoc() const { 241 return std::pair<unsigned, unsigned>(LineStart, ColumnStart); 242 } 243 244 inline std::pair<unsigned, unsigned> endLoc() const { 245 return std::pair<unsigned, unsigned>(LineEnd, ColumnEnd); 246 } 247 248 bool operator<(const CounterMappingRegion &Other) const { 249 if (FileID != Other.FileID) 250 return FileID < Other.FileID; 251 return startLoc() < Other.startLoc(); 252 } 253 254 bool contains(const CounterMappingRegion &Other) const { 255 if (FileID != Other.FileID) 256 return false; 257 if (startLoc() > Other.startLoc()) 258 return false; 259 if (endLoc() < Other.endLoc()) 260 return false; 261 return true; 262 } 263}; 264 265/// \brief Associates a source range with an execution count. 266struct CountedRegion : public CounterMappingRegion { 267 uint64_t ExecutionCount; 268 269 CountedRegion(const CounterMappingRegion &R, uint64_t ExecutionCount) 270 : CounterMappingRegion(R), ExecutionCount(ExecutionCount) {} 271}; 272 273/// \brief A Counter mapping context is used to connect the counters, 274/// expressions and the obtained counter values. 275class CounterMappingContext { 276 ArrayRef<CounterExpression> Expressions; 277 ArrayRef<uint64_t> CounterValues; 278 279public: 280 CounterMappingContext(ArrayRef<CounterExpression> Expressions, 281 ArrayRef<uint64_t> CounterValues = None) 282 : Expressions(Expressions), CounterValues(CounterValues) {} 283 284 void setCounts(ArrayRef<uint64_t> Counts) { CounterValues = Counts; } 285 286 void dump(const Counter &C, llvm::raw_ostream &OS) const; 287 void dump(const Counter &C) const { dump(C, dbgs()); } 288 289 /// \brief Return the number of times that a region of code associated with 290 /// this counter was executed. 291 Expected<int64_t> evaluate(const Counter &C) const; 292}; 293 294/// \brief Code coverage information for a single function. 295struct FunctionRecord { 296 /// \brief Raw function name. 297 std::string Name; 298 /// \brief Associated files. 299 std::vector<std::string> Filenames; 300 /// \brief Regions in the function along with their counts. 301 std::vector<CountedRegion> CountedRegions; 302 /// \brief The number of times this function was executed. 303 uint64_t ExecutionCount; 304 305 FunctionRecord(StringRef Name, ArrayRef<StringRef> Filenames) 306 : Name(Name), Filenames(Filenames.begin(), Filenames.end()) {} 307 308 void pushRegion(CounterMappingRegion Region, uint64_t Count) { 309 if (CountedRegions.empty()) 310 ExecutionCount = Count; 311 CountedRegions.emplace_back(Region, Count); 312 } 313}; 314 315/// \brief Iterator over Functions, optionally filtered to a single file. 316class FunctionRecordIterator 317 : public iterator_facade_base<FunctionRecordIterator, 318 std::forward_iterator_tag, FunctionRecord> { 319 ArrayRef<FunctionRecord> Records; 320 ArrayRef<FunctionRecord>::iterator Current; 321 StringRef Filename; 322 323 /// \brief Skip records whose primary file is not \c Filename. 324 void skipOtherFiles(); 325 326public: 327 FunctionRecordIterator(ArrayRef<FunctionRecord> Records_, 328 StringRef Filename = "") 329 : Records(Records_), Current(Records.begin()), Filename(Filename) { 330 skipOtherFiles(); 331 } 332 333 FunctionRecordIterator() : Current(Records.begin()) {} 334 335 bool operator==(const FunctionRecordIterator &RHS) const { 336 return Current == RHS.Current && Filename == RHS.Filename; 337 } 338 339 const FunctionRecord &operator*() const { return *Current; } 340 341 FunctionRecordIterator &operator++() { 342 assert(Current != Records.end() && "incremented past end"); 343 ++Current; 344 skipOtherFiles(); 345 return *this; 346 } 347}; 348 349/// \brief Coverage information for a macro expansion or #included file. 350/// 351/// When covered code has pieces that can be expanded for more detail, such as a 352/// preprocessor macro use and its definition, these are represented as 353/// expansions whose coverage can be looked up independently. 354struct ExpansionRecord { 355 /// \brief The abstract file this expansion covers. 356 unsigned FileID; 357 /// \brief The region that expands to this record. 358 const CountedRegion &Region; 359 /// \brief Coverage for the expansion. 360 const FunctionRecord &Function; 361 362 ExpansionRecord(const CountedRegion &Region, 363 const FunctionRecord &Function) 364 : FileID(Region.ExpandedFileID), Region(Region), Function(Function) {} 365}; 366 367/// \brief The execution count information starting at a point in a file. 368/// 369/// A sequence of CoverageSegments gives execution counts for a file in format 370/// that's simple to iterate through for processing. 371struct CoverageSegment { 372 /// \brief The line where this segment begins. 373 unsigned Line; 374 /// \brief The column where this segment begins. 375 unsigned Col; 376 /// \brief The execution count, or zero if no count was recorded. 377 uint64_t Count; 378 /// \brief When false, the segment was uninstrumented or skipped. 379 bool HasCount; 380 /// \brief Whether this enters a new region or returns to a previous count. 381 bool IsRegionEntry; 382 383 CoverageSegment(unsigned Line, unsigned Col, bool IsRegionEntry) 384 : Line(Line), Col(Col), Count(0), HasCount(false), 385 IsRegionEntry(IsRegionEntry) {} 386 387 CoverageSegment(unsigned Line, unsigned Col, uint64_t Count, 388 bool IsRegionEntry) 389 : Line(Line), Col(Col), Count(Count), HasCount(true), 390 IsRegionEntry(IsRegionEntry) {} 391 392 friend bool operator==(const CoverageSegment &L, const CoverageSegment &R) { 393 return std::tie(L.Line, L.Col, L.Count, L.HasCount, L.IsRegionEntry) == 394 std::tie(R.Line, R.Col, R.Count, R.HasCount, R.IsRegionEntry); 395 } 396}; 397 398/// \brief Coverage information to be processed or displayed. 399/// 400/// This represents the coverage of an entire file, expansion, or function. It 401/// provides a sequence of CoverageSegments to iterate through, as well as the 402/// list of expansions that can be further processed. 403class CoverageData { 404 std::string Filename; 405 std::vector<CoverageSegment> Segments; 406 std::vector<ExpansionRecord> Expansions; 407 friend class CoverageMapping; 408 409public: 410 CoverageData() {} 411 412 CoverageData(StringRef Filename) : Filename(Filename) {} 413 414 CoverageData(CoverageData &&RHS) 415 : Filename(std::move(RHS.Filename)), Segments(std::move(RHS.Segments)), 416 Expansions(std::move(RHS.Expansions)) {} 417 418 /// \brief Get the name of the file this data covers. 419 StringRef getFilename() const { return Filename; } 420 421 std::vector<CoverageSegment>::iterator begin() { return Segments.begin(); } 422 std::vector<CoverageSegment>::iterator end() { return Segments.end(); } 423 bool empty() { return Segments.empty(); } 424 425 /// \brief Expansions that can be further processed. 426 ArrayRef<ExpansionRecord> getExpansions() { return Expansions; } 427}; 428 429/// \brief The mapping of profile information to coverage data. 430/// 431/// This is the main interface to get coverage information, using a profile to 432/// fill out execution counts. 433class CoverageMapping { 434 std::vector<FunctionRecord> Functions; 435 unsigned MismatchedFunctionCount; 436 437 CoverageMapping() : MismatchedFunctionCount(0) {} 438 439public: 440 /// \brief Load the coverage mapping using the given readers. 441 static Expected<std::unique_ptr<CoverageMapping>> 442 load(CoverageMappingReader &CoverageReader, 443 IndexedInstrProfReader &ProfileReader); 444 445 /// \brief Load the coverage mapping from the given files. 446 static Expected<std::unique_ptr<CoverageMapping>> 447 load(StringRef ObjectFilename, StringRef ProfileFilename, 448 StringRef Arch = StringRef()); 449 450 /// \brief The number of functions that couldn't have their profiles mapped. 451 /// 452 /// This is a count of functions whose profile is out of date or otherwise 453 /// can't be associated with any coverage information. 454 unsigned getMismatchedCount() { return MismatchedFunctionCount; } 455 456 /// \brief Returns the list of files that are covered. 457 std::vector<StringRef> getUniqueSourceFiles() const; 458 459 /// \brief Get the coverage for a particular file. 460 /// 461 /// The given filename must be the name as recorded in the coverage 462 /// information. That is, only names returned from getUniqueSourceFiles will 463 /// yield a result. 464 CoverageData getCoverageForFile(StringRef Filename) const; 465 466 /// \brief Gets all of the functions covered by this profile. 467 iterator_range<FunctionRecordIterator> getCoveredFunctions() const { 468 return make_range(FunctionRecordIterator(Functions), 469 FunctionRecordIterator()); 470 } 471 472 /// \brief Gets all of the functions in a particular file. 473 iterator_range<FunctionRecordIterator> 474 getCoveredFunctions(StringRef Filename) const { 475 return make_range(FunctionRecordIterator(Functions, Filename), 476 FunctionRecordIterator()); 477 } 478 479 /// \brief Get the list of function instantiations in the file. 480 /// 481 /// Functions that are instantiated more than once, such as C++ template 482 /// specializations, have distinct coverage records for each instantiation. 483 std::vector<const FunctionRecord *> getInstantiations(StringRef Filename); 484 485 /// \brief Get the coverage for a particular function. 486 CoverageData getCoverageForFunction(const FunctionRecord &Function); 487 488 /// \brief Get the coverage for an expansion within a coverage set. 489 CoverageData getCoverageForExpansion(const ExpansionRecord &Expansion); 490}; 491 492// Profile coverage map has the following layout: 493// [CoverageMapFileHeader] 494// [ArrayStart] 495// [CovMapFunctionRecord] 496// [CovMapFunctionRecord] 497// ... 498// [ArrayEnd] 499// [Encoded Region Mapping Data] 500LLVM_PACKED_START 501template <class IntPtrT> struct CovMapFunctionRecordV1 { 502#define COVMAP_V1 503#define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name; 504#include "llvm/ProfileData/InstrProfData.inc" 505#undef COVMAP_V1 506 507 // Return the structural hash associated with the function. 508 template <support::endianness Endian> uint64_t getFuncHash() const { 509 return support::endian::byte_swap<uint64_t, Endian>(FuncHash); 510 } 511 // Return the coverage map data size for the funciton. 512 template <support::endianness Endian> uint32_t getDataSize() const { 513 return support::endian::byte_swap<uint32_t, Endian>(DataSize); 514 } 515 // Return function lookup key. The value is consider opaque. 516 template <support::endianness Endian> IntPtrT getFuncNameRef() const { 517 return support::endian::byte_swap<IntPtrT, Endian>(NamePtr); 518 } 519 // Return the PGO name of the function */ 520 template <support::endianness Endian> 521 Error getFuncName(InstrProfSymtab &ProfileNames, StringRef &FuncName) const { 522 IntPtrT NameRef = getFuncNameRef<Endian>(); 523 uint32_t NameS = support::endian::byte_swap<uint32_t, Endian>(NameSize); 524 FuncName = ProfileNames.getFuncName(NameRef, NameS); 525 if (NameS && FuncName.empty()) 526 return make_error<CoverageMapError>(coveragemap_error::malformed); 527 return Error::success(); 528 } 529}; 530 531struct CovMapFunctionRecord { 532#define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name; 533#include "llvm/ProfileData/InstrProfData.inc" 534 535 // Return the structural hash associated with the function. 536 template <support::endianness Endian> uint64_t getFuncHash() const { 537 return support::endian::byte_swap<uint64_t, Endian>(FuncHash); 538 } 539 // Return the coverage map data size for the funciton. 540 template <support::endianness Endian> uint32_t getDataSize() const { 541 return support::endian::byte_swap<uint32_t, Endian>(DataSize); 542 } 543 // Return function lookup key. The value is consider opaque. 544 template <support::endianness Endian> uint64_t getFuncNameRef() const { 545 return support::endian::byte_swap<uint64_t, Endian>(NameRef); 546 } 547 // Return the PGO name of the function */ 548 template <support::endianness Endian> 549 Error getFuncName(InstrProfSymtab &ProfileNames, StringRef &FuncName) const { 550 uint64_t NameRef = getFuncNameRef<Endian>(); 551 FuncName = ProfileNames.getFuncName(NameRef); 552 return Error::success(); 553 } 554}; 555 556// Per module coverage mapping data header, i.e. CoverageMapFileHeader 557// documented above. 558struct CovMapHeader { 559#define COVMAP_HEADER(Type, LLVMType, Name, Init) Type Name; 560#include "llvm/ProfileData/InstrProfData.inc" 561 template <support::endianness Endian> uint32_t getNRecords() const { 562 return support::endian::byte_swap<uint32_t, Endian>(NRecords); 563 } 564 template <support::endianness Endian> uint32_t getFilenamesSize() const { 565 return support::endian::byte_swap<uint32_t, Endian>(FilenamesSize); 566 } 567 template <support::endianness Endian> uint32_t getCoverageSize() const { 568 return support::endian::byte_swap<uint32_t, Endian>(CoverageSize); 569 } 570 template <support::endianness Endian> uint32_t getVersion() const { 571 return support::endian::byte_swap<uint32_t, Endian>(Version); 572 } 573}; 574 575LLVM_PACKED_END 576 577enum CovMapVersion { 578 Version1 = 0, 579 // Function's name reference from CovMapFuncRecord is changed from raw 580 // name string pointer to MD5 to support name section compression. Name 581 // section is also compressed. 582 Version2 = 1, 583 // The current version is Version2 584 CurrentVersion = INSTR_PROF_COVMAP_VERSION 585}; 586 587template <int CovMapVersion, class IntPtrT> struct CovMapTraits { 588 typedef CovMapFunctionRecord CovMapFuncRecordType; 589 typedef uint64_t NameRefType; 590}; 591 592template <class IntPtrT> struct CovMapTraits<CovMapVersion::Version1, IntPtrT> { 593 typedef CovMapFunctionRecordV1<IntPtrT> CovMapFuncRecordType; 594 typedef IntPtrT NameRefType; 595}; 596 597} // end namespace coverage 598 599/// \brief Provide DenseMapInfo for CounterExpression 600template<> struct DenseMapInfo<coverage::CounterExpression> { 601 static inline coverage::CounterExpression getEmptyKey() { 602 using namespace coverage; 603 return CounterExpression(CounterExpression::ExprKind::Subtract, 604 Counter::getCounter(~0U), 605 Counter::getCounter(~0U)); 606 } 607 608 static inline coverage::CounterExpression getTombstoneKey() { 609 using namespace coverage; 610 return CounterExpression(CounterExpression::ExprKind::Add, 611 Counter::getCounter(~0U), 612 Counter::getCounter(~0U)); 613 } 614 615 static unsigned getHashValue(const coverage::CounterExpression &V) { 616 return static_cast<unsigned>( 617 hash_combine(V.Kind, V.LHS.getKind(), V.LHS.getCounterID(), 618 V.RHS.getKind(), V.RHS.getCounterID())); 619 } 620 621 static bool isEqual(const coverage::CounterExpression &LHS, 622 const coverage::CounterExpression &RHS) { 623 return LHS.Kind == RHS.Kind && LHS.LHS == RHS.LHS && LHS.RHS == RHS.RHS; 624 } 625}; 626 627} // end namespace llvm 628 629#endif // LLVM_PROFILEDATA_COVERAGEMAPPING_H_ 630