diff options
Diffstat (limited to 'include/llvm/CodeGen/PBQP')
-rw-r--r-- | include/llvm/CodeGen/PBQP/CostAllocator.h | 61 | ||||
-rw-r--r-- | include/llvm/CodeGen/PBQP/Graph.h | 99 | ||||
-rw-r--r-- | include/llvm/CodeGen/PBQP/Math.h | 22 | ||||
-rw-r--r-- | include/llvm/CodeGen/PBQP/ReductionRules.h | 36 | ||||
-rw-r--r-- | include/llvm/CodeGen/PBQP/Solution.h | 2 |
5 files changed, 122 insertions, 98 deletions
diff --git a/include/llvm/CodeGen/PBQP/CostAllocator.h b/include/llvm/CodeGen/PBQP/CostAllocator.h index 02d39fe383f1..bde451ae1fcc 100644 --- a/include/llvm/CodeGen/PBQP/CostAllocator.h +++ b/include/llvm/CodeGen/PBQP/CostAllocator.h @@ -1,4 +1,4 @@ -//===---------- CostAllocator.h - PBQP Cost Allocator -----------*- C++ -*-===// +//===- CostAllocator.h - PBQP Cost Allocator --------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -19,26 +19,28 @@ #define LLVM_CODEGEN_PBQP_COSTALLOCATOR_H #include "llvm/ADT/DenseSet.h" +#include <algorithm> +#include <cstdint> #include <memory> -#include <type_traits> namespace llvm { namespace PBQP { -template <typename ValueT> -class ValuePool { +template <typename ValueT> class ValuePool { public: - typedef std::shared_ptr<const ValueT> PoolRef; + 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; } + + const ValueT &getValue() const { return Value; } + private: ValuePool &Pool; ValueT Value; @@ -46,10 +48,10 @@ private: class PoolEntryDSInfo { public: - static inline PoolEntry* getEmptyKey() { return nullptr; } + static inline PoolEntry *getEmptyKey() { return nullptr; } - static inline PoolEntry* getTombstoneKey() { - return reinterpret_cast<PoolEntry*>(static_cast<uintptr_t>(1)); + static inline PoolEntry *getTombstoneKey() { + return reinterpret_cast<PoolEntry *>(static_cast<uintptr_t>(1)); } template <typename ValueKeyT> @@ -66,8 +68,7 @@ private: } template <typename ValueKeyT1, typename ValueKeyT2> - static - bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) { + static bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) { return C1 == C2; } @@ -83,10 +84,9 @@ private: return P1 == P2; return isEqual(P1->getValue(), P2); } - }; - typedef DenseSet<PoolEntry*, PoolEntryDSInfo> EntrySetT; + using EntrySetT = DenseSet<PoolEntry *, PoolEntryDSInfo>; EntrySetT EntrySet; @@ -105,28 +105,31 @@ public: } }; -template <typename VectorT, typename MatrixT> -class PoolCostAllocator { +template <typename VectorT, typename MatrixT> class PoolCostAllocator { private: - typedef ValuePool<VectorT> VectorCostPool; - typedef ValuePool<MatrixT> MatrixCostPool; + using VectorCostPool = ValuePool<VectorT>; + using MatrixCostPool = ValuePool<MatrixT>; + public: - typedef VectorT Vector; - typedef MatrixT Matrix; - typedef typename VectorCostPool::PoolRef VectorPtr; - typedef typename MatrixCostPool::PoolRef MatrixPtr; + 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 VectorKeyT> - VectorPtr getVector(VectorKeyT v) { return VectorPool.getValue(std::move(v)); } + template <typename MatrixKeyT> MatrixPtr getMatrix(MatrixKeyT m) { + return MatrixPool.getValue(std::move(m)); + } - template <typename MatrixKeyT> - MatrixPtr getMatrix(MatrixKeyT m) { return MatrixPool.getValue(std::move(m)); } private: VectorCostPool VectorPool; MatrixCostPool MatrixPool; }; -} // namespace PBQP -} // namespace llvm +} // end namespace PBQP +} // end namespace llvm -#endif +#endif // LLVM_CODEGEN_PBQP_COSTALLOCATOR_H diff --git a/include/llvm/CodeGen/PBQP/Graph.h b/include/llvm/CodeGen/PBQP/Graph.h index 83487e6a808a..e94878ced10d 100644 --- a/include/llvm/CodeGen/PBQP/Graph.h +++ b/include/llvm/CodeGen/PBQP/Graph.h @@ -1,4 +1,4 @@ -//===-------------------- Graph.h - PBQP Graph ------------------*- C++ -*-===// +//===- Graph.h - PBQP Graph -------------------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -11,16 +11,14 @@ // //===----------------------------------------------------------------------===// - #ifndef LLVM_CODEGEN_PBQP_GRAPH_H #define LLVM_CODEGEN_PBQP_GRAPH_H #include "llvm/ADT/STLExtras.h" -#include "llvm/Support/Debug.h" #include <algorithm> #include <cassert> +#include <iterator> #include <limits> -#include <utility> #include <vector> namespace llvm { @@ -28,8 +26,8 @@ namespace PBQP { class GraphBase { public: - typedef unsigned NodeId; - typedef unsigned EdgeId; + using NodeId = unsigned; + using EdgeId = unsigned; /// @brief Returns a value representing an invalid (non-existent) node. static NodeId invalidNodeId() { @@ -48,32 +46,32 @@ namespace PBQP { template <typename SolverT> class Graph : public GraphBase { private: - typedef typename SolverT::CostAllocator CostAllocator; + using CostAllocator = typename SolverT::CostAllocator; + public: - typedef typename SolverT::RawVector RawVector; - typedef typename SolverT::RawMatrix RawMatrix; - typedef typename SolverT::Vector Vector; - typedef typename SolverT::Matrix Matrix; - typedef typename CostAllocator::VectorPtr VectorPtr; - typedef typename CostAllocator::MatrixPtr MatrixPtr; - typedef typename SolverT::NodeMetadata NodeMetadata; - typedef typename SolverT::EdgeMetadata EdgeMetadata; - typedef typename SolverT::GraphMetadata GraphMetadata; + 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: - typedef std::vector<EdgeId> AdjEdgeList; - typedef AdjEdgeList::size_type AdjEdgeIdx; - typedef AdjEdgeList::const_iterator AdjEdgeItr; + 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(); } - NodeEntry(VectorPtr Costs) : Costs(std::move(Costs)) {} - AdjEdgeIdx addAdjEdgeId(EdgeId EId) { AdjEdgeIdx Idx = AdjEdgeIds.size(); AdjEdgeIds.push_back(EId); @@ -96,6 +94,7 @@ namespace PBQP { VectorPtr Costs; NodeMetadata Metadata; + private: AdjEdgeList AdjEdgeIds; }; @@ -150,8 +149,10 @@ namespace PBQP { 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]; @@ -161,18 +162,20 @@ namespace PBQP { GraphMetadata Metadata; CostAllocator CostAlloc; - SolverT *Solver; + SolverT *Solver = nullptr; - typedef std::vector<NodeEntry> NodeVector; - typedef std::vector<NodeId> FreeNodeVector; + using NodeVector = std::vector<NodeEntry>; + using FreeNodeVector = std::vector<NodeId>; NodeVector Nodes; FreeNodeVector FreeNodeIds; - typedef std::vector<EdgeEntry> EdgeVector; - typedef std::vector<EdgeId> FreeEdgeVector; + using EdgeVector = std::vector<EdgeEntry>; + using FreeEdgeVector = std::vector<EdgeId>; EdgeVector Edges; FreeEdgeVector FreeEdgeIds; + Graph(const Graph &Other) {} + // ----- INTERNAL METHODS ----- NodeEntry &getNode(NodeId NId) { @@ -220,20 +223,18 @@ namespace PBQP { return EId; } - Graph(const Graph &Other) {} void operator=(const Graph &Other) {} public: - - typedef typename NodeEntry::AdjEdgeItr AdjEdgeItr; + using AdjEdgeItr = typename NodeEntry::AdjEdgeItr; class NodeItr { public: - typedef std::forward_iterator_tag iterator_category; - typedef NodeId value_type; - typedef int difference_type; - typedef NodeId* pointer; - typedef NodeId& reference; + 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) { @@ -283,53 +284,65 @@ namespace PBQP { class NodeIdSet { public: - NodeIdSet(const Graph &G) : G(G) { } + 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) { } + 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) { } + 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; }; /// @brief Construct an empty PBQP graph. - Graph() : Solver(nullptr) {} + Graph() = default; /// @brief Construct an empty PBQP graph with the given graph metadata. - Graph(GraphMetadata Metadata) - : Metadata(std::move(Metadata)), Solver(nullptr) {} + Graph(GraphMetadata Metadata) : Metadata(std::move(Metadata)) {} /// @brief Get a reference to the graph metadata. GraphMetadata& getMetadata() { return Metadata; } @@ -656,7 +669,7 @@ namespace PBQP { } }; -} // namespace PBQP -} // namespace llvm +} // end namespace PBQP +} // end 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 278787550a43..ba405e816d10 100644 --- a/include/llvm/CodeGen/PBQP/Math.h +++ b/include/llvm/CodeGen/PBQP/Math.h @@ -1,4 +1,4 @@ -//===------ Math.h - PBQP Vector and Matrix classes -------------*- C++ -*-===// +//===- Math.h - PBQP Vector and Matrix classes ------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -11,20 +11,22 @@ #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 { -typedef float PBQPNum; +using PBQPNum = float; /// \brief PBQP Vector class. class Vector { friend hash_code hash_value(const Vector &); -public: +public: /// \brief Construct a PBQP vector of the given size. explicit Vector(unsigned Length) : Length(Length), Data(llvm::make_unique<PBQPNum []>(Length)) {} @@ -120,8 +122,8 @@ OStream& operator<<(OStream &OS, const Vector &V) { class Matrix { private: friend hash_code hash_value(const Matrix &); -public: +public: /// \brief Construct a PBQP Matrix with the given dimensions. Matrix(unsigned Rows, unsigned Cols) : Rows(Rows), Cols(Cols), Data(llvm::make_unique<PBQPNum []>(Rows * Cols)) { @@ -253,9 +255,11 @@ OStream& operator<<(OStream &OS, const Matrix &M) { template <typename Metadata> class MDVector : public Vector { public: - MDVector(const Vector &v) : Vector(v), md(*this) { } + 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; }; @@ -268,9 +272,11 @@ inline hash_code hash_value(const MDVector<Metadata> &V) { template <typename Metadata> class MDMatrix : public Matrix { public: - MDMatrix(const Matrix &m) : Matrix(m), md(*this) { } + 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; }; @@ -280,7 +286,7 @@ inline hash_code hash_value(const MDMatrix<Metadata> &M) { return hash_value(static_cast<const Matrix&>(M)); } -} // namespace PBQP -} // namespace llvm +} // end namespace PBQP +} // end 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 d4a544bfe721..8aeb51936760 100644 --- a/include/llvm/CodeGen/PBQP/ReductionRules.h +++ b/include/llvm/CodeGen/PBQP/ReductionRules.h @@ -1,4 +1,4 @@ -//===----------- ReductionRules.h - Reduction Rules -------------*- C++ -*-===// +//===- ReductionRules.h - Reduction Rules -----------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -17,6 +17,8 @@ #include "Graph.h" #include "Math.h" #include "Solution.h" +#include <cassert> +#include <limits> namespace llvm { namespace PBQP { @@ -27,11 +29,11 @@ namespace PBQP { /// neighbor. Notify the problem domain. template <typename GraphT> void applyR1(GraphT &G, typename GraphT::NodeId NId) { - typedef typename GraphT::NodeId NodeId; - typedef typename GraphT::EdgeId EdgeId; - typedef typename GraphT::Vector Vector; - typedef typename GraphT::Matrix Matrix; - typedef typename GraphT::RawVector RawVector; + 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."); @@ -71,11 +73,11 @@ namespace PBQP { template <typename GraphT> void applyR2(GraphT &G, typename GraphT::NodeId NId) { - typedef typename GraphT::NodeId NodeId; - typedef typename GraphT::EdgeId EdgeId; - typedef typename GraphT::Vector Vector; - typedef typename GraphT::Matrix Matrix; - typedef typename GraphT::RawMatrix RawMatrix; + 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."); @@ -177,9 +179,9 @@ namespace PBQP { // state. template <typename GraphT, typename StackT> Solution backpropagate(GraphT& G, StackT stack) { - typedef GraphBase::NodeId NodeId; - typedef typename GraphT::Matrix Matrix; - typedef typename GraphT::RawVector RawVector; + using NodeId = GraphBase::NodeId; + using Matrix = typename GraphT::Matrix; + using RawVector = typename GraphT::RawVector; Solution s; @@ -215,7 +217,7 @@ namespace PBQP { return s; } -} // namespace PBQP -} // namespace llvm +} // end namespace PBQP +} // end namespace llvm -#endif +#endif // LLVM_CODEGEN_PBQP_REDUCTIONRULES_H diff --git a/include/llvm/CodeGen/PBQP/Solution.h b/include/llvm/CodeGen/PBQP/Solution.h index d96b5eac4520..8d5d2374679d 100644 --- a/include/llvm/CodeGen/PBQP/Solution.h +++ b/include/llvm/CodeGen/PBQP/Solution.h @@ -26,7 +26,7 @@ namespace PBQP { /// To get the selection for each node in the problem use the getSelection method. class Solution { private: - typedef std::map<GraphBase::NodeId, unsigned> SelectionsMap; + using SelectionsMap = std::map<GraphBase::NodeId, unsigned>; SelectionsMap selections; unsigned r0Reductions = 0; |