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

1 files changed, 282 insertions, 0 deletions

diff --git a/Analysis/LiveVariables.cpp b/Analysis/LiveVariables.cpp
new file mode 100644
index 0000000000..83c9b98044
--- /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