File: | polly/lib/External/isl/isl_sample.c |
Warning: | line 1331, column 2 Undefined or garbage value returned to caller |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | /* | |||
2 | * Copyright 2008-2009 Katholieke Universiteit Leuven | |||
3 | * | |||
4 | * Use of this software is governed by the MIT license | |||
5 | * | |||
6 | * Written by Sven Verdoolaege, K.U.Leuven, Departement | |||
7 | * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium | |||
8 | */ | |||
9 | ||||
10 | #include <isl_ctx_private.h> | |||
11 | #include <isl_map_private.h> | |||
12 | #include "isl_sample.h" | |||
13 | #include <isl/vec.h> | |||
14 | #include <isl/mat.h> | |||
15 | #include <isl_seq.h> | |||
16 | #include "isl_equalities.h" | |||
17 | #include "isl_tab.h" | |||
18 | #include "isl_basis_reduction.h" | |||
19 | #include <isl_factorization.h> | |||
20 | #include <isl_point_private.h> | |||
21 | #include <isl_options_private.h> | |||
22 | #include <isl_vec_private.h> | |||
23 | ||||
24 | #include <bset_from_bmap.c> | |||
25 | #include <set_to_map.c> | |||
26 | ||||
27 | static __isl_give isl_vec *empty_sample(__isl_take isl_basic_setisl_basic_map *bset) | |||
28 | { | |||
29 | struct isl_vec *vec; | |||
30 | ||||
31 | vec = isl_vec_alloc(bset->ctx, 0); | |||
32 | isl_basic_set_free(bset); | |||
33 | return vec; | |||
34 | } | |||
35 | ||||
36 | /* Construct a zero sample of the same dimension as bset. | |||
37 | * As a special case, if bset is zero-dimensional, this | |||
38 | * function creates a zero-dimensional sample point. | |||
39 | */ | |||
40 | static __isl_give isl_vec *zero_sample(__isl_take isl_basic_setisl_basic_map *bset) | |||
41 | { | |||
42 | isl_size dim; | |||
43 | struct isl_vec *sample; | |||
44 | ||||
45 | dim = isl_basic_set_dim(bset, isl_dim_all); | |||
46 | if (dim < 0) | |||
47 | goto error; | |||
48 | sample = isl_vec_alloc(bset->ctx, 1 + dim); | |||
49 | if (sample) { | |||
50 | isl_int_set_si(sample->el[0], 1)isl_sioimath_set_si((sample->el[0]), 1); | |||
51 | isl_seq_clr(sample->el + 1, dim); | |||
52 | } | |||
53 | isl_basic_set_free(bset); | |||
54 | return sample; | |||
55 | error: | |||
56 | isl_basic_set_free(bset); | |||
57 | return NULL((void*)0); | |||
58 | } | |||
59 | ||||
60 | static __isl_give isl_vec *interval_sample(__isl_take isl_basic_setisl_basic_map *bset) | |||
61 | { | |||
62 | int i; | |||
63 | isl_int t; | |||
64 | struct isl_vec *sample; | |||
65 | ||||
66 | bset = isl_basic_set_simplify(bset); | |||
67 | if (!bset) | |||
68 | return NULL((void*)0); | |||
69 | if (isl_basic_set_plain_is_empty(bset)) | |||
70 | return empty_sample(bset); | |||
71 | if (bset->n_eq == 0 && bset->n_ineq == 0) | |||
72 | return zero_sample(bset); | |||
73 | ||||
74 | sample = isl_vec_alloc(bset->ctx, 2); | |||
75 | if (!sample) | |||
76 | goto error; | |||
77 | if (!bset) | |||
78 | return NULL((void*)0); | |||
79 | isl_int_set_si(sample->block.data[0], 1)isl_sioimath_set_si((sample->block.data[0]), 1); | |||
80 | ||||
81 | if (bset->n_eq > 0) { | |||
82 | isl_assert(bset->ctx, bset->n_eq == 1, goto error)do { if (bset->n_eq == 1) break; do { isl_handle_error(bset ->ctx, isl_error_unknown, "Assertion \"" "bset->n_eq == 1" "\" failed", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 82); goto error; } while (0); } while (0); | |||
83 | isl_assert(bset->ctx, bset->n_ineq == 0, goto error)do { if (bset->n_ineq == 0) break; do { isl_handle_error(bset ->ctx, isl_error_unknown, "Assertion \"" "bset->n_ineq == 0" "\" failed", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 83); goto error; } while (0); } while (0); | |||
84 | if (isl_int_is_one(bset->eq[0][1])(isl_sioimath_cmp_si(*(bset->eq[0][1]), 1) == 0)) | |||
85 | isl_int_neg(sample->el[1], bset->eq[0][0])isl_sioimath_neg((sample->el[1]), *(bset->eq[0][0])); | |||
86 | else { | |||
87 | isl_assert(bset->ctx, isl_int_is_negone(bset->eq[0][1]),do { if ((isl_sioimath_cmp_si(*(bset->eq[0][1]), -1) == 0) ) break; do { isl_handle_error(bset->ctx, isl_error_unknown , "Assertion \"" "(isl_sioimath_cmp_si(*(bset->eq[0][1]), -1) == 0)" "\" failed", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 88); goto error; } while (0); } while (0) | |||
88 | goto error)do { if ((isl_sioimath_cmp_si(*(bset->eq[0][1]), -1) == 0) ) break; do { isl_handle_error(bset->ctx, isl_error_unknown , "Assertion \"" "(isl_sioimath_cmp_si(*(bset->eq[0][1]), -1) == 0)" "\" failed", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 88); goto error; } while (0); } while (0); | |||
89 | isl_int_set(sample->el[1], bset->eq[0][0])isl_sioimath_set((sample->el[1]), *(bset->eq[0][0])); | |||
90 | } | |||
91 | isl_basic_set_free(bset); | |||
92 | return sample; | |||
93 | } | |||
94 | ||||
95 | isl_int_init(t)isl_sioimath_init((t)); | |||
96 | if (isl_int_is_one(bset->ineq[0][1])(isl_sioimath_cmp_si(*(bset->ineq[0][1]), 1) == 0)) | |||
97 | isl_int_neg(sample->block.data[1], bset->ineq[0][0])isl_sioimath_neg((sample->block.data[1]), *(bset->ineq[ 0][0])); | |||
98 | else | |||
99 | isl_int_set(sample->block.data[1], bset->ineq[0][0])isl_sioimath_set((sample->block.data[1]), *(bset->ineq[ 0][0])); | |||
100 | for (i = 1; i < bset->n_ineq; ++i) { | |||
101 | isl_seq_inner_product(sample->block.data, | |||
102 | bset->ineq[i], 2, &t); | |||
103 | if (isl_int_is_neg(t)(isl_sioimath_sgn(*(t)) < 0)) | |||
104 | break; | |||
105 | } | |||
106 | isl_int_clear(t)isl_sioimath_clear((t)); | |||
107 | if (i < bset->n_ineq) { | |||
108 | isl_vec_free(sample); | |||
109 | return empty_sample(bset); | |||
110 | } | |||
111 | ||||
112 | isl_basic_set_free(bset); | |||
113 | return sample; | |||
114 | error: | |||
115 | isl_basic_set_free(bset); | |||
116 | isl_vec_free(sample); | |||
117 | return NULL((void*)0); | |||
118 | } | |||
119 | ||||
120 | /* Find a sample integer point, if any, in bset, which is known | |||
121 | * to have equalities. If bset contains no integer points, then | |||
122 | * return a zero-length vector. | |||
123 | * We simply remove the known equalities, compute a sample | |||
124 | * in the resulting bset, using the specified recurse function, | |||
125 | * and then transform the sample back to the original space. | |||
126 | */ | |||
127 | static __isl_give isl_vec *sample_eq(__isl_take isl_basic_setisl_basic_map *bset, | |||
128 | __isl_give isl_vec *(*recurse)(__isl_take isl_basic_setisl_basic_map *)) | |||
129 | { | |||
130 | struct isl_mat *T; | |||
131 | struct isl_vec *sample; | |||
132 | ||||
133 | if (!bset) | |||
134 | return NULL((void*)0); | |||
135 | ||||
136 | bset = isl_basic_set_remove_equalities(bset, &T, NULL((void*)0)); | |||
137 | sample = recurse(bset); | |||
138 | if (!sample || sample->size == 0) | |||
139 | isl_mat_free(T); | |||
140 | else | |||
141 | sample = isl_mat_vec_product(T, sample); | |||
142 | return sample; | |||
143 | } | |||
144 | ||||
145 | /* Return a matrix containing the equalities of the tableau | |||
146 | * in constraint form. The tableau is assumed to have | |||
147 | * an associated bset that has been kept up-to-date. | |||
148 | */ | |||
149 | static struct isl_mat *tab_equalities(struct isl_tab *tab) | |||
150 | { | |||
151 | int i, j; | |||
152 | int n_eq; | |||
153 | struct isl_mat *eq; | |||
154 | struct isl_basic_setisl_basic_map *bset; | |||
155 | ||||
156 | if (!tab) | |||
157 | return NULL((void*)0); | |||
158 | ||||
159 | bset = isl_tab_peek_bset(tab); | |||
160 | isl_assert(tab->mat->ctx, bset, return NULL)do { if (bset) break; do { isl_handle_error(tab->mat->ctx , isl_error_unknown, "Assertion \"" "bset" "\" failed", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 160); return ((void*)0); } while (0); } while (0); | |||
161 | ||||
162 | n_eq = tab->n_var - tab->n_col + tab->n_dead; | |||
163 | if (tab->empty || n_eq == 0) | |||
164 | return isl_mat_alloc(tab->mat->ctx, 0, tab->n_var); | |||
165 | if (n_eq == tab->n_var) | |||
166 | return isl_mat_identity(tab->mat->ctx, tab->n_var); | |||
167 | ||||
168 | eq = isl_mat_alloc(tab->mat->ctx, n_eq, tab->n_var); | |||
169 | if (!eq) | |||
170 | return NULL((void*)0); | |||
171 | for (i = 0, j = 0; i < tab->n_con; ++i) { | |||
172 | if (tab->con[i].is_row) | |||
173 | continue; | |||
174 | if (tab->con[i].index >= 0 && tab->con[i].index >= tab->n_dead) | |||
175 | continue; | |||
176 | if (i < bset->n_eq) | |||
177 | isl_seq_cpy(eq->row[j], bset->eq[i] + 1, tab->n_var); | |||
178 | else | |||
179 | isl_seq_cpy(eq->row[j], | |||
180 | bset->ineq[i - bset->n_eq] + 1, tab->n_var); | |||
181 | ++j; | |||
182 | } | |||
183 | isl_assert(bset->ctx, j == n_eq, goto error)do { if (j == n_eq) break; do { isl_handle_error(bset->ctx , isl_error_unknown, "Assertion \"" "j == n_eq" "\" failed", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 183); goto error; } while (0); } while (0); | |||
184 | return eq; | |||
185 | error: | |||
186 | isl_mat_free(eq); | |||
187 | return NULL((void*)0); | |||
188 | } | |||
189 | ||||
190 | /* Compute and return an initial basis for the bounded tableau "tab". | |||
191 | * | |||
192 | * If the tableau is either full-dimensional or zero-dimensional, | |||
193 | * the we simply return an identity matrix. | |||
194 | * Otherwise, we construct a basis whose first directions correspond | |||
195 | * to equalities. | |||
196 | */ | |||
197 | static struct isl_mat *initial_basis(struct isl_tab *tab) | |||
198 | { | |||
199 | int n_eq; | |||
200 | struct isl_mat *eq; | |||
201 | struct isl_mat *Q; | |||
202 | ||||
203 | tab->n_unbounded = 0; | |||
204 | tab->n_zero = n_eq = tab->n_var - tab->n_col + tab->n_dead; | |||
205 | if (tab->empty || n_eq == 0 || n_eq == tab->n_var) | |||
206 | return isl_mat_identity(tab->mat->ctx, 1 + tab->n_var); | |||
207 | ||||
208 | eq = tab_equalities(tab); | |||
209 | eq = isl_mat_left_hermite(eq, 0, NULL((void*)0), &Q); | |||
210 | if (!eq) | |||
211 | return NULL((void*)0); | |||
212 | isl_mat_free(eq); | |||
213 | ||||
214 | Q = isl_mat_lin_to_aff(Q); | |||
215 | return Q; | |||
216 | } | |||
217 | ||||
218 | /* Compute the minimum of the current ("level") basis row over "tab" | |||
219 | * and store the result in position "level" of "min". | |||
220 | * | |||
221 | * This function assumes that at least one more row and at least | |||
222 | * one more element in the constraint array are available in the tableau. | |||
223 | */ | |||
224 | static enum isl_lp_result compute_min(isl_ctx *ctx, struct isl_tab *tab, | |||
225 | __isl_keep isl_vec *min, int level) | |||
226 | { | |||
227 | return isl_tab_min(tab, tab->basis->row[1 + level], | |||
228 | ctx->one, &min->el[level], NULL((void*)0), 0); | |||
229 | } | |||
230 | ||||
231 | /* Compute the maximum of the current ("level") basis row over "tab" | |||
232 | * and store the result in position "level" of "max". | |||
233 | * | |||
234 | * This function assumes that at least one more row and at least | |||
235 | * one more element in the constraint array are available in the tableau. | |||
236 | */ | |||
237 | static enum isl_lp_result compute_max(isl_ctx *ctx, struct isl_tab *tab, | |||
238 | __isl_keep isl_vec *max, int level) | |||
239 | { | |||
240 | enum isl_lp_result res; | |||
241 | unsigned dim = tab->n_var; | |||
242 | ||||
243 | isl_seq_neg(tab->basis->row[1 + level] + 1, | |||
244 | tab->basis->row[1 + level] + 1, dim); | |||
245 | res = isl_tab_min(tab, tab->basis->row[1 + level], | |||
246 | ctx->one, &max->el[level], NULL((void*)0), 0); | |||
247 | isl_seq_neg(tab->basis->row[1 + level] + 1, | |||
248 | tab->basis->row[1 + level] + 1, dim); | |||
249 | isl_int_neg(max->el[level], max->el[level])isl_sioimath_neg((max->el[level]), *(max->el[level])); | |||
250 | ||||
251 | return res; | |||
252 | } | |||
253 | ||||
254 | /* Perform a greedy search for an integer point in the set represented | |||
255 | * by "tab", given that the minimal rational value (rounded up to the | |||
256 | * nearest integer) at "level" is smaller than the maximal rational | |||
257 | * value (rounded down to the nearest integer). | |||
258 | * | |||
259 | * Return 1 if we have found an integer point (if tab->n_unbounded > 0 | |||
260 | * then we may have only found integer values for the bounded dimensions | |||
261 | * and it is the responsibility of the caller to extend this solution | |||
262 | * to the unbounded dimensions). | |||
263 | * Return 0 if greedy search did not result in a solution. | |||
264 | * Return -1 if some error occurred. | |||
265 | * | |||
266 | * We assign a value half-way between the minimum and the maximum | |||
267 | * to the current dimension and check if the minimal value of the | |||
268 | * next dimension is still smaller than (or equal) to the maximal value. | |||
269 | * We continue this process until either | |||
270 | * - the minimal value (rounded up) is greater than the maximal value | |||
271 | * (rounded down). In this case, greedy search has failed. | |||
272 | * - we have exhausted all bounded dimensions, meaning that we have | |||
273 | * found a solution. | |||
274 | * - the sample value of the tableau is integral. | |||
275 | * - some error has occurred. | |||
276 | */ | |||
277 | static int greedy_search(isl_ctx *ctx, struct isl_tab *tab, | |||
278 | __isl_keep isl_vec *min, __isl_keep isl_vec *max, int level) | |||
279 | { | |||
280 | struct isl_tab_undo *snap; | |||
281 | enum isl_lp_result res; | |||
282 | ||||
283 | snap = isl_tab_snap(tab); | |||
284 | ||||
285 | do { | |||
286 | isl_int_add(tab->basis->row[1 + level][0],isl_sioimath_add((tab->basis->row[1 + level][0]), *(min ->el[level]), *(max->el[level])) | |||
287 | min->el[level], max->el[level])isl_sioimath_add((tab->basis->row[1 + level][0]), *(min ->el[level]), *(max->el[level])); | |||
288 | isl_int_fdiv_q_ui(tab->basis->row[1 + level][0],isl_sioimath_fdiv_q_ui((tab->basis->row[1 + level][0]), *(tab->basis->row[1 + level][0]), 2) | |||
289 | tab->basis->row[1 + level][0], 2)isl_sioimath_fdiv_q_ui((tab->basis->row[1 + level][0]), *(tab->basis->row[1 + level][0]), 2); | |||
290 | isl_int_neg(tab->basis->row[1 + level][0],isl_sioimath_neg((tab->basis->row[1 + level][0]), *(tab ->basis->row[1 + level][0])) | |||
291 | tab->basis->row[1 + level][0])isl_sioimath_neg((tab->basis->row[1 + level][0]), *(tab ->basis->row[1 + level][0])); | |||
292 | if (isl_tab_add_valid_eq(tab, tab->basis->row[1 + level]) < 0) | |||
293 | return -1; | |||
294 | isl_int_set_si(tab->basis->row[1 + level][0], 0)isl_sioimath_set_si((tab->basis->row[1 + level][0]), 0); | |||
295 | ||||
296 | if (++level >= tab->n_var - tab->n_unbounded) | |||
297 | return 1; | |||
298 | if (isl_tab_sample_is_integer(tab)) | |||
299 | return 1; | |||
300 | ||||
301 | res = compute_min(ctx, tab, min, level); | |||
302 | if (res == isl_lp_error) | |||
303 | return -1; | |||
304 | if (res != isl_lp_ok) | |||
305 | isl_die(ctx, isl_error_internal,do { isl_handle_error(ctx, isl_error_internal, "expecting bounded rational solution" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 307); return -1; } while (0) | |||
306 | "expecting bounded rational solution",do { isl_handle_error(ctx, isl_error_internal, "expecting bounded rational solution" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 307); return -1; } while (0) | |||
307 | return -1)do { isl_handle_error(ctx, isl_error_internal, "expecting bounded rational solution" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 307); return -1; } while (0); | |||
308 | res = compute_max(ctx, tab, max, level); | |||
309 | if (res == isl_lp_error) | |||
310 | return -1; | |||
311 | if (res != isl_lp_ok) | |||
312 | isl_die(ctx, isl_error_internal,do { isl_handle_error(ctx, isl_error_internal, "expecting bounded rational solution" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 314); return -1; } while (0) | |||
313 | "expecting bounded rational solution",do { isl_handle_error(ctx, isl_error_internal, "expecting bounded rational solution" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 314); return -1; } while (0) | |||
314 | return -1)do { isl_handle_error(ctx, isl_error_internal, "expecting bounded rational solution" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 314); return -1; } while (0); | |||
315 | } while (isl_int_le(min->el[level], max->el[level])(isl_sioimath_cmp(*(min->el[level]), *(max->el[level])) <= 0)); | |||
316 | ||||
317 | if (isl_tab_rollback(tab, snap) < 0) | |||
318 | return -1; | |||
319 | ||||
320 | return 0; | |||
321 | } | |||
322 | ||||
323 | /* Given a tableau representing a set, find and return | |||
324 | * an integer point in the set, if there is any. | |||
325 | * | |||
326 | * We perform a depth first search | |||
327 | * for an integer point, by scanning all possible values in the range | |||
328 | * attained by a basis vector, where an initial basis may have been set | |||
329 | * by the calling function. Otherwise an initial basis that exploits | |||
330 | * the equalities in the tableau is created. | |||
331 | * tab->n_zero is currently ignored and is clobbered by this function. | |||
332 | * | |||
333 | * The tableau is allowed to have unbounded direction, but then | |||
334 | * the calling function needs to set an initial basis, with the | |||
335 | * unbounded directions last and with tab->n_unbounded set | |||
336 | * to the number of unbounded directions. | |||
337 | * Furthermore, the calling functions needs to add shifted copies | |||
338 | * of all constraints involving unbounded directions to ensure | |||
339 | * that any feasible rational value in these directions can be rounded | |||
340 | * up to yield a feasible integer value. | |||
341 | * In particular, let B define the given basis x' = B x | |||
342 | * and let T be the inverse of B, i.e., X = T x'. | |||
343 | * Let a x + c >= 0 be a constraint of the set represented by the tableau, | |||
344 | * or a T x' + c >= 0 in terms of the given basis. Assume that | |||
345 | * the bounded directions have an integer value, then we can safely | |||
346 | * round up the values for the unbounded directions if we make sure | |||
347 | * that x' not only satisfies the original constraint, but also | |||
348 | * the constraint "a T x' + c + s >= 0" with s the sum of all | |||
349 | * negative values in the last n_unbounded entries of "a T". | |||
350 | * The calling function therefore needs to add the constraint | |||
351 | * a x + c + s >= 0. The current function then scans the first | |||
352 | * directions for an integer value and once those have been found, | |||
353 | * it can compute "T ceil(B x)" to yield an integer point in the set. | |||
354 | * Note that during the search, the first rows of B may be changed | |||
355 | * by a basis reduction, but the last n_unbounded rows of B remain | |||
356 | * unaltered and are also not mixed into the first rows. | |||
357 | * | |||
358 | * The search is implemented iteratively. "level" identifies the current | |||
359 | * basis vector. "init" is true if we want the first value at the current | |||
360 | * level and false if we want the next value. | |||
361 | * | |||
362 | * At the start of each level, we first check if we can find a solution | |||
363 | * using greedy search. If not, we continue with the exhaustive search. | |||
364 | * | |||
365 | * The initial basis is the identity matrix. If the range in some direction | |||
366 | * contains more than one integer value, we perform basis reduction based | |||
367 | * on the value of ctx->opt->gbr | |||
368 | * - ISL_GBR_NEVER: never perform basis reduction | |||
369 | * - ISL_GBR_ONCE: only perform basis reduction the first | |||
370 | * time such a range is encountered | |||
371 | * - ISL_GBR_ALWAYS: always perform basis reduction when | |||
372 | * such a range is encountered | |||
373 | * | |||
374 | * When ctx->opt->gbr is set to ISL_GBR_ALWAYS, then we allow the basis | |||
375 | * reduction computation to return early. That is, as soon as it | |||
376 | * finds a reasonable first direction. | |||
377 | */ | |||
378 | __isl_give isl_vec *isl_tab_sample(struct isl_tab *tab) | |||
379 | { | |||
380 | unsigned dim; | |||
381 | unsigned gbr; | |||
382 | struct isl_ctx *ctx; | |||
383 | struct isl_vec *sample; | |||
384 | struct isl_vec *min; | |||
385 | struct isl_vec *max; | |||
386 | enum isl_lp_result res; | |||
387 | int level; | |||
388 | int init; | |||
389 | int reduced; | |||
390 | struct isl_tab_undo **snap; | |||
391 | ||||
392 | if (!tab) | |||
393 | return NULL((void*)0); | |||
394 | if (tab->empty) | |||
395 | return isl_vec_alloc(tab->mat->ctx, 0); | |||
396 | ||||
397 | if (!tab->basis) | |||
398 | tab->basis = initial_basis(tab); | |||
399 | if (!tab->basis) | |||
400 | return NULL((void*)0); | |||
401 | isl_assert(tab->mat->ctx, tab->basis->n_row == tab->n_var + 1,do { if (tab->basis->n_row == tab->n_var + 1) break; do { isl_handle_error(tab->mat->ctx, isl_error_unknown , "Assertion \"" "tab->basis->n_row == tab->n_var + 1" "\" failed", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 402); return ((void*)0); } while (0); } while (0) | |||
402 | return NULL)do { if (tab->basis->n_row == tab->n_var + 1) break; do { isl_handle_error(tab->mat->ctx, isl_error_unknown , "Assertion \"" "tab->basis->n_row == tab->n_var + 1" "\" failed", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 402); return ((void*)0); } while (0); } while (0); | |||
403 | isl_assert(tab->mat->ctx, tab->basis->n_col == tab->n_var + 1,do { if (tab->basis->n_col == tab->n_var + 1) break; do { isl_handle_error(tab->mat->ctx, isl_error_unknown , "Assertion \"" "tab->basis->n_col == tab->n_var + 1" "\" failed", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 404); return ((void*)0); } while (0); } while (0) | |||
404 | return NULL)do { if (tab->basis->n_col == tab->n_var + 1) break; do { isl_handle_error(tab->mat->ctx, isl_error_unknown , "Assertion \"" "tab->basis->n_col == tab->n_var + 1" "\" failed", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 404); return ((void*)0); } while (0); } while (0); | |||
405 | ||||
406 | ctx = tab->mat->ctx; | |||
407 | dim = tab->n_var; | |||
408 | gbr = ctx->opt->gbr; | |||
409 | ||||
410 | if (tab->n_unbounded == tab->n_var) { | |||
411 | sample = isl_tab_get_sample_value(tab); | |||
412 | sample = isl_mat_vec_product(isl_mat_copy(tab->basis), sample); | |||
413 | sample = isl_vec_ceil(sample); | |||
414 | sample = isl_mat_vec_inverse_product(isl_mat_copy(tab->basis), | |||
415 | sample); | |||
416 | return sample; | |||
417 | } | |||
418 | ||||
419 | if (isl_tab_extend_cons(tab, dim + 1) < 0) | |||
420 | return NULL((void*)0); | |||
421 | ||||
422 | min = isl_vec_alloc(ctx, dim); | |||
423 | max = isl_vec_alloc(ctx, dim); | |||
424 | snap = isl_alloc_array(ctx, struct isl_tab_undo *, dim)((struct isl_tab_undo * *)isl_malloc_or_die(ctx, (dim)*sizeof (struct isl_tab_undo *))); | |||
425 | ||||
426 | if (!min || !max || !snap) | |||
427 | goto error; | |||
428 | ||||
429 | level = 0; | |||
430 | init = 1; | |||
431 | reduced = 0; | |||
432 | ||||
433 | while (level >= 0) { | |||
434 | if (init) { | |||
435 | int choice; | |||
436 | ||||
437 | res = compute_min(ctx, tab, min, level); | |||
438 | if (res == isl_lp_error) | |||
439 | goto error; | |||
440 | if (res != isl_lp_ok) | |||
441 | isl_die(ctx, isl_error_internal,do { isl_handle_error(ctx, isl_error_internal, "expecting bounded rational solution" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 443); goto error; } while (0) | |||
442 | "expecting bounded rational solution",do { isl_handle_error(ctx, isl_error_internal, "expecting bounded rational solution" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 443); goto error; } while (0) | |||
443 | goto error)do { isl_handle_error(ctx, isl_error_internal, "expecting bounded rational solution" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 443); goto error; } while (0); | |||
444 | if (isl_tab_sample_is_integer(tab)) | |||
445 | break; | |||
446 | res = compute_max(ctx, tab, max, level); | |||
447 | if (res == isl_lp_error) | |||
448 | goto error; | |||
449 | if (res != isl_lp_ok) | |||
450 | isl_die(ctx, isl_error_internal,do { isl_handle_error(ctx, isl_error_internal, "expecting bounded rational solution" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 452); goto error; } while (0) | |||
451 | "expecting bounded rational solution",do { isl_handle_error(ctx, isl_error_internal, "expecting bounded rational solution" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 452); goto error; } while (0) | |||
452 | goto error)do { isl_handle_error(ctx, isl_error_internal, "expecting bounded rational solution" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 452); goto error; } while (0); | |||
453 | if (isl_tab_sample_is_integer(tab)) | |||
454 | break; | |||
455 | choice = isl_int_lt(min->el[level], max->el[level])(isl_sioimath_cmp(*(min->el[level]), *(max->el[level])) < 0); | |||
456 | if (choice) { | |||
457 | int g; | |||
458 | g = greedy_search(ctx, tab, min, max, level); | |||
459 | if (g < 0) | |||
460 | goto error; | |||
461 | if (g) | |||
462 | break; | |||
463 | } | |||
464 | if (!reduced && choice && | |||
465 | ctx->opt->gbr != ISL_GBR_NEVER0) { | |||
466 | unsigned gbr_only_first; | |||
467 | if (ctx->opt->gbr == ISL_GBR_ONCE1) | |||
468 | ctx->opt->gbr = ISL_GBR_NEVER0; | |||
469 | tab->n_zero = level; | |||
470 | gbr_only_first = ctx->opt->gbr_only_first; | |||
471 | ctx->opt->gbr_only_first = | |||
472 | ctx->opt->gbr == ISL_GBR_ALWAYS2; | |||
473 | tab = isl_tab_compute_reduced_basis(tab); | |||
474 | ctx->opt->gbr_only_first = gbr_only_first; | |||
475 | if (!tab || !tab->basis) | |||
476 | goto error; | |||
477 | reduced = 1; | |||
478 | continue; | |||
479 | } | |||
480 | reduced = 0; | |||
481 | snap[level] = isl_tab_snap(tab); | |||
482 | } else | |||
483 | isl_int_add_ui(min->el[level], min->el[level], 1)isl_sioimath_add_ui((min->el[level]), *(min->el[level]) , 1); | |||
484 | ||||
485 | if (isl_int_gt(min->el[level], max->el[level])(isl_sioimath_cmp(*(min->el[level]), *(max->el[level])) > 0)) { | |||
486 | level--; | |||
487 | init = 0; | |||
488 | if (level >= 0) | |||
489 | if (isl_tab_rollback(tab, snap[level]) < 0) | |||
490 | goto error; | |||
491 | continue; | |||
492 | } | |||
493 | isl_int_neg(tab->basis->row[1 + level][0], min->el[level])isl_sioimath_neg((tab->basis->row[1 + level][0]), *(min ->el[level])); | |||
494 | if (isl_tab_add_valid_eq(tab, tab->basis->row[1 + level]) < 0) | |||
495 | goto error; | |||
496 | isl_int_set_si(tab->basis->row[1 + level][0], 0)isl_sioimath_set_si((tab->basis->row[1 + level][0]), 0); | |||
497 | if (level + tab->n_unbounded < dim - 1) { | |||
498 | ++level; | |||
499 | init = 1; | |||
500 | continue; | |||
501 | } | |||
502 | break; | |||
503 | } | |||
504 | ||||
505 | if (level >= 0) { | |||
506 | sample = isl_tab_get_sample_value(tab); | |||
507 | if (!sample) | |||
508 | goto error; | |||
509 | if (tab->n_unbounded && !isl_int_is_one(sample->el[0])(isl_sioimath_cmp_si(*(sample->el[0]), 1) == 0)) { | |||
510 | sample = isl_mat_vec_product(isl_mat_copy(tab->basis), | |||
511 | sample); | |||
512 | sample = isl_vec_ceil(sample); | |||
513 | sample = isl_mat_vec_inverse_product( | |||
514 | isl_mat_copy(tab->basis), sample); | |||
515 | } | |||
516 | } else | |||
517 | sample = isl_vec_alloc(ctx, 0); | |||
518 | ||||
519 | ctx->opt->gbr = gbr; | |||
520 | isl_vec_free(min); | |||
521 | isl_vec_free(max); | |||
522 | free(snap); | |||
523 | return sample; | |||
524 | error: | |||
525 | ctx->opt->gbr = gbr; | |||
526 | isl_vec_free(min); | |||
527 | isl_vec_free(max); | |||
528 | free(snap); | |||
529 | return NULL((void*)0); | |||
530 | } | |||
531 | ||||
532 | static __isl_give isl_vec *sample_bounded(__isl_take isl_basic_setisl_basic_map *bset); | |||
533 | ||||
534 | /* Internal data for factored_sample. | |||
535 | * "sample" collects the sample and may get reset to a zero-length vector | |||
536 | * signaling the absence of a sample vector. | |||
537 | * "pos" is the position of the contribution of the next factor. | |||
538 | */ | |||
539 | struct isl_factored_sample_data { | |||
540 | isl_vec *sample; | |||
541 | int pos; | |||
542 | }; | |||
543 | ||||
544 | /* isl_factorizer_every_factor_basic_set callback that extends | |||
545 | * the sample in data->sample with the contribution | |||
546 | * of the factor "bset". | |||
547 | * If "bset" turns out to be empty, then the product is empty too and | |||
548 | * no further factors need to be considered. | |||
549 | */ | |||
550 | static isl_bool factor_sample(__isl_keep isl_basic_setisl_basic_map *bset, void *user) | |||
551 | { | |||
552 | struct isl_factored_sample_data *data = user; | |||
553 | isl_vec *sample; | |||
554 | isl_size n; | |||
555 | ||||
556 | n = isl_basic_set_dim(bset, isl_dim_set); | |||
557 | if (n < 0) | |||
558 | return isl_bool_error; | |||
559 | ||||
560 | sample = sample_bounded(isl_basic_set_copy(bset)); | |||
561 | if (!sample) | |||
562 | return isl_bool_error; | |||
563 | if (sample->size == 0) { | |||
564 | isl_vec_free(data->sample); | |||
565 | data->sample = sample; | |||
566 | return isl_bool_false; | |||
567 | } | |||
568 | isl_seq_cpy(data->sample->el + data->pos, sample->el + 1, n); | |||
569 | isl_vec_free(sample); | |||
570 | data->pos += n; | |||
571 | ||||
572 | return isl_bool_true; | |||
573 | } | |||
574 | ||||
575 | /* Compute a sample point of the given basic set, based on the given, | |||
576 | * non-trivial factorization. | |||
577 | */ | |||
578 | static __isl_give isl_vec *factored_sample(__isl_take isl_basic_setisl_basic_map *bset, | |||
579 | __isl_take isl_factorizer *f) | |||
580 | { | |||
581 | struct isl_factored_sample_data data = { NULL((void*)0) }; | |||
582 | isl_ctx *ctx; | |||
583 | isl_size total; | |||
584 | isl_bool every; | |||
585 | ||||
586 | ctx = isl_basic_set_get_ctx(bset); | |||
587 | total = isl_basic_set_dim(bset, isl_dim_all); | |||
588 | if (!ctx || total < 0) | |||
589 | goto error; | |||
590 | ||||
591 | data.sample = isl_vec_alloc(ctx, 1 + total); | |||
592 | if (!data.sample) | |||
593 | goto error; | |||
594 | isl_int_set_si(data.sample->el[0], 1)isl_sioimath_set_si((data.sample->el[0]), 1); | |||
595 | data.pos = 1; | |||
596 | ||||
597 | every = isl_factorizer_every_factor_basic_set(f, &factor_sample, &data); | |||
598 | if (every < 0) { | |||
599 | data.sample = isl_vec_free(data.sample); | |||
600 | } else if (every) { | |||
601 | isl_morph *morph; | |||
602 | ||||
603 | morph = isl_morph_inverse(isl_morph_copy(f->morph)); | |||
604 | data.sample = isl_morph_vec(morph, data.sample); | |||
605 | } | |||
606 | ||||
607 | isl_basic_set_free(bset); | |||
608 | isl_factorizer_free(f); | |||
609 | return data.sample; | |||
610 | error: | |||
611 | isl_basic_set_free(bset); | |||
612 | isl_factorizer_free(f); | |||
613 | isl_vec_free(data.sample); | |||
614 | return NULL((void*)0); | |||
615 | } | |||
616 | ||||
617 | /* Given a basic set that is known to be bounded, find and return | |||
618 | * an integer point in the basic set, if there is any. | |||
619 | * | |||
620 | * After handling some trivial cases, we construct a tableau | |||
621 | * and then use isl_tab_sample to find a sample, passing it | |||
622 | * the identity matrix as initial basis. | |||
623 | */ | |||
624 | static __isl_give isl_vec *sample_bounded(__isl_take isl_basic_setisl_basic_map *bset) | |||
625 | { | |||
626 | isl_size dim; | |||
627 | struct isl_vec *sample; | |||
628 | struct isl_tab *tab = NULL((void*)0); | |||
629 | isl_factorizer *f; | |||
630 | ||||
631 | if (!bset) | |||
632 | return NULL((void*)0); | |||
633 | ||||
634 | if (isl_basic_set_plain_is_empty(bset)) | |||
635 | return empty_sample(bset); | |||
636 | ||||
637 | dim = isl_basic_set_dim(bset, isl_dim_all); | |||
638 | if (dim < 0) | |||
639 | bset = isl_basic_set_free(bset); | |||
640 | if (dim == 0) | |||
641 | return zero_sample(bset); | |||
642 | if (dim == 1) | |||
643 | return interval_sample(bset); | |||
644 | if (bset->n_eq > 0) | |||
645 | return sample_eq(bset, sample_bounded); | |||
646 | ||||
647 | f = isl_basic_set_factorizer(bset); | |||
648 | if (!f) | |||
649 | goto error; | |||
650 | if (f->n_group != 0) | |||
651 | return factored_sample(bset, f); | |||
652 | isl_factorizer_free(f); | |||
653 | ||||
654 | tab = isl_tab_from_basic_set(bset, 1); | |||
655 | if (tab && tab->empty) { | |||
656 | isl_tab_free(tab); | |||
657 | ISL_F_SET(bset, ISL_BASIC_SET_EMPTY)(((bset)->flags) |= ((1 << 1))); | |||
658 | sample = isl_vec_alloc(isl_basic_set_get_ctx(bset), 0); | |||
659 | isl_basic_set_free(bset); | |||
660 | return sample; | |||
661 | } | |||
662 | ||||
663 | if (!ISL_F_ISSET(bset, ISL_BASIC_SET_NO_IMPLICIT)(!!(((bset)->flags) & ((1 << 2))))) | |||
664 | if (isl_tab_detect_implicit_equalities(tab) < 0) | |||
665 | goto error; | |||
666 | ||||
667 | sample = isl_tab_sample(tab); | |||
668 | if (!sample) | |||
669 | goto error; | |||
670 | ||||
671 | if (sample->size > 0) { | |||
672 | isl_vec_free(bset->sample); | |||
673 | bset->sample = isl_vec_copy(sample); | |||
674 | } | |||
675 | ||||
676 | isl_basic_set_free(bset); | |||
677 | isl_tab_free(tab); | |||
678 | return sample; | |||
679 | error: | |||
680 | isl_basic_set_free(bset); | |||
681 | isl_tab_free(tab); | |||
682 | return NULL((void*)0); | |||
683 | } | |||
684 | ||||
685 | /* Given a basic set "bset" and a value "sample" for the first coordinates | |||
686 | * of bset, plug in these values and drop the corresponding coordinates. | |||
687 | * | |||
688 | * We do this by computing the preimage of the transformation | |||
689 | * | |||
690 | * [ 1 0 ] | |||
691 | * x = [ s 0 ] x' | |||
692 | * [ 0 I ] | |||
693 | * | |||
694 | * where [1 s] is the sample value and I is the identity matrix of the | |||
695 | * appropriate dimension. | |||
696 | */ | |||
697 | static __isl_give isl_basic_setisl_basic_map *plug_in(__isl_take isl_basic_setisl_basic_map *bset, | |||
698 | __isl_take isl_vec *sample) | |||
699 | { | |||
700 | int i; | |||
701 | isl_size total; | |||
702 | struct isl_mat *T; | |||
703 | ||||
704 | total = isl_basic_set_dim(bset, isl_dim_all); | |||
705 | if (total < 0 || !sample) | |||
706 | goto error; | |||
707 | ||||
708 | T = isl_mat_alloc(bset->ctx, 1 + total, 1 + total - (sample->size - 1)); | |||
709 | if (!T) | |||
710 | goto error; | |||
711 | ||||
712 | for (i = 0; i < sample->size; ++i) { | |||
713 | isl_int_set(T->row[i][0], sample->el[i])isl_sioimath_set((T->row[i][0]), *(sample->el[i])); | |||
714 | isl_seq_clr(T->row[i] + 1, T->n_col - 1); | |||
715 | } | |||
716 | for (i = 0; i < T->n_col - 1; ++i) { | |||
717 | isl_seq_clr(T->row[sample->size + i], T->n_col); | |||
718 | isl_int_set_si(T->row[sample->size + i][1 + i], 1)isl_sioimath_set_si((T->row[sample->size + i][1 + i]), 1 ); | |||
719 | } | |||
720 | isl_vec_free(sample); | |||
721 | ||||
722 | bset = isl_basic_set_preimage(bset, T); | |||
723 | return bset; | |||
724 | error: | |||
725 | isl_basic_set_free(bset); | |||
726 | isl_vec_free(sample); | |||
727 | return NULL((void*)0); | |||
728 | } | |||
729 | ||||
730 | /* Given a basic set "bset", return any (possibly non-integer) point | |||
731 | * in the basic set. | |||
732 | */ | |||
733 | static __isl_give isl_vec *rational_sample(__isl_take isl_basic_setisl_basic_map *bset) | |||
734 | { | |||
735 | struct isl_tab *tab; | |||
736 | struct isl_vec *sample; | |||
737 | ||||
738 | if (!bset) | |||
739 | return NULL((void*)0); | |||
740 | ||||
741 | tab = isl_tab_from_basic_set(bset, 0); | |||
742 | sample = isl_tab_get_sample_value(tab); | |||
743 | isl_tab_free(tab); | |||
744 | ||||
745 | isl_basic_set_free(bset); | |||
746 | ||||
747 | return sample; | |||
748 | } | |||
749 | ||||
750 | /* Given a linear cone "cone" and a rational point "vec", | |||
751 | * construct a polyhedron with shifted copies of the constraints in "cone", | |||
752 | * i.e., a polyhedron with "cone" as its recession cone, such that each | |||
753 | * point x in this polyhedron is such that the unit box positioned at x | |||
754 | * lies entirely inside the affine cone 'vec + cone'. | |||
755 | * Any rational point in this polyhedron may therefore be rounded up | |||
756 | * to yield an integer point that lies inside said affine cone. | |||
757 | * | |||
758 | * Denote the constraints of cone by "<a_i, x> >= 0" and the rational | |||
759 | * point "vec" by v/d. | |||
760 | * Let b_i = <a_i, v>. Then the affine cone 'vec + cone' is given | |||
761 | * by <a_i, x> - b/d >= 0. | |||
762 | * The polyhedron <a_i, x> - ceil{b/d} >= 0 is a subset of this affine cone. | |||
763 | * We prefer this polyhedron over the actual affine cone because it doesn't | |||
764 | * require a scaling of the constraints. | |||
765 | * If each of the vertices of the unit cube positioned at x lies inside | |||
766 | * this polyhedron, then the whole unit cube at x lies inside the affine cone. | |||
767 | * We therefore impose that x' = x + \sum e_i, for any selection of unit | |||
768 | * vectors lies inside the polyhedron, i.e., | |||
769 | * | |||
770 | * <a_i, x'> - ceil{b/d} = <a_i, x> + sum a_i - ceil{b/d} >= 0 | |||
771 | * | |||
772 | * The most stringent of these constraints is the one that selects | |||
773 | * all negative a_i, so the polyhedron we are looking for has constraints | |||
774 | * | |||
775 | * <a_i, x> + sum_{a_i < 0} a_i - ceil{b/d} >= 0 | |||
776 | * | |||
777 | * Note that if cone were known to have only non-negative rays | |||
778 | * (which can be accomplished by a unimodular transformation), | |||
779 | * then we would only have to check the points x' = x + e_i | |||
780 | * and we only have to add the smallest negative a_i (if any) | |||
781 | * instead of the sum of all negative a_i. | |||
782 | */ | |||
783 | static __isl_give isl_basic_setisl_basic_map *shift_cone(__isl_take isl_basic_setisl_basic_map *cone, | |||
784 | __isl_take isl_vec *vec) | |||
785 | { | |||
786 | int i, j, k; | |||
787 | isl_size total; | |||
788 | ||||
789 | struct isl_basic_setisl_basic_map *shift = NULL((void*)0); | |||
790 | ||||
791 | total = isl_basic_set_dim(cone, isl_dim_all); | |||
792 | if (total < 0 || !vec) | |||
793 | goto error; | |||
794 | ||||
795 | isl_assert(cone->ctx, cone->n_eq == 0, goto error)do { if (cone->n_eq == 0) break; do { isl_handle_error(cone ->ctx, isl_error_unknown, "Assertion \"" "cone->n_eq == 0" "\" failed", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 795); goto error; } while (0); } while (0); | |||
796 | ||||
797 | shift = isl_basic_set_alloc_space(isl_basic_set_get_space(cone), | |||
798 | 0, 0, cone->n_ineq); | |||
799 | ||||
800 | for (i = 0; i < cone->n_ineq; ++i) { | |||
801 | k = isl_basic_set_alloc_inequality(shift); | |||
802 | if (k < 0) | |||
803 | goto error; | |||
804 | isl_seq_cpy(shift->ineq[k] + 1, cone->ineq[i] + 1, total); | |||
805 | isl_seq_inner_product(shift->ineq[k] + 1, vec->el + 1, total, | |||
806 | &shift->ineq[k][0]); | |||
807 | isl_int_cdiv_q(shift->ineq[k][0],isl_sioimath_cdiv_q((shift->ineq[k][0]), *(shift->ineq[ k][0]), *(vec->el[0])) | |||
808 | shift->ineq[k][0], vec->el[0])isl_sioimath_cdiv_q((shift->ineq[k][0]), *(shift->ineq[ k][0]), *(vec->el[0])); | |||
809 | isl_int_neg(shift->ineq[k][0], shift->ineq[k][0])isl_sioimath_neg((shift->ineq[k][0]), *(shift->ineq[k][ 0])); | |||
810 | for (j = 0; j < total; ++j) { | |||
811 | if (isl_int_is_nonneg(shift->ineq[k][1 + j])(isl_sioimath_sgn(*(shift->ineq[k][1 + j])) >= 0)) | |||
812 | continue; | |||
813 | isl_int_add(shift->ineq[k][0],isl_sioimath_add((shift->ineq[k][0]), *(shift->ineq[k][ 0]), *(shift->ineq[k][1 + j])) | |||
814 | shift->ineq[k][0], shift->ineq[k][1 + j])isl_sioimath_add((shift->ineq[k][0]), *(shift->ineq[k][ 0]), *(shift->ineq[k][1 + j])); | |||
815 | } | |||
816 | } | |||
817 | ||||
818 | isl_basic_set_free(cone); | |||
819 | isl_vec_free(vec); | |||
820 | ||||
821 | return isl_basic_set_finalize(shift); | |||
822 | error: | |||
823 | isl_basic_set_free(shift); | |||
824 | isl_basic_set_free(cone); | |||
825 | isl_vec_free(vec); | |||
826 | return NULL((void*)0); | |||
827 | } | |||
828 | ||||
829 | /* Given a rational point vec in a (transformed) basic set, | |||
830 | * such that cone is the recession cone of the original basic set, | |||
831 | * "round up" the rational point to an integer point. | |||
832 | * | |||
833 | * We first check if the rational point just happens to be integer. | |||
834 | * If not, we transform the cone in the same way as the basic set, | |||
835 | * pick a point x in this cone shifted to the rational point such that | |||
836 | * the whole unit cube at x is also inside this affine cone. | |||
837 | * Then we simply round up the coordinates of x and return the | |||
838 | * resulting integer point. | |||
839 | */ | |||
840 | static __isl_give isl_vec *round_up_in_cone(__isl_take isl_vec *vec, | |||
841 | __isl_take isl_basic_setisl_basic_map *cone, __isl_take isl_mat *U) | |||
842 | { | |||
843 | isl_size total; | |||
844 | ||||
845 | if (!vec || !cone || !U) | |||
846 | goto error; | |||
847 | ||||
848 | isl_assert(vec->ctx, vec->size != 0, goto error)do { if (vec->size != 0) break; do { isl_handle_error(vec-> ctx, isl_error_unknown, "Assertion \"" "vec->size != 0" "\" failed" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 848); goto error; } while (0); } while (0); | |||
849 | if (isl_int_is_one(vec->el[0])(isl_sioimath_cmp_si(*(vec->el[0]), 1) == 0)) { | |||
850 | isl_mat_free(U); | |||
851 | isl_basic_set_free(cone); | |||
852 | return vec; | |||
853 | } | |||
854 | ||||
855 | total = isl_basic_set_dim(cone, isl_dim_all); | |||
856 | if (total < 0) | |||
857 | goto error; | |||
858 | cone = isl_basic_set_preimage(cone, U); | |||
859 | cone = isl_basic_set_remove_dims(cone, isl_dim_set, | |||
860 | 0, total - (vec->size - 1)); | |||
861 | ||||
862 | cone = shift_cone(cone, vec); | |||
863 | ||||
864 | vec = rational_sample(cone); | |||
865 | vec = isl_vec_ceil(vec); | |||
866 | return vec; | |||
867 | error: | |||
868 | isl_mat_free(U); | |||
869 | isl_vec_free(vec); | |||
870 | isl_basic_set_free(cone); | |||
871 | return NULL((void*)0); | |||
872 | } | |||
873 | ||||
874 | /* Concatenate two integer vectors, i.e., two vectors with denominator | |||
875 | * (stored in element 0) equal to 1. | |||
876 | */ | |||
877 | static __isl_give isl_vec *vec_concat(__isl_take isl_vec *vec1, | |||
878 | __isl_take isl_vec *vec2) | |||
879 | { | |||
880 | struct isl_vec *vec; | |||
881 | ||||
882 | if (!vec1 || !vec2) | |||
883 | goto error; | |||
884 | isl_assert(vec1->ctx, vec1->size > 0, goto error)do { if (vec1->size > 0) break; do { isl_handle_error(vec1 ->ctx, isl_error_unknown, "Assertion \"" "vec1->size > 0" "\" failed", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 884); goto error; } while (0); } while (0); | |||
885 | isl_assert(vec2->ctx, vec2->size > 0, goto error)do { if (vec2->size > 0) break; do { isl_handle_error(vec2 ->ctx, isl_error_unknown, "Assertion \"" "vec2->size > 0" "\" failed", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 885); goto error; } while (0); } while (0); | |||
886 | isl_assert(vec1->ctx, isl_int_is_one(vec1->el[0]), goto error)do { if ((isl_sioimath_cmp_si(*(vec1->el[0]), 1) == 0)) break ; do { isl_handle_error(vec1->ctx, isl_error_unknown, "Assertion \"" "(isl_sioimath_cmp_si(*(vec1->el[0]), 1) == 0)" "\" failed" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 886); goto error; } while (0); } while (0); | |||
887 | isl_assert(vec2->ctx, isl_int_is_one(vec2->el[0]), goto error)do { if ((isl_sioimath_cmp_si(*(vec2->el[0]), 1) == 0)) break ; do { isl_handle_error(vec2->ctx, isl_error_unknown, "Assertion \"" "(isl_sioimath_cmp_si(*(vec2->el[0]), 1) == 0)" "\" failed" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 887); goto error; } while (0); } while (0); | |||
888 | ||||
889 | vec = isl_vec_alloc(vec1->ctx, vec1->size + vec2->size - 1); | |||
890 | if (!vec) | |||
891 | goto error; | |||
892 | ||||
893 | isl_seq_cpy(vec->el, vec1->el, vec1->size); | |||
894 | isl_seq_cpy(vec->el + vec1->size, vec2->el + 1, vec2->size - 1); | |||
895 | ||||
896 | isl_vec_free(vec1); | |||
897 | isl_vec_free(vec2); | |||
898 | ||||
899 | return vec; | |||
900 | error: | |||
901 | isl_vec_free(vec1); | |||
902 | isl_vec_free(vec2); | |||
903 | return NULL((void*)0); | |||
904 | } | |||
905 | ||||
906 | /* Give a basic set "bset" with recession cone "cone", compute and | |||
907 | * return an integer point in bset, if any. | |||
908 | * | |||
909 | * If the recession cone is full-dimensional, then we know that | |||
910 | * bset contains an infinite number of integer points and it is | |||
911 | * fairly easy to pick one of them. | |||
912 | * If the recession cone is not full-dimensional, then we first | |||
913 | * transform bset such that the bounded directions appear as | |||
914 | * the first dimensions of the transformed basic set. | |||
915 | * We do this by using a unimodular transformation that transforms | |||
916 | * the equalities in the recession cone to equalities on the first | |||
917 | * dimensions. | |||
918 | * | |||
919 | * The transformed set is then projected onto its bounded dimensions. | |||
920 | * Note that to compute this projection, we can simply drop all constraints | |||
921 | * involving any of the unbounded dimensions since these constraints | |||
922 | * cannot be combined to produce a constraint on the bounded dimensions. | |||
923 | * To see this, assume that there is such a combination of constraints | |||
924 | * that produces a constraint on the bounded dimensions. This means | |||
925 | * that some combination of the unbounded dimensions has both an upper | |||
926 | * bound and a lower bound in terms of the bounded dimensions, but then | |||
927 | * this combination would be a bounded direction too and would have been | |||
928 | * transformed into a bounded dimensions. | |||
929 | * | |||
930 | * We then compute a sample value in the bounded dimensions. | |||
931 | * If no such value can be found, then the original set did not contain | |||
932 | * any integer points and we are done. | |||
933 | * Otherwise, we plug in the value we found in the bounded dimensions, | |||
934 | * project out these bounded dimensions and end up with a set with | |||
935 | * a full-dimensional recession cone. | |||
936 | * A sample point in this set is computed by "rounding up" any | |||
937 | * rational point in the set. | |||
938 | * | |||
939 | * The sample points in the bounded and unbounded dimensions are | |||
940 | * then combined into a single sample point and transformed back | |||
941 | * to the original space. | |||
942 | */ | |||
943 | __isl_give isl_vec *isl_basic_set_sample_with_cone( | |||
944 | __isl_take isl_basic_setisl_basic_map *bset, __isl_take isl_basic_setisl_basic_map *cone) | |||
945 | { | |||
946 | isl_size total; | |||
947 | unsigned cone_dim; | |||
948 | struct isl_mat *M, *U; | |||
949 | struct isl_vec *sample; | |||
950 | struct isl_vec *cone_sample; | |||
951 | struct isl_ctx *ctx; | |||
952 | struct isl_basic_setisl_basic_map *bounded; | |||
953 | ||||
954 | total = isl_basic_set_dim(cone, isl_dim_all); | |||
955 | if (!bset || total < 0) | |||
956 | goto error; | |||
957 | ||||
958 | ctx = isl_basic_set_get_ctx(bset); | |||
959 | cone_dim = total - cone->n_eq; | |||
960 | ||||
961 | M = isl_mat_sub_alloc6(ctx, cone->eq, 0, cone->n_eq, 1, total); | |||
962 | M = isl_mat_left_hermite(M, 0, &U, NULL((void*)0)); | |||
963 | if (!M) | |||
964 | goto error; | |||
965 | isl_mat_free(M); | |||
966 | ||||
967 | U = isl_mat_lin_to_aff(U); | |||
968 | bset = isl_basic_set_preimage(bset, isl_mat_copy(U)); | |||
969 | ||||
970 | bounded = isl_basic_set_copy(bset); | |||
971 | bounded = isl_basic_set_drop_constraints_involving(bounded, | |||
972 | total - cone_dim, cone_dim); | |||
973 | bounded = isl_basic_set_drop_dims(bounded, total - cone_dim, cone_dim); | |||
974 | sample = sample_bounded(bounded); | |||
975 | if (!sample || sample->size == 0) { | |||
976 | isl_basic_set_free(bset); | |||
977 | isl_basic_set_free(cone); | |||
978 | isl_mat_free(U); | |||
979 | return sample; | |||
980 | } | |||
981 | bset = plug_in(bset, isl_vec_copy(sample)); | |||
982 | cone_sample = rational_sample(bset); | |||
983 | cone_sample = round_up_in_cone(cone_sample, cone, isl_mat_copy(U)); | |||
984 | sample = vec_concat(sample, cone_sample); | |||
985 | sample = isl_mat_vec_product(U, sample); | |||
986 | return sample; | |||
987 | error: | |||
988 | isl_basic_set_free(cone); | |||
989 | isl_basic_set_free(bset); | |||
990 | return NULL((void*)0); | |||
991 | } | |||
992 | ||||
993 | static void vec_sum_of_neg(__isl_keep isl_vec *v, isl_int *s) | |||
994 | { | |||
995 | int i; | |||
996 | ||||
997 | isl_int_set_si(*s, 0)isl_sioimath_set_si((*s), 0); | |||
998 | ||||
999 | for (i = 0; i < v->size; ++i) | |||
1000 | if (isl_int_is_neg(v->el[i])(isl_sioimath_sgn(*(v->el[i])) < 0)) | |||
1001 | isl_int_add(*s, *s, v->el[i])isl_sioimath_add((*s), *(*s), *(v->el[i])); | |||
1002 | } | |||
1003 | ||||
1004 | /* Given a tableau "tab", a tableau "tab_cone" that corresponds | |||
1005 | * to the recession cone and the inverse of a new basis U = inv(B), | |||
1006 | * with the unbounded directions in B last, | |||
1007 | * add constraints to "tab" that ensure any rational value | |||
1008 | * in the unbounded directions can be rounded up to an integer value. | |||
1009 | * | |||
1010 | * The new basis is given by x' = B x, i.e., x = U x'. | |||
1011 | * For any rational value of the last tab->n_unbounded coordinates | |||
1012 | * in the update tableau, the value that is obtained by rounding | |||
1013 | * up this value should be contained in the original tableau. | |||
1014 | * For any constraint "a x + c >= 0", we therefore need to add | |||
1015 | * a constraint "a x + c + s >= 0", with s the sum of all negative | |||
1016 | * entries in the last elements of "a U". | |||
1017 | * | |||
1018 | * Since we are not interested in the first entries of any of the "a U", | |||
1019 | * we first drop the columns of U that correpond to bounded directions. | |||
1020 | */ | |||
1021 | static int tab_shift_cone(struct isl_tab *tab, | |||
1022 | struct isl_tab *tab_cone, struct isl_mat *U) | |||
1023 | { | |||
1024 | int i; | |||
1025 | isl_int v; | |||
1026 | struct isl_basic_setisl_basic_map *bset = NULL((void*)0); | |||
1027 | ||||
1028 | if (tab && tab->n_unbounded == 0) { | |||
1029 | isl_mat_free(U); | |||
1030 | return 0; | |||
1031 | } | |||
1032 | isl_int_init(v)isl_sioimath_init((v)); | |||
1033 | if (!tab || !tab_cone || !U) | |||
1034 | goto error; | |||
1035 | bset = isl_tab_peek_bset(tab_cone); | |||
1036 | U = isl_mat_drop_cols(U, 0, tab->n_var - tab->n_unbounded); | |||
1037 | for (i = 0; i < bset->n_ineq; ++i) { | |||
1038 | int ok; | |||
1039 | struct isl_vec *row = NULL((void*)0); | |||
1040 | if (isl_tab_is_equality(tab_cone, tab_cone->n_eq + i)) | |||
1041 | continue; | |||
1042 | row = isl_vec_alloc(bset->ctx, tab_cone->n_var); | |||
1043 | if (!row) | |||
1044 | goto error; | |||
1045 | isl_seq_cpy(row->el, bset->ineq[i] + 1, tab_cone->n_var); | |||
1046 | row = isl_vec_mat_product(row, isl_mat_copy(U)); | |||
1047 | if (!row) | |||
1048 | goto error; | |||
1049 | vec_sum_of_neg(row, &v); | |||
1050 | isl_vec_free(row); | |||
1051 | if (isl_int_is_zero(v)(isl_sioimath_sgn(*(v)) == 0)) | |||
1052 | continue; | |||
1053 | if (isl_tab_extend_cons(tab, 1) < 0) | |||
1054 | goto error; | |||
1055 | isl_int_add(bset->ineq[i][0], bset->ineq[i][0], v)isl_sioimath_add((bset->ineq[i][0]), *(bset->ineq[i][0] ), *(v)); | |||
1056 | ok = isl_tab_add_ineq(tab, bset->ineq[i]) >= 0; | |||
1057 | isl_int_sub(bset->ineq[i][0], bset->ineq[i][0], v)isl_sioimath_sub((bset->ineq[i][0]), *(bset->ineq[i][0] ), *(v)); | |||
1058 | if (!ok) | |||
1059 | goto error; | |||
1060 | } | |||
1061 | ||||
1062 | isl_mat_free(U); | |||
1063 | isl_int_clear(v)isl_sioimath_clear((v)); | |||
1064 | return 0; | |||
1065 | error: | |||
1066 | isl_mat_free(U); | |||
1067 | isl_int_clear(v)isl_sioimath_clear((v)); | |||
1068 | return -1; | |||
1069 | } | |||
1070 | ||||
1071 | /* Compute and return an initial basis for the possibly | |||
1072 | * unbounded tableau "tab". "tab_cone" is a tableau | |||
1073 | * for the corresponding recession cone. | |||
1074 | * Additionally, add constraints to "tab" that ensure | |||
1075 | * that any rational value for the unbounded directions | |||
1076 | * can be rounded up to an integer value. | |||
1077 | * | |||
1078 | * If the tableau is bounded, i.e., if the recession cone | |||
1079 | * is zero-dimensional, then we just use inital_basis. | |||
1080 | * Otherwise, we construct a basis whose first directions | |||
1081 | * correspond to equalities, followed by bounded directions, | |||
1082 | * i.e., equalities in the recession cone. | |||
1083 | * The remaining directions are then unbounded. | |||
1084 | */ | |||
1085 | int isl_tab_set_initial_basis_with_cone(struct isl_tab *tab, | |||
1086 | struct isl_tab *tab_cone) | |||
1087 | { | |||
1088 | struct isl_mat *eq; | |||
1089 | struct isl_mat *cone_eq; | |||
1090 | struct isl_mat *U, *Q; | |||
1091 | ||||
1092 | if (!tab || !tab_cone) | |||
1093 | return -1; | |||
1094 | ||||
1095 | if (tab_cone->n_col == tab_cone->n_dead) { | |||
1096 | tab->basis = initial_basis(tab); | |||
1097 | return tab->basis ? 0 : -1; | |||
1098 | } | |||
1099 | ||||
1100 | eq = tab_equalities(tab); | |||
1101 | if (!eq) | |||
1102 | return -1; | |||
1103 | tab->n_zero = eq->n_row; | |||
1104 | cone_eq = tab_equalities(tab_cone); | |||
1105 | eq = isl_mat_concat(eq, cone_eq); | |||
1106 | if (!eq) | |||
1107 | return -1; | |||
1108 | tab->n_unbounded = tab->n_var - (eq->n_row - tab->n_zero); | |||
1109 | eq = isl_mat_left_hermite(eq, 0, &U, &Q); | |||
1110 | if (!eq) | |||
1111 | return -1; | |||
1112 | isl_mat_free(eq); | |||
1113 | tab->basis = isl_mat_lin_to_aff(Q); | |||
1114 | if (tab_shift_cone(tab, tab_cone, U) < 0) | |||
1115 | return -1; | |||
1116 | if (!tab->basis) | |||
1117 | return -1; | |||
1118 | return 0; | |||
1119 | } | |||
1120 | ||||
1121 | /* Compute and return a sample point in bset using generalized basis | |||
1122 | * reduction. We first check if the input set has a non-trivial | |||
1123 | * recession cone. If so, we perform some extra preprocessing in | |||
1124 | * sample_with_cone. Otherwise, we directly perform generalized basis | |||
1125 | * reduction. | |||
1126 | */ | |||
1127 | static __isl_give isl_vec *gbr_sample(__isl_take isl_basic_setisl_basic_map *bset) | |||
1128 | { | |||
1129 | isl_size dim; | |||
1130 | struct isl_basic_setisl_basic_map *cone; | |||
1131 | ||||
1132 | dim = isl_basic_set_dim(bset, isl_dim_all); | |||
1133 | if (dim < 0) | |||
1134 | goto error; | |||
1135 | ||||
1136 | cone = isl_basic_set_recession_cone(isl_basic_set_copy(bset)); | |||
1137 | if (!cone) | |||
1138 | goto error; | |||
1139 | ||||
1140 | if (cone->n_eq < dim) | |||
1141 | return isl_basic_set_sample_with_cone(bset, cone); | |||
1142 | ||||
1143 | isl_basic_set_free(cone); | |||
1144 | return sample_bounded(bset); | |||
1145 | error: | |||
1146 | isl_basic_set_free(bset); | |||
1147 | return NULL((void*)0); | |||
1148 | } | |||
1149 | ||||
1150 | static __isl_give isl_vec *basic_set_sample(__isl_take isl_basic_setisl_basic_map *bset, | |||
1151 | int bounded) | |||
1152 | { | |||
1153 | struct isl_ctx *ctx; | |||
1154 | isl_size dim; | |||
1155 | if (!bset) | |||
1156 | return NULL((void*)0); | |||
1157 | ||||
1158 | ctx = bset->ctx; | |||
1159 | if (isl_basic_set_plain_is_empty(bset)) | |||
1160 | return empty_sample(bset); | |||
1161 | ||||
1162 | dim = isl_basic_set_dim(bset, isl_dim_set); | |||
1163 | if (dim < 0 || | |||
1164 | isl_basic_set_check_no_params(bset) < 0 || | |||
1165 | isl_basic_set_check_no_locals(bset) < 0) | |||
1166 | goto error; | |||
1167 | ||||
1168 | if (bset->sample && bset->sample->size == 1 + dim) { | |||
1169 | int contains = isl_basic_set_contains(bset, bset->sample); | |||
1170 | if (contains < 0) | |||
1171 | goto error; | |||
1172 | if (contains) { | |||
1173 | struct isl_vec *sample = isl_vec_copy(bset->sample); | |||
1174 | isl_basic_set_free(bset); | |||
1175 | return sample; | |||
1176 | } | |||
1177 | } | |||
1178 | isl_vec_free(bset->sample); | |||
1179 | bset->sample = NULL((void*)0); | |||
1180 | ||||
1181 | if (bset->n_eq > 0) | |||
1182 | return sample_eq(bset, bounded ? isl_basic_set_sample_bounded | |||
1183 | : isl_basic_set_sample_vec); | |||
1184 | if (dim == 0) | |||
1185 | return zero_sample(bset); | |||
1186 | if (dim == 1) | |||
1187 | return interval_sample(bset); | |||
1188 | ||||
1189 | return bounded ? sample_bounded(bset) : gbr_sample(bset); | |||
1190 | error: | |||
1191 | isl_basic_set_free(bset); | |||
1192 | return NULL((void*)0); | |||
1193 | } | |||
1194 | ||||
1195 | __isl_give isl_vec *isl_basic_set_sample_vec(__isl_take isl_basic_setisl_basic_map *bset) | |||
1196 | { | |||
1197 | return basic_set_sample(bset, 0); | |||
1198 | } | |||
1199 | ||||
1200 | /* Compute an integer sample in "bset", where the caller guarantees | |||
1201 | * that "bset" is bounded. | |||
1202 | */ | |||
1203 | __isl_give isl_vec *isl_basic_set_sample_bounded(__isl_take isl_basic_setisl_basic_map *bset) | |||
1204 | { | |||
1205 | return basic_set_sample(bset, 1); | |||
1206 | } | |||
1207 | ||||
1208 | __isl_give isl_basic_setisl_basic_map *isl_basic_set_from_vec(__isl_take isl_vec *vec) | |||
1209 | { | |||
1210 | int i; | |||
1211 | int k; | |||
1212 | struct isl_basic_setisl_basic_map *bset = NULL((void*)0); | |||
1213 | struct isl_ctx *ctx; | |||
1214 | isl_size dim; | |||
1215 | ||||
1216 | if (!vec) | |||
1217 | return NULL((void*)0); | |||
1218 | ctx = vec->ctx; | |||
1219 | isl_assert(ctx, vec->size != 0, goto error)do { if (vec->size != 0) break; do { isl_handle_error(ctx, isl_error_unknown, "Assertion \"" "vec->size != 0" "\" failed" , "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_sample.c" , 1219); goto error; } while (0); } while (0); | |||
1220 | ||||
1221 | bset = isl_basic_set_alloc(ctx, 0, vec->size - 1, 0, vec->size - 1, 0); | |||
1222 | dim = isl_basic_set_dim(bset, isl_dim_set); | |||
1223 | if (dim < 0) | |||
1224 | goto error; | |||
1225 | for (i = dim - 1; i >= 0; --i) { | |||
1226 | k = isl_basic_set_alloc_equality(bset); | |||
1227 | if (k < 0) | |||
1228 | goto error; | |||
1229 | isl_seq_clr(bset->eq[k], 1 + dim); | |||
1230 | isl_int_neg(bset->eq[k][0], vec->el[1 + i])isl_sioimath_neg((bset->eq[k][0]), *(vec->el[1 + i])); | |||
1231 | isl_int_set(bset->eq[k][1 + i], vec->el[0])isl_sioimath_set((bset->eq[k][1 + i]), *(vec->el[0])); | |||
1232 | } | |||
1233 | bset->sample = vec; | |||
1234 | ||||
1235 | return bset; | |||
1236 | error: | |||
1237 | isl_basic_set_free(bset); | |||
1238 | isl_vec_free(vec); | |||
1239 | return NULL((void*)0); | |||
1240 | } | |||
1241 | ||||
1242 | __isl_give isl_basic_map *isl_basic_map_sample(__isl_take isl_basic_map *bmap) | |||
1243 | { | |||
1244 | struct isl_basic_setisl_basic_map *bset; | |||
1245 | struct isl_vec *sample_vec; | |||
1246 | ||||
1247 | bset = isl_basic_map_underlying_set(isl_basic_map_copy(bmap)); | |||
1248 | sample_vec = isl_basic_set_sample_vec(bset); | |||
1249 | if (!sample_vec) | |||
1250 | goto error; | |||
1251 | if (sample_vec->size == 0) { | |||
1252 | isl_vec_free(sample_vec); | |||
1253 | return isl_basic_map_set_to_empty(bmap); | |||
1254 | } | |||
1255 | isl_vec_free(bmap->sample); | |||
1256 | bmap->sample = isl_vec_copy(sample_vec); | |||
1257 | bset = isl_basic_set_from_vec(sample_vec); | |||
1258 | return isl_basic_map_overlying_set(bset, bmap); | |||
1259 | error: | |||
1260 | isl_basic_map_free(bmap); | |||
1261 | return NULL((void*)0); | |||
1262 | } | |||
1263 | ||||
1264 | __isl_give isl_basic_setisl_basic_map *isl_basic_set_sample(__isl_take isl_basic_setisl_basic_map *bset) | |||
1265 | { | |||
1266 | return isl_basic_map_sample(bset); | |||
1267 | } | |||
1268 | ||||
1269 | __isl_give isl_basic_map *isl_map_sample(__isl_take isl_map *map) | |||
1270 | { | |||
1271 | int i; | |||
1272 | isl_basic_map *sample = NULL((void*)0); | |||
1273 | ||||
1274 | if (!map) | |||
1275 | goto error; | |||
1276 | ||||
1277 | for (i = 0; i < map->n; ++i) { | |||
1278 | sample = isl_basic_map_sample(isl_basic_map_copy(map->p[i])); | |||
1279 | if (!sample) | |||
1280 | goto error; | |||
1281 | if (!ISL_F_ISSET(sample, ISL_BASIC_MAP_EMPTY)(!!(((sample)->flags) & ((1 << 1))))) | |||
1282 | break; | |||
1283 | isl_basic_map_free(sample); | |||
1284 | } | |||
1285 | if (i == map->n) | |||
1286 | sample = isl_basic_map_empty(isl_map_get_space(map)); | |||
1287 | isl_map_free(map); | |||
1288 | return sample; | |||
1289 | error: | |||
1290 | isl_map_free(map); | |||
1291 | return NULL((void*)0); | |||
1292 | } | |||
1293 | ||||
1294 | __isl_give isl_basic_setisl_basic_map *isl_set_sample(__isl_take isl_setisl_map *set) | |||
1295 | { | |||
1296 | return bset_from_bmap(isl_map_sample(set_to_map(set))); | |||
1297 | } | |||
1298 | ||||
1299 | __isl_give isl_point *isl_basic_set_sample_point(__isl_take isl_basic_setisl_basic_map *bset) | |||
1300 | { | |||
1301 | isl_vec *vec; | |||
1302 | isl_space *space; | |||
1303 | ||||
1304 | space = isl_basic_set_get_space(bset); | |||
1305 | bset = isl_basic_set_underlying_set(bset); | |||
1306 | vec = isl_basic_set_sample_vec(bset); | |||
1307 | ||||
1308 | return isl_point_alloc(space, vec); | |||
1309 | } | |||
1310 | ||||
1311 | __isl_give isl_point *isl_set_sample_point(__isl_take isl_setisl_map *set) | |||
1312 | { | |||
1313 | int i; | |||
1314 | isl_point *pnt; | |||
| ||||
1315 | ||||
1316 | if (!set) | |||
1317 | return NULL((void*)0); | |||
1318 | ||||
1319 | for (i = 0; i < set->n; ++i) { | |||
1320 | pnt = isl_basic_set_sample_point(isl_basic_set_copy(set->p[i])); | |||
1321 | if (!pnt) | |||
1322 | goto error; | |||
1323 | if (!isl_point_is_void(pnt)) | |||
1324 | break; | |||
1325 | isl_point_free(pnt); | |||
1326 | } | |||
1327 | if (i == set->n) | |||
1328 | pnt = isl_point_void(isl_set_get_space(set)); | |||
1329 | ||||
1330 | isl_set_free(set); | |||
1331 | return pnt; | |||
| ||||
1332 | error: | |||
1333 | isl_set_free(set); | |||
1334 | return NULL((void*)0); | |||
1335 | } |