[analyzer] Export coverage information from the analyzer.

[xazax.hun]

Summary

This patch adds a new option to export an optimistic basic block coverage from the static analyzer.

Example usage:

clang++ --analyze -Xclang -analyzer-config -Xclang record-coverage=gcovfiles foo.cpp

Example output:

-:0:Source:foo.cpp
-:0:Runs:1
-:0:Programs:1
-:1:#include <iostream>
-:2:
-:3:int main() {
1:4:  int i = 2;
1:5:  ++i;
1:6:  if (i) {
1:7:    std::cout << "foo" << std::endl;
-:8:  } else {
#####:9:    std::cout << "bar" << std::endl;
-:10:  }
-:11:}

It will generate a gcov file (sourcename.gcov) for each non system header source file in the directory that was given with the record-coverage option.

The gcov format is relatively easy to read, but HTML can be generated using gcovr:

gcovr -g gcovfiles --html --html-details -r . -o example.html

Possible use cases:

• Get an overview about the coverage of the static analyzer on a given codebase.
• Collect ideas how to increase the coverage and test them.
• Evaluate possible cross translation unit coverage patterns.
• Write rigorous tests about coverage.

[zaks.anna]

Please, add multi-file tests and tests where a line is covered more than once.

lib/StaticAnalyzer/Core/ExprEngine.cpp

262

Can this be a debug checker?

274

Would it be better to break if the buffer is invalid?
Should this be hoisted out of the loop?

277

Please, come up with constructive error messages.

281

What does '-' mean in this case? Why is it needed?

test/Analysis/record-coverage.cpp.expected

3

Does '-' mean not covered? If so, why the first 2 statements are not covered?

[zaks.anna]

lib/StaticAnalyzer/Core/ExprEngine.cpp

274

I see why this cannot be hoisted.

[xazax.hun]

• Improved performance.
• Fixed an off by one error.
• Also export unexecuted lines.
• Added context.

[xazax.hun]

In D25985#580270, @zaks.anna wrote:

Please, add multi-file tests and tests where a line is covered more than once.

Ok, I will add it in the next iteration.

lib/StaticAnalyzer/Core/ExprEngine.cpp

262

You mean the dumping part or also collecting the coverage? It can be a debug checker if we add a new callback like "checkBasicBlockBegin". I did not want to add such callback just for a debug check. However, it is possible to move only the dumping part to a separate checker. What would you prefer?

281

The - means lines without executable code. ###### means lines that contains executable code but unexecuted. The lines that has "0" as the line number are attributes to help the tools consume the gcov file.

test/Analysis/record-coverage.cpp.expected

3

There was an off by one error that I fixed.

[xazax.hun]

• Added a python script to merge gcov files.
• Fixed an error
• Multifile test is not added yet, will do so in the next update.

[zaks.anna]

Added a python script to merge gcov files.

When the patches that are being reviewed are growing new functionality, it's much more difficult to review them. Please, submit the python script as a separate patch.

lib/StaticAnalyzer/Core/ExprEngine.cpp

262

I would prefer to add a "checkBasicBlockBegin" callback and move all of this diagnostic code into a debug checker.

277

How was this addressed?

[xazax.hun]

lib/StaticAnalyzer/Core/ExprEngine.cpp

262

Do you think the checkers should be able to add state transitions from BeginBasicBlock callback? Would you prefer to have an EndBasicBlock callback for symmetry?

[zaks.anna]

lib/StaticAnalyzer/Core/ExprEngine.cpp

262

I cannot think of any right now. The main advantages of having this as a debug checker are:

• Not having this code in ExprEngine.cpp - it's not related to the core engine functionality.
• More importantly, discoverability of this functionality.

On the downside, we would not want to add a checker API if it has no useful users.

[NoQ]

Maybe you could instead make a checker that subscribes for checkEndAnalysis and scans the provided ExplodedGraph's nodes_begin()..nodes_end() for visited statement-based program points (as in PathDiagnosticLocation::getStmt(N))? This should give you per-statement precision, and you'd avoid dealing with the CFG element kinds. That sounds more straightforward and that's essentially how our deadcode checker works (but it suppresses its positives for incomplete analyses - you don't need even that).

include/clang/StaticAnalyzer/Core/AnalyzerOptions.h

private:
   Optional<bool> InlineLambdas;
 
   /// \sa shouldWidenLoops
   Optional<bool> WidenLoops;
 
   /// \sa shouldDisplayNotesAsEvents
   Optional<bool> DisplayNotesAsEvents;
 
