//
// The PBQP solver (pbqp.c) provided for this allocator uses a heuristic tuned
// for register allocation. For more information on PBQP for register
-// allocation see the following papers:
+// allocation, see the following papers:
//
// (1) Hames, L. and Scholz, B. 2006. Nearly optimal register allocation with
// PBQP. In Proceedings of the 7th Joint Modular Languages Conference
// Compilers and Tools for Embedded Systems (LCTES'02), ACM Press, New York,
// NY, USA, 139-148.
//
-// Author: Lang Hames
-// Email: lhames@gmail.com
-//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "regalloc"
#include "PBQP.h"
#include "VirtRegMap.h"
+#include "VirtRegRewriter.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/LiveStackAnalysis.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
au.addPreserved<LiveStacks>();
au.addRequired<MachineLoopInfo>();
au.addPreserved<MachineLoopInfo>();
+ au.addRequired<VirtRegMap>();
MachineFunctionPass::getAnalysisUsage(au);
}
//! \brief Adds a stack interval if the given live interval has been
//! spilled. Used to support stack slot coloring.
- void addStackInterval(const LiveInterval *spilled, float &weight);
+ void addStackInterval(const LiveInterval *spilled,MachineRegisterInfo* mri);
//! \brief Given a solved PBQP problem maps this solution back to a register
//! assignment.
iItr != iEnd; ++iItr) {
const MachineInstr *instr = &*iItr;
- unsigned srcReg, dstReg;
+ unsigned srcReg, dstReg, srcSubReg, dstSubReg;
// If this isn't a copy then continue to the next instruction.
- if (!tii->isMoveInstr(*instr, srcReg, dstReg))
+ if (!tii->isMoveInstr(*instr, srcReg, dstReg, srcSubReg, dstSubReg))
continue;
// If the registers are already the same our job is nice and easy.
return solver;
}
-void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled, float &weight) {
+void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled,
+ MachineRegisterInfo* mri) {
int stackSlot = vrm->getStackSlot(spilled->reg);
if (stackSlot == VirtRegMap::NO_STACK_SLOT)
return;
- LiveInterval &stackInterval = lss->getOrCreateInterval(stackSlot);
- stackInterval.weight += weight;
+ const TargetRegisterClass *RC = mri->getRegClass(spilled->reg);
+ LiveInterval &stackInterval = lss->getOrCreateInterval(stackSlot, RC);
VNInfo *vni;
if (stackInterval.getNumValNums() != 0)
vni = stackInterval.getValNumInfo(0);
else
- vni = stackInterval.getNextValue(-0U, 0, lss->getVNInfoAllocator());
+ vni = stackInterval.getNextValue(0, 0, false, lss->getVNInfoAllocator());
LiveInterval &rhsInterval = lis->getInterval(spilled->reg);
stackInterval.MergeRangesInAsValue(rhsInterval, vni);
// of allocation
vregIntervalsToAlloc.erase(&lis->getInterval(virtReg));
- float ssWeight;
-
// Insert spill ranges for this live range
const LiveInterval *spillInterval = node2LI[node];
double oldSpillWeight = spillInterval->weight;
SmallVector<LiveInterval*, 8> spillIs;
std::vector<LiveInterval*> newSpills =
- lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm,
- ssWeight);
- addStackInterval(spillInterval, ssWeight);
+ lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm);
+ addStackInterval(spillInterval, mri);
DOUT << "VREG " << virtReg << " -> SPILLED (Cost: "
<< oldSpillWeight << ", New vregs: ";
// First allocate registers for the empty intervals.
for (LiveIntervalSet::const_iterator
- itr = emptyVRegIntervals.begin(), end = emptyVRegIntervals.end();
+ itr = emptyVRegIntervals.begin(), end = emptyVRegIntervals.end();
itr != end; ++itr) {
LiveInterval *li = *itr;
- unsigned physReg = li->preference;
-
+ unsigned physReg = vrm->getRegAllocPref(li->reg);
if (physReg == 0) {
const TargetRegisterClass *liRC = mri->getRegClass(li->reg);
physReg = *liRC->allocation_order_begin(*mf);
continue;
}
+ // Ignore unallocated vregs:
+ if (reg == 0) {
+ continue;
+ }
+
// Iterate over the ranges of the current interval...
for (LRIterator lrItr = li->begin(), lrEnd = li->end();
lrItr != lrEnd; ++lrItr) {
lss = &getAnalysis<LiveStacks>();
loopInfo = &getAnalysis<MachineLoopInfo>();
- std::auto_ptr<VirtRegMap> vrmAutoPtr(new VirtRegMap(*mf));
- vrm = vrmAutoPtr.get();
+ vrm = &getAnalysis<VirtRegMap>();
DOUT << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n";
DOUT << "Post alloc VirtRegMap:\n" << *vrm << "\n";
- // Run spiller
- std::auto_ptr<Spiller> spiller(createSpiller());
- spiller->runOnMachineFunction(*mf, *vrm);
+ // Run rewriter
+ std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
+
+ rewriter->runOnMachineFunction(*mf, *vrm, lis);
return true;
}