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/DenseSet.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/DataExtractor.h"
26 #include "llvm/Support/MemoryBuffer.h"
27 #include "llvm/Support/raw_ostream.h"
28 #include <algorithm>
29 #include <cassert>
30 #include <cstddef>
31 #include <cstdint>
32 #include <limits>
33 #include <map>
34 #include <memory>
35 #include <string>
36 #include <utility>
37 
38 namespace llvm {
39 
40 class GCOVFunction;
41 class GCOVBlock;
42 
43 namespace GCOV {
44 
45 enum GCOVVersion { V304, V407, V408, V800, V900, V1200 };
46 
47 /// A struct for passing gcov options between functions.
48 struct Options {
OptionsOptions49   Options(bool A, bool B, bool C, bool F, bool P, bool U, bool I, bool L,
50           bool M, bool N, bool R, bool T, bool X, std::string SourcePrefix)
51       : AllBlocks(A), BranchInfo(B), BranchCount(C), FuncCoverage(F),
52         PreservePaths(P), UncondBranch(U), Intermediate(I), LongFileNames(L),
53         Demangle(M), NoOutput(N), RelativeOnly(R), UseStdout(T),
54         HashFilenames(X), SourcePrefix(std::move(SourcePrefix)) {}
55 
56   bool AllBlocks;
57   bool BranchInfo;
58   bool BranchCount;
59   bool FuncCoverage;
60   bool PreservePaths;
61   bool UncondBranch;
62   bool Intermediate;
63   bool LongFileNames;
64   bool Demangle;
65   bool NoOutput;
66   bool RelativeOnly;
67   bool UseStdout;
68   bool HashFilenames;
69   std::string SourcePrefix;
70 };
71 
72 } // end namespace GCOV
73 
74 /// GCOVBuffer - A wrapper around MemoryBuffer to provide GCOV specific
75 /// read operations.
76 class GCOVBuffer {
77 public:
GCOVBuffer(MemoryBuffer * B)78   GCOVBuffer(MemoryBuffer *B) : Buffer(B) {}
~GCOVBuffer()79   ~GCOVBuffer() { consumeError(cursor.takeError()); }
80 
81   /// readGCNOFormat - Check GCNO signature is valid at the beginning of buffer.
readGCNOFormat()82   bool readGCNOFormat() {
83     StringRef buf = Buffer->getBuffer();
84     StringRef magic = buf.substr(0, 4);
85     if (magic == "gcno") {
86       de = DataExtractor(buf.substr(4), false, 0);
87     } else if (magic == "oncg") {
88       de = DataExtractor(buf.substr(4), true, 0);
89     } else {
90       errs() << "unexpected magic: " << magic << "\n";
91       return false;
92     }
93     return true;
94   }
95 
96   /// readGCDAFormat - Check GCDA signature is valid at the beginning of buffer.
readGCDAFormat()97   bool readGCDAFormat() {
98     StringRef buf = Buffer->getBuffer();
99     StringRef magic = buf.substr(0, 4);
100     if (magic == "gcda") {
101       de = DataExtractor(buf.substr(4), false, 0);
102     } else if (magic == "adcg") {
103       de = DataExtractor(buf.substr(4), true, 0);
104     } else {
105       return false;
106     }
107     return true;
108   }
109 
110   /// readGCOVVersion - Read GCOV version.
readGCOVVersion(GCOV::GCOVVersion & version)111   bool readGCOVVersion(GCOV::GCOVVersion &version) {
112     std::string str(de.getBytes(cursor, 4));
113     if (str.size() != 4)
114       return false;
115     if (de.isLittleEndian())
116       std::reverse(str.begin(), str.end());
117     int ver = str[0] >= 'A'
118                   ? (str[0] - 'A') * 100 + (str[1] - '0') * 10 + str[2] - '0'
119                   : (str[0] - '0') * 10 + str[2] - '0';
120     if (ver >= 120) {
121       this->version = version = GCOV::V1200;
122       return true;
123     } else if (ver >= 90) {
124       // PR gcov-profile/84846, r269678
125       this->version = version = GCOV::V900;
126       return true;
127     } else if (ver >= 80) {
128       // PR gcov-profile/48463
129       this->version = version = GCOV::V800;
130       return true;
131     } else if (ver >= 48) {
132       // r189778: the exit block moved from the last to the second.
133       this->version = version = GCOV::V408;
134       return true;
135     } else if (ver >= 47) {
136       // r173147: split checksum into cfg checksum and line checksum.
137       this->version = version = GCOV::V407;
138       return true;
139     } else if (ver >= 34) {
140       this->version = version = GCOV::V304;
141       return true;
142     }
143     errs() << "unexpected version: " << str << "\n";
144     return false;
145   }
146 
getWord()147   uint32_t getWord() { return de.getU32(cursor); }
getString()148   StringRef getString() {
149     uint32_t len;
150     if (!readInt(len) || len == 0)
151       return {};
152     return de.getBytes(cursor, len * 4).split('\0').first;
153   }
154 
readInt(uint32_t & Val)155   bool readInt(uint32_t &Val) {
156     if (cursor.tell() + 4 > de.size()) {
157       Val = 0;
158       errs() << "unexpected end of memory buffer: " << cursor.tell() << "\n";
159       return false;
160     }
161     Val = de.getU32(cursor);
162     return true;
163   }
164 
readInt64(uint64_t & Val)165   bool readInt64(uint64_t &Val) {
166     uint32_t Lo, Hi;
167     if (!readInt(Lo) || !readInt(Hi))
168       return false;
169     Val = ((uint64_t)Hi << 32) | Lo;
170     return true;
171   }
172 
readString(StringRef & str)173   bool readString(StringRef &str) {
174     uint32_t len;
175     if (!readInt(len) || len == 0)
176       return false;
177     if (version >= GCOV::V1200)
178       str = de.getBytes(cursor, len).drop_back();
179     else
180       str = de.getBytes(cursor, len * 4).split('\0').first;
181     return bool(cursor);
182   }
183 
184   DataExtractor de{ArrayRef<uint8_t>{}, false, 0};
185   DataExtractor::Cursor cursor{0};
186 
187 private:
188   MemoryBuffer *Buffer;
189   GCOV::GCOVVersion version{};
190 };
191 
192 /// GCOVFile - Collects coverage information for one pair of coverage file
193 /// (.gcno and .gcda).
194 class GCOVFile {
195 public:
196   GCOVFile() = default;
197 
198   bool readGCNO(GCOVBuffer &Buffer);
199   bool readGCDA(GCOVBuffer &Buffer);
getVersion()200   GCOV::GCOVVersion getVersion() const { return version; }
201   void print(raw_ostream &OS) const;
202   void dump() const;
203 
204   std::vector<std::string> filenames;
205   StringMap<unsigned> filenameToIdx;
206 
207 public:
208   bool GCNOInitialized = false;
209   GCOV::GCOVVersion version{};
210   uint32_t checksum = 0;
211   StringRef cwd;
212   SmallVector<std::unique_ptr<GCOVFunction>, 16> functions;
213   std::map<uint32_t, GCOVFunction *> identToFunction;
214   uint32_t runCount = 0;
215   uint32_t programCount = 0;
216 
217   using iterator = pointee_iterator<
218       SmallVectorImpl<std::unique_ptr<GCOVFunction>>::const_iterator>;
begin()219   iterator begin() const { return iterator(functions.begin()); }
end()220   iterator end() const { return iterator(functions.end()); }
221 };
222 
223 struct GCOVArc {
GCOVArcGCOVArc224   GCOVArc(GCOVBlock &src, GCOVBlock &dst, uint32_t flags)
225       : src(src), dst(dst), flags(flags) {}
226   bool onTree() const;
227 
228   GCOVBlock &src;
229   GCOVBlock &dst;
230   uint32_t flags;
231   uint64_t count = 0;
232   uint64_t cycleCount = 0;
233 };
234 
235 /// GCOVFunction - Collects function information.
236 class GCOVFunction {
237 public:
238   using BlockIterator = pointee_iterator<
239       SmallVectorImpl<std::unique_ptr<GCOVBlock>>::const_iterator>;
240 
GCOVFunction(GCOVFile & file)241   GCOVFunction(GCOVFile &file) : file(file) {}
242 
243   StringRef getName(bool demangle) const;
244   StringRef getFilename() const;
245   uint64_t getEntryCount() const;
246   GCOVBlock &getExitBlock() const;
247 
blocksRange()248   iterator_range<BlockIterator> blocksRange() const {
249     return make_range(blocks.begin(), blocks.end());
250   }
251 
252   uint64_t propagateCounts(const GCOVBlock &v, GCOVArc *pred);
253   void print(raw_ostream &OS) const;
254   void dump() const;
255 
256   GCOVFile &file;
257   uint32_t ident = 0;
258   uint32_t linenoChecksum;
259   uint32_t cfgChecksum = 0;
260   uint32_t startLine = 0;
261   uint32_t startColumn = 0;
262   uint32_t endLine = 0;
263   uint32_t endColumn = 0;
264   uint8_t artificial = 0;
265   StringRef Name;
266   mutable SmallString<0> demangled;
267   unsigned srcIdx;
268   SmallVector<std::unique_ptr<GCOVBlock>, 0> blocks;
269   SmallVector<std::unique_ptr<GCOVArc>, 0> arcs, treeArcs;
270   DenseSet<const GCOVBlock *> visited;
271 };
272 
273 /// GCOVBlock - Collects block information.
274 class GCOVBlock {
275 public:
276   using EdgeIterator = SmallVectorImpl<GCOVArc *>::const_iterator;
277   using BlockVector = SmallVector<const GCOVBlock *, 1>;
278   using BlockVectorLists = SmallVector<BlockVector, 4>;
279   using Edges = SmallVector<GCOVArc *, 4>;
280 
GCOVBlock(uint32_t N)281   GCOVBlock(uint32_t N) : number(N) {}
282 
addLine(uint32_t N)283   void addLine(uint32_t N) { lines.push_back(N); }
getLastLine()284   uint32_t getLastLine() const { return lines.back(); }
getCount()285   uint64_t getCount() const { return count; }
286 
addSrcEdge(GCOVArc * Edge)287   void addSrcEdge(GCOVArc *Edge) { pred.push_back(Edge); }
288 
addDstEdge(GCOVArc * Edge)289   void addDstEdge(GCOVArc *Edge) { succ.push_back(Edge); }
290 
srcs()291   iterator_range<EdgeIterator> srcs() const {
292     return make_range(pred.begin(), pred.end());
293   }
294 
dsts()295   iterator_range<EdgeIterator> dsts() const {
296     return make_range(succ.begin(), succ.end());
297   }
298 
299   void print(raw_ostream &OS) const;
300   void dump() const;
301 
302   static uint64_t
303   augmentOneCycle(GCOVBlock *src,
304                   std::vector<std::pair<GCOVBlock *, size_t>> &stack);
305   static uint64_t getCyclesCount(const BlockVector &blocks);
306   static uint64_t getLineCount(const BlockVector &Blocks);
307 
308 public:
309   uint32_t number;
310   uint64_t count = 0;
311   SmallVector<GCOVArc *, 2> pred;
312   SmallVector<GCOVArc *, 2> succ;
313   SmallVector<uint32_t, 4> lines;
314   bool traversable = false;
315   GCOVArc *incoming = nullptr;
316 };
317 
318 void gcovOneInput(const GCOV::Options &options, StringRef filename,
319                   StringRef gcno, StringRef gcda, GCOVFile &file);
320 
321 } // end namespace llvm
322 
323 #endif // LLVM_PROFILEDATA_GCOV_H
324