RegAllocFast.cpp revision 8e98de9979fa08dac650bc6ae884e809da2cfdaa 
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 " << PrintReg(LRI->first, TRI)
266                 << " in " << PrintReg(LR.PhysReg, TRI));
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 the 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    DEBUG(dbgs() << "PhysReg: " << PhysReg << " is already used in instr.\n");
425    return spillImpossible;
426  }
427  switch (unsigned VirtReg = PhysRegState[PhysReg]) {
428  case regDisabled:
429    break;
430  case regFree:
431    return 0;
432  case regReserved:
433    DEBUG(dbgs() << "VirtReg: " << VirtReg << " corresponding to PhysReg: "
434          << PhysReg << " is reserved already.\n");
435    return spillImpossible;
436  default:
437    return LiveVirtRegs.lookup(VirtReg).Dirty ? spillDirty : spillClean;
438  }
439
440  // This is a disabled register, add up cost of aliases.
441  DEBUG(dbgs() << "\tRegister: " << PhysReg << " is disabled.\n");
442  unsigned Cost = 0;
443  for (const unsigned *AS = TRI->getAliasSet(PhysReg);
444       unsigned Alias = *AS; ++AS) {
445    switch (unsigned VirtReg = PhysRegState[Alias]) {
446    case regDisabled:
447      break;
448    case regFree:
449      ++Cost;
450      break;
451    case regReserved:
452      return spillImpossible;
453    default:
454      Cost += LiveVirtRegs.lookup(VirtReg).Dirty ? spillDirty : spillClean;
455      break;
456    }
457  }
458  return Cost;
459}
460
461
462/// assignVirtToPhysReg - This method updates local state so that we know
463/// that PhysReg is the proper container for VirtReg now.  The physical
464/// register must not be used for anything else when this is called.
465///
466void RAFast::assignVirtToPhysReg(LiveRegEntry &LRE, unsigned PhysReg) {
467  DEBUG(dbgs() << "Assigning " << PrintReg(LRE.first, TRI) << " to "
468               << PrintReg(PhysReg, TRI) << "\n");
469  PhysRegState[PhysReg] = LRE.first;
470  assert(!LRE.second.PhysReg && "Already assigned a physreg");
471  LRE.second.PhysReg = PhysReg;
472}
473
474/// allocVirtReg - Allocate a physical register for VirtReg.
475void RAFast::allocVirtReg(MachineInstr *MI, LiveRegEntry &LRE, unsigned Hint) {
476  const unsigned VirtReg = LRE.first;
477
478  assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
479         "Can only allocate virtual registers");
480
481  const TargetRegisterClass *RC = MRI->getRegClass(VirtReg);
482
483  // Ignore invalid hints.
484  if (Hint && (!TargetRegisterInfo::isPhysicalRegister(Hint) ||
485               !RC->contains(Hint) || !Allocatable.test(Hint)))
486    Hint = 0;
487
488  // Take hint when possible.
489  if (Hint) {
490    switch(calcSpillCost(Hint)) {
491    default:
492      definePhysReg(MI, Hint, regFree);
493      // Fall through.
494    case 0:
495      return assignVirtToPhysReg(LRE, Hint);
496    case spillImpossible:
497      break;
498    }
499  }
500
501  TargetRegisterClass::iterator AOB = RC->allocation_order_begin(*MF);
502  TargetRegisterClass::iterator AOE = RC->allocation_order_end(*MF);
503
504  // First try to find a completely free register.
505  for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) {
506    unsigned PhysReg = *I;
507    if (PhysRegState[PhysReg] == regFree && !UsedInInstr.test(PhysReg) &&
508        Allocatable.test(PhysReg))
509      return assignVirtToPhysReg(LRE, PhysReg);
510  }
511
512  DEBUG(dbgs() << "Allocating " << PrintReg(VirtReg) << " from "
513               << RC->getName() << "\n");
514
515  unsigned BestReg = 0, BestCost = spillImpossible;
516  for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) {
517    if (!Allocatable.test(*I)) {
518      DEBUG(dbgs() << "\tRegister " << *I << " is not allocatable.\n");
519      continue;
520    }
521    unsigned Cost = calcSpillCost(*I);
522    DEBUG(dbgs() << "\tRegister: " << *I << "\n");
523    DEBUG(dbgs() << "\tCost: " << Cost << "\n");
524    DEBUG(dbgs() << "\tBestCost: " << BestCost << "\n");
525    // Cost is 0 when all aliases are already disabled.
526    if (Cost == 0)
527      return assignVirtToPhysReg(LRE, *I);
528    if (Cost < BestCost)
529      BestReg = *I, BestCost = Cost;
530  }
531
532  if (BestReg) {
533    definePhysReg(MI, BestReg, regFree);
534    return assignVirtToPhysReg(LRE, BestReg);
535  }
536
537  // Nothing we can do.
538  std::string msg;
539  raw_string_ostream Msg(msg);
540  Msg << "Ran out of registers during register allocation!";
541  if (MI->isInlineAsm()) {
542    Msg << "\nPlease check your inline asm statement for "
543        << "invalid constraints:\n";
544    MI->print(Msg, TM);
545  }
546  report_fatal_error(Msg.str());
547}
548
549/// defineVirtReg - Allocate a register for VirtReg and mark it as dirty.
550RAFast::LiveRegMap::iterator
551RAFast::defineVirtReg(MachineInstr *MI, unsigned OpNum,
552                      unsigned VirtReg, unsigned Hint) {
553  assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
554         "Not a virtual register");
555  LiveRegMap::iterator LRI;
556  bool New;
557  tie(LRI, New) = LiveVirtRegs.insert(std::make_pair(VirtReg, LiveReg()));
558  LiveReg &LR = LRI->second;
559  if (New) {
560    // If there is no hint, peek at the only use of this register.
561    if ((!Hint || !TargetRegisterInfo::isPhysicalRegister(Hint)) &&
562        MRI->hasOneNonDBGUse(VirtReg)) {
563      const MachineInstr &UseMI = *MRI->use_nodbg_begin(VirtReg);
564      // It's a copy, use the destination register as a hint.
565      if (UseMI.isCopyLike())
566        Hint = UseMI.getOperand(0).getReg();
567    }
568    allocVirtReg(MI, *LRI, Hint);
569  } else if (LR.LastUse) {
570    // Redefining a live register - kill at the last use, unless it is this
571    // instruction defining VirtReg multiple times.
572    if (LR.LastUse != MI || LR.LastUse->getOperand(LR.LastOpNum).isUse())
573      addKillFlag(LR);
574  }
575  assert(LR.PhysReg && "Register not assigned");
576  LR.LastUse = MI;
577  LR.LastOpNum = OpNum;
578  LR.Dirty = true;
579  UsedInInstr.set(LR.PhysReg);
580  return LRI;
581}
582
583/// reloadVirtReg - Make sure VirtReg is available in a physreg and return it.
584RAFast::LiveRegMap::iterator
585RAFast::reloadVirtReg(MachineInstr *MI, unsigned OpNum,
586                      unsigned VirtReg, unsigned Hint) {
587  assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
588         "Not a virtual register");
589  LiveRegMap::iterator LRI;
590  bool New;
591  tie(LRI, New) = LiveVirtRegs.insert(std::make_pair(VirtReg, LiveReg()));
592  LiveReg &LR = LRI->second;
593  MachineOperand &MO = MI->getOperand(OpNum);
594  if (New) {
595    allocVirtReg(MI, *LRI, Hint);
596    const TargetRegisterClass *RC = MRI->getRegClass(VirtReg);
597    int FrameIndex = getStackSpaceFor(VirtReg, RC);
598    DEBUG(dbgs() << "Reloading " << PrintReg(VirtReg, TRI) << " into "
599                 << PrintReg(LR.PhysReg, TRI) << "\n");
600    TII->loadRegFromStackSlot(*MBB, MI, LR.PhysReg, FrameIndex, RC, TRI);
601    ++NumLoads;
602  } else if (LR.Dirty) {
603    if (isLastUseOfLocalReg(MO)) {
604      DEBUG(dbgs() << "Killing last use: " << MO << "\n");
605      if (MO.isUse())
606        MO.setIsKill();
607      else
608        MO.setIsDead();
609    } else if (MO.isKill()) {
610      DEBUG(dbgs() << "Clearing dubious kill: " << MO << "\n");
611      MO.setIsKill(false);
612    } else if (MO.isDead()) {
613      DEBUG(dbgs() << "Clearing dubious dead: " << MO << "\n");
614      MO.setIsDead(false);
615    }
616  } else if (MO.isKill()) {
617    // We must remove kill flags from uses of reloaded registers because the
618    // register would be killed immediately, and there might be a second use:
619    //   %foo = OR %x<kill>, %x
620    // This would cause a second reload of %x into a different register.
621    DEBUG(dbgs() << "Clearing clean kill: " << MO << "\n");
622    MO.setIsKill(false);
623  } else if (MO.isDead()) {
624    DEBUG(dbgs() << "Clearing clean dead: " << MO << "\n");
625    MO.setIsDead(false);
626  }
627  assert(LR.PhysReg && "Register not assigned");
628  LR.LastUse = MI;
629  LR.LastOpNum = OpNum;
630  UsedInInstr.set(LR.PhysReg);
631  return LRI;
632}
633
634// setPhysReg - Change operand OpNum in MI the refer the PhysReg, considering
635// subregs. This may invalidate any operand pointers.
636// Return true if the operand kills its register.
637bool RAFast::setPhysReg(MachineInstr *MI, unsigned OpNum, unsigned PhysReg) {
638  MachineOperand &MO = MI->getOperand(OpNum);
639  if (!MO.getSubReg()) {
640    MO.setReg(PhysReg);
641    return MO.isKill() || MO.isDead();
642  }
643
644  // Handle subregister index.
645  MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, MO.getSubReg()) : 0);
646  MO.setSubReg(0);
647
648  // A kill flag implies killing the full register. Add corresponding super
649  // register kill.
650  if (MO.isKill()) {
651    MI->addRegisterKilled(PhysReg, TRI, true);
652    return true;
653  }
654  return MO.isDead();
655}
656
657// Handle special instruction operand like early clobbers and tied ops when
658// there are additional physreg defines.
659void RAFast::handleThroughOperands(MachineInstr *MI,
660                                   SmallVectorImpl<unsigned> &VirtDead) {
661  DEBUG(dbgs() << "Scanning for through registers:");
662  SmallSet<unsigned, 8> ThroughRegs;
663  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
664    MachineOperand &MO = MI->getOperand(i);
665    if (!MO.isReg()) continue;
666    unsigned Reg = MO.getReg();
667    if (!TargetRegisterInfo::isVirtualRegister(Reg))
668      continue;
669    if (MO.isEarlyClobber() || MI->isRegTiedToDefOperand(i) ||
670        (MO.getSubReg() && MI->readsVirtualRegister(Reg))) {
671      if (ThroughRegs.insert(Reg))
672        DEBUG(dbgs() << ' ' << PrintReg(Reg));
673    }
674  }
675
676  // If any physreg defines collide with preallocated through registers,
677  // we must spill and reallocate.
678  DEBUG(dbgs() << "\nChecking for physdef collisions.\n");
679  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
680    MachineOperand &MO = MI->getOperand(i);
681    if (!MO.isReg() || !MO.isDef()) continue;
682    unsigned Reg = MO.getReg();
683    if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
684    UsedInInstr.set(Reg);
685    if (ThroughRegs.count(PhysRegState[Reg]))
686      definePhysReg(MI, Reg, regFree);
687    for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
688      UsedInInstr.set(*AS);
689      if (ThroughRegs.count(PhysRegState[*AS]))
690        definePhysReg(MI, *AS, regFree);
691    }
692  }
693
694  SmallVector<unsigned, 8> PartialDefs;
695  DEBUG(dbgs() << "Allocating tied uses and early clobbers.\n");
696  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
697    MachineOperand &MO = MI->getOperand(i);
698    if (!MO.isReg()) continue;
699    unsigned Reg = MO.getReg();
700    if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue;
701    if (MO.isUse()) {
702      unsigned DefIdx = 0;
703      if (!MI->isRegTiedToDefOperand(i, &DefIdx)) continue;
704      DEBUG(dbgs() << "Operand " << i << "("<< MO << ") is tied to operand "
705        << DefIdx << ".\n");
706      LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, 0);
707      unsigned PhysReg = LRI->second.PhysReg;
708      setPhysReg(MI, i, PhysReg);
709      // Note: we don't update the def operand yet. That would cause the normal
710      // def-scan to attempt spilling.
711    } else if (MO.getSubReg() && MI->readsVirtualRegister(Reg)) {
712      DEBUG(dbgs() << "Partial redefine: " << MO << "\n");
713      // Reload the register, but don't assign to the operand just yet.
714      // That would confuse the later phys-def processing pass.
715      LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, 0);
716      PartialDefs.push_back(LRI->second.PhysReg);
717    } else if (MO.isEarlyClobber()) {
718      // Note: defineVirtReg may invalidate MO.
719      LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, 0);
720      unsigned PhysReg = LRI->second.PhysReg;
721      if (setPhysReg(MI, i, PhysReg))
722        VirtDead.push_back(Reg);
723    }
724  }
725
726  // Restore UsedInInstr to a state usable for allocating normal virtual uses.
727  UsedInInstr.reset();
728  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
729    MachineOperand &MO = MI->getOperand(i);
730    if (!MO.isReg() || (MO.isDef() && !MO.isEarlyClobber())) continue;
731    unsigned Reg = MO.getReg();
732    if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
733    DEBUG(dbgs() << "\tSetting reg " << Reg << " as used in instr\n");
734    UsedInInstr.set(Reg);
735    for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
736      DEBUG(dbgs() << "\tSetting alias reg " << *AS << " as used in instr\n");
737      UsedInInstr.set(*AS);
738    }
739  }
740
741  // Also mark PartialDefs as used to avoid reallocation.
742  for (unsigned i = 0, e = PartialDefs.size(); i != e; ++i)
743    UsedInInstr.set(PartialDefs[i]);
744}
745
746void RAFast::AllocateBasicBlock() {
747  DEBUG(dbgs() << "\nAllocating " << *MBB);
748
749  // FIXME: This should probably be added by instruction selection instead?
750  // If the last instruction in the block is a return, make sure to mark it as
751  // using all of the live-out values in the function.  Things marked both call
752  // and return are tail calls; do not do this for them.  The tail callee need
753  // not take the same registers as input that it produces as output, and there
754  // are dependencies for its input registers elsewhere.
755  if (!MBB->empty() && MBB->back().getDesc().isReturn() &&
756      !MBB->back().getDesc().isCall()) {
757    MachineInstr *Ret = &MBB->back();
758
759    for (MachineRegisterInfo::liveout_iterator
760         I = MF->getRegInfo().liveout_begin(),
761         E = MF->getRegInfo().liveout_end(); I != E; ++I) {
762      assert(TargetRegisterInfo::isPhysicalRegister(*I) &&
763             "Cannot have a live-out virtual register.");
764
765      // Add live-out registers as implicit uses.
766      Ret->addRegisterKilled(*I, TRI, true);
767    }
768  }
769
770  PhysRegState.assign(TRI->getNumRegs(), regDisabled);
771  assert(LiveVirtRegs.empty() && "Mapping not cleared form last block?");
772
773  MachineBasicBlock::iterator MII = MBB->begin();
774
775  // Add live-in registers as live.
776  for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
777         E = MBB->livein_end(); I != E; ++I)
778    if (Allocatable.test(*I))
779      definePhysReg(MII, *I, regReserved);
780
781  SmallVector<unsigned, 8> VirtDead;
782  SmallVector<MachineInstr*, 32> Coalesced;
783
784  // Otherwise, sequentially allocate each instruction in the MBB.
785  while (MII != MBB->end()) {
786    MachineInstr *MI = MII++;
787    const TargetInstrDesc &TID = MI->getDesc();
788    DEBUG({
789        dbgs() << "\n>> " << *MI << "Regs:";
790        for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) {
791          if (PhysRegState[Reg] == regDisabled) continue;
792          dbgs() << " " << TRI->getName(Reg);
793          switch(PhysRegState[Reg]) {
794          case regFree:
795            break;
796          case regReserved:
797            dbgs() << "*";
798            break;
799          default:
800            dbgs() << '=' << PrintReg(PhysRegState[Reg]);
801            if (LiveVirtRegs[PhysRegState[Reg]].Dirty)
802              dbgs() << "*";
803            assert(LiveVirtRegs[PhysRegState[Reg]].PhysReg == Reg &&
804                   "Bad inverse map");
805            break;
806          }
807        }
808        dbgs() << '\n';
809        // Check that LiveVirtRegs is the inverse.
810        for (LiveRegMap::iterator i = LiveVirtRegs.begin(),
811             e = LiveVirtRegs.end(); i != e; ++i) {
812           assert(TargetRegisterInfo::isVirtualRegister(i->first) &&
813                  "Bad map key");
814           assert(TargetRegisterInfo::isPhysicalRegister(i->second.PhysReg) &&
815                  "Bad map value");
816           assert(PhysRegState[i->second.PhysReg] == i->first &&
817                  "Bad inverse map");
818        }
819      });
820
821    // Debug values are not allowed to change codegen in any way.
822    if (MI->isDebugValue()) {
823      bool ScanDbgValue = true;
824      while (ScanDbgValue) {
825        ScanDbgValue = false;
826        for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
827          MachineOperand &MO = MI->getOperand(i);
828          if (!MO.isReg()) continue;
829          unsigned Reg = MO.getReg();
830          if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue;
831          LiveDbgValueMap[Reg] = MI;
832          LiveRegMap::iterator LRI = LiveVirtRegs.find(Reg);
833          if (LRI != LiveVirtRegs.end())
834            setPhysReg(MI, i, LRI->second.PhysReg);
835          else {
836            int SS = StackSlotForVirtReg[Reg];
837            if (SS == -1) {
838              // We can't allocate a physreg for a DebugValue, sorry!
839              DEBUG(dbgs() << "Unable to allocate vreg used by DBG_VALUE");
840              MO.setReg(0);
841            }
842            else {
843              // Modify DBG_VALUE now that the value is in a spill slot.
844              int64_t Offset = MI->getOperand(1).getImm();
845              const MDNode *MDPtr =
846                MI->getOperand(MI->getNumOperands()-1).getMetadata();
847              DebugLoc DL = MI->getDebugLoc();
848              if (MachineInstr *NewDV =
849                  TII->emitFrameIndexDebugValue(*MF, SS, Offset, MDPtr, DL)) {
850                DEBUG(dbgs() << "Modifying debug info due to spill:" <<
851                      "\t" << *MI);
852                MachineBasicBlock *MBB = MI->getParent();
853                MBB->insert(MBB->erase(MI), NewDV);
854                // Scan NewDV operands from the beginning.
855                MI = NewDV;
856                ScanDbgValue = true;
857                break;
858              } else {
859                // We can't allocate a physreg for a DebugValue; sorry!
860                DEBUG(dbgs() << "Unable to allocate vreg used by DBG_VALUE");
861                MO.setReg(0);
862              }
863            }
864          }
865        }
866      }
867      // Next instruction.
868      continue;
869    }
870
871    // If this is a copy, we may be able to coalesce.
872    unsigned CopySrc = 0, CopyDst = 0, CopySrcSub = 0, CopyDstSub = 0;
873    if (MI->isCopy()) {
874      CopyDst = MI->getOperand(0).getReg();
875      CopySrc = MI->getOperand(1).getReg();
876      CopyDstSub = MI->getOperand(0).getSubReg();
877      CopySrcSub = MI->getOperand(1).getSubReg();
878    }
879
880    // Track registers used by instruction.
881    UsedInInstr.reset();
882
883    // First scan.
884    // Mark physreg uses and early clobbers as used.
885    // Find the end of the virtreg operands
886    unsigned VirtOpEnd = 0;
887    bool hasTiedOps = false;
888    bool hasEarlyClobbers = false;
889    bool hasPartialRedefs = false;
890    bool hasPhysDefs = false;
891    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
892      MachineOperand &MO = MI->getOperand(i);
893      if (!MO.isReg()) continue;
894      unsigned Reg = MO.getReg();
895      if (!Reg) continue;
896      if (TargetRegisterInfo::isVirtualRegister(Reg)) {
897        VirtOpEnd = i+1;
898        if (MO.isUse()) {
899          hasTiedOps = hasTiedOps ||
900                                TID.getOperandConstraint(i, TOI::TIED_TO) != -1;
901        } else {
902          if (MO.isEarlyClobber())
903            hasEarlyClobbers = true;
904          if (MO.getSubReg() && MI->readsVirtualRegister(Reg))
905            hasPartialRedefs = true;
906        }
907        continue;
908      }
909      if (!Allocatable.test(Reg)) continue;
910      if (MO.isUse()) {
911        usePhysReg(MO);
912      } else if (MO.isEarlyClobber()) {
913        definePhysReg(MI, Reg, (MO.isImplicit() || MO.isDead()) ?
914                               regFree : regReserved);
915        hasEarlyClobbers = true;
916      } else
917        hasPhysDefs = true;
918    }
919
920    // The instruction may have virtual register operands that must be allocated
921    // the same register at use-time and def-time: early clobbers and tied
922    // operands. If there are also physical defs, these registers must avoid
923    // both physical defs and uses, making them more constrained than normal
924    // operands.
925    // Similarly, if there are multiple defs and tied operands, we must make
926    // sure the same register is allocated to uses and defs.
927    // We didn't detect inline asm tied operands above, so just make this extra
928    // pass for all inline asm.
929    if (MI->isInlineAsm() || hasEarlyClobbers || hasPartialRedefs ||
930        (hasTiedOps && (hasPhysDefs || TID.getNumDefs() > 1))) {
931      handleThroughOperands(MI, VirtDead);
932      // Don't attempt coalescing when we have funny stuff going on.
933      CopyDst = 0;
934      // Pretend we have early clobbers so the use operands get marked below.
935      // This is not necessary for the common case of a single tied use.
936      hasEarlyClobbers = true;
937    }
938
939    // Second scan.
940    // Allocate virtreg uses.
941    for (unsigned i = 0; i != VirtOpEnd; ++i) {
942      MachineOperand &MO = MI->getOperand(i);
943      if (!MO.isReg()) continue;
944      unsigned Reg = MO.getReg();
945      if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue;
946      if (MO.isUse()) {
947        LiveRegMap::iterator LRI = reloadVirtReg(MI, i, Reg, CopyDst);
948        unsigned PhysReg = LRI->second.PhysReg;
949        CopySrc = (CopySrc == Reg || CopySrc == PhysReg) ? PhysReg : 0;
950        if (setPhysReg(MI, i, PhysReg))
951          killVirtReg(LRI);
952      }
953    }
954
955    MRI->addPhysRegsUsed(UsedInInstr);
956
957    // Track registers defined by instruction - early clobbers and tied uses at
958    // this point.
959    UsedInInstr.reset();
960    if (hasEarlyClobbers) {
961      for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
962        MachineOperand &MO = MI->getOperand(i);
963        if (!MO.isReg()) continue;
964        unsigned Reg = MO.getReg();
965        if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue;
966        // Look for physreg defs and tied uses.
967        if (!MO.isDef() && !MI->isRegTiedToDefOperand(i)) continue;
968        UsedInInstr.set(Reg);
969        for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS)
970          UsedInInstr.set(*AS);
971      }
972    }
973
974    unsigned DefOpEnd = MI->getNumOperands();
975    if (TID.isCall()) {
976      // Spill all virtregs before a call. This serves two purposes: 1. If an
977      // exception is thrown, the landing pad is going to expect to find
978      // registers in their spill slots, and 2. we don't have to wade through
979      // all the <imp-def> operands on the call instruction.
980      DefOpEnd = VirtOpEnd;
981      DEBUG(dbgs() << "  Spilling remaining registers before call.\n");
982      spillAll(MI);
983
984      // The imp-defs are skipped below, but we still need to mark those
985      // registers as used by the function.
986      SkippedInstrs.insert(&TID);
987    }
988
989    // Third scan.
990    // Allocate defs and collect dead defs.
991    for (unsigned i = 0; i != DefOpEnd; ++i) {
992      MachineOperand &MO = MI->getOperand(i);
993      if (!MO.isReg() || !MO.isDef() || !MO.getReg() || MO.isEarlyClobber())
994        continue;
995      unsigned Reg = MO.getReg();
996
997      if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
998        if (!Allocatable.test(Reg)) continue;
999        definePhysReg(MI, Reg, (MO.isImplicit() || MO.isDead()) ?
1000                               regFree : regReserved);
1001        continue;
1002      }
1003      LiveRegMap::iterator LRI = defineVirtReg(MI, i, Reg, CopySrc);
1004      unsigned PhysReg = LRI->second.PhysReg;
1005      if (setPhysReg(MI, i, PhysReg)) {
1006        VirtDead.push_back(Reg);
1007        CopyDst = 0; // cancel coalescing;
1008      } else
1009        CopyDst = (CopyDst == Reg || CopyDst == PhysReg) ? PhysReg : 0;
1010    }
1011
1012    // Kill dead defs after the scan to ensure that multiple defs of the same
1013    // register are allocated identically. We didn't need to do this for uses
1014    // because we are crerating our own kill flags, and they are always at the
1015    // last use.
1016    for (unsigned i = 0, e = VirtDead.size(); i != e; ++i)
1017      killVirtReg(VirtDead[i]);
1018    VirtDead.clear();
1019
1020    MRI->addPhysRegsUsed(UsedInInstr);
1021
1022    if (CopyDst && CopyDst == CopySrc && CopyDstSub == CopySrcSub) {
1023      DEBUG(dbgs() << "-- coalescing: " << *MI);
1024      Coalesced.push_back(MI);
1025    } else {
1026      DEBUG(dbgs() << "<< " << *MI);
1027    }
1028  }
1029
1030  // Spill all physical registers holding virtual registers now.
1031  DEBUG(dbgs() << "Spilling live registers at end of block.\n");
1032  spillAll(MBB->getFirstTerminator());
1033
1034  // Erase all the coalesced copies. We are delaying it until now because
1035  // LiveVirtRegs might refer to the instrs.
1036  for (unsigned i = 0, e = Coalesced.size(); i != e; ++i)
1037    MBB->erase(Coalesced[i]);
1038  NumCopies += Coalesced.size();
1039
1040  DEBUG(MBB->dump());
1041}
1042
1043/// runOnMachineFunction - Register allocate the whole function
1044///
1045bool RAFast::runOnMachineFunction(MachineFunction &Fn) {
1046  DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n"
1047               << "********** Function: "
1048               << ((Value*)Fn.getFunction())->getName() << '\n');
1049  MF = &Fn;
1050  MRI = &MF->getRegInfo();
1051  TM = &Fn.getTarget();
1052  TRI = TM->getRegisterInfo();
1053  TII = TM->getInstrInfo();
1054
1055  UsedInInstr.resize(TRI->getNumRegs());
1056  Allocatable = TRI->getAllocatableSet(*MF);
1057
1058  // initialize the virtual->physical register map to have a 'null'
1059  // mapping for all virtual registers
1060  StackSlotForVirtReg.resize(MRI->getNumVirtRegs());
1061
1062  // Loop over all of the basic blocks, eliminating virtual register references
1063  for (MachineFunction::iterator MBBi = Fn.begin(), MBBe = Fn.end();
1064       MBBi != MBBe; ++MBBi) {
1065    MBB = &*MBBi;
1066    AllocateBasicBlock();
1067  }
1068
1069  // Make sure the set of used physregs is closed under subreg operations.
1070  MRI->closePhysRegsUsed(*TRI);
1071
1072  // Add the clobber lists for all the instructions we skipped earlier.
1073  for (SmallPtrSet<const TargetInstrDesc*, 4>::const_iterator
1074       I = SkippedInstrs.begin(), E = SkippedInstrs.end(); I != E; ++I)
1075    if (const unsigned *Defs = (*I)->getImplicitDefs())
1076      while (*Defs)
1077        MRI->setPhysRegUsed(*Defs++);
1078
1079  SkippedInstrs.clear();
1080  StackSlotForVirtReg.clear();
1081  LiveDbgValueMap.clear();
1082  return true;
1083}
1084
1085FunctionPass *llvm::createFastRegisterAllocator() {
1086  return new RAFast();
1087}
1088