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