RegAllocFast.cpp revision a65d6a686e6ad865c61aec70c5bdfb30bf6f5b22 
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/MachineInstrBuilder.h"
20#include "llvm/CodeGen/MachineFrameInfo.h"
21#include "llvm/CodeGen/MachineRegisterInfo.h"
22#include "llvm/CodeGen/Passes.h"
23#include "llvm/CodeGen/RegAllocRegistry.h"
24#include "llvm/Target/TargetInstrInfo.h"
25#include "llvm/Target/TargetMachine.h"
26#include "llvm/Support/CommandLine.h"
27#include "llvm/Support/Debug.h"
28#include "llvm/Support/ErrorHandling.h"
29#include "llvm/Support/raw_ostream.h"
30#include "llvm/ADT/DenseMap.h"
31#include "llvm/ADT/IndexedMap.h"
32#include "llvm/ADT/SmallSet.h"
33#include "llvm/ADT/SmallVector.h"
34#include "llvm/ADT/Statistic.h"
35#include "llvm/ADT/STLExtras.h"
36#include <algorithm>
37using namespace llvm;
38
39STATISTIC(NumStores, "Number of stores added");
40STATISTIC(NumLoads , "Number of loads added");
41STATISTIC(NumCopies, "Number of copies coalesced");
42
43static RegisterRegAlloc
44  fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator);
45
46namespace {
47  class RAFast : public MachineFunctionPass {
48  public:
49    static char ID;
50    RAFast() : MachineFunctionPass(ID), StackSlotForVirtReg(-1),
51               isBulkSpilling(false) {
52      initializePHIEliminationPass(*PassRegistry::getPassRegistry());
53      initializeTwoAddressInstructionPassPass(*PassRegistry::getPassRegistry());
54    }
55  private:
56    const TargetMachine *TM;
57    MachineFunction *MF;
58    MachineRegisterInfo *MRI;
59    const TargetRegisterInfo *TRI;
60    const TargetInstrInfo *TII;
61
62    // Basic block currently being allocated.
63    MachineBasicBlock *MBB;
64
65    // StackSlotForVirtReg - Maps virtual regs to the frame index where these
66    // values are spilled.
67    IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg;
68
69    // Everything we know about a live virtual register.
70    struct LiveReg {
71      MachineInstr *LastUse;    // Last instr to use reg.
72      unsigned PhysReg;         // Currently held here.
73      unsigned short LastOpNum; // OpNum on LastUse.
74      bool Dirty;               // Register needs spill.
75
76      LiveReg(unsigned p=0) : LastUse(0), PhysReg(p), LastOpNum(0),
77                              Dirty(false) {}
78    };
79
80    typedef DenseMap<unsigned, LiveReg> LiveRegMap;
81    typedef LiveRegMap::value_type LiveRegEntry;
82
83    // LiveVirtRegs - This map contains entries for each virtual register
84    // that is currently available in a physical register.
85    LiveRegMap LiveVirtRegs;
86
87    DenseMap<unsigned, MachineInstr *> LiveDbgValueMap;
88
89    // RegState - Track the state of a physical register.
90    enum RegState {
91      // A disabled register is not available for allocation, but an alias may
92      // be in use. A register can only be moved out of the disabled state if
93      // all aliases are disabled.
94      regDisabled,
95
96      // A free register is not currently in use and can be allocated
97      // immediately without checking aliases.
98      regFree,
99
100      // A reserved register has been assigned expolicitly (e.g., setting up a
101      // call parameter), and it remains reserved until it is used.
102      regReserved
103
104      // A register state may also be a virtual register number, indication that
105      // the physical register is currently allocated to a virtual register. In
106      // that case, LiveVirtRegs contains the inverse mapping.
107    };
108
109    // PhysRegState - One of the RegState enums, or a virtreg.
110    std::vector<unsigned> PhysRegState;
111
112    // UsedInInstr - BitVector of physregs that are used in the current
113    // instruction, and so cannot be allocated.
114    BitVector UsedInInstr;
115
116    // Allocatable - vector of allocatable physical registers.
117    BitVector Allocatable;
118
119    // SkippedInstrs - Descriptors of instructions whose clobber list was
120    // ignored because all registers were spilled. It is still necessary to
121    // mark all the clobbered registers as used by the function.
122    SmallPtrSet<const TargetInstrDesc*, 4> SkippedInstrs;
123
124    // isBulkSpilling - This flag is set when LiveRegMap will be cleared
125    // completely after spilling all live registers. LiveRegMap entries should
126    // not be erased.
127    bool isBulkSpilling;
128
129    enum {
130      spillClean = 1,
131      spillDirty = 100,
132      spillImpossible = ~0u
133    };
134  public:
135    virtual const char *getPassName() const {
136      return "Fast Register Allocator";
137    }
138
139    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
140      AU.setPreservesCFG();
141      AU.addRequiredID(PHIEliminationID);
142      AU.addRequiredID(TwoAddressInstructionPassID);
143      MachineFunctionPass::getAnalysisUsage(AU);
144    }
145
146  private:
147    bool runOnMachineFunction(MachineFunction &Fn);
148    void AllocateBasicBlock();
149    void handleThroughOperands(MachineInstr *MI,
150                               SmallVectorImpl<unsigned> &VirtDead);
151    int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC);
152    bool isLastUseOfLocalReg(MachineOperand&);
153
154    void addKillFlag(const LiveReg&);
155    void killVirtReg(LiveRegMap::iterator);
156    void killVirtReg(unsigned VirtReg);
157    void spillVirtReg(MachineBasicBlock::iterator MI, LiveRegMap::iterator);
158    void spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg);
159
160    void usePhysReg(MachineOperand&);
161    void definePhysReg(MachineInstr *MI, unsigned PhysReg, RegState NewState);
162    unsigned calcSpillCost(unsigned PhysReg) const;
163    void assignVirtToPhysReg(LiveRegEntry &LRE, unsigned PhysReg);
164    void allocVirtReg(MachineInstr *MI, LiveRegEntry &LRE, unsigned Hint);
165    LiveRegMap::iterator defineVirtReg(MachineInstr *MI, unsigned OpNum,
166                                       unsigned VirtReg, unsigned Hint);
167    LiveRegMap::iterator reloadVirtReg(MachineInstr *MI, unsigned OpNum,
168                                       unsigned VirtReg, unsigned Hint);
169    void spillAll(MachineInstr *MI);
170    bool setPhysReg(MachineInstr *MI, unsigned OpNum, unsigned PhysReg);
171  };
172  char RAFast::ID = 0;
173}
174
175/// getStackSpaceFor - This allocates space for the specified virtual register
176/// to be held on the stack.
177int RAFast::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) {
178  // Find the location Reg would belong...
179  int SS = StackSlotForVirtReg[VirtReg];
180  if (SS != -1)
181    return SS;          // Already has space allocated?
182
183  // Allocate a new stack object for this spill location...
184  int FrameIdx = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(),
185                                                            RC->getAlignment());
186
187  // Assign the slot.
188  StackSlotForVirtReg[VirtReg] = FrameIdx;
189  return FrameIdx;
190}
191
192/// isLastUseOfLocalReg - Return true if MO is the only remaining reference to
193/// its virtual register, and it is guaranteed to be a block-local register.
194///
195bool RAFast::isLastUseOfLocalReg(MachineOperand &MO) {
196  // Check for non-debug uses or defs following MO.
197  // This is the most likely way to fail - fast path it.
198  MachineOperand *Next = &MO;
199  while ((Next = Next->getNextOperandForReg()))
200    if (!Next->isDebug())
201      return false;
202
203  // If the register has ever been spilled or reloaded, we conservatively assume
204  // it is a global register used in multiple blocks.
205  if (StackSlotForVirtReg[MO.getReg()] != -1)
206    return false;
207
208  // Check that the use/def chain has exactly one operand - MO.
209  return &MRI->reg_nodbg_begin(MO.getReg()).getOperand() == &MO;
210}
211
212/// addKillFlag - Set kill flags on last use of a virtual register.
213void RAFast::addKillFlag(const LiveReg &LR) {
214  if (!LR.LastUse) return;
215  MachineOperand &MO = LR.LastUse->getOperand(LR.LastOpNum);
216  if (MO.isUse() && !LR.LastUse->isRegTiedToDefOperand(LR.LastOpNum)) {
217    if (MO.getReg() == LR.PhysReg)
218      MO.setIsKill();
219    else
220      LR.LastUse->addRegisterKilled(LR.PhysReg, TRI, true);
221  }
222}
223
224/// killVirtReg - Mark virtreg as no longer available.
225void RAFast::killVirtReg(LiveRegMap::iterator LRI) {
226  addKillFlag(LRI->second);
227  const LiveReg &LR = LRI->second;
228  assert(PhysRegState[LR.PhysReg] == LRI->first && "Broken RegState mapping");
229  PhysRegState[LR.PhysReg] = regFree;
230  // Erase from LiveVirtRegs unless we're spilling in bulk.
231  if (!isBulkSpilling)
232    LiveVirtRegs.erase(LRI);
233}
234
235/// killVirtReg - Mark virtreg as no longer available.
236void RAFast::killVirtReg(unsigned VirtReg) {
237  assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
238         "killVirtReg needs a virtual register");
239  LiveRegMap::iterator LRI = LiveVirtRegs.find(VirtReg);
240  if (LRI != LiveVirtRegs.end())
241    killVirtReg(LRI);
242}
243
244/// spillVirtReg - This method spills the value specified by VirtReg into the
245/// corresponding stack slot if needed.
246void RAFast::spillVirtReg(MachineBasicBlock::iterator MI, unsigned VirtReg) {
247  assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
248         "Spilling a physical register is illegal!");
249  LiveRegMap::iterator LRI = LiveVirtRegs.find(VirtReg);
250  assert(LRI != LiveVirtRegs.end() && "Spilling unmapped virtual register");
251  spillVirtReg(MI, LRI);
252}
253
254/// spillVirtReg - Do the actual work of spilling.
255void RAFast::spillVirtReg(MachineBasicBlock::iterator MI,
256                          LiveRegMap::iterator LRI) {
257  LiveReg &LR = LRI->second;
258  assert(PhysRegState[LR.PhysReg] == LRI->first && "Broken RegState mapping");
259
260  if (LR.Dirty) {
261    // If this physreg is used by the instruction, we want to kill it on the
262    // instruction, not on the spill.
263    bool SpillKill = LR.LastUse != MI;
264    LR.Dirty = false;
265    DEBUG(dbgs() << "Spilling %reg" << LRI->first
266                 << " in " << TRI->getName(LR.PhysReg));
267    const TargetRegisterClass *RC = MRI->getRegClass(LRI->first);
268    int FI = getStackSpaceFor(LRI->first, RC);
269    DEBUG(dbgs() << " to stack slot #" << FI << "\n");
270    TII->storeRegToStackSlot(*MBB, MI, LR.PhysReg, SpillKill, FI, RC, TRI);
271    ++NumStores;   // Update statistics
272
273    // If this register is used by DBG_VALUE then insert new DBG_VALUE to
274    // identify spilled location as the place to find corresponding variable's
275    // value.
276    if (MachineInstr *DBG = LiveDbgValueMap.lookup(LRI->first)) {
277      const MDNode *MDPtr =
278        DBG->getOperand(DBG->getNumOperands()-1).getMetadata();
279      int64_t Offset = 0;
280      if (DBG->getOperand(1).isImm())
281        Offset = DBG->getOperand(1).getImm();
282      DebugLoc DL;
283      if (MI == MBB->end()) {
284        // If MI is at basic block end then use last instruction's location.
285        MachineBasicBlock::iterator EI = MI;
286        DL = (--EI)->getDebugLoc();
287      }
288      else
289        DL = MI->getDebugLoc();
290      if (MachineInstr *NewDV =
291          TII->emitFrameIndexDebugValue(*MF, FI, Offset, MDPtr, DL)) {
292        MachineBasicBlock *MBB = DBG->getParent();
293        MBB->insert(MI, NewDV);
294        DEBUG(dbgs() << "Inserting debug info due to spill:" << "\n" << *NewDV);
295        LiveDbgValueMap[LRI->first] = NewDV;
296      }
297    }
298    if (SpillKill)
299      LR.LastUse = 0; // Don't kill register again
300  }
301  killVirtReg(LRI);
302}
303
304/// spillAll - Spill all dirty virtregs without killing them.
305void RAFast::spillAll(MachineInstr *MI) {
306  if (LiveVirtRegs.empty()) return;
307  isBulkSpilling = true;
308  // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order
309  // of spilling here is deterministic, if arbitrary.
310  for (LiveRegMap::iterator i = LiveVirtRegs.begin(), e = LiveVirtRegs.end();
311       i != e; ++i)
312    spillVirtReg(MI, i);
313  LiveVirtRegs.clear();
314  isBulkSpilling = false;
315}
316
317/// usePhysReg - Handle the direct use of a physical register.
318/// Check that the register is not used by a virtreg.
319/// Kill the physreg, marking it free.
320/// This may add implicit kills to MO->getParent() and invalidate MO.
321void RAFast::usePhysReg(MachineOperand &MO) {
322  unsigned PhysReg = MO.getReg();
323  assert(TargetRegisterInfo::isPhysicalRegister(PhysReg) &&
324         "Bad usePhysReg operand");
325
326  switch (PhysRegState[PhysReg]) {
327  case regDisabled:
328    break;
329  case regReserved:
330    PhysRegState[PhysReg] = regFree;
331    // Fall through
332  case regFree:
333    UsedInInstr.set(PhysReg);
334    MO.setIsKill();
335    return;
336  default:
337    // The physreg was allocated to a virtual register. That means to value we
338    // wanted has been clobbered.
339    llvm_unreachable("Instruction uses an allocated register");
340  }
341
342  // Maybe a superregister is reserved?
343  for (const unsigned *AS = TRI->getAliasSet(PhysReg);
344       unsigned Alias = *AS; ++AS) {
345    switch (PhysRegState[Alias]) {
346    case regDisabled:
347      break;
348    case regReserved:
349      assert(TRI->isSuperRegister(PhysReg, Alias) &&
350             "Instruction is not using a subregister of a reserved register");
351      // Leave the superregister in the working set.
352      PhysRegState[Alias] = regFree;
353      UsedInInstr.set(Alias);
354      MO.getParent()->addRegisterKilled(Alias, TRI, true);
355      return;
356    case regFree:
357      if (TRI->isSuperRegister(PhysReg, Alias)) {
358        // Leave the superregister in the working set.
359        UsedInInstr.set(Alias);
360        MO.getParent()->addRegisterKilled(Alias, TRI, true);
361        return;
362      }
363      // Some other alias was in the working set - clear it.
364      PhysRegState[Alias] = regDisabled;
365      break;
366    default:
367      llvm_unreachable("Instruction uses an alias of an allocated register");
368    }
369  }
370
371  // All aliases are disabled, bring register into working set.
372  PhysRegState[PhysReg] = regFree;
373  UsedInInstr.set(PhysReg);
374  MO.setIsKill();
375}
376
377/// definePhysReg - Mark PhysReg as reserved or free after spilling any
378/// virtregs. This is very similar to defineVirtReg except the physreg is
379/// reserved instead of allocated.
380void RAFast::definePhysReg(MachineInstr *MI, unsigned PhysReg,
381                           RegState NewState) {
382  UsedInInstr.set(PhysReg);
383  switch (unsigned VirtReg = PhysRegState[PhysReg]) {
384  case regDisabled:
385    break;
386  default:
387    spillVirtReg(MI, VirtReg);
388    // Fall through.
389  case regFree:
390  case regReserved:
391    PhysRegState[PhysReg] = NewState;
392    return;
393  }
394
395  // This is a disabled register, disable all aliases.
396  PhysRegState[PhysReg] = NewState;
397  for (const unsigned *AS = TRI->getAliasSet(PhysReg);
398       unsigned Alias = *AS; ++AS) {
399    UsedInInstr.set(Alias);
400    switch (unsigned VirtReg = PhysRegState[Alias]) {
401    case regDisabled:
402      break;
403    default:
404      spillVirtReg(MI, VirtReg);
405      // Fall through.
406    case regFree:
407    case regReserved:
408      PhysRegState[Alias] = regDisabled;
409      if (TRI->isSuperRegister(PhysReg, Alias))
410        return;
411      break;
412    }
413  }
414}
415
416
417// calcSpillCost - Return the cost of spilling clearing out PhysReg and
418// aliases so it is free for allocation.
419// Returns 0 when PhysReg is free or disabled with all aliases disabled - it
420// can be allocated directly.
421// Returns spillImpossible when PhysReg or an alias can't be spilled.
422unsigned RAFast::calcSpillCost(unsigned PhysReg) const {
423  if (UsedInInstr.test(PhysReg))
424    return spillImpossible;
425  switch (unsigned VirtReg = PhysRegState[PhysReg]) {
426  case regDisabled:
427    break;
428  case regFree:
429    return 0;
430  case regReserved:
431    return spillImpossible;
432  default:
433    return LiveVirtRegs.lookup(VirtReg).Dirty ? spillDirty : spillClean;
434  }
435
436  // This is a disabled register, add up const of aliases.
437  unsigned Cost = 0;
438  for (const unsigned *AS = TRI->getAliasSet(PhysReg);
439       unsigned Alias = *AS; ++AS) {
440    if (UsedInInstr.test(Alias))
441      return spillImpossible;
442    switch (unsigned VirtReg = PhysRegState[Alias]) {
443    case regDisabled:
444      break;
445    case regFree:
446      ++Cost;
447      break;
448    case regReserved:
449      return spillImpossible;
450    default:
451      Cost += LiveVirtRegs.lookup(VirtReg).Dirty ? spillDirty : spillClean;
452      break;
453    }
454  }
455  return Cost;
456}
457
458
459/// assignVirtToPhysReg - This method updates local state so that we know
460/// that PhysReg is the proper container for VirtReg now.  The physical
461/// register must not be used for anything else when this is called.
462///
463void RAFast::assignVirtToPhysReg(LiveRegEntry &LRE, unsigned PhysReg) {
464  DEBUG(dbgs() << "Assigning %reg" << LRE.first << " to "
465               << TRI->getName(PhysReg) << "\n");
466  PhysRegState[PhysReg] = LRE.first;
467  assert(!LRE.second.PhysReg && "Already assigned a physreg");
468  LRE.second.PhysReg = PhysReg;
469}
470
471/// allocVirtReg - Allocate a physical register for VirtReg.
472void RAFast::allocVirtReg(MachineInstr *MI, LiveRegEntry &LRE, unsigned Hint) {
473  const unsigned VirtReg = LRE.first;
474
475  assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
476         "Can only allocate virtual registers");
477
478  const TargetRegisterClass *RC = MRI->getRegClass(VirtReg);
479
480  // Ignore invalid hints.
481  if (Hint && (!TargetRegisterInfo::isPhysicalRegister(Hint) ||
482               !RC->contains(Hint) || !Allocatable.test(Hint)))
483    Hint = 0;
484
485  // Take hint when possible.
486  if (Hint) {
487    switch(calcSpillCost(Hint)) {
488    default:
489      definePhysReg(MI, Hint, regFree);
490      // Fall through.
491    case 0:
492      return assignVirtToPhysReg(LRE, Hint);
493    case spillImpossible:
494      break;
495    }
496  }
497
498  TargetRegisterClass::iterator AOB = RC->allocation_order_begin(*MF);
499  TargetRegisterClass::iterator AOE = RC->allocation_order_end(*MF);
500
501  // First try to find a completely free register.
502  for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) {
503    unsigned PhysReg = *I;
504    if (PhysRegState[PhysReg] == regFree && !UsedInInstr.test(PhysReg) &&
505        Allocatable.test(PhysReg))
506      return assignVirtToPhysReg(LRE, PhysReg);
507  }
508
509  DEBUG(dbgs() << "Allocating %reg" << VirtReg << " from " << RC->getName()
510               << "\n");
511
512  unsigned BestReg = 0, BestCost = spillImpossible;
513  for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) {
514    if (!Allocatable.test(*I))
515      continue;
516    unsigned Cost = calcSpillCost(*I);
517    // Cost is 0 when all aliases are already disabled.
518    if (Cost == 0)
519      return assignVirtToPhysReg(LRE, *I);
520    if (Cost < BestCost)
521      BestReg = *I, BestCost = Cost;
522  }
523
524  if (BestReg) {
525    definePhysReg(MI, BestReg, regFree);
526    return assignVirtToPhysReg(LRE, BestReg);
527  }
528
529  // Nothing we can do.
530  std::string msg;
531  raw_string_ostream Msg(msg);
532  Msg << "Ran out of registers during register allocation!";
533  if (MI->isInlineAsm()) {
534    Msg << "\nPlease check your inline asm statement for "
535        << "invalid constraints:\n";
536    MI->print(Msg, TM);
537  }
538  report_fatal_error(Msg.str());
539}
540
541/// defineVirtReg - Allocate a register for VirtReg and mark it as dirty.
542RAFast::LiveRegMap::iterator
543RAFast::defineVirtReg(MachineInstr *MI, unsigned OpNum,
544                      unsigned VirtReg, unsigned Hint) {
545  assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
546         "Not a virtual register");
547  LiveRegMap::iterator LRI;
548  bool New;
549  tie(LRI, New) = LiveVirtRegs.insert(std::make_pair(VirtReg, LiveReg()));
550  LiveReg &LR = LRI->second;
551  if (New) {
552    // If there is no hint, peek at the only use of this register.
553    if ((!Hint || !TargetRegisterInfo::isPhysicalRegister(Hint)) &&
554        MRI->hasOneNonDBGUse(VirtReg)) {
555      const MachineInstr &UseMI = *MRI->use_nodbg_begin(VirtReg);
556      // It's a copy, use the destination register as a hint.
557      if (UseMI.isCopyLike())
558        Hint = UseMI.getOperand(0).getReg();
559    }
560    allocVirtReg(MI, *LRI, Hint);
561  } else if (LR.LastUse) {
562    // Redefining a live register - kill at the last use, unless it is this
563    // instruction defining VirtReg multiple times.
564    if (LR.LastUse != MI || LR.LastUse->getOperand(LR.LastOpNum).isUse())
565      addKillFlag(LR);
566  }
567  assert(LR.PhysReg && "Register not assigned");
568  LR.LastUse = MI;
569  LR.LastOpNum = OpNum;
570  LR.Dirty = true;
571  UsedInInstr.set(LR.PhysReg);
572  return LRI;
573}
574
575/// reloadVirtReg - Make sure VirtReg is available in a physreg and return it.
576RAFast::LiveRegMap::iterator
577RAFast::reloadVirtReg(MachineInstr *MI, unsigned OpNum,
578                      unsigned VirtReg, unsigned Hint) {
579  assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
580         "Not a virtual register");
581  LiveRegMap::iterator LRI;
582  bool New;
583  tie(LRI, New) = LiveVirtRegs.insert(std::make_pair(VirtReg, LiveReg()));
584  LiveReg &LR = LRI->second;
585  MachineOperand &MO = MI->getOperand(OpNum);
586  if (New) {
587    allocVirtReg(MI, *LRI, Hint);
588    const TargetRegisterClass *RC = MRI->getRegClass(VirtReg);
589    int FrameIndex = getStackSpaceFor(VirtReg, RC);
590    DEBUG(dbgs() << "Reloading %reg" << VirtReg << " into "
591                 << TRI->getName(LR.PhysReg) << "\n");
592    TII->loadRegFromStackSlot(*MBB, MI, LR.PhysReg, FrameIndex, RC, TRI);
593    ++NumLoads;
594  } else if (LR.Dirty) {
595    if (isLastUseOfLocalReg(MO)) {
596      DEBUG(dbgs() << "Killing last use: " << MO << "\n");
597      if (MO.isUse())
598        MO.setIsKill();
599      else
600        MO.setIsDead();
601    } else if (MO.isKill()) {
602      DEBUG(dbgs() << "Clearing dubious kill: " << MO << "\n");
603      MO.setIsKill(false);
604    } else if (MO.isDead()) {
605      DEBUG(dbgs() << "Clearing dubious dead: " << MO << "\n");
606      MO.setIsDead(false);
607    }
608  } else if (MO.isKill()) {
609    // We must remove kill flags from uses of reloaded registers because the
610    // register would be killed immediately, and there might be a second use:
611    //   %foo = OR %x<kill>, %x
612    // This would cause a second reload of %x into a different register.
613    DEBUG(dbgs() << "Clearing clean kill: " << MO << "\n");
614    MO.setIsKill(false);
615  } else if (MO.isDead()) {
616    DEBUG(dbgs() << "Clearing clean dead: " << MO << "\n");
617    MO.setIsDead(false);
618  }
619  assert(LR.PhysReg && "Register not assigned");
620  LR.LastUse = MI;
621  LR.LastOpNum = OpNum;
622  UsedInInstr.set(LR.PhysReg);
623  return LRI;
624}
625
626// setPhysReg - Change operand OpNum in MI the refer the PhysReg, considering
627// subregs. This may invalidate any operand pointers.
628// Return true if the operand kills its register.
629bool RAFast::setPhysReg(MachineInstr *MI, unsigned OpNum, unsigned PhysReg) {
630  MachineOperand &MO = MI->getOperand(OpNum);
631  if (!MO.getSubReg()) {
632    MO.setReg(PhysReg);
633    return MO.isKill() || MO.isDead();
634  }
635
636  // Handle subregister index.
637  MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, MO.getSubReg()) : 0);
638  MO.setSubReg(0);
639
640  // A kill flag implies killing the full register. Add corresponding super
641  // register kill.
642  if (MO.isKill()) {
643    MI->addRegisterKilled(PhysReg, TRI, true);
644    return true;
645  }
646  return MO.isDead();
647}
648
649// Handle special instruction operand like early clobbers and tied ops when
650// there are additional physreg defines.
651void RAFast::handleThroughOperands(MachineInstr *MI,
652                                   SmallVectorImpl<unsigned> &VirtDead) {
653  DEBUG(dbgs() << "Scanning for through registers:");
654  SmallSet<unsigned, 8> ThroughRegs;
655  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
656    MachineOperand &MO = MI->getOperand(i);
657    if (!MO.isReg()) continue;
658    unsigned Reg = MO.getReg();
659    if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
660    if (MO.isEarlyClobber() || MI->isRegTiedToDefOperand(i) ||
661        (MO.getSubReg() && MI->readsVirtualRegister(Reg))) {
662      if (ThroughRegs.insert(Reg))
663        DEBUG(dbgs() << " %reg" << Reg);
664    }
665  }
666
667  // If any physreg defines collide with preallocated through registers,
668  // we must spill and reallocate.
669  DEBUG(dbgs() << "\nChecking for physdef collisions.\n");
670  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
671    MachineOperand &MO = MI->getOperand(i);
672    if (!MO.isReg() || !MO.isDef()) continue;
673    unsigned Reg = MO.getReg();
674    if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
675    UsedInInstr.set(Reg);
676    if (ThroughRegs.count(PhysRegState[Reg]))
677      definePhysReg(MI, Reg, regFree);
678    for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
679      UsedInInstr.set(*AS);
680      if (ThroughRegs.count(PhysRegState[*AS]))
681        definePhysReg(MI, *AS, regFree);
682    }
683  }
684
685  SmallVector<unsigned, 8> PartialDefs;
686  DEBUG(dbgs() << "Allocating tied uses and early clobbers.\n");
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 DefIdx = 0;
694      if (!MI->isRegTiedToDefOperand(i, &DefIdx)) continue;
695      DEBUG(dbgs() << "Operand " << i << "("<< MO << ") is tied to operand "
696        << DefIdx << ".\n");
697      LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, 0);
698      unsigned PhysReg = LRI->second.PhysReg;
699      setPhysReg(MI, i, PhysReg);
700      // Note: we don't update the def operand yet. That would cause the normal
701      // def-scan to attempt spilling.
702    } else if (MO.getSubReg() && MI->readsVirtualRegister(Reg)) {
703      DEBUG(dbgs() << "Partial redefine: " << MO << "\n");
704      // Reload the register, but don't assign to the operand just yet.
705      // That would confuse the later phys-def processing pass.
706      LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, 0);
707      PartialDefs.push_back(LRI->second.PhysReg);
708    } else if (MO.isEarlyClobber()) {
709      // Note: defineVirtReg may invalidate MO.
710      LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, 0);
711      unsigned PhysReg = LRI->second.PhysReg;
712      if (setPhysReg(MI, i, PhysReg))
713        VirtDead.push_back(Reg);
714    }
715  }
716
717  // Restore UsedInInstr to a state usable for allocating normal virtual uses.
718  UsedInInstr.reset();
719  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
720    MachineOperand &MO = MI->getOperand(i);
721    if (!MO.isReg() || (MO.isDef() && !MO.isEarlyClobber())) continue;
722    unsigned Reg = MO.getReg();
723    if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
724    UsedInInstr.set(Reg);
725    for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS)
726      UsedInInstr.set(*AS);
727  }
728
729  // Also mark PartialDefs as used to avoid reallocation.
730  for (unsigned i = 0, e = PartialDefs.size(); i != e; ++i)
731    UsedInInstr.set(PartialDefs[i]);
732}
733
734void RAFast::AllocateBasicBlock() {
735  DEBUG(dbgs() << "\nAllocating " << *MBB);
736
737  PhysRegState.assign(TRI->getNumRegs(), regDisabled);
738  assert(LiveVirtRegs.empty() && "Mapping not cleared form last block?");
739
740  MachineBasicBlock::iterator MII = MBB->begin();
741
742  // Add live-in registers as live.
743  for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
744         E = MBB->livein_end(); I != E; ++I)
745    if (Allocatable.test(*I))
746      definePhysReg(MII, *I, regReserved);
747
748  SmallVector<unsigned, 8> VirtDead;
749  SmallVector<MachineInstr*, 32> Coalesced;
750
751  // Otherwise, sequentially allocate each instruction in the MBB.
752  while (MII != MBB->end()) {
753    MachineInstr *MI = MII++;
754    const TargetInstrDesc &TID = MI->getDesc();
755    DEBUG({
756        dbgs() << "\n>> " << *MI << "Regs:";
757        for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) {
758          if (PhysRegState[Reg] == regDisabled) continue;
759          dbgs() << " " << TRI->getName(Reg);
760          switch(PhysRegState[Reg]) {
761          case regFree:
762            break;
763          case regReserved:
764            dbgs() << "*";
765            break;
766          default:
767            dbgs() << "=%reg" << PhysRegState[Reg];
768            if (LiveVirtRegs[PhysRegState[Reg]].Dirty)
769              dbgs() << "*";
770            assert(LiveVirtRegs[PhysRegState[Reg]].PhysReg == Reg &&
771                   "Bad inverse map");
772            break;
773          }
774        }
775        dbgs() << '\n';
776        // Check that LiveVirtRegs is the inverse.
777        for (LiveRegMap::iterator i = LiveVirtRegs.begin(),
778             e = LiveVirtRegs.end(); i != e; ++i) {
779           assert(TargetRegisterInfo::isVirtualRegister(i->first) &&
780                  "Bad map key");
781           assert(TargetRegisterInfo::isPhysicalRegister(i->second.PhysReg) &&
782                  "Bad map value");
783           assert(PhysRegState[i->second.PhysReg] == i->first &&
784                  "Bad inverse map");
785        }
786      });
787
788    // Debug values are not allowed to change codegen in any way.
789    if (MI->isDebugValue()) {
790      bool ScanDbgValue = true;
791      while (ScanDbgValue) {
792        ScanDbgValue = false;
793        for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
794          MachineOperand &MO = MI->getOperand(i);
795          if (!MO.isReg()) continue;
796          unsigned Reg = MO.getReg();
797          if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
798          LiveDbgValueMap[Reg] = MI;
799          LiveRegMap::iterator LRI = LiveVirtRegs.find(Reg);
800          if (LRI != LiveVirtRegs.end())
801            setPhysReg(MI, i, LRI->second.PhysReg);
802          else {
803            int SS = StackSlotForVirtReg[Reg];
804            if (SS == -1) {
805              // We can't allocate a physreg for a DebugValue, sorry!
806              DEBUG(dbgs() << "Unable to allocate vreg used by DBG_VALUE");
807              MO.setReg(0);
808            }
809            else {
810              // Modify DBG_VALUE now that the value is in a spill slot.
811              int64_t Offset = MI->getOperand(1).getImm();
812              const MDNode *MDPtr =
813                MI->getOperand(MI->getNumOperands()-1).getMetadata();
814              DebugLoc DL = MI->getDebugLoc();
815              if (MachineInstr *NewDV =
816                  TII->emitFrameIndexDebugValue(*MF, SS, Offset, MDPtr, DL)) {
817                DEBUG(dbgs() << "Modifying debug info due to spill:" <<
818                      "\t" << *MI);
819                MachineBasicBlock *MBB = MI->getParent();
820                MBB->insert(MBB->erase(MI), NewDV);
821                // Scan NewDV operands from the beginning.
822                MI = NewDV;
823                ScanDbgValue = true;
824                break;
825              } else {
826                // We can't allocate a physreg for a DebugValue; sorry!
827                DEBUG(dbgs() << "Unable to allocate vreg used by DBG_VALUE");
828                MO.setReg(0);
829              }
830            }
831          }
832        }
833      }
834      // Next instruction.
835      continue;
836    }
837
838    // If this is a copy, we may be able to coalesce.
839    unsigned CopySrc = 0, CopyDst = 0, CopySrcSub = 0, CopyDstSub = 0;
840    if (MI->isCopy()) {
841      CopyDst = MI->getOperand(0).getReg();
842      CopySrc = MI->getOperand(1).getReg();
843      CopyDstSub = MI->getOperand(0).getSubReg();
844      CopySrcSub = MI->getOperand(1).getSubReg();
845    }
846
847    // Track registers used by instruction.
848    UsedInInstr.reset();
849
850    // First scan.
851    // Mark physreg uses and early clobbers as used.
852    // Find the end of the virtreg operands
853    unsigned VirtOpEnd = 0;
854    bool hasTiedOps = false;
855    bool hasEarlyClobbers = false;
856    bool hasPartialRedefs = false;
857    bool hasPhysDefs = false;
858    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
859      MachineOperand &MO = MI->getOperand(i);
860      if (!MO.isReg()) continue;
861      unsigned Reg = MO.getReg();
862      if (!Reg) continue;
863      if (TargetRegisterInfo::isVirtualRegister(Reg)) {
864        VirtOpEnd = i+1;
865        if (MO.isUse()) {
866          hasTiedOps = hasTiedOps ||
867                                TID.getOperandConstraint(i, TOI::TIED_TO) != -1;
868        } else {
869          if (MO.isEarlyClobber())
870            hasEarlyClobbers = true;
871          if (MO.getSubReg() && MI->readsVirtualRegister(Reg))
872            hasPartialRedefs = true;
873        }
874        continue;
875      }
876      if (!Allocatable.test(Reg)) continue;
877      if (MO.isUse()) {
878        usePhysReg(MO);
879      } else if (MO.isEarlyClobber()) {
880        definePhysReg(MI, Reg, (MO.isImplicit() || MO.isDead()) ?
881                               regFree : regReserved);
882        hasEarlyClobbers = true;
883      } else
884        hasPhysDefs = true;
885    }
886
887    // The instruction may have virtual register operands that must be allocated
888    // the same register at use-time and def-time: early clobbers and tied
889    // operands. If there are also physical defs, these registers must avoid
890    // both physical defs and uses, making them more constrained than normal
891    // operands.
892    // Similarly, if there are multiple defs and tied operands, we must make
893    // sure the same register is allocated to uses and defs.
894    // We didn't detect inline asm tied operands above, so just make this extra
895    // pass for all inline asm.
896    if (MI->isInlineAsm() || hasEarlyClobbers || hasPartialRedefs ||
897        (hasTiedOps && (hasPhysDefs || TID.getNumDefs() > 1))) {
898      handleThroughOperands(MI, VirtDead);
899      // Don't attempt coalescing when we have funny stuff going on.
900      CopyDst = 0;
901      // Pretend we have early clobbers so the use operands get marked below.
902      // This is not necessary for the common case of a single tied use.
903      hasEarlyClobbers = true;
904    }
905
906    // Second scan.
907    // Allocate virtreg uses.
908    for (unsigned i = 0; i != VirtOpEnd; ++i) {
909      MachineOperand &MO = MI->getOperand(i);
910      if (!MO.isReg()) continue;
911      unsigned Reg = MO.getReg();
912      if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
913      if (MO.isUse()) {
914        LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, CopyDst);
915        unsigned PhysReg = LRI->second.PhysReg;
916        CopySrc = (CopySrc == Reg || CopySrc == PhysReg) ? PhysReg : 0;
917        if (setPhysReg(MI, i, PhysReg))
918          killVirtReg(LRI);
919      }
920    }
921
922    MRI->addPhysRegsUsed(UsedInInstr);
923
924    // Track registers defined by instruction - early clobbers and tied uses at
925    // this point.
926    UsedInInstr.reset();
927    if (hasEarlyClobbers) {
928      for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
929        MachineOperand &MO = MI->getOperand(i);
930        if (!MO.isReg()) continue;
931        unsigned Reg = MO.getReg();
932        if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
933        // Look for physreg defs and tied uses.
934        if (!MO.isDef() && !MI->isRegTiedToDefOperand(i)) continue;
935        UsedInInstr.set(Reg);
936        for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS)
937          UsedInInstr.set(*AS);
938      }
939    }
940
941    unsigned DefOpEnd = MI->getNumOperands();
942    if (TID.isCall()) {
943      // Spill all virtregs before a call. This serves two purposes: 1. If an
944      // exception is thrown, the landing pad is going to expect to find
945      // registers in their spill slots, and 2. we don't have to wade through
946      // all the <imp-def> operands on the call instruction.
947      DefOpEnd = VirtOpEnd;
948      DEBUG(dbgs() << "  Spilling remaining registers before call.\n");
949      spillAll(MI);
950
951      // The imp-defs are skipped below, but we still need to mark those
952      // registers as used by the function.
953      SkippedInstrs.insert(&TID);
954    }
955
956    // Third scan.
957    // Allocate defs and collect dead defs.
958    for (unsigned i = 0; i != DefOpEnd; ++i) {
959      MachineOperand &MO = MI->getOperand(i);
960      if (!MO.isReg() || !MO.isDef() || !MO.getReg() || MO.isEarlyClobber())
961        continue;
962      unsigned Reg = MO.getReg();
963
964      if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
965        if (!Allocatable.test(Reg)) continue;
966        definePhysReg(MI, Reg, (MO.isImplicit() || MO.isDead()) ?
967                               regFree : regReserved);
968        continue;
969      }
970      LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, CopySrc);
971      unsigned PhysReg = LRI->second.PhysReg;
972      if (setPhysReg(MI, i, PhysReg)) {
973        VirtDead.push_back(Reg);
974        CopyDst = 0; // cancel coalescing;
975      } else
976        CopyDst = (CopyDst == Reg || CopyDst == PhysReg) ? PhysReg : 0;
977    }
978
979    // Kill dead defs after the scan to ensure that multiple defs of the same
980    // register are allocated identically. We didn't need to do this for uses
981    // because we are crerating our own kill flags, and they are always at the
982    // last use.
983    for (unsigned i = 0, e = VirtDead.size(); i != e; ++i)
984      killVirtReg(VirtDead[i]);
985    VirtDead.clear();
986
987    MRI->addPhysRegsUsed(UsedInInstr);
988
989    if (CopyDst && CopyDst == CopySrc && CopyDstSub == CopySrcSub) {
990      DEBUG(dbgs() << "-- coalescing: " << *MI);
991      Coalesced.push_back(MI);
992    } else {
993      DEBUG(dbgs() << "<< " << *MI);
994    }
995  }
996
997  // Spill all physical registers holding virtual registers now.
998  DEBUG(dbgs() << "Spilling live registers at end of block.\n");
999  spillAll(MBB->getFirstTerminator());
1000
1001  // Erase all the coalesced copies. We are delaying it until now because
1002  // LiveVirtRegs might refer to the instrs.
1003  for (unsigned i = 0, e = Coalesced.size(); i != e; ++i)
1004    MBB->erase(Coalesced[i]);
1005  NumCopies += Coalesced.size();
1006
1007  DEBUG(MBB->dump());
1008}
1009
1010/// runOnMachineFunction - Register allocate the whole function
1011///
1012bool RAFast::runOnMachineFunction(MachineFunction &Fn) {
1013  DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n"
1014               << "********** Function: "
1015               << ((Value*)Fn.getFunction())->getName() << '\n');
1016  MF = &Fn;
1017  MRI = &MF->getRegInfo();
1018  TM = &Fn.getTarget();
1019  TRI = TM->getRegisterInfo();
1020  TII = TM->getInstrInfo();
1021
1022  UsedInInstr.resize(TRI->getNumRegs());
1023  Allocatable = TRI->getAllocatableSet(*MF);
1024
1025  // initialize the virtual->physical register map to have a 'null'
1026  // mapping for all virtual registers
1027  unsigned LastVirtReg = MRI->getLastVirtReg();
1028  StackSlotForVirtReg.grow(LastVirtReg);
1029
1030  // Loop over all of the basic blocks, eliminating virtual register references
1031  for (MachineFunction::iterator MBBi = Fn.begin(), MBBe = Fn.end();
1032       MBBi != MBBe; ++MBBi) {
1033    MBB = &*MBBi;
1034    AllocateBasicBlock();
1035  }
1036
1037  // Make sure the set of used physregs is closed under subreg operations.
1038  MRI->closePhysRegsUsed(*TRI);
1039
1040  // Add the clobber lists for all the instructions we skipped earlier.
1041  for (SmallPtrSet<const TargetInstrDesc*, 4>::const_iterator
1042       I = SkippedInstrs.begin(), E = SkippedInstrs.end(); I != E; ++I)
1043    if (const unsigned *Defs = (*I)->getImplicitDefs())
1044      while (*Defs)
1045        MRI->setPhysRegUsed(*Defs++);
1046
1047  SkippedInstrs.clear();
1048  StackSlotForVirtReg.clear();
1049  LiveDbgValueMap.clear();
1050  return true;
1051}
1052
1053FunctionPass *llvm::createFastRegisterAllocator() {
1054  return new RAFast();
1055}
1056