a57b31ebded7f8fa9a2da7779fb9c801c31b02fa
[platform/upstream/isl.git] / isl_local_space.c
1 /*
2  * Copyright 2011      INRIA Saclay
3  *
4  * Use of this software is governed by the GNU LGPLv2.1 license
5  *
6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
8  * 91893 Orsay, France
9  */
10
11 #include <isl_ctx_private.h>
12 #include <isl_map_private.h>
13 #include <isl_local_space_private.h>
14 #include <isl_dim_private.h>
15 #include <isl_mat_private.h>
16 #include <isl/seq.h>
17
18 isl_ctx *isl_local_space_get_ctx(__isl_keep isl_local_space *ls)
19 {
20         return ls ? ls->dim->ctx : NULL;
21 }
22
23 __isl_give isl_local_space *isl_local_space_alloc_div(__isl_take isl_dim *dim,
24         __isl_take isl_mat *div)
25 {
26         isl_ctx *ctx;
27         isl_local_space *ls = NULL;
28
29         if (!dim)
30                 goto error;
31
32         ctx = isl_dim_get_ctx(dim);
33         ls = isl_calloc_type(ctx, struct isl_local_space);
34         if (!ls)
35                 goto error;
36
37         ls->ref = 1;
38         ls->dim = dim;
39         ls->div = div;
40
41         return ls;
42 error:
43         isl_dim_free(dim);
44         isl_local_space_free(ls);
45         return NULL;
46 }
47
48 __isl_give isl_local_space *isl_local_space_alloc(__isl_take isl_dim *dim,
49         unsigned n_div)
50 {
51         isl_ctx *ctx;
52         isl_mat *div;
53         unsigned total;
54
55         if (!dim)
56                 return NULL;
57
58         total = isl_dim_total(dim);
59
60         ctx = isl_dim_get_ctx(dim);
61         div = isl_mat_alloc(ctx, n_div, 1 + 1 + total + n_div);
62         return isl_local_space_alloc_div(dim, div);
63 }
64
65 __isl_give isl_local_space *isl_local_space_from_dim(__isl_take isl_dim *dim)
66 {
67         return isl_local_space_alloc(dim, 0);
68 }
69
70 __isl_give isl_local_space *isl_local_space_copy(__isl_keep isl_local_space *ls)
71 {
72         if (!ls)
73                 return NULL;
74
75         ls->ref++;
76         return ls;
77 }
78
79 __isl_give isl_local_space *isl_local_space_dup(__isl_keep isl_local_space *ls)
80 {
81         if (!ls)
82                 return NULL;
83
84         return isl_local_space_alloc_div(isl_dim_copy(ls->dim),
85                                          isl_mat_copy(ls->div));
86
87 }
88
89 __isl_give isl_local_space *isl_local_space_cow(__isl_take isl_local_space *ls)
90 {
91         if (!ls)
92                 return NULL;
93
94         if (ls->ref == 1)
95                 return ls;
96         ls->ref--;
97         return isl_local_space_dup(ls);
98 }
99
100 void *isl_local_space_free(__isl_take isl_local_space *ls)
101 {
102         if (!ls)
103                 return NULL;
104
105         if (--ls->ref > 0)
106                 return NULL;
107
108         isl_dim_free(ls->dim);
109         isl_mat_free(ls->div);
110
111         free(ls);
112
113         return NULL;
114 }
115
116 /* Return true if the two local spaces are identical, with identical
117  * expressions for the integer divisions.
118  */
119 int isl_local_space_is_equal(__isl_keep isl_local_space *ls1,
120         __isl_keep isl_local_space *ls2)
121 {
122         int equal;
123
124         if (!ls1 || !ls2)
125                 return -1;
126
127         equal = isl_dim_equal(ls1->dim, ls2->dim);
128         if (equal < 0 || !equal)
129                 return equal;
130
131         return isl_mat_is_equal(ls1->div, ls2->div);
132 }
133
134 int isl_local_space_dim(__isl_keep isl_local_space *ls,
135         enum isl_dim_type type)
136 {
137         if (!ls)
138                 return 0;
139         if (type == isl_dim_div)
140                 return ls->div->n_row;
141         if (type == isl_dim_all)
142                 return isl_dim_size(ls->dim, isl_dim_all) + ls->div->n_row;
143         return isl_dim_size(ls->dim, type);
144 }
145
146 unsigned isl_local_space_offset(__isl_keep isl_local_space *ls,
147         enum isl_dim_type type)
148 {
149         isl_dim *dim;
150
151         if (!ls)
152                 return 0;
153
154         dim = ls->dim;
155         switch (type) {
156         case isl_dim_cst:       return 0;
157         case isl_dim_param:     return 1;
158         case isl_dim_in:        return 1 + dim->nparam;
159         case isl_dim_out:       return 1 + dim->nparam + dim->n_in;
160         case isl_dim_div:       return 1 + dim->nparam + dim->n_in + dim->n_out;
161         default:                return 0;
162         }
163 }
164
165 const char *isl_local_space_get_dim_name(__isl_keep isl_local_space *ls,
166         enum isl_dim_type type, unsigned pos)
167 {
168         return ls ? isl_dim_get_name(ls->dim, type, pos) : NULL;
169 }
170
171 __isl_give isl_div *isl_local_space_get_div(__isl_keep isl_local_space *ls,
172         int pos)
173 {
174         isl_basic_map *bmap;
175
176         if (!ls)
177                 return NULL;
178
179         if (pos < 0 || pos >= ls->div->n_row)
180                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
181                         "index out of bounds", return NULL);
182
183         bmap = isl_basic_map_from_local_space(isl_local_space_copy(ls));
184         return isl_basic_map_div(bmap, pos);
185 }
186
187 __isl_give isl_dim *isl_local_space_get_dim(__isl_keep isl_local_space *ls)
188 {
189         if (!ls)
190                 return NULL;
191
192         return isl_dim_copy(ls->dim);
193 }
194
195 __isl_give isl_local_space *isl_local_space_set_dim_name(
196         __isl_take isl_local_space *ls,
197         enum isl_dim_type type, unsigned pos, const char *s)
198 {
199         ls = isl_local_space_cow(ls);
200         if (!ls)
201                 return NULL;
202         ls->dim = isl_dim_set_name(ls->dim, type, pos, s);
203         if (!ls->dim)
204                 return isl_local_space_free(ls);
205
206         return ls;
207 }
208
209 __isl_give isl_local_space *isl_local_space_add_div(
210         __isl_take isl_local_space *ls, __isl_take isl_vec *div)
211 {
212         ls = isl_local_space_cow(ls);
213         if (!ls || !div)
214                 goto error;
215
216         if (ls->div->n_col != div->size)
217                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
218                         "incompatible dimensions", goto error);
219
220         ls->div = isl_mat_add_zero_cols(ls->div, 1);
221         ls->div = isl_mat_add_rows(ls->div, 1);
222         if (!ls->div)
223                 goto error;
224
225         isl_seq_cpy(ls->div->row[ls->div->n_row - 1], div->el, div->size);
226         isl_int_set_si(ls->div->row[ls->div->n_row - 1][div->size], 0);
227
228         isl_vec_free(div);
229         return ls;
230 error:
231         isl_local_space_free(ls);
232         isl_vec_free(div);
233         return NULL;
234 }
235
236 __isl_give isl_local_space *isl_local_space_replace_divs(
237         __isl_take isl_local_space *ls, __isl_take isl_mat *div)
238 {
239         ls = isl_local_space_cow(ls);
240
241         if (!ls || !div)
242                 goto error;
243
244         isl_mat_free(ls->div);
245         ls->div = div;
246         return ls;
247 error:
248         isl_mat_free(div);
249         isl_local_space_free(ls);
250         return NULL;
251 }
252
253 /* Copy row "s" of "src" to row "d" of "dst", applying the expansion
254  * defined by "exp".
255  */
256 static void expand_row(__isl_keep isl_mat *dst, int d,
257         __isl_keep isl_mat *src, int s, int *exp)
258 {
259         int i;
260         unsigned c = src->n_col - src->n_row;
261
262         isl_seq_cpy(dst->row[d], src->row[s], c);
263         isl_seq_clr(dst->row[d] + c, dst->n_col - c);
264
265         for (i = 0; i < s; ++i)
266                 isl_int_set(dst->row[d][c + exp[i]], src->row[s][c + i]);
267 }
268
269 /* Compare (known) divs.
270  * Return non-zero if at least one of the two divs is unknown.
271  */
272 static int cmp_row(__isl_keep isl_mat *div, int i, int j)
273 {
274         int li, lj;
275
276         if (isl_int_is_zero(div->row[j][0]))
277                 return -1;
278         if (isl_int_is_zero(div->row[i][0]))
279                 return 1;
280
281         li = isl_seq_last_non_zero(div->row[i], div->n_col);
282         lj = isl_seq_last_non_zero(div->row[j], div->n_col);
283
284         if (li != lj)
285                 return li - lj;
286
287         return isl_seq_cmp(div->row[i], div->row[j], div->n_col);
288 }
289
290 /* Combine the two lists of divs into a single list.
291  * For each row i in div1, exp1[i] is set to the position of the corresponding
292  * row in the result.  Similarly for div2 and exp2.
293  * This function guarantees
294  *      exp1[i] >= i
295  *      exp1[i+1] > exp1[i]
296  * For optimal merging, the two input list should have been sorted.
297  */
298 __isl_give isl_mat *isl_merge_divs(__isl_keep isl_mat *div1,
299         __isl_keep isl_mat *div2, int *exp1, int *exp2)
300 {
301         int i, j, k;
302         isl_mat *div = NULL;
303         unsigned d = div1->n_col - div1->n_row;
304
305         div = isl_mat_alloc(div1->ctx, 1 + div1->n_row + div2->n_row,
306                                 d + div1->n_row + div2->n_row);
307         if (!div)
308                 return NULL;
309
310         for (i = 0, j = 0, k = 0; i < div1->n_row && j < div2->n_row; ++k) {
311                 int cmp;
312
313                 expand_row(div, k, div1, i, exp1);
314                 expand_row(div, k + 1, div2, j, exp2);
315
316                 cmp = cmp_row(div, k, k + 1);
317                 if (cmp == 0) {
318                         exp1[i++] = k;
319                         exp2[j++] = k;
320                 } else if (cmp < 0) {
321                         exp1[i++] = k;
322                 } else {
323                         exp2[j++] = k;
324                         isl_seq_cpy(div->row[k], div->row[k + 1], div->n_col);
325                 }
326         }
327         for (; i < div1->n_row; ++i, ++k) {
328                 expand_row(div, k, div1, i, exp1);
329                 exp1[i] = k;
330         }
331         for (; j < div2->n_row; ++j, ++k) {
332                 expand_row(div, k, div2, j, exp2);
333                 exp2[j] = k;
334         }
335
336         div->n_row = k;
337         div->n_col = d + k;
338
339         return div;
340 }
341
342 int isl_local_space_divs_known(__isl_keep isl_local_space *ls)
343 {
344         int i;
345
346         if (!ls)
347                 return -1;
348
349         for (i = 0; i < ls->div->n_row; ++i)
350                 if (isl_int_is_zero(ls->div->row[i][0]))
351                         return 0;
352
353         return 1;
354 }
355
356 /* Construct a local space for a map that has the given local
357  * space as domain and that has a zero-dimensional range.
358  */
359 __isl_give isl_local_space *isl_local_space_from_domain(
360         __isl_take isl_local_space *ls)
361 {
362         ls = isl_local_space_cow(ls);
363         if (!ls)
364                 return NULL;
365         ls->dim = isl_dim_from_domain(ls->dim);
366         if (!ls->dim)
367                 return isl_local_space_free(ls);
368         return ls;
369 }
370
371 __isl_give isl_local_space *isl_local_space_add_dims(
372         __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned n)
373 {
374         int pos;
375
376         if (!ls)
377                 return NULL;
378         pos = isl_local_space_dim(ls, type);
379         return isl_local_space_insert_dims(ls, type, pos, n);
380 }
381
382 /* Remove common factor of non-constant terms and denominator.
383  */
384 static void normalize_div(__isl_keep isl_local_space *ls, int div)
385 {
386         isl_ctx *ctx = ls->div->ctx;
387         unsigned total = ls->div->n_col - 2;
388
389         isl_seq_gcd(ls->div->row[div] + 2, total, &ctx->normalize_gcd);
390         isl_int_gcd(ctx->normalize_gcd,
391                     ctx->normalize_gcd, ls->div->row[div][0]);
392         if (isl_int_is_one(ctx->normalize_gcd))
393                 return;
394
395         isl_seq_scale_down(ls->div->row[div] + 2, ls->div->row[div] + 2,
396                             ctx->normalize_gcd, total);
397         isl_int_divexact(ls->div->row[div][0], ls->div->row[div][0],
398                             ctx->normalize_gcd);
399         isl_int_fdiv_q(ls->div->row[div][1], ls->div->row[div][1],
400                             ctx->normalize_gcd);
401 }
402
403 /* Exploit the equalities in "eq" to simplify the expressions of
404  * the integer divisions in "ls".
405  * The integer divisions in "ls" are assumed to appear as regular
406  * dimensions in "eq".
407  */
408 __isl_give isl_local_space *isl_local_space_substitute_equalities(
409         __isl_take isl_local_space *ls, __isl_take isl_basic_set *eq)
410 {
411         int i, j, k;
412         unsigned total;
413         unsigned n_div;
414
415         ls = isl_local_space_cow(ls);
416         if (!ls || !eq)
417                 goto error;
418
419         total = isl_dim_total(eq->dim);
420         if (isl_local_space_dim(ls, isl_dim_all) != total)
421                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
422                         "dimensions don't match", goto error);
423         total++;
424         n_div = eq->n_div;
425         for (i = 0; i < eq->n_eq; ++i) {
426                 j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
427                 if (j < 0 || j == 0 || j >= total)
428                         continue;
429
430                 for (k = 0; k < ls->div->n_row; ++k) {
431                         if (isl_int_is_zero(ls->div->row[k][1 + j]))
432                                 continue;
433                         isl_seq_elim(ls->div->row[k] + 1, eq->eq[i], j, total,
434                                         &ls->div->row[k][0]);
435                         normalize_div(ls, k);
436                 }
437         }
438
439         isl_basic_set_free(eq);
440         return ls;
441 error:
442         isl_basic_set_free(eq);
443         isl_local_space_free(ls);
444         return NULL;
445 }
446
447 int isl_local_space_is_named_or_nested(__isl_keep isl_local_space *ls,
448         enum isl_dim_type type)
449 {
450         if (!ls)
451                 return -1;
452         return isl_dim_is_named_or_nested(ls->dim, type);
453 }
454
455 __isl_give isl_local_space *isl_local_space_drop_dims(
456         __isl_take isl_local_space *ls,
457         enum isl_dim_type type, unsigned first, unsigned n)
458 {
459         isl_ctx *ctx;
460
461         if (!ls)
462                 return NULL;
463         if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))
464                 return ls;
465
466         ctx = isl_local_space_get_ctx(ls);
467         if (first + n > isl_local_space_dim(ls, type))
468                 isl_die(ctx, isl_error_invalid, "range out of bounds",
469                         return isl_local_space_free(ls));
470
471         ls = isl_local_space_cow(ls);
472         if (!ls)
473                 return NULL;
474
475         if (type == isl_dim_div) {
476                 ls->div = isl_mat_drop_rows(ls->div, first, n);
477         } else {
478                 ls->dim = isl_dim_drop(ls->dim, type, first, n);
479                 if (!ls->dim)
480                         return isl_local_space_free(ls);
481         }
482
483         first += 1 + isl_local_space_offset(ls, type);
484         ls->div = isl_mat_drop_cols(ls->div, first, n);
485         if (!ls->div)
486                 return isl_local_space_free(ls);
487
488         return ls;
489 }
490
491 __isl_give isl_local_space *isl_local_space_insert_dims(
492         __isl_take isl_local_space *ls,
493         enum isl_dim_type type, unsigned first, unsigned n)
494 {
495         isl_ctx *ctx;
496
497         if (!ls)
498                 return NULL;
499         if (n == 0 && !isl_local_space_is_named_or_nested(ls, type))
500                 return ls;
501
502         ctx = isl_local_space_get_ctx(ls);
503         if (first > isl_local_space_dim(ls, type))
504                 isl_die(ctx, isl_error_invalid, "position out of bounds",
505                         return isl_local_space_free(ls));
506
507         ls = isl_local_space_cow(ls);
508         if (!ls)
509                 return NULL;
510
511         if (type == isl_dim_div) {
512                 ls->div = isl_mat_insert_zero_rows(ls->div, first, n);
513         } else {
514                 ls->dim = isl_dim_insert(ls->dim, type, first, n);
515                 if (!ls->dim)
516                         return isl_local_space_free(ls);
517         }
518
519         first += 1 + isl_local_space_offset(ls, type);
520         ls->div = isl_mat_insert_zero_cols(ls->div, first, n);
521         if (!ls->div)
522                 return isl_local_space_free(ls);
523
524         return ls;
525 }