254 lines · cpp
1//===- RegAllocBase.cpp - Register Allocator Base Class -------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file defines the RegAllocBase class which provides common functionality10// for LiveIntervalUnion-based register allocators.11//12//===----------------------------------------------------------------------===//13 14#include "RegAllocBase.h"15#include "llvm/ADT/SmallVector.h"16#include "llvm/ADT/Statistic.h"17#include "llvm/CodeGen/LiveInterval.h"18#include "llvm/CodeGen/LiveIntervals.h"19#include "llvm/CodeGen/LiveRegMatrix.h"20#include "llvm/CodeGen/MachineInstr.h"21#include "llvm/CodeGen/MachineModuleInfo.h"22#include "llvm/CodeGen/MachineRegisterInfo.h"23#include "llvm/CodeGen/Spiller.h"24#include "llvm/CodeGen/TargetRegisterInfo.h"25#include "llvm/CodeGen/VirtRegMap.h"26#include "llvm/IR/DiagnosticInfo.h"27#include "llvm/IR/Module.h"28#include "llvm/Pass.h"29#include "llvm/Support/CommandLine.h"30#include "llvm/Support/Debug.h"31#include "llvm/Support/ErrorHandling.h"32#include "llvm/Support/Timer.h"33#include "llvm/Support/raw_ostream.h"34#include <cassert>35 36using namespace llvm;37 38#define DEBUG_TYPE "regalloc"39 40STATISTIC(NumNewQueued, "Number of new live ranges queued");41 42// Temporary verification option until we can put verification inside43// MachineVerifier.44static cl::opt<bool, true>45 VerifyRegAlloc("verify-regalloc", cl::location(RegAllocBase::VerifyEnabled),46 cl::Hidden, cl::desc("Verify during register allocation"));47 48const char RegAllocBase::TimerGroupName[] = "regalloc";49const char RegAllocBase::TimerGroupDescription[] = "Register Allocation";50bool RegAllocBase::VerifyEnabled = false;51 52//===----------------------------------------------------------------------===//53// RegAllocBase Implementation54//===----------------------------------------------------------------------===//55 56// Pin the vtable to this file.57void RegAllocBase::anchor() {}58 59void RegAllocBase::init(VirtRegMap &vrm, LiveIntervals &lis,60 LiveRegMatrix &mat) {61 TRI = &vrm.getTargetRegInfo();62 MRI = &vrm.getRegInfo();63 VRM = &vrm;64 LIS = &lis;65 Matrix = &mat;66 MRI->freezeReservedRegs();67 RegClassInfo.runOnMachineFunction(vrm.getMachineFunction());68 FailedVRegs.clear();69}70 71// Visit all the live registers. If they are already assigned to a physical72// register, unify them with the corresponding LiveIntervalUnion, otherwise push73// them on the priority queue for later assignment.74void RegAllocBase::seedLiveRegs() {75 NamedRegionTimer T("seed", "Seed Live Regs", TimerGroupName,76 TimerGroupDescription, TimePassesIsEnabled);77 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {78 Register Reg = Register::index2VirtReg(i);79 if (MRI->reg_nodbg_empty(Reg))80 continue;81 enqueue(&LIS->getInterval(Reg));82 }83}84 85// Top-level driver to manage the queue of unassigned VirtRegs and call the86// selectOrSplit implementation.87void RegAllocBase::allocatePhysRegs() {88 seedLiveRegs();89 90 // Continue assigning vregs one at a time to available physical registers.91 while (const LiveInterval *VirtReg = dequeue()) {92 assert(!VRM->hasPhys(VirtReg->reg()) && "Register already assigned");93 94 // Unused registers can appear when the spiller coalesces snippets.95 if (MRI->reg_nodbg_empty(VirtReg->reg())) {96 LLVM_DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n');97 aboutToRemoveInterval(*VirtReg);98 LIS->removeInterval(VirtReg->reg());99 continue;100 }101 102 // Invalidate all interference queries, live ranges could have changed.103 Matrix->invalidateVirtRegs();104 105 // selectOrSplit requests the allocator to return an available physical106 // register if possible and populate a list of new live intervals that107 // result from splitting.108 LLVM_DEBUG(dbgs() << "\nselectOrSplit "109 << TRI->getRegClassName(MRI->getRegClass(VirtReg->reg()))110 << ':' << *VirtReg << '\n');111 112 using VirtRegVec = SmallVector<Register, 4>;113 114 VirtRegVec SplitVRegs;115 MCRegister AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs);116 117 if (AvailablePhysReg == ~0u) {118 // selectOrSplit failed to find a register!119 // Probably caused by an inline asm.120 MachineInstr *MI = nullptr;121 for (MachineInstr &MIR : MRI->reg_instructions(VirtReg->reg())) {122 MI = &MIR;123 if (MI->isInlineAsm())124 break;125 }126 127 const TargetRegisterClass *RC = MRI->getRegClass(VirtReg->reg());128 AvailablePhysReg = getErrorAssignment(*RC, MI);129 130 // Keep going after reporting the error.131 cleanupFailedVReg(VirtReg->reg(), AvailablePhysReg, SplitVRegs);132 } else if (AvailablePhysReg)133 Matrix->assign(*VirtReg, AvailablePhysReg);134 135 for (Register Reg : SplitVRegs) {136 assert(LIS->hasInterval(Reg));137 138 LiveInterval *SplitVirtReg = &LIS->getInterval(Reg);139 assert(!VRM->hasPhys(SplitVirtReg->reg()) && "Register already assigned");140 if (MRI->reg_nodbg_empty(SplitVirtReg->reg())) {141 assert(SplitVirtReg->empty() && "Non-empty but used interval");142 LLVM_DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n');143 aboutToRemoveInterval(*SplitVirtReg);144 LIS->removeInterval(SplitVirtReg->reg());145 continue;146 }147 LLVM_DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n");148 assert(SplitVirtReg->reg().isVirtual() &&149 "expect split value in virtual register");150 enqueue(SplitVirtReg);151 ++NumNewQueued;152 }153 }154}155 156void RegAllocBase::postOptimization() {157 spiller().postOptimization();158 for (auto *DeadInst : DeadRemats) {159 LIS->RemoveMachineInstrFromMaps(*DeadInst);160 DeadInst->eraseFromParent();161 }162 DeadRemats.clear();163}164 165void RegAllocBase::cleanupFailedVReg(Register FailedReg, MCRegister PhysReg,166 SmallVectorImpl<Register> &SplitRegs) {167 // We still should produce valid IR. Kill all the uses and reduce the live168 // ranges so that we don't think it's possible to introduce kill flags later169 // which will fail the verifier.170 for (MachineOperand &MO : MRI->reg_operands(FailedReg)) {171 if (MO.readsReg())172 MO.setIsUndef(true);173 }174 175 if (!MRI->isReserved(PhysReg)) {176 // Physical liveness for any aliasing registers is now unreliable, so delete177 // the uses.178 for (MCRegAliasIterator Aliases(PhysReg, TRI, true); Aliases.isValid();179 ++Aliases) {180 for (MachineOperand &MO : MRI->reg_operands(*Aliases)) {181 if (MO.readsReg())182 MO.setIsUndef(true);183 }184 }185 }186 187 // Directly perform the rewrite, and do not leave it to VirtRegRewriter as188 // usual. This avoids trying to manage illegal overlapping assignments in189 // LiveRegMatrix.190 MRI->replaceRegWith(FailedReg, PhysReg);191 LIS->removeInterval(FailedReg);192}193 194void RegAllocBase::enqueue(const LiveInterval *LI) {195 const Register Reg = LI->reg();196 197 assert(Reg.isVirtual() && "Can only enqueue virtual registers");198 199 if (VRM->hasPhys(Reg))200 return;201 202 if (shouldAllocateRegister(Reg)) {203 LLVM_DEBUG(dbgs() << "Enqueuing " << printReg(Reg, TRI) << '\n');204 enqueueImpl(LI);205 } else {206 LLVM_DEBUG(dbgs() << "Not enqueueing " << printReg(Reg, TRI)207 << " in skipped register class\n");208 }209}210 211MCPhysReg RegAllocBase::getErrorAssignment(const TargetRegisterClass &RC,212 const MachineInstr *CtxMI) {213 MachineFunction &MF = VRM->getMachineFunction();214 215 // Avoid printing the error for every single instance of the register. It216 // would be better if this were per register class.217 bool EmitError = !MF.getProperties().hasFailedRegAlloc();218 if (EmitError)219 MF.getProperties().setFailedRegAlloc();220 221 const Function &Fn = MF.getFunction();222 LLVMContext &Context = Fn.getContext();223 224 ArrayRef<MCPhysReg> AllocOrder = RegClassInfo.getOrder(&RC);225 if (AllocOrder.empty()) {226 // If the allocation order is empty, it likely means all registers in the227 // class are reserved. We still to need to pick something, so look at the228 // underlying class.229 ArrayRef<MCPhysReg> RawRegs = RC.getRegisters();230 231 if (EmitError) {232 Context.diagnose(DiagnosticInfoRegAllocFailure(233 "no registers from class available to allocate", Fn,234 CtxMI ? CtxMI->getDebugLoc() : DiagnosticLocation()));235 }236 237 assert(!RawRegs.empty() && "register classes cannot have no registers");238 return RawRegs.front();239 }240 241 if (EmitError) {242 if (CtxMI && CtxMI->isInlineAsm()) {243 CtxMI->emitInlineAsmError(244 "inline assembly requires more registers than available");245 } else {246 Context.diagnose(DiagnosticInfoRegAllocFailure(247 "ran out of registers during register allocation", Fn,248 CtxMI ? CtxMI->getDebugLoc() : DiagnosticLocation()));249 }250 }251 252 return AllocOrder.front();253}254