[gcov] Fix wrong line hit counts when multiple blocks are on the same line

Summary:
The goal of this patch is to have the same behaviour than gcc-gcov.
Currently the hit counts for a line is the sum of the counts for each block on that line.
The idea is to detect the cycles in the graph of blocks in using the algorithm by Hawick & James.
The count for a cycle is the min of the counts for each edge in the cycle.
Once we've the count for each cycle, we can sum them and add the transition counts of those cycles.

Fix both https://bugs.llvm.org/show_bug.cgi?id=38065 and https://bugs.llvm.org/show_bug.cgi?id=38066

Reviewers: marco-c, davidxl

Reviewed By: marco-c

Subscribers: vsk, lebedev.ri, sylvestre.ledru, dblaikie, llvm-commits

Differential Revision: https://reviews.llvm.org/D49659

llvm-svn: 342657

1 files changed, 18 insertions, 2 deletions

diff --git a/llvm/include/llvm/ProfileData/GCOV.h b/llvm/include/llvm/ProfileData/GCOV.h
index 8500401e44a..a088f63a691 100644
--- a/llvm/include/llvm/ProfileData/GCOV.h
+++ b/llvm/include/llvm/ProfileData/GCOV.h
@@ -24,9 +24,11 @@
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/raw_ostream.h"
+#include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
+#include <limits>
 #include <memory>
 #include <string>
 #include <utility>
@@ -266,13 +268,14 @@ struct GCOVEdge {
   GCOVBlock &Src;
   GCOVBlock &Dst;
   uint64_t Count = 0;
+  uint64_t CyclesCount = 0;
 };
 
 /// GCOVFunction - Collects function information.
 class GCOVFunction {
 public:
-  using BlockIterator = pointee_iterator<SmallVectorImpl<
-      std::unique_ptr<GCOVBlock>>::const_iterator>;
+  using BlockIterator = pointee_iterator<
+      SmallVectorImpl<std::unique_ptr<GCOVBlock>>::const_iterator>;
 
   GCOVFunction(GCOVFile &P) : Parent(P) {}
 
@@ -322,6 +325,9 @@ class GCOVBlock {
 
 public:
   using EdgeIterator = SmallVectorImpl<GCOVEdge *>::const_iterator;
+  using BlockVector = SmallVector<const GCOVBlock *, 4>;
+  using BlockVectorLists = SmallVector<BlockVector, 4>;
+  using Edges = SmallVector<GCOVEdge *, 4>;
 
   GCOVBlock(GCOVFunction &P, uint32_t N) : Parent(P), Number(N) {}
   ~GCOVBlock();
@@ -365,6 +371,16 @@ public:
   void dump() const;
   void collectLineCounts(FileInfo &FI);
 
+  static uint64_t getCycleCount(const Edges &Path);
+  static void unblock(const GCOVBlock *U, BlockVector &Blocked,
+                      BlockVectorLists &BlockLists);
+  static bool lookForCircuit(const GCOVBlock *V, const GCOVBlock *Start,
+                             Edges &Path, BlockVector &Blocked,
+                             BlockVectorLists &BlockLists,
+                             const BlockVector &Blocks, uint64_t &Count);
+  static void getCyclesCount(const BlockVector &Blocks, uint64_t &Count);
+  static uint64_t getLineCount(const BlockVector &Blocks);
+
 private:
   GCOVFunction &Parent;
   uint32_t Number;