[analyzer] Overhaul how the static analyzer expects CFGs by forcing CFGs to be linearized only when used by the static analyzer. This required a rewrite of LiveVariables, and exposed a ton of subtle bugs.

The motivation of this large change is to drastically simplify the logic in ExprEngine going forward.

Some fallout is that the output of some BugReporterVisitors is not as accurate as before; those will
need to be fixed over time.  There is also some possible performance regression as RemoveDeadBindings
will be called frequently; this can also be improved over time.

llvm-svn: 136419

1 files changed, 401 insertions, 307 deletions

diff --git a/clang/lib/Analysis/LiveVariables.cpp b/clang/lib/Analysis/LiveVariables.cpp
index b7ae141781e..f81019e2c9f 100644
--- a/clang/lib/Analysis/LiveVariables.cpp
+++ b/clang/lib/Analysis/LiveVariables.cpp
@@ -1,392 +1,486 @@
-//=- LiveVariables.cpp - Live Variable Analysis for Source CFGs -*- C++ --*-==//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file implements Live Variables analysis for source-level CFGs.
-//
-//===----------------------------------------------------------------------===//
-
 #include "clang/Analysis/Analyses/LiveVariables.h"
-#include "clang/Basic/SourceManager.h"
-#include "clang/AST/ASTContext.h"
-#include "clang/AST/Expr.h"
+#include "clang/AST/Stmt.h"
 #include "clang/Analysis/CFG.h"
-#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h"
-#include "clang/Analysis/FlowSensitive/DataflowSolver.h"
-#include "clang/Analysis/Support/SaveAndRestore.h"
 #include "clang/Analysis/AnalysisContext.h"
-#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/Support/raw_ostream.h"
+#include "clang/AST/StmtVisitor.h"
+
+#include <deque>
+#include <algorithm>
+#include <vector>
 
 using namespace clang;
 
-//===----------------------------------------------------------------------===//
-// Useful constants.
-//===----------------------------------------------------------------------===//
+namespace {
+  class LiveVariablesImpl {
+  public:  
+    AnalysisContext &analysisContext;
+    std::vector<LiveVariables::LivenessValues> cfgBlockValues;
+    llvm::ImmutableSet<const Stmt *>::Factory SSetFact;
+    llvm::ImmutableSet<const VarDecl *>::Factory DSetFact;
+    llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness;
+    llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness;
+    llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness;
+    llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment;
+    const bool killAtAssign;
+    
+    LiveVariables::LivenessValues
+    merge(LiveVariables::LivenessValues valsA,
+          LiveVariables::LivenessValues valsB);
+        
+    LiveVariables::LivenessValues runOnBlock(const CFGBlock *block,
+                                             LiveVariables::LivenessValues val,
+                                             LiveVariables::Observer *obs = 0);
+
+    void dumpBlockLiveness(const SourceManager& M);
+
+    LiveVariablesImpl(AnalysisContext &ac, bool KillAtAssign)
+      : analysisContext(ac), killAtAssign(KillAtAssign) {}
+  };
+}
 
-static const bool Alive = true;
-static const bool Dead = false;
+static LiveVariablesImpl &getImpl(void* x) {
+  return *((LiveVariablesImpl *) x);
+}
 
 //===----------------------------------------------------------------------===//
-// Dataflow initialization logic.
+// Operations and queries on LivenessValues.
 //===----------------------------------------------------------------------===//
 
