lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp

   1 //===-- PhyRegAlloc.cpp ---------------------------------------------------===//
   2 //
   3 //  Register allocation for LLVM.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "llvm/CodeGen/RegisterAllocation.h"
   8 #include "RegAllocCommon.h"
   9 #include "RegClass.h"
  10 #include "llvm/CodeGen/IGNode.h"
  11 #include "llvm/CodeGen/PhyRegAlloc.h"
  12 #include "llvm/CodeGen/MachineInstrBuilder.h"
  13 #include "llvm/CodeGen/MachineInstrAnnot.h"
  14 #include "llvm/CodeGen/MachineFunction.h"
  15 #include "llvm/CodeGen/MachineFunctionInfo.h"
  16 #include "llvm/CodeGen/FunctionLiveVarInfo.h"
  17 #include "llvm/CodeGen/InstrSelection.h"
  18 #include "llvm/Analysis/LoopInfo.h"
  19 #include "llvm/Target/TargetMachine.h"
  20 #include "llvm/Target/TargetFrameInfo.h"
  21 #include "llvm/Target/TargetInstrInfo.h"
  22 #include "llvm/Target/TargetRegInfo.h"
  23 #include "llvm/Function.h"
  24 #include "llvm/Type.h"
  25 #include "llvm/iOther.h"
  26 #include "Support/STLExtras.h"
  27 #include "Support/CommandLine.h"
  28 #include <math.h>
  29 using std::cerr;
  30 using std::vector;
  31
  32 RegAllocDebugLevel_t DEBUG_RA;
  33
  34 static cl::opt<RegAllocDebugLevel_t, true>
  35 DRA_opt("dregalloc", cl::Hidden, cl::location(DEBUG_RA),
  36         cl::desc("enable register allocation debugging information"),
  37         cl::values(
  38   clEnumValN(RA_DEBUG_None   ,     "n", "disable debug output"),
  39   clEnumValN(RA_DEBUG_Results,     "y", "debug output for allocation results"),
  40   clEnumValN(RA_DEBUG_Coloring,    "c", "debug output for graph coloring step"),
  41   clEnumValN(RA_DEBUG_Interference,"ig","debug output for interference graphs"),
  42   clEnumValN(RA_DEBUG_LiveRanges , "lr","debug output for live ranges"),
  43   clEnumValN(RA_DEBUG_Verbose,     "v", "extra debug output"),
  44                    0));
  45
  46 //----------------------------------------------------------------------------
  47 // RegisterAllocation pass front end...
  48 //----------------------------------------------------------------------------
  49 namespace {
  50   class RegisterAllocator : public FunctionPass {
  51     TargetMachine &Target;
  52   public:
  53     inline RegisterAllocator(TargetMachine &T) : Target(T) {}
  54
  55     const char *getPassName() const { return "Register Allocation"; }
  56
  57     bool runOnFunction(Function &F) {
  58       if (DEBUG_RA)
  59         cerr << "\n********* Function "<< F.getName() << " ***********\n";
  60
  61       PhyRegAlloc PRA(&F, Target, &getAnalysis<FunctionLiveVarInfo>(),
  62                       &getAnalysis<LoopInfo>());
  63       PRA.allocateRegisters();
  64
  65       if (DEBUG_RA) cerr << "\nRegister allocation complete!\n";
  66       return false;
  67     }
  68
  69     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  70       AU.addRequired<LoopInfo>();
  71       AU.addRequired<FunctionLiveVarInfo>();
  72     }
  73   };
  74 }
  75
  76 Pass *getRegisterAllocator(TargetMachine &T) {
  77   return new RegisterAllocator(T);
  78 }
  79
  80 //----------------------------------------------------------------------------
  81 // Constructor: Init local composite objects and create register classes.
  82 //----------------------------------------------------------------------------
  83 PhyRegAlloc::PhyRegAlloc(Function *F, const TargetMachine& tm,
  84                          FunctionLiveVarInfo *Lvi, LoopInfo *LDC)
  85   :  TM(tm), Fn(F), MF(MachineFunction::get(F)), LVI(Lvi),
  86      LRI(F, tm, RegClassList), MRI(tm.getRegInfo()),
  87      NumOfRegClasses(MRI.getNumOfRegClasses()), 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, &tm.getRegInfo(),
  93                                         MRI.getMachineRegClass(rc)));
  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 >= RA_DEBUG_LiveRanges) 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 LIVE RANGE FOUND FOR: "
 126                << RAV(HMI->first) << "****\n";
 127         continue;
 128       }
 129
 130       // if the Value * is not null, and LR is not yet written to the IGNodeList
 131       if (!(L->getUserIGNode())  ) {
 132         RegClass *const RC =           // RegClass of first value in the LR
 133           RegClassList[ L->getRegClass()->getID() ];
 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 >= RA_DEBUG_LiveRanges) cerr << "LRLists Created!\n";
 144 }
 145
 146
 147 //----------------------------------------------------------------------------
 148 // This method will add all interferences at for a given instruction.
 149 // Interence occurs only if the LR of Def (Inst or Arg) is of the same reg
 150 // class as that of live var. The live var passed to this function is the
 151 // LVset AFTER the instruction
 152 //----------------------------------------------------------------------------
 153
 154 void PhyRegAlloc::addInterference(const Value *Def,
 155                                   const ValueSet *LVSet,
 156                                   bool isCallInst) {
 157
 158   ValueSet::const_iterator LIt = LVSet->begin();
 159
 160   // get the live range of instruction
 161   //
 162   const LiveRange *const LROfDef = LRI.getLiveRangeForValue( Def );
 163
 164   IGNode *const IGNodeOfDef = LROfDef->getUserIGNode();
 165   assert( IGNodeOfDef );
 166
 167   RegClass *const RCOfDef = LROfDef->getRegClass();
 168
 169   // for each live var in live variable set
 170   //
 171   for ( ; LIt != LVSet->end(); ++LIt) {
 172
 173     if (DEBUG_RA >= RA_DEBUG_Verbose)
 174       cerr << "< Def=" << RAV(Def) << ", Lvar=" << RAV(*LIt) << "> ";
 175
 176     //  get the live range corresponding to live var
 177     //
 178     LiveRange *LROfVar = LRI.getLiveRangeForValue(*LIt);
 179
 180     // LROfVar can be null if it is a const since a const
 181     // doesn't have a dominating def - see Assumptions above
 182     //
 183     if (LROfVar)
 184       if (LROfDef != LROfVar)                  // do not set interf for same LR
 185         if (RCOfDef == LROfVar->getRegClass()) // 2 reg classes are the same
 186           RCOfDef->setInterference( LROfDef, LROfVar);
 187   }
 188 }
 189
 190
 191
 192 //----------------------------------------------------------------------------
 193 // For a call instruction, this method sets the CallInterference flag in
 194 // the LR of each variable live int the Live Variable Set live after the
 195 // call instruction (except the return value of the call instruction - since
 196 // the return value does not interfere with that call itself).
 197 //----------------------------------------------------------------------------
 198
 199 void PhyRegAlloc::setCallInterferences(const MachineInstr *MInst,
 200                                        const ValueSet *LVSetAft) {
 201
 202   if (DEBUG_RA >= RA_DEBUG_Interference)
 203     cerr << "\n For call inst: " << *MInst;
 204
 205   // for each live var in live variable set after machine inst
 206   //
 207   for (ValueSet::const_iterator LIt = LVSetAft->begin(), LEnd = LVSetAft->end();
 208        LIt != LEnd; ++LIt) {
 209
 210     //  get the live range corresponding to live var
 211     //
 212     LiveRange *const LR = LRI.getLiveRangeForValue(*LIt );
 213
 214     // LR can be null if it is a const since a const
 215     // doesn't have a dominating def - see Assumptions above
 216     //
 217     if (LR ) {
 218       if (DEBUG_RA >= RA_DEBUG_Interference) {
 219         cerr << "\n\tLR after Call: ";
 220         printSet(*LR);
 221       }
 222       LR->setCallInterference();
 223       if (DEBUG_RA >= RA_DEBUG_Interference) {
 224         cerr << "\n  ++After adding call interference for LR: " ;
 225         printSet(*LR);
 226       }
 227     }
 228
 229   }
 230
 231   // Now find the LR of the return value of the call
 232   // We do this because, we look at the LV set *after* the instruction
 233   // to determine, which LRs must be saved across calls. The return value
 234   // of the call is live in this set - but it does not interfere with call
 235   // (i.e., we can allocate a volatile register to the return value)
 236   //
 237   CallArgsDescriptor* argDesc = CallArgsDescriptor::get(MInst);
 238
 239   if (const Value *RetVal = argDesc->getReturnValue()) {
 240     LiveRange *RetValLR = LRI.getLiveRangeForValue( RetVal );
 241     assert( RetValLR && "No LR for RetValue of call");
 242     RetValLR->clearCallInterference();
 243   }
 244
 245   // If the CALL is an indirect call, find the LR of the function pointer.
 246   // That has a call interference because it conflicts with outgoing args.
 247   if (const Value *AddrVal = argDesc->getIndirectFuncPtr()) {
 248     LiveRange *AddrValLR = LRI.getLiveRangeForValue( AddrVal );
 249     assert( AddrValLR && "No LR for indirect addr val of call");
 250     AddrValLR->setCallInterference();
 251   }
 252
 253 }
 254
 255
 256
 257
 258 //----------------------------------------------------------------------------
 259 // This method will walk thru code and create interferences in the IG of
 260 // each RegClass. Also, this method calculates the spill cost of each
 261 // Live Range (it is done in this method to save another pass over the code).
 262 //----------------------------------------------------------------------------
 263 void PhyRegAlloc::buildInterferenceGraphs()
 264 {
 265
 266   if (DEBUG_RA >= RA_DEBUG_Interference)
 267     cerr << "Creating interference graphs ...\n";
 268
 269   unsigned BBLoopDepthCost;
 270   for (MachineFunction::iterator BBI = MF.begin(), BBE = MF.end();
 271        BBI != BBE; ++BBI) {
 272     const MachineBasicBlock &MBB = *BBI;
 273     const BasicBlock *BB = MBB.getBasicBlock();
 274
 275     // find the 10^(loop_depth) of this BB
 276     //
 277     BBLoopDepthCost = (unsigned)pow(10.0, LoopDepthCalc->getLoopDepth(BB));
 278
 279     // get the iterator for machine instructions
 280     //
 281     MachineBasicBlock::const_iterator MII = MBB.begin();
 282
 283     // iterate over all the machine instructions in BB
 284     //
 285     for ( ; MII != MBB.end(); ++MII) {
 286       const MachineInstr *MInst = *MII;
 287
 288       // get the LV set after the instruction
 289       //
 290       const ValueSet &LVSetAI = LVI->getLiveVarSetAfterMInst(MInst, BB);
 291       bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpCode());
 292
 293       if (isCallInst ) {
 294         // set the isCallInterference flag of each live range wich extends
 295         // accross this call instruction. This information is used by graph
 296         // coloring algo to avoid allocating volatile colors to live ranges
 297         // that span across calls (since they have to be saved/restored)
 298         //
 299         setCallInterferences(MInst, &LVSetAI);
 300       }
 301
 302       // iterate over all MI operands to find defs
 303       //
 304       for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
 305              OpE = MInst->end(); OpI != OpE; ++OpI) {
 306         if (OpI.isDefOnly() || OpI.isDefAndUse()) // create a new LR since def
 307           addInterference(*OpI, &LVSetAI, isCallInst);
 308
 309         // Calculate the spill cost of each live range
 310         //
 311         LiveRange *LR = LRI.getLiveRangeForValue(*OpI);
 312         if (LR) LR->addSpillCost(BBLoopDepthCost);
 313       }
 314
 315
 316       // if there are multiple defs in this instruction e.g. in SETX
 317       //
 318       if (TM.getInstrInfo().isPseudoInstr(MInst->getOpCode()))
 319         addInterf4PseudoInstr(MInst);
 320
 321
 322       // Also add interference for any implicit definitions in a machine
 323       // instr (currently, only calls have this).
 324       //
 325       unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
 326       for (unsigned z=0; z < NumOfImpRefs; z++)
 327         if (MInst->getImplicitOp(z).opIsDefOnly() ||
 328             MInst->getImplicitOp(z).opIsDefAndUse())
 329           addInterference( MInst->getImplicitRef(z), &LVSetAI, isCallInst );
 330
 331     } // for all machine instructions in BB
 332   } // for all BBs in function
 333
 334
 335   // add interferences for function arguments. Since there are no explict
 336   // defs in the function for args, we have to add them manually
 337   //
 338   addInterferencesForArgs();
 339
 340   if (DEBUG_RA >= RA_DEBUG_Interference)
 341     cerr << "Interference graphs calculated!\n";
 342 }
 343
 344
 345
 346 //--------------------------------------------------------------------------
 347 // Pseudo instructions will be exapnded to multiple instructions by the
 348 // assembler. Consequently, all the opernds must get distinct registers.
 349 // Therefore, we mark all operands of a pseudo instruction as they interfere
 350 // with one another.
 351 //--------------------------------------------------------------------------
 352 void PhyRegAlloc::addInterf4PseudoInstr(const MachineInstr *MInst) {
 353
 354   bool setInterf = false;
 355
 356   // iterate over  MI operands to find defs
 357   //
 358   for (MachineInstr::const_val_op_iterator It1 = MInst->begin(),
 359          ItE = MInst->end(); It1 != ItE; ++It1) {
 360     const LiveRange *LROfOp1 = LRI.getLiveRangeForValue(*It1);
 361     assert((LROfOp1 || !It1.isUseOnly())&& "No LR for Def in PSEUDO insruction");
 362
 363     MachineInstr::const_val_op_iterator It2 = It1;
 364     for (++It2; It2 != ItE; ++It2) {
 365       const LiveRange *LROfOp2 = LRI.getLiveRangeForValue(*It2);
 366
 367       if (LROfOp2) {
 368         RegClass *RCOfOp1 = LROfOp1->getRegClass();
 369         RegClass *RCOfOp2 = LROfOp2->getRegClass();
 370
 371         if (RCOfOp1 == RCOfOp2 ){
 372           RCOfOp1->setInterference( LROfOp1, LROfOp2 );
 373           setInterf = true;
 374         }
 375       } // if Op2 has a LR
 376     } // for all other defs in machine instr
 377   } // for all operands in an instruction
 378
 379   if (!setInterf && MInst->getNumOperands() > 2) {
 380     cerr << "\nInterf not set for any operand in pseudo instr:\n";
 381     cerr << *MInst;
 382     assert(0 && "Interf not set for pseudo instr with > 2 operands" );
 383   }
 384 }
 385
 386
 387
 388 //----------------------------------------------------------------------------
 389 // This method will add interferences for incoming arguments to a function.
 390 //----------------------------------------------------------------------------
 391
 392 void PhyRegAlloc::addInterferencesForArgs() {
 393   // get the InSet of root BB
 394   const ValueSet &InSet = LVI->getInSetOfBB(&Fn->front());
 395
 396   for (Function::const_aiterator AI = Fn->abegin(); AI != Fn->aend(); ++AI) {
 397     // add interferences between args and LVars at start
 398     addInterference(AI, &InSet, false);
 399
 400     if (DEBUG_RA >= RA_DEBUG_Interference)
 401       cerr << " - %% adding interference for  argument " << RAV(AI) << "\n";
 402   }
 403 }
 404
 405
 406 //----------------------------------------------------------------------------
 407 // This method is called after register allocation is complete to set the
 408 // allocated reisters in the machine code. This code will add register numbers
 409 // to MachineOperands that contain a Value. Also it calls target specific
 410 // methods to produce caller saving instructions. At the end, it adds all
 411 // additional instructions produced by the register allocator to the
 412 // instruction stream.
 413 //----------------------------------------------------------------------------
 414
 415 //-----------------------------
 416 // Utility functions used below
 417 //-----------------------------
 418 inline void
 419 InsertBefore(MachineInstr* newMI,
 420              MachineBasicBlock& MBB,
 421              MachineBasicBlock::iterator& MII)
 422 {
 423   MII = MBB.insert(MII, newMI);
 424   ++MII;
 425 }
 426
 427 inline void
 428 InsertAfter(MachineInstr* newMI,
 429             MachineBasicBlock& MBB,
 430             MachineBasicBlock::iterator& MII)
 431 {
 432   ++MII;    // insert before the next instruction
 433   MII = MBB.insert(MII, newMI);
 434 }
 435
 436 inline void
 437 DeleteInstruction(MachineBasicBlock& MBB,
 438                   MachineBasicBlock::iterator& MII)
 439 {
 440   MII = MBB.erase(MII);
 441 }
 442
 443 inline void
 444 SubstituteInPlace(MachineInstr* newMI,
 445                   MachineBasicBlock& MBB,
 446                   MachineBasicBlock::iterator MII)
 447 {
 448   *MII = newMI;
 449 }
 450
 451 inline void
 452 PrependInstructions(vector<MachineInstr *> &IBef,
 453                     MachineBasicBlock& MBB,
 454                     MachineBasicBlock::iterator& MII,
 455                     const std::string& msg)
 456 {
 457   if (!IBef.empty())
 458     {
 459       MachineInstr* OrigMI = *MII;
 460       std::vector<MachineInstr *>::iterator AdIt;
 461       for (AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt)
 462         {
 463           if (DEBUG_RA) {
 464             if (OrigMI) cerr << "For MInst:\n  " << *OrigMI;
 465             cerr << msg << "PREPENDed instr:\n  " << **AdIt << "\n";
 466           }
 467           InsertBefore(*AdIt, MBB, MII);
 468         }
 469     }
 470 }
 471
 472 inline void
 473 AppendInstructions(std::vector<MachineInstr *> &IAft,
 474                    MachineBasicBlock& MBB,
 475                    MachineBasicBlock::iterator& MII,
 476                    const std::string& msg)
 477 {
 478   if (!IAft.empty())
 479     {
 480       MachineInstr* OrigMI = *MII;
 481       std::vector<MachineInstr *>::iterator AdIt;
 482       for ( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt )
 483         {
 484           if (DEBUG_RA) {
 485             if (OrigMI) cerr << "For MInst:\n  " << *OrigMI;
 486             cerr << msg << "APPENDed instr:\n  "  << **AdIt << "\n";
 487           }
 488           InsertAfter(*AdIt, MBB, MII);
 489         }
 490     }
 491 }
 492
 493 static bool MarkAllocatedRegs(MachineInstr* MInst,
 494                               LiveRangeInfo& LRI,
 495                               const TargetRegInfo& MRI)
 496 {
 497   bool instrNeedsSpills = false;
 498
 499   // First, set the registers for operands in the machine instruction
 500   // if a register was successfully allocated.  Do this first because we
 501   // will need to know which registers are already used by this instr'n.
 502   //
 503   for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum)
 504     {
 505       MachineOperand& Op = MInst->getOperand(OpNum);
 506       if (Op.getType() ==  MachineOperand::MO_VirtualRegister ||
 507           Op.getType() ==  MachineOperand::MO_CCRegister)
 508         {
 509           const Value *const Val =  Op.getVRegValue();
 510           if (const LiveRange* LR = LRI.getLiveRangeForValue(Val)) {
 511             // Remember if any operand needs spilling
 512             instrNeedsSpills |= LR->isMarkedForSpill();
 513
 514             // An operand may have a color whether or not it needs spilling
 515             if (LR->hasColor())
 516               MInst->SetRegForOperand(OpNum,
 517                           MRI.getUnifiedRegNum(LR->getRegClass()->getID(),
 518                                                LR->getColor()));
 519           }
 520         }
 521     } // for each operand
 522
 523   return instrNeedsSpills;
 524 }
 525
 526 void PhyRegAlloc::updateInstruction(MachineBasicBlock::iterator& MII,
 527                                     MachineBasicBlock &MBB)
 528 {
 529   MachineInstr* MInst = *MII;
 530   unsigned Opcode = MInst->getOpCode();
 531
 532   // Reset tmp stack positions so they can be reused for each machine instr.
 533   MF.getInfo()->popAllTempValues();
 534
 535   // Mark the operands for which regs have been allocated.
 536   bool instrNeedsSpills = MarkAllocatedRegs(*MII, LRI, MRI);
 537
 538 #ifndef NDEBUG
 539   // Mark that the operands have been updated.  Later,
 540   // setRelRegsUsedByThisInst() is called to find registers used by each
 541   // MachineInst, and it should not be used for an instruction until
 542   // this is done.  This flag just serves as a sanity check.
 543   OperandsColoredMap[MInst] = true;
 544 #endif
 545
 546   // Now insert caller-saving code before/after the call.
 547   // Do this before inserting spill code since some registers must be
 548   // used by save/restore and spill code should not use those registers.
 549   //
 550   if (TM.getInstrInfo().isCall(Opcode)) {
 551     AddedInstrns &AI = AddedInstrMap[MInst];
 552     insertCallerSavingCode(AI.InstrnsBefore, AI.InstrnsAfter, MInst,
 553                            MBB.getBasicBlock());
 554   }
 555
 556   // Now insert spill code for remaining operands not allocated to
 557   // registers.  This must be done even for call return instructions
 558   // since those are not handled by the special code above.
 559   if (instrNeedsSpills)
 560     for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum)
 561       {
 562         MachineOperand& Op = MInst->getOperand(OpNum);
 563         if (Op.getType() ==  MachineOperand::MO_VirtualRegister ||
 564             Op.getType() ==  MachineOperand::MO_CCRegister)
 565           {
 566             const Value* Val = Op.getVRegValue();
 567             if (const LiveRange *LR = LRI.getLiveRangeForValue(Val))
 568               if (LR->isMarkedForSpill())
 569                 insertCode4SpilledLR(LR, MII, MBB, OpNum);
 570           }
 571       } // for each operand
 572 }
 573
 574 void PhyRegAlloc::updateMachineCode()
 575 {
 576   // Insert any instructions needed at method entry
 577   MachineBasicBlock::iterator MII = MF.front().begin();
 578   PrependInstructions(AddedInstrAtEntry.InstrnsBefore, MF.front(), MII,
 579                       "At function entry: \n");
 580   assert(AddedInstrAtEntry.InstrnsAfter.empty() &&
 581          "InstrsAfter should be unnecessary since we are just inserting at "
 582          "the function entry point here.");
 583
 584   for (MachineFunction::iterator BBI = MF.begin(), BBE = MF.end();
 585        BBI != BBE; ++BBI) {
 586
 587     MachineBasicBlock &MBB = *BBI;
 588
 589     // Iterate over all machine instructions in BB and mark operands with
 590     // their assigned registers or insert spill code, as appropriate.
 591     // Also, fix operands of call/return instructions.
 592     for (MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII)
 593       if (! TM.getInstrInfo().isDummyPhiInstr((*MII)->getOpCode()))
 594         updateInstruction(MII, MBB);
 595
 596     // Now, move code out of delay slots of branches and returns if needed.
 597     // (Also, move "after" code from calls to the last delay slot instruction.)
 598     // Moving code out of delay slots is needed in 2 situations:
 599     // (1) If this is a branch and it needs instructions inserted after it,
 600     //     move any existing instructions out of the delay slot so that the
 601     //     instructions can go into the delay slot.  This only supports the
 602     //     case that #instrsAfter <= #delay slots.
 603     //
 604     // (2) If any instruction in the delay slot needs
 605     //     instructions inserted, move it out of the delay slot and before the
 606     //     branch because putting code before or after it would be VERY BAD!
 607     //
 608     // If the annul bit of the branch is set, neither of these is legal!
 609     // If so, we need to handle spill differently but annulling is not yet used.
 610     //
 611     for (MachineBasicBlock::iterator MII = MBB.begin();
 612          MII != MBB.end(); ++MII)
 613       if (unsigned delaySlots =
 614           TM.getInstrInfo().getNumDelaySlots((*MII)->getOpCode()))
 615         {
 616           MachineInstr *MInst = *MII, *DelaySlotMI = *(MII+1);
 617
 618           // Check the 2 conditions above:
 619           // (1) Does a branch need instructions added after it?
 620           // (2) O/w does delay slot instr. need instrns before or after?
 621           bool isBranch = (TM.getInstrInfo().isBranch(MInst->getOpCode()) ||
 622                            TM.getInstrInfo().isReturn(MInst->getOpCode()));
 623           bool cond1 = (isBranch &&
 624                         AddedInstrMap.count(MInst) &&
 625                         AddedInstrMap[MInst].InstrnsAfter.size() > 0);
 626           bool cond2 = (AddedInstrMap.count(DelaySlotMI) &&
 627                         (AddedInstrMap[DelaySlotMI].InstrnsBefore.size() > 0 ||
 628                          AddedInstrMap[DelaySlotMI].InstrnsAfter.size()  > 0));
 629
 630           if (cond1 || cond2)
 631             {
 632               assert((MInst->getOpCodeFlags() & AnnulFlag) == 0 &&
 633                      "FIXME: Moving an annulled delay slot instruction!");
 634               assert(delaySlots==1 &&
 635                      "InsertBefore does not yet handle >1 delay slots!");
 636               InsertBefore(DelaySlotMI, MBB, MII); // MII pts back to branch
 637
 638               // In case (1), delete it and don't replace with anything!
 639               // Otherwise (i.e., case (2) only) replace it with a NOP.
 640               if (cond1) {
 641                 DeleteInstruction(MBB, ++MII); // MII now points to next inst.
 642                 --MII;                         // reset MII for ++MII of loop
 643               }
 644               else
 645                 SubstituteInPlace(BuildMI(TM.getInstrInfo().getNOPOpCode(),1),
 646                                   MBB, MII+1);        // replace with NOP
 647
 648               if (DEBUG_RA) {
 649                 cerr << "\nRegAlloc: Moved instr. with added code: "
 650                      << *DelaySlotMI
 651                      << "           out of delay slots of instr: " << *MInst;
 652               }
 653             }
 654           else
 655             // For non-branch instr with delay slots (probably a call), move
 656             // InstrAfter to the instr. in the last delay slot.
 657             move2DelayedInstr(*MII, *(MII+delaySlots));
 658         }
 659
 660     // Finally iterate over all instructions in BB and insert before/after
 661     //
 662     for (MachineBasicBlock::iterator MII=MBB.begin(); MII != MBB.end(); ++MII) {
 663       MachineInstr *MInst = *MII;
 664
 665       // do not process Phis
 666       if (TM.getInstrInfo().isDummyPhiInstr(MInst->getOpCode()))
 667         continue;
 668
 669       // if there are any added instructions...
 670       if (AddedInstrMap.count(MInst)) {
 671         AddedInstrns &CallAI = AddedInstrMap[MInst];
 672
 673 #ifndef NDEBUG
 674         bool isBranch = (TM.getInstrInfo().isBranch(MInst->getOpCode()) ||
 675                          TM.getInstrInfo().isReturn(MInst->getOpCode()));
 676         assert((!isBranch ||
 677                 AddedInstrMap[MInst].InstrnsAfter.size() <=
 678                 TM.getInstrInfo().getNumDelaySlots(MInst->getOpCode())) &&
 679                "Cannot put more than #delaySlots instrns after "
 680                "branch or return! Need to handle temps differently.");
 681 #endif
 682
 683 #ifndef NDEBUG
 684         // Temporary sanity checking code to detect whether the same machine
 685         // instruction is ever inserted twice before/after a call.
 686         // I suspect this is happening but am not sure. --Vikram, 7/1/03.
 687         //
 688         std::set<const MachineInstr*> instrsSeen;
 689         for (int i = 0, N = CallAI.InstrnsBefore.size(); i < N; ++i) {
 690           assert(instrsSeen.count(CallAI.InstrnsBefore[i]) == 0 &&
 691                  "Duplicate machine instruction in InstrnsBefore!");
 692           instrsSeen.insert(CallAI.InstrnsBefore[i]);
 693         }
 694         for (int i = 0, N = CallAI.InstrnsAfter.size(); i < N; ++i) {
 695           assert(instrsSeen.count(CallAI.InstrnsAfter[i]) == 0 &&
 696                  "Duplicate machine instruction in InstrnsBefore/After!");
 697           instrsSeen.insert(CallAI.InstrnsAfter[i]);
 698         }
 699 #endif
 700
 701         // Now add the instructions before/after this MI.
 702         // We do this here to ensure that spill for an instruction is inserted
 703         // as close as possible to an instruction (see above insertCode4Spill)
 704         //
 705         if (! CallAI.InstrnsBefore.empty())
 706           PrependInstructions(CallAI.InstrnsBefore, MBB, MII,"");
 707
 708         if (! CallAI.InstrnsAfter.empty())
 709           AppendInstructions(CallAI.InstrnsAfter, MBB, MII,"");
 710
 711       } // if there are any added instructions
 712
 713     } // for each machine instruction
 714
 715   }
 716 }
 717
 718
 719
 720 //----------------------------------------------------------------------------
 721 // This method inserts spill code for AN operand whose LR was spilled.
 722 // This method may be called several times for a single machine instruction
 723 // if it contains many spilled operands. Each time it is called, it finds
 724 // a register which is not live at that instruction and also which is not
 725 // used by other spilled operands of the same instruction. Then it uses
 726 // this register temporarily to accomodate the spilled value.
 727 //----------------------------------------------------------------------------
 728
 729 void PhyRegAlloc::insertCode4SpilledLR(const LiveRange *LR,
 730                                        MachineBasicBlock::iterator& MII,
 731                                        MachineBasicBlock &MBB,
 732                                        const unsigned OpNum) {
 733
 734   MachineInstr *MInst = *MII;
 735   const BasicBlock *BB = MBB.getBasicBlock();
 736
 737   assert((! TM.getInstrInfo().isCall(MInst->getOpCode()) || OpNum == 0) &&
 738          "Outgoing arg of a call must be handled elsewhere (func arg ok)");
 739   assert(! TM.getInstrInfo().isReturn(MInst->getOpCode()) &&
 740          "Return value of a ret must be handled elsewhere");
 741
 742   MachineOperand& Op = MInst->getOperand(OpNum);
 743   bool isDef =  Op.opIsDefOnly();
 744   bool isDefAndUse = Op.opIsDefAndUse();
 745   unsigned RegType = MRI.getRegTypeForLR(LR);
 746   int SpillOff = LR->getSpillOffFromFP();
 747   RegClass *RC = LR->getRegClass();
 748
 749   // Get the live-variable set to find registers free before this instr.
 750   // If this instr. is in the delay slot of a branch or return, use the live
 751   // var set before that branch or return -- we don't want to trample those!
 752   //
 753   MachineInstr *LiveBeforeThisMI = MInst;
 754   if (MII != MBB.begin()) {
 755     MachineInstr *PredMI = *(MII-1);
 756     if (unsigned DS = TM.getInstrInfo().getNumDelaySlots(PredMI->getOpCode())) {
 757       assert(DS == 1 && "Only checking immediate pred. for delay slots!");
 758       LiveBeforeThisMI = PredMI;
 759     }
 760   }
 761   const ValueSet &LVSetBef = LVI->getLiveVarSetBeforeMInst(LiveBeforeThisMI,BB);
 762
 763   MF.getInfo()->pushTempValue(MRI.getSpilledRegSize(RegType) );
 764
 765   vector<MachineInstr*> MIBef, MIAft;
 766   vector<MachineInstr*> AdIMid;
 767
 768   // Choose a register to hold the spilled value, if one was not preallocated.
 769   // This may insert code before and after MInst to free up the value.  If so,
 770   // this code should be first/last in the spill sequence before/after MInst.
 771   int TmpRegU=(LR->hasColor()
 772                ? MRI.getUnifiedRegNum(LR->getRegClass()->getID(),LR->getColor())
 773                : getUsableUniRegAtMI(RegType, &LVSetBef, MInst, MIBef,MIAft));
 774
 775   // Set the operand first so that it this register does not get used
 776   // as a scratch register for later calls to getUsableUniRegAtMI below
 777   MInst->SetRegForOperand(OpNum, TmpRegU);
 778
 779   // get the added instructions for this instruction
 780   AddedInstrns &AI = AddedInstrMap[MInst];
 781
 782   // We may need a scratch register to copy the spilled value to/from memory.
 783   // This may itself have to insert code to free up a scratch register.
 784   // Any such code should go before (after) the spill code for a load (store).
 785   // The scratch reg is not marked as used because it is only used
 786   // for the copy and not used across MInst.
 787   int scratchRegType = -1;
 788   int scratchReg = -1;
 789   if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
 790     {
 791       scratchReg = getUsableUniRegAtMI(scratchRegType, &LVSetBef,
 792                                        MInst, MIBef, MIAft);
 793       assert(scratchReg != MRI.getInvalidRegNum());
 794     }
 795
 796   if (!isDef || isDefAndUse) {
 797     // for a USE, we have to load the value of LR from stack to a TmpReg
 798     // and use the TmpReg as one operand of instruction
 799
 800     // actual loading instruction(s)
 801     MRI.cpMem2RegMI(AdIMid, MRI.getFramePointer(), SpillOff, TmpRegU,
 802                     RegType, scratchReg);
 803
 804     // the actual load should be after the instructions to free up TmpRegU
 805     MIBef.insert(MIBef.end(), AdIMid.begin(), AdIMid.end());
 806     AdIMid.clear();
 807   }
 808
 809   if (isDef || isDefAndUse) {   // if this is a Def
 810     // for a DEF, we have to store the value produced by this instruction
 811     // on the stack position allocated for this LR
 812
 813     // actual storing instruction(s)
 814     MRI.cpReg2MemMI(AdIMid, TmpRegU, MRI.getFramePointer(), SpillOff,
 815                     RegType, scratchReg);
 816
 817     MIAft.insert(MIAft.begin(), AdIMid.begin(), AdIMid.end());
 818   }  // if !DEF
 819
 820   // Finally, insert the entire spill code sequences before/after MInst
 821   AI.InstrnsBefore.insert(AI.InstrnsBefore.end(), MIBef.begin(), MIBef.end());
 822   AI.InstrnsAfter.insert(AI.InstrnsAfter.begin(), MIAft.begin(), MIAft.end());
 823
 824   if (DEBUG_RA) {
 825     cerr << "\nFor Inst:\n  " << *MInst;
 826     cerr << "SPILLED LR# " << LR->getUserIGNode()->getIndex();
 827     cerr << "; added Instructions:";
 828     for_each(MIBef.begin(), MIBef.end(), std::mem_fun(&MachineInstr::dump));
 829     for_each(MIAft.begin(), MIAft.end(), std::mem_fun(&MachineInstr::dump));
 830   }
 831 }
 832
 833
 834
 835 //----------------------------------------------------------------------------
 836 // This method inserts caller saving/restoring instructons before/after
 837 // a call machine instruction. The caller saving/restoring instructions are
 838 // inserted like:
 839 //    ** caller saving instructions
 840 //    other instructions inserted for the call by ColorCallArg
 841 //    CALL instruction
 842 //    other instructions inserted for the call ColorCallArg
 843 //    ** caller restoring instructions
 844 //----------------------------------------------------------------------------
 845
 846 void
 847 PhyRegAlloc::insertCallerSavingCode(std::vector<MachineInstr*> &instrnsBefore,
 848                                     std::vector<MachineInstr*> &instrnsAfter,
 849                                     MachineInstr *CallMI,
 850                                     const BasicBlock *BB)
 851 {
 852   assert(TM.getInstrInfo().isCall(CallMI->getOpCode()));
 853
 854   // has set to record which registers were saved/restored
 855   //
 856   hash_set<unsigned> PushedRegSet;
 857
 858   CallArgsDescriptor* argDesc = CallArgsDescriptor::get(CallMI);
 859
 860   // if the call is to a instrumentation function, do not insert save and
 861   // restore instructions the instrumentation function takes care of save
 862   // restore for volatile regs.
 863   //
 864   // FIXME: this should be made general, not specific to the reoptimizer!
 865   //
 866   const Function *Callee = argDesc->getCallInst()->getCalledFunction();
 867   bool isLLVMFirstTrigger = Callee && Callee->getName() == "llvm_first_trigger";
 868
 869   // Now check if the call has a return value (using argDesc) and if so,
 870   // find the LR of the TmpInstruction representing the return value register.
 871   // (using the last or second-last *implicit operand* of the call MI).
 872   // Insert it to to the PushedRegSet since we must not save that register
 873   // and restore it after the call.
 874   // We do this because, we look at the LV set *after* the instruction
 875   // to determine, which LRs must be saved across calls. The return value
 876   // of the call is live in this set - but we must not save/restore it.
 877   //
 878   if (const Value *origRetVal = argDesc->getReturnValue()) {
 879     unsigned retValRefNum = (CallMI->getNumImplicitRefs() -
 880                              (argDesc->getIndirectFuncPtr()? 1 : 2));
 881     const TmpInstruction* tmpRetVal =
 882       cast<TmpInstruction>(CallMI->getImplicitRef(retValRefNum));
 883     assert(tmpRetVal->getOperand(0) == origRetVal &&
 884            tmpRetVal->getType() == origRetVal->getType() &&
 885            "Wrong implicit ref?");
 886     LiveRange *RetValLR = LRI.getLiveRangeForValue(tmpRetVal);
 887     assert(RetValLR && "No LR for RetValue of call");
 888
 889     if (! RetValLR->isMarkedForSpill())
 890       PushedRegSet.insert(MRI.getUnifiedRegNum(RetValLR->getRegClassID(),
 891                                                RetValLR->getColor()));
 892   }
 893
 894   const ValueSet &LVSetAft =  LVI->getLiveVarSetAfterMInst(CallMI, BB);
 895   ValueSet::const_iterator LIt = LVSetAft.begin();
 896
 897   // for each live var in live variable set after machine inst
 898   for( ; LIt != LVSetAft.end(); ++LIt) {
 899
 900    //  get the live range corresponding to live var
 901     LiveRange *const LR = LRI.getLiveRangeForValue(*LIt);
 902
 903     // LR can be null if it is a const since a const
 904     // doesn't have a dominating def - see Assumptions above
 905     if( LR )   {
 906
 907       if(! LR->isMarkedForSpill()) {
 908
 909         assert(LR->hasColor() && "LR is neither spilled nor colored?");
 910         unsigned RCID = LR->getRegClassID();
 911         unsigned Color = LR->getColor();
 912
 913         if (MRI.isRegVolatile(RCID, Color) ) {
 914
 915           //if the function is special LLVM function,
 916           //And the register is not modified by call, don't save and restore
 917           if (isLLVMFirstTrigger && !MRI.modifiedByCall(RCID, Color))
 918             continue;
 919
 920           // if the value is in both LV sets (i.e., live before and after
 921           // the call machine instruction)
 922
 923           unsigned Reg = MRI.getUnifiedRegNum(RCID, Color);
 924
 925           if( PushedRegSet.find(Reg) == PushedRegSet.end() ) {
 926
 927             // if we haven't already pushed that register
 928
 929             unsigned RegType = MRI.getRegTypeForLR(LR);
 930
 931             // Now get two instructions - to push on stack and pop from stack
 932             // and add them to InstrnsBefore and InstrnsAfter of the
 933             // call instruction
 934             //
 935             int StackOff =
 936               MF.getInfo()->pushTempValue(MRI.getSpilledRegSize(RegType));
 937
 938             //---- Insert code for pushing the reg on stack ----------
 939
 940             std::vector<MachineInstr*> AdIBef, AdIAft;
 941
 942             // We may need a scratch register to copy the saved value
 943             // to/from memory.  This may itself have to insert code to
 944             // free up a scratch register.  Any such code should go before
 945             // the save code.  The scratch register, if any, is by default
 946             // temporary and not "used" by the instruction unless the
 947             // copy code itself decides to keep the value in the scratch reg.
 948             int scratchRegType = -1;
 949             int scratchReg = -1;
 950             if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
 951               { // Find a register not live in the LVSet before CallMI
 952                 const ValueSet &LVSetBef =
 953                   LVI->getLiveVarSetBeforeMInst(CallMI, BB);
 954                 scratchReg = getUsableUniRegAtMI(scratchRegType, &LVSetBef,
 955                                                  CallMI, AdIBef, AdIAft);
 956                 assert(scratchReg != MRI.getInvalidRegNum());
 957               }
 958
 959             if (AdIBef.size() > 0)
 960               instrnsBefore.insert(instrnsBefore.end(),
 961                                    AdIBef.begin(), AdIBef.end());
 962
 963             MRI.cpReg2MemMI(instrnsBefore, Reg, MRI.getFramePointer(),
 964                             StackOff, RegType, scratchReg);
 965
 966             if (AdIAft.size() > 0)
 967               instrnsBefore.insert(instrnsBefore.end(),
 968                                    AdIAft.begin(), AdIAft.end());
 969
 970             //---- Insert code for popping the reg from the stack ----------
 971
 972             AdIBef.clear();
 973             AdIAft.clear();
 974
 975             // We may need a scratch register to copy the saved value
 976             // from memory.  This may itself have to insert code to
 977             // free up a scratch register.  Any such code should go
 978             // after the save code.  As above, scratch is not marked "used".
 979             //
 980             scratchRegType = -1;
 981             scratchReg = -1;
 982             if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
 983               { // Find a register not live in the LVSet after CallMI
 984                 scratchReg = getUsableUniRegAtMI(scratchRegType, &LVSetAft,
 985                                                  CallMI, AdIBef, AdIAft);
 986                 assert(scratchReg != MRI.getInvalidRegNum());
 987               }
 988
 989             if (AdIBef.size() > 0)
 990               instrnsAfter.insert(instrnsAfter.end(),
 991                                   AdIBef.begin(), AdIBef.end());
 992
 993             MRI.cpMem2RegMI(instrnsAfter, MRI.getFramePointer(), StackOff,
 994                             Reg, RegType, scratchReg);
 995
 996             if (AdIAft.size() > 0)
 997               instrnsAfter.insert(instrnsAfter.end(),
 998                                   AdIAft.begin(), AdIAft.end());
 999
1000             PushedRegSet.insert(Reg);
1001
1002             if(DEBUG_RA) {
1003               std::cerr << "\nFor call inst:" << *CallMI;
1004               std::cerr << " -inserted caller saving instrs: Before:\n\t ";
1005               for_each(instrnsBefore.begin(), instrnsBefore.end(),
1006                        std::mem_fun(&MachineInstr::dump));
1007               std::cerr << " -and After:\n\t ";
1008               for_each(instrnsAfter.begin(), instrnsAfter.end(),
1009                        std::mem_fun(&MachineInstr::dump));
1010             }
1011           } // if not already pushed
1012
1013         } // if LR has a volatile color
1014
1015       } // if LR has color
1016
1017     } // if there is a LR for Var
1018
1019   } // for each value in the LV set after instruction
1020 }
1021
1022
1023 //----------------------------------------------------------------------------
1024 // We can use the following method to get a temporary register to be used
1025 // BEFORE any given machine instruction. If there is a register available,
1026 // this method will simply return that register and set MIBef = MIAft = NULL.
1027 // Otherwise, it will return a register and MIAft and MIBef will contain
1028 // two instructions used to free up this returned register.
1029 // Returned register number is the UNIFIED register number
1030 //----------------------------------------------------------------------------
1031
1032 int PhyRegAlloc::getUsableUniRegAtMI(const int RegType,
1033                                      const ValueSet *LVSetBef,
1034                                      MachineInstr *MInst,
1035                                      std::vector<MachineInstr*>& MIBef,
1036                                      std::vector<MachineInstr*>& MIAft) {
1037
1038   RegClass* RC = getRegClassByID(MRI.getRegClassIDOfRegType(RegType));
1039
1040   int RegU =  getUnusedUniRegAtMI(RC, RegType, MInst, LVSetBef);
1041
1042   if (RegU == -1) {
1043     // we couldn't find an unused register. Generate code to free up a reg by
1044     // saving it on stack and restoring after the instruction
1045
1046     int TmpOff = MF.getInfo()->pushTempValue(MRI.getSpilledRegSize(RegType));
1047
1048     RegU = getUniRegNotUsedByThisInst(RC, RegType, MInst);
1049
1050     // Check if we need a scratch register to copy this register to memory.
1051     int scratchRegType = -1;
1052     if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
1053       {
1054         int scratchReg = getUsableUniRegAtMI(scratchRegType, LVSetBef,
1055                                              MInst, MIBef, MIAft);
1056         assert(scratchReg != MRI.getInvalidRegNum());
1057
1058         // We may as well hold the value in the scratch register instead
1059         // of copying it to memory and back.  But we have to mark the
1060         // register as used by this instruction, so it does not get used
1061         // as a scratch reg. by another operand or anyone else.
1062         MInst->insertUsedReg(scratchReg);
1063         MRI.cpReg2RegMI(MIBef, RegU, scratchReg, RegType);
1064         MRI.cpReg2RegMI(MIAft, scratchReg, RegU, RegType);
1065       }
1066     else
1067       { // the register can be copied directly to/from memory so do it.
1068         MRI.cpReg2MemMI(MIBef, RegU, MRI.getFramePointer(), TmpOff, RegType);
1069         MRI.cpMem2RegMI(MIAft, MRI.getFramePointer(), TmpOff, RegU, RegType);
1070       }
1071   }
1072
1073   return RegU;
1074 }
1075
1076
1077 //----------------------------------------------------------------------------
1078 // This method is called to get a new unused register that can be used
1079 // to accomodate a temporary value.  This method may be called several times
1080 // for a single machine instruction.  Each time it is called, it finds a
1081 // register which is not live at that instruction and also which is not used
1082 // by other spilled operands of the same instruction.  Return register number
1083 // is relative to the register class, NOT the unified number.
1084 //----------------------------------------------------------------------------
1085
1086 int PhyRegAlloc::getUnusedUniRegAtMI(RegClass *RC,
1087                                      const int RegType,
1088                                      const MachineInstr *MInst,
1089                                      const ValueSet* LVSetBef) {
1090
1091   RC->clearColorsUsed();     // Reset array
1092
1093   if (LVSetBef == NULL) {
1094       LVSetBef = &LVI->getLiveVarSetBeforeMInst(MInst);
1095       assert(LVSetBef != NULL && "Unable to get live-var set before MInst?");
1096   }
1097
1098   ValueSet::const_iterator LIt = LVSetBef->begin();
1099
1100   // for each live var in live variable set after machine inst
1101   for ( ; LIt != LVSetBef->end(); ++LIt) {
1102
1103    //  get the live range corresponding to live var, and its RegClass
1104     LiveRange *const LRofLV = LRI.getLiveRangeForValue(*LIt );
1105
1106     // LR can be null if it is a const since a const
1107     // doesn't have a dominating def - see Assumptions above
1108     if (LRofLV && LRofLV->getRegClass() == RC && LRofLV->hasColor())
1109       RC->markColorsUsed(LRofLV->getColor(),
1110                          MRI.getRegTypeForLR(LRofLV), RegType);
1111   }
1112
1113   // It is possible that one operand of this MInst was already spilled
1114   // and it received some register temporarily. If that's the case,
1115   // it is recorded in machine operand. We must skip such registers.
1116   //
1117   setRelRegsUsedByThisInst(RC, RegType, MInst);
1118
1119   int unusedReg = RC->getUnusedColor(RegType);   // find first unused color
1120   if (unusedReg >= 0)
1121     return MRI.getUnifiedRegNum(RC->getID(), unusedReg);
1122
1123   return -1;
1124 }
1125
1126
1127 //----------------------------------------------------------------------------
1128 // Get any other register in a register class, other than what is used
1129 // by operands of a machine instruction. Returns the unified reg number.
1130 //----------------------------------------------------------------------------
1131 int PhyRegAlloc::getUniRegNotUsedByThisInst(RegClass *RC,
1132                                             const int RegType,
1133                                             const MachineInstr *MInst) {
1134   RC->clearColorsUsed();
1135
1136   setRelRegsUsedByThisInst(RC, RegType, MInst);
1137
1138   // find the first unused color
1139   int unusedReg = RC->getUnusedColor(RegType);
1140   assert(unusedReg >= 0 &&
1141          "FATAL: No free register could be found in reg class!!");
1142
1143   return MRI.getUnifiedRegNum(RC->getID(), unusedReg);
1144 }
1145
1146
1147 //----------------------------------------------------------------------------
1148 // This method modifies the IsColorUsedArr of the register class passed to it.
1149 // It sets the bits corresponding to the registers used by this machine
1150 // instructions. Both explicit and implicit operands are set.
1151 //----------------------------------------------------------------------------
1152
1153 void PhyRegAlloc::setRelRegsUsedByThisInst(RegClass *RC,
1154                                            const int RegType,
1155                                            const MachineInstr *MInst )
1156 {
1157   assert(OperandsColoredMap[MInst] == true &&
1158          "Illegal to call setRelRegsUsedByThisInst() until colored operands "
1159          "are marked for an instruction.");
1160
1161   // Add the registers already marked as used by the instruction.
1162   // This should include any scratch registers that are used to save
1163   // values across the instruction (e.g., for saving state register values).
1164   const std::set<int> &regsUsed = MInst->getRegsUsed();
1165   for (std::set<int>::iterator I=regsUsed.begin(),E=regsUsed.end(); I != E; ++I)
1166     {
1167       int i = *I;
1168       unsigned classId = 0;
1169       int classRegNum = MRI.getClassRegNum(i, classId);
1170       if (RC->getID() == classId)
1171         RC->markColorsUsed(classRegNum, RegType, RegType);
1172     }
1173
1174   // If there are implicit references, mark their allocated regs as well
1175   //
1176   for (unsigned z=0; z < MInst->getNumImplicitRefs(); z++)
1177     if (const LiveRange*
1178         LRofImpRef = LRI.getLiveRangeForValue(MInst->getImplicitRef(z)))
1179       if (LRofImpRef->hasColor())
1180         // this implicit reference is in a LR that received a color
1181         RC->markColorsUsed(LRofImpRef->getColor(),
1182                            MRI.getRegTypeForLR(LRofImpRef), RegType);
1183 }
1184
1185
1186 //----------------------------------------------------------------------------
1187 // If there are delay slots for an instruction, the instructions
1188 // added after it must really go after the delayed instruction(s).
1189 // So, we move the InstrAfter of that instruction to the
1190 // corresponding delayed instruction using the following method.
1191 //----------------------------------------------------------------------------
1192
1193 void PhyRegAlloc::move2DelayedInstr(const MachineInstr *OrigMI,
1194                                     const MachineInstr *DelayedMI)
1195 {
1196   if (DEBUG_RA) {
1197     cerr << "\nRegAlloc: Moved InstrnsAfter for: " << *OrigMI;
1198     cerr << "         to last delay slot instrn: " << *DelayedMI;
1199   }
1200
1201   // "added after" instructions of the original instr
1202   std::vector<MachineInstr *> &OrigAft = AddedInstrMap[OrigMI].InstrnsAfter;
1203
1204   // "added after" instructions of the delayed instr
1205   std::vector<MachineInstr *> &DelayedAft=AddedInstrMap[DelayedMI].InstrnsAfter;
1206
1207   // go thru all the "added after instructions" of the original instruction
1208   // and append them to the "added after instructions" of the delayed
1209   // instructions
1210   DelayedAft.insert(DelayedAft.end(), OrigAft.begin(), OrigAft.end());
1211
1212   // empty the "added after instructions" of the original instruction
1213   OrigAft.clear();
1214 }
1215
1216 //----------------------------------------------------------------------------
1217 // This method prints the code with registers after register allocation is
1218 // complete.
1219 //----------------------------------------------------------------------------
1220 void PhyRegAlloc::printMachineCode()
1221 {
1222
1223   cerr << "\n;************** Function " << Fn->getName()
1224        << " *****************\n";
1225
1226   for (MachineFunction::iterator BBI = MF.begin(), BBE = MF.end();
1227        BBI != BBE; ++BBI) {
1228     cerr << "\n"; printLabel(BBI->getBasicBlock()); cerr << ": ";
1229
1230     // get the iterator for machine instructions
1231     MachineBasicBlock& MBB = *BBI;
1232     MachineBasicBlock::iterator MII = MBB.begin();
1233
1234     // iterate over all the machine instructions in BB
1235     for ( ; MII != MBB.end(); ++MII) {
1236       MachineInstr *MInst = *MII;
1237
1238       cerr << "\n\t";
1239       cerr << TM.getInstrInfo().getName(MInst->getOpCode());
1240
1241       for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
1242         MachineOperand& Op = MInst->getOperand(OpNum);
1243
1244         if (Op.getType() ==  MachineOperand::MO_VirtualRegister ||
1245             Op.getType() ==  MachineOperand::MO_CCRegister /*||
1246             Op.getType() ==  MachineOperand::MO_PCRelativeDisp*/ ) {
1247
1248           const Value *const Val = Op.getVRegValue () ;
1249           // ****this code is temporary till NULL Values are fixed
1250           if (! Val ) {
1251             cerr << "\t<*NULL*>";
1252             continue;
1253           }
1254
1255           // if a label or a constant
1256           if (isa<BasicBlock>(Val)) {
1257             cerr << "\t"; printLabel(   Op.getVRegValue () );
1258           } else {
1259             // else it must be a register value
1260             const int RegNum = Op.getAllocatedRegNum();
1261
1262             cerr << "\t" << "%" << MRI.getUnifiedRegName( RegNum );
1263             if (Val->hasName() )
1264               cerr << "(" << Val->getName() << ")";
1265             else
1266               cerr << "(" << Val << ")";
1267
1268             if (Op.opIsDefOnly() || Op.opIsDefAndUse())
1269               cerr << "*";
1270
1271             const LiveRange *LROfVal = LRI.getLiveRangeForValue(Val);
1272             if (LROfVal )
1273               if (LROfVal->hasSpillOffset() )
1274                 cerr << "$";
1275           }
1276
1277         }
1278         else if (Op.getType() ==  MachineOperand::MO_MachineRegister) {
1279           cerr << "\t" << "%" << MRI.getUnifiedRegName(Op.getMachineRegNum());
1280         }
1281
1282         else
1283           cerr << "\t" << Op;      // use dump field
1284       }
1285
1286
1287
1288       unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
1289       if (NumOfImpRefs > 0) {
1290         cerr << "\tImplicit:";
1291
1292         for (unsigned z=0; z < NumOfImpRefs; z++)
1293           cerr << RAV(MInst->getImplicitRef(z)) << "\t";
1294       }
1295
1296     } // for all machine instructions
1297
1298     cerr << "\n";
1299
1300   } // for all BBs
1301
1302   cerr << "\n";
1303 }
1304
1305
1306 //----------------------------------------------------------------------------
1307
1308 //----------------------------------------------------------------------------
1309 void PhyRegAlloc::colorIncomingArgs()
1310 {
1311   MRI.colorMethodArgs(Fn, LRI, AddedInstrAtEntry.InstrnsBefore,
1312                       AddedInstrAtEntry.InstrnsAfter);
1313 }
1314
1315
1316 //----------------------------------------------------------------------------
1317 // Used to generate a label for a basic block
1318 //----------------------------------------------------------------------------
1319 void PhyRegAlloc::printLabel(const Value *Val) {
1320   if (Val->hasName())
1321     cerr  << Val->getName();
1322   else
1323     cerr << "Label" << Val;
1324 }
1325
1326
1327 //----------------------------------------------------------------------------
1328 // This method calls setSugColorUsable method of each live range. This
1329 // will determine whether the suggested color of LR is  really usable.
1330 // A suggested color is not usable when the suggested color is volatile
1331 // AND when there are call interferences
1332 //----------------------------------------------------------------------------
1333
1334 void PhyRegAlloc::markUnusableSugColors()
1335 {
1336   // hash map iterator
1337   LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();
1338   LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();
1339
1340     for (; HMI != HMIEnd ; ++HMI ) {
1341       if (HMI->first) {
1342         LiveRange *L = HMI->second;      // get the LiveRange
1343         if (L) {
1344           if (L->hasSuggestedColor()) {
1345             int RCID = L->getRegClass()->getID();
1346             if (MRI.isRegVolatile( RCID,  L->getSuggestedColor()) &&
1347                 L->isCallInterference() )
1348               L->setSuggestedColorUsable( false );
1349             else
1350               L->setSuggestedColorUsable( true );
1351           }
1352         } // if L->hasSuggestedColor()
1353       }
1354     } // for all LR's in hash map
1355 }
1356
1357
1358
1359 //----------------------------------------------------------------------------
1360 // The following method will set the stack offsets of the live ranges that
1361 // are decided to be spillled. This must be called just after coloring the
1362 // LRs using the graph coloring algo. For each live range that is spilled,
1363 // this method allocate a new spill position on the stack.
1364 //----------------------------------------------------------------------------
1365
1366 void PhyRegAlloc::allocateStackSpace4SpilledLRs() {
1367   if (DEBUG_RA) cerr << "\nSetting LR stack offsets for spills...\n";
1368
1369   LiveRangeMapType::const_iterator HMI    = LRI.getLiveRangeMap()->begin();
1370   LiveRangeMapType::const_iterator HMIEnd = LRI.getLiveRangeMap()->end();
1371
1372   for ( ; HMI != HMIEnd ; ++HMI) {
1373     if (HMI->first && HMI->second) {
1374       LiveRange *L = HMI->second;       // get the LiveRange
1375       if (L->isMarkedForSpill()) {      // NOTE: allocating size of long Type **
1376         int stackOffset = MF.getInfo()->allocateSpilledValue(Type::LongTy);
1377         L->setSpillOffFromFP(stackOffset);
1378         if (DEBUG_RA)
1379           cerr << "  LR# " << L->getUserIGNode()->getIndex()
1380                << ": stack-offset = " << stackOffset << "\n";
1381       }
1382     }
1383   } // for all LR's in hash map
1384 }
1385
1386
1387 //----------------------------------------------------------------------------
1388 // The entry pont to Register Allocation
1389 //----------------------------------------------------------------------------
1390
1391 void PhyRegAlloc::allocateRegisters()
1392 {
1393
1394   // make sure that we put all register classes into the RegClassList
1395   // before we call constructLiveRanges (now done in the constructor of
1396   // PhyRegAlloc class).
1397   //
1398   LRI.constructLiveRanges();            // create LR info
1399
1400   if (DEBUG_RA >= RA_DEBUG_LiveRanges)
1401     LRI.printLiveRanges();
1402
1403   createIGNodeListsAndIGs();            // create IGNode list and IGs
1404
1405   buildInterferenceGraphs();            // build IGs in all reg classes
1406
1407
1408   if (DEBUG_RA >= RA_DEBUG_LiveRanges) {
1409     // print all LRs in all reg classes
1410     for ( unsigned rc=0; rc < NumOfRegClasses  ; rc++)
1411       RegClassList[rc]->printIGNodeList();
1412
1413     // print IGs in all register classes
1414     for ( unsigned rc=0; rc < NumOfRegClasses ; rc++)
1415       RegClassList[rc]->printIG();
1416   }
1417
1418   LRI.coalesceLRs();                    // coalesce all live ranges
1419
1420   if (DEBUG_RA >= RA_DEBUG_LiveRanges) {
1421     // print all LRs in all reg classes
1422     for (unsigned rc=0; rc < NumOfRegClasses; rc++)
1423       RegClassList[rc]->printIGNodeList();
1424
1425     // print IGs in all register classes
1426     for (unsigned rc=0; rc < NumOfRegClasses; rc++)
1427       RegClassList[rc]->printIG();
1428   }
1429
1430
1431   // mark un-usable suggested color before graph coloring algorithm.
1432   // When this is done, the graph coloring algo will not reserve
1433   // suggested color unnecessarily - they can be used by another LR
1434   //
1435   markUnusableSugColors();
1436
1437   // color all register classes using the graph coloring algo
1438   for (unsigned rc=0; rc < NumOfRegClasses ; rc++)
1439     RegClassList[rc]->colorAllRegs();
1440
1441   // Atter graph coloring, if some LRs did not receive a color (i.e, spilled)
1442   // a poistion for such spilled LRs
1443   //
1444   allocateStackSpace4SpilledLRs();
1445
1446   // Reset the temp. area on the stack before use by the first instruction.
1447   // This will also happen after updating each instruction.
1448   MF.getInfo()->popAllTempValues();
1449
1450   // color incoming args - if the correct color was not received
1451   // insert code to copy to the correct register
1452   //
1453   colorIncomingArgs();
1454
1455   // Now update the machine code with register names and add any
1456   // additional code inserted by the register allocator to the instruction
1457   // stream
1458   //
1459   updateMachineCode();
1460
1461   if (DEBUG_RA) {
1462     cerr << "\n**** Machine Code After Register Allocation:\n\n";
1463     MF.dump();
1464   }
1465 }
1466
1467
1468