-//===-- RegAllocBasic.cpp - basic register allocator ----------------------===//
+//===-- RegAllocBasic.cpp - Basic Register Allocator ----------------------===//
//
// The LLVM Compiler Infrastructure
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "regalloc"
+#include "llvm/CodeGen/Passes.h"
+#include "AllocationOrder.h"
+#include "LiveDebugVariables.h"
#include "RegAllocBase.h"
-#include "RenderMachineFunction.h"
#include "Spiller.h"
-#include "VirtRegRewriter.h"
-#include "llvm/Function.h"
-#include "llvm/PassAnalysisSupport.h"
+#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/CalcSpillWeights.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
+#include "llvm/CodeGen/LiveRangeEdit.h"
+#include "llvm/CodeGen/LiveRegMatrix.h"
#include "llvm/CodeGen/LiveStackAnalysis.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/RegisterCoalescer.h"
-#include "llvm/Target/TargetMachine.h"
-#include "llvm/Target/TargetOptions.h"
+#include "llvm/CodeGen/VirtRegMap.h"
+#include "llvm/PassAnalysisSupport.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Target/TargetOptions.h"
+#include "llvm/Target/TargetRegisterInfo.h"
+#include <cstdlib>
+#include <queue>
using namespace llvm;
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
class RABasic : public MachineFunctionPass, public RegAllocBase
{
// context
- MachineFunction *mf_;
- const TargetMachine *tm_;
- MachineRegisterInfo *mri_;
-
- // analyses
- LiveStacks *ls_;
- RenderMachineFunction *rmf_;
+ MachineFunction *MF;
// state
- std::auto_ptr<Spiller> spiller_;
+ std::auto_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;
public:
RABasic();
}
/// RABasic analysis usage.
- virtual void getAnalysisUsage(AnalysisUsage &au) const;
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const;
virtual void releaseMemory();
- virtual unsigned selectOrSplit(LiveInterval &lvr, LiveVirtRegs &splitLVRs);
+ virtual Spiller &spiller() { return *SpillerInstance; }
+
+ virtual float getPriority(LiveInterval *LI) { return LI->weight; }
+
+ virtual void enqueue(LiveInterval *LI) {
+ Queue.push(LI);
+ }
+
+ virtual LiveInterval *dequeue() {
+ if (Queue.empty())
+ return 0;
+ LiveInterval *LI = Queue.top();
+ Queue.pop();
+ return LI;
+ }
+
+ virtual unsigned selectOrSplit(LiveInterval &VirtReg,
+ SmallVectorImpl<LiveInterval*> &SplitVRegs);
/// Perform register allocation.
virtual bool runOnMachineFunction(MachineFunction &mf);
+ // 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<LiveInterval*> &SplitVRegs);
+
static char ID;
};
} // end anonymous namespace
-// We should not need to publish the initializer as long as no other passes
-// require RABasic.
-#if 0 // disable INITIALIZE_PASS
-INITIALIZE_PASS_BEGIN(RABasic, "basic-regalloc",
- "Basic Register Allocator", false, false)
-INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
-INITIALIZE_PASS_DEPENDENCY(StrongPHIElimination)
-INITIALIZE_AG_DEPENDENCY(RegisterCoalescer)
-INITIALIZE_PASS_DEPENDENCY(CalculateSpillWeights)
-INITIALIZE_PASS_DEPENDENCY(LiveStacks)
-INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
-INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
-#ifndef NDEBUG
-INITIALIZE_PASS_DEPENDENCY(RenderMachineFunction)
-#endif
-INITIALIZE_PASS_END(RABasic, "basic-regalloc",
- "Basic Register Allocator", false, false)
-#endif // INITIALIZE_PASS
-
RABasic::RABasic(): MachineFunctionPass(ID) {
+ initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry());
initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
initializeSlotIndexesPass(*PassRegistry::getPassRegistry());
- initializeStrongPHIEliminationPass(*PassRegistry::getPassRegistry());
- initializeRegisterCoalescerAnalysisGroup(*PassRegistry::getPassRegistry());
+ initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry());
+ initializeMachineSchedulerPass(*PassRegistry::getPassRegistry());
initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry());
initializeLiveStacksPass(*PassRegistry::getPassRegistry());
+ initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
initializeVirtRegMapPass(*PassRegistry::getPassRegistry());
- initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry());
+ initializeLiveRegMatrixPass(*PassRegistry::getPassRegistry());
}
-void RABasic::getAnalysisUsage(AnalysisUsage &au) const {
- au.setPreservesCFG();
- au.addRequired<LiveIntervals>();
- au.addPreserved<SlotIndexes>();
- if (StrongPHIElim)
- au.addRequiredID(StrongPHIEliminationID);
- au.addRequiredTransitive<RegisterCoalescer>();
- au.addRequired<CalculateSpillWeights>();
- au.addRequired<LiveStacks>();
- au.addPreserved<LiveStacks>();
- au.addRequired<MachineLoopInfo>();
- au.addPreserved<MachineLoopInfo>();
- au.addRequired<VirtRegMap>();
- au.addPreserved<VirtRegMap>();
- DEBUG(au.addRequired<RenderMachineFunction>());
- MachineFunctionPass::getAnalysisUsage(au);
+void RABasic::getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesCFG();
+ AU.addRequired<AliasAnalysis>();
+ AU.addPreserved<AliasAnalysis>();
+ AU.addRequired<LiveIntervals>();
+ AU.addPreserved<LiveIntervals>();
+ AU.addPreserved<SlotIndexes>();
+ AU.addRequired<LiveDebugVariables>();
+ AU.addPreserved<LiveDebugVariables>();
+ AU.addRequired<CalculateSpillWeights>();
+ AU.addRequired<LiveStacks>();
+ AU.addPreserved<LiveStacks>();
+ 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() {
- spiller_.reset(0);
- RegAllocBase::releaseMemory();
+ SpillerInstance.reset(0);
}
-//===----------------------------------------------------------------------===//
-// RegAllocBase Implementation
-//===----------------------------------------------------------------------===//
-// Instantiate a LiveIntervalUnion for each physical register.
-void RegAllocBase::LIUArray::init(unsigned nRegs) {
- array_.reset(new LiveIntervalUnion[nRegs]);
- nRegs_ = nRegs;
- for (unsigned pr = 0; pr < nRegs; ++pr) {
- array_[pr].init(pr);
+// 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<LiveInterval*> &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();
+ if (Q.seenUnspillableVReg())
+ return false;
+ 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);
+ }
}
-}
+ DEBUG(dbgs() << "spilling " << TRI->getName(PhysReg) <<
+ " interferences with " << VirtReg << "\n");
+ assert(!Intfs.empty() && "expected interference");
-void RegAllocBase::init(const TargetRegisterInfo &tri, VirtRegMap &vrm,
- LiveIntervals &lis) {
- tri_ = &tri;
- vrm_ = &vrm;
- lis_ = &lis;
- physReg2liu_.init(tri_->getNumRegs());
-}
+ // Spill each interfering vreg allocated to PhysReg or an alias.
+ for (unsigned i = 0, e = Intfs.size(); i != e; ++i) {
+ LiveInterval &Spill = *Intfs[i];
-void RegAllocBase::LIUArray::clear() {
- nRegs_ = 0;
- array_.reset(0);
-}
+ // Skip duplicates.
+ if (!VRM->hasPhys(Spill.reg))
+ continue;
-void RegAllocBase::releaseMemory() {
- physReg2liu_.clear();
-}
+ // Deallocate the interfering vreg by removing it from the union.
+ // A LiveInterval instance may not be in a union during modification!
+ Matrix->unassign(Spill);
-// Check if this live virtual reg interferes with a physical register. If not,
-// then check for interference on each register that aliases with the physical
-// register.
-bool RegAllocBase::checkPhysRegInterference(LiveIntervalUnion::Query &query,
- unsigned preg) {
- if (query.checkInterference())
- return true;
- for (const unsigned *asI = tri_->getAliasSet(preg); *asI; ++asI) {
- // We assume it's very unlikely for a register in the alias set to also be
- // in the original register class. So we don't bother caching the
- // interference.
- LiveIntervalUnion::Query subQuery(query.lvr(), physReg2liu_[*asI] );
- if (subQuery.checkInterference())
- return true;
+ // Spill the extracted interval.
+ LiveRangeEdit LRE(&Spill, SplitVRegs, *MF, *LIS, VRM);
+ spiller().spill(LRE);
}
- return false;
+ return true;
}
-//===----------------------------------------------------------------------===//
-// RABasic Implementation
-//===----------------------------------------------------------------------===//
-
// Driver for the register assignment and splitting heuristics.
// Manages iteration over the LiveIntervalUnions.
-//
-// Minimal implementation of register assignment and splitting--spills whenever
-// we run out of registers.
+//
+// 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.
-unsigned RABasic::selectOrSplit(LiveInterval &lvr, LiveVirtRegs &splitLVRs) {
- // Check for an available reg in this class.
- const TargetRegisterClass *trc = mri_->getRegClass(lvr.reg);
- for (TargetRegisterClass::iterator trcI = trc->allocation_order_begin(*mf_),
- trcEnd = trc->allocation_order_end(*mf_);
- trcI != trcEnd; ++trcI) {
- unsigned preg = *trcI;
- LiveIntervalUnion::Query query(lvr, physReg2liu_[preg]);
- if (!checkPhysRegInterference(query, preg)) {
- DEBUG(dbgs() << "\tallocating: " << tri_->getName(preg) << lvr << '\n');
- return preg;
+// minimal, there is no value in caching them outside the scope of
+// selectOrSplit().
+unsigned RABasic::selectOrSplit(LiveInterval &VirtReg,
+ SmallVectorImpl<LiveInterval*> &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);
+ 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;
}
}
- DEBUG(dbgs() << "\tspilling: " << lvr << '\n');
- SmallVector<LiveInterval*, 1> spillIs; // ignored
- spiller_->spill(&lvr, splitLVRs, spillIs);
- // FIXME: update LiveStacks
+ // 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.
+ DEBUG(dbgs() << "spilling: " << VirtReg << '\n');
+ if (!VirtReg.isSpillable())
+ return ~0u;
+ LiveRangeEdit LRE(&VirtReg, SplitVRegs, *MF, *LIS, VRM);
+ 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) {
DEBUG(dbgs() << "********** BASIC REGISTER ALLOCATION **********\n"
<< "********** Function: "
- << ((Value*)mf.getFunction())->getName() << '\n');
+ << mf.getName() << '\n');
- mf_ = &mf;
- tm_ = &mf.getTarget();
- mri_ = &mf.getRegInfo();
+ MF = &mf;
+ RegAllocBase::init(getAnalysis<VirtRegMap>(),
+ getAnalysis<LiveIntervals>(),
+ getAnalysis<LiveRegMatrix>());
+ SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM));
- DEBUG(rmf_ = &getAnalysis<RenderMachineFunction>());
-
- RegAllocBase::init(*tm_->getRegisterInfo(), getAnalysis<VirtRegMap>(),
- getAnalysis<LiveIntervals>());
-
- spiller_.reset(createSpiller(*this, *mf_, *vrm_));
-
- allocatePhysRegs(LessSpillWeightPriority());
+ allocatePhysRegs();
// Diagnostic output before rewriting
- DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm_ << "\n");
-
- // optional HTML output
- DEBUG(rmf_->renderMachineFunction("After basic register allocation.", vrm_));
+ DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *VRM << "\n");
- // Run rewriter
- std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
- rewriter->runOnMachineFunction(*mf_, *vrm_, lis_);
-
+ releaseMemory();
return true;
}
-FunctionPass* llvm::createBasicRegisterAllocator()
+FunctionPass* llvm::createBasicRegisterAllocator()
{
return new RABasic();
}