1 #include "llvm/Analysis/LiveVar/BBLiveVar.h"
2 #include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
3 #include "llvm/CodeGen/MachineInstr.h"
5 /// BROKEN: Should not include sparc stuff directly into here
6 #include "../../Target/Sparc/SparcInternals.h" // Only for PHI defn
12 //-----------------------------------------------------------------------------
14 //-----------------------------------------------------------------------------
15 BBLiveVar::BBLiveVar( const BasicBlock *const baseBB, unsigned int RdfoId)
16 : BaseBB(baseBB), DefSet(), InSet(),
17 OutSet(), PhiArgMap() {
19 InSetChanged = OutSetChanged = false;
24 //-----------------------------------------------------------------------------
25 // caluculates def and use sets for each BB
26 // There are two passes over operands of a machine instruction. This is
27 // because, we can have instructions like V = V + 1, since we no longer
28 // assume single definition.
29 //-----------------------------------------------------------------------------
31 void BBLiveVar::calcDefUseSets()
33 // get the iterator for machine instructions
34 const MachineCodeForBasicBlock& MIVec = BaseBB->getMachineInstrVec();
35 MachineCodeForBasicBlock::const_reverse_iterator
36 MInstIterator = MIVec.rbegin();
38 // iterate over all the machine instructions in BB
39 for( ; MInstIterator != MIVec.rend(); ++MInstIterator) {
41 const MachineInstr * MInst = *MInstIterator; // MInst is the machine inst
44 if( DEBUG_LV > 1) { // debug msg
45 cerr << " *Iterating over machine instr ";
50 // iterate over MI operands to find defs
51 for( MachineInstr::val_const_op_iterator OpI(MInst); !OpI.done() ; ++OpI) {
53 if( OpI.isDef() ) // add to Defs only if this operand is a def
57 // do for implicit operands as well
58 for( unsigned i=0; i < MInst->getNumImplicitRefs(); ++i) {
59 if( MInst->implicitRefIsDefined(i) )
60 addDef( MInst->getImplicitRef(i) );
64 bool IsPhi = ( MInst->getOpCode() == PHI );
67 // iterate over MI operands to find uses
68 for (MachineInstr::val_const_op_iterator OpI(MInst); !OpI.done() ; ++OpI) {
69 const Value *Op = *OpI;
71 if ( ((Op)->getType())->isLabelType() )
72 continue; // don't process labels
74 if(! OpI.isDef() ) { // add to Defs only if this operand is a use
77 if( IsPhi ) { // for a phi node
78 // put args into the PhiArgMap (Val -> BB)
80 const Value * ArgVal = Op;
81 ++OpI; // increment to point to BB of value
82 const Value * BBVal = *OpI;
85 assert( (BBVal)->getValueType() == Value::BasicBlockVal );
87 PhiArgMap[ ArgVal ] = (const BasicBlock *) (BBVal);
88 assert( PhiArgMap[ ArgVal ] );
90 if( DEBUG_LV > 1) { // debug msg of level 2
91 cerr << " - phi operand ";
93 cerr << " came from BB ";
94 printValue( PhiArgMap[ ArgVal ]);
102 } // for all operands
104 // do for implicit operands as well
105 for( unsigned i=0; i < MInst->getNumImplicitRefs(); ++i) {
107 assert( !IsPhi && "Phi cannot have implicit opeands");
108 const Value *Op = MInst->getImplicitRef(i);
110 if ( ((Op)->getType())->isLabelType() )
111 continue; // don't process labels
112 if( ! MInst->implicitRefIsDefined(i) )
116 } // for all machine instructions
121 //-----------------------------------------------------------------------------
122 // To add an operand which is a def
123 //-----------------------------------------------------------------------------
124 void BBLiveVar::addDef(const Value *Op)
126 DefSet.add( Op ); // operand is a def - so add to def set
127 InSet.remove( Op); // this definition kills any uses
131 cerr << " +Def: "; printValue( Op ); cerr << "\n";
136 //-----------------------------------------------------------------------------
137 // To add an operand which is a use
138 //-----------------------------------------------------------------------------
139 void BBLiveVar::addUse(const Value *Op)
141 InSet.add( Op ); // An operand is a use - so add to use set
142 OutSet.remove( Op ); // remove if there is a def below this use
145 if( DEBUG_LV > 1) { // debug msg of level 2
146 cerr << " Use: "; printValue( Op ); cerr << endl;
152 //-----------------------------------------------------------------------------
153 // Applies the transfer function to a basic block to produce the InSet using
155 //-----------------------------------------------------------------------------
157 bool BBLiveVar::applyTransferFunc() // calculates the InSet in terms of OutSet
160 // IMPORTANT: caller should check whether the OutSet changed
161 // (else no point in calling)
163 LiveVarSet OutMinusDef; // set to hold (Out[B] - Def[B])
164 OutMinusDef.setDifference( &OutSet, &DefSet);
165 InSetChanged = InSet.setUnion( &OutMinusDef );
167 OutSetChanged = false; // no change to OutSet since transf func applied
173 //-----------------------------------------------------------------------------
174 // calculates Out set using In sets of the predecessors
175 //-----------------------------------------------------------------------------
176 bool BBLiveVar::setPropagate( LiveVarSet *const OutSet,
177 const LiveVarSet *const InSet,
178 const BasicBlock *const PredBB) {
180 LiveVarSet::const_iterator InIt;
181 pair<LiveVarSet::iterator, bool> result;
182 bool changed = false;
183 const BasicBlock *PredBBOfPhiArg;
185 // for all all elements in InSet
186 for( InIt = InSet->begin() ; InIt != InSet->end(); InIt++) {
187 PredBBOfPhiArg = PhiArgMap[ *InIt ];
189 // if this var is not a phi arg OR
190 // it's a phi arg and the var went down from this BB
191 if( !PredBBOfPhiArg || PredBBOfPhiArg == PredBB) {
192 result = OutSet->insert( *InIt ); // insert to this set
193 if( result.second == true) changed = true;
201 //-----------------------------------------------------------------------------
202 // propogates in set to OutSets of PREDECESSORs
203 //-----------------------------------------------------------------------------
204 bool BBLiveVar::applyFlowFunc(BBToBBLiveVarMapType LVMap)
207 // IMPORTANT: caller should check whether inset changed
208 // (else no point in calling)
210 bool needAnotherIt= false; // did this BB change any OutSets of pred.s
211 // whose POId is lower
214 BasicBlock::pred_const_iterator PredBBI = BaseBB->pred_begin();
216 for( ; PredBBI != BaseBB->pred_end() ; PredBBI++) {
217 assert( *PredBBI ); // assert that the predecessor is valid
218 BBLiveVar *PredLVBB = LVMap[*PredBBI];
221 if( setPropagate( &(PredLVBB->OutSet), &InSet, *PredBBI ) == true) {
222 PredLVBB->OutSetChanged = true;
224 // if the predec POId is lower than mine
225 if( PredLVBB->getPOId() <= POId)
226 needAnotherIt = true;
231 return needAnotherIt;
237 /* ----------------- Methods For Debugging (Printing) ----------------- */
239 void BBLiveVar::printAllSets() const
241 cerr << " Defs: "; DefSet.printSet(); cerr << endl;
242 cerr << " In: "; InSet.printSet(); cerr << endl;
243 cerr << " Out: "; OutSet.printSet(); cerr << endl;
246 void BBLiveVar::printInOutSets() const
248 cerr << " In: "; InSet.printSet(); cerr << endl;
249 cerr << " Out: "; OutSet.printSet(); cerr << endl;