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