?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
add isl_aff_normalize
[isl.git] / isl_aff.c
blob71e15a30c6dbf8f57c2287994df8028792ad86fd
1 /*
2 * Copyright 2011 INRIA Saclay
3 * Copyright 2011 Sven Verdoolaege
4 *
5 * Use of this software is governed by the GNU LGPLv2.1 license
6 *
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
9 * 91893 Orsay, France
10 */
11
12 #include <isl_ctx_private.h>
13 #include <isl_map_private.h>
14 #include <isl_aff_private.h>
15 #include <isl_space_private.h>
16 #include <isl_local_space_private.h>
17 #include <isl_mat_private.h>
18 #include <isl_list_private.h>
19 #include <isl/constraint.h>
20 #include <isl/seq.h>
21 #include <isl/set.h>
22
23 __isl_give isl_aff *isl_aff_alloc_vec(__isl_take isl_local_space *ls,
24 __isl_take isl_vec *v)
25 {
26 isl_aff *aff;
27
28 if (!ls || !v)
29 goto error;
30
31 aff = isl_calloc_type(v->ctx, struct isl_aff);
32 if (!aff)
33 goto error;
34
35 aff->ref = 1;
36 aff->ls = ls;
37 aff->v = v;
38
39 return aff;
40 error:
41 isl_local_space_free(ls);
42 isl_vec_free(v);
43 return NULL;
44 }
45
46 __isl_give isl_aff *isl_aff_alloc(__isl_take isl_local_space *ls)
47 {
48 isl_ctx *ctx;
49 isl_vec *v;
50 unsigned total;
51
52 if (!ls)
53 return NULL;
54
55 ctx = isl_local_space_get_ctx(ls);
56 if (!isl_local_space_divs_known(ls))
57 isl_die(ctx, isl_error_invalid, "local space has unknown divs",
58 goto error);
59 if (!isl_local_space_is_set(ls))
60 isl_die(ctx, isl_error_invalid,
61 "domain of affine expression should be a set",
62 goto error);
63
64 total = isl_local_space_dim(ls, isl_dim_all);
65 v = isl_vec_alloc(ctx, 1 + 1 + total);
66 return isl_aff_alloc_vec(ls, v);
67 error:
68 isl_local_space_free(ls);
69 return NULL;
70 }
71
72 __isl_give isl_aff *isl_aff_zero_on_domain(__isl_take isl_local_space *ls)
73 {
74 isl_aff *aff;
75
76 aff = isl_aff_alloc(ls);
77 if (!aff)
78 return NULL;
79
80 isl_int_set_si(aff->v->el[0], 1);
81 isl_seq_clr(aff->v->el + 1, aff->v->size - 1);
82
83 return aff;
84 }
85
86 __isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff)
87 {
88 if (!aff)
89 return NULL;
90
91 aff->ref++;
92 return aff;
93 }
94
95 __isl_give isl_aff *isl_aff_dup(__isl_keep isl_aff *aff)
96 {
97 if (!aff)
98 return NULL;
99
100 return isl_aff_alloc_vec(isl_local_space_copy(aff->ls),
101 isl_vec_copy(aff->v));
102 }
103
104 __isl_give isl_aff *isl_aff_cow(__isl_take isl_aff *aff)
105 {
106 if (!aff)
107 return NULL;
108
109 if (aff->ref == 1)
110 return aff;
111 aff->ref--;
112 return isl_aff_dup(aff);
113 }
114
115 void *isl_aff_free(__isl_take isl_aff *aff)
116 {
117 if (!aff)
118 return NULL;
119
120 if (--aff->ref > 0)
121 return NULL;
122
123 isl_local_space_free(aff->ls);
124 isl_vec_free(aff->v);
125
126 free(aff);
127
128 return NULL;
129 }
130
131 isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff)
132 {
133 return aff ? isl_local_space_get_ctx(aff->ls) : NULL;
134 }
135
136 /* Externally, an isl_aff has a map space, but internally, the
137 * ls field corresponds to the domain of that space.
138 */
139 int isl_aff_dim(__isl_keep isl_aff *aff, enum isl_dim_type type)
140 {
141 if (!aff)
142 return 0;
143 if (type == isl_dim_out)
144 return 1;
145 if (type == isl_dim_in)
146 type = isl_dim_set;
147 return isl_local_space_dim(aff->ls, type);
148 }
149
150 __isl_give isl_space *isl_aff_get_domain_space(__isl_keep isl_aff *aff)
151 {
152 return aff ? isl_local_space_get_space(aff->ls) : NULL;
153 }
154
155 __isl_give isl_space *isl_aff_get_space(__isl_keep isl_aff *aff)
156 {
157 isl_space *space;
158 if (!aff)
159 return NULL;
160 space = isl_local_space_get_space(aff->ls);
161 space = isl_space_from_domain(space);
162 space = isl_space_add_dims(space, isl_dim_out, 1);
163 return space;
164 }
165
166 __isl_give isl_local_space *isl_aff_get_domain_local_space(
167 __isl_keep isl_aff *aff)
168 {
169 return aff ? isl_local_space_copy(aff->ls) : NULL;
170 }
171
172 __isl_give isl_local_space *isl_aff_get_local_space(__isl_keep isl_aff *aff)
173 {
174 isl_local_space *ls;
175 if (!aff)
176 return NULL;
177 ls = isl_local_space_copy(aff->ls);
178 ls = isl_local_space_from_domain(ls);
179 ls = isl_local_space_add_dims(ls, isl_dim_out, 1);
180 return ls;
181 }
182
183 /* Externally, an isl_aff has a map space, but internally, the
184 * ls field corresponds to the domain of that space.
185 */
186 const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff,
187 enum isl_dim_type type, unsigned pos)
188 {
189 if (!aff)
190 return NULL;
191 if (type == isl_dim_out)
192 return NULL;
193 if (type == isl_dim_in)
194 type = isl_dim_set;
195 return isl_local_space_get_dim_name(aff->ls, type, pos);
196 }
197
198 __isl_give isl_aff *isl_aff_reset_domain_space(__isl_take isl_aff *aff,
199 __isl_take isl_space *dim)
200 {
201 aff = isl_aff_cow(aff);
202 if (!aff || !dim)
203 goto error;
204
205 aff->ls = isl_local_space_reset_space(aff->ls, dim);
206 if (!aff->ls)
207 return isl_aff_free(aff);
208
209 return aff;
210 error:
211 isl_aff_free(aff);
212 isl_space_free(dim);
213 return NULL;
214 }
215
216 /* Reset the space of "aff". This function is called from isl_pw_templ.c
217 * and doesn't know if the space of an element object is represented
218 * directly or through its domain. It therefore passes along both.
219 */
220 __isl_give isl_aff *isl_aff_reset_space_and_domain(__isl_take isl_aff *aff,
221 __isl_take isl_space *space, __isl_take isl_space *domain)
222 {
223 isl_space_free(space);
224 return isl_aff_reset_domain_space(aff, domain);
225 }
226
227 /* Reorder the coefficients of the affine expression based
228 * on the given reodering.
229 * The reordering r is assumed to have been extended with the local
230 * variables.
231 */
232 static __isl_give isl_vec *vec_reorder(__isl_take isl_vec *vec,
233 __isl_take isl_reordering *r, int n_div)
234 {
235 isl_vec *res;
236 int i;
237
238 if (!vec || !r)
239 goto error;
240
241 res = isl_vec_alloc(vec->ctx,
242 2 + isl_space_dim(r->dim, isl_dim_all) + n_div);
243 isl_seq_cpy(res->el, vec->el, 2);
244 isl_seq_clr(res->el + 2, res->size - 2);
245 for (i = 0; i < r->len; ++i)
246 isl_int_set(res->el[2 + r->pos[i]], vec->el[2 + i]);
247
248 isl_reordering_free(r);
249 isl_vec_free(vec);
250 return res;
251 error:
252 isl_vec_free(vec);
253 isl_reordering_free(r);
254 return NULL;
255 }
256
257 /* Reorder the dimensions of the domain of "aff" according
258 * to the given reordering.
259 */
260 __isl_give isl_aff *isl_aff_realign_domain(__isl_take isl_aff *aff,
261 __isl_take isl_reordering *r)
262 {
263 aff = isl_aff_cow(aff);
264 if (!aff)
265 goto error;
266
267 r = isl_reordering_extend(r, aff->ls->div->n_row);
268 aff->v = vec_reorder(aff->v, isl_reordering_copy(r),
269 aff->ls->div->n_row);
270 aff->ls = isl_local_space_realign(aff->ls, r);
271
272 if (!aff->v || !aff->ls)
273 return isl_aff_free(aff);
274
275 return aff;
276 error:
277 isl_aff_free(aff);
278 isl_reordering_free(r);
279 return NULL;
280 }
281
282 int isl_aff_plain_is_zero(__isl_keep isl_aff *aff)
283 {
284 if (!aff)
285 return -1;
286
287 return isl_seq_first_non_zero(aff->v->el + 1, aff->v->size - 1) < 0;
288 }
289
290 int isl_aff_plain_is_equal(__isl_keep isl_aff *aff1, __isl_keep isl_aff *aff2)
291 {
292 int equal;
293
294 if (!aff1 || !aff2)
295 return -1;
296
297 equal = isl_local_space_is_equal(aff1->ls, aff2->ls);
298 if (equal < 0 || !equal)
299 return equal;
300
301 return isl_vec_is_equal(aff1->v, aff2->v);
302 }
303
304 int isl_aff_get_denominator(__isl_keep isl_aff *aff, isl_int *v)
305 {
306 if (!aff)
307 return -1;
308 isl_int_set(*v, aff->v->el[0]);
309 return 0;
310 }
311
312 int isl_aff_get_constant(__isl_keep isl_aff *aff, isl_int *v)
313 {
314 if (!aff)
315 return -1;
316 isl_int_set(*v, aff->v->el[1]);
317 return 0;
318 }
319
320 int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
321 enum isl_dim_type type, int pos, isl_int *v)
322 {
323 if (!aff)
324 return -1;
325
326 if (type == isl_dim_out)
327 isl_die(aff->v->ctx, isl_error_invalid,
328 "output/set dimension does not have a coefficient",
329 return -1);
330 if (type == isl_dim_in)
331 type = isl_dim_set;
332
333 if (pos >= isl_local_space_dim(aff->ls, type))
334 isl_die(aff->v->ctx, isl_error_invalid,
335 "position out of bounds", return -1);
336
337 pos += isl_local_space_offset(aff->ls, type);
338 isl_int_set(*v, aff->v->el[1 + pos]);
339
340 return 0;
341 }
342
343 __isl_give isl_aff *isl_aff_set_denominator(__isl_take isl_aff *aff, isl_int v)
344 {
345 aff = isl_aff_cow(aff);
346 if (!aff)
347 return NULL;
348
349 aff->v = isl_vec_cow(aff->v);
350 if (!aff->v)
351 return isl_aff_free(aff);
352
353 isl_int_set(aff->v->el[0], v);
354
355 return aff;
356 }
357
358 __isl_give isl_aff *isl_aff_set_constant(__isl_take isl_aff *aff, isl_int v)
359 {
360 aff = isl_aff_cow(aff);
361 if (!aff)
362 return NULL;
363
364 aff->v = isl_vec_cow(aff->v);
365 if (!aff->v)
366 return isl_aff_free(aff);
367
368 isl_int_set(aff->v->el[1], v);
369
370 return aff;
371 }
372
373 __isl_give isl_aff *isl_aff_add_constant(__isl_take isl_aff *aff, isl_int v)
374 {
375 if (isl_int_is_zero(v))
376 return aff;
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_addmul(aff->v->el[1], aff->v->el[0], v);
387
388 return aff;
389 }
390
391 __isl_give isl_aff *isl_aff_add_constant_si(__isl_take isl_aff *aff, int v)
392 {
393 isl_int t;
394
395 isl_int_init(t);
396 isl_int_set_si(t, v);
397 aff = isl_aff_add_constant(aff, t);
398 isl_int_clear(t);
399
400 return aff;
401 }
402
403 __isl_give isl_aff *isl_aff_set_constant_si(__isl_take isl_aff *aff, int v)
404 {
405 aff = isl_aff_cow(aff);
406 if (!aff)
407 return NULL;
408
409 aff->v = isl_vec_cow(aff->v);
410 if (!aff->v)
411 return isl_aff_free(aff);
412
413 isl_int_set_si(aff->v->el[1], v);
414
415 return aff;
416 }
417
418 __isl_give isl_aff *isl_aff_set_coefficient(__isl_take isl_aff *aff,
419 enum isl_dim_type type, int pos, isl_int v)
420 {
421 if (!aff)
422 return NULL;
423
424 if (type == isl_dim_out)
425 isl_die(aff->v->ctx, isl_error_invalid,
426 "output/set dimension does not have a coefficient",
427 return isl_aff_free(aff));
428 if (type == isl_dim_in)
429 type = isl_dim_set;
430
431 if (pos >= isl_local_space_dim(aff->ls, type))
432 isl_die(aff->v->ctx, isl_error_invalid,
433 "position out of bounds", return isl_aff_free(aff));
434
435 aff = isl_aff_cow(aff);
436 if (!aff)
437 return NULL;
438
439 aff->v = isl_vec_cow(aff->v);
440 if (!aff->v)
441 return isl_aff_free(aff);
442
443 pos += isl_local_space_offset(aff->ls, type);
444 isl_int_set(aff->v->el[1 + pos], v);
445
446 return aff;
447 }
448
449 __isl_give isl_aff *isl_aff_set_coefficient_si(__isl_take isl_aff *aff,
450 enum isl_dim_type type, int pos, int v)
451 {
452 if (!aff)
453 return NULL;
454
455 if (type == isl_dim_out)
456 isl_die(aff->v->ctx, isl_error_invalid,
457 "output/set dimension does not have a coefficient",
458 return isl_aff_free(aff));
459 if (type == isl_dim_in)
460 type = isl_dim_set;
461
462 if (pos >= isl_local_space_dim(aff->ls, type))
463 isl_die(aff->v->ctx, isl_error_invalid,
464 "position out of bounds", return isl_aff_free(aff));
465
466 aff = isl_aff_cow(aff);
467 if (!aff)
468 return NULL;
469
470 aff->v = isl_vec_cow(aff->v);
471 if (!aff->v)
472 return isl_aff_free(aff);
473
474 pos += isl_local_space_offset(aff->ls, type);
475 isl_int_set_si(aff->v->el[1 + pos], v);
476
477 return aff;
478 }
479
480 __isl_give isl_aff *isl_aff_add_coefficient(__isl_take isl_aff *aff,
481 enum isl_dim_type type, int pos, isl_int v)
482 {
483 if (!aff)
484 return NULL;
485
486 if (type == isl_dim_out)
487 isl_die(aff->v->ctx, isl_error_invalid,
488 "output/set dimension does not have a coefficient",
489 return isl_aff_free(aff));
490 if (type == isl_dim_in)
491 type = isl_dim_set;
492
493 if (pos >= isl_local_space_dim(aff->ls, type))
494 isl_die(aff->v->ctx, isl_error_invalid,
495 "position out of bounds", return isl_aff_free(aff));
496
497 aff = isl_aff_cow(aff);
498 if (!aff)
499 return NULL;
500
501 aff->v = isl_vec_cow(aff->v);
502 if (!aff->v)
503 return isl_aff_free(aff);
504
505 pos += isl_local_space_offset(aff->ls, type);
506 isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v);
507
508 return aff;
509 }
510
511 __isl_give isl_aff *isl_aff_add_coefficient_si(__isl_take isl_aff *aff,
512 enum isl_dim_type type, int pos, int v)
513 {
514 isl_int t;
515
516 isl_int_init(t);
517 isl_int_set_si(t, v);
518 aff = isl_aff_add_coefficient(aff, type, pos, t);
519 isl_int_clear(t);
520
521 return aff;
522 }
523
524 __isl_give isl_aff *isl_aff_get_div(__isl_keep isl_aff *aff, int pos)
525 {
526 if (!aff)
527 return NULL;
528
529 return isl_local_space_get_div(aff->ls, pos);
530 }
531
532 __isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff)
533 {
534 aff = isl_aff_cow(aff);
535 if (!aff)
536 return NULL;
537 aff->v = isl_vec_cow(aff->v);
538 if (!aff->v)
539 return isl_aff_free(aff);
540
541 isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1);
542
543 return aff;
544 }
545
546 __isl_give isl_aff *isl_aff_normalize(__isl_take isl_aff *aff)
547 {
548 if (!aff)
549 return NULL;
550 aff->v = isl_vec_normalize(aff->v);
551 if (!aff->v)
552 return isl_aff_free(aff);
553 return aff;
554 }
555
556 /* Given f, return floor(f).
557 * If f is an integer expression, then just return f.
558 * Otherwise, if f = g/m, write g = q m + r,
559 * create a new div d = [r/m] and return the expression q + d.
560 * The coefficients in r are taken to lie between -m/2 and m/2.
561 */
562 __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
563 {
564 int i;
565 int size;
566 isl_ctx *ctx;
567 isl_vec *div;
568
569 if (!aff)
570 return NULL;
571
572 if (isl_int_is_one(aff->v->el[0]))
573 return aff;
574
575 aff = isl_aff_cow(aff);
576 if (!aff)
577 return NULL;
578
579 aff->v = isl_vec_cow(aff->v);
580 div = isl_vec_copy(aff->v);
581 div = isl_vec_cow(div);
582 if (!div)
583 return isl_aff_free(aff);
584
585 ctx = isl_aff_get_ctx(aff);
586 isl_int_fdiv_q(aff->v->el[0], aff->v->el[0], ctx->two);
587 for (i = 1; i < aff->v->size; ++i) {
588 isl_int_fdiv_r(div->el[i], div->el[i], div->el[0]);
589 isl_int_fdiv_q(aff->v->el[i], aff->v->el[i], div->el[0]);
590 if (isl_int_gt(div->el[i], aff->v->el[0])) {
591 isl_int_sub(div->el[i], div->el[i], div->el[0]);
592 isl_int_add_ui(aff->v->el[i], aff->v->el[i], 1);
593 }
594 }
595
596 aff->ls = isl_local_space_add_div(aff->ls, div);
597 if (!aff->ls)
598 return isl_aff_free(aff);
599
600 size = aff->v->size;
601 aff->v = isl_vec_extend(aff->v, size + 1);
602 if (!aff->v)
603 return isl_aff_free(aff);
604 isl_int_set_si(aff->v->el[0], 1);
605 isl_int_set_si(aff->v->el[size], 1);
606
607 return aff;
608 }
609
610 /* Compute
611 *
612 * aff mod m = aff - m * floor(aff/m)
613 */
614 __isl_give isl_aff *isl_aff_mod(__isl_take isl_aff *aff, isl_int m)
615 {
616 isl_aff *res;
617
618 res = isl_aff_copy(aff);
619 aff = isl_aff_scale_down(aff, m);
620 aff = isl_aff_floor(aff);
621 aff = isl_aff_scale(aff, m);
622 res = isl_aff_sub(res, aff);
623
624 return res;
625 }
626
627 /* Compute
628 *
629 * pwaff mod m = pwaff - m * floor(pwaff/m)
630 */
631 __isl_give isl_pw_aff *isl_pw_aff_mod(__isl_take isl_pw_aff *pwaff, isl_int m)
632 {
633 isl_pw_aff *res;
634
635 res = isl_pw_aff_copy(pwaff);
636 pwaff = isl_pw_aff_scale_down(pwaff, m);
637 pwaff = isl_pw_aff_floor(pwaff);
638 pwaff = isl_pw_aff_scale(pwaff, m);
639 res = isl_pw_aff_sub(res, pwaff);
640
641 return res;
642 }
643
644 /* Given f, return ceil(f).
645 * If f is an integer expression, then just return f.
646 * Otherwise, create a new div d = [-f] and return the expression -d.
647 */
648 __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
649 {
650 if (!aff)
651 return NULL;
652
653 if (isl_int_is_one(aff->v->el[0]))
654 return aff;
655
656 aff = isl_aff_neg(aff);
657 aff = isl_aff_floor(aff);
658 aff = isl_aff_neg(aff);
659
660 return aff;
661 }
662
663 /* Apply the expansion computed by isl_merge_divs.
664 * The expansion itself is given by "exp" while the resulting
665 * list of divs is given by "div".
666 */
667 __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
668 __isl_take isl_mat *div, int *exp)
669 {
670 int i, j;
671 int old_n_div;
672 int new_n_div;
673 int offset;
674
675 aff = isl_aff_cow(aff);
676 if (!aff || !div)
677 goto error;
678
679 old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
680 new_n_div = isl_mat_rows(div);
681 if (new_n_div < old_n_div)
682 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
683 "not an expansion", goto error);
684
685 aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div);
686 if (!aff->v)
687 goto error;
688
689 offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
690 j = old_n_div - 1;
691 for (i = new_n_div - 1; i >= 0; --i) {
692 if (j >= 0 && exp[j] == i) {
693 if (i != j)
694 isl_int_swap(aff->v->el[offset + i],
695 aff->v->el[offset + j]);
696 j--;
697 } else
698 isl_int_set_si(aff->v->el[offset + i], 0);
699 }
700
701 aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div));
702 if (!aff->ls)
703 goto error;
704 isl_mat_free(div);
705 return aff;
706 error:
707 isl_aff_free(aff);
708 isl_mat_free(div);
709 return NULL;
710 }
711
712 /* Add two affine expressions that live in the same local space.
713 */
714 static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
715 __isl_take isl_aff *aff2)
716 {
717 isl_int gcd, f;
718
719 aff1 = isl_aff_cow(aff1);
720 if (!aff1 || !aff2)
721 goto error;
722
723 aff1->v = isl_vec_cow(aff1->v);
724 if (!aff1->v)
725 goto error;
726
727 isl_int_init(gcd);
728 isl_int_init(f);
729 isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
730 isl_int_divexact(f, aff2->v->el[0], gcd);
731 isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
732 isl_int_divexact(f, aff1->v->el[0], gcd);
733 isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
734 isl_int_divexact(f, aff2->v->el[0], gcd);
735 isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
736 isl_int_clear(f);
737 isl_int_clear(gcd);
738
739 isl_aff_free(aff2);
740 return aff1;
741 error:
742 isl_aff_free(aff1);
743 isl_aff_free(aff2);
744 return NULL;
745 }
746
747 __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
748 __isl_take isl_aff *aff2)
749 {
750 isl_ctx *ctx;
751 int *exp1 = NULL;
752 int *exp2 = NULL;
753 isl_mat *div;
754
755 if (!aff1 || !aff2)
756 goto error;
757
758 ctx = isl_aff_get_ctx(aff1);
759 if (!isl_space_is_equal(aff1->ls->dim, aff2->ls->dim))
760 isl_die(ctx, isl_error_invalid,
761 "spaces don't match", goto error);
762
763 if (aff1->ls->div->n_row == 0 && aff2->ls->div->n_row == 0)
764 return add_expanded(aff1, aff2);
765
766 exp1 = isl_alloc_array(ctx, int, aff1->ls->div->n_row);
767 exp2 = isl_alloc_array(ctx, int, aff2->ls->div->n_row);
768 if (!exp1 || !exp2)
769 goto error;
770
771 div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
772 aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
773 aff2 = isl_aff_expand_divs(aff2, div, exp2);
774 free(exp1);
775 free(exp2);
776
777 return add_expanded(aff1, aff2);
778 error:
779 free(exp1);
780 free(exp2);
781 isl_aff_free(aff1);
782 isl_aff_free(aff2);
783 return NULL;
784 }
785
786 __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
787 __isl_take isl_aff *aff2)
788 {
789 return isl_aff_add(aff1, isl_aff_neg(aff2));
790 }
791
792 __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
793 {
794 isl_int gcd;
795
796 if (isl_int_is_one(f))
797 return aff;
798
799 aff = isl_aff_cow(aff);
800 if (!aff)
801 return NULL;
802 aff->v = isl_vec_cow(aff->v);
803 if (!aff->v)
804 return isl_aff_free(aff);
805
806 isl_int_init(gcd);
807 isl_int_gcd(gcd, aff->v->el[0], f);
808 isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
809 isl_int_divexact(gcd, f, gcd);
810 isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
811 isl_int_clear(gcd);
812
813 return aff;
814 }
815
816 __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
817 {
818 isl_int gcd;
819
820 if (isl_int_is_one(f))
821 return aff;
822
823 aff = isl_aff_cow(aff);
824 if (!aff)
825 return NULL;
826 aff->v = isl_vec_cow(aff->v);
827 if (!aff->v)
828 return isl_aff_free(aff);
829
830 isl_int_init(gcd);
831 isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
832 isl_int_gcd(gcd, gcd, f);
833 isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
834 isl_int_divexact(gcd, f, gcd);
835 isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
836 isl_int_clear(gcd);
837
838 return aff;
839 }
840
841 __isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f)
842 {
843 isl_int v;
844
845 if (f == 1)
846 return aff;
847
848 isl_int_init(v);
849 isl_int_set_ui(v, f);
850 aff = isl_aff_scale_down(aff, v);
851 isl_int_clear(v);
852
853 return aff;
854 }
855
856 __isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff,
857 enum isl_dim_type type, unsigned pos, const char *s)
858 {
859 aff = isl_aff_cow(aff);
860 if (!aff)
861 return NULL;
862 if (type == isl_dim_out)
863 isl_die(aff->v->ctx, isl_error_invalid,
864 "cannot set name of output/set dimension",
865 return isl_aff_free(aff));
866 if (type == isl_dim_in)
867 type = isl_dim_set;
868 aff->ls = isl_local_space_set_dim_name(aff->ls, type, pos, s);
869 if (!aff->ls)
870 return isl_aff_free(aff);
871
872 return aff;
873 }
874
875 __isl_give isl_aff *isl_aff_set_dim_id(__isl_take isl_aff *aff,
876 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
877 {
878 aff = isl_aff_cow(aff);
879 if (!aff)
880 return isl_id_free(id);
881 if (type == isl_dim_out)
882 isl_die(aff->v->ctx, isl_error_invalid,
883 "cannot set name of output/set dimension",
884 goto error);
885 if (type == isl_dim_in)
886 type = isl_dim_set;
887 aff->ls = isl_local_space_set_dim_id(aff->ls, type, pos, id);
888 if (!aff->ls)
889 return isl_aff_free(aff);
890
891 return aff;
892 error:
893 isl_id_free(id);
894 isl_aff_free(aff);
895 return NULL;
896 }
897
898 /* Exploit the equalities in "eq" to simplify the affine expression
899 * and the expressions of the integer divisions in the local space.
900 * The integer divisions in this local space are assumed to appear
901 * as regular dimensions in "eq".
902 */
903 static __isl_give isl_aff *isl_aff_substitute_equalities_lifted(
904 __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
905 {
906 int i, j;
907 unsigned total;
908 unsigned n_div;
909
910 if (!eq)
911 goto error;
912 if (eq->n_eq == 0) {
913 isl_basic_set_free(eq);
914 return aff;
915 }
916
917 aff = isl_aff_cow(aff);
918 if (!aff)
919 goto error;
920
921 aff->ls = isl_local_space_substitute_equalities(aff->ls,
922 isl_basic_set_copy(eq));
923 if (!aff->ls)
924 goto error;
925
926 total = 1 + isl_space_dim(eq->dim, isl_dim_all);
927 n_div = eq->n_div;
928 for (i = 0; i < eq->n_eq; ++i) {
929 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
930 if (j < 0 || j == 0 || j >= total)
931 continue;
932
933 isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total,
934 &aff->v->el[0]);
935 }
936
937 isl_basic_set_free(eq);
938 return aff;
939 error:
940 isl_basic_set_free(eq);
941 isl_aff_free(aff);
942 return NULL;
943 }
944
945 /* Exploit the equalities in "eq" to simplify the affine expression
946 * and the expressions of the integer divisions in the local space.
947 */
948 static __isl_give isl_aff *isl_aff_substitute_equalities(
949 __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
950 {
951 int n_div;
952
953 if (!aff || !eq)
954 goto error;
955 n_div = isl_local_space_dim(aff->ls, isl_dim_div);
956 if (n_div > 0)
957 eq = isl_basic_set_add(eq, isl_dim_set, n_div);
958 return isl_aff_substitute_equalities_lifted(aff, eq);
959 error:
960 isl_basic_set_free(eq);
961 isl_aff_free(aff);
962 return NULL;
963 }
964
965 /* Look for equalities among the variables shared by context and aff
966 * and the integer divisions of aff, if any.
967 * The equalities are then used to eliminate coefficients and/or integer
968 * divisions from aff.
969 */
970 __isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
971 __isl_take isl_set *context)
972 {
973 isl_basic_set *hull;
974 int n_div;
975
976 if (!aff)
977 goto error;
978 n_div = isl_local_space_dim(aff->ls, isl_dim_div);
979 if (n_div > 0) {
980 isl_basic_set *bset;
981 isl_local_space *ls;
982 context = isl_set_add_dims(context, isl_dim_set, n_div);
983 ls = isl_aff_get_domain_local_space(aff);
984 bset = isl_basic_set_from_local_space(ls);
985 bset = isl_basic_set_lift(bset);
986 bset = isl_basic_set_flatten(bset);
987 context = isl_set_intersect(context,
988 isl_set_from_basic_set(bset));
989 }
990
991 hull = isl_set_affine_hull(context);
992 return isl_aff_substitute_equalities_lifted(aff, hull);
993 error:
994 isl_aff_free(aff);
995 isl_set_free(context);
996 return NULL;
997 }
998
999 /* Return a basic set containing those elements in the space
1000 * of aff where it is non-negative.
1001 */
1002 __isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff)
1003 {
1004 isl_constraint *ineq;
1005
1006 ineq = isl_inequality_from_aff(aff);
1007
1008 return isl_basic_set_from_constraint(ineq);
1009 }
1010
1011 /* Return a basic set containing those elements in the space
1012 * of aff where it is zero.
1013 */
1014 __isl_give isl_basic_set *isl_aff_zero_basic_set(__isl_take isl_aff *aff)
1015 {
1016 isl_constraint *ineq;
1017
1018 ineq = isl_equality_from_aff(aff);
1019
1020 return isl_basic_set_from_constraint(ineq);
1021 }
1022
1023 /* Return a basic set containing those elements in the shared space
1024 * of aff1 and aff2 where aff1 is greater than or equal to aff2.
1025 */
1026 __isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1,
1027 __isl_take isl_aff *aff2)
1028 {
1029 aff1 = isl_aff_sub(aff1, aff2);
1030
1031 return isl_aff_nonneg_basic_set(aff1);
1032 }
1033
1034 /* Return a basic set containing those elements in the shared space
1035 * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
1036 */
1037 __isl_give isl_basic_set *isl_aff_le_basic_set(__isl_take isl_aff *aff1,
1038 __isl_take isl_aff *aff2)
1039 {
1040 return isl_aff_ge_basic_set(aff2, aff1);
1041 }
1042
1043 __isl_give isl_aff *isl_aff_add_on_domain(__isl_keep isl_set *dom,
1044 __isl_take isl_aff *aff1, __isl_take isl_aff *aff2)
1045 {
1046 aff1 = isl_aff_add(aff1, aff2);
1047 aff1 = isl_aff_gist(aff1, isl_set_copy(dom));
1048 return aff1;
1049 }
1050
1051 int isl_aff_is_empty(__isl_keep isl_aff *aff)
1052 {
1053 if (!aff)
1054 return -1;
1055
1056 return 0;
1057 }
1058
1059 /* Check whether the given affine expression has non-zero coefficient
1060 * for any dimension in the given range or if any of these dimensions
1061 * appear with non-zero coefficients in any of the integer divisions
1062 * involved in the affine expression.
1063 */
1064 int isl_aff_involves_dims(__isl_keep isl_aff *aff,
1065 enum isl_dim_type type, unsigned first, unsigned n)
1066 {
1067 int i;
1068 isl_ctx *ctx;
1069 int *active = NULL;
1070 int involves = 0;
1071
1072 if (!aff)
1073 return -1;
1074 if (n == 0)
1075 return 0;
1076
1077 ctx = isl_aff_get_ctx(aff);
1078 if (first + n > isl_aff_dim(aff, type))
1079 isl_die(ctx, isl_error_invalid,
1080 "range out of bounds", return -1);
1081
1082 active = isl_local_space_get_active(aff->ls, aff->v->el + 2);
1083 if (!active)
1084 goto error;
1085
1086 first += isl_local_space_offset(aff->ls, type) - 1;
1087 for (i = 0; i < n; ++i)
1088 if (active[first + i]) {
1089 involves = 1;
1090 break;
1091 }
1092
1093 free(active);
1094
1095 return involves;
1096 error:
1097 free(active);
1098 return -1;
1099 }
1100
1101 __isl_give isl_aff *isl_aff_drop_dims(__isl_take isl_aff *aff,
1102 enum isl_dim_type type, unsigned first, unsigned n)
1103 {
1104 isl_ctx *ctx;
1105
1106 if (!aff)
1107 return NULL;
1108 if (type == isl_dim_out)
1109 isl_die(aff->v->ctx, isl_error_invalid,
1110 "cannot drop output/set dimension",
1111 return isl_aff_free(aff));
1112 if (type == isl_dim_in)
1113 type = isl_dim_set;
1114 if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1115 return aff;
1116
1117 ctx = isl_aff_get_ctx(aff);
1118 if (first + n > isl_local_space_dim(aff->ls, type))
1119 isl_die(ctx, isl_error_invalid, "range out of bounds",
1120 return isl_aff_free(aff));
1121
1122 aff = isl_aff_cow(aff);
1123 if (!aff)
1124 return NULL;
1125
1126 aff->ls = isl_local_space_drop_dims(aff->ls, type, first, n);
1127 if (!aff->ls)
1128 return isl_aff_free(aff);
1129
1130 first += 1 + isl_local_space_offset(aff->ls, type);
1131 aff->v = isl_vec_drop_els(aff->v, first, n);
1132 if (!aff->v)
1133 return isl_aff_free(aff);
1134
1135 return aff;
1136 }
1137
1138 __isl_give isl_aff *isl_aff_insert_dims(__isl_take isl_aff *aff,
1139 enum isl_dim_type type, unsigned first, unsigned n)
1140 {
1141 isl_ctx *ctx;
1142
1143 if (!aff)
1144 return NULL;
1145 if (type == isl_dim_out)
1146 isl_die(aff->v->ctx, isl_error_invalid,
1147 "cannot insert output/set dimensions",
1148 return isl_aff_free(aff));
1149 if (type == isl_dim_in)
1150 type = isl_dim_set;
1151 if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1152 return aff;
1153
1154 ctx = isl_aff_get_ctx(aff);
1155 if (first > isl_local_space_dim(aff->ls, type))
1156 isl_die(ctx, isl_error_invalid, "position out of bounds",
1157 return isl_aff_free(aff));
1158
1159 aff = isl_aff_cow(aff);
1160 if (!aff)
1161 return NULL;
1162
1163 aff->ls = isl_local_space_insert_dims(aff->ls, type, first, n);
1164 if (!aff->ls)
1165 return isl_aff_free(aff);
1166
1167 first += 1 + isl_local_space_offset(aff->ls, type);
1168 aff->v = isl_vec_insert_zero_els(aff->v, first, n);
1169 if (!aff->v)
1170 return isl_aff_free(aff);
1171
1172 return aff;
1173 }
1174
1175 __isl_give isl_aff *isl_aff_add_dims(__isl_take isl_aff *aff,
1176 enum isl_dim_type type, unsigned n)
1177 {
1178 unsigned pos;
1179
1180 pos = isl_aff_dim(aff, type);
1181
1182 return isl_aff_insert_dims(aff, type, pos, n);
1183 }
1184
1185 __isl_give isl_pw_aff *isl_pw_aff_add_dims(__isl_take isl_pw_aff *pwaff,
1186 enum isl_dim_type type, unsigned n)
1187 {
1188 unsigned pos;
1189
1190 pos = isl_pw_aff_dim(pwaff, type);
1191
1192 return isl_pw_aff_insert_dims(pwaff, type, pos, n);
1193 }
1194
1195 __isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff)
1196 {
1197 isl_set *dom = isl_set_universe(isl_aff_get_domain_space(aff));
1198 return isl_pw_aff_alloc(dom, aff);
1199 }
1200
1201 #undef PW
1202 #define PW isl_pw_aff
1203 #undef EL
1204 #define EL isl_aff
1205 #undef EL_IS_ZERO
1206 #define EL_IS_ZERO is_empty
1207 #undef ZERO
1208 #define ZERO empty
1209 #undef IS_ZERO
1210 #define IS_ZERO is_empty
1211 #undef FIELD
1212 #define FIELD aff
1213
1214 #define NO_EVAL
1215 #define NO_OPT
1216 #define NO_MOVE_DIMS
1217 #define NO_LIFT
1218 #define NO_MORPH
1219
1220 #include <isl_pw_templ.c>
1221
1222 static __isl_give isl_set *align_params_pw_pw_set_and(
1223 __isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2,
1224 __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1225 __isl_take isl_pw_aff *pwaff2))
1226 {
1227 if (!pwaff1 || !pwaff2)
1228 goto error;
1229 if (isl_space_match(pwaff1->dim, isl_dim_param,
1230 pwaff2->dim, isl_dim_param))
1231 return fn(pwaff1, pwaff2);
1232 if (!isl_space_has_named_params(pwaff1->dim) ||
1233 !isl_space_has_named_params(pwaff2->dim))
1234 isl_die(isl_pw_aff_get_ctx(pwaff1), isl_error_invalid,
1235 "unaligned unnamed parameters", goto error);
1236 pwaff1 = isl_pw_aff_align_params(pwaff1, isl_pw_aff_get_space(pwaff2));
1237 pwaff2 = isl_pw_aff_align_params(pwaff2, isl_pw_aff_get_space(pwaff1));
1238 return fn(pwaff1, pwaff2);
1239 error:
1240 isl_pw_aff_free(pwaff1);
1241 isl_pw_aff_free(pwaff2);
1242 return NULL;
1243 }
1244
1245 /* Compute a piecewise quasi-affine expression with a domain that
1246 * is the union of those of pwaff1 and pwaff2 and such that on each
1247 * cell, the quasi-affine expression is the better (according to cmp)
1248 * of those of pwaff1 and pwaff2. If only one of pwaff1 or pwaff2
1249 * is defined on a given cell, then the associated expression
1250 * is the defined one.
1251 */
1252 static __isl_give isl_pw_aff *pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1253 __isl_take isl_pw_aff *pwaff2,
1254 __isl_give isl_basic_set *(*cmp)(__isl_take isl_aff *aff1,
1255 __isl_take isl_aff *aff2))
1256 {
1257 int i, j, n;
1258 isl_pw_aff *res;
1259 isl_ctx *ctx;
1260 isl_set *set;
1261
1262 if (!pwaff1 || !pwaff2)
1263 goto error;
1264
1265 ctx = isl_space_get_ctx(pwaff1->dim);
1266 if (!isl_space_is_equal(pwaff1->dim, pwaff2->dim))
1267 isl_die(ctx, isl_error_invalid,
1268 "arguments should live in same space", goto error);
1269
1270 if (isl_pw_aff_is_empty(pwaff1)) {
1271 isl_pw_aff_free(pwaff1);
1272 return pwaff2;
1273 }
1274
1275 if (isl_pw_aff_is_empty(pwaff2)) {
1276 isl_pw_aff_free(pwaff2);
1277 return pwaff1;
1278 }
1279
1280 n = 2 * (pwaff1->n + 1) * (pwaff2->n + 1);
1281 res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1282
1283 for (i = 0; i < pwaff1->n; ++i) {
1284 set = isl_set_copy(pwaff1->p[i].set);
1285 for (j = 0; j < pwaff2->n; ++j) {
1286 struct isl_set *common;
1287 isl_set *better;
1288
1289 common = isl_set_intersect(
1290 isl_set_copy(pwaff1->p[i].set),
1291 isl_set_copy(pwaff2->p[j].set));
1292 better = isl_set_from_basic_set(cmp(
1293 isl_aff_copy(pwaff2->p[j].aff),
1294 isl_aff_copy(pwaff1->p[i].aff)));
1295 better = isl_set_intersect(common, better);
1296 if (isl_set_plain_is_empty(better)) {
1297 isl_set_free(better);
1298 continue;
1299 }
1300 set = isl_set_subtract(set, isl_set_copy(better));
1301
1302 res = isl_pw_aff_add_piece(res, better,
1303 isl_aff_copy(pwaff2->p[j].aff));
1304 }
1305 res = isl_pw_aff_add_piece(res, set,
1306 isl_aff_copy(pwaff1->p[i].aff));
1307 }
1308
1309 for (j = 0; j < pwaff2->n; ++j) {
1310 set = isl_set_copy(pwaff2->p[j].set);
1311 for (i = 0; i < pwaff1->n; ++i)
1312 set = isl_set_subtract(set,
1313 isl_set_copy(pwaff1->p[i].set));
1314 res = isl_pw_aff_add_piece(res, set,
1315 isl_aff_copy(pwaff2->p[j].aff));
1316 }
1317
1318 isl_pw_aff_free(pwaff1);
1319 isl_pw_aff_free(pwaff2);
1320
1321 return res;
1322 error:
1323 isl_pw_aff_free(pwaff1);
1324 isl_pw_aff_free(pwaff2);
1325 return NULL;
1326 }
1327
1328 /* Compute a piecewise quasi-affine expression with a domain that
1329 * is the union of those of pwaff1 and pwaff2 and such that on each
1330 * cell, the quasi-affine expression is the maximum of those of pwaff1
1331 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1332 * cell, then the associated expression is the defined one.
1333 */
1334 static __isl_give isl_pw_aff *pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1335 __isl_take isl_pw_aff *pwaff2)
1336 {
1337 return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_ge_basic_set);
1338 }
1339
1340 __isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1341 __isl_take isl_pw_aff *pwaff2)
1342 {
1343 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
1344 &pw_aff_union_max);
1345 }
1346
1347 /* Compute a piecewise quasi-affine expression with a domain that
1348 * is the union of those of pwaff1 and pwaff2 and such that on each
1349 * cell, the quasi-affine expression is the minimum of those of pwaff1
1350 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1351 * cell, then the associated expression is the defined one.
1352 */
1353 static __isl_give isl_pw_aff *pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1354 __isl_take isl_pw_aff *pwaff2)
1355 {
1356 return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_le_basic_set);
1357 }
1358
1359 __isl_give isl_pw_aff *isl_pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1360 __isl_take isl_pw_aff *pwaff2)
1361 {
1362 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
1363 &pw_aff_union_min);
1364 }
1365
1366 __isl_give isl_pw_aff *isl_pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1367 __isl_take isl_pw_aff *pwaff2, int max)
1368 {
1369 if (max)
1370 return isl_pw_aff_union_max(pwaff1, pwaff2);
1371 else
1372 return isl_pw_aff_union_min(pwaff1, pwaff2);
1373 }
1374
1375 /* Construct a map with as domain the domain of pwaff and
1376 * one-dimensional range corresponding to the affine expressions.
1377 */
1378 static __isl_give isl_map *map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1379 {
1380 int i;
1381 isl_space *dim;
1382 isl_map *map;
1383
1384 if (!pwaff)
1385 return NULL;
1386
1387 dim = isl_pw_aff_get_space(pwaff);
1388 map = isl_map_empty(dim);
1389
1390 for (i = 0; i < pwaff->n; ++i) {
1391 isl_basic_map *bmap;
1392 isl_map *map_i;
1393
1394 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
1395 map_i = isl_map_from_basic_map(bmap);
1396 map_i = isl_map_intersect_domain(map_i,
1397 isl_set_copy(pwaff->p[i].set));
1398 map = isl_map_union_disjoint(map, map_i);
1399 }
1400
1401 isl_pw_aff_free(pwaff);
1402
1403 return map;
1404 }
1405
1406 /* Construct a map with as domain the domain of pwaff and
1407 * one-dimensional range corresponding to the affine expressions.
1408 */
1409 __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1410 {
1411 if (isl_space_is_set(pwaff->dim))
1412 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1413 "space of input is not a map",
1414 return isl_pw_aff_free(pwaff));
1415 return map_from_pw_aff(pwaff);
1416 }
1417
1418 /* Construct a one-dimensional set with as parameter domain
1419 * the domain of pwaff and the single set dimension
1420 * corresponding to the affine expressions.
1421 */
1422 __isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1423 {
1424 if (!isl_space_is_set(pwaff->dim))
1425 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1426 "space of input is not a set",
1427 return isl_pw_aff_free(pwaff));
1428 return map_from_pw_aff(pwaff);
1429 }
1430
1431 /* Return a set containing those elements in the domain
1432 * of pwaff where it is non-negative.
1433 */
1434 __isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
1435 {
1436 int i;
1437 isl_set *set;
1438
1439 if (!pwaff)
1440 return NULL;
1441
1442 set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1443
1444 for (i = 0; i < pwaff->n; ++i) {
1445 isl_basic_set *bset;
1446 isl_set *set_i;
1447
1448 bset = isl_aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff));
1449 set_i = isl_set_from_basic_set(bset);
1450 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1451 set = isl_set_union_disjoint(set, set_i);
1452 }
1453
1454 isl_pw_aff_free(pwaff);
1455
1456 return set;
1457 }
1458
1459 /* Return a set containing those elements in the domain
1460 * of pwaff where it is zero.
1461 */
1462 __isl_give isl_set *isl_pw_aff_zero_set(__isl_take isl_pw_aff *pwaff)
1463 {
1464 int i;
1465 isl_set *set;
1466
1467 if (!pwaff)
1468 return NULL;
1469
1470 set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1471
1472 for (i = 0; i < pwaff->n; ++i) {
1473 isl_basic_set *bset;
1474 isl_set *set_i;
1475
1476 bset = isl_aff_zero_basic_set(isl_aff_copy(pwaff->p[i].aff));
1477 set_i = isl_set_from_basic_set(bset);
1478 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1479 set = isl_set_union_disjoint(set, set_i);
1480 }
1481
1482 isl_pw_aff_free(pwaff);
1483
1484 return set;
1485 }
1486
1487 /* Return a set containing those elements in the domain
1488 * of pwaff where it is not zero.
1489 */
1490 __isl_give isl_set *isl_pw_aff_non_zero_set(__isl_take isl_pw_aff *pwaff)
1491 {
1492 return isl_set_complement(isl_pw_aff_zero_set(pwaff));
1493 }
1494
1495 /* Return a set containing those elements in the shared domain
1496 * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
1497 *
1498 * We compute the difference on the shared domain and then construct
1499 * the set of values where this difference is non-negative.
1500 * If strict is set, we first subtract 1 from the difference.
1501 * If equal is set, we only return the elements where pwaff1 and pwaff2
1502 * are equal.
1503 */
1504 static __isl_give isl_set *pw_aff_gte_set(__isl_take isl_pw_aff *pwaff1,
1505 __isl_take isl_pw_aff *pwaff2, int strict, int equal)
1506 {
1507 isl_set *set1, *set2;
1508
1509 set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1));
1510 set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2));
1511 set1 = isl_set_intersect(set1, set2);
1512 pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1));
1513 pwaff2 = isl_pw_aff_intersect_domain(pwaff2, isl_set_copy(set1));
1514 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2));
1515
1516 if (strict) {
1517 isl_space *dim = isl_set_get_space(set1);
1518 isl_aff *aff;
1519 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
1520 aff = isl_aff_add_constant_si(aff, -1);
1521 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_alloc(set1, aff));
1522 } else
1523 isl_set_free(set1);
1524
1525 if (equal)
1526 return isl_pw_aff_zero_set(pwaff1);
1527 return isl_pw_aff_nonneg_set(pwaff1);
1528 }
1529
1530 /* Return a set containing those elements in the shared domain
1531 * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
1532 */
1533 static __isl_give isl_set *pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1534 __isl_take isl_pw_aff *pwaff2)
1535 {
1536 return pw_aff_gte_set(pwaff1, pwaff2, 0, 1);
1537 }
1538
1539 __isl_give isl_set *isl_pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1540 __isl_take isl_pw_aff *pwaff2)
1541 {
1542 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_eq_set);
1543 }
1544
1545 /* Return a set containing those elements in the shared domain
1546 * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
1547 */
1548 static __isl_give isl_set *pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1549 __isl_take isl_pw_aff *pwaff2)
1550 {
1551 return pw_aff_gte_set(pwaff1, pwaff2, 0, 0);
1552 }
1553
1554 __isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1555 __isl_take isl_pw_aff *pwaff2)
1556 {
1557 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ge_set);
1558 }
1559
1560 /* Return a set containing those elements in the shared domain
1561 * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
1562 */
1563 static __isl_give isl_set *pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1564 __isl_take isl_pw_aff *pwaff2)
1565 {
1566 return pw_aff_gte_set(pwaff1, pwaff2, 1, 0);
1567 }
1568
1569 __isl_give isl_set *isl_pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1570 __isl_take isl_pw_aff *pwaff2)
1571 {
1572 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_gt_set);
1573 }
1574
1575 __isl_give isl_set *isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1,
1576 __isl_take isl_pw_aff *pwaff2)
1577 {
1578 return isl_pw_aff_ge_set(pwaff2, pwaff1);
1579 }
1580
1581 __isl_give isl_set *isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1,
1582 __isl_take isl_pw_aff *pwaff2)
1583 {
1584 return isl_pw_aff_gt_set(pwaff2, pwaff1);
1585 }
1586
1587 /* Return a set containing those elements in the shared domain
1588 * of the elements of list1 and list2 where each element in list1
1589 * has the relation specified by "fn" with each element in list2.
1590 */
1591 static __isl_give isl_set *pw_aff_list_set(__isl_take isl_pw_aff_list *list1,
1592 __isl_take isl_pw_aff_list *list2,
1593 __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1594 __isl_take isl_pw_aff *pwaff2))
1595 {
1596 int i, j;
1597 isl_ctx *ctx;
1598 isl_set *set;
1599
1600 if (!list1 || !list2)
1601 goto error;
1602
1603 ctx = isl_pw_aff_list_get_ctx(list1);
1604 if (list1->n < 1 || list2->n < 1)
1605 isl_die(ctx, isl_error_invalid,
1606 "list should contain at least one element", goto error);
1607
1608 set = isl_set_universe(isl_pw_aff_get_domain_space(list1->p[0]));
1609 for (i = 0; i < list1->n; ++i)
1610 for (j = 0; j < list2->n; ++j) {
1611 isl_set *set_ij;
1612
1613 set_ij = fn(isl_pw_aff_copy(list1->p[i]),
1614 isl_pw_aff_copy(list2->p[j]));
1615 set = isl_set_intersect(set, set_ij);
1616 }
1617
1618 isl_pw_aff_list_free(list1);
1619 isl_pw_aff_list_free(list2);
1620 return set;
1621 error:
1622 isl_pw_aff_list_free(list1);
1623 isl_pw_aff_list_free(list2);
1624 return NULL;
1625 }
1626
1627 /* Return a set containing those elements in the shared domain
1628 * of the elements of list1 and list2 where each element in list1
1629 * is equal to each element in list2.
1630 */
1631 __isl_give isl_set *isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list *list1,
1632 __isl_take isl_pw_aff_list *list2)
1633 {
1634 return pw_aff_list_set(list1, list2, &isl_pw_aff_eq_set);
1635 }
1636
1637 __isl_give isl_set *isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list *list1,
1638 __isl_take isl_pw_aff_list *list2)
1639 {
1640 return pw_aff_list_set(list1, list2, &isl_pw_aff_ne_set);
1641 }
1642
1643 /* Return a set containing those elements in the shared domain
1644 * of the elements of list1 and list2 where each element in list1
1645 * is less than or equal to each element in list2.
1646 */
1647 __isl_give isl_set *isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list *list1,
1648 __isl_take isl_pw_aff_list *list2)
1649 {
1650 return pw_aff_list_set(list1, list2, &isl_pw_aff_le_set);
1651 }
1652
1653 __isl_give isl_set *isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list *list1,
1654 __isl_take isl_pw_aff_list *list2)
1655 {
1656 return pw_aff_list_set(list1, list2, &isl_pw_aff_lt_set);
1657 }
1658
1659 __isl_give isl_set *isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list *list1,
1660 __isl_take isl_pw_aff_list *list2)
1661 {
1662 return pw_aff_list_set(list1, list2, &isl_pw_aff_ge_set);
1663 }
1664
1665 __isl_give isl_set *isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list *list1,
1666 __isl_take isl_pw_aff_list *list2)
1667 {
1668 return pw_aff_list_set(list1, list2, &isl_pw_aff_gt_set);
1669 }
1670
1671
1672 /* Return a set containing those elements in the shared domain
1673 * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
1674 */
1675 static __isl_give isl_set *pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1676 __isl_take isl_pw_aff *pwaff2)
1677 {
1678 isl_set *set_lt, *set_gt;
1679
1680 set_lt = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1),
1681 isl_pw_aff_copy(pwaff2));
1682 set_gt = isl_pw_aff_gt_set(pwaff1, pwaff2);
1683 return isl_set_union_disjoint(set_lt, set_gt);
1684 }
1685
1686 __isl_give isl_set *isl_pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1687 __isl_take isl_pw_aff *pwaff2)
1688 {
1689 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ne_set);
1690 }
1691
1692 __isl_give isl_pw_aff *isl_pw_aff_scale_down(__isl_take isl_pw_aff *pwaff,
1693 isl_int v)
1694 {
1695 int i;
1696
1697 if (isl_int_is_one(v))
1698 return pwaff;
1699 if (!isl_int_is_pos(v))
1700 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1701 "factor needs to be positive",
1702 return isl_pw_aff_free(pwaff));
1703 pwaff = isl_pw_aff_cow(pwaff);
1704 if (!pwaff)
1705 return NULL;
1706 if (pwaff->n == 0)
1707 return pwaff;
1708
1709 for (i = 0; i < pwaff->n; ++i) {
1710 pwaff->p[i].aff = isl_aff_scale_down(pwaff->p[i].aff, v);
1711 if (!pwaff->p[i].aff)
1712 return isl_pw_aff_free(pwaff);
1713 }
1714
1715 return pwaff;
1716 }
1717
1718 __isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff)
1719 {
1720 int i;
1721
1722 pwaff = isl_pw_aff_cow(pwaff);
1723 if (!pwaff)
1724 return NULL;
1725 if (pwaff->n == 0)
1726 return pwaff;
1727
1728 for (i = 0; i < pwaff->n; ++i) {
1729 pwaff->p[i].aff = isl_aff_floor(pwaff->p[i].aff);
1730 if (!pwaff->p[i].aff)
1731 return isl_pw_aff_free(pwaff);
1732 }
1733
1734 return pwaff;
1735 }
1736
1737 __isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff)
1738 {
1739 int i;
1740
1741 pwaff = isl_pw_aff_cow(pwaff);
1742 if (!pwaff)
1743 return NULL;
1744 if (pwaff->n == 0)
1745 return pwaff;
1746
1747 for (i = 0; i < pwaff->n; ++i) {
1748 pwaff->p[i].aff = isl_aff_ceil(pwaff->p[i].aff);
1749 if (!pwaff->p[i].aff)
1750 return isl_pw_aff_free(pwaff);
1751 }
1752
1753 return pwaff;
1754 }
1755
1756 /* Return an affine expression that is equal to pwaff_true for elements
1757 * in "cond" and to pwaff_false for elements not in "cond".
1758 * That is, return cond ? pwaff_true : pwaff_false;
1759 */
1760 __isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_set *cond,
1761 __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false)
1762 {
1763 isl_set *comp;
1764
1765 comp = isl_set_complement(isl_set_copy(cond));
1766 pwaff_true = isl_pw_aff_intersect_domain(pwaff_true, cond);
1767 pwaff_false = isl_pw_aff_intersect_domain(pwaff_false, comp);
1768
1769 return isl_pw_aff_add_disjoint(pwaff_true, pwaff_false);
1770 }
1771
1772 int isl_aff_is_cst(__isl_keep isl_aff *aff)
1773 {
1774 if (!aff)
1775 return -1;
1776
1777 return isl_seq_first_non_zero(aff->v->el + 2, aff->v->size - 2) == -1;
1778 }
1779
1780 /* Check whether pwaff is a piecewise constant.
1781 */
1782 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff)
1783 {
1784 int i;
1785
1786 if (!pwaff)
1787 return -1;
1788
1789 for (i = 0; i < pwaff->n; ++i) {
1790 int is_cst = isl_aff_is_cst(pwaff->p[i].aff);
1791 if (is_cst < 0 || !is_cst)
1792 return is_cst;
1793 }
1794
1795 return 1;
1796 }
1797
1798 __isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
1799 __isl_take isl_aff *aff2)
1800 {
1801 if (!isl_aff_is_cst(aff2) && isl_aff_is_cst(aff1))
1802 return isl_aff_mul(aff2, aff1);
1803
1804 if (!isl_aff_is_cst(aff2))
1805 isl_die(isl_aff_get_ctx(aff1), isl_error_invalid,
1806 "at least one affine expression should be constant",
1807 goto error);
1808
1809 aff1 = isl_aff_cow(aff1);
1810 if (!aff1 || !aff2)
1811 goto error;
1812
1813 aff1 = isl_aff_scale(aff1, aff2->v->el[1]);
1814 aff1 = isl_aff_scale_down(aff1, aff2->v->el[0]);
1815
1816 isl_aff_free(aff2);
1817 return aff1;
1818 error:
1819 isl_aff_free(aff1);
1820 isl_aff_free(aff2);
1821 return NULL;
1822 }
1823
1824 static __isl_give isl_pw_aff *pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1825 __isl_take isl_pw_aff *pwaff2)
1826 {
1827 int i, j, n;
1828 isl_pw_aff *res;
1829
1830 if (!pwaff1 || !pwaff2)
1831 goto error;
1832
1833 n = pwaff1->n * pwaff2->n;
1834 res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1835
1836 for (i = 0; i < pwaff1->n; ++i) {
1837 for (j = 0; j < pwaff2->n; ++j) {
1838 isl_set *common;
1839 isl_aff *prod;
1840 common = isl_set_intersect(
1841 isl_set_copy(pwaff1->p[i].set),
1842 isl_set_copy(pwaff2->p[j].set));
1843 if (isl_set_plain_is_empty(common)) {
1844 isl_set_free(common);
1845 continue;
1846 }
1847
1848 prod = isl_aff_mul(isl_aff_copy(pwaff1->p[i].aff),
1849 isl_aff_copy(pwaff2->p[j].aff));
1850
1851 res = isl_pw_aff_add_piece(res, common, prod);
1852 }
1853 }
1854
1855 isl_pw_aff_free(pwaff1);
1856 isl_pw_aff_free(pwaff2);
1857 return res;
1858 error:
1859 isl_pw_aff_free(pwaff1);
1860 isl_pw_aff_free(pwaff2);
1861 return NULL;
1862 }
1863
1864 __isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1865 __isl_take isl_pw_aff *pwaff2)
1866 {
1867 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul);
1868 }
1869
1870 static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1871 __isl_take isl_pw_aff *pwaff2)
1872 {
1873 isl_set *le;
1874
1875 le = isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1),
1876 isl_pw_aff_copy(pwaff2));
1877 return isl_pw_aff_cond(le, pwaff1, pwaff2);
1878 }
1879
1880 __isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1881 __isl_take isl_pw_aff *pwaff2)
1882 {
1883 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_min);
1884 }
1885
1886 static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1887 __isl_take isl_pw_aff *pwaff2)
1888 {
1889 isl_set *le;
1890
1891 le = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1),
1892 isl_pw_aff_copy(pwaff2));
1893 return isl_pw_aff_cond(le, pwaff1, pwaff2);
1894 }
1895
1896 __isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1897 __isl_take isl_pw_aff *pwaff2)
1898 {
1899 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_max);
1900 }
1901
1902 static __isl_give isl_pw_aff *pw_aff_list_reduce(
1903 __isl_take isl_pw_aff_list *list,
1904 __isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pwaff1,
1905 __isl_take isl_pw_aff *pwaff2))
1906 {
1907 int i;
1908 isl_ctx *ctx;
1909 isl_pw_aff *res;
1910
1911 if (!list)
1912 return NULL;
1913
1914 ctx = isl_pw_aff_list_get_ctx(list);
1915 if (list->n < 1)
1916 isl_die(ctx, isl_error_invalid,
1917 "list should contain at least one element",
1918 return isl_pw_aff_list_free(list));
1919
1920 res = isl_pw_aff_copy(list->p[0]);
1921 for (i = 1; i < list->n; ++i)
1922 res = fn(res, isl_pw_aff_copy(list->p[i]));
1923
1924 isl_pw_aff_list_free(list);
1925 return res;
1926 }
1927
1928 /* Return an isl_pw_aff that maps each element in the intersection of the
1929 * domains of the elements of list to the minimal corresponding affine
1930 * expression.
1931 */
1932 __isl_give isl_pw_aff *isl_pw_aff_list_min(__isl_take isl_pw_aff_list *list)
1933 {
1934 return pw_aff_list_reduce(list, &isl_pw_aff_min);
1935 }
1936
1937 /* Return an isl_pw_aff that maps each element in the intersection of the
1938 * domains of the elements of list to the maximal corresponding affine
1939 * expression.
1940 */
1941 __isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list)
1942 {
1943 return pw_aff_list_reduce(list, &isl_pw_aff_max);
1944 }
1945
1946 #undef BASE
1947 #define BASE aff
1948
1949 #include <isl_multi_templ.c>
1950
1951 __isl_give isl_multi_aff *isl_multi_aff_add(__isl_take isl_multi_aff *maff1,
1952 __isl_take isl_multi_aff *maff2)
1953 {
1954 int i;
1955 isl_ctx *ctx;
1956
1957 maff1 = isl_multi_aff_cow(maff1);
1958 if (!maff1 || !maff2)
1959 goto error;
1960
1961 ctx = isl_multi_aff_get_ctx(maff1);
1962 if (!isl_space_is_equal(maff1->space, maff2->space))
1963 isl_die(ctx, isl_error_invalid,
1964 "spaces don't match", goto error);
1965
1966 for (i = 0; i < maff1->n; ++i) {
1967 maff1->p[i] = isl_aff_add(maff1->p[i],
1968 isl_aff_copy(maff2->p[i]));
1969 if (!maff1->p[i])
1970 goto error;
1971 }
1972
1973 isl_multi_aff_free(maff2);
1974 return maff1;
1975 error:
1976 isl_multi_aff_free(maff1);
1977 isl_multi_aff_free(maff2);
1978 return NULL;
1979 }
1980
1981 /* Exploit the equalities in "eq" to simplify the affine expressions.
1982 */
1983 static __isl_give isl_multi_aff *isl_multi_aff_substitute_equalities(
1984 __isl_take isl_multi_aff *maff, __isl_take isl_basic_set *eq)
1985 {
1986 int i;
1987
1988 maff = isl_multi_aff_cow(maff);
1989 if (!maff || !eq)
1990 goto error;
1991
1992 for (i = 0; i < maff->n; ++i) {
1993 maff->p[i] = isl_aff_substitute_equalities(maff->p[i],
1994 isl_basic_set_copy(eq));
1995 if (!maff->p[i])
1996 goto error;
1997 }
1998
1999 isl_basic_set_free(eq);
2000 return maff;
2001 error:
2002 isl_basic_set_free(eq);
2003 isl_multi_aff_free(maff);
2004 return NULL;
2005 }
2006
2007 __isl_give isl_multi_aff *isl_multi_aff_scale(__isl_take isl_multi_aff *maff,
2008 isl_int f)
2009 {
2010 int i;
2011
2012 maff = isl_multi_aff_cow(maff);
2013 if (!maff)
2014 return NULL;
2015
2016 for (i = 0; i < maff->n; ++i) {
2017 maff->p[i] = isl_aff_scale(maff->p[i], f);
2018 if (!maff->p[i])
2019 return isl_multi_aff_free(maff);
2020 }
2021
2022 return maff;
2023 }
2024
2025 __isl_give isl_multi_aff *isl_multi_aff_add_on_domain(__isl_keep isl_set *dom,
2026 __isl_take isl_multi_aff *maff1, __isl_take isl_multi_aff *maff2)
2027 {
2028 maff1 = isl_multi_aff_add(maff1, maff2);
2029 maff1 = isl_multi_aff_gist(maff1, isl_set_copy(dom));
2030 return maff1;
2031 }
2032
2033 int isl_multi_aff_is_empty(__isl_keep isl_multi_aff *maff)
2034 {
2035 if (!maff)
2036 return -1;
2037
2038 return 0;
2039 }
2040
2041 int isl_multi_aff_plain_is_equal(__isl_keep isl_multi_aff *maff1,
2042 __isl_keep isl_multi_aff *maff2)
2043 {
2044 int i;
2045 int equal;
2046
2047 if (!maff1 || !maff2)
2048 return -1;
2049 if (maff1->n != maff2->n)
2050 return 0;
2051 equal = isl_space_is_equal(maff1->space, maff2->space);
2052 if (equal < 0 || !equal)
2053 return equal;
2054
2055 for (i = 0; i < maff1->n; ++i) {
2056 equal = isl_aff_plain_is_equal(maff1->p[i], maff2->p[i]);
2057 if (equal < 0 || !equal)
2058 return equal;
2059 }
2060
2061 return 1;
2062 }
2063
2064 __isl_give isl_multi_aff *isl_multi_aff_set_dim_name(
2065 __isl_take isl_multi_aff *maff,
2066 enum isl_dim_type type, unsigned pos, const char *s)
2067 {
2068 int i;
2069
2070 maff = isl_multi_aff_cow(maff);
2071 if (!maff)
2072 return NULL;
2073
2074 maff->space = isl_space_set_dim_name(maff->space, type, pos, s);
2075 if (!maff->space)
2076 return isl_multi_aff_free(maff);
2077 for (i = 0; i < maff->n; ++i) {
2078 maff->p[i] = isl_aff_set_dim_name(maff->p[i], type, pos, s);
2079 if (!maff->p[i])
2080 return isl_multi_aff_free(maff);
2081 }
2082
2083 return maff;
2084 }
2085
2086 __isl_give isl_multi_aff *isl_multi_aff_drop_dims(__isl_take isl_multi_aff *maff,
2087 enum isl_dim_type type, unsigned first, unsigned n)
2088 {
2089 int i;
2090
2091 maff = isl_multi_aff_cow(maff);
2092 if (!maff)
2093 return NULL;
2094
2095 maff->space = isl_space_drop_dims(maff->space, type, first, n);
2096 if (!maff->space)
2097 return isl_multi_aff_free(maff);
2098 for (i = 0; i < maff->n; ++i) {
2099 maff->p[i] = isl_aff_drop_dims(maff->p[i], type, first, n);
2100 if (!maff->p[i])
2101 return isl_multi_aff_free(maff);
2102 }
2103
2104 return maff;
2105 }
2106
2107 #undef PW
2108 #define PW isl_pw_multi_aff
2109 #undef EL
2110 #define EL isl_multi_aff
2111 #undef EL_IS_ZERO
2112 #define EL_IS_ZERO is_empty
2113 #undef ZERO
2114 #define ZERO empty
2115 #undef IS_ZERO
2116 #define IS_ZERO is_empty
2117 #undef FIELD
2118 #define FIELD maff
2119
2120 #define NO_NEG
2121 #define NO_EVAL
2122 #define NO_OPT
2123 #define NO_INVOLVES_DIMS
2124 #define NO_MOVE_DIMS
2125 #define NO_INSERT_DIMS
2126 #define NO_LIFT
2127 #define NO_MORPH
2128
2129 #include <isl_pw_templ.c>
2130
2131 /* Construct a map mapping the domain the piecewise multi-affine expression
2132 * to its range, with each dimension in the range equated to the
2133 * corresponding affine expression on its cell.
2134 */
2135 __isl_give isl_map *isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
2136 {
2137 int i;
2138 isl_map *map;
2139
2140 if (!pma)
2141 return NULL;
2142
2143 map = isl_map_empty(isl_pw_multi_aff_get_space(pma));
2144
2145 for (i = 0; i < pma->n; ++i) {
2146 isl_multi_aff *maff;
2147 isl_basic_map *bmap;
2148 isl_map *map_i;
2149
2150 maff = isl_multi_aff_copy(pma->p[i].maff);
2151 bmap = isl_basic_map_from_multi_aff(maff);
2152 map_i = isl_map_from_basic_map(bmap);
2153 map_i = isl_map_intersect_domain(map_i,
2154 isl_set_copy(pma->p[i].set));
2155 map = isl_map_union_disjoint(map, map_i);
2156 }
2157
2158 isl_pw_multi_aff_free(pma);
2159 return map;
2160 }
2161
2162 __isl_give isl_set *isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
2163 {
2164 if (!isl_space_is_set(pma->dim))
2165 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
2166 "isl_pw_multi_aff cannot be converted into an isl_set",
2167 return isl_pw_multi_aff_free(pma));
2168
2169 return isl_map_from_pw_multi_aff(pma);
2170 }
2171
2172 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
2173 * This obivously only works if the input "map" is single-valued.
2174 * If so, we compute the lexicographic minimum of the image in the form
2175 * of an isl_pw_multi_aff. Since the image is unique, it is equal
2176 * to its lexicographic minimum.
2177 * If the input is not single-valued, we produce an error.
2178 */
2179 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_map(__isl_take isl_map *map)
2180 {
2181 int i;
2182 int sv;
2183 isl_pw_multi_aff *pma;
2184
2185 if (!map)
2186 return NULL;
2187
2188 sv = isl_map_is_single_valued(map);
2189 if (sv < 0)
2190 goto error;
2191 if (!sv)
2192 isl_die(isl_map_get_ctx(map), isl_error_invalid,
2193 "map is not single-valued", goto error);
2194 map = isl_map_make_disjoint(map);
2195 if (!map)
2196 return NULL;
2197
2198 pma = isl_pw_multi_aff_empty(isl_map_get_space(map));
2199
2200 for (i = 0; i < map->n; ++i) {
2201 isl_pw_multi_aff *pma_i;
2202 isl_basic_map *bmap;
2203 bmap = isl_basic_map_copy(map->p[i]);
2204 pma_i = isl_basic_map_lexmin_pw_multi_aff(bmap);
2205 pma = isl_pw_multi_aff_add_disjoint(pma, pma_i);
2206 }
2207
2208 isl_map_free(map);
2209 return pma;
2210 error:
2211 isl_map_free(map);
2212 return NULL;
2213 }
2214
2215 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_set(__isl_take isl_set *set)
2216 {
2217 return isl_pw_multi_aff_from_map(set);
2218 }
2219
2220 /* Plug in "subs" for dimension "type", "pos" of "aff".
2221 *
2222 * Let i be the dimension to replace and let "subs" be of the form
2223 *
2224 * f/d
2225 *
2226 * and "aff" of the form
2227 *
2228 * (a i + g)/m
2229 *
2230 * The result is
2231 *
2232 * floor((a f + d g')/(m d))
2233 *
2234 * where g' is the result of plugging in "subs" in each of the integer
2235 * divisions in g.
2236 */
2237 __isl_give isl_aff *isl_aff_substitute(__isl_take isl_aff *aff,
2238 enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
2239 {
2240 isl_ctx *ctx;
2241 isl_int v;
2242
2243 aff = isl_aff_cow(aff);
2244 if (!aff || !subs)
2245 return isl_aff_free(aff);
2246
2247 ctx = isl_aff_get_ctx(aff);
2248 if (!isl_space_is_equal(aff->ls->dim, subs->ls->dim))
2249 isl_die(ctx, isl_error_invalid,
2250 "spaces don't match", return isl_aff_free(aff));
2251 if (isl_local_space_dim(subs->ls, isl_dim_div) != 0)
2252 isl_die(ctx, isl_error_unsupported,
2253 "cannot handle divs yet", return isl_aff_free(aff));
2254
2255 aff->ls = isl_local_space_substitute(aff->ls, type, pos, subs);
2256 if (!aff->ls)
2257 return isl_aff_free(aff);
2258
2259 aff->v = isl_vec_cow(aff->v);
2260 if (!aff->v)
2261 return isl_aff_free(aff);
2262
2263 pos += isl_local_space_offset(aff->ls, type);
2264
2265 isl_int_init(v);
2266 isl_int_set(v, aff->v->el[1 + pos]);
2267 isl_int_set_si(aff->v->el[1 + pos], 0);
2268 isl_seq_combine(aff->v->el + 1, subs->v->el[0], aff->v->el + 1,
2269 v, subs->v->el + 1, subs->v->size - 1);
2270 isl_int_mul(aff->v->el[0], aff->v->el[0], subs->v->el[0]);
2271 isl_int_clear(v);
2272
2273 return aff;
2274 }
2275
2276 /* Plug in "subs" for dimension "type", "pos" in each of the affine
2277 * expressions in "maff".
2278 */
2279 __isl_give isl_multi_aff *isl_multi_aff_substitute(
2280 __isl_take isl_multi_aff *maff, enum isl_dim_type type, unsigned pos,
2281 __isl_keep isl_aff *subs)
2282 {
2283 int i;
2284
2285 maff = isl_multi_aff_cow(maff);
2286 if (!maff || !subs)
2287 return isl_multi_aff_free(maff);
2288
2289 if (type == isl_dim_in)
2290 type = isl_dim_set;
2291
2292 for (i = 0; i < maff->n; ++i) {
2293 maff->p[i] = isl_aff_substitute(maff->p[i], type, pos, subs);
2294 if (!maff->p[i])
2295 return isl_multi_aff_free(maff);
2296 }
2297
2298 return maff;
2299 }
2300
2301 /* Plug in "subs" for dimension "type", "pos" of "pma".
2302 *
2303 * pma is of the form
2304 *
2305 * A_i(v) -> M_i(v)
2306 *
2307 * while subs is of the form
2308 *
2309 * v' = B_j(v) -> S_j
2310 *
2311 * Each pair i,j such that C_ij = A_i \cap B_i is non-empty
2312 * has a contribution in the result, in particular
2313 *
2314 * C_ij(S_j) -> M_i(S_j)
2315 *
2316 * Note that plugging in S_j in C_ij may also result in an empty set
2317 * and this contribution should simply be discarded.
2318 */
2319 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_substitute(
2320 __isl_take isl_pw_multi_aff *pma, enum isl_dim_type type, unsigned pos,
2321 __isl_keep isl_pw_aff *subs)
2322 {
2323 int i, j, n;
2324 isl_pw_multi_aff *res;
2325
2326 if (!pma || !subs)
2327 return isl_pw_multi_aff_free(pma);
2328
2329 n = pma->n * subs->n;
2330 res = isl_pw_multi_aff_alloc_size(isl_space_copy(pma->dim), n);
2331
2332 for (i = 0; i < pma->n; ++i) {
2333 for (j = 0; j < subs->n; ++j) {
2334 isl_set *common;
2335 isl_multi_aff *res_ij;
2336 common = isl_set_intersect(
2337 isl_set_copy(pma->p[i].set),
2338 isl_set_copy(subs->p[j].set));
2339 common = isl_set_substitute(common,
2340 type, pos, subs->p[j].aff);
2341 if (isl_set_plain_is_empty(common)) {
2342 isl_set_free(common);
2343 continue;
2344 }
2345
2346 res_ij = isl_multi_aff_substitute(
2347 isl_multi_aff_copy(pma->p[i].maff),
2348 type, pos, subs->p[j].aff);
2349
2350 res = isl_pw_multi_aff_add_piece(res, common, res_ij);
2351 }
2352 }
2353
2354 isl_pw_multi_aff_free(pma);
2355 return res;
2356 }
2357
2358 /* Extend the local space of "dst" to include the divs
2359 * in the local space of "src".
2360 */
2361 __isl_give isl_aff *isl_aff_align_divs(__isl_take isl_aff *dst,
2362 __isl_keep isl_aff *src)
2363 {
2364 isl_ctx *ctx;
2365 int *exp1 = NULL;
2366 int *exp2 = NULL;
2367 isl_mat *div;
2368
2369 if (!src || !dst)
2370 return isl_aff_free(dst);
2371
2372 ctx = isl_aff_get_ctx(src);
2373 if (!isl_space_is_equal(src->ls->dim, dst->ls->dim))
2374 isl_die(ctx, isl_error_invalid,
2375 "spaces don't match", goto error);
2376
2377 if (src->ls->div->n_row == 0)
2378 return dst;
2379
2380 exp1 = isl_alloc_array(ctx, int, src->ls->div->n_row);
2381 exp2 = isl_alloc_array(ctx, int, dst->ls->div->n_row);
2382 if (!exp1 || !exp2)
2383 goto error;
2384
2385 div = isl_merge_divs(src->ls->div, dst->ls->div, exp1, exp2);
2386 dst = isl_aff_expand_divs(dst, div, exp2);
2387 free(exp1);
2388 free(exp2);
2389
2390 return dst;
2391 error:
2392 free(exp1);
2393 free(exp2);
2394 return isl_aff_free(dst);
2395 }
2396
2397 /* Adjust the local spaces of the affine expressions in "maff"
2398 * such that they all have the save divs.
2399 */
2400 __isl_give isl_multi_aff *isl_multi_aff_align_divs(
2401 __isl_take isl_multi_aff *maff)
2402 {
2403 int i;
2404
2405 if (!maff)
2406 return NULL;
2407 if (maff->n == 0)
2408 return maff;
2409 maff = isl_multi_aff_cow(maff);
2410 if (!maff)
2411 return NULL;
2412
2413 for (i = 1; i < maff->n; ++i)
2414 maff->p[0] = isl_aff_align_divs(maff->p[0], maff->p[i]);
2415 for (i = 1; i < maff->n; ++i) {
2416 maff->p[i] = isl_aff_align_divs(maff->p[i], maff->p[0]);
2417 if (!maff->p[i])
2418 return isl_multi_aff_free(maff);
2419 }
2420
2421 return maff;
2422 }
2423
2424 __isl_give isl_aff *isl_aff_lift(__isl_take isl_aff *aff)
2425 {
2426 aff = isl_aff_cow(aff);
2427 if (!aff)
2428 return NULL;
2429
2430 aff->ls = isl_local_space_lift(aff->ls);
2431 if (!aff->ls)
2432 return isl_aff_free(aff);
2433
2434 return aff;
2435 }
2436
2437 /* Lift "maff" to a space with extra dimensions such that the result
2438 * has no more existentially quantified variables.
2439 * If "ls" is not NULL, then *ls is assigned the local space that lies
2440 * at the basis of the lifting applied to "maff".
2441 */
2442 __isl_give isl_multi_aff *isl_multi_aff_lift(__isl_take isl_multi_aff *maff,
2443 __isl_give isl_local_space **ls)
2444 {
2445 int i;
2446 isl_space *space;
2447 unsigned n_div;
2448
2449 if (ls)
2450 *ls = NULL;
2451
2452 if (!maff)
2453 return NULL;
2454
2455 if (maff->n == 0) {
2456 if (ls) {
2457 isl_space *space = isl_multi_aff_get_domain_space(maff);
2458 *ls = isl_local_space_from_space(space);
2459 if (!*ls)
2460 return isl_multi_aff_free(maff);
2461 }
2462 return maff;
2463 }
2464
2465 maff = isl_multi_aff_cow(maff);
2466 maff = isl_multi_aff_align_divs(maff);
2467 if (!maff)
2468 return NULL;
2469
2470 n_div = isl_aff_dim(maff->p[0], isl_dim_div);
2471 space = isl_multi_aff_get_space(maff);
2472 space = isl_space_lift(isl_space_domain(space), n_div);
2473 space = isl_space_extend_domain_with_range(space,
2474 isl_multi_aff_get_space(maff));
2475 if (!space)
2476 return isl_multi_aff_free(maff);
2477 isl_space_free(maff->space);
2478 maff->space = space;
2479
2480 if (ls) {
2481 *ls = isl_aff_get_domain_local_space(maff->p[0]);
2482 if (!*ls)
2483 return isl_multi_aff_free(maff);
2484 }
2485
2486 for (i = 0; i < maff->n; ++i) {
2487 maff->p[i] = isl_aff_lift(maff->p[i]);
2488 if (!maff->p[i])
2489 goto error;
2490 }
2491
2492 return maff;
2493 error:
2494 if (ls)
2495 isl_local_space_free(*ls);
2496 return isl_multi_aff_free(maff);
2497 }
Integer set library