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