mlir/unittests/Analysis/Presburger/LinearTransformTest.cpp

   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 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<DynamicAPInt, 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   IntMatrix 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   IntMatrix 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   IntMatrix 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   IntMatrix 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   IntMatrix 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   IntMatrix 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 }