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 void 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
  63 void 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
  80 void 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
  87 void 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
 103 void 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
 113 static 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
 128 static 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;
 169 error:
 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         if (!dim_map)
 193                 return NULL;
 194
 195         offset = isl_basic_map_offset(bmap, isl_dim_div);
 196
 197         res = isl_dim_map_alloc(bmap->ctx, dim_map->len - 1 + bmap->n_div);
 198         if (!res)
 199                 return NULL;
 200
 201         for (i = 0; i < dim_map->len; ++i)
 202                 res->m[i] = dim_map->m[i];
 203         for (i = 0; i < bmap->n_div; ++i) {
 204                 res->m[dim_map->len + i].pos = offset + i;
 205                 res->m[dim_map->len + i].sgn = 1;
 206         }
 207
 208         return res;
 209 }
 210
 211 /* Extract a dim_map from a reordering.
 212  * We essentially need to reverse the mapping, and add an offset
 213  * of 1 for the constant term.
 214  */
 215 __isl_give isl_dim_map *isl_dim_map_from_reordering(
 216         __isl_keep isl_reordering *exp)
 217 {
 218         int i;
 219         isl_ctx *ctx;
 220         struct isl_dim_map *dim_map;
 221
 222         if (!exp)
 223                 return NULL;
 224
 225         ctx = isl_space_get_ctx(exp->dim);
 226         dim_map = isl_dim_map_alloc(ctx, isl_space_dim(exp->dim, isl_dim_all));
 227         if (!dim_map)
 228                 return NULL;
 229
 230         for (i = 0; i < exp->len; ++i) {
 231                 dim_map->m[1 + exp->pos[i]].pos = 1 + i;
 232                 dim_map->m[1 + exp->pos[i]].sgn = 1;
 233         }
 234
 235         return dim_map;
 236 }