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