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