373 lines · c
1/*2 * Copyright 2011 INRIA Saclay3 * Copyright 2014 Ecole Normale Superieure4 * Copyright 2015 Sven Verdoolaege5 *6 * Use of this software is governed by the MIT license7 *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, France11 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France12 */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 */23isl_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 describing32 * 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) or59 * 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 */63isl_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 TYPE91#define TYPE isl_local92static93#include "check_type_range_templ.c"94 95/* Check that "pos" is a valid position for a variable in "local".96 */97static 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 having104 * an explicit representation?105 * Note that even if this variable is not marked in this way and therefore106 * does have an explicit representation, this representation may still107 * depend (indirectly) on other local variables that do not108 * have an explicit representation.109 */110isl_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 only122 * an explicit representation, but also that all local variables123 * that appear in this explicit representation in turn have124 * a complete explicit representation.125 */126isl_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 */161isl_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 over180 * 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 involve186 * earlier dimensions in the sense that we consider matrices where187 * the first differing div involves earlier dimensions to be smaller.188 */189int 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 type234 * 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 minus238 * the number of local variables.239 */240isl_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 the260 * 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);290error: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/* Extend a vector "v" representing an integer point323 * in the domain space of "local"324 * to one that also includes values for the local variables.325 * All local variables are required to have an explicit representation.326 * If there are no local variables, then the point is not required327 * to be integral.328 */329__isl_give isl_vec *isl_local_extend_point_vec(__isl_keep isl_local *local,330 __isl_take isl_vec *v)331{332 isl_size dim, n_div, size;333 isl_bool known;334 isl_mat *mat = local;335 336 if (!local || !v)337 return isl_vec_free(v);338 known = isl_local_divs_known(local);339 if (known < 0)340 return isl_vec_free(v);341 if (!known)342 isl_die(isl_local_get_ctx(local), isl_error_invalid,343 "unknown local variables", return isl_vec_free(v));344 dim = isl_local_dim(local, isl_dim_set);345 n_div = isl_local_dim(local, isl_dim_div);346 size = isl_vec_size(v);347 if (dim < 0 || n_div < 0 || size < 0)348 return isl_vec_free(v);349 if (size != 1 + dim)350 isl_die(isl_local_get_ctx(local), isl_error_invalid,351 "incorrect size", return isl_vec_free(v));352 if (n_div == 0)353 return v;354 if (!isl_int_is_one(v->el[0]))355 isl_die(isl_local_get_ctx(local), isl_error_invalid,356 "expecting integer point", return isl_vec_free(v));357 {358 int i;359 v = isl_vec_add_els(v, n_div);360 if (!v)361 return NULL;362 363 for (i = 0; i < n_div; ++i) {364 isl_seq_inner_product(mat->row[i] + 1, v->el,365 1 + dim + i, &v->el[1+dim+i]);366 isl_int_fdiv_q(v->el[1+dim+i], v->el[1+dim+i],367 mat->row[i][0]);368 }369 }370 371 return v;372}373