lib/CodeGen/RegAllocLocal.cpp

   1 //===-- RegAllocLocal.cpp - A BasicBlock generic register allocator -------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // 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/BasicBlock.h"
  17 #include "llvm/CodeGen/MachineFunctionPass.h"
  18 #include "llvm/CodeGen/MachineInstr.h"
  19 #include "llvm/CodeGen/MachineFrameInfo.h"
  20 #include "llvm/CodeGen/MachineRegisterInfo.h"
  21 #include "llvm/CodeGen/Passes.h"
  22 #include "llvm/CodeGen/RegAllocRegistry.h"
  23 #include "llvm/Target/TargetInstrInfo.h"
  24 #include "llvm/Target/TargetMachine.h"
  25 #include "llvm/Support/CommandLine.h"
  26 #include "llvm/Support/Debug.h"
  27 #include "llvm/Support/ErrorHandling.h"
  28 #include "llvm/Support/raw_ostream.h"
  29 #include "llvm/ADT/DenseMap.h"
  30 #include "llvm/ADT/IndexedMap.h"
  31 #include "llvm/ADT/SmallSet.h"
  32 #include "llvm/ADT/SmallVector.h"
  33 #include "llvm/ADT/Statistic.h"
  34 #include "llvm/ADT/STLExtras.h"
  35 #include <algorithm>
  36 using namespace llvm;
  37
  38 STATISTIC(NumStores, "Number of stores added");
  39 STATISTIC(NumLoads , "Number of loads added");
  40 STATISTIC(NumCopies, "Number of copies coalesced");
  41
  42 static RegisterRegAlloc
  43   localRegAlloc("local", "local register allocator",
  44                 createLocalRegisterAllocator);
  45
  46 namespace {
  47   class RALocal : public MachineFunctionPass {
  48   public:
  49     static char ID;
  50     RALocal() : MachineFunctionPass(&ID), StackSlotForVirtReg(-1) {}
  51   private:
  52     const TargetMachine *TM;
  53     MachineFunction *MF;
  54     MachineRegisterInfo *MRI;
  55     const TargetRegisterInfo *TRI;
  56     const TargetInstrInfo *TII;
  57
  58     // StackSlotForVirtReg - Maps virtual regs to the frame index where these
  59     // values are spilled.
  60     IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg;
  61
  62     // Virt2PhysRegMap - This map contains entries for each virtual register
  63     // that is currently available in a physical register.
  64     IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2PhysRegMap;
  65
  66     unsigned &getVirt2PhysRegMapSlot(unsigned VirtReg) {
  67       return Virt2PhysRegMap[VirtReg];
  68     }
  69
  70     // PhysRegsUsed - This array is effectively a map, containing entries for
  71     // each physical register that currently has a value (ie, it is in
  72     // Virt2PhysRegMap).  The value mapped to is the virtual register
  73     // corresponding to the physical register (the inverse of the
  74     // Virt2PhysRegMap), or 0.  The value is set to 0 if this register is pinned
  75     // because it is used by a future instruction, and to -2 if it is not
  76     // allocatable.  If the entry for a physical register is -1, then the
  77     // physical register is "not in the map".
  78     //
  79     std::vector<int> PhysRegsUsed;
  80
  81     // PhysRegsUseOrder - This contains a list of the physical registers that
  82     // currently have a virtual register value in them.  This list provides an
  83     // ordering of registers, imposing a reallocation order.  This list is only
  84     // used if all registers are allocated and we have to spill one, in which
  85     // case we spill the least recently used register.  Entries at the front of
  86     // the list are the least recently used registers, entries at the back are
  87     // the most recently used.
  88     //
  89     std::vector<unsigned> PhysRegsUseOrder;
  90
  91     // Virt2LastUseMap - This maps each virtual register to its last use
  92     // (MachineInstr*, operand index pair).
  93     IndexedMap<std::pair<MachineInstr*, unsigned>, VirtReg2IndexFunctor>
  94     Virt2LastUseMap;
  95
  96     std::pair<MachineInstr*,unsigned>& getVirtRegLastUse(unsigned Reg) {
  97       assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!");
  98       return Virt2LastUseMap[Reg];
  99     }
 100
 101     // VirtRegModified - This bitset contains information about which virtual
 102     // registers need to be spilled back to memory when their registers are
 103     // scavenged.  If a virtual register has simply been rematerialized, there
 104     // is no reason to spill it to memory when we need the register back.
 105     //
 106     BitVector VirtRegModified;
 107
 108     // UsedInMultipleBlocks - Tracks whether a particular register is used in
 109     // more than one block.
 110     BitVector UsedInMultipleBlocks;
 111
 112     void markVirtRegModified(unsigned Reg, bool Val = true) {
 113       assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!");
 114       Reg -= TargetRegisterInfo::FirstVirtualRegister;
 115       if (Val)
 116         VirtRegModified.set(Reg);
 117       else
 118         VirtRegModified.reset(Reg);
 119     }
 120
 121     bool isVirtRegModified(unsigned Reg) const {
 122       assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!");
 123       assert(Reg - TargetRegisterInfo::FirstVirtualRegister <
 124              VirtRegModified.size() && "Illegal virtual register!");
 125       return VirtRegModified[Reg - TargetRegisterInfo::FirstVirtualRegister];
 126     }
 127
 128     void AddToPhysRegsUseOrder(unsigned Reg) {
 129       std::vector<unsigned>::iterator It =
 130         std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), Reg);
 131       if (It != PhysRegsUseOrder.end())
 132         PhysRegsUseOrder.erase(It);
 133       PhysRegsUseOrder.push_back(Reg);
 134     }
 135
 136     void MarkPhysRegRecentlyUsed(unsigned Reg) {
 137       if (PhysRegsUseOrder.empty() ||
 138           PhysRegsUseOrder.back() == Reg) return;  // Already most recently used
 139
 140       for (unsigned i = PhysRegsUseOrder.size(); i != 0; --i) {
 141         unsigned RegMatch = PhysRegsUseOrder[i-1];       // remove from middle
 142         if (!areRegsEqual(Reg, RegMatch)) continue;
 143
 144         PhysRegsUseOrder.erase(PhysRegsUseOrder.begin()+i-1);
 145         // Add it to the end of the list
 146         PhysRegsUseOrder.push_back(RegMatch);
 147         if (RegMatch == Reg)
 148           return;    // Found an exact match, exit early
 149       }
 150     }
 151
 152   public:
 153     virtual const char *getPassName() const {
 154       return "Local Register Allocator";
 155     }
 156
 157     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 158       AU.setPreservesCFG();
 159       AU.addRequiredID(PHIEliminationID);
 160       AU.addRequiredID(TwoAddressInstructionPassID);
 161       MachineFunctionPass::getAnalysisUsage(AU);
 162     }
 163
 164   private:
 165     /// runOnMachineFunction - Register allocate the whole function
 166     bool runOnMachineFunction(MachineFunction &Fn);
 167
 168     /// AllocateBasicBlock - Register allocate the specified basic block.
 169     void AllocateBasicBlock(MachineBasicBlock &MBB);
 170
 171
 172     /// areRegsEqual - This method returns true if the specified registers are
 173     /// related to each other.  To do this, it checks to see if they are equal
 174     /// or if the first register is in the alias set of the second register.
 175     ///
 176     bool areRegsEqual(unsigned R1, unsigned R2) const {
 177       if (R1 == R2) return true;
 178       for (const unsigned *AliasSet = TRI->getAliasSet(R2);
 179            *AliasSet; ++AliasSet) {
 180         if (*AliasSet == R1) return true;
 181       }
 182       return false;
 183     }
 184
 185     /// getStackSpaceFor - This returns the frame index of the specified virtual
 186     /// register on the stack, allocating space if necessary.
 187     int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC);
 188
 189     /// removePhysReg - This method marks the specified physical register as no
 190     /// longer being in use.
 191     ///
 192     void removePhysReg(unsigned PhysReg);
 193
 194     void storeVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator I,
 195                       unsigned VirtReg, unsigned PhysReg, bool isKill);
 196
 197     /// spillVirtReg - This method spills the value specified by PhysReg into
 198     /// the virtual register slot specified by VirtReg.  It then updates the RA
 199     /// data structures to indicate the fact that PhysReg is now available.
 200     ///
 201     void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
 202                       unsigned VirtReg, unsigned PhysReg);
 203
 204     /// spillPhysReg - This method spills the specified physical register into
 205     /// the virtual register slot associated with it.  If OnlyVirtRegs is set to
 206     /// true, then the request is ignored if the physical register does not
 207     /// contain a virtual register.
 208     ///
 209     void spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I,
 210                       unsigned PhysReg, bool OnlyVirtRegs = false);
 211
 212     /// assignVirtToPhysReg - This method updates local state so that we know
 213     /// that PhysReg is the proper container for VirtReg now.  The physical
 214     /// register must not be used for anything else when this is called.
 215     ///
 216     void assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg);
 217
 218     /// isPhysRegAvailable - Return true if the specified physical register is
 219     /// free and available for use.  This also includes checking to see if
 220     /// aliased registers are all free...
 221     ///
 222     bool isPhysRegAvailable(unsigned PhysReg) const;
 223
 224     /// getFreeReg - Look to see if there is a free register available in the
 225     /// specified register class.  If not, return 0.
 226     ///
 227     unsigned getFreeReg(const TargetRegisterClass *RC);
 228
 229     /// getReg - Find a physical register to hold the specified virtual
 230     /// register.  If all compatible physical registers are used, this method
 231     /// spills the last used virtual register to the stack, and uses that
 232     /// register. If NoFree is true, that means the caller knows there isn't
 233     /// a free register, do not call getFreeReg().
 234     unsigned getReg(MachineBasicBlock &MBB, MachineInstr *MI,
 235                     unsigned VirtReg, bool NoFree = false);
 236
 237     /// reloadVirtReg - This method transforms the specified virtual
 238     /// register use to refer to a physical register.  This method may do this
 239     /// in one of several ways: if the register is available in a physical
 240     /// register already, it uses that physical register.  If the value is not
 241     /// in a physical register, and if there are physical registers available,
 242     /// it loads it into a register: PhysReg if that is an available physical
 243     /// register, otherwise any physical register of the right class.
 244     /// If register pressure is high, and it is possible, it tries to fold the
 245     /// load of the virtual register into the instruction itself.  It avoids
 246     /// doing this if register pressure is low to improve the chance that
 247     /// subsequent instructions can use the reloaded value.  This method
 248     /// returns the modified instruction.
 249     ///
 250     MachineInstr *reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
 251                                 unsigned OpNum, SmallSet<unsigned, 4> &RRegs,
 252                                 unsigned PhysReg);
 253
 254     /// ComputeLocalLiveness - Computes liveness of registers within a basic
 255     /// block, setting the killed/dead flags as appropriate.
 256     void ComputeLocalLiveness(MachineBasicBlock& MBB);
 257
 258     void reloadPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 259                        unsigned PhysReg);
 260   };
 261   char RALocal::ID = 0;
 262 }
 263
 264 /// getStackSpaceFor - This allocates space for the specified virtual register
 265 /// to be held on the stack.
 266 int RALocal::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) {
 267   // Find the location Reg would belong...
 268   int SS = StackSlotForVirtReg[VirtReg];
 269   if (SS != -1)
 270     return SS;          // Already has space allocated?
 271
 272   // Allocate a new stack object for this spill location...
 273   int FrameIdx = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(),
 274                                                             RC->getAlignment());
 275
 276   // Assign the slot.
 277   StackSlotForVirtReg[VirtReg] = FrameIdx;
 278   return FrameIdx;
 279 }
 280
 281
 282 /// removePhysReg - This method marks the specified physical register as no
 283 /// longer being in use.
 284 ///
 285 void RALocal::removePhysReg(unsigned PhysReg) {
 286   PhysRegsUsed[PhysReg] = -1;      // PhyReg no longer used
 287
 288   std::vector<unsigned>::iterator It =
 289     std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), PhysReg);
 290   if (It != PhysRegsUseOrder.end())
 291     PhysRegsUseOrder.erase(It);
 292 }
 293
 294 /// storeVirtReg - Store a virtual register to its assigned stack slot.
 295 void RALocal::storeVirtReg(MachineBasicBlock &MBB,
 296                            MachineBasicBlock::iterator I,
 297                            unsigned VirtReg, unsigned PhysReg,
 298                            bool isKill) {
 299   const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg);
 300   int FrameIndex = getStackSpaceFor(VirtReg, RC);
 301   DEBUG(dbgs() << " to stack slot #" << FrameIndex);
 302   TII->storeRegToStackSlot(MBB, I, PhysReg, isKill, FrameIndex, RC, TRI);
 303   ++NumStores;   // Update statistics
 304
 305   // Mark the spill instruction as last use if we're not killing the register.
 306   if (!isKill) {
 307     MachineInstr *Spill = llvm::prior(I);
 308     int OpNum = Spill->findRegisterUseOperandIdx(PhysReg);
 309     if (OpNum < 0)
 310       getVirtRegLastUse(VirtReg) = std::make_pair((MachineInstr*)0, 0);
 311     else
 312       getVirtRegLastUse(VirtReg) = std::make_pair(Spill, OpNum);
 313   }
 314 }
 315
 316 /// spillVirtReg - This method spills the value specified by PhysReg into the
 317 /// virtual register slot specified by VirtReg.  It then updates the RA data
 318 /// structures to indicate the fact that PhysReg is now available.
 319 ///
 320 void RALocal::spillVirtReg(MachineBasicBlock &MBB,
 321                            MachineBasicBlock::iterator I,
 322                            unsigned VirtReg, unsigned PhysReg) {
 323   assert(VirtReg && "Spilling a physical register is illegal!"
 324          " Must not have appropriate kill for the register or use exists beyond"
 325          " the intended one.");
 326   DEBUG(dbgs() << "  Spilling register " << TRI->getName(PhysReg)
 327                << " containing %reg" << VirtReg);
 328
 329   if (!isVirtRegModified(VirtReg)) {
 330     DEBUG(dbgs() << " which has not been modified, so no store necessary!");
 331     std::pair<MachineInstr*, unsigned> &LastUse = getVirtRegLastUse(VirtReg);
 332     if (LastUse.first)
 333       LastUse.first->getOperand(LastUse.second).setIsKill();
 334   } else {
 335     // Otherwise, there is a virtual register corresponding to this physical
 336     // register.  We only need to spill it into its stack slot if it has been
 337     // modified.
 338     // If the instruction reads the register that's spilled, (e.g. this can
 339     // happen if it is a move to a physical register), then the spill
 340     // instruction is not a kill.
 341     bool isKill = !(I != MBB.end() && I->readsRegister(PhysReg));
 342     storeVirtReg(MBB, I, VirtReg, PhysReg, isKill);
 343   }
 344
 345   getVirt2PhysRegMapSlot(VirtReg) = 0;   // VirtReg no longer available
 346
 347   DEBUG(dbgs() << '\n');
 348   removePhysReg(PhysReg);
 349 }
 350
 351
 352 /// spillPhysReg - This method spills the specified physical register into the
 353 /// virtual register slot associated with it.  If OnlyVirtRegs is set to true,
 354 /// then the request is ignored if the physical register does not contain a
 355 /// virtual register.
 356 ///
 357 void RALocal::spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I,
 358                            unsigned PhysReg, bool OnlyVirtRegs) {
 359   if (PhysRegsUsed[PhysReg] != -1) {            // Only spill it if it's used!
 360     assert(PhysRegsUsed[PhysReg] != -2 && "Non allocable reg used!");
 361     if (PhysRegsUsed[PhysReg] || !OnlyVirtRegs)
 362       spillVirtReg(MBB, I, PhysRegsUsed[PhysReg], PhysReg);
 363     return;
 364   }
 365
 366   // If the selected register aliases any other registers, we must make
 367   // sure that one of the aliases isn't alive.
 368   for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg);
 369        *AliasSet; ++AliasSet) {
 370     if (PhysRegsUsed[*AliasSet] == -1 ||     // Spill aliased register.
 371         PhysRegsUsed[*AliasSet] == -2)       // If allocatable.
 372       continue;
 373
 374     if (PhysRegsUsed[*AliasSet])
 375       spillVirtReg(MBB, I, PhysRegsUsed[*AliasSet], *AliasSet);
 376   }
 377 }
 378
 379
 380 /// assignVirtToPhysReg - This method updates local state so that we know
 381 /// that PhysReg is the proper container for VirtReg now.  The physical
 382 /// register must not be used for anything else when this is called.
 383 ///
 384 void RALocal::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) {
 385   assert(PhysRegsUsed[PhysReg] == -1 && "Phys reg already assigned!");
 386   // Update information to note the fact that this register was just used, and
 387   // it holds VirtReg.
 388   PhysRegsUsed[PhysReg] = VirtReg;
 389   getVirt2PhysRegMapSlot(VirtReg) = PhysReg;
 390   AddToPhysRegsUseOrder(PhysReg);   // New use of PhysReg
 391 }
 392
 393
 394 /// isPhysRegAvailable - Return true if the specified physical register is free
 395 /// and available for use.  This also includes checking to see if aliased
 396 /// registers are all free...
 397 ///
 398 bool RALocal::isPhysRegAvailable(unsigned PhysReg) const {
 399   if (PhysRegsUsed[PhysReg] != -1) return false;
 400
 401   // If the selected register aliases any other allocated registers, it is
 402   // not free!
 403   for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg);
 404        *AliasSet; ++AliasSet)
 405     if (PhysRegsUsed[*AliasSet] >= 0) // Aliased register in use?
 406       return false;                    // Can't use this reg then.
 407   return true;
 408 }
 409
 410
 411 /// getFreeReg - Look to see if there is a free register available in the
 412 /// specified register class.  If not, return 0.
 413 ///
 414 unsigned RALocal::getFreeReg(const TargetRegisterClass *RC) {
 415   // Get iterators defining the range of registers that are valid to allocate in
 416   // this class, which also specifies the preferred allocation order.
 417   TargetRegisterClass::iterator RI = RC->allocation_order_begin(*MF);
 418   TargetRegisterClass::iterator RE = RC->allocation_order_end(*MF);
 419
 420   for (; RI != RE; ++RI)
 421     if (isPhysRegAvailable(*RI)) {       // Is reg unused?
 422       assert(*RI != 0 && "Cannot use register!");
 423       return *RI; // Found an unused register!
 424     }
 425   return 0;
 426 }
 427
 428
 429 /// getReg - Find a physical register to hold the specified virtual
 430 /// register.  If all compatible physical registers are used, this method spills
 431 /// the last used virtual register to the stack, and uses that register.
 432 ///
 433 unsigned RALocal::getReg(MachineBasicBlock &MBB, MachineInstr *I,
 434                          unsigned VirtReg, bool NoFree) {
 435   const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg);
 436
 437   // First check to see if we have a free register of the requested type...
 438   unsigned PhysReg = NoFree ? 0 : getFreeReg(RC);
 439
 440   if (PhysReg != 0) {
 441     // Assign the register.
 442     assignVirtToPhysReg(VirtReg, PhysReg);
 443     return PhysReg;
 444   }
 445
 446   // If we didn't find an unused register, scavenge one now!
 447   assert(!PhysRegsUseOrder.empty() && "No allocated registers??");
 448
 449   // Loop over all of the preallocated registers from the least recently used
 450   // to the most recently used.  When we find one that is capable of holding
 451   // our register, use it.
 452   for (unsigned i = 0; PhysReg == 0; ++i) {
 453     assert(i != PhysRegsUseOrder.size() &&
 454            "Couldn't find a register of the appropriate class!");
 455
 456     unsigned R = PhysRegsUseOrder[i];
 457
 458     // We can only use this register if it holds a virtual register (ie, it
 459     // can be spilled).  Do not use it if it is an explicitly allocated
 460     // physical register!
 461     assert(PhysRegsUsed[R] != -1 &&
 462            "PhysReg in PhysRegsUseOrder, but is not allocated?");
 463     if (PhysRegsUsed[R] && PhysRegsUsed[R] != -2) {
 464       // If the current register is compatible, use it.
 465       if (RC->contains(R)) {
 466         PhysReg = R;
 467         break;
 468       }
 469
 470       // If one of the registers aliased to the current register is
 471       // compatible, use it.
 472       for (const unsigned *AliasIt = TRI->getAliasSet(R);
 473            *AliasIt; ++AliasIt) {
 474         if (!RC->contains(*AliasIt)) continue;
 475
 476         // If this is pinned down for some reason, don't use it.  For
 477         // example, if CL is pinned, and we run across CH, don't use
 478         // CH as justification for using scavenging ECX (which will
 479         // fail).
 480         if (PhysRegsUsed[*AliasIt] == 0) continue;
 481
 482         // Make sure the register is allocatable.  Don't allocate SIL on
 483         // x86-32.
 484         if (PhysRegsUsed[*AliasIt] == -2) continue;
 485
 486         PhysReg = *AliasIt;    // Take an aliased register
 487         break;
 488       }
 489     }
 490   }
 491
 492   assert(PhysReg && "Physical register not assigned!?!?");
 493
 494   // At this point PhysRegsUseOrder[i] is the least recently used register of
 495   // compatible register class.  Spill it to memory and reap its remains.
 496   spillPhysReg(MBB, I, PhysReg);
 497
 498   // Now that we know which register we need to assign this to, do it now!
 499   assignVirtToPhysReg(VirtReg, PhysReg);
 500   return PhysReg;
 501 }
 502
 503
 504 /// reloadVirtReg - This method transforms the specified virtual
 505 /// register use to refer to a physical register.  This method may do this in
 506 /// one of several ways: if the register is available in a physical register
 507 /// already, it uses that physical register.  If the value is not in a physical
 508 /// register, and if there are physical registers available, it loads it into a
 509 /// register: PhysReg if that is an available physical register, otherwise any
 510 /// register.  If register pressure is high, and it is possible, it tries to
 511 /// fold the load of the virtual register into the instruction itself.  It
 512 /// avoids doing this if register pressure is low to improve the chance that
 513 /// subsequent instructions can use the reloaded value.  This method returns
 514 /// the modified instruction.
 515 ///
 516 MachineInstr *RALocal::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
 517                                      unsigned OpNum,
 518                                      SmallSet<unsigned, 4> &ReloadedRegs,
 519                                      unsigned PhysReg) {
 520   unsigned VirtReg = MI->getOperand(OpNum).getReg();
 521   unsigned SubIdx = MI->getOperand(OpNum).getSubReg();
 522
 523   // If the virtual register is already available, just update the instruction
 524   // and return.
 525   if (unsigned PR = getVirt2PhysRegMapSlot(VirtReg)) {
 526     if (SubIdx) {
 527       PR = TRI->getSubReg(PR, SubIdx);
 528       MI->getOperand(OpNum).setSubReg(0);
 529     }
 530     MI->getOperand(OpNum).setReg(PR);  // Assign the input register
 531     if (!MI->isDebugValue()) {
 532       // Do not do these for DBG_VALUE as they can affect codegen.
 533       MarkPhysRegRecentlyUsed(PR);       // Already have this value available!
 534       getVirtRegLastUse(VirtReg) = std::make_pair(MI, OpNum);
 535     }
 536     return MI;
 537   }
 538
 539   // Otherwise, we need to fold it into the current instruction, or reload it.
 540   // If we have registers available to hold the value, use them.
 541   const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg);
 542   // If we already have a PhysReg (this happens when the instruction is a
 543   // reg-to-reg copy with a PhysReg destination) use that.
 544   if (!PhysReg || !TargetRegisterInfo::isPhysicalRegister(PhysReg) ||
 545       !isPhysRegAvailable(PhysReg))
 546     PhysReg = getFreeReg(RC);
 547   int FrameIndex = getStackSpaceFor(VirtReg, RC);
 548
 549   if (PhysReg) {   // Register is available, allocate it!
 550     assignVirtToPhysReg(VirtReg, PhysReg);
 551   } else {         // No registers available.
 552     // Force some poor hapless value out of the register file to
 553     // make room for the new register, and reload it.
 554     PhysReg = getReg(MBB, MI, VirtReg, true);
 555   }
 556
 557   markVirtRegModified(VirtReg, false);   // Note that this reg was just reloaded
 558
 559   DEBUG(dbgs() << "  Reloading %reg" << VirtReg << " into "
 560                << TRI->getName(PhysReg) << "\n");
 561
 562   // Add move instruction(s)
 563   TII->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC, TRI);
 564   ++NumLoads;    // Update statistics
 565
 566   MF->getRegInfo().setPhysRegUsed(PhysReg);
 567   // Assign the input register.
 568   if (SubIdx) {
 569     MI->getOperand(OpNum).setSubReg(0);
 570     MI->getOperand(OpNum).setReg(TRI->getSubReg(PhysReg, SubIdx));
 571   } else
 572     MI->getOperand(OpNum).setReg(PhysReg);  // Assign the input register
 573   getVirtRegLastUse(VirtReg) = std::make_pair(MI, OpNum);
 574
 575   if (!ReloadedRegs.insert(PhysReg)) {
 576     std::string msg;
 577     raw_string_ostream Msg(msg);
 578     Msg << "Ran out of registers during register allocation!";
 579     if (MI->isInlineAsm()) {
 580       Msg << "\nPlease check your inline asm statement for invalid "
 581            << "constraints:\n";
 582       MI->print(Msg, TM);
 583     }
 584     report_fatal_error(Msg.str());
 585   }
 586   for (const unsigned *SubRegs = TRI->getSubRegisters(PhysReg);
 587        *SubRegs; ++SubRegs) {
 588     if (ReloadedRegs.insert(*SubRegs)) continue;
 589
 590     std::string msg;
 591     raw_string_ostream Msg(msg);
 592     Msg << "Ran out of registers during register allocation!";
 593     if (MI->isInlineAsm()) {
 594       Msg << "\nPlease check your inline asm statement for invalid "
 595            << "constraints:\n";
 596       MI->print(Msg, TM);
 597     }
 598     report_fatal_error(Msg.str());
 599   }
 600
 601   return MI;
 602 }
 603
 604 /// isReadModWriteImplicitKill - True if this is an implicit kill for a
 605 /// read/mod/write register, i.e. update partial register.
 606 static bool isReadModWriteImplicitKill(MachineInstr *MI, unsigned Reg) {
 607   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 608     MachineOperand &MO = MI->getOperand(i);
 609     if (MO.isReg() && MO.getReg() == Reg && MO.isImplicit() &&
 610         MO.isDef() && !MO.isDead())
 611       return true;
 612   }
 613   return false;
 614 }
 615
 616 /// isReadModWriteImplicitDef - True if this is an implicit def for a
 617 /// read/mod/write register, i.e. update partial register.
 618 static bool isReadModWriteImplicitDef(MachineInstr *MI, unsigned Reg) {
 619   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 620     MachineOperand &MO = MI->getOperand(i);
 621     if (MO.isReg() && MO.getReg() == Reg && MO.isImplicit() &&
 622         !MO.isDef() && MO.isKill())
 623       return true;
 624   }
 625   return false;
 626 }
 627
 628 // precedes - Helper function to determine with MachineInstr A
 629 // precedes MachineInstr B within the same MBB.
 630 static bool precedes(MachineBasicBlock::iterator A,
 631                      MachineBasicBlock::iterator B) {
 632   if (A == B)
 633     return false;
 634
 635   MachineBasicBlock::iterator I = A->getParent()->begin();
 636   while (I != A->getParent()->end()) {
 637     if (I == A)
 638       return true;
 639     else if (I == B)
 640       return false;
 641
 642     ++I;
 643   }
 644
 645   return false;
 646 }
 647
 648 /// ComputeLocalLiveness - Computes liveness of registers within a basic
 649 /// block, setting the killed/dead flags as appropriate.
 650 void RALocal::ComputeLocalLiveness(MachineBasicBlock& MBB) {
 651   // Keep track of the most recently seen previous use or def of each reg,
 652   // so that we can update them with dead/kill markers.
 653   DenseMap<unsigned, std::pair<MachineInstr*, unsigned> > LastUseDef;
 654   for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end();
 655        I != E; ++I) {
 656     if (I->isDebugValue())
 657       continue;
 658
 659     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 660       MachineOperand &MO = I->getOperand(i);
 661       // Uses don't trigger any flags, but we need to save
 662       // them for later.  Also, we have to process these
 663       // _before_ processing the defs, since an instr
 664       // uses regs before it defs them.
 665       if (!MO.isReg() || !MO.getReg() || !MO.isUse())
 666         continue;
 667
 668       // Ignore helpful kill flags from earlier passes.
 669       MO.setIsKill(false);
 670
 671       LastUseDef[MO.getReg()] = std::make_pair(I, i);
 672
 673       if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) continue;
 674
 675       const unsigned *Aliases = TRI->getAliasSet(MO.getReg());
 676       if (Aliases == 0)
 677         continue;
 678
 679       while (*Aliases) {
 680         DenseMap<unsigned, std::pair<MachineInstr*, unsigned> >::iterator
 681           alias = LastUseDef.find(*Aliases);
 682
 683         if (alias != LastUseDef.end() && alias->second.first != I)
 684           LastUseDef[*Aliases] = std::make_pair(I, i);
 685
 686         ++Aliases;
 687       }
 688     }
 689
 690     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
 691       MachineOperand &MO = I->getOperand(i);
 692       // Defs others than 2-addr redefs _do_ trigger flag changes:
 693       //   - A def followed by a def is dead
 694       //   - A use followed by a def is a kill
 695       if (!MO.isReg() || !MO.getReg() || !MO.isDef()) continue;
 696
 697       unsigned SubIdx = MO.getSubReg();
 698       DenseMap<unsigned, std::pair<MachineInstr*, unsigned> >::iterator
 699         last = LastUseDef.find(MO.getReg());
 700       if (last != LastUseDef.end()) {
 701         // Check if this is a two address instruction.  If so, then
 702         // the def does not kill the use.
 703         if (last->second.first == I && I->isRegTiedToUseOperand(i))
 704           continue;
 705
 706         MachineOperand &lastUD =
 707                     last->second.first->getOperand(last->second.second);
 708         if (SubIdx && lastUD.getSubReg() != SubIdx)
 709           // Partial re-def, the last def is not dead.
 710           // %reg1024:5<def> =
 711           // %reg1024:6<def> =
 712           // or
 713           // %reg1024:5<def> = op %reg1024, 5
 714           continue;
 715
 716         if (lastUD.isDef())
 717           lastUD.setIsDead(true);
 718         else
 719           lastUD.setIsKill(true);
 720       }
 721
 722       LastUseDef[MO.getReg()] = std::make_pair(I, i);
 723     }
 724   }
 725
 726   // Live-out (of the function) registers contain return values of the function,
 727   // so we need to make sure they are alive at return time.
 728   MachineBasicBlock::iterator Ret = MBB.getFirstTerminator();
 729   bool BBEndsInReturn = (Ret != MBB.end() && Ret->getDesc().isReturn());
 730
 731   if (BBEndsInReturn)
 732     for (MachineRegisterInfo::liveout_iterator
 733          I = MF->getRegInfo().liveout_begin(),
 734          E = MF->getRegInfo().liveout_end(); I != E; ++I)
 735       if (!Ret->readsRegister(*I)) {
 736         Ret->addOperand(MachineOperand::CreateReg(*I, false, true));
 737         LastUseDef[*I] = std::make_pair(Ret, Ret->getNumOperands()-1);
 738       }
 739
 740   // Finally, loop over the final use/def of each reg
 741   // in the block and determine if it is dead.
 742   for (DenseMap<unsigned, std::pair<MachineInstr*, unsigned> >::iterator
 743        I = LastUseDef.begin(), E = LastUseDef.end(); I != E; ++I) {
 744     MachineInstr *MI = I->second.first;
 745     unsigned idx = I->second.second;
 746     MachineOperand &MO = MI->getOperand(idx);
 747
 748     bool isPhysReg = TargetRegisterInfo::isPhysicalRegister(MO.getReg());
 749
 750     // A crude approximation of "live-out" calculation
 751     bool usedOutsideBlock = isPhysReg ? false :
 752           UsedInMultipleBlocks.test(MO.getReg() -
 753                                     TargetRegisterInfo::FirstVirtualRegister);
 754
 755     // If the machine BB ends in a return instruction, then the value isn't used
 756     // outside of the BB.
 757     if (!isPhysReg && (!usedOutsideBlock || BBEndsInReturn)) {
 758       // DBG_VALUE complicates this:  if the only refs of a register outside
 759       // this block are DBG_VALUE, we can't keep the reg live just for that,
 760       // as it will cause the reg to be spilled at the end of this block when
 761       // it wouldn't have been otherwise.  Nullify the DBG_VALUEs when that
 762       // happens.
 763       bool UsedByDebugValueOnly = false;
 764       for (MachineRegisterInfo::reg_iterator UI = MRI->reg_begin(MO.getReg()),
 765              UE = MRI->reg_end(); UI != UE; ++UI) {
 766         // Two cases:
 767         // - used in another block
 768         // - used in the same block before it is defined (loop)
 769         if (UI->getParent() == &MBB &&
 770             !(MO.isDef() && UI.getOperand().isUse() && precedes(&*UI, MI)))
 771           continue;
 772
 773         if (UI->isDebugValue()) {
 774           UsedByDebugValueOnly = true;
 775           continue;
 776         }
 777
 778         // A non-DBG_VALUE use means we can leave DBG_VALUE uses alone.
 779         UsedInMultipleBlocks.set(MO.getReg() -
 780                                  TargetRegisterInfo::FirstVirtualRegister);
 781         usedOutsideBlock = true;
 782         UsedByDebugValueOnly = false;
 783         break;
 784       }
 785
 786       if (UsedByDebugValueOnly)
 787         for (MachineRegisterInfo::reg_iterator UI = MRI->reg_begin(MO.getReg()),
 788              UE = MRI->reg_end(); UI != UE; ++UI)
 789           if (UI->isDebugValue() &&
 790               (UI->getParent() != &MBB ||
 791                (MO.isDef() && precedes(&*UI, MI))))
 792             UI.getOperand().setReg(0U);
 793     }
 794
 795     // Physical registers and those that are not live-out of the block are
 796     // killed/dead at their last use/def within this block.
 797     if (isPhysReg || !usedOutsideBlock || BBEndsInReturn) {
 798       if (MO.isUse()) {
 799         // Don't mark uses that are tied to defs as kills.
 800         if (!MI->isRegTiedToDefOperand(idx))
 801           MO.setIsKill(true);
 802       } else {
 803         MO.setIsDead(true);
 804       }
 805     }
 806   }
 807 }
 808
 809 void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) {
 810   // loop over each instruction
 811   MachineBasicBlock::iterator MII = MBB.begin();
 812
 813   DEBUG({
 814       const BasicBlock *LBB = MBB.getBasicBlock();
 815       if (LBB)
 816         dbgs() << "\nStarting RegAlloc of BB: " << LBB->getName();
 817     });
 818
 819   // Add live-in registers as active.
 820   for (MachineBasicBlock::livein_iterator I = MBB.livein_begin(),
 821          E = MBB.livein_end(); I != E; ++I) {
 822     unsigned Reg = *I;
 823     MF->getRegInfo().setPhysRegUsed(Reg);
 824     PhysRegsUsed[Reg] = 0;            // It is free and reserved now
 825     AddToPhysRegsUseOrder(Reg);
 826     for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
 827          *SubRegs; ++SubRegs) {
 828       if (PhysRegsUsed[*SubRegs] == -2) continue;
 829
 830       AddToPhysRegsUseOrder(*SubRegs);
 831       PhysRegsUsed[*SubRegs] = 0;  // It is free and reserved now
 832       MF->getRegInfo().setPhysRegUsed(*SubRegs);
 833     }
 834   }
 835
 836   ComputeLocalLiveness(MBB);
 837
 838   // Otherwise, sequentially allocate each instruction in the MBB.
 839   while (MII != MBB.end()) {
 840     MachineInstr *MI = MII++;
 841     const TargetInstrDesc &TID = MI->getDesc();
 842     DEBUG({
 843         dbgs() << "\nStarting RegAlloc of: " << *MI;
 844         dbgs() << "  Regs have values: ";
 845         for (unsigned i = 0; i != TRI->getNumRegs(); ++i)
 846           if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) {
 847             if (PhysRegsUsed[i] && isVirtRegModified(PhysRegsUsed[i]))
 848               dbgs() << "*";
 849             dbgs() << "[" << TRI->getName(i)
 850                    << ",%reg" << PhysRegsUsed[i] << "] ";
 851           }
 852         dbgs() << '\n';
 853       });
 854
 855     // Determine whether this is a copy instruction.  The cases where the
 856     // source or destination are phys regs are handled specially.
 857     unsigned SrcCopyReg, DstCopyReg, SrcCopySubReg, DstCopySubReg;
 858     unsigned SrcCopyPhysReg = 0U;
 859     bool isCopy = TII->isMoveInstr(*MI, SrcCopyReg, DstCopyReg,
 860                                    SrcCopySubReg, DstCopySubReg) &&
 861       SrcCopySubReg == DstCopySubReg;
 862     if (isCopy && TargetRegisterInfo::isVirtualRegister(SrcCopyReg))
 863       SrcCopyPhysReg = getVirt2PhysRegMapSlot(SrcCopyReg);
 864
 865     // Loop over the implicit uses, making sure that they are at the head of the
 866     // use order list, so they don't get reallocated.
 867     if (TID.ImplicitUses) {
 868       for (const unsigned *ImplicitUses = TID.ImplicitUses;
 869            *ImplicitUses; ++ImplicitUses)
 870         MarkPhysRegRecentlyUsed(*ImplicitUses);
 871     }
 872
 873     SmallVector<unsigned, 8> Kills;
 874     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 875       MachineOperand &MO = MI->getOperand(i);
 876       if (!MO.isReg() || !MO.isKill()) continue;
 877
 878       if (!MO.isImplicit())
 879         Kills.push_back(MO.getReg());
 880       else if (!isReadModWriteImplicitKill(MI, MO.getReg()))
 881         // These are extra physical register kills when a sub-register
 882         // is defined (def of a sub-register is a read/mod/write of the
 883         // larger registers). Ignore.
 884         Kills.push_back(MO.getReg());
 885     }
 886
 887     // If any physical regs are earlyclobber, spill any value they might
 888     // have in them, then mark them unallocatable.
 889     // If any virtual regs are earlyclobber, allocate them now (before
 890     // freeing inputs that are killed).
 891     if (MI->isInlineAsm()) {
 892       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 893         MachineOperand &MO = MI->getOperand(i);
 894         if (!MO.isReg() || !MO.isDef() || !MO.isEarlyClobber() ||
 895             !MO.getReg())
 896           continue;
 897
 898         if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
 899           unsigned DestVirtReg = MO.getReg();
 900           unsigned DestPhysReg;
 901
 902           // If DestVirtReg already has a value, use it.
 903           if (!(DestPhysReg = getVirt2PhysRegMapSlot(DestVirtReg)))
 904             DestPhysReg = getReg(MBB, MI, DestVirtReg);
 905           MF->getRegInfo().setPhysRegUsed(DestPhysReg);
 906           markVirtRegModified(DestVirtReg);
 907           getVirtRegLastUse(DestVirtReg) =
 908                  std::make_pair((MachineInstr*)0, 0);
 909           DEBUG(dbgs() << "  Assigning " << TRI->getName(DestPhysReg)
 910                        << " to %reg" << DestVirtReg << "\n");
 911           if (unsigned DestSubIdx = MO.getSubReg()) {
 912             MO.setSubReg(0);
 913             DestPhysReg = TRI->getSubReg(DestPhysReg, DestSubIdx);
 914           }
 915           MO.setReg(DestPhysReg);  // Assign the earlyclobber register
 916         } else {
 917           unsigned Reg = MO.getReg();
 918           if (PhysRegsUsed[Reg] == -2) continue;  // Something like ESP.
 919           // These are extra physical register defs when a sub-register
 920           // is defined (def of a sub-register is a read/mod/write of the
 921           // larger registers). Ignore.
 922           if (isReadModWriteImplicitDef(MI, MO.getReg())) continue;
 923
 924           MF->getRegInfo().setPhysRegUsed(Reg);
 925           spillPhysReg(MBB, MI, Reg, true); // Spill any existing value in reg
 926           PhysRegsUsed[Reg] = 0;            // It is free and reserved now
 927           AddToPhysRegsUseOrder(Reg);
 928
 929           for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
 930                *SubRegs; ++SubRegs) {
 931             if (PhysRegsUsed[*SubRegs] == -2) continue;
 932             MF->getRegInfo().setPhysRegUsed(*SubRegs);
 933             PhysRegsUsed[*SubRegs] = 0;  // It is free and reserved now
 934             AddToPhysRegsUseOrder(*SubRegs);
 935           }
 936         }
 937       }
 938     }
 939
 940     // If a DBG_VALUE says something is located in a spilled register,
 941     // change the DBG_VALUE to be undef, which prevents the register
 942     // from being reloaded here.  Doing that would change the generated
 943     // code, unless another use immediately follows this instruction.
 944     if (MI->isDebugValue() &&
 945         MI->getNumOperands()==3 && MI->getOperand(0).isReg()) {
 946       unsigned VirtReg = MI->getOperand(0).getReg();
 947       if (VirtReg && TargetRegisterInfo::isVirtualRegister(VirtReg) &&
 948           !getVirt2PhysRegMapSlot(VirtReg))
 949         MI->getOperand(0).setReg(0U);
 950     }
 951
 952     // Get the used operands into registers.  This has the potential to spill
 953     // incoming values if we are out of registers.  Note that we completely
 954     // ignore physical register uses here.  We assume that if an explicit
 955     // physical register is referenced by the instruction, that it is guaranteed
 956     // to be live-in, or the input is badly hosed.
 957     //
 958     SmallSet<unsigned, 4> ReloadedRegs;
 959     for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
 960       MachineOperand &MO = MI->getOperand(i);
 961       // here we are looking for only used operands (never def&use)
 962       if (MO.isReg() && !MO.isDef() && MO.getReg() && !MO.isImplicit() &&
 963           TargetRegisterInfo::isVirtualRegister(MO.getReg()))
 964         MI = reloadVirtReg(MBB, MI, i, ReloadedRegs,
 965                            isCopy ? DstCopyReg : 0);
 966     }
 967
 968     // If this instruction is the last user of this register, kill the
 969     // value, freeing the register being used, so it doesn't need to be
 970     // spilled to memory.
 971     //
 972     for (unsigned i = 0, e = Kills.size(); i != e; ++i) {
 973       unsigned VirtReg = Kills[i];
 974       unsigned PhysReg = VirtReg;
 975       if (TargetRegisterInfo::isVirtualRegister(VirtReg)) {
 976         // If the virtual register was never materialized into a register, it
 977         // might not be in the map, but it won't hurt to zero it out anyway.
 978         unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg);
 979         PhysReg = PhysRegSlot;
 980         PhysRegSlot = 0;
 981       } else if (PhysRegsUsed[PhysReg] == -2) {
 982         // Unallocatable register dead, ignore.
 983         continue;
 984       } else {
 985         assert((!PhysRegsUsed[PhysReg] || PhysRegsUsed[PhysReg] == -1) &&
 986                "Silently clearing a virtual register?");
 987       }
 988
 989       if (!PhysReg) continue;
 990
 991       DEBUG(dbgs() << "  Last use of " << TRI->getName(PhysReg)
 992                    << "[%reg" << VirtReg <<"], removing it from live set\n");
 993       removePhysReg(PhysReg);
 994       for (const unsigned *SubRegs = TRI->getSubRegisters(PhysReg);
 995            *SubRegs; ++SubRegs) {
 996         if (PhysRegsUsed[*SubRegs] != -2) {
 997           DEBUG(dbgs()  << "  Last use of "
 998                         << TRI->getName(*SubRegs) << "[%reg" << VirtReg
 999                         <<"], removing it from live set\n");
1000           removePhysReg(*SubRegs);
1001         }
1002       }
1003     }
1004
1005     // Loop over all of the operands of the instruction, spilling registers that
1006     // are defined, and marking explicit destinations in the PhysRegsUsed map.
1007     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1008       MachineOperand &MO = MI->getOperand(i);
1009       if (!MO.isReg() || !MO.isDef() || MO.isImplicit() || !MO.getReg() ||
1010           MO.isEarlyClobber() ||
1011           !TargetRegisterInfo::isPhysicalRegister(MO.getReg()))
1012         continue;
1013
1014       unsigned Reg = MO.getReg();
1015       if (PhysRegsUsed[Reg] == -2) continue;  // Something like ESP.
1016       // These are extra physical register defs when a sub-register
1017       // is defined (def of a sub-register is a read/mod/write of the
1018       // larger registers). Ignore.
1019       if (isReadModWriteImplicitDef(MI, MO.getReg())) continue;
1020
1021       MF->getRegInfo().setPhysRegUsed(Reg);
1022       spillPhysReg(MBB, MI, Reg, true); // Spill any existing value in reg
1023       PhysRegsUsed[Reg] = 0;            // It is free and reserved now
1024       AddToPhysRegsUseOrder(Reg);
1025
1026       for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
1027            *SubRegs; ++SubRegs) {
1028         if (PhysRegsUsed[*SubRegs] == -2) continue;
1029
1030         MF->getRegInfo().setPhysRegUsed(*SubRegs);
1031         PhysRegsUsed[*SubRegs] = 0;  // It is free and reserved now
1032         AddToPhysRegsUseOrder(*SubRegs);
1033       }
1034     }
1035
1036     // Loop over the implicit defs, spilling them as well.
1037     if (TID.ImplicitDefs) {
1038       for (const unsigned *ImplicitDefs = TID.ImplicitDefs;
1039            *ImplicitDefs; ++ImplicitDefs) {
1040         unsigned Reg = *ImplicitDefs;
1041         if (PhysRegsUsed[Reg] != -2) {
1042           spillPhysReg(MBB, MI, Reg, true);
1043           AddToPhysRegsUseOrder(Reg);
1044           PhysRegsUsed[Reg] = 0;            // It is free and reserved now
1045         }
1046         MF->getRegInfo().setPhysRegUsed(Reg);
1047         for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
1048              *SubRegs; ++SubRegs) {
1049           if (PhysRegsUsed[*SubRegs] == -2) continue;
1050
1051           AddToPhysRegsUseOrder(*SubRegs);
1052           PhysRegsUsed[*SubRegs] = 0;  // It is free and reserved now
1053           MF->getRegInfo().setPhysRegUsed(*SubRegs);
1054         }
1055       }
1056     }
1057
1058     SmallVector<unsigned, 8> DeadDefs;
1059     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1060       MachineOperand &MO = MI->getOperand(i);
1061       if (MO.isReg() && MO.isDead())
1062         DeadDefs.push_back(MO.getReg());
1063     }
1064
1065     // Okay, we have allocated all of the source operands and spilled any values
1066     // that would be destroyed by defs of this instruction.  Loop over the
1067     // explicit defs and assign them to a register, spilling incoming values if
1068     // we need to scavenge a register.
1069     //
1070     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1071       MachineOperand &MO = MI->getOperand(i);
1072       if (!MO.isReg() || !MO.isDef() || !MO.getReg() ||
1073           MO.isEarlyClobber() ||
1074           !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
1075         continue;
1076
1077       unsigned DestVirtReg = MO.getReg();
1078       unsigned DestPhysReg;
1079
1080       // If DestVirtReg already has a value, use it.
1081       if (!(DestPhysReg = getVirt2PhysRegMapSlot(DestVirtReg))) {
1082         // If this is a copy try to reuse the input as the output;
1083         // that will make the copy go away.
1084         // If this is a copy, the source reg is a phys reg, and
1085         // that reg is available, use that phys reg for DestPhysReg.
1086         // If this is a copy, the source reg is a virtual reg, and
1087         // the phys reg that was assigned to that virtual reg is now
1088         // available, use that phys reg for DestPhysReg.  (If it's now
1089         // available that means this was the last use of the source.)
1090         if (isCopy &&
1091             TargetRegisterInfo::isPhysicalRegister(SrcCopyReg) &&
1092             isPhysRegAvailable(SrcCopyReg)) {
1093           DestPhysReg = SrcCopyReg;
1094           assignVirtToPhysReg(DestVirtReg, DestPhysReg);
1095         } else if (isCopy &&
1096             TargetRegisterInfo::isVirtualRegister(SrcCopyReg) &&
1097             SrcCopyPhysReg && isPhysRegAvailable(SrcCopyPhysReg) &&
1098             MF->getRegInfo().getRegClass(DestVirtReg)->
1099                              contains(SrcCopyPhysReg)) {
1100           DestPhysReg = SrcCopyPhysReg;
1101           assignVirtToPhysReg(DestVirtReg, DestPhysReg);
1102         } else
1103           DestPhysReg = getReg(MBB, MI, DestVirtReg);
1104       }
1105       MF->getRegInfo().setPhysRegUsed(DestPhysReg);
1106       markVirtRegModified(DestVirtReg);
1107       getVirtRegLastUse(DestVirtReg) = std::make_pair((MachineInstr*)0, 0);
1108       DEBUG(dbgs() << "  Assigning " << TRI->getName(DestPhysReg)
1109                    << " to %reg" << DestVirtReg << "\n");
1110
1111       if (unsigned DestSubIdx = MO.getSubReg()) {
1112         MO.setSubReg(0);
1113         DestPhysReg = TRI->getSubReg(DestPhysReg, DestSubIdx);
1114       }
1115       MO.setReg(DestPhysReg);  // Assign the output register
1116     }
1117
1118     // If this instruction defines any registers that are immediately dead,
1119     // kill them now.
1120     //
1121     for (unsigned i = 0, e = DeadDefs.size(); i != e; ++i) {
1122       unsigned VirtReg = DeadDefs[i];
1123       unsigned PhysReg = VirtReg;
1124       if (TargetRegisterInfo::isVirtualRegister(VirtReg)) {
1125         unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg);
1126         PhysReg = PhysRegSlot;
1127         assert(PhysReg != 0);
1128         PhysRegSlot = 0;
1129       } else if (PhysRegsUsed[PhysReg] == -2) {
1130         // Unallocatable register dead, ignore.
1131         continue;
1132       } else if (!PhysReg)
1133         continue;
1134
1135       DEBUG(dbgs()  << "  Register " << TRI->getName(PhysReg)
1136                     << " [%reg" << VirtReg
1137                     << "] is never used, removing it from live set\n");
1138       removePhysReg(PhysReg);
1139       for (const unsigned *AliasSet = TRI->getAliasSet(PhysReg);
1140            *AliasSet; ++AliasSet) {
1141         if (PhysRegsUsed[*AliasSet] != -2) {
1142           DEBUG(dbgs()  << "  Register " << TRI->getName(*AliasSet)
1143                         << " [%reg" << *AliasSet
1144                         << "] is never used, removing it from live set\n");
1145           removePhysReg(*AliasSet);
1146         }
1147       }
1148     }
1149
1150     // If this instruction is a call, make sure there are no dirty registers. The
1151     // call might throw an exception, and the landing pad expects to find all
1152     // registers in stack slots.
1153     if (TID.isCall())
1154       for (unsigned i = 0, e = TRI->getNumRegs(); i != e; ++i) {
1155         if (PhysRegsUsed[i] <= 0) continue;
1156         unsigned VirtReg = PhysRegsUsed[i];
1157         if (!isVirtRegModified(VirtReg)) continue;
1158         DEBUG(dbgs() << "  Storing dirty %reg" << VirtReg);
1159         storeVirtReg(MBB, MI, VirtReg, i, false);
1160         markVirtRegModified(VirtReg, false);
1161         DEBUG(dbgs() << " because the call might throw\n");
1162       }
1163
1164     // Finally, if this is a noop copy instruction, zap it.  (Except that if
1165     // the copy is dead, it must be kept to avoid messing up liveness info for
1166     // the register scavenger.  See pr4100.)
1167     if (TII->isMoveInstr(*MI, SrcCopyReg, DstCopyReg,
1168                          SrcCopySubReg, DstCopySubReg) &&
1169         SrcCopyReg == DstCopyReg && SrcCopySubReg == DstCopySubReg &&
1170         DeadDefs.empty()) {
1171       ++NumCopies;
1172       MBB.erase(MI);
1173     }
1174   }
1175
1176   MachineBasicBlock::iterator MI = MBB.getFirstTerminator();
1177
1178   // Spill all physical registers holding virtual registers now.
1179   for (unsigned i = 0, e = TRI->getNumRegs(); i != e; ++i)
1180     if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2) {
1181       if (unsigned VirtReg = PhysRegsUsed[i])
1182         spillVirtReg(MBB, MI, VirtReg, i);
1183       else
1184         removePhysReg(i);
1185     }
1186
1187 #if 0
1188   // This checking code is very expensive.
1189   bool AllOk = true;
1190   for (unsigned i = TargetRegisterInfo::FirstVirtualRegister,
1191            e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i)
1192     if (unsigned PR = Virt2PhysRegMap[i]) {
1193       cerr << "Register still mapped: " << i << " -> " << PR << "\n";
1194       AllOk = false;
1195     }
1196   assert(AllOk && "Virtual registers still in phys regs?");
1197 #endif
1198
1199   // Clear any physical register which appear live at the end of the basic
1200   // block, but which do not hold any virtual registers.  e.g., the stack
1201   // pointer.
1202   PhysRegsUseOrder.clear();
1203 }
1204
1205 /// runOnMachineFunction - Register allocate the whole function
1206 ///
1207 bool RALocal::runOnMachineFunction(MachineFunction &Fn) {
1208   DEBUG(dbgs() << "Machine Function\n");
1209   MF = &Fn;
1210   MRI = &Fn.getRegInfo();
1211   TM = &Fn.getTarget();
1212   TRI = TM->getRegisterInfo();
1213   TII = TM->getInstrInfo();
1214
1215   PhysRegsUsed.assign(TRI->getNumRegs(), -1);
1216
1217   // At various places we want to efficiently check to see whether a register
1218   // is allocatable.  To handle this, we mark all unallocatable registers as
1219   // being pinned down, permanently.
1220   {
1221     BitVector Allocable = TRI->getAllocatableSet(Fn);
1222     for (unsigned i = 0, e = Allocable.size(); i != e; ++i)
1223       if (!Allocable[i])
1224         PhysRegsUsed[i] = -2;  // Mark the reg unallocable.
1225   }
1226
1227   // initialize the virtual->physical register map to have a 'null'
1228   // mapping for all virtual registers
1229   unsigned LastVirtReg = MF->getRegInfo().getLastVirtReg();
1230   StackSlotForVirtReg.grow(LastVirtReg);
1231   Virt2PhysRegMap.grow(LastVirtReg);
1232   Virt2LastUseMap.grow(LastVirtReg);
1233   VirtRegModified.resize(LastVirtReg+1 -
1234                          TargetRegisterInfo::FirstVirtualRegister);
1235   UsedInMultipleBlocks.resize(LastVirtReg+1 -
1236                               TargetRegisterInfo::FirstVirtualRegister);
1237
1238   // Loop over all of the basic blocks, eliminating virtual register references
1239   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
1240        MBB != MBBe; ++MBB)
1241     AllocateBasicBlock(*MBB);
1242
1243   StackSlotForVirtReg.clear();
1244   PhysRegsUsed.clear();
1245   VirtRegModified.clear();
1246   UsedInMultipleBlocks.clear();
1247   Virt2PhysRegMap.clear();
1248   Virt2LastUseMap.clear();
1249   return true;
1250 }
1251
1252 FunctionPass *llvm::createLocalRegisterAllocator() {
1253   return new RALocal();
1254 }