1274955Ssvnmir//===---------- CostAllocator.h - PBQP Cost Allocator -----------*- C++ -*-===// 2274955Ssvnmir// 3274955Ssvnmir// The LLVM Compiler Infrastructure 4274955Ssvnmir// 5274955Ssvnmir// This file is distributed under the University of Illinois Open Source 6274955Ssvnmir// License. See LICENSE.TXT for details. 7274955Ssvnmir// 8274955Ssvnmir//===----------------------------------------------------------------------===// 9274955Ssvnmir// 10274955Ssvnmir// Defines classes conforming to the PBQP cost value manager concept. 11274955Ssvnmir// 12274955Ssvnmir// Cost value managers are memory managers for PBQP cost values (vectors and 13274955Ssvnmir// matrices). Since PBQP graphs can grow very large (E.g. hundreds of thousands 14274955Ssvnmir// of edges on the largest function in SPEC2006). 15274955Ssvnmir// 16274955Ssvnmir//===----------------------------------------------------------------------===// 17274955Ssvnmir 18280031Sdim#ifndef LLVM_CODEGEN_PBQP_COSTALLOCATOR_H 19280031Sdim#define LLVM_CODEGEN_PBQP_COSTALLOCATOR_H 20274955Ssvnmir 21280031Sdim#include "llvm/ADT/DenseSet.h" 22280031Sdim#include <memory> 23274955Ssvnmir#include <type_traits> 24274955Ssvnmir 25280031Sdimnamespace llvm { 26274955Ssvnmirnamespace PBQP { 27274955Ssvnmir 28280031Sdimtemplate <typename ValueT> 29280031Sdimclass ValuePool { 30274955Ssvnmirpublic: 31280031Sdim typedef std::shared_ptr<const ValueT> PoolRef; 32274955Ssvnmir 33280031Sdimprivate: 34280031Sdim 35280031Sdim class PoolEntry : public std::enable_shared_from_this<PoolEntry> { 36274955Ssvnmir public: 37280031Sdim template <typename ValueKeyT> 38280031Sdim PoolEntry(ValuePool &Pool, ValueKeyT Value) 39280031Sdim : Pool(Pool), Value(std::move(Value)) {} 40280031Sdim ~PoolEntry() { Pool.removeEntry(this); } 41280031Sdim const ValueT& getValue() const { return Value; } 42274955Ssvnmir private: 43280031Sdim ValuePool &Pool; 44280031Sdim ValueT Value; 45274955Ssvnmir }; 46274955Ssvnmir 47280031Sdim class PoolEntryDSInfo { 48274955Ssvnmir public: 49280031Sdim static inline PoolEntry* getEmptyKey() { return nullptr; } 50280031Sdim 51280031Sdim static inline PoolEntry* getTombstoneKey() { 52280031Sdim return reinterpret_cast<PoolEntry*>(static_cast<uintptr_t>(1)); 53274955Ssvnmir } 54280031Sdim 55280031Sdim template <typename ValueKeyT> 56280031Sdim static unsigned getHashValue(const ValueKeyT &C) { 57280031Sdim return hash_value(C); 58274955Ssvnmir } 59280031Sdim 60280031Sdim static unsigned getHashValue(PoolEntry *P) { 61280031Sdim return getHashValue(P->getValue()); 62274955Ssvnmir } 63274955Ssvnmir 64280031Sdim static unsigned getHashValue(const PoolEntry *P) { 65280031Sdim return getHashValue(P->getValue()); 66274955Ssvnmir } 67280031Sdim 68280031Sdim template <typename ValueKeyT1, typename ValueKeyT2> 69280031Sdim static 70280031Sdim bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) { 71280031Sdim return C1 == C2; 72274955Ssvnmir } 73274955Ssvnmir 74280031Sdim template <typename ValueKeyT> 75280031Sdim static bool isEqual(const ValueKeyT &C, PoolEntry *P) { 76280031Sdim if (P == getEmptyKey() || P == getTombstoneKey()) 77280031Sdim return false; 78280031Sdim return isEqual(C, P->getValue()); 79274955Ssvnmir } 80280031Sdim 81280031Sdim static bool isEqual(PoolEntry *P1, PoolEntry *P2) { 82280031Sdim if (P1 == getEmptyKey() || P1 == getTombstoneKey()) 83280031Sdim return P1 == P2; 84280031Sdim return isEqual(P1->getValue(), P2); 85274955Ssvnmir } 86280031Sdim 87274955Ssvnmir }; 88274955Ssvnmir 89280031Sdim typedef DenseSet<PoolEntry*, PoolEntryDSInfo> EntrySetT; 90274955Ssvnmir 91280031Sdim EntrySetT EntrySet; 92274955Ssvnmir 93280031Sdim void removeEntry(PoolEntry *P) { EntrySet.erase(P); } 94274955Ssvnmir 95274955Ssvnmirpublic: 96280031Sdim template <typename ValueKeyT> PoolRef getValue(ValueKeyT ValueKey) { 97280031Sdim typename EntrySetT::iterator I = EntrySet.find_as(ValueKey); 98274955Ssvnmir 99280031Sdim if (I != EntrySet.end()) 100280031Sdim return PoolRef((*I)->shared_from_this(), &(*I)->getValue()); 101274955Ssvnmir 102280031Sdim auto P = std::make_shared<PoolEntry>(*this, std::move(ValueKey)); 103280031Sdim EntrySet.insert(P.get()); 104280031Sdim return PoolRef(std::move(P), &P->getValue()); 105274955Ssvnmir } 106274955Ssvnmir}; 107274955Ssvnmir 108280031Sdimtemplate <typename VectorT, typename MatrixT> 109274955Ssvnmirclass PoolCostAllocator { 110274955Ssvnmirprivate: 111280031Sdim typedef ValuePool<VectorT> VectorCostPool; 112280031Sdim typedef ValuePool<MatrixT> MatrixCostPool; 113274955Ssvnmirpublic: 114274955Ssvnmir typedef VectorT Vector; 115274955Ssvnmir typedef MatrixT Matrix; 116274955Ssvnmir typedef typename VectorCostPool::PoolRef VectorPtr; 117274955Ssvnmir typedef typename MatrixCostPool::PoolRef MatrixPtr; 118274955Ssvnmir 119274955Ssvnmir template <typename VectorKeyT> 120280031Sdim VectorPtr getVector(VectorKeyT v) { return VectorPool.getValue(std::move(v)); } 121274955Ssvnmir 122274955Ssvnmir template <typename MatrixKeyT> 123280031Sdim MatrixPtr getMatrix(MatrixKeyT m) { return MatrixPool.getValue(std::move(m)); } 124274955Ssvnmirprivate: 125280031Sdim VectorCostPool VectorPool; 126280031Sdim MatrixCostPool MatrixPool; 127274955Ssvnmir}; 128274955Ssvnmir 129280031Sdim} // namespace PBQP 130280031Sdim} // namespace llvm 131274955Ssvnmir 132280031Sdim#endif 133