1//===- LinearTransformTest.cpp - Tests for LinearTransform ----------------===//
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 <gmock/gmock.h>
11#include <gtest/gtest.h>
12
13using namespace mlir;
14using namespace presburger;
15
16void testColumnEchelonForm(const IntMatrix &m, unsigned expectedRank) {
17 unsigned lastAllowedNonZeroCol = 0;
18 std::pair<unsigned, LinearTransform> result =
19 LinearTransform::makeTransformToColumnEchelon(m);
20 unsigned rank = result.first;
21 EXPECT_EQ(rank, expectedRank);
22 LinearTransform transform = result.second;
23 // In column echelon form, each row's last non-zero value can be at most one
24 // column to the right of the last non-zero column among the previous rows.
25 for (unsigned row = 0, nRows = m.getNumRows(); row < nRows; ++row) {
26 SmallVector<MPInt, 8> rowVec = transform.preMultiplyWithRow(rowVec: m.getRow(row));
27 for (unsigned col = lastAllowedNonZeroCol + 1, nCols = m.getNumColumns();
28 col < nCols; ++col) {
29 EXPECT_EQ(rowVec[col], 0);
30 if (rowVec[col] != 0) {
31 llvm::errs() << "Failed at input matrix:\n";
32 m.dump();
33 }
34 }
35 if (rowVec[lastAllowedNonZeroCol] != 0)
36 lastAllowedNonZeroCol++;
37 }
38 // The final value of lastAllowedNonZeroCol is the index of the first
39 // all-zeros column, so it must be equal to the rank.
40 EXPECT_EQ(lastAllowedNonZeroCol, rank);
41}
42
43TEST(LinearTransformTest, transformToColumnEchelonTest) {
44 // m1, m2, m3 are rank 1 matrices -- the first and second rows are identical.
45 IntMatrix m1(2, 2);
46 m1(0, 0) = 4;
47 m1(0, 1) = -7;
48 m1(1, 0) = 4;
49 m1(1, 1) = -7;
50 testColumnEchelonForm(m: m1, expectedRank: 1u);
51
52 IntMatrix m2(2, 2);
53 m2(0, 0) = -4;
54 m2(0, 1) = 7;
55 m2(1, 0) = 4;
56 m2(1, 1) = -7;
57 testColumnEchelonForm(m: m2, expectedRank: 1u);
58
59 IntMatrix m3(2, 2);
60 m3(0, 0) = -4;
61 m3(0, 1) = -7;
62 m3(1, 0) = -4;
63 m3(1, 1) = -7;
64 testColumnEchelonForm(m: m3, expectedRank: 1u);
65
66 // m4, m5, m6 are rank 2 matrices -- the first and second rows are different.
67 IntMatrix m4(2, 2);
68 m4(0, 0) = 4;
69 m4(0, 1) = -7;
70 m4(1, 0) = -4;
71 m4(1, 1) = -7;
72 testColumnEchelonForm(m: m4, expectedRank: 2u);
73
74 IntMatrix m5(2, 2);
75 m5(0, 0) = -4;
76 m5(0, 1) = 7;
77 m5(1, 0) = 4;
78 m5(1, 1) = 7;
79 testColumnEchelonForm(m: m5, expectedRank: 2u);
80
81 IntMatrix m6(2, 2);
82 m6(0, 0) = -4;
83 m6(0, 1) = -7;
84 m6(1, 0) = 4;
85 m6(1, 1) = -7;
86 testColumnEchelonForm(m: m5, expectedRank: 2u);
87}
88

source code of mlir/unittests/Analysis/Presburger/LinearTransformTest.cpp