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