RegAllocBase.cpp revision b21ab43cfc3fa0dacf5c95f04e58b6d804b59a16
1c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)//===-- RegAllocBase.cpp - Register Allocator Base Class ------------------===// 2c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// 3c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// The LLVM Compiler Infrastructure 4c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// 5c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// This file is distributed under the University of Illinois Open Source 6c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// License. See LICENSE.TXT for details. 7c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// 8c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)//===----------------------------------------------------------------------===// 9c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// 10c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// This file defines the RegAllocBase class which provides comon functionality 11c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// for LiveIntervalUnion-based register allocators. 12c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// 13c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)//===----------------------------------------------------------------------===// 14c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 15c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#define DEBUG_TYPE "regalloc" 16c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "RegAllocBase.h" 17c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "Spiller.h" 18c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/ADT/Statistic.h" 19c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/CodeGen/LiveIntervalAnalysis.h" 20c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/CodeGen/LiveRangeEdit.h" 21c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/CodeGen/LiveRegMatrix.h" 22c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/CodeGen/MachineInstr.h" 23c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/CodeGen/MachineRegisterInfo.h" 24c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/CodeGen/VirtRegMap.h" 25c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/Target/TargetMachine.h" 26c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/Target/TargetRegisterInfo.h" 27c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#ifndef NDEBUG 28c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/ADT/SparseBitVector.h" 29c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#endif 30c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/Support/CommandLine.h" 31c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/Support/Debug.h" 32c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/Support/ErrorHandling.h" 33c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/Support/raw_ostream.h" 34c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "llvm/Support/Timer.h" 35c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 36c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)using namespace llvm; 37c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 38c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)STATISTIC(NumNewQueued , "Number of new live ranges queued"); 39c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 40c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Temporary verification option until we can put verification inside 41c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// MachineVerifier. 42c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)static cl::opt<bool, true> 43c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)VerifyRegAlloc("verify-regalloc", cl::location(RegAllocBase::VerifyEnabled), 44c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) cl::desc("Verify during register allocation")); 45c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 46c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)const char RegAllocBase::TimerGroupName[] = "Register Allocation"; 47c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)bool RegAllocBase::VerifyEnabled = false; 48c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 49c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)//===----------------------------------------------------------------------===// 50c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// RegAllocBase Implementation 51c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)//===----------------------------------------------------------------------===// 52c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 53c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)void RegAllocBase::init(VirtRegMap &vrm, 54c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) LiveIntervals &lis, 55c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) LiveRegMatrix &mat) { 56c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) TRI = &vrm.getTargetRegInfo(); 57c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) MRI = &vrm.getRegInfo(); 58c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) VRM = &vrm; 59c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) LIS = &lis; 60c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Matrix = &mat; 61c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) MRI->freezeReservedRegs(vrm.getMachineFunction()); 62c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) RegClassInfo.runOnMachineFunction(vrm.getMachineFunction()); 63c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 64c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 65c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Visit all the live registers. If they are already assigned to a physical 66c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// register, unify them with the corresponding LiveIntervalUnion, otherwise push 67c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// them on the priority queue for later assignment. 68c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)void RegAllocBase::seedLiveRegs() { 69c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) NamedRegionTimer T("Seed Live Regs", TimerGroupName, TimePassesIsEnabled); 70c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 71c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 72c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (MRI->reg_nodbg_empty(Reg)) 73c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) continue; 74c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) enqueue(&LIS->getInterval(Reg)); 75c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 76c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)} 77c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 78c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// Top-level driver to manage the queue of unassigned VirtRegs and call the 79c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// selectOrSplit implementation. 80c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)void RegAllocBase::allocatePhysRegs() { 81c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) seedLiveRegs(); 82c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 83c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Continue assigning vregs one at a time to available physical registers. 84c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) while (LiveInterval *VirtReg = dequeue()) { 85c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) assert(!VRM->hasPhys(VirtReg->reg) && "Register already assigned"); 86c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 87c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Unused registers can appear when the spiller coalesces snippets. 88c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) if (MRI->reg_nodbg_empty(VirtReg->reg)) { 89c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n'); 90c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) LIS->removeInterval(VirtReg->reg); 91c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) continue; 92c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) } 93c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 94c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // Invalidate all interference queries, live ranges could have changed. 95c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) Matrix->invalidateVirtRegs(); 96c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 97c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) // selectOrSplit requests the allocator to return an available physical 98 // register if possible and populate a list of new live intervals that 99 // result from splitting. 100 DEBUG(dbgs() << "\nselectOrSplit " 101 << MRI->getRegClass(VirtReg->reg)->getName() 102 << ':' << *VirtReg << '\n'); 103 typedef SmallVector<unsigned, 4> VirtRegVec; 104 VirtRegVec SplitVRegs; 105 unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs); 106 107 if (AvailablePhysReg == ~0u) { 108 // selectOrSplit failed to find a register! 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("inline assembly requires more registers than available"); 117 else 118 report_fatal_error("ran out of registers during register allocation"); 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 = &LIS->getInterval(*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