-namespace {
-class RegisterDecls
-  : public CFGRecStmtDeclVisitor<RegisterDecls> {
-
-  LiveVariables::AnalysisDataTy& AD;
-
-  typedef SmallVector<VarDecl*, 20> AlwaysLiveTy;
-  AlwaysLiveTy AlwaysLive;
+bool LiveVariables::LivenessValues::isLive(const Stmt *S) const {
+  return liveStmts.contains(S);
+}
 
+bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const {
+  return liveDecls.contains(D);
+}
 
-public:
-  RegisterDecls(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
+namespace {
+  template <typename SET>
+  SET mergeSets(typename SET::Factory &F, SET A, SET B) {
+    for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) {
+      A = F.add(A, *it);
+    }
+    return A;
+  }
+}
 
-  ~RegisterDecls() {
+LiveVariables::LivenessValues
+LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA,
+                         LiveVariables::LivenessValues valsB) {  
+  return LiveVariables::LivenessValues(mergeSets(SSetFact, valsA.liveStmts, valsB.liveStmts),
+                        mergeSets(DSetFact, valsA.liveDecls, valsB.liveDecls));
+}
 
-    AD.AlwaysLive.resetValues(AD);
+bool LiveVariables::LivenessValues::equals(const LivenessValues &V) const {
+  return liveStmts == V.liveStmts && liveDecls == V.liveDecls;
+}
 
-    for (AlwaysLiveTy::iterator I = AlwaysLive.begin(), E = AlwaysLive.end();
-         I != E; ++ I)
-      AD.AlwaysLive(*I, AD) = Alive;
-  }
+//===----------------------------------------------------------------------===//
+// Query methods.
+//===----------------------------------------------------------------------===//
 
-  void VisitImplicitParamDecl(ImplicitParamDecl* IPD) {
-    // Register the VarDecl for tracking.
-    AD.Register(IPD);
-  }
+static bool isAlwaysAlive(const VarDecl *D) {
+  return D->hasGlobalStorage();
+}
 
-  void VisitVarDecl(VarDecl* VD) {
-    // Register the VarDecl for tracking.
-    AD.Register(VD);
+bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) {
+  return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D);
+}
 
-    // Does the variable have global storage?  If so, it is always live.
-    if (VD->hasGlobalStorage())
-      AlwaysLive.push_back(VD);
-  }
+bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) {
+  return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D);
+}
 
-  CFG& getCFG() { return AD.getCFG(); }
-};
-} // end anonymous namespace
-
-LiveVariables::LiveVariables(AnalysisContext &AC, bool killAtAssign) {
-  // Register all referenced VarDecls.
-  CFG &cfg = *AC.getCFG();
-  getAnalysisData().setCFG(cfg);
-  getAnalysisData().setContext(AC.getASTContext());
-  getAnalysisData().AC = &AC;
-  getAnalysisData().killAtAssign = killAtAssign;
-
-  RegisterDecls R(getAnalysisData());
-  cfg.VisitBlockStmts(R);
-
-  // Register all parameters even if they didn't occur in the function body.
-  if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(AC.getDecl()))
-    for (FunctionDecl::param_const_iterator PI = FD->param_begin(), 
-           PE = FD->param_end(); PI != PE; ++PI)
-      getAnalysisData().Register(*PI);
+bool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) {
+  return getImpl(impl).stmtsToLiveness[Loc].isLive(S);
 }
 
 //===----------------------------------------------------------------------===//
