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