Vendor import of clang trunk r126079:

http://llvm.org/svn/llvm-project/cfe/trunk@126079

1 files changed, 848 insertions, 0 deletions

diff --git a/lib/StaticAnalyzer/Core/CoreEngine.cpp b/lib/StaticAnalyzer/Core/CoreEngine.cpp
new file mode 100644
index 0000000..070042a
--- /dev/null
+++ b/lib/StaticAnalyzer/Core/CoreEngine.cpp
@@ -0,0 +1,848 @@
+//==- CoreEngine.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/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
+#include "clang/Index/TranslationUnit.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;
+using namespace ento;
+
+// This should be removed in the future.
+namespace clang {
+namespace ento {
+TransferFuncs* MakeCFRefCountTF(ASTContext& Ctx, bool GCEnabled,
+                                  const LangOptions& lopts);
+}
+}
+
+//===----------------------------------------------------------------------===//
+// Worklist classes for exploration of reachable states.
+//===----------------------------------------------------------------------===//
+
+WorkList::Visitor::~Visitor() {}
+
+namespace {
+class DFS : public WorkList {
+  llvm::SmallVector<WorkListUnit,20> Stack;
+public:
+  virtual bool hasWork() const {
+    return !Stack.empty();
+  }
+
+  virtual void enqueue(const WorkListUnit& U) {
+    Stack.push_back(U);
+  }
+
+  virtual WorkListUnit dequeue() {
+    assert (!Stack.empty());
+    const WorkListUnit& U = Stack.back();
+    Stack.pop_back(); // This technically "invalidates" U, but we are fine.
+    return U;
+  }
+  
+  virtual bool visitItemsInWorkList(Visitor &V) {
+    for (llvm::SmallVectorImpl<WorkListUnit>::iterator
+         I = Stack.begin(), E = Stack.end(); I != E; ++I) {
+      if (V.visit(*I))
+        return true;
+    }
+    return false;
+  }
+};
+
+class BFS : public WorkList {
+  std::deque<WorkListUnit> Queue;
+public:
+  virtual bool hasWork() const {
+    return !Queue.empty();
+  }
+
+  virtual void enqueue(const WorkListUnit& U) {
+    Queue.push_front(U);
+  }
+
+  virtual WorkListUnit dequeue() {
+    WorkListUnit U = Queue.front();
+    Queue.pop_front();
+    return U;
+  }
+  
+  virtual bool visitItemsInWorkList(Visitor &V) {
+    for (std::deque<WorkListUnit>::iterator
+         I = Queue.begin(), E = Queue.end(); I != E; ++I) {
+      if (V.visit(*I))
+        return true;
+    }
+    return false;
+  }
+};
+
+} // end anonymous namespace
+
+// Place the dstor for WorkList here because it contains virtual member
+// functions, and we the code for the dstor generated in one compilation unit.
+WorkList::~WorkList() {}
+
+WorkList *WorkList::makeDFS() { return new DFS(); }
+WorkList *WorkList::makeBFS() { return new BFS(); }
+
+namespace {
+  class BFSBlockDFSContents : public WorkList {
+    std::deque<WorkListUnit> Queue;
+    llvm::SmallVector<WorkListUnit,20> Stack;
+  public:
+    virtual bool hasWork() const {
+      return !Queue.empty() || !Stack.empty();
+    }
+
+    virtual void enqueue(const WorkListUnit& U) {
+      if (isa<BlockEntrance>(U.getNode()->getLocation()))
+        Queue.push_front(U);
+      else
+        Stack.push_back(U);
+    }
+
+    virtual WorkListUnit dequeue() {
+      // Process all basic blocks to completion.
+      if (!Stack.empty()) {
+        const WorkListUnit& 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.
+      WorkListUnit U = Queue.front();
+      Queue.pop_front();
+      return U;
+    }
+    virtual bool visitItemsInWorkList(Visitor &V) {
+      for (llvm::SmallVectorImpl<WorkListUnit>::iterator
+           I = Stack.begin(), E = Stack.end(); I != E; ++I) {
+        if (V.visit(*I))
+          return true;
+      }
+      for (std::deque<WorkListUnit>::iterator
+           I = Queue.begin(), E = Queue.end(); I != E; ++I) {
+        if (V.visit(*I))
+          return true;
+      }
+      return false;
+    }
+
+  };
+} // end anonymous namespace
+
+WorkList* WorkList::makeBFSBlockDFSContents() {
+  return new BFSBlockDFSContents();
+}
+
+//===----------------------------------------------------------------------===//
+// Core analysis engine.
+//===----------------------------------------------------------------------===//
+
+/// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps.
+bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps,
+                                   const GRState *InitState) {
+
+  if (G->num_roots() == 0) { // Initialize the analysis by constructing
+    // the root if none exists.
+
+    const 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.
+    const 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());
+
+    if (!InitState)
+      // Generate the root.
+      generateNode(StartLoc, SubEng.getInitialState(L), 0);
+    else
+      generateNode(StartLoc, InitState, 0);
+  }
+
+  // Check if we have a steps limit
+  bool UnlimitedSteps = Steps == 0;
+
+  while (WList->hasWork()) {
+    if (!UnlimitedSteps) {
+      if (Steps == 0)
+        break;
+      --Steps;
+    }
+
+    const WorkListUnit& 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;
+
+      case ProgramPoint::CallEnterKind:
+        HandleCallEnter(cast<CallEnter>(Node->getLocation()), WU.getBlock(), 
+                        WU.getIndex(), Node);
+        break;
+
+      case ProgramPoint::CallExitKind:
+        HandleCallExit(cast<CallExit>(Node->getLocation()), Node);
+        break;
+
+      default:
+        assert(isa<PostStmt>(Node->getLocation()) || 
+               isa<PostInitializer>(Node->getLocation()));
+        HandlePostStmt(WU.getBlock(), WU.getIndex(), Node);
+        break;
+    }
+  }
+
+  SubEng.processEndWorklist(hasWorkRemaining());
+  return WList->hasWork();
+}
+
+void CoreEngine::ExecuteWorkListWithInitialState(const LocationContext *L, 
+                                                   unsigned Steps,
+                                                   const GRState *InitState, 
+                                                   ExplodedNodeSet &Dst) {
+  ExecuteWorkList(L, Steps, InitState);
+  for (llvm::SmallVectorImpl<ExplodedNode*>::iterator I = G->EndNodes.begin(), 
+                                           E = G->EndNodes.end(); I != E; ++I) {
+    Dst.Add(*I);
+  }
+}
+
+void CoreEngine::HandleCallEnter(const CallEnter &L, const CFGBlock *Block,
+                                   unsigned Index, ExplodedNode *Pred) {
+  CallEnterNodeBuilder Builder(*this, Pred, L.getCallExpr(), 
+                                 L.getCalleeContext(), Block, Index);
+  SubEng.processCallEnter(Builder);
+}
+
+void CoreEngine::HandleCallExit(const CallExit &L, ExplodedNode *Pred) {
+  CallExitNodeBuilder Builder(*this, Pred);
+  SubEng.processCallExit(Builder);
+}
+
+void CoreEngine::HandleBlockEdge(const BlockEdge& L, ExplodedNode* Pred) {
+
+  const 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.
+    EndOfFunctionNodeBuilder Builder(Blk, Pred, this);
+    SubEng.processEndOfFunction(Builder);
+
+    // This path is done. Don't enqueue any more nodes.
+    return;
+  }
+
+  // Call into the subengine to process entering the CFGBlock.
+  ExplodedNodeSet dstNodes;
+  BlockEntrance BE(Blk, Pred->getLocationContext());
+  GenericNodeBuilder<BlockEntrance> nodeBuilder(*this, Pred, BE);
+  SubEng.processCFGBlockEntrance(dstNodes, nodeBuilder);
+
+  if (dstNodes.empty()) {
+    if (!nodeBuilder.hasGeneratedNode) {
+      // Auto-generate a node and enqueue it to the worklist.
+      generateNode(BE, Pred->State, Pred);    
+    }
+  }
+  else {
+    for (ExplodedNodeSet::iterator I = dstNodes.begin(), E = dstNodes.end();
+         I != E; ++I) {
+      WList->enqueue(*I);
+    }
+  }
+
+  for (llvm::SmallVectorImpl<ExplodedNode*>::const_iterator
+       I = nodeBuilder.sinks().begin(), E = nodeBuilder.sinks().end();
+       I != E; ++I) {
+    blocksAborted.push_back(std::make_pair(L, *I));
+  }
+}
+
+void CoreEngine::HandleBlockEntrance(const BlockEntrance& L,
+                                       ExplodedNode* Pred) {
+
+  // Increment the block counter.
+  BlockCounter Counter = WList->getBlockCounter();
+  Counter = BCounterFactory.IncrementCount(Counter, 
+                             Pred->getLocationContext()->getCurrentStackFrame(),
+                                           L.getBlock()->getBlockID());
+  WList->setBlockCounter(Counter);
+
+  // Process the entrance of the block.
+  if (CFGElement E = L.getFirstElement()) {
+    StmtNodeBuilder Builder(L.getBlock(), 0, Pred, this,
+                              SubEng.getStateManager());
+    SubEng.processCFGElement(E, Builder);
+  }
+  else
+    HandleBlockExit(L.getBlock(), Pred);
+}
+
+void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode* Pred) {
+
+  if (const 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::BinaryConditionalOperatorClass:
+      case Stmt::ConditionalOperatorClass:
+        HandleBranch(cast<AbstractConditionalOperator>(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);
+
+        IndirectGotoNodeBuilder
+           builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(),
+                   *(B->succ_begin()), this);
+
+        SubEng.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: {
+        SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(),
+                                    this);
+
+        SubEng.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 CoreEngine::HandleBranch(const Stmt* Cond, const Stmt* Term, 
+                                const CFGBlock * B, ExplodedNode* Pred) {
+  assert(B->succ_size() == 2);
+  BranchNodeBuilder Builder(B, *(B->succ_begin()), *(B->succ_begin()+1),
+                            Pred, this);
+  SubEng.processBranch(Cond, Term, Builder);
+}
+
+void CoreEngine::HandlePostStmt(const CFGBlock* B, unsigned StmtIdx, 
+                                  ExplodedNode* Pred) {
+  assert (!B->empty());
+
+  if (StmtIdx == B->size())
+    HandleBlockExit(B, Pred);
+  else {
+    StmtNodeBuilder Builder(B, StmtIdx, Pred, this,
+                              SubEng.getStateManager());
+    SubEng.processCFGElement((*B)[StmtIdx], Builder);
+  }
+}
+
+/// generateNode - Utility method to generate nodes, hook up successors,
+///  and add nodes to the worklist.
+void CoreEngine::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);
+}
+
+ExplodedNode *
+GenericNodeBuilderImpl::generateNodeImpl(const GRState *state,
+                                         ExplodedNode *pred,
+                                         ProgramPoint programPoint,
+                                         bool asSink) {
+  
+  hasGeneratedNode = true;
+  bool isNew;
+  ExplodedNode *node = engine.getGraph().getNode(programPoint, state, &isNew);
+  if (pred)
+    node->addPredecessor(pred, engine.getGraph());
+  if (isNew) {
+    if (asSink) {
+      node->markAsSink();
+      sinksGenerated.push_back(node);
+    }
+    return node;
+  }
+  return 0;
+}
+
+StmtNodeBuilder::StmtNodeBuilder(const CFGBlock* b, unsigned idx,
+                                     ExplodedNode* N, CoreEngine* e,
+                                     GRStateManager &mgr)
+  : Eng(*e), B(*b), Idx(idx), Pred(N), Mgr(mgr),
+    PurgingDeadSymbols(false), BuildSinks(false), hasGeneratedNode(false),
+    PointKind(ProgramPoint::PostStmtKind), Tag(0) {
+  Deferred.insert(N);
+  CleanedState = Pred->getState();
+}
+
+StmtNodeBuilder::~StmtNodeBuilder() {
+  for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I)
+    if (!(*I)->isSink())
+      GenerateAutoTransition(*I);
+}
+
+void StmtNodeBuilder::GenerateAutoTransition(ExplodedNode* N) {
+  assert (!N->isSink());
+
+  // Check if this node entered a callee.
+  if (isa<CallEnter>(N->getLocation())) {
+    // Still use the index of the CallExpr. It's needed to create the callee
+    // StackFrameContext.
+    Eng.WList->enqueue(N, &B, Idx);
+    return;
+  }
+
+  // Do not create extra nodes. Move to the next CFG element.
+  if (isa<PostInitializer>(N->getLocation())) {
+    Eng.WList->enqueue(N, &B, Idx+1);
+    return;
+  }
+
+  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);
+}
+
+ExplodedNode* StmtNodeBuilder::MakeNode(ExplodedNodeSet& Dst, const Stmt* S, 
+                                          ExplodedNode* Pred, const GRState* St,
+                                          ProgramPoint::Kind K) {
+
+  ExplodedNode* N = generateNode(S, St, Pred, K);
+
+  if (N) {
+    if (BuildSinks)
+      N->markAsSink();
+    else
+      Dst.Add(N);
+  }
+  
+  return N;
+}
+
+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*
+StmtNodeBuilder::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*
+StmtNodeBuilder::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);
+    return N;
+  }
+
+  return NULL;
+}
+
+ExplodedNode* BranchNodeBuilder::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;
+}
+
+BranchNodeBuilder::~BranchNodeBuilder() {
+  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*
+IndirectGotoNodeBuilder::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*
+SwitchNodeBuilder::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*
+SwitchNodeBuilder::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;
+}
+
+EndOfFunctionNodeBuilder::~EndOfFunctionNodeBuilder() {
+  // Auto-generate an EOP node if one has not been generated.
+  if (!hasGeneratedNode) {
+    // If we are in an inlined call, generate CallExit node.
+    if (Pred->getLocationContext()->getParent())
+      GenerateCallExitNode(Pred->State);
+    else
+      generateNode(Pred->State);
+  }
+}
+
+ExplodedNode*
+EndOfFunctionNodeBuilder::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;
+}
+
+void EndOfFunctionNodeBuilder::GenerateCallExitNode(const GRState *state) {
+  hasGeneratedNode = true;
+  // Create a CallExit node and enqueue it.
+  const StackFrameContext *LocCtx
+                         = cast<StackFrameContext>(Pred->getLocationContext());
+  const Stmt *CE = LocCtx->getCallSite();
+
+  // Use the the callee location context.
+  CallExit Loc(CE, LocCtx);
+
+  bool isNew;
+  ExplodedNode *Node = Eng.G->getNode(Loc, state, &isNew);
+  Node->addPredecessor(Pred, *Eng.G);
+
+  if (isNew)
+    Eng.WList->enqueue(Node);
+}
+                                                
+
+void CallEnterNodeBuilder::generateNode(const GRState *state) {
+  // Check if the callee is in the same translation unit.
+  if (CalleeCtx->getTranslationUnit() != 
+      Pred->getLocationContext()->getTranslationUnit()) {
+    // Create a new engine. We must be careful that the new engine should not
+    // reference data structures owned by the old engine.
+
+    AnalysisManager &OldMgr = Eng.SubEng.getAnalysisManager();
+    
+    // Get the callee's translation unit.
+    idx::TranslationUnit *TU = CalleeCtx->getTranslationUnit();
+
+    // Create a new AnalysisManager with components of the callee's
+    // TranslationUnit.
+    // The Diagnostic is actually shared when we create ASTUnits from AST files.
+    AnalysisManager AMgr(TU->getASTContext(), TU->getDiagnostic(), 
+                         OldMgr.getLangOptions(), 
+                         OldMgr.getPathDiagnosticClient(),
+                         OldMgr.getStoreManagerCreator(),
+                         OldMgr.getConstraintManagerCreator(),
+                         OldMgr.getCheckerManager(),
+                         OldMgr.getIndexer(),
+                         OldMgr.getMaxNodes(), OldMgr.getMaxVisit(),
+                         OldMgr.shouldVisualizeGraphviz(),
+                         OldMgr.shouldVisualizeUbigraph(),
+                         OldMgr.shouldPurgeDead(),
+                         OldMgr.shouldEagerlyAssume(),
+                         OldMgr.shouldTrimGraph(),
+                         OldMgr.shouldInlineCall(),
+                     OldMgr.getAnalysisContextManager().getUseUnoptimizedCFG(),
+                     OldMgr.getAnalysisContextManager().getAddImplicitDtors(),
+                     OldMgr.getAnalysisContextManager().getAddInitializers(),
+                     OldMgr.shouldEagerlyTrimExplodedGraph());
+    llvm::OwningPtr<TransferFuncs> TF(MakeCFRefCountTF(AMgr.getASTContext(),
+                                                         /* GCEnabled */ false,
+                                                        AMgr.getLangOptions()));
+    // Create the new engine.
+    ExprEngine NewEng(AMgr, TF.take());
+
+    // Create the new LocationContext.
+    AnalysisContext *NewAnaCtx = AMgr.getAnalysisContext(CalleeCtx->getDecl(), 
+                                               CalleeCtx->getTranslationUnit());
+    const StackFrameContext *OldLocCtx = CalleeCtx;
+    const StackFrameContext *NewLocCtx = AMgr.getStackFrame(NewAnaCtx, 
+                                               OldLocCtx->getParent(),
+                                               OldLocCtx->getCallSite(),
+                                               OldLocCtx->getCallSiteBlock(), 
+                                               OldLocCtx->getIndex());
+
+    // Now create an initial state for the new engine.
+    const GRState *NewState = NewEng.getStateManager().MarshalState(state,
+                                                                    NewLocCtx);
+    ExplodedNodeSet ReturnNodes;
+    NewEng.ExecuteWorkListWithInitialState(NewLocCtx, AMgr.getMaxNodes(), 
+                                           NewState, ReturnNodes);
+    return;
+  }
+
+  // Get the callee entry block.
+  const CFGBlock *Entry = &(CalleeCtx->getCFG()->getEntry());
+  assert(Entry->empty());
+  assert(Entry->succ_size() == 1);
+
+  // Get the solitary successor.
+  const CFGBlock *SuccB = *(Entry->succ_begin());
+
+  // Construct an edge representing the starting location in the callee.
+  BlockEdge Loc(Entry, SuccB, CalleeCtx);
+
+  bool isNew;
+  ExplodedNode *Node = Eng.G->getNode(Loc, state, &isNew);
+  Node->addPredecessor(const_cast<ExplodedNode*>(Pred), *Eng.G);
+
+  if (isNew)
+    Eng.WList->enqueue(Node);
+}
+
+void CallExitNodeBuilder::generateNode(const GRState *state) {
+  // Get the callee's location context.
+  const StackFrameContext *LocCtx 
+                         = cast<StackFrameContext>(Pred->getLocationContext());
+  // When exiting an implicit automatic obj dtor call, the callsite is the Stmt
+  // that triggers the dtor.
+  PostStmt Loc(LocCtx->getCallSite(), LocCtx->getParent());
+  bool isNew;
+  ExplodedNode *Node = Eng.G->getNode(Loc, state, &isNew);
+  Node->addPredecessor(const_cast<ExplodedNode*>(Pred), *Eng.G);
+  if (isNew)
+    Eng.WList->enqueue(Node, LocCtx->getCallSiteBlock(),
+                       LocCtx->getIndex() + 1);
+}