X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=doc%2Fuser.pod;h=593572f52281e57783695d3a917e02be36962e9b;hb=6a01887a15af84c688f61df13ccf6939f9435248;hp=3502045076209f50dca8a50bd81bed034a81de54;hpb=6c4e01de2066522ab9058794ffa37a8678678a03;p=platform%2Fupstream%2Fisl.git diff --git a/doc/user.pod b/doc/user.pod index 3502045..593572f 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -153,6 +153,21 @@ dimension manipulation on the result. =back +=head3 Changes since isl-0.09 + +=over + +=item * The C option has been replaced +by the C option. + +=item * The first argument of C is now +an C instead of an C. +A call C can be replaced by + + isl_pw_aff_cond(isl_set_indicator_function(a), b, c) + +=back + =head1 Installation The source of C can be obtained either as a tarball @@ -479,6 +494,49 @@ a C value for an C<__isl_take> argument. =back +=head2 Error Handling + +C supports different ways to react in case a runtime error is triggered. +Runtime errors arise, e.g., if a function such as C is called +with two maps that have incompatible spaces. There are three possible ways +to react on error: to warn, to continue or to abort. + +The default behavior is to warn. In this mode, C prints a warning, stores +the last error in the corresponding C and the function in which the +error was triggered returns C. An error does not corrupt internal state, +such that isl can continue to be used. C also provides functions to +read the last error and to reset the memory that stores the last error. The +last error is only stored for information purposes. Its presence does not +change the behavior of C. Hence, resetting an error is not required to +continue to use isl, but only to observe new errors. + + #include + enum isl_error isl_ctx_last_error(isl_ctx *ctx); + void isl_ctx_reset_error(isl_ctx *ctx); + +Another option is to continue on error. This is similar to warn on error mode, +except that C does not print any warning. This allows a program to +implement its own error reporting. + +The last option is to directly abort the execution of the program from within +the isl library. This makes it obviously impossible to recover from an error, +but it allows to directly spot the error location. By aborting on error, +debuggers break at the location the error occurred and can provide a stack +trace. Other tools that automatically provide stack traces on abort or that do +not want to continue execution after an error was triggered may also prefer to +abort on error. + +The on error behavior of isl can be specified by calling +C or by setting the command line option +C<--isl-on-error>. Valid arguments for the function call are +C, C and C. The +choices for the command line option are C, C and C. +It is also possible to query the current error mode. + + #include + int isl_options_set_on_error(isl_ctx *ctx, int val); + int isl_options_get_on_error(isl_ctx *ctx); + =head2 Identifiers Identifiers are used to identify both individual dimensions @@ -624,11 +682,15 @@ using the following functions. __isl_give isl_id *isl_space_get_dim_id( __isl_keep isl_space *space, enum isl_dim_type type, unsigned pos); - __isl_give isl_space *isl_space_set_dim_name(__isl_take isl_space *space, - enum isl_dim_type type, unsigned pos, - __isl_keep const char *name); - __isl_keep const char *isl_space_get_dim_name(__isl_keep isl_space *space, - enum isl_dim_type type, unsigned pos); + __isl_give isl_space *isl_space_set_dim_name( + __isl_take isl_space *space, + enum isl_dim_type type, unsigned pos, + __isl_keep const char *name); + int isl_space_has_dim_name(__isl_keep isl_space *space, + enum isl_dim_type type, unsigned pos); + __isl_keep const char *isl_space_get_dim_name( + __isl_keep isl_space *space, + enum isl_dim_type type, unsigned pos); Note that C returns a pointer to some internal data structure, so the result can only be used while the @@ -721,6 +783,9 @@ using the following functions. unsigned n); __isl_give isl_space *isl_space_map_from_set( __isl_take isl_space *space); + __isl_give isl_space *isl_space_map_from_domain_and_range( + __isl_take isl_space *domain, + __isl_take isl_space *range); __isl_give isl_space *isl_space_zip(__isl_take isl_space *space); Note that if dimensions are added or removed from a space, then @@ -783,6 +848,8 @@ using the following functions. __isl_give isl_local_space *isl_local_space_domain( __isl_take isl_local_space *ls); + __isl_give isl_local_space *isl_local_space_range( + __isl_take isl_local_space *ls); __isl_give isl_local_space *isl_local_space_from_domain( __isl_take isl_local_space *ls); __isl_give isl_local_space *isl_local_space_intersect( @@ -1226,6 +1293,8 @@ L<"Piecewise Multiple Quasi Affine Expressions">). __isl_take isl_aff_list *list); __isl_give isl_basic_map *isl_basic_map_from_multi_aff( __isl_take isl_multi_aff *maff) + __isl_give isl_map *isl_map_from_multi_aff( + __isl_take isl_multi_aff *maff) __isl_give isl_set *isl_set_from_pw_multi_aff( __isl_take isl_pw_multi_aff *pma); __isl_give isl_map *isl_map_from_pw_multi_aff( @@ -1516,6 +1585,8 @@ read off using the following functions. const char *isl_basic_set_get_dim_name( __isl_keep isl_basic_set *bset, enum isl_dim_type type, unsigned pos); + int isl_set_has_dim_name(__isl_keep isl_set *set, + enum isl_dim_type type, unsigned pos); const char *isl_set_get_dim_name( __isl_keep isl_set *set, enum isl_dim_type type, unsigned pos); @@ -1563,6 +1634,8 @@ is already known to be empty. =item * Single-valuedness + int isl_map_plain_is_single_valued( + __isl_keep isl_map *map); int isl_map_is_single_valued(__isl_keep isl_map *map); int isl_union_map_is_single_valued(__isl_keep isl_union_map *umap); @@ -1656,6 +1729,9 @@ i.e., whether both domain and range are nested relations. =item * Subset + int isl_basic_set_is_subset( + __isl_keep isl_basic_set *bset1, + __isl_keep isl_basic_set *bset2); int isl_set_is_subset(__isl_keep isl_set *set1, __isl_keep isl_set *set2); int isl_set_is_strict_subset( @@ -1696,6 +1772,8 @@ i.e., whether both domain and range are nested relations. __isl_give isl_set *isl_set_complement( __isl_take isl_set *set); + __isl_give isl_map *isl_map_complement( + __isl_take isl_map *map); =item * Inverse map @@ -1762,6 +1840,9 @@ that maps (a wrapped version of) the input relation to its domain or range. __isl_take isl_basic_map *bmap, enum isl_dim_type type, unsigned first, unsigned n); + __isl_give isl_map *isl_map_eliminate( + __isl_take isl_map *map, enum isl_dim_type type, + unsigned first, unsigned n); Eliminate the coefficients for the given dimensions from the constraints, without removing the dimensions. @@ -1792,12 +1873,20 @@ dimension has the fixed given value. __isl_give isl_basic_map *isl_basic_map_lower_bound_si( __isl_take isl_basic_map *bmap, enum isl_dim_type type, unsigned pos, int value); + __isl_give isl_set *isl_set_lower_bound( + __isl_take isl_set *set, + enum isl_dim_type type, unsigned pos, + isl_int 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_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( + __isl_take isl_set *set, + enum isl_dim_type type, unsigned pos, + isl_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); @@ -1806,7 +1895,7 @@ dimension has the fixed given value. 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 the fixed given value. +dimension has a value bounded by the fixed given value. __isl_give isl_set *isl_set_equate(__isl_take isl_set *set, enum isl_dim_type type1, int pos1, @@ -1868,6 +1957,17 @@ basic set or relation. __isl_give isl_union_map *isl_union_map_coalesce( __isl_take isl_union_map *umap); +One of the methods for combining pairs of basic sets or relations +can result in coefficients that are much larger than those that appear +in the constraints of the input. By default, the coefficients are +not allowed to grow larger, but this can be changed by unsetting +the following option. + + int isl_options_set_coalesce_bounded_wrapping( + isl_ctx *ctx, int val); + int isl_options_get_coalesce_bounded_wrapping( + isl_ctx *ctx); + =item * Detecting equalities __isl_give isl_basic_set *isl_basic_set_detect_equalities( @@ -1962,6 +2062,20 @@ that contains the whole input set or relation. In case of union sets and relations, the polyhedral hull is computed per space. +=item * Feasibility + + __isl_give isl_basic_set *isl_basic_set_sample( + __isl_take isl_basic_set *bset); + __isl_give isl_basic_set *isl_set_sample( + __isl_take isl_set *set); + __isl_give isl_basic_map *isl_basic_map_sample( + __isl_take isl_basic_map *bmap); + __isl_give isl_basic_map *isl_map_sample( + __isl_take isl_map *map); + +If the input (basic) set or relation is non-empty, then return +a singleton subset of the input. Otherwise, return an empty set. + =item * Optimization #include @@ -2020,6 +2134,15 @@ dualization algorithms or skip the elimination step. =item * Power + __isl_give isl_map *isl_map_fixed_power( + __isl_take isl_map *map, isl_int exp); + __isl_give isl_union_map *isl_union_map_fixed_power( + __isl_take isl_union_map *umap, isl_int exp); + +Compute the given power of C, where C is assumed to be non-zero. +If the exponent C is negative, then the -C th power of the inverse +of C is computed. + __isl_give isl_map *isl_map_power(__isl_take isl_map *map, int *exact); __isl_give isl_union_map *isl_union_map_power( @@ -2435,6 +2558,9 @@ instead. __isl_give isl_union_map *isl_union_map_gist_domain( __isl_take isl_union_map *umap, __isl_take isl_union_set *uset); + __isl_give isl_union_map *isl_union_map_gist_range( + __isl_take isl_union_map *umap, + __isl_take isl_union_set *uset); The gist operation returns a set or relation that has the same intersection with the context as the input set or relation. @@ -2613,6 +2739,35 @@ Lists can be printed using __isl_take isl_printer *p, __isl_keep isl_set_list *list); +=head2 Vectors + +Vectors can be created, copied and freed using the following functions. + + #include + __isl_give isl_vec *isl_vec_alloc(isl_ctx *ctx, + unsigned size); + __isl_give isl_vec *isl_vec_copy(__isl_keep isl_vec *vec); + void isl_vec_free(__isl_take isl_vec *vec); + +Note that the elements of a newly created vector may have arbitrary values. +The elements can be changed and inspected using the following functions. + + isl_ctx *isl_vec_get_ctx(__isl_keep isl_vec *vec); + 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_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(__isl_take isl_vec *vec, + isl_int v); + __isl_give isl_vec *isl_vec_set_si(__isl_take isl_vec *vec, + int v); + +C will return a negative value if anything went wrong. +In that case, the value of C<*v> is undefined. + =head2 Matrices Matrices can be created, copied and freed using the following functions. @@ -2674,6 +2829,13 @@ be created using the following functions. __isl_give isl_pw_aff *isl_pw_aff_from_aff( __isl_take isl_aff *aff); +A piecewise quasi affine expression that is equal to 1 on a set +and 0 outside the set can be created using the following function. + + #include + __isl_give isl_pw_aff *isl_set_indicator_function( + __isl_take isl_set *set); + Quasi affine expressions can be copied and freed using #include @@ -2738,6 +2900,7 @@ The expression can be inspected using __isl_give isl_aff *isl_aff_get_div( __isl_keep isl_aff *aff, int pos); + int isl_pw_aff_n_piece(__isl_keep isl_pw_aff *pwaff); int isl_pw_aff_foreach_piece(__isl_keep isl_pw_aff *pwaff, int (*fn)(__isl_take isl_set *set, __isl_take isl_aff *aff, @@ -2882,10 +3045,16 @@ Operations include __isl_give isl_pw_aff *isl_pw_aff_coalesce( __isl_take isl_pw_aff *pwqp); + __isl_give isl_aff *isl_aff_align_params( + __isl_take isl_aff *aff, + __isl_take isl_space *model); __isl_give isl_pw_aff *isl_pw_aff_align_params( __isl_take isl_pw_aff *pwaff, __isl_take isl_space *model); + __isl_give isl_aff *isl_aff_project_domain_on_params( + __isl_take isl_aff *aff); + __isl_give isl_aff *isl_aff_gist_params( __isl_take isl_aff *aff, __isl_take isl_set *context); @@ -2982,14 +3151,14 @@ of C where C is non-negative. #include __isl_give isl_pw_aff *isl_pw_aff_cond( - __isl_take isl_set *cond, + __isl_take isl_pw_aff *cond, __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false); The function C performs a conditional operator and returns an expression that is equal to C -for elements in C and equal to C for elements -not in C. +for elements where C is non-zero and equal to C for elements +where C is zero. #include __isl_give isl_pw_aff *isl_pw_aff_union_min( @@ -3040,13 +3209,17 @@ following function. __isl_take isl_space *space, __isl_take isl_aff_list *list); -An empty piecewise multiple quasi affine expression (one with no cells) or +An empty piecewise multiple quasi affine expression (one with no cells), +the zero piecewise multiple quasi affine expression (with value zero +for each output dimension) or a piecewise multiple quasi affine expression with a single cell can be created using the following functions. #include __isl_give isl_pw_multi_aff *isl_pw_multi_aff_empty( __isl_take isl_space *space); + __isl_give isl_multi_aff *isl_multi_aff_zero( + __isl_take isl_space *space); __isl_give isl_pw_multi_aff *isl_pw_multi_aff_alloc( __isl_take isl_set *set, __isl_take isl_multi_aff *maff); @@ -3086,6 +3259,8 @@ The expression can be inspected using enum isl_dim_type type); __isl_give isl_aff *isl_multi_aff_get_aff( __isl_keep isl_multi_aff *multi, int pos); + __isl_give isl_pw_aff *isl_pw_multi_aff_get_pw_aff( + __isl_keep isl_pw_multi_aff *pma, int pos); const char *isl_pw_multi_aff_get_dim_name( __isl_keep isl_pw_multi_aff *pma, enum isl_dim_type type, unsigned pos); @@ -3114,13 +3289,23 @@ The expression can be inspected using It can be modified using #include + __isl_give isl_multi_aff *isl_multi_aff_set_aff( + __isl_take isl_multi_aff *multi, int pos, + __isl_take isl_aff *aff); __isl_give isl_multi_aff *isl_multi_aff_set_dim_name( __isl_take isl_multi_aff *maff, enum isl_dim_type type, unsigned pos, const char *s); + __isl_give isl_multi_aff *isl_multi_aff_set_tuple_id( + __isl_take isl_multi_aff *maff, + enum isl_dim_type type, __isl_take isl_id *id); __isl_give isl_pw_multi_aff *isl_pw_multi_aff_set_tuple_id( __isl_take isl_pw_multi_aff *pma, enum isl_dim_type type, __isl_take isl_id *id); + __isl_give isl_multi_aff *isl_multi_aff_drop_dims( + __isl_take isl_multi_aff *maff, + enum isl_dim_type type, unsigned first, unsigned n); + To check whether two multiple affine expressions are obviously equal to each other, use @@ -3154,6 +3339,8 @@ Operations include __isl_give isl_multi_aff *isl_multi_aff_lift( __isl_take isl_multi_aff *maff, __isl_give isl_local_space **ls); + __isl_give isl_pw_multi_aff *isl_pw_multi_aff_coalesce( + __isl_take isl_pw_multi_aff *pma); __isl_give isl_multi_aff *isl_multi_aff_gist_params( __isl_take isl_multi_aff *maff, __isl_take isl_set *context); @@ -3166,6 +3353,8 @@ Operations include __isl_give isl_pw_multi_aff *isl_pw_multi_aff_gist( __isl_take isl_pw_multi_aff *pma, __isl_take isl_set *set); + __isl_give isl_set *isl_pw_multi_aff_domain( + __isl_take isl_pw_multi_aff *pma); If the C argument of C is not C, then it is assigned the local space that lies at the basis of @@ -3406,7 +3595,7 @@ functions. __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_copy( __isl_keep isl_union_pw_qpolynomial *upwqp); - void isl_union_pw_qpolynomial_free( + void *isl_union_pw_qpolynomial_free( __isl_take isl_union_pw_qpolynomial *upwqp); =head3 Inspecting (Piecewise) Quasipolynomials @@ -3665,7 +3854,7 @@ following functions. __isl_take isl_qpolynomial_fold *fold); void *isl_pw_qpolynomial_fold_free( __isl_take isl_pw_qpolynomial_fold *pwf); - void isl_union_pw_qpolynomial_fold_free( + void *isl_union_pw_qpolynomial_fold_free( __isl_take isl_union_pw_qpolynomial_fold *upwf); =head3 Printing Piecewise Quasipolynomial Reductions @@ -3976,22 +4165,105 @@ Any of C, C, C or C may be C, but a C value for any of the other arguments is treated as an error. +=head3 Interaction with Dependence Analysis + +During the dependence analysis, we frequently need to perform +the following operation. Given a relation between sink iterations +and potential soure iterations from a particular source domain, +what is the last potential source iteration corresponding to each +sink iteration. It can sometimes be convenient to adjust +the set of potential source iterations before or after each such operation. +The prototypical example is fuzzy array dataflow analysis, +where we need to analyze if, based on data-dependent constraints, +the sink iteration can ever be executed without one or more of +the corresponding potential source iterations being executed. +If so, we can introduce extra parameters and select an unknown +but fixed source iteration from the potential source iterations. +To be able to perform such manipulations, C provides the following +function. + + #include + + typedef __isl_give isl_restriction *(*isl_access_restrict)( + __isl_keep isl_map *source_map, + __isl_keep isl_set *sink, void *source_user, + void *user); + __isl_give isl_access_info *isl_access_info_set_restrict( + __isl_take isl_access_info *acc, + isl_access_restrict fn, void *user); + +The function C should be called +before calling C and registers a callback function +that will be called any time C is about to compute the last +potential source. The first argument is the (reverse) proto-dependence, +mapping sink iterations to potential source iterations. +The second argument represents the sink iterations for which +we want to compute the last source iteration. +The third argument is the token corresponding to the source +and the final argument is the token passed to C. +The callback is expected to return a restriction on either the input or +the output of the operation computing the last potential source. +If the input needs to be restricted then restrictions are needed +for both the source and the sink iterations. The sink iterations +and the potential source iterations will be intersected with these sets. +If the output needs to be restricted then only a restriction on the source +iterations is required. +If any error occurs, the callback should return C. +An C object can be created and freed using the following +functions. + + #include + + __isl_give isl_restriction *isl_restriction_input( + __isl_take isl_set *source_restr, + __isl_take isl_set *sink_restr); + __isl_give isl_restriction *isl_restriction_output( + __isl_take isl_set *source_restr); + __isl_give isl_restriction *isl_restriction_none( + __isl_keep isl_map *source_map); + __isl_give isl_restriction *isl_restriction_empty( + __isl_keep isl_map *source_map); + void *isl_restriction_free( + __isl_take isl_restriction *restr); + +C and C are special +cases of C. C +is essentially equivalent to + + isl_restriction_input(isl_set_universe( + isl_space_range(isl_map_get_space(source_map))), + isl_set_universe( + isl_space_domain(isl_map_get_space(source_map)))); + +whereas C is essentially equivalent to + + isl_restriction_input(isl_set_empty( + isl_space_range(isl_map_get_space(source_map))), + isl_set_universe( + isl_space_domain(isl_map_get_space(source_map)))); + =head2 Scheduling B The following function can be used to compute a schedule -for a union of domains. The generated schedule respects -all C dependences. That is, all dependence distances -over these dependences in the scheduled space are lexicographically -positive. The generated schedule schedule also tries to minimize -the dependence distances over C dependences. +for a union of domains. +By default, the algorithm used to construct the schedule is similar +to that of C. +Alternatively, Feautrier's multi-dimensional scheduling algorithm can +be selected. +The generated schedule respects all C dependences. +That is, all dependence distances over these dependences in the +scheduled space are lexicographically positive. +The default algorithm tries to minimize the dependence distances over +C dependences. Moreover, it tries to obtain sequences (bands) of schedule dimensions for groups of domains where the dependence distances have only non-negative values. -The algorithm used to construct the schedule is similar to that -of C. +When using Feautrier's algorithm, the C dependence +distances are only minimized during the extension to a +full-dimensional schedule. #include __isl_give isl_schedule *isl_union_set_compute_schedule( @@ -4075,20 +4347,81 @@ A representation of the band can be printed using =head3 Options #include + int isl_options_set_schedule_max_coefficient( + isl_ctx *ctx, int val); + int isl_options_get_schedule_max_coefficient( + isl_ctx *ctx); + int isl_options_set_schedule_max_constant_term( + isl_ctx *ctx, int val); + int isl_options_get_schedule_max_constant_term( + isl_ctx *ctx); + int isl_options_set_schedule_maximize_band_depth( + isl_ctx *ctx, int val); + int isl_options_get_schedule_maximize_band_depth( + isl_ctx *ctx); int isl_options_set_schedule_outer_zero_distance( isl_ctx *ctx, int val); int isl_options_get_schedule_outer_zero_distance( isl_ctx *ctx); + int isl_options_set_schedule_split_scaled( + isl_ctx *ctx, int val); + int isl_options_get_schedule_split_scaled( + isl_ctx *ctx); + int isl_options_set_schedule_algorithm( + isl_ctx *ctx, int val); + int isl_options_get_schedule_algorithm( + isl_ctx *ctx); + =over +=item * schedule_max_coefficient + +This option enforces that the coefficients for variable and parameter +dimensions in the calculated schedule are not larger than the specified value. +This option can significantly increase the speed of the scheduling calculation +and may also prevent fusing of unrelated dimensions. A value of -1 means that +this option does not introduce bounds on the variable or parameter +coefficients. + +=item * schedule_max_constant_term + +This option enforces that the constant coefficients in the calculated schedule +are not larger than the maximal constant term. This option can significantly +increase the speed of the scheduling calculation and may also prevent fusing of +unrelated dimensions. A value of -1 means that this option does not introduce +bounds on the constant coefficients. + +=item * schedule_maximize_band_depth + +If this option is set, we do not split bands at the point +where we detect splitting is necessary. Instead, we +backtrack and split bands as early as possible. This +reduces the number of splits and maximizes the width of +the bands. Wider bands give more possibilities for tiling. + =item * schedule_outer_zero_distance -It this option is set, then we try to construct schedules +If this option is set, then we try to construct schedules where the outermost scheduling dimension in each band results in a zero dependence distance over the proximity dependences. +=item * schedule_split_scaled + +If this option is set, then we try to construct schedules in which the +constant term is split off from the linear part if the linear parts of +the scheduling rows for all nodes in the graphs have a common non-trivial +divisor. +The constant term is then placed in a separate band and the linear +part is reduced. + +=item * schedule_algorithm + +Selects the scheduling algorithm to be used. +Available scheduling algorithms are C +and C. + =back =head2 Parametric Vertex Enumeration