isl_dim_map.c

   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         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
  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->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 }