isl_polynomial.c: move merge_divs to isl_local_space.c
[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_map_private.h>
12 #include <isl_local_space_private.h>
13 #include <isl_dim_private.h>
14 #include <isl_mat_private.h>
15 #include <isl/seq.h>
16
17 isl_ctx *isl_local_space_get_ctx(__isl_keep isl_local_space *ls)
18 {
19         return ls ? ls->dim->ctx : NULL;
20 }
21
22 __isl_give isl_local_space *isl_local_space_alloc_div(__isl_take isl_dim *dim,
23         __isl_take isl_mat *div)
24 {
25         isl_ctx *ctx;
26         isl_local_space *ls = NULL;
27
28         if (!dim)
29                 goto error;
30
31         ctx = isl_dim_get_ctx(dim);
32         ls = isl_calloc_type(ctx, struct isl_local_space);
33         if (!ls)
34                 goto error;
35
36         ls->ref = 1;
37         ls->dim = dim;
38         ls->div = div;
39
40         return ls;
41 error:
42         isl_dim_free(dim);
43         isl_local_space_free(ls);
44         return NULL;
45 }
46
47 __isl_give isl_local_space *isl_local_space_alloc(__isl_take isl_dim *dim,
48         unsigned n_div)
49 {
50         isl_ctx *ctx;
51         isl_mat *div;
52         unsigned total;
53
54         if (!dim)
55                 return NULL;
56
57         total = isl_dim_total(dim);
58
59         ctx = isl_dim_get_ctx(dim);
60         div = isl_mat_alloc(ctx, n_div, 1 + 1 + total + n_div);
61         return isl_local_space_alloc_div(dim, div);
62 }
63
64 __isl_give isl_local_space *isl_local_space_from_dim(__isl_take isl_dim *dim)
65 {
66         return isl_local_space_alloc(dim, 0);
67 }
68
69 __isl_give isl_local_space *isl_local_space_copy(__isl_keep isl_local_space *ls)
70 {
71         if (!ls)
72                 return NULL;
73
74         ls->ref++;
75         return ls;
76 }
77
78 __isl_give isl_local_space *isl_local_space_dup(__isl_keep isl_local_space *ls)
79 {
80         isl_local_space *dup;
81
82         if (!ls)
83                 return NULL;
84
85         return isl_local_space_alloc_div(isl_dim_copy(ls->dim),
86                                          isl_mat_copy(ls->div));
87
88 }
89
90 __isl_give isl_local_space *isl_local_space_cow(__isl_take isl_local_space *ls)
91 {
92         if (!ls)
93                 return NULL;
94
95         if (ls->ref == 1)
96                 return ls;
97         ls->ref--;
98         return isl_local_space_dup(ls);
99 }
100
101 void *isl_local_space_free(__isl_take isl_local_space *ls)
102 {
103         if (!ls)
104                 return NULL;
105
106         if (--ls->ref > 0)
107                 return NULL;
108
109         isl_dim_free(ls->dim);
110         isl_mat_free(ls->div);
111
112         free(ls);
113
114         return NULL;
115 }
116
117 int isl_local_space_dim(__isl_keep isl_local_space *ls,
118         enum isl_dim_type type)
119 {
120         if (!ls)
121                 return 0;
122         if (type == isl_dim_div)
123                 return ls->div->n_row;
124         if (type == isl_dim_all)
125                 return isl_dim_size(ls->dim, isl_dim_all) + ls->div->n_row;
126         return isl_dim_size(ls->dim, type);
127 }
128
129 unsigned isl_local_space_offset(__isl_keep isl_local_space *ls,
130         enum isl_dim_type type)
131 {
132         isl_dim *dim;
133
134         if (!ls)
135                 return 0;
136
137         dim = ls->dim;
138         switch (type) {
139         case isl_dim_cst:       return 0;
140         case isl_dim_param:     return 1;
141         case isl_dim_in:        return 1 + dim->nparam;
142         case isl_dim_out:       return 1 + dim->nparam + dim->n_in;
143         case isl_dim_div:       return 1 + dim->nparam + dim->n_in + dim->n_out;
144         default:                return 0;
145         }
146 }
147
148 const char *isl_local_space_get_dim_name(__isl_keep isl_local_space *ls,
149         enum isl_dim_type type, unsigned pos)
150 {
151         return ls ? isl_dim_get_name(ls->dim, type, pos) : NULL;
152 }
153
154 __isl_give isl_div *isl_local_space_get_div(__isl_keep isl_local_space *ls,
155         int pos)
156 {
157         isl_basic_map *bmap;
158
159         if (!ls)
160                 return NULL;
161
162         if (pos < 0 || pos >= ls->div->n_row)
163                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
164                         "index out of bounds", return NULL);
165
166         bmap = isl_basic_map_from_local_space(isl_local_space_copy(ls));
167         return isl_basic_map_div(bmap, pos);
168 }
169
170 __isl_give isl_dim *isl_local_space_get_dim(__isl_keep isl_local_space *ls)
171 {
172         if (!ls)
173                 return NULL;
174
175         return isl_dim_copy(ls->dim);
176 }
177
178 __isl_give isl_local_space *isl_local_space_add_div(
179         __isl_take isl_local_space *ls, __isl_take isl_vec *div)
180 {
181         ls = isl_local_space_cow(ls);
182         if (!ls || !div)
183                 goto error;
184
185         if (ls->div->n_col != div->size)
186                 isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
187                         "incompatible dimensions", goto error);
188
189         ls->div = isl_mat_add_zero_cols(ls->div, 1);
190         ls->div = isl_mat_add_rows(ls->div, 1);
191         if (!ls->div)
192                 goto error;
193
194         isl_seq_cpy(ls->div->row[ls->div->n_row - 1], div->el, div->size);
195         isl_int_set_si(ls->div->row[ls->div->n_row - 1][div->size], 0);
196
197         isl_vec_free(div);
198         return ls;
199 error:
200         isl_local_space_free(ls);
201         isl_vec_free(div);
202         return NULL;
203 }
204
205 __isl_give isl_local_space *isl_local_space_replace_divs(
206         __isl_take isl_local_space *ls, __isl_take isl_mat *div)
207 {
208         ls = isl_local_space_cow(ls);
209
210         if (!ls || !div)
211                 goto error;
212
213         isl_mat_free(ls->div);
214         ls->div = div;
215         return ls;
216 error:
217         isl_mat_free(div);
218         isl_local_space_free(ls);
219         return NULL;
220 }
221
222 /* Copy row "s" of "src" to row "d" of "dst", applying the expansion
223  * defined by "exp".
224  */
225 static void expand_row(__isl_keep isl_mat *dst, int d,
226         __isl_keep isl_mat *src, int s, int *exp)
227 {
228         int i;
229         unsigned c = src->n_col - src->n_row;
230
231         isl_seq_cpy(dst->row[d], src->row[s], c);
232         isl_seq_clr(dst->row[d] + c, dst->n_col - c);
233
234         for (i = 0; i < s; ++i)
235                 isl_int_set(dst->row[d][c + exp[i]], src->row[s][c + i]);
236 }
237
238 /* Compare (known) divs.
239  * Return non-zero if at least one of the two divs is unknown.
240  */
241 static int cmp_row(__isl_keep isl_mat *div, int i, int j)
242 {
243         int li, lj;
244
245         if (isl_int_is_zero(div->row[j][0]))
246                 return -1;
247         if (isl_int_is_zero(div->row[i][0]))
248                 return 1;
249
250         li = isl_seq_last_non_zero(div->row[i], div->n_col);
251         lj = isl_seq_last_non_zero(div->row[j], div->n_col);
252
253         if (li != lj)
254                 return li - lj;
255
256         return isl_seq_cmp(div->row[i], div->row[j], div->n_col);
257 }
258
259 /* Combine the two lists of divs into a single list.
260  * For each row i in div1, exp1[i] is set to the position of the corresponding
261  * row in the result.  Similarly for div2 and exp2.
262  * This function guarantees
263  *      exp1[i] >= i
264  *      exp1[i+1] > exp1[i]
265  * For optimal merging, the two input list should have been sorted.
266  */
267 __isl_give isl_mat *isl_merge_divs(__isl_keep isl_mat *div1,
268         __isl_keep isl_mat *div2, int *exp1, int *exp2)
269 {
270         int i, j, k;
271         isl_mat *div = NULL;
272         unsigned d = div1->n_col - div1->n_row;
273
274         div = isl_mat_alloc(div1->ctx, 1 + div1->n_row + div2->n_row,
275                                 d + div1->n_row + div2->n_row);
276         if (!div)
277                 return NULL;
278
279         for (i = 0, j = 0, k = 0; i < div1->n_row && j < div2->n_row; ++k) {
280                 int cmp;
281
282                 expand_row(div, k, div1, i, exp1);
283                 expand_row(div, k + 1, div2, j, exp2);
284
285                 cmp = cmp_row(div, k, k + 1);
286                 if (cmp == 0) {
287                         exp1[i++] = k;
288                         exp2[j++] = k;
289                 } else if (cmp < 0) {
290                         exp1[i++] = k;
291                 } else {
292                         exp2[j++] = k;
293                         isl_seq_cpy(div->row[k], div->row[k + 1], div->n_col);
294                 }
295         }
296         for (; i < div1->n_row; ++i, ++k) {
297                 expand_row(div, k, div1, i, exp1);
298                 exp1[i] = k;
299         }
300         for (; j < div2->n_row; ++j, ++k) {
301                 expand_row(div, k, div2, j, exp2);
302                 exp2[j] = k;
303         }
304
305         div->n_row = k;
306         div->n_col = d + k;
307
308         return div;
309 }