File: | tools/polly/lib/External/isl/isl_vertices.c |
Warning: | line 1096, column 2 Use of memory after it is freed |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | /* | |||
2 | * Copyright 2010 INRIA Saclay | |||
3 | * | |||
4 | * Use of this software is governed by the MIT license | |||
5 | * | |||
6 | * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France, | |||
7 | * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod, | |||
8 | * 91893 Orsay, France | |||
9 | */ | |||
10 | ||||
11 | #include <isl_map_private.h> | |||
12 | #include <isl_aff_private.h> | |||
13 | #include <isl/set.h> | |||
14 | #include <isl_seq.h> | |||
15 | #include <isl_tab.h> | |||
16 | #include <isl_space_private.h> | |||
17 | #include <isl_morph.h> | |||
18 | #include <isl_vertices_private.h> | |||
19 | #include <isl_mat_private.h> | |||
20 | #include <isl_vec_private.h> | |||
21 | ||||
22 | #define SELECTED1 1 | |||
23 | #define DESELECTED-1 -1 | |||
24 | #define UNSELECTED0 0 | |||
25 | ||||
26 | static __isl_give isl_vertices *compute_chambers(__isl_take isl_basic_setisl_basic_map *bset, | |||
27 | __isl_take isl_vertices *vertices); | |||
28 | ||||
29 | __isl_give isl_vertices *isl_vertices_copy(__isl_keep isl_vertices *vertices) | |||
30 | { | |||
31 | if (!vertices) | |||
32 | return NULL((void*)0); | |||
33 | ||||
34 | vertices->ref++; | |||
35 | return vertices; | |||
36 | } | |||
37 | ||||
38 | __isl_null isl_vertices *isl_vertices_free(__isl_take isl_vertices *vertices) | |||
39 | { | |||
40 | int i; | |||
41 | ||||
42 | if (!vertices) | |||
43 | return NULL((void*)0); | |||
44 | ||||
45 | if (--vertices->ref > 0) | |||
46 | return NULL((void*)0); | |||
47 | ||||
48 | for (i = 0; i < vertices->n_vertices; ++i) { | |||
49 | isl_basic_set_free(vertices->v[i].vertex); | |||
50 | isl_basic_set_free(vertices->v[i].dom); | |||
51 | } | |||
52 | free(vertices->v); | |||
53 | ||||
54 | for (i = 0; i < vertices->n_chambers; ++i) { | |||
55 | free(vertices->c[i].vertices); | |||
56 | isl_basic_set_free(vertices->c[i].dom); | |||
57 | } | |||
58 | free(vertices->c); | |||
59 | ||||
60 | isl_basic_set_free(vertices->bset); | |||
61 | free(vertices); | |||
62 | ||||
63 | return NULL((void*)0); | |||
64 | } | |||
65 | ||||
66 | struct isl_vertex_list { | |||
67 | struct isl_vertex v; | |||
68 | struct isl_vertex_list *next; | |||
69 | }; | |||
70 | ||||
71 | static struct isl_vertex_list *free_vertex_list(struct isl_vertex_list *list) | |||
72 | { | |||
73 | struct isl_vertex_list *next; | |||
74 | ||||
75 | for (; list; list = next) { | |||
76 | next = list->next; | |||
77 | isl_basic_set_free(list->v.vertex); | |||
78 | isl_basic_set_free(list->v.dom); | |||
79 | free(list); | |||
80 | } | |||
81 | ||||
82 | return NULL((void*)0); | |||
83 | } | |||
84 | ||||
85 | static __isl_give isl_vertices *vertices_from_list(__isl_keep isl_basic_setisl_basic_map *bset, | |||
86 | int n_vertices, struct isl_vertex_list *list) | |||
87 | { | |||
88 | int i; | |||
89 | struct isl_vertex_list *next; | |||
90 | isl_vertices *vertices; | |||
91 | ||||
92 | vertices = isl_calloc_type(bset->ctx, isl_vertices)((isl_vertices *)isl_calloc_or_die(bset->ctx, 1, sizeof(isl_vertices ))); | |||
93 | if (!vertices) | |||
94 | goto error; | |||
95 | vertices->ref = 1; | |||
96 | vertices->bset = isl_basic_set_copy(bset); | |||
97 | vertices->v = isl_alloc_array(bset->ctx, struct isl_vertex, n_vertices)((struct isl_vertex *)isl_malloc_or_die(bset->ctx, (n_vertices )*sizeof(struct isl_vertex))); | |||
98 | if (n_vertices && !vertices->v) | |||
99 | goto error; | |||
100 | vertices->n_vertices = n_vertices; | |||
101 | ||||
102 | for (i = 0; list; list = next, i++) { | |||
103 | next = list->next; | |||
104 | vertices->v[i] = list->v; | |||
105 | free(list); | |||
106 | } | |||
107 | ||||
108 | return vertices; | |||
109 | error: | |||
110 | isl_vertices_free(vertices); | |||
111 | free_vertex_list(list); | |||
112 | return NULL((void*)0); | |||
113 | } | |||
114 | ||||
115 | /* Prepend a vertex to the linked list "list" based on the equalities in "tab". | |||
116 | * Return isl_bool_true if the vertex was actually added and | |||
117 | * isl_bool_false otherwise. | |||
118 | * In particular, vertices with a lower-dimensional activity domain are | |||
119 | * not added to the list because they would not be included in any chamber. | |||
120 | * Return isl_bool_error on error. | |||
121 | */ | |||
122 | static isl_bool add_vertex(struct isl_vertex_list **list, | |||
123 | __isl_keep isl_basic_setisl_basic_map *bset, struct isl_tab *tab) | |||
124 | { | |||
125 | unsigned nvar; | |||
126 | struct isl_vertex_list *v = NULL((void*)0); | |||
127 | ||||
128 | if (isl_tab_detect_implicit_equalities(tab) < 0) | |||
129 | return isl_bool_error; | |||
130 | ||||
131 | nvar = isl_basic_set_dim(bset, isl_dim_set); | |||
132 | ||||
133 | v = isl_calloc_type(tab->mat->ctx, struct isl_vertex_list)((struct isl_vertex_list *)isl_calloc_or_die(tab->mat-> ctx, 1, sizeof(struct isl_vertex_list))); | |||
134 | if (!v) | |||
135 | goto error; | |||
136 | ||||
137 | v->v.vertex = isl_basic_set_copy(bset); | |||
138 | v->v.vertex = isl_basic_set_cow(v->v.vertex); | |||
139 | v->v.vertex = isl_basic_set_update_from_tab(v->v.vertex, tab); | |||
140 | v->v.vertex = isl_basic_set_simplify(v->v.vertex); | |||
141 | v->v.vertex = isl_basic_set_finalize(v->v.vertex); | |||
142 | if (!v->v.vertex) | |||
143 | goto error; | |||
144 | isl_assert(bset->ctx, v->v.vertex->n_eq >= nvar, goto error)do { if (v->v.vertex->n_eq >= nvar) break; do { isl_handle_error (bset->ctx, isl_error_unknown, "Assertion \"" "v->v.vertex->n_eq >= nvar" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_vertices.c" , 144); goto error; } while (0); } while (0); | |||
145 | v->v.dom = isl_basic_set_copy(v->v.vertex); | |||
146 | v->v.dom = isl_basic_set_params(v->v.dom); | |||
147 | if (!v->v.dom) | |||
148 | goto error; | |||
149 | ||||
150 | if (v->v.dom->n_eq > 0) { | |||
151 | free_vertex_list(v); | |||
152 | return isl_bool_false; | |||
153 | } | |||
154 | ||||
155 | v->next = *list; | |||
156 | *list = v; | |||
157 | ||||
158 | return isl_bool_true; | |||
159 | error: | |||
160 | free_vertex_list(v); | |||
161 | return isl_bool_error; | |||
162 | } | |||
163 | ||||
164 | /* Compute the parametric vertices and the chamber decomposition | |||
165 | * of an empty parametric polytope. | |||
166 | */ | |||
167 | static __isl_give isl_vertices *vertices_empty(__isl_keep isl_basic_setisl_basic_map *bset) | |||
168 | { | |||
169 | isl_vertices *vertices; | |||
170 | ||||
171 | if (!bset) | |||
172 | return NULL((void*)0); | |||
173 | ||||
174 | vertices = isl_calloc_type(bset->ctx, isl_vertices)((isl_vertices *)isl_calloc_or_die(bset->ctx, 1, sizeof(isl_vertices ))); | |||
175 | if (!vertices) | |||
176 | return NULL((void*)0); | |||
177 | vertices->bset = isl_basic_set_copy(bset); | |||
178 | vertices->ref = 1; | |||
179 | ||||
180 | vertices->n_vertices = 0; | |||
181 | vertices->n_chambers = 0; | |||
182 | ||||
183 | return vertices; | |||
184 | } | |||
185 | ||||
186 | /* Compute the parametric vertices and the chamber decomposition | |||
187 | * of the parametric polytope defined using the same constraints | |||
188 | * as "bset" in the 0D case. | |||
189 | * There is exactly one 0D vertex and a single chamber containing | |||
190 | * the vertex. | |||
191 | */ | |||
192 | static __isl_give isl_vertices *vertices_0D(__isl_keep isl_basic_setisl_basic_map *bset) | |||
193 | { | |||
194 | isl_vertices *vertices; | |||
195 | ||||
196 | if (!bset) | |||
197 | return NULL((void*)0); | |||
198 | ||||
199 | vertices = isl_calloc_type(bset->ctx, isl_vertices)((isl_vertices *)isl_calloc_or_die(bset->ctx, 1, sizeof(isl_vertices ))); | |||
200 | if (!vertices) | |||
201 | return NULL((void*)0); | |||
202 | vertices->ref = 1; | |||
203 | vertices->bset = isl_basic_set_copy(bset); | |||
204 | ||||
205 | vertices->v = isl_calloc_array(bset->ctx, struct isl_vertex, 1)((struct isl_vertex *)isl_calloc_or_die(bset->ctx, 1, sizeof (struct isl_vertex))); | |||
206 | if (!vertices->v) | |||
207 | goto error; | |||
208 | vertices->n_vertices = 1; | |||
209 | vertices->v[0].vertex = isl_basic_set_copy(bset); | |||
210 | vertices->v[0].dom = isl_basic_set_params(isl_basic_set_copy(bset)); | |||
211 | if (!vertices->v[0].vertex || !vertices->v[0].dom) | |||
212 | goto error; | |||
213 | ||||
214 | vertices->c = isl_calloc_array(bset->ctx, struct isl_chamber, 1)((struct isl_chamber *)isl_calloc_or_die(bset->ctx, 1, sizeof (struct isl_chamber))); | |||
215 | if (!vertices->c) | |||
216 | goto error; | |||
217 | vertices->n_chambers = 1; | |||
218 | vertices->c[0].n_vertices = 1; | |||
219 | vertices->c[0].vertices = isl_calloc_array(bset->ctx, int, 1)((int *)isl_calloc_or_die(bset->ctx, 1, sizeof(int))); | |||
220 | if (!vertices->c[0].vertices) | |||
221 | goto error; | |||
222 | vertices->c[0].dom = isl_basic_set_copy(vertices->v[0].dom); | |||
223 | if (!vertices->c[0].dom) | |||
224 | goto error; | |||
225 | ||||
226 | return vertices; | |||
227 | error: | |||
228 | isl_vertices_free(vertices); | |||
229 | return NULL((void*)0); | |||
230 | } | |||
231 | ||||
232 | /* Is the row pointed to by "f" linearly independent of the "n" first | |||
233 | * rows in "facets"? | |||
234 | */ | |||
235 | static int is_independent(__isl_keep isl_mat *facets, int n, isl_int *f) | |||
236 | { | |||
237 | int rank; | |||
238 | ||||
239 | if (isl_seq_first_non_zero(f, facets->n_col) < 0) | |||
240 | return 0; | |||
241 | ||||
242 | isl_seq_cpy(facets->row[n], f, facets->n_col); | |||
243 | facets->n_row = n + 1; | |||
244 | rank = isl_mat_rank(facets); | |||
245 | if (rank < 0) | |||
246 | return -1; | |||
247 | ||||
248 | return rank == n + 1; | |||
249 | } | |||
250 | ||||
251 | /* Check whether we can select constraint "level", given the current selection | |||
252 | * reflected by facets in "tab", the rows of "facets" and the earlier | |||
253 | * "selected" elements of "selection". | |||
254 | * | |||
255 | * If the constraint is (strictly) redundant in the tableau, selecting it would | |||
256 | * result in an empty tableau, so it can't be selected. | |||
257 | * If the set variable part of the constraint is not linearly independent | |||
258 | * of the set variable parts of the already selected constraints, | |||
259 | * the constraint cannot be selected. | |||
260 | * If selecting the constraint results in an empty tableau, the constraint | |||
261 | * cannot be selected. | |||
262 | * Finally, if selecting the constraint results in some explicitly | |||
263 | * deselected constraints turning into equalities, then the corresponding | |||
264 | * vertices have already been generated, so the constraint cannot be selected. | |||
265 | */ | |||
266 | static int can_select(__isl_keep isl_basic_setisl_basic_map *bset, int level, | |||
267 | struct isl_tab *tab, __isl_keep isl_mat *facets, int selected, | |||
268 | int *selection) | |||
269 | { | |||
270 | int i; | |||
271 | int indep; | |||
272 | unsigned ovar; | |||
273 | struct isl_tab_undo *snap; | |||
274 | ||||
275 | if (isl_tab_is_redundant(tab, level)) | |||
276 | return 0; | |||
277 | ||||
278 | ovar = isl_space_offset(bset->dim, isl_dim_set); | |||
279 | ||||
280 | indep = is_independent(facets, selected, bset->ineq[level] + 1 + ovar); | |||
281 | if (indep < 0) | |||
282 | return -1; | |||
283 | if (!indep) | |||
284 | return 0; | |||
285 | ||||
286 | snap = isl_tab_snap(tab); | |||
287 | if (isl_tab_select_facet(tab, level) < 0) | |||
288 | return -1; | |||
289 | ||||
290 | if (tab->empty) { | |||
291 | if (isl_tab_rollback(tab, snap) < 0) | |||
292 | return -1; | |||
293 | return 0; | |||
294 | } | |||
295 | ||||
296 | for (i = 0; i < level; ++i) { | |||
297 | int sgn; | |||
298 | ||||
299 | if (selection[i] != DESELECTED-1) | |||
300 | continue; | |||
301 | ||||
302 | if (isl_tab_is_equality(tab, i)) | |||
303 | sgn = 0; | |||
304 | else if (isl_tab_is_redundant(tab, i)) | |||
305 | sgn = 1; | |||
306 | else | |||
307 | sgn = isl_tab_sign_of_max(tab, i); | |||
308 | if (sgn < -1) | |||
309 | return -1; | |||
310 | if (sgn <= 0) { | |||
311 | if (isl_tab_rollback(tab, snap) < 0) | |||
312 | return -1; | |||
313 | return 0; | |||
314 | } | |||
315 | } | |||
316 | ||||
317 | return 1; | |||
318 | } | |||
319 | ||||
320 | /* Compute the parametric vertices and the chamber decomposition | |||
321 | * of a parametric polytope that is not full-dimensional. | |||
322 | * | |||
323 | * Simply map the parametric polytope to a lower dimensional space | |||
324 | * and map the resulting vertices back. | |||
325 | */ | |||
326 | static __isl_give isl_vertices *lower_dim_vertices( | |||
327 | __isl_keep isl_basic_setisl_basic_map *bset) | |||
328 | { | |||
329 | isl_morph *morph; | |||
330 | isl_vertices *vertices; | |||
331 | ||||
332 | bset = isl_basic_set_copy(bset); | |||
333 | morph = isl_basic_set_full_compression(bset); | |||
334 | bset = isl_morph_basic_set(isl_morph_copy(morph), bset); | |||
335 | ||||
336 | vertices = isl_basic_set_compute_vertices(bset); | |||
337 | isl_basic_set_free(bset); | |||
338 | ||||
339 | morph = isl_morph_inverse(morph); | |||
340 | ||||
341 | vertices = isl_morph_vertices(morph, vertices); | |||
342 | ||||
343 | return vertices; | |||
344 | } | |||
345 | ||||
346 | /* Compute the parametric vertices and the chamber decomposition | |||
347 | * of the parametric polytope defined using the same constraints | |||
348 | * as "bset". "bset" is assumed to have no existentially quantified | |||
349 | * variables. | |||
350 | * | |||
351 | * The vertices themselves are computed in a fairly simplistic way. | |||
352 | * We simply run through all combinations of d constraints, | |||
353 | * with d the number of set variables, and check if those d constraints | |||
354 | * define a vertex. To avoid the generation of duplicate vertices, | |||
355 | * which we may happen if a vertex is defined by more that d constraints, | |||
356 | * we make sure we only generate the vertex for the d constraints with | |||
357 | * smallest index. | |||
358 | * | |||
359 | * We set up a tableau and keep track of which facets have been | |||
360 | * selected. The tableau is marked strict_redundant so that we can be | |||
361 | * sure that any constraint that is marked redundant (and that is not | |||
362 | * also marked zero) is not an equality. | |||
363 | * If a constraint is marked DESELECTED, it means the constraint was | |||
364 | * SELECTED before (in combination with the same selection of earlier | |||
365 | * constraints). If such a deselected constraint turns out to be an | |||
366 | * equality, then any vertex that may still be found with the current | |||
367 | * selection has already been generated when the constraint was selected. | |||
368 | * A constraint is marked UNSELECTED when there is no way selecting | |||
369 | * the constraint could lead to a vertex (in combination with the current | |||
370 | * selection of earlier constraints). | |||
371 | * | |||
372 | * The set variable coefficients of the selected constraints are stored | |||
373 | * in the facets matrix. | |||
374 | */ | |||
375 | __isl_give isl_vertices *isl_basic_set_compute_vertices( | |||
376 | __isl_keep isl_basic_setisl_basic_map *bset) | |||
377 | { | |||
378 | struct isl_tab *tab; | |||
379 | int level; | |||
380 | int init; | |||
381 | unsigned nvar; | |||
382 | int *selection = NULL((void*)0); | |||
383 | int selected; | |||
384 | struct isl_tab_undo **snap = NULL((void*)0); | |||
385 | isl_mat *facets = NULL((void*)0); | |||
386 | struct isl_vertex_list *list = NULL((void*)0); | |||
387 | int n_vertices = 0; | |||
388 | isl_vertices *vertices; | |||
389 | ||||
390 | if (!bset) | |||
391 | return NULL((void*)0); | |||
392 | ||||
393 | if (isl_basic_set_plain_is_empty(bset)) | |||
394 | return vertices_empty(bset); | |||
395 | ||||
396 | if (bset->n_eq != 0) | |||
397 | return lower_dim_vertices(bset); | |||
398 | ||||
399 | isl_assert(bset->ctx, isl_basic_set_dim(bset, isl_dim_div) == 0,do { if (isl_basic_set_dim(bset, isl_dim_div) == 0) break; do { isl_handle_error(bset->ctx, isl_error_unknown, "Assertion \"" "isl_basic_set_dim(bset, isl_dim_div) == 0" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_vertices.c" , 400); return ((void*)0); } while (0); } while (0) | |||
400 | return NULL)do { if (isl_basic_set_dim(bset, isl_dim_div) == 0) break; do { isl_handle_error(bset->ctx, isl_error_unknown, "Assertion \"" "isl_basic_set_dim(bset, isl_dim_div) == 0" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_vertices.c" , 400); return ((void*)0); } while (0); } while (0); | |||
401 | ||||
402 | if (isl_basic_set_dim(bset, isl_dim_set) == 0) | |||
403 | return vertices_0D(bset); | |||
404 | ||||
405 | nvar = isl_basic_set_dim(bset, isl_dim_set); | |||
406 | ||||
407 | bset = isl_basic_set_copy(bset); | |||
408 | bset = isl_basic_set_set_rational(bset); | |||
409 | if (!bset) | |||
410 | return NULL((void*)0); | |||
411 | ||||
412 | tab = isl_tab_from_basic_set(bset, 0); | |||
413 | if (!tab) | |||
414 | goto error; | |||
415 | tab->strict_redundant = 1; | |||
416 | ||||
417 | if (tab->empty) { | |||
418 | vertices = vertices_empty(bset); | |||
419 | isl_basic_set_free(bset); | |||
420 | isl_tab_free(tab); | |||
421 | return vertices; | |||
422 | } | |||
423 | ||||
424 | selection = isl_alloc_array(bset->ctx, int, bset->n_ineq)((int *)isl_malloc_or_die(bset->ctx, (bset->n_ineq)*sizeof (int))); | |||
425 | snap = isl_alloc_array(bset->ctx, struct isl_tab_undo *, bset->n_ineq)((struct isl_tab_undo * *)isl_malloc_or_die(bset->ctx, (bset ->n_ineq)*sizeof(struct isl_tab_undo *))); | |||
426 | facets = isl_mat_alloc(bset->ctx, nvar, nvar); | |||
427 | if ((bset->n_ineq && (!selection || !snap)) || !facets) | |||
428 | goto error; | |||
429 | ||||
430 | level = 0; | |||
431 | init = 1; | |||
432 | selected = 0; | |||
433 | ||||
434 | while (level >= 0) { | |||
435 | if (level >= bset->n_ineq || | |||
436 | (!init && selection[level] != SELECTED1)) { | |||
437 | --level; | |||
438 | init = 0; | |||
439 | continue; | |||
440 | } | |||
441 | if (init) { | |||
442 | int ok; | |||
443 | snap[level] = isl_tab_snap(tab); | |||
444 | ok = can_select(bset, level, tab, facets, selected, | |||
445 | selection); | |||
446 | if (ok < 0) | |||
447 | goto error; | |||
448 | if (ok) { | |||
449 | selection[level] = SELECTED1; | |||
450 | selected++; | |||
451 | } else | |||
452 | selection[level] = UNSELECTED0; | |||
453 | } else { | |||
454 | selection[level] = DESELECTED-1; | |||
455 | selected--; | |||
456 | if (isl_tab_rollback(tab, snap[level]) < 0) | |||
457 | goto error; | |||
458 | } | |||
459 | if (selected == nvar) { | |||
460 | if (tab->n_dead == nvar) { | |||
461 | isl_bool added = add_vertex(&list, bset, tab); | |||
462 | if (added < 0) | |||
463 | goto error; | |||
464 | if (added) | |||
465 | n_vertices++; | |||
466 | } | |||
467 | init = 0; | |||
468 | continue; | |||
469 | } | |||
470 | ++level; | |||
471 | init = 1; | |||
472 | } | |||
473 | ||||
474 | isl_mat_free(facets); | |||
475 | free(selection); | |||
476 | free(snap); | |||
477 | ||||
478 | isl_tab_free(tab); | |||
479 | ||||
480 | vertices = vertices_from_list(bset, n_vertices, list); | |||
481 | ||||
482 | vertices = compute_chambers(bset, vertices); | |||
483 | ||||
484 | return vertices; | |||
485 | error: | |||
486 | free_vertex_list(list); | |||
487 | isl_mat_free(facets); | |||
488 | free(selection); | |||
489 | free(snap); | |||
490 | isl_tab_free(tab); | |||
491 | isl_basic_set_free(bset); | |||
492 | return NULL((void*)0); | |||
493 | } | |||
494 | ||||
495 | struct isl_chamber_list { | |||
496 | struct isl_chamber c; | |||
497 | struct isl_chamber_list *next; | |||
498 | }; | |||
499 | ||||
500 | static void free_chamber_list(struct isl_chamber_list *list) | |||
501 | { | |||
502 | struct isl_chamber_list *next; | |||
503 | ||||
504 | for (; list; list = next) { | |||
505 | next = list->next; | |||
506 | isl_basic_set_free(list->c.dom); | |||
507 | free(list->c.vertices); | |||
508 | free(list); | |||
509 | } | |||
510 | } | |||
511 | ||||
512 | /* Check whether the basic set "bset" is a superset of the basic set described | |||
513 | * by "tab", i.e., check whether all constraints of "bset" are redundant. | |||
514 | */ | |||
515 | static isl_bool bset_covers_tab(__isl_keep isl_basic_setisl_basic_map *bset, | |||
516 | struct isl_tab *tab) | |||
517 | { | |||
518 | int i; | |||
519 | ||||
520 | if (!bset || !tab) | |||
521 | return isl_bool_error; | |||
522 | ||||
523 | for (i = 0; i < bset->n_ineq; ++i) { | |||
524 | enum isl_ineq_type type = isl_tab_ineq_type(tab, bset->ineq[i]); | |||
525 | switch (type) { | |||
526 | case isl_ineq_error: return isl_bool_error; | |||
527 | case isl_ineq_redundant: continue; | |||
528 | default: return isl_bool_false; | |||
529 | } | |||
530 | } | |||
531 | ||||
532 | return isl_bool_true; | |||
533 | } | |||
534 | ||||
535 | static __isl_give isl_vertices *vertices_add_chambers( | |||
536 | __isl_take isl_vertices *vertices, int n_chambers, | |||
537 | struct isl_chamber_list *list) | |||
538 | { | |||
539 | int i; | |||
540 | isl_ctx *ctx; | |||
541 | struct isl_chamber_list *next; | |||
542 | ||||
543 | ctx = isl_vertices_get_ctx(vertices); | |||
544 | vertices->c = isl_alloc_array(ctx, struct isl_chamber, n_chambers)((struct isl_chamber *)isl_malloc_or_die(ctx, (n_chambers)*sizeof (struct isl_chamber))); | |||
545 | if (!vertices->c) | |||
546 | goto error; | |||
547 | vertices->n_chambers = n_chambers; | |||
548 | ||||
549 | for (i = 0; list; list = next, i++) { | |||
550 | next = list->next; | |||
551 | vertices->c[i] = list->c; | |||
552 | free(list); | |||
553 | } | |||
554 | ||||
555 | return vertices; | |||
556 | error: | |||
557 | isl_vertices_free(vertices); | |||
558 | free_chamber_list(list); | |||
559 | return NULL((void*)0); | |||
560 | } | |||
561 | ||||
562 | /* Can "tab" be intersected with "bset" without resulting in | |||
563 | * a lower-dimensional set. | |||
564 | * "bset" itself is assumed to be full-dimensional. | |||
565 | */ | |||
566 | static isl_bool can_intersect(struct isl_tab *tab, | |||
567 | __isl_keep isl_basic_setisl_basic_map *bset) | |||
568 | { | |||
569 | int i; | |||
570 | struct isl_tab_undo *snap; | |||
571 | ||||
572 | if (bset->n_eq > 0) | |||
573 | isl_die(isl_basic_set_get_ctx(bset), isl_error_internal,do { isl_handle_error(isl_basic_set_get_ctx(bset), isl_error_internal , "expecting full-dimensional input", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_vertices.c" , 575); return isl_bool_error; } while (0) | |||
574 | "expecting full-dimensional input",do { isl_handle_error(isl_basic_set_get_ctx(bset), isl_error_internal , "expecting full-dimensional input", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_vertices.c" , 575); return isl_bool_error; } while (0) | |||
575 | return isl_bool_error)do { isl_handle_error(isl_basic_set_get_ctx(bset), isl_error_internal , "expecting full-dimensional input", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_vertices.c" , 575); return isl_bool_error; } while (0); | |||
576 | ||||
577 | if (isl_tab_extend_cons(tab, bset->n_ineq) < 0) | |||
578 | return isl_bool_error; | |||
579 | ||||
580 | snap = isl_tab_snap(tab); | |||
581 | ||||
582 | for (i = 0; i < bset->n_ineq; ++i) { | |||
583 | if (isl_tab_ineq_type(tab, bset->ineq[i]) == isl_ineq_redundant) | |||
584 | continue; | |||
585 | if (isl_tab_add_ineq(tab, bset->ineq[i]) < 0) | |||
586 | return isl_bool_error; | |||
587 | } | |||
588 | ||||
589 | if (isl_tab_detect_implicit_equalities(tab) < 0) | |||
590 | return isl_bool_error; | |||
591 | if (tab->n_dead) { | |||
592 | if (isl_tab_rollback(tab, snap) < 0) | |||
593 | return isl_bool_error; | |||
594 | return isl_bool_false; | |||
595 | } | |||
596 | ||||
597 | return isl_bool_true; | |||
598 | } | |||
599 | ||||
600 | static int add_chamber(struct isl_chamber_list **list, | |||
601 | __isl_keep isl_vertices *vertices, struct isl_tab *tab, int *selection) | |||
602 | { | |||
603 | int n_frozen; | |||
604 | int i, j; | |||
605 | int n_vertices = 0; | |||
606 | struct isl_tab_undo *snap; | |||
607 | struct isl_chamber_list *c = NULL((void*)0); | |||
608 | ||||
609 | for (i = 0; i < vertices->n_vertices; ++i) | |||
610 | if (selection[i]) | |||
611 | n_vertices++; | |||
612 | ||||
613 | snap = isl_tab_snap(tab); | |||
614 | ||||
615 | for (i = 0; i < tab->n_con && tab->con[i].frozen; ++i) | |||
616 | tab->con[i].frozen = 0; | |||
617 | n_frozen = i; | |||
618 | ||||
619 | if (isl_tab_detect_redundant(tab) < 0) | |||
620 | return -1; | |||
621 | ||||
622 | c = isl_calloc_type(tab->mat->ctx, struct isl_chamber_list)((struct isl_chamber_list *)isl_calloc_or_die(tab->mat-> ctx, 1, sizeof(struct isl_chamber_list))); | |||
623 | if (!c) | |||
624 | goto error; | |||
625 | c->c.vertices = isl_alloc_array(tab->mat->ctx, int, n_vertices)((int *)isl_malloc_or_die(tab->mat->ctx, (n_vertices)*sizeof (int))); | |||
626 | if (n_vertices && !c->c.vertices) | |||
627 | goto error; | |||
628 | c->c.dom = isl_basic_set_copy(isl_tab_peek_bset(tab)); | |||
629 | c->c.dom = isl_basic_set_set_rational(c->c.dom); | |||
630 | c->c.dom = isl_basic_set_cow(c->c.dom); | |||
631 | c->c.dom = isl_basic_set_update_from_tab(c->c.dom, tab); | |||
632 | c->c.dom = isl_basic_set_simplify(c->c.dom); | |||
633 | c->c.dom = isl_basic_set_finalize(c->c.dom); | |||
634 | if (!c->c.dom) | |||
635 | goto error; | |||
636 | ||||
637 | c->c.n_vertices = n_vertices; | |||
638 | ||||
639 | for (i = 0, j = 0; i < vertices->n_vertices; ++i) | |||
640 | if (selection[i]) { | |||
641 | c->c.vertices[j] = i; | |||
642 | j++; | |||
643 | } | |||
644 | ||||
645 | c->next = *list; | |||
646 | *list = c; | |||
647 | ||||
648 | for (i = 0; i < n_frozen; ++i) | |||
649 | tab->con[i].frozen = 1; | |||
650 | ||||
651 | if (isl_tab_rollback(tab, snap) < 0) | |||
652 | return -1; | |||
653 | ||||
654 | return 0; | |||
655 | error: | |||
656 | free_chamber_list(c); | |||
657 | return -1; | |||
658 | } | |||
659 | ||||
660 | struct isl_facet_todo { | |||
661 | struct isl_tab *tab; /* A tableau representation of the facet */ | |||
662 | isl_basic_setisl_basic_map *bset; /* A normalized basic set representation */ | |||
663 | isl_vec *constraint; /* Constraint pointing to the other side */ | |||
664 | struct isl_facet_todo *next; | |||
665 | }; | |||
666 | ||||
667 | static void free_todo(struct isl_facet_todo *todo) | |||
668 | { | |||
669 | while (todo) { | |||
670 | struct isl_facet_todo *next = todo->next; | |||
671 | ||||
672 | isl_tab_free(todo->tab); | |||
673 | isl_basic_set_free(todo->bset); | |||
674 | isl_vec_free(todo->constraint); | |||
675 | free(todo); | |||
676 | ||||
677 | todo = next; | |||
678 | } | |||
679 | } | |||
680 | ||||
681 | static struct isl_facet_todo *create_todo(struct isl_tab *tab, int con) | |||
682 | { | |||
683 | int i; | |||
684 | int n_frozen; | |||
685 | struct isl_tab_undo *snap; | |||
686 | struct isl_facet_todo *todo; | |||
687 | ||||
688 | snap = isl_tab_snap(tab); | |||
689 | ||||
690 | for (i = 0; i < tab->n_con && tab->con[i].frozen; ++i) | |||
691 | tab->con[i].frozen = 0; | |||
692 | n_frozen = i; | |||
693 | ||||
694 | if (isl_tab_detect_redundant(tab) < 0) | |||
695 | return NULL((void*)0); | |||
696 | ||||
697 | todo = isl_calloc_type(tab->mat->ctx, struct isl_facet_todo)((struct isl_facet_todo *)isl_calloc_or_die(tab->mat->ctx , 1, sizeof(struct isl_facet_todo))); | |||
698 | if (!todo) | |||
699 | return NULL((void*)0); | |||
700 | ||||
701 | todo->constraint = isl_vec_alloc(tab->mat->ctx, 1 + tab->n_var); | |||
702 | if (!todo->constraint) | |||
703 | goto error; | |||
704 | isl_seq_neg(todo->constraint->el, tab->bmap->ineq[con], 1 + tab->n_var); | |||
705 | todo->bset = isl_basic_set_copy(isl_tab_peek_bset(tab)); | |||
706 | todo->bset = isl_basic_set_set_rational(todo->bset); | |||
707 | todo->bset = isl_basic_set_cow(todo->bset); | |||
708 | todo->bset = isl_basic_set_update_from_tab(todo->bset, tab); | |||
709 | todo->bset = isl_basic_set_simplify(todo->bset); | |||
710 | todo->bset = isl_basic_set_sort_constraints(todo->bset); | |||
711 | if (!todo->bset) | |||
712 | goto error; | |||
713 | ISL_F_SET(todo->bset, ISL_BASIC_SET_NORMALIZED)(((todo->bset)->flags) |= ((1 << 5))); | |||
714 | todo->tab = isl_tab_dup(tab); | |||
715 | if (!todo->tab) | |||
716 | goto error; | |||
717 | ||||
718 | for (i = 0; i < n_frozen; ++i) | |||
719 | tab->con[i].frozen = 1; | |||
720 | ||||
721 | if (isl_tab_rollback(tab, snap) < 0) | |||
722 | goto error; | |||
723 | ||||
724 | return todo; | |||
725 | error: | |||
726 | free_todo(todo); | |||
727 | return NULL((void*)0); | |||
728 | } | |||
729 | ||||
730 | /* Create todo items for all interior facets of the chamber represented | |||
731 | * by "tab" and collect them in "next". | |||
732 | */ | |||
733 | static int init_todo(struct isl_facet_todo **next, struct isl_tab *tab) | |||
734 | { | |||
735 | int i; | |||
736 | struct isl_tab_undo *snap; | |||
737 | struct isl_facet_todo *todo; | |||
738 | ||||
739 | snap = isl_tab_snap(tab); | |||
740 | ||||
741 | for (i = 0; i < tab->n_con; ++i) { | |||
742 | if (tab->con[i].frozen) | |||
743 | continue; | |||
744 | if (tab->con[i].is_redundant) | |||
745 | continue; | |||
746 | ||||
747 | if (isl_tab_select_facet(tab, i) < 0) | |||
748 | return -1; | |||
749 | ||||
750 | todo = create_todo(tab, i); | |||
751 | if (!todo) | |||
752 | return -1; | |||
753 | ||||
754 | todo->next = *next; | |||
755 | *next = todo; | |||
756 | ||||
757 | if (isl_tab_rollback(tab, snap) < 0) | |||
758 | return -1; | |||
759 | } | |||
760 | ||||
761 | return 0; | |||
762 | } | |||
763 | ||||
764 | /* Does the linked list contain a todo item that is the opposite of "todo". | |||
765 | * If so, return 1 and remove the opposite todo item. | |||
766 | */ | |||
767 | static int has_opposite(struct isl_facet_todo *todo, | |||
768 | struct isl_facet_todo **list) | |||
769 | { | |||
770 | for (; *list; list = &(*list)->next) { | |||
771 | int eq; | |||
772 | eq = isl_basic_set_plain_is_equal(todo->bset, (*list)->bset); | |||
773 | if (eq < 0) | |||
774 | return -1; | |||
775 | if (!eq) | |||
776 | continue; | |||
777 | todo = *list; | |||
778 | *list = todo->next; | |||
779 | todo->next = NULL((void*)0); | |||
780 | free_todo(todo); | |||
781 | return 1; | |||
782 | } | |||
783 | ||||
784 | return 0; | |||
785 | } | |||
786 | ||||
787 | /* Create todo items for all interior facets of the chamber represented | |||
788 | * by "tab" and collect them in first->next, taking care to cancel | |||
789 | * opposite todo items. | |||
790 | */ | |||
791 | static int update_todo(struct isl_facet_todo *first, struct isl_tab *tab) | |||
792 | { | |||
793 | int i; | |||
794 | struct isl_tab_undo *snap; | |||
795 | struct isl_facet_todo *todo; | |||
796 | ||||
797 | snap = isl_tab_snap(tab); | |||
798 | ||||
799 | for (i = 0; i < tab->n_con; ++i) { | |||
800 | int drop; | |||
801 | ||||
802 | if (tab->con[i].frozen) | |||
803 | continue; | |||
804 | if (tab->con[i].is_redundant) | |||
805 | continue; | |||
806 | ||||
807 | if (isl_tab_select_facet(tab, i) < 0) | |||
808 | return -1; | |||
809 | ||||
810 | todo = create_todo(tab, i); | |||
811 | if (!todo) | |||
812 | return -1; | |||
813 | ||||
814 | drop = has_opposite(todo, &first->next); | |||
815 | if (drop < 0) | |||
816 | return -1; | |||
817 | ||||
818 | if (drop) | |||
819 | free_todo(todo); | |||
820 | else { | |||
821 | todo->next = first->next; | |||
822 | first->next = todo; | |||
823 | } | |||
824 | ||||
825 | if (isl_tab_rollback(tab, snap) < 0) | |||
826 | return -1; | |||
827 | } | |||
828 | ||||
829 | return 0; | |||
830 | } | |||
831 | ||||
832 | /* Compute the chamber decomposition of the parametric polytope respresented | |||
833 | * by "bset" given the parametric vertices and their activity domains. | |||
834 | * | |||
835 | * We are only interested in full-dimensional chambers. | |||
836 | * Each of these chambers is the intersection of the activity domains of | |||
837 | * one or more vertices and the union of all chambers is equal to the | |||
838 | * projection of the entire parametric polytope onto the parameter space. | |||
839 | * | |||
840 | * We first create an initial chamber by intersecting as many activity | |||
841 | * domains as possible without ending up with an empty or lower-dimensional | |||
842 | * set. As a minor optimization, we only consider those activity domains | |||
843 | * that contain some arbitrary point. | |||
844 | * | |||
845 | * For each of the interior facets of the chamber, we construct a todo item, | |||
846 | * containing the facet and a constraint containing the other side of the facet, | |||
847 | * for constructing the chamber on the other side. | |||
848 | * While their are any todo items left, we pick a todo item and | |||
849 | * create the required chamber by intersecting all activity domains | |||
850 | * that contain the facet and have a full-dimensional intersection with | |||
851 | * the other side of the facet. For each of the interior facets, we | |||
852 | * again create todo items, taking care to cancel opposite todo items. | |||
853 | */ | |||
854 | static __isl_give isl_vertices *compute_chambers(__isl_take isl_basic_setisl_basic_map *bset, | |||
855 | __isl_take isl_vertices *vertices) | |||
856 | { | |||
857 | int i; | |||
858 | isl_ctx *ctx; | |||
859 | isl_vec *sample = NULL((void*)0); | |||
860 | struct isl_tab *tab = NULL((void*)0); | |||
861 | struct isl_tab_undo *snap; | |||
862 | int *selection = NULL((void*)0); | |||
863 | int n_chambers = 0; | |||
864 | struct isl_chamber_list *list = NULL((void*)0); | |||
865 | struct isl_facet_todo *todo = NULL((void*)0); | |||
866 | ||||
867 | if (!bset || !vertices) | |||
868 | goto error; | |||
869 | ||||
870 | ctx = isl_vertices_get_ctx(vertices); | |||
871 | selection = isl_alloc_array(ctx, int, vertices->n_vertices)((int *)isl_malloc_or_die(ctx, (vertices->n_vertices)*sizeof (int))); | |||
872 | if (vertices->n_vertices && !selection) | |||
873 | goto error; | |||
874 | ||||
875 | bset = isl_basic_set_params(bset); | |||
876 | ||||
877 | tab = isl_tab_from_basic_set(bset, 1); | |||
878 | if (!tab) | |||
879 | goto error; | |||
880 | for (i = 0; i < bset->n_ineq; ++i) | |||
881 | if (isl_tab_freeze_constraint(tab, i) < 0) | |||
882 | goto error; | |||
883 | isl_basic_set_free(bset); | |||
884 | ||||
885 | snap = isl_tab_snap(tab); | |||
886 | ||||
887 | sample = isl_tab_get_sample_value(tab); | |||
888 | ||||
889 | for (i = 0; i < vertices->n_vertices; ++i) { | |||
890 | selection[i] = isl_basic_set_contains(vertices->v[i].dom, sample); | |||
891 | if (selection[i] < 0) | |||
892 | goto error; | |||
893 | if (!selection[i]) | |||
894 | continue; | |||
895 | selection[i] = can_intersect(tab, vertices->v[i].dom); | |||
896 | if (selection[i] < 0) | |||
897 | goto error; | |||
898 | } | |||
899 | ||||
900 | if (isl_tab_detect_redundant(tab) < 0) | |||
901 | goto error; | |||
902 | ||||
903 | if (add_chamber(&list, vertices, tab, selection) < 0) | |||
904 | goto error; | |||
905 | n_chambers++; | |||
906 | ||||
907 | if (init_todo(&todo, tab) < 0) | |||
908 | goto error; | |||
909 | ||||
910 | while (todo) { | |||
911 | struct isl_facet_todo *next; | |||
912 | ||||
913 | if (isl_tab_rollback(tab, snap) < 0) | |||
914 | goto error; | |||
915 | ||||
916 | if (isl_tab_add_ineq(tab, todo->constraint->el) < 0) | |||
917 | goto error; | |||
918 | if (isl_tab_freeze_constraint(tab, tab->n_con - 1) < 0) | |||
919 | goto error; | |||
920 | ||||
921 | for (i = 0; i < vertices->n_vertices; ++i) { | |||
922 | selection[i] = bset_covers_tab(vertices->v[i].dom, | |||
923 | todo->tab); | |||
924 | if (selection[i] < 0) | |||
925 | goto error; | |||
926 | if (!selection[i]) | |||
927 | continue; | |||
928 | selection[i] = can_intersect(tab, vertices->v[i].dom); | |||
929 | if (selection[i] < 0) | |||
930 | goto error; | |||
931 | } | |||
932 | ||||
933 | if (isl_tab_detect_redundant(tab) < 0) | |||
934 | goto error; | |||
935 | ||||
936 | if (add_chamber(&list, vertices, tab, selection) < 0) | |||
937 | goto error; | |||
938 | n_chambers++; | |||
939 | ||||
940 | if (update_todo(todo, tab) < 0) | |||
941 | goto error; | |||
942 | ||||
943 | next = todo->next; | |||
944 | todo->next = NULL((void*)0); | |||
945 | free_todo(todo); | |||
946 | todo = next; | |||
947 | } | |||
948 | ||||
949 | isl_vec_free(sample); | |||
950 | ||||
951 | isl_tab_free(tab); | |||
952 | free(selection); | |||
953 | ||||
954 | vertices = vertices_add_chambers(vertices, n_chambers, list); | |||
955 | ||||
956 | for (i = 0; vertices && i < vertices->n_vertices; ++i) { | |||
957 | isl_basic_set_free(vertices->v[i].dom); | |||
958 | vertices->v[i].dom = NULL((void*)0); | |||
959 | } | |||
960 | ||||
961 | return vertices; | |||
962 | error: | |||
963 | free_chamber_list(list); | |||
964 | free_todo(todo); | |||
965 | isl_vec_free(sample); | |||
966 | isl_tab_free(tab); | |||
967 | free(selection); | |||
968 | if (!tab) | |||
969 | isl_basic_set_free(bset); | |||
970 | isl_vertices_free(vertices); | |||
971 | return NULL((void*)0); | |||
972 | } | |||
973 | ||||
974 | isl_ctx *isl_vertex_get_ctx(__isl_keep isl_vertex *vertex) | |||
975 | { | |||
976 | return vertex ? isl_vertices_get_ctx(vertex->vertices) : NULL((void*)0); | |||
977 | } | |||
978 | ||||
979 | int isl_vertex_get_id(__isl_keep isl_vertex *vertex) | |||
980 | { | |||
981 | return vertex ? vertex->id : -1; | |||
982 | } | |||
983 | ||||
984 | /* Return the activity domain of the vertex "vertex". | |||
985 | */ | |||
986 | __isl_give isl_basic_setisl_basic_map *isl_vertex_get_domain(__isl_keep isl_vertex *vertex) | |||
987 | { | |||
988 | struct isl_vertex *v; | |||
989 | ||||
990 | if (!vertex) | |||
991 | return NULL((void*)0); | |||
992 | ||||
993 | v = &vertex->vertices->v[vertex->id]; | |||
994 | if (!v->dom) { | |||
995 | v->dom = isl_basic_set_copy(v->vertex); | |||
996 | v->dom = isl_basic_set_params(v->dom); | |||
997 | v->dom = isl_basic_set_set_integral(v->dom); | |||
998 | } | |||
999 | ||||
1000 | return isl_basic_set_copy(v->dom); | |||
1001 | } | |||
1002 | ||||
1003 | /* Return a multiple quasi-affine expression describing the vertex "vertex" | |||
1004 | * in terms of the parameters, | |||
1005 | */ | |||
1006 | __isl_give isl_multi_aff *isl_vertex_get_expr(__isl_keep isl_vertex *vertex) | |||
1007 | { | |||
1008 | struct isl_vertex *v; | |||
1009 | isl_basic_setisl_basic_map *bset; | |||
1010 | ||||
1011 | if (!vertex) | |||
1012 | return NULL((void*)0); | |||
1013 | ||||
1014 | v = &vertex->vertices->v[vertex->id]; | |||
1015 | ||||
1016 | bset = isl_basic_set_copy(v->vertex); | |||
1017 | return isl_multi_aff_from_basic_set_equalities(bset); | |||
1018 | } | |||
1019 | ||||
1020 | static __isl_give isl_vertex *isl_vertex_alloc(__isl_take isl_vertices *vertices, | |||
1021 | int id) | |||
1022 | { | |||
1023 | isl_ctx *ctx; | |||
1024 | isl_vertex *vertex; | |||
1025 | ||||
1026 | if (!vertices) | |||
1027 | return NULL((void*)0); | |||
1028 | ||||
1029 | ctx = isl_vertices_get_ctx(vertices); | |||
1030 | vertex = isl_alloc_type(ctx, isl_vertex)((isl_vertex *)isl_malloc_or_die(ctx, sizeof(isl_vertex))); | |||
1031 | if (!vertex) | |||
1032 | goto error; | |||
1033 | ||||
1034 | vertex->vertices = vertices; | |||
1035 | vertex->id = id; | |||
1036 | ||||
1037 | return vertex; | |||
1038 | error: | |||
1039 | isl_vertices_free(vertices); | |||
1040 | return NULL((void*)0); | |||
1041 | } | |||
1042 | ||||
1043 | void isl_vertex_free(__isl_take isl_vertex *vertex) | |||
1044 | { | |||
1045 | if (!vertex) | |||
1046 | return; | |||
1047 | isl_vertices_free(vertex->vertices); | |||
1048 | free(vertex); | |||
1049 | } | |||
1050 | ||||
1051 | isl_ctx *isl_cell_get_ctx(__isl_keep isl_cell *cell) | |||
1052 | { | |||
1053 | return cell ? cell->dom->ctx : NULL((void*)0); | |||
1054 | } | |||
1055 | ||||
1056 | __isl_give isl_basic_setisl_basic_map *isl_cell_get_domain(__isl_keep isl_cell *cell) | |||
1057 | { | |||
1058 | return cell ? isl_basic_set_copy(cell->dom) : NULL((void*)0); | |||
1059 | } | |||
1060 | ||||
1061 | static __isl_give isl_cell *isl_cell_alloc(__isl_take isl_vertices *vertices, | |||
1062 | __isl_take isl_basic_setisl_basic_map *dom, int id) | |||
1063 | { | |||
1064 | int i; | |||
1065 | isl_cell *cell = NULL((void*)0); | |||
1066 | ||||
1067 | if (!vertices || !dom) | |||
1068 | goto error; | |||
1069 | ||||
1070 | cell = isl_calloc_type(dom->ctx, isl_cell)((isl_cell *)isl_calloc_or_die(dom->ctx, 1, sizeof(isl_cell ))); | |||
1071 | if (!cell) | |||
1072 | goto error; | |||
1073 | ||||
1074 | cell->n_vertices = vertices->c[id].n_vertices; | |||
1075 | cell->ids = isl_alloc_array(dom->ctx, int, cell->n_vertices)((int *)isl_malloc_or_die(dom->ctx, (cell->n_vertices)* sizeof(int))); | |||
1076 | if (cell->n_vertices && !cell->ids) | |||
1077 | goto error; | |||
1078 | for (i = 0; i < cell->n_vertices; ++i) | |||
1079 | cell->ids[i] = vertices->c[id].vertices[i]; | |||
1080 | cell->vertices = vertices; | |||
1081 | cell->dom = dom; | |||
1082 | ||||
1083 | return cell; | |||
1084 | error: | |||
1085 | isl_cell_free(cell); | |||
1086 | isl_vertices_free(vertices); | |||
1087 | isl_basic_set_free(dom); | |||
1088 | return NULL((void*)0); | |||
1089 | } | |||
1090 | ||||
1091 | void isl_cell_free(__isl_take isl_cell *cell) | |||
1092 | { | |||
1093 | if (!cell) | |||
1094 | return; | |||
1095 | ||||
1096 | isl_vertices_free(cell->vertices); | |||
| ||||
1097 | free(cell->ids); | |||
1098 | isl_basic_set_free(cell->dom); | |||
1099 | free(cell); | |||
1100 | } | |||
1101 | ||||
1102 | /* Create a tableau of the cone obtained by first homogenizing the given | |||
1103 | * polytope and then making all inequalities strict by setting the | |||
1104 | * constant term to -1. | |||
1105 | */ | |||
1106 | static struct isl_tab *tab_for_shifted_cone(__isl_keep isl_basic_setisl_basic_map *bset) | |||
1107 | { | |||
1108 | int i; | |||
1109 | isl_vec *c = NULL((void*)0); | |||
1110 | struct isl_tab *tab; | |||
1111 | ||||
1112 | if (!bset) | |||
1113 | return NULL((void*)0); | |||
1114 | tab = isl_tab_alloc(bset->ctx, bset->n_eq + bset->n_ineq + 1, | |||
1115 | 1 + isl_basic_set_total_dim(bset), 0); | |||
1116 | if (!tab) | |||
1117 | return NULL((void*)0); | |||
1118 | tab->rational = ISL_F_ISSET(bset, ISL_BASIC_SET_RATIONAL)(!!(((bset)->flags) & ((1 << 4)))); | |||
1119 | if (ISL_F_ISSET(bset, ISL_BASIC_MAP_EMPTY)(!!(((bset)->flags) & ((1 << 1))))) { | |||
1120 | if (isl_tab_mark_empty(tab) < 0) | |||
1121 | goto error; | |||
1122 | return tab; | |||
1123 | } | |||
1124 | ||||
1125 | c = isl_vec_alloc(bset->ctx, 1 + 1 + isl_basic_set_total_dim(bset)); | |||
1126 | if (!c) | |||
1127 | goto error; | |||
1128 | ||||
1129 | isl_int_set_si(c->el[0], 0)isl_sioimath_set_si((c->el[0]), 0); | |||
1130 | for (i = 0; i < bset->n_eq; ++i) { | |||
1131 | isl_seq_cpy(c->el + 1, bset->eq[i], c->size - 1); | |||
1132 | if (isl_tab_add_eq(tab, c->el) < 0) | |||
1133 | goto error; | |||
1134 | } | |||
1135 | ||||
1136 | isl_int_set_si(c->el[0], -1)isl_sioimath_set_si((c->el[0]), -1); | |||
1137 | for (i = 0; i < bset->n_ineq; ++i) { | |||
1138 | isl_seq_cpy(c->el + 1, bset->ineq[i], c->size - 1); | |||
1139 | if (isl_tab_add_ineq(tab, c->el) < 0) | |||
1140 | goto error; | |||
1141 | if (tab->empty) { | |||
1142 | isl_vec_free(c); | |||
1143 | return tab; | |||
1144 | } | |||
1145 | } | |||
1146 | ||||
1147 | isl_seq_clr(c->el + 1, c->size - 1); | |||
1148 | isl_int_set_si(c->el[1], 1)isl_sioimath_set_si((c->el[1]), 1); | |||
1149 | if (isl_tab_add_ineq(tab, c->el) < 0) | |||
1150 | goto error; | |||
1151 | ||||
1152 | isl_vec_free(c); | |||
1153 | return tab; | |||
1154 | error: | |||
1155 | isl_vec_free(c); | |||
1156 | isl_tab_free(tab); | |||
1157 | return NULL((void*)0); | |||
1158 | } | |||
1159 | ||||
1160 | /* Compute an interior point of "bset" by selecting an interior | |||
1161 | * point in homogeneous space and projecting the point back down. | |||
1162 | */ | |||
1163 | static __isl_give isl_vec *isl_basic_set_interior_point( | |||
1164 | __isl_keep isl_basic_setisl_basic_map *bset) | |||
1165 | { | |||
1166 | isl_vec *vec; | |||
1167 | struct isl_tab *tab; | |||
1168 | ||||
1169 | tab = tab_for_shifted_cone(bset); | |||
1170 | vec = isl_tab_get_sample_value(tab); | |||
1171 | isl_tab_free(tab); | |||
1172 | if (!vec) | |||
1173 | return NULL((void*)0); | |||
1174 | ||||
1175 | isl_seq_cpy(vec->el, vec->el + 1, vec->size - 1); | |||
1176 | vec->size--; | |||
1177 | ||||
1178 | return vec; | |||
1179 | } | |||
1180 | ||||
1181 | /* Call "fn" on all chambers of the parametric polytope with the shared | |||
1182 | * facets of neighboring chambers only appearing in one of the chambers. | |||
1183 | * | |||
1184 | * We pick an interior point from one of the chambers and then make | |||
1185 | * all constraints that do not satisfy this point strict. | |||
1186 | * For constraints that saturate the interior point, the sign | |||
1187 | * of the first non-zero coefficient is used to determine which | |||
1188 | * of the two (internal) constraints should be tightened. | |||
1189 | */ | |||
1190 | isl_stat isl_vertices_foreach_disjoint_cell(__isl_keep isl_vertices *vertices, | |||
1191 | isl_stat (*fn)(__isl_take isl_cell *cell, void *user), void *user) | |||
1192 | { | |||
1193 | int i; | |||
1194 | isl_vec *vec; | |||
1195 | isl_cell *cell; | |||
1196 | ||||
1197 | if (!vertices) | |||
1198 | return isl_stat_error; | |||
1199 | ||||
1200 | if (vertices->n_chambers == 0) | |||
1201 | return isl_stat_ok; | |||
1202 | ||||
1203 | if (vertices->n_chambers == 1) { | |||
1204 | isl_basic_setisl_basic_map *dom = isl_basic_set_copy(vertices->c[0].dom); | |||
1205 | dom = isl_basic_set_set_integral(dom); | |||
1206 | cell = isl_cell_alloc(isl_vertices_copy(vertices), dom, 0); | |||
1207 | if (!cell) | |||
1208 | return isl_stat_error; | |||
1209 | return fn(cell, user); | |||
1210 | } | |||
1211 | ||||
1212 | vec = isl_basic_set_interior_point(vertices->c[0].dom); | |||
1213 | if (!vec) | |||
1214 | return isl_stat_error; | |||
1215 | ||||
1216 | for (i = 0; i < vertices->n_chambers; ++i) { | |||
1217 | int r; | |||
1218 | isl_basic_setisl_basic_map *dom = isl_basic_set_copy(vertices->c[i].dom); | |||
1219 | if (i) | |||
1220 | dom = isl_basic_set_tighten_outward(dom, vec); | |||
1221 | dom = isl_basic_set_set_integral(dom); | |||
1222 | cell = isl_cell_alloc(isl_vertices_copy(vertices), dom, i); | |||
1223 | if (!cell) | |||
1224 | goto error; | |||
1225 | r = fn(cell, user); | |||
1226 | if (r < 0) | |||
1227 | goto error; | |||
1228 | } | |||
1229 | ||||
1230 | isl_vec_free(vec); | |||
1231 | ||||
1232 | return isl_stat_ok; | |||
1233 | error: | |||
1234 | isl_vec_free(vec); | |||
1235 | return isl_stat_error; | |||
1236 | } | |||
1237 | ||||
1238 | isl_stat isl_vertices_foreach_cell(__isl_keep isl_vertices *vertices, | |||
1239 | isl_stat (*fn)(__isl_take isl_cell *cell, void *user), void *user) | |||
1240 | { | |||
1241 | int i; | |||
1242 | isl_cell *cell; | |||
1243 | ||||
1244 | if (!vertices) | |||
1245 | return isl_stat_error; | |||
1246 | ||||
1247 | if (vertices->n_chambers == 0) | |||
1248 | return isl_stat_ok; | |||
1249 | ||||
1250 | for (i = 0; i < vertices->n_chambers; ++i) { | |||
1251 | isl_stat r; | |||
1252 | isl_basic_setisl_basic_map *dom = isl_basic_set_copy(vertices->c[i].dom); | |||
1253 | ||||
1254 | cell = isl_cell_alloc(isl_vertices_copy(vertices), dom, i); | |||
1255 | if (!cell) | |||
1256 | return isl_stat_error; | |||
1257 | ||||
1258 | r = fn(cell, user); | |||
1259 | if (r < 0) | |||
1260 | return isl_stat_error; | |||
1261 | } | |||
1262 | ||||
1263 | return isl_stat_ok; | |||
1264 | } | |||
1265 | ||||
1266 | isl_stat isl_vertices_foreach_vertex(__isl_keep isl_vertices *vertices, | |||
1267 | isl_stat (*fn)(__isl_take isl_vertex *vertex, void *user), void *user) | |||
1268 | { | |||
1269 | int i; | |||
1270 | isl_vertex *vertex; | |||
1271 | ||||
1272 | if (!vertices) | |||
1273 | return isl_stat_error; | |||
1274 | ||||
1275 | if (vertices->n_vertices == 0) | |||
1276 | return isl_stat_ok; | |||
1277 | ||||
1278 | for (i = 0; i < vertices->n_vertices; ++i) { | |||
1279 | isl_stat r; | |||
1280 | ||||
1281 | vertex = isl_vertex_alloc(isl_vertices_copy(vertices), i); | |||
1282 | if (!vertex) | |||
1283 | return isl_stat_error; | |||
1284 | ||||
1285 | r = fn(vertex, user); | |||
1286 | if (r < 0) | |||
1287 | return isl_stat_error; | |||
1288 | } | |||
1289 | ||||
1290 | return isl_stat_ok; | |||
1291 | } | |||
1292 | ||||
1293 | isl_stat isl_cell_foreach_vertex(__isl_keep isl_cell *cell, | |||
1294 | isl_stat (*fn)(__isl_take isl_vertex *vertex, void *user), void *user) | |||
1295 | { | |||
1296 | int i; | |||
1297 | isl_vertex *vertex; | |||
1298 | ||||
1299 | if (!cell) | |||
1300 | return isl_stat_error; | |||
1301 | ||||
1302 | if (cell->n_vertices == 0) | |||
1303 | return isl_stat_ok; | |||
1304 | ||||
1305 | for (i = 0; i < cell->n_vertices; ++i) { | |||
1306 | isl_stat r; | |||
1307 | ||||
1308 | vertex = isl_vertex_alloc(isl_vertices_copy(cell->vertices), | |||
1309 | cell->ids[i]); | |||
1310 | if (!vertex) | |||
1311 | return isl_stat_error; | |||
1312 | ||||
1313 | r = fn(vertex, user); | |||
1314 | if (r < 0) | |||
1315 | return isl_stat_error; | |||
1316 | } | |||
1317 | ||||
1318 | return isl_stat_ok; | |||
1319 | } | |||
1320 | ||||
1321 | isl_ctx *isl_vertices_get_ctx(__isl_keep isl_vertices *vertices) | |||
1322 | { | |||
1323 | return vertices ? vertices->bset->ctx : NULL((void*)0); | |||
1324 | } | |||
1325 | ||||
1326 | int isl_vertices_get_n_vertices(__isl_keep isl_vertices *vertices) | |||
1327 | { | |||
1328 | return vertices ? vertices->n_vertices : -1; | |||
1329 | } | |||
1330 | ||||
1331 | __isl_give isl_vertices *isl_morph_vertices(__isl_take isl_morph *morph, | |||
1332 | __isl_take isl_vertices *vertices) | |||
1333 | { | |||
1334 | int i; | |||
1335 | isl_morph *param_morph = NULL((void*)0); | |||
1336 | ||||
1337 | if (!morph || !vertices) | |||
1338 | goto error; | |||
1339 | ||||
1340 | isl_assert(vertices->bset->ctx, vertices->ref == 1, goto error)do { if (vertices->ref == 1) break; do { isl_handle_error( vertices->bset->ctx, isl_error_unknown, "Assertion \"" "vertices->ref == 1" "\" failed", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_vertices.c" , 1340); goto error; } while (0); } while (0); | |||
1341 | ||||
1342 | param_morph = isl_morph_copy(morph); | |||
1343 | param_morph = isl_morph_dom_params(param_morph); | |||
1344 | param_morph = isl_morph_ran_params(param_morph); | |||
1345 | ||||
1346 | for (i = 0; i < vertices->n_vertices; ++i) { | |||
1347 | vertices->v[i].dom = isl_morph_basic_set( | |||
1348 | isl_morph_copy(param_morph), vertices->v[i].dom); | |||
1349 | vertices->v[i].vertex = isl_morph_basic_set( | |||
1350 | isl_morph_copy(morph), vertices->v[i].vertex); | |||
1351 | if (!vertices->v[i].vertex) | |||
1352 | goto error; | |||
1353 | } | |||
1354 | ||||
1355 | for (i = 0; i < vertices->n_chambers; ++i) { | |||
1356 | vertices->c[i].dom = isl_morph_basic_set( | |||
1357 | isl_morph_copy(param_morph), vertices->c[i].dom); | |||
1358 | if (!vertices->c[i].dom) | |||
1359 | goto error; | |||
1360 | } | |||
1361 | ||||
1362 | isl_morph_free(param_morph); | |||
1363 | isl_morph_free(morph); | |||
1364 | return vertices; | |||
1365 | error: | |||
1366 | isl_morph_free(param_morph); | |||
1367 | isl_morph_free(morph); | |||
1368 | isl_vertices_free(vertices); | |||
1369 | return NULL((void*)0); | |||
1370 | } | |||
1371 | ||||
1372 | /* Construct a simplex isl_cell spanned by the vertices with indices in | |||
1373 | * "simplex_ids" and "other_ids" and call "fn" on this isl_cell. | |||
1374 | */ | |||
1375 | static isl_stat call_on_simplex(__isl_keep isl_cell *cell, | |||
1376 | int *simplex_ids, int n_simplex, int *other_ids, int n_other, | |||
1377 | isl_stat (*fn)(__isl_take isl_cell *simplex, void *user), void *user) | |||
1378 | { | |||
1379 | int i; | |||
1380 | isl_ctx *ctx; | |||
1381 | struct isl_cell *simplex; | |||
1382 | ||||
1383 | ctx = isl_cell_get_ctx(cell); | |||
1384 | ||||
1385 | simplex = isl_calloc_type(ctx, struct isl_cell)((struct isl_cell *)isl_calloc_or_die(ctx, 1, sizeof(struct isl_cell ))); | |||
1386 | if (!simplex) | |||
1387 | return isl_stat_error; | |||
1388 | simplex->vertices = isl_vertices_copy(cell->vertices); | |||
1389 | if (!simplex->vertices) | |||
1390 | goto error; | |||
1391 | simplex->dom = isl_basic_set_copy(cell->dom); | |||
1392 | if (!simplex->dom) | |||
1393 | goto error; | |||
1394 | simplex->n_vertices = n_simplex + n_other; | |||
1395 | simplex->ids = isl_alloc_array(ctx, int, simplex->n_vertices)((int *)isl_malloc_or_die(ctx, (simplex->n_vertices)*sizeof (int))); | |||
1396 | if (!simplex->ids) | |||
1397 | goto error; | |||
1398 | ||||
1399 | for (i = 0; i < n_simplex; ++i) | |||
1400 | simplex->ids[i] = simplex_ids[i]; | |||
1401 | for (i = 0; i < n_other; ++i) | |||
1402 | simplex->ids[n_simplex + i] = other_ids[i]; | |||
1403 | ||||
1404 | return fn(simplex, user); | |||
1405 | error: | |||
1406 | isl_cell_free(simplex); | |||
1407 | return isl_stat_error; | |||
1408 | } | |||
1409 | ||||
1410 | /* Check whether the parametric vertex described by "vertex" | |||
1411 | * lies on the facet corresponding to constraint "facet" of "bset". | |||
1412 | * The isl_vec "v" is a temporary vector than can be used by this function. | |||
1413 | * | |||
1414 | * We eliminate the variables from the facet constraint using the | |||
1415 | * equalities defining the vertex and check if the result is identical | |||
1416 | * to zero. | |||
1417 | * | |||
1418 | * It would probably be better to keep track of the constraints defining | |||
1419 | * a vertex during the vertex construction so that we could simply look | |||
1420 | * it up here. | |||
1421 | */ | |||
1422 | static int vertex_on_facet(__isl_keep isl_basic_setisl_basic_map *vertex, | |||
1423 | __isl_keep isl_basic_setisl_basic_map *bset, int facet, __isl_keep isl_vec *v) | |||
1424 | { | |||
1425 | int i; | |||
1426 | isl_int m; | |||
1427 | ||||
1428 | isl_seq_cpy(v->el, bset->ineq[facet], v->size); | |||
1429 | ||||
1430 | isl_int_init(m)isl_sioimath_init((m)); | |||
1431 | for (i = 0; i < vertex->n_eq; ++i) { | |||
1432 | int k = isl_seq_last_non_zero(vertex->eq[i], v->size); | |||
1433 | isl_seq_elim(v->el, vertex->eq[i], k, v->size, &m); | |||
1434 | } | |||
1435 | isl_int_clear(m)isl_sioimath_clear((m)); | |||
1436 | ||||
1437 | return isl_seq_first_non_zero(v->el, v->size) == -1; | |||
1438 | } | |||
1439 | ||||
1440 | /* Triangulate the polytope spanned by the vertices with ids | |||
1441 | * in "simplex_ids" and "other_ids" and call "fn" on each of | |||
1442 | * the resulting simplices. | |||
1443 | * If the input polytope is already a simplex, we simply call "fn". | |||
1444 | * Otherwise, we pick a point from "other_ids" and add it to "simplex_ids". | |||
1445 | * Then we consider each facet of "bset" that does not contain the point | |||
1446 | * we just picked, but does contain some of the other points in "other_ids" | |||
1447 | * and call ourselves recursively on the polytope spanned by the new | |||
1448 | * "simplex_ids" and those points in "other_ids" that lie on the facet. | |||
1449 | */ | |||
1450 | static isl_stat triangulate(__isl_keep isl_cell *cell, __isl_keep isl_vec *v, | |||
1451 | int *simplex_ids, int n_simplex, int *other_ids, int n_other, | |||
1452 | isl_stat (*fn)(__isl_take isl_cell *simplex, void *user), void *user) | |||
1453 | { | |||
1454 | int i, j, k; | |||
1455 | int d, nparam; | |||
1456 | int *ids; | |||
1457 | isl_ctx *ctx; | |||
1458 | isl_basic_setisl_basic_map *vertex; | |||
1459 | isl_basic_setisl_basic_map *bset; | |||
1460 | ||||
1461 | ctx = isl_cell_get_ctx(cell); | |||
1462 | d = isl_basic_set_dim(cell->vertices->bset, isl_dim_set); | |||
1463 | nparam = isl_basic_set_dim(cell->vertices->bset, isl_dim_param); | |||
1464 | ||||
1465 | if (n_simplex + n_other == d + 1) | |||
1466 | return call_on_simplex(cell, simplex_ids, n_simplex, | |||
1467 | other_ids, n_other, fn, user); | |||
1468 | ||||
1469 | simplex_ids[n_simplex] = other_ids[0]; | |||
1470 | vertex = cell->vertices->v[other_ids[0]].vertex; | |||
1471 | bset = cell->vertices->bset; | |||
1472 | ||||
1473 | ids = isl_alloc_array(ctx, int, n_other - 1)((int *)isl_malloc_or_die(ctx, (n_other - 1)*sizeof(int))); | |||
1474 | if (!ids) | |||
1475 | goto error; | |||
1476 | for (i = 0; i < bset->n_ineq; ++i) { | |||
1477 | if (isl_seq_first_non_zero(bset->ineq[i] + 1 + nparam, d) == -1) | |||
1478 | continue; | |||
1479 | if (vertex_on_facet(vertex, bset, i, v)) | |||
1480 | continue; | |||
1481 | ||||
1482 | for (j = 1, k = 0; j < n_other; ++j) { | |||
1483 | isl_basic_setisl_basic_map *ov; | |||
1484 | ov = cell->vertices->v[other_ids[j]].vertex; | |||
1485 | if (vertex_on_facet(ov, bset, i, v)) | |||
1486 | ids[k++] = other_ids[j]; | |||
1487 | } | |||
1488 | if (k == 0) | |||
1489 | continue; | |||
1490 | ||||
1491 | if (triangulate(cell, v, simplex_ids, n_simplex + 1, | |||
1492 | ids, k, fn, user) < 0) | |||
1493 | goto error; | |||
1494 | } | |||
1495 | free(ids); | |||
1496 | ||||
1497 | return isl_stat_ok; | |||
1498 | error: | |||
1499 | free(ids); | |||
1500 | return isl_stat_error; | |||
1501 | } | |||
1502 | ||||
1503 | /* Triangulate the given cell and call "fn" on each of the resulting | |||
1504 | * simplices. | |||
1505 | */ | |||
1506 | isl_stat isl_cell_foreach_simplex(__isl_take isl_cell *cell, | |||
1507 | isl_stat (*fn)(__isl_take isl_cell *simplex, void *user), void *user) | |||
1508 | { | |||
1509 | int d, total; | |||
1510 | isl_stat r; | |||
1511 | isl_ctx *ctx; | |||
1512 | isl_vec *v = NULL((void*)0); | |||
1513 | int *simplex_ids = NULL((void*)0); | |||
1514 | ||||
1515 | if (!cell) | |||
| ||||
1516 | return isl_stat_error; | |||
1517 | ||||
1518 | d = isl_basic_set_dim(cell->vertices->bset, isl_dim_set); | |||
1519 | total = isl_basic_set_total_dim(cell->vertices->bset); | |||
1520 | ||||
1521 | if (cell->n_vertices == d + 1) | |||
1522 | return fn(cell, user); | |||
1523 | ||||
1524 | ctx = isl_cell_get_ctx(cell); | |||
1525 | simplex_ids = isl_alloc_array(ctx, int, d + 1)((int *)isl_malloc_or_die(ctx, (d + 1)*sizeof(int))); | |||
1526 | if (!simplex_ids) | |||
1527 | goto error; | |||
1528 | ||||
1529 | v = isl_vec_alloc(ctx, 1 + total); | |||
1530 | if (!v) | |||
1531 | goto error; | |||
1532 | ||||
1533 | r = triangulate(cell, v, simplex_ids, 0, | |||
1534 | cell->ids, cell->n_vertices, fn, user); | |||
1535 | ||||
1536 | isl_vec_free(v); | |||
1537 | free(simplex_ids); | |||
1538 | ||||
1539 | isl_cell_free(cell); | |||
1540 | ||||
1541 | return r; | |||
1542 | error: | |||
1543 | free(simplex_ids); | |||
1544 | isl_vec_free(v); | |||
1545 | isl_cell_free(cell); | |||
1546 | return isl_stat_error; | |||
1547 | } |