1 //===---------- CostAllocator.h - PBQP Cost Allocator -----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Defines classes conforming to the PBQP cost value manager concept.
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).
16 //===----------------------------------------------------------------------===//
18 #ifndef LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
19 #define LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
22 #include <type_traits>
26 template <typename CostT,
27 typename CostKeyTComparator>
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; }
49 PoolRef(PoolEntry *entry) : entry(entry) {
50 this->entry->incRef();
52 PoolRef(const PoolRef &r) {
56 PoolRef& operator=(const PoolRef &r) {
57 assert(entry != nullptr && "entry should not be null.");
58 PoolEntry *temp = r.entry;
69 void reset(PoolEntry *entry) {
71 this->entry->decRef();
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(); }
83 class EntryComparator {
85 template <typename CostKeyT>
86 typename std::enable_if<
87 !std::is_same<PoolEntry*,
88 typename std::remove_const<CostKeyT>::type>::value,
90 operator()(const PoolEntry* a, const CostKeyT &b) {
91 return compare(a->getCost(), b);
93 bool operator()(const PoolEntry* a, const PoolEntry* b) {
94 return compare(a->getCost(), b->getCost());
97 CostKeyTComparator compare;
100 typedef std::set<PoolEntry*, EntryComparator> EntrySet;
104 void removeEntry(PoolEntry *p) { entrySet.erase(p); }
108 template <typename CostKeyT>
109 PoolRef getCost(CostKeyT costKey) {
110 typename EntrySet::iterator itr =
111 std::lower_bound(entrySet.begin(), entrySet.end(), costKey,
114 if (itr != entrySet.end() && costKey == (*itr)->getCost())
115 return PoolRef(*itr);
117 PoolEntry *p = new PoolEntry(*this, std::move(costKey));
118 entrySet.insert(itr, p);
123 template <typename VectorT, typename VectorTComparator,
124 typename MatrixT, typename MatrixTComparator>
125 class PoolCostAllocator {
127 typedef CostPool<VectorT, VectorTComparator> VectorCostPool;
128 typedef CostPool<MatrixT, MatrixTComparator> MatrixCostPool;
130 typedef VectorT Vector;
131 typedef MatrixT Matrix;
132 typedef typename VectorCostPool::PoolRef VectorPtr;
133 typedef typename MatrixCostPool::PoolRef MatrixPtr;
135 template <typename VectorKeyT>
136 VectorPtr getVector(VectorKeyT v) { return vectorPool.getCost(std::move(v)); }
138 template <typename MatrixKeyT>
139 MatrixPtr getMatrix(MatrixKeyT m) { return matrixPool.getCost(std::move(m)); }
141 VectorCostPool vectorPool;
142 MatrixCostPool matrixPool;