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