isl_dim_map.c

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