*** empty log message ***
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@291 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/LiveVar/BBLiveVar.cpp b/lib/Analysis/LiveVar/BBLiveVar.cpp
new file mode 100644
index 0000000..aeb7f91
--- /dev/null
+++ b/lib/Analysis/LiveVar/BBLiveVar.cpp
@@ -0,0 +1,158 @@
+#include "llvm/Analysis/LiveVar/BBLiveVar.h"
+
+
+/********************* Implementation **************************************/
+
+BBLiveVar::BBLiveVar( const BasicBlock* baseBB, unsigned int RdfoId)
+ : DefSet(), InSet(), OutSet(), PhiArgMap() {
+ BaseBB = baseBB;
+ InSetChanged = OutSetChanged = false;
+ POId = RdfoId;
+}
+
+
+
+void BBLiveVar::calcDefUseSets() // caluculates def and use sets for each BB
+{
+ // instructions in basic block
+ const BasicBlock::InstListType& InstListInBB = BaseBB->getInstList();
+
+ BasicBlock::InstListType::const_reverse_iterator
+ InstIterator = InstListInBB.rbegin(); // get the iterator for instructions
+
+ // iterate over all the instructions in BB
+ for( ; InstIterator != InstListInBB.rend(); InstIterator++) {
+
+ const Instruction * Inst = *InstIterator; // Inst is the current instr
+ assert(Inst);
+
+ if( Inst->isDefinition() ) { // add to Defs only if this instr is a def
+
+ DefSet.add( Inst ); // nstruction is a def - so add to def set
+ InSet.remove( Inst); // this definition kills any uses
+ InSetChanged = true;
+ //cout << " adding inst to def "; printValue( Inst ); cout << endl;
+ }
+
+ Instruction::op_const_iterator
+ OpI = Inst->op_begin(); // get iterator for operands
+
+ bool IsPhi=( Inst->getOpcode() == Instruction::PHINode ); // Is this a phi
+
+ for(int OpNum=0 ; OpI != Inst->op_end() ; OpI++) { // iterate over operands
+
+ if ( ((*OpI)->getType())->isLabelType() )
+ continue; // don't process labels
+
+ InSet.add( *OpI ); // An operand is a use - so add to use set
+ OutSet.remove( *OpI ); // remove if there is a definition below this use
+
+ if( IsPhi ) { // for a phi node
+ // put args into the PhiArgMap
+ PhiArgMap[ *OpI ] = ((PHINode *) Inst )->getIncomingBlock( OpNum++ );
+ assert( PhiArgMap[ *OpI ] );
+ //cout << " Phi operand "; printValue( *OpI );
+ //cout << " came from BB "; printValue(PhiArgMap[*OpI]); cout<<endl;
+ }
+
+ InSetChanged = true;
+ //cout << " adding operand to use "; printValue( *OpI ); cout << endl;
+ }
+
+ }
+}
+
+
+
+
+bool BBLiveVar::applyTransferFunc() // calculates the InSet in terms of OutSet
+{
+
+ // IMPORTANT: caller should check whether the OutSet changed
+ // (else no point in calling)
+
+ LiveVarSet OutMinusDef; // set to hold (Out[B] - Def[B])
+ OutMinusDef.setDifference( &OutSet, &DefSet);
+ InSetChanged = InSet.setUnion( &OutMinusDef );
+
+ OutSetChanged = false; // no change to OutSet since transfer func applied
+
+ return InSetChanged;
+}
+
+
+
+ // calculates Out set using In sets of the predecessors
+bool BBLiveVar::setPropagate( LiveVarSet *const OutSet,
+ const LiveVarSet *const InSet,
+ const BasicBlock *const PredBB) {
+
+ LiveVarSet::const_iterator InIt;
+ pair<LiveVarSet::iterator, bool> result;
+ bool changed = false;
+ const BasicBlock *PredBBOfPhiArg;
+
+ // for all all elements in InSet
+ for( InIt = InSet->begin() ; InIt != InSet->end(); InIt++) {
+ PredBBOfPhiArg = PhiArgMap[ *InIt ];
+
+ // if this var is not a phi arg or it came from this BB
+ if( !PredBBOfPhiArg || PredBBOfPhiArg == PredBB) {
+ result = OutSet->insert( *InIt ); // insert to this set
+ if( result.second == true) changed = true;
+ }
+ }
+
+ return changed;
+}
+
+
+
+ // propogates in set to OutSets of PREDECESSORs
+bool BBLiveVar::applyFlowFunc(BBToBBLiveVarMapType LVMap)
+{
+
+ // IMPORTANT: caller should check whether inset changed
+ // (else no point in calling)
+
+ bool needAnotherIt= false; // did this BB change any OutSets of pred.s
+ // whose POId is lower
+
+
+ cfg::pred_const_iterator PredBBI = cfg::pred_begin(BaseBB);
+
+ for( ; PredBBI != cfg::pred_end(BaseBB) ; PredBBI++) {
+ assert( *PredBBI ); // assert that the predecessor is valid
+ BBLiveVar *PredLVBB = LVMap[*PredBBI];
+
+ // do set union
+ if( setPropagate( &(PredLVBB->OutSet), &InSet, *PredBBI ) == true) {
+ PredLVBB->OutSetChanged = true;
+
+ if( PredLVBB->getPOId() <= POId) // if the predec POId is lower than mine
+ needAnotherIt = true;
+ }
+ } // for
+
+ return needAnotherIt;
+
+}
+
+
+
+
+
+/* ----------------- Methods For Debugging (Printing) ----------------- */
+
+void BBLiveVar::printAllSets() const
+{
+ cout << "Defs: "; DefSet.printSet(); cout << endl;
+ cout << "In: "; InSet.printSet(); cout << endl;
+ cout << "Out: "; OutSet.printSet(); cout << endl;
+}
+
+void BBLiveVar::printInOutSets() const
+{
+ cout << "In: "; InSet.printSet(); cout << endl;
+ cout << "Out: "; OutSet.printSet(); cout << endl;
+}
diff --git a/lib/Analysis/LiveVar/BBLiveVar.h b/lib/Analysis/LiveVar/BBLiveVar.h
new file mode 100644
index 0000000..7917cc2
--- /dev/null
+++ b/lib/Analysis/LiveVar/BBLiveVar.h
@@ -0,0 +1,69 @@
+/* Title: ValueSet.h
+ Author: Ruchira Sasanka
+ Date: Jun 30, 01
+ Purpose: This is a wrapper class for BasicBlock which is used by live
+ variable anaysis
+*/
+
+#ifndef LIVE_VAR_BB_H
+#define LIVE_VAR_BB_H
+
+#include "LiveVarSet.h"
+#include "LiveVarMap.h"
+
+#include "llvm/BasicBlock.h"
+#include "llvm/Instruction.h"
+#include "llvm/CFG.h"
+#include "llvm/Type.h"
+#include "llvm/iOther.h"
+
+
+class BBLiveVar
+{
+ const BasicBlock* BaseBB; // pointer to BasicBlock
+ unsigned int POId; // Post-Order ID
+
+ LiveVarSet DefSet; // Def set for LV analysis
+ LiveVarSet InSet, OutSet; // In & Out for LV analysis
+ bool InSetChanged, OutSetChanged; // set if the InSet/OutSet is modified
+
+ // map that contains phi args->BB they came
+ hash_map<const Value *, const BasicBlock *, hashFuncValue> PhiArgMap;
+
+ // method to propogate an InSet to OutSet of a predecessor
+ bool setPropagate( LiveVarSet *const OutSetOfPred,
+ const LiveVarSet *const InSetOfThisBB,
+ const BasicBlock *const PredBB);
+
+ public:
+
+ BBLiveVar( const BasicBlock* baseBB, unsigned int POId);
+
+ inline bool isInSetChanged() const { return InSetChanged; }
+ inline bool isOutSetChanged() const { return OutSetChanged; }
+
+ inline unsigned int getPOId() const { return POId; }
+
+ void calcDefUseSets() ; // calculates the Def & Use sets for this BB
+ bool applyTransferFunc(); // calcultes the In in terms of Out
+
+ // calculates Out set using In sets of the predecessors
+ bool applyFlowFunc(BBToBBLiveVarMapType LVMap);
+
+ inline const LiveVarSet* getOutSet() const { return &OutSet; }
+ inline const LiveVarSet* getInSet() const { return &InSet; }
+
+ void printAllSets() const; // for printing Def/In/Out sets
+ void printInOutSets() const; // for printing In/Out sets
+
+ //TODO write a destructor to deallocate Def/In.Out sets and PhiArgMap
+
+};
+
+
+
+
+
+
+#endif
+
diff --git a/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp b/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp
new file mode 100644
index 0000000..b4126b0
--- /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
+*/
+
+
+
+
+
+
+
+
+
+
+
diff --git a/lib/Analysis/LiveVar/LiveVarSet.cpp b/lib/Analysis/LiveVar/LiveVarSet.cpp
new file mode 100644
index 0000000..c893817
--- /dev/null
+++ b/lib/Analysis/LiveVar/LiveVarSet.cpp
@@ -0,0 +1,20 @@
+#include "llvm/Analysis/LiveVar/LiveVarSet.h"
+
+
+// This function applies an instruction to a live var set (accepts OutSet) and
+// makes necessary changes to it (produces InSet)
+
+void LiveVarSet::applyTranferFuncForInst(const Instruction *const Inst)
+{
+
+ if( Inst->isDefinition() ) { // add to Defs iff this instr is a definition
+ remove(Inst); // this definition kills any uses
+ }
+ Instruction::op_const_iterator OpI = Inst->op_begin(); // get operand iterat
+
+ for( ; OpI != Inst->op_end() ; OpI++) { // iterate over operands
+ if ( ((*OpI)->getType())->isLabelType()) continue; // don't process labels
+ add( *OpI ); // An operand is a use - so add to use set
+ }
+
+}
diff --git a/lib/Analysis/LiveVar/Makefile b/lib/Analysis/LiveVar/Makefile
new file mode 100644
index 0000000..81d4948
--- /dev/null
+++ b/lib/Analysis/LiveVar/Makefile
@@ -0,0 +1,7 @@
+
+LEVEL = ../../..
+
+LIBRARYNAME = livevar
+
+include $(LEVEL)/Makefile.common
+
diff --git a/lib/Analysis/LiveVar/ValueSet.cpp b/lib/Analysis/LiveVar/ValueSet.cpp
new file mode 100644
index 0000000..d86587c
--- /dev/null
+++ b/lib/Analysis/LiveVar/ValueSet.cpp
@@ -0,0 +1,63 @@
+
+#include "llvm/Analysis/LiveVar/ValueSet.h"
+
+
+void printValue( const Value *const v) // func to print a Value
+{
+ if( (*v).hasName() ) cout << v << "(" << ((*v).getName()) << ") ";
+ //if( (*v).hasName() ) cout << ((*v).getName()) << " ";
+ else cout << v << " ";
+}
+
+
+//---------------- Method implementations --------------------------
+
+
+ValueSet:: ValueSet() : hash_set<const Value *, hashFuncValue> () { }
+
+ // for performing two set unions
+bool ValueSet::setUnion( const ValueSet *const set1) {
+ const_iterator set1it;
+ pair<iterator, bool> result;
+ bool changed = false;
+
+ for( set1it = set1->begin() ; set1it != set1->end(); set1it++) {
+ // for all all elements in set1
+ result = insert( *set1it ); // insert to this set
+ if( result.second == true) changed = true;
+ }
+
+ return changed;
+}
+
+
+ // for performing set difference
+void ValueSet::setDifference( const ValueSet *const set1,
+ const ValueSet *const set2) {
+
+ const_iterator set1it, set2it;
+ for( set1it = set1->begin() ; set1it != set1->end(); set1it++) {
+ // for all elements in set1
+ iterator set2it = set2->find( *set1it ); // find wether the elem is in set2
+ if( set2it == set2->end() ) // if the element is not in set2
+ insert( *set1it ); // insert to this set
+ }
+}
+
+
+ // for performing set subtraction
+void ValueSet::setSubtract( const ValueSet *const set1) {
+ const_iterator set1it;
+ for( set1it = set1->begin() ; set1it != set1->end(); set1it++)
+ // for all elements in set1
+ erase( *set1it ); // erase that element from this set
+}
+
+
+
+
+void ValueSet::printSet() const { // for printing a live variable set
+ const_iterator it;
+ for( it = begin() ; it != end(); it++)
+ printValue( *it );
+}
diff --git a/lib/Target/SparcV9/LiveVar/BBLiveVar.cpp b/lib/Target/SparcV9/LiveVar/BBLiveVar.cpp
new file mode 100644
index 0000000..aeb7f91
--- /dev/null
+++ b/lib/Target/SparcV9/LiveVar/BBLiveVar.cpp
@@ -0,0 +1,158 @@
+#include "llvm/Analysis/LiveVar/BBLiveVar.h"
+
+
+/********************* Implementation **************************************/
+
+BBLiveVar::BBLiveVar( const BasicBlock* baseBB, unsigned int RdfoId)
+ : DefSet(), InSet(), OutSet(), PhiArgMap() {
+ BaseBB = baseBB;
+ InSetChanged = OutSetChanged = false;
+ POId = RdfoId;
+}
+
+
+
+void BBLiveVar::calcDefUseSets() // caluculates def and use sets for each BB
+{
+ // instructions in basic block
+ const BasicBlock::InstListType& InstListInBB = BaseBB->getInstList();
+
+ BasicBlock::InstListType::const_reverse_iterator
+ InstIterator = InstListInBB.rbegin(); // get the iterator for instructions
+
+ // iterate over all the instructions in BB
+ for( ; InstIterator != InstListInBB.rend(); InstIterator++) {
+
+ const Instruction * Inst = *InstIterator; // Inst is the current instr
+ assert(Inst);
+
+ if( Inst->isDefinition() ) { // add to Defs only if this instr is a def
+
+ DefSet.add( Inst ); // nstruction is a def - so add to def set
+ InSet.remove( Inst); // this definition kills any uses
+ InSetChanged = true;
+ //cout << " adding inst to def "; printValue( Inst ); cout << endl;
+ }
+
+ Instruction::op_const_iterator
+ OpI = Inst->op_begin(); // get iterator for operands
+
+ bool IsPhi=( Inst->getOpcode() == Instruction::PHINode ); // Is this a phi
+
+ for(int OpNum=0 ; OpI != Inst->op_end() ; OpI++) { // iterate over operands
+
+ if ( ((*OpI)->getType())->isLabelType() )
+ continue; // don't process labels
+
+ InSet.add( *OpI ); // An operand is a use - so add to use set
+ OutSet.remove( *OpI ); // remove if there is a definition below this use
+
+ if( IsPhi ) { // for a phi node
+ // put args into the PhiArgMap
+ PhiArgMap[ *OpI ] = ((PHINode *) Inst )->getIncomingBlock( OpNum++ );
+ assert( PhiArgMap[ *OpI ] );
+ //cout << " Phi operand "; printValue( *OpI );
+ //cout << " came from BB "; printValue(PhiArgMap[*OpI]); cout<<endl;
+ }
+
+ InSetChanged = true;
+ //cout << " adding operand to use "; printValue( *OpI ); cout << endl;
+ }
+
+ }
+}
+
+
+
+
+bool BBLiveVar::applyTransferFunc() // calculates the InSet in terms of OutSet
+{
+
+ // IMPORTANT: caller should check whether the OutSet changed
+ // (else no point in calling)
+
+ LiveVarSet OutMinusDef; // set to hold (Out[B] - Def[B])
+ OutMinusDef.setDifference( &OutSet, &DefSet);
+ InSetChanged = InSet.setUnion( &OutMinusDef );
+
+ OutSetChanged = false; // no change to OutSet since transfer func applied
+
+ return InSetChanged;
+}
+
+
+
+ // calculates Out set using In sets of the predecessors
+bool BBLiveVar::setPropagate( LiveVarSet *const OutSet,
+ const LiveVarSet *const InSet,
+ const BasicBlock *const PredBB) {
+
+ LiveVarSet::const_iterator InIt;
+ pair<LiveVarSet::iterator, bool> result;
+ bool changed = false;
+ const BasicBlock *PredBBOfPhiArg;
+
+ // for all all elements in InSet
+ for( InIt = InSet->begin() ; InIt != InSet->end(); InIt++) {
+ PredBBOfPhiArg = PhiArgMap[ *InIt ];
+
+ // if this var is not a phi arg or it came from this BB
+ if( !PredBBOfPhiArg || PredBBOfPhiArg == PredBB) {
+ result = OutSet->insert( *InIt ); // insert to this set
+ if( result.second == true) changed = true;
+ }
+ }
+
+ return changed;
+}
+
+
+
+ // propogates in set to OutSets of PREDECESSORs
+bool BBLiveVar::applyFlowFunc(BBToBBLiveVarMapType LVMap)
+{
+
+ // IMPORTANT: caller should check whether inset changed
+ // (else no point in calling)
+
+ bool needAnotherIt= false; // did this BB change any OutSets of pred.s
+ // whose POId is lower
+
+
+ cfg::pred_const_iterator PredBBI = cfg::pred_begin(BaseBB);
+
+ for( ; PredBBI != cfg::pred_end(BaseBB) ; PredBBI++) {
+ assert( *PredBBI ); // assert that the predecessor is valid
+ BBLiveVar *PredLVBB = LVMap[*PredBBI];
+
+ // do set union
+ if( setPropagate( &(PredLVBB->OutSet), &InSet, *PredBBI ) == true) {
+ PredLVBB->OutSetChanged = true;
+
+ if( PredLVBB->getPOId() <= POId) // if the predec POId is lower than mine
+ needAnotherIt = true;
+ }
+ } // for
+
+ return needAnotherIt;
+
+}
+
+
+
+
+
+/* ----------------- Methods For Debugging (Printing) ----------------- */
+
+void BBLiveVar::printAllSets() const
+{
+ cout << "Defs: "; DefSet.printSet(); cout << endl;
+ cout << "In: "; InSet.printSet(); cout << endl;
+ cout << "Out: "; OutSet.printSet(); cout << endl;
+}
+
+void BBLiveVar::printInOutSets() const
+{
+ cout << "In: "; InSet.printSet(); cout << endl;
+ cout << "Out: "; OutSet.printSet(); cout << endl;
+}
diff --git a/lib/Target/SparcV9/LiveVar/BBLiveVar.h b/lib/Target/SparcV9/LiveVar/BBLiveVar.h
new file mode 100644
index 0000000..7917cc2
--- /dev/null
+++ b/lib/Target/SparcV9/LiveVar/BBLiveVar.h
@@ -0,0 +1,69 @@
+/* Title: ValueSet.h
+ Author: Ruchira Sasanka
+ Date: Jun 30, 01
+ Purpose: This is a wrapper class for BasicBlock which is used by live
+ variable anaysis
+*/
+
+#ifndef LIVE_VAR_BB_H
+#define LIVE_VAR_BB_H
+
+#include "LiveVarSet.h"
+#include "LiveVarMap.h"
+
+#include "llvm/BasicBlock.h"
+#include "llvm/Instruction.h"
+#include "llvm/CFG.h"
+#include "llvm/Type.h"
+#include "llvm/iOther.h"
+
+
+class BBLiveVar
+{
+ const BasicBlock* BaseBB; // pointer to BasicBlock
+ unsigned int POId; // Post-Order ID
+
+ LiveVarSet DefSet; // Def set for LV analysis
+ LiveVarSet InSet, OutSet; // In & Out for LV analysis
+ bool InSetChanged, OutSetChanged; // set if the InSet/OutSet is modified
+
+ // map that contains phi args->BB they came
+ hash_map<const Value *, const BasicBlock *, hashFuncValue> PhiArgMap;
+
+ // method to propogate an InSet to OutSet of a predecessor
+ bool setPropagate( LiveVarSet *const OutSetOfPred,
+ const LiveVarSet *const InSetOfThisBB,
+ const BasicBlock *const PredBB);
+
+ public:
+
+ BBLiveVar( const BasicBlock* baseBB, unsigned int POId);
+
+ inline bool isInSetChanged() const { return InSetChanged; }
+ inline bool isOutSetChanged() const { return OutSetChanged; }
+
+ inline unsigned int getPOId() const { return POId; }
+
+ void calcDefUseSets() ; // calculates the Def & Use sets for this BB
+ bool applyTransferFunc(); // calcultes the In in terms of Out
+
+ // calculates Out set using In sets of the predecessors
+ bool applyFlowFunc(BBToBBLiveVarMapType LVMap);
+
+ inline const LiveVarSet* getOutSet() const { return &OutSet; }
+ inline const LiveVarSet* getInSet() const { return &InSet; }
+
+ void printAllSets() const; // for printing Def/In/Out sets
+ void printInOutSets() const; // for printing In/Out sets
+
+ //TODO write a destructor to deallocate Def/In.Out sets and PhiArgMap
+
+};
+
+
+
+
+
+
+#endif
+
diff --git a/lib/Target/SparcV9/LiveVar/FunctionLiveVarInfo.cpp b/lib/Target/SparcV9/LiveVar/FunctionLiveVarInfo.cpp
new file mode 100644
index 0000000..b4126b0
--- /dev/null
+++ b/lib/Target/SparcV9/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
+*/
+
+
+
+
+
+
+
+
+
+
+
diff --git a/lib/Target/SparcV9/LiveVar/LiveVarSet.cpp b/lib/Target/SparcV9/LiveVar/LiveVarSet.cpp
new file mode 100644
index 0000000..c893817
--- /dev/null
+++ b/lib/Target/SparcV9/LiveVar/LiveVarSet.cpp
@@ -0,0 +1,20 @@
+#include "llvm/Analysis/LiveVar/LiveVarSet.h"
+
+
+// This function applies an instruction to a live var set (accepts OutSet) and
+// makes necessary changes to it (produces InSet)
+
+void LiveVarSet::applyTranferFuncForInst(const Instruction *const Inst)
+{
+
+ if( Inst->isDefinition() ) { // add to Defs iff this instr is a definition
+ remove(Inst); // this definition kills any uses
+ }
+ Instruction::op_const_iterator OpI = Inst->op_begin(); // get operand iterat
+
+ for( ; OpI != Inst->op_end() ; OpI++) { // iterate over operands
+ if ( ((*OpI)->getType())->isLabelType()) continue; // don't process labels
+ add( *OpI ); // An operand is a use - so add to use set
+ }
+
+}
diff --git a/lib/Target/SparcV9/LiveVar/Makefile b/lib/Target/SparcV9/LiveVar/Makefile
new file mode 100644
index 0000000..81d4948
--- /dev/null
+++ b/lib/Target/SparcV9/LiveVar/Makefile
@@ -0,0 +1,7 @@
+
+LEVEL = ../../..
+
+LIBRARYNAME = livevar
+
+include $(LEVEL)/Makefile.common
+
diff --git a/lib/Target/SparcV9/LiveVar/ValueSet.cpp b/lib/Target/SparcV9/LiveVar/ValueSet.cpp
new file mode 100644
index 0000000..d86587c
--- /dev/null
+++ b/lib/Target/SparcV9/LiveVar/ValueSet.cpp
@@ -0,0 +1,63 @@
+
+#include "llvm/Analysis/LiveVar/ValueSet.h"
+
+
+void printValue( const Value *const v) // func to print a Value
+{
+ if( (*v).hasName() ) cout << v << "(" << ((*v).getName()) << ") ";
+ //if( (*v).hasName() ) cout << ((*v).getName()) << " ";
+ else cout << v << " ";
+}
+
+
+//---------------- Method implementations --------------------------
+
+
+ValueSet:: ValueSet() : hash_set<const Value *, hashFuncValue> () { }
+
+ // for performing two set unions
+bool ValueSet::setUnion( const ValueSet *const set1) {
+ const_iterator set1it;
+ pair<iterator, bool> result;
+ bool changed = false;
+
+ for( set1it = set1->begin() ; set1it != set1->end(); set1it++) {
+ // for all all elements in set1
+ result = insert( *set1it ); // insert to this set
+ if( result.second == true) changed = true;
+ }
+
+ return changed;
+}
+
+
+ // for performing set difference
+void ValueSet::setDifference( const ValueSet *const set1,
+ const ValueSet *const set2) {
+
+ const_iterator set1it, set2it;
+ for( set1it = set1->begin() ; set1it != set1->end(); set1it++) {
+ // for all elements in set1
+ iterator set2it = set2->find( *set1it ); // find wether the elem is in set2
+ if( set2it == set2->end() ) // if the element is not in set2
+ insert( *set1it ); // insert to this set
+ }
+}
+
+
+ // for performing set subtraction
+void ValueSet::setSubtract( const ValueSet *const set1) {
+ const_iterator set1it;
+ for( set1it = set1->begin() ; set1it != set1->end(); set1it++)
+ // for all elements in set1
+ erase( *set1it ); // erase that element from this set
+}
+
+
+
+
+void ValueSet::printSet() const { // for printing a live variable set
+ const_iterator it;
+ for( it = begin() ; it != end(); it++)
+ printValue( *it );
+}