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