diff options
Diffstat (limited to 'contrib/llvm/lib/CodeGen/RegAllocBasic.cpp')
| -rw-r--r-- | contrib/llvm/lib/CodeGen/RegAllocBasic.cpp | 333 |
1 files changed, 0 insertions, 333 deletions
diff --git a/contrib/llvm/lib/CodeGen/RegAllocBasic.cpp b/contrib/llvm/lib/CodeGen/RegAllocBasic.cpp deleted file mode 100644 index 46f6946f7003..000000000000 --- a/contrib/llvm/lib/CodeGen/RegAllocBasic.cpp +++ /dev/null @@ -1,333 +0,0 @@ -//===-- RegAllocBasic.cpp - Basic Register Allocator ----------------------===// -// -// 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 RABasic function pass, which provides a minimal -// implementation of the basic register allocator. -// -//===----------------------------------------------------------------------===// - -#include "AllocationOrder.h" -#include "LiveDebugVariables.h" -#include "RegAllocBase.h" -#include "Spiller.h" -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/CodeGen/CalcSpillWeights.h" -#include "llvm/CodeGen/LiveIntervals.h" -#include "llvm/CodeGen/LiveRangeEdit.h" -#include "llvm/CodeGen/LiveRegMatrix.h" -#include "llvm/CodeGen/LiveStacks.h" -#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" -#include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/MachineInstr.h" -#include "llvm/CodeGen/MachineLoopInfo.h" -#include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/CodeGen/Passes.h" -#include "llvm/CodeGen/RegAllocRegistry.h" -#include "llvm/CodeGen/TargetRegisterInfo.h" -#include "llvm/CodeGen/VirtRegMap.h" -#include "llvm/PassAnalysisSupport.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" -#include <cstdlib> -#include <queue> - -using namespace llvm; - -#define DEBUG_TYPE "regalloc" - -static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator", - createBasicRegisterAllocator); - -namespace { - struct CompSpillWeight { - bool operator()(LiveInterval *A, LiveInterval *B) const { - return A->weight < B->weight; - } - }; -} - -namespace { -/// RABasic provides a minimal implementation of the basic register allocation -/// algorithm. It prioritizes live virtual registers by spill weight and spills -/// whenever a register is unavailable. This is not practical in production but -/// provides a useful baseline both for measuring other allocators and comparing -/// the speed of the basic algorithm against other styles of allocators. -class RABasic : public MachineFunctionPass, - public RegAllocBase, - private LiveRangeEdit::Delegate { - // context - MachineFunction *MF; - - // state - std::unique_ptr<Spiller> SpillerInstance; - std::priority_queue<LiveInterval*, std::vector<LiveInterval*>, - CompSpillWeight> Queue; - - // Scratch space. Allocated here to avoid repeated malloc calls in - // selectOrSplit(). - BitVector UsableRegs; - - bool LRE_CanEraseVirtReg(unsigned) override; - void LRE_WillShrinkVirtReg(unsigned) override; - -public: - RABasic(); - - /// Return the pass name. - StringRef getPassName() const override { return "Basic Register Allocator"; } - - /// RABasic analysis usage. - void getAnalysisUsage(AnalysisUsage &AU) const override; - - void releaseMemory() override; - - Spiller &spiller() override { return *SpillerInstance; } - - void enqueue(LiveInterval *LI) override { - Queue.push(LI); - } - - LiveInterval *dequeue() override { - if (Queue.empty()) - return nullptr; - LiveInterval *LI = Queue.top(); - Queue.pop(); - return LI; - } - - unsigned selectOrSplit(LiveInterval &VirtReg, - SmallVectorImpl<unsigned> &SplitVRegs) override; - - /// Perform register allocation. - bool runOnMachineFunction(MachineFunction &mf) override; - - MachineFunctionProperties getRequiredProperties() const override { - return MachineFunctionProperties().set( - MachineFunctionProperties::Property::NoPHIs); - } - - // Helper for spilling all live virtual registers currently unified under preg - // that interfere with the most recently queried lvr. Return true if spilling - // was successful, and append any new spilled/split intervals to splitLVRs. - bool spillInterferences(LiveInterval &VirtReg, unsigned PhysReg, - SmallVectorImpl<unsigned> &SplitVRegs); - - static char ID; -}; - -char RABasic::ID = 0; - -} // end anonymous namespace - -char &llvm::RABasicID = RABasic::ID; - -INITIALIZE_PASS_BEGIN(RABasic, "regallocbasic", "Basic Register Allocator", - false, false) -INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) -INITIALIZE_PASS_DEPENDENCY(SlotIndexes) -INITIALIZE_PASS_DEPENDENCY(LiveIntervals) -INITIALIZE_PASS_DEPENDENCY(RegisterCoalescer) -INITIALIZE_PASS_DEPENDENCY(MachineScheduler) -INITIALIZE_PASS_DEPENDENCY(LiveStacks) -INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) -INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) -INITIALIZE_PASS_DEPENDENCY(VirtRegMap) -INITIALIZE_PASS_DEPENDENCY(LiveRegMatrix) -INITIALIZE_PASS_END(RABasic, "regallocbasic", "Basic Register Allocator", false, - false) - -bool RABasic::LRE_CanEraseVirtReg(unsigned VirtReg) { - LiveInterval &LI = LIS->getInterval(VirtReg); - if (VRM->hasPhys(VirtReg)) { - Matrix->unassign(LI); - aboutToRemoveInterval(LI); - return true; - } - // Unassigned virtreg is probably in the priority queue. - // RegAllocBase will erase it after dequeueing. - // Nonetheless, clear the live-range so that the debug - // dump will show the right state for that VirtReg. - LI.clear(); - return false; -} - -void RABasic::LRE_WillShrinkVirtReg(unsigned VirtReg) { - if (!VRM->hasPhys(VirtReg)) - return; - - // Register is assigned, put it back on the queue for reassignment. - LiveInterval &LI = LIS->getInterval(VirtReg); - Matrix->unassign(LI); - enqueue(&LI); -} - -RABasic::RABasic(): MachineFunctionPass(ID) { -} - -void RABasic::getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesCFG(); - AU.addRequired<AAResultsWrapperPass>(); - AU.addPreserved<AAResultsWrapperPass>(); - AU.addRequired<LiveIntervals>(); - AU.addPreserved<LiveIntervals>(); - AU.addPreserved<SlotIndexes>(); - AU.addRequired<LiveDebugVariables>(); - AU.addPreserved<LiveDebugVariables>(); - AU.addRequired<LiveStacks>(); - AU.addPreserved<LiveStacks>(); - AU.addRequired<MachineBlockFrequencyInfo>(); - AU.addPreserved<MachineBlockFrequencyInfo>(); - AU.addRequiredID(MachineDominatorsID); - AU.addPreservedID(MachineDominatorsID); - AU.addRequired<MachineLoopInfo>(); - AU.addPreserved<MachineLoopInfo>(); - AU.addRequired<VirtRegMap>(); - AU.addPreserved<VirtRegMap>(); - AU.addRequired<LiveRegMatrix>(); - AU.addPreserved<LiveRegMatrix>(); - MachineFunctionPass::getAnalysisUsage(AU); -} - -void RABasic::releaseMemory() { - SpillerInstance.reset(); -} - - -// Spill or split all live virtual registers currently unified under PhysReg -// that interfere with VirtReg. The newly spilled or split live intervals are -// returned by appending them to SplitVRegs. -bool RABasic::spillInterferences(LiveInterval &VirtReg, unsigned PhysReg, - SmallVectorImpl<unsigned> &SplitVRegs) { - // Record each interference and determine if all are spillable before mutating - // either the union or live intervals. - SmallVector<LiveInterval*, 8> Intfs; - - // Collect interferences assigned to any alias of the physical register. - for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { - LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units); - Q.collectInterferingVRegs(); - for (unsigned i = Q.interferingVRegs().size(); i; --i) { - LiveInterval *Intf = Q.interferingVRegs()[i - 1]; - if (!Intf->isSpillable() || Intf->weight > VirtReg.weight) - return false; - Intfs.push_back(Intf); - } - } - LLVM_DEBUG(dbgs() << "spilling " << printReg(PhysReg, TRI) - << " interferences with " << VirtReg << "\n"); - assert(!Intfs.empty() && "expected interference"); - - // Spill each interfering vreg allocated to PhysReg or an alias. - for (unsigned i = 0, e = Intfs.size(); i != e; ++i) { - LiveInterval &Spill = *Intfs[i]; - - // Skip duplicates. - if (!VRM->hasPhys(Spill.reg)) - continue; - - // Deallocate the interfering vreg by removing it from the union. - // A LiveInterval instance may not be in a union during modification! - Matrix->unassign(Spill); - - // Spill the extracted interval. - LiveRangeEdit LRE(&Spill, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats); - spiller().spill(LRE); - } - return true; -} - -// Driver for the register assignment and splitting heuristics. -// Manages iteration over the LiveIntervalUnions. -// -// This is a minimal implementation of register assignment and splitting that -// spills whenever we run out of registers. -// -// selectOrSplit can only be called once per live virtual register. We then do a -// single interference test for each register the correct class until we find an -// available register. So, the number of interference tests in the worst case is -// |vregs| * |machineregs|. And since the number of interference tests is -// minimal, there is no value in caching them outside the scope of -// selectOrSplit(). -unsigned RABasic::selectOrSplit(LiveInterval &VirtReg, - SmallVectorImpl<unsigned> &SplitVRegs) { - // Populate a list of physical register spill candidates. - SmallVector<unsigned, 8> PhysRegSpillCands; - - // Check for an available register in this class. - AllocationOrder Order(VirtReg.reg, *VRM, RegClassInfo, Matrix); - while (unsigned PhysReg = Order.next()) { - // Check for interference in PhysReg - switch (Matrix->checkInterference(VirtReg, PhysReg)) { - case LiveRegMatrix::IK_Free: - // PhysReg is available, allocate it. - return PhysReg; - - case LiveRegMatrix::IK_VirtReg: - // Only virtual registers in the way, we may be able to spill them. - PhysRegSpillCands.push_back(PhysReg); - continue; - - default: - // RegMask or RegUnit interference. - continue; - } - } - - // Try to spill another interfering reg with less spill weight. - for (SmallVectorImpl<unsigned>::iterator PhysRegI = PhysRegSpillCands.begin(), - PhysRegE = PhysRegSpillCands.end(); PhysRegI != PhysRegE; ++PhysRegI) { - if (!spillInterferences(VirtReg, *PhysRegI, SplitVRegs)) - continue; - - assert(!Matrix->checkInterference(VirtReg, *PhysRegI) && - "Interference after spill."); - // Tell the caller to allocate to this newly freed physical register. - return *PhysRegI; - } - - // No other spill candidates were found, so spill the current VirtReg. - LLVM_DEBUG(dbgs() << "spilling: " << VirtReg << '\n'); - if (!VirtReg.isSpillable()) - return ~0u; - LiveRangeEdit LRE(&VirtReg, SplitVRegs, *MF, *LIS, VRM, this, &DeadRemats); - spiller().spill(LRE); - - // The live virtual register requesting allocation was spilled, so tell - // the caller not to allocate anything during this round. - return 0; -} - -bool RABasic::runOnMachineFunction(MachineFunction &mf) { - LLVM_DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n" - << "********** Function: " << mf.getName() << '\n'); - - MF = &mf; - RegAllocBase::init(getAnalysis<VirtRegMap>(), - getAnalysis<LiveIntervals>(), - getAnalysis<LiveRegMatrix>()); - - calculateSpillWeightsAndHints(*LIS, *MF, VRM, - getAnalysis<MachineLoopInfo>(), - getAnalysis<MachineBlockFrequencyInfo>()); - - SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM)); - - allocatePhysRegs(); - postOptimization(); - - // Diagnostic output before rewriting - LLVM_DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n"); - - releaseMemory(); - return true; -} - -FunctionPass* llvm::createBasicRegisterAllocator() -{ - return new RABasic(); -} |