Merge "Update prebuilt Clang to r353983." into p9.0HEADp9.0-backupp9.0

5 files changed, 1376 insertions, 0 deletions

diff --git a/clang-r353983/include/llvm/CodeGen/PBQP/CostAllocator.h b/clang-r353983/include/llvm/CodeGen/PBQP/CostAllocator.h
new file mode 100644
index 00000000..0d6d8a31
--- /dev/null
+++ b/clang-r353983/include/llvm/CodeGen/PBQP/CostAllocator.h
@@ -0,0 +1,134 @@
+//===- CostAllocator.h - PBQP Cost Allocator --------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines classes conforming to the PBQP cost value manager concept.
+//
+// Cost value managers are memory managers for PBQP cost values (vectors and
+// matrices). Since PBQP graphs can grow very large (E.g. hundreds of thousands
+// of edges on the largest function in SPEC2006).
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
+#define LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
+
+#include "llvm/ADT/DenseSet.h"
+#include <algorithm>
+#include <cstdint>
+#include <memory>
+
+namespace llvm {
+namespace PBQP {
+
+template <typename ValueT> class ValuePool {
+public:
+  using PoolRef = std::shared_ptr<const ValueT>;
+
+private:
+  class PoolEntry : public std::enable_shared_from_this<PoolEntry> {
+  public:
+    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:
+    ValuePool &Pool;
+    ValueT Value;
+  };
+
+  class PoolEntryDSInfo {
+  public:
+    static inline PoolEntry *getEmptyKey() { return nullptr; }
+
+    static inline PoolEntry *getTombstoneKey() {
+      return reinterpret_cast<PoolEntry *>(static_cast<uintptr_t>(1));
+    }
+
+    template <typename ValueKeyT>
+    static unsigned getHashValue(const ValueKeyT &C) {
+      return hash_value(C);
+    }
+
+    static unsigned getHashValue(PoolEntry *P) {
+      return getHashValue(P->getValue());
+    }
+
+    static unsigned getHashValue(const PoolEntry *P) {
+      return getHashValue(P->getValue());
+    }
+
+    template <typename ValueKeyT1, typename ValueKeyT2>
+    static bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
+      return C1 == C2;
+    }
+
+    template <typename ValueKeyT>
+    static bool isEqual(const ValueKeyT &C, PoolEntry *P) {
+      if (P == getEmptyKey() || P == getTombstoneKey())
+        return false;
+      return isEqual(C, P->getValue());
+    }
+
+    static bool isEqual(PoolEntry *P1, PoolEntry *P2) {
+      if (P1 == getEmptyKey() || P1 == getTombstoneKey())
+        return P1 == P2;
+      return isEqual(P1->getValue(), P2);
+    }
+  };
+
+  using EntrySetT = DenseSet<PoolEntry *, PoolEntryDSInfo>;
+
+  EntrySetT EntrySet;
+
+  void removeEntry(PoolEntry *P) { EntrySet.erase(P); }
+
+public:
+  template <typename ValueKeyT> PoolRef getValue(ValueKeyT ValueKey) {
+    typename EntrySetT::iterator I = EntrySet.find_as(ValueKey);
+
+    if (I != EntrySet.end())
+      return PoolRef((*I)->shared_from_this(), &(*I)->getValue());
+
+    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 MatrixT> class PoolCostAllocator {
+private:
+  using VectorCostPool = ValuePool<VectorT>;
+  using MatrixCostPool = ValuePool<MatrixT>;
+
+public:
+  using Vector = VectorT;
+  using Matrix = MatrixT;
+  using VectorPtr = typename VectorCostPool::PoolRef;
+  using MatrixPtr = typename MatrixCostPool::PoolRef;
+
+  template <typename VectorKeyT> VectorPtr getVector(VectorKeyT v) {
+    return VectorPool.getValue(std::move(v));
+  }
+
+  template <typename MatrixKeyT> MatrixPtr getMatrix(MatrixKeyT m) {
+    return MatrixPool.getValue(std::move(m));
+  }
+
+private:
+  VectorCostPool VectorPool;
+  MatrixCostPool MatrixPool;
+};
+
+} // end namespace PBQP
+} // end namespace llvm
+
+#endif // LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
diff --git a/clang-r353983/include/llvm/CodeGen/PBQP/Graph.h b/clang-r353983/include/llvm/CodeGen/PBQP/Graph.h
new file mode 100644
index 00000000..c2cd6dad
--- /dev/null
+++ b/clang-r353983/include/llvm/CodeGen/PBQP/Graph.h
@@ -0,0 +1,674 @@
+//===- Graph.h - PBQP Graph -------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// PBQP Graph class.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_PBQP_GRAPH_H
+#define LLVM_CODEGEN_PBQP_GRAPH_H
+
+#include "llvm/ADT/STLExtras.h"
+#include <algorithm>
+#include <cassert>
+#include <iterator>
+#include <limits>
+#include <vector>
+
+namespace llvm {
+namespace PBQP {
+
+  class GraphBase {
+  public:
+    using NodeId = unsigned;
+    using EdgeId = unsigned;
+
+    /// Returns a value representing an invalid (non-existent) node.
+    static NodeId invalidNodeId() {
+      return std::numeric_limits<NodeId>::max();
+    }
+
+    /// Returns a value representing an invalid (non-existent) edge.
+    static EdgeId invalidEdgeId() {
+      return std::numeric_limits<EdgeId>::max();
+    }
+  };
+
+  /// PBQP Graph class.
+  /// Instances of this class describe PBQP problems.
+  ///
+  template <typename SolverT>
+  class Graph : public GraphBase {
+  private:
+    using CostAllocator = typename SolverT::CostAllocator;
+
+  public:
+    using RawVector = typename SolverT::RawVector;
+    using RawMatrix = typename SolverT::RawMatrix;
+    using Vector = typename SolverT::Vector;
+    using Matrix = typename SolverT::Matrix;
+    using VectorPtr = typename CostAllocator::VectorPtr;
+    using MatrixPtr = typename CostAllocator::MatrixPtr;
+    using NodeMetadata = typename SolverT::NodeMetadata;
+    using EdgeMetadata = typename SolverT::EdgeMetadata;
+    using GraphMetadata = typename SolverT::GraphMetadata;
+
+  private:
+    class NodeEntry {
+    public:
+      using AdjEdgeList = std::vector<EdgeId>;
+      using AdjEdgeIdx = AdjEdgeList::size_type;
+      using AdjEdgeItr = AdjEdgeList::const_iterator;
+
+      NodeEntry(VectorPtr Costs) : Costs(std::move(Costs)) {}
+
+      static AdjEdgeIdx getInvalidAdjEdgeIdx() {
+        return std::numeric_limits<AdjEdgeIdx>::max();
+      }
+
+      AdjEdgeIdx addAdjEdgeId(EdgeId EId) {
+        AdjEdgeIdx Idx = AdjEdgeIds.size();
+        AdjEdgeIds.push_back(EId);
+        return Idx;
+      }
+
+      void removeAdjEdgeId(Graph &G, NodeId ThisNId, AdjEdgeIdx Idx) {
+        // Swap-and-pop for fast removal.
+        //   1) Update the adj index of the edge currently at back().
+        //   2) Move last Edge down to Idx.
+        //   3) pop_back()
+        // If Idx == size() - 1 then the setAdjEdgeIdx and swap are
+        // redundant, but both operations are cheap.
+        G.getEdge(AdjEdgeIds.back()).setAdjEdgeIdx(ThisNId, Idx);
+        AdjEdgeIds[Idx] = AdjEdgeIds.back();
+        AdjEdgeIds.pop_back();
+      }
+
+      const AdjEdgeList& getAdjEdgeIds() const { return AdjEdgeIds; }
+
+      VectorPtr Costs;
+      NodeMetadata Metadata;
+
+    private:
+      AdjEdgeList AdjEdgeIds;
+    };
+
+    class EdgeEntry {
+    public:
+      EdgeEntry(NodeId N1Id, NodeId N2Id, MatrixPtr Costs)
+          : Costs(std::move(Costs)) {
+        NIds[0] = N1Id;
+        NIds[1] = N2Id;
+        ThisEdgeAdjIdxs[0] = NodeEntry::getInvalidAdjEdgeIdx();
+        ThisEdgeAdjIdxs[1] = NodeEntry::getInvalidAdjEdgeIdx();
+      }
+
+      void connectToN(Graph &G, EdgeId ThisEdgeId, unsigned NIdx) {
+        assert(ThisEdgeAdjIdxs[NIdx] == NodeEntry::getInvalidAdjEdgeIdx() &&
+               "Edge already connected to NIds[NIdx].");
+        NodeEntry &N = G.getNode(NIds[NIdx]);
+        ThisEdgeAdjIdxs[NIdx] = N.addAdjEdgeId(ThisEdgeId);
+      }
+
+      void connect(Graph &G, EdgeId ThisEdgeId) {
+        connectToN(G, ThisEdgeId, 0);
+        connectToN(G, ThisEdgeId, 1);
+      }
+
+      void setAdjEdgeIdx(NodeId NId, typename NodeEntry::AdjEdgeIdx NewIdx) {
+        if (NId == NIds[0])
+          ThisEdgeAdjIdxs[0] = NewIdx;
+        else {
+          assert(NId == NIds[1] && "Edge not connected to NId");
+          ThisEdgeAdjIdxs[1] = NewIdx;
+        }
+      }
+
+      void disconnectFromN(Graph &G, unsigned NIdx) {
+        assert(ThisEdgeAdjIdxs[NIdx] != NodeEntry::getInvalidAdjEdgeIdx() &&
+               "Edge not connected to NIds[NIdx].");
+        NodeEntry &N = G.getNode(NIds[NIdx]);
+        N.removeAdjEdgeId(G, NIds[NIdx], ThisEdgeAdjIdxs[NIdx]);
+        ThisEdgeAdjIdxs[NIdx] = NodeEntry::getInvalidAdjEdgeIdx();
+      }
+
+      void disconnectFrom(Graph &G, NodeId NId) {
+        if (NId == NIds[0])
+          disconnectFromN(G, 0);
+        else {
+          assert(NId == NIds[1] && "Edge does not connect NId");
+          disconnectFromN(G, 1);
+        }
+      }
+
+      NodeId getN1Id() const { return NIds[0]; }
+      NodeId getN2Id() const { return NIds[1]; }
+
+      MatrixPtr Costs;
+      EdgeMetadata Metadata;
+
+    private:
+      NodeId NIds[2];
+      typename NodeEntry::AdjEdgeIdx ThisEdgeAdjIdxs[2];
+    };
+
+    // ----- MEMBERS -----
+
+    GraphMetadata Metadata;
+    CostAllocator CostAlloc;
+    SolverT *Solver = nullptr;
+
+    using NodeVector = std::vector<NodeEntry>;
+    using FreeNodeVector = std::vector<NodeId>;
+    NodeVector Nodes;
+    FreeNodeVector FreeNodeIds;
+
+    using EdgeVector = std::vector<EdgeEntry>;
+    using FreeEdgeVector = std::vector<EdgeId>;
+    EdgeVector Edges;
+    FreeEdgeVector FreeEdgeIds;
+
+    Graph(const Graph &Other) {}
+
+    // ----- INTERNAL METHODS -----
+
+    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(NodeEntry N) {
+      NodeId NId = 0;
+      if (!FreeNodeIds.empty()) {
+        NId = FreeNodeIds.back();
+        FreeNodeIds.pop_back();
+        Nodes[NId] = std::move(N);
+      } else {
+        NId = Nodes.size();
+        Nodes.push_back(std::move(N));
+      }
+      return NId;
+    }
+
+    EdgeId addConstructedEdge(EdgeEntry E) {
+      assert(findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() &&
+             "Attempt to add duplicate edge.");
+      EdgeId EId = 0;
+      if (!FreeEdgeIds.empty()) {
+        EId = FreeEdgeIds.back();
+        FreeEdgeIds.pop_back();
+        Edges[EId] = std::move(E);
+      } else {
+        EId = Edges.size();
+        Edges.push_back(std::move(E));
+      }
+
+      EdgeEntry &NE = getEdge(EId);
+
+      // Add the edge to the adjacency sets of its nodes.
+      NE.connect(*this, EId);
+      return EId;
+    }
+
+    void operator=(const Graph &Other) {}
+
+  public:
+    using AdjEdgeItr = typename NodeEntry::AdjEdgeItr;
+
+    class NodeItr {
+    public:
+      using iterator_category = std::forward_iterator_tag;
+      using value_type = NodeId;
+      using difference_type = int;
+      using pointer = NodeId *;
+      using reference = NodeId &;
+
+      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
+      }
+
+      bool operator==(const NodeItr &O) const { return CurNId == O.CurNId; }
+      bool operator!=(const NodeItr &O) const { return !(*this == O); }
+      NodeItr& operator++() { CurNId = findNextInUse(++CurNId); return *this; }
+      NodeId operator*() const { return CurNId; }
+
+    private:
+      NodeId findNextInUse(NodeId NId) const {
+        while (NId < EndNId && is_contained(FreeNodeIds, NId)) {
+          ++NId;
+        }
+        return NId;
+      }
+
+      NodeId CurNId, EndNId;
+      const FreeNodeVector &FreeNodeIds;
+    };
+
+    class EdgeItr {
+    public:
+      EdgeItr(EdgeId CurEId, const Graph &G)
+        : CurEId(CurEId), EndEId(G.Edges.size()), FreeEdgeIds(G.FreeEdgeIds) {
+        this->CurEId = findNextInUse(CurEId); // Move to first in-use edge id
+      }
+
+      bool operator==(const EdgeItr &O) const { return CurEId == O.CurEId; }
+      bool operator!=(const EdgeItr &O) const { return !(*this == O); }
+      EdgeItr& operator++() { CurEId = findNextInUse(++CurEId); return *this; }
+      EdgeId operator*() const { return CurEId; }
+
+    private:
+      EdgeId findNextInUse(EdgeId EId) const {
+        while (EId < EndEId && is_contained(FreeEdgeIds, EId)) {
+          ++EId;
+        }
+        return EId;
+      }
+
+      EdgeId CurEId, EndEId;
+      const FreeEdgeVector &FreeEdgeIds;
+    };
+
+    class NodeIdSet {
+    public:
+      NodeIdSet(const Graph &G) : G(G) {}
+
+      NodeItr begin() const { return NodeItr(0, G); }
+      NodeItr end() const { return NodeItr(G.Nodes.size(), G); }
+
+      bool empty() const { return G.Nodes.empty(); }
+
+      typename NodeVector::size_type size() const {
+        return G.Nodes.size() - G.FreeNodeIds.size();
+      }
+
+    private:
+      const Graph& G;
+    };
+
+    class EdgeIdSet {
+    public:
+      EdgeIdSet(const Graph &G) : G(G) {}
+
+      EdgeItr begin() const { return EdgeItr(0, G); }
+      EdgeItr end() const { return EdgeItr(G.Edges.size(), G); }
+
+      bool empty() const { return G.Edges.empty(); }
+
+      typename NodeVector::size_type size() const {
+        return G.Edges.size() - G.FreeEdgeIds.size();
+      }
+
+    private:
+      const Graph& G;
+    };
+
+    class AdjEdgeIdSet {
+    public:
+      AdjEdgeIdSet(const NodeEntry &NE) : NE(NE) {}
+
+      typename NodeEntry::AdjEdgeItr begin() const {
+        return NE.getAdjEdgeIds().begin();
+      }
+
+      typename NodeEntry::AdjEdgeItr end() const {
+        return NE.getAdjEdgeIds().end();
+      }
+
+      bool empty() const { return NE.getAdjEdgeIds().empty(); }
+
+      typename NodeEntry::AdjEdgeList::size_type size() const {
+        return NE.getAdjEdgeIds().size();
+      }
+
+    private:
+      const NodeEntry &NE;
+    };
+
+    /// Construct an empty PBQP graph.
+    Graph() = default;
+
+    /// Construct an empty PBQP graph with the given graph metadata.
+    Graph(GraphMetadata Metadata) : Metadata(std::move(Metadata)) {}
+
+    /// Get a reference to the graph metadata.
+    GraphMetadata& getMetadata() { return Metadata; }
+
+    /// Get a const-reference to the graph metadata.
+    const GraphMetadata& getMetadata() const { return Metadata; }
+
+    /// 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.
+    void setSolver(SolverT &S) {
+      assert(!Solver && "Solver already set. Call unsetSolver().");
+      Solver = &S;
+      for (auto NId : nodeIds())
+        Solver->handleAddNode(NId);
+      for (auto EId : edgeIds())
+        Solver->handleAddEdge(EId);
+    }
+
+    /// Release from solver instance.
+    void unsetSolver() {
+      assert(Solver && "Solver not set.");
+      Solver = nullptr;
+    }
+
+    /// 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>
+    NodeId addNode(OtherVectorT Costs) {
+      // Get cost vector from the problem domain
+      VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
+      NodeId NId = addConstructedNode(NodeEntry(AllocatedCosts));
+      if (Solver)
+        Solver->handleAddNode(NId);
+      return NId;
+    }
+
+    /// 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;
+    }
+
+    /// 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) {
+      assert(getNodeCosts(N1Id).getLength() == Costs.getRows() &&
+             getNodeCosts(N2Id).getLength() == Costs.getCols() &&
+             "Matrix dimensions mismatch.");
+      // Get cost matrix from the problem domain.
+      MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
+      EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, AllocatedCosts));
+      if (Solver)
+        Solver->handleAddEdge(EId);
+      return EId;
+    }
+
+    /// 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;
+    }
+
+    /// Returns true if the graph is empty.
+    bool empty() const { return NodeIdSet(*this).empty(); }
+
+    NodeIdSet nodeIds() const { return NodeIdSet(*this); }
+    EdgeIdSet edgeIds() const { return EdgeIdSet(*this); }
+
+    AdjEdgeIdSet adjEdgeIds(NodeId NId) { return AdjEdgeIdSet(getNode(NId)); }
+
+    /// Get the number of nodes in the graph.
+    /// @return Number of nodes in the graph.
+    unsigned getNumNodes() const { return NodeIdSet(*this).size(); }
+
+    /// Get the number of edges in the graph.
+    /// @return Number of edges in the graph.
+    unsigned getNumEdges() const { return EdgeIdSet(*this).size(); }
+
+    /// Set a node's cost vector.
+    /// @param NId Node to update.
+    /// @param Costs New costs to set.
+    template <typename OtherVectorT>
+    void setNodeCosts(NodeId NId, OtherVectorT Costs) {
+      VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs));
+      if (Solver)
+        Solver->handleSetNodeCosts(NId, *AllocatedCosts);
+      getNode(NId).Costs = AllocatedCosts;
+    }
+
+    /// 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;
+    }
+
+    /// Get a node's cost vector.
+    /// @param NId Node id.
+    /// @return Node cost vector.
+    const Vector& getNodeCosts(NodeId NId) const {
+      return *getNodeCostsPtr(NId);
+    }
+
+    NodeMetadata& getNodeMetadata(NodeId NId) {
+      return getNode(NId).Metadata;
+    }
+
+    const NodeMetadata& getNodeMetadata(NodeId NId) const {
+      return getNode(NId).Metadata;
+    }
+
+    typename NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const {
+      return getNode(NId).getAdjEdgeIds().size();
+    }
+
+    /// Update an edge's cost matrix.
+    /// @param EId Edge id.
+    /// @param Costs New cost matrix.
+    template <typename OtherMatrixT>
+    void updateEdgeCosts(EdgeId EId, OtherMatrixT Costs) {
+      MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs));
+      if (Solver)
+        Solver->handleUpdateCosts(EId, *AllocatedCosts);
+      getEdge(EId).Costs = AllocatedCosts;
+    }
+
+    /// 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;
+    }
+
+    /// Get an edge's cost matrix.
+    /// @param EId Edge id.
+    /// @return Edge cost matrix.
+    const Matrix& getEdgeCosts(EdgeId EId) const {
+      return *getEdge(EId).Costs;
+    }
+
+    EdgeMetadata& getEdgeMetadata(EdgeId EId) {
+      return getEdge(EId).Metadata;
+    }
+
+    const EdgeMetadata& getEdgeMetadata(EdgeId EId) const {
+      return getEdge(EId).Metadata;
+    }
+
+    /// 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) const {
+      return getEdge(EId).getN1Id();
+    }
+
+    /// 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) const {
+      return getEdge(EId).getN2Id();
+    }
+
+    /// 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.
+    NodeId getEdgeOtherNodeId(EdgeId EId, NodeId NId) {
+      EdgeEntry &E = getEdge(EId);
+      if (E.getN1Id() == NId) {
+        return E.getN2Id();
+      } // else
+      return E.getN1Id();
+    }
+
+    /// 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,
+    ///         otherwise returns an invalid edge id.
+    EdgeId findEdge(NodeId N1Id, NodeId N2Id) {
+      for (auto AEId : adjEdgeIds(N1Id)) {
+        if ((getEdgeNode1Id(AEId) == N2Id) ||
+            (getEdgeNode2Id(AEId) == N2Id)) {
+          return AEId;
+        }
+      }
+      return invalidEdgeId();
+    }
+
+    /// Remove a node from the graph.
+    /// @param NId Node id.
+    void removeNode(NodeId NId) {
+      if (Solver)
+        Solver->handleRemoveNode(NId);
+      NodeEntry &N = getNode(NId);
+      // TODO: Can this be for-each'd?
+      for (AdjEdgeItr AEItr = N.adjEdgesBegin(),
+             AEEnd = N.adjEdgesEnd();
+           AEItr != AEEnd;) {
+        EdgeId EId = *AEItr;
+        ++AEItr;
+        removeEdge(EId);
+      }
+      FreeNodeIds.push_back(NId);
+    }
+
+    /// 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
+    /// longer appear in an iteration over the given node's (NId's) edges, but
+    /// will appear in an iteration over the 'other', unnamed node's edges.
+    ///
+    /// This does not correspond to any normal graph operation, but exists to
+    /// support efficient PBQP graph-reduction based solvers. It is used to
+    /// 'effectively' remove the unnamed node from the graph while the solver
+    /// is performing the reduction. The solver will later call reconnectNode
+    /// to restore the edge in the named node's adjacency list.
+    ///
+    /// Since the degree of a node is the number of connected edges,
+    /// disconnecting an edge from a node 'u' will cause the degree of 'u' to
+    /// drop by 1.
+    ///
+    /// A disconnected edge WILL still appear in an iteration over the graph
+    /// edges.
+    ///
+    /// A disconnected edge should not be removed from the graph, it should be
+    /// reconnected first.
+    ///
+    /// A disconnected edge can be reconnected by calling the reconnectEdge
+    /// method.
+    void disconnectEdge(EdgeId EId, NodeId NId) {
+      if (Solver)
+        Solver->handleDisconnectEdge(EId, NId);
+
+      EdgeEntry &E = getEdge(EId);
+      E.disconnectFrom(*this, NId);
+    }
+
+    /// Convenience method to disconnect all neighbours from the given
+    ///        node.
+    void disconnectAllNeighborsFromNode(NodeId NId) {
+      for (auto AEId : adjEdgeIds(NId))
+        disconnectEdge(AEId, getEdgeOtherNodeId(AEId, NId));
+    }
+
+    /// 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.
+    void reconnectEdge(EdgeId EId, NodeId NId) {
+      EdgeEntry &E = getEdge(EId);
+      E.connectTo(*this, EId, NId);
+      if (Solver)
+        Solver->handleReconnectEdge(EId, NId);
+    }
+
+    /// Remove an edge from the graph.
+    /// @param EId Edge id.
+    void removeEdge(EdgeId EId) {
+      if (Solver)
+        Solver->handleRemoveEdge(EId);
+      EdgeEntry &E = getEdge(EId);
+      E.disconnect();
+      FreeEdgeIds.push_back(EId);
+      Edges[EId].invalidate();
+    }
+
+    /// Remove all nodes and edges from the graph.
+    void clear() {
+      Nodes.clear();
+      FreeNodeIds.clear();
+      Edges.clear();
+      FreeEdgeIds.clear();
+    }
+  };
+
+} // end namespace PBQP
+} // end namespace llvm
+
+#endif // LLVM_CODEGEN_PBQP_GRAPH_HPP
diff --git a/clang-r353983/include/llvm/CodeGen/PBQP/Math.h b/clang-r353983/include/llvm/CodeGen/PBQP/Math.h
new file mode 100644
index 00000000..8b014ccb
--- /dev/null
+++ b/clang-r353983/include/llvm/CodeGen/PBQP/Math.h
@@ -0,0 +1,291 @@
+//===- Math.h - PBQP Vector and Matrix classes ------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_PBQP_MATH_H
+#define LLVM_CODEGEN_PBQP_MATH_H
+
+#include "llvm/ADT/Hashing.h"
+#include "llvm/ADT/STLExtras.h"
+#include <algorithm>
+#include <cassert>
+#include <functional>
+#include <memory>
+
+namespace llvm {
+namespace PBQP {
+
+using PBQPNum = float;
+
+/// PBQP Vector class.
+class Vector {
+  friend hash_code hash_value(const Vector &);
+
+public:
+  /// Construct a PBQP vector of the given size.
+  explicit Vector(unsigned Length)
+    : Length(Length), Data(llvm::make_unique<PBQPNum []>(Length)) {}
+
+  /// Construct a PBQP vector with initializer.
+  Vector(unsigned Length, PBQPNum InitVal)
+    : Length(Length), Data(llvm::make_unique<PBQPNum []>(Length)) {
+    std::fill(Data.get(), Data.get() + Length, InitVal);
+  }
+
+  /// Copy construct a PBQP vector.
+  Vector(const Vector &V)
+    : Length(V.Length), Data(llvm::make_unique<PBQPNum []>(Length)) {
+    std::copy(V.Data.get(), V.Data.get() + Length, Data.get());
+  }
+
+  /// Move construct a PBQP vector.
+  Vector(Vector &&V)
+    : Length(V.Length), Data(std::move(V.Data)) {
+    V.Length = 0;
+  }
+
+  /// Comparison operator.
+  bool operator==(const Vector &V) const {
+    assert(Length != 0 && Data && "Invalid vector");
+    if (Length != V.Length)
+      return false;
+    return std::equal(Data.get(), Data.get() + Length, V.Data.get());
+  }
+
+  /// Return the length of the vector
+  unsigned getLength() const {
+    assert(Length != 0 && Data && "Invalid vector");
+    return Length;
+  }
+
+  /// Element access.
+  PBQPNum& operator[](unsigned Index) {
+    assert(Length != 0 && Data && "Invalid vector");
+    assert(Index < Length && "Vector element access out of bounds.");
+    return Data[Index];
+  }
+
+  /// Const element access.
+  const PBQPNum& operator[](unsigned Index) const {
+    assert(Length != 0 && Data && "Invalid vector");
+    assert(Index < Length && "Vector element access out of bounds.");
+    return Data[Index];
+  }
+
+  /// Add another vector to this one.
+  Vector& operator+=(const Vector &V) {
+    assert(Length != 0 && Data && "Invalid vector");
+    assert(Length == V.Length && "Vector length mismatch.");
+    std::transform(Data.get(), Data.get() + Length, V.Data.get(), Data.get(),
+                   std::plus<PBQPNum>());
+    return *this;
+  }
+
+  /// Returns the index of the minimum value in this vector
+  unsigned minIndex() const {
+    assert(Length != 0 && Data && "Invalid vector");
+    return std::min_element(Data.get(), Data.get() + Length) - Data.get();
+  }
+
+private:
+  unsigned Length;
+  std::unique_ptr<PBQPNum []> Data;
+};
+
+/// Return a hash_value for the given vector.
+inline hash_code hash_value(const Vector &V) {
+  unsigned *VBegin = reinterpret_cast<unsigned*>(V.Data.get());
+  unsigned *VEnd = reinterpret_cast<unsigned*>(V.Data.get() + V.Length);
+  return hash_combine(V.Length, hash_combine_range(VBegin, VEnd));
+}
+
+/// Output a textual representation of the given vector on the given
+///        output stream.
+template <typename OStream>
+OStream& operator<<(OStream &OS, const Vector &V) {
+  assert((V.getLength() != 0) && "Zero-length vector badness.");
+
+  OS << "[ " << V[0];
+  for (unsigned i = 1; i < V.getLength(); ++i)
+    OS << ", " << V[i];
+  OS << " ]";
+
+  return OS;
+}
+
+/// PBQP Matrix class
+class Matrix {
+private:
+  friend hash_code hash_value(const Matrix &);
+
+public:
+  /// Construct a PBQP Matrix with the given dimensions.
+  Matrix(unsigned Rows, unsigned Cols) :
+    Rows(Rows), Cols(Cols), Data(llvm::make_unique<PBQPNum []>(Rows * Cols)) {
+  }
+
+  /// Construct a PBQP Matrix with the given dimensions and initial
+  /// value.
+  Matrix(unsigned Rows, unsigned Cols, PBQPNum InitVal)
+    : Rows(Rows), Cols(Cols),
+      Data(llvm::make_unique<PBQPNum []>(Rows * Cols)) {
+    std::fill(Data.get(), Data.get() + (Rows * Cols), InitVal);
+  }
+
+  /// Copy construct a PBQP matrix.
+  Matrix(const Matrix &M)
+    : Rows(M.Rows), Cols(M.Cols),
+      Data(llvm::make_unique<PBQPNum []>(Rows * Cols)) {
+    std::copy(M.Data.get(), M.Data.get() + (Rows * Cols), Data.get());
+  }
+
+  /// Move construct a PBQP matrix.
+  Matrix(Matrix &&M)
+    : Rows(M.Rows), Cols(M.Cols), Data(std::move(M.Data)) {
+    M.Rows = M.Cols = 0;
+  }
+
+  /// Comparison operator.
+  bool operator==(const Matrix &M) const {
+    assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
+    if (Rows != M.Rows || Cols != M.Cols)
+      return false;
+    return std::equal(Data.get(), Data.get() + (Rows * Cols), M.Data.get());
+  }
+
+  /// Return the number of rows in this matrix.
+  unsigned getRows() const {
+    assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
+    return Rows;
+  }
+
+  /// Return the number of cols in this matrix.
+  unsigned getCols() const {
+    assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
+    return Cols;
+  }
+
+  /// Matrix element access.
+  PBQPNum* operator[](unsigned R) {
+    assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
+    assert(R < Rows && "Row out of bounds.");
+    return Data.get() + (R * Cols);
+  }
+
+  /// Matrix element access.
+  const PBQPNum* operator[](unsigned R) const {
+    assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
+    assert(R < Rows && "Row out of bounds.");
+    return Data.get() + (R * Cols);
+  }
+
+  /// Returns the given row as a vector.
+  Vector getRowAsVector(unsigned R) const {
+    assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
+    Vector V(Cols);
+    for (unsigned C = 0; C < Cols; ++C)
+      V[C] = (*this)[R][C];
+    return V;
+  }
+
+  /// Returns the given column as a vector.
+  Vector getColAsVector(unsigned C) const {
+    assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
+    Vector V(Rows);
+    for (unsigned R = 0; R < Rows; ++R)
+      V[R] = (*this)[R][C];
+    return V;
+  }
+
+  /// Matrix transpose.
+  Matrix transpose() const {
+    assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
+    Matrix M(Cols, Rows);
+    for (unsigned r = 0; r < Rows; ++r)
+      for (unsigned c = 0; c < Cols; ++c)
+        M[c][r] = (*this)[r][c];
+    return M;
+  }
+
+  /// Add the given matrix to this one.
+  Matrix& operator+=(const Matrix &M) {
+    assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
+    assert(Rows == M.Rows && Cols == M.Cols &&
+           "Matrix dimensions mismatch.");
+    std::transform(Data.get(), Data.get() + (Rows * Cols), M.Data.get(),
+                   Data.get(), std::plus<PBQPNum>());
+    return *this;
+  }
+
+  Matrix operator+(const Matrix &M) {
+    assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
+    Matrix Tmp(*this);
+    Tmp += M;
+    return Tmp;
+  }
+
+private:
+  unsigned Rows, Cols;
+  std::unique_ptr<PBQPNum []> Data;
+};
+
+/// Return a hash_code for the given matrix.
+inline hash_code hash_value(const Matrix &M) {
+  unsigned *MBegin = reinterpret_cast<unsigned*>(M.Data.get());
+  unsigned *MEnd =
+    reinterpret_cast<unsigned*>(M.Data.get() + (M.Rows * M.Cols));
+  return hash_combine(M.Rows, M.Cols, hash_combine_range(MBegin, MEnd));
+}
+
+/// Output a textual representation of the given matrix on the given
+///        output stream.
+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) << "\n";
+  return OS;
+}
+
+template <typename Metadata>
+class MDVector : public Vector {
+public:
+  MDVector(const Vector &v) : Vector(v), md(*this) {}
+  MDVector(Vector &&v) : Vector(std::move(v)), md(*this) { }
+
+  const Metadata& getMetadata() const { return md; }
+
+private:
+  Metadata md;
+};
+
+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) {}
+  MDMatrix(Matrix &&m) : Matrix(std::move(m)), md(*this) { }
+
+  const Metadata& getMetadata() const { return md; }
+
+private:
+  Metadata md;
+};
+
+template <typename Metadata>
+inline hash_code hash_value(const MDMatrix<Metadata> &M) {
+  return hash_value(static_cast<const Matrix&>(M));
+}
+
+} // end namespace PBQP
+} // end namespace llvm
+
+#endif // LLVM_CODEGEN_PBQP_MATH_H
diff --git a/clang-r353983/include/llvm/CodeGen/PBQP/ReductionRules.h b/clang-r353983/include/llvm/CodeGen/PBQP/ReductionRules.h
new file mode 100644
index 00000000..51822d08
--- /dev/null
+++ b/clang-r353983/include/llvm/CodeGen/PBQP/ReductionRules.h
@@ -0,0 +1,222 @@
+//===- ReductionRules.h - Reduction Rules -----------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Reduction Rules.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_PBQP_REDUCTIONRULES_H
+#define LLVM_CODEGEN_PBQP_REDUCTIONRULES_H
+
+#include "Graph.h"
+#include "Math.h"
+#include "Solution.h"
+#include <cassert>
+#include <limits>
+
+namespace llvm {
+namespace PBQP {
+
+  /// Reduce a node of degree one.
+  ///
+  /// Propagate costs from the given node, which must be of degree one, to its
+  /// neighbor. Notify the problem domain.
+  template <typename GraphT>
+  void applyR1(GraphT &G, typename GraphT::NodeId NId) {
+    using NodeId = typename GraphT::NodeId;
+    using EdgeId = typename GraphT::EdgeId;
+    using Vector = typename GraphT::Vector;
+    using Matrix = typename GraphT::Matrix;
+    using RawVector = typename GraphT::RawVector;
+
+    assert(G.getNodeDegree(NId) == 1 &&
+           "R1 applied to node with degree != 1.");
+
+    EdgeId EId = *G.adjEdgeIds(NId).begin();
+    NodeId MId = G.getEdgeOtherNodeId(EId, NId);
+
+    const Matrix &ECosts = G.getEdgeCosts(EId);
+    const Vector &XCosts = G.getNodeCosts(NId);
+    RawVector YCosts = G.getNodeCosts(MId);
+
+    // Duplicate a little to avoid transposing matrices.
+    if (NId == G.getEdgeNode1Id(EId)) {
+      for (unsigned j = 0; j < YCosts.getLength(); ++j) {
+        PBQPNum Min = ECosts[0][j] + XCosts[0];
+        for (unsigned i = 1; i < XCosts.getLength(); ++i) {
+          PBQPNum C = ECosts[i][j] + XCosts[i];
+          if (C < Min)
+            Min = C;
+        }
+        YCosts[j] += Min;
+      }
+    } else {
+      for (unsigned i = 0; i < YCosts.getLength(); ++i) {
+        PBQPNum Min = ECosts[i][0] + XCosts[0];
+        for (unsigned j = 1; j < XCosts.getLength(); ++j) {
+          PBQPNum C = ECosts[i][j] + XCosts[j];
+          if (C < Min)
+            Min = C;
+        }
+        YCosts[i] += Min;
+      }
+    }
+    G.setNodeCosts(MId, YCosts);
+    G.disconnectEdge(EId, MId);
+  }
+
+  template <typename GraphT>
+  void applyR2(GraphT &G, typename GraphT::NodeId NId) {
+    using NodeId = typename GraphT::NodeId;
+    using EdgeId = typename GraphT::EdgeId;
+    using Vector = typename GraphT::Vector;
+    using Matrix = typename GraphT::Matrix;
+    using RawMatrix = typename GraphT::RawMatrix;
+
+    assert(G.getNodeDegree(NId) == 2 &&
+           "R2 applied to node with degree != 2.");
+
+    const Vector &XCosts = G.getNodeCosts(NId);
+
+    typename GraphT::AdjEdgeItr AEItr = G.adjEdgeIds(NId).begin();
+    EdgeId YXEId = *AEItr,
+           ZXEId = *(++AEItr);
+
+    NodeId YNId = G.getEdgeOtherNodeId(YXEId, NId),
+           ZNId = G.getEdgeOtherNodeId(ZXEId, NId);
+
+    bool FlipEdge1 = (G.getEdgeNode1Id(YXEId) == NId),
+         FlipEdge2 = (G.getEdgeNode1Id(ZXEId) == NId);
+
+    const Matrix *YXECosts = FlipEdge1 ?
+      new Matrix(G.getEdgeCosts(YXEId).transpose()) :
+      &G.getEdgeCosts(YXEId);
+
+    const Matrix *ZXECosts = FlipEdge2 ?
+      new Matrix(G.getEdgeCosts(ZXEId).transpose()) :
+      &G.getEdgeCosts(ZXEId);
+
+    unsigned XLen = XCosts.getLength(),
+      YLen = YXECosts->getRows(),
+      ZLen = ZXECosts->getRows();
+
+    RawMatrix Delta(YLen, ZLen);
+
+    for (unsigned i = 0; i < YLen; ++i) {
+      for (unsigned j = 0; j < ZLen; ++j) {
+        PBQPNum Min = (*YXECosts)[i][0] + (*ZXECosts)[j][0] + XCosts[0];
+        for (unsigned k = 1; k < XLen; ++k) {
+          PBQPNum C = (*YXECosts)[i][k] + (*ZXECosts)[j][k] + XCosts[k];
+          if (C < Min) {
+            Min = C;
+          }
+        }
+        Delta[i][j] = Min;
+      }
+    }
+
+    if (FlipEdge1)
+      delete YXECosts;
+
+    if (FlipEdge2)
+      delete ZXECosts;
+
+    EdgeId YZEId = G.findEdge(YNId, ZNId);
+
+    if (YZEId == G.invalidEdgeId()) {
+      YZEId = G.addEdge(YNId, ZNId, Delta);
+    } else {
+      const Matrix &YZECosts = G.getEdgeCosts(YZEId);
+      if (YNId == G.getEdgeNode1Id(YZEId)) {
+        G.updateEdgeCosts(YZEId, Delta + YZECosts);
+      } else {
+        G.updateEdgeCosts(YZEId, Delta.transpose() + YZECosts);
+      }
+    }
+
+    G.disconnectEdge(YXEId, YNId);
+    G.disconnectEdge(ZXEId, ZNId);
+
+    // TODO: Try to normalize newly added/modified edge.
+  }
+
+#ifndef NDEBUG
+  // Does this Cost vector have any register options ?
+  template <typename VectorT>
+  bool hasRegisterOptions(const VectorT &V) {
+    unsigned VL = V.getLength();
+
+    // An empty or spill only cost vector does not provide any register option.
+    if (VL <= 1)
+      return false;
+
+    // If there are registers in the cost vector, but all of them have infinite
+    // costs, then ... there is no available register.
+    for (unsigned i = 1; i < VL; ++i)
+      if (V[i] != std::numeric_limits<PBQP::PBQPNum>::infinity())
+        return true;
+
+    return false;
+  }
+#endif
+
+  // Find a solution to a fully reduced graph by backpropagation.
+  //
+  // Given a graph and a reduction order, pop each node from the reduction
+  // order and greedily compute a minimum solution based on the node costs, and
+  // the dependent costs due to previously solved nodes.
+  //
+  // Note - This does not return the graph to its original (pre-reduction)
+  //        state: the existing solvers destructively alter the node and edge
+  //        costs. Given that, the backpropagate function doesn't attempt to
+  //        replace the edges either, but leaves the graph in its reduced
+  //        state.
+  template <typename GraphT, typename StackT>
+  Solution backpropagate(GraphT& G, StackT stack) {
+    using NodeId = GraphBase::NodeId;
+    using Matrix = typename GraphT::Matrix;
+    using RawVector = typename GraphT::RawVector;
+
+    Solution s;
+
+    while (!stack.empty()) {
+      NodeId NId = stack.back();
+      stack.pop_back();
+
+      RawVector v = G.getNodeCosts(NId);
+
+#ifndef NDEBUG
+      // Although a conservatively allocatable node can be allocated to a register,
+      // spilling it may provide a lower cost solution. Assert here that spilling
+      // is done by choice, not because there were no register available.
+      if (G.getNodeMetadata(NId).wasConservativelyAllocatable())
+        assert(hasRegisterOptions(v) && "A conservatively allocatable node "
+                                        "must have available register options");
+#endif
+
+      for (auto EId : G.adjEdgeIds(NId)) {
+        const Matrix& edgeCosts = G.getEdgeCosts(EId);
+        if (NId == G.getEdgeNode1Id(EId)) {
+          NodeId mId = G.getEdgeNode2Id(EId);
+          v += edgeCosts.getColAsVector(s.getSelection(mId));
+        } else {
+          NodeId mId = G.getEdgeNode1Id(EId);
+          v += edgeCosts.getRowAsVector(s.getSelection(mId));
+        }
+      }
+
+      s.setSelection(NId, v.minIndex());
+    }
+
+    return s;
+  }
+
+} // end namespace PBQP
+} // end namespace llvm
+
+#endif // LLVM_CODEGEN_PBQP_REDUCTIONRULES_H
diff --git a/clang-r353983/include/llvm/CodeGen/PBQP/Solution.h b/clang-r353983/include/llvm/CodeGen/PBQP/Solution.h
new file mode 100644
index 00000000..d5b1474f
--- /dev/null
+++ b/clang-r353983/include/llvm/CodeGen/PBQP/Solution.h
@@ -0,0 +1,55 @@
+//===- Solution.h - PBQP Solution -------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// PBQP Solution class.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_PBQP_SOLUTION_H
+#define LLVM_CODEGEN_PBQP_SOLUTION_H
+
+#include "llvm/CodeGen/PBQP/Graph.h"
+#include <cassert>
+#include <map>
+
+namespace llvm {
+namespace PBQP {
+
+  /// Represents a solution to a PBQP problem.
+  ///
+  /// To get the selection for each node in the problem use the getSelection method.
+  class Solution {
+  private:
+    using SelectionsMap = std::map<GraphBase::NodeId, unsigned>;
+    SelectionsMap selections;
+
+  public:
+    /// Initialise an empty solution.
+    Solution() = default;
+
+    /// Set the selection for a given node.
+    /// @param nodeId Node id.
+    /// @param selection Selection for nodeId.
+    void setSelection(GraphBase::NodeId nodeId, unsigned selection) {
+      selections[nodeId] = selection;
+    }
+
+    /// Get a node's selection.
+    /// @param nodeId Node id.
+    /// @return The selection for nodeId;
+    unsigned getSelection(GraphBase::NodeId nodeId) const {
+      SelectionsMap::const_iterator sItr = selections.find(nodeId);
+      assert(sItr != selections.end() && "No selection for node.");
+      return sItr->second;
+    }
+  };
+
+} // end namespace PBQP
+} // end namespace llvm
+
+#endif // LLVM_CODEGEN_PBQP_SOLUTION_H