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