lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp

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