lib/Target/SparcV9/RegAlloc/LiveRangeInfo.cpp

   1 #include "llvm/CodeGen/LiveRangeInfo.h"
   2
   3 LiveRangeInfo::LiveRangeInfo(const Method *const M,
   4                              const TargetMachine& tm,
   5                              vector<RegClass *> &RCL)
   6                              : Meth(M), LiveRangeMap(),
   7                                TM(tm), RegClassList(RCL)
   8 { }
   9
  10
  11 // union two live ranges into one. The 2nd LR is deleted. Used for coalescing.
  12 // Note: the caller must make sure that L1 and L2 are distinct
  13
  14 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *const L1, LiveRange *L2)
  15 {
  16   assert( L1 != L2);
  17   L1->setUnion( L2 );             // add elements of L2 to L1
  18   ValueSet::iterator L2It;
  19
  20   for( L2It = L2->begin() ; L2It != L2->end(); ++L2It) {
  21
  22     //assert(( L1->getTypeID() == L2->getTypeID()) && "Merge:Different types");
  23
  24     L1->add( *L2It );            // add the var in L2 to L1
  25     LiveRangeMap[ *L2It ] = L1;  // now the elements in L2 should map to L1
  26   }
  27   delete ( L2 );                 // delete L2 as it is no longer needed
  28 }
  29
  30
  31
  32
  33 void LiveRangeInfo::constructLiveRanges()
  34 {
  35
  36   if( DEBUG_RA)
  37     cout << "Consturcting Live Ranges ..." << endl;
  38
  39   // first find the live ranges for all incoming args of the method since
  40   // those LRs start from the start of the method
  41
  42                                                  // get the argument list
  43   const Method::ArgumentListType& ArgList = Meth->getArgumentList();
  44                                                  // get an iterator to arg list
  45   Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
  46
  47
  48   for( ; ArgIt != ArgList.end() ; ++ArgIt) {     // for each argument
  49
  50     LiveRange * ArgRange = new LiveRange();      // creates a new LR and
  51     const Value *const Val = (const Value *) *ArgIt;
  52
  53     assert( Val);
  54
  55     ArgRange->add( Val );     // add the arg (def) to it
  56     LiveRangeMap[ Val ] = ArgRange;
  57
  58     // create a temp machine op to find the register class of value
  59     //const MachineOperand Op(MachineOperand::MO_VirtualRegister);
  60
  61     unsigned rcid = (TM.getRegInfo()).getRegClassIDOfValue( Val );
  62     ArgRange->setRegClass(RegClassList[ rcid ] );
  63
  64
  65     if( DEBUG_RA > 1) {
  66       cout << " adding LiveRange for argument ";
  67       printValue( (const Value *) *ArgIt); cout  << endl;
  68     }
  69   }
  70
  71
  72   // Now find all LRs for machine the instructions. A new LR will be created
  73   // only for defs in the machine instr since, we assume that all Values are
  74   // defined before they are used. However, there can be multiple defs for
  75   // the same Value in machine instructions.
  76
  77   Method::const_iterator BBI = Meth->begin();    // random iterator for BBs
  78
  79   for( ; BBI != Meth->end(); ++BBI) {            // go thru BBs in random order
  80
  81     // get the iterator for machine instructions
  82     const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
  83     MachineCodeForBasicBlock::const_iterator
  84       MInstIterator = MIVec.begin();
  85
  86     // iterate over all the machine instructions in BB
  87     for( ; MInstIterator != MIVec.end(); MInstIterator++) {
  88
  89       const MachineInstr * MInst = *MInstIterator;
  90
  91       // iterate over  MI operands to find defs
  92       for( MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done(); OpI++) {
  93
  94
  95         // delete later from here ************
  96         MachineOperand::MachineOperandType OpTyp =
  97           OpI.getMachineOperand().getOperandType();
  98
  99         if (DEBUG_RA && OpTyp == MachineOperand::MO_CCRegister) {
 100           cout << "\n**CC reg found. Is Def=" << OpI.isDef() << " Val:";
 101           printValue( OpI.getMachineOperand().getVRegValue() );
 102           cout << endl;
 103         }
 104         // ************* to here
 105
 106
 107
 108         // create a new LR iff this operand is a def
 109         if( OpI.isDef() ) {
 110
 111           const Value *const Def = *OpI;
 112           LiveRange *DefRange = LiveRangeMap[Def];
 113
 114           // see LR already there (because of multiple defs)
 115
 116           if( !DefRange) {                  // if it is not in LiveRangeMap
 117
 118             DefRange = new LiveRange();     // creates a new live range and
 119             DefRange->add( Def );           // add the instruction (def) to it
 120             LiveRangeMap[ Def ] = DefRange; // update the map
 121
 122             if( DEBUG_RA > 1) {
 123               cout << "  creating a LR for def: ";
 124               printValue(Def); cout  << endl;
 125             }
 126
 127             // set the register class of the new live range
 128             //assert( RegClassList.size() );
 129             MachineOperand::MachineOperandType OpTy =
 130               OpI.getMachineOperand().getOperandType();
 131
 132             bool isCC = ( OpTy == MachineOperand::MO_CCRegister);
 133             unsigned rcid = (TM.getRegInfo()).getRegClassIDOfValue(
 134                             OpI.getMachineOperand().getVRegValue(), isCC );
 135
 136
 137             if(isCC && DEBUG_RA) {
 138               cout  << "\a**created a LR for a CC reg:";
 139               printValue( OpI.getMachineOperand().getVRegValue() );
 140             }
 141
 142             DefRange->setRegClass( RegClassList[ rcid ] );
 143
 144           }
 145           else {
 146             DefRange->add( Def );           // add the opearand to def range
 147                                             // update the map - Operand points
 148                                             // to the merged set
 149             LiveRangeMap[ Def ] = DefRange;
 150
 151             if( DEBUG_RA > 1) {
 152               cout << "   added to an existing LR for def: ";
 153               printValue( Def ); cout  << endl;
 154             }
 155           }
 156
 157
 158
 159
 160         } // if isDef()
 161
 162       } // for all opereands in machine instructions
 163
 164     } // for all machine instructions in the BB
 165
 166   } // for all BBs in method
 167
 168   if( DEBUG_RA)
 169     cout << "Initial Live Ranges constructed!" << endl;
 170
 171 }
 172
 173
 174
 175 void LiveRangeInfo::coalesceLRs()
 176 {
 177
 178 /* Algorithm:
 179    for each BB in method
 180      for each machine instruction (inst)
 181        for each definition (def) in inst
 182          for each operand (op) of inst that is a use
 183            if the def and op are of the same type
 184              if the def and op do not interfere //i.e., not simultaneously live
 185                if (degree(LR of def) + degree(LR of op)) <= # avail regs
 186                  merge2IGNodes(def, op) // i.e., merge 2 LRs
 187
 188 */
 189
 190   if( DEBUG_RA)
 191     cout << endl << "Coalscing LRs ..." << endl;
 192
 193   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 194
 195   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 196
 197     // get the iterator for machine instructions
 198     const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 199     MachineCodeForBasicBlock::const_iterator
 200       MInstIterator = MIVec.begin();
 201
 202     // iterate over all the machine instructions in BB
 203     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 204
 205       const MachineInstr * MInst = *MInstIterator;
 206
 207       if( DEBUG_RA > 1) {
 208         cout << " *Iterating over machine instr ";
 209         MInst->dump();
 210         cout << endl;
 211       }
 212
 213
 214       // iterate over  MI operands to find defs
 215       for(MachineInstr::val_op_const_iterator DefI(MInst);!DefI.done();++DefI){
 216
 217         if( DefI.isDef() ) {            // iff this operand is a def
 218
 219           LiveRange *const LROfDef = getLiveRangeForValue( *DefI );
 220           assert( LROfDef );
 221           RegClass *const RCOfDef = LROfDef->getRegClass();
 222
 223           MachineInstr::val_op_const_iterator UseI(MInst);
 224           for( ; !UseI.done(); ++UseI){ // for all uses
 225
 226             LiveRange *const LROfUse = getLiveRangeForValue( *UseI );
 227
 228             if( ! LROfUse ) {           // if LR of use is not found
 229
 230               //don't warn about labels
 231               if (!((*UseI)->getType())->isLabelType() && DEBUG_RA) {
 232                 cout<<" !! Warning: No LR for use "; printValue(*UseI);
 233                 cout << endl;
 234               }
 235               continue;                 // ignore and continue
 236             }
 237
 238             if( LROfUse == LROfDef)     // nothing to merge if they are same
 239               continue;
 240
 241             // RegClass *const RCOfUse = LROfUse->getRegClass();
 242
 243             //if( RCOfDef == RCOfUse ) {  // if the reg classes are the same
 244
 245
 246             if( LROfUse->getTypeID() == LROfDef->getTypeID() ) {
 247
 248               if( ! RCOfDef->getInterference(LROfDef, LROfUse) ) {
 249
 250                 unsigned CombinedDegree =
 251                   LROfDef->getUserIGNode()->getNumOfNeighbors() +
 252                   LROfUse->getUserIGNode()->getNumOfNeighbors();
 253
 254                 if( CombinedDegree <= RCOfDef->getNumOfAvailRegs() ) {
 255
 256                   RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
 257                   unionAndUpdateLRs(LROfDef, LROfUse);
 258
 259                 } // if combined degree is less than # of regs
 260
 261               } // if def and use do not interfere
 262
 263             } // if reg classes are the same
 264
 265           } // for all uses
 266
 267         } // if def
 268
 269       } // for all defs
 270
 271     } // for all machine instructions
 272
 273   } // for all BBs
 274
 275   if( DEBUG_RA)
 276     cout << endl << "Coalscing Done!" << endl;
 277
 278 }
 279
 280
 281
 282
 283
 284 /*--------------------------- Debug code for printing ---------------*/
 285
 286
 287 void LiveRangeInfo::printLiveRanges()
 288 {
 289   LiveRangeMapType::iterator HMI = LiveRangeMap.begin();   // hash map iterator
 290   cout << endl << "Printing Live Ranges from Hash Map:" << endl;
 291   for( ; HMI != LiveRangeMap.end() ; HMI ++ ) {
 292     if( (*HMI).first ) {
 293       cout <<" "; printValue((*HMI).first);  cout  << "\t: ";
 294       ((*HMI).second)->printSet(); cout << endl;
 295     }
 296   }
 297 }
 298
 299