lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp

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