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