Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 14 | pmbaty | 1 | //===- CostAllocator.h - PBQP Cost Allocator --------------------*- C++ -*-===// |
| 2 | // |
||
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
||
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
||
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
||
| 6 | // |
||
| 7 | //===----------------------------------------------------------------------===// |
||
| 8 | // |
||
| 9 | // Defines classes conforming to the PBQP cost value manager concept. |
||
| 10 | // |
||
| 11 | // Cost value managers are memory managers for PBQP cost values (vectors and |
||
| 12 | // matrices). Since PBQP graphs can grow very large (E.g. hundreds of thousands |
||
| 13 | // of edges on the largest function in SPEC2006). |
||
| 14 | // |
||
| 15 | //===----------------------------------------------------------------------===// |
||
| 16 | |||
| 17 | #ifndef LLVM_CODEGEN_PBQP_COSTALLOCATOR_H |
||
| 18 | #define LLVM_CODEGEN_PBQP_COSTALLOCATOR_H |
||
| 19 | |||
| 20 | #include "llvm/ADT/DenseSet.h" |
||
| 21 | #include <algorithm> |
||
| 22 | #include <cstdint> |
||
| 23 | #include <memory> |
||
| 24 | |||
| 25 | namespace llvm { |
||
| 26 | namespace PBQP { |
||
| 27 | |||
| 28 | template <typename ValueT> class ValuePool { |
||
| 29 | public: |
||
| 30 | using PoolRef = std::shared_ptr<const ValueT>; |
||
| 31 | |||
| 32 | private: |
||
| 33 | class PoolEntry : public std::enable_shared_from_this<PoolEntry> { |
||
| 34 | public: |
||
| 35 | template <typename ValueKeyT> |
||
| 36 | PoolEntry(ValuePool &Pool, ValueKeyT Value) |
||
| 37 | : Pool(Pool), Value(std::move(Value)) {} |
||
| 38 | |||
| 39 | ~PoolEntry() { Pool.removeEntry(this); } |
||
| 40 | |||
| 41 | const ValueT &getValue() const { return Value; } |
||
| 42 | |||
| 43 | private: |
||
| 44 | ValuePool &Pool; |
||
| 45 | ValueT Value; |
||
| 46 | }; |
||
| 47 | |||
| 48 | class PoolEntryDSInfo { |
||
| 49 | public: |
||
| 50 | static inline PoolEntry *getEmptyKey() { return nullptr; } |
||
| 51 | |||
| 52 | static inline PoolEntry *getTombstoneKey() { |
||
| 53 | return reinterpret_cast<PoolEntry *>(static_cast<uintptr_t>(1)); |
||
| 54 | } |
||
| 55 | |||
| 56 | template <typename ValueKeyT> |
||
| 57 | static unsigned getHashValue(const ValueKeyT &C) { |
||
| 58 | return hash_value(C); |
||
| 59 | } |
||
| 60 | |||
| 61 | static unsigned getHashValue(PoolEntry *P) { |
||
| 62 | return getHashValue(P->getValue()); |
||
| 63 | } |
||
| 64 | |||
| 65 | static unsigned getHashValue(const PoolEntry *P) { |
||
| 66 | return getHashValue(P->getValue()); |
||
| 67 | } |
||
| 68 | |||
| 69 | template <typename ValueKeyT1, typename ValueKeyT2> |
||
| 70 | static bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) { |
||
| 71 | return C1 == C2; |
||
| 72 | } |
||
| 73 | |||
| 74 | template <typename ValueKeyT> |
||
| 75 | static bool isEqual(const ValueKeyT &C, PoolEntry *P) { |
||
| 76 | if (P == getEmptyKey() || P == getTombstoneKey()) |
||
| 77 | return false; |
||
| 78 | return isEqual(C, P->getValue()); |
||
| 79 | } |
||
| 80 | |||
| 81 | static bool isEqual(PoolEntry *P1, PoolEntry *P2) { |
||
| 82 | if (P1 == getEmptyKey() || P1 == getTombstoneKey()) |
||
| 83 | return P1 == P2; |
||
| 84 | return isEqual(P1->getValue(), P2); |
||
| 85 | } |
||
| 86 | }; |
||
| 87 | |||
| 88 | using EntrySetT = DenseSet<PoolEntry *, PoolEntryDSInfo>; |
||
| 89 | |||
| 90 | EntrySetT EntrySet; |
||
| 91 | |||
| 92 | void removeEntry(PoolEntry *P) { EntrySet.erase(P); } |
||
| 93 | |||
| 94 | public: |
||
| 95 | template <typename ValueKeyT> PoolRef getValue(ValueKeyT ValueKey) { |
||
| 96 | typename EntrySetT::iterator I = EntrySet.find_as(ValueKey); |
||
| 97 | |||
| 98 | if (I != EntrySet.end()) |
||
| 99 | return PoolRef((*I)->shared_from_this(), &(*I)->getValue()); |
||
| 100 | |||
| 101 | auto P = std::make_shared<PoolEntry>(*this, std::move(ValueKey)); |
||
| 102 | EntrySet.insert(P.get()); |
||
| 103 | return PoolRef(std::move(P), &P->getValue()); |
||
| 104 | } |
||
| 105 | }; |
||
| 106 | |||
| 107 | template <typename VectorT, typename MatrixT> class PoolCostAllocator { |
||
| 108 | private: |
||
| 109 | using VectorCostPool = ValuePool<VectorT>; |
||
| 110 | using MatrixCostPool = ValuePool<MatrixT>; |
||
| 111 | |||
| 112 | public: |
||
| 113 | using Vector = VectorT; |
||
| 114 | using Matrix = MatrixT; |
||
| 115 | using VectorPtr = typename VectorCostPool::PoolRef; |
||
| 116 | using MatrixPtr = typename MatrixCostPool::PoolRef; |
||
| 117 | |||
| 118 | template <typename VectorKeyT> VectorPtr getVector(VectorKeyT v) { |
||
| 119 | return VectorPool.getValue(std::move(v)); |
||
| 120 | } |
||
| 121 | |||
| 122 | template <typename MatrixKeyT> MatrixPtr getMatrix(MatrixKeyT m) { |
||
| 123 | return MatrixPool.getValue(std::move(m)); |
||
| 124 | } |
||
| 125 | |||
| 126 | private: |
||
| 127 | VectorCostPool VectorPool; |
||
| 128 | MatrixCostPool MatrixPool; |
||
| 129 | }; |
||
| 130 | |||
| 131 | } // end namespace PBQP |
||
| 132 | } // end namespace llvm |
||
| 133 | |||
| 134 | #endif // LLVM_CODEGEN_PBQP_COSTALLOCATOR_H |