• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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/space.h>
14 #include <isl_vec_private.h>
15 #include <isl_mat_private.h>
16 #include <isl_reordering.h>
17 #include <isl_seq.h>
18 #include <isl_local_private.h>
19 
20 /* Return the isl_ctx to which "local" belongs.
21  */
isl_local_get_ctx(__isl_keep isl_local * local)22 isl_ctx *isl_local_get_ctx(__isl_keep isl_local *local)
23 {
24 	if (!local)
25 		return NULL;
26 
27 	return isl_mat_get_ctx(local);
28 }
29 
30 /* Create an isl_local object from a matrix describing
31  * integer divisions.
32  *
33  * An isl_local object is current defined as exactly such a matrix,
34  * so simply return the input.
35  */
isl_local_alloc_from_mat(__isl_take isl_mat * mat)36 __isl_give isl_local *isl_local_alloc_from_mat(__isl_take isl_mat *mat)
37 {
38 	return mat;
39 }
40 
41 /* Free "local" and return NULL.
42  */
isl_local_free(__isl_take isl_local * local)43 __isl_null isl_local *isl_local_free(__isl_take isl_local *local)
44 {
45 	isl_mat_free(local);
46 	return NULL;
47 }
48 
49 /* Return the number of local variables (isl_dim_div),
50  * the number of other variables (isl_dim_set) or
51  * the total number of variables (isl_dim_all) in "local".
52  *
53  * Other types do not have any meaning for an isl_local object.
54  */
isl_local_dim(__isl_keep isl_local * local,enum isl_dim_type type)55 isl_size isl_local_dim(__isl_keep isl_local *local, enum isl_dim_type type)
56 {
57 	isl_mat *mat = local;
58 
59 	if (!local)
60 		return isl_size_error;
61 	if (type == isl_dim_div)
62 		return isl_mat_rows(mat);
63 	if (type == isl_dim_all) {
64 		isl_size cols = isl_mat_cols(mat);
65 		if (cols < 0)
66 			return isl_size_error;
67 		return cols - 2;
68 	}
69 	if (type == isl_dim_set) {
70 		isl_size total, n_div;
71 
72 		total = isl_local_dim(local, isl_dim_all);
73 		n_div = isl_local_dim(local, isl_dim_div);
74 		if (total < 0 || n_div < 0)
75 			return isl_size_error;
76 		return total - n_div;
77 	}
78 	isl_die(isl_local_get_ctx(local), isl_error_unsupported,
79 		"unsupported dimension type", return isl_size_error);
80 }
81 
82 #undef TYPE
83 #define TYPE	isl_local
84 static
85 #include "check_type_range_templ.c"
86 
87 /* Check that "pos" is a valid position for a variable in "local".
88  */
isl_local_check_pos(__isl_keep isl_local * local,int pos)89 static isl_stat isl_local_check_pos(__isl_keep isl_local *local, int pos)
90 {
91 	return isl_local_check_range(local, isl_dim_div, pos, 1);
92 }
93 
94 /* Given local variables "local",
95  * is the variable at position "pos" marked as not having
96  * an explicit representation?
97  * Note that even if this variable is not marked in this way and therefore
98  * does have an explicit representation, this representation may still
99  * depend (indirectly) on other local variables that do not
100  * have an explicit representation.
101  */
isl_local_div_is_marked_unknown(__isl_keep isl_local * local,int pos)102 isl_bool isl_local_div_is_marked_unknown(__isl_keep isl_local *local, int pos)
103 {
104 	isl_mat *mat = local;
105 
106 	if (isl_local_check_pos(local, pos) < 0)
107 		return isl_bool_error;
108 	return isl_bool_ok(isl_int_is_zero(mat->row[pos][0]));
109 }
110 
111 /* Given local variables "local",
112  * does the variable at position "pos" have a complete explicit representation?
113  * Having a complete explicit representation requires not only
114  * an explicit representation, but also that all local variables
115  * that appear in this explicit representation in turn have
116  * a complete explicit representation.
117  */
isl_local_div_is_known(__isl_keep isl_local * local,int pos)118 isl_bool isl_local_div_is_known(__isl_keep isl_local *local, int pos)
119 {
120 	isl_bool marked;
121 	int i, off;
122 	isl_size n, cols;
123 	isl_mat *mat = local;
124 
125 	if (isl_local_check_pos(local, pos) < 0)
126 		return isl_bool_error;
127 
128 	marked = isl_local_div_is_marked_unknown(local, pos);
129 	if (marked < 0 || marked)
130 		return isl_bool_not(marked);
131 
132 	n = isl_local_dim(local, isl_dim_div);
133 	cols = isl_mat_cols(mat);
134 	if (n < 0 || cols < 0)
135 		return isl_bool_error;
136 	off = cols - n;
137 
138 	for (i = n - 1; i >= 0; --i) {
139 		isl_bool known;
140 
141 		if (isl_int_is_zero(mat->row[pos][off + i]))
142 			continue;
143 		known = isl_local_div_is_known(local, i);
144 		if (known < 0 || !known)
145 			return known;
146 	}
147 
148 	return isl_bool_true;
149 }
150 
151 /* Does "local" have an explicit representation for all local variables?
152  */
isl_local_divs_known(__isl_keep isl_local * local)153 isl_bool isl_local_divs_known(__isl_keep isl_local *local)
154 {
155 	int i;
156 	isl_size n;
157 
158 	n = isl_local_dim(local, isl_dim_div);
159 	if (n < 0)
160 		return isl_bool_error;
161 
162 	for (i = 0; i < n; ++i) {
163 		isl_bool unknown = isl_local_div_is_marked_unknown(local, i);
164 		if (unknown < 0 || unknown)
165 			return isl_bool_not(unknown);
166 	}
167 
168 	return isl_bool_true;
169 }
170 
171 /* Compare two sets of local variables, defined over
172  * the same space.
173  *
174  * Return -1 if "local1" is "smaller" than "local2", 1 if "local1" is "greater"
175  * than "local2" and 0 if they are equal.
176  *
177  * The order is fairly arbitrary.  We do "prefer" divs that only involve
178  * earlier dimensions in the sense that we consider matrices where
179  * the first differing div involves earlier dimensions to be smaller.
180  */
isl_local_cmp(__isl_keep isl_local * local1,__isl_keep isl_local * local2)181 int isl_local_cmp(__isl_keep isl_local *local1, __isl_keep isl_local *local2)
182 {
183 	int i;
184 	int cmp;
185 	isl_bool unknown1, unknown2;
186 	int last1, last2;
187 	isl_size n_col;
188 	isl_mat *mat1 = local1;
189 	isl_mat *mat2 = local2;
190 
191 	if (local1 == local2)
192 		return 0;
193 	if (!local1)
194 		return -1;
195 	if (!local2)
196 		return 1;
197 
198 	if (mat1->n_row != mat2->n_row)
199 		return mat1->n_row - mat2->n_row;
200 
201 	n_col = isl_mat_cols(mat1);
202 	if (n_col < 0)
203 		return -1;
204 	for (i = 0; i < mat1->n_row; ++i) {
205 		unknown1 = isl_local_div_is_marked_unknown(local1, i);
206 		unknown2 = isl_local_div_is_marked_unknown(local2, i);
207 		if (unknown1 && unknown2)
208 			continue;
209 		if (unknown1)
210 			return 1;
211 		if (unknown2)
212 			return -1;
213 		last1 = isl_seq_last_non_zero(mat1->row[i] + 1, n_col - 1);
214 		last2 = isl_seq_last_non_zero(mat2->row[i] + 1, n_col - 1);
215 		if (last1 != last2)
216 			return last1 - last2;
217 		cmp = isl_seq_cmp(mat1->row[i], mat2->row[i], n_col);
218 		if (cmp != 0)
219 			return cmp;
220 	}
221 
222 	return 0;
223 }
224 
225 /* Reorder the columns of the given local variables according to the
226  * given reordering.
227  * The order of the local variables themselves is assumed not to change.
228  */
isl_local_reorder(__isl_take isl_local * local,__isl_take isl_reordering * r)229 __isl_give isl_local *isl_local_reorder(__isl_take isl_local *local,
230 	__isl_take isl_reordering *r)
231 {
232 	isl_mat *div = local;
233 	int i, j;
234 	isl_size dim;
235 	isl_space *space;
236 	isl_mat *mat;
237 	int extra;
238 
239 	if (!local || !r)
240 		goto error;
241 
242 	space = isl_reordering_peek_space(r);
243 	dim = isl_space_dim(space, isl_dim_all);
244 	if (dim < 0)
245 		goto error;
246 	extra = dim + div->n_row - r->len;
247 	mat = isl_mat_alloc(div->ctx, div->n_row, div->n_col + extra);
248 	if (!mat)
249 		goto error;
250 
251 	for (i = 0; i < div->n_row; ++i) {
252 		isl_seq_cpy(mat->row[i], div->row[i], 2);
253 		isl_seq_clr(mat->row[i] + 2, mat->n_col - 2);
254 		for (j = 0; j < r->len; ++j)
255 			isl_int_set(mat->row[i][2 + r->pos[j]],
256 				    div->row[i][2 + j]);
257 	}
258 
259 	isl_reordering_free(r);
260 	isl_local_free(local);
261 	return isl_local_alloc_from_mat(mat);
262 error:
263 	isl_reordering_free(r);
264 	isl_local_free(local);
265 	return NULL;
266 }
267 
268 /* Extend a vector "v" representing an integer point
269  * in the domain space of "local"
270  * to one that also includes values for the local variables.
271  * All local variables are required to have an explicit representation.
272  * If there are no local variables, then the point is not required
273  * to be integral.
274  */
isl_local_extend_point_vec(__isl_keep isl_local * local,__isl_take isl_vec * v)275 __isl_give isl_vec *isl_local_extend_point_vec(__isl_keep isl_local *local,
276 	__isl_take isl_vec *v)
277 {
278 	isl_size dim, n_div, size;
279 	isl_bool known;
280 	isl_mat *mat = local;
281 
282 	if (!local || !v)
283 		return isl_vec_free(v);
284 	known = isl_local_divs_known(local);
285 	if (known < 0)
286 		return isl_vec_free(v);
287 	if (!known)
288 		isl_die(isl_local_get_ctx(local), isl_error_invalid,
289 			"unknown local variables", return isl_vec_free(v));
290 	dim = isl_local_dim(local, isl_dim_set);
291 	n_div = isl_local_dim(local, isl_dim_div);
292 	size = isl_vec_size(v);
293 	if (dim < 0 || n_div < 0 || size < 0)
294 		return isl_vec_free(v);
295 	if (size != 1 + dim)
296 		isl_die(isl_local_get_ctx(local), isl_error_invalid,
297 			"incorrect size", return isl_vec_free(v));
298 	if (n_div == 0)
299 		return v;
300 	if (!isl_int_is_one(v->el[0]))
301 		isl_die(isl_local_get_ctx(local), isl_error_invalid,
302 			"expecting integer point", return isl_vec_free(v));
303 	{
304 		int i;
305 		v = isl_vec_add_els(v, n_div);
306 		if (!v)
307 			return NULL;
308 
309 		for (i = 0; i < n_div; ++i) {
310 			isl_seq_inner_product(mat->row[i] + 1, v->el,
311 						1 + dim + i, &v->el[1+dim+i]);
312 			isl_int_fdiv_q(v->el[1+dim+i], v->el[1+dim+i],
313 					mat->row[i][0]);
314 		}
315 	}
316 
317 	return v;
318 }
319