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