141 lines · 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-exception6//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 15using namespace mlir;16using namespace presburger;17 18// Test the arithmetic operations on QuasiPolynomials;19// addition, subtraction, multiplication, and division20// by a constant.21// Two QPs of 3 parameters each were generated randomly22// and their sum, difference, and product computed by hand.23TEST(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 that119// are identically zero. A random QP was generated and terms were120// changed to account for each condition in simplify() – 121// the term coefficient being zero, or all the coefficients in some122// affine term in the product being zero.123TEST(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}141