[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.

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

20 files changed, 2065 insertions, 1867 deletions

diff --git a/include/clang/Analysis/Analyses/LiveVariables.h b/include/clang/Analysis/Analyses/LiveVariables.h
index fbbd2613e7..6a1bae03be 100644
--- a/include/clang/Analysis/Analyses/LiveVariables.h
+++ b/include/clang/Analysis/Analyses/LiveVariables.h
@@ -1,4 +1,4 @@
-//===- LiveVariables.h - Live Variable Analysis for Source CFGs -*- C++ --*-===//
+//===- LiveVariables.h - Live Variable Analysis for Source CFGs -*- C++ --*-//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -15,109 +15,89 @@
 #define LLVM_CLANG_LIVEVARIABLES_H
 
 #include "clang/AST/Decl.h"
-#include "clang/Analysis/Support/BlkExprDeclBitVector.h"
-#include "clang/Analysis/FlowSensitive/DataflowValues.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/ImmutableSet.h"
 
 namespace clang {
 
+class CFG;
+class CFGBlock;
 class Stmt;
 class DeclRefExpr;
 class SourceManager;
 class AnalysisContext;
-
-struct LiveVariables_ValueTypes {
-
-  struct ObserverTy;
-
-  // We keep dataflow state for declarations and block-level expressions;
-  typedef StmtDeclBitVector_Types::ValTy ValTy;
-
-  // We need to keep track of both declarations and CFGBlock-level expressions,
-  // (so that we don't explore such expressions twice).  We also want
-  // to compute liveness information for block-level expressions, since these
-  // act as "temporary" values.
-
-  struct AnalysisDataTy : public StmtDeclBitVector_Types::AnalysisDataTy {
-    ObserverTy* Observer;
-    ValTy AlwaysLive;
-    AnalysisContext *AC;
-    bool killAtAssign;
-
-    AnalysisDataTy() : Observer(NULL), AC(NULL), killAtAssign(true) {}
+  
+class LiveVariables {
+public:
+  class LivenessValues {
+  public:
+
+    llvm::ImmutableSet<const Stmt *> liveStmts;
+    llvm::ImmutableSet<const VarDecl *> liveDecls;
+    
+    bool equals(const LivenessValues &V) const;
+
+    LivenessValues()
+      : liveStmts(0), liveDecls(0) {}
+
+    LivenessValues(llvm::ImmutableSet<const Stmt *> LiveStmts,
+                   llvm::ImmutableSet<const VarDecl *> LiveDecls)
+      : liveStmts(LiveStmts), liveDecls(LiveDecls) {}
+
+    ~LivenessValues() {}
+    
+    bool isLive(const Stmt *S) const;
+    bool isLive(const VarDecl *D) const;
+    
+    friend class LiveVariables;    
   };
-
-  //===-----------------------------------------------------===//
-  // ObserverTy - Observer for uninitialized values queries.
-  //===-----------------------------------------------------===//
-
-  struct ObserverTy {
-    virtual ~ObserverTy() {}
-
-    /// ObserveStmt - A callback invoked right before invoking the
+  
+  struct Observer {
+    virtual ~Observer() {}
+    
+    /// A callback invoked right before invoking the
     ///  liveness transfer function on the given statement.
-    virtual void ObserveStmt(Stmt* S, const CFGBlock *currentBlock,
-                             const AnalysisDataTy& AD,
-                             const ValTy& V) {}
-
-    virtual void ObserverKill(DeclRefExpr* DR) {}
-  };
-};
-
-class LiveVariables : public DataflowValues<LiveVariables_ValueTypes,
-                                            dataflow::backward_analysis_tag> {
-
-
-public:
-  typedef LiveVariables_ValueTypes::ObserverTy ObserverTy;
-
-  LiveVariables(AnalysisContext &AC, bool killAtAssign = true);
-
-  /// IsLive - Return true if a variable is live at the end of a
+    virtual void observeStmt(const Stmt* S,
+                             const CFGBlock *currentBlock,
+                             const LivenessValues& V) {}
+    
+    /// Called when the live variables analysis registers
+    /// that a variable is killed.
+    virtual void observerKill(const DeclRefExpr* DR) {}
+  };    
+
+
+  ~LiveVariables();
+  
+  /// Compute the liveness information for a given CFG.
+  static LiveVariables *computeLiveness(AnalysisContext &analysisContext,
+                                          bool killAtAssign = true);
+  
+  /// Return true if a variable is live at the end of a
   /// specified block.
-  bool isLive(const CFGBlock* B, const VarDecl* D) const;
-
-  /// IsLive - Returns true if a variable is live at the beginning of the
+  bool isLive(const CFGBlock* B, const VarDecl* D);
+  
+  /// Returns true if a variable is live at the beginning of the
   ///  the statement.  This query only works if liveness information
   ///  has been recorded at the statement level (see runOnAllBlocks), and
   ///  only returns liveness information for block-level expressions.
-  bool isLive(const Stmt* S, const VarDecl* D) const;
-
-  /// IsLive - Returns true the block-level expression "value" is live
+  bool isLive(const Stmt* S, const VarDecl* D);
+  
+  /// Returns true the block-level expression "value" is live
   ///  before the given block-level expression (see runOnAllBlocks).
-  bool isLive(const Stmt* Loc, const Stmt* StmtVal) const;
+  bool isLive(const Stmt* Loc, const Stmt* StmtVal);
+    
+  /// Print to stderr the liveness information associated with
+  /// each basic block.
+  void dumpBlockLiveness(const SourceManager& M);
 
-  /// IsLive - Return true if a variable is live according to the
-  ///  provided livness bitvector.
-  bool isLive(const ValTy& V, const VarDecl* D) const;
+  void runOnAllBlocks(Observer &obs);
 
-  /// dumpLiveness - Print to stderr the liveness information encoded
-  ///  by a specified bitvector.
-  void dumpLiveness(const ValTy& V, const SourceManager& M) const;
-
-  /// dumpBlockLiveness - Print to stderr the liveness information
-  ///  associated with each basic block.
-  void dumpBlockLiveness(const SourceManager& M) const;
-
-  /// getNumDecls - Return the number of variables (declarations) that
-  ///  whose liveness status is being tracked by the dataflow
-  ///  analysis.
-  unsigned getNumDecls() const { return getAnalysisData().getNumDecls(); }
-
-  /// IntializeValues - This routine can perform extra initialization, but
-  ///  for LiveVariables this does nothing since all that logic is in
-  ///  the constructor.
-  void InitializeValues(const CFG& cfg) {}
-
-  void runOnCFG(CFG& cfg);
-
-  /// runOnAllBlocks - Propagate the dataflow values once for each block,
-  ///  starting from the current dataflow values.  'recordStmtValues' indicates
-  ///  whether the method should store dataflow values per each individual
-  ///  block-level expression.
-  void runOnAllBlocks(const CFG& cfg, ObserverTy* Obs,
-                      bool recordStmtValues=false);
+private:
+  LiveVariables(void *impl);
+  void *impl;
 };
-
+  
 } // end namespace clang
 
 #endif
diff --git a/include/clang/Analysis/CFG.h b/include/clang/Analysis/CFG.h
index 87f32a5166..2f6c4b3640 100644
--- a/include/clang/Analysis/CFG.h
+++ b/include/clang/Analysis/CFG.h
@@ -545,8 +545,13 @@ public:
       return alwaysAddMask[stmt->getStmtClass()];
     }
     
-    BuildOptions &setAlwaysAdd(Stmt::StmtClass stmtClass) {
-      alwaysAddMask[stmtClass] = true;
+    BuildOptions &setAlwaysAdd(Stmt::StmtClass stmtClass, bool val = true) {
+      alwaysAddMask[stmtClass] = val;
+      return *this;
+    }
+    
+    BuildOptions &setAllAlwaysAdd() {
+      alwaysAddMask.set();
       return *this;
     }
 
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h
index 0cb4ad992b..66ecba7dcf 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h
@@ -19,9 +19,11 @@
 #include "clang/AST/Expr.h"
 #include "clang/Analysis/AnalysisContext.h"
 #include "clang/Basic/LLVM.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h"
 #include "llvm/Support/DataTypes.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/DenseMap.h"
 
 namespace llvm {
 class BumpPtrAllocator;
@@ -40,10 +42,10 @@ namespace ento {
 
 class SymExpr : public llvm::FoldingSetNode {
 public:
-  enum Kind { BEGIN_SYMBOLS,
-              RegionValueKind, ConjuredKind, DerivedKind, ExtentKind,
+  enum Kind { RegionValueKind, ConjuredKind, DerivedKind, ExtentKind,
               MetadataKind,
-              END_SYMBOLS,
+              BEGIN_SYMBOLS = RegionValueKind,
+              END_SYMBOLS = MetadataKind,
               SymIntKind, SymSymKind };
 private:
   Kind K;
@@ -84,7 +86,7 @@ public:
   // Implement isa<T> support.
   static inline bool classof(const SymExpr* SE) {
     Kind k = SE->getKind();
-    return k > BEGIN_SYMBOLS && k < END_SYMBOLS;
+    return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS;
   }
 };
 
@@ -419,10 +421,13 @@ class SymbolReaper {
   const LocationContext *LCtx;
   const Stmt *Loc;
   SymbolManager& SymMgr;
+  StoreRef reapedStore;
+  llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache;
 
 public:
-  SymbolReaper(const LocationContext *ctx, const Stmt *s, SymbolManager& symmgr)
-   : LCtx(ctx), Loc(s), SymMgr(symmgr) {}
+  SymbolReaper(const LocationContext *ctx, const Stmt *s, SymbolManager& symmgr,
+               StoreManager &storeMgr)
+   : LCtx(ctx), Loc(s), SymMgr(symmgr), reapedStore(0, storeMgr) {}
 
   ~SymbolReaper() {}
 
@@ -431,7 +436,7 @@ public:
 
   bool isLive(SymbolRef sym);
   bool isLive(const Stmt *ExprVal) const;
-  bool isLive(const VarRegion *VR) const;
+  bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const;
 
   // markLive - Unconditionally marks a symbol as live. This should never be
   //  used by checkers, only by the state infrastructure such as the store and
@@ -464,6 +469,10 @@ public:
   bool isDead(SymbolRef sym) const {
     return TheDead.count(sym);
   }
+  
+  /// Set to the value of the symbolic store after
+  /// StoreManager::removeDeadBindings has been called.
+  void setReapedStore(StoreRef st) { reapedStore = st; }
 };
 
 class SymbolVisitor {
diff --git a/lib/Analysis/AnalysisContext.cpp b/lib/Analysis/AnalysisContext.cpp
index 7ee247da00..5a85899389 100644
--- a/lib/Analysis/AnalysisContext.cpp
+++ b/lib/Analysis/AnalysisContext.cpp
@@ -177,25 +177,14 @@ PseudoConstantAnalysis *AnalysisContext::getPseudoConstantAnalysis() {
 }
 
 LiveVariables *AnalysisContext::getLiveVariables() {
-  if (!liveness) {
-    if (CFG *c = getCFG()) {
-      liveness.reset(new LiveVariables(*this));
-      liveness->runOnCFG(*c);
-      liveness->runOnAllBlocks(*c, 0, true);
-    }
-  }
-
+  if (!liveness)
+    liveness.reset(LiveVariables::computeLiveness(*this));
   return liveness.get();
 }
 
 LiveVariables *AnalysisContext::getRelaxedLiveVariables() {
   if (!relaxedLiveness)
-    if (CFG *c = getCFG()) {
-      relaxedLiveness.reset(new LiveVariables(*this, false));
-      relaxedLiveness->runOnCFG(*c);
-      relaxedLiveness->runOnAllBlocks(*c, 0, true);
-    }
-
+    relaxedLiveness.reset(LiveVariables::computeLiveness(*this, false));
   return relaxedLiveness.get();
 }
 
diff --git a/lib/Analysis/LiveVariables.cpp b/lib/Analysis/LiveVariables.cpp
index b7ae141781..f81019e2c9 100644
--- a/lib/Analysis/LiveVariables.cpp
+++ b/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 decla