LLVM 20.0.0git
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
25namespace llvm {
26namespace PBQP {
27
28template <typename ValueT> class ValuePool {
29public:
30 using PoolRef = std::shared_ptr<const ValueT>;
31
32private:
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;
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
88 using EntrySetT = DenseSet<PoolEntry *, PoolEntryDSInfo>;
89
90 EntrySetT EntrySet;
91
92 void removeEntry(PoolEntry *P) { EntrySet.erase(P); }
93
94public:
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
107template <typename VectorT, typename MatrixT> class PoolCostAllocator {
108private:
111
112public:
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
126private:
127 VectorCostPool VectorPool;
128 MatrixCostPool MatrixPool;
129};
130
131} // end namespace PBQP
132} // end namespace llvm
133
134#endif // LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
This file defines the DenseSet and SmallDenseSet classes.
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
VectorPtr getVector(VectorKeyT v)
typename MatrixCostPool::PoolRef MatrixPtr
MatrixPtr getMatrix(MatrixKeyT m)
typename VectorCostPool::PoolRef VectorPtr
PoolRef getValue(ValueKeyT ValueKey)
Definition: CostAllocator.h:95
std::shared_ptr< const ValueT > PoolRef
Definition: CostAllocator.h:30
LLVM Value Representation.
Definition: Value.h:74
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
hash_code hash_value(const Vector &V)
Return a hash_value for the given vector.
Definition: Math.h:100
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool isEqual(const GCNRPTracker::LiveRegSet &S1, const GCNRPTracker::LiveRegSet &S2)