=item * The functions C<isl_printer_print_basic_set> and
C<isl_printer_print_basic_map> no longer print a newline.
+=item * The functions C<isl_flow_get_no_source>
+and C<isl_union_map_compute_flow> now return
+the accesses for which no source could be found instead of
+the iterations where those accesses occur.
+
+=item * The functions C<isl_basic_map_identity> and
+C<isl_map_identity> now take the dimension specification
+of a B<map> as input. An old call
+C<isl_map_identity(dim)> can be rewritten to
+C<isl_map_identity(isl_dim_map_from_set(dim))>.
+
+=item * The function C<isl_map_power> no longer takes
+a parameter position as input. Instead, the exponent
+is now expressed as the domain of the resulting relation.
+
+=back
+
+=head3 Changes since isl-0.06
+
+=over
+
+=item * The format of C<isl_printer_print_qpolynomial>'s
+C<ISL_FORMAT_ISL> output has changed.
+Use C<ISL_FORMAT_C> to obtain the old output.
+
=back
=head1 Installation
If the user still wants to use one or more of these arguments
after the function call, she should pass along a copy of the
object rather than the object itself.
-The user is then responsible for make sure that the original
+The user is then responsible for making sure that the original
object gets used somewhere else or is explicitly freed.
The arguments and return values of all documents functions are
__isl_give isl_dim *isl_union_map_get_dim(
__isl_keep isl_union_map *umap);
+ #include <isl/constraint.h>
+ __isl_give isl_dim *isl_constraint_get_dim(
+ __isl_keep isl_constraint *constraint);
+
#include <isl/polynomial.h>
__isl_give isl_dim *isl_qpolynomial_get_dim(
__isl_keep isl_qpolynomial *qp);
+ __isl_give isl_dim *isl_qpolynomial_fold_get_dim(
+ __isl_keep isl_qpolynomial_fold *fold);
__isl_give isl_dim *isl_pw_qpolynomial_get_dim(
__isl_keep isl_pw_qpolynomial *pwqp);
__isl_give isl_dim *isl_union_pw_qpolynomial_get_dim(
__isl_give isl_dim *isl_union_pw_qpolynomial_fold_get_dim(
__isl_keep isl_union_pw_qpolynomial_fold *upwf);
+ #include <isl/aff.h>
+ __isl_give isl_dim *isl_aff_get_dim(
+ __isl_keep isl_aff *aff);
+
The names of the individual dimensions may be set or read off
using the following functions.
__isl_give isl_dim *isl_dim_reverse(__isl_take isl_dim *dim);
__isl_give isl_dim *isl_dim_join(__isl_take isl_dim *left,
__isl_take isl_dim *right);
+ __isl_give isl_dim *isl_dim_align_params(
+ __isl_take isl_dim *dim1, __isl_take isl_dim *dim2)
__isl_give isl_dim *isl_dim_insert(__isl_take isl_dim *dim,
enum isl_dim_type type, unsigned pos, unsigned n);
__isl_give isl_dim *isl_dim_add(__isl_take isl_dim *dim,
enum isl_dim_type type, unsigned n);
__isl_give isl_dim *isl_dim_drop(__isl_take isl_dim *dim,
enum isl_dim_type type, unsigned first, unsigned n);
+ __isl_give isl_dim *isl_dim_map_from_set(
+ __isl_take isl_dim *dim);
+ __isl_give isl_dim *isl_dim_zip(__isl_take isl_dim *dim);
Note that if dimensions are added or removed from a space, then
the name and the internal structure are lost.
+=head2 Local Spaces
+
+A local space is essentially a dimension specification with
+zero or more existentially quantified variables.
+The local space of a basic set or relation can be obtained
+using the following functions.
+
+ #include <isl/set.h>
+ __isl_give isl_local_space *isl_basic_set_get_local_space(
+ __isl_keep isl_basic_set *bset);
+
+ #include <isl/map.h>
+ __isl_give isl_local_space *isl_basic_map_get_local_space(
+ __isl_keep isl_basic_map *bmap);
+
+A new local space can be created from a dimension specification using
+
+ #include <isl/local_space.h>
+ __isl_give isl_local_space *isl_local_space_from_dim(
+ __isl_take isl_dim *dim);
+
+They can be inspected, copied and freed using the following functions.
+
+ #include <isl/local_space.h>
+ isl_ctx *isl_local_space_get_ctx(
+ __isl_keep isl_local_space *ls);
+ int isl_local_space_dim(__isl_keep isl_local_space *ls,
+ enum isl_dim_type type);
+ const char *isl_local_space_get_dim_name(
+ __isl_keep isl_local_space *ls,
+ enum isl_dim_type type, unsigned pos);
+ __isl_give isl_dim *isl_local_space_get_dim(
+ __isl_keep isl_local_space *ls);
+ __isl_give isl_div *isl_local_space_get_div(
+ __isl_keep isl_local_space *ls, int pos);
+ __isl_give isl_local_space *isl_local_space_copy(
+ __isl_keep isl_local_space *ls);
+ void *isl_local_space_free(__isl_take isl_local_space *ls);
+
+Local spaces can be created from other local spaces
+using the following functions.
+
+ __isl_give isl_local_space *isl_local_space_from_domain(
+ __isl_take isl_local_space *ls);
+ __isl_give isl_local_space *isl_local_space_add_dim(
+ __isl_take isl_local_space *ls,
+ enum isl_dim_type type, unsigned n);
+
=head2 Input and Output
C<isl> supports its own input/output format, which is similar
const char *str, int nparam);
#include <isl/union_set.h>
+ __isl_give isl_union_set *isl_union_set_read_from_file(
+ isl_ctx *ctx, FILE *input);
__isl_give isl_union_set *isl_union_set_read_from_str(
struct isl_ctx *ctx, const char *str);
#include <isl/union_map.h>
+ __isl_give isl_union_map *isl_union_map_read_from_file(
+ isl_ctx *ctx, FILE *input);
__isl_give isl_union_map *isl_union_map_read_from_str(
struct isl_ctx *ctx, const char *str);
__isl_take isl_printer *p, int output_format);
__isl_give isl_printer *isl_printer_set_indent(
__isl_take isl_printer *p, int indent);
+ __isl_give isl_printer *isl_printer_indent(
+ __isl_take isl_printer *p, int indent);
__isl_give isl_printer *isl_printer_set_prefix(
__isl_take isl_printer *p, const char *prefix);
__isl_give isl_printer *isl_printer_set_suffix(
The C<output_format> may be either C<ISL_FORMAT_ISL>, C<ISL_FORMAT_OMEGA>,
C<ISL_FORMAT_POLYLIB>, C<ISL_FORMAT_EXT_POLYLIB> or C<ISL_FORMAT_LATEX>
and defaults to C<ISL_FORMAT_ISL>.
-Each line in the output is indented by C<indent> spaces
+Each line in the output is indented by C<indent> (set by
+C<isl_printer_set_indent>) spaces
(default: 0), prefixed by C<prefix> and suffixed by C<suffix>.
In the C<PolyLib> format output,
the coefficients of the existentially quantified variables
appear between those of the set variables and those
of the parameters.
+The function C<isl_printer_indent> increases the indentation
+by the specified amount (which may be negative).
To actually print something, use
__isl_take isl_dim *dim);
__isl_give isl_map *isl_map_universe(
__isl_take isl_dim *dim);
+ __isl_give isl_union_set *isl_union_set_universe(
+ __isl_take isl_union_set *uset);
+ __isl_give isl_union_map *isl_union_map_universe(
+ __isl_take isl_union_map *umap);
+
+The sets and relations constructed by the functions above
+contain all integer values, while those constructed by the
+functions below only contain non-negative values.
+
+ __isl_give isl_basic_set *isl_basic_set_nat_universe(
+ __isl_take isl_dim *dim);
+ __isl_give isl_basic_map *isl_basic_map_nat_universe(
+ __isl_take isl_dim *dim);
+ __isl_give isl_set *isl_set_nat_universe(
+ __isl_take isl_dim *dim);
+ __isl_give isl_map *isl_map_nat_universe(
+ __isl_take isl_dim *dim);
=item * Identity relations
__isl_give isl_basic_map *isl_basic_map_identity(
- __isl_take isl_dim *set_dim);
+ __isl_take isl_dim *dim);
__isl_give isl_map *isl_map_identity(
- __isl_take isl_dim *set_dim);
+ __isl_take isl_dim *dim);
-These functions take a dimension specification for a B<set>
-and return an identity relation between two such sets.
+The number of input and output dimensions in C<dim> needs
+to be the same.
=item * Lexicographic order
inequality constraints and then projecting out the
existentially quantified variables, if any.
Constraints can be constructed, manipulated and
-added to basic sets and relations using the following functions.
+added to (basic) sets and relations using the following functions.
#include <isl/constraint.h>
__isl_give isl_constraint *isl_equality_alloc(
__isl_give isl_basic_set *isl_basic_set_add_constraint(
__isl_take isl_basic_set *bset,
__isl_take isl_constraint *constraint);
+ __isl_give isl_map *isl_map_add_constraint(
+ __isl_take isl_map *map,
+ __isl_take isl_constraint *constraint);
+ __isl_give isl_set *isl_set_add_constraint(
+ __isl_take isl_set *set,
+ __isl_take isl_constraint *constraint);
For example, to create a set containing the even integers
between 10 and 42, you would use the following code.
of C<isl_dim_cst>, C<isl_dim_param>,
C<isl_dim_in>, C<isl_dim_out> and C<isl_dim_div> for relations.
+A basic relation can also be constructed from an affine expression
+or a list of affine expressions (See L<"Quasi Affine Expressions">).
+
+ __isl_give isl_basic_map *isl_basic_map_from_aff(
+ __isl_take isl_aff *aff);
+ __isl_give isl_basic_map *isl_basic_map_from_aff_list(
+ __isl_take isl_dim *domain_dim,
+ __isl_take isl_aff_list *list);
+
+The C<domain_dim> argument describes the domain of the resulting
+basic relation. It is required because the C<list> may consist
+of zero affine expressions.
+
=head2 Inspecting Sets and Relations
Usually, the user should not have to care about the actual constraints
__isl_take isl_basic_map *bmap);
__isl_give isl_set *isl_set_remove_divs(
__isl_take isl_set *set);
+ __isl_give isl_map *isl_map_remove_divs(
+ __isl_take isl_map *map);
To iterate over all the sets or maps in a union set or map, use
void isl_constraint_get_coefficient(
__isl_keep isl_constraint *constraint,
enum isl_dim_type type, int pos, isl_int *v);
+ int isl_constraint_involves_dims(
+ __isl_keep isl_constraint *constraint,
+ enum isl_dim_type type, unsigned first, unsigned n);
The explicit representations of the existentially quantified
variables can be inspected using the following functions.
__isl_give isl_div *isl_constraint_div(
__isl_keep isl_constraint *constraint, int pos);
+ isl_ctx *isl_div_get_ctx(__isl_keep isl_div *div);
void isl_div_get_constant(__isl_keep isl_div *div,
isl_int *v);
void isl_div_get_denominator(__isl_keep isl_div *div,
The names of the domain and range spaces of a set or relation can be
read off using the following functions.
+ const char *isl_basic_set_get_tuple_name(
+ __isl_keep isl_basic_set *bset);
const char *isl_set_get_tuple_name(
__isl_keep isl_set *set);
const char *isl_basic_map_get_tuple_name(
const char *isl_constraint_get_dim_name(
__isl_keep isl_constraint *constraint,
enum isl_dim_type type, unsigned pos);
+ const char *isl_basic_set_get_dim_name(
+ __isl_keep isl_basic_set *bset,
+ 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);
=item * Emptiness
The following functions test whether the given set or relation
-contains any integer points. The ``fast'' variants do not perform
+contains any integer points. The ``plain'' variants do not perform
any computations, but simply check if the given set or relation
is already known to be empty.
- int isl_basic_set_fast_is_empty(__isl_keep isl_basic_set *bset);
+ int isl_basic_set_plain_is_empty(__isl_keep isl_basic_set *bset);
int isl_basic_set_is_empty(__isl_keep isl_basic_set *bset);
+ int isl_set_plain_is_empty(__isl_keep isl_set *set);
int isl_set_is_empty(__isl_keep isl_set *set);
int isl_union_set_is_empty(__isl_keep isl_union_set *uset);
- int isl_basic_map_fast_is_empty(__isl_keep isl_basic_map *bmap);
+ int isl_basic_map_plain_is_empty(__isl_keep isl_basic_map *bmap);
int isl_basic_map_is_empty(__isl_keep isl_basic_map *bmap);
- int isl_map_fast_is_empty(__isl_keep isl_map *map);
+ int isl_map_plain_is_empty(__isl_keep isl_map *map);
int isl_map_is_empty(__isl_keep isl_map *map);
int isl_union_map_is_empty(__isl_keep isl_union_map *umap);
int isl_basic_set_is_universe(__isl_keep isl_basic_set *bset);
int isl_basic_map_is_universe(__isl_keep isl_basic_map *bmap);
- int isl_set_fast_is_universe(__isl_keep isl_set *set);
+ int isl_set_plain_is_universe(__isl_keep isl_set *set);
=item * Single-valuedness
int isl_map_is_single_valued(__isl_keep isl_map *map);
+ int isl_union_map_is_single_valued(__isl_keep isl_union_map *umap);
+
+=item * Injectivity
+
+ int isl_map_plain_is_injective(__isl_keep isl_map *map);
+ int isl_map_is_injective(__isl_keep isl_map *map);
+ int isl_union_map_plain_is_injective(
+ __isl_keep isl_union_map *umap);
+ int isl_union_map_is_injective(
+ __isl_keep isl_union_map *umap);
=item * Bijectivity
int isl_map_is_bijective(__isl_keep isl_map *map);
+ int isl_union_map_is_bijective(__isl_keep isl_union_map *umap);
=item * Wrapping
-The followning functions check whether the domain of the given
+The following functions check whether the domain of the given
(basic) set is a wrapped relation.
int isl_basic_set_is_wrapping(
__isl_keep isl_basic_set *bset);
int isl_set_is_wrapping(__isl_keep isl_set *set);
+=item * Internal Product
+
+ int isl_basic_map_can_zip(
+ __isl_keep isl_basic_map *bmap);
+ int isl_map_can_zip(__isl_keep isl_map *map);
+
+Check whether the product of domain and range of the given relation
+can be computed,
+i.e., whether both domain and range are nested relations.
+
=back
=head3 Binary Properties
=item * Equality
- int isl_set_fast_is_equal(__isl_keep isl_set *set1,
+ int isl_set_plain_is_equal(__isl_keep isl_set *set1,
__isl_keep isl_set *set2);
int isl_set_is_equal(__isl_keep isl_set *set1,
__isl_keep isl_set *set2);
__isl_keep isl_basic_map *bmap2);
int isl_map_is_equal(__isl_keep isl_map *map1,
__isl_keep isl_map *map2);
- int isl_map_fast_is_equal(__isl_keep isl_map *map1,
+ int isl_map_plain_is_equal(__isl_keep isl_map *map1,
__isl_keep isl_map *map2);
int isl_union_map_is_equal(
__isl_keep isl_union_map *umap1,
=item * Disjointness
- int isl_set_fast_is_disjoint(__isl_keep isl_set *set1,
+ int isl_set_plain_is_disjoint(__isl_keep isl_set *set1,
__isl_keep isl_set *set2);
=item * Subset
The functions above construct a (basic, regular or union) relation
that maps (a wrapped version of) the input relation to its domain or range.
+=item * Elimination
+
+ __isl_give isl_set *isl_set_eliminate(
+ __isl_take isl_set *set, enum isl_dim_type type,
+ unsigned first, unsigned n);
+
+Eliminate the coefficients for the given dimensions from the constraints,
+without removing the dimensions.
+
+=item * Slicing
+
+ __isl_give isl_basic_set *isl_basic_set_fix(
+ __isl_take isl_basic_set *bset,
+ enum isl_dim_type type, unsigned pos,
+ isl_int value);
+ __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_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_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_map *isl_map_fix_si(__isl_take isl_map *map,
+ enum isl_dim_type type, unsigned pos, int value);
+
+Intersect the set or relation with the hyperplane where the given
+dimension has the fixed given value.
+
=item * Identity
__isl_give isl_map *isl_set_identity(
These functions return a (basic) set containing the differences
between image elements and corresponding domain elements in the input.
+ __isl_give isl_basic_map *isl_basic_map_deltas_map(
+ __isl_take isl_basic_map *bmap);
+ __isl_give isl_map *isl_map_deltas_map(
+ __isl_take isl_map *map);
+ __isl_give isl_union_map *isl_union_map_deltas_map(
+ __isl_take isl_union_map *umap);
+
+The functions above construct a (basic, regular or union) relation
+that maps (a wrapped version of) the input relation to its delta set.
+
=item * Coalescing
Simplify the representation of a set or relation by trying
__isl_give isl_union_map *isl_union_map_coalesce(
__isl_take isl_union_map *umap);
+=item * Detecting equalities
+
+ __isl_give isl_basic_set *isl_basic_set_detect_equalities(
+ __isl_take isl_basic_set *bset);
+ __isl_give isl_basic_map *isl_basic_map_detect_equalities(
+ __isl_take isl_basic_map *bmap);
+ __isl_give isl_set *isl_set_detect_equalities(
+ __isl_take isl_set *set);
+ __isl_give isl_map *isl_map_detect_equalities(
+ __isl_take isl_map *map);
+ __isl_give isl_union_set *isl_union_set_detect_equalities(
+ __isl_take isl_union_set *uset);
+ __isl_give isl_union_map *isl_union_map_detect_equalities(
+ __isl_take isl_union_map *umap);
+
+Simplify the representation of a set or relation by detecting implicit
+equalities.
+
+=item * Removing redundant constraints
+
+ __isl_give isl_basic_set *isl_basic_set_remove_redundancies(
+ __isl_take isl_basic_set *bset);
+ __isl_give isl_basic_map *isl_basic_map_remove_redundancies(
+ __isl_take isl_basic_map *bmap);
+
=item * Convex hull
__isl_give isl_basic_set *isl_set_convex_hull(
__isl_take isl_set *set);
__isl_give isl_basic_map *isl_map_simple_hull(
__isl_take isl_map *map);
+ __isl_give isl_union_map *isl_union_map_simple_hull(
+ __isl_take isl_union_map *umap);
These functions compute a single basic set or relation
that contains the whole input set or relation.
In case of union sets and relations, the polyhedral hull is computed
per space.
+=item * Optimization
+
+ #include <isl/ilp.h>
+ enum isl_lp_result isl_basic_set_max(
+ __isl_keep isl_basic_set *bset,
+ __isl_keep isl_aff *obj, isl_int *opt)
+ enum isl_lp_result isl_set_max(__isl_keep isl_set *set,
+ __isl_keep isl_aff *obj, isl_int *opt);
+
+Compute the 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>.
+
+=item * Dual
+
+The following functions compute either the set of (rational) coefficient
+values of valid constraints for the given set or the set of (rational)
+values satisfying the constraints with coefficients from the given set.
+Internally, these two sets of functions perform essentially the
+same operations, except that the set of coefficients is assumed to
+be a cone, while the set of values may be any polyhedron.
+The current implementation is based on the Farkas lemma and
+Fourier-Motzkin elimination, but this may change or be made optional
+in future. In particular, future implementations may use different
+dualization algorithms or skip the elimination step.
+
+ __isl_give isl_basic_set *isl_basic_set_coefficients(
+ __isl_take isl_basic_set *bset);
+ __isl_give isl_basic_set *isl_set_coefficients(
+ __isl_take isl_set *set);
+ __isl_give isl_union_set *isl_union_set_coefficients(
+ __isl_take isl_union_set *bset);
+ __isl_give isl_basic_set *isl_basic_set_solutions(
+ __isl_take isl_basic_set *bset);
+ __isl_give isl_basic_set *isl_set_solutions(
+ __isl_take isl_set *set);
+ __isl_give isl_union_set *isl_union_set_solutions(
+ __isl_take isl_union_set *bset);
+
=item * Power
__isl_give isl_map *isl_map_power(__isl_take isl_map *map,
- unsigned param, int *exact);
+ int *exact);
+ __isl_give isl_union_map *isl_union_map_power(
+ __isl_take isl_union_map *umap, int *exact);
Compute a parametric representation for all positive powers I<k> of C<map>.
-The power I<k> is equated to the parameter at position C<param>.
-The result may be an overapproximation. If the result is exact,
+The result maps I<k> to a nested relation corresponding to the
+I<k>th power of C<map>.
+The result may be an overapproximation. If the result is known to be exact,
then C<*exact> is set to C<1>.
-The current implementation only produces exact results for particular
-cases of piecewise translations (i.e., piecewise uniform dependences).
=item * Transitive closure
Compute the transitive closure of C<map>.
The result may be an overapproximation. If the result is known to be exact,
then C<*exact> is set to C<1>.
-The current implementation only produces exact results for particular
-cases of piecewise translations (i.e., piecewise uniform dependences).
=item * Reaching path lengths
set or relation. If there is any such internal structure in the input,
then the name of the space is also removed.
+ __isl_give isl_basic_set *isl_basic_set_flatten(
+ __isl_take isl_basic_set *bset);
__isl_give isl_set *isl_set_flatten(
__isl_take isl_set *set);
+ __isl_give isl_basic_map *isl_basic_map_flatten_range(
+ __isl_take isl_basic_map *bmap);
+ __isl_give isl_map *isl_map_flatten_range(
+ __isl_take isl_map *map);
+ __isl_give isl_basic_map *isl_basic_map_flatten(
+ __isl_take isl_basic_map *bmap);
__isl_give isl_map *isl_map_flatten(
__isl_take isl_map *map);
The function above constructs a relation
that maps the input set to a flattened version of the set.
+=item * Lifting
+
+Lift the input set to a space with extra dimensions corresponding
+to the existentially quantified variables in the input.
+In particular, the result lives in a wrapped map where the domain
+is the original space and the range corresponds to the original
+existentially quantified variables.
+
+ __isl_give isl_basic_set *isl_basic_set_lift(
+ __isl_take isl_basic_set *bset);
+ __isl_give isl_set *isl_set_lift(
+ __isl_take isl_set *set);
+ __isl_give isl_union_set *isl_union_set_lift(
+ __isl_take isl_union_set *uset);
+
+=item * Internal Product
+
+ __isl_give isl_basic_map *isl_basic_map_zip(
+ __isl_take isl_basic_map *bmap);
+ __isl_give isl_map *isl_map_zip(
+ __isl_take isl_map *map);
+ __isl_give isl_union_map *isl_union_map_zip(
+ __isl_take isl_union_map *umap);
+
+Given a relation with nested relations for domain and range,
+interchange the range of the domain with the domain of the range.
+
+=item * Aligning parameters
+
+ __isl_give isl_set *isl_set_align_params(
+ __isl_take isl_set *set,
+ __isl_take isl_dim *model);
+ __isl_give isl_map *isl_map_align_params(
+ __isl_take isl_map *map,
+ __isl_take isl_dim *model);
+
+Change the order of the parameters of the given set or relation
+such that the first parameters match those of C<model>.
+This may involve the introduction of extra parameters.
+All parameters need to be named.
+
=item * Dimension manipulation
__isl_give isl_set *isl_set_add_dims(
It is usually not advisable to directly change the (input or output)
space of a set or a relation as this removes the name and the internal
structure of the space. However, the above functions can be useful
-to add new parameters.
+to add new parameters, assuming
+C<isl_set_align_params> and C<isl_map_align_params>
+are not sufficient.
=back
__isl_take isl_union_map *umap1,
__isl_take isl_union_map *umap2);
+=item * Cartesian Product
+
+ __isl_give isl_set *isl_set_product(
+ __isl_take isl_set *set1,
+ __isl_take isl_set *set2);
+ __isl_give isl_union_set *isl_union_set_product(
+ __isl_take isl_union_set *uset1,
+ __isl_take isl_union_set *uset2);
+ __isl_give isl_basic_map *isl_basic_map_range_product(
+ __isl_take isl_basic_map *bmap1,
+ __isl_take isl_basic_map *bmap2);
+ __isl_give isl_map *isl_map_range_product(
+ __isl_take isl_map *map1,
+ __isl_take isl_map *map2);
+ __isl_give isl_union_map *isl_union_map_range_product(
+ __isl_take isl_union_map *umap1,
+ __isl_take isl_union_map *umap2);
+ __isl_give isl_map *isl_map_product(
+ __isl_take isl_map *map1,
+ __isl_take isl_map *map2);
+ __isl_give isl_union_map *isl_union_map_product(
+ __isl_take isl_union_map *umap1,
+ __isl_take isl_union_map *umap2);
+
+The above functions compute the cross product of the given
+sets or relations. The domains and ranges of the results
+are wrapped maps between domains and ranges of the inputs.
+To obtain a ``flat'' product, use the following functions
+instead.
+
+ __isl_give isl_basic_set *isl_basic_set_flat_product(
+ __isl_take isl_basic_set *bset1,
+ __isl_take isl_basic_set *bset2);
+ __isl_give isl_set *isl_set_flat_product(
+ __isl_take isl_set *set1,
+ __isl_take isl_set *set2);
+ __isl_give isl_basic_map *isl_basic_map_flat_range_product(
+ __isl_take isl_basic_map *bmap1,
+ __isl_take isl_basic_map *bmap2);
+ __isl_give isl_map *isl_map_flat_range_product(
+ __isl_take isl_map *map1,
+ __isl_take isl_map *map2);
+ __isl_give isl_union_map *isl_union_map_flat_range_product(
+ __isl_take isl_union_map *umap1,
+ __isl_take isl_union_map *umap2);
+ __isl_give isl_basic_map *isl_basic_map_flat_product(
+ __isl_take isl_basic_map *bmap1,
+ __isl_take isl_basic_map *bmap2);
+ __isl_give isl_map *isl_map_flat_product(
+ __isl_take isl_map *map1,
+ __isl_take isl_map *map2);
+
=item * Simplification
__isl_give isl_basic_set *isl_basic_set_gist(
__isl_give isl_union_map *isl_union_map_lexmax(
__isl_take isl_union_map *umap);
+=head2 Lists
+
+Lists are defined over several element types, including
+C<isl_aff>, C<isl_basic_set> and C<isl_set>.
+Here we take lists of C<isl_set>s as an example.
+Lists can be created, copied and freed using the following functions.
+
+ #include <isl/list.h>
+ __isl_give isl_set_list *isl_set_list_alloc(
+ isl_ctx *ctx, int n);
+ __isl_give isl_set_list *isl_set_list_copy(
+ __isl_keep isl_set_list *list);
+ __isl_give isl_set_list *isl_set_list_add(
+ __isl_take isl_set_list *list,
+ __isl_take isl_set *el);
+ void isl_set_list_free(__isl_take isl_set_list *list);
+
+C<isl_set_list_alloc> creates an empty list with a capacity for
+C<n> elements.
+
+Lists can be inspected using the following functions.
+
+ #include <isl/list.h>
+ isl_ctx *isl_set_list_get_ctx(__isl_keep isl_set_list *list);
+ int isl_set_list_n_set(__isl_keep isl_set_list *list);
+ __isl_give struct isl_set *isl_set_list_get_set(
+ __isl_keep isl_set_list *list, int index);
+ int isl_set_list_foreach(__isl_keep isl_set_list *list,
+ int (*fn)(__isl_take struct isl_set *el, void *user),
+ void *user);
+
+Lists can be printed using
+
+ #include <isl/list.h>
+ __isl_give isl_printer *isl_printer_print_set_list(
+ __isl_take isl_printer *p,
+ __isl_keep isl_set_list *list);
+
=head2 Matrices
Matrices can be created, copied and freed using the following functions.
Note that the elements of a newly created matrix may have arbitrary values.
The elements can be changed and inspected using the following functions.
+ isl_ctx *isl_mat_get_ctx(__isl_keep isl_mat *mat);
int isl_mat_rows(__isl_keep isl_mat *mat);
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_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);
C<isl_mat_get_element> will return a negative value if anything went wrong.
In that case, the value of C<*v> is undefined.
__isl_give isl_mat *isl_mat_right_kernel(__isl_take isl_mat *mat);
+=head2 Quasi Affine Expressions
+
+The zero quasi affine expression can be created using
+
+ __isl_give isl_aff *isl_aff_zero(
+ __isl_take isl_local_space *ls);
+
+Quasi affine expressions can be copied and free using
+
+ #include <isl/aff.h>
+ __isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff);
+ void *isl_aff_free(__isl_take isl_aff *aff);
+
+A (rational) bound on a dimension can be extracted from an C<isl_constraint>
+using the following function. The constraint is required to have
+a non-zero coefficient for the specified dimension.
+
+ #include <isl/constraint.h>
+ __isl_give isl_aff *isl_constraint_get_bound(
+ __isl_keep isl_constraint *constraint,
+ enum isl_dim_type type, int pos);
+
+Conversely, an equality constraint equating
+the affine expression to zero or an inequality constraint enforcing
+the affine expression to be non-negative, can be constructed using
+
+ __isl_give isl_constraint *isl_equality_from_aff(
+ __isl_take isl_aff *aff);
+ __isl_give isl_constraint *isl_inequality_from_aff(
+ __isl_take isl_aff *aff);
+
+The expression can be inspected using
+
+ #include <isl/aff.h>
+ isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff);
+ int isl_aff_dim(__isl_keep isl_aff *aff,
+ enum isl_dim_type type);
+ __isl_give isl_local_space *isl_aff_get_local_space(
+ __isl_keep isl_aff *aff);
+ const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff,
+ enum isl_dim_type type, unsigned pos);
+ int isl_aff_get_constant(__isl_keep isl_aff *aff,
+ isl_int *v);
+ int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
+ enum isl_dim_type type, int pos, isl_int *v);
+ int isl_aff_get_denominator(__isl_keep isl_aff *aff,
+ isl_int *v);
+ __isl_give isl_div *isl_aff_get_div(
+ __isl_keep isl_aff *aff, int pos);
+
+It can be modified using
+
+ #include <isl/aff.h>
+ __isl_give isl_aff *isl_aff_set_constant(
+ __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_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_denominator(
+ __isl_take isl_aff *aff, isl_int v);
+
+ __isl_give isl_aff *isl_aff_add_constant(
+ __isl_take isl_aff *aff, isl_int v);
+ __isl_give isl_aff *isl_aff_add_coefficient_si(
+ __isl_take isl_aff *aff,
+ enum isl_dim_type type, int pos, int v);
+
+Note that the C<set_constant> and C<set_coefficient> functions
+set the I<numerator> of the constant or coefficient, while
+C<add_constant> and C<add_coefficient> add an integer value to
+the possibly rational constant or coefficient.
+
+Operations include
+
+ #include <isl/aff.h>
+ __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
+ __isl_take isl_aff *aff2);
+ __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
+ __isl_take isl_aff *aff2);
+ __isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff);
+ __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff);
+ __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff,
+ isl_int f);
+ __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff,
+ isl_int f);
+
+An expression can be printed using
+
+ #include <isl/aff.h>
+ __isl_give isl_printer *isl_printer_print_aff(
+ __isl_take isl_printer *p, __isl_keep isl_aff *aff);
+
=head2 Points
Points are elements of a set. They can be used to construct
__isl_take isl_point *pnt,
enum isl_dim_type type, int pos, unsigned val);
+Other properties can be obtained using
+
+ isl_ctx *isl_point_get_ctx(__isl_keep isl_point *pnt);
+
Points can be copied or freed using
__isl_give isl_point *isl_point_copy(
__isl_give isl_qpolynomial *isl_qpolynomial_var(
__isl_take isl_dim *dim,
enum isl_dim_type type, unsigned pos);
+ __isl_give isl_qpolynomial *isl_qpolynomial_from_aff(
+ __isl_take isl_aff *aff);
The zero piecewise quasipolynomial or a piecewise quasipolynomial
with a single cell can be created using the following functions.
__isl_take isl_union_pw_qpolynomial *upwpq,
__isl_take isl_union_set *uset);
+ __isl_give isl_qpolynomial *isl_qpolynomial_align_params(
+ __isl_take isl_qpolynomial *qp,
+ __isl_take isl_dim *model);
+
__isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_coalesce(
__isl_take isl_union_pw_qpolynomial *upwqp);
+ __isl_give isl_qpolynomial *isl_qpolynomial_gist(
+ __isl_take isl_qpolynomial *qp,
+ __isl_take isl_set *context);
+
__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_gist(
__isl_take isl_pw_qpolynomial *pwqp,
__isl_take isl_set *context);
to simplify the quasipolynomial reductions associated to each cell.
__isl_give isl_pw_qpolynomial_fold *
+ isl_set_apply_pw_qpolynomial_fold(
+ __isl_take isl_set *set,
+ __isl_take isl_pw_qpolynomial_fold *pwf,
+ int *tight);
+ __isl_give isl_pw_qpolynomial_fold *
isl_map_apply_pw_qpolynomial_fold(
__isl_take isl_map *map,
__isl_take isl_pw_qpolynomial_fold *pwf,
int *tight);
__isl_give isl_union_pw_qpolynomial_fold *
+ isl_union_set_apply_union_pw_qpolynomial_fold(
+ __isl_take isl_union_set *uset,
+ __isl_take isl_union_pw_qpolynomial_fold *upwf,
+ int *tight);
+ __isl_give isl_union_pw_qpolynomial_fold *
isl_union_map_apply_union_pw_qpolynomial_fold(
__isl_take isl_union_map *umap,
__isl_take isl_union_pw_qpolynomial_fold *upwf,
int *tight);
-These functions
+The functions taking a map
compose the given map with the given piecewise quasipolynomial reduction.
That is, compute a bound (of the same type as C<pwf> or C<upwf> itself)
over all elements in the intersection of the range of the map
and the domain of the piecewise quasipolynomial reduction
as a function of an element in the domain of the map.
+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 Dependence Analysis
int (*fn)(__isl_take isl_map *dep, int must,
void *dep_user, void *user),
void *user);
- __isl_give isl_set *isl_flow_get_no_source(
+ __isl_give isl_map *isl_flow_get_no_source(
__isl_keep isl_flow *deps, int must);
void isl_flow_free(__isl_take isl_flow *deps);
C<isl_access_info_compute_flow>.
The result of the dependence analysis is collected in an
-C<isl_flow>. There may be elements in the domain of
+C<isl_flow>. There may be elements of
the sink access for which no preceding source access could be
found or for which all preceding sources are I<may> accesses.
-The sets of these elements can be obtained through
+The relations containing these elements can be obtained through
calls to C<isl_flow_get_no_source>, the first with C<must> set
and the second with C<must> unset.
In the case of standard flow dependence analysis,
with the sink a read and the sources I<must> writes,
-the first set corresponds to the reads from uninitialized
-array elements and the second set is empty.
+the first relation corresponds to the reads from uninitialized
+array elements and the second relation is empty.
The actual flow dependences can be extracted using
C<isl_flow_foreach>. This function will call the user-specified
callback function C<fn> for each B<non-empty> dependence between
__isl_take isl_union_map *schedule,
__isl_give isl_union_map **must_dep,
__isl_give isl_union_map **may_dep,
- __isl_give isl_union_set **must_no_source,
- __isl_give isl_union_set **may_no_source);
+ __isl_give isl_union_map **must_no_source,
+ __isl_give isl_union_map **may_no_source);
The arrays are identified by the tuple names of the ranges
of the accesses. The iteration domains by the tuple names
of the domains of the accesses and of the schedule.
The relative order of the iteration domains is given by the
-schedule. Any of C<must_dep>, C<may_dep>, C<must_no_source>
+schedule. The relations returned through C<must_no_source>
+and C<may_no_source> are subsets of C<sink>.
+Any of C<must_dep>, C<may_dep>, C<must_no_source>
or C<may_no_source> may be C<NULL>, but a C<NULL> value for
any of the other arguments is treated as an error.
+=head2 Scheduling
+
+B<The functionality described in this section is fairly new
+and may be subject to change.>
+
+The following function can be used to compute a schedule
+for a union of domains. The generated schedule respects
+all C<validity> 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<proximity> 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<Pluto>.
+
+ #include <isl/schedule.h>
+ __isl_give isl_schedule *isl_union_set_compute_schedule(
+ __isl_take isl_union_set *domain,
+ __isl_take isl_union_map *validity,
+ __isl_take isl_union_map *proximity);
+ void *isl_schedule_free(__isl_take isl_schedule *sched);
+
+A mapping from the domains to the scheduled space can be obtained
+from an C<isl_schedule> using the following function.
+
+ __isl_give isl_union_map *isl_schedule_get_map(
+ __isl_keep isl_schedule *sched);
+
+A representation of the schedule can be printed using
+
+ __isl_give isl_printer *isl_printer_print_schedule(
+ __isl_take isl_printer *p,
+ __isl_keep isl_schedule *schedule);
+
+A representation of the schedule as a forest of bands can be obtained
+using the following function.
+
+ __isl_give isl_band_list *isl_schedule_get_band_forest(
+ __isl_keep isl_schedule *schedule);
+
+The list can be manipulated as explained in L<"Lists">.
+The bands inside the list can be copied and freed using the following
+functions.
+
+ #include <isl/band.h>
+ __isl_give isl_band *isl_band_copy(
+ __isl_keep isl_band *band);
+ void *isl_band_free(__isl_take isl_band *band);
+
+Each band contains zero or more scheduling dimensions.
+These are referred to as the members of the band.
+The section of the schedule that corresponds to the band is
+referred to as the partial schedule of the band.
+For those nodes that participate in a band, the outer scheduling
+dimensions form the prefix schedule, while the inner scheduling
+dimensions form the suffix schedule.
+That is, if we take a cut of the band forest, then the union of
+the concatenations of the prefix, partial and suffix schedules of
+each band in the cut is equal to the entire schedule (modulo
+some possible padding at the end with zero scheduling dimensions).
+The properties of a band can be inspected using the following functions.
+
+ #include <isl/band.h>
+ isl_ctx *isl_band_get_ctx(__isl_keep isl_band *band);
+
+ int isl_band_has_children(__isl_keep isl_band *band);
+ __isl_give isl_band_list *isl_band_get_children(
+ __isl_keep isl_band *band);
+
+ __isl_give isl_union_map *isl_band_get_prefix_schedule(
+ __isl_keep isl_band *band);
+ __isl_give isl_union_map *isl_band_get_partial_schedule(
+ __isl_keep isl_band *band);
+ __isl_give isl_union_map *isl_band_get_suffix_schedule(
+ __isl_keep isl_band *band);
+
+ int isl_band_n_member(__isl_keep isl_band *band);
+ int isl_band_member_is_zero_distance(
+ __isl_keep isl_band *band, int pos);
+
+Note that a scheduling dimension is considered to be ``zero
+distance'' if it does not carry any proximity dependences
+within its band.
+That is, if the dependence distances of the proximity
+dependences are all zero in that direction (for fixed
+iterations of outer bands).
+
+A representation of the band can be printed using
+
+ #include <isl/band.h>
+ __isl_give isl_printer *isl_printer_print_band(
+ __isl_take isl_printer *p,
+ __isl_keep isl_band *band);
+
+Alternatively, the schedule mapping
+can also be obtained in pieces using the following functions.
+
+ int isl_schedule_n_band(__isl_keep isl_schedule *sched);
+ __isl_give isl_union_map *isl_schedule_get_band(
+ __isl_keep isl_schedule *sched, unsigned band);
+
+C<isl_schedule_n_band> returns the maximal number of bands.
+C<isl_schedule_get_band> returns a union of mappings from a domain to
+the band of consecutive schedule dimensions with the given sequence
+number for that domain. Bands with the same sequence number but for
+different domains may be completely unrelated.
+Within a band, the corresponding coordinates of the distance vectors
+are all non-negative, assuming that the coordinates for all previous
+bands are all zero.
+
=head2 Parametric Vertex Enumeration
The parametric vertex enumeration described in this section
Given a polytope, C<isl_polytope_scan> prints
all integer points in the polytope.
-
-=head1 C<isl-polylib>
-
-The C<isl-polylib> library provides the following functions for converting
-between C<isl> objects and C<PolyLib> objects.
-The library is distributed separately for licensing reasons.
-
- #include <isl_set_polylib.h>
- __isl_give isl_basic_set *isl_basic_set_new_from_polylib(
- Polyhedron *P, __isl_take isl_dim *dim);
- Polyhedron *isl_basic_set_to_polylib(
- __isl_keep isl_basic_set *bset);
- __isl_give isl_set *isl_set_new_from_polylib(Polyhedron *D,
- __isl_take isl_dim *dim);
- Polyhedron *isl_set_to_polylib(__isl_keep isl_set *set);
-
- #include <isl_map_polylib.h>
- __isl_give isl_basic_map *isl_basic_map_new_from_polylib(
- Polyhedron *P, __isl_take isl_dim *dim);
- __isl_give isl_map *isl_map_new_from_polylib(Polyhedron *D,
- __isl_take isl_dim *dim);
- Polyhedron *isl_basic_map_to_polylib(
- __isl_keep isl_basic_map *bmap);
- Polyhedron *isl_map_to_polylib(__isl_keep isl_map *map);
projects / platform / upstream / isl.git / blobdiff