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 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 45void isl_dim_map_range(__isl_keep isl_dim_map *dim_map, 46 unsigned dst_pos, unsigned dst_stride, 47 unsigned src_pos, unsigned src_stride, 48 unsigned n, int sign) 49{ 50 int i; 51 52 if (!dim_map) 53 return; 54 55 for (i = 0; i < n; ++i) { 56 unsigned d = 1 + dst_pos + dst_stride * i; 57 unsigned s = 1 + src_pos + src_stride * i; 58 dim_map->m[d].pos = s; 59 dim_map->m[d].sgn = sign; 60 } 61} 62 63void isl_dim_map_dim_range(__isl_keep isl_dim_map *dim_map, 64 __isl_keep isl_space *dim, enum isl_dim_type type, 65 unsigned first, unsigned n, unsigned dst_pos) 66{ 67 int i; 68 unsigned src_pos; 69 70 if (!dim_map || !dim) 71 return; 72 73 src_pos = 1 + isl_space_offset(dim, type); 74 for (i = 0; i < n; ++i) { 75 dim_map->m[1 + dst_pos + i].pos = src_pos + first + i; 76 dim_map->m[1 + dst_pos + i].sgn = 1; 77 } 78} 79 80void isl_dim_map_dim(__isl_keep isl_dim_map *dim_map, __isl_keep isl_space *dim, 81 enum isl_dim_type type, unsigned dst_pos) 82{ 83 isl_dim_map_dim_range(dim_map, dim, type, 84 0, isl_space_dim(dim, type), dst_pos); 85} 86 87void isl_dim_map_div(__isl_keep isl_dim_map *dim_map, 88 __isl_keep isl_basic_map *bmap, unsigned dst_pos) 89{ 90 int i; 91 unsigned src_pos; 92 93 if (!dim_map || !bmap) 94 return; 95 96 src_pos = 1 + isl_space_dim(bmap->dim, isl_dim_all); 97 for (i = 0; i < bmap->n_div; ++i) { 98 dim_map->m[1 + dst_pos + i].pos = src_pos + i; 99 dim_map->m[1 + dst_pos + i].sgn = 1; 100 } 101} 102 103void isl_dim_map_dump(struct isl_dim_map *dim_map) 104{ 105 int i; 106 107 for (i = 0; i < dim_map->len; ++i) 108 fprintf(stderr, "%d -> %d * %d; ", i, 109 dim_map->m[i].sgn, dim_map->m[i].pos); 110 fprintf(stderr, "\n"); 111} 112 113static void copy_constraint_dim_map(isl_int *dst, isl_int *src, 114 struct isl_dim_map *dim_map) 115{ 116 int i; 117 118 for (i = 0; i < dim_map->len; ++i) { 119 if (dim_map->m[i].sgn == 0) 120 isl_int_set_si(dst[i], 0); 121 else if (dim_map->m[i].sgn > 0) 122 isl_int_set(dst[i], src[dim_map->m[i].pos]); 123 else 124 isl_int_neg(dst[i], src[dim_map->m[i].pos]); 125 } 126} 127 128static void copy_div_dim_map(isl_int *dst, isl_int *src, 129 struct isl_dim_map *dim_map) 130{ 131 isl_int_set(dst[0], src[0]); 132 copy_constraint_dim_map(dst+1, src+1, dim_map); 133} 134 135__isl_give isl_basic_map *isl_basic_map_add_constraints_dim_map( 136 __isl_take isl_basic_map *dst, __isl_take isl_basic_map *src, 137 __isl_take isl_dim_map *dim_map) 138{ 139 int i; 140 141 if (!src || !dst || !dim_map) 142 goto error; 143 144 for (i = 0; i < src->n_eq; ++i) { 145 int i1 = isl_basic_map_alloc_equality(dst); 146 if (i1 < 0) 147 goto error; 148 copy_constraint_dim_map(dst->eq[i1], src->eq[i], dim_map); 149 } 150 151 for (i = 0; i < src->n_ineq; ++i) { 152 int i1 = isl_basic_map_alloc_inequality(dst); 153 if (i1 < 0) 154 goto error; 155 copy_constraint_dim_map(dst->ineq[i1], src->ineq[i], dim_map); 156 } 157 158 for (i = 0; i < src->n_div; ++i) { 159 int i1 = isl_basic_map_alloc_div(dst); 160 if (i1 < 0) 161 goto error; 162 copy_div_dim_map(dst->div[i1], src->div[i], dim_map); 163 } 164 165 free(dim_map); 166 isl_basic_map_free(src); 167 168 return dst; 169error: 170 free(dim_map); 171 isl_basic_map_free(src); 172 isl_basic_map_free(dst); 173 return NULL; 174} 175 176__isl_give isl_basic_set *isl_basic_set_add_constraints_dim_map( 177 __isl_take isl_basic_set *dst, __isl_take isl_basic_set *src, 178 __isl_take isl_dim_map *dim_map) 179{ 180 return isl_basic_map_add_constraints_dim_map(dst, src, dim_map); 181} 182 183/* Extend the given dim_map with mappings for the divs in bmap. 184 */ 185__isl_give isl_dim_map *isl_dim_map_extend(__isl_keep isl_dim_map *dim_map, 186 __isl_keep isl_basic_map *bmap) 187{ 188 int i; 189 struct isl_dim_map *res; 190 int offset; 191 192 offset = isl_basic_map_offset(bmap, isl_dim_div); 193 194 res = isl_dim_map_alloc(bmap->ctx, dim_map->len - 1 + bmap->n_div); 195 if (!res) 196 return NULL; 197 198 for (i = 0; i < dim_map->len; ++i) 199 res->m[i] = dim_map->m[i]; 200 for (i = 0; i < bmap->n_div; ++i) { 201 res->m[dim_map->len + i].pos = offset + i; 202 res->m[dim_map->len + i].sgn = 1; 203 } 204 205 return res; 206} 207 208/* Extract a dim_map from a reordering. 209 * We essentially need to reverse the mapping, and add an offset 210 * of 1 for the constant term. 211 */ 212__isl_give isl_dim_map *isl_dim_map_from_reordering( 213 __isl_keep isl_reordering *exp) 214{ 215 int i; 216 isl_ctx *ctx; 217 struct isl_dim_map *dim_map; 218 219 if (!exp) 220 return NULL; 221 222 ctx = isl_space_get_ctx(exp->dim); 223 dim_map = isl_dim_map_alloc(ctx, isl_space_dim(exp->dim, isl_dim_all)); 224 if (!dim_map) 225 return NULL; 226 227 for (i = 0; i < exp->len; ++i) { 228 dim_map->m[1 + exp->pos[i]].pos = 1 + i; 229 dim_map->m[1 + exp->pos[i]].sgn = 1; 230 } 231 232 return dim_map; 233} 234