Significant cleanups and bug-fixes to LiveVariables. Uses new refactored

ExprDeclBitVector class for defining dataflow state.


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

3 files changed, 78 insertions, 105 deletions

diff --git a/Analysis/DeadStores.cpp b/Analysis/DeadStores.cpp
index 642b90b8d8..28c21b0b2d 100644
--- a/Analysis/DeadStores.cpp
+++ b/Analysis/DeadStores.cpp
@@ -38,7 +38,7 @@ public:
       
       if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(B->getLHS()))
         // Is the variable NOT live?  If so, flag a dead store.
-        if (!Live(AD,DR->getDecl())) {
+        if (!Live(DR->getDecl(),AD)) {
           SourceRange R = B->getRHS()->getSourceRange();
           Diags.Report(DR->getSourceRange().Begin(), diag::warn_dead_store,
                        0, 0, &R, 1);                                                                        
@@ -50,7 +50,7 @@ public:
       for (VarDecl* V = cast<VarDecl>(DS->getDecl()); V != NULL ; 
                     V = cast_or_null<VarDecl>(V->getNextDeclarator())) {
         if (Expr* E = V->getInit()) {
-          if (!Live(AD,DS->getDecl())) {
+          if (!Live(DS->getDecl(),AD)) {
             // Special case: check for initializations with constants.
             //
             //  e.g. : int x = 0;
diff --git a/Analysis/LiveVariables.cpp b/Analysis/LiveVariables.cpp
index 10b806329c..d40941d13b 100644
--- a/Analysis/LiveVariables.cpp
+++ b/Analysis/LiveVariables.cpp
@@ -31,16 +31,18 @@ using namespace clang;
 //===----------------------------------------------------------------------===//      
 
 namespace {
-struct RegisterDecls : public CFGRecStmtDeclVisitor<RegisterDecls> {
+class RegisterDeclsExprs : public CFGRecStmtDeclVisitor<RegisterDeclsExprs> {  
   LiveVariables::AnalysisDataTy& AD;
-  void VisitVarDecl(VarDecl* VD) { AD.RegisterDecl(VD); }
-
-  RegisterDecls(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
+public:
+  RegisterDeclsExprs(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
+  
+  void VisitVarDecl(VarDecl* VD) { AD.Register(VD); }
+  void BlockStmt_VisitExpr(Expr* E) { AD.Register(E); }
 };  
 } // end anonymous namespace
 
 void LiveVariables::InitializeValues(const CFG& cfg) {
-  RegisterDecls R(getAnalysisData());
+  RegisterDeclsExprs R(getAnalysisData());
   cfg.VisitBlockStmts(R);
 }
 
@@ -49,29 +51,38 @@ void LiveVariables::InitializeValues(const CFG& cfg) {
 //===----------------------------------------------------------------------===//      
 
 namespace {
+  
+static const bool Alive = true;
+static const bool Dead = false;  
+
 class TransferFuncs : public CFGStmtVisitor<TransferFuncs> {
   LiveVariables::AnalysisDataTy& AD;
-  LiveVariables::ValTy Live;
+  LiveVariables::ValTy LiveState;
+  bool ExprLiveness;
 public:
-  TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
+  TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad), 
+                                                     ExprLiveness(Dead) {}
 
-  LiveVariables::ValTy& getVal() { return Live; }
+  LiveVariables::ValTy& getVal() { return LiveState; }
   
   void VisitDeclRefExpr(DeclRefExpr* DR);
   void VisitBinaryOperator(BinaryOperator* B);
   void VisitAssign(BinaryOperator* B);
   void VisitDeclStmt(DeclStmt* DS);
   void VisitUnaryOperator(UnaryOperator* U);
-  void VisitStmt(Stmt* S) { VisitChildren(S); }
+  void VisitStmt(Stmt* S);
+  void BlockStmt_VisitExpr(Expr *E);
+  
   void Visit(Stmt *S) {
-    if (AD.Observer) AD.Observer->ObserveStmt(S,AD,Live);
+    if (AD.Observer) AD.Observer->ObserveStmt(S,AD,LiveState);
     static_cast<CFGStmtVisitor<TransferFuncs>*>(this)->Visit(S);
   }
 };
+  
 
 void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
   if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl())) 
-    Live.set(AD[V]);   // Register a use of the variable.
+    LiveState(V,AD) = Alive;
 }
   
 void TransferFuncs::VisitBinaryOperator(BinaryOperator* B) {     
@@ -93,28 +104,27 @@ void TransferFuncs::VisitUnaryOperator(UnaryOperator* U) {
       if (ParenExpr* P = dyn_cast<ParenExpr>(S)) { S=P->getSubExpr(); continue;} 
       else if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(S)) {
         // Treat the --/++/& operator as a kill.
-        Live.reset(AD[DR->getDecl()]);
-        if (AD.Observer) AD.Observer->ObserverKill(DR);
-        VisitDeclRefExpr(DR);          
+        LiveState(DR->getDecl(),AD) = Dead;
+        if (AD.Observer) { AD.Observer->ObserverKill(DR); }
+        return VisitDeclRefExpr(DR);
       }
-      else Visit(S);
-
-      break;   
-    }        
-    break;
+      else return Visit(S);
+    }
+      
+    assert (false && "Unreachable.");
   
   default:
-    Visit(U->getSubExpr());
-    break;
+    return Visit(U->getSubExpr());
   }
 }
 
 void TransferFuncs::VisitAssign(BinaryOperator* B) {    
   Stmt* LHS = B->getLHS();
 
-  if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS)) { // Assigning to a var?    
-    Live.reset(AD[DR->getDecl()]);
-    if (AD.Observer) AD.Observer->ObserverKill(DR);
+  if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS)) { // Assigning to a var?
+    LiveState(DR->getDecl(),AD) = Dead;
+    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() != BinaryOperator::Assign) Visit(LHS);
@@ -129,21 +139,34 @@ void TransferFuncs::VisitDeclStmt(DeclStmt* DS) {
   // Declarations effectively "kill" a variable since they cannot
   // possibly be live before they are declared.
   for (ScopedDecl* D = DS->getDecl(); D != NULL ; D = D->getNextDeclarator())
-    Live.reset(AD[D]);
+    LiveState(D,AD) = Dead;
+}
+  
+void TransferFuncs::VisitStmt(Stmt* S) {
+  if (AD.isTracked(static_cast<Expr*>(S))) return;
+  else VisitChildren(S); 
+}
+  
+void TransferFuncs::BlockStmt_VisitExpr(Expr* E) {
+  assert (AD.isTracked(E));
+  static_cast<CFGStmtVisitor<TransferFuncs>*>(this)->Visit(E);
 }
+  
 } // end anonymous namespace
 
-namespace {
-struct Merge {
-  void operator()(LiveVariables::ValTy& Dst, LiveVariables::ValTy& Src) {
-    Src |= Dst;
-  }
-};
-} // end anonymous namespace
+//===----------------------------------------------------------------------===//
+// Merge operator: if something is live on any successor block, it is live
+//  in the current block (a set union).
+//===----------------------------------------------------------------------===//      
 
 namespace {
+typedef DeclBitVector_Types::Union Merge;
 typedef DataflowSolver<LiveVariables,TransferFuncs,Merge> Solver;
-}
+} // end anonymous namespace
+
+//===----------------------------------------------------------------------===//
+// External interface to run Liveness analysis.
+//===----------------------------------------------------------------------===//      
 
 void LiveVariables::runOnCFG(const CFG& cfg) {
   Solver S(*this);
@@ -164,11 +187,11 @@ void LiveVariables::runOnAllBlocks(const CFG& cfg,
 //
 
 bool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const {
-  return getBlockData(B)[ getAnalysisData()[D] ];
+  return getBlockData(B)(D,getAnalysisData());
 }
 
 bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const {
-  return Live[ getAnalysisData()[D] ];
+  return Live(D,getAnalysisData());
 }
 
 //===----------------------------------------------------------------------===//
@@ -178,8 +201,9 @@ bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const {
 void LiveVariables::dumpLiveness(const ValTy& V, SourceManager& SM) const {
   const AnalysisDataTy& AD = getAnalysisData();
   
-  for (AnalysisDataTy::iterator I = AD.begin(), E = AD.end(); I!=E; ++I)
-    if (V[I->second]) {      
+  for (AnalysisDataTy::decl_iterator I = AD.begin_decl(),
+                                     E = AD.end_decl(); I!=E; ++I)
+    if (V.getDeclBit(I->second)) {      
       SourceLocation PhysLoc = SM.getPhysicalLoc(I->first->getLocation());
     
       fprintf(stderr, "  %s <%s:%u:%u>\n", 
diff --git a/include/clang/Analysis/LiveVariables.h b/include/clang/Analysis/LiveVariables.h
index 2e10f4a0a3..08f37e0b56 100644
--- a/include/clang/Analysis/LiveVariables.h
+++ b/include/clang/Analysis/LiveVariables.h
@@ -15,9 +15,8 @@
 #define LLVM_CLANG_LIVEVARIABLES_H
 
 #include "clang/AST/Decl.h"
+#include "clang/Analysis/ExprDeclBitVector.h"
 #include "clang/Analysis/FlowSensitive/DataflowValues.h"
-#include "llvm/ADT/BitVector.h"
-#include "llvm/ADT/DenseMap.h"
 
 namespace clang {
 
@@ -26,80 +25,30 @@ class DeclRefExpr;
 class SourceManager;
   
 struct LiveVariables_ValueTypes {
-  //===-----------------------------------------------------===//
-  // AnalysisDataTy - Whole-function analysis meta data.
-  //===-----------------------------------------------------===//
 
-  class ObserverTy;
-  
-  class AnalysisDataTy {
-    typedef llvm::DenseMap<const VarDecl*, unsigned> VMapTy;
-    VMapTy M;
-    unsigned NDecls;
-   public:
-    ObserverTy* Observer;
-    
-    AnalysisDataTy() : NDecls(0), Observer(NULL) {}
-    
-    bool Tracked(const VarDecl* VD) const { return M.find(VD) != M.end(); }
-    void RegisterDecl(const VarDecl* VD) { if (!Tracked(VD)) M[VD] = NDecls++; }
+  struct ObserverTy;
 
-    unsigned operator[](const VarDecl* VD) const {
-      VMapTy::const_iterator I = M.find(VD);
-      assert (I != M.end());
-      return I->second;
-    }
-    
-    unsigned operator[](const ScopedDecl* S) const {
-      return (*this)[cast<VarDecl>(S)];
-    }
 
-    unsigned getNumDecls() const { return NDecls; }
-    
-    typedef VMapTy::const_iterator iterator;
-    iterator begin() const { return M.begin(); }
-    iterator end() const { return M.end(); }
-  };
-  
-  //===-----------------------------------------------------===//
-  // ValTy - Dataflow value.
-  //===-----------------------------------------------------===//
-  class ValTy {
-    llvm::BitVector V;
-  public:
-    void copyValues(const ValTy& RHS) { V = RHS.V; }
+  // We need to keep track of both declarations and CFGBlock-level expressions,
+  // (so that we don't explore such expressions twice), but we only need
+  // liveness information for declarations (hence 
+  // ValTy = DeclBitVector_Types::ValTy instead of 
+  // ValTy = ExprDeclBitVector_Types::ValTy).
 
-    bool operator==(const ValTy& RHS) const { return V == RHS.V; }
-    
-    void resetValues(const AnalysisDataTy& AD) {
-      V.resize(AD.getNumDecls());
-      V.reset();
-    }
-          
-    llvm::BitVector::reference operator[](unsigned i) {
-      assert (i < V.size() && "Liveness bitvector access is out-of-bounds.");
-      return V[i];
-    }
-    
-    const llvm::BitVector::reference operator[](unsigned i) const {
-      return const_cast<ValTy&>(*this)[i];
-    }
-    
-    bool operator()(const AnalysisDataTy& AD, const ScopedDecl* D) const {
-      return (*this)[AD[D]];
-    }
-    
-    ValTy& operator|=(ValTy& RHS) { V |= RHS.V; return *this; }
+  struct AnalysisDataTy : public ExprDeclBitVector_Types::AnalysisDataTy {
+    ObserverTy* Observer;
     
-    void set(unsigned i) { V.set(i); }
-    void reset(unsigned i) { V.reset(i); }
+    AnalysisDataTy() : Observer(NULL) {}
   };
+
+    // We only keep actual dataflow state for declarations.
+  typedef DeclBitVector_Types::ValTy ValTy;
   
   //===-----------------------------------------------------===//
   // ObserverTy - Observer for uninitialized values queries.
   //===-----------------------------------------------------===//
-  class ObserverTy {
-  public:
+
+  struct ObserverTy {
     virtual ~ObserverTy() {}
     
     /// ObserveStmt - A callback invoked right before invoking the