llvm/mlir/unittests/Analysis/Presburger/PresburgerSetTest.cpp

//===- SetTest.cpp - Tests for PresburgerSet ------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file contains tests for PresburgerSet. The tests for union,
// intersection, subtract, and complement work by computing the operation on
// two sets and checking, for a set of points, that the resulting set contains
// the point iff the result is supposed to contain it. The test for isEqual just
// checks if the result for two sets matches the expected result.
//
//===----------------------------------------------------------------------===//

#include "Parser.h"
#include "Utils.h"
#include "mlir/Analysis/Presburger/PresburgerRelation.h"
#include "mlir/IR/MLIRContext.h"

#include <gmock/gmock.h>
#include <gtest/gtest.h>
#include <optional>

usingnamespacemlir;
usingnamespacepresburger;

/// Compute the union of s and t, and check that each of the given points
/// belongs to the union iff it belongs to at least one of s and t.
static void testUnionAtPoints(const PresburgerSet &s, const PresburgerSet &t,
                              ArrayRef<SmallVector<int64_t, 4>> points) { … }

/// Compute the intersection of s and t, and check that each of the given points
/// belongs to the intersection iff it belongs to both s and t.
static void testIntersectAtPoints(const PresburgerSet &s,
                                  const PresburgerSet &t,
                                  ArrayRef<SmallVector<int64_t, 4>> points) { … }

/// Compute the set difference s \ t, and check that each of the given points
/// belongs to the difference iff it belongs to s and does not belong to t.
static void testSubtractAtPoints(const PresburgerSet &s, const PresburgerSet &t,
                                 ArrayRef<SmallVector<int64_t, 4>> points) { … }

/// Compute the complement of s, and check that each of the given points
/// belongs to the complement iff it does not belong to s.
static void testComplementAtPoints(const PresburgerSet &s,
                                   ArrayRef<SmallVector<int64_t, 4>> points) { … }

/// Construct a PresburgerSet having `numDims` dimensions and no symbols from
/// the given list of IntegerPolyhedron. Each Poly in `polys` should also have
/// `numDims` dimensions and no symbols, although it can have any number of
/// local ids.
static PresburgerSet makeSetFromPoly(unsigned numDims,
                                     ArrayRef<IntegerPolyhedron> polys) { … }

TEST(SetTest, containsPoint) { … }

TEST(SetTest, Union) { … }

TEST(SetTest, Intersect) { … }

TEST(SetTest, Subtract) { … }

TEST(SetTest, Complement) { … }

TEST(SetTest, isEqual) { … }

void expectEqual(const PresburgerSet &s, const PresburgerSet &t) { … }

void expectEqual(const IntegerPolyhedron &s, const IntegerPolyhedron &t) { … }

void expectEmpty(const PresburgerSet &s) { … }

TEST(SetTest, divisions) { … }

void convertSuffixDimsToLocals(IntegerPolyhedron &poly, unsigned numLocals) { … }

inline IntegerPolyhedron
parseIntegerPolyhedronAndMakeLocals(StringRef str, unsigned numLocals) { … }

TEST(SetTest, divisionsDefByEq) { … }

TEST(SetTest, divisionNonDivLocals) { … }

TEST(SetTest, subtractDuplicateDivsRegression) { … }

/// Coalesce `set` and check that the `newSet` is equal to `set` and that
/// `expectedNumPoly` matches the number of Poly in the coalesced set.
void expectCoalesce(size_t expectedNumPoly, const PresburgerSet &set) { … }

TEST(SetTest, coalesceNoPoly) { … }

TEST(SetTest, coalesceContainedOneDim) { … }

TEST(SetTest, coalesceFirstEmpty) { … }

TEST(SetTest, coalesceSecondEmpty) { … }

TEST(SetTest, coalesceBothEmpty) { … }

TEST(SetTest, coalesceFirstUniv) { … }

TEST(SetTest, coalesceSecondUniv) { … }

TEST(SetTest, coalesceBothUniv) { … }

TEST(SetTest, coalesceFirstUnivSecondEmpty) { … }

TEST(SetTest, coalesceFirstEmptySecondUniv) { … }

TEST(SetTest, coalesceCutOneDim) { … }

TEST(SetTest, coalesceSeparateOneDim) { … }

TEST(SetTest, coalesceAdjEq) { … }

TEST(SetTest, coalesceContainedTwoDim) { … }

TEST(SetTest, coalesceCutTwoDim) { … }

TEST(SetTest, coalesceEqStickingOut) { … }

TEST(SetTest, coalesceSeparateTwoDim) { … }

TEST(SetTest, coalesceContainedEq) { … }

TEST(SetTest, coalesceCuttingEq) { … }

TEST(SetTest, coalesceSeparateEq) { … }

TEST(SetTest, coalesceContainedEqAsIneq) { … }

TEST(SetTest, coalesceContainedEqComplex) { … }

TEST(SetTest, coalesceThreeContained) { … }

TEST(SetTest, coalesceDoubleIncrement) { … }

TEST(SetTest, coalesceLastCoalesced) { … }

TEST(SetTest, coalesceDiv) { … }

TEST(SetTest, coalesceDivOtherContained) { … }

static void
expectComputedVolumeIsValidOverapprox(const PresburgerSet &set,
                                      std::optional<int64_t> trueVolume,
                                      std::optional<int64_t> resultBound) { … }

TEST(SetTest, computeVolume) { … }

// The last `numToProject` dims will be projected out, i.e., converted to
// locals.
void testComputeReprAtPoints(IntegerPolyhedron poly,
                             ArrayRef<SmallVector<int64_t, 4>> points,
                             unsigned numToProject) { … }

void testComputeRepr(IntegerPolyhedron poly, const PresburgerSet &expected,
                     unsigned numToProject) { … }

TEST(SetTest, computeReprWithOnlyDivLocals) { … }

TEST(SetTest, subtractOutputSizeRegression) { … }