[PBQP] Use DenseSet rather than std::set for PBQP's PoolCostAllocator
[oota-llvm.git] / include / llvm / CodeGen / PBQP / CostAllocator.h
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_CODEGEN_PBQP_COSTALLOCATOR_H
19 #define LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
20
21 #include "llvm/ADT/DenseSet.h"
22 #include <memory>
23 #include <type_traits>
24
25 namespace llvm {
26 namespace PBQP {
27
28 template <typename CostT>
29 class CostPool {
30 public:
31   typedef std::shared_ptr<CostT> PoolRef;
32
33 private:
34
35   class PoolEntry : public std::enable_shared_from_this<PoolEntry> {
36   public:
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; }
43   private:
44     CostPool &pool;
45     CostT cost;
46   };
47
48   class PoolEntryDSInfo {
49   public:
50     static inline PoolEntry* getEmptyKey() { return nullptr; }
51
52     static inline PoolEntry* getTombstoneKey() {
53       return reinterpret_cast<PoolEntry*>(static_cast<uintptr_t>(1));
54     }
55
56     template <typename CostKeyT>
57     static unsigned getHashValue(const CostKeyT &C) {
58       return hash_value(C);
59     }
60
61     static unsigned getHashValue(PoolEntry *P) {
62       return getHashValue(P->getCost());
63     }
64
65     static unsigned getHashValue(const PoolEntry *P) {
66       return getHashValue(P->getCost());
67     }
68
69     template <typename CostKeyT1, typename CostKeyT2>
70     static
71     bool isEqual(const CostKeyT1 &C1, const CostKeyT2 &C2) {
72       return C1 == C2;
73     }
74
75     template <typename CostKeyT>
76     static bool isEqual(const CostKeyT &C, PoolEntry *P) {
77       if (P == getEmptyKey() || P == getTombstoneKey())
78         return false;
79       return isEqual(C, P->getCost());
80     }
81
82     static bool isEqual(PoolEntry *P1, PoolEntry *P2) {
83       if (P1 == getEmptyKey() || P1 == getTombstoneKey())
84         return P1 == P2;
85       return isEqual(P1->getCost(), P2);
86     }
87
88   };
89
90   typedef DenseSet<PoolEntry*, PoolEntryDSInfo> EntrySet;
91
92   EntrySet entrySet;
93
94   void removeEntry(PoolEntry *p) { entrySet.erase(p); }
95
96 public:
97   template <typename CostKeyT> PoolRef getCost(CostKeyT costKey) {
98     typename EntrySet::iterator itr = entrySet.find_as(costKey);
99
100     if (itr != entrySet.end())
101       return PoolRef((*itr)->shared_from_this(), &(*itr)->getCost());
102
103     auto p = std::make_shared<PoolEntry>(*this, std::move(costKey));
104     entrySet.insert(p.get());
105     return PoolRef(std::move(p), &p->getCost());
106   }
107 };
108
109 template <typename VectorT, typename MatrixT>
110 class PoolCostAllocator {
111 private:
112   typedef CostPool<VectorT> VectorCostPool;
113   typedef CostPool<MatrixT> MatrixCostPool;
114 public:
115   typedef VectorT Vector;
116   typedef MatrixT Matrix;
117   typedef typename VectorCostPool::PoolRef VectorPtr;
118   typedef typename MatrixCostPool::PoolRef MatrixPtr;
119
120   template <typename VectorKeyT>
121   VectorPtr getVector(VectorKeyT v) { return vectorPool.getCost(std::move(v)); }
122
123   template <typename MatrixKeyT>
124   MatrixPtr getMatrix(MatrixKeyT m) { return matrixPool.getCost(std::move(m)); }
125 private:
126   VectorCostPool vectorPool;
127   MatrixCostPool matrixPool;
128 };
129
130 } // namespace PBQP
131 } // namespace llvm
132
133 #endif