lib/CodeGen/RegAllocLocal.cpp

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