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 <algorithm>
23 #include <cstdint>
24 #include <memory>
25 
26 namespace llvm {
27 namespace PBQP {
28 
29 template <typename ValueT> class ValuePool {
30 public:
31   using PoolRef = std::shared_ptr<const ValueT>;
32 
33 private:
34   class PoolEntry : public std::enable_shared_from_this<PoolEntry> {
35   public:
36     template <typename ValueKeyT>
PoolEntry(ValuePool & Pool,ValueKeyT Value)37     PoolEntry(ValuePool &Pool, ValueKeyT Value)
38         : Pool(Pool), Value(std::move(Value)) {}
39 
~PoolEntry()40     ~PoolEntry() { Pool.removeEntry(this); }
41 
getValue()42     const ValueT &getValue() const { return Value; }
43 
44   private:
45     ValuePool &Pool;
46     ValueT Value;
47   };
48 
49   class PoolEntryDSInfo {
50   public:
getEmptyKey()51     static inline PoolEntry *getEmptyKey() { return nullptr; }
52 
getTombstoneKey()53     static inline PoolEntry *getTombstoneKey() {
54       return reinterpret_cast<PoolEntry *>(static_cast<uintptr_t>(1));
55     }
56 
57     template <typename ValueKeyT>
getHashValue(const ValueKeyT & C)58     static unsigned getHashValue(const ValueKeyT &C) {
59       return hash_value(C);
60     }
61 
getHashValue(PoolEntry * P)62     static unsigned getHashValue(PoolEntry *P) {
63       return getHashValue(P->getValue());
64     }
65 
getHashValue(const PoolEntry * P)66     static unsigned getHashValue(const PoolEntry *P) {
67       return getHashValue(P->getValue());
68     }
69 
70     template <typename ValueKeyT1, typename ValueKeyT2>
isEqual(const ValueKeyT1 & C1,const ValueKeyT2 & C2)71     static bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
72       return C1 == C2;
73     }
74 
75     template <typename ValueKeyT>
isEqual(const ValueKeyT & C,PoolEntry * P)76     static bool isEqual(const ValueKeyT &C, PoolEntry *P) {
77       if (P == getEmptyKey() || P == getTombstoneKey())
78         return false;
79       return isEqual(C, P->getValue());
80     }
81 
isEqual(PoolEntry * P1,PoolEntry * P2)82     static bool isEqual(PoolEntry *P1, PoolEntry *P2) {
83       if (P1 == getEmptyKey() || P1 == getTombstoneKey())
84         return P1 == P2;
85       return isEqual(P1->getValue(), P2);
86     }
87   };
88 
89   using EntrySetT = DenseSet<PoolEntry *, PoolEntryDSInfo>;
90 
91   EntrySetT EntrySet;
92 
removeEntry(PoolEntry * P)93   void removeEntry(PoolEntry *P) { EntrySet.erase(P); }
94 
95 public:
getValue(ValueKeyT ValueKey)96   template <typename ValueKeyT> PoolRef getValue(ValueKeyT ValueKey) {
97     typename EntrySetT::iterator I = EntrySet.find_as(ValueKey);
98 
99     if (I != EntrySet.end())
100       return PoolRef((*I)->shared_from_this(), &(*I)->getValue());
101 
102     auto P = std::make_shared<PoolEntry>(*this, std::move(ValueKey));
103     EntrySet.insert(P.get());
104     return PoolRef(std::move(P), &P->getValue());
105   }
106 };
107 
108 template <typename VectorT, typename MatrixT> class PoolCostAllocator {
109 private:
110   using VectorCostPool = ValuePool<VectorT>;
111   using MatrixCostPool = ValuePool<MatrixT>;
112 
113 public:
114   using Vector = VectorT;
115   using Matrix = MatrixT;
116   using VectorPtr = typename VectorCostPool::PoolRef;
117   using MatrixPtr = typename MatrixCostPool::PoolRef;
118 
getVector(VectorKeyT v)119   template <typename VectorKeyT> VectorPtr getVector(VectorKeyT v) {
120     return VectorPool.getValue(std::move(v));
121   }
122 
getMatrix(MatrixKeyT m)123   template <typename MatrixKeyT> MatrixPtr getMatrix(MatrixKeyT m) {
124     return MatrixPool.getValue(std::move(m));
125   }
126 
127 private:
128   VectorCostPool VectorPool;
129   MatrixCostPool MatrixPool;
130 };
131 
132 } // end namespace PBQP
133 } // end namespace llvm
134 
135 #endif // LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
136