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