mlir/unittests/Analysis/Presburger/QuasiPolynomialTest.cpp

   1 //===- MatrixTest.cpp - Tests for QuasiPolynomial -------------------------===//
   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/QuasiPolynomial.h"
  10 #include "./Utils.h"
  11 #include "mlir/Analysis/Presburger/Fraction.h"
  12 #include <gmock/gmock.h>
  13 #include <gtest/gtest.h>
  14
  15 using namespace mlir;
  16 using namespace presburger;
  17
  18 // Test the arithmetic operations on QuasiPolynomials;
  19 // addition, subtraction, multiplication, and division
  20 // by a constant.
  21 // Two QPs of 3 parameters each were generated randomly
  22 // and their sum, difference, and product computed by hand.
  23 TEST(QuasiPolynomialTest, arithmetic) {
  24   QuasiPolynomial qp1(
  25       3, {Fraction(1, 3), Fraction(1, 1), Fraction(1, 2)},
  26       {{{Fraction(1, 1), Fraction(-1, 2), Fraction(4, 5), Fraction(0, 1)},
  27         {Fraction(2, 3), Fraction(3, 4), Fraction(-1, 1), Fraction(5, 7)}},
  28        {{Fraction(1, 2), Fraction(1, 1), Fraction(4, 5), Fraction(1, 1)}},
  29        {{Fraction(-3, 2), Fraction(1, 1), Fraction(5, 6), Fraction(7, 5)},
  30         {Fraction(1, 4), Fraction(2, 1), Fraction(6, 5), Fraction(-9, 8)},
  31         {Fraction(3, 2), Fraction(2, 5), Fraction(-7, 4), Fraction(0, 1)}}});
  32   QuasiPolynomial qp2(
  33       3, {Fraction(1, 1), Fraction(2, 1)},
  34       {{{Fraction(1, 2), Fraction(0, 1), Fraction(-1, 3), Fraction(5, 3)},
  35         {Fraction(2, 1), Fraction(5, 4), Fraction(9, 7), Fraction(-1, 5)}},
  36        {{Fraction(1, 3), Fraction(-2, 3), Fraction(1, 1), Fraction(0, 1)}}});
  37
  38   QuasiPolynomial sum = qp1 + qp2;
  39   EXPECT_EQ_REPR_QUASIPOLYNOMIAL(
  40       sum,
  41       QuasiPolynomial(
  42           3,
  43           {Fraction(1, 3), Fraction(1, 1), Fraction(1, 2), Fraction(1, 1),
  44            Fraction(2, 1)},
  45           {{{Fraction(1, 1), Fraction(-1, 2), Fraction(4, 5), Fraction(0, 1)},
  46             {Fraction(2, 3), Fraction(3, 4), Fraction(-1, 1), Fraction(5, 7)}},
  47            {{Fraction(1, 2), Fraction(1, 1), Fraction(4, 5), Fraction(1, 1)}},
  48            {{Fraction(-3, 2), Fraction(1, 1), Fraction(5, 6), Fraction(7, 5)},
  49             {Fraction(1, 4), Fraction(2, 1), Fraction(6, 5), Fraction(-9, 8)},
  50             {Fraction(3, 2), Fraction(2, 5), Fraction(-7, 4), Fraction(0, 1)}},
  51            {{Fraction(1, 2), Fraction(0, 1), Fraction(-1, 3), Fraction(5, 3)},
  52             {Fraction(2, 1), Fraction(5, 4), Fraction(9, 7), Fraction(-1, 5)}},
  53            {{Fraction(1, 3), Fraction(-2, 3), Fraction(1, 1),
  54              Fraction(0, 1)}}}));
  55
  56   QuasiPolynomial diff = qp1 - qp2;
  57   EXPECT_EQ_REPR_QUASIPOLYNOMIAL(
  58       diff,
  59       QuasiPolynomial(
  60           3,
  61           {Fraction(1, 3), Fraction(1, 1), Fraction(1, 2), Fraction(-1, 1),
  62            Fraction(-2, 1)},
  63           {{{Fraction(1, 1), Fraction(-1, 2), Fraction(4, 5), Fraction(0, 1)},
  64             {Fraction(2, 3), Fraction(3, 4), Fraction(-1, 1), Fraction(5, 7)}},
  65            {{Fraction(1, 2), Fraction(1, 1), Fraction(4, 5), Fraction(1, 1)}},
  66            {{Fraction(-3, 2), Fraction(1, 1), Fraction(5, 6), Fraction(7, 5)},
  67             {Fraction(1, 4), Fraction(2, 1), Fraction(6, 5), Fraction(-9, 8)},
  68             {Fraction(3, 2), Fraction(2, 5), Fraction(-7, 4), Fraction(0, 1)}},
  69            {{Fraction(1, 2), Fraction(0, 1), Fraction(-1, 3), Fraction(5, 3)},
  70             {Fraction(2, 1), Fraction(5, 4), Fraction(9, 7), Fraction(-1, 5)}},
  71            {{Fraction(1, 3), Fraction(-2, 3), Fraction(1, 1),
  72              Fraction(0, 1)}}}));
  73
  74   QuasiPolynomial prod = qp1 * qp2;
  75   EXPECT_EQ_REPR_QUASIPOLYNOMIAL(
  76       prod,
  77       QuasiPolynomial(
  78           3,
  79           {Fraction(1, 3), Fraction(2, 3), Fraction(1, 1), Fraction(2, 1),
  80            Fraction(1, 2), Fraction(1, 1)},
  81           {{{Fraction(1, 1), Fraction(-1, 2), Fraction(4, 5), Fraction(0, 1)},
  82             {Fraction(2, 3), Fraction(3, 4), Fraction(-1, 1), Fraction(5, 7)},
  83             {Fraction(1, 2), Fraction(0, 1), Fraction(-1, 3), Fraction(5, 3)},
  84             {Fraction(2, 1), Fraction(5, 4), Fraction(9, 7), Fraction(-1, 5)}},
  85            {{Fraction(1, 1), Fraction(-1, 2), Fraction(4, 5), Fraction(0, 1)},
  86             {Fraction(2, 3), Fraction(3, 4), Fraction(-1, 1), Fraction(5, 7)},
  87             {Fraction(1, 3), Fraction(-2, 3), Fraction(1, 1), Fraction(0, 1)}},
  88            {{Fraction(1, 2), Fraction(1, 1), Fraction(4, 5), Fraction(1, 1)},
  89             {Fraction(1, 2), Fraction(0, 1), Fraction(-1, 3), Fraction(5, 3)},
  90             {Fraction(2, 1), Fraction(5, 4), Fraction(9, 7), Fraction(-1, 5)}},
  91            {{Fraction(1, 2), Fraction(1, 1), Fraction(4, 5), Fraction(1, 1)},
  92             {Fraction(1, 3), Fraction(-2, 3), Fraction(1, 1), Fraction(0, 1)}},
  93            {{Fraction(-3, 2), Fraction(1, 1), Fraction(5, 6), Fraction(7, 5)},
  94             {Fraction(1, 4), Fraction(2, 1), Fraction(6, 5), Fraction(-9, 8)},
  95             {Fraction(3, 2), Fraction(2, 5), Fraction(-7, 4), Fraction(0, 1)},
  96             {Fraction(1, 2), Fraction(0, 1), Fraction(-1, 3), Fraction(5, 3)},
  97             {Fraction(2, 1), Fraction(5, 4), Fraction(9, 7), Fraction(-1, 5)}},
  98            {{Fraction(-3, 2), Fraction(1, 1), Fraction(5, 6), Fraction(7, 5)},
  99             {Fraction(1, 4), Fraction(2, 1), Fraction(6, 5), Fraction(-9, 8)},
 100             {Fraction(3, 2), Fraction(2, 5), Fraction(-7, 4), Fraction(0, 1)},
 101             {Fraction(1, 3), Fraction(-2, 3), Fraction(1, 1),
 102              Fraction(0, 1)}}}));
 103
 104   QuasiPolynomial quot = qp1 / 2;
 105   EXPECT_EQ_REPR_QUASIPOLYNOMIAL(
 106       quot,
 107       QuasiPolynomial(
 108           3, {Fraction(1, 6), Fraction(1, 2), Fraction(1, 4)},
 109           {{{Fraction(1, 1), Fraction(-1, 2), Fraction(4, 5), Fraction(0, 1)},
 110             {Fraction(2, 3), Fraction(3, 4), Fraction(-1, 1), Fraction(5, 7)}},
 111            {{Fraction(1, 2), Fraction(1, 1), Fraction(4, 5), Fraction(1, 1)}},
 112            {{Fraction(-3, 2), Fraction(1, 1), Fraction(5, 6), Fraction(7, 5)},
 113             {Fraction(1, 4), Fraction(2, 1), Fraction(6, 5), Fraction(-9, 8)},
 114             {Fraction(3, 2), Fraction(2, 5), Fraction(-7, 4),
 115              Fraction(0, 1)}}}));
 116 }
 117
 118 // Test the simplify() operation on QPs, which removes terms that
 119 // are identically zero. A random QP was generated and terms were
 120 // changed to account for each condition in simplify() –
 121 // the term coefficient being zero, or all the coefficients in some
 122 // affine term in the product being zero.
 123 TEST(QuasiPolynomialTest, simplify) {
 124   QuasiPolynomial qp(2,
 125                      {Fraction(2, 3), Fraction(0, 1), Fraction(1, 1),
 126                       Fraction(1, 2), Fraction(0, 1)},
 127                      {{{Fraction(1, 1), Fraction(3, 4), Fraction(5, 3)},
 128                        {Fraction(2, 1), Fraction(0, 1), Fraction(0, 1)}},
 129                       {{Fraction(1, 3), Fraction(8, 5), Fraction(2, 5)}},
 130                       {{Fraction(2, 7), Fraction(9, 5), Fraction(0, 1)},
 131                        {Fraction(0, 1), Fraction(0, 1), Fraction(0, 1)}},
 132                       {{Fraction(1, 1), Fraction(4, 5), Fraction(6, 5)}},
 133                       {{Fraction(1, 3), Fraction(4, 3), Fraction(7, 8)}}});
 134   EXPECT_EQ_REPR_QUASIPOLYNOMIAL(
 135       qp.simplify(),
 136       QuasiPolynomial(2, {Fraction(2, 3), Fraction(1, 2)},
 137                       {{{Fraction(1, 1), Fraction(3, 4), Fraction(5, 3)},
 138                         {Fraction(2, 1), Fraction(0, 1), Fraction(0, 1)}},
 139                        {{Fraction(1, 1), Fraction(4, 5), Fraction(6, 5)}}}));
 140 }