Update aosp/master LLVM for rebase to r222494.

Change-Id: Ic787f5e0124df789bd26f3f24680f45e678eef2d

6 files changed, 248 insertions, 526 deletions

diff --git a/include/llvm/CodeGen/PBQP/CostAllocator.h b/include/llvm/CodeGen/PBQP/CostAllocator.h
index ff62c09..02d39fe 100644
--- a/include/llvm/CodeGen/PBQP/CostAllocator.h
+++ b/include/llvm/CodeGen/PBQP/CostAllocator.h
@@ -15,117 +15,101 @@
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_COSTALLOCATOR_H
-#define LLVM_COSTALLOCATOR_H
+#ifndef LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
+#define LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
 
-#include <set>
+#include "llvm/ADT/DenseSet.h"
+#include <memory>
 #include <type_traits>
 
+namespace llvm {
 namespace PBQP {
 
-template <typename CostT,
-          typename CostKeyTComparator>
-class CostPool {
+template <typename ValueT>
+class ValuePool {
 public:
+  typedef std::shared_ptr<const ValueT> PoolRef;
 
-  class PoolEntry {
+private:
+
+  class PoolEntry : public std::enable_shared_from_this<PoolEntry> {
   public:
-    template <typename CostKeyT>
-    PoolEntry(CostPool &pool, CostKeyT cost)
-      : pool(pool), cost(std::move(cost)), refCount(0) {}
-    ~PoolEntry() { pool.removeEntry(this); }
-    void incRef() { ++refCount; }
-    bool decRef() { --refCount; return (refCount == 0); }
-    CostT& getCost() { return cost; }
-    const CostT& getCost() const { return cost; }
+    template <typename ValueKeyT>
+    PoolEntry(ValuePool &Pool, ValueKeyT Value)
+        : Pool(Pool), Value(std::move(Value)) {}
+    ~PoolEntry() { Pool.removeEntry(this); }
+    const ValueT& getValue() const { return Value; }
   private:
-    CostPool &pool;
-    CostT cost;
-    std::size_t refCount;
+    ValuePool &Pool;
+    ValueT Value;
   };
 
-  class PoolRef {
+  class PoolEntryDSInfo {
   public:
-    PoolRef(PoolEntry *entry) : entry(entry) {
-      this->entry->incRef();
+    static inline PoolEntry* getEmptyKey() { return nullptr; }
+
+    static inline PoolEntry* getTombstoneKey() {
+      return reinterpret_cast<PoolEntry*>(static_cast<uintptr_t>(1));
     }
-    PoolRef(const PoolRef &r) {
-      entry = r.entry;
-      entry->incRef();
+
+    template <typename ValueKeyT>
+    static unsigned getHashValue(const ValueKeyT &C) {
+      return hash_value(C);
     }
-    PoolRef& operator=(const PoolRef &r) {
-      assert(entry != nullptr && "entry should not be null.");
-      PoolEntry *temp = r.entry;
-      temp->incRef();
-      entry->decRef();
-      entry = temp;
-      return *this;
+
+    static unsigned getHashValue(PoolEntry *P) {
+      return getHashValue(P->getValue());
     }
 
-    ~PoolRef() {
-      if (entry->decRef())
-        delete entry;
+    static unsigned getHashValue(const PoolEntry *P) {
+      return getHashValue(P->getValue());
     }
-    void reset(PoolEntry *entry) {
-      entry->incRef();
-      this->entry->decRef();
-      this->entry = entry;
+
+    template <typename ValueKeyT1, typename ValueKeyT2>
+    static
+    bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
+      return C1 == C2;
     }
-    CostT& operator*() { return entry->getCost(); }
-    const CostT& operator*() const { return entry->getCost(); }
-    CostT* operator->() { return &entry->getCost(); }
-    const CostT* operator->() const { return &entry->getCost(); }
-  private:
-    PoolEntry *entry;
-  };
 
-private:
-  class EntryComparator {
-  public:
-    template <typename CostKeyT>
-    typename std::enable_if<
-               !std::is_same<PoolEntry*,
-                             typename std::remove_const<CostKeyT>::type>::value,
-               bool>::type
-    operator()(const PoolEntry* a, const CostKeyT &b) {
-      return compare(a->getCost(), b);
+    template <typename ValueKeyT>
+    static bool isEqual(const ValueKeyT &C, PoolEntry *P) {
+      if (P == getEmptyKey() || P == getTombstoneKey())
+        return false;
+      return isEqual(C, P->getValue());
     }
-    bool operator()(const PoolEntry* a, const PoolEntry* b) {
-      return compare(a->getCost(), b->getCost());
+
+    static bool isEqual(PoolEntry *P1, PoolEntry *P2) {
+      if (P1 == getEmptyKey() || P1 == getTombstoneKey())
+        return P1 == P2;
+      return isEqual(P1->getValue(), P2);
     }
-  private:
-    CostKeyTComparator compare;
+
   };
 
-  typedef std::set<PoolEntry*, EntryComparator> EntrySet;
+  typedef DenseSet<PoolEntry*, PoolEntryDSInfo> EntrySetT;
 
-  EntrySet entrySet;
+  EntrySetT EntrySet;
 
-  void removeEntry(PoolEntry *p) { entrySet.erase(p); }
+  void removeEntry(PoolEntry *P) { EntrySet.erase(P); }
 
 public:
+  template <typename ValueKeyT> PoolRef getValue(ValueKeyT ValueKey) {
+    typename EntrySetT::iterator I = EntrySet.find_as(ValueKey);
 
-  template <typename CostKeyT>
-  PoolRef getCost(CostKeyT costKey) {
-    typename EntrySet::iterator itr =
-      std::lower_bound(entrySet.begin(), entrySet.end(), costKey,
-                       EntryComparator());
-
-    if (itr != entrySet.end() && costKey == (*itr)->getCost())
-      return PoolRef(*itr);
+    if (I != EntrySet.end())
+      return PoolRef((*I)->shared_from_this(), &(*I)->getValue());
 
-    PoolEntry *p = new PoolEntry(*this, std::move(costKey));
-    entrySet.insert(itr, p);
-    return PoolRef(p);
+    auto P = std::make_shared<PoolEntry>(*this, std::move(ValueKey));
+    EntrySet.insert(P.get());
+    return PoolRef(std::move(P), &P->getValue());
   }
 };
 
-template <typename VectorT, typename VectorTComparator,
-          typename MatrixT, typename MatrixTComparator>
+template <typename VectorT, typename MatrixT>
 class PoolCostAllocator {
 private:
-  typedef CostPool<VectorT, VectorTComparator> VectorCostPool;
-  typedef CostPool<MatrixT, MatrixTComparator> MatrixCostPool;
+  typedef ValuePool<VectorT> VectorCostPool;
+  typedef ValuePool<MatrixT> MatrixCostPool;
 public:
   typedef VectorT Vector;
   typedef MatrixT Matrix;
@@ -133,15 +117,16 @@ public:
   typedef typename MatrixCostPool::PoolRef MatrixPtr;
 
   template <typename VectorKeyT>
-  VectorPtr getVector(VectorKeyT v) { return vectorPool.getCost(std::move(v)); }
+  VectorPtr getVector(VectorKeyT v) { return VectorPool.getValue(std::move(v)); }
 
   template <typename MatrixKeyT>
-  MatrixPtr getMatrix(MatrixKeyT m) { return matrixPool.getCost(std::move(m)); }
+  MatrixPtr getMatrix(MatrixKeyT m) { return MatrixPool.getValue(std::move(m)); }
 private:
-  VectorCostPool vectorPool;
-  MatrixCostPool matrixPool;
+  VectorCostPool VectorPool;
+  MatrixCostPool MatrixPool;
 };
 
-}
+} // namespace PBQP
+} // namespace llvm
 
-#endif // LLVM_COSTALLOCATOR_H
+#endif
diff --git a/include/llvm/CodeGen/PBQP/Graph.h b/include/llvm/CodeGen/PBQP/Graph.h
index a55f0ea..4dc5674 100644
--- a/include/llvm/CodeGen/PBQP/Graph.h
+++ b/include/llvm/CodeGen/PBQP/Graph.h
@@ -17,11 +17,12 @@
 
 #include "llvm/ADT/ilist.h"
 #include "llvm/ADT/ilist_node.h"
-#include "llvm/Support/Compiler.h"
+#include "llvm/Support/Debug.h"
 #include <list>
 #include <map>
 #include <set>
 
+namespace llvm {
 namespace PBQP {
 
   class GraphBase {
@@ -29,12 +30,12 @@ namespace PBQP {
     typedef unsigned NodeId;
     typedef unsigned EdgeId;
 
-    /// \brief Returns a value representing an invalid (non-existent) node.
+    /// @brief Returns a value representing an invalid (non-existent) node.
     static NodeId invalidNodeId() {
       return std::numeric_limits<NodeId>::max();
     }
 
-    /// \brief Returns a value representing an invalid (non-existent) edge.
+    /// @brief Returns a value representing an invalid (non-existent) edge.
     static EdgeId invalidEdgeId() {
       return std::numeric_limits<EdgeId>::max();
     }
@@ -56,6 +57,7 @@ namespace PBQP {
     typedef typename CostAllocator::MatrixPtr MatrixPtr;
     typedef typename SolverT::NodeMetadata NodeMetadata;
     typedef typename SolverT::EdgeMetadata EdgeMetadata;
+    typedef typename SolverT::GraphMetadata GraphMetadata;
 
   private:
 
@@ -172,6 +174,7 @@ namespace PBQP {
 
     // ----- MEMBERS -----
 
+    GraphMetadata Metadata;
     CostAllocator CostAlloc;
     SolverT *Solver;
 
@@ -187,13 +190,19 @@ namespace PBQP {
 
     // ----- INTERNAL METHODS -----
 
-    NodeEntry& getNode(NodeId NId) { return Nodes[NId]; }
-    const NodeEntry& getNode(NodeId NId) const { return Nodes[NId]; }
+    NodeEntry &getNode(NodeId NId) {
+      assert(NId < Nodes.size() && "Out of bound NodeId");
+      return Nodes[NId];
+    }
+    const NodeEntry &getNode(NodeId NId) const {
+      assert(NId < Nodes.size() && "Out of bound NodeId");
+      return Nodes[NId];
+    }
 
     EdgeEntry& getEdge(EdgeId EId) { return Edges[EId]; }
     const EdgeEntry& getEdge(EdgeId EId) const { return Edges[EId]; }
 
-    NodeId addConstructedNode(const NodeEntry &N) {
+    NodeId addConstructedNode(NodeEntry N) {
       NodeId NId = 0;
       if (!FreeNodeIds.empty()) {
         NId = FreeNodeIds.back();
@@ -206,7 +215,7 @@ namespace PBQP {
       return NId;
     }
 
-    EdgeId addConstructedEdge(const EdgeEntry &E) {
+    EdgeId addConstructedEdge(EdgeEntry E) {
       assert(findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() &&
              "Attempt to add duplicate edge.");
       EdgeId EId = 0;
@@ -235,6 +244,12 @@ namespace PBQP {
 
     class NodeItr {
     public:
+      typedef std::forward_iterator_tag iterator_category;
+      typedef NodeId value_type;
+      typedef int difference_type;
+      typedef NodeId* pointer;
+      typedef NodeId& reference;
+
       NodeItr(NodeId CurNId, const Graph &G)
         : CurNId(CurNId), EndNId(G.Nodes.size()), FreeNodeIds(G.FreeNodeIds) {
         this->CurNId = findNextInUse(CurNId); // Move to first in-use node id
@@ -249,7 +264,7 @@ namespace PBQP {
       NodeId findNextInUse(NodeId NId) const {
         while (NId < EndNId &&
                std::find(FreeNodeIds.begin(), FreeNodeIds.end(), NId) !=
-                 FreeNodeIds.end()) {
+               FreeNodeIds.end()) {
           ++NId;
         }
         return NId;
@@ -328,10 +343,19 @@ namespace PBQP {
       const NodeEntry &NE;
     };
 
-    /// \brief Construct an empty PBQP graph.
-    Graph() : Solver(nullptr) { }
+    /// @brief Construct an empty PBQP graph.
+    Graph() : Solver(nullptr) {}
+
+    /// @brief Construct an empty PBQP graph with the given graph metadata.
+    Graph(GraphMetadata Metadata) : Metadata(Metadata), Solver(nullptr) {}
+
+    /// @brief Get a reference to the graph metadata.
+    GraphMetadata& getMetadata() { return Metadata; }
 
-    /// \brief Lock this graph to the given solver instance in preparation
+    /// @brief Get a const-reference to the graph metadata.
+    const GraphMetadata& getMetadata() const { return Metadata; }
+
+    /// @brief Lock this graph to the given solver instance in preparation
     /// for running the solver. This method will call solver.handleAddNode for
     /// each node in the graph, and handleAddEdge for each edge, to give the
     /// solver an opportunity to set up any requried metadata.
@@ -344,13 +368,13 @@ namespace PBQP {
         Solver->handleAddEdge(EId);
     }
 
-    /// \brief Release from solver instance.
+    /// @brief Release from solver instance.
     void unsetSolver() {
       assert(Solver && "Solver not set.");
       Solver = nullptr;
     }
 
-    /// \brief Add a node with the given costs.
+    /// @brief Add a node with the given costs.
     /// @param Costs Cost vector for the new node.
     /// @return Node iterator for the added node.
     template <typename OtherVectorT>
@@ -363,9 +387,29 @@ namespace PBQP {
       return NId;
     }
 
-    /// \brief Add an edge between the given nodes with the given costs.
+    /// @brief Add a node bypassing the cost allocator.
+    /// @param Costs Cost vector ptr for the new node (must be convertible to
+    ///        VectorPtr).
+    /// @return Node iterator for the added node.
+    ///
+    ///   This method allows for fast addition of a node whose costs don't need
+    /// to be passed through the cost allocator. The most common use case for
+    /// this is when duplicating costs from an existing node (when using a
+    /// pooling allocator). These have already been uniqued, so we can avoid
+    /// re-constructing and re-uniquing them by attaching them directly to the
+    /// new node.
+    template <typename OtherVectorPtrT>
+    NodeId addNodeBypassingCostAllocator(OtherVectorPtrT Costs) {
+      NodeId NId = addConstructedNode(NodeEntry(Costs));
+      if (Solver)
+        Solver->handleAddNode(NId);
+      return NId;
+    }
+
+    /// @brief Add an edge between the given nodes with the given costs.
     /// @param N1Id First node.
     /// @param N2Id Second node.
+    /// @param Costs Cost matrix for new edge.
     /// @return Edge iterator for the added edge.
     template <typename OtherVectorT>
     EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs) {
@@ -380,7 +424,32 @@ namespace PBQP {
       return EId;
     }
 
-    /// \brief Returns true if the graph is empty.
+    /// @brief Add an edge bypassing the cost allocator.
+    /// @param N1Id First node.
+    /// @param N2Id Second node.
+    /// @param Costs Cost matrix for new edge.
+    /// @return Edge iterator for the added edge.
+    ///
+    ///   This method allows for fast addition of an edge whose costs don't need
+    /// to be passed through the cost allocator. The most common use case for
+    /// this is when duplicating costs from an existing edge (when using a
+    /// pooling allocator). These have already been uniqued, so we can avoid
+    /// re-constructing and re-uniquing them by attaching them directly to the
+    /// new edge.
+    template <typename OtherMatrixPtrT>
+    NodeId addEdgeBypassingCostAllocator(NodeId N1Id, NodeId N2Id,
+                                         OtherMatrixPtrT Costs) {
+      assert(getNodeCosts(N1Id).getLength() == Costs->getRows() &&
+             getNodeCosts(N2Id).getLength() == Costs->getCols() &&
+             "Matrix dimensions mismatch.");
+      // Get cost matrix from the problem domain.
+      EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, Costs));
+      if (Solver)
+        Solver->handleAddEdge(EId);
+      return EId;
+    }
+
+    /// @brief Returns true if the graph is empty.
     bool empty() const { return NodeIdSet(*this).empty(); }
 
     NodeIdSet nodeIds() const { return NodeIdSet(*this); }
@@ -388,15 +457,15 @@ namespace PBQP {
 
     AdjEdgeIdSet adjEdgeIds(NodeId NId) { return AdjEdgeIdSet(getNode(NId)); }
 
-    /// \brief Get the number of nodes in the graph.
+    /// @brief Get the number of nodes in the graph.
     /// @return Number of nodes in the graph.
     unsigned getNumNodes() const { return NodeIdSet(*this).size(); }
 
-    /// \brief Get the number of edges in the graph.
+    /// @brief Get the number of edges in the graph.
     /// @return Number of edges in the graph.
     unsigned getNumEdges() const { return EdgeIdSet(*this).size(); }
 
-    /// \brief Set a node's cost vector.
+    /// @brief Set a node's cost vector.
     /// @param NId Node to update.
     /// @param Costs New costs to set.
     template <typename OtherVectorT>
@@ -407,11 +476,23 @@ namespace PBQP {
       getNode(NId).Costs = AllocatedCosts;
     }
 
-    /// \brief Get a node's cost vector (const version).
+    /// @brief Get a VectorPtr to a node's cost vector. Rarely useful - use
+    ///        getNodeCosts where possible.
+    /// @param NId Node id.
+    /// @return VectorPtr to node cost vector.
+    ///
+    ///   This method is primarily useful for duplicating costs quickly by
+    /// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer
+    /// getNodeCosts when dealing with node cost values.
+    const VectorPtr& getNodeCostsPtr(NodeId NId) const {
+      return getNode(NId).Costs;
+    }
+
+    /// @brief Get a node's cost vector.
     /// @param NId Node id.
     /// @return Node cost vector.
     const Vector& getNodeCosts(NodeId NId) const {
-      return *getNode(NId).Costs;
+      return *getNodeCostsPtr(NId);
     }
 
     NodeMetadata& getNodeMetadata(NodeId NId) {
@@ -426,7 +507,7 @@ namespace PBQP {
       return getNode(NId).getAdjEdgeIds().size();
     }
 
-    /// \brief Set an edge's cost matrix.
+    /// @brief Set an edge's cost matrix.
     /// @param EId Edge id.
     /// @param Costs New cost matrix.
     template <typename OtherMatrixT>
@@ -437,34 +518,48 @@ namespace PBQP {
       getEdge(EId).Costs = AllocatedCosts;
     }
 
-    /// \brief Get an edge's cost matrix (const version).
+    /// @brief Get a MatrixPtr to a node's cost matrix. Rarely useful - use
+    ///        getEdgeCosts where possible.
+    /// @param EId Edge id.
+    /// @return MatrixPtr to edge cost matrix.
+    ///
+    ///   This method is primarily useful for duplicating costs quickly by
+    /// bypassing the cost allocator. See addNodeBypassingCostAllocator. Prefer
+    /// getEdgeCosts when dealing with edge cost values.
+    const MatrixPtr& getEdgeCostsPtr(EdgeId EId) const {
+      return getEdge(EId).Costs;
+    }
+
+    /// @brief Get an edge's cost matrix.
     /// @param EId Edge id.
     /// @return Edge cost matrix.
-    const Matrix& getEdgeCosts(EdgeId EId) const { return *getEdge(EId).Costs; }
+    const Matrix& getEdgeCosts(EdgeId EId) const {
+      return *getEdge(EId).Costs;
+    }
 
-    EdgeMetadata& getEdgeMetadata(EdgeId NId) {
-      return getEdge(NId).Metadata;
+    EdgeMetadata& getEdgeMetadata(EdgeId EId) {
+      return getEdge(EId).Metadata;
     }
 
-    const EdgeMetadata& getEdgeMetadata(EdgeId NId) const {
-      return getEdge(NId).Metadata;
+    const EdgeMetadata& getEdgeMetadata(EdgeId EId) const {
+      return getEdge(EId).Metadata;
     }
 
-    /// \brief Get the first node connected to this edge.
+    /// @brief Get the first node connected to this edge.
     /// @param EId Edge id.
     /// @return The first node connected to the given edge.
     NodeId getEdgeNode1Id(EdgeId EId) {
       return getEdge(EId).getN1Id();
     }
 
-    /// \brief Get the second node connected to this edge.
+    /// @brief Get the second node connected to this edge.
     /// @param EId Edge id.
     /// @return The second node connected to the given edge.
     NodeId getEdgeNode2Id(EdgeId EId) {
       return getEdge(EId).getN2Id();
     }
 
-    /// \brief Get the "other" node connected to this edge.
+    /// @brief Get the "other" node connected to this edge.
     /// @param EId Edge id.
     /// @param NId Node id for the "given" node.
     /// @return The iterator for the "other" node connected to this edge.
@@ -476,7 +571,7 @@ namespace PBQP {
       return E.getN1Id();
     }
 
-    /// \brief Get the edge connecting two nodes.
+    /// @brief Get the edge connecting two nodes.
     /// @param N1Id First node id.
     /// @param N2Id Second node id.
     /// @return An id for edge (N1Id, N2Id) if such an edge exists,
@@ -491,7 +586,7 @@ namespace PBQP {
       return invalidEdgeId();
     }
 
-    /// \brief Remove a node from the graph.
+    /// @brief Remove a node from the graph.
     /// @param NId Node id.
     void removeNode(NodeId NId) {
       if (Solver)
@@ -499,7 +594,7 @@ namespace PBQP {
       NodeEntry &N = getNode(NId);
       // TODO: Can this be for-each'd?
       for (AdjEdgeItr AEItr = N.adjEdgesBegin(),
-                      AEEnd = N.adjEdgesEnd();
+             AEEnd = N.adjEdgesEnd();
            AEItr != AEEnd;) {
         EdgeId EId = *AEItr;
         ++AEItr;
@@ -508,7 +603,7 @@ namespace PBQP {
       FreeNodeIds.push_back(NId);
     }
 
-    /// \brief Disconnect an edge from the given node.
+    /// @brief Disconnect an edge from the given node.
     ///
     /// Removes the given edge from the adjacency list of the given node.
     /// This operation leaves the edge in an 'asymmetric' state: It will no
@@ -541,14 +636,14 @@ namespace PBQP {
       E.disconnectFrom(*this, NId);
     }
 
-    /// \brief Convenience method to disconnect all neighbours from the given
+    /// @brief Convenience method to disconnect all neighbours from the given
     ///        node.
     void disconnectAllNeighborsFromNode(NodeId NId) {
       for (auto AEId : adjEdgeIds(NId))
         disconnectEdge(AEId, getEdgeOtherNodeId(AEId, NId));
     }
 
-    /// \brief Re-attach an edge to its nodes.
+    /// @brief Re-attach an edge to its nodes.
     ///
     /// Adds an edge that had been previously disconnected back into the
     /// adjacency set of the nodes that the edge connects.
@@ -559,7 +654,7 @@ namespace PBQP {
         Solver->handleReconnectEdge(EId, NId);
     }
 
-    /// \brief Remove an edge from the graph.
+    /// @brief Remove an edge from the graph.
     /// @param EId Edge id.
     void removeEdge(EdgeId EId) {
       if (Solver)
@@ -570,7 +665,7 @@ namespace PBQP {
       Edges[EId].invalidate();
     }
 
-    /// \brief Remove all nodes and edges from the graph.
+    /// @brief Remove all nodes and edges from the graph.
     void clear() {
       Nodes.clear();
       FreeNodeIds.clear();
@@ -578,9 +673,9 @@ namespace PBQP {
       FreeEdgeIds.clear();
     }
 
-    /// \brief Dump a graph to an output stream.
+    /// @brief Dump a graph to an output stream.
     template <typename OStream>
-    void dump(OStream &OS) {
+    void dumpToStream(OStream &OS) {
       OS << nodeIds().size() << " " << edgeIds().size() << "\n";
 
       for (auto NId : nodeIds()) {
@@ -613,7 +708,12 @@ namespace PBQP {
       }
     }
 
-    /// \brief Print a representation of this graph in DOT format.
+    /// @brief Dump this graph to dbgs().
+    void dump() {
+      dumpToStream(dbgs());
+    }
+
+    /// @brief Print a representation of this graph in DOT format.
     /// @param OS Output stream to print on.
     template <typename OStream>
     void printDot(OStream &OS) {
@@ -637,6 +737,7 @@ namespace PBQP {
     }
   };
 
-}
+}  // namespace PBQP
+}  // namespace llvm
 
 #endif // LLVM_CODEGEN_PBQP_GRAPH_HPP
diff --git a/include/llvm/CodeGen/PBQP/Math.h b/include/llvm/CodeGen/PBQP/Math.h
index 69a9d83..2792608 100644
--- a/include/llvm/CodeGen/PBQP/Math.h
+++ b/include/llvm/CodeGen/PBQP/Math.h
@@ -10,17 +10,19 @@
 #ifndef LLVM_CODEGEN_PBQP_MATH_H
 #define LLVM_CODEGEN_PBQP_MATH_H
 
+#include "llvm/ADT/Hashing.h"
 #include <algorithm>
 #include <cassert>
 #include <functional>
 
+namespace llvm {
 namespace PBQP {
 
 typedef float PBQPNum;
 
 /// \brief PBQP Vector class.
 class Vector {
-  friend class VectorComparator;
+  friend hash_code hash_value(const Vector &);
 public:
 
   /// \brief Construct a PBQP vector of the given size.
@@ -136,21 +138,12 @@ private:
   PBQPNum *Data;
 };
 
-class VectorComparator {
-public:
-  bool operator()(const Vector &A, const Vector &B) {
-    if (A.Length < B.Length)
-      return true;
-    if (B.Length < A.Length)
-      return false;
-    char *AData = reinterpret_cast<char*>(A.Data);
-    char *BData = reinterpret_cast<char*>(B.Data);
-    return std::lexicographical_compare(AData,
-                                        AData + A.Length * sizeof(PBQPNum),
-                                        BData,
-                                        BData + A.Length * sizeof(PBQPNum));
-  }
-};
+/// \brief Return a hash_value for the given vector.
+inline hash_code hash_value(const Vector &V) {
+  unsigned *VBegin = reinterpret_cast<unsigned*>(V.Data);
+  unsigned *VEnd = reinterpret_cast<unsigned*>(V.Data + V.Length);
+  return hash_combine(V.Length, hash_combine_range(VBegin, VEnd));
+}
 
 /// \brief Output a textual representation of the given vector on the given
 ///        output stream.
@@ -166,11 +159,10 @@ OStream& operator<<(OStream &OS, const Vector &V) {
   return OS;
 }
 
-
 /// \brief PBQP Matrix class
 class Matrix {
 private:
-  friend class MatrixComparator;
+  friend hash_code hash_value(const Matrix &);
 public:
 
   /// \brief Construct a PBQP Matrix with the given dimensions.
@@ -384,24 +376,12 @@ private:
   PBQPNum *Data;
 };
 
-class MatrixComparator {
-public:
-  bool operator()(const Matrix &A, const Matrix &B) {
-    if (A.Rows < B.Rows)
-      return true;
-    if (B.Rows < A.Rows)
-      return false;
-    if (A.Cols < B.Cols)
-      return true;
-    if (B.Cols < A.Cols)
-      return false;
-    char *AData = reinterpret_cast<char*>(A.Data);
-    char *BData = reinterpret_cast<char*>(B.Data);
-    return std::lexicographical_compare(
-             AData, AData + (A.Rows * A.Cols * sizeof(PBQPNum)),
-             BData, BData + (A.Rows * A.Cols * sizeof(PBQPNum)));
-  }
-};
+/// \brief Return a hash_code for the given matrix.
+inline hash_code hash_value(const Matrix &M) {
+  unsigned *MBegin = reinterpret_cast<unsigned*>(M.Data);
+  unsigned *MEnd = reinterpret_cast<unsigned*>(M.Data + (M.Rows * M.Cols));
+  return hash_combine(M.Rows, M.Cols, hash_combine_range(MBegin, MEnd));
+}
 
 /// \brief Output a textual representation of the given matrix on the given
 ///        output stream.
@@ -409,7 +389,7 @@ template <typename OStream>
 OStream& operator<<(OStream &OS, const Matrix &M) {
   assert((M.getRows() != 0) && "Zero-row matrix badness.");
   for (unsigned i = 0; i < M.getRows(); ++i)
-    OS << M.getRowAsVector(i);
+    OS << M.getRowAsVector(i) << "\n";
   return OS;
 }
 
@@ -424,6 +404,11 @@ private:
 };
 
 template <typename Metadata>
+inline hash_code hash_value(const MDVector<Metadata> &V) {
+  return hash_value(static_cast<const Vector&>(V));
+}
+
+template <typename Metadata>
 class MDMatrix : public Matrix {
 public:
   MDMatrix(const Matrix &m) : Matrix(m), md(*this) { }
@@ -433,6 +418,12 @@ private:
   Metadata md;
 };
 
+template <typename Metadata>
+inline hash_code hash_value(const MDMatrix<Metadata> &M) {
+  return hash_value(static_cast<const Matrix&>(M));
 }
 
+} // namespace PBQP
+} // namespace llvm
+
 #endif // LLVM_CODEGEN_PBQP_MATH_H
diff --git a/include/llvm/CodeGen/PBQP/ReductionRules.h b/include/llvm/CodeGen/PBQP/ReductionRules.h
index a55a060..21fde4d 100644
--- a/include/llvm/CodeGen/PBQP/ReductionRules.h
+++ b/include/llvm/CodeGen/PBQP/ReductionRules.h
@@ -11,13 +11,14 @@
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_REDUCTIONRULES_H
-#define LLVM_REDUCTIONRULES_H
+#ifndef LLVM_CODEGEN_PBQP_REDUCTIONRULES_H
+#define LLVM_CODEGEN_PBQP_REDUCTIONRULES_H
 
 #include "Graph.h"
 #include "Math.h"
 #include "Solution.h"
 
+namespace llvm {
 namespace PBQP {
 
   /// \brief Reduce a node of degree one.
@@ -186,6 +187,7 @@ namespace PBQP {
     return s;
   }
 
-}
+} // namespace PBQP
+} // namespace llvm
 
-#endif // LLVM_REDUCTIONRULES_H
+#endif
diff --git a/include/llvm/CodeGen/PBQP/RegAllocSolver.h b/include/llvm/CodeGen/PBQP/RegAllocSolver.h
deleted file mode 100644
index 977c348..0000000
--- a/include/llvm/CodeGen/PBQP/RegAllocSolver.h
+++ /dev/null
@@ -1,359 +0,0 @@
-//===-- RegAllocSolver.h - Heuristic PBQP Solver for reg alloc --*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Heuristic PBQP solver for register allocation problems. This solver uses a
-// graph reduction approach. Nodes of degree 0, 1 and 2 are eliminated with
-// optimality-preserving rules (see ReductionRules.h). When no low-degree (<3)
-// nodes are present, a heuristic derived from Brigg's graph coloring approach
-// is used.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CODEGEN_PBQP_REGALLOCSOLVER_H
-#define LLVM_CODEGEN_PBQP_REGALLOCSOLVER_H
-
-#include "CostAllocator.h"
-#include "Graph.h"
-#include "ReductionRules.h"
-#include "Solution.h"
-#include "llvm/Support/ErrorHandling.h"
-#include <limits>
-#include <vector>
-
-namespace PBQP {
-
-  namespace RegAlloc {
-
-    /// \brief Metadata to speed allocatability test.
-    ///
-    /// Keeps track of the number of infinities in each row and column.
-    class MatrixMetadata {
-    private:
-      MatrixMetadata(const MatrixMetadata&);
-      void operator=(const MatrixMetadata&);
-    public:
-      MatrixMetadata(const PBQP::Matrix& M)
-        : WorstRow(0), WorstCol(0),
-          UnsafeRows(new bool[M.getRows() - 1]()),
-          UnsafeCols(new bool[M.getCols() - 1]()) {
-
-        unsigned* ColCounts = new unsigned[M.getCols() - 1]();
-
-        for (unsigned i = 1; i < M.getRows(); ++i) {
-          unsigned RowCount = 0;
-          for (unsigned j = 1; j < M.getCols(); ++j) {
-            if (M[i][j] == std::numeric_limits<PBQP::PBQPNum>::infinity()) {
-              ++RowCount;
-              ++ColCounts[j - 1];
-              UnsafeRows[i - 1] = true;
-              UnsafeCols[j - 1] = true;
-            }
-          }
-          WorstRow = std::max(WorstRow, RowCount);
-        }
-        unsigned WorstColCountForCurRow =
-          *std::max_element(ColCounts, ColCounts + M.getCols() - 1);
-        WorstCol = std::max(WorstCol, WorstColCountForCurRow);
-        delete[] ColCounts;
-      }
-
-      ~MatrixMetadata() {
-        delete[] UnsafeRows;
-        delete[] UnsafeCols;
-      }
-
-      unsigned getWorstRow() const { return WorstRow; }
-      unsigned getWorstCol() const { return WorstCol; }
-      const bool* getUnsafeRows() const { return UnsafeRows; }
-      const bool* getUnsafeCols() const { return UnsafeCols; }
-
-    private:
-      unsigned WorstRow, WorstCol;
-      bool* UnsafeRows;
-      bool* UnsafeCols;
-    };
-
-    class NodeMetadata {
-    public:
-      typedef enum { Unprocessed,
-                     OptimallyReducible,
-                     ConservativelyAllocatable,
-                     NotProvablyAllocatable } ReductionState;
-
-      NodeMetadata() : RS(Unprocessed), DeniedOpts(0), OptUnsafeEdges(nullptr){}
-      ~NodeMetadata() { delete[] OptUnsafeEdges; }
-
-      void setup(const Vector& Costs) {
-        NumOpts = Costs.getLength() - 1;
-        OptUnsafeEdges = new unsigned[NumOpts]();
-      }
-
-      ReductionState getReductionState() const { return RS; }
-      void setReductionState(ReductionState RS) { this->RS = RS; }
-
-      void handleAddEdge(const MatrixMetadata& MD, bool Transpose) {
-        DeniedOpts += Transpose ? MD.getWorstCol() : MD.getWorstRow();
-        const bool* UnsafeOpts =
-          Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows();
-        for (unsigned i = 0; i < NumOpts; ++i)
-          OptUnsafeEdges[i] += UnsafeOpts[i];
-      }
-
-      void handleRemoveEdge(const MatrixMetadata& MD, bool Transpose) {
-        DeniedOpts -= Transpose ? MD.getWorstCol() : MD.getWorstRow();
-        const bool* UnsafeOpts =
-          Transpose ? MD.getUnsafeCols() : MD.getUnsafeRows();
-        for (unsigned i = 0; i < NumOpts; ++i)
-          OptUnsafeEdges[i] -= UnsafeOpts[i];
-      }
-
-      bool isConservativelyAllocatable() const {
-        return (DeniedOpts < NumOpts) ||
-               (std::find(OptUnsafeEdges, OptUnsafeEdges + NumOpts, 0) !=
-                  OptUnsafeEdges + NumOpts);
-      }
-
-    private:
-      ReductionState RS;
-      unsigned NumOpts;
-      unsigned DeniedOpts;
-      unsigned* OptUnsafeEdges;
-    };
-
-    class RegAllocSolverImpl {
-    private:
-      typedef PBQP::MDMatrix<MatrixMetadata> RAMatrix;
-    public:
-      typedef PBQP::Vector RawVector;
-      typedef PBQP::Matrix RawMatrix;
-      typedef PBQP::Vector Vector;
-      typedef RAMatrix     Matrix;
-      typedef PBQP::PoolCostAllocator<
-                Vector, PBQP::VectorComparator,
-                Matrix, PBQP::MatrixComparator> CostAllocator;
-
-      typedef PBQP::GraphBase::NodeId NodeId;
-      typedef PBQP::GraphBase::EdgeId EdgeId;
-
-      typedef RegAlloc::NodeMetadata NodeMetadata;
-
-      struct EdgeMetadata { };
-
-      typedef PBQP::Graph<RegAllocSolverImpl> Graph;
-
-      RegAllocSolverImpl(Graph &G) : G(G) {}
-
-      Solution solve() {
-        G.setSolver(*this);
-        Solution S;
-        setup();
-        S = backpropagate(G, reduce());
-        G.unsetSolver();
-        return S;
-      }
-
-      void handleAddNode(NodeId NId) {
-        G.getNodeMetadata(NId).setup(G.getNodeCosts(NId));
-      }
-      void handleRemoveNode(NodeId NId) {}
-      void handleSetNodeCosts(NodeId NId, const Vector& newCosts) {}
-
-      void handleAddEdge(EdgeId EId) {
-        handleReconnectEdge(EId, G.getEdgeNode1Id(EId));
-        handleReconnectEdge(EId, G.getEdgeNode2Id(EId));
-      }
-
-      void handleRemoveEdge(EdgeId EId) {
-        handleDisconnectEdge(EId, G.getEdgeNode1Id(EId));
-        handleDisconnectEdge(EId, G.getEdgeNode2Id(EId));
-      }
-
-      void handleDisconnectEdge(EdgeId EId, NodeId NId) {
-        NodeMetadata& NMd = G.getNodeMetadata(NId);
-        const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata();
-        NMd.handleRemoveEdge(MMd, NId == G.getEdgeNode2Id(EId));
-        if (G.getNodeDegree(NId) == 3) {
-          // This node is becoming optimally reducible.
-          moveToOptimallyReducibleNodes(NId);
-        } else if (NMd.getReductionState() ==
-                     NodeMetadata::NotProvablyAllocatable &&
-                   NMd.isConservativelyAllocatable()) {
-          // This node just became conservatively allocatable.
-          moveToConservativelyAllocatableNodes(NId);
-        }
-      }
-
-      void handleReconnectEdge(EdgeId EId, NodeId NId) {
-        NodeMetadata& NMd = G.getNodeMetadata(NId);
-        const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata();
-        NMd.handleAddEdge(MMd, NId == G.getEdgeNode2Id(EId));
-      }
-
-      void handleSetEdgeCosts(EdgeId EId, const Matrix& NewCosts) {
-        handleRemoveEdge(EId);
-
-        NodeId N1Id = G.getEdgeNode1Id(EId);
-        NodeId N2Id = G.getEdgeNode2Id(EId);
-        NodeMetadata& N1Md = G.getNodeMetadata(N1Id);
-        NodeMetadata& N2Md = G.getNodeMetadata(N2Id);
-        const MatrixMetadata& MMd = NewCosts.getMetadata();
-        N1Md.handleAddEdge(MMd, N1Id != G.getEdgeNode1Id(EId));
-        N2Md.handleAddEdge(MMd, N2Id != G.getEdgeNode1Id(EId));
-      }
-
-    private:
-
-      void removeFromCurrentSet(NodeId NId) {
-        switch (G.getNodeMetadata(NId).getReductionState()) {
-          case NodeMetadata::Unprocessed: break;
-          case NodeMetadata::OptimallyReducible:
-            assert(OptimallyReducibleNodes.find(NId) !=
-                     OptimallyReducibleNodes.end() &&
-                   "Node not in optimally reducible set.");
-            OptimallyReducibleNodes.erase(NId);
-            break;
-          case NodeMetadata::ConservativelyAllocatable:
-            assert(ConservativelyAllocatableNodes.find(NId) !=
-                     ConservativelyAllocatableNodes.end() &&
-                   "Node not in conservatively allocatable set.");
-            ConservativelyAllocatableNodes.erase(NId);
-            break;
-          case NodeMetadata::NotProvablyAllocatable:
-            assert(NotProvablyAllocatableNodes.find(NId) !=
-                     NotProvablyAllocatableNodes.end() &&
-                   "Node not in not-provably-allocatable set.");
-            NotProvablyAllocatableNodes.erase(NId);
-            break;
-        }
-      }
-
-      void moveToOptimallyReducibleNodes(NodeId NId) {
-        removeFromCurrentSet(NId);
-        OptimallyReducibleNodes.insert(NId);
-        G.getNodeMetadata(NId).setReductionState(
-          NodeMetadata::OptimallyReducible);
-      }
-
-      void moveToConservativelyAllocatableNodes(NodeId NId) {
-        removeFromCurrentSet(NId);
-        ConservativelyAllocatableNodes.insert(NId);
-        G.getNodeMetadata(NId).setReductionState(
-          NodeMetadata::ConservativelyAllocatable);
-      }
-
-      void moveToNotProvablyAllocatableNodes(NodeId NId) {
-        removeFromCurrentSet(NId);
-        NotProvablyAllocatableNodes.insert(NId);
-        G.getNodeMetadata(NId).setReductionState(
-          NodeMetadata::NotProvablyAllocatable);
-      }
-
-      void setup() {
-        // Set up worklists.
-        for (auto NId : G.nodeIds()) {
-          if (G.getNodeDegree(NId) < 3)
-            moveToOptimallyReducibleNodes(NId);
-          else if (G.getNodeMetadata(NId).isConservativelyAllocatable())
-            moveToConservativelyAllocatableNodes(NId);
-          else
-            moveToNotProvablyAllocatableNodes(NId);
-        }
-      }
-
-      // Compute a reduction order for the graph by iteratively applying PBQP
-      // reduction rules. Locally optimal rules are applied whenever possible (R0,
-      // R1, R2). If no locally-optimal rules apply then any conservatively
-      // allocatable node is reduced. Finally, if no conservatively allocatable
-      // node exists then the node with the lowest spill-cost:degree ratio is
-      // selected.
-      std::vector<GraphBase::NodeId> reduce() {
-        assert(!G.empty() && "Cannot reduce empty graph.");
-
-        typedef GraphBase::NodeId NodeId;
-        std::vector<NodeId> NodeStack;
-
-        // Consume worklists.
-        while (true) {
-          if (!OptimallyReducibleNodes.empty()) {
-            NodeSet::iterator NItr = OptimallyReducibleNodes.begin();
-            NodeId NId = *NItr;
-            OptimallyReducibleNodes.erase(NItr);
-            NodeStack.push_back(NId);
-            switch (G.getNodeDegree(NId)) {
-              case 0:
-                break;
-              case 1:
-                applyR1(G, NId);
-                break;
-              case 2:
-                applyR2(G, NId);
-                break;
-              default: llvm_unreachable("Not an optimally reducible node.");
-            }
-          } else if (!ConservativelyAllocatableNodes.empty()) {
-            // Conservatively allocatable nodes will never spill. For now just
-            // take the first node in the set and push it on the stack. When we
-            // start optimizing more heavily for register preferencing, it may
-            // would be better to push nodes with lower 'expected' or worst-case
-            // register costs first (since early nodes are the most
-            // constrained).
-            NodeSet::iterator NItr = ConservativelyAllocatableNodes.begin();
-            NodeId NId = *NItr;
-            ConservativelyAllocatableNodes.erase(NItr);
-            NodeStack.push_back(NId);
-            G.disconnectAllNeighborsFromNode(NId);
-
-          } else if (!NotProvablyAllocatableNodes.empty()) {
-            NodeSet::iterator NItr =
-              std::min_element(NotProvablyAllocatableNodes.begin(),
-                               NotProvablyAllocatableNodes.end(),
-                               SpillCostComparator(G));
-            NodeId NId = *NItr;
-            NotProvablyAllocatableNodes.erase(NItr);
-            NodeStack.push_back(NId);
-            G.disconnectAllNeighborsFromNode(NId);
-          } else
-            break;
-        }
-
-        return NodeStack;
-      }
-
-      class SpillCostComparator {
-      public:
-        SpillCostComparator(const Graph& G) : G(G) {}
-        bool operator()(NodeId N1Id, NodeId N2Id) {
-          PBQPNum N1SC = G.getNodeCosts(N1Id)[0] / G.getNodeDegree(N1Id);
-          PBQPNum N2SC = G.getNodeCosts(N2Id)[0] / G.getNodeDegree(N2Id);
-          return N1SC < N2SC;
-        }
-      private:
-        const Graph& G;
-      };
-
-      Graph& G;
-      typedef std::set<NodeId> NodeSet;
-      NodeSet OptimallyReducibleNodes;
-      NodeSet ConservativelyAllocatableNodes;
-      NodeSet NotProvablyAllocatableNodes;
-    };
-
-    typedef Graph<RegAllocSolverImpl> Graph;
-
-    inline Solution solve(Graph& G) {
-      if (G.empty())
-        return Solution();
-      RegAllocSolverImpl RegAllocSolver(G);
-      return RegAllocSolver.solve();
-    }
-
-  }
-}
-
-#endif // LLVM_CODEGEN_PBQP_REGALLOCSOLVER_H
diff --git a/include/llvm/CodeGen/PBQP/Solution.h b/include/llvm/CodeGen/PBQP/Solution.h
index 3556e60..a3bfaeb 100644
--- a/include/llvm/CodeGen/PBQP/Solution.h
+++ b/include/llvm/CodeGen/PBQP/Solution.h
@@ -18,6 +18,7 @@
 #include "Math.h"
 #include <map>
 
+namespace llvm {
 namespace PBQP {
 
   /// \brief Represents a solution to a PBQP problem.
@@ -87,6 +88,7 @@ namespace PBQP {
 
   };
 
-}
+} // namespace PBQP
+} // namespace llvm
 
 #endif // LLVM_CODEGEN_PBQP_SOLUTION_H