include/llvm/ProfileData/GCOV.h

   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
  35 namespace llvm {
  36
  37 class GCOVFunction;
  38 class GCOVBlock;
  39 class FileInfo;
  40
  41 namespace GCOV {
  42
  43 enum GCOVVersion { V402, V404, V704 };
  44
  45 /// A struct for passing gcov options between functions.
  46 struct 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.
  67 class GCOVBuffer {
  68 public:
  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
 238 private:
 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).
 245 class GCOVFile {
 246 public:
 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
 256 private:
 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.
 266 struct 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.
 276 class GCOVFunction {
 277 public:
 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
 301 private:
 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.
 313 class GCOVBlock {
 314   struct EdgeWeight {
 315     EdgeWeight(GCOVBlock *D) : Dst(D) {}
 316
 317     GCOVBlock *Dst;
 318     uint64_t Count = 0;
 319   };
 320
 321 public:
 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
 379 private:
 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
 389 class FileInfo {
 390 protected:
 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
 422 public:
 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
 443 protected:
 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