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
  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         } //if this is a def
 271       } // for all operands
 272
 273
 274       // if there are multiple defs in this instruction e.g. in SETX
 275       //
 276       if( (TM.getInstrInfo()).isPseudoInstr( MInst->getOpCode()) )
 277         addInterf4PseudoInstr(MInst);
 278
 279
 280       // Also add interference for any implicit definitions in a machine
 281       // instr (currently, only calls have this).
 282
 283       unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
 284       if(  NumOfImpRefs > 0 ) {
 285         for(unsigned z=0; z < NumOfImpRefs; z++)
 286           if( MInst->implicitRefIsDefined(z) )
 287             addInterference( MInst->getImplicitRef(z), LVSetAI, isCallInst );
 288       }
 289
 290       /*
 291       // record phi instrns in PhiInstList
 292       if( TM.getInstrInfo().isDummyPhiInstr(MInst->getOpCode()) )
 293         PhiInstList.push_back( MInst );
 294       */
 295
 296     } // for all machine instructions in BB
 297
 298   } // for all BBs in method
 299
 300
 301   // add interferences for method arguments. Since there are no explict
 302   // defs in method for args, we have to add them manually
 303
 304   addInterferencesForArgs();            // add interference for method args
 305
 306   if( DEBUG_RA)
 307     cout << "Interference graphs calculted!" << endl;
 308
 309 }
 310
 311 //--------------------------------------------------------------------------
 312 // Pseudo instructions will be exapnded to multiple instructions by the
 313 // assembler. Consequently, all the opernds must get distinct registers
 314 //--------------------------------------------------------------------------
 315
 316 void PhyRegAlloc::addInterf4PseudoInstr(const MachineInstr *MInst) {
 317
 318   bool setInterf = false;
 319
 320   // iterate over  MI operands to find defs
 321   for( MachineInstr::val_op_const_iterator It1(MInst);!It1.done(); ++It1) {
 322
 323     const LiveRange *const LROfOp1 = LRI.getLiveRangeForValue( *It1 );
 324
 325     if( !LROfOp1 && It1.isDef() )
 326       assert( 0 && "No LR for Def in PSEUDO insruction");
 327
 328     //if( !LROfOp1 ) continue;
 329
 330     MachineInstr::val_op_const_iterator It2 = It1;
 331     ++It2;
 332
 333     for(  ; !It2.done(); ++It2) {
 334
 335       const LiveRange *const LROfOp2 = LRI.getLiveRangeForValue( *It2 );
 336
 337       if( LROfOp2) {
 338
 339         RegClass *const RCOfOp1 = LROfOp1->getRegClass();
 340         RegClass *const RCOfOp2 = LROfOp2->getRegClass();
 341
 342         if( RCOfOp1 == RCOfOp2 ){
 343           RCOfOp1->setInterference( LROfOp1, LROfOp2 );
 344           //cerr << "\nSet interfs for PSEUDO inst: " << *MInst;
 345           setInterf = true;
 346         }
 347
 348
 349       } // if Op2 has a LR
 350
 351     } // for all other defs in machine instr
 352
 353   } // for all operands in an instruction
 354
 355   if( !setInterf && (MInst->getNumOperands() > 2) ) {
 356     cerr << "\nInterf not set for any operand in pseudo instr:\n";
 357     cerr << *MInst;
 358     assert(0 && "Interf not set for pseudo instr with > 2 operands" );
 359
 360   }
 361
 362 }
 363
 364
 365
 366
 367
 368 //----------------------------------------------------------------------------
 369 // This method will add interferences for incoming arguments to a method.
 370 //----------------------------------------------------------------------------
 371 void PhyRegAlloc::addInterferencesForArgs()
 372 {
 373                                               // get the InSet of root BB
 374   const LiveVarSet *const InSet = LVI->getInSetOfBB( Meth->front() );
 375
 376                                               // get the argument list
 377   const Method::ArgumentListType& ArgList = Meth->getArgumentList();
 378
 379                                               // get an iterator to arg list
 380   Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
 381
 382
 383   for( ; ArgIt != ArgList.end() ; ++ArgIt) {  // for each argument
 384     addInterference( *ArgIt, InSet, false );  // add interferences between
 385                                               // args and LVars at start
 386     if( DEBUG_RA > 1) {
 387        cout << " - %% adding interference for  argument ";
 388       printValue( (const Value *) *ArgIt); cout  << endl;
 389     }
 390   }
 391 }
 392
 393
 394 //----------------------------------------------------------------------------
 395 // This method is called after register allocation is complete to set the
 396 // allocated reisters in the machine code. This code will add register numbers
 397 // to MachineOperands that contain a Value.
 398 //----------------------------------------------------------------------------
 399
 400 void PhyRegAlloc::updateMachineCode()
 401 {
 402
 403   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 404
 405   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 406
 407     // get the iterator for machine instructions
 408     MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 409     MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
 410
 411     // iterate over all the machine instructions in BB
 412     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 413
 414       MachineInstr *MInst = *MInstIterator;
 415
 416       // do not process Phis
 417       if( (TM.getInstrInfo()).isPhi( MInst->getOpCode()) )
 418         continue;
 419
 420
 421       // if this machine instr is call, insert caller saving code
 422
 423       if( (TM.getInstrInfo()).isCall( MInst->getOpCode()) )
 424         MRI.insertCallerSavingCode(MInst,  *BBI, *this );
 425
 426
 427       // reset the stack offset for temporary variables since we may
 428       // need that to spill
 429       //mcInfo.popAllTempValues(TM);
 430       // TODO ** : do later
 431
 432       //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) {
 433
 434
 435       // Now replace set the registers for operands in the machine instruction
 436
 437       for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 438
 439         MachineOperand& Op = MInst->getOperand(OpNum);
 440
 441         if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 442             Op.getOperandType() ==  MachineOperand::MO_CCRegister) {
 443
 444           const Value *const Val =  Op.getVRegValue();
 445
 446           // delete this condition checking later (must assert if Val is null)
 447           if( !Val) {
 448             if (DEBUG_RA)
 449               cout << "Warning: NULL Value found for operand" << endl;
 450             continue;
 451           }
 452           assert( Val && "Value is NULL");
 453
 454           LiveRange *const LR = LRI.getLiveRangeForValue(Val);
 455
 456           if ( !LR ) {
 457
 458             // nothing to worry if it's a const or a label
 459
 460             if (DEBUG_RA) {
 461               cout << "*NO LR for operand : " << Op ;
 462               cout << " [reg:" <<  Op.getAllocatedRegNum() << "]";
 463               cout << " in inst:\t" << *MInst << endl;
 464             }
 465
 466             // if register is not allocated, mark register as invalid
 467             if( Op.getAllocatedRegNum() == -1)
 468               Op.setRegForValue( MRI.getInvalidRegNum());
 469
 470
 471             continue;
 472           }
 473
 474           unsigned RCID = (LR->getRegClass())->getID();
 475
 476           if( LR->hasColor() ) {
 477             Op.setRegForValue( MRI.getUnifiedRegNum(RCID, LR->getColor()) );
 478           }
 479           else {
 480
 481             // LR did NOT receive a color (register). Now, insert spill code
 482             // for spilled opeands in this machine instruction
 483
 484             //assert(0 && "LR must be spilled");
 485             insertCode4SpilledLR(LR, MInst, *BBI, OpNum );
 486
 487           }
 488         }
 489
 490       } // for each operand
 491
 492
 493       // If there are instructions to be added, *before* this machine
 494       // instruction, add them now.
 495
 496       if( AddedInstrMap[ MInst ] ) {
 497
 498         deque<MachineInstr *> &IBef = (AddedInstrMap[MInst])->InstrnsBefore;
 499
 500         if( ! IBef.empty() ) {
 501
 502           deque<MachineInstr *>::iterator AdIt;
 503
 504           for( AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt ) {
 505
 506             if( DEBUG_RA) {
 507               cerr << "For inst " << *MInst;
 508               cerr << " PREPENDed instr: " << **AdIt << endl;
 509             }
 510
 511             MInstIterator = MIVec.insert( MInstIterator, *AdIt );
 512             ++MInstIterator;
 513           }
 514
 515         }
 516
 517       }
 518
 519       // If there are instructions to be added *after* this machine
 520       // instruction, add them now
 521
 522       if( AddedInstrMap[ MInst ] &&
 523           ! (AddedInstrMap[ MInst ]->InstrnsAfter).empty() ) {
 524
 525         // if there are delay slots for this instruction, the instructions
 526         // added after it must really go after the delayed instruction(s)
 527         // So, we move the InstrAfter of the current instruction to the
 528         // corresponding delayed instruction
 529
 530         unsigned delay;
 531         if((delay=TM.getInstrInfo().getNumDelaySlots(MInst->getOpCode())) >0){
 532           move2DelayedInstr(MInst,  *(MInstIterator+delay) );
 533
 534           if(DEBUG_RA)  cout<< "\nMoved an added instr after the delay slot";
 535         }
 536
 537         else {
 538
 539
 540           // Here we can add the "instructions after" to the current
 541           // instruction since there are no delay slots for this instruction
 542
 543           deque<MachineInstr *> &IAft = (AddedInstrMap[MInst])->InstrnsAfter;
 544
 545           if( ! IAft.empty() ) {
 546
 547             deque<MachineInstr *>::iterator AdIt;
 548
 549             ++MInstIterator;   // advance to the next instruction
 550
 551             for( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt ) {
 552
 553               if(DEBUG_RA) {
 554                 cerr << "For inst " << *MInst;
 555                 cerr << " APPENDed instr: "  << **AdIt << endl;
 556               }
 557
 558               MInstIterator = MIVec.insert( MInstIterator, *AdIt );
 559               ++MInstIterator;
 560             }
 561
 562             // MInsterator already points to the next instr. Since the
 563             // for loop also increments it, decrement it to point to the
 564             // instruction added last
 565             --MInstIterator;
 566
 567           }
 568
 569         }  // if not delay
 570
 571       }
 572
 573     } // for each machine instruction
 574   }
 575 }
 576
 577
 578
 579 //----------------------------------------------------------------------------
 580 // This method inserts spill code for AN operand whose LR was spilled.
 581 // This method may be called several times for a single machine instruction
 582 // if it contains many spilled operands. Each time it is called, it finds
 583 // a register which is not live at that instruction and also which is not
 584 // used by other spilled operands of the same instruction. Then it uses
 585 // this register temporarily to accomodate the spilled value.
 586 //----------------------------------------------------------------------------
 587 void PhyRegAlloc::insertCode4SpilledLR(const LiveRange *LR,
 588                                        MachineInstr *MInst,
 589                                        const BasicBlock *BB,
 590                                        const unsigned OpNum) {
 591
 592   assert(! TM.getInstrInfo().isCall(MInst->getOpCode()) &&
 593          (! TM.getInstrInfo().isReturn(MInst->getOpCode())) &&
 594          "Arg of a call/ret must be handled elsewhere");
 595
 596   MachineOperand& Op = MInst->getOperand(OpNum);
 597   bool isDef =  MInst->operandIsDefined(OpNum);
 598   unsigned RegType = MRI.getRegType( LR );
 599   int SpillOff = LR->getSpillOffFromFP();
 600   RegClass *RC = LR->getRegClass();
 601   const LiveVarSet *LVSetBef =  LVI->getLiveVarSetBeforeMInst(MInst, BB);
 602
 603   /**** NOTE: THIS SHOULD USE THE RIGHT SIZE FOR THE REG BEING PUSHED ****/
 604   int TmpOff =
 605     mcInfo.pushTempValue(TM, 8 /* TM.findOptimalStorageSize(LR->getType()) */);
 606
 607   MachineInstr *MIBef=NULL,  *AdIMid=NULL, *MIAft=NULL;
 608
 609   int TmpRegU = getUsableUniRegAtMI(RC, RegType, MInst,LVSetBef, MIBef, MIAft);
 610
 611   // get the added instructions for this instruciton
 612   AddedInstrns *AI = AddedInstrMap[ MInst ];
 613   if ( !AI ) {
 614     AI = new AddedInstrns();
 615     AddedInstrMap[ MInst ] = AI;
 616   }
 617
 618
 619   if( !isDef ) {
 620
 621     // for a USE, we have to load the value of LR from stack to a TmpReg
 622     // and use the TmpReg as one operand of instruction
 623
 624     // actual loading instruction
 625     AdIMid = MRI.cpMem2RegMI(MRI.getFramePointer(), SpillOff, TmpRegU,RegType);
 626
 627     if( MIBef )
 628       (AI->InstrnsBefore).push_back(MIBef);
 629
 630     (AI->InstrnsBefore).push_back(AdIMid);
 631
 632     if( MIAft)
 633       (AI->InstrnsAfter).push_front(MIAft);
 634
 635
 636   }
 637   else {   // if this is a Def
 638
 639     // for a DEF, we have to store the value produced by this instruction
 640     // on the stack position allocated for this LR
 641
 642     // actual storing instruction
 643     AdIMid = MRI.cpReg2MemMI(TmpRegU, MRI.getFramePointer(), SpillOff,RegType);
 644
 645     if( MIBef )
 646       (AI->InstrnsBefore).push_back(MIBef);
 647
 648     (AI->InstrnsAfter).push_front(AdIMid);
 649
 650     if( MIAft)
 651       (AI->InstrnsAfter).push_front(MIAft);
 652
 653   }  // if !DEF
 654
 655   cerr << "\nFor Inst " << *MInst;
 656   cerr << " - SPILLED LR: "; LR->printSet();
 657   cerr << "\n - Added Instructions:";
 658   if( MIBef ) cerr <<  *MIBef;
 659   cerr <<  *AdIMid;
 660   if( MIAft ) cerr <<  *MIAft;
 661
 662   Op.setRegForValue( TmpRegU );    // set the opearnd
 663
 664
 665 }
 666
 667
 668
 669
 670
 671
 672 //----------------------------------------------------------------------------
 673 // We can use the following method to get a temporary register to be used
 674 // BEFORE any given machine instruction. If there is a register available,
 675 // this method will simply return that register and set MIBef = MIAft = NULL.
 676 // Otherwise, it will return a register and MIAft and MIBef will contain
 677 // two instructions used to free up this returned register.
 678 // Returned register number is the UNIFIED register number
 679 //----------------------------------------------------------------------------
 680
 681 int PhyRegAlloc::getUsableUniRegAtMI(RegClass *RC,
 682                                   const int RegType,
 683                                   const MachineInstr *MInst,
 684                                   const LiveVarSet *LVSetBef,
 685                                   MachineInstr *MIBef,
 686                                   MachineInstr *MIAft) {
 687
 688   int RegU =  getUnusedUniRegAtMI(RC, MInst, LVSetBef);
 689
 690
 691   if( RegU != -1) {
 692     // we found an unused register, so we can simply use it
 693     MIBef = MIAft = NULL;
 694   }
 695   else {
 696     // we couldn't find an unused register. Generate code to free up a reg by
 697     // saving it on stack and restoring after the instruction
 698
 699     /**** NOTE: THIS SHOULD USE THE RIGHT SIZE FOR THE REG BEING PUSHED ****/
 700     int TmpOff = mcInfo.pushTempValue(TM, /*size*/ 8);
 701
 702     RegU = getUniRegNotUsedByThisInst(RC, MInst);
 703     MIBef = MRI.cpReg2MemMI(RegU, MRI.getFramePointer(), TmpOff, RegType );
 704     MIAft = MRI.cpMem2RegMI(MRI.getFramePointer(), TmpOff, RegU, RegType );
 705   }
 706
 707   return RegU;
 708 }
 709
 710 //----------------------------------------------------------------------------
 711 // This method is called to get a new unused register that can be used to
 712 // accomodate a spilled value.
 713 // This method may be called several times for a single machine instruction
 714 // if it contains many spilled operands. Each time it is called, it finds
 715 // a register which is not live at that instruction and also which is not
 716 // used by other spilled operands of the same instruction.
 717 // Return register number is relative to the register class. NOT
 718 // unified number
 719 //----------------------------------------------------------------------------
 720 int PhyRegAlloc::getUnusedUniRegAtMI(RegClass *RC,
 721                                   const MachineInstr *MInst,
 722                                   const LiveVarSet *LVSetBef) {
 723
 724   unsigned NumAvailRegs =  RC->getNumOfAvailRegs();
 725
 726   bool *IsColorUsedArr = RC->getIsColorUsedArr();
 727
 728   for(unsigned i=0; i <  NumAvailRegs; i++)     // Reset array
 729       IsColorUsedArr[i] = false;
 730
 731   LiveVarSet::const_iterator LIt = LVSetBef->begin();
 732
 733   // for each live var in live variable set after machine inst
 734   for( ; LIt != LVSetBef->end(); ++LIt) {
 735
 736    //  get the live range corresponding to live var
 737     LiveRange *const LRofLV = LRI.getLiveRangeForValue(*LIt );
 738
 739     // LR can be null if it is a const since a const
 740     // doesn't have a dominating def - see Assumptions above
 741     if( LRofLV )
 742       if( LRofLV->hasColor() )
 743         IsColorUsedArr[ LRofLV->getColor() ] = true;
 744   }
 745
 746   // It is possible that one operand of this MInst was already spilled
 747   // and it received some register temporarily. If that's the case,
 748   // it is recorded in machine operand. We must skip such registers.
 749
 750   setRelRegsUsedByThisInst(RC, MInst);
 751
 752   unsigned c;                         // find first unused color
 753   for( c=0; c < NumAvailRegs; c++)
 754      if( ! IsColorUsedArr[ c ] ) break;
 755
 756   if(c < NumAvailRegs)
 757     return  MRI.getUnifiedRegNum(RC->getID(), c);
 758   else
 759     return -1;
 760
 761
 762 }
 763
 764
 765 //----------------------------------------------------------------------------
 766 // Get any other register in a register class, other than what is used
 767 // by operands of a machine instruction. Returns the unified reg number.
 768 //----------------------------------------------------------------------------
 769 int PhyRegAlloc::getUniRegNotUsedByThisInst(RegClass *RC,
 770                                          const MachineInstr *MInst) {
 771
 772   bool *IsColorUsedArr = RC->getIsColorUsedArr();
 773   unsigned NumAvailRegs =  RC->getNumOfAvailRegs();
 774
 775
 776   for(unsigned i=0; i < NumAvailRegs ; i++)   // Reset array
 777     IsColorUsedArr[i] = false;
 778
 779   setRelRegsUsedByThisInst(RC, MInst);
 780
 781   unsigned c;                         // find first unused color
 782   for( c=0; c <  RC->getNumOfAvailRegs(); c++)
 783      if( ! IsColorUsedArr[ c ] ) break;
 784
 785   if(c < NumAvailRegs)
 786     return  MRI.getUnifiedRegNum(RC->getID(), c);
 787   else
 788     assert( 0 && "FATAL: No free register could be found in reg class!!");
 789
 790 }
 791
 792
 793
 794
 795
 796 //----------------------------------------------------------------------------
 797 // This method modifies the IsColorUsedArr of the register class passed to it.
 798 // It sets the bits corresponding to the registers used by this machine
 799 // instructions. Both explicit and implicit operands are set.
 800 //----------------------------------------------------------------------------
 801 void PhyRegAlloc::setRelRegsUsedByThisInst(RegClass *RC,
 802                                        const MachineInstr *MInst ) {
 803
 804  bool *IsColorUsedArr = RC->getIsColorUsedArr();
 805
 806  for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 807
 808    const MachineOperand& Op = MInst->getOperand(OpNum);
 809
 810     if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 811         Op.getOperandType() ==  MachineOperand::MO_CCRegister ) {
 812
 813       const Value *const Val =  Op.getVRegValue();
 814
 815       if( Val )
 816         if( MRI.getRegClassIDOfValue(Val) == RC->getID() ) {
 817           int Reg;
 818           if( (Reg=Op.getAllocatedRegNum()) != -1) {
 819             IsColorUsedArr[ Reg ] = true;
 820           }
 821           else {
 822             // it is possilbe that this operand still is not marked with
 823             // a register but it has a LR and that received a color
 824
 825             LiveRange *LROfVal =  LRI.getLiveRangeForValue(Val);
 826             if( LROfVal)
 827               if( LROfVal->hasColor() )
 828                 IsColorUsedArr[ LROfVal->getColor() ] = true;
 829           }
 830
 831         } // if reg classes are the same
 832     }
 833     else if (Op.getOperandType() ==  MachineOperand::MO_MachineRegister) {
 834       IsColorUsedArr[ Op.getMachineRegNum() ] = true;
 835     }
 836  }
 837
 838  // If there are implicit references, mark them as well
 839
 840  for(unsigned z=0; z < MInst->getNumImplicitRefs(); z++) {
 841
 842    LiveRange *const LRofImpRef =
 843      LRI.getLiveRangeForValue( MInst->getImplicitRef(z)  );
 844
 845    if( LRofImpRef )
 846      if( LRofImpRef->hasColor() )
 847        IsColorUsedArr[ LRofImpRef->getColor() ] = true;
 848  }
 849
 850
 851
 852 }
 853
 854
 855
 856
 857
 858
 859
 860
 861 //----------------------------------------------------------------------------
 862 // If there are delay slots for an instruction, the instructions
 863 // added after it must really go after the delayed instruction(s).
 864 // So, we move the InstrAfter of that instruction to the
 865 // corresponding delayed instruction using the following method.
 866
 867 //----------------------------------------------------------------------------
 868 void PhyRegAlloc:: move2DelayedInstr(const MachineInstr *OrigMI,
 869                                      const MachineInstr *DelayedMI) {
 870
 871
 872   // "added after" instructions of the original instr
 873   deque<MachineInstr *> &OrigAft = (AddedInstrMap[OrigMI])->InstrnsAfter;
 874
 875   // "added instructions" of the delayed instr
 876   AddedInstrns *DelayAdI = AddedInstrMap[DelayedMI];
 877
 878   if(! DelayAdI )  {                // create a new "added after" if necessary
 879     DelayAdI = new AddedInstrns();
 880     AddedInstrMap[DelayedMI] =  DelayAdI;
 881   }
 882
 883   // "added after" instructions of the delayed instr
 884   deque<MachineInstr *> &DelayedAft = DelayAdI->InstrnsAfter;
 885
 886   // go thru all the "added after instructions" of the original instruction
 887   // and append them to the "addded after instructions" of the delayed
 888   // instructions
 889
 890   deque<MachineInstr *>::iterator OrigAdIt;
 891
 892   for( OrigAdIt = OrigAft.begin(); OrigAdIt != OrigAft.end() ; ++OrigAdIt ) {
 893     DelayedAft.push_back( *OrigAdIt );
 894   }
 895
 896   // empty the "added after instructions" of the original instruction
 897   OrigAft.clear();
 898
 899 }
 900
 901 //----------------------------------------------------------------------------
 902 // This method prints the code with registers after register allocation is
 903 // complete.
 904 //----------------------------------------------------------------------------
 905 void PhyRegAlloc::printMachineCode()
 906 {
 907
 908   cout << endl << ";************** Method ";
 909   cout << Meth->getName() << " *****************" << endl;
 910
 911   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 912
 913   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 914
 915     cout << endl ; printLabel( *BBI); cout << ": ";
 916
 917     // get the iterator for machine instructions
 918     MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 919     MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
 920
 921     // iterate over all the machine instructions in BB
 922     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 923
 924       MachineInstr *const MInst = *MInstIterator;
 925
 926
 927       cout << endl << "\t";
 928       cout << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
 929
 930
 931       //for(MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done();++OpI) {
 932
 933       for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 934
 935         MachineOperand& Op = MInst->getOperand(OpNum);
 936
 937         if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 938             Op.getOperandType() ==  MachineOperand::MO_CCRegister /*||
 939             Op.getOperandType() ==  MachineOperand::MO_PCRelativeDisp*/ ) {
 940
 941           const Value *const Val = Op.getVRegValue () ;
 942           // ****this code is temporary till NULL Values are fixed
 943           if( ! Val ) {
 944             cout << "\t<*NULL*>";
 945             continue;
 946           }
 947
 948           // if a label or a constant
 949           if( (Val->getValueType() == Value::BasicBlockVal)  ) {
 950
 951             cout << "\t"; printLabel(   Op.getVRegValue () );
 952           }
 953           else {
 954             // else it must be a register value
 955             const int RegNum = Op.getAllocatedRegNum();
 956
 957             cout << "\t" << "%" << MRI.getUnifiedRegName( RegNum );
 958             if (Val->hasName() )
 959               cout << "(" << Val->getName() << ")";
 960             else
 961               cout << "(" << Val << ")";
 962
 963             if( Op.opIsDef() )
 964               cout << "*";
 965
 966             const LiveRange *LROfVal = LRI.getLiveRangeForValue(Val);
 967             if( LROfVal )
 968               if( LROfVal->hasSpillOffset() )
 969                 cout << "$";
 970           }
 971
 972         }
 973         else if(Op.getOperandType() ==  MachineOperand::MO_MachineRegister) {
 974           cout << "\t" << "%" << MRI.getUnifiedRegName(Op.getMachineRegNum());
 975         }
 976
 977         else
 978           cout << "\t" << Op;      // use dump field
 979       }
 980
 981
 982
 983       unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
 984       if(  NumOfImpRefs > 0 ) {
 985
 986         cout << "\tImplicit:";
 987
 988         for(unsigned z=0; z < NumOfImpRefs; z++) {
 989           printValue(  MInst->getImplicitRef(z) );
 990           cout << "\t";
 991         }
 992
 993       }
 994
 995     } // for all machine instructions
 996
 997
 998     cout << endl;
 999
