File: | polly/lib/External/isl/isl_scan.c |
Warning: | line 117, column 3 Value stored to 'bset' is never read |
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_basis_reduction.h" |
13 | #include "isl_scan.h" |
14 | #include <isl_seq.h> |
15 | #include "isl_tab.h" |
16 | #include <isl_val_private.h> |
17 | #include <isl_vec_private.h> |
18 | |
19 | struct isl_counter { |
20 | struct isl_scan_callback callback; |
21 | isl_int count; |
22 | isl_int max; |
23 | }; |
24 | |
25 | static isl_stat increment_counter(struct isl_scan_callback *cb, |
26 | __isl_take isl_vec *sample) |
27 | { |
28 | struct isl_counter *cnt = (struct isl_counter *)cb; |
29 | |
30 | isl_int_add_ui(cnt->count, cnt->count, 1)isl_sioimath_add_ui((cnt->count), *(cnt->count), 1); |
31 | |
32 | isl_vec_free(sample); |
33 | |
34 | if (isl_int_is_zero(cnt->max)(isl_sioimath_sgn(*(cnt->max)) == 0) || isl_int_lt(cnt->count, cnt->max)(isl_sioimath_cmp(*(cnt->count), *(cnt->max)) < 0)) |
35 | return isl_stat_ok; |
36 | return isl_stat_error; |
37 | } |
38 | |
39 | static int increment_range(struct isl_scan_callback *cb, isl_int min, isl_int max) |
40 | { |
41 | struct isl_counter *cnt = (struct isl_counter *)cb; |
42 | |
43 | isl_int_add(cnt->count, cnt->count, max)isl_sioimath_add((cnt->count), *(cnt->count), *(max)); |
44 | isl_int_sub(cnt->count, cnt->count, min)isl_sioimath_sub((cnt->count), *(cnt->count), *(min)); |
45 | isl_int_add_ui(cnt->count, cnt->count, 1)isl_sioimath_add_ui((cnt->count), *(cnt->count), 1); |
46 | |
47 | if (isl_int_is_zero(cnt->max)(isl_sioimath_sgn(*(cnt->max)) == 0) || isl_int_lt(cnt->count, cnt->max)(isl_sioimath_cmp(*(cnt->count), *(cnt->max)) < 0)) |
48 | return 0; |
49 | isl_int_set(cnt->count, cnt->max)isl_sioimath_set((cnt->count), *(cnt->max)); |
50 | return -1; |
51 | } |
52 | |
53 | /* Call callback->add with the current sample value of the tableau "tab". |
54 | */ |
55 | static int add_solution(struct isl_tab *tab, struct isl_scan_callback *callback) |
56 | { |
57 | struct isl_vec *sample; |
58 | |
59 | if (!tab) |
60 | return -1; |
61 | sample = isl_tab_get_sample_value(tab); |
62 | if (!sample) |
63 | return -1; |
64 | |
65 | return callback->add(callback, sample); |
66 | } |
67 | |
68 | static isl_stat scan_0D(__isl_take isl_basic_setisl_basic_map *bset, |
69 | struct isl_scan_callback *callback) |
70 | { |
71 | struct isl_vec *sample; |
72 | |
73 | sample = isl_vec_alloc(bset->ctx, 1); |
74 | isl_basic_set_free(bset); |
75 | |
76 | if (!sample) |
77 | return isl_stat_error; |
78 | |
79 | isl_int_set_si(sample->el[0], 1)isl_sioimath_set_si((sample->el[0]), 1); |
80 | |
81 | return callback->add(callback, sample); |
82 | } |
83 | |
84 | /* Look for all integer points in "bset", which is assumed to be bounded, |
85 | * and call callback->add on each of them. |
86 | * |
87 | * We first compute a reduced basis for the set and then scan |
88 | * the set in the directions of this basis. |
89 | * We basically perform a depth first search, where in each level i |
90 | * we compute the range in the i-th basis vector direction, given |
91 | * fixed values in the directions of the previous basis vector. |
92 | * We then add an equality to the tableau fixing the value in the |
93 | * direction of the current basis vector to each value in the range |
94 | * in turn and then continue to the next level. |
95 | * |
96 | * The search is implemented iteratively. "level" identifies the current |
97 | * basis vector. "init" is true if we want the first value at the current |
98 | * level and false if we want the next value. |
99 | * Solutions are added in the leaves of the search tree, i.e., after |
100 | * we have fixed a value in each direction of the basis. |
101 | */ |
102 | isl_stat isl_basic_set_scan(__isl_take isl_basic_setisl_basic_map *bset, |
103 | struct isl_scan_callback *callback) |
104 | { |
105 | isl_size dim; |
106 | struct isl_mat *B = NULL((void*)0); |
107 | struct isl_tab *tab = NULL((void*)0); |
108 | struct isl_vec *min; |
109 | struct isl_vec *max; |
110 | struct isl_tab_undo **snap; |
111 | int level; |
112 | int init; |
113 | enum isl_lp_result res; |
114 | |
115 | dim = isl_basic_set_dim(bset, isl_dim_all); |
116 | if (dim < 0) { |
117 | bset = isl_basic_set_free(bset); |
Value stored to 'bset' is never read | |
118 | return isl_stat_error; |
119 | } |
120 | |
121 | if (dim == 0) |
122 | return scan_0D(bset, callback); |
123 | |
124 | min = isl_vec_alloc(bset->ctx, dim); |
125 | max = isl_vec_alloc(bset->ctx, dim); |
126 | snap = isl_alloc_array(bset->ctx, struct isl_tab_undo *, dim)((struct isl_tab_undo * *)isl_malloc_or_die(bset->ctx, (dim )*sizeof(struct isl_tab_undo *))); |
127 | |
128 | if (!min || !max || !snap) |
129 | goto error; |
130 | |
131 | tab = isl_tab_from_basic_set(bset, 0); |
132 | if (!tab) |
133 | goto error; |
134 | if (isl_tab_extend_cons(tab, dim + 1) < 0) |
135 | goto error; |
136 | |
137 | tab->basis = isl_mat_identity(bset->ctx, 1 + dim); |
138 | if (1) |
139 | tab = isl_tab_compute_reduced_basis(tab); |
140 | if (!tab) |
141 | goto error; |
142 | B = isl_mat_copy(tab->basis); |
143 | if (!B) |
144 | goto error; |
145 | |
146 | level = 0; |
147 | init = 1; |
148 | |
149 | while (level >= 0) { |
150 | int empty = 0; |
151 | if (init) { |
152 | res = isl_tab_min(tab, B->row[1 + level], |
153 | bset->ctx->one, &min->el[level], NULL((void*)0), 0); |
154 | if (res == isl_lp_empty) |
155 | empty = 1; |
156 | if (res == isl_lp_error || res == isl_lp_unbounded) |
157 | goto error; |
158 | isl_seq_neg(B->row[1 + level] + 1, |
159 | B->row[1 + level] + 1, dim); |
160 | res = isl_tab_min(tab, B->row[1 + level], |
161 | bset->ctx->one, &max->el[level], NULL((void*)0), 0); |
162 | isl_seq_neg(B->row[1 + level] + 1, |
163 | B->row[1 + level] + 1, dim); |
164 | isl_int_neg(max->el[level], max->el[level])isl_sioimath_neg((max->el[level]), *(max->el[level])); |
165 | if (res == isl_lp_empty) |
166 | empty = 1; |
167 | if (res == isl_lp_error || res == isl_lp_unbounded) |
168 | goto error; |
169 | snap[level] = isl_tab_snap(tab); |
170 | } else |
171 | isl_int_add_ui(min->el[level], min->el[level], 1)isl_sioimath_add_ui((min->el[level]), *(min->el[level]) , 1); |
172 | |
173 | if (empty || isl_int_gt(min->el[level], max->el[level])(isl_sioimath_cmp(*(min->el[level]), *(max->el[level])) > 0)) { |
174 | level--; |
175 | init = 0; |
176 | if (level >= 0) |
177 | if (isl_tab_rollback(tab, snap[level]) < 0) |
178 | goto error; |
179 | continue; |
180 | } |
181 | if (level == dim - 1 && callback->add == increment_counter) { |
182 | if (increment_range(callback, |
183 | min->el[level], max->el[level])) |
184 | goto error; |
185 | level--; |
186 | init = 0; |
187 | if (level >= 0) |
188 | if (isl_tab_rollback(tab, snap[level]) < 0) |
189 | goto error; |
190 | continue; |
191 | } |
192 | isl_int_neg(B->row[1 + level][0], min->el[level])isl_sioimath_neg((B->row[1 + level][0]), *(min->el[level ])); |
193 | if (isl_tab_add_valid_eq(tab, B->row[1 + level]) < 0) |
194 | goto error; |
195 | isl_int_set_si(B->row[1 + level][0], 0)isl_sioimath_set_si((B->row[1 + level][0]), 0); |
196 | if (level < dim - 1) { |
197 | ++level; |
198 | init = 1; |
199 | continue; |
200 | } |
201 | if (add_solution(tab, callback) < 0) |
202 | goto error; |
203 | init = 0; |
204 | if (isl_tab_rollback(tab, snap[level]) < 0) |
205 | goto error; |
206 | } |
207 | |
208 | isl_tab_free(tab); |
209 | free(snap); |
210 | isl_vec_free(min); |
211 | isl_vec_free(max); |
212 | isl_basic_set_free(bset); |
213 | isl_mat_free(B); |
214 | return isl_stat_ok; |
215 | error: |
216 | isl_tab_free(tab); |
217 | free(snap); |
218 | isl_vec_free(min); |
219 | isl_vec_free(max); |
220 | isl_basic_set_free(bset); |
221 | isl_mat_free(B); |
222 | return isl_stat_error; |
223 | } |
224 | |
225 | isl_stat isl_set_scan(__isl_take isl_setisl_map *set, |
226 | struct isl_scan_callback *callback) |
227 | { |
228 | int i; |
229 | |
230 | if (!set || !callback) |
231 | goto error; |
232 | |
233 | set = isl_set_cow(set); |
234 | set = isl_set_make_disjoint(set); |
235 | set = isl_set_compute_divs(set); |
236 | if (!set) |
237 | goto error; |
238 | |
239 | for (i = 0; i < set->n; ++i) |
240 | if (isl_basic_set_scan(isl_basic_set_copy(set->p[i]), |
241 | callback) < 0) |
242 | goto error; |
243 | |
244 | isl_set_free(set); |
245 | return isl_stat_ok; |
246 | error: |
247 | isl_set_free(set); |
248 | return isl_stat_error; |
249 | } |
250 | |
251 | int isl_basic_set_count_upto(__isl_keep isl_basic_setisl_basic_map *bset, |
252 | isl_int max, isl_int *count) |
253 | { |
254 | struct isl_counter cnt = { { &increment_counter } }; |
255 | |
256 | if (!bset) |
257 | return -1; |
258 | |
259 | isl_int_init(cnt.count)isl_sioimath_init((cnt.count)); |
260 | isl_int_init(cnt.max)isl_sioimath_init((cnt.max)); |
261 | |
262 | isl_int_set_si(cnt.count, 0)isl_sioimath_set_si((cnt.count), 0); |
263 | isl_int_set(cnt.max, max)isl_sioimath_set((cnt.max), *(max)); |
264 | if (isl_basic_set_scan(isl_basic_set_copy(bset), &cnt.callback) < 0 && |
265 | isl_int_lt(cnt.count, cnt.max)(isl_sioimath_cmp(*(cnt.count), *(cnt.max)) < 0)) |
266 | goto error; |
267 | |
268 | isl_int_set(*count, cnt.count)isl_sioimath_set((*count), *(cnt.count)); |
269 | isl_int_clear(cnt.max)isl_sioimath_clear((cnt.max)); |
270 | isl_int_clear(cnt.count)isl_sioimath_clear((cnt.count)); |
271 | |
272 | return 0; |
273 | error: |
274 | isl_int_clear(cnt.count)isl_sioimath_clear((cnt.count)); |
275 | return -1; |
276 | } |
277 | |
278 | int isl_set_count_upto(__isl_keep isl_setisl_map *set, isl_int max, isl_int *count) |
279 | { |
280 | struct isl_counter cnt = { { &increment_counter } }; |
281 | |
282 | if (!set) |
283 | return -1; |
284 | |
285 | isl_int_init(cnt.count)isl_sioimath_init((cnt.count)); |
286 | isl_int_init(cnt.max)isl_sioimath_init((cnt.max)); |
287 | |
288 | isl_int_set_si(cnt.count, 0)isl_sioimath_set_si((cnt.count), 0); |
289 | isl_int_set(cnt.max, max)isl_sioimath_set((cnt.max), *(max)); |
290 | if (isl_set_scan(isl_set_copy(set), &cnt.callback) < 0 && |
291 | isl_int_lt(cnt.count, cnt.max)(isl_sioimath_cmp(*(cnt.count), *(cnt.max)) < 0)) |
292 | goto error; |
293 | |
294 | isl_int_set(*count, cnt.count)isl_sioimath_set((*count), *(cnt.count)); |
295 | isl_int_clear(cnt.max)isl_sioimath_clear((cnt.max)); |
296 | isl_int_clear(cnt.count)isl_sioimath_clear((cnt.count)); |
297 | |
298 | return 0; |
299 | error: |
300 | isl_int_clear(cnt.count)isl_sioimath_clear((cnt.count)); |
301 | return -1; |
302 | } |
303 | |
304 | int isl_set_count(__isl_keep isl_setisl_map *set, isl_int *count) |
305 | { |
306 | if (!set) |
307 | return -1; |
308 | return isl_set_count_upto(set, set->ctx->zero, count); |
309 | } |
310 | |
311 | /* Count the total number of elements in "set" (in an inefficient way) and |
312 | * return the result. |
313 | */ |
314 | __isl_give isl_val *isl_set_count_val(__isl_keep isl_setisl_map *set) |
315 | { |
316 | isl_val *v; |
317 | |
318 | if (!set) |
319 | return NULL((void*)0); |
320 | v = isl_val_zero(isl_set_get_ctx(set)); |
321 | v = isl_val_cow(v); |
322 | if (!v) |
323 | return NULL((void*)0); |
324 | if (isl_set_count(set, &v->n) < 0) |
325 | v = isl_val_free(v); |
326 | return v; |
327 | } |