LLVM  9.0.0svn
Math.h
Go to the documentation of this file.
1 //===- Math.h - PBQP Vector and Matrix classes ------------------*- 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 #ifndef LLVM_CODEGEN_PBQP_MATH_H
10 #define LLVM_CODEGEN_PBQP_MATH_H
11 
12 #include "llvm/ADT/Hashing.h"
13 #include "llvm/ADT/STLExtras.h"
14 #include <algorithm>
15 #include <cassert>
16 #include <functional>
17 #include <memory>
18 
19 namespace llvm {
20 namespace PBQP {
21 
22 using PBQPNum = float;
23 
24 /// PBQP Vector class.
25 class Vector {
26  friend hash_code hash_value(const Vector &);
27 
28 public:
29  /// Construct a PBQP vector of the given size.
30  explicit Vector(unsigned Length)
31  : Length(Length), Data(llvm::make_unique<PBQPNum []>(Length)) {}
32 
33  /// Construct a PBQP vector with initializer.
34  Vector(unsigned Length, PBQPNum InitVal)
35  : Length(Length), Data(llvm::make_unique<PBQPNum []>(Length)) {
36  std::fill(Data.get(), Data.get() + Length, InitVal);
37  }
38 
39  /// Copy construct a PBQP vector.
40  Vector(const Vector &V)
41  : Length(V.Length), Data(llvm::make_unique<PBQPNum []>(Length)) {
42  std::copy(V.Data.get(), V.Data.get() + Length, Data.get());
43  }
44 
45  /// Move construct a PBQP vector.
47  : Length(V.Length), Data(std::move(V.Data)) {
48  V.Length = 0;
49  }
50 
51  /// Comparison operator.
52  bool operator==(const Vector &V) const {
53  assert(Length != 0 && Data && "Invalid vector");
54  if (Length != V.Length)
55  return false;
56  return std::equal(Data.get(), Data.get() + Length, V.Data.get());
57  }
58 
59  /// Return the length of the vector
60  unsigned getLength() const {
61  assert(Length != 0 && Data && "Invalid vector");
62  return Length;
63  }
64 
65  /// Element access.
66  PBQPNum& operator[](unsigned Index) {
67  assert(Length != 0 && Data && "Invalid vector");
68  assert(Index < Length && "Vector element access out of bounds.");
69  return Data[Index];
70  }
71 
72  /// Const element access.
73  const PBQPNum& operator[](unsigned Index) const {
74  assert(Length != 0 && Data && "Invalid vector");
75  assert(Index < Length && "Vector element access out of bounds.");
76  return Data[Index];
77  }
78 
79  /// Add another vector to this one.
80  Vector& operator+=(const Vector &V) {
81  assert(Length != 0 && Data && "Invalid vector");
82  assert(Length == V.Length && "Vector length mismatch.");
83  std::transform(Data.get(), Data.get() + Length, V.Data.get(), Data.get(),
84  std::plus<PBQPNum>());
85  return *this;
86  }
87 
88  /// Returns the index of the minimum value in this vector
89  unsigned minIndex() const {
90  assert(Length != 0 && Data && "Invalid vector");
91  return std::min_element(Data.get(), Data.get() + Length) - Data.get();
92  }
93 
94 private:
95  unsigned Length;
96  std::unique_ptr<PBQPNum []> Data;
97 };
98 
99 /// Return a hash_value for the given vector.
100 inline hash_code hash_value(const Vector &V) {
101  unsigned *VBegin = reinterpret_cast<unsigned*>(V.Data.get());
102  unsigned *VEnd = reinterpret_cast<unsigned*>(V.Data.get() + V.Length);
103  return hash_combine(V.Length, hash_combine_range(VBegin, VEnd));
104 }
105 
106 /// Output a textual representation of the given vector on the given
107 /// output stream.
108 template <typename OStream>
109 OStream& operator<<(OStream &OS, const Vector &V) {
110  assert((V.getLength() != 0) && "Zero-length vector badness.");
111 
112  OS << "[ " << V[0];
113  for (unsigned i = 1; i < V.getLength(); ++i)
114  OS << ", " << V[i];
115  OS << " ]";
116 
117  return OS;
118 }
119 
120 /// PBQP Matrix class
121 class Matrix {
122 private:
123  friend hash_code hash_value(const Matrix &);
124 
125 public:
126  /// Construct a PBQP Matrix with the given dimensions.
127  Matrix(unsigned Rows, unsigned Cols) :
128  Rows(Rows), Cols(Cols), Data(llvm::make_unique<PBQPNum []>(Rows * Cols)) {
129  }
130 
131  /// Construct a PBQP Matrix with the given dimensions and initial
132  /// value.
133  Matrix(unsigned Rows, unsigned Cols, PBQPNum InitVal)
134  : Rows(Rows), Cols(Cols),
135  Data(llvm::make_unique<PBQPNum []>(Rows * Cols)) {
136  std::fill(Data.get(), Data.get() + (Rows * Cols), InitVal);
137  }
138 
139  /// Copy construct a PBQP matrix.
140  Matrix(const Matrix &M)
141  : Rows(M.Rows), Cols(M.Cols),
142  Data(llvm::make_unique<PBQPNum []>(Rows * Cols)) {
143  std::copy(M.Data.get(), M.Data.get() + (Rows * Cols), Data.get());
144  }
145 
146  /// Move construct a PBQP matrix.
148  : Rows(M.Rows), Cols(M.Cols), Data(std::move(M.Data)) {
149  M.Rows = M.Cols = 0;
150  }
151 
152  /// Comparison operator.
153  bool operator==(const Matrix &M) const {
154  assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
155  if (Rows != M.Rows || Cols != M.Cols)
156  return false;
157  return std::equal(Data.get(), Data.get() + (Rows * Cols), M.Data.get());
158  }
159 
160  /// Return the number of rows in this matrix.
161  unsigned getRows() const {
162  assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
163  return Rows;
164  }
165 
166  /// Return the number of cols in this matrix.
167  unsigned getCols() const {
168  assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
169  return Cols;
170  }
171 
172  /// Matrix element access.
173  PBQPNum* operator[](unsigned R) {
174  assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
175  assert(R < Rows && "Row out of bounds.");
176  return Data.get() + (R * Cols);
177  }
178 
179  /// Matrix element access.
180  const PBQPNum* operator[](unsigned R) const {
181  assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
182  assert(R < Rows && "Row out of bounds.");
183  return Data.get() + (R * Cols);
184  }
185 
186  /// Returns the given row as a vector.
187  Vector getRowAsVector(unsigned R) const {
188  assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
189  Vector V(Cols);
190  for (unsigned C = 0; C < Cols; ++C)
191  V[C] = (*this)[R][C];
192  return V;
193  }
194 
195  /// Returns the given column as a vector.
196  Vector getColAsVector(unsigned C) const {
197  assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
198  Vector V(Rows);
199  for (unsigned R = 0; R < Rows; ++R)
200  V[R] = (*this)[R][C];
201  return V;
202  }
203 
204  /// Matrix transpose.
205  Matrix transpose() const {
206  assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
207  Matrix M(Cols, Rows);
208  for (unsigned r = 0; r < Rows; ++r)
209  for (unsigned c = 0; c < Cols; ++c)
210  M[c][r] = (*this)[r][c];
211  return M;
212  }
213 
214  /// Add the given matrix to this one.
215  Matrix& operator+=(const Matrix &M) {
216  assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
217  assert(Rows == M.Rows && Cols == M.Cols &&
218  "Matrix dimensions mismatch.");
219  std::transform(Data.get(), Data.get() + (Rows * Cols), M.Data.get(),
220  Data.get(), std::plus<PBQPNum>());
221  return *this;
222  }
223 
224  Matrix operator+(const Matrix &M) {
225  assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
226  Matrix Tmp(*this);
227  Tmp += M;
228  return Tmp;
229  }
230 
231 private:
232  unsigned Rows, Cols;
233  std::unique_ptr<PBQPNum []> Data;
234 };
235 
236 /// Return a hash_code for the given matrix.
237 inline hash_code hash_value(const Matrix &M) {
238  unsigned *MBegin = reinterpret_cast<unsigned*>(M.Data.get());
239  unsigned *MEnd =
240  reinterpret_cast<unsigned*>(M.Data.get() + (M.Rows * M.Cols));
241  return hash_combine(M.Rows, M.Cols, hash_combine_range(MBegin, MEnd));
242 }
243 
244 /// Output a textual representation of the given matrix on the given
245 /// output stream.
246 template <typename OStream>
247 OStream& operator<<(OStream &OS, const Matrix &M) {
248  assert((M.getRows() != 0) && "Zero-row matrix badness.");
249  for (unsigned i = 0; i < M.getRows(); ++i)
250  OS << M.getRowAsVector(i) << "\n";
251  return OS;
252 }
253 
254 template <typename Metadata>
255 class MDVector : public Vector {
256 public:
257  MDVector(const Vector &v) : Vector(v), md(*this) {}
258  MDVector(Vector &&v) : Vector(std::move(v)), md(*this) { }
259 
260  const Metadata& getMetadata() const { return md; }
261 
262 private:
263  Metadata md;
264 };
265 
266 template <typename Metadata>
268  return hash_value(static_cast<const Vector&>(V));
269 }
270 
271 template <typename Metadata>
272 class MDMatrix : public Matrix {
273 public:
274  MDMatrix(const Matrix &m) : Matrix(m), md(*this) {}
275  MDMatrix(Matrix &&m) : Matrix(std::move(m)), md(*this) { }
276 
277  const Metadata& getMetadata() const { return md; }
278 
279 private:
280  Metadata md;
281 };
282 
283 template <typename Metadata>
285  return hash_value(static_cast<const Matrix&>(M));
286 }
287 
288 } // end namespace PBQP
289 } // end namespace llvm
290 
291 #endif // LLVM_CODEGEN_PBQP_MATH_H
uint64_t CallInst * C
OStream & operator<<(OStream &OS, const Vector &V)
Output a textual representation of the given vector on the given output stream.
Definition: Math.h:109
MDMatrix(Matrix &&m)
Definition: Math.h:275
This class represents lattice values for constants.
Definition: AllocatorList.h:23
PBQPNum * operator[](unsigned R)
Matrix element access.
Definition: Math.h:173
unsigned getLength() const
Return the length of the vector.
Definition: Math.h:60
PBQPNum & operator[](unsigned Index)
Element access.
Definition: Math.h:66
Vector getRowAsVector(unsigned R) const
Returns the given row as a vector.
Definition: Math.h:187
std::enable_if<!std::is_array< T >::value, std::unique_ptr< T > >::type make_unique(Args &&... args)
Constructs a new T() with the given args and returns a unique_ptr<T> which owns the object...
Definition: STLExtras.h:1405
MDMatrix(const Matrix &m)
Definition: Math.h:274
Matrix(unsigned Rows, unsigned Cols, PBQPNum InitVal)
Construct a PBQP Matrix with the given dimensions and initial value.
Definition: Math.h:133
Matrix(unsigned Rows, unsigned Cols)
Construct a PBQP Matrix with the given dimensions.
Definition: Math.h:127
MDVector(Vector &&v)
Definition: Math.h:258
Definition: BitVector.h:937
float PBQPNum
Definition: Math.h:22
Vector getColAsVector(unsigned C) const
Returns the given column as a vector.
Definition: Math.h:196
const PBQPNum & operator[](unsigned Index) const
Const element access.
Definition: Math.h:73
unsigned getRows() const
Return the number of rows in this matrix.
Definition: Math.h:161
unsigned minIndex() const
Returns the index of the minimum value in this vector.
Definition: Math.h:89
Vector(unsigned Length)
Construct a PBQP vector of the given size.
Definition: Math.h:30
unsigned getCols() const
Return the number of cols in this matrix.
Definition: Math.h:167
PBQP Matrix class.
Definition: Math.h:121
Matrix & operator+=(const Matrix &M)
Add the given matrix to this one.
Definition: Math.h:215
friend hash_code hash_value(const Vector &)
Return a hash_value for the given vector.
Definition: Math.h:100
PBQP Vector class.
Definition: Math.h:25
Matrix(Matrix &&M)
Move construct a PBQP matrix.
Definition: Math.h:147
Vector(const Vector &V)
Copy construct a PBQP vector.
Definition: Math.h:40
const PBQPNum * operator[](unsigned R) const
Matrix element access.
Definition: Math.h:180
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:600
Matrix operator+(const Matrix &M)
Definition: Math.h:224
bool operator==(const Vector &V) const
Comparison operator.
Definition: Math.h:52
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
Definition: Hashing.h:478
An opaque object representing a hash code.
Definition: Hashing.h:71
const Metadata & getMetadata() const
Definition: Math.h:260
bool operator==(const Matrix &M) const
Comparison operator.
Definition: Math.h:153
const Metadata & getMetadata() const
Definition: Math.h:277
Vector(Vector &&V)
Move construct a PBQP vector.
Definition: Math.h:46
Vector & operator+=(const Vector &V)
Add another vector to this one.
Definition: Math.h:80
Matrix transpose() const
Matrix transpose.
Definition: Math.h:205
OutputIt transform(R &&Range, OutputIt d_first, UnaryPredicate P)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere...
Definition: STLExtras.h:1274
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Matrix(const Matrix &M)
Copy construct a PBQP matrix.
Definition: Math.h:140
OutputIt copy(R &&Range, OutputIt Out)
Definition: STLExtras.h:1244
Root of the metadata hierarchy.
Definition: Metadata.h:57
Vector(unsigned Length, PBQPNum InitVal)
Construct a PBQP vector with initializer.
Definition: Math.h:34
MDVector(const Vector &v)
Definition: Math.h:257