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