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
| 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_COSTALLOCATOR_H 19#define LLVM_COSTALLOCATOR_H
| 18#ifndef LLVM_CODEGEN_PBQP_COSTALLOCATOR_H 19#define LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
|
20
| 20
|
21#include <set>
| 21#include "llvm/ADT/DenseSet.h" 22#include <memory>
|
22#include <type_traits> 23
| 23#include <type_traits> 24
|
| 25namespace llvm {
|
24namespace PBQP { 25
| 26namespace PBQP { 27
|
26template <typename CostT, 27 typename CostKeyTComparator> 28class CostPool {
| 28template <typename ValueT> 29class ValuePool {
|
29public:
| 30public:
|
| 31 typedef std::shared_ptr<const ValueT> PoolRef;
|
30
| 32
|
31 class PoolEntry {
| 33private: 34 35 class PoolEntry : public std::enable_shared_from_this<PoolEntry> {
|
32 public:
| 36 public:
|
33 template <typename CostKeyT> 34 PoolEntry(CostPool &pool, CostKeyT cost) 35 : pool(pool), cost(std::move(cost)), refCount(0) {} 36 ~PoolEntry() { pool.removeEntry(this); } 37 void incRef() { ++refCount; } 38 bool decRef() { --refCount; return (refCount == 0); } 39 CostT& getCost() { return cost; } 40 const CostT& getCost() const { return cost; }
| 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; }
|
41 private:
| 42 private:
|
42 CostPool &pool; 43 CostT cost; 44 std::size_t refCount;
| 43 ValuePool &Pool; 44 ValueT Value;
|
45 }; 46
| 45 }; 46
|
47 class PoolRef {
| 47 class PoolEntryDSInfo {
|
48 public:
| 48 public:
|
49 PoolRef(PoolEntry *entry) : entry(entry) { 50 this->entry->incRef();
| 49 static inline PoolEntry* getEmptyKey() { return nullptr; } 50 51 static inline PoolEntry* getTombstoneKey() { 52 return reinterpret_cast<PoolEntry*>(static_cast<uintptr_t>(1));
|
51 }
| 53 }
|
52 PoolRef(const PoolRef &r) { 53 entry = r.entry; 54 entry->incRef();
| 54 55 template <typename ValueKeyT> 56 static unsigned getHashValue(const ValueKeyT &C) { 57 return hash_value(C);
|
55 }
| 58 }
|
56 PoolRef& operator=(const PoolRef &r) { 57 assert(entry != nullptr && "entry should not be null."); 58 PoolEntry *temp = r.entry; 59 temp->incRef(); 60 entry->decRef(); 61 entry = temp; 62 return *this;
| 59 60 static unsigned getHashValue(PoolEntry *P) { 61 return getHashValue(P->getValue());
|
63 } 64
| 62 } 63
|
65 ~PoolRef() { 66 if (entry->decRef()) 67 delete entry;
| 64 static unsigned getHashValue(const PoolEntry *P) { 65 return getHashValue(P->getValue());
|
68 }
| 66 }
|
69 void reset(PoolEntry *entry) { 70 entry->incRef(); 71 this->entry->decRef(); 72 this->entry = entry;
| 67 68 template <typename ValueKeyT1, typename ValueKeyT2> 69 static 70 bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) { 71 return C1 == C2;
|
73 }
| 72 }
|
74 CostT& operator*() { return entry->getCost(); } 75 const CostT& operator*() const { return entry->getCost(); } 76 CostT* operator->() { return &entry->getCost(); } 77 const CostT* operator->() const { return &entry->getCost(); } 78 private: 79 PoolEntry *entry; 80 };
| |
81
| 73
|
82private: 83 class EntryComparator { 84 public: 85 template <typename CostKeyT> 86 typename std::enable_if< 87 !std::is_same<PoolEntry*, 88 typename std::remove_const<CostKeyT>::type>::value, 89 bool>::type 90 operator()(const PoolEntry* a, const CostKeyT &b) { 91 return compare(a->getCost(), b);
| 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());
|
92 }
| 79 }
|
93 bool operator()(const PoolEntry* a, const PoolEntry* b) { 94 return compare(a->getCost(), b->getCost());
| 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);
|
95 }
| 85 }
|
96 private: 97 CostKeyTComparator compare;
| 86
|
98 }; 99
| 87 }; 88
|
100 typedef std::set<PoolEntry*, EntryComparator> EntrySet;
| 89 typedef DenseSet<PoolEntry*, PoolEntryDSInfo> EntrySetT;
|
101
| 90
|
102 EntrySet entrySet;
| 91 EntrySetT EntrySet;
|
103
| 92
|
104 void removeEntry(PoolEntry *p) { entrySet.erase(p); }
| 93 void removeEntry(PoolEntry *P) { EntrySet.erase(P); }
|
105 106public:
| 94 95public:
|
| 96 template <typename ValueKeyT> PoolRef getValue(ValueKeyT ValueKey) { 97 typename EntrySetT::iterator I = EntrySet.find_as(ValueKey);
|
107
| 98
|
108 template <typename CostKeyT> 109 PoolRef getCost(CostKeyT costKey) { 110 typename EntrySet::iterator itr = 111 std::lower_bound(entrySet.begin(), entrySet.end(), costKey, 112 EntryComparator());
| 99 if (I != EntrySet.end()) 100 return PoolRef((*I)->shared_from_this(), &(*I)->getValue());
|
113
| 101
|
114 if (itr != entrySet.end() && costKey == (*itr)->getCost()) 115 return PoolRef(*itr); 116 117 PoolEntry *p = new PoolEntry(*this, std::move(costKey)); 118 entrySet.insert(itr, p); 119 return PoolRef(p);
| 102 auto P = std::make_shared<PoolEntry>(*this, std::move(ValueKey)); 103 EntrySet.insert(P.get()); 104 return PoolRef(std::move(P), &P->getValue());
|
120 } 121}; 122
| 105 } 106}; 107
|
123template <typename VectorT, typename VectorTComparator, 124 typename MatrixT, typename MatrixTComparator>
| 108template <typename VectorT, typename MatrixT>
|
125class PoolCostAllocator { 126private:
| 109class PoolCostAllocator { 110private:
|
127 typedef CostPool<VectorT, VectorTComparator> VectorCostPool; 128 typedef CostPool<MatrixT, MatrixTComparator> MatrixCostPool;
| 111 typedef ValuePool<VectorT> VectorCostPool; 112 typedef ValuePool<MatrixT> MatrixCostPool;
|
129public: 130 typedef VectorT Vector; 131 typedef MatrixT Matrix; 132 typedef typename VectorCostPool::PoolRef VectorPtr; 133 typedef typename MatrixCostPool::PoolRef MatrixPtr; 134 135 template <typename VectorKeyT>
| 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>
|
136 VectorPtr getVector(VectorKeyT v) { return vectorPool.getCost(std::move(v)); }
| 120 VectorPtr getVector(VectorKeyT v) { return VectorPool.getValue(std::move(v)); }
|
137 138 template <typename MatrixKeyT>
| 121 122 template <typename MatrixKeyT>
|
139 MatrixPtr getMatrix(MatrixKeyT m) { return matrixPool.getCost(std::move(m)); }
| 123 MatrixPtr getMatrix(MatrixKeyT m) { return MatrixPool.getValue(std::move(m)); }
|
140private:
| 124private:
|
141 VectorCostPool vectorPool; 142 MatrixCostPool matrixPool;
| 125 VectorCostPool VectorPool; 126 MatrixCostPool MatrixPool;
|
143}; 144
| 127}; 128
|
145}
| 129} // namespace PBQP 130} // namespace llvm
|
146
| 131
|
147#endif // LLVM_COSTALLOCATOR_H
| 132#endif
|
| |