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