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     else if(DEBUG_RA > 1)  {
 129       // we will not have LRs for values not explicitly allocated in the
 130       // instruction stream (e.g., constants)
 131       cout << " warning: no live range for " ;
 132       printValue( *LIt); cout << endl; }
 133
 134     }
 135
 136   }
 137
 138 }
 139
 140
 141 //----------------------------------------------------------------------------
 142 // For a call instruction, this method sets the CallInterference flag in
 143 // the LR of each variable live int the Live Variable Set live after the
 144 // call instruction (except the return value of the call instruction - since
 145 // the return value does not interfere with that call itself).
 146 //----------------------------------------------------------------------------
 147
 148 void PhyRegAlloc::setCallInterferences(const MachineInstr *MInst,
 149                                        const LiveVarSet *const LVSetAft )
 150 {
 151   // Now find the LR of the return value of the call
 152   // The last *implicit operand* is the return value of a call
 153
 154   // We do this because, we look at the LV set *after* the instruction
 155   // to determine, which LRs must be saved across calls. The return value
 156   // of the call is live in this set - but it does not interfere with call
 157   // (i.e., we can allocate a volatile register to the return value)
 158
 159   LiveRange *RetValLR = NULL;
 160
 161   unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
 162   if(  NumOfImpRefs > 0 ) {
 163
 164     if(  MInst->implicitRefIsDefined(NumOfImpRefs-1) ) {
 165
 166       const Value *RetVal = MInst->getImplicitRef(NumOfImpRefs-1);
 167       RetValLR = LRI.getLiveRangeForValue( RetVal );
 168       assert( RetValLR && "No LR for RetValue of call");
 169     }
 170
 171   }
 172
 173
 174   if( DEBUG_RA)
 175     cout << "\n For call inst: " << *MInst;
 176
 177   LiveVarSet::const_iterator LIt = LVSetAft->begin();
 178
 179   // for each live var in live variable set after machine inst
 180   for( ; LIt != LVSetAft->end(); ++LIt) {
 181
 182    //  get the live range corresponding to live var
 183     LiveRange *const LR = LRI.getLiveRangeForValue(*LIt );
 184
 185     if( LR && DEBUG_RA) {
 186       cout << "\n\tLR Aft Call: ";
 187       LR->printSet();
 188     }
 189
 190
 191     // LR can be null if it is a const since a const
 192     // doesn't have a dominating def - see Assumptions above
 193     if( LR && (LR != RetValLR) )   {
 194       LR->setCallInterference();
 195       if( DEBUG_RA) {
 196         cout << "\n  ++Added call interf for LR: " ;
 197         LR->printSet();
 198       }
 199     }
 200
 201   }
 202
 203 }
 204
 205
 206 //----------------------------------------------------------------------------
 207 // This method will walk thru code and create interferences in the IG of
 208 // each RegClass.
 209 //----------------------------------------------------------------------------
 210
 211 void PhyRegAlloc::buildInterferenceGraphs()
 212 {
 213
 214   if(DEBUG_RA) cout << "Creating interference graphs ..." << endl;
 215
 216   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 217
 218   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 219
 220     // get the iterator for machine instructions
 221     const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 222     MachineCodeForBasicBlock::const_iterator
 223       MInstIterator = MIVec.begin();
 224
 225     // iterate over all the machine instructions in BB
 226     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 227
 228       const MachineInstr *const MInst = *MInstIterator;
 229
 230       // get the LV set after the instruction
 231       const LiveVarSet *const LVSetAI =
 232         LVI->getLiveVarSetAfterMInst(MInst, *BBI);
 233
 234       const bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpCode());
 235
 236       if( isCallInst ) {
 237         //cout << "\nFor call inst: " << *MInst;
 238
 239         // set the isCallInterference flag of each live range wich extends
 240         // accross this call instruction. This information is used by graph
 241         // coloring algo to avoid allocating volatile colors to live ranges
 242         // that span across calls (since they have to be saved/restored)
 243         setCallInterferences( MInst,  LVSetAI);
 244       }
 245
 246
 247       // iterate over  MI operands to find defs
 248       for( MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done(); ++OpI) {
 249
 250         if( OpI.isDef() ) {
 251           // create a new LR iff this operand is a def
 252           addInterference(*OpI, LVSetAI, isCallInst );
 253
 254         } //if this is a def
 255
 256       } // for all operands
 257
 258
 259       // Also add interference for any implicit definitions in a machine
 260       // instr (currently, only calls have this).
 261
 262       unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
 263       if(  NumOfImpRefs > 0 ) {
 264         for(unsigned z=0; z < NumOfImpRefs; z++)
 265           if( MInst->implicitRefIsDefined(z) )
 266             addInterference( MInst->getImplicitRef(z), LVSetAI, isCallInst );
 267       }
 268
 269     } // for all machine instructions in BB
 270
 271
 272 #if 0
 273
 274     // go thru LLVM instructions in the basic block and record all CALL
 275     // instructions and Return instructions in the CallInstrList
 276     // This is done because since there are no reverse pointers in machine
 277     // instructions to find the llvm instruction, when we encounter a call
 278     // or a return whose args must be specailly colored (e.g., %o's for args)
 279     BasicBlock::const_iterator InstIt = (*BBI)->begin();
 280
 281     for( ; InstIt != (*BBI)->end() ; ++ InstIt) {
 282       unsigned OpCode =  (*InstIt)->getOpcode();
 283
 284       if( OpCode == Instruction::Call )
 285         CallInstrList.push_back( *InstIt );
 286
 287       else if( OpCode == Instruction::Ret )
 288         RetInstrList.push_back( *InstIt );
 289     }
 290
 291 #endif
 292
 293
 294   } // for all BBs in method
 295
 296
 297   // add interferences for method arguments. Since there are no explict
 298   // defs in method for args, we have to add them manually
 299
 300   addInterferencesForArgs();            // add interference for method args
 301
 302   if( DEBUG_RA)
 303     cout << "Interference graphs calculted!" << endl;
 304
 305 }
 306
 307
 308
 309
 310 //----------------------------------------------------------------------------
 311 // This method will add interferences for incoming arguments to a method.
 312 //----------------------------------------------------------------------------
 313 void PhyRegAlloc::addInterferencesForArgs()
 314 {
 315                                               // get the InSet of root BB
 316   const LiveVarSet *const InSet = LVI->getInSetOfBB( Meth->front() );
 317
 318                                               // get the argument list
 319   const Method::ArgumentListType& ArgList = Meth->getArgumentList();
 320
 321                                               // get an iterator to arg list
 322   Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
 323
 324
 325   for( ; ArgIt != ArgList.end() ; ++ArgIt) {  // for each argument
 326     addInterference( *ArgIt, InSet, false );  // add interferences between
 327                                               // args and LVars at start
 328     if( DEBUG_RA > 1) {
 329        cout << " - %% adding interference for  argument ";
 330       printValue( (const Value *) *ArgIt); cout  << endl;
 331     }
 332   }
 333 }
 334
 335
 336
 337 //----------------------------------------------------------------------------
 338 // This method inserts caller saving/restoring instructons before/after
 339 // a call machine instruction.
 340 //----------------------------------------------------------------------------
 341
 342
 343 void PhyRegAlloc::insertCallerSavingCode(const MachineInstr *MInst,
 344                                          const BasicBlock *BB  )
 345 {
 346   // assert( (TM.getInstrInfo()).isCall( MInst->getOpCode() ) );
 347
 348   int StackOff = -8;  // ****TODO : Change
 349   hash_set<unsigned> PushedRegSet;
 350
 351   // Now find the LR of the return value of the call
 352   // The last *implicit operand* is the return value of a call
 353   // Insert it to to he PushedRegSet since we must not save that register
 354   // and restore it after the call.
 355   // We do this because, we look at the LV set *after* the instruction
 356   // to determine, which LRs must be saved across calls. The return value
 357   // of the call is live in this set - but we must not save/restore it.
 358
 359   unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
 360   if(  NumOfImpRefs > 0 ) {
 361
 362     if(  MInst->implicitRefIsDefined(NumOfImpRefs-1) ) {
 363
 364       const Value *RetVal = MInst->getImplicitRef(NumOfImpRefs-1);
 365       LiveRange *RetValLR = LRI.getLiveRangeForValue( RetVal );
 366       assert( RetValLR && "No LR for RetValue of call");
 367
 368       PushedRegSet.insert(
 369         MRI.getUnifiedRegNum((RetValLR->getRegClass())->getID(),
 370                              RetValLR->getColor() ) );
 371     }
 372
 373   }
 374
 375
 376   const LiveVarSet *LVSetAft =  LVI->getLiveVarSetAfterMInst(MInst, BB);
 377
 378   LiveVarSet::const_iterator LIt = LVSetAft->begin();
 379
 380   // for each live var in live variable set after machine inst
 381   for( ; LIt != LVSetAft->end(); ++LIt) {
 382
 383    //  get the live range corresponding to live var
 384     LiveRange *const LR = LRI.getLiveRangeForValue(*LIt );
 385
 386     // LR can be null if it is a const since a const
 387     // doesn't have a dominating def - see Assumptions above
 388     if( LR )   {
 389
 390       if( LR->hasColor() ) {
 391
 392         unsigned RCID = (LR->getRegClass())->getID();
 393         unsigned Color = LR->getColor();
 394
 395         if ( MRI.isRegVolatile(RCID, Color) ) {
 396
 397           // if the value is in both LV sets (i.e., live before and after
 398           // the call machine instruction)
 399
 400           unsigned Reg =   MRI.getUnifiedRegNum(RCID, Color);
 401
 402           if( PushedRegSet.find(Reg) == PushedRegSet.end() ) {
 403
 404             // if we haven't already pushed that register
 405
 406             unsigned RegType = MRI.getRegType( LR );
 407
 408             // Now get two instructions - to push on stack and pop from stack
 409             // and add them to InstrnsBefore and InstrnsAfter of the
 410             // call instruction
 411
 412             MachineInstr *AdIBef =
 413               MRI.cpReg2MemMI(Reg, MRI.getFramePointer(), StackOff, RegType );
 414
 415             MachineInstr *AdIAft =
 416               MRI.cpMem2RegMI(MRI.getFramePointer(), StackOff, Reg, RegType );
 417
 418             ((AddedInstrMap[MInst])->InstrnsBefore).push_front(AdIBef);
 419             ((AddedInstrMap[MInst])->InstrnsAfter).push_back(AdIAft);
 420
 421             PushedRegSet.insert( Reg );
 422             StackOff -= 8; // ****TODO: Correct ??????
 423
 424             if(DEBUG_RA) {
 425               cerr << "\nFor callee save call inst:" << *MInst;
 426               cerr << "\n  -inserted caller saving instrs:\n\t ";
 427               cerr << *AdIBef << "\n\t" << *AdIAft  ;
 428             }
 429           } // if not already pushed
 430
 431         } // if LR has a volatile color
 432
 433       } // if LR has color
 434
 435     } // if there is a LR for Var
 436
 437   } // for each value in the LV set after instruction
 438
 439 }
 440
 441
 442 //----------------------------------------------------------------------------
 443 // This method is called after register allocation is complete to set the
 444 // allocated reisters in the machine code. This code will add register numbers
 445 // to MachineOperands that contain a Value.
 446 //----------------------------------------------------------------------------
 447
 448 void PhyRegAlloc::updateMachineCode()
 449 {
 450
 451   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 452
 453   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 454
 455     // get the iterator for machine instructions
 456     MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 457     MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
 458
 459     // iterate over all the machine instructions in BB
 460     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 461
 462       MachineInstr *MInst = *MInstIterator;
 463
 464       // if this machine instr is call, insert caller saving code
 465
 466       if( (TM.getInstrInfo()).isCall( MInst->getOpCode()) )
 467         insertCallerSavingCode(MInst,  *BBI );
 468
 469       // If there are instructions to be added, *before* this machine
 470       // instruction, add them now.
 471
 472       if( AddedInstrMap[ MInst ] ) {
 473
 474         deque<MachineInstr *> &IBef = (AddedInstrMap[MInst])->InstrnsBefore;
 475
 476         if( ! IBef.empty() ) {
 477
 478           deque<MachineInstr *>::iterator AdIt;
 479
 480           for( AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt ) {
 481
 482             if( DEBUG_RA)
 483               cerr << " *$* PREPENDed instr " << *AdIt << endl;
 484
 485             MInstIterator = MIVec.insert( MInstIterator, *AdIt );
 486             ++MInstIterator;
 487           }
 488
 489         }
 490
 491       }
 492
 493
 494
 495       //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) {
 496
 497       for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 498
 499         MachineOperand& Op = MInst->getOperand(OpNum);
 500
 501         if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 502             Op.getOperandType() ==  MachineOperand::MO_CCRegister) {
 503
 504           const Value *const Val =  Op.getVRegValue();
 505
 506           // delete this condition checking later (must assert if Val is null)
 507           if( !Val) {
 508             if (DEBUG_RA)
 509               cout << "Warning: NULL Value found for operand" << endl;
 510             continue;
 511           }
 512           assert( Val && "Value is NULL");
 513
 514           const LiveRange *const LR = LRI.getLiveRangeForValue(Val);
 515
 516           if ( !LR ) {
 517
 518             // nothing to worry if it's a const or a label
 519
 520             if (DEBUG_RA) {
 521               cout << "*NO LR for operand : " << Op ;
 522               cout << " [reg:" <<  Op.getAllocatedRegNum() << "]";
 523               cout << " in inst:\t" << *MInst << endl;
 524             }
 525
 526             // if register is not allocated, mark register as invalid
 527             if( Op.getAllocatedRegNum() == -1)
 528               Op.setRegForValue( MRI.getInvalidRegNum());
 529
 530 #if 0
 531             if(  ((Val->getType())->isLabelType()) ||
 532                  (Val->getValueType() == Value::ConstantVal)  )
 533               ;                         // do nothing
 534
 535             // The return address is not explicitly defined within a
 536             // method. So, it is not colored by usual algorithm. In that case
 537             // color it here.
 538
 539             //else if (TM.getInstrInfo().isCall(MInst->getOpCode()))
 540             //Op.setRegForValue( MRI.getCallAddressReg() );
 541
 542             //TM.getInstrInfo().isReturn(MInst->getOpCode())
 543             else if(TM.getInstrInfo().isReturn(MInst->getOpCode()) ) {
 544               if (DEBUG_RA) cout << endl << "RETURN found" << endl;
 545               Op.setRegForValue( MRI.getReturnAddressReg() );
 546
 547             }
 548
 549             if (Val->getValueType() == Value::InstructionVal)
 550             {
 551               if( DEBUG_RA ) {
 552                 cout << "!Warning: No LiveRange for: ";
 553                 printValue( Val); cout << " Type: " << Val->getValueType();
 554                 cout << " RegVal=" <<  Op.getAllocatedRegNum() << endl;
 555               }
 556             }
 557
 558 #endif
 559
 560             continue;
 561           }
 562
 563           unsigned RCID = (LR->getRegClass())->getID();
 564
 565           Op.setRegForValue( MRI.getUnifiedRegNum(RCID, LR->getColor()) );
 566
 567           int RegNum = MRI.getUnifiedRegNum(RCID, LR->getColor());
 568
 569         }
 570
 571       } // for each operand
 572
 573
 574       // If there are instructions to be added *after* this machine
 575       // instruction, add them now
 576
 577       if( AddedInstrMap[ MInst ] ) {
 578
 579         deque<MachineInstr *> &IAft = (AddedInstrMap[MInst])->InstrnsAfter;
 580
 581         if( ! IAft.empty() ) {
 582
 583           deque<MachineInstr *>::iterator AdIt;
 584
 585           ++MInstIterator;   // advance to the next instruction
 586
 587           for( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt ) {
 588
 589             if(DEBUG_RA)
 590               cerr << " *#* APPENDed instr opcode: "  << *AdIt << endl;
 591
 592             MInstIterator = MIVec.insert( MInstIterator, *AdIt );
 593             ++MInstIterator;
 594           }
 595
 596           // MInsterator already points to the next instr. Since the
 597           // for loop also increments it, decrement it to point to the
 598           // instruction added last
 599           --MInstIterator;
 600
 601         }
 602
 603       }
 604
 605     } // for each machine instruction
 606   }
 607 }
 608
 609
 610
 611
 612 //----------------------------------------------------------------------------
 613 // This method prints the code with registers after register allocation is
 614 // complete.
 615 //----------------------------------------------------------------------------
 616 void PhyRegAlloc::printMachineCode()
 617 {
 618
 619   cout << endl << ";************** Method ";
 620   cout << Meth->getName() << " *****************" << endl;
 621
 622   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 623
 624   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 625
 626     cout << endl ; printLabel( *BBI); cout << ": ";
 627
 628     // get the iterator for machine instructions
 629     MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 630     MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
 631
 632     // iterate over all the machine instructions in BB
 633     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 634
 635       MachineInstr *const MInst = *MInstIterator;
 636
 637
 638       cout << endl << "\t";
 639       cout << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
 640
 641
 642       //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) {
 643
 644       for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 645
 646         MachineOperand& Op = MInst->getOperand(OpNum);
 647
 648         if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 649             Op.getOperandType() ==  MachineOperand::MO_CCRegister /*||
 650             Op.getOperandType() ==  MachineOperand::MO_PCRelativeDisp*/ ) {
 651
 652           const Value *const Val = Op.getVRegValue () ;
 653           // ****this code is temporary till NULL Values are fixed
 654           if( ! Val ) {
 655             cout << "\t<*NULL*>";
 656             continue;
 657           }
 658
 659           // if a label or a constant
 660           if( (Val->getValueType() == Value::BasicBlockVal)  ) {
 661
 662             cout << "\t"; printLabel(   Op.getVRegValue () );
 663           }
 664           else {
 665             // else it must be a register value
 666             const int RegNum = Op.getAllocatedRegNum();
 667
 668             //if( RegNum != 1000)
 669
 670               cout << "\t" << "%" << MRI.getUnifiedRegName( RegNum );
 671             // else cout << "\t<*NoReg*>";
 672
 673           }
 674
 675         }
 676         else if(Op.getOperandType() ==  MachineOperand::MO_MachineRegister) {
 677           cout << "\t" << "%" << MRI.getUnifiedRegName(Op.getMachineRegNum());
 678         }
 679
 680         else
 681           cout << "\t" << Op;      // use dump field
 682       }
 683
 684
 685
 686       unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
 687       if(  NumOfImpRefs > 0 ) {
 688
 689         cout << "\tImplicit:";
 690
 691         for(unsigned z=0; z < NumOfImpRefs; z++) {
 692           printValue(  MInst->getImplicitRef(z) );
 693           cout << "\t";
 694         }
 695
 696       }
 697
 698     } // for all machine instructions
 699
 700
 701     cout << endl;
 702
 703   } // for all BBs
 704
 705   cout << endl;
 706 }
 707
 708
 709 //----------------------------------------------------------------------------
 710 //
 711 //----------------------------------------------------------------------------
 712
 713 void PhyRegAlloc::colorCallRetArgs()
 714 {
 715
 716   CallRetInstrListType &CallRetInstList = LRI.getCallRetInstrList();
 717   CallRetInstrListType::const_iterator It = CallRetInstList.begin();
 718
 719   for( ; It != CallRetInstList.end(); ++It ) {
 720
 721     const MachineInstr *const CRMI = *It;
 722     unsigned OpCode =  CRMI->getOpCode();
 723
 724     // get the added instructions for this Call/Ret instruciton
 725     AddedInstrns *AI = AddedInstrMap[ CRMI ];
 726     if ( !AI ) {
 727       AI = new AddedInstrns();
 728       AddedInstrMap[ CRMI ] = AI;
 729     }
 730
 731     if( (TM.getInstrInfo()).isCall( OpCode ) )
 732       MRI.colorCallArgs( CRMI, LRI, AI );
 733
 734     else if (  (TM.getInstrInfo()).isReturn(OpCode) )
 735       MRI.colorRetValue( CRMI, LRI, AI );
 736
 737     else assert( 0 && "Non Call/Ret instrn in CallRetInstrList\n" );
 738
 739   }
 740
 741 }
 742
 743 //----------------------------------------------------------------------------
 744
 745 //----------------------------------------------------------------------------
 746 void PhyRegAlloc::colorIncomingArgs()
 747 {
 748   const BasicBlock *const FirstBB = Meth->front();
 749   const MachineInstr *FirstMI = *((FirstBB->getMachineInstrVec()).begin());
 750   assert( FirstMI && "No machine instruction in entry BB");
 751
 752   AddedInstrns *AI = AddedInstrMap[ FirstMI ];
 753   if ( !AI ) {
 754     AI = new AddedInstrns();
 755     AddedInstrMap[ FirstMI  ] = AI;
 756   }
 757
 758   MRI.colorMethodArgs(Meth, LRI, AI );
 759 }
 760
 761
 762 //----------------------------------------------------------------------------
 763 // Used to generate a label for a basic block
 764 //----------------------------------------------------------------------------
 765 void PhyRegAlloc::printLabel(const Value *const Val)
 766 {
 767   if( Val->hasName() )
 768     cout  << Val->getName();
 769   else
 770     cout << "Label" <<  Val;
 771 }
 772
 773
 774 //----------------------------------------------------------------------------
 775 // The entry pont to Register Allocation
 776 //----------------------------------------------------------------------------
 777
 778 void PhyRegAlloc::allocateRegisters()
 779 {
 780
 781   // make sure that we put all register classes into the RegClassList
 782   // before we call constructLiveRanges (now done in the constructor of
 783   // PhyRegAlloc class).
 784
 785   constructLiveRanges();                // create LR info
 786
 787   if( DEBUG_RA )
 788     LRI.printLiveRanges();
 789
 790   createIGNodeListsAndIGs();            // create IGNode list and IGs
 791
 792   buildInterferenceGraphs();            // build IGs in all reg classes
 793
 794
 795   if( DEBUG_RA ) {
 796     // print all LRs in all reg classes
 797     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)
 798       RegClassList[ rc ]->printIGNodeList();
 799
 800     // print IGs in all register classes
 801     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 802       RegClassList[ rc ]->printIG();
 803   }
 804
 805   LRI.coalesceLRs();                    // coalesce all live ranges
 806
 807   if( DEBUG_RA) {
 808     // print all LRs in all reg classes
 809     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)
 810       RegClassList[ rc ]->printIGNodeList();
 811
 812     // print IGs in all register classes
 813     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 814       RegClassList[ rc ]->printIG();
 815   }
 816
 817   // color all register classes
 818   for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 819     RegClassList[ rc ]->colorAllRegs();
 820
 821
 822   // color incoming args and call args
 823   colorIncomingArgs();
 824   colorCallRetArgs();
 825
 826
 827   updateMachineCode();
 828   if (DEBUG_RA) {
 829     PrintMachineInstructions(Meth);
 830     printMachineCode();                   // only for DEBUGGING
 831   }
 832 }
 833
 834
 835
 836