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