[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

2

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

2

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) {
+  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());
+  for (unsigned Line : LinesInBlock) {
+    CoverageInfo[FE][Line]++;
+  }
+}
+
 /// 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))))

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: -:5:  int i = 2;
+// CHECK-NEXT: 1:6:  ++i;
+// CHECK-NEXT: 1:7:  if (i != 0) {
+// CHECK-NEXT: 1:8:    ++i;
+// CHECK-NEXT: 1:9:  } else {
+// CHECK-NEXT: -:10:    --i;
+// CHECK-NEXT: -:11:  }
+// CHECK-NEXT: -:12:}