lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp

   1 #include "llvm/CodeGen/PhyRegAlloc.h"
   2
   3 cl::Enum<RegAllocDebugLevel_t> DEBUG_RA("dregalloc", cl::NoFlags,
   4   "enable register allocation debugging information",
   5   clEnumValN(RA_DEBUG_None   , "n", "disable debug output"),
   6   clEnumValN(RA_DEBUG_Normal , "y", "enable debug output"),
   7   clEnumValN(RA_DEBUG_Verbose, "v", "enable extra debug output"), 0);
   8
   9
  10 //----------------------------------------------------------------------------
  11 // Constructor: Init local composite objects and create register classes.
  12 //----------------------------------------------------------------------------
  13 PhyRegAlloc::PhyRegAlloc(const Method *const M,
  14                          const TargetMachine& tm,
  15                          MethodLiveVarInfo *const Lvi)
  16                         : RegClassList(),
  17                           Meth(M), TM(tm), LVI(Lvi), LRI(M, tm, RegClassList),
  18                           MRI( tm.getRegInfo() ),
  19                           NumOfRegClasses(MRI.getNumOfRegClasses()),
  20                           AddedInstrMap()
  21
  22 {
  23   // **TODO: use an actual reserved color list
  24   ReservedColorListType *RCL = new ReservedColorListType();
  25
  26   // create each RegisterClass and put in RegClassList
  27   for( unsigned int rc=0; rc < NumOfRegClasses; rc++)
  28     RegClassList.push_back( new RegClass(M, MRI.getMachineRegClass(rc), RCL) );
  29
  30 }
  31
  32 //----------------------------------------------------------------------------
  33 // This method initally creates interference graphs (one in each reg class)
  34 // and IGNodeList (one in each IG). The actual nodes will be pushed later.
  35 //----------------------------------------------------------------------------
  36
  37 void PhyRegAlloc::createIGNodeListsAndIGs()
  38 {
  39   if(DEBUG_RA ) cout << "Creating LR lists ..." << endl;
  40
  41   // hash map iterator
  42   LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
  43
  44   // hash map end
  45   LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
  46
  47     for(  ; HMI != HMIEnd ; ++HMI ) {
  48
  49       if( (*HMI).first ) {
  50
  51         LiveRange *L = (*HMI).second;      // get the LiveRange
  52
  53         if( !L) {
  54           if( DEBUG_RA) {
  55             cout << "\n*?!?Warning: Null liver range found for: ";
  56             printValue( (*HMI).first) ; cout << endl;
  57           }
  58           continue;
  59         }
  60                                         // if the Value * is not null, and LR
  61                                         // is not yet written to the IGNodeList
  62        if( !(L->getUserIGNode())  ) {
  63
  64          RegClass *const RC =           // RegClass of first value in the LR
  65            //RegClassList [MRI.getRegClassIDOfValue(*(L->begin()))];
  66            RegClassList[ L->getRegClass()->getID() ];
  67
  68          RC-> addLRToIG( L );           // add this LR to an IG
  69        }
  70     }
  71   }
  72
  73                                         // init RegClassList
  74   for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
  75     RegClassList[ rc ]->createInterferenceGraph();
  76
  77   if( DEBUG_RA)
  78     cout << "LRLists Created!" << endl;
  79 }
  80
  81
  82
  83 //----------------------------------------------------------------------------
  84 // This method will add all interferences at for a given instruction.
  85 // Interence occurs only if the LR of Def (Inst or Arg) is of the same reg
  86 // class as that of live var. The live var passed to this function is the
  87 // LVset AFTER the instruction
  88 //----------------------------------------------------------------------------
  89
  90 void PhyRegAlloc::addInterference(const Value *const Def,
  91                                   const LiveVarSet *const LVSet,
  92                                   const bool isCallInst) {
  93
  94   LiveVarSet::const_iterator LIt = LVSet->begin();
  95
  96   // get the live range of instruction
  97   const LiveRange *const LROfDef = LRI.getLiveRangeForValue( Def );
  98
  99   IGNode *const IGNodeOfDef = LROfDef->getUserIGNode();
 100   assert( IGNodeOfDef );
 101
 102   RegClass *const RCOfDef = LROfDef->getRegClass();
 103
 104   // for each live var in live variable set
 105   for( ; LIt != LVSet->end(); ++LIt) {
 106
 107     if( DEBUG_RA > 1) {
 108       cout << "< Def="; printValue(Def);
 109       cout << ", Lvar=";  printValue( *LIt); cout  << "> ";
 110     }
 111
 112     //  get the live range corresponding to live var
 113     LiveRange *const LROfVar = LRI.getLiveRangeForValue(*LIt );
 114
 115     // LROfVar can be null if it is a const since a const
 116     // doesn't have a dominating def - see Assumptions above
 117     if( LROfVar)   {
 118
 119       if(LROfDef == LROfVar)            // do not set interf for same LR
 120         continue;
 121
 122       // if 2 reg classes are the same set interference
 123       if( RCOfDef == LROfVar->getRegClass() ){
 124         RCOfDef->setInterference( LROfDef, LROfVar);
 125
 126       }
 127
 128       //the live range of this var interferes with this call
 129       if( isCallInst ) {
 130         LROfVar->addCallInterference( (const Instruction *const) Def );
 131         // cout << "\n ++Added Call Interf to set:";
 132         // LROfVar->printSet();
 133       }
 134     }
 135     else if(DEBUG_RA > 1)  {
 136       // we will not have LRs for values not explicitly allocated in the
 137       // instruction stream (e.g., constants)
 138       cout << " warning: no live range for " ;
 139       printValue( *LIt); cout << endl; }
 140
 141   }
 142
 143 }
 144
 145 //----------------------------------------------------------------------------
 146 // This method will walk thru code and create interferences in the IG of
 147 // each RegClass.
 148 //----------------------------------------------------------------------------
 149
 150 void PhyRegAlloc::buildInterferenceGraphs()
 151 {
 152
 153   if(DEBUG_RA) cout << "Creating interference graphs ..." << endl;
 154
 155   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 156
 157   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 158
 159     // get the iterator for machine instructions
 160     const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 161     MachineCodeForBasicBlock::const_iterator
 162       MInstIterator = MIVec.begin();
 163
 164     // iterate over all the machine instructions in BB
 165     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 166
 167       const MachineInstr *const MInst = *MInstIterator;
 168
 169       // get the LV set after the instruction
 170       const LiveVarSet *const LVSetAI =
 171         LVI->getLiveVarSetAfterMInst(MInst, *BBI);
 172
 173       const bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpCode());
 174
 175       // if( isCallInst) cout << "\n%%% Found call Inst:\n";
 176
 177       // iterate over  MI operands to find defs
 178       for( MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done(); ++OpI) {
 179
 180         if( OpI.isDef() ) {
 181           // create a new LR iff this operand is a def
 182           addInterference(*OpI, LVSetAI, isCallInst );
 183
 184         } //if this is a def
 185
 186       } // for all operands
 187
 188
 189       // Also add interference for any implicit definitions in a machine
 190       // instr (currently, only calls have this).
 191
 192       unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
 193       if(  NumOfImpRefs > 0 ) {
 194         for(unsigned z=0; z < NumOfImpRefs; z++)
 195           if( MInst->implicitRefIsDefined(z) )
 196             addInterference( MInst->getImplicitRef(z), LVSetAI, isCallInst );
 197       }
 198
 199     } // for all machine instructions in BB
 200
 201
 202 #if 0
 203
 204     // go thru LLVM instructions in the basic block and record all CALL
 205     // instructions and Return instructions in the CallInstrList
 206     // This is done because since there are no reverse pointers in machine
 207     // instructions to find the llvm instruction, when we encounter a call
 208     // or a return whose args must be specailly colored (e.g., %o's for args)
 209     BasicBlock::const_iterator InstIt = (*BBI)->begin();
 210
 211     for( ; InstIt != (*BBI)->end() ; ++ InstIt) {
 212       unsigned OpCode =  (*InstIt)->getOpcode();
 213
 214       if( OpCode == Instruction::Call )
 215         CallInstrList.push_back( *InstIt );
 216
 217       else if( OpCode == Instruction::Ret )
 218         RetInstrList.push_back( *InstIt );
 219     }
 220
 221 #endif
 222
 223
 224   } // for all BBs in method
 225
 226
 227   // add interferences for method arguments. Since there are no explict
 228   // defs in method for args, we have to add them manually
 229
 230   addInterferencesForArgs();            // add interference for method args
 231
 232   if( DEBUG_RA)
 233     cout << "Interference graphs calculted!" << endl;
 234
 235 }
 236
 237
 238
 239
 240 //----------------------------------------------------------------------------
 241 // This method will add interferences for incoming arguments to a method.
 242 //----------------------------------------------------------------------------
 243 void PhyRegAlloc::addInterferencesForArgs()
 244 {
 245                                               // get the InSet of root BB
 246   const LiveVarSet *const InSet = LVI->getInSetOfBB( Meth->front() );
 247
 248                                               // get the argument list
 249   const Method::ArgumentListType& ArgList = Meth->getArgumentList();
 250
 251                                               // get an iterator to arg list
 252   Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
 253
 254
 255   for( ; ArgIt != ArgList.end() ; ++ArgIt) {  // for each argument
 256     addInterference( *ArgIt, InSet, false );  // add interferences between
 257                                               // args and LVars at start
 258     if( DEBUG_RA > 1) {
 259       cout << " - %% adding interference for  argument ";
 260       printValue( (const Value *) *ArgIt); cout  << endl;
 261     }
 262   }
 263 }
 264
 265
 266
 267 //----------------------------------------------------------------------------
 268 // This method inserts caller saving/restoring instructons before/after
 269 // a call machine instruction.
 270 //----------------------------------------------------------------------------
 271
 272
 273 void PhyRegAlloc::insertCallerSavingCode(const MachineInstr *MInst,
 274                                          const BasicBlock *BB  )
 275 {
 276   assert( (TM.getInstrInfo()).isCall( MInst->getOpCode() ) );
 277
 278   int StackOff = 10;  // ****TODO : Change
 279   hash_set<unsigned> PushedRegSet;
 280
 281   // Now find the LR of the return value of the call
 282   // The last *implicit operand* is the return value of a call
 283   // Insert it to to he PushedRegSet since we must not save that register
 284   // and restore it after the call.
 285   // We do this because, we look at the LV set *after* the instruction
 286   // to determine, which LRs must be saved across calls. The return value
 287   // of the call is live in this set - but we must not save/restore it.
 288
 289   unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
 290   if(  NumOfImpRefs > 0 ) {
 291
 292     if(  MInst->implicitRefIsDefined(NumOfImpRefs-1) ) {
 293
 294       const Value *RetVal = MInst->getImplicitRef(NumOfImpRefs-1);
 295       LiveRange *RetValLR = LRI.getLiveRangeForValue( RetVal );
 296       assert( RetValLR && "No LR for RetValue of call");
 297
 298       PushedRegSet.insert(
 299         MRI.getUnifiedRegNum((RetValLR->getRegClass())->getID(),
 300                              RetValLR->getColor() ) );
 301     }
 302
 303   }
 304
 305
 306   const LiveVarSet *LVSetAft =  LVI->getLiveVarSetAfterMInst(MInst, BB);
 307
 308   LiveVarSet::const_iterator LIt = LVSetAft->begin();
 309
 310   // for each live var in live variable set after machine inst
 311   for( ; LIt != LVSetAft->end(); ++LIt) {
 312
 313    //  get the live range corresponding to live var
 314     LiveRange *const LR = LRI.getLiveRangeForValue(*LIt );
 315
 316     // LROfVar can be null if it is a const since a const
 317     // doesn't have a dominating def - see Assumptions above
 318     if( LR )   {
 319
 320       if( LR->hasColor() ) {
 321
 322         unsigned RCID = (LR->getRegClass())->getID();
 323         unsigned Color = LR->getColor();
 324
 325         if ( MRI.isRegVolatile(RCID, Color) ) {
 326
 327           // if the value is in both LV sets (i.e., live before and after
 328           // the call machine instruction)
 329
 330           unsigned Reg =   MRI.getUnifiedRegNum(RCID, Color);
 331
 332           if( PushedRegSet.find(Reg) == PushedRegSet.end() ) {
 333
 334             // if we haven't already pushed that register
 335
 336             unsigned RegType = MRI.getRegType( LR );
 337
 338             // Now get two instructions - to push on stack and pop from stack
 339             // and add them to InstrnsBefore and InstrnsAfter of the
 340             // call instruction
 341
 342             MachineInstr *AdIBef =
 343               MRI.cpReg2MemMI(Reg, MRI.getFramePointer(), StackOff, RegType );
 344
 345             MachineInstr *AdIAft =
 346               MRI.cpMem2RegMI(MRI.getFramePointer(), StackOff, Reg, RegType );
 347
 348             ((AddedInstrMap[MInst])->InstrnsBefore).push_front(AdIBef);
 349             ((AddedInstrMap[MInst])->InstrnsAfter).push_back(AdIAft);
 350
 351             PushedRegSet.insert( Reg );
 352             StackOff += 4; // ****TODO: Correct ??????
 353             cout << "\n $$$ Inserted caller saving instr";
 354
 355           } // if not already pushed
 356
 357         } // if LR has a volatile color
 358
 359       } // if LR has color
 360
 361     } // if there is a LR for Var
 362
 363   } // for each value in the LV set after instruction
 364
 365 }
 366
 367
 368 //----------------------------------------------------------------------------
 369 // This method is called after register allocation is complete to set the
 370 // allocated reisters in the machine code. This code will add register numbers
 371 // to MachineOperands that contain a Value.
 372 //----------------------------------------------------------------------------
 373
 374 void PhyRegAlloc::updateMachineCode()
 375 {
 376
 377   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 378
 379   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 380
 381     // get the iterator for machine instructions
 382     MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 383     MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
 384
 385     // iterate over all the machine instructions in BB
 386     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 387
 388       MachineInstr *MInst = *MInstIterator;
 389
 390       // if this machine instr is call, insert caller saving code
 391
 392       if( (TM.getInstrInfo()).isCall( MInst->getOpCode()) )
 393         insertCallerSavingCode(MInst,  *BBI );
 394
 395       // If there are instructions to be added, *before* this machine
 396       // instruction, add them now.
 397
 398       if( AddedInstrMap[ MInst ] ) {
 399
 400         deque<MachineInstr *> &IBef = (AddedInstrMap[MInst])->InstrnsBefore;
 401
 402         if( ! IBef.empty() ) {
 403
 404           deque<MachineInstr *>::iterator AdIt;
 405
 406           for( AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt ) {
 407
 408             cout << " *$* PREPENDed instr opcode: ";
 409             cout << TargetInstrDescriptors[(*AdIt)->getOpCode()].opCodeString;
 410             cout << endl;
 411
 412             MInstIterator = MIVec.insert( MInstIterator, *AdIt );
 413             ++MInstIterator;
 414           }
 415
 416         }
 417
 418       }
 419
 420
 421
 422       //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) {
 423
 424       for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 425
 426         MachineOperand& Op = MInst->getOperand(OpNum);
 427
 428         if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 429             Op.getOperandType() ==  MachineOperand::MO_CCRegister) {
 430
 431           const Value *const Val =  Op.getVRegValue();
 432
 433           // delete this condition checking later (must assert if Val is null)
 434           if( !Val) {
 435             if (DEBUG_RA)
 436               cout << "Warning: NULL Value found for operand" << endl;
 437             continue;
 438           }
 439           assert( Val && "Value is NULL");
 440
 441           const LiveRange *const LR = LRI.getLiveRangeForValue(Val);
 442
 443           if ( !LR ) {
 444
 445             // nothing to worry if it's a const or a label
 446
 447             if (DEBUG_RA) {
 448               cout << "*NO LR for inst opcode: ";
 449               cout << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
 450             }
 451
 452             // if register is not allocated, mark register as invalid
 453             if( Op.getAllocatedRegNum() == -1)
 454               Op.setRegForValue( MRI.getInvalidRegNum());
 455
 456 #if 0
 457             if(  ((Val->getType())->isLabelType()) ||
 458                  (Val->getValueType() == Value::ConstantVal)  )
 459               ;                         // do nothing
 460
 461             // The return address is not explicitly defined within a
 462             // method. So, it is not colored by usual algorithm. In that case
 463             // color it here.
 464
 465             //else if (TM.getInstrInfo().isCall(MInst->getOpCode()))
 466             //Op.setRegForValue( MRI.getCallAddressReg() );
 467
 468             //TM.getInstrInfo().isReturn(MInst->getOpCode())
 469             else if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ) {
 470               if (DEBUG_RA) cout << endl << "RETURN found" << endl;
 471               Op.setRegForValue( MRI.getReturnAddressReg() );
 472
 473             }
 474
 475             if (Val->getValueType() == Value::InstructionVal)
 476             {
 477               cout << "!Warning: No LiveRange for: ";
 478               printValue( Val); cout << " Type: " << Val->getValueType();
 479               cout << " RegVal=" <<  Op.getAllocatedRegNum() << endl;
 480             }
 481
 482 #endif
 483
 484             continue;
 485           }
 486
 487           unsigned RCID = (LR->getRegClass())->getID();
 488
 489           Op.setRegForValue( MRI.getUnifiedRegNum(RCID, LR->getColor()) );
 490
 491           int RegNum = MRI.getUnifiedRegNum(RCID, LR->getColor());
 492
 493         }
 494
 495       } // for each operand
 496
 497
 498       // If there are instructions to be added *after* this machine
 499       // instruction, add them now
 500
 501       if( AddedInstrMap[ MInst ] ) {
 502
 503         deque<MachineInstr *> &IAft = (AddedInstrMap[MInst])->InstrnsAfter;
 504
 505         if( ! IAft.empty() ) {
 506
 507           deque<MachineInstr *>::iterator AdIt;
 508
 509           ++MInstIterator;   // advance to the next instruction
 510
 511           for( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt ) {
 512
 513             cout << " *#* APPENDed instr opcode: ";
 514             cout << TargetInstrDescriptors[(*AdIt)->getOpCode()].opCodeString;
 515             cout << endl;
 516
 517             MInstIterator = MIVec.insert( MInstIterator, *AdIt );
 518             ++MInstIterator;
 519           }
 520
 521           // MInsterator already points to the next instr. Since the
 522           // for loop also increments it, decrement it to point to the
 523           // instruction added last
 524           --MInstIterator;
 525
 526         }
 527
 528       }
 529
 530     } // for each machine instruction
 531   }
 532 }
 533
 534
 535
 536
 537 //----------------------------------------------------------------------------
 538 // This method prints the code with registers after register allocation is
 539 // complete.
 540 //----------------------------------------------------------------------------
 541 void PhyRegAlloc::printMachineCode()
 542 {
 543
 544   cout << endl << ";************** Method ";
 545   cout << Meth->getName() << " *****************" << endl;
 546
 547   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 548
 549   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 550
 551     cout << endl ; printLabel( *BBI); cout << ": ";
 552
 553     // get the iterator for machine instructions
 554     MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 555     MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
 556
 557     // iterate over all the machine instructions in BB
 558     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 559
 560       MachineInstr *const MInst = *MInstIterator;
 561
 562
 563       cout << endl << "\t";
 564       cout << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
 565
 566
 567       //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) {
 568
 569       for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 570
 571         MachineOperand& Op = MInst->getOperand(OpNum);
 572
 573         if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 574             Op.getOperandType() ==  MachineOperand::MO_CCRegister ||
 575             Op.getOperandType() ==  MachineOperand::MO_PCRelativeDisp ) {
 576
 577           const Value *const Val = Op.getVRegValue () ;
 578           // ****this code is temporary till NULL Values are fixed
 579           if( ! Val ) {
 580             cout << "\t<*NULL*>";
 581             continue;
 582           }
 583
 584           // if a label or a constant
 585           if( (Val->getValueType() == Value::BasicBlockVal)  ) {
 586
 587             cout << "\t"; printLabel(   Op.getVRegValue () );
 588           }
 589           else {
 590             // else it must be a register value
 591             const int RegNum = Op.getAllocatedRegNum();
 592
 593             //if( RegNum != 1000)
 594
 595               cout << "\t" << "%" << MRI.getUnifiedRegName( RegNum );
 596             // else cout << "\t<*NoReg*>";
 597
 598           }
 599
 600         }
 601         else if(Op.getOperandType() ==  MachineOperand::MO_MachineRegister) {
 602           cout << "\t" << "%" << MRI.getUnifiedRegName(Op.getMachineRegNum());
 603         }
 604
 605         else
 606           cout << "\t" << Op;      // use dump field
 607       }
 608
 609
 610
 611       unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
 612       if(  NumOfImpRefs > 0 ) {
 613
 614         cout << "\tImplicit:";
 615
 616         for(unsigned z=0; z < NumOfImpRefs; z++) {
 617           printValue(  MInst->getImplicitRef(z) );
 618           cout << "\t";
 619         }
 620
 621       }
 622
 623     } // for all machine instructions
 624
 625
 626     cout << endl;
 627
 628   } // for all BBs
 629
 630   cout << endl;
 631 }
 632
 633
 634 //----------------------------------------------------------------------------
 635 //
 636 //----------------------------------------------------------------------------
 637
 638 void PhyRegAlloc::colorCallRetArgs()
 639 {
 640
 641   CallRetInstrListType &CallRetInstList = LRI.getCallRetInstrList();
 642   CallRetInstrListType::const_iterator It = CallRetInstList.begin();
 643
 644   for( ; It != CallRetInstList.end(); ++It ) {
 645
 646     const MachineInstr *const CRMI = *It;
 647     unsigned OpCode =  CRMI->getOpCode();
 648
 649     // get the added instructions for this Call/Ret instruciton
 650     AddedInstrns *AI = AddedInstrMap[ CRMI ];
 651     if ( !AI ) {
 652       AI = new AddedInstrns();
 653       AddedInstrMap[ CRMI ] = AI;
 654     }
 655
 656     if( (TM.getInstrInfo()).isCall( OpCode ) )
 657       MRI.colorCallArgs( CRMI, LRI, AI );
 658
 659     else if (  (TM.getInstrInfo()).isReturn(OpCode) )
 660       MRI.colorRetValue( CRMI, LRI, AI );
 661
 662     else assert( 0 && "Non Call/Ret instrn in CallRetInstrList\n" );
 663
 664   }
 665
 666 }
 667
 668 //----------------------------------------------------------------------------
 669
 670 //----------------------------------------------------------------------------
 671 void PhyRegAlloc::colorIncomingArgs()
 672 {
 673   const BasicBlock *const FirstBB = Meth->front();
 674   const MachineInstr *FirstMI = *((FirstBB->getMachineInstrVec()).begin());
 675   assert( FirstMI && "No machine instruction in entry BB");
 676
 677   AddedInstrns *AI = AddedInstrMap[ FirstMI ];
 678   if ( !AI ) {
 679     AI = new AddedInstrns();
 680     AddedInstrMap[ FirstMI  ] = AI;
 681   }
 682
 683   MRI.colorMethodArgs(Meth, LRI, AI );
 684 }
 685
 686
 687 //----------------------------------------------------------------------------
 688 // Used to generate a label for a basic block
 689 //----------------------------------------------------------------------------
 690 void PhyRegAlloc::printLabel(const Value *const Val)
 691 {
 692   if( Val->hasName() )
 693     cout  << Val->getName();
 694   else
 695     cout << "Label" <<  Val;
 696 }
 697
 698
 699 //----------------------------------------------------------------------------
 700 // The entry pont to Register Allocation
 701 //----------------------------------------------------------------------------
 702
 703 void PhyRegAlloc::allocateRegisters()
 704 {
 705
 706   // make sure that we put all register classes into the RegClassList
 707   // before we call constructLiveRanges (now done in the constructor of
 708   // PhyRegAlloc class).
 709
 710   constructLiveRanges();                // create LR info
 711
 712   if( DEBUG_RA )
 713     LRI.printLiveRanges();
 714
 715   createIGNodeListsAndIGs();            // create IGNode list and IGs
 716
 717   buildInterferenceGraphs();            // build IGs in all reg classes
 718
 719
 720   if( DEBUG_RA ) {
 721     // print all LRs in all reg classes
 722     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)
 723       RegClassList[ rc ]->printIGNodeList();
 724
 725     // print IGs in all register classes
 726     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 727       RegClassList[ rc ]->printIG();
 728   }
 729
 730   LRI.coalesceLRs();                    // coalesce all live ranges
 731
 732   if( DEBUG_RA) {
 733     // print all LRs in all reg classes
 734     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)
 735       RegClassList[ rc ]->printIGNodeList();
 736
 737     // print IGs in all register classes
 738     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 739       RegClassList[ rc ]->printIG();
 740   }
 741
 742   // color all register classes
 743   for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 744     RegClassList[ rc ]->colorAllRegs();
 745
 746
 747   // color incoming args and call args
 748   colorIncomingArgs();
 749   colorCallRetArgs();
 750
 751
 752   updateMachineCode();
 753   if (DEBUG_RA) {
 754     // PrintMachineInstructions(Meth);
 755     printMachineCode();                   // only for DEBUGGING
 756   }
 757 }
 758
 759
 760
 761