isl_reordering.c

Go to the documentation of this file.

/*
 * Copyright 2010      INRIA Saclay
 *
 * Use of this software is governed by the MIT license
 *
 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
 * 91893 Orsay, France
 */
 
#include <isl_ctx_private.h>
#include <isl/id.h>
#include <isl_space_private.h>
#include <isl_reordering.h>
 
/* Create a new reordering description based on
 * the number of source dimensions "src_len" and
 * (an initial value for) the number of target dimensions "dst_len".
 *
 * The caller still needs to fill in the space field and
 * possibly adjust the target dimensionality if this is not known yet
 * when this function is called.
 */
__isl_give isl_reordering *isl_reordering_alloc(isl_ctx *ctx, int src_len,
  int dst_len)
{
  isl_reordering *exp;
 
  exp = isl_alloc(ctx, struct isl_reordering,
    sizeof(struct isl_reordering) + (src_len - 1) * sizeof(int));
  if (!exp)
    return NULL;
 
  exp->ref = 1;
  exp->src_len = src_len;
  exp->dst_len = dst_len;
  exp->space = NULL;
 
  return exp;
}
 
/* Set r->dst_len to the total dimensionality of r->space.
 */
static __isl_give isl_reordering *isl_reordering_set_dst_len_from_space(
  __isl_take isl_reordering *r)
{
  isl_size n;
 
  if (!r)
    return NULL;
 
  n = isl_space_dim(r->space, isl_dim_all);
  if (n < 0)
    return isl_reordering_free(r);
  r->dst_len = n;
  return r;
}
 
__isl_give isl_reordering *isl_reordering_copy(__isl_keep isl_reordering *exp)
{
  if (!exp)
    return NULL;
 
  exp->ref++;
  return exp;
}
 
__isl_give isl_reordering *isl_reordering_dup(__isl_keep isl_reordering *r)
{
  int i;
  isl_reordering *dup;
 
  if (!r)
    return NULL;
 
  dup = isl_reordering_alloc(isl_reordering_get_ctx(r),
            r->src_len, r->dst_len);
  if (!dup)
    return NULL;
 
  dup->space = isl_reordering_get_space(r);
  if (!dup->space)
    return isl_reordering_free(dup);
  for (i = 0; i < dup->src_len; ++i)
    dup->pos[i] = r->pos[i];
 
  return dup;
}
 
__isl_give isl_reordering *isl_reordering_cow(__isl_take isl_reordering *r)
{
  if (!r)
    return NULL;
 
  if (r->ref == 1)
    return r;
  r->ref--;
  return isl_reordering_dup(r);
}
 
__isl_null isl_reordering *isl_reordering_free(__isl_take isl_reordering *exp)
{
  if (!exp)
    return NULL;
 
  if (--exp->ref > 0)
    return NULL;
 
  isl_space_free(exp->space);
  free(exp);
  return NULL;
}
 
/* Return the isl_ctx to which "r" belongs.
 */
isl_ctx *isl_reordering_get_ctx(__isl_keep isl_reordering *r)
{
  return isl_space_get_ctx(isl_reordering_peek_space(r));
}
 
/* Return the space of "r".
 */
__isl_keep isl_space *isl_reordering_peek_space(__isl_keep isl_reordering *r)
{
  if (!r)
    return NULL;
  return r->space;
}
 
/* Return a copy of the space of "r".
 */
__isl_give isl_space *isl_reordering_get_space(__isl_keep isl_reordering *r)
{
  return isl_space_copy(isl_reordering_peek_space(r));
}
 
/* Construct a reordering that maps the parameters of "alignee"
 * to the corresponding parameters in a new dimension specification
 * that has the parameters of "aligner" first, followed by
 * any remaining parameters of "alignee" that do not occur in "aligner".
 * The other dimensions of "alignee" are mapped to subsequent positions
 * in order.
 */
__isl_give isl_reordering *isl_parameter_alignment_reordering(
  __isl_keep isl_space *alignee, __isl_keep isl_space *aligner)
{
  int i, j, offset;
  isl_ctx *ctx;
  isl_reordering *exp;
  isl_size dim, n_alignee, n_aligner;
 
  dim = isl_space_dim(alignee, isl_dim_all);
  n_alignee = isl_space_dim(alignee, isl_dim_param);
  n_aligner = isl_space_dim(aligner, isl_dim_param);
  if (dim < 0 || n_alignee < 0 || n_aligner < 0)
    return NULL;
 
  ctx = isl_space_get_ctx(alignee);
  exp = isl_reordering_alloc(ctx, dim, dim);
  if (!exp)
    return NULL;
 
  exp->space = isl_space_replace_params(isl_space_copy(alignee), aligner);
 
  for (i = 0; i < n_alignee; ++i) {
    isl_id *id_i;
    id_i = isl_space_get_dim_id(alignee, isl_dim_param, i);
    if (!id_i)
      isl_die(ctx, isl_error_invalid,
        "cannot align unnamed parameters", goto error);
    for (j = 0; j < n_aligner; ++j) {
      isl_id *id_j;
      id_j = isl_space_get_dim_id(aligner, isl_dim_param, j);
      isl_id_free(id_j);
      if (id_i == id_j)
        break;
    }
    if (j < n_aligner) {
      exp->pos[i] = j;
      isl_id_free(id_i);
    } else {
      isl_size pos;
      pos = isl_space_dim(exp->space, isl_dim_param);
      if (pos < 0)
        exp->space = isl_space_free(exp->space);
      exp->space = isl_space_add_dims(exp->space,
            isl_dim_param, 1);
      exp->space = isl_space_set_dim_id(exp->space,
            isl_dim_param, pos, id_i);
      exp->pos[i] = pos;
    }
  }
 
  exp = isl_reordering_set_dst_len_from_space(exp);
  if (!exp)
    return NULL;
 
  offset = exp->dst_len - exp->src_len;
  for (i = n_alignee; i < dim; ++i)
    exp->pos[i] = offset + i;
 
  return exp;
error:
  isl_reordering_free(exp);
  return NULL;
}
 
