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