Merge branch 'maint'
[isl.git] / isl_aff.c
blob30d11e6f493f7014c128ac45b4999f47d163c3ed
1 /*
2 * Copyright 2011 INRIA Saclay
3 * Copyright 2011 Sven Verdoolaege
4 * Copyright 2012-2014 Ecole Normale Superieure
6 * Use of this software is governed by the MIT license
8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * 91893 Orsay, France
11 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
14 #include <isl_ctx_private.h>
15 #define ISL_DIM_H
16 #include <isl_map_private.h>
17 #include <isl_union_map_private.h>
18 #include <isl_aff_private.h>
19 #include <isl_space_private.h>
20 #include <isl_local_space_private.h>
21 #include <isl_vec_private.h>
22 #include <isl_mat_private.h>
23 #include <isl/constraint.h>
24 #include <isl_seq.h>
25 #include <isl/set.h>
26 #include <isl_val_private.h>
27 #include <isl/deprecated/aff_int.h>
28 #include <isl_config.h>
30 #undef BASE
31 #define BASE aff
33 #include <isl_list_templ.c>
35 #undef BASE
36 #define BASE pw_aff
38 #include <isl_list_templ.c>
40 __isl_give isl_aff *isl_aff_alloc_vec(__isl_take isl_local_space *ls,
41 __isl_take isl_vec *v)
43 isl_aff *aff;
45 if (!ls || !v)
46 goto error;
48 aff = isl_calloc_type(v->ctx, struct isl_aff);
49 if (!aff)
50 goto error;
52 aff->ref = 1;
53 aff->ls = ls;
54 aff->v = v;
56 return aff;
57 error:
58 isl_local_space_free(ls);
59 isl_vec_free(v);
60 return NULL;
63 __isl_give isl_aff *isl_aff_alloc(__isl_take isl_local_space *ls)
65 isl_ctx *ctx;
66 isl_vec *v;
67 unsigned total;
69 if (!ls)
70 return NULL;
72 ctx = isl_local_space_get_ctx(ls);
73 if (!isl_local_space_divs_known(ls))
74 isl_die(ctx, isl_error_invalid, "local space has unknown divs",
75 goto error);
76 if (!isl_local_space_is_set(ls))
77 isl_die(ctx, isl_error_invalid,
78 "domain of affine expression should be a set",
79 goto error);
81 total = isl_local_space_dim(ls, isl_dim_all);
82 v = isl_vec_alloc(ctx, 1 + 1 + total);
83 return isl_aff_alloc_vec(ls, v);
84 error:
85 isl_local_space_free(ls);
86 return NULL;
89 __isl_give isl_aff *isl_aff_zero_on_domain(__isl_take isl_local_space *ls)
91 isl_aff *aff;
93 aff = isl_aff_alloc(ls);
94 if (!aff)
95 return NULL;
97 isl_int_set_si(aff->v->el[0], 1);
98 isl_seq_clr(aff->v->el + 1, aff->v->size - 1);
100 return aff;
103 /* Return a piecewise affine expression defined on the specified domain
104 * that is equal to zero.
106 __isl_give isl_pw_aff *isl_pw_aff_zero_on_domain(__isl_take isl_local_space *ls)
108 return isl_pw_aff_from_aff(isl_aff_zero_on_domain(ls));
111 /* Return an affine expression defined on the specified domain
112 * that represents NaN.
114 __isl_give isl_aff *isl_aff_nan_on_domain(__isl_take isl_local_space *ls)
116 isl_aff *aff;
118 aff = isl_aff_alloc(ls);
119 if (!aff)
120 return NULL;
122 isl_seq_clr(aff->v->el, aff->v->size);
124 return aff;
127 /* Return a piecewise affine expression defined on the specified domain
128 * that represents NaN.
130 __isl_give isl_pw_aff *isl_pw_aff_nan_on_domain(__isl_take isl_local_space *ls)
132 return isl_pw_aff_from_aff(isl_aff_nan_on_domain(ls));
135 /* Return an affine expression that is equal to "val" on
136 * domain local space "ls".
138 __isl_give isl_aff *isl_aff_val_on_domain(__isl_take isl_local_space *ls,
139 __isl_take isl_val *val)
141 isl_aff *aff;
143 if (!ls || !val)
144 goto error;
145 if (!isl_val_is_rat(val))
146 isl_die(isl_val_get_ctx(val), isl_error_invalid,
147 "expecting rational value", goto error);
149 aff = isl_aff_alloc(isl_local_space_copy(ls));
150 if (!aff)
151 goto error;
153 isl_seq_clr(aff->v->el + 2, aff->v->size - 2);
154 isl_int_set(aff->v->el[1], val->n);
155 isl_int_set(aff->v->el[0], val->d);
157 isl_local_space_free(ls);
158 isl_val_free(val);
159 return aff;
160 error:
161 isl_local_space_free(ls);
162 isl_val_free(val);
163 return NULL;
166 /* Return an affine expression that is equal to the specified dimension
167 * in "ls".
169 __isl_give isl_aff *isl_aff_var_on_domain(__isl_take isl_local_space *ls,
170 enum isl_dim_type type, unsigned pos)
172 isl_space *space;
173 isl_aff *aff;
175 if (!ls)
176 return NULL;
178 space = isl_local_space_get_space(ls);
179 if (!space)
180 goto error;
181 if (isl_space_is_map(space))
182 isl_die(isl_space_get_ctx(space), isl_error_invalid,
183 "expecting (parameter) set space", goto error);
184 if (pos >= isl_local_space_dim(ls, type))
185 isl_die(isl_space_get_ctx(space), isl_error_invalid,
186 "position out of bounds", goto error);
188 isl_space_free(space);
189 aff = isl_aff_alloc(ls);
190 if (!aff)
191 return NULL;
193 pos += isl_local_space_offset(aff->ls, type);
195 isl_int_set_si(aff->v->el[0], 1);
196 isl_seq_clr(aff->v->el + 1, aff->v->size - 1);
197 isl_int_set_si(aff->v->el[1 + pos], 1);
199 return aff;
200 error:
201 isl_local_space_free(ls);
202 isl_space_free(space);
203 return NULL;
206 /* Return a piecewise affine expression that is equal to
207 * the specified dimension in "ls".
209 __isl_give isl_pw_aff *isl_pw_aff_var_on_domain(__isl_take isl_local_space *ls,
210 enum isl_dim_type type, unsigned pos)
212 return isl_pw_aff_from_aff(isl_aff_var_on_domain(ls, type, pos));
215 __isl_give isl_aff *isl_aff_copy(__isl_keep isl_aff *aff)
217 if (!aff)
218 return NULL;
220 aff->ref++;
221 return aff;
224 __isl_give isl_aff *isl_aff_dup(__isl_keep isl_aff *aff)
226 if (!aff)
227 return NULL;
229 return isl_aff_alloc_vec(isl_local_space_copy(aff->ls),
230 isl_vec_copy(aff->v));
233 __isl_give isl_aff *isl_aff_cow(__isl_take isl_aff *aff)
235 if (!aff)
236 return NULL;
238 if (aff->ref == 1)
239 return aff;
240 aff->ref--;
241 return isl_aff_dup(aff);
244 __isl_null isl_aff *isl_aff_free(__isl_take isl_aff *aff)
246 if (!aff)
247 return NULL;
249 if (--aff->ref > 0)
250 return NULL;
252 isl_local_space_free(aff->ls);
253 isl_vec_free(aff->v);
255 free(aff);
257 return NULL;
260 isl_ctx *isl_aff_get_ctx(__isl_keep isl_aff *aff)
262 return aff ? isl_local_space_get_ctx(aff->ls) : NULL;
265 /* Externally, an isl_aff has a map space, but internally, the
266 * ls field corresponds to the domain of that space.
268 int isl_aff_dim(__isl_keep isl_aff *aff, enum isl_dim_type type)
270 if (!aff)
271 return 0;
272 if (type == isl_dim_out)
273 return 1;
274 if (type == isl_dim_in)
275 type = isl_dim_set;
276 return isl_local_space_dim(aff->ls, type);
279 __isl_give isl_space *isl_aff_get_domain_space(__isl_keep isl_aff *aff)
281 return aff ? isl_local_space_get_space(aff->ls) : NULL;
284 __isl_give isl_space *isl_aff_get_space(__isl_keep isl_aff *aff)
286 isl_space *space;
287 if (!aff)
288 return NULL;
289 space = isl_local_space_get_space(aff->ls);
290 space = isl_space_from_domain(space);
291 space = isl_space_add_dims(space, isl_dim_out, 1);
292 return space;
295 __isl_give isl_local_space *isl_aff_get_domain_local_space(
296 __isl_keep isl_aff *aff)
298 return aff ? isl_local_space_copy(aff->ls) : NULL;
301 __isl_give isl_local_space *isl_aff_get_local_space(__isl_keep isl_aff *aff)
303 isl_local_space *ls;
304 if (!aff)
305 return NULL;
306 ls = isl_local_space_copy(aff->ls);
307 ls = isl_local_space_from_domain(ls);
308 ls = isl_local_space_add_dims(ls, isl_dim_out, 1);
309 return ls;
312 /* Externally, an isl_aff has a map space, but internally, the
313 * ls field corresponds to the domain of that space.
315 const char *isl_aff_get_dim_name(__isl_keep isl_aff *aff,
316 enum isl_dim_type type, unsigned pos)
318 if (!aff)
319 return NULL;
320 if (type == isl_dim_out)
321 return NULL;
322 if (type == isl_dim_in)
323 type = isl_dim_set;
324 return isl_local_space_get_dim_name(aff->ls, type, pos);
327 __isl_give isl_aff *isl_aff_reset_domain_space(__isl_take isl_aff *aff,
328 __isl_take isl_space *dim)
330 aff = isl_aff_cow(aff);
331 if (!aff || !dim)
332 goto error;
334 aff->ls = isl_local_space_reset_space(aff->ls, dim);
335 if (!aff->ls)
336 return isl_aff_free(aff);
338 return aff;
339 error:
340 isl_aff_free(aff);
341 isl_space_free(dim);
342 return NULL;
345 /* Reset the space of "aff". This function is called from isl_pw_templ.c
346 * and doesn't know if the space of an element object is represented
347 * directly or through its domain. It therefore passes along both.
349 __isl_give isl_aff *isl_aff_reset_space_and_domain(__isl_take isl_aff *aff,
350 __isl_take isl_space *space, __isl_take isl_space *domain)
352 isl_space_free(space);
353 return isl_aff_reset_domain_space(aff, domain);
356 /* Reorder the coefficients of the affine expression based
357 * on the given reodering.
358 * The reordering r is assumed to have been extended with the local
359 * variables.
361 static __isl_give isl_vec *vec_reorder(__isl_take isl_vec *vec,
362 __isl_take isl_reordering *r, int n_div)
364 isl_vec *res;
365 int i;
367 if (!vec || !r)
368 goto error;
370 res = isl_vec_alloc(vec->ctx,
371 2 + isl_space_dim(r->dim, isl_dim_all) + n_div);
372 isl_seq_cpy(res->el, vec->el, 2);
373 isl_seq_clr(res->el + 2, res->size - 2);
374 for (i = 0; i < r->len; ++i)
375 isl_int_set(res->el[2 + r->pos[i]], vec->el[2 + i]);
377 isl_reordering_free(r);
378 isl_vec_free(vec);
379 return res;
380 error:
381 isl_vec_free(vec);
382 isl_reordering_free(r);
383 return NULL;
386 /* Reorder the dimensions of the domain of "aff" according
387 * to the given reordering.
389 __isl_give isl_aff *isl_aff_realign_domain(__isl_take isl_aff *aff,
390 __isl_take isl_reordering *r)
392 aff = isl_aff_cow(aff);
393 if (!aff)
394 goto error;
396 r = isl_reordering_extend(r, aff->ls->div->n_row);
397 aff->v = vec_reorder(aff->v, isl_reordering_copy(r),
398 aff->ls->div->n_row);
399 aff->ls = isl_local_space_realign(aff->ls, r);
401 if (!aff->v || !aff->ls)
402 return isl_aff_free(aff);
404 return aff;
405 error:
406 isl_aff_free(aff);
407 isl_reordering_free(r);
408 return NULL;
411 __isl_give isl_aff *isl_aff_align_params(__isl_take isl_aff *aff,
412 __isl_take isl_space *model)
414 if (!aff || !model)
415 goto error;
417 if (!isl_space_match(aff->ls->dim, isl_dim_param,
418 model, isl_dim_param)) {
419 isl_reordering *exp;
421 model = isl_space_drop_dims(model, isl_dim_in,
422 0, isl_space_dim(model, isl_dim_in));
423 model = isl_space_drop_dims(model, isl_dim_out,
424 0, isl_space_dim(model, isl_dim_out));
425 exp = isl_parameter_alignment_reordering(aff->ls->dim, model);
426 exp = isl_reordering_extend_space(exp,
427 isl_aff_get_domain_space(aff));
428 aff = isl_aff_realign_domain(aff, exp);
431 isl_space_free(model);
432 return aff;
433 error:
434 isl_space_free(model);
435 isl_aff_free(aff);
436 return NULL;
439 /* Is "aff" obviously equal to zero?
441 * If the denominator is zero, then "aff" is not equal to zero.
443 int isl_aff_plain_is_zero(__isl_keep isl_aff *aff)
445 if (!aff)
446 return -1;
448 if (isl_int_is_zero(aff->v->el[0]))
449 return 0;
450 return isl_seq_first_non_zero(aff->v->el + 1, aff->v->size - 1) < 0;
453 /* Does "aff" represent NaN?
455 int isl_aff_is_nan(__isl_keep isl_aff *aff)
457 if (!aff)
458 return -1;
460 return isl_seq_first_non_zero(aff->v->el, 2) < 0;
463 /* Does "pa" involve any NaNs?
465 int isl_pw_aff_involves_nan(__isl_keep isl_pw_aff *pa)
467 int i;
469 if (!pa)
470 return -1;
471 if (pa->n == 0)
472 return 0;
474 for (i = 0; i < pa->n; ++i) {
475 int is_nan = isl_aff_is_nan(pa->p[i].aff);
476 if (is_nan < 0 || is_nan)
477 return is_nan;
480 return 0;
483 /* Are "aff1" and "aff2" obviously equal?
485 * NaN is not equal to anything, not even to another NaN.
487 int isl_aff_plain_is_equal(__isl_keep isl_aff *aff1, __isl_keep isl_aff *aff2)
489 int equal;
491 if (!aff1 || !aff2)
492 return -1;
494 if (isl_aff_is_nan(aff1) || isl_aff_is_nan(aff2))
495 return 0;
497 equal = isl_local_space_is_equal(aff1->ls, aff2->ls);
498 if (equal < 0 || !equal)
499 return equal;
501 return isl_vec_is_equal(aff1->v, aff2->v);
504 /* Return the common denominator of "aff" in "v".
506 * We cannot return anything meaningful in case of a NaN.
508 int isl_aff_get_denominator(__isl_keep isl_aff *aff, isl_int *v)
510 if (!aff)
511 return -1;
512 if (isl_aff_is_nan(aff))
513 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
514 "cannot get denominator of NaN", return -1);
515 isl_int_set(*v, aff->v->el[0]);
516 return 0;
519 /* Return the common denominator of "aff".
521 __isl_give isl_val *isl_aff_get_denominator_val(__isl_keep isl_aff *aff)
523 isl_ctx *ctx;
525 if (!aff)
526 return NULL;
528 ctx = isl_aff_get_ctx(aff);
529 if (isl_aff_is_nan(aff))
530 return isl_val_nan(ctx);
531 return isl_val_int_from_isl_int(ctx, aff->v->el[0]);
534 /* Return the constant term of "aff" in "v".
536 * We cannot return anything meaningful in case of a NaN.
538 int isl_aff_get_constant(__isl_keep isl_aff *aff, isl_int *v)
540 if (!aff)
541 return -1;
542 if (isl_aff_is_nan(aff))
543 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
544 "cannot get constant term of NaN", return -1);
545 isl_int_set(*v, aff->v->el[1]);
546 return 0;
549 /* Return the constant term of "aff".
551 __isl_give isl_val *isl_aff_get_constant_val(__isl_keep isl_aff *aff)
553 isl_ctx *ctx;
554 isl_val *v;
556 if (!aff)
557 return NULL;
559 ctx = isl_aff_get_ctx(aff);
560 if (isl_aff_is_nan(aff))
561 return isl_val_nan(ctx);
562 v = isl_val_rat_from_isl_int(ctx, aff->v->el[1], aff->v->el[0]);
563 return isl_val_normalize(v);
566 /* Return the coefficient of the variable of type "type" at position "pos"
567 * of "aff" in "v".
569 * We cannot return anything meaningful in case of a NaN.
571 int isl_aff_get_coefficient(__isl_keep isl_aff *aff,
572 enum isl_dim_type type, int pos, isl_int *v)
574 if (!aff)
575 return -1;
577 if (type == isl_dim_out)
578 isl_die(aff->v->ctx, isl_error_invalid,
579 "output/set dimension does not have a coefficient",
580 return -1);
581 if (type == isl_dim_in)
582 type = isl_dim_set;
584 if (pos >= isl_local_space_dim(aff->ls, type))
585 isl_die(aff->v->ctx, isl_error_invalid,
586 "position out of bounds", return -1);
588 if (isl_aff_is_nan(aff))
589 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
590 "cannot get coefficient of NaN", return -1);
591 pos += isl_local_space_offset(aff->ls, type);
592 isl_int_set(*v, aff->v->el[1 + pos]);
594 return 0;
597 /* Return the coefficient of the variable of type "type" at position "pos"
598 * of "aff".
600 __isl_give isl_val *isl_aff_get_coefficient_val(__isl_keep isl_aff *aff,
601 enum isl_dim_type type, int pos)
603 isl_ctx *ctx;
604 isl_val *v;
606 if (!aff)
607 return NULL;
609 ctx = isl_aff_get_ctx(aff);
610 if (type == isl_dim_out)
611 isl_die(ctx, isl_error_invalid,
612 "output/set dimension does not have a coefficient",
613 return NULL);
614 if (type == isl_dim_in)
615 type = isl_dim_set;
617 if (pos >= isl_local_space_dim(aff->ls, type))
618 isl_die(ctx, isl_error_invalid,
619 "position out of bounds", return NULL);
621 if (isl_aff_is_nan(aff))
622 return isl_val_nan(ctx);
623 pos += isl_local_space_offset(aff->ls, type);
624 v = isl_val_rat_from_isl_int(ctx, aff->v->el[1 + pos], aff->v->el[0]);
625 return isl_val_normalize(v);
628 /* Replace the denominator of "aff" by "v".
630 * A NaN is unaffected by this operation.
632 __isl_give isl_aff *isl_aff_set_denominator(__isl_take isl_aff *aff, isl_int v)
634 if (!aff)
635 return NULL;
636 if (isl_aff_is_nan(aff))
637 return aff;
638 aff = isl_aff_cow(aff);
639 if (!aff)
640 return NULL;
642 aff->v = isl_vec_cow(aff->v);
643 if (!aff->v)
644 return isl_aff_free(aff);
646 isl_int_set(aff->v->el[0], v);
648 return aff;
651 /* Replace the numerator of the constant term of "aff" by "v".
653 * A NaN is unaffected by this operation.
655 __isl_give isl_aff *isl_aff_set_constant(__isl_take isl_aff *aff, isl_int v)
657 if (!aff)
658 return NULL;
659 if (isl_aff_is_nan(aff))
660 return aff;
661 aff = isl_aff_cow(aff);
662 if (!aff)
663 return NULL;
665 aff->v = isl_vec_cow(aff->v);
666 if (!aff->v)
667 return isl_aff_free(aff);
669 isl_int_set(aff->v->el[1], v);
671 return aff;
674 /* Replace the constant term of "aff" by "v".
676 * A NaN is unaffected by this operation.
678 __isl_give isl_aff *isl_aff_set_constant_val(__isl_take isl_aff *aff,
679 __isl_take isl_val *v)
681 if (!aff || !v)
682 goto error;
684 if (isl_aff_is_nan(aff)) {
685 isl_val_free(v);
686 return aff;
689 if (!isl_val_is_rat(v))
690 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
691 "expecting rational value", goto error);
693 if (isl_int_eq(aff->v->el[1], v->n) &&
694 isl_int_eq(aff->v->el[0], v->d)) {
695 isl_val_free(v);
696 return aff;
699 aff = isl_aff_cow(aff);
700 if (!aff)
701 goto error;
702 aff->v = isl_vec_cow(aff->v);
703 if (!aff->v)
704 goto error;
706 if (isl_int_eq(aff->v->el[0], v->d)) {
707 isl_int_set(aff->v->el[1], v->n);
708 } else if (isl_int_is_one(v->d)) {
709 isl_int_mul(aff->v->el[1], aff->v->el[0], v->n);
710 } else {
711 isl_seq_scale(aff->v->el + 1,
712 aff->v->el + 1, v->d, aff->v->size - 1);
713 isl_int_mul(aff->v->el[1], aff->v->el[0], v->n);
714 isl_int_mul(aff->v->el[0], aff->v->el[0], v->d);
715 aff->v = isl_vec_normalize(aff->v);
716 if (!aff->v)
717 goto error;
720 isl_val_free(v);
721 return aff;
722 error:
723 isl_aff_free(aff);
724 isl_val_free(v);
725 return NULL;
728 /* Add "v" to the constant term of "aff".
730 * A NaN is unaffected by this operation.
732 __isl_give isl_aff *isl_aff_add_constant(__isl_take isl_aff *aff, isl_int v)
734 if (isl_int_is_zero(v))
735 return aff;
737 if (!aff)
738 return NULL;
739 if (isl_aff_is_nan(aff))
740 return aff;
741 aff = isl_aff_cow(aff);
742 if (!aff)
743 return NULL;
745 aff->v = isl_vec_cow(aff->v);
746 if (!aff->v)
747 return isl_aff_free(aff);
749 isl_int_addmul(aff->v->el[1], aff->v->el[0], v);
751 return aff;
754 /* Add "v" to the constant term of "aff".
756 * A NaN is unaffected by this operation.
758 __isl_give isl_aff *isl_aff_add_constant_val(__isl_take isl_aff *aff,
759 __isl_take isl_val *v)
761 if (!aff || !v)
762 goto error;
764 if (isl_aff_is_nan(aff) || isl_val_is_zero(v)) {
765 isl_val_free(v);
766 return aff;
769 if (!isl_val_is_rat(v))
770 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
771 "expecting rational value", goto error);
773 aff = isl_aff_cow(aff);
774 if (!aff)
775 goto error;
777 aff->v = isl_vec_cow(aff->v);
778 if (!aff->v)
779 goto error;
781 if (isl_int_is_one(v->d)) {
782 isl_int_addmul(aff->v->el[1], aff->v->el[0], v->n);
783 } else if (isl_int_eq(aff->v->el[0], v->d)) {
784 isl_int_add(aff->v->el[1], aff->v->el[1], v->n);
785 aff->v = isl_vec_normalize(aff->v);
786 if (!aff->v)
787 goto error;
788 } else {
789 isl_seq_scale(aff->v->el + 1,
790 aff->v->el + 1, v->d, aff->v->size - 1);
791 isl_int_addmul(aff->v->el[1], aff->v->el[0], v->n);
792 isl_int_mul(aff->v->el[0], aff->v->el[0], v->d);
793 aff->v = isl_vec_normalize(aff->v);
794 if (!aff->v)
795 goto error;
798 isl_val_free(v);
799 return aff;
800 error:
801 isl_aff_free(aff);
802 isl_val_free(v);
803 return NULL;
806 __isl_give isl_aff *isl_aff_add_constant_si(__isl_take isl_aff *aff, int v)
808 isl_int t;
810 isl_int_init(t);
811 isl_int_set_si(t, v);
812 aff = isl_aff_add_constant(aff, t);
813 isl_int_clear(t);
815 return aff;
818 /* Add "v" to the numerator of the constant term of "aff".
820 * A NaN is unaffected by this operation.
822 __isl_give isl_aff *isl_aff_add_constant_num(__isl_take isl_aff *aff, isl_int v)
824 if (isl_int_is_zero(v))
825 return aff;
827 if (!aff)
828 return NULL;
829 if (isl_aff_is_nan(aff))
830 return aff;
831 aff = isl_aff_cow(aff);
832 if (!aff)
833 return NULL;
835 aff->v = isl_vec_cow(aff->v);
836 if (!aff->v)
837 return isl_aff_free(aff);
839 isl_int_add(aff->v->el[1], aff->v->el[1], v);
841 return aff;
844 /* Add "v" to the numerator of the constant term of "aff".
846 * A NaN is unaffected by this operation.
848 __isl_give isl_aff *isl_aff_add_constant_num_si(__isl_take isl_aff *aff, int v)
850 isl_int t;
852 if (v == 0)
853 return aff;
855 isl_int_init(t);
856 isl_int_set_si(t, v);
857 aff = isl_aff_add_constant_num(aff, t);
858 isl_int_clear(t);
860 return aff;
863 /* Replace the numerator of the constant term of "aff" by "v".
865 * A NaN is unaffected by this operation.
867 __isl_give isl_aff *isl_aff_set_constant_si(__isl_take isl_aff *aff, int v)
869 if (!aff)
870 return NULL;
871 if (isl_aff_is_nan(aff))
872 return aff;
873 aff = isl_aff_cow(aff);
874 if (!aff)
875 return NULL;
877 aff->v = isl_vec_cow(aff->v);
878 if (!aff->v)
879 return isl_aff_free(aff);
881 isl_int_set_si(aff->v->el[1], v);
883 return aff;
886 /* Replace the numerator of the coefficient of the variable of type "type"
887 * at position "pos" of "aff" by "v".
889 * A NaN is unaffected by this operation.
891 __isl_give isl_aff *isl_aff_set_coefficient(__isl_take isl_aff *aff,
892 enum isl_dim_type type, int pos, isl_int v)
894 if (!aff)
895 return NULL;
897 if (type == isl_dim_out)
898 isl_die(aff->v->ctx, isl_error_invalid,
899 "output/set dimension does not have a coefficient",
900 return isl_aff_free(aff));
901 if (type == isl_dim_in)
902 type = isl_dim_set;
904 if (pos >= isl_local_space_dim(aff->ls, type))
905 isl_die(aff->v->ctx, isl_error_invalid,
906 "position out of bounds", return isl_aff_free(aff));
908 if (isl_aff_is_nan(aff))
909 return aff;
910 aff = isl_aff_cow(aff);
911 if (!aff)
912 return NULL;
914 aff->v = isl_vec_cow(aff->v);
915 if (!aff->v)
916 return isl_aff_free(aff);
918 pos += isl_local_space_offset(aff->ls, type);
919 isl_int_set(aff->v->el[1 + pos], v);
921 return aff;
924 /* Replace the numerator of the coefficient of the variable of type "type"
925 * at position "pos" of "aff" by "v".
927 * A NaN is unaffected by this operation.
929 __isl_give isl_aff *isl_aff_set_coefficient_si(__isl_take isl_aff *aff,
930 enum isl_dim_type type, int pos, int v)
932 if (!aff)
933 return NULL;
935 if (type == isl_dim_out)
936 isl_die(aff->v->ctx, isl_error_invalid,
937 "output/set dimension does not have a coefficient",
938 return isl_aff_free(aff));
939 if (type == isl_dim_in)
940 type = isl_dim_set;
942 if (pos < 0 || pos >= isl_local_space_dim(aff->ls, type))
943 isl_die(aff->v->ctx, isl_error_invalid,
944 "position out of bounds", return isl_aff_free(aff));
946 if (isl_aff_is_nan(aff))
947 return aff;
948 pos += isl_local_space_offset(aff->ls, type);
949 if (isl_int_cmp_si(aff->v->el[1 + pos], v) == 0)
950 return aff;
952 aff = isl_aff_cow(aff);
953 if (!aff)
954 return NULL;
956 aff->v = isl_vec_cow(aff->v);
957 if (!aff->v)
958 return isl_aff_free(aff);
960 isl_int_set_si(aff->v->el[1 + pos], v);
962 return aff;
965 /* Replace the coefficient of the variable of type "type" at position "pos"
966 * of "aff" by "v".
968 * A NaN is unaffected by this operation.
970 __isl_give isl_aff *isl_aff_set_coefficient_val(__isl_take isl_aff *aff,
971 enum isl_dim_type type, int pos, __isl_take isl_val *v)
973 if (!aff || !v)
974 goto error;
976 if (type == isl_dim_out)
977 isl_die(aff->v->ctx, isl_error_invalid,
978 "output/set dimension does not have a coefficient",
979 goto error);
980 if (type == isl_dim_in)
981 type = isl_dim_set;
983 if (pos >= isl_local_space_dim(aff->ls, type))
984 isl_die(aff->v->ctx, isl_error_invalid,
985 "position out of bounds", goto error);
987 if (isl_aff_is_nan(aff)) {
988 isl_val_free(v);
989 return aff;
991 if (!isl_val_is_rat(v))
992 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
993 "expecting rational value", goto error);
995 pos += isl_local_space_offset(aff->ls, type);
996 if (isl_int_eq(aff->v->el[1 + pos], v->n) &&
997 isl_int_eq(aff->v->el[0], v->d)) {
998 isl_val_free(v);
999 return aff;
1002 aff = isl_aff_cow(aff);
1003 if (!aff)
1004 goto error;
1005 aff->v = isl_vec_cow(aff->v);
1006 if (!aff->v)
1007 goto error;
1009 if (isl_int_eq(aff->v->el[0], v->d)) {
1010 isl_int_set(aff->v->el[1 + pos], v->n);
1011 } else if (isl_int_is_one(v->d)) {
1012 isl_int_mul(aff->v->el[1 + pos], aff->v->el[0], v->n);
1013 } else {
1014 isl_seq_scale(aff->v->el + 1,
1015 aff->v->el + 1, v->d, aff->v->size - 1);
1016 isl_int_mul(aff->v->el[1 + pos], aff->v->el[0], v->n);
1017 isl_int_mul(aff->v->el[0], aff->v->el[0], v->d);
1018 aff->v = isl_vec_normalize(aff->v);
1019 if (!aff->v)
1020 goto error;
1023 isl_val_free(v);
1024 return aff;
1025 error:
1026 isl_aff_free(aff);
1027 isl_val_free(v);
1028 return NULL;
1031 /* Add "v" to the coefficient of the variable of type "type"
1032 * at position "pos" of "aff".
1034 * A NaN is unaffected by this operation.
1036 __isl_give isl_aff *isl_aff_add_coefficient(__isl_take isl_aff *aff,
1037 enum isl_dim_type type, int pos, isl_int v)
1039 if (!aff)
1040 return NULL;
1042 if (type == isl_dim_out)
1043 isl_die(aff->v->ctx, isl_error_invalid,
1044 "output/set dimension does not have a coefficient",
1045 return isl_aff_free(aff));
1046 if (type == isl_dim_in)
1047 type = isl_dim_set;
1049 if (pos >= isl_local_space_dim(aff->ls, type))
1050 isl_die(aff->v->ctx, isl_error_invalid,
1051 "position out of bounds", return isl_aff_free(aff));
1053 if (isl_aff_is_nan(aff))
1054 return aff;
1055 aff = isl_aff_cow(aff);
1056 if (!aff)
1057 return NULL;
1059 aff->v = isl_vec_cow(aff->v);
1060 if (!aff->v)
1061 return isl_aff_free(aff);
1063 pos += isl_local_space_offset(aff->ls, type);
1064 isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v);
1066 return aff;
1069 /* Add "v" to the coefficient of the variable of type "type"
1070 * at position "pos" of "aff".
1072 * A NaN is unaffected by this operation.
1074 __isl_give isl_aff *isl_aff_add_coefficient_val(__isl_take isl_aff *aff,
1075 enum isl_dim_type type, int pos, __isl_take isl_val *v)
1077 if (!aff || !v)
1078 goto error;
1080 if (isl_val_is_zero(v)) {
1081 isl_val_free(v);
1082 return aff;
1085 if (type == isl_dim_out)
1086 isl_die(aff->v->ctx, isl_error_invalid,
1087 "output/set dimension does not have a coefficient",
1088 goto error);
1089 if (type == isl_dim_in)
1090 type = isl_dim_set;
1092 if (pos >= isl_local_space_dim(aff->ls, type))
1093 isl_die(aff->v->ctx, isl_error_invalid,
1094 "position out of bounds", goto error);
1096 if (isl_aff_is_nan(aff)) {
1097 isl_val_free(v);
1098 return aff;
1100 if (!isl_val_is_rat(v))
1101 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
1102 "expecting rational value", goto error);
1104 aff = isl_aff_cow(aff);
1105 if (!aff)
1106 goto error;
1108 aff->v = isl_vec_cow(aff->v);
1109 if (!aff->v)
1110 goto error;
1112 pos += isl_local_space_offset(aff->ls, type);
1113 if (isl_int_is_one(v->d)) {
1114 isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v->n);
1115 } else if (isl_int_eq(aff->v->el[0], v->d)) {
1116 isl_int_add(aff->v->el[1 + pos], aff->v->el[1 + pos], v->n);
1117 aff->v = isl_vec_normalize(aff->v);
1118 if (!aff->v)
1119 goto error;
1120 } else {
1121 isl_seq_scale(aff->v->el + 1,
1122 aff->v->el + 1, v->d, aff->v->size - 1);
1123 isl_int_addmul(aff->v->el[1 + pos], aff->v->el[0], v->n);
1124 isl_int_mul(aff->v->el[0], aff->v->el[0], v->d);
1125 aff->v = isl_vec_normalize(aff->v);
1126 if (!aff->v)
1127 goto error;
1130 isl_val_free(v);
1131 return aff;
1132 error:
1133 isl_aff_free(aff);
1134 isl_val_free(v);
1135 return NULL;
1138 __isl_give isl_aff *isl_aff_add_coefficient_si(__isl_take isl_aff *aff,
1139 enum isl_dim_type type, int pos, int v)
1141 isl_int t;
1143 isl_int_init(t);
1144 isl_int_set_si(t, v);
1145 aff = isl_aff_add_coefficient(aff, type, pos, t);
1146 isl_int_clear(t);
1148 return aff;
1151 __isl_give isl_aff *isl_aff_get_div(__isl_keep isl_aff *aff, int pos)
1153 if (!aff)
1154 return NULL;
1156 return isl_local_space_get_div(aff->ls, pos);
1159 /* Return the negation of "aff".
1161 * As a special case, -NaN = NaN.
1163 __isl_give isl_aff *isl_aff_neg(__isl_take isl_aff *aff)
1165 if (!aff)
1166 return NULL;
1167 if (isl_aff_is_nan(aff))
1168 return aff;
1169 aff = isl_aff_cow(aff);
1170 if (!aff)
1171 return NULL;
1172 aff->v = isl_vec_cow(aff->v);
1173 if (!aff->v)
1174 return isl_aff_free(aff);
1176 isl_seq_neg(aff->v->el + 1, aff->v->el + 1, aff->v->size - 1);
1178 return aff;
1181 /* Remove divs from the local space that do not appear in the affine
1182 * expression.
1183 * We currently only remove divs at the end.
1184 * Some intermediate divs may also not appear directly in the affine
1185 * expression, but we would also need to check that no other divs are
1186 * defined in terms of them.
1188 __isl_give isl_aff *isl_aff_remove_unused_divs( __isl_take isl_aff *aff)
1190 int pos;
1191 int off;
1192 int n;
1194 if (!aff)
1195 return NULL;
1197 n = isl_local_space_dim(aff->ls, isl_dim_div);
1198 off = isl_local_space_offset(aff->ls, isl_dim_div);
1200 pos = isl_seq_last_non_zero(aff->v->el + 1 + off, n) + 1;
1201 if (pos == n)
1202 return aff;
1204 aff = isl_aff_cow(aff);
1205 if (!aff)
1206 return NULL;
1208 aff->ls = isl_local_space_drop_dims(aff->ls, isl_dim_div, pos, n - pos);
1209 aff->v = isl_vec_drop_els(aff->v, 1 + off + pos, n - pos);
1210 if (!aff->ls || !aff->v)
1211 return isl_aff_free(aff);
1213 return aff;
1216 /* Given two affine expressions "p" of length p_len (including the
1217 * denominator and the constant term) and "subs" of length subs_len,
1218 * plug in "subs" for the variable at position "pos".
1219 * The variables of "subs" and "p" are assumed to match up to subs_len,
1220 * but "p" may have additional variables.
1221 * "v" is an initialized isl_int that can be used internally.
1223 * In particular, if "p" represents the expression
1225 * (a i + g)/m
1227 * with i the variable at position "pos" and "subs" represents the expression
1229 * f/d
1231 * then the result represents the expression
1233 * (a f + d g)/(m d)
1236 void isl_seq_substitute(isl_int *p, int pos, isl_int *subs,
1237 int p_len, int subs_len, isl_int v)
1239 isl_int_set(v, p[1 + pos]);
1240 isl_int_set_si(p[1 + pos], 0);
1241 isl_seq_combine(p + 1, subs[0], p + 1, v, subs + 1, subs_len - 1);
1242 isl_seq_scale(p + subs_len, p + subs_len, subs[0], p_len - subs_len);
1243 isl_int_mul(p[0], p[0], subs[0]);
1246 /* Look for any divs in the aff->ls with a denominator equal to one
1247 * and plug them into the affine expression and any subsequent divs
1248 * that may reference the div.
1250 static __isl_give isl_aff *plug_in_integral_divs(__isl_take isl_aff *aff)
1252 int i, n;
1253 int len;
1254 isl_int v;
1255 isl_vec *vec;
1256 isl_local_space *ls;
1257 unsigned pos;
1259 if (!aff)
1260 return NULL;
1262 n = isl_local_space_dim(aff->ls, isl_dim_div);
1263 len = aff->v->size;
1264 for (i = 0; i < n; ++i) {
1265 if (!isl_int_is_one(aff->ls->div->row[i][0]))
1266 continue;
1267 ls = isl_local_space_copy(aff->ls);
1268 ls = isl_local_space_substitute_seq(ls, isl_dim_div, i,
1269 aff->ls->div->row[i], len, i + 1, n - (i + 1));
1270 vec = isl_vec_copy(aff->v);
1271 vec = isl_vec_cow(vec);
1272 if (!ls || !vec)
1273 goto error;
1275 isl_int_init(v);
1277 pos = isl_local_space_offset(aff->ls, isl_dim_div) + i;
1278 isl_seq_substitute(vec->el, pos, aff->ls->div->row[i],
1279 len, len, v);
1281 isl_int_clear(v);
1283 isl_vec_free(aff->v);
1284 aff->v = vec;
1285 isl_local_space_free(aff->ls);
1286 aff->ls = ls;
1289 return aff;
1290 error:
1291 isl_vec_free(vec);
1292 isl_local_space_free(ls);
1293 return isl_aff_free(aff);
1296 /* Look for any divs j that appear with a unit coefficient inside
1297 * the definitions of other divs i and plug them into the definitions
1298 * of the divs i.
1300 * In particular, an expression of the form
1302 * floor((f(..) + floor(g(..)/n))/m)
1304 * is simplified to
1306 * floor((n * f(..) + g(..))/(n * m))
1308 * This simplification is correct because we can move the expression
1309 * f(..) into the inner floor in the original expression to obtain
1311 * floor(floor((n * f(..) + g(..))/n)/m)
1313 * from which we can derive the simplified expression.
1315 static __isl_give isl_aff *plug_in_unit_divs(__isl_take isl_aff *aff)
1317 int i, j, n;
1318 int off;
1320 if (!aff)
1321 return NULL;
1323 n = isl_local_space_dim(aff->ls, isl_dim_div);
1324 off = isl_local_space_offset(aff->ls, isl_dim_div);
1325 for (i = 1; i < n; ++i) {
1326 for (j = 0; j < i; ++j) {
1327 if (!isl_int_is_one(aff->ls->div->row[i][1 + off + j]))
1328 continue;
1329 aff->ls = isl_local_space_substitute_seq(aff->ls,
1330 isl_dim_div, j, aff->ls->div->row[j],
1331 aff->v->size, i, 1);
1332 if (!aff->ls)
1333 return isl_aff_free(aff);
1337 return aff;
1340 /* Swap divs "a" and "b" in "aff", which is assumed to be non-NULL.
1342 * Even though this function is only called on isl_affs with a single
1343 * reference, we are careful to only change aff->v and aff->ls together.
1345 static __isl_give isl_aff *swap_div(__isl_take isl_aff *aff, int a, int b)
1347 unsigned off = isl_local_space_offset(aff->ls, isl_dim_div);
1348 isl_local_space *ls;
1349 isl_vec *v;
1351 ls = isl_local_space_copy(aff->ls);
1352 ls = isl_local_space_swap_div(ls, a, b);
1353 v = isl_vec_copy(aff->v);
1354 v = isl_vec_cow(v);
1355 if (!ls || !v)
1356 goto error;
1358 isl_int_swap(v->el[1 + off + a], v->el[1 + off + b]);
1359 isl_vec_free(aff->v);
1360 aff->v = v;
1361 isl_local_space_free(aff->ls);
1362 aff->ls = ls;
1364 return aff;
1365 error:
1366 isl_vec_free(v);
1367 isl_local_space_free(ls);
1368 return isl_aff_free(aff);
1371 /* Merge divs "a" and "b" in "aff", which is assumed to be non-NULL.
1373 * We currently do not actually remove div "b", but simply add its
1374 * coefficient to that of "a" and then zero it out.
1376 static __isl_give isl_aff *merge_divs(__isl_take isl_aff *aff, int a, int b)
1378 unsigned off = isl_local_space_offset(aff->ls, isl_dim_div);
1380 if (isl_int_is_zero(aff->v->el[1 + off + b]))
1381 return aff;
1383 aff->v = isl_vec_cow(aff->v);
1384 if (!aff->v)
1385 return isl_aff_free(aff);
1387 isl_int_add(aff->v->el[1 + off + a],
1388 aff->v->el[1 + off + a], aff->v->el[1 + off + b]);
1389 isl_int_set_si(aff->v->el[1 + off + b], 0);
1391 return aff;
1394 /* Sort the divs in the local space of "aff" according to
1395 * the comparison function "cmp_row" in isl_local_space.c,
1396 * combining the coefficients of identical divs.
1398 * Reordering divs does not change the semantics of "aff",
1399 * so there is no need to call isl_aff_cow.
1400 * Moreover, this function is currently only called on isl_affs
1401 * with a single reference.
1403 static __isl_give isl_aff *sort_divs(__isl_take isl_aff *aff)
1405 int i, j, n;
1406 unsigned off;
1408 if (!aff)
1409 return NULL;
1411 off = isl_local_space_offset(aff->ls, isl_dim_div);
1412 n = isl_aff_dim(aff, isl_dim_div);
1413 for (i = 1; i < n; ++i) {
1414 for (j = i - 1; j >= 0; --j) {
1415 int cmp = isl_mat_cmp_div(aff->ls->div, j, j + 1);
1416 if (cmp < 0)
1417 break;
1418 if (cmp == 0)
1419 aff = merge_divs(aff, j, j + 1);
1420 else
1421 aff = swap_div(aff, j, j + 1);
1422 if (!aff)
1423 return NULL;
1427 return aff;
1430 /* Normalize the representation of "aff".
1432 * This function should only be called of "new" isl_affs, i.e.,
1433 * with only a single reference. We therefore do not need to
1434 * worry about affecting other instances.
1436 __isl_give isl_aff *isl_aff_normalize(__isl_take isl_aff *aff)
1438 if (!aff)
1439 return NULL;
1440 aff->v = isl_vec_normalize(aff->v);
1441 if (!aff->v)
1442 return isl_aff_free(aff);
1443 aff = plug_in_integral_divs(aff);
1444 aff = plug_in_unit_divs(aff);
1445 aff = sort_divs(aff);
1446 aff = isl_aff_remove_unused_divs(aff);
1447 return aff;
1450 /* Given f, return floor(f).
1451 * If f is an integer expression, then just return f.
1452 * If f is a constant, then return the constant floor(f).
1453 * Otherwise, if f = g/m, write g = q m + r,
1454 * create a new div d = [r/m] and return the expression q + d.
1455 * The coefficients in r are taken to lie between -m/2 and m/2.
1457 * As a special case, floor(NaN) = NaN.
1459 __isl_give isl_aff *isl_aff_floor(__isl_take isl_aff *aff)
1461 int i;
1462 int size;
1463 isl_ctx *ctx;
1464 isl_vec *div;
1466 if (!aff)
1467 return NULL;
1469 if (isl_aff_is_nan(aff))
1470 return aff;
1471 if (isl_int_is_one(aff->v->el[0]))
1472 return aff;
1474 aff = isl_aff_cow(aff);
1475 if (!aff)
1476 return NULL;
1478 aff->v = isl_vec_cow(aff->v);
1479 if (!aff->v)
1480 return isl_aff_free(aff);
1482 if (isl_aff_is_cst(aff)) {
1483 isl_int_fdiv_q(aff->v->el[1], aff->v->el[1], aff->v->el[0]);
1484 isl_int_set_si(aff->v->el[0], 1);
1485 return aff;
1488 div = isl_vec_copy(aff->v);
1489 div = isl_vec_cow(div);
1490 if (!div)
1491 return isl_aff_free(aff);
1493 ctx = isl_aff_get_ctx(aff);
1494 isl_int_fdiv_q(aff->v->el[0], aff->v->el[0], ctx->two);
1495 for (i = 1; i < aff->v->size; ++i) {
1496 isl_int_fdiv_r(div->el[i], div->el[i], div->el[0]);
1497 isl_int_fdiv_q(aff->v->el[i], aff->v->el[i], div->el[0]);
1498 if (isl_int_gt(div->el[i], aff->v->el[0])) {
1499 isl_int_sub(div->el[i], div->el[i], div->el[0]);
1500 isl_int_add_ui(aff->v->el[i], aff->v->el[i], 1);
1504 aff->ls = isl_local_space_add_div(aff->ls, div);
1505 if (!aff->ls)
1506 return isl_aff_free(aff);
1508 size = aff->v->size;
1509 aff->v = isl_vec_extend(aff->v, size + 1);
1510 if (!aff->v)
1511 return isl_aff_free(aff);
1512 isl_int_set_si(aff->v->el[0], 1);
1513 isl_int_set_si(aff->v->el[size], 1);
1515 aff = isl_aff_normalize(aff);
1517 return aff;
1520 /* Compute
1522 * aff mod m = aff - m * floor(aff/m)
1524 __isl_give isl_aff *isl_aff_mod(__isl_take isl_aff *aff, isl_int m)
1526 isl_aff *res;
1528 res = isl_aff_copy(aff);
1529 aff = isl_aff_scale_down(aff, m);
1530 aff = isl_aff_floor(aff);
1531 aff = isl_aff_scale(aff, m);
1532 res = isl_aff_sub(res, aff);
1534 return res;
1537 /* Compute
1539 * aff mod m = aff - m * floor(aff/m)
1541 * with m an integer value.
1543 __isl_give isl_aff *isl_aff_mod_val(__isl_take isl_aff *aff,
1544 __isl_take isl_val *m)
1546 isl_aff *res;
1548 if (!aff || !m)
1549 goto error;
1551 if (!isl_val_is_int(m))
1552 isl_die(isl_val_get_ctx(m), isl_error_invalid,
1553 "expecting integer modulo", goto error);
1555 res = isl_aff_copy(aff);
1556 aff = isl_aff_scale_down_val(aff, isl_val_copy(m));
1557 aff = isl_aff_floor(aff);
1558 aff = isl_aff_scale_val(aff, m);
1559 res = isl_aff_sub(res, aff);
1561 return res;
1562 error:
1563 isl_aff_free(aff);
1564 isl_val_free(m);
1565 return NULL;
1568 /* Compute
1570 * pwaff mod m = pwaff - m * floor(pwaff/m)
1572 __isl_give isl_pw_aff *isl_pw_aff_mod(__isl_take isl_pw_aff *pwaff, isl_int m)
1574 isl_pw_aff *res;
1576 res = isl_pw_aff_copy(pwaff);
1577 pwaff = isl_pw_aff_scale_down(pwaff, m);
1578 pwaff = isl_pw_aff_floor(pwaff);
1579 pwaff = isl_pw_aff_scale(pwaff, m);
1580 res = isl_pw_aff_sub(res, pwaff);
1582 return res;
1585 /* Compute
1587 * pa mod m = pa - m * floor(pa/m)
1589 * with m an integer value.
1591 __isl_give isl_pw_aff *isl_pw_aff_mod_val(__isl_take isl_pw_aff *pa,
1592 __isl_take isl_val *m)
1594 if (!pa || !m)
1595 goto error;
1596 if (!isl_val_is_int(m))
1597 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
1598 "expecting integer modulo", goto error);
1599 pa = isl_pw_aff_mod(pa, m->n);
1600 isl_val_free(m);
1601 return pa;
1602 error:
1603 isl_pw_aff_free(pa);
1604 isl_val_free(m);
1605 return NULL;
1608 /* Given f, return ceil(f).
1609 * If f is an integer expression, then just return f.
1610 * Otherwise, let f be the expression
1612 * e/m
1614 * then return
1616 * floor((e + m - 1)/m)
1618 * As a special case, ceil(NaN) = NaN.
1620 __isl_give isl_aff *isl_aff_ceil(__isl_take isl_aff *aff)
1622 if (!aff)
1623 return NULL;
1625 if (isl_aff_is_nan(aff))
1626 return aff;
1627 if (isl_int_is_one(aff->v->el[0]))
1628 return aff;
1630 aff = isl_aff_cow(aff);
1631 if (!aff)
1632 return NULL;
1633 aff->v = isl_vec_cow(aff->v);
1634 if (!aff->v)
1635 return isl_aff_free(aff);
1637 isl_int_add(aff->v->el[1], aff->v->el[1], aff->v->el[0]);
1638 isl_int_sub_ui(aff->v->el[1], aff->v->el[1], 1);
1639 aff = isl_aff_floor(aff);
1641 return aff;
1644 /* Apply the expansion computed by isl_merge_divs.
1645 * The expansion itself is given by "exp" while the resulting
1646 * list of divs is given by "div".
1648 __isl_give isl_aff *isl_aff_expand_divs( __isl_take isl_aff *aff,
1649 __isl_take isl_mat *div, int *exp)
1651 int i, j;
1652 int old_n_div;
1653 int new_n_div;
1654 int offset;
1656 aff = isl_aff_cow(aff);
1657 if (!aff || !div)
1658 goto error;
1660 old_n_div = isl_local_space_dim(aff->ls, isl_dim_div);
1661 new_n_div = isl_mat_rows(div);
1662 if (new_n_div < old_n_div)
1663 isl_die(isl_mat_get_ctx(div), isl_error_invalid,
1664 "not an expansion", goto error);
1666 aff->v = isl_vec_extend(aff->v, aff->v->size + new_n_div - old_n_div);
1667 if (!aff->v)
1668 goto error;
1670 offset = 1 + isl_local_space_offset(aff->ls, isl_dim_div);
1671 j = old_n_div - 1;
1672 for (i = new_n_div - 1; i >= 0; --i) {
1673 if (j >= 0 && exp[j] == i) {
1674 if (i != j)
1675 isl_int_swap(aff->v->el[offset + i],
1676 aff->v->el[offset + j]);
1677 j--;
1678 } else
1679 isl_int_set_si(aff->v->el[offset + i], 0);
1682 aff->ls = isl_local_space_replace_divs(aff->ls, isl_mat_copy(div));
1683 if (!aff->ls)
1684 goto error;
1685 isl_mat_free(div);
1686 return aff;
1687 error:
1688 isl_aff_free(aff);
1689 isl_mat_free(div);
1690 return NULL;
1693 /* Add two affine expressions that live in the same local space.
1695 static __isl_give isl_aff *add_expanded(__isl_take isl_aff *aff1,
1696 __isl_take isl_aff *aff2)
1698 isl_int gcd, f;
1700 aff1 = isl_aff_cow(aff1);
1701 if (!aff1 || !aff2)
1702 goto error;
1704 aff1->v = isl_vec_cow(aff1->v);
1705 if (!aff1->v)
1706 goto error;
1708 isl_int_init(gcd);
1709 isl_int_init(f);
1710 isl_int_gcd(gcd, aff1->v->el[0], aff2->v->el[0]);
1711 isl_int_divexact(f, aff2->v->el[0], gcd);
1712 isl_seq_scale(aff1->v->el + 1, aff1->v->el + 1, f, aff1->v->size - 1);
1713 isl_int_divexact(f, aff1->v->el[0], gcd);
1714 isl_seq_addmul(aff1->v->el + 1, f, aff2->v->el + 1, aff1->v->size - 1);
1715 isl_int_divexact(f, aff2->v->el[0], gcd);
1716 isl_int_mul(aff1->v->el[0], aff1->v->el[0], f);
1717 isl_int_clear(f);
1718 isl_int_clear(gcd);
1720 isl_aff_free(aff2);
1721 return aff1;
1722 error:
1723 isl_aff_free(aff1);
1724 isl_aff_free(aff2);
1725 return NULL;
1728 /* Return the sum of "aff1" and "aff2".
1730 * If either of the two is NaN, then the result is NaN.
1732 __isl_give isl_aff *isl_aff_add(__isl_take isl_aff *aff1,
1733 __isl_take isl_aff *aff2)
1735 isl_ctx *ctx;
1736 int *exp1 = NULL;
1737 int *exp2 = NULL;
1738 isl_mat *div;
1739 int n_div1, n_div2;
1741 if (!aff1 || !aff2)
1742 goto error;
1744 ctx = isl_aff_get_ctx(aff1);
1745 if (!isl_space_is_equal(aff1->ls->dim, aff2->ls->dim))
1746 isl_die(ctx, isl_error_invalid,
1747 "spaces don't match", goto error);
1749 if (isl_aff_is_nan(aff1)) {
1750 isl_aff_free(aff2);
1751 return aff1;
1753 if (isl_aff_is_nan(aff2)) {
1754 isl_aff_free(aff1);
1755 return aff2;
1758 n_div1 = isl_aff_dim(aff1, isl_dim_div);
1759 n_div2 = isl_aff_dim(aff2, isl_dim_div);
1760 if (n_div1 == 0 && n_div2 == 0)
1761 return add_expanded(aff1, aff2);
1763 exp1 = isl_alloc_array(ctx, int, n_div1);
1764 exp2 = isl_alloc_array(ctx, int, n_div2);
1765 if ((n_div1 && !exp1) || (n_div2 && !exp2))
1766 goto error;
1768 div = isl_merge_divs(aff1->ls->div, aff2->ls->div, exp1, exp2);
1769 aff1 = isl_aff_expand_divs(aff1, isl_mat_copy(div), exp1);
1770 aff2 = isl_aff_expand_divs(aff2, div, exp2);
1771 free(exp1);
1772 free(exp2);
1774 return add_expanded(aff1, aff2);
1775 error:
1776 free(exp1);
1777 free(exp2);
1778 isl_aff_free(aff1);
1779 isl_aff_free(aff2);
1780 return NULL;
1783 __isl_give isl_aff *isl_aff_sub(__isl_take isl_aff *aff1,
1784 __isl_take isl_aff *aff2)
1786 return isl_aff_add(aff1, isl_aff_neg(aff2));
1789 /* Return the result of scaling "aff" by a factor of "f".
1791 * As a special case, f * NaN = NaN.
1793 __isl_give isl_aff *isl_aff_scale(__isl_take isl_aff *aff, isl_int f)
1795 isl_int gcd;
1797 if (!aff)
1798 return NULL;
1799 if (isl_aff_is_nan(aff))
1800 return aff;
1802 if (isl_int_is_one(f))
1803 return aff;
1805 aff = isl_aff_cow(aff);
1806 if (!aff)
1807 return NULL;
1808 aff->v = isl_vec_cow(aff->v);
1809 if (!aff->v)
1810 return isl_aff_free(aff);
1812 if (isl_int_is_pos(f) && isl_int_is_divisible_by(aff->v->el[0], f)) {
1813 isl_int_divexact(aff->v->el[0], aff->v->el[0], f);
1814 return aff;
1817 isl_int_init(gcd);
1818 isl_int_gcd(gcd, aff->v->el[0], f);
1819 isl_int_divexact(aff->v->el[0], aff->v->el[0], gcd);
1820 isl_int_divexact(gcd, f, gcd);
1821 isl_seq_scale(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
1822 isl_int_clear(gcd);
1824 return aff;
1827 /* Multiple "aff" by "v".
1829 __isl_give isl_aff *isl_aff_scale_val(__isl_take isl_aff *aff,
1830 __isl_take isl_val *v)
1832 if (!aff || !v)
1833 goto error;
1835 if (isl_val_is_one(v)) {
1836 isl_val_free(v);
1837 return aff;
1840 if (!isl_val_is_rat(v))
1841 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
1842 "expecting rational factor", goto error);
1844 aff = isl_aff_scale(aff, v->n);
1845 aff = isl_aff_scale_down(aff, v->d);
1847 isl_val_free(v);
1848 return aff;
1849 error:
1850 isl_aff_free(aff);
1851 isl_val_free(v);
1852 return NULL;
1855 /* Return the result of scaling "aff" down by a factor of "f".
1857 * As a special case, NaN/f = NaN.
1859 __isl_give isl_aff *isl_aff_scale_down(__isl_take isl_aff *aff, isl_int f)
1861 isl_int gcd;
1863 if (!aff)
1864 return NULL;
1865 if (isl_aff_is_nan(aff))
1866 return aff;
1868 if (isl_int_is_one(f))
1869 return aff;
1871 aff = isl_aff_cow(aff);
1872 if (!aff)
1873 return NULL;
1875 if (isl_int_is_zero(f))
1876 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
1877 "cannot scale down by zero", return isl_aff_free(aff));
1879 aff->v = isl_vec_cow(aff->v);
1880 if (!aff->v)
1881 return isl_aff_free(aff);
1883 isl_int_init(gcd);
1884 isl_seq_gcd(aff->v->el + 1, aff->v->size - 1, &gcd);
1885 isl_int_gcd(gcd, gcd, f);
1886 isl_seq_scale_down(aff->v->el + 1, aff->v->el + 1, gcd, aff->v->size - 1);
1887 isl_int_divexact(gcd, f, gcd);
1888 isl_int_mul(aff->v->el[0], aff->v->el[0], gcd);
1889 isl_int_clear(gcd);
1891 return aff;
1894 /* Divide "aff" by "v".
1896 __isl_give isl_aff *isl_aff_scale_down_val(__isl_take isl_aff *aff,
1897 __isl_take isl_val *v)
1899 if (!aff || !v)
1900 goto error;
1902 if (isl_val_is_one(v)) {
1903 isl_val_free(v);
1904 return aff;
1907 if (!isl_val_is_rat(v))
1908 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
1909 "expecting rational factor", goto error);
1910 if (!isl_val_is_pos(v))
1911 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
1912 "factor needs to be positive", goto error);
1914 aff = isl_aff_scale(aff, v->d);
1915 aff = isl_aff_scale_down(aff, v->n);
1917 isl_val_free(v);
1918 return aff;
1919 error:
1920 isl_aff_free(aff);
1921 isl_val_free(v);
1922 return NULL;
1925 __isl_give isl_aff *isl_aff_scale_down_ui(__isl_take isl_aff *aff, unsigned f)
1927 isl_int v;
1929 if (f == 1)
1930 return aff;
1932 isl_int_init(v);
1933 isl_int_set_ui(v, f);
1934 aff = isl_aff_scale_down(aff, v);
1935 isl_int_clear(v);
1937 return aff;
1940 __isl_give isl_aff *isl_aff_set_dim_name(__isl_take isl_aff *aff,
1941 enum isl_dim_type type, unsigned pos, const char *s)
1943 aff = isl_aff_cow(aff);
1944 if (!aff)
1945 return NULL;
1946 if (type == isl_dim_out)
1947 isl_die(aff->v->ctx, isl_error_invalid,
1948 "cannot set name of output/set dimension",
1949 return isl_aff_free(aff));
1950 if (type == isl_dim_in)
1951 type = isl_dim_set;
1952 aff->ls = isl_local_space_set_dim_name(aff->ls, type, pos, s);
1953 if (!aff->ls)
1954 return isl_aff_free(aff);
1956 return aff;
1959 __isl_give isl_aff *isl_aff_set_dim_id(__isl_take isl_aff *aff,
1960 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
1962 aff = isl_aff_cow(aff);
1963 if (!aff)
1964 goto error;
1965 if (type == isl_dim_out)
1966 isl_die(aff->v->ctx, isl_error_invalid,
1967 "cannot set name of output/set dimension",
1968 goto error);
1969 if (type == isl_dim_in)
1970 type = isl_dim_set;
1971 aff->ls = isl_local_space_set_dim_id(aff->ls, type, pos, id);
1972 if (!aff->ls)
1973 return isl_aff_free(aff);
1975 return aff;
1976 error:
1977 isl_id_free(id);
1978 isl_aff_free(aff);
1979 return NULL;
1982 /* Replace the identifier of the input tuple of "aff" by "id".
1983 * type is currently required to be equal to isl_dim_in
1985 __isl_give isl_aff *isl_aff_set_tuple_id(__isl_take isl_aff *aff,
1986 enum isl_dim_type type, __isl_take isl_id *id)
1988 aff = isl_aff_cow(aff);
1989 if (!aff)
1990 goto error;
1991 if (type != isl_dim_out)
1992 isl_die(aff->v->ctx, isl_error_invalid,
1993 "cannot only set id of input tuple", goto error);
1994 aff->ls = isl_local_space_set_tuple_id(aff->ls, isl_dim_set, id);
1995 if (!aff->ls)
1996 return isl_aff_free(aff);
1998 return aff;
1999 error:
2000 isl_id_free(id);
2001 isl_aff_free(aff);
2002 return NULL;
2005 /* Exploit the equalities in "eq" to simplify the affine expression
2006 * and the expressions of the integer divisions in the local space.
2007 * The integer divisions in this local space are assumed to appear
2008 * as regular dimensions in "eq".
2010 static __isl_give isl_aff *isl_aff_substitute_equalities_lifted(
2011 __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
2013 int i, j;
2014 unsigned total;
2015 unsigned n_div;
2017 if (!eq)
2018 goto error;
2019 if (eq->n_eq == 0) {
2020 isl_basic_set_free(eq);
2021 return aff;
2024 aff = isl_aff_cow(aff);
2025 if (!aff)
2026 goto error;
2028 aff->ls = isl_local_space_substitute_equalities(aff->ls,
2029 isl_basic_set_copy(eq));
2030 aff->v = isl_vec_cow(aff->v);
2031 if (!aff->ls || !aff->v)
2032 goto error;
2034 total = 1 + isl_space_dim(eq->dim, isl_dim_all);
2035 n_div = eq->n_div;
2036 for (i = 0; i < eq->n_eq; ++i) {
2037 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
2038 if (j < 0 || j == 0 || j >= total)
2039 continue;
2041 isl_seq_elim(aff->v->el + 1, eq->eq[i], j, total,
2042 &aff->v->el[0]);
2045 isl_basic_set_free(eq);
2046 aff = isl_aff_normalize(aff);
2047 return aff;
2048 error:
2049 isl_basic_set_free(eq);
2050 isl_aff_free(aff);
2051 return NULL;
2054 /* Exploit the equalities in "eq" to simplify the affine expression
2055 * and the expressions of the integer divisions in the local space.
2057 static __isl_give isl_aff *isl_aff_substitute_equalities(
2058 __isl_take isl_aff *aff, __isl_take isl_basic_set *eq)
2060 int n_div;
2062 if (!aff || !eq)
2063 goto error;
2064 n_div = isl_local_space_dim(aff->ls, isl_dim_div);
2065 if (n_div > 0)
2066 eq = isl_basic_set_add_dims(eq, isl_dim_set, n_div);
2067 return isl_aff_substitute_equalities_lifted(aff, eq);
2068 error:
2069 isl_basic_set_free(eq);
2070 isl_aff_free(aff);
2071 return NULL;
2074 /* Look for equalities among the variables shared by context and aff
2075 * and the integer divisions of aff, if any.
2076 * The equalities are then used to eliminate coefficients and/or integer
2077 * divisions from aff.
2079 __isl_give isl_aff *isl_aff_gist(__isl_take isl_aff *aff,
2080 __isl_take isl_set *context)
2082 isl_basic_set *hull;
2083 int n_div;
2085 if (!aff)
2086 goto error;
2087 n_div = isl_local_space_dim(aff->ls, isl_dim_div);
2088 if (n_div > 0) {
2089 isl_basic_set *bset;
2090 isl_local_space *ls;
2091 context = isl_set_add_dims(context, isl_dim_set, n_div);
2092 ls = isl_aff_get_domain_local_space(aff);
2093 bset = isl_basic_set_from_local_space(ls);
2094 bset = isl_basic_set_lift(bset);
2095 bset = isl_basic_set_flatten(bset);
2096 context = isl_set_intersect(context,
2097 isl_set_from_basic_set(bset));
2100 hull = isl_set_affine_hull(context);
2101 return isl_aff_substitute_equalities_lifted(aff, hull);
2102 error:
2103 isl_aff_free(aff);
2104 isl_set_free(context);
2105 return NULL;
2108 __isl_give isl_aff *isl_aff_gist_params(__isl_take isl_aff *aff,
2109 __isl_take isl_set *context)
2111 isl_set *dom_context = isl_set_universe(isl_aff_get_domain_space(aff));
2112 dom_context = isl_set_intersect_params(dom_context, context);
2113 return isl_aff_gist(aff, dom_context);
2116 /* Return a basic set containing those elements in the space
2117 * of aff where it is non-negative.
2118 * If "rational" is set, then return a rational basic set.
2120 * If "aff" is NaN, then it is not non-negative (it's not negative either).
2122 static __isl_give isl_basic_set *aff_nonneg_basic_set(
2123 __isl_take isl_aff *aff, int rational)
2125 isl_constraint *ineq;
2126 isl_basic_set *bset;
2128 if (!aff)
2129 return NULL;
2130 if (isl_aff_is_nan(aff)) {
2131 isl_space *space = isl_aff_get_domain_space(aff);
2132 isl_aff_free(aff);
2133 return isl_basic_set_empty(space);
2136 ineq = isl_inequality_from_aff(aff);
2138 bset = isl_basic_set_from_constraint(ineq);
2139 if (rational)
2140 bset = isl_basic_set_set_rational(bset);
2141 bset = isl_basic_set_simplify(bset);
2142 return bset;
2145 /* Return a basic set containing those elements in the space
2146 * of aff where it is non-negative.
2148 __isl_give isl_basic_set *isl_aff_nonneg_basic_set(__isl_take isl_aff *aff)
2150 return aff_nonneg_basic_set(aff, 0);
2153 /* Return a basic set containing those elements in the domain space
2154 * of aff where it is negative.
2156 __isl_give isl_basic_set *isl_aff_neg_basic_set(__isl_take isl_aff *aff)
2158 aff = isl_aff_neg(aff);
2159 aff = isl_aff_add_constant_num_si(aff, -1);
2160 return isl_aff_nonneg_basic_set(aff);
2163 /* Return a basic set containing those elements in the space
2164 * of aff where it is zero.
2165 * If "rational" is set, then return a rational basic set.
2167 * If "aff" is NaN, then it is not zero.
2169 static __isl_give isl_basic_set *aff_zero_basic_set(__isl_take isl_aff *aff,
2170 int rational)
2172 isl_constraint *ineq;
2173 isl_basic_set *bset;
2175 if (!aff)
2176 return NULL;
2177 if (isl_aff_is_nan(aff)) {
2178 isl_space *space = isl_aff_get_domain_space(aff);
2179 isl_aff_free(aff);
2180 return isl_basic_set_empty(space);
2183 ineq = isl_equality_from_aff(aff);
2185 bset = isl_basic_set_from_constraint(ineq);
2186 if (rational)
2187 bset = isl_basic_set_set_rational(bset);
2188 bset = isl_basic_set_simplify(bset);
2189 return bset;
2192 /* Return a basic set containing those elements in the space
2193 * of aff where it is zero.
2195 __isl_give isl_basic_set *isl_aff_zero_basic_set(__isl_take isl_aff *aff)
2197 return aff_zero_basic_set(aff, 0);
2200 /* Return a basic set containing those elements in the shared space
2201 * of aff1 and aff2 where aff1 is greater than or equal to aff2.
2203 __isl_give isl_basic_set *isl_aff_ge_basic_set(__isl_take isl_aff *aff1,
2204 __isl_take isl_aff *aff2)
2206 aff1 = isl_aff_sub(aff1, aff2);
2208 return isl_aff_nonneg_basic_set(aff1);
2211 /* Return a basic set containing those elements in the shared space
2212 * of aff1 and aff2 where aff1 is smaller than or equal to aff2.
2214 __isl_give isl_basic_set *isl_aff_le_basic_set(__isl_take isl_aff *aff1,
2215 __isl_take isl_aff *aff2)
2217 return isl_aff_ge_basic_set(aff2, aff1);
2220 __isl_give isl_aff *isl_aff_add_on_domain(__isl_keep isl_set *dom,
2221 __isl_take isl_aff *aff1, __isl_take isl_aff *aff2)
2223 aff1 = isl_aff_add(aff1, aff2);
2224 aff1 = isl_aff_gist(aff1, isl_set_copy(dom));
2225 return aff1;
2228 int isl_aff_is_empty(__isl_keep isl_aff *aff)
2230 if (!aff)
2231 return -1;
2233 return 0;
2236 /* Check whether the given affine expression has non-zero coefficient
2237 * for any dimension in the given range or if any of these dimensions
2238 * appear with non-zero coefficients in any of the integer divisions
2239 * involved in the affine expression.
2241 int isl_aff_involves_dims(__isl_keep isl_aff *aff,
2242 enum isl_dim_type type, unsigned first, unsigned n)
2244 int i;
2245 isl_ctx *ctx;
2246 int *active = NULL;
2247 int involves = 0;
2249 if (!aff)
2250 return -1;
2251 if (n == 0)
2252 return 0;
2254 ctx = isl_aff_get_ctx(aff);
2255 if (first + n > isl_aff_dim(aff, type))
2256 isl_die(ctx, isl_error_invalid,
2257 "range out of bounds", return -1);
2259 active = isl_local_space_get_active(aff->ls, aff->v->el + 2);
2260 if (!active)
2261 goto error;
2263 first += isl_local_space_offset(aff->ls, type) - 1;
2264 for (i = 0; i < n; ++i)
2265 if (active[first + i]) {
2266 involves = 1;
2267 break;
2270 free(active);
2272 return involves;
2273 error:
2274 free(active);
2275 return -1;
2278 __isl_give isl_aff *isl_aff_drop_dims(__isl_take isl_aff *aff,
2279 enum isl_dim_type type, unsigned first, unsigned n)
2281 isl_ctx *ctx;
2283 if (!aff)
2284 return NULL;
2285 if (type == isl_dim_out)
2286 isl_die(aff->v->ctx, isl_error_invalid,
2287 "cannot drop output/set dimension",
2288 return isl_aff_free(aff));
2289 if (type == isl_dim_in)
2290 type = isl_dim_set;
2291 if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
2292 return aff;
2294 ctx = isl_aff_get_ctx(aff);
2295 if (first + n > isl_local_space_dim(aff->ls, type))
2296 isl_die(ctx, isl_error_invalid, "range out of bounds",
2297 return isl_aff_free(aff));
2299 aff = isl_aff_cow(aff);
2300 if (!aff)
2301 return NULL;
2303 aff->ls = isl_local_space_drop_dims(aff->ls, type, first, n);
2304 if (!aff->ls)
2305 return isl_aff_free(aff);
2307 first += 1 + isl_local_space_offset(aff->ls, type);
2308 aff->v = isl_vec_drop_els(aff->v, first, n);
2309 if (!aff->v)
2310 return isl_aff_free(aff);
2312 return aff;
2315 /* Project the domain of the affine expression onto its parameter space.
2316 * The affine expression may not involve any of the domain dimensions.
2318 __isl_give isl_aff *isl_aff_project_domain_on_params(__isl_take isl_aff *aff)
2320 isl_space *space;
2321 unsigned n;
2322 int involves;
2324 n = isl_aff_dim(aff, isl_dim_in);
2325 involves = isl_aff_involves_dims(aff, isl_dim_in, 0, n);
2326 if (involves < 0)
2327 return isl_aff_free(aff);
2328 if (involves)
2329 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
2330 "affine expression involves some of the domain dimensions",
2331 return isl_aff_free(aff));
2332 aff = isl_aff_drop_dims(aff, isl_dim_in, 0, n);
2333 space = isl_aff_get_domain_space(aff);
2334 space = isl_space_params(space);
2335 aff = isl_aff_reset_domain_space(aff, space);
2336 return aff;
2339 __isl_give isl_aff *isl_aff_insert_dims(__isl_take isl_aff *aff,
2340 enum isl_dim_type type, unsigned first, unsigned n)
2342 isl_ctx *ctx;
2344 if (!aff)
2345 return NULL;
2346 if (type == isl_dim_out)
2347 isl_die(aff->v->ctx, isl_error_invalid,
2348 "cannot insert output/set dimensions",
2349 return isl_aff_free(aff));
2350 if (type == isl_dim_in)
2351 type = isl_dim_set;
2352 if (n == 0 && !isl_local_space_is_named_or_nested(aff->ls, type))
2353 return aff;
2355 ctx = isl_aff_get_ctx(aff);
2356 if (first > isl_local_space_dim(aff->ls, type))
2357 isl_die(ctx, isl_error_invalid, "position out of bounds",
2358 return isl_aff_free(aff));
2360 aff = isl_aff_cow(aff);
2361 if (!aff)
2362 return NULL;
2364 aff->ls = isl_local_space_insert_dims(aff->ls, type, first, n);
2365 if (!aff->ls)
2366 return isl_aff_free(aff);
2368 first += 1 + isl_local_space_offset(aff->ls, type);
2369 aff->v = isl_vec_insert_zero_els(aff->v, first, n);
2370 if (!aff->v)
2371 return isl_aff_free(aff);
2373 return aff;
2376 __isl_give isl_aff *isl_aff_add_dims(__isl_take isl_aff *aff,
2377 enum isl_dim_type type, unsigned n)
2379 unsigned pos;
2381 pos = isl_aff_dim(aff, type);
2383 return isl_aff_insert_dims(aff, type, pos, n);
2386 __isl_give isl_pw_aff *isl_pw_aff_add_dims(__isl_take isl_pw_aff *pwaff,
2387 enum isl_dim_type type, unsigned n)
2389 unsigned pos;
2391 pos = isl_pw_aff_dim(pwaff, type);
2393 return isl_pw_aff_insert_dims(pwaff, type, pos, n);
2396 /* Move the "n" dimensions of "src_type" starting at "src_pos" of "aff"
2397 * to dimensions of "dst_type" at "dst_pos".
2399 * We only support moving input dimensions to parameters and vice versa.
2401 __isl_give isl_aff *isl_aff_move_dims(__isl_take isl_aff *aff,
2402 enum isl_dim_type dst_type, unsigned dst_pos,
2403 enum isl_dim_type src_type, unsigned src_pos, unsigned n)
2405 unsigned g_dst_pos;
2406 unsigned g_src_pos;
2408 if (!aff)
2409 return NULL;
2410 if (n == 0 &&
2411 !isl_local_space_is_named_or_nested(aff->ls, src_type) &&
2412 !isl_local_space_is_named_or_nested(aff->ls, dst_type))
2413 return aff;
2415 if (dst_type == isl_dim_out || src_type == isl_dim_out)
2416 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
2417 "cannot move output/set dimension", isl_aff_free(aff));
2418 if (dst_type == isl_dim_div || src_type == isl_dim_div)
2419 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
2420 "cannot move divs", isl_aff_free(aff));
2421 if (dst_type == isl_dim_in)
2422 dst_type = isl_dim_set;
2423 if (src_type == isl_dim_in)
2424 src_type = isl_dim_set;
2426 if (src_pos + n > isl_local_space_dim(aff->ls, src_type))
2427 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
2428 "range out of bounds", isl_aff_free(aff));
2429 if (dst_type == src_type)
2430 isl_die(isl_aff_get_ctx(aff), isl_error_unsupported,
2431 "moving dims within the same type not supported",
2432 isl_aff_free(aff));
2434 aff = isl_aff_cow(aff);
2435 if (!aff)
2436 return NULL;
2438 g_src_pos = 1 + isl_local_space_offset(aff->ls, src_type) + src_pos;
2439 g_dst_pos = 1 + isl_local_space_offset(aff->ls, dst_type) + dst_pos;
2440 if (dst_type > src_type)
2441 g_dst_pos -= n;
2443 aff->v = isl_vec_move_els(aff->v, g_dst_pos, g_src_pos, n);
2444 aff->ls = isl_local_space_move_dims(aff->ls, dst_type, dst_pos,
2445 src_type, src_pos, n);
2446 if (!aff->v || !aff->ls)
2447 return isl_aff_free(aff);
2449 aff = sort_divs(aff);
2451 return aff;
2454 __isl_give isl_pw_aff *isl_pw_aff_from_aff(__isl_take isl_aff *aff)
2456 isl_set *dom = isl_set_universe(isl_aff_get_domain_space(aff));
2457 return isl_pw_aff_alloc(dom, aff);
2460 #undef PW
2461 #define PW isl_pw_aff
2462 #undef EL
2463 #define EL isl_aff
2464 #undef EL_IS_ZERO
2465 #define EL_IS_ZERO is_empty
2466 #undef ZERO
2467 #define ZERO empty
2468 #undef IS_ZERO
2469 #define IS_ZERO is_empty
2470 #undef FIELD
2471 #define FIELD aff
2472 #undef DEFAULT_IS_ZERO
2473 #define DEFAULT_IS_ZERO 0
2475 #define NO_EVAL
2476 #define NO_OPT
2477 #define NO_LIFT
2478 #define NO_MORPH
2480 #include <isl_pw_templ.c>
2482 static __isl_give isl_set *align_params_pw_pw_set_and(
2483 __isl_take isl_pw_aff *pwaff1, __isl_take isl_pw_aff *pwaff2,
2484 __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
2485 __isl_take isl_pw_aff *pwaff2))
2487 if (!pwaff1 || !pwaff2)
2488 goto error;
2489 if (isl_space_match(pwaff1->dim, isl_dim_param,
2490 pwaff2->dim, isl_dim_param))
2491 return fn(pwaff1, pwaff2);
2492 if (!isl_space_has_named_params(pwaff1->dim) ||
2493 !isl_space_has_named_params(pwaff2->dim))
2494 isl_die(isl_pw_aff_get_ctx(pwaff1), isl_error_invalid,
2495 "unaligned unnamed parameters", goto error);
2496 pwaff1 = isl_pw_aff_align_params(pwaff1, isl_pw_aff_get_space(pwaff2));
2497 pwaff2 = isl_pw_aff_align_params(pwaff2, isl_pw_aff_get_space(pwaff1));
2498 return fn(pwaff1, pwaff2);
2499 error:
2500 isl_pw_aff_free(pwaff1);
2501 isl_pw_aff_free(pwaff2);
2502 return NULL;
2505 /* Compute a piecewise quasi-affine expression with a domain that
2506 * is the union of those of pwaff1 and pwaff2 and such that on each
2507 * cell, the quasi-affine expression is the better (according to cmp)
2508 * of those of pwaff1 and pwaff2. If only one of pwaff1 or pwaff2
2509 * is defined on a given cell, then the associated expression
2510 * is the defined one.
2512 static __isl_give isl_pw_aff *pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
2513 __isl_take isl_pw_aff *pwaff2,
2514 __isl_give isl_basic_set *(*cmp)(__isl_take isl_aff *aff1,
2515 __isl_take isl_aff *aff2))
2517 int i, j, n;
2518 isl_pw_aff *res;
2519 isl_ctx *ctx;
2520 isl_set *set;
2522 if (!pwaff1 || !pwaff2)
2523 goto error;
2525 ctx = isl_space_get_ctx(pwaff1->dim);
2526 if (!isl_space_is_equal(pwaff1->dim, pwaff2->dim))
2527 isl_die(ctx, isl_error_invalid,
2528 "arguments should live in same space", goto error);
2530 if (isl_pw_aff_is_empty(pwaff1)) {
2531 isl_pw_aff_free(pwaff1);
2532 return pwaff2;
2535 if (isl_pw_aff_is_empty(pwaff2)) {
2536 isl_pw_aff_free(pwaff2);
2537 return pwaff1;
2540 n = 2 * (pwaff1->n + 1) * (pwaff2->n + 1);
2541 res = isl_pw_aff_alloc_size(isl_space_copy(pwaff1->dim), n);
2543 for (i = 0; i < pwaff1->n; ++i) {
2544 set = isl_set_copy(pwaff1->p[i].set);
2545 for (j = 0; j < pwaff2->n; ++j) {
2546 struct isl_set *common;
2547 isl_set *better;
2549 common = isl_set_intersect(
2550 isl_set_copy(pwaff1->p[i].set),
2551 isl_set_copy(pwaff2->p[j].set));
2552 better = isl_set_from_basic_set(cmp(
2553 isl_aff_copy(pwaff2->p[j].aff),
2554 isl_aff_copy(pwaff1->p[i].aff)));
2555 better = isl_set_intersect(common, better);
2556 if (isl_set_plain_is_empty(better)) {
2557 isl_set_free(better);
2558 continue;
2560 set = isl_set_subtract(set, isl_set_copy(better));
2562 res = isl_pw_aff_add_piece(res, better,
2563 isl_aff_copy(pwaff2->p[j].aff));
2565 res = isl_pw_aff_add_piece(res, set,
2566 isl_aff_copy(pwaff1->p[i].aff));
2569 for (j = 0; j < pwaff2->n; ++j) {
2570 set = isl_set_copy(pwaff2->p[j].set);
2571 for (i = 0; i < pwaff1->n; ++i)
2572 set = isl_set_subtract(set,
2573 isl_set_copy(pwaff1->p[i].set));
2574 res = isl_pw_aff_add_piece(res, set,
2575 isl_aff_copy(pwaff2->p[j].aff));
2578 isl_pw_aff_free(pwaff1);
2579 isl_pw_aff_free(pwaff2);
2581 return res;
2582 error:
2583 isl_pw_aff_free(pwaff1);
2584 isl_pw_aff_free(pwaff2);
2585 return NULL;
2588 /* Compute a piecewise quasi-affine expression with a domain that
2589 * is the union of those of pwaff1 and pwaff2 and such that on each
2590 * cell, the quasi-affine expression is the maximum of those of pwaff1
2591 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
2592 * cell, then the associated expression is the defined one.
2594 static __isl_give isl_pw_aff *pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
2595 __isl_take isl_pw_aff *pwaff2)
2597 return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_ge_basic_set);
2600 __isl_give isl_pw_aff *isl_pw_aff_union_max(__isl_take isl_pw_aff *pwaff1,
2601 __isl_take isl_pw_aff *pwaff2)
2603 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
2604 &pw_aff_union_max);
2607 /* Compute a piecewise quasi-affine expression with a domain that
2608 * is the union of those of pwaff1 and pwaff2 and such that on each
2609 * cell, the quasi-affine expression is the minimum of those of pwaff1
2610 * and pwaff2. If only one of pwaff1 or pwaff2 is defined on a given
2611 * cell, then the associated expression is the defined one.
2613 static __isl_give isl_pw_aff *pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
2614 __isl_take isl_pw_aff *pwaff2)
2616 return pw_aff_union_opt(pwaff1, pwaff2, &isl_aff_le_basic_set);
2619 __isl_give isl_pw_aff *isl_pw_aff_union_min(__isl_take isl_pw_aff *pwaff1,
2620 __isl_take isl_pw_aff *pwaff2)
2622 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2,
2623 &pw_aff_union_min);
2626 __isl_give isl_pw_aff *isl_pw_aff_union_opt(__isl_take isl_pw_aff *pwaff1,
2627 __isl_take isl_pw_aff *pwaff2, int max)
2629 if (max)
2630 return isl_pw_aff_union_max(pwaff1, pwaff2);
2631 else
2632 return isl_pw_aff_union_min(pwaff1, pwaff2);
2635 /* Construct a map with as domain the domain of pwaff and
2636 * one-dimensional range corresponding to the affine expressions.
2638 static __isl_give isl_map *map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
2640 int i;
2641 isl_space *dim;
2642 isl_map *map;
2644 if (!pwaff)
2645 return NULL;
2647 dim = isl_pw_aff_get_space(pwaff);
2648 map = isl_map_empty(dim);
2650 for (i = 0; i < pwaff->n; ++i) {
2651 isl_basic_map *bmap;
2652 isl_map *map_i;
2654 bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
2655 map_i = isl_map_from_basic_map(bmap);
2656 map_i = isl_map_intersect_domain(map_i,
2657 isl_set_copy(pwaff->p[i].set));
2658 map = isl_map_union_disjoint(map, map_i);
2661 isl_pw_aff_free(pwaff);
2663 return map;
2666 /* Construct a map with as domain the domain of pwaff and
2667 * one-dimensional range corresponding to the affine expressions.
2669 __isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
2671 if (!pwaff)
2672 return NULL;
2673 if (isl_space_is_set(pwaff->dim))
2674 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
2675 "space of input is not a map", goto error);
2676 return map_from_pw_aff(pwaff);
2677 error:
2678 isl_pw_aff_free(pwaff);
2679 return NULL;
2682 /* Construct a one-dimensional set with as parameter domain
2683 * the domain of pwaff and the single set dimension
2684 * corresponding to the affine expressions.
2686 __isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
2688 if (!pwaff)
2689 return NULL;
2690 if (!isl_space_is_set(pwaff->dim))
2691 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
2692 "space of input is not a set", goto error);
2693 return map_from_pw_aff(pwaff);
2694 error:
2695 isl_pw_aff_free(pwaff);
2696 return NULL;
2699 /* Return a set containing those elements in the domain
2700 * of pwaff where it is non-negative.
2702 __isl_give isl_set *isl_pw_aff_nonneg_set(__isl_take isl_pw_aff *pwaff)
2704 int i;
2705 isl_set *set;
2707 if (!pwaff)
2708 return NULL;
2710 set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
2712 for (i = 0; i < pwaff->n; ++i) {
2713 isl_basic_set *bset;
2714 isl_set *set_i;
2715 int rational;
2717 rational = isl_set_has_rational(pwaff->p[i].set);
2718 bset = aff_nonneg_basic_set(isl_aff_copy(pwaff->p[i].aff),
2719 rational);
2720 set_i = isl_set_from_basic_set(bset);
2721 set_i = isl_set_intersect(set_i, isl_set_copy(pwaff->p[i].set));
2722 set = isl_set_union_disjoint(set, set_i);
2725 isl_pw_aff_free(pwaff);
2727 return set;
2730 /* Return a set containing those elements in the domain
2731 * of pwaff where it is zero (if complement is 0) or not zero
2732 * (if complement is 1).
2734 * The pieces with a NaN never belong to the result since
2735 * NaN is neither zero nor non-zero.
2737 static __isl_give isl_set *pw_aff_zero_set(__isl_take isl_pw_aff *pwaff,
2738 int complement)
2740 int i;
2741 isl_set *set;
2743 if (!pwaff)
2744 return NULL;
2746 set = isl_set_empty(isl_pw_aff_get_domain_space(pwaff));
2748 for (i = 0; i < pwaff->n; ++i) {
2749 isl_basic_set *bset;
2750 isl_set *set_i, *zero;
2751 int rational;
2753 if (isl_aff_is_nan(pwaff->p[i].aff))
2754 continue;
2756 rational = isl_set_has_rational(pwaff->p[i].set);
2757 bset = aff_zero_basic_set(isl_aff_copy(pwaff->p[i].aff),
2758 rational);
2759 zero = isl_set_from_basic_set(bset);
2760 set_i = isl_set_copy(pwaff->p[i].set);
2761 if (complement)
2762 set_i = isl_set_subtract(set_i, zero);
2763 else
2764 set_i = isl_set_intersect(set_i, zero);
2765 set = isl_set_union_disjoint(set, set_i);
2768 isl_pw_aff_free(pwaff);
2770 return set;
2773 /* Return a set containing those elements in the domain
2774 * of pwaff where it is zero.
2776 __isl_give isl_set *isl_pw_aff_zero_set(__isl_take isl_pw_aff *pwaff)
2778 return pw_aff_zero_set(pwaff, 0);
2781 /* Return a set containing those elements in the domain
2782 * of pwaff where it is not zero.
2784 __isl_give isl_set *isl_pw_aff_non_zero_set(__isl_take isl_pw_aff *pwaff)
2786 return pw_aff_zero_set(pwaff, 1);
2789 /* Return a set containing those elements in the shared domain
2790 * of pwaff1 and pwaff2 where pwaff1 is greater than (or equal) to pwaff2.
2792 * We compute the difference on the shared domain and then construct
2793 * the set of values where this difference is non-negative.
2794 * If strict is set, we first subtract 1 from the difference.
2795 * If equal is set, we only return the elements where pwaff1 and pwaff2
2796 * are equal.
2798 static __isl_give isl_set *pw_aff_gte_set(__isl_take isl_pw_aff *pwaff1,
2799 __isl_take isl_pw_aff *pwaff2, int strict, int equal)
2801 isl_set *set1, *set2;
2803 set1 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff1));
2804 set2 = isl_pw_aff_domain(isl_pw_aff_copy(pwaff2));
2805 set1 = isl_set_intersect(set1, set2);
2806 pwaff1 = isl_pw_aff_intersect_domain(pwaff1, isl_set_copy(set1));
2807 pwaff2 = isl_pw_aff_intersect_domain(pwaff2, isl_set_copy(set1));
2808 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_neg(pwaff2));
2810 if (strict) {
2811 isl_space *dim = isl_set_get_space(set1);
2812 isl_aff *aff;
2813 aff = isl_aff_zero_on_domain(isl_local_space_from_space(dim));
2814 aff = isl_aff_add_constant_si(aff, -1);
2815 pwaff1 = isl_pw_aff_add(pwaff1, isl_pw_aff_alloc(set1, aff));
2816 } else
2817 isl_set_free(set1);
2819 if (equal)
2820 return isl_pw_aff_zero_set(pwaff1);
2821 return isl_pw_aff_nonneg_set(pwaff1);
2824 /* Return a set containing those elements in the shared domain
2825 * of pwaff1 and pwaff2 where pwaff1 is equal to pwaff2.
2827 static __isl_give isl_set *pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
2828 __isl_take isl_pw_aff *pwaff2)
2830 return pw_aff_gte_set(pwaff1, pwaff2, 0, 1);
2833 __isl_give isl_set *isl_pw_aff_eq_set(__isl_take isl_pw_aff *pwaff1,
2834 __isl_take isl_pw_aff *pwaff2)
2836 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_eq_set);
2839 /* Return a set containing those elements in the shared domain
2840 * of pwaff1 and pwaff2 where pwaff1 is greater than or equal to pwaff2.
2842 static __isl_give isl_set *pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
2843 __isl_take isl_pw_aff *pwaff2)
2845 return pw_aff_gte_set(pwaff1, pwaff2, 0, 0);
2848 __isl_give isl_set *isl_pw_aff_ge_set(__isl_take isl_pw_aff *pwaff1,
2849 __isl_take isl_pw_aff *pwaff2)
2851 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ge_set);
2854 /* Return a set containing those elements in the shared domain
2855 * of pwaff1 and pwaff2 where pwaff1 is strictly greater than pwaff2.
2857 static __isl_give isl_set *pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
2858 __isl_take isl_pw_aff *pwaff2)
2860 return pw_aff_gte_set(pwaff1, pwaff2, 1, 0);
2863 __isl_give isl_set *isl_pw_aff_gt_set(__isl_take isl_pw_aff *pwaff1,
2864 __isl_take isl_pw_aff *pwaff2)
2866 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_gt_set);
2869 __isl_give isl_set *isl_pw_aff_le_set(__isl_take isl_pw_aff *pwaff1,
2870 __isl_take isl_pw_aff *pwaff2)
2872 return isl_pw_aff_ge_set(pwaff2, pwaff1);
2875 __isl_give isl_set *isl_pw_aff_lt_set(__isl_take isl_pw_aff *pwaff1,
2876 __isl_take isl_pw_aff *pwaff2)
2878 return isl_pw_aff_gt_set(pwaff2, pwaff1);
2881 /* Return a set containing those elements in the shared domain
2882 * of the elements of list1 and list2 where each element in list1
2883 * has the relation specified by "fn" with each element in list2.
2885 static __isl_give isl_set *pw_aff_list_set(__isl_take isl_pw_aff_list *list1,
2886 __isl_take isl_pw_aff_list *list2,
2887 __isl_give isl_set *(*fn)(__isl_take isl_pw_aff *pwaff1,
2888 __isl_take isl_pw_aff *pwaff2))
2890 int i, j;
2891 isl_ctx *ctx;
2892 isl_set *set;
2894 if (!list1 || !list2)
2895 goto error;
2897 ctx = isl_pw_aff_list_get_ctx(list1);
2898 if (list1->n < 1 || list2->n < 1)
2899 isl_die(ctx, isl_error_invalid,
2900 "list should contain at least one element", goto error);
2902 set = isl_set_universe(isl_pw_aff_get_domain_space(list1->p[0]));
2903 for (i = 0; i < list1->n; ++i)
2904 for (j = 0; j < list2->n; ++j) {
2905 isl_set *set_ij;
2907 set_ij = fn(isl_pw_aff_copy(list1->p[i]),
2908 isl_pw_aff_copy(list2->p[j]));
2909 set = isl_set_intersect(set, set_ij);
2912 isl_pw_aff_list_free(list1);
2913 isl_pw_aff_list_free(list2);
2914 return set;
2915 error:
2916 isl_pw_aff_list_free(list1);
2917 isl_pw_aff_list_free(list2);
2918 return NULL;
2921 /* Return a set containing those elements in the shared domain
2922 * of the elements of list1 and list2 where each element in list1
2923 * is equal to each element in list2.
2925 __isl_give isl_set *isl_pw_aff_list_eq_set(__isl_take isl_pw_aff_list *list1,
2926 __isl_take isl_pw_aff_list *list2)
2928 return pw_aff_list_set(list1, list2, &isl_pw_aff_eq_set);
2931 __isl_give isl_set *isl_pw_aff_list_ne_set(__isl_take isl_pw_aff_list *list1,
2932 __isl_take isl_pw_aff_list *list2)
2934 return pw_aff_list_set(list1, list2, &isl_pw_aff_ne_set);
2937 /* Return a set containing those elements in the shared domain
2938 * of the elements of list1 and list2 where each element in list1
2939 * is less than or equal to each element in list2.
2941 __isl_give isl_set *isl_pw_aff_list_le_set(__isl_take isl_pw_aff_list *list1,
2942 __isl_take isl_pw_aff_list *list2)
2944 return pw_aff_list_set(list1, list2, &isl_pw_aff_le_set);
2947 __isl_give isl_set *isl_pw_aff_list_lt_set(__isl_take isl_pw_aff_list *list1,
2948 __isl_take isl_pw_aff_list *list2)
2950 return pw_aff_list_set(list1, list2, &isl_pw_aff_lt_set);
2953 __isl_give isl_set *isl_pw_aff_list_ge_set(__isl_take isl_pw_aff_list *list1,
2954 __isl_take isl_pw_aff_list *list2)
2956 return pw_aff_list_set(list1, list2, &isl_pw_aff_ge_set);
2959 __isl_give isl_set *isl_pw_aff_list_gt_set(__isl_take isl_pw_aff_list *list1,
2960 __isl_take isl_pw_aff_list *list2)
2962 return pw_aff_list_set(list1, list2, &isl_pw_aff_gt_set);
2966 /* Return a set containing those elements in the shared domain
2967 * of pwaff1 and pwaff2 where pwaff1 is not equal to pwaff2.
2969 static __isl_give isl_set *pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
2970 __isl_take isl_pw_aff *pwaff2)
2972 isl_set *set_lt, *set_gt;
2974 set_lt = isl_pw_aff_lt_set(isl_pw_aff_copy(pwaff1),
2975 isl_pw_aff_copy(pwaff2));
2976 set_gt = isl_pw_aff_gt_set(pwaff1, pwaff2);
2977 return isl_set_union_disjoint(set_lt, set_gt);
2980 __isl_give isl_set *isl_pw_aff_ne_set(__isl_take isl_pw_aff *pwaff1,
2981 __isl_take isl_pw_aff *pwaff2)
2983 return align_params_pw_pw_set_and(pwaff1, pwaff2, &pw_aff_ne_set);
2986 __isl_give isl_pw_aff *isl_pw_aff_scale_down(__isl_take isl_pw_aff *pwaff,
2987 isl_int v)
2989 int i;
2991 if (isl_int_is_one(v))
2992 return pwaff;
2993 if (!isl_int_is_pos(v))
2994 isl_die(isl_pw_aff_get_ctx(pwaff), isl_error_invalid,
2995 "factor needs to be positive",
2996 return isl_pw_aff_free(pwaff));
2997 pwaff = isl_pw_aff_cow(pwaff);
2998 if (!pwaff)
2999 return NULL;
3000 if (pwaff->n == 0)
3001 return pwaff;
3003 for (i = 0; i < pwaff->n; ++i) {
3004 pwaff->p[i].aff = isl_aff_scale_down(pwaff->p[i].aff, v);
3005 if (!pwaff->p[i].aff)
3006 return isl_pw_aff_free(pwaff);
3009 return pwaff;
3012 /* Divide "pa" by "f".
3014 __isl_give isl_pw_aff *isl_pw_aff_scale_down_val(__isl_take isl_pw_aff *pa,
3015 __isl_take isl_val *f)
3017 int i;
3019 if (!pa || !f)
3020 goto error;
3022 if (isl_val_is_one(f)) {
3023 isl_val_free(f);
3024 return pa;
3027 if (!isl_val_is_rat(f))
3028 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
3029 "expecting rational factor", goto error);
3030 if (!isl_val_is_pos(f))
3031 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
3032 "factor needs to be positive", goto error);
3034 pa = isl_pw_aff_cow(pa);
3035 if (!pa)
3036 return NULL;
3037 if (pa->n == 0)
3038 return pa;
3040 for (i = 0; i < pa->n; ++i) {
3041 pa->p[i].aff = isl_aff_scale_down_val(pa->p[i].aff,
3042 isl_val_copy(f));
3043 if (!pa->p[i].aff)
3044 goto error;
3047 isl_val_free(f);
3048 return pa;
3049 error:
3050 isl_pw_aff_free(pa);
3051 isl_val_free(f);
3052 return NULL;
3055 __isl_give isl_pw_aff *isl_pw_aff_floor(__isl_take isl_pw_aff *pwaff)
3057 int i;
3059 pwaff = isl_pw_aff_cow(pwaff);
3060 if (!pwaff)
3061 return NULL;
3062 if (pwaff->n == 0)
3063 return pwaff;
3065 for (i = 0; i < pwaff->n; ++i) {
3066 pwaff->p[i].aff = isl_aff_floor(pwaff->p[i].aff);
3067 if (!pwaff->p[i].aff)
3068 return isl_pw_aff_free(pwaff);
3071 return pwaff;
3074 __isl_give isl_pw_aff *isl_pw_aff_ceil(__isl_take isl_pw_aff *pwaff)
3076 int i;
3078 pwaff = isl_pw_aff_cow(pwaff);
3079 if (!pwaff)
3080 return NULL;
3081 if (pwaff->n == 0)
3082 return pwaff;
3084 for (i = 0; i < pwaff->n; ++i) {
3085 pwaff->p[i].aff = isl_aff_ceil(pwaff->p[i].aff);
3086 if (!pwaff->p[i].aff)
3087 return isl_pw_aff_free(pwaff);
3090 return pwaff;
3093 /* Assuming that "cond1" and "cond2" are disjoint,
3094 * return an affine expression that is equal to pwaff1 on cond1
3095 * and to pwaff2 on cond2.
3097 static __isl_give isl_pw_aff *isl_pw_aff_select(
3098 __isl_take isl_set *cond1, __isl_take isl_pw_aff *pwaff1,
3099 __isl_take isl_set *cond2, __isl_take isl_pw_aff *pwaff2)
3101 pwaff1 = isl_pw_aff_intersect_domain(pwaff1, cond1);
3102 pwaff2 = isl_pw_aff_intersect_domain(pwaff2, cond2);
3104 return isl_pw_aff_add_disjoint(pwaff1, pwaff2);
3107 /* Return an affine expression that is equal to pwaff_true for elements
3108 * where "cond" is non-zero and to pwaff_false for elements where "cond"
3109 * is zero.
3110 * That is, return cond ? pwaff_true : pwaff_false;
3112 * If "cond" involves and NaN, then we conservatively return a NaN
3113 * on its entire domain. In principle, we could consider the pieces
3114 * where it is NaN separately from those where it is not.
3116 __isl_give isl_pw_aff *isl_pw_aff_cond(__isl_take isl_pw_aff *cond,
3117 __isl_take isl_pw_aff *pwaff_true, __isl_take isl_pw_aff *pwaff_false)
3119 isl_set *cond_true, *cond_false;
3121 if (!cond)
3122 goto error;
3123 if (isl_pw_aff_involves_nan(cond)) {
3124 isl_space *space = isl_pw_aff_get_domain_space(cond);
3125 isl_local_space *ls = isl_local_space_from_space(space);
3126 isl_pw_aff_free(cond);
3127 isl_pw_aff_free(pwaff_true);
3128 isl_pw_aff_free(pwaff_false);
3129 return isl_pw_aff_nan_on_domain(ls);
3132 cond_true = isl_pw_aff_non_zero_set(isl_pw_aff_copy(cond));
3133 cond_false = isl_pw_aff_zero_set(cond);
3134 return isl_pw_aff_select(cond_true, pwaff_true,
3135 cond_false, pwaff_false);
3136 error:
3137 isl_pw_aff_free(cond);
3138 isl_pw_aff_free(pwaff_true);
3139 isl_pw_aff_free(pwaff_false);
3140 return NULL;
3143 int isl_aff_is_cst(__isl_keep isl_aff *aff)
3145 if (!aff)
3146 return -1;
3148 return isl_seq_first_non_zero(aff->v->el + 2, aff->v->size - 2) == -1;
3151 /* Check whether pwaff is a piecewise constant.
3153 int isl_pw_aff_is_cst(__isl_keep isl_pw_aff *pwaff)
3155 int i;
3157 if (!pwaff)
3158 return -1;
3160 for (i = 0; i < pwaff->n; ++i) {
3161 int is_cst = isl_aff_is_cst(pwaff->p[i].aff);
3162 if (is_cst < 0 || !is_cst)
3163 return is_cst;
3166 return 1;
3169 /* Return the product of "aff1" and "aff2".
3171 * If either of the two is NaN, then the result is NaN.
3173 * Otherwise, at least one of "aff1" or "aff2" needs to be a constant.
3175 __isl_give isl_aff *isl_aff_mul(__isl_take isl_aff *aff1,
3176 __isl_take isl_aff *aff2)
3178 if (!aff1 || !aff2)
3179 goto error;
3181 if (isl_aff_is_nan(aff1)) {
3182 isl_aff_free(aff2);
3183 return aff1;
3185 if (isl_aff_is_nan(aff2)) {
3186 isl_aff_free(aff1);
3187 return aff2;
3190 if (!isl_aff_is_cst(aff2) && isl_aff_is_cst(aff1))
3191 return isl_aff_mul(aff2, aff1);
3193 if (!isl_aff_is_cst(aff2))
3194 isl_die(isl_aff_get_ctx(aff1), isl_error_invalid,
3195 "at least one affine expression should be constant",
3196 goto error);
3198 aff1 = isl_aff_cow(aff1);
3199 if (!aff1 || !aff2)
3200 goto error;
3202 aff1 = isl_aff_scale(aff1, aff2->v->el[1]);
3203 aff1 = isl_aff_scale_down(aff1, aff2->v->el[0]);
3205 isl_aff_free(aff2);
3206 return aff1;
3207 error:
3208 isl_aff_free(aff1);
3209 isl_aff_free(aff2);
3210 return NULL;
3213 /* Divide "aff1" by "aff2", assuming "aff2" is a constant.
3215 * If either of the two is NaN, then the result is NaN.
3217 __isl_give isl_aff *isl_aff_div(__isl_take isl_aff *aff1,
3218 __isl_take isl_aff *aff2)
3220 int is_cst;
3221 int neg;
3223 if (!aff1 || !aff2)
3224 goto error;
3226 if (isl_aff_is_nan(aff1)) {
3227 isl_aff_free(aff2);
3228 return aff1;
3230 if (isl_aff_is_nan(aff2)) {
3231 isl_aff_free(aff1);
3232 return aff2;
3235 is_cst = isl_aff_is_cst(aff2);
3236 if (is_cst < 0)
3237 goto error;
3238 if (!is_cst)
3239 isl_die(isl_aff_get_ctx(aff2), isl_error_invalid,
3240 "second argument should be a constant", goto error);
3242 if (!aff2)
3243 goto error;
3245 neg = isl_int_is_neg(aff2->v->el[1]);
3246 if (neg) {
3247 isl_int_neg(aff2->v->el[0], aff2->v->el[0]);
3248 isl_int_neg(aff2->v->el[1], aff2->v->el[1]);
3251 aff1 = isl_aff_scale(aff1, aff2->v->el[0]);
3252 aff1 = isl_aff_scale_down(aff1, aff2->v->el[1]);
3254 if (neg) {
3255 isl_int_neg(aff2->v->el[0], aff2->v->el[0]);
3256 isl_int_neg(aff2->v->el[1], aff2->v->el[1]);
3259 isl_aff_free(aff2);
3260 return aff1;
3261 error:
3262 isl_aff_free(aff1);
3263 isl_aff_free(aff2);
3264 return NULL;
3267 static __isl_give isl_pw_aff *pw_aff_add(__isl_take isl_pw_aff *pwaff1,
3268 __isl_take isl_pw_aff *pwaff2)
3270 return isl_pw_aff_on_shared_domain(pwaff1, pwaff2, &isl_aff_add);
3273 __isl_give isl_pw_aff *isl_pw_aff_add(__isl_take isl_pw_aff *pwaff1,
3274 __isl_take isl_pw_aff *pwaff2)
3276 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_add);
3279 __isl_give isl_pw_aff *isl_pw_aff_union_add(__isl_take isl_pw_aff *pwaff1,
3280 __isl_take isl_pw_aff *pwaff2)
3282 return isl_pw_aff_union_add_(pwaff1, pwaff2);
3285 static __isl_give isl_pw_aff *pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
3286 __isl_take isl_pw_aff *pwaff2)
3288 return isl_pw_aff_on_shared_domain(pwaff1, pwaff2, &isl_aff_mul);
3291 __isl_give isl_pw_aff *isl_pw_aff_mul(__isl_take isl_pw_aff *pwaff1,
3292 __isl_take isl_pw_aff *pwaff2)
3294 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_mul);
3297 static __isl_give isl_pw_aff *pw_aff_div(__isl_take isl_pw_aff *pa1,
3298 __isl_take isl_pw_aff *pa2)
3300 return isl_pw_aff_on_shared_domain(pa1, pa2, &isl_aff_div);
3303 /* Divide "pa1" by "pa2", assuming "pa2" is a piecewise constant.
3305 __isl_give isl_pw_aff *isl_pw_aff_div(__isl_take isl_pw_aff *pa1,
3306 __isl_take isl_pw_aff *pa2)
3308 int is_cst;
3310 is_cst = isl_pw_aff_is_cst(pa2);
3311 if (is_cst < 0)
3312 goto error;
3313 if (!is_cst)
3314 isl_die(isl_pw_aff_get_ctx(pa2), isl_error_invalid,
3315 "second argument should be a piecewise constant",
3316 goto error);
3317 return isl_pw_aff_align_params_pw_pw_and(pa1, pa2, &pw_aff_div);
3318 error:
3319 isl_pw_aff_free(pa1);
3320 isl_pw_aff_free(pa2);
3321 return NULL;
3324 /* Compute the quotient of the integer division of "pa1" by "pa2"
3325 * with rounding towards zero.
3326 * "pa2" is assumed to be a piecewise constant.
3328 * In particular, return
3330 * pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2)
3333 __isl_give isl_pw_aff *isl_pw_aff_tdiv_q(__isl_take isl_pw_aff *pa1,
3334 __isl_take isl_pw_aff *pa2)
3336 int is_cst;
3337 isl_set *cond;
3338 isl_pw_aff *f, *c;
3340 is_cst = isl_pw_aff_is_cst(pa2);
3341 if (is_cst < 0)
3342 goto error;
3343 if (!is_cst)
3344 isl_die(isl_pw_aff_get_ctx(pa2), isl_error_invalid,
3345 "second argument should be a piecewise constant",
3346 goto error);
3348 pa1 = isl_pw_aff_div(pa1, pa2);
3350 cond = isl_pw_aff_nonneg_set(isl_pw_aff_copy(pa1));
3351 f = isl_pw_aff_floor(isl_pw_aff_copy(pa1));
3352 c = isl_pw_aff_ceil(pa1);
3353 return isl_pw_aff_cond(isl_set_indicator_function(cond), f, c);
3354 error:
3355 isl_pw_aff_free(pa1);
3356 isl_pw_aff_free(pa2);
3357 return NULL;
3360 /* Compute the remainder of the integer division of "pa1" by "pa2"
3361 * with rounding towards zero.
3362 * "pa2" is assumed to be a piecewise constant.
3364 * In particular, return
3366 * pa1 - pa2 * (pa1 >= 0 ? floor(pa1/pa2) : ceil(pa1/pa2))
3369 __isl_give isl_pw_aff *isl_pw_aff_tdiv_r(__isl_take isl_pw_aff *pa1,
3370 __isl_take isl_pw_aff *pa2)
3372 int is_cst;
3373 isl_pw_aff *res;
3375 is_cst = isl_pw_aff_is_cst(pa2);
3376 if (is_cst < 0)
3377 goto error;
3378 if (!is_cst)
3379 isl_die(isl_pw_aff_get_ctx(pa2), isl_error_invalid,
3380 "second argument should be a piecewise constant",
3381 goto error);
3382 res = isl_pw_aff_tdiv_q(isl_pw_aff_copy(pa1), isl_pw_aff_copy(pa2));
3383 res = isl_pw_aff_mul(pa2, res);
3384 res = isl_pw_aff_sub(pa1, res);
3385 return res;
3386 error:
3387 isl_pw_aff_free(pa1);
3388 isl_pw_aff_free(pa2);
3389 return NULL;
3392 static __isl_give isl_pw_aff *pw_aff_min(__isl_take isl_pw_aff *pwaff1,
3393 __isl_take isl_pw_aff *pwaff2)
3395 isl_set *le;
3396 isl_set *dom;
3398 dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1)),
3399 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2)));
3400 le = isl_pw_aff_le_set(isl_pw_aff_copy(pwaff1),
3401 isl_pw_aff_copy(pwaff2));
3402 dom = isl_set_subtract(dom, isl_set_copy(le));
3403 return isl_pw_aff_select(le, pwaff1, dom, pwaff2);
3406 __isl_give isl_pw_aff *isl_pw_aff_min(__isl_take isl_pw_aff *pwaff1,
3407 __isl_take isl_pw_aff *pwaff2)
3409 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_min);
3412 static __isl_give isl_pw_aff *pw_aff_max(__isl_take isl_pw_aff *pwaff1,
3413 __isl_take isl_pw_aff *pwaff2)
3415 isl_set *ge;
3416 isl_set *dom;
3418 dom = isl_set_intersect(isl_pw_aff_domain(isl_pw_aff_copy(pwaff1)),
3419 isl_pw_aff_domain(isl_pw_aff_copy(pwaff2)));
3420 ge = isl_pw_aff_ge_set(isl_pw_aff_copy(pwaff1),
3421 isl_pw_aff_copy(pwaff2));
3422 dom = isl_set_subtract(dom, isl_set_copy(ge));
3423 return isl_pw_aff_select(ge, pwaff1, dom, pwaff2);
3426 __isl_give isl_pw_aff *isl_pw_aff_max(__isl_take isl_pw_aff *pwaff1,
3427 __isl_take isl_pw_aff *pwaff2)
3429 return isl_pw_aff_align_params_pw_pw_and(pwaff1, pwaff2, &pw_aff_max);
3432 static __isl_give isl_pw_aff *pw_aff_list_reduce(
3433 __isl_take isl_pw_aff_list *list,
3434 __isl_give isl_pw_aff *(*fn)(__isl_take isl_pw_aff *pwaff1,
3435 __isl_take isl_pw_aff *pwaff2))
3437 int i;
3438 isl_ctx *ctx;
3439 isl_pw_aff *res;
3441 if (!list)
3442 return NULL;
3444 ctx = isl_pw_aff_list_get_ctx(list);
3445 if (list->n < 1)
3446 isl_die(ctx, isl_error_invalid,
3447 "list should contain at least one element", goto error);
3449 res = isl_pw_aff_copy(list->p[0]);
3450 for (i = 1; i < list->n; ++i)
3451 res = fn(res, isl_pw_aff_copy(list->p[i]));
3453 isl_pw_aff_list_free(list);
3454 return res;
3455 error:
3456 isl_pw_aff_list_free(list);
3457 return NULL;
3460 /* Return an isl_pw_aff that maps each element in the intersection of the
3461 * domains of the elements of list to the minimal corresponding affine
3462 * expression.
3464 __isl_give isl_pw_aff *isl_pw_aff_list_min(__isl_take isl_pw_aff_list *list)
3466 return pw_aff_list_reduce(list, &isl_pw_aff_min);
3469 /* Return an isl_pw_aff that maps each element in the intersection of the
3470 * domains of the elements of list to the maximal corresponding affine
3471 * expression.
3473 __isl_give isl_pw_aff *isl_pw_aff_list_max(__isl_take isl_pw_aff_list *list)
3475 return pw_aff_list_reduce(list, &isl_pw_aff_max);
3478 /* Mark the domains of "pwaff" as rational.
3480 __isl_give isl_pw_aff *isl_pw_aff_set_rational(__isl_take isl_pw_aff *pwaff)
3482 int i;
3484 pwaff = isl_pw_aff_cow(pwaff);
3485 if (!pwaff)
3486 return NULL;
3487 if (pwaff->n == 0)
3488 return pwaff;
3490 for (i = 0; i < pwaff->n; ++i) {
3491 pwaff->p[i].set = isl_set_set_rational(pwaff->p[i].set);
3492 if (!pwaff->p[i].set)
3493 return isl_pw_aff_free(pwaff);
3496 return pwaff;
3499 /* Mark the domains of the elements of "list" as rational.
3501 __isl_give isl_pw_aff_list *isl_pw_aff_list_set_rational(
3502 __isl_take isl_pw_aff_list *list)
3504 int i, n;
3506 if (!list)
3507 return NULL;
3508 if (list->n == 0)
3509 return list;
3511 n = list->n;
3512 for (i = 0; i < n; ++i) {
3513 isl_pw_aff *pa;
3515 pa = isl_pw_aff_list_get_pw_aff(list, i);
3516 pa = isl_pw_aff_set_rational(pa);
3517 list = isl_pw_aff_list_set_pw_aff(list, i, pa);
3520 return list;
3523 /* Do the parameters of "aff" match those of "space"?
3525 int isl_aff_matching_params(__isl_keep isl_aff *aff,
3526 __isl_keep isl_space *space)
3528 isl_space *aff_space;
3529 int match;
3531 if (!aff || !space)
3532 return -1;
3534 aff_space = isl_aff_get_domain_space(aff);
3536 match = isl_space_match(space, isl_dim_param, aff_space, isl_dim_param);
3538 isl_space_free(aff_space);
3539 return match;
3542 /* Check that the domain space of "aff" matches "space".
3544 * Return 0 on success and -1 on error.
3546 int isl_aff_check_match_domain_space(__isl_keep isl_aff *aff,
3547 __isl_keep isl_space *space)
3549 isl_space *aff_space;
3550 int match;
3552 if (!aff || !space)
3553 return -1;
3555 aff_space = isl_aff_get_domain_space(aff);
3557 match = isl_space_match(space, isl_dim_param, aff_space, isl_dim_param);
3558 if (match < 0)
3559 goto error;
3560 if (!match)
3561 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
3562 "parameters don't match", goto error);
3563 match = isl_space_tuple_match(space, isl_dim_in,
3564 aff_space, isl_dim_set);
3565 if (match < 0)
3566 goto error;
3567 if (!match)
3568 isl_die(isl_aff_get_ctx(aff), isl_error_invalid,
3569 "domains don't match", goto error);
3570 isl_space_free(aff_space);
3571 return 0;
3572 error:
3573 isl_space_free(aff_space);
3574 return -1;
3577 #undef BASE
3578 #define BASE aff
3579 #define NO_INTERSECT_DOMAIN
3580 #define NO_DOMAIN
3582 #include <isl_multi_templ.c>
3584 #undef NO_DOMAIN
3585 #undef NO_INTERSECT_DOMAIN
3587 /* Remove any internal structure of the domain of "ma".
3588 * If there is any such internal structure in the input,
3589 * then the name of the corresponding space is also removed.
3591 __isl_give isl_multi_aff *isl_multi_aff_flatten_domain(
3592 __isl_take isl_multi_aff *ma)
3594 isl_space *space;
3596 if (!ma)
3597 return NULL;
3599 if (!ma->space->nested[0])
3600 return ma;
3602 space = isl_multi_aff_get_space(ma);
3603 space = isl_space_flatten_domain(space);
3604 ma = isl_multi_aff_reset_space(ma, space);
3606 return ma;
3609 /* Given a map space, return an isl_multi_aff that maps a wrapped copy
3610 * of the space to its domain.
3612 __isl_give isl_multi_aff *isl_multi_aff_domain_map(__isl_take isl_space *space)
3614 int i, n_in;
3615 isl_local_space *ls;
3616 isl_multi_aff *ma;
3618 if (!space)
3619 return NULL;
3620 if (!isl_space_is_map(space))
3621 isl_die(isl_space_get_ctx(space), isl_error_invalid,
3622 "not a map space", goto error);
3624 n_in = isl_space_dim(space, isl_dim_in);
3625 space = isl_space_domain_map(space);
3627 ma = isl_multi_aff_alloc(isl_space_copy(space));
3628 if (n_in == 0) {
3629 isl_space_free(space);
3630 return ma;
3633 space = isl_space_domain(space);
3634 ls = isl_local_space_from_space(space);
3635 for (i = 0; i < n_in; ++i) {
3636 isl_aff *aff;
3638 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
3639 isl_dim_set, i);
3640 ma = isl_multi_aff_set_aff(ma, i, aff);
3642 isl_local_space_free(ls);
3643 return ma;
3644 error:
3645 isl_space_free(space);
3646 return NULL;
3649 /* Given a map space, return an isl_multi_aff that maps a wrapped copy
3650 * of the space to its range.
3652 __isl_give isl_multi_aff *isl_multi_aff_range_map(__isl_take isl_space *space)
3654 int i, n_in, n_out;
3655 isl_local_space *ls;
3656 isl_multi_aff *ma;
3658 if (!space)
3659 return NULL;
3660 if (!isl_space_is_map(space))
3661 isl_die(isl_space_get_ctx(space), isl_error_invalid,
3662 "not a map space", goto error);
3664 n_in = isl_space_dim(space, isl_dim_in);
3665 n_out = isl_space_dim(space, isl_dim_out);
3666 space = isl_space_range_map(space);
3668 ma = isl_multi_aff_alloc(isl_space_copy(space));
3669 if (n_out == 0) {
3670 isl_space_free(space);
3671 return ma;
3674 space = isl_space_domain(space);
3675 ls = isl_local_space_from_space(space);
3676 for (i = 0; i < n_out; ++i) {
3677 isl_aff *aff;
3679 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
3680 isl_dim_set, n_in + i);
3681 ma = isl_multi_aff_set_aff(ma, i, aff);
3683 isl_local_space_free(ls);
3684 return ma;
3685 error:
3686 isl_space_free(space);
3687 return NULL;
3690 /* Given the space of a set and a range of set dimensions,
3691 * construct an isl_multi_aff that projects out those dimensions.
3693 __isl_give isl_multi_aff *isl_multi_aff_project_out_map(
3694 __isl_take isl_space *space, enum isl_dim_type type,
3695 unsigned first, unsigned n)
3697 int i, dim;
3698 isl_local_space *ls;
3699 isl_multi_aff *ma;
3701 if (!space)
3702 return NULL;
3703 if (!isl_space_is_set(space))
3704 isl_die(isl_space_get_ctx(space), isl_error_unsupported,
3705 "expecting set space", goto error);
3706 if (type != isl_dim_set)
3707 isl_die(isl_space_get_ctx(space), isl_error_invalid,
3708 "only set dimensions can be projected out", goto error);
3710 dim = isl_space_dim(space, isl_dim_set);
3711 if (first + n > dim)
3712 isl_die(isl_space_get_ctx(space), isl_error_invalid,
3713 "range out of bounds", goto error);
3715 space = isl_space_from_domain(space);
3716 space = isl_space_add_dims(space, isl_dim_out, dim - n);
3718 if (dim == n)
3719 return isl_multi_aff_alloc(space);
3721 ma = isl_multi_aff_alloc(isl_space_copy(space));
3722 space = isl_space_domain(space);
3723 ls = isl_local_space_from_space(space);
3725 for (i = 0; i < first; ++i) {
3726 isl_aff *aff;
3728 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
3729 isl_dim_set, i);
3730 ma = isl_multi_aff_set_aff(ma, i, aff);
3733 for (i = 0; i < dim - (first + n); ++i) {
3734 isl_aff *aff;
3736 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
3737 isl_dim_set, first + n + i);
3738 ma = isl_multi_aff_set_aff(ma, first + i, aff);
3741 isl_local_space_free(ls);
3742 return ma;
3743 error:
3744 isl_space_free(space);
3745 return NULL;
3748 /* Given the space of a set and a range of set dimensions,
3749 * construct an isl_pw_multi_aff that projects out those dimensions.
3751 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_project_out_map(
3752 __isl_take isl_space *space, enum isl_dim_type type,
3753 unsigned first, unsigned n)
3755 isl_multi_aff *ma;
3757 ma = isl_multi_aff_project_out_map(space, type, first, n);
3758 return isl_pw_multi_aff_from_multi_aff(ma);
3761 /* Create an isl_pw_multi_aff with the given isl_multi_aff on a universe
3762 * domain.
3764 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_multi_aff(
3765 __isl_take isl_multi_aff *ma)
3767 isl_set *dom = isl_set_universe(isl_multi_aff_get_domain_space(ma));
3768 return isl_pw_multi_aff_alloc(dom, ma);
3771 /* Create a piecewise multi-affine expression in the given space that maps each
3772 * input dimension to the corresponding output dimension.
3774 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_identity(
3775 __isl_take isl_space *space)
3777 return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_identity(space));
3780 /* Add "ma2" to "ma1" and return the result.
3782 * The parameters of "ma1" and "ma2" are assumed to have been aligned.
3784 static __isl_give isl_multi_aff *isl_multi_aff_add_aligned(
3785 __isl_take isl_multi_aff *maff1, __isl_take isl_multi_aff *maff2)
3787 return isl_multi_aff_bin_op(maff1, maff2, &isl_aff_add);
3790 /* Add "ma2" to "ma1" and return the result.
3792 __isl_give isl_multi_aff *isl_multi_aff_add(__isl_take isl_multi_aff *ma1,
3793 __isl_take isl_multi_aff *ma2)
3795 return isl_multi_aff_align_params_multi_multi_and(ma1, ma2,
3796 &isl_multi_aff_add_aligned);
3799 /* Subtract "ma2" from "ma1" and return the result.
3801 * The parameters of "ma1" and "ma2" are assumed to have been aligned.
3803 static __isl_give isl_multi_aff *isl_multi_aff_sub_aligned(
3804 __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2)
3806 return isl_multi_aff_bin_op(ma1, ma2, &isl_aff_sub);
3809 /* Subtract "ma2" from "ma1" and return the result.
3811 __isl_give isl_multi_aff *isl_multi_aff_sub(__isl_take isl_multi_aff *ma1,
3812 __isl_take isl_multi_aff *ma2)
3814 return isl_multi_aff_align_params_multi_multi_and(ma1, ma2,
3815 &isl_multi_aff_sub_aligned);
3818 /* Exploit the equalities in "eq" to simplify the affine expressions.
3820 static __isl_give isl_multi_aff *isl_multi_aff_substitute_equalities(
3821 __isl_take isl_multi_aff *maff, __isl_take isl_basic_set *eq)
3823 int i;
3825 maff = isl_multi_aff_cow(maff);
3826 if (!maff || !eq)
3827 goto error;
3829 for (i = 0; i < maff->n; ++i) {
3830 maff->p[i] = isl_aff_substitute_equalities(maff->p[i],
3831 isl_basic_set_copy(eq));
3832 if (!maff->p[i])
3833 goto error;
3836 isl_basic_set_free(eq);
3837 return maff;
3838 error:
3839 isl_basic_set_free(eq);
3840 isl_multi_aff_free(maff);
3841 return NULL;
3844 /* Given f, return floor(f).
3846 __isl_give isl_multi_aff *isl_multi_aff_floor(__isl_take isl_multi_aff *ma)
3848 int i;
3850 ma = isl_multi_aff_cow(ma);
3851 if (!ma)
3852 return NULL;
3854 for (i = 0; i < ma->n; ++i) {
3855 ma->p[i] = isl_aff_floor(ma->p[i]);
3856 if (!ma->p[i])
3857 return isl_multi_aff_free(ma);
3860 return ma;
3863 __isl_give isl_multi_aff *isl_multi_aff_scale(__isl_take isl_multi_aff *maff,
3864 isl_int f)
3866 int i;
3868 maff = isl_multi_aff_cow(maff);
3869 if (!maff)
3870 return NULL;
3872 for (i = 0; i < maff->n; ++i) {
3873 maff->p[i] = isl_aff_scale(maff->p[i], f);
3874 if (!maff->p[i])
3875 return isl_multi_aff_free(maff);
3878 return maff;
3881 __isl_give isl_multi_aff *isl_multi_aff_add_on_domain(__isl_keep isl_set *dom,
3882 __isl_take isl_multi_aff *maff1, __isl_take isl_multi_aff *maff2)
3884 maff1 = isl_multi_aff_add(maff1, maff2);
3885 maff1 = isl_multi_aff_gist(maff1, isl_set_copy(dom));
3886 return maff1;
3889 int isl_multi_aff_is_empty(__isl_keep isl_multi_aff *maff)
3891 if (!maff)
3892 return -1;
3894 return 0;
3897 /* Return the set of domain elements where "ma1" is lexicographically
3898 * smaller than or equal to "ma2".
3900 __isl_give isl_set *isl_multi_aff_lex_le_set(__isl_take isl_multi_aff *ma1,
3901 __isl_take isl_multi_aff *ma2)
3903 return isl_multi_aff_lex_ge_set(ma2, ma1);
3906 /* Return the set of domain elements where "ma1" is lexicographically
3907 * greater than or equal to "ma2".
3909 __isl_give isl_set *isl_multi_aff_lex_ge_set(__isl_take isl_multi_aff *ma1,
3910 __isl_take isl_multi_aff *ma2)
3912 isl_space *space;
3913 isl_map *map1, *map2;
3914 isl_map *map, *ge;
3916 map1 = isl_map_from_multi_aff(ma1);
3917 map2 = isl_map_from_multi_aff(ma2);
3918 map = isl_map_range_product(map1, map2);
3919 space = isl_space_range(isl_map_get_space(map));
3920 space = isl_space_domain(isl_space_unwrap(space));
3921 ge = isl_map_lex_ge(space);
3922 map = isl_map_intersect_range(map, isl_map_wrap(ge));
3924 return isl_map_domain(map);
3927 #undef PW
3928 #define PW isl_pw_multi_aff
3929 #undef EL
3930 #define EL isl_multi_aff
3931 #undef EL_IS_ZERO
3932 #define EL_IS_ZERO is_empty
3933 #undef ZERO
3934 #define ZERO empty
3935 #undef IS_ZERO
3936 #define IS_ZERO is_empty
3937 #undef FIELD
3938 #define FIELD maff
3939 #undef DEFAULT_IS_ZERO
3940 #define DEFAULT_IS_ZERO 0
3942 #define NO_NEG
3943 #define NO_EVAL
3944 #define NO_OPT
3945 #define NO_INVOLVES_DIMS
3946 #define NO_INSERT_DIMS
3947 #define NO_LIFT
3948 #define NO_MORPH
3950 #include <isl_pw_templ.c>
3952 #undef UNION
3953 #define UNION isl_union_pw_multi_aff
3954 #undef PART
3955 #define PART isl_pw_multi_aff
3956 #undef PARTS
3957 #define PARTS pw_multi_aff
3958 #define ALIGN_DOMAIN
3960 #define NO_EVAL
3962 #include <isl_union_templ.c>
3964 /* Given a function "cmp" that returns the set of elements where
3965 * "ma1" is "better" than "ma2", return the intersection of this
3966 * set with "dom1" and "dom2".
3968 static __isl_give isl_set *shared_and_better(__isl_keep isl_set *dom1,
3969 __isl_keep isl_set *dom2, __isl_keep isl_multi_aff *ma1,
3970 __isl_keep isl_multi_aff *ma2,
3971 __isl_give isl_set *(*cmp)(__isl_take isl_multi_aff *ma1,
3972 __isl_take isl_multi_aff *ma2))
3974 isl_set *common;
3975 isl_set *better;
3976 int is_empty;
3978 common = isl_set_intersect(isl_set_copy(dom1), isl_set_copy(dom2));
3979 is_empty = isl_set_plain_is_empty(common);
3980 if (is_empty >= 0 && is_empty)
3981 return common;
3982 if (is_empty < 0)
3983 return isl_set_free(common);
3984 better = cmp(isl_multi_aff_copy(ma1), isl_multi_aff_copy(ma2));
3985 better = isl_set_intersect(common, better);
3987 return better;
3990 /* Given a function "cmp" that returns the set of elements where
3991 * "ma1" is "better" than "ma2", return a piecewise multi affine
3992 * expression defined on the union of the definition domains
3993 * of "pma1" and "pma2" that maps to the "best" of "pma1" and
3994 * "pma2" on each cell. If only one of the two input functions
3995 * is defined on a given cell, then it is considered the best.
3997 static __isl_give isl_pw_multi_aff *pw_multi_aff_union_opt(
3998 __isl_take isl_pw_multi_aff *pma1,
3999 __isl_take isl_pw_multi_aff *pma2,
4000 __isl_give isl_set *(*cmp)(__isl_take isl_multi_aff *ma1,
4001 __isl_take isl_multi_aff *ma2))
4003 int i, j, n;
4004 isl_pw_multi_aff *res = NULL;
4005 isl_ctx *ctx;
4006 isl_set *set = NULL;
4008 if (!pma1 || !pma2)
4009 goto error;
4011 ctx = isl_space_get_ctx(pma1->dim);
4012 if (!isl_space_is_equal(pma1->dim, pma2->dim))
4013 isl_die(ctx, isl_error_invalid,
4014 "arguments should live in the same space", goto error);
4016 if (isl_pw_multi_aff_is_empty(pma1)) {
4017 isl_pw_multi_aff_free(pma1);
4018 return pma2;
4021 if (isl_pw_multi_aff_is_empty(pma2)) {
4022 isl_pw_multi_aff_free(pma2);
4023 return pma1;
4026 n = 2 * (pma1->n + 1) * (pma2->n + 1);
4027 res = isl_pw_multi_aff_alloc_size(isl_space_copy(pma1->dim), n);
4029 for (i = 0; i < pma1->n; ++i) {
4030 set = isl_set_copy(pma1->p[i].set);
4031 for (j = 0; j < pma2->n; ++j) {
4032 isl_set *better;
4033 int is_empty;
4035 better = shared_and_better(pma2->p[j].set,
4036 pma1->p[i].set, pma2->p[j].maff,
4037 pma1->p[i].maff, cmp);
4038 is_empty = isl_set_plain_is_empty(better);
4039 if (is_empty < 0 || is_empty) {
4040 isl_set_free(better);
4041 if (is_empty < 0)
4042 goto error;
4043 continue;
4045 set = isl_set_subtract(set, isl_set_copy(better));
4047 res = isl_pw_multi_aff_add_piece(res, better,
4048 isl_multi_aff_copy(pma2->p[j].maff));
4050 res = isl_pw_multi_aff_add_piece(res, set,
4051 isl_multi_aff_copy(pma1->p[i].maff));
4054 for (j = 0; j < pma2->n; ++j) {
4055 set = isl_set_copy(pma2->p[j].set);
4056 for (i = 0; i < pma1->n; ++i)
4057 set = isl_set_subtract(set,
4058 isl_set_copy(pma1->p[i].set));
4059 res = isl_pw_multi_aff_add_piece(res, set,
4060 isl_multi_aff_copy(pma2->p[j].maff));
4063 isl_pw_multi_aff_free(pma1);
4064 isl_pw_multi_aff_free(pma2);
4066 return res;
4067 error:
4068 isl_pw_multi_aff_free(pma1);
4069 isl_pw_multi_aff_free(pma2);
4070 isl_set_free(set);
4071 return isl_pw_multi_aff_free(res);
4074 static __isl_give isl_pw_multi_aff *pw_multi_aff_union_lexmax(
4075 __isl_take isl_pw_multi_aff *pma1,
4076 __isl_take isl_pw_multi_aff *pma2)
4078 return pw_multi_aff_union_opt(pma1, pma2, &isl_multi_aff_lex_ge_set);
4081 /* Given two piecewise multi affine expressions, return a piecewise
4082 * multi-affine expression defined on the union of the definition domains
4083 * of the inputs that is equal to the lexicographic maximum of the two
4084 * inputs on each cell. If only one of the two inputs is defined on
4085 * a given cell, then it is considered to be the maximum.
4087 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_lexmax(
4088 __isl_take isl_pw_multi_aff *pma1,
4089 __isl_take isl_pw_multi_aff *pma2)
4091 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
4092 &pw_multi_aff_union_lexmax);
4095 static __isl_give isl_pw_multi_aff *pw_multi_aff_union_lexmin(
4096 __isl_take isl_pw_multi_aff *pma1,
4097 __isl_take isl_pw_multi_aff *pma2)
4099 return pw_multi_aff_union_opt(pma1, pma2, &isl_multi_aff_lex_le_set);
4102 /* Given two piecewise multi affine expressions, return a piecewise
4103 * multi-affine expression defined on the union of the definition domains
4104 * of the inputs that is equal to the lexicographic minimum of the two
4105 * inputs on each cell. If only one of the two inputs is defined on
4106 * a given cell, then it is considered to be the minimum.
4108 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_lexmin(
4109 __isl_take isl_pw_multi_aff *pma1,
4110 __isl_take isl_pw_multi_aff *pma2)
4112 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
4113 &pw_multi_aff_union_lexmin);
4116 static __isl_give isl_pw_multi_aff *pw_multi_aff_add(
4117 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4119 return isl_pw_multi_aff_on_shared_domain(pma1, pma2,
4120 &isl_multi_aff_add);
4123 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_add(
4124 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4126 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
4127 &pw_multi_aff_add);
4130 static __isl_give isl_pw_multi_aff *pw_multi_aff_sub(
4131 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4133 return isl_pw_multi_aff_on_shared_domain(pma1, pma2,
4134 &isl_multi_aff_sub);
4137 /* Subtract "pma2" from "pma1" and return the result.
4139 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_sub(
4140 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4142 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
4143 &pw_multi_aff_sub);
4146 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_union_add(
4147 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4149 return isl_pw_multi_aff_union_add_(pma1, pma2);
4152 /* Given two piecewise multi-affine expressions A -> B and C -> D,
4153 * construct a piecewise multi-affine expression [A -> C] -> [B -> D].
4155 static __isl_give isl_pw_multi_aff *pw_multi_aff_product(
4156 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4158 int i, j, n;
4159 isl_space *space;
4160 isl_pw_multi_aff *res;
4162 if (!pma1 || !pma2)
4163 goto error;
4165 n = pma1->n * pma2->n;
4166 space = isl_space_product(isl_space_copy(pma1->dim),
4167 isl_space_copy(pma2->dim));
4168 res = isl_pw_multi_aff_alloc_size(space, n);
4170 for (i = 0; i < pma1->n; ++i) {
4171 for (j = 0; j < pma2->n; ++j) {
4172 isl_set *domain;
4173 isl_multi_aff *ma;
4175 domain = isl_set_product(isl_set_copy(pma1->p[i].set),
4176 isl_set_copy(pma2->p[j].set));
4177 ma = isl_multi_aff_product(
4178 isl_multi_aff_copy(pma1->p[i].maff),
4179 isl_multi_aff_copy(pma2->p[j].maff));
4180 res = isl_pw_multi_aff_add_piece(res, domain, ma);
4184 isl_pw_multi_aff_free(pma1);
4185 isl_pw_multi_aff_free(pma2);
4186 return res;
4187 error:
4188 isl_pw_multi_aff_free(pma1);
4189 isl_pw_multi_aff_free(pma2);
4190 return NULL;
4193 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_product(
4194 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
4196 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
4197 &pw_multi_aff_product);
4200 /* Construct a map mapping the domain of the piecewise multi-affine expression
4201 * to its range, with each dimension in the range equated to the
4202 * corresponding affine expression on its cell.
4204 __isl_give isl_map *isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
4206 int i;
4207 isl_map *map;
4209 if (!pma)
4210 return NULL;
4212 map = isl_map_empty(isl_pw_multi_aff_get_space(pma));
4214 for (i = 0; i < pma->n; ++i) {
4215 isl_multi_aff *maff;
4216 isl_basic_map *bmap;
4217 isl_map *map_i;
4219 maff = isl_multi_aff_copy(pma->p[i].maff);
4220 bmap = isl_basic_map_from_multi_aff(maff);
4221 map_i = isl_map_from_basic_map(bmap);
4222 map_i = isl_map_intersect_domain(map_i,
4223 isl_set_copy(pma->p[i].set));
4224 map = isl_map_union_disjoint(map, map_i);
4227 isl_pw_multi_aff_free(pma);
4228 return map;
4231 __isl_give isl_set *isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
4233 if (!pma)
4234 return NULL;
4236 if (!isl_space_is_set(pma->dim))
4237 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
4238 "isl_pw_multi_aff cannot be converted into an isl_set",
4239 goto error);
4241 return isl_map_from_pw_multi_aff(pma);
4242 error:
4243 isl_pw_multi_aff_free(pma);
4244 return NULL;
4247 /* Given a basic map with a single output dimension that is defined
4248 * in terms of the parameters and input dimensions using an equality,
4249 * extract an isl_aff that expresses the output dimension in terms
4250 * of the parameters and input dimensions.
4252 * This function shares some similarities with
4253 * isl_basic_map_has_defining_equality and isl_constraint_get_bound.
4255 static __isl_give isl_aff *extract_isl_aff_from_basic_map(
4256 __isl_take isl_basic_map *bmap)
4258 int i;
4259 unsigned offset;
4260 unsigned total;
4261 isl_local_space *ls;
4262 isl_aff *aff;
4264 if (!bmap)
4265 return NULL;
4266 if (isl_basic_map_dim(bmap, isl_dim_out) != 1)
4267 isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
4268 "basic map should have a single output dimension",
4269 goto error);
4270 offset = isl_basic_map_offset(bmap, isl_dim_out);
4271 total = isl_basic_map_total_dim(bmap);
4272 for (i = 0; i < bmap->n_eq; ++i) {
4273 if (isl_int_is_zero(bmap->eq[i][offset]))
4274 continue;
4275 if (isl_seq_first_non_zero(bmap->eq[i] + offset + 1,
4276 1 + total - (offset + 1)) != -1)
4277 continue;
4278 break;
4280 if (i >= bmap->n_eq)
4281 isl_die(isl_basic_map_get_ctx(bmap), isl_error_invalid,
4282 "unable to find suitable equality", goto error);
4283 ls = isl_basic_map_get_local_space(bmap);
4284 aff = isl_aff_alloc(isl_local_space_domain(ls));
4285 if (!aff)
4286 goto error;
4287 if (isl_int_is_neg(bmap->eq[i][offset]))
4288 isl_seq_cpy(aff->v->el + 1, bmap->eq[i], offset);
4289 else
4290 isl_seq_neg(aff->v->el + 1, bmap->eq[i], offset);
4291 isl_seq_clr(aff->v->el + 1 + offset, aff->v->size - (1 + offset));
4292 isl_int_abs(aff->v->el[0], bmap->eq[i][offset]);
4293 isl_basic_map_free(bmap);
4295 aff = isl_aff_remove_unused_divs(aff);
4296 return aff;
4297 error:
4298 isl_basic_map_free(bmap);
4299 return NULL;
4302 /* Given a basic map where each output dimension is defined
4303 * in terms of the parameters and input dimensions using an equality,
4304 * extract an isl_multi_aff that expresses the output dimensions in terms
4305 * of the parameters and input dimensions.
4307 static __isl_give isl_multi_aff *extract_isl_multi_aff_from_basic_map(
4308 __isl_take isl_basic_map *bmap)
4310 int i;
4311 unsigned n_out;
4312 isl_multi_aff *ma;
4314 if (!bmap)
4315 return NULL;
4317 ma = isl_multi_aff_alloc(isl_basic_map_get_space(bmap));
4318 n_out = isl_basic_map_dim(bmap, isl_dim_out);
4320 for (i = 0; i < n_out; ++i) {
4321 isl_basic_map *bmap_i;
4322 isl_aff *aff;
4324 bmap_i = isl_basic_map_copy(bmap);
4325 bmap_i = isl_basic_map_project_out(bmap_i, isl_dim_out,
4326 i + 1, n_out - (1 + i));
4327 bmap_i = isl_basic_map_project_out(bmap_i, isl_dim_out, 0, i);
4328 aff = extract_isl_aff_from_basic_map(bmap_i);
4329 ma = isl_multi_aff_set_aff(ma, i, aff);
4332 isl_basic_map_free(bmap);
4334 return ma;
4337 /* Given a basic set where each set dimension is defined
4338 * in terms of the parameters using an equality,
4339 * extract an isl_multi_aff that expresses the set dimensions in terms
4340 * of the parameters.
4342 __isl_give isl_multi_aff *isl_multi_aff_from_basic_set_equalities(
4343 __isl_take isl_basic_set *bset)
4345 return extract_isl_multi_aff_from_basic_map(bset);
4348 /* Create an isl_pw_multi_aff that is equivalent to
4349 * isl_map_intersect_domain(isl_map_from_basic_map(bmap), domain).
4350 * The given basic map is such that each output dimension is defined
4351 * in terms of the parameters and input dimensions using an equality.
4353 * Since some applications expect the result of isl_pw_multi_aff_from_map
4354 * to only contain integer affine expressions, we compute the floor
4355 * of the expression before returning.
4357 static __isl_give isl_pw_multi_aff *plain_pw_multi_aff_from_map(
4358 __isl_take isl_set *domain, __isl_take isl_basic_map *bmap)
4360 isl_multi_aff *ma;
4362 ma = extract_isl_multi_aff_from_basic_map(bmap);
4363 ma = isl_multi_aff_floor(ma);
4364 return isl_pw_multi_aff_alloc(domain, ma);
4367 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
4368 * This obviously only works if the input "map" is single-valued.
4369 * If so, we compute the lexicographic minimum of the image in the form
4370 * of an isl_pw_multi_aff. Since the image is unique, it is equal
4371 * to its lexicographic minimum.
4372 * If the input is not single-valued, we produce an error.
4374 static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_base(
4375 __isl_take isl_map *map)
4377 int i;
4378 int sv;
4379 isl_pw_multi_aff *pma;
4381 sv = isl_map_is_single_valued(map);
4382 if (sv < 0)
4383 goto error;
4384 if (!sv)
4385 isl_die(isl_map_get_ctx(map), isl_error_invalid,
4386 "map is not single-valued", goto error);
4387 map = isl_map_make_disjoint(map);
4388 if (!map)
4389 return NULL;
4391 pma = isl_pw_multi_aff_empty(isl_map_get_space(map));
4393 for (i = 0; i < map->n; ++i) {
4394 isl_pw_multi_aff *pma_i;
4395 isl_basic_map *bmap;
4396 bmap = isl_basic_map_copy(map->p[i]);
4397 pma_i = isl_basic_map_lexmin_pw_multi_aff(bmap);
4398 pma = isl_pw_multi_aff_add_disjoint(pma, pma_i);
4401 isl_map_free(map);
4402 return pma;
4403 error:
4404 isl_map_free(map);
4405 return NULL;
4408 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
4409 * taking into account that the output dimension at position "d"
4410 * can be represented as
4412 * x = floor((e(...) + c1) / m)
4414 * given that constraint "i" is of the form
4416 * e(...) + c1 - m x >= 0
4419 * Let "map" be of the form
4421 * A -> B
4423 * We construct a mapping
4425 * A -> [A -> x = floor(...)]
4427 * apply that to the map, obtaining
4429 * [A -> x = floor(...)] -> B
4431 * and equate dimension "d" to x.
4432 * We then compute a isl_pw_multi_aff representation of the resulting map
4433 * and plug in the mapping above.
4435 static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_div(
4436 __isl_take isl_map *map, __isl_take isl_basic_map *hull, int d, int i)
4438 isl_ctx *ctx;
4439 isl_space *space;
4440 isl_local_space *ls;
4441 isl_multi_aff *ma;
4442 isl_aff *aff;
4443 isl_vec *v;
4444 isl_map *insert;
4445 int offset;
4446 int n;
4447 int n_in;
4448 isl_pw_multi_aff *pma;
4449 int is_set;
4451 is_set = isl_map_is_set(map);
4453 offset = isl_basic_map_offset(hull, isl_dim_out);
4454 ctx = isl_map_get_ctx(map);
4455 space = isl_space_domain(isl_map_get_space(map));
4456 n_in = isl_space_dim(space, isl_dim_set);
4457 n = isl_space_dim(space, isl_dim_all);
4459 v = isl_vec_alloc(ctx, 1 + 1 + n);
4460 if (v) {
4461 isl_int_neg(v->el[0], hull->ineq[i][offset + d]);
4462 isl_seq_cpy(v->el + 1, hull->ineq[i], 1 + n);
4464 isl_basic_map_free(hull);
4466 ls = isl_local_space_from_space(isl_space_copy(space));
4467 aff = isl_aff_alloc_vec(ls, v);
4468 aff = isl_aff_floor(aff);
4469 if (is_set) {
4470 isl_space_free(space);
4471 ma = isl_multi_aff_from_aff(aff);
4472 } else {
4473 ma = isl_multi_aff_identity(isl_space_map_from_set(space));
4474 ma = isl_multi_aff_range_product(ma,
4475 isl_multi_aff_from_aff(aff));
4478 insert = isl_map_from_multi_aff(isl_multi_aff_copy(ma));
4479 map = isl_map_apply_domain(map, insert);
4480 map = isl_map_equate(map, isl_dim_in, n_in, isl_dim_out, d);
4481 pma = isl_pw_multi_aff_from_map(map);
4482 pma = isl_pw_multi_aff_pullback_multi_aff(pma, ma);
4484 return pma;
4487 /* Is constraint "c" of the form
4489 * e(...) + c1 - m x >= 0
4491 * or
4493 * -e(...) + c2 + m x >= 0
4495 * where m > 1 and e only depends on parameters and input dimemnsions?
4497 * "offset" is the offset of the output dimensions
4498 * "pos" is the position of output dimension x.
4500 static int is_potential_div_constraint(isl_int *c, int offset, int d, int total)
4502 if (isl_int_is_zero(c[offset + d]))
4503 return 0;
4504 if (isl_int_is_one(c[offset + d]))
4505 return 0;
4506 if (isl_int_is_negone(c[offset + d]))
4507 return 0;
4508 if (isl_seq_first_non_zero(c + offset, d) != -1)
4509 return 0;
4510 if (isl_seq_first_non_zero(c + offset + d + 1,
4511 total - (offset + d + 1)) != -1)
4512 return 0;
4513 return 1;
4516 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
4518 * As a special case, we first check if there is any pair of constraints,
4519 * shared by all the basic maps in "map" that force a given dimension
4520 * to be equal to the floor of some affine combination of the input dimensions.
4522 * In particular, if we can find two constraints
4524 * e(...) + c1 - m x >= 0 i.e., m x <= e(...) + c1
4526 * and
4528 * -e(...) + c2 + m x >= 0 i.e., m x >= e(...) - c2
4530 * where m > 1 and e only depends on parameters and input dimemnsions,
4531 * and such that
4533 * c1 + c2 < m i.e., -c2 >= c1 - (m - 1)
4535 * then we know that we can take
4537 * x = floor((e(...) + c1) / m)
4539 * without having to perform any computation.
4541 * Note that we know that
4543 * c1 + c2 >= 1
4545 * If c1 + c2 were 0, then we would have detected an equality during
4546 * simplification. If c1 + c2 were negative, then we would have detected
4547 * a contradiction.
4549 static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_check_div(
4550 __isl_take isl_map *map)
4552 int d, dim;
4553 int i, j, n;
4554 int offset, total;
4555 isl_int sum;
4556 isl_basic_map *hull;
4558 hull = isl_map_unshifted_simple_hull(isl_map_copy(map));
4559 if (!hull)
4560 goto error;
4562 isl_int_init(sum);
4563 dim = isl_map_dim(map, isl_dim_out);
4564 offset = isl_basic_map_offset(hull, isl_dim_out);
4565 total = 1 + isl_basic_map_total_dim(hull);
4566 n = hull->n_ineq;
4567 for (d = 0; d < dim; ++d) {
4568 for (i = 0; i < n; ++i) {
4569 if (!is_potential_div_constraint(hull->ineq[i],
4570 offset, d, total))
4571 continue;
4572 for (j = i + 1; j < n; ++j) {
4573 if (!isl_seq_is_neg(hull->ineq[i] + 1,
4574 hull->ineq[j] + 1, total - 1))
4575 continue;
4576 isl_int_add(sum, hull->ineq[i][0],
4577 hull->ineq[j][0]);
4578 if (isl_int_abs_lt(sum,
4579 hull->ineq[i][offset + d]))
4580 break;
4583 if (j >= n)
4584 continue;
4585 isl_int_clear(sum);
4586 if (isl_int_is_pos(hull->ineq[j][offset + d]))
4587 j = i;
4588 return pw_multi_aff_from_map_div(map, hull, d, j);
4591 isl_int_clear(sum);
4592 isl_basic_map_free(hull);
4593 return pw_multi_aff_from_map_base(map);
4594 error:
4595 isl_map_free(map);
4596 isl_basic_map_free(hull);
4597 return NULL;
4600 /* Given an affine expression
4602 * [A -> B] -> f(A,B)
4604 * construct an isl_multi_aff
4606 * [A -> B] -> B'
4608 * such that dimension "d" in B' is set to "aff" and the remaining
4609 * dimensions are set equal to the corresponding dimensions in B.
4610 * "n_in" is the dimension of the space A.
4611 * "n_out" is the dimension of the space B.
4613 * If "is_set" is set, then the affine expression is of the form
4615 * [B] -> f(B)
4617 * and we construct an isl_multi_aff
4619 * B -> B'
4621 static __isl_give isl_multi_aff *range_map(__isl_take isl_aff *aff, int d,
4622 unsigned n_in, unsigned n_out, int is_set)
4624 int i;
4625 isl_multi_aff *ma;
4626 isl_space *space, *space2;
4627 isl_local_space *ls;
4629 space = isl_aff_get_domain_space(aff);
4630 ls = isl_local_space_from_space(isl_space_copy(space));
4631 space2 = isl_space_copy(space);
4632 if (!is_set)
4633 space2 = isl_space_range(isl_space_unwrap(space2));
4634 space = isl_space_map_from_domain_and_range(space, space2);
4635 ma = isl_multi_aff_alloc(space);
4636 ma = isl_multi_aff_set_aff(ma, d, aff);
4638 for (i = 0; i < n_out; ++i) {
4639 if (i == d)
4640 continue;
4641 aff = isl_aff_var_on_domain(isl_local_space_copy(ls),
4642 isl_dim_set, n_in + i);
4643 ma = isl_multi_aff_set_aff(ma, i, aff);
4646 isl_local_space_free(ls);
4648 return ma;
4651 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map,
4652 * taking into account that the dimension at position "d" can be written as
4654 * x = m a + f(..) (1)
4656 * where m is equal to "gcd".
4657 * "i" is the index of the equality in "hull" that defines f(..).
4658 * In particular, the equality is of the form
4660 * f(..) - x + m g(existentials) = 0
4662 * or
4664 * -f(..) + x + m g(existentials) = 0
4666 * We basically plug (1) into "map", resulting in a map with "a"
4667 * in the range instead of "x". The corresponding isl_pw_multi_aff
4668 * defining "a" is then plugged back into (1) to obtain a definition fro "x".
4670 * Specifically, given the input map
4672 * A -> B
4674 * We first wrap it into a set
4676 * [A -> B]
4678 * and define (1) on top of the corresponding space, resulting in "aff".
4679 * We use this to create an isl_multi_aff that maps the output position "d"
4680 * from "a" to "x", leaving all other (intput and output) dimensions unchanged.
4681 * We plug this into the wrapped map, unwrap the result and compute the
4682 * corresponding isl_pw_multi_aff.
4683 * The result is an expression
4685 * A -> T(A)
4687 * We adjust that to
4689 * A -> [A -> T(A)]
4691 * so that we can plug that into "aff", after extending the latter to
4692 * a mapping
4694 * [A -> B] -> B'
4697 * If "map" is actually a set, then there is no "A" space, meaning
4698 * that we do not need to perform any wrapping, and that the result
4699 * of the recursive call is of the form
4701 * [T]
4703 * which is plugged into a mapping of the form
4705 * B -> B'
4707 static __isl_give isl_pw_multi_aff *pw_multi_aff_from_map_stride(
4708 __isl_take isl_map *map, __isl_take isl_basic_map *hull, int d, int i,
4709 isl_int gcd)
4711 isl_set *set;
4712 isl_space *space;
4713 isl_local_space *ls;
4714 isl_aff *aff;
4715 isl_multi_aff *ma;
4716 isl_pw_multi_aff *pma, *id;
4717 unsigned n_in;
4718 unsigned o_out;
4719 unsigned n_out;
4720 int is_set;
4722 is_set = isl_map_is_set(map);
4724 n_in = isl_basic_map_dim(hull, isl_dim_in);
4725 n_out = isl_basic_map_dim(hull, isl_dim_out);
4726 o_out = isl_basic_map_offset(hull, isl_dim_out);
4728 if (is_set)
4729 set = map;
4730 else
4731 set = isl_map_wrap(map);
4732 space = isl_space_map_from_set(isl_set_get_space(set));
4733 ma = isl_multi_aff_identity(space);
4734 ls = isl_local_space_from_space(isl_set_get_space(set));
4735 aff = isl_aff_alloc(ls);
4736 if (aff) {
4737 isl_int_set_si(aff->v->el[0], 1);
4738 if (isl_int_is_one(hull->eq[i][o_out + d]))
4739 isl_seq_neg(aff->v->el + 1, hull->eq[i],
4740 aff->v->size - 1);
4741 else
4742 isl_seq_cpy(aff->v->el + 1, hull->eq[i],
4743 aff->v->size - 1);
4744 isl_int_set(aff->v->el[1 + o_out + d], gcd);
4746 ma = isl_multi_aff_set_aff(ma, n_in + d, isl_aff_copy(aff));
4747 set = isl_set_preimage_multi_aff(set, ma);
4749 ma = range_map(aff, d, n_in, n_out, is_set);
4751 if (is_set)
4752 map = set;
4753 else
4754 map = isl_set_unwrap(set);
4755 pma = isl_pw_multi_aff_from_map(set);
4757 if (!is_set) {
4758 space = isl_pw_multi_aff_get_domain_space(pma);
4759 space = isl_space_map_from_set(space);
4760 id = isl_pw_multi_aff_identity(space);
4761 pma = isl_pw_multi_aff_range_product(id, pma);
4763 id = isl_pw_multi_aff_from_multi_aff(ma);
4764 pma = isl_pw_multi_aff_pullback_pw_multi_aff(id, pma);
4766 isl_basic_map_free(hull);
4767 return pma;
4770 /* Try and create an isl_pw_multi_aff that is equivalent to the given isl_map.
4772 * As a special case, we first check if all output dimensions are uniquely
4773 * defined in terms of the parameters and input dimensions over the entire
4774 * domain. If so, we extract the desired isl_pw_multi_aff directly
4775 * from the affine hull of "map" and its domain.
4777 * Otherwise, we check if any of the output dimensions is "strided".
4778 * That is, we check if can be written as
4780 * x = m a + f(..)
4782 * with m greater than 1, a some combination of existentiall quantified
4783 * variables and f and expression in the parameters and input dimensions.
4784 * If so, we remove the stride in pw_multi_aff_from_map_stride.
4786 * Otherwise, we continue with pw_multi_aff_from_map_check_div for a further
4787 * special case.
4789 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_map(__isl_take isl_map *map)
4791 int i, j;
4792 int sv;
4793 isl_basic_map *hull;
4794 unsigned n_out;
4795 unsigned o_out;
4796 unsigned n_div;
4797 unsigned o_div;
4798 isl_int gcd;
4800 if (!map)
4801 return NULL;
4803 hull = isl_map_affine_hull(isl_map_copy(map));
4804 sv = isl_basic_map_plain_is_single_valued(hull);
4805 if (sv >= 0 && sv)
4806 return plain_pw_multi_aff_from_map(isl_map_domain(map), hull);
4807 if (sv < 0)
4808 hull = isl_basic_map_free(hull);
4809 if (!hull)
4810 goto error;
4812 n_div = isl_basic_map_dim(hull, isl_dim_div);
4813 o_div = isl_basic_map_offset(hull, isl_dim_div);
4815 if (n_div == 0) {
4816 isl_basic_map_free(hull);
4817 return pw_multi_aff_from_map_check_div(map);
4820 isl_int_init(gcd);
4822 n_out = isl_basic_map_dim(hull, isl_dim_out);
4823 o_out = isl_basic_map_offset(hull, isl_dim_out);
4825 for (i = 0; i < n_out; ++i) {
4826 for (j = 0; j < hull->n_eq; ++j) {
4827 isl_int *eq = hull->eq[j];
4828 isl_pw_multi_aff *res;
4830 if (!isl_int_is_one(eq[o_out + i]) &&
4831 !isl_int_is_negone(eq[o_out + i]))
4832 continue;
4833 if (isl_seq_first_non_zero(eq + o_out, i) != -1)
4834 continue;
4835 if (isl_seq_first_non_zero(eq + o_out + i + 1,
4836 n_out - (i + 1)) != -1)
4837 continue;
4838 isl_seq_gcd(eq + o_div, n_div, &gcd);
4839 if (isl_int_is_zero(gcd))
4840 continue;
4841 if (isl_int_is_one(gcd))
4842 continue;
4844 res = pw_multi_aff_from_map_stride(map, hull,
4845 i, j, gcd);
4846 isl_int_clear(gcd);
4847 return res;
4851 isl_int_clear(gcd);
4852 isl_basic_map_free(hull);
4853 return pw_multi_aff_from_map_check_div(map);
4854 error:
4855 isl_map_free(map);
4856 return NULL;
4859 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_set(__isl_take isl_set *set)
4861 return isl_pw_multi_aff_from_map(set);
4864 /* Convert "map" into an isl_pw_multi_aff (if possible) and
4865 * add it to *user.
4867 static int pw_multi_aff_from_map(__isl_take isl_map *map, void *user)
4869 isl_union_pw_multi_aff **upma = user;
4870 isl_pw_multi_aff *pma;
4872 pma = isl_pw_multi_aff_from_map(map);
4873 *upma = isl_union_pw_multi_aff_add_pw_multi_aff(*upma, pma);
4875 return *upma ? 0 : -1;
4878 /* Try and create an isl_union_pw_multi_aff that is equivalent
4879 * to the given isl_union_map.
4880 * The isl_union_map is required to be single-valued in each space.
4881 * Otherwise, an error is produced.
4883 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_from_union_map(
4884 __isl_take isl_union_map *umap)
4886 isl_space *space;
4887 isl_union_pw_multi_aff *upma;
4889 space = isl_union_map_get_space(umap);
4890 upma = isl_union_pw_multi_aff_empty(space);
4891 if (isl_union_map_foreach_map(umap, &pw_multi_aff_from_map, &upma) < 0)
4892 upma = isl_union_pw_multi_aff_free(upma);
4893 isl_union_map_free(umap);
4895 return upma;
4898 /* Try and create an isl_union_pw_multi_aff that is equivalent
4899 * to the given isl_union_set.
4900 * The isl_union_set is required to be a singleton in each space.
4901 * Otherwise, an error is produced.
4903 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_from_union_set(
4904 __isl_take isl_union_set *uset)
4906 return isl_union_pw_multi_aff_from_union_map(uset);
4909 /* Return the piecewise affine expression "set ? 1 : 0".
4911 __isl_give isl_pw_aff *isl_set_indicator_function(__isl_take isl_set *set)
4913 isl_pw_aff *pa;
4914 isl_space *space = isl_set_get_space(set);
4915 isl_local_space *ls = isl_local_space_from_space(space);
4916 isl_aff *zero = isl_aff_zero_on_domain(isl_local_space_copy(ls));
4917 isl_aff *one = isl_aff_zero_on_domain(ls);
4919 one = isl_aff_add_constant_si(one, 1);
4920 pa = isl_pw_aff_alloc(isl_set_copy(set), one);
4921 set = isl_set_complement(set);
4922 pa = isl_pw_aff_add_disjoint(pa, isl_pw_aff_alloc(set, zero));
4924 return pa;
4927 /* Plug in "subs" for dimension "type", "pos" of "aff".
4929 * Let i be the dimension to replace and let "subs" be of the form
4931 * f/d
4933 * and "aff" of the form
4935 * (a i + g)/m
4937 * The result is
4939 * (a f + d g')/(m d)
4941 * where g' is the result of plugging in "subs" in each of the integer
4942 * divisions in g.
4944 __isl_give isl_aff *isl_aff_substitute(__isl_take isl_aff *aff,
4945 enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
4947 isl_ctx *ctx;
4948 isl_int v;
4950 aff = isl_aff_cow(aff);
4951 if (!aff || !subs)
4952 return isl_aff_free(aff);
4954 ctx = isl_aff_get_ctx(aff);
4955 if (!isl_space_is_equal(aff->ls->dim, subs->ls->dim))
4956 isl_die(ctx, isl_error_invalid,
4957 "spaces don't match", return isl_aff_free(aff));
4958 if (isl_local_space_dim(subs->ls, isl_dim_div) != 0)
4959 isl_die(ctx, isl_error_unsupported,
4960 "cannot handle divs yet", return isl_aff_free(aff));
4962 aff->ls = isl_local_space_substitute(aff->ls, type, pos, subs);
4963 if (!aff->ls)
4964 return isl_aff_free(aff);
4966 aff->v = isl_vec_cow(aff->v);
4967 if (!aff->v)
4968 return isl_aff_free(aff);
4970 pos += isl_local_space_offset(aff->ls, type);
4972 isl_int_init(v);
4973 isl_seq_substitute(aff->v->el, pos, subs->v->el,
4974 aff->v->size, subs->v->size, v);
4975 isl_int_clear(v);
4977 return aff;
4980 /* Plug in "subs" for dimension "type", "pos" in each of the affine
4981 * expressions in "maff".
4983 __isl_give isl_multi_aff *isl_multi_aff_substitute(
4984 __isl_take isl_multi_aff *maff, enum isl_dim_type type, unsigned pos,
4985 __isl_keep isl_aff *subs)
4987 int i;
4989 maff = isl_multi_aff_cow(maff);
4990 if (!maff || !subs)
4991 return isl_multi_aff_free(maff);
4993 if (type == isl_dim_in)
4994 type = isl_dim_set;
4996 for (i = 0; i < maff->n; ++i) {
4997 maff->p[i] = isl_aff_substitute(maff->p[i], type, pos, subs);
4998 if (!maff->p[i])
4999 return isl_multi_aff_free(maff);
5002 return maff;
5005 /* Plug in "subs" for dimension "type", "pos" of "pma".
5007 * pma is of the form
5009 * A_i(v) -> M_i(v)
5011 * while subs is of the form
5013 * v' = B_j(v) -> S_j
5015 * Each pair i,j such that C_ij = A_i \cap B_i is non-empty
5016 * has a contribution in the result, in particular
5018 * C_ij(S_j) -> M_i(S_j)
5020 * Note that plugging in S_j in C_ij may also result in an empty set
5021 * and this contribution should simply be discarded.
5023 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_substitute(
5024 __isl_take isl_pw_multi_aff *pma, enum isl_dim_type type, unsigned pos,
5025 __isl_keep isl_pw_aff *subs)
5027 int i, j, n;
5028 isl_pw_multi_aff *res;
5030 if (!pma || !subs)
5031 return isl_pw_multi_aff_free(pma);
5033 n = pma->n * subs->n;
5034 res = isl_pw_multi_aff_alloc_size(isl_space_copy(pma->dim), n);
5036 for (i = 0; i < pma->n; ++i) {
5037 for (j = 0; j < subs->n; ++j) {
5038 isl_set *common;
5039 isl_multi_aff *res_ij;
5040 int empty;
5042 common = isl_set_intersect(
5043 isl_set_copy(pma->p[i].set),
5044 isl_set_copy(subs->p[j].set));
5045 common = isl_set_substitute(common,
5046 type, pos, subs->p[j].aff);
5047 empty = isl_set_plain_is_empty(common);
5048 if (empty < 0 || empty) {
5049 isl_set_free(common);
5050 if (empty < 0)
5051 goto error;
5052 continue;
5055 res_ij = isl_multi_aff_substitute(
5056 isl_multi_aff_copy(pma->p[i].maff),
5057 type, pos, subs->p[j].aff);
5059 res = isl_pw_multi_aff_add_piece(res, common, res_ij);
5063 isl_pw_multi_aff_free(pma);
5064 return res;
5065 error:
5066 isl_pw_multi_aff_free(pma);
5067 isl_pw_multi_aff_free(res);
5068 return NULL;
5071 /* Compute the preimage of a range of dimensions in the affine expression "src"
5072 * under "ma" and put the result in "dst". The number of dimensions in "src"
5073 * that precede the range is given by "n_before". The number of dimensions
5074 * in the range is given by the number of output dimensions of "ma".
5075 * The number of dimensions that follow the range is given by "n_after".
5076 * If "has_denom" is set (to one),
5077 * then "src" and "dst" have an extra initial denominator.
5078 * "n_div_ma" is the number of existentials in "ma"
5079 * "n_div_bset" is the number of existentials in "src"
5080 * The resulting "dst" (which is assumed to have been allocated by
5081 * the caller) contains coefficients for both sets of existentials,
5082 * first those in "ma" and then those in "src".
5083 * f, c1, c2 and g are temporary objects that have been initialized
5084 * by the caller.
5086 * Let src represent the expression
5088 * (a(p) + f_u u + b v + f_w w + c(divs))/d
5090 * and let ma represent the expressions
5092 * v_i = (r_i(p) + s_i(y) + t_i(divs'))/m_i
5094 * We start out with the following expression for dst:
5096 * (a(p) + f_u u + 0 y + f_w w + 0 divs' + c(divs) + f \sum_i b_i v_i)/d
5098 * with the multiplication factor f initially equal to 1
5099 * and f \sum_i b_i v_i kept separately.
5100 * For each x_i that we substitute, we multiply the numerator
5101 * (and denominator) of dst by c_1 = m_i and add the numerator
5102 * of the x_i expression multiplied by c_2 = f b_i,
5103 * after removing the common factors of c_1 and c_2.
5104 * The multiplication factor f also needs to be multiplied by c_1
5105 * for the next x_j, j > i.
5107 void isl_seq_preimage(isl_int *dst, isl_int *src,
5108 __isl_keep isl_multi_aff *ma, int n_before, int n_after,
5109 int n_div_ma, int n_div_bmap,
5110 isl_int f, isl_int c1, isl_int c2, isl_int g, int has_denom)
5112 int i;
5113 int n_param, n_in, n_out;
5114 int o_dst, o_src;
5116 n_param = isl_multi_aff_dim(ma, isl_dim_param);
5117 n_in = isl_multi_aff_dim(ma, isl_dim_in);
5118 n_out = isl_multi_aff_dim(ma, isl_dim_out);
5120 isl_seq_cpy(dst, src, has_denom + 1 + n_param + n_before);
5121 o_dst = o_src = has_denom + 1 + n_param + n_before;
5122 isl_seq_clr(dst + o_dst, n_in);
5123 o_dst += n_in;
5124 o_src += n_out;
5125 isl_seq_cpy(dst + o_dst, src + o_src, n_after);
5126 o_dst += n_after;
5127 o_src += n_after;
5128 isl_seq_clr(dst + o_dst, n_div_ma);
5129 o_dst += n_div_ma;
5130 isl_seq_cpy(dst + o_dst, src + o_src, n_div_bmap);
5132 isl_int_set_si(f, 1);
5134 for (i = 0; i < n_out; ++i) {
5135 int offset = has_denom + 1 + n_param + n_before + i;
5137 if (isl_int_is_zero(src[offset]))
5138 continue;
5139 isl_int_set(c1, ma->p[i]->v->el[0]);
5140 isl_int_mul(c2, f, src[offset]);
5141 isl_int_gcd(g, c1, c2);
5142 isl_int_divexact(c1, c1, g);
5143 isl_int_divexact(c2, c2, g);
5145 isl_int_mul(f, f, c1);
5146 o_dst = has_denom;
5147 o_src = 1;
5148 isl_seq_combine(dst + o_dst, c1, dst + o_dst,
5149 c2, ma->p[i]->v->el + o_src, 1 + n_param);
5150 o_dst += 1 + n_param;
5151 o_src += 1 + n_param;
5152 isl_seq_scale(dst + o_dst, dst + o_dst, c1, n_before);
5153 o_dst += n_before;
5154 isl_seq_combine(dst + o_dst, c1, dst + o_dst,
5155 c2, ma->p[i]->v->el + o_src, n_in);
5156 o_dst += n_in;
5157 o_src += n_in;
5158 isl_seq_scale(dst + o_dst, dst + o_dst, c1, n_after);
5159 o_dst += n_after;
5160 isl_seq_combine(dst + o_dst, c1, dst + o_dst,
5161 c2, ma->p[i]->v->el + o_src, n_div_ma);
5162 o_dst += n_div_ma;
5163 o_src += n_div_ma;
5164 isl_seq_scale(dst + o_dst, dst + o_dst, c1, n_div_bmap);
5165 if (has_denom)
5166 isl_int_mul(dst[0], dst[0], c1);
5170 /* Compute the pullback of "aff" by the function represented by "ma".
5171 * In other words, plug in "ma" in "aff". The result is an affine expression
5172 * defined over the domain space of "ma".
5174 * If "aff" is represented by
5176 * (a(p) + b x + c(divs))/d
5178 * and ma is represented by
5180 * x = D(p) + F(y) + G(divs')
5182 * then the result is
5184 * (a(p) + b D(p) + b F(y) + b G(divs') + c(divs))/d
5186 * The divs in the local space of the input are similarly adjusted
5187 * through a call to isl_local_space_preimage_multi_aff.
5189 __isl_give isl_aff *isl_aff_pullback_multi_aff(__isl_take isl_aff *aff,
5190 __isl_take isl_multi_aff *ma)
5192 isl_aff *res = NULL;
5193 isl_local_space *ls;
5194 int n_div_aff, n_div_ma;
5195 isl_int f, c1, c2, g;
5197 ma = isl_multi_aff_align_divs(ma);
5198 if (!aff || !ma)
5199 goto error;
5201 n_div_aff = isl_aff_dim(aff, isl_dim_div);
5202 n_div_ma = ma->n ? isl_aff_dim(ma->p[0], isl_dim_div) : 0;
5204 ls = isl_aff_get_domain_local_space(aff);
5205 ls = isl_local_space_preimage_multi_aff(ls, isl_multi_aff_copy(ma));
5206 res = isl_aff_alloc(ls);
5207 if (!res)
5208 goto error;
5210 isl_int_init(f);
5211 isl_int_init(c1);
5212 isl_int_init(c2);
5213 isl_int_init(g);
5215 isl_seq_preimage(res->v->el, aff->v->el, ma, 0, 0, n_div_ma, n_div_aff,
5216 f, c1, c2, g, 1);
5218 isl_int_clear(f);
5219 isl_int_clear(c1);
5220 isl_int_clear(c2);
5221 isl_int_clear(g);
5223 isl_aff_free(aff);
5224 isl_multi_aff_free(ma);
5225 res = isl_aff_normalize(res);
5226 return res;
5227 error:
5228 isl_aff_free(aff);
5229 isl_multi_aff_free(ma);
5230 isl_aff_free(res);
5231 return NULL;
5234 /* Compute the pullback of "aff1" by the function represented by "aff2".
5235 * In other words, plug in "aff2" in "aff1". The result is an affine expression
5236 * defined over the domain space of "aff1".
5238 * The domain of "aff1" should match the range of "aff2", which means
5239 * that it should be single-dimensional.
5241 __isl_give isl_aff *isl_aff_pullback_aff(__isl_take isl_aff *aff1,
5242 __isl_take isl_aff *aff2)
5244 isl_multi_aff *ma;
5246 ma = isl_multi_aff_from_aff(aff2);
5247 return isl_aff_pullback_multi_aff(aff1, ma);
5250 /* Compute the pullback of "ma1" by the function represented by "ma2".
5251 * In other words, plug in "ma2" in "ma1".
5253 * The parameters of "ma1" and "ma2" are assumed to have been aligned.
5255 static __isl_give isl_multi_aff *isl_multi_aff_pullback_multi_aff_aligned(
5256 __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2)
5258 int i;
5259 isl_space *space = NULL;
5261 ma2 = isl_multi_aff_align_divs(ma2);
5262 ma1 = isl_multi_aff_cow(ma1);
5263 if (!ma1 || !ma2)
5264 goto error;
5266 space = isl_space_join(isl_multi_aff_get_space(ma2),
5267 isl_multi_aff_get_space(ma1));
5269 for (i = 0; i < ma1->n; ++i) {
5270 ma1->p[i] = isl_aff_pullback_multi_aff(ma1->p[i],
5271 isl_multi_aff_copy(ma2));
5272 if (!ma1->p[i])
5273 goto error;
5276 ma1 = isl_multi_aff_reset_space(ma1, space);
5277 isl_multi_aff_free(ma2);
5278 return ma1;
5279 error:
5280 isl_space_free(space);
5281 isl_multi_aff_free(ma2);
5282 isl_multi_aff_free(ma1);
5283 return NULL;
5286 /* Compute the pullback of "ma1" by the function represented by "ma2".
5287 * In other words, plug in "ma2" in "ma1".
5289 __isl_give isl_multi_aff *isl_multi_aff_pullback_multi_aff(
5290 __isl_take isl_multi_aff *ma1, __isl_take isl_multi_aff *ma2)
5292 return isl_multi_aff_align_params_multi_multi_and(ma1, ma2,
5293 &isl_multi_aff_pullback_multi_aff_aligned);
5296 /* Extend the local space of "dst" to include the divs
5297 * in the local space of "src".
5299 __isl_give isl_aff *isl_aff_align_divs(__isl_take isl_aff *dst,
5300 __isl_keep isl_aff *src)
5302 isl_ctx *ctx;
5303 int *exp1 = NULL;
5304 int *exp2 = NULL;
5305 isl_mat *div;
5307 if (!src || !dst)
5308 return isl_aff_free(dst);
5310 ctx = isl_aff_get_ctx(src);
5311 if (!isl_space_is_equal(src->ls->dim, dst->ls->dim))
5312 isl_die(ctx, isl_error_invalid,
5313 "spaces don't match", goto error);
5315 if (src->ls->div->n_row == 0)
5316 return dst;
5318 exp1 = isl_alloc_array(ctx, int, src->ls->div->n_row);
5319 exp2 = isl_alloc_array(ctx, int, dst->ls->div->n_row);
5320 if (!exp1 || (dst->ls->div->n_row && !exp2))
5321 goto error;
5323 div = isl_merge_divs(src->ls->div, dst->ls->div, exp1, exp2);
5324 dst = isl_aff_expand_divs(dst, div, exp2);
5325 free(exp1);
5326 free(exp2);
5328 return dst;
5329 error:
5330 free(exp1);
5331 free(exp2);
5332 return isl_aff_free(dst);
5335 /* Adjust the local spaces of the affine expressions in "maff"
5336 * such that they all have the save divs.
5338 __isl_give isl_multi_aff *isl_multi_aff_align_divs(
5339 __isl_take isl_multi_aff *maff)
5341 int i;
5343 if (!maff)
5344 return NULL;
5345 if (maff->n == 0)
5346 return maff;
5347 maff = isl_multi_aff_cow(maff);
5348 if (!maff)
5349 return NULL;
5351 for (i = 1; i < maff->n; ++i)
5352 maff->p[0] = isl_aff_align_divs(maff->p[0], maff->p[i]);
5353 for (i = 1; i < maff->n; ++i) {
5354 maff->p[i] = isl_aff_align_divs(maff->p[i], maff->p[0]);
5355 if (!maff->p[i])
5356 return isl_multi_aff_free(maff);
5359 return maff;
5362 __isl_give isl_aff *isl_aff_lift(__isl_take isl_aff *aff)
5364 aff = isl_aff_cow(aff);
5365 if (!aff)
5366 return NULL;
5368 aff->ls = isl_local_space_lift(aff->ls);
5369 if (!aff->ls)
5370 return isl_aff_free(aff);
5372 return aff;
5375 /* Lift "maff" to a space with extra dimensions such that the result
5376 * has no more existentially quantified variables.
5377 * If "ls" is not NULL, then *ls is assigned the local space that lies
5378 * at the basis of the lifting applied to "maff".
5380 __isl_give isl_multi_aff *isl_multi_aff_lift(__isl_take isl_multi_aff *maff,
5381 __isl_give isl_local_space **ls)
5383 int i;
5384 isl_space *space;
5385 unsigned n_div;
5387 if (ls)
5388 *ls = NULL;
5390 if (!maff)
5391 return NULL;
5393 if (maff->n == 0) {
5394 if (ls) {
5395 isl_space *space = isl_multi_aff_get_domain_space(maff);
5396 *ls = isl_local_space_from_space(space);
5397 if (!*ls)
5398 return isl_multi_aff_free(maff);
5400 return maff;
5403 maff = isl_multi_aff_cow(maff);
5404 maff = isl_multi_aff_align_divs(maff);
5405 if (!maff)
5406 return NULL;
5408 n_div = isl_aff_dim(maff->p[0], isl_dim_div);
5409 space = isl_multi_aff_get_space(maff);
5410 space = isl_space_lift(isl_space_domain(space), n_div);
5411 space = isl_space_extend_domain_with_range(space,
5412 isl_multi_aff_get_space(maff));
5413 if (!space)
5414 return isl_multi_aff_free(maff);
5415 isl_space_free(maff->space);
5416 maff->space = space;
5418 if (ls) {
5419 *ls = isl_aff_get_domain_local_space(maff->p[0]);
5420 if (!*ls)
5421 return isl_multi_aff_free(maff);
5424 for (i = 0; i < maff->n; ++i) {
5425 maff->p[i] = isl_aff_lift(maff->p[i]);
5426 if (!maff->p[i])
5427 goto error;
5430 return maff;
5431 error:
5432 if (ls)
5433 isl_local_space_free(*ls);
5434 return isl_multi_aff_free(maff);
5438 /* Extract an isl_pw_aff corresponding to output dimension "pos" of "pma".
5440 __isl_give isl_pw_aff *isl_pw_multi_aff_get_pw_aff(
5441 __isl_keep isl_pw_multi_aff *pma, int pos)
5443 int i;
5444 int n_out;
5445 isl_space *space;
5446 isl_pw_aff *pa;
5448 if (!pma)
5449 return NULL;
5451 n_out = isl_pw_multi_aff_dim(pma, isl_dim_out);
5452 if (pos < 0 || pos >= n_out)
5453 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
5454 "index out of bounds", return NULL);
5456 space = isl_pw_multi_aff_get_space(pma);
5457 space = isl_space_drop_dims(space, isl_dim_out,
5458 pos + 1, n_out - pos - 1);
5459 space = isl_space_drop_dims(space, isl_dim_out, 0, pos);
5461 pa = isl_pw_aff_alloc_size(space, pma->n);
5462 for (i = 0; i < pma->n; ++i) {
5463 isl_aff *aff;
5464 aff = isl_multi_aff_get_aff(pma->p[i].maff, pos);
5465 pa = isl_pw_aff_add_piece(pa, isl_set_copy(pma->p[i].set), aff);
5468 return pa;
5471 /* Return an isl_pw_multi_aff with the given "set" as domain and
5472 * an unnamed zero-dimensional range.
5474 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_domain(
5475 __isl_take isl_set *set)
5477 isl_multi_aff *ma;
5478 isl_space *space;
5480 space = isl_set_get_space(set);
5481 space = isl_space_from_domain(space);
5482 ma = isl_multi_aff_zero(space);
5483 return isl_pw_multi_aff_alloc(set, ma);
5486 /* Add an isl_pw_multi_aff with the given "set" as domain and
5487 * an unnamed zero-dimensional range to *user.
5489 static int add_pw_multi_aff_from_domain(__isl_take isl_set *set, void *user)
5491 isl_union_pw_multi_aff **upma = user;
5492 isl_pw_multi_aff *pma;
5494 pma = isl_pw_multi_aff_from_domain(set);
5495 *upma = isl_union_pw_multi_aff_add_pw_multi_aff(*upma, pma);
5497 return 0;
5500 /* Return an isl_union_pw_multi_aff with the given "uset" as domain and
5501 * an unnamed zero-dimensional range.
5503 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_from_domain(
5504 __isl_take isl_union_set *uset)
5506 isl_space *space;
5507 isl_union_pw_multi_aff *upma;
5509 if (!uset)
5510 return NULL;
5512 space = isl_union_set_get_space(uset);
5513 upma = isl_union_pw_multi_aff_empty(space);
5515 if (isl_union_set_foreach_set(uset,
5516 &add_pw_multi_aff_from_domain, &upma) < 0)
5517 goto error;
5519 isl_union_set_free(uset);
5520 return upma;
5521 error:
5522 isl_union_set_free(uset);
5523 isl_union_pw_multi_aff_free(upma);
5524 return NULL;
5527 /* Convert "pma" to an isl_map and add it to *umap.
5529 static int map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma, void *user)
5531 isl_union_map **umap = user;
5532 isl_map *map;
5534 map = isl_map_from_pw_multi_aff(pma);
5535 *umap = isl_union_map_add_map(*umap, map);
5537 return 0;
5540 /* Construct a union map mapping the domain of the union
5541 * piecewise multi-affine expression to its range, with each dimension
5542 * in the range equated to the corresponding affine expression on its cell.
5544 __isl_give isl_union_map *isl_union_map_from_union_pw_multi_aff(
5545 __isl_take isl_union_pw_multi_aff *upma)
5547 isl_space *space;
5548 isl_union_map *umap;
5550 if (!upma)
5551 return NULL;
5553 space = isl_union_pw_multi_aff_get_space(upma);
5554 umap = isl_union_map_empty(space);
5556 if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma,
5557 &map_from_pw_multi_aff, &umap) < 0)
5558 goto error;
5560 isl_union_pw_multi_aff_free(upma);
5561 return umap;
5562 error:
5563 isl_union_pw_multi_aff_free(upma);
5564 isl_union_map_free(umap);
5565 return NULL;
5568 /* Local data for bin_entry and the callback "fn".
5570 struct isl_union_pw_multi_aff_bin_data {
5571 isl_union_pw_multi_aff *upma2;
5572 isl_union_pw_multi_aff *res;
5573 isl_pw_multi_aff *pma;
5574 int (*fn)(void **entry, void *user);
5577 /* Given an isl_pw_multi_aff from upma1, store it in data->pma
5578 * and call data->fn for each isl_pw_multi_aff in data->upma2.
5580 static int bin_entry(void **entry, void *user)
5582 struct isl_union_pw_multi_aff_bin_data *data = user;
5583 isl_pw_multi_aff *pma = *entry;
5585 data->pma = pma;
5586 if (isl_hash_table_foreach(data->upma2->dim->ctx, &data->upma2->table,
5587 data->fn, data) < 0)
5588 return -1;
5590 return 0;
5593 /* Call "fn" on each pair of isl_pw_multi_affs in "upma1" and "upma2".
5594 * The isl_pw_multi_aff from upma1 is stored in data->pma (where data is
5595 * passed as user field) and the isl_pw_multi_aff from upma2 is available
5596 * as *entry. The callback should adjust data->res if desired.
5598 static __isl_give isl_union_pw_multi_aff *bin_op(
5599 __isl_take isl_union_pw_multi_aff *upma1,
5600 __isl_take isl_union_pw_multi_aff *upma2,
5601 int (*fn)(void **entry, void *user))
5603 isl_space *space;
5604 struct isl_union_pw_multi_aff_bin_data data = { NULL, NULL, NULL, fn };
5606 space = isl_union_pw_multi_aff_get_space(upma2);
5607 upma1 = isl_union_pw_multi_aff_align_params(upma1, space);
5608 space = isl_union_pw_multi_aff_get_space(upma1);
5609 upma2 = isl_union_pw_multi_aff_align_params(upma2, space);
5611 if (!upma1 || !upma2)
5612 goto error;
5614 data.upma2 = upma2;
5615 data.res = isl_union_pw_multi_aff_alloc(isl_space_copy(upma1->dim),
5616 upma1->table.n);
5617 if (isl_hash_table_foreach(upma1->dim->ctx, &upma1->table,
5618 &bin_entry, &data) < 0)
5619 goto error;
5621 isl_union_pw_multi_aff_free(upma1);
5622 isl_union_pw_multi_aff_free(upma2);
5623 return data.res;
5624 error:
5625 isl_union_pw_multi_aff_free(upma1);
5626 isl_union_pw_multi_aff_free(upma2);
5627 isl_union_pw_multi_aff_free(data.res);
5628 return NULL;
5631 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
5632 * construct an isl_pw_multi_aff (A * C) -> [B -> D].
5634 static __isl_give isl_pw_multi_aff *pw_multi_aff_range_product(
5635 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
5637 isl_space *space;
5639 space = isl_space_range_product(isl_pw_multi_aff_get_space(pma1),
5640 isl_pw_multi_aff_get_space(pma2));
5641 return isl_pw_multi_aff_on_shared_domain_in(pma1, pma2, space,
5642 &isl_multi_aff_range_product);
5645 /* Given two isl_pw_multi_affs A -> B and C -> D,
5646 * construct an isl_pw_multi_aff (A * C) -> [B -> D].
5648 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_range_product(
5649 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
5651 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
5652 &pw_multi_aff_range_product);
5655 /* Given two aligned isl_pw_multi_affs A -> B and C -> D,
5656 * construct an isl_pw_multi_aff (A * C) -> (B, D).
5658 static __isl_give isl_pw_multi_aff *pw_multi_aff_flat_range_product(
5659 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
5661 isl_space *space;
5663 space = isl_space_range_product(isl_pw_multi_aff_get_space(pma1),
5664 isl_pw_multi_aff_get_space(pma2));
5665 space = isl_space_flatten_range(space);
5666 return isl_pw_multi_aff_on_shared_domain_in(pma1, pma2, space,
5667 &isl_multi_aff_flat_range_product);
5670 /* Given two isl_pw_multi_affs A -> B and C -> D,
5671 * construct an isl_pw_multi_aff (A * C) -> (B, D).
5673 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_flat_range_product(
5674 __isl_take isl_pw_multi_aff *pma1, __isl_take isl_pw_multi_aff *pma2)
5676 return isl_pw_multi_aff_align_params_pw_pw_and(pma1, pma2,
5677 &pw_multi_aff_flat_range_product);
5680 /* If data->pma and *entry have the same domain space, then compute
5681 * their flat range product and the result to data->res.
5683 static int flat_range_product_entry(void **entry, void *user)
5685 struct isl_union_pw_multi_aff_bin_data *data = user;
5686 isl_pw_multi_aff *pma2 = *entry;
5688 if (!isl_space_tuple_match(data->pma->dim, isl_dim_in,
5689 pma2->dim, isl_dim_in))
5690 return 0;
5692 pma2 = isl_pw_multi_aff_flat_range_product(
5693 isl_pw_multi_aff_copy(data->pma),
5694 isl_pw_multi_aff_copy(pma2));
5696 data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, pma2);
5698 return 0;
5701 /* Given two isl_union_pw_multi_affs A -> B and C -> D,
5702 * construct an isl_union_pw_multi_aff (A * C) -> (B, D).
5704 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_flat_range_product(
5705 __isl_take isl_union_pw_multi_aff *upma1,
5706 __isl_take isl_union_pw_multi_aff *upma2)
5708 return bin_op(upma1, upma2, &flat_range_product_entry);
5711 /* Replace the affine expressions at position "pos" in "pma" by "pa".
5712 * The parameters are assumed to have been aligned.
5714 * The implementation essentially performs an isl_pw_*_on_shared_domain,
5715 * except that it works on two different isl_pw_* types.
5717 static __isl_give isl_pw_multi_aff *pw_multi_aff_set_pw_aff(
5718 __isl_take isl_pw_multi_aff *pma, unsigned pos,
5719 __isl_take isl_pw_aff *pa)
5721 int i, j, n;
5722 isl_pw_multi_aff *res = NULL;
5724 if (!pma || !pa)
5725 goto error;
5727 if (!isl_space_tuple_match(pma->dim, isl_dim_in, pa->dim, isl_dim_in))
5728 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
5729 "domains don't match", goto error);
5730 if (pos >= isl_pw_multi_aff_dim(pma, isl_dim_out))
5731 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
5732 "index out of bounds", goto error);
5734 n = pma->n * pa->n;
5735 res = isl_pw_multi_aff_alloc_size(isl_pw_multi_aff_get_space(pma), n);
5737 for (i = 0; i < pma->n; ++i) {
5738 for (j = 0; j < pa->n; ++j) {
5739 isl_set *common;
5740 isl_multi_aff *res_ij;
5741 int empty;
5743 common = isl_set_intersect(isl_set_copy(pma->p[i].set),
5744 isl_set_copy(pa->p[j].set));
5745 empty = isl_set_plain_is_empty(common);
5746 if (empty < 0 || empty) {
5747 isl_set_free(common);
5748 if (empty < 0)
5749 goto error;
5750 continue;
5753 res_ij = isl_multi_aff_set_aff(
5754 isl_multi_aff_copy(pma->p[i].maff), pos,
5755 isl_aff_copy(pa->p[j].aff));
5756 res_ij = isl_multi_aff_gist(res_ij,
5757 isl_set_copy(common));
5759 res = isl_pw_multi_aff_add_piece(res, common, res_ij);
5763 isl_pw_multi_aff_free(pma);
5764 isl_pw_aff_free(pa);
5765 return res;
5766 error:
5767 isl_pw_multi_aff_free(pma);
5768 isl_pw_aff_free(pa);
5769 return isl_pw_multi_aff_free(res);
5772 /* Replace the affine expressions at position "pos" in "pma" by "pa".
5774 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_set_pw_aff(
5775 __isl_take isl_pw_multi_aff *pma, unsigned pos,
5776 __isl_take isl_pw_aff *pa)
5778 if (!pma || !pa)
5779 goto error;
5780 if (isl_space_match(pma->dim, isl_dim_param, pa->dim, isl_dim_param))
5781 return pw_multi_aff_set_pw_aff(pma, pos, pa);
5782 if (!isl_space_has_named_params(pma->dim) ||
5783 !isl_space_has_named_params(pa->dim))
5784 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
5785 "unaligned unnamed parameters", goto error);
5786 pma = isl_pw_multi_aff_align_params(pma, isl_pw_aff_get_space(pa));
5787 pa = isl_pw_aff_align_params(pa, isl_pw_multi_aff_get_space(pma));
5788 return pw_multi_aff_set_pw_aff(pma, pos, pa);
5789 error:
5790 isl_pw_multi_aff_free(pma);
5791 isl_pw_aff_free(pa);
5792 return NULL;
5795 /* Do the parameters of "pa" match those of "space"?
5797 int isl_pw_aff_matching_params(__isl_keep isl_pw_aff *pa,
5798 __isl_keep isl_space *space)
5800 isl_space *pa_space;
5801 int match;
5803 if (!pa || !space)
5804 return -1;
5806 pa_space = isl_pw_aff_get_space(pa);
5808 match = isl_space_match(space, isl_dim_param, pa_space, isl_dim_param);
5810 isl_space_free(pa_space);
5811 return match;
5814 /* Check that the domain space of "pa" matches "space".
5816 * Return 0 on success and -1 on error.
5818 int isl_pw_aff_check_match_domain_space(__isl_keep isl_pw_aff *pa,
5819 __isl_keep isl_space *space)
5821 isl_space *pa_space;
5822 int match;
5824 if (!pa || !space)
5825 return -1;
5827 pa_space = isl_pw_aff_get_space(pa);
5829 match = isl_space_match(space, isl_dim_param, pa_space, isl_dim_param);
5830 if (match < 0)
5831 goto error;
5832 if (!match)
5833 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
5834 "parameters don't match", goto error);
5835 match = isl_space_tuple_match(space, isl_dim_in, pa_space, isl_dim_in);
5836 if (match < 0)
5837 goto error;
5838 if (!match)
5839 isl_die(isl_pw_aff_get_ctx(pa), isl_error_invalid,
5840 "domains don't match", goto error);
5841 isl_space_free(pa_space);
5842 return 0;
5843 error:
5844 isl_space_free(pa_space);
5845 return -1;
5848 #undef BASE
5849 #define BASE pw_aff
5851 #include <isl_multi_templ.c>
5853 /* Scale the elements of "pma" by the corresponding elements of "mv".
5855 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_scale_multi_val(
5856 __isl_take isl_pw_multi_aff *pma, __isl_take isl_multi_val *mv)
5858 int i;
5860 pma = isl_pw_multi_aff_cow(pma);
5861 if (!pma || !mv)
5862 goto error;
5863 if (!isl_space_tuple_match(pma->dim, isl_dim_out,
5864 mv->space, isl_dim_set))
5865 isl_die(isl_pw_multi_aff_get_ctx(pma), isl_error_invalid,
5866 "spaces don't match", goto error);
5867 if (!isl_space_match(pma->dim, isl_dim_param,
5868 mv->space, isl_dim_param)) {
5869 pma = isl_pw_multi_aff_align_params(pma,
5870 isl_multi_val_get_space(mv));
5871 mv = isl_multi_val_align_params(mv,
5872 isl_pw_multi_aff_get_space(pma));
5873 if (!pma || !mv)
5874 goto error;
5877 for (i = 0; i < pma->n; ++i) {
5878 pma->p[i].maff = isl_multi_aff_scale_multi_val(pma->p[i].maff,
5879 isl_multi_val_copy(mv));
5880 if (!pma->p[i].maff)
5881 goto error;
5884 isl_multi_val_free(mv);
5885 return pma;
5886 error:
5887 isl_multi_val_free(mv);
5888 isl_pw_multi_aff_free(pma);
5889 return NULL;
5892 /* Internal data structure for isl_union_pw_multi_aff_scale_multi_val.
5893 * mv contains the mv argument.
5894 * res collects the results.
5896 struct isl_union_pw_multi_aff_scale_multi_val_data {
5897 isl_multi_val *mv;
5898 isl_union_pw_multi_aff *res;
5901 /* This function is called for each entry of an isl_union_pw_multi_aff.
5902 * If the space of the entry matches that of data->mv,
5903 * then apply isl_pw_multi_aff_scale_multi_val and add the result
5904 * to data->res.
5906 static int union_pw_multi_aff_scale_multi_val_entry(void **entry, void *user)
5908 struct isl_union_pw_multi_aff_scale_multi_val_data *data = user;
5909 isl_pw_multi_aff *pma = *entry;
5911 if (!pma)
5912 return -1;
5913 if (!isl_space_tuple_match(pma->dim, isl_dim_out,
5914 data->mv->space, isl_dim_set))
5915 return 0;
5917 pma = isl_pw_multi_aff_copy(pma);
5918 pma = isl_pw_multi_aff_scale_multi_val(pma,
5919 isl_multi_val_copy(data->mv));
5920 data->res = isl_union_pw_multi_aff_add_pw_multi_aff(data->res, pma);
5921 if (!data->res)
5922 return -1;
5924 return 0;
5927 /* Scale the elements of "upma" by the corresponding elements of "mv",
5928 * for those entries that match the space of "mv".
5930 __isl_give isl_union_pw_multi_aff *isl_union_pw_multi_aff_scale_multi_val(
5931 __isl_take isl_union_pw_multi_aff *upma, __isl_take isl_multi_val *mv)
5933 struct isl_union_pw_multi_aff_scale_multi_val_data data;
5935 upma = isl_union_pw_multi_aff_align_params(upma,
5936 isl_multi_val_get_space(mv));
5937 mv = isl_multi_val_align_params(mv,
5938 isl_union_pw_multi_aff_get_space(upma));
5939 if (!upma || !mv)
5940 goto error;
5942 data.mv = mv;
5943 data.res = isl_union_pw_multi_aff_alloc(isl_space_copy(upma->dim),
5944 upma->table.n);
5945 if (isl_hash_table_foreach(upma->dim->ctx, &upma->table,
5946 &union_pw_multi_aff_scale_multi_val_entry, &data) < 0)
5947 goto error;
5949 isl_multi_val_free(mv);
5950 isl_union_pw_multi_aff_free(upma);
5951 return data.res;
5952 error:
5953 isl_multi_val_free(mv);
5954 isl_union_pw_multi_aff_free(upma);
5955 return NULL;
5958 /* Construct and return a piecewise multi affine expression
5959 * in the given space with value zero in each of the output dimensions and
5960 * a universe domain.
5962 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_zero(__isl_take isl_space *space)
5964 return isl_pw_multi_aff_from_multi_aff(isl_multi_aff_zero(space));
5967 /* Construct and return a piecewise multi affine expression
5968 * that is equal to the given piecewise affine expression.
5970 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_pw_aff(
5971 __isl_take isl_pw_aff *pa)
5973 int i;
5974 isl_space *space;
5975 isl_pw_multi_aff *pma;
5977 if (!pa)
5978 return NULL;
5980 space = isl_pw_aff_get_space(pa);
5981 pma = isl_pw_multi_aff_alloc_size(space, pa->n);
5983 for (i = 0; i < pa->n; ++i) {
5984 isl_set *set;
5985 isl_multi_aff *ma;
5987 set = isl_set_copy(pa->p[i].set);
5988 ma = isl_multi_aff_from_aff(isl_aff_copy(pa->p[i].aff));
5989 pma = isl_pw_multi_aff_add_piece(pma, set, ma);
5992 isl_pw_aff_free(pa);
5993 return pma;
5996 /* Construct a set or map mapping the shared (parameter) domain
5997 * of the piecewise affine expressions to the range of "mpa"
5998 * with each dimension in the range equated to the
5999 * corresponding piecewise affine expression.
6001 static __isl_give isl_map *map_from_multi_pw_aff(
6002 __isl_take isl_multi_pw_aff *mpa)
6004 int i;
6005 isl_space *space;
6006 isl_map *map;
6008 if (!mpa)
6009 return NULL;
6011 if (isl_space_dim(mpa->space, isl_dim_out) != mpa->n)
6012 isl_die(isl_multi_pw_aff_get_ctx(mpa), isl_error_internal,
6013 "invalid space", goto error);
6015 space = isl_multi_pw_aff_get_domain_space(mpa);
6016 map = isl_map_universe(isl_space_from_domain(space));
6018 for (i = 0; i < mpa->n; ++i) {
6019 isl_pw_aff *pa;
6020 isl_map *map_i;
6022 pa = isl_pw_aff_copy(mpa->p[i]);
6023 map_i = map_from_pw_aff(pa);
6025 map = isl_map_flat_range_product(map, map_i);
6028 map = isl_map_reset_space(map, isl_multi_pw_aff_get_space(mpa));
6030 isl_multi_pw_aff_free(mpa);
6031 return map;
6032 error:
6033 isl_multi_pw_aff_free(mpa);
6034 return NULL;
6037 /* Construct a map mapping the shared domain
6038 * of the piecewise affine expressions to the range of "mpa"
6039 * with each dimension in the range equated to the
6040 * corresponding piecewise affine expression.
6042 __isl_give isl_map *isl_map_from_multi_pw_aff(__isl_take isl_multi_pw_aff *mpa)
6044 if (!mpa)
6045 return NULL;
6046 if (isl_space_is_set(mpa->space))
6047 isl_die(isl_multi_pw_aff_get_ctx(mpa), isl_error_internal,
6048 "space of input is not a map", goto error);
6050 return map_from_multi_pw_aff(mpa);
6051 error:
6052 isl_multi_pw_aff_free(mpa);
6053 return NULL;
6056 /* Construct a set mapping the shared parameter domain
6057 * of the piecewise affine expressions to the space of "mpa"
6058 * with each dimension in the range equated to the
6059 * corresponding piecewise affine expression.
6061 __isl_give isl_set *isl_set_from_multi_pw_aff(__isl_take isl_multi_pw_aff *mpa)
6063 if (!mpa)
6064 return NULL;
6065 if (!isl_space_is_set(mpa->space))
6066 isl_die(isl_multi_pw_aff_get_ctx(mpa), isl_error_internal,
6067 "space of input is not a set", goto error);
6069 return map_from_multi_pw_aff(mpa);
6070 error:
6071 isl_multi_pw_aff_free(mpa);
6072 return NULL;
6075 /* Construct and return a piecewise multi affine expression
6076 * that is equal to the given multi piecewise affine expression
6077 * on the shared domain of the piecewise affine expressions.
6079 __isl_give isl_pw_multi_aff *isl_pw_multi_aff_from_multi_pw_aff(
6080 __isl_take isl_multi_pw_aff *mpa)
6082 int i;
6083 isl_space *space;
6084 isl_pw_aff *pa;
6085 isl_pw_multi_aff *pma;
6087 if (!mpa)
6088 return NULL;
6090 space = isl_multi_pw_aff_get_space(mpa);
6092 if (mpa->n == 0) {
6093 isl_multi_pw_aff_free(mpa);
6094 return isl_pw_multi_aff_zero(space);
6097 pa = isl_multi_pw_aff_get_pw_aff(mpa, 0);
6098 pma = isl_pw_multi_aff_from_pw_aff(pa);
6100 for (i = 1; i < mpa->n; ++i) {
6101 isl_pw_multi_aff *pma_i;
6103 pa = isl_multi_pw_aff_get_pw_aff(mpa, i);
6104 pma_i = isl_pw_multi_aff_from_pw_aff(pa);
6105 pma = isl_pw_multi_aff_range_product(pma, pma_i);
6108 pma = isl_pw_multi_aff_reset_space(pma, space);
6110 isl_multi_pw_aff_free(mpa);
6111 return pma;
6114 /* Construct and return a multi piecewise affine expression
6115 * that is equal to the given multi affine expression.
6117 __isl_give isl_multi_pw_aff *isl_multi_pw_aff_from_multi_aff(
6118 __isl_take isl_multi_aff *ma)
6120 int i, n;
6121 isl_multi_pw_aff *mpa;
6123 if (!ma)
6124 return NULL;
6126 n = isl_multi_aff_dim(ma, isl_dim_out);
6127 mpa = isl_multi_pw_aff_alloc(isl_multi_aff_get_space(ma));
6129 for (i = 0; i < n; ++i) {
6130 isl_pw_aff *pa;
6132 pa = isl_pw_aff_from_aff(isl_multi_aff_get_aff(ma, i));
6133 mpa = isl_multi_pw_aff_set_pw_aff(mpa, i, pa);
6136 isl_multi_aff_free(ma);
6137 return mpa;
6140 /* Construct and return a multi piecewise affine expression
6141 * that is equal to the given piecewise multi affine expression.
6143 __isl_give isl_multi_pw_aff *isl_multi_pw_aff_from_pw_multi_aff(
6144 __isl_take isl_pw_multi_aff *pma)
6146 int i, n;
6147 isl_space *space;
6148 isl_multi_pw_aff *mpa;
6150 if (!pma)
6151 return NULL;
6153 n = isl_pw_multi_aff_dim(pma, isl_dim_out);
6154 space = isl_pw_multi_aff_get_space(pma);
6155 mpa = isl_multi_pw_aff_alloc(space);
6157 for (i = 0; i < n; ++i) {
6158 isl_pw_aff *pa;
6160 pa = isl_pw_multi_aff_get_pw_aff(pma, i);
6161 mpa = isl_multi_pw_aff_set_pw_aff(mpa, i, pa);
6164 isl_pw_multi_aff_free(pma);
6165 return mpa;
6168 /* Do "pa1" and "pa2" represent the same function?
6170 * We first check if they are obviously equal.
6171 * If not, we convert them to maps and check if those are equal.
6173 int isl_pw_aff_is_equal(__isl_keep isl_pw_aff *pa1, __isl_keep isl_pw_aff *pa2)
6175 int equal;
6176 isl_map *map1, *map2;
6178 if (!pa1 || !pa2)
6179 return -1;
6181 equal = isl_pw_aff_plain_is_equal(pa1, pa2);
6182 if (equal < 0 || equal)
6183 return equal;
6185 map1 = map_from_pw_aff(isl_pw_aff_copy(pa1));
6186 map2 = map_from_pw_aff(isl_pw_aff_copy(pa2));
6187 equal = isl_map_is_equal(map1, map2);
6188 isl_map_free(map1);
6189 isl_map_free(map2);
6191 return equal;
6194 /* Do "mpa1" and "mpa2" represent the same function?
6196 * Note that we cannot convert the entire isl_multi_pw_aff
6197 * to a map because the domains of the piecewise affine expressions
6198 * may not be the same.
6200 int isl_multi_pw_aff_is_equal(__isl_keep isl_multi_pw_aff *mpa1,
6201 __isl_keep isl_multi_pw_aff *mpa2)
6203 int i;
6204 int equal;
6206 if (!mpa1 || !mpa2)
6207 return -1;
6209 if (!isl_space_match(mpa1->space, isl_dim_param,
6210 mpa2->space, isl_dim_param)) {
6211 if (!isl_space_has_named_params(mpa1->space))
6212 return 0;
6213 if (!isl_space_has_named_params(mpa2->space))
6214 return 0;
6215 mpa1 = isl_multi_pw_aff_copy(mpa1);
6216 mpa2 = isl_multi_pw_aff_copy(mpa2);
6217 mpa1 = isl_multi_pw_aff_align_params(mpa1,
6218 isl_multi_pw_aff_get_space(mpa2));
6219 mpa2 = isl_multi_pw_aff_align_params(mpa2,
6220 isl_multi_pw_aff_get_space(mpa1));
6221 equal = isl_multi_pw_aff_is_equal(mpa1, mpa2);
6222 isl_multi_pw_aff_free(mpa1);
6223 isl_multi_pw_aff_free(mpa2);
6224 return equal;
6227 equal = isl_space_is_equal(mpa1->space, mpa2->space);
6228 if (equal < 0 || !equal)
6229 return equal;
6231 for (i = 0; i < mpa1->n; ++i) {
6232 equal = isl_pw_aff_is_equal(mpa1->p[i], mpa2->p[i]);
6233 if (equal < 0 || !equal)
6234 return equal;
6237 return 1;
6240 /* Coalesce the elements of "mpa".
6242 * Note that such coalescing does not change the meaning of "mpa"
6243 * so there is no need to cow. We do need to be careful not to
6244 * destroy any other copies of "mpa" in case of failure.
6246 __isl_give isl_multi_pw_aff *isl_multi_pw_aff_coalesce(
6247 __isl_take isl_multi_pw_aff *mpa)
6249 int i;
6251 if (!mpa)
6252 return NULL;
6254 for (i = 0; i < mpa->n; ++i) {
6255 isl_pw_aff *pa = isl_pw_aff_copy(mpa->p[i]);
6256 pa = isl_pw_aff_coalesce(pa);
6257 if (!pa)
6258 return isl_multi_pw_aff_free(mpa);
6259 isl_pw_aff_free(mpa->p[i]);
6260 mpa->p[i] = pa;
6263 return mpa;
6266 /* Compute the pullback of "mpa" by the function represented by "ma".
6267 * In other words, plug in "ma" in "mpa".
6269 * The parameters of "mpa" and "ma" are assumed to have been aligned.
6271 static __isl_give isl_multi_pw_aff *isl_multi_pw_aff_pullback_multi_aff_aligned(
6272 __isl_take isl_multi_pw_aff *mpa, __isl_take isl_multi_aff *ma)
6274 int i;
6275 isl_space *space = NULL;
6277 mpa = isl_multi_pw_aff_cow(mpa);
6278 if (!mpa || !ma)
6279 goto error;
6281 space = isl_space_join(isl_multi_aff_get_space(ma),
6282 isl_multi_pw_aff_get_space(mpa));
6283 if (!space)
6284 goto error;
6286 for (i = 0; i < mpa->n; ++i) {
6287 mpa->p[i] = isl_pw_aff_pullback_multi_aff(mpa->p[i],
6288 isl_multi_aff_copy(ma));
6289 if (!mpa->p[i])
6290 goto error;
6293 isl_multi_aff_free(ma);
6294 isl_space_free(mpa->space);
6295 mpa->space = space;
6296 return mpa;
6297 error:
6298 isl_space_free(space);
6299 isl_multi_pw_aff_free(mpa);
6300 isl_multi_aff_free(ma);
6301 return NULL;
6304 /* Compute the pullback of "mpa" by the function represented by "ma".
6305 * In other words, plug in "ma" in "mpa".
6307 __isl_give isl_multi_pw_aff *isl_multi_pw_aff_pullback_multi_aff(
6308 __isl_take isl_multi_pw_aff *mpa, __isl_take isl_multi_aff *ma)
6310 if (!mpa || !ma)
6311 goto error;
6312 if (isl_space_match(mpa->space, isl_dim_param,
6313 ma->space, isl_dim_param))
6314 return isl_multi_pw_aff_pullback_multi_aff_aligned(mpa, ma);
6315 mpa = isl_multi_pw_aff_align_params(mpa, isl_multi_aff_get_space(ma));
6316 ma = isl_multi_aff_align_params(ma, isl_multi_pw_aff_get_space(mpa));
6317 return isl_multi_pw_aff_pullback_multi_aff_aligned(mpa, ma);
6318 error:
6319 isl_multi_pw_aff_free(mpa);
6320 isl_multi_aff_free(ma);
6321 return NULL;
6324 /* Compute the pullback of "mpa" by the function represented by "pma".
6325 * In other words, plug in "pma" in "mpa".
6327 * The parameters of "mpa" and "mpa" are assumed to have been aligned.
6329 static __isl_give isl_multi_pw_aff *
6330 isl_multi_pw_aff_pullback_pw_multi_aff_aligned(
6331 __isl_take isl_multi_pw_aff *mpa, __isl_take isl_pw_multi_aff *pma)
6333 int i;
6334 isl_space *space = NULL;
6336 mpa = isl_multi_pw_aff_cow(mpa);
6337 if (!mpa || !pma)
6338 goto error;
6340 space = isl_space_join(isl_pw_multi_aff_get_space(pma),
6341 isl_multi_pw_aff_get_space(mpa));
6343 for (i = 0; i < mpa->n; ++i) {
6344 mpa->p[i] = isl_pw_aff_pullback_pw_multi_aff_aligned(mpa->p[i],
6345 isl_pw_multi_aff_copy(pma));
6346 if (!mpa->p[i])
6347 goto error;
6350 isl_pw_multi_aff_free(pma);
6351 isl_space_free(mpa->space);
6352 mpa->space = space;
6353 return mpa;
6354 error:
6355 isl_space_free(space);
6356 isl_multi_pw_aff_free(mpa);
6357 isl_pw_multi_aff_free(pma);
6358 return NULL;
6361 /* Compute the pullback of "mpa" by the function represented by "pma".
6362 * In other words, plug in "pma" in "mpa".
6364 __isl_give isl_multi_pw_aff *isl_multi_pw_aff_pullback_pw_multi_aff(
6365 __isl_take isl_multi_pw_aff *mpa, __isl_take isl_pw_multi_aff *pma)
6367 if (!mpa || !pma)
6368 goto error;
6369 if (isl_space_match(mpa->space, isl_dim_param, pma->dim, isl_dim_param))
6370 return isl_multi_pw_aff_pullback_pw_multi_aff_aligned(mpa, pma);
6371 mpa = isl_multi_pw_aff_align_params(mpa,
6372 isl_pw_multi_aff_get_space(pma));
6373 pma = isl_pw_multi_aff_align_params(pma,
6374 isl_multi_pw_aff_get_space(mpa));
6375 return isl_multi_pw_aff_pullback_pw_multi_aff_aligned(mpa, pma);
6376 error:
6377 isl_multi_pw_aff_free(mpa);
6378 isl_pw_multi_aff_free(pma);
6379 return NULL;
6382 /* Apply "aff" to "mpa". The range of "mpa" needs to be compatible
6383 * with the domain of "aff". The domain of the result is the same
6384 * as that of "mpa".
6385 * "mpa" and "aff" are assumed to have been aligned.
6387 * We first extract the parametric constant from "aff", defined
6388 * over the correct domain.
6389 * Then we add the appropriate combinations of the members of "mpa".
6390 * Finally, we add the integer divisions through recursive calls.
6392 static __isl_give isl_pw_aff *isl_multi_pw_aff_apply_aff_aligned(
6393 __isl_take isl_multi_pw_aff *mpa, __isl_take isl_aff *aff)
6395 int i, n_param, n_in, n_div;
6396 isl_space *space;
6397 isl_val *v;
6398 isl_pw_aff *pa;
6399 isl_aff *tmp;
6401 n_param = isl_aff_dim(aff, isl_dim_param);
6402 n_in = isl_aff_dim(aff, isl_dim_in);
6403 n_div = isl_aff_dim(aff, isl_dim_div);
6405 space = isl_space_domain(isl_multi_pw_aff_get_space(mpa));
6406 tmp = isl_aff_copy(aff);
6407 tmp = isl_aff_drop_dims(tmp, isl_dim_div, 0, n_div);
6408 tmp = isl_aff_drop_dims(tmp, isl_dim_in, 0, n_in);
6409 tmp = isl_aff_add_dims(tmp, isl_dim_in,
6410 isl_space_dim(space, isl_dim_set));
6411 tmp = isl_aff_reset_domain_space(tmp, space);
6412 pa = isl_pw_aff_from_aff(tmp);
6414 for (i = 0; i < n_in; ++i) {
6415 isl_pw_aff *pa_i;
6417 if (!isl_aff_involves_dims(aff, isl_dim_in, i, 1))
6418 continue;
6419 v = isl_aff_get_coefficient_val(aff, isl_dim_in, i);
6420 pa_i = isl_multi_pw_aff_get_pw_aff(mpa, i);
6421 pa_i = isl_pw_aff_scale_val(pa_i, v);
6422 pa = isl_pw_aff_add(pa, pa_i);
6425 for (i = 0; i < n_div; ++i) {
6426 isl_aff *div;
6427 isl_pw_aff *pa_i;
6429 if (!isl_aff_involves_dims(aff, isl_dim_div, i, 1))
6430 continue;
6431 div = isl_aff_get_div(aff, i);
6432 pa_i = isl_multi_pw_aff_apply_aff_aligned(
6433 isl_multi_pw_aff_copy(mpa), div);
6434 pa_i = isl_pw_aff_floor(pa_i);
6435 v = isl_aff_get_coefficient_val(aff, isl_dim_div, i);
6436 pa_i = isl_pw_aff_scale_val(pa_i, v);
6437 pa = isl_pw_aff_add(pa, pa_i);
6440 isl_multi_pw_aff_free(mpa);
6441 isl_aff_free(aff);
6443 return pa;
6446 /* Apply "aff" to "mpa". The range of "mpa" needs to be compatible
6447 * with the domain of "aff". The domain of the result is the same
6448 * as that of "mpa".
6450 __isl_give isl_pw_aff *isl_multi_pw_aff_apply_aff(
6451 __isl_take isl_multi_pw_aff *mpa, __isl_take isl_aff *aff)
6453 if (!aff || !mpa)
6454 goto error;
6455 if (isl_space_match(aff->ls->dim, isl_dim_param,
6456 mpa->space, isl_dim_param))
6457 return isl_multi_pw_aff_apply_aff_aligned(mpa, aff);
6459 aff = isl_aff_align_params(aff, isl_multi_pw_aff_get_space(mpa));
6460 mpa = isl_multi_pw_aff_align_params(mpa, isl_aff_get_space(aff));
6462 return isl_multi_pw_aff_apply_aff_aligned(mpa, aff);
6463 error:
6464 isl_aff_free(aff);
6465 isl_multi_pw_aff_free(mpa);
6466 return NULL;
6469 /* Apply "pa" to "mpa". The range of "mpa" needs to be compatible
6470 * with the domain of "pa". The domain of the result is the same
6471 * as that of "mpa".
6472 * "mpa" and "pa" are assumed to have been aligned.
6474 * We consider each piece in turn. Note that the domains of the
6475 * pieces are assumed to be disjoint and they remain disjoint
6476 * after taking the preimage (over the same function).
6478 static __isl_give isl_pw_aff *isl_multi_pw_aff_apply_pw_aff_aligned(
6479 __isl_take isl_multi_pw_aff *mpa, __isl_take isl_pw_aff *pa)
6481 isl_space *space;
6482 isl_pw_aff *res;
6483 int i;
6485 if (!mpa || !pa)
6486 goto error;
6488 space = isl_space_join(isl_multi_pw_aff_get_space(mpa),
6489 isl_pw_aff_get_space(pa));
6490 res = isl_pw_aff_empty(space);
6492 for (i = 0; i < pa->n; ++i) {
6493 isl_pw_aff *pa_i;
6494 isl_set *domain;
6496 pa_i = isl_multi_pw_aff_apply_aff_aligned(
6497 isl_multi_pw_aff_copy(mpa),
6498 isl_aff_copy(pa->p[i].aff));
6499 domain = isl_set_copy(pa->p[i].set);
6500 domain = isl_set_preimage_multi_pw_aff(domain,
6501 isl_multi_pw_aff_copy(mpa));
6502 pa_i = isl_pw_aff_intersect_domain(pa_i, domain);
6503 res = isl_pw_aff_add_disjoint(res, pa_i);
6506 isl_pw_aff_free(pa);
6507 isl_multi_pw_aff_free(mpa);
6508 return res;
6509 error:
6510 isl_pw_aff_free(pa);
6511 isl_multi_pw_aff_free(mpa);
6512 return NULL;
6515 /* Apply "pa" to "mpa". The range of "mpa" needs to be compatible
6516 * with the domain of "pa". The domain of the result is the same
6517 * as that of "mpa".
6519 __isl_give isl_pw_aff *isl_multi_pw_aff_apply_pw_aff(
6520 __isl_take isl_multi_pw_aff *mpa, __isl_take isl_pw_aff *pa)
6522 if (!pa || !mpa)
6523 goto error;
6524 if (isl_space_match(pa->dim, isl_dim_param, mpa->space, isl_dim_param))
6525 return isl_multi_pw_aff_apply_pw_aff_aligned(mpa, pa);
6527 pa = isl_pw_aff_align_params(pa, isl_multi_pw_aff_get_space(mpa));
6528 mpa = isl_multi_pw_aff_align_params(mpa, isl_pw_aff_get_space(pa));
6530 return isl_multi_pw_aff_apply_pw_aff_aligned(mpa, pa);
6531 error:
6532 isl_pw_aff_free(pa);
6533 isl_multi_pw_aff_free(mpa);
6534 return NULL;
6537 /* Compute the pullback of "pa" by the function represented by "mpa".
6538 * In other words, plug in "mpa" in "pa".
6539 * "pa" and "mpa" are assumed to have been aligned.
6541 * The pullback is computed by applying "pa" to "mpa".
6543 static __isl_give isl_pw_aff *isl_pw_aff_pullback_multi_pw_aff_aligned(
6544 __isl_take isl_pw_aff *pa, __isl_take isl_multi_pw_aff *mpa)
6546 return isl_multi_pw_aff_apply_pw_aff_aligned(mpa, pa);
6549 /* Compute the pullback of "pa" by the function represented by "mpa".
6550 * In other words, plug in "mpa" in "pa".
6552 * The pullback is computed by applying "pa" to "mpa".
6554 __isl_give isl_pw_aff *isl_pw_aff_pullback_multi_pw_aff(
6555 __isl_take isl_pw_aff *pa, __isl_take isl_multi_pw_aff *mpa)
6557 return isl_multi_pw_aff_apply_pw_aff(mpa, pa);
6560 /* Compute the pullback of "mpa1" by the function represented by "mpa2".
6561 * In other words, plug in "mpa2" in "mpa1".
6563 * The parameters of "mpa1" and "mpa2" are assumed to have been aligned.
6565 * We pullback each member of "mpa1" in turn.
6567 static __isl_give isl_multi_pw_aff *
6568 isl_multi_pw_aff_pullback_multi_pw_aff_aligned(
6569 __isl_take isl_multi_pw_aff *mpa1, __isl_take isl_multi_pw_aff *mpa2)
6571 int i;
6572 isl_space *space = NULL;
6574 mpa1 = isl_multi_pw_aff_cow(mpa1);
6575 if (!mpa1 || !mpa2)
6576 goto error;
6578 space = isl_space_join(isl_multi_pw_aff_get_space(mpa2),
6579 isl_multi_pw_aff_get_space(mpa1));
6581 for (i = 0; i < mpa1->n; ++i) {
6582 mpa1->p[i] = isl_pw_aff_pullback_multi_pw_aff_aligned(
6583 mpa1->p[i], isl_multi_pw_aff_copy(mpa2));
6584 if (!mpa1->p[i])
6585 goto error;
6588 mpa1 = isl_multi_pw_aff_reset_space(mpa1, space);
6590 isl_multi_pw_aff_free(mpa2);
6591 return mpa1;
6592 error:
6593 isl_space_free(space);
6594 isl_multi_pw_aff_free(mpa1);
6595 isl_multi_pw_aff_free(mpa2);
6596 return NULL;
6599 /* Compute the pullback of "mpa1" by the function represented by "mpa2".
6600 * In other words, plug in "mpa2" in "mpa1".
6602 __isl_give isl_multi_pw_aff *isl_multi_pw_aff_pullback_multi_pw_aff(
6603 __isl_take isl_multi_pw_aff *mpa1, __isl_take isl_multi_pw_aff *mpa2)
6605 return isl_multi_pw_aff_align_params_multi_multi_and(mpa1, mpa2,
6606 &isl_multi_pw_aff_pullback_multi_pw_aff_aligned);
6609 /* Compare two isl_affs.
6611 * Return -1 if "aff1" is "smaller" than "aff2", 1 if "aff1" is "greater"
6612 * than "aff2" and 0 if they are equal.
6614 * The order is fairly arbitrary. We do consider expressions that only involve
6615 * earlier dimensions as "smaller".
6617 int isl_aff_plain_cmp(__isl_keep isl_aff *aff1, __isl_keep isl_aff *aff2)
6619 int cmp;
6620 int last1, last2;
6622 if (aff1 == aff2)
6623 return 0;
6625 if (!aff1)
6626 return -1;
6627 if (!aff2)
6628 return 1;
6630 cmp = isl_local_space_cmp(aff1->ls, aff2->ls);
6631 if (cmp != 0)
6632 return cmp;
6634 last1 = isl_seq_last_non_zero(aff1->v->el + 1, aff1->v->size - 1);
6635 last2 = isl_seq_last_non_zero(aff2->v->el + 1, aff1->v->size - 1);
6636 if (last1 != last2)
6637 return last1 - last2;
6639 return isl_seq_cmp(aff1->v->el, aff2->v->el, aff1->v->size);
6642 /* Compare two isl_pw_affs.
6644 * Return -1 if "pa1" is "smaller" than "pa2", 1 if "pa1" is "greater"
6645 * than "pa2" and 0 if they are equal.
6647 * The order is fairly arbitrary. We do consider expressions that only involve
6648 * earlier dimensions as "smaller".
6650 int isl_pw_aff_plain_cmp(__isl_keep isl_pw_aff *pa1,
6651 __isl_keep isl_pw_aff *pa2)
6653 int i;
6654 int cmp;
6656 if (pa1 == pa2)
6657 return 0;
6659 if (!pa1)
6660 return -1;
6661 if (!pa2)
6662 return 1;
6664 cmp = isl_space_cmp(pa1->dim, pa2->dim);
6665 if (cmp != 0)
6666 return cmp;
6668 if (pa1->n != pa2->n)
6669 return pa1->n - pa2->n;
6671 for (i = 0; i < pa1->n; ++i) {
6672 cmp = isl_set_plain_cmp(pa1->p[i].set, pa2->p[i].set);
6673 if (cmp != 0)
6674 return cmp;
6675 cmp = isl_aff_plain_cmp(pa1->p[i].aff, pa2->p[i].aff);
6676 if (cmp != 0)
6677 return cmp;
6680 return 0;