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