Added an early implementation of Live-Variables analysis built on
source-level CFGs. This code may change significantly in the near
future as we explore different means to implement dataflow analyses.
Added a driver option, -dump-live-variables, to view the output of
live variable analysis. This output is very ALPHA; it will be improved shortly.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@41737 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/Analysis/LiveVariables.cpp b/Analysis/LiveVariables.cpp
new file mode 100644
index 0000000..83c9b98
--- /dev/null
+++ b/Analysis/LiveVariables.cpp
@@ -0,0 +1,282 @@
+//==- LiveVariables.cpp - Live Variable Analysis for Source CFGs -*- C++ --*-==//
+//
+// 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.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements Live Variables analysis for source-level CFGs.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/LiveVariables.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>
+
+using namespace clang;
+
+//===----------------------------------------------------------------------===//
+// RegisterDecls - Utility class to create VarInfo objects for all
+// Decls referenced in a function.
+//
+
+namespace {
+
+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 Register(Decl* 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) {
+ for (Decl* D = DR->getDecl() ; D != NULL ; D = D->getNextDeclarator())
+ Register(D);
+}
+
+void RegisterDecls::Register(Decl* D) {
+ LiveVariables::VPair& VP = L.getVarInfoMap()[const_cast<const Decl*>(D)];
+
+ VP.V.AliveBlocks.reserve(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));
+}
+
+
+} // 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
+
+//===----------------------------------------------------------------------===//
+// TFuncs
+//
+
+namespace {
+
+class LivenessTFuncs : public StmtVisitor<LivenessTFuncs,void> {
+ LiveVariables& L;
+ llvm::BitVector Live;
+ llvm::BitVector Killed;
+public:
+ LivenessTFuncs(LiveVariables& l) : L(l) {
+ Live.resize(l.getNumDecls());
+ Killed.resize(l.getNumDecls());
+ }
+
+ void VisitStmt(Stmt* S);
+ void VisitDeclRefExpr(DeclRefExpr* DR);
+ void VisitBinaryOperator(BinaryOperator* B);
+ void VisitAssign(BinaryOperator* B);
+ void VisitStmtExpr(StmtExpr* S);
+
+ unsigned getIdx(const Decl* D) {
+ LiveVariables::VarInfoMap& V = L.getVarInfoMap();
+ LiveVariables::VarInfoMap::iterator I = V.find(D);
+ assert (I != V.end());
+ return I->second.Idx;
+ }
+
+ bool ProcessBlock(const CFGBlock* B);
+ llvm::BitVector* getLiveness(const CFGBlock* B);
+
+};
+
+void LivenessTFuncs::VisitStmt(Stmt* S) {
+ // Evaluate the transfer functions for all subexpressions. Note that
+ // each invocation of "Visit" will have a side-effect: "Liveness" and "Kills"
+ // 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) {
+ // Register a use of the variable.
+ Live.set(getIdx(DR->getDecl()));
+}
+
+void LivenessTFuncs::VisitStmtExpr(StmtExpr* S) {
+ // Do nothing. The substatements of S are segmented into separate
+ // statements in the CFG.
+}
+
+void LivenessTFuncs::VisitBinaryOperator(BinaryOperator* B) {
+ switch (B->getOpcode()) {
+ case BinaryOperator::LAnd:
+ case BinaryOperator::LOr:
+ 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
+ // be evalualated elsewhere in the CFG.
+ break;
+
+ // FIXME: handle '++' and '--'
+ default:
+ if (B->isAssignmentOp()) VisitAssign(B);
+ else Visit(B);
+ }
+}
+
+
+void LivenessTFuncs::VisitAssign(BinaryOperator* B) {
+ Stmt* LHS = B->getLHS();
+
+ if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS)) {
+ unsigned i = getIdx(DR->getDecl());
+ Live.reset(i);
+ Killed.set(i);
+ }
+ else Visit(LHS);
+
+ Visit(B->getRHS());
+}
+
+
+llvm::BitVector* LivenessTFuncs::getLiveness(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) {
+ // First: merge all predecessors.
+ Live.reset();
+ Killed.reset();
+
+ for (CFGBlock::const_succ_iterator I=B->succ_begin(),E=B->succ_end();I!=E;++I)
+ if (llvm::BitVector* V = getLiveness(*I))
+ Live |= *V;
+
+ // Second: 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);
+ }
+
+ // Third: compare the computed "Live" values with what we already have
+ // for this block.
+ bool hasChanged = false;
+
+ LiveVariables::BlockLivenessMap& BMap = L.getLiveAtBlockEntryMap();
+ LiveVariables::BlockLivenessMap::iterator I = BMap.find(B);
+ if (I == BMap.end()) {
+ hasChanged = true;
+ llvm::BitVector& V = BMap[B];
+ V.resize(L.getNumDecls());
+ V |= Live;
+ }
+ else if (I->second != Live) {
+ hasChanged = true;
+ I->second = Live;
+ }
+
+ return hasChanged;
+}
+
+} // end anonymous namespace
+
+//===----------------------------------------------------------------------===//
+// runOnCFG - Method to run the actual liveness computation.
+//
+
+void LiveVariables::runOnCFG(const CFG& cfg) {
+ // 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);
+
+ // 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.
+ for (CFG::const_iterator I = cfg.begin(), E = cfg.end(); I != E; ++I)
+ LiveAtBlockEntryMap[&(*I)].resize(NumDecls);
+}
+
+//===----------------------------------------------------------------------===//
+// printing liveness state for debugging
+//
+
+void LiveVariables::printLiveness(const llvm::BitVector& V,
+ std::ostream& OS) const {
+
+ for (VarInfoMap::iterator I = VarInfos.begin(), E=VarInfos.end(); I!=E; ++I) {
+ if (V[I->second.Idx]) {
+ OS << I->first->getIdentifier()->getName() << "\n";
+ }
+ }
+}
+
+void LiveVariables::printBlockLiveness(std::ostream& OS) 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);
+}
\ No newline at end of file