1 //===- PWMAFunctionTest.cpp - Tests for PWMAFunction ----------------------===//
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 // This file contains tests for PWMAFunction.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "./Utils.h"
14 
15 #include "mlir/Analysis/Presburger/PWMAFunction.h"
16 #include "mlir/Analysis/Presburger/PresburgerRelation.h"
17 #include "mlir/IR/MLIRContext.h"
18 
19 #include <gmock/gmock.h>
20 #include <gtest/gtest.h>
21 
22 using namespace mlir;
23 using namespace presburger;
24 
25 using testing::ElementsAre;
26 
27 TEST(PWAFunctionTest, isEqual) {
28   // The output expressions are different but it doesn't matter because they are
29   // equal in this domain.
30   PWMAFunction idAtZeros = parsePWMAF(
31       /*numInputs=*/2, /*numOutputs=*/2,
32       {
33           {"(x, y) : (y == 0)", {{1, 0, 0}, {0, 1, 0}}},             // (x, y).
34           {"(x, y) : (y - 1 >= 0, x == 0)", {{1, 0, 0}, {0, 1, 0}}}, // (x, y).
35           {"(x, y) : (-y - 1 >= 0, x == 0)", {{1, 0, 0}, {0, 1, 0}}} // (x, y).
36       });
37   PWMAFunction idAtZeros2 = parsePWMAF(
38       /*numInputs=*/2, /*numOutputs=*/2,
39       {
40           {"(x, y) : (y == 0)", {{1, 0, 0}, {0, 20, 0}}}, // (x, 20y).
41           {"(x, y) : (y - 1 >= 0, x == 0)", {{30, 0, 0}, {0, 1, 0}}}, //(30x, y)
42           {"(x, y) : (-y - 1 > =0, x == 0)", {{30, 0, 0}, {0, 1, 0}}} //(30x, y)
43       });
44   EXPECT_TRUE(idAtZeros.isEqual(idAtZeros2));
45 
46   PWMAFunction notIdAtZeros = parsePWMAF(
47       /*numInputs=*/2, /*numOutputs=*/2,
48       {
49           {"(x, y) : (y == 0)", {{1, 0, 0}, {0, 1, 0}}},              // (x, y).
50           {"(x, y) : (y - 1 >= 0, x == 0)", {{1, 0, 0}, {0, 2, 0}}},  // (x, 2y)
51           {"(x, y) : (-y - 1 >= 0, x == 0)", {{1, 0, 0}, {0, 2, 0}}}, // (x, 2y)
52       });
53   EXPECT_FALSE(idAtZeros.isEqual(notIdAtZeros));
54 
55   // These match at their intersection but one has a bigger domain.
56   PWMAFunction idNoNegNegQuadrant = parsePWMAF(
57       /*numInputs=*/2, /*numOutputs=*/2,
58       {
59           {"(x, y) : (x >= 0)", {{1, 0, 0}, {0, 1, 0}}},             // (x, y).
60           {"(x, y) : (-x - 1 >= 0, y >= 0)", {{1, 0, 0}, {0, 1, 0}}} // (x, y).
61       });
62   PWMAFunction idOnlyPosX =
63       parsePWMAF(/*numInputs=*/2, /*numOutputs=*/2,
64                  {
65                      {"(x, y) : (x >= 0)", {{1, 0, 0}, {0, 1, 0}}}, // (x, y).
66                  });
67   EXPECT_FALSE(idNoNegNegQuadrant.isEqual(idOnlyPosX));
68 
69   // Different representations of the same domain.
70   PWMAFunction sumPlusOne = parsePWMAF(
71       /*numInputs=*/2, /*numOutputs=*/1,
72       {
73           {"(x, y) : (x >= 0)", {{1, 1, 1}}},                   // x + y + 1.
74           {"(x, y) : (-x - 1 >= 0, -y - 1 >= 0)", {{1, 1, 1}}}, // x + y + 1.
75           {"(x, y) : (-x - 1 >= 0, y >= 0)", {{1, 1, 1}}}       // x + y + 1.
76       });
77   PWMAFunction sumPlusOne2 =
78       parsePWMAF(/*numInputs=*/2, /*numOutputs=*/1,
79                  {
80                      {"(x, y) : ()", {{1, 1, 1}}}, // x + y + 1.
81                  });
82   EXPECT_TRUE(sumPlusOne.isEqual(sumPlusOne2));
83 
84   // Functions with zero input dimensions.
85   PWMAFunction noInputs1 = parsePWMAF(/*numInputs=*/0, /*numOutputs=*/1,
86                                       {
87                                           {"() : ()", {{1}}}, // 1.
88                                       });
89   PWMAFunction noInputs2 = parsePWMAF(/*numInputs=*/0, /*numOutputs=*/1,
90                                       {
91                                           {"() : ()", {{2}}}, // 1.
92                                       });
93   EXPECT_TRUE(noInputs1.isEqual(noInputs1));
94   EXPECT_FALSE(noInputs1.isEqual(noInputs2));
95 
96   // Mismatched dimensionalities.
97   EXPECT_FALSE(noInputs1.isEqual(sumPlusOne));
98   EXPECT_FALSE(idOnlyPosX.isEqual(sumPlusOne));
99 
100   // Divisions.
101   // Domain is only multiples of 6; x = 6k for some k.
102   // x + 4(x/2) + 4(x/3) == 26k.
103   PWMAFunction mul2AndMul3 = parsePWMAF(
104       /*numInputs=*/1, /*numOutputs=*/1,
105       {
106           {"(x) : (x - 2*(x floordiv 2) == 0, x - 3*(x floordiv 3) == 0)",
107            {{1, 4, 4, 0}}}, // x + 4(x/2) + 4(x/3).
108       });
109   PWMAFunction mul6 = parsePWMAF(
110       /*numInputs=*/1, /*numOutputs=*/1,
111       {
112           {"(x) : (x - 6*(x floordiv 6) == 0)", {{0, 26, 0}}}, // 26(x/6).
113       });
114   EXPECT_TRUE(mul2AndMul3.isEqual(mul6));
115 
116   PWMAFunction mul6diff = parsePWMAF(
117       /*numInputs=*/1, /*numOutputs=*/1,
118       {
119           {"(x) : (x - 5*(x floordiv 5) == 0)", {{0, 52, 0}}}, // 52(x/6).
120       });
121   EXPECT_FALSE(mul2AndMul3.isEqual(mul6diff));
122 
123   PWMAFunction mul5 = parsePWMAF(
124       /*numInputs=*/1, /*numOutputs=*/1,
125       {
126           {"(x) : (x - 5*(x floordiv 5) == 0)", {{0, 26, 0}}}, // 26(x/5).
127       });
128   EXPECT_FALSE(mul2AndMul3.isEqual(mul5));
129 }
130 
131 TEST(PWMAFunction, valueAt) {
132   PWMAFunction nonNegPWMAF = parsePWMAF(
133       /*numInputs=*/2, /*numOutputs=*/2,
134       {
135           {"(x, y) : (x >= 0)", {{1, 2, 3}, {3, 4, 5}}}, // (x, y).
136           {"(x, y) : (y >= 0, -x - 1 >= 0)", {{-1, 2, 3}, {-3, 4, 5}}} // (x, y)
137       });
138   EXPECT_THAT(*nonNegPWMAF.valueAt({2, 3}), ElementsAre(11, 23));
139   EXPECT_THAT(*nonNegPWMAF.valueAt({-2, 3}), ElementsAre(11, 23));
140   EXPECT_THAT(*nonNegPWMAF.valueAt({2, -3}), ElementsAre(-1, -1));
141   EXPECT_FALSE(nonNegPWMAF.valueAt({-2, -3}).hasValue());
142 
143   PWMAFunction divPWMAF = parsePWMAF(
144       /*numInputs=*/2, /*numOutputs=*/2,
145       {
146           {"(x, y) : (x >= 0, x - 2*(x floordiv 2) == 0)",
147            {{0, 2, 1, 3}, {0, 4, 3, 5}}}, // (x, y).
148           {"(x, y) : (y >= 0, -x - 1 >= 0)", {{-1, 2, 3}, {-3, 4, 5}}} // (x, y)
149       });
150   EXPECT_THAT(*divPWMAF.valueAt({4, 3}), ElementsAre(11, 23));
151   EXPECT_THAT(*divPWMAF.valueAt({4, -3}), ElementsAre(-1, -1));
152   EXPECT_FALSE(divPWMAF.valueAt({3, 3}).hasValue());
153   EXPECT_FALSE(divPWMAF.valueAt({3, -3}).hasValue());
154 
155   EXPECT_THAT(*divPWMAF.valueAt({-2, 3}), ElementsAre(11, 23));
156   EXPECT_FALSE(divPWMAF.valueAt({-2, -3}).hasValue());
157 }
158 
159 TEST(PWMAFunction, removeIdRangeRegressionTest) {
160   PWMAFunction pwmafA = parsePWMAF(
161       /*numInputs=*/2, /*numOutputs=*/1,
162       {
163           {"(x, y) : (x == 0, y == 0, x - 2*(x floordiv 2) == 0, y - 2*(y "
164            "floordiv 2) == 0)",
165            {{0, 0, 0, 0, 0}}} // (0, 0)
166       });
167   PWMAFunction pwmafB = parsePWMAF(
168       /*numInputs=*/2, /*numOutputs=*/1,
169       {
170           {"(x, y) : (x - 11*y == 0, 11*x - y == 0, x - 2*(x floordiv 2) == 0, "
171            "y - 2*(y floordiv 2) == 0)",
172            {{0, 0, 0, 0, 0}}} // (0, 0)
173       });
174   EXPECT_TRUE(pwmafA.isEqual(pwmafB));
175 }
176 
177 TEST(PWMAFunction, eliminateRedundantLocalIdRegressionTest) {
178   PWMAFunction pwmafA = parsePWMAF(
179       /*numInputs=*/2, /*numOutputs=*/1,
180       {
181           {"(x, y) : (x - 2*(x floordiv 2) == 0, x - 2*y == 0)",
182            {{0, 1, 0, 0}}} // (0, 0)
183       });
184   PWMAFunction pwmafB = parsePWMAF(
185       /*numInputs=*/2, /*numOutputs=*/1,
186       {
187           {"(x, y) : (x - 2*(x floordiv 2) == 0, x - 2*y == 0)",
188            {{1, -1, 0, 0}}} // (0, 0)
189       });
190   EXPECT_TRUE(pwmafA.isEqual(pwmafB));
191 }
192