RegAllocBase.cpp revision 216532ac0a7b333e814cc86b7c91358db6a7e819
1//===-- RegAllocBase.cpp - Register Allocator Base Class ------------------===// 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 file defines the RegAllocBase class which provides comon functionality 11// for LiveIntervalUnion-based register allocators. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "regalloc" 16#include "RegAllocBase.h" 17#include "LiveRegMatrix.h" 18#include "Spiller.h" 19#include "VirtRegMap.h" 20#include "llvm/ADT/Statistic.h" 21#include "llvm/CodeGen/LiveIntervalAnalysis.h" 22#include "llvm/CodeGen/LiveRangeEdit.h" 23#include "llvm/CodeGen/MachineInstr.h" 24#include "llvm/CodeGen/MachineRegisterInfo.h" 25#include "llvm/Target/TargetMachine.h" 26#include "llvm/Target/TargetRegisterInfo.h" 27#ifndef NDEBUG 28#include "llvm/ADT/SparseBitVector.h" 29#endif 30#include "llvm/Support/CommandLine.h" 31#include "llvm/Support/Debug.h" 32#include "llvm/Support/ErrorHandling.h" 33#include "llvm/Support/raw_ostream.h" 34#include "llvm/Support/Timer.h" 35 36using namespace llvm; 37 38STATISTIC(NumNewQueued , "Number of new live ranges queued"); 39 40// Temporary verification option until we can put verification inside 41// MachineVerifier. 42static cl::opt<bool, true> 43VerifyRegAlloc("verify-regalloc", cl::location(RegAllocBase::VerifyEnabled), 44 cl::desc("Verify during register allocation")); 45 46const char *RegAllocBase::TimerGroupName = "Register Allocation"; 47bool RegAllocBase::VerifyEnabled = false; 48 49//===----------------------------------------------------------------------===// 50// RegAllocBase Implementation 51//===----------------------------------------------------------------------===// 52 53void RegAllocBase::init(VirtRegMap &vrm, 54 LiveIntervals &lis, 55 LiveRegMatrix &mat) { 56 TRI = &vrm.getTargetRegInfo(); 57 MRI = &vrm.getRegInfo(); 58 VRM = &vrm; 59 LIS = &lis; 60 Matrix = &mat; 61 RegClassInfo.runOnMachineFunction(vrm.getMachineFunction()); 62} 63 64// Visit all the live registers. If they are already assigned to a physical 65// register, unify them with the corresponding LiveIntervalUnion, otherwise push 66// them on the priority queue for later assignment. 67void RegAllocBase::seedLiveRegs() { 68 NamedRegionTimer T("Seed Live Regs", TimerGroupName, TimePassesIsEnabled); 69 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 70 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 71 if (MRI->reg_nodbg_empty(Reg)) 72 continue; 73 enqueue(&LIS->getInterval(Reg)); 74 } 75} 76 77// Top-level driver to manage the queue of unassigned VirtRegs and call the 78// selectOrSplit implementation. 79void RegAllocBase::allocatePhysRegs() { 80 seedLiveRegs(); 81 82 // Continue assigning vregs one at a time to available physical registers. 83 while (LiveInterval *VirtReg = dequeue()) { 84 assert(!VRM->hasPhys(VirtReg->reg) && "Register already assigned"); 85 86 // Unused registers can appear when the spiller coalesces snippets. 87 if (MRI->reg_nodbg_empty(VirtReg->reg)) { 88 DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n'); 89 LIS->removeInterval(VirtReg->reg); 90 continue; 91 } 92 93 // Invalidate all interference queries, live ranges could have changed. 94 Matrix->invalidateVirtRegs(); 95 96 // selectOrSplit requests the allocator to return an available physical 97 // register if possible and populate a list of new live intervals that 98 // result from splitting. 99 DEBUG(dbgs() << "\nselectOrSplit " 100 << MRI->getRegClass(VirtReg->reg)->getName() 101 << ':' << PrintReg(VirtReg->reg) << ' ' << *VirtReg << '\n'); 102 typedef SmallVector<LiveInterval*, 4> VirtRegVec; 103 VirtRegVec SplitVRegs; 104 unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs); 105 106 if (AvailablePhysReg == ~0u) { 107 // selectOrSplit failed to find a register! 108 const char *Msg = "ran out of registers during register allocation"; 109 // Probably caused by an inline asm. 110 MachineInstr *MI; 111 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(VirtReg->reg); 112 (MI = I.skipInstruction());) 113 if (MI->isInlineAsm()) 114 break; 115 if (MI) 116 MI->emitError(Msg); 117 else 118 report_fatal_error(Msg); 119 // Keep going after reporting the error. 120 VRM->assignVirt2Phys(VirtReg->reg, 121 RegClassInfo.getOrder(MRI->getRegClass(VirtReg->reg)).front()); 122 continue; 123 } 124 125 if (AvailablePhysReg) 126 Matrix->assign(*VirtReg, AvailablePhysReg); 127 128 for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end(); 129 I != E; ++I) { 130 LiveInterval *SplitVirtReg = *I; 131 assert(!VRM->hasPhys(SplitVirtReg->reg) && "Register already assigned"); 132 if (MRI->reg_nodbg_empty(SplitVirtReg->reg)) { 133 DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n'); 134 LIS->removeInterval(SplitVirtReg->reg); 135 continue; 136 } 137 DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n"); 138 assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) && 139 "expect split value in virtual register"); 140 enqueue(SplitVirtReg); 141 ++NumNewQueued; 142 } 143 } 144} 145