?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_stream_read_map: accept ternary operators in variable definitions
[isl.git] / isl_aff.c
blobde0bd222e2faafa406cadc2d8449551765bd5c18
1 /*
2 * Copyright 2011 INRIA Saclay
3 * Copyright 2011 Universiteit Leiden
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 * and Leiden Institute of Advanced Computer Science,
11 * Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands
12 */
13
14 #include <isl_map_private.h>
15 #include <isl_aff_private.h>
16 #include <isl_dim_private.h>
17 #include <isl_local_space_private.h>
18 #include <isl_mat_private.h>
19 #include <isl_list_private.h>
20 #include <isl/constraint.h>
21 #include <isl/seq.h>
22 #include <isl/set.h>
23
24 __isl_give isl_aff *isl_aff_alloc_vec(__isl_take isl_local_space *ls,
25 __isl_take isl_vec *v)
26 {
27 isl_aff *aff;
28
29 if (!ls || !v)
30 goto error;
31
32 aff = isl_calloc_type(v->ctx, struct isl_aff);
33 if (!aff)
34 goto error;
35
36 aff->ref = 1;
37 aff->ls = ls;
38 aff->v = v;
39
40 return aff;
41 error:
42 isl_local_space_free(ls);
43 isl_vec_free(v);
44 return NULL;
45 }
46
47 __isl_give isl_aff *isl_aff_alloc(__isl_take isl_local_space *ls)
48 {
49 isl_ctx *ctx;
50 isl_vec *v;
51 unsigned total;
52
53 if (!ls)
54 return NULL;
55
56 ctx = isl_local_space_get_ctx(ls);
57 if (!isl_local_space_divs_known(ls))
58 isl_die(ctx, isl_error_invalid, "local space has unknown divs",
59 goto error);
60
61 total = isl_local_space_dim(ls, isl_dim_all);
62 v = isl_vec_alloc(ctx, 1 + 1 + total);
63 return isl_aff_alloc_vec(ls, v);
64 error:
65 isl_local_space_free(ls);
66 return NULL;
67 }
68
69 __isl_give isl_aff *isl_aff_zero(__isl_take isl_local_space *ls)
70 {
71 isl_aff *aff;
72
73 aff = isl_aff_alloc(ls);
74 if (!aff)
75 return NULL;
76
77 isl_int_set_si(aff->v->el[0], 1);
78 isl_seq_clr(aff->v->el + 1, aff->v->size - 1);
79
80 return aff;
81 }
82
83 __isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff)
84 {
85 if (!aff)
86 return NULL;
87
88 aff->ref++;
89 return aff;
90 }
91
92 __isl_give isl_aff *isl_aff_dup(__isl_keep isl_aff *aff)
93 {
94 if (!aff)
95 return NULL;
96
97 return isl_aff_alloc_vec(isl_local_space_copy(aff->ls),
98 isl_vec_copy(aff->v));
99 }
100
101 __isl_give isl_aff *isl_aff_cow(__isl_take isl_aff *aff)
102 {
103 if (!aff)
104 return NULL;
105
106 if (aff->ref == 1)
107 return aff;
108 aff->ref--;
109 return isl_aff_dup(aff);
110 }
111
112 void *isl_aff_free(__isl_take isl_aff *aff)
113 {
114 if (!aff)
115 return NULL;
116
117 if (--aff->ref > 0)
118 return NULL;
119
120 isl_local_space_free(aff->ls);
121 isl_vec_free(aff->v);
122
123 free(aff);
124
125 return NULL;
126 }
127
128 isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff)
129 {
130 return aff ? isl_local_space_get_ctx(aff->ls) : NULL;
131 }
132
133 int isl_aff_dim(__isl_keep isl_aff *aff, enum isl_dim_type type)
134 {
135 return aff ? isl_local_space_dim(aff->ls, type) : 0;
136 }
137
138 __isl_give isl_dim *isl_aff_get_dim(__isl_keep isl_aff *aff)
139 {
140 return aff ? isl_local_space_get_dim(aff->ls) : NULL;
141 }
142
143 __isl_give isl_local_space *isl_aff_get_local_space(__isl_keep isl_aff *aff)
144 {
145 return aff ? isl_local_space_copy(aff->ls) : NULL;
146 }
147
148 const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff,
149 enum isl_dim_type type, unsigned pos)
150 {
151 return aff ? isl_local_space_get_dim_name(aff->ls, type, pos) : 0;
152 }
153
154 __isl_give isl_aff *isl_aff_reset_dim(__isl_take isl_aff *aff,
155 __isl_take isl_dim *dim)
156 {
157 aff = isl_aff_cow(aff);
158 if (!aff || !dim)
159 goto error;
160
161 aff->ls = isl_local_space_reset_dim(aff->ls, dim);
162 if (!aff->ls)
163 return isl_aff_free(aff);
164
165 return aff;
166 error:
167 isl_aff_free(aff);
168 isl_dim_free(dim);
169 return NULL;
170 }
171
172 /* Reorder the coefficients of the affine expression based
173 * on the given reodering.
174 * The reordering r is assumed to have been extended with the local
175 * variables.
176 */
177 static __isl_give isl_vec *vec_reorder(__isl_take isl_vec *vec,
178 __isl_take isl_reordering *r, int n_div)
179 {
180 isl_vec *res;
181 int i;
182
183 if (!vec || !r)
184 goto error;
185
186 res = isl_vec_alloc(vec->ctx, 2 + isl_dim_total(r->dim) + n_div);
187 isl_seq_cpy(res->el, vec->el, 2);
188 isl_seq_clr(res->el + 2, res->size - 2);
189 for (i = 0; i < r->len; ++i)
190 isl_int_set(res->el[2 + r->pos[i]], vec->el[2 + i]);
191
192 isl_reordering_free(r);
193 isl_vec_free(vec);
194 return res;
195 error:
196 isl_vec_free(vec);
197 isl_reordering_free(r);
198 return NULL;
199 }
200
201 /* Reorder the dimensions of "aff" according to the given reordering.
202 */
203 __isl_give isl_aff *isl_aff_realign(__isl_take isl_aff *aff,
204 __isl_take isl_reordering *r)
205 {
206 aff = isl_aff_cow(aff);
207 if (!aff)
208 goto error;
209
210 r = isl_reordering_extend(r, aff->ls->div->n_row);
211 aff->v = vec_reorder(aff->v, isl_reordering_copy(r),
212 aff->ls->div->n_row);
213 aff->ls = isl_local_space_realign(aff->ls, r);
214
215 if (!aff->v || !aff->ls)
216 return isl_aff_free(aff);
217
218 return aff;
219 error:
220 isl_aff_free(aff);
221 isl_reordering_free(r);
222 return NULL;
223 }
224
225 int isl_aff_plain_is_zero(__isl_keep isl_aff *aff)
226 {
227 if (!aff)
228 return -1;
229
230 return isl_seq_first_non_zero(aff->v->el + 1, aff->v->size - 1) < 0;
231 }
232
233 int isl_aff_plain_is_equal(__isl_keep isl_aff *aff1, __isl_keep isl_aff *aff2)
234 {
235 int equal;
236
237 if (!aff1 || !aff2)
238 return -1;
239
240 equal = isl_local_space_is_equal(aff1->ls, aff2->ls);
241 if (equal < 0 || !equal)
242 return equal;
243
244 return isl_vec_is_equal(aff1->v, aff2->v);
245 }
246
247 int isl_aff_get_denominator(__isl_keep isl_aff *aff, isl_int *v)
248 {
249 if (!aff)
250 return -1;
251 isl_int_set(*v, aff->v->el[0]);
252 return 0;
253 }
254
255 int isl_aff_get_constant(__isl_keep isl_aff *aff, isl_int *v)
256 {
257 if (!aff)
258 return -1;
259 isl_int_set(*v, aff->v->el[1]);
260 return 0;
261 }
262
263 int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
264 enum isl_dim_type type, int pos, isl_int *v)
265 {
266 if (!aff)
267 return -1;
268
269 if (pos >= isl_local_space_dim(aff->ls, type))
270 isl_die(aff->v->ctx, isl_error_invalid,
271 "position out of bounds", return -1);
272
273 pos += isl_local_space_offset(aff->ls, type);
274 isl_int_set(*v, aff->v->el[1 + pos]);
275
276 return 0;
277 }
278
279 __isl_give isl_aff *isl_aff_set_denominator(__isl_take isl_aff *aff, isl_int v)
280 {
281 aff = isl_aff_cow(aff);
282 if (!aff)
283 return NULL;
284
285 aff->v = isl_vec_cow(aff->v);
286 if (!aff->v)
287 return isl_aff_free(aff);
288
289 isl_int_set(aff->v->el[0], v);
290
291 return aff;
292 }
293
294 __isl_give isl_aff *isl_aff_set_constant(__isl_take isl_aff *aff, isl_int v)
295 {
296 aff = isl_aff_cow(aff);
297 if (!aff)
298 return NULL;
299
300 aff->v = isl_vec_cow(aff->v);
301 if (!aff->v)
302 return isl_aff_free(aff);
303
304 isl_int_set(aff->v->el[1], v);
305
306 return aff;
307 }
308
309 __isl_give isl_aff *isl_aff_add_constant(__isl_take isl_aff *aff, isl_int v)
310 {
311 if (isl_int_is_zero(v))
312 return aff;
313
314 aff = isl_aff_cow(aff);
315 if (!aff)
316 return NULL;
317
318 aff->v = isl_vec_cow(aff->v);
319 if (!aff->v)
320 return isl_aff_free(aff);
321
322 isl_int_addmul(aff->v->el[1], aff->v->el[0], v);
323
324 return aff;
325 }
326
327 __isl_give isl_aff *isl_aff_add_constant_si(__isl_take isl_aff *aff, int v)
328 {
329 isl_int t;
330
331 isl_int_init(t);
332 isl_int_set_si(t, v);
333 aff = isl_aff_add_constant(aff, t);
334 isl_int_clear(t);
335
336 return aff;
337 }
338
339 __isl_give isl_aff *isl_aff_set_constant_si(__isl_take isl_aff *aff, int v)
340 {
341 aff = isl_aff_cow(aff);
342 if (!aff)
343 return NULL;
344
345 aff->v = isl_vec_cow(aff->v);
346 if (!aff->v)
347 return isl_aff_free(aff);
348
349 isl_int_set_si(aff->v->el[1], v);
350
351 return aff;
352 }
353
354 __isl_give isl_aff *isl_aff_set_coefficient(__isl_take isl_aff *aff,
355 enum isl_dim_type type, int pos, isl_int v)
356 {
357 if (!aff)
358 return NULL;
359
360 if (pos >= isl_local_space_dim(aff->ls, type))
361 isl_die(aff->v->ctx, isl_error_invalid,
362 "position out of bounds", return isl_aff_free(aff));
363
364 aff = isl_aff_cow(aff);
365 if (!aff)
366 return NULL;
367
368 aff->v = isl_vec_cow(aff->v);
369 if (!aff->v)
370 return isl_aff_free(aff);
371
372 pos += isl_local_space_offset(aff->ls, type);
373 isl_int_set(aff->v->el[1 + pos], v);
374
375 return aff;
376 }
377
378 __isl_give isl_aff *isl_aff_set_coefficient_si(__isl_take isl_aff *aff,
379 enum isl_dim_type type, int pos, int v)
380 {
381 if (!aff)
382 return NULL;
383
384 if (pos >= isl_local_space_dim(aff->ls, type))
385 isl_die(aff->v->ctx, isl_error_invalid,
386 "position out of bounds", return isl_aff_free(aff));
387
388 aff = isl_aff_cow(aff);
389 if (!aff)
390 return NULL;
391
392 aff->v = isl_vec_cow(aff->v);
393 if (!aff->v)
394 return isl_aff_free(aff);
395
396 pos += isl_local_space_offset(aff->ls, type);
397 isl_int_set_si(aff->v->el[1 + pos], v);
398
399 return aff;
400 }
401
402 __isl_give isl_aff *isl_aff_add_coefficient(__isl_take isl_aff *aff,
403 enum isl_dim_type type, int pos, isl_int v)
404 {
405 if (!aff)
406 return NULL;
407
408 if (pos >= isl_local_space_dim(aff->ls, type))
409 isl_die(aff->v->ctx, isl_error_invalid,
410 "position out of bounds", return isl_aff_free(aff));
411
412 aff = isl_aff_cow(aff);
413 if (!aff)
414 return NULL;
415
416 aff->v = isl_vec_cow(aff->v);
417 if (!aff->v)
418 return isl_aff_free(aff);
419
420 pos += isl_local_space_offset(aff->ls, type);
421 isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v);
422
423 return aff;
424 }
425
426 __isl_give isl_aff *isl_aff_add_coefficient_si(__isl_take isl_aff *aff,
427 enum isl_dim_type type, int pos, int v)
428 {
429 isl_int t;
430
431 isl_int_init(t);
432 isl_int_set_si(t, v);
433 aff = isl_aff_add_coefficient(aff, type, pos, t);
434 isl_int_clear(t);
435
436 return aff;
437 }
438
439 __isl_give isl_div *isl_aff_get_div(__isl_keep isl_aff *aff, int pos)
440 {
441 if (!aff)
442 return NULL;
443
444 return isl_local_space_get_div(aff->ls, pos);
445 }
446
447 __isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff)
448 {
449 aff = isl_aff_cow(aff);
450 if (!aff)
451 return NULL;
452 aff->v = isl_vec_cow(aff->v);
453 if (!aff->v)
454 return isl_aff_free(aff);
455
456 isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1);
457
458 return aff;
459 }
460
461 /* Given f, return floor(f).
462 * If f is an integer expression, then just return f.
463 * Otherwise, create a new div d = [f] and return the expression d.
464 */
465 __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
466 {
467 int size;
468 isl_ctx *ctx;
469
470 if (!aff)
471 return NULL;
472
473 if (isl_int_is_one(aff->v->el[0]))
474 return aff;
475
476 aff = isl_aff_cow(aff);
477 if (!aff)
478 return NULL;
479
480 aff->ls = isl_local_space_add_div(aff->ls, isl_vec_copy(aff->v));
481 if (!aff->ls)
482 return isl_aff_free(aff);
483
484 ctx = isl_aff_get_ctx(aff);
485 size = aff->v->size;
486 isl_vec_free(aff->v);
487 aff->v = isl_vec_alloc(ctx, size + 1);
488 aff->v = isl_vec_clr(aff->v);
489 if (!aff->v)
490 return isl_aff_free(aff);
491 isl_int_set_si(aff->v->el[0], 1);
492 isl_int_set_si(aff->v->el[size], 1);
493
494 return aff;
495 }
496
497 /* Given f, return ceil(f).
498 * If f is an integer expression, then just return f.
499 * Otherwise, create a new div d = [-f] and return the expression -d.
500 */
501 __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
502 {
503 if (!aff)
504 return NULL;
505
506 if (isl_int_is_one(aff->v->el[0]))
507 return aff;
508
509 aff = isl_aff_neg(aff);
510 aff = isl_aff_floor(aff);
511 aff = isl_aff_neg(aff);
512
513 return aff;
514 }
515
516 /* Apply the expansion computed by isl_merge_divs.
517 * The expansion itself is given by "exp" while the resulting
518 * list of divs is given by "div".
519 */
520 __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
521 __isl_take isl_mat *div, int *exp)
522 {
523 int i, j;
524 int old_n_div;
525 int new_n_div;
526 int offset;
527
528 aff = isl_aff_cow(aff);
529 if (!aff || !div)
530 goto error;
531
532 old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
533 new_n_div = isl_mat_rows(div);
534 if (new_n_div < old_n_div)
535 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
536 "not an expansion", goto error);
537
538 aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div);
539 if (!aff->v)
540 goto error;
541
542 offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
543 j = old_n_div - 1;
544 for (i = new_n_div - 1; i >= 0; --i) {
545 if (j >= 0 && exp[j] == i) {
546 if (i != j)
547 isl_int_swap(aff->v->el[offset + i],
548 aff->v->el[offset + j]);
549 j--;
550 } else
551 isl_int_set_si(aff->v->el[offset + i], 0);
552 }
553
554 aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div));
555 if (!aff->ls)
556 goto error;
557 isl_mat_free(div);
558 return aff;
559 error:
560 isl_aff_free(aff);
561 isl_mat_free(div);
562 return NULL;
563 }
564
565 /* Add two affine expressions that live in the same local space.
566 */
567 static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
568 __isl_take isl_aff *aff2)
569 {
570 isl_int gcd, f;
571
572 aff1 = isl_aff_cow(aff1);
573 if (!aff1 || !aff2)
574 goto error;
575
576 aff1->v = isl_vec_cow(aff1->v);
577 if (!aff1->v)
578 goto error;
579
580 isl_int_init(gcd);
581 isl_int_init(f);
582 isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
583 isl_int_divexact(f, aff2->v->el[0], gcd);
584 isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
585 isl_int_divexact(f, aff1->v->el[0], gcd);
586 isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
587 isl_int_divexact(f, aff2->v->el[0], gcd);
588 isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
589 isl_int_clear(f);
590 isl_int_clear(gcd);
591
592 isl_aff_free(aff2);
593 return aff1;
594 error:
595 isl_aff_free(aff1);
596 isl_aff_free(aff2);
597 return NULL;
598 }
599
600 __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
601 __isl_take isl_aff *aff2)
602 {
603 isl_ctx *ctx;
604 int *exp1 = NULL;
605 int *exp2 = NULL;
606 isl_mat *div;
607
608 if (!aff1 || !aff2)
609 goto error;
610
611 ctx = isl_aff_get_ctx(aff1);
612 if (!isl_dim_equal(aff1->ls->dim, aff2->ls->dim))
613 isl_die(ctx, isl_error_invalid,
614 "spaces don't match", goto error);
615
616 if (aff1->ls->div->n_row == 0 && aff2->ls->div->n_row == 0)
617 return add_expanded(aff1, aff2);
618
619 exp1 = isl_alloc_array(ctx, int, aff1->ls->div->n_row);
620 exp2 = isl_alloc_array(ctx, int, aff2->ls->div->n_row);
621 if (!exp1 || !exp2)
622 goto error;
623
624 div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
625 aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
626 aff2 = isl_aff_expand_divs(aff2, div, exp2);
627 free(exp1);
628 free(exp2);
629
630 return add_expanded(aff1, aff2);
631 error:
632 free(exp1);
633 free(exp2);
634 isl_aff_free(aff1);
635 isl_aff_free(aff2);
636 return NULL;
637 }
638
639 __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
640 __isl_take isl_aff *aff2)
641 {
642 return isl_aff_add(aff1, isl_aff_neg(aff2));
643 }
644
645 __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
646 {
647 isl_int gcd;
648
649 if (isl_int_is_one(f))
650 return aff;
651
652 aff = isl_aff_cow(aff);
653 if (!aff)
654 return NULL;
655 aff->v = isl_vec_cow(aff->v);
656 if (!aff->v)
657 return isl_aff_free(aff);
658
659 isl_int_init(gcd);
660 isl_int_gcd(gcd, aff->v->el[0], f);
661 isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
662 isl_int_divexact(gcd, f, gcd);
663 isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
664 isl_int_clear(gcd);
665
666 return aff;
667 }
668
669 __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
670 {
671 isl_int gcd;
672
673 if (isl_int_is_one(f))
674 return aff;
675
676 aff = isl_aff_cow(aff);
677 if (!aff)
678 return NULL;
679 aff->v = isl_vec_cow(aff->v);
680 if (!aff->v)
681 return isl_aff_free(aff);
682
683 isl_int_init(gcd);
684 isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
685 isl_int_gcd(gcd, gcd, f);
686 isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
687 isl_int_divexact(gcd, f, gcd);
688 isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
689 isl_int_clear(gcd);
690
691 return aff;
692 }
693
694 __isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f)
695 {
696 isl_int v;
697
698 if (f == 1)
699 return aff;
700
701 isl_int_init(v);
702 isl_int_set_ui(v, f);
703 aff = isl_aff_scale_down(aff, v);
704 isl_int_clear(v);
705
706 return aff;
707 }
708
709 __isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff,
710 enum isl_dim_type type, unsigned pos, const char *s)
711 {
712 aff = isl_aff_cow(aff);
713 if (!aff)
714 return NULL;
715 aff->ls = isl_local_space_set_dim_name(aff->ls, type, pos, s);
716 if (!aff->ls)
717 return isl_aff_free(aff);
718
719 return aff;
720 }
721
722 /* Exploit the equalities in "eq" to simplify the affine expression
723 * and the expressions of the integer divisions in the local space.
724 * The integer divisions in this local space are assumed to appear
725 * as regular dimensions in "eq".
726 */
727 static __isl_give isl_aff *isl_aff_substitute_equalities_lifted(
728 __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
729 {
730 int i, j;
731 unsigned total;
732 unsigned n_div;
733
734 if (!eq)
735 goto error;
736 if (eq->n_eq == 0) {
737 isl_basic_set_free(eq);
738 return aff;
739 }
740
741 aff = isl_aff_cow(aff);
742 if (!aff)
743 goto error;
744
745 aff->ls = isl_local_space_substitute_equalities(aff->ls,
746 isl_basic_set_copy(eq));
747 if (!aff->ls)
748 goto error;
749
750 total = 1 + isl_dim_total(eq->dim);
751 n_div = eq->n_div;
752 for (i = 0; i < eq->n_eq; ++i) {
753 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
754 if (j < 0 || j == 0 || j >= total)
755 continue;
756
757 isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total,
758 &aff->v->el[0]);
759 }
760
761 isl_basic_set_free(eq);
762 return aff;
763 error:
764 isl_basic_set_free(eq);
765 isl_aff_free(aff);
766 return NULL;
767 }
768
769 /* Exploit the equalities in "eq" to simplify the affine expression
770 * and the expressions of the integer divisions in the local space.
771 */
772 static __isl_give isl_aff *isl_aff_substitute_equalities(
773 __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
774 {
775 int n_div;
776
777 if (!aff || !eq)
778 goto error;
779 n_div = isl_local_space_dim(aff->ls, isl_dim_div);
780 if (n_div > 0)
781 eq = isl_basic_set_add(eq, isl_dim_set, n_div);
782 return isl_aff_substitute_equalities_lifted(aff, eq);
783 error:
784 isl_basic_set_free(eq);
785 isl_aff_free(aff);
786 return NULL;
787 }
788
789 /* Look for equalities among the variables shared by context and aff
790 * and the integer divisions of aff, if any.
791 * The equalities are then used to eliminate coefficients and/or integer
792 * divisions from aff.
793 */
794 __isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
795 __isl_take isl_set *context)
796 {
797 isl_basic_set *hull;
798 int n_div;
799
800 if (!aff)
801 goto error;
802 n_div = isl_local_space_dim(aff->ls, isl_dim_div);
803 if (n_div > 0) {
804 isl_basic_set *bset;
805 context = isl_set_add_dims(context, isl_dim_set, n_div);
806 bset = isl_basic_set_from_local_space(
807 isl_aff_get_local_space(aff));
808 bset = isl_basic_set_lift(bset);
809 bset = isl_basic_set_flatten(bset);
810 context = isl_set_intersect(context,
811 isl_set_from_basic_set(bset));
812 }
813
814 hull = isl_set_affine_hull(context);
815 return isl_aff_substitute_equalities_lifted(aff, hull);
816 error:
817 isl_aff_free(aff);
818 isl_set_free(context);
819 return NULL;
820 }
821
822 /* Return a basic set containing those elements in the space
823 * of aff where it is non-negative.
824 */
825 __isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff)
826 {
827 isl_constraint *ineq;
828
829 ineq = isl_inequality_from_aff(aff);
830
831 return isl_basic_set_from_constraint(ineq);
832 }
833
834 /* Return a basic set containing those elements in the space
835 * of aff where it is zero.
836 */
837 __isl_give isl_basic_set *isl_aff_zero_basic_set(__isl_take isl_aff *aff)
838 {
839 isl_constraint *ineq;
840
841 ineq = isl_equality_from_aff(aff);
842
843 return isl_basic_set_from_constraint(ineq);
844 }
845
846 /* Return a basic set containing those elements in the shared space
847 * of aff1 and aff2 where aff1 is greater than or equal to aff2.
848 */
849 __isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1,
850 __isl_take isl_aff *aff2)
851 {
852 aff1 = isl_aff_sub(aff1, aff2);
853
854 return isl_aff_nonneg_basic_set(aff1);
855 }
856
857 __isl_give isl_aff *isl_aff_add_on_domain(__isl_keep isl_set *dom,
858 __isl_take isl_aff *aff1, __isl_take isl_aff *aff2)
859 {
860 aff1 = isl_aff_add(aff1, aff2);
861 aff1 = isl_aff_gist(aff1, isl_set_copy(dom));
862 return aff1;
863 }
864
865 int isl_aff_is_empty(__isl_keep isl_aff *aff)
866 {
867 if (!aff)
868 return -1;
869
870 return 0;
871 }
872
873 /* Set active[i] to 1 if the dimension at position i is involved
874 * in the affine expression.
875 */
876 static int set_active(__isl_keep isl_aff *aff, int *active)
877 {
878 int i, j;
879 unsigned total;
880 unsigned offset;
881
882 if (!aff || !active)
883 return -1;
884
885 total = aff->v->size - 2;
886 for (i = 0; i < total; ++i)
887 active[i] = !isl_int_is_zero(aff->v->el[2 + i]);
888
889 offset = isl_local_space_offset(aff->ls, isl_dim_div) - 1;
890 for (i = aff->ls->div->n_row - 1; i >= 0; --i) {
891 if (!active[offset + i])
892 continue;
893 for (j = 0; j < total; ++j)
894 active[j] |=
895 !isl_int_is_zero(aff->ls->div->row[i][2 + j]);
896 }
897
898 return 0;
899 }
900
901 /* Check whether the given affine expression has non-zero coefficient
902 * for any dimension in the given range or if any of these dimensions
903 * appear with non-zero coefficients in any of the integer divisions
904 * involved in the affine expression.
905 */
906 int isl_aff_involves_dims(__isl_keep isl_aff *aff,
907 enum isl_dim_type type, unsigned first, unsigned n)
908 {
909 int i;
910 isl_ctx *ctx;
911 int *active = NULL;
912 int involves = 0;
913
914 if (!aff)
915 return -1;
916 if (n == 0)
917 return 0;
918
919 ctx = isl_aff_get_ctx(aff);
920 if (first + n > isl_aff_dim(aff, type))
921 isl_die(ctx, isl_error_invalid,
922 "range out of bounds", return -1);
923
924 active = isl_calloc_array(ctx, int,
925 isl_local_space_dim(aff->ls, isl_dim_all));
926 if (set_active(aff, active) < 0)
927 goto error;
928
929 first += isl_local_space_offset(aff->ls, type) - 1;
930 for (i = 0; i < n; ++i)
931 if (active[first + i]) {
932 involves = 1;
933 break;
934 }
935
936 free(active);
937
938 return involves;
939 error:
940 free(active);
941 return -1;
942 }
943
944 __isl_give isl_aff *isl_aff_drop_dims(__isl_take isl_aff *aff,
945 enum isl_dim_type type, unsigned first, unsigned n)
946 {
947 isl_ctx *ctx;
948
949 if (!aff)
950 return NULL;
951 if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
952 return aff;
953
954 ctx = isl_aff_get_ctx(aff);
955 if (first + n > isl_aff_dim(aff, type))
956 isl_die(ctx, isl_error_invalid, "range out of bounds",
957 return isl_aff_free(aff));
958
959 aff = isl_aff_cow(aff);
960 if (!aff)
961 return NULL;
962
963 aff->ls = isl_local_space_drop_dims(aff->ls, type, first, n);
964 if (!aff->ls)
965 return isl_aff_free(aff);
966
967 first += 1 + isl_local_space_offset(aff->ls, type);
968 aff->v = isl_vec_drop_els(aff->v, first, n);
969 if (!aff->v)
970 return isl_aff_free(aff);
971
972 return aff;
973 }
974
975 __isl_give isl_aff *isl_aff_insert_dims(__isl_take isl_aff *aff,
976 enum isl_dim_type type, unsigned first, unsigned n)
977 {
978 isl_ctx *ctx;
979
980 if (!aff)
981 return NULL;
982 if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
983 return aff;
984
985 ctx = isl_aff_get_ctx(aff);
986 if (first > isl_aff_dim(aff, type))
987 isl_die(ctx, isl_error_invalid, "position out of bounds",
988 return isl_aff_free(aff));
989
990 aff = isl_aff_cow(aff);
991 if (!aff)
992 return NULL;
993
994 aff->ls = isl_local_space_insert_dims(aff->ls, type, first, n);
995 if (!aff->ls)
996 return isl_aff_free(aff);
997
998 first += 1 + isl_local_space_offset(aff->ls, type);
999 aff->v = isl_vec_insert_zero_els(aff->v, first, n);
1000 if (!aff->v)
1001 return isl_aff_free(aff);
1002
1003 return aff;
1004 }
1005
1006 __isl_give isl_aff *isl_aff_add_dims(__isl_take isl_aff *aff,
1007 enum isl_dim_type type, unsigned n)
1008 {
1009 unsigned pos;
1010
1011 pos = isl_aff_dim(aff, type);
1012
1013 return isl_aff_insert_dims(aff, type, pos, n);
1014 }
1015
1016 __isl_give isl_pw_aff *isl_pw_aff_add_dims(__isl_take isl_pw_aff *pwaff,
1017 enum isl_dim_type type, unsigned n)
1018 {
1019 unsigned pos;
1020
1021 pos = isl_pw_aff_dim(pwaff, type);
1022
1023 return isl_pw_aff_insert_dims(pwaff, type, pos, n);
1024 }
1025
1026 __isl_give isl_pw_aff *isl_pw_aff_set_tuple_id(__isl_take isl_pw_aff *pwaff,
1027 __isl_take isl_id *id)
1028 {
1029 isl_dim *dim;
1030
1031 dim = isl_pw_aff_get_dim(pwaff);
1032 dim = isl_dim_set_tuple_id(dim, isl_dim_set, id);
1033
1034 return isl_pw_aff_reset_dim(pwaff, dim);
1035 }
1036
1037 __isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff)
1038 {
1039 isl_set *dom = isl_set_universe(isl_aff_get_dim(aff));
1040 return isl_pw_aff_alloc(dom, aff);
1041 }
1042
1043 #undef PW
1044 #define PW isl_pw_aff
1045 #undef EL
1046 #define EL isl_aff
1047 #undef EL_IS_ZERO
1048 #define EL_IS_ZERO is_empty
1049 #undef ZERO
1050 #define ZERO empty
1051 #undef IS_ZERO
1052 #define IS_ZERO is_empty
1053 #undef FIELD
1054 #define FIELD aff
1055
1056 #define NO_EVAL
1057 #define NO_OPT
1058 #define NO_MOVE_DIMS
1059 #define NO_LIFT
1060 #define NO_MORPH
1061
1062 #include <isl_pw_templ.c>
1063
1064 static __isl_give isl_set *align_params_pw_pw_set_and(
1065 __isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2,
1066 __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1067 __isl_take isl_pw_aff *pwaff2))
1068 {
1069 if (!pwaff1 || !pwaff2)
1070 goto error;
1071 if (isl_dim_match(pwaff1->dim, isl_dim_param,
1072 pwaff2->dim, isl_dim_param))
1073 return fn(pwaff1, pwaff2);
1074 if (!isl_dim_has_named_params(pwaff1->dim) ||
1075 !isl_dim_has_named_params(pwaff2->dim))
1076 isl_die(isl_pw_aff_get_ctx(pwaff1), isl_error_invalid,
1077 "unaligned unnamed parameters", goto error);
1078 pwaff1 = isl_pw_aff_align_params(pwaff1, isl_pw_aff_get_dim(pwaff2));
1079 pwaff2 = isl_pw_aff_align_params(pwaff2, isl_pw_aff_get_dim(pwaff1));
1080 return fn(pwaff1, pwaff2);
1081 error:
1082 isl_pw_aff_free(pwaff1);
1083 isl_pw_aff_free(pwaff2);
1084 return NULL;
1085 }
1086
1087 /* Compute a piecewise quasi-affine expression with a domain that
1088 * is the union of those of pwaff1 and pwaff2 and such that on each
1089 * cell, the quasi-affine expression is the maximum of those of pwaff1
1090 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
1091 * cell, then the associated expression is the defined one.
1092 */
1093 static __isl_give isl_pw_aff *pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1094 __isl_take isl_pw_aff *pwaff2)
1095 {
1096 int i, j, n;
1097 isl_pw_aff *res;
1098 isl_ctx *ctx;
1099 isl_set *set;
1100
1101 if (!pwaff1 || !pwaff2)
1102 goto error;
1103
1104 ctx = isl_dim_get_ctx(pwaff1->dim);
1105 if (!isl_dim_equal(pwaff1->dim, pwaff2->dim))
1106 isl_die(ctx, isl_error_invalid,
1107 "arguments should live in same space", goto error);
1108
1109 if (isl_pw_aff_is_empty(pwaff1)) {
1110 isl_pw_aff_free(pwaff1);
1111 return pwaff2;
1112 }
1113
1114 if (isl_pw_aff_is_empty(pwaff2)) {
1115 isl_pw_aff_free(pwaff2);
1116 return pwaff1;
1117 }
1118
1119 n = 2 * (pwaff1->n + 1) * (pwaff2->n + 1);
1120 res = isl_pw_aff_alloc_(isl_dim_copy(pwaff1->dim), n);
1121
1122 for (i = 0; i < pwaff1->n; ++i) {
1123 set = isl_set_copy(pwaff1->p[i].set);
1124 for (j = 0; j < pwaff2->n; ++j) {
1125 struct isl_set *common;
1126 isl_set *ge;
1127
1128 common = isl_set_intersect(
1129 isl_set_copy(pwaff1->p[i].set),
1130 isl_set_copy(pwaff2->p[j].set));
1131 ge = isl_set_from_basic_set(isl_aff_ge_basic_set(
1132 isl_aff_copy(pwaff2->p[j].aff),
1133 isl_aff_copy(pwaff1->p[i].aff)));
1134 ge = isl_set_intersect(common, ge);
1135 if (isl_set_plain_is_empty(ge)) {
1136 isl_set_free(ge);
1137 continue;
1138 }
1139 set = isl_set_subtract(set, isl_set_copy(ge));
1140
1141 res = isl_pw_aff_add_piece(res, ge,
1142 isl_aff_copy(pwaff2->p[j].aff));
1143 }
1144 res = isl_pw_aff_add_piece(res, set,
1145 isl_aff_copy(pwaff1->p[i].aff));
1146 }
1147
1148 for (j = 0; j < pwaff2->n; ++j) {
1149 set = isl_set_copy(pwaff2->p[j].set);
1150 for (i = 0; i < pwaff1->n; ++i)
1151 set = isl_set_subtract(set,
1152 isl_set_copy(pwaff1->p[i].set));
1153 res = isl_pw_aff_add_piece(res, set,
1154 isl_aff_copy(pwaff2->p[j].aff));
1155 }
1156
1157 isl_pw_aff_free(pwaff1);
1158 isl_pw_aff_free(pwaff2);
1159
1160 return res;
1161 error:
1162 isl_pw_aff_free(pwaff1);
1163 isl_pw_aff_free(pwaff2);
1164 return NULL;
1165 }
1166
1167 __isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
1168 __isl_take isl_pw_aff *pwaff2)
1169 {
1170 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_union_max);
1171 }
1172
1173 /* Construct a map with as domain the domain of pwaff and
1174 * one-dimensional range corresponding to the affine expressions.
1175 */
1176 __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
1177 {
1178 int i;
1179 isl_dim *dim;
1180 isl_map *map;
1181
1182 if (!pwaff)
1183 return NULL;
1184
1185 dim = isl_pw_aff_get_dim(pwaff);
1186 dim = isl_dim_from_domain(dim);
1187 dim = isl_dim_add(dim, isl_dim_out, 1);
1188 map = isl_map_empty(dim);
1189
1190 for (i = 0; i < pwaff->n; ++i) {
1191 isl_basic_map *bmap;
1192 isl_map *map_i;
1193
1194 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
1195 map_i = isl_map_from_basic_map(bmap);
1196 map_i = isl_map_intersect_domain(map_i,
1197 isl_set_copy(pwaff->p[i].set));
1198 map = isl_map_union_disjoint(map, map_i);
1199 }
1200
1201 isl_pw_aff_free(pwaff);
1202
1203 return map;
1204 }
1205
1206 /* Return a set containing those elements in the domain
1207 * of pwaff where it is non-negative.
1208 */
1209 __isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
1210 {
1211 int i;
1212 isl_set *set;
1213
1214 if (!pwaff)
1215 return NULL;
1216
1217 set = isl_set_empty(isl_pw_aff_get_dim(pwaff));
1218
1219 for (i = 0; i < pwaff->n; ++i) {
1220 isl_basic_set *bset;
1221 isl_set *set_i;
1222
1223 bset = isl_aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff));
1224 set_i = isl_set_from_basic_set(bset);
1225 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1226 set = isl_set_union_disjoint(set, set_i);
1227 }
1228
1229 isl_pw_aff_free(pwaff);
1230
1231 return set;
1232 }
1233
1234 /* Return a set containing those elements in the domain
1235 * of pwaff where it is zero.
1236 */
1237 __isl_give isl_set *isl_pw_aff_zero_set(__isl_take isl_pw_aff *pwaff)
1238 {
1239 int i;
1240 isl_set *set;
1241
1242 if (!pwaff)
1243 return NULL;
1244
1245 set = isl_set_empty(isl_pw_aff_get_dim(pwaff));
1246
1247 for (i = 0; i < pwaff->n; ++i) {
1248 isl_basic_set *bset;
1249 isl_set *set_i;
1250
1251 bset = isl_aff_zero_basic_set(isl_aff_copy(pwaff->p[i].aff));
1252 set_i = isl_set_from_basic_set(bset);
1253 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
1254 set = isl_set_union_disjoint(set, set_i);
1255 }
1256
1257 isl_pw_aff_free(pwaff);
1258
1259 return set;
1260 }
1261
1262 /* Return a set containing those elements in the domain
1263 * of pwaff where it is not zero.
1264 */
1265 __isl_give isl_set *isl_pw_aff_non_zero_set(__isl_take isl_pw_aff *pwaff)
1266 {
1267 return isl_set_complement(isl_pw_aff_zero_set(pwaff));
1268 }
1269
1270 /* Return a set containing those elements in the shared domain
1271 * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
1272 *
1273 * We compute the difference on the shared domain and then construct
1274 * the set of values where this difference is non-negative.
1275 * If strict is set, we first subtract 1 from the difference.
1276 * If equal is set, we only return the elements where pwaff1 and pwaff2
1277 * are equal.
1278 */
1279 static __isl_give isl_set *pw_aff_gte_set(__isl_take isl_pw_aff *pwaff1,
1280 __isl_take isl_pw_aff *pwaff2, int strict, int equal)
1281 {
1282 isl_set *set1, *set2;
1283
1284 set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1));
1285 set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2));
1286 set1 = isl_set_intersect(set1, set2);
1287 pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1));
1288 pwaff2 = isl_pw_aff_intersect_domain(pwaff2, isl_set_copy(set1));
1289 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2));
1290
1291 if (strict) {
1292 isl_dim *dim = isl_set_get_dim(set1);
1293 isl_aff *aff;
1294 aff = isl_aff_zero(isl_local_space_from_dim(dim));
1295 aff = isl_aff_add_constant_si(aff, -1);
1296 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_alloc(set1, aff));
1297 } else
1298 isl_set_free(set1);
1299
1300 if (equal)
1301 return isl_pw_aff_zero_set(pwaff1);
1302 return isl_pw_aff_nonneg_set(pwaff1);
1303 }
1304
1305 /* Return a set containing those elements in the shared domain
1306 * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
1307 */
1308 static __isl_give isl_set *pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1309 __isl_take isl_pw_aff *pwaff2)
1310 {
1311 return pw_aff_gte_set(pwaff1, pwaff2, 0, 1);
1312 }
1313
1314 __isl_give isl_set *isl_pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
1315 __isl_take isl_pw_aff *pwaff2)
1316 {
1317 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_eq_set);
1318 }
1319
1320 /* Return a set containing those elements in the shared domain
1321 * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
1322 */
1323 static __isl_give isl_set *pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1324 __isl_take isl_pw_aff *pwaff2)
1325 {
1326 return pw_aff_gte_set(pwaff1, pwaff2, 0, 0);
1327 }
1328
1329 __isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
1330 __isl_take isl_pw_aff *pwaff2)
1331 {
1332 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ge_set);
1333 }
1334
1335 /* Return a set containing those elements in the shared domain
1336 * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
1337 */
1338 static __isl_give isl_set *pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1339 __isl_take isl_pw_aff *pwaff2)
1340 {
1341 return pw_aff_gte_set(pwaff1, pwaff2, 1, 0);
1342 }
1343
1344 __isl_give isl_set *isl_pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
1345 __isl_take isl_pw_aff *pwaff2)
1346 {
1347 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_gt_set);
1348 }
1349
1350 __isl_give isl_set *isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1,
1351 __isl_take isl_pw_aff *pwaff2)
1352 {
1353 return isl_pw_aff_ge_set(pwaff2, pwaff1);
1354 }
1355
1356 __isl_give isl_set *isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1,
1357 __isl_take isl_pw_aff *pwaff2)
1358 {
1359 return isl_pw_aff_gt_set(pwaff2, pwaff1);
1360 }
1361
1362 /* Return a set containing those elements in the shared domain
1363 * of the elements of list1 and list2 where each element in list1
1364 * has the relation specified by "fn" with each element in list2.
1365 */
1366 static __isl_give isl_set *pw_aff_list_set(__isl_take isl_pw_aff_list *list1,
1367 __isl_take isl_pw_aff_list *list2,
1368 __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
1369 __isl_take isl_pw_aff *pwaff2))
1370 {
1371 int i, j;
1372 isl_ctx *ctx;
1373 isl_set *set;
1374
1375 if (!list1 || !list2)
1376 goto error;
1377
1378 ctx = isl_pw_aff_list_get_ctx(list1);
1379 if (list1->n < 1 || list2->n < 1)
1380 isl_die(ctx, isl_error_invalid,
1381 "list should contain at least one element", goto error);
1382
1383 set = isl_set_universe(isl_pw_aff_get_dim(list1->p[0]));
1384 for (i = 0; i < list1->n; ++i)
1385 for (j = 0; j < list2->n; ++j) {
1386 isl_set *set_ij;
1387
1388 set_ij = fn(isl_pw_aff_copy(list1->p[i]),
1389 isl_pw_aff_copy(list2->p[j]));
1390 set = isl_set_intersect(set, set_ij);
1391 }
1392
1393 isl_pw_aff_list_free(list1);
1394 isl_pw_aff_list_free(list2);
1395 return set;
1396 error:
1397 isl_pw_aff_list_free(list1);
1398 isl_pw_aff_list_free(list2);
1399 return NULL;
1400 }
1401
1402 /* Return a set containing those elements in the shared domain
1403 * of the elements of list1 and list2 where each element in list1
1404 * is equal to each element in list2.
1405 */
1406 __isl_give isl_set *isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list *list1,
1407 __isl_take isl_pw_aff_list *list2)
1408 {
1409 return pw_aff_list_set(list1, list2, &isl_pw_aff_eq_set);
1410 }
1411
1412 __isl_give isl_set *isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list *list1,
1413 __isl_take isl_pw_aff_list *list2)
1414 {
1415 return pw_aff_list_set(list1, list2, &isl_pw_aff_ne_set);
1416 }
1417
1418 /* Return a set containing those elements in the shared domain
1419 * of the elements of list1 and list2 where each element in list1
1420 * is less than or equal to each element in list2.
1421 */
1422 __isl_give isl_set *isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list *list1,
1423 __isl_take isl_pw_aff_list *list2)
1424 {
1425 return pw_aff_list_set(list1, list2, &isl_pw_aff_le_set);
1426 }
1427
1428 __isl_give isl_set *isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list *list1,
1429 __isl_take isl_pw_aff_list *list2)
1430 {
1431 return pw_aff_list_set(list1, list2, &isl_pw_aff_lt_set);
1432 }
1433
1434 __isl_give isl_set *isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list *list1,
1435 __isl_take isl_pw_aff_list *list2)
1436 {
1437 return pw_aff_list_set(list1, list2, &isl_pw_aff_ge_set);
1438 }
1439
1440 __isl_give isl_set *isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list *list1,
1441 __isl_take isl_pw_aff_list *list2)
1442 {
1443 return pw_aff_list_set(list1, list2, &isl_pw_aff_gt_set);
1444 }
1445
1446
1447 /* Return a set containing those elements in the shared domain
1448 * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
1449 */
1450 static __isl_give isl_set *pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1451 __isl_take isl_pw_aff *pwaff2)
1452 {
1453 isl_set *set_lt, *set_gt;
1454
1455 set_lt = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1),
1456 isl_pw_aff_copy(pwaff2));
1457 set_gt = isl_pw_aff_gt_set(pwaff1, pwaff2);
1458 return isl_set_union_disjoint(set_lt, set_gt);
1459 }
1460
1461 __isl_give isl_set *isl_pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
1462 __isl_take isl_pw_aff *pwaff2)
1463 {
1464 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ne_set);
1465 }
1466
1467 __isl_give isl_pw_aff *isl_pw_aff_scale_down(__isl_take isl_pw_aff *pwaff,
1468 isl_int v)
1469 {
1470 int i;
1471
1472 if (isl_int_is_one(v))
1473 return pwaff;
1474 if (!isl_int_is_pos(v))
1475 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
1476 "factor needs to be positive",
1477 return isl_pw_aff_free(pwaff));
1478 pwaff = isl_pw_aff_cow(pwaff);
1479 if (!pwaff)
1480 return NULL;
1481 if (pwaff->n == 0)
1482 return pwaff;
1483
1484 for (i = 0; i < pwaff->n; ++i) {
1485 pwaff->p[i].aff = isl_aff_scale_down(pwaff->p[i].aff, v);
1486 if (!pwaff->p[i].aff)
1487 return isl_pw_aff_free(pwaff);
1488 }
1489
1490 return pwaff;
1491 }
1492
1493 __isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff)
1494 {
1495 int i;
1496
1497 pwaff = isl_pw_aff_cow(pwaff);
1498 if (!pwaff)
1499 return NULL;
1500 if (pwaff->n == 0)
1501 return pwaff;
1502
1503 for (i = 0; i < pwaff->n; ++i) {
1504 pwaff->p[i].aff = isl_aff_floor(pwaff->p[i].aff);
1505 if (!pwaff->p[i].aff)
1506 return isl_pw_aff_free(pwaff);
1507 }
1508
1509 return pwaff;
1510 }
1511
1512 __isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff)
1513 {
1514 int i;
1515
1516 pwaff = isl_pw_aff_cow(pwaff);
1517 if (!pwaff)
1518 return NULL;
1519 if (pwaff->n == 0)
1520 return pwaff;
1521
1522 for (i = 0; i < pwaff->n; ++i) {
1523 pwaff->p[i].aff = isl_aff_ceil(pwaff->p[i].aff);
1524 if (!pwaff->p[i].aff)
1525 return isl_pw_aff_free(pwaff);
1526 }
1527
1528 return pwaff;
1529 }
1530
1531 /* Return an affine expression that is equal to pwaff_true for elements
1532 * in "cond" and to pwaff_false for elements not in "cond".
1533 * That is, return cond ? pwaff_true : pwaff_false;
1534 */
1535 __isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_set *cond,
1536 __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false)
1537 {
1538 isl_set *comp;
1539
1540 comp = isl_set_complement(isl_set_copy(cond));
1541 pwaff_true = isl_pw_aff_intersect_domain(pwaff_true, cond);
1542 pwaff_false = isl_pw_aff_intersect_domain(pwaff_false, comp);
1543
1544 return isl_pw_aff_add_disjoint(pwaff_true, pwaff_false);
1545 }
1546
1547 int isl_aff_is_cst(__isl_keep isl_aff *aff)
1548 {
1549 if (!aff)
1550 return -1;
1551
1552 return isl_seq_first_non_zero(aff->v->el + 2, aff->v->size - 2) == -1;
1553 }
1554
1555 /* Check whether pwaff is a piecewise constant.
1556 */
1557 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff)
1558 {
1559 int i;
1560
1561 if (!pwaff)
1562 return -1;
1563
1564 for (i = 0; i < pwaff->n; ++i) {
1565 int is_cst = isl_aff_is_cst(pwaff->p[i].aff);
1566 if (is_cst < 0 || !is_cst)
1567 return is_cst;
1568 }
1569
1570 return 1;
1571 }
1572
1573 __isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
1574 __isl_take isl_aff *aff2)
1575 {
1576 if (!isl_aff_is_cst(aff2) && isl_aff_is_cst(aff1))
1577 return isl_aff_mul(aff2, aff1);
1578
1579 if (!isl_aff_is_cst(aff2))
1580 isl_die(isl_aff_get_ctx(aff1), isl_error_invalid,
1581 "at least one affine expression should be constant",
1582 goto error);
1583
1584 aff1 = isl_aff_cow(aff1);
1585 if (!aff1 || !aff2)
1586 goto error;
1587
1588 aff1 = isl_aff_scale(aff1, aff2->v->el[1]);
1589 aff1 = isl_aff_scale_down(aff1, aff2->v->el[0]);
1590
1591 isl_aff_free(aff2);
1592 return aff1;
1593 error:
1594 isl_aff_free(aff1);
1595 isl_aff_free(aff2);
1596 return NULL;
1597 }
1598
1599 static __isl_give isl_pw_aff *pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1600 __isl_take isl_pw_aff *pwaff2)
1601 {
1602 int i, j, n;
1603 isl_pw_aff *res;
1604
1605 if (!pwaff1 || !pwaff2)
1606 goto error;
1607
1608 n = pwaff1->n * pwaff2->n;
1609 res = isl_pw_aff_alloc_(isl_dim_copy(pwaff1->dim), n);
1610
1611 for (i = 0; i < pwaff1->n; ++i) {
1612 for (j = 0; j < pwaff2->n; ++j) {
1613 isl_set *common;
1614 isl_aff *prod;
1615 common = isl_set_intersect(
1616 isl_set_copy(pwaff1->p[i].set),
1617 isl_set_copy(pwaff2->p[j].set));
1618 if (isl_set_plain_is_empty(common)) {
1619 isl_set_free(common);
1620 continue;
1621 }
1622
1623 prod = isl_aff_mul(isl_aff_copy(pwaff1->p[i].aff),
1624 isl_aff_copy(pwaff2->p[j].aff));
1625
1626 res = isl_pw_aff_add_piece(res, common, prod);
1627 }
1628 }
1629
1630 isl_pw_aff_free(pwaff1);
1631 isl_pw_aff_free(pwaff2);
1632 return res;
1633 error:
1634 isl_pw_aff_free(pwaff1);
1635 isl_pw_aff_free(pwaff2);
1636 return NULL;
1637 }
1638
1639 __isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
1640 __isl_take isl_pw_aff *pwaff2)
1641 {
1642 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul);
1643 }
1644
1645 static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1646 __isl_take isl_pw_aff *pwaff2)
1647 {
1648 isl_set *le;
1649
1650 le = isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1),
1651 isl_pw_aff_copy(pwaff2));
1652 return isl_pw_aff_cond(le, pwaff1, pwaff2);
1653 }
1654
1655 __isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
1656 __isl_take isl_pw_aff *pwaff2)
1657 {
1658 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_min);
1659 }
1660
1661 static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1662 __isl_take isl_pw_aff *pwaff2)
1663 {
1664 isl_set *le;
1665
1666 le = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1),
1667 isl_pw_aff_copy(pwaff2));
1668 return isl_pw_aff_cond(le, pwaff1, pwaff2);
1669 }
1670
1671 __isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
1672 __isl_take isl_pw_aff *pwaff2)
1673 {
1674 return align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_max);
1675 }
1676
1677 static __isl_give isl_pw_aff *pw_aff_list_reduce(
1678 __isl_take isl_pw_aff_list *list,
1679 __isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pwaff1,
1680 __isl_take isl_pw_aff *pwaff2))
1681 {
1682 int i;
1683 isl_ctx *ctx;
1684 isl_pw_aff *res;
1685
1686 if (!list)
1687 return NULL;
1688
1689 ctx = isl_pw_aff_list_get_ctx(list);
1690 if (list->n < 1)
1691 isl_die(ctx, isl_error_invalid,
1692 "list should contain at least one element",
1693 return isl_pw_aff_list_free(list));
1694
1695 res = isl_pw_aff_copy(list->p[0]);
1696 for (i = 1; i < list->n; ++i)
1697 res = fn(res, isl_pw_aff_copy(list->p[i]));
1698
1699 isl_pw_aff_list_free(list);
1700 return res;
1701 }
1702
1703 /* Return an isl_pw_aff that maps each element in the intersection of the
1704 * domains of the elements of list to the minimal corresponding affine
1705 * expression.
1706 */
1707 __isl_give isl_pw_aff *isl_pw_aff_list_min(__isl_take isl_pw_aff_list *list)
1708 {
1709 return pw_aff_list_reduce(list, &isl_pw_aff_min);
1710 }
1711
1712 /* Return an isl_pw_aff that maps each element in the intersection of the
1713 * domains of the elements of list to the maximal corresponding affine
1714 * expression.
1715 */
1716 __isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list)
1717 {
1718 return pw_aff_list_reduce(list, &isl_pw_aff_max);
1719 }
Integer set library