Split libAnalysis into two libraries: libAnalysis and libChecker.

(1) libAnalysis is a generic analysis library that can be used by
    Sema.  It defines the CFG, basic dataflow analysis primitives, and
    inexpensive flow-sensitive analyses (e.g. LiveVariables).

(2) libChecker contains the guts of the static analyzer, incuding the
    path-sensitive analysis engine and domain-specific checks.

Now any clients that want to use the frontend to build their own tools
don't need to link in the entire static analyzer.

This change exposes various obvious cleanups that can be made to the
layout of files and headers in libChecker.  More changes pending.  :)

This change also exposed a layering violation between AnalysisContext
and MemRegion.  BlockInvocationContext shouldn't explicitly know about
BlockDataRegions.  For now I've removed the BlockDataRegion* from
BlockInvocationContext (removing context-sensitivity; although this
wasn't used yet).  We need to have a better way to extend
BlockInvocationContext (and any LocationContext) to add
context-sensitivty.

llvm-svn: 94406

1 files changed, 599 insertions, 0 deletions

diff --git a/clang/lib/Checker/GRCoreEngine.cpp b/clang/lib/Checker/GRCoreEngine.cpp
new file mode 100644
index 00000000000..d54b0777eda
--- /dev/null
+++ b/clang/lib/Checker/GRCoreEngine.cpp
@@ -0,0 +1,599 @@
+//==- GRCoreEngine.cpp - Path-Sensitive Dataflow Engine ------------*- C++ -*-//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines a generic engine for intraprocedural, path-sensitive,
+//  dataflow analysis via graph reachability engine.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Checker/PathSensitive/GRCoreEngine.h"
+#include "clang/Checker/PathSensitive/GRExprEngine.h"
+#include "clang/AST/Expr.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/ADT/DenseMap.h"
+#include <vector>
+#include <queue>
+
+using llvm::cast;
+using llvm::isa;
+using namespace clang;
+
+//===----------------------------------------------------------------------===//
+// Worklist classes for exploration of reachable states.
+//===----------------------------------------------------------------------===//
+
+namespace {
+class DFS : public GRWorkList {
+  llvm::SmallVector<GRWorkListUnit,20> Stack;
+public:
+  virtual bool hasWork() const {
+    return !Stack.empty();
+  }
+
+  virtual void Enqueue(const GRWorkListUnit& U) {
+    Stack.push_back(U);
+  }
+
+  virtual GRWorkListUnit Dequeue() {
+    assert (!Stack.empty());
+    const GRWorkListUnit& U = Stack.back();
+    Stack.pop_back(); // This technically "invalidates" U, but we are fine.
+    return U;
+  }
+};
+
+class BFS : public GRWorkList {
+  std::queue<GRWorkListUnit> Queue;
+public:
+  virtual bool hasWork() const {
+    return !Queue.empty();
+  }
+
+  virtual void Enqueue(const GRWorkListUnit& U) {
+    Queue.push(U);
+  }
+
+  virtual GRWorkListUnit Dequeue() {
+    // Don't use const reference.  The subsequent pop_back() might make it
+    // unsafe.
+    GRWorkListUnit U = Queue.front();
+    Queue.pop();
+    return U;
+  }
+};
+
+} // end anonymous namespace
+
+// Place the dstor for GRWorkList here because it contains virtual member
+// functions, and we the code for the dstor generated in one compilation unit.
+GRWorkList::~GRWorkList() {}
+
+GRWorkList *GRWorkList::MakeDFS() { return new DFS(); }
+GRWorkList *GRWorkList::MakeBFS() { return new BFS(); }
+
+namespace {
+  class BFSBlockDFSContents : public GRWorkList {
+    std::queue<GRWorkListUnit> Queue;
+    llvm::SmallVector<GRWorkListUnit,20> Stack;
+  public:
+    virtual bool hasWork() const {
+      return !Queue.empty() || !Stack.empty();
+    }
+
+    virtual void Enqueue(const GRWorkListUnit& U) {
+      if (isa<BlockEntrance>(U.getNode()->getLocation()))
+        Queue.push(U);
+      else
+        Stack.push_back(U);
+    }
+
+    virtual GRWorkListUnit Dequeue() {
+      // Process all basic blocks to completion.
+      if (!Stack.empty()) {
+        const GRWorkListUnit& U = Stack.back();
+        Stack.pop_back(); // This technically "invalidates" U, but we are fine.
+        return U;
+      }
+
+      assert(!Queue.empty());
+      // Don't use const reference.  The subsequent pop_back() might make it
+      // unsafe.
+      GRWorkListUnit U = Queue.front();
+      Queue.pop();
+      return U;
+    }
+  };
+} // end anonymous namespace
+
+GRWorkList* GRWorkList::MakeBFSBlockDFSContents() {
+  return new BFSBlockDFSContents();
+}
+
+//===----------------------------------------------------------------------===//
+// Core analysis engine.
+//===----------------------------------------------------------------------===//
+void GRCoreEngine::ProcessEndPath(GREndPathNodeBuilder& Builder) {
+  SubEngine.ProcessEndPath(Builder);
+}
+
+void GRCoreEngine::ProcessStmt(CFGElement E, GRStmtNodeBuilder& Builder) {
+  SubEngine.ProcessStmt(E, Builder);
+}
+
+bool GRCoreEngine::ProcessBlockEntrance(CFGBlock* Blk, const GRState* State,
+                                        GRBlockCounter BC) {
+  return SubEngine.ProcessBlockEntrance(Blk, State, BC);
+}
+
+void GRCoreEngine::ProcessBranch(Stmt* Condition, Stmt* Terminator,
+                   GRBranchNodeBuilder& Builder) {
+  SubEngine.ProcessBranch(Condition, Terminator, Builder);
+}
+
+void GRCoreEngine::ProcessIndirectGoto(GRIndirectGotoNodeBuilder& Builder) {
+  SubEngine.ProcessIndirectGoto(Builder);
+}
+
+void GRCoreEngine::ProcessSwitch(GRSwitchNodeBuilder& Builder) {
+  SubEngine.ProcessSwitch(Builder);
+}
+
+/// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
+bool GRCoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps) {
+
+  if (G->num_roots() == 0) { // Initialize the analysis by constructing
+    // the root if none exists.
+
+    CFGBlock* Entry = &(L->getCFG()->getEntry());
+
+    assert (Entry->empty() &&
+            "Entry block must be empty.");
+
+    assert (Entry->succ_size() == 1 &&
+            "Entry block must have 1 successor.");
+
+    // Get the solitary successor.
+    CFGBlock* Succ = *(Entry->succ_begin());
+
+    // Construct an edge representing the
+    // starting location in the function.
+    BlockEdge StartLoc(Entry, Succ, L);
+
+    // Set the current block counter to being empty.
+    WList->setBlockCounter(BCounterFactory.GetEmptyCounter());
+
+    // Generate the root.
+    GenerateNode(StartLoc, getInitialState(L), 0);
+  }
+
+  while (Steps && WList->hasWork()) {
+    --Steps;
+    const GRWorkListUnit& WU = WList->Dequeue();
+
+    // Set the current block counter.
+    WList->setBlockCounter(WU.getBlockCounter());
+
+    // Retrieve the node.
+    ExplodedNode* Node = WU.getNode();
+
+    // Dispatch on the location type.
+    switch (Node->getLocation().getKind()) {
+      case ProgramPoint::BlockEdgeKind:
+        HandleBlockEdge(cast<BlockEdge>(Node->getLocation()), Node);
+        break;
+
+      case ProgramPoint::BlockEntranceKind:
+        HandleBlockEntrance(cast<BlockEntrance>(Node->getLocation()), Node);
+        break;
+
+      case ProgramPoint::BlockExitKind:
+        assert (false && "BlockExit location never occur in forward analysis.");
+        break;
+
+      default:
+        assert(isa<PostStmt>(Node->getLocation()));
+        HandlePostStmt(cast<PostStmt>(Node->getLocation()), WU.getBlock(),
+                       WU.getIndex(), Node);
+        break;
+    }
+  }
+
+  return WList->hasWork();
+}
+
+
+void GRCoreEngine::HandleBlockEdge(const BlockEdge& L, ExplodedNode* Pred) {
+
+  CFGBlock* Blk = L.getDst();
+
+  // Check if we are entering the EXIT block.
+  if (Blk == &(L.getLocationContext()->getCFG()->getExit())) {
+
+    assert (L.getLocationContext()->getCFG()->getExit().size() == 0
+            && "EXIT block cannot contain Stmts.");
+
+    // Process the final state transition.
+    GREndPathNodeBuilder Builder(Blk, Pred, this);
+    ProcessEndPath(Builder);
+
+    // This path is done. Don't enqueue any more nodes.
+    return;
+  }
+
+  // FIXME: Should we allow ProcessBlockEntrance to also manipulate state?
+
+  if (ProcessBlockEntrance(Blk, Pred->State, WList->getBlockCounter()))
+    GenerateNode(BlockEntrance(Blk, Pred->getLocationContext()), Pred->State, Pred);
+}
+
+void GRCoreEngine::HandleBlockEntrance(const BlockEntrance& L,
+                                       ExplodedNode* Pred) {
+
+  // Increment the block counter.
+  GRBlockCounter Counter = WList->getBlockCounter();
+  Counter = BCounterFactory.IncrementCount(Counter, L.getBlock()->getBlockID());
+  WList->setBlockCounter(Counter);
+
+  // Process the entrance of the block.
+  if (CFGElement E = L.getFirstElement()) {
+    GRStmtNodeBuilder Builder(L.getBlock(), 0, Pred, this,
+                              SubEngine.getStateManager());
+    ProcessStmt(E, Builder);
+  }
+  else
+    HandleBlockExit(L.getBlock(), Pred);
+}
+
+void GRCoreEngine::HandleBlockExit(CFGBlock * B, ExplodedNode* Pred) {
+
+  if (Stmt* Term = B->getTerminator()) {
+    switch (Term->getStmtClass()) {
+      default:
+        assert(false && "Analysis for this terminator not implemented.");
+        break;
+
+      case Stmt::BinaryOperatorClass: // '&&' and '||'
+        HandleBranch(cast<BinaryOperator>(Term)->getLHS(), Term, B, Pred);
+        return;
+
+      case Stmt::ConditionalOperatorClass:
+        HandleBranch(cast<ConditionalOperator>(Term)->getCond(), Term, B, Pred);
+        return;
+
+        // FIXME: Use constant-folding in CFG construction to simplify this
+        // case.
+
+      case Stmt::ChooseExprClass:
+        HandleBranch(cast<ChooseExpr>(Term)->getCond(), Term, B, Pred);
+        return;
+
+      case Stmt::DoStmtClass:
+        HandleBranch(cast<DoStmt>(Term)->getCond(), Term, B, Pred);
+        return;
+
+      case Stmt::ForStmtClass:
+        HandleBranch(cast<ForStmt>(Term)->getCond(), Term, B, Pred);
+        return;
+
+      case Stmt::ContinueStmtClass:
+      case Stmt::BreakStmtClass:
+      case Stmt::GotoStmtClass:
+        break;
+
+      case Stmt::IfStmtClass:
+        HandleBranch(cast<IfStmt>(Term)->getCond(), Term, B, Pred);
+        return;
+
+      case Stmt::IndirectGotoStmtClass: {
+        // Only 1 successor: the indirect goto dispatch block.
+        assert (B->succ_size() == 1);
+
+        GRIndirectGotoNodeBuilder
+           builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(),
+                   *(B->succ_begin()), this);
+
+        ProcessIndirectGoto(builder);
+        return;
+      }
+
+      case Stmt::ObjCForCollectionStmtClass: {
+        // In the case of ObjCForCollectionStmt, it appears twice in a CFG:
+        //
+        //  (1) inside a basic block, which represents the binding of the
+        //      'element' variable to a value.
+        //  (2) in a terminator, which represents the branch.
+        //
+        // For (1), subengines will bind a value (i.e., 0 or 1) indicating
+        // whether or not collection contains any more elements.  We cannot
+        // just test to see if the element is nil because a container can
+        // contain nil elements.
+        HandleBranch(Term, Term, B, Pred);
+        return;
+      }
+
+      case Stmt::SwitchStmtClass: {
+        GRSwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(),
+                                    this);
+
+        ProcessSwitch(builder);
+        return;
+      }
+
+      case Stmt::WhileStmtClass:
+        HandleBranch(cast<WhileStmt>(Term)->getCond(), Term, B, Pred);
+        return;
+    }
+  }
+
+  assert (B->succ_size() == 1 &&
+          "Blocks with no terminator should have at most 1 successor.");
+
+  GenerateNode(BlockEdge(B, *(B->succ_begin()), Pred->getLocationContext()),
+               Pred->State, Pred);
+}
+
+void GRCoreEngine::HandleBranch(Stmt* Cond, Stmt* Term, CFGBlock * B,
+                                ExplodedNode* Pred) {
+  assert (B->succ_size() == 2);
+
+  GRBranchNodeBuilder Builder(B, *(B->succ_begin()), *(B->succ_begin()+1),
+                              Pred, this);
+
+  ProcessBranch(Cond, Term, Builder);
+}
+
+void GRCoreEngine::HandlePostStmt(const PostStmt& L, CFGBlock* B,
+                                  unsigned StmtIdx, ExplodedNode* Pred) {
+
+  assert (!B->empty());
+
+  if (StmtIdx == B->size())
+    HandleBlockExit(B, Pred);
+  else {
+    GRStmtNodeBuilder Builder(B, StmtIdx, Pred, this,
+                              SubEngine.getStateManager());
+    ProcessStmt((*B)[StmtIdx], Builder);
+  }
+}
+
+/// GenerateNode - Utility method to generate nodes, hook up successors,
+///  and add nodes to the worklist.
+void GRCoreEngine::GenerateNode(const ProgramPoint& Loc,
+                                const GRState* State, ExplodedNode* Pred) {
+
+  bool IsNew;
+  ExplodedNode* Node = G->getNode(Loc, State, &IsNew);
+
+  if (Pred)
+    Node->addPredecessor(Pred, *G);  // Link 'Node' with its predecessor.
+  else {
+    assert (IsNew);
+    G->addRoot(Node);  // 'Node' has no predecessor.  Make it a root.
+  }
+
+  // Only add 'Node' to the worklist if it was freshly generated.
+  if (IsNew) WList->Enqueue(Node);
+}
+
+GRStmtNodeBuilder::GRStmtNodeBuilder(CFGBlock* b, unsigned idx,
+                                     ExplodedNode* N, GRCoreEngine* e,
+                                     GRStateManager &mgr)
+  : Eng(*e), B(*b), Idx(idx), Pred(N), LastNode(N), Mgr(mgr), Auditor(0),
+    PurgingDeadSymbols(false), BuildSinks(false), HasGeneratedNode(false),
+    PointKind(ProgramPoint::PostStmtKind), Tag(0) {
+  Deferred.insert(N);
+  CleanedState = getLastNode()->getState();
+}
+
+GRStmtNodeBuilder::~GRStmtNodeBuilder() {
+  for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I)
+    if (!(*I)->isSink())
+      GenerateAutoTransition(*I);
+}
+
+void GRStmtNodeBuilder::GenerateAutoTransition(ExplodedNode* N) {
+  assert (!N->isSink());
+
+  PostStmt Loc(getStmt(), N->getLocationContext());
+
+  if (Loc == N->getLocation()) {
+    // Note: 'N' should be a fresh node because otherwise it shouldn't be
+    // a member of Deferred.
+    Eng.WList->Enqueue(N, B, Idx+1);
+    return;
+  }
+
+  bool IsNew;
+  ExplodedNode* Succ = Eng.G->getNode(Loc, N->State, &IsNew);
+  Succ->addPredecessor(N, *Eng.G);
+
+  if (IsNew)
+    Eng.WList->Enqueue(Succ, B, Idx+1);
+}
+
+static ProgramPoint GetProgramPoint(const Stmt *S, ProgramPoint::Kind K,
+                                    const LocationContext *LC, const void *tag){
+  switch (K) {
+    default:
+      assert(false && "Unhandled ProgramPoint kind");    
+    case ProgramPoint::PreStmtKind:
+      return PreStmt(S, LC, tag);
+    case ProgramPoint::PostStmtKind:
+      return PostStmt(S, LC, tag);
+    case ProgramPoint::PreLoadKind:
+      return PreLoad(S, LC, tag);
+    case ProgramPoint::PostLoadKind:
+      return PostLoad(S, LC, tag);
+    case ProgramPoint::PreStoreKind:
+      return PreStore(S, LC, tag);
+    case ProgramPoint::PostStoreKind:
+      return PostStore(S, LC, tag);
+    case ProgramPoint::PostLValueKind:
+      return PostLValue(S, LC, tag);
+    case ProgramPoint::PostPurgeDeadSymbolsKind:
+      return PostPurgeDeadSymbols(S, LC, tag);
+  }
+}
+
+ExplodedNode*
+GRStmtNodeBuilder::generateNodeInternal(const Stmt* S, const GRState* state,
+                                        ExplodedNode* Pred,
+                                        ProgramPoint::Kind K,
+                                        const void *tag) {
+  
+  const ProgramPoint &L = GetProgramPoint(S, K, Pred->getLocationContext(),tag);
+  return generateNodeInternal(L, state, Pred);
+}
+
+ExplodedNode*
+GRStmtNodeBuilder::generateNodeInternal(const ProgramPoint &Loc,
+                                        const GRState* State,
+                                        ExplodedNode* Pred) {
+  bool IsNew;
+  ExplodedNode* N = Eng.G->getNode(Loc, State, &IsNew);
+  N->addPredecessor(Pred, *Eng.G);
+  Deferred.erase(Pred);
+
+  if (IsNew) {
+    Deferred.insert(N);
+    LastNode = N;
+    return N;
+  }
+
+  LastNode = NULL;
+  return NULL;
+}
+
+ExplodedNode* GRBranchNodeBuilder::generateNode(const GRState* State,
+                                                bool branch) {
+
+  // If the branch has been marked infeasible we should not generate a node.
+  if (!isFeasible(branch))
+    return NULL;
+
+  bool IsNew;
+
+  ExplodedNode* Succ =
+    Eng.G->getNode(BlockEdge(Src,branch ? DstT:DstF,Pred->getLocationContext()),
+                   State, &IsNew);
+
+  Succ->addPredecessor(Pred, *Eng.G);
+
+  if (branch)
+    GeneratedTrue = true;
+  else
+    GeneratedFalse = true;
+
+  if (IsNew) {
+    Deferred.push_back(Succ);
+    return Succ;
+  }
+
+  return NULL;
+}
+
+GRBranchNodeBuilder::~GRBranchNodeBuilder() {
+  if (!GeneratedTrue) generateNode(Pred->State, true);
+  if (!GeneratedFalse) generateNode(Pred->State, false);
+
+  for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I)
+    if (!(*I)->isSink()) Eng.WList->Enqueue(*I);
+}
+
+
+ExplodedNode*
+GRIndirectGotoNodeBuilder::generateNode(const iterator& I, const GRState* St,
+                                        bool isSink) {
+  bool IsNew;
+
+  ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(),
+                                      Pred->getLocationContext()), St, &IsNew);
+
+  Succ->addPredecessor(Pred, *Eng.G);
+
+  if (IsNew) {
+
+    if (isSink)
+      Succ->markAsSink();
+    else
+      Eng.WList->Enqueue(Succ);
+
+    return Succ;
+  }
+
+  return NULL;
+}
+
+
+ExplodedNode*
+GRSwitchNodeBuilder::generateCaseStmtNode(const iterator& I, const GRState* St){
+
+  bool IsNew;
+
+  ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, I.getBlock(),
+                                       Pred->getLocationContext()), St, &IsNew);
+  Succ->addPredecessor(Pred, *Eng.G);
+
+  if (IsNew) {
+    Eng.WList->Enqueue(Succ);
+    return Succ;
+  }
+
+  return NULL;
+}
+
+
+ExplodedNode*
+GRSwitchNodeBuilder::generateDefaultCaseNode(const GRState* St, bool isSink) {
+
+  // Get the block for the default case.
+  assert (Src->succ_rbegin() != Src->succ_rend());
+  CFGBlock* DefaultBlock = *Src->succ_rbegin();
+
+  bool IsNew;
+
+  ExplodedNode* Succ = Eng.G->getNode(BlockEdge(Src, DefaultBlock,
+                                       Pred->getLocationContext()), St, &IsNew);
+  Succ->addPredecessor(Pred, *Eng.G);
+
+  if (IsNew) {
+    if (isSink)
+      Succ->markAsSink();
+    else
+      Eng.WList->Enqueue(Succ);
+
+    return Succ;
+  }
+
+  return NULL;
+}
+
+GREndPathNodeBuilder::~GREndPathNodeBuilder() {
+  // Auto-generate an EOP node if one has not been generated.
+  if (!HasGeneratedNode) generateNode(Pred->State);
+}
+
+ExplodedNode*
+GREndPathNodeBuilder::generateNode(const GRState* State, const void *tag,
+                                   ExplodedNode* P) {
+  HasGeneratedNode = true;
+  bool IsNew;
+
+  ExplodedNode* Node = Eng.G->getNode(BlockEntrance(&B,
+                               Pred->getLocationContext(), tag), State, &IsNew);
+
+  Node->addPredecessor(P ? P : Pred, *Eng.G);
+
+  if (IsNew) {
+    Eng.G->addEndOfPath(Node);
+    return Node;
+  }
+
+  return NULL;
+}