*** empty log message ***

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@291 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 189 insertions, 0 deletions

diff --git a/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp b/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp
new file mode 100644
index 0000000000..b4126b0029
--- /dev/null
+++ b/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp
@@ -0,0 +1,189 @@
+/* Title:   ValueSet.h
+   Author:  Ruchira Sasanka
+   Date:    Jun 30, 01
+   Purpose: 
+
+   This is the interface for live variable info of a method that is required by 
+   any other part of the compiler.
+
+*/
+
+
+#include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
+
+
+
+
+/************************** Constructor/Destructor ***************************/
+
+
+MethodLiveVarInfo::MethodLiveVarInfo(Method *const MethPtr) :  BB2BBLVMap()  
+{
+  Meth = MethPtr;  // init BB2BBLVMap and records Method for future use
+}
+
+
+
+MethodLiveVarInfo:: ~MethodLiveVarInfo()
+{
+  BBToBBLiveVarMapType::iterator HMI = BB2BBLVMap.begin();   // hash map iterator
+
+  for( ; HMI != BB2BBLVMap.end() ; HMI ++ ) {  
+    if( (*HMI).first )                    // delete all LiveVarSets in BB2BBLVMap
+      delete (*HMI).second;
+   }
+}
+
+
+// -------------------------- support functions -------------------------------
+
+
+
+                                // constructs BBLiveVars and init Def and In sets
+void MethodLiveVarInfo::constructBBs()   
+{
+  unsigned int POId = 0;   // Reverse Depth-first Order ID
+
+  cfg::po_const_iterator BBI = cfg::po_begin(Meth);
+
+  for(  ; BBI != cfg::po_end(Meth) ; ++BBI, ++POId) 
+  { 
+
+    if(DEBUG_LV) cout << "-- For BB " << (*BBI)->getName() << ":" << endl ;
+
+    const BasicBlock *BB = *BBI;      // get the current BB 
+    BBLiveVar * LVBB = new BBLiveVar( BB, POId );  // create a new BBLiveVar
+    
+    BB2BBLVMap[ BB ] = LVBB;  // insert the pair to Map
+    
+    LVBB->calcDefUseSets();  // calculates the def and in set
+
+    if(DEBUG_LV) LVBB->printAllSets();
+    //cout << "InSetChanged: " << LVBB->isInSetChanged() << endl; 
+  }
+
+ 
+}
+
+                                             // do one backward pass over the CFG
+bool MethodLiveVarInfo::doSingleBackwardPass()  
+{
+  bool ResultFlow, NeedAnotherIteration = false;
+
+  if(DEBUG_LV) cout << endl <<  "------- After Backward Pass --------" << endl;
+
+  cfg::po_const_iterator BBI = cfg::po_begin(Meth);
+
+  for( ; BBI != cfg::po_end(Meth) ; ++BBI) 
+  { 
+
+    BBLiveVar* LVBB = BB2BBLVMap[*BBI];
+    assert( LVBB );
+
+    if(DEBUG_LV) cout << "-- For BB " << (*BBI)->getName() << ":"  << endl;
+    // cout << " (POId=" << LVBB->getPOId() << ")" << endl ;
+
+    ResultFlow = false;
+
+    if( LVBB->isOutSetChanged() ) 
+      LVBB->applyTransferFunc();   // apply the Transfer Func to calc the InSet
+    if( LVBB->isInSetChanged() )  
+      ResultFlow = LVBB->applyFlowFunc( BB2BBLVMap ); // to calc Outsets of preds
+
+    if(DEBUG_LV) LVBB->printInOutSets();
+    //cout << "InChanged = " << LVBB->isInSetChanged() 
+    //cout << "   UpdatedBBwithLowerPOId = " << ResultFlow  << endl;
+
+    if( ResultFlow ) NeedAnotherIteration = true;
+
+  }
+
+  return NeedAnotherIteration; // true if we need to reiterate over the CFG
+}
+
+
+
+
+
+void MethodLiveVarInfo::analyze()          // performs live var anal for a method
+{
+  //cout << "In analyze . . ." << cout;
+
+  constructBBs();          // create and initialize all the BBLiveVars of the CFG
+
+  bool NeedAnotherIteration = false;
+  do {
+    NeedAnotherIteration = doSingleBackwardPass( );   // do one  pass over  CFG
+  } while (NeedAnotherIteration );      // repeat until we need more iterations
+}
+
+
+
+
+/* This function will give the LiveVar info for any instruction in a method. It 
+   should be called after a call to analyze().
+
+   This function calucluates live var info for all the instructions in a BB, 
+   when LVInfo for one inst is requested. Hence, this function is useful when 
+   live var info is required for many (or all) instructions in a basic block
+   Also, the arguments to this method does not require specific iterators
+*/
+
+
+const LiveVarSet * 
+MethodLiveVarInfo::getLiveVarSetBeforeInst(const Instruction *const Inst) 
+{
+                                   // get the BB corresponding to the instruction
+  const BasicBlock *const CurBB = Inst->getParent();  
+
+  const LiveVarSet *LVSet = Inst2LVSetMap[Inst];
+
+  if( LVSet  ) return LVSet;                     // if found, just return the set
+
+  const BasicBlock::InstListType&  InstListInBB = CurBB->getInstList();         
+  BasicBlock::InstListType::const_reverse_iterator 
+    InstItEnd= InstListInBB.rend() - 1;    // InstItEnd is set to the first instr
+
+                                                  // LVSet of first instr = InSet
+  Inst2LVSetMap[*InstItEnd] = getInSetOfBB( CurBB );  
+
+                  // if the first instruction is requested, just return the InSet
+  if( Inst == *InstItEnd) return  Inst2LVSetMap[Inst];      
+
+                 // else calculate for all other instruction in the BB
+
+  BasicBlock::InstListType::const_reverse_iterator 
+    InstIt= InstListInBB.rbegin();  // get the iterator for instructions in BB
+
+  LiveVarSet *CurSet = new LiveVarSet();
+  CurSet->setUnion( getOutSetOfBB( CurBB ));   // LVSet now contains the OutSet
+
+    // calculate LVSet for all instructions in the basic block (except the first)
+  for( ; InstIt != InstItEnd ;  InstIt++) {    
+
+    CurSet->applyTranferFuncForInst( *InstIt );  // apply the transfer Func
+    LiveVarSet *NewSet = new LiveVarSet();       // create a new set and
+    NewSet->setUnion( CurSet );                  // copy the set after T/F to it 
+    Inst2LVSetMap[*InstIt] = NewSet;             // record that in the map
+  }
+
+  return Inst2LVSetMap[Inst];
+}
+
+
+
+/*
+NOTES: delete all the LVBBs allocated by adding a destructor to the BB2BBLVMap???
+            use the dfo_iterator in the doSingleBackwardPass  
+*/
+
+
+
+
+
+
+
+
+
+
+