+  /// \sa shouldRecordCoverage
+  Optional<StringRef> CoverageExportDir;  
+
   /// A helper function that retrieves option for a given full-qualified
   /// checker name.
   /// Options for checkers can be specified via 'analyzer-config' command-line
   /// option.
   /// Example:
   /// @code-analyzer-config unix.Malloc:OptionName=CheckerOptionValue @endcode
   /// or @code-analyzer-config unix:OptionName=GroupOptionValue @endcode
   /// for groups of checkers.
public:
   /// Returns true if the bug reporter should transparently treat extra note
   /// diagnostic pieces as event diagnostic pieces. Useful when the diagnostic
   /// consumer doesn't support the extra note pieces.
   ///
   /// This is controlled by the 'extra-notes-as-events' option, which defaults
   /// to false when unset.
   bool shouldDisplayNotesAsEvents();
 
+  /// Determines where the coverage info should be dumped to. The coverage
+  /// information is recorded on the basic block level granularity.
+  StringRef coverageExportDir();
+
 public:
   AnalyzerOptions() :
     AnalysisStoreOpt(RegionStoreModel),
     AnalysisConstraintsOpt(RangeConstraintsModel),
     AnalysisDiagOpt(PD_HTML),
     AnalysisPurgeOpt(PurgeStmt),
     DisableAllChecks(0),
     ShowCheckerHelp(0),

lib/StaticAnalyzer/Core/AnalyzerOptions.cpp

 }
 
 bool AnalyzerOptions::shouldDisplayNotesAsEvents() {
   if (!DisplayNotesAsEvents.hasValue())
     DisplayNotesAsEvents =
         getBooleanOption("notes-as-events", /*Default=*/false);
   return DisplayNotesAsEvents.getValue();
 }
+
+StringRef AnalyzerOptions::coverageExportDir() {
+  if (!CoverageExportDir.hasValue())
+    CoverageExportDir = getOptionAsString("record-coverage", /*Default=*/"");
+  return CoverageExportDir.getValue();
+}
+

lib/StaticAnalyzer/Core/ExprEngine.cpp

 #include "clang/Basic/PrettyStackTrace.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/LineIterator.h"
+#include "llvm/Support/Path.h"
 #include "llvm/Support/SaveAndRestore.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/raw_os_ostream.h"
+#include <fstream>
 
 #ifndef NDEBUG
 #include "llvm/Support/GraphWriter.h"
 #endif
 
 using namespace clang;
 using namespace ento;
 using llvm::APSInt;
for (SmallVectorImpl<const CastExpr *>::reverse_iterator I = Casts.rbegin(),
        I != E; ++I) {
     Reg = StoreMgr.evalDerivedToBase(Reg, *I);
   }
 
   State = State->BindExpr(Result, LC, Reg);
   return State;
 }
 
