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