lib/Target/SparcV9/LiveVar/BBLiveVar.cpp

   1 #include "llvm/Analysis/LiveVar/BBLiveVar.h"
   2
   3
   4 /********************* Implementation **************************************/
   5
   6 BBLiveVar::BBLiveVar( const BasicBlock* baseBB, unsigned int RdfoId)
   7                       : DefSet(),  InSet(), OutSet(), PhiArgMap() {
   8     BaseBB = baseBB;
   9     InSetChanged = OutSetChanged = false;
  10     POId = RdfoId;
  11 }
  12
  13
  14
  15 void BBLiveVar::calcDefUseSets()  // caluculates def and use sets for each BB
  16 {
  17                                                 // instructions in basic block
  18   const BasicBlock::InstListType&  InstListInBB = BaseBB->getInstList();
  19
  20   BasicBlock::InstListType::const_reverse_iterator
  21     InstIterator = InstListInBB.rbegin();  // get the iterator for instructions
  22
  23                                      // iterate over all the instructions in BB
  24   for( ; InstIterator != InstListInBB.rend(); InstIterator++) {
  25
  26     const Instruction * Inst  = *InstIterator;     // Inst is the current instr
  27     assert(Inst);
  28
  29     if( Inst->isDefinition() ) {  // add to Defs only if this instr is a def
  30
  31       DefSet.add( Inst );   // nstruction is a def - so add to def set
  32       InSet.remove( Inst);  // this definition kills any uses
  33       InSetChanged = true;
  34       //cout << " adding inst to def "; printValue( Inst ); cout << endl;
  35     }
  36
  37     Instruction::op_const_iterator
  38       OpI = Inst->op_begin();                // get iterator for operands
  39
  40     bool IsPhi=( Inst->getOpcode() == Instruction::PHINode );  // Is this a phi
  41
  42     for(int OpNum=0 ; OpI != Inst->op_end() ; OpI++) { // iterate over operands
  43
  44       if ( ((*OpI)->getType())->isLabelType() )
  45         continue;                                      // don't process labels
  46
  47       InSet.add( *OpI );      // An operand is a use - so add to use set
  48       OutSet.remove( *OpI );  // remove if there is a definition below this use
  49
  50       if( IsPhi ) {           // for a phi node
  51                               // put args into the PhiArgMap
  52         PhiArgMap[ *OpI ] = ((PHINode *) Inst )->getIncomingBlock( OpNum++ );
  53         assert( PhiArgMap[ *OpI ] );
  54         //cout << " Phi operand "; printValue( *OpI );
  55         //cout  << " came from BB "; printValue(PhiArgMap[*OpI]); cout<<endl;
  56       }
  57
  58       InSetChanged = true;
  59       //cout << " adding operand to use "; printValue( *OpI ); cout << endl;
  60     }
  61
  62   }
  63 }
  64
  65
  66
  67
  68 bool BBLiveVar::applyTransferFunc() // calculates the InSet in terms of OutSet
  69 {
  70
  71   // IMPORTANT: caller should check whether the OutSet changed
  72   //           (else no point in calling)
  73
  74   LiveVarSet OutMinusDef;                      // set to hold (Out[B] - Def[B])
  75   OutMinusDef.setDifference( &OutSet, &DefSet);
  76   InSetChanged = InSet.setUnion( &OutMinusDef );
  77
  78   OutSetChanged = false;    // no change to OutSet since transfer func applied
  79
  80   return InSetChanged;
  81 }
  82
  83
  84
  85                         // calculates Out set using In sets of the predecessors
  86 bool BBLiveVar::setPropagate( LiveVarSet *const OutSet,
  87                               const LiveVarSet *const InSet,
  88                               const BasicBlock *const PredBB) {
  89
  90   LiveVarSet::const_iterator InIt;
  91   pair<LiveVarSet::iterator, bool> result;
  92   bool changed = false;
  93   const BasicBlock *PredBBOfPhiArg;
  94
  95                                                // for all all elements in InSet
  96   for( InIt = InSet->begin() ; InIt != InSet->end(); InIt++) {
  97     PredBBOfPhiArg =  PhiArgMap[ *InIt ];
  98
  99                         // if this var is not a phi arg or it came from this BB
 100     if( !PredBBOfPhiArg || PredBBOfPhiArg == PredBB) {
 101       result = OutSet->insert( *InIt );               // insert to this set
 102       if( result.second == true) changed = true;
 103     }
 104   }
 105
 106   return changed;
 107 }
 108
 109
 110
 111                                 // propogates in set to OutSets of PREDECESSORs
 112 bool BBLiveVar::applyFlowFunc(BBToBBLiveVarMapType LVMap)
 113 {
 114
 115   // IMPORTANT: caller should check whether inset changed
 116   //            (else no point in calling)
 117
 118   bool needAnotherIt= false;  // did this BB change any OutSets of pred.s
 119                               // whose POId is lower
 120
 121
 122   cfg::pred_const_iterator PredBBI = cfg::pred_begin(BaseBB);
 123
 124   for( ; PredBBI != cfg::pred_end(BaseBB) ; PredBBI++) {
 125     assert( *PredBBI );                 // assert that the predecessor is valid
 126     BBLiveVar  *PredLVBB = LVMap[*PredBBI];
 127
 128                                                                // do set union
 129     if(  setPropagate( &(PredLVBB->OutSet), &InSet, *PredBBI ) == true) {
 130       PredLVBB->OutSetChanged = true;
 131
 132       if( PredLVBB->getPOId() <= POId) // if the predec POId is lower than mine
 133         needAnotherIt = true;
 134     }
 135   } // for
 136
 137   return needAnotherIt;
 138
 139 }
 140
 141
 142
 143
 144
 145 /* ----------------- Methods For Debugging (Printing) ----------------- */
 146
 147 void BBLiveVar::printAllSets() const
 148 {
 149   cout << "Defs: ";   DefSet.printSet();  cout << endl;
 150   cout << "In: ";   InSet.printSet();  cout << endl;
 151   cout << "Out: ";   OutSet.printSet();  cout << endl;
 152 }
 153
 154 void BBLiveVar::printInOutSets() const
 155 {
 156   cout << "In: ";   InSet.printSet();  cout << endl;
 157   cout << "Out: ";   OutSet.printSet();  cout << endl;
 158 }