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