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