/*

 * Copyright 2012-2013 Ecole Normale Superieure

 *

 * Use of this software is governed by the MIT license

 *

 * Written by Sven Verdoolaege,

 * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France

 */

#include <isl/val.h>

#include <isl_map_private.h>

#include <isl_aff_private.h>

#include <isl/constraint.h>

#include <isl/set.h>

/* Stride information about a specific set dimension.

 * The values of the set dimension are equal to

 * "offset" plus a multiple of "stride".

 */

struct isl_stride_info {

  isl_val *stride;

  isl_aff *offset;

};

/* Return the ctx to which "si" belongs.

 */

isl_ctx *isl_stride_info_get_ctx(__isl_keep isl_stride_info *si)

{

  if (!si)

    return NULL;

  return isl_val_get_ctx(si->stride);

}

/* Free "si" and return NULL.

 */

__isl_null isl_stride_info *isl_stride_info_free(

  __isl_take isl_stride_info *si)

{

  if (!si)

    return NULL;

  isl_val_free(si->stride);

  isl_aff_free(si->offset);

  free(si);

  return NULL;

}

/* Construct an isl_stride_info object with given offset and stride.

 */

__isl_give isl_stride_info *isl_stride_info_alloc(

  __isl_take isl_val *stride, __isl_take isl_aff *offset)

{

  struct isl_stride_info *si;

  if (!stride || !offset)

    goto error;

  si = isl_alloc_type(isl_val_get_ctx(stride), struct isl_stride_info);

  if (!si)

    goto error;

  si->stride = stride;

  si->offset = offset;

  return si;

error:

  isl_val_free(stride);

  isl_aff_free(offset);

  return NULL;

}

/* Make a copy of "si" and return it.

 */

__isl_give isl_stride_info *isl_stride_info_copy(

  __isl_keep isl_stride_info *si)

{

  if (!si)

    return NULL;

  return isl_stride_info_alloc(isl_val_copy(si->stride),

    isl_aff_copy(si->offset));

}

/* Return the stride of "si".

 */

__isl_give isl_val *isl_stride_info_get_stride(__isl_keep isl_stride_info *si)

{

  if (!si)

    return NULL;

  return isl_val_copy(si->stride);

}

/* Return the offset of "si".

 */

__isl_give isl_aff *isl_stride_info_get_offset(__isl_keep isl_stride_info *si)

{

  if (!si)

    return NULL;

  return isl_aff_copy(si->offset);

}

/* Information used inside detect_stride.

 *

 * "pos" is the set dimension at which the stride is being determined.

 * "want_offset" is set if the offset should be computed.

 * "found" is set if some stride was found already.

 * "stride" and "offset" contain the (combined) stride and offset

 * found so far and are NULL when "found" is not set.

 * If "want_offset" is not set, then "offset" remains NULL.

 */

struct isl_detect_stride_data {

  int pos;

  int want_offset;

  int found;

  isl_val *stride;

  isl_aff *offset;

};

/* Set the stride and offset of data->pos to the given

 * value and expression.

 *

 * If we had already found a stride before, then the two strides

 * are combined into a single stride.

 *

 * In particular, if the new stride information is of the form

 *

 *  i = f + s (...)

 *

 * and the old stride information is of the form

 *

 *  i = f2 + s2 (...)

 *

 * then we compute the extended gcd of s and s2

 *

 *  a s + b s2 = g,

 *

 * with g = gcd(s,s2), multiply the first equation with t1 = b s2/g

 * and the second with t2 = a s1/g.

 * This results in

 *

 *  i = (b s2 + a s1)/g i = t1 f + t2 f2 + (s s2)/g (...)

 *

 * so that t1 f + t2 f2 is the combined offset and (s s2)/g = lcm(s,s2)

 * is the combined stride.

 */

static isl_stat set_stride(struct isl_detect_stride_data *data,

  __isl_take isl_val *stride, __isl_take isl_aff *offset)

