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