MLIR  19.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 
13 #include "mlir/Support/LLVM.h"
14 #include <utility>
15 
16 using namespace mlir;
17 using namespace presburger;
18 
19 LinearTransform::LinearTransform(IntMatrix &&oMatrix) : matrix(oMatrix) {}
20 LinearTransform::LinearTransform(const IntMatrix &oMatrix) : matrix(oMatrix) {}
21 
22 std::pair<unsigned, LinearTransform>
24  // Compute the hermite normal form of m. This, is by definition, is in column
25  // echelon form.
26  auto [h, u] = m.computeHermiteNormalForm();
27 
28  // Since the matrix is in column ecehlon form, a zero column means the rest of
29  // the columns are zero. Thus, once we find a zero column, we can stop.
30  unsigned col, e;
31  for (col = 0, e = m.getNumColumns(); col < e; ++col) {
32  bool zeroCol = true;
33  for (unsigned row = 0, f = m.getNumRows(); row < f; ++row) {
34  if (h(row, col) != 0) {
35  zeroCol = false;
36  break;
37  }
38  }
39 
40  if (zeroCol)
41  break;
42  }
43 
44  return {col, LinearTransform(std::move(u))};
45 }
46 
48  IntegerRelation result(rel.getSpace());
49 
50  for (unsigned i = 0, e = rel.getNumEqualities(); i < e; ++i) {
51  ArrayRef<MPInt> eq = rel.getEquality(i);
52 
53  const MPInt &c = eq.back();
54 
55  SmallVector<MPInt, 8> newEq = preMultiplyWithRow(eq.drop_back());
56  newEq.push_back(c);
57  result.addEquality(newEq);
58  }
59 
60  for (unsigned i = 0, e = rel.getNumInequalities(); i < e; ++i) {
61  ArrayRef<MPInt> ineq = rel.getInequality(i);
62 
63  const MPInt &c = ineq.back();
64 
65  SmallVector<MPInt, 8> newIneq = preMultiplyWithRow(ineq.drop_back());
66  newIneq.push_back(c);
67  result.addInequality(newIneq);
68  }
69 
70  return result;
71 }
std::pair< IntMatrix, IntMatrix > 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:459
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 IntMatrix &m)
SmallVector< MPInt, 8 > preMultiplyWithRow(ArrayRef< MPInt > rowVec) const
LinearTransform(IntMatrix &&oMatrix)
IntegerRelation applyTo(const IntegerRelation &rel) const
This class provides support for multi-precision arithmetic.
Definition: MPInt.h:87
unsigned getNumRows() const
Definition: Matrix.h:85
unsigned getNumColumns() const
Definition: Matrix.h:87
Include the generated interface declarations.