{

  int pos;

  if (!stride || !offset)

    goto error;

  pos = data->pos;

  if (data->found) {

    isl_val *stride2, *a, *b, *g;

    isl_aff *offset2;

    stride2 = data->stride;

    g = isl_val_gcdext(isl_val_copy(stride), isl_val_copy(stride2),

          &a, &b);

    a = isl_val_mul(a, isl_val_copy(stride));

    a = isl_val_div(a, isl_val_copy(g));

    stride2 = isl_val_div(stride2, g);

    b = isl_val_mul(b, isl_val_copy(stride2));

    stride = isl_val_mul(stride, stride2);

    if (!data->want_offset) {

      isl_val_free(a);

      isl_val_free(b);

    } else {

      offset2 = data->offset;

      offset2 = isl_aff_scale_val(offset2, a);

      offset = isl_aff_scale_val(offset, b);

      offset = isl_aff_add(offset, offset2);

    }

  }

  data->found = 1;

  data->stride = stride;

  if (data->want_offset)

    data->offset = offset;

  else

    isl_aff_free(offset);

  if (!data->stride || (data->want_offset && !data->offset))

    return isl_stat_error;

  return isl_stat_ok;

error:

  isl_val_free(stride);

  isl_aff_free(offset);

  return isl_stat_error;

}

/* Check if constraint "c" imposes any stride on dimension data->pos

 * and, if so, update the stride information in "data".

 *

 * In order to impose a stride on the dimension, "c" needs to be an equality

 * and it needs to involve the dimension.  Note that "c" may also be

 * a div constraint and thus an inequality that we cannot use.

 *

 * Let c be of the form

 *

 *  h(p) + g * v * i + g * stride * f(alpha) = 0

 *

 * with h(p) an expression in terms of the parameters and other dimensions

 * and f(alpha) an expression in terms of the existentially quantified

 * variables.

 *

 * If "stride" is not zero and not one, then it represents a non-trivial stride

 * on "i".  We compute a and b such that

 *

 *  a v + b stride = 1

 *

 * We have

 *

 *  g v i = -h(p) + g stride f(alpha)

 *

 *  a g v i = -a h(p) + g stride f(alpha)

 *

 *  a g v i + b g stride i = -a h(p) + g stride * (...)

 *

 *  g i = -a h(p) + g stride * (...)

 *

 *  i = -a h(p)/g + stride * (...)

 *

 * The expression "-a h(p)/g" can therefore be used as offset.

 */

static isl_stat detect_stride(__isl_take isl_constraint *c, void *user)

{

  struct isl_detect_stride_data *data = user;

  int i, n_div;

  isl_ctx *ctx;

  isl_stat r = isl_stat_ok;

  isl_val *v, *stride, *m;

  isl_bool is_eq, relevant, has_stride;

  is_eq = isl_constraint_is_equality(c);

  relevant = isl_constraint_involves_dims(c, isl_dim_set, data->pos, 1);

  if (is_eq < 0 || relevant < 0)

    goto error;

  if (!is_eq || 
!relevant6.95k
) {

    isl_constraint_free(c);

    return isl_stat_ok;

  }

  ctx = isl_constraint_get_ctx(c);

  stride = isl_val_zero(ctx);

  n_div = isl_constraint_dim(c, isl_dim_div);

  for (i = 0; i < n_div; 
++i76
) {

    v = isl_constraint_get_coefficient_val(c, isl_dim_div, i);

    stride = isl_val_gcd(stride, v);

  }

  v = isl_constraint_get_coefficient_val(c, isl_dim_set, data->pos);

  m = isl_val_gcd(isl_val_copy(stride), isl_val_copy(v));

  stride = isl_val_div(stride, isl_val_copy(m));

  v = isl_val_div(v, isl_val_copy(m));

  has_stride = isl_val_gt_si(stride, 1);

  if (has_stride >= 0 && has_stride) {

    isl_aff *aff;

    isl_val *gcd, *a, *b;

    gcd = isl_val_gcdext(v, isl_val_copy(stride), &a, &b);

    isl_val_free(gcd);

    isl_val_free(b);

    aff = isl_constraint_get_aff(c);

    for (i = 0; i < n_div; 
++i17
)

      aff = isl_aff_set_coefficient_si(aff,

               isl_dim_div, i, 0);

    aff = isl_aff_set_coefficient_si(aff, isl_dim_in, data->pos, 0);

    aff = isl_aff_remove_unused_divs(aff);

    a = isl_val_neg(a);

    aff = isl_aff_scale_val(aff, a);

    aff = isl_aff_scale_down_val(aff, m);

    r = set_stride(data, stride, aff);

  } else {

    isl_val_free(stride);

    isl_val_free(m);

    isl_val_free(v);

  }

  isl_constraint_free(c);

  if (has_stride < 0)

    return isl_stat_error;

  return r;

error:

  isl_constraint_free(c);

  return isl_stat_error;

}

