133410Swosch/* 233410Swosch * Copyright 2008-2009 Katholieke Universiteit Leuven 354232Swosch * Copyright 2010-2011 INRIA Saclay 433410Swosch * 554232Swosch * Use of this software is governed by the MIT license 654232Swosch * 754232Swosch * Written by Sven Verdoolaege, K.U.Leuven, Departement 854232Swosch * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium 954232Swosch * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite, 1054232Swosch * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France 1154232Swosch */ 1254232Swosch 1354232Swosch#include <isl_map_private.h> 1454232Swosch#include <isl_space_private.h> 1554232Swosch#include <isl_dim_map.h> 1654232Swosch#include <isl_reordering.h> 1754232Swosch 1854232Swoschstruct isl_dim_map_entry { 1954232Swosch int pos; 2054232Swosch int sgn; 2154232Swosch}; 2254232Swosch 2354232Swosch/* Maps dst positions to src positions */ 2454232Swoschstruct isl_dim_map { 2554232Swosch unsigned len; 2654232Swosch struct isl_dim_map_entry m[1]; 2757712Ssheldonh}; 2833410Swosch 2950477Speter__isl_give isl_dim_map *isl_dim_map_alloc(isl_ctx *ctx, unsigned len) 3033410Swosch{ 3133410Swosch int i; 3233410Swosch struct isl_dim_map *dim_map; 3333410Swosch dim_map = isl_alloc(ctx, struct isl_dim_map, 3433410Swosch sizeof(struct isl_dim_map) + len * sizeof(struct isl_dim_map_entry)); 3533410Swosch if (!dim_map) 3633410Swosch return NULL; 3733410Swosch dim_map->len = 1 + len; 3833410Swosch dim_map->m[0].pos = 0; 3933410Swosch dim_map->m[0].sgn = 1; 4033410Swosch for (i = 0; i < len; ++i) 4133410Swosch dim_map->m[1 + i].sgn = 0; 4233410Swosch return dim_map; 4333410Swosch} 4433410Swosch 4533410Swosch/* Free "dim_map" and return NULL. 4633410Swosch */ 47103910Sache__isl_null isl_dim_map *isl_dim_map_free(__isl_take isl_dim_map *dim_map) 4833410Swosch{ 4933410Swosch free(dim_map); 5033410Swosch return NULL; 5133410Swosch} 5233410Swosch 5333410Swoschvoid isl_dim_map_range(__isl_keep isl_dim_map *dim_map, 5433410Swosch unsigned dst_pos, int dst_stride, unsigned src_pos, int src_stride, 5533410Swosch unsigned n, int sign) 5633410Swosch{ 5757697Ssheldonh int i; 5833410Swosch 5933410Swosch if (!dim_map) 6033410Swosch return; 6133410Swosch 6233410Swosch 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 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 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 else 134 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 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