LLVM  14.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 
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 
88  using EntrySetT = DenseSet<PoolEntry *, PoolEntryDSInfo>;
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
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::RegAllocType::PBQP
@ PBQP
llvm::PBQP::PoolCostAllocator::Vector
VectorT Vector
Definition: CostAllocator.h:113
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
C1
instcombine should handle this C2 when C1
Definition: README.txt:263
llvm::isEqual
bool isEqual(const GCNRPTracker::LiveRegSet &S1, const GCNRPTracker::LiveRegSet &S2)
Definition: GCNRegPressure.cpp:55
llvm::PBQP::PoolCostAllocator::VectorPtr
typename VectorCostPool::PoolRef VectorPtr
Definition: CostAllocator.h:115
llvm::PBQP::PoolCostAllocator::getVector
VectorPtr getVector(VectorKeyT v)
Definition: CostAllocator.h:118
P2
This might compile to this xmm1 xorps xmm0 movss xmm0 ret Now consider if the code caused xmm1 to get spilled This might produce this xmm1 movaps xmm0 movaps xmm1 movss xmm0 ret since the reload is only used by these we could fold it into the producing something like xmm1 movaps xmm0 ret saving two instructions The basic idea is that a reload from a spill if only one byte chunk is bring in zeros the one element instead of elements This can be used to simplify a variety of shuffle where the elements are fixed zeros This code generates ugly probably due to costs being off or< 4 x float > * P2
Definition: README-SSE.txt:278
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::PBQP::PoolCostAllocator::getMatrix
MatrixPtr getMatrix(MatrixKeyT m)
Definition: CostAllocator.h:122
DenseSet.h
llvm::PBQP::hash_value
hash_code hash_value(const Vector &V)
Return a hash_value for the given vector.
Definition: Math.h:100
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::PBQP::PoolCostAllocator::MatrixPtr
typename MatrixCostPool::PoolRef MatrixPtr
Definition: CostAllocator.h:116
ValueT
llvm::PBQP::ValuePool< AllowedRegVector >::PoolRef
std::shared_ptr< const AllowedRegVector > PoolRef
Definition: CostAllocator.h:30
llvm::PBQP::PoolCostAllocator
Definition: CostAllocator.h:107
llvm::PBQP::ValuePool
Definition: CostAllocator.h:28
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::PBQP::ValuePool::getValue
PoolRef getValue(ValueKeyT ValueKey)
Definition: CostAllocator.h:95
llvm::PBQP::PoolCostAllocator::Matrix
MatrixT Matrix
Definition: CostAllocator.h:114
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::detail::DenseSetImpl< PoolEntry *, DenseMap< PoolEntry *, detail::DenseSetEmpty, PoolEntryDSInfo, detail::DenseSetPair< PoolEntry * > >, PoolEntryDSInfo >::iterator
Iterator iterator
Definition: DenseSet.h:170