?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
add isl_local_space_set_dim_id
[isl.git] / isl_aff.c
blob1c4f03f1eec847a46179f688f9cd47efad910870
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_from_aff(__isl_take isl_aff *aff)
1163 {
1164 isl_set *dom = isl_set_universe(isl_aff_get_domain_space(aff));
1165 return isl_pw_aff_alloc(dom, aff);
1166 }
1167
1168 #undef PW
1169 #define PW isl_pw_aff
1170 #undef EL
1171 #define EL isl_aff
1172 #undef EL_IS_ZERO
1173 #define EL_IS_ZERO is_empty
1174 #undef ZERO
1175 #define ZERO empty
1176 #undef IS_ZERO
1177 #define IS_ZERO is_empty
1178 #undef FIELD
1179 #define FIELD aff
1180
1181 #define NO_EVAL
1182 #define NO_OPT
1183 #define NO_MOVE_DIMS
1184 #define NO_LIFT
1185 #define NO_MORPH
1186
1187 #include <isl_pw_templ.c>
1188
1189 static __isl_give isl_set *align_params_pw_pw_set_and(
1190 __isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2,
1191 __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1192 __isl_take isl_pw_aff *pwaff2))
1193 {
1194 if (!pwaff1 || !pwaff2)
1195 goto error;
1196 if (isl_space_match(pwaff1->dim, isl_dim_param,
1197 pwaff2->dim, isl_dim_param))
1198 return fn(pwaff1, pwaff2);
1199 if (!isl_space_has_named_params(pwaff1->dim) ||
1200 !isl_space_has_named_params(pwaff2->dim))
1201 isl_die(isl_pw_aff_get_ctx(pwaff1), isl_error_invalid,
1202 "unaligned unnamed parameters", goto error);
1203 pwaff1 = isl_pw_aff_align_params(pwaff1, isl_pw_aff_get_space(pwaff2));
1204 pwaff2 = isl_pw_aff_align_params(pwaff2, isl_pw_aff_get_space(pwaff1));
1205 return fn(pwaff1, pwaff2);
1206 error:
1207 isl_pw_aff_free(pwaff1);
1208 isl_pw_aff_free(pwaff2);
1209 return NULL;
1210 }
1211
1212 /* Compute a piecewise quasi-affine expression with a domain that
1213 * is the union of those of pwaff1 and pwaff2 and such that on each
1214 * cell, the quasi-affine expression is the better (according to cmp)
1215 * of those of pwaff1 and pwaff2. If only one of pwaff1 or pwaff2
1216 * is defined on a given cell, then the associated expression
1217 * is the defined one.
1218 */
1219 static __isl_give isl_pw_aff *pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1220 __isl_take isl_pw_aff *pwaff2,
1221 __isl_give isl_basic_set *(*cmp)(__isl_take isl_aff *aff1,
1222 __isl_take isl_aff *aff2))
1223 {
1224 int i, j, n;
1225 isl_pw_aff *res;
1226 isl_ctx *ctx;
1227 isl_set *set;
1228
1229 if (!pwaff1 || !pwaff2)
1230 goto error;
1231
1232 ctx = isl_space_get_ctx(pwaff1->dim);
1233 if (!isl_space_is_equal(pwaff1->dim, pwaff2->dim))
1234 isl_die(ctx, isl_error_invalid,
1235 "arguments should live in same space", goto error);
1236
1237 if (isl_pw_aff_is_empty(pwaff1)) {
1238 isl_pw_aff_free(pwaff1);
1239 return pwaff2;
1240 }
1241
1242 if (isl_pw_aff_is_empty(pwaff2)) {
1243 isl_pw_aff_free(pwaff2);
1244 return pwaff1;
1245 }
1246
1247 n = 2 * (pwaff1->n + 1) * (pwaff2->n + 1);
1248 res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1249
1250 for (i = 0; i < pwaff1->n; ++i) {
1251 set = isl_set_copy(pwaff1->p[i].set);
1252 for (j = 0; j < pwaff2->n; ++j) {
1253 struct isl_set *common;
1254 isl_set *better;
1255
1256 common = isl_set_intersect(
1257 isl_set_copy(pwaff1->p[i].set),
1258 isl_set_copy(pwaff2->p[j].set));
1259 better = isl_set_from_basic_set(cmp(
1260 isl_aff_copy(pwaff2->p[j].aff),
1261 isl_aff_copy(pwaff1->p[i].aff)));
1262 better = isl_set_intersect(common, better);
1263 if (isl_set_plain_is_empty(better)) {
1264 isl_set_free(better);
1265 continue;
1266 }
1267 set = isl_set_subtract(set, isl_set_copy(better));
1268
1269 res = isl_pw_aff_add_piece(res, better,
1270 isl_aff_copy(pwaff2->p[j].aff));
1271 }
1272 res = isl_pw_aff_add_piece(res, set,
1273 isl_aff_copy(pwaff1->p[i].aff));
1274 }
1275
1276 for (j = 0; j < pwaff2->n; ++j) {
1277 set = isl_set_copy(pwaff2->p[j].set);
1278 for (i = 0; i < pwaff1->n; ++i)
1279 set = isl_set_subtract(set,
1280 isl_set_copy(pwaff1->p[i].set));
1281 res = isl_pw_aff_add_piece(res, set,
1282 isl_aff_copy(pwaff2->p[j].aff));
1283 }
1284
1285 isl_pw_aff_free(pwaff1);
1286 isl_pw_aff_free(pwaff2);
1287
1288 return res;
1289 error:
1290 isl_pw_aff_free(pwaff1);
1291 isl_pw_aff_free(pwaff2);
1292 return NULL;
1293 }
1294
1295 /* Compute a piecewise quasi-affine expression with a domain that
1296 * is the union of those of pwaff1 and pwaff2 and such that on each
1297 * cell, the quasi-affine expression is the maximum of those of pwaff1
1298 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1299 * cell, then the associated expression is the defined one.
1300 */
1301 static __isl_give isl_pw_aff *pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1302 __isl_take isl_pw_aff *pwaff2)
1303 {
1304 return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_ge_basic_set);
1305 }
1306
1307 __isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1308 __isl_take isl_pw_aff *pwaff2)
1309 {
1310 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_union_max);
1311 }
1312
1313 /* Compute a piecewise quasi-affine expression with a domain that
1314 * is the union of those of pwaff1 and pwaff2 and such that on each
1315 * cell, the quasi-affine expression is the minimum of those of pwaff1
1316 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1317 * cell, then the associated expression is the defined one.
1318 */
1319 static __isl_give isl_pw_aff *pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1320 __isl_take isl_pw_aff *pwaff2)
1321 {
1322 return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_le_basic_set);
1323 }
1324
1325 __isl_give isl_pw_aff *isl_pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
1326 __isl_take isl_pw_aff *pwaff2)
1327 {
1328 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_union_min);
1329 }
1330
1331 __isl_give isl_pw_aff *isl_pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
1332 __isl_take isl_pw_aff *pwaff2, int max)
1333 {
1334 if (max)
1335 return isl_pw_aff_union_max(pwaff1, pwaff2);
1336 else
1337 return isl_pw_aff_union_min(pwaff1, pwaff2);
1338 }
1339
1340 /* Construct a map with as domain the domain of pwaff and
1341 * one-dimensional range corresponding to the affine expressions.
1342 */
1343 static __isl_give isl_map *map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1344 {
1345 int i;
1346 isl_space *dim;
1347 isl_map *map;
1348
1349 if (!pwaff)
1350 return NULL;
1351
1352 dim = isl_pw_aff_get_space(pwaff);
1353 map = isl_map_empty(dim);
1354
1355 for (i = 0; i < pwaff->n; ++i) {
1356 isl_basic_map *bmap;
1357 isl_map *map_i;
1358
1359 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
1360 map_i = isl_map_from_basic_map(bmap);
1361 map_i = isl_map_intersect_domain(map_i,
1362 isl_set_copy(pwaff->p[i].set));
1363 map = isl_map_union_disjoint(map, map_i);
1364 }
1365
1366 isl_pw_aff_free(pwaff);
1367
1368 return map;
1369 }
1370
1371 /* Construct a map with as domain the domain of pwaff and
1372 * one-dimensional range corresponding to the affine expressions.
1373 */
1374 __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1375 {
1376 if (isl_space_is_set(pwaff->dim))
1377 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1378 "space of input is not a map",
1379 return isl_pw_aff_free(pwaff));
1380 return map_from_pw_aff(pwaff);
1381 }
1382
1383 /* Construct a one-dimensional set with as parameter domain
1384 * the domain of pwaff and the single set dimension
1385 * corresponding to the affine expressions.
1386 */
1387 __isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1388 {
1389 if (!isl_space_is_set(pwaff->dim))
1390 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1391 "space of input is not a set",
1392 return isl_pw_aff_free(pwaff));
1393 return map_from_pw_aff(pwaff);
1394 }
1395
1396 /* Return a set containing those elements in the domain
1397 * of pwaff where it is non-negative.
1398 */
1399 __isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
1400 {
1401 int i;
1402 isl_set *set;
1403
1404 if (!pwaff)
1405 return NULL;
1406
1407 set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1408
1409 for (i = 0; i < pwaff->n; ++i) {
1410 isl_basic_set *bset;
1411 isl_set *set_i;
1412
1413 bset = isl_aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff));
1414 set_i = isl_set_from_basic_set(bset);
1415 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1416 set = isl_set_union_disjoint(set, set_i);
1417 }
1418
1419 isl_pw_aff_free(pwaff);
1420
1421 return set;
1422 }
1423
1424 /* Return a set containing those elements in the domain
1425 * of pwaff where it is zero.
1426 */
1427 __isl_give isl_set *isl_pw_aff_zero_set(__isl_take isl_pw_aff *pwaff)
1428 {
1429 int i;
1430 isl_set *set;
1431
1432 if (!pwaff)
1433 return NULL;
1434
1435 set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
1436
1437 for (i = 0; i < pwaff->n; ++i) {
1438 isl_basic_set *bset;
1439 isl_set *set_i;
1440
1441 bset = isl_aff_zero_basic_set(isl_aff_copy(pwaff->p[i].aff));
1442 set_i = isl_set_from_basic_set(bset);
1443 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1444 set = isl_set_union_disjoint(set, set_i);
1445 }
1446
1447 isl_pw_aff_free(pwaff);
1448
1449 return set;
1450 }
1451
1452 /* Return a set containing those elements in the domain
1453 * of pwaff where it is not zero.
1454 */
1455 __isl_give isl_set *isl_pw_aff_non_zero_set(__isl_take isl_pw_aff *pwaff)
1456 {
1457 return isl_set_complement(isl_pw_aff_zero_set(pwaff));
1458 }
1459
1460 /* Return a set containing those elements in the shared domain
1461 * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
1462 *
1463 * We compute the difference on the shared domain and then construct
1464 * the set of values where this difference is non-negative.
1465 * If strict is set, we first subtract 1 from the difference.
1466 * If equal is set, we only return the elements where pwaff1 and pwaff2
1467 * are equal.
1468 */
1469 static __isl_give isl_set *pw_aff_gte_set(__isl_take isl_pw_aff *pwaff1,
1470 __isl_take isl_pw_aff *pwaff2, int strict, int equal)
1471 {
1472 isl_set *set1, *set2;
1473
1474 set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1));
1475 set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2));
1476 set1 = isl_set_intersect(set1, set2);
1477 pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1));
1478 pwaff2 = isl_pw_aff_intersect_domain(pwaff2, isl_set_copy(set1));
1479 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2));
1480
1481 if (strict) {
1482 isl_space *dim = isl_set_get_space(set1);
1483 isl_aff *aff;
1484 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
1485 aff = isl_aff_add_constant_si(aff, -1);
1486 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_alloc(set1, aff));
1487 } else
1488 isl_set_free(set1);
1489
1490 if (equal)
1491 return isl_pw_aff_zero_set(pwaff1);
1492 return isl_pw_aff_nonneg_set(pwaff1);
1493 }
1494
1495 /* Return a set containing those elements in the shared domain
1496 * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
1497 */
1498 static __isl_give isl_set *pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1499 __isl_take isl_pw_aff *pwaff2)
1500 {
1501 return pw_aff_gte_set(pwaff1, pwaff2, 0, 1);
1502 }
1503
1504 __isl_give isl_set *isl_pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1505 __isl_take isl_pw_aff *pwaff2)
1506 {
1507 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_eq_set);
1508 }
1509
1510 /* Return a set containing those elements in the shared domain
1511 * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
1512 */
1513 static __isl_give isl_set *pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1514 __isl_take isl_pw_aff *pwaff2)
1515 {
1516 return pw_aff_gte_set(pwaff1, pwaff2, 0, 0);
1517 }
1518
1519 __isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1520 __isl_take isl_pw_aff *pwaff2)
1521 {
1522 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ge_set);
1523 }
1524
1525 /* Return a set containing those elements in the shared domain
1526 * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
1527 */
1528 static __isl_give isl_set *pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1529 __isl_take isl_pw_aff *pwaff2)
1530 {
1531 return pw_aff_gte_set(pwaff1, pwaff2, 1, 0);
1532 }
1533
1534 __isl_give isl_set *isl_pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1535 __isl_take isl_pw_aff *pwaff2)
1536 {
1537 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_gt_set);
1538 }
1539
1540 __isl_give isl_set *isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1,
1541 __isl_take isl_pw_aff *pwaff2)
1542 {
1543 return isl_pw_aff_ge_set(pwaff2, pwaff1);
1544 }
1545
1546 __isl_give isl_set *isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1,
1547 __isl_take isl_pw_aff *pwaff2)
1548 {
1549 return isl_pw_aff_gt_set(pwaff2, pwaff1);
1550 }
1551
1552 /* Return a set containing those elements in the shared domain
1553 * of the elements of list1 and list2 where each element in list1
1554 * has the relation specified by "fn" with each element in list2.
1555 */
1556 static __isl_give isl_set *pw_aff_list_set(__isl_take isl_pw_aff_list *list1,
1557 __isl_take isl_pw_aff_list *list2,
1558 __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1559 __isl_take isl_pw_aff *pwaff2))
1560 {
1561 int i, j;
1562 isl_ctx *ctx;
1563 isl_set *set;
1564
1565 if (!list1 || !list2)
1566 goto error;
1567
1568 ctx = isl_pw_aff_list_get_ctx(list1);
1569 if (list1->n < 1 || list2->n < 1)
1570 isl_die(ctx, isl_error_invalid,
1571 "list should contain at least one element", goto error);
1572
1573 set = isl_set_universe(isl_pw_aff_get_domain_space(list1->p[0]));
1574 for (i = 0; i < list1->n; ++i)
1575 for (j = 0; j < list2->n; ++j) {
1576 isl_set *set_ij;
1577
1578 set_ij = fn(isl_pw_aff_copy(list1->p[i]),
1579 isl_pw_aff_copy(list2->p[j]));
1580 set = isl_set_intersect(set, set_ij);
1581 }
1582
1583 isl_pw_aff_list_free(list1);
1584 isl_pw_aff_list_free(list2);
1585 return set;
1586 error:
1587 isl_pw_aff_list_free(list1);
1588 isl_pw_aff_list_free(list2);
1589 return NULL;
1590 }
1591
1592 /* Return a set containing those elements in the shared domain
1593 * of the elements of list1 and list2 where each element in list1
1594 * is equal to each element in list2.
1595 */
1596 __isl_give isl_set *isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list *list1,
1597 __isl_take isl_pw_aff_list *list2)
1598 {
1599 return pw_aff_list_set(list1, list2, &isl_pw_aff_eq_set);
1600 }
1601
1602 __isl_give isl_set *isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list *list1,
1603 __isl_take isl_pw_aff_list *list2)
1604 {
1605 return pw_aff_list_set(list1, list2, &isl_pw_aff_ne_set);
1606 }
1607
1608 /* Return a set containing those elements in the shared domain
1609 * of the elements of list1 and list2 where each element in list1
1610 * is less than or equal to each element in list2.
1611 */
1612 __isl_give isl_set *isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list *list1,
1613 __isl_take isl_pw_aff_list *list2)
1614 {
1615 return pw_aff_list_set(list1, list2, &isl_pw_aff_le_set);
1616 }
1617
1618 __isl_give isl_set *isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list *list1,
1619 __isl_take isl_pw_aff_list *list2)
1620 {
1621 return pw_aff_list_set(list1, list2, &isl_pw_aff_lt_set);
1622 }
1623
1624 __isl_give isl_set *isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list *list1,
1625 __isl_take isl_pw_aff_list *list2)
1626 {
1627 return pw_aff_list_set(list1, list2, &isl_pw_aff_ge_set);
1628 }
1629
1630 __isl_give isl_set *isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list *list1,
1631 __isl_take isl_pw_aff_list *list2)
1632 {
1633 return pw_aff_list_set(list1, list2, &isl_pw_aff_gt_set);
1634 }
1635
1636
1637 /* Return a set containing those elements in the shared domain
1638 * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
1639 */
1640 static __isl_give isl_set *pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1641 __isl_take isl_pw_aff *pwaff2)
1642 {
1643 isl_set *set_lt, *set_gt;
1644
1645 set_lt = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1),
1646 isl_pw_aff_copy(pwaff2));
1647 set_gt = isl_pw_aff_gt_set(pwaff1, pwaff2);
1648 return isl_set_union_disjoint(set_lt, set_gt);
1649 }
1650
1651 __isl_give isl_set *isl_pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1652 __isl_take isl_pw_aff *pwaff2)
1653 {
1654 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ne_set);
1655 }
1656
1657 __isl_give isl_pw_aff *isl_pw_aff_scale_down(__isl_take isl_pw_aff *pwaff,
1658 isl_int v)
1659 {
1660 int i;
1661
1662 if (isl_int_is_one(v))
1663 return pwaff;
1664 if (!isl_int_is_pos(v))
1665 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1666 "factor needs to be positive",
1667 return isl_pw_aff_free(pwaff));
1668 pwaff = isl_pw_aff_cow(pwaff);
1669 if (!pwaff)
1670 return NULL;
1671 if (pwaff->n == 0)
1672 return pwaff;
1673
1674 for (i = 0; i < pwaff->n; ++i) {
1675 pwaff->p[i].aff = isl_aff_scale_down(pwaff->p[i].aff, v);
1676 if (!pwaff->p[i].aff)
1677 return isl_pw_aff_free(pwaff);
1678 }
1679
1680 return pwaff;
1681 }
1682
1683 __isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff)
1684 {
1685 int i;
1686
1687 pwaff = isl_pw_aff_cow(pwaff);
1688 if (!pwaff)
1689 return NULL;
1690 if (pwaff->n == 0)
1691 return pwaff;
1692
1693 for (i = 0; i < pwaff->n; ++i) {
1694 pwaff->p[i].aff = isl_aff_floor(pwaff->p[i].aff);
1695 if (!pwaff->p[i].aff)
1696 return isl_pw_aff_free(pwaff);
1697 }
1698
1699 return pwaff;
1700 }
1701
1702 __isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff)
1703 {
1704 int i;
1705
1706 pwaff = isl_pw_aff_cow(pwaff);
1707 if (!pwaff)
1708 return NULL;
1709 if (pwaff->n == 0)
1710 return pwaff;
1711
1712 for (i = 0; i < pwaff->n; ++i) {
1713 pwaff->p[i].aff = isl_aff_ceil(pwaff->p[i].aff);
1714 if (!pwaff->p[i].aff)
1715 return isl_pw_aff_free(pwaff);
1716 }
1717
1718 return pwaff;
1719 }
1720
1721 /* Return an affine expression that is equal to pwaff_true for elements
1722 * in "cond" and to pwaff_false for elements not in "cond".
1723 * That is, return cond ? pwaff_true : pwaff_false;
1724 */
1725 __isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_set *cond,
1726 __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false)
1727 {
1728 isl_set *comp;
1729
1730 comp = isl_set_complement(isl_set_copy(cond));
1731 pwaff_true = isl_pw_aff_intersect_domain(pwaff_true, cond);
1732 pwaff_false = isl_pw_aff_intersect_domain(pwaff_false, comp);
1733
1734 return isl_pw_aff_add_disjoint(pwaff_true, pwaff_false);
1735 }
1736
1737 int isl_aff_is_cst(__isl_keep isl_aff *aff)
1738 {
1739 if (!aff)
1740 return -1;
1741
1742 return isl_seq_first_non_zero(aff->v->el + 2, aff->v->size - 2) == -1;
1743 }
1744
1745 /* Check whether pwaff is a piecewise constant.
1746 */
1747 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff)
1748 {
1749 int i;
1750
1751 if (!pwaff)
1752 return -1;
1753
1754 for (i = 0; i < pwaff->n; ++i) {
1755 int is_cst = isl_aff_is_cst(pwaff->p[i].aff);
1756 if (is_cst < 0 || !is_cst)
1757 return is_cst;
1758 }
1759
1760 return 1;
1761 }
1762
1763 __isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
1764 __isl_take isl_aff *aff2)
1765 {
1766 if (!isl_aff_is_cst(aff2) && isl_aff_is_cst(aff1))
1767 return isl_aff_mul(aff2, aff1);
1768
1769 if (!isl_aff_is_cst(aff2))
1770 isl_die(isl_aff_get_ctx(aff1), isl_error_invalid,
1771 "at least one affine expression should be constant",
1772 goto error);
1773
1774 aff1 = isl_aff_cow(aff1);
1775 if (!aff1 || !aff2)
1776 goto error;
1777
1778 aff1 = isl_aff_scale(aff1, aff2->v->el[1]);
1779 aff1 = isl_aff_scale_down(aff1, aff2->v->el[0]);
1780
1781 isl_aff_free(aff2);
1782 return aff1;
1783 error:
1784 isl_aff_free(aff1);
1785 isl_aff_free(aff2);
1786 return NULL;
1787 }
1788
1789 static __isl_give isl_pw_aff *pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1790 __isl_take isl_pw_aff *pwaff2)
1791 {
1792 int i, j, n;
1793 isl_pw_aff *res;
1794
1795 if (!pwaff1 || !pwaff2)
1796 goto error;
1797
1798 n = pwaff1->n * pwaff2->n;
1799 res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
1800
1801 for (i = 0; i < pwaff1->n; ++i) {
1802 for (j = 0; j < pwaff2->n; ++j) {
1803 isl_set *common;
1804 isl_aff *prod;
1805 common = isl_set_intersect(
1806 isl_set_copy(pwaff1->p[i].set),
1807 isl_set_copy(pwaff2->p[j].set));
1808 if (isl_set_plain_is_empty(common)) {
1809 isl_set_free(common);
1810 continue;
1811 }
1812
1813 prod = isl_aff_mul(isl_aff_copy(pwaff1->p[i].aff),
1814 isl_aff_copy(pwaff2->p[j].aff));
1815
1816 res = isl_pw_aff_add_piece(res, common, prod);
1817 }
1818 }
1819
1820 isl_pw_aff_free(pwaff1);
1821 isl_pw_aff_free(pwaff2);
1822 return res;
1823 error:
1824 isl_pw_aff_free(pwaff1);
1825 isl_pw_aff_free(pwaff2);
1826 return NULL;
1827 }
1828
1829 __isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1830 __isl_take isl_pw_aff *pwaff2)
1831 {
1832 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul);
1833 }
1834
1835 static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1836 __isl_take isl_pw_aff *pwaff2)
1837 {
1838 isl_set *le;
1839
1840 le = isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1),
1841 isl_pw_aff_copy(pwaff2));
1842 return isl_pw_aff_cond(le, pwaff1, pwaff2);
1843 }
1844
1845 __isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1846 __isl_take isl_pw_aff *pwaff2)
1847 {
1848 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_min);
1849 }
1850
1851 static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1852 __isl_take isl_pw_aff *pwaff2)
1853 {
1854 isl_set *le;
1855
1856 le = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1),
1857 isl_pw_aff_copy(pwaff2));
1858 return isl_pw_aff_cond(le, pwaff1, pwaff2);
1859 }
1860
1861 __isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1862 __isl_take isl_pw_aff *pwaff2)
1863 {
1864 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_max);
1865 }
1866
1867 static __isl_give isl_pw_aff *pw_aff_list_reduce(
1868 __isl_take isl_pw_aff_list *list,
1869 __isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pwaff1,
1870 __isl_take isl_pw_aff *pwaff2))
1871 {
1872 int i;
1873 isl_ctx *ctx;
1874 isl_pw_aff *res;
1875
1876 if (!list)
1877 return NULL;
1878
1879 ctx = isl_pw_aff_list_get_ctx(list);
1880 if (list->n < 1)
1881 isl_die(ctx, isl_error_invalid,
1882 "list should contain at least one element",
1883 return isl_pw_aff_list_free(list));
1884
1885 res = isl_pw_aff_copy(list->p[0]);
1886 for (i = 1; i < list->n; ++i)
1887 res = fn(res, isl_pw_aff_copy(list->p[i]));
1888
1889 isl_pw_aff_list_free(list);
1890 return res;
1891 }
1892
1893 /* Return an isl_pw_aff that maps each element in the intersection of the
1894 * domains of the elements of list to the minimal corresponding affine
1895 * expression.
1896 */
1897 __isl_give isl_pw_aff *isl_pw_aff_list_min(__isl_take isl_pw_aff_list *list)
1898 {
1899 return pw_aff_list_reduce(list, &isl_pw_aff_min);
1900 }
1901
1902 /* Return an isl_pw_aff that maps each element in the intersection of the
1903 * domains of the elements of list to the maximal corresponding affine
1904 * expression.
1905 */
1906 __isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list)
1907 {
1908 return pw_aff_list_reduce(list, &isl_pw_aff_max);
1909 }
Integer set library