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

12 files changed, 1503 insertions, 2056 deletions

diff --git a/lib/CodeGen/PBQP/AnnotatedGraph.h b/lib/CodeGen/PBQP/AnnotatedGraph.h
deleted file mode 100644
index 738dea0d37..0000000000
--- a/lib/CodeGen/PBQP/AnnotatedGraph.h
+++ /dev/null
@@ -1,184 +0,0 @@
-//===-- AnnotatedGraph.h - Annotated PBQP Graph -----------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Annotated PBQP Graph class. This class is used internally by the PBQP solver
-// to cache information to speed up reduction.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CODEGEN_PBQP_ANNOTATEDGRAPH_H
-#define LLVM_CODEGEN_PBQP_ANNOTATEDGRAPH_H
-
-#include "GraphBase.h"
-
-namespace PBQP {
-
-
-template <typename NodeData, typename EdgeData> class AnnotatedEdge;
-
-template <typename NodeData, typename EdgeData>
-class AnnotatedNode : public NodeBase<AnnotatedNode<NodeData, EdgeData>,
-                                      AnnotatedEdge<NodeData, EdgeData> > {
-private:
-
-  NodeData nodeData; 
-
-public:
-
-  AnnotatedNode(const Vector &costs, const NodeData &nodeData) :
-    NodeBase<AnnotatedNode<NodeData, EdgeData>,
-             AnnotatedEdge<NodeData, EdgeData> >(costs),
-             nodeData(nodeData) {}
-
-  NodeData& getNodeData() { return nodeData; }
-  const NodeData& getNodeData() const { return nodeData; }
-
-};
-
-template <typename NodeData, typename EdgeData>
-class AnnotatedEdge : public EdgeBase<AnnotatedNode<NodeData, EdgeData>,
-                                      AnnotatedEdge<NodeData, EdgeData> > {
-private:
-
-  typedef typename GraphBase<AnnotatedNode<NodeData, EdgeData>,
-                             AnnotatedEdge<NodeData, EdgeData> >::NodeIterator
-    NodeIterator;
-
-  EdgeData edgeData; 
-
-public:
-
-
-  AnnotatedEdge(const NodeIterator &node1Itr, const NodeIterator &node2Itr,
-                const Matrix &costs, const EdgeData &edgeData) :
-    EdgeBase<AnnotatedNode<NodeData, EdgeData>,
-             AnnotatedEdge<NodeData, EdgeData> >(node1Itr, node2Itr, costs),
-    edgeData(edgeData) {}
-
-  EdgeData& getEdgeData() { return edgeData; }
-  const EdgeData& getEdgeData() const { return edgeData; }
-
-};
-
-template <typename NodeData, typename EdgeData>
-class AnnotatedGraph : public GraphBase<AnnotatedNode<NodeData, EdgeData>,
-                                        AnnotatedEdge<NodeData, EdgeData> > {
-private:
-
-  typedef GraphBase<AnnotatedNode<NodeData, EdgeData>,
-                    AnnotatedEdge<NodeData, EdgeData> > PGraph;
-
-  typedef AnnotatedNode<NodeData, EdgeData> NodeEntry;
-  typedef AnnotatedEdge<NodeData, EdgeData> EdgeEntry;
-
-
-  void copyFrom(const AnnotatedGraph &other) {
-    if (!other.areNodeIDsValid()) {
-      other.assignNodeIDs();
-    }
-    std::vector<NodeIterator> newNodeItrs(other.getNumNodes());
-
-    for (ConstNodeIterator nItr = other.nodesBegin(), nEnd = other.nodesEnd();
-         nItr != nEnd; ++nItr) {
-      newNodeItrs[other.getNodeID(nItr)] = addNode(other.getNodeCosts(nItr));
-    }
-
-    for (ConstEdgeIterator eItr = other.edgesBegin(), eEnd = other.edgesEnd();
-         eItr != eEnd; ++eItr) {
-
-      unsigned node1ID = other.getNodeID(other.getEdgeNode1(eItr)),
-               node2ID = other.getNodeID(other.getEdgeNode2(eItr));
-
-      addEdge(newNodeItrs[node1ID], newNodeItrs[node2ID],
-              other.getEdgeCosts(eItr), other.getEdgeData(eItr));
-    }
-
-  }
-
-public:
-
-  typedef typename PGraph::NodeIterator NodeIterator;
-  typedef typename PGraph::ConstNodeIterator ConstNodeIterator;
-  typedef typename PGraph::EdgeIterator EdgeIterator;
-  typedef typename PGraph::ConstEdgeIterator ConstEdgeIterator;
-
-  AnnotatedGraph() {}
-
-  AnnotatedGraph(const AnnotatedGraph &other) {
-    copyFrom(other);
-  }
-
-  AnnotatedGraph& operator=(const AnnotatedGraph &other) {
-    PGraph::clear();
-    copyFrom(other);
-    return *this;
-  }
-
-  NodeIterator addNode(const Vector &costs, const NodeData &data) {
-    return PGraph::addConstructedNode(NodeEntry(costs, data));
-  }
-
-  EdgeIterator addEdge(const NodeIterator &node1Itr,
-                       const NodeIterator &node2Itr,
-                       const Matrix &costs, const EdgeData &data) {
-    return PGraph::addConstructedEdge(EdgeEntry(node1Itr, node2Itr,
-                                                costs, data));
-  }
-
-  NodeData& getNodeData(const NodeIterator &nodeItr) {
-    return PGraph::getNodeEntry(nodeItr).getNodeData();
-  }
-
-  const NodeData& getNodeData(const NodeIterator &nodeItr) const {
-    return PGraph::getNodeEntry(nodeItr).getNodeData();
-  }
-
-  EdgeData& getEdgeData(const EdgeIterator &edgeItr) {
-    return PGraph::getEdgeEntry(edgeItr).getEdgeData();
-  }
-
-  const EdgeEntry& getEdgeData(const EdgeIterator &edgeItr) const {
-    return PGraph::getEdgeEntry(edgeItr).getEdgeData();
-  }
-
-  SimpleGraph toSimpleGraph() const {
-    SimpleGraph g;
-
-    if (!PGraph::areNodeIDsValid()) {
-      PGraph::assignNodeIDs();
-    }
-    std::vector<SimpleGraph::NodeIterator> newNodeItrs(PGraph::getNumNodes());
-
-    for (ConstNodeIterator nItr = PGraph::nodesBegin(), 
-         nEnd = PGraph::nodesEnd();
-         nItr != nEnd; ++nItr) {
-
-      newNodeItrs[getNodeID(nItr)] = g.addNode(getNodeCosts(nItr));
-    }
-
-    for (ConstEdgeIterator
-         eItr = PGraph::edgesBegin(), eEnd = PGraph::edgesEnd();
-         eItr != eEnd; ++eItr) {
-
-      unsigned node1ID = getNodeID(getEdgeNode1(eItr)),
-               node2ID = getNodeID(getEdgeNode2(eItr));
-
-        g.addEdge(newNodeItrs[node1ID], newNodeItrs[node2ID],
-                  getEdgeCosts(eItr));
-    }
-
-    return g;
-  }
-
-};
-
-
-}
-
-#endif // LLVM_CODEGEN_PBQP_ANNOTATEDGRAPH_H
diff --git a/lib/CodeGen/PBQP/ExhaustiveSolver.h b/lib/CodeGen/PBQP/ExhaustiveSolver.h
deleted file mode 100644
index 35ec4f1b0b..0000000000
--- a/lib/CodeGen/PBQP/ExhaustiveSolver.h
+++ /dev/null
@@ -1,110 +0,0 @@
-//===-- ExhaustiveSolver.h - Brute Force PBQP Solver ------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Uses a trivial brute force algorithm to solve a PBQP problem.
-// PBQP is NP-HARD - This solver should only be used for debugging small
-// problems.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CODEGEN_PBQP_EXHAUSTIVESOLVER_H
-#define LLVM_CODEGEN_PBQP_EXHAUSTIVESOLVER_H
-
-#include "Solver.h"
-
-namespace PBQP {
-
-/// A brute force PBQP solver. This solver takes exponential time. It should
-/// only be used for debugging purposes. 
-class ExhaustiveSolverImpl {
-private:
-
-  const SimpleGraph &g;
-
-  PBQPNum getSolutionCost(const Solution &solution) const {
-    PBQPNum cost = 0.0;
-    
-    for (SimpleGraph::ConstNodeIterator
-         nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
-         nodeItr != nodeEnd; ++nodeItr) {
-      
-      unsigned nodeId = g.getNodeID(nodeItr);
-
-      cost += g.getNodeCosts(nodeItr)[solution.getSelection(nodeId)];
-    }
-
-    for (SimpleGraph::ConstEdgeIterator
-         edgeItr = g.edgesBegin(), edgeEnd = g.edgesEnd();
-         edgeItr != edgeEnd; ++edgeItr) {
-      
-      SimpleGraph::ConstNodeIterator n1 = g.getEdgeNode1Itr(edgeItr),
-                                     n2 = g.getEdgeNode2Itr(edgeItr);
-      unsigned sol1 = solution.getSelection(g.getNodeID(n1)),
-               sol2 = solution.getSelection(g.getNodeID(n2));
-
-      cost += g.getEdgeCosts(edgeItr)[sol1][sol2];
-    }
-
-    return cost;
-  }
-
-public:
-
-  ExhaustiveSolverImpl(const SimpleGraph &g) : g(g) {}
-
-  Solution solve() const {
-    Solution current(g.getNumNodes(), true), optimal(current);
-
-    PBQPNum bestCost = std::numeric_limits<PBQPNum>::infinity();
-    bool finished = false;
-
-    while (!finished) {
-      PBQPNum currentCost = getSolutionCost(current);
-
-      if (currentCost < bestCost) {
-        optimal = current;
-        bestCost = currentCost;
-      }
-
-      // assume we're done.
-      finished = true;
-
-      for (unsigned i = 0; i < g.getNumNodes(); ++i) {
-        if (current.getSelection(i) ==
-            (g.getNodeCosts(g.getNodeItr(i)).getLength() - 1)) {
-          current.setSelection(i, 0);
-        }
-        else {
-          current.setSelection(i, current.getSelection(i) + 1);
-          finished = false;
-          break;
-        }
-      }
-
-    }
-
-    optimal.setSolutionCost(bestCost);
-
-    return optimal;
-  }
-
-};
-
-class ExhaustiveSolver : public Solver {
-public:
-  ~ExhaustiveSolver() {}
-  Solution solve(const SimpleGraph &g) const {
-    ExhaustiveSolverImpl solver(g);
-    return solver.solve();
-  }
-};
-
-}
-
-#endif // LLVM_CODGEN_PBQP_EXHAUSTIVESOLVER_HPP
diff --git a/lib/CodeGen/PBQP/Graph.h b/lib/CodeGen/PBQP/Graph.h
new file mode 100644
index 0000000000..40fc9197a9
--- /dev/null
+++ b/lib/CodeGen/PBQP/Graph.h
@@ -0,0 +1,357 @@
+//===-------------------- Graph.h - PBQP Graph ------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// PBQP Graph class.
+//
+//===----------------------------------------------------------------------===//
+
+
+#ifndef LLVM_CODEGEN_PBQP_GRAPH_H
+#define LLVM_CODEGEN_PBQP_GRAPH_H
+
+#include "Math.h"
+
+#include <list>
+#include <vector>
+
+namespace PBQP {
+
+  /// PBQP Graph class.
+  /// Instances of this class describe PBQP problems.
+  class Graph {
+  private:
+
+    // ----- TYPEDEFS -----
+    class NodeEntry;
+    class EdgeEntry;
+
+    typedef std::list<NodeEntry> NodeList;
+    typedef std::list<EdgeEntry> EdgeList;
+
+  public:
+
+    typedef NodeList::iterator NodeItr;
+    typedef EdgeList::iterator EdgeItr;
+
+  private:
+
+    typedef std::list<EdgeItr> AdjEdgeList;
+  
+  public:
+
+    typedef AdjEdgeList::iterator AdjEdgeItr;
+
+  private:
+
+    class NodeEntry {
+    private:
+      Vector costs;      
+      AdjEdgeList adjEdges;
+      unsigned degree;
+      void *data;
+    public:
+      NodeEntry(const Vector &costs) : costs(costs), degree(0) {}
+      Vector& getCosts() { return costs; }
+      unsigned getDegree() const { return degree; }
+      AdjEdgeItr edgesBegin() { return adjEdges.begin(); }
+      AdjEdgeItr edgesEnd() { return adjEdges.end(); }
+      AdjEdgeItr addEdge(EdgeItr e) {
+        ++degree;
+        return adjEdges.insert(adjEdges.end(), e);
+      }
+      void removeEdge(AdjEdgeItr ae) {
+        --degree;
+        adjEdges.erase(ae);
+      }
+      void setData(void *data) { this->data = data; }
+      void* getData() { return data; }
+    };
+
+    class EdgeEntry {
+    private:
+      NodeItr node1, node2;
+      Matrix costs;
+      AdjEdgeItr node1AEItr, node2AEItr;
+      void *data;
+    public:
+      EdgeEntry(NodeItr node1, NodeItr node2, const Matrix &costs)
+        : node1(node1), node2(node2), costs(costs) {}
+      NodeItr getNode1() const { return node1; }
+      NodeItr getNode2() const { return node2; }
+      Matrix& getCosts() { return costs; }
+      void setNode1AEItr(AdjEdgeItr ae) { node1AEItr = ae; }
+      AdjEdgeItr getNode1AEItr() { return node1AEItr; }
+      void setNode2AEItr(AdjEdgeItr ae) { node2AEItr = ae; }
+      AdjEdgeItr getNode2AEItr() { return node2AEItr; }
+      void setData(void *data) { this->data = data; }
+      void *getData() { return data; }
+    };
+
+    // ----- MEMBERS -----
+
+    NodeList nodes;
+    unsigned numNodes;
+
+    EdgeList edges;
+    unsigned numEdges;
+
+    // ----- INTERNAL METHODS -----
+
+    NodeEntry& getNode(NodeItr nItr) { return *nItr; }
+    const NodeEntry& getNode(NodeItr nItr) const { return *nItr; }
+    EdgeEntry& getEdge(EdgeItr eItr) { return *eItr; }
+    const EdgeEntry& getEdge(EdgeItr eItr) const { return *eItr; }
+
+    NodeItr addConstructedNode(const NodeEntry &n) {
+      ++numNodes;
+      return nodes.insert(nodes.end(), n);
+    }
+
+    EdgeItr addConstructedEdge(const EdgeEntry &e) {
+      assert(findEdge(e.getNode1(), e.getNode2()) == edges.end() &&
+             "Attempt to add duplicate edge.");
+      ++numEdges;
+      EdgeItr edgeItr = edges.insert(edges.end(), e);
+      EdgeEntry &ne = getEdge(edgeItr);
+      NodeEntry &n1 = getNode(ne.getNode1());
+      NodeEntry &n2 = getNode(ne.getNode2());
+      // Sanity check on matrix dimensions:
+      assert((n1.getCosts().getLength() == ne.getCosts().getRows()) &&
+             (n2.getCosts().getLength() == ne.getCosts().getCols()) &&
+             "Edge cost dimensions do not match node costs dimensions.");
+      ne.setNode1AEItr(n1.addEdge(edgeItr));
+      ne.setNode2AEItr(n2.addEdge(edgeItr));
+      return edgeItr;
+    }
+
+  public:
+
+    Graph() : numNodes(0), numEdges(0) {}
+
+    /// \brief Add a node with the given costs.
+    /// @param costs Cost vector for the new node.
+    /// @return Node iterator for the added node.
+    NodeItr addNode(const Vector &costs) {
+      return addConstructedNode(NodeEntry(costs));
+    }
+
+    /// \brief Add an edge between the given nodes with the given costs.
+    /// @param n1Itr First node.
+    /// @param n2Itr Second node.
+    /// @return Edge iterator for the added edge.
+    EdgeItr addEdge(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr,
+                    const Matrix &costs) {
+      assert(getNodeCosts(n1Itr).getLength() == costs.getRows() &&
+             getNodeCosts(n2Itr).getLength() == costs.getCols() &&
+             "Matrix dimensions mismatch.");
+      return addConstructedEdge(EdgeEntry(n1Itr, n2Itr, costs)); 
+    }
+
+    /// \brief Get the number of nodes in the graph.
+    /// @return Number of nodes in the graph.
+    unsigned getNumNodes() const { return numNodes; }
+
+    /// \brief Get the number of edges in the graph.
+    /// @return Number of edges in the graph.
+    unsigned getNumEdges() const { return numEdges; }
+
+    /// \brief Get a node's cost vector.
+    /// @param nItr Node iterator.
+    /// @return Node cost vector.
+    Vector& getNodeCosts(NodeItr nItr) { return getNode(nItr).getCosts(); }
+
+    /// \brief Set a node's data pointer.
+    /// @param nItr Node iterator.
+    /// @param data Pointer to node data.
+    ///
+    /// Typically used by a PBQP solver to attach data to aid in solution.
+    void setNodeData(NodeItr nItr, void *data) { getNode(nItr).setData(data); }
+
+    /// \brief Get the node's data pointer.
+    /// @param nItr Node iterator.
+    /// @return Pointer to node data.
+    void* getNodeData(NodeItr nItr) { return getNode(nItr).getData(); }
+    
+    /// \brief Get an edge's cost matrix.
+    /// @param eItr Edge iterator.
+    /// @return Edge cost matrix.
+    Matrix& getEdgeCosts(EdgeItr eItr) { return getEdge(eItr).getCosts(); }
+
+    /// \brief Set an edge's data pointer.
+    /// @param eItr Edge iterator.
+    /// @param data Pointer to edge data.
+    ///
+    /// Typically used by a PBQP solver to attach data to aid in solution.
+    void setEdgeData(EdgeItr eItr, void *data) { getEdge(eItr).setData(data); }
+
+    /// \brief Get an edge's data pointer.
+    /// @param eItr Edge iterator.
+    /// @return Pointer to edge data. 
+    void* getEdgeData(EdgeItr eItr) { return getEdge(eItr).getData(); }
+
+    /// \brief Get a node's degree.
+    /// @param nItr Node iterator.
+    /// @return The degree of the node.
+    unsigned getNodeDegree(NodeItr nItr) const {
+      return getNode(nItr).getDegree();
+    }
+
+    /// \brief Begin iterator for node set.
+    NodeItr nodesBegin() { return nodes.begin(); }
+
+    /// \brief End iterator for node set.
+    NodeItr nodesEnd() { return nodes.end(); }
+
+    /// \brief Begin iterator for edge set.
+    EdgeItr edgesBegin() { return edges.begin(); }
+
+    /// \brief End iterator for edge set.
+    EdgeItr edgesEnd() { return edges.end(); }
+
+    /// \brief Get begin iterator for adjacent edge set.
+    /// @param nItr Node iterator.
+    /// @return Begin iterator for the set of edges connected to the given node.
+    AdjEdgeItr adjEdgesBegin(NodeItr nItr) {
+      return getNode(nItr).edgesBegin();
+    }
+
+    /// \brief Get end iterator for adjacent edge set.
+    /// @param nItr Node iterator.
+    /// @return End iterator for the set of edges connected to the given node.
+    AdjEdgeItr adjEdgesEnd(NodeItr nItr) {
+      return getNode(nItr).edgesEnd();
+    }
+
+    /// \brief Get the first node connected to this edge.
+    /// @param eItr Edge iterator.
+    /// @return The first node connected to the given edge. 
+    NodeItr getEdgeNode1(EdgeItr eItr) {
+      return getEdge(eItr).getNode1();
+    }
+
+    /// \brief Get the second node connected to this edge.
+    /// @param eItr Edge iterator.
+    /// @return The second node connected to the given edge. 
+    NodeItr getEdgeNode2(EdgeItr eItr) {
+      return getEdge(eItr).getNode2();
+    } 
+
+    /// \brief Get the "other" node connected to this edge.
+    /// @param eItr Edge iterator.
+    /// @param nItr Node iterator for the "given" node.
+    /// @return The iterator for the "other" node connected to this edge. 
+    NodeItr getEdgeOtherNode(EdgeItr eItr, NodeItr nItr) {
+      EdgeEntry &e = getEdge(eItr);
+      if (e.getNode1() == nItr) {
+        return e.getNode2();
+      } // else
+      return e.getNode1();
+    }
+
+    /// \brief Get the edge connecting two nodes.
+    /// @param n1Itr First node iterator.
+    /// @param n2Itr Second node iterator.
+    /// @return An iterator for edge (n1Itr, n2Itr) if such an edge exists,
+    ///         otherwise returns edgesEnd(). 
+    EdgeItr findEdge(NodeItr n1Itr, NodeItr n2Itr) {
+      for (AdjEdgeItr aeItr = adjEdgesBegin(n1Itr), aeEnd = adjEdgesEnd(n1Itr);
+         aeItr != aeEnd; ++aeItr) {
+        if ((getEdgeNode1(*aeItr) == n2Itr) ||
+            (getEdgeNode2(*aeItr) == n2Itr)) {
+          return *aeItr;
+        }
+      }
+      return edges.end();
+    }
+
+    /// \brief Remove a node from the graph.
+    /// @param nItr Node iterator.
+    void removeNode(NodeItr nItr) {
+      NodeEntry &n = getNode(nItr);
+      for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end;) {
+        EdgeItr eItr = *itr;
+        ++itr;
+        removeEdge(eItr); 
+      }
+      nodes.erase(nItr);
+      --numNodes;
+    }
+
+    /// \brief Remove an edge from the graph.
+    /// @param eItr Edge iterator.
+    void removeEdge(EdgeItr eItr) {
+      EdgeEntry &e = getEdge(eItr);
+      NodeEntry &n1 = getNode(e.getNode1());
+      NodeEntry &n2 = getNode(e.getNode2());
+      n1.removeEdge(e.getNode1AEItr());
+      n2.removeEdge(e.getNode2AEItr());
+      edges.erase(eItr);
+      --numEdges;
+    }
+
+    /// \brief Remove all nodes and edges from the graph.
+    void clear() {
+      nodes.clear();
+      edges.clear();
+      numNodes = numEdges = 0;
+    }
+
+    /// \brief Print a representation of this graph in DOT format.
+    /// @param os Output stream to print on.
+    template <typename OStream>
+    void printDot(OStream &os) {
+    
+      os << "graph {\n";
+
+      for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd();
+           nodeItr != nodeEnd; ++nodeItr) {
+
+        os << "  node" << nodeItr << " [ label=\""
+           << nodeItr << ": " << getNodeCosts(nodeItr) << "\" ]\n";
+      }
+
+      os << "  edge [ len=" << getNumNodes() << " ]\n";
+
+      for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
+           edgeItr != edgeEnd; ++edgeItr) {
+
+        os << "  node" << getEdgeNode1(edgeItr)
+           << " -- node" << getEdgeNode2(edgeItr)
+           << " [ label=\"";
+
+        const Matrix &edgeCosts = getEdgeCosts(edgeItr);
+
+        for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
+          os << edgeCosts.getRowAsVector(i) << "\\n";
+        }
+        os << "\" ]\n";
+      }
+      os << "}\n";
+    }
+
+  };
+
+  class NodeItrComparator {
+  public:
+    bool operator()(Graph::NodeItr n1, Graph::NodeItr n2) const {
+      return &*n1 < &*n2;
+    }
+  };
+
+  class EdgeItrCompartor {
+  public:
+    bool operator()(Graph::EdgeItr e1, Graph::EdgeItr e2) const {
+      return &*e1 < &*e2;
+    }
+  };
+
+
+}
+
+#endif // LLVM_CODEGEN_PBQP_GRAPH_HPP
diff --git a/lib/CodeGen/PBQP/GraphBase.h b/lib/CodeGen/PBQP/GraphBase.h
deleted file mode 100644
index becd98afdb..0000000000
--- a/lib/CodeGen/PBQP/GraphBase.h
+++ /dev/null
@@ -1,582 +0,0 @@
-//===-- GraphBase.h - Abstract Base PBQP Graph ------------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Base class for PBQP Graphs.
-//
-//===----------------------------------------------------------------------===//
-
-
-#ifndef LLVM_CODEGEN_PBQP_GRAPHBASE_H
-#define LLVM_CODEGEN_PBQP_GRAPHBASE_H
-
-#include "PBQPMath.h"
-
-#include <list>
-#include <vector>
-
-namespace PBQP {
-
-// UGLY, but I'm not sure there's a good way around this: We need to be able to
-// look up a Node's "adjacent edge list" structure type before the Node type is
-// fully constructed.  We can enable this by pushing the choice of data type
-// out into this traits class.
-template <typename Graph>
-class NodeBaseTraits {
-  public:
-    typedef std::list<typename Graph::EdgeIterator> AdjEdgeList;
-    typedef typename AdjEdgeList::iterator AdjEdgeIterator;
-    typedef typename AdjEdgeList::const_iterator ConstAdjEdgeIterator;
-};
-
-/// \brief Base for concrete graph classes. Provides a basic set of graph
-///        operations which are useful for PBQP solvers.
-template <typename NodeEntry, typename EdgeEntry>
-class GraphBase {
-private:
-
-  typedef GraphBase<NodeEntry, EdgeEntry> ThisGraphT;
-
-  typedef std::list<NodeEntry> NodeList;
-  typedef std::list<EdgeEntry> EdgeList;
-
-  NodeList nodeList;
-  unsigned nodeListSize;
-
-  EdgeList edgeList;
-  unsigned edgeListSize;
-
-  GraphBase(const ThisGraphT &other) { abort(); }
-  void operator=(const ThisGraphT &other) { abort(); } 
-  
-public:
-
-  /// \brief Iterates over the nodes of a graph.
-  typedef typename NodeList::iterator NodeIterator;
-  /// \brief Iterates over the nodes of a const graph.
-  typedef typename NodeList::const_iterator ConstNodeIterator;
-  /// \brief Iterates over the edges of a graph.
-  typedef typename EdgeList::iterator EdgeIterator;
-  /// \brief Iterates over the edges of a const graph.
-  typedef typename EdgeList::const_iterator ConstEdgeIterator;
-
-  /// \brief Iterates over the edges attached to a node.
-  typedef typename NodeBaseTraits<ThisGraphT>::AdjEdgeIterator
-    AdjEdgeIterator;
-
-  /// \brief Iterates over the edges attached to a node in a const graph.
-  typedef typename NodeBaseTraits<ThisGraphT>::ConstAdjEdgeIterator
-    ConstAdjEdgeIterator;
-
-private:
-
-  typedef std::vector<NodeIterator> IDToNodeMap;
-
-  IDToNodeMap idToNodeMap;
-  bool nodeIDsValid;
-
-  void invalidateNodeIDs() {
-    if (nodeIDsValid) {
-      idToNodeMap.clear();
-      nodeIDsValid = false;
-    }
-  }
-
-  template <typename ItrT>
-  bool iteratorInRange(ItrT itr, const ItrT &begin, const ItrT &end) {
-    for (ItrT t = begin; t != end; ++t) {
-      if (itr == t)
-        return true;
-    }
-
-    return false;
-  }
-
-protected:
-
-  GraphBase() : nodeListSize(0), edgeListSize(0), nodeIDsValid(false) {}
-  
-  NodeEntry& getNodeEntry(const NodeIterator &nodeItr) { return *nodeItr; }
-  const NodeEntry& getNodeEntry(const ConstNodeIterator &nodeItr) const {
-    return *nodeItr;
-  }
-
-  EdgeEntry& getEdgeEntry(const EdgeIterator &edgeItr) { return *edgeItr; }
-  const EdgeEntry& getEdgeEntry(const ConstEdgeIterator &edgeItr) const {
-    return *edgeItr;
-  }
-
-  NodeIterator addConstructedNode(const NodeEntry &nodeEntry) {
-    ++nodeListSize;
-
-    invalidateNodeIDs();
-
-    NodeIterator newNodeItr = nodeList.insert(nodeList.end(), nodeEntry);
-
-    return newNodeItr;
-  }
-
-  EdgeIterator addConstructedEdge(const EdgeEntry &edgeEntry) {
-
-    assert((findEdge(edgeEntry.getNode1Itr(), edgeEntry.getNode2Itr())
-          == edgeList.end()) && "Attempt to add duplicate edge.");
-
-    ++edgeListSize;
-
-    // Add the edge to the graph.
-    EdgeIterator edgeItr = edgeList.insert(edgeList.end(), edgeEntry);
-
-    // Get a reference to the version in the graph.
-    EdgeEntry &newEdgeEntry = getEdgeEntry(edgeItr);
-
-    // Node entries:
-    NodeEntry &node1Entry = getNodeEntry(newEdgeEntry.getNode1Itr()),
-              &node2Entry = getNodeEntry(newEdgeEntry.getNode2Itr());
-
-    // Sanity check on matrix dimensions.
-    assert((node1Entry.getCosts().getLength() == 
-            newEdgeEntry.getCosts().getRows()) && 
-           (node2Entry.getCosts().getLength() == 
-            newEdgeEntry.getCosts().getCols()) &&
-        "Matrix dimensions do not match cost vector dimensions.");
-
-    // Create links between nodes and edges.
-    newEdgeEntry.setNode1ThisEdgeItr(
-        node1Entry.addAdjEdge(edgeItr));
-    newEdgeEntry.setNode2ThisEdgeItr(
-        node2Entry.addAdjEdge(edgeItr));
-
-    return edgeItr;
-  }
-
-public:
-
-  /// \brief Returns the number of nodes in this graph.
-  unsigned getNumNodes() const { return nodeListSize; }
-
-  /// \brief Returns the number of edges in this graph.
-  unsigned getNumEdges() const { return edgeListSize; } 
-
-  /// \brief Return the cost vector for the given node.
-  Vector& getNodeCosts(const NodeIterator &nodeItr) {
-    return getNodeEntry(nodeItr).getCosts();
-  }
-
-  /// \brief Return the cost vector for the give node. 
-  const Vector& getNodeCosts(const ConstNodeIterator &nodeItr) const {
-    return getNodeEntry(nodeItr).getCosts();
-  }
-
-  /// \brief Return the degree of the given node.
-  unsigned getNodeDegree(const NodeIterator &nodeItr) const {
-    return getNodeEntry(nodeItr).getDegree();
-  }
-
-  /// \brief Assigns sequential IDs to the nodes, starting at 0, which
-  /// remain valid until the next addition or removal of a node.
-  void assignNodeIDs() {
-    unsigned curID = 0;
-    idToNodeMap.resize(getNumNodes());
-    for (NodeIterator nodeItr = nodesBegin(), nodeEnd = nodesEnd();
-         nodeItr != nodeEnd; ++nodeItr, ++curID) {
-      getNodeEntry(nodeItr).setID(curID);
-      idToNodeMap[curID] = nodeItr;
-    }
-    nodeIDsValid = true;
-  }
-
-  /// \brief Assigns sequential IDs to the nodes using the ordering of the
-  /// given vector.
-  void assignNodeIDs(const std::vector<NodeIterator> &nodeOrdering) {
-    assert((getNumNodes() == nodeOrdering.size()) && 
-           "Wrong number of nodes in node ordering.");
-    idToNodeMap = nodeOrdering;
-    for (unsigned nodeID = 0; nodeID < idToNodeMap.size(); ++nodeID) {
-      getNodeEntry(idToNodeMap[nodeID]).setID(nodeID);
-    }
-    nodeIDsValid = true;
-  }
-
-  /// \brief Returns true if valid node IDs are assigned, false otherwise.
-  bool areNodeIDsValid() const { return nodeIDsValid; }
-
-  /// \brief Return the numeric ID of the given node.
-  ///
-  /// Calls to this method will result in an assertion failure if there have
-  /// been any node additions or removals since the last call to
-  /// assignNodeIDs().
-  unsigned getNodeID(const ConstNodeIterator &nodeItr) const {
-    assert(nodeIDsValid && "Attempt to retrieve invalid ID.");
-    return getNodeEntry(nodeItr).getID();
-  }
-
-  /// \brief Returns the iterator associated with the given node ID.
-  NodeIterator getNodeItr(unsigned nodeID) {
-    assert(nodeIDsValid && "Attempt to retrieve iterator with invalid ID.");
-    return idToNodeMap[nodeID];
-  }
-
-  /// \brief Returns the iterator associated with the given node ID.
-  ConstNodeIterator getNodeItr(unsigned nodeID) const {
-    assert(nodeIDsValid && "Attempt to retrieve iterator with invalid ID.");
-    return idToNodeMap[nodeID];
-  }
-
-  /// \brief Removes the given node (and all attached edges) from the graph.
-  void removeNode(const NodeIterator &nodeItr) {
-    assert(iteratorInRange(nodeItr, nodeList.begin(), nodeList.end()) &&
-           "Iterator does not belong to this graph!");
-
-    invalidateNodeIDs();
-    
-    NodeEntry &nodeEntry = getNodeEntry(nodeItr);
-
-    // We need to copy this out because it will be destroyed as the edges are
-    // removed.
-    typedef std::vector<EdgeIterator> AdjEdgeList;
-    typedef typename AdjEdgeList::iterator AdjEdgeListItr;
-
-    AdjEdgeList adjEdges;
-    adjEdges.reserve(nodeEntry.getDegree());
-    std::copy(nodeEntry.adjEdgesBegin(), nodeEntry.adjEdgesEnd(),
-              std::back_inserter(adjEdges));
-
-    // Iterate over the copied out edges and remove them from the graph.
-    for (AdjEdgeListItr itr = adjEdges.begin(), end = adjEdges.end();
-         itr != end; ++itr) {
-      removeEdge(*itr);
-    }
-
-    // Erase the node from the nodelist.
-    nodeList.erase(nodeItr);
-    --nodeListSize;
-  }
-
-  NodeIterator nodesBegin() { return nodeList.begin(); }
-  ConstNodeIterator nodesBegin() const { return nodeList.begin(); }
-  NodeIterator nodesEnd() { return nodeList.end(); }
-  ConstNodeIterator nodesEnd() const { return nodeList.end(); }
-
-  AdjEdgeIterator adjEdgesBegin(const NodeIterator &nodeItr) {
-    return getNodeEntry(nodeItr).adjEdgesBegin();
-  }
-
-  ConstAdjEdgeIterator adjEdgesBegin(const ConstNodeIterator &nodeItr) const {
-    return getNodeEntry(nodeItr).adjEdgesBegin();
-  }
-
-  AdjEdgeIterator adjEdgesEnd(const NodeIterator &nodeItr) {
-    return getNodeEntry(nodeItr).adjEdgesEnd();
-  }
-  
-  ConstAdjEdgeIterator adjEdgesEnd(const ConstNodeIterator &nodeItr) const {
-    getNodeEntry(nodeItr).adjEdgesEnd();
-  }
-
-  EdgeIterator findEdge(const NodeIterator &node1Itr,
-                        const NodeIterator &node2Itr) {
-
-    for (AdjEdgeIterator adjEdgeItr = adjEdgesBegin(node1Itr),
-         adjEdgeEnd = adjEdgesEnd(node1Itr);
-         adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) {
-      if ((getEdgeNode1Itr(*adjEdgeItr) == node2Itr) ||
-          (getEdgeNode2Itr(*adjEdgeItr) == node2Itr)) {
-        return *adjEdgeItr;
-      }
-    }
-
-    return edgeList.end();
-  }
-
-  ConstEdgeIterator findEdge(const ConstNodeIterator &node1Itr,
-                             const ConstNodeIterator &node2Itr) const {
-
-    for (ConstA