diff options
author | Ruchira Sasanka <sasanka@students.uiuc.edu> | 2001-07-24 17:14:13 +0000 |
---|---|---|
committer | Ruchira Sasanka <sasanka@students.uiuc.edu> | 2001-07-24 17:14:13 +0000 |
commit | 683847fb751890fb0ca16657be68f769bdff786c (patch) | |
tree | 7bdc59d4565c8d04335ddae7d2b5114292f51320 /lib/Analysis/LiveVar | |
parent | 2233a07b686ead865b0bfeed5a50d178d05f9549 (diff) | |
download | external_llvm-683847fb751890fb0ca16657be68f769bdff786c.zip external_llvm-683847fb751890fb0ca16657be68f769bdff786c.tar.gz external_llvm-683847fb751890fb0ca16657be68f769bdff786c.tar.bz2 |
*** empty log message ***
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@291 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Analysis/LiveVar')
-rw-r--r-- | lib/Analysis/LiveVar/BBLiveVar.cpp | 158 | ||||
-rw-r--r-- | lib/Analysis/LiveVar/BBLiveVar.h | 69 | ||||
-rw-r--r-- | lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp | 189 | ||||
-rw-r--r-- | lib/Analysis/LiveVar/LiveVarSet.cpp | 20 | ||||
-rw-r--r-- | lib/Analysis/LiveVar/Makefile | 7 | ||||
-rw-r--r-- | lib/Analysis/LiveVar/ValueSet.cpp | 63 |
6 files changed, 506 insertions, 0 deletions
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 ); +} |