summaryrefslogtreecommitdiffstats
path: root/lib/CodeGen/RegAllocPBQP.cpp
diff options
context:
space:
mode:
authorrdivacky <rdivacky@FreeBSD.org>2010-02-16 09:30:23 +0000
committerrdivacky <rdivacky@FreeBSD.org>2010-02-16 09:30:23 +0000
commitf25ddd991a5601d0101602c4c263a58c7af4b8a2 (patch)
tree4cfca640904d1896e25032757a61f8959c066919 /lib/CodeGen/RegAllocPBQP.cpp
parent3fd58f91dd318518f7daa4ba64c0aaf31799d89b (diff)
downloadFreeBSD-src-f25ddd991a5601d0101602c4c263a58c7af4b8a2.zip
FreeBSD-src-f25ddd991a5601d0101602c4c263a58c7af4b8a2.tar.gz
Update LLVM to r96341.
Diffstat (limited to 'lib/CodeGen/RegAllocPBQP.cpp')
-rw-r--r--lib/CodeGen/RegAllocPBQP.cpp64
1 files changed, 34 insertions, 30 deletions
diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp
index fc59653..2701faf 100644
--- a/lib/CodeGen/RegAllocPBQP.cpp
+++ b/lib/CodeGen/RegAllocPBQP.cpp
@@ -32,7 +32,7 @@
#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"
@@ -58,12 +58,12 @@ using namespace llvm;
static RegisterRegAlloc
registerPBQPRepAlloc("pbqp", "PBQP register allocator.",
- llvm::createPBQPRegisterAllocator);
+ llvm::createPBQPRegisterAllocator);
static cl::opt<bool>
pbqpCoalescing("pbqp-coalescing",
- cl::desc("Attempt coalescing during PBQP register allocation."),
- cl::init(false), cl::Hidden);
+ cl::desc("Attempt coalescing during PBQP register allocation."),
+ cl::init(false), cl::Hidden);
namespace {
@@ -114,6 +114,8 @@ namespace {
typedef std::set<LiveInterval*> LiveIntervalSet;
+ typedef std::vector<PBQP::Graph::NodeItr> NodeVector;
+
MachineFunction *mf;
const TargetMachine *tm;
const TargetRegisterInfo *tri;
@@ -130,6 +132,7 @@ namespace {
AllowedSetMap allowedSets;
LiveIntervalSet vregIntervalsToAlloc,
emptyVRegIntervals;
+ NodeVector problemNodes;
/// Builds a PBQP cost vector.
@@ -174,7 +177,7 @@ namespace {
/// 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.
@@ -408,16 +411,16 @@ PBQPRegAlloc::CoalesceMap PBQPRegAlloc::findCoalesces() {
// 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;
}
@@ -439,6 +442,12 @@ PBQPRegAlloc::CoalesceMap PBQPRegAlloc::findCoalesces() {
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)) {
@@ -460,6 +469,11 @@ PBQPRegAlloc::CoalesceMap PBQPRegAlloc::findCoalesces() {
if ((*vniItr)->getCopy() == instr)
continue;
+ if (!(*vniItr)->def.isValid()) {
+ badDef = true;
+ break;
+ }
+
if (srcLI->liveAt((*vniItr)->def)) {
badDef = true;
break;
@@ -510,11 +524,10 @@ void PBQPRegAlloc::findVRegIntervalsToAlloc() {
}
}
-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;
@@ -553,8 +566,8 @@ PBQP::SimpleGraph PBQPRegAlloc::constructPBQPProblem() {
}
// 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());
@@ -657,12 +670,7 @@ PBQP::SimpleGraph PBQPRegAlloc::constructPBQPProblem() {
}
}
- 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";
@@ -696,10 +704,6 @@ void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled,
bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) {
- // 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;
@@ -709,7 +713,7 @@ bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) {
// 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...
@@ -849,7 +853,7 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) {
vrm = &getAnalysis<VirtRegMap>();
- DEBUG(dbgs() << "PBQP2 Register Allocating for " << mf->getFunction()->getName() << "\n");
+ DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n");
// Allocator main loop:
//
@@ -876,10 +880,9 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) {
while (!pbqpAllocComplete) {
DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n");
- PBQP::SimpleGraph problem = constructPBQPProblem();
- PBQP::HeuristicSolver<PBQP::Heuristics::Briggs> solver;
- problem.assignNodeIDs();
- PBQP::Solution solution = solver.solve(problem);
+ PBQP::Graph problem = constructPBQPProblem();
+ PBQP::Solution solution =
+ PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve(problem);
pbqpAllocComplete = mapPBQPToRegAlloc(solution);
@@ -895,6 +898,7 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) {
li2Node.clear();
node2LI.clear();
allowedSets.clear();
+ problemNodes.clear();
DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n");
OpenPOWER on IntegriCloud