From 0b57cec536236d46e3dba9bd041533462f33dbb7 Mon Sep 17 00:00:00 2001 From: Dimitry Andric Date: Fri, 20 Dec 2019 19:53:05 +0000 Subject: Move all sources from the llvm project into contrib/llvm-project. This uses the new layout of the upstream repository, which was recently migrated to GitHub, and converted into a "monorepo". That is, most of the earlier separate sub-projects with their own branches and tags were consolidated into one top-level directory, and are now branched and tagged together. Updating the vendor area to match this layout is next. --- .../llvm-project/llvm/lib/CodeGen/RegAllocBase.cpp | 172 +++++++++++++++++++++ 1 file changed, 172 insertions(+) create mode 100644 contrib/llvm-project/llvm/lib/CodeGen/RegAllocBase.cpp (limited to 'contrib/llvm-project/llvm/lib/CodeGen/RegAllocBase.cpp') diff --git a/contrib/llvm-project/llvm/lib/CodeGen/RegAllocBase.cpp b/contrib/llvm-project/llvm/lib/CodeGen/RegAllocBase.cpp new file mode 100644 index 000000000000..1cbe75c27d13 --- /dev/null +++ b/contrib/llvm-project/llvm/lib/CodeGen/RegAllocBase.cpp @@ -0,0 +1,172 @@ +//===- RegAllocBase.cpp - Register Allocator Base Class -------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines the RegAllocBase class which provides common functionality +// for LiveIntervalUnion-based register allocators. +// +//===----------------------------------------------------------------------===// + +#include "RegAllocBase.h" +#include "Spiller.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/CodeGen/LiveInterval.h" +#include "llvm/CodeGen/LiveIntervals.h" +#include "llvm/CodeGen/LiveRegMatrix.h" +#include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/MachineModuleInfo.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/TargetRegisterInfo.h" +#include "llvm/CodeGen/VirtRegMap.h" +#include "llvm/Pass.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/Timer.h" +#include "llvm/Support/raw_ostream.h" +#include + +using namespace llvm; + +#define DEBUG_TYPE "regalloc" + +STATISTIC(NumNewQueued , "Number of new live ranges queued"); + +// Temporary verification option until we can put verification inside +// MachineVerifier. +static cl::opt + VerifyRegAlloc("verify-regalloc", cl::location(RegAllocBase::VerifyEnabled), + cl::Hidden, cl::desc("Verify during register allocation")); + +const char RegAllocBase::TimerGroupName[] = "regalloc"; +const char RegAllocBase::TimerGroupDescription[] = "Register Allocation"; +bool RegAllocBase::VerifyEnabled = false; + +//===----------------------------------------------------------------------===// +// RegAllocBase Implementation +//===----------------------------------------------------------------------===// + +// Pin the vtable to this file. +void RegAllocBase::anchor() {} + +void RegAllocBase::init(VirtRegMap &vrm, + LiveIntervals &lis, + LiveRegMatrix &mat) { + TRI = &vrm.getTargetRegInfo(); + MRI = &vrm.getRegInfo(); + VRM = &vrm; + LIS = &lis; + Matrix = &mat; + MRI->freezeReservedRegs(vrm.getMachineFunction()); + RegClassInfo.runOnMachineFunction(vrm.getMachineFunction()); +} + +// Visit all the live registers. If they are already assigned to a physical +// register, unify them with the corresponding LiveIntervalUnion, otherwise push +// them on the priority queue for later assignment. +void RegAllocBase::seedLiveRegs() { + NamedRegionTimer T("seed", "Seed Live Regs", TimerGroupName, + TimerGroupDescription, TimePassesIsEnabled); + for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { + unsigned Reg = TargetRegisterInfo::index2VirtReg(i); + if (MRI->reg_nodbg_empty(Reg)) + continue; + enqueue(&LIS->getInterval(Reg)); + } +} + +// Top-level driver to manage the queue of unassigned VirtRegs and call the +// selectOrSplit implementation. +void RegAllocBase::allocatePhysRegs() { + seedLiveRegs(); + + // Continue assigning vregs one at a time to available physical registers. + while (LiveInterval *VirtReg = dequeue()) { + assert(!VRM->hasPhys(VirtReg->reg) && "Register already assigned"); + + // Unused registers can appear when the spiller coalesces snippets. + if (MRI->reg_nodbg_empty(VirtReg->reg)) { + LLVM_DEBUG(dbgs() << "Dropping unused " << *VirtReg << '\n'); + aboutToRemoveInterval(*VirtReg); + LIS->removeInterval(VirtReg->reg); + continue; + } + + // Invalidate all interference queries, live ranges could have changed. + Matrix->invalidateVirtRegs(); + + // selectOrSplit requests the allocator to return an available physical + // register if possible and populate a list of new live intervals that + // result from splitting. + LLVM_DEBUG(dbgs() << "\nselectOrSplit " + << TRI->getRegClassName(MRI->getRegClass(VirtReg->reg)) + << ':' << *VirtReg << " w=" << VirtReg->weight << '\n'); + + using VirtRegVec = SmallVector; + + VirtRegVec SplitVRegs; + unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs); + + if (AvailablePhysReg == ~0u) { + // selectOrSplit failed to find a register! + // Probably caused by an inline asm. + MachineInstr *MI = nullptr; + for (MachineRegisterInfo::reg_instr_iterator + I = MRI->reg_instr_begin(VirtReg->reg), E = MRI->reg_instr_end(); + I != E; ) { + MI = &*(I++); + if (MI->isInlineAsm()) + break; + } + if (MI && MI->isInlineAsm()) { + MI->emitError("inline assembly requires more registers than available"); + } else if (MI) { + LLVMContext &Context = + MI->getParent()->getParent()->getMMI().getModule()->getContext(); + Context.emitError("ran out of registers during register allocation"); + } else { + report_fatal_error("ran out of registers during register allocation"); + } + // Keep going after reporting the error. + VRM->assignVirt2Phys(VirtReg->reg, + RegClassInfo.getOrder(MRI->getRegClass(VirtReg->reg)).front()); + continue; + } + + if (AvailablePhysReg) + Matrix->assign(*VirtReg, AvailablePhysReg); + + for (unsigned Reg : SplitVRegs) { + assert(LIS->hasInterval(Reg)); + + LiveInterval *SplitVirtReg = &LIS->getInterval(Reg); + assert(!VRM->hasPhys(SplitVirtReg->reg) && "Register already assigned"); + if (MRI->reg_nodbg_empty(SplitVirtReg->reg)) { + assert(SplitVirtReg->empty() && "Non-empty but used interval"); + LLVM_DEBUG(dbgs() << "not queueing unused " << *SplitVirtReg << '\n'); + aboutToRemoveInterval(*SplitVirtReg); + LIS->removeInterval(SplitVirtReg->reg); + continue; + } + LLVM_DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n"); + assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) && + "expect split value in virtual register"); + enqueue(SplitVirtReg); + ++NumNewQueued; + } + } +} + +void RegAllocBase::postOptimization() { + spiller().postOptimization(); + for (auto DeadInst : DeadRemats) { + LIS->RemoveMachineInstrFromMaps(*DeadInst); + DeadInst->eraseFromParent(); + } + DeadRemats.clear(); +} -- cgit v1.2.3