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
26namespace llvm {
27namespace PBQP {
28
29template <typename ValueT> class ValuePool {
30public:
31  using PoolRef = std::shared_ptr<const ValueT>;
32
33private:
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
89  using EntrySetT = DenseSet<PoolEntry *, PoolEntryDSInfo>;
90
91  EntrySetT EntrySet;
92
93  void removeEntry(PoolEntry *P) { EntrySet.erase(P); }
94
95public:
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
108template <typename VectorT, typename MatrixT> class PoolCostAllocator {
109private:
110  using VectorCostPool = ValuePool<VectorT>;
111  using MatrixCostPool = ValuePool<MatrixT>;
112
113public:
114  using Vector = VectorT;
115  using Matrix = MatrixT;
116  using VectorPtr = typename VectorCostPool::PoolRef;
117  using MatrixPtr = typename MatrixCostPool::PoolRef;
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
127private:
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