RegAllocFast.cpp revision c9c4dacd03a4b80d61ed6b9c6ffeb1b1f76b8d1c 
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    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.
151int 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.
167void 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.
180void 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.
189void 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.
200void 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.
239void 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.
250void 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.
284void 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///
322RAFast::LiveRegMap::iterator
323RAFast::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.
331RAFast::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.
483unsigned 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.
501unsigned 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.
525void 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.
565void 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
573void 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///
785bool 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
815FunctionPass *llvm::createFastRegisterAllocator() {
816  return new RAFast();
817}
818