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