lib/Target/SparcV9/RegAlloc/PhyRegAlloc.cpp

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