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 <memory> 23#include <type_traits> 24 25namespace llvm { 26namespace PBQP { 27 28template <typename ValueT> 29class ValuePool { 30public: 31 typedef std::shared_ptr<const ValueT> PoolRef; 32 33private: 34 35 class PoolEntry : public std::enable_shared_from_this<PoolEntry> { 36 public: 37 template <typename ValueKeyT> 38 PoolEntry(ValuePool &Pool, ValueKeyT Value) 39 : Pool(Pool), Value(std::move(Value)) {} 40 ~PoolEntry() { Pool.removeEntry(this); } 41 const ValueT& getValue() const { return Value; } 42 private: 43 ValuePool &Pool; 44 ValueT Value; 45 }; 46 47 class PoolEntryDSInfo { 48 public: 49 static inline PoolEntry* getEmptyKey() { return nullptr; } 50 51 static inline PoolEntry* getTombstoneKey() { 52 return reinterpret_cast<PoolEntry*>(static_cast<uintptr_t>(1)); 53 } 54 55 template <typename ValueKeyT> 56 static unsigned getHashValue(const ValueKeyT &C) { 57 return hash_value(C); 58 } 59 60 static unsigned getHashValue(PoolEntry *P) { 61 return getHashValue(P->getValue()); 62 } 63 64 static unsigned getHashValue(const PoolEntry *P) { 65 return getHashValue(P->getValue()); 66 } 67 68 template <typename ValueKeyT1, typename ValueKeyT2> 69 static 70 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 89 typedef DenseSet<PoolEntry*, PoolEntryDSInfo> EntrySetT; 90 91 EntrySetT EntrySet; 92 93 void removeEntry(PoolEntry *P) { EntrySet.erase(P); } 94 95public: 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 108template <typename VectorT, typename MatrixT> 109class PoolCostAllocator { 110private: 111 typedef ValuePool<VectorT> VectorCostPool; 112 typedef ValuePool<MatrixT> MatrixCostPool; 113public: 114 typedef VectorT Vector; 115 typedef MatrixT Matrix; 116 typedef typename VectorCostPool::PoolRef VectorPtr; 117 typedef typename MatrixCostPool::PoolRef MatrixPtr; 118 119 template <typename VectorKeyT> 120 VectorPtr getVector(VectorKeyT v) { return VectorPool.getValue(std::move(v)); } 121 122 template <typename MatrixKeyT> 123 MatrixPtr getMatrix(MatrixKeyT m) { return MatrixPool.getValue(std::move(m)); } 124private: 125 VectorCostPool VectorPool; 126 MatrixCostPool MatrixPool; 127}; 128 129} // namespace PBQP 130} // namespace llvm 131 132#endif 133