1 #include "llvm/Analysis/LiveVar/BBLiveVar.h"
2 #include "llvm/Analysis/LiveVar/MethodLiveVarInfo.h"
3 #include "llvm/CodeGen/MachineInstr.h"
4 #include "llvm/BasicBlock.h"
6 /// BROKEN: Should not include sparc stuff directly into here
7 #include "../../Target/Sparc/SparcInternals.h" // Only for PHI defn
13 //-----------------------------------------------------------------------------
15 //-----------------------------------------------------------------------------
16 BBLiveVar::BBLiveVar( const BasicBlock *const baseBB, unsigned int RdfoId)
17 : BaseBB(baseBB), DefSet(), InSet(),
18 OutSet(), PhiArgMap() {
20 InSetChanged = OutSetChanged = false;
25 //-----------------------------------------------------------------------------
26 // caluculates def and use sets for each BB
27 // There are two passes over operands of a machine instruction. This is
28 // because, we can have instructions like V = V + 1, since we no longer
29 // assume single definition.
30 //-----------------------------------------------------------------------------
32 void BBLiveVar::calcDefUseSets()
34 // get the iterator for machine instructions
35 const MachineCodeForBasicBlock& MIVec = BaseBB->getMachineInstrVec();
36 MachineCodeForBasicBlock::const_reverse_iterator
37 MInstIterator = MIVec.rbegin();
39 // iterate over all the machine instructions in BB
40 for( ; MInstIterator != MIVec.rend(); ++MInstIterator) {
42 const MachineInstr * MInst = *MInstIterator; // MInst is the machine inst
45 if( DEBUG_LV > 1) { // debug msg
46 cerr << " *Iterating over machine instr ";
51 // iterate over MI operands to find defs
52 for( MachineInstr::val_const_op_iterator OpI(MInst); !OpI.done() ; ++OpI) {
54 if( OpI.isDef() ) // add to Defs only if this operand is a def
58 // do for implicit operands as well
59 for( unsigned i=0; i < MInst->getNumImplicitRefs(); ++i) {
60 if( MInst->implicitRefIsDefined(i) )
61 addDef( MInst->getImplicitRef(i) );
65 bool IsPhi = ( MInst->getOpCode() == PHI );
68 // iterate over MI operands to find uses
69 for (MachineInstr::val_const_op_iterator OpI(MInst); !OpI.done() ; ++OpI) {
70 const Value *Op = *OpI;
72 if ( ((Op)->getType())->isLabelType() )
73 continue; // don't process labels
75 if(! OpI.isDef() ) { // add to Defs only if this operand is a use
78 if( IsPhi ) { // for a phi node
79 // put args into the PhiArgMap (Val -> BB)
81 const Value * ArgVal = Op;
82 ++OpI; // increment to point to BB of value
83 const Value * BBVal = *OpI;
86 assert( (BBVal)->getValueType() == Value::BasicBlockVal );
88 PhiArgMap[ ArgVal ] = (const BasicBlock *) (BBVal);
89 assert( PhiArgMap[ ArgVal ] );
91 if( DEBUG_LV > 1) { // debug msg of level 2
92 cerr << " - phi operand ";
94 cerr << " came from BB ";
95 printValue( PhiArgMap[ ArgVal ]);
103 } // for all operands
105 // do for implicit operands as well
106 for( unsigned i=0; i < MInst->getNumImplicitRefs(); ++i) {
108 assert( !IsPhi && "Phi cannot have implicit opeands");
109 const Value *Op = MInst->getImplicitRef(i);
111 if ( ((Op)->getType())->isLabelType() )
112 continue; // don't process labels
113 if( ! MInst->implicitRefIsDefined(i) )
117 } // for all machine instructions
122 //-----------------------------------------------------------------------------
123 // To add an operand which is a def
124 //-----------------------------------------------------------------------------
125 void BBLiveVar::addDef(const Value *Op)
127 DefSet.insert(Op); // operand is a def - so add to def set
128 InSet.erase(Op); // this definition kills any uses
132 cerr << " +Def: "; printValue( Op ); cerr << "\n";
137 //-----------------------------------------------------------------------------
138 // To add an operand which is a use
139 //-----------------------------------------------------------------------------
140 void BBLiveVar::addUse(const Value *Op)
142 InSet.insert(Op); // An operand is a use - so add to use set
143 OutSet.erase(Op); // remove if there is a def below this use
146 if( DEBUG_LV > 1) { // debug msg of level 2
147 cerr << " Use: "; printValue( Op ); cerr << endl;
153 //-----------------------------------------------------------------------------
154 // Applies the transfer function to a basic block to produce the InSet using
156 //-----------------------------------------------------------------------------
158 bool BBLiveVar::applyTransferFunc() // calculates the InSet in terms of OutSet
161 // IMPORTANT: caller should check whether the OutSet changed
162 // (else no point in calling)
164 LiveVarSet OutMinusDef; // set to hold (Out[B] - Def[B])
165 OutMinusDef.setDifference( &OutSet, &DefSet);
166 InSetChanged = InSet.setUnion( &OutMinusDef );
168 OutSetChanged = false; // no change to OutSet since transf func applied
174 //-----------------------------------------------------------------------------
175 // calculates Out set using In sets of the predecessors
176 //-----------------------------------------------------------------------------
177 bool BBLiveVar::setPropagate( LiveVarSet *const OutSet,
178 const LiveVarSet *const InSet,
179 const BasicBlock *const PredBB) {
181 LiveVarSet::const_iterator InIt;
182 pair<LiveVarSet::iterator, bool> result;
183 bool changed = false;
184 const BasicBlock *PredBBOfPhiArg;
186 // for all all elements in InSet
187 for( InIt = InSet->begin() ; InIt != InSet->end(); InIt++) {
188 PredBBOfPhiArg = PhiArgMap[ *InIt ];
190 // if this var is not a phi arg OR
191 // it's a phi arg and the var went down from this BB
192 if( !PredBBOfPhiArg || PredBBOfPhiArg == PredBB) {
193 result = OutSet->insert( *InIt ); // insert to this set
194 if( result.second == true) changed = true;
202 //-----------------------------------------------------------------------------
203 // propogates in set to OutSets of PREDECESSORs
204 //-----------------------------------------------------------------------------
205 bool BBLiveVar::applyFlowFunc(BBToBBLiveVarMapType LVMap)
208 // IMPORTANT: caller should check whether inset changed
209 // (else no point in calling)
211 bool needAnotherIt= false; // did this BB change any OutSets of pred.s
212 // whose POId is lower
215 BasicBlock::pred_const_iterator PredBBI = BaseBB->pred_begin();
217 for( ; PredBBI != BaseBB->pred_end() ; PredBBI++) {
218 assert( *PredBBI ); // assert that the predecessor is valid
219 BBLiveVar *PredLVBB = LVMap[*PredBBI];
222 if( setPropagate( &(PredLVBB->OutSet), &InSet, *PredBBI ) == true) {
223 PredLVBB->OutSetChanged = true;
225 // if the predec POId is lower than mine
226 if( PredLVBB->getPOId() <= POId)
227 needAnotherIt = true;
232 return needAnotherIt;
238 /* ----------------- Methods For Debugging (Printing) ----------------- */
240 void BBLiveVar::printAllSets() const
242 cerr << " Defs: "; DefSet.printSet(); cerr << endl;
243 cerr << " In: "; InSet.printSet(); cerr << endl;
244 cerr << " Out: "; OutSet.printSet(); cerr << endl;
247 void BBLiveVar::printInOutSets() const
249 cerr << " In: "; InSet.printSet(); cerr << endl;
250 cerr << " Out: "; OutSet.printSet(); cerr << endl;