1 /*
2 * Copyright 2010 INRIA Saclay
3 *
4 * Use of this software is governed by the MIT 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/id.h>
13 #include <isl_space_private.h>
14 #include <isl_reordering.h>
15
16 /* Create a new reordering description based on
17 * the number of source dimensions "src_len" and
18 * (an initial value for) the number of target dimensions "dst_len".
19 *
20 * The caller still needs to fill in the space field and
21 * possibly adjust the target dimensionality if this is not known yet
22 * when this function is called.
23 */
isl_reordering_alloc(isl_ctx * ctx,int src_len,int dst_len)24 __isl_give isl_reordering *isl_reordering_alloc(isl_ctx *ctx, int src_len,
25 int dst_len)
26 {
27 isl_reordering *exp;
28
29 exp = isl_alloc(ctx, struct isl_reordering,
30 sizeof(struct isl_reordering) + (src_len - 1) * sizeof(int));
31 if (!exp)
32 return NULL;
33
34 exp->ref = 1;
35 exp->src_len = src_len;
36 exp->dst_len = dst_len;
37 exp->space = NULL;
38
39 return exp;
40 }
41
42 /* Set r->dst_len to the total dimensionality of r->space.
43 */
isl_reordering_set_dst_len_from_space(__isl_take isl_reordering * r)44 static __isl_give isl_reordering *isl_reordering_set_dst_len_from_space(
45 __isl_take isl_reordering *r)
46 {
47 isl_size n;
48
49 if (!r)
50 return NULL;
51
52 n = isl_space_dim(r->space, isl_dim_all);
53 if (n < 0)
54 return isl_reordering_free(r);
55 r->dst_len = n;
56 return r;
57 }
58
isl_reordering_copy(__isl_keep isl_reordering * exp)59 __isl_give isl_reordering *isl_reordering_copy(__isl_keep isl_reordering *exp)
60 {
61 if (!exp)
62 return NULL;
63
64 exp->ref++;
65 return exp;
66 }
67
isl_reordering_dup(__isl_keep isl_reordering * r)68 __isl_give isl_reordering *isl_reordering_dup(__isl_keep isl_reordering *r)
69 {
70 int i;
71 isl_reordering *dup;
72
73 if (!r)
74 return NULL;
75
76 dup = isl_reordering_alloc(isl_reordering_get_ctx(r),
77 r->src_len, r->dst_len);
78 if (!dup)
79 return NULL;
80
81 dup->space = isl_reordering_get_space(r);
82 if (!dup->space)
83 return isl_reordering_free(dup);
84 for (i = 0; i < dup->src_len; ++i)
85 dup->pos[i] = r->pos[i];
86
87 return dup;
88 }
89
isl_reordering_cow(__isl_take isl_reordering * r)90 __isl_give isl_reordering *isl_reordering_cow(__isl_take isl_reordering *r)
91 {
92 if (!r)
93 return NULL;
94
95 if (r->ref == 1)
96 return r;
97 r->ref--;
98 return isl_reordering_dup(r);
99 }
100
isl_reordering_free(__isl_take isl_reordering * exp)101 __isl_null isl_reordering *isl_reordering_free(__isl_take isl_reordering *exp)
102 {
103 if (!exp)
104 return NULL;
105
106 if (--exp->ref > 0)
107 return NULL;
108
109 isl_space_free(exp->space);
110 free(exp);
111 return NULL;
112 }
113
114 /* Return the isl_ctx to which "r" belongs.
115 */
isl_reordering_get_ctx(__isl_keep isl_reordering * r)116 isl_ctx *isl_reordering_get_ctx(__isl_keep isl_reordering *r)
117 {
118 return isl_space_get_ctx(isl_reordering_peek_space(r));
119 }
120
121 /* Return the space of "r".
122 */
isl_reordering_peek_space(__isl_keep isl_reordering * r)123 __isl_keep isl_space *isl_reordering_peek_space(__isl_keep isl_reordering *r)
124 {
125 if (!r)
126 return NULL;
127 return r->space;
128 }
129
130 /* Return a copy of the space of "r".
131 */
isl_reordering_get_space(__isl_keep isl_reordering * r)132 __isl_give isl_space *isl_reordering_get_space(__isl_keep isl_reordering *r)
133 {
134 return isl_space_copy(isl_reordering_peek_space(r));
135 }
136
137 /* Construct a reordering that maps the parameters of "alignee"
138 * to the corresponding parameters in a new dimension specification
139 * that has the parameters of "aligner" first, followed by
140 * any remaining parameters of "alignee" that do not occur in "aligner".
141 * The other dimensions of "alignee" are mapped to subsequent positions
142 * in order.
143 */
isl_parameter_alignment_reordering(__isl_keep isl_space * alignee,__isl_keep isl_space * aligner)144 __isl_give isl_reordering *isl_parameter_alignment_reordering(
145 __isl_keep isl_space *alignee, __isl_keep isl_space *aligner)
146 {
147 int i, j, offset;
148 isl_ctx *ctx;
149 isl_reordering *exp;
150 isl_size dim, n_alignee, n_aligner;
151
152 dim = isl_space_dim(alignee, isl_dim_all);
153 n_alignee = isl_space_dim(alignee, isl_dim_param);
154 n_aligner = isl_space_dim(aligner, isl_dim_param);
155 if (dim < 0 || n_alignee < 0 || n_aligner < 0)
156 return NULL;
157
158 ctx = isl_space_get_ctx(alignee);
159 exp = isl_reordering_alloc(ctx, dim, dim);
160 if (!exp)
161 return NULL;
162
163 exp->space = isl_space_replace_params(isl_space_copy(alignee), aligner);
164
165 for (i = 0; i < n_alignee; ++i) {
166 isl_id *id_i;
167 id_i = isl_space_get_dim_id(alignee, isl_dim_param, i);
168 if (!id_i)
169 isl_die(ctx, isl_error_invalid,
170 "cannot align unnamed parameters", goto error);
171 for (j = 0; j < n_aligner; ++j) {
172 isl_id *id_j;
173 id_j = isl_space_get_dim_id(aligner, isl_dim_param, j);
174 isl_id_free(id_j);
175 if (id_i == id_j)
176 break;
177 }
178 if (j < n_aligner) {
179 exp->pos[i] = j;
180 isl_id_free(id_i);
181 } else {
182 isl_size pos;
183 pos = isl_space_dim(exp->space, isl_dim_param);
184 if (pos < 0)
185 exp->space = isl_space_free(exp->space);
186 exp->space = isl_space_add_dims(exp->space,
187 isl_dim_param, 1);
188 exp->space = isl_space_set_dim_id(exp->space,
189 isl_dim_param, pos, id_i);
190 exp->pos[i] = pos;
191 }
192 }
193
194 exp = isl_reordering_set_dst_len_from_space(exp);
195 if (!exp)
196 return NULL;
197
198 offset = exp->dst_len - exp->src_len;
199 for (i = n_alignee; i < dim; ++i)
200 exp->pos[i] = offset + i;
201
202 return exp;
203 error:
204 isl_reordering_free(exp);
205 return NULL;
206 }
207
208 /* Return a reordering that moves the parameters identified by
209 * the elements of "tuple" to a domain tuple inserted into "space".
210 * The parameters that remain, are moved from their original positions
211 * in the list of parameters to their new positions in this list.
212 * The parameters that get removed, are moved to the corresponding
213 * positions in the new domain. Note that these set dimensions
214 * do not necessarily need to appear as parameters in "space".
215 * Any other dimensions are shifted by the number of extra dimensions
216 * introduced, i.e., the number of dimensions in the new domain
217 * that did not appear as parameters in "space".
218 */
isl_reordering_unbind_params_insert_domain(__isl_keep isl_space * space,__isl_keep isl_multi_id * tuple)219 __isl_give isl_reordering *isl_reordering_unbind_params_insert_domain(
220 __isl_keep isl_space *space, __isl_keep isl_multi_id *tuple)
221 {
222 int i, n;
223 int offset, first;
224 isl_size dim;
225 isl_ctx *ctx;
226 isl_reordering *r;
227
228 dim = isl_space_dim(space, isl_dim_all);
229 if (dim < 0 || !tuple)
230 return NULL;
231
232 ctx = isl_space_get_ctx(space);
233 r = isl_reordering_alloc(ctx, dim, dim);
234 if (!r)
235 return NULL;
236
237 r->space = isl_space_copy(space);
238 r->space = isl_space_unbind_params_insert_domain(r->space, tuple);
239 if (!r->space)
240 return isl_reordering_free(r);
241
242 n = isl_space_dim(r->space, isl_dim_param);
243 for (i = 0; i < n; ++i) {
244 int pos;
245 isl_id *id;
246
247 id = isl_space_get_dim_id(r->space, isl_dim_param, i);
248 if (!id)
249 return isl_reordering_free(r);
250 pos = isl_space_find_dim_by_id(space, isl_dim_param, id);
251 isl_id_free(id);
252 r->pos[pos] = i;
253 }
254
255 offset = isl_space_dim(r->space, isl_dim_param);
256 n = isl_multi_id_size(tuple);
257 for (i = 0; i < n; ++i) {
258 int pos;
259 isl_id *id;
260
261 id = isl_multi_id_get_id(tuple, i);
262 if (!id)
263 return isl_reordering_free(r);
264 pos = isl_space_find_dim_by_id(space, isl_dim_param, id);
265 isl_id_free(id);
266 if (pos < 0)
267 continue;
268 r->pos[pos] = offset + i;
269 }
270
271 offset = isl_space_dim(r->space, isl_dim_all) - dim;
272 first = isl_space_dim(space, isl_dim_param);
273 n = dim - first;
274 for (i = 0; i < n; ++i)
275 r->pos[first + i] = first + offset + i;
276
277 return isl_reordering_set_dst_len_from_space(r);
278 }
279
isl_reordering_extend(__isl_take isl_reordering * exp,unsigned extra)280 __isl_give isl_reordering *isl_reordering_extend(__isl_take isl_reordering *exp,
281 unsigned extra)
282 {
283 int i;
284 isl_ctx *ctx;
285 isl_reordering *res;
286 int offset;
287
288 if (!exp)
289 return NULL;
290 if (extra == 0)
291 return exp;
292
293 ctx = isl_reordering_get_ctx(exp);
294 offset = exp->dst_len - exp->src_len;
295 res = isl_reordering_alloc(ctx, exp->src_len + extra,
296 exp->dst_len + extra);
297 if (!res)
298 goto error;
299 res->space = isl_reordering_get_space(exp);
300 for (i = 0; i < exp->src_len; ++i)
301 res->pos[i] = exp->pos[i];
302 for (i = exp->src_len; i < res->src_len; ++i)
303 res->pos[i] = offset + i;
304
305 isl_reordering_free(exp);
306
307 return res;
308 error:
309 isl_reordering_free(exp);
310 return NULL;
311 }
312
isl_reordering_extend_space(__isl_take isl_reordering * exp,__isl_take isl_space * space)313 __isl_give isl_reordering *isl_reordering_extend_space(
314 __isl_take isl_reordering *exp, __isl_take isl_space *space)
315 {
316 isl_space *exp_space;
317 isl_reordering *res;
318 isl_size dim;
319
320 dim = isl_space_dim(space, isl_dim_all);
321 if (!exp || dim < 0)
322 goto error;
323
324 res = isl_reordering_extend(isl_reordering_copy(exp),
325 dim - exp->src_len);
326 res = isl_reordering_cow(res);
327 if (!res)
328 goto error;
329 isl_space_free(res->space);
330 exp_space = isl_reordering_peek_space(exp);
331 res->space = isl_space_replace_params(space, exp_space);
332
333 isl_reordering_free(exp);
334
335 if (!res->space)
336 return isl_reordering_free(res);
337
338 return res;
339 error:
340 isl_reordering_free(exp);
341 isl_space_free(space);
342 return NULL;
343 }
344
isl_reordering_dump(__isl_keep isl_reordering * exp)345 void isl_reordering_dump(__isl_keep isl_reordering *exp)
346 {
347 int i;
348
349 isl_space_dump(exp->space);
350 for (i = 0; i < exp->src_len; ++i)
351 fprintf(stderr, "%d -> %d; ", i, exp->pos[i]);
352 fprintf(stderr, "\n");
353 }
354