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