Bug Summary

File:tools/polly/lib/External/isl/isl_list_templ.c
Warning:line 243, column 3
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_ast_graft.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-config-compatibility-mode=true -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 -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-8/lib/clang/8.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-8~svn348900/build-llvm/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/pet/include -I /build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/ppcg/include -I /build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/ppcg/imath -I /build/llvm-toolchain-snapshot-8~svn348900/build-llvm/tools/polly/lib/External/ppcg -I /build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl -I /build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/imath -I /build/llvm-toolchain-snapshot-8~svn348900/build-llvm/tools/polly/lib/External/isl -I /build/llvm-toolchain-snapshot-8~svn348900/build-llvm/tools/polly/include -I /build/llvm-toolchain-snapshot-8~svn348900/build-llvm/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-8~svn348900/tools/polly/include -I /build/llvm-toolchain-snapshot-8~svn348900/build-llvm/include -I /build/llvm-toolchain-snapshot-8~svn348900/include -U NDEBUG -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-8/lib/clang/8.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-command-line-argument -Wno-unknown-warning-option -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-8~svn348900/build-llvm/tools/polly/lib/External -ferror-limit 19 -fmessage-length 0 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-12-12-042652-12204-1 -x c /build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/isl_ast_graft.c -faddrsig

/build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/isl_ast_graft.c

