[analyzer] Track terminator conditions on which a tracked expression depends

This patch is a major part of my GSoC project, aimed to improve the bug
reports of the analyzer.

TL;DR: Help the analyzer understand that some conditions are important,
and should be explained better. If an CFGBlock is a control dependency
of a block where an expression value is tracked, explain the condition
expression better by tracking it.

if (A) // let's explain why we believe A to be true
  10 / x; // division by zero

This is an experimental feature, and can be enabled by the
off-by-default analyzer configuration "track-conditions".

In detail:

This idea was inspired by the program slicing algorithm. Essentially,
two things are used to produce a program slice (a subset of the program
relevant to a (statement, variable) pair): data and control
dependencies. The bug path (the linear path in the ExplodedGraph that leads
from the beginning of the analysis to the error node) enables to
analyzer to argue about data dependencies with relative ease.

Control dependencies are a different slice of the cake entirely.

Just because we reached a branch during symbolic execution, it
doesn't mean that that particular branch has any effect on whether the
bug would've occured. This means that we can't simply rely on the bug
path to gather control dependencies.

In previous patches, LLVM's IDFCalculator, which works on a control flow
graph rather than the ExplodedGraph was generalized to solve this issue.
We use this information to heuristically guess that the value of a tracked
expression depends greatly on it's control dependencies, and start
tracking them as well.

After plenty of evaluations this was seen as great idea, but still
lacking refinements (we should have different descriptions about a
conditions value), hence it's off-by-default.

Differential Revision: https://reviews.llvm.org/D62883

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@365207 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 15 insertions, 0 deletions

diff --git a/include/clang/StaticAnalyzer/Core/AnalyzerOptions.def b/include/clang/StaticAnalyzer/Core/AnalyzerOptions.def
index 40d5d47bbc..77e99297d2 100644
--- a/include/clang/StaticAnalyzer/Core/AnalyzerOptions.def
+++ b/include/clang/StaticAnalyzer/Core/AnalyzerOptions.def
@@ -291,6 +291,11 @@ ANALYZER_OPTION(bool, DisplayCTUProgress, "display-ctu-progress",
                 "the analyzer's progress related to ctu.",
                 false)
 
+ANALYZER_OPTION(bool, ShouldTrackConditions, "track-conditions",
+                "Whether to track conditions that are a control dependency of "
+                "an already tracked variable.",
+                false)
+
 //===----------------------------------------------------------------------===//
 // Unsinged analyzer options.
 //===----------------------------------------------------------------------===//
diff --git a/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h b/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h
index 4cccb38ce2..d30ad19b20 100644
--- a/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h
+++ b/include/clang/StaticAnalyzer/Core/BugReporter/BugReporter.h
@@ -153,6 +153,9 @@ protected:
   /// \sa removeInvalidation
   llvm::SmallSet<InvalidationRecord, 4> Invalidations;
 
+  /// Conditions we're already tracking.
+  llvm::SmallSet<const ExplodedNode *, 4> TrackedConditions;
+
 private:
   // Used internally by BugReporter.
   Symbols &getInterestingSymbols();
@@ -349,6 +352,13 @@ public:
   visitor_iterator visitor_begin() { return Callbacks.begin(); }
   visitor_iterator visitor_end() { return Callbacks.end(); }
 
+  /// Notes that the condition of the CFGBlock associated with \p Cond is
+  /// being tracked.
+  /// \returns false if the condition is already being tracked.
+  bool addTrackedCondition(const ExplodedNode *Cond) {
+    return TrackedConditions.insert(Cond).second;
+  }
+
   /// Profile to identify equivalent bug reports for error report coalescing.
   /// Reports are uniqued to ensure that we do not emit multiple diagnostics
   /// for each bug.