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 */
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(mat: 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(mat: isl_mat_copy(mat: 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(mat: 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 */
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, type: isl_dim_all);
81 n_div = isl_local_dim(local, type: 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
92static
93#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(obj: local, type: isl_dim_div, first: pos, n: 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 */
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 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 */
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(b: marked);
139
140 n = isl_local_dim(local, type: 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, pos: 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, type: 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, pos: i);
172 if (unknown < 0 || unknown)
173 return isl_bool_not(b: 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 */
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(mat: 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(local: local1, pos: i);
214 unknown2 = isl_local_div_is_marked_unknown(local: local2, pos: 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(p: mat1->row[i] + 1, len: n_col - 1);
222 last2 = isl_seq_last_non_zero(p: mat2->row[i] + 1, len: n_col - 1);
223 if (last1 != last2)
224 return last1 - last2;
225 cmp = isl_seq_cmp(p1: mat1->row[i], p2: mat2->row[i], len: 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 */
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, type: isl_dim_div);
253 n_all = isl_local_dim(local, type: 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(ctx: div->ctx, n_row: div->n_row, n_col: div->n_col + extra);
276 if (!mat)
277 goto error;
278
279 for (i = 0; i < div->n_row; ++i) {
280 isl_seq_cpy(dst: mat->row[i], src: div->row[i], len: 2);
281 isl_seq_clr(p: mat->row[i] + 2, len: 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(exp: r);
288 isl_local_free(local);
289 return isl_local_alloc_from_mat(mat);
290error:
291 isl_reordering_free(exp: 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, type: 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, dst_col: 2 + dst_pos, src_col: 2 + src_pos, n);
318
319 return isl_local_alloc_from_mat(mat);
320}
321
322/* Extend a vector "v" representing an integer point
323 * 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 required
327 * 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(vec: v);
338 known = isl_local_divs_known(local);
339 if (known < 0)
340 return isl_vec_free(vec: 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, type: isl_dim_set);
345 n_div = isl_local_dim(local, type: isl_dim_div);
346 size = isl_vec_size(vec: v);
347 if (dim < 0 || n_div < 0 || size < 0)
348 return isl_vec_free(vec: 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(vec: v, n: n_div);
360 if (!v)
361 return NULL;
362
363 for (i = 0; i < n_div; ++i) {
364 isl_seq_inner_product(p1: mat->row[i] + 1, p2: v->el,
365 len: 1 + dim + i, prod: &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

source code of polly/lib/External/isl/isl_local.c