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