Bug Summary

File:tools/polly/lib/External/isl/isl_ast_graft.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-eagerly-assume -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-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/pet/include -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/ppcg/include -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/ppcg/imath -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/polly/lib/External/ppcg -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/isl -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/isl/imath -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/polly/lib/External/isl -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/polly/include -I /usr/include/jsoncpp -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/polly/lib/External/isl/include -I /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/include -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn329677/include -U NDEBUG -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=gnu99 -fconst-strings -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/tools/polly/lib/External -fdebug-prefix-map=/build/llvm-toolchain-snapshot-7~svn329677=. -ferror-limit 19 -fmessage-length 0 -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-04-11-031539-24776-1 -x c /build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/isl/isl_ast_graft.c

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

/build/llvm-toolchain-snapshot-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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-7~svn329677/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)
32
Taking false branch
236 return NULL((void*)0);
237
238 if (--list->ref > 0)
33
Assuming the condition is false
34
Taking false branch
239 return NULL((void*)0);
240
241 isl_ctx_deref(list->ctx);
242 for (i = 0; i < list->n; ++i)
35
Loop condition is true. Entering loop body
243 FN(EL,free)isl_ast_graft_free(list->p[i]);
36
Within the expansion of the macro 'FN':
a
Use of memory after it is freed
244 free(list);
245
246 return NULL((void*)0);
247}
248
249int FN(FN(LIST(EL),n),BASE)isl_ast_graft_list_n_ast_graft(__isl_keep LIST(EL)isl_ast_graft_list *list)
250{
251 return list ? list->n : 0;
252}
253
254__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)
255{
256 if (FN(LIST(EL),check_index)isl_ast_graft_list_check_index(list, index) < 0)
12
Taking false branch
257 return NULL((void*)0);
258 return FN(EL,copy)isl_ast_graft_copy(list->p[index]);
13
Within the expansion of the macro 'FN':
a
Calling 'isl_ast_graft_copy'
b
Returning from 'isl_ast_graft_copy'
259}
260
261/* Replace the element at position "index" in "list" by "el".
262 */
263__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,
264 int index, __isl_take ELisl_ast_graft *el)
265{
266 if (!list || !el)
267 goto error;
268 if (FN(LIST(EL),check_index)isl_ast_graft_list_check_index(list, index) < 0)
269 goto error;
270 if (list->p[index] == el) {
271 FN(EL,free)isl_ast_graft_free(el);
272 return list;
273 }
274 list = FN(LIST(EL),cow)isl_ast_graft_list_cow(list);
275 if (!list)
276 goto error;
277 FN(EL,free)isl_ast_graft_free(list->p[index]);
278 list->p[index] = el;
279 return list;
280error:
281 FN(EL,free)isl_ast_graft_free(el);
282 FN(LIST(EL),free)isl_ast_graft_list_free(list);
283 return NULL((void*)0);
284}
285
286/* Return the element at position "index" of "list".
287 * This may be either a copy or the element itself
288 * if there is only one reference to "list".
289 * This allows the element to be modified inplace
290 * if both the list and the element have only a single reference.
291 * The caller is not allowed to modify "list" between
292 * this call to isl_list_*_take_* and a subsequent call
293 * to isl_list_*_restore_*.
294 * The only exception is that isl_list_*_free can be called instead.
295 */
296static __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,
297 int index)
298{
299 ELisl_ast_graft *el;
300
301 if (FN(LIST(EL),check_index)isl_ast_graft_list_check_index(list, index) < 0)
302 return NULL((void*)0);
303 if (list->ref != 1)
304 return FN(FN(LIST(EL),get),BASE)isl_ast_graft_list_get_ast_graft(list, index);
305 el = list->p[index];
306 list->p[index] = NULL((void*)0);
307 return el;
308}
309
310/* Set the element at position "index" of "list" to "el",
311 * where the position may be empty due to a previous call
312 * to isl_list_*_take_*.
313 */
314static __isl_give LIST(EL)isl_ast_graft_list *FN(FN(LIST(EL),restore),BASE)isl_ast_graft_list_restore_ast_graft(
315 __isl_take LIST(EL)isl_ast_graft_list *list, int index, __isl_take ELisl_ast_graft *el)
316{
317 return FN(FN(LIST(EL),set),BASE)isl_ast_graft_list_set_ast_graft(list, index, el);
318}
319
320isl_stat FN(LIST(EL),foreach)isl_ast_graft_list_foreach(__isl_keep LIST(EL)isl_ast_graft_list *list,
321 isl_stat (*fn)(__isl_take ELisl_ast_graft *el, void *user), void *user)
322{
323 int i;
324
325 if (!list)
326 return isl_stat_error;
327
328 for (i = 0; i < list->n; ++i) {
329 ELisl_ast_graft *el = FN(EL,copy)isl_ast_graft_copy(list->p[i]);
330 if (!el)
331 return isl_stat_error;
332 if (fn(el, user) < 0)
333 return isl_stat_error;
334 }
335
336 return isl_stat_ok;
337}
338
339/* Replace each element in "list" by the result of calling "fn"
340 * on the element.
341 */
342__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,
343 __isl_give ELisl_ast_graft *(*fn)(__isl_take ELisl_ast_graft *el, void *user), void *user)
344{
345 int i, n;
346
347 if (!list)
348 return NULL((void*)0);
349
350 n = list->n;
351 for (i = 0; i < n; ++i) {
352 ELisl_ast_graft *el = FN(FN(LIST(EL),take),BASE)isl_ast_graft_list_take_ast_graft(list, i);
353 if (!el)
354 return FN(LIST(EL),free)isl_ast_graft_list_free(list);
355 el = fn(el, user);
356 list = FN(FN(LIST(EL),restore),BASE)isl_ast_graft_list_restore_ast_graft(list, i, el);
357 }
358
359 return list;
360}
361
362/* Internal data structure for isl_*_list_sort.
363 *
364 * "cmp" is the original comparison function.
365 * "user" is a user provided pointer that should be passed to "cmp".
366 */
367S(LIST(EL),sort_data)struct isl_ast_graft_list_sort_data {
368 int (*cmp)(__isl_keep ELisl_ast_graft *a, __isl_keep ELisl_ast_graft *b, void *user);
369 void *user;
370};
371
372/* Compare two entries of an isl_*_list based on the user provided
373 * comparison function on pairs of isl_* objects.
374 */
375static int FN(LIST(EL),cmp)isl_ast_graft_list_cmp(const void *a, const void *b, void *user)
376{
377 S(LIST(EL),sort_data)struct isl_ast_graft_list_sort_data *data = user;
378 ELisl_ast_graft * const *el1 = a;
379 ELisl_ast_graft * const *el2 = b;
380
381 return data->cmp(*el1, *el2, data->user);
382}
383
384/* Sort the elements of "list" in ascending order according to
385 * comparison function "cmp".
386 */
387__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,
388 int (*cmp)(__isl_keep ELisl_ast_graft *a, __isl_keep ELisl_ast_graft *b, void *user), void *user)
389{
390 S(LIST(EL),sort_data)struct isl_ast_graft_list_sort_data data = { cmp, user };
391
392 if (!list)
393 return NULL((void*)0);
394 if (list->n <= 1)
395 return list;
396 list = FN(LIST(EL),cow)isl_ast_graft_list_cow(list);
397 if (!list)
398 return NULL((void*)0);
399
400 if (isl_sort(list->p, list->n, sizeof(list->p[0]),
401 &FN(LIST(EL),cmp)isl_ast_graft_list_cmp, &data) < 0)
402 return FN(LIST(EL),free)isl_ast_graft_list_free(list);
403
404 return list;
405}
406
407/* Internal data structure for isl_*_list_foreach_scc.
408 *
409 * "list" is the original list.
410 * "follows" is the user provided callback that defines the edges of the graph.
411 */
412S(LIST(EL),foreach_scc_data)struct isl_ast_graft_list_foreach_scc_data {
413 LIST(EL)isl_ast_graft_list *list;
414 isl_bool (*follows)(__isl_keep ELisl_ast_graft *a, __isl_keep ELisl_ast_graft *b, void *user);
415 void *follows_user;
416};
417
418/* Does element i of data->list follow element j?
419 *
420 * Use the user provided callback to find out.
421 */
422static isl_bool FN(LIST(EL),follows)isl_ast_graft_list_follows(int i, int j, void *user)
423{
424 S(LIST(EL),foreach_scc_data)struct isl_ast_graft_list_foreach_scc_data *data = user;
425
426 return data->follows(data->list->p[i], data->list->p[j],
427 data->follows_user);
428}
429
430/* Call "fn" on the sublist of "list" that consists of the elements
431 * with indices specified by the "n" elements of "pos".
432 */
433static 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,
434 int n, isl_stat (*fn)(__isl_take LIST(EL)isl_ast_graft_list *scc, void *user), void *user)
435{
436 int i;
437 isl_ctx *ctx;
438 LIST(EL)isl_ast_graft_list *slice;
439
440 ctx = FN(LIST(EL),get_ctx)isl_ast_graft_list_get_ctx(list);
441 slice = FN(LIST(EL),alloc)isl_ast_graft_list_alloc(ctx, n);
442 for (i = 0; i < n; ++i) {
443 ELisl_ast_graft *el;
444
445 el = FN(EL,copy)isl_ast_graft_copy(list->p[pos[i]]);
446 slice = FN(LIST(EL),add)isl_ast_graft_list_add(slice, el);
447 }
448
449 return fn(slice, user);
450}
451
452/* Call "fn" on each of the strongly connected components (SCCs) of
453 * the graph with as vertices the elements of "list" and
454 * a directed edge from node b to node a iff follows(a, b)
455 * returns 1. follows should return -1 on error.
456 *
457 * If SCC a contains a node i that follows a node j in another SCC b
458 * (i.e., follows(i, j, user) returns 1), then fn will be called on SCC a
459 * after being called on SCC b.
460 *
461 * We simply call isl_tarjan_graph_init, extract the SCCs from the result and
462 * call fn on each of them.
463 */
464isl_stat FN(LIST(EL),foreach_scc)isl_ast_graft_list_foreach_scc(__isl_keep LIST(EL)isl_ast_graft_list *list,
465 isl_bool (*follows)(__isl_keep ELisl_ast_graft *a, __isl_keep ELisl_ast_graft *b, void *user),
466 void *follows_user,
467 isl_stat (*fn)(__isl_take LIST(EL)isl_ast_graft_list *scc, void *user), void *fn_user)
468{
469 S(LIST(EL),foreach_scc_data)struct isl_ast_graft_list_foreach_scc_data data = { list, follows, follows_user };
470 int i, n;
471 isl_ctx *ctx;
472 struct isl_tarjan_graph *g;
473
474 if (!list)
475 return isl_stat_error;
476 if (list->n == 0)
477 return isl_stat_ok;
478 if (list->n == 1)
479 return fn(FN(LIST(EL),copy)isl_ast_graft_list_copy(list), fn_user);
480
481 ctx = FN(LIST(EL),get_ctx)isl_ast_graft_list_get_ctx(list);
482 n = list->n;
483 g = isl_tarjan_graph_init(ctx, n, &FN(LIST(EL),follows)isl_ast_graft_list_follows, &data);
484 if (!g)
485 return isl_stat_error;
486
487 i = 0;
488 do {
489 int first;
490
491 if (g->order[i] == -1)
492 isl_die(ctx, isl_error_internal, "cannot happen",do { isl_handle_error(ctx, isl_error_internal, "cannot happen"
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/isl/isl_list_templ.c"
, 493); break; } while (0)
493 break)do { isl_handle_error(ctx, isl_error_internal, "cannot happen"
, "/build/llvm-toolchain-snapshot-7~svn329677/tools/polly/lib/External/isl/isl_list_templ.c"
, 493); break; } while (0)
;
494 first = i;
495 while (g->order[i] != -1) {
496 ++i; --n;
497 }
498 if (first == 0 && n == 0) {
499 isl_tarjan_graph_free(g);
500 return fn(FN(LIST(EL),copy)isl_ast_graft_list_copy(list), fn_user);
501 }
502 if (FN(LIST(EL),call_on_scc)isl_ast_graft_list_call_on_scc(list, g->order + first, i - first,
503 fn, fn_user) < 0)
504 break;
505 ++i;
506 } while (n);
507
508 isl_tarjan_graph_free(g);
509
510 return n > 0 ? isl_stat_error : isl_stat_ok;
511}
512
513__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)
514{
515 isl_ctx *ctx;
516 LIST(EL)isl_ast_graft_list *list;
517
518 if (!el)
519 return NULL((void*)0);
520 ctx = FN(EL,get_ctx)isl_ast_graft_get_ctx(el);
521 list = FN(LIST(EL),alloc)isl_ast_graft_list_alloc(ctx, 1);
522 if (!list)
523 goto error;
524 list = FN(LIST(EL),add)isl_ast_graft_list_add(list, el);
525 return list;
526error:
527 FN(EL,free)isl_ast_graft_free(el);
528 return NULL((void*)0);
529}
530
531/* Append the elements of "list2" to "list1", where "list1" is known
532 * to have only a single reference and enough room to hold
533 * the extra elements.
534 */
535static __isl_give LIST(EL)isl_ast_graft_list *FN(LIST(EL),concat_inplace)isl_ast_graft_list_concat_inplace(
536 __isl_take LIST(EL)isl_ast_graft_list *list1, __isl_take LIST(EL)isl_ast_graft_list *list2)
537{
538 int i;
539
540 for (i = 0; i < list2->n; ++i)
541 list1 = FN(LIST(EL),add)isl_ast_graft_list_add(list1, FN(EL,copy)isl_ast_graft_copy(list2->p[i]));
542 FN(LIST(EL),free)isl_ast_graft_list_free(list2);
543 return list1;
544}
545
546/* Concatenate "list1" and "list2".
547 * If "list1" has only one reference and has enough room
548 * for the elements of "list2", the add the elements to "list1" itself.
549 * Otherwise, create a new list to store the result.
550 */
551__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,
552 __isl_take LIST(EL)isl_ast_graft_list *list2)
553{
554 int i;
555 isl_ctx *ctx;
556 LIST(EL)isl_ast_graft_list *res;
557
558 if (!list1 || !list2)
559 goto error;
560
561 if (list1->ref == 1 && list1->n + list2->n <= list1->size)
562 return FN(LIST(EL),concat_inplace)isl_ast_graft_list_concat_inplace(list1, list2);
563
564 ctx = FN(LIST(EL),get_ctx)isl_ast_graft_list_get_ctx(list1);
565 res = FN(LIST(EL),alloc)isl_ast_graft_list_alloc(ctx, list1->n + list2->n);
566 for (i = 0; i < list1->n; ++i)
567 res = FN(LIST(EL),add)isl_ast_graft_list_add(res, FN(EL,copy)isl_ast_graft_copy(list1->p[i]));
568 for (i = 0; i < list2->n; ++i)
569 res = FN(LIST(EL),add)isl_ast_graft_list_add(res, FN(EL,copy)isl_ast_graft_copy(list2->p[i]));
570
571 FN(LIST(EL),free)isl_ast_graft_list_free(list1);
572 FN(LIST(EL),free)isl_ast_graft_list_free(list2);
573 return res;
574error:
575 FN(LIST(EL),free)isl_ast_graft_list_free(list1);
576 FN(LIST(EL),free)isl_ast_graft_list_free(list2);
577 return NULL((void*)0);
578}
579
580__isl_give isl_printer *CAT(isl_printer_print_,LIST(BASE))isl_printer_print_ast_graft_list(
581 __isl_take isl_printer *p, __isl_keep LIST(EL)isl_ast_graft_list *list)
582{
583 int i;
584
585 if (!p || !list)
586 goto error;
587 p = isl_printer_print_str(p, "(");
588 for (i = 0; i < list->n; ++i) {
589 if (i)
590 p = isl_printer_print_str(p, ",");
591 p = CAT(isl_printer_print_,BASE)isl_printer_print_ast_graft(p, list->p[i]);
592 }
593 p = isl_printer_print_str(p, ")");
594 return p;
595error:
596 isl_printer_free(p);
597 return NULL((void*)0);
598}
599
600void FN(LIST(EL),dump)isl_ast_graft_list_dump(__isl_keep LIST(EL)isl_ast_graft_list *list)
601{
602 isl_printer *printer;
603
604 if (!list)
605 return;
606
607 printer = isl_printer_to_file(FN(LIST(EL),get_ctx)isl_ast_graft_list_get_ctx(list), stderrstderr);
608 printer = CAT(isl_printer_print_,LIST(BASE))isl_printer_print_ast_graft_list(printer, list);
609 printer = isl_printer_end_line(printer);
610
611 isl_printer_free(printer);
612}