1/*
2 * Copyright 2012 Ecole Normale Superieure
3 * Copyright 2014 INRIA Rocquencourt
4 *
5 * Use of this software is governed by the MIT license
6 *
7 * Written by Sven Verdoolaege,
8 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
9 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
10 * B.P. 105 - 78153 Le Chesnay, France
11 */
12
13#include <isl/id.h>
14#include <isl/space.h>
15#include <isl_ast_private.h>
16#include <isl_ast_build_expr.h>
17#include <isl_ast_build_private.h>
18#include <isl_ast_graft_private.h>
19
20static __isl_give isl_ast_graft *isl_ast_graft_copy(
21 __isl_keep isl_ast_graft *graft);
22
23#undef BASEast_graft
24#define BASEast_graft ast_graft
25
26#include <isl_list_templ.c>
27
28#undef BASEast_graft
29#define BASEast_graft ast_graft
30#include <print_templ.c>
31
32isl_ctx *isl_ast_graft_get_ctx(__isl_keep isl_ast_graft *graft)
33{
34 if (!graft)
35 return NULL((void*)0);
36 return isl_basic_set_get_ctx(graft->enforced);
37}
38
39__isl_give isl_ast_node *isl_ast_graft_get_node(
40 __isl_keep isl_ast_graft *graft)
41{
42 return graft ? isl_ast_node_copy(graft->node) : NULL((void*)0);
43}
44
45/* Create a graft for "node" with no guards and no enforced conditions.
46 */
47__isl_give isl_ast_graft *isl_ast_graft_alloc(
48 __isl_take isl_ast_node *node, __isl_keep isl_ast_build *build)
49{
50 isl_ctx *ctx;
51 isl_space *space;
52 isl_ast_graft *graft;
53
54 if (!node)
55 return NULL((void*)0);
56
57 ctx = isl_ast_node_get_ctx(node);
58 graft = isl_calloc_type(ctx, isl_ast_graft)((isl_ast_graft *)isl_calloc_or_die(ctx, 1, sizeof(isl_ast_graft
)))
;
59 if (!graft)
60 goto error;
61
62 space = isl_ast_build_get_space(build, 1);
63
64 graft->ref = 1;
65 graft->node = node;
66 graft->guard = isl_set_universe(isl_space_copy(space));
67 graft->enforced = isl_basic_set_universe(space);
68
69 if (!graft->guard || !graft->enforced)
70 return isl_ast_graft_free(graft);
71
72 return graft;
73error:
74 isl_ast_node_free(node);
75 return NULL((void*)0);
76}
77
78/* Create a graft with no guards and no enforced conditions
79 * encapsulating a call to the domain element specified by "executed".
80 * "executed" is assumed to be single-valued.
81 */
82__isl_give isl_ast_graft *isl_ast_graft_alloc_domain(
83 __isl_take isl_map *executed, __isl_keep isl_ast_build *build)
84{
85 isl_ast_node *node;
86
87 node = isl_ast_build_call_from_executed(build, executed);
88
89 return isl_ast_graft_alloc(node, build);
90}
91
92static __isl_give isl_ast_graft *isl_ast_graft_copy(
93 __isl_keep isl_ast_graft *graft)
94{
95 if (!graft)
31
Assuming 'graft' is non-null
32
Taking false branch
96 return NULL((void*)0);
97
98 graft->ref++;
99 return graft;
100}
101
102/* Do all the grafts in "list" have the same guard and is this guard
103 * independent of the current depth?
104 */
105static int equal_independent_guards(__isl_keep isl_ast_graft_list *list,
106 __isl_keep isl_ast_build *build)
107{
108 int i, n;
109 int depth;
110 isl_ast_graft *graft_0;
111 int equal = 1;
112 int skip;
113
114 graft_0 = isl_ast_graft_list_get_ast_graft(list, 0);
115 if (!graft_0)
116 return -1;
117
118 depth = isl_ast_build_get_depth(build);
119 if (isl_set_dim(graft_0->guard, isl_dim_set) <= depth)
120 skip = 0;
121 else
122 skip = isl_set_involves_dims(graft_0->guard,
123 isl_dim_set, depth, 1);
124 if (skip < 0 || skip) {
125 isl_ast_graft_free(graft_0);
126 return skip < 0 ? -1 : 0;
127 }
128
129 n = isl_ast_graft_list_n_ast_graft(list);
130 for (i = 1; i < n; ++i) {
131 isl_ast_graft *graft;
132 graft = isl_ast_graft_list_get_ast_graft(list, i);
133 if (!graft)
134 equal = -1;
135 else
136 equal = isl_set_is_equal(graft_0->guard, graft->guard);
137 isl_ast_graft_free(graft);
138 if (equal < 0 || !equal)
139 break;
140 }
141
142 isl_ast_graft_free(graft_0);
143
144 return equal;
145}
146
147/* Hoist "guard" out of the current level (given by "build").
148 *
149 * In particular, eliminate the dimension corresponding to the current depth.
150 */
151static __isl_give isl_set *hoist_guard(__isl_take isl_set *guard,
152 __isl_keep isl_ast_build *build)
153{
154 int depth;
155
156 depth = isl_ast_build_get_depth(build);
157 if (depth < isl_set_dim(guard, isl_dim_set)) {
158 guard = isl_set_remove_divs_involving_dims(guard,
159 isl_dim_set, depth, 1);
160 guard = isl_set_eliminate(guard, isl_dim_set, depth, 1);
161 guard = isl_set_compute_divs(guard);
162 }
163
164 return guard;
165}
166
167/* Extract a common guard from the grafts in "list" that can be hoisted
168 * out of the current level. If no such guard can be found, then return
169 * a universal set.
170 *
171 * If all the grafts in the list have the same guard and if this guard
172 * is independent of the current level, then it can be hoisted out.
173 * If there is only one graft in the list and if its guard
174 * depends on the current level, then we eliminate this level and
175 * return the result.
176 *
177 * Otherwise, we return the unshifted simple hull of the guards.
178 * In order to be able to hoist as many constraints as possible,
179 * but at the same time avoid hoisting constraints that did not
180 * appear in the guards in the first place, we intersect the guards
181 * with all the information that is available (i.e., the domain
182 * from the build and the enforced constraints of the graft) and
183 * compute the unshifted hull of the result using only constraints
184 * from the original guards.
185 * In particular, intersecting the guards with other known information
186 * allows us to hoist guards that are only explicit is some of
187 * the grafts and implicit in the others.
188 *
189 * The special case for equal guards is needed in case those guards
190 * are non-convex. Taking the simple hull would remove information
191 * and would not allow for these guards to be hoisted completely.
192 */
193__isl_give isl_set *isl_ast_graft_list_extract_hoistable_guard(
194 __isl_keep isl_ast_graft_list *list, __isl_keep isl_ast_build *build)
195{
196 int i, n;
197 int equal;
198 isl_ctx *ctx;
199 isl_set *guard;
200 isl_set_list *set_list;
201 isl_basic_set *hull;
202
203 if (!list || !build)
204 return NULL((void*)0);
205
206 n = isl_ast_graft_list_n_ast_graft(list);
207 if (n == 0)
208 return isl_set_universe(isl_ast_build_get_space(build, 1));
209
210 equal = equal_independent_guards(list, build);
211 if (equal < 0)
212 return NULL((void*)0);
213
214 if (equal || n == 1) {
215 isl_ast_graft *graft_0;
216
217 graft_0 = isl_ast_graft_list_get_ast_graft(list, 0);
218 if (!graft_0)
219 return NULL((void*)0);
220 guard = isl_set_copy(graft_0->guard);
221 if (!equal)
222 guard = hoist_guard(guard, build);
223 isl_ast_graft_free(graft_0);
224 return guard;
225 }
226
227 ctx = isl_ast_build_get_ctx(build);
228 set_list = isl_set_list_alloc(ctx, n);
229 guard = isl_set_empty(isl_ast_build_get_space(build, 1));
230 for (i = 0; i < n; ++i) {
231 isl_ast_graft *graft;
232 isl_basic_set *enforced;
233 isl_set *guard_i;
234
235 graft = isl_ast_graft_list_get_ast_graft(list, i);
236 enforced = isl_ast_graft_get_enforced(graft);
237 guard_i = isl_set_copy(graft->guard);
238 isl_ast_graft_free(graft);
239 set_list = isl_set_list_add(set_list, isl_set_copy(guard_i));
240 guard_i = isl_set_intersect(guard_i,
241 isl_set_from_basic_set(enforced));
242 guard_i = isl_set_intersect(guard_i,
243 isl_ast_build_get_domain(build));
244 guard = isl_set_union(guard, guard_i);
245 }
246 hull = isl_set_unshifted_simple_hull_from_set_list(guard, set_list);
247 guard = isl_set_from_basic_set(hull);
248 return hoist_guard(guard, build);
249}
250
251/* Internal data structure used inside insert_if.
252 *
253 * list is the list of guarded nodes created by each call to insert_if.
254 * node is the original node that is guarded by insert_if.
255 * build is the build in which the AST is constructed.
256 */
257struct isl_insert_if_data {
258 isl_ast_node_list *list;
259 isl_ast_node *node;
260 isl_ast_build *build;
261};
262
263static isl_stat insert_if(__isl_take isl_basic_set *bset, void *user);
264
265/* Insert an if node around "node" testing the condition encoded
266 * in guard "guard".
267 *
268 * If the user does not want any disjunctions in the if conditions
269 * and if "guard" does involve a disjunction, then we make the different
270 * disjuncts disjoint and insert an if node corresponding to each disjunct
271 * around a copy of "node". The result is then a block node containing
272 * this sequence of guarded copies of "node".
273 */
274static __isl_give isl_ast_node *ast_node_insert_if(
275 __isl_take isl_ast_node *node, __isl_take isl_set *guard,
276 __isl_keep isl_ast_build *build)
277{
278 struct isl_insert_if_data data;
279 isl_ctx *ctx;
280
281 ctx = isl_ast_build_get_ctx(build);
282 if (isl_options_get_ast_build_allow_or(ctx) ||
283 isl_set_n_basic_set(guard) <= 1) {
284 isl_ast_node *if_node;
285 isl_ast_expr *expr;
286
287 expr = isl_ast_build_expr_from_set_internal(build, guard);
288
289 if_node = isl_ast_node_alloc_if(expr);
290 return isl_ast_node_if_set_then(if_node, node);
291 }
292
293 guard = isl_set_make_disjoint(guard);
294
295 data.list = isl_ast_node_list_alloc(ctx, 0);
296 data.node = node;
297 data.build = build;
298 if (isl_set_foreach_basic_set(guard, &insert_if, &data) < 0)
299 data.list = isl_ast_node_list_free(data.list);
300
301 isl_set_free(guard);
302 isl_ast_node_free(data.node);
303 return isl_ast_node_alloc_block(data.list);
304}
305
306/* Insert an if node around a copy of "data->node" testing the condition
307 * encoded in guard "bset" and add the result to data->list.
308 */
309static isl_stat insert_if(__isl_take isl_basic_set *bset, void *user)
310{
311 struct isl_insert_if_data *data = user;
312 isl_ast_node *node;
313 isl_set *set;
314
315 set = isl_set_from_basic_set(bset);
316 node = isl_ast_node_copy(data->node);
317 node = ast_node_insert_if(node, set, data->build);
318 data->list = isl_ast_node_list_add(data->list, node);
319
320 return isl_stat_ok;
321}
322
323/* Insert an if node around graft->node testing the condition encoded
324 * in guard "guard", assuming guard involves any conditions.
325 */
326static __isl_give isl_ast_graft *insert_if_node(
327 __isl_take isl_ast_graft *graft, __isl_take isl_set *guard,
328 __isl_keep isl_ast_build *build)
329{
330 int univ;
331
332 if (!graft)
333 goto error;
334
335 univ = isl_set_plain_is_universe(guard);
336 if (univ < 0)
337 goto error;
338 if (univ) {
339 isl_set_free(guard);
340 return graft;
341 }
342
343 build = isl_ast_build_copy(build);
344 graft->node = ast_node_insert_if(graft->node, guard, build);
345 isl_ast_build_free(build);
346
347 if (!graft->node)
348 return isl_ast_graft_free(graft);
349
350 return graft;
351error:
352 isl_set_free(guard);
353 return isl_ast_graft_free(graft);
354}
355
356/* Insert an if node around graft->node testing the condition encoded
357 * in graft->guard, assuming graft->guard involves any conditions.
358 */
359static __isl_give isl_ast_graft *insert_pending_guard_node(
360 __isl_take isl_ast_graft *graft, __isl_keep isl_ast_build *build)
361{
362 if (!graft)
363 return NULL((void*)0);
364
365 return insert_if_node(graft, isl_set_copy(graft->guard), build);
366}
367
368/* Replace graft->enforced by "enforced".
369 */
370__isl_give isl_ast_graft *isl_ast_graft_set_enforced(
371 __isl_take isl_ast_graft *graft, __isl_take isl_basic_set *enforced)
372{
373 if (!graft || !enforced)
374 goto error;
375
376 isl_basic_set_free(graft->enforced);
377 graft->enforced = enforced;
378
379 return graft;
380error:
381 isl_basic_set_free(enforced);
382 return isl_ast_graft_free(graft);
383}
384
385/* Update "enforced" such that it only involves constraints that are
386 * also enforced by "graft".
387 */
388static __isl_give isl_basic_set *update_enforced(
389 __isl_take isl_basic_set *enforced, __isl_keep isl_ast_graft *graft,
390 int depth)
391{
392 isl_basic_set *enforced_g;
393
394 enforced_g = isl_ast_graft_get_enforced(graft);
395 if (depth < isl_basic_set_dim(enforced_g, isl_dim_set))
396 enforced_g = isl_basic_set_eliminate(enforced_g,
397 isl_dim_set, depth, 1);
398 enforced_g = isl_basic_set_remove_unknown_divs(enforced_g);
399 enforced_g = isl_basic_set_align_params(enforced_g,
400 isl_basic_set_get_space(enforced));
401 enforced = isl_basic_set_align_params(enforced,
402 isl_basic_set_get_space(enforced_g));
403 enforced = isl_set_simple_hull(isl_basic_set_union(enforced,
404 enforced_g));
405
406 return enforced;
407}
408
409/* Extend the node at *body with node.
410 *
411 * If body points to the else branch, then *body may still be NULL.
412 * If so, we simply attach node to this else branch.
413 * Otherwise, we attach a list containing the statements already
414 * attached at *body followed by node.
415 */
416static void extend_body(__isl_keep isl_ast_node **body,
417 __isl_take isl_ast_node *node)
418{
419 isl_ast_node_list *list;
420
421 if (!*body) {
422 *body = node;
423 return;
424 }
425
426 if ((*body)->type == isl_ast_node_block) {
427 list = isl_ast_node_block_get_children(*body);
428 isl_ast_node_free(*body);
429 } else
430 list = isl_ast_node_list_from_ast_node(*body);
431 list = isl_ast_node_list_add(list, node);
432 *body = isl_ast_node_alloc_block(list);
433}
434
435/* Merge "graft" into the last graft of "list".
436 * body points to the then or else branch of an if node in that last graft.
437 *
438 * We attach graft->node to this branch and update the enforced
439 * set of the last graft of "list" to take into account the enforced
440 * set of "graft".
441 */
442static __isl_give isl_ast_graft_list *graft_extend_body(
443 __isl_take isl_ast_graft_list *list,
444 __isl_keep isl_ast_node **body, __isl_take isl_ast_graft *graft,
445 __isl_keep isl_ast_build *build)
446{
447 int n;
448 int depth;
449 isl_ast_graft *last;
450 isl_space *space;
451 isl_basic_set *enforced;
452
453 if (!list || !graft)
454 goto error;
455 extend_body(body, isl_ast_node_copy(graft->node));
456 if (!*body)
457 goto error;
458
459 n = isl_ast_graft_list_n_ast_graft(list);
460 last = isl_ast_graft_list_get_ast_graft(list, n - 1);
461
462 depth = isl_ast_build_get_depth(build);
463 space = isl_ast_build_get_space(build, 1);
464 enforced = isl_basic_set_empty(space);
465 enforced = update_enforced(enforced, last, depth);
466 enforced = update_enforced(enforced, graft, depth);
467 last = isl_ast_graft_set_enforced(last, enforced);
468
469 list = isl_ast_graft_list_set_ast_graft(list, n - 1, last);
470 isl_ast_graft_free(graft);
471 return list;
472error:
473 isl_ast_graft_free(graft);
474 return isl_ast_graft_list_free(list);
475}
476
477/* Merge "graft" into the last graft of "list", attaching graft->node
478 * to the then branch of "last_if".
479 */
480static __isl_give isl_ast_graft_list *extend_then(
481 __isl_take isl_ast_graft_list *list,
482 __isl_keep isl_ast_node *last_if, __isl_take isl_ast_graft *graft,
483 __isl_keep isl_ast_build *build)
484{
485 return graft_extend_body(list, &last_if->u.i.then, graft, build);
486}
487
488/* Merge "graft" into the last graft of "list", attaching graft->node
489 * to the else branch of "last_if".
490 */
491static __isl_give isl_ast_graft_list *extend_else(
492 __isl_take isl_ast_graft_list *list,
493 __isl_keep isl_ast_node *last_if, __isl_take isl_ast_graft *graft,
494 __isl_keep isl_ast_build *build)
495{
496 return graft_extend_body(list, &last_if->u.i.else_node, graft, build);
497}
498
499/* This data structure keeps track of an if node.
500 *
501 * "node" is the actual if-node
502 * "guard" is the original, non-simplified guard of the node
503 * "complement" is the complement of "guard" in the context of outer if nodes
504 */
505struct isl_if_node {
506 isl_ast_node *node;
507 isl_set *guard;
508 isl_set *complement;
509};
510
511/* Given a list of "n" if nodes, clear those starting at "first"
512 * and return "first" (i.e., the updated size of the array).
513 */
514static int clear_if_nodes(struct isl_if_node *if_node, int first, int n)
515{
516 int i;
517
518 for (i = first; i < n; ++i) {
519 isl_set_free(if_node[i].guard);
520 isl_set_free(if_node[i].complement);
521 }
522
523 return first;
524}
525
526/* For each graft in "list",
527 * insert an if node around graft->node testing the condition encoded
528 * in graft->guard, assuming graft->guard involves any conditions.
529 *
530 * We keep track of a list of generated if nodes that can be extended
531 * without changing the order of the elements in "list".
532 * If the guard of a graft is a subset of either the guard or its complement
533 * of one of those if nodes, then the node
534 * of the new graft is inserted into the then or else branch of the last graft
535 * and the current graft is discarded.
536 * The guard of the node is then simplified based on the conditions
537 * enforced at that then or else branch.
538 * Otherwise, the current graft is appended to the list.
539 *
540 * We only construct else branches if allowed by the user.
541 */
542static __isl_give isl_ast_graft_list *insert_pending_guard_nodes(
543 __isl_take isl_ast_graft_list *list,
544 __isl_keep isl_ast_build *build)
545{
546 int i, j, n, n_if;
547 int allow_else;
548 isl_ctx *ctx;
549 isl_ast_graft_list *res;
550 struct isl_if_node *if_node = NULL((void*)0);
551
552 if (!build || !list)
553 return isl_ast_graft_list_free(list);
554
555 ctx = isl_ast_build_get_ctx(build);
556 n = isl_ast_graft_list_n_ast_graft(list);
557
558 allow_else = isl_options_get_ast_build_allow_else(ctx);
559
560 n_if = 0;
561 if (n > 1) {
562 if_node = isl_alloc_array(ctx, struct isl_if_node, n - 1)((struct isl_if_node *)isl_malloc_or_die(ctx, (n - 1)*sizeof(
struct isl_if_node)))
;
563 if (!if_node)
564 return isl_ast_graft_list_free(list);
565 }
566
567 res = isl_ast_graft_list_alloc(ctx, n);
568
569 for (i = 0; i < n; ++i) {
570 isl_set *guard;
571 isl_ast_graft *graft;
572 int subset, found_then, found_else;
573 isl_ast_node *node;
574
575 graft = isl_ast_graft_list_get_ast_graft(list, i);
576 if (!graft)
577 break;
578 subset = 0;
579 found_then = found_else = -1;
580 if (n_if > 0) {
581 isl_set *test;
582 test = isl_set_copy(graft->guard);
583 test = isl_set_intersect(test,
584 isl_set_copy(build->domain));
585 for (j = n_if - 1; j >= 0; --j) {
586 subset = isl_set_is_subset(test,
587 if_node[j].guard);
588 if (subset < 0 || subset) {
589 found_then = j;
590 break;
591 }
592 if (!allow_else)
593 continue;
594 subset = isl_set_is_subset(test,
595 if_node[j].complement);
596 if (subset < 0 || subset) {
597 found_else = j;
598 break;
599 }
600 }
601 n_if = clear_if_nodes(if_node, j + 1, n_if);
602 isl_set_free(test);
603 }
604 if (subset < 0) {
605 graft = isl_ast_graft_free(graft);
606 break;
607 }
608
609 guard = isl_set_copy(graft->guard);
610 if (found_then >= 0)
611 graft->guard = isl_set_gist(graft->guard,
612 isl_set_copy(if_node[found_then].guard));
613 else if (found_else >= 0)
614 graft->guard = isl_set_gist(graft->guard,
615 isl_set_copy(if_node[found_else].complement));
616
617 node = graft->node;
618 if (!graft->guard)
619 graft = isl_ast_graft_free(graft);
620 graft = insert_pending_guard_node(graft, build);
621 if (graft && graft->node != node && i != n - 1) {
622 isl_set *set;
623 if_node[n_if].node = graft->node;
624 if_node[n_if].guard = guard;
625 if (found_then >= 0)
626 set = if_node[found_then].guard;
627 else if (found_else >= 0)
628 set = if_node[found_else].complement;
629 else
630 set = build->domain;
631 set = isl_set_copy(set);
632 set = isl_set_subtract(set, isl_set_copy(guard));
633 if_node[n_if].complement = set;
634 n_if++;
635 } else
636 isl_set_free(guard);
637 if (!graft)
638 break;
639
640 if (found_then >= 0)
641 res = extend_then(res, if_node[found_then].node,
642 graft, build);
643 else if (found_else >= 0)
644 res = extend_else(res, if_node[found_else].node,
645 graft, build);
646 else
647 res = isl_ast_graft_list_add(res, graft);
648 }
649 if (i < n)
650 res = isl_ast_graft_list_free(res);
651
652 isl_ast_graft_list_free(list);
653 clear_if_nodes(if_node, 0, n_if);
654 free(if_node);
655 return res;
656}
657
658/* For each graft in "list",
659 * insert an if node around graft->node testing the condition encoded
660 * in graft->guard, assuming graft->guard involves any conditions.
661 * Subsequently remove the guards from the grafts.
662 */
663__isl_give isl_ast_graft_list *isl_ast_graft_list_insert_pending_guard_nodes(
664 __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build)
665{
666 int i, n;
667 isl_set *universe;
668
669 list = insert_pending_guard_nodes(list, build);
670 if (!list)
671 return NULL((void*)0);
672
673 universe = isl_set_universe(isl_ast_build_get_space(build, 1));
674 n = isl_ast_graft_list_n_ast_graft(list);
675 for (i = 0; i < n; ++i) {
676 isl_ast_graft *graft;
677
678 graft = isl_ast_graft_list_get_ast_graft(list, i);
679 if (!graft)
680 break;
681 isl_set_free(graft->guard);
682 graft->guard = isl_set_copy(universe);
683 if (!graft->guard)
684 graft = isl_ast_graft_free(graft);
685 list = isl_ast_graft_list_set_ast_graft(list, i, graft);
686 }
687 isl_set_free(universe);
688 if (i < n)
689 return isl_ast_graft_list_free(list);
690
691 return list;
692}
693
694/* Collect the nodes contained in the grafts in "list" in a node list.
695 */
696static __isl_give isl_ast_node_list *extract_node_list(
697 __isl_keep isl_ast_graft_list *list)
698{
699 int i, n;
700 isl_ctx *ctx;
701 isl_ast_node_list *node_list;
702
703 if (!list)
704 return NULL((void*)0);
705 ctx = isl_ast_graft_list_get_ctx(list);
706 n = isl_ast_graft_list_n_ast_graft(list);
707 node_list = isl_ast_node_list_alloc(ctx, n);
708 for (i = 0; i < n; ++i) {
709 isl_ast_node *node;
710 isl_ast_graft *graft;
711
712 graft = isl_ast_graft_list_get_ast_graft(list, i);
713 node = isl_ast_graft_get_node(graft);
714 node_list = isl_ast_node_list_add(node_list, node);
715 isl_ast_graft_free(graft);
716 }
717
718 return node_list;
719}
720
721/* Look for shared enforced constraints by all the elements in "list"
722 * on outer loops (with respect to the current depth) and return the result.
723 *
724 * If there are no elements in "list", then return the empty set.
725 */
726__isl_give isl_basic_set *isl_ast_graft_list_extract_shared_enforced(
727 __isl_keep isl_ast_graft_list *list,
728 __isl_keep isl_ast_build *build)
729{
730 int i, n;
731 int depth;
732 isl_space *space;
733 isl_basic_set *enforced;
734
735 if (!list)
736 return NULL((void*)0);
737
738 space = isl_ast_build_get_space(build, 1);
739 enforced = isl_basic_set_empty(space);
740
741 depth = isl_ast_build_get_depth(build);
742 n = isl_ast_graft_list_n_ast_graft(list);
743 for (i = 0; i < n; ++i) {
744 isl_ast_graft *graft;
745
746 graft = isl_ast_graft_list_get_ast_graft(list, i);
747 enforced = update_enforced(enforced, graft, depth);
748 isl_ast_graft_free(graft);
749 }
750
751 return enforced;
752}
753
754/* Record "guard" in "graft" so that it will be enforced somewhere
755 * up the tree. If the graft already has a guard, then it may be partially
756 * redundant in combination with the new guard and in the context
757 * the generated constraints of "build". In fact, the new guard
758 * may in itself have some redundant constraints.
759 * We therefore (re)compute the gist of the intersection
760 * and coalesce the result.
761 */
762static __isl_give isl_ast_graft *store_guard(__isl_take isl_ast_graft *graft,
763 __isl_take isl_set *guard, __isl_keep isl_ast_build *build)
764{
765 int is_universe;
766
767 if (!graft)
768 goto error;
769
770 is_universe = isl_set_plain_is_universe(guard);
771 if (is_universe < 0)
772 goto error;
773 if (is_universe) {
774 isl_set_free(guard);
775 return graft;
776 }
777
778 graft->guard = isl_set_intersect(graft->guard, guard);
779 graft->guard = isl_set_gist(graft->guard,
780 isl_ast_build_get_generated(build));
781 graft->guard = isl_set_coalesce(graft->guard);
782 if (!graft->guard)
783 return isl_ast_graft_free(graft);
784
785 return graft;
786error:
787 isl_set_free(guard);
788 return isl_ast_graft_free(graft);
789}
790
791/* For each graft in "list", replace its guard with the gist with
792 * respect to "context".
793 */
794static __isl_give isl_ast_graft_list *gist_guards(
795 __isl_take isl_ast_graft_list *list, __isl_keep isl_set *context)
796{
797 int i, n;
798
799 if (!list)
25
Taking false branch
800 return NULL((void*)0);
801
802 n = isl_ast_graft_list_n_ast_graft(list);
803 for (i = 0; i < n; ++i) {
26
Assuming 'i' is < 'n'
27
Loop condition is true. Entering loop body
804 isl_ast_graft *graft;
805
806 graft = isl_ast_graft_list_get_ast_graft(list, i);
28
Calling 'isl_ast_graft_list_get_ast_graft'
35
Returning from 'isl_ast_graft_list_get_ast_graft'
807 if (!graft)
36
Taking false branch
808 break;
809 graft->guard = isl_set_gist(graft->guard,
810 isl_set_copy(context));
811 if (!graft->guard)
37
Assuming the condition is true
38
Taking true branch
812 graft = isl_ast_graft_free(graft);
39
Calling 'isl_ast_graft_free'
44
Returning; memory was released via 1st parameter
813 list = isl_ast_graft_list_set_ast_graft(list, i, graft);
45
Calling 'isl_ast_graft_list_set_ast_graft'
814 }
815 if (i < n)
816 return isl_ast_graft_list_free(list);
817
818 return list;
819}
820
821/* For each graft in "list", replace its guard with the gist with
822 * respect to "context".
823 */
824__isl_give isl_ast_graft_list *isl_ast_graft_list_gist_guards(
825 __isl_take isl_ast_graft_list *list, __isl_take isl_set *context)
826{
827 list = gist_guards(list, context);
828 isl_set_free(context);
829
830 return list;
831}
832
833/* Allocate a graft in "build" based on the list of grafts in "sub_build".
834 * "guard" and "enforced" are the guard and enforced constraints
835 * of the allocated graft. The guard is used to simplify the guards
836 * of the elements in "list".
837 *
838 * The node is initialized to either a block containing the nodes of "children"
839 * or, if there is only a single child, the node of that child.
840 * If the current level requires a for node, it should be inserted by
841 * a subsequent call to isl_ast_graft_insert_for.
842 */
843__isl_give isl_ast_graft *isl_ast_graft_alloc_from_children(
844 __isl_take isl_ast_graft_list *list, __isl_take isl_set *guard,
845 __isl_take isl_basic_set *enforced, __isl_keep isl_ast_build *build,
846 __isl_keep isl_ast_build *sub_build)
847{
848 isl_ast_build *guard_build;
849 isl_ast_node *node;
850 isl_ast_node_list *node_list;
851 isl_ast_graft *graft;
852
853 guard_build = isl_ast_build_copy(sub_build);
854 guard_build = isl_ast_build_replace_pending_by_guard(guard_build,
855 isl_set_copy(guard));
856 list = gist_guards(list, guard);
24
Calling 'gist_guards'
857 list = insert_pending_guard_nodes(list, guard_build);
858 isl_ast_build_free(guard_build);
859
860 node_list = extract_node_list(list);
861 node = isl_ast_node_from_ast_node_list(node_list);
862 isl_ast_graft_list_free(list);
863
864 graft = isl_ast_graft_alloc(node, build);
865 graft = store_guard(graft, guard, build);
866 graft = isl_ast_graft_enforce(graft, enforced);
867
868 return graft;
869}
870
871/* Combine the grafts in the list into a single graft.
872 *
873 * The guard is initialized to the shared guard of the list elements (if any),
874 * provided it does not depend on the current dimension.
875 * The guards in the elements are then simplified with respect to the
876 * hoisted guard and materialized as if nodes around the contained AST nodes
877 * in the context of "sub_build".
878 *
879 * The enforced set is initialized to the simple hull of the enforced sets
880 * of the elements, provided the ast_build_exploit_nested_bounds option is set
881 * or the new graft will be used at the same level.
882 *
883 * The node is initialized to either a block containing the nodes of "list"
884 * or, if there is only a single element, the node of that element.
885 */
886static __isl_give isl_ast_graft *ast_graft_list_fuse(
887 __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build)
888{
889 isl_ast_graft *graft;
890 isl_basic_set *enforced;
891 isl_set *guard;
892
893 if (!list)
22
Taking false branch
894 return NULL((void*)0);
895
896 enforced = isl_ast_graft_list_extract_shared_enforced(list, build);
897 guard = isl_ast_graft_list_extract_hoistable_guard(list, build);
898 graft = isl_ast_graft_alloc_from_children(list, guard, enforced,
23
Calling 'isl_ast_graft_alloc_from_children'
899 build, build);
900
901 return graft;
902}
903
904/* Combine the grafts in the list into a single graft.
905 * Return a list containing this single graft.
906 * If the original list is empty, then return an empty list.
907 */
908__isl_give isl_ast_graft_list *isl_ast_graft_list_fuse(
909 __isl_take isl_ast_graft_list *list,
910 __isl_keep isl_ast_build *build)
911{
912 isl_ast_graft *graft;
913
914 if (!list)
915 return NULL((void*)0);
916 if (isl_ast_graft_list_n_ast_graft(list) <= 1)
917 return list;
918 graft = ast_graft_list_fuse(list, build);
919 return isl_ast_graft_list_from_ast_graft(graft);
920}
921
922/* Combine the two grafts into a single graft.
923 * Return a list containing this single graft.
924 */
925static __isl_give isl_ast_graft *isl_ast_graft_fuse(
926 __isl_take isl_ast_graft *graft1, __isl_take isl_ast_graft *graft2,
927 __isl_keep isl_ast_build *build)
928{
929 isl_ctx *ctx;
930 isl_ast_graft_list *list;
931
932 ctx = isl_ast_build_get_ctx(build);
933
934 list = isl_ast_graft_list_alloc(ctx, 2);
935 list = isl_ast_graft_list_add(list, graft1);
936 list = isl_ast_graft_list_add(list, graft2);
937
938 return ast_graft_list_fuse(list, build);
21
Calling 'ast_graft_list_fuse'
939}
940
941/* Insert a for node enclosing the current graft->node.
942 */
943__isl_give isl_ast_graft *isl_ast_graft_insert_for(
944 __isl_take isl_ast_graft *graft, __isl_take isl_ast_node *node)
945{
946 if (!graft)
947 goto error;
948
949 graft->node = isl_ast_node_for_set_body(node, graft->node);
950 if (!graft->node)
951 return isl_ast_graft_free(graft);
952
953 return graft;
954error:
955 isl_ast_node_free(node);
956 isl_ast_graft_free(graft);
957 return NULL((void*)0);
958}
959
960/* Insert a mark governing the current graft->node.
961 */
962__isl_give isl_ast_graft *isl_ast_graft_insert_mark(
963 __isl_take isl_ast_graft *graft, __isl_take isl_id *mark)
964{
965 if (!graft)
966 goto error;
967
968 graft->node = isl_ast_node_alloc_mark(mark, graft->node);
969 if (!graft->node)
970 return isl_ast_graft_free(graft);
971
972 return graft;
973error:
974 isl_id_free(mark);
975 isl_ast_graft_free(graft);
976 return NULL((void*)0);
977}
978
979/* Represent the graft list as an AST node.
980 * This operation drops the information about guards in the grafts, so
981 * if there are any pending guards, then they are materialized as if nodes.
982 */
983__isl_give isl_ast_node *isl_ast_node_from_graft_list(
984 __isl_take isl_ast_graft_list *list,
985 __isl_keep isl_ast_build *build)
986{
987 isl_ast_node_list *node_list;
988
989 list = insert_pending_guard_nodes(list, build);
990 node_list = extract_node_list(list);
991 isl_ast_graft_list_free(list);
992
993 return isl_ast_node_from_ast_node_list(node_list);
994}
995
996__isl_null isl_ast_graft *isl_ast_graft_free(__isl_take isl_ast_graft *graft)
997{
998 if (!graft)
40
Taking false branch
999 return NULL((void*)0);
1000
1001 if (--graft->ref > 0)
41
Assuming the condition is false
42
Taking false branch
1002 return NULL((void*)0);
1003
1004 isl_ast_node_free(graft->node);
1005 isl_set_free(graft->guard);
1006 isl_basic_set_free(graft->enforced);
1007 free(graft);
43
Memory is released
1008
1009 return NULL((void*)0);
1010}
1011
1012/* Record that the grafted tree enforces
1013 * "enforced" by intersecting graft->enforced with "enforced".
1014 */
1015__isl_give isl_ast_graft *isl_ast_graft_enforce(
1016 __isl_take isl_ast_graft *graft, __isl_take isl_basic_set *enforced)
1017{
1018 if (!graft || !enforced)
1019 goto error;
1020
1021 enforced = isl_basic_set_align_params(enforced,
1022 isl_basic_set_get_space(graft->enforced));
1023 graft->enforced = isl_basic_set_align_params(graft->enforced,
1024 isl_basic_set_get_space(enforced));
1025 graft->enforced = isl_basic_set_intersect(graft->enforced, enforced);
1026 if (!graft->enforced)
1027 return isl_ast_graft_free(graft);
1028
1029 return graft;
1030error:
1031 isl_basic_set_free(enforced);
1032 return isl_ast_graft_free(graft);
1033}
1034
1035__isl_give isl_basic_set *isl_ast_graft_get_enforced(
1036 __isl_keep isl_ast_graft *graft)
1037{
1038 return graft ? isl_basic_set_copy(graft->enforced) : NULL((void*)0);
1039}
1040
1041__isl_give isl_set *isl_ast_graft_get_guard(__isl_keep isl_ast_graft *graft)
1042{
1043 return graft ? isl_set_copy(graft->guard) : NULL((void*)0);
1044}
1045
1046/* Record that "guard" needs to be inserted in "graft".
1047 */
1048__isl_give isl_ast_graft *isl_ast_graft_add_guard(
1049 __isl_take isl_ast_graft *graft,
1050 __isl_take isl_set *guard, __isl_keep isl_ast_build *build)
1051{
1052 return store_guard(graft, guard, build);
1053}
1054
1055/* Reformulate the "graft", which was generated in the context
1056 * of an inner code generation, in terms of the outer code generation
1057 * AST build.
1058 *
1059 * If "product" is set, then the domain of the inner code generation build is
1060 *
1061 * [O -> S]
1062 *
1063 * with O the domain of the outer code generation build.
1064 * We essentially need to project out S.
1065 *
1066 * If "product" is not set, then we need to project the domains onto
1067 * their parameter spaces.
1068 */
1069__isl_give isl_ast_graft *isl_ast_graft_unembed(__isl_take isl_ast_graft *graft,
1070 int product)
1071{
1072 isl_basic_set *enforced;
1073
1074 if (!graft)
1075 return NULL((void*)0);
1076
1077 if (product) {
1078 enforced = graft->enforced;
1079 enforced = isl_basic_map_domain(isl_basic_set_unwrap(enforced));
1080 graft->enforced = enforced;
1081 graft->guard = isl_map_domain(isl_set_unwrap(graft->guard));
1082 } else {
1083 graft->enforced = isl_basic_set_params(graft->enforced);
1084 graft->guard = isl_set_params(graft->guard);
1085 }
1086 graft->guard = isl_set_compute_divs(graft->guard);
1087
1088 if (!graft->enforced || !graft->guard)
1089 return isl_ast_graft_free(graft);
1090
1091 return graft;
1092}
1093
1094/* Reformulate the grafts in "list", which were generated in the context
1095 * of an inner code generation, in terms of the outer code generation
1096 * AST build.
1097 */
1098__isl_give isl_ast_graft_list *isl_ast_graft_list_unembed(
1099 __isl_take isl_ast_graft_list *list, int product)
1100{
1101 int i, n;
1102
1103 n = isl_ast_graft_list_n_ast_graft(list);
1104 for (i = 0; i < n; ++i) {
1105 isl_ast_graft *graft;
1106
1107 graft = isl_ast_graft_list_get_ast_graft(list, i);
1108 graft = isl_ast_graft_unembed(graft, product);
1109 list = isl_ast_graft_list_set_ast_graft(list, i, graft);
1110 }
1111
1112 return list;
1113}
1114
1115/* Compute the preimage of "graft" under the function represented by "ma".
1116 * In other words, plug in "ma" in "enforced" and "guard" fields of "graft".
1117 */
1118__isl_give isl_ast_graft *isl_ast_graft_preimage_multi_aff(
1119 __isl_take isl_ast_graft *graft, __isl_take isl_multi_aff *ma)
1120{
1121 isl_basic_set *enforced;
1122
1123 if (!graft)
1124 return NULL((void*)0);
1125
1126 enforced = graft->enforced;
1127 graft->enforced = isl_basic_set_preimage_multi_aff(enforced,
1128 isl_multi_aff_copy(ma));
1129 graft->guard = isl_set_preimage_multi_aff(graft->guard, ma);
1130
1131 if (!graft->enforced || !graft->guard)
1132 return isl_ast_graft_free(graft);
1133
1134 return graft;
1135}
1136
1137/* Compute the preimage of all the grafts in "list" under
1138 * the function represented by "ma".
1139 */
1140__isl_give isl_ast_graft_list *isl_ast_graft_list_preimage_multi_aff(
1141 __isl_take isl_ast_graft_list *list, __isl_take isl_multi_aff *ma)
1142{
1143 int i, n;
1144
1145 n = isl_ast_graft_list_n_ast_graft(list);
1146 for (i = 0; i < n; ++i) {
1147 isl_ast_graft *graft;
1148
1149 graft = isl_ast_graft_list_get_ast_graft(list, i);
1150 graft = isl_ast_graft_preimage_multi_aff(graft,
1151 isl_multi_aff_copy(ma));
1152 list = isl_ast_graft_list_set_ast_graft(list, i, graft);
1153 }
1154
1155 isl_multi_aff_free(ma);
1156 return list;
1157}
1158
1159/* Compare two grafts based on their guards.
1160 */
1161static int cmp_graft(__isl_keep isl_ast_graft *a, __isl_keep isl_ast_graft *b,
1162 void *user)
1163{
1164 return isl_set_plain_cmp(a->guard, b->guard);
1165}
1166
1167/* Order the elements in "list" based on their guards.
1168 */
1169__isl_give isl_ast_graft_list *isl_ast_graft_list_sort_guard(
1170 __isl_take isl_ast_graft_list *list)
1171{
1172 return isl_ast_graft_list_sort(list, &cmp_graft, NULL((void*)0));
1173}
1174
1175/* Merge the given two lists into a single list of grafts,
1176 * merging grafts with the same guard into a single graft.
1177 *
1178 * "list2" has been sorted using isl_ast_graft_list_sort.
1179 * "list1" may be the result of a previous call to isl_ast_graft_list_merge
1180 * and may therefore not be completely sorted.
1181 *
1182 * The elements in "list2" need to be executed after those in "list1",
1183 * but if the guard of a graft in "list2" is disjoint from the guards
1184 * of some final elements in "list1", then it can be moved up to before
1185 * those final elements.
1186 *
1187 * In particular, we look at each element g of "list2" in turn
1188 * and move it up beyond elements of "list1" that would be sorted
1189 * after g as long as each of these elements has a guard that is disjoint
1190 * from that of g.
1191 *
1192 * We do not allow the second or any later element of "list2" to be moved
1193 * before a previous elements of "list2" even if the reason that
1194 * that element didn't move up further was that its guard was not disjoint
1195 * from that of the previous element in "list1".
1196 */
1197__isl_give isl_ast_graft_list *isl_ast_graft_list_merge(
1198 __isl_take isl_ast_graft_list *list1,
1199 __isl_take isl_ast_graft_list *list2,
1200 __isl_keep isl_ast_build *build)
1201{
1202 int i, j, first;
1203
1204 if (!list1 || !list2 || !build)
1
Assuming 'list1' is non-null
2
Assuming 'list2' is non-null
3
Assuming 'build' is non-null
4
Taking false branch
1205 goto error;
1206 if (list2->n == 0) {
5
Assuming the condition is false
6
Taking false branch
1207 isl_ast_graft_list_free(list2);
1208 return list1;
1209 }
1210 if (list1->n == 0) {
7
Assuming the condition is false
8
Taking false branch
1211 isl_ast_graft_list_free(list1);
1212 return list2;
1213 }
1214
1215 first = 0;
1216 for (i = 0; i < list2->n; ++i) {
9
Assuming the condition is true
10
Loop condition is true. Entering loop body
1217 isl_ast_graft *graft;
1218 graft = isl_ast_graft_list_get_ast_graft(list2, i);
1219 if (!graft)
11
Taking false branch
1220 break;
1221
1222 for (j = list1->n; j >= 0; --j) {
12
Assuming 'j' is >= 0
13
Loop condition is true. Entering loop body
1223 int cmp, disjoint;
1224 isl_ast_graft *graft_j;
1225
1226 if (j == first)
14
Taking false branch
1227 cmp = -1;
1228 else
1229 cmp = isl_set_plain_cmp(list1->p[j - 1]->guard,
1230 graft->guard);
1231 if (cmp > 0) {
15
Assuming 'cmp' is <= 0
16
Taking false branch
1232 disjoint = isl_set_is_disjoint(graft->guard,
1233 list1->p[j - 1]->guard);
1234 if (disjoint < 0) {
1235 isl_ast_graft_free(graft);
1236 list1 = isl_ast_graft_list_free(list1);
1237 break;
1238 }
1239 if (!disjoint)
1240 cmp = -1;
1241 }
1242 if (cmp > 0)
17
Taking false branch
1243 continue;
1244 if (cmp < 0) {
18
Assuming 'cmp' is >= 0
19
Taking false branch
1245 list1 = isl_ast_graft_list_insert(list1, j,
1246 graft);
1247 break;
1248 }
1249
1250 --j;
1251
1252 graft_j = isl_ast_graft_list_get_ast_graft(list1, j);
1253 graft_j = isl_ast_graft_fuse(graft_j, graft, build);
20
Calling 'isl_ast_graft_fuse'
1254 list1 = isl_ast_graft_list_set_ast_graft(list1, j,
1255 graft_j);
1256 break;
1257 }
1258
1259 if (j < 0) {
1260 isl_ast_graft_free(graft);
1261 isl_die(isl_ast_build_get_ctx(build),do { isl_handle_error(isl_ast_build_get_ctx(build), isl_error_internal
, "element failed to get inserted", "/build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/isl_ast_graft.c"
, 1263); break; } while (0)
1262 isl_error_internal,do { isl_handle_error(isl_ast_build_get_ctx(build), isl_error_internal
, "element failed to get inserted", "/build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/isl_ast_graft.c"
, 1263); break; } while (0)
1263 "element failed to get inserted", break)do { isl_handle_error(isl_ast_build_get_ctx(build), isl_error_internal
, "element failed to get inserted", "/build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/isl_ast_graft.c"
, 1263); break; } while (0)
;
1264 }
1265
1266 first = j + 1;
1267 if (!list1)
1268 break;
1269 }
1270 if (i < list2->n)
1271 list1 = isl_ast_graft_list_free(list1);
1272 isl_ast_graft_list_free(list2);
1273
1274 return list1;
1275error:
1276 isl_ast_graft_list_free(list1);
1277 isl_ast_graft_list_free(list2);
1278 return NULL((void*)0);
1279}
1280
1281__isl_give isl_printer *isl_printer_print_ast_graft(__isl_take isl_printer *p,
1282 __isl_keep isl_ast_graft *graft)
1283{
1284 if (!p)
1285 return NULL((void*)0);
1286 if (!graft)
1287 return isl_printer_free(p);
1288
1289 p = isl_printer_print_str(p, "(");
1290 p = isl_printer_print_str(p, "guard: ");
1291 p = isl_printer_print_set(p, graft->guard);
1292 p = isl_printer_print_str(p, ", ");
1293 p = isl_printer_print_str(p, "enforced: ");
1294 p = isl_printer_print_basic_set(p, graft->enforced);
1295 p = isl_printer_print_str(p, ", ");
1296 p = isl_printer_print_str(p, "node: ");
1297 p = isl_printer_print_ast_node(p, graft->node);
1298 p = isl_printer_print_str(p, ")");
1299
1300 return p;
1301}

