#include "PBQP/Heuristics/Briggs.h"
#include "VirtRegMap.h"
#include "VirtRegRewriter.h"
+#include "llvm/CodeGen/CalcSpillWeights.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/LiveStackAnalysis.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
registerPBQPRepAlloc("pbqp", "PBQP register allocator.",
llvm::createPBQPRegisterAllocator);
+static cl::opt<bool>
+pbqpCoalescing("pbqp-coalescing",
+ cl::desc("Attempt coalescing during PBQP register allocation."),
+ cl::init(false), cl::Hidden);
+
namespace {
///
/// PBQP based allocators solve the register allocation problem by mapping
/// register allocation problems to Partitioned Boolean Quadratic
/// Programming problems.
- class VISIBILITY_HIDDEN PBQPRegAlloc : public MachineFunctionPass {
+ class PBQPRegAlloc : public MachineFunctionPass {
public:
static char ID;
-
+
/// Construct a PBQP register allocator.
PBQPRegAlloc() : MachineFunctionPass(&ID) {}
/// PBQP analysis usage.
virtual void getAnalysisUsage(AnalysisUsage &au) const {
+ au.addRequired<SlotIndexes>();
+ au.addPreserved<SlotIndexes>();
au.addRequired<LiveIntervals>();
//au.addRequiredID(SplitCriticalEdgesID);
+ au.addRequired<RegisterCoalescer>();
+ au.addRequired<CalculateSpillWeights>();
au.addRequired<LiveStacks>();
au.addPreserved<LiveStacks>();
au.addRequired<MachineLoopInfo>();
unsigned reg2 = *a2Itr;
// If the row/column regs are identical or alias insert an infinity.
- if ((reg1 == reg2) || tri->areAliases(reg1, reg2)) {
+ if (tri->regsOverlap(reg1, reg2)) {
(*m)[ri][ci] = std::numeric_limits<PBQP::PBQPNum>::infinity();
isZeroMatrix = false;
}
}
// Get the set of potential coalesces.
- CoalesceMap coalesces;//(findCoalesces());
+ CoalesceMap coalesces;
+
+ if (pbqpCoalescing) {
+ coalesces = findCoalesces();
+ }
// Construct a PBQP solver for this problem
PBQP::SimpleGraph problem;
if (stackInterval.getNumValNums() != 0)
vni = stackInterval.getValNumInfo(0);
else
- vni = stackInterval.getNextValue(0, 0, false, lss->getVNInfoAllocator());
+ vni = stackInterval.getNextValue(
+ SlotIndex(), 0, false, lss->getVNInfoAllocator());
LiveInterval &rhsInterval = lis->getInterval(spilled->reg);
stackInterval.MergeRangesInAsValue(rhsInterval, vni);
bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) {
- static unsigned round = 0;
- (void) round;
+ // Assert that this is a valid solution to the regalloc problem.
+ assert(solution.getCost() != std::numeric_limits<PBQP::PBQPNum>::infinity() &&
+ "Invalid (infinite cost) solution for PBQP problem.");
// Set to true if we have any spills
bool anotherRoundNeeded = false;
// Clear the existing allocation.
vrm->clearAllVirt();
-
+
// Iterate over the nodes mapping the PBQP solution to a register assignment.
for (unsigned node = 0; node < node2LI.size(); ++node) {
unsigned virtReg = node2LI[node]->reg,
// Get the physical reg, subtracting 1 to account for the spill option.
unsigned physReg = allowedSets[node][allocSelection - 1];
- DOUT << "VREG " << virtReg << " -> " << tri->getName(physReg) << "\n";
+ DEBUG(errs() << "VREG " << virtReg << " -> "
+ << tri->getName(physReg) << "\n");
assert(physReg != 0);
lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm);
addStackInterval(spillInterval, mri);
- DOUT << "VREG " << virtReg << " -> SPILLED (Cost: "
- << oldSpillWeight << ", New vregs: ";
+ (void) oldSpillWeight;
+ DEBUG(errs() << "VREG " << virtReg << " -> SPILLED (Cost: "
+ << oldSpillWeight << ", New vregs: ");
// Copy any newly inserted live intervals into the list of regs to
// allocate.
assert(!(*itr)->empty() && "Empty spill range.");
- DOUT << (*itr)->reg << " ";
+ DEBUG(errs() << (*itr)->reg << " ");
vregIntervalsToAlloc.insert(*itr);
}
- DOUT << ")\n";
+ DEBUG(errs() << ")\n");
// We need another round if spill intervals were added.
anotherRoundNeeded |= !newSpills.empty();
// 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;
tm = &mf->getTarget();
tri = tm->getRegisterInfo();
tii = tm->getInstrInfo();
- mri = &mf->getRegInfo();
+ mri = &mf->getRegInfo();
lis = &getAnalysis<LiveIntervals>();
lss = &getAnalysis<LiveStacks>();
PBQP::HeuristicSolver<PBQP::Heuristics::Briggs> solver;
problem.assignNodeIDs();
PBQP::Solution solution = solver.solve(problem);
-/*
- std::cerr << "Solution:\n";
- for (unsigned i = 0; i < solution.numNodes(); ++i) {
- std::cerr << " " << i << " -> " << solution.getSelection(i) << "\n";
- }
-*/
+
pbqpAllocComplete = mapPBQPToRegAlloc(solution);
++round;