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