lib/CodeGen/RegAllocFast.cpp

   1 //===-- RegAllocFast.cpp - A fast register allocator for debug code -------===//
   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
  41 static RegisterRegAlloc
  42   fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator);
  43
  44 namespace {
  45   class RAFast : public MachineFunctionPass {
  46   public:
  47     static char ID;
  48     RAFast() : MachineFunctionPass(&ID), StackSlotForVirtReg(-1) {}
  49   private:
  50     const TargetMachine *TM;
  51     MachineFunction *MF;
  52     MachineRegisterInfo *MRI;
  53     const TargetRegisterInfo *TRI;
  54     const TargetInstrInfo *TII;
  55
  56     // StackSlotForVirtReg - Maps virtual regs to the frame index where these
  57     // values are spilled.
  58     IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg;
  59
  60     // Everything we know about a live virtual register.
  61     struct LiveReg {
  62       MachineInstr *LastUse;    // Last instr to use reg.
  63       unsigned PhysReg;         // Currently held here.
  64       unsigned short LastOpNum; // OpNum on LastUse.
  65       bool Dirty;               // Register needs spill.
  66
  67       LiveReg(unsigned p=0) : LastUse(0), PhysReg(p), LastOpNum(0),
  68                               Dirty(false) {
  69         assert(p && "Don't create LiveRegs without a PhysReg");
  70       }
  71     };
  72
  73     typedef DenseMap<unsigned, LiveReg> LiveRegMap;
  74
  75     // LiveVirtRegs - This map contains entries for each virtual register
  76     // that is currently available in a physical register.
  77     LiveRegMap LiveVirtRegs;
  78
  79     // RegState - Track the state of a physical register.
  80     enum RegState {
  81       // A disabled register is not available for allocation, but an alias may
  82       // be in use. A register can only be moved out of the disabled state if
  83       // all aliases are disabled.
  84       regDisabled,
  85
  86       // A free register is not currently in use and can be allocated
  87       // immediately without checking aliases.
  88       regFree,
  89
  90       // A reserved register has been assigned expolicitly (e.g., setting up a
  91       // call parameter), and it remains reserved until it is used.
  92       regReserved
  93
  94       // A register state may also be a virtual register number, indication that
  95       // the physical register is currently allocated to a virtual register. In
  96       // that case, LiveVirtRegs contains the inverse mapping.
  97     };
  98
  99     // PhysRegState - One of the RegState enums, or a virtreg.
 100     std::vector<unsigned> PhysRegState;
 101
 102     // UsedInInstr - BitVector of physregs that are used in the current
 103     // instruction, and so cannot be allocated.
 104     BitVector UsedInInstr;
 105
 106     // ReservedRegs - vector of reserved physical registers.
 107     BitVector ReservedRegs;
 108
 109   public:
 110     virtual const char *getPassName() const {
 111       return "Fast Register Allocator";
 112     }
 113
 114     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 115       AU.setPreservesCFG();
 116       AU.addRequiredID(PHIEliminationID);
 117       AU.addRequiredID(TwoAddressInstructionPassID);
 118       MachineFunctionPass::getAnalysisUsage(AU);
 119     }
 120
 121   private:
 122     bool runOnMachineFunction(MachineFunction &Fn);
 123     void AllocateBasicBlock(MachineBasicBlock &MBB);
 124     int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC);
 125     void addKillFlag(LiveRegMap::iterator i);
 126     void killVirtReg(LiveRegMap::iterator i);
 127     void killVirtReg(unsigned VirtReg);
 128     void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
 129                       unsigned VirtReg, bool isKill);
 130     void killPhysReg(unsigned PhysReg);
 131     void spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I,
 132                       unsigned PhysReg, bool isKill);
 133     LiveRegMap::iterator assignVirtToPhysReg(unsigned VirtReg,
 134                                              unsigned PhysReg);
 135     LiveRegMap::iterator allocVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
 136                                       unsigned VirtReg, unsigned Hint);
 137     unsigned defineVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
 138                            unsigned OpNum, unsigned VirtReg, unsigned Hint);
 139     unsigned reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
 140                            unsigned OpNum, unsigned VirtReg, unsigned Hint);
 141     void reservePhysReg(MachineBasicBlock &MBB, MachineInstr *MI,
 142                         unsigned PhysReg);
 143     void spillAll(MachineBasicBlock &MBB, MachineInstr *MI);
 144     void setPhysReg(MachineOperand &MO, unsigned PhysReg);
 145   };
 146   char RAFast::ID = 0;
 147 }
 148
 149 /// getStackSpaceFor - This allocates space for the specified virtual register
 150 /// to be held on the stack.
 151 int RAFast::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) {
 152   // Find the location Reg would belong...
 153   int SS = StackSlotForVirtReg[VirtReg];
 154   if (SS != -1)
 155     return SS;          // Already has space allocated?
 156
 157   // Allocate a new stack object for this spill location...
 158   int FrameIdx = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(),
 159                                                             RC->getAlignment());
 160
 161   // Assign the slot.
 162   StackSlotForVirtReg[VirtReg] = FrameIdx;
 163   return FrameIdx;
 164 }
 165
 166 /// addKillFlag - Set kill flags on last use of a virtual register.
 167 void RAFast::addKillFlag(LiveRegMap::iterator lri) {
 168   assert(lri != LiveVirtRegs.end() && "Killing unmapped virtual register");
 169   const LiveReg &LR = lri->second;
 170   if (LR.LastUse) {
 171     MachineOperand &MO = LR.LastUse->getOperand(LR.LastOpNum);
 172     if (MO.isDef())
 173       MO.setIsDead();
 174     else if (!LR.LastUse->isRegTiedToDefOperand(LR.LastOpNum))
 175       MO.setIsKill();
 176   }
 177 }
 178
 179 /// killVirtReg - Mark virtreg as no longer available.
 180 void RAFast::killVirtReg(LiveRegMap::iterator lri) {
 181   addKillFlag(lri);
 182   const LiveReg &LR = lri->second;
 183   assert(PhysRegState[LR.PhysReg] == lri->first && "Broken RegState mapping");
 184   PhysRegState[LR.PhysReg] = regFree;
 185   LiveVirtRegs.erase(lri);
 186 }
 187
 188 /// killVirtReg - Mark virtreg as no longer available.
 189 void RAFast::killVirtReg(unsigned VirtReg) {
 190   assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
 191          "killVirtReg needs a virtual register");
 192   LiveRegMap::iterator lri = LiveVirtRegs.find(VirtReg);
 193   if (lri != LiveVirtRegs.end())
 194     killVirtReg(lri);
 195 }
 196
 197 /// spillVirtReg - This method spills the value specified by VirtReg into the
 198 /// corresponding stack slot if needed. If isKill is set, the register is also
 199 /// killed.
 200 void RAFast::spillVirtReg(MachineBasicBlock &MBB,
 201                           MachineBasicBlock::iterator MI,
 202                           unsigned VirtReg, bool isKill) {
 203   assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
 204          "Spilling a physical register is illegal!");
 205   LiveRegMap::iterator lri = LiveVirtRegs.find(VirtReg);
 206   assert(lri != LiveVirtRegs.end() && "Spilling unmapped virtual register");
 207   LiveReg &LR = lri->second;
 208   assert(PhysRegState[LR.PhysReg] == VirtReg && "Broken RegState mapping");
 209
 210   // If this physreg is used by the instruction, we want to kill it on the
 211   // instruction, not on the spill.
 212   bool spillKill = isKill && LR.LastUse != MI;
 213
 214   if (LR.Dirty) {
 215     LR.Dirty = false;
 216     DEBUG(dbgs() << "Spilling register " << TRI->getName(LR.PhysReg)
 217       << " containing %reg" << VirtReg);
 218     const TargetRegisterClass *RC = MRI->getRegClass(VirtReg);
 219     int FrameIndex = getStackSpaceFor(VirtReg, RC);
 220     DEBUG(dbgs() << " to stack slot #" << FrameIndex << "\n");
 221     TII->storeRegToStackSlot(MBB, MI, LR.PhysReg, spillKill,
 222                              FrameIndex, RC, TRI);
 223     ++NumStores;   // Update statistics
 224
 225     if (spillKill)
 226       LR.LastUse = 0; // Don't kill register again
 227     else if (!isKill) {
 228       MachineInstr *Spill = llvm::prior(MI);
 229       LR.LastUse = Spill;
 230       LR.LastOpNum = Spill->findRegisterUseOperandIdx(LR.PhysReg);
 231     }
 232   }
 233
 234   if (isKill)
 235     killVirtReg(lri);
 236 }
 237
 238 /// spillAll - Spill all dirty virtregs without killing them.
 239 void RAFast::spillAll(MachineBasicBlock &MBB, MachineInstr *MI) {
 240   SmallVector<unsigned, 16> Dirty;
 241   for (LiveRegMap::iterator i = LiveVirtRegs.begin(),
 242        e = LiveVirtRegs.end(); i != e; ++i)
 243     if (i->second.Dirty)
 244       Dirty.push_back(i->first);
 245   for (unsigned i = 0, e = Dirty.size(); i != e; ++i)
 246     spillVirtReg(MBB, MI, Dirty[i], false);
 247 }
 248
 249 /// killPhysReg - Kill any virtual register aliased by PhysReg.
 250 void RAFast::killPhysReg(unsigned PhysReg) {
 251   // Fast path for the normal case.
 252   switch (unsigned VirtReg = PhysRegState[PhysReg]) {
 253   case regDisabled:
 254     break;
 255   case regFree:
 256     return;
 257   case regReserved:
 258     PhysRegState[PhysReg] = regFree;
 259     return;
 260   default:
 261     killVirtReg(VirtReg);
 262     return;
 263   }
 264
 265   // This is a disabled register, we have to check aliases.
 266   for (const unsigned *AS = TRI->getAliasSet(PhysReg);
 267        unsigned Alias = *AS; ++AS) {
 268     switch (unsigned VirtReg = PhysRegState[Alias]) {
 269     case regDisabled:
 270     case regFree:
 271       break;
 272     case regReserved:
 273       PhysRegState[Alias] = regFree;
 274       break;
 275     default:
 276       killVirtReg(VirtReg);
 277       break;
 278     }
 279   }
 280 }
 281
 282 /// spillPhysReg - Spill any dirty virtual registers that aliases PhysReg. If
 283 /// isKill is set, they are also killed.
 284 void RAFast::spillPhysReg(MachineBasicBlock &MBB, MachineInstr *MI,
 285                            unsigned PhysReg, bool isKill) {
 286   switch (unsigned VirtReg = PhysRegState[PhysReg]) {
 287   case regDisabled:
 288     break;
 289   case regFree:
 290     return;
 291   case regReserved:
 292     if (isKill)
 293       PhysRegState[PhysReg] = regFree;
 294     return;
 295   default:
 296     spillVirtReg(MBB, MI, VirtReg, isKill);
 297     return;
 298   }
 299
 300   // This is a disabled register, we have to check aliases.
 301   for (const unsigned *AS = TRI->getAliasSet(PhysReg);
 302        unsigned Alias = *AS; ++AS) {
 303     switch (unsigned VirtReg = PhysRegState[Alias]) {
 304     case regDisabled:
 305     case regFree:
 306       break;
 307     case regReserved:
 308       if (isKill)
 309         PhysRegState[Alias] = regFree;
 310       break;
 311     default:
 312       spillVirtReg(MBB, MI, VirtReg, isKill);
 313       break;
 314     }
 315   }
 316 }
 317
 318 /// assignVirtToPhysReg - This method updates local state so that we know
 319 /// that PhysReg is the proper container for VirtReg now.  The physical
 320 /// register must not be used for anything else when this is called.
 321 ///
 322 RAFast::LiveRegMap::iterator
 323 RAFast::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) {
 324   DEBUG(dbgs() << "Assigning %reg" << VirtReg << " to "
 325                << TRI->getName(PhysReg) << "\n");
 326   PhysRegState[PhysReg] = VirtReg;
 327   return LiveVirtRegs.insert(std::make_pair(VirtReg, PhysReg)).first;
 328 }
 329
 330 /// allocVirtReg - Allocate a physical register for VirtReg.
 331 RAFast::LiveRegMap::iterator RAFast::allocVirtReg(MachineBasicBlock &MBB,
 332                                                   MachineInstr *MI,
 333                                                   unsigned VirtReg,
 334                                                   unsigned Hint) {
 335   const unsigned spillCost = 100;
 336   assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
 337          "Can only allocate virtual registers");
 338
 339   const TargetRegisterClass *RC = MRI->getRegClass(VirtReg);
 340   TargetRegisterClass::iterator AOB = RC->allocation_order_begin(*MF);
 341   TargetRegisterClass::iterator AOE = RC->allocation_order_end(*MF);
 342
 343   // Ignore invalid hints.
 344   if (Hint && (!TargetRegisterInfo::isPhysicalRegister(Hint) ||
 345                !RC->contains(Hint) || UsedInInstr.test(Hint)))
 346     Hint = 0;
 347
 348   // If there is no hint, peek at the first use of this register.
 349   if (!Hint && !MRI->use_nodbg_empty(VirtReg)) {
 350     MachineInstr &MI = *MRI->use_nodbg_begin(VirtReg);
 351     unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
 352     // Copy to physreg -> use physreg as hint.
 353     if (TII->isMoveInstr(MI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
 354         SrcReg == VirtReg && TargetRegisterInfo::isPhysicalRegister(DstReg) &&
 355         RC->contains(DstReg) && !UsedInInstr.test(DstReg)) {
 356       Hint = DstReg;
 357       DEBUG(dbgs() << "%reg" << VirtReg << " gets hint from " << MI);
 358     }
 359   }
 360
 361   // Take hint when possible.
 362   if (Hint) {
 363     assert(RC->contains(Hint) && !UsedInInstr.test(Hint) &&
 364            "Invalid hint should have been cleared");
 365     switch(PhysRegState[Hint]) {
 366     case regDisabled:
 367     case regReserved:
 368       break;
 369     default:
 370       spillVirtReg(MBB, MI, PhysRegState[Hint], true);
 371       // Fall through.
 372     case regFree:
 373       return assignVirtToPhysReg(VirtReg, Hint);
 374     }
 375   }
 376
 377   // First try to find a completely free register.
 378   unsigned BestCost = 0, BestReg = 0;
 379   bool hasDisabled = false;
 380   for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) {
 381     unsigned PhysReg = *I;
 382     switch(PhysRegState[PhysReg]) {
 383     case regDisabled:
 384       hasDisabled = true;
 385     case regReserved:
 386       continue;
 387     case regFree:
 388       if (!UsedInInstr.test(PhysReg))
 389         return assignVirtToPhysReg(VirtReg, PhysReg);
 390       continue;
 391     default:
 392       // Grab the first spillable register we meet.
 393       if (!BestReg && !UsedInInstr.test(PhysReg))
 394         BestReg = PhysReg, BestCost = spillCost;
 395       continue;
 396     }
 397   }
 398
 399   DEBUG(dbgs() << "Allocating %reg" << VirtReg << " from " << RC->getName()
 400                << " candidate=" << TRI->getName(BestReg) << "\n");
 401
 402   // Try to extend the working set for RC if there were any disabled registers.
 403   if (hasDisabled && (!BestReg || BestCost >= spillCost)) {
 404     for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) {
 405       unsigned PhysReg = *I;
 406       if (PhysRegState[PhysReg] != regDisabled || UsedInInstr.test(PhysReg))
 407         continue;
 408
 409       // Calculate the cost of bringing PhysReg into the working set.
 410       unsigned Cost=0;
 411       bool Impossible = false;
 412       for (const unsigned *AS = TRI->getAliasSet(PhysReg);
 413       unsigned Alias = *AS; ++AS) {
 414         if (UsedInInstr.test(Alias)) {
 415           Impossible = true;
 416           break;
 417         }
 418         switch (PhysRegState[Alias]) {
 419         case regDisabled:
 420           break;
 421         case regReserved:
 422           Impossible = true;
 423           break;
 424         case regFree:
 425           Cost++;
 426           break;
 427         default:
 428           Cost += spillCost;
 429           break;
 430         }
 431       }
 432       if (Impossible) continue;
 433       DEBUG(dbgs() << "- candidate " << TRI->getName(PhysReg)
 434         << " cost=" << Cost << "\n");
 435       if (!BestReg || Cost < BestCost) {
 436         BestReg = PhysReg;
 437         BestCost = Cost;
 438         if (Cost < spillCost) break;
 439       }
 440     }
 441   }
 442
 443   if (BestReg) {
 444     // BestCost is 0 when all aliases are already disabled.
 445     if (BestCost) {
 446       if (PhysRegState[BestReg] != regDisabled)
 447         spillVirtReg(MBB, MI, PhysRegState[BestReg], true);
 448       else {
 449         // Make sure all aliases are disabled.
 450         for (const unsigned *AS = TRI->getAliasSet(BestReg);
 451              unsigned Alias = *AS; ++AS) {
 452           switch (PhysRegState[Alias]) {
 453           case regDisabled:
 454             continue;
 455           case regFree:
 456             PhysRegState[Alias] = regDisabled;
 457             break;
 458           default:
 459             spillVirtReg(MBB, MI, PhysRegState[Alias], true);
 460             PhysRegState[Alias] = regDisabled;
 461             break;
 462           }
 463         }
 464       }
 465     }
 466     return assignVirtToPhysReg(VirtReg, BestReg);
 467   }
 468
 469   // Nothing we can do.
 470   std::string msg;
 471   raw_string_ostream Msg(msg);
 472   Msg << "Ran out of registers during register allocation!";
 473   if (MI->isInlineAsm()) {
 474     Msg << "\nPlease check your inline asm statement for "
 475         << "invalid constraints:\n";
 476     MI->print(Msg, TM);
 477   }
 478   report_fatal_error(Msg.str());
 479   return LiveVirtRegs.end();
 480 }
 481
 482 /// defineVirtReg - Allocate a register for VirtReg and mark it as dirty.
 483 unsigned RAFast::defineVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
 484                               unsigned OpNum, unsigned VirtReg, unsigned Hint) {
 485   assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
 486          "Not a virtual register");
 487   LiveRegMap::iterator lri = LiveVirtRegs.find(VirtReg);
 488   if (lri == LiveVirtRegs.end())
 489     lri = allocVirtReg(MBB, MI, VirtReg, Hint);
 490   else
 491     addKillFlag(lri); // Kill before redefine.
 492   LiveReg &LR = lri->second;
 493   LR.LastUse = MI;
 494   LR.LastOpNum = OpNum;
 495   LR.Dirty = true;
 496   UsedInInstr.set(LR.PhysReg);
 497   return LR.PhysReg;
 498 }
 499
 500 /// reloadVirtReg - Make sure VirtReg is available in a physreg and return it.
 501 unsigned RAFast::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI,
 502                               unsigned OpNum, unsigned VirtReg, unsigned Hint) {
 503   assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
 504          "Not a virtual register");
 505   LiveRegMap::iterator lri = LiveVirtRegs.find(VirtReg);
 506   if (lri == LiveVirtRegs.end()) {
 507     lri = allocVirtReg(MBB, MI, VirtReg, Hint);
 508     const TargetRegisterClass *RC = MRI->getRegClass(VirtReg);
 509     int FrameIndex = getStackSpaceFor(VirtReg, RC);
 510     DEBUG(dbgs() << "Reloading %reg" << VirtReg << " into "
 511                  << TRI->getName(lri->second.PhysReg) << "\n");
 512     TII->loadRegFromStackSlot(MBB, MI, lri->second.PhysReg, FrameIndex, RC,
 513                               TRI);
 514     ++NumLoads;
 515   }
 516   LiveReg &LR = lri->second;
 517   LR.LastUse = MI;
 518   LR.LastOpNum = OpNum;
 519   UsedInInstr.set(LR.PhysReg);
 520   return LR.PhysReg;
 521 }
 522
 523 /// reservePhysReg - Mark PhysReg as reserved. This is very similar to
 524 /// defineVirtReg except the physreg is reserved instead of allocated.
 525 void RAFast::reservePhysReg(MachineBasicBlock &MBB, MachineInstr *MI,
 526                             unsigned PhysReg) {
 527   UsedInInstr.set(PhysReg);
 528   switch (unsigned VirtReg = PhysRegState[PhysReg]) {
 529   case regDisabled:
 530     break;
 531   case regFree:
 532     PhysRegState[PhysReg] = regReserved;
 533     return;
 534   case regReserved:
 535     return;
 536   default:
 537     spillVirtReg(MBB, MI, VirtReg, true);
 538     PhysRegState[PhysReg] = regReserved;
 539     return;
 540   }
 541
 542   // This is a disabled register, disable all aliases.
 543   for (const unsigned *AS = TRI->getAliasSet(PhysReg);
 544        unsigned Alias = *AS; ++AS) {
 545     UsedInInstr.set(Alias);
 546     switch (unsigned VirtReg = PhysRegState[Alias]) {
 547     case regDisabled:
 548     case regFree:
 549       break;
 550     case regReserved:
 551       // is a super register already reserved?
 552       if (TRI->isSuperRegister(PhysReg, Alias))
 553         return;
 554       break;
 555     default:
 556       spillVirtReg(MBB, MI, VirtReg, true);
 557       break;
 558     }
 559     PhysRegState[Alias] = regDisabled;
 560   }
 561   PhysRegState[PhysReg] = regReserved;
 562 }
 563
 564 // setPhysReg - Change MO the refer the PhysReg, considering subregs.
 565 void RAFast::setPhysReg(MachineOperand &MO, unsigned PhysReg) {
 566   if (unsigned Idx = MO.getSubReg()) {
 567     MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, Idx) : 0);
 568     MO.setSubReg(0);
 569   } else
 570     MO.setReg(PhysReg);
 571 }
 572
 573 void RAFast::AllocateBasicBlock(MachineBasicBlock &MBB) {
 574   DEBUG(dbgs() << "\nAllocating " << MBB);
 575
 576   PhysRegState.assign(TRI->getNumRegs(), regDisabled);
 577   assert(LiveVirtRegs.empty() && "Mapping not cleared form last block?");
 578
 579   MachineBasicBlock::iterator MII = MBB.begin();
 580
 581   // Add live-in registers as live.
 582   for (MachineBasicBlock::livein_iterator I = MBB.livein_begin(),
 583          E = MBB.livein_end(); I != E; ++I)
 584     reservePhysReg(MBB, MII, *I);
 585
 586   SmallVector<unsigned, 8> VirtKills, PhysKills, PhysDefs;
 587
 588   // Otherwise, sequentially allocate each instruction in the MBB.
 589   while (MII != MBB.end()) {
 590     MachineInstr *MI = MII++;
 591     const TargetInstrDesc &TID = MI->getDesc();
 592     DEBUG({
 593         dbgs() << "\n>> " << *MI << "Regs:";
 594         for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) {
 595           if (PhysRegState[Reg] == regDisabled) continue;
 596           dbgs() << " " << TRI->getName(Reg);
 597           switch(PhysRegState[Reg]) {
 598           case regFree:
 599             break;
 600           case regReserved:
 601             dbgs() << "*";
 602             break;
 603           default:
 604             dbgs() << "=%reg" << PhysRegState[Reg];
 605             if (LiveVirtRegs[PhysRegState[Reg]].Dirty)
 606               dbgs() << "*";
 607             assert(LiveVirtRegs[PhysRegState[Reg]].PhysReg == Reg &&
 608                    "Bad inverse map");
 609             break;
 610           }
 611         }
 612         dbgs() << '\n';
 613         // Check that LiveVirtRegs is the inverse.
 614         for (LiveRegMap::iterator i = LiveVirtRegs.begin(),
 615              e = LiveVirtRegs.end(); i != e; ++i) {
 616            assert(TargetRegisterInfo::isVirtualRegister(i->first) &&
 617                   "Bad map key");
 618            assert(TargetRegisterInfo::isPhysicalRegister(i->second.PhysReg) &&
 619                   "Bad map value");
 620            assert(PhysRegState[i->second.PhysReg] == i->first &&
 621                   "Bad inverse map");
 622         }
 623       });
 624
 625     // Debug values are not allowed to change codegen in any way.
 626     if (MI->isDebugValue()) {
 627       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 628         MachineOperand &MO = MI->getOperand(i);
 629         if (!MO.isReg()) continue;
 630         unsigned Reg = MO.getReg();
 631         if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
 632         LiveRegMap::iterator lri = LiveVirtRegs.find(Reg);
 633         if (lri != LiveVirtRegs.end())
 634           setPhysReg(MO, lri->second.PhysReg);
 635         else
 636           MO.setReg(0); // We can't allocate a physreg for a DebugValue, sorry!
 637       }
 638       // Next instruction.
 639       continue;
 640     }
 641
 642     // If this is a copy, we may be able to coalesce.
 643     unsigned CopySrc, CopyDst, CopySrcSub, CopyDstSub;
 644     if (!TII->isMoveInstr(*MI, CopySrc, CopyDst, CopySrcSub, CopyDstSub))
 645       CopySrc = CopyDst = 0;
 646
 647     // Track registers used by instruction.
 648     UsedInInstr.reset();
 649     PhysDefs.clear();
 650
 651     // First scan.
 652     // Mark physreg uses and early clobbers as used.
 653     // Collect PhysKills.
 654     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 655       MachineOperand &MO = MI->getOperand(i);
 656       if (!MO.isReg()) continue;
 657
 658       // FIXME: For now, don't trust kill flags
 659       if (MO.isUse()) MO.setIsKill(false);
 660
 661       unsigned Reg = MO.getReg();
 662       if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg) ||
 663           ReservedRegs.test(Reg)) continue;
 664       if (MO.isUse()) {
 665 #ifndef NDEBUG
 666         // We are using a physreg directly. It had better not be clobbered by a
 667         // virtreg.
 668         assert(PhysRegState[Reg] <= regReserved && "Using clobbered physreg");
 669         if (PhysRegState[Reg] == regDisabled)
 670           for (const unsigned *AS = TRI->getAliasSet(Reg);
 671                unsigned Alias = *AS; ++AS)
 672             assert(PhysRegState[Alias] <= regReserved &&
 673                    "Physreg alias was clobbered");
 674 #endif
 675         PhysKills.push_back(Reg); // Any clean physreg use is a kill.
 676         UsedInInstr.set(Reg);
 677       } else if (MO.isEarlyClobber()) {
 678         spillPhysReg(MBB, MI, Reg, true);
 679         UsedInInstr.set(Reg);
 680         PhysDefs.push_back(Reg);
 681       }
 682     }
 683
 684     // Second scan.
 685     // Allocate virtreg uses and early clobbers.
 686     // Collect VirtKills
 687     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 688       MachineOperand &MO = MI->getOperand(i);
 689       if (!MO.isReg()) continue;
 690       unsigned Reg = MO.getReg();
 691       if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
 692       if (MO.isUse()) {
 693         unsigned PhysReg = reloadVirtReg(MBB, MI, i, Reg, CopyDst);
 694         if (CopySrc == Reg)
 695           CopySrc = PhysReg;
 696         setPhysReg(MO, PhysReg);
 697         if (MO.isKill())
 698           VirtKills.push_back(Reg);
 699       } else if (MO.isEarlyClobber()) {
 700         unsigned PhysReg = defineVirtReg(MBB, MI, i, Reg, 0);
 701         setPhysReg(MO, PhysReg);
 702         PhysDefs.push_back(PhysReg);
 703       }
 704     }
 705
 706     // Process virtreg kills
 707     for (unsigned i = 0, e = VirtKills.size(); i != e; ++i)
 708       killVirtReg(VirtKills[i]);
 709     VirtKills.clear();
 710
 711     // Process physreg kills
 712     for (unsigned i = 0, e = PhysKills.size(); i != e; ++i)
 713       killPhysReg(PhysKills[i]);
 714     PhysKills.clear();
 715
 716     MRI->addPhysRegsUsed(UsedInInstr);
 717
 718     // Track registers defined by instruction - early clobbers at this point.
 719     UsedInInstr.reset();
 720     for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) {
 721       unsigned PhysReg = PhysDefs[i];
 722       UsedInInstr.set(PhysReg);
 723       for (const unsigned *AS = TRI->getAliasSet(PhysReg);
 724             unsigned Alias = *AS; ++AS)
 725         UsedInInstr.set(Alias);
 726     }
 727
 728     // Third scan.
 729     // Allocate defs and collect dead defs.
 730     for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 731       MachineOperand &MO = MI->getOperand(i);
 732       if (!MO.isReg() || !MO.isDef() || !MO.getReg()) continue;
 733       unsigned Reg = MO.getReg();
 734
 735       if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
 736         if (ReservedRegs.test(Reg)) continue;
 737         if (MO.isImplicit())
 738           spillPhysReg(MBB, MI, Reg, true);
 739         else
 740           reservePhysReg(MBB, MI, Reg);
 741         if (MO.isDead())
 742           PhysKills.push_back(Reg);
 743         continue;
 744       }
 745       if (MO.isDead())
 746         VirtKills.push_back(Reg);
 747       unsigned PhysReg = defineVirtReg(MBB, MI, i, Reg, CopySrc);
 748       if (CopyDst == Reg)
 749         CopyDst = PhysReg;
 750       setPhysReg(MO, PhysReg);
 751     }
 752
 753     // Spill all dirty virtregs before a call, in case of an exception.
 754     if (TID.isCall()) {
 755       DEBUG(dbgs() << "  Spilling remaining registers before call.\n");
 756       spillAll(MBB, MI);
 757     }
 758
 759     // Process virtreg deads.
 760     for (unsigned i = 0, e = VirtKills.size(); i != e; ++i)
 761       killVirtReg(VirtKills[i]);
 762     VirtKills.clear();
 763
 764     // Process physreg deads.
 765     for (unsigned i = 0, e = PhysKills.size(); i != e; ++i)
 766       killPhysReg(PhysKills[i]);
 767     PhysKills.clear();
 768
 769     MRI->addPhysRegsUsed(UsedInInstr);
 770
 771     DEBUG(dbgs() << "<< " << *MI);
 772   }
 773
 774   // Spill all physical registers holding virtual registers now.
 775   DEBUG(dbgs() << "Killing live registers at end of block.\n");
 776   MachineBasicBlock::iterator MI = MBB.getFirstTerminator();
 777   while (!LiveVirtRegs.empty())
 778     spillVirtReg(MBB, MI, LiveVirtRegs.begin()->first, true);
 779
 780   DEBUG(MBB.dump());
 781 }
 782
 783 /// runOnMachineFunction - Register allocate the whole function
 784 ///
 785 bool RAFast::runOnMachineFunction(MachineFunction &Fn) {
 786   DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n"
 787                << "********** Function: "
 788                << ((Value*)Fn.getFunction())->getName() << '\n');
 789   MF = &Fn;
 790   MRI = &MF->getRegInfo();
 791   TM = &Fn.getTarget();
 792   TRI = TM->getRegisterInfo();
 793   TII = TM->getInstrInfo();
 794
 795   UsedInInstr.resize(TRI->getNumRegs());
 796   ReservedRegs = TRI->getReservedRegs(*MF);
 797
 798   // initialize the virtual->physical register map to have a 'null'
 799   // mapping for all virtual registers
 800   unsigned LastVirtReg = MRI->getLastVirtReg();
 801   StackSlotForVirtReg.grow(LastVirtReg);
 802
 803   // Loop over all of the basic blocks, eliminating virtual register references
 804   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
 805        MBB != MBBe; ++MBB)
 806     AllocateBasicBlock(*MBB);
 807
 808   // Make sure the set of used physregs is closed under subreg operations.
 809   MRI->closePhysRegsUsed(*TRI);
 810
 811   StackSlotForVirtReg.clear();
 812   return true;
 813 }
 814
 815 FunctionPass *llvm::createFastRegisterAllocator() {
 816   return new RAFast();
 817 }