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