lib/Target/SparcV9/RegAlloc/LiveRangeInfo.cpp

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