C<isl_set_dim_has_upper_bound> have been renamed to
C<isl_set_dim_has_any_lower_bound> and
C<isl_set_dim_has_any_upper_bound>.
+The new C<isl_set_dim_has_lower_bound> and
+C<isl_set_dim_has_upper_bound> have slightly different meanings.
=back
=back
-=head1 Library
+=head1 Integer Set Library
=head2 Initialization
isl_ctx *isl_ctx_alloc();
void isl_ctx_free(isl_ctx *ctx);
-=head2 Integers
+=head2 Values
+
+An C<isl_val> represents an integer value, a rational value
+or one of three special values, infinity, negative infinity and NaN.
+Some predefined values can be created using the following functions.
+
+ #include <isl/val.h>
+ __isl_give isl_val *isl_val_zero(isl_ctx *ctx);
+ __isl_give isl_val *isl_val_one(isl_ctx *ctx);
+ __isl_give isl_val *isl_val_nan(isl_ctx *ctx);
+ __isl_give isl_val *isl_val_infty(isl_ctx *ctx);
+ __isl_give isl_val *isl_val_neginfty(isl_ctx *ctx);
+
+Specific integer values can be created using the following functions.
+
+ #include <isl/val.h>
+ __isl_give isl_val *isl_val_int_from_si(isl_ctx *ctx,
+ long i);
+ __isl_give isl_val *isl_val_int_from_ui(isl_ctx *ctx,
+ unsigned long u);
+
+They can be copied and freed using the following functions.
+
+ #include <isl/val.h>
+ __isl_give isl_val *isl_val_copy(__isl_keep isl_val *v);
+ void *isl_val_free(__isl_take isl_val *v);
+
+They can be inspected using the following functions.
+
+ #include <isl/val.h>
+ isl_ctx *isl_val_get_ctx(__isl_keep isl_val *val);
+ long isl_val_get_num_si(__isl_keep isl_val *v);
+ long isl_val_get_den_si(__isl_keep isl_val *v);
+ double isl_val_get_d(__isl_keep isl_val *v);
+
+Note that C<isl_val_get_num_si>, C<isl_val_get_den_si> and
+C<isl_val_get_d> can only be applied to rational values.
+
+An C<isl_val> can be modified using the following function.
+
+ #include <isl/val.h>
+ __isl_give isl_val *isl_val_set_si(__isl_take isl_val *v,
+ long i);
+
+The following unary properties are defined on C<isl_val>s.
+
+ #include <isl/val.h>
+ int isl_val_sgn(__isl_keep isl_val *v);
+ int isl_val_is_zero(__isl_keep isl_val *v);
+ int isl_val_is_one(__isl_keep isl_val *v);
+ int isl_val_is_negone(__isl_keep isl_val *v);
+ int isl_val_is_nonneg(__isl_keep isl_val *v);
+ int isl_val_is_nonpos(__isl_keep isl_val *v);
+ int isl_val_is_pos(__isl_keep isl_val *v);
+ int isl_val_is_neg(__isl_keep isl_val *v);
+ int isl_val_is_int(__isl_keep isl_val *v);
+ int isl_val_is_rat(__isl_keep isl_val *v);
+ int isl_val_is_nan(__isl_keep isl_val *v);
+ int isl_val_is_infty(__isl_keep isl_val *v);
+ int isl_val_is_neginfty(__isl_keep isl_val *v);
+
+Note that the sign of NaN is undefined.
+
+The following binary properties are defined on pairs of C<isl_val>s.
+
+ #include <isl/val.h>
+ int isl_val_lt(__isl_keep isl_val *v1,
+ __isl_keep isl_val *v2);
+ int isl_val_le(__isl_keep isl_val *v1,
+ __isl_keep isl_val *v2);
+ int isl_val_gt(__isl_keep isl_val *v1,
+ __isl_keep isl_val *v2);
+ int isl_val_ge(__isl_keep isl_val *v1,
+ __isl_keep isl_val *v2);
+ int isl_val_eq(__isl_keep isl_val *v1,
+ __isl_keep isl_val *v2);
+ int isl_val_ne(__isl_keep isl_val *v1,
+ __isl_keep isl_val *v2);
+
+For integer C<isl_val>s we additionally have the following binary property.
+
+ #include <isl/val.h>
+ int isl_val_is_divisible_by(__isl_keep isl_val *v1,
+ __isl_keep isl_val *v2);
+
+An C<isl_val> can also be compared to an integer using the following
+function. The result is undefined for NaN.
+
+ #include <isl/val.h>
+ int isl_val_cmp_si(__isl_keep isl_val *v, long i);
+
+The following unary operations are available on C<isl_val>s.
+
+ #include <isl/val.h>
+ __isl_give isl_val *isl_val_abs(__isl_take isl_val *v);
+ __isl_give isl_val *isl_val_neg(__isl_take isl_val *v);
+ __isl_give isl_val *isl_val_floor(__isl_take isl_val *v);
+ __isl_give isl_val *isl_val_ceil(__isl_take isl_val *v);
+ __isl_give isl_val *isl_val_trunc(__isl_take isl_val *v);
+
+The following binary operations are available on C<isl_val>s.
+
+ #include <isl/val.h>
+ __isl_give isl_val *isl_val_abs(__isl_take isl_val *v);
+ __isl_give isl_val *isl_val_neg(__isl_take isl_val *v);
+ __isl_give isl_val *isl_val_floor(__isl_take isl_val *v);
+ __isl_give isl_val *isl_val_ceil(__isl_take isl_val *v);
+ __isl_give isl_val *isl_val_trunc(__isl_take isl_val *v);
+ __isl_give isl_val *isl_val_2exp(__isl_take isl_val *v);
+ __isl_give isl_val *isl_val_min(__isl_take isl_val *v1,
+ __isl_take isl_val *v2);
+ __isl_give isl_val *isl_val_max(__isl_take isl_val *v1,
+ __isl_take isl_val *v2);
+ __isl_give isl_val *isl_val_add(__isl_take isl_val *v1,
+ __isl_take isl_val *v2);
+ __isl_give isl_val *isl_val_add_ui(__isl_take isl_val *v1,
+ unsigned long v2);
+ __isl_give isl_val *isl_val_sub(__isl_take isl_val *v1,
+ __isl_take isl_val *v2);
+ __isl_give isl_val *isl_val_sub_ui(__isl_take isl_val *v1,
+ unsigned long v2);
+ __isl_give isl_val *isl_val_mul(__isl_take isl_val *v1,
+ __isl_take isl_val *v2);
+ __isl_give isl_val *isl_val_mul_ui(__isl_take isl_val *v1,
+ unsigned long v2);
+ __isl_give isl_val *isl_val_div(__isl_take isl_val *v1,
+ __isl_take isl_val *v2);
+
+On integer values, we additionally have the following operations.
+
+ #include <isl/val.h>
+ __isl_give isl_val *isl_val_2exp(__isl_take isl_val *v);
+ __isl_give isl_val *isl_val_mod(__isl_take isl_val *v1,
+ __isl_take isl_val *v2);
+ __isl_give isl_val *isl_val_gcd(__isl_take isl_val *v1,
+ __isl_take isl_val *v2);
+ __isl_give isl_val *isl_val_gcdext(__isl_take isl_val *v1,
+ __isl_take isl_val *v2, __isl_give isl_val **x,
+ __isl_give isl_val **y);
+
+The function C<isl_val_gcdext> returns the greatest common divisor g
+of C<v1> and C<v2> as well as two integers C<*x> and C<*y> such
+that C<*x> * C<v1> + C<*y> * C<v2> = g.
+
+A value can be read from input using
+
+ #include <isl/val.h>
+ __isl_give isl_val *isl_val_read_from_str(isl_ctx *ctx,
+ const char *str);
+
+A value can be printed using
+
+ #include <isl/val.h>
+ __isl_give isl_printer *isl_printer_print_val(
+ __isl_take isl_printer *p, __isl_keep isl_val *v);
+
+=head3 GMP specific functions
+
+These functions are only available if C<isl> has been compiled with C<GMP>
+support.
+
+Specific integer and rational values can be created from C<GMP> values using
+the following functions.
+
+ #include <isl/val_gmp.h>
+ __isl_give isl_val *isl_val_int_from_gmp(isl_ctx *ctx,
+ mpz_t z);
+ __isl_give isl_val *isl_val_from_gmp(isl_ctx *ctx,
+ const mpz_t n, const mpz_t d);
+
+The numerator and denominator of a rational value can be extracted as
+C<GMP> values using the following functions.
+
+ #include <isl/val_gmp.h>
+ int isl_val_get_num_gmp(__isl_keep isl_val *v, mpz_t z);
+ int isl_val_get_den_gmp(__isl_keep isl_val *v, mpz_t z);
+
+=head2 Integers (obsolescent)
All operations on integers, mainly the coefficients
of the constraints describing the sets and relations,
#include <isl/id.h>
__isl_give isl_id *isl_id_alloc(isl_ctx *ctx,
__isl_keep const char *name, void *user);
+ __isl_give isl_id *isl_id_set_free_user(
+ __isl_take isl_id *id,
+ __isl_give void (*free_user)(void *user));
__isl_give isl_id *isl_id_copy(isl_id *id);
void *isl_id_free(__isl_take isl_id *id);
__isl_give isl_printer *isl_printer_print_id(
__isl_take isl_printer *p, __isl_keep isl_id *id);
+The callback set by C<isl_id_set_free_user> is called on the user
+pointer when the last reference to the C<isl_id> is freed.
Note that C<isl_id_get_name> returns a pointer to some internal
data structure, so the result can only be used while the
corresponding C<isl_id> is alive.
__isl_give isl_space *isl_union_pw_qpolynomial_fold_get_space(
__isl_keep isl_union_pw_qpolynomial_fold *upwf);
+ #include <isl/val.h>
+ __isl_give isl_space *isl_multi_val_get_space(
+ __isl_keep isl_multi_val *mv);
+
#include <isl/aff.h>
__isl_give isl_space *isl_aff_get_domain_space(
__isl_keep isl_aff *aff);
__isl_keep isl_local_space *ls);
void *isl_local_space_free(__isl_take isl_local_space *ls);
+Note that C<isl_local_space_get_div> can only be used on local spaces
+of sets.
+
Two local spaces can be compared using
int isl_local_space_is_equal(__isl_keep isl_local_space *ls1,
__isl_give isl_map *isl_map_from_union_map(
__isl_take isl_union_map *umap);
-A zero-dimensional set can be constructed on a given parameter domain
+A zero-dimensional (basic) set can be constructed on a given parameter domain
using the following function.
+ __isl_give isl_basic_set *isl_basic_set_from_params(
+ __isl_take isl_basic_set *bset);
__isl_give isl_set *isl_set_from_params(
__isl_take isl_set *set);
__isl_take isl_constraint *constraint, isl_int v);
__isl_give isl_constraint *isl_constraint_set_constant_si(
__isl_take isl_constraint *constraint, int v);
+ __isl_give isl_constraint *isl_constraint_set_constant_val(
+ __isl_take isl_constraint *constraint,
+ __isl_take isl_val *v);
__isl_give isl_constraint *isl_constraint_set_coefficient(
__isl_take isl_constraint *constraint,
enum isl_dim_type type, int pos, isl_int v);
__isl_give isl_constraint *isl_constraint_set_coefficient_si(
__isl_take isl_constraint *constraint,
enum isl_dim_type type, int pos, int v);
+ __isl_give isl_constraint *
+ isl_constraint_set_coefficient_val(
+ __isl_take isl_constraint *constraint,
+ enum isl_dim_type type, int pos, isl_val *v);
__isl_give isl_basic_map *isl_basic_map_add_constraint(
__isl_take isl_basic_map *bmap,
__isl_take isl_constraint *constraint);
enum isl_dim_type type, unsigned pos);
void isl_constraint_get_constant(
__isl_keep isl_constraint *constraint, isl_int *v);
+ __isl_give isl_val *isl_constraint_get_constant_val(
+ __isl_keep isl_constraint *constraint);
void isl_constraint_get_coefficient(
__isl_keep isl_constraint *constraint,
enum isl_dim_type type, int pos, isl_int *v);
+ __isl_give isl_val *isl_constraint_get_coefficient_val(
+ __isl_keep isl_constraint *constraint,
+ enum isl_dim_type type, int pos);
int isl_constraint_involves_dims(
__isl_keep isl_constraint *constraint,
enum isl_dim_type type, unsigned first, unsigned n);
int isl_set_dim_has_any_upper_bound(__isl_keep isl_set *set,
enum isl_dim_type type, unsigned pos);
+Note that these functions return true even if there is a bound on
+the dimension on only some of the basic sets of C<set>.
+To check if they have a bound for all of the basic sets in C<set>,
+use the following functions instead.
+
+ int isl_set_dim_has_lower_bound(__isl_keep isl_set *set,
+ enum isl_dim_type type, unsigned pos);
+ int isl_set_dim_has_upper_bound(__isl_keep isl_set *set,
+ enum isl_dim_type type, unsigned pos);
+
The identifiers or names of the domain and range spaces of a set
or relation can be read off or set using the following functions.
Check if the relation obviously lies on a hyperplane where the given dimension
has a fixed value and if so, return that value in C<*val>.
+ __isl_give isl_val *
+ isl_basic_map_plain_get_val_if_fixed(
+ __isl_keep isl_basic_map *bmap,
+ enum isl_dim_type type, unsigned pos);
+ __isl_give isl_val *isl_map_plain_get_val_if_fixed(
+ __isl_keep isl_map *map,
+ enum isl_dim_type type, unsigned pos);
+
+If the relation obviously lies on a hyperplane where the given dimension
+has a fixed value, then return that value.
+Otherwise return NaN.
+
=item * Space
To check whether a set is a parameter domain, use this function:
__isl_give isl_basic_set *isl_basic_set_fix_si(
__isl_take isl_basic_set *bset,
enum isl_dim_type type, unsigned pos, int value);
+ __isl_give isl_basic_set *isl_basic_set_fix_val(
+ __isl_take isl_basic_set *bset,
+ enum isl_dim_type type, unsigned pos,
+ __isl_take isl_val *v);
__isl_give isl_set *isl_set_fix(__isl_take isl_set *set,
enum isl_dim_type type, unsigned pos,
isl_int value);
__isl_give isl_set *isl_set_fix_si(__isl_take isl_set *set,
enum isl_dim_type type, unsigned pos, int value);
+ __isl_give isl_set *isl_set_fix_val(
+ __isl_take isl_set *set,
+ enum isl_dim_type type, unsigned pos,
+ __isl_take isl_val *v);
__isl_give isl_basic_map *isl_basic_map_fix_si(
__isl_take isl_basic_map *bmap,
enum isl_dim_type type, unsigned pos, int value);
+ __isl_give isl_basic_map *isl_basic_map_fix_val(
+ __isl_take isl_basic_map *bmap,
+ enum isl_dim_type type, unsigned pos,
+ __isl_take isl_val *v);
__isl_give isl_map *isl_map_fix(__isl_take isl_map *map,
enum isl_dim_type type, unsigned pos,
isl_int value);
__isl_give isl_map *isl_map_fix_si(__isl_take isl_map *map,
enum isl_dim_type type, unsigned pos, int value);
+ __isl_give isl_map *isl_map_fix_val(
+ __isl_take isl_map *map,
+ enum isl_dim_type type, unsigned pos,
+ __isl_take isl_val *v);
Intersect the set or relation with the hyperplane where the given
dimension has the fixed given value.
__isl_give isl_set *isl_set_lower_bound_si(
__isl_take isl_set *set,
enum isl_dim_type type, unsigned pos, int value);
+ __isl_give isl_set *isl_set_lower_bound_val(
+ __isl_take isl_set *set,
+ enum isl_dim_type type, unsigned pos,
+ __isl_take isl_val *value);
__isl_give isl_map *isl_map_lower_bound_si(
__isl_take isl_map *map,
enum isl_dim_type type, unsigned pos, int value);
__isl_give isl_set *isl_set_upper_bound_si(
__isl_take isl_set *set,
enum isl_dim_type type, unsigned pos, int value);
+ __isl_give isl_set *isl_set_upper_bound_val(
+ __isl_take isl_set *set,
+ enum isl_dim_type type, unsigned pos,
+ __isl_take isl_val *value);
__isl_give isl_map *isl_map_upper_bound_si(
__isl_take isl_map *map,
enum isl_dim_type type, unsigned pos, int value);
Intersect the set or relation with the half-space where the given
-dimension has a value bounded by the fixed given value.
+dimension has a value bounded by the fixed given integer value.
__isl_give isl_set *isl_set_equate(__isl_take isl_set *set,
enum isl_dim_type type1, int pos1,
__isl_give isl_map *isl_map_order_lt(__isl_take isl_map *map,
enum isl_dim_type type1, int pos1,
enum isl_dim_type type2, int pos2);
+ __isl_give isl_basic_map *isl_basic_map_order_gt(
+ __isl_take isl_basic_map *bmap,
+ enum isl_dim_type type1, int pos1,
+ enum isl_dim_type type2, int pos2);
__isl_give isl_map *isl_map_order_gt(__isl_take isl_map *map,
enum isl_dim_type type1, int pos1,
enum isl_dim_type type2, int pos2);
__isl_take isl_basic_set *bset,
enum isl_dim_type type,
unsigned first, unsigned n);
+ __isl_give isl_basic_map *
+ isl_basic_map_drop_constraints_involving_dims(
+ __isl_take isl_basic_map *bmap,
+ enum isl_dim_type type,
+ unsigned first, unsigned n);
__isl_give isl_basic_set *
isl_basic_set_drop_constraints_not_involving_dims(
__isl_take isl_basic_set *bset,
enum isl_lp_result isl_basic_set_max(
__isl_keep isl_basic_set *bset,
__isl_keep isl_aff *obj, isl_int *opt)
+ __isl_give isl_val *isl_basic_set_max_val(
+ __isl_keep isl_basic_set *bset,
+ __isl_keep isl_aff *obj);
enum isl_lp_result isl_set_min(__isl_keep isl_set *set,
__isl_keep isl_aff *obj, isl_int *opt);
+ __isl_give isl_val *isl_set_min_val(
+ __isl_keep isl_set *set,
+ __isl_keep isl_aff *obj);
enum isl_lp_result isl_set_max(__isl_keep isl_set *set,
__isl_keep isl_aff *obj, isl_int *opt);
+ __isl_give isl_val *isl_set_max_val(
+ __isl_keep isl_set *set,
+ __isl_keep isl_aff *obj);
Compute the minimum or maximum of the integer affine expression C<obj>
over the points in C<set>, returning the result in C<opt>.
The return value may be one of C<isl_lp_error>,
-C<isl_lp_ok>, C<isl_lp_unbounded> or C<isl_lp_empty>.
+C<isl_lp_ok>, C<isl_lp_unbounded> or C<isl_lp_empty>, in case of
+an C<isl_lp_result>. If the result is an C<isl_val> then
+the result is C<NULL> in case of an error, the optimal value in case
+there is one, negative infinity or infinity if the problem is unbounded and
+NaN if the problem is empty.
=item * Parametric optimization
__isl_take isl_map *map);
__isl_give isl_union_map *isl_union_map_curry(
__isl_take isl_union_map *umap);
+ __isl_give isl_union_map *isl_union_map_uncurry(
+ __isl_take isl_union_map *umap);
Given a relation with a nested relation for domain,
the C<curry> functions
=item * Dimension manipulation
+ __isl_give isl_basic_set *isl_basic_set_add_dims(
+ __isl_take isl_basic_set *bset,
+ enum isl_dim_type type, unsigned n);
__isl_give isl_set *isl_set_add_dims(
__isl_take isl_set *set,
enum isl_dim_type type, unsigned n);
isl_basic_set_preimage_multi_aff(
__isl_take isl_basic_set *bset,
__isl_take isl_multi_aff *ma);
+ __isl_give isl_set *isl_set_preimage_multi_aff(
+ __isl_take isl_set *set,
+ __isl_take isl_multi_aff *ma);
+ __isl_give isl_set *isl_set_preimage_pw_multi_aff(
+ __isl_take isl_set *set,
+ __isl_take isl_pw_multi_aff *pma);
+ __isl_give isl_map *isl_map_preimage_domain_multi_aff(
+ __isl_take isl_map *map,
+ __isl_take isl_multi_aff *ma);
+ __isl_give isl_union_map *
+ isl_union_map_preimage_domain_multi_aff(
+ __isl_take isl_union_map *umap,
+ __isl_take isl_multi_aff *ma);
-This function computes the preimage of the given set under
+These functions compute the preimage of the given set or map domain under
the given function. In other words, the expression is plugged
-into the set description.
-Objects of type C<isl_multi_aff> are described in
+into the set description or into the domain of the map.
+Objects of types C<isl_multi_aff> and C<isl_pw_multi_aff> are described in
L</"Piecewise Multiple Quasi Affine Expressions">.
=item * Cartesian Product
__isl_take isl_basic_map *bmap,
__isl_take isl_basic_set *dom,
__isl_give isl_set **empty);
+ __isl_give isl_pw_multi_aff *isl_set_lexmin_pw_multi_aff(
+ __isl_take isl_set *set);
+ __isl_give isl_pw_multi_aff *isl_set_lexmax_pw_multi_aff(
+ __isl_take isl_set *set);
__isl_give isl_pw_multi_aff *isl_map_lexmin_pw_multi_aff(
__isl_take isl_map *map);
__isl_give isl_pw_multi_aff *isl_map_lexmax_pw_multi_aff(
=head2 Lists
Lists are defined over several element types, including
-C<isl_id>, C<isl_aff>, C<isl_pw_aff>, C<isl_constraint>,
-C<isl_basic_set> and C<isl_set>.
+C<isl_val>, C<isl_id>, C<isl_aff>, C<isl_pw_aff>, C<isl_constraint>,
+C<isl_basic_set>, C<isl_set>, C<isl_ast_expr> and C<isl_ast_node>.
Here we take lists of C<isl_set>s as an example.
Lists can be created, copied, modified and freed using the following functions.
__isl_give isl_set_list *isl_set_list_concat(
__isl_take isl_set_list *list1,
__isl_take isl_set_list *list2);
+ __isl_give isl_set_list *isl_set_list_sort(
+ __isl_take isl_set_list *list,
+ int (*cmp)(__isl_keep isl_set *a,
+ __isl_keep isl_set *b, void *user),
+ void *user);
void *isl_set_list_free(__isl_take isl_set_list *list);
C<isl_set_list_alloc> creates an empty list with a capacity for
int isl_set_list_foreach(__isl_keep isl_set_list *list,
int (*fn)(__isl_take isl_set *el, void *user),
void *user);
+ int isl_set_list_foreach_scc(__isl_keep isl_set_list *list,
+ int (*follows)(__isl_keep isl_set *a,
+ __isl_keep isl_set *b, void *user),
+ void *follows_user
+ int (*fn)(__isl_take isl_set *el, void *user),
+ void *fn_user);
+
+The function C<isl_set_list_foreach_scc> calls C<fn> on each of the
+strongly connected components of the graph with as vertices the elements
+of C<list> and a directed edge from vertex C<b> to vertex C<a>
+iff C<follows(a, b)> returns C<1>. The callbacks C<follows> and C<fn>
+should return C<-1> on error.
Lists can be printed using
__isl_take isl_printer *p,
__isl_keep isl_set_list *list);
+=head2 Multiple Values
+
+An C<isl_multi_val> object represents a sequence of zero or more values,
+living in a set space.
+
+An C<isl_multi_val> can be constructed from an C<isl_val_list>
+using the following function
+
+ #include <isl/val.h>
+ __isl_give isl_multi_val *isl_multi_val_from_val_list(
+ __isl_take isl_space *space,
+ __isl_take isl_val_list *list);
+
+The zero multiple value (with value zero for each set dimension)
+can be created using the following function.
+
+ #include <isl/val.h>
+ __isl_give isl_multi_val *isl_multi_val_zero(
+ __isl_take isl_space *space);
+
+Multiple values can be copied and freed using
+
+ #include <isl/val.h>
+ __isl_give isl_multi_val *isl_multi_val_copy(
+ __isl_keep isl_multi_val *mv);
+ void *isl_multi_val_free(__isl_take isl_multi_val *mv);
+
+They can be inspected using
+
+ #include <isl/val.h>
+ isl_ctx *isl_multi_val_get_ctx(
+ __isl_keep isl_multi_val *mv);
+ unsigned isl_multi_val_dim(__isl_keep isl_multi_val *mv,
+ enum isl_dim_type type);
+ __isl_give isl_val *isl_multi_val_get_val(
+ __isl_keep isl_multi_val *mv, int pos);
+ const char *isl_multi_val_get_tuple_name(
+ __isl_keep isl_multi_val *mv,
+ enum isl_dim_type type);
+
+They can be modified using
+
+ #include <isl/val.h>
+ __isl_give isl_multi_val *isl_multi_val_set_val(
+ __isl_take isl_multi_val *mv, int pos,
+ __isl_take isl_val *val);
+ __isl_give isl_multi_val *isl_multi_val_set_dim_name(
+ __isl_take isl_multi_val *mv,
+ enum isl_dim_type type, unsigned pos, const char *s);
+ __isl_give isl_multi_val *isl_multi_val_set_tuple_name(
+ __isl_take isl_multi_val *mv,
+ enum isl_dim_type type, const char *s);
+ __isl_give isl_multi_val *isl_multi_val_set_tuple_id(
+ __isl_take isl_multi_val *mv,
+ enum isl_dim_type type, __isl_take isl_id *id);
+
+ __isl_give isl_multi_val *isl_multi_val_insert_dims(
+ __isl_take isl_multi_val *mv,
+ enum isl_dim_type type, unsigned first, unsigned n);
+ __isl_give isl_multi_val *isl_multi_val_add_dims(
+ __isl_take isl_multi_val *mv,
+ enum isl_dim_type type, unsigned n);
+ __isl_give isl_multi_val *isl_multi_val_drop_dims(
+ __isl_take isl_multi_val *mv,
+ enum isl_dim_type type, unsigned first, unsigned n);
+
+Operations include
+
+ #include <isl/val.h>
+ __isl_give isl_multi_val *isl_multi_val_align_params(
+ __isl_take isl_multi_val *mv,
+ __isl_take isl_space *model);
+ __isl_give isl_multi_val *isl_multi_val_range_splice(
+ __isl_take isl_multi_val *mv1, unsigned pos,
+ __isl_take isl_multi_val *mv2);
+ __isl_give isl_multi_val *isl_multi_val_range_product(
+ __isl_take isl_multi_val *mv1,
+ __isl_take isl_multi_val *mv2);
+ __isl_give isl_multi_val *isl_multi_val_flat_range_product(
+ __isl_take isl_multi_val *mv1,
+ __isl_take isl_multi_aff *mv2);
+ __isl_give isl_multi_val *isl_multi_val_add_val(
+ __isl_take isl_multi_val *mv,
+ __isl_take isl_val *v);
+ __isl_give isl_multi_val *isl_multi_val_mod_val(
+ __isl_take isl_multi_val *mv,
+ __isl_take isl_val *v);
+ __isl_give isl_multi_val *isl_multi_val_scale_val(
+ __isl_take isl_multi_val *mv,
+ __isl_take isl_val *v);
+
=head2 Vectors
Vectors can be created, copied and freed using the following functions.
int isl_vec_size(__isl_keep isl_vec *vec);
int isl_vec_get_element(__isl_keep isl_vec *vec,
int pos, isl_int *v);
+ __isl_give isl_val *isl_vec_get_element_val(
+ __isl_keep isl_vec *vec, int pos);
__isl_give isl_vec *isl_vec_set_element(
__isl_take isl_vec *vec, int pos, isl_int v);
__isl_give isl_vec *isl_vec_set_element_si(
__isl_take isl_vec *vec, int pos, int v);
+ __isl_give isl_vec *isl_vec_set_element_val(
+ __isl_take isl_vec *vec, int pos,
+ __isl_take isl_val *v);
__isl_give isl_vec *isl_vec_set(__isl_take isl_vec *vec,
isl_int v);
__isl_give isl_vec *isl_vec_set_si(__isl_take isl_vec *vec,
int v);
+ __isl_give isl_vec *isl_vec_set_val(
+ __isl_take isl_vec *vec, __isl_take isl_val *v);
__isl_give isl_vec *isl_vec_fdiv_r(__isl_take isl_vec *vec,
isl_int m);
__isl_give isl_mat *isl_mat_alloc(isl_ctx *ctx,
unsigned n_row, unsigned n_col);
__isl_give isl_mat *isl_mat_copy(__isl_keep isl_mat *mat);
- void isl_mat_free(__isl_take isl_mat *mat);
+ void *isl_mat_free(__isl_take isl_mat *mat);
Note that the elements of a newly created matrix may have arbitrary values.
The elements can be changed and inspected using the following functions.
int isl_mat_cols(__isl_keep isl_mat *mat);
int isl_mat_get_element(__isl_keep isl_mat *mat,
int row, int col, isl_int *v);
+ __isl_give isl_val *isl_mat_get_element_val(
+ __isl_keep isl_mat *mat, int row, int col);
__isl_give isl_mat *isl_mat_set_element(__isl_take isl_mat *mat,
int row, int col, isl_int v);
__isl_give isl_mat *isl_mat_set_element_si(__isl_take isl_mat *mat,
int row, int col, int v);
+ __isl_give isl_mat *isl_mat_set_element_val(
+ __isl_take isl_mat *mat, int row, int col,
+ __isl_take isl_val *v);
C<isl_mat_get_element> will return a negative value if anything went wrong.
In that case, the value of C<*v> is undefined.
enum isl_dim_type type);
int isl_aff_get_constant(__isl_keep isl_aff *aff,
isl_int *v);
+ __isl_give isl_val *isl_aff_get_constant_val(
+ __isl_keep isl_aff *aff);
int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
enum isl_dim_type type, int pos, isl_int *v);
+ __isl_give isl_val *isl_aff_get_coefficient_val(
+ __isl_keep isl_aff *aff,
+ enum isl_dim_type type, int pos);
int isl_aff_get_denominator(__isl_keep isl_aff *aff,
isl_int *v);
+ __isl_give isl_val *isl_aff_get_denominator_val(
+ __isl_keep isl_aff *aff);
__isl_give isl_aff *isl_aff_get_div(
__isl_keep isl_aff *aff, int pos);
__isl_take isl_aff *aff, isl_int v);
__isl_give isl_aff *isl_aff_set_constant_si(
__isl_take isl_aff *aff, int v);
+ __isl_give isl_aff *isl_aff_set_constant_val(
+ __isl_take isl_aff *aff, __isl_take isl_val *v);
__isl_give isl_aff *isl_aff_set_coefficient(
__isl_take isl_aff *aff,
enum isl_dim_type type, int pos, isl_int v);
__isl_give isl_aff *isl_aff_set_coefficient_si(
__isl_take isl_aff *aff,
enum isl_dim_type type, int pos, int v);
+ __isl_give isl_aff *isl_aff_set_coefficient_val(
+ __isl_take isl_aff *aff,
+ enum isl_dim_type type, int pos,
+ __isl_take isl_val *v);
__isl_give isl_aff *isl_aff_set_denominator(
__isl_take isl_aff *aff, isl_int v);
__isl_take isl_aff *aff, isl_int v);
__isl_give isl_aff *isl_aff_add_constant_si(
__isl_take isl_aff *aff, int v);
+ __isl_give isl_aff *isl_aff_add_constant_val(
+ __isl_take isl_aff *aff, __isl_take isl_val *v);
__isl_give isl_aff *isl_aff_add_constant_num(
__isl_take isl_aff *aff, isl_int v);
__isl_give isl_aff *isl_aff_add_constant_num_si(
__isl_give isl_aff *isl_aff_add_coefficient_si(
__isl_take isl_aff *aff,
enum isl_dim_type type, int pos, int v);
+ __isl_give isl_aff *isl_aff_add_coefficient_val(
+ __isl_take isl_aff *aff,
+ enum isl_dim_type type, int pos,
+ __isl_take isl_val *v);
__isl_give isl_aff *isl_aff_insert_dims(
__isl_take isl_aff *aff,
__isl_take isl_pw_aff *pwaff,
enum isl_dim_type type, unsigned first, unsigned n);
-Note that the C<set_constant> and C<set_coefficient> functions
+Note that C<isl_aff_set_constant>, C<isl_aff_set_constant_si>,
+C<isl_aff_set_coefficient> and C<isl_aff_set_coefficient_si>
set the I<numerator> of the constant or coefficient, while
-C<add_constant> and C<add_coefficient> add an integer value to
+C<isl_aff_set_constant_val> and C<isl_aff_set_coefficient_val> set
+the constant or coefficient as a whole.
+The C<add_constant> and C<add_coefficient> functions add an integer
+or rational value to
the possibly rational constant or coefficient.
The C<add_constant_num> functions add an integer value to
the numerator.
__isl_take isl_pw_aff *pwaff);
__isl_give isl_aff *isl_aff_mod(__isl_take isl_aff *aff,
isl_int mod);
+ __isl_give isl_aff *isl_aff_mod_val(__isl_take isl_aff *aff,
+ __isl_take isl_val *mod);
__isl_give isl_pw_aff *isl_pw_aff_mod(
__isl_take isl_pw_aff *pwaff, isl_int mod);
+ __isl_give isl_pw_aff *isl_pw_aff_mod_val(
+ __isl_take isl_pw_aff *pa,
+ __isl_take isl_val *mod);
__isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff,
isl_int f);
+ __isl_give isl_aff *isl_aff_scale_val(__isl_take isl_aff *aff,
+ __isl_take isl_val *v);
__isl_give isl_pw_aff *isl_pw_aff_scale(
__isl_take isl_pw_aff *pwaff, isl_int f);
+ __isl_give isl_pw_aff *isl_pw_aff_scale_val(
+ __isl_take isl_pw_aff *pa, __isl_take isl_val *v);
__isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff,
isl_int f);
__isl_give isl_aff *isl_aff_scale_down_ui(
__isl_take isl_aff *aff, unsigned f);
+ __isl_give isl_aff *isl_aff_scale_down_val(
+ __isl_take isl_aff *aff, __isl_take isl_val *v);
__isl_give isl_pw_aff *isl_pw_aff_scale_down(
__isl_take isl_pw_aff *pwaff, isl_int f);
+ __isl_give isl_pw_aff *isl_pw_aff_scale_down_val(
+ __isl_take isl_pw_aff *pa,
+ __isl_take isl_val *f);
__isl_give isl_pw_aff *isl_pw_aff_list_min(
__isl_take isl_pw_aff_list *list);
remainder.
#include <isl/aff.h>
+ __isl_give isl_aff *isl_aff_pullback_multi_aff(
+ __isl_take isl_aff *aff,
+ __isl_take isl_multi_aff *ma);
+ __isl_give isl_pw_aff *isl_pw_aff_pullback_multi_aff(
+ __isl_take isl_pw_aff *pa,
+ __isl_take isl_multi_aff *ma);
+ __isl_give isl_pw_aff *isl_pw_aff_pullback_pw_multi_aff(
+ __isl_take isl_pw_aff *pa,
+ __isl_take isl_pw_multi_aff *pma);
+
+These functions precompose the input expression by the given
+C<isl_multi_aff> or C<isl_pw_multi_aff>. In other words,
+the C<isl_multi_aff> or C<isl_pw_multi_aff> is plugged
+into the (piecewise) affine expression.
+Objects of type C<isl_multi_aff> are described in
+L</"Piecewise Multiple Quasi Affine Expressions">.
+
+ #include <isl/aff.h>
__isl_give isl_basic_set *isl_aff_zero_basic_set(
__isl_take isl_aff *aff);
__isl_give isl_basic_set *isl_aff_neg_basic_set(
A piecewise multiple quasi affine expression can also be initialized
from an C<isl_set> or C<isl_map>, provided the C<isl_set> is a singleton
and the C<isl_map> is single-valued.
+In case of a conversion from an C<isl_union_set> or an C<isl_union_map>
+to an C<isl_union_pw_multi_aff>, these properties need to hold in each space.
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_set(
__isl_take isl_set *set);
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_map(
__isl_take isl_map *map);
+ __isl_give isl_union_pw_multi_aff *
+ isl_union_pw_multi_aff_from_union_set(
+ __isl_take isl_union_set *uset);
+ __isl_give isl_union_pw_multi_aff *
+ isl_union_pw_multi_aff_from_union_map(
+ __isl_take isl_union_map *umap);
+
Multiple quasi affine expressions can be copied and freed using
#include <isl/aff.h>
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_add(
__isl_take isl_pw_multi_aff *pma1,
__isl_take isl_pw_multi_aff *pma2);
+ __isl_give isl_multi_aff *isl_multi_aff_sub(
+ __isl_take isl_multi_aff *ma1,
+ __isl_take isl_multi_aff *ma2);
+ __isl_give isl_pw_multi_aff *isl_pw_multi_aff_sub(
+ __isl_take isl_pw_multi_aff *pma1,
+ __isl_take isl_pw_multi_aff *pma2);
+ __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_sub(
+ __isl_take isl_union_pw_multi_aff *upma1,
+ __isl_take isl_union_pw_multi_aff *upma2);
+
+C<isl_multi_aff_sub> subtracts the second argument from the first.
+
__isl_give isl_multi_aff *isl_multi_aff_scale(
__isl_take isl_multi_aff *maff,
isl_int f);
+ __isl_give isl_multi_aff *isl_multi_aff_scale_val(
+ __isl_take isl_multi_aff *ma,
+ __isl_take isl_val *v);
+ __isl_give isl_pw_multi_aff *isl_pw_multi_aff_scale_val(
+ __isl_take isl_pw_multi_aff *pma,
+ __isl_take isl_val *v);
+ __isl_give isl_multi_pw_aff *isl_multi_pw_aff_scale_val(
+ __isl_take isl_multi_pw_aff *mpa,
+ __isl_take isl_val *v);
+ __isl_give isl_multi_aff *isl_multi_aff_scale_vec(
+ __isl_take isl_multi_aff *ma,
+ __isl_take isl_vec *v);
+ __isl_give isl_pw_multi_aff *isl_pw_multi_aff_scale_vec(
+ __isl_take isl_pw_multi_aff *pma,
+ __isl_take isl_vec *v);
+ __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_scale_vec(
+ __isl_take isl_union_pw_multi_aff *upma,
+ __isl_take isl_vec *v);
+
+C<isl_multi_aff_scale_vec> scales the first elements of C<ma>
+by the corresponding elements of C<v>.
+
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_intersect_params(
__isl_take isl_pw_multi_aff *pma,
__isl_take isl_set *set);
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_intersect_domain(
__isl_take isl_pw_multi_aff *pma,
__isl_take isl_set *set);
+ __isl_give isl_union_pw_multi_aff *
+ isl_union_pw_multi_aff_intersect_domain(
+ __isl_take isl_union_pw_multi_aff *upma,
+ __isl_take isl_union_set *uset);
__isl_give isl_multi_aff *isl_multi_aff_lift(
__isl_take isl_multi_aff *maff,
__isl_give isl_local_space **ls);
then it is assigned the local space that lies at the basis of
the lifting applied.
+ #include <isl/aff.h>
+ __isl_give isl_multi_aff *isl_multi_aff_pullback_multi_aff(
+ __isl_take isl_multi_aff *ma1,
+ __isl_take isl_multi_aff *ma2);
+ __isl_give isl_pw_multi_aff *
+ isl_pw_multi_aff_pullback_multi_aff(
+ __isl_take isl_pw_multi_aff *pma,
+ __isl_take isl_multi_aff *ma);
+ __isl_give isl_pw_multi_aff *
+ isl_pw_multi_aff_pullback_pw_multi_aff(
+ __isl_take isl_pw_multi_aff *pma1,
+ __isl_take isl_pw_multi_aff *pma2);
+
+The function C<isl_multi_aff_pullback_multi_aff> precomposes C<ma1> by C<ma2>.
+In other words, C<ma2> is plugged
+into C<ma1>.
+
__isl_give isl_set *isl_multi_aff_lex_le_set(
__isl_take isl_multi_aff *ma1,
__isl_take isl_multi_aff *ma2);
isl_ctx *ctx, const char *str);
__isl_give isl_pw_multi_aff *isl_pw_multi_aff_read_from_str(
isl_ctx *ctx, const char *str);
+ __isl_give isl_union_pw_multi_aff *
+ isl_union_pw_multi_aff_read_from_str(
+ isl_ctx *ctx, const char *str);
An expression can be printed using
int isl_point_get_coordinate(__isl_keep isl_point *pnt,
enum isl_dim_type type, int pos, isl_int *v);
+ __isl_give isl_val *isl_point_get_coordinate_val(
+ __isl_keep isl_point *pnt,
+ enum isl_dim_type type, int pos);
__isl_give isl_point *isl_point_set_coordinate(
__isl_take isl_point *pnt,
enum isl_dim_type type, int pos, isl_int v);
+ __isl_give isl_point *isl_point_set_coordinate_val(
+ __isl_take isl_point *pnt,
+ enum isl_dim_type type, int pos,
+ __isl_take isl_val *v);
__isl_give isl_point *isl_point_add_ui(
__isl_take isl_point *pnt,
__isl_give isl_qpolynomial *isl_qpolynomial_rat_cst_on_domain(
__isl_take isl_space *domain,
const isl_int n, const isl_int d);
+ __isl_give isl_qpolynomial *isl_qpolynomial_val_on_domain(
+ __isl_take isl_space *domain,
+ __isl_take isl_val *val);
__isl_give isl_qpolynomial *isl_qpolynomial_var_on_domain(
__isl_take isl_space *domain,
enum isl_dim_type type, unsigned pos);
the dimensions of the sets may be different for different
invocations of C<fn>.
+The constant term of a quasipolynomial can be extracted using
+
+ __isl_give isl_val *isl_qpolynomial_get_constant_val(
+ __isl_keep isl_qpolynomial *qp);
+
To iterate over all terms in a quasipolynomial,
use
isl_int *n);
void isl_term_get_den(__isl_keep isl_term *term,
isl_int *d);
+ __isl_give isl_val *isl_term_get_coefficient_val(
+ __isl_keep isl_term *term);
int isl_term_get_exp(__isl_keep isl_term *term,
enum isl_dim_type type, unsigned pos);
__isl_give isl_aff *isl_term_get_div(
__isl_give isl_qpolynomial *isl_qpolynomial_scale(
__isl_take isl_qpolynomial *qp, isl_int v);
+ __isl_give isl_qpolynomial *isl_qpolynomial_scale_val(
+ __isl_take isl_qpolynomial *qp,
+ __isl_take isl_val *v);
__isl_give isl_qpolynomial *isl_qpolynomial_neg(
__isl_take isl_qpolynomial *qp);
__isl_give isl_qpolynomial *isl_qpolynomial_add(
__isl_give isl_qpolynomial *isl_qpolynomial_pow(
__isl_take isl_qpolynomial *qp, unsigned exponent);
+ __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_fix_val(
+ __isl_take isl_pw_qpolynomial *pwqp,
+ enum isl_dim_type type, unsigned n,
+ __isl_take isl_val *v);
+ __isl_give isl_pw_qpolynomial *
+ isl_pw_qpolynomial_scale_val(
+ __isl_take isl_pw_qpolynomial *pwqp,
+ __isl_take isl_val *v);
__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_add(
__isl_take isl_pw_qpolynomial *pwqp1,
__isl_take isl_pw_qpolynomial *pwqp2);
__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_pow(
__isl_take isl_pw_qpolynomial *pwqp, unsigned exponent);
+ __isl_give isl_union_pw_qpolynomial *
+ isl_union_pw_qpolynomial_scale_val(
+ __isl_take isl_union_pw_qpolynomial *upwqp,
+ __isl_take isl_val *v);
__isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_add(
__isl_take isl_union_pw_qpolynomial *upwqp1,
__isl_take isl_union_pw_qpolynomial *upwqp2);
__isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale(
__isl_take isl_qpolynomial_fold *fold, isl_int v);
+ __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_scale_val(
+ __isl_take isl_qpolynomial_fold *fold,
+ __isl_take isl_val *v);
+ __isl_give isl_pw_qpolynomial_fold *
+ isl_pw_qpolynomial_fold_scale_val(
+ __isl_take isl_pw_qpolynomial_fold *pwf,
+ __isl_take isl_val *v);
+ __isl_give isl_union_pw_qpolynomial_fold *
+ isl_union_pw_qpolynomial_fold_scale_val(
+ __isl_take isl_union_pw_qpolynomial_fold *upwf,
+ __isl_take isl_val *v);
__isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_add(
__isl_take isl_pw_qpolynomial_fold *pwf1,
intersection of the set and the domain of the
piecewise quasipolynomial reduction.
+=head2 Parametric Vertex Enumeration
+
+The parametric vertex enumeration described in this section
+is mainly intended to be used internally and by the C<barvinok>
+library.
+
+ #include <isl/vertices.h>
+ __isl_give isl_vertices *isl_basic_set_compute_vertices(
+ __isl_keep isl_basic_set *bset);
+
+The function C<isl_basic_set_compute_vertices> performs the
+actual computation of the parametric vertices and the chamber
+decomposition and store the result in an C<isl_vertices> object.
+This information can be queried by either iterating over all
+the vertices or iterating over all the chambers or cells
+and then iterating over all vertices that are active on the chamber.
+
+ int isl_vertices_foreach_vertex(
+ __isl_keep isl_vertices *vertices,
+ int (*fn)(__isl_take isl_vertex *vertex, void *user),
+ void *user);
+
+ int isl_vertices_foreach_cell(
+ __isl_keep isl_vertices *vertices,
+ int (*fn)(__isl_take isl_cell *cell, void *user),
+ void *user);
+ int isl_cell_foreach_vertex(__isl_keep isl_cell *cell,
+ int (*fn)(__isl_take isl_vertex *vertex, void *user),
+ void *user);
+
+Other operations that can be performed on an C<isl_vertices> object are
+the following.
+
+ isl_ctx *isl_vertices_get_ctx(
+ __isl_keep isl_vertices *vertices);
+ int isl_vertices_get_n_vertices(
+ __isl_keep isl_vertices *vertices);
+ void isl_vertices_free(__isl_take isl_vertices *vertices);
+
+Vertices can be inspected and destroyed using the following functions.
+
+ isl_ctx *isl_vertex_get_ctx(__isl_keep isl_vertex *vertex);
+ int isl_vertex_get_id(__isl_keep isl_vertex *vertex);
+ __isl_give isl_basic_set *isl_vertex_get_domain(
+ __isl_keep isl_vertex *vertex);
+ __isl_give isl_basic_set *isl_vertex_get_expr(
+ __isl_keep isl_vertex *vertex);
+ void isl_vertex_free(__isl_take isl_vertex *vertex);
+
+C<isl_vertex_get_expr> returns a singleton parametric set describing
+the vertex, while C<isl_vertex_get_domain> returns the activity domain
+of the vertex.
+Note that C<isl_vertex_get_domain> and C<isl_vertex_get_expr> return
+B<rational> basic sets, so they should mainly be used for inspection
+and should not be mixed with integer sets.
+
+Chambers can be inspected and destroyed using the following functions.
+
+ isl_ctx *isl_cell_get_ctx(__isl_keep isl_cell *cell);
+ __isl_give isl_basic_set *isl_cell_get_domain(
+ __isl_keep isl_cell *cell);
+ void isl_cell_free(__isl_take isl_cell *cell);
+
+=head1 Polyhedral Compilation Library
+
+This section collects functionality in C<isl> that has been specifically
+designed for use during polyhedral compilation.
+
=head2 Dependence Analysis
C<isl> contains specialized functionality for performing
int isl_options_set_tile_scale_tile_loops(isl_ctx *ctx,
int val);
int isl_options_get_tile_scale_tile_loops(isl_ctx *ctx);
+ int isl_options_set_tile_shift_point_loops(isl_ctx *ctx,
+ int val);
+ int isl_options_get_tile_shift_point_loops(isl_ctx *ctx);
The C<isl_band_tile> function tiles the band using the given tile sizes
inside its schedule.
inserted between the modified band and its children.
The C<tile_scale_tile_loops> option specifies whether the tile
loops iterators should be scaled by the tile sizes.
+If the C<tile_shift_point_loops> option is set, then the point loops
+are shifted to start at zero.
+
+A band can be split into two nested bands using the following function.
+
+ int isl_band_split(__isl_keep isl_band *band, int pos);
+
+The resulting outer band contains the first C<pos> dimensions of C<band>
+while the inner band contains the remaining dimensions.
A representation of the band can be printed using
=back
-=head2 Parametric Vertex Enumeration
+=head2 AST Generation
+
+This section describes the C<isl> functionality for generating
+ASTs that visit all the elements
+in a domain in an order specified by a schedule.
+In particular, given a C<isl_union_map>, an AST is generated
+that visits all the elements in the domain of the C<isl_union_map>
+according to the lexicographic order of the corresponding image
+element(s). If the range of the C<isl_union_map> consists of
+elements in more than one space, then each of these spaces is handled
+separately in an arbitrary order.
+It should be noted that the image elements only specify the I<order>
+in which the corresponding domain elements should be visited.
+No direct relation between the image elements and the loop iterators
+in the generated AST should be assumed.
+
+Each AST is generated within a build. The initial build
+simply specifies the constraints on the parameters (if any)
+and can be created, inspected, copied and freed using the following functions.
+
+ #include <isl/ast_build.h>
+ __isl_give isl_ast_build *isl_ast_build_from_context(
+ __isl_take isl_set *set);
+ isl_ctx *isl_ast_build_get_ctx(
+ __isl_keep isl_ast_build *build);
+ __isl_give isl_ast_build *isl_ast_build_copy(
+ __isl_keep isl_ast_build *build);
+ void *isl_ast_build_free(
+ __isl_take isl_ast_build *build);
+
+The C<set> argument is usually a parameter set with zero or more parameters.
+More C<isl_ast_build> functions are described in L</"Nested AST Generation">
+and L</"Fine-grained Control over AST Generation">.
+Finally, the AST itself can be constructed using the following
+function.
-The parametric vertex enumeration described in this section
-is mainly intended to be used internally and by the C<barvinok>
-library.
+ #include <isl/ast_build.h>
+ __isl_give isl_ast_node *isl_ast_build_ast_from_schedule(
+ __isl_keep isl_ast_build *build,
+ __isl_take isl_union_map *schedule);
+
+=head3 Inspecting the AST
+
+The basic properties of an AST node can be obtained as follows.
+
+ #include <isl/ast.h>
+ isl_ctx *isl_ast_node_get_ctx(
+ __isl_keep isl_ast_node *node);
+ enum isl_ast_node_type isl_ast_node_get_type(
+ __isl_keep isl_ast_node *node);
+
+The type of an AST node is one of
+C<isl_ast_node_for>,
+C<isl_ast_node_if>,
+C<isl_ast_node_block> or
+C<isl_ast_node_user>.
+An C<isl_ast_node_for> represents a for node.
+An C<isl_ast_node_if> represents an if node.
+An C<isl_ast_node_block> represents a compound node.
+An C<isl_ast_node_user> represents an expression statement.
+An expression statement typically corresponds to a domain element, i.e.,
+one of the elements that is visited by the AST.
+
+Each type of node has its own additional properties.
+
+ #include <isl/ast.h>
+ __isl_give isl_ast_expr *isl_ast_node_for_get_iterator(
+ __isl_keep isl_ast_node *node);
+ __isl_give isl_ast_expr *isl_ast_node_for_get_init(
+ __isl_keep isl_ast_node *node);
+ __isl_give isl_ast_expr *isl_ast_node_for_get_cond(
+ __isl_keep isl_ast_node *node);
+ __isl_give isl_ast_expr *isl_ast_node_for_get_inc(
+ __isl_keep isl_ast_node *node);
+ __isl_give isl_ast_node *isl_ast_node_for_get_body(
+ __isl_keep isl_ast_node *node);
+ int isl_ast_node_for_is_degenerate(
+ __isl_keep isl_ast_node *node);
+
+An C<isl_ast_for> is considered degenerate if it is known to execute
+exactly once.
+
+ #include <isl/ast.h>
+ __isl_give isl_ast_expr *isl_ast_node_if_get_cond(
+ __isl_keep isl_ast_node *node);
+ __isl_give isl_ast_node *isl_ast_node_if_get_then(
+ __isl_keep isl_ast_node *node);
+ int isl_ast_node_if_has_else(
+ __isl_keep isl_ast_node *node);
+ __isl_give isl_ast_node *isl_ast_node_if_get_else(
+ __isl_keep isl_ast_node *node);
+
+ __isl_give isl_ast_node_list *
+ isl_ast_node_block_get_children(
+ __isl_keep isl_ast_node *node);
+
+ __isl_give isl_ast_expr *isl_ast_node_user_get_expr(
+ __isl_keep isl_ast_node *node);
+
+Each of the returned C<isl_ast_expr>s can in turn be inspected using
+the following functions.
- #include <isl/vertices.h>
- __isl_give isl_vertices *isl_basic_set_compute_vertices(
- __isl_keep isl_basic_set *bset);
+ #include <isl/ast.h>
+ isl_ctx *isl_ast_expr_get_ctx(
+ __isl_keep isl_ast_expr *expr);
+ enum isl_ast_expr_type isl_ast_expr_get_type(
+ __isl_keep isl_ast_expr *expr);
+
+The type of an AST expression is one of
+C<isl_ast_expr_op>,
+C<isl_ast_expr_id> or
+C<isl_ast_expr_int>.
+An C<isl_ast_expr_op> represents the result of an operation.
+An C<isl_ast_expr_id> represents an identifier.
+An C<isl_ast_expr_int> represents an integer value.
+
+Each type of expression has its own additional properties.
+
+ #include <isl/ast.h>
+ enum isl_ast_op_type isl_ast_expr_get_op_type(
+ __isl_keep isl_ast_expr *expr);
+ int isl_ast_expr_get_op_n_arg(__isl_keep isl_ast_expr *expr);
+ __isl_give isl_ast_expr *isl_ast_expr_get_op_arg(
+ __isl_keep isl_ast_expr *expr, int pos);
+ int isl_ast_node_foreach_ast_op_type(
+ __isl_keep isl_ast_node *node,
+ int (*fn)(enum isl_ast_op_type type, void *user),
+ void *user);
-The function C<isl_basic_set_compute_vertices> performs the
-actual computation of the parametric vertices and the chamber
-decomposition and store the result in an C<isl_vertices> object.
-This information can be queried by either iterating over all
-the vertices or iterating over all the chambers or cells
-and then iterating over all vertices that are active on the chamber.
+C<isl_ast_expr_get_op_type> returns the type of the operation
+performed. C<isl_ast_expr_get_op_n_arg> returns the number of
+arguments. C<isl_ast_expr_get_op_arg> returns the specified
+argument.
+C<isl_ast_node_foreach_ast_op_type> calls C<fn> for each distinct
+C<isl_ast_op_type> that appears in C<node>.
+The operation type is one of the following.
- int isl_vertices_foreach_vertex(
- __isl_keep isl_vertices *vertices,
- int (*fn)(__isl_take isl_vertex *vertex, void *user),
- void *user);
+=over
- int isl_vertices_foreach_cell(
- __isl_keep isl_vertices *vertices,
- int (*fn)(__isl_take isl_cell *cell, void *user),
+=item C<isl_ast_op_and>
+
+Logical I<and> of two arguments.
+Both arguments can be evaluated.
+
+=item C<isl_ast_op_and_then>
+
+Logical I<and> of two arguments.
+The second argument can only be evaluated if the first evaluates to true.
+
+=item C<isl_ast_op_or>
+
+Logical I<or> of two arguments.
+Both arguments can be evaluated.
+
+=item C<isl_ast_op_or_else>
+
+Logical I<or> of two arguments.
+The second argument can only be evaluated if the first evaluates to false.
+
+=item C<isl_ast_op_max>
+
+Maximum of two or more arguments.
+
+=item C<isl_ast_op_min>
+
+Minimum of two or more arguments.
+
+=item C<isl_ast_op_minus>
+
+Change sign.
+
+=item C<isl_ast_op_add>
+
+Sum of two arguments.
+
+=item C<isl_ast_op_sub>
+
+Difference of two arguments.
+
+=item C<isl_ast_op_mul>
+
+Product of two arguments.
+
+=item C<isl_ast_op_div>
+
+Exact division. That is, the result is known to be an integer.
+
+=item C<isl_ast_op_fdiv_q>
+
+Result of integer division, rounded towards negative
+infinity.
+
+=item C<isl_ast_op_pdiv_q>
+
+Result of integer division, where dividend is known to be non-negative.
+
+=item C<isl_ast_op_pdiv_r>
+
+Remainder of integer division, where dividend is known to be non-negative.
+
+=item C<isl_ast_op_cond>
+
+Conditional operator defined on three arguments.
+If the first argument evaluates to true, then the result
+is equal to the second argument. Otherwise, the result
+is equal to the third argument.
+The second and third argument may only be evaluated if
+the first argument evaluates to true and false, respectively.
+Corresponds to C<a ? b : c> in C.
+
+=item C<isl_ast_op_select>
+
+Conditional operator defined on three arguments.
+If the first argument evaluates to true, then the result
+is equal to the second argument. Otherwise, the result
+is equal to the third argument.
+The second and third argument may be evaluated independently
+of the value of the first argument.
+Corresponds to C<a * b + (1 - a) * c> in C.
+
+=item C<isl_ast_op_eq>
+
+Equality relation.
+
+=item C<isl_ast_op_le>
+
+Less than or equal relation.
+
+=item C<isl_ast_op_lt>
+
+Less than relation.
+
+=item C<isl_ast_op_ge>
+
+Greater than or equal relation.
+
+=item C<isl_ast_op_gt>
+
+Greater than relation.
+
+=item C<isl_ast_op_call>
+
+A function call.
+The number of arguments of the C<isl_ast_expr> is one more than
+the number of arguments in the function call, the first argument
+representing the function being called.
+
+=back
+
+ #include <isl/ast.h>
+ __isl_give isl_id *isl_ast_expr_get_id(
+ __isl_keep isl_ast_expr *expr);
+
+Return the identifier represented by the AST expression.
+
+ #include <isl/ast.h>
+ int isl_ast_expr_get_int(__isl_keep isl_ast_expr *expr,
+ isl_int *v);
+
+Return the integer represented by the AST expression.
+Note that the integer is returned through the C<v> argument.
+The return value of the function itself indicates whether the
+operation was performed successfully.
+
+=head3 Manipulating and printing the AST
+
+AST nodes can be copied and freed using the following functions.
+
+ #include <isl/ast.h>
+ __isl_give isl_ast_node *isl_ast_node_copy(
+ __isl_keep isl_ast_node *node);
+ void *isl_ast_node_free(__isl_take isl_ast_node *node);
+
+AST expressions can be copied and freed using the following functions.
+
+ #include <isl/ast.h>
+ __isl_give isl_ast_expr *isl_ast_expr_copy(
+ __isl_keep isl_ast_expr *expr);
+ void *isl_ast_expr_free(__isl_take isl_ast_expr *expr);
+
+New AST expressions can be created either directly or within
+the context of an C<isl_ast_build>.
+
+ #include <isl/ast.h>
+ __isl_give isl_ast_expr *isl_ast_expr_from_id(
+ __isl_take isl_id *id);
+ __isl_give isl_ast_expr *isl_ast_expr_neg(
+ __isl_take isl_ast_expr *expr);
+ __isl_give isl_ast_expr *isl_ast_expr_add(
+ __isl_take isl_ast_expr *expr1,
+ __isl_take isl_ast_expr *expr2);
+ __isl_give isl_ast_expr *isl_ast_expr_sub(
+ __isl_take isl_ast_expr *expr1,
+ __isl_take isl_ast_expr *expr2);
+ __isl_give isl_ast_expr *isl_ast_expr_mul(
+ __isl_take isl_ast_expr *expr1,
+ __isl_take isl_ast_expr *expr2);
+ __isl_give isl_ast_expr *isl_ast_expr_div(
+ __isl_take isl_ast_expr *expr1,
+ __isl_take isl_ast_expr *expr2);
+ __isl_give isl_ast_expr *isl_ast_expr_and(
+ __isl_take isl_ast_expr *expr1,
+ __isl_take isl_ast_expr *expr2)
+ __isl_give isl_ast_expr *isl_ast_expr_or(
+ __isl_take isl_ast_expr *expr1,
+ __isl_take isl_ast_expr *expr2)
+
+ #include <isl/ast_build.h>
+ __isl_give isl_ast_expr *isl_ast_build_expr_from_pw_aff(
+ __isl_keep isl_ast_build *build,
+ __isl_take isl_pw_aff *pa);
+ __isl_give isl_ast_expr *
+ isl_ast_build_call_from_pw_multi_aff(
+ __isl_keep isl_ast_build *build,
+ __isl_take isl_pw_multi_aff *pma);
+
+The domains of C<pa> and C<pma> should correspond
+to the schedule space of C<build>.
+The tuple id of C<pma> is used as the function being called.
+
+User specified data can be attached to an C<isl_ast_node> and obtained
+from the same C<isl_ast_node> using the following functions.
+
+ #include <isl/ast.h>
+ __isl_give isl_ast_node *isl_ast_node_set_annotation(
+ __isl_take isl_ast_node *node,
+ __isl_take isl_id *annotation);
+ __isl_give isl_id *isl_ast_node_get_annotation(
+ __isl_keep isl_ast_node *node);
+
+Basic printing can be performed using the following functions.
+
+ #include <isl/ast.h>
+ __isl_give isl_printer *isl_printer_print_ast_expr(
+ __isl_take isl_printer *p,
+ __isl_keep isl_ast_expr *expr);
+ __isl_give isl_printer *isl_printer_print_ast_node(
+ __isl_take isl_printer *p,
+ __isl_keep isl_ast_node *node);
+
+More advanced printing can be performed using the following functions.
+
+ #include <isl/ast.h>
+ __isl_give isl_printer *isl_ast_op_type_print_macro(
+ enum isl_ast_op_type type,
+ __isl_take isl_printer *p);
+ __isl_give isl_printer *isl_ast_node_print_macros(
+ __isl_keep isl_ast_node *node,
+ __isl_take isl_printer *p);
+ __isl_give isl_printer *isl_ast_node_print(
+ __isl_keep isl_ast_node *node,
+ __isl_take isl_printer *p,
+ __isl_take isl_ast_print_options *options);
+ __isl_give isl_printer *isl_ast_node_for_print(
+ __isl_keep isl_ast_node *node,
+ __isl_take isl_printer *p,
+ __isl_take isl_ast_print_options *options);
+ __isl_give isl_printer *isl_ast_node_if_print(
+ __isl_keep isl_ast_node *node,
+ __isl_take isl_printer *p,
+ __isl_take isl_ast_print_options *options);
+
+While printing an C<isl_ast_node> in C<ISL_FORMAT_C>,
+C<isl> may print out an AST that makes use of macros such
+as C<floord>, C<min> and C<max>.
+C<isl_ast_op_type_print_macro> prints out the macro
+corresponding to a specific C<isl_ast_op_type>.
+C<isl_ast_node_print_macros> scans the C<isl_ast_node>
+for expressions where these macros would be used and prints
+out the required macro definitions.
+Essentially, C<isl_ast_node_print_macros> calls
+C<isl_ast_node_foreach_ast_op_type> with C<isl_ast_op_type_print_macro>
+as function argument.
+C<isl_ast_node_print>, C<isl_ast_node_for_print> and
+C<isl_ast_node_if_print> print an C<isl_ast_node>
+in C<ISL_FORMAT_C>, but allow for some extra control
+through an C<isl_ast_print_options> object.
+This object can be created using the following functions.
+
+ #include <isl/ast.h>
+ __isl_give isl_ast_print_options *
+ isl_ast_print_options_alloc(isl_ctx *ctx);
+ __isl_give isl_ast_print_options *
+ isl_ast_print_options_copy(
+ __isl_keep isl_ast_print_options *options);
+ void *isl_ast_print_options_free(
+ __isl_take isl_ast_print_options *options);
+
+ __isl_give isl_ast_print_options *
+ isl_ast_print_options_set_print_user(
+ __isl_take isl_ast_print_options *options,
+ __isl_give isl_printer *(*print_user)(
+ __isl_take isl_printer *p,
+ __isl_take isl_ast_print_options *options,
+ __isl_keep isl_ast_node *node, void *user),
void *user);
- int isl_cell_foreach_vertex(__isl_keep isl_cell *cell,
- int (*fn)(__isl_take isl_vertex *vertex, void *user),
+ __isl_give isl_ast_print_options *
+ isl_ast_print_options_set_print_for(
+ __isl_take isl_ast_print_options *options,
+ __isl_give isl_printer *(*print_for)(
+ __isl_take isl_printer *p,
+ __isl_take isl_ast_print_options *options,
+ __isl_keep isl_ast_node *node, void *user),
void *user);
-Other operations that can be performed on an C<isl_vertices> object are
-the following.
+The callback set by C<isl_ast_print_options_set_print_user>
+is called whenever a node of type C<isl_ast_node_user> needs to
+be printed.
+The callback set by C<isl_ast_print_options_set_print_for>
+is called whenever a node of type C<isl_ast_node_for> needs to
+be printed.
+Note that C<isl_ast_node_for_print> will I<not> call the
+callback set by C<isl_ast_print_options_set_print_for> on the node
+on which C<isl_ast_node_for_print> is called, but only on nested
+nodes of type C<isl_ast_node_for>. It is therefore safe to
+call C<isl_ast_node_for_print> from within the callback set by
+C<isl_ast_print_options_set_print_for>.
+
+The following option determines the type to be used for iterators
+while printing the AST.
+
+ int isl_options_set_ast_iterator_type(
+ isl_ctx *ctx, const char *val);
+ const char *isl_options_get_ast_iterator_type(
+ isl_ctx *ctx);
- isl_ctx *isl_vertices_get_ctx(
- __isl_keep isl_vertices *vertices);
- int isl_vertices_get_n_vertices(
- __isl_keep isl_vertices *vertices);
- void isl_vertices_free(__isl_take isl_vertices *vertices);
+=head3 Options
-Vertices can be inspected and destroyed using the following functions.
+ #include <isl/ast_build.h>
+ int isl_options_set_ast_build_atomic_upper_bound(
+ isl_ctx *ctx, int val);
+ int isl_options_get_ast_build_atomic_upper_bound(
+ isl_ctx *ctx);
+ int isl_options_set_ast_build_prefer_pdiv(isl_ctx *ctx,
+ int val);
+ int isl_options_get_ast_build_prefer_pdiv(isl_ctx *ctx);
+ int isl_options_set_ast_build_exploit_nested_bounds(
+ isl_ctx *ctx, int val);
+ int isl_options_get_ast_build_exploit_nested_bounds(
+ isl_ctx *ctx);
+ int isl_options_set_ast_build_group_coscheduled(
+ isl_ctx *ctx, int val);
+ int isl_options_get_ast_build_group_coscheduled(
+ isl_ctx *ctx);
+ int isl_options_set_ast_build_scale_strides(
+ isl_ctx *ctx, int val);
+ int isl_options_get_ast_build_scale_strides(
+ isl_ctx *ctx);
+ int isl_options_set_ast_build_allow_else(isl_ctx *ctx,
+ int val);
+ int isl_options_get_ast_build_allow_else(isl_ctx *ctx);
+ int isl_options_set_ast_build_allow_or(isl_ctx *ctx,
+ int val);
+ int isl_options_get_ast_build_allow_or(isl_ctx *ctx);
- isl_ctx *isl_vertex_get_ctx(__isl_keep isl_vertex *vertex);
- int isl_vertex_get_id(__isl_keep isl_vertex *vertex);
- __isl_give isl_basic_set *isl_vertex_get_domain(
- __isl_keep isl_vertex *vertex);
- __isl_give isl_basic_set *isl_vertex_get_expr(
- __isl_keep isl_vertex *vertex);
- void isl_vertex_free(__isl_take isl_vertex *vertex);
+=over
-C<isl_vertex_get_expr> returns a singleton parametric set describing
-the vertex, while C<isl_vertex_get_domain> returns the activity domain
-of the vertex.
-Note that C<isl_vertex_get_domain> and C<isl_vertex_get_expr> return
-B<rational> basic sets, so they should mainly be used for inspection
-and should not be mixed with integer sets.
+=item * ast_build_atomic_upper_bound
-Chambers can be inspected and destroyed using the following functions.
+Generate loop upper bounds that consist of the current loop iterator,
+an operator and an expression not involving the iterator.
+If this option is not set, then the current loop iterator may appear
+several times in the upper bound.
+For example, when this option is turned off, AST generation
+for the schedule
- isl_ctx *isl_cell_get_ctx(__isl_keep isl_cell *cell);
- __isl_give isl_basic_set *isl_cell_get_domain(
- __isl_keep isl_cell *cell);
- void isl_cell_free(__isl_take isl_cell *cell);
+ [n] -> { A[i] -> [i] : 0 <= i <= 100, n }
+
+produces
+
+ for (int c0 = 0; c0 <= 100 && n >= c0; c0 += 1)
+ A(c0);
+
+When the option is turned on, the following AST is generated
+
+ for (int c0 = 0; c0 <= min(100, n); c0 += 1)
+ A(c0);
+
+=item * ast_build_prefer_pdiv
+
+If this option is turned off, then the AST generation will
+produce ASTs that may only contain C<isl_ast_op_fdiv_q>
+operators, but no C<isl_ast_op_pdiv_q> or
+C<isl_ast_op_pdiv_r> operators.
+If this options is turned on, then C<isl> will try to convert
+some of the C<isl_ast_op_fdiv_q> operators to (expressions containing)
+C<isl_ast_op_pdiv_q> or C<isl_ast_op_pdiv_r> operators.
+
+=item * ast_build_exploit_nested_bounds
+
+Simplify conditions based on bounds of nested for loops.
+In particular, remove conditions that are implied by the fact
+that one or more nested loops have at least one iteration,
+meaning that the upper bound is at least as large as the lower bound.
+For example, when this option is turned off, AST generation
+for the schedule
+
+ [N,M] -> { A[i,j] -> [i,j] : 0 <= i <= N and
+ 0 <= j <= M }
+
+produces
+
+ if (M >= 0)
+ for (int c0 = 0; c0 <= N; c0 += 1)
+ for (int c1 = 0; c1 <= M; c1 += 1)
+ A(c0, c1);
+
+When the option is turned on, the following AST is generated
+
+ for (int c0 = 0; c0 <= N; c0 += 1)
+ for (int c1 = 0; c1 <= M; c1 += 1)
+ A(c0, c1);
+
+=item * ast_build_group_coscheduled
+
+If two domain elements are assigned the same schedule point, then
+they may be executed in any order and they may even appear in different
+loops. If this options is set, then the AST generator will make
+sure that coscheduled domain elements do not appear in separate parts
+of the AST. This is useful in case of nested AST generation
+if the outer AST generation is given only part of a schedule
+and the inner AST generation should handle the domains that are
+coscheduled by this initial part of the schedule together.
+For example if an AST is generated for a schedule
+
+ { A[i] -> [0]; B[i] -> [0] }
+
+then the C<isl_ast_build_set_create_leaf> callback described
+below may get called twice, once for each domain.
+Setting this option ensures that the callback is only called once
+on both domains together.
+
+=item * ast_build_separation_bounds
+
+This option specifies which bounds to use during separation.
+If this option is set to C<ISL_AST_BUILD_SEPARATION_BOUNDS_IMPLICIT>
+then all (possibly implicit) bounds on the current dimension will
+be used during separation.
+If this option is set to C<ISL_AST_BUILD_SEPARATION_BOUNDS_EXPLICIT>
+then only those bounds that are explicitly available will
+be used during separation.
+
+=item * ast_build_scale_strides
+
+This option specifies whether the AST generator is allowed
+to scale down iterators of strided loops.
+
+=item * ast_build_allow_else
+
+This option specifies whether the AST generator is allowed
+to construct if statements with else branches.
+
+=item * ast_build_allow_or
+
+This option specifies whether the AST generator is allowed
+to construct if conditions with disjunctions.
+
+=back
+
+=head3 Fine-grained Control over AST Generation
+
+Besides specifying the constraints on the parameters,
+an C<isl_ast_build> object can be used to control
+various aspects of the AST generation process.
+The most prominent way of control is through ``options'',
+which can be set using the following function.
+
+ #include <isl/ast_build.h>
+ __isl_give isl_ast_build *
+ isl_ast_build_set_options(
+ __isl_take isl_ast_build *control,
+ __isl_take isl_union_map *options);
+
+The options are encoded in an <isl_union_map>.
+The domain of this union relation refers to the schedule domain,
+i.e., the range of the schedule passed to C<isl_ast_build_ast_from_schedule>.
+In the case of nested AST generation (see L</"Nested AST Generation">),
+the domain of C<options> should refer to the extra piece of the schedule.
+That is, it should be equal to the range of the wrapped relation in the
+range of the schedule.
+The range of the options can consist of elements in one or more spaces,
+the names of which determine the effect of the option.
+The values of the range typically also refer to the schedule dimension
+to which the option applies. In case of nested AST generation
+(see L</"Nested AST Generation">), these values refer to the position
+of the schedule dimension within the innermost AST generation.
+The constraints on the domain elements of
+the option should only refer to this dimension and earlier dimensions.
+We consider the following spaces.
+
+=over
+
+=item C<separation_class>
+
+This space is a wrapped relation between two one dimensional spaces.
+The input space represents the schedule dimension to which the option
+applies and the output space represents the separation class.
+While constructing a loop corresponding to the specified schedule
+dimension(s), the AST generator will try to generate separate loops
+for domain elements that are assigned different classes.
+If only some of the elements are assigned a class, then those elements
+that are not assigned any class will be treated as belonging to a class
+that is separate from the explicitly assigned classes.
+The typical use case for this option is to separate full tiles from
+partial tiles.
+The other options, described below, are applied after the separation
+into classes.
+
+As an example, consider the separation into full and partial tiles
+of a tiling of a triangular domain.
+Take, for example, the domain
+
+ { A[i,j] : 0 <= i,j and i + j <= 100 }
+
+and a tiling into tiles of 10 by 10. The input to the AST generator
+is then the schedule
+
+ { A[i,j] -> [([i/10]),[j/10],i,j] : 0 <= i,j and
+ i + j <= 100 }
+
+Without any options, the following AST is generated
+
+ for (int c0 = 0; c0 <= 10; c0 += 1)
+ for (int c1 = 0; c1 <= -c0 + 10; c1 += 1)
+ for (int c2 = 10 * c0;
+ c2 <= min(-10 * c1 + 100, 10 * c0 + 9);
+ c2 += 1)
+ for (int c3 = 10 * c1;
+ c3 <= min(10 * c1 + 9, -c2 + 100);
+ c3 += 1)
+ A(c2, c3);
+
+Separation into full and partial tiles can be obtained by assigning
+a class, say C<0>, to the full tiles. The full tiles are represented by those
+values of the first and second schedule dimensions for which there are
+values of the third and fourth dimensions to cover an entire tile.
+That is, we need to specify the following option
+
+ { [a,b,c,d] -> separation_class[[0]->[0]] :
+ exists b': 0 <= 10a,10b' and
+ 10a+9+10b'+9 <= 100;
+ [a,b,c,d] -> separation_class[[1]->[0]] :
+ 0 <= 10a,10b and 10a+9+10b+9 <= 100 }
+
+which simplifies to
+
+ { [a, b, c, d] -> separation_class[[1] -> [0]] :
+ a >= 0 and b >= 0 and b <= 8 - a;
+ [a, b, c, d] -> separation_class[[0] -> [0]] :
+ a >= 0 and a <= 8 }
+
+With this option, the generated AST is as follows
+
+ {
+ for (int c0 = 0; c0 <= 8; c0 += 1) {
+ for (int c1 = 0; c1 <= -c0 + 8; c1 += 1)
+ for (int c2 = 10 * c0;
+ c2 <= 10 * c0 + 9; c2 += 1)
+ for (int c3 = 10 * c1;
+ c3 <= 10 * c1 + 9; c3 += 1)
+ A(c2, c3);
+ for (int c1 = -c0 + 9; c1 <= -c0 + 10; c1 += 1)
+ for (int c2 = 10 * c0;
+ c2 <= min(-10 * c1 + 100, 10 * c0 + 9);
+ c2 += 1)
+ for (int c3 = 10 * c1;
+ c3 <= min(-c2 + 100, 10 * c1 + 9);
+ c3 += 1)
+ A(c2, c3);
+ }
+ for (int c0 = 9; c0 <= 10; c0 += 1)
+ for (int c1 = 0; c1 <= -c0 + 10; c1 += 1)
+ for (int c2 = 10 * c0;
+ c2 <= min(-10 * c1 + 100, 10 * c0 + 9);
+ c2 += 1)
+ for (int c3 = 10 * c1;
+ c3 <= min(10 * c1 + 9, -c2 + 100);
+ c3 += 1)
+ A(c2, c3);
+ }
+
+=item C<separate>
+
+This is a single-dimensional space representing the schedule dimension(s)
+to which ``separation'' should be applied. Separation tries to split
+a loop into several pieces if this can avoid the generation of guards
+inside the loop.
+See also the C<atomic> option.
+
+=item C<atomic>
+
+This is a single-dimensional space representing the schedule dimension(s)
+for which the domains should be considered ``atomic''. That is, the
+AST generator will make sure that any given domain space will only appear
+in a single loop at the specified level.
+
+Consider the following schedule
+
+ { a[i] -> [i] : 0 <= i < 10;
+ b[i] -> [i+1] : 0 <= i < 10 }
+
+If the following option is specified
+
+ { [i] -> separate[x] }
+
+then the following AST will be generated
+
+ {
+ a(0);
+ for (int c0 = 1; c0 <= 9; c0 += 1) {
+ a(c0);
+ b(c0 - 1);
+ }
+ b(9);
+ }
+
+If, on the other hand, the following option is specified
+
+ { [i] -> atomic[x] }
+
+then the following AST will be generated
+
+ for (int c0 = 0; c0 <= 10; c0 += 1) {
+ if (c0 <= 9)
+ a(c0);
+ if (c0 >= 1)
+ b(c0 - 1);
+ }
+
+If neither C<atomic> nor C<separate> is specified, then the AST generator
+may produce either of these two results or some intermediate form.
+
+=item C<unroll>
+
+This is a single-dimensional space representing the schedule dimension(s)
+that should be I<completely> unrolled.
+To obtain a partial unrolling, the user should apply an additional
+strip-mining to the schedule and fully unroll the inner loop.
+
+=back
+
+Additional control is available through the following functions.
+
+ #include <isl/ast_build.h>
+ __isl_give isl_ast_build *
+ isl_ast_build_set_iterators(
+ __isl_take isl_ast_build *control,
+ __isl_take isl_id_list *iterators);
+
+The function C<isl_ast_build_set_iterators> allows the user to
+specify a list of iterator C<isl_id>s to be used as iterators.
+If the input schedule is injective, then
+the number of elements in this list should be as large as the dimension
+of the schedule space, but no direct correspondence should be assumed
+between dimensions and elements.
+If the input schedule is not injective, then an additional number
+of C<isl_id>s equal to the largest dimension of the input domains
+may be required.
+If the number of provided C<isl_id>s is insufficient, then additional
+names are automatically generated.
+
+ #include <isl/ast_build.h>
+ __isl_give isl_ast_build *
+ isl_ast_build_set_create_leaf(
+ __isl_take isl_ast_build *control,
+ __isl_give isl_ast_node *(*fn)(
+ __isl_take isl_ast_build *build,
+ void *user), void *user);
+
+The
+C<isl_ast_build_set_create_leaf> function allows for the
+specification of a callback that should be called whenever the AST
+generator arrives at an element of the schedule domain.
+The callback should return an AST node that should be inserted
+at the corresponding position of the AST. The default action (when
+the callback is not set) is to continue generating parts of the AST to scan
+all the domain elements associated to the schedule domain element
+and to insert user nodes, ``calling'' the domain element, for each of them.
+The C<build> argument contains the current state of the C<isl_ast_build>.
+To ease nested AST generation (see L</"Nested AST Generation">),
+all control information that is
+specific to the current AST generation such as the options and
+the callbacks has been removed from this C<isl_ast_build>.
+The callback would typically return the result of a nested
+AST generation or a
+user defined node created using the following function.
+
+ #include <isl/ast.h>
+ __isl_give isl_ast_node *isl_ast_node_alloc_user(
+ __isl_take isl_ast_expr *expr);
+
+ #include <isl/ast_build.h>
+ __isl_give isl_ast_build *
+ isl_ast_build_set_at_each_domain(
+ __isl_take isl_ast_build *build,
+ __isl_give isl_ast_node *(*fn)(
+ __isl_take isl_ast_node *node,
+ __isl_keep isl_ast_build *build,
+ void *user), void *user);
+ __isl_give isl_ast_build *
+ isl_ast_build_set_before_each_for(
+ __isl_take isl_ast_build *build,
+ __isl_give isl_id *(*fn)(
+ __isl_keep isl_ast_build *build,
+ void *user), void *user);
+ __isl_give isl_ast_build *
+ isl_ast_build_set_after_each_for(
+ __isl_take isl_ast_build *build,
+ __isl_give isl_ast_node *(*fn)(
+ __isl_take isl_ast_node *node,
+ __isl_keep isl_ast_build *build,
+ void *user), void *user);
+
+The callback set by C<isl_ast_build_set_at_each_domain> will
+be called for each domain AST node.
+The callbacks set by C<isl_ast_build_set_before_each_for>
+and C<isl_ast_build_set_after_each_for> will be called
+for each for AST node. The first will be called in depth-first
+pre-order, while the second will be called in depth-first post-order.
+Since C<isl_ast_build_set_before_each_for> is called before the for
+node is actually constructed, it is only passed an C<isl_ast_build>.
+The returned C<isl_id> will be added as an annotation (using
+C<isl_ast_node_set_annotation>) to the constructed for node.
+In particular, if the user has also specified an C<after_each_for>
+callback, then the annotation can be retrieved from the node passed to
+that callback using C<isl_ast_node_get_annotation>.
+All callbacks should C<NULL> on failure.
+The given C<isl_ast_build> can be used to create new
+C<isl_ast_expr> objects using C<isl_ast_build_expr_from_pw_aff>
+or C<isl_ast_build_call_from_pw_multi_aff>.
+
+=head3 Nested AST Generation
+
+C<isl> allows the user to create an AST within the context
+of another AST. These nested ASTs are created using the
+same C<isl_ast_build_ast_from_schedule> function that is used to create the
+outer AST. The C<build> argument should be an C<isl_ast_build>
+passed to a callback set by
+C<isl_ast_build_set_create_leaf>.
+The space of the range of the C<schedule> argument should refer
+to this build. In particular, the space should be a wrapped
+relation and the domain of this wrapped relation should be the
+same as that of the range of the schedule returned by
+C<isl_ast_build_get_schedule> below.
+In practice, the new schedule is typically
+created by calling C<isl_union_map_range_product> on the old schedule
+and some extra piece of the schedule.
+The space of the schedule domain is also available from
+the C<isl_ast_build>.
+
+ #include <isl/ast_build.h>
+ __isl_give isl_union_map *isl_ast_build_get_schedule(
+ __isl_keep isl_ast_build *build);
+ __isl_give isl_space *isl_ast_build_get_schedule_space(
+ __isl_keep isl_ast_build *build);
+ __isl_give isl_ast_build *isl_ast_build_restrict(
+ __isl_take isl_ast_build *build,
+ __isl_take isl_set *set);
+
+The C<isl_ast_build_get_schedule> function returns a (partial)
+schedule for the domains elements for which part of the AST still needs to
+be generated in the current build.
+In particular, the domain elements are mapped to those iterations of the loops
+enclosing the current point of the AST generation inside which
+the domain elements are executed.
+No direct correspondence between
+the input schedule and this schedule should be assumed.
+The space obtained from C<isl_ast_build_get_schedule_space> can be used
+to create a set for C<isl_ast_build_restrict> to intersect
+with the current build. In particular, the set passed to
+C<isl_ast_build_restrict> can have additional parameters.
+The ids of the set dimensions in the space returned by
+C<isl_ast_build_get_schedule_space> correspond to the
+iterators of the already generated loops.
+The user should not rely on the ids of the output dimensions
+of the relations in the union relation returned by
+C<isl_ast_build_get_schedule> having any particular value.
=head1 Applications
Given a polytope, C<isl_polytope_scan> prints
all integer points in the polytope.
+
+=head2 C<isl_codegen>
+
+Given a schedule, a context set and an options relation,
+C<isl_codegen> prints out an AST that scans the domain elements
+of the schedule in the order of their image(s) taking into account
+the constraints in the context set.