1 //===- Utils.h - Utils for Presburger Tests ---------------------*- C++ -*-===//
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 defines helper functions for Presburger unittests.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #ifndef MLIR_UNITTESTS_ANALYSIS_PRESBURGER_UTILS_H
14 #define MLIR_UNITTESTS_ANALYSIS_PRESBURGER_UTILS_H
15
16 #include "mlir/Analysis/Presburger/GeneratingFunction.h"
17 #include "mlir/Analysis/Presburger/IntegerRelation.h"
18 #include "mlir/Analysis/Presburger/Matrix.h"
19 #include "mlir/Analysis/Presburger/QuasiPolynomial.h"
20
21 #include <gtest/gtest.h>
22 #include <optional>
23
24 namespace mlir {
25 namespace presburger {
26 using llvm::dynamicAPIntFromInt64;
27
makeIntMatrix(unsigned numRow,unsigned numColumns,ArrayRef<SmallVector<int,8>> matrix)28 inline IntMatrix makeIntMatrix(unsigned numRow, unsigned numColumns,
29 ArrayRef<SmallVector<int, 8>> matrix) {
30 IntMatrix results(numRow, numColumns);
31 assert(matrix.size() == numRow);
32 for (unsigned i = 0; i < numRow; ++i) {
33 assert(matrix[i].size() == numColumns &&
34 "Output expression has incorrect dimensionality!");
35 for (unsigned j = 0; j < numColumns; ++j)
36 results(i, j) = DynamicAPInt(matrix[i][j]);
37 }
38 return results;
39 }
40
makeFracMatrix(unsigned numRow,unsigned numColumns,ArrayRef<SmallVector<Fraction,8>> matrix)41 inline FracMatrix makeFracMatrix(unsigned numRow, unsigned numColumns,
42 ArrayRef<SmallVector<Fraction, 8>> matrix) {
43 FracMatrix results(numRow, numColumns);
44 assert(matrix.size() == numRow);
45 for (unsigned i = 0; i < numRow; ++i) {
46 assert(matrix[i].size() == numColumns &&
47 "Output expression has incorrect dimensionality!");
48 for (unsigned j = 0; j < numColumns; ++j)
49 results(i, j) = matrix[i][j];
50 }
51 return results;
52 }
53
EXPECT_EQ_INT_MATRIX(IntMatrix a,IntMatrix b)54 inline void EXPECT_EQ_INT_MATRIX(IntMatrix a, IntMatrix b) {
55 EXPECT_EQ(a.getNumRows(), b.getNumRows());
56 EXPECT_EQ(a.getNumColumns(), b.getNumColumns());
57
58 for (unsigned row = 0; row < a.getNumRows(); row++)
59 for (unsigned col = 0; col < a.getNumColumns(); col++)
60 EXPECT_EQ(a(row, col), b(row, col));
61 }
62
EXPECT_EQ_FRAC_MATRIX(FracMatrix a,FracMatrix b)63 inline void EXPECT_EQ_FRAC_MATRIX(FracMatrix a, FracMatrix b) {
64 EXPECT_EQ(a.getNumRows(), b.getNumRows());
65 EXPECT_EQ(a.getNumColumns(), b.getNumColumns());
66
67 for (unsigned row = 0; row < a.getNumRows(); row++)
68 for (unsigned col = 0; col < a.getNumColumns(); col++)
69 EXPECT_EQ(a(row, col), b(row, col));
70 }
71
72 // Check the coefficients (in order) of two generating functions.
73 // Note that this is not a true equality check.
EXPECT_EQ_REPR_GENERATINGFUNCTION(detail::GeneratingFunction a,detail::GeneratingFunction b)74 inline void EXPECT_EQ_REPR_GENERATINGFUNCTION(detail::GeneratingFunction a,
75 detail::GeneratingFunction b) {
76 EXPECT_EQ(a.getNumParams(), b.getNumParams());
77
78 SmallVector<int> aSigns = a.getSigns();
79 SmallVector<int> bSigns = b.getSigns();
80 EXPECT_EQ(aSigns.size(), bSigns.size());
81 for (unsigned i = 0, e = aSigns.size(); i < e; i++)
82 EXPECT_EQ(aSigns[i], bSigns[i]);
83
84 std::vector<detail::ParamPoint> aNums = a.getNumerators();
85 std::vector<detail::ParamPoint> bNums = b.getNumerators();
86 EXPECT_EQ(aNums.size(), bNums.size());
87 for (unsigned i = 0, e = aNums.size(); i < e; i++)
88 EXPECT_EQ_FRAC_MATRIX(aNums[i], bNums[i]);
89
90 std::vector<std::vector<detail::Point>> aDens = a.getDenominators();
91 std::vector<std::vector<detail::Point>> bDens = b.getDenominators();
92 EXPECT_EQ(aDens.size(), bDens.size());
93 for (unsigned i = 0, e = aDens.size(); i < e; i++) {
94 EXPECT_EQ(aDens[i].size(), bDens[i].size());
95 for (unsigned j = 0, f = aDens[i].size(); j < f; j++) {
96 EXPECT_EQ(aDens[i][j].size(), bDens[i][j].size());
97 for (unsigned k = 0, g = aDens[i][j].size(); k < g; k++) {
98 EXPECT_EQ(aDens[i][j][k], bDens[i][j][k]);
99 }
100 }
101 }
102 }
103
104 // Check the coefficients (in order) of two quasipolynomials.
105 // Note that this is not a true equality check.
EXPECT_EQ_REPR_QUASIPOLYNOMIAL(QuasiPolynomial a,QuasiPolynomial b)106 inline void EXPECT_EQ_REPR_QUASIPOLYNOMIAL(QuasiPolynomial a,
107 QuasiPolynomial b) {
108 EXPECT_EQ(a.getNumInputs(), b.getNumInputs());
109
110 SmallVector<Fraction> aCoeffs = a.getCoefficients(),
111 bCoeffs = b.getCoefficients();
112 EXPECT_EQ(aCoeffs.size(), bCoeffs.size());
113 for (unsigned i = 0, e = aCoeffs.size(); i < e; i++)
114 EXPECT_EQ(aCoeffs[i], bCoeffs[i]);
115
116 std::vector<std::vector<SmallVector<Fraction>>> aAff = a.getAffine(),
117 bAff = b.getAffine();
118 EXPECT_EQ(aAff.size(), bAff.size());
119 for (unsigned i = 0, e = aAff.size(); i < e; i++) {
120 EXPECT_EQ(aAff[i].size(), bAff[i].size());
121 for (unsigned j = 0, f = aAff[i].size(); j < f; j++)
122 for (unsigned k = 0, g = a.getNumInputs(); k <= g; k++)
123 EXPECT_EQ(aAff[i][j][k], bAff[i][j][k]);
124 }
125 }
126
127 /// lhs and rhs represent non-negative integers or positive infinity. The
128 /// infinity case corresponds to when the Optional is empty.
infinityOrUInt64LE(std::optional<DynamicAPInt> lhs,std::optional<DynamicAPInt> rhs)129 inline bool infinityOrUInt64LE(std::optional<DynamicAPInt> lhs,
130 std::optional<DynamicAPInt> rhs) {
131 // No constraint.
132 if (!rhs)
133 return true;
134 // Finite rhs provided so lhs has to be finite too.
135 if (!lhs)
136 return false;
137 return *lhs <= *rhs;
138 }
139
140 /// Expect that the computed volume is a valid overapproximation of
141 /// the true volume `trueVolume`, while also being at least as good an
142 /// approximation as `resultBound`.
expectComputedVolumeIsValidOverapprox(const std::optional<DynamicAPInt> & computedVolume,const std::optional<DynamicAPInt> & trueVolume,const std::optional<DynamicAPInt> & resultBound)143 inline void expectComputedVolumeIsValidOverapprox(
144 const std::optional<DynamicAPInt> &computedVolume,
145 const std::optional<DynamicAPInt> &trueVolume,
146 const std::optional<DynamicAPInt> &resultBound) {
147 assert(infinityOrUInt64LE(trueVolume, resultBound) &&
148 "can't expect result to be less than the true volume");
149 EXPECT_TRUE(infinityOrUInt64LE(trueVolume, computedVolume));
150 EXPECT_TRUE(infinityOrUInt64LE(computedVolume, resultBound));
151 }
152
expectComputedVolumeIsValidOverapprox(const std::optional<DynamicAPInt> & computedVolume,std::optional<int64_t> trueVolume,std::optional<int64_t> resultBound)153 inline void expectComputedVolumeIsValidOverapprox(
154 const std::optional<DynamicAPInt> &computedVolume,
155 std::optional<int64_t> trueVolume, std::optional<int64_t> resultBound) {
156 expectComputedVolumeIsValidOverapprox(
157 computedVolume,
158 llvm::transformOptional(trueVolume, dynamicAPIntFromInt64),
159 llvm::transformOptional(resultBound, dynamicAPIntFromInt64));
160 }
161
162 } // namespace presburger
163 } // namespace mlir
164
165 #endif // MLIR_UNITTESTS_ANALYSIS_PRESBURGER_UTILS_H
166