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
9#include "mlir/Analysis/Presburger/LinearTransform.h"
10#include "mlir/Analysis/Presburger/IntegerRelation.h"
11#include "mlir/Analysis/Presburger/MPInt.h"
12#include "mlir/Analysis/Presburger/Matrix.h"
13#include "mlir/Support/LLVM.h"
14#include <utility>
15
16using namespace mlir;
17using namespace presburger;
18
19LinearTransform::LinearTransform(IntMatrix &&oMatrix) : matrix(oMatrix) {}
20LinearTransform::LinearTransform(const IntMatrix &oMatrix) : matrix(oMatrix) {}
21
22std::pair<unsigned, LinearTransform>
23LinearTransform::makeTransformToColumnEchelon(const IntMatrix &m) {
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
47IntegerRelation LinearTransform::applyTo(const IntegerRelation &rel) const {
48 IntegerRelation result(rel.getSpace());
49
50 for (unsigned i = 0, e = rel.getNumEqualities(); i < e; ++i) {
51 ArrayRef<MPInt> eq = rel.getEquality(idx: i);
52
53 const MPInt &c = eq.back();
54
55 SmallVector<MPInt, 8> newEq = preMultiplyWithRow(rowVec: eq.drop_back());
56 newEq.push_back(Elt: c);
57 result.addEquality(eq: newEq);
58 }
59
60 for (unsigned i = 0, e = rel.getNumInequalities(); i < e; ++i) {
61 ArrayRef<MPInt> ineq = rel.getInequality(idx: i);
62
63 const MPInt &c = ineq.back();
64
65 SmallVector<MPInt, 8> newIneq = preMultiplyWithRow(rowVec: ineq.drop_back());
66 newIneq.push_back(Elt: c);
67 result.addInequality(inEq: newIneq);
68 }
69
70 return result;
71}
72

source code of mlir/lib/Analysis/Presburger/LinearTransform.cpp