From a2639798a8546537dc7cdd3bf21e4c179243e941 Mon Sep 17 00:00:00 2001 From: Yuchen Wu Date: Fri, 13 Dec 2013 01:15:07 +0000 Subject: llvm-cov: Added -b option for branch probabilities. This option tells llvm-cov to print out branch probabilities when a basic block contains multiple branches. It also prints out some function summary info including the number of times the function enters, the percent of time it returns, and how many blocks were executed. Also updated tests. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@197198 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/GCOV.h | 77 ++++++++++-- lib/IR/GCOV.cpp | 157 +++++++++++++++++++++---- test/tools/llvm-cov/Inputs/test_-a_-b.cpp.gcov | 134 +++++++++++++++++++++ test/tools/llvm-cov/Inputs/test_-a_-b.h.gcov | 12 ++ test/tools/llvm-cov/llvm-cov.test | 4 + tools/llvm-cov/llvm-cov.cpp | 8 +- 6 files changed, 355 insertions(+), 37 deletions(-) create mode 100644 test/tools/llvm-cov/Inputs/test_-a_-b.cpp.gcov create mode 100644 test/tools/llvm-cov/Inputs/test_-a_-b.h.gcov diff --git a/include/llvm/Support/GCOV.h b/include/llvm/Support/GCOV.h index 852c0bef45..9b3d4962a4 100644 --- a/include/llvm/Support/GCOV.h +++ b/include/llvm/Support/GCOV.h @@ -36,9 +36,9 @@ namespace GCOV { /// GCOVOptions - A struct for passing gcov options between functions. struct GCOVOptions { - GCOVOptions(bool A): AllBlocks(A) {} - + GCOVOptions(bool A, bool B): AllBlocks(A), BranchProb(B) {} bool AllBlocks; + bool BranchProb; }; /// GCOVBuffer - A wrapper around MemoryBuffer to provide GCOV specific @@ -236,6 +236,7 @@ private: uint32_t ProgramCount; }; +/// GCOVEdge - Collects edge information. struct GCOVEdge { GCOVEdge(GCOVBlock *S, GCOVBlock *D): Src(S), Dst(D), Count(0) {} @@ -247,12 +248,21 @@ struct GCOVEdge { /// GCOVFunction - Collects function information. class GCOVFunction { public: + typedef SmallVectorImpl::const_iterator BlockIterator; + GCOVFunction(GCOVFile &P) : Parent(P), Ident(0), LineNumber(0) {} ~GCOVFunction(); bool readGCNO(GCOVBuffer &Buffer, GCOV::GCOVVersion Version); bool readGCDA(GCOVBuffer &Buffer, GCOV::GCOVVersion Version); + StringRef getName() const { return Name; } StringRef getFilename() const { return Filename; } size_t getNumBlocks() const { return Blocks.size(); } + uint64_t getEntryCount() const; + uint64_t getExitCount() const; + + BlockIterator block_begin() const { return Blocks.begin(); } + BlockIterator block_end() const { return Blocks.end(); } + void dump() const; void collectLineCounts(FileInfo &FI); private: @@ -268,26 +278,43 @@ private: /// GCOVBlock - Collects block information. class GCOVBlock { + struct EdgeWeight { + EdgeWeight(GCOVBlock *D): Dst(D), Count(0) {} + + GCOVBlock *Dst; + uint64_t Count; + }; + + struct SortDstEdgesFunctor { + bool operator()(const GCOVEdge *E1, const GCOVEdge *E2) { + return E1->Dst->Number < E2->Dst->Number; + } + }; public: typedef SmallVectorImpl::const_iterator EdgeIterator; - GCOVBlock(GCOVFunction &P, uint32_t N) : - Parent(P), Number(N), Counter(0), SrcEdges(), DstEdges(), Lines() {} + GCOVBlock(GCOVFunction &P, uint32_t N) : Parent(P), Number(N), Counter(0), + DstEdgesAreSorted(true), SrcEdges(), DstEdges(), Lines() {} ~GCOVBlock(); + void addLine(uint32_t N) { Lines.push_back(N); } + uint32_t getLastLine() const { return Lines.back(); } + void addCount(size_t DstEdgeNo, uint64_t N); + uint64_t getCount() const { return Counter; } + void addSrcEdge(GCOVEdge *Edge) { assert(Edge->Dst == this); // up to caller to ensure edge is valid SrcEdges.push_back(Edge); } void addDstEdge(GCOVEdge *Edge) { assert(Edge->Src == this); // up to caller to ensure edge is valid + // Check if adding this edge causes list to become unsorted. + if (DstEdges.size() && DstEdges.back()->Dst->Number > Edge->Dst->Number) + DstEdgesAreSorted = false; DstEdges.push_back(Edge); } - void addLine(uint32_t N) { Lines.push_back(N); } - uint32_t getLastLine() const { return Lines.back(); } - void addCount(size_t DstEdgeNo, uint64_t N); - uint64_t getCount() const { return Counter; } size_t getNumSrcEdges() const { return SrcEdges.size(); } size_t getNumDstEdges() const { return DstEdges.size(); } + void sortDstEdges(); EdgeIterator src_begin() const { return SrcEdges.begin(); } EdgeIterator src_end() const { return SrcEdges.end(); } @@ -300,23 +327,47 @@ private: GCOVFunction &Parent; uint32_t Number; uint64_t Counter; + bool DstEdgesAreSorted; SmallVector SrcEdges; SmallVector DstEdges; SmallVector Lines; }; -typedef SmallVector BlockVector; -typedef DenseMap LineData; class FileInfo { + // It is unlikely--but possible--for multiple functions to be on the same line. + // Therefore this typedef allows LineData.Functions to store multiple functions + // per instance. This is rare, however, so optimize for the common case. + typedef SmallVector FunctionVector; + typedef DenseMap FunctionLines; + typedef SmallVector BlockVector; + typedef DenseMap BlockLines; + + struct LineData { + BlockLines Blocks; + FunctionLines Functions; + }; public: + FileInfo(const GCOVOptions &Options) : + Options(Options), LineInfo(), RunCount(0), ProgramCount(0) {} + void addBlockLine(StringRef Filename, uint32_t Line, const GCOVBlock *Block) { - LineInfo[Filename][Line-1].push_back(Block); + LineInfo[Filename].Blocks[Line-1].push_back(Block); + } + void addFunctionLine(StringRef Filename, uint32_t Line, + const GCOVFunction *Function) { + LineInfo[Filename].Functions[Line-1].push_back(Function); } void setRunCount(uint32_t Runs) { RunCount = Runs; } void setProgramCount(uint32_t Programs) { ProgramCount = Programs; } - void print(StringRef GCNOFile, StringRef GCDAFile, - const GCOVOptions &Options) const; + void print(StringRef GCNOFile, StringRef GCDAFile) const; + void printFunctionSummary(raw_fd_ostream &OS, + const FunctionVector &Funcs) const; + void printBlockInfo(raw_fd_ostream &OS, const GCOVBlock &Block, + uint32_t LineIndex, uint32_t &BlockNo) const; + void printBranchInfo(raw_fd_ostream &OS, const GCOVBlock &Block, + uint32_t LineIndex, uint32_t &EdgeNo) const; private: + const GCOVOptions &Options; StringMap LineInfo; uint32_t RunCount; uint32_t ProgramCount; diff --git a/lib/IR/GCOV.cpp b/lib/IR/GCOV.cpp index 5587cbfa08..73642c98f4 100644 --- a/lib/IR/GCOV.cpp +++ b/lib/IR/GCOV.cpp @@ -19,6 +19,7 @@ #include "llvm/Support/Format.h" #include "llvm/Support/MemoryObject.h" #include "llvm/Support/system_error.h" +#include using namespace llvm; //===----------------------------------------------------------------------===// @@ -278,10 +279,23 @@ bool GCOVFunction::readGCDA(GCOVBuffer &Buff, GCOV::GCOVVersion Version) { Block.addCount(EdgeNo, ArcCount); --Count; } + Block.sortDstEdges(); } return true; } +/// getEntryCount - Get the number of times the function was called by +/// retrieving the entry block's count. +uint64_t GCOVFunction::getEntryCount() const { + return Blocks.front()->getCount(); +} + +/// getExitCount - Get the number of times the function returned by retrieving +/// the exit block's count. +uint64_t GCOVFunction::getExitCount() const { + return Blocks.back()->getCount(); +} + /// dump - Dump GCOVFunction content to dbgs() for debugging purposes. void GCOVFunction::dump() const { dbgs() << "===== " << Name << " @ " << Filename << ":" << LineNumber << "\n"; @@ -296,6 +310,7 @@ void GCOVFunction::collectLineCounts(FileInfo &FI) { for (SmallVectorImpl::iterator I = Blocks.begin(), E = Blocks.end(); I != E; ++I) (*I)->collectLineCounts(FI); + FI.addFunctionLine(Filename, LineNumber, this); } //===----------------------------------------------------------------------===// @@ -318,6 +333,15 @@ void GCOVBlock::addCount(size_t DstEdgeNo, uint64_t N) { DstEdges[DstEdgeNo]->Dst->Counter += N; } +/// sortDstEdges - Sort destination edges by block number, nop if already +/// sorted. This is required for printing branch info in the correct order. +void GCOVBlock::sortDstEdges() { + if (!DstEdgesAreSorted) { + SortDstEdgesFunctor SortEdges; + std::stable_sort(DstEdges.begin(), DstEdges.end(), SortEdges); + } +} + /// collectLineCounts - Collect line counts. This must be used after /// reading .gcno and .gcda files. void GCOVBlock::collectLineCounts(FileInfo &FI) { @@ -357,9 +381,32 @@ void GCOVBlock::dump() const { //===----------------------------------------------------------------------===// // FileInfo implementation. +// Safe integer division, returns 0 if numerator is 0. +static uint32_t safeDiv(uint64_t Numerator, uint64_t Divisor) { + if (!Numerator) + return 0; + return Numerator/Divisor; +} + +// This custom division function mimics gcov's branch ouputs: +// - Round to closest whole number +// - Only output 0% or 100% if it's exactly that value +static uint32_t branchDiv(uint64_t Numerator, uint64_t Divisor) { + if (!Numerator) + return 0; + if (Numerator == Divisor) + return 100; + + uint8_t Res = (Numerator*100+Divisor/2) / Divisor; + if (Res == 0) + return 1; + if (Res == 100) + return 99; + return Res; +} + /// print - Print source files with collected line count information. -void FileInfo::print(StringRef GCNOFile, StringRef GCDAFile, - const GCOVOptions &Options) const { +void FileInfo::print(StringRef GCNOFile, StringRef GCDAFile) const { for (StringMap::const_iterator I = LineInfo.begin(), E = LineInfo.end(); I != E; ++I) { StringRef Filename = I->first(); @@ -383,12 +430,24 @@ void FileInfo::print(StringRef GCNOFile, StringRef GCDAFile, OS << " -: 0:Programs:" << ProgramCount << "\n"; const LineData &Line = I->second; - for (uint32_t i = 0; !AllLines.empty(); ++i) { - LineData::const_iterator BlocksIt = Line.find(i); + for (uint32_t LineIndex = 0; !AllLines.empty(); ++LineIndex) { + if (Options.BranchProb) { + FunctionLines::const_iterator FuncsIt = Line.Functions.find(LineIndex); + if (FuncsIt != Line.Functions.end()) + printFunctionSummary(OS, FuncsIt->second); + } - if (BlocksIt != Line.end()) { - // Add up the block counts to form line counts. + BlockLines::const_iterator BlocksIt = Line.Blocks.find(LineIndex); + if (BlocksIt == Line.Blocks.end()) { + // No basic blocks are on this line. Not an executable line of code. + OS << " -:"; + std::pair P = AllLines.split('\n'); + OS << format("%5u:", LineIndex+1) << P.first << "\n"; + AllLines = P.second; + } else { const BlockVector &Blocks = BlocksIt->second; + + // Add up the block counts to form line counts. uint64_t LineCount = 0; for (BlockVector::const_iterator I = Blocks.begin(), E = Blocks.end(); I != E; ++I) { @@ -406,30 +465,84 @@ void FileInfo::print(StringRef GCNOFile, StringRef GCDAFile, OS << " #####:"; else OS << format("%9" PRIu64 ":", LineCount); - } else { - OS << " -:"; - } - std::pair P = AllLines.split('\n'); - OS << format("%5u:", i+1) << P.first << "\n"; - AllLines = P.second; - if (Options.AllBlocks && BlocksIt != Line.end()) { - // Output the counts for each block at the last line of the block. + std::pair P = AllLines.split('\n'); + OS << format("%5u:", LineIndex+1) << P.first << "\n"; + AllLines = P.second; + uint32_t BlockNo = 0; - const BlockVector &Blocks = BlocksIt->second; + uint32_t EdgeNo = 0; for (BlockVector::const_iterator I = Blocks.begin(), E = Blocks.end(); I != E; ++I) { const GCOVBlock *Block = *I; - if (Block->getLastLine() != i+1) - continue; - if (Block->getCount() == 0) - OS << " $$$$$:"; - else - OS << format("%9" PRIu64 ":", (uint64_t)Block->getCount()); - OS << format("%5u-block %u\n", i+1, BlockNo++); + // Only print block and branch information at the end of the block. + if (Block->getLastLine() != LineIndex+1) + continue; + if (Options.AllBlocks) + printBlockInfo(OS, *Block, LineIndex, BlockNo); + if (Options.BranchProb) + printBranchInfo(OS, *Block, LineIndex, EdgeNo); } } } } } + +/// printFunctionSummary - Print function and block summary. +void FileInfo::printFunctionSummary(raw_fd_ostream &OS, + const FunctionVector &Funcs) const { + for (FunctionVector::const_iterator I = Funcs.begin(), E = Funcs.end(); + I != E; ++I) { + const GCOVFunction *Func = *I; + uint64_t EntryCount = Func->getEntryCount(); + uint32_t BlocksExecuted = 0; + for (GCOVFunction::BlockIterator I = Func->block_begin(), + E = Func->block_end(); I != E; ++I) { + const GCOVBlock *Block = *I; + if (Block->getNumDstEdges() && Block->getCount()) + ++BlocksExecuted; + } + + OS << "function " << Func->getName() << " called " << EntryCount + << " returned " << safeDiv(Func->getExitCount()*100, EntryCount) + << "% blocks executed " + << safeDiv(BlocksExecuted*100, Func->getNumBlocks()-1) << "%\n"; + } +} + +/// printBlockInfo - Output counts for each block. +void FileInfo::printBlockInfo(raw_fd_ostream &OS, const GCOVBlock &Block, + uint32_t LineIndex, uint32_t &BlockNo) const { + if (Block.getCount() == 0) + OS << " $$$$$:"; + else + OS << format("%9" PRIu64 ":", Block.getCount()); + OS << format("%5u-block %2u\n", LineIndex+1, BlockNo++); +} + +/// printBranchInfo - Print branch probabilities for blocks that have +/// conditional branches. +void FileInfo::printBranchInfo(raw_fd_ostream &OS, const GCOVBlock &Block, + uint32_t LineIndex, uint32_t &EdgeNo) const { + if (Block.getNumDstEdges() < 2) + return; + + SmallVector BranchCounts; + uint64_t TotalCounts = 0; + for (GCOVBlock::EdgeIterator I = Block.dst_begin(), E = Block.dst_end(); + I != E; ++I) { + const GCOVEdge *Edge = *I; + BranchCounts.push_back(Edge->Count); + TotalCounts += Edge->Count; + } + + for (SmallVectorImpl::const_iterator I = BranchCounts.begin(), + E = BranchCounts.end(); I != E; ++I) { + if (TotalCounts) + OS << format("branch %2u taken %u%%\n", EdgeNo++, + branchDiv(*I, TotalCounts)); + else + OS << format("branch %2u never executed\n", EdgeNo++); + } +} diff --git a/test/tools/llvm-cov/Inputs/test_-a_-b.cpp.gcov b/test/tools/llvm-cov/Inputs/test_-a_-b.cpp.gcov new file mode 100644 index 0000000000..ae21037401 --- /dev/null +++ b/test/tools/llvm-cov/Inputs/test_-a_-b.cpp.gcov @@ -0,0 +1,134 @@ + -: 0:Source:test.cpp + -: 0:Graph:test.gcno + -: 0:Data:test.gcda + -: 0:Runs:2 + -: 0:Programs:1 + -: 1:#include "test.h" + -: 2:#include + -: 3: + -: 4:bool on = false; + -: 5:int len = 42; + -: 6:double grid[10][10] = {0}; + -: 7:const char * hello = "world"; + -: 8:const char * world = "hello"; + -: 9: +function _ZN1A1BEv called 8589934592 returned 100% blocks executed 100% +8589934592: 10:void A::B() {} +8589934592: 10-block 0 + -: 11: +function _Z7uselessv called 0 returned 0% blocks executed 0% + #####: 12:void useless() {} + $$$$$: 12-block 0 + -: 13: +function _Z12more_uselessv called 0 returned 0% blocks executed 0% + -: 14:double more_useless() { + #####: 15: return 0; + $$$$$: 15-block 0 + -: 16:} + -: 17: +function _Z3foov called 2 returned 100% blocks executed 100% + -: 18:int foo() { + 2: 19: on = true; + 2: 20: return 3; + 2: 20-block 0 + -: 21:} + -: 22: +function _Z3barv called 0 returned 0% blocks executed 0% + -: 23:int bar() { + #####: 24: len--; + #####: 25: return foo() + 45; + $$$$$: 25-block 0 + -: 26:} + -: 27: +function _Z6assignii called 8 returned 100% blocks executed 100% + 8: 28:void assign(int ii, int jj) { + 8: 29: grid[ii][jj] = (ii+1) * (jj+1); + 8: 30:} + 8: 30-block 0 + -: 31: +function _Z15initialize_gridv called 2 returned 100% blocks executed 100% + -: 32:void initialize_grid() { + 6: 33: for (int ii = 0; ii < 2; ii++) + 2: 33-block 0 + 6: 33-block 1 +branch 0 taken 67% +branch 1 taken 33% + 4: 33-block 2 + 12: 34: for (int jj = 0; jj < 2; jj++) + 4: 34-block 0 + 12: 34-block 1 +branch 0 taken 67% +branch 1 taken 33% + 8: 34-block 2 + 8: 35: assign(ii, jj); + 8: 35-block 0 + 4: 35-block 1 + 2: 36:} + 2: 36-block 0 + -: 37: +function main called 2 returned 100% blocks executed 94% + -: 38:int main() { + 2: 39: initialize_grid(); + -: 40: + 2: 41: int a = 2; + 2: 42: on = rand() % 2; + 2: 43: if (on) { + 2: 43-block 0 +branch 0 taken 100% +branch 1 taken 0% + 2: 44: foo(); + 2: 45: ++a; + 2: 46: } else { + 2: 46-block 0 + #####: 47: bar(); + #####: 48: a += rand(); + $$$$$: 48-block 0 + -: 49: } + -: 50: + 22: 51: for (int ii = 0; ii < 10; ++ii) { + 2: 51-block 0 + 22: 51-block 1 +branch 0 taken 91% +branch 1 taken 9% + 20: 51-block 2 + 20: 52: switch (rand() % 5) { + 20: 52-block 0 +branch 0 taken 20% +branch 1 taken 0% +branch 2 taken 10% +branch 3 taken 30% +branch 4 taken 40% + -: 53: case 0: + 4: 54: a += rand(); + 4: 55: break; + 4: 55-block 0 + -: 56: case 1: + -: 57: case 2: + 2: 58: a += rand() / rand(); + 2: 59: break; + 2: 59-block 0 + -: 60: case 3: + 6: 61: a -= rand(); + 6: 62: break; + 6: 62-block 0 + -: 63: default: + 8: 64: a = -1; + 8: 65: } + 8: 65-block 0 + 20: 66: } + 20: 66-block 0 + -: 67: + 2: 68: A thing; +8589934594: 69: for (uint64_t ii = 0; ii < 4294967296; ++ii) + 2: 69-block 0 +8589934594: 69-block 1 +branch 0 taken 99% +branch 1 taken 1% +8589934592: 69-block 2 +8589934592: 70: thing.B(); +8589934592: 70-block 0 + -: 71: + 2: 72: return a + 8 + grid[2][3] + len; + 2: 72-block 0 + -: 73: return more_useless(); + -: 74:} diff --git a/test/tools/llvm-cov/Inputs/test_-a_-b.h.gcov b/test/tools/llvm-cov/Inputs/test_-a_-b.h.gcov new file mode 100644 index 0000000000..f3dabcb727 --- /dev/null +++ b/test/tools/llvm-cov/Inputs/test_-a_-b.h.gcov @@ -0,0 +1,12 @@ + -: 0:Source:./test.h + -: 0:Graph:test.gcno + -: 0:Data:test.gcda + -: 0:Runs:2 + -: 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 { + 2: 1-block 0 + 2: 1-block 1 + -: 2: virtual void B(); + -: 3:}; diff --git a/test/tools/llvm-cov/llvm-cov.test b/test/tools/llvm-cov/llvm-cov.test index 43725a3cbd..bf0fb07631 100644 --- a/test/tools/llvm-cov/llvm-cov.test +++ b/test/tools/llvm-cov/llvm-cov.test @@ -13,6 +13,10 @@ RUN: llvm-cov -gcno=test.gcno -gcda=test.gcda -a RUN: diff -aub test_-a.cpp.gcov test.cpp.gcov RUN: diff -aub test_-a.h.gcov test.h.gcov +RUN: llvm-cov -gcno=test.gcno -gcda=test.gcda -a -b +RUN: diff -aub test_-a_-b.cpp.gcov test.cpp.gcov +RUN: diff -aub test_-a_-b.h.gcov test.h.gcov + RUN: not llvm-cov -gcno=test_read_fail.gcno -gcda=test.gcda RUN: not llvm-cov -gcno=test.gcno -gcda=test_file_checksum_fail.gcda diff --git a/tools/llvm-cov/llvm-cov.cpp b/tools/llvm-cov/llvm-cov.cpp index 235670b7ce..fd4fa24411 100644 --- a/tools/llvm-cov/llvm-cov.cpp +++ b/tools/llvm-cov/llvm-cov.cpp @@ -33,6 +33,9 @@ InputGCDA("gcda", cl::desc(""), cl::init("")); static cl::opt AllBlocks("a", cl::init(false), cl::desc("display all block info")); +static cl::opt +BranchProb("b", cl::init(false), cl::desc("display branch info")); + //===----------------------------------------------------------------------===// int main(int argc, char **argv) { // Print a stack trace if we signal out. @@ -73,8 +76,9 @@ int main(int argc, char **argv) { if (DumpGCOV) GF.dump(); - FileInfo FI; + GCOVOptions Options(AllBlocks, BranchProb); + FileInfo FI(Options); GF.collectLineCounts(FI); - FI.print(InputGCNO, InputGCDA, GCOVOptions(AllBlocks)); + FI.print(InputGCNO, InputGCDA); return 0; } -- cgit v1.2.3