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 #include <math.h>
  18
  19
  20 // ***TODO: There are several places we add instructions. Validate the order
  21 //          of adding these instructions.
  22
  23
  24
  25 cl::Enum<RegAllocDebugLevel_t> DEBUG_RA("dregalloc", cl::NoFlags,
  26   "enable register allocation debugging information",
  27   clEnumValN(RA_DEBUG_None   , "n", "disable debug output"),
  28   clEnumValN(RA_DEBUG_Normal , "y", "enable debug output"),
  29   clEnumValN(RA_DEBUG_Verbose, "v", "enable extra debug output"), 0);
  30
  31
  32 //----------------------------------------------------------------------------
  33 // Constructor: Init local composite objects and create register classes.
  34 //----------------------------------------------------------------------------
  35 PhyRegAlloc::PhyRegAlloc(Method *M,
  36                          const TargetMachine& tm,
  37                          MethodLiveVarInfo *const Lvi)
  38                         : RegClassList(),
  39                           TM(tm),
  40                           Meth(M),
  41                           mcInfo(MachineCodeForMethod::get(M)),
  42                           LVI(Lvi), LRI(M, tm, RegClassList),
  43                           MRI( tm.getRegInfo() ),
  44                           NumOfRegClasses(MRI.getNumOfRegClasses()),
  45                           AddedInstrMap(), LoopDepthCalc(M), ResColList() {
  46
  47   // create each RegisterClass and put in RegClassList
  48   //
  49   for( unsigned int rc=0; rc < NumOfRegClasses; rc++)
  50     RegClassList.push_back( new RegClass(M, MRI.getMachineRegClass(rc),
  51                                          &ResColList) );
  52 }
  53
  54
  55 //----------------------------------------------------------------------------
  56 // Destructor: Deletes register classes
  57 //----------------------------------------------------------------------------
  58 PhyRegAlloc::~PhyRegAlloc() {
  59
  60   for( unsigned int rc=0; rc < NumOfRegClasses; rc++) {
  61     RegClass *RC = RegClassList[rc];
  62     delete RC;
  63   }
  64 }
  65
  66 //----------------------------------------------------------------------------
  67 // This method initally creates interference graphs (one in each reg class)
  68 // and IGNodeList (one in each IG). The actual nodes will be pushed later.
  69 //----------------------------------------------------------------------------
  70 void PhyRegAlloc::createIGNodeListsAndIGs()
  71 {
  72   if(DEBUG_RA ) cout << "Creating LR lists ..." << endl;
  73
  74   // hash map iterator
  75   LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
  76
  77   // hash map end
  78   LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
  79
  80     for(  ; HMI != HMIEnd ; ++HMI ) {
  81
  82       if( (*HMI).first ) {
  83
  84         LiveRange *L = (*HMI).second;   // get the LiveRange
  85
  86         if( !L) {
  87           if( DEBUG_RA) {
  88             cout << "\n*?!?Warning: Null liver range found for: ";
  89             printValue( (*HMI).first) ; cout << endl;
  90           }
  91           continue;
  92         }
  93                                         // if the Value * is not null, and LR
  94                                         // is not yet written to the IGNodeList
  95        if( !(L->getUserIGNode())  ) {
  96
  97          RegClass *const RC =           // RegClass of first value in the LR
  98            //RegClassList [MRI.getRegClassIDOfValue(*(L->begin()))];
  99            RegClassList[ L->getRegClass()->getID() ];
 100
 101          RC-> addLRToIG( L );           // add this LR to an IG
 102        }
 103     }
 104   }
 105
 106                                         // init RegClassList
 107   for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
 108     RegClassList[ rc ]->createInterferenceGraph();
 109
 110   if( DEBUG_RA)
 111     cout << "LRLists Created!" << endl;
 112 }
 113
 114
 115
 116
 117 //----------------------------------------------------------------------------
 118 // This method will add all interferences at for a given instruction.
 119 // Interence occurs only if the LR of Def (Inst or Arg) is of the same reg
 120 // class as that of live var. The live var passed to this function is the
 121 // LVset AFTER the instruction
 122 //----------------------------------------------------------------------------
 123 void PhyRegAlloc::addInterference(const Value *const Def,
 124                                   const LiveVarSet *const LVSet,
 125                                   const bool isCallInst) {
 126
 127   LiveVarSet::const_iterator LIt = LVSet->begin();
 128
 129   // get the live range of instruction
 130   //
 131   const LiveRange *const LROfDef = LRI.getLiveRangeForValue( Def );
 132
 133   IGNode *const IGNodeOfDef = LROfDef->getUserIGNode();
 134   assert( IGNodeOfDef );
 135
 136   RegClass *const RCOfDef = LROfDef->getRegClass();
 137
 138   // for each live var in live variable set
 139   //
 140   for( ; LIt != LVSet->end(); ++LIt) {
 141
 142     if( DEBUG_RA > 1) {
 143       cout << "< Def="; printValue(Def);
 144       cout << ", Lvar=";  printValue( *LIt); cout  << "> ";
 145     }
 146
 147     //  get the live range corresponding to live var
 148     //
 149     LiveRange *const LROfVar = LRI.getLiveRangeForValue(*LIt );
 150
 151     // LROfVar can be null if it is a const since a const
 152     // doesn't have a dominating def - see Assumptions above
 153     //
 154     if( LROfVar)   {
 155
 156       if(LROfDef == LROfVar)            // do not set interf for same LR
 157         continue;
 158
 159       // if 2 reg classes are the same set interference
 160       //
 161       if( RCOfDef == LROfVar->getRegClass() ){
 162         RCOfDef->setInterference( LROfDef, LROfVar);
 163
 164       }
 165
 166     else if(DEBUG_RA > 1)  {
 167       // we will not have LRs for values not explicitly allocated in the
 168       // instruction stream (e.g., constants)
 169       cout << " warning: no live range for " ;
 170       printValue( *LIt); cout << endl; }
 171
 172     }
 173
 174   }
 175
 176 }
 177
 178
 179
 180
 181 //----------------------------------------------------------------------------
 182 // For a call instruction, this method sets the CallInterference flag in
 183 // the LR of each variable live int the Live Variable Set live after the
 184 // call instruction (except the return value of the call instruction - since
 185 // the return value does not interfere with that call itself).
 186 //----------------------------------------------------------------------------
 187
 188 void PhyRegAlloc::setCallInterferences(const MachineInstr *MInst,
 189                                        const LiveVarSet *const LVSetAft ) {
 190
 191   // Now find the LR of the return value of the call
 192   // We do this because, we look at the LV set *after* the instruction
 193   // to determine, which LRs must be saved across calls. The return value
 194   // of the call is live in this set - but it does not interfere with call
 195   // (i.e., we can allocate a volatile register to the return value)
 196   //
 197   LiveRange *RetValLR = NULL;
 198   const Value *RetVal = MRI.getCallInstRetVal( MInst );
 199
 200   if( RetVal ) {
 201     RetValLR = LRI.getLiveRangeForValue( RetVal );
 202     assert( RetValLR && "No LR for RetValue of call");
 203   }
 204
 205   if( DEBUG_RA)
 206     cout << "\n For call inst: " << *MInst;
 207
 208   LiveVarSet::const_iterator LIt = LVSetAft->begin();
 209
 210   // for each live var in live variable set after machine inst
 211   //
 212   for( ; LIt != LVSetAft->end(); ++LIt) {
 213
 214     //  get the live range corresponding to live var
 215     //
 216     LiveRange *const LR = LRI.getLiveRangeForValue(*LIt );
 217
 218     if( LR && DEBUG_RA) {
 219       cout << "\n\tLR Aft Call: ";
 220       LR->printSet();
 221     }
 222
 223
 224     // LR can be null if it is a const since a const
 225     // doesn't have a dominating def - see Assumptions above
 226     //
 227     if( LR && (LR != RetValLR) )   {
 228       LR->setCallInterference();
 229       if( DEBUG_RA) {
 230         cout << "\n  ++Added call interf for LR: " ;
 231         LR->printSet();
 232       }
 233     }
 234
 235   }
 236
 237 }
 238
 239
 240
 241
 242 //----------------------------------------------------------------------------
 243 // This method will walk thru code and create interferences in the IG of
 244 // each RegClass. Also, this method calculates the spill cost of each
 245 // Live Range (it is done in this method to save another pass over the code).
 246 //----------------------------------------------------------------------------
 247 void PhyRegAlloc::buildInterferenceGraphs()
 248 {
 249
 250   if(DEBUG_RA) cout << "Creating interference graphs ..." << endl;
 251
 252   unsigned BBLoopDepthCost;
 253   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 254
 255   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 256
 257     // find the 10^(loop_depth) of this BB
 258     //
 259     BBLoopDepthCost = (unsigned) pow( 10.0, LoopDepthCalc.getLoopDepth(*BBI));
 260
 261     // get the iterator for machine instructions
 262     //
 263     const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 264     MachineCodeForBasicBlock::const_iterator
 265       MInstIterator = MIVec.begin();
 266
 267     // iterate over all the machine instructions in BB
 268     //
 269     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 270
 271       const MachineInstr * MInst = *MInstIterator;
 272
 273       // get the LV set after the instruction
 274       //
 275       const LiveVarSet *const LVSetAI =
 276         LVI->getLiveVarSetAfterMInst(MInst, *BBI);
 277
 278       const bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpCode());
 279
 280       if( isCallInst ) {
 281         // set the isCallInterference flag of each live range wich extends
 282         // accross this call instruction. This information is used by graph
 283         // coloring algo to avoid allocating volatile colors to live ranges
 284         // that span across calls (since they have to be saved/restored)
 285         //
 286         setCallInterferences( MInst,  LVSetAI);
 287       }
 288
 289
 290       // iterate over all MI operands to find defs
 291       //
 292       for( MachineInstr::val_const_op_iterator OpI(MInst);!OpI.done(); ++OpI) {
 293
 294         if( OpI.isDef() ) {
 295           // create a new LR iff this operand is a def
 296           //
 297           addInterference(*OpI, LVSetAI, isCallInst );
 298         }
 299
 300         // Calculate the spill cost of each live range
 301         //
 302         LiveRange *LR = LRI.getLiveRangeForValue( *OpI );
 303         if( LR )
 304           LR->addSpillCost(BBLoopDepthCost);
 305       }
 306
 307
 308       // if there are multiple defs in this instruction e.g. in SETX
 309       //
 310       if( (TM.getInstrInfo()).isPseudoInstr( MInst->getOpCode()) )
 311         addInterf4PseudoInstr(MInst);
 312
 313
 314       // Also add interference for any implicit definitions in a machine
 315       // instr (currently, only calls have this).
 316       //
 317       unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
 318       if(  NumOfImpRefs > 0 ) {
 319         for(unsigned z=0; z < NumOfImpRefs; z++)
 320           if( MInst->implicitRefIsDefined(z) )
 321             addInterference( MInst->getImplicitRef(z), LVSetAI, isCallInst );
 322       }
 323
 324
 325     } // for all machine instructions in BB
 326
 327   } // for all BBs in method
 328
 329
 330   // add interferences for method arguments. Since there are no explict
 331   // defs in method for args, we have to add them manually
 332   //
 333   addInterferencesForArgs();
 334
 335   if( DEBUG_RA)
 336     cout << "Interference graphs calculted!" << endl;
 337
 338 }
 339
 340
 341
 342 //--------------------------------------------------------------------------
 343 // Pseudo instructions will be exapnded to multiple instructions by the
 344 // assembler. Consequently, all the opernds must get distinct registers.
 345 // Therefore, we mark all operands of a pseudo instruction as they interfere
 346 // with one another.
 347 //--------------------------------------------------------------------------
 348 void PhyRegAlloc::addInterf4PseudoInstr(const MachineInstr *MInst) {
 349
 350   bool setInterf = false;
 351
 352   // iterate over  MI operands to find defs
 353   //
 354   for( MachineInstr::val_const_op_iterator It1(MInst);!It1.done(); ++It1) {
 355
 356     const LiveRange *const LROfOp1 = LRI.getLiveRangeForValue( *It1 );
 357
 358     if( !LROfOp1 && It1.isDef() )
 359       assert( 0 && "No LR for Def in PSEUDO insruction");
 360
 361     MachineInstr::val_const_op_iterator It2 = It1;
 362     ++It2;
 363
 364     for(  ; !It2.done(); ++It2) {
 365
 366       const LiveRange *const LROfOp2 = LRI.getLiveRangeForValue( *It2 );
 367
 368       if( LROfOp2) {
 369
 370         RegClass *const RCOfOp1 = LROfOp1->getRegClass();
 371         RegClass *const RCOfOp2 = LROfOp2->getRegClass();
 372
 373         if( RCOfOp1 == RCOfOp2 ){
 374           RCOfOp1->setInterference( LROfOp1, LROfOp2 );
 375           setInterf = true;
 376         }
 377
 378       } // if Op2 has a LR
 379
 380     } // for all other defs in machine instr
 381
 382   } // for all operands in an instruction
 383
 384   if( !setInterf && (MInst->getNumOperands() > 2) ) {
 385     cerr << "\nInterf not set for any operand in pseudo instr:\n";
 386     cerr << *MInst;
 387     assert(0 && "Interf not set for pseudo instr with > 2 operands" );
 388
 389   }
 390
 391 }
 392
 393
 394
 395 //----------------------------------------------------------------------------
 396 // This method will add interferences for incoming arguments to a method.
 397 //----------------------------------------------------------------------------
 398 void PhyRegAlloc::addInterferencesForArgs()
 399 {
 400                                               // get the InSet of root BB
 401   const LiveVarSet *const InSet = LVI->getInSetOfBB( Meth->front() );
 402
 403                                               // get the argument list
 404   const Method::ArgumentListType& ArgList = Meth->getArgumentList();
 405
 406                                               // get an iterator to arg list
 407   Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
 408
 409
 410   for( ; ArgIt != ArgList.end() ; ++ArgIt) {  // for each argument
 411     addInterference( *ArgIt, InSet, false );  // add interferences between
 412                                               // args and LVars at start
 413     if( DEBUG_RA > 1) {
 414        cout << " - %% adding interference for  argument ";
 415       printValue( (const Value *) *ArgIt); cout  << endl;
 416     }
 417   }
 418 }
 419
 420
 421
 422
 423 //----------------------------------------------------------------------------
 424 // This method is called after register allocation is complete to set the
 425 // allocated reisters in the machine code. This code will add register numbers
 426 // to MachineOperands that contain a Value. Also it calls target specific
 427 // methods to produce caller saving instructions. At the end, it adds all
 428 // additional instructions produced by the register allocator to the
 429 // instruction stream.
 430 //----------------------------------------------------------------------------
 431 void PhyRegAlloc::updateMachineCode()
 432 {
 433
 434   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 435
 436   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 437
 438     // get the iterator for machine instructions
 439     //
 440     MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 441     MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
 442
 443     // iterate over all the machine instructions in BB
 444     //
 445     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 446
 447       MachineInstr *MInst = *MInstIterator;
 448
 449       unsigned Opcode =  MInst->getOpCode();
 450
 451       // do not process Phis
 452       if( (TM.getInstrInfo()).isPhi( Opcode ) )
 453         continue;
 454
 455       // Now insert speical instructions (if necessary) for call/return
 456       // instructions.
 457       //
 458       if( (TM.getInstrInfo()).isCall( Opcode) ||
 459           (TM.getInstrInfo()).isReturn( Opcode)  ) {
 460
 461         AddedInstrns *AI = AddedInstrMap[ MInst];
 462         if ( !AI ) {
 463           AI = new AddedInstrns();
 464           AddedInstrMap[ MInst ] = AI;
 465         }
 466
 467         // Tmp stack poistions are needed by some calls that have spilled args
 468         // So reset it before we call each such method
 469         //
 470         mcInfo.popAllTempValues(TM);
 471
 472         if( (TM.getInstrInfo()).isCall( Opcode ) )
 473           MRI.colorCallArgs( MInst, LRI, AI, *this, *BBI );
 474
 475         else if (  (TM.getInstrInfo()).isReturn(Opcode) )
 476           MRI.colorRetValue( MInst, LRI, AI );
 477
 478       }
 479
 480
 481       /* -- Using above code instead of this
 482
 483       // if this machine instr is call, insert caller saving code
 484
 485       if( (TM.getInstrInfo()).isCall( MInst->getOpCode()) )
 486         MRI.insertCallerSavingCode(MInst,  *BBI, *this );
 487
 488       */
 489
 490
 491       // reset the stack offset for temporary variables since we may
 492       // need that to spill
 493       // mcInfo.popAllTempValues(TM);
 494       // TODO ** : do later
 495
 496       //for(MachineInstr::val_const_op_iterator OpI(MInst);!OpI.done();++OpI) {
 497
 498
 499       // Now replace set the registers for operands in the machine instruction
 500       //
 501       for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 502
 503         MachineOperand& Op = MInst->getOperand(OpNum);
 504
 505         if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 506             Op.getOperandType() ==  MachineOperand::MO_CCRegister) {
 507
 508           const Value *const Val =  Op.getVRegValue();
 509
 510           // delete this condition checking later (must assert if Val is null)
 511           if( !Val) {
 512             if (DEBUG_RA)
 513               cout << "Warning: NULL Value found for operand" << endl;
 514             continue;
 515           }
 516           assert( Val && "Value is NULL");
 517
 518           LiveRange *const LR = LRI.getLiveRangeForValue(Val);
 519
 520           if ( !LR ) {
 521
 522             // nothing to worry if it's a const or a label
 523
 524             if (DEBUG_RA) {
 525               cout << "*NO LR for operand : " << Op ;
 526               cout << " [reg:" <<  Op.getAllocatedRegNum() << "]";
 527               cout << " in inst:\t" << *MInst << endl;
 528             }
 529
 530             // if register is not allocated, mark register as invalid
 531             if( Op.getAllocatedRegNum() == -1)
 532               Op.setRegForValue( MRI.getInvalidRegNum());
 533
 534
 535             continue;
 536           }
 537
 538           unsigned RCID = (LR->getRegClass())->getID();
 539
 540           if( LR->hasColor() ) {
 541             Op.setRegForValue( MRI.getUnifiedRegNum(RCID, LR->getColor()) );
 542           }
 543           else {
 544
 545             // LR did NOT receive a color (register). Now, insert spill code
 546             // for spilled opeands in this machine instruction
 547
 548             //assert(0 && "LR must be spilled");
 549             insertCode4SpilledLR(LR, MInst, *BBI, OpNum );
 550
 551           }
 552         }
 553
 554       } // for each operand
 555
 556
 557       // Now add instructions that the register allocator inserts before/after
 558       // this machine instructions (done only for calls/rets/incoming args)
 559       // We do this here, to ensure that spill for an instruction is inserted
 560       // closest as possible to an instruction (see above insertCode4Spill...)
 561       //
 562       // If there are instructions to be added, *before* this machine
 563       // instruction, add them now.
 564       //
 565       if( AddedInstrMap[ MInst ] ) {
 566
 567         deque<MachineInstr *> &IBef = (AddedInstrMap[MInst])->InstrnsBefore;
 568
 569         if( ! IBef.empty() ) {
 570
 571           deque<MachineInstr *>::iterator AdIt;
 572
 573           for( AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt ) {
 574
 575             if( DEBUG_RA) {
 576               cerr << "For inst " << *MInst;
 577               cerr << " PREPENDed instr: " << **AdIt << endl;
 578             }
 579
 580             MInstIterator = MIVec.insert( MInstIterator, *AdIt );
 581             ++MInstIterator;
 582           }
 583
 584         }
 585
 586       }
 587
 588       // If there are instructions to be added *after* this machine
 589       // instruction, add them now
 590       //
 591       if( AddedInstrMap[ MInst ] &&
 592           ! (AddedInstrMap[ MInst ]->InstrnsAfter).empty() ) {
 593
 594         // if there are delay slots for this instruction, the instructions
 595         // added after it must really go after the delayed instruction(s)
 596         // So, we move the InstrAfter of the current instruction to the
 597         // corresponding delayed instruction
 598
 599         unsigned delay;
 600         if((delay=TM.getInstrInfo().getNumDelaySlots(MInst->getOpCode())) >0){
 601           move2DelayedInstr(MInst,  *(MInstIterator+delay) );
 602
 603           if(DEBUG_RA)  cout<< "\nMoved an added instr after the delay slot";
 604         }
 605
 606         else {
 607
 608
 609           // Here we can add the "instructions after" to the current
 610           // instruction since there are no delay slots for this instruction
 611
 612           deque<MachineInstr *> &IAft = (AddedInstrMap[MInst])->InstrnsAfter;
 613
 614           if( ! IAft.empty() ) {
 615
 616             deque<MachineInstr *>::iterator AdIt;
 617
 618             ++MInstIterator;   // advance to the next instruction
 619
 620             for( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt ) {
 621
 622               if(DEBUG_RA) {
 623                 cerr << "For inst " << *MInst;
 624                 cerr << " APPENDed instr: "  << **AdIt << endl;
 625               }
 626
 627               MInstIterator = MIVec.insert( MInstIterator, *AdIt );
 628               ++MInstIterator;
 629             }
 630
 631             // MInsterator already points to the next instr. Since the
 632             // for loop also increments it, decrement it to point to the
 633             // instruction added last
 634             --MInstIterator;
 635
 636           }
 637
 638         }  // if not delay
 639
 640       }
 641
 642     } // for each machine instruction
 643   }
 644 }
 645
 646
 647
 648 //----------------------------------------------------------------------------
 649 // This method inserts spill code for AN operand whose LR was spilled.
 650 // This method may be called several times for a single machine instruction
 651 // if it contains many spilled operands. Each time it is called, it finds
 652 // a register which is not live at that instruction and also which is not
 653 // used by other spilled operands of the same instruction. Then it uses
 654 // this register temporarily to accomodate the spilled value.
 655 //----------------------------------------------------------------------------
 656 void PhyRegAlloc::insertCode4SpilledLR(const LiveRange *LR,
 657                                        MachineInstr *MInst,
 658                                        const BasicBlock *BB,
 659                                        const unsigned OpNum) {
 660
 661   assert(! TM.getInstrInfo().isCall(MInst->getOpCode()) &&
 662          (! TM.getInstrInfo().isReturn(MInst->getOpCode())) &&
 663          "Arg of a call/ret must be handled elsewhere");
 664
 665   MachineOperand& Op = MInst->getOperand(OpNum);
 666   bool isDef =  MInst->operandIsDefined(OpNum);
 667   unsigned RegType = MRI.getRegType( LR );
 668   int SpillOff = LR->getSpillOffFromFP();
 669   RegClass *RC = LR->getRegClass();
 670   const LiveVarSet *LVSetBef =  LVI->getLiveVarSetBeforeMInst(MInst, BB);
 671
 672
 673   int TmpOff =
 674     mcInfo.pushTempValue(TM, MRI.getSpilledRegSize(RegType) );
 675
 676   MachineInstr *MIBef=NULL,  *AdIMid=NULL, *MIAft=NULL;
 677
 678   int TmpRegU = getUsableUniRegAtMI(RC, RegType, MInst,LVSetBef, MIBef, MIAft);
 679
 680   // get the added instructions for this instruciton
 681   AddedInstrns *AI = AddedInstrMap[ MInst ];
 682   if ( !AI ) {
 683     AI = new AddedInstrns();
 684     AddedInstrMap[ MInst ] = AI;
 685   }
 686
 687
 688   if( !isDef ) {
 689
 690     // for a USE, we have to load the value of LR from stack to a TmpReg
 691     // and use the TmpReg as one operand of instruction
 692
 693     // actual loading instruction
 694     AdIMid = MRI.cpMem2RegMI(MRI.getFramePointer(), SpillOff, TmpRegU,RegType);
 695
 696     if( MIBef )
 697       (AI->InstrnsBefore).push_back(MIBef);
 698
 699     (AI->InstrnsBefore).push_back(AdIMid);
 700
 701     if( MIAft)
 702       (AI->InstrnsAfter).push_front(MIAft);
 703
 704
 705   }
 706   else {   // if this is a Def
 707
 708     // for a DEF, we have to store the value produced by this instruction
 709     // on the stack position allocated for this LR
 710
 711     // actual storing instruction
 712     AdIMid = MRI.cpReg2MemMI(TmpRegU, MRI.getFramePointer(), SpillOff,RegType);
 713
 714     if( MIBef )
 715       (AI->InstrnsBefore).push_back(MIBef);
 716
 717     (AI->InstrnsAfter).push_front(AdIMid);
 718
 719     if( MIAft)
 720       (AI->InstrnsAfter).push_front(MIAft);
 721
 722   }  // if !DEF
 723
 724   cerr << "\nFor Inst " << *MInst;
 725   cerr << " - SPILLED LR: "; LR->printSet();
 726   cerr << "\n - Added Instructions:";
 727   if( MIBef ) cerr <<  *MIBef;
 728   cerr <<  *AdIMid;
 729   if( MIAft ) cerr <<  *MIAft;
 730
 731   Op.setRegForValue( TmpRegU );    // set the opearnd
 732
 733
 734 }
 735
 736
 737
 738
 739
 740
 741 //----------------------------------------------------------------------------
 742 // We can use the following method to get a temporary register to be used
 743 // BEFORE any given machine instruction. If there is a register available,
 744 // this method will simply return that register and set MIBef = MIAft = NULL.
 745 // Otherwise, it will return a register and MIAft and MIBef will contain
 746 // two instructions used to free up this returned register.
 747 // Returned register number is the UNIFIED register number
 748 //----------------------------------------------------------------------------
 749
 750 int PhyRegAlloc::getUsableUniRegAtMI(RegClass *RC,
 751                                   const int RegType,
 752                                   const MachineInstr *MInst,
 753                                   const LiveVarSet *LVSetBef,
 754                                   MachineInstr *MIBef,
 755                                   MachineInstr *MIAft) {
 756
 757   int RegU =  getUnusedUniRegAtMI(RC, MInst, LVSetBef);
 758
 759
 760   if( RegU != -1) {
 761     // we found an unused register, so we can simply use it
 762     MIBef = MIAft = NULL;
 763   }
 764   else {
 765     // we couldn't find an unused register. Generate code to free up a reg by
 766     // saving it on stack and restoring after the instruction
 767
 768     int TmpOff = mcInfo.pushTempValue(TM,  MRI.getSpilledRegSize(RegType) );
 769
 770     RegU = getUniRegNotUsedByThisInst(RC, MInst);
 771     MIBef = MRI.cpReg2MemMI(RegU, MRI.getFramePointer(), TmpOff, RegType );
 772     MIAft = MRI.cpMem2RegMI(MRI.getFramePointer(), TmpOff, RegU, RegType );
 773   }
 774
 775   return RegU;
 776 }
 777
 778 //----------------------------------------------------------------------------
 779 // This method is called to get a new unused register that can be used to
 780 // accomodate a spilled value.
 781 // This method may be called several times for a single machine instruction
 782 // if it contains many spilled operands. Each time it is called, it finds
 783 // a register which is not live at that instruction and also which is not
 784 // used by other spilled operands of the same instruction.
 785 // Return register number is relative to the register class. NOT
 786 // unified number
 787 //----------------------------------------------------------------------------
 788 int PhyRegAlloc::getUnusedUniRegAtMI(RegClass *RC,
 789                                   const MachineInstr *MInst,
 790                                   const LiveVarSet *LVSetBef) {
 791
 792   unsigned NumAvailRegs =  RC->getNumOfAvailRegs();
 793
 794   bool *IsColorUsedArr = RC->getIsColorUsedArr();
 795
 796   for(unsigned i=0; i <  NumAvailRegs; i++)     // Reset array
 797       IsColorUsedArr[i] = false;
 798
 799   LiveVarSet::const_iterator LIt = LVSetBef->begin();
 800
 801   // for each live var in live variable set after machine inst
 802   for( ; LIt != LVSetBef->end(); ++LIt) {
 803
 804    //  get the live range corresponding to live var
 805     LiveRange *const LRofLV = LRI.getLiveRangeForValue(*LIt );
 806
 807     // LR can be null if it is a const since a const
 808     // doesn't have a dominating def - see Assumptions above
 809     if( LRofLV )
 810       if( LRofLV->hasColor() )
 811         IsColorUsedArr[ LRofLV->getColor() ] = true;
 812   }
 813
 814   // It is possible that one operand of this MInst was already spilled
 815   // and it received some register temporarily. If that's the case,
 816   // it is recorded in machine operand. We must skip such registers.
 817
 818   setRelRegsUsedByThisInst(RC, MInst);
 819
 820   unsigned c;                         // find first unused color
 821   for( c=0; c < NumAvailRegs; c++)
 822      if( ! IsColorUsedArr[ c ] ) break;
 823
 824   if(c < NumAvailRegs)
 825     return  MRI.getUnifiedRegNum(RC->getID(), c);
 826   else
 827     return -1;
 828
 829
 830 }
 831
 832
 833 //----------------------------------------------------------------------------
 834 // Get any other register in a register class, other than what is used
 835 // by operands of a machine instruction. Returns the unified reg number.
 836 //----------------------------------------------------------------------------
 837 int PhyRegAlloc::getUniRegNotUsedByThisInst(RegClass *RC,
 838                                          const MachineInstr *MInst) {
 839
 840   bool *IsColorUsedArr = RC->getIsColorUsedArr();
 841   unsigned NumAvailRegs =  RC->getNumOfAvailRegs();
 842
 843
 844   for(unsigned i=0; i < NumAvailRegs ; i++)   // Reset array
 845     IsColorUsedArr[i] = false;
 846
 847   setRelRegsUsedByThisInst(RC, MInst);
 848
 849   unsigned c;                         // find first unused color
 850   for( c=0; c <  RC->getNumOfAvailRegs(); c++)
 851      if( ! IsColorUsedArr[ c ] ) break;
 852
 853   if(c < NumAvailRegs)
 854     return  MRI.getUnifiedRegNum(RC->getID(), c);
 855   else
 856     assert( 0 && "FATAL: No free register could be found in reg class!!");
 857
 858 }
 859
 860
 861
 862
 863
 864 //----------------------------------------------------------------------------
 865 // This method modifies the IsColorUsedArr of the register class passed to it.
 866 // It sets the bits corresponding to the registers used by this machine
 867 // instructions. Both explicit and implicit operands are set.
 868 //----------------------------------------------------------------------------
 869 void PhyRegAlloc::setRelRegsUsedByThisInst(RegClass *RC,
 870                                        const MachineInstr *MInst ) {
 871
 872  bool *IsColorUsedArr = RC->getIsColorUsedArr();
 873
 874  for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 875
 876    const MachineOperand& Op = MInst->getOperand(OpNum);
 877
 878     if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 879         Op.getOperandType() ==  MachineOperand::MO_CCRegister ) {
 880
 881       const Value *const Val =  Op.getVRegValue();
 882
 883       if( Val )
 884         if( MRI.getRegClassIDOfValue(Val) == RC->getID() ) {
 885           int Reg;
 886           if( (Reg=Op.getAllocatedRegNum()) != -1) {
 887             IsColorUsedArr[ Reg ] = true;
 888           }
 889           else {
 890             // it is possilbe that this operand still is not marked with
 891             // a register but it has a LR and that received a color
 892
 893             LiveRange *LROfVal =  LRI.getLiveRangeForValue(Val);
 894             if( LROfVal)
 895               if( LROfVal->hasColor() )
 896                 IsColorUsedArr[ LROfVal->getColor() ] = true;
 897           }
 898
 899         } // if reg classes are the same
 900     }
 901     else if (Op.getOperandType() ==  MachineOperand::MO_MachineRegister) {
 902       IsColorUsedArr[ Op.getMachineRegNum() ] = true;
 903     }
 904  }
 905
 906  // If there are implicit references, mark them as well
 907
 908  for(unsigned z=0; z < MInst->getNumImplicitRefs(); z++) {
 909
 910    LiveRange *const LRofImpRef =
 911      LRI.getLiveRangeForValue( MInst->getImplicitRef(z)  );
 912
 913    if( LRofImpRef )
 914      if( LRofImpRef->hasColor() )
 915        IsColorUsedArr[ LRofImpRef->getColor() ] = true;
 916  }
 917
 918
 919
 920 }
 921
 922
 923
 924
 925
 926
 927
 928
 929 //----------------------------------------------------------------------------
 930 // If there are delay slots for an instruction, the instructions
 931 // added after it must really go after the delayed instruction(s).
 932 // So, we move the InstrAfter of that instruction to the
 933 // corresponding delayed instruction using the following method.
 934
 935 //----------------------------------------------------------------------------
 936 void PhyRegAlloc:: move2DelayedInstr(const MachineInstr *OrigMI,
 937                                      const MachineInstr *DelayedMI) {
 938
 939
 940   // "added after" instructions of the original instr
 941   deque<MachineInstr *> &OrigAft = (AddedInstrMap[OrigMI])->InstrnsAfter;
 942
 943   // "added instructions" of the delayed instr
 944   AddedInstrns *DelayAdI = AddedInstrMap[DelayedMI];
 945
 946   if(! DelayAdI )  {                // create a new "added after" if necessary
 947     DelayAdI = new AddedInstrns();
 948     AddedInstrMap[DelayedMI] =  DelayAdI;
 949   }
 950
 951   // "added after" instructions of the delayed instr
 952   deque<MachineInstr *> &DelayedAft = DelayAdI->InstrnsAfter;
 953
 954   // go thru all the "added after instructions" of the original instruction
 955   // and append them to the "addded after instructions" of the delayed
 956   // instructions
 957
 958   deque<MachineInstr *>::iterator OrigAdIt;
 959
 960   for( OrigAdIt = OrigAft.begin(); OrigAdIt != OrigAft.end() ; ++OrigAdIt ) {
 961     DelayedAft.push_back( *OrigAdIt );
 962   }
 963
 964   // empty the "added after instructions" of the original instruction
 965   OrigAft.clear();
 966
 967 }
 968
 969 //----------------------------------------------------------------------------
 970 // This method prints the code with registers after register allocation is
 971 // complete.
 972 //----------------------------------------------------------------------------
 973 void PhyRegAlloc::printMachineCode()
 974 {
 975
 976   cout << endl << ";************** Method ";
 977   cout << Meth->getName() << " *****************" << endl;
 978
 979   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 980
 981   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 982
 983     cout << endl ; printLabel( *BBI); cout << ": ";
 984
 985     // get the iterator for machine instructions
 986     MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 987     MachineCodeForBasicBlock::iterator MInstIterator = MIVec.begin();
 988
 989     // iterate over all the machine instructions in BB
 990     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 991
 992       MachineInstr *const MInst = *MInstIterator;
 993
 994
 995       cout << endl << "\t";
 996       cout << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
 997
 998
 999       //for(MachineInstr::val_const_op_iterator OpI(MInst);!OpI.done();++OpI) {
1000
1001       for(unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
1002
1003         MachineOperand& Op = MInst->getOperand(OpNum);
1004
1005         if( Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
1006             Op.getOperandType() ==  MachineOperand::MO_CCRegister /*||
1007             Op.getOperandType() ==  MachineOperand::MO_PCRelativeDisp*/ ) {
1008
1009           const Value *const Val = Op.getVRegValue () ;
1010           // ****this code is temporary till NULL Values are fixed
1011           if( ! Val ) {
1012             cout << "\t<*NULL*>";
1013             continue;
1014           }
1015
1016           // if a label or a constant
1017           if( (Val->getValueType() == Value::BasicBlockVal)  ) {
1018
1019             cout << "\t"; printLabel(   Op.getVRegValue () );
1020           }
1021           else {
1022             // else it must be a register value
1023             const int RegNum = Op.getAllocatedRegNum();
1024
1025             cout << "\t" << "%" << MRI.getUnifiedRegName( RegNum );
1026             if (Val->hasName() )
1027               cout << "(" << Val->getName() << ")";
1028             else
1029               cout << "(" << Val << ")";
1030
1031             if( Op.opIsDef() )
1032               cout << "*";
1033
1034             const LiveRange *LROfVal = LRI.getLiveRangeForValue(Val);
1035             if( LROfVal )
1036               if( LROfVal->hasSpillOffset() )
1037                 cout << "$";
1038           }
1039
1040         }
1041         else if(Op.getOperandType() ==  MachineOperand::MO_MachineRegister) {
1042           cout << "\t" << "%" << MRI.getUnifiedRegName(Op.getMachineRegNum());
1043         }
1044
1045         else
1046           cout << "\t" << Op;      // use dump field
1047       }
1048
1049
1050
1051       unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
1052       if(  NumOfImpRefs > 0 ) {
1053
1054         cout << "\tImplicit:";
1055
1056         for(unsigned z=0; z < NumOfImpRefs; z++) {
1057           printValue(  MInst->getImplicitRef(z) );
1058           cout << "\t";
1059         }
1060
1061       }
1062
1063     } // for all machine instructions
1064
1065
1066     cout << endl;
1067
1068   } // for all BBs
1069
1070   cout << endl;
1071 }
1072
1073
1074 #if 0
1075
1076 //----------------------------------------------------------------------------
1077 //
1078 //----------------------------------------------------------------------------
1079
1080 void PhyRegAlloc::colorCallRetArgs()
1081 {
1082
1083   CallRetInstrListType &CallRetInstList = LRI.getCallRetInstrList();
1084   CallRetInstrListType::const_iterator It = CallRetInstList.begin();
1085
1086   for( ; It != CallRetInstList.end(); ++It ) {
1087
1088     const MachineInstr *const CRMI = *It;
1089     unsigned OpCode =  CRMI->getOpCode();
1090
1091     // get the added instructions for this Call/Ret instruciton
1092     AddedInstrns *AI = AddedInstrMap[ CRMI ];
1093     if ( !AI ) {
1094       AI = new AddedInstrns();
1095       AddedInstrMap[ CRMI ] = AI;
1096     }
1097
1098     // Tmp stack poistions are needed by some calls that have spilled args
1099     // So reset it before we call each such method
1100     //mcInfo.popAllTempValues(TM);
1101
1102
1103
1104     if( (TM.getInstrInfo()).isCall( OpCode ) )
1105       MRI.colorCallArgs( CRMI, LRI, AI, *this );
1106
1107     else if (  (TM.getInstrInfo()).isReturn(OpCode) )
1108       MRI.colorRetValue( CRMI, LRI, AI );
1109
1110     else assert( 0 && "Non Call/Ret instrn in CallRetInstrList\n" );
1111
1112   }
1113
1114 }
1115
1116 #endif
1117
1118 //----------------------------------------------------------------------------
1119
1120 //----------------------------------------------------------------------------
1121 void PhyRegAlloc::colorIncomingArgs()
1122 {
1123   const BasicBlock *const FirstBB = Meth->front();
1124   const MachineInstr *FirstMI = *((FirstBB->getMachineInstrVec()).begin());
1125   assert( FirstMI && "No machine instruction in entry BB");
1126
1127   AddedInstrns *AI = AddedInstrMap[ FirstMI ];
1128   if ( !AI ) {
1129     AI = new AddedInstrns();
1130     AddedInstrMap[ FirstMI  ] = AI;
1131   }
1132
1133   MRI.colorMethodArgs(Meth, LRI, AI );
1134 }
1135
1136
1137 //----------------------------------------------------------------------------
1138 // Used to generate a label for a basic block
1139 //----------------------------------------------------------------------------
1140 void PhyRegAlloc::printLabel(const Value *const Val)
1141 {
1142   if( Val->hasName() )
1143     cout  << Val->getName();
1144   else
1145     cout << "Label" <<  Val;
1146 }
1147
1148
1149 //----------------------------------------------------------------------------
1150 // This method calls setSugColorUsable method of each live range. This
1151 // will determine whether the suggested color of LR is  really usable.
1152 // A suggested color is not usable when the suggested color is volatile
1153 // AND when there are call interferences
1154 //----------------------------------------------------------------------------
1155
1156 void PhyRegAlloc::markUnusableSugColors()
1157 {
1158   if(DEBUG_RA ) cout << "\nmarking unusable suggested colors ..." << endl;
1159
1160   // hash map iterator
1161   LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
1162   LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
1163
1164     for(  ; HMI != HMIEnd ; ++HMI ) {
1165
1166       if( (*HMI).first ) {
1167
1168         LiveRange *L = (*HMI).second;      // get the LiveRange
1169
1170         if(L) {
1171           if( L->hasSuggestedColor() ) {
1172
1173             int RCID = (L->getRegClass())->getID();
1174             if( MRI.isRegVolatile( RCID,  L->getSuggestedColor()) &&
1175                 L->isCallInterference() )
1176               L->setSuggestedColorUsable( false );
1177             else
1178               L->setSuggestedColorUsable( true );
1179           }
1180         } // if L->hasSuggestedColor()
1181       }
1182     } // for all LR's in hash map
1183 }
1184
1185
1186
1187 //----------------------------------------------------------------------------
1188 // The following method will set the stack offsets of the live ranges that
1189 // are decided to be spillled. This must be called just after coloring the
1190 // LRs using the graph coloring algo. For each live range that is spilled,
1191 // this method allocate a new spill position on the stack.
1192 //----------------------------------------------------------------------------
1193
1194 void PhyRegAlloc::allocateStackSpace4SpilledLRs()
1195 {
1196   if(DEBUG_RA ) cout << "\nsetting LR stack offsets ..." << endl;
1197
1198   // hash map iterator
1199   LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
1200   LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
1201
1202     for(  ; HMI != HMIEnd ; ++HMI ) {
1203       if( (*HMI).first ) {
1204         LiveRange *L = (*HMI).second;      // get the LiveRange
1205         if(L)
1206           if( ! L->hasColor() )
1207
1208             //  NOTE: ** allocating the size of long Type **
1209             L->setSpillOffFromFP(mcInfo.allocateSpilledValue(TM,
1210                                  Type::LongTy));
1211
1212       }
1213     } // for all LR's in hash map
1214 }
1215
1216
1217
1218 //----------------------------------------------------------------------------
1219 // The entry pont to Register Allocation
1220 //----------------------------------------------------------------------------
1221
1222 void PhyRegAlloc::allocateRegisters()
1223 {
1224
1225   // make sure that we put all register classes into the RegClassList
1226   // before we call constructLiveRanges (now done in the constructor of
1227   // PhyRegAlloc class).
1228   //
1229   LRI.constructLiveRanges();            // create LR info
1230
1231   if( DEBUG_RA )
1232     LRI.printLiveRanges();
1233
1234   createIGNodeListsAndIGs();            // create IGNode list and IGs
1235
1236   buildInterferenceGraphs();            // build IGs in all reg classes
1237
1238
1239   if( DEBUG_RA ) {
1240     // print all LRs in all reg classes
1241     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)
1242       RegClassList[ rc ]->printIGNodeList();
1243
1244     // print IGs in all register classes
1245     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
1246       RegClassList[ rc ]->printIG();
1247   }
1248
1249
1250   LRI.coalesceLRs();                    // coalesce all live ranges
1251
1252
1253   if( DEBUG_RA) {
1254     // print all LRs in all reg classes
1255     for( unsigned int rc=0; rc < NumOfRegClasses  ; rc++)
1256       RegClassList[ rc ]->printIGNodeList();
1257
1258     // print IGs in all register classes
1259     for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
1260       RegClassList[ rc ]->printIG();
1261   }
1262
1263
1264   // mark un-usable suggested color before graph coloring algorithm.
1265   // When this is done, the graph coloring algo will not reserve
1266   // suggested color unnecessarily - they can be used by another LR
1267   //
1268   markUnusableSugColors();
1269
1270   // color all register classes using the graph coloring algo
1271   for( unsigned int rc=0; rc < NumOfRegClasses ; rc++)
1272     RegClassList[ rc ]->colorAllRegs();
1273
1274   // Atter grpah coloring, if some LRs did not receive a color (i.e, spilled)
1275   // a poistion for such spilled LRs
1276   //
1277   allocateStackSpace4SpilledLRs();
1278
1279   mcInfo.popAllTempValues(TM);  // TODO **Check
1280
1281   // color incoming args - if the correct color was not received
1282   // insert code to copy to the correct register
1283   //
1284   colorIncomingArgs();
1285
1286
1287   // Now update the machine code with register names and add any
1288   // additional code inserted by the register allocator to the instruction
1289   // stream
1290   //
1291   updateMachineCode();
1292
1293
1294   if (DEBUG_RA) {
1295     MachineCodeForMethod::get(Meth).dump();
1296     printMachineCode();                   // only for DEBUGGING
1297   }
1298
1299 }
1300
1301
1302