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

source code of polly/lib/External/isl/isl_ast_graft.c