#define DEBUG_TYPE "regalloc"
#include "PBQP/HeuristicSolver.h"
-#include "PBQP/SimpleGraph.h"
+#include "PBQP/Graph.h"
#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"
using namespace llvm;
static RegisterRegAlloc
-registerPBQPRepAlloc("pbqp", "PBQP register allocator.",
- llvm::createPBQPRegisterAllocator);
+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((intptr_t)&ID) {}
+ PBQPRegAlloc() : MachineFunctionPass(&ID) {}
/// Return the pass name.
- virtual const char* getPassName() const throw() {
+ virtual const char* getPassName() const {
return "PBQP Register Allocator";
}
/// 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>();
typedef std::set<LiveInterval*> LiveIntervalSet;
+ typedef std::vector<PBQP::Graph::NodeItr> NodeVector;
+
MachineFunction *mf;
const TargetMachine *tm;
const TargetRegisterInfo *tri;
AllowedSetMap allowedSets;
LiveIntervalSet vregIntervalsToAlloc,
emptyVRegIntervals;
+ NodeVector problemNodes;
/// Builds a PBQP cost vector.
/// allocation problem for this function.
///
/// @return a PBQP solver object for the register allocation problem.
- PBQP::SimpleGraph constructPBQPProblem();
+ PBQP::Graph constructPBQPProblem();
/// \brief Adds a stack interval if the given live interval has been
/// spilled. Used to support stack slot coloring.
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;
}
// We also need any physical regs to be allocable, coalescing with
// a non-allocable register is invalid.
if (srcRegIsPhysical) {
- if (std::find(srcRegClass->allocation_order_begin(*mf),
- srcRegClass->allocation_order_end(*mf), srcReg) ==
- srcRegClass->allocation_order_end(*mf))
+ if (std::find(dstRegClass->allocation_order_begin(*mf),
+ dstRegClass->allocation_order_end(*mf), srcReg) ==
+ dstRegClass->allocation_order_end(*mf))
continue;
}
if (dstRegIsPhysical) {
- if (std::find(dstRegClass->allocation_order_begin(*mf),
- dstRegClass->allocation_order_end(*mf), dstReg) ==
- dstRegClass->allocation_order_end(*mf))
+ if (std::find(srcRegClass->allocation_order_begin(*mf),
+ srcRegClass->allocation_order_end(*mf), dstReg) ==
+ srcRegClass->allocation_order_end(*mf))
continue;
}
vniItr = srcLI->vni_begin(), vniEnd = srcLI->vni_end();
vniItr != vniEnd; ++vniItr) {
+ // If we find a poorly defined def we err on the side of caution.
+ if (!(*vniItr)->def.isValid()) {
+ badDef = true;
+ break;
+ }
+
// If we find a def that kills the coalescing opportunity then
// record it and break from the loop.
if (dstLI->liveAt((*vniItr)->def)) {
vniItr != vniEnd; ++vniItr) {
// We want to make sure we skip the copy instruction itself.
- if ((*vniItr)->copy == instr)
+ if ((*vniItr)->getCopy() == instr)
continue;
+ if (!(*vniItr)->def.isValid()) {
+ badDef = true;
+ break;
+ }
+
if (srcLI->liveAt((*vniItr)->def)) {
badDef = true;
break;
}
}
-PBQP::SimpleGraph PBQPRegAlloc::constructPBQPProblem() {
+PBQP::Graph PBQPRegAlloc::constructPBQPProblem() {
typedef std::vector<const LiveInterval*> LIVector;
typedef std::vector<unsigned> RegVector;
- typedef std::vector<PBQP::SimpleGraph::NodeIterator> NodeVector;
// This will store the physical intervals for easy reference.
LIVector physIntervals;
}
// 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;
- NodeVector problemNodes(vregIntervalsToAlloc.size());
+ PBQP::Graph problem;
+ problemNodes.resize(vregIntervalsToAlloc.size());
// Resize allowedSets container appropriately.
allowedSets.resize(vregIntervalsToAlloc.size());
}
}
- problem.assignNodeIDs();
-
assert(problem.getNumNodes() == allowedSets.size());
- for (unsigned i = 0; i < allowedSets.size(); ++i) {
- assert(problem.getNodeItr(i) == problemNodes[i]);
- }
/*
std::cerr << "Allocating for " << problem.getNumNodes() << " nodes, "
<< problem.getNumEdges() << " edges.\n";
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;
-
// Set to true if we have any spills
bool anotherRoundNeeded = false;
// Clear the existing allocation.
vrm->clearAllVirt();
- CoalesceMap coalesces;//(findCoalesces());
-
- for (unsigned i = 0; i < node2LI.size(); ++i) {
- if (solution.getSelection(i) == 0) {
- continue;
- }
-
- unsigned iSel = solution.getSelection(i);
- unsigned iAlloc = allowedSets[i][iSel - 1];
-
- for (unsigned j = i + 1; j < node2LI.size(); ++j) {
-
- if (solution.getSelection(j) == 0) {
- continue;
- }
-
- unsigned jSel = solution.getSelection(j);
- unsigned jAlloc = allowedSets[j][jSel - 1];
-
- if ((iAlloc != jAlloc) && !tri->areAliases(iAlloc, jAlloc)) {
- continue;
- }
-
- if (node2LI[i]->overlaps(*node2LI[j])) {
- if (coalesces.find(RegPair(node2LI[i]->reg, node2LI[j]->reg)) == coalesces.end()) {
- DEBUG(errs() << "In round " << ++round << ":\n"
- << "Bogusness in " << mf->getFunction()->getName() << "!\n"
- << "Live interval " << i << " (reg" << node2LI[i]->reg << ") and\n"
- << "Live interval " << j << " (reg" << node2LI[j]->reg << ")\n"
- << " were allocated registers " << iAlloc << " (index " << iSel << ") and "
- << jAlloc << "(index " << jSel
- << ") respectively in a graph of " << solution.numNodes() << " nodes.\n"
- << "li[i]->empty() = " << node2LI[i]->empty() << "\n"
- << "li[j]->empty() = " << node2LI[j]->empty() << "\n"
- << "li[i]->overlaps(li[j]) = " << node2LI[i]->overlaps(*node2LI[j]) << "\n"
- << "coalesce = " << (coalesces.find(RegPair(node2LI[i]->reg, node2LI[j]->reg)) != coalesces.end()) << "\n");
-
- DEBUG(errs() << "solution.getCost() = " << solution.getCost() << "\n");
- exit(1);
- }
- }
- }
- }
-
-
// 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,
- allocSelection = solution.getSelection(node);
+ allocSelection = solution.getSelection(problemNodes[node]);
// If the PBQP solution is non-zero it's a physical register...
// 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(dbgs() << "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(dbgs() << "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(dbgs() << (*itr)->reg << " ");
vregIntervalsToAlloc.insert(*itr);
}
- DOUT << ")\n";
+ DEBUG(dbgs() << ")\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>();
vrm = &getAnalysis<VirtRegMap>();
- DEBUG(errs() << "PBQP2 Register Allocating for " << mf->getFunction()->getName() << "\n");
+ DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n");
// Allocator main loop:
//
// Find the vreg intervals in need of allocation.
findVRegIntervalsToAlloc();
- // If there aren't any then we're done here.
- if (vregIntervalsToAlloc.empty() && emptyVRegIntervals.empty())
- return true;
-
// If there are non-empty intervals allocate them using pbqp.
if (!vregIntervalsToAlloc.empty()) {
unsigned round = 0;
while (!pbqpAllocComplete) {
- DEBUG(errs() << " PBQP Regalloc round " << round << ":\n");
+ DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n");
+
+ PBQP::Graph problem = constructPBQPProblem();
+ PBQP::Solution solution =
+ PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve(problem);
- PBQP::SimpleGraph problem = constructPBQPProblem();
- 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;
li2Node.clear();
node2LI.clear();
allowedSets.clear();
+ problemNodes.clear();
- DEBUG(errs() << "Post alloc VirtRegMap:\n" << *vrm << "\n");
+ DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n");
// Run rewriter
std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
projects / oota-llvm.git / blobdiff