#include <cmath>
#include <cstdint>
#include <limits>
#include <utility>
#include "AffineExprDetail.h"
#include "mlir/IR/AffineExpr.h"
#include "mlir/IR/AffineExprVisitor.h"
#include "mlir/IR/AffineMap.h"
#include "mlir/IR/IntegerSet.h"
#include "mlir/Support/TypeID.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/MathExtras.h"
#include <numeric>
#include <optional>

Functions
static bool	canSimplifyDivisionBySymbol (AffineExpr expr, unsigned symbolPos, AffineExprKind opKind, bool fromMul=false)
	Returns true if the expression is divisible by the given symbol with position `symbolPos`. More...

static AffineExpr	symbolicDivide (AffineExpr expr, unsigned symbolPos, AffineExprKind opKind)
	Divides the given expression by the given symbol at position `symbolPos`. More...

static void	getSummandExprs (AffineExpr expr, SmallVector< AffineExpr > &result)
	Populate `result` with all summand operands of given (potentially nested) addition. More...

static bool	isNegatedAffineExpr (AffineExpr candidate, AffineExpr &expr)
	Return "true" if `candidate` is a negated expression, i.e., Mul(-1, expr). More...

static bool	isModOfModSubtraction (AffineExpr lhs, AffineExpr rhs, unsigned numDims, unsigned numSymbols)
	Return "true" if `lhs` % `rhs` is guaranteed to evaluate to zero based on the fact that `lhs` contains another modulo expression that ensures that `lhs` is divisible by `rhs`. More...

static AffineExpr	simplifySemiAffine (AffineExpr expr, unsigned numDims, unsigned numSymbols)
	Simplify a semi-affine expression by handling modulo, floordiv, or ceildiv operations when the second operand simplifies to a symbol and the first operand is divisible by that symbol. More...

static AffineExpr	getAffineDimOrSymbol (AffineExprKind kind, unsigned position, MLIRContext *context)

static AffineExpr	simplifyAdd (AffineExpr lhs, AffineExpr rhs)
	Simplify add expression. Return nullptr if it can't be simplified. More...

static AffineExpr	simplifyMul (AffineExpr lhs, AffineExpr rhs)
	Simplify a multiply expression. Return nullptr if it can't be simplified. More...

static AffineExpr	simplifyFloorDiv (AffineExpr lhs, AffineExpr rhs)

static AffineExpr	simplifyCeilDiv (AffineExpr lhs, AffineExpr rhs)

static AffineExpr	simplifyMod (AffineExpr lhs, AffineExpr rhs)

static AffineExpr	getSemiAffineExprFromFlatForm (ArrayRef< int64_t > flatExprs, unsigned numDims, unsigned numSymbols, ArrayRef< AffineExpr > localExprs, MLIRContext *context)
	Constructs a semi-affine expression from a flat ArrayRef. More...

Function Documentation

◆ canSimplifyDivisionBySymbol()

static bool canSimplifyDivisionBySymbol	(	AffineExpr	expr,
		unsigned	symbolPos,
		AffineExprKind	opKind,
		bool	fromMul = `false`
	)

static

Returns true if the expression is divisible by the given symbol with position symbolPos.

The argument opKind specifies here what kind of division or mod operation called this division. It helps in implementing the commutative property of the floordiv and ceildiv operations. If the argument exprKind is floordiv and expr is also a binary expression of a floordiv operation, then the commutative property can be used otherwise, the floordiv operation is not divisible. The same argument holds for ceildiv operation.

Definition at line 359 of file AffineExpr.cpp.

References mlir::Add, mlir::CeilDiv, mlir::Constant, mlir::DimId, mlir::FloorDiv, mlir::AffineExpr::getKind(), mlir::AffineBinaryOpExpr::getLHS(), mlir::AffineBinaryOpExpr::getRHS(), mlir::Mod, mlir::Mul, and mlir::SymbolId.

Referenced by simplifySemiAffine(), and symbolicDivide().

◆ getAffineDimOrSymbol()

static AffineExpr getAffineDimOrSymbol	(	AffineExprKind	kind,
		unsigned	position,
		MLIRContext *	context
	)

static

