6 #include "isl_equalities.h"
12 #include "isl_map_private.h"
13 #include "isl_map_piplib.h"
14 #include "isl_sample.h"
17 /* Maps dst positions to src positions */
23 static struct isl_dim_map *isl_dim_map_alloc(struct isl_ctx *ctx, unsigned len)
26 struct isl_dim_map *dim_map;
27 dim_map = isl_alloc(ctx, struct isl_dim_map,
28 sizeof(struct isl_dim_map) + len * sizeof(int));
31 dim_map->len = 1 + len;
33 for (i = 0; i < len; ++i)
34 dim_map->pos[1 + i] = -1;
38 static unsigned n(struct isl_dim *dim, enum isl_dim_type type)
41 case isl_dim_param: return dim->nparam;
42 case isl_dim_in: return dim->n_in;
43 case isl_dim_out: return dim->n_out;
47 static unsigned pos(struct isl_dim *dim, enum isl_dim_type type)
50 case isl_dim_param: return 1;
51 case isl_dim_in: return 1 + dim->nparam;
52 case isl_dim_out: return 1 + dim->nparam + dim->n_in;
56 static void isl_dim_map_dim(struct isl_dim_map *dim_map, struct isl_dim *dim,
57 enum isl_dim_type type, unsigned dst_pos)
65 src_pos = pos(dim, type);
66 for (i = 0; i < n(dim, type); ++i)
67 dim_map->pos[1 + dst_pos + i] = src_pos + i;
70 static void isl_dim_map_div(struct isl_dim_map *dim_map,
71 struct isl_basic_map *bmap, unsigned dst_pos)
76 if (!dim_map || !bmap)
79 src_pos = 1 + isl_dim_total(bmap->dim);
80 for (i = 0; i < bmap->n_div; ++i)
81 dim_map->pos[1 + dst_pos + i] = src_pos + i;
84 static void isl_dim_map_dump(struct isl_dim_map *dim_map)
88 for (i = 0; i < dim_map->len; ++i)
89 fprintf(stderr, "%d -> %d; ", i, dim_map->pos[i]);
90 fprintf(stderr, "\n");
93 unsigned isl_basic_set_n_dim(const struct isl_basic_set *bset)
95 return bset->dim->n_out;
98 unsigned isl_basic_set_n_param(const struct isl_basic_set *bset)
100 return bset->dim->nparam;
103 unsigned isl_basic_set_total_dim(const struct isl_basic_set *bset)
105 return isl_dim_total(bset->dim) + bset->n_div;
108 unsigned isl_set_n_dim(const struct isl_set *set)
110 return set->dim->n_out;
113 unsigned isl_set_n_param(const struct isl_set *set)
115 return set->dim->nparam;
118 unsigned isl_basic_map_n_in(const struct isl_basic_map *bmap)
120 return bmap->dim->n_in;
123 unsigned isl_basic_map_n_out(const struct isl_basic_map *bmap)
125 return bmap->dim->n_out;
128 unsigned isl_basic_map_n_param(const struct isl_basic_map *bmap)
130 return bmap->dim->nparam;
133 unsigned isl_basic_map_n_div(const struct isl_basic_map *bmap)
138 unsigned isl_basic_map_total_dim(const struct isl_basic_map *bmap)
140 return isl_dim_total(bmap->dim) + bmap->n_div;
143 unsigned isl_map_n_in(const struct isl_map *map)
145 return map->dim->n_in;
148 unsigned isl_map_n_out(const struct isl_map *map)
150 return map->dim->n_out;
153 unsigned isl_map_n_param(const struct isl_map *map)
155 return map->dim->nparam;
158 int isl_map_compatible_domain(struct isl_map *map, struct isl_set *set)
160 return map->dim->n_in == set->dim->n_out &&
161 map->dim->nparam == set->dim->nparam;
164 int isl_basic_map_compatible_domain(struct isl_basic_map *bmap,
165 struct isl_basic_set *bset)
167 return bmap->dim->n_in == bset->dim->n_out &&
168 bmap->dim->nparam == bset->dim->nparam;
171 int isl_basic_map_compatible_range(struct isl_basic_map *bmap,
172 struct isl_basic_set *bset)
174 return bmap->dim->n_out == bset->dim->n_out &&
175 bmap->dim->nparam == bset->dim->nparam;
178 static struct isl_basic_map *basic_map_init(struct isl_ctx *ctx,
179 struct isl_basic_map *bmap, unsigned extra,
180 unsigned n_eq, unsigned n_ineq)
183 size_t row_size = 1 + isl_dim_total(bmap->dim) + extra;
185 bmap->block = isl_blk_alloc(ctx, (n_eq + n_ineq) * row_size);
186 if (isl_blk_is_error(bmap->block)) {
191 bmap->eq = isl_alloc_array(ctx, isl_int *, n_eq + n_ineq);
193 isl_blk_free(ctx, bmap->block);
199 bmap->block2 = isl_blk_empty();
202 bmap->block2 = isl_blk_alloc(ctx, extra * (1 + row_size));
203 if (isl_blk_is_error(bmap->block2)) {
205 isl_blk_free(ctx, bmap->block);
210 bmap->div = isl_alloc_array(ctx, isl_int *, extra);
212 isl_blk_free(ctx, bmap->block2);
214 isl_blk_free(ctx, bmap->block);
220 for (i = 0; i < n_eq + n_ineq; ++i)
221 bmap->eq[i] = bmap->block.data + i * row_size;
223 for (i = 0; i < extra; ++i)
224 bmap->div[i] = bmap->block2.data + i * (1 + row_size);
230 bmap->c_size = n_eq + n_ineq;
231 bmap->ineq = bmap->eq + n_eq;
240 isl_basic_map_free(bmap);
244 struct isl_basic_set *isl_basic_set_alloc(struct isl_ctx *ctx,
245 unsigned nparam, unsigned dim, unsigned extra,
246 unsigned n_eq, unsigned n_ineq)
248 struct isl_basic_map *bmap;
249 bmap = isl_basic_map_alloc(ctx, nparam, 0, dim, extra, n_eq, n_ineq);
250 return (struct isl_basic_set *)bmap;
253 struct isl_basic_set *isl_basic_set_alloc_dim(struct isl_ctx *ctx,
254 struct isl_dim *dim, unsigned extra,
255 unsigned n_eq, unsigned n_ineq)
257 struct isl_basic_map *bmap;
260 isl_assert(ctx, dim->n_in == 0, return NULL);
261 bmap = isl_basic_map_alloc_dim(ctx, dim, extra, n_eq, n_ineq);
262 return (struct isl_basic_set *)bmap;
265 struct isl_basic_map *isl_basic_map_alloc_dim(struct isl_ctx *ctx,
266 struct isl_dim *dim, unsigned extra,
267 unsigned n_eq, unsigned n_ineq)
269 struct isl_basic_map *bmap;
273 bmap = isl_alloc_type(ctx, struct isl_basic_map);
278 return basic_map_init(ctx, bmap, extra, n_eq, n_ineq);
284 struct isl_basic_map *isl_basic_map_alloc(struct isl_ctx *ctx,
285 unsigned nparam, unsigned in, unsigned out, unsigned extra,
286 unsigned n_eq, unsigned n_ineq)
288 struct isl_basic_map *bmap;
291 dim = isl_dim_alloc(ctx, nparam, in, out);
295 bmap = isl_basic_map_alloc_dim(ctx, dim, extra, n_eq, n_ineq);
299 static void dup_constraints(
300 struct isl_basic_map *dst, struct isl_basic_map *src)
303 unsigned total = isl_basic_map_total_dim(src);
305 for (i = 0; i < src->n_eq; ++i) {
306 int j = isl_basic_map_alloc_equality(dst);
307 isl_seq_cpy(dst->eq[j], src->eq[i], 1+total);
310 for (i = 0; i < src->n_ineq; ++i) {
311 int j = isl_basic_map_alloc_inequality(dst);
312 isl_seq_cpy(dst->ineq[j], src->ineq[i], 1+total);
315 for (i = 0; i < src->n_div; ++i) {
316 int j = isl_basic_map_alloc_div(dst);
317 isl_seq_cpy(dst->div[j], src->div[i], 1+1+total);
319 F_SET(dst, ISL_BASIC_SET_FINAL);
322 struct isl_basic_map *isl_basic_map_dup(struct isl_basic_map *bmap)
324 struct isl_basic_map *dup;
328 dup = isl_basic_map_alloc_dim(bmap->ctx, isl_dim_copy(bmap->dim),
329 bmap->n_div, bmap->n_eq, bmap->n_ineq);
332 dup->flags = bmap->flags;
333 dup_constraints(dup, bmap);
334 dup->sample = isl_vec_copy(bmap->ctx, bmap->sample);
338 struct isl_basic_set *isl_basic_set_dup(struct isl_basic_set *bset)
340 struct isl_basic_map *dup;
342 dup = isl_basic_map_dup((struct isl_basic_map *)bset);
343 return (struct isl_basic_set *)dup;
346 struct isl_basic_set *isl_basic_set_copy(struct isl_basic_set *bset)
351 if (F_ISSET(bset, ISL_BASIC_SET_FINAL)) {
355 return isl_basic_set_dup(bset);
358 struct isl_set *isl_set_copy(struct isl_set *set)
367 struct isl_basic_map *isl_basic_map_copy(struct isl_basic_map *bmap)
372 if (F_ISSET(bmap, ISL_BASIC_SET_FINAL)) {
376 return isl_basic_map_dup(bmap);
379 struct isl_map *isl_map_copy(struct isl_map *map)
388 void isl_basic_map_free(struct isl_basic_map *bmap)
396 isl_ctx_deref(bmap->ctx);
398 isl_blk_free(bmap->ctx, bmap->block2);
400 isl_blk_free(bmap->ctx, bmap->block);
401 isl_vec_free(bmap->ctx, bmap->sample);
402 isl_dim_free(bmap->dim);
406 void isl_basic_set_free(struct isl_basic_set *bset)
408 isl_basic_map_free((struct isl_basic_map *)bset);
411 int isl_basic_map_alloc_equality(struct isl_basic_map *bmap)
417 isl_assert(ctx, bmap->n_eq + bmap->n_ineq < bmap->c_size, return -1);
418 isl_assert(ctx, bmap->eq + bmap->n_eq <= bmap->ineq, return -1);
419 if (bmap->eq + bmap->n_eq == bmap->ineq) {
421 int j = isl_basic_map_alloc_inequality(bmap);
425 bmap->ineq[0] = bmap->ineq[j];
430 isl_seq_clr(bmap->eq[bmap->n_eq] +
431 1 + isl_basic_map_total_dim(bmap),
432 bmap->extra - bmap->n_div);
436 int isl_basic_set_alloc_equality(struct isl_basic_set *bset)
438 return isl_basic_map_alloc_equality((struct isl_basic_map *)bset);
441 int isl_basic_map_free_equality(struct isl_basic_map *bmap, unsigned n)
445 isl_assert(bmap->ctx, n <= bmap->n_eq, return -1);
450 int isl_basic_map_drop_equality(struct isl_basic_map *bmap, unsigned pos)
455 isl_assert(bmap->ctx, pos < bmap->n_eq, return -1);
457 if (pos != bmap->n_eq - 1) {
459 bmap->eq[pos] = bmap->eq[bmap->n_eq - 1];
460 bmap->eq[bmap->n_eq - 1] = t;
466 int isl_basic_set_drop_equality(struct isl_basic_set *bset, unsigned pos)
468 return isl_basic_map_drop_equality((struct isl_basic_map *)bset, pos);
471 void isl_basic_map_inequality_to_equality(
472 struct isl_basic_map *bmap, unsigned pos)
477 bmap->ineq[pos] = bmap->ineq[0];
478 bmap->ineq[0] = bmap->eq[bmap->n_eq];
479 bmap->eq[bmap->n_eq] = t;
483 F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
486 int isl_basic_map_alloc_inequality(struct isl_basic_map *bmap)
492 isl_assert(ctx, (bmap->ineq - bmap->eq) + bmap->n_ineq < bmap->c_size,
494 F_CLR(bmap, ISL_BASIC_MAP_NO_IMPLICIT);
495 F_CLR(bmap, ISL_BASIC_MAP_NO_REDUNDANT);
496 F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
497 isl_seq_clr(bmap->ineq[bmap->n_ineq] +
498 1 + isl_basic_map_total_dim(bmap),
499 bmap->extra - bmap->n_div);
500 return bmap->n_ineq++;
503 int isl_basic_set_alloc_inequality(struct isl_basic_set *bset)
505 return isl_basic_map_alloc_inequality((struct isl_basic_map *)bset);
508 int isl_basic_map_free_inequality(struct isl_basic_map *bmap, unsigned n)
512 isl_assert(bmap->ctx, n <= bmap->n_ineq, return -1);
517 int isl_basic_set_free_inequality(struct isl_basic_set *bset, unsigned n)
519 return isl_basic_map_free_inequality((struct isl_basic_map *)bset, n);
522 int isl_basic_map_drop_inequality(struct isl_basic_map *bmap, unsigned pos)
527 isl_assert(bmap->ctx, pos < bmap->n_ineq, return -1);
529 if (pos != bmap->n_ineq - 1) {
531 bmap->ineq[pos] = bmap->ineq[bmap->n_ineq - 1];
532 bmap->ineq[bmap->n_ineq - 1] = t;
533 F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
539 int isl_basic_set_drop_inequality(struct isl_basic_set *bset, unsigned pos)
541 return isl_basic_map_drop_inequality((struct isl_basic_map *)bset, pos);
544 int isl_basic_map_alloc_div(struct isl_basic_map *bmap)
548 isl_assert(bmap->ctx, bmap->n_div < bmap->extra, return -1);
549 isl_seq_clr(bmap->div[bmap->n_div] +
550 1 + 1 + isl_basic_map_total_dim(bmap),
551 bmap->extra - bmap->n_div);
552 return bmap->n_div++;
555 int isl_basic_map_free_div(struct isl_basic_map *bmap, unsigned n)
559 isl_assert(bmap->ctx, n <= bmap->n_div, return -1);
564 /* Copy constraint from src to dst, putting the vars of src at offset
565 * dim_off in dst and the divs of src at offset div_off in dst.
566 * If both sets are actually map, then dim_off applies to the input
569 static void copy_constraint(struct isl_basic_map *dst_map, isl_int *dst,
570 struct isl_basic_map *src_map, isl_int *src,
571 unsigned in_off, unsigned out_off, unsigned div_off)
573 unsigned src_nparam = isl_basic_map_n_param(src_map);
574 unsigned dst_nparam = isl_basic_map_n_param(dst_map);
575 unsigned src_in = isl_basic_map_n_in(src_map);
576 unsigned dst_in = isl_basic_map_n_in(dst_map);
577 unsigned src_out = isl_basic_map_n_out(src_map);
578 unsigned dst_out = isl_basic_map_n_out(dst_map);
579 isl_int_set(dst[0], src[0]);
580 isl_seq_cpy(dst+1, src+1, isl_min(dst_nparam, src_nparam));
581 if (dst_nparam > src_nparam)
582 isl_seq_clr(dst+1+src_nparam,
583 dst_nparam - src_nparam);
584 isl_seq_clr(dst+1+dst_nparam, in_off);
585 isl_seq_cpy(dst+1+dst_nparam+in_off,
587 isl_min(dst_in-in_off, src_in));
588 if (dst_in-in_off > src_in)
589 isl_seq_clr(dst+1+dst_nparam+in_off+src_in,
590 dst_in - in_off - src_in);
591 isl_seq_clr(dst+1+dst_nparam+dst_in, out_off);
592 isl_seq_cpy(dst+1+dst_nparam+dst_in+out_off,
593 src+1+src_nparam+src_in,
594 isl_min(dst_out-out_off, src_out));
595 if (dst_out-out_off > src_out)
596 isl_seq_clr(dst+1+dst_nparam+dst_in+out_off+src_out,
597 dst_out - out_off - src_out);
598 isl_seq_clr(dst+1+dst_nparam+dst_in+dst_out, div_off);
599 isl_seq_cpy(dst+1+dst_nparam+dst_in+dst_out+div_off,
600 src+1+src_nparam+src_in+src_out,
601 isl_min(dst_map->extra-div_off, src_map->n_div));
602 if (dst_map->n_div-div_off > src_map->n_div)
603 isl_seq_clr(dst+1+dst_nparam+dst_in+dst_out+
604 div_off+src_map->n_div,
605 dst_map->n_div - div_off - src_map->n_div);
608 static void copy_div(struct isl_basic_map *dst_map, isl_int *dst,
609 struct isl_basic_map *src_map, isl_int *src,
610 unsigned in_off, unsigned out_off, unsigned div_off)
612 isl_int_set(dst[0], src[0]);
613 copy_constraint(dst_map, dst+1, src_map, src+1, in_off, out_off, div_off);
616 static struct isl_basic_map *add_constraints(struct isl_basic_map *bmap1,
617 struct isl_basic_map *bmap2, unsigned i_pos, unsigned o_pos)
622 if (!bmap1 || !bmap2)
625 div_off = bmap1->n_div;
627 for (i = 0; i < bmap2->n_eq; ++i) {
628 int i1 = isl_basic_map_alloc_equality(bmap1);
631 copy_constraint(bmap1, bmap1->eq[i1], bmap2, bmap2->eq[i],
632 i_pos, o_pos, div_off);
635 for (i = 0; i < bmap2->n_ineq; ++i) {
636 int i1 = isl_basic_map_alloc_inequality(bmap1);
639 copy_constraint(bmap1, bmap1->ineq[i1], bmap2, bmap2->ineq[i],
640 i_pos, o_pos, div_off);
643 for (i = 0; i < bmap2->n_div; ++i) {
644 int i1 = isl_basic_map_alloc_div(bmap1);
647 copy_div(bmap1, bmap1->div[i1], bmap2, bmap2->div[i],
648 i_pos, o_pos, div_off);
651 isl_basic_map_free(bmap2);
656 isl_basic_map_free(bmap1);
657 isl_basic_map_free(bmap2);
661 static void copy_constraint_dim_map(isl_int *dst, isl_int *src,
662 struct isl_dim_map *dim_map)
666 for (i = 0; i < dim_map->len; ++i) {
667 if (dim_map->pos[i] < 0)
668 isl_int_set_si(dst[i], 0);
670 isl_int_set(dst[i], src[dim_map->pos[i]]);
674 static void copy_div_dim_map(isl_int *dst, isl_int *src,
675 struct isl_dim_map *dim_map)
677 isl_int_set(dst[0], src[0]);
678 copy_constraint_dim_map(dst+1, src+1, dim_map);
681 static struct isl_basic_map *add_constraints_dim_map(struct isl_basic_map *dst,
682 struct isl_basic_map *src, struct isl_dim_map *dim_map)
686 if (!src || !dst || !dim_map)
689 for (i = 0; i < src->n_eq; ++i) {
690 int i1 = isl_basic_map_alloc_equality(dst);
693 copy_constraint_dim_map(dst->eq[i1], src->eq[i], dim_map);
696 for (i = 0; i < src->n_ineq; ++i) {
697 int i1 = isl_basic_map_alloc_inequality(dst);
700 copy_constraint_dim_map(dst->ineq[i1], src->ineq[i], dim_map);
703 for (i = 0; i < src->n_div; ++i) {
704 int i1 = isl_basic_map_alloc_div(dst);
707 copy_div_dim_map(dst->div[i1], src->div[i], dim_map);
711 isl_basic_map_free(src);
716 isl_basic_map_free(src);
717 isl_basic_map_free(dst);
721 static struct isl_basic_set *set_add_constraints(struct isl_basic_set *bset1,
722 struct isl_basic_set *bset2, unsigned pos)
724 return (struct isl_basic_set *)
725 add_constraints((struct isl_basic_map *)bset1,
726 (struct isl_basic_map *)bset2, 0, pos);
729 struct isl_basic_map *isl_basic_map_extend_dim(struct isl_basic_map *base,
730 struct isl_dim *dim, unsigned extra,
731 unsigned n_eq, unsigned n_ineq)
733 struct isl_basic_map *ext;
740 base = isl_basic_map_cow(base);
744 dims_ok = isl_dim_equal(base->dim, dim) &&
745 base->extra >= base->n_div + extra;
747 if (dims_ok && n_eq == 0 && n_ineq == 0) {
752 isl_assert(base->ctx, base->dim->nparam <= dim->nparam, goto error);
753 isl_assert(base->ctx, base->dim->n_in <= dim->n_in, goto error);
754 isl_assert(base->ctx, base->dim->n_out <= dim->n_out, goto error);
755 extra += base->extra;
757 n_ineq += base->n_ineq;
759 ext = isl_basic_map_alloc_dim(base->ctx, dim, extra, n_eq, n_ineq);
765 ext = add_constraints(ext, base, 0, 0);
768 F_CLR(ext, ISL_BASIC_SET_FINAL);
775 isl_basic_map_free(base);
779 struct isl_basic_map *isl_basic_map_extend_constraints(
780 struct isl_basic_map *base, unsigned n_eq, unsigned n_ineq)
784 return isl_basic_map_extend_dim(base, isl_dim_copy(base->dim),
788 struct isl_basic_map *isl_basic_map_extend(struct isl_basic_map *base,
789 unsigned nparam, unsigned n_in, unsigned n_out, unsigned extra,
790 unsigned n_eq, unsigned n_ineq)
792 struct isl_basic_map *bmap;
797 dim = isl_dim_alloc(base->ctx, nparam, n_in, n_out);
801 bmap = isl_basic_map_extend_dim(base, dim, extra, n_eq, n_ineq);
805 struct isl_basic_set *isl_basic_set_extend(struct isl_basic_set *base,
806 unsigned nparam, unsigned dim, unsigned extra,
807 unsigned n_eq, unsigned n_ineq)
809 return (struct isl_basic_set *)
810 isl_basic_map_extend((struct isl_basic_map *)base,
811 nparam, 0, dim, extra, n_eq, n_ineq);
814 struct isl_basic_set *isl_basic_set_extend_constraints(
815 struct isl_basic_set *base, unsigned n_eq, unsigned n_ineq)
817 return (struct isl_basic_set *)
818 isl_basic_map_extend_constraints((struct isl_basic_map *)base,
822 struct isl_basic_set *isl_basic_set_cow(struct isl_basic_set *bset)
824 return (struct isl_basic_set *)
825 isl_basic_map_cow((struct isl_basic_map *)bset);
828 struct isl_basic_map *isl_basic_map_cow(struct isl_basic_map *bmap)
835 bmap = isl_basic_map_dup(bmap);
837 F_CLR(bmap, ISL_BASIC_SET_FINAL);
841 struct isl_set *isl_set_cow(struct isl_set *set)
849 return isl_set_dup(set);
852 struct isl_map *isl_map_cow(struct isl_map *map)
860 return isl_map_dup(map);
863 static void swap_vars(struct isl_blk blk, isl_int *a,
864 unsigned a_len, unsigned b_len)
866 isl_seq_cpy(blk.data, a+a_len, b_len);
867 isl_seq_cpy(blk.data+b_len, a, a_len);
868 isl_seq_cpy(a, blk.data, b_len+a_len);
871 struct isl_basic_set *isl_basic_set_swap_vars(
872 struct isl_basic_set *bset, unsigned n)
882 nparam = isl_basic_set_n_param(bset);
883 dim = isl_basic_set_n_dim(bset);
884 isl_assert(bset->ctx, n <= dim, goto error);
889 bset = isl_basic_set_cow(bset);
893 blk = isl_blk_alloc(bset->ctx, dim);
894 if (isl_blk_is_error(blk))
897 for (i = 0; i < bset->n_eq; ++i)
899 bset->eq[i]+1+nparam, n, dim - n);
901 for (i = 0; i < bset->n_ineq; ++i)
903 bset->ineq[i]+1+nparam, n, dim - n);
905 for (i = 0; i < bset->n_div; ++i)
907 bset->div[i]+1+1+nparam, n, dim - n);
909 isl_blk_free(bset->ctx, blk);
911 F_CLR(bset, ISL_BASIC_SET_NORMALIZED);
915 isl_basic_set_free(bset);
919 struct isl_set *isl_set_swap_vars(struct isl_set *set, unsigned n)
922 set = isl_set_cow(set);
926 for (i = 0; i < set->n; ++i) {
927 set->p[i] = isl_basic_set_swap_vars(set->p[i], n);
933 F_CLR(set, ISL_SET_NORMALIZED);
937 static void constraint_drop_vars(isl_int *c, unsigned n, unsigned rem)
939 isl_seq_cpy(c, c + n, rem);
940 isl_seq_clr(c + rem, n);
943 struct isl_basic_set *isl_basic_set_drop_dims(
944 struct isl_basic_set *bset, unsigned first, unsigned n)
951 isl_assert(bset->ctx, first + n <= bset->dim->n_out, goto error);
956 bset = isl_basic_set_cow(bset);
959 bset->dim = isl_dim_cow(bset->dim);
963 for (i = 0; i < bset->n_eq; ++i)
964 constraint_drop_vars(bset->eq[i]+1+bset->dim->nparam+first, n,
965 (bset->dim->n_out-first-n)+bset->extra);
967 for (i = 0; i < bset->n_ineq; ++i)
968 constraint_drop_vars(bset->ineq[i]+1+bset->dim->nparam+first, n,
969 (bset->dim->n_out-first-n)+bset->extra);
971 for (i = 0; i < bset->n_div; ++i)
972 constraint_drop_vars(bset->div[i]+1+1+bset->dim->nparam+first, n,
973 (bset->dim->n_out-first-n)+bset->extra);
975 bset->dim->n_out -= n;
978 F_CLR(bset, ISL_BASIC_SET_NORMALIZED);
979 bset = isl_basic_set_simplify(bset);
980 return isl_basic_set_finalize(bset);
982 isl_basic_set_free(bset);
986 static struct isl_set *isl_set_drop_dims(
987 struct isl_set *set, unsigned first, unsigned n)
994 isl_assert(set->ctx, first + n <= set->dim->n_out, goto error);
998 set = isl_set_cow(set);
1001 set->dim = isl_dim_cow(set->dim);
1005 for (i = 0; i < set->n; ++i) {
1006 set->p[i] = isl_basic_set_drop_dims(set->p[i], first, n);
1010 set->dim->n_out -= n;
1012 F_CLR(set, ISL_SET_NORMALIZED);
1019 struct isl_basic_map *isl_basic_map_drop_inputs(
1020 struct isl_basic_map *bmap, unsigned first, unsigned n)
1030 nparam = isl_basic_map_n_param(bmap);
1031 n_in = isl_basic_map_n_in(bmap);
1032 n_out = isl_basic_map_n_out(bmap);
1033 isl_assert(bmap->ctx, first + n <= n_in, goto error);
1038 bmap = isl_basic_map_cow(bmap);
1041 bmap->dim = isl_dim_cow(bmap->dim);
1045 for (i = 0; i < bmap->n_eq; ++i)
1046 constraint_drop_vars(bmap->eq[i]+1+nparam+first, n,
1047 (n_in-first-n)+n_out+bmap->extra);
1049 for (i = 0; i < bmap->n_ineq; ++i)
1050 constraint_drop_vars(bmap->ineq[i]+1+nparam+first, n,
1051 (n_in-first-n)+n_out+bmap->extra);
1053 for (i = 0; i < bmap->n_div; ++i)
1054 constraint_drop_vars(bmap->div[i]+1+1+nparam+first, n,
1055 (n_in-first-n)+n_out+bmap->extra);
1057 bmap->dim->n_in -= n;
1060 F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1061 bmap = isl_basic_map_simplify(bmap);
1062 return isl_basic_map_finalize(bmap);
1064 isl_basic_map_free(bmap);
1068 static struct isl_map *isl_map_drop_inputs(
1069 struct isl_map *map, unsigned first, unsigned n)
1076 isl_assert(map->ctx, first + n <= map->dim->n_in, goto error);
1080 map = isl_map_cow(map);
1083 map->dim = isl_dim_cow(map->dim);
1087 for (i = 0; i < map->n; ++i) {
1088 map->p[i] = isl_basic_map_drop_inputs(map->p[i], first, n);
1092 map->dim->n_in -= n;
1093 F_CLR(map, ISL_MAP_NORMALIZED);
1102 * We don't cow, as the div is assumed to be redundant.
1104 static struct isl_basic_map *isl_basic_map_drop_div(
1105 struct isl_basic_map *bmap, unsigned div)
1113 pos = 1 + isl_dim_total(bmap->dim) + div;
1115 isl_assert(bmap->ctx, div < bmap->n_div, goto error);
1117 for (i = 0; i < bmap->n_eq; ++i)
1118 constraint_drop_vars(bmap->eq[i]+pos, 1, bmap->extra-div-1);
1120 for (i = 0; i < bmap->n_ineq; ++i) {
1121 if (!isl_int_is_zero(bmap->ineq[i][pos])) {
1122 isl_basic_map_drop_inequality(bmap, i);
1126 constraint_drop_vars(bmap->ineq[i]+pos, 1, bmap->extra-div-1);
1129 for (i = 0; i < bmap->n_div; ++i)
1130 constraint_drop_vars(bmap->div[i]+1+pos, 1, bmap->extra-div-1);
1132 if (div != bmap->n_div - 1) {
1134 isl_int *t = bmap->div[div];
1136 for (j = div; j < bmap->n_div - 1; ++j)
1137 bmap->div[j] = bmap->div[j+1];
1139 bmap->div[bmap->n_div - 1] = t;
1141 F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1142 isl_basic_map_free_div(bmap, 1);
1146 isl_basic_map_free(bmap);
1150 static void eliminate_div(struct isl_basic_map *bmap, isl_int *eq, unsigned div)
1153 unsigned pos = 1 + isl_dim_total(bmap->dim) + div;
1155 len = 1 + isl_basic_map_total_dim(bmap);
1157 for (i = 0; i < bmap->n_eq; ++i)
1158 if (bmap->eq[i] != eq)
1159 isl_seq_elim(bmap->eq[i], eq, pos, len, NULL);
1161 for (i = 0; i < bmap->n_ineq; ++i)
1162 isl_seq_elim(bmap->ineq[i], eq, pos, len, NULL);
1164 /* We need to be careful about circular definitions,
1165 * so for now we just remove the definitions of other divs that
1166 * depend on this div and (possibly) recompute them later.
1168 for (i = 0; i < bmap->n_div; ++i)
1169 if (!isl_int_is_zero(bmap->div[i][0]) &&
1170 !isl_int_is_zero(bmap->div[i][1 + pos]))
1171 isl_seq_clr(bmap->div[i], 1 + len);
1173 isl_basic_map_drop_div(bmap, div);
1176 struct isl_basic_map *isl_basic_map_set_to_empty(struct isl_basic_map *bmap)
1182 total = isl_basic_map_total_dim(bmap);
1183 isl_basic_map_free_div(bmap, bmap->n_div);
1184 isl_basic_map_free_inequality(bmap, bmap->n_ineq);
1186 isl_basic_map_free_equality(bmap, bmap->n_eq-1);
1188 isl_basic_map_alloc_equality(bmap);
1192 isl_int_set_si(bmap->eq[i][0], 1);
1193 isl_seq_clr(bmap->eq[i]+1, total);
1194 F_SET(bmap, ISL_BASIC_MAP_EMPTY);
1195 return isl_basic_map_finalize(bmap);
1197 isl_basic_map_free(bmap);
1201 struct isl_basic_set *isl_basic_set_set_to_empty(struct isl_basic_set *bset)
1203 return (struct isl_basic_set *)
1204 isl_basic_map_set_to_empty((struct isl_basic_map *)bset);
1207 static void swap_equality(struct isl_basic_map *bmap, int a, int b)
1209 isl_int *t = bmap->eq[a];
1210 bmap->eq[a] = bmap->eq[b];
1214 static void swap_inequality(struct isl_basic_map *bmap, int a, int b)
1217 isl_int *t = bmap->ineq[a];
1218 bmap->ineq[a] = bmap->ineq[b];
1223 static void set_swap_inequality(struct isl_basic_set *bset, int a, int b)
1225 swap_inequality((struct isl_basic_map *)bset, a, b);
1228 static void swap_div(struct isl_basic_map *bmap, int a, int b)
1231 unsigned off = isl_dim_total(bmap->dim);
1232 isl_int *t = bmap->div[a];
1233 bmap->div[a] = bmap->div[b];
1236 for (i = 0; i < bmap->n_eq; ++i)
1237 isl_int_swap(bmap->eq[i][1+off+a], bmap->eq[i][1+off+b]);
1239 for (i = 0; i < bmap->n_ineq; ++i)
1240 isl_int_swap(bmap->ineq[i][1+off+a], bmap->ineq[i][1+off+b]);
1242 for (i = 0; i < bmap->n_div; ++i)
1243 isl_int_swap(bmap->div[i][1+1+off+a], bmap->div[i][1+1+off+b]);
1244 F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1247 static void eliminate_var_using_equality(struct isl_basic_map *bmap,
1248 unsigned pos, isl_int *eq, int *progress)
1253 total = isl_basic_map_total_dim(bmap);
1254 for (k = 0; k < bmap->n_eq; ++k) {
1255 if (bmap->eq[k] == eq)
1257 if (isl_int_is_zero(bmap->eq[k][1+pos]))
1261 isl_seq_elim(bmap->eq[k], eq, 1+pos, 1+total, NULL);
1264 for (k = 0; k < bmap->n_ineq; ++k) {
1265 if (isl_int_is_zero(bmap->ineq[k][1+pos]))
1269 isl_seq_elim(bmap->ineq[k], eq, 1+pos, 1+total, NULL);
1270 F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1273 for (k = 0; k < bmap->n_div; ++k) {
1274 if (isl_int_is_zero(bmap->div[k][0]))
1276 if (isl_int_is_zero(bmap->div[k][1+1+pos]))
1280 isl_seq_elim(bmap->div[k]+1, eq,
1281 1+pos, 1+total, &bmap->div[k][0]);
1282 F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1287 struct isl_basic_map *isl_basic_map_gauss(
1288 struct isl_basic_map *bmap, int *progress)
1299 total = isl_basic_map_total_dim(bmap);
1300 total_var = total - bmap->n_div;
1302 last_var = total - 1;
1303 for (done = 0; done < bmap->n_eq; ++done) {
1304 for (; last_var >= 0; --last_var) {
1305 for (k = done; k < bmap->n_eq; ++k)
1306 if (!isl_int_is_zero(bmap->eq[k][1+last_var]))
1314 swap_equality(bmap, k, done);
1315 if (isl_int_is_neg(bmap->eq[done][1+last_var]))
1316 isl_seq_neg(bmap->eq[done], bmap->eq[done], 1+total);
1318 eliminate_var_using_equality(bmap, last_var, bmap->eq[done],
1321 if (last_var >= total_var &&
1322 isl_int_is_zero(bmap->div[last_var - total_var][0])) {
1323 unsigned div = last_var - total_var;
1324 isl_seq_neg(bmap->div[div]+1, bmap->eq[done], 1+total);
1325 isl_int_set_si(bmap->div[div][1+1+last_var], 0);
1326 isl_int_set(bmap->div[div][0],
1327 bmap->eq[done][1+last_var]);
1328 F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1331 if (done == bmap->n_eq)
1333 for (k = done; k < bmap->n_eq; ++k) {
1334 if (isl_int_is_zero(bmap->eq[k][0]))
1336 return isl_basic_map_set_to_empty(bmap);
1338 isl_basic_map_free_equality(bmap, bmap->n_eq-done);
1342 struct isl_basic_set *isl_basic_set_gauss(
1343 struct isl_basic_set *bset, int *progress)
1345 return (struct isl_basic_set*)isl_basic_map_gauss(
1346 (struct isl_basic_map *)bset, progress);
1349 static unsigned int round_up(unsigned int v)
1360 static int hash_index(isl_int ***index, unsigned int size, int bits,
1361 struct isl_basic_map *bmap, int k)
1364 unsigned total = isl_basic_map_total_dim(bmap);
1365 uint32_t hash = isl_seq_get_hash_bits(bmap->ineq[k]+1, total, bits);
1366 for (h = hash; index[h]; h = (h+1) % size)
1367 if (&bmap->ineq[k] != index[h] &&
1368 isl_seq_eq(bmap->ineq[k]+1, index[h][0]+1, total))
1373 static int set_hash_index(isl_int ***index, unsigned int size, int bits,
1374 struct isl_basic_set *bset, int k)
1376 return hash_index(index, size, bits, (struct isl_basic_map *)bset, k);
1379 static struct isl_basic_map *remove_duplicate_constraints(
1380 struct isl_basic_map *bmap, int *progress)
1386 unsigned total = isl_basic_map_total_dim(bmap);
1389 if (bmap->n_ineq <= 1)
1392 size = round_up(4 * (bmap->n_ineq+1) / 3 - 1);
1393 bits = ffs(size) - 1;
1394 index = isl_calloc_array(ctx, isl_int **, size);
1398 index[isl_seq_get_hash_bits(bmap->ineq[0]+1, total, bits)] = &bmap->ineq[0];
1399 for (k = 1; k < bmap->n_ineq; ++k) {
1400 h = hash_index(index, size, bits, bmap, k);
1402 index[h] = &bmap->ineq[k];
1407 l = index[h] - &bmap->ineq[0];
1408 if (isl_int_lt(bmap->ineq[k][0], bmap->ineq[l][0]))
1409 swap_inequality(bmap, k, l);
1410 isl_basic_map_drop_inequality(bmap, k);
1414 for (k = 0; k < bmap->n_ineq-1; ++k) {
1415 isl_seq_neg(bmap->ineq[k]+1, bmap->ineq[k]+1, total);
1416 h = hash_index(index, size, bits, bmap, k);
1417 isl_seq_neg(bmap->ineq[k]+1, bmap->ineq[k]+1, total);
1420 l = index[h] - &bmap->ineq[0];
1421 isl_int_add(sum, bmap->ineq[k][0], bmap->ineq[l][0]);
1422 if (isl_int_is_pos(sum))
1424 if (isl_int_is_zero(sum)) {
1425 /* We need to break out of the loop after these
1426 * changes since the contents of the hash
1427 * will no longer be valid.
1428 * Plus, we probably we want to regauss first.
1430 isl_basic_map_drop_inequality(bmap, l);
1431 isl_basic_map_inequality_to_equality(bmap, k);
1433 bmap = isl_basic_map_set_to_empty(bmap);
1442 static void compute_elimination_index(struct isl_basic_map *bmap, int *elim)
1447 total = isl_dim_total(bmap->dim);
1448 for (d = 0; d < total; ++d)
1450 for (d = total - 1, i = 0; d >= 0 && i < bmap->n_eq; ++i) {
1451 for (; d >= 0; --d) {
1452 if (isl_int_is_zero(bmap->eq[i][1+d]))
1460 static void set_compute_elimination_index(struct isl_basic_set *bset, int *elim)
1462 return compute_elimination_index((struct isl_basic_map *)bset, elim);
1465 static int reduced_using_equalities(isl_int *dst, isl_int *src,
1466 struct isl_basic_map *bmap, int *elim)
1472 total = isl_dim_total(bmap->dim);
1473 for (d = total - 1; d >= 0; --d) {
1474 if (isl_int_is_zero(src[1+d]))
1479 isl_seq_cpy(dst, src, 1 + total);
1482 isl_seq_elim(dst, bmap->eq[elim[d]], 1 + d, 1 + total, NULL);
1487 static int set_reduced_using_equalities(isl_int *dst, isl_int *src,
1488 struct isl_basic_set *bset, int *elim)
1490 return reduced_using_equalities(dst, src,
1491 (struct isl_basic_map *)bset, elim);
1494 /* Quick check to see if two basic maps are disjoint.
1495 * In particular, we reduce the equalities and inequalities of
1496 * one basic map in the context of the equalities of the other
1497 * basic map and check if we get a contradiction.
1499 int isl_basic_map_fast_is_disjoint(struct isl_basic_map *bmap1,
1500 struct isl_basic_map *bmap2)
1502 struct isl_vec *v = NULL;
1507 if (!bmap1 || !bmap2)
1509 isl_assert(bmap1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim),
1511 if (bmap1->n_div || bmap2->n_div)
1513 if (!bmap1->n_eq && !bmap2->n_eq)
1516 total = isl_dim_total(bmap1->dim);
1519 v = isl_vec_alloc(bmap1->ctx, 1 + total);
1522 elim = isl_alloc_array(bmap1->ctx, int, total);
1525 compute_elimination_index(bmap1, elim);
1526 for (i = 0; i < bmap2->n_eq; ++i) {
1528 reduced = reduced_using_equalities(v->block.data, bmap2->eq[i],
1530 if (reduced && !isl_int_is_zero(v->block.data[0]) &&
1531 isl_seq_first_non_zero(v->block.data + 1, total) == -1)
1534 for (i = 0; i < bmap2->n_ineq; ++i) {
1536 reduced = reduced_using_equalities(v->block.data,
1537 bmap2->ineq[i], bmap1, elim);
1538 if (reduced && isl_int_is_neg(v->block.data[0]) &&
1539 isl_seq_first_non_zero(v->block.data + 1, total) == -1)
1542 compute_elimination_index(bmap2, elim);
1543 for (i = 0; i < bmap1->n_ineq; ++i) {
1545 reduced = reduced_using_equalities(v->block.data,
1546 bmap1->ineq[i], bmap2, elim);
1547 if (reduced && isl_int_is_neg(v->block.data[0]) &&
1548 isl_seq_first_non_zero(v->block.data + 1, total) == -1)
1551 isl_vec_free(bmap1->ctx, v);
1555 isl_vec_free(bmap1->ctx, v);
1559 isl_vec_free(bmap1->ctx, v);
1564 int isl_basic_set_fast_is_disjoint(struct isl_basic_set *bset1,
1565 struct isl_basic_set *bset2)
1567 return isl_basic_map_fast_is_disjoint((struct isl_basic_map *)bset1,
1568 (struct isl_basic_map *)bset2);
1571 int isl_map_fast_is_disjoint(struct isl_map *map1, struct isl_map *map2)
1578 if (isl_map_fast_is_equal(map1, map2))
1581 for (i = 0; i < map1->n; ++i) {
1582 for (j = 0; j < map2->n; ++j) {
1583 int d = isl_basic_map_fast_is_disjoint(map1->p[i],
1592 int isl_set_fast_is_disjoint(struct isl_set *set1, struct isl_set *set2)
1594 return isl_map_fast_is_disjoint((struct isl_map *)set1,
1595 (struct isl_map *)set2);
1598 static struct isl_basic_map *remove_duplicate_divs(
1599 struct isl_basic_map *bmap, int *progress)
1606 unsigned total_var = isl_dim_total(bmap->dim);
1607 unsigned total = total_var + bmap->n_div;
1608 struct isl_ctx *ctx;
1610 if (bmap->n_div <= 1)
1614 for (k = bmap->n_div - 1; k >= 0; --k)
1615 if (!isl_int_is_zero(bmap->div[k][0]))
1620 size = round_up(4 * bmap->n_div / 3 - 1);
1621 bits = ffs(size) - 1;
1622 index = isl_calloc_array(ctx, int, size);
1625 eq = isl_blk_alloc(ctx, 1+total);
1626 if (isl_blk_is_error(eq))
1629 isl_seq_clr(eq.data, 1+total);
1630 index[isl_seq_get_hash_bits(bmap->div[k], 2+total, bits)] = k + 1;
1631 for (--k; k >= 0; --k) {
1634 if (isl_int_is_zero(bmap->div[k][0]))
1637 hash = isl_seq_get_hash_bits(bmap->div[k], 2+total, bits);
1638 for (h = hash; index[h]; h = (h+1) % size)
1639 if (isl_seq_eq(bmap->div[k],
1640 bmap->div[index[h]-1], 2+total))
1645 isl_int_set_si(eq.data[1+total_var+k], -1);
1646 isl_int_set_si(eq.data[1+total_var+l], 1);
1647 eliminate_div(bmap, eq.data, l);
1648 isl_int_set_si(eq.data[1+total_var+k], 0);
1649 isl_int_set_si(eq.data[1+total_var+l], 0);
1654 isl_blk_free(ctx, eq);
1660 /* Elimininate divs based on equalities
1662 static struct isl_basic_map *eliminate_divs_eq(
1663 struct isl_basic_map *bmap, int *progress)
1673 off = 1 + isl_dim_total(bmap->dim);
1675 for (d = bmap->n_div - 1; d >= 0 ; --d) {
1676 for (i = 0; i < bmap->n_eq; ++i) {
1677 if (!isl_int_is_one(bmap->eq[i][off + d]) &&
1678 !isl_int_is_negone(bmap->eq[i][off + d]))
1682 eliminate_div(bmap, bmap->eq[i], d);
1683 isl_basic_map_drop_equality(bmap, i);
1688 return eliminate_divs_eq(bmap, progress);
1692 static struct isl_basic_map *normalize_constraints(struct isl_basic_map *bmap)
1696 unsigned total = isl_basic_map_total_dim(bmap);
1699 for (i = bmap->n_eq - 1; i >= 0; --i) {
1700 isl_seq_gcd(bmap->eq[i]+1, total, &gcd);
1701 if (isl_int_is_zero(gcd)) {
1702 if (!isl_int_is_zero(bmap->eq[i][0])) {
1703 bmap = isl_basic_map_set_to_empty(bmap);
1706 isl_basic_map_drop_equality(bmap, i);
1709 if (F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL))
1710 isl_int_gcd(gcd, gcd, bmap->eq[i][0]);
1711 if (isl_int_is_one(gcd))
1713 if (!isl_int_is_divisible_by(bmap->eq[i][0], gcd)) {
1714 bmap = isl_basic_map_set_to_empty(bmap);
1717 isl_seq_scale_down(bmap->eq[i], bmap->eq[i], gcd, 1+total);
1720 for (i = bmap->n_ineq - 1; i >= 0; --i) {
1721 isl_seq_gcd(bmap->ineq[i]+1, total, &gcd);
1722 if (isl_int_is_zero(gcd)) {
1723 if (isl_int_is_neg(bmap->ineq[i][0])) {
1724 bmap = isl_basic_map_set_to_empty(bmap);
1727 isl_basic_map_drop_inequality(bmap, i);
1730 if (F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL))
1731 isl_int_gcd(gcd, gcd, bmap->ineq[i][0]);
1732 if (isl_int_is_one(gcd))
1734 isl_int_fdiv_q(bmap->ineq[i][0], bmap->ineq[i][0], gcd);
1735 isl_seq_scale_down(bmap->ineq[i]+1, bmap->ineq[i]+1, gcd, total);
1743 /* Eliminate the specified variables from the constraints using
1744 * Fourier-Motzkin. The variables themselves are not removed.
1746 struct isl_basic_map *isl_basic_map_eliminate_vars(
1747 struct isl_basic_map *bmap, int pos, unsigned n)
1757 total = isl_basic_map_total_dim(bmap);
1759 bmap = isl_basic_map_cow(bmap);
1760 for (d = pos + n - 1; d >= pos; --d) {
1761 int n_lower, n_upper;
1764 for (i = 0; i < bmap->n_eq; ++i) {
1765 if (isl_int_is_zero(bmap->eq[i][1+d]))
1767 eliminate_var_using_equality(bmap, d, bmap->eq[i], NULL);
1768 isl_basic_map_drop_equality(bmap, i);
1775 for (i = 0; i < bmap->n_ineq; ++i) {
1776 if (isl_int_is_pos(bmap->ineq[i][1+d]))
1778 else if (isl_int_is_neg(bmap->ineq[i][1+d]))
1781 bmap = isl_basic_map_extend_constraints(bmap,
1782 0, n_lower * n_upper);
1783 for (i = bmap->n_ineq - 1; i >= 0; --i) {
1785 if (isl_int_is_zero(bmap->ineq[i][1+d]))
1788 for (j = 0; j < i; ++j) {
1789 if (isl_int_is_zero(bmap->ineq[j][1+d]))
1792 if (isl_int_sgn(bmap->ineq[i][1+d]) ==
1793 isl_int_sgn(bmap->ineq[j][1+d]))
1795 k = isl_basic_map_alloc_inequality(bmap);
1798 isl_seq_cpy(bmap->ineq[k], bmap->ineq[i],
1800 isl_seq_elim(bmap->ineq[k], bmap->ineq[j],
1801 1+d, 1+total, NULL);
1803 isl_basic_map_drop_inequality(bmap, i);
1806 if (n_lower > 0 && n_upper > 0) {
1807 bmap = normalize_constraints(bmap);
1808 bmap = remove_duplicate_constraints(bmap, NULL);
1809 bmap = isl_basic_map_gauss(bmap, NULL);
1810 bmap = isl_basic_map_convex_hull(bmap);
1813 if (F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
1817 F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
1820 isl_basic_map_free(bmap);
1824 struct isl_basic_set *isl_basic_set_eliminate_vars(
1825 struct isl_basic_set *bset, unsigned pos, unsigned n)
1827 return (struct isl_basic_set *)isl_basic_map_eliminate_vars(
1828 (struct isl_basic_map *)bset, pos, n);
1831 /* Eliminate the specified n dimensions starting at first from the
1832 * constraints using Fourier-Motzkin, The dimensions themselves
1835 struct isl_set *isl_set_eliminate_dims(struct isl_set *set,
1836 unsigned first, unsigned n)
1846 set = isl_set_cow(set);
1849 isl_assert(set->ctx, first+n <= isl_set_n_dim(set), goto error);
1850 nparam = isl_set_n_param(set);
1852 for (i = 0; i < set->n; ++i) {
1853 set->p[i] = isl_basic_set_eliminate_vars(set->p[i],
1864 /* Project out n dimensions starting at first using Fourier-Motzkin */
1865 struct isl_set *isl_set_remove_dims(struct isl_set *set,
1866 unsigned first, unsigned n)
1868 set = isl_set_eliminate_dims(set, first, n);
1869 set = isl_set_drop_dims(set, first, n);
1873 struct isl_basic_set *isl_basic_set_remove_divs(struct isl_basic_set *bset)
1875 bset = isl_basic_set_eliminate_vars(bset, isl_dim_total(bset->dim),
1883 struct isl_set *isl_set_remove_divs(struct isl_set *set)
1892 set = isl_set_cow(set);
1896 for (i = 0; i < set->n; ++i) {
1897 set->p[i] = isl_basic_set_remove_divs(set->p[i]);
1907 /* Project out n inputs starting at first using Fourier-Motzkin */
1908 struct isl_map *isl_map_remove_inputs(struct isl_map *map,
1909 unsigned first, unsigned n)
1917 map = isl_map_cow(map);
1920 nparam = isl_map_n_param(map);
1921 isl_assert(map->ctx, first+n <= isl_map_n_in(map), goto error);
1923 for (i = 0; i < map->n; ++i) {
1924 map->p[i] = isl_basic_map_eliminate_vars(map->p[i],
1929 map = isl_map_drop_inputs(map, first, n);
1936 /* Project out n dimensions starting at first using Fourier-Motzkin */
1937 struct isl_basic_set *isl_basic_set_remove_dims(struct isl_basic_set *bset,
1938 unsigned first, unsigned n)
1940 unsigned nparam = isl_basic_set_n_param(bset);
1941 bset = isl_basic_set_eliminate_vars(bset, nparam + first, n);
1942 bset = isl_basic_set_drop_dims(bset, first, n);
1946 /* Elimininate divs based on inequalities
1948 static struct isl_basic_map *eliminate_divs_ineq(
1949 struct isl_basic_map *bmap, int *progress)
1954 struct isl_ctx *ctx;
1960 off = 1 + isl_dim_total(bmap->dim);
1962 for (d = bmap->n_div - 1; d >= 0 ; --d) {
1963 for (i = 0; i < bmap->n_eq; ++i)
1964 if (!isl_int_is_zero(bmap->eq[i][off + d]))
1968 for (i = 0; i < bmap->n_ineq; ++i)
1969 if (isl_int_abs_gt(bmap->ineq[i][off + d], ctx->one))
1971 if (i < bmap->n_ineq)
1974 bmap = isl_basic_map_eliminate_vars(bmap, (off-1)+d, 1);
1975 if (F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
1977 bmap = isl_basic_map_drop_div(bmap, d);
1984 struct isl_basic_map *isl_basic_map_simplify(struct isl_basic_map *bmap)
1991 bmap = normalize_constraints(bmap);
1992 bmap = eliminate_divs_eq(bmap, &progress);
1993 bmap = eliminate_divs_ineq(bmap, &progress);
1994 bmap = isl_basic_map_gauss(bmap, &progress);
1995 bmap = remove_duplicate_divs(bmap, &progress);
1996 bmap = remove_duplicate_constraints(bmap, &progress);
2001 struct isl_basic_set *isl_basic_set_simplify(struct isl_basic_set *bset)
2003 return (struct isl_basic_set *)
2004 isl_basic_map_simplify((struct isl_basic_map *)bset);
2007 static void dump_term(struct isl_basic_map *bmap,
2008 isl_int c, int pos, FILE *out)
2010 unsigned in = isl_basic_map_n_in(bmap);
2011 unsigned dim = in + isl_basic_map_n_out(bmap);
2012 unsigned nparam = isl_basic_map_n_param(bmap);
2014 isl_int_print(out, c, 0);
2016 if (!isl_int_is_one(c))
2017 isl_int_print(out, c, 0);
2018 if (pos < 1 + nparam)
2019 fprintf(out, "p%d", pos - 1);
2020 else if (pos < 1 + nparam + in)
2021 fprintf(out, "i%d", pos - 1 - nparam);
2022 else if (pos < 1 + nparam + dim)
2023 fprintf(out, "o%d", pos - 1 - nparam - in);
2025 fprintf(out, "e%d", pos - 1 - nparam - dim);
2029 static void dump_constraint_sign(struct isl_basic_map *bmap, isl_int *c,
2030 int sign, FILE *out)
2034 unsigned len = 1 + isl_basic_map_total_dim(bmap);
2038 for (i = 0, first = 1; i < len; ++i) {
2039 if (isl_int_sgn(c[i]) * sign <= 0)
2042 fprintf(out, " + ");
2044 isl_int_abs(v, c[i]);
2045 dump_term(bmap, v, i, out);
2052 static void dump_constraint(struct isl_basic_map *bmap, isl_int *c,
2053 const char *op, FILE *out, int indent)
2057 fprintf(out, "%*s", indent, "");
2059 dump_constraint_sign(bmap, c, 1, out);
2060 fprintf(out, " %s ", op);
2061 dump_constraint_sign(bmap, c, -1, out);
2065 for (i = bmap->n_div; i < bmap->extra; ++i) {
2066 if (isl_int_is_zero(c[1+isl_dim_total(bmap->dim)+i]))
2068 fprintf(out, "%*s", indent, "");
2069 fprintf(out, "ERROR: unused div coefficient not zero\n");
2074 static void dump_constraints(struct isl_basic_map *bmap,
2075 isl_int **c, unsigned n,
2076 const char *op, FILE *out, int indent)
2080 for (i = 0; i < n; ++i)
2081 dump_constraint(bmap, c[i], op, out, indent);
2084 static void dump_affine(struct isl_basic_map *bmap, isl_int *exp, FILE *out)
2088 unsigned total = isl_basic_map_total_dim(bmap);
2090 for (j = 0; j < 1 + total; ++j) {
2091 if (isl_int_is_zero(exp[j]))
2093 if (!first && isl_int_is_pos(exp[j]))
2095 dump_term(bmap, exp[j], j, out);
2100 static void dump(struct isl_basic_map *bmap, FILE *out, int indent)
2104 dump_constraints(bmap, bmap->eq, bmap->n_eq, "=", out, indent);
2105 dump_constraints(bmap, bmap->ineq, bmap->n_ineq, ">=", out, indent);
2107 for (i = 0; i < bmap->n_div; ++i) {
2108 fprintf(out, "%*s", indent, "");
2109 fprintf(out, "e%d = [(", i);
2110 dump_affine(bmap, bmap->div[i]+1, out);
2112 isl_int_print(out, bmap->div[i][0], 0);
2113 fprintf(out, "]\n");
2117 void isl_basic_set_dump(struct isl_basic_set *bset, FILE *out, int indent)
2120 fprintf(out, "null basic set\n");
2124 fprintf(out, "%*s", indent, "");
2125 fprintf(out, "ref: %d, nparam: %d, dim: %d, extra: %d, flags: %x\n",
2126 bset->ref, bset->dim->nparam, bset->dim->n_out,
2127 bset->extra, bset->flags);
2128 dump((struct isl_basic_map *)bset, out, indent);
2131 void isl_basic_map_dump(struct isl_basic_map *bmap, FILE *out, int indent)
2134 fprintf(out, "null basic map\n");
2138 fprintf(out, "%*s", indent, "");
2139 fprintf(out, "ref: %d, nparam: %d, in: %d, out: %d, extra: %d, flags: %x\n",
2141 bmap->dim->nparam, bmap->dim->n_in, bmap->dim->n_out,
2142 bmap->extra, bmap->flags);
2143 dump(bmap, out, indent);
2146 int isl_inequality_negate(struct isl_basic_map *bmap, unsigned pos)
2151 total = isl_basic_map_total_dim(bmap);
2152 isl_assert(bmap->ctx, pos < bmap->n_ineq, return -1);
2153 isl_seq_neg(bmap->ineq[pos], bmap->ineq[pos], 1 + total);
2154 isl_int_sub_ui(bmap->ineq[pos][0], bmap->ineq[pos][0], 1);
2155 F_CLR(bmap, ISL_BASIC_MAP_NORMALIZED);
2159 struct isl_set *isl_set_alloc_dim(struct isl_ctx *ctx,
2160 struct isl_dim *dim, int n, unsigned flags)
2162 struct isl_set *set;
2166 isl_assert(ctx, dim->n_in == 0, return NULL);
2167 isl_assert(ctx, n >= 0, return NULL);
2168 set = isl_alloc(ctx, struct isl_set,
2169 sizeof(struct isl_set) +
2170 n * sizeof(struct isl_basic_set *));
2187 struct isl_set *isl_set_alloc(struct isl_ctx *ctx,
2188 unsigned nparam, unsigned dim, int n, unsigned flags)
2190 struct isl_set *set;
2191 struct isl_dim *dims;
2193 dims = isl_dim_alloc(ctx, nparam, 0, dim);
2197 set = isl_set_alloc_dim(ctx, dims, n, flags);
2201 struct isl_set *isl_set_dup(struct isl_set *set)
2204 struct isl_set *dup;
2209 dup = isl_set_alloc_dim(set->ctx, isl_dim_copy(set->dim),
2210 set->n, set->flags);
2213 for (i = 0; i < set->n; ++i)
2214 dup = isl_set_add(dup, isl_basic_set_copy(set->p[i]));
2218 struct isl_set *isl_set_from_basic_set(struct isl_basic_set *bset)
2220 struct isl_set *set;
2225 set = isl_set_alloc_dim(bset->ctx, isl_dim_copy(bset->dim),
2226 1, ISL_MAP_DISJOINT);
2228 isl_basic_set_free(bset);
2231 return isl_set_add(set, bset);
2234 struct isl_map *isl_map_from_basic_map(struct isl_basic_map *bmap)
2236 struct isl_map *map;
2241 map = isl_map_alloc_dim(bmap->ctx, isl_dim_copy(bmap->dim),
2242 1, ISL_MAP_DISJOINT);
2244 isl_basic_map_free(bmap);
2247 return isl_map_add(map, bmap);
2250 struct isl_set *isl_set_add(struct isl_set *set, struct isl_basic_set *bset)
2254 isl_assert(set->ctx, isl_dim_equal(set->dim, bset->dim), goto error);
2255 isl_assert(set->ctx, set->n < set->size, goto error);
2256 set->p[set->n] = bset;
2263 isl_basic_set_free(bset);
2267 void isl_set_free(struct isl_set *set)
2277 isl_ctx_deref(set->ctx);
2278 for (i = 0; i < set->n; ++i)
2279 isl_basic_set_free(set->p[i]);
2280 isl_dim_free(set->dim);
2284 void isl_set_dump(struct isl_set *set, FILE *out, int indent)
2289 fprintf(out, "null set\n");
2293 fprintf(out, "%*s", indent, "");
2294 fprintf(out, "ref: %d, n: %d, nparam: %d, dim: %d, flags: %x\n",
2295 set->ref, set->n, set->dim->nparam, set->dim->n_out,
2297 for (i = 0; i < set->n; ++i) {
2298 fprintf(out, "%*s", indent, "");
2299 fprintf(out, "basic set %d:\n", i);
2300 isl_basic_set_dump(set->p[i], out, indent+4);
2304 void isl_map_dump(struct isl_map *map, FILE *out, int indent)
2309 fprintf(out, "null map\n");
2313 fprintf(out, "%*s", indent, "");
2314 fprintf(out, "ref: %d, n: %d, nparam: %d, in: %d, out: %d, flags: %x\n",
2315 map->ref, map->n, map->dim->nparam, map->dim->n_in,
2316 map->dim->n_out, map->flags);
2317 for (i = 0; i < map->n; ++i) {
2318 fprintf(out, "%*s", indent, "");
2319 fprintf(out, "basic map %d:\n", i);
2320 isl_basic_map_dump(map->p[i], out, indent+4);
2324 struct isl_basic_map *isl_basic_map_intersect_domain(
2325 struct isl_basic_map *bmap, struct isl_basic_set *bset)
2327 struct isl_basic_map *bmap_domain;
2328 struct isl_dim *dim;
2333 isl_assert(set->ctx, isl_basic_map_compatible_domain(bmap, bset),
2336 bmap = isl_basic_map_extend(bmap,
2337 isl_basic_map_n_param(bmap), isl_basic_map_n_in(bmap),
2338 isl_basic_map_n_out(bmap),
2339 bset->n_div, bset->n_eq, bset->n_ineq);
2342 dim = isl_dim_reverse(isl_dim_copy(bset->dim));
2343 bmap_domain = isl_basic_map_from_basic_set(bset, dim);
2344 bmap = add_constraints(bmap, bmap_domain, 0, 0);
2346 bmap = isl_basic_map_simplify(bmap);
2347 return isl_basic_map_finalize(bmap);
2349 isl_basic_map_free(bmap);
2350 isl_basic_set_free(bset);
2354 struct isl_basic_map *isl_basic_map_intersect_range(
2355 struct isl_basic_map *bmap, struct isl_basic_set *bset)
2357 struct isl_basic_map *bmap_range;
2362 isl_assert(bset->ctx, isl_basic_map_compatible_range(bmap, bset),
2365 bmap = isl_basic_map_extend(bmap,
2366 isl_basic_map_n_param(bmap), isl_basic_map_n_in(bmap),
2367 isl_basic_map_n_out(bmap),
2368 bset->n_div, bset->n_eq, bset->n_ineq);
2371 bmap_range = isl_basic_map_from_basic_set(bset, isl_dim_copy(bset->dim));
2372 bmap = add_constraints(bmap, bmap_range, 0, 0);
2374 bmap = isl_basic_map_simplify(bmap);
2375 return isl_basic_map_finalize(bmap);
2377 isl_basic_map_free(bmap);
2378 isl_basic_set_free(bset);
2382 struct isl_basic_map *isl_basic_map_intersect(
2383 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2385 if (!bmap1 || !bmap2)
2388 isl_assert(map1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim), goto error);
2390 bmap1 = isl_basic_map_extend(bmap1, isl_basic_map_n_param(bmap1),
2391 isl_basic_map_n_in(bmap1), isl_basic_map_n_out(bmap1),
2392 bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
2395 bmap1 = add_constraints(bmap1, bmap2, 0, 0);
2397 bmap1 = isl_basic_map_simplify(bmap1);
2398 return isl_basic_map_finalize(bmap1);
2400 isl_basic_map_free(bmap1);
2401 isl_basic_map_free(bmap2);
2405 struct isl_basic_set *isl_basic_set_intersect(
2406 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
2408 return (struct isl_basic_set *)
2409 isl_basic_map_intersect(
2410 (struct isl_basic_map *)bset1,
2411 (struct isl_basic_map *)bset2);
2414 struct isl_map *isl_map_intersect(struct isl_map *map1, struct isl_map *map2)
2417 struct isl_map *result;
2423 if (F_ISSET(map1, ISL_MAP_DISJOINT) &&
2424 F_ISSET(map2, ISL_MAP_DISJOINT))
2425 FL_SET(flags, ISL_MAP_DISJOINT);
2427 result = isl_map_alloc_dim(map1->ctx, isl_dim_copy(map1->dim),
2428 map1->n * map2->n, flags);
2431 for (i = 0; i < map1->n; ++i)
2432 for (j = 0; j < map2->n; ++j) {
2433 struct isl_basic_map *part;
2434 part = isl_basic_map_intersect(
2435 isl_basic_map_copy(map1->p[i]),
2436 isl_basic_map_copy(map2->p[j]));
2437 if (isl_basic_map_is_empty(part))
2438 isl_basic_map_free(part);
2440 result = isl_map_add(result, part);
2453 struct isl_set *isl_set_intersect(struct isl_set *set1, struct isl_set *set2)
2455 return (struct isl_set *)
2456 isl_map_intersect((struct isl_map *)set1,
2457 (struct isl_map *)set2);
2460 struct isl_basic_map *isl_basic_map_reverse(struct isl_basic_map *bmap)
2462 struct isl_dim *dim;
2463 struct isl_basic_set *bset;
2468 bmap = isl_basic_map_cow(bmap);
2471 dim = isl_dim_reverse(isl_dim_copy(bmap->dim));
2472 in = isl_basic_map_n_in(bmap);
2473 bset = isl_basic_set_from_basic_map(bmap);
2474 bset = isl_basic_set_swap_vars(bset, in);
2475 return isl_basic_map_from_basic_set(bset, dim);
2478 /* Turn final n dimensions into existentially quantified variables.
2480 struct isl_basic_set *isl_basic_set_project_out(
2481 struct isl_basic_set *bset, unsigned n, unsigned flags)
2491 isl_assert(bset->ctx, n <= isl_basic_set_n_dim(bset), goto error);
2496 bset = isl_basic_set_cow(bset);
2498 row_size = 1 + isl_dim_total(bset->dim) + bset->extra;
2499 old = bset->block2.data;
2500 bset->block2 = isl_blk_extend(bset->ctx, bset->block2,
2501 (bset->extra + n) * (1 + row_size));
2502 if (!bset->block2.data)
2504 new_div = isl_alloc_array(ctx, isl_int *, bset->extra + n);
2507 for (i = 0; i < n; ++i) {
2508 new_div[i] = bset->block2.data +
2509 (bset->extra + i) * (1 + row_size);
2510 isl_seq_clr(new_div[i], 1 + row_size);
2512 for (i = 0; i < bset->extra; ++i)
2513 new_div[n + i] = bset->block2.data + (bset->div[i] - old);
2515 bset->div = new_div;
2518 bset->dim = isl_dim_cow(bset->dim);
2521 bset->dim->n_out -= n;
2522 bset = isl_basic_set_simplify(bset);
2523 return isl_basic_set_finalize(bset);
2525 isl_basic_set_free(bset);
2529 struct isl_basic_map *add_divs(struct isl_basic_map *bmap, unsigned n)
2533 for (i = 0; i < n; ++i) {
2534 j = isl_basic_map_alloc_div(bmap);
2537 isl_seq_clr(bmap->div[j], 1+1+isl_basic_map_total_dim(bmap));
2541 isl_basic_map_free(bmap);
2545 struct isl_basic_map *isl_basic_map_apply_range(
2546 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2548 struct isl_dim *dim_result = NULL;
2549 struct isl_basic_map *bmap;
2550 unsigned n_in, n_out, n, nparam, total, pos;
2551 struct isl_dim_map *dim_map1, *dim_map2;
2553 if (!bmap1 || !bmap2)
2556 dim_result = isl_dim_join(isl_dim_copy(bmap1->dim),
2557 isl_dim_copy(bmap2->dim));
2559 n_in = isl_basic_map_n_in(bmap1);
2560 n_out = isl_basic_map_n_out(bmap2);
2561 n = isl_basic_map_n_out(bmap1);
2562 nparam = isl_basic_map_n_param(bmap1);
2564 total = nparam + n_in + n_out + bmap1->n_div + bmap2->n_div + n;
2565 dim_map1 = isl_dim_map_alloc(bmap1->ctx, total);
2566 dim_map2 = isl_dim_map_alloc(bmap1->ctx, total);
2567 isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_param, pos = 0);
2568 isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_param, pos = 0);
2569 isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_in, pos += nparam);
2570 isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_out, pos += n_in);
2571 isl_dim_map_div(dim_map1, bmap1, pos += n_out);
2572 isl_dim_map_div(dim_map2, bmap2, pos += bmap1->n_div);
2573 isl_dim_map_dim(dim_map1, bmap1->dim, isl_dim_out, pos += bmap2->n_div);
2574 isl_dim_map_dim(dim_map2, bmap2->dim, isl_dim_in, pos);
2576 bmap = isl_basic_map_alloc_dim(bmap1->ctx, dim_result,
2577 bmap1->n_div + bmap2->n_div + n,
2578 bmap1->n_eq + bmap2->n_eq,
2579 bmap1->n_ineq + bmap2->n_ineq);
2580 bmap = add_constraints_dim_map(bmap, bmap1, dim_map1);
2581 bmap = add_constraints_dim_map(bmap, bmap2, dim_map2);
2582 bmap = add_divs(bmap, n);
2583 bmap = isl_basic_map_simplify(bmap);
2584 return isl_basic_map_finalize(bmap);
2586 isl_basic_map_free(bmap1);
2587 isl_basic_map_free(bmap2);
2591 struct isl_basic_set *isl_basic_set_apply(
2592 struct isl_basic_set *bset, struct isl_basic_map *bmap)
2597 isl_assert(set->ctx, isl_basic_map_compatible_domain(bmap, bset),
2600 return (struct isl_basic_set *)
2601 isl_basic_map_apply_range((struct isl_basic_map *)bset, bmap);
2603 isl_basic_set_free(bset);
2604 isl_basic_map_free(bmap);
2608 struct isl_basic_map *isl_basic_map_apply_domain(
2609 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
2611 if (!bmap1 || !bmap2)
2615 isl_basic_map_n_in(bmap1) == isl_basic_map_n_in(bmap2), goto error);
2617 isl_basic_map_n_param(bmap1) == isl_basic_map_n_param(bmap2),
2620 bmap1 = isl_basic_map_reverse(bmap1);
2621 bmap1 = isl_basic_map_apply_range(bmap1, bmap2);
2622 return isl_basic_map_reverse(bmap1);
2624 isl_basic_map_free(bmap1);
2625 isl_basic_map_free(bmap2);
2629 static struct isl_basic_map *var_equal(struct isl_ctx *ctx,
2630 struct isl_basic_map *bmap, unsigned pos)
2636 i = isl_basic_map_alloc_equality(bmap);
2639 nparam = isl_basic_map_n_param(bmap);
2640 n_in = isl_basic_map_n_in(bmap);
2641 isl_seq_clr(bmap->eq[i], 1 + isl_basic_map_total_dim(bmap));
2642 isl_int_set_si(bmap->eq[i][1+nparam+pos], -1);
2643 isl_int_set_si(bmap->eq[i][1+nparam+n_in+pos], 1);
2644 return isl_basic_map_finalize(bmap);
2646 isl_basic_map_free(bmap);
2650 static struct isl_basic_map *var_more(struct isl_ctx *ctx,
2651 struct isl_basic_map *bmap, unsigned pos)
2657 i = isl_basic_map_alloc_inequality(bmap);
2660 nparam = isl_basic_map_n_param(bmap);
2661 n_in = isl_basic_map_n_in(bmap);
2662 isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2663 isl_int_set_si(bmap->ineq[i][0], -1);
2664 isl_int_set_si(bmap->ineq[i][1+nparam+pos], -1);
2665 isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], 1);
2666 return isl_basic_map_finalize(bmap);
2668 isl_basic_map_free(bmap);
2672 static struct isl_basic_map *var_less(struct isl_ctx *ctx,
2673 struct isl_basic_map *bmap, unsigned pos)
2679 i = isl_basic_map_alloc_inequality(bmap);
2682 nparam = isl_basic_map_n_param(bmap);
2683 n_in = isl_basic_map_n_in(bmap);
2684 isl_seq_clr(bmap->ineq[i], 1 + isl_basic_map_total_dim(bmap));
2685 isl_int_set_si(bmap->ineq[i][0], -1);
2686 isl_int_set_si(bmap->ineq[i][1+nparam+pos], 1);
2687 isl_int_set_si(bmap->ineq[i][1+nparam+n_in+pos], -1);
2688 return isl_basic_map_finalize(bmap);
2690 isl_basic_map_free(bmap);
2694 struct isl_basic_map *isl_basic_map_equal(struct isl_ctx *ctx,
2695 unsigned nparam, unsigned in, unsigned out, unsigned n_equal)
2698 struct isl_basic_map *bmap;
2699 bmap = isl_basic_map_alloc(ctx, nparam, in, out, 0, n_equal, 0);
2702 for (i = 0; i < n_equal && bmap; ++i)
2703 bmap = var_equal(ctx, bmap, i);
2704 return isl_basic_map_finalize(bmap);
2707 struct isl_basic_map *isl_basic_map_less_at(struct isl_ctx *ctx,
2708 unsigned nparam, unsigned in, unsigned out, unsigned pos)
2711 struct isl_basic_map *bmap;
2712 bmap = isl_basic_map_alloc(ctx, nparam, in, out, 0, pos, 1);
2715 for (i = 0; i < pos && bmap; ++i)
2716 bmap = var_equal(ctx, bmap, i);
2718 bmap = var_less(ctx, bmap, pos);
2719 return isl_basic_map_finalize(bmap);
2722 struct isl_basic_map *isl_basic_map_more_at(struct isl_ctx *ctx,
2723 unsigned nparam, unsigned in, unsigned out, unsigned pos)
2726 struct isl_basic_map *bmap;
2727 bmap = isl_basic_map_alloc(ctx, nparam, in, out, 0, pos, 1);
2730 for (i = 0; i < pos && bmap; ++i)
2731 bmap = var_equal(ctx, bmap, i);
2733 bmap = var_more(ctx, bmap, pos);
2734 return isl_basic_map_finalize(bmap);
2737 struct isl_basic_map *isl_basic_map_from_basic_set(
2738 struct isl_basic_set *bset, struct isl_dim *dim)
2740 struct isl_basic_map *bmap;
2742 bset = isl_basic_set_cow(bset);
2746 isl_assert(bset->ctx, isl_dim_compatible(bset->dim, dim), goto error);
2747 isl_dim_free(bset->dim);
2748 bmap = (struct isl_basic_map *) bset;
2750 return isl_basic_map_finalize(bmap);
2752 isl_basic_set_free(bset);
2757 struct isl_basic_set *isl_basic_set_from_basic_map(struct isl_basic_map *bmap)
2761 if (bmap->dim->n_in == 0)
2762 return (struct isl_basic_set *)bmap;
2763 bmap = isl_basic_map_cow(bmap);
2766 bmap->dim = isl_dim_cow(bmap->dim);
2769 bmap->dim->n_out += bmap->dim->n_in;
2770 bmap->dim->n_in = 0;
2771 bmap = isl_basic_map_finalize(bmap);
2772 return (struct isl_basic_set *)bmap;
2774 isl_basic_map_free(bmap);
2778 /* For a div d = floor(f/m), add the constraints
2781 * -(f-(n-1)) + m d >= 0
2783 * Note that the second constraint is the negation of
2787 static int add_div_constraints(struct isl_basic_map *bmap, unsigned div)
2790 unsigned total = isl_basic_map_total_dim(bmap);
2791 unsigned div_pos = 1 + total - bmap->n_div + div;
2793 i = isl_basic_map_alloc_inequality(bmap);
2796 isl_seq_cpy(bmap->ineq[i], bmap->div[div]+1, 1+total);
2797 isl_int_neg(bmap->ineq[i][div_pos], bmap->div[div][0]);
2799 j = isl_basic_map_alloc_inequality(bmap);
2802 isl_seq_neg(bmap->ineq[j], bmap->ineq[i], 1 + total);
2803 isl_int_add(bmap->ineq[j][0], bmap->ineq[j][0], bmap->ineq[j][div_pos]);
2804 isl_int_sub_ui(bmap->ineq[j][0], bmap->ineq[j][0], 1);
2808 struct isl_basic_set *isl_basic_map_underlying_set(
2809 struct isl_basic_map *bmap)
2813 if (bmap->dim->nparam == 0 && bmap->dim->n_in == 0 && bmap->n_div == 0)
2814 return (struct isl_basic_set *)bmap;
2815 bmap = isl_basic_map_cow(bmap);
2818 bmap->dim = isl_dim_cow(bmap->dim);
2821 bmap->dim->n_out += bmap->dim->nparam + bmap->dim->n_in + bmap->n_div;
2822 bmap->dim->nparam = 0;
2823 bmap->dim->n_in = 0;
2824 bmap->extra -= bmap->n_div;
2826 bmap = isl_basic_map_finalize(bmap);
2827 return (struct isl_basic_set *)bmap;
2832 struct isl_basic_map *isl_basic_map_overlying_set(
2833 struct isl_basic_set *bset, struct isl_basic_map *like)
2835 struct isl_basic_map *bmap;
2836 struct isl_ctx *ctx;
2843 isl_assert(ctx, bset->dim->n_out == isl_basic_map_total_dim(like),
2845 if (like->dim->nparam == 0 && like->dim->n_in == 0 && like->n_div == 0) {
2846 isl_basic_map_free(like);
2847 return (struct isl_basic_map *)bset;
2849 bset = isl_basic_set_cow(bset);
2852 total = bset->dim->n_out + bset->extra;
2853 bmap = (struct isl_basic_map *)bset;
2854 isl_dim_free(bmap->dim);
2855 bmap->dim = isl_dim_copy(like->dim);
2858 bmap->extra += like->n_div;
2861 ltotal = total - bmap->extra + like->extra;
2864 bmap->block2 = isl_blk_extend(ctx, bmap->block2,
2865 bmap->extra * (1 + 1 + total));
2866 if (isl_blk_is_error(bmap->block2))
2868 bmap->div = isl_realloc_array(ctx, bmap->div, isl_int *,
2872 bmap = isl_basic_map_extend_constraints(bmap,
2873 0, 2 * like->n_div);
2874 for (i = 0; i < like->n_div; ++i) {
2875 k = isl_basic_map_alloc_div(bmap);
2878 isl_seq_cpy(bmap->div[k], like->div[i], 1 + 1 + ltotal);
2879 isl_seq_clr(bmap->div[k]+1+1+ltotal, total - ltotal);
2880 if (add_div_constraints(bmap, k) < 0)
2884 isl_basic_map_free(like);
2885 bmap = isl_basic_map_finalize(bmap);
2888 isl_basic_map_free(like);
2889 isl_basic_set_free(bset);
2893 struct isl_basic_set *isl_basic_set_from_underlying_set(
2894 struct isl_basic_set *bset, struct isl_basic_set *like)
2896 return (struct isl_basic_set *)
2897 isl_basic_map_overlying_set(bset, (struct isl_basic_map *)like);
2900 struct isl_set *isl_set_from_underlying_set(
2901 struct isl_set *set, struct isl_basic_set *like)
2907 isl_assert(set->ctx, set->dim->n_out == isl_basic_set_total_dim(like),
2909 if (like->dim->nparam == 0 && like->n_div == 0) {
2910 isl_basic_set_free(like);
2913 set = isl_set_cow(set);
2916 for (i = 0; i < set->n; ++i) {
2917 set->p[i] = isl_basic_set_from_underlying_set(set->p[i],
2918 isl_basic_set_copy(like));
2922 isl_dim_free(set->dim);
2923 set->dim = isl_dim_copy(like->dim);
2926 isl_basic_set_free(like);
2929 isl_basic_set_free(like);
2934 struct isl_set *isl_map_underlying_set(struct isl_map *map)
2938 map = isl_map_align_divs(map);
2939 map = isl_map_cow(map);
2942 map->dim = isl_dim_cow(map->dim);
2946 for (i = 0; i < map->n; ++i) {
2947 map->p[i] = (struct isl_basic_map *)
2948 isl_basic_map_underlying_set(map->p[i]);
2953 map->dim->n_out += map->dim->nparam + map->dim->n_in;
2955 map->dim->n_out = map->p[0]->dim->n_out;
2956 map->dim->nparam = 0;
2958 return (struct isl_set *)map;
2964 struct isl_set *isl_set_to_underlying_set(struct isl_set *set)
2966 return (struct isl_set *)isl_map_underlying_set((struct isl_map *)set);
2969 struct isl_basic_set *isl_basic_map_domain(struct isl_basic_map *bmap)
2971 struct isl_basic_set *domain;
2975 n_out = isl_basic_map_n_out(bmap);
2976 domain = isl_basic_set_from_basic_map(bmap);
2977 return isl_basic_set_project_out(domain, n_out, 0);
2980 struct isl_basic_set *isl_basic_map_range(struct isl_basic_map *bmap)
2982 return isl_basic_map_domain(isl_basic_map_reverse(bmap));
2985 struct isl_set *isl_map_range(struct isl_map *map)
2988 struct isl_set *set;
2992 map = isl_map_cow(map);
2996 set = (struct isl_set *) map;
2997 if (set->dim->n_in != 0) {
2998 set->dim = isl_dim_cow(set->dim);
3003 for (i = 0; i < map->n; ++i) {
3004 set->p[i] = isl_basic_map_range(map->p[i]);
3008 F_CLR(set, ISL_MAP_DISJOINT);
3009 F_CLR(set, ISL_SET_NORMALIZED);
3016 struct isl_map *isl_map_from_set(struct isl_set *set, struct isl_dim *dim)
3019 struct isl_map *map = NULL;
3021 set = isl_set_cow(set);
3024 isl_assert(set->ctx, isl_dim_compatible(set->dim, dim), goto error);
3025 map = (struct isl_map *)set;
3026 for (i = 0; i < set->n; ++i) {
3027 map->p[i] = isl_basic_map_from_basic_set(
3028 set->p[i], isl_dim_copy(dim));
3032 isl_dim_free(map->dim);
3041 struct isl_set *isl_set_from_map(struct isl_map *map)
3044 struct isl_set *set = NULL;
3048 map = isl_map_cow(map);
3051 map->dim = isl_dim_cow(map->dim);
3054 map->dim->n_out += map->dim->n_in;
3056 set = (struct isl_set *)map;
3057 for (i = 0; i < map->n; ++i) {
3058 set->p[i] = isl_basic_set_from_basic_map(map->p[i]);
3068 struct isl_map *isl_map_alloc_dim(struct isl_ctx *ctx,
3069 struct isl_dim *dim, int n, unsigned flags)
3071 struct isl_map *map;
3075 isl_assert(ctx, n >= 0, return NULL);
3076 map = isl_alloc(ctx, struct isl_map,
3077 sizeof(struct isl_map) +
3078 n * sizeof(struct isl_basic_map *));
3095 struct isl_map *isl_map_alloc(struct isl_ctx *ctx,
3096 unsigned nparam, unsigned in, unsigned out, int n,
3099 struct isl_map *map;
3100 struct isl_dim *dims;
3102 dims = isl_dim_alloc(ctx, nparam, in, out);
3106 map = isl_map_alloc_dim(ctx, dims, n, flags);
3110 struct isl_basic_map *isl_basic_map_empty(struct isl_ctx *ctx,
3111 unsigned nparam, unsigned in, unsigned out)
3113 struct isl_basic_map *bmap;
3114 bmap = isl_basic_map_alloc(ctx, nparam, in, out, 0, 1, 0);
3115 bmap = isl_basic_map_set_to_empty(bmap);
3119 struct isl_basic_set *isl_basic_set_empty(struct isl_ctx *ctx,
3120 unsigned nparam, unsigned dim)
3122 struct isl_basic_set *bset;
3123 bset = isl_basic_set_alloc(ctx, nparam, dim, 0, 1, 0);
3124 bset = isl_basic_set_set_to_empty(bset);
3128 struct isl_basic_map *isl_basic_map_empty_like(struct isl_basic_map *model)
3130 struct isl_basic_map *bmap;
3133 bmap = isl_basic_map_alloc_dim(model->ctx, isl_dim_copy(model->dim),
3135 bmap = isl_basic_map_set_to_empty(bmap);
3139 struct isl_basic_map *isl_basic_map_empty_like_map(struct isl_map *model)
3141 struct isl_basic_map *bmap;
3144 bmap = isl_basic_map_alloc_dim(model->ctx, isl_dim_copy(model->dim),
3146 bmap = isl_basic_map_set_to_empty(bmap);
3150 struct isl_basic_set *isl_basic_set_empty_like(struct isl_basic_set *model)
3152 struct isl_basic_set *bset;
3155 bset = isl_basic_set_alloc_dim(model->ctx, isl_dim_copy(model->dim),
3157 bset = isl_basic_set_set_to_empty(bset);
3161 struct isl_basic_map *isl_basic_map_universe(struct isl_ctx *ctx,
3162 unsigned nparam, unsigned in, unsigned out)
3164 struct isl_basic_map *bmap;
3165 bmap = isl_basic_map_alloc(ctx, nparam, in, out, 0, 0, 0);
3169 struct isl_basic_set *isl_basic_set_universe(struct isl_ctx *ctx,
3170 unsigned nparam, unsigned dim)
3172 struct isl_basic_set *bset;
3173 bset = isl_basic_set_alloc(ctx, nparam, dim, 0, 0, 0);
3177 struct isl_basic_set *isl_basic_set_universe_like(struct isl_basic_set *model)
3181 return isl_basic_set_alloc_dim(model->ctx, isl_dim_copy(model->dim),
3185 struct isl_map *isl_map_empty(struct isl_ctx *ctx,
3186 unsigned nparam, unsigned in, unsigned out)
3188 return isl_map_alloc(ctx, nparam, in, out, 0, ISL_MAP_DISJOINT);
3191 struct isl_map *isl_map_empty_like_basic_map(struct isl_basic_map *model)
3195 return isl_map_alloc_dim(model->ctx, isl_dim_copy(model->dim),
3196 0, ISL_MAP_DISJOINT);
3199 struct isl_set *isl_set_empty(struct isl_ctx *ctx,
3200 unsigned nparam, unsigned dim)
3202 return isl_set_alloc(ctx, nparam, dim, 0, ISL_MAP_DISJOINT);
3205 struct isl_set *isl_set_empty_like(struct isl_set *model)
3209 return isl_set_alloc_dim(model->ctx, model->dim, 0, ISL_MAP_DISJOINT);
3212 struct isl_map *isl_map_dup(struct isl_map *map)
3215 struct isl_map *dup;
3219 dup = isl_map_alloc_dim(map->ctx, isl_dim_copy(map->dim),
3220 map->n, map->flags);
3221 for (i = 0; i < map->n; ++i)
3222 dup = isl_map_add(dup, isl_basic_map_copy(map->p[i]));
3226 struct isl_map *isl_map_add(struct isl_map *map, struct isl_basic_map *bmap)
3230 isl_assert(map->ctx, isl_dim_equal(map->dim, bmap->dim), goto error);
3231 isl_assert(map->ctx, map->n < map->size, goto error);
3232 map->p[map->n] = bmap;
3234 F_CLR(map, ISL_MAP_NORMALIZED);
3240 isl_basic_map_free(bmap);
3244 void isl_map_free(struct isl_map *map)
3254 isl_ctx_deref(map->ctx);
3255 for (i = 0; i < map->n; ++i)
3256 isl_basic_map_free(map->p[i]);
3257 isl_dim_free(map->dim);
3261 struct isl_map *isl_map_extend(struct isl_map *base,
3262 unsigned nparam, unsigned n_in, unsigned n_out)
3266 base = isl_map_cow(base);
3270 isl_assert(base->ctx, base->dim->nparam <= nparam, goto error);
3271 isl_assert(base->ctx, base->dim->n_in <= n_in, goto error);
3272 isl_assert(base->ctx, base->dim->n_out <= n_out, goto error);
3273 base->dim = isl_dim_cow(base->dim);
3276 base->dim->nparam = nparam;
3277 base->dim->n_in = n_in;
3278 base->dim->n_out = n_out;
3279 for (i = 0; i < base->n; ++i) {
3280 base->p[i] = isl_basic_map_extend(base->p[i],
3281 nparam, n_in, n_out, 0, 0, 0);
3291 struct isl_set *isl_set_extend(struct isl_set *base,
3292 unsigned nparam, unsigned dim)
3294 return (struct isl_set *)isl_map_extend((struct isl_map *)base,
3298 static struct isl_basic_map *isl_basic_map_fix_var(struct isl_basic_map *bmap,
3299 unsigned var, int value)
3303 bmap = isl_basic_map_cow(bmap);
3304 bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
3305 j = isl_basic_map_alloc_equality(bmap);
3308 isl_seq_clr(bmap->eq[j], 1 + isl_basic_map_total_dim(bmap));
3309 isl_int_set_si(bmap->eq[j][1 + var], -1);
3310 isl_int_set_si(bmap->eq[j][0], value);
3311 bmap = isl_basic_map_simplify(bmap);
3312 return isl_basic_map_finalize(bmap);
3314 isl_basic_map_free(bmap);
3318 struct isl_basic_map *isl_basic_map_fix_input_si(struct isl_basic_map *bmap,
3319 unsigned input, int value)
3323 isl_assert(bmap->ctx, input < isl_basic_map_n_in(bmap), goto error);
3324 return isl_basic_map_fix_var(bmap, isl_basic_map_n_param(bmap) + input,
3327 isl_basic_map_free(bmap);
3331 struct isl_basic_set *isl_basic_set_fix_dim_si(struct isl_basic_set *bset,
3332 unsigned dim, int value)
3336 isl_assert(bset->ctx, dim < isl_basic_set_n_dim(bset), goto error);
3337 return (struct isl_basic_set *)
3338 isl_basic_map_fix_var((struct isl_basic_map *)bset,
3339 isl_basic_set_n_param(bset) + dim, value);
3341 isl_basic_set_free(bset);
3345 struct isl_map *isl_map_fix_input_si(struct isl_map *map,
3346 unsigned input, int value)
3350 map = isl_map_cow(map);
3354 isl_assert(ctx, input < isl_map_n_in(map), goto error);
3355 for (i = 0; i < map->n; ++i) {
3356 map->p[i] = isl_basic_map_fix_input_si(map->p[i], input, value);
3360 F_CLR(map, ISL_MAP_NORMALIZED);
3367 struct isl_set *isl_set_fix_dim_si(struct isl_set *set, unsigned dim, int value)
3371 set = isl_set_cow(set);
3375 isl_assert(set->ctx, dim < isl_set_n_dim(set), goto error);
3376 for (i = 0; i < set->n; ++i) {
3377 set->p[i] = isl_basic_set_fix_dim_si(set->p[i], dim, value);
3387 struct isl_basic_set *isl_basic_set_lower_bound_dim(struct isl_basic_set *bset,
3388 unsigned dim, isl_int value)
3393 bset = isl_basic_set_cow(bset);
3394 bset = isl_basic_set_extend_constraints(bset, 0, 1);
3395 j = isl_basic_set_alloc_inequality(bset);
3398 isl_seq_clr(bset->ineq[j], 1 + isl_basic_set_total_dim(bset));
3399 isl_int_set_si(bset->ineq[j][1 + isl_basic_set_n_param(bset) + dim], 1);
3400 isl_int_neg(bset->ineq[j][0], value);
3401 bset = isl_basic_set_simplify(bset);
3402 return isl_basic_set_finalize(bset);
3404 isl_basic_set_free(bset);
3408 struct isl_set *isl_set_lower_bound_dim(struct isl_set *set, unsigned dim,
3413 set = isl_set_cow(set);
3417 isl_assert(set->ctx, dim < isl_set_n_dim(set), goto error);
3418 for (i = 0; i < set->n; ++i) {
3419 set->p[i] = isl_basic_set_lower_bound_dim(set->p[i], dim, value);
3429 struct isl_map *isl_map_reverse(struct isl_map *map)
3434 map = isl_map_cow(map);
3438 map->dim = isl_dim_reverse(map->dim);
3441 for (i = 0; i < map->n; ++i) {
3442 map->p[i] = isl_basic_map_reverse(map->p[i]);
3446 F_CLR(map, ISL_MAP_NORMALIZED);
3453 struct isl_map *isl_basic_map_lexmax(
3454 struct isl_basic_map *bmap, struct isl_basic_set *dom,
3455 struct isl_set **empty)
3457 return isl_pip_basic_map_lexmax(bmap, dom, empty);
3460 struct isl_map *isl_basic_map_lexmin(
3461 struct isl_basic_map *bmap, struct isl_basic_set *dom,
3462 struct isl_set **empty)
3464 return isl_pip_basic_map_lexmin(bmap, dom, empty);
3467 struct isl_set *isl_basic_set_lexmin(struct isl_basic_set *bset)
3469 struct isl_basic_map *bmap = NULL;
3470 struct isl_basic_set *dom = NULL;
3471 struct isl_map *min;
3475 bmap = isl_basic_map_from_basic_set(bset, isl_dim_copy(bset->dim));
3478 dom = isl_basic_set_universe(bmap->ctx, isl_basic_map_n_param(bmap), 0);
3481 min = isl_basic_map_lexmin(bmap, dom, NULL);
3482 return isl_map_range(min);
3484 isl_basic_map_free(bmap);
3488 struct isl_map *isl_basic_map_compute_divs(struct isl_basic_map *bmap)
3492 if (bmap->n_div == 0)
3493 return isl_map_from_basic_map(bmap);
3494 return isl_pip_basic_map_compute_divs(bmap);
3497 struct isl_map *isl_map_compute_divs(struct isl_map *map)
3500 struct isl_map *res;
3506 res = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[0]));
3507 for (i = 1 ; i < map->n; ++i) {
3509 r2 = isl_basic_map_compute_divs(isl_basic_map_copy(map->p[i]));
3510 if (F_ISSET(map, ISL_MAP_DISJOINT))
3511 res = isl_map_union_disjoint(res, r2);
3513 res = isl_map_union(res, r2);
3520 struct isl_set *isl_basic_set_compute_divs(struct isl_basic_set *bset)
3522 return (struct isl_set *)
3523 isl_basic_map_compute_divs((struct isl_basic_map *)bset);
3526 struct isl_set *isl_set_compute_divs(struct isl_set *set)
3528 return (struct isl_set *)
3529 isl_map_compute_divs((struct isl_map *)set);
3532 struct isl_set *isl_map_domain(struct isl_map *map)
3535 struct isl_set *set;
3540 map = isl_map_cow(map);
3544 set = (struct isl_set *)map;
3545 set->dim = isl_dim_cow(set->dim);
3548 set->dim->n_out = map->dim->n_in;
3550 for (i = 0; i < map->n; ++i) {
3551 set->p[i] = isl_basic_map_domain(map->p[i]);
3555 F_CLR(set, ISL_MAP_DISJOINT);
3556 F_CLR(set, ISL_SET_NORMALIZED);
3563 struct isl_map *isl_map_union_disjoint(
3564 struct isl_map *map1, struct isl_map *map2)
3568 struct isl_map *map = NULL;
3582 isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
3584 if (F_ISSET(map1, ISL_MAP_DISJOINT) &&
3585 F_ISSET(map2, ISL_MAP_DISJOINT))
3586 FL_SET(flags, ISL_MAP_DISJOINT);
3588 map = isl_map_alloc_dim(map1->ctx, isl_dim_copy(map1->dim),
3589 map1->n + map2->n, flags);
3592 for (i = 0; i < map1->n; ++i) {
3593 map = isl_map_add(map,
3594 isl_basic_map_copy(map1->p[i]));
3598 for (i = 0; i < map2->n; ++i) {
3599 map = isl_map_add(map,
3600 isl_basic_map_copy(map2->p[i]));
3614 struct isl_map *isl_map_union(struct isl_map *map1, struct isl_map *map2)
3616 map1 = isl_map_union_disjoint(map1, map2);
3620 F_CLR(map1, ISL_MAP_DISJOINT);
3624 struct isl_set *isl_set_union_disjoint(
3625 struct isl_set *set1, struct isl_set *set2)
3627 return (struct isl_set *)
3628 isl_map_union_disjoint(
3629 (struct isl_map *)set1, (struct isl_map *)set2);
3632 struct isl_set *isl_set_union(struct isl_set *set1, struct isl_set *set2)
3634 return (struct isl_set *)
3635 isl_map_union((struct isl_map *)set1, (struct isl_map *)set2);
3638 struct isl_map *isl_map_intersect_range(
3639 struct isl_map *map, struct isl_set *set)
3642 struct isl_map *result;
3648 if (F_ISSET(map, ISL_MAP_DISJOINT) &&
3649 F_ISSET(set, ISL_MAP_DISJOINT))
3650 FL_SET(flags, ISL_MAP_DISJOINT);
3652 result = isl_map_alloc_dim(map->ctx, isl_dim_copy(map->dim),
3653 map->n * set->n, flags);
3656 for (i = 0; i < map->n; ++i)
3657 for (j = 0; j < set->n; ++j) {
3658 result = isl_map_add(result,
3659 isl_basic_map_intersect_range(
3660 isl_basic_map_copy(map->p[i]),
3661 isl_basic_set_copy(set->p[j])));
3674 struct isl_map *isl_map_intersect_domain(
3675 struct isl_map *map, struct isl_set *set)
3677 return isl_map_reverse(
3678 isl_map_intersect_range(isl_map_reverse(map), set));
3681 struct isl_map *isl_map_apply_domain(
3682 struct isl_map *map1, struct isl_map *map2)
3686 map1 = isl_map_reverse(map1);
3687 map1 = isl_map_apply_range(map1, map2);
3688 return isl_map_reverse(map1);
3695 struct isl_map *isl_map_apply_range(
3696 struct isl_map *map1, struct isl_map *map2)
3698 struct isl_dim *dim_result;
3699 struct isl_map *result;
3708 dim_result = isl_dim_join(isl_dim_copy(map1->dim),
3709 isl_dim_copy(map2->dim));
3711 result = isl_map_alloc_dim(map1->ctx, dim_result, map1->n * map2->n, 0);
3714 for (i = 0; i < map1->n; ++i)
3715 for (j = 0; j < map2->n; ++j) {
3716 result = isl_map_add(result,
3717 isl_basic_map_apply_range(
3718 isl_basic_map_copy(map1->p[i]),
3719 isl_basic_map_copy(map2->p[j])));
3725 if (result && result->n <= 1)
3726 F_SET(result, ISL_MAP_DISJOINT);
3735 * returns range - domain
3737 struct isl_basic_set *isl_basic_map_deltas(struct isl_basic_map *bmap)
3739 struct isl_basic_set *bset;
3746 dim = isl_basic_map_n_in(bmap);
3747 nparam = isl_basic_map_n_param(bmap);
3748 isl_assert(bmap->ctx, dim == isl_basic_map_n_out(bmap), goto error);
3749 bset = isl_basic_set_from_basic_map(bmap);
3750 bset = isl_basic_set_extend(bset, nparam, 3*dim, 0, dim, 0);
3751 bset = isl_basic_set_swap_vars(bset, 2*dim);
3752 for (i = 0; i < dim; ++i) {
3753 int j = isl_basic_map_alloc_equality(
3754 (struct isl_basic_map *)bset);
3757 isl_seq_clr(bset->eq[j], 1 + isl_basic_set_total_dim(bset));
3758 isl_int_set_si(bset->eq[j][1+nparam+i], 1);
3759 isl_int_set_si(bset->eq[j][1+nparam+dim+i], 1);
3760 isl_int_set_si(bset->eq[j][1+nparam+2*dim+i], -1);
3762 return isl_basic_set_project_out(bset, 2*dim, 0);
3764 isl_basic_map_free(bmap);
3769 * returns range - domain
3771 struct isl_set *isl_map_deltas(struct isl_map *map)
3774 struct isl_set *result;
3779 isl_assert(map->ctx, isl_map_n_in(map) == isl_map_n_out(map), goto error);
3780 result = isl_set_alloc(map->ctx, isl_map_n_param(map),
3781 isl_map_n_in(map), map->n, map->flags);
3784 for (i = 0; i < map->n; ++i)
3785 result = isl_set_add(result,
3786 isl_basic_map_deltas(isl_basic_map_copy(map->p[i])));
3794 /* If the only constraints a div d=floor(f/m)
3795 * appears in are its two defining constraints
3798 * -(f - (m - 1)) + m d >= 0
3800 * then it can safely be removed.
3802 static int div_is_redundant(struct isl_basic_map *bmap, int div)
3805 unsigned pos = 1 + isl_dim_total(bmap->dim) + div;
3807 for (i = 0; i < bmap->n_eq; ++i)
3808 if (!isl_int_is_zero(bmap->eq[i][pos]))
3811 for (i = 0; i < bmap->n_ineq; ++i) {
3812 if (isl_int_is_zero(bmap->ineq[i][pos]))
3814 if (isl_int_eq(bmap->ineq[i][pos], bmap->div[div][0])) {
3816 isl_int_sub(bmap->div[div][1],
3817 bmap->div[div][1], bmap->div[div][0]);
3818 isl_int_add_ui(bmap->div[div][1], bmap->div[div][1], 1);
3819 neg = isl_seq_is_neg(bmap->ineq[i], bmap->div[div]+1, pos);
3820 isl_int_sub_ui(bmap->div[div][1], bmap->div[div][1], 1);
3821 isl_int_add(bmap->div[div][1],
3822 bmap->div[div][1], bmap->div[div][0]);
3825 if (isl_seq_first_non_zero(bmap->ineq[i]+pos+1,
3826 bmap->n_div-div-1) != -1)
3828 } else if (isl_int_abs_eq(bmap->ineq[i][pos], bmap->div[div][0])) {
3829 if (!isl_seq_eq(bmap->ineq[i], bmap->div[div]+1, pos))
3831 if (isl_seq_first_non_zero(bmap->ineq[i]+pos+1,
3832 bmap->n_div-div-1) != -1)
3838 for (i = 0; i < bmap->n_div; ++i)
3839 if (!isl_int_is_zero(bmap->div[i][1+pos]))
3846 * Remove divs that don't occur in any of the constraints or other divs.
3847 * These can arise when dropping some of the variables in a quast
3848 * returned by piplib.
3850 static struct isl_basic_map *remove_redundant_divs(struct isl_basic_map *bmap)
3857 for (i = bmap->n_div-1; i >= 0; --i) {
3858 if (!div_is_redundant(bmap, i))
3860 bmap = isl_basic_map_drop_div(bmap, i);
3865 struct isl_basic_map *isl_basic_map_finalize(struct isl_basic_map *bmap)
3867 bmap = remove_redundant_divs(bmap);
3870 F_SET(bmap, ISL_BASIC_SET_FINAL);
3874 struct isl_basic_set *isl_basic_set_finalize(struct isl_basic_set *bset)
3876 return (struct isl_basic_set *)
3877 isl_basic_map_finalize((struct isl_basic_map *)bset);
3880 struct isl_set *isl_set_finalize(struct isl_set *set)
3886 for (i = 0; i < set->n; ++i) {
3887 set->p[i] = isl_basic_set_finalize(set->p[i]);
3897 struct isl_map *isl_map_finalize(struct isl_map *map)
3903 for (i = 0; i < map->n; ++i) {
3904 map->p[i] = isl_basic_map_finalize(map->p[i]);
3908 F_CLR(map, ISL_MAP_NORMALIZED);
3915 struct isl_basic_map *isl_basic_map_identity(struct isl_ctx *ctx,
3916 unsigned nparam, unsigned dim)
3918 struct isl_basic_map *bmap;
3921 bmap = isl_basic_map_alloc(ctx, nparam, dim, dim, 0, dim, 0);
3925 for (i = 0; i < dim; ++i) {
3926 int j = isl_basic_map_alloc_equality(bmap);
3929 isl_seq_clr(bmap->eq[j], 1 + isl_basic_map_total_dim(bmap));
3930 isl_int_set_si(bmap->eq[j][1+nparam+i], 1);
3931 isl_int_set_si(bmap->eq[j][1+nparam+dim+i], -1);
3933 return isl_basic_map_finalize(bmap);
3935 isl_basic_map_free(bmap);
3939 struct isl_map *isl_map_identity(struct isl_ctx *ctx,
3940 unsigned nparam, unsigned dim)
3942 struct isl_map *map = isl_map_alloc(ctx, nparam, dim, dim, 1,
3946 map = isl_map_add(map,
3947 isl_basic_map_identity(ctx, nparam, dim));
3954 int isl_set_is_equal(struct isl_set *set1, struct isl_set *set2)
3956 return isl_map_is_equal((struct isl_map *)set1, (struct isl_map *)set2);
3959 int isl_set_is_subset(struct isl_set *set1, struct isl_set *set2)
3961 return isl_map_is_subset(
3962 (struct isl_map *)set1, (struct isl_map *)set2);
3965 int isl_basic_map_is_subset(
3966 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
3969 struct isl_map *map1;
3970 struct isl_map *map2;
3972 if (!bmap1 || !bmap2)
3975 map1 = isl_map_from_basic_map(isl_basic_map_copy(bmap1));
3976 map2 = isl_map_from_basic_map(isl_basic_map_copy(bmap2));
3978 is_subset = isl_map_is_subset(map1, map2);
3986 int isl_basic_map_is_equal(
3987 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
3991 if (!bmap1 || !bmap2)
3993 is_subset = isl_basic_map_is_subset(bmap1, bmap2);
3996 is_subset = isl_basic_map_is_subset(bmap2, bmap1);
4000 int isl_basic_set_is_equal(
4001 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
4003 return isl_basic_map_is_equal(
4004 (struct isl_basic_map *)bset1, (struct isl_basic_map *)bset2);
4007 int isl_map_is_empty(struct isl_map *map)
4014 for (i = 0; i < map->n; ++i) {
4015 is_empty = isl_basic_map_is_empty(map->p[i]);
4024 int isl_set_is_empty(struct isl_set *set)
4026 return isl_map_is_empty((struct isl_map *)set);
4029 int isl_map_is_subset(struct isl_map *map1, struct isl_map *map2)
4033 struct isl_map *diff;
4038 if (isl_map_is_empty(map1))
4041 if (isl_map_is_empty(map2))
4044 diff = isl_map_subtract(isl_map_copy(map1), isl_map_copy(map2));
4048 is_subset = isl_map_is_empty(diff);
4054 int isl_map_is_equal(struct isl_map *map1, struct isl_map *map2)
4060 is_subset = isl_map_is_subset(map1, map2);
4063 is_subset = isl_map_is_subset(map2, map1);
4067 int isl_basic_map_is_strict_subset(
4068 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4072 if (!bmap1 || !bmap2)
4074 is_subset = isl_basic_map_is_subset(bmap1, bmap2);
4077 is_subset = isl_basic_map_is_subset(bmap2, bmap1);
4078 if (is_subset == -1)
4083 static int basic_map_contains(struct isl_basic_map *bmap, struct isl_vec *vec)
4089 total = 1 + isl_basic_map_total_dim(bmap);
4090 if (total != vec->size)
4095 for (i = 0; i < bmap->n_eq; ++i) {
4096 isl_seq_inner_product(vec->block.data, bmap->eq[i], total, &s);
4097 if (!isl_int_is_zero(s)) {
4103 for (i = 0; i < bmap->n_ineq; ++i) {
4104 isl_seq_inner_product(vec->block.data, bmap->ineq[i], total, &s);
4105 if (isl_int_is_neg(s)) {
4116 int isl_basic_map_is_universe(struct isl_basic_map *bmap)
4120 return bmap->n_eq == 0 && bmap->n_ineq == 0;
4123 int isl_basic_map_is_empty(struct isl_basic_map *bmap)
4125 struct isl_basic_set *bset = NULL;
4126 struct isl_vec *sample = NULL;
4133 if (F_ISSET(bmap, ISL_BASIC_MAP_EMPTY))
4136 if (F_ISSET(bmap, ISL_BASIC_MAP_RATIONAL)) {
4137 struct isl_basic_map *copy = isl_basic_map_copy(bmap);
4138 copy = isl_basic_map_convex_hull(copy);
4139 empty = F_ISSET(copy, ISL_BASIC_MAP_EMPTY);
4140 isl_basic_map_free(copy);
4144 total = 1 + isl_basic_map_total_dim(bmap);
4145 if (bmap->sample && bmap->sample->size == total) {
4146 int contains = basic_map_contains(bmap, bmap->sample);
4152 bset = isl_basic_map_underlying_set(isl_basic_map_copy(bmap));
4155 sample = isl_basic_set_sample(bset);
4158 empty = sample->size == 0;
4160 isl_vec_free(bmap->ctx, bmap->sample);
4161 bmap->sample = sample;
4166 struct isl_map *isl_basic_map_union(
4167 struct isl_basic_map *bmap1, struct isl_basic_map *bmap2)
4169 struct isl_map *map;
4170 if (!bmap1 || !bmap2)
4173 isl_assert(map1->ctx, isl_dim_equal(bmap1->dim, bmap2->dim), goto error);
4175 map = isl_map_alloc_dim(bmap1->ctx, isl_dim_copy(bmap1->dim), 2, 0);
4178 map = isl_map_add(map, bmap1);
4179 map = isl_map_add(map, bmap2);
4182 isl_basic_map_free(bmap1);
4183 isl_basic_map_free(bmap2);
4187 struct isl_set *isl_basic_set_union(
4188 struct isl_basic_set *bset1, struct isl_basic_set *bset2)
4190 return (struct isl_set *)isl_basic_map_union(
4191 (struct isl_basic_map *)bset1,
4192 (struct isl_basic_map *)bset2);
4195 /* Order divs such that any div only depends on previous divs */
4196 static struct isl_basic_map *order_divs(struct isl_basic_map *bmap)
4199 unsigned off = isl_dim_total(bmap->dim);
4201 for (i = 0; i < bmap->n_div; ++i) {
4203 pos = isl_seq_first_non_zero(bmap->div[i]+1+1+off+i,
4207 swap_div(bmap, i, pos);
4213 static int find_div(struct isl_basic_map *dst,
4214 struct isl_basic_map *src, unsigned div)
4218 unsigned total = isl_basic_map_total_dim(src);
4220 for (i = 0; i < dst->n_div; ++i)
4221 if (isl_seq_eq(dst->div[i], src->div[div], 1+1+total) &&
4222 isl_seq_first_non_zero(dst->div[i]+1+1+total,
4223 dst->n_div - src->n_div) == -1)
4228 struct isl_basic_map *isl_basic_map_align_divs(
4229 struct isl_basic_map *dst, struct isl_basic_map *src)
4232 unsigned total = isl_basic_map_total_dim(src);
4237 if (src->n_div == 0)
4240 src = order_divs(src);
4241 dst = isl_basic_map_extend(dst, isl_basic_map_n_param(dst),
4242 isl_basic_map_n_in(dst), isl_basic_map_n_out(dst),
4243 src->n_div, 0, 2 * src->n_div);
4246 for (i = 0; i < src->n_div; ++i) {
4247 int j = find_div(dst, src, i);
4249 j = isl_basic_map_alloc_div(dst);
4252 isl_seq_cpy(dst->div[j], src->div[i], 1+1+total);
4253 isl_seq_clr(dst->div[j]+1+1+total,
4254 dst->n_div - src->n_div);
4255 if (add_div_constraints(dst, j) < 0)
4259 swap_div(dst, i, j);
4263 isl_basic_map_free(dst);
4267 struct isl_basic_set *isl_basic_set_align_divs(
4268 struct isl_basic_set *dst, struct isl_basic_set *src)
4270 return (struct isl_basic_set *)isl_basic_map_align_divs(
4271 (struct isl_basic_map *)dst, (struct isl_basic_map *)src);
4274 struct isl_map *isl_map_align_divs(struct isl_map *map)
4278 map = isl_map_compute_divs(map);
4279 map = isl_map_cow(map);
4283 for (i = 1; i < map->n; ++i)
4284 map->p[0] = isl_basic_map_align_divs(map->p[0], map->p[i]);
4285 for (i = 1; i < map->n; ++i)
4286 map->p[i] = isl_basic_map_align_divs(map->p[i], map->p[0]);
4288 F_CLR(map, ISL_MAP_NORMALIZED);
4292 static struct isl_map *add_cut_constraint(struct isl_map *dst,
4293 struct isl_basic_map *src, isl_int *c,
4294 unsigned len, int oppose)
4296 struct isl_basic_map *copy = NULL;
4301 copy = isl_basic_map_copy(src);
4302 copy = isl_basic_map_cow(copy);
4305 copy = isl_basic_map_extend_constraints(copy, 0, 1);
4306 k = isl_basic_map_alloc_inequality(copy);
4310 isl_seq_neg(copy->ineq[k], c, len);
4312 isl_seq_cpy(copy->ineq[k], c, len);
4313 total = 1 + isl_basic_map_total_dim(copy);
4314 isl_seq_clr(copy->ineq[k]+len, total - len);
4315 isl_inequality_negate(copy, k);
4316 copy = isl_basic_map_simplify(copy);
4317 copy = isl_basic_map_finalize(copy);
4318 is_empty = isl_basic_map_is_empty(copy);
4322 dst = isl_map_add(dst, copy);
4324 isl_basic_map_free(copy);
4327 isl_basic_map_free(copy);
4332 static struct isl_map *subtract(struct isl_map *map, struct isl_basic_map *bmap)
4336 struct isl_map *rest = NULL;
4338 unsigned total = isl_basic_map_total_dim(bmap);
4345 if (F_ISSET(map, ISL_MAP_DISJOINT))
4346 FL_SET(flags, ISL_MAP_DISJOINT);
4348 max = map->n * (2 * bmap->n_eq + bmap->n_ineq);
4349 rest = isl_map_alloc_dim(map->ctx, isl_dim_copy(map->dim), max, flags);
4353 for (i = 0; i < map->n; ++i) {
4354 map->p[i] = isl_basic_map_align_divs(map->p[i], bmap);
4359 for (j = 0; j < map->n; ++j)
4360 map->p[j] = isl_basic_map_cow(map->p[j]);
4362 for (i = 0; i < bmap->n_eq; ++i) {
4363 for (j = 0; j < map->n; ++j) {
4364 rest = add_cut_constraint(rest,
4365 map->p[j], bmap->eq[i], 1+total, 0);
4369 rest = add_cut_constraint(rest,
4370 map->p[j], bmap->eq[i], 1+total, 1);
4374 map->p[j] = isl_basic_map_extend_constraints(map->p[j],
4378 k = isl_basic_map_alloc_equality(map->p[j]);
4381 isl_seq_cpy(map->p[j]->eq[k], bmap->eq[i], 1+total);
4382 isl_seq_clr(map->p[j]->eq[k]+1+total,
4383 map->p[j]->n_div - bmap->n_div);
4387 for (i = 0; i < bmap->n_ineq; ++i) {
4388 for (j = 0; j < map->n; ++j) {
4389 rest = add_cut_constraint(rest,
4390 map->p[j], bmap->ineq[i], 1+total, 0);
4394 map->p[j] = isl_basic_map_extend_constraints(map->p[j],
4398 k = isl_basic_map_alloc_inequality(map->p[j]);
4401 isl_seq_cpy(map->p[j]->ineq[k], bmap->ineq[i], 1+total);
4402 isl_seq_clr(map->p[j]->ineq[k]+1+total,
4403 map->p[j]->n_div - bmap->n_div);
4415 struct isl_map *isl_map_subtract(struct isl_map *map1, struct isl_map *map2)
4421 isl_assert(map1->ctx, isl_dim_equal(map1->dim, map2->dim), goto error);
4423 if (isl_map_is_empty(map2)) {
4428 map1 = isl_map_compute_divs(map1);
4429 map2 = isl_map_compute_divs(map2);
4433 for (i = 0; map1 && i < map2->n; ++i)
4434 map1 = subtract(map1, map2->p[i]);
4444 struct isl_set *isl_set_subtract(struct isl_set *set1, struct isl_set *set2)
4446 return (struct isl_set *)
4448 (struct isl_map *)set1, (struct isl_map *)set2);
4451 struct isl_set *isl_set_apply(struct isl_set *set, struct isl_map *map)
4455 isl_assert(set->ctx, isl_map_compatible_domain(map, set), goto error);
4456 map = isl_map_intersect_domain(map, set);
4457 set = isl_map_range(map);
4465 /* There is no need to cow as removing empty parts doesn't change
4466 * the meaning of the set.
4468 struct isl_map *isl_map_remove_empty_parts(struct isl_map *map)
4475 for (i = map->n-1; i >= 0; --i) {
4476 if (!F_ISSET(map->p[i], ISL_BASIC_MAP_EMPTY))
4478 isl_basic_map_free(map->p[i]);
4479 if (i != map->n-1) {
4480 F_CLR(map, ISL_MAP_NORMALIZED);
4481 map->p[i] = map->p[map->n-1];
4489 struct isl_set *isl_set_remove_empty_parts(struct isl_set *set)
4491 return (struct isl_set *)
4492 isl_map_remove_empty_parts((struct isl_map *)set);
4495 struct isl_basic_set *isl_set_copy_basic_set(struct isl_set *set)
4497 struct isl_basic_set *bset;
4498 if (!set || set->n == 0)
4500 bset = set->p[set->n-1];
4501 isl_assert(set->ctx, F_ISSET(bset, ISL_BASIC_SET_FINAL), return NULL);
4502 return isl_basic_set_copy(bset);
4505 struct isl_set *isl_set_drop_basic_set(struct isl_set *set,
4506 struct isl_basic_set *bset)
4512 for (i = set->n-1; i >= 0; --i) {
4513 if (set->p[i] != bset)
4515 set = isl_set_cow(set);
4518 isl_basic_set_free(set->p[i]);
4519 if (i != set->n-1) {
4520 F_CLR(set, ISL_SET_NORMALIZED);
4521 set->p[i] = set->p[set->n-1];
4526 isl_basic_set_free(bset);
4530 isl_basic_set_free(bset);
4534 /* Given two _disjoint_ basic sets bset1 and bset2, check whether
4535 * for any common value of the parameters and dimensions preceding dim
4536 * in both basic sets, the values of dimension pos in bset1 are
4537 * smaller or larger than those in bset2.
4540 * 1 if bset1 follows bset2
4541 * -1 if bset1 precedes bset2
4542 * 0 if bset1 and bset2 are incomparable
4543 * -2 if some error occurred.
4545 int isl_basic_set_compare_at(struct isl_basic_set *bset1,
4546 struct isl_basic_set *bset2, int pos)
4548 struct isl_dim *dims;
4549 struct isl_basic_map *bmap1 = NULL;
4550 struct isl_basic_map *bmap2 = NULL;
4551 struct isl_ctx *ctx;
4552 struct isl_vec *obj;
4555 unsigned dim1, dim2;
4557 enum isl_lp_result res;
4560 if (!bset1 || !bset2)
4563 nparam = isl_basic_set_n_param(bset1);
4564 dim1 = isl_basic_set_n_dim(bset1);
4565 dim2 = isl_basic_set_n_dim(bset2);
4566 dims = isl_dim_alloc(bset1->ctx, nparam, pos, dim1 - pos);
4567 bmap1 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset1), dims);
4568 dims = isl_dim_alloc(bset2->ctx, nparam, pos, dim2 - pos);
4569 bmap2 = isl_basic_map_from_basic_set(isl_basic_set_copy(bset2), dims);
4570 if (!bmap1 || !bmap2)
4572 bmap1 = isl_basic_map_extend(bmap1, nparam,
4573 pos, (dim1 - pos) + (dim2 - pos),
4574 bmap2->n_div, bmap2->n_eq, bmap2->n_ineq);
4577 total = isl_basic_map_total_dim(bmap1);
4579 obj = isl_vec_alloc(ctx, total);
4580 isl_seq_clr(obj->block.data, total);
4581 isl_int_set_si(obj->block.data[nparam+pos], 1);
4582 isl_int_set_si(obj->block.data[nparam+pos+(dim1-pos)], -1);
4585 bmap1 = add_constraints(bmap1, bmap2, 0, dim1 - pos);
4588 res = isl_solve_lp(bmap1, 0, obj->block.data, ctx->one, &num, &den);
4589 if (res == isl_lp_empty)
4591 else if (res == isl_lp_ok && isl_int_is_pos(num))
4593 else if ((res == isl_lp_ok && isl_int_is_neg(num)) ||
4594 res == isl_lp_unbounded)
4600 isl_basic_map_free(bmap1);
4601 isl_vec_free(ctx, obj);
4604 isl_basic_map_free(bmap1);
4605 isl_basic_map_free(bmap2);
4609 static int isl_basic_map_fast_has_fixed_var(struct isl_basic_map *bmap,
4610 unsigned pos, isl_int *val)
4618 total = isl_basic_map_total_dim(bmap);
4619 for (i = 0, d = total-1; i < bmap->n_eq && d+1 > pos; ++i) {
4620 for (; d+1 > pos; --d)
4621 if (!isl_int_is_zero(bmap->eq[i][1+d]))
4625 if (isl_seq_first_non_zero(bmap->eq[i]+1, d) != -1)
4627 if (isl_seq_first_non_zero(bmap->eq[i]+1+d+1, total-d-1) != -1)
4629 if (!isl_int_is_one(bmap->eq[i][1+d]))
4632 isl_int_neg(*val, bmap->eq[i][0]);
4638 static int isl_map_fast_has_fixed_var(struct isl_map *map,
4639 unsigned pos, isl_int *val)
4651 return isl_basic_map_fast_has_fixed_var(map->p[0], pos, val);
4654 fixed = isl_basic_map_fast_has_fixed_var(map->p[0], pos, &v);
4655 for (i = 1; fixed == 1 && i < map->n; ++i) {
4656 fixed = isl_basic_map_fast_has_fixed_var(map->p[i], pos, &tmp);
4657 if (fixed == 1 && isl_int_ne(tmp, v))
4661 isl_int_set(*val, v);
4667 static int isl_set_fast_has_fixed_var(struct isl_set *set, unsigned pos,
4670 return isl_map_fast_has_fixed_var((struct isl_map *)set, pos, val);
4673 /* Check if dimension dim has fixed value and if so and if val is not NULL,
4674 * then return this fixed value in *val.
4676 int isl_set_fast_dim_is_fixed(struct isl_set *set, unsigned dim, isl_int *val)
4678 return isl_set_fast_has_fixed_var(set, isl_set_n_param(set) + dim, val);
4681 /* Check if input variable in has fixed value and if so and if val is not NULL,
4682 * then return this fixed value in *val.
4684 int isl_map_fast_input_is_fixed(struct isl_map *map, unsigned in, isl_int *val)
4686 return isl_map_fast_has_fixed_var(map, isl_map_n_param(map) + in, val);
4689 /* Check if dimension dim has an (obvious) fixed lower bound and if so
4690 * and if val is not NULL, then return this lower bound in *val.
4692 int isl_basic_set_fast_dim_has_fixed_lower_bound(struct isl_basic_set *bset,
4693 unsigned dim, isl_int *val)
4695 int i, i_eq = -1, i_ineq = -1;
4702 total = isl_basic_set_total_dim(bset);
4703 nparam = isl_basic_set_n_param(bset);
4704 for (i = 0; i < bset->n_eq; ++i) {
4705 if (isl_int_is_zero(bset->eq[i][1+nparam+dim]))
4711 for (i = 0; i < bset->n_ineq; ++i) {
4712 if (!isl_int_is_pos(bset->ineq[i][1+nparam+dim]))
4714 if (i_eq != -1 || i_ineq != -1)
4718 if (i_eq == -1 && i_ineq == -1)
4720 c = i_eq != -1 ? bset->eq[i_eq] : bset->ineq[i_ineq];
4721 /* The coefficient should always be one due to normalization. */
4722 if (!isl_int_is_one(c[1+nparam+dim]))
4724 if (isl_seq_first_non_zero(c+1, nparam+dim) != -1)
4726 if (isl_seq_first_non_zero(c+1+nparam+dim+1,
4727 total - nparam - dim - 1) != -1)
4730 isl_int_neg(*val, c[0]);
4734 int isl_set_fast_dim_has_fixed_lower_bound(struct isl_set *set,
4735 unsigned dim, isl_int *val)
4747 return isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
4751 fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[0],
4753 for (i = 1; fixed == 1 && i < set->n; ++i) {
4754 fixed = isl_basic_set_fast_dim_has_fixed_lower_bound(set->p[i],
4756 if (fixed == 1 && isl_int_ne(tmp, v))
4760 isl_int_set(*val, v);
4766 static struct isl_basic_set *isl_basic_set_reduce_using_equalities(
4767 struct isl_basic_set *bset, struct isl_basic_set *context)
4772 if (!bset || !context)
4775 bset = isl_basic_set_cow(bset);
4779 elim = isl_alloc_array(ctx, int, isl_basic_set_n_dim(bset));
4782 set_compute_elimination_index(context, elim);
4783 for (i = 0; i < bset->n_eq; ++i)
4784 set_reduced_using_equalities(bset->eq[i], bset->eq[i],
4786 for (i = 0; i < bset->n_ineq; ++i)
4787 set_reduced_using_equalities(bset->ineq[i], bset->ineq[i],
4789 isl_basic_set_free(context);
4791 bset = isl_basic_set_simplify(bset);
4792 bset = isl_basic_set_finalize(bset);
4795 isl_basic_set_free(bset);
4796 isl_basic_set_free(context);
4800 static struct isl_basic_set *remove_shifted_constraints(
4801 struct isl_basic_set *bset, struct isl_basic_set *context)
4811 size = round_up(4 * (context->n_ineq+1) / 3 - 1);
4812 bits = ffs(size) - 1;
4813 index = isl_calloc_array(ctx, isl_int **, size);
4817 for (k = 0; k < context->n_ineq; ++k) {
4818 h = set_hash_index(index, size, bits, context, k);
4819 index[h] = &context->ineq[k];
4821 for (k = 0; k < bset->n_ineq; ++k) {
4822 h = set_hash_index(index, size, bits, bset, k);
4825 l = index[h] - &context->ineq[0];
4826 if (isl_int_lt(bset->ineq[k][0], context->ineq[l][0]))
4828 bset = isl_basic_set_cow(bset);
4831 isl_basic_set_drop_inequality(bset, k);
4841 /* Remove all information from bset that is redundant in the context
4842 * of context. In particular, equalities that are linear combinations
4843 * of those in context are removed. Then the inequalities that are
4844 * redundant in the context of the equalities and inequalities of
4845 * context are removed.
4847 static struct isl_basic_set *uset_gist(struct isl_basic_set *bset,
4848 struct isl_basic_set *context)
4852 struct isl_basic_set *combined;
4853 struct isl_ctx *ctx;
4855 if (!bset || !context)
4858 if (context->n_eq > 0) {
4861 struct isl_ctx *ctx = context->ctx;
4862 struct isl_basic_set *reduced_context;
4863 reduced_context = isl_basic_set_remove_equalities(
4864 isl_basic_set_copy(context), &T, &T2);
4865 if (!reduced_context)
4867 bset = isl_basic_set_preimage(ctx, bset, T);
4868 bset = uset_gist(bset, reduced_context);
4869 bset = isl_basic_set_preimage(ctx, bset, T2);
4870 bset = isl_basic_set_reduce_using_equalities(bset, context);
4873 if (!context->n_ineq)
4875 bset = remove_shifted_constraints(bset, context);
4876 combined = isl_basic_set_extend_constraints(isl_basic_set_copy(bset),
4877 context->n_eq, context->n_ineq);
4878 context = set_add_constraints(combined, context, 0);
4883 for (i = bset->n_ineq-1; i >= 0; --i) {
4885 set_swap_inequality(context, i, context->n_ineq-1);
4887 redundant = isl_basic_set_constraint_is_redundant(&context,
4888 context->ineq[context->n_ineq], &opt, NULL);
4889 if (redundant == -1) {
4893 if (F_ISSET(context, ISL_BASIC_MAP_EMPTY)) {
4894 bset = isl_basic_set_set_to_empty(bset);
4898 set_swap_inequality(context, i, context->n_ineq-1);
4900 isl_basic_set_drop_inequality(context, i);
4901 isl_basic_set_drop_inequality(bset, i);
4906 isl_basic_set_free(context);
4909 isl_basic_set_free(context);
4910 isl_basic_set_free(bset);
4914 struct isl_basic_map *isl_basic_map_gist(struct isl_basic_map *bmap,
4915 struct isl_basic_map *context)
4917 struct isl_basic_set *bset;
4919 if (!bmap || !context)
4922 context = isl_basic_map_align_divs(context, bmap);
4923 bmap = isl_basic_map_align_divs(bmap, context);
4925 bset = uset_gist(isl_basic_map_underlying_set(isl_basic_map_copy(bmap)),
4926 isl_basic_map_underlying_set(context));
4928 return isl_basic_map_overlying_set(bset, bmap);
4930 isl_basic_map_free(bmap);
4931 isl_basic_map_free(context);
4935 struct isl_map *isl_map_gist(struct isl_map *map, struct isl_basic_map *context)
4939 map = isl_map_cow(map);
4940 if (!map || !context)
4942 isl_assert(map->ctx, isl_dim_equal(map->dim, context->dim), goto error);
4943 for (i = 0; i < map->n; ++i)
4944 context = isl_basic_map_align_divs(context, map->p[i]);
4945 for (i = 0; i < map->n; ++i) {
4946 map->p[i] = isl_basic_map_gist(map->p[i],
4947 isl_basic_map_copy(context));
4951 isl_basic_map_free(context);
4952 F_CLR(map, ISL_MAP_NORMALIZED);
4956 isl_basic_map_free(context);
4960 struct isl_basic_set *isl_basic_set_gist(struct isl_basic_set *bset,
4961 struct isl_basic_set *context)
4963 return (struct isl_basic_set *)isl_basic_map_gist(
4964 (struct isl_basic_map *)bset, (struct isl_basic_map *)context);
4967 struct isl_set *isl_set_gist(struct isl_set *set, struct isl_basic_set *context)
4969 return (struct isl_set *)isl_map_gist((struct isl_map *)set,
4970 (struct isl_basic_map *)context);
4978 static int qsort_constraint_cmp(const void *p1, const void *p2)
4980 const struct constraint *c1 = (const struct constraint *)p1;
4981 const struct constraint *c2 = (const struct constraint *)p2;
4982 unsigned size = isl_min(c1->size, c2->size);
4983 return isl_seq_cmp(c1->c, c2->c, size);
4986 static struct isl_basic_map *isl_basic_map_sort_constraints(
4987 struct isl_basic_map *bmap)
4990 struct constraint *c;
4995 total = isl_basic_map_total_dim(bmap);
4996 c = isl_alloc_array(bmap->ctx, struct constraint, bmap->n_ineq);
4999 for (i = 0; i < bmap->n_ineq; ++i) {
5001 c[i].c = bmap->ineq[i];
5003 qsort(c, bmap->n_ineq, sizeof(struct constraint), qsort_constraint_cmp);
5004 for (i = 0; i < bmap->n_ineq; ++i)
5005 bmap->ineq[i] = c[i].c;
5009 isl_basic_map_free(bmap);
5013 struct isl_basic_map *isl_basic_map_normalize(struct isl_basic_map *bmap)
5017 if (F_ISSET(bmap, ISL_BASIC_MAP_NORMALIZED))
5019 bmap = isl_basic_map_convex_hull(bmap);
5020 bmap = isl_basic_map_sort_constraints(bmap);
5021 F_SET(bmap, ISL_BASIC_MAP_NORMALIZED);
5025 struct isl_basic_set *isl_basic_set_normalize(struct isl_basic_set *bset)
5027 return (struct isl_basic_set *)isl_basic_map_normalize(
5028 (struct isl_basic_map *)bset);
5031 static int isl_basic_map_fast_cmp(const struct isl_basic_map *bmap1,
5032 const struct isl_basic_map *bmap2)
5039 if (isl_basic_map_n_param(bmap1) != isl_basic_map_n_param(bmap2))
5040 return isl_basic_map_n_param(bmap1) - isl_basic_map_n_param(bmap2);
5041 if (isl_basic_map_n_in(bmap1) != isl_basic_map_n_in(bmap2))
5042 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
5043 if (isl_basic_map_n_out(bmap1) != isl_basic_map_n_out(bmap2))
5044 return isl_basic_map_n_out(bmap1) - isl_basic_map_n_out(bmap2);
5045 if (F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY) &&
5046 F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
5048 if (F_ISSET(bmap1, ISL_BASIC_MAP_EMPTY))
5050 if (F_ISSET(bmap2, ISL_BASIC_MAP_EMPTY))
5052 if (bmap1->n_eq != bmap2->n_eq)
5053 return bmap1->n_eq - bmap2->n_eq;
5054 if (bmap1->n_ineq != bmap2->n_ineq)
5055 return bmap1->n_ineq - bmap2->n_ineq;
5056 if (bmap1->n_div != bmap2->n_div)
5057 return bmap1->n_div - bmap2->n_div;
5058 total = isl_basic_map_total_dim(bmap1);
5059 for (i = 0; i < bmap1->n_eq; ++i) {
5060 cmp = isl_seq_cmp(bmap1->eq[i], bmap2->eq[i], 1+total);
5064 for (i = 0; i < bmap1->n_ineq; ++i) {
5065 cmp = isl_seq_cmp(bmap1->ineq[i], bmap2->ineq[i], 1+total);
5069 for (i = 0; i < bmap1->n_div; ++i) {
5070 cmp = isl_seq_cmp(bmap1->div[i], bmap2->div[i], 1+1+total);
5077 static int isl_basic_map_fast_is_equal(struct isl_basic_map *bmap1,
5078 struct isl_basic_map *bmap2)
5080 return isl_basic_map_fast_cmp(bmap1, bmap2) == 0;
5083 static int qsort_bmap_cmp(const void *p1, const void *p2)
5085 const struct isl_basic_map *bmap1 = *(const struct isl_basic_map **)p1;
5086 const struct isl_basic_map *bmap2 = *(const struct isl_basic_map **)p2;
5088 return isl_basic_map_fast_cmp(bmap1, bmap2);
5091 /* We normalize in place, but if anything goes wrong we need
5092 * to return NULL, so we need to make sure we don't change the
5093 * meaning of any possible other copies of map.
5095 struct isl_map *isl_map_normalize(struct isl_map *map)
5098 struct isl_basic_map *bmap;
5102 if (F_ISSET(map, ISL_MAP_NORMALIZED))
5104 for (i = 0; i < map->n; ++i) {
5105 bmap = isl_basic_map_normalize(isl_basic_map_copy(map->p[i]));
5108 isl_basic_map_free(map->p[i]);
5111 qsort(map->p, map->n, sizeof(struct isl_basic_map *), qsort_bmap_cmp);
5112 F_SET(map, ISL_MAP_NORMALIZED);
5113 map = isl_map_remove_empty_parts(map);
5116 for (i = map->n - 1; i >= 1; --i) {
5117 if (!isl_basic_map_fast_is_equal(map->p[i-1], map->p[i]))
5119 isl_basic_map_free(map->p[i-1]);
5120 for (j = i; j < map->n; ++j)
5121 map->p[j-1] = map->p[j];
5131 struct isl_set *isl_set_normalize(struct isl_set *set)
5133 return (struct isl_set *)isl_map_normalize((struct isl_map *)set);
5136 int isl_map_fast_is_equal(struct isl_map *map1, struct isl_map *map2)
5146 if (!isl_dim_equal(map1->dim, map2->dim))
5149 map1 = isl_map_copy(map1);
5150 map2 = isl_map_copy(map2);
5151 map1 = isl_map_normalize(map1);
5152 map2 = isl_map_normalize(map2);
5155 equal = map1->n == map2->n;
5156 for (i = 0; equal && i < map1->n; ++i) {
5157 equal = isl_basic_map_fast_is_equal(map1->p[i], map2->p[i]);
5170 int isl_set_fast_is_equal(struct isl_set *set1, struct isl_set *set2)
5172 return isl_map_fast_is_equal((struct isl_map *)set1,
5173 (struct isl_map *)set2);
5176 /* Return an interval that ranges from min to max (inclusive)
5178 struct isl_basic_set *isl_basic_set_interval(struct isl_ctx *ctx,
5179 isl_int min, isl_int max)
5182 struct isl_basic_set *bset = NULL;
5184 bset = isl_basic_set_alloc(ctx, 0, 1, 0, 0, 2);
5188 k = isl_basic_set_alloc_inequality(bset);
5191 isl_int_set_si(bset->ineq[k][1], 1);
5192 isl_int_neg(bset->ineq[k][0], min);
5194 k = isl_basic_set_alloc_inequality(bset);
5197 isl_int_set_si(bset->ineq[k][1], -1);
5198 isl_int_set(bset->ineq[k][0], max);
5202 isl_basic_set_free(bset);
5206 /* Return the Cartesian product of the basic sets in list (in the given order).
5208 struct isl_basic_set *isl_basic_set_product(struct isl_basic_set_list *list)
5216 struct isl_basic_set *product = NULL;
5220 isl_assert(list->ctx, list->n > 0, goto error);
5221 isl_assert(list->ctx, list->p[0], goto error);
5222 nparam = isl_basic_set_n_param(list->p[0]);
5223 dim = isl_basic_set_n_dim(list->p[0]);
5224 extra = list->p[0]->n_div;
5225 n_eq = list->p[0]->n_eq;
5226 n_ineq = list->p[0]->n_ineq;
5227 for (i = 1; i < list->n; ++i) {
5228 isl_assert(list->ctx, list->p[i], goto error);
5229 isl_assert(list->ctx,
5230 nparam == isl_basic_set_n_param(list->p[i]), goto error);
5231 dim += isl_basic_set_n_dim(list->p[i]);
5232 extra += list->p[i]->n_div;
5233 n_eq += list->p[i]->n_eq;
5234 n_ineq += list->p[i]->n_ineq;
5236 product = isl_basic_set_alloc(list->ctx, nparam, dim, extra,
5241 for (i = 0; i < list->n; ++i) {
5242 set_add_constraints(product,
5243 isl_basic_set_copy(list->p[i]), dim);
5244 dim += isl_basic_set_n_dim(list->p[i]);
5246 isl_basic_set_list_free(list);
5249 isl_basic_set_free(product);
5250 isl_basic_set_list_free(list);
5254 uint32_t isl_basic_set_get_hash(struct isl_basic_set *bset)
5262 bset = isl_basic_set_copy(bset);
5263 bset = isl_basic_set_normalize(bset);
5266 total = isl_basic_set_total_dim(bset);
5267 isl_hash_byte(hash, bset->n_eq & 0xFF);
5268 for (i = 0; i < bset->n_eq; ++i) {
5270 c_hash = isl_seq_get_hash(bset->eq[i], 1 + total);
5271 isl_hash_hash(hash, c_hash);
5273 isl_hash_byte(hash, bset->n_ineq & 0xFF);
5274 for (i = 0; i < bset->n_ineq; ++i) {
5276 c_hash = isl_seq_get_hash(bset->ineq[i], 1 + total);
5277 isl_hash_hash(hash, c_hash);
5279 isl_hash_byte(hash, bset->n_div & 0xFF);
5280 for (i = 0; i < bset->n_div; ++i) {
5282 if (isl_int_is_zero(bset->div[i][0]))
5284 isl_hash_byte(hash, i & 0xFF);
5285 c_hash = isl_seq_get_hash(bset->div[i], 1 + 1 + total);
5286 isl_hash_hash(hash, c_hash);
5288 isl_basic_set_free(bset);
5292 uint32_t isl_set_get_hash(struct isl_set *set)
5299 set = isl_set_copy(set);
5300 set = isl_set_normalize(set);
5304 hash = isl_hash_init();
5305 for (i = 0; i < set->n; ++i) {
5307 bset_hash = isl_basic_set_get_hash(set->p[i]);
5308 isl_hash_hash(hash, bset_hash);
5316 /* Check if the value for dimension dim is completely determined
5317 * by the values of the other parameters and variables.
5318 * That is, check if dimension dim is involved in an equality.
5320 int isl_basic_set_dim_is_unique(struct isl_basic_set *bset, unsigned dim)
5327 nparam = isl_basic_set_n_param(bset);
5328 for (i = 0; i < bset->n_eq; ++i)
5329 if (!isl_int_is_zero(bset->eq[i][1 + nparam + dim]))
5334 /* Check if the value for dimension dim is completely determined
5335 * by the values of the other parameters and variables.
5336 * That is, check if dimension dim is involved in an equality
5337 * for each of the subsets.
5339 int isl_set_dim_is_unique(struct isl_set *set, unsigned dim)
5345 for (i = 0; i < set->n; ++i) {
5347 unique = isl_basic_set_dim_is_unique(set->p[i], dim);