1 #include "llvm/Analysis/LiveVar/BBLiveVar.h"
2 #include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
3 #include "llvm/CodeGen/MachineInstr.h"
4 #include "../../Target/Sparc/SparcInternals.h" // TODO: FIXME!! Only for PHI defn
7 /********************* Implementation **************************************/
9 BBLiveVar::BBLiveVar( const BasicBlock *const baseBB, unsigned int RdfoId)
10 : BaseBB(baseBB), DefSet(), InSet(),
11 OutSet(), PhiArgMap() {
13 InSetChanged = OutSetChanged = false;
17 // caluculates def and use sets for each BB
18 // There are two passes over operands of a machine instruction. This is
19 // because, we can have instructions like V = V + 1, since we no longer
20 // assume single definition.
22 void BBLiveVar::calcDefUseSets()
24 // get the iterator for machine instructions
25 const MachineCodeForBasicBlock& MIVec = BaseBB->getMachineInstrVec();
26 MachineCodeForBasicBlock::const_reverse_iterator
27 MInstIterator = MIVec.rbegin();
29 // iterate over all the machine instructions in BB
30 for( ; MInstIterator != MIVec.rend(); ++MInstIterator) {
32 const MachineInstr * MInst = *MInstIterator; // MInst is the machine inst
35 if( DEBUG_LV > 1) { // debug msg
36 cerr << " *Iterating over machine instr ";
41 // iterate over MI operands to find defs
42 for( MachineInstr::val_op_const_iterator OpI(MInst); !OpI.done() ; ++OpI) {
44 if( OpI.isDef() ) // add to Defs only if this operand is a def
48 // do for implicit operands as well
49 for( unsigned i=0; i < MInst->getNumImplicitRefs(); ++i) {
50 if( MInst->implicitRefIsDefined(i) )
51 addDef( MInst->getImplicitRef(i) );
55 bool IsPhi = ( MInst->getOpCode() == PHI );
58 // iterate over MI operands to find uses
59 for(MachineInstr::val_op_const_iterator OpI(MInst); !OpI.done() ; ++OpI) {
60 const Value *Op = *OpI;
62 if ( ((Op)->getType())->isLabelType() )
63 continue; // don't process labels
65 if(! OpI.isDef() ) { // add to Defs only if this operand is a use
68 if( IsPhi ) { // for a phi node
69 // put args into the PhiArgMap (Val -> BB)
71 const Value * ArgVal = Op;
72 ++OpI; // increment to point to BB of value
73 const Value * BBVal = *OpI;
76 assert( (BBVal)->getValueType() == Value::BasicBlockVal );
78 PhiArgMap[ ArgVal ] = (const BasicBlock *) (BBVal);
79 assert( PhiArgMap[ ArgVal ] );
81 if( DEBUG_LV > 1) { // debug msg of level 2
82 cerr << " - phi operand ";
84 cerr << " came from BB ";
85 printValue( PhiArgMap[ ArgVal ]);
95 // do for implicit operands as well
96 for( unsigned i=0; i < MInst->getNumImplicitRefs(); ++i) {
98 assert( !IsPhi && "Phi cannot have implicit opeands");
99 const Value *Op = MInst->getImplicitRef(i);
101 if ( ((Op)->getType())->isLabelType() )
102 continue; // don't process labels
103 if( ! MInst->implicitRefIsDefined(i) )
107 } // for all machine instructions
111 // To add an operand wichi is a def
113 void BBLiveVar::addDef(const Value *Op)
115 DefSet.add( Op ); // operand is a def - so add to def set
116 InSet.remove( Op); // this definition kills any uses
120 cerr << " +Def: "; printValue( Op ); cerr << endl;
124 // To add an operand which is a use
126 void BBLiveVar::addUse(const Value *Op)
128 InSet.add( Op ); // An operand is a use - so add to use set
129 OutSet.remove( Op ); // remove if there is a def below this use
132 if( DEBUG_LV > 1) { // debug msg of level 2
133 cerr << " Use: "; printValue( Op ); cerr << endl;
140 bool BBLiveVar::applyTransferFunc() // calculates the InSet in terms of OutSet
143 // IMPORTANT: caller should check whether the OutSet changed
144 // (else no point in calling)
146 LiveVarSet OutMinusDef; // set to hold (Out[B] - Def[B])
147 OutMinusDef.setDifference( &OutSet, &DefSet);
148 InSetChanged = InSet.setUnion( &OutMinusDef );
150 OutSetChanged = false; // no change to OutSet since transf func applied
157 // calculates Out set using In sets of the predecessors
158 bool BBLiveVar::setPropagate( LiveVarSet *const OutSet,
159 const LiveVarSet *const InSet,
160 const BasicBlock *const PredBB) {
162 LiveVarSet::const_iterator InIt;
163 pair<LiveVarSet::iterator, bool> result;
164 bool changed = false;
165 const BasicBlock *PredBBOfPhiArg;
167 // for all all elements in InSet
168 for( InIt = InSet->begin() ; InIt != InSet->end(); InIt++) {
169 PredBBOfPhiArg = PhiArgMap[ *InIt ];
171 // if this var is not a phi arg OR
172 // it's a phi arg and the var went down from this BB
173 if( !PredBBOfPhiArg || PredBBOfPhiArg == PredBB) {
174 result = OutSet->insert( *InIt ); // insert to this set
175 if( result.second == true) changed = true;
184 // propogates in set to OutSets of PREDECESSORs
186 bool BBLiveVar::applyFlowFunc(BBToBBLiveVarMapType LVMap)
189 // IMPORTANT: caller should check whether inset changed
190 // (else no point in calling)
192 bool needAnotherIt= false; // did this BB change any OutSets of pred.s
193 // whose POId is lower
196 BasicBlock::pred_const_iterator PredBBI = BaseBB->pred_begin();
198 for( ; PredBBI != BaseBB->pred_end() ; PredBBI++) {
199 assert( *PredBBI ); // assert that the predecessor is valid
200 BBLiveVar *PredLVBB = LVMap[*PredBBI];
203 if( setPropagate( &(PredLVBB->OutSet), &InSet, *PredBBI ) == true) {
204 PredLVBB->OutSetChanged = true;
206 // if the predec POId is lower than mine
207 if( PredLVBB->getPOId() <= POId)
208 needAnotherIt = true;
213 return needAnotherIt;
219 /* ----------------- Methods For Debugging (Printing) ----------------- */
221 void BBLiveVar::printAllSets() const
223 cerr << " Defs: "; DefSet.printSet(); cerr << endl;
224 cerr << " In: "; InSet.printSet(); cerr << endl;
225 cerr << " Out: "; OutSet.printSet(); cerr << endl;
228 void BBLiveVar::printInOutSets() const
230 cerr << " In: "; InSet.printSet(); cerr << endl;
231 cerr << " Out: "; OutSet.printSet(); cerr << endl;