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/MachineCodeForBasicBlock.h"
  17 #include "llvm/CodeGen/MachineCodeForMethod.h"
  18 #include "llvm/Analysis/LiveVar/FunctionLiveVarInfo.h"
  19 #include "llvm/Analysis/LoopInfo.h"
  20 #include "llvm/Target/TargetMachine.h"
  21 #include "llvm/Target/MachineFrameInfo.h"
  22 #include "llvm/BasicBlock.h"
  23 #include "llvm/Function.h"
  24 #include "llvm/Type.h"
  25 #include "llvm/iOther.h"
  26 #include "llvm/CodeGen/RegAllocCommon.h"
  27 #include "Support/CommandLine.h"
  28 #include "Support/STLExtras.h"
  29 #include <iostream>
  30 #include <math.h>
  31 using std::cerr;
  32 using std::vector;
  33
  34 RegAllocDebugLevel_t DEBUG_RA;
  35 static cl::Enum<RegAllocDebugLevel_t> DEBUG_RA_c(DEBUG_RA, "dregalloc",
  36                                                  cl::Hidden,
  37   "enable register allocation debugging information",
  38   clEnumValN(RA_DEBUG_None   , "n", "disable debug output"),
  39   clEnumValN(RA_DEBUG_Normal , "y", "enable debug output"),
  40   clEnumValN(RA_DEBUG_Verbose, "v", "enable extra debug output"), 0);
  41
  42
  43 //----------------------------------------------------------------------------
  44 // RegisterAllocation pass front end...
  45 //----------------------------------------------------------------------------
  46 namespace {
  47   class RegisterAllocator : public FunctionPass {
  48     TargetMachine &Target;
  49   public:
  50     inline RegisterAllocator(TargetMachine &T) : Target(T) {}
  51
  52     const char *getPassName() const { return "Register Allocation"; }
  53
  54     bool runOnFunction(Function &F) {
  55       if (DEBUG_RA)
  56         cerr << "\n********* Function "<< F.getName() << " ***********\n";
  57
  58       PhyRegAlloc PRA(&F, Target, &getAnalysis<FunctionLiveVarInfo>(),
  59                       &getAnalysis<LoopInfo>());
  60       PRA.allocateRegisters();
  61
  62       if (DEBUG_RA) cerr << "\nRegister allocation complete!\n";
  63       return false;
  64     }
  65
  66     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  67       AU.addRequired(LoopInfo::ID);
  68       AU.addRequired(FunctionLiveVarInfo::ID);
  69     }
  70   };
  71 }
  72
  73 Pass *getRegisterAllocator(TargetMachine &T) {
  74   return new RegisterAllocator(T);
  75 }
  76
  77 //----------------------------------------------------------------------------
  78 // Constructor: Init local composite objects and create register classes.
  79 //----------------------------------------------------------------------------
  80 PhyRegAlloc::PhyRegAlloc(Function *F, const TargetMachine& tm,
  81                          FunctionLiveVarInfo *Lvi, 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 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 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 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 >= RA_DEBUG_Verbose)
 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 >= RA_DEBUG_Verbose)  {
 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   CallArgsDescriptor* argDesc = CallArgsDescriptor::get(MInst);
 254
 255   if (const Value *RetVal = argDesc->getReturnValue()) {
 256     LiveRange *RetValLR = LRI.getLiveRangeForValue( RetVal );
 257     assert( RetValLR && "No LR for RetValue of call");
 258     RetValLR->clearCallInterference();
 259   }
 260
 261   // If the CALL is an indirect call, find the LR of the function pointer.
 262   // That has a call interference because it conflicts with outgoing args.
 263   if (const Value *AddrVal = argDesc->getIndirectFuncPtr()) {
 264     LiveRange *AddrValLR = LRI.getLiveRangeForValue( AddrVal );
 265     assert( AddrValLR && "No LR for indirect addr val of call");
 266     AddrValLR->setCallInterference();
 267   }
 268
 269 }
 270
 271
 272
 273
 274 //----------------------------------------------------------------------------
 275 // This method will walk thru code and create interferences in the IG of
 276 // each RegClass. Also, this method calculates the spill cost of each
 277 // Live Range (it is done in this method to save another pass over the code).
 278 //----------------------------------------------------------------------------
 279 void PhyRegAlloc::buildInterferenceGraphs()
 280 {
 281
 282   if (DEBUG_RA) cerr << "Creating interference graphs ...\n";
 283
 284   unsigned BBLoopDepthCost;
 285   for (Function::const_iterator BBI = Meth->begin(), BBE = Meth->end();
 286        BBI != BBE; ++BBI) {
 287
 288     // find the 10^(loop_depth) of this BB
 289     //
 290     BBLoopDepthCost = (unsigned)pow(10.0, LoopDepthCalc->getLoopDepth(BBI));
 291
 292     // get the iterator for machine instructions
 293     //
 294     const MachineCodeForBasicBlock& MIVec = MachineCodeForBasicBlock::get(BBI);
 295     MachineCodeForBasicBlock::const_iterator MII = MIVec.begin();
 296
 297     // iterate over all the machine instructions in BB
 298     //
 299     for ( ; MII != MIVec.end(); ++MII) {
 300
 301       const MachineInstr *MInst = *MII;
 302
 303       // get the LV set after the instruction
 304       //
 305       const ValueSet &LVSetAI = LVI->getLiveVarSetAfterMInst(MInst, BBI);
 306
 307       const bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpCode());
 308
 309       if (isCallInst ) {
 310         // set the isCallInterference flag of each live range wich extends
 311         // accross this call instruction. This information is used by graph
 312         // coloring algo to avoid allocating volatile colors to live ranges
 313         // that span across calls (since they have to be saved/restored)
 314         //
 315         setCallInterferences(MInst, &LVSetAI);
 316       }
 317
 318
 319       // iterate over all MI operands to find defs
 320       //
 321       for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
 322              OpE = MInst->end(); OpI != OpE; ++OpI) {
 323         if (OpI.isDef())    // create a new LR iff this operand is a def
 324           addInterference(*OpI, &LVSetAI, isCallInst);
 325
 326         // Calculate the spill cost of each live range
 327         //
 328         LiveRange *LR = LRI.getLiveRangeForValue(*OpI);
 329         if (LR) LR->addSpillCost(BBLoopDepthCost);
 330       }
 331
 332
 333       // if there are multiple defs in this instruction e.g. in SETX
 334       //
 335       if (TM.getInstrInfo().isPseudoInstr(MInst->getOpCode()))
 336         addInterf4PseudoInstr(MInst);
 337
 338
 339       // Also add interference for any implicit definitions in a machine
 340       // instr (currently, only calls have this).
 341       //
 342       unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
 343       if ( NumOfImpRefs > 0 ) {
 344         for (unsigned z=0; z < NumOfImpRefs; z++)
 345           if (MInst->implicitRefIsDefined(z) )
 346             addInterference( MInst->getImplicitRef(z), &LVSetAI, isCallInst );
 347       }
 348
 349
 350     } // for all machine instructions in BB
 351   } // for all BBs in function
 352
 353
 354   // add interferences for function arguments. Since there are no explict
 355   // defs in the function for args, we have to add them manually
 356   //
 357   addInterferencesForArgs();
 358
 359   if (DEBUG_RA)
 360     cerr << "Interference graphs calculted!\n";
 361
 362 }
 363
 364
 365
 366 //--------------------------------------------------------------------------
 367 // Pseudo instructions will be exapnded to multiple instructions by the
 368 // assembler. Consequently, all the opernds must get distinct registers.
 369 // Therefore, we mark all operands of a pseudo instruction as they interfere
 370 // with one another.
 371 //--------------------------------------------------------------------------
 372 void PhyRegAlloc::addInterf4PseudoInstr(const MachineInstr *MInst) {
 373
 374   bool setInterf = false;
 375
 376   // iterate over  MI operands to find defs
 377   //
 378   for (MachineInstr::const_val_op_iterator It1 = MInst->begin(),
 379          ItE = MInst->end(); It1 != ItE; ++It1) {
 380     const LiveRange *LROfOp1 = LRI.getLiveRangeForValue(*It1);
 381     assert((LROfOp1 || !It1.isDef()) && "No LR for Def in PSEUDO insruction");
 382
 383     MachineInstr::const_val_op_iterator It2 = It1;
 384     for (++It2; It2 != ItE; ++It2) {
 385       const LiveRange *LROfOp2 = LRI.getLiveRangeForValue(*It2);
 386
 387       if (LROfOp2) {
 388         RegClass *RCOfOp1 = LROfOp1->getRegClass();
 389         RegClass *RCOfOp2 = LROfOp2->getRegClass();
 390
 391         if (RCOfOp1 == RCOfOp2 ){
 392           RCOfOp1->setInterference( LROfOp1, LROfOp2 );
 393           setInterf = true;
 394         }
 395       } // if Op2 has a LR
 396     } // for all other defs in machine instr
 397   } // for all operands in an instruction
 398
 399   if (!setInterf && MInst->getNumOperands() > 2) {
 400     cerr << "\nInterf not set for any operand in pseudo instr:\n";
 401     cerr << *MInst;
 402     assert(0 && "Interf not set for pseudo instr with > 2 operands" );
 403   }
 404 }
 405
 406
 407
 408 //----------------------------------------------------------------------------
 409 // This method will add interferences for incoming arguments to a function.
 410 //----------------------------------------------------------------------------
 411 void PhyRegAlloc::addInterferencesForArgs() {
 412   // get the InSet of root BB
 413   const ValueSet &InSet = LVI->getInSetOfBB(&Meth->front());
 414
 415   for (Function::const_aiterator AI = Meth->abegin(); AI != Meth->aend(); ++AI) {
 416     // add interferences between args and LVars at start
 417     addInterference(AI, &InSet, false);
 418
 419     if (DEBUG_RA >= RA_DEBUG_Verbose)
 420       cerr << " - %% adding interference for  argument " << RAV(AI) << "\n";
 421   }
 422 }
 423
 424
 425 //----------------------------------------------------------------------------
 426 // This method is called after register allocation is complete to set the
 427 // allocated reisters in the machine code. This code will add register numbers
 428 // to MachineOperands that contain a Value. Also it calls target specific
 429 // methods to produce caller saving instructions. At the end, it adds all
 430 // additional instructions produced by the register allocator to the
 431 // instruction stream.
 432 //----------------------------------------------------------------------------
 433
 434 //-----------------------------
 435 // Utility functions used below
 436 //-----------------------------
 437 inline void
 438 PrependInstructions(vector<MachineInstr *> &IBef,
 439                     MachineCodeForBasicBlock& MIVec,
 440                     MachineCodeForBasicBlock::iterator& MII,
 441                     const std::string& msg)
 442 {
 443   if (!IBef.empty())
 444     {
 445       MachineInstr* OrigMI = *MII;
 446       std::vector<MachineInstr *>::iterator AdIt;
 447       for (AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt)
 448         {
 449           if (DEBUG_RA) {
 450             if (OrigMI) cerr << "For MInst: " << *OrigMI;
 451             cerr << msg << " PREPENDed instr: " << **AdIt << "\n";
 452           }
 453           MII = MIVec.insert(MII, *AdIt);
 454           ++MII;
 455         }
 456     }
 457 }
 458
 459 inline void
 460 AppendInstructions(std::vector<MachineInstr *> &IAft,
 461                    MachineCodeForBasicBlock& MIVec,
 462                    MachineCodeForBasicBlock::iterator& MII,
 463                    const std::string& msg)
 464 {
 465   if (!IAft.empty())
 466     {
 467       MachineInstr* OrigMI = *MII;
 468       std::vector<MachineInstr *>::iterator AdIt;
 469       for ( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt )
 470         {
 471           if (DEBUG_RA) {
 472             if (OrigMI) cerr << "For MInst: " << *OrigMI;
 473             cerr << msg << " APPENDed instr: "  << **AdIt << "\n";
 474           }
 475           ++MII;    // insert before the next instruction
 476           MII = MIVec.insert(MII, *AdIt);
 477         }
 478     }
 479 }
 480
 481
 482 void PhyRegAlloc::updateMachineCode()
 483 {
 484   MachineCodeForBasicBlock& MIVec = MachineCodeForBasicBlock::get(&Meth->getEntryNode());
 485
 486   // Insert any instructions needed at method entry
 487   MachineCodeForBasicBlock::iterator MII = MIVec.begin();
 488   PrependInstructions(AddedInstrAtEntry.InstrnsBefore, MIVec, MII,
 489                       "At function entry: \n");
 490   assert(AddedInstrAtEntry.InstrnsAfter.empty() &&
 491          "InstrsAfter should be unnecessary since we are just inserting at "
 492          "the function entry point here.");
 493
 494   for (Function::const_iterator BBI = Meth->begin(), BBE = Meth->end();
 495        BBI != BBE; ++BBI) {
 496
 497     // iterate over all the machine instructions in BB
 498     MachineCodeForBasicBlock &MIVec = MachineCodeForBasicBlock::get(BBI);
 499     for (MachineCodeForBasicBlock::iterator MII = MIVec.begin();
 500         MII != MIVec.end(); ++MII) {
 501
 502       MachineInstr *MInst = *MII;
 503
 504       unsigned Opcode =  MInst->getOpCode();
 505
 506       // do not process Phis
 507       if (TM.getInstrInfo().isDummyPhiInstr(Opcode))
 508         continue;
 509
 510       // Reset tmp stack positions so they can be reused for each machine instr.
 511       mcInfo.popAllTempValues(TM);
 512
 513       // Now insert speical instructions (if necessary) for call/return
 514       // instructions.
 515       //
 516       if (TM.getInstrInfo().isCall(Opcode) ||
 517           TM.getInstrInfo().isReturn(Opcode)) {
 518
 519         AddedInstrns &AI = AddedInstrMap[MInst];
 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       // Set the registers for operands in the machine instruction
 528       // if a register was successfully allocated.  If not, insert
 529       // code to spill the register value.
 530       //
 531       for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum)
 532         {
 533           MachineOperand& Op = MInst->getOperand(OpNum);
 534           if (Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 535               Op.getOperandType() ==  MachineOperand::MO_CCRegister)
 536             {
 537               const Value *const Val =  Op.getVRegValue();
 538
 539               LiveRange *const LR = LRI.getLiveRangeForValue(Val);
 540               if (!LR)              // consts or labels will have no live range
 541                 {
 542                   // if register is not allocated, mark register as invalid
 543                   if (Op.getAllocatedRegNum() == -1)
 544                     MInst->SetRegForOperand(OpNum, MRI.getInvalidRegNum());
 545                   continue;
 546                 }
 547
 548               if (LR->hasColor() )
 549                 MInst->SetRegForOperand(OpNum,
 550                                 MRI.getUnifiedRegNum(LR->getRegClass()->getID(),
 551                                                      LR->getColor()));
 552               else
 553                 // LR did NOT receive a color (register). Insert spill code.
 554                 insertCode4SpilledLR(LR, MInst, BBI, OpNum );
 555             }
 556         } // for each operand
 557
 558
 559       // Now add instructions that the register allocator inserts before/after
 560       // this machine instructions (done only for calls/rets/incoming args)
 561       // We do this here, to ensure that spill for an instruction is inserted
 562       // closest as possible to an instruction (see above insertCode4Spill...)
 563       //
 564       // If there are instructions to be added, *before* this machine
 565       // instruction, add them now.
 566       //
 567       if (AddedInstrMap.count(MInst)) {
 568         PrependInstructions(AddedInstrMap[MInst].InstrnsBefore, MIVec, MII,"");
 569       }
 570
 571       // If there are instructions to be added *after* this machine
 572       // instruction, add them now
 573       //
 574       if (!AddedInstrMap[MInst].InstrnsAfter.empty()) {
 575
 576         // if there are delay slots for this instruction, the instructions
 577         // added after it must really go after the delayed instruction(s)
 578         // So, we move the InstrAfter of the current instruction to the
 579         // corresponding delayed instruction
 580
 581         unsigned delay;
 582         if ((delay=TM.getInstrInfo().getNumDelaySlots(MInst->getOpCode())) >0){
 583           move2DelayedInstr(MInst,  *(MII+delay) );
 584         }
 585         else {
 586           // Here we can add the "instructions after" to the current
 587           // instruction since there are no delay slots for this instruction
 588           AppendInstructions(AddedInstrMap[MInst].InstrnsAfter, MIVec, MII,"");
 589         }  // if not delay
 590       }
 591
 592     } // for each machine instruction
 593   }
 594 }
 595
 596
 597
 598 //----------------------------------------------------------------------------
 599 // This method inserts spill code for AN operand whose LR was spilled.
 600 // This method may be called several times for a single machine instruction
 601 // if it contains many spilled operands. Each time it is called, it finds
 602 // a register which is not live at that instruction and also which is not
 603 // used by other spilled operands of the same instruction. Then it uses
 604 // this register temporarily to accomodate the spilled value.
 605 //----------------------------------------------------------------------------
 606 void PhyRegAlloc::insertCode4SpilledLR(const LiveRange *LR,
 607                                        MachineInstr *MInst,
 608                                        const BasicBlock *BB,
 609                                        const unsigned OpNum) {
 610
 611   assert(! TM.getInstrInfo().isCall(MInst->getOpCode()) &&
 612          (! TM.getInstrInfo().isReturn(MInst->getOpCode())) &&
 613          "Arg of a call/ret must be handled elsewhere");
 614
 615   MachineOperand& Op = MInst->getOperand(OpNum);
 616   bool isDef =  MInst->operandIsDefined(OpNum);
 617   bool isDefAndUse =  MInst->operandIsDefinedAndUsed(OpNum);
 618   unsigned RegType = MRI.getRegType( LR );
 619   int SpillOff = LR->getSpillOffFromFP();
 620   RegClass *RC = LR->getRegClass();
 621   const ValueSet &LVSetBef = LVI->getLiveVarSetBeforeMInst(MInst, BB);
 622
 623   mcInfo.pushTempValue(TM, MRI.getSpilledRegSize(RegType) );
 624
 625   vector<MachineInstr*> MIBef, MIAft;
 626   vector<MachineInstr*> AdIMid;
 627
 628   // Choose a register to hold the spilled value.  This may insert code
 629   // before and after MInst to free up the value.  If so, this code should
 630   // be first and last in the spill sequence before/after MInst.
 631   int TmpRegU = getUsableUniRegAtMI(RegType, &LVSetBef, MInst, MIBef, MIAft);
 632
 633   // Set the operand first so that it this register does not get used
 634   // as a scratch register for later calls to getUsableUniRegAtMI below
 635   MInst->SetRegForOperand(OpNum, TmpRegU);
 636
 637   // get the added instructions for this instruction
 638   AddedInstrns &AI = AddedInstrMap[MInst];
 639
 640   // We may need a scratch register to copy the spilled value to/from memory.
 641   // This may itself have to insert code to free up a scratch register.
 642   // Any such code should go before (after) the spill code for a load (store).
 643   int scratchRegType = -1;
 644   int scratchReg = -1;
 645   if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
 646     {
 647       scratchReg = this->getUsableUniRegAtMI(scratchRegType, &LVSetBef,
 648                                              MInst, MIBef, MIAft);
 649       assert(scratchReg != MRI.getInvalidRegNum());
 650       MInst->getRegsUsed().insert(scratchReg);
 651     }
 652
 653   if (!isDef || isDefAndUse) {
 654     // for a USE, we have to load the value of LR from stack to a TmpReg
 655     // and use the TmpReg as one operand of instruction
 656
 657     // actual loading instruction(s)
 658     MRI.cpMem2RegMI(AdIMid, MRI.getFramePointer(), SpillOff, TmpRegU, RegType,
 659                     scratchReg);
 660
 661     // the actual load should be after the instructions to free up TmpRegU
 662     MIBef.insert(MIBef.end(), AdIMid.begin(), AdIMid.end());
 663     AdIMid.clear();
 664   }
 665
 666   if (isDef) {   // if this is a Def
 667     // for a DEF, we have to store the value produced by this instruction
 668     // on the stack position allocated for this LR
 669
 670     // actual storing instruction(s)
 671     MRI.cpReg2MemMI(AdIMid, TmpRegU, MRI.getFramePointer(), SpillOff, RegType,
 672                     scratchReg);
 673
 674     MIAft.insert(MIAft.begin(), AdIMid.begin(), AdIMid.end());
 675   }  // if !DEF
 676
 677   // Finally, insert the entire spill code sequences before/after MInst
 678   AI.InstrnsBefore.insert(AI.InstrnsBefore.end(), MIBef.begin(), MIBef.end());
 679   AI.InstrnsAfter.insert(AI.InstrnsAfter.begin(), MIAft.begin(), MIAft.end());
 680
 681   if (DEBUG_RA) {
 682     cerr << "\nFor Inst " << *MInst;
 683     cerr << " - SPILLED LR: "; printSet(*LR);
 684     cerr << "\n - Added Instructions:";
 685     for_each(MIBef.begin(), MIBef.end(), std::mem_fun(&MachineInstr::dump));
 686     for_each(MIAft.begin(), MIAft.end(), std::mem_fun(&MachineInstr::dump));
 687   }
 688 }
 689
 690
 691 //----------------------------------------------------------------------------
 692 // We can use the following method to get a temporary register to be used
 693 // BEFORE any given machine instruction. If there is a register available,
 694 // this method will simply return that register and set MIBef = MIAft = NULL.
 695 // Otherwise, it will return a register and MIAft and MIBef will contain
 696 // two instructions used to free up this returned register.
 697 // Returned register number is the UNIFIED register number
 698 //----------------------------------------------------------------------------
 699
 700 int PhyRegAlloc::getUsableUniRegAtMI(const int RegType,
 701                                      const ValueSet *LVSetBef,
 702                                      MachineInstr *MInst,
 703                                      std::vector<MachineInstr*>& MIBef,
 704                                      std::vector<MachineInstr*>& MIAft) {
 705
 706   RegClass* RC = this->getRegClassByID(MRI.getRegClassIDOfRegType(RegType));
 707
 708   int RegU =  getUnusedUniRegAtMI(RC, MInst, LVSetBef);
 709
 710   if (RegU == -1) {
 711     // we couldn't find an unused register. Generate code to free up a reg by
 712     // saving it on stack and restoring after the instruction
 713
 714     int TmpOff = mcInfo.pushTempValue(TM,  MRI.getSpilledRegSize(RegType) );
 715
 716     RegU = getUniRegNotUsedByThisInst(RC, MInst);
 717
 718     // Check if we need a scratch register to copy this register to memory.
 719     int scratchRegType = -1;
 720     if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
 721       {
 722         int scratchReg = this->getUsableUniRegAtMI(scratchRegType, LVSetBef,
 723                                                    MInst, MIBef, MIAft);
 724         assert(scratchReg != MRI.getInvalidRegNum());
 725
 726         // We may as well hold the value in the scratch register instead
 727         // of copying it to memory and back.  But we have to mark the
 728         // register as used by this instruction, so it does not get used
 729         // as a scratch reg. by another operand or anyone else.
 730         MInst->getRegsUsed().insert(scratchReg);
 731         MRI.cpReg2RegMI(MIBef, RegU, scratchReg, RegType);
 732         MRI.cpReg2RegMI(MIAft, scratchReg, RegU, RegType);
 733       }
 734     else
 735       { // the register can be copied directly to/from memory so do it.
 736         MRI.cpReg2MemMI(MIBef, RegU, MRI.getFramePointer(), TmpOff, RegType);
 737         MRI.cpMem2RegMI(MIAft, MRI.getFramePointer(), TmpOff, RegU, RegType);
 738       }
 739   }
 740
 741   return RegU;
 742 }
 743
 744 //----------------------------------------------------------------------------
 745 // This method is called to get a new unused register that can be used to
 746 // accomodate a spilled value.
 747 // This method may be called several times for a single machine instruction
 748 // if it contains many spilled operands. Each time it is called, it finds
 749 // a register which is not live at that instruction and also which is not
 750 // used by other spilled operands of the same instruction.
 751 // Return register number is relative to the register class. NOT
 752 // unified number
 753 //----------------------------------------------------------------------------
 754 int PhyRegAlloc::getUnusedUniRegAtMI(RegClass *RC,
 755                                   const MachineInstr *MInst,
 756                                   const ValueSet *LVSetBef) {
 757
 758   unsigned NumAvailRegs =  RC->getNumOfAvailRegs();
 759
 760   std::vector<bool> &IsColorUsedArr = RC->getIsColorUsedArr();
 761
 762   for (unsigned i=0; i <  NumAvailRegs; i++)     // Reset array
 763       IsColorUsedArr[i] = false;
 764
 765   ValueSet::const_iterator LIt = LVSetBef->begin();
 766
 767   // for each live var in live variable set after machine inst
 768   for ( ; LIt != LVSetBef->end(); ++LIt) {
 769
 770    //  get the live range corresponding to live var
 771     LiveRange *const LRofLV = LRI.getLiveRangeForValue(*LIt );
 772
 773     // LR can be null if it is a const since a const
 774     // doesn't have a dominating def - see Assumptions above
 775     if (LRofLV && LRofLV->getRegClass() == RC && LRofLV->hasColor() )
 776       IsColorUsedArr[ LRofLV->getColor() ] = true;
 777   }
 778
 779   // It is possible that one operand of this MInst was already spilled
 780   // and it received some register temporarily. If that's the case,
 781   // it is recorded in machine operand. We must skip such registers.
 782
 783   setRelRegsUsedByThisInst(RC, MInst);
 784
 785   for (unsigned c=0; c < NumAvailRegs; c++)   // find first unused color
 786      if (!IsColorUsedArr[c])
 787        return MRI.getUnifiedRegNum(RC->getID(), c);
 788
 789   return -1;
 790 }
 791
 792
 793 //----------------------------------------------------------------------------
 794 // Get any other register in a register class, other than what is used
 795 // by operands of a machine instruction. Returns the unified reg number.
 796 //----------------------------------------------------------------------------
 797 int PhyRegAlloc::getUniRegNotUsedByThisInst(RegClass *RC,
 798                                             const MachineInstr *MInst) {
 799
 800   vector<bool> &IsColorUsedArr = RC->getIsColorUsedArr();
 801   unsigned NumAvailRegs =  RC->getNumOfAvailRegs();
 802
 803   for (unsigned i=0; i < NumAvailRegs ; i++)   // Reset array
 804     IsColorUsedArr[i] = false;
 805
 806   setRelRegsUsedByThisInst(RC, MInst);
 807
 808   for (unsigned c=0; c < RC->getNumOfAvailRegs(); c++)// find first unused color
 809     if (!IsColorUsedArr[c])
 810       return  MRI.getUnifiedRegNum(RC->getID(), c);
 811
 812   assert(0 && "FATAL: No free register could be found in reg class!!");
 813   return 0;
 814 }
 815
 816
 817 //----------------------------------------------------------------------------
 818 // This method modifies the IsColorUsedArr of the register class passed to it.
 819 // It sets the bits corresponding to the registers used by this machine
 820 // instructions. Both explicit and implicit operands are set.
 821 //----------------------------------------------------------------------------
 822 void PhyRegAlloc::setRelRegsUsedByThisInst(RegClass *RC,
 823                                            const MachineInstr *MInst ) {
 824
 825   vector<bool> &IsColorUsedArr = RC->getIsColorUsedArr();
 826
 827   // Add the registers already marked as used by the instruction.
 828   // This should include any scratch registers that are used to save
 829   // values across the instruction (e.g., for saving state register values).
 830   const hash_set<int>& regsUsed = MInst->getRegsUsed();
 831   for (hash_set<int>::const_iterator SI=regsUsed.begin(), SE=regsUsed.end();
 832        SI != SE; ++SI)
 833     {
 834       unsigned classId = 0;
 835       int classRegNum = MRI.getClassRegNum(*SI, classId);
 836       if (RC->getID() == classId)
 837         {
 838           assert(classRegNum < (int) IsColorUsedArr.size() &&
 839                  "Illegal register number for this reg class?");
 840           IsColorUsedArr[classRegNum] = true;
 841         }
 842     }
 843
 844   // Now add registers allocated to the live ranges of values used in
 845   // the instruction.  These are not yet recorded in the instruction.
 846   for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum)
 847     {
 848       const MachineOperand& Op = MInst->getOperand(OpNum);
 849
 850       if (Op.getOperandType() == MachineOperand::MO_VirtualRegister ||
 851           Op.getOperandType() == MachineOperand::MO_CCRegister)
 852         if (const Value* Val = Op.getVRegValue())
 853           if (MRI.getRegClassIDOfValue(Val) == RC->getID())
 854             if (Op.getAllocatedRegNum() == -1)
 855               if (LiveRange *LROfVal = LRI.getLiveRangeForValue(Val))
 856                 if (LROfVal->hasColor() )
 857                   // this operand is in a LR that received a color
 858                   IsColorUsedArr[LROfVal->getColor()] = true;
 859     }
 860
 861   // If there are implicit references, mark their allocated regs as well
 862   //
 863   for (unsigned z=0; z < MInst->getNumImplicitRefs(); z++)
 864     if (const LiveRange*
 865         LRofImpRef = LRI.getLiveRangeForValue(MInst->getImplicitRef(z)))
 866       if (LRofImpRef->hasColor())
 867         // this implicit reference is in a LR that received a color
 868         IsColorUsedArr[LRofImpRef->getColor()] = true;
 869 }
 870
 871
 872 //----------------------------------------------------------------------------
 873 // If there are delay slots for an instruction, the instructions
 874 // added after it must really go after the delayed instruction(s).
 875 // So, we move the InstrAfter of that instruction to the
 876 // corresponding delayed instruction using the following method.
 877
 878 //----------------------------------------------------------------------------
 879 void PhyRegAlloc::move2DelayedInstr(const MachineInstr *OrigMI,
 880                                     const MachineInstr *DelayedMI) {
 881
 882   // "added after" instructions of the original instr
 883   std::vector<MachineInstr *> &OrigAft = AddedInstrMap[OrigMI].InstrnsAfter;
 884
 885   // "added instructions" of the delayed instr
 886   AddedInstrns &DelayAdI = AddedInstrMap[DelayedMI];
 887
 888   // "added after" instructions of the delayed instr
 889   std::vector<MachineInstr *> &DelayedAft = DelayAdI.InstrnsAfter;
 890
 891   // go thru all the "added after instructions" of the original instruction
 892   // and append them to the "addded after instructions" of the delayed
 893   // instructions
 894   DelayedAft.insert(DelayedAft.end(), OrigAft.begin(), OrigAft.end());
 895
 896   // empty the "added after instructions" of the original instruction
 897   OrigAft.clear();
 898 }
 899
 900 //----------------------------------------------------------------------------
 901 // This method prints the code with registers after register allocation is
 902 // complete.
 903 //----------------------------------------------------------------------------
 904 void PhyRegAlloc::printMachineCode()
 905 {
 906
 907   cerr << "\n;************** Function " << Meth->getName()
 908        << " *****************\n";
 909
 910   for (Function::const_iterator BBI = Meth->begin(), BBE = Meth->end();
 911        BBI != BBE; ++BBI) {
 912     cerr << "\n"; printLabel(BBI); cerr << ": ";
 913
 914     // get the iterator for machine instructions
 915     MachineCodeForBasicBlock& MIVec = MachineCodeForBasicBlock::get(BBI);
 916     MachineCodeForBasicBlock::iterator MII = MIVec.begin();
 917
 918     // iterate over all the machine instructions in BB
 919     for ( ; MII != MIVec.end(); ++MII) {
 920       MachineInstr *const MInst = *MII;
 921
 922       cerr << "\n\t";
 923       cerr << TargetInstrDescriptors[MInst->getOpCode()].opCodeString;
 924
 925       for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
 926         MachineOperand& Op = MInst->getOperand(OpNum);
 927
 928         if (Op.getOperandType() ==  MachineOperand::MO_VirtualRegister ||
 929             Op.getOperandType() ==  MachineOperand::MO_CCRegister /*||
 930             Op.getOperandType() ==  MachineOperand::MO_PCRelativeDisp*/ ) {
 931
 932           const Value *const Val = Op.getVRegValue () ;
 933           // ****this code is temporary till NULL Values are fixed
 934           if (! Val ) {
 935             cerr << "\t<*NULL*>";
 936             continue;
 937           }
 938
 939           // if a label or a constant
 940           if (isa<BasicBlock>(Val)) {
 941             cerr << "\t"; printLabel(   Op.getVRegValue () );
 942           } else {
 943             // else it must be a register value
 944             const int RegNum = Op.getAllocatedRegNum();
 945
 946             cerr << "\t" << "%" << MRI.getUnifiedRegName( RegNum );
 947             if (Val->hasName() )
 948               cerr << "(" << Val->getName() << ")";
 949             else
 950               cerr << "(" << Val << ")";
 951
 952             if (Op.opIsDef() )
 953               cerr << "*";
 954
 955             const LiveRange *LROfVal = LRI.getLiveRangeForValue(Val);
 956             if (LROfVal )
 957               if (LROfVal->hasSpillOffset() )
 958                 cerr << "$";
 959           }
 960
 961         }
 962         else if (Op.getOperandType() ==  MachineOperand::MO_MachineRegister) {
 963           cerr << "\t" << "%" << MRI.getUnifiedRegName(Op.getMachineRegNum());
 964         }
 965
 966         else
 967           cerr << "\t" << Op;      // use dump field
 968       }
 969
 970
 971
 972       unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
 973       if (NumOfImpRefs > 0) {
 974         cerr << "\tImplicit:";
 975
 976         for (unsigned z=0; z < NumOfImpRefs; z++)
 977           cerr << RAV(MInst->getImplicitRef(z)) << "\t";
 978       }
 979
 980     } // for all machine instructions
 981
 982     cerr << "\n";
 983
 984   } // for all BBs
 985
 986   cerr << "\n";
 987 }
 988
 989
 990 //----------------------------------------------------------------------------
 991
 992 //----------------------------------------------------------------------------
 993 void PhyRegAlloc::colorIncomingArgs()
 994 {
 995   const BasicBlock &FirstBB = Meth->front();
 996   const MachineInstr *FirstMI = MachineCodeForBasicBlock::get(&FirstBB).front();
 997   assert(FirstMI && "No machine instruction in entry BB");
 998
 999   MRI.colorMethodArgs(Meth, LRI, &AddedInstrAtEntry);
1000 }
1001
1002
1003 //----------------------------------------------------------------------------
1004 // Used to generate a label for a basic block
1005 //----------------------------------------------------------------------------
1006 void PhyRegAlloc::printLabel(const Value *const Val) {
1007   if (Val->hasName())
1008     cerr  << Val->getName();
1009   else
1010     cerr << "Label" <<  Val;
1011 }
1012
1013
1014 //----------------------------------------------------------------------------
1015 // This method calls setSugColorUsable method of each live range. This
1016 // will determine whether the suggested color of LR is  really usable.
1017 // A suggested color is not usable when the suggested color is volatile
1018 // AND when there are call interferences
1019 //----------------------------------------------------------------------------
1020
1021 void PhyRegAlloc::markUnusableSugColors()
1022 {
1023   if (DEBUG_RA ) cerr << "\nmarking unusable suggested colors ...\n";
1024
1025   // hash map iterator
1026   LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
1027   LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
1028
1029     for (; HMI != HMIEnd ; ++HMI ) {
1030       if (HMI->first) {
1031         LiveRange *L = HMI->second;      // get the LiveRange
1032         if (L) {
1033           if (L->hasSuggestedColor()) {
1034             int RCID = L->getRegClass()->getID();
1035             if (MRI.isRegVolatile( RCID,  L->getSuggestedColor()) &&
1036                 L->isCallInterference() )
1037               L->setSuggestedColorUsable( false );
1038             else
1039               L->setSuggestedColorUsable( true );
1040           }
1041         } // if L->hasSuggestedColor()
1042       }
1043     } // for all LR's in hash map
1044 }
1045
1046
1047
1048 //----------------------------------------------------------------------------
1049 // The following method will set the stack offsets of the live ranges that
1050 // are decided to be spillled. This must be called just after coloring the
1051 // LRs using the graph coloring algo. For each live range that is spilled,
1052 // this method allocate a new spill position on the stack.
1053 //----------------------------------------------------------------------------
1054
1055 void PhyRegAlloc::allocateStackSpace4SpilledLRs() {
1056   if (DEBUG_RA) cerr << "\nsetting LR stack offsets ...\n";
1057
1058   LiveRangeMapType::const_iterator HMI    = LRI.getLiveRangeMap()->begin();
1059   LiveRangeMapType::const_iterator HMIEnd = LRI.getLiveRangeMap()->end();
1060
1061   for ( ; HMI != HMIEnd ; ++HMI) {
1062     if (HMI->first && HMI->second) {
1063       LiveRange *L = HMI->second;      // get the LiveRange
1064       if (!L->hasColor())   //  NOTE: ** allocating the size of long Type **
1065         L->setSpillOffFromFP(mcInfo.allocateSpilledValue(TM, Type::LongTy));
1066     }
1067   } // for all LR's in hash map
1068 }
1069
1070
1071
1072 //----------------------------------------------------------------------------
1073 // The entry pont to Register Allocation
1074 //----------------------------------------------------------------------------
1075
1076 void PhyRegAlloc::allocateRegisters()
1077 {
1078
1079   // make sure that we put all register classes into the RegClassList
1080   // before we call constructLiveRanges (now done in the constructor of
1081   // PhyRegAlloc class).
1082   //
1083   LRI.constructLiveRanges();            // create LR info
1084
1085   if (DEBUG_RA)
1086     LRI.printLiveRanges();
1087
1088   createIGNodeListsAndIGs();            // create IGNode list and IGs
1089
1090   buildInterferenceGraphs();            // build IGs in all reg classes
1091
1092
1093   if (DEBUG_RA) {
1094     // print all LRs in all reg classes
1095     for ( unsigned rc=0; rc < NumOfRegClasses  ; rc++)
1096       RegClassList[rc]->printIGNodeList();
1097
1098     // print IGs in all register classes
1099     for ( unsigned rc=0; rc < NumOfRegClasses ; rc++)
1100       RegClassList[rc]->printIG();
1101   }
1102
1103
1104   LRI.coalesceLRs();                    // coalesce all live ranges
1105
1106
1107   if (DEBUG_RA) {
1108     // print all LRs in all reg classes
1109     for ( unsigned rc=0; rc < NumOfRegClasses  ; rc++)
1110       RegClassList[ rc ]->printIGNodeList();
1111
1112     // print IGs in all register classes
1113     for ( unsigned rc=0; rc < NumOfRegClasses ; rc++)
1114       RegClassList[ rc ]->printIG();
1115   }
1116
1117
1118   // mark un-usable suggested color before graph coloring algorithm.
1119   // When this is done, the graph coloring algo will not reserve
1120   // suggested color unnecessarily - they can be used by another LR
1121   //
1122   markUnusableSugColors();
1123
1124   // color all register classes using the graph coloring algo
1125   for (unsigned rc=0; rc < NumOfRegClasses ; rc++)
1126     RegClassList[ rc ]->colorAllRegs();
1127
1128   // Atter grpah coloring, if some LRs did not receive a color (i.e, spilled)
1129   // a poistion for such spilled LRs
1130   //
1131   allocateStackSpace4SpilledLRs();
1132
1133   mcInfo.popAllTempValues(TM);  // TODO **Check
1134
1135   // color incoming args - if the correct color was not received
1136   // insert code to copy to the correct register
1137   //
1138   colorIncomingArgs();
1139
1140   // Now update the machine code with register names and add any
1141   // additional code inserted by the register allocator to the instruction
1142   // stream
1143   //
1144   updateMachineCode();
1145
1146   if (DEBUG_RA) {
1147     MachineCodeForMethod::get(Meth).dump();
1148     printMachineCode();                   // only for DEBUGGING
1149   }
1150 }
1151
1152
1153