lib/CodeGen/RegAllocLocal.cpp

   1 //===-- RegAllocLocal.cpp - A BasicBlock generic register allocator -------===//
   2 //
   3 // This register allocator allocates registers to a basic block at a time,
   4 // attempting to keep values in registers and reusing registers as appropriate.
   5 //
   6 //===----------------------------------------------------------------------===//
   7
   8 #include "llvm/CodeGen/MachineFunction.h"
   9 #include "llvm/CodeGen/MachineInstr.h"
  10 #include "llvm/Target/MachineInstrInfo.h"
  11 #include "llvm/Target/TargetMachine.h"
  12 #include "Support/Statistic.h"
  13 #include <iostream>
  14
  15 /// PhysRegClassMap - Construct a mapping of physical register numbers to their
  16 /// register classes.
  17 ///
  18 /// NOTE: This class will eventually be pulled out to somewhere shared.
  19 ///
  20 class PhysRegClassMap {
  21   std::map<unsigned, const TargetRegisterClass*> PhysReg2RegClassMap;
  22 public:
  23   PhysRegClassMap(const MRegisterInfo &RI) {
  24     for (MRegisterInfo::const_iterator I = RI.regclass_begin(),
  25            E = RI.regclass_end(); I != E; ++I)
  26       for (unsigned i=0; i < (*I)->getNumRegs(); ++i)
  27         PhysReg2RegClassMap[(*I)->getRegister(i)] = *I;
  28   }
  29
  30   const TargetRegisterClass *operator[](unsigned Reg) {
  31     assert(PhysReg2RegClassMap[Reg] && "Register is not a known physreg!");
  32     return PhysReg2RegClassMap[Reg];
  33   }
  34
  35   const TargetRegisterClass *get(unsigned Reg) { return operator[](Reg); }
  36 };
  37
  38 namespace {
  39   Statistic<> NumSpilled ("ra-local", "Number of registers spilled");
  40   Statistic<> NumReloaded("ra-local", "Number of registers reloaded");
  41
  42   class RA : public FunctionPass {
  43     TargetMachine &TM;
  44     MachineFunction *MF;
  45     const MRegisterInfo &RegInfo;
  46     const MachineInstrInfo &MIInfo;
  47     unsigned NumBytesAllocated;
  48     PhysRegClassMap PhysRegClasses;
  49
  50     // Maps SSA Regs => offsets on the stack where these values are stored
  51     std::map<unsigned, unsigned> VirtReg2OffsetMap;
  52
  53     // Virt2PhysRegMap - This map contains entries for each virtual register
  54     // that is currently available in a physical register.
  55     //
  56     std::map<unsigned, unsigned> Virt2PhysRegMap;
  57
  58     // PhysRegsUsed - This map contains entries for each physical register that
  59     // currently has a value (ie, it is in Virt2PhysRegMap).  The value mapped
  60     // to is the virtual register corresponding to the physical register (the
  61     // inverse of the Virt2PhysRegMap), or 0.  The value is set to 0 if this
  62     // register is pinned because it is used by a future instruction.
  63     //
  64     std::map<unsigned, unsigned> PhysRegsUsed;
  65
  66     // PhysRegsUseOrder - This contains a list of the physical registers that
  67     // currently have a virtual register value in them.  This list provides an
  68     // ordering of registers, imposing a reallocation order.  This list is only
  69     // used if all registers are allocated and we have to spill one, in which
  70     // case we spill the least recently used register.  Entries at the front of
  71     // the list are the least recently used registers, entries at the back are
  72     // the most recently used.
  73     //
  74     std::vector<unsigned> PhysRegsUseOrder;
  75
  76     void MarkPhysRegRecentlyUsed(unsigned Reg) {
  77       assert(std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), Reg) !=
  78              PhysRegsUseOrder.end() && "Register isn't used yet!");
  79       if (PhysRegsUseOrder.back() != Reg) {
  80         for (unsigned i = PhysRegsUseOrder.size(); ; --i)
  81           if (PhysRegsUseOrder[i-1] == Reg) {  // remove from middle
  82             PhysRegsUseOrder.erase(PhysRegsUseOrder.begin()+i-1);
  83             PhysRegsUseOrder.push_back(Reg);  // Add it to the end of the list
  84             return;
  85           }
  86       }
  87     }
  88
  89   public:
  90
  91     RA(TargetMachine &tm)
  92       : TM(tm), RegInfo(*tm.getRegisterInfo()), MIInfo(tm.getInstrInfo()),
  93         PhysRegClasses(RegInfo) {
  94       cleanupAfterFunction();
  95     }
  96
  97     bool runOnFunction(Function &Fn) {
  98       return runOnMachineFunction(MachineFunction::get(&Fn));
  99     }
 100
 101     virtual const char *getPassName() const {
 102       return "Local Register Allocator";
 103     }
 104
 105   private:
 106     /// runOnMachineFunction - Register allocate the whole function
 107     bool runOnMachineFunction(MachineFunction &Fn);
 108
 109     /// AllocateBasicBlock - Register allocate the specified basic block.
 110     void AllocateBasicBlock(MachineBasicBlock &MBB);
 111
 112     /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
 113     /// in predecessor basic blocks.
 114     void EliminatePHINodes(MachineBasicBlock &MBB);
 115
 116     /// EmitPrologue/EmitEpilogue - Use the register info object to add a
 117     /// prologue/epilogue to the function and save/restore any callee saved
 118     /// registers we are responsible for.
 119     ///
 120     void EmitPrologue();
 121     void EmitEpilogue(MachineBasicBlock &MBB);
 122
 123     /// isAllocatableRegister - A register may be used by the program if it's
 124     /// not the stack or frame pointer.
 125     bool isAllocatableRegister(unsigned R) const {
 126       unsigned FP = RegInfo.getFramePointer(), SP = RegInfo.getStackPointer();
 127       // Don't allocate the Frame or Stack pointers
 128       if (R == FP || R == SP)
 129         return false;
 130
 131       // Check to see if this register aliases the stack or frame pointer...
 132       if (const unsigned *AliasSet = RegInfo.getAliasSet(R)) {
 133         for (unsigned i = 0; AliasSet[i]; ++i)
 134           if (AliasSet[i] == FP || AliasSet[i] == SP)
 135             return false;
 136       }
 137       return true;
 138     }
 139
 140     /// getStackSpaceFor - This returns the offset of the specified virtual
 141     /// register on the stack, allocating space if neccesary.
 142     unsigned getStackSpaceFor(unsigned VirtReg,
 143                               const TargetRegisterClass *regClass);
 144
 145     void cleanupAfterFunction() {
 146       VirtReg2OffsetMap.clear();
 147       NumBytesAllocated = 4;   // FIXME: This is X86 specific
 148     }
 149
 150
 151     /// spillVirtReg - This method spills the value specified by PhysReg into
 152     /// the virtual register slot specified by VirtReg.  It then updates the RA
 153     /// data structures to indicate the fact that PhysReg is now available.
 154     ///
 155     void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 156                       unsigned VirtReg, unsigned PhysReg);
 157
 158     /// spillPhysReg - This method spills the specified physical register into
 159     /// the virtual register slot associated with it.
 160     //
 161     void spillPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 162                       unsigned PhysReg) {
 163       std::map<unsigned, unsigned>::iterator PI = PhysRegsUsed.find(PhysReg);
 164       if (PI != PhysRegsUsed.end())   // Only spill it if it's used!
 165         spillVirtReg(MBB, I, PI->second, PhysReg);
 166     }
 167
 168     void AssignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg);
 169
 170     /// isPhysRegAvailable - Return true if the specified physical register is
 171     /// free and available for use.  This also includes checking to see if
 172     /// aliased registers are all free...
 173     ///
 174     bool RA::isPhysRegAvailable(unsigned PhysReg) const;
 175
 176     /// getFreeReg - Find a physical register to hold the specified virtual
 177     /// register.  If all compatible physical registers are used, this method
 178     /// spills the last used virtual register to the stack, and uses that
 179     /// register.
 180     ///
 181     unsigned getFreeReg(MachineBasicBlock &MBB,
 182                         MachineBasicBlock::iterator &I,
 183                         unsigned virtualReg);
 184
 185     /// reloadVirtReg - This method loads the specified virtual register into a
 186     /// physical register, returning the physical register chosen.  This updates
 187     /// the regalloc data structures to reflect the fact that the virtual reg is
 188     /// now alive in a physical register, and the previous one isn't.
 189     ///
 190     unsigned reloadVirtReg(MachineBasicBlock &MBB,
 191                            MachineBasicBlock::iterator &I, unsigned VirtReg);
 192   };
 193 }
 194
 195
 196 /// getStackSpaceFor - This allocates space for the specified virtual
 197 /// register to be held on the stack.
 198 unsigned RA::getStackSpaceFor(unsigned VirtReg,
 199                               const TargetRegisterClass *RegClass) {
 200   // Find the location VirtReg would belong...
 201   std::map<unsigned, unsigned>::iterator I =
 202     VirtReg2OffsetMap.lower_bound(VirtReg);
 203
 204   if (I != VirtReg2OffsetMap.end() && I->first == VirtReg)
 205     return I->second;          // Already has space allocated?
 206
 207   unsigned RegSize = RegClass->getDataSize();
 208
 209   // Align NumBytesAllocated.  We should be using TargetData alignment stuff
 210   // to determine this, but we don't know the LLVM type associated with the
 211   // virtual register.  Instead, just align to a multiple of the size for now.
 212   NumBytesAllocated += RegSize-1;
 213   NumBytesAllocated = NumBytesAllocated/RegSize*RegSize;
 214
 215   // Assign the slot...
 216   VirtReg2OffsetMap.insert(I, std::make_pair(VirtReg, NumBytesAllocated));
 217
 218   // Reserve the space!
 219   NumBytesAllocated += RegSize;
 220   return NumBytesAllocated-RegSize;
 221 }
 222
 223
 224 /// spillVirtReg - This method spills the value specified by PhysReg into the
 225 /// virtual register slot specified by VirtReg.  It then updates the RA data
 226 /// structures to indicate the fact that PhysReg is now available.
 227 ///
 228 void RA::spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 229                       unsigned VirtReg, unsigned PhysReg) {
 230   // If this is just a marker register, we don't need to spill it.
 231   if (VirtReg != 0) {
 232     const TargetRegisterClass *RegClass = MF->getRegClass(VirtReg);
 233     unsigned stackOffset = getStackSpaceFor(VirtReg, RegClass);
 234
 235     // Add move instruction(s)
 236     I = RegInfo.storeReg2RegOffset(MBB, I, PhysReg, RegInfo.getFramePointer(),
 237                                    -stackOffset, RegClass->getDataSize());
 238     ++NumSpilled;   // Update statistics
 239     Virt2PhysRegMap.erase(VirtReg);   // VirtReg no longer available
 240   }
 241   PhysRegsUsed.erase(PhysReg);      // PhyReg no longer used
 242
 243   std::vector<unsigned>::iterator It =
 244     std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), PhysReg);
 245   assert(It != PhysRegsUseOrder.end() &&
 246          "Spilled a physical register, but it was not in use list!");
 247   PhysRegsUseOrder.erase(It);
 248 }
 249
 250
 251 /// isPhysRegAvailable - Return true if the specified physical register is free
 252 /// and available for use.  This also includes checking to see if aliased
 253 /// registers are all free...
 254 ///
 255 bool RA::isPhysRegAvailable(unsigned PhysReg) const {
 256   if (PhysRegsUsed.count(PhysReg)) return false;
 257
 258   // If the selected register aliases any other allocated registers, it is
 259   // not free!
 260   if (const unsigned *AliasSet = RegInfo.getAliasSet(PhysReg))
 261     for (unsigned i = 0; AliasSet[i]; ++i)
 262       if (PhysRegsUsed.count(AliasSet[i])) // Aliased register in use?
 263         return false;                      // Can't use this reg then.
 264   return true;
 265 }
 266
 267
 268
 269 /// getFreeReg - Find a physical register to hold the specified virtual
 270 /// register.  If all compatible physical registers are used, this method spills
 271 /// the last used virtual register to the stack, and uses that register.
 272 ///
 273 unsigned RA::getFreeReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 274                         unsigned VirtReg) {
 275   const TargetRegisterClass *RegClass = MF->getRegClass(VirtReg);
 276   unsigned PhysReg = 0;
 277
 278   // First check to see if we have a free register of the requested type...
 279   for (TargetRegisterClass::iterator It = RegClass->begin(),E = RegClass->end();
 280        It != E; ++It) {
 281     unsigned R = *It;
 282     if (isPhysRegAvailable(R)) {       // Is reg unused?
 283       if (isAllocatableRegister(R)) {  // And is not a frame register?
 284         // Found an unused register!
 285         PhysReg = R;
 286         break;
 287       }
 288     }
 289   }
 290
 291   // If we didn't find an unused register, scavenge one now!
 292   if (PhysReg == 0) {
 293     assert(!PhysRegsUseOrder.empty() && "No allocated registers??");
 294
 295     // Loop over all of the preallocated registers from the least recently used
 296     // to the most recently used.  When we find one that is capable of holding
 297     // our register, use it.
 298     for (unsigned i = 0; PhysReg == 0; ++i) {
 299       assert(i != PhysRegsUseOrder.size() &&
 300              "Couldn't find a register of the appropriate class!");
 301
 302       unsigned R = PhysRegsUseOrder[i];
 303       // If the current register is compatible, use it.
 304       if (isAllocatableRegister(R)) {
 305         if (PhysRegClasses[R] == RegClass) {
 306           PhysReg = R;
 307           break;
 308         } else {
 309           // If one of the registers aliased to the current register is
 310           // compatible, use it.
 311           if (const unsigned *AliasSet = RegInfo.getAliasSet(R))
 312             for (unsigned a = 0; AliasSet[a]; ++a)
 313               if (PhysRegClasses[AliasSet[a]] == RegClass) {
 314                 PhysReg = AliasSet[a];    // Take an aliased register
 315                 break;
 316               }
 317         }
 318       }
 319     }
 320
 321     assert(isAllocatableRegister(PhysReg) && "Register is not allocatable!");
 322
 323     assert(PhysReg && "Physical register not assigned!?!?");
 324
 325     // At this point PhysRegsUseOrder[i] is the least recently used register of
 326     // compatible register class.  Spill it to memory and reap its remains.
 327     spillPhysReg(MBB, I, PhysReg);
 328
 329     // If the selected register aliases any other registers, we must make sure
 330     // to spill them as well...
 331     if (const unsigned *AliasSet = RegInfo.getAliasSet(PhysReg))
 332       for (unsigned i = 0; AliasSet[i]; ++i)
 333         if (PhysRegsUsed.count(AliasSet[i]))     // Spill aliased register...
 334           spillPhysReg(MBB, I, AliasSet[i]);
 335   }
 336
 337   // Now that we know which register we need to assign this to, do it now!
 338   AssignVirtToPhysReg(VirtReg, PhysReg);
 339   return PhysReg;
 340 }
 341
 342
 343 void RA::AssignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) {
 344   assert(PhysRegsUsed.find(PhysReg) == PhysRegsUsed.end() &&
 345          "Phys reg already assigned!");
 346   // Update information to note the fact that this register was just used, and
 347   // it holds VirtReg.
 348   PhysRegsUsed[PhysReg] = VirtReg;
 349   Virt2PhysRegMap[VirtReg] = PhysReg;
 350   PhysRegsUseOrder.push_back(PhysReg);   // New use of PhysReg
 351 }
 352
 353
 354 /// reloadVirtReg - This method loads the specified virtual register into a
 355 /// physical register, returning the physical register chosen.  This updates the
 356 /// regalloc data structures to reflect the fact that the virtual reg is now
 357 /// alive in a physical register, and the previous one isn't.
 358 ///
 359 unsigned RA::reloadVirtReg(MachineBasicBlock &MBB,
 360                            MachineBasicBlock::iterator &I,
 361                            unsigned VirtReg) {
 362   std::map<unsigned, unsigned>::iterator It = Virt2PhysRegMap.find(VirtReg);
 363   if (It != Virt2PhysRegMap.end()) {
 364     MarkPhysRegRecentlyUsed(It->second);
 365     return It->second;               // Already have this value available!
 366   }
 367
 368   unsigned PhysReg = getFreeReg(MBB, I, VirtReg);
 369
 370   const TargetRegisterClass *RegClass = MF->getRegClass(VirtReg);
 371   unsigned StackOffset = getStackSpaceFor(VirtReg, RegClass);
 372
 373   // Add move instruction(s)
 374   I = RegInfo.loadRegOffset2Reg(MBB, I, PhysReg, RegInfo.getFramePointer(),
 375                                 -StackOffset, RegClass->getDataSize());
 376   ++NumReloaded;    // Update statistics
 377   return PhysReg;
 378 }
 379
 380
 381 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
 382 /// predecessor basic blocks.
 383 ///
 384 void RA::EliminatePHINodes(MachineBasicBlock &MBB) {
 385   const MachineInstrInfo &MII = TM.getInstrInfo();
 386
 387   while (MBB.front()->getOpcode() == MachineInstrInfo::PHI) {
 388     MachineInstr *MI = MBB.front();
 389     // Unlink the PHI node from the basic block... but don't delete the PHI yet
 390     MBB.erase(MBB.begin());
 391
 392     DEBUG(std::cerr << "num ops: " << MI->getNumOperands() << "\n");
 393     assert(MI->getOperand(0).isVirtualRegister() &&
 394            "PHI node doesn't write virt reg?");
 395
 396     unsigned virtualReg = MI->getOperand(0).getAllocatedRegNum();
 397
 398     for (int i = MI->getNumOperands() - 1; i >= 2; i-=2) {
 399       MachineOperand &opVal = MI->getOperand(i-1);
 400
 401       // Get the MachineBasicBlock equivalent of the BasicBlock that is the
 402       // source path the phi
 403       MachineBasicBlock &opBlock = *MI->getOperand(i).getMachineBasicBlock();
 404
 405       // Check to make sure we haven't already emitted the copy for this block.
 406       // This can happen because PHI nodes may have multiple entries for the
 407       // same basic block.  It doesn't matter which entry we use though, because
 408       // all incoming values are guaranteed to be the same for a particular bb.
 409       //
 410       // Note that this is N^2 in the number of phi node entries, but since the
 411       // # of entries is tiny, this is not a problem.
 412       //
 413       bool HaveNotEmitted = true;
 414       for (int op = MI->getNumOperands() - 1; op != i; op -= 2)
 415         if (&opBlock == MI->getOperand(op).getMachineBasicBlock()) {
 416           HaveNotEmitted = false;
 417           break;
 418         }
 419
 420       if (HaveNotEmitted) {
 421         MachineBasicBlock::iterator opI = opBlock.end();
 422         MachineInstr *opMI = *--opI;
 423
 424         // must backtrack over ALL the branches in the previous block
 425         while (MII.isBranch(opMI->getOpcode()) && opI != opBlock.begin())
 426           opMI = *--opI;
 427
 428         // move back to the first branch instruction so new instructions
 429         // are inserted right in front of it and not in front of a non-branch
 430         if (!MII.isBranch(opMI->getOpcode()))
 431           ++opI;
 432
 433         unsigned dataSize = MF->getRegClass(virtualReg)->getDataSize();
 434
 435         // Retrieve the constant value from this op, move it to target
 436         // register of the phi
 437         if (opVal.isImmediate()) {
 438           opI = RegInfo.moveImm2Reg(opBlock, opI, virtualReg,
 439                                     (unsigned) opVal.getImmedValue(),
 440                                     dataSize);
 441         } else {
 442           opI = RegInfo.moveReg2Reg(opBlock, opI, virtualReg,
 443                                     opVal.getAllocatedRegNum(), dataSize);
 444         }
 445       }
 446     }
 447
 448     // really delete the PHI instruction now!
 449     delete MI;
 450   }
 451 }
 452
 453
 454 void RA::AllocateBasicBlock(MachineBasicBlock &MBB) {
 455   // loop over each instruction
 456   MachineBasicBlock::iterator I = MBB.begin();
 457   for (; I != MBB.end(); ++I) {
 458     MachineInstr *MI = *I;
 459     const MachineInstrDescriptor &MID = MIInfo.get(MI->getOpcode());
 460
 461     // Loop over all of the operands of the instruction, spilling registers that
 462     // are defined, and marking explicit destinations in the PhysRegsUsed map.
 463     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
 464       if (MI->getOperand(i).opIsDef() &&
 465           MI->getOperand(i).isPhysicalRegister()) {
 466         unsigned Reg = MI->getOperand(i).getAllocatedRegNum();
 467         spillPhysReg(MBB, I, Reg);
 468         PhysRegsUsed[Reg] = 0;  // It's free now, and it's reserved
 469         PhysRegsUseOrder.push_back(Reg);
 470       }
 471
 472     // Loop over the implicit defs, spilling them, as above.
 473     if (const unsigned *ImplicitDefs = MID.ImplicitDefs)
 474       for (unsigned i = 0; ImplicitDefs[i]; ++i) {
 475         unsigned Reg = ImplicitDefs[i];
 476         spillPhysReg(MBB, I, Reg);
 477         PhysRegsUsed[Reg] = 0;  // It's free now, and it's reserved
 478         PhysRegsUseOrder.push_back(Reg);
 479       }
 480
 481     // Loop over the implicit uses, making sure that they are at the head of the
 482     // use order list, so they don't get reallocated.
 483     if (const unsigned *ImplicitUses = MID.ImplicitUses)
 484       for (unsigned i = 0; ImplicitUses[i]; ++i)
 485         MarkPhysRegRecentlyUsed(ImplicitUses[i]);
 486
 487     // Loop over all of the operands again, getting the used operands into
 488     // registers.  This has the potiential to spill incoming values because we
 489     // are out of registers.
 490     //
 491     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
 492       if (MI->getOperand(i).opIsUse() &&
 493           MI->getOperand(i).isVirtualRegister()) {
 494         unsigned VirtSrcReg = MI->getOperand(i).getAllocatedRegNum();
 495         unsigned PhysSrcReg = reloadVirtReg(MBB, I, VirtSrcReg);
 496         MI->SetMachineOperandReg(i, PhysSrcReg);  // Assign the input register
 497       }
 498
 499     // Okay, we have allocated all of the source operands and spilled any values
 500     // that would be destroyed by defs of this instruction.  Loop over the
 501     // implicit defs and assign them to a register, spilling the incoming value
 502     // if we need to scavange a register.
 503
 504     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
 505       if (MI->getOperand(i).opIsDef() &&
 506           !MI->getOperand(i).isPhysicalRegister()) {
 507         unsigned DestVirtReg = MI->getOperand(i).getAllocatedRegNum();
 508         unsigned DestPhysReg;
 509
 510         if (TM.getInstrInfo().isTwoAddrInstr(MI->getOpcode()) && i == 0) {
 511           // must be same register number as the first operand
 512           // This maps a = b + c into b += c, and saves b into a's spot
 513           assert(MI->getOperand(1).isRegister()  &&
 514                  MI->getOperand(1).getAllocatedRegNum() &&
 515                  MI->getOperand(1).opIsUse() &&
 516                  "Two address instruction invalid!");
 517           DestPhysReg = MI->getOperand(1).getAllocatedRegNum();
 518
 519           // Spill the incoming value, because we are about to change the
 520           // register contents.
 521           spillPhysReg(MBB, I, DestPhysReg);
 522           AssignVirtToPhysReg(DestVirtReg, DestPhysReg);
 523         } else {
 524           DestPhysReg = getFreeReg(MBB, I, DestVirtReg);
 525         }
 526         MI->SetMachineOperandReg(i, DestPhysReg);  // Assign the output register
 527       }
 528   }
 529
 530   // Rewind the iterator to point to the first flow control instruction...
 531   const MachineInstrInfo &MII = TM.getInstrInfo();
 532   I = MBB.end();
 533   do {
 534     --I;
 535   } while ((MII.isReturn((*I)->getOpcode()) ||
 536             MII.isBranch((*I)->getOpcode())) && I != MBB.begin());
 537
 538   if (!MII.isReturn((*I)->getOpcode()) && !MII.isBranch((*I)->getOpcode()))
 539     ++I;
 540
 541   // Spill all physical registers holding virtual registers now.
 542   while (!PhysRegsUsed.empty())
 543     spillVirtReg(MBB, I, PhysRegsUsed.begin()->second,
 544                  PhysRegsUsed.begin()->first);
 545
 546   assert(Virt2PhysRegMap.empty() && "Virtual registers still in phys regs?");
 547   assert(PhysRegsUseOrder.empty() && "Physical regs still allocated?");
 548 }
 549
 550
 551 /// EmitPrologue - Use the register info object to add a prologue to the
 552 /// function and save any callee saved registers we are responsible for.
 553 ///
 554 void RA::EmitPrologue() {
 555   // Get a list of the callee saved registers, so that we can save them on entry
 556   // to the function.
 557   //
 558
 559   MachineBasicBlock &MBB = MF->front();   // Prolog goes in entry BB
 560   MachineBasicBlock::iterator I = MBB.begin();
 561
 562   const unsigned *CSRegs = RegInfo.getCalleeSaveRegs();
 563   for (unsigned i = 0; CSRegs[i]; ++i) {
 564     const TargetRegisterClass *RegClass = PhysRegClasses[CSRegs[i]];
 565     unsigned Offset = getStackSpaceFor(CSRegs[i], RegClass);
 566
 567     // Insert the spill to the stack frame...
 568     ++NumSpilled;
 569     I = RegInfo.storeReg2RegOffset(MBB, I, CSRegs[i], RegInfo.getFramePointer(),
 570                                    -Offset, RegClass->getDataSize());
 571   }
 572
 573   // Add prologue to the function...
 574   RegInfo.emitPrologue(*MF, NumBytesAllocated);
 575 }
 576
 577
 578 /// EmitEpilogue - Use the register info object to add a epilogue to the
 579 /// function and restore any callee saved registers we are responsible for.
 580 ///
 581 void RA::EmitEpilogue(MachineBasicBlock &MBB) {
 582   // Insert instructions before the return.
 583   MachineBasicBlock::iterator I = --MBB.end();
 584
 585   const unsigned *CSRegs = RegInfo.getCalleeSaveRegs();
 586   for (unsigned i = 0; CSRegs[i]; ++i) {
 587     const TargetRegisterClass *RegClass = PhysRegClasses[CSRegs[i]];
 588     unsigned Offset = getStackSpaceFor(CSRegs[i], RegClass);
 589     ++NumReloaded;
 590     I = RegInfo.loadRegOffset2Reg(MBB, I, CSRegs[i], RegInfo.getFramePointer(),
 591                                   -Offset, RegClass->getDataSize());
 592     --I;  // Insert in reverse order
 593   }
 594
 595   RegInfo.emitEpilogue(MBB, NumBytesAllocated);
 596 }
 597
 598
 599 /// runOnMachineFunction - Register allocate the whole function
 600 ///
 601 bool RA::runOnMachineFunction(MachineFunction &Fn) {
 602   DEBUG(std::cerr << "Machine Function " << "\n");
 603   MF = &Fn;
 604
 605   // First pass: eliminate PHI instructions by inserting copies into predecessor
 606   // blocks.
 607   // FIXME: In this pass, count how many uses of each VReg exist!
 608   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 609        MBB != MBBe; ++MBB)
 610     EliminatePHINodes(*MBB);
 611
 612   // Loop over all of the basic blocks, eliminating virtual register references
 613   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 614        MBB != MBBe; ++MBB)
 615     AllocateBasicBlock(*MBB);
 616
 617
 618   // Emit a prologue for the function...
 619   EmitPrologue();
 620
 621   const MachineInstrInfo &MII = TM.getInstrInfo();
 622
 623   // Add epilogue to restore the callee-save registers in each exiting block
 624   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 625        MBB != MBBe; ++MBB) {
 626     // If last instruction is a return instruction, add an epilogue
 627     if (MII.isReturn(MBB->back()->getOpcode()))
 628       EmitEpilogue(*MBB);
 629   }
 630
 631   cleanupAfterFunction();
 632   return true;
 633 }
 634
 635 Pass *createLocalRegisterAllocator(TargetMachine &TM) {
 636   return new RA(TM);
 637 }