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(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 |
135 | |