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

//===- IntegerPolyhedron.cpp - Tests for IntegerPolyhedron class ----------===//
//
// 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
//
//===----------------------------------------------------------------------===//

#include "Parser.h"
#include "Utils.h"
#include "mlir/Analysis/Presburger/IntegerRelation.h"
#include "mlir/Analysis/Presburger/PWMAFunction.h"
#include "mlir/Analysis/Presburger/Simplex.h"

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

#include <numeric>
#include <optional>

usingnamespacemlir;
usingnamespacepresburger;

ElementsAre;

enum class TestFunction { … };

/// Construct a IntegerPolyhedron from a set of inequality and
/// equality constraints.
static IntegerPolyhedron
makeSetFromConstraints(unsigned ids, ArrayRef<SmallVector<int64_t, 4>> ineqs,
                       ArrayRef<SmallVector<int64_t, 4>> eqs,
                       unsigned syms = 0) { … }

static void dump(ArrayRef<DynamicAPInt> vec) { … }

/// If fn is TestFunction::Sample (default):
///
///   If hasSample is true, check that findIntegerSample returns a valid sample
///   for the IntegerPolyhedron poly. Also check that getIntegerLexmin finds a
///   non-empty lexmin.
///
///   If hasSample is false, check that findIntegerSample returns std::nullopt
///   and findIntegerLexMin returns Empty.
///
/// If fn is TestFunction::Empty, check that isIntegerEmpty returns the
/// opposite of hasSample.
static void checkSample(bool hasSample, const IntegerPolyhedron &poly,
                        TestFunction fn = TestFunction::Sample) { … }

/// Check sampling for all the permutations of the dimensions for the given
/// constraint set. Since the GBR algorithm progresses dimension-wise, different
/// orderings may cause the algorithm to proceed differently. At least some of
///.these permutations should make it past the heuristics and test the
/// implementation of the GBR algorithm itself.
/// Use TestFunction fn to test.
static void checkPermutationsSample(bool hasSample, unsigned nDim,
                                    ArrayRef<SmallVector<int64_t, 4>> ineqs,
                                    ArrayRef<SmallVector<int64_t, 4>> eqs,
                                    TestFunction fn = TestFunction::Sample) { … }

TEST(IntegerPolyhedronTest, removeInequality) { … }

TEST(IntegerPolyhedronTest, removeEquality) { … }

TEST(IntegerPolyhedronTest, clearConstraints) { … }

TEST(IntegerPolyhedronTest, removeIdRange) { … }

TEST(IntegerPolyhedronTest, FindSampleTest) { … }

TEST(IntegerPolyhedronTest, IsIntegerEmptyTest) { … }

TEST(IntegerPolyhedronTest, removeRedundantConstraintsTest) { … }

TEST(IntegerPolyhedronTest, addConstantUpperBound) { … }

TEST(IntegerPolyhedronTest, addConstantLowerBound) { … }

/// Check if the expected division representation of local variables matches the
/// computed representation. The expected division representation is given as
/// a vector of expressions set in `expectedDividends` and the corressponding
/// denominator in `expectedDenominators`. The `denominators` and `dividends`
/// obtained through `getLocalRepr` function is verified against the
/// `expectedDenominators` and `expectedDividends` respectively.
static void checkDivisionRepresentation(
    IntegerPolyhedron &poly,
    const std::vector<SmallVector<int64_t, 8>> &expectedDividends,
    ArrayRef<int64_t> expectedDenominators) { … }

TEST(IntegerPolyhedronTest, computeLocalReprSimple) { … }

TEST(IntegerPolyhedronTest, computeLocalReprConstantFloorDiv) { … }

TEST(IntegerPolyhedronTest, computeLocalReprRecursive) { … }

TEST(IntegerPolyhedronTest, computeLocalReprTightUpperBound) { … }

TEST(IntegerPolyhedronTest, computeLocalReprFromEquality) { … }

TEST(IntegerPolyhedronTest, computeLocalReprFromEqualityAndInequality) { … }

TEST(IntegerPolyhedronTest, computeLocalReprNoRepr) { … }

TEST(IntegerPolyhedronTest, computeLocalReprNegConstNormalize) { … }

TEST(IntegerPolyhedronTest, simplifyLocalsTest) { … }

TEST(IntegerPolyhedronTest, mergeDivisionsSimple) { … }

TEST(IntegerPolyhedronTest, mergeDivisionsNestedDivsions) { … }

TEST(IntegerPolyhedronTest, mergeDivisionsConstants) { … }

TEST(IntegerPolyhedronTest, mergeDivisionsDuplicateInSameSet) { … }

TEST(IntegerPolyhedronTest, negativeDividends) { … }

void expectRationalLexMin(const IntegerPolyhedron &poly,
                          ArrayRef<Fraction> min) { … }

void expectNoRationalLexMin(OptimumKind kind, const IntegerPolyhedron &poly) { … }

TEST(IntegerPolyhedronTest, findRationalLexMin) { … }

void expectIntegerLexMin(const IntegerPolyhedron &poly, ArrayRef<int64_t> min) { … }

void expectNoIntegerLexMin(OptimumKind kind, const IntegerPolyhedron &poly) { … }

TEST(IntegerPolyhedronTest, findIntegerLexMin) { … }

void expectSymbolicIntegerLexMin(
    StringRef polyStr,
    ArrayRef<std::pair<StringRef, StringRef>> expectedLexminRepr,
    ArrayRef<StringRef> expectedUnboundedDomainRepr) { … }

void expectSymbolicIntegerLexMin(
    StringRef polyStr, ArrayRef<std::pair<StringRef, StringRef>> result) { … }

TEST(IntegerPolyhedronTest, findSymbolicIntegerLexMin) { … }

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

TEST(IntegerPolyhedronTest, computeVolume) { … }

bool containsPointNoLocal(const IntegerPolyhedron &poly,
                          ArrayRef<int64_t> point) { … }

TEST(IntegerPolyhedronTest, containsPointNoLocal) { … }

TEST(IntegerPolyhedronTest, truncateEqualityRegressionTest) { … }