Home | History | Annotate | Line # | Download | only in dist 
      1 /*
      2  * Copyright 2008-2009 Katholieke Universiteit Leuven
      3  * Copyright 2010-2011 INRIA Saclay
      4  *
      5  * Use of this software is governed by the MIT license
      6  *
      7  * Written by Sven Verdoolaege, K.U.Leuven, Departement
      8  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
      9  * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
     10  * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
     11  */
     12 
     13 #include <isl_map_private.h>
     14 #include <isl_space_private.h>
     15 #include <isl_dim_map.h>
     16 #include <isl_reordering.h>
     17 
     18 struct isl_dim_map_entry {
     19 	int pos;
     20 	int sgn;
     21 };
     22 
     23 /* Maps dst positions to src positions */
     24 struct isl_dim_map {
     25 	unsigned len;
     26 	struct isl_dim_map_entry m[1];
     27 };
     28 
     29 __isl_give isl_dim_map *isl_dim_map_alloc(isl_ctx *ctx, unsigned len)
     30 {
     31 	int i;
     32 	struct isl_dim_map *dim_map;
     33 	dim_map = isl_alloc(ctx, struct isl_dim_map,
     34 	    sizeof(struct isl_dim_map) + len * sizeof(struct isl_dim_map_entry));
     35 	if (!dim_map)
     36 		return NULL;
     37 	dim_map->len = 1 + len;
     38 	dim_map->m[0].pos = 0;
     39 	dim_map->m[0].sgn = 1;
     40 	for (i = 0; i < len; ++i)
     41 		dim_map->m[1 + i].sgn = 0;
     42 	return dim_map;
     43 }
     44 
     45 /* Free "dim_map" and return NULL.
     46  */
     47 __isl_null isl_dim_map *isl_dim_map_free(__isl_take isl_dim_map *dim_map)
     48 {
     49 	free(dim_map);
     50 	return NULL;
     51 }
     52 
     53 void isl_dim_map_range(__isl_keep isl_dim_map *dim_map,
     54 	unsigned dst_pos, int dst_stride, unsigned src_pos, int src_stride,
     55 	unsigned n, int sign)
     56 {
     57 	int i;
     58 
     59 	if (!dim_map)
     60 		return;
     61 
     62 	for (i = 0; i < n; ++i) {
     63 		unsigned d = 1 + dst_pos + dst_stride * i;
     64 		unsigned s = 1 + src_pos + src_stride * i;
     65 		dim_map->m[d].pos = s;
     66 		dim_map->m[d].sgn = sign;
     67 	}
     68 }
     69 
     70 void isl_dim_map_dim_range(__isl_keep isl_dim_map *dim_map,
     71 	__isl_keep isl_space *space, enum isl_dim_type type,
     72 	unsigned first, unsigned n, unsigned dst_pos)
     73 {
     74 	int i;
     75 	isl_size off;
     76 
     77 	off = isl_space_offset(space, type);
     78 	if (!dim_map || off < 0)
     79 		return;
     80 
     81 	for (i = 0; i < n; ++i) {
     82 		dim_map->m[1 + dst_pos + i].pos = 1 + off + first + i;
     83 		dim_map->m[1 + dst_pos + i].sgn = 1;
     84 	}
     85 }
     86 
     87 void isl_dim_map_dim(__isl_keep isl_dim_map *dim_map,
     88 	__isl_keep isl_space *space, enum isl_dim_type type, unsigned dst_pos)
     89 {
     90 	isl_size dim = isl_space_dim(space, type);
     91 
     92 	if (dim < 0)
     93 		return;
     94 	isl_dim_map_dim_range(dim_map, space, type, 0, dim, dst_pos);
     95 }
     96 
     97 void isl_dim_map_div(__isl_keep isl_dim_map *dim_map,
     98 	__isl_keep isl_basic_map *bmap, unsigned dst_pos)
     99 {
    100 	int i;
    101 	unsigned src_pos;
    102 
    103 	if (!dim_map || !bmap)
    104 		return;
    105 
    106 	src_pos = isl_basic_map_offset(bmap, isl_dim_div);
    107 	for (i = 0; i < bmap->n_div; ++i) {
    108 		dim_map->m[1 + dst_pos + i].pos = src_pos + i;
    109 		dim_map->m[1 + dst_pos + i].sgn = 1;
    110 	}
    111 }
    112 
    113 void isl_dim_map_dump(struct isl_dim_map *dim_map)
    114 {
    115 	int i;
    116 
    117 	for (i = 0; i < dim_map->len; ++i)
    118 		fprintf(stderr, "%d -> %d * %d; ", i,
    119 			dim_map->m[i].sgn, dim_map->m[i].pos);
    120 	fprintf(stderr, "\n");
    121 }
    122 
    123 static void copy_constraint_dim_map(isl_int *dst, isl_int *src,
    124 					struct isl_dim_map *dim_map)
    125 {
    126 	int i;
    127 
    128 	for (i = 0; i < dim_map->len; ++i) {
    129 		if (dim_map->m[i].sgn == 0)
    130 			isl_int_set_si(dst[i], 0);
    131 		else if (dim_map->m[i].sgn > 0)
    132 			isl_int_set(dst[i], src[dim_map->m[i].pos]);
    133 		else
    134 			isl_int_neg(dst[i], src[dim_map->m[i].pos]);
    135 	}
    136 }
    137 
    138 static void copy_div_dim_map(isl_int *dst, isl_int *src,
    139 					struct isl_dim_map *dim_map)
    140 {
    141 	isl_int_set(dst[0], src[0]);
    142 	copy_constraint_dim_map(dst+1, src+1, dim_map);
    143 }
    144 
    145 __isl_give isl_basic_map *isl_basic_map_add_constraints_dim_map(
    146 	__isl_take isl_basic_map *dst, __isl_take isl_basic_map *src,
    147 	__isl_take isl_dim_map *dim_map)
    148 {
    149 	int i;
    150 
    151 	if (!src || !dst || !dim_map)
    152 		goto error;
    153 
    154 	for (i = 0; i < src->n_eq; ++i) {
    155 		int i1 = isl_basic_map_alloc_equality(dst);
    156 		if (i1 < 0)
    157 			goto error;
    158 		copy_constraint_dim_map(dst->eq[i1], src->eq[i], dim_map);
    159 	}
    160 
    161 	for (i = 0; i < src->n_ineq; ++i) {
    162 		int i1 = isl_basic_map_alloc_inequality(dst);
    163 		if (i1 < 0)
    164 			goto error;
    165 		copy_constraint_dim_map(dst->ineq[i1], src->ineq[i], dim_map);
    166 	}
    167 
    168 	for (i = 0; i < src->n_div; ++i) {
    169 		int i1 = isl_basic_map_alloc_div(dst);
    170 		if (i1 < 0)
    171 			goto error;
    172 		copy_div_dim_map(dst->div[i1], src->div[i], dim_map);
    173 	}
    174 
    175 	isl_dim_map_free(dim_map);
    176 	isl_basic_map_free(src);
    177 
    178 	return dst;
    179 error:
    180 	isl_dim_map_free(dim_map);
    181 	isl_basic_map_free(src);
    182 	isl_basic_map_free(dst);
    183 	return NULL;
    184 }
    185 
    186 __isl_give isl_basic_set *isl_basic_set_add_constraints_dim_map(
    187 	__isl_take isl_basic_set *dst, __isl_take isl_basic_set *src,
    188 	__isl_take isl_dim_map *dim_map)
    189 {
    190 	return isl_basic_map_add_constraints_dim_map(dst, src, dim_map);
    191 }
    192 
    193 /* Extend the given dim_map with mappings for the divs in bmap.
    194  */
    195 __isl_give isl_dim_map *isl_dim_map_extend(__isl_keep isl_dim_map *dim_map,
    196 	__isl_keep isl_basic_map *bmap)
    197 {
    198 	int i;
    199 	struct isl_dim_map *res;
    200 	int offset;
    201 
    202 	if (!dim_map)
    203 		return NULL;
    204 
    205 	offset = isl_basic_map_offset(bmap, isl_dim_div);
    206 
    207 	res = isl_dim_map_alloc(bmap->ctx, dim_map->len - 1 + bmap->n_div);
    208 	if (!res)
    209 		return NULL;
    210 
    211 	for (i = 0; i < dim_map->len; ++i)
    212 		res->m[i] = dim_map->m[i];
    213 	for (i = 0; i < bmap->n_div; ++i) {
    214 		res->m[dim_map->len + i].pos = offset + i;
    215 		res->m[dim_map->len + i].sgn = 1;
    216 	}
    217 
    218 	return res;
    219 }
    220 
    221 /* Extract a dim_map from a reordering.
    222  * We essentially need to reverse the mapping, and add an offset
    223  * of 1 for the constant term.
    224  */
    225 __isl_give isl_dim_map *isl_dim_map_from_reordering(
    226 	__isl_keep isl_reordering *exp)
    227 {
    228 	int i;
    229 	isl_ctx *ctx;
    230 	isl_size dim;
    231 	isl_space *space;
    232 	struct isl_dim_map *dim_map;
    233 
    234 	if (!exp)
    235 		return NULL;
    236 
    237 	ctx = isl_reordering_get_ctx(exp);
    238 	space = isl_reordering_peek_space(exp);
    239 	dim = isl_space_dim(space, isl_dim_all);
    240 	if (dim < 0)
    241 		return NULL;
    242 	dim_map = isl_dim_map_alloc(ctx, dim);
    243 	if (!dim_map)
    244 		return NULL;
    245 
    246 	for (i = 0; i < exp->src_len; ++i) {
    247 		dim_map->m[1 + exp->pos[i]].pos = 1 + i;
    248 		dim_map->m[1 + exp->pos[i]].sgn = 1;
    249 	}
    250 
    251 	return dim_map;
    252 }
    253