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