doc: update isl_pw_qpolynomial_gist description
[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 =head1 Installation
50
51 The source of C<isl> can be obtained either as a tarball
52 or from the git repository.  Both are available from
53 L<http://freshmeat.net/projects/isl/>.
54 The installation process depends on how you obtained
55 the source.
56
57 =head2 Installation from the git repository
58
59 =over
60
61 =item 1 Clone or update the repository
62
63 The first time the source is obtained, you need to clone
64 the repository.
65
66         git clone git://repo.or.cz/isl.git
67
68 To obtain updates, you need to pull in the latest changes
69
70         git pull
71
72 =item 2 Generate C<configure>
73
74         ./autogen.sh
75
76 =back
77
78 After performing the above steps, continue
79 with the L<Common installation instructions>.
80
81 =head2 Common installation instructions
82
83 =over
84
85 =item 1 Obtain C<GMP>
86
87 Building C<isl> requires C<GMP>, including its headers files.
88 Your distribution may not provide these header files by default
89 and you may need to install a package called C<gmp-devel> or something
90 similar.  Alternatively, C<GMP> can be built from
91 source, available from L<http://gmplib.org/>.
92
93 =item 2 Configure
94
95 C<isl> uses the standard C<autoconf> C<configure> script.
96 To run it, just type
97
98         ./configure
99
100 optionally followed by some configure options.
101 A complete list of options can be obtained by running
102
103         ./configure --help
104
105 Below we discuss some of the more common options.
106
107 C<isl> can optionally use C<piplib>, but no
108 C<piplib> functionality is currently used by default.
109 The C<--with-piplib> option can
110 be used to specify which C<piplib>
111 library to use, either an installed version (C<system>),
112 an externally built version (C<build>)
113 or no version (C<no>).  The option C<build> is mostly useful
114 in C<configure> scripts of larger projects that bundle both C<isl>
115 and C<piplib>.
116
117 =over
118
119 =item C<--prefix>
120
121 Installation prefix for C<isl>
122
123 =item C<--with-gmp-prefix>
124
125 Installation prefix for C<GMP> (architecture-independent files).
126
127 =item C<--with-gmp-exec-prefix>
128
129 Installation prefix for C<GMP> (architecture-dependent files).
130
131 =item C<--with-piplib>
132
133 Which copy of C<piplib> to use, either C<no> (default), C<system> or C<build>.
134
135 =item C<--with-piplib-prefix>
136
137 Installation prefix for C<system> C<piplib> (architecture-independent files).
138
139 =item C<--with-piplib-exec-prefix>
140
141 Installation prefix for C<system> C<piplib> (architecture-dependent files).
142
143 =item C<--with-piplib-builddir>
144
145 Location where C<build> C<piplib> was built.
146
147 =back
148
149 =item 3 Compile
150
151         make
152
153 =item 4 Install (optional)
154
155         make install
156
157 =back
158
159 =head1 Library
160
161 =head2 Initialization
162
163 All manipulations of integer sets and relations occur within
164 the context of an C<isl_ctx>.
165 A given C<isl_ctx> can only be used within a single thread.
166 All arguments of a function are required to have been allocated
167 within the same context.
168 There are currently no functions available for moving an object
169 from one C<isl_ctx> to another C<isl_ctx>.  This means that
170 there is currently no way of safely moving an object from one
171 thread to another, unless the whole C<isl_ctx> is moved.
172
173 An C<isl_ctx> can be allocated using C<isl_ctx_alloc> and
174 freed using C<isl_ctx_free>.
175 All objects allocated within an C<isl_ctx> should be freed
176 before the C<isl_ctx> itself is freed.
177
178         isl_ctx *isl_ctx_alloc();
179         void isl_ctx_free(isl_ctx *ctx);
180
181 =head2 Integers
182
183 All operations on integers, mainly the coefficients
184 of the constraints describing the sets and relations,
185 are performed in exact integer arithmetic using C<GMP>.
186 However, to allow future versions of C<isl> to optionally
187 support fixed integer arithmetic, all calls to C<GMP>
188 are wrapped inside C<isl> specific macros.
189 The basic type is C<isl_int> and the following operations
190 are available on this type.
191 The meanings of these operations are essentially the same
192 as their C<GMP> C<mpz_> counterparts.
193 As always with C<GMP> types, C<isl_int>s need to be
194 initialized with C<isl_int_init> before they can be used
195 and they need to be released with C<isl_int_clear>
196 after the last use.
197
198 =over
199
200 =item isl_int_init(i)
201
202 =item isl_int_clear(i)
203
204 =item isl_int_set(r,i)
205
206 =item isl_int_set_si(r,i)
207
208 =item isl_int_set_gmp(r,g)
209
210 =item isl_int_get_gmp(i,g)
211
212 =item isl_int_abs(r,i)
213
214 =item isl_int_neg(r,i)
215
216 =item isl_int_swap(i,j)
217
218 =item isl_int_swap_or_set(i,j)
219
220 =item isl_int_add_ui(r,i,j)
221
222 =item isl_int_sub_ui(r,i,j)
223
224 =item isl_int_add(r,i,j)
225
226 =item isl_int_sub(r,i,j)
227
228 =item isl_int_mul(r,i,j)
229
230 =item isl_int_mul_ui(r,i,j)
231
232 =item isl_int_addmul(r,i,j)
233
234 =item isl_int_submul(r,i,j)
235
236 =item isl_int_gcd(r,i,j)
237
238 =item isl_int_lcm(r,i,j)
239
240 =item isl_int_divexact(r,i,j)
241
242 =item isl_int_cdiv_q(r,i,j)
243
244 =item isl_int_fdiv_q(r,i,j)
245
246 =item isl_int_fdiv_r(r,i,j)
247
248 =item isl_int_fdiv_q_ui(r,i,j)
249
250 =item isl_int_read(r,s)
251
252 =item isl_int_print(out,i,width)
253
254 =item isl_int_sgn(i)
255
256 =item isl_int_cmp(i,j)
257
258 =item isl_int_cmp_si(i,si)
259
260 =item isl_int_eq(i,j)
261
262 =item isl_int_ne(i,j)
263
264 =item isl_int_lt(i,j)
265
266 =item isl_int_le(i,j)
267
268 =item isl_int_gt(i,j)
269
270 =item isl_int_ge(i,j)
271
272 =item isl_int_abs_eq(i,j)
273
274 =item isl_int_abs_ne(i,j)
275
276 =item isl_int_abs_lt(i,j)
277
278 =item isl_int_abs_gt(i,j)
279
280 =item isl_int_abs_ge(i,j)
281
282 =item isl_int_is_zero(i)
283
284 =item isl_int_is_one(i)
285
286 =item isl_int_is_negone(i)
287
288 =item isl_int_is_pos(i)
289
290 =item isl_int_is_neg(i)
291
292 =item isl_int_is_nonpos(i)
293
294 =item isl_int_is_nonneg(i)
295
296 =item isl_int_is_divisible_by(i,j)
297
298 =back
299
300 =head2 Sets and Relations
301
302 C<isl> uses six types of objects for representing sets and relations,
303 C<isl_basic_set>, C<isl_basic_map>, C<isl_set>, C<isl_map>,
304 C<isl_union_set> and C<isl_union_map>.
305 C<isl_basic_set> and C<isl_basic_map> represent sets and relations that
306 can be described as a conjunction of affine constraints, while
307 C<isl_set> and C<isl_map> represent unions of
308 C<isl_basic_set>s and C<isl_basic_map>s, respectively.
309 However, all C<isl_basic_set>s or C<isl_basic_map>s in the union need
310 to have the same dimension.  C<isl_union_set>s and C<isl_union_map>s
311 represent unions of C<isl_set>s or C<isl_map>s of I<different> dimensions,
312 where dimensions with different space names
313 (see L<Dimension Specifications>) are considered different as well.
314 The difference between sets and relations (maps) is that sets have
315 one set of variables, while relations have two sets of variables,
316 input variables and output variables.
317
318 =head2 Memory Management
319
320 Since a high-level operation on sets and/or relations usually involves
321 several substeps and since the user is usually not interested in
322 the intermediate results, most functions that return a new object
323 will also release all the objects passed as arguments.
324 If the user still wants to use one or more of these arguments
325 after the function call, she should pass along a copy of the
326 object rather than the object itself.
327 The user is then responsible for make sure that the original
328 object gets used somewhere else or is explicitly freed.
329
330 The arguments and return values of all documents functions are
331 annotated to make clear which arguments are released and which
332 arguments are preserved.  In particular, the following annotations
333 are used
334
335 =over
336
337 =item C<__isl_give>
338
339 C<__isl_give> means that a new object is returned.
340 The user should make sure that the returned pointer is
341 used exactly once as a value for an C<__isl_take> argument.
342 In between, it can be used as a value for as many
343 C<__isl_keep> arguments as the user likes.
344 There is one exception, and that is the case where the
345 pointer returned is C<NULL>.  Is this case, the user
346 is free to use it as an C<__isl_take> argument or not.
347
348 =item C<__isl_take>
349
350 C<__isl_take> means that the object the argument points to
351 is taken over by the function and may no longer be used
352 by the user as an argument to any other function.
353 The pointer value must be one returned by a function
354 returning an C<__isl_give> pointer.
355 If the user passes in a C<NULL> value, then this will
356 be treated as an error in the sense that the function will
357 not perform its usual operation.  However, it will still
358 make sure that all the the other C<__isl_take> arguments
359 are released.
360
361 =item C<__isl_keep>
362
363 C<__isl_keep> means that the function will only use the object
364 temporarily.  After the function has finished, the user
365 can still use it as an argument to other functions.
366 A C<NULL> value will be treated in the same way as
367 a C<NULL> value for an C<__isl_take> argument.
368
369 =back
370
371 =head2 Dimension Specifications
372
373 Whenever a new set or relation is created from scratch,
374 its dimension needs to be specified using an C<isl_dim>.
375
376         #include <isl_dim.h>
377         __isl_give isl_dim *isl_dim_alloc(isl_ctx *ctx,
378                 unsigned nparam, unsigned n_in, unsigned n_out);
379         __isl_give isl_dim *isl_dim_set_alloc(isl_ctx *ctx,
380                 unsigned nparam, unsigned dim);
381         __isl_give isl_dim *isl_dim_copy(__isl_keep isl_dim *dim);
382         void isl_dim_free(__isl_take isl_dim *dim);
383         unsigned isl_dim_size(__isl_keep isl_dim *dim,
384                 enum isl_dim_type type);
385
386 The dimension specification used for creating a set
387 needs to be created using C<isl_dim_set_alloc>, while
388 that for creating a relation
389 needs to be created using C<isl_dim_alloc>.
390 C<isl_dim_size> can be used
391 to find out the number of dimensions of each type in
392 a dimension specification, where type may be
393 C<isl_dim_param>, C<isl_dim_in> (only for relations),
394 C<isl_dim_out> (only for relations), C<isl_dim_set>
395 (only for sets) or C<isl_dim_all>.
396
397 It is often useful to create objects that live in the
398 same space as some other object.  This can be accomplished
399 by creating the new objects
400 (see L<Creating New Sets and Relations> or
401 L<Creating New (Piecewise) Quasipolynomials>) based on the dimension
402 specification of the original object.
403
404         #include <isl_set.h>
405         __isl_give isl_dim *isl_basic_set_get_dim(
406                 __isl_keep isl_basic_set *bset);
407         __isl_give isl_dim *isl_set_get_dim(__isl_keep isl_set *set);
408
409         #include <isl_union_set.h>
410         __isl_give isl_dim *isl_union_set_get_dim(
411                 __isl_keep isl_union_set *uset);
412
413         #include <isl_map.h>
414         __isl_give isl_dim *isl_basic_map_get_dim(
415                 __isl_keep isl_basic_map *bmap);
416         __isl_give isl_dim *isl_map_get_dim(__isl_keep isl_map *map);
417
418         #include <isl_union_map.h>
419         __isl_give isl_dim *isl_union_map_get_dim(
420                 __isl_keep isl_union_map *umap);
421
422         #include <isl_polynomial.h>
423         __isl_give isl_dim *isl_qpolynomial_get_dim(
424                 __isl_keep isl_qpolynomial *qp);
425         __isl_give isl_dim *isl_pw_qpolynomial_get_dim(
426                 __isl_keep isl_pw_qpolynomial *pwqp);
427         __isl_give isl_dim *isl_union_pw_qpolynomial_get_dim(
428                 __isl_keep isl_union_pw_qpolynomial *upwqp);
429         __isl_give isl_dim *isl_union_pw_qpolynomial_fold_get_dim(
430                 __isl_keep isl_union_pw_qpolynomial_fold *upwf);
431
432 The names of the individual dimensions may be set or read off
433 using the following functions.
434
435         #include <isl_dim.h>
436         __isl_give isl_dim *isl_dim_set_name(__isl_take isl_dim *dim,
437                                  enum isl_dim_type type, unsigned pos,
438                                  __isl_keep const char *name);
439         __isl_keep const char *isl_dim_get_name(__isl_keep isl_dim *dim,
440                                  enum isl_dim_type type, unsigned pos);
441
442 Note that C<isl_dim_get_name> returns a pointer to some internal
443 data structure, so the result can only be used while the
444 corresponding C<isl_dim> is alive.
445 Also note that every function that operates on two sets or relations
446 requires that both arguments have the same parameters.  This also
447 means that if one of the arguments has named parameters, then the
448 other needs to have named parameters too and the names need to match.
449 Pairs of C<isl_union_set> and/or C<isl_union_map> arguments may
450 have different parameters (as long as they are named), in which case
451 the result will have as parameters the union of the parameters of
452 the arguments.
453
454 The names of entire spaces may be set or read off
455 using the following functions.
456
457         #include <isl_dim.h>
458         __isl_give isl_dim *isl_dim_set_tuple_name(
459                 __isl_take isl_dim *dim,
460                 enum isl_dim_type type, const char *s);
461         const char *isl_dim_get_tuple_name(__isl_keep isl_dim *dim,
462                 enum isl_dim_type type);
463
464 The C<dim> argument needs to be one of C<isl_dim_in>, C<isl_dim_out>
465 or C<isl_dim_set>.  As with C<isl_dim_get_name>,
466 the C<isl_dim_get_tuple_name> function returns a pointer to some internal
467 data structure.
468 Binary operations require the corresponding spaces of their arguments
469 to have the same name.
470
471 Spaces can be nested.  In particular, the domain of a set or
472 the domain or range of a relation can be a nested relation.
473 The following functions can be used to construct and deconstruct
474 such nested dimension specifications.
475
476         #include <isl_dim.h>
477         int isl_dim_is_wrapping(__isl_keep isl_dim *dim);
478         __isl_give isl_dim *isl_dim_wrap(__isl_take isl_dim *dim);
479         __isl_give isl_dim *isl_dim_unwrap(__isl_take isl_dim *dim);
480
481 The input to C<isl_dim_is_wrapping> and C<isl_dim_unwrap> should
482 be the dimension specification of a set, while that of
483 C<isl_dim_wrap> should be the dimension specification of a relation.
484 Conversely, the output of C<isl_dim_unwrap> is the dimension specification
485 of a relation, while that of C<isl_dim_wrap> is the dimension specification
486 of a set.
487
488 Dimension specifications can be created from other dimension
489 specifications using the following functions.
490
491         __isl_give isl_dim *isl_dim_domain(__isl_take isl_dim *dim);
492         __isl_give isl_dim *isl_dim_from_domain(__isl_take isl_dim *dim);
493         __isl_give isl_dim *isl_dim_range(__isl_take isl_dim *dim);
494         __isl_give isl_dim *isl_dim_from_range(__isl_take isl_dim *dim);
495         __isl_give isl_dim *isl_dim_reverse(__isl_take isl_dim *dim);
496         __isl_give isl_dim *isl_dim_join(__isl_take isl_dim *left,
497                 __isl_take isl_dim *right);
498         __isl_give isl_dim *isl_dim_insert(__isl_take isl_dim *dim,
499                 enum isl_dim_type type, unsigned pos, unsigned n);
500         __isl_give isl_dim *isl_dim_add(__isl_take isl_dim *dim,
501                 enum isl_dim_type type, unsigned n);
502         __isl_give isl_dim *isl_dim_drop(__isl_take isl_dim *dim,
503                 enum isl_dim_type type, unsigned first, unsigned n);
504
505 Note that if dimensions are added or removed from a space, then
506 the name and the internal structure are lost.
507
508 =head2 Input and Output
509
510 C<isl> supports its own input/output format, which is similar
511 to the C<Omega> format, but also supports the C<PolyLib> format
512 in some cases.
513
514 =head3 C<isl> format
515
516 The C<isl> format is similar to that of C<Omega>, but has a different
517 syntax for describing the parameters and allows for the definition
518 of an existentially quantified variable as the integer division
519 of an affine expression.
520 For example, the set of integers C<i> between C<0> and C<n>
521 such that C<i % 10 <= 6> can be described as
522
523         [n] -> { [i] : exists (a = [i/10] : 0 <= i and i <= n and
524                                 i - 10 a <= 6) }
525
526 A set or relation can have several disjuncts, separated
527 by the keyword C<or>.  Each disjunct is either a conjunction
528 of constraints or a projection (C<exists>) of a conjunction
529 of constraints.  The constraints are separated by the keyword
530 C<and>.
531
532 =head3 C<PolyLib> format
533
534 If the represented set is a union, then the first line
535 contains a single number representing the number of disjuncts.
536 Otherwise, a line containing the number C<1> is optional.
537
538 Each disjunct is represented by a matrix of constraints.
539 The first line contains two numbers representing
540 the number of rows and columns,
541 where the number of rows is equal to the number of constraints
542 and the number of columns is equal to two plus the number of variables.
543 The following lines contain the actual rows of the constraint matrix.
544 In each row, the first column indicates whether the constraint
545 is an equality (C<0>) or inequality (C<1>).  The final column
546 corresponds to the constant term.
547
548 If the set is parametric, then the coefficients of the parameters
549 appear in the last columns before the constant column.
550 The coefficients of any existentially quantified variables appear
551 between those of the set variables and those of the parameters.
552
553 =head3 Extended C<PolyLib> format
554
555 The extended C<PolyLib> format is nearly identical to the
556 C<PolyLib> format.  The only difference is that the line
557 containing the number of rows and columns of a constraint matrix
558 also contains four additional numbers:
559 the number of output dimensions, the number of input dimensions,
560 the number of local dimensions (i.e., the number of existentially
561 quantified variables) and the number of parameters.
562 For sets, the number of ``output'' dimensions is equal
563 to the number of set dimensions, while the number of ``input''
564 dimensions is zero.
565
566 =head3 Input
567
568         #include <isl_set.h>
569         __isl_give isl_basic_set *isl_basic_set_read_from_file(
570                 isl_ctx *ctx, FILE *input, int nparam);
571         __isl_give isl_basic_set *isl_basic_set_read_from_str(
572                 isl_ctx *ctx, const char *str, int nparam);
573         __isl_give isl_set *isl_set_read_from_file(isl_ctx *ctx,
574                 FILE *input, int nparam);
575         __isl_give isl_set *isl_set_read_from_str(isl_ctx *ctx,
576                 const char *str, int nparam);
577
578         #include <isl_map.h>
579         __isl_give isl_basic_map *isl_basic_map_read_from_file(
580                 isl_ctx *ctx, FILE *input, int nparam);
581         __isl_give isl_basic_map *isl_basic_map_read_from_str(
582                 isl_ctx *ctx, const char *str, int nparam);
583         __isl_give isl_map *isl_map_read_from_file(
584                 struct isl_ctx *ctx, FILE *input, int nparam);
585         __isl_give isl_map *isl_map_read_from_str(isl_ctx *ctx,
586                 const char *str, int nparam);
587
588 The input format is autodetected and may be either the C<PolyLib> format
589 or the C<isl> format.
590 C<nparam> specifies how many of the final columns in
591 the C<PolyLib> format correspond to parameters.
592 If input is given in the C<isl> format, then the number
593 of parameters needs to be equal to C<nparam>.
594 If C<nparam> is negative, then any number of parameters
595 is accepted in the C<isl> format and zero parameters
596 are assumed in the C<PolyLib> format.
597
598 =head3 Output
599
600 Before anything can be printed, an C<isl_printer> needs to
601 be created.
602
603         __isl_give isl_printer *isl_printer_to_file(isl_ctx *ctx,
604                 FILE *file);
605         __isl_give isl_printer *isl_printer_to_str(isl_ctx *ctx);
606         void isl_printer_free(__isl_take isl_printer *printer);
607         __isl_give char *isl_printer_get_str(
608                 __isl_keep isl_printer *printer);
609
610 The behavior of the printer can be modified in various ways
611
612         __isl_give isl_printer *isl_printer_set_output_format(
613                 __isl_take isl_printer *p, int output_format);
614         __isl_give isl_printer *isl_printer_set_indent(
615                 __isl_take isl_printer *p, int indent);
616         __isl_give isl_printer *isl_printer_set_prefix(
617                 __isl_take isl_printer *p, const char *prefix);
618         __isl_give isl_printer *isl_printer_set_suffix(
619                 __isl_take isl_printer *p, const char *suffix);
620
621 The C<output_format> may be either C<ISL_FORMAT_ISL>, C<ISL_FORMAT_OMEGA>,
622 C<ISL_FORMAT_POLYLIB>, C<ISL_FORMAT_EXT_POLYLIB> or C<ISL_FORMAT_LATEX>
623 and defaults to C<ISL_FORMAT_ISL>.
624 Each line in the output is indented by C<indent> spaces
625 (default: 0), prefixed by C<prefix> and suffixed by C<suffix>.
626 In the C<PolyLib> format output,
627 the coefficients of the existentially quantified variables
628 appear between those of the set variables and those
629 of the parameters.
630
631 To actually print something, use
632
633         #include <isl_set.h>
634         __isl_give isl_printer *isl_printer_print_basic_set(
635                 __isl_take isl_printer *printer,
636                 __isl_keep isl_basic_set *bset);
637         __isl_give isl_printer *isl_printer_print_set(
638                 __isl_take isl_printer *printer,
639                 __isl_keep isl_set *set);
640
641         #include <isl_map.h>
642         __isl_give isl_printer *isl_printer_print_basic_map(
643                 __isl_take isl_printer *printer,
644                 __isl_keep isl_basic_map *bmap);
645         __isl_give isl_printer *isl_printer_print_map(
646                 __isl_take isl_printer *printer,
647                 __isl_keep isl_map *map);
648
649         #include <isl_union_set.h>
650         __isl_give isl_printer *isl_printer_print_union_set(
651                 __isl_take isl_printer *p,
652                 __isl_keep isl_union_set *uset);
653
654         #include <isl_union_map.h>
655         __isl_give isl_printer *isl_printer_print_union_map(
656                 __isl_take isl_printer *p,
657                 __isl_keep isl_union_map *umap);
658
659 When called on a file printer, the following function flushes
660 the file.  When called on a string printer, the buffer is cleared.
661
662         __isl_give isl_printer *isl_printer_flush(
663                 __isl_take isl_printer *p);
664
665 =head2 Creating New Sets and Relations
666
667 C<isl> has functions for creating some standard sets and relations.
668
669 =over
670
671 =item * Empty sets and relations
672
673         __isl_give isl_basic_set *isl_basic_set_empty(
674                 __isl_take isl_dim *dim);
675         __isl_give isl_basic_map *isl_basic_map_empty(
676                 __isl_take isl_dim *dim);
677         __isl_give isl_set *isl_set_empty(
678                 __isl_take isl_dim *dim);
679         __isl_give isl_map *isl_map_empty(
680                 __isl_take isl_dim *dim);
681         __isl_give isl_union_set *isl_union_set_empty(
682                 __isl_take isl_dim *dim);
683         __isl_give isl_union_map *isl_union_map_empty(
684                 __isl_take isl_dim *dim);
685
686 For C<isl_union_set>s and C<isl_union_map>s, the dimensions specification
687 is only used to specify the parameters.
688
689 =item * Universe sets and relations
690
691         __isl_give isl_basic_set *isl_basic_set_universe(
692                 __isl_take isl_dim *dim);
693         __isl_give isl_basic_map *isl_basic_map_universe(
694                 __isl_take isl_dim *dim);
695         __isl_give isl_set *isl_set_universe(
696                 __isl_take isl_dim *dim);
697         __isl_give isl_map *isl_map_universe(
698                 __isl_take isl_dim *dim);
699
700 =item * Identity relations
701
702         __isl_give isl_basic_map *isl_basic_map_identity(
703                 __isl_take isl_dim *set_dim);
704         __isl_give isl_map *isl_map_identity(
705                 __isl_take isl_dim *set_dim);
706
707 These functions take a dimension specification for a B<set>
708 and return an identity relation between two such sets.
709
710 =item * Lexicographic order
711
712         __isl_give isl_map *isl_map_lex_lt(
713                 __isl_take isl_dim *set_dim);
714         __isl_give isl_map *isl_map_lex_le(
715                 __isl_take isl_dim *set_dim);
716         __isl_give isl_map *isl_map_lex_gt(
717                 __isl_take isl_dim *set_dim);
718         __isl_give isl_map *isl_map_lex_ge(
719                 __isl_take isl_dim *set_dim);
720         __isl_give isl_map *isl_map_lex_lt_first(
721                 __isl_take isl_dim *dim, unsigned n);
722         __isl_give isl_map *isl_map_lex_le_first(
723                 __isl_take isl_dim *dim, unsigned n);
724         __isl_give isl_map *isl_map_lex_gt_first(
725                 __isl_take isl_dim *dim, unsigned n);
726         __isl_give isl_map *isl_map_lex_ge_first(
727                 __isl_take isl_dim *dim, unsigned n);
728
729 The first four functions take a dimension specification for a B<set>
730 and return relations that express that the elements in the domain
731 are lexicographically less
732 (C<isl_map_lex_lt>), less or equal (C<isl_map_lex_le>),
733 greater (C<isl_map_lex_gt>) or greater or equal (C<isl_map_lex_ge>)
734 than the elements in the range.
735 The last four functions take a dimension specification for a map
736 and return relations that express that the first C<n> dimensions
737 in the domain are lexicographically less
738 (C<isl_map_lex_lt_first>), less or equal (C<isl_map_lex_le_first>),
739 greater (C<isl_map_lex_gt_first>) or greater or equal (C<isl_map_lex_ge_first>)
740 than the first C<n> dimensions in the range.
741
742 =back
743
744 A basic set or relation can be converted to a set or relation
745 using the following functions.
746
747         __isl_give isl_set *isl_set_from_basic_set(
748                 __isl_take isl_basic_set *bset);
749         __isl_give isl_map *isl_map_from_basic_map(
750                 __isl_take isl_basic_map *bmap);
751
752 Sets and relations can be converted to union sets and relations
753 using the following functions.
754
755         __isl_give isl_union_map *isl_union_map_from_map(
756                 __isl_take isl_map *map);
757         __isl_give isl_union_set *isl_union_set_from_set(
758                 __isl_take isl_set *set);
759
760 Sets and relations can be copied and freed again using the following
761 functions.
762
763         __isl_give isl_basic_set *isl_basic_set_copy(
764                 __isl_keep isl_basic_set *bset);
765         __isl_give isl_set *isl_set_copy(__isl_keep isl_set *set);
766         __isl_give isl_union_set *isl_union_set_copy(
767                 __isl_keep isl_union_set *uset);
768         __isl_give isl_basic_map *isl_basic_map_copy(
769                 __isl_keep isl_basic_map *bmap);
770         __isl_give isl_map *isl_map_copy(__isl_keep isl_map *map);
771         __isl_give isl_union_map *isl_union_map_copy(
772                 __isl_keep isl_union_map *umap);
773         void isl_basic_set_free(__isl_take isl_basic_set *bset);
774         void isl_set_free(__isl_take isl_set *set);
775         void isl_union_set_free(__isl_take isl_union_set *uset);
776         void isl_basic_map_free(__isl_take isl_basic_map *bmap);
777         void isl_map_free(__isl_take isl_map *map);
778         void isl_union_map_free(__isl_take isl_union_map *umap);
779
780 Other sets and relations can be constructed by starting
781 from a universe set or relation, adding equality and/or
782 inequality constraints and then projecting out the
783 existentially quantified variables, if any.
784 Constraints can be constructed, manipulated and
785 added to basic sets and relations using the following functions.
786
787         #include <isl_constraint.h>
788         __isl_give isl_constraint *isl_equality_alloc(
789                 __isl_take isl_dim *dim);
790         __isl_give isl_constraint *isl_inequality_alloc(
791                 __isl_take isl_dim *dim);
792         void isl_constraint_set_constant(
793                 __isl_keep isl_constraint *constraint, isl_int v);
794         void isl_constraint_set_coefficient(
795                 __isl_keep isl_constraint *constraint,
796                 enum isl_dim_type type, int pos, isl_int v);
797         __isl_give isl_basic_map *isl_basic_map_add_constraint(
798                 __isl_take isl_basic_map *bmap,
799                 __isl_take isl_constraint *constraint);
800         __isl_give isl_basic_set *isl_basic_set_add_constraint(
801                 __isl_take isl_basic_set *bset,
802                 __isl_take isl_constraint *constraint);
803
804 For example, to create a set containing the even integers
805 between 10 and 42, you would use the following code.
806
807         isl_int v;
808         struct isl_dim *dim;
809         struct isl_constraint *c;
810         struct isl_basic_set *bset;
811
812         isl_int_init(v);
813         dim = isl_dim_set_alloc(ctx, 0, 2);
814         bset = isl_basic_set_universe(isl_dim_copy(dim));
815
816         c = isl_equality_alloc(isl_dim_copy(dim));
817         isl_int_set_si(v, -1);
818         isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
819         isl_int_set_si(v, 2);
820         isl_constraint_set_coefficient(c, isl_dim_set, 1, v);
821         bset = isl_basic_set_add_constraint(bset, c);
822
823         c = isl_inequality_alloc(isl_dim_copy(dim));
824         isl_int_set_si(v, -10);
825         isl_constraint_set_constant(c, v);
826         isl_int_set_si(v, 1);
827         isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
828         bset = isl_basic_set_add_constraint(bset, c);
829
830         c = isl_inequality_alloc(dim);
831         isl_int_set_si(v, 42);
832         isl_constraint_set_constant(c, v);
833         isl_int_set_si(v, -1);
834         isl_constraint_set_coefficient(c, isl_dim_set, 0, v);
835         bset = isl_basic_set_add_constraint(bset, c);
836
837         bset = isl_basic_set_project_out(bset, isl_dim_set, 1, 1);
838
839         isl_int_clear(v);
840
841 Or, alternatively,
842
843         struct isl_basic_set *bset;
844         bset = isl_basic_set_read_from_str(ctx,
845                 "{[i] : exists (a : i = 2a and i >= 10 and i <= 42)}", -1);
846
847 A basic set or relation can also be constructed from two matrices
848 describing the equalities and the inequalities.
849
850         __isl_give isl_basic_set *isl_basic_set_from_constraint_matrices(
851                 __isl_take isl_dim *dim,
852                 __isl_take isl_mat *eq, __isl_take isl_mat *ineq,
853                 enum isl_dim_type c1,
854                 enum isl_dim_type c2, enum isl_dim_type c3,
855                 enum isl_dim_type c4);
856         __isl_give isl_basic_map *isl_basic_map_from_constraint_matrices(
857                 __isl_take isl_dim *dim,
858                 __isl_take isl_mat *eq, __isl_take isl_mat *ineq,
859                 enum isl_dim_type c1,
860                 enum isl_dim_type c2, enum isl_dim_type c3,
861                 enum isl_dim_type c4, enum isl_dim_type c5);
862
863 The C<isl_dim_type> arguments indicate the order in which
864 different kinds of variables appear in the input matrices
865 and should be a permutation of C<isl_dim_cst>, C<isl_dim_param>,
866 C<isl_dim_set> and C<isl_dim_div> for sets and
867 of C<isl_dim_cst>, C<isl_dim_param>,
868 C<isl_dim_in>, C<isl_dim_out> and C<isl_dim_div> for relations.
869
870 =head2 Inspecting Sets and Relations
871
872 Usually, the user should not have to care about the actual constraints
873 of the sets and maps, but should instead apply the abstract operations
874 explained in the following sections.
875 Occasionally, however, it may be required to inspect the individual
876 coefficients of the constraints.  This section explains how to do so.
877 In these cases, it may also be useful to have C<isl> compute
878 an explicit representation of the existentially quantified variables.
879
880         __isl_give isl_set *isl_set_compute_divs(
881                 __isl_take isl_set *set);
882         __isl_give isl_map *isl_map_compute_divs(
883                 __isl_take isl_map *map);
884         __isl_give isl_union_set *isl_union_set_compute_divs(
885                 __isl_take isl_union_set *uset);
886         __isl_give isl_union_map *isl_union_map_compute_divs(
887                 __isl_take isl_union_map *umap);
888
889 This explicit representation defines the existentially quantified
890 variables as integer divisions of the other variables, possibly
891 including earlier existentially quantified variables.
892 An explicitly represented existentially quantified variable therefore
893 has a unique value when the values of the other variables are known.
894 If, furthermore, the same existentials, i.e., existentials
895 with the same explicit representations, should appear in the
896 same order in each of the disjuncts of a set or map, then the user should call
897 either of the following functions.
898
899         __isl_give isl_set *isl_set_align_divs(
900                 __isl_take isl_set *set);
901         __isl_give isl_map *isl_map_align_divs(
902                 __isl_take isl_map *map);
903
904 Alternatively, the existentially quantified variables can be removed
905 using the following functions, which compute an overapproximation.
906
907         __isl_give isl_basic_set *isl_basic_set_remove_divs(
908                 __isl_take isl_basic_set *bset);
909         __isl_give isl_basic_map *isl_basic_map_remove_divs(
910                 __isl_take isl_basic_map *bmap);
911         __isl_give isl_set *isl_set_remove_divs(
912                 __isl_take isl_set *set);
913
914 To iterate over all the sets or maps in a union set or map, use
915
916         int isl_union_set_foreach_set(__isl_keep isl_union_set *uset,
917                 int (*fn)(__isl_take isl_set *set, void *user),
918                 void *user);
919         int isl_union_map_foreach_map(__isl_keep isl_union_map *umap,
920                 int (*fn)(__isl_take isl_map *map, void *user),
921                 void *user);
922
923 The number of sets or maps in a union set or map can be obtained
924 from
925
926         int isl_union_set_n_set(__isl_keep isl_union_set *uset);
927         int isl_union_map_n_map(__isl_keep isl_union_map *umap);
928
929 To extract the set or map from a union with a given dimension
930 specification, use
931
932         __isl_give isl_set *isl_union_set_extract_set(
933                 __isl_keep isl_union_set *uset,
934                 __isl_take isl_dim *dim);
935         __isl_give isl_map *isl_union_map_extract_map(
936                 __isl_keep isl_union_map *umap,
937                 __isl_take isl_dim *dim);
938
939 To iterate over all the basic sets or maps in a set or map, use
940
941         int isl_set_foreach_basic_set(__isl_keep isl_set *set,
942                 int (*fn)(__isl_take isl_basic_set *bset, void *user),
943                 void *user);
944         int isl_map_foreach_basic_map(__isl_keep isl_map *map,
945                 int (*fn)(__isl_take isl_basic_map *bmap, void *user),
946                 void *user);
947
948 The callback function C<fn> should return 0 if successful and
949 -1 if an error occurs.  In the latter case, or if any other error
950 occurs, the above functions will return -1.
951
952 It should be noted that C<isl> does not guarantee that
953 the basic sets or maps passed to C<fn> are disjoint.
954 If this is required, then the user should call one of
955 the following functions first.
956
957         __isl_give isl_set *isl_set_make_disjoint(
958                 __isl_take isl_set *set);
959         __isl_give isl_map *isl_map_make_disjoint(
960                 __isl_take isl_map *map);
961
962 The number of basic sets in a set can be obtained
963 from
964
965         int isl_set_n_basic_set(__isl_keep isl_set *set);
966
967 To iterate over the constraints of a basic set or map, use
968
969         #include <isl_constraint.h>
970
971         int isl_basic_map_foreach_constraint(
972                 __isl_keep isl_basic_map *bmap,
973                 int (*fn)(__isl_take isl_constraint *c, void *user),
974                 void *user);
975         void isl_constraint_free(struct isl_constraint *c);
976
977 Again, the callback function C<fn> should return 0 if successful and
978 -1 if an error occurs.  In the latter case, or if any other error
979 occurs, the above functions will return -1.
980 The constraint C<c> represents either an equality or an inequality.
981 Use the following function to find out whether a constraint
982 represents an equality.  If not, it represents an inequality.
983
984         int isl_constraint_is_equality(
985                 __isl_keep isl_constraint *constraint);
986
987 The coefficients of the constraints can be inspected using
988 the following functions.
989
990         void isl_constraint_get_constant(
991                 __isl_keep isl_constraint *constraint, isl_int *v);
992         void isl_constraint_get_coefficient(
993                 __isl_keep isl_constraint *constraint,
994                 enum isl_dim_type type, int pos, isl_int *v);
995
996 The explicit representations of the existentially quantified
997 variables can be inspected using the following functions.
998 Note that the user is only allowed to use these functions
999 if the inspected set or map is the result of a call
1000 to C<isl_set_compute_divs> or C<isl_map_compute_divs>.
1001
1002         __isl_give isl_div *isl_constraint_div(
1003                 __isl_keep isl_constraint *constraint, int pos);
1004         void isl_div_get_constant(__isl_keep isl_div *div,
1005                 isl_int *v);
1006         void isl_div_get_denominator(__isl_keep isl_div *div,
1007                 isl_int *v);
1008         void isl_div_get_coefficient(__isl_keep isl_div *div,
1009                 enum isl_dim_type type, int pos, isl_int *v);
1010
1011 To obtain the constraints of a basic map in matrix
1012 form, use the following functions.
1013
1014         __isl_give isl_mat *isl_basic_map_equalities_matrix(
1015                         __isl_keep isl_basic_map *bmap,
1016                         enum isl_dim_type c1,
1017                         enum isl_dim_type c2, enum isl_dim_type c3,
1018                         enum isl_dim_type c4, enum isl_dim_type c5);
1019         __isl_give isl_mat *isl_basic_map_inequalities_matrix(
1020                         __isl_keep isl_basic_map *bmap,
1021                         enum isl_dim_type c1,
1022                         enum isl_dim_type c2, enum isl_dim_type c3,
1023                         enum isl_dim_type c4, enum isl_dim_type c5);
1024
1025 The C<isl_dim_type> arguments dictate the order in which
1026 different kinds of variables appear in the resulting matrix
1027 and should be a permutation of C<isl_dim_cst>, C<isl_dim_param>,
1028 C<isl_dim_in>, C<isl_dim_out> and C<isl_dim_div>.
1029
1030 The names of the domain and range spaces of a set or relation can be
1031 read off using the following functions.
1032
1033         const char *isl_set_get_tuple_name(
1034                 __isl_keep isl_set *set);
1035         const char *isl_basic_map_get_tuple_name(
1036                 __isl_keep isl_basic_map *bmap,
1037                 enum isl_dim_type type);
1038         const char *isl_map_get_tuple_name(
1039                 __isl_keep isl_map *map,
1040                 enum isl_dim_type type);
1041
1042 As with C<isl_dim_get_tuple_name>, the value returned points to
1043 an internal data structure.
1044 The names of individual dimensions can be read off using
1045 the following functions.
1046
1047         const char *isl_constraint_get_dim_name(
1048                 __isl_keep isl_constraint *constraint,
1049                 enum isl_dim_type type, unsigned pos);
1050         const char *isl_set_get_dim_name(
1051                 __isl_keep isl_set *set,
1052                 enum isl_dim_type type, unsigned pos);
1053         const char *isl_basic_map_get_dim_name(
1054                 __isl_keep isl_basic_map *bmap,
1055                 enum isl_dim_type type, unsigned pos);
1056         const char *isl_map_get_dim_name(
1057                 __isl_keep isl_map *map,
1058                 enum isl_dim_type type, unsigned pos);
1059
1060 These functions are mostly useful to obtain the names
1061 of the parameters.
1062
1063 =head2 Properties
1064
1065 =head3 Unary Properties
1066
1067 =over
1068
1069 =item * Emptiness
1070
1071 The following functions test whether the given set or relation
1072 contains any integer points.  The ``fast'' variants do not perform
1073 any computations, but simply check if the given set or relation
1074 is already known to be empty.
1075
1076         int isl_basic_set_fast_is_empty(__isl_keep isl_basic_set *bset);
1077         int isl_basic_set_is_empty(__isl_keep isl_basic_set *bset);
1078         int isl_set_is_empty(__isl_keep isl_set *set);
1079         int isl_union_set_is_empty(__isl_keep isl_union_set *uset);
1080         int isl_basic_map_fast_is_empty(__isl_keep isl_basic_map *bmap);
1081         int isl_basic_map_is_empty(__isl_keep isl_basic_map *bmap);
1082         int isl_map_fast_is_empty(__isl_keep isl_map *map);
1083         int isl_map_is_empty(__isl_keep isl_map *map);
1084         int isl_union_map_is_empty(__isl_keep isl_union_map *umap);
1085
1086 =item * Universality
1087
1088         int isl_basic_set_is_universe(__isl_keep isl_basic_set *bset);
1089         int isl_basic_map_is_universe(__isl_keep isl_basic_map *bmap);
1090         int isl_set_fast_is_universe(__isl_keep isl_set *set);
1091
1092 =item * Single-valuedness
1093
1094         int isl_map_is_single_valued(__isl_keep isl_map *map);
1095
1096 =item * Bijectivity
1097
1098         int isl_map_is_bijective(__isl_keep isl_map *map);
1099
1100 =item * Wrapping
1101
1102 The followning functions check whether the domain of the given
1103 (basic) set is a wrapped relation.
1104
1105         int isl_basic_set_is_wrapping(
1106                 __isl_keep isl_basic_set *bset);
1107         int isl_set_is_wrapping(__isl_keep isl_set *set);
1108
1109 =back
1110
1111 =head3 Binary Properties
1112
1113 =over
1114
1115 =item * Equality
1116
1117         int isl_set_fast_is_equal(__isl_keep isl_set *set1,
1118                 __isl_keep isl_set *set2);
1119         int isl_set_is_equal(__isl_keep isl_set *set1,
1120                 __isl_keep isl_set *set2);
1121         int isl_basic_map_is_equal(
1122                 __isl_keep isl_basic_map *bmap1,
1123                 __isl_keep isl_basic_map *bmap2);
1124         int isl_map_is_equal(__isl_keep isl_map *map1,
1125                 __isl_keep isl_map *map2);
1126         int isl_map_fast_is_equal(__isl_keep isl_map *map1,
1127                 __isl_keep isl_map *map2);
1128         int isl_union_map_is_equal(
1129                 __isl_keep isl_union_map *umap1,
1130                 __isl_keep isl_union_map *umap2);
1131
1132 =item * Disjointness
1133
1134         int isl_set_fast_is_disjoint(__isl_keep isl_set *set1,
1135                 __isl_keep isl_set *set2);
1136
1137 =item * Subset
1138
1139         int isl_set_is_subset(__isl_keep isl_set *set1,
1140                 __isl_keep isl_set *set2);
1141         int isl_set_is_strict_subset(
1142                 __isl_keep isl_set *set1,
1143                 __isl_keep isl_set *set2);
1144         int isl_basic_map_is_subset(
1145                 __isl_keep isl_basic_map *bmap1,
1146                 __isl_keep isl_basic_map *bmap2);
1147         int isl_basic_map_is_strict_subset(
1148                 __isl_keep isl_basic_map *bmap1,
1149                 __isl_keep isl_basic_map *bmap2);
1150         int isl_map_is_subset(
1151                 __isl_keep isl_map *map1,
1152                 __isl_keep isl_map *map2);
1153         int isl_map_is_strict_subset(
1154                 __isl_keep isl_map *map1,
1155                 __isl_keep isl_map *map2);
1156         int isl_union_map_is_subset(
1157                 __isl_keep isl_union_map *umap1,
1158                 __isl_keep isl_union_map *umap2);
1159         int isl_union_map_is_strict_subset(
1160                 __isl_keep isl_union_map *umap1,
1161                 __isl_keep isl_union_map *umap2);
1162
1163 =back
1164
1165 =head2 Unary Operations
1166
1167 =over
1168
1169 =item * Complement
1170
1171         __isl_give isl_set *isl_set_complement(
1172                 __isl_take isl_set *set);
1173
1174 =item * Inverse map
1175
1176         __isl_give isl_basic_map *isl_basic_map_reverse(
1177                 __isl_take isl_basic_map *bmap);
1178         __isl_give isl_map *isl_map_reverse(
1179                 __isl_take isl_map *map);
1180         __isl_give isl_union_map *isl_union_map_reverse(
1181                 __isl_take isl_union_map *umap);
1182
1183 =item * Projection
1184
1185         __isl_give isl_basic_set *isl_basic_set_project_out(
1186                 __isl_take isl_basic_set *bset,
1187                 enum isl_dim_type type, unsigned first, unsigned n);
1188         __isl_give isl_basic_map *isl_basic_map_project_out(
1189                 __isl_take isl_basic_map *bmap,
1190                 enum isl_dim_type type, unsigned first, unsigned n);
1191         __isl_give isl_set *isl_set_project_out(__isl_take isl_set *set,
1192                 enum isl_dim_type type, unsigned first, unsigned n);
1193         __isl_give isl_map *isl_map_project_out(__isl_take isl_map *map,
1194                 enum isl_dim_type type, unsigned first, unsigned n);
1195         __isl_give isl_basic_set *isl_basic_map_domain(
1196                 __isl_take isl_basic_map *bmap);
1197         __isl_give isl_basic_set *isl_basic_map_range(
1198                 __isl_take isl_basic_map *bmap);
1199         __isl_give isl_set *isl_map_domain(
1200                 __isl_take isl_map *bmap);
1201         __isl_give isl_set *isl_map_range(
1202                 __isl_take isl_map *map);
1203         __isl_give isl_union_set *isl_union_map_domain(
1204                 __isl_take isl_union_map *umap);
1205         __isl_give isl_union_set *isl_union_map_range(
1206                 __isl_take isl_union_map *umap);
1207
1208         __isl_give isl_basic_map *isl_basic_map_domain_map(
1209                 __isl_take isl_basic_map *bmap);
1210         __isl_give isl_basic_map *isl_basic_map_range_map(
1211                 __isl_take isl_basic_map *bmap);
1212         __isl_give isl_map *isl_map_domain_map(__isl_take isl_map *map);
1213         __isl_give isl_map *isl_map_range_map(__isl_take isl_map *map);
1214         __isl_give isl_union_map *isl_union_map_domain_map(
1215                 __isl_take isl_union_map *umap);
1216         __isl_give isl_union_map *isl_union_map_range_map(
1217                 __isl_take isl_union_map *umap);
1218
1219 The functions above construct a (basic, regular or union) relation
1220 that maps (a wrapped version of) the input relation to its domain or range.
1221
1222 =item * Identity
1223
1224         __isl_give isl_map *isl_set_identity(
1225                 __isl_take isl_set *set);
1226         __isl_give isl_union_map *isl_union_set_identity(
1227                 __isl_take isl_union_set *uset);
1228
1229 Construct an identity relation on the given (union) set.
1230
1231 =item * Deltas
1232
1233         __isl_give isl_basic_set *isl_basic_map_deltas(
1234                 __isl_take isl_basic_map *bmap);
1235         __isl_give isl_set *isl_map_deltas(__isl_take isl_map *map);
1236         __isl_give isl_union_set *isl_union_map_deltas(
1237                 __isl_take isl_union_map *umap);
1238
1239 These functions return a (basic) set containing the differences
1240 between image elements and corresponding domain elements in the input.
1241
1242 =item * Coalescing
1243
1244 Simplify the representation of a set or relation by trying
1245 to combine pairs of basic sets or relations into a single
1246 basic set or relation.
1247
1248         __isl_give isl_set *isl_set_coalesce(__isl_take isl_set *set);
1249         __isl_give isl_map *isl_map_coalesce(__isl_take isl_map *map);
1250         __isl_give isl_union_set *isl_union_set_coalesce(
1251                 __isl_take isl_union_set *uset);
1252         __isl_give isl_union_map *isl_union_map_coalesce(
1253                 __isl_take isl_union_map *umap);
1254
1255 =item * Convex hull
1256
1257         __isl_give isl_basic_set *isl_set_convex_hull(
1258                 __isl_take isl_set *set);
1259         __isl_give isl_basic_map *isl_map_convex_hull(
1260                 __isl_take isl_map *map);
1261
1262 If the input set or relation has any existentially quantified
1263 variables, then the result of these operations is currently undefined.
1264
1265 =item * Simple hull
1266
1267         __isl_give isl_basic_set *isl_set_simple_hull(
1268                 __isl_take isl_set *set);
1269         __isl_give isl_basic_map *isl_map_simple_hull(
1270                 __isl_take isl_map *map);
1271
1272 These functions compute a single basic set or relation
1273 that contains the whole input set or relation.
1274 In particular, the output is described by translates
1275 of the constraints describing the basic sets or relations in the input.
1276
1277 =begin latex
1278
1279 (See \autoref{s:simple hull}.)
1280
1281 =end latex
1282
1283 =item * Affine hull
1284
1285         __isl_give isl_basic_set *isl_basic_set_affine_hull(
1286                 __isl_take isl_basic_set *bset);
1287         __isl_give isl_basic_set *isl_set_affine_hull(
1288                 __isl_take isl_set *set);
1289         __isl_give isl_union_set *isl_union_set_affine_hull(
1290                 __isl_take isl_union_set *uset);
1291         __isl_give isl_basic_map *isl_basic_map_affine_hull(
1292                 __isl_take isl_basic_map *bmap);
1293         __isl_give isl_basic_map *isl_map_affine_hull(
1294                 __isl_take isl_map *map);
1295         __isl_give isl_union_map *isl_union_map_affine_hull(
1296                 __isl_take isl_union_map *umap);
1297
1298 In case of union sets and relations, the affine hull is computed
1299 per space.
1300
1301 =item * Polyhedral hull
1302
1303         __isl_give isl_basic_set *isl_set_polyhedral_hull(
1304                 __isl_take isl_set *set);
1305         __isl_give isl_basic_map *isl_map_polyhedral_hull(
1306                 __isl_take isl_map *map);
1307         __isl_give isl_union_set *isl_union_set_polyhedral_hull(
1308                 __isl_take isl_union_set *uset);
1309         __isl_give isl_union_map *isl_union_map_polyhedral_hull(
1310                 __isl_take isl_union_map *umap);
1311
1312 These functions compute a single basic set or relation
1313 not involving any existentially quantified variables
1314 that contains the whole input set or relation.
1315 In case of union sets and relations, the polyhedral hull is computed
1316 per space.
1317
1318 =item * Power
1319
1320         __isl_give isl_map *isl_map_power(__isl_take isl_map *map,
1321                 unsigned param, int *exact);
1322
1323 Compute a parametric representation for all positive powers I<k> of C<map>.
1324 The power I<k> is equated to the parameter at position C<param>.
1325 The result may be an overapproximation.  If the result is exact,
1326 then C<*exact> is set to C<1>.
1327 The current implementation only produces exact results for particular
1328 cases of piecewise translations (i.e., piecewise uniform dependences).
1329
1330 =item * Transitive closure
1331
1332         __isl_give isl_map *isl_map_transitive_closure(
1333                 __isl_take isl_map *map, int *exact);
1334         __isl_give isl_union_map *isl_union_map_transitive_closure(
1335                 __isl_take isl_union_map *umap, int *exact);
1336
1337 Compute the transitive closure of C<map>.
1338 The result may be an overapproximation.  If the result is known to be exact,
1339 then C<*exact> is set to C<1>.
1340 The current implementation only produces exact results for particular
1341 cases of piecewise translations (i.e., piecewise uniform dependences).
1342
1343 =item * Reaching path lengths
1344
1345         __isl_give isl_map *isl_map_reaching_path_lengths(
1346                 __isl_take isl_map *map, int *exact);
1347
1348 Compute a relation that maps each element in the range of C<map>
1349 to the lengths of all paths composed of edges in C<map> that
1350 end up in the given element.
1351 The result may be an overapproximation.  If the result is known to be exact,
1352 then C<*exact> is set to C<1>.
1353 To compute the I<maximal> path length, the resulting relation
1354 should be postprocessed by C<isl_map_lexmax>.
1355 In particular, if the input relation is a dependence relation
1356 (mapping sources to sinks), then the maximal path length corresponds
1357 to the free schedule.
1358 Note, however, that C<isl_map_lexmax> expects the maximum to be
1359 finite, so if the path lengths are unbounded (possibly due to
1360 the overapproximation), then you will get an error message.
1361
1362 =item * Wrapping
1363
1364         __isl_give isl_basic_set *isl_basic_map_wrap(
1365                 __isl_take isl_basic_map *bmap);
1366         __isl_give isl_set *isl_map_wrap(
1367                 __isl_take isl_map *map);
1368         __isl_give isl_union_set *isl_union_map_wrap(
1369                 __isl_take isl_union_map *umap);
1370         __isl_give isl_basic_map *isl_basic_set_unwrap(
1371                 __isl_take isl_basic_set *bset);
1372         __isl_give isl_map *isl_set_unwrap(
1373                 __isl_take isl_set *set);
1374         __isl_give isl_union_map *isl_union_set_unwrap(
1375                 __isl_take isl_union_set *uset);
1376
1377 =item * Flattening
1378
1379 Remove any internal structure of domain (and range) of the given
1380 set or relation.  If there is any such internal structure in the input,
1381 then the name of the space is also removed.
1382
1383         __isl_give isl_set *isl_set_flatten(
1384                 __isl_take isl_set *set);
1385         __isl_give isl_map *isl_map_flatten(
1386                 __isl_take isl_map *map);
1387
1388         __isl_give isl_map *isl_set_flatten_map(
1389                 __isl_take isl_set *set);
1390
1391 The function above constructs a relation
1392 that maps the input set to a flattened version of the set.
1393
1394 =item * Dimension manipulation
1395
1396         __isl_give isl_set *isl_set_add_dims(
1397                 __isl_take isl_set *set,
1398                 enum isl_dim_type type, unsigned n);
1399         __isl_give isl_map *isl_map_add_dims(
1400                 __isl_take isl_map *map,
1401                 enum isl_dim_type type, unsigned n);
1402
1403 It is usually not advisable to directly change the (input or output)
1404 space of a set or a relation as this removes the name and the internal
1405 structure of the space.  However, the above functions can be useful
1406 to add new parameters.
1407
1408 =back
1409
1410 =head2 Binary Operations
1411
1412 The two arguments of a binary operation not only need to live
1413 in the same C<isl_ctx>, they currently also need to have
1414 the same (number of) parameters.
1415
1416 =head3 Basic Operations
1417
1418 =over
1419
1420 =item * Intersection
1421
1422         __isl_give isl_basic_set *isl_basic_set_intersect(
1423                 __isl_take isl_basic_set *bset1,
1424                 __isl_take isl_basic_set *bset2);
1425         __isl_give isl_set *isl_set_intersect(
1426                 __isl_take isl_set *set1,
1427                 __isl_take isl_set *set2);
1428         __isl_give isl_union_set *isl_union_set_intersect(
1429                 __isl_take isl_union_set *uset1,
1430                 __isl_take isl_union_set *uset2);
1431         __isl_give isl_basic_map *isl_basic_map_intersect_domain(
1432                 __isl_take isl_basic_map *bmap,
1433                 __isl_take isl_basic_set *bset);
1434         __isl_give isl_basic_map *isl_basic_map_intersect_range(
1435                 __isl_take isl_basic_map *bmap,
1436                 __isl_take isl_basic_set *bset);
1437         __isl_give isl_basic_map *isl_basic_map_intersect(
1438                 __isl_take isl_basic_map *bmap1,
1439                 __isl_take isl_basic_map *bmap2);
1440         __isl_give isl_map *isl_map_intersect_domain(
1441                 __isl_take isl_map *map,
1442                 __isl_take isl_set *set);
1443         __isl_give isl_map *isl_map_intersect_range(
1444                 __isl_take isl_map *map,
1445                 __isl_take isl_set *set);
1446         __isl_give isl_map *isl_map_intersect(
1447                 __isl_take isl_map *map1,
1448                 __isl_take isl_map *map2);
1449         __isl_give isl_union_map *isl_union_map_intersect_domain(
1450                 __isl_take isl_union_map *umap,
1451                 __isl_take isl_union_set *uset);
1452         __isl_give isl_union_map *isl_union_map_intersect_range(
1453                 __isl_take isl_union_map *umap,
1454                 __isl_take isl_union_set *uset);
1455         __isl_give isl_union_map *isl_union_map_intersect(
1456                 __isl_take isl_union_map *umap1,
1457                 __isl_take isl_union_map *umap2);
1458
1459 =item * Union
1460
1461         __isl_give isl_set *isl_basic_set_union(
1462                 __isl_take isl_basic_set *bset1,
1463                 __isl_take isl_basic_set *bset2);
1464         __isl_give isl_map *isl_basic_map_union(
1465                 __isl_take isl_basic_map *bmap1,
1466                 __isl_take isl_basic_map *bmap2);
1467         __isl_give isl_set *isl_set_union(
1468                 __isl_take isl_set *set1,
1469                 __isl_take isl_set *set2);
1470         __isl_give isl_map *isl_map_union(
1471                 __isl_take isl_map *map1,
1472                 __isl_take isl_map *map2);
1473         __isl_give isl_union_set *isl_union_set_union(
1474                 __isl_take isl_union_set *uset1,
1475                 __isl_take isl_union_set *uset2);
1476         __isl_give isl_union_map *isl_union_map_union(
1477                 __isl_take isl_union_map *umap1,
1478                 __isl_take isl_union_map *umap2);
1479
1480 =item * Set difference
1481
1482         __isl_give isl_set *isl_set_subtract(
1483                 __isl_take isl_set *set1,
1484                 __isl_take isl_set *set2);
1485         __isl_give isl_map *isl_map_subtract(
1486                 __isl_take isl_map *map1,
1487                 __isl_take isl_map *map2);
1488         __isl_give isl_union_set *isl_union_set_subtract(
1489                 __isl_take isl_union_set *uset1,
1490                 __isl_take isl_union_set *uset2);
1491         __isl_give isl_union_map *isl_union_map_subtract(
1492                 __isl_take isl_union_map *umap1,
1493                 __isl_take isl_union_map *umap2);
1494
1495 =item * Application
1496
1497         __isl_give isl_basic_set *isl_basic_set_apply(
1498                 __isl_take isl_basic_set *bset,
1499                 __isl_take isl_basic_map *bmap);
1500         __isl_give isl_set *isl_set_apply(
1501                 __isl_take isl_set *set,
1502                 __isl_take isl_map *map);
1503         __isl_give isl_union_set *isl_union_set_apply(
1504                 __isl_take isl_union_set *uset,
1505                 __isl_take isl_union_map *umap);
1506         __isl_give isl_basic_map *isl_basic_map_apply_domain(
1507                 __isl_take isl_basic_map *bmap1,
1508                 __isl_take isl_basic_map *bmap2);
1509         __isl_give isl_basic_map *isl_basic_map_apply_range(
1510                 __isl_take isl_basic_map *bmap1,
1511                 __isl_take isl_basic_map *bmap2);
1512         __isl_give isl_map *isl_map_apply_domain(
1513                 __isl_take isl_map *map1,
1514                 __isl_take isl_map *map2);
1515         __isl_give isl_union_map *isl_union_map_apply_domain(
1516                 __isl_take isl_union_map *umap1,
1517                 __isl_take isl_union_map *umap2);
1518         __isl_give isl_map *isl_map_apply_range(
1519                 __isl_take isl_map *map1,
1520                 __isl_take isl_map *map2);
1521         __isl_give isl_union_map *isl_union_map_apply_range(
1522                 __isl_take isl_union_map *umap1,
1523                 __isl_take isl_union_map *umap2);
1524
1525 =item * Simplification
1526
1527         __isl_give isl_basic_set *isl_basic_set_gist(
1528                 __isl_take isl_basic_set *bset,
1529                 __isl_take isl_basic_set *context);
1530         __isl_give isl_set *isl_set_gist(__isl_take isl_set *set,
1531                 __isl_take isl_set *context);
1532         __isl_give isl_union_set *isl_union_set_gist(
1533                 __isl_take isl_union_set *uset,
1534                 __isl_take isl_union_set *context);
1535         __isl_give isl_basic_map *isl_basic_map_gist(
1536                 __isl_take isl_basic_map *bmap,
1537                 __isl_take isl_basic_map *context);
1538         __isl_give isl_map *isl_map_gist(__isl_take isl_map *map,
1539                 __isl_take isl_map *context);
1540         __isl_give isl_union_map *isl_union_map_gist(
1541                 __isl_take isl_union_map *umap,
1542                 __isl_take isl_union_map *context);
1543
1544 The gist operation returns a set or relation that has the
1545 same intersection with the context as the input set or relation.
1546 Any implicit equality in the intersection is made explicit in the result,
1547 while all inequalities that are redundant with respect to the intersection
1548 are removed.
1549 In case of union sets and relations, the gist operation is performed
1550 per space.
1551
1552 =back
1553
1554 =head3 Lexicographic Optimization
1555
1556 Given a (basic) set C<set> (or C<bset>) and a zero-dimensional domain C<dom>,
1557 the following functions
1558 compute a set that contains the lexicographic minimum or maximum
1559 of the elements in C<set> (or C<bset>) for those values of the parameters
1560 that satisfy C<dom>.
1561 If C<empty> is not C<NULL>, then C<*empty> is assigned a set
1562 that contains the parameter values in C<dom> for which C<set> (or C<bset>)
1563 has no elements.
1564 In other words, the union of the parameter values
1565 for which the result is non-empty and of C<*empty>
1566 is equal to C<dom>.
1567
1568         __isl_give isl_set *isl_basic_set_partial_lexmin(
1569                 __isl_take isl_basic_set *bset,
1570                 __isl_take isl_basic_set *dom,
1571                 __isl_give isl_set **empty);
1572         __isl_give isl_set *isl_basic_set_partial_lexmax(
1573                 __isl_take isl_basic_set *bset,
1574                 __isl_take isl_basic_set *dom,
1575                 __isl_give isl_set **empty);
1576         __isl_give isl_set *isl_set_partial_lexmin(
1577                 __isl_take isl_set *set, __isl_take isl_set *dom,
1578                 __isl_give isl_set **empty);
1579         __isl_give isl_set *isl_set_partial_lexmax(
1580                 __isl_take isl_set *set, __isl_take isl_set *dom,
1581                 __isl_give isl_set **empty);
1582
1583 Given a (basic) set C<set> (or C<bset>), the following functions simply
1584 return a set containing the lexicographic minimum or maximum
1585 of the elements in C<set> (or C<bset>).
1586 In case of union sets, the optimum is computed per space.
1587
1588         __isl_give isl_set *isl_basic_set_lexmin(
1589                 __isl_take isl_basic_set *bset);
1590         __isl_give isl_set *isl_basic_set_lexmax(
1591                 __isl_take isl_basic_set *bset);
1592         __isl_give isl_set *isl_set_lexmin(
1593                 __isl_take isl_set *set);
1594         __isl_give isl_set *isl_set_lexmax(
1595                 __isl_take isl_set *set);
1596         __isl_give isl_union_set *isl_union_set_lexmin(
1597                 __isl_take isl_union_set *uset);
1598         __isl_give isl_union_set *isl_union_set_lexmax(
1599                 __isl_take isl_union_set *uset);
1600
1601 Given a (basic) relation C<map> (or C<bmap>) and a domain C<dom>,
1602 the following functions
1603 compute a relation that maps each element of C<dom>
1604 to the single lexicographic minimum or maximum
1605 of the elements that are associated to that same
1606 element in C<map> (or C<bmap>).
1607 If C<empty> is not C<NULL>, then C<*empty> is assigned a set
1608 that contains the elements in C<dom> that do not map
1609 to any elements in C<map> (or C<bmap>).
1610 In other words, the union of the domain of the result and of C<*empty>
1611 is equal to C<dom>.
1612
1613         __isl_give isl_map *isl_basic_map_partial_lexmax(
1614                 __isl_take isl_basic_map *bmap,
1615                 __isl_take isl_basic_set *dom,
1616                 __isl_give isl_set **empty);
1617         __isl_give isl_map *isl_basic_map_partial_lexmin(
1618                 __isl_take isl_basic_map *bmap,
1619                 __isl_take isl_basic_set *dom,
1620                 __isl_give isl_set **empty);
1621         __isl_give isl_map *isl_map_partial_lexmax(
1622                 __isl_take isl_map *map, __isl_take isl_set *dom,
1623                 __isl_give isl_set **empty);
1624         __isl_give isl_map *isl_map_partial_lexmin(
1625                 __isl_take isl_map *map, __isl_take isl_set *dom,
1626                 __isl_give isl_set **empty);
1627
1628 Given a (basic) map C<map> (or C<bmap>), the following functions simply
1629 return a map mapping each element in the domain of
1630 C<map> (or C<bmap>) to the lexicographic minimum or maximum
1631 of all elements associated to that element.
1632 In case of union relations, the optimum is computed per space.
1633
1634         __isl_give isl_map *isl_basic_map_lexmin(
1635                 __isl_take isl_basic_map *bmap);
1636         __isl_give isl_map *isl_basic_map_lexmax(
1637                 __isl_take isl_basic_map *bmap);
1638         __isl_give isl_map *isl_map_lexmin(
1639                 __isl_take isl_map *map);
1640         __isl_give isl_map *isl_map_lexmax(
1641                 __isl_take isl_map *map);
1642         __isl_give isl_union_map *isl_union_map_lexmin(
1643                 __isl_take isl_union_map *umap);
1644         __isl_give isl_union_map *isl_union_map_lexmax(
1645                 __isl_take isl_union_map *umap);
1646
1647 =head2 Matrices
1648
1649 Matrices can be created, copied and freed using the following functions.
1650
1651         #include <isl_mat.h>
1652         __isl_give isl_mat *isl_mat_alloc(struct isl_ctx *ctx,
1653                 unsigned n_row, unsigned n_col);
1654         __isl_give isl_mat *isl_mat_copy(__isl_keep isl_mat *mat);
1655         void isl_mat_free(__isl_take isl_mat *mat);
1656
1657 Note that the elements of a newly created matrix may have arbitrary values.
1658 The elements can be changed and inspected using the following functions.
1659
1660         int isl_mat_rows(__isl_keep isl_mat *mat);
1661         int isl_mat_cols(__isl_keep isl_mat *mat);
1662         int isl_mat_get_element(__isl_keep isl_mat *mat,
1663                 int row, int col, isl_int *v);
1664         __isl_give isl_mat *isl_mat_set_element(__isl_take isl_mat *mat,
1665                 int row, int col, isl_int v);
1666
1667 C<isl_mat_get_element> will return a negative value if anything went wrong.
1668 In that case, the value of C<*v> is undefined.
1669
1670 The following function can be used to compute the (right) inverse
1671 of a matrix, i.e., a matrix such that the product of the original
1672 and the inverse (in that order) is a multiple of the identity matrix.
1673 The input matrix is assumed to be of full row-rank.
1674
1675         __isl_give isl_mat *isl_mat_right_inverse(__isl_take isl_mat *mat);
1676
1677 The following function can be used to compute the (right) kernel
1678 (or null space) of a matrix, i.e., a matrix such that the product of
1679 the original and the kernel (in that order) is the zero matrix.
1680
1681         __isl_give isl_mat *isl_mat_right_kernel(__isl_take isl_mat *mat);
1682
1683 =head2 Points
1684
1685 Points are elements of a set.  They can be used to construct
1686 simple sets (boxes) or they can be used to represent the
1687 individual elements of a set.
1688 The zero point (the origin) can be created using
1689
1690         __isl_give isl_point *isl_point_zero(__isl_take isl_dim *dim);
1691
1692 The coordinates of a point can be inspected, set and changed
1693 using
1694
1695         void isl_point_get_coordinate(__isl_keep isl_point *pnt,
1696                 enum isl_dim_type type, int pos, isl_int *v);
1697         __isl_give isl_point *isl_point_set_coordinate(
1698                 __isl_take isl_point *pnt,
1699                 enum isl_dim_type type, int pos, isl_int v);
1700
1701         __isl_give isl_point *isl_point_add_ui(
1702                 __isl_take isl_point *pnt,
1703                 enum isl_dim_type type, int pos, unsigned val);
1704         __isl_give isl_point *isl_point_sub_ui(
1705                 __isl_take isl_point *pnt,
1706                 enum isl_dim_type type, int pos, unsigned val);
1707
1708 Points can be copied or freed using
1709
1710         __isl_give isl_point *isl_point_copy(
1711                 __isl_keep isl_point *pnt);
1712         void isl_point_free(__isl_take isl_point *pnt);
1713
1714 A singleton set can be created from a point using
1715
1716         __isl_give isl_set *isl_set_from_point(
1717                 __isl_take isl_point *pnt);
1718
1719 and a box can be created from two opposite extremal points using
1720
1721         __isl_give isl_set *isl_set_box_from_points(
1722                 __isl_take isl_point *pnt1,
1723                 __isl_take isl_point *pnt2);
1724
1725 All elements of a B<bounded> (union) set can be enumerated using
1726 the following functions.
1727
1728         int isl_set_foreach_point(__isl_keep isl_set *set,
1729                 int (*fn)(__isl_take isl_point *pnt, void *user),
1730                 void *user);
1731         int isl_union_set_foreach_point(__isl_keep isl_union_set *uset,
1732                 int (*fn)(__isl_take isl_point *pnt, void *user),
1733                 void *user);
1734
1735 The function C<fn> is called for each integer point in
1736 C<set> with as second argument the last argument of
1737 the C<isl_set_foreach_point> call.  The function C<fn>
1738 should return C<0> on success and C<-1> on failure.
1739 In the latter case, C<isl_set_foreach_point> will stop
1740 enumerating and return C<-1> as well.
1741 If the enumeration is performed successfully and to completion,
1742 then C<isl_set_foreach_point> returns C<0>.
1743
1744 To obtain a single point of a (basic) set, use
1745
1746         __isl_give isl_point *isl_basic_set_sample_point(
1747                 __isl_take isl_basic_set *bset);
1748         __isl_give isl_point *isl_set_sample_point(
1749                 __isl_take isl_set *set);
1750
1751 If C<set> does not contain any (integer) points, then the
1752 resulting point will be ``void'', a property that can be
1753 tested using
1754
1755         int isl_point_is_void(__isl_keep isl_point *pnt);
1756
1757 =head2 Piecewise Quasipolynomials
1758
1759 A piecewise quasipolynomial is a particular kind of function that maps
1760 a parametric point to a rational value.
1761 More specifically, a quasipolynomial is a polynomial expression in greatest
1762 integer parts of affine expressions of parameters and variables.
1763 A piecewise quasipolynomial is a subdivision of a given parametric
1764 domain into disjoint cells with a quasipolynomial associated to
1765 each cell.  The value of the piecewise quasipolynomial at a given
1766 point is the value of the quasipolynomial associated to the cell
1767 that contains the point.  Outside of the union of cells,
1768 the value is assumed to be zero.
1769 For example, the piecewise quasipolynomial
1770
1771         [n] -> { [x] -> ((1 + n) - x) : x <= n and x >= 0 }
1772
1773 maps C<x> to C<1 + n - x> for values of C<x> between C<0> and C<n>.
1774 A given piecewise quasipolynomial has a fixed domain dimension.
1775 Union piecewise quasipolynomials are used to contain piecewise quasipolynomials
1776 defined over different domains.
1777 Piecewise quasipolynomials are mainly used by the C<barvinok>
1778 library for representing the number of elements in a parametric set or map.
1779 For example, the piecewise quasipolynomial above represents
1780 the number of points in the map
1781
1782         [n] -> { [x] -> [y] : x,y >= 0 and 0 <= x + y <= n }
1783
1784 =head3 Printing (Piecewise) Quasipolynomials
1785
1786 Quasipolynomials and piecewise quasipolynomials can be printed
1787 using the following functions.
1788
1789         __isl_give isl_printer *isl_printer_print_qpolynomial(
1790                 __isl_take isl_printer *p,
1791                 __isl_keep isl_qpolynomial *qp);
1792
1793         __isl_give isl_printer *isl_printer_print_pw_qpolynomial(
1794                 __isl_take isl_printer *p,
1795                 __isl_keep isl_pw_qpolynomial *pwqp);
1796
1797         __isl_give isl_printer *isl_printer_print_union_pw_qpolynomial(
1798                 __isl_take isl_printer *p,
1799                 __isl_keep isl_union_pw_qpolynomial *upwqp);
1800
1801 The output format of the printer
1802 needs to be set to either C<ISL_FORMAT_ISL> or C<ISL_FORMAT_C>.
1803 For C<isl_printer_print_union_pw_qpolynomial>, only C<ISL_FORMAT_ISL>
1804 is supported.
1805 In case of printing in C<ISL_FORMAT_C>, the user may want
1806 to set the names of all dimensions
1807
1808         __isl_give isl_qpolynomial *isl_qpolynomial_set_dim_name(
1809                 __isl_take isl_qpolynomial *qp,
1810                 enum isl_dim_type type, unsigned pos,
1811                 const char *s);
1812         __isl_give isl_pw_qpolynomial *
1813         isl_pw_qpolynomial_set_dim_name(
1814                 __isl_take isl_pw_qpolynomial *pwqp,
1815                 enum isl_dim_type type, unsigned pos,
1816                 const char *s);
1817
1818 =head3 Creating New (Piecewise) Quasipolynomials
1819
1820 Some simple quasipolynomials can be created using the following functions.
1821 More complicated quasipolynomials can be created by applying
1822 operations such as addition and multiplication
1823 on the resulting quasipolynomials
1824
1825         __isl_give isl_qpolynomial *isl_qpolynomial_zero(
1826                 __isl_take isl_dim *dim);
1827         __isl_give isl_qpolynomial *isl_qpolynomial_one(
1828                 __isl_take isl_dim *dim);
1829         __isl_give isl_qpolynomial *isl_qpolynomial_infty(
1830                 __isl_take isl_dim *dim);
1831         __isl_give isl_qpolynomial *isl_qpolynomial_neginfty(
1832                 __isl_take isl_dim *dim);
1833         __isl_give isl_qpolynomial *isl_qpolynomial_nan(
1834                 __isl_take isl_dim *dim);
1835         __isl_give isl_qpolynomial *isl_qpolynomial_rat_cst(
1836                 __isl_take isl_dim *dim,
1837                 const isl_int n, const isl_int d);
1838         __isl_give isl_qpolynomial *isl_qpolynomial_div(
1839                 __isl_take isl_div *div);
1840         __isl_give isl_qpolynomial *isl_qpolynomial_var(
1841                 __isl_take isl_dim *dim,
1842                 enum isl_dim_type type, unsigned pos);
1843
1844 The zero piecewise quasipolynomial or a piecewise quasipolynomial
1845 with a single cell can be created using the following functions.
1846 Multiple of these single cell piecewise quasipolynomials can
1847 be combined to create more complicated piecewise quasipolynomials.
1848
1849         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_zero(
1850                 __isl_take isl_dim *dim);
1851         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_alloc(
1852                 __isl_take isl_set *set,
1853                 __isl_take isl_qpolynomial *qp);
1854
1855         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_zero(
1856                 __isl_take isl_dim *dim);
1857         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_from_pw_qpolynomial(
1858                 __isl_take isl_pw_qpolynomial *pwqp);
1859         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_add_pw_qpolynomial(
1860                 __isl_take isl_union_pw_qpolynomial *upwqp,
1861                 __isl_take isl_pw_qpolynomial *pwqp);
1862
1863 Quasipolynomials can be copied and freed again using the following
1864 functions.
1865
1866         __isl_give isl_qpolynomial *isl_qpolynomial_copy(
1867                 __isl_keep isl_qpolynomial *qp);
1868         void isl_qpolynomial_free(__isl_take isl_qpolynomial *qp);
1869
1870         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_copy(
1871                 __isl_keep isl_pw_qpolynomial *pwqp);
1872         void isl_pw_qpolynomial_free(
1873                 __isl_take isl_pw_qpolynomial *pwqp);
1874
1875         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_copy(
1876                 __isl_keep isl_union_pw_qpolynomial *upwqp);
1877         void isl_union_pw_qpolynomial_free(
1878                 __isl_take isl_union_pw_qpolynomial *upwqp);
1879
1880 =head3 Inspecting (Piecewise) Quasipolynomials
1881
1882 To iterate over all piecewise quasipolynomials in a union
1883 piecewise quasipolynomial, use the following function
1884
1885         int isl_union_pw_qpolynomial_foreach_pw_qpolynomial(
1886                 __isl_keep isl_union_pw_qpolynomial *upwqp,
1887                 int (*fn)(__isl_take isl_pw_qpolynomial *pwqp, void *user),
1888                 void *user);
1889
1890 To extract the piecewise quasipolynomial from a union with a given dimension
1891 specification, use
1892
1893         __isl_give isl_pw_qpolynomial *
1894         isl_union_pw_qpolynomial_extract_pw_qpolynomial(
1895                 __isl_keep isl_union_pw_qpolynomial *upwqp,
1896                 __isl_take isl_dim *dim);
1897
1898 To iterate over the cells in a piecewise quasipolynomial,
1899 use either of the following two functions
1900
1901         int isl_pw_qpolynomial_foreach_piece(
1902                 __isl_keep isl_pw_qpolynomial *pwqp,
1903                 int (*fn)(__isl_take isl_set *set,
1904                           __isl_take isl_qpolynomial *qp,
1905                           void *user), void *user);
1906         int isl_pw_qpolynomial_foreach_lifted_piece(
1907                 __isl_keep isl_pw_qpolynomial *pwqp,
1908                 int (*fn)(__isl_take isl_set *set,
1909                           __isl_take isl_qpolynomial *qp,
1910                           void *user), void *user);
1911
1912 As usual, the function C<fn> should return C<0> on success
1913 and C<-1> on failure.  The difference between
1914 C<isl_pw_qpolynomial_foreach_piece> and
1915 C<isl_pw_qpolynomial_foreach_lifted_piece> is that
1916 C<isl_pw_qpolynomial_foreach_lifted_piece> will first
1917 compute unique representations for all existentially quantified
1918 variables and then turn these existentially quantified variables
1919 into extra set variables, adapting the associated quasipolynomial
1920 accordingly.  This means that the C<set> passed to C<fn>
1921 will not have any existentially quantified variables, but that
1922 the dimensions of the sets may be different for different
1923 invocations of C<fn>.
1924
1925 To iterate over all terms in a quasipolynomial,
1926 use
1927
1928         int isl_qpolynomial_foreach_term(
1929                 __isl_keep isl_qpolynomial *qp,
1930                 int (*fn)(__isl_take isl_term *term,
1931                           void *user), void *user);
1932
1933 The terms themselves can be inspected and freed using
1934 these functions
1935
1936         unsigned isl_term_dim(__isl_keep isl_term *term,
1937                 enum isl_dim_type type);
1938         void isl_term_get_num(__isl_keep isl_term *term,
1939                 isl_int *n);
1940         void isl_term_get_den(__isl_keep isl_term *term,
1941                 isl_int *d);
1942         int isl_term_get_exp(__isl_keep isl_term *term,
1943                 enum isl_dim_type type, unsigned pos);
1944         __isl_give isl_div *isl_term_get_div(
1945                 __isl_keep isl_term *term, unsigned pos);
1946         void isl_term_free(__isl_take isl_term *term);
1947
1948 Each term is a product of parameters, set variables and
1949 integer divisions.  The function C<isl_term_get_exp>
1950 returns the exponent of a given dimensions in the given term.
1951 The C<isl_int>s in the arguments of C<isl_term_get_num>
1952 and C<isl_term_get_den> need to have been initialized
1953 using C<isl_int_init> before calling these functions.
1954
1955 =head3 Properties of (Piecewise) Quasipolynomials
1956
1957 To check whether a quasipolynomial is actually a constant,
1958 use the following function.
1959
1960         int isl_qpolynomial_is_cst(__isl_keep isl_qpolynomial *qp,
1961                 isl_int *n, isl_int *d);
1962
1963 If C<qp> is a constant and if C<n> and C<d> are not C<NULL>
1964 then the numerator and denominator of the constant
1965 are returned in C<*n> and C<*d>, respectively.
1966
1967 =head3 Operations on (Piecewise) Quasipolynomials
1968
1969         __isl_give isl_qpolynomial *isl_qpolynomial_neg(
1970                 __isl_take isl_qpolynomial *qp);
1971         __isl_give isl_qpolynomial *isl_qpolynomial_add(
1972                 __isl_take isl_qpolynomial *qp1,
1973                 __isl_take isl_qpolynomial *qp2);
1974         __isl_give isl_qpolynomial *isl_qpolynomial_sub(
1975                 __isl_take isl_qpolynomial *qp1,
1976                 __isl_take isl_qpolynomial *qp2);
1977         __isl_give isl_qpolynomial *isl_qpolynomial_mul(
1978                 __isl_take isl_qpolynomial *qp1,
1979                 __isl_take isl_qpolynomial *qp2);
1980
1981         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_add(
1982                 __isl_take isl_pw_qpolynomial *pwqp1,
1983                 __isl_take isl_pw_qpolynomial *pwqp2);
1984         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_sub(
1985                 __isl_take isl_pw_qpolynomial *pwqp1,
1986                 __isl_take isl_pw_qpolynomial *pwqp2);
1987         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_add_disjoint(
1988                 __isl_take isl_pw_qpolynomial *pwqp1,
1989                 __isl_take isl_pw_qpolynomial *pwqp2);
1990         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_neg(
1991                 __isl_take isl_pw_qpolynomial *pwqp);
1992         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_mul(
1993                 __isl_take isl_pw_qpolynomial *pwqp1,
1994                 __isl_take isl_pw_qpolynomial *pwqp2);
1995
1996         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_add(
1997                 __isl_take isl_union_pw_qpolynomial *upwqp1,
1998                 __isl_take isl_union_pw_qpolynomial *upwqp2);
1999         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_sub(
2000                 __isl_take isl_union_pw_qpolynomial *upwqp1,
2001                 __isl_take isl_union_pw_qpolynomial *upwqp2);
2002         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_mul(
2003                 __isl_take isl_union_pw_qpolynomial *upwqp1,
2004                 __isl_take isl_union_pw_qpolynomial *upwqp2);
2005
2006         __isl_give isl_qpolynomial *isl_pw_qpolynomial_eval(
2007                 __isl_take isl_pw_qpolynomial *pwqp,
2008                 __isl_take isl_point *pnt);
2009
2010         __isl_give isl_qpolynomial *isl_union_pw_qpolynomial_eval(
2011                 __isl_take isl_union_pw_qpolynomial *upwqp,
2012                 __isl_take isl_point *pnt);
2013
2014         __isl_give isl_set *isl_pw_qpolynomial_domain(
2015                 __isl_take isl_pw_qpolynomial *pwqp);
2016         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_intersect_domain(
2017                 __isl_take isl_pw_qpolynomial *pwpq,
2018                 __isl_take isl_set *set);
2019
2020         __isl_give isl_union_set *isl_union_pw_qpolynomial_domain(
2021                 __isl_take isl_union_pw_qpolynomial *upwqp);
2022         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_intersect_domain(
2023                 __isl_take isl_union_pw_qpolynomial *upwpq,
2024                 __isl_take isl_union_set *uset);
2025
2026         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_coalesce(
2027                 __isl_take isl_union_pw_qpolynomial *upwqp);
2028
2029         __isl_give isl_pw_qpolynomial *isl_pw_qpolynomial_gist(
2030                 __isl_take isl_pw_qpolynomial *pwqp,
2031                 __isl_take isl_set *context);
2032
2033         __isl_give isl_union_pw_qpolynomial *isl_union_pw_qpolynomial_gist(
2034                 __isl_take isl_union_pw_qpolynomial *upwqp,
2035                 __isl_take isl_union_set *context);
2036
2037 The gist operation applies the gist operation to each of
2038 the cells in the domain of the input piecewise quasipolynomial.
2039 The context is also exploited
2040 to simplify the quasipolynomials associated to each cell.
2041
2042 =head2 Bounds on Piecewise Quasipolynomials and Piecewise Quasipolynomial Reductions
2043
2044 A piecewise quasipolynomial reduction is a piecewise
2045 reduction (or fold) of quasipolynomials.
2046 In particular, the reduction can be maximum or a minimum.
2047 The objects are mainly used to represent the result of
2048 an upper or lower bound on a quasipolynomial over its domain,
2049 i.e., as the result of the following function.
2050
2051         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_bound(
2052                 __isl_take isl_pw_qpolynomial *pwqp,
2053                 enum isl_fold type, int *tight);
2054
2055         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_bound(
2056                 __isl_take isl_union_pw_qpolynomial *upwqp,
2057                 enum isl_fold type, int *tight);
2058
2059 The C<type> argument may be either C<isl_fold_min> or C<isl_fold_max>.
2060 If C<tight> is not C<NULL>, then C<*tight> is set to C<1>
2061 is the returned bound is known be tight, i.e., for each value
2062 of the parameters there is at least
2063 one element in the domain that reaches the bound.
2064 If the domain of C<pwqp> is not wrapping, then the bound is computed
2065 over all elements in that domain and the result has a purely parametric
2066 domain.  If the domain of C<pwqp> is wrapping, then the bound is
2067 computed over the range of the wrapped relation.  The domain of the
2068 wrapped relation becomes the domain of the result.
2069
2070 A (piecewise) quasipolynomial reduction can be copied or freed using the
2071 following functions.
2072
2073         __isl_give isl_qpolynomial_fold *isl_qpolynomial_fold_copy(
2074                 __isl_keep isl_qpolynomial_fold *fold);
2075         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_copy(
2076                 __isl_keep isl_pw_qpolynomial_fold *pwf);
2077         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_copy(
2078                 __isl_keep isl_union_pw_qpolynomial_fold *upwf);
2079         void isl_qpolynomial_fold_free(
2080                 __isl_take isl_qpolynomial_fold *fold);
2081         void isl_pw_qpolynomial_fold_free(
2082                 __isl_take isl_pw_qpolynomial_fold *pwf);
2083         void isl_union_pw_qpolynomial_fold_free(
2084                 __isl_take isl_union_pw_qpolynomial_fold *upwf);
2085
2086 =head3 Printing Piecewise Quasipolynomial Reductions
2087
2088 Piecewise quasipolynomial reductions can be printed
2089 using the following function.
2090
2091         __isl_give isl_printer *isl_printer_print_pw_qpolynomial_fold(
2092                 __isl_take isl_printer *p,
2093                 __isl_keep isl_pw_qpolynomial_fold *pwf);
2094         __isl_give isl_printer *isl_printer_print_union_pw_qpolynomial_fold(
2095                 __isl_take isl_printer *p,
2096                 __isl_keep isl_union_pw_qpolynomial_fold *upwf);
2097
2098 For C<isl_printer_print_pw_qpolynomial_fold>,
2099 output format of the printer
2100 needs to be set to either C<ISL_FORMAT_ISL> or C<ISL_FORMAT_C>.
2101 For C<isl_printer_print_union_pw_qpolynomial_fold>,
2102 output format of the printer
2103 needs to be set to C<ISL_FORMAT_ISL>.
2104 In case of printing in C<ISL_FORMAT_C>, the user may want
2105 to set the names of all dimensions
2106
2107         __isl_give isl_pw_qpolynomial_fold *
2108         isl_pw_qpolynomial_fold_set_dim_name(
2109                 __isl_take isl_pw_qpolynomial_fold *pwf,
2110                 enum isl_dim_type type, unsigned pos,
2111                 const char *s);
2112
2113 =head3 Inspecting (Piecewise) Quasipolynomial Reductions
2114
2115 To iterate over all piecewise quasipolynomial reductions in a union
2116 piecewise quasipolynomial reduction, use the following function
2117
2118         int isl_union_pw_qpolynomial_fold_foreach_pw_qpolynomial_fold(
2119                 __isl_keep isl_union_pw_qpolynomial_fold *upwf,
2120                 int (*fn)(__isl_take isl_pw_qpolynomial_fold *pwf,
2121                             void *user), void *user);
2122
2123 To iterate over the cells in a piecewise quasipolynomial reduction,
2124 use either of the following two functions
2125
2126         int isl_pw_qpolynomial_fold_foreach_piece(
2127                 __isl_keep isl_pw_qpolynomial_fold *pwf,
2128                 int (*fn)(__isl_take isl_set *set,
2129                           __isl_take isl_qpolynomial_fold *fold,
2130                           void *user), void *user);
2131         int isl_pw_qpolynomial_fold_foreach_lifted_piece(
2132                 __isl_keep isl_pw_qpolynomial_fold *pwf,
2133                 int (*fn)(__isl_take isl_set *set,
2134                           __isl_take isl_qpolynomial_fold *fold,
2135                           void *user), void *user);
2136
2137 See L<Inspecting (Piecewise) Quasipolynomials> for an explanation
2138 of the difference between these two functions.
2139
2140 To iterate over all quasipolynomials in a reduction, use
2141
2142         int isl_qpolynomial_fold_foreach_qpolynomial(
2143                 __isl_keep isl_qpolynomial_fold *fold,
2144                 int (*fn)(__isl_take isl_qpolynomial *qp,
2145                           void *user), void *user);
2146
2147 =head3 Operations on Piecewise Quasipolynomial Reductions
2148
2149         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_add(
2150                 __isl_take isl_pw_qpolynomial_fold *pwf1,
2151                 __isl_take isl_pw_qpolynomial_fold *pwf2);
2152
2153         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_fold(
2154                 __isl_take isl_pw_qpolynomial_fold *pwf1,
2155                 __isl_take isl_pw_qpolynomial_fold *pwf2);
2156
2157         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_fold(
2158                 __isl_take isl_union_pw_qpolynomial_fold *upwf1,
2159                 __isl_take isl_union_pw_qpolynomial_fold *upwf2);
2160
2161         __isl_give isl_qpolynomial *isl_pw_qpolynomial_fold_eval(
2162                 __isl_take isl_pw_qpolynomial_fold *pwf,
2163                 __isl_take isl_point *pnt);
2164
2165         __isl_give isl_qpolynomial *isl_union_pw_qpolynomial_fold_eval(
2166                 __isl_take isl_union_pw_qpolynomial_fold *upwf,
2167                 __isl_take isl_point *pnt);
2168
2169         __isl_give isl_union_set *isl_union_pw_qpolynomial_fold_domain(
2170                 __isl_take isl_union_pw_qpolynomial_fold *upwf);
2171         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_intersect_domain(
2172                 __isl_take isl_union_pw_qpolynomial_fold *upwf,
2173                 __isl_take isl_union_set *uset);
2174
2175         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_coalesce(
2176                 __isl_take isl_pw_qpolynomial_fold *pwf);
2177
2178         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_coalesce(
2179                 __isl_take isl_union_pw_qpolynomial_fold *upwf);
2180
2181         __isl_give isl_pw_qpolynomial_fold *isl_pw_qpolynomial_fold_gist(
2182                 __isl_take isl_pw_qpolynomial_fold *pwf,
2183                 __isl_take isl_set *context);
2184
2185         __isl_give isl_union_pw_qpolynomial_fold *isl_union_pw_qpolynomial_fold_gist(
2186                 __isl_take isl_union_pw_qpolynomial_fold *upwf,
2187                 __isl_take isl_union_set *context);
2188
2189 The gist operation applies the gist operation to each of
2190 the cells in the domain of the input piecewise quasipolynomial reduction.
2191 In future, the operation will also exploit the context
2192 to simplify the quasipolynomial reductions associated to each cell.
2193
2194         __isl_give isl_pw_qpolynomial_fold *
2195         isl_map_apply_pw_qpolynomial_fold(
2196                 __isl_take isl_map *map,
2197                 __isl_take isl_pw_qpolynomial_fold *pwf,
2198                 int *tight);
2199         __isl_give isl_union_pw_qpolynomial_fold *
2200         isl_union_map_apply_union_pw_qpolynomial_fold(
2201                 __isl_take isl_union_map *umap,
2202                 __isl_take isl_union_pw_qpolynomial_fold *upwf,
2203                 int *tight);
2204
2205 These functions
2206 compose the given map with the given piecewise quasipolynomial reduction.
2207 That is, compute a bound (of the same type as C<pwf> or C<upwf> itself)
2208 over all elements in the intersection of the range of the map
2209 and the domain of the piecewise quasipolynomial reduction
2210 as a function of an element in the domain of the map.
2211
2212 =head2 Dependence Analysis
2213
2214 C<isl> contains specialized functionality for performing
2215 array dataflow analysis.  That is, given a I<sink> access relation
2216 and a collection of possible I<source> access relations,
2217 C<isl> can compute relations that describe
2218 for each iteration of the sink access, which iteration
2219 of which of the source access relations was the last
2220 to access the same data element before the given iteration
2221 of the sink access.
2222 To compute standard flow dependences, the sink should be
2223 a read, while the sources should be writes.
2224 If any of the source accesses are marked as being I<may>
2225 accesses, then there will be a dependence to the last
2226 I<must> access B<and> to any I<may> access that follows
2227 this last I<must> access.
2228 In particular, if I<all> sources are I<may> accesses,
2229 then memory based dependence analysis is performed.
2230 If, on the other hand, all sources are I<must> accesses,
2231 then value based dependence analysis is performed.
2232
2233         #include <isl_flow.h>
2234
2235         typedef int (*isl_access_level_before)(void *first, void *second);
2236
2237         __isl_give isl_access_info *isl_access_info_alloc(
2238                 __isl_take isl_map *sink,
2239                 void *sink_user, isl_access_level_before fn,
2240                 int max_source);
2241         __isl_give isl_access_info *isl_access_info_add_source(
2242                 __isl_take isl_access_info *acc,
2243                 __isl_take isl_map *source, int must,
2244                 void *source_user);
2245         void isl_access_info_free(__isl_take isl_access_info *acc);
2246
2247         __isl_give isl_flow *isl_access_info_compute_flow(
2248                 __isl_take isl_access_info *acc);
2249
2250         int isl_flow_foreach(__isl_keep isl_flow *deps,
2251                 int (*fn)(__isl_take isl_map *dep, int must,
2252                           void *dep_user, void *user),
2253                 void *user);
2254         __isl_give isl_set *isl_flow_get_no_source(
2255                 __isl_keep isl_flow *deps, int must);
2256         void isl_flow_free(__isl_take isl_flow *deps);
2257
2258 The function C<isl_access_info_compute_flow> performs the actual
2259 dependence analysis.  The other functions are used to construct
2260 the input for this function or to read off the output.
2261
2262 The input is collected in an C<isl_access_info>, which can
2263 be created through a call to C<isl_access_info_alloc>.
2264 The arguments to this functions are the sink access relation
2265 C<sink>, a token C<sink_user> used to identify the sink
2266 access to the user, a callback function for specifying the
2267 relative order of source and sink accesses, and the number
2268 of source access relations that will be added.
2269 The callback function has type C<int (*)(void *first, void *second)>.
2270 The function is called with two user supplied tokens identifying
2271 either a source or the sink and it should return the shared nesting
2272 level and the relative order of the two accesses.
2273 In particular, let I<n> be the number of loops shared by
2274 the two accesses.  If C<first> precedes C<second> textually,
2275 then the function should return I<2 * n + 1>; otherwise,
2276 it should return I<2 * n>.
2277 The sources can be added to the C<isl_access_info> by performing
2278 (at most) C<max_source> calls to C<isl_access_info_add_source>.
2279 C<must> indicates whether the source is a I<must> access
2280 or a I<may> access.  Note that a multi-valued access relation
2281 should only be marked I<must> if every iteration in the domain
2282 of the relation accesses I<all> elements in its image.
2283 The C<source_user> token is again used to identify
2284 the source access.  The range of the source access relation
2285 C<source> should have the same dimension as the range
2286 of the sink access relation.
2287 The C<isl_access_info_free> function should usually not be
2288 called explicitly, because it is called implicitly by
2289 C<isl_access_info_compute_flow>.
2290
2291 The result of the dependence analysis is collected in an
2292 C<isl_flow>.  There may be elements in the domain of
2293 the sink access for which no preceding source access could be
2294 found or for which all preceding sources are I<may> accesses.
2295 The sets of these elements can be obtained through
2296 calls to C<isl_flow_get_no_source>, the first with C<must> set
2297 and the second with C<must> unset.
2298 In the case of standard flow dependence analysis,
2299 with the sink a read and the sources I<must> writes,
2300 the first set corresponds to the reads from uninitialized
2301 array elements and the second set is empty.
2302 The actual flow dependences can be extracted using
2303 C<isl_flow_foreach>.  This function will call the user-specified
2304 callback function C<fn> for each B<non-empty> dependence between
2305 a source and the sink.  The callback function is called
2306 with four arguments, the actual flow dependence relation
2307 mapping source iterations to sink iterations, a boolean that
2308 indicates whether it is a I<must> or I<may> dependence, a token
2309 identifying the source and an additional C<void *> with value
2310 equal to the third argument of the C<isl_flow_foreach> call.
2311 A dependence is marked I<must> if it originates from a I<must>
2312 source and if it is not followed by any I<may> sources.
2313
2314 After finishing with an C<isl_flow>, the user should call
2315 C<isl_flow_free> to free all associated memory.
2316
2317 A higher-level interface to dependence analysis is provided
2318 by the following function.
2319
2320         #include <isl_flow.h>
2321
2322         int isl_union_map_compute_flow(__isl_take isl_union_map *sink,
2323                 __isl_take isl_union_map *must_source,
2324                 __isl_take isl_union_map *may_source,
2325                 __isl_take isl_union_map *schedule,
2326                 __isl_give isl_union_map **must_dep,
2327                 __isl_give isl_union_map **may_dep,
2328                 __isl_give isl_union_set **must_no_source,
2329                 __isl_give isl_union_set **may_no_source);
2330
2331 The arrays are identified by the tuple names of the ranges
2332 of the accesses.  The iteration domains by the tuple names
2333 of the domains of the accesses and of the schedule.
2334 The relative order of the iteration domains is given by the
2335 schedule.  Any of C<must_dep>, C<may_dep>, C<must_no_source>
2336 or C<may_no_source> may be C<NULL>, but a C<NULL> value for
2337 any of the other arguments is treated as an error.
2338
2339 =head2 Parametric Vertex Enumeration
2340
2341 The parametric vertex enumeration described in this section
2342 is mainly intended to be used internally and by the C<barvinok>
2343 library.
2344
2345         #include <isl_vertices.h>
2346         __isl_give isl_vertices *isl_basic_set_compute_vertices(
2347                 __isl_keep isl_basic_set *bset);
2348
2349 The function C<isl_basic_set_compute_vertices> performs the
2350 actual computation of the parametric vertices and the chamber
2351 decomposition and store the result in an C<isl_vertices> object.
2352 This information can be queried by either iterating over all
2353 the vertices or iterating over all the chambers or cells
2354 and then iterating over all vertices that are active on the chamber.
2355
2356         int isl_vertices_foreach_vertex(
2357                 __isl_keep isl_vertices *vertices,
2358                 int (*fn)(__isl_take isl_vertex *vertex, void *user),
2359                 void *user);
2360
2361         int isl_vertices_foreach_cell(
2362                 __isl_keep isl_vertices *vertices,
2363                 int (*fn)(__isl_take isl_cell *cell, void *user),
2364                 void *user);
2365         int isl_cell_foreach_vertex(__isl_keep isl_cell *cell,
2366                 int (*fn)(__isl_take isl_vertex *vertex, void *user),
2367                 void *user);
2368
2369 Other operations that can be performed on an C<isl_vertices> object are
2370 the following.
2371
2372         isl_ctx *isl_vertices_get_ctx(
2373                 __isl_keep isl_vertices *vertices);
2374         int isl_vertices_get_n_vertices(
2375                 __isl_keep isl_vertices *vertices);
2376         void isl_vertices_free(__isl_take isl_vertices *vertices);
2377
2378 Vertices can be inspected and destroyed using the following functions.
2379
2380         isl_ctx *isl_vertex_get_ctx(__isl_keep isl_vertex *vertex);
2381         int isl_vertex_get_id(__isl_keep isl_vertex *vertex);
2382         __isl_give isl_basic_set *isl_vertex_get_domain(
2383                 __isl_keep isl_vertex *vertex);
2384         __isl_give isl_basic_set *isl_vertex_get_expr(
2385                 __isl_keep isl_vertex *vertex);
2386         void isl_vertex_free(__isl_take isl_vertex *vertex);
2387
2388 C<isl_vertex_get_expr> returns a singleton parametric set describing
2389 the vertex, while C<isl_vertex_get_domain> returns the activity domain
2390 of the vertex.
2391 Note that C<isl_vertex_get_domain> and C<isl_vertex_get_expr> return
2392 B<rational> basic sets, so they should mainly be used for inspection
2393 and should not be mixed with integer sets.
2394
2395 Chambers can be inspected and destroyed using the following functions.
2396
2397         isl_ctx *isl_cell_get_ctx(__isl_keep isl_cell *cell);
2398         __isl_give isl_basic_set *isl_cell_get_domain(
2399                 __isl_keep isl_cell *cell);
2400         void isl_cell_free(__isl_take isl_cell *cell);
2401
2402 =head1 Applications
2403
2404 Although C<isl> is mainly meant to be used as a library,
2405 it also contains some basic applications that use some
2406 of the functionality of C<isl>.
2407 The input may be specified in either the L<isl format>
2408 or the L<PolyLib format>.
2409
2410 =head2 C<isl_polyhedron_sample>
2411
2412 C<isl_polyhedron_sample> takes a polyhedron as input and prints
2413 an integer element of the polyhedron, if there is any.
2414 The first column in the output is the denominator and is always
2415 equal to 1.  If the polyhedron contains no integer points,
2416 then a vector of length zero is printed.
2417
2418 =head2 C<isl_pip>
2419
2420 C<isl_pip> takes the same input as the C<example> program
2421 from the C<piplib> distribution, i.e., a set of constraints
2422 on the parameters, a line containing only -1 and finally a set
2423 of constraints on a parametric polyhedron.
2424 The coefficients of the parameters appear in the last columns
2425 (but before the final constant column).
2426 The output is the lexicographic minimum of the parametric polyhedron.
2427 As C<isl> currently does not have its own output format, the output
2428 is just a dump of the internal state.
2429
2430 =head2 C<isl_polyhedron_minimize>
2431
2432 C<isl_polyhedron_minimize> computes the minimum of some linear
2433 or affine objective function over the integer points in a polyhedron.
2434 If an affine objective function
2435 is given, then the constant should appear in the last column.
2436
2437 =head2 C<isl_polytope_scan>
2438
2439 Given a polytope, C<isl_polytope_scan> prints
2440 all integer points in the polytope.
2441
2442 =head1 C<isl-polylib>
2443
2444 The C<isl-polylib> library provides the following functions for converting
2445 between C<isl> objects and C<PolyLib> objects.
2446 The library is distributed separately for licensing reasons.
2447
2448         #include <isl_set_polylib.h>
2449         __isl_give isl_basic_set *isl_basic_set_new_from_polylib(
2450                 Polyhedron *P, __isl_take isl_dim *dim);
2451         Polyhedron *isl_basic_set_to_polylib(
2452                 __isl_keep isl_basic_set *bset);
2453         __isl_give isl_set *isl_set_new_from_polylib(Polyhedron *D,
2454                 __isl_take isl_dim *dim);
2455         Polyhedron *isl_set_to_polylib(__isl_keep isl_set *set);
2456
2457         #include <isl_map_polylib.h>
2458         __isl_give isl_basic_map *isl_basic_map_new_from_polylib(
2459                 Polyhedron *P, __isl_take isl_dim *dim);
2460         __isl_give isl_map *isl_map_new_from_polylib(Polyhedron *D,
2461                 __isl_take isl_dim *dim);
2462         Polyhedron *isl_basic_map_to_polylib(
2463                 __isl_keep isl_basic_map *bmap);
2464         Polyhedron *isl_map_to_polylib(__isl_keep isl_map *map);