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 */
isl_local_get_ctx(__isl_keep isl_local * local)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 */
isl_local_alloc_from_mat(__isl_take isl_mat * mat)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 */
isl_local_copy(__isl_keep isl_local * local)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 */
isl_local_free(__isl_take isl_local * local)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 */
isl_local_dim(__isl_keep isl_local * local,enum isl_dim_type type)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 */
isl_local_check_pos(__isl_keep isl_local * local,int pos)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 */
isl_local_div_is_marked_unknown(__isl_keep isl_local * local,int pos)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 */
isl_local_div_is_known(__isl_keep isl_local * local,int pos)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 */
isl_local_divs_known(__isl_keep isl_local * local)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 */
isl_local_cmp(__isl_keep isl_local * local1,__isl_keep isl_local * local2)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 */
isl_local_var_offset(__isl_keep isl_local * local,enum isl_dim_type type)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 */
isl_local_reorder(__isl_take isl_local * local,__isl_take isl_reordering * r)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 */
isl_local_move_vars(__isl_take isl_local * local,unsigned dst_pos,unsigned src_pos,unsigned n)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 */
isl_local_involves_vars(__isl_keep isl_local * local,unsigned first,unsigned n)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 */
isl_local_extend_point_vec(__isl_keep isl_local * local,__isl_take isl_vec * v)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