/*

 * Copyright 2011      INRIA Saclay

 * Copyright 2014      Ecole Normale Superieure

 *

 * 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

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

 */

#include <isl/space.h>

#include <isl_vec_private.h>

#include <isl_mat_private.h>

#include <isl_reordering.h>

#include <isl_seq.h>

#include <isl_local.h>

/* Return the isl_ctx to which "local" belongs.

 */

isl_ctx *isl_local_get_ctx(__isl_keep isl_local *local)

{

  if (!local)

    return NULL;

  return isl_mat_get_ctx(local);

}

/* Create an isl_local object from a matrix describing

 * integer divisions.

 *

 * An isl_local object is current defined as exactly such a matrix,

 * so simply return the input.

 */

__isl_give isl_local *isl_local_alloc_from_mat(__isl_take isl_mat *mat)

{

  return mat;

}

/* Free "local" and return NULL.

 */

__isl_null isl_local *isl_local_free(__isl_take isl_local *local)

{

  isl_mat_free(local);

  return NULL;

}

/* Return the number of local variables (isl_dim_div),

 * the number of other variables (isl_dim_set) or

 * the total number of variables (isl_dim_all) in "local".

 *

 * Other types do not have any meaning for an isl_local object.

 */

int isl_local_dim(__isl_keep isl_local *local, enum isl_dim_type type)

{

  isl_mat *mat = local;

  if (!local)

    return 0;

  if (type == isl_dim_div)

    return isl_mat_rows(mat);

  if (type == isl_dim_all)

    return isl_mat_cols(mat) - 2;

  if (type == isl_dim_set)

    return isl_local_dim(local, isl_dim_all) -

      isl_local_dim(local, isl_dim_div);

  isl_die(isl_local_get_ctx(local), isl_error_unsupported,

    "unsupported dimension type", return 0);

}

/* Check that "pos" is a valid position for a variable in "local".

 */

static isl_stat isl_local_check_pos(__isl_keep isl_local *local, int pos)

{

  if (!local)

    return isl_stat_error;

  if (pos < 0 || pos >= isl_local_dim(local, isl_dim_div))

    
isl_die0
(isl_local_get_ctx(local), isl_error_invalid,

      "position out of bounds", return isl_stat_error);

  return isl_stat_ok;

}

/* Given local variables "local",

 * is the variable at position "pos" marked as not having

 * an explicit representation?

 * Note that even if this variable is not marked in this way and therefore

 * does have an explicit representation, this representation may still

 * depend (indirectly) on other local variables that do not

 * have an explicit representation.

 */

isl_bool isl_local_div_is_marked_unknown(__isl_keep isl_local *local, int pos)

{

  isl_mat *mat = local;

  if (isl_local_check_pos(local, pos) < 0)

    return isl_bool_error;

  return isl_int_is_zero(mat->row[pos][0]);

}

/* Given local variables "local",

 * does the variable at position "pos" have a complete explicit representation?

 * Having a complete explicit representation requires not only

 * an explicit representation, but also that all local variables

 * that appear in this explicit representation in turn have

 * a complete explicit representation.

 */

isl_bool isl_local_div_is_known(__isl_keep isl_local *local, int pos)

{

  isl_bool marked;

  int i, n, off;

  isl_mat *mat = local;

  if (isl_local_check_pos(local, pos) < 0)

    return isl_bool_error;

  marked = isl_local_div_is_marked_unknown(local, pos);

  if (marked < 0 || marked)

    return isl_bool_not(marked);

  n = isl_local_dim(local, isl_dim_div);

  off = isl_mat_cols(mat) - n;

  for (i = n - 1; i >= 0; 
--i4.20k
) {

    isl_bool known;

    if (isl_int_is_zero(mat->row[pos][off + i]))

      
continue4.20k
;

    known = isl_local_div_is_known(local, i);

    if (known < 0 || !known)

      return known;

  }

  return isl_bool_true;

}

/* Does "local" have an explicit representation for all local variables?

 */

isl_bool isl_local_divs_known(__isl_keep isl_local *local)

{

  int i, n;

  if (!local)

    return isl_bool_error;

  n = isl_local_dim(local, isl_dim_div);

  for (i = 0; i < n; 
++i165k
) {

    isl_bool unknown = isl_local_div_is_marked_unknown(local, i);

    if (unknown < 0 || unknown)

      return isl_bool_not(unknown);

  }

  return isl_bool_true;

}

