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 135