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/LiveVariables.h"
  18 #include "llvm/CodeGen/MachineFunctionPass.h"
  19 #include "llvm/CodeGen/MachineInstr.h"
  20 #include "llvm/CodeGen/MachineFrameInfo.h"
  21 #include "llvm/CodeGen/MachineRegisterInfo.h"
  22 #include "llvm/CodeGen/Passes.h"
  23 #include "llvm/CodeGen/RegAllocRegistry.h"
  24 #include "llvm/Target/TargetInstrInfo.h"
  25 #include "llvm/Target/TargetMachine.h"
  26 #include "llvm/Support/CommandLine.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/Compiler.h"
  29 #include "llvm/ADT/IndexedMap.h"
  30 #include "llvm/ADT/SmallVector.h"
  31 #include "llvm/ADT/Statistic.h"
  32 #include "llvm/ADT/STLExtras.h"
  33 #include <algorithm>
  34 using namespace llvm;
  35
  36 STATISTIC(NumStores, "Number of stores added");
  37 STATISTIC(NumLoads , "Number of loads added");
  38
  39 namespace {
  40   static RegisterRegAlloc
  41     localRegAlloc("local", "  local register allocator",
  42                   createLocalRegisterAllocator);
  43
  44
  45   class VISIBILITY_HIDDEN RALocal : public MachineFunctionPass {
  46   public:
  47     static char ID;
  48     RALocal() : MachineFunctionPass((intptr_t)&ID) {}
  49   private:
  50     const TargetMachine *TM;
  51     MachineFunction *MF;
  52     const MRegisterInfo *MRI;
  53     const TargetInstrInfo *TII;
  54
  55     // StackSlotForVirtReg - Maps virtual regs to the frame index where these
  56     // values are spilled.
  57     std::map<unsigned, int> StackSlotForVirtReg;
  58
  59     // Virt2PhysRegMap - This map contains entries for each virtual register
  60     // that is currently available in a physical register.
  61     IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2PhysRegMap;
  62
  63     unsigned &getVirt2PhysRegMapSlot(unsigned VirtReg) {
  64       return Virt2PhysRegMap[VirtReg];
  65     }
  66
  67     // PhysRegsUsed - This array is effectively a map, containing entries for
  68     // each physical register that currently has a value (ie, it is in
  69     // Virt2PhysRegMap).  The value mapped to is the virtual register
  70     // corresponding to the physical register (the inverse of the
  71     // Virt2PhysRegMap), or 0.  The value is set to 0 if this register is pinned
  72     // because it is used by a future instruction, and to -2 if it is not
  73     // allocatable.  If the entry for a physical register is -1, then the
  74     // physical register is "not in the map".
  75     //
  76     std::vector<int> PhysRegsUsed;
  77
  78     // PhysRegsUseOrder - This contains a list of the physical registers that
  79     // currently have a virtual register value in them.  This list provides an
  80     // ordering of registers, imposing a reallocation order.  This list is only
  81     // used if all registers are allocated and we have to spill one, in which
  82     // case we spill the least recently used register.  Entries at the front of
  83     // the list are the least recently used registers, entries at the back are
  84     // the most recently used.
  85     //
  86     std::vector<unsigned> PhysRegsUseOrder;
  87
  88     // Virt2LastUseMap - This maps each virtual register to its last use
  89     // (MachineInstr*, operand index pair).
  90     IndexedMap<std::pair<MachineInstr*, unsigned>, VirtReg2IndexFunctor>
  91     Virt2LastUseMap;
  92
  93     std::pair<MachineInstr*,unsigned>& getVirtRegLastUse(unsigned Reg) {
  94       assert(MRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!");
  95       return Virt2LastUseMap[Reg];
  96     }
  97
  98     // VirtRegModified - This bitset contains information about which virtual
  99     // registers need to be spilled back to memory when their registers are
 100     // scavenged.  If a virtual register has simply been rematerialized, there
 101     // is no reason to spill it to memory when we need the register back.
 102     //
 103     BitVector VirtRegModified;
 104
 105     void markVirtRegModified(unsigned Reg, bool Val = true) {
 106       assert(MRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!");
 107       Reg -= MRegisterInfo::FirstVirtualRegister;
 108       if (Val)
 109         VirtRegModified.set(Reg);
 110       else
 111         VirtRegModified.reset(Reg);
 112     }
 113
 114     bool isVirtRegModified(unsigned Reg) const {
 115       assert(MRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!");
 116       assert(Reg - MRegisterInfo::FirstVirtualRegister < VirtRegModified.size()
 117              && "Illegal virtual register!");
 118       return VirtRegModified[Reg - MRegisterInfo::FirstVirtualRegister];
 119     }
 120
 121     void AddToPhysRegsUseOrder(unsigned Reg) {
 122       std::vector<unsigned>::iterator It =
 123         std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), Reg);
 124       if (It != PhysRegsUseOrder.end())
 125         PhysRegsUseOrder.erase(It);
 126       PhysRegsUseOrder.push_back(Reg);
 127     }
 128
 129     void MarkPhysRegRecentlyUsed(unsigned Reg) {
 130       if (PhysRegsUseOrder.empty() ||
 131           PhysRegsUseOrder.back() == Reg) return;  // Already most recently used
 132
 133       for (unsigned i = PhysRegsUseOrder.size(); i != 0; --i)
 134         if (areRegsEqual(Reg, PhysRegsUseOrder[i-1])) {
 135           unsigned RegMatch = PhysRegsUseOrder[i-1];       // remove from middle
 136           PhysRegsUseOrder.erase(PhysRegsUseOrder.begin()+i-1);
 137           // Add it to the end of the list
 138           PhysRegsUseOrder.push_back(RegMatch);
 139           if (RegMatch == Reg)
 140             return;    // Found an exact match, exit early
 141         }
 142     }
 143
 144   public:
 145     virtual const char *getPassName() const {
 146       return "Local Register Allocator";
 147     }
 148
 149     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 150       AU.addRequired<LiveVariables>();
 151       AU.addRequiredID(PHIEliminationID);
 152       AU.addRequiredID(TwoAddressInstructionPassID);
 153       MachineFunctionPass::getAnalysisUsage(AU);
 154     }
 155
 156   private:
 157     /// runOnMachineFunction - Register allocate the whole function
 158     bool runOnMachineFunction(MachineFunction &Fn);
 159
 160     /// AllocateBasicBlock - Register allocate the specified basic block.
 161     void AllocateBasicBlock(MachineBasicBlock &MBB);
 162
 163
 164     /// areRegsEqual - This method returns true if the specified registers are
 165     /// related to each other.  To do this, it checks to see if they are equal
 166     /// or if the first register is in the alias set of the second register.
 167     ///
 168     bool areRegsEqual(unsigned R1, unsigned R2) const {
 169       if (R1 == R2) return true;
 170       for (const unsigned *AliasSet = MRI->getAliasSet(R2);
 171            *AliasSet; ++AliasSet) {
 172         if (*AliasSet == R1) return true;
 173       }
 174       return false;
 175     }
 176
 177     /// getStackSpaceFor - This returns the frame index of the specified virtual
 178     /// register on the stack, allocating space if necessary.
 179     int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC);
 180
 181     /// removePhysReg - This method marks the specified physical register as no
 182     /// longer being in use.
 183     ///
 184     void removePhysReg(unsigned PhysReg);
 185
 186     /// spillVirtReg - This method spills the value specified by PhysReg into
 187     /// the virtual register slot specified by VirtReg.  It then updates the RA
 188     /// data structures to indicate the fact that PhysReg is now available.
 189     ///
 190     void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
 191                       unsigned VirtReg, unsigned PhysReg);
 192
 193     /// spillPhysReg - This method spills the specified physical register into
 194     /// the virtual register slot associated with it.  If OnlyVirtRegs is set to
 195     /// true, then the request is ignored if the physical register does not
 196     /// contain a virtual register.
 197     ///
 198     void spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I,
 199                       unsigned PhysReg, bool OnlyVirtRegs = false);
 200
 201     /// assignVirtToPhysReg - This method updates local state so that we know
 202     /// that PhysReg is the proper container for VirtReg now.  The physical
 203     /// register must not be used for anything else when this is called.
 204     ///
 205     void assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg);
 206
 207     /// isPhysRegAvailable - Return true if the specified physical register is
 208     /// free and available for use.  This also includes checking to see if
 209     /// aliased registers are all free...
 210     ///
 211     bool isPhysRegAvailable(unsigned PhysReg) const;
 212
 213     /// getFreeReg - Look to see if there is a free register available in the
 214     /// specified register class.  If not, return 0.
 215     ///
 216     unsigned getFreeReg(const TargetRegisterClass *RC);
 217
 218     /// getReg - Find a physical register to hold the specified virtual
 219     /// register.  If all compatible physical registers are used, this method
 220     /// spills the last used virtual register to the stack, and uses that
 221     /// register.
 222     ///
 223     unsigned getReg(MachineBasicBlock &MBB, MachineInstr *MI,
 224                     unsigned VirtReg);
 225
 226     /// reloadVirtReg - This method transforms the specified specified virtual
 227     /// register use to refer to a physical register.  This method may do this
 228     /// in one of several ways: if the register is available in a physical
 229     /// register already, it uses that physical register.  If the value is not
 230     /// in a physical register, and if there are physical registers available,
 231     /// it loads it into a register.  If register pressure is high, and it is
 232     /// possible, it tries to fold the load of the virtual register into the
 233     /// instruction itself.  It avoids doing this if register pressure is low to
 234     /// improve the chance that subsequent instructions can use the reloaded
 235     /// value.  This method returns the modified instruction.
 236     ///
 237     MachineInstr *reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
 238                                 unsigned OpNum);
 239
 240
 241     void reloadPhysReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator &I,
 242                        unsigned PhysReg);
 243   };
 244   char RALocal::ID = 0;
 245 }
 246
 247 /// getStackSpaceFor - This allocates space for the specified virtual register
 248 /// to be held on the stack.
 249 int RALocal::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) {
 250   // Find the location Reg would belong...
 251   std::map<unsigned, int>::iterator I =StackSlotForVirtReg.lower_bound(VirtReg);
 252
 253   if (I != StackSlotForVirtReg.end() && I->first == VirtReg)
 254     return I->second;          // Already has space allocated?
 255
 256   // Allocate a new stack object for this spill location...
 257   int FrameIdx = MF->getFrameInfo()->CreateStackObject(RC->getSize(),
 258                                                        RC->getAlignment());
 259
 260   // Assign the slot...
 261   StackSlotForVirtReg.insert(I, std::make_pair(VirtReg, FrameIdx));
 262   return FrameIdx;
 263 }
 264
 265
 266 /// removePhysReg - This method marks the specified physical register as no
 267 /// longer being in use.
 268 ///
 269 void RALocal::removePhysReg(unsigned PhysReg) {
 270   PhysRegsUsed[PhysReg] = -1;      // PhyReg no longer used
 271
 272   std::vector<unsigned>::iterator It =
 273     std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), PhysReg);
 274   if (It != PhysRegsUseOrder.end())
 275     PhysRegsUseOrder.erase(It);
 276 }
 277
 278
 279 /// spillVirtReg - This method spills the value specified by PhysReg into the
 280 /// virtual register slot specified by VirtReg.  It then updates the RA data
 281 /// structures to indicate the fact that PhysReg is now available.
 282 ///
 283 void RALocal::spillVirtReg(MachineBasicBlock &MBB,
 284                            MachineBasicBlock::iterator I,
 285                            unsigned VirtReg, unsigned PhysReg) {
 286   assert(VirtReg && "Spilling a physical register is illegal!"
 287          " Must not have appropriate kill for the register or use exists beyond"
 288          " the intended one.");
 289   DOUT << "  Spilling register " << MRI->getName(PhysReg)
 290        << " containing %reg" << VirtReg;
 291
 292   const TargetInstrInfo* TII = MBB.getParent()->getTarget().getInstrInfo();
 293
 294   if (!isVirtRegModified(VirtReg)) {
 295     DOUT << " which has not been modified, so no store necessary!";
 296     std::pair<MachineInstr*, unsigned> &LastUse = getVirtRegLastUse(VirtReg);
 297     if (LastUse.first)
 298       LastUse.first->getOperand(LastUse.second).setIsKill();
 299   } else {
 300     // Otherwise, there is a virtual register corresponding to this physical
 301     // register.  We only need to spill it into its stack slot if it has been
 302     // modified.
 303     const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg);
 304     int FrameIndex = getStackSpaceFor(VirtReg, RC);
 305     DOUT << " to stack slot #" << FrameIndex;
 306     TII->storeRegToStackSlot(MBB, I, PhysReg, true, FrameIndex, RC);
 307
 308     // If the instruction reads the register that's spilled, (e.g. this can
 309     // happen if it is a move to a physical register), then the spill
 310     // instruction is not a kill.
 311     if (I != MBB.end() && I->findRegisterUseOperandIdx(PhysReg) != -1) {
 312       MachineBasicBlock::iterator StoreMI = prior(I);
 313       int Idx = StoreMI->findRegisterUseOperandIdx(PhysReg, true);
 314       assert(Idx != -1 && "Unrecognized spill instruction!");
 315       StoreMI->getOperand(Idx).setIsKill(false);
 316     }
 317     ++NumStores;   // Update statistics
 318   }
 319
 320   getVirt2PhysRegMapSlot(VirtReg) = 0;   // VirtReg no longer available
 321
 322   DOUT << "\n";
 323   removePhysReg(PhysReg);
 324 }
 325
 326
 327 /// spillPhysReg - This method spills the specified physical register into the
 328 /// virtual register slot associated with it.  If OnlyVirtRegs is set to true,
 329 /// then the request is ignored if the physical register does not contain a
 330 /// virtual register.
 331 ///
 332 void RALocal::spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I,
 333                            unsigned PhysReg, bool OnlyVirtRegs) {
 334   if (PhysRegsUsed[PhysReg] != -1) {            // Only spill it if it's used!
 335     assert(PhysRegsUsed[PhysReg] != -2 && "Non allocable reg used!");
 336     if (PhysRegsUsed[PhysReg] || !OnlyVirtRegs)
 337       spillVirtReg(MBB, I, PhysRegsUsed[PhysReg], PhysReg);
 338   } else {
 339     // If the selected register aliases any other registers, we must make
 340     // sure that one of the aliases isn't alive.
 341     for (const unsigned *AliasSet = MRI->getAliasSet(PhysReg);
 342          *AliasSet; ++AliasSet)
 343       if (PhysRegsUsed[*AliasSet] != -1 &&     // Spill aliased register.
 344           PhysRegsUsed[*AliasSet] != -2)       // If allocatable.
 345           if (PhysRegsUsed[*AliasSet])
 346             spillVirtReg(MBB, I, PhysRegsUsed[*AliasSet], *AliasSet);
 347   }
 348 }
 349
 350
 351 /// assignVirtToPhysReg - This method updates local state so that we know
 352 /// that PhysReg is the proper container for VirtReg now.  The physical
 353 /// register must not be used for anything else when this is called.
 354 ///
 355 void RALocal::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) {
 356   assert(PhysRegsUsed[PhysReg] == -1 && "Phys reg already assigned!");
 357   // Update information to note the fact that this register was just used, and
 358   // it holds VirtReg.
 359   PhysRegsUsed[PhysReg] = VirtReg;
 360   getVirt2PhysRegMapSlot(VirtReg) = PhysReg;
 361   AddToPhysRegsUseOrder(PhysReg);   // New use of PhysReg
 362 }
 363
 364
 365 /// isPhysRegAvailable - Return true if the specified physical register is free
 366 /// and available for use.  This also includes checking to see if aliased
 367 /// registers are all free...
 368 ///
 369 bool RALocal::isPhysRegAvailable(unsigned PhysReg) const {
 370   if (PhysRegsUsed[PhysReg] != -1) return false;
 371
 372   // If the selected register aliases any other allocated registers, it is
 373   // not free!
 374   for (const unsigned *AliasSet = MRI->getAliasSet(PhysReg);
 375        *AliasSet; ++AliasSet)
 376     if (PhysRegsUsed[*AliasSet] != -1) // Aliased register in use?
 377       return false;                    // Can't use this reg then.
 378   return true;
 379 }
 380
 381
 382 /// getFreeReg - Look to see if there is a free register available in the
 383 /// specified register class.  If not, return 0.
 384 ///
 385 unsigned RALocal::getFreeReg(const TargetRegisterClass *RC) {
 386   // Get iterators defining the range of registers that are valid to allocate in
 387   // this class, which also specifies the preferred allocation order.
 388   TargetRegisterClass::iterator RI = RC->allocation_order_begin(*MF);
 389   TargetRegisterClass::iterator RE = RC->allocation_order_end(*MF);
 390
 391   for (; RI != RE; ++RI)
 392     if (isPhysRegAvailable(*RI)) {       // Is reg unused?
 393       assert(*RI != 0 && "Cannot use register!");
 394       return *RI; // Found an unused register!
 395     }
 396   return 0;
 397 }
 398
 399
 400 /// getReg - Find a physical register to hold the specified virtual
 401 /// register.  If all compatible physical registers are used, this method spills
 402 /// the last used virtual register to the stack, and uses that register.
 403 ///
 404 unsigned RALocal::getReg(MachineBasicBlock &MBB, MachineInstr *I,
 405                          unsigned VirtReg) {
 406   const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg);
 407
 408   // First check to see if we have a free register of the requested type...
 409   unsigned PhysReg = getFreeReg(RC);
 410
 411   // If we didn't find an unused register, scavenge one now!
 412   if (PhysReg == 0) {
 413     assert(!PhysRegsUseOrder.empty() && "No allocated registers??");
 414
 415     // Loop over all of the preallocated registers from the least recently used
 416     // to the most recently used.  When we find one that is capable of holding
 417     // our register, use it.
 418     for (unsigned i = 0; PhysReg == 0; ++i) {
 419       assert(i != PhysRegsUseOrder.size() &&
 420              "Couldn't find a register of the appropriate class!");
 421
 422       unsigned R = PhysRegsUseOrder[i];
 423
 424       // We can only use this register if it holds a virtual register (ie, it
 425       // can be spilled).  Do not use it if it is an explicitly allocated
 426       // physical register!
 427       assert(PhysRegsUsed[R] != -1 &&
 428              "PhysReg in PhysRegsUseOrder, but is not allocated?");
 429       if (PhysRegsUsed[R] && PhysRegsUsed[R] != -2) {
 430         // If the current register is compatible, use it.
 431         if (RC->contains(R)) {
 432           PhysReg = R;
 433           break;
 434         } else {
 435           // If one of the registers aliased to the current register is
 436           // compatible, use it.
 437           for (const unsigned *AliasIt = MRI->getAliasSet(R);
 438                *AliasIt; ++AliasIt) {
 439             if (RC->contains(*AliasIt) &&
 440                 // If this is pinned down for some reason, don't use it.  For
 441                 // example, if CL is pinned, and we run across CH, don't use
 442                 // CH as justification for using scavenging ECX (which will
 443                 // fail).
 444                 PhysRegsUsed[*AliasIt] != 0 &&
 445
 446                 // Make sure the register is allocatable.  Don't allocate SIL on
 447                 // x86-32.
 448                 PhysRegsUsed[*AliasIt] != -2) {
 449               PhysReg = *AliasIt;    // Take an aliased register
 450               break;
 451             }
 452           }
 453         }
 454       }
 455     }
 456
 457     assert(PhysReg && "Physical register not assigned!?!?");
 458
 459     // At this point PhysRegsUseOrder[i] is the least recently used register of
 460     // compatible register class.  Spill it to memory and reap its remains.
 461     spillPhysReg(MBB, I, PhysReg);
 462   }
 463
 464   // Now that we know which register we need to assign this to, do it now!
 465   assignVirtToPhysReg(VirtReg, PhysReg);
 466   return PhysReg;
 467 }
 468
 469
 470 /// reloadVirtReg - This method transforms the specified specified virtual
 471 /// register use to refer to a physical register.  This method may do this in
 472 /// one of several ways: if the register is available in a physical register
 473 /// already, it uses that physical register.  If the value is not in a physical
 474 /// register, and if there are physical registers available, it loads it into a
 475 /// register.  If register pressure is high, and it is possible, it tries to
 476 /// fold the load of the virtual register into the instruction itself.  It
 477 /// avoids doing this if register pressure is low to improve the chance that
 478 /// subsequent instructions can use the reloaded value.  This method returns the
 479 /// modified instruction.
 480 ///
 481 MachineInstr *RALocal::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
 482                                      unsigned OpNum) {
 483   unsigned VirtReg = MI->getOperand(OpNum).getReg();
 484
 485   // If the virtual register is already available, just update the instruction
 486   // and return.
 487   if (unsigned PR = getVirt2PhysRegMapSlot(VirtReg)) {
 488     MarkPhysRegRecentlyUsed(PR);          // Already have this value available!
 489     MI->getOperand(OpNum).setReg(PR);  // Assign the input register
 490     return MI;
 491   }
 492
 493   // Otherwise, we need to fold it into the current instruction, or reload it.
 494   // If we have registers available to hold the value, use them.
 495   const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg);
 496   unsigned PhysReg = getFreeReg(RC);
 497   int FrameIndex = getStackSpaceFor(VirtReg, RC);
 498
 499   if (PhysReg) {   // Register is available, allocate it!
 500     assignVirtToPhysReg(VirtReg, PhysReg);
 501   } else {         // No registers available.
 502     // Force some poor hapless value out of the register file to
 503     // make room for the new register, and reload it.
 504     PhysReg = getReg(MBB, MI, VirtReg);
 505   }
 506
 507   markVirtRegModified(VirtReg, false);   // Note that this reg was just reloaded
 508
 509   DOUT << "  Reloading %reg" << VirtReg << " into "
 510        << MRI->getName(PhysReg) << "\n";
 511
 512   // Add move instruction(s)
 513   const TargetInstrInfo* TII = MBB.getParent()->getTarget().getInstrInfo();
 514   TII->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC);
 515   ++NumLoads;    // Update statistics
 516
 517   MF->getRegInfo().setPhysRegUsed(PhysReg);
 518   MI->getOperand(OpNum).setReg(PhysReg);  // Assign the input register
 519   getVirtRegLastUse(VirtReg) = std::make_pair(MI, OpNum);
 520   return MI;
 521 }
 522
 523 /// isReadModWriteImplicitKill - True if this is an implicit kill for a
 524 /// read/mod/write register, i.e. update partial register.
 525 static bool isReadModWriteImplicitKill(MachineInstr *MI, unsigned Reg) {
 526   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 527     MachineOperand& MO = MI->getOperand(i);
 528     if (MO.isRegister() && MO.getReg() == Reg && MO.isImplicit() &&
 529         MO.isDef() && !MO.isDead())
 530       return true;
 531   }
 532   return false;
 533 }
 534
 535 /// isReadModWriteImplicitDef - True if this is an implicit def for a
 536 /// read/mod/write register, i.e. update partial register.
 537 static bool isReadModWriteImplicitDef(MachineInstr *MI, unsigned Reg) {
 538   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 539     MachineOperand& MO = MI->getOperand(i);
 540     if (MO.isRegister() && MO.getReg() == Reg && MO.isImplicit() &&
 541         !MO.isDef() && MO.isKill())
 542       return true;
 543   }
 544   return false;
 545 }
 546
 547 void RALocal::AllocateBasicBlock(MachineBasicBlock &MBB) {
 548   // loop over each instruction
 549   MachineBasicBlock::iterator MII = MBB.begin();
 550   const TargetInstrInfo &TII = *TM->getInstrInfo();
 551
 552   DEBUG(const BasicBlock *LBB = MBB.getBasicBlock();
 553         if (LBB) DOUT << "\nStarting RegAlloc of BB: " << LBB->getName());
 554
 555   // If this is the first basic block in the machine function, add live-in
 556   // registers as active.
 557   if (&MBB == &*MF->begin()) {
 558     for (MachineRegisterInfo::livein_iterator I=MF->getRegInfo().livein_begin(),
 559          E = MF->getRegInfo().livein_end(); I != E; ++I) {
 560       unsigned Reg = I->first;
 561       MF->getRegInfo().setPhysRegUsed(Reg);
 562       PhysRegsUsed[Reg] = 0;            // It is free and reserved now
 563       AddToPhysRegsUseOrder(Reg);
 564       for (const unsigned *AliasSet = MRI->getSubRegisters(Reg);
 565            *AliasSet; ++AliasSet) {
 566         if (PhysRegsUsed[*AliasSet] != -2) {
 567           AddToPhysRegsUseOrder(*AliasSet);
 568           PhysRegsUsed[*AliasSet] = 0;  // It is free and reserved now
 569           MF->getRegInfo().setPhysRegUsed(*AliasSet);
 570         }
 571       }
 572     }
 573   }
 574
 575   // Otherwise, sequentially allocate each instruction in the MBB.
 576   while (MII != MBB.end()) {
 577     MachineInstr *MI = MII++;
 578     const TargetInstrDesc &TID = MI->getDesc();
 579     DEBUG(DOUT << "\nStarting RegAlloc of: " << *MI;
 580           DOUT << "  Regs have values: ";
 581           for (unsigned i = 0; i != MRI->getNumRegs(); ++i)
 582             if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2)
 583                DOUT << "[" << MRI->getName(i)
 584                     << ",%reg" << PhysRegsUsed[i] << "] ";
 585           DOUT << "\n");
 586
 587     // Loop over the implicit uses, making sure that they are at the head of the
 588     // use order list, so they don't get reallocated.
 589     if (TID.ImplicitUses) {
 590       for (const unsigned *ImplicitUses = TID.ImplicitUses;
 591            *ImplicitUses; ++ImplicitUses)
 592         MarkPhysRegRecentlyUsed(*ImplicitUses);
 593     }
 594
 595     SmallVector<unsigned, 8> Kills;
 596     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 597       MachineOperand& MO = MI->getOperand(i);
 598       if (MO.isRegister() && MO.isKill()) {
 599         if (!MO.isImplicit())
 600           Kills.push_back(MO.getReg());
 601         else if (!isReadModWriteImplicitKill(MI, MO.getReg()))
 602           // These are extra physical register kills when a sub-register
 603           // is defined (def of a sub-register is a read/mod/write of the
 604           // larger registers). Ignore.
 605           Kills.push_back(MO.getReg());
 606       }
 607     }
 608
 609     // Get the used operands into registers.  This has the potential to spill
 610     // incoming values if we are out of registers.  Note that we completely
 611     // ignore physical register uses here.  We assume that if an explicit
 612     // physical register is referenced by the instruction, that it is guaranteed
 613     // to be live-in, or the input is badly hosed.
 614     //
 615     for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
 616       MachineOperand& MO = MI->getOperand(i);
 617       // here we are looking for only used operands (never def&use)
 618       if (MO.isRegister() && !MO.isDef() && MO.getReg() && !MO.isImplicit() &&
 619           MRegisterInfo::isVirtualRegister(MO.getReg()))
 620         MI = reloadVirtReg(MBB, MI, i);
 621     }
 622
 623     // If this instruction is the last user of this register, kill the
 624     // value, freeing the register being used, so it doesn't need to be
 625     // spilled to memory.
 626     //
 627     for (unsigned i = 0, e = Kills.size(); i != e; ++i) {
 628       unsigned VirtReg = Kills[i];
 629       unsigned PhysReg = VirtReg;
 630       if (MRegisterInfo::isVirtualRegister(VirtReg)) {
 631         // If the virtual register was never materialized into a register, it
 632         // might not be in the map, but it won't hurt to zero it out anyway.
 633         unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg);
 634         PhysReg = PhysRegSlot;
 635         PhysRegSlot = 0;
 636       } else if (PhysRegsUsed[PhysReg] == -2) {
 637         // Unallocatable register dead, ignore.
 638         continue;
 639       } else {
 640         assert((!PhysRegsUsed[PhysReg] || PhysRegsUsed[PhysReg] == -1) &&
 641                "Silently clearing a virtual register?");
 642       }
 643
 644       if (PhysReg) {
 645         DOUT << "  Last use of " << MRI->getName(PhysReg)
 646              << "[%reg" << VirtReg <<"], removing it from live set\n";
 647         removePhysReg(PhysReg);
 648         for (const unsigned *AliasSet = MRI->getSubRegisters(PhysReg);
 649              *AliasSet; ++AliasSet) {
 650           if (PhysRegsUsed[*AliasSet] != -2) {
 651             DOUT  << "  Last use of "
 652                   << MRI->getName(*AliasSet)
 653                   << "[%reg" << VirtReg <<"], removing it from live set\n";
 654             removePhysReg(*AliasSet);
 655           }
 656         }
 657       }
 658     }
 659
 660     // Loop over all of the operands of the instruction, spilling registers that
 661     // are defined, and marking explicit destinations in the PhysRegsUsed map.
 662     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 663       MachineOperand& MO = MI->getOperand(i);
 664       if (MO.isRegister() && MO.isDef() && !MO.isImplicit() && MO.getReg() &&
 665           MRegisterInfo::isPhysicalRegister(MO.getReg())) {
 666         unsigned Reg = MO.getReg();
 667         if (PhysRegsUsed[Reg] == -2) continue;  // Something like ESP.
 668         // These are extra physical register defs when a sub-register
 669         // is defined (def of a sub-register is a read/mod/write of the
 670         // larger registers). Ignore.
 671         if (isReadModWriteImplicitDef(MI, MO.getReg())) continue;
 672
 673         MF->getRegInfo().setPhysRegUsed(Reg);
 674         spillPhysReg(MBB, MI, Reg, true); // Spill any existing value in reg
 675         PhysRegsUsed[Reg] = 0;            // It is free and reserved now
 676         AddToPhysRegsUseOrder(Reg);
 677
 678         for (const unsigned *AliasSet = MRI->getSubRegisters(Reg);
 679              *AliasSet; ++AliasSet) {
 680           if (PhysRegsUsed[*AliasSet] != -2) {
 681             MF->getRegInfo().setPhysRegUsed(*AliasSet);
 682             PhysRegsUsed[*AliasSet] = 0;  // It is free and reserved now
 683             AddToPhysRegsUseOrder(*AliasSet);
 684           }
 685         }
 686       }
 687     }
 688
 689     // Loop over the implicit defs, spilling them as well.
 690     if (TID.ImplicitDefs) {
 691       for (const unsigned *ImplicitDefs = TID.ImplicitDefs;
 692            *ImplicitDefs; ++ImplicitDefs) {
 693         unsigned Reg = *ImplicitDefs;
 694         if (PhysRegsUsed[Reg] != -2) {
 695           spillPhysReg(MBB, MI, Reg, true);
 696           AddToPhysRegsUseOrder(Reg);
 697           PhysRegsUsed[Reg] = 0;            // It is free and reserved now
 698         }
 699         MF->getRegInfo().setPhysRegUsed(Reg);
 700         for (const unsigned *AliasSet = MRI->getSubRegisters(Reg);
 701              *AliasSet; ++AliasSet) {
 702           if (PhysRegsUsed[*AliasSet] != -2) {
 703             AddToPhysRegsUseOrder(*AliasSet);
 704             PhysRegsUsed[*AliasSet] = 0;  // It is free and reserved now
 705             MF->getRegInfo().setPhysRegUsed(*AliasSet);
 706           }
 707         }
 708       }
 709     }
 710
 711     SmallVector<unsigned, 8> DeadDefs;
 712     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 713       MachineOperand& MO = MI->getOperand(i);
 714       if (MO.isRegister() && MO.isDead())
 715         DeadDefs.push_back(MO.getReg());
 716     }
 717
 718     // Okay, we have allocated all of the source operands and spilled any values
 719     // that would be destroyed by defs of this instruction.  Loop over the
 720     // explicit defs and assign them to a register, spilling incoming values if
 721     // we need to scavenge a register.
 722     //
 723     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 724       MachineOperand& MO = MI->getOperand(i);
 725       if (MO.isRegister() && MO.isDef() && MO.getReg() &&
 726           MRegisterInfo::isVirtualRegister(MO.getReg())) {
 727         unsigned DestVirtReg = MO.getReg();
 728         unsigned DestPhysReg;
 729
 730         // If DestVirtReg already has a value, use it.
 731         if (!(DestPhysReg = getVirt2PhysRegMapSlot(DestVirtReg)))
 732           DestPhysReg = getReg(MBB, MI, DestVirtReg);
 733         MF->getRegInfo().setPhysRegUsed(DestPhysReg);
 734         markVirtRegModified(DestVirtReg);
 735         getVirtRegLastUse(DestVirtReg) = std::make_pair((MachineInstr*)0, 0);
 736         MI->getOperand(i).setReg(DestPhysReg);  // Assign the output register
 737       }
 738     }
 739
 740     // If this instruction defines any registers that are immediately dead,
 741     // kill them now.
 742     //
 743     for (unsigned i = 0, e = DeadDefs.size(); i != e; ++i) {
 744       unsigned VirtReg = DeadDefs[i];
 745       unsigned PhysReg = VirtReg;
 746       if (MRegisterInfo::isVirtualRegister(VirtReg)) {
 747         unsigned &PhysRegSlot = getVirt2PhysRegMapSlot(VirtReg);
 748         PhysReg = PhysRegSlot;
 749         assert(PhysReg != 0);
 750         PhysRegSlot = 0;
 751       } else if (PhysRegsUsed[PhysReg] == -2) {
 752         // Unallocatable register dead, ignore.
 753         continue;
 754       }
 755
 756       if (PhysReg) {
 757         DOUT  << "  Register " << MRI->getName(PhysReg)
 758               << " [%reg" << VirtReg
 759               << "] is never used, removing it frame live list\n";
 760         removePhysReg(PhysReg);
 761         for (const unsigned *AliasSet = MRI->getAliasSet(PhysReg);
 762              *AliasSet; ++AliasSet) {
 763           if (PhysRegsUsed[*AliasSet] != -2) {
 764             DOUT  << "  Register " << MRI->getName(*AliasSet)
 765                   << " [%reg" << *AliasSet
 766                   << "] is never used, removing it frame live list\n";
 767             removePhysReg(*AliasSet);
 768           }
 769         }
 770       }
 771     }
 772
 773     // Finally, if this is a noop copy instruction, zap it.
 774     unsigned SrcReg, DstReg;
 775     if (TII.isMoveInstr(*MI, SrcReg, DstReg) && SrcReg == DstReg)
 776       MBB.erase(MI);
 777   }
 778
 779   MachineBasicBlock::iterator MI = MBB.getFirstTerminator();
 780
 781   // Spill all physical registers holding virtual registers now.
 782   for (unsigned i = 0, e = MRI->getNumRegs(); i != e; ++i)
 783     if (PhysRegsUsed[i] != -1 && PhysRegsUsed[i] != -2)
 784       if (unsigned VirtReg = PhysRegsUsed[i])
 785         spillVirtReg(MBB, MI, VirtReg, i);
 786       else
 787         removePhysReg(i);
 788
 789 #if 0
 790   // This checking code is very expensive.
 791   bool AllOk = true;
 792   for (unsigned i = MRegisterInfo::FirstVirtualRegister,
 793            e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i)
 794     if (unsigned PR = Virt2PhysRegMap[i]) {
 795       cerr << "Register still mapped: " << i << " -> " << PR << "\n";
 796       AllOk = false;
 797     }
 798   assert(AllOk && "Virtual registers still in phys regs?");
 799 #endif
 800
 801   // Clear any physical register which appear live at the end of the basic
 802   // block, but which do not hold any virtual registers.  e.g., the stack
 803   // pointer.
 804   PhysRegsUseOrder.clear();
 805 }
 806
 807
 808 /// runOnMachineFunction - Register allocate the whole function
 809 ///
 810 bool RALocal::runOnMachineFunction(MachineFunction &Fn) {
 811   DOUT << "Machine Function " << "\n";
 812   MF = &Fn;
 813   TM = &Fn.getTarget();
 814   MRI = TM->getRegisterInfo();
 815   TII = TM->getInstrInfo();
 816
 817   PhysRegsUsed.assign(MRI->getNumRegs(), -1);
 818
 819   // At various places we want to efficiently check to see whether a register
 820   // is allocatable.  To handle this, we mark all unallocatable registers as
 821   // being pinned down, permanently.
 822   {
 823     BitVector Allocable = MRI->getAllocatableSet(Fn);
 824     for (unsigned i = 0, e = Allocable.size(); i != e; ++i)
 825       if (!Allocable[i])
 826         PhysRegsUsed[i] = -2;  // Mark the reg unallocable.
 827   }
 828
 829   // initialize the virtual->physical register map to have a 'null'
 830   // mapping for all virtual registers
 831   unsigned LastVirtReg = MF->getRegInfo().getLastVirtReg();
 832   Virt2PhysRegMap.grow(LastVirtReg);
 833   Virt2LastUseMap.grow(LastVirtReg);
 834   VirtRegModified.resize(LastVirtReg+1-MRegisterInfo::FirstVirtualRegister);
 835
 836   // Loop over all of the basic blocks, eliminating virtual register references
 837   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 838        MBB != MBBe; ++MBB)
 839     AllocateBasicBlock(*MBB);
 840
 841   StackSlotForVirtReg.clear();
 842   PhysRegsUsed.clear();
 843   VirtRegModified.clear();
 844   Virt2PhysRegMap.clear();
 845   Virt2LastUseMap.clear();
 846   return true;
 847 }
 848
 849 FunctionPass *llvm::createLocalRegisterAllocator() {
 850   return new RALocal();
 851 }