Further refactored DataflowSolver. Now most code for the solver is shared
between forward and backward analyses, with trait classes being used
to implement the key differences in operations/functionality.
Converted the LiveVariables analysis to use the generic DataflowSolver. This,
along with removing some extra functionality that was not needed, reduced
the code for LiveVariables by over half.
Modified Driver code to handle the updated interface to LiveVariables.
Modified the DeadStores checker to handle the update interface to
LiveVariables.
Updated DataflowValues (generic ADT to store dataflow values) to also
store values for blocks. This is used by DeadStores. Updated some comments.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@42293 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/Analysis/DataflowSolver.h b/Analysis/DataflowSolver.h
index 4e7370f..ebb5e6f 100644
--- a/Analysis/DataflowSolver.h
+++ b/Analysis/DataflowSolver.h
@@ -45,6 +45,61 @@
};
//===----------------------------------------------------------------------===//
+// BlockItrTraits - Traits classes that allow transparent iteration over
+// successors/predecessors of a block depending on the direction of our
+// dataflow analysis.
+
+namespace dataflow {
+template<typename Tag> struct ItrTraits {};
+
+template <> struct ItrTraits<forward_analysis_tag> {
+ typedef CFGBlock::const_pred_iterator PrevBItr;
+ typedef CFGBlock::const_succ_iterator NextBItr;
+ typedef CFGBlock::const_iterator StmtItr;
+
+ static PrevBItr PrevBegin(const CFGBlock* B) { return B->pred_begin(); }
+ static PrevBItr PrevEnd(const CFGBlock* B) { return B->pred_end(); }
+
+ static NextBItr NextBegin(const CFGBlock* B) { return B->succ_begin(); }
+ static NextBItr NextEnd(const CFGBlock* B) { return B->succ_end(); }
+
+ static StmtItr StmtBegin(const CFGBlock* B) { return B->begin(); }
+ static StmtItr StmtEnd(const CFGBlock* B) { return B->end(); }
+
+ static CFG::Edge PrevEdge(const CFGBlock* B, const CFGBlock* PrevBlk) {
+ return CFG::Edge(PrevBlk,B);
+ }
+
+ static CFG::Edge NextEdge(const CFGBlock* B, const CFGBlock* NextBlk) {
+ return CFG::Edge(B,NextBlk);
+ }
+};
+
+template <> struct ItrTraits<backward_analysis_tag> {
+ typedef CFGBlock::const_succ_iterator PrevBItr;
+ typedef CFGBlock::const_pred_iterator NextBItr;
+ typedef CFGBlock::const_reverse_iterator StmtItr;
+
+ static PrevBItr PrevBegin(const CFGBlock* B) { return B->succ_begin(); }
+ static PrevBItr PrevEnd(const CFGBlock* B) { return B->succ_end(); }
+
+ static NextBItr NextBegin(const CFGBlock* B) { return B->pred_begin(); }
+ static NextBItr NextEnd(const CFGBlock* B) { return B->pred_end(); }
+
+ static StmtItr StmtBegin(const CFGBlock* B) { return B->rbegin(); }
+ static StmtItr StmtEnd(const CFGBlock* B) { return B->rend(); }
+
+ static CFG::Edge PrevEdge(const CFGBlock* B, const CFGBlock* PrevBlk) {
+ return CFG::Edge(B,PrevBlk);
+ }
+
+ static CFG::Edge NextEdge(const CFGBlock* B, const CFGBlock* NextBlk) {
+ return CFG::Edge(NextBlk,B);
+ }
+};
+} // end namespace dataflow
+
+//===----------------------------------------------------------------------===//
/// DataflowSolverTy - Generic dataflow solver.
template <typename _DFValuesTy, // Usually a subclass of DataflowValues
typename _TransferFuncsTy,
@@ -57,14 +112,20 @@
//===--------------------------------------------------------------------===//
public:
- typedef _DFValuesTy DFValuesTy;
- typedef _TransferFuncsTy TransferFuncsTy;
- typedef _MergeOperatorTy MergeOperatorTy;
+ typedef _DFValuesTy DFValuesTy;
+ typedef _TransferFuncsTy TransferFuncsTy;
+ typedef _MergeOperatorTy MergeOperatorTy;
+
+ typedef typename _DFValuesTy::AnalysisDirTag AnalysisDirTag;
+ typedef typename _DFValuesTy::ValTy ValTy;
+ typedef typename _DFValuesTy::EdgeDataMapTy EdgeDataMapTy;
+ typedef typename _DFValuesTy::BlockDataMapTy BlockDataMapTy;
- typedef typename _DFValuesTy::AnalysisDirTag AnalysisDirTag;
- typedef typename _DFValuesTy::ValTy ValTy;
- typedef typename _DFValuesTy::EdgeDataMapTy EdgeDataMapTy;
-
+ typedef dataflow::ItrTraits<AnalysisDirTag> ItrTraits;
+ typedef typename ItrTraits::NextBItr NextBItr;
+ typedef typename ItrTraits::PrevBItr PrevBItr;
+ typedef typename ItrTraits::StmtItr StmtItr;
+
//===--------------------------------------------------------------------===//
// External interface: constructing and running the solver.
//===--------------------------------------------------------------------===//
@@ -88,13 +149,18 @@
/// only be used for querying the dataflow values within a block with
/// and Observer object.
void runOnBlock(const CFGBlock* B) {
- if (hasData(B,AnalysisDirTag()))
- ProcessBlock(B,AnalysisDirTag());
+ BlockDataMapTy& M = D.getBlockDataMap();
+ typename BlockDataMapTy::iterator I = M.find(B);
+
+ if (I != M.end()) {
+ TF.getVal().copyValues(I->second);
+ ProcessBlock(B);
+ }
}
void runOnBlock(const CFGBlock& B) { runOnBlock(&B); }
- void runOnBlock(CFG::iterator &I) { runOnBlock(*I); }
- void runOnBlock(CFG::const_iterator &I) { runOnBlock(*I); }
+ void runOnBlock(CFG::iterator& I) { runOnBlock(*I); }
+ void runOnBlock(CFG::const_iterator& I) { runOnBlock(*I); }
void runOnAllBlocks(const CFG& cfg) {
for (CFG::const_iterator I=cfg.begin(), E=cfg.end(); I!=E; ++I)
@@ -110,17 +176,13 @@
/// SolveDataflowEquations - Perform the actual
/// worklist algorithm to compute dataflow values.
void SolveDataflowEquations(const CFG& cfg) {
-
EnqueueFirstBlock(cfg,AnalysisDirTag());
- // Process the worklist until it is empty.
while (!WorkList.isEmpty()) {
const CFGBlock* B = WorkList.dequeue();
- // If the dataflow values at the block's entry have changed,
- // enqueue all predecessor blocks onto the worklist to have
- // their values updated.
- ProcessBlock(B,AnalysisDirTag());
- UpdateEdges(B,TF.getVal(),AnalysisDirTag());
+ ProcessMerge(B);
+ ProcessBlock(B);
+ UpdateEdges(B,TF.getVal());
}
}
@@ -131,42 +193,8 @@
void EnqueueFirstBlock(const CFG& cfg, dataflow::backward_analysis_tag) {
WorkList.enqueue(&cfg.getExit());
}
-
- /// ProcessBlock (FORWARD ANALYSIS) - Process the transfer functions
- /// for a given block based on a forward analysis.
- void ProcessBlock(const CFGBlock* B, dataflow::forward_analysis_tag) {
-
- // Merge dataflow values from all predecessors of this block.
- ValTy& V = TF.getVal();
- V.resetValues(D.getAnalysisData());
- MergeOperatorTy Merge;
-
- EdgeDataMapTy& M = D.getEdgeDataMap();
- bool firstMerge = true;
-
- for (CFGBlock::const_pred_iterator I=B->pred_begin(),
- E=B->pred_end(); I!=E; ++I) {
- typename EdgeDataMapTy::iterator BI = M.find(CFG::Edge(*I,B));
- if (BI != M.end()) {
- if (firstMerge) {
- firstMerge = false;
- V.copyValues(BI->second);
- }
- else
- Merge(V,BI->second);
- }
- }
- // Process the statements in the block in the forward direction.
- for (CFGBlock::const_iterator I=B->begin(), E=B->end(); I!=E; ++I)
- TF.BlockStmt_Visit(const_cast<Stmt*>(*I));
- }
-
- /// ProcessBlock (BACKWARD ANALYSIS) - Process the transfer functions
- /// for a given block based on a forward analysis.
- void ProcessBlock(const CFGBlock* B, TransferFuncsTy& TF,
- dataflow::backward_analysis_tag) {
-
+ void ProcessMerge(const CFGBlock* B) {
// Merge dataflow values from all predecessors of this block.
ValTy& V = TF.getVal();
V.resetValues(D.getAnalysisData());
@@ -174,59 +202,47 @@
EdgeDataMapTy& M = D.getEdgeDataMap();
bool firstMerge = true;
+
+ for (PrevBItr I=ItrTraits::PrevBegin(B),E=ItrTraits::PrevEnd(B); I!=E; ++I){
- for (CFGBlock::const_succ_iterator I=B->succ_begin(),
- E=B->succ_end(); I!=E; ++I) {
- typename EdgeDataMapTy::iterator BI = M.find(CFG::Edge(B,*I));
- if (BI != M.end()) {
+ typename EdgeDataMapTy::iterator EI = M.find(ItrTraits::PrevEdge(B,*I));
+
+ if (EI != M.end()) {
if (firstMerge) {
firstMerge = false;
- V.copyValues(BI->second);
+ V.copyValues(EI->second);
}
- else
- Merge(V,BI->second);
+ else Merge(V,EI->second);
}
}
- // Process the statements in the block in the forward direction.
- for (CFGBlock::const_reverse_iterator I=B->begin(), E=B->end(); I!=E; ++I)
- TF.BlockStmt_Visit(const_cast<Stmt*>(*I));
+ // Set the data for the block.
+ D.getBlockDataMap()[B].copyValues(V);
+ }
+
+
+ /// ProcessBlock - Process the transfer functions for a given block.
+ void ProcessBlock(const CFGBlock* B) {
+ for (StmtItr I=ItrTraits::StmtBegin(B), E=ItrTraits::StmtEnd(B); I!=E; ++I)
+ TF.BlockStmt_Visit(const_cast<Stmt*>(*I));
}
- /// UpdateEdges (FORWARD ANALYSIS) - After processing the transfer
+ /// UpdateEdges - After processing the transfer
/// functions for a block, update the dataflow value associated with the
- /// block's outgoing edges. Enqueue any successor blocks for an
- /// outgoing edge whose value has changed.
- void UpdateEdges(const CFGBlock* B, ValTy& V,dataflow::forward_analysis_tag) {
- for (CFGBlock::const_succ_iterator I=B->succ_begin(), E=B->succ_end();
- I!=E; ++I) {
-
- CFG::Edge Edg(B,*I);
- UpdateEdgeValue(Edg,V,*I);
- }
+ /// block's outgoing/incoming edges (depending on whether we do a
+ // forward/backward analysis respectively)
+ void UpdateEdges(const CFGBlock* B, ValTy& V) {
+ for (NextBItr I=ItrTraits::NextBegin(B), E=ItrTraits::NextEnd(B); I!=E; ++I)
+ UpdateEdgeValue(ItrTraits::NextEdge(B,*I),V,*I);
}
-
- /// UpdateEdges (BACKWARD ANALYSIS) - After processing the transfer
- /// functions for a block, update the dataflow value associated with the
- /// block's incoming edges. Enqueue any predecessor blocks for an
- /// outgoing edge whose value has changed.
- void UpdateEdges(const CFGBlock* B, ValTy& V,dataflow::backward_analysis_tag){
- for (CFGBlock::const_pred_iterator I=B->succ_begin(), E=B->succ_end();
- I!=E; ++I) {
-
- CFG::Edge Edg(*I,B);
- UpdateEdgeValue(Edg,V,*I);
- }
- }
-
+
/// UpdateEdgeValue - Update the value associated with a given edge.
- void UpdateEdgeValue(CFG::Edge& E, ValTy& V, const CFGBlock* TargetBlock) {
+ void UpdateEdgeValue(CFG::Edge E, ValTy& V, const CFGBlock* TargetBlock) {
EdgeDataMapTy& M = D.getEdgeDataMap();
typename EdgeDataMapTy::iterator I = M.find(E);
- if (I == M.end()) {
- // First value for this edge.
+ if (I == M.end()) { // First computed value for this edge?
M[E].copyValues(V);
WorkList.enqueue(TargetBlock);
}
@@ -235,33 +251,7 @@
WorkList.enqueue(TargetBlock);
}
}
-
- /// hasData (FORWARD ANALYSIS) - Is there any dataflow values associated
- /// with the incoming edges of a block?
- bool hasData(const CFGBlock* B, dataflow::forward_analysis_tag) {
- EdgeDataMapTy& M = D.getEdgeDataMap();
-
- for (CFGBlock::const_pred_iterator I=B->pred_begin(), E=B->pred_end();
- I!=E; ++I)
- if (M.find(CFG::Edge(*I,B)) != M.end())
- return true;
-
- return false;
- }
-
- /// hasData (BACKWARD ANALYSIS) - Is there any dataflow values associated
- /// with the outgoing edges of a block?
- bool hasData(const CFGBlock* B, dataflow::backward_analysis_tag) {
- EdgeDataMapTy& M = D.getEdgeDataMap();
- for (CFGBlock::const_succ_iterator I=B->succ_begin(), E=B->succ_end();
- I!=E; ++I)
- if (M.find(CFG::Edge(B,*I)) != M.end())
- return true;
-
- return false;
- }
-
private:
DFValuesTy& D;
DataflowWorkListTy WorkList;
diff --git a/Analysis/DeadStores.cpp b/Analysis/DeadStores.cpp
index 8e2e362..b976d92 100644
--- a/Analysis/DeadStores.cpp
+++ b/Analysis/DeadStores.cpp
@@ -12,50 +12,57 @@
//
//===----------------------------------------------------------------------===//
-#include "clang/AST/Expr.h"
#include "clang/Analysis/LocalCheckers.h"
#include "clang/Analysis/LiveVariables.h"
-#include "clang/AST/CFG.h"
+#include "clang/Analysis/Visitors/CFGRecStmtVisitor.h"
#include "clang/Basic/Diagnostic.h"
#include "clang/AST/ASTContext.h"
+#include "llvm/ADT/SmallPtrSet.h"
using namespace clang;
namespace {
-class DeadStoreObserver : public LiveVariablesObserver {
+class EverKilled : public LiveVariables::ObserverTy {
+ llvm::SmallPtrSet<const VarDecl*, 10> Killed;
+public:
+ virtual void ObserveKill(DeclRefExpr* DR) {
+ Killed.insert(cast<VarDecl>(DR->getDecl()));
+ }
+
+ bool hasKill(const VarDecl* V) { return Killed.count(V) != 0; }
+};
+
+class DeadStoreObs : public LiveVariables::ObserverTy {
ASTContext &Ctx;
Diagnostic &Diags;
+ EverKilled EK;
public:
- DeadStoreObserver(ASTContext &ctx, Diagnostic &diags)
- : Ctx(ctx), Diags(diags) {
- }
+ DeadStoreObs(ASTContext &ctx,Diagnostic &diags) : Ctx(ctx), Diags(diags){}
+ virtual ~DeadStoreObs() {}
+
+ virtual void ObserveStmt(Stmt* S,
+ const LiveVariables::AnalysisDataTy& AD,
+ const LiveVariables::ValTy& Live) {
- virtual ~DeadStoreObserver() {}
-
- virtual void ObserveStmt(Stmt* S, LiveVariables& L, llvm::BitVector& Live) {
if (BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
- // Is this an assignment?
- if (!B->isAssignmentOp())
- return;
+ if (!B->isAssignmentOp()) return; // Skip non-assignments.
- // Is this an assignment to a variable?
if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(B->getLHS()))
- // Is the variable live?
- if (!L.isLive(Live,cast<VarDecl>(DR->getDecl()))) {
+ // Is the variable NOT live? If so, flag a dead store.
+ if (!Live(AD,DR->getDecl())) {
SourceRange R = B->getRHS()->getSourceRange();
Diags.Report(DR->getSourceRange().Begin(), diag::warn_dead_store,
- 0, 0, &R, 1);
-
+ 0, 0, &R, 1);
}
}
- else if(DeclStmt* DS = dyn_cast<DeclStmt>(S)) {
- // Iterate through the decls. Warn if any of them (which have
- // initializers) are not live.
+ else if(DeclStmt* DS = dyn_cast<DeclStmt>(S))
+ // Iterate through the decls. Warn if any initializers are complex
+ // expressions that are not live (never used).
for (VarDecl* V = cast<VarDecl>(DS->getDecl()); V != NULL ;
- V = cast_or_null<VarDecl>(V->getNextDeclarator()))
- if (Expr* E = V->getInit())
- if (!L.isLive(Live,V))
+ V = cast_or_null<VarDecl>(V->getNextDeclarator())) {
+ if (Expr* E = V->getInit()) {
+ if (!Live(AD,DS->getDecl())) {
// Special case: check for initializations with constants.
//
// e.g. : int x = 0;
@@ -63,14 +70,15 @@
// If x is EVER assigned a new value later, don't issue
// a warning. This is because such initialization can be
// due to defensive programming.
- if (!E->isConstantExpr(Ctx,NULL) ||
- L.getVarInfo(V).Kills.size() == 0) {
+ if (!E->isConstantExpr(Ctx,NULL)) {
// Flag a warning.
SourceRange R = E->getSourceRange();
Diags.Report(V->getLocation(), diag::warn_dead_store, 0, 0,
&R,1);
}
- }
+ }
+ }
+ }
}
};
@@ -78,18 +86,11 @@
namespace clang {
-void CheckDeadStores(CFG& cfg, LiveVariables& L,
- ASTContext &Ctx, Diagnostic &Diags) {
- DeadStoreObserver A(Ctx, Diags);
-
- for (CFG::iterator I = cfg.begin(), E = cfg.end(); I != E; ++I)
- L.runOnBlock(&(*I),&A);
-}
-
void CheckDeadStores(CFG& cfg, ASTContext &Ctx, Diagnostic &Diags) {
LiveVariables L;
L.runOnCFG(cfg);
- CheckDeadStores(cfg,L, Ctx, Diags);
+ DeadStoreObs A(Ctx, Diags);
+ L.runOnAllBlocks(cfg,A);
}
} // end namespace clang
diff --git a/Analysis/LiveVariables.cpp b/Analysis/LiveVariables.cpp
index 2d622c4..fb4f3a6 100644
--- a/Analysis/LiveVariables.cpp
+++ b/Analysis/LiveVariables.cpp
@@ -3,7 +3,8 @@
// The LLVM Compiler Infrastructure
//
// This file was developed by Ted Kremenek and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// the University of Illinois Open Source License. See LICENSE.TXT for
+// details.
//
//===----------------------------------------------------------------------===//
//
@@ -15,7 +16,8 @@
#include "clang/Basic/SourceManager.h"
#include "clang/AST/Expr.h"
#include "clang/AST/CFG.h"
-#include "clang/Analysis/Visitors/DataflowStmtVisitor.h"
+#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h"
+#include "DataflowSolver.h"
#include "clang/Lex/IdentifierTable.h"
#include "llvm/ADT/SmallPtrSet.h"
@@ -25,326 +27,136 @@
using namespace clang;
//===----------------------------------------------------------------------===//
-// RegisterDecls - Utility class to create VarInfo objects for all
-// Decls referenced in a function.
-//
+// Dataflow initialization logic.
+//===----------------------------------------------------------------------===//
namespace {
+struct RegisterDecls : public CFGRecStmtDeclVisitor<RegisterDecls> {
+ LiveVariables::AnalysisDataTy& AD;
+ void VisitVarDecl(VarDecl* VD) { AD.RegisterDecl(VD); }
-class RegisterDecls : public StmtVisitor<RegisterDecls,void> {
- LiveVariables& L;
- const CFG& cfg;
-public:
- RegisterDecls(LiveVariables& l, const CFG& c)
- : L(l), cfg(c) {}
-
- void VisitStmt(Stmt* S);
- void VisitDeclRefExpr(DeclRefExpr* DR);
- void VisitDeclStmt(DeclStmt* DS);
- void Register(ScopedDecl* D);
- void RegisterDeclChain(ScopedDecl* D);
- void RegisterUsedDecls();
-};
-
-void RegisterDecls::VisitStmt(Stmt* S) {
- for (Stmt::child_iterator I = S->child_begin(),E = S->child_end(); I != E;++I)
- Visit(*I);
-}
-
-void RegisterDecls::VisitDeclRefExpr(DeclRefExpr* DR) {
- RegisterDeclChain(DR->getDecl());
-}
-
-void RegisterDecls::VisitDeclStmt(DeclStmt* DS) {
- RegisterDeclChain(DS->getDecl());
-}
-
-void RegisterDecls::RegisterDeclChain(ScopedDecl* D) {
- for (; D != NULL ; D = D->getNextDeclarator())
- Register(D);
-}
-
-void RegisterDecls::Register(ScopedDecl* D) {
- if (VarDecl* V = dyn_cast<VarDecl>(D)) {
- LiveVariables::VPair& VP = L.getVarInfoMap()[V];
-
- VP.V.AliveBlocks.resize(cfg.getNumBlockIDs());
- VP.Idx = L.getNumDecls()++;
- }
-}
-
-void RegisterDecls::RegisterUsedDecls() {
- for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI)
- for (CFGBlock::const_iterator SI=BI->begin(),SE = BI->end();SI != SE;++SI)
- Visit(const_cast<Stmt*>(*SI));
-}
-
-
+ RegisterDecls(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
+};
} // end anonymous namespace
-//===----------------------------------------------------------------------===//
-// WorkList - Data structure representing the liveness algorithm worklist.
-//
-
-namespace {
-
-class WorkListTy {
- typedef llvm::SmallPtrSet<const CFGBlock*,20> BlockSet;
- BlockSet wlist;
-public:
- void enqueue(const CFGBlock* B) { wlist.insert(B); }
-
- const CFGBlock* dequeue() {
- assert (!wlist.empty());
- const CFGBlock* B = *wlist.begin();
- wlist.erase(B);
- return B;
- }
-
- bool isEmpty() const { return wlist.empty(); }
-};
-
-} // end anonymous namespace
+void LiveVariables::InitializeValues(const CFG& cfg) {
+ RegisterDecls R(getAnalysisData());
+ cfg.VisitBlockStmts(R);
+}
//===----------------------------------------------------------------------===//
-// TFuncs
-//
+// Transfer functions.
+//===----------------------------------------------------------------------===//
namespace {
-
-class LivenessTFuncs : public DataflowStmtVisitor<LivenessTFuncs,
- dataflow::backward_analysis_tag> {
- LiveVariables& L;
- llvm::BitVector Live;
- llvm::BitVector KilledAtLeastOnce;
- Stmt* CurrentStmt;
- const CFGBlock* CurrentBlock;
- bool blockPreviouslyProcessed;
- LiveVariablesObserver* Observer;
-
+class TransferFuncs : public CFGStmtVisitor<TransferFuncs> {
+ LiveVariables::AnalysisDataTy& AD;
+ LiveVariables::ValTy Live;
public:
- LivenessTFuncs(LiveVariables& l, LiveVariablesObserver* A = NULL)
- : L(l), CurrentStmt(NULL), CurrentBlock(NULL),
- blockPreviouslyProcessed(false), Observer(A) {
- Live.resize(l.getNumDecls());
- KilledAtLeastOnce.resize(l.getNumDecls());
- }
+ TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad) {}
+
+ LiveVariables::ValTy& getVal() { return Live; }
void VisitDeclRefExpr(DeclRefExpr* DR);
void VisitBinaryOperator(BinaryOperator* B);
void VisitAssign(BinaryOperator* B);
void VisitDeclStmt(DeclStmt* DS);
void VisitUnaryOperator(UnaryOperator* U);
- void ObserveStmt(Stmt* S);
-
- unsigned getIdx(const VarDecl* D) {
- LiveVariables::VarInfoMap& V = L.getVarInfoMap();
- LiveVariables::VarInfoMap::iterator I = V.find(D);
- assert (I != V.end());
- return I->second.Idx;
+ void VisitStmt(Stmt* S) { VisitChildren(S); }
+ void Visit(Stmt *S) {
+ if (AD.Observer) AD.Observer->ObserveStmt(S,AD,Live);
+ static_cast<CFGStmtVisitor<TransferFuncs>*>(this)->Visit(S);
}
-
- bool ProcessBlock(const CFGBlock* B);
- llvm::BitVector* getBlockEntryLiveness(const CFGBlock* B);
- LiveVariables::VarInfo& KillVar(VarDecl* D);
};
-void LivenessTFuncs::ObserveStmt(Stmt* S) {
- if (Observer) Observer->ObserveStmt(S,L,Live);
-}
-
-void LivenessTFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
- // Register a use of the variable.
- if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl()))
- Live.set(getIdx(V));
+void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
+ if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl()))
+ Live.set(AD[V]); // Register a use of the variable.
}
-void LivenessTFuncs::VisitBinaryOperator(BinaryOperator* B) {
+void TransferFuncs::VisitBinaryOperator(BinaryOperator* B) {
if (B->isAssignmentOp()) VisitAssign(B);
else VisitStmt(B);
}
-void LivenessTFuncs::VisitUnaryOperator(UnaryOperator* U) {
+void TransferFuncs::VisitUnaryOperator(UnaryOperator* U) {
switch (U->getOpcode()) {
- case UnaryOperator::PostInc:
- case UnaryOperator::PostDec:
- case UnaryOperator::PreInc:
- case UnaryOperator::PreDec:
- case UnaryOperator::AddrOf:
- // Walk through the subexpressions, blasting through ParenExprs until
- // we either find a DeclRefExpr or some non-DeclRefExpr expression.
- for (Stmt* S = U->getSubExpr() ; ; ) {
- 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.
- LiveVariables::VarInfo& V =
- KillVar(cast<VarDecl>(DR->getDecl()));
+ case UnaryOperator::PostInc:
+ case UnaryOperator::PostDec:
+ case UnaryOperator::PreInc:
+ case UnaryOperator::PreDec:
+ case UnaryOperator::AddrOf:
+ // Walk through the subexpressions, blasting through ParenExprs
+ // until we either find a DeclRefExpr or some non-DeclRefExpr
+ // expression.
+ for (Stmt* S = U->getSubExpr() ;;) {
+ 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);
+ }
+ else Visit(S);
- if (!blockPreviouslyProcessed)
- V.AddKill(CurrentStmt,DR);
-
- VisitDeclRefExpr(DR);
- }
- else Visit(S);
-
- break;
- }
- break;
-
- default:
- Visit(U->getSubExpr());
- break;
+ break;
+ }
+ break;
+
+ default:
+ Visit(U->getSubExpr());
+ break;
}
}
-LiveVariables::VarInfo& LivenessTFuncs::KillVar(VarDecl* D) {
- LiveVariables::VarInfoMap::iterator I = L.getVarInfoMap().find(D);
-
- assert (I != L.getVarInfoMap().end() &&
- "Declaration not managed by variable map in LiveVariables");
-
- // Mark the variable dead, and remove the current block from
- // the set of blocks where the variable may be alive the entire time.
- Live.reset(I->second.Idx);
- I->second.V.AliveBlocks.reset(CurrentBlock->getBlockID());
-
- return I->second.V;
-}
-
-void LivenessTFuncs::VisitAssign(BinaryOperator* B) {
- // Check if we are assigning to a variable.
+void TransferFuncs::VisitAssign(BinaryOperator* B) {
Stmt* LHS = B->getLHS();
-
- if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS)) {
- LiveVariables::VarInfo& V = KillVar(cast<VarDecl>(DR->getDecl()));
-
- // We only need to register kills once, so we check if this block
- // has been previously processed.
- if (!blockPreviouslyProcessed)
- V.AddKill(CurrentStmt,DR);
-
- if (B->getOpcode() != BinaryOperator::Assign)
- Visit(LHS);
+
+ if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS)) { // Assigning to a var?
+ Live.reset(AD[DR->getDecl()]);
+ 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);
}
- else
+ else // Not assigning to a variable. Process LHS as usual.
Visit(LHS);
- Visit(B->getRHS());
+ Visit(B->getRHS());
}
-void LivenessTFuncs::VisitDeclStmt(DeclStmt* DS) {
- // Declarations effectively "kill" a variable since they cannot possibly
- // be live before they are declared. Declarations, however, are not kills
- // in the sense that the value is obliterated, so we do not register
- // DeclStmts as a "kill site" for a variable.
+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())
- KillVar(cast<VarDecl>(D));
+ Live.reset(AD[D]);
}
-
-llvm::BitVector* LivenessTFuncs::getBlockEntryLiveness(const CFGBlock* B) {
- LiveVariables::BlockLivenessMap& BMap = L.getLiveAtBlockEntryMap();
-
- LiveVariables::BlockLivenessMap::iterator I = BMap.find(B);
- return (I == BMap.end()) ? NULL : &(I->second);
-}
-
-
-bool LivenessTFuncs::ProcessBlock(const CFGBlock* B) {
-
- CurrentBlock = B;
- Live.reset();
- KilledAtLeastOnce.reset();
-
- // Check if this block has been previously processed.
- LiveVariables::BlockLivenessMap& BMap = L.getLiveAtBlockEntryMap();
- LiveVariables::BlockLivenessMap::iterator BI = BMap.find(B);
-
- blockPreviouslyProcessed = BI != BMap.end();
-
- // Merge liveness information from all predecessors.
- for (CFGBlock::const_succ_iterator I=B->succ_begin(),E=B->succ_end();I!=E;++I)
- if (llvm::BitVector* V = getBlockEntryLiveness(*I))
- Live |= *V;
-
- if (Observer)
- Observer->ObserveBlockExit(B,L,Live);
-
- // Tentatively mark all variables alive at the end of the current block
- // as being alive during the whole block. We then cull these out as
- // we process the statements of this block.
- for (LiveVariables::VarInfoMap::iterator
- I=L.getVarInfoMap().begin(), E=L.getVarInfoMap().end(); I != E; ++I)
- if (Live[I->second.Idx])
- I->second.V.AliveBlocks.set(B->getBlockID());
-
- // Visit the statements in reverse order;
- VisitBlock(B);
-
- // Compare the computed "Live" values with what we already have
- // for the entry to this block.
- bool hasChanged = false;
-
- if (!blockPreviouslyProcessed) {
- // We have not previously calculated liveness information for this block.
- // Lazily instantiate a bitvector, and copy the bits from Live.
- hasChanged = true;
- llvm::BitVector& V = BMap[B];
- V.resize(L.getNumDecls());
- V = Live;
- }
- else if (BI->second != Live) {
- hasChanged = true;
- BI->second = Live;
- }
-
- return hasChanged;
-}
-
} // end anonymous namespace
-//===----------------------------------------------------------------------===//
-// runOnCFG - Method to run the actual liveness computation.
-//
+namespace {
+struct Merge {
+ void operator()(LiveVariables::ValTy& Dst, LiveVariables::ValTy& Src) {
+ Src |= Dst;
+ }
+};
+} // end anonymous namespace
-void LiveVariables::runOnCFG(const CFG& cfg, LiveVariablesObserver* Observer) {
- // Scan a CFG for DeclRefStmts. For each one, create a VarInfo object.
- {
- RegisterDecls R(*this,cfg);
- R.RegisterUsedDecls();
- }
-
- // Create the worklist and enqueue the exit block.
- WorkListTy WorkList;
- WorkList.enqueue(&cfg.getExit());
-
- // Create the state for transfer functions.
- LivenessTFuncs TF(*this,Observer);
-
- // Process the worklist until it is empty.
-
- while (!WorkList.isEmpty()) {
- const CFGBlock* B = WorkList.dequeue();
- if (TF.ProcessBlock(B))
- for (CFGBlock::const_pred_iterator I = B->pred_begin(), E = B->pred_end();
- I != E; ++I)
- WorkList.enqueue(*I);
- }
-
- // Go through each block and reserve a bitvector. This is needed if
- // a block was never visited by the worklist algorithm.
- for (CFG::const_iterator I = cfg.begin(), E = cfg.end(); I != E; ++I)
- LiveAtBlockEntryMap[&(*I)].resize(NumDecls);
+namespace {
+typedef DataflowSolver<LiveVariables,TransferFuncs,Merge> Solver;
}
+void LiveVariables::runOnCFG(const CFG& cfg) {
+ Solver S(*this);
+ S.runOnCFG(cfg);
+}
-void LiveVariables::runOnBlock(const CFGBlock* B,
- LiveVariablesObserver* Observer)
-{
- LivenessTFuncs TF(*this,Observer);
- TF.ProcessBlock(B);
+void LiveVariables::runOnAllBlocks(const CFG& cfg,
+ LiveVariables::ObserverTy& Obs) {
+ Solver S(*this);
+ ObserverTy* OldObserver = getAnalysisData().Observer;
+ getAnalysisData().Observer = &Obs;
+ S.runOnAllBlocks(cfg);
+ getAnalysisData().Observer = OldObserver;
}
//===----------------------------------------------------------------------===//
@@ -352,81 +164,36 @@
//
bool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const {
- BlockLivenessMap::const_iterator I = LiveAtBlockEntryMap.find(B);
- assert (I != LiveAtBlockEntryMap.end());
-
- VarInfoMap::const_iterator VI = VarInfos.find(D);
- assert (VI != VarInfos.end());
-
- return I->second[VI->second.Idx];
+ return getBlockData(B)[ getAnalysisData()[D] ];
}
-bool LiveVariables::isLive(llvm::BitVector& Live, const VarDecl* D) const {
- VarInfoMap::const_iterator VI = VarInfos.find(D);
- assert (VI != VarInfos.end());
- return Live[VI->second.Idx];
+bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const {
+ return Live[ getAnalysisData()[D] ];
}
-bool LiveVariables::KillsVar(const Stmt* S, const VarDecl* D) const {
- VarInfoMap::const_iterator VI = VarInfos.find(D);
- assert (VI != VarInfos.end());
-
- for (VarInfo::KillsSet::const_iterator
- I = VI->second.V.Kills.begin(), E = VI->second.V.Kills.end(); I!=E;++I)
- if (I->first == S)
- return true;
-
- return false;
-}
-
-LiveVariables::VarInfo& LiveVariables::getVarInfo(const VarDecl* D) {
- VarInfoMap::iterator VI = VarInfos.find(D);
- assert (VI != VarInfos.end());
- return VI->second.V;
-}
-
-const LiveVariables::VarInfo& LiveVariables::getVarInfo(const VarDecl* D) const{
- return const_cast<LiveVariables*>(this)->getVarInfo(D);
-}
-
-//===----------------------------------------------------------------------===//
-// Defaults for LiveVariablesObserver
-
-void LiveVariablesObserver::ObserveStmt(Stmt* S, LiveVariables& L,
- llvm::BitVector& V) {}
-
-void LiveVariablesObserver::ObserveBlockExit(const CFGBlock* B,
- LiveVariables& L,
- llvm::BitVector& V) {}
-
//===----------------------------------------------------------------------===//
// printing liveness state for debugging
//
-void LiveVariables::dumpLiveness(const llvm::BitVector& V,
- SourceManager& SM) const {
-
- for (VarInfoMap::iterator I = VarInfos.begin(), E=VarInfos.end(); I!=E; ++I) {
- if (V[I->second.Idx]) {
-
+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]) {
SourceLocation PhysLoc = SM.getPhysicalLoc(I->first->getLocation());
-
+
fprintf(stderr, " %s <%s:%u:%u>\n",
I->first->getIdentifier()->getName(),
SM.getSourceName(PhysLoc),
SM.getLineNumber(PhysLoc),
SM.getColumnNumber(PhysLoc));
}
- }
}
void LiveVariables::dumpBlockLiveness(SourceManager& M) const {
- for (BlockLivenessMap::iterator I = LiveAtBlockEntryMap.begin(),
- E = LiveAtBlockEntryMap.end();
- I != E; ++I) {
-
- fprintf(stderr,
- "\n[ B%d (live variables at block entry) ]\n",
+ for (BlockDataMapTy::iterator I = getBlockDataMap().begin(),
+ E = getBlockDataMap().end(); I!=E; ++I) {
+ fprintf(stderr, "\n[ B%d (live variables at block exit) ]\n",
I->first->getBlockID());
dumpLiveness(I->second,M);
@@ -434,41 +201,3 @@
fprintf(stderr,"\n");
}
-
-void LiveVariables::dumpVarLiveness(SourceManager& SM) const {
-
- for (VarInfoMap::iterator I = VarInfos.begin(), E=VarInfos.end(); I!=E; ++I) {
- SourceLocation PhysLoc = SM.getPhysicalLoc(I->first->getLocation());
-
- fprintf(stderr, "[ %s <%s:%u:%u> ]\n",
- I->first->getIdentifier()->getName(),
- SM.getSourceName(PhysLoc),
- SM.getLineNumber(PhysLoc),
- SM.getColumnNumber(PhysLoc));
-
- I->second.V.Dump(SM);
- }
-}
-
-void LiveVariables::VarInfo::Dump(SourceManager& SM) const {
- fprintf(stderr," Blocks Alive:");
- for (unsigned i = 0; i < AliveBlocks.size(); ++i) {
- if (i % 5 == 0)
- fprintf(stderr,"\n ");
-
- fprintf(stderr," B%d", i);
- }
-
- fprintf(stderr,"\n Kill Sites:\n");
- for (KillsSet::const_iterator I = Kills.begin(), E = Kills.end(); I!=E; ++I) {
- SourceLocation PhysLoc =
- SM.getPhysicalLoc(I->second->getSourceRange().Begin());
-
- fprintf(stderr, " <%s:%u:%u>\n",
- SM.getSourceName(PhysLoc),
- SM.getLineNumber(PhysLoc),
- SM.getColumnNumber(PhysLoc));
- }
-
- fprintf(stderr,"\n");
-}