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/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");
-}