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