polly/lib/External/isl/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 /* Create a new reordering description based on
  17  * the number of source dimensions "src_len" and
  18  * (an initial value for) the number of target dimensions "dst_len".
  19  *
  20  * The caller still needs to fill in the space field and
  21  * possibly adjust the target dimensionality if this is not known yet
  22  * when this function is called.
  23  */
  24 __isl_give isl_reordering *isl_reordering_alloc(isl_ctx *ctx, int src_len,
  25         int dst_len)
  26 {
  27         isl_reordering *exp;
  28
  29         exp = isl_alloc(ctx, struct isl_reordering,
  30                 sizeof(struct isl_reordering) + (src_len - 1) * sizeof(int));
  31         if (!exp)
  32                 return NULL;
  33
  34         exp->ref = 1;
  35         exp->src_len = src_len;
  36         exp->dst_len = dst_len;
  37         exp->space = NULL;
  38
  39         return exp;
  40 }
  41
  42 /* Set r->dst_len to the total dimensionality of r->space.
  43  */
  44 static __isl_give isl_reordering *isl_reordering_set_dst_len_from_space(
  45         __isl_take isl_reordering *r)
  46 {
  47         isl_size n;
  48
  49         if (!r)
  50                 return NULL;
  51
  52         n = isl_space_dim(r->space, isl_dim_all);
  53         if (n < 0)
  54                 return isl_reordering_free(r);
  55         r->dst_len = n;
  56         return r;
  57 }
  58
  59 __isl_give isl_reordering *isl_reordering_copy(__isl_keep isl_reordering *exp)
  60 {
  61         if (!exp)
  62                 return NULL;
  63
  64         exp->ref++;
  65         return exp;
  66 }
  67
  68 __isl_give isl_reordering *isl_reordering_dup(__isl_keep isl_reordering *r)
  69 {
  70         int i;
  71         isl_reordering *dup;
  72
  73         if (!r)
  74                 return NULL;
  75
  76         dup = isl_reordering_alloc(isl_reordering_get_ctx(r),
  77                                     r->src_len, r->dst_len);
  78         if (!dup)
  79                 return NULL;
  80
  81         dup->space = isl_reordering_get_space(r);
  82         if (!dup->space)
  83                 return isl_reordering_free(dup);
  84         for (i = 0; i < dup->src_len; ++i)
  85                 dup->pos[i] = r->pos[i];
  86
  87         return dup;
  88 }
  89
  90 __isl_give isl_reordering *isl_reordering_cow(__isl_take isl_reordering *r)
  91 {
  92         if (!r)
  93                 return NULL;
  94
  95         if (r->ref == 1)
  96                 return r;
  97         r->ref--;
  98         return isl_reordering_dup(r);
  99 }
 100
 101 __isl_null isl_reordering *isl_reordering_free(__isl_take isl_reordering *exp)
 102 {
 103         if (!exp)
 104                 return NULL;
 105
 106         if (--exp->ref > 0)
 107                 return NULL;
 108
 109         isl_space_free(exp->space);
 110         free(exp);
 111         return NULL;
 112 }
 113
 114 /* Return the isl_ctx to which "r" belongs.
 115  */
 116 isl_ctx *isl_reordering_get_ctx(__isl_keep isl_reordering *r)
 117 {
 118         return isl_space_get_ctx(isl_reordering_peek_space(r));
 119 }
 120
 121 /* Return the space of "r".
 122  */
 123 __isl_keep isl_space *isl_reordering_peek_space(__isl_keep isl_reordering *r)
 124 {
 125         if (!r)
 126                 return NULL;
 127         return r->space;
 128 }
 129
 130 /* Return a copy of the space of "r".
 131  */
 132 __isl_give isl_space *isl_reordering_get_space(__isl_keep isl_reordering *r)
 133 {
 134         return isl_space_copy(isl_reordering_peek_space(r));
 135 }
 136
 137 /* Construct a reordering that maps the parameters of "alignee"
 138  * to the corresponding parameters in a new dimension specification
 139  * that has the parameters of "aligner" first, followed by
 140  * any remaining parameters of "alignee" that do not occur in "aligner".
 141  * The other dimensions of "alignee" are mapped to subsequent positions
 142  * in order.
 143  */
 144 __isl_give isl_reordering *isl_parameter_alignment_reordering(
 145         __isl_keep isl_space *alignee, __isl_keep isl_space *aligner)
 146 {
 147         int i, j, offset;
 148         isl_ctx *ctx;
 149         isl_reordering *exp;
 150         isl_size dim, n_alignee, n_aligner;
 151
 152         dim = isl_space_dim(alignee, isl_dim_all);
 153         n_alignee = isl_space_dim(alignee, isl_dim_param);
 154         n_aligner = isl_space_dim(aligner, isl_dim_param);
 155         if (dim < 0 || n_alignee < 0 || n_aligner < 0)
 156                 return NULL;
 157
 158         ctx = isl_space_get_ctx(alignee);
 159         exp = isl_reordering_alloc(ctx, dim, dim);
 160         if (!exp)
 161                 return NULL;
 162
 163         exp->space = isl_space_replace_params(isl_space_copy(alignee), aligner);
 164
 165         for (i = 0; i < n_alignee; ++i) {
 166                 isl_id *id_i;
 167                 id_i = isl_space_get_dim_id(alignee, isl_dim_param, i);
 168                 if (!id_i)
 169                         isl_die(ctx, isl_error_invalid,
 170                                 "cannot align unnamed parameters", goto error);
 171                 for (j = 0; j < n_aligner; ++j) {
 172                         isl_id *id_j;
 173                         id_j = isl_space_get_dim_id(aligner, isl_dim_param, j);
 174                         isl_id_free(id_j);
 175                         if (id_i == id_j)
 176                                 break;
 177                 }
 178                 if (j < n_aligner) {
 179                         exp->pos[i] = j;
 180                         isl_id_free(id_i);
 181                 } else {
 182                         isl_size pos;
 183                         pos = isl_space_dim(exp->space, isl_dim_param);
 184                         if (pos < 0)
 185                                 exp->space = isl_space_free(exp->space);
 186                         exp->space = isl_space_add_dims(exp->space,
 187                                                 isl_dim_param, 1);
 188                         exp->space = isl_space_set_dim_id(exp->space,
 189                                                 isl_dim_param, pos, id_i);
 190                         exp->pos[i] = pos;
 191                 }
 192         }
 193
 194         exp = isl_reordering_set_dst_len_from_space(exp);
 195         if (!exp)
 196                 return NULL;
 197
 198         offset = exp->dst_len - exp->src_len;
 199         for (i = n_alignee; i < dim; ++i)
 200                 exp->pos[i] = offset + i;
 201
 202         return exp;
 203 error:
 204         isl_reordering_free(exp);
 205         return NULL;
 206 }
 207
 208 /* Return a reordering that moves the parameters identified by
 209  * the elements of "tuple" to a domain tuple inserted into "space".
 210  * The parameters that remain, are moved from their original positions
 211  * in the list of parameters to their new positions in this list.
 212  * The parameters that get removed, are moved to the corresponding
 213  * positions in the new domain.  Note that these set dimensions
 214  * do not necessarily need to appear as parameters in "space".
 215  * Any other dimensions are shifted by the number of extra dimensions
 216  * introduced, i.e., the number of dimensions in the new domain
 217  * that did not appear as parameters in "space".
 218  */
 219 __isl_give isl_reordering *isl_reordering_unbind_params_insert_domain(
 220         __isl_keep isl_space *space, __isl_keep isl_multi_id *tuple)
 221 {
 222         int i, n;
 223         int offset, first;
 224         isl_size dim;
 225         isl_ctx *ctx;
 226         isl_reordering *r;
 227
 228         dim = isl_space_dim(space, isl_dim_all);
 229         if (dim < 0 || !tuple)
 230                 return NULL;
 231
 232         ctx = isl_space_get_ctx(space);
 233         r = isl_reordering_alloc(ctx, dim, dim);
 234         if (!r)
 235                 return NULL;
 236
 237         r->space = isl_space_copy(space);
 238         r->space = isl_space_unbind_params_insert_domain(r->space, tuple);
 239         if (!r->space)
 240                 return isl_reordering_free(r);
 241
 242         n = isl_space_dim(r->space, isl_dim_param);
 243         for (i = 0; i < n; ++i) {
 244                 int pos;
 245                 isl_id *id;
 246
 247                 id = isl_space_get_dim_id(r->space, isl_dim_param, i);
 248                 if (!id)
 249                         return isl_reordering_free(r);
 250                 pos = isl_space_find_dim_by_id(space, isl_dim_param, id);
 251                 isl_id_free(id);
 252                 r->pos[pos] = i;
 253         }
 254
 255         offset = isl_space_dim(r->space, isl_dim_param);
 256         n = isl_multi_id_size(tuple);
 257         for (i = 0; i < n; ++i) {
 258                 int pos;
 259                 isl_id *id;
 260
 261                 id = isl_multi_id_get_id(tuple, i);
 262                 if (!id)
 263                         return isl_reordering_free(r);
 264                 pos = isl_space_find_dim_by_id(space, isl_dim_param, id);
 265                 isl_id_free(id);
 266                 if (pos < 0)
 267                         continue;
 268                 r->pos[pos] = offset + i;
 269         }
 270
 271         offset = isl_space_dim(r->space, isl_dim_all) - dim;
 272         first = isl_space_dim(space, isl_dim_param);
 273         n = dim - first;
 274         for (i = 0; i < n; ++i)
 275                 r->pos[first + i] = first + offset + i;
 276
 277         return isl_reordering_set_dst_len_from_space(r);
 278 }
 279
 280 __isl_give isl_reordering *isl_reordering_extend(__isl_take isl_reordering *exp,
 281         unsigned extra)
 282 {
 283         int i;
 284         isl_ctx *ctx;
 285         isl_reordering *res;
 286         int offset;
 287
 288         if (!exp)
 289                 return NULL;
 290         if (extra == 0)
 291                 return exp;
 292
 293         ctx = isl_reordering_get_ctx(exp);
 294         offset = exp->dst_len - exp->src_len;
 295         res = isl_reordering_alloc(ctx, exp->src_len + extra,
 296                                         exp->dst_len + extra);
 297         if (!res)
 298                 goto error;
 299         res->space = isl_reordering_get_space(exp);
 300         for (i = 0; i < exp->src_len; ++i)
 301                 res->pos[i] = exp->pos[i];
 302         for (i = exp->src_len; i < res->src_len; ++i)
 303                 res->pos[i] = offset + i;
 304
 305         isl_reordering_free(exp);
 306
 307         return res;
 308 error:
 309         isl_reordering_free(exp);
 310         return NULL;
 311 }
 312
 313 __isl_give isl_reordering *isl_reordering_extend_space(
 314         __isl_take isl_reordering *exp, __isl_take isl_space *space)
 315 {
 316         isl_space *exp_space;
 317         isl_reordering *res;
 318         isl_size dim;
 319
 320         dim = isl_space_dim(space, isl_dim_all);
 321         if (!exp || dim < 0)
 322                 goto error;
 323
 324         res = isl_reordering_extend(isl_reordering_copy(exp),
 325                                     dim - exp->src_len);
 326         res = isl_reordering_cow(res);
 327         if (!res)
 328                 goto error;
 329         isl_space_free(res->space);
 330         exp_space = isl_reordering_peek_space(exp);
 331         res->space = isl_space_replace_params(space, exp_space);
 332
 333         isl_reordering_free(exp);
 334
 335         if (!res->space)
 336                 return isl_reordering_free(res);
 337
 338         return res;
 339 error:
 340         isl_reordering_free(exp);
 341         isl_space_free(space);
 342         return NULL;
 343 }
 344
 345 void isl_reordering_dump(__isl_keep isl_reordering *exp)
 346 {
 347         int i;
 348
 349         isl_space_dump(exp->space);
 350         for (i = 0; i < exp->src_len; ++i)
 351                 fprintf(stderr, "%d -> %d; ", i, exp->pos[i]);
 352         fprintf(stderr, "\n");
 353 }