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                                MRI( tm.getRegInfo()),
   9                                CallRetInstrList()
  10 { }
  11
  12
  13 // union two live ranges into one. The 2nd LR is deleted. Used for coalescing.
  14 // Note: the caller must make sure that L1 and L2 are distinct and both
  15 // LRs don't have suggested colors
  16
  17 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *const L1, LiveRange *L2)
  18 {
  19   assert( L1 != L2);
  20   L1->setUnion( L2 );             // add elements of L2 to L1
  21   ValueSet::iterator L2It;
  22
  23   for( L2It = L2->begin() ; L2It != L2->end(); ++L2It) {
  24
  25     //assert(( L1->getTypeID() == L2->getTypeID()) && "Merge:Different types");
  26
  27     L1->add( *L2It );            // add the var in L2 to L1
  28     LiveRangeMap[ *L2It ] = L1;  // now the elements in L2 should map to L1
  29   }
  30
  31
  32   // Now if LROfDef(L1) has a suggested color, it will remain.
  33   // But, if LROfUse(L2) has a suggested color, the new range
  34   // must have the same color.
  35
  36   if(L2->hasSuggestedColor())
  37     L1->setSuggestedColor( L2->getSuggestedColor() );
  38
  39
  40   if( L2->isCallInterference() )
  41     L1->setCallInterference();
  42
  43
  44   delete ( L2 );                 // delete L2 as it is no longer needed
  45 }
  46
  47
  48
  49
  50 void LiveRangeInfo::constructLiveRanges()
  51 {
  52
  53   if( DEBUG_RA)
  54     cout << "Consturcting Live Ranges ..." << endl;
  55
  56   // first find the live ranges for all incoming args of the method since
  57   // those LRs start from the start of the method
  58
  59                                                  // get the argument list
  60   const Method::ArgumentListType& ArgList = Meth->getArgumentList();
  61                                                  // get an iterator to arg list
  62   Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
  63
  64
  65   for( ; ArgIt != ArgList.end() ; ++ArgIt) {     // for each argument
  66
  67     LiveRange * ArgRange = new LiveRange();      // creates a new LR and
  68     const Value *const Val = (const Value *) *ArgIt;
  69
  70     assert( Val);
  71
  72     ArgRange->add( Val );     // add the arg (def) to it
  73     LiveRangeMap[ Val ] = ArgRange;
  74
  75     // create a temp machine op to find the register class of value
  76     //const MachineOperand Op(MachineOperand::MO_VirtualRegister);
  77
  78     unsigned rcid = MRI.getRegClassIDOfValue( Val );
  79     ArgRange->setRegClass(RegClassList[ rcid ] );
  80
  81
  82     if( DEBUG_RA > 1) {
  83       cout << " adding LiveRange for argument ";
  84       printValue( (const Value *) *ArgIt); cout  << endl;
  85     }
  86   }
  87
  88   // Now suggest hardware registers for these method args
  89   MRI.suggestRegs4MethodArgs(Meth, *this);
  90
  91
  92
  93   // Now find speical LLVM instructions (CALL, RET) and LRs in machine
  94   // instructions.
  95
  96
  97   Method::const_iterator BBI = Meth->begin();    // random iterator for BBs
  98
  99   for( ; BBI != Meth->end(); ++BBI) {            // go thru BBs in random order
 100
 101     // Now find all LRs for machine the instructions. A new LR will be created
 102     // only for defs in the machine instr since, we assume that all Values are
 103     // defined before they are used. However, there can be multiple defs for
 104     // the same Value in machine instructions.
 105
 106     // get the iterator for machine instructions
 107     const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 108     MachineCodeForBasicBlock::const_iterator
 109       MInstIterator = MIVec.begin();
 110
 111     // iterate over all the machine instructions in BB
 112     for( ; MInstIterator != MIVec.end(); MInstIterator++) {
 113
 114       const MachineInstr * MInst = *MInstIterator;
 115
 116       // Now if the machine instruction is a  call/return instruction,
 117       // add it to CallRetInstrList for processing its implicit operands
 118
 119       if( (TM.getInstrInfo()).isReturn( MInst->getOpCode()) ||
 120           (TM.getInstrInfo()).isCall( MInst->getOpCode()) )
 121         CallRetInstrList.push_back( MInst );
 122
 123
 124       // iterate over  MI operands to find defs
 125       for( MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done(); ++OpI) {
 126
 127         if( DEBUG_RA) {
 128           MachineOperand::MachineOperandType OpTyp =
 129             OpI.getMachineOperand().getOperandType();
 130
 131           if ( OpTyp == MachineOperand::MO_CCRegister) {
 132             cout << "\n**CC reg found. Is Def=" << OpI.isDef() << " Val:";
 133             printValue( OpI.getMachineOperand().getVRegValue() );
 134             cout << endl;
 135           }
 136         }
 137
 138         // create a new LR iff this operand is a def
 139         if( OpI.isDef() ) {
 140
 141           const Value *const Def = *OpI;
 142
 143
 144           // Only instruction values are accepted for live ranges here
 145
 146           if( Def->getValueType() != Value::InstructionVal ) {
 147             cout << "\n**%%Error: Def is not an instruction val. Def=";
 148             printValue( Def ); cout << endl;
 149             continue;
 150           }
 151
 152
 153           LiveRange *DefRange = LiveRangeMap[Def];
 154
 155           // see LR already there (because of multiple defs)
 156
 157           if( !DefRange) {                  // if it is not in LiveRangeMap
 158
 159             DefRange = new LiveRange();     // creates a new live range and
 160             DefRange->add( Def );           // add the instruction (def) to it
 161             LiveRangeMap[ Def ] = DefRange; // update the map
 162
 163             if( DEBUG_RA > 1) {
 164               cout << "  creating a LR for def: ";
 165               printValue(Def); cout  << endl;
 166             }
 167
 168             // set the register class of the new live range
 169             //assert( RegClassList.size() );
 170             MachineOperand::MachineOperandType OpTy =
 171               OpI.getMachineOperand().getOperandType();
 172
 173             bool isCC = ( OpTy == MachineOperand::MO_CCRegister);
 174             unsigned rcid = MRI.getRegClassIDOfValue(
 175                             OpI.getMachineOperand().getVRegValue(), isCC );
 176
 177
 178             if(isCC && DEBUG_RA) {
 179               cout  << "\a**created a LR for a CC reg:";
 180               printValue( OpI.getMachineOperand().getVRegValue() );
 181             }
 182
 183             DefRange->setRegClass( RegClassList[ rcid ] );
 184
 185           }
 186           else {
 187             DefRange->add( Def );           // add the opearand to def range
 188                                             // update the map - Operand points
 189                                             // to the merged set
 190             LiveRangeMap[ Def ] = DefRange;
 191
 192             if( DEBUG_RA > 1) {
 193               cout << "   added to an existing LR for def: ";
 194               printValue( Def ); cout  << endl;
 195             }
 196           }
 197
 198         } // if isDef()
 199
 200       } // for all opereands in machine instructions
 201
 202     } // for all machine instructions in the BB
 203
 204   } // for all BBs in method
 205
 206
 207   // Now we have to suggest clors for call and return arg live ranges.
 208   // Also, if there are implicit defs (e.g., retun value of a call inst)
 209   // they must be added to the live range list
 210
 211   suggestRegs4CallRets();
 212
 213   if( DEBUG_RA)
 214     cout << "Initial Live Ranges constructed!" << endl;
 215
 216 }
 217
 218
 219
 220 // Suggest colors for call and return args.
 221 // Also create new LRs for implicit defs
 222
 223 void LiveRangeInfo::suggestRegs4CallRets()
 224 {
 225
 226   CallRetInstrListType::const_iterator It =  CallRetInstrList.begin();
 227
 228   for( ; It !=  CallRetInstrList.end(); ++It ) {
 229
 230     const MachineInstr *MInst = *It;
 231     MachineOpCode OpCode =  MInst->getOpCode();
 232
 233     if( (TM.getInstrInfo()).isReturn(OpCode)  )
 234       MRI.suggestReg4RetValue( MInst, *this);
 235
 236     else if( (TM.getInstrInfo()).isCall( OpCode ) )
 237       MRI.suggestRegs4CallArgs( MInst, *this, RegClassList );
 238
 239     else
 240       assert( 0 && "Non call/ret instr in  CallRetInstrList" );
 241   }
 242
 243 }
 244
 245
 246
 247
 248 void LiveRangeInfo::coalesceLRs()
 249 {
 250
 251 /* Algorithm:
 252    for each BB in method
 253      for each machine instruction (inst)
 254        for each definition (def) in inst
 255          for each operand (op) of inst that is a use
 256            if the def and op are of the same register class
 257              if the def and op do not interfere //i.e., not simultaneously live
 258                if (degree(LR of def) + degree(LR of op)) <= # avail regs
 259                  if both LRs do not have suggested colors
 260                     merge2IGNodes(def, op) // i.e., merge 2 LRs
 261
 262 */
 263
 264   if( DEBUG_RA)
 265     cout << endl << "Coalscing LRs ..." << endl;
 266
 267   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 268
 269   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 270
 271     // get the iterator for machine instructions
 272     const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 273     MachineCodeForBasicBlock::const_iterator
 274       MInstIterator = MIVec.begin();
 275
 276     // iterate over all the machine instructions in BB
 277     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 278
 279       const MachineInstr * MInst = *MInstIterator;
 280
 281       if( DEBUG_RA > 1) {
 282         cout << " *Iterating over machine instr ";
 283         MInst->dump();
 284         cout << endl;
 285       }
 286
 287
 288       // iterate over  MI operands to find defs
 289       for(MachineInstr::val_op_const_iterator DefI(MInst);!DefI.done();++DefI){
 290
 291         if( DefI.isDef() ) {            // iff this operand is a def
 292
 293           LiveRange *const LROfDef = getLiveRangeForValue( *DefI );
 294           assert( LROfDef );
 295           RegClass *const RCOfDef = LROfDef->getRegClass();
 296
 297           MachineInstr::val_op_const_iterator UseI(MInst);
 298           for( ; !UseI.done(); ++UseI){ // for all uses
 299
 300             LiveRange *const LROfUse = getLiveRangeForValue( *UseI );
 301
 302             if( ! LROfUse ) {           // if LR of use is not found
 303
 304               //don't warn about labels
 305               if (!((*UseI)->getType())->isLabelType() && DEBUG_RA) {
 306                 cout<<" !! Warning: No LR for use "; printValue(*UseI);
 307                 cout << endl;
 308               }
 309               continue;                 // ignore and continue
 310             }
 311
 312             if( LROfUse == LROfDef)     // nothing to merge if they are same
 313               continue;
 314
 315             RegClass *const RCOfUse = LROfUse->getRegClass();
 316
 317             if( RCOfDef == RCOfUse ) {  // if the reg classes are the same
 318
 319               if( ! RCOfDef->getInterference(LROfDef, LROfUse) ) {
 320
 321                 unsigned CombinedDegree =
 322                   LROfDef->getUserIGNode()->getNumOfNeighbors() +
 323                   LROfUse->getUserIGNode()->getNumOfNeighbors();
 324
 325                 if( CombinedDegree <= RCOfDef->getNumOfAvailRegs() ) {
 326
 327                   // if both LRs do not have suggested colors
 328                   if( ! (LROfDef->hasSuggestedColor() &&
 329                          LROfUse->hasSuggestedColor() ) ) {
 330
 331                     RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
 332                     unionAndUpdateLRs(LROfDef, LROfUse);
 333                   }
 334
 335
 336                 } // if combined degree is less than # of regs
 337
 338               } // if def and use do not interfere
 339
 340             }// if reg classes are the same
 341
 342           } // for all uses
 343
 344         } // if def
 345
 346       } // for all defs
 347
 348     } // for all machine instructions
 349
 350   } // for all BBs
 351
 352   if( DEBUG_RA)
 353     cout << endl << "Coalscing Done!" << endl;
 354
 355 }
 356
 357
 358
 359
 360
 361 /*--------------------------- Debug code for printing ---------------*/
 362
 363
 364 void LiveRangeInfo::printLiveRanges()
 365 {
 366   LiveRangeMapType::iterator HMI = LiveRangeMap.begin();   // hash map iterator
 367   cout << endl << "Printing Live Ranges from Hash Map:" << endl;
 368   for( ; HMI != LiveRangeMap.end() ; HMI ++ ) {
 369     if( (*HMI).first && (*HMI).second ) {
 370       cout <<" "; printValue((*HMI).first);  cout  << "\t: ";
 371       ((*HMI).second)->printSet(); cout << endl;
 372     }
 373   }
 374 }
 375
 376