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 */
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 */
44static __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(space: r->space, type: isl_dim_all);
53 if (n < 0)
54 return isl_reordering_free(exp: r);
55 r->dst_len = n;
56 return r;
57}
58
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
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(ctx: isl_reordering_get_ctx(r),
77 src_len: r->src_len, dst_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(exp: dup);
84 for (i = 0; i < dup->src_len; ++i)
85 dup->pos[i] = r->pos[i];
86
87 return dup;
88}
89
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
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(space: exp->space);
110 free(ptr: exp);
111 return NULL;
112}
113
114/* Return the isl_ctx to which "r" belongs.
115 */
116isl_ctx *isl_reordering_get_ctx(__isl_keep isl_reordering *r)
117{
118 return isl_space_get_ctx(space: isl_reordering_peek_space(r));
119}
120
121/* Return the space of "r".
122 */
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 */
132__isl_give isl_space *isl_reordering_get_space(__isl_keep isl_reordering *r)
133{
134 return isl_space_copy(space: 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 */
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(space: alignee, type: isl_dim_all);
153 n_alignee = isl_space_dim(space: alignee, type: isl_dim_param);
154 n_aligner = isl_space_dim(space: aligner, type: isl_dim_param);
155 if (dim < 0 || n_alignee < 0 || n_aligner < 0)
156 return NULL;
157
158 ctx = isl_space_get_ctx(space: alignee);
159 exp = isl_reordering_alloc(ctx, src_len: dim, dst_len: dim);
160 if (!exp)
161 return NULL;
162
163 exp->space = isl_space_replace_params(dst: isl_space_copy(space: alignee), src: aligner);
164
165 for (i = 0; i < n_alignee; ++i) {
166 isl_id *id_i;
167 id_i = isl_space_get_dim_id(space: alignee, type: isl_dim_param, pos: 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(space: aligner, type: isl_dim_param, pos: j);
174 isl_id_free(id: 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: id_i);
181 } else {
182 isl_size pos;
183 pos = isl_space_dim(space: exp->space, type: isl_dim_param);
184 if (pos < 0)
185 exp->space = isl_space_free(space: exp->space);
186 exp->space = isl_space_add_dims(space: exp->space,
187 type: isl_dim_param, n: 1);
188 exp->space = isl_space_set_dim_id(space: exp->space,
189 type: isl_dim_param, pos, id: id_i);
190 exp->pos[i] = pos;
191 }
192 }
193
194 exp = isl_reordering_set_dst_len_from_space(r: 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;
203error:
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 */
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, type: 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, src_len: dim, dst_len: dim);
234 if (!r)
235 return NULL;
236
237 r->space = isl_space_copy(space);
238 r->space = isl_space_unbind_params_insert_domain(space: r->space, tuple);
239 if (!r->space)
240 return isl_reordering_free(exp: r);
241
242 n = isl_space_dim(space: r->space, type: 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(space: r->space, type: isl_dim_param, pos: i);
248 if (!id)
249 return isl_reordering_free(exp: r);
250 pos = isl_space_find_dim_by_id(space, type: isl_dim_param, id);
251 isl_id_free(id);
252 r->pos[pos] = i;
253 }
254
255 offset = isl_space_dim(space: r->space, type: isl_dim_param);
256 n = isl_multi_id_size(multi: tuple);
257 for (i = 0; i < n; ++i) {
258 int pos;
259 isl_id *id;
260
261 id = isl_multi_id_get_id(multi: tuple, pos: i);
262 if (!id)
263 return isl_reordering_free(exp: r);
264 pos = isl_space_find_dim_by_id(space, type: 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(space: r->space, type: isl_dim_all) - dim;
272 first = isl_space_dim(space, type: 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
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(r: exp);
294 offset = exp->dst_len - exp->src_len;
295 res = isl_reordering_alloc(ctx, src_len: exp->src_len + extra,
296 dst_len: exp->dst_len + extra);
297 if (!res)
298 goto error;
299 res->space = isl_reordering_get_space(r: 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;
308error:
309 isl_reordering_free(exp);
310 return NULL;
311}
312
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, type: isl_dim_all);
321 if (!exp || dim < 0)
322 goto error;
323
324 res = isl_reordering_extend(exp: isl_reordering_copy(exp),
325 extra: dim - exp->src_len);
326 res = isl_reordering_cow(r: res);
327 if (!res)
328 goto error;
329 isl_space_free(space: res->space);
330 exp_space = isl_reordering_peek_space(r: exp);
331 res->space = isl_space_replace_params(dst: space, src: exp_space);
332
333 isl_reordering_free(exp);
334
335 if (!res->space)
336 return isl_reordering_free(exp: res);
337
338 return res;
339error:
340 isl_reordering_free(exp);
341 isl_space_free(space);
342 return NULL;
343}
344
345void isl_reordering_dump(__isl_keep isl_reordering *exp)
346{
347 int i;
348
349 isl_space_dump(space: exp->space);
350 for (i = 0; i < exp->src_len; ++i)
351 fprintf(stderr, format: "%d -> %d; ", i, exp->pos[i]);
352 fprintf(stderr, format: "\n");
353}
354

source code of polly/lib/External/isl/isl_reordering.c