-// Transfer functions.
+// Dataflow computation.
 //===----------------------------------------------------------------------===//
 
 namespace {
-
-class TransferFuncs : public CFGRecStmtVisitor<TransferFuncs>{
-  LiveVariables::AnalysisDataTy& AD;
-  LiveVariables::ValTy LiveState;
-  const CFGBlock *currentBlock;
+class Worklist {
+  llvm::BitVector isBlockEnqueued;
+  std::deque<const CFGBlock *> workListContents;
 public:
-  TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad), currentBlock(0) {}
-
-  LiveVariables::ValTy& getVal() { return LiveState; }
-  CFG& getCFG() { return AD.getCFG(); }
-
-  void VisitDeclRefExpr(DeclRefExpr* DR);
-  void VisitBinaryOperator(BinaryOperator* B);
-  void VisitBlockExpr(BlockExpr *B);
-  void VisitAssign(BinaryOperator* B);
-  void VisitDeclStmt(DeclStmt* DS);
-  void BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S);
-  void VisitUnaryOperator(UnaryOperator* U);
-  void Visit(Stmt *S);
-  void VisitTerminator(CFGBlock* B);
+  Worklist(CFG &cfg) : isBlockEnqueued(cfg.getNumBlockIDs()) {}
   
-  /// VisitConditionVariableInit - Handle the initialization of condition
-  ///  variables at branches.  Valid statements include IfStmt, ForStmt,
-  ///  WhileStmt, and SwitchStmt.
-  void VisitConditionVariableInit(Stmt *S);
-
-  void SetTopValue(LiveVariables::ValTy& V) {
-    V = AD.AlwaysLive;
+  bool empty() const { return workListContents.empty(); }
+  
+  const CFGBlock *getNextItem() {
+    const CFGBlock *block = workListContents.front();
+    workListContents.pop_front();
+    isBlockEnqueued[block->getBlockID()] = false;
+    return block;
   }
   
-  void setCurrentBlock(const CFGBlock *block) {
-    currentBlock = block;
+  void enqueueBlock(const CFGBlock *block) {
+    if (!isBlockEnqueued[block->getBlockID()]) {
+      isBlockEnqueued[block->getBlockID()] = true;
+      workListContents.push_back(block);
+    }
   }
 };
+  
+class TransferFunctions : public StmtVisitor<TransferFunctions> {
+  LiveVariablesImpl &LV;
+  LiveVariables::LivenessValues &val;
+  LiveVariables::Observer *observer;
+  const CFGBlock *currentBlock;
+public:
+  TransferFunctions(LiveVariablesImpl &im,
+                    LiveVariables::LivenessValues &Val,
+                    LiveVariables::Observer *Observer,
+                    const CFGBlock *CurrentBlock)
+  : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {}
+
+  void VisitBinaryOperator(BinaryOperator *BO);
+  void VisitBlockExpr(BlockExpr *BE);
+  void VisitDeclRefExpr(DeclRefExpr *DR);  
+  void VisitDeclStmt(DeclStmt *DS);
+  void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS);
+  void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE);
+  void VisitUnaryOperator(UnaryOperator *UO);
+  void Visit(Stmt *S);
+};
+}
 
-void TransferFuncs::Visit(Stmt *S) {
-
-  if (S == getCurrentBlkStmt()) {
-
-    if (AD.Observer)
-      AD.Observer->ObserveStmt(S, currentBlock, AD, LiveState);
-
-    if (getCFG().isBlkExpr(S))
-      LiveState(S, AD) = Dead;
-
-    StmtVisitor<TransferFuncs,void>::Visit(S);
+void TransferFunctions::Visit(Stmt *S) {
+  if (observer)
+    observer->observeStmt(S, currentBlock, val);
+  
+  StmtVisitor<TransferFunctions>::Visit(S);
+  
+  if (isa<Expr>(S)) {
+    val.liveStmts = LV.SSetFact.remove(val.liveStmts, S);
   }
-  else if (!getCFG().isBlkExpr(S)) {
-
-    if (AD.Observer)
-      AD.Observer->ObserveStmt(S, currentBlock, AD, LiveState);
 
-    StmtVisitor<TransferFuncs,void>::Visit(S);
-
-  }
-  else {
-    // For block-level expressions, mark that they are live.
-    LiveState(S, AD) = Alive;
+  // Mark all children expressions live.
+  
+  switch (S->getStmtClass()) {
+    default:
+      break;
+    case Stmt::StmtExprClass: {
+      // For statement expressions, look through the compound statement.
+      S = cast<StmtExpr>(S)->getSubStmt();
+      break;
+    }
+    case Stmt::CXXMemberCallExprClass: {
+      // Include the implicit "this" pointer as being live.
+      CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S);
+      val.liveStmts =
+        LV.SSetFact.add(val.liveStmts,
+                        CE->getImplicitObjectArgument()->IgnoreParens());
+      break;
+    }
+    // FIXME: These cases eventually shouldn't be needed.
+    case Stmt::ExprWithCleanupsClass: {
+      S = cast<ExprWithCleanups>(S)->getSubExpr();
+      break;
+    }
+    case Stmt::CXXBindTemporaryExprClass: {
+      S = cast<CXXBindTemporaryExpr>(S)->getSubExpr();
+      break;
+    }
+    case Stmt::MaterializeTemporaryExprClass: {
+      S = cast<MaterializeTemporaryExpr>(S)->GetTemporaryExpr();
+      break;
+    }
   }
-}
   
-void TransferFuncs::VisitConditionVariableInit(Stmt *S) {
-  assert(!getCFG().isBlkExpr(S));
-  CFGRecStmtVisitor<TransferFuncs>::VisitConditionVariableInit(S);
+  for (Stmt::child_iterator it = S->child_begin(), ei = S->child_end();
+       it != ei; ++it) {
+    if (Stmt *child = *it) {
+      if (Expr *Ex = dyn_cast<Expr>(child))
+        child = Ex->IgnoreParens();
+               
+      val.liveStmts = LV.SSetFact.add(val.liveStmts, child);
+    }
+  }
 }
 
-void TransferFuncs::VisitTerminator(CFGBlock* B) {
-
-  const Stmt* E = B->getTerminatorCondition();
-
-  if (!E)
-    return;
-
-  assert (getCFG().isBlkExpr(E));
-  LiveState(E, AD) = Alive;
+void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
+  if (B->isAssignmentOp()) {
+    if (!LV.killAtAssign)
+      return;
+    
+    // Assigning to a variable?
+    Expr *LHS = B->getLHS()->IgnoreParens();
+    
+    if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS))
+      if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
+        // Assignments to references don't kill the ref's address
+        if (VD->getType()->isReferenceType())
+          return;
+
+        if (!isAlwaysAlive(VD)) {
+          // The variable is now dead.
+          val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
+        }
+
+        if (observer)
+          observer->observerKill(DR);
+      }
+  }
 }
 
