Functions for transforming and analyzing expressions. More...

Functions
Expression	sdfg::symbolic::expand (const Expression expr)
	Expands an expression algebraically.
Expression	sdfg::symbolic::factor (const Expression expr)
	Factors an expression into a product of simpler terms.
Expression	sdfg::symbolic::simplify (const Expression expr)
	Simplifies an expression.
Expression	sdfg::symbolic::overapproximate (const Expression expr)
	Overapproximates an expression by resolving min/max to upper bounds.
bool	sdfg::symbolic::eq (const Expression lhs, const Expression rhs)
	Tests structural equality of two expressions.
bool	sdfg::symbolic::null_safe_eq (const Expression lhs, const Expression rhs)
	Tests equality of expressions with null-safety.
bool	sdfg::symbolic::uses (const Expression expr, const Symbol sym)
	Tests if an expression uses a specific symbol.
bool	sdfg::symbolic::uses (const Expression expr, const std::string &name)
	Tests if an expression uses a symbol with a specific name.
SymbolSet	sdfg::symbolic::atoms (const Expression expr)
	Extracts all symbols (atoms) from an expression.
template<typename T>
bool	sdfg::symbolic::has (const Expression expr)
	Checks if an expression contains a specific SymEngine type.
template<typename T>
ExpressionSet	sdfg::symbolic::find (const Expression expr)
	Finds all instances of a specific SymEngine type in an expression.
bool	sdfg::symbolic::has_dynamic_sizeof (const Expression expr)
	Checks if an expression contains a dynamic_sizeof operation.
ExpressionSet	sdfg::symbolic::muls (const Expression expr)
	Extracts all multiplication operations from an expression.
Expression	sdfg::symbolic::subs (const Expression expr, const Expression old_expr, const Expression new_expr)
	Substitutes a sub-expression with another expression.
Expression	sdfg::symbolic::subs (const Expression expr, const symbolic::ExpressionMapping &replacements)
	Bulk replacement.
Condition	sdfg::symbolic::subs (const Condition expr, const Expression old_expr, const Expression new_expr)
	Substitutes a sub-expression in a condition.
Condition	sdfg::symbolic::subs (const Condition expr, const symbolic::ExpressionMapping &replacements)
	Bulk replacement.
bool	sdfg::symbolic::substitute (ExpressionSet &set, const symbolic::ExpressionMapping &replacements)
MultiExpression	sdfg::symbolic::substitute (const MultiExpression &vec, const symbolic::ExpressionMapping &replacements)
Expression	sdfg::symbolic::inverse (const Expression expr, const Symbol symbol)
	Computes the inverse of an expression with respect to a symbol.

Detailed Description

Functions for transforming and analyzing expressions.

These functions provide utilities for expanding, simplifying, and analyzing symbolic expressions. They are essential for expression optimization and analysis.

Function Documentation

◆ atoms()

SymbolSet sdfg::symbolic::atoms ( const Expression expr )

Extracts all symbols (atoms) from an expression.

Parameters

expr	Expression to analyze

Returns: Set of all symbols appearing in the expression

◆ eq()

bool sdfg::symbolic::eq	(	const Expression	lhs,
		const Expression	rhs )

Tests structural equality of two expressions.

Parameters

lhs	First expression
rhs	Second expression

Returns: true if the expressions are structurally equal

◆ expand()

Expression sdfg::symbolic::expand ( const Expression expr )

Expands an expression algebraically.

Parameters

expr	Expression to expand

Returns: Expanded form of the expression

Performs algebraic expansion, such as distributing multiplications over additions.

◆ factor()

Expression sdfg::symbolic::factor ( const Expression expr )

Factors an expression into a product of simpler terms.

Parameters

expr	Expression to factor

Returns: Factored form of the expression

Attempts to factor polynomials by finding integer roots via trial division and detecting perfect squares. For example, x^2 - 4*x + 4 becomes (x - 2)^2. Recurses into Mul and Pow sub-expressions.

◆ find()

template<typename T>

ExpressionSet sdfg::symbolic::find ( const Expression expr )

inline

Finds all instances of a specific SymEngine type in an expression.

Template Parameters

T	SymEngine type to search for

Parameters

expr	Expression to search

Returns: Set of all sub-expressions of type T

◆ has()

template<typename T>

bool sdfg::symbolic::has ( const Expression expr )

inline

