1 //===- CostAllocator.h - PBQP Cost Allocator --------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Defines classes conforming to the PBQP cost value manager concept.
10 //
11 // Cost value managers are memory managers for PBQP cost values (vectors and
12 // matrices). Since PBQP graphs can grow very large (E.g. hundreds of thousands
13 // of edges on the largest function in SPEC2006).
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #ifndef LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
18 #define LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
19 
20 #include "llvm/ADT/DenseSet.h"
21 #include <algorithm>
22 #include <cstdint>
23 #include <memory>
24 
25 namespace llvm {
26 namespace PBQP {
27 
28 template <typename ValueT> class ValuePool {
29 public:
30   using PoolRef = std::shared_ptr<const ValueT>;
31 
32 private:
33   class PoolEntry : public std::enable_shared_from_this<PoolEntry> {
34   public:
35     template <typename ValueKeyT>
PoolEntry(ValuePool & Pool,ValueKeyT Value)36     PoolEntry(ValuePool &Pool, ValueKeyT Value)
37         : Pool(Pool), Value(std::move(Value)) {}
38 
~PoolEntry()39     ~PoolEntry() { Pool.removeEntry(this); }
40 
getValue()41     const ValueT &getValue() const { return Value; }
42 
43   private:
44     ValuePool &Pool;
45     ValueT Value;
46   };
47 
48   class PoolEntryDSInfo {
49   public:
getEmptyKey()50     static inline PoolEntry *getEmptyKey() { return nullptr; }
51 
getTombstoneKey()52     static inline PoolEntry *getTombstoneKey() {
53       return reinterpret_cast<PoolEntry *>(static_cast<uintptr_t>(1));
54     }
55 
56     template <typename ValueKeyT>
getHashValue(const ValueKeyT & C)57     static unsigned getHashValue(const ValueKeyT &C) {
58       return hash_value(C);
59     }
60 
getHashValue(PoolEntry * P)61     static unsigned getHashValue(PoolEntry *P) {
62       return getHashValue(P->getValue());
63     }
64 
getHashValue(const PoolEntry * P)65     static unsigned getHashValue(const PoolEntry *P) {
66       return getHashValue(P->getValue());
67     }
68 
69     template <typename ValueKeyT1, typename ValueKeyT2>
isEqual(const ValueKeyT1 & C1,const ValueKeyT2 & C2)70     static bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
71       return C1 == C2;
72     }
73 
74     template <typename ValueKeyT>
isEqual(const ValueKeyT & C,PoolEntry * P)75     static bool isEqual(const ValueKeyT &C, PoolEntry *P) {
76       if (P == getEmptyKey() || P == getTombstoneKey())
77         return false;
78       return isEqual(C, P->getValue());
79     }
80 
isEqual(PoolEntry * P1,PoolEntry * P2)81     static bool isEqual(PoolEntry *P1, PoolEntry *P2) {
82       if (P1 == getEmptyKey() || P1 == getTombstoneKey())
83         return P1 == P2;
84       return isEqual(P1->getValue(), P2);
85     }
86   };
87 
88   using EntrySetT = DenseSet<PoolEntry *, PoolEntryDSInfo>;
89 
90   EntrySetT EntrySet;
91 
removeEntry(PoolEntry * P)92   void removeEntry(PoolEntry *P) { EntrySet.erase(P); }
93 
94 public:
getValue(ValueKeyT ValueKey)95   template <typename ValueKeyT> PoolRef getValue(ValueKeyT ValueKey) {
96     typename EntrySetT::iterator I = EntrySet.find_as(ValueKey);
97 
98     if (I != EntrySet.end())
99       return PoolRef((*I)->shared_from_this(), &(*I)->getValue());
100 
101     auto P = std::make_shared<PoolEntry>(*this, std::move(ValueKey));
102     EntrySet.insert(P.get());
103     return PoolRef(P, &P->getValue());
104   }
105 };
106 
107 template <typename VectorT, typename MatrixT> class PoolCostAllocator {
108 private:
109   using VectorCostPool = ValuePool<VectorT>;
110   using MatrixCostPool = ValuePool<MatrixT>;
111 
112 public:
113   using Vector = VectorT;
114   using Matrix = MatrixT;
115   using VectorPtr = typename VectorCostPool::PoolRef;
116   using MatrixPtr = typename MatrixCostPool::PoolRef;
117 
getVector(VectorKeyT v)118   template <typename VectorKeyT> VectorPtr getVector(VectorKeyT v) {
119     return VectorPool.getValue(std::move(v));
120   }
121 
getMatrix(MatrixKeyT m)122   template <typename MatrixKeyT> MatrixPtr getMatrix(MatrixKeyT m) {
123     return MatrixPool.getValue(std::move(m));
124   }
125 
126 private:
127   VectorCostPool VectorPool;
128   MatrixCostPool MatrixPool;
129 };
130 
131 } // end namespace PBQP
132 } // end namespace llvm
133 
134 #endif // LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
135