Definition at line 606 of file AffineExpr.cpp.

References mlir::StorageUniquer::get(), and mlir::MLIRContext::getAffineUniquer().

Referenced by mlir::getAffineDimExpr(), and mlir::getAffineSymbolExpr().

◆ getSemiAffineExprFromFlatForm()

static AffineExpr getSemiAffineExprFromFlatForm	(	ArrayRef< int64_t >	flatExprs,
		unsigned	numDims,
		unsigned	numSymbols,
		ArrayRef< AffineExpr >	localExprs,
		MLIRContext *	context
	)

static

Constructs a semi-affine expression from a flat ArrayRef.

If there are local identifiers (neither dimensional nor symbolic) that appear in the sum of products expression, localExprs is expected to have the AffineExprs for it, and is substituted into. The ArrayRef flatExprs is expected to be in the format [dims, symbols, locals, constant term]. The semi-affine expression is constructed in the sorted order of dimension and symbol position numbers. Note: local expressions/ids are used for mod, div as well as symbolic RHS terms for terms that are not pure affine.

Definition at line 1091 of file AffineExpr.cpp.

References mlir::detail::enumerate(), mlir::getAffineConstantExpr(), mlir::getAffineDimExpr(), mlir::getAffineSymbolExpr(), and max().

Referenced by mlir::simplifyAffineExpr().

◆ getSummandExprs()

static void getSummandExprs	(	AffineExpr	expr,
		SmallVector< AffineExpr > &	result
	)

static

Populate result with all summand operands of given (potentially nested) addition.

If the given expression is not an addition, just populate the expression itself. Example: Add(Add(7, 8), Mul(9, 10)) will return [7, 8, Mul(9, 10)].

Definition at line 483 of file AffineExpr.cpp.

References mlir::Add.

Referenced by isModOfModSubtraction().

◆ isModOfModSubtraction()

static bool isModOfModSubtraction	(	AffineExpr	lhs,
		AffineExpr	rhs,
		unsigned	numDims,
		unsigned	numSymbols
	)

static

Return "true" if lhs % rhs is guaranteed to evaluate to zero based on the fact that lhs contains another modulo expression that ensures that lhs is divisible by rhs.

This is a common pattern in the resulting IR after loop peeling.

Example: lhs = ub - ub % step rhs = step => (ub - ub % step) % step is guaranteed to evaluate to 0.

Definition at line 522 of file AffineExpr.cpp.

References mlir::getAffineConstantExpr(), mlir::AffineExpr::getContext(), mlir::AffineExpr::getKind(), mlir::AffineBinaryOpExpr::getLHS(), mlir::AffineBinaryOpExpr::getRHS(), getSummandExprs(), isNegatedAffineExpr(), mlir::Mod, and mlir::simplifyAffineExpr().

Referenced by simplifySemiAffine().

◆ isNegatedAffineExpr()

static bool isNegatedAffineExpr	(	AffineExpr	candidate,
		AffineExpr &	expr
	)

static

Return "true" if candidate is a negated expression, i.e., Mul(-1, expr).

If so, also return the non-negated expression via expr.

Definition at line 495 of file AffineExpr.cpp.

References mlir::Mul.

Referenced by isModOfModSubtraction().

◆ simplifyAdd()

static AffineExpr simplifyAdd	(	AffineExpr	lhs,
		AffineExpr	rhs
	)

static

Simplify add expression. Return nullptr if it can't be simplified.

Definition at line 659 of file AffineExpr.cpp.

References mlir::Add, mlir::FloorDiv, mlir::getAffineBinaryOpExpr(), mlir::getAffineConstantExpr(), mlir::AffineExpr::getContext(), mlir::AffineExpr::getKind(), mlir::AffineBinaryOpExpr::getLHS(), mlir::AffineBinaryOpExpr::getRHS(), mlir::AffineConstantExpr::getValue(), mlir::AffineExpr::isSymbolicOrConstant(), and mlir::Mul.

Referenced by mlir::AffineExpr::operator+().

◆ simplifyCeilDiv()

static AffineExpr simplifyCeilDiv	(	AffineExpr	lhs,
		AffineExpr	rhs
	)

static

