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 using namespace llvm;
  29
  30 namespace {
  31   Statistic<> NumStores("ra-local", "Number of stores added");
  32   Statistic<> NumLoads ("ra-local", "Number of loads added");
  33   Statistic<> NumFolded("ra-local", "Number of loads/stores folded into "
  34                         "instructions");
  35   class RA : public MachineFunctionPass {
  36     const TargetMachine *TM;
  37     MachineFunction *MF;
  38     const MRegisterInfo *RegInfo;
  39     LiveVariables *LV;
  40
  41     // StackSlotForVirtReg - Maps virtual regs to the frame index where these
  42     // values are spilled.
  43     std::map<unsigned, int> StackSlotForVirtReg;
  44
  45     // Virt2PhysRegMap - This map contains entries for each virtual register
  46     // that is currently available in a physical register.
  47     DenseMap<unsigned, VirtReg2IndexFunctor> Virt2PhysRegMap;
  48
  49     unsigned &getVirt2PhysRegMapSlot(unsigned VirtReg) {
  50       return Virt2PhysRegMap[VirtReg];
  51     }
  52
  53     // PhysRegsUsed - This array is effectively a map, containing entries for
  54     // each physical register that currently has a value (ie, it is in
  55     // Virt2PhysRegMap).  The value mapped to is the virtual register
  56     // corresponding to the physical register (the inverse of the
  57     // Virt2PhysRegMap), or 0.  The value is set to 0 if this register is pinned
  58     // because it is used by a future instruction.  If the entry for a physical
  59     // register is -1, then the physical register is "not in the map".
  60     //
  61     std::vector<int> PhysRegsUsed;
  62
  63     // PhysRegsUseOrder - This contains a list of the physical registers that
  64     // currently have a virtual register value in them.  This list provides an
  65     // ordering of registers, imposing a reallocation order.  This list is only
  66     // used if all registers are allocated and we have to spill one, in which
  67     // case we spill the least recently used register.  Entries at the front of
  68     // the list are the least recently used registers, entries at the back are
  69     // the most recently used.
  70     //
  71     std::vector<unsigned> PhysRegsUseOrder;
  72
  73     // VirtRegModified - This bitset contains information about which virtual
  74     // registers need to be spilled back to memory when their registers are
  75     // scavenged.  If a virtual register has simply been rematerialized, there
  76     // is no reason to spill it to memory when we need the register back.
  77     //
  78     std::vector<bool> VirtRegModified;
  79
  80     void markVirtRegModified(unsigned Reg, bool Val = true) {
  81       assert(MRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!");
  82       Reg -= MRegisterInfo::FirstVirtualRegister;
  83       if (VirtRegModified.size() <= Reg) VirtRegModified.resize(Reg+1);
  84       VirtRegModified[Reg] = Val;
  85     }
  86
  87     bool isVirtRegModified(unsigned Reg) const {
  88       assert(MRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!");
  89       assert(Reg - MRegisterInfo::FirstVirtualRegister < VirtRegModified.size()
  90              && "Illegal virtual register!");
  91       return VirtRegModified[Reg - MRegisterInfo::FirstVirtualRegister];
  92     }
  93
  94     void MarkPhysRegRecentlyUsed(unsigned Reg) {
  95       if(PhysRegsUseOrder.empty() ||
  96          PhysRegsUseOrder.back() == Reg) return;  // Already most recently used
  97
  98       for (unsigned i = PhysRegsUseOrder.size(); i != 0; --i)
  99         if (areRegsEqual(Reg, PhysRegsUseOrder[i-1])) {
 100           unsigned RegMatch = PhysRegsUseOrder[i-1];       // remove from middle
 101           PhysRegsUseOrder.erase(PhysRegsUseOrder.begin()+i-1);
 102           // Add it to the end of the list
 103           PhysRegsUseOrder.push_back(RegMatch);
 104           if (RegMatch == Reg)
 105             return;    // Found an exact match, exit early
 106         }
 107     }
 108
 109   public:
 110     virtual const char *getPassName() const {
 111       return "Local Register Allocator";
 112     }
 113
 114     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 115       AU.addRequired<LiveVariables>();
 116       AU.addRequiredID(PHIEliminationID);
 117       AU.addRequiredID(TwoAddressInstructionPassID);
 118       MachineFunctionPass::getAnalysisUsage(AU);
 119     }
 120
 121   private:
 122     /// runOnMachineFunction - Register allocate the whole function
 123     bool runOnMachineFunction(MachineFunction &Fn);
 124
 125     /// AllocateBasicBlock - Register allocate the specified basic block.
 126     void AllocateBasicBlock(MachineBasicBlock &MBB);
 127
 128
 129     /// areRegsEqual - This method returns true if the specified registers are
 130     /// related to each other.  To do this, it checks to see if they are equal
 131     /// or if the first register is in the alias set of the second register.
 132     ///
 133     bool areRegsEqual(unsigned R1, unsigned R2) const {
 134       if (R1 == R2) return true;
 135       for (const unsigned *AliasSet = RegInfo->getAliasSet(R2);
 136            *AliasSet; ++AliasSet) {
 137         if (*AliasSet == R1) return true;
 138       }
 139       return false;
 140     }
 141
 142     /// getStackSpaceFor - This returns the frame index of the specified virtual
 143     /// register on the stack, allocating space if necessary.
 144     int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC);
 145
 146     /// removePhysReg - This method marks the specified physical register as no
 147     /// longer being in use.
 148     ///
 149     void removePhysReg(unsigned PhysReg);
 150
 151     /// spillVirtReg - This method spills the value specified by PhysReg into
 152     /// the virtual register slot specified by VirtReg.  It then updates the RA
 153     /// data structures to indicate the fact that PhysReg is now available.
 154     ///
 155     void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
 156                       unsigned VirtReg, unsigned PhysReg);
 157
 158     /// spillPhysReg - This method spills the specified physical register into
 159     /// the virtual register slot associated with it.  If OnlyVirtRegs is set to
 160     /// true, then the request is ignored if the physical register does not
 161     /// contain a virtual register.
 162     ///
 163     void spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I,
 164                       unsigned PhysReg, bool OnlyVirtRegs = false);
 165
 166     /// assignVirtToPhysReg - This method updates local state so that we know
 167     /// that PhysReg is the proper container for VirtReg now.  The physical
 168     /// register must not be used for anything else when this is called.
 169     ///
 170     void assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg);
 171
 172     /// liberatePhysReg - Make sure the specified physical register is available
 173     /// for use.  If there is currently a value in it, it is either moved out of
 174     /// the way or spilled to memory.
 175     ///
 176     void liberatePhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 177                          unsigned PhysReg);
 178
 179     /// isPhysRegAvailable - Return true if the specified physical register is
 180     /// free and available for use.  This also includes checking to see if
 181     /// aliased registers are all free...
 182     ///
 183     bool isPhysRegAvailable(unsigned PhysReg) const;
 184
 185     /// getFreeReg - Look to see if there is a free register available in the
 186     /// specified register class.  If not, return 0.
 187     ///
 188     unsigned getFreeReg(const TargetRegisterClass *RC);
 189
 190     /// getReg - Find a physical register to hold the specified virtual
 191     /// register.  If all compatible physical registers are used, this method
 192     /// spills the last used virtual register to the stack, and uses that
 193     /// register.
 194     ///
 195     unsigned getReg(MachineBasicBlock &MBB, MachineInstr *MI,
 196                     unsigned VirtReg);
 197
 198     /// reloadVirtReg - This method transforms the specified specified virtual
 199     /// register use to refer to a physical register.  This method may do this
 200     /// in one of several ways: if the register is available in a physical
 201     /// register already, it uses that physical register.  If the value is not
 202     /// in a physical register, and if there are physical registers available,
 203     /// it loads it into a register.  If register pressure is high, and it is
 204     /// possible, it tries to fold the load of the virtual register into the
 205     /// instruction itself.  It avoids doing this if register pressure is low to
 206     /// improve the chance that subsequent instructions can use the reloaded
 207     /// value.  This method returns the modified instruction.
 208     ///
 209     MachineInstr *reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
 210                                 unsigned OpNum);
 211
 212
 213     void reloadPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 214                        unsigned PhysReg);
 215   };
 216 }
 217
 218 /// getStackSpaceFor - This allocates space for the specified virtual register
 219 /// to be held on the stack.
 220 int RA::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) {
 221   // Find the location Reg would belong...
 222   std::map<unsigned, int>::iterator I =StackSlotForVirtReg.lower_bound(VirtReg);
 223
 224   if (I != StackSlotForVirtReg.end() && I->first == VirtReg)
 225     return I->second;          // Already has space allocated?
 226
 227   // Allocate a new stack object for this spill location...
 228   int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC->getSize(),
 229                                                        RC->getAlignment());
 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);
 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     if (MachineInstr* FMI = RegInfo->foldMemoryOperand(MI, OpNum, FrameIndex)){
 491       ++NumFolded;
 492       // Since we changed the address of MI, make sure to update live variables
 493       // to know that the new instruction has the properties of the old one.
 494       LV->instructionChanged(MI, FMI);
 495       return MBB.insert(MBB.erase(MI), FMI);
 496     }
 497
 498     // It looks like we can't fold this virtual register load into this
 499     // instruction.  Force some poor hapless value out of the register file to
 500     // make room for the new register, and reload it.
 501     PhysReg = getReg(MBB, MI, VirtReg);
 502   }
 503
 504   markVirtRegModified(VirtReg, false);   // Note that this reg was just reloaded
 505
 506   DEBUG(std::cerr << "  Reloading %reg" << VirtReg << " into "
 507                   << RegInfo->getName(PhysReg) << "\n");
 508
 509   // Add move instruction(s)
 510   RegInfo->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex);
 511   ++NumLoads;    // Update statistics
 512
 513   MI->SetMachineOperandReg(OpNum, PhysReg);  // Assign the input register
 514   return MI;
 515 }
 516
 517
 518
 519 void RA::AllocateBasicBlock(MachineBasicBlock &MBB) {
 520   // loop over each instruction
 521   MachineBasicBlock::iterator MI = MBB.begin();
 522   for (; MI != MBB.end(); ++MI) {
 523     const TargetInstrDescriptor &TID = TM->getInstrInfo()->get(MI->getOpcode());
 524     DEBUG(std::cerr << "\nStarting RegAlloc of: " << *MI;
 525           std::cerr << "  Regs have values: ";
 526           for (unsigned i = 0; i != RegInfo->getNumRegs(); ++i)
 527             if (PhysRegsUsed[i] != -1)
 528                std::cerr << "[" << RegInfo->getName(i)
 529                          << ",%reg" << PhysRegsUsed[i] << "] ";
 530           std::cerr << "\n");
 531
 532     // Loop over the implicit uses, making sure that they are at the head of the
 533     // use order list, so they don't get reallocated.
 534     for (const unsigned *ImplicitUses = TID.ImplicitUses;
 535          *ImplicitUses; ++ImplicitUses)
 536       MarkPhysRegRecentlyUsed(*ImplicitUses);
 537
 538     // Get the used operands into registers.  This has the potential to spill
 539     // incoming values if we are out of registers.  Note that we completely
 540     // ignore physical register uses here.  We assume that if an explicit
 541     // physical register is referenced by the instruction, that it is guaranteed
 542     // to be live-in, or the input is badly hosed.
 543     //
 544     for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
 545       MachineOperand& MO = MI->getOperand(i);
 546       // here we are looking for only used operands (never def&use)
 547       if (!MO.isDef() && MO.isRegister() && MO.getReg() &&
 548           MRegisterInfo::isVirtualRegister(MO.getReg()))
 549         MI = reloadVirtReg(MBB, MI, i);
 550     }
 551
 552     // If this instruction is the last user of anything in registers, kill the
 553     // value, freeing the register being used, so it doesn't need to be
 554     // spilled to memory.
 555     //
 556     for (LiveVariables::killed_iterator KI = LV->killed_begin(MI),
 557            KE = LV->killed_end(MI); KI != KE; ++KI) {
 558       unsigned VirtReg = KI->second;
 559       unsigned PhysReg = VirtReg;
 560       if (MRegisterInfo::isVirtualRegister(VirtReg)) {
 561         // If the virtual register was never materialized into a register, it
 562         // might not be in the map, but it won't hurt to zero it out anyway.
 563         unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg);
 564         PhysReg = PhysRegSlot;
 565         PhysRegSlot = 0;
 566       }
 567
 568       if (PhysReg) {
 569         DEBUG(std::cerr << "  Last use of " << RegInfo->getName(PhysReg)
 570               << "[%reg" << VirtReg <<"], removing it from live set\n");
 571         removePhysReg(PhysReg);
 572       }
 573     }
 574
 575     // Loop over all of the operands of the instruction, spilling registers that
 576     // are defined, and marking explicit destinations in the PhysRegsUsed map.
 577     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 578       MachineOperand& MO = MI->getOperand(i);
 579       if (MO.isDef() && MO.isRegister() && MO.getReg() &&
 580           MRegisterInfo::isPhysicalRegister(MO.getReg())) {
 581         unsigned Reg = MO.getReg();
 582         spillPhysReg(MBB, MI, Reg, true); // Spill any existing value in the reg
 583         PhysRegsUsed[Reg] = 0;            // It is free and reserved now
 584         PhysRegsUseOrder.push_back(Reg);
 585         for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg);
 586              *AliasSet; ++AliasSet) {
 587           PhysRegsUseOrder.push_back(*AliasSet);
 588           PhysRegsUsed[*AliasSet] = 0;  // It is free and reserved now
 589         }
 590       }
 591     }
 592
 593     // Loop over the implicit defs, spilling them as well.
 594     for (const unsigned *ImplicitDefs = TID.ImplicitDefs;
 595          *ImplicitDefs; ++ImplicitDefs) {
 596       unsigned Reg = *ImplicitDefs;
 597       spillPhysReg(MBB, MI, Reg, true);
 598       PhysRegsUseOrder.push_back(Reg);
 599       PhysRegsUsed[Reg] = 0;            // It is free and reserved now
 600       for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg);
 601            *AliasSet; ++AliasSet) {
 602         PhysRegsUseOrder.push_back(*AliasSet);
 603         PhysRegsUsed[*AliasSet] = 0;  // It is free and reserved now
 604       }
 605     }
 606
 607     // Okay, we have allocated all of the source operands and spilled any values
 608     // that would be destroyed by defs of this instruction.  Loop over the
 609     // implicit defs and assign them to a register, spilling incoming values if
 610     // we need to scavenge a register.
 611     //
 612     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 613       MachineOperand& MO = MI->getOperand(i);
 614       if (MO.isDef() && MO.isRegister() && MO.getReg() &&
 615           MRegisterInfo::isVirtualRegister(MO.getReg())) {
 616         unsigned DestVirtReg = MO.getReg();
 617         unsigned DestPhysReg;
 618
 619         // If DestVirtReg already has a value, use it.
 620         if (!(DestPhysReg = getVirt2PhysRegMapSlot(DestVirtReg)))
 621           DestPhysReg = getReg(MBB, MI, DestVirtReg);
 622         markVirtRegModified(DestVirtReg);
 623         MI->SetMachineOperandReg(i, DestPhysReg);  // Assign the output register
 624       }
 625     }
 626
 627     // If this instruction defines any registers that are immediately dead,
 628     // kill them now.
 629     //
 630     for (LiveVariables::killed_iterator KI = LV->dead_begin(MI),
 631            KE = LV->dead_end(MI); KI != KE; ++KI) {
 632       unsigned VirtReg = KI->second;
 633       unsigned PhysReg = VirtReg;
 634       if (MRegisterInfo::isVirtualRegister(VirtReg)) {
 635         unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg);
 636         PhysReg = PhysRegSlot;
 637         assert(PhysReg != 0);
 638         PhysRegSlot = 0;
 639       }
 640
 641       if (PhysReg) {
 642         DEBUG(std::cerr << "  Register " << RegInfo->getName(PhysReg)
 643               << " [%reg" << VirtReg
 644               << "] is never used, removing it frame live list\n");
 645         removePhysReg(PhysReg);
 646       }
 647     }
 648   }
 649
 650   MI = MBB.getFirstTerminator();
 651
 652   // Spill all physical registers holding virtual registers now.
 653   for (unsigned i = 0, e = RegInfo->getNumRegs(); i != e; ++i)
 654     if (PhysRegsUsed[i] != -1)
 655       if (unsigned VirtReg = PhysRegsUsed[i])
 656         spillVirtReg(MBB, MI, VirtReg, i);
 657       else
 658         removePhysReg(i);
 659
 660 #ifndef NDEBUG
 661   bool AllOk = true;
 662   for (unsigned i = MRegisterInfo::FirstVirtualRegister,
 663            e = MF->getSSARegMap()->getLastVirtReg(); i <= e; ++i)
 664     if (unsigned PR = Virt2PhysRegMap[i]) {
 665       std::cerr << "Register still mapped: " << i << " -> " << PR << "\n";
 666       AllOk = false;
 667     }
 668   assert(AllOk && "Virtual registers still in phys regs?");
 669 #endif
 670
 671   // Clear any physical register which appear live at the end of the basic
 672   // block, but which do not hold any virtual registers.  e.g., the stack
 673   // pointer.
 674   PhysRegsUseOrder.clear();
 675 }
 676
 677
 678 /// runOnMachineFunction - Register allocate the whole function
 679 ///
 680 bool RA::runOnMachineFunction(MachineFunction &Fn) {
 681   DEBUG(std::cerr << "Machine Function " << "\n");
 682   MF = &Fn;
 683   TM = &Fn.getTarget();
 684   RegInfo = TM->getRegisterInfo();
 685   LV = &getAnalysis<LiveVariables>();
 686
 687   PhysRegsUsed.assign(RegInfo->getNumRegs(), -1);
 688
 689   // initialize the virtual->physical register map to have a 'null'
 690   // mapping for all virtual registers
 691   Virt2PhysRegMap.grow(MF->getSSARegMap()->getLastVirtReg());
 692
 693   // Loop over all of the basic blocks, eliminating virtual register references
 694   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 695        MBB != MBBe; ++MBB)
 696     AllocateBasicBlock(*MBB);
 697
 698   StackSlotForVirtReg.clear();
 699   PhysRegsUsed.clear();
 700   VirtRegModified.clear();
 701   Virt2PhysRegMap.clear();
 702   return true;
 703 }
 704
 705 FunctionPass *llvm::createLocalRegisterAllocator() {
 706   return new RA();
 707 }