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