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