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