-void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
-  if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl()))
-    LiveState(V, AD) = Alive;
-}
-  
-void TransferFuncs::VisitBlockExpr(BlockExpr *BE) {
+void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
   AnalysisContext::referenced_decls_iterator I, E;
-  llvm::tie(I, E) = AD.AC->getReferencedBlockVars(BE->getBlockDecl());
+  llvm::tie(I, E) =
+    LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl());
   for ( ; I != E ; ++I) {
-    DeclBitVector_Types::Idx i = AD.getIdx(*I);
-    if (i.isValid())
-      LiveState.getBit(i) = Alive;
+    const VarDecl *VD = *I;
+    if (isAlwaysAlive(VD))
+      continue;
+    val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
   }
 }
 
-void TransferFuncs::VisitBinaryOperator(BinaryOperator* B) {
-  if (B->isAssignmentOp()) VisitAssign(B);
-  else VisitStmt(B);
+void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {
+  if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl()))
+    if (!isAlwaysAlive(D) && LV.inAssignment.find(DR) == LV.inAssignment.end())
+      val.liveDecls = LV.DSetFact.add(val.liveDecls, D);
 }
 
-void
-TransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) {
-
-  // This is a block-level expression.  Its value is 'dead' before this point.
-  LiveState(S, AD) = Dead;
-
-  // This represents a 'use' of the collection.
-  Visit(S->getCollection());
+void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
+  for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end();
+       DI != DE; ++DI)
+    if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) {
+      if (!isAlwaysAlive(VD))
+        val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
+    }
+}
 
-  // This represents a 'kill' for the variable.
-  Stmt* Element = S->getElement();
-  DeclRefExpr* DR = 0;
-  VarDecl* VD = 0;
+void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {
+  // Kill the iteration variable.
+  DeclRefExpr *DR = 0;
+  const VarDecl *VD = 0;
 
-  if (DeclStmt* DS = dyn_cast<DeclStmt>(Element))
+  Stmt *element = OS->getElement();
+  if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) {
     VD = cast<VarDecl>(DS->getSingleDecl());
-  else {
-    Expr* ElemExpr = cast<Expr>(Element)->IgnoreParens();
-    if ((DR = dyn_cast<DeclRefExpr>(ElemExpr)))
-      VD = cast<VarDecl>(DR->getDecl());
-    else {
-      Visit(ElemExpr);
-      return;
-    }
   }
-
+  else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) {
+    VD = cast<VarDecl>(DR->getDecl());
+  }
+  
   if (VD) {
-    LiveState(VD, AD) = Dead;
-    if (AD.Observer && DR) { AD.Observer->ObserverKill(DR); }
+    val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
+    if (observer && DR)
+      observer->observerKill(DR);
   }
 }
 
