Utils.h | Explore in Territory

//===- Utils.h - General utilities for Presburger library ------*- C++ -*-===//
//
// 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.
//
//===----------------------------------------------------------------------===//

#ifndef MLIR_ANALYSIS_PRESBURGER_UTILS_H
#define MLIR_ANALYSIS_PRESBURGER_UTILS_H

#include "mlir/Analysis/Presburger/Matrix.h"
#include "llvm/ADT/DynamicAPInt.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallBitVector.h"
#include "llvm/Support/raw_ostream.h"
#include <optional>
#include <string>

namespace mlir {
namespace presburger {
class IntegerRelation;

/// This class represents the result of operations optimizing something subject
/// to some constraints. If the constraints were not satisfiable the, kind will
/// be Empty. If the optimum is unbounded, the kind is Unbounded, and if the
/// optimum is bounded, the kind will be Bounded and `optimum` holds the optimal
/// value.
enum class OptimumKind { … };
template <typename T>
class MaybeOptimum { … };

/// `ReprKind` enum is used to set the constraint type in `MaybeLocalRepr`.
enum class ReprKind { … };

/// `MaybeLocalRepr` contains the indices of the constraints that can be
/// expressed as a floordiv of an affine function. If it's an `equality`
/// constraint, `equalityIdx` is set, in case of `inequality` the
/// `lowerBoundIdx` and `upperBoundIdx` is set. By default the kind attribute is
/// set to None.
struct MaybeLocalRepr { … };

/// Class storing division representation of local variables of a constraint
/// system. The coefficients of the dividends are stored in order:
/// [nonLocalVars, localVars, constant]. Each local variable may or may not have
/// a representation. If the local does not have a representation, the dividend
/// of the division has no meaning and the denominator is zero. If it has a
/// representation, the denominator will be positive.
///
/// The i^th division here, represents the division representation of the
/// variable at position `divOffset + i` in the constraint system.
class DivisionRepr { … };

/// If `q` is defined to be equal to `expr floordiv d`, this equivalent to
/// saying that `q` is an integer and `q` is subject to the inequalities
/// `0 <= expr - d*q <= c - 1` (quotient remainder theorem).
///
/// Rearranging, we get the bounds on `q`: d*q <= expr <= d*q + d - 1.
///
/// `getDivUpperBound` returns `d*q <= expr`, and
/// `getDivLowerBound` returns `expr <= d*q + d - 1`.
///
/// The parameter `dividend` corresponds to `expr` above, `divisor` to `d`, and
/// `localVarIdx` to the position of `q` in the coefficient list.
///
/// The coefficient of `q` in `dividend` must be zero, as it is not allowed for
/// local variable to be a floor division of an expression involving itself.
/// The divisor must be positive.
SmallVector<DynamicAPInt, 8> getDivUpperBound(ArrayRef<DynamicAPInt> dividend,
                                              const DynamicAPInt &divisor,
                                              unsigned localVarIdx);
SmallVector<DynamicAPInt, 8> getDivLowerBound(ArrayRef<DynamicAPInt> dividend,
                                              const DynamicAPInt &divisor,
                                              unsigned localVarIdx);

llvm::SmallBitVector getSubrangeBitVector(unsigned len, unsigned setOffset,
                                          unsigned numSet);

/// 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.
/// Return the given array as an array of DynamicAPInts.
SmallVector<DynamicAPInt, 8> getDynamicAPIntVec(ArrayRef<int64_t> range);
/// Return the given array as an array of int64_t.
SmallVector<int64_t, 8> getInt64Vec(ArrayRef<DynamicAPInt> range);

/// 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 `divisor` are set,
/// in which case, denominator will be positive. If the representation could
/// not be computed, the kind attribute in `MaybeLocalRepr` is set to None.
MaybeLocalRepr computeSingleVarRepr(const IntegerRelation &cst,
                                    ArrayRef<bool> foundRepr, unsigned pos,
                                    MutableArrayRef<DynamicAPInt> dividend,
                                    DynamicAPInt &divisor);

/// The following overload using int64_t is required for a callsite in
/// AffineStructures.h.
MaybeLocalRepr computeSingleVarRepr(const IntegerRelation &cst,
                                    ArrayRef<bool> foundRepr, unsigned pos,
                                    SmallVector<int64_t, 8> &dividend,
                                    unsigned &divisor);

/// Given two relations, A and B, add additional local vars to the sets such
/// that both have the union of the local vars in each set, without changing
/// the set of points that lie in A and B.
///
/// While taking union, if a local var in any set has a division representation
/// which is a duplicate of division representation, of another local var in any
/// set, it is not added to the final union of local vars and is instead merged.
///
/// On every possible merge, `merge(i, j)` is called. `i`, `j` are position
/// of local variables in both sets which are being merged. If `merge(i, j)`
/// returns true, the divisions are merged, otherwise the divisions are not
/// merged.
void mergeLocalVars(IntegerRelation &relA, IntegerRelation &relB,
                    llvm::function_ref<bool(unsigned i, unsigned j)> merge);

/// Compute the gcd of the range.
DynamicAPInt gcdRange(ArrayRef<DynamicAPInt> range);

/// Divide the range by its gcd and return the gcd.
DynamicAPInt normalizeRange(MutableArrayRef<DynamicAPInt> range);

/// Normalize the given (numerator, denominator) pair by dividing out the
/// common factors between them. The numerator here is an affine expression
/// with integer coefficients. The denominator must be positive.
void normalizeDiv(MutableArrayRef<DynamicAPInt> num, DynamicAPInt &denom);

/// Return `coeffs` with all the elements negated.
SmallVector<DynamicAPInt, 8> getNegatedCoeffs(ArrayRef<DynamicAPInt> coeffs);

/// Return the complement of the given inequality.
///
/// The complement of a_1 x_1 + ... + a_n x_ + c >= 0 is
/// a_1 x_1 + ... + a_n x_ + c < 0, i.e., -a_1 x_1 - ... - a_n x_ - c - 1 >= 0,
/// since all the variables are constrained to be integers.
SmallVector<DynamicAPInt, 8> getComplementIneq(ArrayRef<DynamicAPInt> ineq);

/// Compute the dot product of two vectors.
/// The vectors must have the same sizes.
Fraction dotProduct(ArrayRef<Fraction> a, ArrayRef<Fraction> b);

/// Find the product of two polynomials, each given by an array of
/// coefficients.
std::vector<Fraction> multiplyPolynomials(ArrayRef<Fraction> a,
                                          ArrayRef<Fraction> b);

bool isRangeZero(ArrayRef<Fraction> arr);

/// Example usage:
/// Print .12, 3.4, 56.7
/// preAlign = ".", minSpacing = 1,
///    .12   .12
///   3.4   3.4
///  56.7  56.7
struct PrintTableMetrics { … };

/// Iterate over each val in the table and update 'm' where
/// .maxPreIndent and .maxPostIndent are initialized to 0.
/// class T is any type that can be handled by llvm::raw_string_ostream.
template <class T>
void updatePrintMetrics(T val, PrintTableMetrics &m) { … }

/// Print val in the table with metrics specified in 'm'.
template <class T>
void printWithPrintMetrics(raw_ostream &os, T val, unsigned minSpacing,
                           const PrintTableMetrics &m) { … }
} // namespace presburger
} // namespace mlir

#endif // MLIR_ANALYSIS_PRESBURGER_UTILS_H
llvm/mlir/include/mlir/Analysis/Presburger/Utils.h
