?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
add isl_basic_map_has_dim_id
[isl.git] / isl_aff.c
blobc18493d732c6ed22604d6dcc796b12a1da181963
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 /* Given f, return floor(f).
547 * If f is an integer expression, then just return f.
548 * Otherwise, if f = g/m, write g = q m + r,
549 * create a new div d = [r/m] and return the expression q + d.
550 * The coefficients in r are taken to lie between -m/2 and m/2.
551 */
552 __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
553 {
554 int i;
555 int size;
556 isl_ctx *ctx;
557 isl_vec *div;
558
559 if (!aff)
560 return NULL;
561
562 if (isl_int_is_one(aff->v->el[0]))
563 return aff;
564
565 aff = isl_aff_cow(aff);
566 if (!aff)
567 return NULL;
568
569 aff->v = isl_vec_cow(aff->v);
570 div = isl_vec_copy(aff->v);
571 div = isl_vec_cow(div);
572 if (!div)
573 return isl_aff_free(aff);
574
575 ctx = isl_aff_get_ctx(aff);
576 isl_int_fdiv_q(aff->v->el[0], aff->v->el[0], ctx->two);
577 for (i = 1; i < aff->v->size; ++i) {
578 isl_int_fdiv_r(div->el[i], div->el[i], div->el[0]);
579 isl_int_fdiv_q(aff->v->el[i], aff->v->el[i], div->el[0]);
580 if (isl_int_gt(div->el[i], aff->v->el[0])) {
581 isl_int_sub(div->el[i], div->el[i], div->el[0]);
582 isl_int_add_ui(aff->v->el[i], aff->v->el[i], 1);
583 }
584 }
585
586 aff->ls = isl_local_space_add_div(aff->ls, div);
587 if (!aff->ls)
588 return isl_aff_free(aff);
589
590 size = aff->v->size;
591 aff->v = isl_vec_extend(aff->v, size + 1);
592 if (!aff->v)
593 return isl_aff_free(aff);
594 isl_int_set_si(aff->v->el[0], 1);
595 isl_int_set_si(aff->v->el[size], 1);
596
597 return aff;
598 }
599
600 /* Compute
601 *
602 * aff mod m = aff - m * floor(aff/m)
603 */
604 __isl_give isl_aff *isl_aff_mod(__isl_take isl_aff *aff, isl_int m)
605 {
606 isl_aff *res;
607
608 res = isl_aff_copy(aff);
609 aff = isl_aff_scale_down(aff, m);
610 aff = isl_aff_floor(aff);
611 aff = isl_aff_scale(aff, m);
612 res = isl_aff_sub(res, aff);
613
614 return res;
615 }
616
617 /* Compute
618 *
619 * pwaff mod m = pwaff - m * floor(pwaff/m)
620 */
621 __isl_give isl_pw_aff *isl_pw_aff_mod(__isl_take isl_pw_aff *pwaff, isl_int m)
622 {
623 isl_pw_aff *res;
624
625 res = isl_pw_aff_copy(pwaff);
626 pwaff = isl_pw_aff_scale_down(pwaff, m);
627 pwaff = isl_pw_aff_floor(pwaff);
628 pwaff = isl_pw_aff_scale(pwaff, m);
629 res = isl_pw_aff_sub(res, pwaff);
630
631 return res;
632 }
633
634 /* Given f, return ceil(f).
635 * If f is an integer expression, then just return f.
636 * Otherwise, create a new div d = [-f] and return the expression -d.
637 */
638 __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
639 {
640 if (!aff)
641 return NULL;
642
643 if (isl_int_is_one(aff->v->el[0]))
644 return aff;
645
646 aff = isl_aff_neg(aff);
647 aff = isl_aff_floor(aff);
648 aff = isl_aff_neg(aff);
649
650 return aff;
651 }
652
653 /* Apply the expansion computed by isl_merge_divs.
654 * The expansion itself is given by "exp" while the resulting
655 * list of divs is given by "div".
656 */
657 __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
658 __isl_take isl_mat *div, int *exp)
659 {
660 int i, j;
661 int old_n_div;
662 int new_n_div;
663 int offset;
664
665 aff = isl_aff_cow(aff);
666 if (!aff || !div)
667 goto error;
668
669 old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
670 new_n_div = isl_mat_rows(div);
671 if (new_n_div < old_n_div)
672 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
673 "not an expansion", goto error);
674
675 aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div);
676 if (!aff->v)
677 goto error;
678
679 offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
680 j = old_n_div - 1;
681 for (i = new_n_div - 1; i >= 0; --i) {
682 if (j >= 0 && exp[j] == i) {
683 if (i != j)
684 isl_int_swap(aff->v->el[offset + i],
685 aff->v->el[offset + j]);
686 j--;
687 } else
688 isl_int_set_si(aff->v->el[offset + i], 0);
689 }
690
691 aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div));
692 if (!aff->ls)
693 goto error;
694 isl_mat_free(div);
695 return aff;
696 error:
697 isl_aff_free(aff);
698 isl_mat_free(div);
699 return NULL;
700 }
701
702 /* Add two affine expressions that live in the same local space.
703 */
704 static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
705 __isl_take isl_aff *aff2)
706 {
707 isl_int gcd, f;
708
709 aff1 = isl_aff_cow(aff1);
710 if (!aff1 || !aff2)
711 goto error;
712
713 aff1->v = isl_vec_cow(aff1->v);
714 if (!aff1->v)
715 goto error;
716
717 isl_int_init(gcd);
718 isl_int_init(f);
719 isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
720 isl_int_divexact(f, aff2->v->el[0], gcd);
721 isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
722 isl_int_divexact(f, aff1->v->el[0], gcd);
723 isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
724 isl_int_divexact(f, aff2->v->el[0], gcd);
725 isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
726 isl_int_clear(f);
727 isl_int_clear(gcd);
728
729 isl_aff_free(aff2);
730 return aff1;
731 error:
732 isl_aff_free(aff1);
733 isl_aff_free(aff2);
734 return NULL;
735 }
736
737 __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
738 __isl_take isl_aff *aff2)
739 {
740 isl_ctx *ctx;
741 int *exp1 = NULL;
742 int *exp2 = NULL;
743 isl_mat *div;
744
745 if (!aff1 || !aff2)
746 goto error;
747
748 ctx = isl_aff_get_ctx(aff1);
749 if (!isl_space_is_equal(aff1->ls->dim, aff2->ls->dim))
750 isl_die(ctx, isl_error_invalid,
751 "spaces don't match", goto error);
752
753 if (aff1->ls->div->n_row == 0 && aff2->ls->div->n_row == 0)
754 return add_expanded(aff1, aff2);
755
756 exp1 = isl_alloc_array(ctx, int, aff1->ls->div->n_row);
757 exp2 = isl_alloc_array(ctx, int, aff2->ls->div->n_row);
758 if (!exp1 || !exp2)
759 goto error;
760
761 div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
762 aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
763 aff2 = isl_aff_expand_divs(aff2, div, exp2);
764 free(exp1);
765 free(exp2);
766
767 return add_expanded(aff1, aff2);
768 error:
769 free(exp1);
770 free(exp2);
771 isl_aff_free(aff1);
772 isl_aff_free(aff2);
773 return NULL;
774 }
775
776 __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
777 __isl_take isl_aff *aff2)
778 {
779 return isl_aff_add(aff1, isl_aff_neg(aff2));
780 }
781
782 __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
783 {
784 isl_int gcd;
785
786 if (isl_int_is_one(f))
787 return aff;
788
789 aff = isl_aff_cow(aff);
790 if (!aff)
791 return NULL;
792 aff->v = isl_vec_cow(aff->v);
793 if (!aff->v)
794 return isl_aff_free(aff);
795
796 isl_int_init(gcd);
797 isl_int_gcd(gcd, aff->v->el[0], f);
798 isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
799 isl_int_divexact(gcd, f, gcd);
800 isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
801 isl_int_clear(gcd);
802
803 return aff;
804 }
805
806 __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
807 {
808 isl_int gcd;
809
810 if (isl_int_is_one(f))
811 return aff;
812
813 aff = isl_aff_cow(aff);
814 if (!aff)
815 return NULL;
816 aff->v = isl_vec_cow(aff->v);
817 if (!aff->v)
818 return isl_aff_free(aff);
819
820 isl_int_init(gcd);
821 isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
822 isl_int_gcd(gcd, gcd, f);
823 isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
824 isl_int_divexact(gcd, f, gcd);
825 isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
826 isl_int_clear(gcd);
827
828 return aff;
829 }
830
831 __isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f)
832 {
833 isl_int v;
834
835 if (f == 1)
836 return aff;
837
838 isl_int_init(v);
839 isl_int_set_ui(v, f);
840 aff = isl_aff_scale_down(aff, v);
841 isl_int_clear(v);
842
843 return aff;
844 }
845
846 __isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff,
847 enum isl_dim_type type, unsigned pos, const char *s)
848 {
849 aff = isl_aff_cow(aff);
850 if (!aff)
851 return NULL;
852 if (type == isl_dim_out)
853 isl_die(aff->v->ctx, isl_error_invalid,
854 "cannot set name of output/set dimension",
855 return isl_aff_free(aff));
856 if (type == isl_dim_in)
857 type = isl_dim_set;
858 aff->ls = isl_local_space_set_dim_name(aff->ls, type, pos, s);
859 if (!aff->ls)
860 return isl_aff_free(aff);
861
862 return aff;
863 }
864
865 __isl_give isl_aff *isl_aff_set_dim_id(__isl_take isl_aff *aff,
866 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
867 {
868 aff = isl_aff_cow(aff);
869 if (!aff)
870 return isl_id_free(id);
871 if (type == isl_dim_out)
872 isl_die(aff->v->ctx, isl_error_invalid,
873 "cannot set name of output/set dimension",
874 goto error);
875 if (type == isl_dim_in)
876 type = isl_dim_set;
877 aff->ls = isl_local_space_set_dim_id(aff->ls, type, pos, id);
878 if (!aff->ls)
879 return isl_aff_free(aff);
880
881 return aff;
882 error:
883 isl_id_free(id);
884 isl_aff_free(aff);
885 return NULL;
886 }
887
888 /* Exploit the equalities in "eq" to simplify the affine expression
889 * and the expressions of the integer divisions in the local space.
890 * The integer divisions in this local space are assumed to appear
891 * as regular dimensions in "eq".
892 */
893 static __isl_give isl_aff *isl_aff_substitute_equalities_lifted(
894 __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
895 {
896 int i, j;
897 unsigned total;
898 unsigned n_div;
899
900 if (!eq)
901 goto error;
902 if (eq->n_eq == 0) {
903 isl_basic_set_free(eq);
904 return aff;
905 }
906
907 aff = isl_aff_cow(aff);
908 if (!aff)
909 goto error;
910
911 aff->ls = isl_local_space_substitute_equalities(aff->ls,
912 isl_basic_set_copy(eq));
913 if (!aff->ls)
914 goto error;
915
916 total = 1 + isl_space_dim(eq->dim, isl_dim_all);
917 n_div = eq->n_div;
918 for (i = 0; i < eq->n_eq; ++i) {
919 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
920 if (j < 0 || j == 0 || j >= total)
921 continue;
922
923 isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total,
924 &aff->v->el[0]);
925 }
926
927 isl_basic_set_free(eq);
928 return aff;
929 error:
930 isl_basic_set_free(eq);
931 isl_aff_free(aff);
932 return NULL;
933 }
934
935 /* Exploit the equalities in "eq" to simplify the affine expression
936 * and the expressions of the integer divisions in the local space.
937 */
938 static __isl_give isl_aff *isl_aff_substitute_equalities(
939 __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
940 {
941 int n_div;
942
943 if (!aff || !eq)
944 goto error;
945 n_div = isl_local_space_dim(aff->ls, isl_dim_div);
946 if (n_div > 0)
947 eq = isl_basic_set_add(eq, isl_dim_set, n_div);
948 return isl_aff_substitute_equalities_lifted(aff, eq);
949 error:
950 isl_basic_set_free(eq);
951 isl_aff_free(aff);
952 return NULL;
953 }
954
955 /* Look for equalities among the variables shared by context and aff
956 * and the integer divisions of aff, if any.
957 * The equalities are then used to eliminate coefficients and/or integer
958 * divisions from aff.
959 */
960 __isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
961 __isl_take isl_set *context)
962 {
963 isl_basic_set *hull;
964 int n_div;
965
966 if (!aff)
967 goto error;
968 n_div = isl_local_space_dim(aff->ls, isl_dim_div);
969 if (n_div > 0) {
970 isl_basic_set *bset;
971 isl_local_space *ls;
972 context = isl_set_add_dims(context, isl_dim_set, n_div);
973 ls = isl_aff_get_domain_local_space(aff);
974 bset = isl_basic_set_from_local_space(ls);
975 bset = isl_basic_set_lift(bset);
976 bset = isl_basic_set_flatten(bset);
977 context = isl_set_intersect(context,
978 isl_set_from_basic_set(bset));
979 }
980
981 hull = isl_set_affine_hull(context);
982 return isl_aff_substitute_equalities_lifted(aff, hull);
983 error:
984 isl_aff_free(aff);
985 isl_set_free(context);
986 return NULL;
987 }
988
989 /* Return a basic set containing those elements in the space
990 * of aff where it is non-negative.
991 */
992 __isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff)
993 {
994 isl_constraint *ineq;
995
996 ineq = isl_inequality_from_aff(aff);
997
998 return isl_basic_set_from_constraint(ineq);
999 }
1000
1001 /* Return a basic set containing those elements in the space
1002 * of aff where it is zero.
1003 */
1004 __isl_give isl_basic_set *isl_aff_zero_basic_set(__isl_take isl_aff *aff)
1005 {
1006 isl_constraint *ineq;
1007
1008 ineq = isl_equality_from_aff(aff);
1009
1010 return isl_basic_set_from_constraint(ineq);
1011 }
1012
1013 /* Return a basic set containing those elements in the shared space
1014 * of aff1 and aff2 where aff1 is greater than or equal to aff2.
1015 */
1016 __isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1,
1017 __isl_take isl_aff *aff2)
1018 {
1019 aff1 = isl_aff_sub(aff1, aff2);
1020
1021 return isl_aff_nonneg_basic_set(aff1);
1022 }
1023
1024 /* Return a basic set containing those elements in the shared space
1025 * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
1026 */
1027 __isl_give isl_basic_set *isl_aff_le_basic_set(__isl_take isl_aff *aff1,
1028 __isl_take isl_aff *aff2)
1029 {
1030 return isl_aff_ge_basic_set(aff2, aff1);
1031 }
1032
1033 __isl_give isl_aff *isl_aff_add_on_domain(__isl_keep isl_set *dom,
1034 __isl_take isl_aff *aff1, __isl_take isl_aff *aff2)
1035 {
1036 aff1 = isl_aff_add(aff1, aff2);
1037 aff1 = isl_aff_gist(aff1, isl_set_copy(dom));
1038 return aff1;
1039 }
1040
1041 int isl_aff_is_empty(__isl_keep isl_aff *aff)
1042 {
1043 if (!aff)
1044 return -1;
1045
1046 return 0;
1047 }
1048
1049 /* Check whether the given affine expression has non-zero coefficient
1050 * for any dimension in the given range or if any of these dimensions
1051 * appear with non-zero coefficients in any of the integer divisions
1052 * involved in the affine expression.
1053 */
1054 int isl_aff_involves_dims(__isl_keep isl_aff *aff,
1055 enum isl_dim_type type, unsigned first, unsigned n)
1056 {
1057 int i;
1058 isl_ctx *ctx;
1059 int *active = NULL;
1060 int involves = 0;
1061
1062 if (!aff)
1063 return -1;
1064 if (n == 0)
1065 return 0;
1066
1067 ctx = isl_aff_get_ctx(aff);
1068 if (first + n > isl_aff_dim(aff, type))
1069 isl_die(ctx, isl_error_invalid,
1070 "range out of bounds", return -1);
1071
1072 active = isl_local_space_get_active(aff->ls, aff->v->el + 2);
1073 if (!active)
1074 goto error;
1075
1076 first += isl_local_space_offset(aff->ls, type) - 1;
1077 for (i = 0; i < n; ++i)
1078 if (active[first + i]) {
1079 involves = 1;
1080 break;
1081 }
1082
1083 free(active);
1084
1085 return involves;
1086 error:
1087 free(active);
1088 return -1;
1089 }
1090
1091 __isl_give isl_aff *isl_aff_drop_dims(__isl_take isl_aff *aff,
1092 enum isl_dim_type type, unsigned first, unsigned n)
1093 {
1094 isl_ctx *ctx;
1095
1096 if (!aff)
1097 return NULL;
1098 if (type == isl_dim_out)
1099 isl_die(aff->v->ctx, isl_error_invalid,
1100 "cannot drop output/set dimension",
1101 return isl_aff_free(aff));
1102 if (type == isl_dim_in)
1103 type = isl_dim_set;
1104 if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1105 return aff;
1106
1107 ctx = isl_aff_get_ctx(aff);
1108 if (first + n > isl_local_space_dim(aff->ls, type))
1109 isl_die(ctx, isl_error_invalid, "range out of bounds",
1110 return isl_aff_free(aff));
1111
1112 aff = isl_aff_cow(aff);
1113 if (!aff)
1114 return NULL;
1115
1116 aff->ls = isl_local_space_drop_dims(aff->ls, type, first, n);
1117 if (!aff->ls)
1118 return isl_aff_free(aff);
1119
1120 first += 1 + isl_local_space_offset(aff->ls, type);
1121 aff->v = isl_vec_drop_els(aff->v, first, n);
1122 if (!aff->v)
1123 return isl_aff_free(aff);
1124
1125 return aff;
1126 }
1127
1128 __isl_give isl_aff *isl_aff_insert_dims(__isl_take isl_aff *aff,
1129 enum isl_dim_type type, unsigned first, unsigned n)
1130 {
1131 isl_ctx *ctx;
1132
1133 if (!aff)
1134 return NULL;
1135 if (type == isl_dim_out)
1136 isl_die(aff->v->ctx, isl_error_invalid,
1137 "cannot insert output/set dimensions",
1138 return isl_aff_free(aff));
1139 if (type == isl_dim_in)
1140 type = isl_dim_set;
1141 if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1142 return aff;
1143
1144 ctx = isl_aff_get_ctx(aff);
1145 if (first > isl_local_space_dim(aff->ls, type))
1146 isl_die(ctx, isl_error_invalid, "position out of bounds",
1147 return isl_aff_free(aff));
1148
1149 aff = isl_aff_cow(aff);
1150 if (!aff)
1151 return NULL;
1152
1153 aff->ls = isl_local_space_insert_dims(aff->ls, type, first, n);
1154 if (!aff->ls)
1155 return isl_aff_free(aff);
1156
1157 first += 1 + isl_local_space_offset(aff->ls, type);
1158 aff->v = isl_vec_insert_zero_els(aff->v, first, n);
1159 if (!aff->v)
1160 return isl_aff_free(aff);
1161
1162 return aff;
1163 }
1164
1165 __isl_give isl_aff *isl_aff_add_dims(__isl_take isl_aff *aff,
1166 enum isl_dim_type type, unsigned n)
1167 {
1168 unsigned pos;
1169
1170 pos = isl_aff_dim(aff, type);
1171
1172 return isl_aff_insert_dims(aff, type, pos, n);
1173 }
1174
1175 __isl_give isl_pw_aff *isl_pw_aff_add_dims(__isl_take isl_pw_aff *pwaff,
1176 enum isl_dim_type type, unsigned n)
1177 {
1178 unsigned pos;
1179
1180 pos = isl_pw_aff_dim(pwaff, type);
1181
1182 return isl_pw_aff_insert_dims(pwaff, type, pos, n);
1183 }
1184
1185 __isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff)
1186 {
1187 isl_set *dom = isl_set_universe(isl_aff_get_domain_space(aff));
1188 return isl_pw_aff_alloc(dom, aff);
1189 }
1190
1191 #undef PW
1192 #define PW isl_pw_aff
1193 #undef EL
1194 #define EL isl_aff
1195 #undef EL_IS_ZERO
1196 #define EL_IS_ZERO is_empty
1197 #undef ZERO
1198 #define ZERO empty
1199 #undef IS_ZERO
1200 #define IS_ZERO is_empty
1201 #undef FIELD
1202 #define FIELD aff
1203
1204 #define NO_EVAL
1205 #define NO_OPT
1206 #define NO_MOVE_DIMS
1207 #define NO_LIFT
1208 #define NO_MORPH
1209
1210 #include <isl_pw_templ.c>
1211
1212 static __isl_give isl_set *align_params_pw_pw_set_and(
1213 __isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2,
1214 __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1215 __isl_take isl_pw_aff *pwaff2))
1216 {
1217 if (!pwaff1 || !pwaff2)
1218 goto error;
1219 if (isl_space_match(pwaff1->dim, isl_dim_param,
1220 pwaff2->dim, isl_dim_param))
1221 return fn(pwaff1, pwaff2);
1222 if (!isl_space_has_named_params(pwaff1->dim) ||
1223 !isl_space_has_named_params(pwaff2->dim))
1224 isl_die(isl_pw_aff_get_ctx(pwaff1), isl_error_invalid,
1225 "unaligned unnamed parameters", goto error);
1226 pwaff1 = isl_pw_aff_align_params(pwaff1, isl_pw_aff_get_space(pwaff2));
1227 pwaff2 = isl_pw_aff_align_params(pwaff2, isl_pw_aff_get_space(pwaff1));
1228 return fn(pwaff1, pwaff2);
1229 error:
1230 isl_pw_aff_free(pwaff1);
1231 isl_pw_aff_free(pwaff2);
1232 return NULL;
1233 }
1234
1235 /* Compute a piecewise quasi-affine expression with a domain that
1236 * is the union of those of pwaff1 and pwaff2 and such that on each
1237 * cell, the quasi-affine expression is the better (according to cmp)
1238 * of those of pwaff1 and pwaff2. If only one of pwaff1 or pwaff2
1239 * is defined on a given cell, then the associated expression
1240 * is the defined one.
1241 */
1242 static __isl_give isl_pw_aff *pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1243 __isl_take isl_pw_aff *pwaff2,
1244 __isl_give isl_basic_set *(*cmp)(__isl_take isl_aff *aff1,
1245 __isl_take isl_aff *aff2))
1246 {
1247 int i, j, n;
1248 isl_pw_aff *res;
1249 isl_ctx *ctx;
1250 isl_set *set;
1251
1252 if (!pwaff1 || !pwaff2)
1253 goto error;
1254
1255 ctx = isl_space_get_ctx(pwaff1->dim);
1256 if (!isl_space_is_equal(pwaff1->dim, pwaff2->dim))
1257 isl_die(ctx, isl_error_invalid,
1258 "arguments should live in same space", goto error);
1259
1260 if (isl_pw_aff_is_empty(pwaff1)) {
1261 isl_pw_aff_free(pwaff1);
1262 return pwaff2;
1263 }
1264
1265 if (isl_pw_aff_is_empty(pwaff2)) {
1266 isl_pw_aff_free(pwaff2);
1267 return pwaff1;
1268 }
1269
1270 n = 2 * (pwaff1->n + 1) * (pwaff2->n + 1);
1271 res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1272
1273 for (i = 0; i < pwaff1->n; ++i) {
1274 set = isl_set_copy(pwaff1->p[i].set);
1275 for (j = 0; j < pwaff2->n; ++j) {
1276 struct isl_set *common;
1277 isl_set *better;
1278
1279 common = isl_set_intersect(
1280 isl_set_copy(pwaff1->p[i].set),
1281 isl_set_copy(pwaff2->p[j].set));
1282 better = isl_set_from_basic_set(cmp(
1283 isl_aff_copy(pwaff2->p[j].aff),
1284 isl_aff_copy(pwaff1->p[i].aff)));
1285 better = isl_set_intersect(common, better);
1286 if (isl_set_plain_is_empty(better)) {
1287 isl_set_free(better);
1288 continue;
1289 }
1290 set = isl_set_subtract(set, isl_set_copy(better));
1291
1292 res = isl_pw_aff_add_piece(res, better,
1293 isl_aff_copy(pwaff2->p[j].aff));
1294 }
1295 res = isl_pw_aff_add_piece(res, set,
1296 isl_aff_copy(pwaff1->p[i].aff));
1297 }
1298
1299 for (j = 0; j < pwaff2->n; ++j) {
1300 set = isl_set_copy(pwaff2->p[j].set);
1301 for (i = 0; i < pwaff1->n; ++i)
1302 set = isl_set_subtract(set,
1303 isl_set_copy(pwaff1->p[i].set));
1304 res = isl_pw_aff_add_piece(res, set,
1305 isl_aff_copy(pwaff2->p[j].aff));
1306 }
1307
1308 isl_pw_aff_free(pwaff1);
1309 isl_pw_aff_free(pwaff2);
1310
1311 return res;
1312 error:
1313 isl_pw_aff_free(pwaff1);
1314 isl_pw_aff_free(pwaff2);
1315 return NULL;
1316 }
1317
1318 /* Compute a piecewise quasi-affine expression with a domain that
1319 * is the union of those of pwaff1 and pwaff2 and such that on each
1320 * cell, the quasi-affine expression is the maximum of those of pwaff1
1321 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1322 * cell, then the associated expression is the defined one.
1323 */
1324 static __isl_give isl_pw_aff *pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1325 __isl_take isl_pw_aff *pwaff2)
1326 {
1327 return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_ge_basic_set);
1328 }
1329
1330 __isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1331 __isl_take isl_pw_aff *pwaff2)
1332 {
1333 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_union_max);
1334 }
1335
1336 /* Compute a piecewise quasi-affine expression with a domain that
1337 * is the union of those of pwaff1 and pwaff2 and such that on each
1338 * cell, the quasi-affine expression is the minimum of those of pwaff1
1339 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1340 * cell, then the associated expression is the defined one.
1341 */
1342 static __isl_give isl_pw_aff *pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1343 __isl_take isl_pw_aff *pwaff2)
1344 {
1345 return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_le_basic_set);
1346 }
1347
1348 __isl_give isl_pw_aff *isl_pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1349 __isl_take isl_pw_aff *pwaff2)
1350 {
1351 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_union_min);
1352 }
1353
1354 __isl_give isl_pw_aff *isl_pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1355 __isl_take isl_pw_aff *pwaff2, int max)
1356 {
1357 if (max)
1358 return isl_pw_aff_union_max(pwaff1, pwaff2);
1359 else
1360 return isl_pw_aff_union_min(pwaff1, pwaff2);
1361 }
1362
1363 /* Construct a map with as domain the domain of pwaff and
1364 * one-dimensional range corresponding to the affine expressions.
1365 */
1366 static __isl_give isl_map *map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1367 {
1368 int i;
1369 isl_space *dim;
1370 isl_map *map;
1371
1372 if (!pwaff)
1373 return NULL;
1374
1375 dim = isl_pw_aff_get_space(pwaff);
1376 map = isl_map_empty(dim);
1377
1378 for (i = 0; i < pwaff->n; ++i) {
1379 isl_basic_map *bmap;
1380 isl_map *map_i;
1381
1382 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
1383 map_i = isl_map_from_basic_map(bmap);
1384 map_i = isl_map_intersect_domain(map_i,
1385 isl_set_copy(pwaff->p[i].set));
1386 map = isl_map_union_disjoint(map, map_i);
1387 }
1388
1389 isl_pw_aff_free(pwaff);
1390
1391 return map;
1392 }
1393
1394 /* Construct a map with as domain the domain of pwaff and
1395 * one-dimensional range corresponding to the affine expressions.
1396 */
1397 __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1398 {
1399 if (isl_space_is_set(pwaff->dim))
1400 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1401 "space of input is not a map",
1402 return isl_pw_aff_free(pwaff));
1403 return map_from_pw_aff(pwaff);
1404 }
1405
1406 /* Construct a one-dimensional set with as parameter domain
1407 * the domain of pwaff and the single set dimension
1408 * corresponding to the affine expressions.
1409 */
1410 __isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1411 {
1412 if (!isl_space_is_set(pwaff->dim))
1413 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1414 "space of input is not a set",
1415 return isl_pw_aff_free(pwaff));
1416 return map_from_pw_aff(pwaff);
1417 }
1418
1419 /* Return a set containing those elements in the domain
1420 * of pwaff where it is non-negative.
1421 */
1422 __isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
1423 {
1424 int i;
1425 isl_set *set;
1426
1427 if (!pwaff)
1428 return NULL;
1429
1430 set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1431
1432 for (i = 0; i < pwaff->n; ++i) {
1433 isl_basic_set *bset;
1434 isl_set *set_i;
1435
1436 bset = isl_aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff));
1437 set_i = isl_set_from_basic_set(bset);
1438 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1439 set = isl_set_union_disjoint(set, set_i);
1440 }
1441
1442 isl_pw_aff_free(pwaff);
1443
1444 return set;
1445 }
1446
1447 /* Return a set containing those elements in the domain
1448 * of pwaff where it is zero.
1449 */
1450 __isl_give isl_set *isl_pw_aff_zero_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_zero_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 not zero.
1477 */
1478 __isl_give isl_set *isl_pw_aff_non_zero_set(__isl_take isl_pw_aff *pwaff)
1479 {
1480 return isl_set_complement(isl_pw_aff_zero_set(pwaff));
1481 }
1482
1483 /* Return a set containing those elements in the shared domain
1484 * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
1485 *
1486 * We compute the difference on the shared domain and then construct
1487 * the set of values where this difference is non-negative.
1488 * If strict is set, we first subtract 1 from the difference.
1489 * If equal is set, we only return the elements where pwaff1 and pwaff2
1490 * are equal.
1491 */
1492 static __isl_give isl_set *pw_aff_gte_set(__isl_take isl_pw_aff *pwaff1,
1493 __isl_take isl_pw_aff *pwaff2, int strict, int equal)
1494 {
1495 isl_set *set1, *set2;
1496
1497 set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1));
1498 set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2));
1499 set1 = isl_set_intersect(set1, set2);
1500 pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1));
1501 pwaff2 = isl_pw_aff_intersect_domain(pwaff2, isl_set_copy(set1));
1502 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2));
1503
1504 if (strict) {
1505 isl_space *dim = isl_set_get_space(set1);
1506 isl_aff *aff;
1507 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
1508 aff = isl_aff_add_constant_si(aff, -1);
1509 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_alloc(set1, aff));
1510 } else
1511 isl_set_free(set1);
1512
1513 if (equal)
1514 return isl_pw_aff_zero_set(pwaff1);
1515 return isl_pw_aff_nonneg_set(pwaff1);
1516 }
1517
1518 /* Return a set containing those elements in the shared domain
1519 * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
1520 */
1521 static __isl_give isl_set *pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1522 __isl_take isl_pw_aff *pwaff2)
1523 {
1524 return pw_aff_gte_set(pwaff1, pwaff2, 0, 1);
1525 }
1526
1527 __isl_give isl_set *isl_pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1528 __isl_take isl_pw_aff *pwaff2)
1529 {
1530 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_eq_set);
1531 }
1532
1533 /* Return a set containing those elements in the shared domain
1534 * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
1535 */
1536 static __isl_give isl_set *pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1537 __isl_take isl_pw_aff *pwaff2)
1538 {
1539 return pw_aff_gte_set(pwaff1, pwaff2, 0, 0);
1540 }
1541
1542 __isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1543 __isl_take isl_pw_aff *pwaff2)
1544 {
1545 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ge_set);
1546 }
1547
1548 /* Return a set containing those elements in the shared domain
1549 * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
1550 */
1551 static __isl_give isl_set *pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1552 __isl_take isl_pw_aff *pwaff2)
1553 {
1554 return pw_aff_gte_set(pwaff1, pwaff2, 1, 0);
1555 }
1556
1557 __isl_give isl_set *isl_pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1558 __isl_take isl_pw_aff *pwaff2)
1559 {
1560 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_gt_set);
1561 }
1562
1563 __isl_give isl_set *isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1,
1564 __isl_take isl_pw_aff *pwaff2)
1565 {
1566 return isl_pw_aff_ge_set(pwaff2, pwaff1);
1567 }
1568
1569 __isl_give isl_set *isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1,
1570 __isl_take isl_pw_aff *pwaff2)
1571 {
1572 return isl_pw_aff_gt_set(pwaff2, pwaff1);
1573 }
1574
1575 /* Return a set containing those elements in the shared domain
1576 * of the elements of list1 and list2 where each element in list1
1577 * has the relation specified by "fn" with each element in list2.
1578 */
1579 static __isl_give isl_set *pw_aff_list_set(__isl_take isl_pw_aff_list *list1,
1580 __isl_take isl_pw_aff_list *list2,
1581 __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1582 __isl_take isl_pw_aff *pwaff2))
1583 {
1584 int i, j;
1585 isl_ctx *ctx;
1586 isl_set *set;
1587
1588 if (!list1 || !list2)
1589 goto error;
1590
1591 ctx = isl_pw_aff_list_get_ctx(list1);
1592 if (list1->n < 1 || list2->n < 1)
1593 isl_die(ctx, isl_error_invalid,
1594 "list should contain at least one element", goto error);
1595
1596 set = isl_set_universe(isl_pw_aff_get_domain_space(list1->p[0]));
1597 for (i = 0; i < list1->n; ++i)
1598 for (j = 0; j < list2->n; ++j) {
1599 isl_set *set_ij;
1600
1601 set_ij = fn(isl_pw_aff_copy(list1->p[i]),
1602 isl_pw_aff_copy(list2->p[j]));
1603 set = isl_set_intersect(set, set_ij);
1604 }
1605
1606 isl_pw_aff_list_free(list1);
1607 isl_pw_aff_list_free(list2);
1608 return set;
1609 error:
1610 isl_pw_aff_list_free(list1);
1611 isl_pw_aff_list_free(list2);
1612 return NULL;
1613 }
1614
1615 /* Return a set containing those elements in the shared domain
1616 * of the elements of list1 and list2 where each element in list1
1617 * is equal to each element in list2.
1618 */
1619 __isl_give isl_set *isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list *list1,
1620 __isl_take isl_pw_aff_list *list2)
1621 {
1622 return pw_aff_list_set(list1, list2, &isl_pw_aff_eq_set);
1623 }
1624
1625 __isl_give isl_set *isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list *list1,
1626 __isl_take isl_pw_aff_list *list2)
1627 {
1628 return pw_aff_list_set(list1, list2, &isl_pw_aff_ne_set);
1629 }
1630
1631 /* Return a set containing those elements in the shared domain
1632 * of the elements of list1 and list2 where each element in list1
1633 * is less than or equal to each element in list2.
1634 */
1635 __isl_give isl_set *isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list *list1,
1636 __isl_take isl_pw_aff_list *list2)
1637 {
1638 return pw_aff_list_set(list1, list2, &isl_pw_aff_le_set);
1639 }
1640
1641 __isl_give isl_set *isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list *list1,
1642 __isl_take isl_pw_aff_list *list2)
1643 {
1644 return pw_aff_list_set(list1, list2, &isl_pw_aff_lt_set);
1645 }
1646
1647 __isl_give isl_set *isl_pw_aff_list_ge_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_ge_set);
1651 }
1652
1653 __isl_give isl_set *isl_pw_aff_list_gt_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_gt_set);
1657 }
1658
1659
1660 /* Return a set containing those elements in the shared domain
1661 * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
1662 */
1663 static __isl_give isl_set *pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1664 __isl_take isl_pw_aff *pwaff2)
1665 {
1666 isl_set *set_lt, *set_gt;
1667
1668 set_lt = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1),
1669 isl_pw_aff_copy(pwaff2));
1670 set_gt = isl_pw_aff_gt_set(pwaff1, pwaff2);
1671 return isl_set_union_disjoint(set_lt, set_gt);
1672 }
1673
1674 __isl_give isl_set *isl_pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1675 __isl_take isl_pw_aff *pwaff2)
1676 {
1677 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ne_set);
1678 }
1679
1680 __isl_give isl_pw_aff *isl_pw_aff_scale_down(__isl_take isl_pw_aff *pwaff,
1681 isl_int v)
1682 {
1683 int i;
1684
1685 if (isl_int_is_one(v))
1686 return pwaff;
1687 if (!isl_int_is_pos(v))
1688 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1689 "factor needs to be positive",
1690 return isl_pw_aff_free(pwaff));
1691 pwaff = isl_pw_aff_cow(pwaff);
1692 if (!pwaff)
1693 return NULL;
1694 if (pwaff->n == 0)
1695 return pwaff;
1696
1697 for (i = 0; i < pwaff->n; ++i) {
1698 pwaff->p[i].aff = isl_aff_scale_down(pwaff->p[i].aff, v);
1699 if (!pwaff->p[i].aff)
1700 return isl_pw_aff_free(pwaff);
1701 }
1702
1703 return pwaff;
1704 }
1705
1706 __isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff)
1707 {
1708 int i;
1709
1710 pwaff = isl_pw_aff_cow(pwaff);
1711 if (!pwaff)
1712 return NULL;
1713 if (pwaff->n == 0)
1714 return pwaff;
1715
1716 for (i = 0; i < pwaff->n; ++i) {
1717 pwaff->p[i].aff = isl_aff_floor(pwaff->p[i].aff);
1718 if (!pwaff->p[i].aff)
1719 return isl_pw_aff_free(pwaff);
1720 }
1721
1722 return pwaff;
1723 }
1724
1725 __isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff)
1726 {
1727 int i;
1728
1729 pwaff = isl_pw_aff_cow(pwaff);
1730 if (!pwaff)
1731 return NULL;
1732 if (pwaff->n == 0)
1733 return pwaff;
1734
1735 for (i = 0; i < pwaff->n; ++i) {
1736 pwaff->p[i].aff = isl_aff_ceil(pwaff->p[i].aff);
1737 if (!pwaff->p[i].aff)
1738 return isl_pw_aff_free(pwaff);
1739 }
1740
1741 return pwaff;
1742 }
1743
1744 /* Return an affine expression that is equal to pwaff_true for elements
1745 * in "cond" and to pwaff_false for elements not in "cond".
1746 * That is, return cond ? pwaff_true : pwaff_false;
1747 */
1748 __isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_set *cond,
1749 __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false)
1750 {
1751 isl_set *comp;
1752
1753 comp = isl_set_complement(isl_set_copy(cond));
1754 pwaff_true = isl_pw_aff_intersect_domain(pwaff_true, cond);
1755 pwaff_false = isl_pw_aff_intersect_domain(pwaff_false, comp);
1756
1757 return isl_pw_aff_add_disjoint(pwaff_true, pwaff_false);
1758 }
1759
1760 int isl_aff_is_cst(__isl_keep isl_aff *aff)
1761 {
1762 if (!aff)
1763 return -1;
1764
1765 return isl_seq_first_non_zero(aff->v->el + 2, aff->v->size - 2) == -1;
1766 }
1767
1768 /* Check whether pwaff is a piecewise constant.
1769 */
1770 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff)
1771 {
1772 int i;
1773
1774 if (!pwaff)
1775 return -1;
1776
1777 for (i = 0; i < pwaff->n; ++i) {
1778 int is_cst = isl_aff_is_cst(pwaff->p[i].aff);
1779 if (is_cst < 0 || !is_cst)
1780 return is_cst;
1781 }
1782
1783 return 1;
1784 }
1785
1786 __isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
1787 __isl_take isl_aff *aff2)
1788 {
1789 if (!isl_aff_is_cst(aff2) && isl_aff_is_cst(aff1))
1790 return isl_aff_mul(aff2, aff1);
1791
1792 if (!isl_aff_is_cst(aff2))
1793 isl_die(isl_aff_get_ctx(aff1), isl_error_invalid,
1794 "at least one affine expression should be constant",
1795 goto error);
1796
1797 aff1 = isl_aff_cow(aff1);
1798 if (!aff1 || !aff2)
1799 goto error;
1800
1801 aff1 = isl_aff_scale(aff1, aff2->v->el[1]);
1802 aff1 = isl_aff_scale_down(aff1, aff2->v->el[0]);
1803
1804 isl_aff_free(aff2);
1805 return aff1;
1806 error:
1807 isl_aff_free(aff1);
1808 isl_aff_free(aff2);
1809 return NULL;
1810 }
1811
1812 static __isl_give isl_pw_aff *pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1813 __isl_take isl_pw_aff *pwaff2)
1814 {
1815 int i, j, n;
1816 isl_pw_aff *res;
1817
1818 if (!pwaff1 || !pwaff2)
1819 goto error;
1820
1821 n = pwaff1->n * pwaff2->n;
1822 res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1823
1824 for (i = 0; i < pwaff1->n; ++i) {
1825 for (j = 0; j < pwaff2->n; ++j) {
1826 isl_set *common;
1827 isl_aff *prod;
1828 common = isl_set_intersect(
1829 isl_set_copy(pwaff1->p[i].set),
1830 isl_set_copy(pwaff2->p[j].set));
1831 if (isl_set_plain_is_empty(common)) {
1832 isl_set_free(common);
1833 continue;
1834 }
1835
1836 prod = isl_aff_mul(isl_aff_copy(pwaff1->p[i].aff),
1837 isl_aff_copy(pwaff2->p[j].aff));
1838
1839 res = isl_pw_aff_add_piece(res, common, prod);
1840 }
1841 }
1842
1843 isl_pw_aff_free(pwaff1);
1844 isl_pw_aff_free(pwaff2);
1845 return res;
1846 error:
1847 isl_pw_aff_free(pwaff1);
1848 isl_pw_aff_free(pwaff2);
1849 return NULL;
1850 }
1851
1852 __isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1853 __isl_take isl_pw_aff *pwaff2)
1854 {
1855 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul);
1856 }
1857
1858 static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1859 __isl_take isl_pw_aff *pwaff2)
1860 {
1861 isl_set *le;
1862
1863 le = isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1),
1864 isl_pw_aff_copy(pwaff2));
1865 return isl_pw_aff_cond(le, pwaff1, pwaff2);
1866 }
1867
1868 __isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1869 __isl_take isl_pw_aff *pwaff2)
1870 {
1871 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_min);
1872 }
1873
1874 static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1875 __isl_take isl_pw_aff *pwaff2)
1876 {
1877 isl_set *le;
1878
1879 le = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1),
1880 isl_pw_aff_copy(pwaff2));
1881 return isl_pw_aff_cond(le, pwaff1, pwaff2);
1882 }
1883
1884 __isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1885 __isl_take isl_pw_aff *pwaff2)
1886 {
1887 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_max);
1888 }
1889
1890 static __isl_give isl_pw_aff *pw_aff_list_reduce(
1891 __isl_take isl_pw_aff_list *list,
1892 __isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pwaff1,
1893 __isl_take isl_pw_aff *pwaff2))
1894 {
1895 int i;
1896 isl_ctx *ctx;
1897 isl_pw_aff *res;
1898
1899 if (!list)
1900 return NULL;
1901
1902 ctx = isl_pw_aff_list_get_ctx(list);
1903 if (list->n < 1)
1904 isl_die(ctx, isl_error_invalid,
1905 "list should contain at least one element",
1906 return isl_pw_aff_list_free(list));
1907
1908 res = isl_pw_aff_copy(list->p[0]);
1909 for (i = 1; i < list->n; ++i)
1910 res = fn(res, isl_pw_aff_copy(list->p[i]));
1911
1912 isl_pw_aff_list_free(list);
1913 return res;
1914 }
1915
1916 /* Return an isl_pw_aff that maps each element in the intersection of the
1917 * domains of the elements of list to the minimal corresponding affine
1918 * expression.
1919 */
1920 __isl_give isl_pw_aff *isl_pw_aff_list_min(__isl_take isl_pw_aff_list *list)
1921 {
1922 return pw_aff_list_reduce(list, &isl_pw_aff_min);
1923 }
1924
1925 /* Return an isl_pw_aff that maps each element in the intersection of the
1926 * domains of the elements of list to the maximal corresponding affine
1927 * expression.
1928 */
1929 __isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list)
1930 {
1931 return pw_aff_list_reduce(list, &isl_pw_aff_max);
1932 }
Integer set library