Definition at line 930 of file AffineExpr.cpp.

References mlir::getAffineConstantExpr(), mlir::AffineExpr::getContext(), and mlir::Mul.

Referenced by mlir::AffineExpr::ceilDiv().

◆ simplifyFloorDiv()

static AffineExpr simplifyFloorDiv	(	AffineExpr	lhs,
		AffineExpr	rhs
	)

static

Definition at line 871 of file AffineExpr.cpp.

References mlir::Add, mlir::getAffineConstantExpr(), mlir::AffineExpr::getContext(), and mlir::Mul.

Referenced by mlir::AffineExpr::floorDiv().

◆ simplifyMod()

static AffineExpr simplifyMod	(	AffineExpr	lhs,
		AffineExpr	rhs
	)

static

Definition at line 977 of file AffineExpr.cpp.

References mlir::Add, mlir::getAffineConstantExpr(), mlir::AffineExpr::getContext(), mlir::AffineExpr::getLargestKnownDivisor(), and mlir::Mod.

Referenced by mlir::AffineExpr::operator%().

◆ simplifyMul()

static AffineExpr simplifyMul	(	AffineExpr	lhs,
		AffineExpr	rhs
	)

static

Simplify a multiply expression. Return nullptr if it can't be simplified.

Definition at line 796 of file AffineExpr.cpp.

References mlir::getAffineConstantExpr(), mlir::AffineExpr::getContext(), mlir::AffineExpr::isSymbolicOrConstant(), mlir::Mul, and product().

Referenced by mlir::AffineExpr::operator*().

◆ simplifySemiAffine()

static AffineExpr simplifySemiAffine	(	AffineExpr	expr,
		unsigned	numDims,
		unsigned	numSymbols
	)

static

Simplify a semi-affine expression by handling modulo, floordiv, or ceildiv operations when the second operand simplifies to a symbol and the first operand is divisible by that symbol.

It can be applied to any semi-affine expression. Returned expression can either be a semi-affine or pure affine expression.

Definition at line 560 of file AffineExpr.cpp.

References mlir::Add, canSimplifyDivisionBySymbol(), mlir::CeilDiv, mlir::Constant, mlir::DimId, mlir::FloorDiv, mlir::getAffineBinaryOpExpr(), mlir::getAffineConstantExpr(), mlir::AffineExpr::getContext(), mlir::AffineExpr::getKind(), mlir::AffineBinaryOpExpr::getLHS(), mlir::AffineSymbolExpr::getPosition(), mlir::AffineBinaryOpExpr::getRHS(), isModOfModSubtraction(), mlir::Mod, mlir::Mul, symbolicDivide(), and mlir::SymbolId.

Referenced by mlir::simplifyAffineExpr().

◆ symbolicDivide()

static AffineExpr symbolicDivide	(	AffineExpr	expr,
		unsigned	symbolPos,
		AffineExprKind	opKind
	)

static

Divides the given expression by the given symbol at position symbolPos.

It considers the divisibility condition is checked before calling itself. A null expression is returned whenever the divisibility condition fails.

Definition at line 427 of file AffineExpr.cpp.

References mlir::Add, canSimplifyDivisionBySymbol(), mlir::CeilDiv, mlir::Constant, mlir::DimId, mlir::FloorDiv, mlir::getAffineBinaryOpExpr(), mlir::getAffineConstantExpr(), mlir::AffineExpr::getContext(), mlir::AffineExpr::getKind(), mlir::AffineBinaryOpExpr::getLHS(), mlir::AffineBinaryOpExpr::getRHS(), mlir::Mod, mlir::Mul, and mlir::SymbolId.

Referenced by simplifySemiAffine().

Functions

Function Documentation

◆ canSimplifyDivisionBySymbol()

◆ getAffineDimOrSymbol()

◆ getSemiAffineExprFromFlatForm()

◆ getSummandExprs()

◆ isModOfModSubtraction()

◆ isNegatedAffineExpr()

◆ simplifyAdd()

◆ simplifyCeilDiv()

◆ simplifyFloorDiv()

◆ simplifyMod()

◆ simplifyMul()

◆ simplifySemiAffine()

◆ symbolicDivide()