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