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 using namespace mlir;
14 using namespace presburger;
15 
16 void testColumnEchelonForm(const Matrix &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<int64_t, 8> rowVec =
27         transform.preMultiplyWithRow(m.getRow(row));
28     for (unsigned col = lastAllowedNonZeroCol + 1, nCols = m.getNumColumns();
29          col < nCols; ++col) {
30       EXPECT_EQ(rowVec[col], 0);
31       if (rowVec[col] != 0) {
32         llvm::errs() << "Failed at input matrix:\n";
33         m.dump();
34       }
35     }
36     if (rowVec[lastAllowedNonZeroCol] != 0)
37       lastAllowedNonZeroCol++;
38   }
39   // The final value of lastAllowedNonZeroCol is the index of the first
40   // all-zeros column, so it must be equal to the rank.
41   EXPECT_EQ(lastAllowedNonZeroCol, rank);
42 }
43 
44 TEST(LinearTransformTest, transformToColumnEchelonTest) {
45   // m1, m2, m3 are rank 1 matrices -- the first and second rows are identical.
46   Matrix m1(2, 2);
47   m1(0, 0) = 4;
48   m1(0, 1) = -7;
49   m1(1, 0) = 4;
50   m1(1, 1) = -7;
51   testColumnEchelonForm(m1, 1u);
52 
53   Matrix m2(2, 2);
54   m2(0, 0) = -4;
55   m2(0, 1) = 7;
56   m2(1, 0) = 4;
57   m2(1, 1) = -7;
58   testColumnEchelonForm(m2, 1u);
59 
60   Matrix m3(2, 2);
61   m3(0, 0) = -4;
62   m3(0, 1) = -7;
63   m3(1, 0) = -4;
64   m3(1, 1) = -7;
65   testColumnEchelonForm(m3, 1u);
66 
67   // m4, m5, m6 are rank 2 matrices -- the first and second rows are different.
68   Matrix m4(2, 2);
69   m4(0, 0) = 4;
70   m4(0, 1) = -7;
71   m4(1, 0) = -4;
72   m4(1, 1) = -7;
73   testColumnEchelonForm(m4, 2u);
74 
75   Matrix m5(2, 2);
76   m5(0, 0) = -4;
77   m5(0, 1) = 7;
78   m5(1, 0) = 4;
79   m5(1, 1) = 7;
80   testColumnEchelonForm(m5, 2u);
81 
82   Matrix m6(2, 2);
83   m6(0, 0) = -4;
84   m6(0, 1) = -7;
85   m6(1, 0) = 4;
86   m6(1, 1) = -7;
87   testColumnEchelonForm(m5, 2u);
88 }
89