lib/CodeGen/RegAllocLocal.cpp

   1 //===-- RegAllocLocal.cpp - A BasicBlock generic register allocator -------===//
   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 // This register allocator allocates registers to a basic block at a time,
  11 // attempting to keep values in registers and reusing registers as appropriate.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "regalloc"
  16 #include "llvm/CodeGen/Passes.h"
  17 #include "llvm/CodeGen/MachineFunctionPass.h"
  18 #include "llvm/CodeGen/MachineInstr.h"
  19 #include "llvm/CodeGen/SSARegMap.h"
  20 #include "llvm/CodeGen/MachineFrameInfo.h"
  21 #include "llvm/CodeGen/LiveVariables.h"
  22 #include "llvm/CodeGen/TwoAddressInstructionPass.h"
  23 #include "llvm/Target/TargetInstrInfo.h"
  24 #include "llvm/Target/TargetMachine.h"
  25 #include "Support/CommandLine.h"
  26 #include "Support/Debug.h"
  27 #include "Support/Statistic.h"
  28 #include <iostream>
  29
  30 namespace llvm {
  31
  32 namespace {
  33   Statistic<> NumSpilled ("ra-local", "Number of registers spilled");
  34   Statistic<> NumReloaded("ra-local", "Number of registers reloaded");
  35   cl::opt<bool> DisableKill("disable-kill", cl::Hidden,
  36                             cl::desc("Disable register kill in local-ra"));
  37
  38   class RA : public MachineFunctionPass {
  39     const TargetMachine *TM;
  40     MachineFunction *MF;
  41     const MRegisterInfo *RegInfo;
  42     LiveVariables *LV;
  43
  44     // StackSlotForVirtReg - Maps virtual regs to the frame index where these
  45     // values are spilled.
  46     std::map<unsigned, int> StackSlotForVirtReg;
  47
  48     // Virt2PhysRegMap - This map contains entries for each virtual register
  49     // that is currently available in a physical register.
  50     //
  51     std::map<unsigned, unsigned> Virt2PhysRegMap;
  52
  53     // PhysRegsUsed - This map contains entries for each physical register that
  54     // currently has a value (ie, it is in Virt2PhysRegMap).  The value mapped
  55     // to is the virtual register corresponding to the physical register (the
  56     // inverse of the Virt2PhysRegMap), or 0.  The value is set to 0 if this
  57     // register is pinned because it is used by a future instruction.
  58     //
  59     std::map<unsigned, unsigned> PhysRegsUsed;
  60
  61     // PhysRegsUseOrder - This contains a list of the physical registers that
  62     // currently have a virtual register value in them.  This list provides an
  63     // ordering of registers, imposing a reallocation order.  This list is only
  64     // used if all registers are allocated and we have to spill one, in which
  65     // case we spill the least recently used register.  Entries at the front of
  66     // the list are the least recently used registers, entries at the back are
  67     // the most recently used.
  68     //
  69     std::vector<unsigned> PhysRegsUseOrder;
  70
  71     // VirtRegModified - This bitset contains information about which virtual
  72     // registers need to be spilled back to memory when their registers are
  73     // scavenged.  If a virtual register has simply been rematerialized, there
  74     // is no reason to spill it to memory when we need the register back.
  75     //
  76     std::vector<bool> VirtRegModified;
  77
  78     void markVirtRegModified(unsigned Reg, bool Val = true) {
  79       assert(Reg >= MRegisterInfo::FirstVirtualRegister && "Illegal VirtReg!");
  80       Reg -= MRegisterInfo::FirstVirtualRegister;
  81       if (VirtRegModified.size() <= Reg) VirtRegModified.resize(Reg+1);
  82       VirtRegModified[Reg] = Val;
  83     }
  84
  85     bool isVirtRegModified(unsigned Reg) const {
  86       assert(Reg >= MRegisterInfo::FirstVirtualRegister && "Illegal VirtReg!");
  87       assert(Reg - MRegisterInfo::FirstVirtualRegister < VirtRegModified.size()
  88              && "Illegal virtual register!");
  89       return VirtRegModified[Reg - MRegisterInfo::FirstVirtualRegister];
  90     }
  91
  92     void MarkPhysRegRecentlyUsed(unsigned Reg) {
  93       assert(!PhysRegsUseOrder.empty() && "No registers used!");
  94       if (PhysRegsUseOrder.back() == Reg) return;  // Already most recently used
  95
  96       for (unsigned i = PhysRegsUseOrder.size(); i != 0; --i)
  97         if (areRegsEqual(Reg, PhysRegsUseOrder[i-1])) {
  98           unsigned RegMatch = PhysRegsUseOrder[i-1];       // remove from middle
  99           PhysRegsUseOrder.erase(PhysRegsUseOrder.begin()+i-1);
 100           // Add it to the end of the list
 101           PhysRegsUseOrder.push_back(RegMatch);
 102           if (RegMatch == Reg)
 103             return;    // Found an exact match, exit early
 104         }
 105     }
 106
 107   public:
 108     virtual const char *getPassName() const {
 109       return "Local Register Allocator";
 110     }
 111
 112     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 113       if (!DisableKill)
 114         AU.addRequired<LiveVariables>();
 115       AU.addRequiredID(PHIEliminationID);
 116       AU.addRequired<TwoAddressInstructionPass>();
 117       MachineFunctionPass::getAnalysisUsage(AU);
 118     }
 119
 120   private:
 121     /// runOnMachineFunction - Register allocate the whole function
 122     bool runOnMachineFunction(MachineFunction &Fn);
 123
 124     /// AllocateBasicBlock - Register allocate the specified basic block.
 125     void AllocateBasicBlock(MachineBasicBlock &MBB);
 126
 127
 128     /// areRegsEqual - This method returns true if the specified registers are
 129     /// related to each other.  To do this, it checks to see if they are equal
 130     /// or if the first register is in the alias set of the second register.
 131     ///
 132     bool areRegsEqual(unsigned R1, unsigned R2) const {
 133       if (R1 == R2) return true;
 134       for (const unsigned *AliasSet = RegInfo->getAliasSet(R2);
 135            *AliasSet; ++AliasSet) {
 136         if (*AliasSet == R1) return true;
 137       }
 138       return false;
 139     }
 140
 141     /// getStackSpaceFor - This returns the frame index of the specified virtual
 142     /// register on the stack, allocating space if necessary.
 143     int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC);
 144
 145     /// removePhysReg - This method marks the specified physical register as no
 146     /// longer being in use.
 147     ///
 148     void removePhysReg(unsigned PhysReg);
 149
 150     /// spillVirtReg - This method spills the value specified by PhysReg into
 151     /// the virtual register slot specified by VirtReg.  It then updates the RA
 152     /// data structures to indicate the fact that PhysReg is now available.
 153     ///
 154     void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 155                       unsigned VirtReg, unsigned PhysReg);
 156
 157     /// spillPhysReg - This method spills the specified physical register into
 158     /// the virtual register slot associated with it.  If OnlyVirtRegs is set to
 159     /// true, then the request is ignored if the physical register does not
 160     /// contain a virtual register.
 161     ///
 162     void spillPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 163                       unsigned PhysReg, bool OnlyVirtRegs = false);
 164
 165     /// assignVirtToPhysReg - This method updates local state so that we know
 166     /// that PhysReg is the proper container for VirtReg now.  The physical
 167     /// register must not be used for anything else when this is called.
 168     ///
 169     void assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg);
 170
 171     /// liberatePhysReg - Make sure the specified physical register is available
 172     /// for use.  If there is currently a value in it, it is either moved out of
 173     /// the way or spilled to memory.
 174     ///
 175     void liberatePhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 176                          unsigned PhysReg);
 177
 178     /// isPhysRegAvailable - Return true if the specified physical register is
 179     /// free and available for use.  This also includes checking to see if
 180     /// aliased registers are all free...
 181     ///
 182     bool isPhysRegAvailable(unsigned PhysReg) const;
 183
 184     /// getFreeReg - Look to see if there is a free register available in the
 185     /// specified register class.  If not, return 0.
 186     ///
 187     unsigned getFreeReg(const TargetRegisterClass *RC);
 188
 189     /// getReg - Find a physical register to hold the specified virtual
 190     /// register.  If all compatible physical registers are used, this method
 191     /// spills the last used virtual register to the stack, and uses that
 192     /// register.
 193     ///
 194     unsigned getReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 195                     unsigned VirtReg);
 196
 197     /// reloadVirtReg - This method loads the specified virtual register into a
 198     /// physical register, returning the physical register chosen.  This updates
 199     /// the regalloc data structures to reflect the fact that the virtual reg is
 200     /// now alive in a physical register, and the previous one isn't.
 201     ///
 202     unsigned reloadVirtReg(MachineBasicBlock &MBB,
 203                            MachineBasicBlock::iterator &I, unsigned VirtReg);
 204
 205     void reloadPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 206                        unsigned PhysReg);
 207   };
 208 }
 209
 210 /// getStackSpaceFor - This allocates space for the specified virtual register
 211 /// to be held on the stack.
 212 int RA::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) {
 213   // Find the location Reg would belong...
 214   std::map<unsigned, int>::iterator I =StackSlotForVirtReg.lower_bound(VirtReg);
 215
 216   if (I != StackSlotForVirtReg.end() && I->first == VirtReg)
 217     return I->second;          // Already has space allocated?
 218
 219   // Allocate a new stack object for this spill location...
 220   int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC);
 221
 222   // Assign the slot...
 223   StackSlotForVirtReg.insert(I, std::make_pair(VirtReg, FrameIdx));
 224   return FrameIdx;
 225 }
 226
 227
 228 /// removePhysReg - This method marks the specified physical register as no
 229 /// longer being in use.
 230 ///
 231 void RA::removePhysReg(unsigned PhysReg) {
 232   PhysRegsUsed.erase(PhysReg);      // PhyReg no longer used
 233
 234   std::vector<unsigned>::iterator It =
 235     std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), PhysReg);
 236   assert(It != PhysRegsUseOrder.end() &&
 237          "Spilled a physical register, but it was not in use list!");
 238   PhysRegsUseOrder.erase(It);
 239 }
 240
 241
 242 /// spillVirtReg - This method spills the value specified by PhysReg into the
 243 /// virtual register slot specified by VirtReg.  It then updates the RA data
 244 /// structures to indicate the fact that PhysReg is now available.
 245 ///
 246 void RA::spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 247                       unsigned VirtReg, unsigned PhysReg) {
 248   if (!VirtReg && DisableKill) return;
 249   assert(VirtReg && "Spilling a physical register is illegal!"
 250          " Must not have appropriate kill for the register or use exists beyond"
 251          " the intended one.");
 252   DEBUG(std::cerr << "  Spilling register " << RegInfo->getName(PhysReg);
 253         std::cerr << " containing %reg" << VirtReg;
 254         if (!isVirtRegModified(VirtReg))
 255         std::cerr << " which has not been modified, so no store necessary!");
 256
 257   // Otherwise, there is a virtual register corresponding to this physical
 258   // register.  We only need to spill it into its stack slot if it has been
 259   // modified.
 260   if (isVirtRegModified(VirtReg)) {
 261     const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg);
 262     int FrameIndex = getStackSpaceFor(VirtReg, RC);
 263     DEBUG(std::cerr << " to stack slot #" << FrameIndex);
 264     RegInfo->storeRegToStackSlot(MBB, I, PhysReg, FrameIndex, RC);
 265     ++NumSpilled;   // Update statistics
 266   }
 267   Virt2PhysRegMap.erase(VirtReg);   // VirtReg no longer available
 268
 269   DEBUG(std::cerr << "\n");
 270   removePhysReg(PhysReg);
 271 }
 272
 273
 274 /// spillPhysReg - This method spills the specified physical register into the
 275 /// virtual register slot associated with it.  If OnlyVirtRegs is set to true,
 276 /// then the request is ignored if the physical register does not contain a
 277 /// virtual register.
 278 ///
 279 void RA::spillPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 280                       unsigned PhysReg, bool OnlyVirtRegs) {
 281   std::map<unsigned, unsigned>::iterator PI = PhysRegsUsed.find(PhysReg);
 282   if (PI != PhysRegsUsed.end()) {             // Only spill it if it's used!
 283     if (PI->second || !OnlyVirtRegs)
 284       spillVirtReg(MBB, I, PI->second, PhysReg);
 285   } else {
 286     // If the selected register aliases any other registers, we must make
 287     // sure that one of the aliases isn't alive...
 288     for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg);
 289          *AliasSet; ++AliasSet) {
 290       PI = PhysRegsUsed.find(*AliasSet);
 291       if (PI != PhysRegsUsed.end())     // Spill aliased register...
 292         if (PI->second || !OnlyVirtRegs)
 293           spillVirtReg(MBB, I, PI->second, *AliasSet);
 294     }
 295   }
 296 }
 297
 298
 299 /// assignVirtToPhysReg - This method updates local state so that we know
 300 /// that PhysReg is the proper container for VirtReg now.  The physical
 301 /// register must not be used for anything else when this is called.
 302 ///
 303 void RA::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) {
 304   assert(PhysRegsUsed.find(PhysReg) == PhysRegsUsed.end() &&
 305          "Phys reg already assigned!");
 306   // Update information to note the fact that this register was just used, and
 307   // it holds VirtReg.
 308   PhysRegsUsed[PhysReg] = VirtReg;
 309   Virt2PhysRegMap[VirtReg] = PhysReg;
 310   PhysRegsUseOrder.push_back(PhysReg);   // New use of PhysReg
 311 }
 312
 313
 314 /// isPhysRegAvailable - Return true if the specified physical register is free
 315 /// and available for use.  This also includes checking to see if aliased
 316 /// registers are all free...
 317 ///
 318 bool RA::isPhysRegAvailable(unsigned PhysReg) const {
 319   if (PhysRegsUsed.count(PhysReg)) return false;
 320
 321   // If the selected register aliases any other allocated registers, it is
 322   // not free!
 323   for (const unsigned *AliasSet = RegInfo->getAliasSet(PhysReg);
 324        *AliasSet; ++AliasSet)
 325     if (PhysRegsUsed.count(*AliasSet)) // Aliased register in use?
 326       return false;                    // Can't use this reg then.
 327   return true;
 328 }
 329
 330
 331 /// getFreeReg - Look to see if there is a free register available in the
 332 /// specified register class.  If not, return 0.
 333 ///
 334 unsigned RA::getFreeReg(const TargetRegisterClass *RC) {
 335   // Get iterators defining the range of registers that are valid to allocate in
 336   // this class, which also specifies the preferred allocation order.
 337   TargetRegisterClass::iterator RI = RC->allocation_order_begin(*MF);
 338   TargetRegisterClass::iterator RE = RC->allocation_order_end(*MF);
 339
 340   for (; RI != RE; ++RI)
 341     if (isPhysRegAvailable(*RI)) {       // Is reg unused?
 342       assert(*RI != 0 && "Cannot use register!");
 343       return *RI; // Found an unused register!
 344     }
 345   return 0;
 346 }
 347
 348
 349 /// liberatePhysReg - Make sure the specified physical register is available for
 350 /// use.  If there is currently a value in it, it is either moved out of the way
 351 /// or spilled to memory.
 352 ///
 353 void RA::liberatePhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 354                          unsigned PhysReg) {
 355   // FIXME: This code checks to see if a register is available, but it really
 356   // wants to know if a reg is available BEFORE the instruction executes.  If
 357   // called after killed operands are freed, it runs the risk of reallocating a
 358   // used operand...
 359 #if 0
 360   if (isPhysRegAvailable(PhysReg)) return;  // Already available...
 361
 362   // Check to see if the register is directly used, not indirectly used through
 363   // aliases.  If aliased registers are the ones actually used, we cannot be
 364   // sure that we will be able to save the whole thing if we do a reg-reg copy.
 365   std::map<unsigned, unsigned>::iterator PRUI = PhysRegsUsed.find(PhysReg);
 366   if (PRUI != PhysRegsUsed.end()) {
 367     unsigned VirtReg = PRUI->second;   // The virtual register held...
 368
 369     // Check to see if there is a compatible register available.  If so, we can
 370     // move the value into the new register...
 371     //
 372     const TargetRegisterClass *RC = RegInfo->getRegClass(PhysReg);
 373     if (unsigned NewReg = getFreeReg(RC)) {
 374       // Emit the code to copy the value...
 375       RegInfo->copyRegToReg(MBB, I, NewReg, PhysReg, RC);
 376
 377       // Update our internal state to indicate that PhysReg is available and Reg
 378       // isn't.
 379       Virt2PhysRegMap.erase(VirtReg);
 380       removePhysReg(PhysReg);  // Free the physreg
 381
 382       // Move reference over to new register...
 383       assignVirtToPhysReg(VirtReg, NewReg);
 384       return;
 385     }
 386   }
 387 #endif
 388   spillPhysReg(MBB, I, PhysReg);
 389 }
 390
 391
 392 /// getReg - Find a physical register to hold the specified virtual
 393 /// register.  If all compatible physical registers are used, this method spills
 394 /// the last used virtual register to the stack, and uses that register.
 395 ///
 396 unsigned RA::getReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 397                     unsigned VirtReg) {
 398   const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg);
 399
 400   // First check to see if we have a free register of the requested type...
 401   unsigned PhysReg = getFreeReg(RC);
 402
 403   // If we didn't find an unused register, scavenge one now!
 404   if (PhysReg == 0) {
 405     assert(!PhysRegsUseOrder.empty() && "No allocated registers??");
 406
 407     // Loop over all of the preallocated registers from the least recently used
 408     // to the most recently used.  When we find one that is capable of holding
 409     // our register, use it.
 410     for (unsigned i = 0; PhysReg == 0; ++i) {
 411       assert(i != PhysRegsUseOrder.size() &&
 412              "Couldn't find a register of the appropriate class!");
 413
 414       unsigned R = PhysRegsUseOrder[i];
 415
 416       // We can only use this register if it holds a virtual register (ie, it
 417       // can be spilled).  Do not use it if it is an explicitly allocated
 418       // physical register!
 419       assert(PhysRegsUsed.count(R) &&
 420              "PhysReg in PhysRegsUseOrder, but is not allocated?");
 421       if (PhysRegsUsed[R]) {
 422         // If the current register is compatible, use it.
 423         if (RegInfo->getRegClass(R) == RC) {
 424           PhysReg = R;
 425           break;
 426         } else {
 427           // If one of the registers aliased to the current register is
 428           // compatible, use it.
 429           for (const unsigned *AliasSet = RegInfo->getAliasSet(R);
 430                *AliasSet; ++AliasSet) {
 431             if (RegInfo->getRegClass(*AliasSet) == RC) {
 432               PhysReg = *AliasSet;    // Take an aliased register
 433               break;
 434             }
 435           }
 436         }
 437       }
 438     }
 439
 440     assert(PhysReg && "Physical register not assigned!?!?");
 441
 442     // At this point PhysRegsUseOrder[i] is the least recently used register of
 443     // compatible register class.  Spill it to memory and reap its remains.
 444     spillPhysReg(MBB, I, PhysReg);
 445   }
 446
 447   // Now that we know which register we need to assign this to, do it now!
 448   assignVirtToPhysReg(VirtReg, PhysReg);
 449   return PhysReg;
 450 }
 451
 452
 453 /// reloadVirtReg - This method loads the specified virtual register into a
 454 /// physical register, returning the physical register chosen.  This updates the
 455 /// regalloc data structures to reflect the fact that the virtual reg is now
 456 /// alive in a physical register, and the previous one isn't.
 457 ///
 458 unsigned RA::reloadVirtReg(MachineBasicBlock &MBB,
 459                            MachineBasicBlock::iterator &I,
 460                            unsigned VirtReg) {
 461   std::map<unsigned, unsigned>::iterator It = Virt2PhysRegMap.find(VirtReg);
 462   if (It != Virt2PhysRegMap.end()) {
 463     MarkPhysRegRecentlyUsed(It->second);
 464     return It->second;               // Already have this value available!
 465   }
 466
 467   unsigned PhysReg = getReg(MBB, I, VirtReg);
 468
 469   const TargetRegisterClass *RC = MF->getSSARegMap()->getRegClass(VirtReg);
 470   int FrameIndex = getStackSpaceFor(VirtReg, RC);
 471
 472   markVirtRegModified(VirtReg, false);   // Note that this reg was just reloaded
 473
 474   DEBUG(std::cerr << "  Reloading %reg" << VirtReg << " into "
 475                   << RegInfo->getName(PhysReg) << "\n");
 476
 477   // Add move instruction(s)
 478   RegInfo->loadRegFromStackSlot(MBB, I, PhysReg, FrameIndex, RC);
 479   ++NumReloaded;    // Update statistics
 480   return PhysReg;
 481 }
 482
 483
 484
 485 void RA::AllocateBasicBlock(MachineBasicBlock &MBB) {
 486   // loop over each instruction
 487   MachineBasicBlock::iterator I = MBB.begin();
 488   for (; I != MBB.end(); ++I) {
 489     MachineInstr *MI = *I;
 490     const TargetInstrDescriptor &TID = TM->getInstrInfo().get(MI->getOpcode());
 491     DEBUG(std::cerr << "\nStarting RegAlloc of: " << *MI;
 492           std::cerr << "  Regs have values: ";
 493           for (std::map<unsigned, unsigned>::const_iterator
 494                  I = PhysRegsUsed.begin(), E = PhysRegsUsed.end(); I != E; ++I)
 495              std::cerr << "[" << RegInfo->getName(I->first)
 496                        << ",%reg" << I->second << "] ";
 497           std::cerr << "\n");
 498
 499     // Loop over the implicit uses, making sure that they are at the head of the
 500     // use order list, so they don't get reallocated.
 501     for (const unsigned *ImplicitUses = TID.ImplicitUses;
 502          *ImplicitUses; ++ImplicitUses)
 503         MarkPhysRegRecentlyUsed(*ImplicitUses);
 504
 505     // Get the used operands into registers.  This has the potential to spill
 506     // incoming values if we are out of registers.  Note that we completely
 507     // ignore physical register uses here.  We assume that if an explicit
 508     // physical register is referenced by the instruction, that it is guaranteed
 509     // to be live-in, or the input is badly hosed.
 510     //
 511     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
 512       if (MI->getOperand(i).isUse() &&
 513           !MI->getOperand(i).isDef() &&
 514           MI->getOperand(i).isVirtualRegister()){
 515         unsigned VirtSrcReg = MI->getOperand(i).getAllocatedRegNum();
 516         unsigned PhysSrcReg = reloadVirtReg(MBB, I, VirtSrcReg);
 517         MI->SetMachineOperandReg(i, PhysSrcReg);  // Assign the input register
 518       }
 519
 520     if (!DisableKill) {
 521       // If this instruction is the last user of anything in registers, kill the
 522       // value, freeing the register being used, so it doesn't need to be
 523       // spilled to memory.
 524       //
 525       for (LiveVariables::killed_iterator KI = LV->killed_begin(MI),
 526              KE = LV->killed_end(MI); KI != KE; ++KI) {
 527         unsigned VirtReg = KI->second;
 528         unsigned PhysReg = VirtReg;
 529         if (VirtReg >= MRegisterInfo::FirstVirtualRegister) {
 530           std::map<unsigned, unsigned>::iterator I =
 531             Virt2PhysRegMap.find(VirtReg);
 532           assert(I != Virt2PhysRegMap.end());
 533           PhysReg = I->second;
 534           Virt2PhysRegMap.erase(I);
 535         }
 536
 537         if (PhysReg) {
 538           DEBUG(std::cerr << "  Last use of " << RegInfo->getName(PhysReg)
 539                       << "[%reg" << VirtReg <<"], removing it from live set\n");
 540           removePhysReg(PhysReg);
 541         }
 542       }
 543     }
 544
 545     // Loop over all of the operands of the instruction, spilling registers that
 546     // are defined, and marking explicit destinations in the PhysRegsUsed map.
 547     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
 548       if (MI->getOperand(i).isDef() &&
 549           MI->getOperand(i).isPhysicalRegister()) {
 550         unsigned Reg = MI->getOperand(i).getAllocatedRegNum();
 551         spillPhysReg(MBB, I, Reg, true);  // Spill any existing value in the reg
 552         PhysRegsUsed[Reg] = 0;            // It is free and reserved now
 553         PhysRegsUseOrder.push_back(Reg);
 554       }
 555
 556     // Loop over the implicit defs, spilling them as well.
 557     for (const unsigned *ImplicitDefs = TID.ImplicitDefs;
 558          *ImplicitDefs; ++ImplicitDefs) {
 559       unsigned Reg = *ImplicitDefs;
 560       spillPhysReg(MBB, I, Reg);
 561       PhysRegsUseOrder.push_back(Reg);
 562       PhysRegsUsed[Reg] = 0;            // It is free and reserved now
 563     }
 564
 565     // Okay, we have allocated all of the source operands and spilled any values
 566     // that would be destroyed by defs of this instruction.  Loop over the
 567     // implicit defs and assign them to a register, spilling incoming values if
 568     // we need to scavenge a register.
 569     //
 570     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
 571       if (MI->getOperand(i).isDef() &&
 572           MI->getOperand(i).isVirtualRegister()) {
 573         unsigned DestVirtReg = MI->getOperand(i).getAllocatedRegNum();
 574         unsigned DestPhysReg;
 575
 576         // If DestVirtReg already has a value, use it.
 577         std::map<unsigned, unsigned>::iterator DestI =
 578           Virt2PhysRegMap.find(DestVirtReg);
 579         if (DestI != Virt2PhysRegMap.end()) {
 580           DestPhysReg = DestI->second;
 581         }
 582         else {
 583           DestPhysReg = getReg(MBB, I, DestVirtReg);
 584         }
 585         markVirtRegModified(DestVirtReg);
 586         MI->SetMachineOperandReg(i, DestPhysReg);  // Assign the output register
 587       }
 588
 589     if (!DisableKill) {
 590       // If this instruction defines any registers that are immediately dead,
 591       // kill them now.
 592       //
 593       for (LiveVariables::killed_iterator KI = LV->dead_begin(MI),
 594              KE = LV->dead_end(MI); KI != KE; ++KI) {
 595         unsigned VirtReg = KI->second;
 596         unsigned PhysReg = VirtReg;
 597         if (VirtReg >= MRegisterInfo::FirstVirtualRegister) {
 598           std::map<unsigned, unsigned>::iterator I =
 599             Virt2PhysRegMap.find(VirtReg);
 600           assert(I != Virt2PhysRegMap.end());
 601           PhysReg = I->second;
 602           Virt2PhysRegMap.erase(I);
 603         }
 604
 605         if (PhysReg) {
 606           DEBUG(std::cerr << "  Register " << RegInfo->getName(PhysReg)
 607                           << " [%reg" << VirtReg
 608                           << "] is never used, removing it frame live list\n");
 609           removePhysReg(PhysReg);
 610         }
 611       }
 612     }
 613   }
 614
 615   // Rewind the iterator to point to the first flow control instruction...
 616   const TargetInstrInfo &TII = TM->getInstrInfo();
 617   I = MBB.end();
 618   while (I != MBB.begin() && TII.isTerminatorInstr((*(I-1))->getOpcode()))
 619     --I;
 620
 621   // Spill all physical registers holding virtual registers now.
 622   while (!PhysRegsUsed.empty())
 623     if (unsigned VirtReg = PhysRegsUsed.begin()->second)
 624       spillVirtReg(MBB, I, VirtReg, PhysRegsUsed.begin()->first);
 625     else
 626       removePhysReg(PhysRegsUsed.begin()->first);
 627
 628   for (std::map<unsigned, unsigned>::iterator I = Virt2PhysRegMap.begin(),
 629          E = Virt2PhysRegMap.end(); I != E; ++I)
 630     std::cerr << "Register still mapped: " << I->first << " -> "
 631               << I->second << "\n";
 632
 633   assert(Virt2PhysRegMap.empty() && "Virtual registers still in phys regs?");
 634
 635   // Clear any physical register which appear live at the end of the basic
 636   // block, but which do not hold any virtual registers.  e.g., the stack
 637   // pointer.
 638   PhysRegsUseOrder.clear();
 639 }
 640
 641
 642 /// runOnMachineFunction - Register allocate the whole function
 643 ///
 644 bool RA::runOnMachineFunction(MachineFunction &Fn) {
 645   DEBUG(std::cerr << "Machine Function " << "\n");
 646   MF = &Fn;
 647   TM = &Fn.getTarget();
 648   RegInfo = TM->getRegisterInfo();
 649
 650   if (!DisableKill)
 651     LV = &getAnalysis<LiveVariables>();
 652
 653   // Loop over all of the basic blocks, eliminating virtual register references
 654   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 655        MBB != MBBe; ++MBB)
 656     AllocateBasicBlock(*MBB);
 657
 658   StackSlotForVirtReg.clear();
 659   VirtRegModified.clear();
 660   return true;
 661 }
 662
 663 FunctionPass *createLocalRegisterAllocator() {
 664   return new RA();
 665 }
 666
 667 } // End llvm namespace