LLVM  6.0.0svn
CostAllocator.h
Go to the documentation of this file.
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>
37  PoolEntry(ValuePool &Pool, ValueKeyT Value)
38  : Pool(Pool), Value(std::move(Value)) {}
39 
40  ~PoolEntry() { Pool.removeEntry(this); }
41 
42  const ValueT &getValue() const { return Value; }
43 
44  private:
45  ValuePool &Pool;
46  ValueT Value;
47  };
48 
49  class PoolEntryDSInfo {
50  public:
51  static inline PoolEntry *getEmptyKey() { return nullptr; }
52 
53  static inline PoolEntry *getTombstoneKey() {
54  return reinterpret_cast<PoolEntry *>(static_cast<uintptr_t>(1));
55  }
56 
57  template <typename ValueKeyT>
58  static unsigned getHashValue(const ValueKeyT &C) {
59  return hash_value(C);
60  }
61 
62  static unsigned getHashValue(PoolEntry *P) {
63  return getHashValue(P->getValue());
64  }
65 
66  static unsigned getHashValue(const PoolEntry *P) {
67  return getHashValue(P->getValue());
68  }
69 
70  template <typename ValueKeyT1, typename ValueKeyT2>
71  static bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
72  return C1 == C2;
73  }
74 
75  template <typename ValueKeyT>
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 
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 
90 
91  EntrySetT EntrySet;
92 
93  void removeEntry(PoolEntry *P) { EntrySet.erase(P); }
94 
95 public:
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:
112 
113 public:
114  using Vector = VectorT;
115  using Matrix = MatrixT;
118 
119  template <typename VectorKeyT> VectorPtr getVector(VectorKeyT v) {
120  return VectorPool.getValue(std::move(v));
121  }
122 
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
uint64_t CallInst * C
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
MatrixPtr getMatrix(MatrixKeyT m)
PoolRef getValue(ValueKeyT ValueKey)
Definition: CostAllocator.h:96
bool erase(const ValueT &V)
Definition: DenseSet.h:95
typename MatrixCostPool::PoolRef MatrixPtr
static bool isEqual(const Function &Caller, const Function &Callee)
#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:101
std::shared_ptr< const AllowedRegVector > PoolRef
Definition: CostAllocator.h:31
typename VectorCostPool::PoolRef VectorPtr
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM Value Representation.
Definition: Value.h:73