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