Checks if an expression contains a specific SymEngine type.

Template Parameters

T	SymEngine type to search for

Parameters

expr	Expression to search

Returns: true if expr contains an instance of type T

◆ has_dynamic_sizeof()

bool sdfg::symbolic::has_dynamic_sizeof ( const Expression expr )

Checks if an expression contains a dynamic_sizeof operation.

Parameters

expr	Expression to check

Returns: true if expr contains dynamic_sizeof

◆ inverse()

Expression sdfg::symbolic::inverse	(	const Expression	expr,
		const Symbol	symbol )

Computes the inverse of an expression with respect to a symbol.

Parameters

expr	Expression to invert
symbol	Symbol to solve for

Returns: Inverse expression, or null if inverse doesn't exist

For an expression y = f(x), computes x = f^(-1)(y).

◆ muls()

ExpressionSet sdfg::symbolic::muls ( const Expression expr )

Extracts all multiplication operations from an expression.

Parameters

expr	Expression to analyze

Returns: Set of multiplication sub-expressions

◆ null_safe_eq()

bool sdfg::symbolic::null_safe_eq	(	const Expression	lhs,
		const Expression	rhs )

Tests equality of expressions with null-safety.

Parameters

lhs	First expression (can be null)
rhs	Second expression (can be null)

Returns: true if expressions are equal; both null is considered equal

This is a null-safe version of eq() where both inputs being null is also considered equal.

◆ overapproximate()

Expression sdfg::symbolic::overapproximate ( const Expression expr )

Overapproximates an expression by resolving min/max to upper bounds.

Parameters

expr	Expression to overapproximate

Returns: An expression that is >= the original for all symbol valuations

Traverses the expression and replaces:

min(a, b) with the argument that has the larger constant offset (upper bound of min)
max(a, b) with the argument that has the larger constant offset (upper bound of max)

This is useful for computing conservative upper bounds on working set sizes, e.g. a tile extent of min(32, M - i_tile) overapproximates to 32.

◆ simplify()

Expression sdfg::symbolic::simplify ( const Expression expr )

Simplifies an expression.

Parameters

expr	Expression to simplify

Returns: Simplified form of the expression

Applies simplification rules to reduce the expression to a canonical form.

◆ subs() [1/4]

Condition sdfg::symbolic::subs	(	const Condition	expr,
		const Expression	old_expr,
		const Expression	new_expr )

Substitutes a sub-expression in a condition.

Parameters

expr	Condition to perform substitution in
old_expr	Sub-expression to replace
new_expr	Expression to substitute

Returns: New condition with substitution applied

◆ subs() [2/4]

Condition sdfg::symbolic::subs	(	const Condition	expr,
		const symbolic::ExpressionMapping &	replacements )

Bulk replacement.

◆ subs() [3/4]

Expression sdfg::symbolic::subs	(	const Expression	expr,
		const Expression	old_expr,
		const Expression	new_expr )

Substitutes a sub-expression with another expression.

Parameters

expr	Expression to perform substitution in
old_expr	Sub-expression to replace
new_expr	Expression to substitute

Returns: New expression with substitution applied

auto x = symbolic::symbol("x");
auto expr = symbolic::add(x, symbolic::integer(1));  // x + 1
auto result = symbolic::subs(expr, x, symbolic::integer(5));  // 5 + 1 = 6

◆ subs() [4/4]

Expression sdfg::symbolic::subs	(	const Expression	expr,
		const symbolic::ExpressionMapping &	replacements )

inline

Bulk replacement.

◆ substitute() [1/2]

MultiExpression sdfg::symbolic::substitute	(	const MultiExpression &	vec,
		const symbolic::ExpressionMapping &	replacements )

◆ substitute() [2/2]

bool sdfg::symbolic::substitute	(	ExpressionSet &	set,
		const symbolic::ExpressionMapping &	replacements )

◆ uses() [1/2]

bool sdfg::symbolic::uses	(	const Expression	expr,
		const std::string &	name )

Tests if an expression uses a symbol with a specific name.

Parameters

expr	Expression to search
name	Name of the symbol to look for

Returns: true if expr contains a symbol with the given name

◆ uses() [2/2]

bool sdfg::symbolic::uses	(	const Expression	expr,
		const Symbol	sym )

Tests if an expression uses a specific symbol.

Parameters

expr	Expression to search
sym	Symbol to look for

Returns: true if expr contains sym