Bug Summary

File:tools/polly/lib/External/isl/isl_vertices.c
Warning:line 1096, column 2
Use of memory after it is freed

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name isl_vertices.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-9/lib/clang/9.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/pet/include -I /build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/ppcg/include -I /build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/ppcg/imath -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/tools/polly/lib/External/ppcg -I /build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl -I /build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/imath -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/tools/polly/lib/External/isl -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/tools/polly/include -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-9~svn362543/tools/polly/include -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/include -I /build/llvm-toolchain-snapshot-9~svn362543/include -U NDEBUG -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-9/lib/clang/9.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=gnu99 -fconst-strings -fdebug-compilation-dir /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/tools/polly/lib/External -fdebug-prefix-map=/build/llvm-toolchain-snapshot-9~svn362543=. -ferror-limit 19 -fmessage-length 0 -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2019-06-05-060531-1271-1 -x c /build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_vertices.c -faddrsig
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
26static __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)
22
Taking false branch
43 return NULL((void*)0);
44
45 if (--vertices->ref > 0)
23
Assuming the condition is false
24
Taking false branch
46 return NULL((void*)0);
47
48 for (i = 0; i < vertices->n_vertices; ++i) {
25
Assuming the condition is false
26
Loop condition is false. Execution continues on line 52
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) {
27
Assuming the condition is false
28
Loop condition is false. Execution continues on line 58
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);
29
Memory is released
62
63 return NULL((void*)0);
64}
65
66struct isl_vertex_list {
67 struct isl_vertex v;
68 struct isl_vertex_list *next;
69};
70
71static 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
85static __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;
109error:
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 */
122static 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;
159error:
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 */
167static __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 */
192static __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;
227error:
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 */
235static 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 */
266static 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 */
326static __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;
485error:
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
495struct isl_chamber_list {
496 struct isl_chamber c;
497 struct isl_chamber_list *next;
498};
499
500static 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 */
515static 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
535static __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;
556error:
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 */
566static 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
600static 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;
655error:
656 free_chamber_list(c);
657 return -1;
658}
659
660struct 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
667static 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
681static 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;
725error:
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 */
733static 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 */
767static 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 */
791static 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 */
854static __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;
962error:
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
974isl_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
979int 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
1020static __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;
1038error:
1039 isl_vertices_free(vertices);
1040 return NULL((void*)0);
1041}
1042
1043void 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
1051isl_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
1061static __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;
1084error:
1085 isl_cell_free(cell);
1086 isl_vertices_free(vertices);
1087 isl_basic_set_free(dom);
1088 return NULL((void*)0);
1089}
1090
1091void isl_cell_free(__isl_take isl_cell *cell)
1092{
1093 if (!cell)
20
Taking false branch
35
Taking false branch
1094 return;
1095
1096 isl_vertices_free(cell->vertices);
21
Calling 'isl_vertices_free'
30
Returning; memory was released via 1st parameter
36
Use of memory after it is freed
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 */
1106static 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;
1154error:
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 */
1163static __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 */
1190isl_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;
1233error:
1234 isl_vec_free(vec);
1235 return isl_stat_error;
1236}
1237
1238isl_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
1266isl_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
1293isl_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
1321isl_ctx *isl_vertices_get_ctx(__isl_keep isl_vertices *vertices)
1322{
1323 return vertices ? vertices->bset->ctx : NULL((void*)0);
1324}
1325
1326int 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;
1365error:
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 */
1375static 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)
13
Assuming 'simplex' is non-null
14
Taking false branch
1387 return isl_stat_error;
1388 simplex->vertices = isl_vertices_copy(cell->vertices);
1389 if (!simplex->vertices)
15
Taking false branch
1390 goto error;
1391 simplex->dom = isl_basic_set_copy(cell->dom);
1392 if (!simplex->dom)
16
Assuming the condition is true
17
Taking true branch
1393 goto error;
18
Control jumps to line 1406
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);
1405error:
1406 isl_cell_free(simplex);
19
Calling 'isl_cell_free'
31
Returning; memory was released
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 */
1422static 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 */
1450static 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)
10
Assuming the condition is true
11
Taking true branch
1466 return call_on_simplex(cell, simplex_ids, n_simplex,
12
Calling 'call_on_simplex'
32
Returning; memory was released
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;
1498error:
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 */
1506isl_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)
1
Assuming 'cell' is non-null
2
Taking false branch
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)
3
Assuming the condition is false
4
Taking false branch
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)
5
Assuming 'simplex_ids' is non-null
6
Taking false branch
1527 goto error;
1528
1529 v = isl_vec_alloc(ctx, 1 + total);
1530 if (!v)
7
Assuming 'v' is non-null
8
Taking false branch
1531 goto error;
1532
1533 r = triangulate(cell, v, simplex_ids, 0,
9
Calling 'triangulate'
33
Returning; memory was released
1534 cell->ids, cell->n_vertices, fn, user);
1535
1536 isl_vec_free(v);
1537 free(simplex_ids);
1538
1539 isl_cell_free(cell);
34
Calling 'isl_cell_free'
1540
1541 return r;
1542error:
1543 free(simplex_ids);
1544 isl_vec_free(v);
1545 isl_cell_free(cell);
1546 return isl_stat_error;
1547}