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