isl_local.c

   1 /*
   2  * Copyright 2011      INRIA Saclay
   3  * Copyright 2014      Ecole Normale Superieure
   4  *
   5  * Use of this software is governed by the MIT license
   6  *
   7  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   8  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   9  * 91893 Orsay, France
  10  * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
  11  */
  12
  13 #include <isl/space.h>
  14 #include <isl_vec_private.h>
  15 #include <isl_mat_private.h>
  16 #include <isl_reordering.h>
  17 #include <isl_seq.h>
  18 #include <isl_local_private.h>
  19
  20 /* Return the isl_ctx to which "local" belongs.
  21  */
  22 isl_ctx *isl_local_get_ctx(__isl_keep isl_local *local)
  23 {
  24         if (!local)
  25                 return NULL;
  26
  27         return isl_mat_get_ctx(local);
  28 }
  29
  30 /* Create an isl_local object from a matrix describing
  31  * integer divisions.
  32  *
  33  * An isl_local object is current defined as exactly such a matrix,
  34  * so simply return the input.
  35  */
  36 __isl_give isl_local *isl_local_alloc_from_mat(__isl_take isl_mat *mat)
  37 {
  38         return mat;
  39 }
  40
  41 /* Free "local" and return NULL.
  42  */
  43 __isl_null isl_local *isl_local_free(__isl_take isl_local *local)
  44 {
  45         isl_mat_free(local);
  46         return NULL;
  47 }
  48
  49 /* Return the number of local variables (isl_dim_div),
  50  * the number of other variables (isl_dim_set) or
  51  * the total number of variables (isl_dim_all) in "local".
  52  *
  53  * Other types do not have any meaning for an isl_local object.
  54  */
  55 isl_size isl_local_dim(__isl_keep isl_local *local, enum isl_dim_type type)
  56 {
  57         isl_mat *mat = local;
  58
  59         if (!local)
  60                 return isl_size_error;
  61         if (type == isl_dim_div)
  62                 return isl_mat_rows(mat);
  63         if (type == isl_dim_all) {
  64                 isl_size cols = isl_mat_cols(mat);
  65                 if (cols < 0)
  66                         return isl_size_error;
  67                 return cols - 2;
  68         }
  69         if (type == isl_dim_set) {
  70                 isl_size total, n_div;
  71
  72                 total = isl_local_dim(local, isl_dim_all);
  73                 n_div = isl_local_dim(local, isl_dim_div);
  74                 if (total < 0 || n_div < 0)
  75                         return isl_size_error;
  76                 return total - n_div;
  77         }
  78         isl_die(isl_local_get_ctx(local), isl_error_unsupported,
  79                 "unsupported dimension type", return isl_size_error);
  80 }
  81
  82 #undef TYPE
  83 #define TYPE    isl_local
  84 static
  85 #include "check_type_range_templ.c"
  86
  87 /* Check that "pos" is a valid position for a variable in "local".
  88  */
  89 static isl_stat isl_local_check_pos(__isl_keep isl_local *local, int pos)
  90 {
  91         return isl_local_check_range(local, isl_dim_div, pos, 1);
  92 }
  93
  94 /* Given local variables "local",
  95  * is the variable at position "pos" marked as not having
  96  * an explicit representation?
  97  * Note that even if this variable is not marked in this way and therefore
  98  * does have an explicit representation, this representation may still
  99  * depend (indirectly) on other local variables that do not
 100  * have an explicit representation.
 101  */
 102 isl_bool isl_local_div_is_marked_unknown(__isl_keep isl_local *local, int pos)
 103 {
 104         isl_mat *mat = local;
 105
 106         if (isl_local_check_pos(local, pos) < 0)
 107                 return isl_bool_error;
 108         return isl_bool_ok(isl_int_is_zero(mat->row[pos][0]));
 109 }
 110
 111 /* Given local variables "local",
 112  * does the variable at position "pos" have a complete explicit representation?
 113  * Having a complete explicit representation requires not only
 114  * an explicit representation, but also that all local variables
 115  * that appear in this explicit representation in turn have
 116  * a complete explicit representation.
 117  */
 118 isl_bool isl_local_div_is_known(__isl_keep isl_local *local, int pos)
 119 {
 120         isl_bool marked;
 121         int i, off;
 122         isl_size n, cols;
 123         isl_mat *mat = local;
 124
 125         if (isl_local_check_pos(local, pos) < 0)
 126                 return isl_bool_error;
 127
 128         marked = isl_local_div_is_marked_unknown(local, pos);
 129         if (marked < 0 || marked)
 130                 return isl_bool_not(marked);
 131
 132         n = isl_local_dim(local, isl_dim_div);
 133         cols = isl_mat_cols(mat);
 134         if (n < 0 || cols < 0)
 135                 return isl_bool_error;
 136         off = cols - n;
 137
 138         for (i = n - 1; i >= 0; --i) {
 139                 isl_bool known;
 140
 141                 if (isl_int_is_zero(mat->row[pos][off + i]))
 142                         continue;
 143                 known = isl_local_div_is_known(local, i);
 144                 if (known < 0 || !known)
 145                         return known;
 146         }
 147
 148         return isl_bool_true;
 149 }
 150
 151 /* Does "local" have an explicit representation for all local variables?
 152  */
 153 isl_bool isl_local_divs_known(__isl_keep isl_local *local)
 154 {
 155         int i;
 156         isl_size n;
 157
 158         n = isl_local_dim(local, isl_dim_div);
 159         if (n < 0)
 160                 return isl_bool_error;
 161
 162         for (i = 0; i < n; ++i) {
 163                 isl_bool unknown = isl_local_div_is_marked_unknown(local, i);
 164                 if (unknown < 0 || unknown)
 165                         return isl_bool_not(unknown);
 166         }
 167
 168         return isl_bool_true;
 169 }
 170
 171 /* Compare two sets of local variables, defined over
 172  * the same space.
 173  *
 174  * Return -1 if "local1" is "smaller" than "local2", 1 if "local1" is "greater"
 175  * than "local2" and 0 if they are equal.
 176  *
 177  * The order is fairly arbitrary.  We do "prefer" divs that only involve
 178  * earlier dimensions in the sense that we consider matrices where
 179  * the first differing div involves earlier dimensions to be smaller.
 180  */
 181 int isl_local_cmp(__isl_keep isl_local *local1, __isl_keep isl_local *local2)
 182 {
 183         int i;
 184         int cmp;
 185         isl_bool unknown1, unknown2;
 186         int last1, last2;
 187         isl_size n_col;
 188         isl_mat *mat1 = local1;
 189         isl_mat *mat2 = local2;
 190
 191         if (local1 == local2)
 192                 return 0;
 193         if (!local1)
 194                 return -1;
 195         if (!local2)
 196                 return 1;
 197
 198         if (mat1->n_row != mat2->n_row)
 199                 return mat1->n_row - mat2->n_row;
 200
 201         n_col = isl_mat_cols(mat1);
 202         if (n_col < 0)
 203                 return -1;
 204         for (i = 0; i < mat1->n_row; ++i) {
 205                 unknown1 = isl_local_div_is_marked_unknown(local1, i);
 206                 unknown2 = isl_local_div_is_marked_unknown(local2, i);
 207                 if (unknown1 && unknown2)
 208                         continue;
 209                 if (unknown1)
 210                         return 1;
 211                 if (unknown2)
 212                         return -1;
 213                 last1 = isl_seq_last_non_zero(mat1->row[i] + 1, n_col - 1);
 214                 last2 = isl_seq_last_non_zero(mat2->row[i] + 1, n_col - 1);
 215                 if (last1 != last2)
 216                         return last1 - last2;
 217                 cmp = isl_seq_cmp(mat1->row[i], mat2->row[i], n_col);
 218                 if (cmp != 0)
 219                         return cmp;
 220         }
 221
 222         return 0;
 223 }
 224
 225 /* Reorder the columns of the given local variables according to the
 226  * given reordering.
 227  * The order of the local variables themselves is assumed not to change.
 228  */
 229 __isl_give isl_local *isl_local_reorder(__isl_take isl_local *local,
 230         __isl_take isl_reordering *r)
 231 {
 232         isl_mat *div = local;
 233         int i, j;
 234         isl_size dim;
 235         isl_space *space;
 236         isl_mat *mat;
 237         int extra;
 238
 239         if (!local || !r)
 240                 goto error;
 241
 242         space = isl_reordering_peek_space(r);
 243         dim = isl_space_dim(space, isl_dim_all);
 244         if (dim < 0)
 245                 goto error;
 246         extra = dim + div->n_row - r->len;
 247         mat = isl_mat_alloc(div->ctx, div->n_row, div->n_col + extra);
 248         if (!mat)
 249                 goto error;
 250
 251         for (i = 0; i < div->n_row; ++i) {
 252                 isl_seq_cpy(mat->row[i], div->row[i], 2);
 253                 isl_seq_clr(mat->row[i] + 2, mat->n_col - 2);
 254                 for (j = 0; j < r->len; ++j)
 255                         isl_int_set(mat->row[i][2 + r->pos[j]],
 256                                     div->row[i][2 + j]);
 257         }
 258
 259         isl_reordering_free(r);
 260         isl_local_free(local);
 261         return isl_local_alloc_from_mat(mat);
 262 error:
 263         isl_reordering_free(r);
 264         isl_local_free(local);
 265         return NULL;
 266 }
 267
 268 /* Extend a vector "v" representing an integer point
 269  * in the domain space of "local"
 270  * to one that also includes values for the local variables.
 271  * All local variables are required to have an explicit representation.
 272  * If there are no local variables, then the point is not required
 273  * to be integral.
 274  */
 275 __isl_give isl_vec *isl_local_extend_point_vec(__isl_keep isl_local *local,
 276         __isl_take isl_vec *v)
 277 {
 278         isl_size dim, n_div, size;
 279         isl_bool known;
 280         isl_mat *mat = local;
 281
 282         if (!local || !v)
 283                 return isl_vec_free(v);
 284         known = isl_local_divs_known(local);
 285         if (known < 0)
 286                 return isl_vec_free(v);
 287         if (!known)
 288                 isl_die(isl_local_get_ctx(local), isl_error_invalid,
 289                         "unknown local variables", return isl_vec_free(v));
 290         dim = isl_local_dim(local, isl_dim_set);
 291         n_div = isl_local_dim(local, isl_dim_div);
 292         size = isl_vec_size(v);
 293         if (dim < 0 || n_div < 0 || size < 0)
 294                 return isl_vec_free(v);
 295         if (size != 1 + dim)
 296                 isl_die(isl_local_get_ctx(local), isl_error_invalid,
 297                         "incorrect size", return isl_vec_free(v));
 298         if (n_div == 0)
 299                 return v;
 300         if (!isl_int_is_one(v->el[0]))
 301                 isl_die(isl_local_get_ctx(local), isl_error_invalid,
 302                         "expecting integer point", return isl_vec_free(v));
 303         {
 304                 int i;
 305                 v = isl_vec_add_els(v, n_div);
 306                 if (!v)
 307                         return NULL;
 308
 309                 for (i = 0; i < n_div; ++i) {
 310                         isl_seq_inner_product(mat->row[i] + 1, v->el,
 311                                                 1 + dim + i, &v->el[1+dim+i]);
 312                         isl_int_fdiv_q(v->el[1+dim+i], v->el[1+dim+i],
 313                                         mat->row[i][0]);
 314                 }
 315         }
 316
 317         return v;
 318 }