Index: include/llvm/ProfileData/GCOV.h =================================================================== --- include/llvm/ProfileData/GCOV.h +++ 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 #include #include #include +#include #include #include #include @@ -266,6 +268,7 @@ GCOVBlock &Src; GCOVBlock &Dst; uint64_t Count = 0; + uint64_t CyclesCount = 0; }; /// GCOVFunction - Collects function information. @@ -322,7 +325,10 @@ public: using EdgeIterator = SmallVectorImpl::const_iterator; - + using BlockVector = SmallVector; + using BlockVectorLists = SmallVector; + using Edges = SmallVector; + GCOVBlock(GCOVFunction &P, uint32_t N) : Parent(P), Number(N) {} ~GCOVBlock(); @@ -347,6 +353,8 @@ size_t getNumSrcEdges() const { return SrcEdges.size(); } size_t getNumDstEdges() const { return DstEdges.size(); } + bool hasSrcEdges() const { return !SrcEdges.empty(); } + bool hasDstEdges() const { return !DstEdges.empty(); } void sortDstEdges(); EdgeIterator src_begin() const { return SrcEdges.begin(); } @@ -365,6 +373,14 @@ void dump() const; void collectLineCounts(FileInfo &FI); + static uint64_t cycle(const Edges &Path); + static void unblock(const GCOVBlock *U, BlockVector &Blocked, BlockVectorLists &BlockLists); + static bool isBlocked(const GCOVBlock *V, const BlockVector &Blocked); + static bool isBlockOnSameLine(const GCOVBlock *V, const BlockVector &Blocks); + static bool circuit(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; Index: lib/ProfileData/GCOV.cpp =================================================================== --- lib/ProfileData/GCOV.cpp +++ lib/ProfileData/GCOV.cpp @@ -442,6 +442,136 @@ } #endif + +//===----------------------------------------------------------------------===// +// Cycles detection +// +// The algorithm in GCC is based on the algorihtm by Hawick & James: +// "Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs" +// http://complexity.massey.ac.nz/cstn/013/cstn-013.pdf + +/// Get the count for the detected cycle +uint64_t GCOVBlock::cycle(const Edges &Path) { + uint64_t CycleCount = std::numeric_limits::max(); + for (auto E : Path) { + CycleCount = std::min(E->CyclesCount, CycleCount); + } + for (auto E : Path) { + E->CyclesCount -= CycleCount; + } + return CycleCount; +} + +/// Unblock a vertex previously marked as blocked +void GCOVBlock::unblock(const GCOVBlock *U, BlockVector &Blocked, BlockVectorLists &BlockLists) { + auto it = std::find(Blocked.begin(), Blocked.end(), U); + if (it == Blocked.end()) { + return; + } + + const size_t index = it - Blocked.begin(); + Blocked.erase(it); + + const BlockVector ToUnblock(BlockLists[index]); + BlockLists.erase(BlockLists.begin() + index); + for (auto GB : ToUnblock) { + GCOVBlock::unblock(GB, Blocked, BlockLists); + } +} + +/// Check if a vertex is blocked +bool GCOVBlock::isBlocked(const GCOVBlock *V, const BlockVector &Blocked) { + return std::find(Blocked.begin(), Blocked.end(), V) != Blocked.end(); +} + +/// Check if a vertex is on the same line as the others +bool GCOVBlock::isBlockOnSameLine(const GCOVBlock *V, const BlockVector &Blocks) { + return std::find(Blocks.begin(), Blocks.end(), V) != Blocks.end(); +} + +/// Look for a circuit +bool GCOVBlock::circuit(const GCOVBlock *V, const GCOVBlock *Start, Edges &Path, BlockVector &Blocked, BlockVectorLists &BlockLists, const BlockVector &Blocks, uint64_t &Count) { + Blocked.push_back(V); + BlockLists.emplace_back(BlockVector()); + bool FoundCircuit = false; + + for (auto E : V->dsts()) { + const GCOVBlock *W = &E->Dst; + if (W < Start || !GCOVBlock::isBlockOnSameLine(W, Blocks)) { + continue; + } + + Path.push_back(E); + + if (W == Start) { + // We've a cycle + Count += GCOVBlock::cycle(Path); + FoundCircuit = true; + } else if (!GCOVBlock::isBlocked(W, Blocked) && + GCOVBlock::circuit(W, Start, Path, Blocked, BlockLists, Blocks, Count)) { + FoundCircuit = true; + } + + Path.pop_back(); + } + + if (FoundCircuit) { + GCOVBlock::unblock(V, Blocked, BlockLists); + } else { + for (auto E : V->dsts()) { + const GCOVBlock *W = &E->Dst; + if (W < Start || !GCOVBlock::isBlockOnSameLine(W, Blocks)) { + continue; + } + const size_t index = std::find(Blocked.begin(), Blocked.end(), W) - Blocked.begin(); + BlockVector &List = BlockLists[index]; + if (std::find(List.begin(), List.end(), V) == List.end()) { + List.push_back(V); + } + } + } + + return FoundCircuit; +} + +/// Get the count for the list of blocks which lie on the same line +void GCOVBlock::getCyclesCount(const BlockVector &Blocks, uint64_t &Count) { + for (auto Block : Blocks) { + Edges Path; + BlockVector Blocked; + BlockVectorLists BlockLists; + + GCOVBlock::circuit(Block, Block, Path, Blocked, BlockLists, Blocks, Count); + } +} + +/// Get the count for the list of blocks which lie on the same line +uint64_t GCOVBlock::getLineCount(const BlockVector &Blocks) { + uint64_t Count = 0; + + for (auto Block : Blocks) { + if (!Block->hasSrcEdges() && Block->Counter) { + // the block has no predecessor and a non-null counter + // (can be the case with entry block in functions) + Count += Block->Counter; + } else { + for (auto E : Block->srcs()) { + const GCOVBlock *W = &E->Src; + if (!GCOVBlock::isBlockOnSameLine(W, Blocks)) { + Count += E->Count; + } + } + } + for (auto E : Block->dsts()) { + E->CyclesCount = E->Count; + } + } + + GCOVBlock::getCyclesCount(Blocks, Count); + + return Count; +} + //===----------------------------------------------------------------------===// // FileInfo implementation. @@ -628,17 +758,7 @@ // Add up the block counts to form line counts. DenseMap LineExecs; - uint64_t LineCount = 0; for (const GCOVBlock *Block : Blocks) { - if (Options.AllBlocks) { - // Only take the highest block count for that line. - uint64_t BlockCount = Block->getCount(); - LineCount = LineCount > BlockCount ? LineCount : BlockCount; - } else { - // Sum up all of the block counts. - LineCount += Block->getCount(); - } - if (Options.FuncCoverage) { // This is a slightly convoluted way to most accurately gather line // statistics for functions. Basically what is happening is that we @@ -673,7 +793,8 @@ } } } - + + const uint64_t LineCount = GCOVBlock::getLineCount(Blocks); if (LineCount == 0) CovOS << " #####:"; else { Index: test/tools/llvm-cov/Inputs/test_-a.h.gcov =================================================================== --- test/tools/llvm-cov/Inputs/test_-a.h.gcov +++ test/tools/llvm-cov/Inputs/test_-a.h.gcov @@ -3,7 +3,7 @@ -: 0:Data:test.gcda -: 0:Runs:2 -: 0:Programs:1 - 2: 1:struct A { + 4: 1:struct A { 2: 1-block 0 2: 1-block 1 -: 2: virtual void B(); Index: test/tools/llvm-cov/Inputs/test_-a.cpp.gcov =================================================================== --- test/tools/llvm-cov/Inputs/test_-a.cpp.gcov +++ test/tools/llvm-cov/Inputs/test_-a.cpp.gcov @@ -49,7 +49,7 @@ 4: 34-block 0 12: 34-block 1 8: 34-block 2 - 8: 35: assign(ii, jj); + 12: 35: assign(ii, jj); 8: 35-block 0 4: 35-block 1 2: 36:} Index: test/tools/llvm-cov/Inputs/test_-a_-b.h.gcov =================================================================== --- test/tools/llvm-cov/Inputs/test_-a_-b.h.gcov +++ test/tools/llvm-cov/Inputs/test_-a_-b.h.gcov @@ -5,7 +5,7 @@ -: 0:Programs:1 function _ZN1AC1Ev called 2 returned 100% blocks executed 100% function _ZN1AC2Ev called 2 returned 100% blocks executed 100% - 2: 1:struct A { + 4: 1:struct A { 2: 1-block 0 2: 1-block 1 -: 2: virtual void B(); Index: test/tools/llvm-cov/Inputs/test_-a_-b.cpp.gcov =================================================================== --- test/tools/llvm-cov/Inputs/test_-a_-b.cpp.gcov +++ test/tools/llvm-cov/Inputs/test_-a_-b.cpp.gcov @@ -60,7 +60,7 @@ branch 0 taken 67% branch 1 taken 33% 8: 34-block 2 - 8: 35: assign(ii, jj); + 12: 35: assign(ii, jj); 8: 35-block 0 4: 35-block 1 2: 36:} Index: test/tools/llvm-cov/Inputs/test_-a_-b_-c_-u.h.gcov =================================================================== --- test/tools/llvm-cov/Inputs/test_-a_-b_-c_-u.h.gcov +++ test/tools/llvm-cov/Inputs/test_-a_-b_-c_-u.h.gcov @@ -5,7 +5,7 @@ -: 0:Programs:1 function _ZN1AC1Ev called 2 returned 100% blocks executed 100% function _ZN1AC2Ev called 2 returned 100% blocks executed 100% - 2: 1:struct A { + 4: 1:struct A { 2: 1-block 0 unconditional 0 taken 2 2: 1-block 1 Index: test/tools/llvm-cov/Inputs/test_-a_-b_-c_-u.cpp.gcov =================================================================== --- test/tools/llvm-cov/Inputs/test_-a_-b_-c_-u.cpp.gcov +++ test/tools/llvm-cov/Inputs/test_-a_-b_-c_-u.cpp.gcov @@ -70,7 +70,7 @@ branch 2 taken 4 8: 34-block 2 unconditional 3 taken 8 - 8: 35: assign(ii, jj); + 12: 35: assign(ii, jj); 8: 35-block 0 unconditional 0 taken 8 4: 35-block 1 Index: test/tools/llvm-cov/Inputs/test_-a_-b_-u.h.gcov =================================================================== --- test/tools/llvm-cov/Inputs/test_-a_-b_-u.h.gcov +++ test/tools/llvm-cov/Inputs/test_-a_-b_-u.h.gcov @@ -5,7 +5,7 @@ -: 0:Programs:1 function _ZN1AC1Ev called 2 returned 100% blocks executed 100% function _ZN1AC2Ev called 2 returned 100% blocks executed 100% - 2: 1:struct A { + 4: 1:struct A { 2: 1-block 0 unconditional 0 taken 100% 2: 1-block 1 Index: test/tools/llvm-cov/Inputs/test_-a_-b_-u.cpp.gcov =================================================================== --- test/tools/llvm-cov/Inputs/test_-a_-b_-u.cpp.gcov +++ test/tools/llvm-cov/Inputs/test_-a_-b_-u.cpp.gcov @@ -70,7 +70,7 @@ branch 2 taken 33% 8: 34-block 2 unconditional 3 taken 100% - 8: 35: assign(ii, jj); + 12: 35: assign(ii, jj); 8: 35-block 0 unconditional 0 taken 100% 4: 35-block 1 Index: test/tools/llvm-cov/Inputs/test_missing.cpp.gcov =================================================================== --- test/tools/llvm-cov/Inputs/test_missing.cpp.gcov +++ test/tools/llvm-cov/Inputs/test_missing.cpp.gcov @@ -35,8 +35,8 @@ 12: 30:/*EOF*/ -: 31:/*EOF*/ -: 32:/*EOF*/ - 21: 33:/*EOF*/ - 36: 34:/*EOF*/ + 9: 33:/*EOF*/ + 18: 34:/*EOF*/ 18: 35:/*EOF*/ 3: 36:/*EOF*/ -: 37:/*EOF*/ @@ -53,7 +53,7 @@ #####: 48:/*EOF*/ -: 49:/*EOF*/ -: 50:/*EOF*/ - 66: 51:/*EOF*/ + 33: 51:/*EOF*/ 30: 52:/*EOF*/ -: 53:/*EOF*/ 6: 54:/*EOF*/ @@ -71,7 +71,7 @@ 30: 66:/*EOF*/ -: 67:/*EOF*/ 3: 68:/*EOF*/ -25769803782: 69:/*EOF*/ +12884901891: 69:/*EOF*/ 12884901888: 70:/*EOF*/ -: 71:/*EOF*/ 3: 72:/*EOF*/ Index: test/tools/llvm-cov/Inputs/test_no_options.cpp.gcov =================================================================== --- test/tools/llvm-cov/Inputs/test_no_options.cpp.gcov +++ test/tools/llvm-cov/Inputs/test_no_options.cpp.gcov @@ -35,8 +35,8 @@ 8: 30:} -: 31: -: 32:void initialize_grid() { - 12: 33: for (int ii = 0; ii < 2; ii++) - 24: 34: for (int jj = 0; jj < 2; jj++) + 6: 33: for (int ii = 0; ii < 2; ii++) + 12: 34: for (int jj = 0; jj < 2; jj++) 12: 35: assign(ii, jj); 2: 36:} -: 37: @@ -53,7 +53,7 @@ #####: 48: a += rand(); -: 49: } -: 50: - 44: 51: for (int ii = 0; ii < 10; ++ii) { + 22: 51: for (int ii = 0; ii < 10; ++ii) { 20: 52: switch (rand() % 5) { -: 53: case 0: 4: 54: a += rand(); @@ -71,7 +71,7 @@ 20: 66: } -: 67: 2: 68: A thing; -17179869188: 69: for (uint64_t ii = 0; ii < 4294967296; ++ii) +8589934594: 69: for (uint64_t ii = 0; ii < 4294967296; ++ii) 8589934592: 70: thing.B(); -: 71: 2: 72: return a + 8 + grid[2][3] + len; Index: test/tools/llvm-cov/Inputs/test_objdir.cpp.gcov =================================================================== --- test/tools/llvm-cov/Inputs/test_objdir.cpp.gcov +++ test/tools/llvm-cov/Inputs/test_objdir.cpp.gcov @@ -35,8 +35,8 @@ 8: 30:} -: 31: -: 32:void initialize_grid() { - 12: 33: for (int ii = 0; ii < 2; ii++) - 24: 34: for (int jj = 0; jj < 2; jj++) + 6: 33: for (int ii = 0; ii < 2; ii++) + 12: 34: for (int jj = 0; jj < 2; jj++) 12: 35: assign(ii, jj); 2: 36:} -: 37: @@ -53,7 +53,7 @@ #####: 48: a += rand(); -: 49: } -: 50: - 44: 51: for (int ii = 0; ii < 10; ++ii) { + 22: 51: for (int ii = 0; ii < 10; ++ii) { 20: 52: switch (rand() % 5) { -: 53: case 0: 4: 54: a += rand(); @@ -71,7 +71,7 @@ 20: 66: } -: 67: 2: 68: A thing; -17179869188: 69: for (uint64_t ii = 0; ii < 4294967296; ++ii) +8589934594: 69: for (uint64_t ii = 0; ii < 4294967296; ++ii) 8589934592: 70: thing.B(); -: 71: 2: 72: return a + 8 + grid[2][3] + len; Index: test/tools/llvm-cov/Inputs/test_paths.cpp.gcov =================================================================== --- test/tools/llvm-cov/Inputs/test_paths.cpp.gcov +++ test/tools/llvm-cov/Inputs/test_paths.cpp.gcov @@ -35,8 +35,8 @@ 12: 30:} -: 31: -: 32:void initialize_grid() { - 21: 33: for (int ii = 0; ii < 2; ii++) - 36: 34: for (int jj = 0; jj < 2; jj++) + 9: 33: for (int ii = 0; ii < 2; ii++) + 18: 34: for (int jj = 0; jj < 2; jj++) 18: 35: assign(ii, jj); 3: 36:} -: 37: @@ -53,7 +53,7 @@ #####: 48: a += rand(); -: 49: } -: 50: - 66: 51: for (int ii = 0; ii < 10; ++ii) { + 33: 51: for (int ii = 0; ii < 10; ++ii) { 30: 52: switch (rand() % 5) { -: 53: case 0: 6: 54: a += rand(); @@ -71,7 +71,7 @@ 30: 66: } -: 67: 3: 68: A thing; -25769803782: 69: for (uint64_t ii = 0; ii < 4294967296; ++ii) +12884901891: 69: for (uint64_t ii = 0; ii < 4294967296; ++ii) 12884901888: 70: thing.B(); -: 71: 3: 72: return a + 8 + grid[2][3] + len; Index: test/tools/llvm-cov/range_based_for.cpp =================================================================== --- test/tools/llvm-cov/range_based_for.cpp +++ test/tools/llvm-cov/range_based_for.cpp @@ -20,7 +20,7 @@ int main(int argc, const char *argv[]) { // GCOV: 1: [[@LINE]]:int main( int V[] = {1, 2}; // GCOV: 1: [[@LINE]]: int V[] - for (int &I : V) { // GCOV: 10: [[@LINE]]: for ( + for (int &I : V) { // GCOV: 5: [[@LINE]]: for ( } // GCOV: 2: [[@LINE]]: } return 0; // GCOV: 1: [[@LINE]]: return } // GCOV: -: [[@LINE]]:}