+// Mapping from file to line indexed hit count vector.
+static llvm::DenseMap<const FileEntry *,std::vector<int>> CoverageInfo;
+
+static void dumpCoverageInfo(llvm::SmallVectorImpl<char> &Path,
+                             SourceManager &SM) {
+  for (auto &Entry : CoverageInfo) {
+    SmallString<128> FilePath;
+    const FileEntry *FE = Entry.getFirst();
+    llvm::sys::path::append(FilePath, Path, FE->getName() + ".gcov");
+    SmallString<128> DirPath = FilePath;
+    llvm::sys::path::remove_filename(DirPath);
+    llvm::sys::fs::create_directories(DirPath);
+    bool Invalid = false;
+    llvm::MemoryBuffer *Buf = SM.getMemoryBufferForFile(FE, &Invalid);
+    if (Invalid)
+      continue;
+    std::ofstream OutFile(FilePath.c_str());
+    if (!OutFile) {
+      llvm::errs() << FilePath << " Fuck!\n";
+      continue;
+    }
+    llvm::raw_os_ostream Out(OutFile);
+    Out << "-:0:Source:" << FE->getName() << '\n';
+    Out << "-:0:Runs:1\n";
+    Out << "-:0:Programs:1\n";
+    for (llvm::line_iterator LI(*Buf, false); !LI.is_at_eof(); ++LI) {
+      int Count = Entry.getSecond()[LI.line_number() - 1];
+      if (Count > 0) {
+        Out << Count;
+      } else if (Count < 0) {
+        Out << "#####";
+      } else {
+        Out << '-';
+      }
+      Out << ':' << LI.line_number() << ':' << *LI << '\n';
+    }
+  }
+}
+
 //===----------------------------------------------------------------------===//
 // Top-level transfer function logic (Dispatcher).
 //===----------------------------------------------------------------------===//
 
 /// evalAssume - Called by ConstraintManager. Used to call checker-specific
 ///  logic for handling assumptions on symbolic values.
 ProgramStateRef ExprEngine::processAssume(ProgramStateRef state,
                                               SVal cond, bool assumption) {

 }
 
 void ExprEngine::printState(raw_ostream &Out, ProgramStateRef State,
                             const char *NL, const char *Sep) {
   getCheckerManager().runCheckersForPrintState(Out, State, NL, Sep);
 }
 
 void ExprEngine::processEndWorklist(bool hasWorkRemaining) {
+  if (!AMgr.options.coverageExportDir().empty()) {
+    SmallString<128> Path = AMgr.options.coverageExportDir();
+    SourceManager &SM = getContext().getSourceManager();
+    SM.getFileManager().makeAbsolutePath(Path);
+    dumpCoverageInfo(Path, SM);
+  }
   getCheckerManager().runCheckersForEndAnalysis(G, BR, *this);
 }
 
 void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred,
                                    unsigned StmtIdx, NodeBuilderContext *Ctx) {
   PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
   currStmtIdx = StmtIdx;
   currBldrCtx = Ctx;
bool ExprEngine::replayWithoutInlining(ExplodedNode *N,
 
   // Add the new node to the work list.
   Engine.enqueueStmtNode(NewNode, CalleeSF->getCallSiteBlock(),
                                   CalleeSF->getIndex());
   NumTimesRetriedWithoutInlining++;
   return true;
 }
 
+// Add the line range of the CFGBlock to a file entry indexed map.
+static void processCoverageInfo(const CFGBlock &Block, SourceManager &SM,
+                                bool Unexecuted = false) {
+  llvm::SmallVector<unsigned, 32> LinesInBlock;
+  const FileEntry *FE = nullptr;
+  for (unsigned I = 0; I < Block.size(); ++I) {
+    const Stmt *S = nullptr;
+    switch (Block[I].getKind()) {
+    case CFGElement::Statement:
+      S = Block[I].castAs<CFGStmt>().getStmt();
+      break;
+    case CFGElement::Initializer:
+      S = Block[I].castAs<CFGInitializer>().getInitializer()->getInit();
+      if (!S)
+        continue;
+      break;
+    case CFGElement::NewAllocator:
+      S = Block[I].castAs<CFGNewAllocator>().getAllocatorExpr();
+      break;
+    default:
+      continue;
+    }
+    assert(S);
+    SourceLocation SpellingStartLoc = SM.getSpellingLoc(S->getLocStart());
+    if (SM.isInSystemHeader(SpellingStartLoc))
+      return;
+    FileID FID = SM.getFileID(SpellingStartLoc);
+    if (FE) {
+      if (FE != SM.getFileEntryForID(FID))
+        continue;
+    } else {
+      FE = SM.getFileEntryForID(FID);
+      if (CoverageInfo.find(FE) == CoverageInfo.end()) {
+        unsigned Lines = SM.getSpellingLineNumber(SM.getLocForEndOfFile(FID));
+        CoverageInfo.insert(std::make_pair(FE, std::vector<int>(Lines, 0)));
+      }
+    }
+    bool Invalid = false;
+    unsigned LineBegin = SM.getSpellingLineNumber(S->getLocStart(), &Invalid);
+    if (Invalid)
+      continue;
+    unsigned LineEnd = SM.getSpellingLineNumber(S->getLocEnd(), &Invalid);
+    if (Invalid)
+      continue;
+    for (unsigned Line = LineBegin; Line <= LineEnd; ++Line) {
+      LinesInBlock.push_back(Line);
+    }
+  }
+  if (!FE)
+    return;
+  std::sort(LinesInBlock.begin(), LinesInBlock.end());
+  LinesInBlock.erase(std::unique(LinesInBlock.begin(), LinesInBlock.end()),
+                     LinesInBlock.end());
+  std::vector<int> &FileCov = CoverageInfo[FE];
+  if (Unexecuted) {
+    for (unsigned Line : LinesInBlock) {
+      if (FileCov[Line - 1] == 0)
+        FileCov[Line - 1] = -1;
+    }
+    return;
+  }
+  for (unsigned Line : LinesInBlock) {
+    if (FileCov[Line - 1] < 0)
+      FileCov[Line - 1] = 1;
+    else
+      ++FileCov[Line - 1];
+  }
+}
+
 /// Block entrance.  (Update counters).
 void ExprEngine::processCFGBlockEntrance(const BlockEdge &L,
                                          NodeBuilderWithSinks &nodeBuilder,
                                          ExplodedNode *Pred) {
   PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
 
+  if (!AMgr.options.coverageExportDir().empty())
+    processCoverageInfo(*L.getDst(), getContext().getSourceManager());
+
   // If this block is terminated by a loop and it has already been visited the
   // maximum number of times, widen the loop.
   unsigned int BlockCount = nodeBuilder.getContext().blockCount();
   if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 &&
       AMgr.options.shouldWidenLoops()) {
     const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminator();
     if (!(Term &&
           (isa<ForStmt>(Term) || isa<WhileStmt>(Term) || isa<DoStmt>(Term))))
return std::find_if(Set.begin(), Set.end(),
          }) == Set.end();
 }
 #endif
 
 void ExprEngine::processBeginOfFunction(NodeBuilderContext &BC,
                                         ExplodedNode *Pred,
                                         ExplodedNodeSet &Dst,
                                         const BlockEdge &L) {
+  if (!AMgr.options.coverageExportDir().empty()) {
+    for (auto BlockIT : *L.getLocationContext()->getCFG())
+      processCoverageInfo(*BlockIT, getContext().getSourceManager(), true);
+  }
   SaveAndRestore<const NodeBuilderContext *> NodeContextRAII(currBldrCtx, &BC);
   getCheckerManager().runCheckersForBeginFunction(Dst, L, Pred, *this);
 }
 
 /// ProcessEndPath - Called by CoreEngine.  Used to generate end-of-path
 ///  nodes when the control reaches the end of a function.
 void ExprEngine::processEndOfFunction(NodeBuilderContext& BC,
                                       ExplodedNode *Pred,

test/Analysis/analyzer-config.c

 // CHECK-NEXT: ipa = dynamic-bifurcate
 // CHECK-NEXT: ipa-always-inline-size = 3
 // CHECK-NEXT: leak-diagnostics-reference-allocation = false
 // CHECK-NEXT: max-inlinable-size = 50
 // CHECK-NEXT: max-nodes = 150000
 // CHECK-NEXT: max-times-inline-large = 32
 // CHECK-NEXT: min-cfg-size-treat-functions-as-large = 14
 // CHECK-NEXT: mode = deep
+// CHECK-NEXT: record-coverage =
 // CHECK-NEXT: region-store-small-struct-limit = 2
 // CHECK-NEXT: widen-loops = false
 // CHECK-NEXT: [stats]
-// CHECK-NEXT: num-entries = 15
+// CHECK-NEXT: num-entries = 16
 

test/Analysis/analyzer-config.cpp

 // CHECK-NEXT: ipa = dynamic-bifurcate
 // CHECK-NEXT: ipa-always-inline-size = 3
 // CHECK-NEXT: leak-diagnostics-reference-allocation = false
 // CHECK-NEXT: max-inlinable-size = 50
 // CHECK-NEXT: max-nodes = 150000
 // CHECK-NEXT: max-times-inline-large = 32
 // CHECK-NEXT: min-cfg-size-treat-functions-as-large = 14
 // CHECK-NEXT: mode = deep
+// CHECK-NEXT: record-coverage =
 // CHECK-NEXT: region-store-small-struct-limit = 2
 // CHECK-NEXT: widen-loops = false
 // CHECK-NEXT: [stats]
-// CHECK-NEXT: num-entries = 20
+// CHECK-NEXT: num-entries = 21

test/Analysis/record-coverage.cpp

+// RUN: %clang_cc1 -analyze -analyzer-checker=core -analyzer-config record-coverage=%T %s
+// RUN: FileCheck -input-file %T/%s.gcov %s.expected
+
+int main() {
+  int i = 2;
+  ++i;
+  if (i != 0) {
+    ++i;
+  } else {
+    --i;
+  }
+}

test/Analysis/record-coverage.cpp.expected

+// CHECK:      -:4:int main() {
+// CHECK-NEXT: 1:5:  int i = 2;
+// CHECK-NEXT: 1:6:  ++i;
+// CHECK-NEXT: 1:7:  if (i != 0) {
+// CHECK-NEXT: 1:8:    ++i;
+// CHECK-NEXT: -:9:  } else {
+// CHECK-NEXT: #####:10:    --i;
+// CHECK-NEXT: -:11:  }
+// CHECK-NEXT: -:12:}

utils/analyzer/MergeCoverage.py

+'''
+   Script to merge gcov files produced by the static analyzer.
+   So coverage information of header files from multiple translation units are
+   merged together. The output can be pocessed by gcovr format like:
+        gcovr -g outputdir --html --html-details -r sourceroot -o example.html
+   The expected layout of input (the input should be the gcovdir):
+        gcovdir/TranslationUnit1/file1.gcov
+        gcovdir/TranslationUnit1/subdir/file2.gcov
+        ...
+        gcovdir/TranslationUnit1/fileN.gcov
+        ...
+        gcovdir/TranslationUnitK/fileM.gcov
+   The output:
+        outputdir/file1.gcov
+        outputdir/subdir/file2.gcov
+        ...
+        outputdir/fileM.gcov
+'''
+
+import argparse
+import os
+import sys
+import shutil
+
+def is_num(val):
+    '''Check if val can be converted to int.'''
+    try:
+        int(val)
+        return True
+    except ValueError:
+        return False
+
+
+def is_valid(line):
+    '''Check whether a list is a valid gcov line after join on colon.'''
+    if len(line) == 4:
+        return line[2].lower() in {"graph", "data", "runs", "programs",
+                "source"}
+    else:
+        return len(line) == 3
+
+
+def merge_gcov(from_gcov, to_gcov):
+    '''Merge to existing gcov file, modify the second one.'''
+    with open(from_gcov) as from_file, open(to_gcov) as to_file:
+        from_lines = from_file.readlines()
+        to_lines = to_file.readlines()
+
+        if len(from_lines) != len(to_lines):
+            print("Fatal error: failed to match gcov files,"
+                    " different line count: (%s, %s)" %
+                    (from_gcov, to_gcov))
+            sys.exit(1)
+
+        for i in range(len(from_lines)):
+            from_split = from_lines[i].split(":")
+            to_split = to_lines[i].split(":")
+
+            if not is_valid(from_split) or not is_valid(to_split):
+                print("Fatal error: invalid gcov format (%s, %s)" %
+                        (from_gcov, to_gcov))
+                print("%s, %s" % (from_split, to_split))
+                sys.exit(1)
+
+            for j in range(2):
+                if from_split[j+1] != to_split[j+1]:
+                    print("Fatal error: failed to match gcov files: (%s, %s)" %
+                            (from_gcov, to_gcov))
+                    print("%s != %s" % (from_split[j+1], to_split[j+1]))
+                    sys.exit(1)
+
+            if to_split[0] == '#####':
+                to_split[0] = from_split[0]
+            elif to_split[0] == '-':
+                assert from_split[0] == '-'
+            elif is_num(to_split[0]):
+                assert is_num(from_split[0]) or from_split[0] == '#####'
+                if is_num(from_split[0]):
+                    to_split[0] = str(int(to_split[0]) + int(from_split[0]))
+
+            to_lines[i] = ":".join(to_split)
+
+    with open(to_gcov, 'w') as to_file:
+        to_file.writelines(to_lines)
+
+
+def process_tu(tu_path, output):
+    '''Process a directory containing files originated from checking a tu.'''
+    for root, _, files in os.walk(tu_path):
+        for gcovfile in files:
+            _, ext = os.path.splitext(gcovfile)
+            if ext != ".gcov":
+                continue
+            gcov_in_path = os.path.join(root, gcovfile)
+            gcov_out_path = os.path.join(
+                    output, os.path.relpath(gcov_in_path, tu_path))
+            if os.path.exists(gcov_out_path):
+                merge_gcov(gcov_in_path, gcov_out_path)
+            else:
+                # No merging needed.
+                shutil.copyfile(gcov_in_path, gcov_out_path)
+
+
+def main():
+    '''Parsing arguments, process each tu dir.'''
+    parser = argparse.ArgumentParser(description="Merge gcov files from "
+            "different translation units")
+    parser.add_argument("--input", "-i", help="Directory containing the input"
+            " gcov files", required=True)
+    parser.add_argument("--output", "-o", help="Output directory for gcov"
+            " files. Warning! Output tree will be cleared!", required=True)
+    args = parser.parse_args()
+
+    if os.path.exists(args.output):
+        shutil.rmtree(args.output)
+    os.mkdir(args.output)
+
+    for tu_dir in os.listdir(args.input):
+        tu_path = os.path.join(args.input, tu_dir)
+        if not os.path.isdir(tu_path):
+            continue
+
+        process_tu(tu_path, args.output)
+
+
+if __name__ == '__main__':
+    main()