lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp

   1 //***************************************************************************
   2 // File:
   3 //      PhyRegAlloc.cpp
   4 //
   5 // Purpose:
   6 //      Register allocation for LLVM.
   7 //
   8 // History:
   9 //      9/10/01  -  Ruchira Sasanka - created.
  10 //**************************************************************************/
  11
  12 #include "llvm/CodeGen/RegisterAllocation.h"
  13 #include "llvm/CodeGen/PhyRegAlloc.h"
  14 #include "llvm/CodeGen/MachineInstr.h"
  15 #include "llvm/CodeGen/MachineInstrAnnot.h"
  16 #include "llvm/CodeGen/MachineCodeForMethod.h"
  17 #include "llvm/Analysis/LiveVar/FunctionLiveVarInfo.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 "llvm/iOther.h"
  25 #include "llvm/CodeGen/RegAllocCommon.h"
  26 #include "Support/CommandLine.h"
  27 #include <iostream>
  28 #include <math.h>
  29 using std::cerr;
  30 using std::vector;
  31
  32 RegAllocDebugLevel_t DEBUG_RA;
  33 static cl::Enum<RegAllocDebugLevel_t> DEBUG_RA_c(DEBUG_RA, "dregalloc",
  34                                                  cl::Hidden,
  35   "enable register allocation debugging information",
  36   clEnumValN(RA_DEBUG_None   , "n", "disable debug output"),
  37   clEnumValN(RA_DEBUG_Normal , "y", "enable debug output"),
  38   clEnumValN(RA_DEBUG_Verbose, "v", "enable extra debug output"), 0);
  39
  40
  41 //----------------------------------------------------------------------------
  42 // RegisterAllocation pass front end...
  43 //----------------------------------------------------------------------------
  44 namespace {
  45   class RegisterAllocator : public FunctionPass {
  46     TargetMachine &Target;
  47   public:
  48     inline RegisterAllocator(TargetMachine &T) : Target(T) {}
  49
  50     const char *getPassName() const { return "Register Allocation"; }
  51
  52     bool runOnFunction(Function &F) {
  53       if (DEBUG_RA)
  54         cerr << "\n********* Function "<< F.getName() << " ***********\n";
  55
  56       PhyRegAlloc PRA(&F, Target, &getAnalysis<FunctionLiveVarInfo>(),
  57                       &getAnalysis<LoopInfo>());
  58       PRA.allocateRegisters();
  59
  60       if (DEBUG_RA) cerr << "\nRegister allocation complete!\n";
  61       return false;
  62     }
  63
  64     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  65       AU.addRequired(LoopInfo::ID);
  66       AU.addRequired(FunctionLiveVarInfo::ID);
  67     }
  68   };
  69 }
  70
  71 Pass *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, const TargetMachine& tm,
  79                          FunctionLiveVarInfo *Lvi, LoopInfo *LDC)
  80                        :  TM(tm), Meth(F),
  81                           mcInfo(MachineCodeForMethod::get(F)),
  82                           LVI(Lvi), LRI(F, tm, RegClassList),
  83                           MRI(tm.getRegInfo()),
  84                           NumOfRegClasses(MRI.getNumOfRegClasses()),
  85                           LoopDepthCalc(LDC) {
  86
  87   // create each RegisterClass and put in RegClassList
  88   //
  89   for (unsigned rc=0; rc < NumOfRegClasses; rc++)
  90     RegClassList.push_back(new RegClass(F, MRI.getMachineRegClass(rc),
  91                                         &ResColList));
  92 }
  93
  94
  95 //----------------------------------------------------------------------------
  96 // Destructor: Deletes register classes
  97 //----------------------------------------------------------------------------
  98 PhyRegAlloc::~PhyRegAlloc() {
  99   for ( unsigned rc=0; rc < NumOfRegClasses; rc++)
 100     delete RegClassList[rc];
 101
 102   AddedInstrMap.clear();
 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 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   CallArgsDescriptor* argDesc = CallArgsDescriptor::get(MInst);
 252
 253   if (const Value *RetVal = argDesc->getReturnValue()) {
 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 = argDesc->getIndirectFuncPtr()) {
 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   for (Function::const_aiterator AI = Meth->abegin(); AI != Meth->aend(); ++AI) {
 414     // add interferences between args and LVars at start
 415     addInterference(AI, &InSet, false);
 416
 417     if (DEBUG_RA > 1)
 418       cerr << " - %% adding interference for  argument " << RAV(AI) << "\n";
 419   }
 420 }
 421
 422
 423 //----------------------------------------------------------------------------
 424 // This method is called after register allocation is complete to set the
 425 // allocated reisters in the machine code. This code will add register numbers
 426 // to MachineOperands that contain a Value. Also it calls target specific
 427 // methods to produce caller saving instructions. At the end, it adds all
 428 // additional instructions produced by the register allocator to the
 429 // instruction stream.
 430 //----------------------------------------------------------------------------
 431
 432 //-----------------------------
 433 // Utility functions used below
 434 //-----------------------------
 435 inline void
 436 PrependInstructions(vector<MachineInstr *> &IBef,
 437                     MachineCodeForBasicBlock& MIVec,
 438                     MachineCodeForBasicBlock::iterator& MII,
 439                     const std::string& msg)
 440 {
 441   if (!IBef.empty())
 442     {
 443       MachineInstr* OrigMI = *MII;
 444       std::vector<MachineInstr *>::iterator AdIt;
 445       for (AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt)
 446         {
 447           if (DEBUG_RA) {
 448             if (OrigMI) cerr << "For MInst: " << *OrigMI;
 449             cerr << msg << " PREPENDed instr: " << **AdIt << "\n";
 450           }
 451           MII = MIVec.insert(MII, *AdIt);
 452           ++MII;
 453         }
 454     }
 455 }
 456
 457 inline void
 458 AppendInstructions(std::vector<MachineInstr *> &IAft,
 459                    MachineCodeForBasicBlock& MIVec,
 460                    MachineCodeForBasicBlock::iterator& MII,
 461                    const std::string& msg)
 462 {
 463   if (!IAft.empty())
 464     {
 465       MachineInstr* OrigMI = *MII;
 466       std::vector<MachineInstr *>::iterator AdIt;
 467       for ( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt )
 468         {
 469           if (DEBUG_RA) {
 470             if (OrigMI) cerr << "For MInst: " << *OrigMI;
 471             cerr << msg << " APPENDed instr: "  << **AdIt << "\n";
 472           }
 473           ++MII;    // insert before the next instruction
 474           MII = MIVec.insert(MII, *AdIt);
 475         }
 476     }
 477 }
 478
 479
 480 void PhyRegAlloc::updateMachineCode()
 481 {
 482   MachineCodeForBasicBlock& MIVec = Meth->getEntryNode().getMachineInstrVec();
 483
 484   // Insert any instructions needed at method entry
 485   MachineCodeForBasicBlock::iterator MII = MIVec.begin();
 486   PrependInstructions(AddedInstrAtEntry.InstrnsBefore, MIVec, MII,
 487                       "At function entry: \n");
 488   assert(AddedInstrAtEntry.InstrnsAfter.empty() &&
 489          "InstrsAfter should be unnecessary since we are just inserting at "
 490          "the function entry point here.");
 491
 492   for (Function::const_iterator BBI = Meth->begin(), BBE = Meth->end();
 493        BBI != BBE; ++BBI) {
 494
 495     // iterate over all the machine instructions in BB
 496     MachineCodeForBasicBlock &MIVec = BBI->getMachineInstrVec();
 497     for (MachineCodeForBasicBlock::iterator MII = MIVec.begin();
 498         MII != MIVec.end(); ++MII) {
 499
 500       MachineInstr *MInst = *MII;
 501
 502       unsigned Opcode =  MInst->getOpCode();
 503
 504       // do not process Phis
 505       if (TM.getInstrInfo().isDummyPhiInstr(Opcode))
 506         continue;
 507
 508       // Now insert speical instructions (if necessary) for call/return
 509       // instructions.
 510       //
 511       if (TM.getInstrInfo().isCall(Opcode) ||
 512           TM.getInstrInfo().isReturn(Opcode)) {
 513
 514         AddedInstrns &AI = AddedInstrMap[MInst];
 515
 516         // Tmp stack poistions are needed by some calls that have spilled args
 517         // So reset it before we call each such method
 518         //
 519         mcInfo.popAllTempValues(TM);
 520
 521         if (TM.getInstrInfo().isCall(Opcode))
 522           MRI.colorCallArgs(MInst, LRI, &AI, *this, BBI);
 523         else if (TM.getInstrInfo().isReturn(Opcode))
 524           MRI.colorRetValue(MInst, LRI, &AI);
 525       }
 526
 527
 528       /* -- Using above code instead of this
 529
 530       // if this machine instr is call, insert caller saving code
 531
 532       if ((TM.getInstrInfo()).isCall( MInst->getOpCode()) )
 533         MRI.insertCallerSavingCode(MInst,  *BBI, *this );
 534
 535       */
 536
 537
 538       // reset the stack offset for temporary variables since we may
 539       // need that to spill
 540       // mcInfo.popAllTempValues(TM);
 541       // TODO ** : do later
 542
 543       //for (MachineInstr::val_const_op_iterator OpI(MInst);!OpI.done();++OpI) {
 544
 545
 546       // Now replace set the registers for operands in the machine instruction
 547       //
 548       for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 549
 550         MachineOperand& Op = MInst->getOperand(OpNum);
 551
 552         if (Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 553             Op.getOperandType() ==  MachineOperand::MO_CCRegister) {
 554
 555           const Value *const Val =  Op.getVRegValue();
 556
 557           // delete this condition checking later (must assert if Val is null)
 558           if (!Val) {
 559             if (DEBUG_RA)
 560               cerr << "Warning: NULL Value found for operand\n";
 561             continue;
 562           }
 563           assert( Val && "Value is NULL");
 564
 565           LiveRange *const LR = LRI.getLiveRangeForValue(Val);
 566
 567           if (!LR ) {
 568
 569             // nothing to worry if it's a const or a label
 570
 571             if (DEBUG_RA) {
 572               cerr << "*NO LR for operand : " << Op ;
 573               cerr << " [reg:" <<  Op.getAllocatedRegNum() << "]";
 574               cerr << " in inst:\t" << *MInst << "\n";
 575             }
 576
 577             // if register is not allocated, mark register as invalid
 578             if (Op.getAllocatedRegNum() == -1)
 579               Op.setRegForValue( MRI.getInvalidRegNum());
 580
 581
 582             continue;
 583           }
 584
 585           unsigned RCID = (LR->getRegClass())->getID();
 586
 587           if (LR->hasColor() ) {
 588             Op.setRegForValue( MRI.getUnifiedRegNum(RCID, LR->getColor()) );
 589           }
 590           else {
 591
 592             // LR did NOT receive a color (register). Now, insert spill code
 593             // for spilled opeands in this machine instruction
 594
 595             //assert(0 && "LR must be spilled");
 596             insertCode4SpilledLR(LR, MInst, BBI, OpNum );
 597
 598           }
 599         }
 600
 601       } // for each operand
 602
 603
 604       // Now add instructions that the register allocator inserts before/after
 605       // this machine instructions (done only for calls/rets/incoming args)
 606       // We do this here, to ensure that spill for an instruction is inserted
 607       // closest as possible to an instruction (see above insertCode4Spill...)
 608       //
 609       // If there are instructions to be added, *before* this machine
 610       // instruction, add them now.
 611       //
 612       if (AddedInstrMap.count(MInst)) {
 613         PrependInstructions(AddedInstrMap[MInst].InstrnsBefore, MIVec, MII,"");
 614       }
 615
 616       // If there are instructions to be added *after* this machine
 617       // instruction, add them now
 618       //
 619       if (!AddedInstrMap[MInst].InstrnsAfter.empty()) {
 620
 621         // if there are delay slots for this instruction, the instructions
 622         // added after it must really go after the delayed instruction(s)
 623         // So, we move the InstrAfter of the current instruction to the
 624         // corresponding delayed instruction
 625
 626         unsigned delay;
 627         if ((delay=TM.getInstrInfo().getNumDelaySlots(MInst->getOpCode())) >0){
 628           move2DelayedInstr(MInst,  *(MII+delay) );
 629
 630           if (DEBUG_RA)  cerr<< "\nMoved an added instr after the delay slot";
 631         }
 632
 633         else {
 634           // Here we can add the "instructions after" to the current
 635           // instruction since there are no delay slots for this instruction
 636           AppendInstructions(AddedInstrMap[MInst].InstrnsAfter, MIVec, MII,"");
 637         }  // if not delay
 638
 639       }
 640
 641     } // for each machine instruction
 642   }
 643 }
 644
 645
 646
 647 //----------------------------------------------------------------------------
 648 // This method inserts spill code for AN operand whose LR was spilled.
 649 // This method may be called several times for a single machine instruction
 650 // if it contains many spilled operands. Each time it is called, it finds
 651 // a register which is not live at that instruction and also which is not
 652 // used by other spilled operands of the same instruction. Then it uses
 653 // this register temporarily to accomodate the spilled value.
 654 //----------------------------------------------------------------------------
 655 void PhyRegAlloc::insertCode4SpilledLR(const LiveRange *LR,
 656                                        MachineInstr *MInst,
 657                                        const BasicBlock *BB,
 658                                        const unsigned OpNum) {
 659
 660   assert(! TM.getInstrInfo().isCall(MInst->getOpCode()) &&
 661          (! TM.getInstrInfo().isReturn(MInst->getOpCode())) &&
 662          "Arg of a call/ret must be handled elsewhere");
 663
 664   MachineOperand& Op = MInst->getOperand(OpNum);
 665   bool isDef =  MInst->operandIsDefined(OpNum);
 666   unsigned RegType = MRI.getRegType( LR );
 667   int SpillOff = LR->getSpillOffFromFP();
 668   RegClass *RC = LR->getRegClass();
 669   const ValueSet &LVSetBef = LVI->getLiveVarSetBeforeMInst(MInst, BB);
 670
 671   mcInfo.pushTempValue(TM, MRI.getSpilledRegSize(RegType) );
 672
 673   MachineInstr *MIBef=NULL, *MIAft=NULL;
 674   vector<MachineInstr*> AdIMid;
 675
 676   int TmpRegU = getUsableUniRegAtMI(RC, RegType, MInst,&LVSetBef, MIBef, MIAft);
 677
 678   // get the added instructions for this instruciton
 679   AddedInstrns &AI = AddedInstrMap[MInst];
 680
 681   if (!isDef) {
 682     // for a USE, we have to load the value of LR from stack to a TmpReg
 683     // and use the TmpReg as one operand of instruction
 684
 685     // actual loading instruction
 686     MRI.cpMem2RegMI(MRI.getFramePointer(), SpillOff, TmpRegU,RegType, AdIMid);
 687     AI.InstrnsBefore.insert(AI.InstrnsBefore.end(),
 688                             AdIMid.begin(), AdIMid.end());
 689
 690     if (MIBef)
 691       AI.InstrnsBefore.push_back(MIBef);
 692
 693     if (MIAft)
 694       AI.InstrnsAfter.insert(AI.InstrnsAfter.begin(), MIAft);
 695
 696   } else {   // if this is a Def
 697     // for a DEF, we have to store the value produced by this instruction
 698     // on the stack position allocated for this LR
 699
 700     // actual storing instruction
 701     MRI.cpReg2MemMI(TmpRegU, MRI.getFramePointer(), SpillOff,RegType, AdIMid);
 702
 703     if (MIBef)
 704       AI.InstrnsBefore.push_back(MIBef);
 705
 706     AI.InstrnsAfter.insert(AI.InstrnsAfter.begin(),
 707                            AdIMid.begin(), AdIMid.end());
 708
 709     if (MIAft)
 710       AI.InstrnsAfter.insert(AI.InstrnsAfter.begin(), MIAft);
 711
 712   }  // if !DEF
 713
 714   if (DEBUG_RA) {
 715     cerr << "\nFor Inst " << *MInst;
 716     cerr << " - SPILLED LR: "; printSet(*LR);
 717     cerr << "\n - Added Instructions:";
 718     if (MIBef) cerr <<  *MIBef;
 719     for (vector<MachineInstr*>::const_iterator II=AdIMid.begin();
 720          II != AdIMid.end(); ++II)
 721       cerr <<  **II;
 722     if (MIAft) cerr <<  *MIAft;
 723   }
 724
 725   Op.setRegForValue(TmpRegU);    // set the opearnd
 726 }
 727
 728
 729
 730 //----------------------------------------------------------------------------
 731 // We can use the following method to get a temporary register to be used
 732 // BEFORE any given machine instruction. If there is a register available,
 733 // this method will simply return that register and set MIBef = MIAft = NULL.
 734 // Otherwise, it will return a register and MIAft and MIBef will contain
 735 // two instructions used to free up this returned register.
 736 // Returned register number is the UNIFIED register number
 737 //----------------------------------------------------------------------------
 738
 739 int PhyRegAlloc::getUsableUniRegAtMI(RegClass *RC,
 740                                   const int RegType,
 741                                   const MachineInstr *MInst,
 742                                   const ValueSet *LVSetBef,
 743                                   MachineInstr *&MIBef,
 744                                   MachineInstr *&MIAft) {
 745
 746   int RegU =  getUnusedUniRegAtMI(RC, MInst, LVSetBef);
 747
 748
 749   if (RegU != -1) {
 750     // we found an unused register, so we can simply use it
 751     MIBef = MIAft = NULL;
 752   }
 753   else {
 754     // we couldn't find an unused register. Generate code to free up a reg by
 755     // saving it on stack and restoring after the instruction
 756
 757     int TmpOff = mcInfo.pushTempValue(TM,  MRI.getSpilledRegSize(RegType) );
 758
 759     RegU = getUniRegNotUsedByThisInst(RC, MInst);
 760
 761     vector<MachineInstr*> mvec;
 762
 763     MRI.cpReg2MemMI(RegU, MRI.getFramePointer(), TmpOff, RegType, mvec);
 764     assert(mvec.size() == 1 && "Need to return a vector here too");
 765     MIBef = * mvec.begin();
 766
 767     MRI.cpMem2RegMI(MRI.getFramePointer(), TmpOff, RegU, RegType, mvec);
 768     assert(mvec.size() == 1 && "Need to return a vector here too");
 769     MIAft = * mvec.begin();
 770   }
 771
 772   return RegU;
 773 }
 774
 775 //----------------------------------------------------------------------------
 776 // This method is called to get a new unused register that can be used to
 777 // accomodate a spilled value.
 778 // This method may be called several times for a single machine instruction
 779 // if it contains many spilled operands. Each time it is called, it finds
 780 // a register which is not live at that instruction and also which is not
 781 // used by other spilled operands of the same instruction.
 782 // Return register number is relative to the register class. NOT
 783 // unified number
 784 //----------------------------------------------------------------------------
 785 int PhyRegAlloc::getUnusedUniRegAtMI(RegClass *RC,
 786                                   const MachineInstr *MInst,
 787                                   const ValueSet *LVSetBef) {
 788
 789   unsigned NumAvailRegs =  RC->getNumOfAvailRegs();
 790
 791   std::vector<bool> &IsColorUsedArr = RC->getIsColorUsedArr();
 792
 793   for (unsigned i=0; i <  NumAvailRegs; i++)     // Reset array
 794       IsColorUsedArr[i] = false;
 795
 796   ValueSet::const_iterator LIt = LVSetBef->begin();
 797
 798   // for each live var in live variable set after machine inst
 799   for ( ; LIt != LVSetBef->end(); ++LIt) {
 800
 801    //  get the live range corresponding to live var
 802     LiveRange *const LRofLV = LRI.getLiveRangeForValue(*LIt );
 803
 804     // LR can be null if it is a const since a const
 805     // doesn't have a dominating def - see Assumptions above
 806     if (LRofLV && LRofLV->getRegClass() == RC && 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   for (unsigned c=0; c < NumAvailRegs; c++)   // find first unused color
 817      if (!IsColorUsedArr[c])
 818        return MRI.getUnifiedRegNum(RC->getID(), c);
 819
 820   return -1;
 821 }
 822
 823
 824 //----------------------------------------------------------------------------
 825 // Get any other register in a register class, other than what is used
 826 // by operands of a machine instruction. Returns the unified reg number.
 827 //----------------------------------------------------------------------------
 828 int PhyRegAlloc::getUniRegNotUsedByThisInst(RegClass *RC,
 829                                             const MachineInstr *MInst) {
 830
 831   vector<bool> &IsColorUsedArr = RC->getIsColorUsedArr();
 832   unsigned NumAvailRegs =  RC->getNumOfAvailRegs();
 833
 834
 835   for (unsigned i=0; i < NumAvailRegs ; i++)   // Reset array
 836     IsColorUsedArr[i] = false;
 837
 838   setRelRegsUsedByThisInst(RC, MInst);
 839
 840   for (unsigned c=0; c < RC->getNumOfAvailRegs(); c++)// find first unused color
 841     if (!IsColorUsedArr[c])
 842       return  MRI.getUnifiedRegNum(RC->getID(), c);
 843
 844   assert(0 && "FATAL: No free register could be found in reg class!!");
 845   return 0;
 846 }
 847
 848
 849 //----------------------------------------------------------------------------
 850 // This method modifies the IsColorUsedArr of the register class passed to it.
 851 // It sets the bits corresponding to the registers used by this machine
 852 // instructions. Both explicit and implicit operands are set.
 853 //----------------------------------------------------------------------------
 854 void PhyRegAlloc::setRelRegsUsedByThisInst(RegClass *RC,
 855                                        const MachineInstr *MInst ) {
 856
 857  vector<bool> &IsColorUsedArr = RC->getIsColorUsedArr();
 858
 859  for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 860
 861    const MachineOperand& Op = MInst->getOperand(OpNum);
 862
 863     if (Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 864         Op.getOperandType() ==  MachineOperand::MO_CCRegister ) {
 865
 866       const Value *const Val =  Op.getVRegValue();
 867
 868       if (Val )
 869         if (MRI.getRegClassIDOfValue(Val) == RC->getID() ) {
 870           int Reg;
 871           if ((Reg=Op.getAllocatedRegNum()) != -1) {
 872             IsColorUsedArr[Reg] = true;
 873           }
 874           else {
 875             // it is possilbe that this operand still is not marked with
 876             // a register but it has a LR and that received a color
 877
 878             LiveRange *LROfVal =  LRI.getLiveRangeForValue(Val);
 879             if (LROfVal)
 880               if (LROfVal->hasColor() )
 881                 IsColorUsedArr[LROfVal->getColor()] = true;
 882           }
 883
 884         } // if reg classes are the same
 885     }
 886     else if (Op.getOperandType() ==  MachineOperand::MO_MachineRegister) {
 887       assert((unsigned)Op.getMachineRegNum() < IsColorUsedArr.size());
 888       IsColorUsedArr[Op.getMachineRegNum()] = true;
 889     }
 890  }
 891
 892  // If there are implicit references, mark them as well
 893
 894  for (unsigned z=0; z < MInst->getNumImplicitRefs(); z++) {
 895
 896    LiveRange *const LRofImpRef =
 897      LRI.getLiveRangeForValue( MInst->getImplicitRef(z)  );
 898
 899    if (LRofImpRef && LRofImpRef->hasColor())
 900      IsColorUsedArr[LRofImpRef->getColor()] = true;
 901  }
 902 }
 903
 904
 905
 906
 907
 908
 909
 910
 911 //----------------------------------------------------------------------------
 912 // If there are delay slots for an instruction, the instructions
 913 // added after it must really go after the delayed instruction(s).
 914 // So, we move the InstrAfter of that instruction to the
 915 // corresponding delayed instruction using the following method.
 916
 917 //----------------------------------------------------------------------------
 918 void PhyRegAlloc::move2DelayedInstr(const MachineInstr *OrigMI,
 919                                     const MachineInstr *DelayedMI) {
 920
 921   // "added after" instructions of the original instr
 922   std::vector<MachineInstr *> &OrigAft = AddedInstrMap[OrigMI].InstrnsAfter;
 923
 924   // "added instructions" of the delayed instr
 925   AddedInstrns &DelayAdI = AddedInstrMap[DelayedMI];
 926
 927   // "added after" instructions of the delayed instr
 928   std::vector<MachineInstr *> &DelayedAft = DelayAdI.InstrnsAfter;
 929
 930   // go thru all the "added after instructions" of the original instruction
 931   // and append them to the "addded after instructions" of the delayed
 932   // instructions
 933   DelayedAft.insert(DelayedAft.end(), OrigAft.begin(), OrigAft.end());
 934
 935   // empty the "added after instructions" of the original instruction
 936   OrigAft.clear();
 937 }
 938
 939 //----------------------------------------------------------------------------
 940 // This method prints the code with registers after register allocation is
 941 // complete.
 942 //----------------------------------------------------------------------------
 943 void PhyRegAlloc::printMachineCode()
 944 {
 945
 946   cerr << "\n;************** Function " << Meth->getName()
 947        << " *****************\n";
 948
 949   for (Function::const_iterator BBI = Meth->begin(), BBE = Meth->end();
 950        BBI != BBE; ++BBI) {
 951     cerr << "\n"; printLabel(BBI); cerr << ": ";
 952
 953     // get the iterator for machine instructions
 954     MachineCodeForBasicBlock& MIVec = BBI->getMachineInstrVec();
 955     MachineCodeForBasicBlock::iterator MII = MIVec.begin();
 956
 957     // iterate over all the machine instructions in BB
 958     for ( ; MII != MIVec.end(); ++MII) {
 959       MachineInstr *const MInst = *MII;
 960
 961       cerr << "\n\t";
 962       cerr << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
 963
 964       for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 965         MachineOperand& Op = MInst->getOperand(OpNum);
 966
 967         if (Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 968             Op.getOperandType() ==  MachineOperand::MO_CCRegister /*||
 969             Op.getOperandType() ==  MachineOperand::MO_PCRelativeDisp*/ ) {
 970
 971           const Value *const Val = Op.getVRegValue () ;
 972           // ****this code is temporary till NULL Values are fixed
 973           if (! Val ) {
 974             cerr << "\t<*NULL*>";
 975             continue;
 976           }
 977
 978           // if a label or a constant
 979           if (isa<BasicBlock>(Val)) {
 980             cerr << "\t"; printLabel(   Op.getVRegValue () );
 981           } else {
 982             // else it must be a register value
 983             const int RegNum = Op.getAllocatedRegNum();
 984
 985             cerr << "\t" << "%" << MRI.getUnifiedRegName( RegNum );
 986             if (Val->hasName() )
 987               cerr << "(" << Val->getName() << ")";
 988             else
 989               cerr << "(" << Val << ")";
 990
 991             if (Op.opIsDef() )
 992               cerr << "*";
 993
 994             const LiveRange *LROfVal = LRI.getLiveRangeForValue(Val);
 995             if (LROfVal )
 996               if (LROfVal->hasSpillOffset() )
 997                 cerr << "$";
 998           }
 999
1000         }
1001         else if (Op.getOperandType() ==  MachineOperand::MO_MachineRegister) {
1002           cerr << "\t" << "%" << MRI.getUnifiedRegName(Op.getMachineRegNum());
1003         }
1004
1005         else
1006           cerr << "\t" << Op;      // use dump field
1007       }
1008
1009
1010
1011       unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
1012       if (NumOfImpRefs > 0) {
1013         cerr << "\tImplicit:";
1014
1015         for (unsigned z=0; z < NumOfImpRefs; z++)
1016           cerr << RAV(MInst->getImplicitRef(z)) << "\t";
1017       }
1018
1019     } // for all machine instructions
1020
1021     cerr << "\n";
1022
1023   } // for all BBs
1024
1025   cerr << "\n";
1026 }
1027
1028
1029 #if 0
1030
1031 //----------------------------------------------------------------------------
1032 //
1033 //----------------------------------------------------------------------------
1034
1035 void PhyRegAlloc::colorCallRetArgs()
1036 {
1037
1038   CallRetInstrListType &CallRetInstList = LRI.getCallRetInstrList();
1039   CallRetInstrListType::const_iterator It = CallRetInstList.begin();
1040
1041   for ( ; It != CallRetInstList.end(); ++It ) {
1042
1043     const MachineInstr *const CRMI = *It;
1044     unsigned OpCode =  CRMI->getOpCode();
1045
1046     // get the added instructions for this Call/Ret instruciton
1047     AddedInstrns &AI = AddedInstrMap[CRMI];
1048
1049     // Tmp stack positions are needed by some calls that have spilled args
1050     // So reset it before we call each such method
1051     //mcInfo.popAllTempValues(TM);
1052
1053
1054     if (TM.getInstrInfo().isCall(OpCode))
1055       MRI.colorCallArgs(CRMI, LRI, &AI, *this);
1056     else if (TM.getInstrInfo().isReturn(OpCode))
1057       MRI.colorRetValue(CRMI, LRI, &AI);
1058     else
1059       assert(0 && "Non Call/Ret instrn in CallRetInstrList\n");
1060   }
1061 }
1062
1063 #endif
1064
1065 //----------------------------------------------------------------------------
1066
1067 //----------------------------------------------------------------------------
1068 void PhyRegAlloc::colorIncomingArgs()
1069 {
1070   const BasicBlock &FirstBB = Meth->front();
1071   const MachineInstr *FirstMI = FirstBB.getMachineInstrVec().front();
1072   assert(FirstMI && "No machine instruction in entry BB");
1073
1074   MRI.colorMethodArgs(Meth, LRI, &AddedInstrAtEntry);
1075 }
1076
1077
1078 //----------------------------------------------------------------------------
1079 // Used to generate a label for a basic block
1080 //----------------------------------------------------------------------------
1081 void PhyRegAlloc::printLabel(const Value *const Val) {
1082   if (Val->hasName())
1083     cerr  << Val->getName();
1084   else
1085     cerr << "Label" <<  Val;
1086 }
1087
1088
1089 //----------------------------------------------------------------------------
1090 // This method calls setSugColorUsable method of each live range. This
1091 // will determine whether the suggested color of LR is  really usable.
1092 // A suggested color is not usable when the suggested color is volatile
1093 // AND when there are call interferences
1094 //----------------------------------------------------------------------------
1095
1096 void PhyRegAlloc::markUnusableSugColors()
1097 {
1098   if (DEBUG_RA ) cerr << "\nmarking unusable suggested colors ...\n";
1099
1100   // hash map iterator
1101   LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
1102   LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
1103
1104     for (; HMI != HMIEnd ; ++HMI ) {
1105       if (HMI->first) {
1106         LiveRange *L = HMI->second;      // get the LiveRange
1107         if (L) {
1108           if (L->hasSuggestedColor()) {
1109             int RCID = L->getRegClass()->getID();
1110             if (MRI.isRegVolatile( RCID,  L->getSuggestedColor()) &&
1111                 L->isCallInterference() )
1112               L->setSuggestedColorUsable( false );
1113             else
1114               L->setSuggestedColorUsable( true );
1115           }
1116         } // if L->hasSuggestedColor()
1117       }
1118     } // for all LR's in hash map
1119 }
1120
1121
1122
1123 //----------------------------------------------------------------------------
1124 // The following method will set the stack offsets of the live ranges that
1125 // are decided to be spillled. This must be called just after coloring the
1126 // LRs using the graph coloring algo. For each live range that is spilled,
1127 // this method allocate a new spill position on the stack.
1128 //----------------------------------------------------------------------------
1129
1130 void PhyRegAlloc::allocateStackSpace4SpilledLRs() {
1131   if (DEBUG_RA) cerr << "\nsetting LR stack offsets ...\n";
1132
1133   LiveRangeMapType::const_iterator HMI    = LRI.getLiveRangeMap()->begin();
1134   LiveRangeMapType::const_iterator HMIEnd = LRI.getLiveRangeMap()->end();
1135
1136   for ( ; HMI != HMIEnd ; ++HMI) {
1137     if (HMI->first && HMI->second) {
1138       LiveRange *L = HMI->second;      // get the LiveRange
1139       if (!L->hasColor())   //  NOTE: ** allocating the size of long Type **
1140         L->setSpillOffFromFP(mcInfo.allocateSpilledValue(TM, Type::LongTy));
1141     }
1142   } // for all LR's in hash map
1143 }
1144
1145
1146
1147 //----------------------------------------------------------------------------
1148 // The entry pont to Register Allocation
1149 //----------------------------------------------------------------------------
1150
1151 void PhyRegAlloc::allocateRegisters()
1152 {
1153
1154   // make sure that we put all register classes into the RegClassList
1155   // before we call constructLiveRanges (now done in the constructor of
1156   // PhyRegAlloc class).
1157   //
1158   LRI.constructLiveRanges();            // create LR info
1159
1160   if (DEBUG_RA)
1161     LRI.printLiveRanges();
1162
1163   createIGNodeListsAndIGs();            // create IGNode list and IGs
1164
1165   buildInterferenceGraphs();            // build IGs in all reg classes
1166
1167
1168   if (DEBUG_RA) {
1169     // print all LRs in all reg classes
1170     for ( unsigned rc=0; rc < NumOfRegClasses  ; rc++)
1171       RegClassList[rc]->printIGNodeList();
1172
1173     // print IGs in all register classes
1174     for ( unsigned rc=0; rc < NumOfRegClasses ; rc++)
1175       RegClassList[rc]->printIG();
1176   }
1177
1178
1179   LRI.coalesceLRs();                    // coalesce all live ranges
1180
1181
1182   if (DEBUG_RA) {
1183     // print all LRs in all reg classes
1184     for ( unsigned rc=0; rc < NumOfRegClasses  ; rc++)
1185       RegClassList[ rc ]->printIGNodeList();
1186
1187     // print IGs in all register classes
1188     for ( unsigned rc=0; rc < NumOfRegClasses ; rc++)
1189       RegClassList[ rc ]->printIG();
1190   }
1191
1192
1193   // mark un-usable suggested color before graph coloring algorithm.
1194   // When this is done, the graph coloring algo will not reserve
1195   // suggested color unnecessarily - they can be used by another LR
1196   //
1197   markUnusableSugColors();
1198
1199   // color all register classes using the graph coloring algo
1200   for (unsigned rc=0; rc < NumOfRegClasses ; rc++)
1201     RegClassList[ rc ]->colorAllRegs();
1202
1203   // Atter grpah coloring, if some LRs did not receive a color (i.e, spilled)
1204   // a poistion for such spilled LRs
1205   //
1206   allocateStackSpace4SpilledLRs();
1207
1208   mcInfo.popAllTempValues(TM);  // TODO **Check
1209
1210   // color incoming args - if the correct color was not received
1211   // insert code to copy to the correct register
1212   //
1213   colorIncomingArgs();
1214
1215   // Now update the machine code with register names and add any
1216   // additional code inserted by the register allocator to the instruction
1217   // stream
1218   //
1219   updateMachineCode();
1220
1221   if (DEBUG_RA) {
1222     MachineCodeForMethod::get(Meth).dump();
1223     printMachineCode();                   // only for DEBUGGING
1224   }
1225 }
1226
1227
1228