isl_reordering.c

   1 /*
   2  * Copyright 2010      INRIA Saclay
   3  *
   4  * Use of this software is governed by the MIT license
   5  *
   6  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   7  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   8  * 91893 Orsay, France
   9  */
  10
  11 #include <isl_ctx_private.h>
  12 #include <isl/id.h>
  13 #include <isl_space_private.h>
  14 #include <isl_reordering.h>
  15
  16 __isl_give isl_reordering *isl_reordering_alloc(isl_ctx *ctx, int len)
  17 {
  18         isl_reordering *exp;
  19
  20         exp = isl_alloc(ctx, struct isl_reordering,
  21                         sizeof(struct isl_reordering) + (len - 1) * sizeof(int));
  22         if (!exp)
  23                 return NULL;
  24
  25         exp->ref = 1;
  26         exp->len = len;
  27         exp->space = NULL;
  28
  29         return exp;
  30 }
  31
  32 __isl_give isl_reordering *isl_reordering_copy(__isl_keep isl_reordering *exp)
  33 {
  34         if (!exp)
  35                 return NULL;
  36
  37         exp->ref++;
  38         return exp;
  39 }
  40
  41 __isl_give isl_reordering *isl_reordering_dup(__isl_keep isl_reordering *r)
  42 {
  43         int i;
  44         isl_reordering *dup;
  45
  46         if (!r)
  47                 return NULL;
  48
  49         dup = isl_reordering_alloc(isl_reordering_get_ctx(r), r->len);
  50         if (!dup)
  51                 return NULL;
  52
  53         dup->space = isl_reordering_get_space(r);
  54         if (!dup->space)
  55                 return isl_reordering_free(dup);
  56         for (i = 0; i < dup->len; ++i)
  57                 dup->pos[i] = r->pos[i];
  58
  59         return dup;
  60 }
  61
  62 __isl_give isl_reordering *isl_reordering_cow(__isl_take isl_reordering *r)
  63 {
  64         if (!r)
  65                 return NULL;
  66
  67         if (r->ref == 1)
  68                 return r;
  69         r->ref--;
  70         return isl_reordering_dup(r);
  71 }
  72
  73 __isl_null isl_reordering *isl_reordering_free(__isl_take isl_reordering *exp)
  74 {
  75         if (!exp)
  76                 return NULL;
  77
  78         if (--exp->ref > 0)
  79                 return NULL;
  80
  81         isl_space_free(exp->space);
  82         free(exp);
  83         return NULL;
  84 }
  85
  86 /* Return the isl_ctx to which "r" belongs.
  87  */
  88 isl_ctx *isl_reordering_get_ctx(__isl_keep isl_reordering *r)
  89 {
  90         return isl_space_get_ctx(isl_reordering_peek_space(r));
  91 }
  92
  93 /* Return the space of "r".
  94  */
  95 __isl_keep isl_space *isl_reordering_peek_space(__isl_keep isl_reordering *r)
  96 {
  97         if (!r)
  98                 return NULL;
  99         return r->space;
 100 }
 101
 102 /* Return a copy of the space of "r".
 103  */
 104 __isl_give isl_space *isl_reordering_get_space(__isl_keep isl_reordering *r)
 105 {
 106         return isl_space_copy(isl_reordering_peek_space(r));
 107 }
 108
 109 /* Construct a reordering that maps the parameters of "alignee"
 110  * to the corresponding parameters in a new dimension specification
 111  * that has the parameters of "aligner" first, followed by
 112  * any remaining parameters of "alignee" that do not occur in "aligner".
 113  */
 114 __isl_give isl_reordering *isl_parameter_alignment_reordering(
 115         __isl_keep isl_space *alignee, __isl_keep isl_space *aligner)
 116 {
 117         int i, j;
 118         isl_reordering *exp;
 119
 120         if (!alignee || !aligner)
 121                 return NULL;
 122
 123         exp = isl_reordering_alloc(alignee->ctx, alignee->nparam);
 124         if (!exp)
 125                 return NULL;
 126
 127         exp->space = isl_space_params(isl_space_copy(aligner));
 128
 129         for (i = 0; i < alignee->nparam; ++i) {
 130                 isl_id *id_i;
 131                 id_i = isl_space_get_dim_id(alignee, isl_dim_param, i);
 132                 if (!id_i)
 133                         isl_die(alignee->ctx, isl_error_invalid,
 134                                 "cannot align unnamed parameters", goto error);
 135                 for (j = 0; j < aligner->nparam; ++j) {
 136                         isl_id *id_j;
 137                         id_j = isl_space_get_dim_id(aligner, isl_dim_param, j);
 138                         isl_id_free(id_j);
 139                         if (id_i == id_j)
 140                                 break;
 141                 }
 142                 if (j < aligner->nparam) {
 143                         exp->pos[i] = j;
 144                         isl_id_free(id_i);
 145                 } else {
 146                         isl_size pos;
 147                         pos = isl_space_dim(exp->space, isl_dim_param);
 148                         if (pos < 0)
 149                                 exp->space = isl_space_free(exp->space);
 150                         exp->space = isl_space_add_dims(exp->space,
 151                                                 isl_dim_param, 1);
 152                         exp->space = isl_space_set_dim_id(exp->space,
 153                                                 isl_dim_param, pos, id_i);
 154                         exp->pos[i] = pos;
 155                 }
 156         }
 157
 158         if (!exp->space)
 159                 return isl_reordering_free(exp);
 160         return exp;
 161 error:
 162         isl_reordering_free(exp);
 163         return NULL;
 164 }
 165
 166 /* Return a reordering that moves the parameters identified by
 167  * the elements of "tuple" to a domain tuple inserted into "space".
 168  * The parameters that remain, are moved from their original positions
 169  * in the list of parameters to their new positions in this list.
 170  * The parameters that get removed, are moved to the corresponding
 171  * positions in the new domain.  Note that these set dimensions
 172  * do not necessarily need to appear as parameters in "space".
 173  * Any other dimensions are shifted by the number of extra dimensions
 174  * introduced, i.e., the number of dimensions in the new domain
 175  * that did not appear as parameters in "space".
 176  */
 177 __isl_give isl_reordering *isl_reordering_unbind_params_insert_domain(
 178         __isl_keep isl_space *space, __isl_keep isl_multi_id *tuple)
 179 {
 180         int i, n;
 181         int offset, first;
 182         isl_ctx *ctx;
 183         isl_reordering *r;
 184
 185         if (!space || !tuple)
 186                 return NULL;
 187
 188         ctx = isl_space_get_ctx(space);
 189         r = isl_reordering_alloc(ctx, isl_space_dim(space, isl_dim_all));
 190         if (!r)
 191                 return NULL;
 192
 193         r->space = isl_space_copy(space);
 194         r->space = isl_space_unbind_params_insert_domain(r->space, tuple);
 195         if (!r->space)
 196                 return isl_reordering_free(r);
 197
 198         n = isl_space_dim(r->space, isl_dim_param);
 199         for (i = 0; i < n; ++i) {
 200                 int pos;
 201                 isl_id *id;
 202
 203                 id = isl_space_get_dim_id(r->space, isl_dim_param, i);
 204                 if (!id)
 205                         return isl_reordering_free(r);
 206                 pos = isl_space_find_dim_by_id(space, isl_dim_param, id);
 207                 isl_id_free(id);
 208                 r->pos[pos] = i;
 209         }
 210
 211         offset = isl_space_dim(r->space, isl_dim_param);
 212         n = isl_multi_id_size(tuple);
 213         for (i = 0; i < n; ++i) {
 214                 int pos;
 215                 isl_id *id;
 216
 217                 id = isl_multi_id_get_id(tuple, i);
 218                 if (!id)
 219                         return isl_reordering_free(r);
 220                 pos = isl_space_find_dim_by_id(space, isl_dim_param, id);
 221                 isl_id_free(id);
 222                 if (pos < 0)
 223                         continue;
 224                 r->pos[pos] = offset + i;
 225         }
 226
 227         offset = isl_space_dim(r->space, isl_dim_all) - r->len;
 228         first = isl_space_dim(space, isl_dim_param);
 229         n = r->len - first;
 230         for (i = 0; i < n; ++i)
 231                 r->pos[first + i] = first + offset + i;
 232
 233         return r;
 234 }
 235
 236 __isl_give isl_reordering *isl_reordering_extend(__isl_take isl_reordering *exp,
 237         unsigned extra)
 238 {
 239         int i;
 240         isl_ctx *ctx;
 241         isl_space *space;
 242         isl_reordering *res;
 243         int offset;
 244         isl_size dim;
 245
 246         if (!exp)
 247                 return NULL;
 248         if (extra == 0)
 249                 return exp;
 250
 251         ctx = isl_reordering_get_ctx(exp);
 252         space = isl_reordering_peek_space(exp);
 253         dim = isl_space_dim(space, isl_dim_all);
 254         if (dim < 0)
 255                 return isl_reordering_free(exp);
 256         offset = dim - exp->len;
 257         res = isl_reordering_alloc(ctx, exp->len + extra);
 258         if (!res)
 259                 goto error;
 260         res->space = isl_reordering_get_space(exp);
 261         for (i = 0; i < exp->len; ++i)
 262                 res->pos[i] = exp->pos[i];
 263         for (i = exp->len; i < res->len; ++i)
 264                 res->pos[i] = offset + i;
 265
 266         isl_reordering_free(exp);
 267
 268         return res;
 269 error:
 270         isl_reordering_free(exp);
 271         return NULL;
 272 }
 273
 274 __isl_give isl_reordering *isl_reordering_extend_space(
 275         __isl_take isl_reordering *exp, __isl_take isl_space *space)
 276 {
 277         isl_space *exp_space;
 278         isl_reordering *res;
 279         isl_size dim;
 280
 281         dim = isl_space_dim(space, isl_dim_all);
 282         if (!exp || dim < 0)
 283                 goto error;
 284
 285         res = isl_reordering_extend(isl_reordering_copy(exp), dim - exp->len);
 286         res = isl_reordering_cow(res);
 287         if (!res)
 288                 goto error;
 289         isl_space_free(res->space);
 290         exp_space = isl_reordering_peek_space(exp);
 291         res->space = isl_space_replace_params(space, exp_space);
 292
 293         isl_reordering_free(exp);
 294
 295         if (!res->space)
 296                 return isl_reordering_free(res);
 297
 298         return res;
 299 error:
 300         isl_reordering_free(exp);
 301         isl_space_free(space);
 302         return NULL;
 303 }
 304
 305 void isl_reordering_dump(__isl_keep isl_reordering *exp)
 306 {
 307         int i;
 308
 309         isl_space_dump(exp->space);
 310         for (i = 0; i < exp->len; ++i)
 311                 fprintf(stderr, "%d -> %d; ", i, exp->pos[i]);
 312         fprintf(stderr, "\n");
 313 }