MLIR  17.0.0git
LinearTransform.cpp
Go to the documentation of this file.
1 //===- LinearTransform.cpp - MLIR LinearTransform Class -------------------===//
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 
11 
12 using namespace mlir;
13 using namespace presburger;
14 
15 LinearTransform::LinearTransform(Matrix &&oMatrix) : matrix(oMatrix) {}
16 LinearTransform::LinearTransform(const Matrix &oMatrix) : matrix(oMatrix) {}
17 
18 std::pair<unsigned, LinearTransform>
20  // Compute the hermite normal form of m. This, is by definition, is in column
21  // echelon form.
22  auto [h, u] = m.computeHermiteNormalForm();
23 
24  // Since the matrix is in column ecehlon form, a zero column means the rest of
25  // the columns are zero. Thus, once we find a zero column, we can stop.
26  unsigned col, e;
27  for (col = 0, e = m.getNumColumns(); col < e; ++col) {
28  bool zeroCol = true;
29  for (unsigned row = 0, f = m.getNumRows(); row < f; ++row) {
30  if (h(row, col) != 0) {
31  zeroCol = false;
32  break;
33  }
34  }
35 
36  if (zeroCol)
37  break;
38  }
39 
40  return {col, LinearTransform(std::move(u))};
41 }
42 
44  IntegerRelation result(rel.getSpace());
45 
46  for (unsigned i = 0, e = rel.getNumEqualities(); i < e; ++i) {
47  ArrayRef<MPInt> eq = rel.getEquality(i);
48 
49  const MPInt &c = eq.back();
50 
51  SmallVector<MPInt, 8> newEq = preMultiplyWithRow(eq.drop_back());
52  newEq.push_back(c);
53  result.addEquality(newEq);
54  }
55 
56  for (unsigned i = 0, e = rel.getNumInequalities(); i < e; ++i) {
57  ArrayRef<MPInt> ineq = rel.getInequality(i);
58 
59  const MPInt &c = ineq.back();
60 
61  SmallVector<MPInt, 8> newIneq = preMultiplyWithRow(ineq.drop_back());
62  newIneq.push_back(c);
63  result.addInequality(newIneq);
64  }
65 
66  return result;
67 }
An IntegerRelation represents the set of points from a PresburgerSpace that satisfy a list of affine ...
ArrayRef< MPInt > getEquality(unsigned idx) const
void addInequality(ArrayRef< MPInt > inEq)
Adds an inequality (>= 0) from the coefficients specified in inEq.
void addEquality(ArrayRef< MPInt > eq)
Adds an equality from the coefficients specified in eq.
ArrayRef< MPInt > getInequality(unsigned idx) const
const PresburgerSpace & getSpace() const
Returns a reference to the underlying space.
static std::pair< unsigned, LinearTransform > makeTransformToColumnEchelon(const Matrix &m)
SmallVector< MPInt, 8 > preMultiplyWithRow(ArrayRef< MPInt > rowVec) const
IntegerRelation applyTo(const IntegerRelation &rel) const
This class provides support for multi-precision arithmetic.
Definition: MPInt.h:87
This is a class to represent a resizable matrix.
Definition: Matrix.h:35
unsigned getNumColumns() const
Definition: Matrix.h:78
unsigned getNumRows() const
Definition: Matrix.h:76
std::pair< Matrix, Matrix > computeHermiteNormalForm() const
Given the current matrix M, returns the matrices H, U such that H is the column hermite normal form o...
Definition: Matrix.cpp:269
This header declares functions that assit transformations in the MemRef dialect.