add isl_basic_map_flat_range_product
[platform/upstream/isl.git] / doc / user.pod
1 =head1 Introduction
2
3 C<isl> is a thread-safe C library for manipulating
4 sets and relations of integer points bounded by affine constraints.
5 The descriptions of the sets and relations may involve
6 both parameters and existentially quantified variables.
7 All computations are performed in exact integer arithmetic
8 using C<GMP>.
9 The C<isl> library offers functionality that is similar
10 to that offered by the C<Omega> and C<Omega+> libraries,
11 but the underlying algorithms are in most cases completely different.
12
13 The library is by no means complete and some fairly basic
14 functionality is still missing.
15 Still, even in its current form, the library has been successfully
16 used as a backend polyhedral library for the polyhedral
17 scanner C<CLooG> and as part of an equivalence checker of
18 static affine programs.
19 For bug reports, feature requests and questions,
20 visit the the discussion group at
21 L<http://groups.google.com/group/isl-development>.
22
23 =head2 Backward Incompatible Changes
24
25 =head3 Changes since isl-0.02
26
27 =over
28
29 =item * The old printing functions have been deprecated
30 and replaced by C<isl_printer> functions, see L<Input and Output>.
31
32 =item * Most functions related to dependence analysis have acquired
33 an extra C<must> argument.  To obtain the old behavior, this argument
34 should be given the value 1.  See L<Dependence Analysis>.
35
36 =back
37
38 =head3 Changes since isl-0.03
39
40 =over
41
42 =item * The function C<isl_pw_qpolynomial_fold_add> has been
43 renamed to C<isl_pw_qpolynomial_fold_fold>.
44 Similarly, C<isl_union_pw_qpolynomial_fold_add> has been
45 renamed to C<isl_union_pw_qpolynomial_fold_fold>.
46
47 =back
48
49 =head3 Changes since isl-0.04
50
51 =over
52
53 =item * All header files have been renamed from C<isl_header.h>
54 to C<isl/header.h>.
55
56 =back
57
58 =head3 Changes since isl-0.05
59
60 =over
61
62 =item * The functions C<isl_printer_print_basic_set> and
63 C<isl_printer_print_basic_map> no longer print a newline.
64
65 =item * The functions C<isl_flow_get_no_source>
66 and C<isl_union_map_compute_flow> now return
67 the accesses for which no source could be found instead of
68 the iterations where those accesses occur.
69
70 =item * The functions C<isl_basic_map_identity> and
71 C<isl_map_identity> now take the dimension specification
72 of a B<map> as input.  An old call
73 C<isl_map_identity(dim)> can be rewritten to
74 C<isl_map_identity(isl_dim_map_from_set(dim))>.
75
76 =item * The function C<isl_map_power> no longer takes
77 a parameter position as input.  Instead, the exponent
78 is now expressed as the domain of the resulting relation.
79
80 =back
81
82 =head3 Changes since isl-0.06
83
84 =over
85
86 =item * The format of C<isl_printer_print_qpolynomial>'s
87 C<ISL_FORMAT_ISL> output has changed.
88 Use C<ISL_FORMAT_C> to obtain the old output.
89
90 =back
91
92 =head1 Installation
93
94 The source of C<isl> can be obtained either as a tarball
95 or from the git repository.  Both are available from
96 L<http://freshmeat.net/projects/isl/>.
97 The installation process depends on how you obtained
98 the source.
99
100 =head2 Installation from the git repository
101
102 =over
103
104 =item 1 Clone or update the repository
105
106 The first time the source is obtained, you need to clone
107 the repository.
108
109         git clone git://repo.or.cz/isl.git
110
111 To obtain updates, you need to pull in the latest changes
112
113         git pull
114
115 =item 2 Generate C<configure>
116
117         ./autogen.sh
118
119 =back
120
121 After performing the above steps, continue
122 with the L<Common installation instructions>.
123
124 =head2 Common installation instructions
125
126 =over
127
128 =item 1 Obtain C<GMP>
129
130 Building C<isl> requires C<GMP>, including its headers files.
131 Your distribution may not provide these header files by default
132 and you may need to install a package called C<gmp-devel> or something
133 similar.  Alternatively, C<GMP> can be built from
134 source, available from L<http://gmplib.org/>.
135
136 =item 2 Configure
137
138 C<isl> uses the standard C<autoconf> C<configure> script.
139 To run it, just type
140
141         ./configure
142
143 optionally followed by some configure options.
144 A complete list of options can be obtained by running
145
146         ./configure --help
147
148 Below we discuss some of the more common options.
149
150 C<isl> can optionally use C<piplib>, but no
151 C<piplib> functionality is currently used by default.
152 The C<--with-piplib> option can
153 be used to specify which C<piplib>
154 library to use, either an installed version (C<system>),
155 an externally built version (C<build>)
156 or no version (C<no>).  The option C<build> is mostly useful
157 in C<configure> scripts of larger projects that bundle both C<isl>
158 and C<piplib>.
159
160 =over
161
162 =item C<--prefix>
163
164 Installation prefix for C<isl>
165
166 =item C<--with-gmp-prefix>
167
168 Installation prefix for C<GMP> (architecture-independent files).
169
170 =item C<--with-gmp-exec-prefix>
171
172 Installation prefix for C<GMP> (architecture-dependent files).
173
174 =item C<--with-piplib>
175
176 Which copy of C<piplib> to use, either C<no> (default), C<system> or C<build>.
177
178 =item C<--with-piplib-prefix>
179
180 Installation prefix for C<system> C<piplib> (architecture-independent files).
181
182 =item C<--with-piplib-exec-prefix>
183
184 Installation prefix for C<system> C<piplib> (architecture-dependent files).
185
186 =item C<--with-piplib-builddir>
187
188 Location where C<build> C<piplib> was built.
189
190 =back
191
192 =item 3 Compile
193
194         make
195
196 =item 4 Install (optional)
197
198         make install
199
200 =back
201
202 =head1 Library
203
204 =head2 Initialization
205
206 All manipulations of integer sets and relations occur within
207 the context of an C<isl_ctx>.
208 A given C<isl_ctx> can only be used within a single thread.
209 All arguments of a function are required to have been allocated
210 within the same context.
211 There are currently no functions available for moving an object
212 from one C<isl_ctx> to another C<isl_ctx>.  This means that
213 there is currently no way of safely moving an object from one
214 thread to another, unless the whole C<isl_ctx> is moved.
215
216 An C<isl_ctx> can be allocated using C<isl_ctx_alloc> and
217 freed using C<isl_ctx_free>.
218 All objects allocated within an C<isl_ctx> should be freed
219 before the C<isl_ctx> itself is freed.
220
221         isl_ctx *isl_ctx_alloc();
222         void isl_ctx_free(isl_ctx *ctx);
223
224 =head2 Integers
225
226 All operations on integers, mainly the coefficients
227 of the constraints describing the sets and relations,
228 are performed in exact integer arithmetic using C<GMP>.
229 However, to allow future versions of C<isl> to optionally
230 support fixed integer arithmetic, all calls to C<GMP>
231 are wrapped inside C<isl> specific macros.
232 The basic type is C<isl_int> and the operations below
233 are available on this type.
234 The meanings of these operations are essentially the same
235 as their C<GMP> C<mpz_> counterparts.
236 As always with C<GMP> types, C<isl_int>s need to be
237 initialized with C<isl_int_init> before they can be used
238 and they need to be released with C<isl_int_clear>
239 after the last use.
240 The user should not assume that an C<isl_int> is represented
241 as a C<mpz_t>, but should instead explicitly convert between
242 C<mpz_t>s and C<isl_int>s using C<isl_int_set_gmp> and
243 C<isl_int_get_gmp> whenever a C<mpz_t> is required.
244
245 =over
246
247 =item isl_int_init(i)
248
249 =item isl_int_clear(i)
250
251 =item isl_int_set(r,i)
252
253 =item isl_int_set_si(r,i)
254
255 =item isl_int_set_gmp(r,g)
256
257 =item isl_int_get_gmp(i,g)
258
259 =item isl_int_abs(r,i)
260
261 =item isl_int_neg(r,i)
262
263 =item isl_int_swap(i,j)
264
265 =item isl_int_swap_or_set(i,j)
266
267 =item isl_int_add_ui(r,i,j)
268
269 =item isl_int_sub_ui(r,i,j)
270
271 =item isl_int_add(r,i,j)
272
273 =item isl_int_sub(r,i,j)
274
275 =item isl_int_mul(r,i,j)
276
277 =item isl_int_mul_ui(r,i,j)
278
279 =item isl_int_addmul(r,i,j)
280
281 =item isl_int_submul(r,i,j)
282
283 =item isl_int_gcd(r,i,j)
284
285 =item isl_int_lcm(r,i,j)
286
287 =item isl_int_divexact(r,i,j)
288
289 =item isl_int_cdiv_q(r,i,j)
290
291 =item isl_int_fdiv_q(r,i,j)
292
293 =item isl_int_fdiv_r(r,i,j)
294
295 =item isl_int_fdiv_q_ui(r,i,j)
296
297 =item isl_int_read(r,s)
298
299 =item isl_int_print(out,i,width)
300
301 =item isl_int_sgn(i)
302
303 =item isl_int_cmp(i,j)
304
305 =item isl_int_cmp_si(i,si)
306
307 =item isl_int_eq(i,j)
308
309 =item isl_int_ne(i,j)
310
311 =item isl_int_lt(i,j)
312
313 =item isl_int_le(i,j)
314
315 =item isl_int_gt(i,j)
316
317 =item isl_int_ge(i,j)
318
319 =item isl_int_abs_eq(i,j)
320
321 =item isl_int_abs_ne(i,j)
322
323 =item isl_int_abs_lt(i,j)
324
325 =item isl_int_abs_gt(i,j)
326
327 =item isl_int_abs_ge(i,j)
328
329 =item isl_int_is_zero(i)
330
331 =item isl_int_is_one(i)
332
333 =item isl_int_is_negone(i)
334
335 =item isl_int_is_pos(i)
336
337 =item isl_int_is_neg(i)
338
339 =item isl_int_is_nonpos(i)
340
341 =item isl_int_is_nonneg(i)
342
343 =item isl_int_is_divisible_by(i,j)
344
345 =back
346
347 =head2 Sets and Relations
348
349 C<isl> uses six types of objects for representing sets and relations,
350 C<isl_basic_set>, C<isl_basic_map>, C<isl_set>, C<isl_map>,
351 C<isl_union_set> and C<isl_union_map>.
352 C<isl_basic_set> and C<isl_basic_map> represent sets and relations that
353 can be described as a conjunction of affine constraints, while
354 C<isl_set> and C<isl_map> represent unions of
355 C<isl_basic_set>s and C<isl_basic_map>s, respectively.
356 However, all C<isl_basic_set>s or C<isl_basic_map>s in the union need
357 to have the same dimension.  C<isl_union_set>s and C<isl_union_map>s
358 represent unions of C<isl_set>s or C<isl_map>s of I<different> dimensions,
359 where dimensions with different space names
360 (see L<Dimension Specifications>) are considered different as well.
361 The difference between sets and relations (maps) is that sets have
362 one set of variables, while relations have two sets of variables,
363 input variables and output variables.
364
365 =head2 Memory Management
366
367 Since a high-level operation on sets and/or relations usually involves
368 several substeps and since the user is usually not interested in
369 the intermediate results, most functions that return a new object
370 will also release all the objects passed as arguments.
371 If the user still wants to use one or more of these arguments
372 after the function call, she should pass along a copy of the
373 object rather than the object itself.
374 The user is then responsible for making sure that the original
375 object gets used somewhere else or is explicitly freed.
376
377 The arguments and return values of all documents functions are
378 annotated to make clear which arguments are released and which
379 arguments are preserved.  In particular, the following annotations
380 are used
381
382 =over
383
384 =item C<__isl_give>
385
386 C<__isl_give> means that a new object is returned.
387 The user should make sure that the returned pointer is
388 used exactly once as a value for an C<__isl_take> argument.
389 In between, it can be used as a value for as many
390 C<__isl_keep> arguments as the user likes.
391 There is one exception, and that is the case where the
392 pointer returned is C<NULL>.  Is this case, the user
393 is free to use it as an C<__isl_take> argument or not.
394
395 =item C<__isl_take>
396
397 C<__isl_take> means that the object the argument points to
398 is taken over by the function and may no longer be used
399 by the user as an argument to any other function.
400 The pointer value must be one returned by a function
401 returning an C<__isl_give> pointer.
402 If the user passes in a C<NULL> value, then this will
403 be treated as an error in the sense that the function will
404 not perform its usual operation.  However, it will still
405 make sure that all the the other C<__isl_take> arguments
406 are released.
407
408 =item C<__isl_keep>
409
410 C<__isl_keep> means that the function will only use the object
411 temporarily.  After the function has finished, the user
412 can still use it as an argument to other functions.
413 A C<NULL> value will be treated in the same way as
414 a C<NULL> value for an C<__isl_take> argument.
415
416 =back
417
418 =head2 Dimension Specifications
419
420 Whenever a new set or relation is created from scratch,
421 its dimension needs to be specified using an C<isl_dim>.
422
423         #include <isl/dim.h>
424         __isl_give isl_dim *isl_dim_alloc(isl_ctx *ctx,
425                 unsigned nparam, unsigned n_in, unsigned n_out);
426         __isl_give isl_dim *isl_dim_set_alloc(isl_ctx *ctx,
427                 unsigned nparam, unsigned dim);
428         __isl_give isl_dim *isl_dim_copy(__isl_keep isl_dim *dim);
429         void isl_dim_free(__isl_take isl_dim *dim);
430         unsigned isl_dim_size(__isl_keep isl_dim *dim,
431                 enum isl_dim_type type);
432
433 The dimension specification used for creating a set
434 needs to be created using C<isl_dim_set_alloc>, while
435 that for creating a relation
436 needs to be created using C<isl_dim_alloc>.
437 C<isl_dim_size> can be used
438 to find out the number of dimensions of each type in
439 a dimension specification, where type may be
440 C<isl_dim_param>, C<isl_dim_in> (only for relations),
441 C<isl_dim_out> (only for relations), C<isl_dim_set>
442 (only for sets) or C<isl_dim_all>.
443
444 It is often useful to create objects that live in the
445 same space as some other object.  This can be accomplished
446 by creating the new objects
447 (see L<Creating New Sets and Relations> or
448 L<Creating New (Piecewise) Quasipolynomials>) based on the dimension
449 specification of the original object.
450
451         #include <isl/set.h>
452         __isl_give isl_dim *isl_basic_set_get_dim(
453                 __isl_keep isl_basic_set *bset);
454         __isl_give isl_dim *isl_set_get_dim(__isl_keep isl_set *set);
455
456         #include <isl/union_set.h>
457         __isl_give isl_dim *isl_union_set_get_dim(
458                 __isl_keep isl_union_set *uset);
459
460         #include <isl/map.h>
461         __isl_give isl_dim *isl_basic_map_get_dim(
462                 __isl_keep isl_basic_map *bmap);
463         __isl_give isl_dim *isl_map_get_dim(__isl_keep isl_map *map);
464
465         #include <isl/union_map.h>
466         __isl_give isl_dim *isl_union_map_get_dim(
467                 __isl_keep isl_union_map *umap);
468
469         #include <isl/constraint.h>
470         __isl_give isl_dim *isl_constraint_get_dim(
471                 __isl_keep isl_constraint *constraint);
472
473         #include <isl/polynomial.h>
474         __isl_give isl_dim *isl_qpolynomial_get_dim(
475                 __isl_keep isl_qpolynomial *qp);
476         __isl_give isl_dim *isl_pw_qpolynomial_get_dim(
477                 __isl_keep isl_pw_qpolynomial *pwqp);
478         __isl_give isl_dim *isl_union_pw_qpolynomial_get_dim(
479                 __isl_keep isl_union_pw_qpolynomial *upwqp);
480         __isl_give isl_dim *isl_union_pw_qpolynomial_fold_get_dim(
481                 __isl_keep isl_union_pw_qpolynomial_fold *upwf);
482
483         #include <isl/aff.h>
484         __isl_give isl_dim *isl_aff_get_dim(
485                 __isl_keep isl_aff *aff);
486
487 The names of the individual dimensions may be set or read off
488 using the following functions.
489
490         #include <isl/dim.h>
491         __isl_give isl_dim *isl_dim_set_name(__isl_take isl_dim *dim,
492                                  enum isl_dim_type type, unsigned pos,
493                                  __isl_keep const char *name);
494         __isl_keep const char *isl_dim_get_name(__isl_keep isl_dim *dim,
495                                  enum isl_dim_type type, unsigned pos);
496
497 Note that C<isl_dim_get_name> returns a pointer to some internal
498 data structure, so the result can only be used while the
499 corresponding C<isl_dim> is alive.
500 Also note that every function that operates on two sets or relations
501 requires that both arguments have the same parameters.  This also
502 means that if one of the arguments has named parameters, then the
503 other needs to have named parameters too and the names need to match.
504 Pairs of C<isl_union_set> and/or C<isl_union_map> arguments may
505 have different parameters (as long as they are named), in which case
506 the result will have as parameters the union of the parameters of
507 the arguments.
508
509 The names of entire spaces may be set or read off
510 using the following functions.
511
512         #include <isl/dim.h>
513         __isl_give isl_dim *isl_dim_set_tuple_name(
514                 __isl_take isl_dim *dim,
515                 enum isl_dim_type type, const char *s);
516         const char *isl_dim_get_tuple_name(__isl_keep isl_dim *dim,
517                 enum isl_dim_type type);
518
519 The C<dim> argument needs to be one of C<isl_dim_in>, C<isl_dim_out>
520 or C<isl_dim_set>.  As with C<isl_dim_get_name>,
521 the C<isl_dim_get_tuple_name> function returns a pointer to some internal
522 data structure.
523 Binary operations require the corresponding spaces of their arguments
524 to have the same name.
525
526 Spaces can be nested.  In particular, the domain of a set or
527 the domain or range of a relation can be a nested relation.
528 The following functions can be used to construct and deconstruct
529 such nested dimension specifications.
530
531         #include <isl/dim.h>
532         int isl_dim_is_wrapping(__isl_keep isl_dim *dim);
533         __isl_give isl_dim *isl_dim_wrap(__isl_take isl_dim *dim);
534         __isl_give isl_dim *isl_dim_unwrap(__isl_take isl_dim *dim);
535
536 The input to C<isl_dim_is_wrapping> and C<isl_dim_unwrap> should
537 be the dimension specification of a set, while that of
538 C<isl_dim_wrap> should be the dimension specification of a relation.
539 Conversely, the output of C<isl_dim_unwrap> is the dimension specification
540 of a relation, while that of C<isl_dim_wrap> is the dimension specification
541 of a set.
542
543 Dimension specifications can be created from other dimension
544 specifications using the following functions.
545
546         __isl_give isl_dim *isl_dim_domain(__isl_take isl_dim *dim);
547         __isl_give isl_dim *isl_dim_from_domain(__isl_take isl_dim *dim);
548         __isl_give isl_dim *isl_dim_range(__isl_take isl_dim *dim);
549         __isl_give isl_dim *isl_dim_from_range(__isl_take isl_dim *dim);
550         __isl_give isl_dim *isl_dim_reverse(__isl_take isl_dim *dim);
551         __isl_give isl_dim *isl_dim_join(__isl_take isl_dim *left,
552                 __isl_take isl_dim *right);
553         __isl_give isl_dim *isl_dim_align_params(
554                 __isl_take isl_dim *dim1, __isl_take isl_dim *dim2)
555         __isl_give isl_dim *isl_dim_insert(__isl_take isl_dim *dim,
556                 enum isl_dim_type type, unsigned pos, unsigned n);
557         __isl_give isl_dim *isl_dim_add(__isl_take isl_dim *dim,
558                 enum isl_dim_type type, unsigned n);
559         __isl_give isl_dim *isl_dim_drop(__isl_take isl_dim *dim,
560                 enum isl_dim_type type, unsigned first, unsigned n);
561         __isl_give isl_dim *isl_dim_map_from_set(
562                 __isl_take isl_dim *dim);
563         __isl_give isl_dim *isl_dim_zip(__isl_take isl_dim *dim);
564
565 Note that if dimensions are added or removed from a space, then
566 the name and the internal structure are lost.
567
568 =head2 Local Spaces
569
570 A local space is essentially a dimension specification with
571 zero or more existentially quantified variables.
572 The local space of a basic set or relation can be obtained
573 using the following functions.
574
575         #include <isl/set.h>
576         __isl_give isl_local_space *isl_basic_set_get_local_space(
577                 __isl_keep isl_basic_set *bset);
578
579         #include <isl/map.h>
580         __isl_give isl_local_space *isl_basic_map_get_local_space(
581                 __isl_keep isl_basic_map *bmap);
582
583 A new local space can be created from a dimension specification using
584
585         #include <isl/local_space.h>
586         __isl_give isl_local_space *isl_local_space_from_dim(
587                 __isl_take isl_dim *dim);
588
589 They can be inspected, copied and freed using the following functions.
590
591         #include <isl/local_space.h>
592         isl_ctx *isl_local_space_get_ctx(
593                 __isl_keep isl_local_space *ls);
594         int isl_local_space_dim(__isl_keep isl_local_space *ls,
595                 enum isl_dim_type type);
596         const char *isl_local_space_get_dim_name(
597                 __isl_keep isl_local_space *ls,
598                 enum isl_dim_type type, unsigned pos);
599         __isl_give isl_dim *isl_local_space_get_dim(
600                 __isl_keep isl_local_space *ls);
601         __isl_give isl_div *isl_local_space_get_div(
602                 __isl_keep isl_local_space *ls, int pos);
603         __isl_give isl_local_space *isl_local_space_copy(
604                 __isl_keep isl_local_space *ls);
605         void *isl_local_space_free(__isl_take isl_local_space *ls);
606
607 =head2 Input and Output
608
609 C<isl> supports its own input/output format, which is similar
610 to the C<Omega> format, but also supports the C<PolyLib> format
611 in some cases.
612
613 =head3 C<isl> format
614
615 The C<isl> format is similar to that of C<Omega>, but has a different
616 syntax for describing the parameters and allows for the definition
617 of an existentially quantified variable as the integer division
618 of an affine expression.
619 For example, the set of integers C<i> between C<0> and C<n>
620 such that C<i % 10 <= 6> can be described as
621
622         [n] -> { [i] : exists (a = [i/10] : 0 <= i and i <= n and
623                                 i - 10 a <= 6) }
624
625 A set or relation can have several disjuncts, separated
626 by the keyword C<or>.  Each disjunct is either a conjunction
627 of constraints or a projection (C<exists>) of a conjunction
628 of constraints.  The constraints are separated by the keyword
629 C<and>.
630
631 =head3 C<PolyLib> format
632
633 If the represented set is a union, then the first line
634 contains a single number representing the number of disjuncts.
635 Otherwise, a line containing the number C<1> is optional.
636
637 Each disjunct is represented by a matrix of constraints.
638 The first line contains two numbers representing
639 the number of rows and columns,
640 where the number of rows is equal to the number of constraints
641 and the number of columns is equal to two plus the number of variables.
642 The following lines contain the actual rows of the constraint matrix.
643 In each row, the first column indicates whether the constraint
644 is an equality (C<0>) or inequality (C<1>).  The final column
645 corresponds to the constant term.
646
647 If the set is parametric, then the coefficients of the parameters
648 appear in the last columns before the constant column.
649 The coefficients of any existentially quantified variables appear
650 between those of the set variables and those of the parameters.
651
652 =head3 Extended C<PolyLib> format
653
654 The extended C<PolyLib> format is nearly identical to the
655 C<PolyLib> format.  The only difference is that the line
656 containing the number of rows and columns of a constraint matrix
657 also contains four additional numbers:
658 the number of output dimensions, the number of input dimensions,
659 the number of local dimensions (i.e., the number of existentially
660 quantified variables) and the number of parameters.
661 For sets, the number of ``output'' dimensions is equal
662 to the number of set dimensions, while the number of ``input''
663 dimensions is zero.
664
665 =head3 Input
666
667         #include <isl/set.h>
668         __isl_give isl_basic_set *isl_basic_set_read_from_file(
669                 isl_ctx *ctx, FILE *input, int nparam);
670         __isl_give isl_basic_set *isl_basic_set_read_from_str(
671                 isl_ctx *ctx, const char *str, int nparam);
672         __isl_give isl_set *isl_set_read_from_file(isl_ctx *ctx,
673                 FILE *input, int nparam);
674         __isl_give isl_set *isl_set_read_from_str(isl_ctx *ctx,
675                 const char *str, int nparam);
676
677         #include <isl/map.h>
678         __isl_give isl_basic_map *isl_basic_map_read_from_file(
679                 isl_ctx *ctx, FILE *input, int nparam);
680         __isl_give isl_basic_map *isl_basic_map_read_from_str(
681                 isl_ctx *ctx, const char *str, int nparam);
682         __isl_give isl_map *isl_map_read_from_file(
683                 struct isl_ctx *ctx, FILE *input, int nparam);
684         __isl_give isl_map *isl_map_read_from_str(isl_ctx *ctx,
685                 const char *str, int nparam);
686
687         #include <isl/union_set.h>
688         __isl_give isl_union_set *isl_union_set_read_from_file(
689                 isl_ctx *ctx, FILE *input);
690         __isl_give isl_union_set *isl_union_set_read_from_str(
691                 struct isl_ctx *ctx, const char *str);
692
693         #include <isl/union_map.h>
694         __isl_give isl_union_map *isl_union_map_read_from_file(
695                 isl_ctx *ctx, FILE *input);
696         __isl_give isl_union_map *isl_union_map_read_from_str(
697                 struct isl_ctx *ctx, const char *str);
698
699 The input format is autodetected and may be either the C<PolyLib> format
700 or the C<isl> format.
701 C<nparam> specifies how many of the final columns in
702 the C<PolyLib> format correspond to parameters.
703 If input is given in the C<isl> format, then the number
704 of parameters needs to be equal to C<nparam>.
705 If C<nparam> is negative, then any number of parameters
706 is accepted in the C<isl> format and zero parameters
707 are assumed in the C<PolyLib> format.
708
709 =head3 Output
710
711 Before anything can be printed, an C<isl_printer> needs to
712 be created.
713
714         __isl_give isl_printer *isl_printer_to_file(isl_ctx *ctx,
715                 FILE *file);
716         __isl_give isl_printer *isl_printer_to_str(isl_ctx *ctx);
717         void isl_printer_free(__isl_take isl_printer *printer);
718         __isl_give char *isl_printer_get_str(
719                 __isl_keep isl_printer *printer);
720
721 The behavior of the printer can be modified in various ways
722
723         __isl_give isl_printer *isl_printer_set_output_format(
724                 __isl_take isl_printer *p, int output_format);
725         __isl_give isl_printer *isl_printer_set_indent(
726                 __isl_take isl_printer *p, int indent);
727         __isl_give isl_printer *isl_printer_indent(
728                 __isl_take isl_printer *p, int indent);
729         __isl_give isl_printer *isl_printer_set_prefix(
730                 __isl_take isl_printer *p, const char *prefix);
731         __isl_give isl_printer *isl_printer_set_suffix(
732                 __isl_take isl_printer *p, const char *suffix);
733
734 The C<output_format> may be either C<ISL_FORMAT_ISL>, C<ISL_FORMAT_OMEGA>,
735 C<ISL_FORMAT_POLYLIB>, C<ISL_FORMAT_EXT_POLYLIB> or C<ISL_FORMAT_LATEX>
736 and defaults to C<ISL_FORMAT_ISL>.
737 Each line in the output is indented by C<indent> (set by
738 C<isl_printer_set_indent>) spaces
739 (default: 0), prefixed by C<prefix> and suffixed by C<suffix>.
740 In the C<PolyLib> format output,
741 the coefficients of the existentially quantified variables
742 appear between those of the set variables and those
743 of the parameters.
744 The function C<isl_printer_indent> increases the indentation
745 by the specified amount (which may be negative).
746
747 To actually print something, use
748
749         #include <isl/set.h>
750         __isl_give isl_printer *isl_printer_print_basic_set(
751                 __isl_take isl_printer *printer,
752                 __isl_keep isl_basic_set *bset);
753         __isl_give isl_printer *isl_printer_print_set(
754                 __isl_take isl_printer *printer,
755                 __isl_keep isl_set *set);
756
757         #include <isl/map.h>
758         __isl_give isl_printer *isl_printer_print_basic_map(
759                 __isl_take isl_printer *printer,
760                 __isl_keep isl_basic_map *bmap);
761         __isl_give isl_printer *isl_printer_print_map(
762                 __isl_take isl_printer *printer,
763                 __isl_keep isl_map *map);
764
765         #include <isl/union_set.h>
766         __isl_give isl_printer *isl_printer_print_union_set(
767                 __isl_take isl_printer *p,
768                 __isl_keep isl_union_set *uset);
769
770         #include <isl/union_map.h>
771         __isl_give isl_printer *isl_printer_print_union_map(
772                 __isl_take isl_printer *p,
773                 __isl_keep isl_union_map *umap);
774
775 When called on a file printer, the following function flushes
776 the file.  When called on a string printer, the buffer is cleared.
777
778         __isl_give isl_printer *isl_printer_flush(
779                 __isl_take isl_printer *p);
780
781 =head2 Creating New Sets and Relations
782
783 C<isl> has functions for creating some standard sets and relations.
784
785 =over
786
787 =item * Empty sets and relations
788
789         __isl_give isl_basic_set *isl_basic_set_empty(
790                 __isl_take isl_dim *dim);
791         __isl_give isl_basic_map *isl_basic_map_empty(
792                 __isl_take isl_dim *dim);
793         __isl_give isl_set *isl_set_empty(
794                 __isl_take isl_dim *dim);
795         __isl_give isl_map *isl_map_empty(
796                 __isl_take isl_dim *dim);
797         __isl_give isl_union_set *isl_union_set_empty(
798                 __isl_take isl_dim *dim);
799         __isl_give isl_union_map *isl_union_map_empty(
800                 __isl_take isl_dim *dim);
801
802 For C<isl_union_set>s and C<isl_union_map>s, the dimensions specification
803 is only used to specify the parameters.
804
805 =item * Universe sets and relations
806
807         __isl_give isl_basic_set *isl_basic_set_universe(
808                 __isl_take isl_dim *dim);
809         __isl_give isl_basic_map *isl_basic_map_universe(
810                 __isl_take isl_dim *dim);
811         __isl_give isl_set *isl_set_universe(
812                 __isl_take isl_dim *dim);
813         __isl_give isl_map *isl_map_universe(
814                 __isl_take isl_dim *dim);
815         __isl_give isl_union_set *isl_union_set_universe(
816                 __isl_take isl_union_set *uset);
817         __isl_give isl_union_map *isl_union_map_universe(
818                 __isl_take isl_union_map *umap);
819
820 The sets and relations constructed by the functions above
821 contain all integer values, while those constructed by the
822 functions below only contain non-negative values.
823
824         __isl_give isl_basic_set *isl_basic_set_nat_universe(
825                 __isl_take isl_dim *dim);
826         __isl_give isl_basic_map *isl_basic_map_nat_universe(
827                 __isl_take isl_dim *dim);
828         __isl_give isl_set *isl_set_nat_universe(
829                 __isl_take isl_dim *dim);
830         __isl_give isl_map *isl_map_nat_universe(
831                 __isl_take isl_dim *dim);
832
833 =item * Identity relations
834
835         __isl_give isl_basic_map *isl_basic_map_identity(
836                 __isl_take isl_dim *dim);
837         __isl_give isl_map *isl_map_identity(
838                 __isl_take isl_dim *dim);
839
840 The number of input and output dimensions in C<dim> needs
841 to be the same.
842
843 =item * Lexicographic order
844
845         __isl_give isl_map *isl_map_lex_lt(
846                 __isl_take isl_dim *set_dim);
847         __isl_give isl_map *isl_map_lex_le(
848                 __isl_take isl_dim *set_dim);
849         __isl_give isl_map *isl_map_lex_gt(
850                 __isl_take isl_dim *set_dim);
851         __isl_give isl_map *isl_map_lex_ge(
852                 __isl_take isl_dim *set_dim);
853         __isl_give isl_map *isl_map_lex_lt_first(
854                 __isl_take isl_dim *dim, unsigned n);
855         __isl_give isl_map *isl_map_lex_le_first(
856                 __isl_take isl_dim *dim, unsigned n);
857         __isl_give isl_map *isl_map_lex_gt_first(
858                 __isl_take isl_dim *dim, unsigned n);
859         __isl_give isl_map *isl_map_lex_ge_first(
860                 __isl_take isl_dim *dim, unsigned n);
861
862 The first four functions take a dimension specification for a B<set>
863 and return relations that express that the elements in the domain
864 are lexicographically less
865 (C<isl_map_lex_lt>), less or equal (C<isl_map_lex_le>),
866 greater (C<isl_map_lex_gt>) or greater or equal (C<isl_map_lex_ge>)
867 than the elements in the range.
868 The last four functions take a dimension specification for a map
869 and return relations that express that the first C<n> dimensions
870 in the domain are lexicographically less
871 (C<isl_map_lex_lt_first>), less or equal (C<isl_map_lex_le_first>),
872 greater (C<isl_map_lex_gt_first>) or greater or equal (C<isl_map_lex_ge_first>)
873 than the first C<n> dimensions in the range.
874
875 =back
876
877 A basic set or relation can be converted to a set or relation
878 using the following functions.
879
880         __isl_give isl_set *isl_set_from_basic_set(
881                 __isl_take isl_basic_set *bset);
882         __isl_give isl_map *isl_map_from_basic_map(
883                 __isl_take isl_basic_map *bmap);
884
885 Sets and relations can be converted to union sets and relations
886 using the following functions.
887
888         __isl_give isl_union_map *isl_union_map_from_map(
889                 __isl_take isl_map *map);
890         __isl_give isl_union_set *isl_union_set_from_set(
891                 __isl_take isl_set *set);
892
893 Sets and relations can be copied and freed again using the following
894 functions.
895
896         __isl_give isl_basic_set *isl_basic_set_copy(
897                 __isl_keep isl_basic_set *bset);
898         __isl_give isl_set *isl_set_copy(__isl_keep isl_set *set);
899         __isl_give isl_union_set *isl_union_set_copy(
900                 __isl_keep isl_union_set *uset);
901         __isl_give isl_basic_map *isl_basic_map_copy(
902                 __isl_keep isl_basic_map *bmap);
903         __isl_give isl_map *isl_map_copy(__isl_keep isl_map *map);
904         __isl_give isl_union_map *isl_union_map_copy(
905                 __isl_keep isl_union_map *umap);
906         void isl_basic_set_free(__isl_take isl_basic_set *bset);
907         void isl_set_free(__isl_take isl_set *set);
908         void isl_union_set_free(__isl_take isl_union_set *uset);
909         void isl_basic_map_free(__isl_take isl_basic_map *bmap);
910         void isl_map_free(__isl_take isl_map *map);
911         void isl_union_map_free(__isl_take isl_union_map *umap);
912
913 Other sets and relations can be constructed by starting
914 from a universe set or relation, adding equality and/or
915 inequality constraints and then projecting out the
916 existentially quantified variables, if any.
917 Constraints can be constructed, manipulated and
918 added to (basic) sets and relations using the following functions.
919
920         #include <isl/constraint.h>
921         __isl_give isl_constraint *isl_equality_alloc(
922                 __isl_take isl_dim *dim);
923         __isl_give isl_constraint *isl_inequality_alloc(
924                 __isl_take isl_dim *dim);
925         void isl_constraint_set_constant(
926                 __isl_keep isl_constraint *constraint, isl_int v);
927         void isl_constraint_set_coefficient(
928                 __isl_keep isl_constraint *constraint,
929                 enum isl_dim_type type, int pos, isl_int v);
930         __isl_give isl_basic_map *isl_basic_map_add_constraint(
931                 __isl_take isl_basic_map *bmap,
932                 __isl_take isl_constraint *constraint);
933         __isl_give isl_basic_set *isl_basic_set_add_constraint(
934                 __isl_take isl_basic_set *bset,
935                 __isl_take isl_constraint *constraint);
936         __isl_give isl_map *isl_map_add_constraint(
937                 __isl_take isl_map *map,
938                 __isl_take isl_constraint *constraint);
939         __isl_give isl_set *isl_set_add_constraint(
940                 __isl_take isl_set *set,
941                 __isl_take isl_constraint *constraint);
942
943 For example, to create a set containing the even integers
944 between 10 and 42, you would use the following code.
945
946         isl_int v;
947         struct isl_dim *dim;
948         struct isl_constraint *c;
949         struct isl_basic_set *bset;
950
951         isl_int_init(v);
952         dim = isl_dim_set_alloc(ctx, 0, 2);
953         bset = isl_basic_set_universe(isl_dim_copy(dim));
954
955         c = isl_equality_alloc(isl_dim_copy(dim));
956         isl_int_set_si(v, -1);
957         isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
958         isl_int_set_si(v, 2);
959         isl_constraint_set_coefficient(c, isl_dim_set, 1, v);
960         bset = isl_basic_set_add_constraint(bset, c);
961
962         c = isl_inequality_alloc(isl_dim_copy(dim));
963         isl_int_set_si(v, -10);
964         isl_constraint_set_constant(c, v);
965         isl_int_set_si(v, 1);
966         isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
967         bset = isl_basic_set_add_constraint(bset, c);
968
969         c = isl_inequality_alloc(dim);
970         isl_int_set_si(v, 42);
971         isl_constraint_set_constant(c, v);
972         isl_int_set_si(v, -1);
973         isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
974         bset = isl_basic_set_add_constraint(bset, c);
975
976         bset = isl_basic_set_project_out(bset, isl_dim_set, 1, 1);
977
978         isl_int_clear(v);
979
980 Or, alternatively,
981
982         struct isl_basic_set *bset;
983         bset = isl_basic_set_read_from_str(ctx,
984                 "{[i] : exists (a : i = 2a and i >= 10 and i <= 42)}", -1);
985
986 A basic set or relation can also be constructed from two matrices
987 describing the equalities and the inequalities.
988
989         __isl_give isl_basic_set *isl_basic_set_from_constraint_matrices(
990                 __isl_take isl_dim *dim,
991                 __isl_take isl_mat *eq, __isl_take isl_mat *ineq,
992                 enum isl_dim_type c1,
993                 enum isl_dim_type c2, enum isl_dim_type c3,
994                 enum isl_dim_type c4);
995         __isl_give isl_basic_map *isl_basic_map_from_constraint_matrices(
996                 __isl_take isl_dim *dim,
997                 __isl_take isl_mat *eq, __isl_take isl_mat *ineq,
998                 enum isl_dim_type c1,
999                 enum isl_dim_type c2, enum isl_dim_type c3,
1000                 enum isl_dim_type c4, enum isl_dim_type c5);
1001
1002 The C<isl_dim_type> arguments indicate the order in which
1003 different kinds of variables appear in the input matrices
1004 and should be a permutation of C<isl_dim_cst>, C<isl_dim_param>,
1005 C<isl_dim_set> and C<isl_dim_div> for sets and
1006 of C<isl_dim_cst>, C<isl_dim_param>,
1007 C<isl_dim_in>, C<isl_dim_out> and C<isl_dim_div> for relations.
1008
1009 =head2 Inspecting Sets and Relations
1010
1011 Usually, the user should not have to care about the actual constraints
1012 of the sets and maps, but should instead apply the abstract operations
1013 explained in the following sections.
1014 Occasionally, however, it may be required to inspect the individual
1015 coefficients of the constraints.  This section explains how to do so.
1016 In these cases, it may also be useful to have C<isl> compute
1017 an explicit representation of the existentially quantified variables.
1018
1019         __isl_give isl_set *isl_set_compute_divs(
1020                 __isl_take isl_set *set);
1021         __isl_give isl_map *isl_map_compute_divs(
1022                 __isl_take isl_map *map);
1023         __isl_give isl_union_set *isl_union_set_compute_divs(
1024                 __isl_take isl_union_set *uset);
1025         __isl_give isl_union_map *isl_union_map_compute_divs(
1026                 __isl_take isl_union_map *umap);
1027
1028 This explicit representation defines the existentially quantified
1029 variables as integer divisions of the other variables, possibly
1030 including earlier existentially quantified variables.
1031 An explicitly represented existentially quantified variable therefore
1032 has a unique value when the values of the other variables are known.
1033 If, furthermore, the same existentials, i.e., existentials
1034 with the same explicit representations, should appear in the
1035 same order in each of the disjuncts of a set or map, then the user should call
1036 either of the following functions.
1037
1038         __isl_give isl_set *isl_set_align_divs(
1039                 __isl_take isl_set *set);
1040         __isl_give isl_map *isl_map_align_divs(
1041                 __isl_take isl_map *map);
1042
1043 Alternatively, the existentially quantified variables can be removed
1044 using the following functions, which compute an overapproximation.
1045
1046         __isl_give isl_basic_set *isl_basic_set_remove_divs(
1047                 __isl_take isl_basic_set *bset);
1048         __isl_give isl_basic_map *isl_basic_map_remove_divs(
1049                 __isl_take isl_basic_map *bmap);
1050         __isl_give isl_set *isl_set_remove_divs(
1051                 __isl_take isl_set *set);
1052         __isl_give isl_map *isl_map_remove_divs(
1053                 __isl_take isl_map *map);
1054
1055 To iterate over all the sets or maps in a union set or map, use
1056
1057         int isl_union_set_foreach_set(__isl_keep isl_union_set *uset,
1058                 int (*fn)(__isl_take isl_set *set, void *user),
1059                 void *user);
1060         int isl_union_map_foreach_map(__isl_keep isl_union_map *umap,
1061                 int (*fn)(__isl_take isl_map *map, void *user),
1062                 void *user);
1063
1064 The number of sets or maps in a union set or map can be obtained
1065 from
1066
1067         int isl_union_set_n_set(__isl_keep isl_union_set *uset);
1068         int isl_union_map_n_map(__isl_keep isl_union_map *umap);
1069
1070 To extract the set or map from a union with a given dimension
1071 specification, use
1072
1073         __isl_give isl_set *isl_union_set_extract_set(
1074                 __isl_keep isl_union_set *uset,
1075                 __isl_take isl_dim *dim);
1076         __isl_give isl_map *isl_union_map_extract_map(
1077                 __isl_keep isl_union_map *umap,
1078                 __isl_take isl_dim *dim);
1079
1080 To iterate over all the basic sets or maps in a set or map, use
1081
1082         int isl_set_foreach_basic_set(__isl_keep isl_set *set,
1083                 int (*fn)(__isl_take isl_basic_set *bset, void *user),
1084                 void *user);
1085         int isl_map_foreach_basic_map(__isl_keep isl_map *map,
1086                 int (*fn)(__isl_take isl_basic_map *bmap, void *user),
1087                 void *user);
1088
1089 The callback function C<fn> should return 0 if successful and
1090 -1 if an error occurs.  In the latter case, or if any other error
1091 occurs, the above functions will return -1.
1092
1093 It should be noted that C<isl> does not guarantee that
1094 the basic sets or maps passed to C<fn> are disjoint.
1095 If this is required, then the user should call one of
1096 the following functions first.
1097
1098         __isl_give isl_set *isl_set_make_disjoint(
1099                 __isl_take isl_set *set);
1100         __isl_give isl_map *isl_map_make_disjoint(
1101                 __isl_take isl_map *map);
1102
1103 The number of basic sets in a set can be obtained
1104 from
1105
1106         int isl_set_n_basic_set(__isl_keep isl_set *set);
1107
1108 To iterate over the constraints of a basic set or map, use
1109
1110         #include <isl/constraint.h>
1111
1112         int isl_basic_map_foreach_constraint(
1113                 __isl_keep isl_basic_map *bmap,
1114                 int (*fn)(__isl_take isl_constraint *c, void *user),
1115                 void *user);
1116         void isl_constraint_free(struct isl_constraint *c);
1117
1118 Again, the callback function C<fn> should return 0 if successful and
1119 -1 if an error occurs.  In the latter case, or if any other error
1120 occurs, the above functions will return -1.
1121 The constraint C<c> represents either an equality or an inequality.
1122 Use the following function to find out whether a constraint
1123 represents an equality.  If not, it represents an inequality.
1124
1125         int isl_constraint_is_equality(
1126                 __isl_keep isl_constraint *constraint);
1127
1128 The coefficients of the constraints can be inspected using
1129 the following functions.
1130
1131         void isl_constraint_get_constant(
1132                 __isl_keep isl_constraint *constraint, isl_int *v);
1133         void isl_constraint_get_coefficient(
1134                 __isl_keep isl_constraint *constraint,
1135                 enum isl_dim_type type, int pos, isl_int *v);
1136         int isl_constraint_involves_dims(
1137                 __isl_keep isl_constraint *constraint,
1138                 enum isl_dim_type type, unsigned first, unsigned n);
1139
1140 The explicit representations of the existentially quantified
1141 variables can be inspected using the following functions.
1142 Note that the user is only allowed to use these functions
1143 if the inspected set or map is the result of a call
1144 to C<isl_set_compute_divs> or C<isl_map_compute_divs>.
1145
1146         __isl_give isl_div *isl_constraint_div(
1147                 __isl_keep isl_constraint *constraint, int pos);
1148         isl_ctx *isl_div_get_ctx(__isl_keep isl_div *div);
1149         void isl_div_get_constant(__isl_keep isl_div *div,
1150                 isl_int *v);
1151         void isl_div_get_denominator(__isl_keep isl_div *div,
1152                 isl_int *v);
1153         void isl_div_get_coefficient(__isl_keep isl_div *div,
1154                 enum isl_dim_type type, int pos, isl_int *v);
1155
1156 To obtain the constraints of a basic set or map in matrix
1157 form, use the following functions.
1158
1159         __isl_give isl_mat *isl_basic_set_equalities_matrix(
1160                 __isl_keep isl_basic_set *bset,
1161                 enum isl_dim_type c1, enum isl_dim_type c2,
1162                 enum isl_dim_type c3, enum isl_dim_type c4);
1163         __isl_give isl_mat *isl_basic_set_inequalities_matrix(
1164                 __isl_keep isl_basic_set *bset,
1165                 enum isl_dim_type c1, enum isl_dim_type c2,
1166                 enum isl_dim_type c3, enum isl_dim_type c4);
1167         __isl_give isl_mat *isl_basic_map_equalities_matrix(
1168                 __isl_keep isl_basic_map *bmap,
1169                 enum isl_dim_type c1,
1170                 enum isl_dim_type c2, enum isl_dim_type c3,
1171                 enum isl_dim_type c4, enum isl_dim_type c5);
1172         __isl_give isl_mat *isl_basic_map_inequalities_matrix(
1173                 __isl_keep isl_basic_map *bmap,
1174                 enum isl_dim_type c1,
1175                 enum isl_dim_type c2, enum isl_dim_type c3,
1176                 enum isl_dim_type c4, enum isl_dim_type c5);
1177
1178 The C<isl_dim_type> arguments dictate the order in which
1179 different kinds of variables appear in the resulting matrix
1180 and should be a permutation of C<isl_dim_cst>, C<isl_dim_param>,
1181 C<isl_dim_in>, C<isl_dim_out> and C<isl_dim_div>.
1182
1183 The names of the domain and range spaces of a set or relation can be
1184 read off using the following functions.
1185
1186         const char *isl_basic_set_get_tuple_name(
1187                 __isl_keep isl_basic_set *bset);
1188         const char *isl_set_get_tuple_name(
1189                 __isl_keep isl_set *set);
1190         const char *isl_basic_map_get_tuple_name(
1191                 __isl_keep isl_basic_map *bmap,
1192                 enum isl_dim_type type);
1193         const char *isl_map_get_tuple_name(
1194                 __isl_keep isl_map *map,
1195                 enum isl_dim_type type);
1196
1197 As with C<isl_dim_get_tuple_name>, the value returned points to
1198 an internal data structure.
1199 The names of individual dimensions can be read off using
1200 the following functions.
1201
1202         const char *isl_constraint_get_dim_name(
1203                 __isl_keep isl_constraint *constraint,
1204                 enum isl_dim_type type, unsigned pos);
1205         const char *isl_basic_set_get_dim_name(
1206                 __isl_keep isl_basic_set *bset,
1207                 enum isl_dim_type type, unsigned pos);
1208         const char *isl_set_get_dim_name(
1209                 __isl_keep isl_set *set,
1210                 enum isl_dim_type type, unsigned pos);
1211         const char *isl_basic_map_get_dim_name(
1212                 __isl_keep isl_basic_map *bmap,
1213                 enum isl_dim_type type, unsigned pos);
1214         const char *isl_map_get_dim_name(
1215                 __isl_keep isl_map *map,
1216                 enum isl_dim_type type, unsigned pos);
1217
1218 These functions are mostly useful to obtain the names
1219 of the parameters.
1220
1221 =head2 Properties
1222
1223 =head3 Unary Properties
1224
1225 =over
1226
1227 =item * Emptiness
1228
1229 The following functions test whether the given set or relation
1230 contains any integer points.  The ``plain'' variants do not perform
1231 any computations, but simply check if the given set or relation
1232 is already known to be empty.
1233
1234         int isl_basic_set_plain_is_empty(__isl_keep isl_basic_set *bset);
1235         int isl_basic_set_is_empty(__isl_keep isl_basic_set *bset);
1236         int isl_set_plain_is_empty(__isl_keep isl_set *set);
1237         int isl_set_is_empty(__isl_keep isl_set *set);
1238         int isl_union_set_is_empty(__isl_keep isl_union_set *uset);
1239         int isl_basic_map_plain_is_empty(__isl_keep isl_basic_map *bmap);
1240         int isl_basic_map_is_empty(__isl_keep isl_basic_map *bmap);
1241         int isl_map_plain_is_empty(__isl_keep isl_map *map);
1242         int isl_map_is_empty(__isl_keep isl_map *map);
1243         int isl_union_map_is_empty(__isl_keep isl_union_map *umap);
1244
1245 =item * Universality
1246
1247         int isl_basic_set_is_universe(__isl_keep isl_basic_set *bset);
1248         int isl_basic_map_is_universe(__isl_keep isl_basic_map *bmap);
1249         int isl_set_plain_is_universe(__isl_keep isl_set *set);
1250
1251 =item * Single-valuedness
1252
1253         int isl_map_is_single_valued(__isl_keep isl_map *map);
1254         int isl_union_map_is_single_valued(__isl_keep isl_union_map *umap);
1255
1256 =item * Injectivity
1257
1258         int isl_map_plain_is_injective(__isl_keep isl_map *map);
1259         int isl_map_is_injective(__isl_keep isl_map *map);
1260         int isl_union_map_plain_is_injective(
1261                 __isl_keep isl_union_map *umap);
1262         int isl_union_map_is_injective(
1263                 __isl_keep isl_union_map *umap);
1264
1265 =item * Bijectivity
1266
1267         int isl_map_is_bijective(__isl_keep isl_map *map);
1268         int isl_union_map_is_bijective(__isl_keep isl_union_map *umap);
1269
1270 =item * Wrapping
1271
1272 The following functions check whether the domain of the given
1273 (basic) set is a wrapped relation.
1274
1275         int isl_basic_set_is_wrapping(
1276                 __isl_keep isl_basic_set *bset);
1277         int isl_set_is_wrapping(__isl_keep isl_set *set);
1278
1279 =item * Internal Product
1280
1281         int isl_basic_map_can_zip(
1282                 __isl_keep isl_basic_map *bmap);
1283         int isl_map_can_zip(__isl_keep isl_map *map);
1284
1285 Check whether the product of domain and range of the given relation
1286 can be computed,
1287 i.e., whether both domain and range are nested relations.
1288
1289 =back
1290
1291 =head3 Binary Properties
1292
1293 =over
1294
1295 =item * Equality
1296
1297         int isl_set_plain_is_equal(__isl_keep isl_set *set1,
1298                 __isl_keep isl_set *set2);
1299         int isl_set_is_equal(__isl_keep isl_set *set1,
1300                 __isl_keep isl_set *set2);
1301         int isl_union_set_is_equal(
1302                 __isl_keep isl_union_set *uset1,
1303                 __isl_keep isl_union_set *uset2);
1304         int isl_basic_map_is_equal(
1305                 __isl_keep isl_basic_map *bmap1,
1306                 __isl_keep isl_basic_map *bmap2);
1307         int isl_map_is_equal(__isl_keep isl_map *map1,
1308                 __isl_keep isl_map *map2);
1309         int isl_map_plain_is_equal(__isl_keep isl_map *map1,
1310                 __isl_keep isl_map *map2);
1311         int isl_union_map_is_equal(
1312                 __isl_keep isl_union_map *umap1,
1313                 __isl_keep isl_union_map *umap2);
1314
1315 =item * Disjointness
1316
1317         int isl_set_plain_is_disjoint(__isl_keep isl_set *set1,
1318                 __isl_keep isl_set *set2);
1319
1320 =item * Subset
1321
1322         int isl_set_is_subset(__isl_keep isl_set *set1,
1323                 __isl_keep isl_set *set2);
1324         int isl_set_is_strict_subset(
1325                 __isl_keep isl_set *set1,
1326                 __isl_keep isl_set *set2);
1327         int isl_union_set_is_subset(
1328                 __isl_keep isl_union_set *uset1,
1329                 __isl_keep isl_union_set *uset2);
1330         int isl_union_set_is_strict_subset(
1331                 __isl_keep isl_union_set *uset1,
1332                 __isl_keep isl_union_set *uset2);
1333         int isl_basic_map_is_subset(
1334                 __isl_keep isl_basic_map *bmap1,
1335                 __isl_keep isl_basic_map *bmap2);
1336         int isl_basic_map_is_strict_subset(
1337                 __isl_keep isl_basic_map *bmap1,
1338                 __isl_keep isl_basic_map *bmap2);
1339         int isl_map_is_subset(
1340                 __isl_keep isl_map *map1,
1341                 __isl_keep isl_map *map2);
1342         int isl_map_is_strict_subset(
1343                 __isl_keep isl_map *map1,
1344                 __isl_keep isl_map *map2);
1345         int isl_union_map_is_subset(
1346                 __isl_keep isl_union_map *umap1,
1347                 __isl_keep isl_union_map *umap2);
1348         int isl_union_map_is_strict_subset(
1349                 __isl_keep isl_union_map *umap1,
1350                 __isl_keep isl_union_map *umap2);
1351
1352 =back
1353
1354 =head2 Unary Operations
1355
1356 =over
1357
1358 =item * Complement
1359
1360         __isl_give isl_set *isl_set_complement(
1361                 __isl_take isl_set *set);
1362
1363 =item * Inverse map
1364
1365         __isl_give isl_basic_map *isl_basic_map_reverse(
1366                 __isl_take isl_basic_map *bmap);
1367         __isl_give isl_map *isl_map_reverse(
1368                 __isl_take isl_map *map);
1369         __isl_give isl_union_map *isl_union_map_reverse(
1370                 __isl_take isl_union_map *umap);
1371
1372 =item * Projection
1373
1374         __isl_give isl_basic_set *isl_basic_set_project_out(
1375                 __isl_take isl_basic_set *bset,
1376                 enum isl_dim_type type, unsigned first, unsigned n);
1377         __isl_give isl_basic_map *isl_basic_map_project_out(
1378                 __isl_take isl_basic_map *bmap,
1379                 enum isl_dim_type type, unsigned first, unsigned n);
1380         __isl_give isl_set *isl_set_project_out(__isl_take isl_set *set,
1381                 enum isl_dim_type type, unsigned first, unsigned n);
1382         __isl_give isl_map *isl_map_project_out(__isl_take isl_map *map,
1383                 enum isl_dim_type type, unsigned first, unsigned n);
1384         __isl_give isl_basic_set *isl_basic_map_domain(
1385                 __isl_take isl_basic_map *bmap);
1386         __isl_give isl_basic_set *isl_basic_map_range(
1387                 __isl_take isl_basic_map *bmap);
1388         __isl_give isl_set *isl_map_domain(
1389                 __isl_take isl_map *bmap);
1390         __isl_give isl_set *isl_map_range(
1391                 __isl_take isl_map *map);
1392         __isl_give isl_union_set *isl_union_map_domain(
1393                 __isl_take isl_union_map *umap);
1394         __isl_give isl_union_set *isl_union_map_range(
1395                 __isl_take isl_union_map *umap);
1396
1397         __isl_give isl_basic_map *isl_basic_map_domain_map(
1398                 __isl_take isl_basic_map *bmap);
1399         __isl_give isl_basic_map *isl_basic_map_range_map(
1400                 __isl_take isl_basic_map *bmap);
1401         __isl_give isl_map *isl_map_domain_map(__isl_take isl_map *map);
1402         __isl_give isl_map *isl_map_range_map(__isl_take isl_map *map);
1403         __isl_give isl_union_map *isl_union_map_domain_map(
1404                 __isl_take isl_union_map *umap);
1405         __isl_give isl_union_map *isl_union_map_range_map(
1406                 __isl_take isl_union_map *umap);
1407
1408 The functions above construct a (basic, regular or union) relation
1409 that maps (a wrapped version of) the input relation to its domain or range.
1410
1411 =item * Elimination
1412
1413         __isl_give isl_set *isl_set_eliminate(
1414                 __isl_take isl_set *set, enum isl_dim_type type,
1415                 unsigned first, unsigned n);
1416
1417 Eliminate the coefficients for the given dimensions from the constraints,
1418 without removing the dimensions.
1419
1420 =item * Slicing
1421
1422         __isl_give isl_basic_set *isl_basic_set_fix(
1423                 __isl_take isl_basic_set *bset,
1424                 enum isl_dim_type type, unsigned pos,
1425                 isl_int value);
1426         __isl_give isl_basic_set *isl_basic_set_fix_si(
1427                 __isl_take isl_basic_set *bset,
1428                 enum isl_dim_type type, unsigned pos, int value);
1429         __isl_give isl_set *isl_set_fix(__isl_take isl_set *set,
1430                 enum isl_dim_type type, unsigned pos,
1431                 isl_int value);
1432         __isl_give isl_set *isl_set_fix_si(__isl_take isl_set *set,
1433                 enum isl_dim_type type, unsigned pos, int value);
1434         __isl_give isl_basic_map *isl_basic_map_fix_si(
1435                 __isl_take isl_basic_map *bmap,
1436                 enum isl_dim_type type, unsigned pos, int value);
1437         __isl_give isl_map *isl_map_fix_si(__isl_take isl_map *map,
1438                 enum isl_dim_type type, unsigned pos, int value);
1439
1440 Intersect the set or relation with the hyperplane where the given
1441 dimension has the fixed given value.
1442
1443 =item * Identity
1444
1445         __isl_give isl_map *isl_set_identity(
1446                 __isl_take isl_set *set);
1447         __isl_give isl_union_map *isl_union_set_identity(
1448                 __isl_take isl_union_set *uset);
1449
1450 Construct an identity relation on the given (union) set.
1451
1452 =item * Deltas
1453
1454         __isl_give isl_basic_set *isl_basic_map_deltas(
1455                 __isl_take isl_basic_map *bmap);
1456         __isl_give isl_set *isl_map_deltas(__isl_take isl_map *map);
1457         __isl_give isl_union_set *isl_union_map_deltas(
1458                 __isl_take isl_union_map *umap);
1459
1460 These functions return a (basic) set containing the differences
1461 between image elements and corresponding domain elements in the input.
1462
1463         __isl_give isl_basic_map *isl_basic_map_deltas_map(
1464                 __isl_take isl_basic_map *bmap);
1465         __isl_give isl_map *isl_map_deltas_map(
1466                 __isl_take isl_map *map);
1467         __isl_give isl_union_map *isl_union_map_deltas_map(
1468                 __isl_take isl_union_map *umap);
1469
1470 The functions above construct a (basic, regular or union) relation
1471 that maps (a wrapped version of) the input relation to its delta set.
1472
1473 =item * Coalescing
1474
1475 Simplify the representation of a set or relation by trying
1476 to combine pairs of basic sets or relations into a single
1477 basic set or relation.
1478
1479         __isl_give isl_set *isl_set_coalesce(__isl_take isl_set *set);
1480         __isl_give isl_map *isl_map_coalesce(__isl_take isl_map *map);
1481         __isl_give isl_union_set *isl_union_set_coalesce(
1482                 __isl_take isl_union_set *uset);
1483         __isl_give isl_union_map *isl_union_map_coalesce(
1484                 __isl_take isl_union_map *umap);
1485
1486 =item * Detecting equalities
1487
1488         __isl_give isl_basic_set *isl_basic_set_detect_equalities(
1489                 __isl_take isl_basic_set *bset);
1490         __isl_give isl_basic_map *isl_basic_map_detect_equalities(
1491                 __isl_take isl_basic_map *bmap);
1492         __isl_give isl_set *isl_set_detect_equalities(
1493                 __isl_take isl_set *set);
1494         __isl_give isl_map *isl_map_detect_equalities(
1495                 __isl_take isl_map *map);
1496         __isl_give isl_union_set *isl_union_set_detect_equalities(
1497                 __isl_take isl_union_set *uset);
1498         __isl_give isl_union_map *isl_union_map_detect_equalities(
1499                 __isl_take isl_union_map *umap);
1500
1501 Simplify the representation of a set or relation by detecting implicit
1502 equalities.
1503
1504 =item * Removing redundant constraints
1505
1506         __isl_give isl_basic_set *isl_basic_set_remove_redundancies(
1507                 __isl_take isl_basic_set *bset);
1508         __isl_give isl_basic_map *isl_basic_map_remove_redundancies(
1509                 __isl_take isl_basic_map *bmap);
1510
1511 =item * Convex hull
1512
1513         __isl_give isl_basic_set *isl_set_convex_hull(
1514                 __isl_take isl_set *set);
1515         __isl_give isl_basic_map *isl_map_convex_hull(
1516                 __isl_take isl_map *map);
1517
1518 If the input set or relation has any existentially quantified
1519 variables, then the result of these operations is currently undefined.
1520
1521 =item * Simple hull
1522
1523         __isl_give isl_basic_set *isl_set_simple_hull(
1524                 __isl_take isl_set *set);
1525         __isl_give isl_basic_map *isl_map_simple_hull(
1526                 __isl_take isl_map *map);
1527         __isl_give isl_union_map *isl_union_map_simple_hull(
1528                 __isl_take isl_union_map *umap);
1529
1530 These functions compute a single basic set or relation
1531 that contains the whole input set or relation.
1532 In particular, the output is described by translates
1533 of the constraints describing the basic sets or relations in the input.
1534
1535 =begin latex
1536
1537 (See \autoref{s:simple hull}.)
1538
1539 =end latex
1540
1541 =item * Affine hull
1542
1543         __isl_give isl_basic_set *isl_basic_set_affine_hull(
1544                 __isl_take isl_basic_set *bset);
1545         __isl_give isl_basic_set *isl_set_affine_hull(
1546                 __isl_take isl_set *set);
1547         __isl_give isl_union_set *isl_union_set_affine_hull(
1548                 __isl_take isl_union_set *uset);
1549         __isl_give isl_basic_map *isl_basic_map_affine_hull(
1550                 __isl_take isl_basic_map *bmap);
1551         __isl_give isl_basic_map *isl_map_affine_hull(
1552                 __isl_take isl_map *map);
1553         __isl_give isl_union_map *isl_union_map_affine_hull(
1554                 __isl_take isl_union_map *umap);
1555
1556 In case of union sets and relations, the affine hull is computed
1557 per space.
1558
1559 =item * Polyhedral hull
1560
1561         __isl_give isl_basic_set *isl_set_polyhedral_hull(
1562                 __isl_take isl_set *set);
1563         __isl_give isl_basic_map *isl_map_polyhedral_hull(
1564                 __isl_take isl_map *map);
1565         __isl_give isl_union_set *isl_union_set_polyhedral_hull(
1566                 __isl_take isl_union_set *uset);
1567         __isl_give isl_union_map *isl_union_map_polyhedral_hull(
1568                 __isl_take isl_union_map *umap);
1569
1570 These functions compute a single basic set or relation
1571 not involving any existentially quantified variables
1572 that contains the whole input set or relation.
1573 In case of union sets and relations, the polyhedral hull is computed
1574 per space.
1575
1576 =item * Optimization
1577
1578         #include <isl/ilp.h>
1579         enum isl_lp_result isl_basic_set_max(
1580                 __isl_keep isl_basic_set *bset,
1581                 __isl_keep isl_aff *obj, isl_int *opt)
1582         enum isl_lp_result isl_set_max(__isl_keep isl_set *set,
1583                 __isl_keep isl_aff *obj, isl_int *opt);
1584
1585 Compute the maximum of the integer affine expression C<obj>
1586 over the points in C<set>, returning the result in C<opt>.
1587 The return value may be one of C<isl_lp_error>,
1588 C<isl_lp_ok>, C<isl_lp_unbounded> or C<isl_lp_empty>.
1589
1590 =item * Dual
1591
1592 The following functions compute either the set of (rational) coefficient
1593 values of valid constraints for the given set or the set of (rational)
1594 values satisfying the constraints with coefficients from the given set.
1595 Internally, these two sets of functions perform essentially the
1596 same operations, except that the set of coefficients is assumed to
1597 be a cone, while the set of values may be any polyhedron.
1598 The current implementation is based on the Farkas lemma and
1599 Fourier-Motzkin elimination, but this may change or be made optional
1600 in future.  In particular, future implementations may use different
1601 dualization algorithms or skip the elimination step.
1602
1603         __isl_give isl_basic_set *isl_basic_set_coefficients(
1604                 __isl_take isl_basic_set *bset);
1605         __isl_give isl_basic_set *isl_set_coefficients(
1606                 __isl_take isl_set *set);
1607         __isl_give isl_union_set *isl_union_set_coefficients(
1608                 __isl_take isl_union_set *bset);
1609         __isl_give isl_basic_set *isl_basic_set_solutions(
1610                 __isl_take isl_basic_set *bset);
1611         __isl_give isl_basic_set *isl_set_solutions(
1612                 __isl_take isl_set *set);
1613         __isl_give isl_union_set *isl_union_set_solutions(
1614                 __isl_take isl_union_set *bset);
1615
1616 =item * Power
1617
1618         __isl_give isl_map *isl_map_power(__isl_take isl_map *map,
1619                 int *exact);
1620         __isl_give isl_union_map *isl_union_map_power(
1621                 __isl_take isl_union_map *umap, int *exact);
1622
1623 Compute a parametric representation for all positive powers I<k> of C<map>.
1624 The result maps I<k> to a nested relation corresponding to the
1625 I<k>th power of C<map>.
1626 The result may be an overapproximation.  If the result is known to be exact,
1627 then C<*exact> is set to C<1>.
1628
1629 =item * Transitive closure
1630
1631         __isl_give isl_map *isl_map_transitive_closure(
1632                 __isl_take isl_map *map, int *exact);
1633         __isl_give isl_union_map *isl_union_map_transitive_closure(
1634                 __isl_take isl_union_map *umap, int *exact);
1635
1636 Compute the transitive closure of C<map>.
1637 The result may be an overapproximation.  If the result is known to be exact,
1638 then C<*exact> is set to C<1>.
1639
1640 =item * Reaching path lengths
1641
1642         __isl_give isl_map *isl_map_reaching_path_lengths(
1643                 __isl_take isl_map *map, int *exact);
1644
1645 Compute a relation that maps each element in the range of C<map>
1646 to the lengths of all paths composed of edges in C<map> that
1647 end up in the given element.
1648 The result may be an overapproximation.  If the result is known to be exact,
1649 then C<*exact> is set to C<1>.
1650 To compute the I<maximal> path length, the resulting relation
1651 should be postprocessed by C<isl_map_lexmax>.
1652 In particular, if the input relation is a dependence relation
1653 (mapping sources to sinks), then the maximal path length corresponds
1654 to the free schedule.
1655 Note, however, that C<isl_map_lexmax> expects the maximum to be
1656 finite, so if the path lengths are unbounded (possibly due to
1657 the overapproximation), then you will get an error message.
1658
1659 =item * Wrapping
1660
1661         __isl_give isl_basic_set *isl_basic_map_wrap(
1662                 __isl_take isl_basic_map *bmap);
1663         __isl_give isl_set *isl_map_wrap(
1664                 __isl_take isl_map *map);
1665         __isl_give isl_union_set *isl_union_map_wrap(
1666                 __isl_take isl_union_map *umap);
1667         __isl_give isl_basic_map *isl_basic_set_unwrap(
1668                 __isl_take isl_basic_set *bset);
1669         __isl_give isl_map *isl_set_unwrap(
1670                 __isl_take isl_set *set);
1671         __isl_give isl_union_map *isl_union_set_unwrap(
1672                 __isl_take isl_union_set *uset);
1673
1674 =item * Flattening
1675
1676 Remove any internal structure of domain (and range) of the given
1677 set or relation.  If there is any such internal structure in the input,
1678 then the name of the space is also removed.
1679
1680         __isl_give isl_basic_set *isl_basic_set_flatten(
1681                 __isl_take isl_basic_set *bset);
1682         __isl_give isl_set *isl_set_flatten(
1683                 __isl_take isl_set *set);
1684         __isl_give isl_basic_map *isl_basic_map_flatten_range(
1685                 __isl_take isl_basic_map *bmap);
1686         __isl_give isl_map *isl_map_flatten_range(
1687                 __isl_take isl_map *map);
1688         __isl_give isl_basic_map *isl_basic_map_flatten(
1689                 __isl_take isl_basic_map *bmap);
1690         __isl_give isl_map *isl_map_flatten(
1691                 __isl_take isl_map *map);
1692
1693         __isl_give isl_map *isl_set_flatten_map(
1694                 __isl_take isl_set *set);
1695
1696 The function above constructs a relation
1697 that maps the input set to a flattened version of the set.
1698
1699 =item * Lifting
1700
1701 Lift the input set to a space with extra dimensions corresponding
1702 to the existentially quantified variables in the input.
1703 In particular, the result lives in a wrapped map where the domain
1704 is the original space and the range corresponds to the original
1705 existentially quantified variables.
1706
1707         __isl_give isl_basic_set *isl_basic_set_lift(
1708                 __isl_take isl_basic_set *bset);
1709         __isl_give isl_set *isl_set_lift(
1710                 __isl_take isl_set *set);
1711         __isl_give isl_union_set *isl_union_set_lift(
1712                 __isl_take isl_union_set *uset);
1713
1714 =item * Internal Product
1715
1716         __isl_give isl_basic_map *isl_basic_map_zip(
1717                 __isl_take isl_basic_map *bmap);
1718         __isl_give isl_map *isl_map_zip(
1719                 __isl_take isl_map *map);
1720         __isl_give isl_union_map *isl_union_map_zip(
1721                 __isl_take isl_union_map *umap);
1722
1723 Given a relation with nested relations for domain and range,
1724 interchange the range of the domain with the domain of the range.
1725
1726 =item * Aligning parameters
1727
1728         __isl_give isl_set *isl_set_align_params(
1729                 __isl_take isl_set *set,
1730                 __isl_take isl_dim *model);
1731         __isl_give isl_map *isl_map_align_params(
1732                 __isl_take isl_map *map,
1733                 __isl_take isl_dim *model);
1734
1735 Change the order of the parameters of the given set or relation
1736 such that the first parameters match those of C<model>.
1737 This may involve the introduction of extra parameters.
1738 All parameters need to be named.
1739
1740 =item * Dimension manipulation
1741
1742         __isl_give isl_set *isl_set_add_dims(
1743                 __isl_take isl_set *set,
1744                 enum isl_dim_type type, unsigned n);
1745         __isl_give isl_map *isl_map_add_dims(
1746                 __isl_take isl_map *map,
1747                 enum isl_dim_type type, unsigned n);
1748
1749 It is usually not advisable to directly change the (input or output)
1750 space of a set or a relation as this removes the name and the internal
1751 structure of the space.  However, the above functions can be useful
1752 to add new parameters, assuming
1753 C<isl_set_align_params> and C<isl_map_align_params>
1754 are not sufficient.
1755
1756 =back
1757
1758 =head2 Binary Operations
1759
1760 The two arguments of a binary operation not only need to live
1761 in the same C<isl_ctx>, they currently also need to have
1762 the same (number of) parameters.
1763
1764 =head3 Basic Operations
1765
1766 =over
1767
1768 =item * Intersection
1769
1770         __isl_give isl_basic_set *isl_basic_set_intersect(
1771                 __isl_take isl_basic_set *bset1,
1772                 __isl_take isl_basic_set *bset2);
1773         __isl_give isl_set *isl_set_intersect(
1774                 __isl_take isl_set *set1,
1775                 __isl_take isl_set *set2);
1776         __isl_give isl_union_set *isl_union_set_intersect(
1777                 __isl_take isl_union_set *uset1,
1778                 __isl_take isl_union_set *uset2);
1779         __isl_give isl_basic_map *isl_basic_map_intersect_domain(
1780                 __isl_take isl_basic_map *bmap,
1781                 __isl_take isl_basic_set *bset);
1782         __isl_give isl_basic_map *isl_basic_map_intersect_range(
1783                 __isl_take isl_basic_map *bmap,
1784                 __isl_take isl_basic_set *bset);
1785         __isl_give isl_basic_map *isl_basic_map_intersect(
1786                 __isl_take isl_basic_map *bmap1,
1787                 __isl_take isl_basic_map *bmap2);
1788         __isl_give isl_map *isl_map_intersect_domain(
1789                 __isl_take isl_map *map,
1790                 __isl_take isl_set *set);
1791         __isl_give isl_map *isl_map_intersect_range(
1792                 __isl_take isl_map *map,
1793                 __isl_take isl_set *set);
1794         __isl_give isl_map *isl_map_intersect(
1795                 __isl_take isl_map *map1,
1796                 __isl_take isl_map *map2);
1797         __isl_give isl_union_map *isl_union_map_intersect_domain(
1798                 __isl_take isl_union_map *umap,
1799                 __isl_take isl_union_set *uset);
1800         __isl_give isl_union_map *isl_union_map_intersect_range(
1801                 __isl_take isl_union_map *umap,
1802                 __isl_take isl_union_set *uset);
1803         __isl_give isl_union_map *isl_union_map_intersect(
1804                 __isl_take isl_union_map *umap1,
1805                 __isl_take isl_union_map *umap2);
1806
1807 =item * Union
1808
1809         __isl_give isl_set *isl_basic_set_union(
1810                 __isl_take isl_basic_set *bset1,
1811                 __isl_take isl_basic_set *bset2);
1812         __isl_give isl_map *isl_basic_map_union(
1813                 __isl_take isl_basic_map *bmap1,
1814                 __isl_take isl_basic_map *bmap2);
1815         __isl_give isl_set *isl_set_union(
1816                 __isl_take isl_set *set1,
1817                 __isl_take isl_set *set2);
1818         __isl_give isl_map *isl_map_union(
1819                 __isl_take isl_map *map1,
1820                 __isl_take isl_map *map2);
1821         __isl_give isl_union_set *isl_union_set_union(
1822                 __isl_take isl_union_set *uset1,
1823                 __isl_take isl_union_set *uset2);
1824         __isl_give isl_union_map *isl_union_map_union(
1825                 __isl_take isl_union_map *umap1,
1826                 __isl_take isl_union_map *umap2);
1827
1828 =item * Set difference
1829
1830         __isl_give isl_set *isl_set_subtract(
1831                 __isl_take isl_set *set1,
1832                 __isl_take isl_set *set2);
1833         __isl_give isl_map *isl_map_subtract(
1834                 __isl_take isl_map *map1,
1835                 __isl_take isl_map *map2);
1836         __isl_give isl_union_set *isl_union_set_subtract(
1837                 __isl_take isl_union_set *uset1,
1838                 __isl_take isl_union_set *uset2);
1839         __isl_give isl_union_map *isl_union_map_subtract(
1840                 __isl_take isl_union_map *umap1,
1841                 __isl_take isl_union_map *umap2);
1842
1843 =item * Application
1844
1845         __isl_give isl_basic_set *isl_basic_set_apply(
1846                 __isl_take isl_basic_set *bset,
1847                 __isl_take isl_basic_map *bmap);
1848         __isl_give isl_set *isl_set_apply(
1849                 __isl_take isl_set *set,
1850                 __isl_take isl_map *map);
1851         __isl_give isl_union_set *isl_union_set_apply(
1852                 __isl_take isl_union_set *uset,
1853                 __isl_take isl_union_map *umap);
1854         __isl_give isl_basic_map *isl_basic_map_apply_domain(
1855                 __isl_take isl_basic_map *bmap1,
1856                 __isl_take isl_basic_map *bmap2);
1857         __isl_give isl_basic_map *isl_basic_map_apply_range(
1858                 __isl_take isl_basic_map *bmap1,
1859                 __isl_take isl_basic_map *bmap2);
1860         __isl_give isl_map *isl_map_apply_domain(
1861                 __isl_take isl_map *map1,
1862                 __isl_take isl_map *map2);
1863         __isl_give isl_union_map *isl_union_map_apply_domain(
1864                 __isl_take isl_union_map *umap1,
1865                 __isl_take isl_union_map *umap2);
1866         __isl_give isl_map *isl_map_apply_range(
1867                 __isl_take isl_map *map1,
1868                 __isl_take isl_map *map2);
1869         __isl_give isl_union_map *isl_union_map_apply_range(
1870                 __isl_take isl_union_map *umap1,
1871                 __isl_take isl_union_map *umap2);
1872
1873 =item * Cartesian Product
1874
1875         __isl_give isl_set *isl_set_product(
1876                 __isl_take isl_set *set1,
1877                 __isl_take isl_set *set2);
1878         __isl_give isl_union_set *isl_union_set_product(
1879                 __isl_take isl_union_set *uset1,
1880                 __isl_take isl_union_set *uset2);
1881         __isl_give isl_basic_map *isl_basic_map_range_product(
1882                 __isl_take isl_basic_map *bmap1,
1883                 __isl_take isl_basic_map *bmap2);
1884         __isl_give isl_map *isl_map_range_product(
1885                 __isl_take isl_map *map1,
1886                 __isl_take isl_map *map2);
1887         __isl_give isl_union_map *isl_union_map_range_product(
1888                 __isl_take isl_union_map *umap1,
1889                 __isl_take isl_union_map *umap2);
1890         __isl_give isl_map *isl_map_product(
1891                 __isl_take isl_map *map1,
1892                 __isl_take isl_map *map2);
1893         __isl_give isl_union_map *isl_union_map_product(
1894                 __isl_take isl_union_map *umap1,
1895                 __isl_take isl_union_map *umap2);
1896
1897 The above functions compute the cross product of the given
1898 sets or relations.  The domains and ranges of the results
1899 are wrapped maps between domains and ranges of the inputs.
1900 To obtain a ``flat'' product, use the following functions
1901 instead.
1902
1903         __isl_give isl_basic_set *isl_basic_set_flat_product(
1904                 __isl_take isl_basic_set *bset1,
1905                 __isl_take isl_basic_set *bset2);
1906         __isl_give isl_set *isl_set_flat_product(
1907                 __isl_take isl_set *set1,
1908                 __isl_take isl_set *set2);
1909         __isl_give isl_basic_map *isl_basic_map_flat_range_product(
1910                 __isl_take isl_basic_map *bmap1,
1911                 __isl_take isl_basic_map *bmap2);
1912         __isl_give isl_map *isl_map_flat_range_product(
1913                 __isl_take isl_map *map1,
1914                 __isl_take isl_map *map2);
1915         __isl_give isl_union_map *isl_union_map_flat_range_product(
1916                 __isl_take isl_union_map *umap1,
1917                 __isl_take isl_union_map *umap2);
1918         __isl_give isl_basic_map *isl_basic_map_flat_product(
1919                 __isl_take isl_basic_map *bmap1,
1920                 __isl_take isl_basic_map *bmap2);
1921         __isl_give isl_map *isl_map_flat_product(
1922                 __isl_take isl_map *map1,
1923                 __isl_take isl_map *map2);
1924
1925 =item * Simplification
1926
1927         __isl_give isl_basic_set *isl_basic_set_gist(
1928                 __isl_take isl_basic_set *bset,
1929                 __isl_take isl_basic_set *context);
1930         __isl_give isl_set *isl_set_gist(__isl_take isl_set *set,
1931                 __isl_take isl_set *context);
1932         __isl_give isl_union_set *isl_union_set_gist(
1933                 __isl_take isl_union_set *uset,
1934                 __isl_take isl_union_set *context);
1935         __isl_give isl_basic_map *isl_basic_map_gist(
1936                 __isl_take isl_basic_map *bmap,
1937                 __isl_take isl_basic_map *context);
1938         __isl_give isl_map *isl_map_gist(__isl_take isl_map *map,
1939                 __isl_take isl_map *context);
1940         __isl_give isl_union_map *isl_union_map_gist(
1941                 __isl_take isl_union_map *umap,
1942                 __isl_take isl_union_map *context);
1943
1944 The gist operation returns a set or relation that has the
1945 same intersection with the context as the input set or relation.
1946 Any implicit equality in the intersection is made explicit in the result,
1947 while all inequalities that are redundant with respect to the intersection
1948 are removed.
1949 In case of union sets and relations, the gist operation is performed
1950 per space.
1951
1952 =back
1953
1954 =head3 Lexicographic Optimization
1955
1956 Given a (basic) set C<set> (or C<bset>) and a zero-dimensional domain C<dom>,
1957 the following functions
1958 compute a set that contains the lexicographic minimum or maximum
1959 of the elements in C<set> (or C<bset>) for those values of the parameters
1960 that satisfy C<dom>.
1961 If C<empty> is not C<NULL>, then C<*empty> is assigned a set
1962 that contains the parameter values in C<dom> for which C<set> (or C<bset>)
1963 has no elements.
1964 In other words, the union of the parameter values
1965 for which the result is non-empty and of C<*empty>
1966 is equal to C<dom>.
1967
1968         __isl_give isl_set *isl_basic_set_partial_lexmin(
1969                 __isl_take isl_basic_set *bset,
1970                 __isl_take isl_basic_set *dom,
1971                 __isl_give isl_set **empty);
1972         __isl_give isl_set *isl_basic_set_partial_lexmax(
1973                 __isl_take isl_basic_set *bset,
1974                 __isl_take isl_basic_set *dom,
1975                 __isl_give isl_set **empty);
1976         __isl_give isl_set *isl_set_partial_lexmin(
1977                 __isl_take isl_set *set, __isl_take isl_set *dom,
1978                 __isl_give isl_set **empty);
1979         __isl_give isl_set *isl_set_partial_lexmax(
1980                 __isl_take isl_set *set, __isl_take isl_set *dom,
1981                 __isl_give isl_set **empty);
1982
1983 Given a (basic) set C<set> (or C<bset>), the following functions simply
1984 return a set containing the lexicographic minimum or maximum
1985 of the elements in C<set> (or C<bset>).
1986 In case of union sets, the optimum is computed per space.
1987
1988         __isl_give isl_set *isl_basic_set_lexmin(
1989                 __isl_take isl_basic_set *bset);
1990         __isl_give isl_set *isl_basic_set_lexmax(
1991                 __isl_take isl_basic_set *bset);
1992         __isl_give isl_set *isl_set_lexmin(
1993                 __isl_take isl_set *set);
1994         __isl_give isl_set *isl_set_lexmax(
1995                 __isl_take isl_set *set);
1996         __isl_give isl_union_set *isl_union_set_lexmin(
1997                 __isl_take isl_union_set *uset);
1998         __isl_give isl_union_set *isl_union_set_lexmax(
1999                 __isl_take isl_union_set *uset);
2000
2001 Given a (basic) relation C<map> (or C<bmap>) and a domain C<dom>,
2002 the following functions
2003 compute a relation that maps each element of C<dom>
2004 to the single lexicographic minimum or maximum
2005 of the elements that are associated to that same
2006 element in C<map> (or C<bmap>).
2007 If C<empty> is not C<NULL>, then C<*empty> is assigned a set
2008 that contains the elements in C<dom> that do not map
2009 to any elements in C<map> (or C<bmap>).
2010 In other words, the union of the domain of the result and of C<*empty>
2011 is equal to C<dom>.
2012
2013         __isl_give isl_map *isl_basic_map_partial_lexmax(
2014                 __isl_take isl_basic_map *bmap,
2015                 __isl_take isl_basic_set *dom,
2016                 __isl_give isl_set **empty);
2017         __isl_give isl_map *isl_basic_map_partial_lexmin(
2018                 __isl_take isl_basic_map *bmap,
2019                 __isl_take isl_basic_set *dom,
2020                 __isl_give isl_set **empty);
2021         __isl_give isl_map *isl_map_partial_lexmax(
2022                 __isl_take isl_map *map, __isl_take isl_set *dom,
2023                 __isl_give isl_set **empty);
2024         __isl_give isl_map *isl_map_partial_lexmin(
2025                 __isl_take isl_map *map, __isl_take isl_set *dom,
2026                 __isl_give isl_set **empty);
2027
2028 Given a (basic) map C<map> (or C<bmap>), the following functions simply
2029 return a map mapping each element in the domain of
2030 C<map> (or C<bmap>) to the lexicographic minimum or maximum
2031 of all elements associated to that element.
2032 In case of union relations, the optimum is computed per space.
2033
2034         __isl_give isl_map *isl_basic_map_lexmin(
2035                 __isl_take isl_basic_map *bmap);
2036         __isl_give isl_map *isl_basic_map_lexmax(
2037                 __isl_take isl_basic_map *bmap);
2038         __isl_give isl_map *isl_map_lexmin(
2039                 __isl_take isl_map *map);
2040         __isl_give isl_map *isl_map_lexmax(
2041                 __isl_take isl_map *map);
2042         __isl_give isl_union_map *isl_union_map_lexmin(
2043                 __isl_take isl_union_map *umap);
2044         __isl_give isl_union_map *isl_union_map_lexmax(
2045                 __isl_take isl_union_map *umap);
2046
2047 =head2 Lists
2048
2049 Lists are defined over several element types, including
2050 C<isl_aff>, C<isl_basic_set> and C<isl_set>.
2051 Here we take lists of C<isl_set>s as an example.
2052 Lists can be created, copied and freed using the following functions.
2053
2054         #include <isl/list.h>
2055         __isl_give isl_set_list *isl_set_list_alloc(
2056                 isl_ctx *ctx, int n);
2057         __isl_give isl_set_list *isl_set_list_copy(
2058                 __isl_keep isl_set_list *list);
2059         __isl_give isl_set_list *isl_set_list_add(
2060                 __isl_take isl_set_list *list,
2061                 __isl_take isl_set *el);
2062         void isl_set_list_free(__isl_take isl_set_list *list);
2063
2064 C<isl_set_list_alloc> creates an empty list with a capacity for
2065 C<n> elements.
2066
2067 Lists can be inspected using the following functions.
2068
2069         #include <isl/list.h>
2070         isl_ctx *isl_set_list_get_ctx(__isl_keep isl_set_list *list);
2071         int isl_set_list_n_set(__isl_keep isl_set_list *list);
2072         __isl_give struct isl_set *isl_set_list_get_set(
2073                 __isl_keep isl_set_list *list, int index);
2074         int isl_set_list_foreach(__isl_keep isl_set_list *list,
2075                 int (*fn)(__isl_take struct isl_set *el, void *user),
2076                 void *user);
2077
2078 Lists can be printed using
2079
2080         #include <isl/list.h>
2081         __isl_give isl_printer *isl_printer_print_set_list(
2082                 __isl_take isl_printer *p,
2083                 __isl_keep isl_set_list *list);
2084
2085 =head2 Matrices
2086
2087 Matrices can be created, copied and freed using the following functions.
2088
2089         #include <isl/mat.h>
2090         __isl_give isl_mat *isl_mat_alloc(struct isl_ctx *ctx,
2091                 unsigned n_row, unsigned n_col);
2092         __isl_give isl_mat *isl_mat_copy(__isl_keep isl_mat *mat);
2093         void isl_mat_free(__isl_take isl_mat *mat);
2094
2095 Note that the elements of a newly created matrix may have arbitrary values.
2096 The elements can be changed and inspected using the following functions.
2097
2098         isl_ctx *isl_mat_get_ctx(__isl_keep isl_mat *mat);
2099         int isl_mat_rows(__isl_keep isl_mat *mat);
2100         int isl_mat_cols(__isl_keep isl_mat *mat);
2101         int isl_mat_get_element(__isl_keep isl_mat *mat,
2102                 int row, int col, isl_int *v);
2103         __isl_give isl_mat *isl_mat_set_element(__isl_take isl_mat *mat,
2104                 int row, int col, isl_int v);
2105         __isl_give isl_mat *isl_mat_set_element_si(__isl_take isl_mat *mat,
2106                 int row, int col, int v);
2107
2108 C<isl_mat_get_element> will return a negative value if anything went wrong.
2109 In that case, the value of C<*v> is undefined.
2110
2111 The following function can be used to compute the (right) inverse
2112 of a matrix, i.e., a matrix such that the product of the original
2113 and the inverse (in that order) is a multiple of the identity matrix.
2114 The input matrix is assumed to be of full row-rank.
2115
2116         __isl_give isl_mat *isl_mat_right_inverse(__isl_take isl_mat *mat);
2117
2118 The following function can be used to compute the (right) kernel
2119 (or null space) of a matrix, i.e., a matrix such that the product of
2120 the original and the kernel (in that order) is the zero matrix.
2121
2122         __isl_give isl_mat *isl_mat_right_kernel(__isl_take isl_mat *mat);
2123
2124 =head2 Quasi Affine Expressions
2125
2126 The zero quasi affine expression can be created using
2127
2128         __isl_give isl_aff *isl_aff_zero(
2129                 __isl_take isl_local_space *ls);
2130
2131 Quasi affine expressions can be copied and free using
2132
2133         #include <isl/aff.h>
2134         __isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff);
2135         void *isl_aff_free(__isl_take isl_aff *aff);
2136
2137 A (rational) bound on a dimension can be extracted from an C<isl_constraint>
2138 using the following function.  The constraint is required to have
2139 a non-zero coefficient for the specified dimension.
2140
2141         #include <isl/constraint.h>
2142         __isl_give isl_aff *isl_constraint_get_bound(
2143                 __isl_keep isl_constraint *constraint,
2144                 enum isl_dim_type type, int pos);
2145
2146 Conversely, an equality constraint equating
2147 the affine expression to zero or an inequality constraint enforcing
2148 the affine expression to be non-negative, can be constructed using
2149
2150         __isl_give isl_constraint *isl_equality_from_aff(
2151                 __isl_take isl_aff *aff);
2152         __isl_give isl_constraint *isl_inequality_from_aff(
2153                 __isl_take isl_aff *aff);
2154
2155 The expression can be inspected using
2156
2157         #include <isl/aff.h>
2158         isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff);
2159         int isl_aff_dim(__isl_keep isl_aff *aff,
2160                 enum isl_dim_type type);
2161         __isl_give isl_local_space *isl_aff_get_local_space(
2162                 __isl_keep isl_aff *aff);
2163         const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff,
2164                 enum isl_dim_type type, unsigned pos);
2165         int isl_aff_get_constant(__isl_keep isl_aff *aff,
2166                 isl_int *v);
2167         int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
2168                 enum isl_dim_type type, int pos, isl_int *v);
2169         int isl_aff_get_denominator(__isl_keep isl_aff *aff,
2170                 isl_int *v);
2171         __isl_give isl_div *isl_aff_get_div(
2172                 __isl_keep isl_aff *aff, int pos);
2173
2174 It can be modified using
2175
2176         #include <isl/aff.h>
2177         __isl_give isl_aff *isl_aff_set_constant(
2178                 __isl_take isl_aff *aff, isl_int v);
2179         __isl_give isl_aff *isl_aff_set_constant_si(
2180                 __isl_take isl_aff *aff, int v);
2181         __isl_give isl_aff *isl_aff_set_coefficient(
2182                 __isl_take isl_aff *aff,
2183                 enum isl_dim_type type, int pos, isl_int v);
2184         __isl_give isl_aff *isl_aff_set_coefficient_si(
2185                 __isl_take isl_aff *aff,
2186                 enum isl_dim_type type, int pos, int v);
2187         __isl_give isl_aff *isl_aff_set_denominator(
2188                 __isl_take isl_aff *aff, isl_int v);
2189
2190         __isl_give isl_aff *isl_aff_add_constant(
2191                 __isl_take isl_aff *aff, isl_int v);
2192         __isl_give isl_aff *isl_aff_add_coefficient_si(
2193                 __isl_take isl_aff *aff,
2194                 enum isl_dim_type type, int pos, int v);
2195
2196 Note that the C<set_constant> and C<set_coefficient> functions
2197 set the I<numerator> of the constant or coefficient, while
2198 C<add_constant> and C<add_coefficient> add an integer value to
2199 the possibly rational constant or coefficient.
2200
2201 Operations include
2202
2203         #include <isl/aff.h>
2204         __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
2205                 __isl_take isl_aff *aff2);
2206         __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
2207                 __isl_take isl_aff *aff2);
2208         __isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff);
2209         __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff);
2210         __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff,
2211                 isl_int f);
2212         __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff,
2213                 isl_int f);
2214
2215 An expression can be printed using
2216
2217         #include <isl/aff.h>
2218         __isl_give isl_printer *isl_printer_print_aff(
2219                 __isl_take isl_printer *p, __isl_keep isl_aff *aff);
2220
2221 =head2 Points
2222
2223 Points are elements of a set.  They can be used to construct
2224 simple sets (boxes) or they can be used to represent the
2225 individual elements of a set.
2226 The zero point (the origin) can be created using
2227
2228         __isl_give isl_point *isl_point_zero(__isl_take isl_dim *dim);
2229
2230 The coordinates of a point can be inspected, set and changed
2231 using
2232
2233         void isl_point_get_coordinate(__isl_keep isl_point *pnt,
2234                 enum isl_dim_type type, int pos, isl_int *v);
2235         __isl_give isl_point *isl_point_set_coordinate(
2236                 __isl_take isl_point *pnt,
2237                 enum isl_dim_type type, int pos, isl_int v);
2238
2239         __isl_give isl_point *isl_point_add_ui(
2240                 __isl_take isl_point *pnt,
2241                 enum isl_dim_type type, int pos, unsigned val);
2242         __isl_give isl_point *isl_point_sub_ui(
2243                 __isl_take isl_point *pnt,
2244                 enum isl_dim_type type, int pos, unsigned val);
2245
2246 Points can be copied or freed using
2247
2248         __isl_give isl_point *isl_point_copy(
2249                 __isl_keep isl_point *pnt);
2250         void isl_point_free(__isl_take isl_point *pnt);
2251
2252 A singleton set can be created from a point using
2253
2254         __isl_give isl_basic_set *isl_basic_set_from_point(
2255                 __isl_take isl_point *pnt);
2256         __isl_give isl_set *isl_set_from_point(
2257                 __isl_take isl_point *pnt);
2258
2259 and a box can be created from two opposite extremal points using
2260
2261         __isl_give isl_basic_set *isl_basic_set_box_from_points(
2262                 __isl_take isl_point *pnt1,
2263                 __isl_take isl_point *pnt2);
2264         __isl_give isl_set *isl_set_box_from_points(
2265                 __isl_take isl_point *pnt1,
2266                 __isl_take isl_point *pnt2);
2267
2268 All elements of a B<bounded> (union) set can be enumerated using
2269 the following functions.
2270
2271         int isl_set_foreach_point(__isl_keep isl_set *set,
2272                 int (*fn)(__isl_take isl_point *pnt, void *user),
2273                 void *user);
2274         int isl_union_set_foreach_point(__isl_keep isl_union_set *uset,
2275                 int (*fn)(__isl_take isl_point *pnt, void *user),
2276                 void *user);
2277
2278 The function C<fn> is called for each integer point in
2279 C<set> with as second argument the last argument of
2280 the C<isl_set_foreach_point> call.  The function C<fn>
2281 should return C<0> on success and C<-1> on failure.
2282 In the latter case, C<isl_set_foreach_point> will stop
2283 enumerating and return C<-1> as well.
2284 If the enumeration is performed successfully and to completion,
2285 then C<isl_set_foreach_point> returns C<0>.
2286
2287 To obtain a single point of a (basic) set, use
2288
2289         __isl_give isl_point *isl_basic_set_sample_point(
2290                 __isl_take isl_basic_set *bset);
2291         __isl_give isl_point *isl_set_sample_point(
2292                 __isl_take isl_set *set);
2293
2294 If C<set> does not contain any (integer) points, then the
2295 resulting point will be ``void'', a property that can be
2296 tested using
2297
2298         int isl_point_is_void(__isl_keep isl_point *pnt);
2299
2300 =head2 Piecewise Quasipolynomials
2301
2302 A piecewise quasipolynomial is a particular kind of function that maps
2303 a parametric point to a rational value.
2304 More specifically, a quasipolynomial is a polynomial expression in greatest
2305 integer parts of affine expressions of parameters and variables.
2306 A piecewise quasipolynomial is a subdivision of a given parametric
2307 domain into disjoint cells with a quasipolynomial associated to
2308 each cell.  The value of the piecewise quasipolynomial at a given
2309 point is the value of the quasipolynomial associated to the cell
2310 that contains the point.  Outside of the union of cells,
2311 the value is assumed to be zero.
2312 For example, the piecewise quasipolynomial
2313
2314         [n] -> { [x] -> ((1 + n) - x) : x <= n and x >= 0 }
2315
2316 maps C<x> to C<1 + n - x> for values of C<x> between C<0> and C<n>.
2317 A given piecewise quasipolynomial has a fixed domain dimension.
2318 Union piecewise quasipolynomials are used to contain piecewise quasipolynomials
2319 defined over different domains.
2320 Piecewise quasipolynomials are mainly used by the C<barvinok>
2321 library for representing the number of elements in a parametric set or map.
2322 For example, the piecewise quasipolynomial above represents
2323 the number of points in the map
2324
2325         [n] -> { [x] -> [y] : x,y >= 0 and 0 <= x + y <= n }
2326
2327 =head3 Printing (Piecewise) Quasipolynomials
2328
2329 Quasipolynomials and piecewise quasipolynomials can be printed
2330 using the following functions.
2331
2332         __isl_give isl_printer *isl_printer_print_qpolynomial(
2333                 __isl_take isl_printer *p,
2334                 __isl_keep isl_qpolynomial *qp);
2335
2336         __isl_give isl_printer *isl_printer_print_pw_qpolynomial(
2337                 __isl_take isl_printer *p,
2338                 __isl_keep isl_pw_qpolynomial *pwqp);
2339
2340         __isl_give isl_printer *isl_printer_print_union_pw_qpolynomial(
2341                 __isl_take isl_printer *p,
2342                 __isl_keep isl_union_pw_qpolynomial *upwqp);
2343
2344 The output format of the printer
2345 needs to be set to either C<ISL_FORMAT_ISL> or C<ISL_FORMAT_C>.
2346 For C<isl_printer_print_union_pw_qpolynomial>, only C<ISL_FORMAT_ISL>
2347 is supported.
2348 In case of printing in C<ISL_FORMAT_C>, the user may want
2349 to set the names of all dimensions
2350
2351         __isl_give isl_qpolynomial *isl_qpolynomial_set_dim_name(
2352                 __isl_take isl_qpolynomial *qp,
2353                 enum isl_dim_type type, unsigned pos,
2354                 const char *s);
2355         __isl_give isl_pw_qpolynomial *
2356         isl_pw_qpolynomial_set_dim_name(
2357                 __isl_take isl_pw_qpolynomial *pwqp,
2358                 enum isl_dim_type type, unsigned pos,
2359                 const char *s);
2360
2361 =head3 Creating New (Piecewise) Quasipolynomials
2362
2363 Some simple quasipolynomials can be created using the following functions.
2364 More complicated quasipolynomials can be created by applying
2365 operations such as addition and multiplication
2366 on the resulting quasipolynomials
2367
2368         __isl_give isl_qpolynomial *isl_qpolynomial_zero(
2369                 __isl_take isl_dim *dim);
2370         __isl_give isl_qpolynomial *isl_qpolynomial_one(
2371                 __isl_take isl_dim *dim);
2372         __isl_give isl_qpolynomial *isl_qpolynomial_infty(
2373                 __isl_take isl_dim *dim);
2374         __isl_give isl_qpolynomial *isl_qpolynomial_neginfty(
2375                 __isl_take isl_dim *dim);
2376         __isl_give isl_qpolynomial *isl_qpolynomial_nan(
2377                 __isl_take isl_dim *dim);
2378         __isl_give isl_qpolynomial *isl_qpolynomial_rat_cst(
2379                 __isl_take isl_dim *dim,
2380                 const isl_int n, const isl_int d);
2381         __isl_give isl_qpolynomial *isl_qpolynomial_div(
2382                 __isl_take isl_div *div);
2383         __isl_give isl_qpolynomial *isl_qpolynomial_var(
2384                 __isl_take isl_dim *dim,
2385                 enum isl_dim_type type, unsigned pos);
2386         __isl_give isl_qpolynomial *isl_qpolynomial_from_aff(
2387                 __isl_take isl_aff *aff);
2388
2389 The zero piecewise quasipolynomial or a piecewise quasipolynomial
2390 with a single cell can be created using the following functions.
2391 Multiple of these single cell piecewise quasipolynomials can
2392 be combined to create more complicated piecewise quasipolynomials.
2393
2394         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_zero(
2395                 __isl_take isl_dim *dim);
2396         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_alloc(
2397                 __isl_take isl_set *set,
2398                 __isl_take isl_qpolynomial *qp);
2399
2400         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_zero(
2401                 __isl_take isl_dim *dim);
2402         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_from_pw_qpolynomial(
2403                 __isl_take isl_pw_qpolynomial *pwqp);
2404         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_add_pw_qpolynomial(
2405                 __isl_take isl_union_pw_qpolynomial *upwqp,
2406                 __isl_take isl_pw_qpolynomial *pwqp);
2407
2408 Quasipolynomials can be copied and freed again using the following
2409 functions.
2410
2411         __isl_give isl_qpolynomial *isl_qpolynomial_copy(
2412                 __isl_keep isl_qpolynomial *qp);
2413         void isl_qpolynomial_free(__isl_take isl_qpolynomial *qp);
2414
2415         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_copy(
2416                 __isl_keep isl_pw_qpolynomial *pwqp);
2417         void isl_pw_qpolynomial_free(
2418                 __isl_take isl_pw_qpolynomial *pwqp);
2419
2420         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_copy(
2421                 __isl_keep isl_union_pw_qpolynomial *upwqp);
2422         void isl_union_pw_qpolynomial_free(
2423                 __isl_take isl_union_pw_qpolynomial *upwqp);
2424
2425 =head3 Inspecting (Piecewise) Quasipolynomials
2426
2427 To iterate over all piecewise quasipolynomials in a union
2428 piecewise quasipolynomial, use the following function
2429
2430         int isl_union_pw_qpolynomial_foreach_pw_qpolynomial(
2431                 __isl_keep isl_union_pw_qpolynomial *upwqp,
2432                 int (*fn)(__isl_take isl_pw_qpolynomial *pwqp, void *user),
2433                 void *user);
2434
2435 To extract the piecewise quasipolynomial from a union with a given dimension
2436 specification, use
2437
2438         __isl_give isl_pw_qpolynomial *
2439         isl_union_pw_qpolynomial_extract_pw_qpolynomial(
2440                 __isl_keep isl_union_pw_qpolynomial *upwqp,
2441                 __isl_take isl_dim *dim);
2442
2443 To iterate over the cells in a piecewise quasipolynomial,
2444 use either of the following two functions
2445
2446         int isl_pw_qpolynomial_foreach_piece(
2447                 __isl_keep isl_pw_qpolynomial *pwqp,
2448                 int (*fn)(__isl_take isl_set *set,
2449                           __isl_take isl_qpolynomial *qp,
2450                           void *user), void *user);
2451         int isl_pw_qpolynomial_foreach_lifted_piece(
2452                 __isl_keep isl_pw_qpolynomial *pwqp,
2453                 int (*fn)(__isl_take isl_set *set,
2454                           __isl_take isl_qpolynomial *qp,
2455                           void *user), void *user);
2456
2457 As usual, the function C<fn> should return C<0> on success
2458 and C<-1> on failure.  The difference between
2459 C<isl_pw_qpolynomial_foreach_piece> and
2460 C<isl_pw_qpolynomial_foreach_lifted_piece> is that
2461 C<isl_pw_qpolynomial_foreach_lifted_piece> will first
2462 compute unique representations for all existentially quantified
2463 variables and then turn these existentially quantified variables
2464 into extra set variables, adapting the associated quasipolynomial
2465 accordingly.  This means that the C<set> passed to C<fn>
2466 will not have any existentially quantified variables, but that
2467 the dimensions of the sets may be different for different
2468 invocations of C<fn>.
2469
2470 To iterate over all terms in a quasipolynomial,
2471 use
2472
2473         int isl_qpolynomial_foreach_term(
2474                 __isl_keep isl_qpolynomial *qp,
2475                 int (*fn)(__isl_take isl_term *term,
2476                           void *user), void *user);
2477
2478 The terms themselves can be inspected and freed using
2479 these functions
2480
2481         unsigned isl_term_dim(__isl_keep isl_term *term,
2482                 enum isl_dim_type type);
2483         void isl_term_get_num(__isl_keep isl_term *term,
2484                 isl_int *n);
2485         void isl_term_get_den(__isl_keep isl_term *term,
2486                 isl_int *d);
2487         int isl_term_get_exp(__isl_keep isl_term *term,
2488                 enum isl_dim_type type, unsigned pos);
2489         __isl_give isl_div *isl_term_get_div(
2490                 __isl_keep isl_term *term, unsigned pos);
2491         void isl_term_free(__isl_take isl_term *term);
2492
2493 Each term is a product of parameters, set variables and
2494 integer divisions.  The function C<isl_term_get_exp>
2495 returns the exponent of a given dimensions in the given term.
2496 The C<isl_int>s in the arguments of C<isl_term_get_num>
2497 and C<isl_term_get_den> need to have been initialized
2498 using C<isl_int_init> before calling these functions.
2499
2500 =head3 Properties of (Piecewise) Quasipolynomials
2501
2502 To check whether a quasipolynomial is actually a constant,
2503 use the following function.
2504
2505         int isl_qpolynomial_is_cst(__isl_keep isl_qpolynomial *qp,
2506                 isl_int *n, isl_int *d);
2507
2508 If C<qp> is a constant and if C<n> and C<d> are not C<NULL>
2509 then the numerator and denominator of the constant
2510 are returned in C<*n> and C<*d>, respectively.
2511
2512 =head3 Operations on (Piecewise) Quasipolynomials
2513
2514         __isl_give isl_qpolynomial *isl_qpolynomial_neg(
2515                 __isl_take isl_qpolynomial *qp);
2516         __isl_give isl_qpolynomial *isl_qpolynomial_add(
2517                 __isl_take isl_qpolynomial *qp1,
2518                 __isl_take isl_qpolynomial *qp2);
2519         __isl_give isl_qpolynomial *isl_qpolynomial_sub(
2520                 __isl_take isl_qpolynomial *qp1,
2521                 __isl_take isl_qpolynomial *qp2);
2522         __isl_give isl_qpolynomial *isl_qpolynomial_mul(
2523                 __isl_take isl_qpolynomial *qp1,
2524                 __isl_take isl_qpolynomial *qp2);
2525         __isl_give isl_qpolynomial *isl_qpolynomial_pow(
2526                 __isl_take isl_qpolynomial *qp, unsigned exponent);
2527
2528         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_add(
2529                 __isl_take isl_pw_qpolynomial *pwqp1,
2530                 __isl_take isl_pw_qpolynomial *pwqp2);
2531         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_sub(
2532                 __isl_take isl_pw_qpolynomial *pwqp1,
2533                 __isl_take isl_pw_qpolynomial *pwqp2);
2534         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_add_disjoint(
2535                 __isl_take isl_pw_qpolynomial *pwqp1,
2536                 __isl_take isl_pw_qpolynomial *pwqp2);
2537         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_neg(
2538                 __isl_take isl_pw_qpolynomial *pwqp);
2539         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_mul(
2540                 __isl_take isl_pw_qpolynomial *pwqp1,
2541                 __isl_take isl_pw_qpolynomial *pwqp2);
2542
2543         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_add(
2544                 __isl_take isl_union_pw_qpolynomial *upwqp1,
2545                 __isl_take isl_union_pw_qpolynomial *upwqp2);
2546         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_sub(
2547                 __isl_take isl_union_pw_qpolynomial *upwqp1,
2548                 __isl_take isl_union_pw_qpolynomial *upwqp2);
2549         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_mul(
2550                 __isl_take isl_union_pw_qpolynomial *upwqp1,
2551                 __isl_take isl_union_pw_qpolynomial *upwqp2);
2552
2553         __isl_give isl_qpolynomial *isl_pw_qpolynomial_eval(
2554                 __isl_take isl_pw_qpolynomial *pwqp,
2555                 __isl_take isl_point *pnt);
2556
2557         __isl_give isl_qpolynomial *isl_union_pw_qpolynomial_eval(
2558                 __isl_take isl_union_pw_qpolynomial *upwqp,
2559                 __isl_take isl_point *pnt);
2560
2561         __isl_give isl_set *isl_pw_qpolynomial_domain(
2562                 __isl_take isl_pw_qpolynomial *pwqp);
2563         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_intersect_domain(
2564                 __isl_take isl_pw_qpolynomial *pwpq,
2565                 __isl_take isl_set *set);
2566
2567         __isl_give isl_union_set *isl_union_pw_qpolynomial_domain(
2568                 __isl_take isl_union_pw_qpolynomial *upwqp);
2569         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_intersect_domain(
2570                 __isl_take isl_union_pw_qpolynomial *upwpq,
2571                 __isl_take isl_union_set *uset);
2572
2573         __isl_give isl_qpolynomial *isl_qpolynomial_align_params(
2574                 __isl_take isl_qpolynomial *qp,
2575                 __isl_take isl_dim *model);
2576
2577         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_coalesce(
2578                 __isl_take isl_union_pw_qpolynomial *upwqp);
2579
2580         __isl_give isl_qpolynomial *isl_qpolynomial_gist(
2581                 __isl_take isl_qpolynomial *qp,
2582                 __isl_take isl_set *context);
2583
2584         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_gist(
2585                 __isl_take isl_pw_qpolynomial *pwqp,
2586                 __isl_take isl_set *context);
2587
2588         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_gist(
2589                 __isl_take isl_union_pw_qpolynomial *upwqp,
2590                 __isl_take isl_union_set *context);
2591
2592 The gist operation applies the gist operation to each of
2593 the cells in the domain of the input piecewise quasipolynomial.
2594 The context is also exploited
2595 to simplify the quasipolynomials associated to each cell.
2596
2597         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_to_polynomial(
2598                 __isl_take isl_pw_qpolynomial *pwqp, int sign);
2599         __isl_give isl_union_pw_qpolynomial *
2600         isl_union_pw_qpolynomial_to_polynomial(
2601                 __isl_take isl_union_pw_qpolynomial *upwqp, int sign);
2602
2603 Approximate each quasipolynomial by a polynomial.  If C<sign> is positive,
2604 the polynomial will be an overapproximation.  If C<sign> is negative,
2605 it will be an underapproximation.  If C<sign> is zero, the approximation
2606 will lie somewhere in between.
2607
2608 =head2 Bounds on Piecewise Quasipolynomials and Piecewise Quasipolynomial Reductions
2609
2610 A piecewise quasipolynomial reduction is a piecewise
2611 reduction (or fold) of quasipolynomials.
2612 In particular, the reduction can be maximum or a minimum.
2613 The objects are mainly used to represent the result of
2614 an upper or lower bound on a quasipolynomial over its domain,
2615 i.e., as the result of the following function.
2616
2617         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
2618                 __isl_take isl_pw_qpolynomial *pwqp,
2619                 enum isl_fold type, int *tight);
2620
2621         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound(
2622                 __isl_take isl_union_pw_qpolynomial *upwqp,
2623                 enum isl_fold type, int *tight);
2624
2625 The C<type> argument may be either C<isl_fold_min> or C<isl_fold_max>.
2626 If C<tight> is not C<NULL>, then C<*tight> is set to C<1>
2627 is the returned bound is known be tight, i.e., for each value
2628 of the parameters there is at least
2629 one element in the domain that reaches the bound.
2630 If the domain of C<pwqp> is not wrapping, then the bound is computed
2631 over all elements in that domain and the result has a purely parametric
2632 domain.  If the domain of C<pwqp> is wrapping, then the bound is
2633 computed over the range of the wrapped relation.  The domain of the
2634 wrapped relation becomes the domain of the result.
2635
2636 A (piecewise) quasipolynomial reduction can be copied or freed using the
2637 following functions.
2638
2639         __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy(
2640                 __isl_keep isl_qpolynomial_fold *fold);
2641         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_copy(
2642                 __isl_keep isl_pw_qpolynomial_fold *pwf);
2643         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_copy(
2644                 __isl_keep isl_union_pw_qpolynomial_fold *upwf);
2645         void isl_qpolynomial_fold_free(
2646                 __isl_take isl_qpolynomial_fold *fold);
2647         void isl_pw_qpolynomial_fold_free(
2648                 __isl_take isl_pw_qpolynomial_fold *pwf);
2649         void isl_union_pw_qpolynomial_fold_free(
2650                 __isl_take isl_union_pw_qpolynomial_fold *upwf);
2651
2652 =head3 Printing Piecewise Quasipolynomial Reductions
2653
2654 Piecewise quasipolynomial reductions can be printed
2655 using the following function.
2656
2657         __isl_give isl_printer *isl_printer_print_pw_qpolynomial_fold(
2658                 __isl_take isl_printer *p,
2659                 __isl_keep isl_pw_qpolynomial_fold *pwf);
2660         __isl_give isl_printer *isl_printer_print_union_pw_qpolynomial_fold(
2661                 __isl_take isl_printer *p,
2662                 __isl_keep isl_union_pw_qpolynomial_fold *upwf);
2663
2664 For C<isl_printer_print_pw_qpolynomial_fold>,
2665 output format of the printer
2666 needs to be set to either C<ISL_FORMAT_ISL> or C<ISL_FORMAT_C>.
2667 For C<isl_printer_print_union_pw_qpolynomial_fold>,
2668 output format of the printer
2669 needs to be set to C<ISL_FORMAT_ISL>.
2670 In case of printing in C<ISL_FORMAT_C>, the user may want
2671 to set the names of all dimensions
2672
2673         __isl_give isl_pw_qpolynomial_fold *
2674         isl_pw_qpolynomial_fold_set_dim_name(
2675                 __isl_take isl_pw_qpolynomial_fold *pwf,
2676                 enum isl_dim_type type, unsigned pos,
2677                 const char *s);
2678
2679 =head3 Inspecting (Piecewise) Quasipolynomial Reductions
2680
2681 To iterate over all piecewise quasipolynomial reductions in a union
2682 piecewise quasipolynomial reduction, use the following function
2683
2684         int isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
2685                 __isl_keep isl_union_pw_qpolynomial_fold *upwf,
2686                 int (*fn)(__isl_take isl_pw_qpolynomial_fold *pwf,
2687                             void *user), void *user);
2688
2689 To iterate over the cells in a piecewise quasipolynomial reduction,
2690 use either of the following two functions
2691
2692         int isl_pw_qpolynomial_fold_foreach_piece(
2693                 __isl_keep isl_pw_qpolynomial_fold *pwf,
2694                 int (*fn)(__isl_take isl_set *set,
2695                           __isl_take isl_qpolynomial_fold *fold,
2696                           void *user), void *user);
2697         int isl_pw_qpolynomial_fold_foreach_lifted_piece(
2698                 __isl_keep isl_pw_qpolynomial_fold *pwf,
2699                 int (*fn)(__isl_take isl_set *set,
2700                           __isl_take isl_qpolynomial_fold *fold,
2701                           void *user), void *user);
2702
2703 See L<Inspecting (Piecewise) Quasipolynomials> for an explanation
2704 of the difference between these two functions.
2705
2706 To iterate over all quasipolynomials in a reduction, use
2707
2708         int isl_qpolynomial_fold_foreach_qpolynomial(
2709                 __isl_keep isl_qpolynomial_fold *fold,
2710                 int (*fn)(__isl_take isl_qpolynomial *qp,
2711                           void *user), void *user);
2712
2713 =head3 Operations on Piecewise Quasipolynomial Reductions
2714
2715         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_add(
2716                 __isl_take isl_pw_qpolynomial_fold *pwf1,
2717                 __isl_take isl_pw_qpolynomial_fold *pwf2);
2718
2719         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_fold(
2720                 __isl_take isl_pw_qpolynomial_fold *pwf1,
2721                 __isl_take isl_pw_qpolynomial_fold *pwf2);
2722
2723         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold(
2724                 __isl_take isl_union_pw_qpolynomial_fold *upwf1,
2725                 __isl_take isl_union_pw_qpolynomial_fold *upwf2);
2726
2727         __isl_give isl_qpolynomial *isl_pw_qpolynomial_fold_eval(
2728                 __isl_take isl_pw_qpolynomial_fold *pwf,
2729                 __isl_take isl_point *pnt);
2730
2731         __isl_give isl_qpolynomial *isl_union_pw_qpolynomial_fold_eval(
2732                 __isl_take isl_union_pw_qpolynomial_fold *upwf,
2733                 __isl_take isl_point *pnt);
2734
2735         __isl_give isl_union_set *isl_union_pw_qpolynomial_fold_domain(
2736                 __isl_take isl_union_pw_qpolynomial_fold *upwf);
2737         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_intersect_domain(
2738                 __isl_take isl_union_pw_qpolynomial_fold *upwf,
2739                 __isl_take isl_union_set *uset);
2740
2741         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_coalesce(
2742                 __isl_take isl_pw_qpolynomial_fold *pwf);
2743
2744         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_coalesce(
2745                 __isl_take isl_union_pw_qpolynomial_fold *upwf);
2746
2747         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_gist(
2748                 __isl_take isl_pw_qpolynomial_fold *pwf,
2749                 __isl_take isl_set *context);
2750
2751         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_gist(
2752                 __isl_take isl_union_pw_qpolynomial_fold *upwf,
2753                 __isl_take isl_union_set *context);
2754
2755 The gist operation applies the gist operation to each of
2756 the cells in the domain of the input piecewise quasipolynomial reduction.
2757 In future, the operation will also exploit the context
2758 to simplify the quasipolynomial reductions associated to each cell.
2759
2760         __isl_give isl_pw_qpolynomial_fold *
2761         isl_set_apply_pw_qpolynomial_fold(
2762                 __isl_take isl_set *set,
2763                 __isl_take isl_pw_qpolynomial_fold *pwf,
2764                 int *tight);
2765         __isl_give isl_pw_qpolynomial_fold *
2766         isl_map_apply_pw_qpolynomial_fold(
2767                 __isl_take isl_map *map,
2768                 __isl_take isl_pw_qpolynomial_fold *pwf,
2769                 int *tight);
2770         __isl_give isl_union_pw_qpolynomial_fold *
2771         isl_union_set_apply_union_pw_qpolynomial_fold(
2772                 __isl_take isl_union_set *uset,
2773                 __isl_take isl_union_pw_qpolynomial_fold *upwf,
2774                 int *tight);
2775         __isl_give isl_union_pw_qpolynomial_fold *
2776         isl_union_map_apply_union_pw_qpolynomial_fold(
2777                 __isl_take isl_union_map *umap,
2778                 __isl_take isl_union_pw_qpolynomial_fold *upwf,
2779                 int *tight);
2780
2781 The functions taking a map
2782 compose the given map with the given piecewise quasipolynomial reduction.
2783 That is, compute a bound (of the same type as C<pwf> or C<upwf> itself)
2784 over all elements in the intersection of the range of the map
2785 and the domain of the piecewise quasipolynomial reduction
2786 as a function of an element in the domain of the map.
2787 The functions taking a set compute a bound over all elements in the
2788 intersection of the set and the domain of the
2789 piecewise quasipolynomial reduction.
2790
2791 =head2 Dependence Analysis
2792
2793 C<isl> contains specialized functionality for performing
2794 array dataflow analysis.  That is, given a I<sink> access relation
2795 and a collection of possible I<source> access relations,
2796 C<isl> can compute relations that describe
2797 for each iteration of the sink access, which iteration
2798 of which of the source access relations was the last
2799 to access the same data element before the given iteration
2800 of the sink access.
2801 To compute standard flow dependences, the sink should be
2802 a read, while the sources should be writes.
2803 If any of the source accesses are marked as being I<may>
2804 accesses, then there will be a dependence to the last
2805 I<must> access B<and> to any I<may> access that follows
2806 this last I<must> access.
2807 In particular, if I<all> sources are I<may> accesses,
2808 then memory based dependence analysis is performed.
2809 If, on the other hand, all sources are I<must> accesses,
2810 then value based dependence analysis is performed.
2811
2812         #include <isl/flow.h>
2813
2814         typedef int (*isl_access_level_before)(void *first, void *second);
2815
2816         __isl_give isl_access_info *isl_access_info_alloc(
2817                 __isl_take isl_map *sink,
2818                 void *sink_user, isl_access_level_before fn,
2819                 int max_source);
2820         __isl_give isl_access_info *isl_access_info_add_source(
2821                 __isl_take isl_access_info *acc,
2822                 __isl_take isl_map *source, int must,
2823                 void *source_user);
2824         void isl_access_info_free(__isl_take isl_access_info *acc);
2825
2826         __isl_give isl_flow *isl_access_info_compute_flow(
2827                 __isl_take isl_access_info *acc);
2828
2829         int isl_flow_foreach(__isl_keep isl_flow *deps,
2830                 int (*fn)(__isl_take isl_map *dep, int must,
2831                           void *dep_user, void *user),
2832                 void *user);
2833         __isl_give isl_map *isl_flow_get_no_source(
2834                 __isl_keep isl_flow *deps, int must);
2835         void isl_flow_free(__isl_take isl_flow *deps);
2836
2837 The function C<isl_access_info_compute_flow> performs the actual
2838 dependence analysis.  The other functions are used to construct
2839 the input for this function or to read off the output.
2840
2841 The input is collected in an C<isl_access_info>, which can
2842 be created through a call to C<isl_access_info_alloc>.
2843 The arguments to this functions are the sink access relation
2844 C<sink>, a token C<sink_user> used to identify the sink
2845 access to the user, a callback function for specifying the
2846 relative order of source and sink accesses, and the number
2847 of source access relations that will be added.
2848 The callback function has type C<int (*)(void *first, void *second)>.
2849 The function is called with two user supplied tokens identifying
2850 either a source or the sink and it should return the shared nesting
2851 level and the relative order of the two accesses.
2852 In particular, let I<n> be the number of loops shared by
2853 the two accesses.  If C<first> precedes C<second> textually,
2854 then the function should return I<2 * n + 1>; otherwise,
2855 it should return I<2 * n>.
2856 The sources can be added to the C<isl_access_info> by performing
2857 (at most) C<max_source> calls to C<isl_access_info_add_source>.
2858 C<must> indicates whether the source is a I<must> access
2859 or a I<may> access.  Note that a multi-valued access relation
2860 should only be marked I<must> if every iteration in the domain
2861 of the relation accesses I<all> elements in its image.
2862 The C<source_user> token is again used to identify
2863 the source access.  The range of the source access relation
2864 C<source> should have the same dimension as the range
2865 of the sink access relation.
2866 The C<isl_access_info_free> function should usually not be
2867 called explicitly, because it is called implicitly by
2868 C<isl_access_info_compute_flow>.
2869
2870 The result of the dependence analysis is collected in an
2871 C<isl_flow>.  There may be elements of
2872 the sink access for which no preceding source access could be
2873 found or for which all preceding sources are I<may> accesses.
2874 The relations containing these elements can be obtained through
2875 calls to C<isl_flow_get_no_source>, the first with C<must> set
2876 and the second with C<must> unset.
2877 In the case of standard flow dependence analysis,
2878 with the sink a read and the sources I<must> writes,
2879 the first relation corresponds to the reads from uninitialized
2880 array elements and the second relation is empty.
2881 The actual flow dependences can be extracted using
2882 C<isl_flow_foreach>.  This function will call the user-specified
2883 callback function C<fn> for each B<non-empty> dependence between
2884 a source and the sink.  The callback function is called
2885 with four arguments, the actual flow dependence relation
2886 mapping source iterations to sink iterations, a boolean that
2887 indicates whether it is a I<must> or I<may> dependence, a token
2888 identifying the source and an additional C<void *> with value
2889 equal to the third argument of the C<isl_flow_foreach> call.
2890 A dependence is marked I<must> if it originates from a I<must>
2891 source and if it is not followed by any I<may> sources.
2892
2893 After finishing with an C<isl_flow>, the user should call
2894 C<isl_flow_free> to free all associated memory.
2895
2896 A higher-level interface to dependence analysis is provided
2897 by the following function.
2898
2899         #include <isl/flow.h>
2900
2901         int isl_union_map_compute_flow(__isl_take isl_union_map *sink,
2902                 __isl_take isl_union_map *must_source,
2903                 __isl_take isl_union_map *may_source,
2904                 __isl_take isl_union_map *schedule,
2905                 __isl_give isl_union_map **must_dep,
2906                 __isl_give isl_union_map **may_dep,
2907                 __isl_give isl_union_map **must_no_source,
2908                 __isl_give isl_union_map **may_no_source);
2909
2910 The arrays are identified by the tuple names of the ranges
2911 of the accesses.  The iteration domains by the tuple names
2912 of the domains of the accesses and of the schedule.
2913 The relative order of the iteration domains is given by the
2914 schedule.  The relations returned through C<must_no_source>
2915 and C<may_no_source> are subsets of C<sink>.
2916 Any of C<must_dep>, C<may_dep>, C<must_no_source>
2917 or C<may_no_source> may be C<NULL>, but a C<NULL> value for
2918 any of the other arguments is treated as an error.
2919
2920 =head2 Scheduling
2921
2922 B<The functionality described in this section is fairly new
2923 and may be subject to change.>
2924
2925 The following function can be used to compute a schedule
2926 for a union of domains.  The generated schedule respects
2927 all C<validity> dependences.  That is, all dependence distances
2928 over these dependences in the scheduled space are lexicographically
2929 positive.  The generated schedule schedule also tries to minimize
2930 the dependence distances over C<proximity> dependences.
2931 Moreover, it tries to obtain sequences (bands) of schedule dimensions
2932 for groups of domains where the dependence distances have only
2933 non-negative values.
2934 The algorithm used to construct the schedule is similar to that
2935 of C<Pluto>.
2936
2937         #include <isl/schedule.h>
2938         __isl_give isl_schedule *isl_union_set_compute_schedule(
2939                 __isl_take isl_union_set *domain,
2940                 __isl_take isl_union_map *validity,
2941                 __isl_take isl_union_map *proximity);
2942         void *isl_schedule_free(__isl_take isl_schedule *sched);
2943
2944 A mapping from the domains to the scheduled space can be obtained
2945 from an C<isl_schedule> using the following function.
2946
2947         __isl_give isl_union_map *isl_schedule_get_map(
2948                 __isl_keep isl_schedule *sched);
2949
2950 A representation of the schedule can be printed using
2951          
2952         __isl_give isl_printer *isl_printer_print_schedule(
2953                 __isl_take isl_printer *p,
2954                 __isl_keep isl_schedule *schedule);
2955
2956 A representation of the schedule as a forest of bands can be obtained
2957 using the following function.
2958
2959         __isl_give isl_band_list *isl_schedule_get_band_forest(
2960                 __isl_keep isl_schedule *schedule);
2961
2962 The list can be manipulated as explained in L<"Lists">.
2963 The bands inside the list can be copied and freed using the following
2964 functions.
2965
2966         #include <isl/band.h>
2967         __isl_give isl_band *isl_band_copy(
2968                 __isl_keep isl_band *band);
2969         void *isl_band_free(__isl_take isl_band *band);
2970
2971 Each band contains zero or more scheduling dimensions.
2972 These are referred to as the members of the band.
2973 The section of the schedule that corresponds to the band is
2974 referred to as the partial schedule of the band.
2975 For those nodes that participate in a band, the outer scheduling
2976 dimensions form the prefix schedule, while the inner scheduling
2977 dimensions form the suffix schedule.
2978 That is, if we take a cut of the band forest, then the union of
2979 the concatenations of the prefix, partial and suffix schedules of
2980 each band in the cut is equal to the entire schedule (modulo
2981 some possible padding at the end with zero scheduling dimensions).
2982 The properties of a band can be inspected using the following functions.
2983
2984         #include <isl/band.h>
2985         isl_ctx *isl_band_get_ctx(__isl_keep isl_band *band);
2986
2987         int isl_band_has_children(__isl_keep isl_band *band);
2988         __isl_give isl_band_list *isl_band_get_children(
2989                 __isl_keep isl_band *band);
2990
2991         __isl_give isl_union_map *isl_band_get_prefix_schedule(
2992                 __isl_keep isl_band *band);
2993         __isl_give isl_union_map *isl_band_get_partial_schedule(
2994                 __isl_keep isl_band *band);
2995         __isl_give isl_union_map *isl_band_get_suffix_schedule(
2996                 __isl_keep isl_band *band);
2997
2998         int isl_band_n_member(__isl_keep isl_band *band);
2999         int isl_band_member_is_parallel(__isl_keep isl_band *band,
3000                 int pos);
3001
3002 Note that a scheduling dimension is considered parallel if it
3003 does not carry any proximity dependences.
3004
3005 A representation of the band can be printed using
3006
3007         #include <isl/band.h>
3008         __isl_give isl_printer *isl_printer_print_band(
3009                 __isl_take isl_printer *p,
3010                 __isl_keep isl_band *band);
3011
3012 Alternatively, the schedule mapping
3013 can also be obtained in pieces using the following functions.
3014
3015         int isl_schedule_n_band(__isl_keep isl_schedule *sched);
3016         __isl_give isl_union_map *isl_schedule_get_band(
3017                 __isl_keep isl_schedule *sched, unsigned band);
3018
3019 C<isl_schedule_n_band> returns the maximal number of bands.
3020 C<isl_schedule_get_band> returns a union of mappings from a domain to
3021 the band of consecutive schedule dimensions with the given sequence
3022 number for that domain.  Bands with the same sequence number but for
3023 different domains may be completely unrelated.
3024 Within a band, the corresponding coordinates of the distance vectors
3025 are all non-negative, assuming that the coordinates for all previous
3026 bands are all zero.
3027
3028 =head2 Parametric Vertex Enumeration
3029
3030 The parametric vertex enumeration described in this section
3031 is mainly intended to be used internally and by the C<barvinok>
3032 library.
3033
3034         #include <isl/vertices.h>
3035         __isl_give isl_vertices *isl_basic_set_compute_vertices(
3036                 __isl_keep isl_basic_set *bset);
3037
3038 The function C<isl_basic_set_compute_vertices> performs the
3039 actual computation of the parametric vertices and the chamber
3040 decomposition and store the result in an C<isl_vertices> object.
3041 This information can be queried by either iterating over all
3042 the vertices or iterating over all the chambers or cells
3043 and then iterating over all vertices that are active on the chamber.
3044
3045         int isl_vertices_foreach_vertex(
3046                 __isl_keep isl_vertices *vertices,
3047                 int (*fn)(__isl_take isl_vertex *vertex, void *user),
3048                 void *user);
3049
3050         int isl_vertices_foreach_cell(
3051                 __isl_keep isl_vertices *vertices,
3052                 int (*fn)(__isl_take isl_cell *cell, void *user),
3053                 void *user);
3054         int isl_cell_foreach_vertex(__isl_keep isl_cell *cell,
3055                 int (*fn)(__isl_take isl_vertex *vertex, void *user),
3056                 void *user);
3057
3058 Other operations that can be performed on an C<isl_vertices> object are
3059 the following.
3060
3061         isl_ctx *isl_vertices_get_ctx(
3062                 __isl_keep isl_vertices *vertices);
3063         int isl_vertices_get_n_vertices(
3064                 __isl_keep isl_vertices *vertices);
3065         void isl_vertices_free(__isl_take isl_vertices *vertices);
3066
3067 Vertices can be inspected and destroyed using the following functions.
3068
3069         isl_ctx *isl_vertex_get_ctx(__isl_keep isl_vertex *vertex);
3070         int isl_vertex_get_id(__isl_keep isl_vertex *vertex);
3071         __isl_give isl_basic_set *isl_vertex_get_domain(
3072                 __isl_keep isl_vertex *vertex);
3073         __isl_give isl_basic_set *isl_vertex_get_expr(
3074                 __isl_keep isl_vertex *vertex);
3075         void isl_vertex_free(__isl_take isl_vertex *vertex);
3076
3077 C<isl_vertex_get_expr> returns a singleton parametric set describing
3078 the vertex, while C<isl_vertex_get_domain> returns the activity domain
3079 of the vertex.
3080 Note that C<isl_vertex_get_domain> and C<isl_vertex_get_expr> return
3081 B<rational> basic sets, so they should mainly be used for inspection
3082 and should not be mixed with integer sets.
3083
3084 Chambers can be inspected and destroyed using the following functions.
3085
3086         isl_ctx *isl_cell_get_ctx(__isl_keep isl_cell *cell);
3087         __isl_give isl_basic_set *isl_cell_get_domain(
3088                 __isl_keep isl_cell *cell);
3089         void isl_cell_free(__isl_take isl_cell *cell);
3090
3091 =head1 Applications
3092
3093 Although C<isl> is mainly meant to be used as a library,
3094 it also contains some basic applications that use some
3095 of the functionality of C<isl>.
3096 The input may be specified in either the L<isl format>
3097 or the L<PolyLib format>.
3098
3099 =head2 C<isl_polyhedron_sample>
3100
3101 C<isl_polyhedron_sample> takes a polyhedron as input and prints
3102 an integer element of the polyhedron, if there is any.
3103 The first column in the output is the denominator and is always
3104 equal to 1.  If the polyhedron contains no integer points,
3105 then a vector of length zero is printed.
3106
3107 =head2 C<isl_pip>
3108
3109 C<isl_pip> takes the same input as the C<example> program
3110 from the C<piplib> distribution, i.e., a set of constraints
3111 on the parameters, a line containing only -1 and finally a set
3112 of constraints on a parametric polyhedron.
3113 The coefficients of the parameters appear in the last columns
3114 (but before the final constant column).
3115 The output is the lexicographic minimum of the parametric polyhedron.
3116 As C<isl> currently does not have its own output format, the output
3117 is just a dump of the internal state.
3118
3119 =head2 C<isl_polyhedron_minimize>
3120
3121 C<isl_polyhedron_minimize> computes the minimum of some linear
3122 or affine objective function over the integer points in a polyhedron.
3123 If an affine objective function
3124 is given, then the constant should appear in the last column.
3125
3126 =head2 C<isl_polytope_scan>
3127
3128 Given a polytope, C<isl_polytope_scan> prints
3129 all integer points in the polytope.