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