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