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