1 files changed, 382 insertions, 0 deletions
diff --git a/contrib/llvm/tools/clang/lib/Analysis/LiveVariables.cpp b/contrib/llvm/tools/clang/lib/Analysis/LiveVariables.cpp
new file mode 100644
index 0000000..01a36a1
--- /dev/null
+++ b/contrib/llvm/tools/clang/lib/Analysis/LiveVariables.cpp
@@ -0,0 +1,382 @@
+//=- 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/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"
+
+using namespace clang;
+
+//===----------------------------------------------------------------------===//
+// Useful constants.
+//===----------------------------------------------------------------------===//
+
+static const bool Alive = true;
+static const bool Dead = false;
+
+//===----------------------------------------------------------------------===//
+// Dataflow initialization logic.
+//===----------------------------------------------------------------------===//
+
+namespace {
+class RegisterDecls
+  : public CFGRecStmtDeclVisitor<RegisterDecls> {
+
+  LiveVariables::AnalysisDataTy& AD;
+
+  typedef llvm::SmallVector<VarDecl*, 20> AlwaysLiveTy;
+  AlwaysLiveTy AlwaysLive;
+
+
+public:
+  RegisterDecls(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
+
+  ~RegisterDecls() {
+
+    AD.AlwaysLive.resetValues(AD);
+
+    for (AlwaysLiveTy::iterator I = AlwaysLive.begin(), E = AlwaysLive.end();
+         I != E; ++ I)
+      AD.AlwaysLive(*I, AD) = Alive;
+  }
+
+  void VisitImplicitParamDecl(ImplicitParamDecl* IPD) {
+    // Register the VarDecl for tracking.
+    AD.Register(IPD);
+  }
+
+  void VisitVarDecl(VarDecl* VD) {
+    // Register the VarDecl for tracking.
+    AD.Register(VD);
+
+    // Does the variable have global storage?  If so, it is always live.
+    if (VD->hasGlobalStorage())
+      AlwaysLive.push_back(VD);
+  }
+
+  CFG& getCFG() { return AD.getCFG(); }
+};
+} // end anonymous namespace
+
+LiveVariables::LiveVariables(AnalysisContext &AC) {  
+  // Register all referenced VarDecls.
+  CFG &cfg = *AC.getCFG();
+  getAnalysisData().setCFG(cfg);
+  getAnalysisData().setContext(AC.getASTContext());
+  getAnalysisData().AC = &AC;
+
+  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);
+}
+
+//===----------------------------------------------------------------------===//
+// Transfer functions.
+//===----------------------------------------------------------------------===//
+
+namespace {
+
+class TransferFuncs : public CFGRecStmtVisitor<TransferFuncs>{
+  LiveVariables::AnalysisDataTy& AD;
+  LiveVariables::ValTy LiveState;
+public:
+  TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
+
+  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);
+  
+  /// 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;
+  }
+
+};
+
+void TransferFuncs::Visit(Stmt *S) {
+
+  if (S == getCurrentBlkStmt()) {
+
+    if (AD.Observer)
+      AD.Observer->ObserveStmt(S,AD,LiveState);
+
+    if (getCFG().isBlkExpr(S))
+      LiveState(S, AD) = Dead;
+
+    StmtVisitor<TransferFuncs,void>::Visit(S);
+  }
+  else if (!getCFG().isBlkExpr(S)) {
+
+    if (AD.Observer)
+      AD.Observer->ObserveStmt(S,AD,LiveState);
+
+    StmtVisitor<TransferFuncs,void>::Visit(S);
+
+  }
+  else {
+    // For block-level expressions, mark that they are live.
+    LiveState(S,AD) = Alive;
+  }
+}
+  
+void TransferFuncs::VisitConditionVariableInit(Stmt *S) {
+  assert(!getCFG().isBlkExpr(S));
+  CFGRecStmtVisitor<TransferFuncs>::VisitConditionVariableInit(S);
+}
+
+void TransferFuncs::VisitTerminator(CFGBlock* B) {
+
+  const Stmt* E = B->getTerminatorCondition();
+
+  if (!E)
+    return;
+
+  assert (getCFG().isBlkExpr(E));
+  LiveState(E, AD) = Alive;
+}
+
+void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
+  if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl()))
+    LiveState(V, AD) = Alive;
+}
+  
+void TransferFuncs::VisitBlockExpr(BlockExpr *BE) {
+  AnalysisContext::referenced_decls_iterator I, E;
+  llvm::tie(I, E) = AD.AC->getReferencedBlockVars(BE->getBlockDecl());
+  for ( ; I != E ; ++I) {
+    DeclBitVector_Types::Idx i = AD.getIdx(*I);
+    if (i.isValid())
+      LiveState.getBit(i) = Alive;
+  }
+}
+
+void TransferFuncs::VisitBinaryOperator(BinaryOperator* B) {
+  if (B->isAssignmentOp()) VisitAssign(B);
+  else VisitStmt(B);
+}
+
+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());
+
+  // This represents a 'kill' for the variable.
+  Stmt* Element = S->getElement();
+  DeclRefExpr* DR = 0;
+  VarDecl* VD = 0;
+
+  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;
+    }
+  }
+
+  if (VD) {
+    LiveState(VD, AD) = Dead;
+    if (AD.Observer && DR) { AD.Observer->ObserverKill(DR); }
+  }
+}
+
+
+void TransferFuncs::VisitUnaryOperator(UnaryOperator* U) {
+  Expr *E = U->getSubExpr();
+
+  switch (U->getOpcode()) {
+  case UnaryOperator::PostInc:
+  case UnaryOperator::PostDec:
+  case UnaryOperator::PreInc:
+  case UnaryOperator::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())) {
+
+    // 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() != BinaryOperator::Assign)
+      VisitDeclRefExpr(DR);
+  }
+  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);
+      }
+    }
+}
+
+} // 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 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);
+}
+
+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);
+}
+
+//===----------------------------------------------------------------------===//
+// liveness queries
+//
+
+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;
+}
+
+bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const {
+  DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D);
+  return i.isValid() ? Live.getBit(i) : false;
+}
+
+bool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const {
+  return getStmtData(Loc)(StmtVal,getAnalysisData());
+}
+
+bool LiveVariables::isLive(const Stmt* Loc, const VarDecl* D) const {
+  return getStmtData(Loc)(D,getAnalysisData());
+}
+
+//===----------------------------------------------------------------------===//
+// printing liveness state for debugging
+//
+
+void LiveVariables::dumpLiveness(const ValTy& V, const SourceManager& SM) const {
+  const AnalysisDataTy& AD = getAnalysisData();
+
+  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);
+      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";
+}