1321369Sdim//===- CoverageMapping.h - Code coverage mapping support --------*- C++ -*-===// 2303231Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6303231Sdim// 7303231Sdim//===----------------------------------------------------------------------===// 8303231Sdim// 9303231Sdim// Code coverage mapping data is generated by clang and read by 10303231Sdim// llvm-cov to show code coverage statistics for a file. 11303231Sdim// 12303231Sdim//===----------------------------------------------------------------------===// 13303231Sdim 14321369Sdim#ifndef LLVM_PROFILEDATA_COVERAGE_COVERAGEMAPPING_H 15321369Sdim#define LLVM_PROFILEDATA_COVERAGE_COVERAGEMAPPING_H 16303231Sdim 17303231Sdim#include "llvm/ADT/ArrayRef.h" 18303231Sdim#include "llvm/ADT/DenseMap.h" 19341825Sdim#include "llvm/ADT/DenseSet.h" 20303231Sdim#include "llvm/ADT/Hashing.h" 21321369Sdim#include "llvm/ADT/None.h" 22321369Sdim#include "llvm/ADT/StringRef.h" 23314564Sdim#include "llvm/ADT/StringSet.h" 24303231Sdim#include "llvm/ADT/iterator.h" 25321369Sdim#include "llvm/ADT/iterator_range.h" 26303231Sdim#include "llvm/ProfileData/InstrProf.h" 27321369Sdim#include "llvm/Support/Compiler.h" 28303231Sdim#include "llvm/Support/Debug.h" 29303231Sdim#include "llvm/Support/Endian.h" 30321369Sdim#include "llvm/Support/Error.h" 31303231Sdim#include "llvm/Support/raw_ostream.h" 32321369Sdim#include <cassert> 33321369Sdim#include <cstdint> 34321369Sdim#include <iterator> 35321369Sdim#include <memory> 36321369Sdim#include <string> 37303231Sdim#include <system_error> 38303231Sdim#include <tuple> 39321369Sdim#include <utility> 40321369Sdim#include <vector> 41303231Sdim 42303231Sdimnamespace llvm { 43321369Sdim 44321369Sdimclass IndexedInstrProfReader; 45321369Sdim 46303231Sdimnamespace coverage { 47303231Sdim 48321369Sdimclass CoverageMappingReader; 49321369Sdimstruct CoverageMappingRecord; 50321369Sdim 51303231Sdimenum class coveragemap_error { 52303231Sdim success = 0, 53303231Sdim eof, 54303231Sdim no_data_found, 55303231Sdim unsupported_version, 56303231Sdim truncated, 57303231Sdim malformed 58303231Sdim}; 59303231Sdim 60303231Sdimconst std::error_category &coveragemap_category(); 61303231Sdim 62303231Sdiminline std::error_code make_error_code(coveragemap_error E) { 63303231Sdim return std::error_code(static_cast<int>(E), coveragemap_category()); 64303231Sdim} 65303231Sdim 66303231Sdimclass CoverageMapError : public ErrorInfo<CoverageMapError> { 67303231Sdimpublic: 68303231Sdim CoverageMapError(coveragemap_error Err) : Err(Err) { 69303231Sdim assert(Err != coveragemap_error::success && "Not an error"); 70303231Sdim } 71303231Sdim 72303231Sdim std::string message() const override; 73303231Sdim 74303231Sdim void log(raw_ostream &OS) const override { OS << message(); } 75303231Sdim 76303231Sdim std::error_code convertToErrorCode() const override { 77303231Sdim return make_error_code(Err); 78303231Sdim } 79303231Sdim 80303231Sdim coveragemap_error get() const { return Err; } 81303231Sdim 82303231Sdim static char ID; 83303231Sdim 84303231Sdimprivate: 85303231Sdim coveragemap_error Err; 86303231Sdim}; 87303231Sdim 88327952Sdim/// A Counter is an abstract value that describes how to compute the 89303231Sdim/// execution count for a region of code using the collected profile count data. 90303231Sdimstruct Counter { 91303231Sdim enum CounterKind { Zero, CounterValueReference, Expression }; 92303231Sdim static const unsigned EncodingTagBits = 2; 93303231Sdim static const unsigned EncodingTagMask = 0x3; 94303231Sdim static const unsigned EncodingCounterTagAndExpansionRegionTagBits = 95303231Sdim EncodingTagBits + 1; 96303231Sdim 97303231Sdimprivate: 98321369Sdim CounterKind Kind = Zero; 99321369Sdim unsigned ID = 0; 100303231Sdim 101303231Sdim Counter(CounterKind Kind, unsigned ID) : Kind(Kind), ID(ID) {} 102303231Sdim 103303231Sdimpublic: 104321369Sdim Counter() = default; 105303231Sdim 106303231Sdim CounterKind getKind() const { return Kind; } 107303231Sdim 108303231Sdim bool isZero() const { return Kind == Zero; } 109303231Sdim 110303231Sdim bool isExpression() const { return Kind == Expression; } 111303231Sdim 112303231Sdim unsigned getCounterID() const { return ID; } 113303231Sdim 114303231Sdim unsigned getExpressionID() const { return ID; } 115303231Sdim 116303231Sdim friend bool operator==(const Counter &LHS, const Counter &RHS) { 117303231Sdim return LHS.Kind == RHS.Kind && LHS.ID == RHS.ID; 118303231Sdim } 119303231Sdim 120303231Sdim friend bool operator!=(const Counter &LHS, const Counter &RHS) { 121303231Sdim return !(LHS == RHS); 122303231Sdim } 123303231Sdim 124303231Sdim friend bool operator<(const Counter &LHS, const Counter &RHS) { 125303231Sdim return std::tie(LHS.Kind, LHS.ID) < std::tie(RHS.Kind, RHS.ID); 126303231Sdim } 127303231Sdim 128327952Sdim /// Return the counter that represents the number zero. 129303231Sdim static Counter getZero() { return Counter(); } 130303231Sdim 131327952Sdim /// Return the counter that corresponds to a specific profile counter. 132303231Sdim static Counter getCounter(unsigned CounterId) { 133303231Sdim return Counter(CounterValueReference, CounterId); 134303231Sdim } 135303231Sdim 136327952Sdim /// Return the counter that corresponds to a specific addition counter 137327952Sdim /// expression. 138303231Sdim static Counter getExpression(unsigned ExpressionId) { 139303231Sdim return Counter(Expression, ExpressionId); 140303231Sdim } 141303231Sdim}; 142303231Sdim 143327952Sdim/// A Counter expression is a value that represents an arithmetic operation 144327952Sdim/// with two counters. 145303231Sdimstruct CounterExpression { 146303231Sdim enum ExprKind { Subtract, Add }; 147303231Sdim ExprKind Kind; 148303231Sdim Counter LHS, RHS; 149303231Sdim 150303231Sdim CounterExpression(ExprKind Kind, Counter LHS, Counter RHS) 151303231Sdim : Kind(Kind), LHS(LHS), RHS(RHS) {} 152303231Sdim}; 153303231Sdim 154327952Sdim/// A Counter expression builder is used to construct the counter expressions. 155327952Sdim/// It avoids unnecessary duplication and simplifies algebraic expressions. 156303231Sdimclass CounterExpressionBuilder { 157327952Sdim /// A list of all the counter expressions 158303231Sdim std::vector<CounterExpression> Expressions; 159321369Sdim 160327952Sdim /// A lookup table for the index of a given expression. 161321369Sdim DenseMap<CounterExpression, unsigned> ExpressionIndices; 162303231Sdim 163327952Sdim /// Return the counter which corresponds to the given expression. 164303231Sdim /// 165303231Sdim /// If the given expression is already stored in the builder, a counter 166303231Sdim /// that references that expression is returned. Otherwise, the given 167303231Sdim /// expression is added to the builder's collection of expressions. 168303231Sdim Counter get(const CounterExpression &E); 169303231Sdim 170321369Sdim /// Represents a term in a counter expression tree. 171321369Sdim struct Term { 172321369Sdim unsigned CounterID; 173321369Sdim int Factor; 174321369Sdim 175321369Sdim Term(unsigned CounterID, int Factor) 176321369Sdim : CounterID(CounterID), Factor(Factor) {} 177321369Sdim }; 178321369Sdim 179327952Sdim /// Gather the terms of the expression tree for processing. 180303231Sdim /// 181303231Sdim /// This collects each addition and subtraction referenced by the counter into 182303231Sdim /// a sequence that can be sorted and combined to build a simplified counter 183303231Sdim /// expression. 184321369Sdim void extractTerms(Counter C, int Sign, SmallVectorImpl<Term> &Terms); 185303231Sdim 186327952Sdim /// Simplifies the given expression tree 187303231Sdim /// by getting rid of algebraically redundant operations. 188303231Sdim Counter simplify(Counter ExpressionTree); 189303231Sdim 190303231Sdimpublic: 191303231Sdim ArrayRef<CounterExpression> getExpressions() const { return Expressions; } 192303231Sdim 193327952Sdim /// Return a counter that represents the expression that adds LHS and RHS. 194303231Sdim Counter add(Counter LHS, Counter RHS); 195303231Sdim 196327952Sdim /// Return a counter that represents the expression that subtracts RHS from 197327952Sdim /// LHS. 198303231Sdim Counter subtract(Counter LHS, Counter RHS); 199303231Sdim}; 200303231Sdim 201327952Sdimusing LineColPair = std::pair<unsigned, unsigned>; 202327952Sdim 203327952Sdim/// A Counter mapping region associates a source range with a specific counter. 204303231Sdimstruct CounterMappingRegion { 205303231Sdim enum RegionKind { 206327952Sdim /// A CodeRegion associates some code with a counter 207303231Sdim CodeRegion, 208303231Sdim 209341825Sdim /// An ExpansionRegion represents a file expansion region that associates 210327952Sdim /// a source range with the expansion of a virtual source file, such as 211327952Sdim /// for a macro instantiation or #include file. 212303231Sdim ExpansionRegion, 213303231Sdim 214327952Sdim /// A SkippedRegion represents a source range with code that was skipped 215327952Sdim /// by a preprocessor or similar means. 216327952Sdim SkippedRegion, 217327952Sdim 218327952Sdim /// A GapRegion is like a CodeRegion, but its count is only set as the 219327952Sdim /// line execution count when its the only region in the line. 220327952Sdim GapRegion 221303231Sdim }; 222303231Sdim 223303231Sdim Counter Count; 224303231Sdim unsigned FileID, ExpandedFileID; 225303231Sdim unsigned LineStart, ColumnStart, LineEnd, ColumnEnd; 226303231Sdim RegionKind Kind; 227303231Sdim 228303231Sdim CounterMappingRegion(Counter Count, unsigned FileID, unsigned ExpandedFileID, 229303231Sdim unsigned LineStart, unsigned ColumnStart, 230303231Sdim unsigned LineEnd, unsigned ColumnEnd, RegionKind Kind) 231303231Sdim : Count(Count), FileID(FileID), ExpandedFileID(ExpandedFileID), 232303231Sdim LineStart(LineStart), ColumnStart(ColumnStart), LineEnd(LineEnd), 233303231Sdim ColumnEnd(ColumnEnd), Kind(Kind) {} 234303231Sdim 235303231Sdim static CounterMappingRegion 236303231Sdim makeRegion(Counter Count, unsigned FileID, unsigned LineStart, 237303231Sdim unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) { 238303231Sdim return CounterMappingRegion(Count, FileID, 0, LineStart, ColumnStart, 239303231Sdim LineEnd, ColumnEnd, CodeRegion); 240303231Sdim } 241303231Sdim 242303231Sdim static CounterMappingRegion 243303231Sdim makeExpansion(unsigned FileID, unsigned ExpandedFileID, unsigned LineStart, 244303231Sdim unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) { 245303231Sdim return CounterMappingRegion(Counter(), FileID, ExpandedFileID, LineStart, 246303231Sdim ColumnStart, LineEnd, ColumnEnd, 247303231Sdim ExpansionRegion); 248303231Sdim } 249303231Sdim 250303231Sdim static CounterMappingRegion 251303231Sdim makeSkipped(unsigned FileID, unsigned LineStart, unsigned ColumnStart, 252303231Sdim unsigned LineEnd, unsigned ColumnEnd) { 253303231Sdim return CounterMappingRegion(Counter(), FileID, 0, LineStart, ColumnStart, 254303231Sdim LineEnd, ColumnEnd, SkippedRegion); 255303231Sdim } 256303231Sdim 257327952Sdim static CounterMappingRegion 258327952Sdim makeGapRegion(Counter Count, unsigned FileID, unsigned LineStart, 259327952Sdim unsigned ColumnStart, unsigned LineEnd, unsigned ColumnEnd) { 260327952Sdim return CounterMappingRegion(Count, FileID, 0, LineStart, ColumnStart, 261327952Sdim LineEnd, (1U << 31) | ColumnEnd, GapRegion); 262303231Sdim } 263303231Sdim 264327952Sdim inline LineColPair startLoc() const { 265327952Sdim return LineColPair(LineStart, ColumnStart); 266303231Sdim } 267327952Sdim 268327952Sdim inline LineColPair endLoc() const { return LineColPair(LineEnd, ColumnEnd); } 269303231Sdim}; 270303231Sdim 271327952Sdim/// Associates a source range with an execution count. 272303231Sdimstruct CountedRegion : public CounterMappingRegion { 273303231Sdim uint64_t ExecutionCount; 274303231Sdim 275303231Sdim CountedRegion(const CounterMappingRegion &R, uint64_t ExecutionCount) 276303231Sdim : CounterMappingRegion(R), ExecutionCount(ExecutionCount) {} 277303231Sdim}; 278303231Sdim 279327952Sdim/// A Counter mapping context is used to connect the counters, expressions 280327952Sdim/// and the obtained counter values. 281303231Sdimclass CounterMappingContext { 282303231Sdim ArrayRef<CounterExpression> Expressions; 283303231Sdim ArrayRef<uint64_t> CounterValues; 284303231Sdim 285303231Sdimpublic: 286303231Sdim CounterMappingContext(ArrayRef<CounterExpression> Expressions, 287303231Sdim ArrayRef<uint64_t> CounterValues = None) 288303231Sdim : Expressions(Expressions), CounterValues(CounterValues) {} 289303231Sdim 290303231Sdim void setCounts(ArrayRef<uint64_t> Counts) { CounterValues = Counts; } 291303231Sdim 292321369Sdim void dump(const Counter &C, raw_ostream &OS) const; 293303231Sdim void dump(const Counter &C) const { dump(C, dbgs()); } 294303231Sdim 295327952Sdim /// Return the number of times that a region of code associated with this 296327952Sdim /// counter was executed. 297303231Sdim Expected<int64_t> evaluate(const Counter &C) const; 298303231Sdim}; 299303231Sdim 300327952Sdim/// Code coverage information for a single function. 301303231Sdimstruct FunctionRecord { 302327952Sdim /// Raw function name. 303303231Sdim std::string Name; 304360784Sdim /// Mapping from FileID (i.e. vector index) to filename. Used to support 305360784Sdim /// macro expansions within a function in which the macro and function are 306360784Sdim /// defined in separate files. 307360784Sdim /// 308360784Sdim /// TODO: Uniquing filenames across all function records may be a performance 309360784Sdim /// optimization. 310303231Sdim std::vector<std::string> Filenames; 311327952Sdim /// Regions in the function along with their counts. 312303231Sdim std::vector<CountedRegion> CountedRegions; 313327952Sdim /// The number of times this function was executed. 314360784Sdim uint64_t ExecutionCount = 0; 315303231Sdim 316303231Sdim FunctionRecord(StringRef Name, ArrayRef<StringRef> Filenames) 317303231Sdim : Name(Name), Filenames(Filenames.begin(), Filenames.end()) {} 318303231Sdim 319314564Sdim FunctionRecord(FunctionRecord &&FR) = default; 320314564Sdim FunctionRecord &operator=(FunctionRecord &&) = default; 321314564Sdim 322303231Sdim void pushRegion(CounterMappingRegion Region, uint64_t Count) { 323303231Sdim if (CountedRegions.empty()) 324303231Sdim ExecutionCount = Count; 325303231Sdim CountedRegions.emplace_back(Region, Count); 326303231Sdim } 327303231Sdim}; 328303231Sdim 329327952Sdim/// Iterator over Functions, optionally filtered to a single file. 330303231Sdimclass FunctionRecordIterator 331303231Sdim : public iterator_facade_base<FunctionRecordIterator, 332303231Sdim std::forward_iterator_tag, FunctionRecord> { 333303231Sdim ArrayRef<FunctionRecord> Records; 334303231Sdim ArrayRef<FunctionRecord>::iterator Current; 335303231Sdim StringRef Filename; 336303231Sdim 337327952Sdim /// Skip records whose primary file is not \c Filename. 338303231Sdim void skipOtherFiles(); 339303231Sdim 340303231Sdimpublic: 341303231Sdim FunctionRecordIterator(ArrayRef<FunctionRecord> Records_, 342303231Sdim StringRef Filename = "") 343303231Sdim : Records(Records_), Current(Records.begin()), Filename(Filename) { 344303231Sdim skipOtherFiles(); 345303231Sdim } 346303231Sdim 347303231Sdim FunctionRecordIterator() : Current(Records.begin()) {} 348303231Sdim 349303231Sdim bool operator==(const FunctionRecordIterator &RHS) const { 350303231Sdim return Current == RHS.Current && Filename == RHS.Filename; 351303231Sdim } 352303231Sdim 353303231Sdim const FunctionRecord &operator*() const { return *Current; } 354303231Sdim 355303231Sdim FunctionRecordIterator &operator++() { 356303231Sdim assert(Current != Records.end() && "incremented past end"); 357303231Sdim ++Current; 358303231Sdim skipOtherFiles(); 359303231Sdim return *this; 360303231Sdim } 361303231Sdim}; 362303231Sdim 363327952Sdim/// Coverage information for a macro expansion or #included file. 364303231Sdim/// 365303231Sdim/// When covered code has pieces that can be expanded for more detail, such as a 366303231Sdim/// preprocessor macro use and its definition, these are represented as 367303231Sdim/// expansions whose coverage can be looked up independently. 368303231Sdimstruct ExpansionRecord { 369327952Sdim /// The abstract file this expansion covers. 370303231Sdim unsigned FileID; 371327952Sdim /// The region that expands to this record. 372303231Sdim const CountedRegion &Region; 373327952Sdim /// Coverage for the expansion. 374303231Sdim const FunctionRecord &Function; 375303231Sdim 376303231Sdim ExpansionRecord(const CountedRegion &Region, 377303231Sdim const FunctionRecord &Function) 378303231Sdim : FileID(Region.ExpandedFileID), Region(Region), Function(Function) {} 379303231Sdim}; 380303231Sdim 381327952Sdim/// The execution count information starting at a point in a file. 382303231Sdim/// 383303231Sdim/// A sequence of CoverageSegments gives execution counts for a file in format 384303231Sdim/// that's simple to iterate through for processing. 385303231Sdimstruct CoverageSegment { 386327952Sdim /// The line where this segment begins. 387303231Sdim unsigned Line; 388327952Sdim /// The column where this segment begins. 389303231Sdim unsigned Col; 390327952Sdim /// The execution count, or zero if no count was recorded. 391303231Sdim uint64_t Count; 392327952Sdim /// When false, the segment was uninstrumented or skipped. 393303231Sdim bool HasCount; 394327952Sdim /// Whether this enters a new region or returns to a previous count. 395303231Sdim bool IsRegionEntry; 396327952Sdim /// Whether this enters a gap region. 397327952Sdim bool IsGapRegion; 398303231Sdim 399303231Sdim CoverageSegment(unsigned Line, unsigned Col, bool IsRegionEntry) 400303231Sdim : Line(Line), Col(Col), Count(0), HasCount(false), 401327952Sdim IsRegionEntry(IsRegionEntry), IsGapRegion(false) {} 402303231Sdim 403303231Sdim CoverageSegment(unsigned Line, unsigned Col, uint64_t Count, 404327952Sdim bool IsRegionEntry, bool IsGapRegion = false) 405303231Sdim : Line(Line), Col(Col), Count(Count), HasCount(true), 406327952Sdim IsRegionEntry(IsRegionEntry), IsGapRegion(IsGapRegion) {} 407303231Sdim 408303231Sdim friend bool operator==(const CoverageSegment &L, const CoverageSegment &R) { 409327952Sdim return std::tie(L.Line, L.Col, L.Count, L.HasCount, L.IsRegionEntry, 410327952Sdim L.IsGapRegion) == std::tie(R.Line, R.Col, R.Count, 411327952Sdim R.HasCount, R.IsRegionEntry, 412327952Sdim R.IsGapRegion); 413303231Sdim } 414303231Sdim}; 415303231Sdim 416327952Sdim/// An instantiation group contains a \c FunctionRecord list, such that each 417327952Sdim/// record corresponds to a distinct instantiation of the same function. 418303231Sdim/// 419327952Sdim/// Note that it's possible for a function to have more than one instantiation 420327952Sdim/// (consider C++ template specializations or static inline functions). 421327952Sdimclass InstantiationGroup { 422327952Sdim friend class CoverageMapping; 423327952Sdim 424327952Sdim unsigned Line; 425327952Sdim unsigned Col; 426327952Sdim std::vector<const FunctionRecord *> Instantiations; 427327952Sdim 428327952Sdim InstantiationGroup(unsigned Line, unsigned Col, 429327952Sdim std::vector<const FunctionRecord *> Instantiations) 430327952Sdim : Line(Line), Col(Col), Instantiations(std::move(Instantiations)) {} 431327952Sdim 432327952Sdimpublic: 433327952Sdim InstantiationGroup(const InstantiationGroup &) = delete; 434327952Sdim InstantiationGroup(InstantiationGroup &&) = default; 435327952Sdim 436327952Sdim /// Get the number of instantiations in this group. 437327952Sdim size_t size() const { return Instantiations.size(); } 438327952Sdim 439327952Sdim /// Get the line where the common function was defined. 440327952Sdim unsigned getLine() const { return Line; } 441327952Sdim 442327952Sdim /// Get the column where the common function was defined. 443327952Sdim unsigned getColumn() const { return Col; } 444327952Sdim 445327952Sdim /// Check if the instantiations in this group have a common mangled name. 446327952Sdim bool hasName() const { 447327952Sdim for (unsigned I = 1, E = Instantiations.size(); I < E; ++I) 448327952Sdim if (Instantiations[I]->Name != Instantiations[0]->Name) 449327952Sdim return false; 450327952Sdim return true; 451327952Sdim } 452327952Sdim 453327952Sdim /// Get the common mangled name for instantiations in this group. 454327952Sdim StringRef getName() const { 455327952Sdim assert(hasName() && "Instantiations don't have a shared name"); 456327952Sdim return Instantiations[0]->Name; 457327952Sdim } 458327952Sdim 459327952Sdim /// Get the total execution count of all instantiations in this group. 460327952Sdim uint64_t getTotalExecutionCount() const { 461327952Sdim uint64_t Count = 0; 462327952Sdim for (const FunctionRecord *F : Instantiations) 463327952Sdim Count += F->ExecutionCount; 464327952Sdim return Count; 465327952Sdim } 466327952Sdim 467327952Sdim /// Get the instantiations in this group. 468327952Sdim ArrayRef<const FunctionRecord *> getInstantiations() const { 469327952Sdim return Instantiations; 470327952Sdim } 471327952Sdim}; 472327952Sdim 473327952Sdim/// Coverage information to be processed or displayed. 474327952Sdim/// 475303231Sdim/// This represents the coverage of an entire file, expansion, or function. It 476303231Sdim/// provides a sequence of CoverageSegments to iterate through, as well as the 477303231Sdim/// list of expansions that can be further processed. 478303231Sdimclass CoverageData { 479321369Sdim friend class CoverageMapping; 480321369Sdim 481303231Sdim std::string Filename; 482303231Sdim std::vector<CoverageSegment> Segments; 483303231Sdim std::vector<ExpansionRecord> Expansions; 484303231Sdim 485303231Sdimpublic: 486321369Sdim CoverageData() = default; 487303231Sdim 488303231Sdim CoverageData(StringRef Filename) : Filename(Filename) {} 489303231Sdim 490327952Sdim /// Get the name of the file this data covers. 491303231Sdim StringRef getFilename() const { return Filename; } 492303231Sdim 493327952Sdim /// Get an iterator over the coverage segments for this object. The segments 494327952Sdim /// are guaranteed to be uniqued and sorted by location. 495314564Sdim std::vector<CoverageSegment>::const_iterator begin() const { 496314564Sdim return Segments.begin(); 497314564Sdim } 498321369Sdim 499314564Sdim std::vector<CoverageSegment>::const_iterator end() const { 500314564Sdim return Segments.end(); 501314564Sdim } 502321369Sdim 503314564Sdim bool empty() const { return Segments.empty(); } 504303231Sdim 505327952Sdim /// Expansions that can be further processed. 506314564Sdim ArrayRef<ExpansionRecord> getExpansions() const { return Expansions; } 507303231Sdim}; 508303231Sdim 509327952Sdim/// The mapping of profile information to coverage data. 510303231Sdim/// 511303231Sdim/// This is the main interface to get coverage information, using a profile to 512303231Sdim/// fill out execution counts. 513303231Sdimclass CoverageMapping { 514341825Sdim DenseMap<size_t, DenseSet<size_t>> RecordProvenance; 515303231Sdim std::vector<FunctionRecord> Functions; 516360784Sdim DenseMap<size_t, SmallVector<unsigned, 0>> FilenameHash2RecordIndices; 517327952Sdim std::vector<std::pair<std::string, uint64_t>> FuncHashMismatches; 518303231Sdim 519321369Sdim CoverageMapping() = default; 520303231Sdim 521327952Sdim /// Add a function record corresponding to \p Record. 522314564Sdim Error loadFunctionRecord(const CoverageMappingRecord &Record, 523314564Sdim IndexedInstrProfReader &ProfileReader); 524314564Sdim 525360784Sdim /// Look up the indices for function records which are at least partially 526360784Sdim /// defined in the specified file. This is guaranteed to return a superset of 527360784Sdim /// such records: extra records not in the file may be included if there is 528360784Sdim /// a hash collision on the filename. Clients must be robust to collisions. 529360784Sdim ArrayRef<unsigned> 530360784Sdim getImpreciseRecordIndicesForFilename(StringRef Filename) const; 531360784Sdim 532303231Sdimpublic: 533321369Sdim CoverageMapping(const CoverageMapping &) = delete; 534321369Sdim CoverageMapping &operator=(const CoverageMapping &) = delete; 535321369Sdim 536327952Sdim /// Load the coverage mapping using the given readers. 537303231Sdim static Expected<std::unique_ptr<CoverageMapping>> 538314564Sdim load(ArrayRef<std::unique_ptr<CoverageMappingReader>> CoverageReaders, 539314564Sdim IndexedInstrProfReader &ProfileReader); 540314564Sdim 541327952Sdim /// Load the coverage mapping from the given object files and profile. If 542327952Sdim /// \p Arches is non-empty, it must specify an architecture for each object. 543360784Sdim /// Ignores non-instrumented object files unless all are not instrumented. 544303231Sdim static Expected<std::unique_ptr<CoverageMapping>> 545314564Sdim load(ArrayRef<StringRef> ObjectFilenames, StringRef ProfileFilename, 546327952Sdim ArrayRef<StringRef> Arches = None); 547303231Sdim 548327952Sdim /// The number of functions that couldn't have their profiles mapped. 549303231Sdim /// 550303231Sdim /// This is a count of functions whose profile is out of date or otherwise 551303231Sdim /// can't be associated with any coverage information. 552344779Sdim unsigned getMismatchedCount() const { return FuncHashMismatches.size(); } 553303231Sdim 554327952Sdim /// A hash mismatch occurs when a profile record for a symbol does not have 555327952Sdim /// the same hash as a coverage mapping record for the same symbol. This 556327952Sdim /// returns a list of hash mismatches, where each mismatch is a pair of the 557327952Sdim /// symbol name and its coverage mapping hash. 558327952Sdim ArrayRef<std::pair<std::string, uint64_t>> getHashMismatches() const { 559327952Sdim return FuncHashMismatches; 560327952Sdim } 561327952Sdim 562327952Sdim /// Returns a lexicographically sorted, unique list of files that are 563314564Sdim /// covered. 564303231Sdim std::vector<StringRef> getUniqueSourceFiles() const; 565303231Sdim 566327952Sdim /// Get the coverage for a particular file. 567303231Sdim /// 568303231Sdim /// The given filename must be the name as recorded in the coverage 569303231Sdim /// information. That is, only names returned from getUniqueSourceFiles will 570303231Sdim /// yield a result. 571303231Sdim CoverageData getCoverageForFile(StringRef Filename) const; 572303231Sdim 573327952Sdim /// Get the coverage for a particular function. 574327952Sdim CoverageData getCoverageForFunction(const FunctionRecord &Function) const; 575327952Sdim 576327952Sdim /// Get the coverage for an expansion within a coverage set. 577327952Sdim CoverageData getCoverageForExpansion(const ExpansionRecord &Expansion) const; 578327952Sdim 579327952Sdim /// Gets all of the functions covered by this profile. 580303231Sdim iterator_range<FunctionRecordIterator> getCoveredFunctions() const { 581303231Sdim return make_range(FunctionRecordIterator(Functions), 582303231Sdim FunctionRecordIterator()); 583303231Sdim } 584303231Sdim 585327952Sdim /// Gets all of the functions in a particular file. 586303231Sdim iterator_range<FunctionRecordIterator> 587303231Sdim getCoveredFunctions(StringRef Filename) const { 588303231Sdim return make_range(FunctionRecordIterator(Functions, Filename), 589303231Sdim FunctionRecordIterator()); 590303231Sdim } 591303231Sdim 592327952Sdim /// Get the list of function instantiation groups in a particular file. 593303231Sdim /// 594327952Sdim /// Every instantiation group in a program is attributed to exactly one file: 595327952Sdim /// the file in which the definition for the common function begins. 596327952Sdim std::vector<InstantiationGroup> 597327952Sdim getInstantiationGroups(StringRef Filename) const; 598327952Sdim}; 599303231Sdim 600327952Sdim/// Coverage statistics for a single line. 601327952Sdimclass LineCoverageStats { 602327952Sdim uint64_t ExecutionCount; 603327952Sdim bool HasMultipleRegions; 604327952Sdim bool Mapped; 605327952Sdim unsigned Line; 606327952Sdim ArrayRef<const CoverageSegment *> LineSegments; 607327952Sdim const CoverageSegment *WrappedSegment; 608303231Sdim 609327952Sdim friend class LineCoverageIterator; 610327952Sdim LineCoverageStats() = default; 611327952Sdim 612327952Sdimpublic: 613327952Sdim LineCoverageStats(ArrayRef<const CoverageSegment *> LineSegments, 614327952Sdim const CoverageSegment *WrappedSegment, unsigned Line); 615327952Sdim 616327952Sdim uint64_t getExecutionCount() const { return ExecutionCount; } 617327952Sdim 618327952Sdim bool hasMultipleRegions() const { return HasMultipleRegions; } 619327952Sdim 620327952Sdim bool isMapped() const { return Mapped; } 621327952Sdim 622327952Sdim unsigned getLine() const { return Line; } 623327952Sdim 624327952Sdim ArrayRef<const CoverageSegment *> getLineSegments() const { 625327952Sdim return LineSegments; 626327952Sdim } 627327952Sdim 628327952Sdim const CoverageSegment *getWrappedSegment() const { return WrappedSegment; } 629303231Sdim}; 630303231Sdim 631327952Sdim/// An iterator over the \c LineCoverageStats objects for lines described by 632327952Sdim/// a \c CoverageData instance. 633327952Sdimclass LineCoverageIterator 634327952Sdim : public iterator_facade_base< 635327952Sdim LineCoverageIterator, std::forward_iterator_tag, LineCoverageStats> { 636327952Sdimpublic: 637327952Sdim LineCoverageIterator(const CoverageData &CD) 638327952Sdim : LineCoverageIterator(CD, CD.begin()->Line) {} 639327952Sdim 640327952Sdim LineCoverageIterator(const CoverageData &CD, unsigned Line) 641327952Sdim : CD(CD), WrappedSegment(nullptr), Next(CD.begin()), Ended(false), 642327952Sdim Line(Line), Segments(), Stats() { 643327952Sdim this->operator++(); 644327952Sdim } 645327952Sdim 646327952Sdim bool operator==(const LineCoverageIterator &R) const { 647327952Sdim return &CD == &R.CD && Next == R.Next && Ended == R.Ended; 648327952Sdim } 649327952Sdim 650327952Sdim const LineCoverageStats &operator*() const { return Stats; } 651327952Sdim 652327952Sdim LineCoverageStats &operator*() { return Stats; } 653327952Sdim 654327952Sdim LineCoverageIterator &operator++(); 655327952Sdim 656327952Sdim LineCoverageIterator getEnd() const { 657327952Sdim auto EndIt = *this; 658327952Sdim EndIt.Next = CD.end(); 659327952Sdim EndIt.Ended = true; 660327952Sdim return EndIt; 661327952Sdim } 662327952Sdim 663327952Sdimprivate: 664327952Sdim const CoverageData &CD; 665327952Sdim const CoverageSegment *WrappedSegment; 666327952Sdim std::vector<CoverageSegment>::const_iterator Next; 667327952Sdim bool Ended; 668327952Sdim unsigned Line; 669327952Sdim SmallVector<const CoverageSegment *, 4> Segments; 670327952Sdim LineCoverageStats Stats; 671327952Sdim}; 672327952Sdim 673327952Sdim/// Get a \c LineCoverageIterator range for the lines described by \p CD. 674327952Sdimstatic inline iterator_range<LineCoverageIterator> 675327952SdimgetLineCoverageStats(const coverage::CoverageData &CD) { 676327952Sdim auto Begin = LineCoverageIterator(CD); 677327952Sdim auto End = Begin.getEnd(); 678327952Sdim return make_range(Begin, End); 679327952Sdim} 680327952Sdim 681303231Sdim// Profile coverage map has the following layout: 682303231Sdim// [CoverageMapFileHeader] 683303231Sdim// [ArrayStart] 684303231Sdim// [CovMapFunctionRecord] 685303231Sdim// [CovMapFunctionRecord] 686303231Sdim// ... 687303231Sdim// [ArrayEnd] 688303231Sdim// [Encoded Region Mapping Data] 689303231SdimLLVM_PACKED_START 690303231Sdimtemplate <class IntPtrT> struct CovMapFunctionRecordV1 { 691303231Sdim#define COVMAP_V1 692303231Sdim#define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name; 693303231Sdim#include "llvm/ProfileData/InstrProfData.inc" 694303231Sdim#undef COVMAP_V1 695303231Sdim 696303231Sdim // Return the structural hash associated with the function. 697303231Sdim template <support::endianness Endian> uint64_t getFuncHash() const { 698303231Sdim return support::endian::byte_swap<uint64_t, Endian>(FuncHash); 699303231Sdim } 700321369Sdim 701303231Sdim // Return the coverage map data size for the funciton. 702303231Sdim template <support::endianness Endian> uint32_t getDataSize() const { 703303231Sdim return support::endian::byte_swap<uint32_t, Endian>(DataSize); 704303231Sdim } 705321369Sdim 706303231Sdim // Return function lookup key. The value is consider opaque. 707303231Sdim template <support::endianness Endian> IntPtrT getFuncNameRef() const { 708303231Sdim return support::endian::byte_swap<IntPtrT, Endian>(NamePtr); 709303231Sdim } 710321369Sdim 711303231Sdim // Return the PGO name of the function */ 712303231Sdim template <support::endianness Endian> 713303231Sdim Error getFuncName(InstrProfSymtab &ProfileNames, StringRef &FuncName) const { 714303231Sdim IntPtrT NameRef = getFuncNameRef<Endian>(); 715303231Sdim uint32_t NameS = support::endian::byte_swap<uint32_t, Endian>(NameSize); 716303231Sdim FuncName = ProfileNames.getFuncName(NameRef, NameS); 717303231Sdim if (NameS && FuncName.empty()) 718303231Sdim return make_error<CoverageMapError>(coveragemap_error::malformed); 719303231Sdim return Error::success(); 720303231Sdim } 721303231Sdim}; 722303231Sdim 723303231Sdimstruct CovMapFunctionRecord { 724303231Sdim#define COVMAP_FUNC_RECORD(Type, LLVMType, Name, Init) Type Name; 725303231Sdim#include "llvm/ProfileData/InstrProfData.inc" 726303231Sdim 727303231Sdim // Return the structural hash associated with the function. 728303231Sdim template <support::endianness Endian> uint64_t getFuncHash() const { 729303231Sdim return support::endian::byte_swap<uint64_t, Endian>(FuncHash); 730303231Sdim } 731321369Sdim 732303231Sdim // Return the coverage map data size for the funciton. 733303231Sdim template <support::endianness Endian> uint32_t getDataSize() const { 734303231Sdim return support::endian::byte_swap<uint32_t, Endian>(DataSize); 735303231Sdim } 736321369Sdim 737303231Sdim // Return function lookup key. The value is consider opaque. 738303231Sdim template <support::endianness Endian> uint64_t getFuncNameRef() const { 739303231Sdim return support::endian::byte_swap<uint64_t, Endian>(NameRef); 740303231Sdim } 741321369Sdim 742303231Sdim // Return the PGO name of the function */ 743303231Sdim template <support::endianness Endian> 744303231Sdim Error getFuncName(InstrProfSymtab &ProfileNames, StringRef &FuncName) const { 745303231Sdim uint64_t NameRef = getFuncNameRef<Endian>(); 746303231Sdim FuncName = ProfileNames.getFuncName(NameRef); 747303231Sdim return Error::success(); 748303231Sdim } 749303231Sdim}; 750303231Sdim 751303231Sdim// Per module coverage mapping data header, i.e. CoverageMapFileHeader 752303231Sdim// documented above. 753303231Sdimstruct CovMapHeader { 754303231Sdim#define COVMAP_HEADER(Type, LLVMType, Name, Init) Type Name; 755303231Sdim#include "llvm/ProfileData/InstrProfData.inc" 756303231Sdim template <support::endianness Endian> uint32_t getNRecords() const { 757303231Sdim return support::endian::byte_swap<uint32_t, Endian>(NRecords); 758303231Sdim } 759321369Sdim 760303231Sdim template <support::endianness Endian> uint32_t getFilenamesSize() const { 761303231Sdim return support::endian::byte_swap<uint32_t, Endian>(FilenamesSize); 762303231Sdim } 763321369Sdim 764303231Sdim template <support::endianness Endian> uint32_t getCoverageSize() const { 765303231Sdim return support::endian::byte_swap<uint32_t, Endian>(CoverageSize); 766303231Sdim } 767321369Sdim 768303231Sdim template <support::endianness Endian> uint32_t getVersion() const { 769303231Sdim return support::endian::byte_swap<uint32_t, Endian>(Version); 770303231Sdim } 771303231Sdim}; 772303231Sdim 773303231SdimLLVM_PACKED_END 774303231Sdim 775303231Sdimenum CovMapVersion { 776303231Sdim Version1 = 0, 777303231Sdim // Function's name reference from CovMapFuncRecord is changed from raw 778303231Sdim // name string pointer to MD5 to support name section compression. Name 779303231Sdim // section is also compressed. 780303231Sdim Version2 = 1, 781327952Sdim // A new interpretation of the columnEnd field is added in order to mark 782327952Sdim // regions as gap areas. 783327952Sdim Version3 = 2, 784327952Sdim // The current version is Version3 785303231Sdim CurrentVersion = INSTR_PROF_COVMAP_VERSION 786303231Sdim}; 787303231Sdim 788303231Sdimtemplate <int CovMapVersion, class IntPtrT> struct CovMapTraits { 789321369Sdim using CovMapFuncRecordType = CovMapFunctionRecord; 790321369Sdim using NameRefType = uint64_t; 791303231Sdim}; 792303231Sdim 793303231Sdimtemplate <class IntPtrT> struct CovMapTraits<CovMapVersion::Version1, IntPtrT> { 794321369Sdim using CovMapFuncRecordType = CovMapFunctionRecordV1<IntPtrT>; 795321369Sdim using NameRefType = IntPtrT; 796303231Sdim}; 797303231Sdim 798303231Sdim} // end namespace coverage 799303231Sdim 800327952Sdim/// Provide DenseMapInfo for CounterExpression 801303231Sdimtemplate<> struct DenseMapInfo<coverage::CounterExpression> { 802303231Sdim static inline coverage::CounterExpression getEmptyKey() { 803303231Sdim using namespace coverage; 804321369Sdim 805303231Sdim return CounterExpression(CounterExpression::ExprKind::Subtract, 806303231Sdim Counter::getCounter(~0U), 807303231Sdim Counter::getCounter(~0U)); 808303231Sdim } 809303231Sdim 810303231Sdim static inline coverage::CounterExpression getTombstoneKey() { 811303231Sdim using namespace coverage; 812321369Sdim 813303231Sdim return CounterExpression(CounterExpression::ExprKind::Add, 814303231Sdim Counter::getCounter(~0U), 815303231Sdim Counter::getCounter(~0U)); 816303231Sdim } 817303231Sdim 818303231Sdim static unsigned getHashValue(const coverage::CounterExpression &V) { 819303231Sdim return static_cast<unsigned>( 820303231Sdim hash_combine(V.Kind, V.LHS.getKind(), V.LHS.getCounterID(), 821303231Sdim V.RHS.getKind(), V.RHS.getCounterID())); 822303231Sdim } 823303231Sdim 824303231Sdim static bool isEqual(const coverage::CounterExpression &LHS, 825303231Sdim const coverage::CounterExpression &RHS) { 826303231Sdim return LHS.Kind == RHS.Kind && LHS.LHS == RHS.LHS && LHS.RHS == RHS.RHS; 827303231Sdim } 828303231Sdim}; 829303231Sdim 830303231Sdim} // end namespace llvm 831303231Sdim 832321369Sdim#endif // LLVM_PROFILEDATA_COVERAGE_COVERAGEMAPPING_H 833