?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_aff.c: fix typo in comment
[isl.git] / isl_aff.c
bloba531bf8c3d589c922c9175155cace8067b3e9db0
1 /*
2 * Copyright 2011 INRIA Saclay
3 * Copyright 2011 Sven Verdoolaege
4 * Copyright 2012 Ecole Normale Superieure
5 *
6 * Use of this software is governed by the MIT license
7 *
8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * 91893 Orsay, France
11 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
12 */
13
14 #include <isl_ctx_private.h>
15 #define ISL_DIM_H
16 #include <isl_map_private.h>
17 #include <isl_union_map_private.h>
18 #include <isl_aff_private.h>
19 #include <isl_space_private.h>
20 #include <isl_local_space_private.h>
21 #include <isl_mat_private.h>
22 #include <isl_list_private.h>
23 #include <isl/constraint.h>
24 #include <isl/seq.h>
25 #include <isl/set.h>
26 #include <isl_config.h>
27
28 __isl_give isl_aff *isl_aff_alloc_vec(__isl_take isl_local_space *ls,
29 __isl_take isl_vec *v)
30 {
31 isl_aff *aff;
32
33 if (!ls || !v)
34 goto error;
35
36 aff = isl_calloc_type(v->ctx, struct isl_aff);
37 if (!aff)
38 goto error;
39
40 aff->ref = 1;
41 aff->ls = ls;
42 aff->v = v;
43
44 return aff;
45 error:
46 isl_local_space_free(ls);
47 isl_vec_free(v);
48 return NULL;
49 }
50
51 __isl_give isl_aff *isl_aff_alloc(__isl_take isl_local_space *ls)
52 {
53 isl_ctx *ctx;
54 isl_vec *v;
55 unsigned total;
56
57 if (!ls)
58 return NULL;
59
60 ctx = isl_local_space_get_ctx(ls);
61 if (!isl_local_space_divs_known(ls))
62 isl_die(ctx, isl_error_invalid, "local space has unknown divs",
63 goto error);
64 if (!isl_local_space_is_set(ls))
65 isl_die(ctx, isl_error_invalid,
66 "domain of affine expression should be a set",
67 goto error);
68
69 total = isl_local_space_dim(ls, isl_dim_all);
70 v = isl_vec_alloc(ctx, 1 + 1 + total);
71 return isl_aff_alloc_vec(ls, v);
72 error:
73 isl_local_space_free(ls);
74 return NULL;
75 }
76
77 __isl_give isl_aff *isl_aff_zero_on_domain(__isl_take isl_local_space *ls)
78 {
79 isl_aff *aff;
80
81 aff = isl_aff_alloc(ls);
82 if (!aff)
83 return NULL;
84
85 isl_int_set_si(aff->v->el[0], 1);
86 isl_seq_clr(aff->v->el + 1, aff->v->size - 1);
87
88 return aff;
89 }
90
91 __isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff)
92 {
93 if (!aff)
94 return NULL;
95
96 aff->ref++;
97 return aff;
98 }
99
100 __isl_give isl_aff *isl_aff_dup(__isl_keep isl_aff *aff)
101 {
102 if (!aff)
103 return NULL;
104
105 return isl_aff_alloc_vec(isl_local_space_copy(aff->ls),
106 isl_vec_copy(aff->v));
107 }
108
109 __isl_give isl_aff *isl_aff_cow(__isl_take isl_aff *aff)
110 {
111 if (!aff)
112 return NULL;
113
114 if (aff->ref == 1)
115 return aff;
116 aff->ref--;
117 return isl_aff_dup(aff);
118 }
119
120 void *isl_aff_free(__isl_take isl_aff *aff)
121 {
122 if (!aff)
123 return NULL;
124
125 if (--aff->ref > 0)
126 return NULL;
127
128 isl_local_space_free(aff->ls);
129 isl_vec_free(aff->v);
130
131 free(aff);
132
133 return NULL;
134 }
135
136 isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff)
137 {
138 return aff ? isl_local_space_get_ctx(aff->ls) : NULL;
139 }
140
141 /* Externally, an isl_aff has a map space, but internally, the
142 * ls field corresponds to the domain of that space.
143 */
144 int isl_aff_dim(__isl_keep isl_aff *aff, enum isl_dim_type type)
145 {
146 if (!aff)
147 return 0;
148 if (type == isl_dim_out)
149 return 1;
150 if (type == isl_dim_in)
151 type = isl_dim_set;
152 return isl_local_space_dim(aff->ls, type);
153 }
154
155 __isl_give isl_space *isl_aff_get_domain_space(__isl_keep isl_aff *aff)
156 {
157 return aff ? isl_local_space_get_space(aff->ls) : NULL;
158 }
159
160 __isl_give isl_space *isl_aff_get_space(__isl_keep isl_aff *aff)
161 {
162 isl_space *space;
163 if (!aff)
164 return NULL;
165 space = isl_local_space_get_space(aff->ls);
166 space = isl_space_from_domain(space);
167 space = isl_space_add_dims(space, isl_dim_out, 1);
168 return space;
169 }
170
171 __isl_give isl_local_space *isl_aff_get_domain_local_space(
172 __isl_keep isl_aff *aff)
173 {
174 return aff ? isl_local_space_copy(aff->ls) : NULL;
175 }
176
177 __isl_give isl_local_space *isl_aff_get_local_space(__isl_keep isl_aff *aff)
178 {
179 isl_local_space *ls;
180 if (!aff)
181 return NULL;
182 ls = isl_local_space_copy(aff->ls);
183 ls = isl_local_space_from_domain(ls);
184 ls = isl_local_space_add_dims(ls, isl_dim_out, 1);
185 return ls;
186 }
187
188 /* Externally, an isl_aff has a map space, but internally, the
189 * ls field corresponds to the domain of that space.
190 */
191 const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff,
192 enum isl_dim_type type, unsigned pos)
193 {
194 if (!aff)
195 return NULL;
196 if (type == isl_dim_out)
197 return NULL;
198 if (type == isl_dim_in)
199 type = isl_dim_set;
200 return isl_local_space_get_dim_name(aff->ls, type, pos);
201 }
202
203 __isl_give isl_aff *isl_aff_reset_domain_space(__isl_take isl_aff *aff,
204 __isl_take isl_space *dim)
205 {
206 aff = isl_aff_cow(aff);
207 if (!aff || !dim)
208 goto error;
209
210 aff->ls = isl_local_space_reset_space(aff->ls, dim);
211 if (!aff->ls)
212 return isl_aff_free(aff);
213
214 return aff;
215 error:
216 isl_aff_free(aff);
217 isl_space_free(dim);
218 return NULL;
219 }
220
221 /* Reset the space of "aff". This function is called from isl_pw_templ.c
222 * and doesn't know if the space of an element object is represented
223 * directly or through its domain. It therefore passes along both.
224 */
225 __isl_give isl_aff *isl_aff_reset_space_and_domain(__isl_take isl_aff *aff,
226 __isl_take isl_space *space, __isl_take isl_space *domain)
227 {
228 isl_space_free(space);
229 return isl_aff_reset_domain_space(aff, domain);
230 }
231
232 /* Reorder the coefficients of the affine expression based
233 * on the given reodering.
234 * The reordering r is assumed to have been extended with the local
235 * variables.
236 */
237 static __isl_give isl_vec *vec_reorder(__isl_take isl_vec *vec,
238 __isl_take isl_reordering *r, int n_div)
239 {
240 isl_vec *res;
241 int i;
242
243 if (!vec || !r)
244 goto error;
245
246 res = isl_vec_alloc(vec->ctx,
247 2 + isl_space_dim(r->dim, isl_dim_all) + n_div);
248 isl_seq_cpy(res->el, vec->el, 2);
249 isl_seq_clr(res->el + 2, res->size - 2);
250 for (i = 0; i < r->len; ++i)
251 isl_int_set(res->el[2 + r->pos[i]], vec->el[2 + i]);
252
253 isl_reordering_free(r);
254 isl_vec_free(vec);
255 return res;
256 error:
257 isl_vec_free(vec);
258 isl_reordering_free(r);
259 return NULL;
260 }
261
262 /* Reorder the dimensions of the domain of "aff" according
263 * to the given reordering.
264 */
265 __isl_give isl_aff *isl_aff_realign_domain(__isl_take isl_aff *aff,
266 __isl_take isl_reordering *r)
267 {
268 aff = isl_aff_cow(aff);
269 if (!aff)
270 goto error;
271
272 r = isl_reordering_extend(r, aff->ls->div->n_row);
273 aff->v = vec_reorder(aff->v, isl_reordering_copy(r),
274 aff->ls->div->n_row);
275 aff->ls = isl_local_space_realign(aff->ls, r);
276
277 if (!aff->v || !aff->ls)
278 return isl_aff_free(aff);
279
280 return aff;
281 error:
282 isl_aff_free(aff);
283 isl_reordering_free(r);
284 return NULL;
285 }
286
287 __isl_give isl_aff *isl_aff_align_params(__isl_take isl_aff *aff,
288 __isl_take isl_space *model)
289 {
290 if (!aff || !model)
291 goto error;
292
293 if (!isl_space_match(aff->ls->dim, isl_dim_param,
294 model, isl_dim_param)) {
295 isl_reordering *exp;
296
297 model = isl_space_drop_dims(model, isl_dim_in,
298 0, isl_space_dim(model, isl_dim_in));
299 model = isl_space_drop_dims(model, isl_dim_out,
300 0, isl_space_dim(model, isl_dim_out));
301 exp = isl_parameter_alignment_reordering(aff->ls->dim, model);
302 exp = isl_reordering_extend_space(exp,
303 isl_aff_get_domain_space(aff));
304 aff = isl_aff_realign_domain(aff, exp);
305 }
306
307 isl_space_free(model);
308 return aff;
309 error:
310 isl_space_free(model);
311 isl_aff_free(aff);
312 return NULL;
313 }
314
315 int isl_aff_plain_is_zero(__isl_keep isl_aff *aff)
316 {
317 if (!aff)
318 return -1;
319
320 return isl_seq_first_non_zero(aff->v->el + 1, aff->v->size - 1) < 0;
321 }
322
323 int isl_aff_plain_is_equal(__isl_keep isl_aff *aff1, __isl_keep isl_aff *aff2)
324 {
325 int equal;
326
327 if (!aff1 || !aff2)
328 return -1;
329
330 equal = isl_local_space_is_equal(aff1->ls, aff2->ls);
331 if (equal < 0 || !equal)
332 return equal;
333
334 return isl_vec_is_equal(aff1->v, aff2->v);
335 }
336
337 int isl_aff_get_denominator(__isl_keep isl_aff *aff, isl_int *v)
338 {
339 if (!aff)
340 return -1;
341 isl_int_set(*v, aff->v->el[0]);
342 return 0;
343 }
344
345 int isl_aff_get_constant(__isl_keep isl_aff *aff, isl_int *v)
346 {
347 if (!aff)
348 return -1;
349 isl_int_set(*v, aff->v->el[1]);
350 return 0;
351 }
352
353 int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
354 enum isl_dim_type type, int pos, isl_int *v)
355 {
356 if (!aff)
357 return -1;
358
359 if (type == isl_dim_out)
360 isl_die(aff->v->ctx, isl_error_invalid,
361 "output/set dimension does not have a coefficient",
362 return -1);
363 if (type == isl_dim_in)
364 type = isl_dim_set;
365
366 if (pos >= isl_local_space_dim(aff->ls, type))
367 isl_die(aff->v->ctx, isl_error_invalid,
368 "position out of bounds", return -1);
369
370 pos += isl_local_space_offset(aff->ls, type);
371 isl_int_set(*v, aff->v->el[1 + pos]);
372
373 return 0;
374 }
375
376 __isl_give isl_aff *isl_aff_set_denominator(__isl_take isl_aff *aff, isl_int v)
377 {
378 aff = isl_aff_cow(aff);
379 if (!aff)
380 return NULL;
381
382 aff->v = isl_vec_cow(aff->v);
383 if (!aff->v)
384 return isl_aff_free(aff);
385
386 isl_int_set(aff->v->el[0], v);
387
388 return aff;
389 }
390
391 __isl_give isl_aff *isl_aff_set_constant(__isl_take isl_aff *aff, isl_int v)
392 {
393 aff = isl_aff_cow(aff);
394 if (!aff)
395 return NULL;
396
397 aff->v = isl_vec_cow(aff->v);
398 if (!aff->v)
399 return isl_aff_free(aff);
400
401 isl_int_set(aff->v->el[1], v);
402
403 return aff;
404 }
405
406 __isl_give isl_aff *isl_aff_add_constant(__isl_take isl_aff *aff, isl_int v)
407 {
408 if (isl_int_is_zero(v))
409 return aff;
410
411 aff = isl_aff_cow(aff);
412 if (!aff)
413 return NULL;
414
415 aff->v = isl_vec_cow(aff->v);
416 if (!aff->v)
417 return isl_aff_free(aff);
418
419 isl_int_addmul(aff->v->el[1], aff->v->el[0], v);
420
421 return aff;
422 }
423
424 __isl_give isl_aff *isl_aff_add_constant_si(__isl_take isl_aff *aff, int v)
425 {
426 isl_int t;
427
428 isl_int_init(t);
429 isl_int_set_si(t, v);
430 aff = isl_aff_add_constant(aff, t);
431 isl_int_clear(t);
432
433 return aff;
434 }
435
436 /* Add "v" to the numerator of the constant term of "aff".
437 */
438 __isl_give isl_aff *isl_aff_add_constant_num(__isl_take isl_aff *aff, isl_int v)
439 {
440 if (isl_int_is_zero(v))
441 return aff;
442
443 aff = isl_aff_cow(aff);
444 if (!aff)
445 return NULL;
446
447 aff->v = isl_vec_cow(aff->v);
448 if (!aff->v)
449 return isl_aff_free(aff);
450
451 isl_int_add(aff->v->el[1], aff->v->el[1], v);
452
453 return aff;
454 }
455
456 /* Add "v" to the numerator of the constant term of "aff".
457 */
458 __isl_give isl_aff *isl_aff_add_constant_num_si(__isl_take isl_aff *aff, int v)
459 {
460 isl_int t;
461
462 if (v == 0)
463 return aff;
464
465 isl_int_init(t);
466 isl_int_set_si(t, v);
467 aff = isl_aff_add_constant_num(aff, t);
468 isl_int_clear(t);
469
470 return aff;
471 }
472
473 __isl_give isl_aff *isl_aff_set_constant_si(__isl_take isl_aff *aff, int v)
474 {
475 aff = isl_aff_cow(aff);
476 if (!aff)
477 return NULL;
478
479 aff->v = isl_vec_cow(aff->v);
480 if (!aff->v)
481 return isl_aff_free(aff);
482
483 isl_int_set_si(aff->v->el[1], v);
484
485 return aff;
486 }
487
488 __isl_give isl_aff *isl_aff_set_coefficient(__isl_take isl_aff *aff,
489 enum isl_dim_type type, int pos, isl_int v)
490 {
491 if (!aff)
492 return NULL;
493
494 if (type == isl_dim_out)
495 isl_die(aff->v->ctx, isl_error_invalid,
496 "output/set dimension does not have a coefficient",
497 return isl_aff_free(aff));
498 if (type == isl_dim_in)
499 type = isl_dim_set;
500
501 if (pos >= isl_local_space_dim(aff->ls, type))
502 isl_die(aff->v->ctx, isl_error_invalid,
503 "position out of bounds", return isl_aff_free(aff));
504
505 aff = isl_aff_cow(aff);
506 if (!aff)
507 return NULL;
508
509 aff->v = isl_vec_cow(aff->v);
510 if (!aff->v)
511 return isl_aff_free(aff);
512
513 pos += isl_local_space_offset(aff->ls, type);
514 isl_int_set(aff->v->el[1 + pos], v);
515
516 return aff;
517 }
518
519 __isl_give isl_aff *isl_aff_set_coefficient_si(__isl_take isl_aff *aff,
520 enum isl_dim_type type, int pos, int v)
521 {
522 if (!aff)
523 return NULL;
524
525 if (type == isl_dim_out)
526 isl_die(aff->v->ctx, isl_error_invalid,
527 "output/set dimension does not have a coefficient",
528 return isl_aff_free(aff));
529 if (type == isl_dim_in)
530 type = isl_dim_set;
531
532 if (pos >= isl_local_space_dim(aff->ls, type))
533 isl_die(aff->v->ctx, isl_error_invalid,
534 "position out of bounds", return isl_aff_free(aff));
535
536 aff = isl_aff_cow(aff);
537 if (!aff)
538 return NULL;
539
540 aff->v = isl_vec_cow(aff->v);
541 if (!aff->v)
542 return isl_aff_free(aff);
543
544 pos += isl_local_space_offset(aff->ls, type);
545 isl_int_set_si(aff->v->el[1 + pos], v);
546
547 return aff;
548 }
549
550 __isl_give isl_aff *isl_aff_add_coefficient(__isl_take isl_aff *aff,
551 enum isl_dim_type type, int pos, isl_int v)
552 {
553 if (!aff)
554 return NULL;
555
556 if (type == isl_dim_out)
557 isl_die(aff->v->ctx, isl_error_invalid,
558 "output/set dimension does not have a coefficient",
559 return isl_aff_free(aff));
560 if (type == isl_dim_in)
561 type = isl_dim_set;
562
563 if (pos >= isl_local_space_dim(aff->ls, type))
564 isl_die(aff->v->ctx, isl_error_invalid,
565 "position out of bounds", return isl_aff_free(aff));
566
567 aff = isl_aff_cow(aff);
568 if (!aff)
569 return NULL;
570
571 aff->v = isl_vec_cow(aff->v);
572 if (!aff->v)
573 return isl_aff_free(aff);
574
575 pos += isl_local_space_offset(aff->ls, type);
576 isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v);
577
578 return aff;
579 }
580
581 __isl_give isl_aff *isl_aff_add_coefficient_si(__isl_take isl_aff *aff,
582 enum isl_dim_type type, int pos, int v)
583 {
584 isl_int t;
585
586 isl_int_init(t);
587 isl_int_set_si(t, v);
588 aff = isl_aff_add_coefficient(aff, type, pos, t);
589 isl_int_clear(t);
590
591 return aff;
592 }
593
594 __isl_give isl_aff *isl_aff_get_div(__isl_keep isl_aff *aff, int pos)
595 {
596 if (!aff)
597 return NULL;
598
599 return isl_local_space_get_div(aff->ls, pos);
600 }
601
602 __isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff)
603 {
604 aff = isl_aff_cow(aff);
605 if (!aff)
606 return NULL;
607 aff->v = isl_vec_cow(aff->v);
608 if (!aff->v)
609 return isl_aff_free(aff);
610
611 isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1);
612
613 return aff;
614 }
615
616 /* Remove divs from the local space that do not appear in the affine
617 * expression.
618 * We currently only remove divs at the end.
619 * Some intermediate divs may also not appear directly in the affine
620 * expression, but we would also need to check that no other divs are
621 * defined in terms of them.
622 */
623 __isl_give isl_aff *isl_aff_remove_unused_divs( __isl_take isl_aff *aff)
624 {
625 int pos;
626 int off;
627 int n;
628
629 if (!aff)
630 return NULL;
631
632 n = isl_local_space_dim(aff->ls, isl_dim_div);
633 off = isl_local_space_offset(aff->ls, isl_dim_div);
634
635 pos = isl_seq_last_non_zero(aff->v->el + 1 + off, n) + 1;
636 if (pos == n)
637 return aff;
638
639 aff = isl_aff_cow(aff);
640 if (!aff)
641 return NULL;
642
643 aff->ls = isl_local_space_drop_dims(aff->ls, isl_dim_div, pos, n - pos);
644 aff->v = isl_vec_drop_els(aff->v, 1 + off + pos, n - pos);
645 if (!aff->ls || !aff->v)
646 return isl_aff_free(aff);
647
648 return aff;
649 }
650
651 __isl_give isl_aff *isl_aff_normalize(__isl_take isl_aff *aff)
652 {
653 if (!aff)
654 return NULL;
655 aff->v = isl_vec_normalize(aff->v);
656 if (!aff->v)
657 return isl_aff_free(aff);
658 aff = isl_aff_remove_unused_divs(aff);
659 return aff;
660 }
661
662 /* Given f, return floor(f).
663 * If f is an integer expression, then just return f.
664 * If f is a constant, then return the constant floor(f).
665 * Otherwise, if f = g/m, write g = q m + r,
666 * create a new div d = [r/m] and return the expression q + d.
667 * The coefficients in r are taken to lie between -m/2 and m/2.
668 */
669 __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
670 {
671 int i;
672 int size;
673 isl_ctx *ctx;
674 isl_vec *div;
675
676 if (!aff)
677 return NULL;
678
679 if (isl_int_is_one(aff->v->el[0]))
680 return aff;
681
682 aff = isl_aff_cow(aff);
683 if (!aff)
684 return NULL;
685
686 aff->v = isl_vec_cow(aff->v);
687 if (!aff->v)
688 return isl_aff_free(aff);
689
690 if (isl_aff_is_cst(aff)) {
691 isl_int_fdiv_q(aff->v->el[1], aff->v->el[1], aff->v->el[0]);
692 isl_int_set_si(aff->v->el[0], 1);
693 return aff;
694 }
695
696 div = isl_vec_copy(aff->v);
697 div = isl_vec_cow(div);
698 if (!div)
699 return isl_aff_free(aff);
700
701 ctx = isl_aff_get_ctx(aff);
702 isl_int_fdiv_q(aff->v->el[0], aff->v->el[0], ctx->two);
703 for (i = 1; i < aff->v->size; ++i) {
704 isl_int_fdiv_r(div->el[i], div->el[i], div->el[0]);
705 isl_int_fdiv_q(aff->v->el[i], aff->v->el[i], div->el[0]);
706 if (isl_int_gt(div->el[i], aff->v->el[0])) {
707 isl_int_sub(div->el[i], div->el[i], div->el[0]);
708 isl_int_add_ui(aff->v->el[i], aff->v->el[i], 1);
709 }
710 }
711
712 aff->ls = isl_local_space_add_div(aff->ls, div);
713 if (!aff->ls)
714 return isl_aff_free(aff);
715
716 size = aff->v->size;
717 aff->v = isl_vec_extend(aff->v, size + 1);
718 if (!aff->v)
719 return isl_aff_free(aff);
720 isl_int_set_si(aff->v->el[0], 1);
721 isl_int_set_si(aff->v->el[size], 1);
722
723 return aff;
724 }
725
726 /* Compute
727 *
728 * aff mod m = aff - m * floor(aff/m)
729 */
730 __isl_give isl_aff *isl_aff_mod(__isl_take isl_aff *aff, isl_int m)
731 {
732 isl_aff *res;
733
734 res = isl_aff_copy(aff);
735 aff = isl_aff_scale_down(aff, m);
736 aff = isl_aff_floor(aff);
737 aff = isl_aff_scale(aff, m);
738 res = isl_aff_sub(res, aff);
739
740 return res;
741 }
742
743 /* Compute
744 *
745 * pwaff mod m = pwaff - m * floor(pwaff/m)
746 */
747 __isl_give isl_pw_aff *isl_pw_aff_mod(__isl_take isl_pw_aff *pwaff, isl_int m)
748 {
749 isl_pw_aff *res;
750
751 res = isl_pw_aff_copy(pwaff);
752 pwaff = isl_pw_aff_scale_down(pwaff, m);
753 pwaff = isl_pw_aff_floor(pwaff);
754 pwaff = isl_pw_aff_scale(pwaff, m);
755 res = isl_pw_aff_sub(res, pwaff);
756
757 return res;
758 }
759
760 /* Given f, return ceil(f).
761 * If f is an integer expression, then just return f.
762 * Otherwise, create a new div d = [-f] and return the expression -d.
763 */
764 __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
765 {
766 if (!aff)
767 return NULL;
768
769 if (isl_int_is_one(aff->v->el[0]))
770 return aff;
771
772 aff = isl_aff_neg(aff);
773 aff = isl_aff_floor(aff);
774 aff = isl_aff_neg(aff);
775
776 return aff;
777 }
778
779 /* Apply the expansion computed by isl_merge_divs.
780 * The expansion itself is given by "exp" while the resulting
781 * list of divs is given by "div".
782 */
783 __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
784 __isl_take isl_mat *div, int *exp)
785 {
786 int i, j;
787 int old_n_div;
788 int new_n_div;
789 int offset;
790
791 aff = isl_aff_cow(aff);
792 if (!aff || !div)
793 goto error;
794
795 old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
796 new_n_div = isl_mat_rows(div);
797 if (new_n_div < old_n_div)
798 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
799 "not an expansion", goto error);
800
801 aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div);
802 if (!aff->v)
803 goto error;
804
805 offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
806 j = old_n_div - 1;
807 for (i = new_n_div - 1; i >= 0; --i) {
808 if (j >= 0 && exp[j] == i) {
809 if (i != j)
810 isl_int_swap(aff->v->el[offset + i],
811 aff->v->el[offset + j]);
812 j--;
813 } else
814 isl_int_set_si(aff->v->el[offset + i], 0);
815 }
816
817 aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div));
818 if (!aff->ls)
819 goto error;
820 isl_mat_free(div);
821 return aff;
822 error:
823 isl_aff_free(aff);
824 isl_mat_free(div);
825 return NULL;
826 }
827
828 /* Add two affine expressions that live in the same local space.
829 */
830 static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
831 __isl_take isl_aff *aff2)
832 {
833 isl_int gcd, f;
834
835 aff1 = isl_aff_cow(aff1);
836 if (!aff1 || !aff2)
837 goto error;
838
839 aff1->v = isl_vec_cow(aff1->v);
840 if (!aff1->v)
841 goto error;
842
843 isl_int_init(gcd);
844 isl_int_init(f);
845 isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
846 isl_int_divexact(f, aff2->v->el[0], gcd);
847 isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
848 isl_int_divexact(f, aff1->v->el[0], gcd);
849 isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
850 isl_int_divexact(f, aff2->v->el[0], gcd);
851 isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
852 isl_int_clear(f);
853 isl_int_clear(gcd);
854
855 isl_aff_free(aff2);
856 return aff1;
857 error:
858 isl_aff_free(aff1);
859 isl_aff_free(aff2);
860 return NULL;
861 }
862
863 __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
864 __isl_take isl_aff *aff2)
865 {
866 isl_ctx *ctx;
867 int *exp1 = NULL;
868 int *exp2 = NULL;
869 isl_mat *div;
870
871 if (!aff1 || !aff2)
872 goto error;
873
874 ctx = isl_aff_get_ctx(aff1);
875 if (!isl_space_is_equal(aff1->ls->dim, aff2->ls->dim))
876 isl_die(ctx, isl_error_invalid,
877 "spaces don't match", goto error);
878
879 if (aff1->ls->div->n_row == 0 && aff2->ls->div->n_row == 0)
880 return add_expanded(aff1, aff2);
881
882 exp1 = isl_alloc_array(ctx, int, aff1->ls->div->n_row);
883 exp2 = isl_alloc_array(ctx, int, aff2->ls->div->n_row);
884 if (!exp1 || !exp2)
885 goto error;
886
887 div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
888 aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
889 aff2 = isl_aff_expand_divs(aff2, div, exp2);
890 free(exp1);
891 free(exp2);
892
893 return add_expanded(aff1, aff2);
894 error:
895 free(exp1);
896 free(exp2);
897 isl_aff_free(aff1);
898 isl_aff_free(aff2);
899 return NULL;
900 }
901
902 __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
903 __isl_take isl_aff *aff2)
904 {
905 return isl_aff_add(aff1, isl_aff_neg(aff2));
906 }
907
908 __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
909 {
910 isl_int gcd;
911
912 if (isl_int_is_one(f))
913 return aff;
914
915 aff = isl_aff_cow(aff);
916 if (!aff)
917 return NULL;
918 aff->v = isl_vec_cow(aff->v);
919 if (!aff->v)
920 return isl_aff_free(aff);
921
922 isl_int_init(gcd);
923 isl_int_gcd(gcd, aff->v->el[0], f);
924 isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
925 isl_int_divexact(gcd, f, gcd);
926 isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
927 isl_int_clear(gcd);
928
929 return aff;
930 }
931
932 __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
933 {
934 isl_int gcd;
935
936 if (isl_int_is_one(f))
937 return aff;
938
939 aff = isl_aff_cow(aff);
940 if (!aff)
941 return NULL;
942
943 if (isl_int_is_zero(f))
944 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
945 "cannot scale down by zero", return isl_aff_free(aff));
946
947 aff->v = isl_vec_cow(aff->v);
948 if (!aff->v)
949 return isl_aff_free(aff);
950
951 isl_int_init(gcd);
952 isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
953 isl_int_gcd(gcd, gcd, f);
954 isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
955 isl_int_divexact(gcd, f, gcd);
956 isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
957 isl_int_clear(gcd);
958
959 return aff;
960 }
961
962 __isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f)
963 {
964 isl_int v;
965
966 if (f == 1)
967 return aff;
968
969 isl_int_init(v);
970 isl_int_set_ui(v, f);
971 aff = isl_aff_scale_down(aff, v);
972 isl_int_clear(v);
973
974 return aff;
975 }
976
977 __isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff,
978 enum isl_dim_type type, unsigned pos, const char *s)
979 {
980 aff = isl_aff_cow(aff);
981 if (!aff)
982 return NULL;
983 if (type == isl_dim_out)
984 isl_die(aff->v->ctx, isl_error_invalid,
985 "cannot set name of output/set dimension",
986 return isl_aff_free(aff));
987 if (type == isl_dim_in)
988 type = isl_dim_set;
989 aff->ls = isl_local_space_set_dim_name(aff->ls, type, pos, s);
990 if (!aff->ls)
991 return isl_aff_free(aff);
992
993 return aff;
994 }
995
996 __isl_give isl_aff *isl_aff_set_dim_id(__isl_take isl_aff *aff,
997 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
998 {
999 aff = isl_aff_cow(aff);
1000 if (!aff)
1001 return isl_id_free(id);
1002 if (type == isl_dim_out)
1003 isl_die(aff->v->ctx, isl_error_invalid,
1004 "cannot set name of output/set dimension",
1005 goto error);
1006 if (type == isl_dim_in)
1007 type = isl_dim_set;
1008 aff->ls = isl_local_space_set_dim_id(aff->ls, type, pos, id);
1009 if (!aff->ls)
1010 return isl_aff_free(aff);
1011
1012 return aff;
1013 error:
1014 isl_id_free(id);
1015 isl_aff_free(aff);
1016 return NULL;
1017 }
1018
1019 /* Exploit the equalities in "eq" to simplify the affine expression
1020 * and the expressions of the integer divisions in the local space.
1021 * The integer divisions in this local space are assumed to appear
1022 * as regular dimensions in "eq".
1023 */
1024 static __isl_give isl_aff *isl_aff_substitute_equalities_lifted(
1025 __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
1026 {
1027 int i, j;
1028 unsigned total;
1029 unsigned n_div;
1030
1031 if (!eq)
1032 goto error;
1033 if (eq->n_eq == 0) {
1034 isl_basic_set_free(eq);
1035 return aff;
1036 }
1037
1038 aff = isl_aff_cow(aff);
1039 if (!aff)
1040 goto error;
1041
1042 aff->ls = isl_local_space_substitute_equalities(aff->ls,
1043 isl_basic_set_copy(eq));
1044 if (!aff->ls)
1045 goto error;
1046
1047 total = 1 + isl_space_dim(eq->dim, isl_dim_all);
1048 n_div = eq->n_div;
1049 for (i = 0; i < eq->n_eq; ++i) {
1050 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
1051 if (j < 0 || j == 0 || j >= total)
1052 continue;
1053
1054 isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total,
1055 &aff->v->el[0]);
1056 }
1057
1058 isl_basic_set_free(eq);
1059 aff = isl_aff_normalize(aff);
1060 return aff;
1061 error:
1062 isl_basic_set_free(eq);
1063 isl_aff_free(aff);
1064 return NULL;
1065 }
1066
1067 /* Exploit the equalities in "eq" to simplify the affine expression
1068 * and the expressions of the integer divisions in the local space.
1069 */
1070 static __isl_give isl_aff *isl_aff_substitute_equalities(
1071 __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
1072 {
1073 int n_div;
1074
1075 if (!aff || !eq)
1076 goto error;
1077 n_div = isl_local_space_dim(aff->ls, isl_dim_div);
1078 if (n_div > 0)
1079 eq = isl_basic_set_add(eq, isl_dim_set, n_div);
1080 return isl_aff_substitute_equalities_lifted(aff, eq);
1081 error:
1082 isl_basic_set_free(eq);
1083 isl_aff_free(aff);
1084 return NULL;
1085 }
1086
1087 /* Look for equalities among the variables shared by context and aff
1088 * and the integer divisions of aff, if any.
1089 * The equalities are then used to eliminate coefficients and/or integer
1090 * divisions from aff.
1091 */
1092 __isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
1093 __isl_take isl_set *context)
1094 {
1095 isl_basic_set *hull;
1096 int n_div;
1097
1098 if (!aff)
1099 goto error;
1100 n_div = isl_local_space_dim(aff->ls, isl_dim_div);
1101 if (n_div > 0) {
1102 isl_basic_set *bset;
1103 isl_local_space *ls;
1104 context = isl_set_add_dims(context, isl_dim_set, n_div);
1105 ls = isl_aff_get_domain_local_space(aff);
1106 bset = isl_basic_set_from_local_space(ls);
1107 bset = isl_basic_set_lift(bset);
1108 bset = isl_basic_set_flatten(bset);
1109 context = isl_set_intersect(context,
1110 isl_set_from_basic_set(bset));
1111 }
1112
1113 hull = isl_set_affine_hull(context);
1114 return isl_aff_substitute_equalities_lifted(aff, hull);
1115 error:
1116 isl_aff_free(aff);
1117 isl_set_free(context);
1118 return NULL;
1119 }
1120
1121 __isl_give isl_aff *isl_aff_gist_params(__isl_take isl_aff *aff,
1122 __isl_take isl_set *context)
1123 {
1124 isl_set *dom_context = isl_set_universe(isl_aff_get_domain_space(aff));
1125 dom_context = isl_set_intersect_params(dom_context, context);
1126 return isl_aff_gist(aff, dom_context);
1127 }
1128
1129 /* Return a basic set containing those elements in the space
1130 * of aff where it is non-negative.
1131 */
1132 __isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff)
1133 {
1134 isl_constraint *ineq;
1135 isl_basic_set *bset;
1136
1137 ineq = isl_inequality_from_aff(aff);
1138
1139 bset = isl_basic_set_from_constraint(ineq);
1140 bset = isl_basic_set_simplify(bset);
1141 return bset;
1142 }
1143
1144 /* Return a basic set containing those elements in the domain space
1145 * of aff where it is negative.
1146 */
1147 __isl_give isl_basic_set *isl_aff_neg_basic_set(__isl_take isl_aff *aff)
1148 {
1149 aff = isl_aff_neg(aff);
1150 aff = isl_aff_add_constant_num_si(aff, -1);
1151 return isl_aff_nonneg_basic_set(aff);
1152 }
1153
1154 /* Return a basic set containing those elements in the space
1155 * of aff where it is zero.
1156 */
1157 __isl_give isl_basic_set *isl_aff_zero_basic_set(__isl_take isl_aff *aff)
1158 {
1159 isl_constraint *ineq;
1160 isl_basic_set *bset;
1161
1162 ineq = isl_equality_from_aff(aff);
1163
1164 bset = isl_basic_set_from_constraint(ineq);
1165 bset = isl_basic_set_simplify(bset);
1166 return bset;
1167 }
1168
1169 /* Return a basic set containing those elements in the shared space
1170 * of aff1 and aff2 where aff1 is greater than or equal to aff2.
1171 */
1172 __isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1,
1173 __isl_take isl_aff *aff2)
1174 {
1175 aff1 = isl_aff_sub(aff1, aff2);
1176
1177 return isl_aff_nonneg_basic_set(aff1);
1178 }
1179
1180 /* Return a basic set containing those elements in the shared space
1181 * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
1182 */
1183 __isl_give isl_basic_set *isl_aff_le_basic_set(__isl_take isl_aff *aff1,
1184 __isl_take isl_aff *aff2)
1185 {
1186 return isl_aff_ge_basic_set(aff2, aff1);
1187 }
1188
1189 __isl_give isl_aff *isl_aff_add_on_domain(__isl_keep isl_set *dom,
1190 __isl_take isl_aff *aff1, __isl_take isl_aff *aff2)
1191 {
1192 aff1 = isl_aff_add(aff1, aff2);
1193 aff1 = isl_aff_gist(aff1, isl_set_copy(dom));
1194 return aff1;
1195 }
1196
1197 int isl_aff_is_empty(__isl_keep isl_aff *aff)
1198 {
1199 if (!aff)
1200 return -1;
1201
1202 return 0;
1203 }
1204
1205 /* Check whether the given affine expression has non-zero coefficient
1206 * for any dimension in the given range or if any of these dimensions
1207 * appear with non-zero coefficients in any of the integer divisions
1208 * involved in the affine expression.
1209 */
1210 int isl_aff_involves_dims(__isl_keep isl_aff *aff,
1211 enum isl_dim_type type, unsigned first, unsigned n)
1212 {
1213 int i;
1214 isl_ctx *ctx;
1215 int *active = NULL;
1216 int involves = 0;
1217
1218 if (!aff)
1219 return -1;
1220 if (n == 0)
1221 return 0;
1222
1223 ctx = isl_aff_get_ctx(aff);
1224 if (first + n > isl_aff_dim(aff, type))
1225 isl_die(ctx, isl_error_invalid,
1226 "range out of bounds", return -1);
1227
1228 active = isl_local_space_get_active(aff->ls, aff->v->el + 2);
1229 if (!active)
1230 goto error;
1231
1232 first += isl_local_space_offset(aff->ls, type) - 1;
1233 for (i = 0; i < n; ++i)
1234 if (active[first + i]) {
1235 involves = 1;
1236 break;
1237 }
1238
1239 free(active);
1240
1241 return involves;
1242 error:
1243 free(active);
1244 return -1;
1245 }
1246
1247 __isl_give isl_aff *isl_aff_drop_dims(__isl_take isl_aff *aff,
1248 enum isl_dim_type type, unsigned first, unsigned n)
1249 {
1250 isl_ctx *ctx;
1251
1252 if (!aff)
1253 return NULL;
1254 if (type == isl_dim_out)
1255 isl_die(aff->v->ctx, isl_error_invalid,
1256 "cannot drop output/set dimension",
1257 return isl_aff_free(aff));
1258 if (type == isl_dim_in)
1259 type = isl_dim_set;
1260 if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1261 return aff;
1262
1263 ctx = isl_aff_get_ctx(aff);
1264 if (first + n > isl_local_space_dim(aff->ls, type))
1265 isl_die(ctx, isl_error_invalid, "range out of bounds",
1266 return isl_aff_free(aff));
1267
1268 aff = isl_aff_cow(aff);
1269 if (!aff)
1270 return NULL;
1271
1272 aff->ls = isl_local_space_drop_dims(aff->ls, type, first, n);
1273 if (!aff->ls)
1274 return isl_aff_free(aff);
1275
1276 first += 1 + isl_local_space_offset(aff->ls, type);
1277 aff->v = isl_vec_drop_els(aff->v, first, n);
1278 if (!aff->v)
1279 return isl_aff_free(aff);
1280
1281 return aff;
1282 }
1283
1284 /* Project the domain of the affine expression onto its parameter space.
1285 * The affine expression may not involve any of the domain dimensions.
1286 */
1287 __isl_give isl_aff *isl_aff_project_domain_on_params(__isl_take isl_aff *aff)
1288 {
1289 isl_space *space;
1290 unsigned n;
1291 int involves;
1292
1293 n = isl_aff_dim(aff, isl_dim_in);
1294 involves = isl_aff_involves_dims(aff, isl_dim_in, 0, n);
1295 if (involves < 0)
1296 return isl_aff_free(aff);
1297 if (involves)
1298 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
1299 "affine expression involves some of the domain dimensions",
1300 return isl_aff_free(aff));
1301 aff = isl_aff_drop_dims(aff, isl_dim_in, 0, n);
1302 space = isl_aff_get_domain_space(aff);
1303 space = isl_space_params(space);
1304 aff = isl_aff_reset_domain_space(aff, space);
1305 return aff;
1306 }
1307
1308 __isl_give isl_aff *isl_aff_insert_dims(__isl_take isl_aff *aff,
1309 enum isl_dim_type type, unsigned first, unsigned n)
1310 {
1311 isl_ctx *ctx;
1312
1313 if (!aff)
1314 return NULL;
1315 if (type == isl_dim_out)
1316 isl_die(aff->v->ctx, isl_error_invalid,
1317 "cannot insert output/set dimensions",
1318 return isl_aff_free(aff));
1319 if (type == isl_dim_in)
1320 type = isl_dim_set;
1321 if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1322 return aff;
1323
1324 ctx = isl_aff_get_ctx(aff);
1325 if (first > isl_local_space_dim(aff->ls, type))
1326 isl_die(ctx, isl_error_invalid, "position out of bounds",
1327 return isl_aff_free(aff));
1328
1329 aff = isl_aff_cow(aff);
1330 if (!aff)
1331 return NULL;
1332
1333 aff->ls = isl_local_space_insert_dims(aff->ls, type, first, n);
1334 if (!aff->ls)
1335 return isl_aff_free(aff);
1336
1337 first += 1 + isl_local_space_offset(aff->ls, type);
1338 aff->v = isl_vec_insert_zero_els(aff->v, first, n);
1339 if (!aff->v)
1340 return isl_aff_free(aff);
1341
1342 return aff;
1343 }
1344
1345 __isl_give isl_aff *isl_aff_add_dims(__isl_take isl_aff *aff,
1346 enum isl_dim_type type, unsigned n)
1347 {
1348 unsigned pos;
1349
1350 pos = isl_aff_dim(aff, type);
1351
1352 return isl_aff_insert_dims(aff, type, pos, n);
1353 }
1354
1355 __isl_give isl_pw_aff *isl_pw_aff_add_dims(__isl_take isl_pw_aff *pwaff,
1356 enum isl_dim_type type, unsigned n)
1357 {
1358 unsigned pos;
1359
1360 pos = isl_pw_aff_dim(pwaff, type);
1361
1362 return isl_pw_aff_insert_dims(pwaff, type, pos, n);
1363 }
1364
1365 __isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff)
1366 {
1367 isl_set *dom = isl_set_universe(isl_aff_get_domain_space(aff));
1368 return isl_pw_aff_alloc(dom, aff);
1369 }
1370
1371 #undef PW
1372 #define PW isl_pw_aff
1373 #undef EL
1374 #define EL isl_aff
1375 #undef EL_IS_ZERO
1376 #define EL_IS_ZERO is_empty
1377 #undef ZERO
1378 #define ZERO empty
1379 #undef IS_ZERO
1380 #define IS_ZERO is_empty
1381 #undef FIELD
1382 #define FIELD aff
1383 #undef DEFAULT_IS_ZERO
1384 #define DEFAULT_IS_ZERO 0
1385
1386 #define NO_EVAL
1387 #define NO_OPT
1388 #define NO_MOVE_DIMS
1389 #define NO_LIFT
1390 #define NO_MORPH
1391
1392 #include <isl_pw_templ.c>
1393
1394 static __isl_give isl_set *align_params_pw_pw_set_and(
1395 __isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2,
1396 __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1397 __isl_take isl_pw_aff *pwaff2))
1398 {
1399 if (!pwaff1 || !pwaff2)
1400 goto error;
1401 if (isl_space_match(pwaff1->dim, isl_dim_param,
1402 pwaff2->dim, isl_dim_param))
1403 return fn(pwaff1, pwaff2);
1404 if (!isl_space_has_named_params(pwaff1->dim) ||
1405 !isl_space_has_named_params(pwaff2->dim))
1406 isl_die(isl_pw_aff_get_ctx(pwaff1), isl_error_invalid,
1407 "unaligned unnamed parameters", goto error);
1408 pwaff1 = isl_pw_aff_align_params(pwaff1, isl_pw_aff_get_space(pwaff2));
1409 pwaff2 = isl_pw_aff_align_params(pwaff2, isl_pw_aff_get_space(pwaff1));
1410 return fn(pwaff1, pwaff2);
1411 error:
1412 isl_pw_aff_free(pwaff1);
1413 isl_pw_aff_free(pwaff2);
1414 return NULL;
1415 }
1416
1417 /* Compute a piecewise quasi-affine expression with a domain that
1418 * is the union of those of pwaff1 and pwaff2 and such that on each
1419 * cell, the quasi-affine expression is the better (according to cmp)
1420 * of those of pwaff1 and pwaff2. If only one of pwaff1 or pwaff2
1421 * is defined on a given cell, then the associated expression
1422 * is the defined one.
1423 */
1424 static __isl_give isl_pw_aff *pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1425 __isl_take isl_pw_aff *pwaff2,
1426 __isl_give isl_basic_set *(*cmp)(__isl_take isl_aff *aff1,
1427 __isl_take isl_aff *aff2))
1428 {
1429 int i, j, n;
1430 isl_pw_aff *res;
1431 isl_ctx *ctx;
1432 isl_set *set;
1433
1434 if (!pwaff1 || !pwaff2)
1435 goto error;
1436
1437 ctx = isl_space_get_ctx(pwaff1->dim);
1438 if (!isl_space_is_equal(pwaff1->dim, pwaff2->dim))
1439 isl_die(ctx, isl_error_invalid,
1440 "arguments should live in same space", goto error);
1441
1442 if (isl_pw_aff_is_empty(pwaff1)) {
1443 isl_pw_aff_free(pwaff1);
1444 return pwaff2;
1445 }
1446
1447 if (isl_pw_aff_is_empty(pwaff2)) {
1448 isl_pw_aff_free(pwaff2);
1449 return pwaff1;
1450 }
1451
1452 n = 2 * (pwaff1->n + 1) * (pwaff2->n + 1);
1453 res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1454
1455 for (i = 0; i < pwaff1->n; ++i) {
1456 set = isl_set_copy(pwaff1->p[i].set);
1457 for (j = 0; j < pwaff2->n; ++j) {
1458 struct isl_set *common;
1459 isl_set *better;
1460
1461 common = isl_set_intersect(
1462 isl_set_copy(pwaff1->p[i].set),
1463 isl_set_copy(pwaff2->p[j].set));
1464 better = isl_set_from_basic_set(cmp(
1465 isl_aff_copy(pwaff2->p[j].aff),
1466 isl_aff_copy(pwaff1->p[i].aff)));
1467 better = isl_set_intersect(common, better);
1468 if (isl_set_plain_is_empty(better)) {
1469 isl_set_free(better);
1470 continue;
1471 }
1472 set = isl_set_subtract(set, isl_set_copy(better));
1473
1474 res = isl_pw_aff_add_piece(res, better,
1475 isl_aff_copy(pwaff2->p[j].aff));
1476 }
1477 res = isl_pw_aff_add_piece(res, set,
1478 isl_aff_copy(pwaff1->p[i].aff));
1479 }
1480
1481 for (j = 0; j < pwaff2->n; ++j) {
1482 set = isl_set_copy(pwaff2->p[j].set);
1483 for (i = 0; i < pwaff1->n; ++i)
1484 set = isl_set_subtract(set,
1485 isl_set_copy(pwaff1->p[i].set));
1486 res = isl_pw_aff_add_piece(res, set,
1487 isl_aff_copy(pwaff2->p[j].aff));
1488 }
1489
1490 isl_pw_aff_free(pwaff1);
1491 isl_pw_aff_free(pwaff2);
1492
1493 return res;
1494 error:
1495 isl_pw_aff_free(pwaff1);
1496 isl_pw_aff_free(pwaff2);
1497 return NULL;
1498 }
1499
1500 /* Compute a piecewise quasi-affine expression with a domain that
1501 * is the union of those of pwaff1 and pwaff2 and such that on each
1502 * cell, the quasi-affine expression is the maximum of those of pwaff1
1503 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1504 * cell, then the associated expression is the defined one.
1505 */
1506 static __isl_give isl_pw_aff *pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1507 __isl_take isl_pw_aff *pwaff2)
1508 {
1509 return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_ge_basic_set);
1510 }
1511
1512 __isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1513 __isl_take isl_pw_aff *pwaff2)
1514 {
1515 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
1516 &pw_aff_union_max);
1517 }
1518
1519 /* Compute a piecewise quasi-affine expression with a domain that
1520 * is the union of those of pwaff1 and pwaff2 and such that on each
1521 * cell, the quasi-affine expression is the minimum of those of pwaff1
1522 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1523 * cell, then the associated expression is the defined one.
1524 */
1525 static __isl_give isl_pw_aff *pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1526 __isl_take isl_pw_aff *pwaff2)
1527 {
1528 return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_le_basic_set);
1529 }
1530
1531 __isl_give isl_pw_aff *isl_pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1532 __isl_take isl_pw_aff *pwaff2)
1533 {
1534 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
1535 &pw_aff_union_min);
1536 }
1537
1538 __isl_give isl_pw_aff *isl_pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1539 __isl_take isl_pw_aff *pwaff2, int max)
1540 {
1541 if (max)
1542 return isl_pw_aff_union_max(pwaff1, pwaff2);
1543 else
1544 return isl_pw_aff_union_min(pwaff1, pwaff2);
1545 }
1546
1547 /* Construct a map with as domain the domain of pwaff and
1548 * one-dimensional range corresponding to the affine expressions.
1549 */
1550 static __isl_give isl_map *map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1551 {
1552 int i;
1553 isl_space *dim;
1554 isl_map *map;
1555
1556 if (!pwaff)
1557 return NULL;
1558
1559 dim = isl_pw_aff_get_space(pwaff);
1560 map = isl_map_empty(dim);
1561
1562 for (i = 0; i < pwaff->n; ++i) {
1563 isl_basic_map *bmap;
1564 isl_map *map_i;
1565
1566 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
1567 map_i = isl_map_from_basic_map(bmap);
1568 map_i = isl_map_intersect_domain(map_i,
1569 isl_set_copy(pwaff->p[i].set));
1570 map = isl_map_union_disjoint(map, map_i);
1571 }
1572
1573 isl_pw_aff_free(pwaff);
1574
1575 return map;
1576 }
1577
1578 /* Construct a map with as domain the domain of pwaff and
1579 * one-dimensional range corresponding to the affine expressions.
1580 */
1581 __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1582 {
1583 if (!pwaff)
1584 return NULL;
1585 if (isl_space_is_set(pwaff->dim))
1586 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1587 "space of input is not a map",
1588 return isl_pw_aff_free(pwaff));
1589 return map_from_pw_aff(pwaff);
1590 }
1591
1592 /* Construct a one-dimensional set with as parameter domain
1593 * the domain of pwaff and the single set dimension
1594 * corresponding to the affine expressions.
1595 */
1596 __isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1597 {
1598 if (!pwaff)
1599 return NULL;
1600 if (!isl_space_is_set(pwaff->dim))
1601 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1602 "space of input is not a set",
1603 return isl_pw_aff_free(pwaff));
1604 return map_from_pw_aff(pwaff);
1605 }
1606
1607 /* Return a set containing those elements in the domain
1608 * of pwaff where it is non-negative.
1609 */
1610 __isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
1611 {
1612 int i;
1613 isl_set *set;
1614
1615 if (!pwaff)
1616 return NULL;
1617
1618 set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1619
1620 for (i = 0; i < pwaff->n; ++i) {
1621 isl_basic_set *bset;
1622 isl_set *set_i;
1623
1624 bset = isl_aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff));
1625 set_i = isl_set_from_basic_set(bset);
1626 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1627 set = isl_set_union_disjoint(set, set_i);
1628 }
1629
1630 isl_pw_aff_free(pwaff);
1631
1632 return set;
1633 }
1634
1635 /* Return a set containing those elements in the domain
1636 * of pwaff where it is zero (if complement is 0) or not zero
1637 * (if complement is 1).
1638 */
1639 static __isl_give isl_set *pw_aff_zero_set(__isl_take isl_pw_aff *pwaff,
1640 int complement)
1641 {
1642 int i;
1643 isl_set *set;
1644
1645 if (!pwaff)
1646 return NULL;
1647
1648 set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1649
1650 for (i = 0; i < pwaff->n; ++i) {
1651 isl_basic_set *bset;
1652 isl_set *set_i, *zero;
1653
1654 bset = isl_aff_zero_basic_set(isl_aff_copy(pwaff->p[i].aff));
1655 zero = isl_set_from_basic_set(bset);
1656 set_i = isl_set_copy(pwaff->p[i].set);
1657 if (complement)
1658 set_i = isl_set_subtract(set_i, zero);
1659 else
1660 set_i = isl_set_intersect(set_i, zero);
1661 set = isl_set_union_disjoint(set, set_i);
1662 }
1663
1664 isl_pw_aff_free(pwaff);
1665
1666 return set;
1667 }
1668
1669 /* Return a set containing those elements in the domain
1670 * of pwaff where it is zero.
1671 */
1672 __isl_give isl_set *isl_pw_aff_zero_set(__isl_take isl_pw_aff *pwaff)
1673 {
1674 return pw_aff_zero_set(pwaff, 0);
1675 }
1676
1677 /* Return a set containing those elements in the domain
1678 * of pwaff where it is not zero.
1679 */
1680 __isl_give isl_set *isl_pw_aff_non_zero_set(__isl_take isl_pw_aff *pwaff)
1681 {
1682 return pw_aff_zero_set(pwaff, 1);
1683 }
1684
1685 /* Return a set containing those elements in the shared domain
1686 * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
1687 *
1688 * We compute the difference on the shared domain and then construct
1689 * the set of values where this difference is non-negative.
1690 * If strict is set, we first subtract 1 from the difference.
1691 * If equal is set, we only return the elements where pwaff1 and pwaff2
1692 * are equal.
1693 */
1694 static __isl_give isl_set *pw_aff_gte_set(__isl_take isl_pw_aff *pwaff1,
1695 __isl_take isl_pw_aff *pwaff2, int strict, int equal)
1696 {
1697 isl_set *set1, *set2;
1698
1699 set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1));
1700 set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2));
1701 set1 = isl_set_intersect(set1, set2);
1702 pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1));
1703 pwaff2 = isl_pw_aff_intersect_domain(pwaff2, isl_set_copy(set1));
1704 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2));
1705
1706 if (strict) {
1707 isl_space *dim = isl_set_get_space(set1);
1708 isl_aff *aff;
1709 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
1710 aff = isl_aff_add_constant_si(aff, -1);
1711 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_alloc(set1, aff));
1712 } else
1713 isl_set_free(set1);
1714
1715 if (equal)
1716 return isl_pw_aff_zero_set(pwaff1);
1717 return isl_pw_aff_nonneg_set(pwaff1);
1718 }
1719
1720 /* Return a set containing those elements in the shared domain
1721 * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
1722 */
1723 static __isl_give isl_set *pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1724 __isl_take isl_pw_aff *pwaff2)
1725 {
1726 return pw_aff_gte_set(pwaff1, pwaff2, 0, 1);
1727 }
1728
1729 __isl_give isl_set *isl_pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1730 __isl_take isl_pw_aff *pwaff2)
1731 {
1732 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_eq_set);
1733 }
1734
1735 /* Return a set containing those elements in the shared domain
1736 * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
1737 */
1738 static __isl_give isl_set *pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1739 __isl_take isl_pw_aff *pwaff2)
1740 {
1741 return pw_aff_gte_set(pwaff1, pwaff2, 0, 0);
1742 }
1743
1744 __isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1745 __isl_take isl_pw_aff *pwaff2)
1746 {
1747 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ge_set);
1748 }
1749
1750 /* Return a set containing those elements in the shared domain
1751 * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
1752 */
1753 static __isl_give isl_set *pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1754 __isl_take isl_pw_aff *pwaff2)
1755 {
1756 return pw_aff_gte_set(pwaff1, pwaff2, 1, 0);
1757 }
1758
1759 __isl_give isl_set *isl_pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1760 __isl_take isl_pw_aff *pwaff2)
1761 {
1762 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_gt_set);
1763 }
1764
1765 __isl_give isl_set *isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1,
1766 __isl_take isl_pw_aff *pwaff2)
1767 {
1768 return isl_pw_aff_ge_set(pwaff2, pwaff1);
1769 }
1770
1771 __isl_give isl_set *isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1,
1772 __isl_take isl_pw_aff *pwaff2)
1773 {
1774 return isl_pw_aff_gt_set(pwaff2, pwaff1);
1775 }
1776
1777 /* Return a set containing those elements in the shared domain
1778 * of the elements of list1 and list2 where each element in list1
1779 * has the relation specified by "fn" with each element in list2.
1780 */
1781 static __isl_give isl_set *pw_aff_list_set(__isl_take isl_pw_aff_list *list1,
1782 __isl_take isl_pw_aff_list *list2,
1783 __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1784 __isl_take isl_pw_aff *pwaff2))
1785 {
1786 int i, j;
1787 isl_ctx *ctx;
1788 isl_set *set;
1789
1790 if (!list1 || !list2)
1791 goto error;
1792
1793 ctx = isl_pw_aff_list_get_ctx(list1);
1794 if (list1->n < 1 || list2->n < 1)
1795 isl_die(ctx, isl_error_invalid,
1796 "list should contain at least one element", goto error);
1797
1798 set = isl_set_universe(isl_pw_aff_get_domain_space(list1->p[0]));
1799 for (i = 0; i < list1->n; ++i)
1800 for (j = 0; j < list2->n; ++j) {
1801 isl_set *set_ij;
1802
1803 set_ij = fn(isl_pw_aff_copy(list1->p[i]),
1804 isl_pw_aff_copy(list2->p[j]));
1805 set = isl_set_intersect(set, set_ij);
1806 }
1807
1808 isl_pw_aff_list_free(list1);
1809 isl_pw_aff_list_free(list2);
1810 return set;
1811 error:
1812 isl_pw_aff_list_free(list1);
1813 isl_pw_aff_list_free(list2);
1814 return NULL;
1815 }
1816
1817 /* Return a set containing those elements in the shared domain
1818 * of the elements of list1 and list2 where each element in list1
1819 * is equal to each element in list2.
1820 */
1821 __isl_give isl_set *isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list *list1,
1822 __isl_take isl_pw_aff_list *list2)
1823 {
1824 return pw_aff_list_set(list1, list2, &isl_pw_aff_eq_set);
1825 }
1826
1827 __isl_give isl_set *isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list *list1,
1828 __isl_take isl_pw_aff_list *list2)
1829 {
1830 return pw_aff_list_set(list1, list2, &isl_pw_aff_ne_set);
1831 }
1832
1833 /* Return a set containing those elements in the shared domain
1834 * of the elements of list1 and list2 where each element in list1
1835 * is less than or equal to each element in list2.
1836 */
1837 __isl_give isl_set *isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list *list1,
1838 __isl_take isl_pw_aff_list *list2)
1839 {
1840 return pw_aff_list_set(list1, list2, &isl_pw_aff_le_set);
1841 }
1842
1843 __isl_give isl_set *isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list *list1,
1844 __isl_take isl_pw_aff_list *list2)
1845 {
1846 return pw_aff_list_set(list1, list2, &isl_pw_aff_lt_set);
1847 }
1848
1849 __isl_give isl_set *isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list *list1,
1850 __isl_take isl_pw_aff_list *list2)
1851 {
1852 return pw_aff_list_set(list1, list2, &isl_pw_aff_ge_set);
1853 }
1854
1855 __isl_give isl_set *isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list *list1,
1856 __isl_take isl_pw_aff_list *list2)
1857 {
1858 return pw_aff_list_set(list1, list2, &isl_pw_aff_gt_set);
1859 }
1860
1861
1862 /* Return a set containing those elements in the shared domain
1863 * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
1864 */
1865 static __isl_give isl_set *pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1866 __isl_take isl_pw_aff *pwaff2)
1867 {
1868 isl_set *set_lt, *set_gt;
1869
1870 set_lt = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1),
1871 isl_pw_aff_copy(pwaff2));
1872 set_gt = isl_pw_aff_gt_set(pwaff1, pwaff2);
1873 return isl_set_union_disjoint(set_lt, set_gt);
1874 }
1875
1876 __isl_give isl_set *isl_pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1877 __isl_take isl_pw_aff *pwaff2)
1878 {
1879 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ne_set);
1880 }
1881
1882 __isl_give isl_pw_aff *isl_pw_aff_scale_down(__isl_take isl_pw_aff *pwaff,
1883 isl_int v)
1884 {
1885 int i;
1886
1887 if (isl_int_is_one(v))
1888 return pwaff;
1889 if (!isl_int_is_pos(v))
1890 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1891 "factor needs to be positive",
1892 return isl_pw_aff_free(pwaff));
1893 pwaff = isl_pw_aff_cow(pwaff);
1894 if (!pwaff)
1895 return NULL;
1896 if (pwaff->n == 0)
1897 return pwaff;
1898
1899 for (i = 0; i < pwaff->n; ++i) {
1900 pwaff->p[i].aff = isl_aff_scale_down(pwaff->p[i].aff, v);
1901 if (!pwaff->p[i].aff)
1902 return isl_pw_aff_free(pwaff);
1903 }
1904
1905 return pwaff;
1906 }
1907
1908 __isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff)
1909 {
1910 int i;
1911
1912 pwaff = isl_pw_aff_cow(pwaff);
1913 if (!pwaff)
1914 return NULL;
1915 if (pwaff->n == 0)
1916 return pwaff;
1917
1918 for (i = 0; i < pwaff->n; ++i) {
1919 pwaff->p[i].aff = isl_aff_floor(pwaff->p[i].aff);
1920 if (!pwaff->p[i].aff)
1921 return isl_pw_aff_free(pwaff);
1922 }
1923
1924 return pwaff;
1925 }
1926
1927 __isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff)
1928 {
1929 int i;
1930
1931 pwaff = isl_pw_aff_cow(pwaff);
1932 if (!pwaff)
1933 return NULL;
1934 if (pwaff->n == 0)
1935 return pwaff;
1936
1937 for (i = 0; i < pwaff->n; ++i) {
1938 pwaff->p[i].aff = isl_aff_ceil(pwaff->p[i].aff);
1939 if (!pwaff->p[i].aff)
1940 return isl_pw_aff_free(pwaff);
1941 }
1942
1943 return pwaff;
1944 }
1945
1946 /* Assuming that "cond1" and "cond2" are disjoint,
1947 * return an affine expression that is equal to pwaff1 on cond1
1948 * and to pwaff2 on cond2.
1949 */
1950 static __isl_give isl_pw_aff *isl_pw_aff_select(
1951 __isl_take isl_set *cond1, __isl_take isl_pw_aff *pwaff1,
1952 __isl_take isl_set *cond2, __isl_take isl_pw_aff *pwaff2)
1953 {
1954 pwaff1 = isl_pw_aff_intersect_domain(pwaff1, cond1);
1955 pwaff2 = isl_pw_aff_intersect_domain(pwaff2, cond2);
1956
1957 return isl_pw_aff_add_disjoint(pwaff1, pwaff2);
1958 }
1959
1960 /* Return an affine expression that is equal to pwaff_true for elements
1961 * where "cond" is non-zero and to pwaff_false for elements where "cond"
1962 * is zero.
1963 * That is, return cond ? pwaff_true : pwaff_false;
1964 */
1965 __isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_pw_aff *cond,
1966 __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false)
1967 {
1968 isl_set *cond_true, *cond_false;
1969
1970 cond_true = isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond));
1971 cond_false = isl_pw_aff_zero_set(cond);
1972 return isl_pw_aff_select(cond_true, pwaff_true,
1973 cond_false, pwaff_false);
1974 }
1975
1976 int isl_aff_is_cst(__isl_keep isl_aff *aff)
1977 {
1978 if (!aff)
1979 return -1;
1980
1981 return isl_seq_first_non_zero(aff->v->el + 2, aff->v->size - 2) == -1;
1982 }
1983
1984 /* Check whether pwaff is a piecewise constant.
1985 */
1986 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff)
1987 {
1988 int i;
1989
1990 if (!pwaff)
1991 return -1;
1992
1993 for (i = 0; i < pwaff->n; ++i) {
1994 int is_cst = isl_aff_is_cst(pwaff->p[i].aff);
1995 if (is_cst < 0 || !is_cst)
1996 return is_cst;
1997 }
1998
1999 return 1;
2000 }
2001
2002 __isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
2003 __isl_take isl_aff *aff2)
2004 {
2005 if (!isl_aff_is_cst(aff2) && isl_aff_is_cst(aff1))
2006 return isl_aff_mul(aff2, aff1);
2007
2008 if (!isl_aff_is_cst(aff2))
2009 isl_die(isl_aff_get_ctx(aff1), isl_error_invalid,
2010 "at least one affine expression should be constant",
2011 goto error);
2012
2013 aff1 = isl_aff_cow(aff1);
2014 if (!aff1 || !aff2)
2015 goto error;
2016
2017 aff1 = isl_aff_scale(aff1, aff2->v->el[1]);
2018 aff1 = isl_aff_scale_down(aff1, aff2->v->el[0]);
2019
2020 isl_aff_free(aff2);
2021 return aff1;
2022 error:
2023 isl_aff_free(aff1);
2024 isl_aff_free(aff2);
2025 return NULL;
2026 }
2027
2028 static __isl_give isl_pw_aff *pw_aff_add(__isl_take isl_pw_aff *pwaff1,
2029 __isl_take isl_pw_aff *pwaff2)
2030 {
2031 return isl_pw_aff_on_shared_domain(pwaff1, pwaff2, &isl_aff_add);
2032 }
2033
2034 __isl_give isl_pw_aff *isl_pw_aff_add(__isl_take isl_pw_aff *pwaff1,
2035 __isl_take isl_pw_aff *pwaff2)
2036 {
2037 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_add);
2038 }
2039
2040 __isl_give isl_pw_aff *isl_pw_aff_union_add(__isl_take isl_pw_aff *pwaff1,
2041 __isl_take isl_pw_aff *pwaff2)
2042 {
2043 return isl_pw_aff_union_add_(pwaff1, pwaff2);
2044 }
2045
2046 static __isl_give isl_pw_aff *pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
2047 __isl_take isl_pw_aff *pwaff2)
2048 {
2049 return isl_pw_aff_on_shared_domain(pwaff1, pwaff2, &isl_aff_mul);
2050 }
2051
2052 __isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
2053 __isl_take isl_pw_aff *pwaff2)
2054 {
2055 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul);
2056 }
2057
2058 static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
2059 __isl_take isl_pw_aff *pwaff2)
2060 {
2061 isl_set *le;
2062 isl_set *dom;
2063
2064 dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1)),
2065 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2)));
2066 le = isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1),
2067 isl_pw_aff_copy(pwaff2));
2068 dom = isl_set_subtract(dom, isl_set_copy(le));
2069 return isl_pw_aff_select(le, pwaff1, dom, pwaff2);
2070 }
2071
2072 __isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
2073 __isl_take isl_pw_aff *pwaff2)
2074 {
2075 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_min);
2076 }
2077
2078 static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
2079 __isl_take isl_pw_aff *pwaff2)
2080 {
2081 isl_set *ge;
2082 isl_set *dom;
2083
2084 dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1)),
2085 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2)));
2086 ge = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1),
2087 isl_pw_aff_copy(pwaff2));
2088 dom = isl_set_subtract(dom, isl_set_copy(ge));
2089 return isl_pw_aff_select(ge, pwaff1, dom, pwaff2);
2090 }
2091
2092 __isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
2093 __isl_take isl_pw_aff *pwaff2)
2094 {
2095 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_max);
2096 }
2097
2098 static __isl_give isl_pw_aff *pw_aff_list_reduce(
2099 __isl_take isl_pw_aff_list *list,
2100 __isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pwaff1,
2101 __isl_take isl_pw_aff *pwaff2))
2102 {
2103 int i;
2104 isl_ctx *ctx;
2105 isl_pw_aff *res;
2106
2107 if (!list)
2108 return NULL;
2109
2110 ctx = isl_pw_aff_list_get_ctx(list);
2111 if (list->n < 1)
2112 isl_die(ctx, isl_error_invalid,
2113 "list should contain at least one element",
2114 return isl_pw_aff_list_free(list));
2115
2116 res = isl_pw_aff_copy(list->p[0]);
2117 for (i = 1; i < list->n; ++i)
2118 res = fn(res, isl_pw_aff_copy(list->p[i]));
2119
2120 isl_pw_aff_list_free(list);
2121 return res;
2122 }
2123
2124 /* Return an isl_pw_aff that maps each element in the intersection of the
2125 * domains of the elements of list to the minimal corresponding affine
2126 * expression.
2127 */
2128 __isl_give isl_pw_aff *isl_pw_aff_list_min(__isl_take isl_pw_aff_list *list)
2129 {
2130 return pw_aff_list_reduce(list, &isl_pw_aff_min);
2131 }
2132
2133 /* Return an isl_pw_aff that maps each element in the intersection of the
2134 * domains of the elements of list to the maximal corresponding affine
2135 * expression.
2136 */
2137 __isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list)
2138 {
2139 return pw_aff_list_reduce(list, &isl_pw_aff_max);
2140 }
2141
2142 #undef BASE
2143 #define BASE aff
2144
2145 #include <isl_multi_templ.c>
2146
2147 /* Construct an isl_multi_aff in the given space with value zero in
2148 * each of the output dimensions.
2149 */
2150 __isl_give isl_multi_aff *isl_multi_aff_zero(__isl_take isl_space *space)
2151 {
2152 int n;
2153 isl_multi_aff *ma;
2154
2155 if (!space)
2156 return NULL;
2157
2158 n = isl_space_dim(space , isl_dim_out);
2159 ma = isl_multi_aff_alloc(isl_space_copy(space));
2160
2161 if (!n)
2162 isl_space_free(space);
2163 else {
2164 int i;
2165 isl_local_space *ls;
2166 isl_aff *aff;
2167
2168 space = isl_space_domain(space);
2169 ls = isl_local_space_from_space(space);
2170 aff = isl_aff_zero_on_domain(ls);
2171
2172 for (i = 0; i < n; ++i)
2173 ma = isl_multi_aff_set_aff(ma, i, isl_aff_copy(aff));
2174
2175 isl_aff_free(aff);
2176 }
2177
2178 return ma;
2179 }
2180
2181 /* Create an isl_multi_aff in the given space that maps each
2182 * input dimension to the corresponding output dimension.
2183 */
2184 __isl_give isl_multi_aff *isl_multi_aff_identity(__isl_take isl_space *space)
2185 {
2186 int n;
2187 isl_multi_aff *ma;
2188
2189 if (!space)
2190 return NULL;
2191
2192 if (isl_space_is_set(space))
2193 isl_die(isl_space_get_ctx(space), isl_error_invalid,
2194 "expecting map space", goto error);
2195
2196 n = isl_space_dim(space, isl_dim_out);
2197 if (n != isl_space_dim(space, isl_dim_in))
2198 isl_die(isl_space_get_ctx(space), isl_error_invalid,
2199 "number of input and output dimensions needs to be "
2200 "the same", goto error);
2201
2202 ma = isl_multi_aff_alloc(isl_space_copy(space));
2203
2204 if (!n)
2205 isl_space_free(space);
2206 else {
2207 int i;
2208 isl_local_space *ls;
2209 isl_aff *aff;
2210
2211 space = isl_space_domain(space);
2212 ls = isl_local_space_from_space(space);
2213 aff = isl_aff_zero_on_domain(ls);
2214
2215 for (i = 0; i < n; ++i) {
2216 isl_aff *aff_i;
2217 aff_i = isl_aff_copy(aff);
2218 aff_i = isl_aff_add_coefficient_si(aff_i,
2219 isl_dim_in, i, 1);
2220 ma = isl_multi_aff_set_aff(ma, i, aff_i);
2221 }
2222
2223 isl_aff_free(aff);
2224 }
2225
2226 return ma;
2227 error:
2228 isl_space_free(space);
2229 return NULL;
2230 }
2231
2232 /* Create an isl_pw_multi_aff with the given isl_multi_aff on a universe
2233 * domain.
2234 */
2235 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_multi_aff(
2236 __isl_take isl_multi_aff *ma)
2237 {
2238 isl_set *dom = isl_set_universe(isl_multi_aff_get_domain_space(ma));
2239 return isl_pw_multi_aff_alloc(dom, ma);
2240 }
2241
2242 __isl_give isl_multi_aff *isl_multi_aff_add(__isl_take isl_multi_aff *maff1,
2243 __isl_take isl_multi_aff *maff2)
2244 {
2245 int i;
2246 isl_ctx *ctx;
2247
2248 maff1 = isl_multi_aff_cow(maff1);
2249 if (!maff1 || !maff2)
2250 goto error;
2251
2252 ctx = isl_multi_aff_get_ctx(maff1);
2253 if (!isl_space_is_equal(maff1->space, maff2->space))
2254 isl_die(ctx, isl_error_invalid,
2255 "spaces don't match", goto error);
2256
2257 for (i = 0; i < maff1->n; ++i) {
2258 maff1->p[i] = isl_aff_add(maff1->p[i],
2259 isl_aff_copy(maff2->p[i]));
2260 if (!maff1->p[i])
2261 goto error;
2262 }
2263
2264 isl_multi_aff_free(maff2);
2265 return maff1;
2266 error:
2267 isl_multi_aff_free(maff1);
2268 isl_multi_aff_free(maff2);
2269 return NULL;
2270 }
2271
2272 /* Given two multi-affine expressions A -> B and C -> D,
2273 * construct a multi-affine expression [A -> C] -> [B -> D].
2274 */
2275 __isl_give isl_multi_aff *isl_multi_aff_product(
2276 __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2)
2277 {
2278 int i;
2279 isl_aff *aff;
2280 isl_space *space;
2281 isl_multi_aff *res;
2282 int in1, in2, out1, out2;
2283
2284 in1 = isl_multi_aff_dim(ma1, isl_dim_in);
2285 in2 = isl_multi_aff_dim(ma2, isl_dim_in);
2286 out1 = isl_multi_aff_dim(ma1, isl_dim_out);
2287 out2 = isl_multi_aff_dim(ma2, isl_dim_out);
2288 space = isl_space_product(isl_multi_aff_get_space(ma1),
2289 isl_multi_aff_get_space(ma2));
2290 res = isl_multi_aff_alloc(isl_space_copy(space));
2291 space = isl_space_domain(space);
2292
2293 for (i = 0; i < out1; ++i) {
2294 aff = isl_multi_aff_get_aff(ma1, i);
2295 aff = isl_aff_insert_dims(aff, isl_dim_in, in1, in2);
2296 aff = isl_aff_reset_domain_space(aff, isl_space_copy(space));
2297 res = isl_multi_aff_set_aff(res, i, aff);
2298 }
2299
2300 for (i = 0; i < out2; ++i) {
2301 aff = isl_multi_aff_get_aff(ma2, i);
2302 aff = isl_aff_insert_dims(aff, isl_dim_in, 0, in1);
2303 aff = isl_aff_reset_domain_space(aff, isl_space_copy(space));
2304 res = isl_multi_aff_set_aff(res, out1 + i, aff);
2305 }
2306
2307 isl_space_free(space);
2308 isl_multi_aff_free(ma1);
2309 isl_multi_aff_free(ma2);
2310 return res;
2311 }
2312
2313 /* Exploit the equalities in "eq" to simplify the affine expressions.
2314 */
2315 static __isl_give isl_multi_aff *isl_multi_aff_substitute_equalities(
2316 __isl_take isl_multi_aff *maff, __isl_take isl_basic_set *eq)
2317 {
2318 int i;
2319
2320 maff = isl_multi_aff_cow(maff);
2321 if (!maff || !eq)
2322 goto error;
2323
2324 for (i = 0; i < maff->n; ++i) {
2325 maff->p[i] = isl_aff_substitute_equalities(maff->p[i],
2326 isl_basic_set_copy(eq));
2327 if (!maff->p[i])
2328 goto error;
2329 }
2330
2331 isl_basic_set_free(eq);
2332 return maff;
2333 error:
2334 isl_basic_set_free(eq);
2335 isl_multi_aff_free(maff);
2336 return NULL;
2337 }
2338
2339 __isl_give isl_multi_aff *isl_multi_aff_scale(__isl_take isl_multi_aff *maff,
2340 isl_int f)
2341 {
2342 int i;
2343
2344 maff = isl_multi_aff_cow(maff);
2345 if (!maff)
2346 return NULL;
2347
2348 for (i = 0; i < maff->n; ++i) {
2349 maff->p[i] = isl_aff_scale(maff->p[i], f);
2350 if (!maff->p[i])
2351 return isl_multi_aff_free(maff);
2352 }
2353
2354 return maff;
2355 }
2356
2357 __isl_give isl_multi_aff *isl_multi_aff_add_on_domain(__isl_keep isl_set *dom,
2358 __isl_take isl_multi_aff *maff1, __isl_take isl_multi_aff *maff2)
2359 {
2360 maff1 = isl_multi_aff_add(maff1, maff2);
2361 maff1 = isl_multi_aff_gist(maff1, isl_set_copy(dom));
2362 return maff1;
2363 }
2364
2365 int isl_multi_aff_is_empty(__isl_keep isl_multi_aff *maff)
2366 {
2367 if (!maff)
2368 return -1;
2369
2370 return 0;
2371 }
2372
2373 int isl_multi_aff_plain_is_equal(__isl_keep isl_multi_aff *maff1,
2374 __isl_keep isl_multi_aff *maff2)
2375 {
2376 int i;
2377 int equal;
2378
2379 if (!maff1 || !maff2)
2380 return -1;
2381 if (maff1->n != maff2->n)
2382 return 0;
2383 equal = isl_space_is_equal(maff1->space, maff2->space);
2384 if (equal < 0 || !equal)
2385 return equal;
2386
2387 for (i = 0; i < maff1->n; ++i) {
2388 equal = isl_aff_plain_is_equal(maff1->p[i], maff2->p[i]);
2389 if (equal < 0 || !equal)
2390 return equal;
2391 }
2392
2393 return 1;
2394 }
2395
2396 __isl_give isl_multi_aff *isl_multi_aff_set_dim_name(
2397 __isl_take isl_multi_aff *maff,
2398 enum isl_dim_type type, unsigned pos, const char *s)
2399 {
2400 int i;
2401
2402 maff = isl_multi_aff_cow(maff);
2403 if (!maff)
2404 return NULL;
2405
2406 maff->space = isl_space_set_dim_name(maff->space, type, pos, s);
2407 if (!maff->space)
2408 return isl_multi_aff_free(maff);
2409
2410 if (type == isl_dim_out)
2411 return maff;
2412 for (i = 0; i < maff->n; ++i) {
2413 maff->p[i] = isl_aff_set_dim_name(maff->p[i], type, pos, s);
2414 if (!maff->p[i])
2415 return isl_multi_aff_free(maff);
2416 }
2417
2418 return maff;
2419 }
2420
2421 __isl_give isl_multi_aff *isl_multi_aff_drop_dims(__isl_take isl_multi_aff *maff,
2422 enum isl_dim_type type, unsigned first, unsigned n)
2423 {
2424 int i;
2425
2426 maff = isl_multi_aff_cow(maff);
2427 if (!maff)
2428 return NULL;
2429
2430 maff->space = isl_space_drop_dims(maff->space, type, first, n);
2431 if (!maff->space)
2432 return isl_multi_aff_free(maff);
2433
2434 if (type == isl_dim_out) {
2435 for (i = 0; i < n; ++i)
2436 isl_aff_free(maff->p[first + i]);
2437 for (i = first; i + n < maff->n; ++i)
2438 maff->p[i] = maff->p[i + n];
2439 maff->n -= n;
2440 return maff;
2441 }
2442
2443 for (i = 0; i < maff->n; ++i) {
2444 maff->p[i] = isl_aff_drop_dims(maff->p[i], type, first, n);
2445 if (!maff->p[i])
2446 return isl_multi_aff_free(maff);
2447 }
2448
2449 return maff;
2450 }
2451
2452 /* Return the set of domain elements where "ma1" is lexicographically
2453 * smaller than or equal to "ma2".
2454 */
2455 __isl_give isl_set *isl_multi_aff_lex_le_set(__isl_take isl_multi_aff *ma1,
2456 __isl_take isl_multi_aff *ma2)
2457 {
2458 return isl_multi_aff_lex_ge_set(ma2, ma1);
2459 }
2460
2461 /* Return the set of domain elements where "ma1" is lexicographically
2462 * greater than or equal to "ma2".
2463 */
2464 __isl_give isl_set *isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff *ma1,
2465 __isl_take isl_multi_aff *ma2)
2466 {
2467 isl_space *space;
2468 isl_map *map1, *map2;
2469 isl_map *map, *ge;
2470
2471 map1 = isl_map_from_multi_aff(ma1);
2472 map2 = isl_map_from_multi_aff(ma2);
2473 map = isl_map_range_product(map1, map2);
2474 space = isl_space_range(isl_map_get_space(map));
2475 space = isl_space_domain(isl_space_unwrap(space));
2476 ge = isl_map_lex_ge(space);
2477 map = isl_map_intersect_range(map, isl_map_wrap(ge));
2478
2479 return isl_map_domain(map);
2480 }
2481
2482 #undef PW
2483 #define PW isl_pw_multi_aff
2484 #undef EL
2485 #define EL isl_multi_aff
2486 #undef EL_IS_ZERO
2487 #define EL_IS_ZERO is_empty
2488 #undef ZERO
2489 #define ZERO empty
2490 #undef IS_ZERO
2491 #define IS_ZERO is_empty
2492 #undef FIELD
2493 #define FIELD maff
2494 #undef DEFAULT_IS_ZERO
2495 #define DEFAULT_IS_ZERO 0
2496
2497 #define NO_NEG
2498 #define NO_EVAL
2499 #define NO_OPT
2500 #define NO_INVOLVES_DIMS
2501 #define NO_MOVE_DIMS
2502 #define NO_INSERT_DIMS
2503 #define NO_LIFT
2504 #define NO_MORPH
2505
2506 #include <isl_pw_templ.c>
2507
2508 #undef UNION
2509 #define UNION isl_union_pw_multi_aff
2510 #undef PART
2511 #define PART isl_pw_multi_aff
2512 #undef PARTS
2513 #define PARTS pw_multi_aff
2514 #define ALIGN_DOMAIN
2515
2516 #define NO_EVAL
2517
2518 #include <isl_union_templ.c>
2519
2520 /* Given a function "cmp" that returns the set of elements where
2521 * "ma1" is "better" than "ma2", return the intersection of this
2522 * set with "dom1" and "dom2".
2523 */
2524 static __isl_give isl_set *shared_and_better(__isl_keep isl_set *dom1,
2525 __isl_keep isl_set *dom2, __isl_keep isl_multi_aff *ma1,
2526 __isl_keep isl_multi_aff *ma2,
2527 __isl_give isl_set *(*cmp)(__isl_take isl_multi_aff *ma1,
2528 __isl_take isl_multi_aff *ma2))
2529 {
2530 isl_set *common;
2531 isl_set *better;
2532 int is_empty;
2533
2534 common = isl_set_intersect(isl_set_copy(dom1), isl_set_copy(dom2));
2535 is_empty = isl_set_plain_is_empty(common);
2536 if (is_empty >= 0 && is_empty)
2537 return common;
2538 if (is_empty < 0)
2539 return isl_set_free(common);
2540 better = cmp(isl_multi_aff_copy(ma1), isl_multi_aff_copy(ma2));
2541 better = isl_set_intersect(common, better);
2542
2543 return better;
2544 }
2545
2546 /* Given a function "cmp" that returns the set of elements where
2547 * "ma1" is "better" than "ma2", return a piecewise multi affine
2548 * expression defined on the union of the definition domains
2549 * of "pma1" and "pma2" that maps to the "best" of "pma1" and
2550 * "pma2" on each cell. If only one of the two input functions
2551 * is defined on a given cell, then it is considered the best.
2552 */
2553 static __isl_give isl_pw_multi_aff *pw_multi_aff_union_opt(
2554 __isl_take isl_pw_multi_aff *pma1,
2555 __isl_take isl_pw_multi_aff *pma2,
2556 __isl_give isl_set *(*cmp)(__isl_take isl_multi_aff *ma1,
2557 __isl_take isl_multi_aff *ma2))
2558 {
2559 int i, j, n;
2560 isl_pw_multi_aff *res = NULL;
2561 isl_ctx *ctx;
2562 isl_set *set = NULL;
2563
2564 if (!pma1 || !pma2)
2565 goto error;
2566
2567 ctx = isl_space_get_ctx(pma1->dim);
2568 if (!isl_space_is_equal(pma1->dim, pma2->dim))
2569 isl_die(ctx, isl_error_invalid,
2570 "arguments should live in the same space", goto error);
2571
2572 if (isl_pw_multi_aff_is_empty(pma1)) {
2573 isl_pw_multi_aff_free(pma1);
2574 return pma2;
2575 }
2576
2577 if (isl_pw_multi_aff_is_empty(pma2)) {
2578 isl_pw_multi_aff_free(pma2);
2579 return pma1;
2580 }
2581
2582 n = 2 * (pma1->n + 1) * (pma2->n + 1);
2583 res = isl_pw_multi_aff_alloc_size(isl_space_copy(pma1->dim), n);
2584
2585 for (i = 0; i < pma1->n; ++i) {
2586 set = isl_set_copy(pma1->p[i].set);
2587 for (j = 0; j < pma2->n; ++j) {
2588 isl_set *better;
2589 int is_empty;
2590
2591 better = shared_and_better(pma2->p[j].set,
2592 pma1->p[i].set, pma2->p[j].maff,
2593 pma1->p[i].maff, cmp);
2594 is_empty = isl_set_plain_is_empty(better);
2595 if (is_empty < 0 || is_empty) {
2596 isl_set_free(better);
2597 if (is_empty < 0)
2598 goto error;
2599 continue;
2600 }
2601 set = isl_set_subtract(set, isl_set_copy(better));
2602
2603 res = isl_pw_multi_aff_add_piece(res, better,
2604 isl_multi_aff_copy(pma2->p[j].maff));
2605 }
2606 res = isl_pw_multi_aff_add_piece(res, set,
2607 isl_multi_aff_copy(pma1->p[i].maff));
2608 }
2609
2610 for (j = 0; j < pma2->n; ++j) {
2611 set = isl_set_copy(pma2->p[j].set);
2612 for (i = 0; i < pma1->n; ++i)
2613 set = isl_set_subtract(set,
2614 isl_set_copy(pma1->p[i].set));
2615 res = isl_pw_multi_aff_add_piece(res, set,
2616 isl_multi_aff_copy(pma2->p[j].maff));
2617 }
2618
2619 isl_pw_multi_aff_free(pma1);
2620 isl_pw_multi_aff_free(pma2);
2621
2622 return res;
2623 error:
2624 isl_pw_multi_aff_free(pma1);
2625 isl_pw_multi_aff_free(pma2);
2626 isl_set_free(set);
2627 return isl_pw_multi_aff_free(res);
2628 }
2629
2630 static __isl_give isl_pw_multi_aff *pw_multi_aff_union_lexmax(
2631 __isl_take isl_pw_multi_aff *pma1,
2632 __isl_take isl_pw_multi_aff *pma2)
2633 {
2634 return pw_multi_aff_union_opt(pma1, pma2, &isl_multi_aff_lex_ge_set);
2635 }
2636
2637 /* Given two piecewise multi affine expressions, return a piecewise
2638 * multi-affine expression defined on the union of the definition domains
2639 * of the inputs that is equal to the lexicographic maximum of the two
2640 * inputs on each cell. If only one of the two inputs is defined on
2641 * a given cell, then it is considered to be the maximum.
2642 */
2643 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_lexmax(
2644 __isl_take isl_pw_multi_aff *pma1,
2645 __isl_take isl_pw_multi_aff *pma2)
2646 {
2647 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
2648 &pw_multi_aff_union_lexmax);
2649 }
2650
2651 static __isl_give isl_pw_multi_aff *pw_multi_aff_union_lexmin(
2652 __isl_take isl_pw_multi_aff *pma1,
2653 __isl_take isl_pw_multi_aff *pma2)
2654 {
2655 return pw_multi_aff_union_opt(pma1, pma2, &isl_multi_aff_lex_le_set);
2656 }
2657
2658 /* Given two piecewise multi affine expressions, return a piecewise
2659 * multi-affine expression defined on the union of the definition domains
2660 * of the inputs that is equal to the lexicographic minimum of the two
2661 * inputs on each cell. If only one of the two inputs is defined on
2662 * a given cell, then it is considered to be the minimum.
2663 */
2664 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_lexmin(
2665 __isl_take isl_pw_multi_aff *pma1,
2666 __isl_take isl_pw_multi_aff *pma2)
2667 {
2668 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
2669 &pw_multi_aff_union_lexmin);
2670 }
2671
2672 static __isl_give isl_pw_multi_aff *pw_multi_aff_add(
2673 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
2674 {
2675 return isl_pw_multi_aff_on_shared_domain(pma1, pma2,
2676 &isl_multi_aff_add);
2677 }
2678
2679 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_add(
2680 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
2681 {
2682 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
2683 &pw_multi_aff_add);
2684 }
2685
2686 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_add(
2687 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
2688 {
2689 return isl_pw_multi_aff_union_add_(pma1, pma2);
2690 }
2691
2692 /* Given two piecewise multi-affine expressions A -> B and C -> D,
2693 * construct a piecewise multi-affine expression [A -> C] -> [B -> D].
2694 */
2695 static __isl_give isl_pw_multi_aff *pw_multi_aff_product(
2696 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
2697 {
2698 int i, j, n;
2699 isl_space *space;
2700 isl_pw_multi_aff *res;
2701
2702 if (!pma1 || !pma2)
2703 goto error;
2704
2705 n = pma1->n * pma2->n;
2706 space = isl_space_product(isl_space_copy(pma1->dim),
2707 isl_space_copy(pma2->dim));
2708 res = isl_pw_multi_aff_alloc_size(space, n);
2709
2710 for (i = 0; i < pma1->n; ++i) {
2711 for (j = 0; j < pma2->n; ++j) {
2712 isl_set *domain;
2713 isl_multi_aff *ma;
2714
2715 domain = isl_set_product(isl_set_copy(pma1->p[i].set),
2716 isl_set_copy(pma2->p[j].set));
2717 ma = isl_multi_aff_product(
2718 isl_multi_aff_copy(pma1->p[i].maff),
2719 isl_multi_aff_copy(pma2->p[i].maff));
2720 res = isl_pw_multi_aff_add_piece(res, domain, ma);
2721 }
2722 }
2723
2724 isl_pw_multi_aff_free(pma1);
2725 isl_pw_multi_aff_free(pma2);
2726 return res;
2727 error:
2728 isl_pw_multi_aff_free(pma1);
2729 isl_pw_multi_aff_free(pma2);
2730 return NULL;
2731 }
2732
2733 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_product(
2734 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
2735 {
2736 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
2737 &pw_multi_aff_product);
2738 }
2739
2740 /* Construct a map mapping the domain of the piecewise multi-affine expression
2741 * to its range, with each dimension in the range equated to the
2742 * corresponding affine expression on its cell.
2743 */
2744 __isl_give isl_map *isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
2745 {
2746 int i;
2747 isl_map *map;
2748
2749 if (!pma)
2750 return NULL;
2751
2752 map = isl_map_empty(isl_pw_multi_aff_get_space(pma));
2753
2754 for (i = 0; i < pma->n; ++i) {
2755 isl_multi_aff *maff;
2756 isl_basic_map *bmap;
2757 isl_map *map_i;
2758
2759 maff = isl_multi_aff_copy(pma->p[i].maff);
2760 bmap = isl_basic_map_from_multi_aff(maff);
2761 map_i = isl_map_from_basic_map(bmap);
2762 map_i = isl_map_intersect_domain(map_i,
2763 isl_set_copy(pma->p[i].set));
2764 map = isl_map_union_disjoint(map, map_i);
2765 }
2766
2767 isl_pw_multi_aff_free(pma);
2768 return map;
2769 }
2770
2771 __isl_give isl_set *isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
2772 {
2773 if (!isl_space_is_set(pma->dim))
2774 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
2775 "isl_pw_multi_aff cannot be converted into an isl_set",
2776 return isl_pw_multi_aff_free(pma));
2777
2778 return isl_map_from_pw_multi_aff(pma);
2779 }
2780
2781 /* Given a basic map with a single output dimension that is defined
2782 * in terms of the parameters and input dimensions using an equality,
2783 * extract an isl_aff that expresses the output dimension in terms
2784 * of the parameters and input dimensions.
2785 *
2786 * Since some applications expect the result of isl_pw_multi_aff_from_map
2787 * to only contain integer affine expressions, we compute the floor
2788 * of the expression before returning.
2789 *
2790 * This function shares some similarities with
2791 * isl_basic_map_has_defining_equality and isl_constraint_get_bound.
2792 */
2793 static __isl_give isl_aff *extract_isl_aff_from_basic_map(
2794 __isl_take isl_basic_map *bmap)
2795 {
2796 int i;
2797 unsigned offset;
2798 unsigned total;
2799 isl_local_space *ls;
2800 isl_aff *aff;
2801
2802 if (!bmap)
2803 return NULL;
2804 if (isl_basic_map_dim(bmap, isl_dim_out) != 1)
2805 isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
2806 "basic map should have a single output dimension",
2807 goto error);
2808 offset = isl_basic_map_offset(bmap, isl_dim_out);
2809 total = isl_basic_map_total_dim(bmap);
2810 for (i = 0; i < bmap->n_eq; ++i) {
2811 if (isl_int_is_zero(bmap->eq[i][offset]))
2812 continue;
2813 if (isl_seq_first_non_zero(bmap->eq[i] + offset + 1,
2814 1 + total - (offset + 1)) != -1)
2815 continue;
2816 break;
2817 }
2818 if (i >= bmap->n_eq)
2819 isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
2820 "unable to find suitable equality", goto error);
2821 ls = isl_basic_map_get_local_space(bmap);
2822 aff = isl_aff_alloc(isl_local_space_domain(ls));
2823 if (!aff)
2824 goto error;
2825 if (isl_int_is_neg(bmap->eq[i][offset]))
2826 isl_seq_cpy(aff->v->el + 1, bmap->eq[i], offset);
2827 else
2828 isl_seq_neg(aff->v->el + 1, bmap->eq[i], offset);
2829 isl_seq_clr(aff->v->el + 1 + offset, aff->v->size - (1 + offset));
2830 isl_int_abs(aff->v->el[0], bmap->eq[i][offset]);
2831 isl_basic_map_free(bmap);
2832
2833 aff = isl_aff_remove_unused_divs(aff);
2834 aff = isl_aff_floor(aff);
2835 return aff;
2836 error:
2837 isl_basic_map_free(bmap);
2838 return NULL;
2839 }
2840
2841 /* Given a basic map where each output dimension is defined
2842 * in terms of the parameters and input dimensions using an equality,
2843 * extract an isl_multi_aff that expresses the output dimensions in terms
2844 * of the parameters and input dimensions.
2845 */
2846 static __isl_give isl_multi_aff *extract_isl_multi_aff_from_basic_map(
2847 __isl_take isl_basic_map *bmap)
2848 {
2849 int i;
2850 unsigned n_out;
2851 isl_multi_aff *ma;
2852
2853 if (!bmap)
2854 return NULL;
2855
2856 ma = isl_multi_aff_alloc(isl_basic_map_get_space(bmap));
2857 n_out = isl_basic_map_dim(bmap, isl_dim_out);
2858
2859 for (i = 0; i < n_out; ++i) {
2860 isl_basic_map *bmap_i;
2861 isl_aff *aff;
2862
2863 bmap_i = isl_basic_map_copy(bmap);
2864 bmap_i = isl_basic_map_project_out(bmap_i, isl_dim_out,
2865 i + 1, n_out - (1 + i));
2866 bmap_i = isl_basic_map_project_out(bmap_i, isl_dim_out, 0, i);
2867 aff = extract_isl_aff_from_basic_map(bmap_i);
2868 ma = isl_multi_aff_set_aff(ma, i, aff);
2869 }
2870
2871 isl_basic_map_free(bmap);
2872
2873 return ma;
2874 }
2875
2876 /* Create an isl_pw_multi_aff that is equivalent to
2877 * isl_map_intersect_domain(isl_map_from_basic_map(bmap), domain).
2878 * The given basic map is such that each output dimension is defined
2879 * in terms of the parameters and input dimensions using an equality.
2880 */
2881 static __isl_give isl_pw_multi_aff *plain_pw_multi_aff_from_map(
2882 __isl_take isl_set *domain, __isl_take isl_basic_map *bmap)
2883 {
2884 isl_multi_aff *ma;
2885
2886 ma = extract_isl_multi_aff_from_basic_map(bmap);
2887 return isl_pw_multi_aff_alloc(domain, ma);
2888 }
2889
2890 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
2891 * This obivously only works if the input "map" is single-valued.
2892 * If so, we compute the lexicographic minimum of the image in the form
2893 * of an isl_pw_multi_aff. Since the image is unique, it is equal
2894 * to its lexicographic minimum.
2895 * If the input is not single-valued, we produce an error.
2896 *
2897 * As a special case, we first check if all output dimensions are uniquely
2898 * defined in terms of the parameters and input dimensions over the entire
2899 * domain. If so, we extract the desired isl_pw_multi_aff directly
2900 * from the affine hull of "map" and its domain.
2901 */
2902 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_map(__isl_take isl_map *map)
2903 {
2904 int i;
2905 int sv;
2906 isl_pw_multi_aff *pma;
2907 isl_basic_map *hull;
2908
2909 if (!map)
2910 return NULL;
2911
2912 hull = isl_map_affine_hull(isl_map_copy(map));
2913 sv = isl_basic_map_plain_is_single_valued(hull);
2914 if (sv >= 0 && sv)
2915 return plain_pw_multi_aff_from_map(isl_map_domain(map), hull);
2916 isl_basic_map_free(hull);
2917 if (sv < 0)
2918 goto error;
2919
2920 sv = isl_map_is_single_valued(map);
2921 if (sv < 0)
2922 goto error;
2923 if (!sv)
2924 isl_die(isl_map_get_ctx(map), isl_error_invalid,
2925 "map is not single-valued", goto error);
2926 map = isl_map_make_disjoint(map);
2927 if (!map)
2928 return NULL;
2929
2930 pma = isl_pw_multi_aff_empty(isl_map_get_space(map));
2931
2932 for (i = 0; i < map->n; ++i) {
2933 isl_pw_multi_aff *pma_i;
2934 isl_basic_map *bmap;
2935 bmap = isl_basic_map_copy(map->p[i]);
2936 pma_i = isl_basic_map_lexmin_pw_multi_aff(bmap);
2937 pma = isl_pw_multi_aff_add_disjoint(pma, pma_i);
2938 }
2939
2940 isl_map_free(map);
2941 return pma;
2942 error:
2943 isl_map_free(map);
2944 return NULL;
2945 }
2946
2947 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_set(__isl_take isl_set *set)
2948 {
2949 return isl_pw_multi_aff_from_map(set);
2950 }
2951
2952 /* Return the piecewise affine expression "set ? 1 : 0".
2953 */
2954 __isl_give isl_pw_aff *isl_set_indicator_function(__isl_take isl_set *set)
2955 {
2956 isl_pw_aff *pa;
2957 isl_space *space = isl_set_get_space(set);
2958 isl_local_space *ls = isl_local_space_from_space(space);
2959 isl_aff *zero = isl_aff_zero_on_domain(isl_local_space_copy(ls));
2960 isl_aff *one = isl_aff_zero_on_domain(ls);
2961
2962 one = isl_aff_add_constant_si(one, 1);
2963 pa = isl_pw_aff_alloc(isl_set_copy(set), one);
2964 set = isl_set_complement(set);
2965 pa = isl_pw_aff_add_disjoint(pa, isl_pw_aff_alloc(set, zero));
2966
2967 return pa;
2968 }
2969
2970 /* Plug in "subs" for dimension "type", "pos" of "aff".
2971 *
2972 * Let i be the dimension to replace and let "subs" be of the form
2973 *
2974 * f/d
2975 *
2976 * and "aff" of the form
2977 *
2978 * (a i + g)/m
2979 *
2980 * The result is
2981 *
2982 * (a f + d g')/(m d)
2983 *
2984 * where g' is the result of plugging in "subs" in each of the integer
2985 * divisions in g.
2986 */
2987 __isl_give isl_aff *isl_aff_substitute(__isl_take isl_aff *aff,
2988 enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
2989 {
2990 isl_ctx *ctx;
2991 isl_int v;
2992
2993 aff = isl_aff_cow(aff);
2994 if (!aff || !subs)
2995 return isl_aff_free(aff);
2996
2997 ctx = isl_aff_get_ctx(aff);
2998 if (!isl_space_is_equal(aff->ls->dim, subs->ls->dim))
2999 isl_die(ctx, isl_error_invalid,
3000 "spaces don't match", return isl_aff_free(aff));
3001 if (isl_local_space_dim(subs->ls, isl_dim_div) != 0)
3002 isl_die(ctx, isl_error_unsupported,
3003 "cannot handle divs yet", return isl_aff_free(aff));
3004
3005 aff->ls = isl_local_space_substitute(aff->ls, type, pos, subs);
3006 if (!aff->ls)
3007 return isl_aff_free(aff);
3008
3009 aff->v = isl_vec_cow(aff->v);
3010 if (!aff->v)
3011 return isl_aff_free(aff);
3012
3013 pos += isl_local_space_offset(aff->ls, type);
3014
3015 isl_int_init(v);
3016 isl_int_set(v, aff->v->el[1 + pos]);
3017 isl_int_set_si(aff->v->el[1 + pos], 0);
3018 isl_seq_combine(aff->v->el + 1, subs->v->el[0], aff->v->el + 1,
3019 v, subs->v->el + 1, subs->v->size - 1);
3020 isl_int_mul(aff->v->el[0], aff->v->el[0], subs->v->el[0]);
3021 isl_int_clear(v);
3022
3023 return aff;
3024 }
3025
3026 /* Plug in "subs" for dimension "type", "pos" in each of the affine
3027 * expressions in "maff".
3028 */
3029 __isl_give isl_multi_aff *isl_multi_aff_substitute(
3030 __isl_take isl_multi_aff *maff, enum isl_dim_type type, unsigned pos,
3031 __isl_keep isl_aff *subs)
3032 {
3033 int i;
3034
3035 maff = isl_multi_aff_cow(maff);
3036 if (!maff || !subs)
3037 return isl_multi_aff_free(maff);
3038
3039 if (type == isl_dim_in)
3040 type = isl_dim_set;
3041
3042 for (i = 0; i < maff->n; ++i) {
3043 maff->p[i] = isl_aff_substitute(maff->p[i], type, pos, subs);
3044 if (!maff->p[i])
3045 return isl_multi_aff_free(maff);
3046 }
3047
3048 return maff;
3049 }
3050
3051 /* Plug in "subs" for dimension "type", "pos" of "pma".
3052 *
3053 * pma is of the form
3054 *
3055 * A_i(v) -> M_i(v)
3056 *
3057 * while subs is of the form
3058 *
3059 * v' = B_j(v) -> S_j
3060 *
3061 * Each pair i,j such that C_ij = A_i \cap B_i is non-empty
3062 * has a contribution in the result, in particular
3063 *
3064 * C_ij(S_j) -> M_i(S_j)
3065 *
3066 * Note that plugging in S_j in C_ij may also result in an empty set
3067 * and this contribution should simply be discarded.
3068 */
3069 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_substitute(
3070 __isl_take isl_pw_multi_aff *pma, enum isl_dim_type type, unsigned pos,
3071 __isl_keep isl_pw_aff *subs)
3072 {
3073 int i, j, n;
3074 isl_pw_multi_aff *res;
3075
3076 if (!pma || !subs)
3077 return isl_pw_multi_aff_free(pma);
3078
3079 n = pma->n * subs->n;
3080 res = isl_pw_multi_aff_alloc_size(isl_space_copy(pma->dim), n);
3081
3082 for (i = 0; i < pma->n; ++i) {
3083 for (j = 0; j < subs->n; ++j) {
3084 isl_set *common;
3085 isl_multi_aff *res_ij;
3086 common = isl_set_intersect(
3087 isl_set_copy(pma->p[i].set),
3088 isl_set_copy(subs->p[j].set));
3089 common = isl_set_substitute(common,
3090 type, pos, subs->p[j].aff);
3091 if (isl_set_plain_is_empty(common)) {
3092 isl_set_free(common);
3093 continue;
3094 }
3095
3096 res_ij = isl_multi_aff_substitute(
3097 isl_multi_aff_copy(pma->p[i].maff),
3098 type, pos, subs->p[j].aff);
3099
3100 res = isl_pw_multi_aff_add_piece(res, common, res_ij);
3101 }
3102 }
3103
3104 isl_pw_multi_aff_free(pma);
3105 return res;
3106 }
3107
3108 /* Extend the local space of "dst" to include the divs
3109 * in the local space of "src".
3110 */
3111 __isl_give isl_aff *isl_aff_align_divs(__isl_take isl_aff *dst,
3112 __isl_keep isl_aff *src)
3113 {
3114 isl_ctx *ctx;
3115 int *exp1 = NULL;
3116 int *exp2 = NULL;
3117 isl_mat *div;
3118
3119 if (!src || !dst)
3120 return isl_aff_free(dst);
3121
3122 ctx = isl_aff_get_ctx(src);
3123 if (!isl_space_is_equal(src->ls->dim, dst->ls->dim))
3124 isl_die(ctx, isl_error_invalid,
3125 "spaces don't match", goto error);
3126
3127 if (src->ls->div->n_row == 0)
3128 return dst;
3129
3130 exp1 = isl_alloc_array(ctx, int, src->ls->div->n_row);
3131 exp2 = isl_alloc_array(ctx, int, dst->ls->div->n_row);
3132 if (!exp1 || !exp2)
3133 goto error;
3134
3135 div = isl_merge_divs(src->ls->div, dst->ls->div, exp1, exp2);
3136 dst = isl_aff_expand_divs(dst, div, exp2);
3137 free(exp1);
3138 free(exp2);
3139
3140 return dst;
3141 error:
3142 free(exp1);
3143 free(exp2);
3144 return isl_aff_free(dst);
3145 }
3146
3147 /* Adjust the local spaces of the affine expressions in "maff"
3148 * such that they all have the save divs.
3149 */
3150 __isl_give isl_multi_aff *isl_multi_aff_align_divs(
3151 __isl_take isl_multi_aff *maff)
3152 {
3153 int i;
3154
3155 if (!maff)
3156 return NULL;
3157 if (maff->n == 0)
3158 return maff;
3159 maff = isl_multi_aff_cow(maff);
3160 if (!maff)
3161 return NULL;
3162
3163 for (i = 1; i < maff->n; ++i)
3164 maff->p[0] = isl_aff_align_divs(maff->p[0], maff->p[i]);
3165 for (i = 1; i < maff->n; ++i) {
3166 maff->p[i] = isl_aff_align_divs(maff->p[i], maff->p[0]);
3167 if (!maff->p[i])
3168 return isl_multi_aff_free(maff);
3169 }
3170
3171 return maff;
3172 }
3173
3174 __isl_give isl_aff *isl_aff_lift(__isl_take isl_aff *aff)
3175 {
3176 aff = isl_aff_cow(aff);
3177 if (!aff)
3178 return NULL;
3179
3180 aff->ls = isl_local_space_lift(aff->ls);
3181 if (!aff->ls)
3182 return isl_aff_free(aff);
3183
3184 return aff;
3185 }
3186
3187 /* Lift "maff" to a space with extra dimensions such that the result
3188 * has no more existentially quantified variables.
3189 * If "ls" is not NULL, then *ls is assigned the local space that lies
3190 * at the basis of the lifting applied to "maff".
3191 */
3192 __isl_give isl_multi_aff *isl_multi_aff_lift(__isl_take isl_multi_aff *maff,
3193 __isl_give isl_local_space **ls)
3194 {
3195 int i;
3196 isl_space *space;
3197 unsigned n_div;
3198
3199 if (ls)
3200 *ls = NULL;
3201
3202 if (!maff)
3203 return NULL;
3204
3205 if (maff->n == 0) {
3206 if (ls) {
3207 isl_space *space = isl_multi_aff_get_domain_space(maff);
3208 *ls = isl_local_space_from_space(space);
3209 if (!*ls)
3210 return isl_multi_aff_free(maff);
3211 }
3212 return maff;
3213 }
3214
3215 maff = isl_multi_aff_cow(maff);
3216 maff = isl_multi_aff_align_divs(maff);
3217 if (!maff)
3218 return NULL;
3219
3220 n_div = isl_aff_dim(maff->p[0], isl_dim_div);
3221 space = isl_multi_aff_get_space(maff);
3222 space = isl_space_lift(isl_space_domain(space), n_div);
3223 space = isl_space_extend_domain_with_range(space,
3224 isl_multi_aff_get_space(maff));
3225 if (!space)
3226 return isl_multi_aff_free(maff);
3227 isl_space_free(maff->space);
3228 maff->space = space;
3229
3230 if (ls) {
3231 *ls = isl_aff_get_domain_local_space(maff->p[0]);
3232 if (!*ls)
3233 return isl_multi_aff_free(maff);
3234 }
3235
3236 for (i = 0; i < maff->n; ++i) {
3237 maff->p[i] = isl_aff_lift(maff->p[i]);
3238 if (!maff->p[i])
3239 goto error;
3240 }
3241
3242 return maff;
3243 error:
3244 if (ls)
3245 isl_local_space_free(*ls);
3246 return isl_multi_aff_free(maff);
3247 }
3248
3249
3250 /* Extract an isl_pw_aff corresponding to output dimension "pos" of "pma".
3251 */
3252 __isl_give isl_pw_aff *isl_pw_multi_aff_get_pw_aff(
3253 __isl_keep isl_pw_multi_aff *pma, int pos)
3254 {
3255 int i;
3256 int n_out;
3257 isl_space *space;
3258 isl_pw_aff *pa;
3259
3260 if (!pma)
3261 return NULL;
3262
3263 n_out = isl_pw_multi_aff_dim(pma, isl_dim_out);
3264 if (pos < 0 || pos >= n_out)
3265 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
3266 "index out of bounds", return NULL);
3267
3268 space = isl_pw_multi_aff_get_space(pma);
3269 space = isl_space_drop_dims(space, isl_dim_out,
3270 pos + 1, n_out - pos - 1);
3271 space = isl_space_drop_dims(space, isl_dim_out, 0, pos);
3272
3273 pa = isl_pw_aff_alloc_size(space, pma->n);
3274 for (i = 0; i < pma->n; ++i) {
3275 isl_aff *aff;
3276 aff = isl_multi_aff_get_aff(pma->p[i].maff, pos);
3277 pa = isl_pw_aff_add_piece(pa, isl_set_copy(pma->p[i].set), aff);
3278 }
3279
3280 return pa;
3281 }
3282
3283 /* Return an isl_pw_multi_aff with the given "set" as domain and
3284 * an unnamed zero-dimensional range.
3285 */
3286 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_domain(
3287 __isl_take isl_set *set)
3288 {
3289 isl_multi_aff *ma;
3290 isl_space *space;
3291
3292 space = isl_set_get_space(set);
3293 space = isl_space_from_domain(space);
3294 ma = isl_multi_aff_zero(space);
3295 return isl_pw_multi_aff_alloc(set, ma);
3296 }
3297
3298 /* Add an isl_pw_multi_aff with the given "set" as domain and
3299 * an unnamed zero-dimensional range to *user.
3300 */
3301 static int add_pw_multi_aff_from_domain(__isl_take isl_set *set, void *user)
3302 {
3303 isl_union_pw_multi_aff **upma = user;
3304 isl_pw_multi_aff *pma;
3305
3306 pma = isl_pw_multi_aff_from_domain(set);
3307 *upma = isl_union_pw_multi_aff_add_pw_multi_aff(*upma, pma);
3308
3309 return 0;
3310 }
3311
3312 /* Return an isl_union_pw_multi_aff with the given "uset" as domain and
3313 * an unnamed zero-dimensional range.
3314 */
3315 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_from_domain(
3316 __isl_take isl_union_set *uset)
3317 {
3318 isl_space *space;
3319 isl_union_pw_multi_aff *upma;
3320
3321 if (!uset)
3322 return NULL;
3323
3324 space = isl_union_set_get_space(uset);
3325 upma = isl_union_pw_multi_aff_empty(space);
3326
3327 if (isl_union_set_foreach_set(uset,
3328 &add_pw_multi_aff_from_domain, &upma) < 0)
3329 goto error;
3330
3331 isl_union_set_free(uset);
3332 return upma;
3333 error:
3334 isl_union_set_free(uset);
3335 isl_union_pw_multi_aff_free(upma);
3336 return NULL;
3337 }
3338
3339 /* Convert "pma" to an isl_map and add it to *umap.
3340 */
3341 static int map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma, void *user)
3342 {
3343 isl_union_map **umap = user;
3344 isl_map *map;
3345
3346 map = isl_map_from_pw_multi_aff(pma);
3347 *umap = isl_union_map_add_map(*umap, map);
3348
3349 return 0;
3350 }
3351
3352 /* Construct a union map mapping the domain of the union
3353 * piecewise multi-affine expression to its range, with each dimension
3354 * in the range equated to the corresponding affine expression on its cell.
3355 */
3356 __isl_give isl_union_map *isl_union_map_from_union_pw_multi_aff(
3357 __isl_take isl_union_pw_multi_aff *upma)
3358 {
3359 isl_space *space;
3360 isl_union_map *umap;
3361
3362 if (!upma)
3363 return NULL;
3364
3365 space = isl_union_pw_multi_aff_get_space(upma);
3366 umap = isl_union_map_empty(space);
3367
3368 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma,
3369 &map_from_pw_multi_aff, &umap) < 0)
3370 goto error;
3371
3372 isl_union_pw_multi_aff_free(upma);
3373 return umap;
3374 error:
3375 isl_union_pw_multi_aff_free(upma);
3376 isl_union_map_free(umap);
3377 return NULL;
3378 }
3379
3380 /* Local data for bin_entry and the callback "fn".
3381 */
3382 struct isl_union_pw_multi_aff_bin_data {
3383 isl_union_pw_multi_aff *upma2;
3384 isl_union_pw_multi_aff *res;
3385 isl_pw_multi_aff *pma;
3386 int (*fn)(void **entry, void *user);
3387 };
3388
3389 /* Given an isl_pw_multi_aff from upma1, store it in data->pma
3390 * and call data->fn for each isl_pw_multi_aff in data->upma2.
3391 */
3392 static int bin_entry(void **entry, void *user)
3393 {
3394 struct isl_union_pw_multi_aff_bin_data *data = user;
3395 isl_pw_multi_aff *pma = *entry;
3396
3397 data->pma = pma;
3398 if (isl_hash_table_foreach(data->upma2->dim->ctx, &data->upma2->table,
3399 data->fn, data) < 0)
3400 return -1;
3401
3402 return 0;
3403 }
3404
3405 /* Call "fn" on each pair of isl_pw_multi_affs in "upma1" and "upma2".
3406 * The isl_pw_multi_aff from upma1 is stored in data->pma (where data is
3407 * passed as user field) and the isl_pw_multi_aff from upma2 is available
3408 * as *entry. The callback should adjust data->res if desired.
3409 */
3410 static __isl_give isl_union_pw_multi_aff *bin_op(
3411 __isl_take isl_union_pw_multi_aff *upma1,
3412 __isl_take isl_union_pw_multi_aff *upma2,
3413 int (*fn)(void **entry, void *user))
3414 {
3415 isl_space *space;
3416 struct isl_union_pw_multi_aff_bin_data data = { NULL, NULL, NULL, fn };
3417
3418 space = isl_union_pw_multi_aff_get_space(upma2);
3419 upma1 = isl_union_pw_multi_aff_align_params(upma1, space);
3420 space = isl_union_pw_multi_aff_get_space(upma1);
3421 upma2 = isl_union_pw_multi_aff_align_params(upma2, space);
3422
3423 if (!upma1 || !upma2)
3424 goto error;
3425
3426 data.upma2 = upma2;
3427 data.res = isl_union_pw_multi_aff_alloc(isl_space_copy(upma1->dim),
3428 upma1->table.n);
3429 if (isl_hash_table_foreach(upma1->dim->ctx, &upma1->table,
3430 &bin_entry, &data) < 0)
3431 goto error;
3432
3433 isl_union_pw_multi_aff_free(upma1);
3434 isl_union_pw_multi_aff_free(upma2);
3435 return data.res;
3436 error:
3437 isl_union_pw_multi_aff_free(upma1);
3438 isl_union_pw_multi_aff_free(upma2);
3439 isl_union_pw_multi_aff_free(data.res);
3440 return NULL;
3441 }
3442
3443 /* Given two isl_multi_affs A -> B and C -> D,
3444 * construct an isl_multi_aff (A * C) -> (B, D).
3445 */
3446 __isl_give isl_multi_aff *isl_multi_aff_flat_range_product(
3447 __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2)
3448 {
3449 int i, n1, n2;
3450 isl_aff *aff;
3451 isl_space *space;
3452 isl_multi_aff *res;
3453
3454 if (!ma1 || !ma2)
3455 goto error;
3456
3457 space = isl_space_range_product(isl_multi_aff_get_space(ma1),
3458 isl_multi_aff_get_space(ma2));
3459 space = isl_space_flatten_range(space);
3460 res = isl_multi_aff_alloc(space);
3461
3462 n1 = isl_multi_aff_dim(ma1, isl_dim_out);
3463 n2 = isl_multi_aff_dim(ma2, isl_dim_out);
3464
3465 for (i = 0; i < n1; ++i) {
3466 aff = isl_multi_aff_get_aff(ma1, i);
3467 res = isl_multi_aff_set_aff(res, i, aff);
3468 }
3469
3470 for (i = 0; i < n2; ++i) {
3471 aff = isl_multi_aff_get_aff(ma2, i);
3472 res = isl_multi_aff_set_aff(res, n1 + i, aff);
3473 }
3474
3475 isl_multi_aff_free(ma1);
3476 isl_multi_aff_free(ma2);
3477 return res;
3478 error:
3479 isl_multi_aff_free(ma1);
3480 isl_multi_aff_free(ma2);
3481 return NULL;
3482 }
3483
3484 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
3485 * construct an isl_pw_multi_aff (A * C) -> (B, D).
3486 */
3487 static __isl_give isl_pw_multi_aff *pw_multi_aff_flat_range_product(
3488 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
3489 {
3490 isl_space *space;
3491
3492 space = isl_space_range_product(isl_pw_multi_aff_get_space(pma1),
3493 isl_pw_multi_aff_get_space(pma2));
3494 space = isl_space_flatten_range(space);
3495 return isl_pw_multi_aff_on_shared_domain_in(pma1, pma2, space,
3496 &isl_multi_aff_flat_range_product);
3497 }
3498
3499 /* Given two isl_pw_multi_affs A -> B and C -> D,
3500 * construct an isl_pw_multi_aff (A * C) -> (B, D).
3501 */
3502 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_flat_range_product(
3503 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
3504 {
3505 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
3506 &pw_multi_aff_flat_range_product);
3507 }
3508
3509 /* If data->pma and *entry have the same domain space, then compute
3510 * their flat range product and the result to data->res.
3511 */
3512 static int flat_range_product_entry(void **entry, void *user)
3513 {
3514 struct isl_union_pw_multi_aff_bin_data *data = user;
3515 isl_pw_multi_aff *pma2 = *entry;
3516
3517 if (!isl_space_tuple_match(data->pma->dim, isl_dim_in,
3518 pma2->dim, isl_dim_in))
3519 return 0;
3520
3521 pma2 = isl_pw_multi_aff_flat_range_product(
3522 isl_pw_multi_aff_copy(data->pma),
3523 isl_pw_multi_aff_copy(pma2));
3524
3525 data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, pma2);
3526
3527 return 0;
3528 }
3529
3530 /* Given two isl_union_pw_multi_affs A -> B and C -> D,
3531 * construct an isl_union_pw_multi_aff (A * C) -> (B, D).
3532 */
3533 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_flat_range_product(
3534 __isl_take isl_union_pw_multi_aff *upma1,
3535 __isl_take isl_union_pw_multi_aff *upma2)
3536 {
3537 return bin_op(upma1, upma2, &flat_range_product_entry);
3538 }
Integer set library