Home | History | Annotate | Line # | Download | only in dist 
      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  */
     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 
     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  */
    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  */
    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 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(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  */
    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;
    308 error:
    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;
    339 error:
    340 	isl_reordering_free(exp);
    341 	isl_space_free(space);
    342 	return NULL;
    343 }
    344 
    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