253 lines · c
1/*2 * Copyright 2008-2009 Katholieke Universiteit Leuven3 * Copyright 2010-2011 INRIA Saclay4 *5 * Use of this software is governed by the MIT license6 *7 * Written by Sven Verdoolaege, K.U.Leuven, Departement8 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium9 * 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 18struct isl_dim_map_entry {19 int pos;20 int sgn;21};22 23/* Maps dst positions to src positions */24struct 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 53void 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 70void 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 unsigned src_pos;76 77 if (!dim_map || !space)78 return;79 80 src_pos = 1 + isl_space_offset(space, type);81 for (i = 0; i < n; ++i) {82 dim_map->m[1 + dst_pos + i].pos = src_pos + first + i;83 dim_map->m[1 + dst_pos + i].sgn = 1;84 }85}86 87void 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 97void 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 113void 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 123static 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 else134 isl_int_neg(dst[i], src[dim_map->m[i].pos]);135 }136}137 138static 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;179error: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 offset223 * 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