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 "llvm/CodeGen/Sparc.h"
   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       const Value *Op = *OpI;
  45
  46       if( OpI.isDef() ) {     // add to Defs only if this operand is a def
  47
  48         DefSet.add( Op );     // operand is a def - so add to def set
  49         InSet.remove( Op);    // this definition kills any uses
  50         InSetChanged = true;
  51
  52         if( DEBUG_LV > 1) {
  53           cout << "  +Def: "; printValue( Op ); cout << endl;
  54         }
  55       }
  56     }
  57
  58     bool IsPhi = ( MInst->getOpCode() == PHI );
  59
  60
  61     // iterate over  MI operands to find uses
  62     for(MachineInstr::val_op_const_iterator OpI(MInst); !OpI.done() ;  ++OpI) {
  63       const Value *Op = *OpI;
  64
  65       if ( ((Op)->getType())->isLabelType() )
  66         continue;             // don't process labels
  67
  68       if(! OpI.isDef() ) {    // add to Defs only if this operand is a use
  69
  70         InSet.add( Op );      // An operand is a use - so add to use set
  71         OutSet.remove( Op );  // remove if there is a def below this use
  72         InSetChanged = true;
  73
  74         if( DEBUG_LV > 1) {   // debug msg of level 2
  75           cout << "   Use: "; printValue( Op ); cout << endl;
  76         }
  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             cout << "   - phi operand ";
  93             printValue( ArgVal );
  94             cout  << " came from BB ";
  95             printValue( PhiArgMap[ ArgVal ]);
  96             cout<<endl;
  97           }
  98
  99         }
 100
 101       }
 102     }
 103
 104   } // for all machine instructions
 105 }
 106
 107
 108
 109 bool BBLiveVar::applyTransferFunc() // calculates the InSet in terms of OutSet
 110 {
 111
 112   // IMPORTANT: caller should check whether the OutSet changed
 113   //           (else no point in calling)
 114
 115   LiveVarSet OutMinusDef;     // set to hold (Out[B] - Def[B])
 116   OutMinusDef.setDifference( &OutSet, &DefSet);
 117   InSetChanged = InSet.setUnion( &OutMinusDef );
 118
 119   OutSetChanged = false;      // no change to OutSet since transf func applied
 120
 121   return InSetChanged;
 122 }
 123
 124
 125
 126 // calculates Out set using In sets of the predecessors
 127 bool BBLiveVar::setPropagate( LiveVarSet *const OutSet,
 128                               const LiveVarSet *const InSet,
 129                               const BasicBlock *const PredBB) {
 130
 131   LiveVarSet::const_iterator InIt;
 132   pair<LiveVarSet::iterator, bool> result;
 133   bool changed = false;
 134   const BasicBlock *PredBBOfPhiArg;
 135
 136   // for all all elements in InSet
 137   for( InIt = InSet->begin() ; InIt != InSet->end(); InIt++) {
 138     PredBBOfPhiArg =  PhiArgMap[ *InIt ];
 139
 140     // if this var is not a phi arg OR
 141     // it's a phi arg and the var went down from this BB
 142     if( !PredBBOfPhiArg || PredBBOfPhiArg == PredBB) {
 143       result = OutSet->insert( *InIt );               // insert to this set
 144       if( result.second == true) changed = true;
 145     }
 146   }
 147
 148   return changed;
 149 }
 150
 151
 152
 153 // propogates in set to OutSets of PREDECESSORs
 154
 155 bool BBLiveVar::applyFlowFunc(BBToBBLiveVarMapType LVMap)
 156 {
 157
 158   // IMPORTANT: caller should check whether inset changed
 159   //            (else no point in calling)
 160
 161   bool needAnotherIt= false;  // did this BB change any OutSets of pred.s
 162                               // whose POId is lower
 163
 164
 165   cfg::pred_const_iterator PredBBI = cfg::pred_begin(BaseBB);
 166
 167   for( ; PredBBI != cfg::pred_end(BaseBB) ; PredBBI++) {
 168     assert( *PredBBI );       // assert that the predecessor is valid
 169     BBLiveVar  *PredLVBB = LVMap[*PredBBI];
 170
 171                               // do set union
 172     if(  setPropagate( &(PredLVBB->OutSet), &InSet, *PredBBI ) == true) {
 173       PredLVBB->OutSetChanged = true;
 174
 175       // if the predec POId is lower than mine
 176       if( PredLVBB->getPOId() <= POId)
 177         needAnotherIt = true;
 178     }
 179
 180   }  // for
 181
 182   return needAnotherIt;
 183
 184 }
 185
 186
 187
 188 /* ----------------- Methods For Debugging (Printing) ----------------- */
 189
 190 void BBLiveVar::printAllSets() const
 191 {
 192   cout << "  Defs: ";   DefSet.printSet();  cout << endl;
 193   cout << "  In: ";   InSet.printSet();  cout << endl;
 194   cout << "  Out: ";   OutSet.printSet();  cout << endl;
 195 }
 196
 197 void BBLiveVar::printInOutSets() const
 198 {
 199   cout << "  In: ";   InSet.printSet();  cout << endl;
 200   cout << "  Out: ";   OutSet.printSet();  cout << endl;
 201 }
 202
 203
 204
 205