diff options
Diffstat (limited to 'Analysis/LiveVariables.cpp')
| -rw-r--r-- | Analysis/LiveVariables.cpp | 473 |
1 files changed, 101 insertions, 372 deletions
diff --git a/Analysis/LiveVariables.cpp b/Analysis/LiveVariables.cpp index 2d622c40b7..fb4f3a681f 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()++; - } -} + RegisterDecls(LiveVariables::AnalysisDataTy& ad) : AD(ad) {} +}; +} // end anonymous namespace -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)); +void LiveVariables::InitializeValues(const CFG& cfg) { + RegisterDecls R(getAnalysisData()); + cfg.VisitBlockStmts(R); } - - -} // end anonymous namespace //===----------------------------------------------------------------------===// -// WorkList - Data structure representing the liveness algorithm worklist. -// +// Transfer functions. +//===----------------------------------------------------------------------===// namespace { - -class WorkListTy { - typedef llvm::SmallPtrSet<const CFGBlock*,20> BlockSet; - BlockSet wlist; +class TransferFuncs : public CFGStmtVisitor<TransferFuncs> { + LiveVariables::AnalysisDataTy& AD; + LiveVariables::ValTy Live; 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 + TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad) {} -//===----------------------------------------------------------------------===// -// TFuncs -// - -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; - -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()); - } + 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())); - - if (!blockPreviouslyProcessed) - V.AddKill(CurrentStmt,DR); - - VisitDeclRefExpr(DR); - } - else Visit(S); - - break; - } - break; - - default: - Visit(U->getSubExpr()); - break; + 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); + + 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]); } +} // end anonymous namespace -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; +namespace { +struct Merge { + void operator()(LiveVariables::ValTy& Dst, LiveVariables::ValTy& Src) { + Src |= Dst; } - - return hasChanged; -} - +}; } // end anonymous namespace -//===----------------------------------------------------------------------===// -// runOnCFG - Method to run the actual liveness computation. -// - -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 @@ void LiveVariables::runOnBlock(const CFGBlock* B, // 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 @@ void LiveVariables::dumpBlockLiveness(SourceManager& M) const { 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"); -} |