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