lib/Target/SparcV9/LiveVar/BBLiveVar.cpp

   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
   5
   6
   7 /********************* Implementation **************************************/
   8
   9 BBLiveVar::BBLiveVar( const BasicBlock *const  baseBB, unsigned int RdfoId)
  10                       : BaseBB(baseBB), DefSet(),  InSet(),
  11                         OutSet(), PhiArgMap() {
  12     BaseBB = baseBB;
  13     InSetChanged = OutSetChanged = false;
  14     POId = RdfoId;
  15 }
  16
  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.
  21
  22 void BBLiveVar::calcDefUseSets()
  23 {
  24   // get the iterator for machine instructions
  25   const MachineCodeForBasicBlock& MIVec = BaseBB->getMachineInstrVec();
  26   MachineCodeForBasicBlock::const_reverse_iterator
  27     MInstIterator = MIVec.rbegin();
  28
  29   // iterate over all the machine instructions in BB
  30   for( ; MInstIterator != MIVec.rend(); ++MInstIterator) {
  31
  32     const MachineInstr * MInst  = *MInstIterator;  // MInst is the machine inst
  33     assert(MInst);
  34
  35     if( DEBUG_LV > 1) {                            // debug msg
  36       cout << " *Iterating over machine instr ";
  37       MInst->dump();
  38       cout << endl;
  39     }
  40
  41     // iterate over  MI operands to find defs
  42     for( MachineInstr::val_op_const_iterator OpI(MInst); !OpI.done() ; ++OpI) {
  43
  44       if( OpI.isDef() )      // add to Defs only if this operand is a def
  45         addDef( *OpI );
  46     }
  47
  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) );
  52      }
  53
  54
  55     bool IsPhi = ( MInst->getOpCode() == PHI );
  56
  57
  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;
  61
  62       if ( ((Op)->getType())->isLabelType() )
  63         continue;             // don't process labels
  64
  65       if(! OpI.isDef() ) {   // add to Defs only if this operand is a use
  66         addUse( Op );
  67
  68         if( IsPhi ) {         // for a phi node
  69           // put args into the PhiArgMap (Val -> BB)
  70
  71           const Value * ArgVal = Op;
  72           ++OpI;              // increment to point to BB of value
  73           const Value * BBVal = *OpI;
  74
  75
  76           assert( (BBVal)->getValueType() == Value::BasicBlockVal );
  77
  78           PhiArgMap[ ArgVal ] = (const BasicBlock *) (BBVal);
  79           assert( PhiArgMap[ ArgVal ] );
  80
  81           if( DEBUG_LV > 1) {   // debug msg of level 2
  82             cout << "   - phi operand ";
  83             printValue( ArgVal );
  84             cout  << " came from BB ";
  85             printValue( PhiArgMap[ ArgVal ]);
  86             cout<<endl;
  87           }
  88
  89         } // if( IsPhi )
  90
  91       } // if a use
  92
  93     } // for all operands
  94
  95     // do for implicit operands as well
  96     for( unsigned i=0; i < MInst->getNumImplicitRefs(); ++i) {
  97
  98       assert( !IsPhi && "Phi cannot have implicit opeands");
  99       const Value *Op =  MInst->getImplicitRef(i);
 100
 101       if ( ((Op)->getType())->isLabelType() )
 102         continue;             // don't process labels
 103       if(  ! MInst->implicitRefIsDefined(i) )
 104         addUse( Op );
 105      }
 106
 107   } // for all machine instructions
 108 }
 109
 110
 111 // To add an operand wichi is a def
 112
 113 void  BBLiveVar::addDef(const Value *Op)
 114 {
 115   DefSet.add( Op );     // operand is a def - so add to def set
 116   InSet.remove( Op);    // this definition kills any uses
 117   InSetChanged = true;
 118
 119   if( DEBUG_LV > 1) {
 120     cout << "  +Def: "; printValue( Op ); cout << endl;
 121   }
 122 }
 123
 124 // To add an operand which is a use
 125
 126 void  BBLiveVar::addUse(const Value *Op)
 127 {
 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
 130   InSetChanged = true;
 131
 132   if( DEBUG_LV > 1) {   // debug msg of level 2
 133     cout << "   Use: "; printValue( Op ); cout << endl;
 134   }
 135
 136 }
 137
 138
 139
 140 bool BBLiveVar::applyTransferFunc() // calculates the InSet in terms of OutSet
 141 {
 142
 143   // IMPORTANT: caller should check whether the OutSet changed
 144   //           (else no point in calling)
 145
 146   LiveVarSet OutMinusDef;     // set to hold (Out[B] - Def[B])
 147   OutMinusDef.setDifference( &OutSet, &DefSet);
 148   InSetChanged = InSet.setUnion( &OutMinusDef );
 149
 150   OutSetChanged = false;      // no change to OutSet since transf func applied
 151
 152   return InSetChanged;
 153 }
 154
 155
 156
 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) {
 161
 162   LiveVarSet::const_iterator InIt;
 163   pair<LiveVarSet::iterator, bool> result;
 164   bool changed = false;
 165   const BasicBlock *PredBBOfPhiArg;
 166
 167   // for all all elements in InSet
 168   for( InIt = InSet->begin() ; InIt != InSet->end(); InIt++) {
 169     PredBBOfPhiArg =  PhiArgMap[ *InIt ];
 170
 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;
 176     }
 177   }
 178
 179   return changed;
 180 }
 181
 182
 183
 184 // propogates in set to OutSets of PREDECESSORs
 185
 186 bool BBLiveVar::applyFlowFunc(BBToBBLiveVarMapType LVMap)
 187 {
 188
 189   // IMPORTANT: caller should check whether inset changed
 190   //            (else no point in calling)
 191
 192   bool needAnotherIt= false;  // did this BB change any OutSets of pred.s
 193                               // whose POId is lower
 194
 195
 196   BasicBlock::pred_const_iterator PredBBI = BaseBB->pred_begin();
 197
 198   for( ; PredBBI != BaseBB->pred_end() ; PredBBI++) {
 199     assert( *PredBBI );       // assert that the predecessor is valid
 200     BBLiveVar  *PredLVBB = LVMap[*PredBBI];
 201
 202                               // do set union
 203     if(  setPropagate( &(PredLVBB->OutSet), &InSet, *PredBBI ) == true) {
 204       PredLVBB->OutSetChanged = true;
 205
 206       // if the predec POId is lower than mine
 207       if( PredLVBB->getPOId() <= POId)
 208         needAnotherIt = true;
 209     }
 210
 211   }  // for
 212
 213   return needAnotherIt;
 214
 215 }
 216
 217
 218
 219 /* ----------------- Methods For Debugging (Printing) ----------------- */
 220
 221 void BBLiveVar::printAllSets() const
 222 {
 223   cout << "  Defs: ";   DefSet.printSet();  cout << endl;
 224   cout << "  In: ";   InSet.printSet();  cout << endl;
 225   cout << "  Out: ";   OutSet.printSet();  cout << endl;
 226 }
 227
 228 void BBLiveVar::printInOutSets() const
 229 {
 230   cout << "  In: ";   InSet.printSet();  cout << endl;
 231   cout << "  Out: ";   OutSet.printSet();  cout << endl;
 232 }
 233
 234
 235
 236