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