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