diff options
Diffstat (limited to 'llvm/lib/Analysis')
| -rw-r--r-- | llvm/lib/Analysis/LiveVar/BBLiveVar.cpp | 155 | ||||
| -rw-r--r-- | llvm/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp | 174 | ||||
| -rw-r--r-- | llvm/lib/Analysis/LiveVar/LiveVarSet.cpp | 38 | ||||
| -rw-r--r-- | llvm/lib/Analysis/LiveVar/ValueSet.cpp | 22 |
4 files changed, 253 insertions, 136 deletions
diff --git a/llvm/lib/Analysis/LiveVar/BBLiveVar.cpp b/llvm/lib/Analysis/LiveVar/BBLiveVar.cpp index aeb7f9184c5..6d925c4a7e0 100644 --- a/llvm/lib/Analysis/LiveVar/BBLiveVar.cpp +++ b/llvm/lib/Analysis/LiveVar/BBLiveVar.cpp @@ -1,69 +1,110 @@ #include "llvm/Analysis/LiveVar/BBLiveVar.h" +#include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/Sparc.h" /********************* Implementation **************************************/ -BBLiveVar::BBLiveVar( const BasicBlock* baseBB, unsigned int RdfoId) - : DefSet(), InSet(), OutSet(), PhiArgMap() { +BBLiveVar::BBLiveVar( const BasicBlock *const baseBB, unsigned int RdfoId) + : BaseBB(baseBB), DefSet(), InSet(), + OutSet(), PhiArgMap() { BaseBB = baseBB; InSetChanged = OutSetChanged = false; POId = RdfoId; } +// caluculates def and use sets for each BB +// There are two passes over operands of a machine instruction. This is +// because, we can have instructions like V = V + 1, since we no longer +// assume single definition. - -void BBLiveVar::calcDefUseSets() // caluculates def and use sets for each BB +void BBLiveVar::calcDefUseSets() { - // instructions in basic block - const BasicBlock::InstListType& InstListInBB = BaseBB->getInstList(); + // get the iterator for machine instructions + const MachineCodeForBasicBlock& MIVec = BaseBB->getMachineInstrVec(); + MachineCodeForBasicBlock::const_reverse_iterator + MInstIterator = MIVec.rbegin(); + + // iterate over all the machine instructions in BB + for( ; MInstIterator != MIVec.rend(); ++MInstIterator) { - BasicBlock::InstListType::const_reverse_iterator - InstIterator = InstListInBB.rbegin(); // get the iterator for instructions + const MachineInstr * MInst = *MInstIterator; // MInst is the machine inst + assert(MInst); + + if( DEBUG_LV > 1) { // debug msg + cout << " *Iterating over machine instr "; + MInst->dump(); + cout << endl; + } - // iterate over all the instructions in BB - for( ; InstIterator != InstListInBB.rend(); InstIterator++) { + // iterate over MI operands to find defs + for( MachineInstr::val_op_const_iterator OpI(MInst); !OpI.done() ; ++OpI) { - const Instruction * Inst = *InstIterator; // Inst is the current instr - assert(Inst); + const Value *Op = *OpI; - if( Inst->isDefinition() ) { // add to Defs only if this instr is a def + if( OpI.isDef() ) { // add to Defs only if this operand 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; + DefSet.add( Op ); // operand is a def - so add to def set + InSet.remove( Op); // this definition kills any uses + InSetChanged = true; + + if( DEBUG_LV > 1) { + cout << " +Def: "; printValue( Op ); cout << endl; + } + } } - Instruction::op_const_iterator - OpI = Inst->op_begin(); // get iterator for operands + bool IsPhi = ( MInst->getOpCode() == PHI ); + + + // iterate over MI operands to find uses + for(MachineInstr::val_op_const_iterator OpI(MInst); !OpI.done() ; ++OpI) { + const Value *Op = *OpI; + + if ( ((Op)->getType())->isLabelType() ) + continue; // don't process labels + + if(! OpI.isDef() ) { // add to Defs only if this operand is a use + + InSet.add( Op ); // An operand is a use - so add to use set + OutSet.remove( Op ); // remove if there is a def below this use + InSetChanged = true; + + if( DEBUG_LV > 1) { // debug msg of level 2 + cout << " Use: "; printValue( Op ); cout << endl; + } + + if( IsPhi ) { // for a phi node + // put args into the PhiArgMap (Val -> BB) - bool IsPhi=( Inst->getOpcode() == Instruction::PHINode ); // Is this a phi + const Value * ArgVal = Op; + ++OpI; // increment to point to BB of value + const Value * BBVal = *OpI; - for(int OpNum=0 ; OpI != Inst->op_end() ; OpI++) { // iterate over operands - if ( ((*OpI)->getType())->isLabelType() ) - continue; // don't process labels + assert( (BBVal)->getValueType() == Value::BasicBlockVal ); + + PhiArgMap[ ArgVal ] = (const BasicBlock *) (BBVal); + assert( PhiArgMap[ ArgVal ] ); - 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( DEBUG_LV > 1) { // debug msg of level 2 + cout << " - phi operand "; + printValue( ArgVal ); + cout << " came from BB "; + printValue( PhiArgMap[ ArgVal ]); + cout<<endl; + } + + } - 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; - } - - } + } // for all machine instructions } - bool BBLiveVar::applyTransferFunc() // calculates the InSet in terms of OutSet { @@ -71,18 +112,18 @@ 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]) + 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 + OutSetChanged = false; // no change to OutSet since transf func applied return InSetChanged; } - // calculates Out set using In sets of the predecessors +// calculates Out set using In sets of the predecessors bool BBLiveVar::setPropagate( LiveVarSet *const OutSet, const LiveVarSet *const InSet, const BasicBlock *const PredBB) { @@ -92,11 +133,12 @@ bool BBLiveVar::setPropagate( LiveVarSet *const OutSet, bool changed = false; const BasicBlock *PredBBOfPhiArg; - // for all all elements in InSet + // 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 this var is not a phi arg OR + // it's a phi arg and the var went down from this BB if( !PredBBOfPhiArg || PredBBOfPhiArg == PredBB) { result = OutSet->insert( *InIt ); // insert to this set if( result.second == true) changed = true; @@ -108,7 +150,8 @@ bool BBLiveVar::setPropagate( LiveVarSet *const OutSet, - // propogates in set to OutSets of PREDECESSORs +// propogates in set to OutSets of PREDECESSORs + bool BBLiveVar::applyFlowFunc(BBToBBLiveVarMapType LVMap) { @@ -122,17 +165,19 @@ bool BBLiveVar::applyFlowFunc(BBToBBLiveVarMapType LVMap) cfg::pred_const_iterator PredBBI = cfg::pred_begin(BaseBB); for( ; PredBBI != cfg::pred_end(BaseBB) ; PredBBI++) { - assert( *PredBBI ); // assert that the predecessor is valid + assert( *PredBBI ); // assert that the predecessor is valid BBLiveVar *PredLVBB = LVMap[*PredBBI]; - // do set union + // 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 + // if the predec POId is lower than mine + if( PredLVBB->getPOId() <= POId) needAnotherIt = true; } - } // for + + } // for return needAnotherIt; @@ -140,19 +185,21 @@ bool BBLiveVar::applyFlowFunc(BBToBBLiveVarMapType LVMap) - - /* ----------------- 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; + 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; + cout << " In: "; InSet.printSet(); cout << endl; + cout << " Out: "; OutSet.printSet(); cout << endl; } + + + + diff --git a/llvm/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp b/llvm/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp index b4126b00293..91c2498e975 100644 --- a/llvm/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp +++ b/llvm/lib/Analysis/LiveVar/FunctionLiveVarInfo.cpp @@ -1,35 +1,38 @@ -/* Title: ValueSet.h +/* Title: MethodLiveVarInfo.cpp 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. + 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" - +#include "llvm/CodeGen/MachineInstr.h" /************************** Constructor/Destructor ***************************/ -MethodLiveVarInfo::MethodLiveVarInfo(Method *const MethPtr) : BB2BBLVMap() -{ - Meth = MethPtr; // init BB2BBLVMap and records Method for future use +MethodLiveVarInfo::MethodLiveVarInfo(const Method *const M) : Meth(M), + BB2BBLVMap() +{ + assert(! M->isExternal() ); // cannot be a prototype decleration + HasAnalyzed = false; // still we haven't called analyze() } MethodLiveVarInfo:: ~MethodLiveVarInfo() { - BBToBBLiveVarMapType::iterator HMI = BB2BBLVMap.begin(); // hash map iterator + // hash map iterator + BBToBBLiveVarMapType::iterator HMI = BB2BBLVMap.begin(); for( ; HMI != BB2BBLVMap.end() ; HMI ++ ) { - if( (*HMI).first ) // delete all LiveVarSets in BB2BBLVMap + if( (*HMI).first ) // delete all LiveVarSets in BB2BBLVMap delete (*HMI).second; } } @@ -39,38 +42,40 @@ MethodLiveVarInfo:: ~MethodLiveVarInfo() - // constructs BBLiveVars and init Def and In sets +// constructs BBLiveVars and init Def and In sets void MethodLiveVarInfo::constructBBs() { - unsigned int POId = 0; // Reverse Depth-first Order ID + 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 ; + 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 + const BasicBlock *BB = *BBI; // get the current BB + // create a new BBLiveVar + BBLiveVar * LVBB = new BBLiveVar( BB, POId ); - BB2BBLVMap[ BB ] = LVBB; // insert the pair to Map + BB2BBLVMap[ BB ] = LVBB; // insert the pair to Map - LVBB->calcDefUseSets(); // calculates the def and in set + LVBB->calcDefUseSets(); // calculates the def and in set - if(DEBUG_LV) LVBB->printAllSets(); - //cout << "InSetChanged: " << LVBB->isInSetChanged() << endl; + if(DEBUG_LV) + LVBB->printAllSets(); } - - } - // do one backward pass over the CFG + + +// do one backward pass over the CFG bool MethodLiveVarInfo::doSingleBackwardPass() { bool ResultFlow, NeedAnotherIteration = false; - if(DEBUG_LV) cout << endl << "------- After Backward Pass --------" << endl; + if(DEBUG_LV) + cout << endl << " After Backward Pass ..." << endl; cfg::po_const_iterator BBI = cfg::po_begin(Meth); @@ -80,102 +85,131 @@ bool MethodLiveVarInfo::doSingleBackwardPass() BBLiveVar* LVBB = BB2BBLVMap[*BBI]; assert( LVBB ); - if(DEBUG_LV) cout << "-- For BB " << (*BBI)->getName() << ":" << endl; + 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 + LVBB->applyTransferFunc(); // apply the Tran Func to calc InSet + + if( LVBB->isInSetChanged() ) // to calc Outsets of preds + ResultFlow = LVBB->applyFlowFunc(BB2BBLVMap); 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 + // true if we need to reiterate over the CFG + return NeedAnotherIteration; } -void MethodLiveVarInfo::analyze() // performs live var anal for a method +// performs live var anal for a method +void MethodLiveVarInfo::analyze() { - //cout << "In analyze . . ." << cout; - constructBBs(); // create and initialize all the BBLiveVars of the CFG + if( DEBUG_LV) cout << "Analysing live variables ..." << endl; + + // create and initialize all the BBLiveVars of the CFG + constructBBs(); bool NeedAnotherIteration = false; - do { - NeedAnotherIteration = doSingleBackwardPass( ); // do one pass over CFG - } while (NeedAnotherIteration ); // repeat until we need more iterations + do { // do one pass over CFG + NeedAnotherIteration = doSingleBackwardPass( ); + } while (NeedAnotherIteration ); // repeat until we need more iterations + + + HasAnalyzed = true; // finished analysing + + if( DEBUG_LV) cout << "Live Variable Analysis complete!" << endl; } -/* This function will give the LiveVar info for any instruction in a method. It - should be called after a call to analyze(). +/* Thsese functions will give the LiveVar info for any machine 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 + Thsese functions calucluates live var info for all the machine instrs 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) +MethodLiveVarInfo::getLiveVarSetBeforeMInst(const MachineInstr *const MInst, + const BasicBlock *const CurBB) { - // get the BB corresponding to the instruction - const BasicBlock *const CurBB = Inst->getParent(); + const LiveVarSet *LVSet = MInst2LVSetBI[MInst]; - const LiveVarSet *LVSet = Inst2LVSetMap[Inst]; - - if( LVSet ) return LVSet; // if found, just return the set + if( LVSet ) return LVSet; // if found, just return the set + else { + calcLiveVarSetsForBB( CurBB ); // else, calc for all instrs in BB + assert( MInst2LVSetBI[ MInst ] ); + return MInst2LVSetBI[ MInst ]; + } +} - 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 ); +const LiveVarSet * +MethodLiveVarInfo::getLiveVarSetAfterMInst(const MachineInstr *const MInst, + const BasicBlock *const CurBB) +{ + const LiveVarSet *LVSet = MInst2LVSetAI[MInst]; - // if the first instruction is requested, just return the InSet - if( Inst == *InstItEnd) return Inst2LVSetMap[Inst]; + if( LVSet ) return LVSet; // if found, just return the set + else { + calcLiveVarSetsForBB( CurBB ); // else, calc for all instrs in BB + assert( MInst2LVSetAI[ MInst ] ); + return MInst2LVSetAI[ MInst ]; + } +} - // else calculate for all other instruction in the BB - BasicBlock::InstListType::const_reverse_iterator - InstIt= InstListInBB.rbegin(); // get the iterator for instructions in BB +void MethodLiveVarInfo::calcLiveVarSetsForBB(const BasicBlock *const BB) +{ + const MachineCodeForBasicBlock& MIVec = BB->getMachineInstrVec(); + MachineCodeForBasicBlock::const_reverse_iterator + MInstIterator = MIVec.rbegin(); LiveVarSet *CurSet = new LiveVarSet(); - CurSet->setUnion( getOutSetOfBB( CurBB )); // LVSet now contains the OutSet + const LiveVarSet *SetAI = getOutSetOfBB(BB); // init SetAI with OutSet + CurSet->setUnion(SetAI); // CurSet now contains OutSet - // calculate LVSet for all instructions in the basic block (except the first) - for( ; InstIt != InstItEnd ; InstIt++) { + // iterate over all the machine instructions in BB + for( ; MInstIterator != MIVec.rend(); MInstIterator++) { - 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 - } + // MInst is cur machine inst + const MachineInstr * MInst = *MInstIterator; + + MInst2LVSetAI[MInst] = SetAI; // record in After Inst map + + CurSet->applyTranferFuncForMInst( MInst ); // apply the transfer Func + LiveVarSet *NewSet = new LiveVarSet(); // create a new set and + NewSet->setUnion( CurSet ); // copy the set after T/F to it + + MInst2LVSetBI[MInst] = NewSet; // record in Before Inst map - return Inst2LVSetMap[Inst]; + // SetAI will be used in the next iteration + SetAI = NewSet; + } + } -/* -NOTES: delete all the LVBBs allocated by adding a destructor to the BB2BBLVMap??? - use the dfo_iterator in the doSingleBackwardPass -*/ + + + diff --git a/llvm/lib/Analysis/LiveVar/LiveVarSet.cpp b/llvm/lib/Analysis/LiveVar/LiveVarSet.cpp index c8938175494..07dc1286014 100644 --- a/llvm/lib/Analysis/LiveVar/LiveVarSet.cpp +++ b/llvm/lib/Analysis/LiveVar/LiveVarSet.cpp @@ -1,9 +1,42 @@ #include "llvm/Analysis/LiveVar/LiveVarSet.h" +#include "llvm/CodeGen/MachineInstr.h" -// This function applies an instruction to a live var set (accepts OutSet) and -// makes necessary changes to it (produces InSet) +// This function applies a machine instr to a live var set (accepts OutSet) and +// makes necessary changes to it (produces InSet). Note that two for loops are +// used to first kill all defs and then to add all uses. This is because there +// can be instructions like Val = Val + 1 since we allow multipe defs to a +// machine instruction operand. + +void LiveVarSet::applyTranferFuncForMInst(const MachineInstr *const MInst) +{ + + for( MachineInstr::val_op_const_iterator OpI(MInst); !OpI.done() ; OpI++) { + + if( OpI.isDef() ) { // kill only if this operand is a def + remove(*OpI); // this definition kills any uses + } + + } + + for( MachineInstr::val_op_const_iterator OpI(MInst); !OpI.done() ; OpI++) { + + if ( ((*OpI)->getType())->isLabelType()) continue; // don't process labels + + if( ! OpI.isDef() ) { // add only if this operand is a use + add( *OpI ); // An operand is a use - so add to use set + } + } +} + + + + + + + +#if 0 void LiveVarSet::applyTranferFuncForInst(const Instruction *const Inst) { @@ -18,3 +51,4 @@ void LiveVarSet::applyTranferFuncForInst(const Instruction *const Inst) } } +#endif diff --git a/llvm/lib/Analysis/LiveVar/ValueSet.cpp b/llvm/lib/Analysis/LiveVar/ValueSet.cpp index 680ad83428e..8cfe6fb289e 100644 --- a/llvm/lib/Analysis/LiveVar/ValueSet.cpp +++ b/llvm/lib/Analysis/LiveVar/ValueSet.cpp @@ -5,11 +5,13 @@ 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 if (v->getValueType() == Value::ConstantVal) // if const + + if( (*v).hasName() ) + cout << v << "(" << ((*v).getName()) << ") "; + else if (v->getValueType() == Value::ConstantVal) // if const cout << v << "(" << ((ConstPoolVal *) v)->getStrValue() << ") "; - else cout << v << " "; + else + cout << v << " "; } @@ -18,15 +20,15 @@ void printValue( const Value *const v) // func to print a Value ValueSet:: ValueSet() : hash_set<const Value *, hashFuncValue> () { } - // for performing two set unions + // 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 + // for all all elements in set1 + result = insert( *set1it ); // insert to this set if( result.second == true) changed = true; } @@ -34,7 +36,7 @@ bool ValueSet::setUnion( const ValueSet *const set1) { } - // for performing set difference + // for performing set difference void ValueSet::setDifference( const ValueSet *const set1, const ValueSet *const set2) { @@ -48,7 +50,7 @@ void ValueSet::setDifference( const ValueSet *const set1, } - // for performing set subtraction + // for performing set subtraction void ValueSet::setSubtract( const ValueSet *const set1) { const_iterator set1it; for( set1it = set1->begin() ; set1it != set1->end(); set1it++) @@ -59,7 +61,7 @@ void ValueSet::setSubtract( const ValueSet *const set1) { -void ValueSet::printSet() const { // for printing a live variable set +void ValueSet::printSet() const { // for printing a live variable set const_iterator it; for( it = begin() ; it != end(); it++) printValue( *it ); |
