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