1//===- GCOV.h - LLVM coverage tool ------------------------------*- 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// This header provides the interface to read and write coverage files that
11// use 'gcov' format.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_SUPPORT_GCOV_H
16#define LLVM_SUPPORT_GCOV_H
17
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/MapVector.h"
20#include "llvm/ADT/SmallVector.h"
21#include "llvm/ADT/StringMap.h"
22#include "llvm/ADT/StringRef.h"
23#include "llvm/ADT/iterator.h"
24#include "llvm/ADT/iterator_range.h"
25#include "llvm/Support/MemoryBuffer.h"
26#include "llvm/Support/raw_ostream.h"
27#include <cassert>
28#include <cstddef>
29#include <cstdint>
30#include <memory>
31#include <string>
32#include <utility>
33
34namespace llvm {
35
36class GCOVFunction;
37class GCOVBlock;
38class FileInfo;
39
40namespace GCOV {
41
42enum GCOVVersion { V402, V404, V704 };
43
44/// \brief A struct for passing gcov options between functions.
45struct Options {
46  Options(bool A, bool B, bool C, bool F, bool P, bool U, bool L, bool N)
47      : AllBlocks(A), BranchInfo(B), BranchCount(C), FuncCoverage(F),
48        PreservePaths(P), UncondBranch(U), LongFileNames(L), NoOutput(N) {}
49
50  bool AllBlocks;
51  bool BranchInfo;
52  bool BranchCount;
53  bool FuncCoverage;
54  bool PreservePaths;
55  bool UncondBranch;
56  bool LongFileNames;
57  bool NoOutput;
58};
59
60} // end namespace GCOV
61
62/// GCOVBuffer - A wrapper around MemoryBuffer to provide GCOV specific
63/// read operations.
64class GCOVBuffer {
65public:
66  GCOVBuffer(MemoryBuffer *B) : Buffer(B) {}
67
68  /// readGCNOFormat - Check GCNO signature is valid at the beginning of buffer.
69  bool readGCNOFormat() {
70    StringRef File = Buffer->getBuffer().slice(0, 4);
71    if (File != "oncg") {
72      errs() << "Unexpected file type: " << File << ".\n";
73      return false;
74    }
75    Cursor = 4;
76    return true;
77  }
78
79  /// readGCDAFormat - Check GCDA signature is valid at the beginning of buffer.
80  bool readGCDAFormat() {
81    StringRef File = Buffer->getBuffer().slice(0, 4);
82    if (File != "adcg") {
83      errs() << "Unexpected file type: " << File << ".\n";
84      return false;
85    }
86    Cursor = 4;
87    return true;
88  }
89
90  /// readGCOVVersion - Read GCOV version.
91  bool readGCOVVersion(GCOV::GCOVVersion &Version) {
92    StringRef VersionStr = Buffer->getBuffer().slice(Cursor, Cursor + 4);
93    if (VersionStr == "*204") {
94      Cursor += 4;
95      Version = GCOV::V402;
96      return true;
97    }
98    if (VersionStr == "*404") {
99      Cursor += 4;
100      Version = GCOV::V404;
101      return true;
102    }
103    if (VersionStr == "*704") {
104      Cursor += 4;
105      Version = GCOV::V704;
106      return true;
107    }
108    errs() << "Unexpected version: " << VersionStr << ".\n";
109    return false;
110  }
111
112  /// readFunctionTag - If cursor points to a function tag then increment the
113  /// cursor and return true otherwise return false.
114  bool readFunctionTag() {
115    StringRef Tag = Buffer->getBuffer().slice(Cursor, Cursor + 4);
116    if (Tag.empty() || Tag[0] != '\0' || Tag[1] != '\0' || Tag[2] != '\0' ||
117        Tag[3] != '\1') {
118      return false;
119    }
120    Cursor += 4;
121    return true;
122  }
123
124  /// readBlockTag - If cursor points to a block tag then increment the
125  /// cursor and return true otherwise return false.
126  bool readBlockTag() {
127    StringRef Tag = Buffer->getBuffer().slice(Cursor, Cursor + 4);
128    if (Tag.empty() || Tag[0] != '\0' || Tag[1] != '\0' || Tag[2] != '\x41' ||
129        Tag[3] != '\x01') {
130      return false;
131    }
132    Cursor += 4;
133    return true;
134  }
135
136  /// readEdgeTag - If cursor points to an edge tag then increment the
137  /// cursor and return true otherwise return false.
138  bool readEdgeTag() {
139    StringRef Tag = Buffer->getBuffer().slice(Cursor, Cursor + 4);
140    if (Tag.empty() || Tag[0] != '\0' || Tag[1] != '\0' || Tag[2] != '\x43' ||
141        Tag[3] != '\x01') {
142      return false;
143    }
144    Cursor += 4;
145    return true;
146  }
147
148  /// readLineTag - If cursor points to a line tag then increment the
149  /// cursor and return true otherwise return false.
150  bool readLineTag() {
151    StringRef Tag = Buffer->getBuffer().slice(Cursor, Cursor + 4);
152    if (Tag.empty() || Tag[0] != '\0' || Tag[1] != '\0' || Tag[2] != '\x45' ||
153        Tag[3] != '\x01') {
154      return false;
155    }
156    Cursor += 4;
157    return true;
158  }
159
160  /// readArcTag - If cursor points to an gcda arc tag then increment the
161  /// cursor and return true otherwise return false.
162  bool readArcTag() {
163    StringRef Tag = Buffer->getBuffer().slice(Cursor, Cursor + 4);
164    if (Tag.empty() || Tag[0] != '\0' || Tag[1] != '\0' || Tag[2] != '\xa1' ||
165        Tag[3] != '\1') {
166      return false;
167    }
168    Cursor += 4;
169    return true;
170  }
171
172  /// readObjectTag - If cursor points to an object summary tag then increment
173  /// the cursor and return true otherwise return false.
174  bool readObjectTag() {
175    StringRef Tag = Buffer->getBuffer().slice(Cursor, Cursor + 4);
176    if (Tag.empty() || Tag[0] != '\0' || Tag[1] != '\0' || Tag[2] != '\0' ||
177        Tag[3] != '\xa1') {
178      return false;
179    }
180    Cursor += 4;
181    return true;
182  }
183
184  /// readProgramTag - If cursor points to a program summary tag then increment
185  /// the cursor and return true otherwise return false.
186  bool readProgramTag() {
187    StringRef Tag = Buffer->getBuffer().slice(Cursor, Cursor + 4);
188    if (Tag.empty() || Tag[0] != '\0' || Tag[1] != '\0' || Tag[2] != '\0' ||
189        Tag[3] != '\xa3') {
190      return false;
191    }
192    Cursor += 4;
193    return true;
194  }
195
196  bool readInt(uint32_t &Val) {
197    if (Buffer->getBuffer().size() < Cursor + 4) {
198      errs() << "Unexpected end of memory buffer: " << Cursor + 4 << ".\n";
199      return false;
200    }
201    StringRef Str = Buffer->getBuffer().slice(Cursor, Cursor + 4);
202    Cursor += 4;
203    Val = *(const uint32_t *)(Str.data());
204    return true;
205  }
206
207  bool readInt64(uint64_t &Val) {
208    uint32_t Lo, Hi;
209    if (!readInt(Lo) || !readInt(Hi))
210      return false;
211    Val = ((uint64_t)Hi << 32) | Lo;
212    return true;
213  }
214
215  bool readString(StringRef &Str) {
216    uint32_t Len = 0;
217    // Keep reading until we find a non-zero length. This emulates gcov's
218    // behaviour, which appears to do the same.
219    while (Len == 0)
220      if (!readInt(Len))
221        return false;
222    Len *= 4;
223    if (Buffer->getBuffer().size() < Cursor + Len) {
224      errs() << "Unexpected end of memory buffer: " << Cursor + Len << ".\n";
225      return false;
226    }
227    Str = Buffer->getBuffer().slice(Cursor, Cursor + Len).split('\0').first;
228    Cursor += Len;
229    return true;
230  }
231
232  uint64_t getCursor() const { return Cursor; }
233  void advanceCursor(uint32_t n) { Cursor += n * 4; }
234
235private:
236  MemoryBuffer *Buffer;
237  uint64_t Cursor = 0;
238};
239
240/// GCOVFile - Collects coverage information for one pair of coverage file
241/// (.gcno and .gcda).
242class GCOVFile {
243public:
244  GCOVFile() = default;
245
246  bool readGCNO(GCOVBuffer &Buffer);
247  bool readGCDA(GCOVBuffer &Buffer);
248  uint32_t getChecksum() const { return Checksum; }
249  void print(raw_ostream &OS) const;
250  void dump() const;
251  void collectLineCounts(FileInfo &FI);
252
253private:
254  bool GCNOInitialized = false;
255  GCOV::GCOVVersion Version;
256  uint32_t Checksum = 0;
257  SmallVector<std::unique_ptr<GCOVFunction>, 16> Functions;
258  uint32_t RunCount = 0;
259  uint32_t ProgramCount = 0;
260};
261
262/// GCOVEdge - Collects edge information.
263struct GCOVEdge {
264  GCOVEdge(GCOVBlock &S, GCOVBlock &D) : Src(S), Dst(D) {}
265
266  GCOVBlock &Src;
267  GCOVBlock &Dst;
268  uint64_t Count = 0;
269};
270
271/// GCOVFunction - Collects function information.
272class GCOVFunction {
273public:
274  typedef pointee_iterator<SmallVectorImpl<
275      std::unique_ptr<GCOVBlock>>::const_iterator> BlockIterator;
276
277  GCOVFunction(GCOVFile &P) : Parent(P) {}
278
279  bool readGCNO(GCOVBuffer &Buffer, GCOV::GCOVVersion Version);
280  bool readGCDA(GCOVBuffer &Buffer, GCOV::GCOVVersion Version);
281  StringRef getName() const { return Name; }
282  StringRef getFilename() const { return Filename; }
283  size_t getNumBlocks() const { return Blocks.size(); }
284  uint64_t getEntryCount() const;
285  uint64_t getExitCount() const;
286
287  BlockIterator block_begin() const { return Blocks.begin(); }
288  BlockIterator block_end() const { return Blocks.end(); }
289  iterator_range<BlockIterator> blocks() const {
290    return make_range(block_begin(), block_end());
291  }
292
293  void print(raw_ostream &OS) const;
294  void dump() const;
295  void collectLineCounts(FileInfo &FI);
296
297private:
298  GCOVFile &Parent;
299  uint32_t Ident = 0;
300  uint32_t Checksum;
301  uint32_t LineNumber = 0;
302  StringRef Name;
303  StringRef Filename;
304  SmallVector<std::unique_ptr<GCOVBlock>, 16> Blocks;
305  SmallVector<std::unique_ptr<GCOVEdge>, 16> Edges;
306};
307
308/// GCOVBlock - Collects block information.
309class GCOVBlock {
310  struct EdgeWeight {
311    EdgeWeight(GCOVBlock *D) : Dst(D) {}
312
313    GCOVBlock *Dst;
314    uint64_t Count = 0;
315  };
316
317  struct SortDstEdgesFunctor {
318    bool operator()(const GCOVEdge *E1, const GCOVEdge *E2) {
319      return E1->Dst.Number < E2->Dst.Number;
320    }
321  };
322
323public:
324  typedef SmallVectorImpl<GCOVEdge *>::const_iterator EdgeIterator;
325
326  GCOVBlock(GCOVFunction &P, uint32_t N) : Parent(P), Number(N) {}
327  ~GCOVBlock();
328
329  const GCOVFunction &getParent() const { return Parent; }
330  void addLine(uint32_t N) { Lines.push_back(N); }
331  uint32_t getLastLine() const { return Lines.back(); }
332  void addCount(size_t DstEdgeNo, uint64_t N);
333  uint64_t getCount() const { return Counter; }
334
335  void addSrcEdge(GCOVEdge *Edge) {
336    assert(&Edge->Dst == this); // up to caller to ensure edge is valid
337    SrcEdges.push_back(Edge);
338  }
339
340  void addDstEdge(GCOVEdge *Edge) {
341    assert(&Edge->Src == this); // up to caller to ensure edge is valid
342    // Check if adding this edge causes list to become unsorted.
343    if (DstEdges.size() && DstEdges.back()->Dst.Number > Edge->Dst.Number)
344      DstEdgesAreSorted = false;
345    DstEdges.push_back(Edge);
346  }
347
348  size_t getNumSrcEdges() const { return SrcEdges.size(); }
349  size_t getNumDstEdges() const { return DstEdges.size(); }
350  void sortDstEdges();
351
352  EdgeIterator src_begin() const { return SrcEdges.begin(); }
353  EdgeIterator src_end() const { return SrcEdges.end(); }
354  iterator_range<EdgeIterator> srcs() const {
355    return make_range(src_begin(), src_end());
356  }
357
358  EdgeIterator dst_begin() const { return DstEdges.begin(); }
359  EdgeIterator dst_end() const { return DstEdges.end(); }
360  iterator_range<EdgeIterator> dsts() const {
361    return make_range(dst_begin(), dst_end());
362  }
363
364  void print(raw_ostream &OS) const;
365  void dump() const;
366  void collectLineCounts(FileInfo &FI);
367
368private:
369  GCOVFunction &Parent;
370  uint32_t Number;
371  uint64_t Counter = 0;
372  bool DstEdgesAreSorted = true;
373  SmallVector<GCOVEdge *, 16> SrcEdges;
374  SmallVector<GCOVEdge *, 16> DstEdges;
375  SmallVector<uint32_t, 16> Lines;
376};
377
378class FileInfo {
379  // It is unlikely--but possible--for multiple functions to be on the same
380  // line.
381  // Therefore this typedef allows LineData.Functions to store multiple
382  // functions
383  // per instance. This is rare, however, so optimize for the common case.
384  typedef SmallVector<const GCOVFunction *, 1> FunctionVector;
385  typedef DenseMap<uint32_t, FunctionVector> FunctionLines;
386  typedef SmallVector<const GCOVBlock *, 4> BlockVector;
387  typedef DenseMap<uint32_t, BlockVector> BlockLines;
388
389  struct LineData {
390    LineData() = default;
391
392    BlockLines Blocks;
393    FunctionLines Functions;
394    uint32_t LastLine = 0;
395  };
396
397  struct GCOVCoverage {
398    GCOVCoverage(StringRef Name) : Name(Name) {}
399
400    StringRef Name;
401
402    uint32_t LogicalLines = 0;
403    uint32_t LinesExec = 0;
404
405    uint32_t Branches = 0;
406    uint32_t BranchesExec = 0;
407    uint32_t BranchesTaken = 0;
408  };
409
410public:
411  FileInfo(const GCOV::Options &Options) : Options(Options) {}
412
413  void addBlockLine(StringRef Filename, uint32_t Line, const GCOVBlock *Block) {
414    if (Line > LineInfo[Filename].LastLine)
415      LineInfo[Filename].LastLine = Line;
416    LineInfo[Filename].Blocks[Line - 1].push_back(Block);
417  }
418
419  void addFunctionLine(StringRef Filename, uint32_t Line,
420                       const GCOVFunction *Function) {
421    if (Line > LineInfo[Filename].LastLine)
422      LineInfo[Filename].LastLine = Line;
423    LineInfo[Filename].Functions[Line - 1].push_back(Function);
424  }
425
426  void setRunCount(uint32_t Runs) { RunCount = Runs; }
427  void setProgramCount(uint32_t Programs) { ProgramCount = Programs; }
428  void print(raw_ostream &OS, StringRef MainFilename, StringRef GCNOFile,
429             StringRef GCDAFile);
430
431private:
432  std::string getCoveragePath(StringRef Filename, StringRef MainFilename);
433  std::unique_ptr<raw_ostream> openCoveragePath(StringRef CoveragePath);
434  void printFunctionSummary(raw_ostream &OS, const FunctionVector &Funcs) const;
435  void printBlockInfo(raw_ostream &OS, const GCOVBlock &Block,
436                      uint32_t LineIndex, uint32_t &BlockNo) const;
437  void printBranchInfo(raw_ostream &OS, const GCOVBlock &Block,
438                       GCOVCoverage &Coverage, uint32_t &EdgeNo);
439  void printUncondBranchInfo(raw_ostream &OS, uint32_t &EdgeNo,
440                             uint64_t Count) const;
441
442  void printCoverage(raw_ostream &OS, const GCOVCoverage &Coverage) const;
443  void printFuncCoverage(raw_ostream &OS) const;
444  void printFileCoverage(raw_ostream &OS) const;
445
446  const GCOV::Options &Options;
447  StringMap<LineData> LineInfo;
448  uint32_t RunCount = 0;
449  uint32_t ProgramCount = 0;
450
451  typedef SmallVector<std::pair<std::string, GCOVCoverage>, 4> FileCoverageList;
452  typedef MapVector<const GCOVFunction *, GCOVCoverage> FuncCoverageMap;
453
454  FileCoverageList FileCoverages;
455  FuncCoverageMap FuncCoverages;
456};
457
458} // end namespace llvm
459
460#endif // LLVM_SUPPORT_GCOV_H
461