/build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/isl_list_templ.c

1/*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2011 INRIA Saclay
4 * Copyright 2012-2013 Ecole Normale Superieure
5 * Copyright 2017 Sven Verdoolaege
6 *
7 * Use of this software is governed by the MIT license
8 *
9 * Written by Sven Verdoolaege, K.U.Leuven, Departement
10 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
11 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
12 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
13 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
14 */
15
16#include <isl_sort.h>
17#include <isl_tarjan.h>
18#include <isl/printer.h>
19
20#define xCAT(A,B)AB A ## B
21#define CAT(A,B)AB xCAT(A,B)AB
22#undef ELisl_ast_graft
23#define ELisl_ast_graft CAT(isl_,BASE)isl_ast_graft
24#define xFN(TYPE,NAME)TYPE_NAME TYPEisl_ast_graft ## _ ## NAME
25#define FN(TYPE,NAME)isl_ast_graft_NAME xFN(TYPE,NAME)TYPE_NAME
26#define xLIST(EL)EL_list ELisl_ast_graft ## _list
27#define LIST(EL)isl_ast_graft_list xLIST(EL)EL_list
28#define xS(TYPE,NAME)struct TYPE_NAME struct TYPEisl_ast_graft ## _ ## NAME
29#define S(TYPE,NAME)struct isl_ast_graft_NAME xS(TYPE,NAME)struct TYPE_NAME
30
31isl_ctx *FN(LIST(EL),get_ctx)isl_ast_graft_list_get_ctx(__isl_keep LIST(EL)isl_ast_graft_list *list)
32{
33 return list ? list->ctx : NULL((void*)0);
34}
35
36__isl_give LIST(EL)isl_ast_graft_list *FN(LIST(EL),alloc)isl_ast_graft_list_alloc(isl_ctx *ctx, int n)
37{
38 LIST(EL)isl_ast_graft_list *list;
39
40 if (n < 0)
41 isl_die(ctx, isl_error_invalid,do { isl_handle_error(ctx, isl_error_invalid, "cannot create list of negative length"
, "/build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/isl_list_templ.c"
, 43); return ((void*)0); } while (0)
42 "cannot create list of negative length",do { isl_handle_error(ctx, isl_error_invalid, "cannot create list of negative length"
, "/build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/isl_list_templ.c"
, 43); return ((void*)0); } while (0)
43 return NULL)do { isl_handle_error(ctx, isl_error_invalid, "cannot create list of negative length"
, "/build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/isl_list_templ.c"
, 43); return ((void*)0); } while (0)
;
44 list = isl_alloc(ctx, LIST(EL),((isl_ast_graft_list *)isl_malloc_or_die(ctx, sizeof(isl_ast_graft_list
) + (n - 1) * sizeof(struct isl_ast_graft *)))
45 sizeof(LIST(EL)) + (n - 1) * sizeof(struct EL *))((isl_ast_graft_list *)isl_malloc_or_die(ctx, sizeof(isl_ast_graft_list
) + (n - 1) * sizeof(struct isl_ast_graft *)))
;
46 if (!list)
47 return NULL((void*)0);
48
49 list->ctx = ctx;
50 isl_ctx_ref(ctx);
51 list->ref = 1;
52 list->size = n;
53 list->n = 0;
54 return list;
55}
56
57__isl_give LIST(EL)isl_ast_graft_list *FN(LIST(EL),copy)isl_ast_graft_list_copy(__isl_keep LIST(EL)isl_ast_graft_list *list)
58{
59 if (!list)
60 return NULL((void*)0);
61
62 list->ref++;
63 return list;
64}
65
66__isl_give LIST(EL)isl_ast_graft_list *FN(LIST(EL),dup)isl_ast_graft_list_dup(__isl_keep LIST(EL)isl_ast_graft_list *list)
67{
68 int i;
69 LIST(EL)isl_ast_graft_list *dup;
70
71 if (!list)
72 return NULL((void*)0);
73
74 dup = FN(LIST(EL),alloc)isl_ast_graft_list_alloc(FN(LIST(EL),get_ctx)isl_ast_graft_list_get_ctx(list), list->n);
75 if (!dup)
76 return NULL((void*)0);
77 for (i = 0; i < list->n; ++i)
78 dup = FN(LIST(EL),add)isl_ast_graft_list_add(dup, FN(EL,copy)isl_ast_graft_copy(list->p[i]));
79 return dup;
80}
81
82__isl_give LIST(EL)isl_ast_graft_list *FN(LIST(EL),cow)isl_ast_graft_list_cow(__isl_take LIST(EL)isl_ast_graft_list *list)
83{
84 if (!list)
85 return NULL((void*)0);
86
87 if (list->ref == 1)
88 return list;
89 list->ref--;
90 return FN(LIST(EL),dup)isl_ast_graft_list_dup(list);
91}
92
93/* Make sure "list" has room for at least "n" more pieces.
94 * Always return a list with a single reference.
95 *
96 * If there is only one reference to list, we extend it in place.
97 * Otherwise, we create a new LIST(EL) and copy the elements.
98 */
99static __isl_give LIST(EL)isl_ast_graft_list *FN(LIST(EL),grow)isl_ast_graft_list_grow(__isl_take LIST(EL)isl_ast_graft_list *list, int n)
100{
101 isl_ctx *ctx;
102 int i, new_size;
103 LIST(EL)isl_ast_graft_list *res;
104
105 if (!list)
106 return NULL((void*)0);
107 if (list->ref == 1 && list->n + n <= list->size)
108 return list;
109
110 ctx = FN(LIST(EL),get_ctx)isl_ast_graft_list_get_ctx(list);
111 new_size = ((list->n + n + 1) * 3) / 2;
112 if (list->ref == 1) {
113 res = isl_realloc(ctx, list, LIST(EL),((isl_ast_graft_list *)isl_realloc_or_die(ctx, list, sizeof(isl_ast_graft_list
) + (new_size - 1) * sizeof(isl_ast_graft *)))
114 sizeof(LIST(EL)) + (new_size - 1) * sizeof(EL *))((isl_ast_graft_list *)isl_realloc_or_die(ctx, list, sizeof(isl_ast_graft_list
) + (new_size - 1) * sizeof(isl_ast_graft *)))
;
115 if (!res)
116 return FN(LIST(EL),free)isl_ast_graft_list_free(list);
117 res->size = new_size;
118 return res;
119 }
120
121 if (list->n + n <= list->size && list->size < new_size)
122 new_size = list->size;
123
124 res = FN(LIST(EL),alloc)isl_ast_graft_list_alloc(ctx, new_size);
125 if (!res)
126 return FN(LIST(EL),free)isl_ast_graft_list_free(list);
127
128 for (i = 0; i < list->n; ++i)
129 res = FN(LIST(EL),add)isl_ast_graft_list_add(res, FN(EL,copy)isl_ast_graft_copy(list->p[i]));
130
131 FN(LIST(EL),free)isl_ast_graft_list_free(list);
132 return res;
133}
134
135/* Check that "index" is a valid position in "list".
136 */
137static isl_stat FN(LIST(EL),check_index)isl_ast_graft_list_check_index(__isl_keep LIST(EL)isl_ast_graft_list *list, int index)
138{
139 if (!list)
140 return isl_stat_error;
141 if (index < 0 || index >= list->n)
142 isl_die(FN(LIST(EL),get_ctx)(list), isl_error_invalid,do { isl_handle_error(isl_ast_graft_list_get_ctx(list), isl_error_invalid
, "index out of bounds", "/build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/isl_list_templ.c"
, 143); return isl_stat_error; } while (0)
143 "index out of bounds", return isl_stat_error)do { isl_handle_error(isl_ast_graft_list_get_ctx(list), isl_error_invalid
, "index out of bounds", "/build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/isl_list_templ.c"
, 143); return isl_stat_error; } while (0)
;
144 return isl_stat_ok;
145}
146
147__isl_give LIST(EL)isl_ast_graft_list *FN(LIST(EL),add)isl_ast_graft_list_add(__isl_take LIST(EL)isl_ast_graft_list *list,
148 __isl_take struct ELisl_ast_graft *el)
149{
150 list = FN(LIST(EL),grow)isl_ast_graft_list_grow(list, 1);
151 if (!list || !el)
152 goto error;
153 list->p[list->n] = el;
154 list->n++;
155 return list;
156error:
157 FN(EL,free)isl_ast_graft_free(el);
158 FN(LIST(EL),free)isl_ast_graft_list_free(list);
159 return NULL((void*)0);
160}
161
162/* Remove the "n" elements starting at "first" from "list".
163 */
164__isl_give LIST(EL)isl_ast_graft_list *FN(LIST(EL),drop)isl_ast_graft_list_drop(__isl_take LIST(EL)isl_ast_graft_list *list,
165 unsigned first, unsigned n)
166{
167 int i;
168
169 if (!list)
170 return NULL((void*)0);
171 if (first + n > list->n || first + n < first)
172 isl_die(list->ctx, isl_error_invalid,do { isl_handle_error(list->ctx, isl_error_invalid, "index out of bounds"
, "/build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/isl_list_templ.c"
, 173); return isl_ast_graft_list_free(list); } while (0)
173 "index out of bounds", return FN(LIST(EL),free)(list))do { isl_handle_error(list->ctx, isl_error_invalid, "index out of bounds"
, "/build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/isl_list_templ.c"
, 173); return isl_ast_graft_list_free(list); } while (0)
;
174 if (n == 0)
175 return list;
176 list = FN(LIST(EL),cow)isl_ast_graft_list_cow(list);
177 if (!list)
178 return NULL((void*)0);
179 for (i = 0; i < n; ++i)
180 FN(EL,free)isl_ast_graft_free(list->p[first + i]);
181 for (i = first; i + n < list->n; ++i)
182 list->p[i] = list->p[i + n];
183 list->n -= n;
184 return list;
185}
186
187/* Insert "el" at position "pos" in "list".
188 *
189 * If there is only one reference to "list" and if it already has space
190 * for one extra element, we insert it directly into "list".
191 * Otherwise, we create a new list consisting of "el" and copied
192 * elements from "list".
193 */
194__isl_give LIST(EL)isl_ast_graft_list *FN(LIST(EL),insert)isl_ast_graft_list_insert(__isl_take LIST(EL)isl_ast_graft_list *list,
195 unsigned pos, __isl_take struct ELisl_ast_graft *el)
196{
197 int i;
198 isl_ctx *ctx;
199 LIST(EL)isl_ast_graft_list *res;
200
201 if (!list || !el)
202 goto error;
203 ctx = FN(LIST(EL),get_ctx)isl_ast_graft_list_get_ctx(list);
204 if (pos > list->n)
205 isl_die(ctx, isl_error_invalid,do { isl_handle_error(ctx, isl_error_invalid, "index out of bounds"
, "/build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/isl_list_templ.c"
, 206); goto error; } while (0)
206 "index out of bounds", goto error)do { isl_handle_error(ctx, isl_error_invalid, "index out of bounds"
, "/build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/isl_list_templ.c"
, 206); goto error; } while (0)
;
207
208 if (list->ref == 1 && list->size > list->n) {
209 for (i = list->n; i > pos; --i)
210 list->p[i] = list->p[i - 1];
211 list->n++;
212 list->p[pos] = el;
213 return list;
214 }
215
216 res = FN(LIST(EL),alloc)isl_ast_graft_list_alloc(ctx, list->n + 1);
217 for (i = 0; i < pos; ++i)
218 res = FN(LIST(EL),add)isl_ast_graft_list_add(res, FN(EL,copy)isl_ast_graft_copy(list->p[i]));
219 res = FN(LIST(EL),add)isl_ast_graft_list_add(res, el);
220 for (i = pos; i < list->n; ++i)
221 res = FN(LIST(EL),add)isl_ast_graft_list_add(res, FN(EL,copy)isl_ast_graft_copy(list->p[i]));
222 FN(LIST(EL),free)isl_ast_graft_list_free(list);
223
224 return res;
225error:
226 FN(EL,free)isl_ast_graft_free(el);
227 FN(LIST(EL),free)isl_ast_graft_list_free(list);
228 return NULL((void*)0);
229}
230
231__isl_null LIST(EL)isl_ast_graft_list *FN(LIST(EL),free)isl_ast_graft_list_free(__isl_take LIST(EL)isl_ast_graft_list *list)
232{
233 int i;
234
235 if (!list)
49
Taking false branch
236 return NULL((void*)0);
237
238 if (--list->ref > 0)
50
Assuming the condition is false
51
Taking false branch
239 return NULL((void*)0);
240
241 isl_ctx_deref(list->ctx);
242 for (i = 0; i < list->n; ++i)
52
Loop condition is true. Entering loop body
243 FN(EL,free)isl_ast_graft_free(list->p[i]);
53
Use of memory after it is freed
244 free(list);
245
246 return NULL((void*)0);
247}
248
249/* Return the number of elements in "list".
250 */
251int FN(LIST(EL),size)isl_ast_graft_list_size(__isl_keep LIST(EL)isl_ast_graft_list *list)
252{
253 return list ? list->n : 0;
254}
255
256/* This is an alternative name for the function above.
257 */
258int FN(FN(LIST(EL),n),BASE)isl_ast_graft_list_n_ast_graft(__isl_keep LIST(EL)isl_ast_graft_list *list)
259{
260 return FN(LIST(EL),size)isl_ast_graft_list_size(list);
261}
262
263/* Return the element at position "index" in "list".
264 */
265static __isl_keep ELisl_ast_graft *FN(LIST(EL),peek)isl_ast_graft_list_peek(__isl_keep LIST(EL)isl_ast_graft_list *list, int index)
266{
267 if (FN(LIST(EL),check_index)isl_ast_graft_list_check_index(list, index) < 0)
268 return NULL((void*)0);
269 return list->p[index];
270}
271
272/* Return a copy of the element at position "index" in "list".
273 */
274__isl_give ELisl_ast_graft *FN(LIST(EL),get_at)isl_ast_graft_list_get_at(__isl_keep LIST(EL)isl_ast_graft_list *list, int index)
275{
276 return FN(EL,copy)isl_ast_graft_copy(FN(LIST(EL),peek)isl_ast_graft_list_peek(list, index));
30
Calling 'isl_ast_graft_copy'
33
Returning from 'isl_ast_graft_copy'
277}
278
279/* This is an alternative name for the function above.
280 */
281__isl_give ELisl_ast_graft *FN(FN(LIST(EL),get),BASE)isl_ast_graft_list_get_ast_graft(__isl_keep LIST(EL)isl_ast_graft_list *list, int index)
282{
283 return FN(LIST(EL),get_at)isl_ast_graft_list_get_at(list, index);
29
Calling 'isl_ast_graft_list_get_at'
34
Returning from 'isl_ast_graft_list_get_at'
284}
285
286/* Replace the element at position "index" in "list" by "el".
287 */
288__isl_give LIST(EL)isl_ast_graft_list *FN(FN(LIST(EL),set),BASE)isl_ast_graft_list_set_ast_graft(__isl_take LIST(EL)isl_ast_graft_list *list,
289 int index, __isl_take ELisl_ast_graft *el)
290{
291 if (!list || !el)
46
Taking true branch
292 goto error;
47
Control jumps to line 306
293 if (FN(LIST(EL),check_index)isl_ast_graft_list_check_index(list, index) < 0)
294 goto error;
295 if (list->p[index] == el) {
296 FN(EL,free)isl_ast_graft_free(el);
297 return list;
298 }
299 list = FN(LIST(EL),cow)isl_ast_graft_list_cow(list);
300 if (!list)
301 goto error;
302 FN(EL,free)isl_ast_graft_free(list->p[index]);
303 list->p[index] = el;
304 return list;
305error:
306 FN(EL,free)isl_ast_graft_free(el);
307 FN(LIST(EL),free)isl_ast_graft_list_free(list);
48
Calling 'isl_ast_graft_list_free'
308 return NULL((void*)0);
309}
310
311/* Return the element at position "index" of "list".
312 * This may be either a copy or the element itself
313 * if there is only one reference to "list".
314 * This allows the element to be modified inplace
315 * if both the list and the element have only a single reference.
316 * The caller is not allowed to modify "list" between
317 * this call to isl_list_*_take_* and a subsequent call
318 * to isl_list_*_restore_*.
319 * The only exception is that isl_list_*_free can be called instead.
320 */
321static __isl_give ELisl_ast_graft *FN(FN(LIST(EL),take),BASE)isl_ast_graft_list_take_ast_graft(__isl_keep LIST(EL)isl_ast_graft_list *list,
322 int index)
323{
324 ELisl_ast_graft *el;
325
326 if (FN(LIST(EL),check_index)isl_ast_graft_list_check_index(list, index) < 0)
327 return NULL((void*)0);
328 if (list->ref != 1)
329 return FN(FN(LIST(EL),get),BASE)isl_ast_graft_list_get_ast_graft(list, index);
330 el = list->p[index];
331 list->p[index] = NULL((void*)0);
332 return el;
333}
334
335/* Set the element at position "index" of "list" to "el",
336 * where the position may be empty due to a previous call
337 * to isl_list_*_take_*.
338 */
339static __isl_give LIST(EL)isl_ast_graft_list *FN(FN(LIST(EL),restore),BASE)isl_ast_graft_list_restore_ast_graft(
340 __isl_take LIST(EL)isl_ast_graft_list *list, int index, __isl_take ELisl_ast_graft *el)
341{
342 return FN(FN(LIST(EL),set),BASE)isl_ast_graft_list_set_ast_graft(list, index, el);
343}
344
345/* Swap the elements of "list" in positions "pos1" and "pos2".
346 */
347__isl_give LIST(EL)isl_ast_graft_list *FN(LIST(EL),swap)isl_ast_graft_list_swap(__isl_take LIST(EL)isl_ast_graft_list *list,
348 unsigned pos1, unsigned pos2)
349{
350 ELisl_ast_graft *el1, *el2;
351
352 if (pos1 == pos2)
353 return list;
354 el1 = FN(FN(LIST(EL),take),BASE)isl_ast_graft_list_take_ast_graft(list, pos1);
355 el2 = FN(FN(LIST(EL),take),BASE)isl_ast_graft_list_take_ast_graft(list, pos2);
356 list = FN(FN(LIST(EL),restore),BASE)isl_ast_graft_list_restore_ast_graft(list, pos1, el2);
357 list = FN(FN(LIST(EL),restore),BASE)isl_ast_graft_list_restore_ast_graft(list, pos2, el1);
358 return list;
359}
360
361/* Reverse the elements of "list".
362 */
363__isl_give LIST(EL)isl_ast_graft_list *FN(LIST(EL),reverse)isl_ast_graft_list_reverse(__isl_take LIST(EL)isl_ast_graft_list *list)
364{
365 int i, n;
366
367 n = FN(LIST(EL),size)isl_ast_graft_list_size(list);
368 for (i = 0; i < n - 1 - i; ++i)
369 list = FN(LIST(EL),swap)isl_ast_graft_list_swap(list, i, n - 1 - i);
370 return list;
371}
372
373isl_stat FN(LIST(EL),foreach)isl_ast_graft_list_foreach(__isl_keep LIST(EL)isl_ast_graft_list *list,
374 isl_stat (*fn)(__isl_take ELisl_ast_graft *el, void *user), void *user)
375{
376 int i;
377
378 if (!list)
379 return isl_stat_error;
380
381 for (i = 0; i < list->n; ++i) {
382 ELisl_ast_graft *el = FN(EL,copy)isl_ast_graft_copy(list->p[i]);
383 if (!el)
384 return isl_stat_error;
385 if (fn(el, user) < 0)
386 return isl_stat_error;
387 }
388
389 return isl_stat_ok;
390}
391
392/* Replace each element in "list" by the result of calling "fn"
393 * on the element.
394 */
395__isl_give LIST(EL)isl_ast_graft_list *FN(LIST(EL),map)isl_ast_graft_list_map(__isl_keep LIST(EL)isl_ast_graft_list *list,
396 __isl_give ELisl_ast_graft *(*fn)(__isl_take ELisl_ast_graft *el, void *user), void *user)
397{
398 int i, n;
399
400 if (!list)
401 return NULL((void*)0);
402
403 n = list->n;
404 for (i = 0; i < n; ++i) {
405 ELisl_ast_graft *el = FN(FN(LIST(EL),take),BASE)isl_ast_graft_list_take_ast_graft(list, i);
406 if (!el)
407 return FN(LIST(EL),free)isl_ast_graft_list_free(list);
408 el = fn(el, user);
409 list = FN(FN(LIST(EL),restore),BASE)isl_ast_graft_list_restore_ast_graft(list, i, el);
410 }
411
412 return list;
413}
414
415/* Internal data structure for isl_*_list_sort.
416 *
417 * "cmp" is the original comparison function.
418 * "user" is a user provided pointer that should be passed to "cmp".
419 */
420S(LIST(EL),sort_data)struct isl_ast_graft_list_sort_data {
421 int (*cmp)(__isl_keep ELisl_ast_graft *a, __isl_keep ELisl_ast_graft *b, void *user);
422 void *user;
423};
424
425/* Compare two entries of an isl_*_list based on the user provided
426 * comparison function on pairs of isl_* objects.
427 */
428static int FN(LIST(EL),cmp)isl_ast_graft_list_cmp(const void *a, const void *b, void *user)
429{
430 S(LIST(EL),sort_data)struct isl_ast_graft_list_sort_data *data = user;
431 ELisl_ast_graft * const *el1 = a;
432 ELisl_ast_graft * const *el2 = b;
433
434 return data->cmp(*el1, *el2, data->user);
435}
436
437/* Sort the elements of "list" in ascending order according to
438 * comparison function "cmp".
439 */
440__isl_give LIST(EL)isl_ast_graft_list *FN(LIST(EL),sort)isl_ast_graft_list_sort(__isl_take LIST(EL)isl_ast_graft_list *list,
441 int (*cmp)(__isl_keep ELisl_ast_graft *a, __isl_keep ELisl_ast_graft *b, void *user), void *user)
442{
443 S(LIST(EL),sort_data)struct isl_ast_graft_list_sort_data data = { cmp, user };
444
445 if (!list)
446 return NULL((void*)0);
447 if (list->n <= 1)
448 return list;
449 list = FN(LIST(EL),cow)isl_ast_graft_list_cow(list);
450 if (!list)
451 return NULL((void*)0);
452
453 if (isl_sort(list->p, list->n, sizeof(list->p[0]),
454 &FN(LIST(EL),cmp)isl_ast_graft_list_cmp, &data) < 0)
455 return FN(LIST(EL),free)isl_ast_graft_list_free(list);
456
457 return list;
458}
459
460/* Internal data structure for isl_*_list_foreach_scc.
461 *
462 * "list" is the original list.
463 * "follows" is the user provided callback that defines the edges of the graph.
464 */
465S(LIST(EL),foreach_scc_data)struct isl_ast_graft_list_foreach_scc_data {
466 LIST(EL)isl_ast_graft_list *list;
467 isl_bool (*follows)(__isl_keep ELisl_ast_graft *a, __isl_keep ELisl_ast_graft *b, void *user);
468 void *follows_user;
469};
470
471/* Does element i of data->list follow element j?
472 *
473 * Use the user provided callback to find out.
474 */
475static isl_bool FN(LIST(EL),follows)isl_ast_graft_list_follows(int i, int j, void *user)
476{
477 S(LIST(EL),foreach_scc_data)struct isl_ast_graft_list_foreach_scc_data *data = user;
478
479 return data->follows(data->list->p[i], data->list->p[j],
480 data->follows_user);
481}
482
483/* Call "fn" on the sublist of "list" that consists of the elements
484 * with indices specified by the "n" elements of "pos".
485 */
486static isl_stat FN(LIST(EL),call_on_scc)isl_ast_graft_list_call_on_scc(__isl_keep LIST(EL)isl_ast_graft_list *list, int *pos,
487 int n, isl_stat (*fn)(__isl_take LIST(EL)isl_ast_graft_list *scc, void *user), void *user)
488{
489 int i;
490 isl_ctx *ctx;
491 LIST(EL)isl_ast_graft_list *slice;
492
493 ctx = FN(LIST(EL),get_ctx)isl_ast_graft_list_get_ctx(list);
494 slice = FN(LIST(EL),alloc)isl_ast_graft_list_alloc(ctx, n);
495 for (i = 0; i < n; ++i) {
496 ELisl_ast_graft *el;
497
498 el = FN(EL,copy)isl_ast_graft_copy(list->p[pos[i]]);
499 slice = FN(LIST(EL),add)isl_ast_graft_list_add(slice, el);
500 }
501
502 return fn(slice, user);
503}
504
505/* Call "fn" on each of the strongly connected components (SCCs) of
506 * the graph with as vertices the elements of "list" and
507 * a directed edge from node b to node a iff follows(a, b)
508 * returns 1. follows should return -1 on error.
509 *
510 * If SCC a contains a node i that follows a node j in another SCC b
511 * (i.e., follows(i, j, user) returns 1), then fn will be called on SCC a
512 * after being called on SCC b.
513 *
514 * We simply call isl_tarjan_graph_init, extract the SCCs from the result and
515 * call fn on each of them.
516 */
517isl_stat FN(LIST(EL),foreach_scc)isl_ast_graft_list_foreach_scc(__isl_keep LIST(EL)isl_ast_graft_list *list,
518 isl_bool (*follows)(__isl_keep ELisl_ast_graft *a, __isl_keep ELisl_ast_graft *b, void *user),
519 void *follows_user,
520 isl_stat (*fn)(__isl_take LIST(EL)isl_ast_graft_list *scc, void *user), void *fn_user)
521{
522 S(LIST(EL),foreach_scc_data)struct isl_ast_graft_list_foreach_scc_data data = { list, follows, follows_user };
523 int i, n;
524 isl_ctx *ctx;
525 struct isl_tarjan_graph *g;
526
527 if (!list)
528 return isl_stat_error;
529 if (list->n == 0)
530 return isl_stat_ok;
531 if (list->n == 1)
532 return fn(FN(LIST(EL),copy)isl_ast_graft_list_copy(list), fn_user);
533
534 ctx = FN(LIST(EL),get_ctx)isl_ast_graft_list_get_ctx(list);
535 n = list->n;
536 g = isl_tarjan_graph_init(ctx, n, &FN(LIST(EL),follows)isl_ast_graft_list_follows, &data);
537 if (!g)
538 return isl_stat_error;
539
540 i = 0;
541 do {
542 int first;
543
544 if (g->order[i] == -1)
545 isl_die(ctx, isl_error_internal, "cannot happen",do { isl_handle_error(ctx, isl_error_internal, "cannot happen"
, "/build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/isl_list_templ.c"
, 546); break; } while (0)
546 break)do { isl_handle_error(ctx, isl_error_internal, "cannot happen"
, "/build/llvm-toolchain-snapshot-8~svn348900/tools/polly/lib/External/isl/isl_list_templ.c"
, 546); break; } while (0)
;
547 first = i;
548 while (g->order[i] != -1) {
549 ++i; --n;
550 }
551 if (first == 0 && n == 0) {
552 isl_tarjan_graph_free(g);
553 return fn(FN(LIST(EL),copy)isl_ast_graft_list_copy(list), fn_user);
554 }
555 if (FN(LIST(EL),call_on_scc)isl_ast_graft_list_call_on_scc(list, g->order + first, i - first,
556 fn, fn_user) < 0)
557 break;
558 ++i;
559 } while (n);
560
561 isl_tarjan_graph_free(g);
562
563 return n > 0 ? isl_stat_error : isl_stat_ok;
564}
565
566__isl_give LIST(EL)isl_ast_graft_list *FN(FN(LIST(EL),from),BASE)isl_ast_graft_list_from_ast_graft(__isl_take ELisl_ast_graft *el)
567{
568 isl_ctx *ctx;
569 LIST(EL)isl_ast_graft_list *list;
570
571 if (!el)
572 return NULL((void*)0);
573 ctx = FN(EL,get_ctx)isl_ast_graft_get_ctx(el);
574 list = FN(LIST(EL),alloc)isl_ast_graft_list_alloc(ctx, 1);
575 if (!list)
576 goto error;
577 list = FN(LIST(EL),add)isl_ast_graft_list_add(list, el);
578 return list;
579error:
580 FN(EL,free)isl_ast_graft_free(el);
581 return NULL((void*)0);
582}
583
584/* Append the elements of "list2" to "list1", where "list1" is known
585 * to have only a single reference and enough room to hold
586 * the extra elements.
587 */
588static __isl_give LIST(EL)isl_ast_graft_list *FN(LIST(EL),concat_inplace)isl_ast_graft_list_concat_inplace(
589 __isl_take LIST(EL)isl_ast_graft_list *list1, __isl_take LIST(EL)isl_ast_graft_list *list2)
590{
591 int i;
592
593 for (i = 0; i < list2->n; ++i)
594 list1 = FN(LIST(EL),add)isl_ast_graft_list_add(list1, FN(EL,copy)isl_ast_graft_copy(list2->p[i]));
595 FN(LIST(EL),free)isl_ast_graft_list_free(list2);
596 return list1;
597}
598
599/* Concatenate "list1" and "list2".
600 * If "list1" has only one reference and has enough room
601 * for the elements of "list2", the add the elements to "list1" itself.
602 * Otherwise, create a new list to store the result.
603 */
604__isl_give LIST(EL)isl_ast_graft_list *FN(LIST(EL),concat)isl_ast_graft_list_concat(__isl_take LIST(EL)isl_ast_graft_list *list1,
605 __isl_take LIST(EL)isl_ast_graft_list *list2)
606{
607 int i;
608 isl_ctx *ctx;
609 LIST(EL)isl_ast_graft_list *res;
610
611 if (!list1 || !list2)
612 goto error;
613
614 if (list1->ref == 1 && list1->n + list2->n <= list1->size)
615 return FN(LIST(EL),concat_inplace)isl_ast_graft_list_concat_inplace(list1, list2);
616
617 ctx = FN(LIST(EL),get_ctx)isl_ast_graft_list_get_ctx(list1);
618 res = FN(LIST(EL),alloc)isl_ast_graft_list_alloc(ctx, list1->n + list2->n);
619 for (i = 0; i < list1->n; ++i)
620 res = FN(LIST(EL),add)isl_ast_graft_list_add(res, FN(EL,copy)isl_ast_graft_copy(list1->p[i]));
621 for (i = 0; i < list2->n; ++i)
622 res = FN(LIST(EL),add)isl_ast_graft_list_add(res, FN(EL,copy)isl_ast_graft_copy(list2->p[i]));
623
624 FN(LIST(EL),free)isl_ast_graft_list_free(list1);
625 FN(LIST(EL),free)isl_ast_graft_list_free(list2);
626 return res;
627error:
628 FN(LIST(EL),free)isl_ast_graft_list_free(list1);
629 FN(LIST(EL),free)isl_ast_graft_list_free(list2);
630 return NULL((void*)0);
631}
632
633__isl_give isl_printer *CAT(isl_printer_print_,LIST(BASE))isl_printer_print_ast_graft_list(
634 __isl_take isl_printer *p, __isl_keep LIST(EL)isl_ast_graft_list *list)
635{
636 int i;
637
638 if (!p || !list)
639 goto error;
640 p = isl_printer_print_str(p, "(");
641 for (i = 0; i < list->n; ++i) {
642 if (i)
643 p = isl_printer_print_str(p, ",");
644 p = CAT(isl_printer_print_,BASE)isl_printer_print_ast_graft(p, list->p[i]);
645 }
646 p = isl_printer_print_str(p, ")");
647 return p;
648error:
649 isl_printer_free(p);
650 return NULL((void*)0);
651}
652
653void FN(LIST(EL),dump)isl_ast_graft_list_dump(__isl_keep LIST(EL)isl_ast_graft_list *list)
654{
655 isl_printer *printer;
656
657 if (!list)
658 return;
659
660 printer = isl_printer_to_file(FN(LIST(EL),get_ctx)isl_ast_graft_list_get_ctx(list), stderrstderr);
661 printer = CAT(isl_printer_print_,LIST(BASE))isl_printer_print_ast_graft_list(printer, list);
662 printer = isl_printer_end_line(printer);
663
664 isl_printer_free(printer);
665}