LLVM  10.0.0svn
CostAllocator.h
Go to the documentation of this file.
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>
36  PoolEntry(ValuePool &Pool, ValueKeyT Value)
37  : Pool(Pool), Value(std::move(Value)) {}
38 
39  ~PoolEntry() { Pool.removeEntry(this); }
40 
41  const ValueT &getValue() const { return Value; }
42 
43  private:
44  ValuePool &Pool;
45  ValueT Value;
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 ValueKeyT>
57  static unsigned getHashValue(const ValueKeyT &C) {
58  return hash_value(C);
59  }
60 
61  static unsigned getHashValue(PoolEntry *P) {
62  return getHashValue(P->getValue());
63  }
64 
65  static unsigned getHashValue(const PoolEntry *P) {
66  return getHashValue(P->getValue());
67  }
68 
69  template <typename ValueKeyT1, typename ValueKeyT2>
70  static bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
71  return C1 == C2;
72  }
73 
74  template <typename ValueKeyT>
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 
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 
89 
90  EntrySetT EntrySet;
91 
92  void removeEntry(PoolEntry *P) { EntrySet.erase(P); }
93 
94 public:
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(std::move(P), &P->getValue());
104  }
105 };
106 
107 template <typename VectorT, typename MatrixT> class PoolCostAllocator {
108 private:
111 
112 public:
113  using Vector = VectorT;
114  using Matrix = MatrixT;
117 
118  template <typename VectorKeyT> VectorPtr getVector(VectorKeyT v) {
119  return VectorPool.getValue(std::move(v));
120  }
121 
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
uint64_t CallInst * C
This class represents lattice values for constants.
Definition: AllocatorList.h:23
MatrixPtr getMatrix(MatrixKeyT m)
PoolRef getValue(ValueKeyT ValueKey)
Definition: CostAllocator.h:95
bool erase(const ValueT &V)
Definition: DenseSet.h:95
typename MatrixCostPool::PoolRef MatrixPtr
#define P(N)
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:187
iterator find_as(const LookupKeyT &Val)
Alternative version of find() which allows a different, and possibly less expensive, key type.
Definition: DenseSet.h:176
VectorPtr getVector(VectorKeyT v)
hash_code hash_value(const Vector &V)
Return a hash_value for the given vector.
Definition: Math.h:100
std::shared_ptr< const AllowedRegVector > PoolRef
Definition: CostAllocator.h:30
typename VectorCostPool::PoolRef VectorPtr
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM Value Representation.
Definition: Value.h:74
bool isEqual(const GCNRPTracker::LiveRegSet &S1, const GCNRPTracker::LiveRegSet &S2)