/* Compare two sets of local variables, defined over

 * the same space.

 *

 * Return -1 if "local1" is "smaller" than "local2", 1 if "local1" is "greater"

 * than "local2" and 0 if they are equal.

 *

 * The order is fairly arbitrary.  We do "prefer" divs that only involve

 * earlier dimensions in the sense that we consider matrices where

 * the first differing div involves earlier dimensions to be smaller.

 */

int isl_local_cmp(__isl_keep isl_local *local1, __isl_keep isl_local *local2)

{

  int i;

  int cmp;

  isl_bool unknown1, unknown2;

  int last1, last2;

  int n_col;

  isl_mat *mat1 = local1;

  isl_mat *mat2 = local2;

  if (local1 == local2)

    return 0;

  if (!local1)

    return -1;

  if (!local2)

    return 1;

  if (mat1->n_row != mat2->n_row)

    return mat1->n_row - mat2->n_row;

  n_col = isl_mat_cols(mat1);

  for (i = 0; i < mat1->n_row; 
++i169
) {

    unknown1 = isl_local_div_is_marked_unknown(local1, i);

    unknown2 = isl_local_div_is_marked_unknown(local2, i);

    if (unknown1 && 
unknown20
)

      continue;

    if (unknown1)

      return 1;

    if (unknown2)

      return -1;

    last1 = isl_seq_last_non_zero(mat1->row[i] + 1, n_col - 1);

    last2 = isl_seq_last_non_zero(mat2->row[i] + 1, n_col - 1);

    if (last1 != last2)

      return last1 - last2;

    cmp = isl_seq_cmp(mat1->row[i], mat2->row[i], n_col);

    if (cmp != 0)

      return cmp;

  }

  
return 016.3k
;

}

/* Reorder the columns of the given local variables according to the

 * given reordering.

 * The order of the local variables themselves is assumed not to change.

 */

__isl_give isl_local *isl_local_reorder(__isl_take isl_local *local,

  __isl_take isl_reordering *r)

{

  isl_mat *div = local;

  int i, j;

  isl_space *space;

  isl_mat *mat;

  int extra;

  if (!local || !r)

    goto error;

  space = isl_reordering_peek_space(r);

  extra = isl_space_dim(space, isl_dim_all) + div->n_row - r->len;

  mat = isl_mat_alloc(div->ctx, div->n_row, div->n_col + extra);

  if (!mat)

    goto error;

  
for (i = 0; 10.2k
i < div->n_row; 
++i405
) {

    isl_seq_cpy(mat->row[i], div->row[i], 2);

    isl_seq_clr(mat->row[i] + 2, mat->n_col - 2);

    for (j = 0; j < r->len; 
++j1.48k
)

      isl_int_set(mat->row[i][2 + r->pos[j]],

            div->row[i][2 + j]);

  }

  isl_reordering_free(r);

  isl_local_free(local);

  return isl_local_alloc_from_mat(mat);

error:

  isl_reordering_free(r);

  isl_local_free(local);

  return NULL;

}

/* Extend a vector "v" representing an integer point

 * in the domain space of "local"

 * to one that also includes values for the local variables.

 * All local variables are required to have an explicit representation.

 */

__isl_give isl_vec *isl_local_extend_point_vec(__isl_keep isl_local *local,

  __isl_take isl_vec *v)

{

  unsigned n_div;

  isl_bool known;

  isl_mat *mat = local;

  if (!local || !v)

    return isl_vec_free(v);

  known = isl_local_divs_known(local);

  if (known < 0)

    return isl_vec_free(v);

  if (!known)

    
isl_die0
(isl_local_get_ctx(local), isl_error_invalid,

      "unknown local variables", return isl_vec_free(v));

  if (isl_vec_size(v) != 1 + isl_local_dim(local, isl_dim_set))

    
isl_die0
(isl_local_get_ctx(local), isl_error_invalid,

      "incorrect size", return isl_vec_free(v));

  if (!isl_int_is_one(v->el[0]))

    
isl_die0
(isl_local_get_ctx(local), isl_error_invalid,

      "expecting integer point", return isl_vec_free(v));

  n_div = isl_local_dim(local, isl_dim_div);

  if (n_div != 0) {

    int i;

    unsigned dim = isl_local_dim(local, isl_dim_set);

    v = isl_vec_add_els(v, n_div);

    if (!v)

      return NULL;

    
for (i = 0; 12
i < n_div; 
++i24
) {

      isl_seq_inner_product(mat->row[i] + 1, v->el,

            1 + dim + i, &v->el[1+dim+i]);

      isl_int_fdiv_q(v->el[1+dim+i], v->el[1+dim+i],

          mat->row[i][0]);

    }

  }

  return v;

}