lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp

   1 // $Id$
   2 //***************************************************************************
   3 // File:
   4 //      PhyRegAlloc.cpp
   5 //
   6 // Purpose:
   7 //      Register allocation for LLVM.
   8 //
   9 // History:
  10 //      9/10/01  -  Ruchira Sasanka - created.
  11 //**************************************************************************/
  12
  13 #include "llvm/CodeGen/PhyRegAlloc.h"
  14 #include "llvm/CodeGen/MachineInstr.h"
  15 #include "llvm/Target/TargetMachine.h"
  16 #include "llvm/Target/MachineFrameInfo.h"
  17
  18
  19 // ***TODO: There are several places we add instructions. Validate the order
  20 //          of adding these instructions.
  21
  22
  23
  24 cl::Enum<RegAllocDebugLevel_t> DEBUG_RA("dregalloc", cl::NoFlags,
  25   "enable register allocation debugging information",
  26   clEnumValN(RA_DEBUG_None   , "n", "disable debug output"),
  27   clEnumValN(RA_DEBUG_Normal , "y", "enable debug output"),
  28   clEnumValN(RA_DEBUG_Verbose, "v", "enable extra debug output"), 0);
  29
  30
  31 //----------------------------------------------------------------------------
  32 // Constructor: Init local composite objects and create register classes.
  33 //----------------------------------------------------------------------------
  34 PhyRegAlloc::PhyRegAlloc(Method *M,
  35                          const TargetMachine& tm,
  36                          MethodLiveVarInfo *const Lvi)
  37                         : RegClassList(),
  38                           TM(tm),
  39                           Meth(M),
  40                           mcInfo(MachineCodeForMethod::get(M)),
  41                           LVI(Lvi), LRI(M, tm, RegClassList),
  42                           MRI( tm.getRegInfo() ),
  43                           NumOfRegClasses(MRI.getNumOfRegClasses()),
  44                           AddedInstrMap()
  45                           /*, PhiInstList()*/
  46 {
  47   // **TODO: use an actual reserved color list
  48   ReservedColorListType *RCL = new ReservedColorListType();
  49
  50   // create each RegisterClass and put in RegClassList
  51   for( unsigned int rc=0; rc < NumOfRegClasses; rc++)
  52     RegClassList.push_back( new RegClass(M, MRI.getMachineRegClass(rc), RCL) );
  53 }
  54
  55 //----------------------------------------------------------------------------
  56 // This method initally creates interference graphs (one in each reg class)
  57 // and IGNodeList (one in each IG). The actual nodes will be pushed later.
  58 //----------------------------------------------------------------------------
  59
  60 void PhyRegAlloc::createIGNodeListsAndIGs()
  61 {
  62   if(DEBUG_RA ) cout << "Creating LR lists ..." << endl;
  63
  64   // hash map iterator
  65   LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
  66
  67   // hash map end
  68   LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
  69
  70     for(  ; HMI != HMIEnd ; ++HMI ) {
  71
  72       if( (*HMI).first ) {
  73
  74         LiveRange *L = (*HMI).second;      // get the LiveRange
  75
  76         if( !L) {
  77           if( DEBUG_RA) {
  78             cout << "\n*?!?Warning: Null liver range found for: ";
  79             printValue( (*HMI).first) ; cout << endl;
  80           }
  81           continue;
  82         }
  83                                         // if the Value * is not null, and LR
  84                                         // is not yet written to the IGNodeList
  85        if( !(L->getUserIGNode())  ) {
  86
  87          RegClass *const RC =           // RegClass of first value in the LR
  88            //RegClassList [MRI.getRegClassIDOfValue(*(L->begin()))];
  89            RegClassList[ L->getRegClass()->getID() ];
  90
  91          RC-> addLRToIG( L );           // add this LR to an IG
  92        }
  93     }
  94   }
  95
  96                                         // init RegClassList
  97   for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
  98     RegClassList[ rc ]->createInterferenceGraph();
  99
 100   if( DEBUG_RA)
 101     cout << "LRLists Created!" << endl;
 102 }
 103
 104
 105
 106 //----------------------------------------------------------------------------
 107 // This method will add all interferences at for a given instruction.
 108 // Interence occurs only if the LR of Def (Inst or Arg) is of the same reg
 109 // class as that of live var. The live var passed to this function is the
 110 // LVset AFTER the instruction
 111 //----------------------------------------------------------------------------
 112
 113 void PhyRegAlloc::addInterference(const Value *const Def,
 114                                   const LiveVarSet *const LVSet,
 115                                   const bool isCallInst) {
 116
 117   LiveVarSet::const_iterator LIt = LVSet->begin();
 118
 119   // get the live range of instruction
 120   const LiveRange *const LROfDef = LRI.getLiveRangeForValue( Def );
 121
 122   IGNode *const IGNodeOfDef = LROfDef->getUserIGNode();
 123   assert( IGNodeOfDef );
 124
 125   RegClass *const RCOfDef = LROfDef->getRegClass();
 126
 127   // for each live var in live variable set
 128   for( ; LIt != LVSet->end(); ++LIt) {
 129
 130     if( DEBUG_RA > 1) {
 131       cout << "< Def="; printValue(Def);
 132       cout << ", Lvar=";  printValue( *LIt); cout  << "> ";
 133     }
 134
 135     //  get the live range corresponding to live var
 136     LiveRange *const LROfVar = LRI.getLiveRangeForValue(*LIt );
 137
 138     // LROfVar can be null if it is a const since a const
 139     // doesn't have a dominating def - see Assumptions above
 140     if( LROfVar)   {
 141
 142       if(LROfDef == LROfVar)            // do not set interf for same LR
 143         continue;
 144
 145       // if 2 reg classes are the same set interference
 146       if( RCOfDef == LROfVar->getRegClass() ){
 147         RCOfDef->setInterference( LROfDef, LROfVar);
 148
 149       }
 150
 151     else if(DEBUG_RA > 1)  {
 152       // we will not have LRs for values not explicitly allocated in the
 153       // instruction stream (e.g., constants)
 154       cout << " warning: no live range for " ;
 155       printValue( *LIt); cout << endl; }
 156
 157     }
 158
 159   }
 160
 161 }
 162
 163
 164 //----------------------------------------------------------------------------
 165 // For a call instruction, this method sets the CallInterference flag in
 166 // the LR of each variable live int the Live Variable Set live after the
 167 // call instruction (except the return value of the call instruction - since
 168 // the return value does not interfere with that call itself).
 169 //----------------------------------------------------------------------------
 170
 171 void PhyRegAlloc::setCallInterferences(const MachineInstr *MInst,
 172                                        const LiveVarSet *const LVSetAft )
 173 {
 174   // Now find the LR of the return value of the call
 175
 176
 177   // We do this because, we look at the LV set *after* the instruction
 178   // to determine, which LRs must be saved across calls. The return value
 179   // of the call is live in this set - but it does not interfere with call
 180   // (i.e., we can allocate a volatile register to the return value)
 181
 182   LiveRange *RetValLR = NULL;
 183
 184   const Value *RetVal = MRI.getCallInstRetVal( MInst );
 185
 186   if( RetVal ) {
 187     RetValLR = LRI.getLiveRangeForValue( RetVal );
 188     assert( RetValLR && "No LR for RetValue of call");
 189   }
 190
 191   if( DEBUG_RA)
 192     cout << "\n For call inst: " << *MInst;
 193
 194   LiveVarSet::const_iterator LIt = LVSetAft->begin();
 195
 196   // for each live var in live variable set after machine inst
 197   for( ; LIt != LVSetAft->end(); ++LIt) {
 198
 199    //  get the live range corresponding to live var
 200     LiveRange *const LR = LRI.getLiveRangeForValue(*LIt );
 201
 202     if( LR && DEBUG_RA) {
 203       cout << "\n\tLR Aft Call: ";
 204       LR->printSet();
 205     }
 206
 207
 208     // LR can be null if it is a const since a const
 209     // doesn't have a dominating def - see Assumptions above
 210     if( LR && (LR != RetValLR) )   {
 211       LR->setCallInterference();
 212       if( DEBUG_RA) {
 213         cout << "\n  ++Added call interf for LR: " ;
 214         LR->printSet();
 215       }
 216     }
 217
 218   }
 219
 220 }
 221
 222
 223 //----------------------------------------------------------------------------
 224 // This method will walk thru code and create interferences in the IG of
 225 // each RegClass.
 226 //----------------------------------------------------------------------------
 227
 228 void PhyRegAlloc::buildInterferenceGraphs()
 229 {
 230
 231   if(DEBUG_RA) cout << "Creating interference graphs ..." << endl;
 232
 233   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 234
 235   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 236
 237     // get the iterator for machine instructions
 238     const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 239     MachineCodeForBasicBlock::const_iterator
 240       MInstIterator = MIVec.begin();
 241
 242     // iterate over all the machine instructions in BB
 243     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 244
 245       const MachineInstr * MInst = *MInstIterator;
 246
 247       // get the LV set after the instruction
 248       const LiveVarSet *const LVSetAI =
 249         LVI->getLiveVarSetAfterMInst(MInst, *BBI);
 250
 251       const bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpCode());
 252
 253       if( isCallInst ) {
 254         //cout << "\nFor call inst: " << *MInst;
 255
 256         // set the isCallInterference flag of each live range wich extends
 257         // accross this call instruction. This information is used by graph
 258         // coloring algo to avoid allocating volatile colors to live ranges
 259         // that span across calls (since they have to be saved/restored)
 260         setCallInterferences( MInst,  LVSetAI);
 261       }
 262
 263
 264       // iterate over  MI operands to find defs
 265       for( MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done(); ++OpI) {
 266
 267         if( OpI.isDef() ) {
 268           // create a new LR iff this operand is a def
 269           addInterference(*OpI, LVSetAI, isCallInst );
 270
 271         } //if this is a def
 272
 273       } // for all operands
 274
 275
 276       // Also add interference for any implicit definitions in a machine
 277       // instr (currently, only calls have this).
 278
 279       unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
 280       if(  NumOfImpRefs > 0 ) {
 281         for(unsigned z=0; z < NumOfImpRefs; z++)
 282           if( MInst->implicitRefIsDefined(z) )
 283             addInterference( MInst->getImplicitRef(z), LVSetAI, isCallInst );
 284       }
 285
 286       /*
 287       // record phi instrns in PhiInstList
 288       if( TM.getInstrInfo().isDummyPhiInstr(MInst->getOpCode()) )
 289         PhiInstList.push_back( MInst );
 290       */
 291
 292     } // for all machine instructions in BB
 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 // This method is called after register allocation is complete to set the
 338 // allocated reisters in the machine code. This code will add register numbers
 339 // to MachineOperands that contain a Value.
 340 //----------------------------------------------------------------------------
 341
 342 void PhyRegAlloc::updateMachineCode()
 343 {
 344
 345   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 346
 347   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 348
 349     // get the iterator for machine instructions
 350     MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 351     MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
 352
 353     // iterate over all the machine instructions in BB
 354     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 355
 356       MachineInstr *MInst = *MInstIterator;
 357
 358       // if this machine instr is call, insert caller saving code
 359
 360       if( (TM.getInstrInfo()).isCall( MInst->getOpCode()) )
 361         MRI.insertCallerSavingCode(MInst,  *BBI, *this );
 362
 363       // If there are instructions to be added, *before* this machine
 364       // instruction, add them now.
 365
 366       if( AddedInstrMap[ MInst ] ) {
 367
 368         deque<MachineInstr *> &IBef = (AddedInstrMap[MInst])->InstrnsBefore;
 369
 370         if( ! IBef.empty() ) {
 371
 372           deque<MachineInstr *>::iterator AdIt;
 373
 374           for( AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt ) {
 375
 376             if( DEBUG_RA)
 377               cerr << " *$* PREPENDed instr " << *AdIt << endl;
 378
 379             MInstIterator = MIVec.insert( MInstIterator, *AdIt );
 380             ++MInstIterator;
 381           }
 382
 383         }
 384
 385       }
 386
 387       // reset the stack offset for temporary variables since we may
 388       // need that to spill
 389       mcInfo.popAllTempValues(TM);
 390
 391       //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) {
 392
 393       for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 394
 395         MachineOperand& Op = MInst->getOperand(OpNum);
 396
 397         if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 398             Op.getOperandType() ==  MachineOperand::MO_CCRegister) {
 399
 400           const Value *const Val =  Op.getVRegValue();
 401
 402           // delete this condition checking later (must assert if Val is null)
 403           if( !Val) {
 404             if (DEBUG_RA)
 405               cout << "Warning: NULL Value found for operand" << endl;
 406             continue;
 407           }
 408           assert( Val && "Value is NULL");
 409
 410           LiveRange *const LR = LRI.getLiveRangeForValue(Val);
 411
 412           if ( !LR ) {
 413
 414             // nothing to worry if it's a const or a label
 415
 416             if (DEBUG_RA) {
 417               cout << "*NO LR for operand : " << Op ;
 418               cout << " [reg:" <<  Op.getAllocatedRegNum() << "]";
 419               cout << " in inst:\t" << *MInst << endl;
 420             }
 421
 422             // if register is not allocated, mark register as invalid
 423             if( Op.getAllocatedRegNum() == -1)
 424               Op.setRegForValue( MRI.getInvalidRegNum());
 425
 426
 427             continue;
 428           }
 429
 430           unsigned RCID = (LR->getRegClass())->getID();
 431
 432           if( LR->hasColor() ) {
 433             Op.setRegForValue( MRI.getUnifiedRegNum(RCID, LR->getColor()) );
 434           }
 435           else {
 436
 437             // LR did NOT receive a color (register). Now, insert spill code
 438             // for spilled opeands in this machine instruction
 439
 440             assert(0 && "LR must be spilled");
 441             //      insertCode4SpilledLR(LR, MInst, *BBI, OpNum );
 442
 443           }
 444         }
 445
 446       } // for each operand
 447
 448
 449       // If there are instructions to be added *after* this machine
 450       // instruction, add them now
 451
 452       if( AddedInstrMap[ MInst ] &&
 453           ! (AddedInstrMap[ MInst ]->InstrnsAfter).empty() ) {
 454
 455         // if there are delay slots for this instruction, the instructions
 456         // added after it must really go after the delayed instruction(s)
 457         // So, we move the InstrAfter of the current instruction to the
 458         // corresponding delayed instruction
 459
 460         unsigned delay;
 461         if((delay=TM.getInstrInfo().getNumDelaySlots(MInst->getOpCode())) >0){
 462           move2DelayedInstr(MInst,  *(MInstIterator+delay) );
 463
 464           if(DEBUG_RA)  cout<< "\nMoved an added instr after the delay slot";
 465         }
 466
 467         else {
 468
 469
 470           // Here we can add the "instructions after" to the current
 471           // instruction since there are no delay slots for this instruction
 472
 473           deque<MachineInstr *> &IAft = (AddedInstrMap[MInst])->InstrnsAfter;
 474
 475           if( ! IAft.empty() ) {
 476
 477             deque<MachineInstr *>::iterator AdIt;
 478
 479             ++MInstIterator;   // advance to the next instruction
 480
 481             for( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt ) {
 482
 483               if(DEBUG_RA)
 484                 cerr << " *#* APPENDed instr opcode: "  << *AdIt << endl;
 485
 486               MInstIterator = MIVec.insert( MInstIterator, *AdIt );
 487               ++MInstIterator;
 488             }
 489
 490             // MInsterator already points to the next instr. Since the
 491             // for loop also increments it, decrement it to point to the
 492             // instruction added last
 493             --MInstIterator;
 494
 495           }
 496
 497         }  // if not delay
 498
 499       }
 500
 501     } // for each machine instruction
 502   }
 503 }
 504
 505
 506 //----------------------------------------------------------------------------
 507 // We can use the following method to get a temporary register to be used
 508 // BEFORE any given machine instruction. If there is a register available,
 509 // this method will simply return that register and set MIBef = MIAft = NULL.
 510 // Otherwise, it will return a register and MIAft and MIBef will contain
 511 // two instructions used to free up this returned register.
 512 // Returned register number is the UNIFIED register number
 513 //----------------------------------------------------------------------------
 514
 515 int PhyRegAlloc::getUsableRegAtMI(RegClass *RC,
 516                                   const int RegType,
 517                                   const MachineInstr *MInst,
 518                                   const LiveVarSet *LVSetBef,
 519                                   MachineInstr *MIBef,
 520                                   MachineInstr *MIAft) {
 521
 522   int Reg =  getUnusedRegAtMI(RC, MInst, LVSetBef);
 523   Reg = MRI.getUnifiedRegNum(RC->getID(), Reg);
 524
 525   if( Reg != -1) {
 526     // we found an unused register, so we can simply used
 527     MIBef = MIAft = NULL;
 528   }
 529   else {
 530     // we couldn't find an unused register. Generate code to free up a reg by
 531     // saving it on stack and restoring after the instruction
 532
 533     /**** NOTE: THIS SHOULD USE THE RIGHT SIZE FOR THE REG BEING PUSHED ****/
 534     int TmpOff = mcInfo.pushTempValue(TM, /*size*/ 8);
 535
 536     Reg = getRegNotUsedByThisInst(RC, MInst);
 537     MIBef = MRI.cpReg2MemMI(Reg, MRI.getFramePointer(), TmpOff, RegType );
 538     MIAft = MRI.cpMem2RegMI(MRI.getFramePointer(), TmpOff, Reg, RegType );
 539   }
 540
 541   return Reg;
 542 }
 543
 544 //----------------------------------------------------------------------------
 545 // This method is called to get a new unused register that can be used to
 546 // accomodate a spilled value.
 547 // This method may be called several times for a single machine instruction
 548 // if it contains many spilled operands. Each time it is called, it finds
 549 // a register which is not live at that instruction and also which is not
 550 // used by other spilled operands of the same instruction.
 551 // Return register number is relative to the register class. NOT
 552 // unified number
 553 //----------------------------------------------------------------------------
 554 int PhyRegAlloc::getUnusedRegAtMI(RegClass *RC,
 555                                   const MachineInstr *MInst,
 556                                   const LiveVarSet *LVSetBef) {
 557
 558   unsigned NumAvailRegs =  RC->getNumOfAvailRegs();
 559
 560   bool *IsColorUsedArr = RC->getIsColorUsedArr();
 561
 562   for(unsigned i=0; i <  NumAvailRegs; i++)
 563       IsColorUsedArr[i] = false;
 564
 565   LiveVarSet::const_iterator LIt = LVSetBef->begin();
 566
 567   // for each live var in live variable set after machine inst
 568   for( ; LIt != LVSetBef->end(); ++LIt) {
 569
 570    //  get the live range corresponding to live var
 571     LiveRange *const LRofLV = LRI.getLiveRangeForValue(*LIt );
 572
 573     // LR can be null if it is a const since a const
 574     // doesn't have a dominating def - see Assumptions above
 575     if( LRofLV )
 576       if( LRofLV->hasColor() )
 577         IsColorUsedArr[ LRofLV->getColor() ] = true;
 578   }
 579
 580   // It is possible that one operand of this MInst was already spilled
 581   // and it received some register temporarily. If that's the case,
 582   // it is recorded in machine operand. We must skip such registers.
 583
 584   setRegsUsedByThisInst(RC, MInst);
 585
 586   unsigned c;                         // find first unused color
 587   for( c=0; c < NumAvailRegs; c++)
 588      if( ! IsColorUsedArr[ c ] ) break;
 589
 590   if(c < NumAvailRegs)
 591     return c;
 592   else
 593     return -1;
 594
 595
 596 }
 597
 598
 599
 600 //----------------------------------------------------------------------------
 601 // This method modifies the IsColorUsedArr of the register class passed to it.
 602 // It sets the bits corresponding to the registers used by this machine
 603 // instructions. Explicit operands are set.
 604 //----------------------------------------------------------------------------
 605 void PhyRegAlloc::setRegsUsedByThisInst(RegClass *RC,
 606                                        const MachineInstr *MInst ) {
 607
 608  bool *IsColorUsedArr = RC->getIsColorUsedArr();
 609
 610  for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 611
 612    const MachineOperand& Op = MInst->getOperand(OpNum);
 613
 614     if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 615         Op.getOperandType() ==  MachineOperand::MO_CCRegister) {
 616
 617       const Value *const Val =  Op.getVRegValue();
 618
 619       if( !Val )
 620         if( MRI.getRegClassIDOfValue( Val )== RC->getID() ) {
 621           int Reg;
 622           if( (Reg=Op.getAllocatedRegNum()) != -1)
 623             IsColorUsedArr[ Reg ] = true;
 624
 625         }
 626     }
 627  }
 628
 629  // If there are implicit references, mark them as well
 630
 631  for(unsigned z=0; z < MInst->getNumImplicitRefs(); z++) {
 632
 633    LiveRange *const LRofImpRef =
 634      LRI.getLiveRangeForValue( MInst->getImplicitRef(z)  );
 635
 636    if( LRofImpRef )
 637      if( LRofImpRef->hasColor() )
 638        IsColorUsedArr[ LRofImpRef->getColor() ] = true;
 639  }
 640
 641
 642
 643 }
 644
 645
 646
 647 //----------------------------------------------------------------------------
 648 // Get any other register in a register class, other than what is used
 649 // by operands of a machine instruction.
 650 //----------------------------------------------------------------------------
 651 int PhyRegAlloc::getRegNotUsedByThisInst(RegClass *RC,
 652                                          const MachineInstr *MInst) {
 653
 654   bool *IsColorUsedArr = RC->getIsColorUsedArr();
 655   unsigned NumAvailRegs =  RC->getNumOfAvailRegs();
 656
 657
 658   for(unsigned i=0; i < NumAvailRegs ; i++)
 659     IsColorUsedArr[i] = false;
 660
 661   setRegsUsedByThisInst(RC, MInst);
 662
 663   unsigned c;                         // find first unused color
 664   for( c=0; c <  RC->getNumOfAvailRegs(); c++)
 665      if( ! IsColorUsedArr[ c ] ) break;
 666
 667   if(c < NumAvailRegs)
 668     return c;
 669   else
 670     assert( 0 && "FATAL: No free register could be found in reg class!!");
 671
 672 }
 673
 674
 675
 676
 677
 678 //----------------------------------------------------------------------------
 679 // If there are delay slots for an instruction, the instructions
 680 // added after it must really go after the delayed instruction(s).
 681 // So, we move the InstrAfter of that instruction to the
 682 // corresponding delayed instruction using the following method.
 683
 684 //----------------------------------------------------------------------------
 685 void PhyRegAlloc:: move2DelayedInstr(const MachineInstr *OrigMI,
 686                                      const MachineInstr *DelayedMI) {
 687
 688
 689   // "added after" instructions of the original instr
 690   deque<MachineInstr *> &OrigAft = (AddedInstrMap[OrigMI])->InstrnsAfter;
 691
 692   // "added instructions" of the delayed instr
 693   AddedInstrns *DelayAdI = AddedInstrMap[DelayedMI];
 694
 695   if(! DelayAdI )  {                // create a new "added after" if necessary
 696     DelayAdI = new AddedInstrns();
 697     AddedInstrMap[DelayedMI] =  DelayAdI;
 698   }
 699
 700   // "added after" instructions of the delayed instr
 701   deque<MachineInstr *> &DelayedAft = DelayAdI->InstrnsAfter;
 702
 703   // go thru all the "added after instructions" of the original instruction
 704   // and append them to the "addded after instructions" of the delayed
 705   // instructions
 706
 707   deque<MachineInstr *>::iterator OrigAdIt;
 708
 709   for( OrigAdIt = OrigAft.begin(); OrigAdIt != OrigAft.end() ; ++OrigAdIt ) {
 710     DelayedAft.push_back( *OrigAdIt );
 711   }
 712
 713   // empty the "added after instructions" of the original instruction
 714   OrigAft.clear();
 715
 716 }
 717
 718 //----------------------------------------------------------------------------
 719 // This method prints the code with registers after register allocation is
 720 // complete.
 721 //----------------------------------------------------------------------------
 722 void PhyRegAlloc::printMachineCode()
 723 {
 724
 725   cout << endl << ";************** Method ";
 726   cout << Meth->getName() << " *****************" << endl;
 727
 728   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 729
 730   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 731
 732     cout << endl ; printLabel( *BBI); cout << ": ";
 733
 734     // get the iterator for machine instructions
 735     MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 736     MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
 737
 738     // iterate over all the machine instructions in BB
 739     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 740
 741       MachineInstr *const MInst = *MInstIterator;
 742
 743
 744       cout << endl << "\t";
 745       cout << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
 746
 747
 748       //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) {
 749
 750       for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 751
 752         MachineOperand& Op = MInst->getOperand(OpNum);
 753
 754         if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 755             Op.getOperandType() ==  MachineOperand::MO_CCRegister /*||
 756             Op.getOperandType() ==  MachineOperand::MO_PCRelativeDisp*/ ) {
 757
 758           const Value *const Val = Op.getVRegValue () ;
 759           // ****this code is temporary till NULL Values are fixed
 760           if( ! Val ) {
 761             cout << "\t<*NULL*>";
 762             continue;
 763           }
 764
 765           // if a label or a constant
 766           if( (Val->getValueType() == Value::BasicBlockVal)  ) {
 767
 768             cout << "\t"; printLabel(   Op.getVRegValue () );
 769           }
 770           else {
 771             // else it must be a register value
 772             const int RegNum = Op.getAllocatedRegNum();
 773
 774             cout << "\t" << "%" << MRI.getUnifiedRegName( RegNum );
 775           }
 776
 777         }
 778         else if(Op.getOperandType() ==  MachineOperand::MO_MachineRegister) {
 779           cout << "\t" << "%" << MRI.getUnifiedRegName(Op.getMachineRegNum());
 780         }
 781
 782         else
 783           cout << "\t" << Op;      // use dump field
 784       }
 785
 786
 787
 788       unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
 789       if(  NumOfImpRefs > 0 ) {
 790
 791         cout << "\tImplicit:";
 792
 793         for(unsigned z=0; z < NumOfImpRefs; z++) {
 794           printValue(  MInst->getImplicitRef(z) );
 795           cout << "\t";
 796         }
 797
 798       }
 799
 800     } // for all machine instructions
 801
 802
 803     cout << endl;
 804
 805   } // for all BBs
 806
 807   cout << endl;
 808 }
 809
 810
 811 //----------------------------------------------------------------------------
 812 //
 813 //----------------------------------------------------------------------------
 814
 815 void PhyRegAlloc::colorCallRetArgs()
 816 {
 817
 818   CallRetInstrListType &CallRetInstList = LRI.getCallRetInstrList();
 819   CallRetInstrListType::const_iterator It = CallRetInstList.begin();
 820
 821   for( ; It != CallRetInstList.end(); ++It ) {
 822
 823     const MachineInstr *const CRMI = *It;
 824     unsigned OpCode =  CRMI->getOpCode();
 825
 826     // get the added instructions for this Call/Ret instruciton
 827     AddedInstrns *AI = AddedInstrMap[ CRMI ];
 828     if ( !AI ) {
 829       AI = new AddedInstrns();
 830       AddedInstrMap[ CRMI ] = AI;
 831     }
 832
 833     // Tmp stack poistions are needed by some calls that have spilled args
 834     // So reset it before we call each such method
 835     mcInfo.popAllTempValues(TM);
 836
 837     if( (TM.getInstrInfo()).isCall( OpCode ) )
 838       MRI.colorCallArgs( CRMI, LRI, AI, *this );
 839
 840     else if (  (TM.getInstrInfo()).isReturn(OpCode) )
 841       MRI.colorRetValue( CRMI, LRI, AI );
 842
 843     else assert( 0 && "Non Call/Ret instrn in CallRetInstrList\n" );
 844
 845   }
 846
 847 }
 848
 849
 850
 851 //----------------------------------------------------------------------------
 852
 853 //----------------------------------------------------------------------------
 854 void PhyRegAlloc::colorIncomingArgs()
 855 {
 856   const BasicBlock *const FirstBB = Meth->front();
 857   const MachineInstr *FirstMI = *((FirstBB->getMachineInstrVec()).begin());
 858   assert( FirstMI && "No machine instruction in entry BB");
 859
 860   AddedInstrns *AI = AddedInstrMap[ FirstMI ];
 861   if ( !AI ) {
 862     AI = new AddedInstrns();
 863     AddedInstrMap[ FirstMI  ] = AI;
 864   }
 865
 866   MRI.colorMethodArgs(Meth, LRI, AI );
 867 }
 868
 869
 870 //----------------------------------------------------------------------------
 871 // Used to generate a label for a basic block
 872 //----------------------------------------------------------------------------
 873 void PhyRegAlloc::printLabel(const Value *const Val)
 874 {
 875   if( Val->hasName() )
 876     cout  << Val->getName();
 877   else
 878     cout << "Label" <<  Val;
 879 }
 880
 881
 882 //----------------------------------------------------------------------------
 883 // This method calls setSugColorUsable method of each live range. This
 884 // will determine whether the suggested color of LR is  really usable.
 885 // A suggested color is not usable when the suggested color is volatile
 886 // AND when there are call interferences
 887 //----------------------------------------------------------------------------
 888
 889 void PhyRegAlloc::markUnusableSugColors()
 890 {
 891   if(DEBUG_RA ) cout << "\nmarking unusable suggested colors ..." << endl;
 892
 893   // hash map iterator
 894   LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
 895   LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
 896
 897     for(  ; HMI != HMIEnd ; ++HMI ) {
 898
 899       if( (*HMI).first ) {
 900
 901         LiveRange *L = (*HMI).second;      // get the LiveRange
 902
 903         if(L) {
 904           if( L->hasSuggestedColor() ) {
 905
 906             int RCID = (L->getRegClass())->getID();
 907             if( MRI.isRegVolatile( RCID,  L->getSuggestedColor()) &&
 908                 L->isCallInterference() )
 909               L->setSuggestedColorUsable( false );
 910             else
 911               L->setSuggestedColorUsable( true );
 912           }
 913         } // if L->hasSuggestedColor()
 914       }
 915     } // for all LR's in hash map
 916 }
 917
 918
 919
 920 //----------------------------------------------------------------------------
 921 // The following method will set the stack offsets of the live ranges that
 922 // are decided to be spillled. This must be called just after coloring the
 923 // LRs using the graph coloring algo. For each live range that is spilled,
 924 // this method allocate a new spill position on the stack.
 925 //----------------------------------------------------------------------------
 926
 927 void PhyRegAlloc::allocateStackSpace4SpilledLRs()
 928 {
 929   if(DEBUG_RA ) cout << "\nsetting LR stack offsets ..." << endl;
 930
 931   // hash map iterator
 932   LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
 933   LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
 934
 935     for(  ; HMI != HMIEnd ; ++HMI ) {
 936       if( (*HMI).first ) {
 937         LiveRange *L = (*HMI).second;      // get the LiveRange
 938         if(L)
 939           if( ! L->hasColor() )
 940             L->setSpillOffFromFP(mcInfo.allocateSpilledValue(TM,L->getType()));
 941       }
 942     } // for all LR's in hash map
 943 }
 944
 945
 946
 947 //----------------------------------------------------------------------------
 948 // The entry pont to Register Allocation
 949 //----------------------------------------------------------------------------
 950
 951 void PhyRegAlloc::allocateRegisters()
 952 {
 953
 954   // make sure that we put all register classes into the RegClassList
 955   // before we call constructLiveRanges (now done in the constructor of
 956   // PhyRegAlloc class).
 957
 958   constructLiveRanges();                // create LR info
 959
 960   if( DEBUG_RA )
 961     LRI.printLiveRanges();
 962
 963   createIGNodeListsAndIGs();            // create IGNode list and IGs
 964
 965   buildInterferenceGraphs();            // build IGs in all reg classes
 966
 967
 968   if( DEBUG_RA ) {
 969     // print all LRs in all reg classes
 970     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)
 971       RegClassList[ rc ]->printIGNodeList();
 972
 973     // print IGs in all register classes
 974     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 975       RegClassList[ rc ]->printIG();
 976   }
 977
 978   LRI.coalesceLRs();                    // coalesce all live ranges
 979
 980   // coalscing could not get rid of all phi's, add phi elimination
 981   // instructions
 982   // insertPhiEleminateInstrns();
 983
 984   if( DEBUG_RA) {
 985     // print all LRs in all reg classes
 986     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)
 987       RegClassList[ rc ]->printIGNodeList();
 988
 989     // print IGs in all register classes
 990     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 991       RegClassList[ rc ]->printIG();
 992   }
 993
 994
 995   // mark un-usable suggested color before graph coloring algorithm.
 996   // When this is done, the graph coloring algo will not reserve
 997   // suggested color unnecessarily - they can be used by another LR
 998   markUnusableSugColors();
 999
1000   // color all register classes using the graph coloring algo
1001   for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
1002     RegClassList[ rc ]->colorAllRegs();
1003
1004   // Atter grpah coloring, if some LRs did not receive a color (i.e, spilled)
1005   // a poistion for such spilled LRs
1006   allocateStackSpace4SpilledLRs();
1007
1008   // color incoming args and call args
1009   colorIncomingArgs();
1010   colorCallRetArgs();
1011
1012
1013   updateMachineCode();
1014   if (DEBUG_RA) {
1015     MachineCodeForMethod::get(Meth).dump();
1016     printMachineCode();                   // only for DEBUGGING
1017   }
1018 }
1019
1020
1021