Bug Summary

File:polly/lib/External/isl/isl_ast_graft.c
Warning:line 634, column 4
Value stored to 'graft' is never read

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