Jakob's review of the basic register allocator.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@117384 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/RegAllocBasic.cpp b/lib/CodeGen/RegAllocBasic.cpp
index ce5f9cf..83999d9 100644
--- a/lib/CodeGen/RegAllocBasic.cpp
+++ b/lib/CodeGen/RegAllocBasic.cpp
@@ -13,6 +13,7 @@
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "regalloc"
+#include "LiveIntervalUnion.h"
#include "RegAllocBase.h"
#include "RenderMachineFunction.h"
#include "Spiller.h"
@@ -33,6 +34,14 @@
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
+#include "VirtRegMap.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
+#include "llvm/Target/TargetRegisterInfo.h"
+
+
+#include <vector>
+#include <queue>
+
using namespace llvm;
static RegisterRegAlloc basicRegAlloc("basic", "basic register allocator",
@@ -72,7 +81,8 @@
virtual void releaseMemory();
- virtual unsigned selectOrSplit(LiveInterval &lvr, LiveVirtRegs &splitLVRs);
+ virtual unsigned selectOrSplit(LiveInterval &lvr,
+ SmallVectorImpl<LiveInterval*> &splitLVRs);
/// Perform register allocation.
virtual bool runOnMachineFunction(MachineFunction &mf);
@@ -101,7 +111,7 @@
#endif
INITIALIZE_PASS_END(RABasic, "basic-regalloc",
"Basic Register Allocator", false, false)
-#endif // INITIALIZE_PASS
+#endif // disable INITIALIZE_PASS
RABasic::RABasic(): MachineFunctionPass(ID) {
initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
@@ -168,6 +178,79 @@
physReg2liu_.clear();
}
+namespace llvm {
+/// This class defines a queue of live virtual registers prioritized by spill
+/// weight. The heaviest vreg is popped first.
+///
+/// Currently, this is trivial wrapper that gives us an opaque type in the
+/// header, but we may later give it a virtual interface for register allocators
+/// to override the priority queue comparator.
+class LiveVirtRegQueue {
+ typedef std::priority_queue
+ <LiveInterval*, std::vector<LiveInterval*>, LessSpillWeightPriority> PQ;
+ PQ pq_;
+
+public:
+ // Is the queue empty?
+ bool empty() { return pq_.empty(); }
+
+ // Get the highest priority lvr (top + pop)
+ LiveInterval *get() {
+ LiveInterval *lvr = pq_.top();
+ pq_.pop();
+ return lvr;
+ }
+ // Add this lvr to the queue
+ void push(LiveInterval *lvr) {
+ pq_.push(lvr);
+ }
+};
+} // end namespace llvm
+
+// Visit all the live virtual 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::seedLiveVirtRegs(LiveVirtRegQueue &lvrQ) {
+ for (LiveIntervals::iterator liItr = lis_->begin(), liEnd = lis_->end();
+ liItr != liEnd; ++liItr) {
+ unsigned reg = liItr->first;
+ LiveInterval &li = *liItr->second;
+ if (TargetRegisterInfo::isPhysicalRegister(reg)) {
+ physReg2liu_[reg].unify(li);
+ }
+ else {
+ lvrQ.push(&li);
+ }
+ }
+}
+
+// Top-level driver to manage the queue of unassigned LiveVirtRegs and call the
+// selectOrSplit implementation.
+void RegAllocBase::allocatePhysRegs() {
+ LiveVirtRegQueue lvrQ;
+ seedLiveVirtRegs(lvrQ);
+ while (!lvrQ.empty()) {
+ LiveInterval *lvr = lvrQ.get();
+ typedef SmallVector<LiveInterval*, 4> LVRVec;
+ LVRVec splitLVRs;
+ unsigned availablePhysReg = selectOrSplit(*lvr, splitLVRs);
+ if (availablePhysReg) {
+ assert(splitLVRs.empty() && "inconsistent splitting");
+ assert(!vrm_->hasPhys(lvr->reg) && "duplicate vreg in interval unions");
+ vrm_->assignVirt2Phys(lvr->reg, availablePhysReg);
+ physReg2liu_[availablePhysReg].unify(*lvr);
+ }
+ else {
+ for (LVRVec::iterator lvrI = splitLVRs.begin(), lvrEnd = splitLVRs.end();
+ lvrI != lvrEnd; ++lvrI) {
+ assert(TargetRegisterInfo::isVirtualRegister((*lvrI)->reg) &&
+ "expect split value in virtual register");
+ lvrQ.push(*lvrI);
+ }
+ }
+ }
+}
+
// 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.
@@ -201,7 +284,8 @@
// 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) {
+unsigned RABasic::selectOrSplit(LiveInterval &lvr,
+ SmallVectorImpl<LiveInterval*> &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_),
@@ -238,7 +322,7 @@
spiller_.reset(createSpiller(*this, *mf_, *vrm_));
- allocatePhysRegs(LessSpillWeightPriority());
+ allocatePhysRegs();
// Diagnostic output before rewriting
DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm_ << "\n");
@@ -249,6 +333,9 @@
// Run rewriter
std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
rewriter->runOnMachineFunction(*mf_, *vrm_, lis_);
+
+ // The pass output is in VirtRegMap. Release all the transient data.
+ releaseMemory();
return true;
}