=back
+=head3 Changes since isl-0.04
+
+=over
+
+=item * All header files have been renamed from C<isl_header.h>
+to C<isl/header.h>.
+
+=back
+
+=head3 Changes since isl-0.05
+
+=over
+
+=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
The source of C<isl> can be obtained either as a tarball
However, to allow future versions of C<isl> to optionally
support fixed integer arithmetic, all calls to C<GMP>
are wrapped inside C<isl> specific macros.
-The basic type is C<isl_int> and the following operations
+The basic type is C<isl_int> and the operations below
are available on this type.
The meanings of these operations are essentially the same
as their C<GMP> C<mpz_> counterparts.
initialized with C<isl_int_init> before they can be used
and they need to be released with C<isl_int_clear>
after the last use.
+The user should not assume that an C<isl_int> is represented
+as a C<mpz_t>, but should instead explicitly convert between
+C<mpz_t>s and C<isl_int>s using C<isl_int_set_gmp> and
+C<isl_int_get_gmp> whenever a C<mpz_t> is required.
=over
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
Whenever a new set or relation is created from scratch,
its dimension needs to be specified using an C<isl_dim>.
- #include <isl_dim.h>
+ #include <isl/dim.h>
__isl_give isl_dim *isl_dim_alloc(isl_ctx *ctx,
unsigned nparam, unsigned n_in, unsigned n_out);
__isl_give isl_dim *isl_dim_set_alloc(isl_ctx *ctx,
L<Creating New (Piecewise) Quasipolynomials>) based on the dimension
specification of the original object.
- #include <isl_set.h>
+ #include <isl/set.h>
__isl_give isl_dim *isl_basic_set_get_dim(
__isl_keep isl_basic_set *bset);
__isl_give isl_dim *isl_set_get_dim(__isl_keep isl_set *set);
- #include <isl_union_set.h>
+ #include <isl/union_set.h>
__isl_give isl_dim *isl_union_set_get_dim(
__isl_keep isl_union_set *uset);
- #include <isl_map.h>
+ #include <isl/map.h>
__isl_give isl_dim *isl_basic_map_get_dim(
__isl_keep isl_basic_map *bmap);
__isl_give isl_dim *isl_map_get_dim(__isl_keep isl_map *map);
- #include <isl_union_map.h>
+ #include <isl/union_map.h>
__isl_give isl_dim *isl_union_map_get_dim(
__isl_keep isl_union_map *umap);
- #include <isl_polynomial.h>
+ #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_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.
- #include <isl_dim.h>
+ #include <isl/dim.h>
__isl_give isl_dim *isl_dim_set_name(__isl_take isl_dim *dim,
enum isl_dim_type type, unsigned pos,
__isl_keep const char *name);
The names of entire spaces may be set or read off
using the following functions.
- #include <isl_dim.h>
+ #include <isl/dim.h>
__isl_give isl_dim *isl_dim_set_tuple_name(
__isl_take isl_dim *dim,
enum isl_dim_type type, const char *s);
The following functions can be used to construct and deconstruct
such nested dimension specifications.
- #include <isl_dim.h>
+ #include <isl/dim.h>
int isl_dim_is_wrapping(__isl_keep isl_dim *dim);
__isl_give isl_dim *isl_dim_wrap(__isl_take isl_dim *dim);
__isl_give isl_dim *isl_dim_unwrap(__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);
+
=head2 Input and Output
C<isl> supports its own input/output format, which is similar
=head3 Input
- #include <isl_set.h>
+ #include <isl/set.h>
__isl_give isl_basic_set *isl_basic_set_read_from_file(
isl_ctx *ctx, FILE *input, int nparam);
__isl_give isl_basic_set *isl_basic_set_read_from_str(
__isl_give isl_set *isl_set_read_from_str(isl_ctx *ctx,
const char *str, int nparam);
- #include <isl_map.h>
+ #include <isl/map.h>
__isl_give isl_basic_map *isl_basic_map_read_from_file(
isl_ctx *ctx, FILE *input, int nparam);
__isl_give isl_basic_map *isl_basic_map_read_from_str(
__isl_give isl_map *isl_map_read_from_str(isl_ctx *ctx,
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);
+
The input format is autodetected and may be either the C<PolyLib> format
or the C<isl> format.
C<nparam> specifies how many of the final columns in
To actually print something, use
- #include <isl_set.h>
+ #include <isl/set.h>
__isl_give isl_printer *isl_printer_print_basic_set(
__isl_take isl_printer *printer,
__isl_keep isl_basic_set *bset);
__isl_take isl_printer *printer,
__isl_keep isl_set *set);
- #include <isl_map.h>
+ #include <isl/map.h>
__isl_give isl_printer *isl_printer_print_basic_map(
__isl_take isl_printer *printer,
__isl_keep isl_basic_map *bmap);
__isl_take isl_printer *printer,
__isl_keep isl_map *map);
- #include <isl_union_set.h>
+ #include <isl/union_set.h>
__isl_give isl_printer *isl_printer_print_union_set(
__isl_take isl_printer *p,
__isl_keep isl_union_set *uset);
- #include <isl_union_map.h>
+ #include <isl/union_map.h>
__isl_give isl_printer *isl_printer_print_union_map(
__isl_take isl_printer *p,
__isl_keep isl_union_map *umap);
__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>
+ #include <isl/constraint.h>
__isl_give isl_constraint *isl_equality_alloc(
__isl_take isl_dim *dim);
__isl_give isl_constraint *isl_inequality_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.
__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
To iterate over the constraints of a basic set or map, use
- #include <isl_constraint.h>
+ #include <isl/constraint.h>
int isl_basic_map_foreach_constraint(
__isl_keep isl_basic_map *bmap,
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,
void isl_div_get_coefficient(__isl_keep isl_div *div,
enum isl_dim_type type, int pos, isl_int *v);
-To obtain the constraints of a basic map in matrix
+To obtain the constraints of a basic set or map in matrix
form, use the following functions.
+ __isl_give isl_mat *isl_basic_set_equalities_matrix(
+ __isl_keep isl_basic_set *bset,
+ enum isl_dim_type c1, enum isl_dim_type c2,
+ enum isl_dim_type c3, enum isl_dim_type c4);
+ __isl_give isl_mat *isl_basic_set_inequalities_matrix(
+ __isl_keep isl_basic_set *bset,
+ enum isl_dim_type c1, enum isl_dim_type c2,
+ enum isl_dim_type c3, enum isl_dim_type c4);
__isl_give isl_mat *isl_basic_map_equalities_matrix(
- __isl_keep isl_basic_map *bmap,
- enum isl_dim_type c1,
- enum isl_dim_type c2, enum isl_dim_type c3,
- enum isl_dim_type c4, enum isl_dim_type c5);
+ __isl_keep isl_basic_map *bmap,
+ enum isl_dim_type c1,
+ enum isl_dim_type c2, enum isl_dim_type c3,
+ enum isl_dim_type c4, enum isl_dim_type c5);
__isl_give isl_mat *isl_basic_map_inequalities_matrix(
- __isl_keep isl_basic_map *bmap,
- enum isl_dim_type c1,
- enum isl_dim_type c2, enum isl_dim_type c3,
- enum isl_dim_type c4, enum isl_dim_type c5);
+ __isl_keep isl_basic_map *bmap,
+ enum isl_dim_type c1,
+ enum isl_dim_type c2, enum isl_dim_type c3,
+ enum isl_dim_type c4, enum isl_dim_type c5);
The C<isl_dim_type> arguments dictate the order in which
different kinds of variables appear in the resulting matrix
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);
+ int isl_union_set_is_equal(
+ __isl_keep isl_union_set *uset1,
+ __isl_keep isl_union_set *uset2);
int isl_basic_map_is_equal(
__isl_keep isl_basic_map *bmap1,
__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
int isl_set_is_strict_subset(
__isl_keep isl_set *set1,
__isl_keep isl_set *set2);
+ int isl_union_set_is_subset(
+ __isl_keep isl_union_set *uset1,
+ __isl_keep isl_union_set *uset2);
+ int isl_union_set_is_strict_subset(
+ __isl_keep isl_union_set *uset1,
+ __isl_keep isl_union_set *uset2);
int isl_basic_map_is_subset(
__isl_keep isl_basic_map *bmap1,
__isl_keep isl_basic_map *bmap2);
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 * 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 affine hull is computed
per space.
+=item * Polyhedral hull
+
+ __isl_give isl_basic_set *isl_set_polyhedral_hull(
+ __isl_take isl_set *set);
+ __isl_give isl_basic_map *isl_map_polyhedral_hull(
+ __isl_take isl_map *map);
+ __isl_give isl_union_set *isl_union_set_polyhedral_hull(
+ __isl_take isl_union_set *uset);
+ __isl_give isl_union_map *isl_union_map_polyhedral_hull(
+ __isl_take isl_union_map *umap);
+
+These functions compute a single basic set or relation
+not involving any existentially quantified variables
+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(
+ __isl_take isl_basic_map *bmap);
__isl_give isl_map *isl_map_flatten(
__isl_take isl_map *map);
+ __isl_give isl_map *isl_set_flatten_map(
+ __isl_take isl_set *set);
+
+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_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_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);
+ int isl_set_list_foreach(__isl_keep isl_set_list *list,
+ int (*fn)(__isl_take struct isl_set *el, void *user),
+ void *user);
+
=head2 Matrices
Matrices can be created, copied and freed using the following functions.
- #include <isl_mat.h>
+ #include <isl/mat.h>
__isl_give isl_mat *isl_mat_alloc(struct isl_ctx *ctx,
unsigned n_row, unsigned n_col);
__isl_give isl_mat *isl_mat_copy(__isl_keep 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.
+ 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
A singleton set can be created from a point using
+ __isl_give isl_basic_set *isl_basic_set_from_point(
+ __isl_take isl_point *pnt);
__isl_give isl_set *isl_set_from_point(
__isl_take isl_point *pnt);
and a box can be created from two opposite extremal points using
+ __isl_give isl_basic_set *isl_basic_set_box_from_points(
+ __isl_take isl_point *pnt1,
+ __isl_take isl_point *pnt2);
__isl_give isl_set *isl_set_box_from_points(
__isl_take isl_point *pnt1,
__isl_take isl_point *pnt2);
__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_give isl_qpolynomial *isl_qpolynomial_mul(
__isl_take isl_qpolynomial *qp1,
__isl_take isl_qpolynomial *qp2);
+ __isl_give isl_qpolynomial *isl_qpolynomial_pow(
+ __isl_take isl_qpolynomial *qp, unsigned exponent);
__isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_add(
__isl_take isl_pw_qpolynomial *pwqp1,
__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);
The gist operation applies the gist operation to each of
the cells in the domain of the input piecewise quasipolynomial.
-In future, the operation will also exploit the context
+The context is also exploited
to simplify the quasipolynomials associated to each cell.
+ __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_to_polynomial(
+ __isl_take isl_pw_qpolynomial *pwqp, int sign);
+ __isl_give isl_union_pw_qpolynomial *
+ isl_union_pw_qpolynomial_to_polynomial(
+ __isl_take isl_union_pw_qpolynomial *upwqp, int sign);
+
+Approximate each quasipolynomial by a polynomial. If C<sign> is positive,
+the polynomial will be an overapproximation. If C<sign> is negative,
+it will be an underapproximation. If C<sign> is zero, the approximation
+will lie somewhere in between.
+
=head2 Bounds on Piecewise Quasipolynomials and Piecewise Quasipolynomial Reductions
A piecewise quasipolynomial reduction is a piecewise
needs to be set to either C<ISL_FORMAT_ISL> or C<ISL_FORMAT_C>.
For C<isl_printer_print_union_pw_qpolynomial_fold>,
output format of the printer
-needs to be set to either C<ISL_FORMAT_ISL>.
+needs to be set to C<ISL_FORMAT_ISL>.
+In case of printing in C<ISL_FORMAT_C>, the user may want
+to set the names of all dimensions
+
+ __isl_give isl_pw_qpolynomial_fold *
+ isl_pw_qpolynomial_fold_set_dim_name(
+ __isl_take isl_pw_qpolynomial_fold *pwf,
+ enum isl_dim_type type, unsigned pos,
+ const char *s);
=head3 Inspecting (Piecewise) Quasipolynomial Reductions
=head3 Operations on Piecewise Quasipolynomial Reductions
+ __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_add(
+ __isl_take isl_pw_qpolynomial_fold *pwf1,
+ __isl_take isl_pw_qpolynomial_fold *pwf2);
+
__isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_fold(
__isl_take isl_pw_qpolynomial_fold *pwf1,
__isl_take isl_pw_qpolynomial_fold *pwf2);
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
If, on the other hand, all sources are I<must> accesses,
then value based dependence analysis is performed.
- #include <isl_flow.h>
+ #include <isl/flow.h>
typedef int (*isl_access_level_before)(void *first, void *second);
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
A higher-level interface to dependence analysis is provided
by the following function.
- #include <isl_flow.h>
+ #include <isl/flow.h>
int isl_union_map_compute_flow(__isl_take isl_union_map *sink,
__isl_take isl_union_map *must_source,
__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);
+
+This 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
is mainly intended to be used internally and by the C<barvinok>
library.
- #include <isl_vertices.h>
+ #include <isl/vertices.h>
__isl_give isl_vertices *isl_basic_set_compute_vertices(
__isl_keep isl_basic_set *bset);
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