Utils.cpp | Explore in Territory

//===- Utils.cpp - General utilities for Presburger library ---------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// Utility functions required by the Presburger Library.
//
//===----------------------------------------------------------------------===//

#include "mlir/Analysis/Presburger/Utils.h"
#include "mlir/Analysis/Presburger/IntegerRelation.h"
#include "mlir/Analysis/Presburger/PresburgerSpace.h"
#include "llvm/ADT/STLFunctionalExtras.h"
#include "llvm/ADT/SmallBitVector.h"
#include "llvm/Support/LogicalResult.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <cstdint>
#include <numeric>
#include <optional>

usingnamespacemlir;
usingnamespacepresburger;
dynamicAPIntFromInt64;

/// Normalize a division's `dividend` and the `divisor` by their GCD. For
/// example: if the dividend and divisor are [2,0,4] and 4 respectively,
/// they get normalized to [1,0,2] and 2. The divisor must be non-negative;
/// it is allowed for the divisor to be zero, but nothing is done in this case.
static void normalizeDivisionByGCD(MutableArrayRef<DynamicAPInt> dividend,
                                   DynamicAPInt &divisor) { … }

/// Check if the pos^th variable can be represented as a division using upper
/// bound inequality at position `ubIneq` and lower bound inequality at position
/// `lbIneq`.
///
/// Let `var` be the pos^th variable, then `var` is equivalent to
/// `expr floordiv divisor` if there are constraints of the form:
///      0 <= expr - divisor * var <= divisor - 1
/// Rearranging, we have:
///       divisor * var - expr + (divisor - 1) >= 0  <-- Lower bound for 'var'
///      -divisor * var + expr                 >= 0  <-- Upper bound for 'var'
///
/// For example:
///     32*k >= 16*i + j - 31                 <-- Lower bound for 'k'
///     32*k  <= 16*i + j                     <-- Upper bound for 'k'
///     expr = 16*i + j, divisor = 32
///     k = ( 16*i + j ) floordiv 32
///
///     4q >= i + j - 2                       <-- Lower bound for 'q'
///     4q <= i + j + 1                       <-- Upper bound for 'q'
///     expr = i + j + 1, divisor = 4
///     q = (i + j + 1) floordiv 4
//
/// This function also supports detecting divisions from bounds that are
/// strictly tighter than the division bounds described above, since tighter
/// bounds imply the division bounds. For example:
///     4q - i - j + 2 >= 0                       <-- Lower bound for 'q'
///    -4q + i + j     >= 0                       <-- Tight upper bound for 'q'
///
/// To extract floor divisions with tighter bounds, we assume that the
/// constraints are of the form:
///     c <= expr - divisior * var <= divisor - 1, where 0 <= c <= divisor - 1
/// Rearranging, we have:
///     divisor * var - expr + (divisor - 1) >= 0  <-- Lower bound for 'var'
///    -divisor * var + expr - c             >= 0  <-- Upper bound for 'var'
///
/// If successful, `expr` is set to dividend of the division and `divisor` is
/// set to the denominator of the division, which will be positive.
/// The final division expression is normalized by GCD.
static LogicalResult getDivRepr(const IntegerRelation &cst, unsigned pos,
                                unsigned ubIneq, unsigned lbIneq,
                                MutableArrayRef<DynamicAPInt> expr,
                                DynamicAPInt &divisor) { … }

/// Check if the pos^th variable can be represented as a division using
/// equality at position `eqInd`.
///
/// For example:
///     32*k == 16*i + j - 31                 <-- `eqInd` for 'k'
///     expr = 16*i + j - 31, divisor = 32
///     k = (16*i + j - 31) floordiv 32
///
/// If successful, `expr` is set to dividend of the division and `divisor` is
/// set to the denominator of the division. The final division expression is
/// normalized by GCD.
static LogicalResult getDivRepr(const IntegerRelation &cst, unsigned pos,
                                unsigned eqInd,
                                MutableArrayRef<DynamicAPInt> expr,
                                DynamicAPInt &divisor) { … }