+void TransferFunctions::
+VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)
+{
+  // While sizeof(var) doesn't technically extend the liveness of 'var', it
+  // does extent the liveness of metadata if 'var' is a VariableArrayType.
+  // We handle that special case here.
+  if (UE->getKind() != UETT_SizeOf || UE->isArgumentType())
+    return;
+
+  const DeclRefExpr *DR =
+    dyn_cast<DeclRefExpr>(UE->getArgumentExpr()->IgnoreParens());
+  
+  if (!DR)
+    return;
+  
+  const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
 
-void TransferFuncs::VisitUnaryOperator(UnaryOperator* U) {
-  Expr *E = U->getSubExpr();
+  if (VD && VD->getType()->isVariableArrayType())
+    val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
+}
 
-  switch (U->getOpcode()) {
+void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) {
+  // Treat ++/-- as a kill.
+  // Note we don't actually have to do anything if we don't have an observer,
+  // since a ++/-- acts as both a kill and a "use".
+  if (!observer)
+    return;
+  
+  switch (UO->getOpcode()) {
+  default:
+    return;
   case UO_PostInc:
-  case UO_PostDec:
+  case UO_PostDec:    
   case UO_PreInc:
   case UO_PreDec:
-    // Walk through the subexpressions, blasting through ParenExprs
-    // until we either find a DeclRefExpr or some non-DeclRefExpr
-    // expression.
-    if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParens()))
-      if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) {
-        // Treat the --/++ operator as a kill.
-        if (AD.Observer) { AD.Observer->ObserverKill(DR); }
-        LiveState(VD, AD) = Alive;
-        return VisitDeclRefExpr(DR);
-      }
-
-    // Fall-through.
-
-  default:
-    return Visit(E);
-  }
-}
-
-void TransferFuncs::VisitAssign(BinaryOperator* B) {
-  Expr* LHS = B->getLHS();
-
-  // Assigning to a variable?
-  if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParens())) {
-    // Assignments to references don't kill the ref's address
-    if (DR->getDecl()->getType()->isReferenceType()) {
-      VisitDeclRefExpr(DR);
-    } else {
-      if (AD.killAtAssign) {
-        // Update liveness inforamtion.
-        unsigned bit = AD.getIdx(DR->getDecl());
-        LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit);
-
-        if (AD.Observer) { AD.Observer->ObserverKill(DR); }
-      }
-      // Handle things like +=, etc., which also generate "uses"
-      // of a variable.  Do this just by visiting the subexpression.
-      if (B->getOpcode() != BO_Assign)
-        VisitDeclRefExpr(DR);
-    }
+    break;
   }
-  else // Not assigning to a variable.  Process LHS as usual.
-    Visit(LHS);
-
-  Visit(B->getRHS());
-}
-
-void TransferFuncs::VisitDeclStmt(DeclStmt* DS) {
-  // Declarations effectively "kill" a variable since they cannot
-  // possibly be live before they are declared.
-  for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end();
-       DI != DE; ++DI)
-    if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) {
-      // Update liveness information by killing the VarDecl.
-      unsigned bit = AD.getIdx(VD);
-      LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit);
-
-      // The initializer is evaluated after the variable comes into scope, but
-      // before the DeclStmt (which binds the value to the variable).
-      // Since this is a reverse dataflow analysis, we must evaluate the
-      // transfer function for this expression after the DeclStmt.  If the
-      // initializer references the variable (which is bad) then we extend
-      // its liveness.
-      if (Expr* Init = VD->getInit())
-        Visit(Init);
-
-      if (const VariableArrayType* VT =
-            AD.getContext().getAsVariableArrayType(VD->getType())) {
-        StmtIterator I(const_cast<VariableArrayType*>(VT));
-        StmtIterator E;
-        for (; I != E; ++I) Visit(*I);
-      }
+  
+  if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens()))
+    if (isa<VarDecl>(DR->getDecl())) {
+      // Treat ++/-- as a kill.
+      observer->observerKill(DR);
     }
 }
 
