diff --git a/include/llvm/CodeGen/PBQP/Graph.h b/include/llvm/CodeGen/PBQP/Graph.h
index b57abca..9f9a567 100644
--- a/include/llvm/CodeGen/PBQP/Graph.h
+++ b/include/llvm/CodeGen/PBQP/Graph.h
@@ -20,79 +20,63 @@
 #include "llvm/ADT/ilist_node.h"
 #include <list>
 #include <map>
+#include <set>
 
 namespace PBQP {
 
   /// PBQP Graph class.
   /// Instances of this class describe PBQP problems.
   class Graph {
-  private:
-
-    // ----- TYPEDEFS -----
-    class NodeEntry;
-    class EdgeEntry;
-
-    typedef llvm::ilist<NodeEntry> NodeList;
-    typedef llvm::ilist<EdgeEntry> EdgeList;
-
   public:
 
-    typedef NodeList::iterator NodeItr;
-    typedef NodeList::const_iterator ConstNodeItr;
-
-    typedef EdgeList::iterator EdgeItr;
-    typedef EdgeList::const_iterator ConstEdgeItr;
+    typedef unsigned NodeId;
+    typedef unsigned EdgeId;
 
   private:
 
-    typedef std::list<EdgeItr> AdjEdgeList;
-  
+    typedef std::set<NodeId> AdjEdgeList;
+
   public:
 
     typedef AdjEdgeList::iterator AdjEdgeItr;
 
   private:
 
-    class NodeEntry : public llvm::ilist_node<NodeEntry> {
-      friend struct llvm::ilist_sentinel_traits<NodeEntry>;
+    class NodeEntry {
     private:
       Vector costs;      
       AdjEdgeList adjEdges;
-      unsigned degree;
       void *data;
       NodeEntry() : costs(0, 0) {}
     public:
-      NodeEntry(const Vector &costs) : costs(costs), degree(0) {}
+      NodeEntry(const Vector &costs) : costs(costs), data(0) {}
       Vector& getCosts() { return costs; }
       const Vector& getCosts() const { return costs; }
-      unsigned getDegree() const { return degree; }
+      unsigned getDegree() const { return adjEdges.size(); }
       AdjEdgeItr edgesBegin() { return adjEdges.begin(); }
       AdjEdgeItr edgesEnd() { return adjEdges.end(); }
-      AdjEdgeItr addEdge(EdgeItr e) {
-        ++degree;
+      AdjEdgeItr addEdge(EdgeId e) {
         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 : public llvm::ilist_node<EdgeEntry> {
-      friend struct llvm::ilist_sentinel_traits<EdgeEntry>;
+    class EdgeEntry {
     private:
-      NodeItr node1, node2;
+      NodeId node1, node2;
       Matrix costs;
       AdjEdgeItr node1AEItr, node2AEItr;
       void *data;
-      EdgeEntry() : costs(0, 0, 0) {}
+      EdgeEntry() : costs(0, 0, 0), data(0) {}
     public:
-      EdgeEntry(NodeItr node1, NodeItr node2, const Matrix &costs)
+      EdgeEntry(NodeId node1, NodeId node2, const Matrix &costs)
         : node1(node1), node2(node2), costs(costs) {}
-      NodeItr getNode1() const { return node1; }
-      NodeItr getNode2() const { return node2; }
+      NodeId getNode1() const { return node1; }
+      NodeId getNode2() const { return node2; }
       Matrix& getCosts() { return costs; }
       const Matrix& getCosts() const { return costs; }
       void setNode1AEItr(AdjEdgeItr ae) { node1AEItr = ae; }
@@ -105,52 +89,126 @@
 
     // ----- MEMBERS -----
 
-    NodeList nodes;
-    unsigned numNodes;
+    typedef std::vector<NodeEntry> NodeVector;
+    typedef std::vector<NodeVector::size_type> FreeNodeVector;
+    NodeVector nodes;
+    FreeNodeVector freeNodes;
 
-    EdgeList edges;
-    unsigned numEdges;
+    typedef std::vector<EdgeEntry> EdgeVector;
+    typedef std::vector<EdgeVector::size_type> FreeEdgeVector;
+    EdgeVector edges;
+    FreeEdgeVector freeEdges;
 
     // ----- INTERNAL METHODS -----
 
-    NodeEntry& getNode(NodeItr nItr) { return *nItr; }
-    const NodeEntry& getNode(ConstNodeItr nItr) const { return *nItr; }
+    NodeEntry& getNode(NodeId nId) { return nodes[nId]; }
+    const NodeEntry& getNode(NodeId nId) const { return nodes[nId]; }
 
-    EdgeEntry& getEdge(EdgeItr eItr) { return *eItr; }
-    const EdgeEntry& getEdge(ConstEdgeItr eItr) const { return *eItr; }
+    EdgeEntry& getEdge(EdgeId eId) { return edges[eId]; }
+    const EdgeEntry& getEdge(EdgeId eId) const { return edges[eId]; }
 
-    NodeItr addConstructedNode(const NodeEntry &n) {
-      ++numNodes;
-      return nodes.insert(nodes.end(), n);
+    NodeId addConstructedNode(const NodeEntry &n) {
+      NodeId nodeId = 0;
+      if (!freeNodes.empty()) {
+        nodeId = freeNodes.back();
+        freeNodes.pop_back();
+        nodes[nodeId] = n;
+      } else {
+        nodeId = nodes.size();
+        nodes.push_back(n);
+      }
+      return nodeId;
     }
 
-    EdgeItr addConstructedEdge(const EdgeEntry &e) {
-      assert(findEdge(e.getNode1(), e.getNode2()) == edges.end() &&
+    EdgeId addConstructedEdge(const EdgeEntry &e) {
+      assert(findEdge(e.getNode1(), e.getNode2()) == invalidEdgeId() &&
              "Attempt to add duplicate edge.");
-      ++numEdges;
-      EdgeItr edgeItr = edges.insert(edges.end(), e);
-      EdgeEntry &ne = getEdge(edgeItr);
+      EdgeId edgeId = 0;
+      if (!freeEdges.empty()) {
+        edgeId = freeEdges.back();
+        freeEdges.pop_back();
+        edges[edgeId] = e;
+      } else {
+        edgeId = edges.size();
+        edges.push_back(e);
+      }
+
+      EdgeEntry &ne = getEdge(edgeId);
       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;
+
+      ne.setNode1AEItr(n1.addEdge(edgeId));
+      ne.setNode2AEItr(n2.addEdge(edgeId));
+      return edgeId;
     }
 
     inline void copyFrom(const Graph &other);
   public:
 
+    class NodeItr {
+    public:
+      NodeItr(NodeId nodeId, const Graph &g)
+        : nodeId(nodeId), endNodeId(g.nodes.size()), freeNodes(g.freeNodes) {
+        this->nodeId = findNextInUse(nodeId); // Move to the first in-use nodeId
+      }
+
+      bool operator==(const NodeItr& n) const { return nodeId == n.nodeId; }
+      bool operator!=(const NodeItr& n) const { return !(*this == n); }
+      NodeItr& operator++() { nodeId = findNextInUse(++nodeId); return *this; }
+      NodeId operator*() const { return nodeId; }
+
+    private:
+      NodeId findNextInUse(NodeId n) const {
+        while (n < endNodeId &&
+               std::find(freeNodes.begin(), freeNodes.end(), n) !=
+                 freeNodes.end()) {
+          ++n;
+        }
+        return n;
+      }
+
+      NodeId nodeId, endNodeId;
+      const FreeNodeVector& freeNodes;
+    };
+
+    class EdgeItr {
+    public:
+      EdgeItr(EdgeId edgeId, const Graph &g)
+        : edgeId(edgeId), endEdgeId(g.edges.size()), freeEdges(g.freeEdges) {
+        this->edgeId = findNextInUse(edgeId); // Move to the first in-use edgeId
+      }
+
+      bool operator==(const EdgeItr& n) const { return edgeId == n.edgeId; }
+      bool operator!=(const EdgeItr& n) const { return !(*this == n); }
+      EdgeItr& operator++() { edgeId = findNextInUse(++edgeId); return *this; }
+      EdgeId operator*() const { return edgeId; }
+
+    private:
+      EdgeId findNextInUse(EdgeId n) const {
+        while (n < endEdgeId &&
+               std::find(freeEdges.begin(), freeEdges.end(), n) !=
+                 freeEdges.end()) {
+          ++n;
+        }
+        return n;
+      }
+
+      EdgeId edgeId, endEdgeId;
+      const FreeEdgeVector& freeEdges;
+    };
+
     /// \brief Construct an empty PBQP graph.
-    Graph() : numNodes(0), numEdges(0) {}
+    Graph() {}
 
     /// \brief Copy construct this graph from "other". Note: Does not copy node
     ///        and edge data, only graph structure and costs.
     /// @param other Source graph to copy from.
-    Graph(const Graph &other) : numNodes(0), numEdges(0) {
+    Graph(const Graph &other) {
       copyFrom(other);
     }
 
@@ -170,7 +228,7 @@
     /// \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) {
+    NodeId addNode(const Vector &costs) {
       return addConstructedNode(NodeEntry(costs));
     }
 
@@ -178,32 +236,31 @@
     /// @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() &&
+    EdgeId addEdge(NodeId n1Id, NodeId n2Id, const Matrix &costs) {
+      assert(getNodeCosts(n1Id).getLength() == costs.getRows() &&
+             getNodeCosts(n2Id).getLength() == costs.getCols() &&
              "Matrix dimensions mismatch.");
-      return addConstructedEdge(EdgeEntry(n1Itr, n2Itr, costs)); 
+      return addConstructedEdge(EdgeEntry(n1Id, n2Id, costs)); 
     }
 
     /// \brief Get the number of nodes in the graph.
     /// @return Number of nodes in the graph.
-    unsigned getNumNodes() const { return numNodes; }
+    unsigned getNumNodes() const { return nodes.size() - freeNodes.size(); }
 
     /// \brief Get the number of edges in the graph.
     /// @return Number of edges in the graph.
-    unsigned getNumEdges() const { return numEdges; }
+    unsigned getNumEdges() const { return edges.size() - freeEdges.size(); }
 
     /// \brief Get a node's cost vector.
     /// @param nItr Node iterator.
     /// @return Node cost vector.
-    Vector& getNodeCosts(NodeItr nItr) { return getNode(nItr).getCosts(); }
+    Vector& getNodeCosts(NodeId nId) { return getNode(nId).getCosts(); }
 
     /// \brief Get a node's cost vector (const version).
     /// @param nItr Node iterator.
     /// @return Node cost vector.
-    const Vector& getNodeCosts(ConstNodeItr nItr) const {
-      return getNode(nItr).getCosts();
+    const Vector& getNodeCosts(NodeId nId) const {
+      return getNode(nId).getCosts();
     }
 
     /// \brief Set a node's data pointer.
@@ -211,23 +268,23 @@
     /// @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); }
+    void setNodeData(NodeId nId, void *data) { getNode(nId).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(); }
+    void* getNodeData(NodeId nId) { return getNode(nId).getData(); }
     
     /// \brief Get an edge's cost matrix.
     /// @param eItr Edge iterator.
     /// @return Edge cost matrix.
-    Matrix& getEdgeCosts(EdgeItr eItr) { return getEdge(eItr).getCosts(); }
+    Matrix& getEdgeCosts(EdgeId eId) { return getEdge(eId).getCosts(); }
 
     /// \brief Get an edge's cost matrix (const version).
     /// @param eItr Edge iterator.
     /// @return Edge cost matrix.
-    const Matrix& getEdgeCosts(ConstEdgeItr eItr) const {
-      return getEdge(eItr).getCosts();
+    const Matrix& getEdgeCosts(EdgeId eId) const {
+      return getEdge(eId).getCosts();
     }
 
     /// \brief Set an edge's data pointer.
@@ -235,124 +292,120 @@
     /// @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); }
+    void setEdgeData(EdgeId eId, void *data) { getEdge(eId).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(); }
+    void* getEdgeData(EdgeId eId) { return getEdge(eId).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();
+    unsigned getNodeDegree(NodeId nId) const {
+      return getNode(nId).getDegree();
     }
 
     /// \brief Begin iterator for node set.
-    NodeItr nodesBegin() { return nodes.begin(); }
-
-    /// \brief Begin const iterator for node set.
-    ConstNodeItr nodesBegin() const { return nodes.begin(); }
+    NodeItr nodesBegin() const { return NodeItr(0, *this);  }
 
     /// \brief End iterator for node set.
-    NodeItr nodesEnd() { return nodes.end(); }
-
-    /// \brief End const iterator for node set.
-    ConstNodeItr nodesEnd() const { return nodes.end(); }
+    NodeItr nodesEnd() const { return NodeItr(nodes.size(), *this); }
 
     /// \brief Begin iterator for edge set.
-    EdgeItr edgesBegin() { return edges.begin(); }
+    EdgeItr edgesBegin() const { return EdgeItr(0, *this); }
 
     /// \brief End iterator for edge set.
-    EdgeItr edgesEnd() { return edges.end(); }
+    EdgeItr edgesEnd() const { return EdgeItr(edges.size(), *this); }
 
     /// \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();
+    AdjEdgeItr adjEdgesBegin(NodeId nId) {
+      return getNode(nId).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();
+    AdjEdgeItr adjEdgesEnd(NodeId nId) {
+      return getNode(nId).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();
+    NodeId getEdgeNode1(EdgeId eId) {
+      return getEdge(eId).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();
+    NodeId getEdgeNode2(EdgeId eId) {
+      return getEdge(eId).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) {
+    NodeId getEdgeOtherNode(EdgeId eId, NodeId nId) {
+      EdgeEntry &e = getEdge(eId);
+      if (e.getNode1() == nId) {
         return e.getNode2();
       } // else
       return e.getNode1();
     }
 
+    EdgeId invalidEdgeId() const {
+      return std::numeric_limits<EdgeVector::size_type>::max();
+    }
+
     /// \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);
+    /// @param n1Id First node id.
+    /// @param n2Id Second node id.
+    /// @return An id for edge (n1Id, n2Id) if such an edge exists,
+    ///         otherwise returns an invalid edge id.
+    EdgeId findEdge(NodeId n1Id, NodeId n2Id) {
+      for (AdjEdgeItr aeItr = adjEdgesBegin(n1Id), aeEnd = adjEdgesEnd(n1Id);
          aeItr != aeEnd; ++aeItr) {
-        if ((getEdgeNode1(*aeItr) == n2Itr) ||
-            (getEdgeNode2(*aeItr) == n2Itr)) {
+        if ((getEdgeNode1(*aeItr) == n2Id) ||
+            (getEdgeNode2(*aeItr) == n2Id)) {
           return *aeItr;
         }
       }
-      return edges.end();
+      return invalidEdgeId();
     }
 
     /// \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); 
+    /// @param nItr Node id.
+    void removeNode(NodeId nId) {
+      NodeEntry &n = getNode(nId);
+      for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end; ++itr) {
+        EdgeId eId = *itr;
+        removeEdge(eId); 
       }
-      nodes.erase(nItr);
-      --numNodes;
+      freeNodes.push_back(nId);
     }
 
     /// \brief Remove an edge from the graph.
     /// @param eItr Edge iterator.
-    void removeEdge(EdgeItr eItr) {
-      EdgeEntry &e = getEdge(eItr);
+    void removeEdge(EdgeId eId) {
+      EdgeEntry &e = getEdge(eId);
       NodeEntry &n1 = getNode(e.getNode1());
       NodeEntry &n2 = getNode(e.getNode2());
       n1.removeEdge(e.getNode1AEItr());
       n2.removeEdge(e.getNode2AEItr());
-      edges.erase(eItr);
-      --numEdges;
+      freeEdges.push_back(eId);
     }
 
     /// \brief Remove all nodes and edges from the graph.
     void clear() {
       nodes.clear();
+      freeNodes.clear();
       edges.clear();
-      numNodes = numEdges = 0;
+      freeEdges.clear();
     }
 
     /// \brief Dump a graph to an output stream.
@@ -362,7 +415,7 @@
 
       for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd();
            nodeItr != nodeEnd; ++nodeItr) {
-        const Vector& v = getNodeCosts(nodeItr);
+        const Vector& v = getNodeCosts(*nodeItr);
         os << "\n" << v.getLength() << "\n";
         assert(v.getLength() != 0 && "Empty vector in graph.");
         os << v[0];
@@ -374,10 +427,10 @@
 
       for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
            edgeItr != edgeEnd; ++edgeItr) {
-        unsigned n1 = std::distance(nodesBegin(), getEdgeNode1(edgeItr));
-        unsigned n2 = std::distance(nodesBegin(), getEdgeNode2(edgeItr));
+        NodeId n1 = getEdgeNode1(*edgeItr);
+        NodeId n2 = getEdgeNode2(*edgeItr);
         assert(n1 != n2 && "PBQP graphs shound not have self-edges.");
-        const Matrix& m = getEdgeCosts(edgeItr);
+        const Matrix& m = getEdgeCosts(*edgeItr);
         os << "\n" << n1 << " " << n2 << "\n"
            << m.getRows() << " " << m.getCols() << "\n";
         assert(m.getRows() != 0 && "No rows in matrix.");
@@ -403,7 +456,7 @@
            nodeItr != nodeEnd; ++nodeItr) {
 
         os << "  node" << nodeItr << " [ label=\""
-           << nodeItr << ": " << getNodeCosts(nodeItr) << "\" ]\n";
+           << nodeItr << ": " << getNodeCosts(*nodeItr) << "\" ]\n";
       }
 
       os << "  edge [ len=" << getNumNodes() << " ]\n";
@@ -411,11 +464,11 @@
       for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
            edgeItr != edgeEnd; ++edgeItr) {
 
-        os << "  node" << getEdgeNode1(edgeItr)
-           << " -- node" << getEdgeNode2(edgeItr)
+        os << "  node" << getEdgeNode1(*edgeItr)
+           << " -- node" << getEdgeNode2(*edgeItr)
            << " [ label=\"";
 
-        const Matrix &edgeCosts = getEdgeCosts(edgeItr);
+        const Matrix &edgeCosts = getEdgeCosts(*edgeItr);
 
         for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
           os << edgeCosts.getRowAsVector(i) << "\\n";
@@ -427,39 +480,16 @@
 
   };
 
-  class NodeItrComparator {
-  public:
-    bool operator()(Graph::NodeItr n1, Graph::NodeItr n2) const {
-      return &*n1 < &*n2;
-    }
+//  void Graph::copyFrom(const Graph &other) {
+//     std::map<Graph::ConstNodeItr, Graph::NodeItr,
+//              NodeItrComparator> nodeMap;
 
-    bool operator()(Graph::ConstNodeItr n1, Graph::ConstNodeItr n2) const {
-      return &*n1 < &*n2;
-    }
-  };
-
-  class EdgeItrCompartor {
-  public:
-    bool operator()(Graph::EdgeItr e1, Graph::EdgeItr e2) const {
-      return &*e1 < &*e2;
-    }
-
-    bool operator()(Graph::ConstEdgeItr e1, Graph::ConstEdgeItr e2) const {
-      return &*e1 < &*e2;
-    }
-  };
-
-  void Graph::copyFrom(const Graph &other) {
-    std::map<Graph::ConstNodeItr, Graph::NodeItr,
-             NodeItrComparator> nodeMap;
-
-     for (Graph::ConstNodeItr nItr = other.nodesBegin(),
-                             nEnd = other.nodesEnd();
-         nItr != nEnd; ++nItr) {
-      nodeMap[nItr] = addNode(other.getNodeCosts(nItr));
-    }
-      
-  }
+//      for (Graph::ConstNodeItr nItr = other.nodesBegin(),
+//                              nEnd = other.nodesEnd();
+//          nItr != nEnd; ++nItr) {
+//       nodeMap[nItr] = addNode(other.getNodeCosts(nItr));
+//     }      
+//  }
 
 }
 
diff --git a/include/llvm/CodeGen/PBQP/HeuristicBase.h b/include/llvm/CodeGen/PBQP/HeuristicBase.h
index 0c1fcb7..36d94d6 100644
--- a/include/llvm/CodeGen/PBQP/HeuristicBase.h
+++ b/include/llvm/CodeGen/PBQP/HeuristicBase.h
@@ -52,7 +52,7 @@
   class HeuristicBase {
   private:
 
-    typedef std::list<Graph::NodeItr> OptimalList;
+    typedef std::list<Graph::NodeId> OptimalList;
 
     HeuristicSolverImpl<HImpl> &s;
     Graph &g;
@@ -63,8 +63,8 @@
 
     // Add the given node to the optimal reductions list. Keep an iterator to
     // its location for fast removal. 
-    void addToOptimalReductionList(Graph::NodeItr nItr) {
-      optimalList.insert(optimalList.end(), nItr);
+    void addToOptimalReductionList(Graph::NodeId nId) {
+      optimalList.insert(optimalList.end(), nId);
     }
 
   public:
@@ -105,8 +105,8 @@
     /// criteria. Note however that your criteria for selecting optimal nodes
     /// should be <i>at least</i> as strong as this. I.e. Nodes of degree 3 or
     /// higher should not be selected under any circumstances.
-    bool shouldOptimallyReduce(Graph::NodeItr nItr) {
-      if (g.getNodeDegree(nItr) < 3)
+    bool shouldOptimallyReduce(Graph::NodeId nId) {
+      if (g.getNodeDegree(nId) < 3)
         return true;
       // else
       return false;
@@ -118,8 +118,8 @@
     /// You probably don't want to over-ride this, except perhaps to record
     /// statistics before calling this implementation. HeuristicBase relies on
     /// its behaviour.
-    void addToOptimalReduceList(Graph::NodeItr nItr) {
-      optimalList.push_back(nItr);
+    void addToOptimalReduceList(Graph::NodeId nId) {
+      optimalList.push_back(nId);
     }
 
     /// \brief Initialise the heuristic.
@@ -132,10 +132,10 @@
     void setup() {
       for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
            nItr != nEnd; ++nItr) {
-        if (impl().shouldOptimallyReduce(nItr)) {
-          addToOptimalReduceList(nItr);
+        if (impl().shouldOptimallyReduce(*nItr)) {
+          addToOptimalReduceList(*nItr);
         } else {
-          impl().addToHeuristicReduceList(nItr);
+          impl().addToHeuristicReduceList(*nItr);
         }
       }
     }
@@ -150,13 +150,13 @@
       if (optimalList.empty())
         return false;
 
-      Graph::NodeItr nItr = optimalList.front();
+      Graph::NodeId nId = optimalList.front();
       optimalList.pop_front();
 
-      switch (s.getSolverDegree(nItr)) {
-        case 0: s.applyR0(nItr); break;
-        case 1: s.applyR1(nItr); break;
-        case 2: s.applyR2(nItr); break;
+      switch (s.getSolverDegree(nId)) {
+        case 0: s.applyR0(nId); break;
+        case 1: s.applyR1(nId); break;
+        case 2: s.applyR2(nId); break;
         default: llvm_unreachable(
                         "Optimal reductions of degree > 2 nodes is invalid.");
       }
@@ -185,7 +185,7 @@
 
     /// \brief Add a node to the heuristic reduce list.
     /// @param nItr Node iterator to add to the heuristic reduce list.
-    void addToHeuristicList(Graph::NodeItr nItr) {
+    void addToHeuristicList(Graph::NodeId nId) {
       llvm_unreachable("Must be implemented in derived class.");
     }
 
@@ -200,19 +200,19 @@
 
     /// \brief Prepare a change in the costs on the given edge.
     /// @param eItr Edge iterator.    
-    void preUpdateEdgeCosts(Graph::EdgeItr eItr) {
+    void preUpdateEdgeCosts(Graph::EdgeId eId) {
       llvm_unreachable("Must be implemented in derived class.");
     }
 
     /// \brief Handle the change in the costs on the given edge.
     /// @param eItr Edge iterator.
-    void postUpdateEdgeCostts(Graph::EdgeItr eItr) {
+    void postUpdateEdgeCostts(Graph::EdgeId eId) {
       llvm_unreachable("Must be implemented in derived class.");
     }
 
     /// \brief Handle the addition of a new edge into the PBQP graph.
     /// @param eItr Edge iterator for the added edge.
-    void handleAddEdge(Graph::EdgeItr eItr) {
+    void handleAddEdge(Graph::EdgeId eId) {
       llvm_unreachable("Must be implemented in derived class.");
     }
 
@@ -223,7 +223,7 @@
     /// Edges are frequently removed due to the removal of a node. This
     /// method allows for the effect to be computed only for the remaining
     /// node in the graph.
-    void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
+    void handleRemoveEdge(Graph::EdgeId eId, Graph::NodeId nId) {
       llvm_unreachable("Must be implemented in derived class.");
     }
 
diff --git a/include/llvm/CodeGen/PBQP/HeuristicSolver.h b/include/llvm/CodeGen/PBQP/HeuristicSolver.h
index 47e15b2..7fa6386 100644
--- a/include/llvm/CodeGen/PBQP/HeuristicSolver.h
+++ b/include/llvm/CodeGen/PBQP/HeuristicSolver.h
@@ -40,7 +40,7 @@
     typedef typename HImpl::NodeData HeuristicNodeData;
     typedef typename HImpl::EdgeData HeuristicEdgeData;
 
-    typedef std::list<Graph::EdgeItr> SolverEdges;
+    typedef std::list<Graph::EdgeId> SolverEdges;
 
   public:
   
@@ -55,9 +55,9 @@
 
       HeuristicNodeData& getHeuristicData() { return hData; }
 
-      SolverEdgeItr addSolverEdge(Graph::EdgeItr eItr) {
+      SolverEdgeItr addSolverEdge(Graph::EdgeId eId) {
         ++solverDegree;
-        return solverEdges.insert(solverEdges.end(), eItr);
+        return solverEdges.insert(solverEdges.end(), eId);
       }
 
       void removeSolverEdge(SolverEdgeItr seItr) {
@@ -104,7 +104,7 @@
     Graph &g;
     HImpl h;
     Solution s;
-    std::vector<Graph::NodeItr> stack;
+    std::vector<Graph::NodeId> stack;
 
     typedef std::list<NodeData> NodeDataList;
     NodeDataList nodeDataList;
@@ -127,15 +127,15 @@
     /// \brief Get the heuristic data attached to the given node.
     /// @param nItr Node iterator.
     /// @return The heuristic data attached to the given node.
-    HeuristicNodeData& getHeuristicNodeData(Graph::NodeItr nItr) {
-      return getSolverNodeData(nItr).getHeuristicData();
+    HeuristicNodeData& getHeuristicNodeData(Graph::NodeId nId) {
+      return getSolverNodeData(nId).getHeuristicData();
     }
 
     /// \brief Get the heuristic data attached to the given edge.
     /// @param eItr Edge iterator.
     /// @return The heuristic data attached to the given node.
-    HeuristicEdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) {
-      return getSolverEdgeData(eItr).getHeuristicData();
+    HeuristicEdgeData& getHeuristicEdgeData(Graph::EdgeId eId) {
+      return getSolverEdgeData(eId).getHeuristicData();
     }
 
     /// \brief Begin iterator for the set of edges adjacent to the given node in
@@ -143,8 +143,8 @@
     /// @param nItr Node iterator.
     /// @return Begin iterator for the set of edges adjacent to the given node
     ///         in the solver graph. 
-    SolverEdgeItr solverEdgesBegin(Graph::NodeItr nItr) {
-      return getSolverNodeData(nItr).solverEdgesBegin();
+    SolverEdgeItr solverEdgesBegin(Graph::NodeId nId) {
+      return getSolverNodeData(nId).solverEdgesBegin();
     }
 
     /// \brief End iterator for the set of edges adjacent to the given node in
@@ -152,8 +152,8 @@
     /// @param nItr Node iterator.
     /// @return End iterator for the set of edges adjacent to the given node in
     ///         the solver graph. 
-    SolverEdgeItr solverEdgesEnd(Graph::NodeItr nItr) {
-      return getSolverNodeData(nItr).solverEdgesEnd();
+    SolverEdgeItr solverEdgesEnd(Graph::NodeId nId) {
+      return getSolverNodeData(nId).solverEdgesEnd();
     }
 
     /// \brief Remove a node from the solver graph.
@@ -161,10 +161,10 @@
     ///
     /// Does <i>not</i> notify the heuristic of the removal. That should be
     /// done manually if necessary.
-    void removeSolverEdge(Graph::EdgeItr eItr) {
-      EdgeData &eData = getSolverEdgeData(eItr);
-      NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)),
-               &n2Data = getSolverNodeData(g.getEdgeNode2(eItr));
+    void removeSolverEdge(Graph::EdgeId eId) {
+      EdgeData &eData = getSolverEdgeData(eId);
+      NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eId)),
+               &n2Data = getSolverNodeData(g.getEdgeNode2(eId));
 
       n1Data.removeSolverEdge(eData.getN1SolverEdgeItr());
       n2Data.removeSolverEdge(eData.getN2SolverEdgeItr());
@@ -189,30 +189,30 @@
 
     /// \brief Add to the end of the stack.
     /// @param nItr Node iterator to add to the reduction stack.
-    void pushToStack(Graph::NodeItr nItr) {
-      getSolverNodeData(nItr).clearSolverEdges();
-      stack.push_back(nItr);
+    void pushToStack(Graph::NodeId nId) {
+      getSolverNodeData(nId).clearSolverEdges();
+      stack.push_back(nId);
     }
 
     /// \brief Returns the solver degree of the given node.
     /// @param nItr Node iterator for which degree is requested.
     /// @return Node degree in the <i>solver</i> graph (not the original graph).
-    unsigned getSolverDegree(Graph::NodeItr nItr) {
-      return  getSolverNodeData(nItr).getSolverDegree();
+    unsigned getSolverDegree(Graph::NodeId nId) {
+      return  getSolverNodeData(nId).getSolverDegree();
     }
 
     /// \brief Set the solution of the given node.
     /// @param nItr Node iterator to set solution for.
     /// @param selection Selection for node.
-    void setSolution(const Graph::NodeItr &nItr, unsigned selection) {
-      s.setSelection(nItr, selection);
+    void setSolution(const Graph::NodeId &nId, unsigned selection) {
+      s.setSelection(nId, selection);
 
-      for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr),
-                             aeEnd = g.adjEdgesEnd(nItr);
+      for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nId),
+                             aeEnd = g.adjEdgesEnd(nId);
            aeItr != aeEnd; ++aeItr) {
-        Graph::EdgeItr eItr(*aeItr);
-        Graph::NodeItr anItr(g.getEdgeOtherNode(eItr, nItr));
-        getSolverNodeData(anItr).addSolverEdge(eItr);
+        Graph::EdgeId eId(*aeItr);
+        Graph::NodeId anId(g.getEdgeOtherNode(eId, nId));
+        getSolverNodeData(anId).addSolverEdge(eId);
       }
     }
 
@@ -220,12 +220,12 @@
     /// @param nItr Node iterator for node to apply R0 to.
     ///
     /// Node will be automatically pushed to the solver stack.
-    void applyR0(Graph::NodeItr nItr) {
-      assert(getSolverNodeData(nItr).getSolverDegree() == 0 &&
+    void applyR0(Graph::NodeId nId) {
+      assert(getSolverNodeData(nId).getSolverDegree() == 0 &&
              "R0 applied to node with degree != 0.");
 
       // Nothing to do. Just push the node onto the reduction stack.
-      pushToStack(nItr);
+      pushToStack(nId);
 
       s.recordR0();
     }
@@ -234,20 +234,20 @@
     /// @param xnItr Node iterator for node to apply R1 to.
     ///
     /// Node will be automatically pushed to the solver stack.
-    void applyR1(Graph::NodeItr xnItr) {
-      NodeData &nd = getSolverNodeData(xnItr);
+    void applyR1(Graph::NodeId xnId) {
+      NodeData &nd = getSolverNodeData(xnId);
       assert(nd.getSolverDegree() == 1 &&
              "R1 applied to node with degree != 1.");
 
-      Graph::EdgeItr eItr = *nd.solverEdgesBegin();
+      Graph::EdgeId eId = *nd.solverEdgesBegin();
 
-      const Matrix &eCosts = g.getEdgeCosts(eItr);
-      const Vector &xCosts = g.getNodeCosts(xnItr);
+      const Matrix &eCosts = g.getEdgeCosts(eId);
+      const Vector &xCosts = g.getNodeCosts(xnId);
       
       // Duplicate a little to avoid transposing matrices.
-      if (xnItr == g.getEdgeNode1(eItr)) {
-        Graph::NodeItr ynItr = g.getEdgeNode2(eItr);
-        Vector &yCosts = g.getNodeCosts(ynItr);
+      if (xnId == g.getEdgeNode1(eId)) {
+        Graph::NodeId ynId = g.getEdgeNode2(eId);
+        Vector &yCosts = g.getNodeCosts(ynId);
         for (unsigned j = 0; j < yCosts.getLength(); ++j) {
           PBQPNum min = eCosts[0][j] + xCosts[0];
           for (unsigned i = 1; i < xCosts.getLength(); ++i) {
@@ -257,10 +257,10 @@
           }
           yCosts[j] += min;
         }
-        h.handleRemoveEdge(eItr, ynItr);
+        h.handleRemoveEdge(eId, ynId);
      } else {
-        Graph::NodeItr ynItr = g.getEdgeNode1(eItr);
-        Vector &yCosts = g.getNodeCosts(ynItr);
+        Graph::NodeId ynId = g.getEdgeNode1(eId);
+        Vector &yCosts = g.getNodeCosts(ynId);
         for (unsigned i = 0; i < yCosts.getLength(); ++i) {
           PBQPNum min = eCosts[i][0] + xCosts[0];
           for (unsigned j = 1; j < xCosts.getLength(); ++j) {
@@ -270,12 +270,12 @@
           }
           yCosts[i] += min;
         }
-        h.handleRemoveEdge(eItr, ynItr);
+        h.handleRemoveEdge(eId, ynId);
       }
-      removeSolverEdge(eItr);
+      removeSolverEdge(eId);
       assert(nd.getSolverDegree() == 0 &&
              "Degree 1 with edge removed should be 0.");
-      pushToStack(xnItr);
+      pushToStack(xnId);
       s.recordR1();
     }
 
@@ -283,30 +283,30 @@
     /// @param xnItr Node iterator for node to apply R2 to.
     ///
     /// Node will be automatically pushed to the solver stack.
-    void applyR2(Graph::NodeItr xnItr) {
-      assert(getSolverNodeData(xnItr).getSolverDegree() == 2 &&
+    void applyR2(Graph::NodeId xnId) {
+      assert(getSolverNodeData(xnId).getSolverDegree() == 2 &&
              "R2 applied to node with degree != 2.");
 
-      NodeData &nd = getSolverNodeData(xnItr);
-      const Vector &xCosts = g.getNodeCosts(xnItr);
+      NodeData &nd = getSolverNodeData(xnId);
+      const Vector &xCosts = g.getNodeCosts(xnId);
 
       SolverEdgeItr aeItr = nd.solverEdgesBegin();
-      Graph::EdgeItr yxeItr = *aeItr,
-                     zxeItr = *(++aeItr);
+      Graph::EdgeId yxeId = *aeItr,
+                    zxeId = *(++aeItr);
 
-      Graph::NodeItr ynItr = g.getEdgeOtherNode(yxeItr, xnItr),
-                     znItr = g.getEdgeOtherNode(zxeItr, xnItr);
+      Graph::NodeId ynId = g.getEdgeOtherNode(yxeId, xnId),
+                    znId = g.getEdgeOtherNode(zxeId, xnId);
 
-      bool flipEdge1 = (g.getEdgeNode1(yxeItr) == xnItr),
-           flipEdge2 = (g.getEdgeNode1(zxeItr) == xnItr);
+      bool flipEdge1 = (g.getEdgeNode1(yxeId) == xnId),
+           flipEdge2 = (g.getEdgeNode1(zxeId) == xnId);
 
       const Matrix *yxeCosts = flipEdge1 ?
-        new Matrix(g.getEdgeCosts(yxeItr).transpose()) :
-        &g.getEdgeCosts(yxeItr);
+        new Matrix(g.getEdgeCosts(yxeId).transpose()) :
+        &g.getEdgeCosts(yxeId);
 
       const Matrix *zxeCosts = flipEdge2 ?
-        new Matrix(g.getEdgeCosts(zxeItr).transpose()) :
-        &g.getEdgeCosts(zxeItr);
+        new Matrix(g.getEdgeCosts(zxeId).transpose()) :
+        &g.getEdgeCosts(zxeId);
 
       unsigned xLen = xCosts.getLength(),
                yLen = yxeCosts->getRows(),
@@ -333,27 +333,27 @@
       if (flipEdge2)
         delete zxeCosts;
 
-      Graph::EdgeItr yzeItr = g.findEdge(ynItr, znItr);
+      Graph::EdgeId yzeId = g.findEdge(ynId, znId);
       bool addedEdge = false;
 
-      if (yzeItr == g.edgesEnd()) {
-        yzeItr = g.addEdge(ynItr, znItr, delta);
+      if (yzeId == g.invalidEdgeId()) {
+        yzeId = g.addEdge(ynId, znId, delta);
         addedEdge = true;
       } else {
-        Matrix &yzeCosts = g.getEdgeCosts(yzeItr);
-        h.preUpdateEdgeCosts(yzeItr);
-        if (ynItr == g.getEdgeNode1(yzeItr)) {
+        Matrix &yzeCosts = g.getEdgeCosts(yzeId);
+        h.preUpdateEdgeCosts(yzeId);
+        if (ynId == g.getEdgeNode1(yzeId)) {
           yzeCosts += delta;
         } else {
           yzeCosts += delta.transpose();
         }
       }
 
-      bool nullCostEdge = tryNormaliseEdgeMatrix(yzeItr);
+      bool nullCostEdge = tryNormaliseEdgeMatrix(yzeId);
 
       if (!addedEdge) {
         // If we modified the edge costs let the heuristic know.
-        h.postUpdateEdgeCosts(yzeItr);
+        h.postUpdateEdgeCosts(yzeId);
       }
  
       if (nullCostEdge) {
@@ -361,26 +361,26 @@
         if (!addedEdge) {
           // We didn't just add it, so we need to notify the heuristic
           // and remove it from the solver.
-          h.handleRemoveEdge(yzeItr, ynItr);
-          h.handleRemoveEdge(yzeItr, znItr);
-          removeSolverEdge(yzeItr);
+          h.handleRemoveEdge(yzeId, ynId);
+          h.handleRemoveEdge(yzeId, znId);
+          removeSolverEdge(yzeId);
         }
-        g.removeEdge(yzeItr);
+        g.removeEdge(yzeId);
       } else if (addedEdge) {
         // If the edge was added, and non-null, finish setting it up, add it to
         // the solver & notify heuristic.
         edgeDataList.push_back(EdgeData());
-        g.setEdgeData(yzeItr, &edgeDataList.back());
-        addSolverEdge(yzeItr);
-        h.handleAddEdge(yzeItr);
+        g.setEdgeData(yzeId, &edgeDataList.back());
+        addSolverEdge(yzeId);
+        h.handleAddEdge(yzeId);
       }
 
-      h.handleRemoveEdge(yxeItr, ynItr);
-      removeSolverEdge(yxeItr);
-      h.handleRemoveEdge(zxeItr, znItr);
-      removeSolverEdge(zxeItr);
+      h.handleRemoveEdge(yxeId, ynId);
+      removeSolverEdge(yxeId);
+      h.handleRemoveEdge(zxeId, znId);
+      removeSolverEdge(zxeId);
 
-      pushToStack(xnItr);
+      pushToStack(xnId);
       s.recordR2();
     }
 
@@ -391,21 +391,21 @@
 
   private:
 
-    NodeData& getSolverNodeData(Graph::NodeItr nItr) {
-      return *static_cast<NodeData*>(g.getNodeData(nItr));
+    NodeData& getSolverNodeData(Graph::NodeId nId) {
+      return *static_cast<NodeData*>(g.getNodeData(nId));
     }
 
-    EdgeData& getSolverEdgeData(Graph::EdgeItr eItr) {
-      return *static_cast<EdgeData*>(g.getEdgeData(eItr));
+    EdgeData& getSolverEdgeData(Graph::EdgeId eId) {
+      return *static_cast<EdgeData*>(g.getEdgeData(eId));
     }
 
-    void addSolverEdge(Graph::EdgeItr eItr) {
-      EdgeData &eData = getSolverEdgeData(eItr);
-      NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)),
-               &n2Data = getSolverNodeData(g.getEdgeNode2(eItr));
+    void addSolverEdge(Graph::EdgeId eId) {
+      EdgeData &eData = getSolverEdgeData(eId);
+      NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eId)),
+               &n2Data = getSolverNodeData(g.getEdgeNode2(eId));
 
-      eData.setN1SolverEdgeItr(n1Data.addSolverEdge(eItr));
-      eData.setN2SolverEdgeItr(n2Data.addSolverEdge(eItr));
+      eData.setN1SolverEdgeItr(n1Data.addSolverEdge(eId));
+      eData.setN2SolverEdgeItr(n2Data.addSolverEdge(eId));
     }
 
     void setup() {
@@ -417,15 +417,15 @@
       for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
            nItr != nEnd; ++nItr) {
         nodeDataList.push_back(NodeData());
-        g.setNodeData(nItr, &nodeDataList.back());
+        g.setNodeData(*nItr, &nodeDataList.back());
       }
 
       // Create edge data objects.
       for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd();
            eItr != eEnd; ++eItr) {
         edgeDataList.push_back(EdgeData());
-        g.setEdgeData(eItr, &edgeDataList.back());
-        addSolverEdge(eItr);
+        g.setEdgeData(*eItr, &edgeDataList.back());
+        addSolverEdge(*eItr);
       }
     }
 
@@ -441,28 +441,30 @@
       for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
            nItr != nEnd; ++nItr) {
 
-        if (g.getNodeCosts(nItr).getLength() == 1) {
+        Graph::NodeId nId = *nItr;
 
-          std::vector<Graph::EdgeItr> edgesToRemove;
+        if (g.getNodeCosts(nId).getLength() == 1) {
 
-          for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr),
-                                 aeEnd = g.adjEdgesEnd(nItr);
+          std::vector<Graph::EdgeId> edgesToRemove;
+
+          for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nId),
+                                 aeEnd = g.adjEdgesEnd(nId);
                aeItr != aeEnd; ++aeItr) {
 
-            Graph::EdgeItr eItr = *aeItr;
+            Graph::EdgeId eId = *aeItr;
 
-            if (g.getEdgeNode1(eItr) == nItr) {
-              Graph::NodeItr otherNodeItr = g.getEdgeNode2(eItr);
-              g.getNodeCosts(otherNodeItr) +=
-                g.getEdgeCosts(eItr).getRowAsVector(0);
+            if (g.getEdgeNode1(eId) == nId) {
+              Graph::NodeId otherNodeId = g.getEdgeNode2(eId);
+              g.getNodeCosts(otherNodeId) +=
+                g.getEdgeCosts(eId).getRowAsVector(0);
             }
             else {
-              Graph::NodeItr otherNodeItr = g.getEdgeNode1(eItr);
-              g.getNodeCosts(otherNodeItr) +=
-                g.getEdgeCosts(eItr).getColAsVector(0);
+              Graph::NodeId otherNodeId = g.getEdgeNode1(eId);
+              g.getNodeCosts(otherNodeId) +=
+                g.getEdgeCosts(eId).getColAsVector(0);
             }
 
-            edgesToRemove.push_back(eItr);
+            edgesToRemove.push_back(eId);
           }
 
           if (!edgesToRemove.empty())
@@ -477,12 +479,12 @@
     }
 
     void eliminateIndependentEdges() {
-      std::vector<Graph::EdgeItr> edgesToProcess;
+      std::vector<Graph::EdgeId> edgesToProcess;
       unsigned numEliminated = 0;
 
       for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd();
            eItr != eEnd; ++eItr) {
-        edgesToProcess.push_back(eItr);
+        edgesToProcess.push_back(*eItr);
       }
 
       while (!edgesToProcess.empty()) {
@@ -492,21 +494,21 @@
       }
     }
 
-    bool tryToEliminateEdge(Graph::EdgeItr eItr) {
-      if (tryNormaliseEdgeMatrix(eItr)) {
-        g.removeEdge(eItr);
+    bool tryToEliminateEdge(Graph::EdgeId eId) {
+      if (tryNormaliseEdgeMatrix(eId)) {
+        g.removeEdge(eId);
         return true; 
       }
       return false;
     }
 
-    bool tryNormaliseEdgeMatrix(Graph::EdgeItr &eItr) {
+    bool tryNormaliseEdgeMatrix(Graph::EdgeId &eId) {
 
       const PBQPNum infinity = std::numeric_limits<PBQPNum>::infinity();
 
-      Matrix &edgeCosts = g.getEdgeCosts(eItr);
-      Vector &uCosts = g.getNodeCosts(g.getEdgeNode1(eItr)),
-             &vCosts = g.getNodeCosts(g.getEdgeNode2(eItr));
+      Matrix &edgeCosts = g.getEdgeCosts(eId);
+      Vector &uCosts = g.getNodeCosts(g.getEdgeNode1(eId)),
+             &vCosts = g.getNodeCosts(g.getEdgeNode2(eId));
 
       for (unsigned r = 0; r < edgeCosts.getRows(); ++r) {
         PBQPNum rowMin = infinity;
@@ -554,34 +556,34 @@
       }
     }
 
-    void computeSolution(Graph::NodeItr nItr) {
+    void computeSolution(Graph::NodeId nId) {
 
-      NodeData &nodeData = getSolverNodeData(nItr);
+      NodeData &nodeData = getSolverNodeData(nId);
 
-      Vector v(g.getNodeCosts(nItr));
+      Vector v(g.getNodeCosts(nId));
 
       // Solve based on existing solved edges.
       for (SolverEdgeItr solvedEdgeItr = nodeData.solverEdgesBegin(),
                          solvedEdgeEnd = nodeData.solverEdgesEnd();
            solvedEdgeItr != solvedEdgeEnd; ++solvedEdgeItr) {
 
-        Graph::EdgeItr eItr(*solvedEdgeItr);
-        Matrix &edgeCosts = g.getEdgeCosts(eItr);
+        Graph::EdgeId eId(*solvedEdgeItr);
+        Matrix &edgeCosts = g.getEdgeCosts(eId);
 
-        if (nItr == g.getEdgeNode1(eItr)) {
-          Graph::NodeItr adjNode(g.getEdgeNode2(eItr));
+        if (nId == g.getEdgeNode1(eId)) {
+          Graph::NodeId adjNode(g.getEdgeNode2(eId));
           unsigned adjSolution = s.getSelection(adjNode);
           v += edgeCosts.getColAsVector(adjSolution);
         }
         else {
-          Graph::NodeItr adjNode(g.getEdgeNode1(eItr));
+          Graph::NodeId adjNode(g.getEdgeNode1(eId));
           unsigned adjSolution = s.getSelection(adjNode);
           v += edgeCosts.getRowAsVector(adjSolution);
         }
 
       }
 
-      setSolution(nItr, v.minIndex());
+      setSolution(nId, v.minIndex());
     }
 
     void cleanup() {
diff --git a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h
index 307d81e..9663b26 100644
--- a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h
+++ b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h
@@ -47,8 +47,8 @@
       class LinkDegreeComparator {
       public:
         LinkDegreeComparator(HeuristicSolverImpl<Briggs> &s) : s(&s) {}
-        bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
-          if (s->getSolverDegree(n1Itr) > s->getSolverDegree(n2Itr))
+        bool operator()(Graph::NodeId n1Id, Graph::NodeId n2Id) const {
+          if (s->getSolverDegree(n1Id) > s->getSolverDegree(n2Id))
             return true;
           return false;
         }
@@ -60,12 +60,12 @@
       public:
         SpillCostComparator(HeuristicSolverImpl<Briggs> &s)
           : s(&s), g(&s.getGraph()) {}
-        bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
-          const PBQP::Vector &cv1 = g->getNodeCosts(n1Itr);
-          const PBQP::Vector &cv2 = g->getNodeCosts(n2Itr);
+        bool operator()(Graph::NodeId n1Id, Graph::NodeId n2Id) const {
+          const PBQP::Vector &cv1 = g->getNodeCosts(n1Id);
+          const PBQP::Vector &cv2 = g->getNodeCosts(n2Id);
 
-          PBQPNum cost1 = cv1[0] / s->getSolverDegree(n1Itr);
-          PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Itr);
+          PBQPNum cost1 = cv1[0] / s->getSolverDegree(n1Id);
+          PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Id);
 
           if (cost1 < cost2)
             return true;
@@ -77,10 +77,10 @@
         Graph *g;
       };
 
-      typedef std::list<Graph::NodeItr> RNAllocableList;
+      typedef std::list<Graph::NodeId> RNAllocableList;
       typedef RNAllocableList::iterator RNAllocableListItr;
 
-      typedef std::list<Graph::NodeItr> RNUnallocableList;  
+      typedef std::list<Graph::NodeId> RNUnallocableList;  
       typedef RNUnallocableList::iterator RNUnallocableListItr;
 
     public:
@@ -123,8 +123,8 @@
       /// infinite are checked for allocability first. Allocable nodes may be
       /// optimally reduced, but nodes whose allocability cannot be proven are
       /// selected for heuristic reduction instead.
-      bool shouldOptimallyReduce(Graph::NodeItr nItr) {
-        if (getSolver().getSolverDegree(nItr) < 3) {
+      bool shouldOptimallyReduce(Graph::NodeId nId) {
+        if (getSolver().getSolverDegree(nId) < 3) {
           return true;
         }
         // else
@@ -133,14 +133,14 @@
 
       /// \brief Add a node to the heuristic reduce list.
       /// @param nItr Node iterator to add to the heuristic reduce list.
-      void addToHeuristicReduceList(Graph::NodeItr nItr) {
-        NodeData &nd = getHeuristicNodeData(nItr);
-        initializeNode(nItr);
+      void addToHeuristicReduceList(Graph::NodeId nId) {
+        NodeData &nd = getHeuristicNodeData(nId);
+        initializeNode(nId);
         nd.isHeuristic = true;
         if (nd.isAllocable) {
-          nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr);
+          nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nId);
         } else {
-          nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nItr);
+          nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nId);
         }
       }
 
@@ -159,19 +159,19 @@
           RNAllocableListItr rnaItr =
             min_element(rnAllocableList.begin(), rnAllocableList.end(),
                         LinkDegreeComparator(getSolver()));
-          Graph::NodeItr nItr = *rnaItr;
+          Graph::NodeId nId = *rnaItr;
           rnAllocableList.erase(rnaItr);
-          handleRemoveNode(nItr);
-          getSolver().pushToStack(nItr);
+          handleRemoveNode(nId);
+          getSolver().pushToStack(nId);
           return true;
         } else if (!rnUnallocableList.empty()) {
           RNUnallocableListItr rnuItr =
             min_element(rnUnallocableList.begin(), rnUnallocableList.end(),
                         SpillCostComparator(getSolver()));
-          Graph::NodeItr nItr = *rnuItr;
+          Graph::NodeId nId = *rnuItr;
           rnUnallocableList.erase(rnuItr);
-          handleRemoveNode(nItr);
-          getSolver().pushToStack(nItr);
+          handleRemoveNode(nId);
+          getSolver().pushToStack(nId);
           return true;
         }
         // else
@@ -180,28 +180,28 @@
 
       /// \brief Prepare a change in the costs on the given edge.
       /// @param eItr Edge iterator.    
-      void preUpdateEdgeCosts(Graph::EdgeItr eItr) {
+      void preUpdateEdgeCosts(Graph::EdgeId eId) {
         Graph &g = getGraph();
-        Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
-                       n2Itr = g.getEdgeNode2(eItr);
-        NodeData &n1 = getHeuristicNodeData(n1Itr),
-                 &n2 = getHeuristicNodeData(n2Itr);
+        Graph::NodeId n1Id = g.getEdgeNode1(eId),
+                      n2Id = g.getEdgeNode2(eId);
+        NodeData &n1 = getHeuristicNodeData(n1Id),
+                 &n2 = getHeuristicNodeData(n2Id);
 
         if (n1.isHeuristic)
-          subtractEdgeContributions(eItr, getGraph().getEdgeNode1(eItr));
+          subtractEdgeContributions(eId, getGraph().getEdgeNode1(eId));
         if (n2.isHeuristic)
-          subtractEdgeContributions(eItr, getGraph().getEdgeNode2(eItr));
+          subtractEdgeContributions(eId, getGraph().getEdgeNode2(eId));
 
-        EdgeData &ed = getHeuristicEdgeData(eItr);
+        EdgeData &ed = getHeuristicEdgeData(eId);
         ed.isUpToDate = false;
       }
 
       /// \brief Handle the change in the costs on the given edge.
       /// @param eItr Edge iterator.
-      void postUpdateEdgeCosts(Graph::EdgeItr eItr) {
+      void postUpdateEdgeCosts(Graph::EdgeId eId) {
         // This is effectively the same as adding a new edge now, since
         // we've factored out the costs of the old one.
-        handleAddEdge(eItr);
+        handleAddEdge(eId);
       }
 
       /// \brief Handle the addition of a new edge into the PBQP graph.
@@ -210,12 +210,12 @@
       /// Updates allocability of any nodes connected by this edge which are
       /// being managed by the heuristic. If allocability changes they are
       /// moved to the appropriate list.
-      void handleAddEdge(Graph::EdgeItr eItr) {
+      void handleAddEdge(Graph::EdgeId eId) {
         Graph &g = getGraph();
-        Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
-                       n2Itr = g.getEdgeNode2(eItr);
-        NodeData &n1 = getHeuristicNodeData(n1Itr),
-                 &n2 = getHeuristicNodeData(n2Itr);
+        Graph::NodeId n1Id = g.getEdgeNode1(eId),
+                      n2Id = g.getEdgeNode2(eId);
+        NodeData &n1 = getHeuristicNodeData(n1Id),
+                 &n2 = getHeuristicNodeData(n2Id);
 
         // If neither node is managed by the heuristic there's nothing to be
         // done.
@@ -223,29 +223,29 @@
           return;
 
         // Ok - we need to update at least one node.
-        computeEdgeContributions(eItr);
+        computeEdgeContributions(eId);
 
         // Update node 1 if it's managed by the heuristic.
         if (n1.isHeuristic) {
           bool n1WasAllocable = n1.isAllocable;
-          addEdgeContributions(eItr, n1Itr);
-          updateAllocability(n1Itr);
+          addEdgeContributions(eId, n1Id);
+          updateAllocability(n1Id);
           if (n1WasAllocable && !n1.isAllocable) {
             rnAllocableList.erase(n1.rnaItr);
             n1.rnuItr =
-              rnUnallocableList.insert(rnUnallocableList.end(), n1Itr);
+              rnUnallocableList.insert(rnUnallocableList.end(), n1Id);
           }
         }
 
         // Likewise for node 2.
         if (n2.isHeuristic) {
           bool n2WasAllocable = n2.isAllocable;
-          addEdgeContributions(eItr, n2Itr);
-          updateAllocability(n2Itr);
+          addEdgeContributions(eId, n2Id);
+          updateAllocability(n2Id);
           if (n2WasAllocable && !n2.isAllocable) {
             rnAllocableList.erase(n2.rnaItr);
             n2.rnuItr =
-              rnUnallocableList.insert(rnUnallocableList.end(), n2Itr);
+              rnUnallocableList.insert(rnUnallocableList.end(), n2Id);
           }
         }
       }
@@ -256,27 +256,27 @@
       ///
       /// Updates allocability of the given node and, if appropriate, moves the
       /// node to a new list.
-      void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
-        NodeData &nd = getHeuristicNodeData(nItr);
+      void handleRemoveEdge(Graph::EdgeId eId, Graph::NodeId nId) {
+        NodeData &nd =getHeuristicNodeData(nId);
 
         // If the node is not managed by the heuristic there's nothing to be
         // done.
         if (!nd.isHeuristic)
           return;
 
-        EdgeData &ed = getHeuristicEdgeData(eItr);
+        EdgeData &ed = getHeuristicEdgeData(eId);
         (void)ed;
         assert(ed.isUpToDate && "Edge data is not up to date.");
 
         // Update node.
         bool ndWasAllocable = nd.isAllocable;
-        subtractEdgeContributions(eItr, nItr);
-        updateAllocability(nItr);
+        subtractEdgeContributions(eId, nId);
+        updateAllocability(nId);
 
         // If the node has gone optimal...
-        if (shouldOptimallyReduce(nItr)) {
+        if (shouldOptimallyReduce(nId)) {
           nd.isHeuristic = false;
-          addToOptimalReduceList(nItr);
+          addToOptimalReduceList(nId);
           if (ndWasAllocable) {
             rnAllocableList.erase(nd.rnaItr);
           } else {
@@ -287,30 +287,30 @@
           // from "unallocable" to "allocable".
           if (!ndWasAllocable && nd.isAllocable) {
             rnUnallocableList.erase(nd.rnuItr);
-            nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr);
+            nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nId);
           }
         }
       }
 
     private:
 
-      NodeData& getHeuristicNodeData(Graph::NodeItr nItr) {
-        return getSolver().getHeuristicNodeData(nItr);
+      NodeData& getHeuristicNodeData(Graph::NodeId nId) {
+        return getSolver().getHeuristicNodeData(nId);
       }
 
-      EdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) {
-        return getSolver().getHeuristicEdgeData(eItr);
+      EdgeData& getHeuristicEdgeData(Graph::EdgeId eId) {
+        return getSolver().getHeuristicEdgeData(eId);
       }
 
       // Work out what this edge will contribute to the allocability of the
       // nodes connected to it.
-      void computeEdgeContributions(Graph::EdgeItr eItr) {
-        EdgeData &ed = getHeuristicEdgeData(eItr);
+      void computeEdgeContributions(Graph::EdgeId eId) {
+        EdgeData &ed = getHeuristicEdgeData(eId);
 
         if (ed.isUpToDate)
           return; // Edge data is already up to date.
 
-        Matrix &eCosts = getGraph().getEdgeCosts(eItr);
+        Matrix &eCosts = getGraph().getEdgeCosts(eId);
 
         unsigned numRegs = eCosts.getRows() - 1,
                  numReverseRegs = eCosts.getCols() - 1;
@@ -352,15 +352,15 @@
       // numDenied and safe members. No action is taken other than to update
       // these member values. Once updated these numbers can be used by clients
       // to update the node's allocability.
-      void addEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
-        EdgeData &ed = getHeuristicEdgeData(eItr);
+      void addEdgeContributions(Graph::EdgeId eId, Graph::NodeId nId) {
+        EdgeData &ed = getHeuristicEdgeData(eId);
 
         assert(ed.isUpToDate && "Using out-of-date edge numbers.");
 
-        NodeData &nd = getHeuristicNodeData(nItr);
-        unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
+        NodeData &nd = getHeuristicNodeData(nId);
+        unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1;
         
-        bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
+        bool nIsNode1 = nId == getGraph().getEdgeNode1(eId);
         EdgeData::UnsafeArray &unsafe =
           nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
         nd.numDenied += nIsNode1 ? ed.worst : ed.reverseWorst;
@@ -379,15 +379,15 @@
       // numDenied and safe members. No action is taken other than to update
       // these member values. Once updated these numbers can be used by clients
       // to update the node's allocability.
-      void subtractEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
-        EdgeData &ed = getHeuristicEdgeData(eItr);
+      void subtractEdgeContributions(Graph::EdgeId eId, Graph::NodeId nId) {
+        EdgeData &ed = getHeuristicEdgeData(eId);
 
         assert(ed.isUpToDate && "Using out-of-date edge numbers.");
 
-        NodeData &nd = getHeuristicNodeData(nItr);
-        unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
+        NodeData &nd = getHeuristicNodeData(nId);
+        unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1;
         
-        bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
+        bool nIsNode1 = nId == getGraph().getEdgeNode1(eId);
         EdgeData::UnsafeArray &unsafe =
           nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
         nd.numDenied -= nIsNode1 ? ed.worst : ed.reverseWorst;
@@ -402,22 +402,22 @@
         }
       }
 
-      void updateAllocability(Graph::NodeItr nItr) {
-        NodeData &nd = getHeuristicNodeData(nItr);
-        unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
+      void updateAllocability(Graph::NodeId nId) {
+        NodeData &nd = getHeuristicNodeData(nId);
+        unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1;
         nd.isAllocable = nd.numDenied < numRegs || nd.numSafe > 0;
       }
 
-      void initializeNode(Graph::NodeItr nItr) {
-        NodeData &nd = getHeuristicNodeData(nItr);
+      void initializeNode(Graph::NodeId nId) {
+        NodeData &nd = getHeuristicNodeData(nId);
 
         if (nd.isInitialized)
           return; // Node data is already up to date.
 
-        unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
+        unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1;
 
         nd.numDenied = 0;
-        const Vector& nCosts = getGraph().getNodeCosts(nItr);
+        const Vector& nCosts = getGraph().getNodeCosts(nId);
         for (unsigned i = 1; i < nCosts.getLength(); ++i) {
           if (nCosts[i] == std::numeric_limits<PBQPNum>::infinity())
             ++nd.numDenied;
@@ -428,27 +428,27 @@
 
         typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
 
-        for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nItr),
-                           aeEnd = getSolver().solverEdgesEnd(nItr);
+        for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nId),
+                           aeEnd = getSolver().solverEdgesEnd(nId);
              aeItr != aeEnd; ++aeItr) {
           
-          Graph::EdgeItr eItr = *aeItr;
-          computeEdgeContributions(eItr);
-          addEdgeContributions(eItr, nItr);
+          Graph::EdgeId eId = *aeItr;
+          computeEdgeContributions(eId);
+          addEdgeContributions(eId, nId);
         }
 
-        updateAllocability(nItr);
+        updateAllocability(nId);
         nd.isInitialized = true;
       }
 
-      void handleRemoveNode(Graph::NodeItr xnItr) {
+      void handleRemoveNode(Graph::NodeId xnId) {
         typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
-        std::vector<Graph::EdgeItr> edgesToRemove;
-        for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnItr),
-                           aeEnd = getSolver().solverEdgesEnd(xnItr);
+        std::vector<Graph::EdgeId> edgesToRemove;
+        for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnId),
+                           aeEnd = getSolver().solverEdgesEnd(xnId);
              aeItr != aeEnd; ++aeItr) {
-          Graph::NodeItr ynItr = getGraph().getEdgeOtherNode(*aeItr, xnItr);
-          handleRemoveEdge(*aeItr, ynItr);
+          Graph::NodeId ynId = getGraph().getEdgeOtherNode(*aeItr, xnId);
+          handleRemoveEdge(*aeItr, ynId);
           edgesToRemove.push_back(*aeItr);
         }
         while (!edgesToRemove.empty()) {
diff --git a/include/llvm/CodeGen/PBQP/Solution.h b/include/llvm/CodeGen/PBQP/Solution.h
index b9f288b..98ba5a1 100644
--- a/include/llvm/CodeGen/PBQP/Solution.h
+++ b/include/llvm/CodeGen/PBQP/Solution.h
@@ -26,8 +26,7 @@
   class Solution {
   private:
 
-    typedef std::map<Graph::ConstNodeItr, unsigned,
-                     NodeItrComparator> SelectionsMap;
+    typedef std::map<Graph::NodeId, unsigned> SelectionsMap;
     SelectionsMap selections;
 
     unsigned r0Reductions, r1Reductions, r2Reductions, rNReductions;
@@ -73,15 +72,15 @@
     /// \brief Set the selection for a given node.
     /// @param nItr Node iterator.
     /// @param selection Selection for nItr.
-    void setSelection(Graph::NodeItr nItr, unsigned selection) {
-      selections[nItr] = selection;
+    void setSelection(Graph::NodeId nodeId, unsigned selection) {
+      selections[nodeId] = selection;
     }
 
     /// \brief Get a node's selection.
     /// @param nItr Node iterator.
     /// @return The selection for nItr;
-    unsigned getSelection(Graph::ConstNodeItr nItr) const {
-      SelectionsMap::const_iterator sItr = selections.find(nItr);
+    unsigned getSelection(Graph::NodeId nodeId) const {
+      SelectionsMap::const_iterator sItr = selections.find(nodeId);
       assert(sItr != selections.end() && "No selection for node.");
       return sItr->second;
     }
diff --git a/include/llvm/CodeGen/RegAllocPBQP.h b/include/llvm/CodeGen/RegAllocPBQP.h
index 6f2d139..7472e5a 100644
--- a/include/llvm/CodeGen/RegAllocPBQP.h
+++ b/include/llvm/CodeGen/RegAllocPBQP.h
@@ -52,22 +52,22 @@
     /// PBQPBuilder you are unlikely to need this: Nodes and options for all
     /// vregs will already have been set up for you by the base class. 
     template <typename AllowedRegsItr>
-    void recordVReg(unsigned vreg, PBQP::Graph::NodeItr node,
+    void recordVReg(unsigned vreg, PBQP::Graph::NodeId nodeId,
                     AllowedRegsItr arBegin, AllowedRegsItr arEnd) {
-      assert(node2VReg.find(node) == node2VReg.end() && "Re-mapping node.");
+      assert(node2VReg.find(nodeId) == node2VReg.end() && "Re-mapping node.");
       assert(vreg2Node.find(vreg) == vreg2Node.end() && "Re-mapping vreg.");
       assert(allowedSets[vreg].empty() && "vreg already has pregs.");
 
-      node2VReg[node] = vreg;
-      vreg2Node[vreg] = node;
+      node2VReg[nodeId] = vreg;
+      vreg2Node[vreg] = nodeId;
       std::copy(arBegin, arEnd, std::back_inserter(allowedSets[vreg]));
     }
 
     /// Get the virtual register corresponding to the given PBQP node.
-    unsigned getVRegForNode(PBQP::Graph::ConstNodeItr node) const;
+    unsigned getVRegForNode(PBQP::Graph::NodeId nodeId) const;
 
     /// Get the PBQP node corresponding to the given virtual register.
-    PBQP::Graph::NodeItr getNodeForVReg(unsigned vreg) const;
+    PBQP::Graph::NodeId getNodeForVReg(unsigned vreg) const;
 
     /// Returns true if the given PBQP option represents a physical register,
     /// false otherwise.
@@ -92,9 +92,8 @@
 
   private:
 
-    typedef std::map<PBQP::Graph::ConstNodeItr, unsigned,
-                     PBQP::NodeItrComparator>  Node2VReg;
-    typedef DenseMap<unsigned, PBQP::Graph::NodeItr> VReg2Node;
+    typedef std::map<PBQP::Graph::NodeId, unsigned>  Node2VReg;
+    typedef DenseMap<unsigned, PBQP::Graph::NodeId> VReg2Node;
     typedef DenseMap<unsigned, AllowedSet> AllowedSetMap;
 
     PBQP::Graph graph;
diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp
index 7786ecd..3873853 100644
--- a/lib/CodeGen/RegAllocPBQP.cpp
+++ b/lib/CodeGen/RegAllocPBQP.cpp
@@ -158,13 +158,13 @@
 
 } // End anonymous namespace.
 
-unsigned PBQPRAProblem::getVRegForNode(PBQP::Graph::ConstNodeItr node) const {
+unsigned PBQPRAProblem::getVRegForNode(PBQP::Graph::NodeId node) const {
   Node2VReg::const_iterator vregItr = node2VReg.find(node);
   assert(vregItr != node2VReg.end() && "No vreg for node.");
   return vregItr->second;
 }
 
-PBQP::Graph::NodeItr PBQPRAProblem::getNodeForVReg(unsigned vreg) const {
+PBQP::Graph::NodeId PBQPRAProblem::getNodeForVReg(unsigned vreg) const {
   VReg2Node::const_iterator nodeItr = vreg2Node.find(vreg);
   assert(nodeItr != vreg2Node.end() && "No node for vreg.");
   return nodeItr->second;
@@ -247,7 +247,7 @@
     }
 
     // Construct the node.
-    PBQP::Graph::NodeItr node =
+    PBQP::Graph::NodeId node =
       g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0));
 
     // Record the mapping and allowed set in the problem.
@@ -273,7 +273,7 @@
 
       assert(!l2.empty() && "Empty interval in vreg set?");
       if (l1.overlaps(l2)) {
-        PBQP::Graph::EdgeItr edge =
+        PBQP::Graph::EdgeId edge =
           g.addEdge(p->getNodeForVReg(vr1), p->getNodeForVReg(vr2),
                     PBQP::Matrix(vr1Allowed.size()+1, vr2Allowed.size()+1, 0));
 
@@ -364,16 +364,16 @@
         }
         if (pregOpt < allowed.size()) {
           ++pregOpt; // +1 to account for spill option.
-          PBQP::Graph::NodeItr node = p->getNodeForVReg(src);
+          PBQP::Graph::NodeId node = p->getNodeForVReg(src);
           addPhysRegCoalesce(g.getNodeCosts(node), pregOpt, cBenefit);
         }
       } else {
         const PBQPRAProblem::AllowedSet *allowed1 = &p->getAllowedSet(dst);
         const PBQPRAProblem::AllowedSet *allowed2 = &p->getAllowedSet(src);
-        PBQP::Graph::NodeItr node1 = p->getNodeForVReg(dst);
-        PBQP::Graph::NodeItr node2 = p->getNodeForVReg(src);
-        PBQP::Graph::EdgeItr edge = g.findEdge(node1, node2);
-        if (edge == g.edgesEnd()) {
+        PBQP::Graph::NodeId node1 = p->getNodeForVReg(dst);
+        PBQP::Graph::NodeId node2 = p->getNodeForVReg(src);
+        PBQP::Graph::EdgeId edge = g.findEdge(node1, node2);
+        if (edge == g.invalidEdgeId()) {
           edge = g.addEdge(node1, node2, PBQP::Matrix(allowed1->size() + 1,
                                                       allowed2->size() + 1,
                                                       0));
@@ -477,11 +477,11 @@
   const PBQP::Graph &g = problem.getGraph();
   // Iterate over the nodes mapping the PBQP solution to a register
   // assignment.
-  for (PBQP::Graph::ConstNodeItr node = g.nodesBegin(),
-                                 nodeEnd = g.nodesEnd();
-       node != nodeEnd; ++node) {
-    unsigned vreg = problem.getVRegForNode(node);
-    unsigned alloc = solution.getSelection(node);
+  for (PBQP::Graph::NodeItr nodeItr = g.nodesBegin(),
+                            nodeEnd = g.nodesEnd();
+       nodeItr != nodeEnd; ++nodeItr) {
+    unsigned vreg = problem.getVRegForNode(*nodeItr);
+    unsigned alloc = solution.getSelection(*nodeItr);
 
     if (problem.isPRegOption(vreg, alloc)) {
       unsigned preg = problem.getPRegForOption(vreg, alloc);