/* Check if the constraints in "set" imply any stride on set dimension "pos" and

 * store the results in data->stride and data->offset.

 *

 * In particular, compute the affine hull and then check if

 * any of the constraints in the hull impose any stride on the dimension.

 * If no such constraint can be found, then the offset is taken

 * to be the zero expression and the stride is taken to be one.

 */

static void set_detect_stride(__isl_keep isl_set *set, int pos,

  struct isl_detect_stride_data *data)

{

  isl_basic_set *hull;

  hull = isl_set_affine_hull(isl_set_copy(set));

  data->pos = pos;

  data->found = 0;

  data->stride = NULL;

  data->offset = NULL;

  if (isl_basic_set_foreach_constraint(hull, &detect_stride, data) < 0)

    goto error;

  if (!data->found) {

    data->stride = isl_val_one(isl_set_get_ctx(set));

    if (data->want_offset) {

      isl_space *space;

      isl_local_space *ls;

      space = isl_set_get_space(set);

      ls = isl_local_space_from_space(space);

      data->offset = isl_aff_zero_on_domain(ls);

    }

  }

  isl_basic_set_free(hull);

  return;

error:

  isl_basic_set_free(hull);

  data->stride = isl_val_free(data->stride);

  data->offset = isl_aff_free(data->offset);

}

/* Check if the constraints in "set" imply any stride on set dimension "pos" and

 * return the results in the form of an offset and a stride.

 */

__isl_give isl_stride_info *isl_set_get_stride_info(__isl_keep isl_set *set,

  int pos)

{

  struct isl_detect_stride_data data;

  data.want_offset = 1;

  set_detect_stride(set, pos, &data);

  return isl_stride_info_alloc(data.stride, data.offset);

}

/* Check if the constraints in "set" imply any stride on set dimension "pos" and

 * return this stride.

 */

__isl_give isl_val *isl_set_get_stride(__isl_keep isl_set *set, int pos)

{

  struct isl_detect_stride_data data;

  data.want_offset = 0;

  set_detect_stride(set, pos, &data);

  return data.stride;

}

/* Check if the constraints in "map" imply any stride on output dimension "pos",

 * independently of any other output dimensions, and

 * return the results in the form of an offset and a stride.

 *

 * Convert the input to a set with only the input dimensions and

 * the single output dimension such that it be passed to

 * isl_set_get_stride_info and convert the result back to

 * an expression defined over the domain of "map".

 */

__isl_give isl_stride_info *isl_map_get_range_stride_info(

  __isl_keep isl_map *map, int pos)

{

  isl_stride_info *si;

  isl_set *set;

  map = isl_map_copy(map);

  map = isl_map_project_onto(map, isl_dim_out, pos, 1);

  pos = isl_map_dim(map, isl_dim_in);

  set = isl_map_wrap(map);

  si = isl_set_get_stride_info(set, pos);

  isl_set_free(set);

  if (!si)

    return NULL;

  si->offset = isl_aff_domain_factor_domain(si->offset);

  if (!si->offset)

    return isl_stride_info_free(si);

  return si;

}