Bug Summary

File:tools/polly/lib/External/isl/isl_ast_graft.c
Warning:line 257, column 9
Use of memory after it is freed

Annotated Source Code

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

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