-} // end anonymous namespace
-
-//===----------------------------------------------------------------------===//
-// Merge operator: if something is live on any successor block, it is live
-//  in the current block (a set union).
-//===----------------------------------------------------------------------===//
+LiveVariables::LivenessValues
+LiveVariablesImpl::runOnBlock(const CFGBlock *block,
+                              LiveVariables::LivenessValues val,
+                              LiveVariables::Observer *obs) {
 
-namespace {
-  typedef StmtDeclBitVector_Types::Union Merge;
-  typedef DataflowSolver<LiveVariables, TransferFuncs, Merge> Solver;
-} // end anonymous namespace
-
-//===----------------------------------------------------------------------===//
-// External interface to run Liveness analysis.
-//===----------------------------------------------------------------------===//
-
-void LiveVariables::runOnCFG(CFG& cfg) {
-  Solver S(*this);
-  S.runOnCFG(cfg);
+  TransferFunctions TF(*this, val, obs, block);
+  
+  // Visit the terminator (if any).
+  if (const Stmt *term = block->getTerminator())
+    TF.Visit(const_cast<Stmt*>(term));
+  
+  // Apply the transfer function for all Stmts in the block.
+  for (CFGBlock::const_reverse_iterator it = block->rbegin(),
+       ei = block->rend(); it != ei; ++it) {
+    const CFGElement &elem = *it;
+    if (!isa<CFGStmt>(elem))
+      continue;
+    
+    const Stmt *S = cast<CFGStmt>(elem).getStmt();
+    TF.Visit(const_cast<Stmt*>(S));
+    stmtsToLiveness[S] = val;
+  }
+  return val;
 }
 
-void LiveVariables::runOnAllBlocks(const CFG& cfg,
-                                   LiveVariables::ObserverTy* Obs,
-                                   bool recordStmtValues) {
-  Solver S(*this);
-  SaveAndRestore<LiveVariables::ObserverTy*> SRObs(getAnalysisData().Observer,
-                                                   Obs);
-  S.runOnAllBlocks(cfg, recordStmtValues);
+void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) {
+  const CFG *cfg = getImpl(impl).analysisContext.getCFG();
+  for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it)
+    getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs);    
 }
 
-//===----------------------------------------------------------------------===//
-// liveness queries
-//
+LiveVariables::LiveVariables(void *im) : impl(im) {} 
 
-bool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const {
-  DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
-  return i.isValid() ? getBlockData(B).getBit(i) : false;
+LiveVariables::~LiveVariables() {
+  delete (LiveVariablesImpl*) impl;
 }
 
-bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const {
-  DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
-  return i.isValid() ? Live.getBit(i) : false;
+LiveVariables *
+LiveVariables::computeLiveness(AnalysisContext &AC,
+                                 bool killAtAssign) {
+
+  // No CFG?  Bail out.
+  CFG *cfg = AC.getCFG();
+  if (!cfg)
+    return 0;
+
+  LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign);
+
+  // Construct the dataflow worklist.  Enqueue the exit block as the
+  // start of the analysis.
+  Worklist worklist(*cfg);
+  llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());
+
+  // FIXME: we should enqueue using post order.
+  for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) {
+    const CFGBlock *block = *it;
+    worklist.enqueueBlock(block);
+    
+    // FIXME: Scan for DeclRefExprs using in the LHS of an assignment.
+    // We need to do this because we lack context in the reverse analysis
+    // to determine if a DeclRefExpr appears in such a context, and thus
+    // doesn't constitute a "use".
+    if (killAtAssign)
+      for (CFGBlock::const_iterator bi = block->begin(), be = block->end();
+           bi != be; ++bi) {
+        if (const CFGStmt *cs = bi->getAs<CFGStmt>()) {
+          if (BinaryOperator *BO = dyn_cast<BinaryOperator>(cs->getStmt())) {
+            if (BO->getOpcode() == BO_Assign) {
+              if (const DeclRefExpr *DR =
+                    dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) {
+                LV->inAssignment[DR] = 1;
+              }
+            }
+          }
+        }
+      }
+  }
+  
+  while (!worklist.empty()) {
+    // Dequeue blocks in FIFO order.
+    const CFGBlock *block = worklist.getNextItem();
+    
+    // Determine if the block's end value has changed.  If not, we
+    // have nothing left to do for this block.
+    LivenessValues &prevVal = LV->blocksEndToLiveness[block];
+    
+    // Merge the values of all successor blocks.
+    LivenessValues val;
+    for (CFGBlock::const_succ_iterator it = block->succ_begin(),
+                                       ei = block->succ_end(); it != ei; ++it) {
+      if (const CFGBlock *succ = *it)      
+        val = LV->merge(val, LV->blocksBeginToLiveness[succ]);
+    }
+    
+    if (!everAnalyzedBlock[block->getBlockID()])
+      everAnalyzedBlock[block->getBlockID()] = true;
+    else if (prevVal.equals(val))
+      continue;
+
+    prevVal = val;
+    
+    // Update the dataflow value for the start of this block.
+    LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
+    
+    // Enqueue the value to the predecessors.
+    for (CFGBlock::const_pred_iterator it = block->pred_begin(),
+                                       ei = block->pred_end(); it != ei; ++it)
+    {
+      if (const CFGBlock *pred = *it)
+        worklist.enqueueBlock(pred);
+    }    
+  }
+  
+  return new LiveVariables(LV);
 }
 
