354 lines · c
1/*2 * Copyright 2010 INRIA Saclay3 *4 * Use of this software is governed by the MIT license5 *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, France9 */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 on17 * the number of source dimensions "src_len" and18 * (an initial value for) the number of target dimensions "dst_len".19 *20 * The caller still needs to fill in the space field and21 * possibly adjust the target dimensionality if this is not known yet22 * 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(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 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(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 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(exp->space);110 free(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(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(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 specification139 * that has the parameters of "aligner" first, followed by140 * any remaining parameters of "alignee" that do not occur in "aligner".141 * The other dimensions of "alignee" are mapped to subsequent positions142 * 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(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;203error:204 isl_reordering_free(exp);205 return NULL;206}207 208/* Return a reordering that moves the parameters identified by209 * the elements of "tuple" to a domain tuple inserted into "space".210 * The parameters that remain, are moved from their original positions211 * in the list of parameters to their new positions in this list.212 * The parameters that get removed, are moved to the corresponding213 * positions in the new domain. Note that these set dimensions214 * do not necessarily need to appear as parameters in "space".215 * Any other dimensions are shifted by the number of extra dimensions216 * introduced, i.e., the number of dimensions in the new domain217 * 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, 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 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;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, 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;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(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