#include "llvm/ADT/OwningPtr.h"
#include "LiveIntervalUnion.h"
-#include <queue>
namespace llvm {
/// be extended to add interesting heuristics.
///
/// Register allocators must override the selectOrSplit() method to implement
-/// live range splitting. They may also override getPriority() which otherwise
-/// defaults to the spill weight computed by CalculateSpillWeights.
+/// live range splitting. They must also override enqueue/dequeue to provide an
+/// assignment order.
class RegAllocBase {
LiveIntervalUnion::Allocator UnionAllocator;
protected:
// Get a temporary reference to a Spiller instance.
virtual Spiller &spiller() = 0;
- // getPriority - Calculate the allocation priority for VirtReg.
- // Virtual registers with higher priorities are allocated first.
- virtual float getPriority(LiveInterval *LI) = 0;
+ /// enqueue - Add VirtReg to the priority queue of unassigned registers.
+ virtual void enqueue(LiveInterval *LI) = 0;
+
+ /// dequeue - Return the next unassigned register, or NULL.
+ virtual LiveInterval *dequeue() = 0;
// A RegAlloc pass should override this to provide the allocation heuristics.
// Each call must guarantee forward progess by returning an available PhysReg
static bool VerifyEnabled;
private:
- void seedLiveVirtRegs(std::priority_queue<std::pair<float, unsigned> >&);
+ void seedLiveRegs();
void spillReg(LiveInterval &VirtReg, unsigned PhysReg,
SmallVectorImpl<LiveInterval*> &SplitVRegs);
#include "llvm/Support/Timer.h"
#include <cstdlib>
+#include <queue>
using namespace llvm;
const char *RegAllocBase::TimerGroupName = "Register Allocation";
bool RegAllocBase::VerifyEnabled = false;
+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
// state
std::auto_ptr<Spiller> SpillerInstance;
-
+ std::priority_queue<LiveInterval*, std::vector<LiveInterval*>,
+ CompSpillWeight> Queue;
public:
RABasic();
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);
PhysReg2LiveUnion.clear();
}
-// 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(std::priority_queue<std::pair<float, unsigned> > &VirtRegQ) {
+// 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() {
for (LiveIntervals::iterator I = LIS->begin(), E = LIS->end(); I != E; ++I) {
unsigned RegNum = I->first;
LiveInterval &VirtReg = *I->second;
if (TargetRegisterInfo::isPhysicalRegister(RegNum))
PhysReg2LiveUnion[RegNum].unify(VirtReg);
else
- VirtRegQ.push(std::make_pair(getPriority(&VirtReg), RegNum));
+ enqueue(&VirtReg);
}
}
// Top-level driver to manage the queue of unassigned VirtRegs and call the
// selectOrSplit implementation.
void RegAllocBase::allocatePhysRegs() {
-
- // Push each vreg onto a queue or "precolor" by adding it to a physreg union.
- std::priority_queue<std::pair<float, unsigned> > VirtRegQ;
- seedLiveVirtRegs(VirtRegQ);
+ seedLiveRegs();
// Continue assigning vregs one at a time to available physical registers.
- while (!VirtRegQ.empty()) {
- // Pop the highest priority vreg.
- LiveInterval &VirtReg = LIS->getInterval(VirtRegQ.top().second);
- VirtRegQ.pop();
-
+ while (LiveInterval *VirtReg = dequeue()) {
// selectOrSplit requests the allocator to return an available physical
// register if possible and populate a list of new live intervals that
// result from splitting.
- DEBUG(dbgs() << "\nselectOrSplit " << MRI->getRegClass(VirtReg.reg)->getName()
- << ':' << VirtReg << '\n');
+ DEBUG(dbgs() << "\nselectOrSplit "
+ << MRI->getRegClass(VirtReg->reg)->getName()
+ << ':' << *VirtReg << '\n');
typedef SmallVector<LiveInterval*, 4> VirtRegVec;
VirtRegVec SplitVRegs;
- unsigned AvailablePhysReg = selectOrSplit(VirtReg, SplitVRegs);
+ unsigned AvailablePhysReg = selectOrSplit(*VirtReg, SplitVRegs);
if (AvailablePhysReg)
- assign(VirtReg, AvailablePhysReg);
+ assign(*VirtReg, AvailablePhysReg);
for (VirtRegVec::iterator I = SplitVRegs.begin(), E = SplitVRegs.end();
I != E; ++I) {
- LiveInterval* SplitVirtReg = *I;
+ LiveInterval *SplitVirtReg = *I;
if (SplitVirtReg->empty()) continue;
DEBUG(dbgs() << "queuing new interval: " << *SplitVirtReg << "\n");
assert(TargetRegisterInfo::isVirtualRegister(SplitVirtReg->reg) &&
"expect split value in virtual register");
- VirtRegQ.push(std::make_pair(getPriority(SplitVirtReg),
- SplitVirtReg->reg));
+ enqueue(SplitVirtReg);
++NumNewQueued;
}
}
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/Timer.h"
+#include <queue>
+
using namespace llvm;
STATISTIC(NumGlobalSplits, "Number of split global live ranges");
// state
std::auto_ptr<Spiller> SpillerInstance;
std::auto_ptr<SplitAnalysis> SA;
+ std::priority_queue<std::pair<unsigned, unsigned> > Queue;
// splitting state.
/// RAGreedy analysis usage.
virtual void getAnalysisUsage(AnalysisUsage &AU) const;
-
virtual void releaseMemory();
-
virtual Spiller &spiller() { return *SpillerInstance; }
-
- virtual float getPriority(LiveInterval *LI);
-
+ virtual void enqueue(LiveInterval *LI);
+ virtual LiveInterval *dequeue();
virtual unsigned selectOrSplit(LiveInterval&,
SmallVectorImpl<LiveInterval*>&);
RegAllocBase::releaseMemory();
}
-float RAGreedy::getPriority(LiveInterval *LI) {
- float Priority = LI->weight;
+void RAGreedy::enqueue(LiveInterval *LI) {
+ // Prioritize live ranges by size, assigning larger ranges first.
+ // The queue holds (size, reg) pairs.
+ unsigned Size = LI->getSize();
+ unsigned Reg = LI->reg;
+ assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
+ "Can only enqueue virtual registers");
- // Prioritize hinted registers so they are allocated first.
- std::pair<unsigned, unsigned> Hint;
- if (Hint.first || Hint.second) {
- // The hint can be target specific, a virtual register, or a physreg.
- Priority *= 2;
+ // Boost ranges that have a physical register hint.
+ unsigned Hint = VRM->getRegAllocPref(Reg);
+ if (TargetRegisterInfo::isPhysicalRegister(Hint))
+ Size |= (1u << 30);
- // Prefer physreg hints above anything else.
- if (Hint.first == 0 && TargetRegisterInfo::isPhysicalRegister(Hint.second))
- Priority *= 2;
- }
- return Priority;
+ Queue.push(std::make_pair(Size, Reg));
}
+LiveInterval *RAGreedy::dequeue() {
+ if (Queue.empty())
+ return 0;
+ LiveInterval *LI = &LIS->getInterval(Queue.top().second);
+ Queue.pop();
+ return LI;
+}
//===----------------------------------------------------------------------===//
// Register Reassignment
projects / oota-llvm.git / commitdiff