117680Spst//===-- RegAllocBase.cpp - Register Allocator Base Class ------------------===// 239297Sfenner// 317680Spst// The LLVM Compiler Infrastructure 417680Spst// 517680Spst// This file is distributed under the University of Illinois Open Source 617680Spst// License. See LICENSE.TXT for details. 717680Spst// 817680Spst//===----------------------------------------------------------------------===// 917680Spst// 1017680Spst// This file defines the RegAllocBase class which provides comon functionality 1117680Spst// for LiveIntervalUnion-based register allocators. 1217680Spst// 1317680Spst//===----------------------------------------------------------------------===// 1417680Spst 1517680Spst#define DEBUG_TYPE "regalloc" 1617680Spst#include "RegAllocBase.h" 1717680Spst#include "Spiller.h" 1817680Spst#include "llvm/ADT/Statistic.h" 1917680Spst#include "llvm/CodeGen/LiveIntervalAnalysis.h" 2017680Spst#include "llvm/CodeGen/LiveRangeEdit.h" 2117680Spst#include "llvm/CodeGen/LiveRegMatrix.h" 2217680Spst#include "llvm/CodeGen/MachineInstr.h" 2317680Spst#include "llvm/CodeGen/MachineRegisterInfo.h" 2417680Spst#include "llvm/CodeGen/VirtRegMap.h" 25127668Sbms#include "llvm/Target/TargetMachine.h" 26214478Srpaulo#include "llvm/Target/TargetRegisterInfo.h" 2717680Spst#ifndef NDEBUG 2817680Spst#include "llvm/ADT/SparseBitVector.h" 2956893Sfenner#endif 3056893Sfenner#include "llvm/Support/CommandLine.h" 3156893Sfenner#include "llvm/Support/Debug.h" 3256893Sfenner#include "llvm/Support/ErrorHandling.h" 33127668Sbms#include "llvm/Support/raw_ostream.h" 3417680Spst#include "llvm/Support/Timer.h" 3539297Sfenner 3639297Sfennerusing namespace llvm; 3739297Sfenner 3817680SpstSTATISTIC(NumNewQueued , "Number of new live ranges queued"); 3917680Spst 4017680Spst// Temporary verification option until we can put verification inside 4117680Spst// MachineVerifier. 4217680Spststatic cl::opt<bool, true> 4317680SpstVerifyRegAlloc("verify-regalloc", cl::location(RegAllocBase::VerifyEnabled), 44127668Sbms cl::desc("Verify during register allocation")); 45172683Smlaier 4617680Spstconst char *RegAllocBase::TimerGroupName = "Register Allocation"; 4717680Spstbool RegAllocBase::VerifyEnabled = false; 4817680Spst 4917680Spst//===----------------------------------------------------------------------===// 5017680Spst// RegAllocBase Implementation 5117680Spst//===----------------------------------------------------------------------===// 5217680Spst 53190207Srpaulovoid RegAllocBase::init(VirtRegMap &vrm, 54172683Smlaier LiveIntervals &lis, 5517680Spst LiveRegMatrix &mat) { 5617680Spst TRI = &vrm.getTargetRegInfo(); 5717680Spst MRI = &vrm.getRegInfo(); 5817680Spst VRM = &vrm; 5917680Spst LIS = &lis; 6017680Spst Matrix = &mat; 6117680Spst MRI->freezeReservedRegs(vrm.getMachineFunction()); 6217680Spst RegClassInfo.runOnMachineFunction(vrm.getMachineFunction()); 6317680Spst} 6417680Spst 6517680Spst// Visit all the live registers. If they are already assigned to a physical 6617680Spst// register, unify them with the corresponding LiveIntervalUnion, otherwise push 6717680Spst// them on the priority queue for later assignment. 6817680Spstvoid RegAllocBase::seedLiveRegs() { 6917680Spst NamedRegionTimer T("Seed Live Regs", TimerGroupName, TimePassesIsEnabled); 7017680Spst for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 7117680Spst unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 7217680Spst if (MRI->reg_nodbg_empty(Reg)) 7317680Spst continue; 7417680Spst enqueue(&LIS->getInterval(Reg)); 7517680Spst } 7617680Spst} 7717680Spst 7817680Spst// Top-level driver to manage the queue of unassigned VirtRegs and call the 7917680Spst// selectOrSplit implementation. 8017680Spstvoid RegAllocBase::allocatePhysRegs() { 8117680Spst seedLiveRegs(); 8217680Spst 8317680Spst // Continue assigning vregs one at a time to available physical registers. 8417680Spst while (LiveInterval *VirtReg = dequeue()) { 8517680Spst assert(!VRM->hasPhys(VirtReg->reg) && "Register already assigned"); 8617680Spst 8717680Spst // Unused registers can appear when the spiller coalesces snippets. 8817680Spst if (MRI->reg_nodbg_empty(VirtReg->reg)) { 8917680Spst DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n'); 90127668Sbms LIS->removeInterval(VirtReg->reg); 9117680Spst continue; 9217680Spst } 9317680Spst 9417680Spst // Invalidate all interference queries, live ranges could have changed. 9517680Spst Matrix->invalidateVirtRegs(); 9617680Spst 9717680Spst // selectOrSplit requests the allocator to return an available physical 9817680Spst // register if possible and populate a list of new live intervals that 9917680Spst // result from splitting. 10017680Spst DEBUG(dbgs() << "\nselectOrSplit " 101172683Smlaier << MRI->getRegClass(VirtReg->reg)->getName() 10217680Spst << ':' << PrintReg(VirtReg->reg) << ' ' << *VirtReg << '\n'); 103172683Smlaier typedef SmallVector<LiveInterval*, 4> VirtRegVec; 104172683Smlaier VirtRegVec SplitVRegs; 105172683Smlaier unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs); 106172683Smlaier 10717680Spst if (AvailablePhysReg == ~0u) { 108172683Smlaier // selectOrSplit failed to find a register! 109172683Smlaier const char *Msg = "ran out of registers during register allocation"; 110127668Sbms // Probably caused by an inline asm. 111172683Smlaier MachineInstr *MI; 112127668Sbms for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(VirtReg->reg); 113127668Sbms (MI = I.skipInstruction());) 114127668Sbms if (MI->isInlineAsm()) 115127668Sbms break; 116127668Sbms if (MI) 117127668Sbms MI->emitError(Msg); 118127668Sbms else 119127668Sbms report_fatal_error(Msg); 120127668Sbms // Keep going after reporting the error. 121127668Sbms VRM->assignVirt2Phys(VirtReg->reg, 12217680Spst RegClassInfo.getOrder(MRI->getRegClass(VirtReg->reg)).front()); 12317680Spst continue; 12417680Spst } 12517680Spst 12617680Spst if (AvailablePhysReg) 12717680Spst Matrix->assign(*VirtReg, AvailablePhysReg); 12817680Spst 129127668Sbms for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end(); 13017680Spst I != E; ++I) { 13117680Spst LiveInterval *SplitVirtReg = *I; 132190207Srpaulo assert(!VRM->hasPhys(SplitVirtReg->reg) && "Register already assigned"); 13317680Spst if (MRI->reg_nodbg_empty(SplitVirtReg->reg)) { 13417680Spst DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n'); 135172683Smlaier LIS->removeInterval(SplitVirtReg->reg); 136127668Sbms continue; 13717680Spst } 13817680Spst DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n"); 13917680Spst assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) && 14017680Spst "expect split value in virtual register"); 14117680Spst enqueue(SplitVirtReg); 14217680Spst ++NumNewQueued; 14317680Spst } 14417680Spst } 14517680Spst} 14617680Spst