sets.h File Reference

Integer set operations for symbolic expressions. More...

#include <string>
#include <vector>
#include "sdfg/symbolic/assumptions.h"
#include "sdfg/symbolic/extreme_values.h"
#include "sdfg/symbolic/symbolic.h"

Go to the source code of this file.

Namespaces
namespace	sdfg
namespace	sdfg::symbolic

Functions
bool	sdfg::symbolic::is_subset (const MultiExpression &expr1, const MultiExpression &expr2, const Assumptions &assums1, const Assumptions &assums2)
	Interprets the expressions as integer sets and checks if expr1 is a subset of expr2.
bool	sdfg::symbolic::is_subset (const MultiExpression &expr1, const MultiExpression &expr2, AssumptionsBounds &bounds1, AssumptionsBounds &bounds2)
	Same as is_subset, but reuses caller-supplied AssumptionsBounds.
bool	sdfg::symbolic::is_disjoint (const MultiExpression &expr1, const MultiExpression &expr2, const Assumptions &assums1, const Assumptions &assums2)
	Interprets the expressions as integer sets and checks if expr1 is disjoint from expr2.
bool	sdfg::symbolic::is_disjoint (const MultiExpression &expr1, const MultiExpression &expr2, AssumptionsBounds &bounds1, AssumptionsBounds &bounds2)
	Same as is_disjoint, but reuses caller-supplied AssumptionsBounds.

Detailed Description

Integer set operations for symbolic expressions.

This file provides operations for interpreting symbolic expressions as integer sets and computing their relations. It integrates with the ISL (Integer Set Library) to perform set-theoretic operations on symbolic expressions.

Integer Set Operations

Symbolic expressions can be interpreted as sets of integer points.

The primary operations are:

• Subset checking: Determining if one set of accesses is contained within another
• Disjointness checking: Verifying that two sets of accesses don't overlap

These operations use assumptions about symbol bounds to compute precise set relations, which is critical for dependence analysis and optimization.

Example Usage

// Check if memory accesses A[i] and A[j] are disjoint when 0 <= i < 10 and 10 <= j < 20
auto i = symbolic::symbol("i");
auto j = symbolic::symbol("j");
 
MultiExpression expr1 = {i};  // Access pattern A[i]
MultiExpression expr2 = {j};  // Access pattern A[j]
 
Assumptions assums1, assums2;
assums1[i].add_lower_bound(symbolic::zero());
assums1[i].add_upper_bound(symbolic::integer(10));
assums2[j].add_lower_bound(symbolic::integer(11));
assums2[j].add_upper_bound(symbolic::integer(20));
 
bool disjoint = is_disjoint(expr1, expr2, assums1, assums2);  // true

See also

assumptions.h for information about symbol assumptions

utils.h for ISL integration utilities