RegAllocBase.cpp revision 5a364c5561ec04e33a6f5d52c14f1bac6f247ea0
172c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer//===-- RegAllocBase.cpp - Register Allocator Base Class ------------------===// 272c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer// 372c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer// The LLVM Compiler Infrastructure 472c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer// 572c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer// This file is distributed under the University of Illinois Open Source 672c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer// License. See LICENSE.TXT for details. 772c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer// 872c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer//===----------------------------------------------------------------------===// 972c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer// 1072c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer// This file defines the RegAllocBase class which provides comon functionality 1172c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer// for LiveIntervalUnion-based register allocators. 1272c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer// 136faff4886a3059a8cda08f015d29a6c9a0a4de3cAlexey Samsonov//===----------------------------------------------------------------------===// 14c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov 1572c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer#define DEBUG_TYPE "regalloc" 1672c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer#include "RegAllocBase.h" 1772c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer#include "Spiller.h" 1872c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer#include "llvm/ADT/Statistic.h" 19cd7c4980d4ee2d22d92a4907f2d029e67b52d732David Blaikie#include "llvm/CodeGen/LiveIntervalAnalysis.h" 2072c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer#include "llvm/CodeGen/LiveRangeEdit.h" 2172c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer#include "llvm/CodeGen/LiveRegMatrix.h" 2272c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer#include "llvm/CodeGen/MachineInstr.h" 23c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov#include "llvm/CodeGen/MachineRegisterInfo.h" 24c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov#include "llvm/CodeGen/VirtRegMap.h" 25c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov#include "llvm/Target/TargetMachine.h" 26c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov#include "llvm/Target/TargetRegisterInfo.h" 27c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov#ifndef NDEBUG 28c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov#include "llvm/ADT/SparseBitVector.h" 29c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov#endif 30c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov#include "llvm/Support/CommandLine.h" 31c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov#include "llvm/Support/Debug.h" 32c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov#include "llvm/Support/ErrorHandling.h" 33c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov#include "llvm/Support/raw_ostream.h" 34c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov#include "llvm/Support/Timer.h" 35c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov 36c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonovusing namespace llvm; 37c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov 3872c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin KramerSTATISTIC(NumNewQueued , "Number of new live ranges queued"); 39dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 4072c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer// Temporary verification option until we can put verification inside 4172c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer// MachineVerifier. 4272c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramerstatic cl::opt<bool, true> 4372c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin KramerVerifyRegAlloc("verify-regalloc", cl::location(RegAllocBase::VerifyEnabled), 4472c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer cl::desc("Verify during register allocation")); 4572c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer 4672c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramerconst char RegAllocBase::TimerGroupName[] = "Register Allocation"; 4772c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramerbool RegAllocBase::VerifyEnabled = false; 4872c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer 4972c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer//===----------------------------------------------------------------------===// 5072c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer// RegAllocBase Implementation 5172c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer//===----------------------------------------------------------------------===// 5272c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer 5372c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer// pin vtable to this file 5472c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramervoid RegAllocBase::anchor() {} 55c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov 5672c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramervoid RegAllocBase::init(VirtRegMap &vrm, 57c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov LiveIntervals &lis, 58c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov LiveRegMatrix &mat) { 59cd7c4980d4ee2d22d92a4907f2d029e67b52d732David Blaikie TRI = &vrm.getTargetRegInfo(); 6072c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer MRI = &vrm.getRegInfo(); 61cd7c4980d4ee2d22d92a4907f2d029e67b52d732David Blaikie VRM = &vrm; 6272c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer LIS = &lis; 63dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Matrix = &mat; 6472c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer MRI->freezeReservedRegs(vrm.getMachineFunction()); 6572c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer RegClassInfo.runOnMachineFunction(vrm.getMachineFunction()); 66c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov} 67c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov 68c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov// Visit all the live registers. If they are already assigned to a physical 69c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov// register, unify them with the corresponding LiveIntervalUnion, otherwise push 70c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov// them on the priority queue for later assignment. 71c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonovvoid RegAllocBase::seedLiveRegs() { 72c5253237f8b3b4eb888f7f85f39acd7d4d0f57cfAlexey Samsonov NamedRegionTimer T("Seed Live Regs", TimerGroupName, TimePassesIsEnabled); 7371f6d6ee1a42a39b897f165802716baaad91e21bAlexey Samsonov for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 7472c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 75cd7c4980d4ee2d22d92a4907f2d029e67b52d732David Blaikie if (MRI->reg_nodbg_empty(Reg)) 7672c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer continue; 77cd7c4980d4ee2d22d92a4907f2d029e67b52d732David Blaikie enqueue(&LIS->getInterval(Reg)); 7871f6d6ee1a42a39b897f165802716baaad91e21bAlexey Samsonov } 796faff4886a3059a8cda08f015d29a6c9a0a4de3cAlexey Samsonov} 806faff4886a3059a8cda08f015d29a6c9a0a4de3cAlexey Samsonov 8172c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer// Top-level driver to manage the queue of unassigned VirtRegs and call the 8272c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer// selectOrSplit implementation. 8372c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramervoid RegAllocBase::allocatePhysRegs() { 8472c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer seedLiveRegs(); 8572c0d7fdd3d0930c7507060e96aec7d7429a8190Benjamin Kramer 86 // Continue assigning vregs one at a time to available physical registers. 87 while (LiveInterval *VirtReg = dequeue()) { 88 assert(!VRM->hasPhys(VirtReg->reg) && "Register already assigned"); 89 90 // Unused registers can appear when the spiller coalesces snippets. 91 if (MRI->reg_nodbg_empty(VirtReg->reg)) { 92 DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n'); 93 LIS->removeInterval(VirtReg->reg); 94 continue; 95 } 96 97 // Invalidate all interference queries, live ranges could have changed. 98 Matrix->invalidateVirtRegs(); 99 100 // selectOrSplit requests the allocator to return an available physical 101 // register if possible and populate a list of new live intervals that 102 // result from splitting. 103 DEBUG(dbgs() << "\nselectOrSplit " 104 << MRI->getRegClass(VirtReg->reg)->getName() 105 << ':' << *VirtReg << '\n'); 106 typedef SmallVector<unsigned, 4> VirtRegVec; 107 VirtRegVec SplitVRegs; 108 unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs); 109 110 if (AvailablePhysReg == ~0u) { 111 // selectOrSplit failed to find a register! 112 // Probably caused by an inline asm. 113 MachineInstr *MI; 114 for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(VirtReg->reg); 115 (MI = I.skipInstruction());) 116 if (MI->isInlineAsm()) 117 break; 118 if (MI) 119 MI->emitError("inline assembly requires more registers than available"); 120 else 121 report_fatal_error("ran out of registers during register allocation"); 122 // Keep going after reporting the error. 123 VRM->assignVirt2Phys(VirtReg->reg, 124 RegClassInfo.getOrder(MRI->getRegClass(VirtReg->reg)).front()); 125 continue; 126 } 127 128 if (AvailablePhysReg) 129 Matrix->assign(*VirtReg, AvailablePhysReg); 130 131 for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end(); 132 I != E; ++I) { 133 LiveInterval *SplitVirtReg = &LIS->getInterval(*I); 134 assert(!VRM->hasPhys(SplitVirtReg->reg) && "Register already assigned"); 135 if (MRI->reg_nodbg_empty(SplitVirtReg->reg)) { 136 DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n'); 137 LIS->removeInterval(SplitVirtReg->reg); 138 continue; 139 } 140 DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n"); 141 assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) && 142 "expect split value in virtual register"); 143 enqueue(SplitVirtReg); 144 ++NumNewQueued; 145 } 146 } 147} 148