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