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
|
| |