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 <memory>
23#include <type_traits>
24
25namespace llvm {
26namespace PBQP {
27
28template <typename ValueT>
29class ValuePool {
30public:
31  typedef std::shared_ptr<const ValueT> PoolRef;
32
33private:
34
35  class PoolEntry : public std::enable_shared_from_this<PoolEntry> {
36  public:
37    template <typename ValueKeyT>
38    PoolEntry(ValuePool &Pool, ValueKeyT Value)
39        : Pool(Pool), Value(std::move(Value)) {}
40    ~PoolEntry() { Pool.removeEntry(this); }
41    const ValueT& getValue() const { return Value; }
42  private:
43    ValuePool &Pool;
44    ValueT Value;
45  };
46
47  class PoolEntryDSInfo {
48  public:
49    static inline PoolEntry* getEmptyKey() { return nullptr; }
50
51    static inline PoolEntry* getTombstoneKey() {
52      return reinterpret_cast<PoolEntry*>(static_cast<uintptr_t>(1));
53    }
54
55    template <typename ValueKeyT>
56    static unsigned getHashValue(const ValueKeyT &C) {
57      return hash_value(C);
58    }
59
60    static unsigned getHashValue(PoolEntry *P) {
61      return getHashValue(P->getValue());
62    }
63
64    static unsigned getHashValue(const PoolEntry *P) {
65      return getHashValue(P->getValue());
66    }
67
68    template <typename ValueKeyT1, typename ValueKeyT2>
69    static
70    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  };
88
89  typedef DenseSet<PoolEntry*, PoolEntryDSInfo> EntrySetT;
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>
109class PoolCostAllocator {
110private:
111  typedef ValuePool<VectorT> VectorCostPool;
112  typedef ValuePool<MatrixT> MatrixCostPool;
113public:
114  typedef VectorT Vector;
115  typedef MatrixT Matrix;
116  typedef typename VectorCostPool::PoolRef VectorPtr;
117  typedef typename MatrixCostPool::PoolRef MatrixPtr;
118
119  template <typename VectorKeyT>
120  VectorPtr getVector(VectorKeyT v) { return VectorPool.getValue(std::move(v)); }
121
122  template <typename MatrixKeyT>
123  MatrixPtr getMatrix(MatrixKeyT m) { return MatrixPool.getValue(std::move(m)); }
124private:
125  VectorCostPool VectorPool;
126  MatrixCostPool MatrixPool;
127};
128
129} // namespace PBQP
130} // namespace llvm
131
132#endif
133