1000   } // for all BBs
1001
1002   cout << endl;
1003 }
1004
1005
1006 //----------------------------------------------------------------------------
1007 //
1008 //----------------------------------------------------------------------------
1009
1010 void PhyRegAlloc::colorCallRetArgs()
1011 {
1012
1013   CallRetInstrListType &CallRetInstList = LRI.getCallRetInstrList();
1014   CallRetInstrListType::const_iterator It = CallRetInstList.begin();
1015
1016   for( ; It != CallRetInstList.end(); ++It ) {
1017
1018     const MachineInstr *const CRMI = *It;
1019     unsigned OpCode =  CRMI->getOpCode();
1020
1021     // get the added instructions for this Call/Ret instruciton
1022     AddedInstrns *AI = AddedInstrMap[ CRMI ];
1023     if ( !AI ) {
1024       AI = new AddedInstrns();
1025       AddedInstrMap[ CRMI ] = AI;
1026     }
1027
1028     // Tmp stack poistions are needed by some calls that have spilled args
1029     // So reset it before we call each such method
1030     //mcInfo.popAllTempValues(TM);
1031
1032
1033
1034     if( (TM.getInstrInfo()).isCall( OpCode ) )
1035       MRI.colorCallArgs( CRMI, LRI, AI, *this );
1036
1037     else if (  (TM.getInstrInfo()).isReturn(OpCode) )
1038       MRI.colorRetValue( CRMI, LRI, AI );
1039
1040     else assert( 0 && "Non Call/Ret instrn in CallRetInstrList\n" );
1041
1042   }
1043
1044 }
1045
1046
1047
1048 //----------------------------------------------------------------------------
1049
1050 //----------------------------------------------------------------------------
1051 void PhyRegAlloc::colorIncomingArgs()
1052 {
1053   const BasicBlock *const FirstBB = Meth->front();
1054   const MachineInstr *FirstMI = *((FirstBB->getMachineInstrVec()).begin());
1055   assert( FirstMI && "No machine instruction in entry BB");
1056
1057   AddedInstrns *AI = AddedInstrMap[ FirstMI ];
1058   if ( !AI ) {
1059     AI = new AddedInstrns();
1060     AddedInstrMap[ FirstMI  ] = AI;
1061   }
1062
1063   MRI.colorMethodArgs(Meth, LRI, AI );
1064 }
1065
1066
1067 //----------------------------------------------------------------------------
1068 // Used to generate a label for a basic block
1069 //----------------------------------------------------------------------------
1070 void PhyRegAlloc::printLabel(const Value *const Val)
1071 {
1072   if( Val->hasName() )
1073     cout  << Val->getName();
1074   else
1075     cout << "Label" <<  Val;
1076 }
1077
1078
1079 //----------------------------------------------------------------------------
1080 // This method calls setSugColorUsable method of each live range. This
1081 // will determine whether the suggested color of LR is  really usable.
1082 // A suggested color is not usable when the suggested color is volatile
1083 // AND when there are call interferences
1084 //----------------------------------------------------------------------------
1085
1086 void PhyRegAlloc::markUnusableSugColors()
1087 {
1088   if(DEBUG_RA ) cout << "\nmarking unusable suggested colors ..." << endl;
1089
1090   // hash map iterator
1091   LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
1092   LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
1093
1094     for(  ; HMI != HMIEnd ; ++HMI ) {
1095
1096       if( (*HMI).first ) {
1097
1098         LiveRange *L = (*HMI).second;      // get the LiveRange
1099
1100         if(L) {
1101           if( L->hasSuggestedColor() ) {
1102
1103             int RCID = (L->getRegClass())->getID();
1104             if( MRI.isRegVolatile( RCID,  L->getSuggestedColor()) &&
1105                 L->isCallInterference() )
1106               L->setSuggestedColorUsable( false );
1107             else
1108               L->setSuggestedColorUsable( true );
1109           }
1110         } // if L->hasSuggestedColor()
1111       }
1112     } // for all LR's in hash map
1113 }
1114
1115
1116
1117 //----------------------------------------------------------------------------
1118 // The following method will set the stack offsets of the live ranges that
1119 // are decided to be spillled. This must be called just after coloring the
1120 // LRs using the graph coloring algo. For each live range that is spilled,
1121 // this method allocate a new spill position on the stack.
1122 //----------------------------------------------------------------------------
1123
1124 void PhyRegAlloc::allocateStackSpace4SpilledLRs()
1125 {
1126   if(DEBUG_RA ) cout << "\nsetting LR stack offsets ..." << endl;
1127
1128   // hash map iterator
1129   LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
1130   LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
1131
1132     for(  ; HMI != HMIEnd ; ++HMI ) {
1133       if( (*HMI).first ) {
1134         LiveRange *L = (*HMI).second;      // get the LiveRange
1135         if(L)
1136           if( ! L->hasColor() )
1137   /**** NOTE: THIS SHOULD USE THE RIGHT SIZE FOR THE REG BEING PUSHED ****/
1138             L->setSpillOffFromFP(mcInfo.allocateSpilledValue(TM, Type::LongTy /*L->getType()*/ ));
1139       }
1140     } // for all LR's in hash map
1141 }
1142
1143
1144
1145 //----------------------------------------------------------------------------
1146 // The entry pont to Register Allocation
1147 //----------------------------------------------------------------------------
1148
1149 void PhyRegAlloc::allocateRegisters()
1150 {
1151
1152   // make sure that we put all register classes into the RegClassList
1153   // before we call constructLiveRanges (now done in the constructor of
1154   // PhyRegAlloc class).
1155
1156   constructLiveRanges();                // create LR info
1157
1158   if( DEBUG_RA )
1159     LRI.printLiveRanges();
1160
1161   createIGNodeListsAndIGs();            // create IGNode list and IGs
1162
1163   buildInterferenceGraphs();            // build IGs in all reg classes
1164
1165
1166   if( DEBUG_RA ) {
1167     // print all LRs in all reg classes
1168     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)
1169       RegClassList[ rc ]->printIGNodeList();
1170
1171     // print IGs in all register classes
1172     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
1173       RegClassList[ rc ]->printIG();
1174   }
1175
1176   LRI.coalesceLRs();                    // coalesce all live ranges
1177
1178   // coalscing could not get rid of all phi's, add phi elimination
1179   // instructions
1180   // insertPhiEleminateInstrns();
1181
1182   if( DEBUG_RA) {
1183     // print all LRs in all reg classes
1184     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)
1185       RegClassList[ rc ]->printIGNodeList();
1186
1187     // print IGs in all register classes
1188     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
1189       RegClassList[ rc ]->printIG();
1190   }
1191
1192
1193   // mark un-usable suggested color before graph coloring algorithm.
1194   // When this is done, the graph coloring algo will not reserve
1195   // suggested color unnecessarily - they can be used by another LR
1196   markUnusableSugColors();
1197
1198   // color all register classes using the graph coloring algo
1199   for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
1200     RegClassList[ rc ]->colorAllRegs();
1201
1202   // Atter grpah coloring, if some LRs did not receive a color (i.e, spilled)
1203   // a poistion for such spilled LRs
1204   allocateStackSpace4SpilledLRs();
1205
1206   mcInfo.popAllTempValues(TM);  // TODO **Check
1207
1208   // color incoming args and call args
1209   colorIncomingArgs();
1210   colorCallRetArgs();
1211
1212
1213   updateMachineCode();
1214   if (DEBUG_RA) {
1215     MachineCodeForMethod::get(Meth).dump();
1216     printMachineCode();                   // only for DEBUGGING
1217   }
1218
1219
1220
1221   /*
1222   printMachineCode();                   // only for DEBUGGING
1223
1224   cout << "\nAllocted for method " <<  Meth->getName();
1225   char ch;
1226   cin >> ch;
1227   */
1228
1229
1230 }
1231
1232
1233