-bool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const {
-  return getStmtData(Loc)(StmtVal,getAnalysisData());
+bool compare_entries(const CFGBlock *A, const CFGBlock *B) {
+  return A->getBlockID() < B->getBlockID();
+}
+bool compare_vd_entries(const Decl *A, const Decl *B) {
+  SourceLocation ALoc = A->getLocStart();
+  SourceLocation BLoc = B->getLocStart();
+  return ALoc.getRawEncoding() < BLoc.getRawEncoding();
 }
 
-bool LiveVariables::isLive(const Stmt* Loc, const VarDecl* D) const {
-  return getStmtData(Loc)(D,getAnalysisData());
+void LiveVariables::dumpBlockLiveness(const SourceManager &M) {
+  getImpl(impl).dumpBlockLiveness(M);
 }
 
-//===----------------------------------------------------------------------===//
-// printing liveness state for debugging
-//
+void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {
+  std::vector<const CFGBlock *> vec;
+  for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator
+       it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end();
+       it != ei; ++it) {
+    vec.push_back(it->first);    
+  }
+  std::sort(vec.begin(), vec.end(), compare_entries);
 
-void LiveVariables::dumpLiveness(const ValTy& V, const SourceManager& SM) const {
-  const AnalysisDataTy& AD = getAnalysisData();
+  std::vector<const VarDecl*> declVec;
 
-  for (AnalysisDataTy::decl_iterator I = AD.begin_decl(),
-                                     E = AD.end_decl(); I!=E; ++I)
-    if (V.getDeclBit(I->second)) {
-      llvm::errs() << "  " << I->first->getIdentifier()->getName() << " <";
-      I->first->getLocation().dump(SM);
+  for (std::vector<const CFGBlock *>::iterator
+        it = vec.begin(), ei = vec.end(); it != ei; ++it) {
+    llvm::errs() << "\n[ B" << (*it)->getBlockID()
+                 << " (live variables at block exit) ]\n";
+    
+    LiveVariables::LivenessValues vals = blocksEndToLiveness[*it];
+    declVec.clear();
+    
+    for (llvm::ImmutableSet<const VarDecl *>::iterator si =
+          vals.liveDecls.begin(),
+          se = vals.liveDecls.end(); si != se; ++si) {
+      declVec.push_back(*si);      
+    }
+    
+    std::sort(declVec.begin(), declVec.end(), compare_vd_entries);
+    
+    for (std::vector<const VarDecl*>::iterator di = declVec.begin(),
+         de = declVec.end(); di != de; ++di) {
+      llvm::errs() << " " << (*di)->getDeclName().getAsString()
+                   << " <";
+      (*di)->getLocation().dump(M);
       llvm::errs() << ">\n";
     }
-}
-
-void LiveVariables::dumpBlockLiveness(const SourceManager& M) const {
-  for (BlockDataMapTy::const_iterator I = getBlockDataMap().begin(),
-       E = getBlockDataMap().end(); I!=E; ++I) {
-    llvm::errs() << "\n[ B" << I->first->getBlockID()
-                 << " (live variables at block exit) ]\n";
-    dumpLiveness(I->second,M);
   }
-
-  llvm::errs() << "\n";
+  llvm::errs() << "\n";  
 }
+