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 CostT>
31 typedef std::shared_ptr<CostT> PoolRef;
35 class PoolEntry : public std::enable_shared_from_this<PoolEntry> {
37 template <typename CostKeyT>
38 PoolEntry(CostPool &pool, CostKeyT cost)
39 : pool(pool), cost(std::move(cost)) {}
40 ~PoolEntry() { pool.removeEntry(this); }
41 CostT& getCost() { return cost; }
42 const CostT& getCost() const { return cost; }
48 class PoolEntryDSInfo {
50 static inline PoolEntry* getEmptyKey() { return nullptr; }
52 static inline PoolEntry* getTombstoneKey() {
53 return reinterpret_cast<PoolEntry*>(static_cast<uintptr_t>(1));
56 template <typename CostKeyT>
57 static unsigned getHashValue(const CostKeyT &C) {
61 static unsigned getHashValue(PoolEntry *P) {
62 return getHashValue(P->getCost());
65 static unsigned getHashValue(const PoolEntry *P) {
66 return getHashValue(P->getCost());
69 template <typename CostKeyT1, typename CostKeyT2>
71 bool isEqual(const CostKeyT1 &C1, const CostKeyT2 &C2) {
75 template <typename CostKeyT>
76 static bool isEqual(const CostKeyT &C, PoolEntry *P) {
77 if (P == getEmptyKey() || P == getTombstoneKey())
79 return isEqual(C, P->getCost());
82 static bool isEqual(PoolEntry *P1, PoolEntry *P2) {
83 if (P1 == getEmptyKey() || P1 == getTombstoneKey())
85 return isEqual(P1->getCost(), P2);
90 typedef DenseSet<PoolEntry*, PoolEntryDSInfo> EntrySet;
94 void removeEntry(PoolEntry *p) { entrySet.erase(p); }
97 template <typename CostKeyT> PoolRef getCost(CostKeyT costKey) {
98 typename EntrySet::iterator itr = entrySet.find_as(costKey);
100 if (itr != entrySet.end())
101 return PoolRef((*itr)->shared_from_this(), &(*itr)->getCost());
103 auto p = std::make_shared<PoolEntry>(*this, std::move(costKey));
104 entrySet.insert(p.get());
105 return PoolRef(std::move(p), &p->getCost());
109 template <typename VectorT, typename MatrixT>
110 class PoolCostAllocator {
112 typedef CostPool<VectorT> VectorCostPool;
113 typedef CostPool<MatrixT> MatrixCostPool;
115 typedef VectorT Vector;
116 typedef MatrixT Matrix;
117 typedef typename VectorCostPool::PoolRef VectorPtr;
118 typedef typename MatrixCostPool::PoolRef MatrixPtr;
120 template <typename VectorKeyT>
121 VectorPtr getVector(VectorKeyT v) { return vectorPool.getCost(std::move(v)); }
123 template <typename MatrixKeyT>
124 MatrixPtr getMatrix(MatrixKeyT m) { return matrixPool.getCost(std::move(m)); }
126 VectorCostPool vectorPool;
127 MatrixCostPool matrixPool;