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
21 #include "llvm/ADT/DenseSet.h"
23 #include <type_traits>
28 template <typename ValueT>
31 typedef std::shared_ptr<const ValueT> PoolRef;
35 class PoolEntry : public std::enable_shared_from_this<PoolEntry> {
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; }
47 class PoolEntryDSInfo {
49 static inline PoolEntry* getEmptyKey() { return nullptr; }
51 static inline PoolEntry* getTombstoneKey() {
52 return reinterpret_cast<PoolEntry*>(static_cast<uintptr_t>(1));
55 template <typename ValueKeyT>
56 static unsigned getHashValue(const ValueKeyT &C) {
60 static unsigned getHashValue(PoolEntry *P) {
61 return getHashValue(P->getValue());
64 static unsigned getHashValue(const PoolEntry *P) {
65 return getHashValue(P->getValue());
68 template <typename ValueKeyT1, typename ValueKeyT2>
70 bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
74 template <typename ValueKeyT>
75 static bool isEqual(const ValueKeyT &C, PoolEntry *P) {
76 if (P == getEmptyKey() || P == getTombstoneKey())
78 return isEqual(C, P->getValue());
81 static bool isEqual(PoolEntry *P1, PoolEntry *P2) {
82 if (P1 == getEmptyKey() || P1 == getTombstoneKey())
84 return isEqual(P1->getValue(), P2);
89 typedef DenseSet<PoolEntry*, PoolEntryDSInfo> EntrySetT;
93 void removeEntry(PoolEntry *P) { EntrySet.erase(P); }
96 template <typename ValueKeyT> PoolRef getValue(ValueKeyT ValueKey) {
97 typename EntrySetT::iterator I = EntrySet.find_as(ValueKey);
99 if (I != EntrySet.end())
100 return PoolRef((*I)->shared_from_this(), &(*I)->getValue());
102 auto P = std::make_shared<PoolEntry>(*this, std::move(ValueKey));
103 EntrySet.insert(P.get());
104 return PoolRef(std::move(P), &P->getValue());
108 template <typename VectorT, typename MatrixT>
109 class PoolCostAllocator {
111 typedef ValuePool<VectorT> VectorCostPool;
112 typedef ValuePool<MatrixT> MatrixCostPool;
114 typedef VectorT Vector;
115 typedef MatrixT Matrix;
116 typedef typename VectorCostPool::PoolRef VectorPtr;
117 typedef typename MatrixCostPool::PoolRef MatrixPtr;
119 template <typename VectorKeyT>
120 VectorPtr getVector(VectorKeyT v) { return VectorPool.getValue(std::move(v)); }
122 template <typename MatrixKeyT>
123 MatrixPtr getMatrix(MatrixKeyT m) { return MatrixPool.getValue(std::move(m)); }
125 VectorCostPool VectorPool;
126 MatrixCostPool MatrixPool;