1ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen//===-- RegAllocBase.cpp - Register Allocator Base Class ------------------===// 2ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen// 3ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen// The LLVM Compiler Infrastructure 4ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen// 5ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 6ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen// License. See LICENSE.TXT for details. 7ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen// 8ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 9ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen// 1036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// This file defines the RegAllocBase class which provides common functionality 11ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen// for LiveIntervalUnion-based register allocators. 12ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen// 13ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 14ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen 15ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen#include "RegAllocBase.h" 16ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen#include "Spiller.h" 17ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 18ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen#include "llvm/CodeGen/LiveIntervalAnalysis.h" 19789d5d85ba6e9259a8e0f0bcfbd06a59ad164512Pete Cooper#include "llvm/CodeGen/LiveRangeEdit.h" 201ead68d769f27f6d68d4aaeffe4199fa2cacbc95Jakob Stoklund Olesen#include "llvm/CodeGen/LiveRegMatrix.h" 21ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen#include "llvm/CodeGen/MachineInstr.h" 22ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 231ead68d769f27f6d68d4aaeffe4199fa2cacbc95Jakob Stoklund Olesen#include "llvm/CodeGen/VirtRegMap.h" 24ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen#include "llvm/Target/TargetRegisterInfo.h" 25ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen#include "llvm/Support/CommandLine.h" 26ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen#include "llvm/Support/Debug.h" 274c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar#include "llvm/Support/raw_ostream.h" 28ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen#include "llvm/Support/ErrorHandling.h" 29ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 30ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen#include "llvm/Support/Timer.h" 31ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen 32ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesenusing namespace llvm; 33ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen 34dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "regalloc" 35dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 36ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund OlesenSTATISTIC(NumNewQueued , "Number of new live ranges queued"); 37ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen 38ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen// Temporary verification option until we can put verification inside 39ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen// MachineVerifier. 40ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesenstatic cl::opt<bool, true> 41ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund OlesenVerifyRegAlloc("verify-regalloc", cl::location(RegAllocBase::VerifyEnabled), 42ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen cl::desc("Verify during register allocation")); 43ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen 448de25f031d8a8c63e0107f7fd0ac4af6b8ab600cCraig Topperconst char RegAllocBase::TimerGroupName[] = "Register Allocation"; 45ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesenbool RegAllocBase::VerifyEnabled = false; 46ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen 47ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 48ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen// RegAllocBase Implementation 49ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen//===----------------------------------------------------------------------===// 50ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen 51354362524a72b3fa43a6c09380b7ae3b2380cbbaJuergen Ributzka// Pin the vtable to this file. 52354362524a72b3fa43a6c09380b7ae3b2380cbbaJuergen Ributzkavoid RegAllocBase::anchor() {} 53354362524a72b3fa43a6c09380b7ae3b2380cbbaJuergen Ributzka 54d4348a2dc24c4fb012c1b9b20e71908f52049283Jakob Stoklund Olesenvoid RegAllocBase::init(VirtRegMap &vrm, 55d4348a2dc24c4fb012c1b9b20e71908f52049283Jakob Stoklund Olesen LiveIntervals &lis, 56d4348a2dc24c4fb012c1b9b20e71908f52049283Jakob Stoklund Olesen LiveRegMatrix &mat) { 57ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen TRI = &vrm.getTargetRegInfo(); 58ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen MRI = &vrm.getRegInfo(); 59ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen VRM = &vrm; 60ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen LIS = &lis; 61d4348a2dc24c4fb012c1b9b20e71908f52049283Jakob Stoklund Olesen Matrix = &mat; 6218bb0545ff79b85ef424e95e2170e3a06f11b735Chad Rosier MRI->freezeReservedRegs(vrm.getMachineFunction()); 63ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen RegClassInfo.runOnMachineFunction(vrm.getMachineFunction()); 64ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen} 65ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen 66ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen// Visit all the live registers. If they are already assigned to a physical 67ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen// register, unify them with the corresponding LiveIntervalUnion, otherwise push 68ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen// them on the priority queue for later assignment. 69ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesenvoid RegAllocBase::seedLiveRegs() { 70ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen NamedRegionTimer T("Seed Live Regs", TimerGroupName, TimePassesIsEnabled); 71d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 72d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 73d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen if (MRI->reg_nodbg_empty(Reg)) 74d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen continue; 75d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen enqueue(&LIS->getInterval(Reg)); 76ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen } 77ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen} 78ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen 79ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen// Top-level driver to manage the queue of unassigned VirtRegs and call the 80ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen// selectOrSplit implementation. 81ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesenvoid RegAllocBase::allocatePhysRegs() { 82ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen seedLiveRegs(); 83ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen 84ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen // Continue assigning vregs one at a time to available physical registers. 85ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen while (LiveInterval *VirtReg = dequeue()) { 86ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen assert(!VRM->hasPhys(VirtReg->reg) && "Register already assigned"); 87ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen 88ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen // Unused registers can appear when the spiller coalesces snippets. 89ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen if (MRI->reg_nodbg_empty(VirtReg->reg)) { 90ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n'); 91ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines aboutToRemoveInterval(*VirtReg); 92ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen LIS->removeInterval(VirtReg->reg); 93ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen continue; 94ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen } 95ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen 96ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen // Invalidate all interference queries, live ranges could have changed. 97d4348a2dc24c4fb012c1b9b20e71908f52049283Jakob Stoklund Olesen Matrix->invalidateVirtRegs(); 98ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen 99ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen // selectOrSplit requests the allocator to return an available physical 100ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen // register if possible and populate a list of new live intervals that 101ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen // result from splitting. 102ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen DEBUG(dbgs() << "\nselectOrSplit " 10337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines << TRI->getRegClassName(MRI->getRegClass(VirtReg->reg)) 10436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines << ':' << *VirtReg << " w=" << VirtReg->weight << '\n'); 1051feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey typedef SmallVector<unsigned, 4> VirtRegVec; 106ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen VirtRegVec SplitVRegs; 107ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs); 108ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen 109ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen if (AvailablePhysReg == ~0u) { 110ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen // selectOrSplit failed to find a register! 111ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen // Probably caused by an inline asm. 112dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines MachineInstr *MI = nullptr; 11336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (MachineRegisterInfo::reg_instr_iterator 11436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines I = MRI->reg_instr_begin(VirtReg->reg), E = MRI->reg_instr_end(); 11536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines I != E; ) { 11636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineInstr *TmpMI = &*(I++); 11736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (TmpMI->isInlineAsm()) { 11836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MI = TmpMI; 119ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen break; 12036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 12136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 122ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen if (MI) 12387855d3013d9a87a3aeb51508312b76e200baac7Benjamin Kramer MI->emitError("inline assembly requires more registers than available"); 124ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen else 12587855d3013d9a87a3aeb51508312b76e200baac7Benjamin Kramer report_fatal_error("ran out of registers during register allocation"); 126ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen // Keep going after reporting the error. 127ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen VRM->assignVirt2Phys(VirtReg->reg, 128ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen RegClassInfo.getOrder(MRI->getRegClass(VirtReg->reg)).front()); 129ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen continue; 130ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen } 131ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen 132ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen if (AvailablePhysReg) 133d4348a2dc24c4fb012c1b9b20e71908f52049283Jakob Stoklund Olesen Matrix->assign(*VirtReg, AvailablePhysReg); 134ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen 135ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end(); 136ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen I != E; ++I) { 1371feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval *SplitVirtReg = &LIS->getInterval(*I); 138ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen assert(!VRM->hasPhys(SplitVirtReg->reg) && "Register already assigned"); 139ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen if (MRI->reg_nodbg_empty(SplitVirtReg->reg)) { 140ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n'); 141ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines aboutToRemoveInterval(*SplitVirtReg); 142ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen LIS->removeInterval(SplitVirtReg->reg); 143ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen continue; 144ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen } 145ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n"); 146ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) && 147ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen "expect split value in virtual register"); 148ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen enqueue(SplitVirtReg); 149ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen ++NumNewQueued; 150ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen } 151ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen } 152ccc9581e8b79b4216cb1143344bdae9342722d5dJakob Stoklund Olesen} 153de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 154de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarvoid RegAllocBase::postOptimization() { 155de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar spiller().postOptimization(); 156de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto DeadInst : DeadRemats) { 157de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LIS->RemoveMachineInstrFromMaps(*DeadInst); 158de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DeadInst->eraseFromParent(); 159de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar } 160de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar DeadRemats.clear(); 161de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 162