diff options
Diffstat (limited to 'llvm')
15 files changed, 174 insertions, 48 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; diff --git a/llvm/lib/ProfileData/GCOV.cpp b/llvm/lib/ProfileData/GCOV.cpp index c9155439ec4..5d9a5ca9895 100644 --- a/llvm/lib/ProfileData/GCOV.cpp +++ b/llvm/lib/ProfileData/GCOV.cpp @@ -111,9 +111,7 @@ void GCOVFile::print(raw_ostream &OS) const { #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) /// dump - Dump GCOVFile content to dbgs() for debugging purposes. -LLVM_DUMP_METHOD void GCOVFile::dump() const { - print(dbgs()); -} +LLVM_DUMP_METHOD void GCOVFile::dump() const { print(dbgs()); } #endif /// collectLineCounts - Collect line counts. This must be used after @@ -359,9 +357,7 @@ void GCOVFunction::print(raw_ostream &OS) const { #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) /// dump - Dump GCOVFunction content to dbgs() for debugging purposes. -LLVM_DUMP_METHOD void GCOVFunction::dump() const { - print(dbgs()); -} +LLVM_DUMP_METHOD void GCOVFunction::dump() const { print(dbgs()); } #endif /// collectLineCounts - Collect line counts. This must be used after @@ -437,12 +433,135 @@ void GCOVBlock::print(raw_ostream &OS) const { #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) /// dump - Dump GCOVBlock content to dbgs() for debugging purposes. -LLVM_DUMP_METHOD void GCOVBlock::dump() const { - print(dbgs()); -} +LLVM_DUMP_METHOD void GCOVBlock::dump() const { print(dbgs()); } #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::getCycleCount(const Edges &Path) { + uint64_t CycleCount = std::numeric_limits<uint64_t>::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 = find(Blocked, 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); + } +} + +bool GCOVBlock::lookForCircuit(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 || find(Blocks, W) == Blocks.end()) { + continue; + } + + Path.push_back(E); + + if (W == Start) { + // We've a cycle. + Count += GCOVBlock::getCycleCount(Path); + FoundCircuit = true; + } else if (find(Blocked, W) == Blocked.end() && // W is not blocked. + GCOVBlock::lookForCircuit(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 || find(Blocks, W) == Blocks.end()) { + continue; + } + const size_t index = find(Blocked, W) - Blocked.begin(); + BlockVector &List = BlockLists[index]; + if (find(List, 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::lookForCircuit(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->getNumSrcEdges() == 0) { + // The block has no predecessors and a non-null counter + // (can be the case with entry block in functions). + Count += Block->getCount(); + } else { + // Add counts from predecessors that are not on the same line. + for (auto E : Block->srcs()) { + const GCOVBlock *W = &E->Src; + if (find(Blocks, W) == Blocks.end()) { + Count += E->Count; + } + } + } + for (auto E : Block->dsts()) { + E->CyclesCount = E->Count; + } + } + + GCOVBlock::getCyclesCount(Blocks, Count); + + return Count; +} + +//===----------------------------------------------------------------------===// // FileInfo implementation. // Safe integer division, returns 0 if numerator is 0. @@ -578,8 +697,8 @@ FileInfo::openCoveragePath(StringRef CoveragePath) { return llvm::make_unique<raw_null_ostream>(); std::error_code EC; - auto OS = llvm::make_unique<raw_fd_ostream>(CoveragePath, EC, - sys::fs::F_Text); + auto OS = + llvm::make_unique<raw_fd_ostream>(CoveragePath, EC, sys::fs::F_Text); if (EC) { errs() << EC.message() << "\n"; return llvm::make_unique<raw_null_ostream>(); @@ -628,17 +747,7 @@ void FileInfo::print(raw_ostream &InfoOS, StringRef MainFilename, // Add up the block counts to form line counts. DenseMap<const GCOVFunction *, bool> 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 @@ -674,6 +783,7 @@ void FileInfo::print(raw_ostream &InfoOS, StringRef MainFilename, } } + const uint64_t LineCount = GCOVBlock::getLineCount(Blocks); if (LineCount == 0) CovOS << " #####:"; else { diff --git a/llvm/test/tools/llvm-cov/Inputs/test_-a.cpp.gcov b/llvm/test/tools/llvm-cov/Inputs/test_-a.cpp.gcov index c2210d5eca1..78ebbfc1a91 100644 --- a/llvm/test/tools/llvm-cov/Inputs/test_-a.cpp.gcov +++ b/llvm/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:} diff --git a/llvm/test/tools/llvm-cov/Inputs/test_-a.h.gcov b/llvm/test/tools/llvm-cov/Inputs/test_-a.h.gcov index a5fe62b1cec..84fcb529d45 100644 --- a/llvm/test/tools/llvm-cov/Inputs/test_-a.h.gcov +++ b/llvm/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(); diff --git a/llvm/test/tools/llvm-cov/Inputs/test_-a_-b.cpp.gcov b/llvm/test/tools/llvm-cov/Inputs/test_-a_-b.cpp.gcov index ae21037401f..b1e658e6d2b 100644 --- a/llvm/test/tools/llvm-cov/Inputs/test_-a_-b.cpp.gcov +++ b/llvm/test/tools/llvm-cov/Inputs/test_-a_-b.cpp.gcov @@ -60,7 +60,7 @@ branch 1 taken 33% 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:} diff --git a/llvm/test/tools/llvm-cov/Inputs/test_-a_-b.h.gcov b/llvm/test/tools/llvm-cov/Inputs/test_-a_-b.h.gcov index f3dabcb727c..d85b56239d1 100644 --- a/llvm/test/tools/llvm-cov/Inputs/test_-a_-b.h.gcov +++ b/llvm/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(); diff --git a/llvm/test/tools/llvm-cov/Inputs/test_-a_-b_-c_-u.cpp.gcov b/llvm/test/tools/llvm-cov/Inputs/test_-a_-b_-c_-u.cpp.gcov index cc5940f8b92..603d14e483b 100644 --- a/llvm/test/tools/llvm-cov/Inputs/test_-a_-b_-c_-u.cpp.gcov +++ b/llvm/test/tools/llvm-cov/Inputs/test_-a_-b_-c_-u.cpp.gcov @@ -70,7 +70,7 @@ branch 1 taken 8 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 diff --git a/llvm/test/tools/llvm-cov/Inputs/test_-a_-b_-c_-u.h.gcov b/llvm/test/tools/llvm-cov/Inputs/test_-a_-b_-c_-u.h.gcov index 840324e9f9f..e980e2101b2 100644 --- a/llvm/test/tools/llvm-cov/Inputs/test_-a_-b_-c_-u.h.gcov +++ b/llvm/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 diff --git a/llvm/test/tools/llvm-cov/Inputs/test_-a_-b_-u.cpp.gcov b/llvm/test/tools/llvm-cov/Inputs/test_-a_-b_-u.cpp.gcov index 0d2c6b39356..f9f5f307a46 100644 --- a/llvm/test/tools/llvm-cov/Inputs/test_-a_-b_-u.cpp.gcov +++ b/llvm/test/tools/llvm-cov/Inputs/test_-a_-b_-u.cpp.gcov @@ -70,7 +70,7 @@ branch 1 taken 67% 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 diff --git a/llvm/test/tools/llvm-cov/Inputs/test_-a_-b_-u.h.gcov b/llvm/test/tools/llvm-cov/Inputs/test_-a_-b_-u.h.gcov index e7fa658b290..923ac8ab64b 100644 --- a/llvm/test/tools/llvm-cov/Inputs/test_-a_-b_-u.h.gcov +++ b/llvm/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 diff --git a/llvm/test/tools/llvm-cov/Inputs/test_missing.cpp.gcov b/llvm/test/tools/llvm-cov/Inputs/test_missing.cpp.gcov index 1c138e42581..9b3da2735a5 100644 --- a/llvm/test/tools/llvm-cov/Inputs/test_missing.cpp.gcov +++ b/llvm/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*/ diff --git a/llvm/test/tools/llvm-cov/Inputs/test_no_options.cpp.gcov b/llvm/test/tools/llvm-cov/Inputs/test_no_options.cpp.gcov index 871e3ba6445..8524c9a5213 100644 --- a/llvm/test/tools/llvm-cov/Inputs/test_no_options.cpp.gcov +++ b/llvm/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; diff --git a/llvm/test/tools/llvm-cov/Inputs/test_objdir.cpp.gcov b/llvm/test/tools/llvm-cov/Inputs/test_objdir.cpp.gcov index abf88567801..22c8a2ad950 100644 --- a/llvm/test/tools/llvm-cov/Inputs/test_objdir.cpp.gcov +++ b/llvm/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; diff --git a/llvm/test/tools/llvm-cov/Inputs/test_paths.cpp.gcov b/llvm/test/tools/llvm-cov/Inputs/test_paths.cpp.gcov index 3982ddf4e5f..9b89f51246c 100644 --- a/llvm/test/tools/llvm-cov/Inputs/test_paths.cpp.gcov +++ b/llvm/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; diff --git a/llvm/test/tools/llvm-cov/range_based_for.cpp b/llvm/test/tools/llvm-cov/range_based_for.cpp index 2934650627e..3331dff55df 100644 --- a/llvm/test/tools/llvm-cov/range_based_for.cpp +++ b/llvm/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]]:} |
