contrib/llvm/include/llvm/ProfileData/GCOV.h

   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 {
  48   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:
  68   GCOVBuffer(MemoryBuffer *B) : Buffer(B) {}
  69
  70   /// readGCNOFormat - Check GCNO signature is valid at the beginning of buffer.
  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.
  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.
  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.
 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.
 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.
 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.
 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.
 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.
 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.
 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
 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
 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
 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
 234   uint64_t getCursor() const { return Cursor; }
 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);
 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 {
 266   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
 280   GCOVFunction(GCOVFile &P) : Parent(P) {}
 281
 282   bool readGCNO(GCOVBuffer &Buffer, GCOV::GCOVVersion Version);
 283   bool readGCDA(GCOVBuffer &Buffer, GCOV::GCOVVersion Version);
 284   StringRef getName() const { return Name; }
 285   StringRef getFilename() const { return Filename; }
 286   size_t getNumBlocks() const { return Blocks.size(); }
 287   uint64_t getEntryCount() const;
 288   uint64_t getExitCount() const;
 289
 290   BlockIterator block_begin() const { return Blocks.begin(); }
 291   BlockIterator block_end() const { return Blocks.end(); }
 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 {
 314     EdgeWeight(GCOVBlock *D) : Dst(D) {}
 315
 316     GCOVBlock *Dst;
 317     uint64_t Count = 0;
 318   };
 319
 320   struct SortDstEdgesFunctor {
 321     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
 332   GCOVBlock(GCOVFunction &P, uint32_t N) : Parent(P), Number(N) {}
 333   ~GCOVBlock();
 334
 335   const GCOVFunction &getParent() const { return Parent; }
 336   void addLine(uint32_t N) { Lines.push_back(N); }
 337   uint32_t getLastLine() const { return Lines.back(); }
 338   void addCount(size_t DstEdgeNo, uint64_t N);
 339   uint64_t getCount() const { return Counter; }
 340
 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
 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
 354   size_t getNumSrcEdges() const { return SrcEdges.size(); }
 355   size_t getNumDstEdges() const { return DstEdges.size(); }
 356   void sortDstEdges();
 357
 358   EdgeIterator src_begin() const { return SrcEdges.begin(); }
 359   EdgeIterator src_end() const { return SrcEdges.end(); }
 360   iterator_range<EdgeIterator> srcs() const {
 361     return make_range(src_begin(), src_end());
 362   }
 363
 364   EdgeIterator dst_begin() const { return DstEdges.begin(); }
 365   EdgeIterator dst_end() const { return DstEdges.end(); }
 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 {
 415     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:
 428   FileInfo(const GCOV::Options &Options) : Options(Options) {}
 429
 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
 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
 443   void setRunCount(uint32_t Runs) { RunCount = Runs; }
 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