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_seq.h>
  17 #include <isl_local.h>
  18
  19 /* Return the isl_ctx to which "local" belongs.
  20  */
  21 isl_ctx *isl_local_get_ctx(__isl_keep isl_local *local)
  22 {
  23         if (!local)
  24                 return NULL;
  25
  26         return isl_mat_get_ctx(local);
  27 }
  28
  29 /* Return the number of local variables (isl_dim_div),
  30  * the number of other variables (isl_dim_set) or
  31  * the total number of variables (isl_dim_all) in "local".
  32  *
  33  * Other types do not have any meaning for an isl_local object.
  34  */
  35 int isl_local_dim(__isl_keep isl_local *local, enum isl_dim_type type)
  36 {
  37         isl_mat *mat = local;
  38
  39         if (!local)
  40                 return 0;
  41         if (type == isl_dim_div)
  42                 return isl_mat_rows(mat);
  43         if (type == isl_dim_all)
  44                 return isl_mat_cols(mat) - 2;
  45         if (type == isl_dim_set)
  46                 return isl_local_dim(local, isl_dim_all) -
  47                         isl_local_dim(local, isl_dim_div);
  48         isl_die(isl_local_get_ctx(local), isl_error_unsupported,
  49                 "unsupported dimension type", return 0);
  50 }
  51
  52 /* Check that "pos" is a valid position for a variable in "local".
  53  */
  54 static isl_stat isl_local_check_pos(__isl_keep isl_local *local, int pos)
  55 {
  56         if (!local)
  57                 return isl_stat_error;
  58         if (pos < 0 || pos >= isl_local_dim(local, isl_dim_div))
  59                 isl_die(isl_local_get_ctx(local), isl_error_invalid,
  60                         "position out of bounds", return isl_stat_error);
  61         return isl_stat_ok;
  62 }
  63
  64 /* Given local variables "local",
  65  * is the variable at position "pos" marked as not having
  66  * an explicit representation?
  67  * Note that even if this variable is not marked in this way and therefore
  68  * does have an explicit representation, this representation may still
  69  * depend (indirectly) on other local variables that do not
  70  * have an explicit representation.
  71  */
  72 isl_bool isl_local_div_is_marked_unknown(__isl_keep isl_local *local, int pos)
  73 {
  74         isl_mat *mat = local;
  75
  76         if (isl_local_check_pos(local, pos) < 0)
  77                 return isl_bool_error;
  78         return isl_int_is_zero(mat->row[pos][0]);
  79 }
  80
  81 /* Given local variables "local",
  82  * does the variable at position "pos" have a complete explicit representation?
  83  * Having a complete explicit representation requires not only
  84  * an explicit representation, but also that all local variables
  85  * that appear in this explicit representation in turn have
  86  * a complete explicit representation.
  87  */
  88 isl_bool isl_local_div_is_known(__isl_keep isl_local *local, int pos)
  89 {
  90         isl_bool marked;
  91         int i, n, off;
  92         isl_mat *mat = local;
  93
  94         if (isl_local_check_pos(local, pos) < 0)
  95                 return isl_bool_error;
  96
  97         marked = isl_local_div_is_marked_unknown(local, pos);
  98         if (marked < 0 || marked)
  99                 return isl_bool_not(marked);
 100
 101         n = isl_local_dim(local, isl_dim_div);
 102         off = isl_mat_cols(mat) - n;
 103
 104         for (i = n - 1; i >= 0; --i) {
 105                 isl_bool known;
 106
 107                 if (isl_int_is_zero(mat->row[pos][off + i]))
 108                         continue;
 109                 known = isl_local_div_is_known(local, i);
 110                 if (known < 0 || !known)
 111                         return known;
 112         }
 113
 114         return isl_bool_true;
 115 }
 116
 117 /* Does "local" have an explicit representation for all local variables?
 118  */
 119 isl_bool isl_local_divs_known(__isl_keep isl_local *local)
 120 {
 121         int i, n;
 122
 123         if (!local)
 124                 return isl_bool_error;
 125
 126         n = isl_local_dim(local, isl_dim_div);
 127         for (i = 0; i < n; ++i) {
 128                 isl_bool unknown = isl_local_div_is_marked_unknown(local, i);
 129                 if (unknown < 0 || unknown)
 130                         return isl_bool_not(unknown);
 131         }
 132
 133         return isl_bool_true;
 134 }
 135
 136 /* Compare two sets of local variables, defined over
 137  * the same space.
 138  *
 139  * Return -1 if "local1" is "smaller" than "local2", 1 if "local1" is "greater"
 140  * than "local2" and 0 if they are equal.
 141  *
 142  * The order is fairly arbitrary.  We do "prefer" divs that only involve
 143  * earlier dimensions in the sense that we consider matrices where
 144  * the first differing div involves earlier dimensions to be smaller.
 145  */
 146 int isl_local_cmp(__isl_keep isl_local *local1, __isl_keep isl_local *local2)
 147 {
 148         int i;
 149         int cmp;
 150         isl_bool unknown1, unknown2;
 151         int last1, last2;
 152         int n_col;
 153         isl_mat *mat1 = local1;
 154         isl_mat *mat2 = local2;
 155
 156         if (local1 == local2)
 157                 return 0;
 158         if (!local1)
 159                 return -1;
 160         if (!local2)
 161                 return 1;
 162
 163         if (mat1->n_row != mat2->n_row)
 164                 return mat1->n_row - mat2->n_row;
 165
 166         n_col = isl_mat_cols(mat1);
 167         for (i = 0; i < mat1->n_row; ++i) {
 168                 unknown1 = isl_local_div_is_marked_unknown(local1, i);
 169                 unknown2 = isl_local_div_is_marked_unknown(local2, i);
 170                 if (unknown1 && unknown2)
 171                         continue;
 172                 if (unknown1)
 173                         return 1;
 174                 if (unknown2)
 175                         return -1;
 176                 last1 = isl_seq_last_non_zero(mat1->row[i] + 1, n_col - 1);
 177                 last2 = isl_seq_last_non_zero(mat2->row[i] + 1, n_col - 1);
 178                 if (last1 != last2)
 179                         return last1 - last2;
 180                 cmp = isl_seq_cmp(mat1->row[i], mat2->row[i], n_col);
 181                 if (cmp != 0)
 182                         return cmp;
 183         }
 184
 185         return 0;
 186 }
 187
 188 /* Extend a vector "v" representing an integer point
 189  * in the domain space of "local"
 190  * to one that also includes values for the local variables.
 191  * All local variables are required to have an explicit representation.
 192  */
 193 __isl_give isl_vec *isl_local_extend_point_vec(__isl_keep isl_local *local,
 194         __isl_take isl_vec *v)
 195 {
 196         unsigned n_div;
 197         isl_bool known;
 198         isl_mat *mat = local;
 199
 200         if (!local || !v)
 201                 return isl_vec_free(v);
 202         known = isl_local_divs_known(local);
 203         if (known < 0)
 204                 return isl_vec_free(v);
 205         if (!known)
 206                 isl_die(isl_local_get_ctx(local), isl_error_invalid,
 207                         "unknown local variables", return isl_vec_free(v));
 208         if (isl_vec_size(v) != 1 + isl_local_dim(local, isl_dim_set))
 209                 isl_die(isl_local_get_ctx(local), isl_error_invalid,
 210                         "incorrect size", return isl_vec_free(v));
 211         if (!isl_int_is_one(v->el[0]))
 212                 isl_die(isl_local_get_ctx(local), isl_error_invalid,
 213                         "expecting integer point", return isl_vec_free(v));
 214         n_div = isl_local_dim(local, isl_dim_div);
 215         if (n_div != 0) {
 216                 int i;
 217                 unsigned dim = isl_local_dim(local, isl_dim_set);
 218                 v = isl_vec_add_els(v, n_div);
 219                 if (!v)
 220                         return NULL;
 221
 222                 for (i = 0; i < n_div; ++i) {
 223                         isl_seq_inner_product(mat->row[i] + 1, v->el,
 224                                                 1 + dim + i, &v->el[1+dim+i]);
 225                         isl_int_fdiv_q(v->el[1+dim+i], v->el[1+dim+i],
 226                                         mat->row[i][0]);
 227                 }
 228         }
 229
 230         return v;
 231 }