nexmon – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /*
2 * Copyright 2011 INRIA Saclay
3 * Copyright 2012 Ecole Normale Superieure
4 *
5 * Use of this software is governed by the GNU LGPLv2.1 license
6 *
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
9 * 91893 Orsay, France
10 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
11 */
12  
13 #include <isl_ctx_private.h>
14 #include <isl_map_private.h>
15 #include <isl_local_space_private.h>
16 #include <isl_space_private.h>
17 #include <isl_mat_private.h>
18 #include <isl_aff_private.h>
19 #include <isl/seq.h>
20  
21 isl_ctx *isl_local_space_get_ctx(__isl_keep isl_local_space *ls)
22 {
23 return ls ? ls->dim->ctx : NULL;
24 }
25  
26 __isl_give isl_local_space *isl_local_space_alloc_div(__isl_take isl_space *dim,
27 __isl_take isl_mat *div)
28 {
29 isl_ctx *ctx;
30 isl_local_space *ls = NULL;
31  
32 if (!dim || !div)
33 goto error;
34  
35 ctx = isl_space_get_ctx(dim);
36 ls = isl_calloc_type(ctx, struct isl_local_space);
37 if (!ls)
38 goto error;
39  
40 ls->ref = 1;
41 ls->dim = dim;
42 ls->div = div;
43  
44 return ls;
45 error:
46 isl_mat_free(div);
47 isl_space_free(dim);
48 isl_local_space_free(ls);
49 return NULL;
50 }
51  
52 __isl_give isl_local_space *isl_local_space_alloc(__isl_take isl_space *dim,
53 unsigned n_div)
54 {
55 isl_ctx *ctx;
56 isl_mat *div;
57 unsigned total;
58  
59 if (!dim)
60 return NULL;
61  
62 total = isl_space_dim(dim, isl_dim_all);
63  
64 ctx = isl_space_get_ctx(dim);
65 div = isl_mat_alloc(ctx, n_div, 1 + 1 + total + n_div);
66 return isl_local_space_alloc_div(dim, div);
67 }
68  
69 __isl_give isl_local_space *isl_local_space_from_space(__isl_take isl_space *dim)
70 {
71 return isl_local_space_alloc(dim, 0);
72 }
73  
74 __isl_give isl_local_space *isl_local_space_copy(__isl_keep isl_local_space *ls)
75 {
76 if (!ls)
77 return NULL;
78  
79 ls->ref++;
80 return ls;
81 }
82  
83 __isl_give isl_local_space *isl_local_space_dup(__isl_keep isl_local_space *ls)
84 {
85 if (!ls)
86 return NULL;
87  
88 return isl_local_space_alloc_div(isl_space_copy(ls->dim),
89 isl_mat_copy(ls->div));
90  
91 }
92  
93 __isl_give isl_local_space *isl_local_space_cow(__isl_take isl_local_space *ls)
94 {
95 if (!ls)
96 return NULL;
97  
98 if (ls->ref == 1)
99 return ls;
100 ls->ref--;
101 return isl_local_space_dup(ls);
102 }
103  
104 void *isl_local_space_free(__isl_take isl_local_space *ls)
105 {
106 if (!ls)
107 return NULL;
108  
109 if (--ls->ref > 0)
110 return NULL;
111  
112 isl_space_free(ls->dim);
113 isl_mat_free(ls->div);
114  
115 free(ls);
116  
117 return NULL;
118 }
119  
120 /* Is the local space that of a set?
121 */
122 int isl_local_space_is_set(__isl_keep isl_local_space *ls)
123 {
124 return ls ? isl_space_is_set(ls->dim) : -1;
125 }
126  
127 /* Return true if the two local spaces are identical, with identical
128 * expressions for the integer divisions.
129 */
130 int isl_local_space_is_equal(__isl_keep isl_local_space *ls1,
131 __isl_keep isl_local_space *ls2)
132 {
133 int equal;
134  
135 if (!ls1 || !ls2)
136 return -1;
137  
138 equal = isl_space_is_equal(ls1->dim, ls2->dim);
139 if (equal < 0 || !equal)
140 return equal;
141  
142 if (!isl_local_space_divs_known(ls1))
143 return 0;
144 if (!isl_local_space_divs_known(ls2))
145 return 0;
146  
147 return isl_mat_is_equal(ls1->div, ls2->div);
148 }
149  
150 int isl_local_space_dim(__isl_keep isl_local_space *ls,
151 enum isl_dim_type type)
152 {
153 if (!ls)
154 return 0;
155 if (type == isl_dim_div)
156 return ls->div->n_row;
157 if (type == isl_dim_all)
158 return isl_space_dim(ls->dim, isl_dim_all) + ls->div->n_row;
159 return isl_space_dim(ls->dim, type);
160 }
161  
162 unsigned isl_local_space_offset(__isl_keep isl_local_space *ls,
163 enum isl_dim_type type)
164 {
165 isl_space *dim;
166  
167 if (!ls)
168 return 0;
169  
170 dim = ls->dim;
171 switch (type) {
172 case isl_dim_cst: return 0;
173 case isl_dim_param: return 1;
174 case isl_dim_in: return 1 + dim->nparam;
175 case isl_dim_out: return 1 + dim->nparam + dim->n_in;
176 case isl_dim_div: return 1 + dim->nparam + dim->n_in + dim->n_out;
177 default: return 0;
178 }
179 }
180  
181 /* Does the given dimension have a name?
182 */
183 int isl_local_space_has_dim_name(__isl_keep isl_local_space *ls,
184 enum isl_dim_type type, unsigned pos)
185 {
186 return ls ? isl_space_has_dim_name(ls->dim, type, pos) : -1;
187 }
188  
189 const char *isl_local_space_get_dim_name(__isl_keep isl_local_space *ls,
190 enum isl_dim_type type, unsigned pos)
191 {
192 return ls ? isl_space_get_dim_name(ls->dim, type, pos) : NULL;
193 }
194  
195 __isl_give isl_aff *isl_local_space_get_div(__isl_keep isl_local_space *ls,
196 int pos)
197 {
198 isl_aff *aff;
199  
200 if (!ls)
201 return NULL;
202  
203 if (pos < 0 || pos >= ls->div->n_row)
204 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
205 "index out of bounds", return NULL);
206  
207 if (isl_int_is_zero(ls->div->row[pos][0]))
208 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
209 "expression of div unknown", return NULL);
210  
211 aff = isl_aff_alloc(isl_local_space_copy(ls));
212 if (!aff)
213 return NULL;
214 isl_seq_cpy(aff->v->el, ls->div->row[pos], aff->v->size);
215 return aff;
216 }
217  
218 __isl_give isl_space *isl_local_space_get_space(__isl_keep isl_local_space *ls)
219 {
220 if (!ls)
221 return NULL;
222  
223 return isl_space_copy(ls->dim);
224 }
225  
226 __isl_give isl_local_space *isl_local_space_set_dim_name(
227 __isl_take isl_local_space *ls,
228 enum isl_dim_type type, unsigned pos, const char *s)
229 {
230 ls = isl_local_space_cow(ls);
231 if (!ls)
232 return NULL;
233 ls->dim = isl_space_set_dim_name(ls->dim, type, pos, s);
234 if (!ls->dim)
235 return isl_local_space_free(ls);
236  
237 return ls;
238 }
239  
240 __isl_give isl_local_space *isl_local_space_set_dim_id(
241 __isl_take isl_local_space *ls,
242 enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
243 {
244 ls = isl_local_space_cow(ls);
245 if (!ls)
246 return isl_id_free(id);
247 ls->dim = isl_space_set_dim_id(ls->dim, type, pos, id);
248 if (!ls->dim)
249 return isl_local_space_free(ls);
250  
251 return ls;
252 }
253  
254 __isl_give isl_local_space *isl_local_space_reset_space(
255 __isl_take isl_local_space *ls, __isl_take isl_space *dim)
256 {
257 ls = isl_local_space_cow(ls);
258 if (!ls || !dim)
259 goto error;
260  
261 isl_space_free(ls->dim);
262 ls->dim = dim;
263  
264 return ls;
265 error:
266 isl_local_space_free(ls);
267 isl_space_free(dim);
268 return NULL;
269 }
270  
271 /* Reorder the columns of the given div definitions according to the
272 * given reordering.
273 * The order of the divs themselves is assumed not to change.
274 */
275 static __isl_give isl_mat *reorder_divs(__isl_take isl_mat *div,
276 __isl_take isl_reordering *r)
277 {
278 int i, j;
279 isl_mat *mat;
280 int extra;
281  
282 if (!div || !r)
283 goto error;
284  
285 extra = isl_space_dim(r->dim, isl_dim_all) + div->n_row - r->len;
286 mat = isl_mat_alloc(div->ctx, div->n_row, div->n_col + extra);
287 if (!mat)
288 goto error;
289  
290 for (i = 0; i < div->n_row; ++i) {
291 isl_seq_cpy(mat->row[i], div->row[i], 2);
292 isl_seq_clr(mat->row[i] + 2, mat->n_col - 2);
293 for (j = 0; j < r->len; ++j)
294 isl_int_set(mat->row[i][2 + r->pos[j]],
295 div->row[i][2 + j]);
296 }
297  
298 isl_reordering_free(r);
299 isl_mat_free(div);
300 return mat;
301 error:
302 isl_reordering_free(r);
303 isl_mat_free(div);
304 return NULL;
305 }
306  
307 /* Reorder the dimensions of "ls" according to the given reordering.
308 * The reordering r is assumed to have been extended with the local
309 * variables, leaving them in the same order.
310 */
311 __isl_give isl_local_space *isl_local_space_realign(
312 __isl_take isl_local_space *ls, __isl_take isl_reordering *r)
313 {
314 ls = isl_local_space_cow(ls);
315 if (!ls || !r)
316 goto error;
317  
318 ls->div = reorder_divs(ls->div, isl_reordering_copy(r));
319 if (!ls->div)
320 goto error;
321  
322 ls = isl_local_space_reset_space(ls, isl_space_copy(r->dim));
323  
324 isl_reordering_free(r);
325 return ls;
326 error:
327 isl_local_space_free(ls);
328 isl_reordering_free(r);
329 return NULL;
330 }
331  
332 __isl_give isl_local_space *isl_local_space_add_div(
333 __isl_take isl_local_space *ls, __isl_take isl_vec *div)
334 {
335 ls = isl_local_space_cow(ls);
336 if (!ls || !div)
337 goto error;
338  
339 if (ls->div->n_col != div->size)
340 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
341 "incompatible dimensions", goto error);
342  
343 ls->div = isl_mat_add_zero_cols(ls->div, 1);
344 ls->div = isl_mat_add_rows(ls->div, 1);
345 if (!ls->div)
346 goto error;
347  
348 isl_seq_cpy(ls->div->row[ls->div->n_row - 1], div->el, div->size);
349 isl_int_set_si(ls->div->row[ls->div->n_row - 1][div->size], 0);
350  
351 isl_vec_free(div);
352 return ls;
353 error:
354 isl_local_space_free(ls);
355 isl_vec_free(div);
356 return NULL;
357 }
358  
359 __isl_give isl_local_space *isl_local_space_replace_divs(
360 __isl_take isl_local_space *ls, __isl_take isl_mat *div)
361 {
362 ls = isl_local_space_cow(ls);
363  
364 if (!ls || !div)
365 goto error;
366  
367 isl_mat_free(ls->div);
368 ls->div = div;
369 return ls;
370 error:
371 isl_mat_free(div);
372 isl_local_space_free(ls);
373 return NULL;
374 }
375  
376 /* Copy row "s" of "src" to row "d" of "dst", applying the expansion
377 * defined by "exp".
378 */
379 static void expand_row(__isl_keep isl_mat *dst, int d,
380 __isl_keep isl_mat *src, int s, int *exp)
381 {
382 int i;
383 unsigned c = src->n_col - src->n_row;
384  
385 isl_seq_cpy(dst->row[d], src->row[s], c);
386 isl_seq_clr(dst->row[d] + c, dst->n_col - c);
387  
388 for (i = 0; i < s; ++i)
389 isl_int_set(dst->row[d][c + exp[i]], src->row[s][c + i]);
390 }
391  
392 /* Compare (known) divs.
393 * Return non-zero if at least one of the two divs is unknown.
394 * In particular, if both divs are unknown, we respect their
395 * current order. Otherwise, we sort the known div after the unknown
396 * div only if the known div depends on the unknown div.
397 */
398 static int cmp_row(isl_int *row_i, isl_int *row_j, int i, int j,
399 unsigned n_row, unsigned n_col)
400 {
401 int li, lj;
402 int unknown_i, unknown_j;
403  
404 unknown_i = isl_int_is_zero(row_i[0]);
405 unknown_j = isl_int_is_zero(row_j[0]);
406  
407 if (unknown_i && unknown_j)
408 return i - j;
409  
410 if (unknown_i)
411 li = n_col - n_row + i;
412 else
413 li = isl_seq_last_non_zero(row_i, n_col);
414 if (unknown_j)
415 lj = n_col - n_row + j;
416 else
417 lj = isl_seq_last_non_zero(row_j, n_col);
418  
419 if (li != lj)
420 return li - lj;
421  
422 return isl_seq_cmp(row_i, row_j, n_col);
423 }
424  
425 /* Call cmp_row for divs in a matrix.
426 */
427 static int mat_cmp_row(__isl_keep isl_mat *div, int i, int j)
428 {
429 return cmp_row(div->row[i], div->row[j], i, j, div->n_row, div->n_col);
430 }
431  
432 /* Call cmp_row for divs in a basic map.
433 */
434 static int bmap_cmp_row(__isl_keep isl_basic_map *bmap, int i, int j,
435 unsigned total)
436 {
437 return cmp_row(bmap->div[i], bmap->div[j], i, j, bmap->n_div, total);
438 }
439  
440 /* Sort the divs in "bmap".
441 *
442 * We first make sure divs are placed after divs on which they depend.
443 * Then we perform a simple insertion sort based on the same ordering
444 * that is used in isl_merge_divs.
445 */
446 __isl_give isl_basic_map *isl_basic_map_sort_divs(
447 __isl_take isl_basic_map *bmap)
448 {
449 int i, j;
450 unsigned total;
451  
452 bmap = isl_basic_map_order_divs(bmap);
453 if (!bmap)
454 return NULL;
455 if (bmap->n_div <= 1)
456 return bmap;
457  
458 total = 2 + isl_basic_map_total_dim(bmap);
459 for (i = 1; i < bmap->n_div; ++i) {
460 for (j = i - 1; j >= 0; --j) {
461 if (bmap_cmp_row(bmap, j, j + 1, total) <= 0)
462 break;
463 isl_basic_map_swap_div(bmap, j, j + 1);
464 }
465 }
466  
467 return bmap;
468 }
469  
470 /* Sort the divs in the basic maps of "map".
471 */
472 __isl_give isl_map *isl_map_sort_divs(__isl_take isl_map *map)
473 {
474 return isl_map_inline_foreach_basic_map(map, &isl_basic_map_sort_divs);
475 }
476  
477 /* Combine the two lists of divs into a single list.
478 * For each row i in div1, exp1[i] is set to the position of the corresponding
479 * row in the result. Similarly for div2 and exp2.
480 * This function guarantees
481 * exp1[i] >= i
482 * exp1[i+1] > exp1[i]
483 * For optimal merging, the two input list should have been sorted.
484 */
485 __isl_give isl_mat *isl_merge_divs(__isl_keep isl_mat *div1,
486 __isl_keep isl_mat *div2, int *exp1, int *exp2)
487 {
488 int i, j, k;
489 isl_mat *div = NULL;
490 unsigned d;
491  
492 if (!div1 || !div2)
493 return NULL;
494  
495 d = div1->n_col - div1->n_row;
496 div = isl_mat_alloc(div1->ctx, 1 + div1->n_row + div2->n_row,
497 d + div1->n_row + div2->n_row);
498 if (!div)
499 return NULL;
500  
501 for (i = 0, j = 0, k = 0; i < div1->n_row && j < div2->n_row; ++k) {
502 int cmp;
503  
504 expand_row(div, k, div1, i, exp1);
505 expand_row(div, k + 1, div2, j, exp2);
506  
507 cmp = mat_cmp_row(div, k, k + 1);
508 if (cmp == 0) {
509 exp1[i++] = k;
510 exp2[j++] = k;
511 } else if (cmp < 0) {
512 exp1[i++] = k;
513 } else {
514 exp2[j++] = k;
515 isl_seq_cpy(div->row[k], div->row[k + 1], div->n_col);
516 }
517 }
518 for (; i < div1->n_row; ++i, ++k) {
519 expand_row(div, k, div1, i, exp1);
520 exp1[i] = k;
521 }
522 for (; j < div2->n_row; ++j, ++k) {
523 expand_row(div, k, div2, j, exp2);
524 exp2[j] = k;
525 }
526  
527 div->n_row = k;
528 div->n_col = d + k;
529  
530 return div;
531 }
532  
533 /* Construct a local space that contains all the divs in either
534 * "ls1" or "ls2".
535 */
536 __isl_give isl_local_space *isl_local_space_intersect(
537 __isl_take isl_local_space *ls1, __isl_take isl_local_space *ls2)
538 {
539 isl_ctx *ctx;
540 int *exp1 = NULL;
541 int *exp2 = NULL;
542 isl_mat *div;
543  
544 if (!ls1 || !ls2)
545 goto error;
546  
547 ctx = isl_local_space_get_ctx(ls1);
548 if (!isl_space_is_equal(ls1->dim, ls2->dim))
549 isl_die(ctx, isl_error_invalid,
550 "spaces should be identical", goto error);
551  
552 if (ls2->div->n_row == 0) {
553 isl_local_space_free(ls2);
554 return ls1;
555 }
556  
557 if (ls1->div->n_row == 0) {
558 isl_local_space_free(ls1);
559 return ls2;
560 }
561  
562 exp1 = isl_alloc_array(ctx, int, ls1->div->n_row);
563 exp2 = isl_alloc_array(ctx, int, ls2->div->n_row);
564 if (!exp1 || !exp2)
565 goto error;
566  
567 div = isl_merge_divs(ls1->div, ls2->div, exp1, exp2);
568 if (!div)
569 goto error;
570  
571 free(exp1);
572 free(exp2);
573 isl_local_space_free(ls2);
574 isl_mat_free(ls1->div);
575 ls1->div = div;
576  
577 return ls1;
578 error:
579 free(exp1);
580 free(exp2);
581 isl_local_space_free(ls1);
582 isl_local_space_free(ls2);
583 return NULL;
584 }
585  
586 int isl_local_space_divs_known(__isl_keep isl_local_space *ls)
587 {
588 int i;
589  
590 if (!ls)
591 return -1;
592  
593 for (i = 0; i < ls->div->n_row; ++i)
594 if (isl_int_is_zero(ls->div->row[i][0]))
595 return 0;
596  
597 return 1;
598 }
599  
600 __isl_give isl_local_space *isl_local_space_domain(
601 __isl_take isl_local_space *ls)
602 {
603 ls = isl_local_space_drop_dims(ls, isl_dim_out,
604 0, isl_local_space_dim(ls, isl_dim_out));
605 ls = isl_local_space_cow(ls);
606 if (!ls)
607 return NULL;
608 ls->dim = isl_space_domain(ls->dim);
609 if (!ls->dim)
610 return isl_local_space_free(ls);
611 return ls;
612 }
613  
614 __isl_give isl_local_space *isl_local_space_range(
615 __isl_take isl_local_space *ls)
616 {
617 ls = isl_local_space_drop_dims(ls, isl_dim_in,
618 0, isl_local_space_dim(ls, isl_dim_in));
619 ls = isl_local_space_cow(ls);
620 if (!ls)
621 return NULL;
622  
623 ls->dim = isl_space_range(ls->dim);
624 if (!ls->dim)
625 return isl_local_space_free(ls);
626 return ls;
627 }
628  
629 /* Construct a local space for a map that has the given local
630 * space as domain and that has a zero-dimensional range.
631 */
632 __isl_give isl_local_space *isl_local_space_from_domain(
633 __isl_take isl_local_space *ls)
634 {
635 ls = isl_local_space_cow(ls);
636 if (!ls)
637 return NULL;
638 ls->dim = isl_space_from_domain(ls->dim);
639 if (!ls->dim)
640 return isl_local_space_free(ls);
641 return ls;
642 }
643  
644 __isl_give isl_local_space *isl_local_space_add_dims(
645 __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned n)
646 {
647 int pos;
648  
649 if (!ls)
650 return NULL;
651 pos = isl_local_space_dim(ls, type);
652 return isl_local_space_insert_dims(ls, type, pos, n);
653 }
654  
655 /* Remove common factor of non-constant terms and denominator.
656 */
657 static void normalize_div(__isl_keep isl_local_space *ls, int div)
658 {
659 isl_ctx *ctx = ls->div->ctx;
660 unsigned total = ls->div->n_col - 2;
661  
662 isl_seq_gcd(ls->div->row[div] + 2, total, &ctx->normalize_gcd);
663 isl_int_gcd(ctx->normalize_gcd,
664 ctx->normalize_gcd, ls->div->row[div][0]);
665 if (isl_int_is_one(ctx->normalize_gcd))
666 return;
667  
668 isl_seq_scale_down(ls->div->row[div] + 2, ls->div->row[div] + 2,
669 ctx->normalize_gcd, total);
670 isl_int_divexact(ls->div->row[div][0], ls->div->row[div][0],
671 ctx->normalize_gcd);
672 isl_int_fdiv_q(ls->div->row[div][1], ls->div->row[div][1],
673 ctx->normalize_gcd);
674 }
675  
676 /* Exploit the equalities in "eq" to simplify the expressions of
677 * the integer divisions in "ls".
678 * The integer divisions in "ls" are assumed to appear as regular
679 * dimensions in "eq".
680 */
681 __isl_give isl_local_space *isl_local_space_substitute_equalities(
682 __isl_take isl_local_space *ls, __isl_take isl_basic_set *eq)
683 {
684 int i, j, k;
685 unsigned total;
686 unsigned n_div;
687  
688 ls = isl_local_space_cow(ls);
689 if (!ls || !eq)
690 goto error;
691  
692 total = isl_space_dim(eq->dim, isl_dim_all);
693 if (isl_local_space_dim(ls, isl_dim_all) != total)
694 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
695 "dimensions don't match", goto error);
696 total++;
697 n_div = eq->n_div;
698 for (i = 0; i < eq->n_eq; ++i) {
699 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
700 if (j < 0 || j == 0 || j >= total)
701 continue;
702  
703 for (k = 0; k < ls->div->n_row; ++k) {
704 if (isl_int_is_zero(ls->div->row[k][1 + j]))
705 continue;
706 isl_seq_elim(ls->div->row[k] + 1, eq->eq[i], j, total,
707 &ls->div->row[k][0]);
708 normalize_div(ls, k);
709 }
710 }
711  
712 isl_basic_set_free(eq);
713 return ls;
714 error:
715 isl_basic_set_free(eq);
716 isl_local_space_free(ls);
717 return NULL;
718 }
719  
720 /* Plug in "subs" for dimension "type", "pos" in the integer divisions
721 * of "ls".
722 *
723 * Let i be the dimension to replace and let "subs" be of the form
724 *
725 * f/d
726 *
727 * Any integer division with a non-zero coefficient for i,
728 *
729 * floor((a i + g)/m)
730 *
731 * is replaced by
732 *
733 * floor((a f + d g)/(m d))
734 */
735 __isl_give isl_local_space *isl_local_space_substitute(
736 __isl_take isl_local_space *ls,
737 enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
738 {
739 int i;
740 isl_int v;
741  
742 ls = isl_local_space_cow(ls);
743 if (!ls || !subs)
744 return isl_local_space_free(ls);
745  
746 if (!isl_space_is_equal(ls->dim, subs->ls->dim))
747 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
748 "spaces don't match", return isl_local_space_free(ls));
749 if (isl_local_space_dim(subs->ls, isl_dim_div) != 0)
750 isl_die(isl_local_space_get_ctx(ls), isl_error_unsupported,
751 "cannot handle divs yet",
752 return isl_local_space_free(ls));
753  
754 pos += isl_local_space_offset(ls, type);
755  
756 isl_int_init(v);
757 for (i = 0; i < ls->div->n_row; ++i) {
758 if (isl_int_is_zero(ls->div->row[i][1 + pos]))
759 continue;
760 isl_int_set(v, ls->div->row[i][1 + pos]);
761 isl_int_set_si(ls->div->row[i][1 + pos], 0);
762 isl_seq_combine(ls->div->row[i] + 1,
763 subs->v->el[0], ls->div->row[i] + 1,
764 v, subs->v->el + 1, subs->v->size - 1);
765 isl_int_mul(ls->div->row[i][0],
766 ls->div->row[i][0], subs->v->el[0]);
767 normalize_div(ls, i);
768 }
769 isl_int_clear(v);
770  
771 return ls;
772 }
773  
774 int isl_local_space_is_named_or_nested(__isl_keep isl_local_space *ls,
775 enum isl_dim_type type)
776 {
777 if (!ls)
778 return -1;
779 return isl_space_is_named_or_nested(ls->dim, type);
780 }
781  
782 __isl_give isl_local_space *isl_local_space_drop_dims(
783 __isl_take isl_local_space *ls,
784 enum isl_dim_type type, unsigned first, unsigned n)
785 {
786 isl_ctx *ctx;
787  
788 if (!ls)
789 return NULL;
790 if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))
791 return ls;
792  
793 ctx = isl_local_space_get_ctx(ls);
794 if (first + n > isl_local_space_dim(ls, type))
795 isl_die(ctx, isl_error_invalid, "range out of bounds",
796 return isl_local_space_free(ls));
797  
798 ls = isl_local_space_cow(ls);
799 if (!ls)
800 return NULL;
801  
802 if (type == isl_dim_div) {
803 ls->div = isl_mat_drop_rows(ls->div, first, n);
804 } else {
805 ls->dim = isl_space_drop_dims(ls->dim, type, first, n);
806 if (!ls->dim)
807 return isl_local_space_free(ls);
808 }
809  
810 first += 1 + isl_local_space_offset(ls, type);
811 ls->div = isl_mat_drop_cols(ls->div, first, n);
812 if (!ls->div)
813 return isl_local_space_free(ls);
814  
815 return ls;
816 }
817  
818 __isl_give isl_local_space *isl_local_space_insert_dims(
819 __isl_take isl_local_space *ls,
820 enum isl_dim_type type, unsigned first, unsigned n)
821 {
822 isl_ctx *ctx;
823  
824 if (!ls)
825 return NULL;
826 if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))
827 return ls;
828  
829 ctx = isl_local_space_get_ctx(ls);
830 if (first > isl_local_space_dim(ls, type))
831 isl_die(ctx, isl_error_invalid, "position out of bounds",
832 return isl_local_space_free(ls));
833  
834 ls = isl_local_space_cow(ls);
835 if (!ls)
836 return NULL;
837  
838 if (type == isl_dim_div) {
839 ls->div = isl_mat_insert_zero_rows(ls->div, first, n);
840 } else {
841 ls->dim = isl_space_insert_dims(ls->dim, type, first, n);
842 if (!ls->dim)
843 return isl_local_space_free(ls);
844 }
845  
846 first += 1 + isl_local_space_offset(ls, type);
847 ls->div = isl_mat_insert_zero_cols(ls->div, first, n);
848 if (!ls->div)
849 return isl_local_space_free(ls);
850  
851 return ls;
852 }
853  
854 /* Check if the constraints pointed to by "constraint" is a div
855 * constraint corresponding to div "div" in "ls".
856 *
857 * That is, if div = floor(f/m), then check if the constraint is
858 *
859 * f - m d >= 0
860 * or
861 * -(f-(m-1)) + m d >= 0
862 */
863 int isl_local_space_is_div_constraint(__isl_keep isl_local_space *ls,
864 isl_int *constraint, unsigned div)
865 {
866 unsigned pos;
867  
868 if (!ls)
869 return -1;
870  
871 if (isl_int_is_zero(ls->div->row[div][0]))
872 return 0;
873  
874 pos = isl_local_space_offset(ls, isl_dim_div) + div;
875  
876 if (isl_int_eq(constraint[pos], ls->div->row[div][0])) {
877 int neg;
878 isl_int_sub(ls->div->row[div][1],
879 ls->div->row[div][1], ls->div->row[div][0]);
880 isl_int_add_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
881 neg = isl_seq_is_neg(constraint, ls->div->row[div]+1, pos);
882 isl_int_sub_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
883 isl_int_add(ls->div->row[div][1],
884 ls->div->row[div][1], ls->div->row[div][0]);
885 if (!neg)
886 return 0;
887 if (isl_seq_first_non_zero(constraint+pos+1,
888 ls->div->n_row-div-1) != -1)
889 return 0;
890 } else if (isl_int_abs_eq(constraint[pos], ls->div->row[div][0])) {
891 if (!isl_seq_eq(constraint, ls->div->row[div]+1, pos))
892 return 0;
893 if (isl_seq_first_non_zero(constraint+pos+1,
894 ls->div->n_row-div-1) != -1)
895 return 0;
896 } else
897 return 0;
898  
899 return 1;
900 }
901  
902 /*
903 * Set active[i] to 1 if the dimension at position i is involved
904 * in the linear expression l.
905 */
906 int *isl_local_space_get_active(__isl_keep isl_local_space *ls, isl_int *l)
907 {
908 int i, j;
909 isl_ctx *ctx;
910 int *active = NULL;
911 unsigned total;
912 unsigned offset;
913  
914 ctx = isl_local_space_get_ctx(ls);
915 total = isl_local_space_dim(ls, isl_dim_all);
916 active = isl_calloc_array(ctx, int, total);
917 if (!active)
918 return NULL;
919  
920 for (i = 0; i < total; ++i)
921 active[i] = !isl_int_is_zero(l[i]);
922  
923 offset = isl_local_space_offset(ls, isl_dim_div) - 1;
924 for (i = ls->div->n_row - 1; i >= 0; --i) {
925 if (!active[offset + i])
926 continue;
927 for (j = 0; j < total; ++j)
928 active[j] |= !isl_int_is_zero(ls->div->row[i][2 + j]);
929 }
930  
931 return active;
932 }
933  
934 /* Given a local space "ls" of a set, create a local space
935 * for the lift of the set. In particular, the result
936 * is of the form [dim -> local[..]], with ls->div->n_row variables in the
937 * range of the wrapped map.
938 */
939 __isl_give isl_local_space *isl_local_space_lift(
940 __isl_take isl_local_space *ls)
941 {
942 ls = isl_local_space_cow(ls);
943 if (!ls)
944 return NULL;
945  
946 ls->dim = isl_space_lift(ls->dim, ls->div->n_row);
947 ls->div = isl_mat_drop_rows(ls->div, 0, ls->div->n_row);
948 if (!ls->dim || !ls->div)
949 return isl_local_space_free(ls);
950  
951 return ls;
952 }
953  
954 /* Construct a basic map that maps a set living in local space "ls"
955 * to the corresponding lifted local space.
956 */
957 __isl_give isl_basic_map *isl_local_space_lifting(
958 __isl_take isl_local_space *ls)
959 {
960 isl_basic_map *lifting;
961 isl_basic_set *bset;
962  
963 if (!ls)
964 return NULL;
965 if (!isl_local_space_is_set(ls))
966 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
967 "lifting only defined on set spaces",
968 return isl_local_space_free(ls));
969  
970 bset = isl_basic_set_from_local_space(ls);
971 lifting = isl_basic_set_unwrap(isl_basic_set_lift(bset));
972 lifting = isl_basic_map_domain_map(lifting);
973 lifting = isl_basic_map_reverse(lifting);
974  
975 return lifting;
976 }