// Returns `false` if the constraints depends on a variable for which an
// explicit representation has not been found yet, otherwise returns `true`.
static bool checkExplicitRepresentation(const IntegerRelation &cst,
                                        ArrayRef<bool> foundRepr,
                                        ArrayRef<DynamicAPInt> dividend,
                                        unsigned pos) { … }

/// Check if the pos^th variable can be expressed as a floordiv of an affine
/// function of other variables (where the divisor is a positive constant).
/// `foundRepr` contains a boolean for each variable indicating if the
/// explicit representation for that variable has already been computed.
/// Returns the `MaybeLocalRepr` struct which contains the indices of the
/// constraints that can be expressed as a floordiv of an affine function. If
/// the representation could be computed, `dividend` and `denominator` are set.
/// If the representation could not be computed, the kind attribute in
/// `MaybeLocalRepr` is set to None.
MaybeLocalRepr presburger::computeSingleVarRepr(
    const IntegerRelation &cst, ArrayRef<bool> foundRepr, unsigned pos,
    MutableArrayRef<DynamicAPInt> dividend, DynamicAPInt &divisor) { … }

MaybeLocalRepr presburger::computeSingleVarRepr(
    const IntegerRelation &cst, ArrayRef<bool> foundRepr, unsigned pos,
    SmallVector<int64_t, 8> &dividend, unsigned &divisor) { … }

llvm::SmallBitVector presburger::getSubrangeBitVector(unsigned len,
                                                      unsigned setOffset,
                                                      unsigned numSet) { … }

void presburger::mergeLocalVars(
    IntegerRelation &relA, IntegerRelation &relB,
    llvm::function_ref<bool(unsigned i, unsigned j)> merge) { … }

SmallVector<DynamicAPInt, 8>
presburger::getDivUpperBound(ArrayRef<DynamicAPInt> dividend,
                             const DynamicAPInt &divisor,
                             unsigned localVarIdx) { … }

SmallVector<DynamicAPInt, 8>
presburger::getDivLowerBound(ArrayRef<DynamicAPInt> dividend,
                             const DynamicAPInt &divisor,
                             unsigned localVarIdx) { … }

DynamicAPInt presburger::gcdRange(ArrayRef<DynamicAPInt> range) { … }

DynamicAPInt presburger::normalizeRange(MutableArrayRef<DynamicAPInt> range) { … }

void presburger::normalizeDiv(MutableArrayRef<DynamicAPInt> num,
                              DynamicAPInt &denom) { … }

SmallVector<DynamicAPInt, 8>
presburger::getNegatedCoeffs(ArrayRef<DynamicAPInt> coeffs) { … }

SmallVector<DynamicAPInt, 8>
presburger::getComplementIneq(ArrayRef<DynamicAPInt> ineq) { … }

SmallVector<std::optional<DynamicAPInt>, 4>
DivisionRepr::divValuesAt(ArrayRef<DynamicAPInt> point) const { … }

void DivisionRepr::removeDuplicateDivs(
    llvm::function_ref<bool(unsigned i, unsigned j)> merge) { … }

void DivisionRepr::normalizeDivs() { … }

void DivisionRepr::insertDiv(unsigned pos, ArrayRef<DynamicAPInt> dividend,
                             const DynamicAPInt &divisor) { … }

void DivisionRepr::insertDiv(unsigned pos, unsigned num) { … }

void DivisionRepr::print(raw_ostream &os) const { … }

void DivisionRepr::dump() const { … }

SmallVector<DynamicAPInt, 8>
presburger::getDynamicAPIntVec(ArrayRef<int64_t> range) { … }

SmallVector<int64_t, 8> presburger::getInt64Vec(ArrayRef<DynamicAPInt> range) { … }

Fraction presburger::dotProduct(ArrayRef<Fraction> a, ArrayRef<Fraction> b) { … }

/// Find the product of two polynomials, each given by an array of
/// coefficients, by taking the convolution.
std::vector<Fraction> presburger::multiplyPolynomials(ArrayRef<Fraction> a,
                                                      ArrayRef<Fraction> b) { … }

bool presburger::isRangeZero(ArrayRef<Fraction> arr) { … }
llvm/mlir/lib/Analysis/Presburger/Utils.cpp