/* Return a reordering that moves the parameters identified by
 * the elements of "tuple" to a domain tuple inserted into "space".
 * The parameters that remain, are moved from their original positions
 * in the list of parameters to their new positions in this list.
 * The parameters that get removed, are moved to the corresponding
 * positions in the new domain.  Note that these set dimensions
 * do not necessarily need to appear as parameters in "space".
 * Any other dimensions are shifted by the number of extra dimensions
 * introduced, i.e., the number of dimensions in the new domain
 * that did not appear as parameters in "space".
 */
__isl_give isl_reordering *isl_reordering_unbind_params_insert_domain(
  __isl_keep isl_space *space, __isl_keep isl_multi_id *tuple)
{
  int i, n;
  int offset, first;
  isl_size dim;
  isl_ctx *ctx;
  isl_reordering *r;
 
  dim = isl_space_dim(space, isl_dim_all);
  if (dim < 0 || !tuple)
    return NULL;
 
  ctx = isl_space_get_ctx(space);
  r = isl_reordering_alloc(ctx, dim, dim);
  if (!r)
    return NULL;
 
  r->space = isl_space_copy(space);
  r->space = isl_space_unbind_params_insert_domain(r->space, tuple);
  if (!r->space)
    return isl_reordering_free(r);
 
  n = isl_space_dim(r->space, isl_dim_param);
  for (i = 0; i < n; ++i) {
    int pos;
    isl_id *id;
 
    id = isl_space_get_dim_id(r->space, isl_dim_param, i);
    if (!id)
      return isl_reordering_free(r);
    pos = isl_space_find_dim_by_id(space, isl_dim_param, id);
    isl_id_free(id);
    r->pos[pos] = i;
  }
 
  offset = isl_space_dim(r->space, isl_dim_param);
  n = isl_multi_id_size(tuple);
  for (i = 0; i < n; ++i) {
    int pos;
    isl_id *id;
 
    id = isl_multi_id_get_id(tuple, i);
    if (!id)
      return isl_reordering_free(r);
    pos = isl_space_find_dim_by_id(space, isl_dim_param, id);
    isl_id_free(id);
    if (pos < 0)
      continue;
    r->pos[pos] = offset + i;
  }
 
  offset = isl_space_dim(r->space, isl_dim_all) - dim;
  first = isl_space_dim(space, isl_dim_param);
  n = dim - first;
  for (i = 0; i < n; ++i)
    r->pos[first + i] = first + offset + i;
 
  return isl_reordering_set_dst_len_from_space(r);
}
 
__isl_give isl_reordering *isl_reordering_extend(__isl_take isl_reordering *exp,
  unsigned extra)
{
  int i;
  isl_ctx *ctx;
  isl_reordering *res;
  int offset;
 
  if (!exp)
    return NULL;
  if (extra == 0)
    return exp;
 
  ctx = isl_reordering_get_ctx(exp);
  offset = exp->dst_len - exp->src_len;
  res = isl_reordering_alloc(ctx, exp->src_len + extra,
          exp->dst_len + extra);
  if (!res)
    goto error;
  res->space = isl_reordering_get_space(exp);
  for (i = 0; i < exp->src_len; ++i)
    res->pos[i] = exp->pos[i];
  for (i = exp->src_len; i < res->src_len; ++i)
    res->pos[i] = offset + i;
 
  isl_reordering_free(exp);
 
  return res;
error:
  isl_reordering_free(exp);
  return NULL;
}
 
__isl_give isl_reordering *isl_reordering_extend_space(
  __isl_take isl_reordering *exp, __isl_take isl_space *space)
{
  isl_space *exp_space;
  isl_reordering *res;
  isl_size dim;
 
  dim = isl_space_dim(space, isl_dim_all);
  if (!exp || dim < 0)
    goto error;
 
  res = isl_reordering_extend(isl_reordering_copy(exp),
            dim - exp->src_len);
  res = isl_reordering_cow(res);
  if (!res)
    goto error;
  isl_space_free(res->space);
  exp_space = isl_reordering_peek_space(exp);
  res->space = isl_space_replace_params(space, exp_space);
 
  isl_reordering_free(exp);
 
  if (!res->space)
    return isl_reordering_free(res);
 
  return res;
error:
  isl_reordering_free(exp);
  isl_space_free(space);
  return NULL;
}
 
void isl_reordering_dump(__isl_keep isl_reordering *exp)
{
  int i;
 
  isl_space_dump(exp->space);
  for (i = 0; i < exp->src_len; ++i)
    fprintf(stderr, "%d -> %d; ", i, exp->pos[i]);
  fprintf(stderr, "\n");
}