LiveVariables:
- Finished 99% of analysis logic. Probably a few bugs.
- Added querying functions to query liveness.
- Added better pretty printing of liveness.
- Added better bookkeeping of per-variable liveness information.
- Added LiveVariablesAuditor interface, which allows "lazy" querying
of intra-basic block liveness information.
Driver:
- Minor cleanups involved in dumping liveness information.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@41753 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/Analysis/LiveVariables.cpp b/Analysis/LiveVariables.cpp
index 83c9b98..6290651 100644
--- a/Analysis/LiveVariables.cpp
+++ b/Analysis/LiveVariables.cpp
@@ -12,13 +12,15 @@
//===----------------------------------------------------------------------===//
#include "clang/Analysis/LiveVariables.h"
+#include "clang/Basic/SourceManager.h"
#include "clang/AST/Expr.h"
#include "clang/AST/CFG.h"
#include "clang/AST/StmtVisitor.h"
#include "clang/Lex/IdentifierTable.h"
#include "llvm/ADT/SmallPtrSet.h"
-#include <iostream>
+#include <string.h>
+#include <stdio.h>
using namespace clang;
@@ -101,11 +103,18 @@
class LivenessTFuncs : public StmtVisitor<LivenessTFuncs,void> {
LiveVariables& L;
llvm::BitVector Live;
- llvm::BitVector Killed;
+ llvm::BitVector KilledAtLeastOnce;
+ Stmt* CurrentStmt;
+ const CFGBlock* CurrentBlock;
+ bool blockPreviouslyProcessed;
+ LiveVariablesAuditor* Auditor;
public:
- LivenessTFuncs(LiveVariables& l) : L(l) {
+ LivenessTFuncs(LiveVariables& l, LiveVariablesAuditor* A = NULL)
+ : L(l), CurrentStmt(NULL), CurrentBlock(NULL),
+ blockPreviouslyProcessed(false), Auditor(A)
+ {
Live.resize(l.getNumDecls());
- Killed.resize(l.getNumDecls());
+ KilledAtLeastOnce.resize(l.getNumDecls());
}
void VisitStmt(Stmt* S);
@@ -113,6 +122,8 @@
void VisitBinaryOperator(BinaryOperator* B);
void VisitAssign(BinaryOperator* B);
void VisitStmtExpr(StmtExpr* S);
+ void VisitDeclStmt(DeclStmt* DS);
+ void VisitUnaryOperator(UnaryOperator* U);
unsigned getIdx(const Decl* D) {
LiveVariables::VarInfoMap& V = L.getVarInfoMap();
@@ -122,19 +133,25 @@
}
bool ProcessBlock(const CFGBlock* B);
- llvm::BitVector* getLiveness(const CFGBlock* B);
-
+ llvm::BitVector* getBlockEntryLiveness(const CFGBlock* B);
+ LiveVariables::VarInfo& KillVar(Decl* D);
};
void LivenessTFuncs::VisitStmt(Stmt* S) {
+ if (Auditor)
+ Auditor->AuditStmt(S,L,Live);
+
// Evaluate the transfer functions for all subexpressions. Note that
// each invocation of "Visit" will have a side-effect: "Liveness" and "Kills"
- // will be updated.
+ // will be updated.
for (Stmt::child_iterator I = S->child_begin(),E = S->child_end(); I != E;++I)
Visit(*I);
}
void LivenessTFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
+ if (Auditor)
+ Auditor->AuditStmt(DR,L,Live);
+
// Register a use of the variable.
Live.set(getIdx(DR->getDecl()));
}
@@ -151,33 +168,101 @@
case BinaryOperator::Comma:
// Do nothing. These operations are broken up into multiple
// statements in the CFG. All these expressions do is return
- // the value of their subexpressions, but these expressions will
+ // the value of their subexpressions, but these subexpressions will
// be evalualated elsewhere in the CFG.
break;
// FIXME: handle '++' and '--'
- default:
+ default:
if (B->isAssignmentOp()) VisitAssign(B);
- else Visit(B);
+ else VisitStmt(B);
}
}
+void LivenessTFuncs::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(DR->getDecl());
+
+ if (!blockPreviouslyProcessed)
+ V.AddKill(CurrentStmt,DR);
+
+ VisitDeclRefExpr(DR);
+ }
+ else
+ Visit(S);
+
+ break;
+ }
+ break;
+
+ default:
+ VisitStmt(U->getSubExpr());
+ break;
+ }
+}
+
+LiveVariables::VarInfo& LivenessTFuncs::KillVar(Decl* 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) {
+ if (Auditor)
+ Auditor->AuditStmt(B,L,Live);
+
+ // Check if we are assigning to a variable.
Stmt* LHS = B->getLHS();
-
+
if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS)) {
- unsigned i = getIdx(DR->getDecl());
- Live.reset(i);
- Killed.set(i);
+ LiveVariables::VarInfo& V = KillVar(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);
}
- else Visit(LHS);
+ else
+ Visit(LHS);
Visit(B->getRHS());
}
+void LivenessTFuncs::VisitDeclStmt(DeclStmt* DS) {
+ if (Auditor)
+ Auditor->AuditStmt(DS,L,Live);
+
+ // 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.
+ for (Decl* D = DS->getDecl(); D != NULL ; D = D->getNextDeclarator())
+ KillVar(D);
+}
-llvm::BitVector* LivenessTFuncs::getLiveness(const CFGBlock* B) {
+llvm::BitVector* LivenessTFuncs::getBlockEntryLiveness(const CFGBlock* B) {
LiveVariables::BlockLivenessMap& BMap = L.getLiveAtBlockEntryMap();
LiveVariables::BlockLivenessMap::iterator I = BMap.find(B);
@@ -185,34 +270,55 @@
}
bool LivenessTFuncs::ProcessBlock(const CFGBlock* B) {
- // First: merge all predecessors.
+
+ CurrentBlock = B;
Live.reset();
- Killed.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 = getLiveness(*I))
+ if (llvm::BitVector* V = getBlockEntryLiveness(*I))
Live |= *V;
+
+ if (Auditor)
+ Auditor->AuditBlockExit(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());
- // Second: march up the statements and process the transfer functions.
+ // March up the statements and process the transfer functions.
for (CFGBlock::const_reverse_iterator I=B->rbegin(), E=B->rend(); I!=E; ++I) {
- Visit(*I);
+ CurrentStmt = *I;
+ Visit(CurrentStmt);
}
- // Third: compare the computed "Live" values with what we already have
- // for this block.
+ // Compare the computed "Live" values with what we already have
+ // for the entry to this block.
bool hasChanged = false;
+
- LiveVariables::BlockLivenessMap& BMap = L.getLiveAtBlockEntryMap();
- LiveVariables::BlockLivenessMap::iterator I = BMap.find(B);
- if (I == BMap.end()) {
+ 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;
+ V = Live;
}
- else if (I->second != Live) {
+ else if (BI->second != Live) {
hasChanged = true;
- I->second = Live;
+ BI->second = Live;
}
return hasChanged;
@@ -224,7 +330,7 @@
// runOnCFG - Method to run the actual liveness computation.
//
-void LiveVariables::runOnCFG(const CFG& cfg) {
+void LiveVariables::runOnCFG(const CFG& cfg, LiveVariablesAuditor* Auditor) {
// Scan a CFG for DeclRefStmts. For each one, create a VarInfo object.
{
RegisterDecls R(*this,cfg);
@@ -236,7 +342,7 @@
WorkList.enqueue(&cfg.getExit());
// Create the state for transfer functions.
- LivenessTFuncs TF(*this);
+ LivenessTFuncs TF(*this,Auditor);
// Process the worklist until it is empty.
@@ -248,35 +354,86 @@
WorkList.enqueue(*I);
}
- // Go through each block and reserve a bitvector.
+ // 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);
}
+
+void LiveVariables::runOnBlock(const CFGBlock* B, LiveVariablesAuditor* Auditor)
+{
+ assert (NumDecls && "You must use runOnCFG before using runOnBlock.");
+ LivenessTFuncs TF(*this,Auditor);
+ TF.ProcessBlock(B);
+}
+
+//===----------------------------------------------------------------------===//
+// liveness queries
+//
+
+bool LiveVariables::IsLive(const CFGBlock* B, const Decl* 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];
+}
+
+bool LiveVariables::KillsVar(const Stmt* S, const Decl* 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 Decl* D) {
+ VarInfoMap::iterator VI = VarInfos.find(D);
+ assert (VI != VarInfos.end());
+ return VI->second.V;
+}
+
+const LiveVariables::VarInfo& LiveVariables::getVarInfo(const Decl* D) const {
+ return const_cast<LiveVariables*>(this)->getVarInfo(D);
+}
+
//===----------------------------------------------------------------------===//
// printing liveness state for debugging
//
-void LiveVariables::printLiveness(const llvm::BitVector& V,
- std::ostream& OS) const {
+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]) {
- OS << I->first->getIdentifier()->getName() << "\n";
+
+ 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::printBlockLiveness(std::ostream& OS) const {
+void LiveVariables::dumpBlockLiveness(SourceManager& M) const {
for (BlockLivenessMap::iterator I = LiveAtBlockEntryMap.begin(),
E = LiveAtBlockEntryMap.end();
I != E; ++I) {
- OS << "\n[ B" << I->first->getBlockID()
- << " (live variables at block entry) ]\n";
- printLiveness(I->second, OS);
- }
-}
-void LiveVariables::DumpBlockLiveness() const {
- printBlockLiveness(std::cerr);
+ fprintf(stderr,
+ "\n[ B%d (live variables at block entry) ]\n",
+ I->first->getBlockID());
+
+ dumpLiveness(I->second,M);
+ }
}
\ No newline at end of file