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