?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
add isl_space_set_from_params
[isl.git] / isl_aff.c
blob65334680c12e2ee4c76024790250031670a42a29
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 /* Exploit the equalities in "eq" to simplify the affine expression
866 * and the expressions of the integer divisions in the local space.
867 * The integer divisions in this local space are assumed to appear
868 * as regular dimensions in "eq".
869 */
870 static __isl_give isl_aff *isl_aff_substitute_equalities_lifted(
871 __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
872 {
873 int i, j;
874 unsigned total;
875 unsigned n_div;
876
877 if (!eq)
878 goto error;
879 if (eq->n_eq == 0) {
880 isl_basic_set_free(eq);
881 return aff;
882 }
883
884 aff = isl_aff_cow(aff);
885 if (!aff)
886 goto error;
887
888 aff->ls = isl_local_space_substitute_equalities(aff->ls,
889 isl_basic_set_copy(eq));
890 if (!aff->ls)
891 goto error;
892
893 total = 1 + isl_space_dim(eq->dim, isl_dim_all);
894 n_div = eq->n_div;
895 for (i = 0; i < eq->n_eq; ++i) {
896 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
897 if (j < 0 || j == 0 || j >= total)
898 continue;
899
900 isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total,
901 &aff->v->el[0]);
902 }
903
904 isl_basic_set_free(eq);
905 return aff;
906 error:
907 isl_basic_set_free(eq);
908 isl_aff_free(aff);
909 return NULL;
910 }
911
912 /* Exploit the equalities in "eq" to simplify the affine expression
913 * and the expressions of the integer divisions in the local space.
914 */
915 static __isl_give isl_aff *isl_aff_substitute_equalities(
916 __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
917 {
918 int n_div;
919
920 if (!aff || !eq)
921 goto error;
922 n_div = isl_local_space_dim(aff->ls, isl_dim_div);
923 if (n_div > 0)
924 eq = isl_basic_set_add(eq, isl_dim_set, n_div);
925 return isl_aff_substitute_equalities_lifted(aff, eq);
926 error:
927 isl_basic_set_free(eq);
928 isl_aff_free(aff);
929 return NULL;
930 }
931
932 /* Look for equalities among the variables shared by context and aff
933 * and the integer divisions of aff, if any.
934 * The equalities are then used to eliminate coefficients and/or integer
935 * divisions from aff.
936 */
937 __isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
938 __isl_take isl_set *context)
939 {
940 isl_basic_set *hull;
941 int n_div;
942
943 if (!aff)
944 goto error;
945 n_div = isl_local_space_dim(aff->ls, isl_dim_div);
946 if (n_div > 0) {
947 isl_basic_set *bset;
948 isl_local_space *ls;
949 context = isl_set_add_dims(context, isl_dim_set, n_div);
950 ls = isl_aff_get_domain_local_space(aff);
951 bset = isl_basic_set_from_local_space(ls);
952 bset = isl_basic_set_lift(bset);
953 bset = isl_basic_set_flatten(bset);
954 context = isl_set_intersect(context,
955 isl_set_from_basic_set(bset));
956 }
957
958 hull = isl_set_affine_hull(context);
959 return isl_aff_substitute_equalities_lifted(aff, hull);
960 error:
961 isl_aff_free(aff);
962 isl_set_free(context);
963 return NULL;
964 }
965
966 /* Return a basic set containing those elements in the space
967 * of aff where it is non-negative.
968 */
969 __isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff)
970 {
971 isl_constraint *ineq;
972
973 ineq = isl_inequality_from_aff(aff);
974
975 return isl_basic_set_from_constraint(ineq);
976 }
977
978 /* Return a basic set containing those elements in the space
979 * of aff where it is zero.
980 */
981 __isl_give isl_basic_set *isl_aff_zero_basic_set(__isl_take isl_aff *aff)
982 {
983 isl_constraint *ineq;
984
985 ineq = isl_equality_from_aff(aff);
986
987 return isl_basic_set_from_constraint(ineq);
988 }
989
990 /* Return a basic set containing those elements in the shared space
991 * of aff1 and aff2 where aff1 is greater than or equal to aff2.
992 */
993 __isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1,
994 __isl_take isl_aff *aff2)
995 {
996 aff1 = isl_aff_sub(aff1, aff2);
997
998 return isl_aff_nonneg_basic_set(aff1);
999 }
1000
1001 /* Return a basic set containing those elements in the shared space
1002 * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
1003 */
1004 __isl_give isl_basic_set *isl_aff_le_basic_set(__isl_take isl_aff *aff1,
1005 __isl_take isl_aff *aff2)
1006 {
1007 return isl_aff_ge_basic_set(aff2, aff1);
1008 }
1009
1010 __isl_give isl_aff *isl_aff_add_on_domain(__isl_keep isl_set *dom,
1011 __isl_take isl_aff *aff1, __isl_take isl_aff *aff2)
1012 {
1013 aff1 = isl_aff_add(aff1, aff2);
1014 aff1 = isl_aff_gist(aff1, isl_set_copy(dom));
1015 return aff1;
1016 }
1017
1018 int isl_aff_is_empty(__isl_keep isl_aff *aff)
1019 {
1020 if (!aff)
1021 return -1;
1022
1023 return 0;
1024 }
1025
1026 /* Check whether the given affine expression has non-zero coefficient
1027 * for any dimension in the given range or if any of these dimensions
1028 * appear with non-zero coefficients in any of the integer divisions
1029 * involved in the affine expression.
1030 */
1031 int isl_aff_involves_dims(__isl_keep isl_aff *aff,
1032 enum isl_dim_type type, unsigned first, unsigned n)
1033 {
1034 int i;
1035 isl_ctx *ctx;
1036 int *active = NULL;
1037 int involves = 0;
1038
1039 if (!aff)
1040 return -1;
1041 if (n == 0)
1042 return 0;
1043
1044 ctx = isl_aff_get_ctx(aff);
1045 if (first + n > isl_aff_dim(aff, type))
1046 isl_die(ctx, isl_error_invalid,
1047 "range out of bounds", return -1);
1048
1049 active = isl_local_space_get_active(aff->ls, aff->v->el + 2);
1050 if (!active)
1051 goto error;
1052
1053 first += isl_local_space_offset(aff->ls, type) - 1;
1054 for (i = 0; i < n; ++i)
1055 if (active[first + i]) {
1056 involves = 1;
1057 break;
1058 }
1059
1060 free(active);
1061
1062 return involves;
1063 error:
1064 free(active);
1065 return -1;
1066 }
1067
1068 __isl_give isl_aff *isl_aff_drop_dims(__isl_take isl_aff *aff,
1069 enum isl_dim_type type, unsigned first, unsigned n)
1070 {
1071 isl_ctx *ctx;
1072
1073 if (!aff)
1074 return NULL;
1075 if (type == isl_dim_out)
1076 isl_die(aff->v->ctx, isl_error_invalid,
1077 "cannot drop output/set dimension",
1078 return isl_aff_free(aff));
1079 if (type == isl_dim_in)
1080 type = isl_dim_set;
1081 if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1082 return aff;
1083
1084 ctx = isl_aff_get_ctx(aff);
1085 if (first + n > isl_local_space_dim(aff->ls, type))
1086 isl_die(ctx, isl_error_invalid, "range out of bounds",
1087 return isl_aff_free(aff));
1088
1089 aff = isl_aff_cow(aff);
1090 if (!aff)
1091 return NULL;
1092
1093 aff->ls = isl_local_space_drop_dims(aff->ls, type, first, n);
1094 if (!aff->ls)
1095 return isl_aff_free(aff);
1096
1097 first += 1 + isl_local_space_offset(aff->ls, type);
1098 aff->v = isl_vec_drop_els(aff->v, first, n);
1099 if (!aff->v)
1100 return isl_aff_free(aff);
1101
1102 return aff;
1103 }
1104
1105 __isl_give isl_aff *isl_aff_insert_dims(__isl_take isl_aff *aff,
1106 enum isl_dim_type type, unsigned first, unsigned n)
1107 {
1108 isl_ctx *ctx;
1109
1110 if (!aff)
1111 return NULL;
1112 if (type == isl_dim_out)
1113 isl_die(aff->v->ctx, isl_error_invalid,
1114 "cannot insert output/set dimensions",
1115 return isl_aff_free(aff));
1116 if (type == isl_dim_in)
1117 type = isl_dim_set;
1118 if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
1119 return aff;
1120
1121 ctx = isl_aff_get_ctx(aff);
1122 if (first > isl_local_space_dim(aff->ls, type))
1123 isl_die(ctx, isl_error_invalid, "position out of bounds",
1124 return isl_aff_free(aff));
1125
1126 aff = isl_aff_cow(aff);
1127 if (!aff)
1128 return NULL;
1129
1130 aff->ls = isl_local_space_insert_dims(aff->ls, type, first, n);
1131 if (!aff->ls)
1132 return isl_aff_free(aff);
1133
1134 first += 1 + isl_local_space_offset(aff->ls, type);
1135 aff->v = isl_vec_insert_zero_els(aff->v, first, n);
1136 if (!aff->v)
1137 return isl_aff_free(aff);
1138
1139 return aff;
1140 }
1141
1142 __isl_give isl_aff *isl_aff_add_dims(__isl_take isl_aff *aff,
1143 enum isl_dim_type type, unsigned n)
1144 {
1145 unsigned pos;
1146
1147 pos = isl_aff_dim(aff, type);
1148
1149 return isl_aff_insert_dims(aff, type, pos, n);
1150 }
1151
1152 __isl_give isl_pw_aff *isl_pw_aff_add_dims(__isl_take isl_pw_aff *pwaff,
1153 enum isl_dim_type type, unsigned n)
1154 {
1155 unsigned pos;
1156
1157 pos = isl_pw_aff_dim(pwaff, type);
1158
1159 return isl_pw_aff_insert_dims(pwaff, type, pos, n);
1160 }
1161
1162 __isl_give isl_pw_aff *isl_pw_aff_set_tuple_id(__isl_take isl_pw_aff *pwaff,
1163 __isl_take isl_id *id)
1164 {
1165 isl_space *dim;
1166
1167 dim = isl_pw_aff_get_space(pwaff);
1168 dim = isl_space_set_tuple_id(dim, isl_dim_in, id);
1169
1170 return isl_pw_aff_reset_space(pwaff, dim);
1171 }
1172
1173 __isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff)
1174 {
1175 isl_set *dom = isl_set_universe(isl_aff_get_domain_space(aff));
1176 return isl_pw_aff_alloc(dom, aff);
1177 }
1178
1179 #undef PW
1180 #define PW isl_pw_aff
1181 #undef EL
1182 #define EL isl_aff
1183 #undef EL_IS_ZERO
1184 #define EL_IS_ZERO is_empty
1185 #undef ZERO
1186 #define ZERO empty
1187 #undef IS_ZERO
1188 #define IS_ZERO is_empty
1189 #undef FIELD
1190 #define FIELD aff
1191
1192 #define NO_EVAL
1193 #define NO_OPT
1194 #define NO_MOVE_DIMS
1195 #define NO_LIFT
1196 #define NO_MORPH
1197
1198 #include <isl_pw_templ.c>
1199
1200 static __isl_give isl_set *align_params_pw_pw_set_and(
1201 __isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2,
1202 __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1203 __isl_take isl_pw_aff *pwaff2))
1204 {
1205 if (!pwaff1 || !pwaff2)
1206 goto error;
1207 if (isl_space_match(pwaff1->dim, isl_dim_param,
1208 pwaff2->dim, isl_dim_param))
1209 return fn(pwaff1, pwaff2);
1210 if (!isl_space_has_named_params(pwaff1->dim) ||
1211 !isl_space_has_named_params(pwaff2->dim))
1212 isl_die(isl_pw_aff_get_ctx(pwaff1), isl_error_invalid,
1213 "unaligned unnamed parameters", goto error);
1214 pwaff1 = isl_pw_aff_align_params(pwaff1, isl_pw_aff_get_space(pwaff2));
1215 pwaff2 = isl_pw_aff_align_params(pwaff2, isl_pw_aff_get_space(pwaff1));
1216 return fn(pwaff1, pwaff2);
1217 error:
1218 isl_pw_aff_free(pwaff1);
1219 isl_pw_aff_free(pwaff2);
1220 return NULL;
1221 }
1222
1223 /* Compute a piecewise quasi-affine expression with a domain that
1224 * is the union of those of pwaff1 and pwaff2 and such that on each
1225 * cell, the quasi-affine expression is the better (according to cmp)
1226 * of those of pwaff1 and pwaff2. If only one of pwaff1 or pwaff2
1227 * is defined on a given cell, then the associated expression
1228 * is the defined one.
1229 */
1230 static __isl_give isl_pw_aff *pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1231 __isl_take isl_pw_aff *pwaff2,
1232 __isl_give isl_basic_set *(*cmp)(__isl_take isl_aff *aff1,
1233 __isl_take isl_aff *aff2))
1234 {
1235 int i, j, n;
1236 isl_pw_aff *res;
1237 isl_ctx *ctx;
1238 isl_set *set;
1239
1240 if (!pwaff1 || !pwaff2)
1241 goto error;
1242
1243 ctx = isl_space_get_ctx(pwaff1->dim);
1244 if (!isl_space_is_equal(pwaff1->dim, pwaff2->dim))
1245 isl_die(ctx, isl_error_invalid,
1246 "arguments should live in same space", goto error);
1247
1248 if (isl_pw_aff_is_empty(pwaff1)) {
1249 isl_pw_aff_free(pwaff1);
1250 return pwaff2;
1251 }
1252
1253 if (isl_pw_aff_is_empty(pwaff2)) {
1254 isl_pw_aff_free(pwaff2);
1255 return pwaff1;
1256 }
1257
1258 n = 2 * (pwaff1->n + 1) * (pwaff2->n + 1);
1259 res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1260
1261 for (i = 0; i < pwaff1->n; ++i) {
1262 set = isl_set_copy(pwaff1->p[i].set);
1263 for (j = 0; j < pwaff2->n; ++j) {
1264 struct isl_set *common;
1265 isl_set *better;
1266
1267 common = isl_set_intersect(
1268 isl_set_copy(pwaff1->p[i].set),
1269 isl_set_copy(pwaff2->p[j].set));
1270 better = isl_set_from_basic_set(cmp(
1271 isl_aff_copy(pwaff2->p[j].aff),
1272 isl_aff_copy(pwaff1->p[i].aff)));
1273 better = isl_set_intersect(common, better);
1274 if (isl_set_plain_is_empty(better)) {
1275 isl_set_free(better);
1276 continue;
1277 }
1278 set = isl_set_subtract(set, isl_set_copy(better));
1279
1280 res = isl_pw_aff_add_piece(res, better,
1281 isl_aff_copy(pwaff2->p[j].aff));
1282 }
1283 res = isl_pw_aff_add_piece(res, set,
1284 isl_aff_copy(pwaff1->p[i].aff));
1285 }
1286
1287 for (j = 0; j < pwaff2->n; ++j) {
1288 set = isl_set_copy(pwaff2->p[j].set);
1289 for (i = 0; i < pwaff1->n; ++i)
1290 set = isl_set_subtract(set,
1291 isl_set_copy(pwaff1->p[i].set));
1292 res = isl_pw_aff_add_piece(res, set,
1293 isl_aff_copy(pwaff2->p[j].aff));
1294 }
1295
1296 isl_pw_aff_free(pwaff1);
1297 isl_pw_aff_free(pwaff2);
1298
1299 return res;
1300 error:
1301 isl_pw_aff_free(pwaff1);
1302 isl_pw_aff_free(pwaff2);
1303 return NULL;
1304 }
1305
1306 /* Compute a piecewise quasi-affine expression with a domain that
1307 * is the union of those of pwaff1 and pwaff2 and such that on each
1308 * cell, the quasi-affine expression is the maximum of those of pwaff1
1309 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1310 * cell, then the associated expression is the defined one.
1311 */
1312 static __isl_give isl_pw_aff *pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1313 __isl_take isl_pw_aff *pwaff2)
1314 {
1315 return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_ge_basic_set);
1316 }
1317
1318 __isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1319 __isl_take isl_pw_aff *pwaff2)
1320 {
1321 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_union_max);
1322 }
1323
1324 /* Compute a piecewise quasi-affine expression with a domain that
1325 * is the union of those of pwaff1 and pwaff2 and such that on each
1326 * cell, the quasi-affine expression is the minimum of those of pwaff1
1327 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1328 * cell, then the associated expression is the defined one.
1329 */
1330 static __isl_give isl_pw_aff *pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1331 __isl_take isl_pw_aff *pwaff2)
1332 {
1333 return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_le_basic_set);
1334 }
1335
1336 __isl_give isl_pw_aff *isl_pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1337 __isl_take isl_pw_aff *pwaff2)
1338 {
1339 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_union_min);
1340 }
1341
1342 __isl_give isl_pw_aff *isl_pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1343 __isl_take isl_pw_aff *pwaff2, int max)
1344 {
1345 if (max)
1346 return isl_pw_aff_union_max(pwaff1, pwaff2);
1347 else
1348 return isl_pw_aff_union_min(pwaff1, pwaff2);
1349 }
1350
1351 /* Construct a map with as domain the domain of pwaff and
1352 * one-dimensional range corresponding to the affine expressions.
1353 */
1354 static __isl_give isl_map *map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1355 {
1356 int i;
1357 isl_space *dim;
1358 isl_map *map;
1359
1360 if (!pwaff)
1361 return NULL;
1362
1363 dim = isl_pw_aff_get_space(pwaff);
1364 map = isl_map_empty(dim);
1365
1366 for (i = 0; i < pwaff->n; ++i) {
1367 isl_basic_map *bmap;
1368 isl_map *map_i;
1369
1370 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
1371 map_i = isl_map_from_basic_map(bmap);
1372 map_i = isl_map_intersect_domain(map_i,
1373 isl_set_copy(pwaff->p[i].set));
1374 map = isl_map_union_disjoint(map, map_i);
1375 }
1376
1377 isl_pw_aff_free(pwaff);
1378
1379 return map;
1380 }
1381
1382 /* Construct a map with as domain the domain of pwaff and
1383 * one-dimensional range corresponding to the affine expressions.
1384 */
1385 __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1386 {
1387 if (isl_space_is_set(pwaff->dim))
1388 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1389 "space of input is not a map",
1390 return isl_pw_aff_free(pwaff));
1391 return map_from_pw_aff(pwaff);
1392 }
1393
1394 /* Construct a one-dimensional set with as parameter domain
1395 * the domain of pwaff and the single set dimension
1396 * corresponding to the affine expressions.
1397 */
1398 __isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1399 {
1400 if (!isl_space_is_set(pwaff->dim))
1401 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1402 "space of input is not a set",
1403 return isl_pw_aff_free(pwaff));
1404 return map_from_pw_aff(pwaff);
1405 }
1406
1407 /* Return a set containing those elements in the domain
1408 * of pwaff where it is non-negative.
1409 */
1410 __isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
1411 {
1412 int i;
1413 isl_set *set;
1414
1415 if (!pwaff)
1416 return NULL;
1417
1418 set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1419
1420 for (i = 0; i < pwaff->n; ++i) {
1421 isl_basic_set *bset;
1422 isl_set *set_i;
1423
1424 bset = isl_aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff));
1425 set_i = isl_set_from_basic_set(bset);
1426 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1427 set = isl_set_union_disjoint(set, set_i);
1428 }
1429
1430 isl_pw_aff_free(pwaff);
1431
1432 return set;
1433 }
1434
1435 /* Return a set containing those elements in the domain
1436 * of pwaff where it is zero.
1437 */
1438 __isl_give isl_set *isl_pw_aff_zero_set(__isl_take isl_pw_aff *pwaff)
1439 {
1440 int i;
1441 isl_set *set;
1442
1443 if (!pwaff)
1444 return NULL;
1445
1446 set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1447
1448 for (i = 0; i < pwaff->n; ++i) {
1449 isl_basic_set *bset;
1450 isl_set *set_i;
1451
1452 bset = isl_aff_zero_basic_set(isl_aff_copy(pwaff->p[i].aff));
1453 set_i = isl_set_from_basic_set(bset);
1454 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1455 set = isl_set_union_disjoint(set, set_i);
1456 }
1457
1458 isl_pw_aff_free(pwaff);
1459
1460 return set;
1461 }
1462
1463 /* Return a set containing those elements in the domain
1464 * of pwaff where it is not zero.
1465 */
1466 __isl_give isl_set *isl_pw_aff_non_zero_set(__isl_take isl_pw_aff *pwaff)
1467 {
1468 return isl_set_complement(isl_pw_aff_zero_set(pwaff));
1469 }
1470
1471 /* Return a set containing those elements in the shared domain
1472 * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
1473 *
1474 * We compute the difference on the shared domain and then construct
1475 * the set of values where this difference is non-negative.
1476 * If strict is set, we first subtract 1 from the difference.
1477 * If equal is set, we only return the elements where pwaff1 and pwaff2
1478 * are equal.
1479 */
1480 static __isl_give isl_set *pw_aff_gte_set(__isl_take isl_pw_aff *pwaff1,
1481 __isl_take isl_pw_aff *pwaff2, int strict, int equal)
1482 {
1483 isl_set *set1, *set2;
1484
1485 set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1));
1486 set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2));
1487 set1 = isl_set_intersect(set1, set2);
1488 pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1));
1489 pwaff2 = isl_pw_aff_intersect_domain(pwaff2, isl_set_copy(set1));
1490 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2));
1491
1492 if (strict) {
1493 isl_space *dim = isl_set_get_space(set1);
1494 isl_aff *aff;
1495 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
1496 aff = isl_aff_add_constant_si(aff, -1);
1497 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_alloc(set1, aff));
1498 } else
1499 isl_set_free(set1);
1500
1501 if (equal)
1502 return isl_pw_aff_zero_set(pwaff1);
1503 return isl_pw_aff_nonneg_set(pwaff1);
1504 }
1505
1506 /* Return a set containing those elements in the shared domain
1507 * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
1508 */
1509 static __isl_give isl_set *pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1510 __isl_take isl_pw_aff *pwaff2)
1511 {
1512 return pw_aff_gte_set(pwaff1, pwaff2, 0, 1);
1513 }
1514
1515 __isl_give isl_set *isl_pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1516 __isl_take isl_pw_aff *pwaff2)
1517 {
1518 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_eq_set);
1519 }
1520
1521 /* Return a set containing those elements in the shared domain
1522 * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
1523 */
1524 static __isl_give isl_set *pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1525 __isl_take isl_pw_aff *pwaff2)
1526 {
1527 return pw_aff_gte_set(pwaff1, pwaff2, 0, 0);
1528 }
1529
1530 __isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1531 __isl_take isl_pw_aff *pwaff2)
1532 {
1533 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ge_set);
1534 }
1535
1536 /* Return a set containing those elements in the shared domain
1537 * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
1538 */
1539 static __isl_give isl_set *pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1540 __isl_take isl_pw_aff *pwaff2)
1541 {
1542 return pw_aff_gte_set(pwaff1, pwaff2, 1, 0);
1543 }
1544
1545 __isl_give isl_set *isl_pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1546 __isl_take isl_pw_aff *pwaff2)
1547 {
1548 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_gt_set);
1549 }
1550
1551 __isl_give isl_set *isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1,
1552 __isl_take isl_pw_aff *pwaff2)
1553 {
1554 return isl_pw_aff_ge_set(pwaff2, pwaff1);
1555 }
1556
1557 __isl_give isl_set *isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1,
1558 __isl_take isl_pw_aff *pwaff2)
1559 {
1560 return isl_pw_aff_gt_set(pwaff2, pwaff1);
1561 }
1562
1563 /* Return a set containing those elements in the shared domain
1564 * of the elements of list1 and list2 where each element in list1
1565 * has the relation specified by "fn" with each element in list2.
1566 */
1567 static __isl_give isl_set *pw_aff_list_set(__isl_take isl_pw_aff_list *list1,
1568 __isl_take isl_pw_aff_list *list2,
1569 __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1570 __isl_take isl_pw_aff *pwaff2))
1571 {
1572 int i, j;
1573 isl_ctx *ctx;
1574 isl_set *set;
1575
1576 if (!list1 || !list2)
1577 goto error;
1578
1579 ctx = isl_pw_aff_list_get_ctx(list1);
1580 if (list1->n < 1 || list2->n < 1)
1581 isl_die(ctx, isl_error_invalid,
1582 "list should contain at least one element", goto error);
1583
1584 set = isl_set_universe(isl_pw_aff_get_domain_space(list1->p[0]));
1585 for (i = 0; i < list1->n; ++i)
1586 for (j = 0; j < list2->n; ++j) {
1587 isl_set *set_ij;
1588
1589 set_ij = fn(isl_pw_aff_copy(list1->p[i]),
1590 isl_pw_aff_copy(list2->p[j]));
1591 set = isl_set_intersect(set, set_ij);
1592 }
1593
1594 isl_pw_aff_list_free(list1);
1595 isl_pw_aff_list_free(list2);
1596 return set;
1597 error:
1598 isl_pw_aff_list_free(list1);
1599 isl_pw_aff_list_free(list2);
1600 return NULL;
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 * is equal to each element in list2.
1606 */
1607 __isl_give isl_set *isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list *list1,
1608 __isl_take isl_pw_aff_list *list2)
1609 {
1610 return pw_aff_list_set(list1, list2, &isl_pw_aff_eq_set);
1611 }
1612
1613 __isl_give isl_set *isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list *list1,
1614 __isl_take isl_pw_aff_list *list2)
1615 {
1616 return pw_aff_list_set(list1, list2, &isl_pw_aff_ne_set);
1617 }
1618
1619 /* Return a set containing those elements in the shared domain
1620 * of the elements of list1 and list2 where each element in list1
1621 * is less than or equal to each element in list2.
1622 */
1623 __isl_give isl_set *isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list *list1,
1624 __isl_take isl_pw_aff_list *list2)
1625 {
1626 return pw_aff_list_set(list1, list2, &isl_pw_aff_le_set);
1627 }
1628
1629 __isl_give isl_set *isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list *list1,
1630 __isl_take isl_pw_aff_list *list2)
1631 {
1632 return pw_aff_list_set(list1, list2, &isl_pw_aff_lt_set);
1633 }
1634
1635 __isl_give isl_set *isl_pw_aff_list_ge_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_ge_set);
1639 }
1640
1641 __isl_give isl_set *isl_pw_aff_list_gt_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_gt_set);
1645 }
1646
1647
1648 /* Return a set containing those elements in the shared domain
1649 * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
1650 */
1651 static __isl_give isl_set *pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1652 __isl_take isl_pw_aff *pwaff2)
1653 {
1654 isl_set *set_lt, *set_gt;
1655
1656 set_lt = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1),
1657 isl_pw_aff_copy(pwaff2));
1658 set_gt = isl_pw_aff_gt_set(pwaff1, pwaff2);
1659 return isl_set_union_disjoint(set_lt, set_gt);
1660 }
1661
1662 __isl_give isl_set *isl_pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1663 __isl_take isl_pw_aff *pwaff2)
1664 {
1665 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ne_set);
1666 }
1667
1668 __isl_give isl_pw_aff *isl_pw_aff_scale_down(__isl_take isl_pw_aff *pwaff,
1669 isl_int v)
1670 {
1671 int i;
1672
1673 if (isl_int_is_one(v))
1674 return pwaff;
1675 if (!isl_int_is_pos(v))
1676 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1677 "factor needs to be positive",
1678 return isl_pw_aff_free(pwaff));
1679 pwaff = isl_pw_aff_cow(pwaff);
1680 if (!pwaff)
1681 return NULL;
1682 if (pwaff->n == 0)
1683 return pwaff;
1684
1685 for (i = 0; i < pwaff->n; ++i) {
1686 pwaff->p[i].aff = isl_aff_scale_down(pwaff->p[i].aff, v);
1687 if (!pwaff->p[i].aff)
1688 return isl_pw_aff_free(pwaff);
1689 }
1690
1691 return pwaff;
1692 }
1693
1694 __isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff)
1695 {
1696 int i;
1697
1698 pwaff = isl_pw_aff_cow(pwaff);
1699 if (!pwaff)
1700 return NULL;
1701 if (pwaff->n == 0)
1702 return pwaff;
1703
1704 for (i = 0; i < pwaff->n; ++i) {
1705 pwaff->p[i].aff = isl_aff_floor(pwaff->p[i].aff);
1706 if (!pwaff->p[i].aff)
1707 return isl_pw_aff_free(pwaff);
1708 }
1709
1710 return pwaff;
1711 }
1712
1713 __isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff)
1714 {
1715 int i;
1716
1717 pwaff = isl_pw_aff_cow(pwaff);
1718 if (!pwaff)
1719 return NULL;
1720 if (pwaff->n == 0)
1721 return pwaff;
1722
1723 for (i = 0; i < pwaff->n; ++i) {
1724 pwaff->p[i].aff = isl_aff_ceil(pwaff->p[i].aff);
1725 if (!pwaff->p[i].aff)
1726 return isl_pw_aff_free(pwaff);
1727 }
1728
1729 return pwaff;
1730 }
1731
1732 /* Return an affine expression that is equal to pwaff_true for elements
1733 * in "cond" and to pwaff_false for elements not in "cond".
1734 * That is, return cond ? pwaff_true : pwaff_false;
1735 */
1736 __isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_set *cond,
1737 __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false)
1738 {
1739 isl_set *comp;
1740
1741 comp = isl_set_complement(isl_set_copy(cond));
1742 pwaff_true = isl_pw_aff_intersect_domain(pwaff_true, cond);
1743 pwaff_false = isl_pw_aff_intersect_domain(pwaff_false, comp);
1744
1745 return isl_pw_aff_add_disjoint(pwaff_true, pwaff_false);
1746 }
1747
1748 int isl_aff_is_cst(__isl_keep isl_aff *aff)
1749 {
1750 if (!aff)
1751 return -1;
1752
1753 return isl_seq_first_non_zero(aff->v->el + 2, aff->v->size - 2) == -1;
1754 }
1755
1756 /* Check whether pwaff is a piecewise constant.
1757 */
1758 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff)
1759 {
1760 int i;
1761
1762 if (!pwaff)
1763 return -1;
1764
1765 for (i = 0; i < pwaff->n; ++i) {
1766 int is_cst = isl_aff_is_cst(pwaff->p[i].aff);
1767 if (is_cst < 0 || !is_cst)
1768 return is_cst;
1769 }
1770
1771 return 1;
1772 }
1773
1774 __isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
1775 __isl_take isl_aff *aff2)
1776 {
1777 if (!isl_aff_is_cst(aff2) && isl_aff_is_cst(aff1))
1778 return isl_aff_mul(aff2, aff1);
1779
1780 if (!isl_aff_is_cst(aff2))
1781 isl_die(isl_aff_get_ctx(aff1), isl_error_invalid,
1782 "at least one affine expression should be constant",
1783 goto error);
1784
1785 aff1 = isl_aff_cow(aff1);
1786 if (!aff1 || !aff2)
1787 goto error;
1788
1789 aff1 = isl_aff_scale(aff1, aff2->v->el[1]);
1790 aff1 = isl_aff_scale_down(aff1, aff2->v->el[0]);
1791
1792 isl_aff_free(aff2);
1793 return aff1;
1794 error:
1795 isl_aff_free(aff1);
1796 isl_aff_free(aff2);
1797 return NULL;
1798 }
1799
1800 static __isl_give isl_pw_aff *pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1801 __isl_take isl_pw_aff *pwaff2)
1802 {
1803 int i, j, n;
1804 isl_pw_aff *res;
1805
1806 if (!pwaff1 || !pwaff2)
1807 goto error;
1808
1809 n = pwaff1->n * pwaff2->n;
1810 res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1811
1812 for (i = 0; i < pwaff1->n; ++i) {
1813 for (j = 0; j < pwaff2->n; ++j) {
1814 isl_set *common;
1815 isl_aff *prod;
1816 common = isl_set_intersect(
1817 isl_set_copy(pwaff1->p[i].set),
1818 isl_set_copy(pwaff2->p[j].set));
1819 if (isl_set_plain_is_empty(common)) {
1820 isl_set_free(common);
1821 continue;
1822 }
1823
1824 prod = isl_aff_mul(isl_aff_copy(pwaff1->p[i].aff),
1825 isl_aff_copy(pwaff2->p[j].aff));
1826
1827 res = isl_pw_aff_add_piece(res, common, prod);
1828 }
1829 }
1830
1831 isl_pw_aff_free(pwaff1);
1832 isl_pw_aff_free(pwaff2);
1833 return res;
1834 error:
1835 isl_pw_aff_free(pwaff1);
1836 isl_pw_aff_free(pwaff2);
1837 return NULL;
1838 }
1839
1840 __isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1841 __isl_take isl_pw_aff *pwaff2)
1842 {
1843 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul);
1844 }
1845
1846 static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1847 __isl_take isl_pw_aff *pwaff2)
1848 {
1849 isl_set *le;
1850
1851 le = isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1),
1852 isl_pw_aff_copy(pwaff2));
1853 return isl_pw_aff_cond(le, pwaff1, pwaff2);
1854 }
1855
1856 __isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1857 __isl_take isl_pw_aff *pwaff2)
1858 {
1859 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_min);
1860 }
1861
1862 static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1863 __isl_take isl_pw_aff *pwaff2)
1864 {
1865 isl_set *le;
1866
1867 le = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1),
1868 isl_pw_aff_copy(pwaff2));
1869 return isl_pw_aff_cond(le, pwaff1, pwaff2);
1870 }
1871
1872 __isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1873 __isl_take isl_pw_aff *pwaff2)
1874 {
1875 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_max);
1876 }
1877
1878 static __isl_give isl_pw_aff *pw_aff_list_reduce(
1879 __isl_take isl_pw_aff_list *list,
1880 __isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pwaff1,
1881 __isl_take isl_pw_aff *pwaff2))
1882 {
1883 int i;
1884 isl_ctx *ctx;
1885 isl_pw_aff *res;
1886
1887 if (!list)
1888 return NULL;
1889
1890 ctx = isl_pw_aff_list_get_ctx(list);
1891 if (list->n < 1)
1892 isl_die(ctx, isl_error_invalid,
1893 "list should contain at least one element",
1894 return isl_pw_aff_list_free(list));
1895
1896 res = isl_pw_aff_copy(list->p[0]);
1897 for (i = 1; i < list->n; ++i)
1898 res = fn(res, isl_pw_aff_copy(list->p[i]));
1899
1900 isl_pw_aff_list_free(list);
1901 return res;
1902 }
1903
1904 /* Return an isl_pw_aff that maps each element in the intersection of the
1905 * domains of the elements of list to the minimal corresponding affine
1906 * expression.
1907 */
1908 __isl_give isl_pw_aff *isl_pw_aff_list_min(__isl_take isl_pw_aff_list *list)
1909 {
1910 return pw_aff_list_reduce(list, &isl_pw_aff_min);
1911 }
1912
1913 /* Return an isl_pw_aff that maps each element in the intersection of the
1914 * domains of the elements of list to the maximal corresponding affine
1915 * expression.
1916 */
1917 __isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list)
1918 {
1919 return pw_aff_list_reduce(list, &isl_pw_aff_max);
1920 }
Integer set library