New PBQP solver.

* Fixed a reduction bug which occasionally led to infinite-cost (invalid)
  register allocation solutions despite the existence finite-cost solutions.
* Significantly reduced memory usage (>50% reduction).
* Simplified a lot of the solver code.



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@94514 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 17 insertions, 24 deletions

diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp
index fc59653f82..74e155fd3f 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.
@@ -510,11 +513,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 +555,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 +659,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 +693,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 +702,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 +842,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 +869,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 +887,7 @@ bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) {
   li2Node.clear();
   node2LI.clear();
   allowedSets.clear();
+  problemNodes.clear();
 
   DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n");