X-Git-Url: http://review.tizen.org/git/?p=platform%2Fupstream%2Fisl.git;a=blobdiff_plain;f=doc%2Fuser.pod;h=7ddf30f98e88ee25b205bb522b3a2f582bf57bcc;hp=0fd72bc52c53381d1b12aee7134e7bddb28bc395;hb=ca90b151a05f17ccc1c3215ff24dc5d7b9198ff4;hpb=a61948594142d2e20b86c0d871d18815e7a269cb diff --git a/doc/user.pod b/doc/user.pod index 0fd72bc..7ddf30f 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -176,6 +176,8 @@ A call C can be replaced by C have been renamed to C and C. +The new C and +C have slightly different meanings. =back @@ -319,7 +321,7 @@ Location where C C was built. =back -=head1 Library +=head1 Integer Set Library =head2 Initialization @@ -341,7 +343,184 @@ before the C itself is freed. isl_ctx *isl_ctx_alloc(); void isl_ctx_free(isl_ctx *ctx); -=head2 Integers +=head2 Values + +An C 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_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_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_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_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, C and +C can only be applied to rational values. + +An C can be modified using the following function. + + #include + __isl_give isl_val *isl_val_set_si(__isl_take isl_val *v, + long i); + +The following unary properties are defined on Cs. + + #include + 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 Cs. + + #include + 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 Cs we additionally have the following binary property. + + #include + int isl_val_is_divisible_by(__isl_keep isl_val *v1, + __isl_keep isl_val *v2); + +An C can also be compared to an integer using the following +function. The result is undefined for NaN. + + #include + int isl_val_cmp_si(__isl_keep isl_val *v, long i); + +The following unary operations are available on Cs. + + #include + __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 Cs. + + #include + __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_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 returns the greatest common divisor g +of C and C as well as two integers C<*x> and C<*y> such +that C<*x> * C + C<*y> * C = g. + +A value can be read from input using + + #include + __isl_give isl_val *isl_val_read_from_str(isl_ctx *ctx, + const char *str); + +A value can be printed using + + #include + __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 has been compiled with C +support. + +Specific integer and rational values can be created from C values using +the following functions. + + #include + __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 values using the following functions. + + #include + 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, @@ -596,6 +775,9 @@ using the following functions. #include __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); @@ -606,6 +788,8 @@ using the following functions. __isl_give isl_printer *isl_printer_print_id( __isl_take isl_printer *p, __isl_keep isl_id *id); +The callback set by C is called on the user +pointer when the last reference to the C is freed. Note that C returns a pointer to some internal data structure, so the result can only be used while the corresponding C is alive. @@ -727,6 +911,10 @@ of the original object. __isl_give isl_space *isl_union_pw_qpolynomial_fold_get_space( __isl_keep isl_union_pw_qpolynomial_fold *upwf); + #include + __isl_give isl_space *isl_multi_val_get_space( + __isl_keep isl_multi_val *mv); + #include __isl_give isl_space *isl_aff_get_domain_space( __isl_keep isl_aff *aff); @@ -943,6 +1131,9 @@ They can be inspected, modified, copied and freed using the following functions. __isl_keep isl_local_space *ls); void *isl_local_space_free(__isl_take isl_local_space *ls); +Note that C 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, @@ -1273,9 +1464,11 @@ space. __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); @@ -1316,12 +1509,19 @@ using the following functions. __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); @@ -1593,9 +1793,14 @@ the following functions. 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); @@ -1675,6 +1880,16 @@ a given dimension is involved in any lower or upper bound. 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. +To check if they have a bound for all of the basic sets in C, +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. @@ -2143,6 +2358,10 @@ dimensions have opposite values. __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); @@ -2313,6 +2532,11 @@ per space. __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, @@ -2546,6 +2770,8 @@ interchange the range of the domain with the domain of the range. __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 functions @@ -2576,6 +2802,9 @@ All parameters need to be named. =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); @@ -2785,10 +3014,17 @@ a parametric set as well. __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); -These functions compute 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. +into the set description or into the domain of the map. Objects of types C and C are described in L. @@ -3034,6 +3270,10 @@ returning a basic set or relation. __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( @@ -3042,8 +3282,8 @@ returning a basic set or relation. =head2 Lists Lists are defined over several element types, including -C, C, C, C, -C and C. +C, C, C, C, C, +C, C, C and C. Here we take lists of Cs as an example. Lists can be created, copied, modified and freed using the following functions. @@ -3069,6 +3309,11 @@ 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 creates an empty list with a capacity for @@ -3085,6 +3330,18 @@ Lists can be inspected using the following functions. 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 calls C on each of the +strongly connected components of the graph with as vertices the elements +of C and a directed edge from vertex C to vertex C +iff C returns C<1>. The callbacks C and C +should return C<-1> on error. Lists can be printed using @@ -3093,6 +3350,94 @@ Lists can be printed using __isl_take isl_printer *p, __isl_keep isl_set_list *list); +=head2 Multiple Values + +An C object represents a sequence of zero or more values, +living in a set space. + +An C can be constructed from an C +using the following function + + #include + __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_give isl_multi_val *isl_multi_val_zero( + __isl_take isl_space *space); + +Multiple values can be copied and freed using + + #include + __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_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_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_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); + =head2 Vectors Vectors can be created, copied and freed using the following functions. @@ -3110,14 +3455,21 @@ The elements can be changed and inspected 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); @@ -3137,7 +3489,7 @@ Matrices can be created, copied and freed using the following functions. __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. @@ -3147,10 +3499,15 @@ 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 will return a negative value if anything went wrong. In that case, the value of C<*v> is undefined. @@ -3266,10 +3623,17 @@ The expression can be inspected using 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); @@ -3312,12 +3676,18 @@ It can be modified using __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); @@ -3325,6 +3695,8 @@ It can be modified using __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( @@ -3335,6 +3707,10 @@ It can be modified using __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, @@ -3355,9 +3731,13 @@ It can be modified using __isl_take isl_pw_aff *pwaff, enum isl_dim_type type, unsigned first, unsigned n); -Note that the C and C functions +Note that C, C, +C and C set the I of the constant or coefficient, while -C and C add an integer value to +C and C set +the constant or coefficient as a whole. +The C and C functions add an integer +or rational value to the possibly rational constant or coefficient. The C functions add an integer value to the numerator. @@ -3403,16 +3783,22 @@ Operations include __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_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_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); @@ -3486,9 +3872,13 @@ remainder. __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. In other words, the C is plugged +C or C. In other words, +the C or C is plugged into the (piecewise) affine expression. Objects of type C are described in L. @@ -3676,12 +4066,21 @@ can be created using the following functions. A piecewise multiple quasi affine expression can also be initialized from an C or C, provided the C is a singleton and the C is single-valued. +In case of a conversion from an C or an C +to an C, 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 @@ -3844,15 +4243,44 @@ Operations include __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 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_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 scales the first elements of C +by the corresponding elements of C. + __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); @@ -3943,6 +4371,10 @@ the lifting applied. 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 precomposes C by C. In other words, C is plugged @@ -3967,6 +4399,9 @@ An expression can be read from input using 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 @@ -3998,9 +4433,16 @@ 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, @@ -4154,6 +4596,9 @@ on the resulting quasipolynomials __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); @@ -4248,6 +4693,11 @@ will not have any existentially quantified variables, but that the dimensions of the sets may be different for different invocations of C. +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 @@ -4265,6 +4715,8 @@ these functions 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( @@ -4301,6 +4753,9 @@ obviously equal, use __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( @@ -4537,6 +4992,9 @@ obviously equal, use __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_add( __isl_take isl_pw_qpolynomial_fold *pwf1, @@ -4640,6 +5098,74 @@ The functions taking a set compute a bound over all elements in the 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 +library. + + #include + __isl_give isl_vertices *isl_basic_set_compute_vertices( + __isl_keep isl_basic_set *bset); + +The function C performs the +actual computation of the parametric vertices and the chamber +decomposition and store the result in an C 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 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 returns a singleton parametric set describing +the vertex, while C returns the activity domain +of the vertex. +Note that C and C return +B 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 that has been specifically +designed for use during polyhedral compilation. + =head2 Dependence Analysis C contains specialized functionality for performing @@ -4971,6 +5497,9 @@ A band can be tiled using the following function. 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 function tiles the band using the given tile sizes inside its schedule. @@ -4978,6 +5507,15 @@ A new child band is created to represent the point loops and it is inserted between the modified band and its children. The C option specifies whether the tile loops iterators should be scaled by the tile sizes. +If the C 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 dimensions of C +while the inner band contains the remaining dimensions. A representation of the band can be printed using @@ -5091,68 +5629,883 @@ schedules. =back -=head2 Parametric Vertex Enumeration +=head2 AST Generation + +This section describes the C functionality for generating +ASTs that visit all the elements +in a domain in an order specified by a schedule. +In particular, given a C, an AST is generated +that visits all the elements in the domain of the C +according to the lexicographic order of the corresponding image +element(s). If the range of the C 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 +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_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 argument is usually a parameter set with zero or more parameters. +More C functions are described in L +and L. +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 -library. + #include + __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_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, +C, +C or +C. +An C represents a for node. +An C represents an if node. +An C represents a compound node. +An C 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_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 is considered degenerate if it is known to execute +exactly once. + + #include + __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 Cs can in turn be inspected using +the following functions. - #include - __isl_give isl_vertices *isl_basic_set_compute_vertices( - __isl_keep isl_basic_set *bset); + #include + 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, +C or +C. +An C represents the result of an operation. +An C represents an identifier. +An C represents an integer value. + +Each type of expression has its own additional properties. + + #include + 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 performs the -actual computation of the parametric vertices and the chamber -decomposition and store the result in an C 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 returns the type of the operation +performed. C returns the number of +arguments. C returns the specified +argument. +C calls C for each distinct +C that appears in C. +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 + +Logical I of two arguments. +Both arguments can be evaluated. + +=item C + +Logical I of two arguments. +The second argument can only be evaluated if the first evaluates to true. + +=item C + +Logical I of two arguments. +Both arguments can be evaluated. + +=item C + +Logical I of two arguments. +The second argument can only be evaluated if the first evaluates to false. + +=item C + +Maximum of two or more arguments. + +=item C + +Minimum of two or more arguments. + +=item C + +Change sign. + +=item C + +Sum of two arguments. + +=item C + +Difference of two arguments. + +=item C + +Product of two arguments. + +=item C + +Exact division. That is, the result is known to be an integer. + +=item C + +Result of integer division, rounded towards negative +infinity. + +=item C + +Result of integer division, where dividend is known to be non-negative. + +=item C + +Remainder of integer division, where dividend is known to be non-negative. + +=item C + +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 in C. + +=item C + +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 in C. + +=item C + +Equality relation. + +=item C + +Less than or equal relation. + +=item C + +Less than relation. + +=item C + +Greater than or equal relation. + +=item C + +Greater than relation. + +=item C + +A function call. +The number of arguments of the C is one more than +the number of arguments in the function call, the first argument +representing the function being called. + +=back + + #include + __isl_give isl_id *isl_ast_expr_get_id( + __isl_keep isl_ast_expr *expr); + +Return the identifier represented by the AST expression. + + #include + 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 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_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_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. + + #include + __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_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 and C should correspond +to the schedule space of C. +The tuple id of C is used as the function being called. + +User specified data can be attached to an C and obtained +from the same C using the following functions. + + #include + __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_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_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 in C, +C may print out an AST that makes use of macros such +as C, C and C. +C prints out the macro +corresponding to a specific C. +C scans the C +for expressions where these macros would be used and prints +out the required macro definitions. +Essentially, C calls +C with C +as function argument. +C, C and +C print an C +in C, but allow for some extra control +through an C object. +This object can be created using the following functions. + + #include + __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 object are -the following. +The callback set by C +is called whenever a node of type C needs to +be printed. +The callback set by C +is called whenever a node of type C needs to +be printed. +Note that C will I call the +callback set by C on the node +on which C is called, but only on nested +nodes of type C. It is therefore safe to +call C from within the callback set by +C. + +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 + 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 returns a singleton parametric set describing -the vertex, while C returns the activity domain -of the vertex. -Note that C and C return -B 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 +operators, but no C or +C operators. +If this options is turned on, then C will try to convert +some of the C operators to (expressions containing) +C or C 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 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 +then all (possibly implicit) bounds on the current dimension will +be used during separation. +If this option is set to C +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 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_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 . +The domain of this union relation refers to the schedule domain, +i.e., the range of the schedule passed to C. +In the case of nested AST generation (see L), +the domain of C 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), 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 + +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 + +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 option. + +=item C + +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 nor C is specified, then the AST generator +may produce either of these two results or some intermediate form. + +=item C + +This is a single-dimensional space representing the schedule dimension(s) +that should be I 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_give isl_ast_build * + isl_ast_build_set_iterators( + __isl_take isl_ast_build *control, + __isl_take isl_id_list *iterators); + +The function C allows the user to +specify a list of iterator Cs 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 Cs equal to the largest dimension of the input domains +may be required. +If the number of provided Cs is insufficient, then additional +names are automatically generated. + + #include + __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 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 argument contains the current state of the C. +To ease nested AST generation (see L), +all control information that is +specific to the current AST generation such as the options and +the callbacks has been removed from this C. +The callback would typically return the result of a nested +AST generation or a +user defined node created using the following function. + + #include + __isl_give isl_ast_node *isl_ast_node_alloc_user( + __isl_take isl_ast_expr *expr); + + #include + __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 will +be called for each domain AST node. +The callbacks set by C +and C 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 is called before the for +node is actually constructed, it is only passed an C. +The returned C will be added as an annotation (using +C) to the constructed for node. +In particular, if the user has also specified an C +callback, then the annotation can be retrieved from the node passed to +that callback using C. +All callbacks should C on failure. +The given C can be used to create new +C objects using C +or C. + +=head3 Nested AST Generation + +C allows the user to create an AST within the context +of another AST. These nested ASTs are created using the +same C function that is used to create the +outer AST. The C argument should be an C +passed to a callback set by +C. +The space of the range of the C 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 below. +In practice, the new schedule is typically +created by calling C on the old schedule +and some extra piece of the schedule. +The space of the schedule domain is also available from +the C. + + #include + __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 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 can be used +to create a set for C to intersect +with the current build. In particular, the set passed to +C can have additional parameters. +The ids of the set dimensions in the space returned by +C 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 having any particular value. =head1 Applications @@ -5193,3 +6546,10 @@ is given, then the constant should appear in the last column. Given a polytope, C prints all integer points in the polytope. + +=head2 C + +Given a schedule, a context set and an options relation, +C 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.