Line data Source code
1 : /*
2 : * Copyright 2013-2014 Ecole Normale Superieure
3 : * Copyright 2014 INRIA Rocquencourt
4 : * Copyright 2016 Sven Verdoolaege
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 : */
13 :
14 : #include <isl/id.h>
15 : #include <isl/val.h>
16 : #include <isl/space.h>
17 : #include <isl/set.h>
18 : #include <isl_schedule_band.h>
19 : #include <isl_schedule_private.h>
20 : #include <isl_schedule_node_private.h>
21 :
22 : /* Create a new schedule node in the given schedule, point at the given
23 : * tree with given ancestors and child positions.
24 : * "child_pos" may be NULL if there are no ancestors.
25 : */
26 0 : __isl_give isl_schedule_node *isl_schedule_node_alloc(
27 : __isl_take isl_schedule *schedule, __isl_take isl_schedule_tree *tree,
28 : __isl_take isl_schedule_tree_list *ancestors, int *child_pos)
29 : {
30 : isl_ctx *ctx;
31 : isl_schedule_node *node;
32 : int i, n;
33 :
34 0 : if (!schedule || !tree || !ancestors)
35 : goto error;
36 0 : n = isl_schedule_tree_list_n_schedule_tree(ancestors);
37 0 : if (n > 0 && !child_pos)
38 0 : goto error;
39 0 : ctx = isl_schedule_get_ctx(schedule);
40 0 : node = isl_calloc_type(ctx, isl_schedule_node);
41 0 : if (!node)
42 0 : goto error;
43 0 : node->ref = 1;
44 0 : node->schedule = schedule;
45 0 : node->tree = tree;
46 0 : node->ancestors = ancestors;
47 0 : node->child_pos = isl_alloc_array(ctx, int, n);
48 0 : if (n && !node->child_pos)
49 0 : return isl_schedule_node_free(node);
50 0 : for (i = 0; i < n; ++i)
51 0 : node->child_pos[i] = child_pos[i];
52 :
53 0 : return node;
54 : error:
55 0 : isl_schedule_free(schedule);
56 0 : isl_schedule_tree_free(tree);
57 0 : isl_schedule_tree_list_free(ancestors);
58 0 : return NULL;
59 : }
60 :
61 : /* Return a pointer to the root of a schedule tree with as single
62 : * node a domain node with the given domain.
63 : */
64 0 : __isl_give isl_schedule_node *isl_schedule_node_from_domain(
65 : __isl_take isl_union_set *domain)
66 : {
67 : isl_schedule *schedule;
68 : isl_schedule_node *node;
69 :
70 0 : schedule = isl_schedule_from_domain(domain);
71 0 : node = isl_schedule_get_root(schedule);
72 0 : isl_schedule_free(schedule);
73 :
74 0 : return node;
75 : }
76 :
77 : /* Return a pointer to the root of a schedule tree with as single
78 : * node a extension node with the given extension.
79 : */
80 0 : __isl_give isl_schedule_node *isl_schedule_node_from_extension(
81 : __isl_take isl_union_map *extension)
82 : {
83 : isl_ctx *ctx;
84 : isl_schedule *schedule;
85 : isl_schedule_tree *tree;
86 : isl_schedule_node *node;
87 :
88 0 : if (!extension)
89 0 : return NULL;
90 :
91 0 : ctx = isl_union_map_get_ctx(extension);
92 0 : tree = isl_schedule_tree_from_extension(extension);
93 0 : schedule = isl_schedule_from_schedule_tree(ctx, tree);
94 0 : node = isl_schedule_get_root(schedule);
95 0 : isl_schedule_free(schedule);
96 :
97 0 : return node;
98 : }
99 :
100 : /* Return the isl_ctx to which "node" belongs.
101 : */
102 0 : isl_ctx *isl_schedule_node_get_ctx(__isl_keep isl_schedule_node *node)
103 : {
104 0 : return node ? isl_schedule_get_ctx(node->schedule) : NULL;
105 : }
106 :
107 : /* Return a pointer to the leaf of the schedule into which "node" points.
108 : */
109 0 : __isl_keep isl_schedule_tree *isl_schedule_node_peek_leaf(
110 : __isl_keep isl_schedule_node *node)
111 : {
112 0 : return node ? isl_schedule_peek_leaf(node->schedule) : NULL;
113 : }
114 :
115 : /* Return a copy of the leaf of the schedule into which "node" points.
116 : */
117 0 : __isl_give isl_schedule_tree *isl_schedule_node_get_leaf(
118 : __isl_keep isl_schedule_node *node)
119 : {
120 0 : return isl_schedule_tree_copy(isl_schedule_node_peek_leaf(node));
121 : }
122 :
123 : /* Return the type of the node or isl_schedule_node_error on error.
124 : */
125 0 : enum isl_schedule_node_type isl_schedule_node_get_type(
126 : __isl_keep isl_schedule_node *node)
127 : {
128 0 : return node ? isl_schedule_tree_get_type(node->tree)
129 : : isl_schedule_node_error;
130 : }
131 :
132 : /* Return the type of the parent of "node" or isl_schedule_node_error on error.
133 : */
134 0 : enum isl_schedule_node_type isl_schedule_node_get_parent_type(
135 : __isl_keep isl_schedule_node *node)
136 : {
137 : int pos;
138 : int has_parent;
139 : isl_schedule_tree *parent;
140 : enum isl_schedule_node_type type;
141 :
142 0 : if (!node)
143 0 : return isl_schedule_node_error;
144 0 : has_parent = isl_schedule_node_has_parent(node);
145 0 : if (has_parent < 0)
146 0 : return isl_schedule_node_error;
147 0 : if (!has_parent)
148 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
149 : "node has no parent", return isl_schedule_node_error);
150 :
151 0 : pos = isl_schedule_tree_list_n_schedule_tree(node->ancestors) - 1;
152 0 : parent = isl_schedule_tree_list_get_schedule_tree(node->ancestors, pos);
153 0 : type = isl_schedule_tree_get_type(parent);
154 0 : isl_schedule_tree_free(parent);
155 :
156 0 : return type;
157 : }
158 :
159 : /* Return a copy of the subtree that this node points to.
160 : */
161 0 : __isl_give isl_schedule_tree *isl_schedule_node_get_tree(
162 : __isl_keep isl_schedule_node *node)
163 : {
164 0 : if (!node)
165 0 : return NULL;
166 :
167 0 : return isl_schedule_tree_copy(node->tree);
168 : }
169 :
170 : /* Return a copy of the schedule into which "node" points.
171 : */
172 0 : __isl_give isl_schedule *isl_schedule_node_get_schedule(
173 : __isl_keep isl_schedule_node *node)
174 : {
175 0 : if (!node)
176 0 : return NULL;
177 0 : return isl_schedule_copy(node->schedule);
178 : }
179 :
180 : /* Return a fresh copy of "node".
181 : */
182 0 : __isl_take isl_schedule_node *isl_schedule_node_dup(
183 : __isl_keep isl_schedule_node *node)
184 : {
185 0 : if (!node)
186 0 : return NULL;
187 :
188 0 : return isl_schedule_node_alloc(isl_schedule_copy(node->schedule),
189 : isl_schedule_tree_copy(node->tree),
190 : isl_schedule_tree_list_copy(node->ancestors),
191 : node->child_pos);
192 : }
193 :
194 : /* Return an isl_schedule_node that is equal to "node" and that has only
195 : * a single reference.
196 : */
197 0 : __isl_give isl_schedule_node *isl_schedule_node_cow(
198 : __isl_take isl_schedule_node *node)
199 : {
200 0 : if (!node)
201 0 : return NULL;
202 :
203 0 : if (node->ref == 1)
204 0 : return node;
205 0 : node->ref--;
206 0 : return isl_schedule_node_dup(node);
207 : }
208 :
209 : /* Return a new reference to "node".
210 : */
211 0 : __isl_give isl_schedule_node *isl_schedule_node_copy(
212 : __isl_keep isl_schedule_node *node)
213 : {
214 0 : if (!node)
215 0 : return NULL;
216 :
217 0 : node->ref++;
218 0 : return node;
219 : }
220 :
221 : /* Free "node" and return NULL.
222 : */
223 0 : __isl_null isl_schedule_node *isl_schedule_node_free(
224 : __isl_take isl_schedule_node *node)
225 : {
226 0 : if (!node)
227 0 : return NULL;
228 0 : if (--node->ref > 0)
229 0 : return NULL;
230 :
231 0 : isl_schedule_tree_list_free(node->ancestors);
232 0 : free(node->child_pos);
233 0 : isl_schedule_tree_free(node->tree);
234 0 : isl_schedule_free(node->schedule);
235 0 : free(node);
236 :
237 0 : return NULL;
238 : }
239 :
240 : /* Do "node1" and "node2" point to the same position in the same
241 : * schedule?
242 : */
243 0 : isl_bool isl_schedule_node_is_equal(__isl_keep isl_schedule_node *node1,
244 : __isl_keep isl_schedule_node *node2)
245 : {
246 : int i, n1, n2;
247 :
248 0 : if (!node1 || !node2)
249 0 : return isl_bool_error;
250 0 : if (node1 == node2)
251 0 : return isl_bool_true;
252 0 : if (node1->schedule != node2->schedule)
253 0 : return isl_bool_false;
254 :
255 0 : n1 = isl_schedule_node_get_tree_depth(node1);
256 0 : n2 = isl_schedule_node_get_tree_depth(node2);
257 0 : if (n1 != n2)
258 0 : return isl_bool_false;
259 0 : for (i = 0; i < n1; ++i)
260 0 : if (node1->child_pos[i] != node2->child_pos[i])
261 0 : return isl_bool_false;
262 :
263 0 : return isl_bool_true;
264 : }
265 :
266 : /* Return the number of outer schedule dimensions of "node"
267 : * in its schedule tree.
268 : *
269 : * Return -1 on error.
270 : */
271 0 : int isl_schedule_node_get_schedule_depth(__isl_keep isl_schedule_node *node)
272 : {
273 : int i, n;
274 0 : int depth = 0;
275 :
276 0 : if (!node)
277 0 : return -1;
278 :
279 0 : n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
280 0 : for (i = n - 1; i >= 0; --i) {
281 : isl_schedule_tree *tree;
282 :
283 0 : tree = isl_schedule_tree_list_get_schedule_tree(
284 : node->ancestors, i);
285 0 : if (!tree)
286 0 : return -1;
287 0 : if (tree->type == isl_schedule_node_band)
288 0 : depth += isl_schedule_tree_band_n_member(tree);
289 0 : isl_schedule_tree_free(tree);
290 : }
291 :
292 0 : return depth;
293 : }
294 :
295 : /* Internal data structure for
296 : * isl_schedule_node_get_prefix_schedule_union_pw_multi_aff
297 : *
298 : * "initialized" is set if the filter field has been initialized.
299 : * If "universe_domain" is not set, then the collected filter is intersected
300 : * with the domain of the root domain node.
301 : * "universe_filter" is set if we are only collecting the universes of filters
302 : * "collect_prefix" is set if we are collecting prefixes.
303 : * "filter" collects all outer filters and is NULL until "initialized" is set.
304 : * "prefix" collects all outer band partial schedules (if "collect_prefix"
305 : * is set). If it is used, then it is initialized by the caller
306 : * of collect_filter_prefix to a zero-dimensional function.
307 : */
308 : struct isl_schedule_node_get_filter_prefix_data {
309 : int initialized;
310 : int universe_domain;
311 : int universe_filter;
312 : int collect_prefix;
313 : isl_union_set *filter;
314 : isl_multi_union_pw_aff *prefix;
315 : };
316 :
317 : static int collect_filter_prefix(__isl_keep isl_schedule_tree_list *list,
318 : int n, struct isl_schedule_node_get_filter_prefix_data *data);
319 :
320 : /* Update the filter and prefix information in "data" based on the first "n"
321 : * elements in "list" and the expansion tree root "tree".
322 : *
323 : * We first collect the information from the elements in "list",
324 : * initializing the filter based on the domain of the expansion.
325 : * Then we map the results to the expanded space and combined them
326 : * with the results already in "data".
327 : */
328 0 : static int collect_filter_prefix_expansion(__isl_take isl_schedule_tree *tree,
329 : __isl_keep isl_schedule_tree_list *list, int n,
330 : struct isl_schedule_node_get_filter_prefix_data *data)
331 : {
332 : struct isl_schedule_node_get_filter_prefix_data contracted;
333 : isl_union_pw_multi_aff *c;
334 : isl_union_map *exp, *universe;
335 : isl_union_set *filter;
336 :
337 0 : c = isl_schedule_tree_expansion_get_contraction(tree);
338 0 : exp = isl_schedule_tree_expansion_get_expansion(tree);
339 :
340 0 : contracted.initialized = 1;
341 0 : contracted.universe_domain = data->universe_domain;
342 0 : contracted.universe_filter = data->universe_filter;
343 0 : contracted.collect_prefix = data->collect_prefix;
344 0 : universe = isl_union_map_universe(isl_union_map_copy(exp));
345 0 : filter = isl_union_map_domain(universe);
346 0 : if (data->collect_prefix) {
347 0 : isl_space *space = isl_union_set_get_space(filter);
348 0 : space = isl_space_set_from_params(space);
349 0 : contracted.prefix = isl_multi_union_pw_aff_zero(space);
350 : }
351 0 : contracted.filter = filter;
352 :
353 0 : if (collect_filter_prefix(list, n, &contracted) < 0)
354 0 : contracted.filter = isl_union_set_free(contracted.filter);
355 0 : if (data->collect_prefix) {
356 : isl_multi_union_pw_aff *prefix;
357 :
358 0 : prefix = contracted.prefix;
359 0 : prefix =
360 0 : isl_multi_union_pw_aff_pullback_union_pw_multi_aff(prefix,
361 : isl_union_pw_multi_aff_copy(c));
362 0 : data->prefix = isl_multi_union_pw_aff_flat_range_product(
363 : prefix, data->prefix);
364 : }
365 0 : filter = contracted.filter;
366 0 : if (data->universe_domain)
367 0 : filter = isl_union_set_preimage_union_pw_multi_aff(filter,
368 : isl_union_pw_multi_aff_copy(c));
369 : else
370 0 : filter = isl_union_set_apply(filter, isl_union_map_copy(exp));
371 0 : if (!data->initialized)
372 0 : data->filter = filter;
373 : else
374 0 : data->filter = isl_union_set_intersect(filter, data->filter);
375 0 : data->initialized = 1;
376 :
377 0 : isl_union_pw_multi_aff_free(c);
378 0 : isl_union_map_free(exp);
379 0 : isl_schedule_tree_free(tree);
380 :
381 0 : return 0;
382 : }
383 :
384 : /* Update the filter information in "data" based on the first "n"
385 : * elements in "list" and the extension tree root "tree", in case
386 : * data->universe_domain is set and data->collect_prefix is not.
387 : *
388 : * We collect the universe domain of the elements in "list" and
389 : * add it to the universe range of the extension (intersected
390 : * with the already collected filter, if any).
391 : */
392 0 : static int collect_universe_domain_extension(__isl_take isl_schedule_tree *tree,
393 : __isl_keep isl_schedule_tree_list *list, int n,
394 : struct isl_schedule_node_get_filter_prefix_data *data)
395 : {
396 : struct isl_schedule_node_get_filter_prefix_data data_outer;
397 : isl_union_map *extension;
398 : isl_union_set *filter;
399 :
400 0 : data_outer.initialized = 0;
401 0 : data_outer.universe_domain = 1;
402 0 : data_outer.universe_filter = data->universe_filter;
403 0 : data_outer.collect_prefix = 0;
404 0 : data_outer.filter = NULL;
405 0 : data_outer.prefix = NULL;
406 :
407 0 : if (collect_filter_prefix(list, n, &data_outer) < 0)
408 0 : data_outer.filter = isl_union_set_free(data_outer.filter);
409 :
410 0 : extension = isl_schedule_tree_extension_get_extension(tree);
411 0 : extension = isl_union_map_universe(extension);
412 0 : filter = isl_union_map_range(extension);
413 0 : if (data_outer.initialized)
414 0 : filter = isl_union_set_union(filter, data_outer.filter);
415 0 : if (data->initialized)
416 0 : filter = isl_union_set_intersect(filter, data->filter);
417 :
418 0 : data->filter = filter;
419 :
420 0 : isl_schedule_tree_free(tree);
421 :
422 0 : return 0;
423 : }
424 :
425 : /* Update "data" based on the tree node "tree" in case "data" has
426 : * not been initialized yet.
427 : *
428 : * Return 0 on success and -1 on error.
429 : *
430 : * If "tree" is a filter, then we set data->filter to this filter
431 : * (or its universe).
432 : * If "tree" is a domain, then this means we have reached the root
433 : * of the schedule tree without being able to extract any information.
434 : * We therefore initialize data->filter to the universe of the domain,
435 : * or the domain itself if data->universe_domain is not set.
436 : * If "tree" is a band with at least one member, then we set data->filter
437 : * to the universe of the schedule domain and replace the zero-dimensional
438 : * data->prefix by the band schedule (if data->collect_prefix is set).
439 : */
440 0 : static int collect_filter_prefix_init(__isl_keep isl_schedule_tree *tree,
441 : struct isl_schedule_node_get_filter_prefix_data *data)
442 : {
443 : enum isl_schedule_node_type type;
444 : isl_multi_union_pw_aff *mupa;
445 : isl_union_set *filter;
446 :
447 0 : type = isl_schedule_tree_get_type(tree);
448 0 : switch (type) {
449 : case isl_schedule_node_error:
450 0 : return -1;
451 : case isl_schedule_node_expansion:
452 0 : isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
453 : "should be handled by caller", return -1);
454 : case isl_schedule_node_extension:
455 0 : isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
456 : "cannot handle extension nodes", return -1);
457 : case isl_schedule_node_context:
458 : case isl_schedule_node_leaf:
459 : case isl_schedule_node_guard:
460 : case isl_schedule_node_mark:
461 : case isl_schedule_node_sequence:
462 : case isl_schedule_node_set:
463 0 : return 0;
464 : case isl_schedule_node_domain:
465 0 : filter = isl_schedule_tree_domain_get_domain(tree);
466 0 : if (data->universe_domain)
467 0 : filter = isl_union_set_universe(filter);
468 0 : data->filter = filter;
469 0 : break;
470 : case isl_schedule_node_band:
471 0 : if (isl_schedule_tree_band_n_member(tree) == 0)
472 0 : return 0;
473 0 : mupa = isl_schedule_tree_band_get_partial_schedule(tree);
474 0 : if (data->collect_prefix) {
475 0 : isl_multi_union_pw_aff_free(data->prefix);
476 0 : mupa = isl_multi_union_pw_aff_reset_tuple_id(mupa,
477 : isl_dim_set);
478 0 : data->prefix = isl_multi_union_pw_aff_copy(mupa);
479 : }
480 0 : filter = isl_multi_union_pw_aff_domain(mupa);
481 0 : filter = isl_union_set_universe(filter);
482 0 : data->filter = filter;
483 0 : break;
484 : case isl_schedule_node_filter:
485 0 : filter = isl_schedule_tree_filter_get_filter(tree);
486 0 : if (data->universe_filter)
487 0 : filter = isl_union_set_universe(filter);
488 0 : data->filter = filter;
489 0 : break;
490 : }
491 :
492 0 : if ((data->collect_prefix && !data->prefix) || !data->filter)
493 0 : return -1;
494 :
495 0 : data->initialized = 1;
496 :
497 0 : return 0;
498 : }
499 :
500 : /* Update "data" based on the tree node "tree" in case "data" has
501 : * already been initialized.
502 : *
503 : * Return 0 on success and -1 on error.
504 : *
505 : * If "tree" is a domain and data->universe_domain is not set, then
506 : * intersect data->filter with the domain.
507 : * If "tree" is a filter, then we intersect data->filter with this filter
508 : * (or its universe).
509 : * If "tree" is a band with at least one member and data->collect_prefix
510 : * is set, then we extend data->prefix with the band schedule.
511 : * If "tree" is an extension, then we make sure that we are not collecting
512 : * information on any extended domain elements.
513 : */
514 0 : static int collect_filter_prefix_update(__isl_keep isl_schedule_tree *tree,
515 : struct isl_schedule_node_get_filter_prefix_data *data)
516 : {
517 : enum isl_schedule_node_type type;
518 : isl_multi_union_pw_aff *mupa;
519 : isl_union_set *filter;
520 : isl_union_map *extension;
521 : int empty;
522 :
523 0 : type = isl_schedule_tree_get_type(tree);
524 0 : switch (type) {
525 : case isl_schedule_node_error:
526 0 : return -1;
527 : case isl_schedule_node_expansion:
528 0 : isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
529 : "should be handled by caller", return -1);
530 : case isl_schedule_node_extension:
531 0 : extension = isl_schedule_tree_extension_get_extension(tree);
532 0 : extension = isl_union_map_intersect_range(extension,
533 : isl_union_set_copy(data->filter));
534 0 : empty = isl_union_map_is_empty(extension);
535 0 : isl_union_map_free(extension);
536 0 : if (empty < 0)
537 0 : return -1;
538 0 : if (empty)
539 0 : break;
540 0 : isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
541 : "cannot handle extension nodes", return -1);
542 : case isl_schedule_node_context:
543 : case isl_schedule_node_leaf:
544 : case isl_schedule_node_guard:
545 : case isl_schedule_node_mark:
546 : case isl_schedule_node_sequence:
547 : case isl_schedule_node_set:
548 0 : break;
549 : case isl_schedule_node_domain:
550 0 : if (data->universe_domain)
551 0 : break;
552 0 : filter = isl_schedule_tree_domain_get_domain(tree);
553 0 : data->filter = isl_union_set_intersect(data->filter, filter);
554 0 : break;
555 : case isl_schedule_node_band:
556 0 : if (isl_schedule_tree_band_n_member(tree) == 0)
557 0 : break;
558 0 : if (!data->collect_prefix)
559 0 : break;
560 0 : mupa = isl_schedule_tree_band_get_partial_schedule(tree);
561 0 : data->prefix = isl_multi_union_pw_aff_flat_range_product(mupa,
562 : data->prefix);
563 0 : if (!data->prefix)
564 0 : return -1;
565 0 : break;
566 : case isl_schedule_node_filter:
567 0 : filter = isl_schedule_tree_filter_get_filter(tree);
568 0 : if (data->universe_filter)
569 0 : filter = isl_union_set_universe(filter);
570 0 : data->filter = isl_union_set_intersect(data->filter, filter);
571 0 : if (!data->filter)
572 0 : return -1;
573 0 : break;
574 : }
575 :
576 0 : return 0;
577 : }
578 :
579 : /* Collect filter and/or prefix information from the first "n"
580 : * elements in "list" (which represent the ancestors of a node).
581 : * Store the results in "data".
582 : *
583 : * Extension nodes are only supported if they do not affect the outcome,
584 : * i.e., if we are collecting information on non-extended domain elements,
585 : * or if we are collecting the universe domain (without prefix).
586 : *
587 : * Return 0 on success and -1 on error.
588 : *
589 : * We traverse the list from innermost ancestor (last element)
590 : * to outermost ancestor (first element), calling collect_filter_prefix_init
591 : * on each node as long as we have not been able to extract any information
592 : * yet and collect_filter_prefix_update afterwards.
593 : * If we come across an expansion node, then we interrupt the traversal
594 : * and call collect_filter_prefix_expansion to restart the traversal
595 : * over the remaining ancestors and to combine the results with those
596 : * that have already been collected.
597 : * If we come across an extension node and we are only computing
598 : * the universe domain, then we interrupt the traversal and call
599 : * collect_universe_domain_extension to restart the traversal
600 : * over the remaining ancestors and to combine the results with those
601 : * that have already been collected.
602 : * On successful return, data->initialized will be set since the outermost
603 : * ancestor is a domain node, which always results in an initialization.
604 : */
605 0 : static int collect_filter_prefix(__isl_keep isl_schedule_tree_list *list,
606 : int n, struct isl_schedule_node_get_filter_prefix_data *data)
607 : {
608 : int i;
609 :
610 0 : if (!list)
611 0 : return -1;
612 :
613 0 : for (i = n - 1; i >= 0; --i) {
614 : isl_schedule_tree *tree;
615 : enum isl_schedule_node_type type;
616 : int r;
617 :
618 0 : tree = isl_schedule_tree_list_get_schedule_tree(list, i);
619 0 : if (!tree)
620 0 : return -1;
621 0 : type = isl_schedule_tree_get_type(tree);
622 0 : if (type == isl_schedule_node_expansion)
623 0 : return collect_filter_prefix_expansion(tree, list, i,
624 : data);
625 0 : if (type == isl_schedule_node_extension &&
626 0 : data->universe_domain && !data->collect_prefix)
627 0 : return collect_universe_domain_extension(tree, list, i,
628 : data);
629 0 : if (!data->initialized)
630 0 : r = collect_filter_prefix_init(tree, data);
631 : else
632 0 : r = collect_filter_prefix_update(tree, data);
633 0 : isl_schedule_tree_free(tree);
634 0 : if (r < 0)
635 0 : return -1;
636 : }
637 :
638 0 : return 0;
639 : }
640 :
641 : /* Return the concatenation of the partial schedules of all outer band
642 : * nodes of "node" interesected with all outer filters
643 : * as an isl_multi_union_pw_aff.
644 : * None of the ancestors of "node" may be an extension node, unless
645 : * there is also a filter ancestor that filters out all the extended
646 : * domain elements.
647 : *
648 : * If "node" is pointing at the root of the schedule tree, then
649 : * there are no domain elements reaching the current node, so
650 : * we return an empty result.
651 : *
652 : * We collect all the filters and partial schedules in collect_filter_prefix
653 : * and intersect the domain of the combined schedule with the combined filter.
654 : */
655 : __isl_give isl_multi_union_pw_aff *
656 0 : isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(
657 : __isl_keep isl_schedule_node *node)
658 : {
659 : int n;
660 : isl_space *space;
661 : struct isl_schedule_node_get_filter_prefix_data data;
662 :
663 0 : if (!node)
664 0 : return NULL;
665 :
666 0 : space = isl_schedule_get_space(node->schedule);
667 0 : space = isl_space_set_from_params(space);
668 0 : if (node->tree == node->schedule->root)
669 0 : return isl_multi_union_pw_aff_zero(space);
670 :
671 0 : data.initialized = 0;
672 0 : data.universe_domain = 1;
673 0 : data.universe_filter = 0;
674 0 : data.collect_prefix = 1;
675 0 : data.filter = NULL;
676 0 : data.prefix = isl_multi_union_pw_aff_zero(space);
677 :
678 0 : n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
679 0 : if (collect_filter_prefix(node->ancestors, n, &data) < 0)
680 0 : data.prefix = isl_multi_union_pw_aff_free(data.prefix);
681 :
682 0 : data.prefix = isl_multi_union_pw_aff_intersect_domain(data.prefix,
683 : data.filter);
684 :
685 0 : return data.prefix;
686 : }
687 :
688 : /* Return the concatenation of the partial schedules of all outer band
689 : * nodes of "node" interesected with all outer filters
690 : * as an isl_union_pw_multi_aff.
691 : * None of the ancestors of "node" may be an extension node, unless
692 : * there is also a filter ancestor that filters out all the extended
693 : * domain elements.
694 : *
695 : * If "node" is pointing at the root of the schedule tree, then
696 : * there are no domain elements reaching the current node, so
697 : * we return an empty result.
698 : *
699 : * We collect all the filters and partial schedules in collect_filter_prefix.
700 : * The partial schedules are collected as an isl_multi_union_pw_aff.
701 : * If this isl_multi_union_pw_aff is zero-dimensional, then it does not
702 : * contain any domain information, so we construct the isl_union_pw_multi_aff
703 : * result as a zero-dimensional function on the collected filter.
704 : * Otherwise, we convert the isl_multi_union_pw_aff to
705 : * an isl_multi_union_pw_aff and intersect the domain with the filter.
706 : */
707 : __isl_give isl_union_pw_multi_aff *
708 0 : isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(
709 : __isl_keep isl_schedule_node *node)
710 : {
711 : int n;
712 : isl_space *space;
713 : isl_union_pw_multi_aff *prefix;
714 : struct isl_schedule_node_get_filter_prefix_data data;
715 :
716 0 : if (!node)
717 0 : return NULL;
718 :
719 0 : space = isl_schedule_get_space(node->schedule);
720 0 : if (node->tree == node->schedule->root)
721 0 : return isl_union_pw_multi_aff_empty(space);
722 :
723 0 : space = isl_space_set_from_params(space);
724 0 : data.initialized = 0;
725 0 : data.universe_domain = 1;
726 0 : data.universe_filter = 0;
727 0 : data.collect_prefix = 1;
728 0 : data.filter = NULL;
729 0 : data.prefix = isl_multi_union_pw_aff_zero(space);
730 :
731 0 : n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
732 0 : if (collect_filter_prefix(node->ancestors, n, &data) < 0)
733 0 : data.prefix = isl_multi_union_pw_aff_free(data.prefix);
734 :
735 0 : if (data.prefix &&
736 0 : isl_multi_union_pw_aff_dim(data.prefix, isl_dim_set) == 0) {
737 0 : isl_multi_union_pw_aff_free(data.prefix);
738 0 : prefix = isl_union_pw_multi_aff_from_domain(data.filter);
739 : } else {
740 0 : prefix =
741 0 : isl_union_pw_multi_aff_from_multi_union_pw_aff(data.prefix);
742 0 : prefix = isl_union_pw_multi_aff_intersect_domain(prefix,
743 : data.filter);
744 : }
745 :
746 0 : return prefix;
747 : }
748 :
749 : /* Return the concatenation of the partial schedules of all outer band
750 : * nodes of "node" interesected with all outer filters
751 : * as an isl_union_map.
752 : */
753 0 : __isl_give isl_union_map *isl_schedule_node_get_prefix_schedule_union_map(
754 : __isl_keep isl_schedule_node *node)
755 : {
756 : isl_union_pw_multi_aff *upma;
757 :
758 0 : upma = isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(node);
759 0 : return isl_union_map_from_union_pw_multi_aff(upma);
760 : }
761 :
762 : /* Return the concatenation of the partial schedules of all outer band
763 : * nodes of "node" intersected with all outer domain constraints.
764 : * None of the ancestors of "node" may be an extension node, unless
765 : * there is also a filter ancestor that filters out all the extended
766 : * domain elements.
767 : *
768 : * Essentially, this function intersects the domain of the output
769 : * of isl_schedule_node_get_prefix_schedule_union_map with the output
770 : * of isl_schedule_node_get_domain, except that it only traverses
771 : * the ancestors of "node" once.
772 : */
773 0 : __isl_give isl_union_map *isl_schedule_node_get_prefix_schedule_relation(
774 : __isl_keep isl_schedule_node *node)
775 : {
776 : int n;
777 : isl_space *space;
778 : isl_union_map *prefix;
779 : struct isl_schedule_node_get_filter_prefix_data data;
780 :
781 0 : if (!node)
782 0 : return NULL;
783 :
784 0 : space = isl_schedule_get_space(node->schedule);
785 0 : if (node->tree == node->schedule->root)
786 0 : return isl_union_map_empty(space);
787 :
788 0 : space = isl_space_set_from_params(space);
789 0 : data.initialized = 0;
790 0 : data.universe_domain = 0;
791 0 : data.universe_filter = 0;
792 0 : data.collect_prefix = 1;
793 0 : data.filter = NULL;
794 0 : data.prefix = isl_multi_union_pw_aff_zero(space);
795 :
796 0 : n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
797 0 : if (collect_filter_prefix(node->ancestors, n, &data) < 0)
798 0 : data.prefix = isl_multi_union_pw_aff_free(data.prefix);
799 :
800 0 : if (data.prefix &&
801 0 : isl_multi_union_pw_aff_dim(data.prefix, isl_dim_set) == 0) {
802 0 : isl_multi_union_pw_aff_free(data.prefix);
803 0 : prefix = isl_union_map_from_domain(data.filter);
804 : } else {
805 0 : prefix = isl_union_map_from_multi_union_pw_aff(data.prefix);
806 0 : prefix = isl_union_map_intersect_domain(prefix, data.filter);
807 : }
808 :
809 0 : return prefix;
810 : }
811 :
812 : /* Return the domain elements that reach "node".
813 : *
814 : * If "node" is pointing at the root of the schedule tree, then
815 : * there are no domain elements reaching the current node, so
816 : * we return an empty result.
817 : * None of the ancestors of "node" may be an extension node, unless
818 : * there is also a filter ancestor that filters out all the extended
819 : * domain elements.
820 : *
821 : * Otherwise, we collect all filters reaching the node,
822 : * intersected with the root domain in collect_filter_prefix.
823 : */
824 0 : __isl_give isl_union_set *isl_schedule_node_get_domain(
825 : __isl_keep isl_schedule_node *node)
826 : {
827 : int n;
828 : struct isl_schedule_node_get_filter_prefix_data data;
829 :
830 0 : if (!node)
831 0 : return NULL;
832 :
833 0 : if (node->tree == node->schedule->root) {
834 : isl_space *space;
835 :
836 0 : space = isl_schedule_get_space(node->schedule);
837 0 : return isl_union_set_empty(space);
838 : }
839 :
840 0 : data.initialized = 0;
841 0 : data.universe_domain = 0;
842 0 : data.universe_filter = 0;
843 0 : data.collect_prefix = 0;
844 0 : data.filter = NULL;
845 0 : data.prefix = NULL;
846 :
847 0 : n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
848 0 : if (collect_filter_prefix(node->ancestors, n, &data) < 0)
849 0 : data.filter = isl_union_set_free(data.filter);
850 :
851 0 : return data.filter;
852 : }
853 :
854 : /* Return the union of universe sets of the domain elements that reach "node".
855 : *
856 : * If "node" is pointing at the root of the schedule tree, then
857 : * there are no domain elements reaching the current node, so
858 : * we return an empty result.
859 : *
860 : * Otherwise, we collect the universes of all filters reaching the node
861 : * in collect_filter_prefix.
862 : */
863 0 : __isl_give isl_union_set *isl_schedule_node_get_universe_domain(
864 : __isl_keep isl_schedule_node *node)
865 : {
866 : int n;
867 : struct isl_schedule_node_get_filter_prefix_data data;
868 :
869 0 : if (!node)
870 0 : return NULL;
871 :
872 0 : if (node->tree == node->schedule->root) {
873 : isl_space *space;
874 :
875 0 : space = isl_schedule_get_space(node->schedule);
876 0 : return isl_union_set_empty(space);
877 : }
878 :
879 0 : data.initialized = 0;
880 0 : data.universe_domain = 1;
881 0 : data.universe_filter = 1;
882 0 : data.collect_prefix = 0;
883 0 : data.filter = NULL;
884 0 : data.prefix = NULL;
885 :
886 0 : n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
887 0 : if (collect_filter_prefix(node->ancestors, n, &data) < 0)
888 0 : data.filter = isl_union_set_free(data.filter);
889 :
890 0 : return data.filter;
891 : }
892 :
893 : /* Return the subtree schedule of "node".
894 : *
895 : * Since isl_schedule_tree_get_subtree_schedule_union_map does not handle
896 : * trees that do not contain any schedule information, we first
897 : * move down to the first relevant descendant and handle leaves ourselves.
898 : *
899 : * If the subtree rooted at "node" contains any expansion nodes, then
900 : * the returned subtree schedule is formulated in terms of the expanded
901 : * domains.
902 : * The subtree is not allowed to contain any extension nodes.
903 : */
904 0 : __isl_give isl_union_map *isl_schedule_node_get_subtree_schedule_union_map(
905 : __isl_keep isl_schedule_node *node)
906 : {
907 : isl_schedule_tree *tree, *leaf;
908 : isl_union_map *umap;
909 :
910 0 : tree = isl_schedule_node_get_tree(node);
911 0 : leaf = isl_schedule_node_peek_leaf(node);
912 0 : tree = isl_schedule_tree_first_schedule_descendant(tree, leaf);
913 0 : if (!tree)
914 0 : return NULL;
915 0 : if (tree == leaf) {
916 : isl_union_set *domain;
917 0 : domain = isl_schedule_node_get_universe_domain(node);
918 0 : isl_schedule_tree_free(tree);
919 0 : return isl_union_map_from_domain(domain);
920 : }
921 :
922 0 : umap = isl_schedule_tree_get_subtree_schedule_union_map(tree);
923 0 : isl_schedule_tree_free(tree);
924 0 : return umap;
925 : }
926 :
927 : /* Return the number of ancestors of "node" in its schedule tree.
928 : */
929 0 : int isl_schedule_node_get_tree_depth(__isl_keep isl_schedule_node *node)
930 : {
931 0 : if (!node)
932 0 : return -1;
933 0 : return isl_schedule_tree_list_n_schedule_tree(node->ancestors);
934 : }
935 :
936 : /* Does "node" have a parent?
937 : *
938 : * That is, does it point to any node of the schedule other than the root?
939 : */
940 0 : isl_bool isl_schedule_node_has_parent(__isl_keep isl_schedule_node *node)
941 : {
942 0 : if (!node)
943 0 : return isl_bool_error;
944 0 : if (!node->ancestors)
945 0 : return isl_bool_error;
946 :
947 0 : return isl_schedule_tree_list_n_schedule_tree(node->ancestors) != 0;
948 : }
949 :
950 : /* Return the position of "node" among the children of its parent.
951 : */
952 0 : int isl_schedule_node_get_child_position(__isl_keep isl_schedule_node *node)
953 : {
954 : int n;
955 : int has_parent;
956 :
957 0 : if (!node)
958 0 : return -1;
959 0 : has_parent = isl_schedule_node_has_parent(node);
960 0 : if (has_parent < 0)
961 0 : return -1;
962 0 : if (!has_parent)
963 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
964 : "node has no parent", return -1);
965 :
966 0 : n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
967 0 : return node->child_pos[n - 1];
968 : }
969 :
970 : /* Does the parent (if any) of "node" have any children with a smaller child
971 : * position than this one?
972 : */
973 0 : isl_bool isl_schedule_node_has_previous_sibling(
974 : __isl_keep isl_schedule_node *node)
975 : {
976 : int n;
977 : isl_bool has_parent;
978 :
979 0 : if (!node)
980 0 : return isl_bool_error;
981 0 : has_parent = isl_schedule_node_has_parent(node);
982 0 : if (has_parent < 0 || !has_parent)
983 0 : return has_parent;
984 :
985 0 : n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
986 :
987 0 : return node->child_pos[n - 1] > 0;
988 : }
989 :
990 : /* Does the parent (if any) of "node" have any children with a greater child
991 : * position than this one?
992 : */
993 0 : isl_bool isl_schedule_node_has_next_sibling(__isl_keep isl_schedule_node *node)
994 : {
995 : int n, n_child;
996 : isl_bool has_parent;
997 : isl_schedule_tree *tree;
998 :
999 0 : if (!node)
1000 0 : return isl_bool_error;
1001 0 : has_parent = isl_schedule_node_has_parent(node);
1002 0 : if (has_parent < 0 || !has_parent)
1003 0 : return has_parent;
1004 :
1005 0 : n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
1006 0 : tree = isl_schedule_tree_list_get_schedule_tree(node->ancestors, n - 1);
1007 0 : if (!tree)
1008 0 : return isl_bool_error;
1009 0 : n_child = isl_schedule_tree_list_n_schedule_tree(tree->children);
1010 0 : isl_schedule_tree_free(tree);
1011 :
1012 0 : return node->child_pos[n - 1] + 1 < n_child;
1013 : }
1014 :
1015 : /* Does "node" have any children?
1016 : *
1017 : * Any node other than the leaf nodes is considered to have at least
1018 : * one child, even if the corresponding isl_schedule_tree does not
1019 : * have any children.
1020 : */
1021 0 : isl_bool isl_schedule_node_has_children(__isl_keep isl_schedule_node *node)
1022 : {
1023 0 : if (!node)
1024 0 : return isl_bool_error;
1025 0 : return !isl_schedule_tree_is_leaf(node->tree);
1026 : }
1027 :
1028 : /* Return the number of children of "node"?
1029 : *
1030 : * Any node other than the leaf nodes is considered to have at least
1031 : * one child, even if the corresponding isl_schedule_tree does not
1032 : * have any children. That is, the number of children of "node" is
1033 : * only zero if its tree is the explicit empty tree. Otherwise,
1034 : * if the isl_schedule_tree has any children, then it is equal
1035 : * to the number of children of "node". If it has zero children,
1036 : * then "node" still has a leaf node as child.
1037 : */
1038 0 : int isl_schedule_node_n_children(__isl_keep isl_schedule_node *node)
1039 : {
1040 : int n;
1041 :
1042 0 : if (!node)
1043 0 : return -1;
1044 :
1045 0 : if (isl_schedule_tree_is_leaf(node->tree))
1046 0 : return 0;
1047 :
1048 0 : n = isl_schedule_tree_n_children(node->tree);
1049 0 : if (n == 0)
1050 0 : return 1;
1051 :
1052 0 : return n;
1053 : }
1054 :
1055 : /* Move the "node" pointer to the ancestor of the given generation
1056 : * of the node it currently points to, where generation 0 is the node
1057 : * itself and generation 1 is its parent.
1058 : */
1059 0 : __isl_give isl_schedule_node *isl_schedule_node_ancestor(
1060 : __isl_take isl_schedule_node *node, int generation)
1061 : {
1062 : int n;
1063 : isl_schedule_tree *tree;
1064 :
1065 0 : if (!node)
1066 0 : return NULL;
1067 0 : if (generation == 0)
1068 0 : return node;
1069 0 : n = isl_schedule_node_get_tree_depth(node);
1070 0 : if (n < 0)
1071 0 : return isl_schedule_node_free(node);
1072 0 : if (generation < 0 || generation > n)
1073 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
1074 : "generation out of bounds",
1075 : return isl_schedule_node_free(node));
1076 0 : node = isl_schedule_node_cow(node);
1077 0 : if (!node)
1078 0 : return NULL;
1079 :
1080 0 : tree = isl_schedule_tree_list_get_schedule_tree(node->ancestors,
1081 : n - generation);
1082 0 : isl_schedule_tree_free(node->tree);
1083 0 : node->tree = tree;
1084 0 : node->ancestors = isl_schedule_tree_list_drop(node->ancestors,
1085 0 : n - generation, generation);
1086 0 : if (!node->ancestors || !node->tree)
1087 0 : return isl_schedule_node_free(node);
1088 :
1089 0 : return node;
1090 : }
1091 :
1092 : /* Move the "node" pointer to the parent of the node it currently points to.
1093 : */
1094 0 : __isl_give isl_schedule_node *isl_schedule_node_parent(
1095 : __isl_take isl_schedule_node *node)
1096 : {
1097 0 : if (!node)
1098 0 : return NULL;
1099 0 : if (!isl_schedule_node_has_parent(node))
1100 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
1101 : "node has no parent",
1102 : return isl_schedule_node_free(node));
1103 0 : return isl_schedule_node_ancestor(node, 1);
1104 : }
1105 :
1106 : /* Move the "node" pointer to the root of its schedule tree.
1107 : */
1108 0 : __isl_give isl_schedule_node *isl_schedule_node_root(
1109 : __isl_take isl_schedule_node *node)
1110 : {
1111 : int n;
1112 :
1113 0 : if (!node)
1114 0 : return NULL;
1115 0 : n = isl_schedule_node_get_tree_depth(node);
1116 0 : if (n < 0)
1117 0 : return isl_schedule_node_free(node);
1118 0 : return isl_schedule_node_ancestor(node, n);
1119 : }
1120 :
1121 : /* Move the "node" pointer to the child at position "pos" of the node
1122 : * it currently points to.
1123 : */
1124 0 : __isl_give isl_schedule_node *isl_schedule_node_child(
1125 : __isl_take isl_schedule_node *node, int pos)
1126 : {
1127 : int n;
1128 : isl_ctx *ctx;
1129 : isl_schedule_tree *tree;
1130 : int *child_pos;
1131 :
1132 0 : node = isl_schedule_node_cow(node);
1133 0 : if (!node)
1134 0 : return NULL;
1135 0 : if (!isl_schedule_node_has_children(node))
1136 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
1137 : "node has no children",
1138 : return isl_schedule_node_free(node));
1139 :
1140 0 : ctx = isl_schedule_node_get_ctx(node);
1141 0 : n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
1142 0 : child_pos = isl_realloc_array(ctx, node->child_pos, int, n + 1);
1143 0 : if (!child_pos)
1144 0 : return isl_schedule_node_free(node);
1145 0 : node->child_pos = child_pos;
1146 0 : node->child_pos[n] = pos;
1147 :
1148 0 : node->ancestors = isl_schedule_tree_list_add(node->ancestors,
1149 0 : isl_schedule_tree_copy(node->tree));
1150 0 : tree = node->tree;
1151 0 : if (isl_schedule_tree_has_children(tree))
1152 0 : tree = isl_schedule_tree_get_child(tree, pos);
1153 : else
1154 0 : tree = isl_schedule_node_get_leaf(node);
1155 0 : isl_schedule_tree_free(node->tree);
1156 0 : node->tree = tree;
1157 :
1158 0 : if (!node->tree || !node->ancestors)
1159 0 : return isl_schedule_node_free(node);
1160 :
1161 0 : return node;
1162 : }
1163 :
1164 : /* Move the "node" pointer to the first child of the node
1165 : * it currently points to.
1166 : */
1167 0 : __isl_give isl_schedule_node *isl_schedule_node_first_child(
1168 : __isl_take isl_schedule_node *node)
1169 : {
1170 0 : return isl_schedule_node_child(node, 0);
1171 : }
1172 :
1173 : /* Move the "node" pointer to the child of this node's parent in
1174 : * the previous child position.
1175 : */
1176 0 : __isl_give isl_schedule_node *isl_schedule_node_previous_sibling(
1177 : __isl_take isl_schedule_node *node)
1178 : {
1179 : int n;
1180 : isl_schedule_tree *parent, *tree;
1181 :
1182 0 : node = isl_schedule_node_cow(node);
1183 0 : if (!node)
1184 0 : return NULL;
1185 0 : if (!isl_schedule_node_has_previous_sibling(node))
1186 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
1187 : "node has no previous sibling",
1188 : return isl_schedule_node_free(node));
1189 :
1190 0 : n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
1191 0 : parent = isl_schedule_tree_list_get_schedule_tree(node->ancestors,
1192 : n - 1);
1193 0 : if (!parent)
1194 0 : return isl_schedule_node_free(node);
1195 0 : node->child_pos[n - 1]--;
1196 0 : tree = isl_schedule_tree_list_get_schedule_tree(parent->children,
1197 0 : node->child_pos[n - 1]);
1198 0 : isl_schedule_tree_free(parent);
1199 0 : if (!tree)
1200 0 : return isl_schedule_node_free(node);
1201 0 : isl_schedule_tree_free(node->tree);
1202 0 : node->tree = tree;
1203 :
1204 0 : return node;
1205 : }
1206 :
1207 : /* Move the "node" pointer to the child of this node's parent in
1208 : * the next child position.
1209 : */
1210 0 : __isl_give isl_schedule_node *isl_schedule_node_next_sibling(
1211 : __isl_take isl_schedule_node *node)
1212 : {
1213 : int n;
1214 : isl_schedule_tree *parent, *tree;
1215 :
1216 0 : node = isl_schedule_node_cow(node);
1217 0 : if (!node)
1218 0 : return NULL;
1219 0 : if (!isl_schedule_node_has_next_sibling(node))
1220 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
1221 : "node has no next sibling",
1222 : return isl_schedule_node_free(node));
1223 :
1224 0 : n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
1225 0 : parent = isl_schedule_tree_list_get_schedule_tree(node->ancestors,
1226 : n - 1);
1227 0 : if (!parent)
1228 0 : return isl_schedule_node_free(node);
1229 0 : node->child_pos[n - 1]++;
1230 0 : tree = isl_schedule_tree_list_get_schedule_tree(parent->children,
1231 0 : node->child_pos[n - 1]);
1232 0 : isl_schedule_tree_free(parent);
1233 0 : if (!tree)
1234 0 : return isl_schedule_node_free(node);
1235 0 : isl_schedule_tree_free(node->tree);
1236 0 : node->tree = tree;
1237 :
1238 0 : return node;
1239 : }
1240 :
1241 : /* Return a copy to the child at position "pos" of "node".
1242 : */
1243 0 : __isl_give isl_schedule_node *isl_schedule_node_get_child(
1244 : __isl_keep isl_schedule_node *node, int pos)
1245 : {
1246 0 : return isl_schedule_node_child(isl_schedule_node_copy(node), pos);
1247 : }
1248 :
1249 : /* Traverse the descendant of "node" in depth-first order, including
1250 : * "node" itself. Call "enter" whenever a node is entered and "leave"
1251 : * whenever a node is left. The callback "enter" is responsible
1252 : * for moving to the deepest initial subtree of its argument that
1253 : * should be traversed.
1254 : */
1255 0 : static __isl_give isl_schedule_node *traverse(
1256 : __isl_take isl_schedule_node *node,
1257 : __isl_give isl_schedule_node *(*enter)(
1258 : __isl_take isl_schedule_node *node, void *user),
1259 : __isl_give isl_schedule_node *(*leave)(
1260 : __isl_take isl_schedule_node *node, void *user),
1261 : void *user)
1262 : {
1263 : int depth;
1264 :
1265 0 : if (!node)
1266 0 : return NULL;
1267 :
1268 0 : depth = isl_schedule_node_get_tree_depth(node);
1269 : do {
1270 0 : node = enter(node, user);
1271 0 : node = leave(node, user);
1272 0 : while (node && isl_schedule_node_get_tree_depth(node) > depth &&
1273 0 : !isl_schedule_node_has_next_sibling(node)) {
1274 0 : node = isl_schedule_node_parent(node);
1275 0 : node = leave(node, user);
1276 : }
1277 0 : if (node && isl_schedule_node_get_tree_depth(node) > depth)
1278 0 : node = isl_schedule_node_next_sibling(node);
1279 0 : } while (node && isl_schedule_node_get_tree_depth(node) > depth);
1280 :
1281 0 : return node;
1282 : }
1283 :
1284 : /* Internal data structure for isl_schedule_node_foreach_descendant_top_down.
1285 : *
1286 : * "fn" is the user-specified callback function.
1287 : * "user" is the user-specified argument for the callback.
1288 : */
1289 : struct isl_schedule_node_preorder_data {
1290 : isl_bool (*fn)(__isl_keep isl_schedule_node *node, void *user);
1291 : void *user;
1292 : };
1293 :
1294 : /* Callback for "traverse" to enter a node and to move
1295 : * to the deepest initial subtree that should be traversed
1296 : * for use in a preorder visit.
1297 : *
1298 : * If the user callback returns a negative value, then we abort
1299 : * the traversal. If this callback returns zero, then we skip
1300 : * the subtree rooted at the current node. Otherwise, we move
1301 : * down to the first child and repeat the process until a leaf
1302 : * is reached.
1303 : */
1304 0 : static __isl_give isl_schedule_node *preorder_enter(
1305 : __isl_take isl_schedule_node *node, void *user)
1306 : {
1307 0 : struct isl_schedule_node_preorder_data *data = user;
1308 :
1309 0 : if (!node)
1310 0 : return NULL;
1311 :
1312 : do {
1313 : isl_bool r;
1314 :
1315 0 : r = data->fn(node, data->user);
1316 0 : if (r < 0)
1317 0 : return isl_schedule_node_free(node);
1318 0 : if (r == isl_bool_false)
1319 0 : return node;
1320 0 : } while (isl_schedule_node_has_children(node) &&
1321 0 : (node = isl_schedule_node_first_child(node)) != NULL);
1322 :
1323 0 : return node;
1324 : }
1325 :
1326 : /* Callback for "traverse" to leave a node
1327 : * for use in a preorder visit.
1328 : * Since we already visited the node when we entered it,
1329 : * we do not need to do anything here.
1330 : */
1331 0 : static __isl_give isl_schedule_node *preorder_leave(
1332 : __isl_take isl_schedule_node *node, void *user)
1333 : {
1334 0 : return node;
1335 : }
1336 :
1337 : /* Traverse the descendants of "node" (including the node itself)
1338 : * in depth first preorder.
1339 : *
1340 : * If "fn" returns isl_bool_error on any of the nodes,
1341 : * then the traversal is aborted.
1342 : * If "fn" returns isl_bool_false on any of the nodes, then the subtree rooted
1343 : * at that node is skipped.
1344 : *
1345 : * Return isl_stat_ok on success and isl_stat_error on failure.
1346 : */
1347 0 : isl_stat isl_schedule_node_foreach_descendant_top_down(
1348 : __isl_keep isl_schedule_node *node,
1349 : isl_bool (*fn)(__isl_keep isl_schedule_node *node, void *user),
1350 : void *user)
1351 : {
1352 0 : struct isl_schedule_node_preorder_data data = { fn, user };
1353 :
1354 0 : node = isl_schedule_node_copy(node);
1355 0 : node = traverse(node, &preorder_enter, &preorder_leave, &data);
1356 0 : isl_schedule_node_free(node);
1357 :
1358 0 : return node ? isl_stat_ok : isl_stat_error;
1359 : }
1360 :
1361 : /* Internal data structure for isl_schedule_node_every_descendant.
1362 : *
1363 : * "test" is the user-specified callback function.
1364 : * "user" is the user-specified callback function argument.
1365 : *
1366 : * "failed" is initialized to 0 and set to 1 if "test" fails
1367 : * on any node.
1368 : */
1369 : struct isl_union_map_every_data {
1370 : isl_bool (*test)(__isl_keep isl_schedule_node *node, void *user);
1371 : void *user;
1372 : int failed;
1373 : };
1374 :
1375 : /* isl_schedule_node_foreach_descendant_top_down callback
1376 : * that sets data->failed if data->test returns false and
1377 : * subsequently aborts the traversal.
1378 : */
1379 0 : static isl_bool call_every(__isl_keep isl_schedule_node *node, void *user)
1380 : {
1381 0 : struct isl_union_map_every_data *data = user;
1382 : isl_bool r;
1383 :
1384 0 : r = data->test(node, data->user);
1385 0 : if (r < 0)
1386 0 : return isl_bool_error;
1387 0 : if (r)
1388 0 : return isl_bool_true;
1389 0 : data->failed = 1;
1390 0 : return isl_bool_error;
1391 : }
1392 :
1393 : /* Does "test" succeed on every descendant of "node" (including "node" itself)?
1394 : */
1395 0 : isl_bool isl_schedule_node_every_descendant(__isl_keep isl_schedule_node *node,
1396 : isl_bool (*test)(__isl_keep isl_schedule_node *node, void *user),
1397 : void *user)
1398 : {
1399 0 : struct isl_union_map_every_data data = { test, user, 0 };
1400 : isl_stat r;
1401 :
1402 0 : r = isl_schedule_node_foreach_descendant_top_down(node, &call_every,
1403 : &data);
1404 0 : if (r >= 0)
1405 0 : return isl_bool_true;
1406 0 : if (data.failed)
1407 0 : return isl_bool_false;
1408 0 : return isl_bool_error;
1409 : }
1410 :
1411 : /* Internal data structure for isl_schedule_node_map_descendant_bottom_up.
1412 : *
1413 : * "fn" is the user-specified callback function.
1414 : * "user" is the user-specified argument for the callback.
1415 : */
1416 : struct isl_schedule_node_postorder_data {
1417 : __isl_give isl_schedule_node *(*fn)(__isl_take isl_schedule_node *node,
1418 : void *user);
1419 : void *user;
1420 : };
1421 :
1422 : /* Callback for "traverse" to enter a node and to move
1423 : * to the deepest initial subtree that should be traversed
1424 : * for use in a postorder visit.
1425 : *
1426 : * Since we are performing a postorder visit, we only need
1427 : * to move to the deepest initial leaf here.
1428 : */
1429 0 : static __isl_give isl_schedule_node *postorder_enter(
1430 : __isl_take isl_schedule_node *node, void *user)
1431 : {
1432 0 : while (node && isl_schedule_node_has_children(node))
1433 0 : node = isl_schedule_node_first_child(node);
1434 :
1435 0 : return node;
1436 : }
1437 :
1438 : /* Callback for "traverse" to leave a node
1439 : * for use in a postorder visit.
1440 : *
1441 : * Since we are performing a postorder visit, we need
1442 : * to call the user callback here.
1443 : */
1444 0 : static __isl_give isl_schedule_node *postorder_leave(
1445 : __isl_take isl_schedule_node *node, void *user)
1446 : {
1447 0 : struct isl_schedule_node_postorder_data *data = user;
1448 :
1449 0 : return data->fn(node, data->user);
1450 : }
1451 :
1452 : /* Traverse the descendants of "node" (including the node itself)
1453 : * in depth first postorder, allowing the user to modify the visited node.
1454 : * The traversal continues from the node returned by the callback function.
1455 : * It is the responsibility of the user to ensure that this does not
1456 : * lead to an infinite loop. It is safest to always return a pointer
1457 : * to the same position (same ancestors and child positions) as the input node.
1458 : */
1459 0 : __isl_give isl_schedule_node *isl_schedule_node_map_descendant_bottom_up(
1460 : __isl_take isl_schedule_node *node,
1461 : __isl_give isl_schedule_node *(*fn)(__isl_take isl_schedule_node *node,
1462 : void *user), void *user)
1463 : {
1464 0 : struct isl_schedule_node_postorder_data data = { fn, user };
1465 :
1466 0 : return traverse(node, &postorder_enter, &postorder_leave, &data);
1467 : }
1468 :
1469 : /* Traverse the ancestors of "node" from the root down to and including
1470 : * the parent of "node", calling "fn" on each of them.
1471 : *
1472 : * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1473 : *
1474 : * Return 0 on success and -1 on failure.
1475 : */
1476 0 : isl_stat isl_schedule_node_foreach_ancestor_top_down(
1477 : __isl_keep isl_schedule_node *node,
1478 : isl_stat (*fn)(__isl_keep isl_schedule_node *node, void *user),
1479 : void *user)
1480 : {
1481 : int i, n;
1482 :
1483 0 : if (!node)
1484 0 : return isl_stat_error;
1485 :
1486 0 : n = isl_schedule_node_get_tree_depth(node);
1487 0 : for (i = 0; i < n; ++i) {
1488 : isl_schedule_node *ancestor;
1489 : isl_stat r;
1490 :
1491 0 : ancestor = isl_schedule_node_copy(node);
1492 0 : ancestor = isl_schedule_node_ancestor(ancestor, n - i);
1493 0 : r = fn(ancestor, user);
1494 0 : isl_schedule_node_free(ancestor);
1495 0 : if (r < 0)
1496 0 : return isl_stat_error;
1497 : }
1498 :
1499 0 : return isl_stat_ok;
1500 : }
1501 :
1502 : /* Is any node in the subtree rooted at "node" anchored?
1503 : * That is, do any of these nodes reference the outer band nodes?
1504 : */
1505 0 : isl_bool isl_schedule_node_is_subtree_anchored(
1506 : __isl_keep isl_schedule_node *node)
1507 : {
1508 0 : if (!node)
1509 0 : return isl_bool_error;
1510 0 : return isl_schedule_tree_is_subtree_anchored(node->tree);
1511 : }
1512 :
1513 : /* Return the number of members in the given band node.
1514 : */
1515 0 : unsigned isl_schedule_node_band_n_member(__isl_keep isl_schedule_node *node)
1516 : {
1517 0 : return node ? isl_schedule_tree_band_n_member(node->tree) : 0;
1518 : }
1519 :
1520 : /* Is the band member at position "pos" of the band node "node"
1521 : * marked coincident?
1522 : */
1523 0 : isl_bool isl_schedule_node_band_member_get_coincident(
1524 : __isl_keep isl_schedule_node *node, int pos)
1525 : {
1526 0 : if (!node)
1527 0 : return isl_bool_error;
1528 0 : return isl_schedule_tree_band_member_get_coincident(node->tree, pos);
1529 : }
1530 :
1531 : /* Mark the band member at position "pos" the band node "node"
1532 : * as being coincident or not according to "coincident".
1533 : */
1534 0 : __isl_give isl_schedule_node *isl_schedule_node_band_member_set_coincident(
1535 : __isl_take isl_schedule_node *node, int pos, int coincident)
1536 : {
1537 : int c;
1538 : isl_schedule_tree *tree;
1539 :
1540 0 : if (!node)
1541 0 : return NULL;
1542 0 : c = isl_schedule_node_band_member_get_coincident(node, pos);
1543 0 : if (c == coincident)
1544 0 : return node;
1545 :
1546 0 : tree = isl_schedule_tree_copy(node->tree);
1547 0 : tree = isl_schedule_tree_band_member_set_coincident(tree, pos,
1548 : coincident);
1549 0 : node = isl_schedule_node_graft_tree(node, tree);
1550 :
1551 0 : return node;
1552 : }
1553 :
1554 : /* Is the band node "node" marked permutable?
1555 : */
1556 0 : isl_bool isl_schedule_node_band_get_permutable(
1557 : __isl_keep isl_schedule_node *node)
1558 : {
1559 0 : if (!node)
1560 0 : return isl_bool_error;
1561 :
1562 0 : return isl_schedule_tree_band_get_permutable(node->tree);
1563 : }
1564 :
1565 : /* Mark the band node "node" permutable or not according to "permutable"?
1566 : */
1567 0 : __isl_give isl_schedule_node *isl_schedule_node_band_set_permutable(
1568 : __isl_take isl_schedule_node *node, int permutable)
1569 : {
1570 : isl_schedule_tree *tree;
1571 :
1572 0 : if (!node)
1573 0 : return NULL;
1574 0 : if (isl_schedule_node_band_get_permutable(node) == permutable)
1575 0 : return node;
1576 :
1577 0 : tree = isl_schedule_tree_copy(node->tree);
1578 0 : tree = isl_schedule_tree_band_set_permutable(tree, permutable);
1579 0 : node = isl_schedule_node_graft_tree(node, tree);
1580 :
1581 0 : return node;
1582 : }
1583 :
1584 : /* Return the schedule space of the band node.
1585 : */
1586 0 : __isl_give isl_space *isl_schedule_node_band_get_space(
1587 : __isl_keep isl_schedule_node *node)
1588 : {
1589 0 : if (!node)
1590 0 : return NULL;
1591 :
1592 0 : return isl_schedule_tree_band_get_space(node->tree);
1593 : }
1594 :
1595 : /* Return the schedule of the band node in isolation.
1596 : */
1597 0 : __isl_give isl_multi_union_pw_aff *isl_schedule_node_band_get_partial_schedule(
1598 : __isl_keep isl_schedule_node *node)
1599 : {
1600 0 : if (!node)
1601 0 : return NULL;
1602 :
1603 0 : return isl_schedule_tree_band_get_partial_schedule(node->tree);
1604 : }
1605 :
1606 : /* Return the schedule of the band node in isolation in the form of
1607 : * an isl_union_map.
1608 : *
1609 : * If the band does not have any members, then we construct a universe map
1610 : * with the universe of the domain elements reaching the node as domain.
1611 : * Otherwise, we extract an isl_multi_union_pw_aff representation and
1612 : * convert that to an isl_union_map.
1613 : */
1614 0 : __isl_give isl_union_map *isl_schedule_node_band_get_partial_schedule_union_map(
1615 : __isl_keep isl_schedule_node *node)
1616 : {
1617 : isl_multi_union_pw_aff *mupa;
1618 :
1619 0 : if (!node)
1620 0 : return NULL;
1621 :
1622 0 : if (isl_schedule_node_get_type(node) != isl_schedule_node_band)
1623 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
1624 : "not a band node", return NULL);
1625 0 : if (isl_schedule_node_band_n_member(node) == 0) {
1626 : isl_union_set *domain;
1627 :
1628 0 : domain = isl_schedule_node_get_universe_domain(node);
1629 0 : return isl_union_map_from_domain(domain);
1630 : }
1631 :
1632 0 : mupa = isl_schedule_node_band_get_partial_schedule(node);
1633 0 : return isl_union_map_from_multi_union_pw_aff(mupa);
1634 : }
1635 :
1636 : /* Return the loop AST generation type for the band member of band node "node"
1637 : * at position "pos".
1638 : */
1639 0 : enum isl_ast_loop_type isl_schedule_node_band_member_get_ast_loop_type(
1640 : __isl_keep isl_schedule_node *node, int pos)
1641 : {
1642 0 : if (!node)
1643 0 : return isl_ast_loop_error;
1644 :
1645 0 : return isl_schedule_tree_band_member_get_ast_loop_type(node->tree, pos);
1646 : }
1647 :
1648 : /* Set the loop AST generation type for the band member of band node "node"
1649 : * at position "pos" to "type".
1650 : */
1651 0 : __isl_give isl_schedule_node *isl_schedule_node_band_member_set_ast_loop_type(
1652 : __isl_take isl_schedule_node *node, int pos,
1653 : enum isl_ast_loop_type type)
1654 : {
1655 : isl_schedule_tree *tree;
1656 :
1657 0 : if (!node)
1658 0 : return NULL;
1659 :
1660 0 : tree = isl_schedule_tree_copy(node->tree);
1661 0 : tree = isl_schedule_tree_band_member_set_ast_loop_type(tree, pos, type);
1662 0 : return isl_schedule_node_graft_tree(node, tree);
1663 : }
1664 :
1665 : /* Return the loop AST generation type for the band member of band node "node"
1666 : * at position "pos" for the isolated part.
1667 : */
1668 0 : enum isl_ast_loop_type isl_schedule_node_band_member_get_isolate_ast_loop_type(
1669 : __isl_keep isl_schedule_node *node, int pos)
1670 : {
1671 0 : if (!node)
1672 0 : return isl_ast_loop_error;
1673 :
1674 0 : return isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1675 : node->tree, pos);
1676 : }
1677 :
1678 : /* Set the loop AST generation type for the band member of band node "node"
1679 : * at position "pos" for the isolated part to "type".
1680 : */
1681 : __isl_give isl_schedule_node *
1682 0 : isl_schedule_node_band_member_set_isolate_ast_loop_type(
1683 : __isl_take isl_schedule_node *node, int pos,
1684 : enum isl_ast_loop_type type)
1685 : {
1686 : isl_schedule_tree *tree;
1687 :
1688 0 : if (!node)
1689 0 : return NULL;
1690 :
1691 0 : tree = isl_schedule_tree_copy(node->tree);
1692 0 : tree = isl_schedule_tree_band_member_set_isolate_ast_loop_type(tree,
1693 : pos, type);
1694 0 : return isl_schedule_node_graft_tree(node, tree);
1695 : }
1696 :
1697 : /* Return the AST build options associated to band node "node".
1698 : */
1699 0 : __isl_give isl_union_set *isl_schedule_node_band_get_ast_build_options(
1700 : __isl_keep isl_schedule_node *node)
1701 : {
1702 0 : if (!node)
1703 0 : return NULL;
1704 :
1705 0 : return isl_schedule_tree_band_get_ast_build_options(node->tree);
1706 : }
1707 :
1708 : /* Replace the AST build options associated to band node "node" by "options".
1709 : */
1710 0 : __isl_give isl_schedule_node *isl_schedule_node_band_set_ast_build_options(
1711 : __isl_take isl_schedule_node *node, __isl_take isl_union_set *options)
1712 : {
1713 : isl_schedule_tree *tree;
1714 :
1715 0 : if (!node || !options)
1716 : goto error;
1717 :
1718 0 : tree = isl_schedule_tree_copy(node->tree);
1719 0 : tree = isl_schedule_tree_band_set_ast_build_options(tree, options);
1720 0 : return isl_schedule_node_graft_tree(node, tree);
1721 : error:
1722 0 : isl_schedule_node_free(node);
1723 0 : isl_union_set_free(options);
1724 0 : return NULL;
1725 : }
1726 :
1727 : /* Return the "isolate" option associated to band node "node".
1728 : */
1729 0 : __isl_give isl_set *isl_schedule_node_band_get_ast_isolate_option(
1730 : __isl_keep isl_schedule_node *node)
1731 : {
1732 : int depth;
1733 :
1734 0 : if (!node)
1735 0 : return NULL;
1736 :
1737 0 : depth = isl_schedule_node_get_schedule_depth(node);
1738 0 : return isl_schedule_tree_band_get_ast_isolate_option(node->tree, depth);
1739 : }
1740 :
1741 : /* Make sure that that spaces of "node" and "mv" are the same.
1742 : * Return -1 on error, reporting the error to the user.
1743 : */
1744 0 : static int check_space_multi_val(__isl_keep isl_schedule_node *node,
1745 : __isl_keep isl_multi_val *mv)
1746 : {
1747 : isl_space *node_space, *mv_space;
1748 : int equal;
1749 :
1750 0 : node_space = isl_schedule_node_band_get_space(node);
1751 0 : mv_space = isl_multi_val_get_space(mv);
1752 0 : equal = isl_space_tuple_is_equal(node_space, isl_dim_set,
1753 : mv_space, isl_dim_set);
1754 0 : isl_space_free(mv_space);
1755 0 : isl_space_free(node_space);
1756 0 : if (equal < 0)
1757 0 : return -1;
1758 0 : if (!equal)
1759 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
1760 : "spaces don't match", return -1);
1761 :
1762 0 : return 0;
1763 : }
1764 :
1765 : /* Multiply the partial schedule of the band node "node"
1766 : * with the factors in "mv".
1767 : */
1768 0 : __isl_give isl_schedule_node *isl_schedule_node_band_scale(
1769 : __isl_take isl_schedule_node *node, __isl_take isl_multi_val *mv)
1770 : {
1771 : isl_schedule_tree *tree;
1772 : int anchored;
1773 :
1774 0 : if (!node || !mv)
1775 : goto error;
1776 0 : if (check_space_multi_val(node, mv) < 0)
1777 0 : goto error;
1778 0 : anchored = isl_schedule_node_is_subtree_anchored(node);
1779 0 : if (anchored < 0)
1780 0 : goto error;
1781 0 : if (anchored)
1782 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
1783 : "cannot scale band node with anchored subtree",
1784 : goto error);
1785 :
1786 0 : tree = isl_schedule_node_get_tree(node);
1787 0 : tree = isl_schedule_tree_band_scale(tree, mv);
1788 0 : return isl_schedule_node_graft_tree(node, tree);
1789 : error:
1790 0 : isl_multi_val_free(mv);
1791 0 : isl_schedule_node_free(node);
1792 0 : return NULL;
1793 : }
1794 :
1795 : /* Divide the partial schedule of the band node "node"
1796 : * by the factors in "mv".
1797 : */
1798 0 : __isl_give isl_schedule_node *isl_schedule_node_band_scale_down(
1799 : __isl_take isl_schedule_node *node, __isl_take isl_multi_val *mv)
1800 : {
1801 : isl_schedule_tree *tree;
1802 : int anchored;
1803 :
1804 0 : if (!node || !mv)
1805 : goto error;
1806 0 : if (check_space_multi_val(node, mv) < 0)
1807 0 : goto error;
1808 0 : anchored = isl_schedule_node_is_subtree_anchored(node);
1809 0 : if (anchored < 0)
1810 0 : goto error;
1811 0 : if (anchored)
1812 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
1813 : "cannot scale down band node with anchored subtree",
1814 : goto error);
1815 :
1816 0 : tree = isl_schedule_node_get_tree(node);
1817 0 : tree = isl_schedule_tree_band_scale_down(tree, mv);
1818 0 : return isl_schedule_node_graft_tree(node, tree);
1819 : error:
1820 0 : isl_multi_val_free(mv);
1821 0 : isl_schedule_node_free(node);
1822 0 : return NULL;
1823 : }
1824 :
1825 : /* Reduce the partial schedule of the band node "node"
1826 : * modulo the factors in "mv".
1827 : */
1828 0 : __isl_give isl_schedule_node *isl_schedule_node_band_mod(
1829 : __isl_take isl_schedule_node *node, __isl_take isl_multi_val *mv)
1830 : {
1831 : isl_schedule_tree *tree;
1832 : isl_bool anchored;
1833 :
1834 0 : if (!node || !mv)
1835 : goto error;
1836 0 : if (check_space_multi_val(node, mv) < 0)
1837 0 : goto error;
1838 0 : anchored = isl_schedule_node_is_subtree_anchored(node);
1839 0 : if (anchored < 0)
1840 0 : goto error;
1841 0 : if (anchored)
1842 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
1843 : "cannot perform mod on band node with anchored subtree",
1844 : goto error);
1845 :
1846 0 : tree = isl_schedule_node_get_tree(node);
1847 0 : tree = isl_schedule_tree_band_mod(tree, mv);
1848 0 : return isl_schedule_node_graft_tree(node, tree);
1849 : error:
1850 0 : isl_multi_val_free(mv);
1851 0 : isl_schedule_node_free(node);
1852 0 : return NULL;
1853 : }
1854 :
1855 : /* Make sure that that spaces of "node" and "mupa" are the same.
1856 : * Return isl_stat_error on error, reporting the error to the user.
1857 : */
1858 0 : static isl_stat check_space_multi_union_pw_aff(
1859 : __isl_keep isl_schedule_node *node,
1860 : __isl_keep isl_multi_union_pw_aff *mupa)
1861 : {
1862 : isl_space *node_space, *mupa_space;
1863 : isl_bool equal;
1864 :
1865 0 : node_space = isl_schedule_node_band_get_space(node);
1866 0 : mupa_space = isl_multi_union_pw_aff_get_space(mupa);
1867 0 : equal = isl_space_tuple_is_equal(node_space, isl_dim_set,
1868 : mupa_space, isl_dim_set);
1869 0 : isl_space_free(mupa_space);
1870 0 : isl_space_free(node_space);
1871 0 : if (equal < 0)
1872 0 : return isl_stat_error;
1873 0 : if (!equal)
1874 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
1875 : "spaces don't match", return isl_stat_error);
1876 :
1877 0 : return isl_stat_ok;
1878 : }
1879 :
1880 : /* Shift the partial schedule of the band node "node" by "shift".
1881 : */
1882 0 : __isl_give isl_schedule_node *isl_schedule_node_band_shift(
1883 : __isl_take isl_schedule_node *node,
1884 : __isl_take isl_multi_union_pw_aff *shift)
1885 : {
1886 : isl_schedule_tree *tree;
1887 : int anchored;
1888 :
1889 0 : if (!node || !shift)
1890 : goto error;
1891 0 : if (check_space_multi_union_pw_aff(node, shift) < 0)
1892 0 : goto error;
1893 0 : anchored = isl_schedule_node_is_subtree_anchored(node);
1894 0 : if (anchored < 0)
1895 0 : goto error;
1896 0 : if (anchored)
1897 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
1898 : "cannot shift band node with anchored subtree",
1899 : goto error);
1900 :
1901 0 : tree = isl_schedule_node_get_tree(node);
1902 0 : tree = isl_schedule_tree_band_shift(tree, shift);
1903 0 : return isl_schedule_node_graft_tree(node, tree);
1904 : error:
1905 0 : isl_multi_union_pw_aff_free(shift);
1906 0 : isl_schedule_node_free(node);
1907 0 : return NULL;
1908 : }
1909 :
1910 : /* Tile "node" with tile sizes "sizes".
1911 : *
1912 : * The current node is replaced by two nested nodes corresponding
1913 : * to the tile dimensions and the point dimensions.
1914 : *
1915 : * Return a pointer to the outer (tile) node.
1916 : *
1917 : * If any of the descendants of "node" depend on the set of outer band nodes,
1918 : * then we refuse to tile the node.
1919 : *
1920 : * If the scale tile loops option is set, then the tile loops
1921 : * are scaled by the tile sizes. If the shift point loops option is set,
1922 : * then the point loops are shifted to start at zero.
1923 : * In particular, these options affect the tile and point loop schedules
1924 : * as follows
1925 : *
1926 : * scale shift original tile point
1927 : *
1928 : * 0 0 i floor(i/s) i
1929 : * 1 0 i s * floor(i/s) i
1930 : * 0 1 i floor(i/s) i - s * floor(i/s)
1931 : * 1 1 i s * floor(i/s) i - s * floor(i/s)
1932 : */
1933 0 : __isl_give isl_schedule_node *isl_schedule_node_band_tile(
1934 : __isl_take isl_schedule_node *node, __isl_take isl_multi_val *sizes)
1935 : {
1936 : isl_schedule_tree *tree;
1937 : int anchored;
1938 :
1939 0 : if (!node || !sizes)
1940 : goto error;
1941 0 : anchored = isl_schedule_node_is_subtree_anchored(node);
1942 0 : if (anchored < 0)
1943 0 : goto error;
1944 0 : if (anchored)
1945 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
1946 : "cannot tile band node with anchored subtree",
1947 : goto error);
1948 :
1949 0 : if (check_space_multi_val(node, sizes) < 0)
1950 0 : goto error;
1951 :
1952 0 : tree = isl_schedule_node_get_tree(node);
1953 0 : tree = isl_schedule_tree_band_tile(tree, sizes);
1954 0 : return isl_schedule_node_graft_tree(node, tree);
1955 : error:
1956 0 : isl_multi_val_free(sizes);
1957 0 : isl_schedule_node_free(node);
1958 0 : return NULL;
1959 : }
1960 :
1961 : /* Move the band node "node" down to all the leaves in the subtree
1962 : * rooted at "node".
1963 : * Return a pointer to the node in the resulting tree that is in the same
1964 : * position as the node pointed to by "node" in the original tree.
1965 : *
1966 : * If the node only has a leaf child, then nothing needs to be done.
1967 : * Otherwise, the child of the node is removed and the result is
1968 : * appended to all the leaves in the subtree rooted at the original child.
1969 : * Since the node is moved to the leaves, it needs to be expanded
1970 : * according to the expansion, if any, defined by that subtree.
1971 : * In the end, the original node is replaced by the result of
1972 : * attaching copies of the expanded node to the leaves.
1973 : *
1974 : * If any of the nodes in the subtree rooted at "node" depend on
1975 : * the set of outer band nodes then we refuse to sink the band node.
1976 : */
1977 0 : __isl_give isl_schedule_node *isl_schedule_node_band_sink(
1978 : __isl_take isl_schedule_node *node)
1979 : {
1980 : enum isl_schedule_node_type type;
1981 : isl_schedule_tree *tree, *child;
1982 : isl_union_pw_multi_aff *contraction;
1983 : int anchored;
1984 :
1985 0 : if (!node)
1986 0 : return NULL;
1987 :
1988 0 : type = isl_schedule_node_get_type(node);
1989 0 : if (type != isl_schedule_node_band)
1990 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
1991 : "not a band node", return isl_schedule_node_free(node));
1992 0 : anchored = isl_schedule_node_is_subtree_anchored(node);
1993 0 : if (anchored < 0)
1994 0 : return isl_schedule_node_free(node);
1995 0 : if (anchored)
1996 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
1997 : "cannot sink band node in anchored subtree",
1998 : return isl_schedule_node_free(node));
1999 0 : if (isl_schedule_tree_n_children(node->tree) == 0)
2000 0 : return node;
2001 :
2002 0 : contraction = isl_schedule_node_get_subtree_contraction(node);
2003 :
2004 0 : tree = isl_schedule_node_get_tree(node);
2005 0 : child = isl_schedule_tree_get_child(tree, 0);
2006 0 : tree = isl_schedule_tree_reset_children(tree);
2007 0 : tree = isl_schedule_tree_pullback_union_pw_multi_aff(tree, contraction);
2008 0 : tree = isl_schedule_tree_append_to_leaves(child, tree);
2009 :
2010 0 : return isl_schedule_node_graft_tree(node, tree);
2011 : }
2012 :
2013 : /* Split "node" into two nested band nodes, one with the first "pos"
2014 : * dimensions and one with the remaining dimensions.
2015 : * The schedules of the two band nodes live in anonymous spaces.
2016 : * The loop AST generation type options and the isolate option
2017 : * are split over the two band nodes.
2018 : */
2019 0 : __isl_give isl_schedule_node *isl_schedule_node_band_split(
2020 : __isl_take isl_schedule_node *node, int pos)
2021 : {
2022 : int depth;
2023 : isl_schedule_tree *tree;
2024 :
2025 0 : depth = isl_schedule_node_get_schedule_depth(node);
2026 0 : tree = isl_schedule_node_get_tree(node);
2027 0 : tree = isl_schedule_tree_band_split(tree, pos, depth);
2028 0 : return isl_schedule_node_graft_tree(node, tree);
2029 : }
2030 :
2031 : /* Return the context of the context node "node".
2032 : */
2033 0 : __isl_give isl_set *isl_schedule_node_context_get_context(
2034 : __isl_keep isl_schedule_node *node)
2035 : {
2036 0 : if (!node)
2037 0 : return NULL;
2038 :
2039 0 : return isl_schedule_tree_context_get_context(node->tree);
2040 : }
2041 :
2042 : /* Return the domain of the domain node "node".
2043 : */
2044 0 : __isl_give isl_union_set *isl_schedule_node_domain_get_domain(
2045 : __isl_keep isl_schedule_node *node)
2046 : {
2047 0 : if (!node)
2048 0 : return NULL;
2049 :
2050 0 : return isl_schedule_tree_domain_get_domain(node->tree);
2051 : }
2052 :
2053 : /* Return the expansion map of expansion node "node".
2054 : */
2055 0 : __isl_give isl_union_map *isl_schedule_node_expansion_get_expansion(
2056 : __isl_keep isl_schedule_node *node)
2057 : {
2058 0 : if (!node)
2059 0 : return NULL;
2060 :
2061 0 : return isl_schedule_tree_expansion_get_expansion(node->tree);
2062 : }
2063 :
2064 : /* Return the contraction of expansion node "node".
2065 : */
2066 0 : __isl_give isl_union_pw_multi_aff *isl_schedule_node_expansion_get_contraction(
2067 : __isl_keep isl_schedule_node *node)
2068 : {
2069 0 : if (!node)
2070 0 : return NULL;
2071 :
2072 0 : return isl_schedule_tree_expansion_get_contraction(node->tree);
2073 : }
2074 :
2075 : /* Replace the contraction and the expansion of the expansion node "node"
2076 : * by "contraction" and "expansion".
2077 : */
2078 : __isl_give isl_schedule_node *
2079 0 : isl_schedule_node_expansion_set_contraction_and_expansion(
2080 : __isl_take isl_schedule_node *node,
2081 : __isl_take isl_union_pw_multi_aff *contraction,
2082 : __isl_take isl_union_map *expansion)
2083 : {
2084 : isl_schedule_tree *tree;
2085 :
2086 0 : if (!node || !contraction || !expansion)
2087 : goto error;
2088 :
2089 0 : tree = isl_schedule_tree_copy(node->tree);
2090 0 : tree = isl_schedule_tree_expansion_set_contraction_and_expansion(tree,
2091 : contraction, expansion);
2092 0 : return isl_schedule_node_graft_tree(node, tree);
2093 : error:
2094 0 : isl_schedule_node_free(node);
2095 0 : isl_union_pw_multi_aff_free(contraction);
2096 0 : isl_union_map_free(expansion);
2097 0 : return NULL;
2098 : }
2099 :
2100 : /* Return the extension of the extension node "node".
2101 : */
2102 0 : __isl_give isl_union_map *isl_schedule_node_extension_get_extension(
2103 : __isl_keep isl_schedule_node *node)
2104 : {
2105 0 : if (!node)
2106 0 : return NULL;
2107 :
2108 0 : return isl_schedule_tree_extension_get_extension(node->tree);
2109 : }
2110 :
2111 : /* Replace the extension of extension node "node" by "extension".
2112 : */
2113 0 : __isl_give isl_schedule_node *isl_schedule_node_extension_set_extension(
2114 : __isl_take isl_schedule_node *node, __isl_take isl_union_map *extension)
2115 : {
2116 : isl_schedule_tree *tree;
2117 :
2118 0 : if (!node || !extension)
2119 : goto error;
2120 :
2121 0 : tree = isl_schedule_tree_copy(node->tree);
2122 0 : tree = isl_schedule_tree_extension_set_extension(tree, extension);
2123 0 : return isl_schedule_node_graft_tree(node, tree);
2124 : error:
2125 0 : isl_schedule_node_free(node);
2126 0 : isl_union_map_free(extension);
2127 0 : return NULL;
2128 : }
2129 :
2130 : /* Return the filter of the filter node "node".
2131 : */
2132 0 : __isl_give isl_union_set *isl_schedule_node_filter_get_filter(
2133 : __isl_keep isl_schedule_node *node)
2134 : {
2135 0 : if (!node)
2136 0 : return NULL;
2137 :
2138 0 : return isl_schedule_tree_filter_get_filter(node->tree);
2139 : }
2140 :
2141 : /* Replace the filter of filter node "node" by "filter".
2142 : */
2143 0 : __isl_give isl_schedule_node *isl_schedule_node_filter_set_filter(
2144 : __isl_take isl_schedule_node *node, __isl_take isl_union_set *filter)
2145 : {
2146 : isl_schedule_tree *tree;
2147 :
2148 0 : if (!node || !filter)
2149 : goto error;
2150 :
2151 0 : tree = isl_schedule_tree_copy(node->tree);
2152 0 : tree = isl_schedule_tree_filter_set_filter(tree, filter);
2153 0 : return isl_schedule_node_graft_tree(node, tree);
2154 : error:
2155 0 : isl_schedule_node_free(node);
2156 0 : isl_union_set_free(filter);
2157 0 : return NULL;
2158 : }
2159 :
2160 : /* Intersect the filter of filter node "node" with "filter".
2161 : *
2162 : * If the filter of the node is already a subset of "filter",
2163 : * then leave the node unchanged.
2164 : */
2165 0 : __isl_give isl_schedule_node *isl_schedule_node_filter_intersect_filter(
2166 : __isl_take isl_schedule_node *node, __isl_take isl_union_set *filter)
2167 : {
2168 0 : isl_union_set *node_filter = NULL;
2169 : isl_bool subset;
2170 :
2171 0 : if (!node || !filter)
2172 : goto error;
2173 :
2174 0 : node_filter = isl_schedule_node_filter_get_filter(node);
2175 0 : subset = isl_union_set_is_subset(node_filter, filter);
2176 0 : if (subset < 0)
2177 0 : goto error;
2178 0 : if (subset) {
2179 0 : isl_union_set_free(node_filter);
2180 0 : isl_union_set_free(filter);
2181 0 : return node;
2182 : }
2183 0 : node_filter = isl_union_set_intersect(node_filter, filter);
2184 0 : node = isl_schedule_node_filter_set_filter(node, node_filter);
2185 0 : return node;
2186 : error:
2187 0 : isl_schedule_node_free(node);
2188 0 : isl_union_set_free(node_filter);
2189 0 : isl_union_set_free(filter);
2190 0 : return NULL;
2191 : }
2192 :
2193 : /* Return the guard of the guard node "node".
2194 : */
2195 0 : __isl_give isl_set *isl_schedule_node_guard_get_guard(
2196 : __isl_keep isl_schedule_node *node)
2197 : {
2198 0 : if (!node)
2199 0 : return NULL;
2200 :
2201 0 : return isl_schedule_tree_guard_get_guard(node->tree);
2202 : }
2203 :
2204 : /* Return the mark identifier of the mark node "node".
2205 : */
2206 0 : __isl_give isl_id *isl_schedule_node_mark_get_id(
2207 : __isl_keep isl_schedule_node *node)
2208 : {
2209 0 : if (!node)
2210 0 : return NULL;
2211 :
2212 0 : return isl_schedule_tree_mark_get_id(node->tree);
2213 : }
2214 :
2215 : /* Replace the child at position "pos" of the sequence node "node"
2216 : * by the children of sequence root node of "tree".
2217 : */
2218 0 : __isl_give isl_schedule_node *isl_schedule_node_sequence_splice(
2219 : __isl_take isl_schedule_node *node, int pos,
2220 : __isl_take isl_schedule_tree *tree)
2221 : {
2222 : isl_schedule_tree *node_tree;
2223 :
2224 0 : if (!node || !tree)
2225 : goto error;
2226 0 : if (isl_schedule_node_get_type(node) != isl_schedule_node_sequence)
2227 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
2228 : "not a sequence node", goto error);
2229 0 : if (isl_schedule_tree_get_type(tree) != isl_schedule_node_sequence)
2230 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
2231 : "not a sequence node", goto error);
2232 0 : node_tree = isl_schedule_node_get_tree(node);
2233 0 : node_tree = isl_schedule_tree_sequence_splice(node_tree, pos, tree);
2234 0 : node = isl_schedule_node_graft_tree(node, node_tree);
2235 :
2236 0 : return node;
2237 : error:
2238 0 : isl_schedule_node_free(node);
2239 0 : isl_schedule_tree_free(tree);
2240 0 : return NULL;
2241 : }
2242 :
2243 : /* Given a sequence node "node", with a child at position "pos" that
2244 : * is also a sequence node, attach the children of that node directly
2245 : * as children of "node" at that position, replacing the original child.
2246 : *
2247 : * The filters of these children are intersected with the filter
2248 : * of the child at position "pos".
2249 : */
2250 0 : __isl_give isl_schedule_node *isl_schedule_node_sequence_splice_child(
2251 : __isl_take isl_schedule_node *node, int pos)
2252 : {
2253 : int i, n;
2254 : isl_union_set *filter;
2255 : isl_schedule_node *child;
2256 : isl_schedule_tree *tree;
2257 :
2258 0 : if (!node)
2259 0 : return NULL;
2260 0 : if (isl_schedule_node_get_type(node) != isl_schedule_node_sequence)
2261 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
2262 : "not a sequence node",
2263 : return isl_schedule_node_free(node));
2264 0 : node = isl_schedule_node_child(node, pos);
2265 0 : node = isl_schedule_node_child(node, 0);
2266 0 : if (isl_schedule_node_get_type(node) != isl_schedule_node_sequence)
2267 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
2268 : "not a sequence node",
2269 : return isl_schedule_node_free(node));
2270 0 : child = isl_schedule_node_copy(node);
2271 0 : node = isl_schedule_node_parent(node);
2272 0 : filter = isl_schedule_node_filter_get_filter(node);
2273 0 : n = isl_schedule_node_n_children(child);
2274 0 : for (i = 0; i < n; ++i) {
2275 0 : child = isl_schedule_node_child(child, i);
2276 0 : child = isl_schedule_node_filter_intersect_filter(child,
2277 : isl_union_set_copy(filter));
2278 0 : child = isl_schedule_node_parent(child);
2279 : }
2280 0 : isl_union_set_free(filter);
2281 0 : tree = isl_schedule_node_get_tree(child);
2282 0 : isl_schedule_node_free(child);
2283 0 : node = isl_schedule_node_parent(node);
2284 0 : node = isl_schedule_node_sequence_splice(node, pos, tree);
2285 :
2286 0 : return node;
2287 : }
2288 :
2289 : /* Update the ancestors of "node" to point to the tree that "node"
2290 : * now points to.
2291 : * That is, replace the child in the original parent that corresponds
2292 : * to the current tree position by node->tree and continue updating
2293 : * the ancestors in the same way until the root is reached.
2294 : *
2295 : * If "fn" is not NULL, then it is called on each ancestor as we move up
2296 : * the tree so that it can modify the ancestor before it is added
2297 : * to the list of ancestors of the modified node.
2298 : * The additional "pos" argument records the position
2299 : * of the "tree" argument in the original schedule tree.
2300 : *
2301 : * If "node" originally points to a leaf of the schedule tree, then make sure
2302 : * that in the end it points to a leaf in the updated schedule tree.
2303 : */
2304 0 : static __isl_give isl_schedule_node *update_ancestors(
2305 : __isl_take isl_schedule_node *node,
2306 : __isl_give isl_schedule_tree *(*fn)(__isl_take isl_schedule_tree *tree,
2307 : __isl_keep isl_schedule_node *pos, void *user), void *user)
2308 : {
2309 : int i, n;
2310 : int is_leaf;
2311 : isl_schedule_tree *tree;
2312 0 : isl_schedule_node *pos = NULL;
2313 :
2314 0 : if (fn)
2315 0 : pos = isl_schedule_node_copy(node);
2316 :
2317 0 : node = isl_schedule_node_cow(node);
2318 0 : if (!node)
2319 0 : return isl_schedule_node_free(pos);
2320 :
2321 0 : n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
2322 0 : tree = isl_schedule_tree_copy(node->tree);
2323 :
2324 0 : for (i = n - 1; i >= 0; --i) {
2325 : isl_schedule_tree *parent;
2326 :
2327 0 : parent = isl_schedule_tree_list_get_schedule_tree(
2328 : node->ancestors, i);
2329 0 : parent = isl_schedule_tree_replace_child(parent,
2330 0 : node->child_pos[i], tree);
2331 0 : if (fn) {
2332 0 : pos = isl_schedule_node_parent(pos);
2333 0 : parent = fn(parent, pos, user);
2334 : }
2335 0 : node->ancestors = isl_schedule_tree_list_set_schedule_tree(
2336 0 : node->ancestors, i, isl_schedule_tree_copy(parent));
2337 :
2338 0 : tree = parent;
2339 : }
2340 :
2341 0 : if (fn)
2342 0 : isl_schedule_node_free(pos);
2343 :
2344 0 : is_leaf = isl_schedule_tree_is_leaf(node->tree);
2345 0 : node->schedule = isl_schedule_set_root(node->schedule, tree);
2346 0 : if (is_leaf) {
2347 0 : isl_schedule_tree_free(node->tree);
2348 0 : node->tree = isl_schedule_node_get_leaf(node);
2349 : }
2350 :
2351 0 : if (!node->schedule || !node->ancestors)
2352 0 : return isl_schedule_node_free(node);
2353 :
2354 0 : return node;
2355 : }
2356 :
2357 : /* Replace the subtree that "pos" points to by "tree", updating
2358 : * the ancestors to maintain a consistent state.
2359 : */
2360 0 : __isl_give isl_schedule_node *isl_schedule_node_graft_tree(
2361 : __isl_take isl_schedule_node *pos, __isl_take isl_schedule_tree *tree)
2362 : {
2363 0 : if (!tree || !pos)
2364 : goto error;
2365 0 : if (pos->tree == tree) {
2366 0 : isl_schedule_tree_free(tree);
2367 0 : return pos;
2368 : }
2369 :
2370 0 : pos = isl_schedule_node_cow(pos);
2371 0 : if (!pos)
2372 0 : goto error;
2373 :
2374 0 : isl_schedule_tree_free(pos->tree);
2375 0 : pos->tree = tree;
2376 :
2377 0 : return update_ancestors(pos, NULL, NULL);
2378 : error:
2379 0 : isl_schedule_node_free(pos);
2380 0 : isl_schedule_tree_free(tree);
2381 0 : return NULL;
2382 : }
2383 :
2384 : /* Make sure we can insert a node between "node" and its parent.
2385 : * Return -1 on error, reporting the reason why we cannot insert a node.
2386 : */
2387 0 : static int check_insert(__isl_keep isl_schedule_node *node)
2388 : {
2389 : int has_parent;
2390 : enum isl_schedule_node_type type;
2391 :
2392 0 : has_parent = isl_schedule_node_has_parent(node);
2393 0 : if (has_parent < 0)
2394 0 : return -1;
2395 0 : if (!has_parent)
2396 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
2397 : "cannot insert node outside of root", return -1);
2398 :
2399 0 : type = isl_schedule_node_get_parent_type(node);
2400 0 : if (type == isl_schedule_node_error)
2401 0 : return -1;
2402 0 : if (type == isl_schedule_node_set || type == isl_schedule_node_sequence)
2403 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
2404 : "cannot insert node between set or sequence node "
2405 : "and its filter children", return -1);
2406 :
2407 0 : return 0;
2408 : }
2409 :
2410 : /* Insert a band node with partial schedule "mupa" between "node" and
2411 : * its parent.
2412 : * Return a pointer to the new band node.
2413 : *
2414 : * If any of the nodes in the subtree rooted at "node" depend on
2415 : * the set of outer band nodes then we refuse to insert the band node.
2416 : */
2417 0 : __isl_give isl_schedule_node *isl_schedule_node_insert_partial_schedule(
2418 : __isl_take isl_schedule_node *node,
2419 : __isl_take isl_multi_union_pw_aff *mupa)
2420 : {
2421 : int anchored;
2422 : isl_schedule_band *band;
2423 : isl_schedule_tree *tree;
2424 :
2425 0 : if (check_insert(node) < 0)
2426 0 : node = isl_schedule_node_free(node);
2427 0 : anchored = isl_schedule_node_is_subtree_anchored(node);
2428 0 : if (anchored < 0)
2429 0 : goto error;
2430 0 : if (anchored)
2431 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
2432 : "cannot insert band node in anchored subtree",
2433 : goto error);
2434 :
2435 0 : tree = isl_schedule_node_get_tree(node);
2436 0 : band = isl_schedule_band_from_multi_union_pw_aff(mupa);
2437 0 : tree = isl_schedule_tree_insert_band(tree, band);
2438 0 : node = isl_schedule_node_graft_tree(node, tree);
2439 :
2440 0 : return node;
2441 : error:
2442 0 : isl_schedule_node_free(node);
2443 0 : isl_multi_union_pw_aff_free(mupa);
2444 0 : return NULL;
2445 : }
2446 :
2447 : /* Insert a context node with context "context" between "node" and its parent.
2448 : * Return a pointer to the new context node.
2449 : */
2450 0 : __isl_give isl_schedule_node *isl_schedule_node_insert_context(
2451 : __isl_take isl_schedule_node *node, __isl_take isl_set *context)
2452 : {
2453 : isl_schedule_tree *tree;
2454 :
2455 0 : if (check_insert(node) < 0)
2456 0 : node = isl_schedule_node_free(node);
2457 :
2458 0 : tree = isl_schedule_node_get_tree(node);
2459 0 : tree = isl_schedule_tree_insert_context(tree, context);
2460 0 : node = isl_schedule_node_graft_tree(node, tree);
2461 :
2462 0 : return node;
2463 : }
2464 :
2465 : /* Insert an expansion node with the given "contraction" and "expansion"
2466 : * between "node" and its parent.
2467 : * Return a pointer to the new expansion node.
2468 : *
2469 : * Typically the domain and range spaces of the expansion are different.
2470 : * This means that only one of them can refer to the current domain space
2471 : * in a consistent tree. It is up to the caller to ensure that the tree
2472 : * returns to a consistent state.
2473 : */
2474 0 : __isl_give isl_schedule_node *isl_schedule_node_insert_expansion(
2475 : __isl_take isl_schedule_node *node,
2476 : __isl_take isl_union_pw_multi_aff *contraction,
2477 : __isl_take isl_union_map *expansion)
2478 : {
2479 : isl_schedule_tree *tree;
2480 :
2481 0 : if (check_insert(node) < 0)
2482 0 : node = isl_schedule_node_free(node);
2483 :
2484 0 : tree = isl_schedule_node_get_tree(node);
2485 0 : tree = isl_schedule_tree_insert_expansion(tree, contraction, expansion);
2486 0 : node = isl_schedule_node_graft_tree(node, tree);
2487 :
2488 0 : return node;
2489 : }
2490 :
2491 : /* Insert an extension node with extension "extension" between "node" and
2492 : * its parent.
2493 : * Return a pointer to the new extension node.
2494 : */
2495 0 : __isl_give isl_schedule_node *isl_schedule_node_insert_extension(
2496 : __isl_take isl_schedule_node *node,
2497 : __isl_take isl_union_map *extension)
2498 : {
2499 : isl_schedule_tree *tree;
2500 :
2501 0 : tree = isl_schedule_node_get_tree(node);
2502 0 : tree = isl_schedule_tree_insert_extension(tree, extension);
2503 0 : node = isl_schedule_node_graft_tree(node, tree);
2504 :
2505 0 : return node;
2506 : }
2507 :
2508 : /* Insert a filter node with filter "filter" between "node" and its parent.
2509 : * Return a pointer to the new filter node.
2510 : */
2511 0 : __isl_give isl_schedule_node *isl_schedule_node_insert_filter(
2512 : __isl_take isl_schedule_node *node, __isl_take isl_union_set *filter)
2513 : {
2514 : isl_schedule_tree *tree;
2515 :
2516 0 : if (check_insert(node) < 0)
2517 0 : node = isl_schedule_node_free(node);
2518 :
2519 0 : tree = isl_schedule_node_get_tree(node);
2520 0 : tree = isl_schedule_tree_insert_filter(tree, filter);
2521 0 : node = isl_schedule_node_graft_tree(node, tree);
2522 :
2523 0 : return node;
2524 : }
2525 :
2526 : /* Insert a guard node with guard "guard" between "node" and its parent.
2527 : * Return a pointer to the new guard node.
2528 : */
2529 0 : __isl_give isl_schedule_node *isl_schedule_node_insert_guard(
2530 : __isl_take isl_schedule_node *node, __isl_take isl_set *guard)
2531 : {
2532 : isl_schedule_tree *tree;
2533 :
2534 0 : if (check_insert(node) < 0)
2535 0 : node = isl_schedule_node_free(node);
2536 :
2537 0 : tree = isl_schedule_node_get_tree(node);
2538 0 : tree = isl_schedule_tree_insert_guard(tree, guard);
2539 0 : node = isl_schedule_node_graft_tree(node, tree);
2540 :
2541 0 : return node;
2542 : }
2543 :
2544 : /* Insert a mark node with mark identifier "mark" between "node" and
2545 : * its parent.
2546 : * Return a pointer to the new mark node.
2547 : */
2548 0 : __isl_give isl_schedule_node *isl_schedule_node_insert_mark(
2549 : __isl_take isl_schedule_node *node, __isl_take isl_id *mark)
2550 : {
2551 : isl_schedule_tree *tree;
2552 :
2553 0 : if (check_insert(node) < 0)
2554 0 : node = isl_schedule_node_free(node);
2555 :
2556 0 : tree = isl_schedule_node_get_tree(node);
2557 0 : tree = isl_schedule_tree_insert_mark(tree, mark);
2558 0 : node = isl_schedule_node_graft_tree(node, tree);
2559 :
2560 0 : return node;
2561 : }
2562 :
2563 : /* Attach the current subtree of "node" to a sequence of filter tree nodes
2564 : * with filters described by "filters", attach this sequence
2565 : * of filter tree nodes as children to a new tree of type "type" and
2566 : * replace the original subtree of "node" by this new tree.
2567 : * Each copy of the original subtree is simplified with respect
2568 : * to the corresponding filter.
2569 : */
2570 0 : static __isl_give isl_schedule_node *isl_schedule_node_insert_children(
2571 : __isl_take isl_schedule_node *node,
2572 : enum isl_schedule_node_type type,
2573 : __isl_take isl_union_set_list *filters)
2574 : {
2575 : int i, n;
2576 : isl_ctx *ctx;
2577 : isl_schedule_tree *tree;
2578 : isl_schedule_tree_list *list;
2579 :
2580 0 : if (check_insert(node) < 0)
2581 0 : node = isl_schedule_node_free(node);
2582 :
2583 0 : if (!node || !filters)
2584 : goto error;
2585 :
2586 0 : ctx = isl_schedule_node_get_ctx(node);
2587 0 : n = isl_union_set_list_n_union_set(filters);
2588 0 : list = isl_schedule_tree_list_alloc(ctx, n);
2589 0 : for (i = 0; i < n; ++i) {
2590 : isl_schedule_node *node_i;
2591 : isl_schedule_tree *tree;
2592 : isl_union_set *filter;
2593 :
2594 0 : filter = isl_union_set_list_get_union_set(filters, i);
2595 0 : node_i = isl_schedule_node_copy(node);
2596 0 : node_i = isl_schedule_node_gist(node_i,
2597 : isl_union_set_copy(filter));
2598 0 : tree = isl_schedule_node_get_tree(node_i);
2599 0 : isl_schedule_node_free(node_i);
2600 0 : tree = isl_schedule_tree_insert_filter(tree, filter);
2601 0 : list = isl_schedule_tree_list_add(list, tree);
2602 : }
2603 0 : tree = isl_schedule_tree_from_children(type, list);
2604 0 : node = isl_schedule_node_graft_tree(node, tree);
2605 :
2606 0 : isl_union_set_list_free(filters);
2607 0 : return node;
2608 : error:
2609 0 : isl_union_set_list_free(filters);
2610 0 : isl_schedule_node_free(node);
2611 0 : return NULL;
2612 : }
2613 :
2614 : /* Insert a sequence node with child filters "filters" between "node" and
2615 : * its parent. That is, the tree that "node" points to is attached
2616 : * to each of the child nodes of the filter nodes.
2617 : * Return a pointer to the new sequence node.
2618 : */
2619 0 : __isl_give isl_schedule_node *isl_schedule_node_insert_sequence(
2620 : __isl_take isl_schedule_node *node,
2621 : __isl_take isl_union_set_list *filters)
2622 : {
2623 0 : return isl_schedule_node_insert_children(node,
2624 : isl_schedule_node_sequence, filters);
2625 : }
2626 :
2627 : /* Insert a set node with child filters "filters" between "node" and
2628 : * its parent. That is, the tree that "node" points to is attached
2629 : * to each of the child nodes of the filter nodes.
2630 : * Return a pointer to the new set node.
2631 : */
2632 0 : __isl_give isl_schedule_node *isl_schedule_node_insert_set(
2633 : __isl_take isl_schedule_node *node,
2634 : __isl_take isl_union_set_list *filters)
2635 : {
2636 0 : return isl_schedule_node_insert_children(node,
2637 : isl_schedule_node_set, filters);
2638 : }
2639 :
2640 : /* Remove "node" from its schedule tree and return a pointer
2641 : * to the leaf at the same position in the updated schedule tree.
2642 : *
2643 : * It is not allowed to remove the root of a schedule tree or
2644 : * a child of a set or sequence node.
2645 : */
2646 0 : __isl_give isl_schedule_node *isl_schedule_node_cut(
2647 : __isl_take isl_schedule_node *node)
2648 : {
2649 : isl_schedule_tree *leaf;
2650 : enum isl_schedule_node_type parent_type;
2651 :
2652 0 : if (!node)
2653 0 : return NULL;
2654 0 : if (!isl_schedule_node_has_parent(node))
2655 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
2656 : "cannot cut root", return isl_schedule_node_free(node));
2657 :
2658 0 : parent_type = isl_schedule_node_get_parent_type(node);
2659 0 : if (parent_type == isl_schedule_node_set ||
2660 : parent_type == isl_schedule_node_sequence)
2661 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
2662 : "cannot cut child of set or sequence",
2663 : return isl_schedule_node_free(node));
2664 :
2665 0 : leaf = isl_schedule_node_get_leaf(node);
2666 0 : return isl_schedule_node_graft_tree(node, leaf);
2667 : }
2668 :
2669 : /* Remove a single node from the schedule tree, attaching the child
2670 : * of "node" directly to its parent.
2671 : * Return a pointer to this former child or to the leaf the position
2672 : * of the original node if there was no child.
2673 : * It is not allowed to remove the root of a schedule tree,
2674 : * a set or sequence node, a child of a set or sequence node or
2675 : * a band node with an anchored subtree.
2676 : */
2677 0 : __isl_give isl_schedule_node *isl_schedule_node_delete(
2678 : __isl_take isl_schedule_node *node)
2679 : {
2680 : int n;
2681 : isl_schedule_tree *tree;
2682 : enum isl_schedule_node_type type;
2683 :
2684 0 : if (!node)
2685 0 : return NULL;
2686 :
2687 0 : if (isl_schedule_node_get_tree_depth(node) == 0)
2688 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
2689 : "cannot delete root node",
2690 : return isl_schedule_node_free(node));
2691 0 : n = isl_schedule_node_n_children(node);
2692 0 : if (n != 1)
2693 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
2694 : "can only delete node with a single child",
2695 : return isl_schedule_node_free(node));
2696 0 : type = isl_schedule_node_get_parent_type(node);
2697 0 : if (type == isl_schedule_node_sequence || type == isl_schedule_node_set)
2698 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
2699 : "cannot delete child of set or sequence",
2700 : return isl_schedule_node_free(node));
2701 0 : if (isl_schedule_node_get_type(node) == isl_schedule_node_band) {
2702 : int anchored;
2703 :
2704 0 : anchored = isl_schedule_node_is_subtree_anchored(node);
2705 0 : if (anchored < 0)
2706 0 : return isl_schedule_node_free(node);
2707 0 : if (anchored)
2708 0 : isl_die(isl_schedule_node_get_ctx(node),
2709 : isl_error_invalid,
2710 : "cannot delete band node with anchored subtree",
2711 : return isl_schedule_node_free(node));
2712 : }
2713 :
2714 0 : tree = isl_schedule_node_get_tree(node);
2715 0 : if (!tree || isl_schedule_tree_has_children(tree)) {
2716 0 : tree = isl_schedule_tree_child(tree, 0);
2717 : } else {
2718 0 : isl_schedule_tree_free(tree);
2719 0 : tree = isl_schedule_node_get_leaf(node);
2720 : }
2721 0 : node = isl_schedule_node_graft_tree(node, tree);
2722 :
2723 0 : return node;
2724 : }
2725 :
2726 : /* Internal data structure for the group_ancestor callback.
2727 : *
2728 : * If "finished" is set, then we no longer need to modify
2729 : * any further ancestors.
2730 : *
2731 : * "contraction" and "expansion" represent the expansion
2732 : * that reflects the grouping.
2733 : *
2734 : * "domain" contains the domain elements that reach the position
2735 : * where the grouping is performed. That is, it is the range
2736 : * of the resulting expansion.
2737 : * "domain_universe" is the universe of "domain".
2738 : * "group" is the set of group elements, i.e., the domain
2739 : * of the resulting expansion.
2740 : * "group_universe" is the universe of "group".
2741 : *
2742 : * "sched" is the schedule for the group elements, in pratice
2743 : * an identity mapping on "group_universe".
2744 : * "dim" is the dimension of "sched".
2745 : */
2746 : struct isl_schedule_group_data {
2747 : int finished;
2748 :
2749 : isl_union_map *expansion;
2750 : isl_union_pw_multi_aff *contraction;
2751 :
2752 : isl_union_set *domain;
2753 : isl_union_set *domain_universe;
2754 : isl_union_set *group;
2755 : isl_union_set *group_universe;
2756 :
2757 : int dim;
2758 : isl_multi_aff *sched;
2759 : };
2760 :
2761 : /* Is domain covered by data->domain within data->domain_universe?
2762 : */
2763 0 : static int locally_covered_by_domain(__isl_keep isl_union_set *domain,
2764 : struct isl_schedule_group_data *data)
2765 : {
2766 : int is_subset;
2767 : isl_union_set *test;
2768 :
2769 0 : test = isl_union_set_copy(domain);
2770 0 : test = isl_union_set_intersect(test,
2771 : isl_union_set_copy(data->domain_universe));
2772 0 : is_subset = isl_union_set_is_subset(test, data->domain);
2773 0 : isl_union_set_free(test);
2774 :
2775 0 : return is_subset;
2776 : }
2777 :
2778 : /* Update the band tree root "tree" to refer to the group instances
2779 : * in data->group rather than the original domain elements in data->domain.
2780 : * "pos" is the position in the original schedule tree where the modified
2781 : * "tree" will be attached.
2782 : *
2783 : * Add the part of the identity schedule on the group instances data->sched
2784 : * that corresponds to this band node to the band schedule.
2785 : * If the domain elements that reach the node and that are part
2786 : * of data->domain_universe are all elements of data->domain (and therefore
2787 : * replaced by the group instances) then this data->domain_universe
2788 : * is removed from the domain of the band schedule.
2789 : */
2790 0 : static __isl_give isl_schedule_tree *group_band(
2791 : __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_node *pos,
2792 : struct isl_schedule_group_data *data)
2793 : {
2794 : isl_union_set *domain;
2795 : isl_multi_aff *ma;
2796 : isl_multi_union_pw_aff *mupa, *partial;
2797 : int is_covered;
2798 : int depth, n, has_id;
2799 :
2800 0 : domain = isl_schedule_node_get_domain(pos);
2801 0 : is_covered = locally_covered_by_domain(domain, data);
2802 0 : if (is_covered >= 0 && is_covered) {
2803 0 : domain = isl_union_set_universe(domain);
2804 0 : domain = isl_union_set_subtract(domain,
2805 : isl_union_set_copy(data->domain_universe));
2806 0 : tree = isl_schedule_tree_band_intersect_domain(tree, domain);
2807 : } else
2808 0 : isl_union_set_free(domain);
2809 0 : if (is_covered < 0)
2810 0 : return isl_schedule_tree_free(tree);
2811 0 : depth = isl_schedule_node_get_schedule_depth(pos);
2812 0 : n = isl_schedule_tree_band_n_member(tree);
2813 0 : ma = isl_multi_aff_copy(data->sched);
2814 0 : ma = isl_multi_aff_drop_dims(ma, isl_dim_out, 0, depth);
2815 0 : ma = isl_multi_aff_drop_dims(ma, isl_dim_out, n, data->dim - depth - n);
2816 0 : mupa = isl_multi_union_pw_aff_from_multi_aff(ma);
2817 0 : partial = isl_schedule_tree_band_get_partial_schedule(tree);
2818 0 : has_id = isl_multi_union_pw_aff_has_tuple_id(partial, isl_dim_set);
2819 0 : if (has_id < 0) {
2820 0 : partial = isl_multi_union_pw_aff_free(partial);
2821 0 : } else if (has_id) {
2822 : isl_id *id;
2823 0 : id = isl_multi_union_pw_aff_get_tuple_id(partial, isl_dim_set);
2824 0 : mupa = isl_multi_union_pw_aff_set_tuple_id(mupa,
2825 : isl_dim_set, id);
2826 : }
2827 0 : partial = isl_multi_union_pw_aff_union_add(partial, mupa);
2828 0 : tree = isl_schedule_tree_band_set_partial_schedule(tree, partial);
2829 :
2830 0 : return tree;
2831 : }
2832 :
2833 : /* Drop the parameters in "uset" that are not also in "space".
2834 : * "n" is the number of parameters in "space".
2835 : */
2836 0 : static __isl_give isl_union_set *union_set_drop_extra_params(
2837 : __isl_take isl_union_set *uset, __isl_keep isl_space *space, int n)
2838 : {
2839 : int n2;
2840 :
2841 0 : uset = isl_union_set_align_params(uset, isl_space_copy(space));
2842 0 : n2 = isl_union_set_dim(uset, isl_dim_param);
2843 0 : uset = isl_union_set_project_out(uset, isl_dim_param, n, n2 - n);
2844 :
2845 0 : return uset;
2846 : }
2847 :
2848 : /* Update the context tree root "tree" to refer to the group instances
2849 : * in data->group rather than the original domain elements in data->domain.
2850 : * "pos" is the position in the original schedule tree where the modified
2851 : * "tree" will be attached.
2852 : *
2853 : * We do not actually need to update "tree" since a context node only
2854 : * refers to the schedule space. However, we may need to update "data"
2855 : * to not refer to any parameters introduced by the context node.
2856 : */
2857 0 : static __isl_give isl_schedule_tree *group_context(
2858 : __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_node *pos,
2859 : struct isl_schedule_group_data *data)
2860 : {
2861 : isl_space *space;
2862 : isl_union_set *domain;
2863 : int n1, n2;
2864 : int involves;
2865 :
2866 0 : if (isl_schedule_node_get_tree_depth(pos) == 1)
2867 0 : return tree;
2868 :
2869 0 : domain = isl_schedule_node_get_universe_domain(pos);
2870 0 : space = isl_union_set_get_space(domain);
2871 0 : isl_union_set_free(domain);
2872 :
2873 0 : n1 = isl_space_dim(space, isl_dim_param);
2874 0 : data->expansion = isl_union_map_align_params(data->expansion, space);
2875 0 : n2 = isl_union_map_dim(data->expansion, isl_dim_param);
2876 :
2877 0 : if (!data->expansion)
2878 0 : return isl_schedule_tree_free(tree);
2879 0 : if (n1 == n2)
2880 0 : return tree;
2881 :
2882 0 : involves = isl_union_map_involves_dims(data->expansion,
2883 0 : isl_dim_param, n1, n2 - n1);
2884 0 : if (involves < 0)
2885 0 : return isl_schedule_tree_free(tree);
2886 0 : if (involves)
2887 0 : isl_die(isl_schedule_node_get_ctx(pos), isl_error_invalid,
2888 : "grouping cannot only refer to global parameters",
2889 : return isl_schedule_tree_free(tree));
2890 :
2891 0 : data->expansion = isl_union_map_project_out(data->expansion,
2892 0 : isl_dim_param, n1, n2 - n1);
2893 0 : space = isl_union_map_get_space(data->expansion);
2894 :
2895 0 : data->contraction = isl_union_pw_multi_aff_align_params(
2896 : data->contraction, isl_space_copy(space));
2897 0 : n2 = isl_union_pw_multi_aff_dim(data->contraction, isl_dim_param);
2898 0 : data->contraction = isl_union_pw_multi_aff_drop_dims(data->contraction,
2899 0 : isl_dim_param, n1, n2 - n1);
2900 :
2901 0 : data->domain = union_set_drop_extra_params(data->domain, space, n1);
2902 0 : data->domain_universe =
2903 0 : union_set_drop_extra_params(data->domain_universe, space, n1);
2904 0 : data->group = union_set_drop_extra_params(data->group, space, n1);
2905 0 : data->group_universe =
2906 0 : union_set_drop_extra_params(data->group_universe, space, n1);
2907 :
2908 0 : data->sched = isl_multi_aff_align_params(data->sched,
2909 : isl_space_copy(space));
2910 0 : n2 = isl_multi_aff_dim(data->sched, isl_dim_param);
2911 0 : data->sched = isl_multi_aff_drop_dims(data->sched,
2912 0 : isl_dim_param, n1, n2 - n1);
2913 :
2914 0 : isl_space_free(space);
2915 :
2916 0 : return tree;
2917 : }
2918 :
2919 : /* Update the domain tree root "tree" to refer to the group instances
2920 : * in data->group rather than the original domain elements in data->domain.
2921 : * "pos" is the position in the original schedule tree where the modified
2922 : * "tree" will be attached.
2923 : *
2924 : * We first double-check that all grouped domain elements are actually
2925 : * part of the root domain and then replace those elements by the group
2926 : * instances.
2927 : */
2928 0 : static __isl_give isl_schedule_tree *group_domain(
2929 : __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_node *pos,
2930 : struct isl_schedule_group_data *data)
2931 : {
2932 : isl_union_set *domain;
2933 : int is_subset;
2934 :
2935 0 : domain = isl_schedule_tree_domain_get_domain(tree);
2936 0 : is_subset = isl_union_set_is_subset(data->domain, domain);
2937 0 : isl_union_set_free(domain);
2938 0 : if (is_subset < 0)
2939 0 : return isl_schedule_tree_free(tree);
2940 0 : if (!is_subset)
2941 0 : isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
2942 : "grouped domain should be part of outer domain",
2943 : return isl_schedule_tree_free(tree));
2944 0 : domain = isl_schedule_tree_domain_get_domain(tree);
2945 0 : domain = isl_union_set_subtract(domain,
2946 : isl_union_set_copy(data->domain));
2947 0 : domain = isl_union_set_union(domain, isl_union_set_copy(data->group));
2948 0 : tree = isl_schedule_tree_domain_set_domain(tree, domain);
2949 :
2950 0 : return tree;
2951 : }
2952 :
2953 : /* Update the expansion tree root "tree" to refer to the group instances
2954 : * in data->group rather than the original domain elements in data->domain.
2955 : * "pos" is the position in the original schedule tree where the modified
2956 : * "tree" will be attached.
2957 : *
2958 : * Let G_1 -> D_1 be the expansion of "tree" and G_2 -> D_2 the newly
2959 : * introduced expansion in a descendant of "tree".
2960 : * We first double-check that D_2 is a subset of D_1.
2961 : * Then we remove D_2 from the range of G_1 -> D_1 and add the mapping
2962 : * G_1 -> D_1 . D_2 -> G_2.
2963 : * Simmilarly, we restrict the domain of the contraction to the universe
2964 : * of the range of the updated expansion and add G_2 -> D_2 . D_1 -> G_1,
2965 : * attempting to remove the domain constraints of this additional part.
2966 : */
2967 0 : static __isl_give isl_schedule_tree *group_expansion(
2968 : __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_node *pos,
2969 : struct isl_schedule_group_data *data)
2970 : {
2971 : isl_union_set *domain;
2972 : isl_union_map *expansion, *umap;
2973 : isl_union_pw_multi_aff *contraction, *upma;
2974 : int is_subset;
2975 :
2976 0 : expansion = isl_schedule_tree_expansion_get_expansion(tree);
2977 0 : domain = isl_union_map_range(expansion);
2978 0 : is_subset = isl_union_set_is_subset(data->domain, domain);
2979 0 : isl_union_set_free(domain);
2980 0 : if (is_subset < 0)
2981 0 : return isl_schedule_tree_free(tree);
2982 0 : if (!is_subset)
2983 0 : isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
2984 : "grouped domain should be part "
2985 : "of outer expansion domain",
2986 : return isl_schedule_tree_free(tree));
2987 0 : expansion = isl_schedule_tree_expansion_get_expansion(tree);
2988 0 : umap = isl_union_map_from_union_pw_multi_aff(
2989 : isl_union_pw_multi_aff_copy(data->contraction));
2990 0 : umap = isl_union_map_apply_range(expansion, umap);
2991 0 : expansion = isl_schedule_tree_expansion_get_expansion(tree);
2992 0 : expansion = isl_union_map_subtract_range(expansion,
2993 : isl_union_set_copy(data->domain));
2994 0 : expansion = isl_union_map_union(expansion, umap);
2995 0 : umap = isl_union_map_universe(isl_union_map_copy(expansion));
2996 0 : domain = isl_union_map_range(umap);
2997 0 : contraction = isl_schedule_tree_expansion_get_contraction(tree);
2998 0 : umap = isl_union_map_from_union_pw_multi_aff(contraction);
2999 0 : umap = isl_union_map_apply_range(isl_union_map_copy(data->expansion),
3000 : umap);
3001 0 : upma = isl_union_pw_multi_aff_from_union_map(umap);
3002 0 : contraction = isl_schedule_tree_expansion_get_contraction(tree);
3003 0 : contraction = isl_union_pw_multi_aff_intersect_domain(contraction,
3004 : domain);
3005 0 : domain = isl_union_pw_multi_aff_domain(
3006 : isl_union_pw_multi_aff_copy(upma));
3007 0 : upma = isl_union_pw_multi_aff_gist(upma, domain);
3008 0 : contraction = isl_union_pw_multi_aff_union_add(contraction, upma);
3009 0 : tree = isl_schedule_tree_expansion_set_contraction_and_expansion(tree,
3010 : contraction, expansion);
3011 :
3012 0 : return tree;
3013 : }
3014 :
3015 : /* Update the tree root "tree" to refer to the group instances
3016 : * in data->group rather than the original domain elements in data->domain.
3017 : * "pos" is the position in the original schedule tree where the modified
3018 : * "tree" will be attached.
3019 : *
3020 : * If we have come across a domain or expansion node before (data->finished
3021 : * is set), then we no longer need perform any modifications.
3022 : *
3023 : * If "tree" is a filter, then we add data->group_universe to the filter.
3024 : * We also remove data->domain_universe from the filter if all the domain
3025 : * elements in this universe that reach the filter node are part of
3026 : * the elements that are being grouped by data->expansion.
3027 : * If "tree" is a band, domain or expansion, then it is handled
3028 : * in a separate function.
3029 : */
3030 0 : static __isl_give isl_schedule_tree *group_ancestor(
3031 : __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_node *pos,
3032 : void *user)
3033 : {
3034 0 : struct isl_schedule_group_data *data = user;
3035 : isl_union_set *domain;
3036 : int is_covered;
3037 :
3038 0 : if (!tree || !pos)
3039 0 : return isl_schedule_tree_free(tree);
3040 :
3041 0 : if (data->finished)
3042 0 : return tree;
3043 :
3044 0 : switch (isl_schedule_tree_get_type(tree)) {
3045 : case isl_schedule_node_error:
3046 0 : return isl_schedule_tree_free(tree);
3047 : case isl_schedule_node_extension:
3048 0 : isl_die(isl_schedule_tree_get_ctx(tree), isl_error_unsupported,
3049 : "grouping not allowed in extended tree",
3050 : return isl_schedule_tree_free(tree));
3051 : case isl_schedule_node_band:
3052 0 : tree = group_band(tree, pos, data);
3053 0 : break;
3054 : case isl_schedule_node_context:
3055 0 : tree = group_context(tree, pos, data);
3056 0 : break;
3057 : case isl_schedule_node_domain:
3058 0 : tree = group_domain(tree, pos, data);
3059 0 : data->finished = 1;
3060 0 : break;
3061 : case isl_schedule_node_filter:
3062 0 : domain = isl_schedule_node_get_domain(pos);
3063 0 : is_covered = locally_covered_by_domain(domain, data);
3064 0 : isl_union_set_free(domain);
3065 0 : if (is_covered < 0)
3066 0 : return isl_schedule_tree_free(tree);
3067 0 : domain = isl_schedule_tree_filter_get_filter(tree);
3068 0 : if (is_covered)
3069 0 : domain = isl_union_set_subtract(domain,
3070 : isl_union_set_copy(data->domain_universe));
3071 0 : domain = isl_union_set_union(domain,
3072 : isl_union_set_copy(data->group_universe));
3073 0 : tree = isl_schedule_tree_filter_set_filter(tree, domain);
3074 0 : break;
3075 : case isl_schedule_node_expansion:
3076 0 : tree = group_expansion(tree, pos, data);
3077 0 : data->finished = 1;
3078 0 : break;
3079 : case isl_schedule_node_leaf:
3080 : case isl_schedule_node_guard:
3081 : case isl_schedule_node_mark:
3082 : case isl_schedule_node_sequence:
3083 : case isl_schedule_node_set:
3084 0 : break;
3085 : }
3086 :
3087 0 : return tree;
3088 : }
3089 :
3090 : /* Group the domain elements that reach "node" into instances
3091 : * of a single statement with identifier "group_id".
3092 : * In particular, group the domain elements according to their
3093 : * prefix schedule.
3094 : *
3095 : * That is, introduce an expansion node with as contraction
3096 : * the prefix schedule (with the target space replaced by "group_id")
3097 : * and as expansion the inverse of this contraction (with its range
3098 : * intersected with the domain elements that reach "node").
3099 : * The outer nodes are then modified to refer to the group instances
3100 : * instead of the original domain elements.
3101 : *
3102 : * No instance of "group_id" is allowed to reach "node" prior
3103 : * to the grouping.
3104 : * No ancestor of "node" is allowed to be an extension node.
3105 : *
3106 : * Return a pointer to original node in tree, i.e., the child
3107 : * of the newly introduced expansion node.
3108 : */
3109 0 : __isl_give isl_schedule_node *isl_schedule_node_group(
3110 : __isl_take isl_schedule_node *node, __isl_take isl_id *group_id)
3111 : {
3112 0 : struct isl_schedule_group_data data = { 0 };
3113 : isl_space *space;
3114 : isl_union_set *domain;
3115 : isl_union_pw_multi_aff *contraction;
3116 : isl_union_map *expansion;
3117 : int disjoint;
3118 :
3119 0 : if (!node || !group_id)
3120 : goto error;
3121 0 : if (check_insert(node) < 0)
3122 0 : goto error;
3123 :
3124 0 : domain = isl_schedule_node_get_domain(node);
3125 0 : data.domain = isl_union_set_copy(domain);
3126 0 : data.domain_universe = isl_union_set_copy(domain);
3127 0 : data.domain_universe = isl_union_set_universe(data.domain_universe);
3128 :
3129 0 : data.dim = isl_schedule_node_get_schedule_depth(node);
3130 0 : if (data.dim == 0) {
3131 : isl_ctx *ctx;
3132 : isl_set *set;
3133 : isl_union_set *group;
3134 : isl_union_map *univ;
3135 :
3136 0 : ctx = isl_schedule_node_get_ctx(node);
3137 0 : space = isl_space_set_alloc(ctx, 0, 0);
3138 0 : space = isl_space_set_tuple_id(space, isl_dim_set, group_id);
3139 0 : set = isl_set_universe(isl_space_copy(space));
3140 0 : group = isl_union_set_from_set(set);
3141 0 : expansion = isl_union_map_from_domain_and_range(domain, group);
3142 0 : univ = isl_union_map_universe(isl_union_map_copy(expansion));
3143 0 : contraction = isl_union_pw_multi_aff_from_union_map(univ);
3144 0 : expansion = isl_union_map_reverse(expansion);
3145 : } else {
3146 : isl_multi_union_pw_aff *prefix;
3147 : isl_union_set *univ;
3148 :
3149 0 : prefix =
3150 : isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(node);
3151 0 : prefix = isl_multi_union_pw_aff_set_tuple_id(prefix,
3152 : isl_dim_set, group_id);
3153 0 : space = isl_multi_union_pw_aff_get_space(prefix);
3154 0 : contraction = isl_union_pw_multi_aff_from_multi_union_pw_aff(
3155 : prefix);
3156 0 : univ = isl_union_set_universe(isl_union_set_copy(domain));
3157 0 : contraction =
3158 : isl_union_pw_multi_aff_intersect_domain(contraction, univ);
3159 0 : expansion = isl_union_map_from_union_pw_multi_aff(
3160 : isl_union_pw_multi_aff_copy(contraction));
3161 0 : expansion = isl_union_map_reverse(expansion);
3162 0 : expansion = isl_union_map_intersect_range(expansion, domain);
3163 : }
3164 0 : space = isl_space_map_from_set(space);
3165 0 : data.sched = isl_multi_aff_identity(space);
3166 0 : data.group = isl_union_map_domain(isl_union_map_copy(expansion));
3167 0 : data.group = isl_union_set_coalesce(data.group);
3168 0 : data.group_universe = isl_union_set_copy(data.group);
3169 0 : data.group_universe = isl_union_set_universe(data.group_universe);
3170 0 : data.expansion = isl_union_map_copy(expansion);
3171 0 : data.contraction = isl_union_pw_multi_aff_copy(contraction);
3172 0 : node = isl_schedule_node_insert_expansion(node, contraction, expansion);
3173 :
3174 0 : disjoint = isl_union_set_is_disjoint(data.domain_universe,
3175 : data.group_universe);
3176 :
3177 0 : node = update_ancestors(node, &group_ancestor, &data);
3178 :
3179 0 : isl_union_set_free(data.domain);
3180 0 : isl_union_set_free(data.domain_universe);
3181 0 : isl_union_set_free(data.group);
3182 0 : isl_union_set_free(data.group_universe);
3183 0 : isl_multi_aff_free(data.sched);
3184 0 : isl_union_map_free(data.expansion);
3185 0 : isl_union_pw_multi_aff_free(data.contraction);
3186 :
3187 0 : node = isl_schedule_node_child(node, 0);
3188 :
3189 0 : if (!node || disjoint < 0)
3190 0 : return isl_schedule_node_free(node);
3191 0 : if (!disjoint)
3192 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
3193 : "group instances already reach node",
3194 : return isl_schedule_node_free(node));
3195 :
3196 0 : return node;
3197 : error:
3198 0 : isl_schedule_node_free(node);
3199 0 : isl_id_free(group_id);
3200 0 : return NULL;
3201 : }
3202 :
3203 : /* Compute the gist of the given band node with respect to "context".
3204 : */
3205 0 : __isl_give isl_schedule_node *isl_schedule_node_band_gist(
3206 : __isl_take isl_schedule_node *node, __isl_take isl_union_set *context)
3207 : {
3208 : isl_schedule_tree *tree;
3209 :
3210 0 : tree = isl_schedule_node_get_tree(node);
3211 0 : tree = isl_schedule_tree_band_gist(tree, context);
3212 0 : return isl_schedule_node_graft_tree(node, tree);
3213 : }
3214 :
3215 : /* Internal data structure for isl_schedule_node_gist.
3216 : * "n_expansion" is the number of outer expansion nodes
3217 : * with respect to the current position
3218 : * "filters" contains an element for each outer filter, expansion or
3219 : * extension node with respect to the current position, each representing
3220 : * the intersection of the previous element and the filter on the filter node
3221 : * or the expansion/extension of the previous element.
3222 : * The first element in the original context passed to isl_schedule_node_gist.
3223 : */
3224 : struct isl_node_gist_data {
3225 : int n_expansion;
3226 : isl_union_set_list *filters;
3227 : };
3228 :
3229 : /* Enter the expansion node "node" during a isl_schedule_node_gist traversal.
3230 : *
3231 : * In particular, add an extra element to data->filters containing
3232 : * the expansion of the previous element and replace the expansion
3233 : * and contraction on "node" by the gist with respect to these filters.
3234 : * Also keep track of the fact that we have entered another expansion.
3235 : */
3236 0 : static __isl_give isl_schedule_node *gist_enter_expansion(
3237 : __isl_take isl_schedule_node *node, struct isl_node_gist_data *data)
3238 : {
3239 : int n;
3240 : isl_union_set *inner;
3241 : isl_union_map *expansion;
3242 : isl_union_pw_multi_aff *contraction;
3243 :
3244 0 : data->n_expansion++;
3245 :
3246 0 : n = isl_union_set_list_n_union_set(data->filters);
3247 0 : inner = isl_union_set_list_get_union_set(data->filters, n - 1);
3248 0 : expansion = isl_schedule_node_expansion_get_expansion(node);
3249 0 : inner = isl_union_set_apply(inner, expansion);
3250 :
3251 0 : contraction = isl_schedule_node_expansion_get_contraction(node);
3252 0 : contraction = isl_union_pw_multi_aff_gist(contraction,
3253 : isl_union_set_copy(inner));
3254 :
3255 0 : data->filters = isl_union_set_list_add(data->filters, inner);
3256 :
3257 0 : inner = isl_union_set_list_get_union_set(data->filters, n - 1);
3258 0 : expansion = isl_schedule_node_expansion_get_expansion(node);
3259 0 : expansion = isl_union_map_gist_domain(expansion, inner);
3260 0 : node = isl_schedule_node_expansion_set_contraction_and_expansion(node,
3261 : contraction, expansion);
3262 :
3263 0 : return node;
3264 : }
3265 :
3266 : /* Leave the expansion node "node" during a isl_schedule_node_gist traversal.
3267 : *
3268 : * In particular, remove the element in data->filters that was added by
3269 : * gist_enter_expansion and decrement the number of outer expansions.
3270 : *
3271 : * The expansion has already been simplified in gist_enter_expansion.
3272 : * If this simplification results in an identity expansion, then
3273 : * it is removed here.
3274 : */
3275 0 : static __isl_give isl_schedule_node *gist_leave_expansion(
3276 : __isl_take isl_schedule_node *node, struct isl_node_gist_data *data)
3277 : {
3278 : int n;
3279 : isl_bool identity;
3280 : isl_union_map *expansion;
3281 :
3282 0 : expansion = isl_schedule_node_expansion_get_expansion(node);
3283 0 : identity = isl_union_map_is_identity(expansion);
3284 0 : isl_union_map_free(expansion);
3285 :
3286 0 : if (identity < 0)
3287 0 : node = isl_schedule_node_free(node);
3288 0 : else if (identity)
3289 0 : node = isl_schedule_node_delete(node);
3290 :
3291 0 : n = isl_union_set_list_n_union_set(data->filters);
3292 0 : data->filters = isl_union_set_list_drop(data->filters, n - 1, 1);
3293 :
3294 0 : data->n_expansion--;
3295 :
3296 0 : return node;
3297 : }
3298 :
3299 : /* Enter the extension node "node" during a isl_schedule_node_gist traversal.
3300 : *
3301 : * In particular, add an extra element to data->filters containing
3302 : * the union of the previous element with the additional domain elements
3303 : * introduced by the extension.
3304 : */
3305 0 : static __isl_give isl_schedule_node *gist_enter_extension(
3306 : __isl_take isl_schedule_node *node, struct isl_node_gist_data *data)
3307 : {
3308 : int n;
3309 : isl_union_set *inner, *extra;
3310 : isl_union_map *extension;
3311 :
3312 0 : n = isl_union_set_list_n_union_set(data->filters);
3313 0 : inner = isl_union_set_list_get_union_set(data->filters, n - 1);
3314 0 : extension = isl_schedule_node_extension_get_extension(node);
3315 0 : extra = isl_union_map_range(extension);
3316 0 : inner = isl_union_set_union(inner, extra);
3317 :
3318 0 : data->filters = isl_union_set_list_add(data->filters, inner);
3319 :
3320 0 : return node;
3321 : }
3322 :
3323 : /* Can we finish gisting at this node?
3324 : * That is, is the filter on the current filter node a subset of
3325 : * the original context passed to isl_schedule_node_gist?
3326 : * If we have gone through any expansions, then we cannot perform
3327 : * this test since the current domain elements are incomparable
3328 : * to the domain elements in the original context.
3329 : */
3330 0 : static int gist_done(__isl_keep isl_schedule_node *node,
3331 : struct isl_node_gist_data *data)
3332 : {
3333 : isl_union_set *filter, *outer;
3334 : int subset;
3335 :
3336 0 : if (data->n_expansion != 0)
3337 0 : return 0;
3338 :
3339 0 : filter = isl_schedule_node_filter_get_filter(node);
3340 0 : outer = isl_union_set_list_get_union_set(data->filters, 0);
3341 0 : subset = isl_union_set_is_subset(filter, outer);
3342 0 : isl_union_set_free(outer);
3343 0 : isl_union_set_free(filter);
3344 :
3345 0 : return subset;
3346 : }
3347 :
3348 : /* Callback for "traverse" to enter a node and to move
3349 : * to the deepest initial subtree that should be traversed
3350 : * by isl_schedule_node_gist.
3351 : *
3352 : * The "filters" list is extended by one element each time
3353 : * we come across a filter node by the result of intersecting
3354 : * the last element in the list with the filter on the filter node.
3355 : *
3356 : * If the filter on the current filter node is a subset of
3357 : * the original context passed to isl_schedule_node_gist,
3358 : * then there is no need to go into its subtree since it cannot
3359 : * be further simplified by the context. The "filters" list is
3360 : * still extended for consistency, but the actual value of the
3361 : * added element is immaterial since it will not be used.
3362 : *
3363 : * Otherwise, the filter on the current filter node is replaced by
3364 : * the gist of the original filter with respect to the intersection
3365 : * of the original context with the intermediate filters.
3366 : *
3367 : * If the new element in the "filters" list is empty, then no elements
3368 : * can reach the descendants of the current filter node. The subtree
3369 : * underneath the filter node is therefore removed.
3370 : *
3371 : * Each expansion node we come across is handled by
3372 : * gist_enter_expansion.
3373 : *
3374 : * Each extension node we come across is handled by
3375 : * gist_enter_extension.
3376 : */
3377 0 : static __isl_give isl_schedule_node *gist_enter(
3378 : __isl_take isl_schedule_node *node, void *user)
3379 : {
3380 0 : struct isl_node_gist_data *data = user;
3381 :
3382 : do {
3383 : isl_union_set *filter, *inner;
3384 : int done, empty;
3385 : int n;
3386 :
3387 0 : switch (isl_schedule_node_get_type(node)) {
3388 : case isl_schedule_node_error:
3389 0 : return isl_schedule_node_free(node);
3390 : case isl_schedule_node_expansion:
3391 0 : node = gist_enter_expansion(node, data);
3392 0 : continue;
3393 : case isl_schedule_node_extension:
3394 0 : node = gist_enter_extension(node, data);
3395 0 : continue;
3396 : case isl_schedule_node_band:
3397 : case isl_schedule_node_context:
3398 : case isl_schedule_node_domain:
3399 : case isl_schedule_node_guard:
3400 : case isl_schedule_node_leaf:
3401 : case isl_schedule_node_mark:
3402 : case isl_schedule_node_sequence:
3403 : case isl_schedule_node_set:
3404 0 : continue;
3405 : case isl_schedule_node_filter:
3406 0 : break;
3407 : }
3408 0 : done = gist_done(node, data);
3409 0 : filter = isl_schedule_node_filter_get_filter(node);
3410 0 : if (done < 0 || done) {
3411 0 : data->filters = isl_union_set_list_add(data->filters,
3412 : filter);
3413 0 : if (done < 0)
3414 0 : return isl_schedule_node_free(node);
3415 0 : return node;
3416 : }
3417 0 : n = isl_union_set_list_n_union_set(data->filters);
3418 0 : inner = isl_union_set_list_get_union_set(data->filters, n - 1);
3419 0 : filter = isl_union_set_gist(filter, isl_union_set_copy(inner));
3420 0 : node = isl_schedule_node_filter_set_filter(node,
3421 : isl_union_set_copy(filter));
3422 0 : filter = isl_union_set_intersect(filter, inner);
3423 0 : empty = isl_union_set_is_empty(filter);
3424 0 : data->filters = isl_union_set_list_add(data->filters, filter);
3425 0 : if (empty < 0)
3426 0 : return isl_schedule_node_free(node);
3427 0 : if (!empty)
3428 0 : continue;
3429 0 : node = isl_schedule_node_child(node, 0);
3430 0 : node = isl_schedule_node_cut(node);
3431 0 : node = isl_schedule_node_parent(node);
3432 0 : return node;
3433 0 : } while (isl_schedule_node_has_children(node) &&
3434 0 : (node = isl_schedule_node_first_child(node)) != NULL);
3435 :
3436 0 : return node;
3437 : }
3438 :
3439 : /* Callback for "traverse" to leave a node for isl_schedule_node_gist.
3440 : *
3441 : * In particular, if the current node is a filter node, then we remove
3442 : * the element on the "filters" list that was added when we entered
3443 : * the node. There is no need to compute any gist here, since we
3444 : * already did that when we entered the node.
3445 : *
3446 : * Expansion nodes are handled by gist_leave_expansion.
3447 : *
3448 : * If the current node is an extension, then remove the element
3449 : * in data->filters that was added by gist_enter_extension.
3450 : *
3451 : * If the current node is a band node, then we compute the gist of
3452 : * the band node with respect to the intersection of the original context
3453 : * and the intermediate filters.
3454 : *
3455 : * If the current node is a sequence or set node, then some of
3456 : * the filter children may have become empty and so they are removed.
3457 : * If only one child is left, then the set or sequence node along with
3458 : * the single remaining child filter is removed. The filter can be
3459 : * removed because the filters on a sequence or set node are supposed
3460 : * to partition the incoming domain instances.
3461 : * In principle, it should then be impossible for there to be zero
3462 : * remaining children, but should this happen, we replace the entire
3463 : * subtree with an empty filter.
3464 : */
3465 0 : static __isl_give isl_schedule_node *gist_leave(
3466 : __isl_take isl_schedule_node *node, void *user)
3467 : {
3468 0 : struct isl_node_gist_data *data = user;
3469 : isl_schedule_tree *tree;
3470 : int i, n;
3471 : isl_union_set *filter;
3472 :
3473 0 : switch (isl_schedule_node_get_type(node)) {
3474 : case isl_schedule_node_error:
3475 0 : return isl_schedule_node_free(node);
3476 : case isl_schedule_node_expansion:
3477 0 : node = gist_leave_expansion(node, data);
3478 0 : break;
3479 : case isl_schedule_node_extension:
3480 : case isl_schedule_node_filter:
3481 0 : n = isl_union_set_list_n_union_set(data->filters);
3482 0 : data->filters = isl_union_set_list_drop(data->filters,
3483 0 : n - 1, 1);
3484 0 : break;
3485 : case isl_schedule_node_band:
3486 0 : n = isl_union_set_list_n_union_set(data->filters);
3487 0 : filter = isl_union_set_list_get_union_set(data->filters, n - 1);
3488 0 : node = isl_schedule_node_band_gist(node, filter);
3489 0 : break;
3490 : case isl_schedule_node_set:
3491 : case isl_schedule_node_sequence:
3492 0 : tree = isl_schedule_node_get_tree(node);
3493 0 : n = isl_schedule_tree_n_children(tree);
3494 0 : for (i = n - 1; i >= 0; --i) {
3495 : isl_schedule_tree *child;
3496 : isl_union_set *filter;
3497 : int empty;
3498 :
3499 0 : child = isl_schedule_tree_get_child(tree, i);
3500 0 : filter = isl_schedule_tree_filter_get_filter(child);
3501 0 : empty = isl_union_set_is_empty(filter);
3502 0 : isl_union_set_free(filter);
3503 0 : isl_schedule_tree_free(child);
3504 0 : if (empty < 0)
3505 0 : tree = isl_schedule_tree_free(tree);
3506 0 : else if (empty)
3507 0 : tree = isl_schedule_tree_drop_child(tree, i);
3508 : }
3509 0 : n = isl_schedule_tree_n_children(tree);
3510 0 : node = isl_schedule_node_graft_tree(node, tree);
3511 0 : if (n == 1) {
3512 0 : node = isl_schedule_node_delete(node);
3513 0 : node = isl_schedule_node_delete(node);
3514 0 : } else if (n == 0) {
3515 : isl_space *space;
3516 :
3517 0 : filter =
3518 0 : isl_union_set_list_get_union_set(data->filters, 0);
3519 0 : space = isl_union_set_get_space(filter);
3520 0 : isl_union_set_free(filter);
3521 0 : filter = isl_union_set_empty(space);
3522 0 : node = isl_schedule_node_cut(node);
3523 0 : node = isl_schedule_node_insert_filter(node, filter);
3524 : }
3525 0 : break;
3526 : case isl_schedule_node_context:
3527 : case isl_schedule_node_domain:
3528 : case isl_schedule_node_guard:
3529 : case isl_schedule_node_leaf:
3530 : case isl_schedule_node_mark:
3531 0 : break;
3532 : }
3533 :
3534 0 : return node;
3535 : }
3536 :
3537 : /* Compute the gist of the subtree at "node" with respect to
3538 : * the reaching domain elements in "context".
3539 : * In particular, compute the gist of all band and filter nodes
3540 : * in the subtree with respect to "context". Children of set or sequence
3541 : * nodes that end up with an empty filter are removed completely.
3542 : *
3543 : * We keep track of the intersection of "context" with all outer filters
3544 : * of the current node within the subtree in the final element of "filters".
3545 : * Initially, this list contains the single element "context" and it is
3546 : * extended or shortened each time we enter or leave a filter node.
3547 : */
3548 0 : __isl_give isl_schedule_node *isl_schedule_node_gist(
3549 : __isl_take isl_schedule_node *node, __isl_take isl_union_set *context)
3550 : {
3551 : struct isl_node_gist_data data;
3552 :
3553 0 : data.n_expansion = 0;
3554 0 : data.filters = isl_union_set_list_from_union_set(context);
3555 0 : node = traverse(node, &gist_enter, &gist_leave, &data);
3556 0 : isl_union_set_list_free(data.filters);
3557 0 : return node;
3558 : }
3559 :
3560 : /* Intersect the domain of domain node "node" with "domain".
3561 : *
3562 : * If the domain of "node" is already a subset of "domain",
3563 : * then nothing needs to be changed.
3564 : *
3565 : * Otherwise, we replace the domain of the domain node by the intersection
3566 : * and simplify the subtree rooted at "node" with respect to this intersection.
3567 : */
3568 0 : __isl_give isl_schedule_node *isl_schedule_node_domain_intersect_domain(
3569 : __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain)
3570 : {
3571 : isl_schedule_tree *tree;
3572 : isl_union_set *uset;
3573 : int is_subset;
3574 :
3575 0 : if (!node || !domain)
3576 : goto error;
3577 :
3578 0 : uset = isl_schedule_tree_domain_get_domain(node->tree);
3579 0 : is_subset = isl_union_set_is_subset(uset, domain);
3580 0 : isl_union_set_free(uset);
3581 0 : if (is_subset < 0)
3582 0 : goto error;
3583 0 : if (is_subset) {
3584 0 : isl_union_set_free(domain);
3585 0 : return node;
3586 : }
3587 :
3588 0 : tree = isl_schedule_tree_copy(node->tree);
3589 0 : uset = isl_schedule_tree_domain_get_domain(tree);
3590 0 : uset = isl_union_set_intersect(uset, domain);
3591 0 : tree = isl_schedule_tree_domain_set_domain(tree,
3592 : isl_union_set_copy(uset));
3593 0 : node = isl_schedule_node_graft_tree(node, tree);
3594 :
3595 0 : node = isl_schedule_node_child(node, 0);
3596 0 : node = isl_schedule_node_gist(node, uset);
3597 0 : node = isl_schedule_node_parent(node);
3598 :
3599 0 : return node;
3600 : error:
3601 0 : isl_schedule_node_free(node);
3602 0 : isl_union_set_free(domain);
3603 0 : return NULL;
3604 : }
3605 :
3606 : /* Replace the domain of domain node "node" with the gist
3607 : * of the original domain with respect to the parameter domain "context".
3608 : */
3609 0 : __isl_give isl_schedule_node *isl_schedule_node_domain_gist_params(
3610 : __isl_take isl_schedule_node *node, __isl_take isl_set *context)
3611 : {
3612 : isl_union_set *domain;
3613 : isl_schedule_tree *tree;
3614 :
3615 0 : if (!node || !context)
3616 : goto error;
3617 :
3618 0 : tree = isl_schedule_tree_copy(node->tree);
3619 0 : domain = isl_schedule_tree_domain_get_domain(node->tree);
3620 0 : domain = isl_union_set_gist_params(domain, context);
3621 0 : tree = isl_schedule_tree_domain_set_domain(tree, domain);
3622 0 : node = isl_schedule_node_graft_tree(node, tree);
3623 :
3624 0 : return node;
3625 : error:
3626 0 : isl_schedule_node_free(node);
3627 0 : isl_set_free(context);
3628 0 : return NULL;
3629 : }
3630 :
3631 : /* Internal data structure for isl_schedule_node_get_subtree_expansion.
3632 : * "expansions" contains a list of accumulated expansions
3633 : * for each outer expansion, set or sequence node. The first element
3634 : * in the list is an identity mapping on the reaching domain elements.
3635 : * "res" collects the results.
3636 : */
3637 : struct isl_subtree_expansion_data {
3638 : isl_union_map_list *expansions;
3639 : isl_union_map *res;
3640 : };
3641 :
3642 : /* Callback for "traverse" to enter a node and to move
3643 : * to the deepest initial subtree that should be traversed
3644 : * by isl_schedule_node_get_subtree_expansion.
3645 : *
3646 : * Whenever we come across an expansion node, the last element
3647 : * of data->expansions is combined with the expansion
3648 : * on the expansion node.
3649 : *
3650 : * Whenever we come across a filter node that is the child
3651 : * of a set or sequence node, data->expansions is extended
3652 : * with a new element that restricts the previous element
3653 : * to the elements selected by the filter.
3654 : * The previous element can then be reused while backtracking.
3655 : */
3656 0 : static __isl_give isl_schedule_node *subtree_expansion_enter(
3657 : __isl_take isl_schedule_node *node, void *user)
3658 : {
3659 0 : struct isl_subtree_expansion_data *data = user;
3660 :
3661 : do {
3662 : enum isl_schedule_node_type type;
3663 : isl_union_set *filter;
3664 : isl_union_map *inner, *expansion;
3665 : int n;
3666 :
3667 0 : switch (isl_schedule_node_get_type(node)) {
3668 : case isl_schedule_node_error:
3669 0 : return isl_schedule_node_free(node);
3670 : case isl_schedule_node_filter:
3671 0 : type = isl_schedule_node_get_parent_type(node);
3672 0 : if (type != isl_schedule_node_set &&
3673 : type != isl_schedule_node_sequence)
3674 0 : break;
3675 0 : filter = isl_schedule_node_filter_get_filter(node);
3676 0 : n = isl_union_map_list_n_union_map(data->expansions);
3677 0 : inner =
3678 0 : isl_union_map_list_get_union_map(data->expansions,
3679 : n - 1);
3680 0 : inner = isl_union_map_intersect_range(inner, filter);
3681 0 : data->expansions =
3682 0 : isl_union_map_list_add(data->expansions, inner);
3683 0 : break;
3684 : case isl_schedule_node_expansion:
3685 0 : n = isl_union_map_list_n_union_map(data->expansions);
3686 0 : expansion =
3687 : isl_schedule_node_expansion_get_expansion(node);
3688 0 : inner =
3689 0 : isl_union_map_list_get_union_map(data->expansions,
3690 : n - 1);
3691 0 : inner = isl_union_map_apply_range(inner, expansion);
3692 0 : data->expansions =
3693 0 : isl_union_map_list_set_union_map(data->expansions,
3694 : n - 1, inner);
3695 0 : break;
3696 : case isl_schedule_node_band:
3697 : case isl_schedule_node_context:
3698 : case isl_schedule_node_domain:
3699 : case isl_schedule_node_extension:
3700 : case isl_schedule_node_guard:
3701 : case isl_schedule_node_leaf:
3702 : case isl_schedule_node_mark:
3703 : case isl_schedule_node_sequence:
3704 : case isl_schedule_node_set:
3705 0 : break;
3706 : }
3707 0 : } while (isl_schedule_node_has_children(node) &&
3708 0 : (node = isl_schedule_node_first_child(node)) != NULL);
3709 :
3710 0 : return node;
3711 : }
3712 :
3713 : /* Callback for "traverse" to leave a node for
3714 : * isl_schedule_node_get_subtree_expansion.
3715 : *
3716 : * If we come across a filter node that is the child
3717 : * of a set or sequence node, then we remove the element
3718 : * of data->expansions that was added in subtree_expansion_enter.
3719 : *
3720 : * If we reach a leaf node, then the accumulated expansion is
3721 : * added to data->res.
3722 : */
3723 0 : static __isl_give isl_schedule_node *subtree_expansion_leave(
3724 : __isl_take isl_schedule_node *node, void *user)
3725 : {
3726 0 : struct isl_subtree_expansion_data *data = user;
3727 : int n;
3728 : isl_union_map *inner;
3729 : enum isl_schedule_node_type type;
3730 :
3731 0 : switch (isl_schedule_node_get_type(node)) {
3732 : case isl_schedule_node_error:
3733 0 : return isl_schedule_node_free(node);
3734 : case isl_schedule_node_filter:
3735 0 : type = isl_schedule_node_get_parent_type(node);
3736 0 : if (type != isl_schedule_node_set &&
3737 : type != isl_schedule_node_sequence)
3738 0 : break;
3739 0 : n = isl_union_map_list_n_union_map(data->expansions);
3740 0 : data->expansions = isl_union_map_list_drop(data->expansions,
3741 0 : n - 1, 1);
3742 0 : break;
3743 : case isl_schedule_node_leaf:
3744 0 : n = isl_union_map_list_n_union_map(data->expansions);
3745 0 : inner = isl_union_map_list_get_union_map(data->expansions,
3746 : n - 1);
3747 0 : data->res = isl_union_map_union(data->res, inner);
3748 0 : break;
3749 : case isl_schedule_node_band:
3750 : case isl_schedule_node_context:
3751 : case isl_schedule_node_domain:
3752 : case isl_schedule_node_expansion:
3753 : case isl_schedule_node_extension:
3754 : case isl_schedule_node_guard:
3755 : case isl_schedule_node_mark:
3756 : case isl_schedule_node_sequence:
3757 : case isl_schedule_node_set:
3758 0 : break;
3759 : }
3760 :
3761 0 : return node;
3762 : }
3763 :
3764 : /* Return a mapping from the domain elements that reach "node"
3765 : * to the corresponding domain elements in the leaves of the subtree
3766 : * rooted at "node" obtained by composing the intermediate expansions.
3767 : *
3768 : * We start out with an identity mapping between the domain elements
3769 : * that reach "node" and compose it with all the expansions
3770 : * on a path from "node" to a leaf while traversing the subtree.
3771 : * Within the children of an a sequence or set node, the
3772 : * accumulated expansion is restricted to the elements selected
3773 : * by the filter child.
3774 : */
3775 0 : __isl_give isl_union_map *isl_schedule_node_get_subtree_expansion(
3776 : __isl_keep isl_schedule_node *node)
3777 : {
3778 : struct isl_subtree_expansion_data data;
3779 : isl_space *space;
3780 : isl_union_set *domain;
3781 : isl_union_map *expansion;
3782 :
3783 0 : if (!node)
3784 0 : return NULL;
3785 :
3786 0 : domain = isl_schedule_node_get_universe_domain(node);
3787 0 : space = isl_union_set_get_space(domain);
3788 0 : expansion = isl_union_set_identity(domain);
3789 0 : data.res = isl_union_map_empty(space);
3790 0 : data.expansions = isl_union_map_list_from_union_map(expansion);
3791 :
3792 0 : node = isl_schedule_node_copy(node);
3793 0 : node = traverse(node, &subtree_expansion_enter,
3794 : &subtree_expansion_leave, &data);
3795 0 : if (!node)
3796 0 : data.res = isl_union_map_free(data.res);
3797 0 : isl_schedule_node_free(node);
3798 :
3799 0 : isl_union_map_list_free(data.expansions);
3800 :
3801 0 : return data.res;
3802 : }
3803 :
3804 : /* Internal data structure for isl_schedule_node_get_subtree_contraction.
3805 : * "contractions" contains a list of accumulated contractions
3806 : * for each outer expansion, set or sequence node. The first element
3807 : * in the list is an identity mapping on the reaching domain elements.
3808 : * "res" collects the results.
3809 : */
3810 : struct isl_subtree_contraction_data {
3811 : isl_union_pw_multi_aff_list *contractions;
3812 : isl_union_pw_multi_aff *res;
3813 : };
3814 :
3815 : /* Callback for "traverse" to enter a node and to move
3816 : * to the deepest initial subtree that should be traversed
3817 : * by isl_schedule_node_get_subtree_contraction.
3818 : *
3819 : * Whenever we come across an expansion node, the last element
3820 : * of data->contractions is combined with the contraction
3821 : * on the expansion node.
3822 : *
3823 : * Whenever we come across a filter node that is the child
3824 : * of a set or sequence node, data->contractions is extended
3825 : * with a new element that restricts the previous element
3826 : * to the elements selected by the filter.
3827 : * The previous element can then be reused while backtracking.
3828 : */
3829 0 : static __isl_give isl_schedule_node *subtree_contraction_enter(
3830 : __isl_take isl_schedule_node *node, void *user)
3831 : {
3832 0 : struct isl_subtree_contraction_data *data = user;
3833 :
3834 : do {
3835 : enum isl_schedule_node_type type;
3836 : isl_union_set *filter;
3837 : isl_union_pw_multi_aff *inner, *contraction;
3838 : int n;
3839 :
3840 0 : switch (isl_schedule_node_get_type(node)) {
3841 : case isl_schedule_node_error:
3842 0 : return isl_schedule_node_free(node);
3843 : case isl_schedule_node_filter:
3844 0 : type = isl_schedule_node_get_parent_type(node);
3845 0 : if (type != isl_schedule_node_set &&
3846 : type != isl_schedule_node_sequence)
3847 0 : break;
3848 0 : filter = isl_schedule_node_filter_get_filter(node);
3849 0 : n = isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3850 : data->contractions);
3851 0 : inner =
3852 0 : isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3853 : data->contractions, n - 1);
3854 0 : inner = isl_union_pw_multi_aff_intersect_domain(inner,
3855 : filter);
3856 0 : data->contractions =
3857 0 : isl_union_pw_multi_aff_list_add(data->contractions,
3858 : inner);
3859 0 : break;
3860 : case isl_schedule_node_expansion:
3861 0 : n = isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3862 : data->contractions);
3863 0 : contraction =
3864 : isl_schedule_node_expansion_get_contraction(node);
3865 0 : inner =
3866 0 : isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3867 : data->contractions, n - 1);
3868 0 : inner =
3869 : isl_union_pw_multi_aff_pullback_union_pw_multi_aff(
3870 : inner, contraction);
3871 0 : data->contractions =
3872 0 : isl_union_pw_multi_aff_list_set_union_pw_multi_aff(
3873 0 : data->contractions, n - 1, inner);
3874 0 : break;
3875 : case isl_schedule_node_band:
3876 : case isl_schedule_node_context:
3877 : case isl_schedule_node_domain:
3878 : case isl_schedule_node_extension:
3879 : case isl_schedule_node_guard:
3880 : case isl_schedule_node_leaf:
3881 : case isl_schedule_node_mark:
3882 : case isl_schedule_node_sequence:
3883 : case isl_schedule_node_set:
3884 0 : break;
3885 : }
3886 0 : } while (isl_schedule_node_has_children(node) &&
3887 0 : (node = isl_schedule_node_first_child(node)) != NULL);
3888 :
3889 0 : return node;
3890 : }
3891 :
3892 : /* Callback for "traverse" to leave a node for
3893 : * isl_schedule_node_get_subtree_contraction.
3894 : *
3895 : * If we come across a filter node that is the child
3896 : * of a set or sequence node, then we remove the element
3897 : * of data->contractions that was added in subtree_contraction_enter.
3898 : *
3899 : * If we reach a leaf node, then the accumulated contraction is
3900 : * added to data->res.
3901 : */
3902 0 : static __isl_give isl_schedule_node *subtree_contraction_leave(
3903 : __isl_take isl_schedule_node *node, void *user)
3904 : {
3905 0 : struct isl_subtree_contraction_data *data = user;
3906 : int n;
3907 : isl_union_pw_multi_aff *inner;
3908 : enum isl_schedule_node_type type;
3909 :
3910 0 : switch (isl_schedule_node_get_type(node)) {
3911 : case isl_schedule_node_error:
3912 0 : return isl_schedule_node_free(node);
3913 : case isl_schedule_node_filter:
3914 0 : type = isl_schedule_node_get_parent_type(node);
3915 0 : if (type != isl_schedule_node_set &&
3916 : type != isl_schedule_node_sequence)
3917 0 : break;
3918 0 : n = isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3919 : data->contractions);
3920 0 : data->contractions =
3921 0 : isl_union_pw_multi_aff_list_drop(data->contractions,
3922 0 : n - 1, 1);
3923 0 : break;
3924 : case isl_schedule_node_leaf:
3925 0 : n = isl_union_pw_multi_aff_list_n_union_pw_multi_aff(
3926 : data->contractions);
3927 0 : inner = isl_union_pw_multi_aff_list_get_union_pw_multi_aff(
3928 : data->contractions, n - 1);
3929 0 : data->res = isl_union_pw_multi_aff_union_add(data->res, inner);
3930 0 : break;
3931 : case isl_schedule_node_band:
3932 : case isl_schedule_node_context:
3933 : case isl_schedule_node_domain:
3934 : case isl_schedule_node_expansion:
3935 : case isl_schedule_node_extension:
3936 : case isl_schedule_node_guard:
3937 : case isl_schedule_node_mark:
3938 : case isl_schedule_node_sequence:
3939 : case isl_schedule_node_set:
3940 0 : break;
3941 : }
3942 :
3943 0 : return node;
3944 : }
3945 :
3946 : /* Return a mapping from the domain elements in the leaves of the subtree
3947 : * rooted at "node" to the corresponding domain elements that reach "node"
3948 : * obtained by composing the intermediate contractions.
3949 : *
3950 : * We start out with an identity mapping between the domain elements
3951 : * that reach "node" and compose it with all the contractions
3952 : * on a path from "node" to a leaf while traversing the subtree.
3953 : * Within the children of an a sequence or set node, the
3954 : * accumulated contraction is restricted to the elements selected
3955 : * by the filter child.
3956 : */
3957 0 : __isl_give isl_union_pw_multi_aff *isl_schedule_node_get_subtree_contraction(
3958 : __isl_keep isl_schedule_node *node)
3959 : {
3960 : struct isl_subtree_contraction_data data;
3961 : isl_space *space;
3962 : isl_union_set *domain;
3963 : isl_union_pw_multi_aff *contraction;
3964 :
3965 0 : if (!node)
3966 0 : return NULL;
3967 :
3968 0 : domain = isl_schedule_node_get_universe_domain(node);
3969 0 : space = isl_union_set_get_space(domain);
3970 0 : contraction = isl_union_set_identity_union_pw_multi_aff(domain);
3971 0 : data.res = isl_union_pw_multi_aff_empty(space);
3972 0 : data.contractions =
3973 0 : isl_union_pw_multi_aff_list_from_union_pw_multi_aff(contraction);
3974 :
3975 0 : node = isl_schedule_node_copy(node);
3976 0 : node = traverse(node, &subtree_contraction_enter,
3977 : &subtree_contraction_leave, &data);
3978 0 : if (!node)
3979 0 : data.res = isl_union_pw_multi_aff_free(data.res);
3980 0 : isl_schedule_node_free(node);
3981 :
3982 0 : isl_union_pw_multi_aff_list_free(data.contractions);
3983 :
3984 0 : return data.res;
3985 : }
3986 :
3987 : /* Do the nearest "n" ancestors of "node" have the types given in "types"
3988 : * (starting at the parent of "node")?
3989 : */
3990 0 : static int has_ancestors(__isl_keep isl_schedule_node *node,
3991 : int n, enum isl_schedule_node_type *types)
3992 : {
3993 : int i, n_ancestor;
3994 :
3995 0 : if (!node)
3996 0 : return -1;
3997 :
3998 0 : n_ancestor = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
3999 0 : if (n_ancestor < n)
4000 0 : return 0;
4001 :
4002 0 : for (i = 0; i < n; ++i) {
4003 : isl_schedule_tree *tree;
4004 : int correct_type;
4005 :
4006 0 : tree = isl_schedule_tree_list_get_schedule_tree(node->ancestors,
4007 0 : n_ancestor - 1 - i);
4008 0 : if (!tree)
4009 0 : return -1;
4010 0 : correct_type = isl_schedule_tree_get_type(tree) == types[i];
4011 0 : isl_schedule_tree_free(tree);
4012 0 : if (!correct_type)
4013 0 : return 0;
4014 : }
4015 :
4016 0 : return 1;
4017 : }
4018 :
4019 : /* Given a node "node" that appears in an extension (i.e., it is the child
4020 : * of a filter in a sequence inside an extension node), are the spaces
4021 : * of the extension specified by "extension" disjoint from those
4022 : * of both the original extension and the domain elements that reach
4023 : * that original extension?
4024 : */
4025 0 : static int is_disjoint_extension(__isl_keep isl_schedule_node *node,
4026 : __isl_keep isl_union_map *extension)
4027 : {
4028 : isl_union_map *old;
4029 : isl_union_set *domain;
4030 : int empty;
4031 :
4032 0 : node = isl_schedule_node_copy(node);
4033 0 : node = isl_schedule_node_parent(node);
4034 0 : node = isl_schedule_node_parent(node);
4035 0 : node = isl_schedule_node_parent(node);
4036 0 : old = isl_schedule_node_extension_get_extension(node);
4037 0 : domain = isl_schedule_node_get_universe_domain(node);
4038 0 : isl_schedule_node_free(node);
4039 0 : old = isl_union_map_universe(old);
4040 0 : domain = isl_union_set_union(domain, isl_union_map_range(old));
4041 0 : extension = isl_union_map_copy(extension);
4042 0 : extension = isl_union_map_intersect_range(extension, domain);
4043 0 : empty = isl_union_map_is_empty(extension);
4044 0 : isl_union_map_free(extension);
4045 :
4046 0 : return empty;
4047 : }
4048 :
4049 : /* Given a node "node" that is governed by an extension node, extend
4050 : * that extension node with "extension".
4051 : *
4052 : * In particular, "node" is the child of a filter in a sequence that
4053 : * is in turn a child of an extension node. Extend that extension node
4054 : * with "extension".
4055 : *
4056 : * Return a pointer to the parent of the original node (i.e., a filter).
4057 : */
4058 0 : static __isl_give isl_schedule_node *extend_extension(
4059 : __isl_take isl_schedule_node *node, __isl_take isl_union_map *extension)
4060 : {
4061 : int pos;
4062 : int disjoint;
4063 : isl_union_map *node_extension;
4064 :
4065 0 : node = isl_schedule_node_parent(node);
4066 0 : pos = isl_schedule_node_get_child_position(node);
4067 0 : node = isl_schedule_node_parent(node);
4068 0 : node = isl_schedule_node_parent(node);
4069 0 : node_extension = isl_schedule_node_extension_get_extension(node);
4070 0 : disjoint = isl_union_map_is_disjoint(extension, node_extension);
4071 0 : extension = isl_union_map_union(extension, node_extension);
4072 0 : node = isl_schedule_node_extension_set_extension(node, extension);
4073 0 : node = isl_schedule_node_child(node, 0);
4074 0 : node = isl_schedule_node_child(node, pos);
4075 :
4076 0 : if (disjoint < 0)
4077 0 : return isl_schedule_node_free(node);
4078 0 : if (!node)
4079 0 : return NULL;
4080 0 : if (!disjoint)
4081 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
4082 : "extension domain should be disjoint from earlier "
4083 : "extensions", return isl_schedule_node_free(node));
4084 :
4085 0 : return node;
4086 : }
4087 :
4088 : /* Return the universe of "uset" if this universe is disjoint from "ref".
4089 : * Otherwise, return "uset".
4090 : *
4091 : * Also check if "uset" itself is disjoint from "ref", reporting
4092 : * an error if it is not.
4093 : */
4094 0 : static __isl_give isl_union_set *replace_by_universe_if_disjoint(
4095 : __isl_take isl_union_set *uset, __isl_keep isl_union_set *ref)
4096 : {
4097 : int disjoint;
4098 : isl_union_set *universe;
4099 :
4100 0 : disjoint = isl_union_set_is_disjoint(uset, ref);
4101 0 : if (disjoint < 0)
4102 0 : return isl_union_set_free(uset);
4103 0 : if (!disjoint)
4104 0 : isl_die(isl_union_set_get_ctx(uset), isl_error_invalid,
4105 : "extension domain should be disjoint from "
4106 : "current domain", return isl_union_set_free(uset));
4107 :
4108 0 : universe = isl_union_set_universe(isl_union_set_copy(uset));
4109 0 : disjoint = isl_union_set_is_disjoint(universe, ref);
4110 0 : if (disjoint >= 0 && disjoint) {
4111 0 : isl_union_set_free(uset);
4112 0 : return universe;
4113 : }
4114 0 : isl_union_set_free(universe);
4115 :
4116 0 : if (disjoint < 0)
4117 0 : return isl_union_set_free(uset);
4118 0 : return uset;
4119 : }
4120 :
4121 : /* Insert an extension node on top of "node" with extension "extension".
4122 : * In addition, insert a filter that separates node from the extension
4123 : * between the extension node and "node".
4124 : * Return a pointer to the inserted filter node.
4125 : *
4126 : * If "node" already appears in an extension (i.e., if it is the child
4127 : * of a filter in a sequence inside an extension node), then extend that
4128 : * extension with "extension" instead.
4129 : * In this case, a pointer to the original filter node is returned.
4130 : * Note that if some of the elements in the new extension live in the
4131 : * same space as those of the original extension or the domain elements
4132 : * reaching the original extension, then we insert a new extension anyway.
4133 : * Otherwise, we would have to adjust the filters in the sequence child
4134 : * of the extension to ensure that the elements in the new extension
4135 : * are filtered out.
4136 : */
4137 0 : static __isl_give isl_schedule_node *insert_extension(
4138 : __isl_take isl_schedule_node *node, __isl_take isl_union_map *extension)
4139 : {
4140 0 : enum isl_schedule_node_type ancestors[] =
4141 : { isl_schedule_node_filter, isl_schedule_node_sequence,
4142 : isl_schedule_node_extension };
4143 : isl_union_set *domain;
4144 : isl_union_set *filter;
4145 : int in_ext;
4146 :
4147 0 : in_ext = has_ancestors(node, 3, ancestors);
4148 0 : if (in_ext < 0)
4149 0 : goto error;
4150 0 : if (in_ext) {
4151 : int disjoint;
4152 :
4153 0 : disjoint = is_disjoint_extension(node, extension);
4154 0 : if (disjoint < 0)
4155 0 : goto error;
4156 0 : if (disjoint)
4157 0 : return extend_extension(node, extension);
4158 : }
4159 :
4160 0 : filter = isl_schedule_node_get_domain(node);
4161 0 : domain = isl_union_map_range(isl_union_map_copy(extension));
4162 0 : filter = replace_by_universe_if_disjoint(filter, domain);
4163 0 : isl_union_set_free(domain);
4164 :
4165 0 : node = isl_schedule_node_insert_filter(node, filter);
4166 0 : node = isl_schedule_node_insert_extension(node, extension);
4167 0 : node = isl_schedule_node_child(node, 0);
4168 0 : return node;
4169 : error:
4170 0 : isl_schedule_node_free(node);
4171 0 : isl_union_map_free(extension);
4172 0 : return NULL;
4173 : }
4174 :
4175 : /* Replace the subtree that "node" points to by "tree" (which has
4176 : * a sequence root with two children), except if the parent of "node"
4177 : * is a sequence as well, in which case "tree" is spliced at the position
4178 : * of "node" in its parent.
4179 : * Return a pointer to the child of the "tree_pos" (filter) child of "tree"
4180 : * in the updated schedule tree.
4181 : */
4182 0 : static __isl_give isl_schedule_node *graft_or_splice(
4183 : __isl_take isl_schedule_node *node, __isl_take isl_schedule_tree *tree,
4184 : int tree_pos)
4185 : {
4186 : int pos;
4187 :
4188 0 : if (isl_schedule_node_get_parent_type(node) ==
4189 : isl_schedule_node_sequence) {
4190 0 : pos = isl_schedule_node_get_child_position(node);
4191 0 : node = isl_schedule_node_parent(node);
4192 0 : node = isl_schedule_node_sequence_splice(node, pos, tree);
4193 : } else {
4194 0 : pos = 0;
4195 0 : node = isl_schedule_node_graft_tree(node, tree);
4196 : }
4197 0 : node = isl_schedule_node_child(node, pos + tree_pos);
4198 0 : node = isl_schedule_node_child(node, 0);
4199 :
4200 0 : return node;
4201 : }
4202 :
4203 : /* Insert a node "graft" into the schedule tree of "node" such that it
4204 : * is executed before (if "before" is set) or after (if "before" is not set)
4205 : * the node that "node" points to.
4206 : * The root of "graft" is an extension node.
4207 : * Return a pointer to the node that "node" pointed to.
4208 : *
4209 : * We first insert an extension node on top of "node" (or extend
4210 : * the extension node if there already is one), with a filter on "node"
4211 : * separating it from the extension.
4212 : * We then insert a filter in the graft to separate it from the original
4213 : * domain elements and combine the original and new tree in a sequence.
4214 : * If we have extended an extension node, then the children of this
4215 : * sequence are spliced in the sequence of the extended extension
4216 : * at the position where "node" appears in the original extension.
4217 : * Otherwise, the sequence pair is attached to the new extension node.
4218 : */
4219 0 : static __isl_give isl_schedule_node *graft_extension(
4220 : __isl_take isl_schedule_node *node, __isl_take isl_schedule_node *graft,
4221 : int before)
4222 : {
4223 : isl_union_map *extension;
4224 : isl_union_set *graft_domain;
4225 : isl_union_set *node_domain;
4226 : isl_schedule_tree *tree, *tree_graft;
4227 :
4228 0 : extension = isl_schedule_node_extension_get_extension(graft);
4229 0 : graft_domain = isl_union_map_range(isl_union_map_copy(extension));
4230 0 : node_domain = isl_schedule_node_get_universe_domain(node);
4231 0 : node = insert_extension(node, extension);
4232 :
4233 0 : graft_domain = replace_by_universe_if_disjoint(graft_domain,
4234 : node_domain);
4235 0 : isl_union_set_free(node_domain);
4236 :
4237 0 : tree = isl_schedule_node_get_tree(node);
4238 0 : if (!isl_schedule_node_has_children(graft)) {
4239 0 : tree_graft = isl_schedule_tree_from_filter(graft_domain);
4240 : } else {
4241 0 : graft = isl_schedule_node_child(graft, 0);
4242 0 : tree_graft = isl_schedule_node_get_tree(graft);
4243 0 : tree_graft = isl_schedule_tree_insert_filter(tree_graft,
4244 : graft_domain);
4245 : }
4246 0 : if (before)
4247 0 : tree = isl_schedule_tree_sequence_pair(tree_graft, tree);
4248 : else
4249 0 : tree = isl_schedule_tree_sequence_pair(tree, tree_graft);
4250 0 : node = graft_or_splice(node, tree, before);
4251 :
4252 0 : isl_schedule_node_free(graft);
4253 :
4254 0 : return node;
4255 : }
4256 :
4257 : /* Replace the root domain node of "node" by an extension node suitable
4258 : * for insertion at "pos".
4259 : * That is, create an extension node that maps the outer band nodes
4260 : * at "pos" to the domain of the root node of "node" and attach
4261 : * the child of this root node to the extension node.
4262 : */
4263 0 : static __isl_give isl_schedule_node *extension_from_domain(
4264 : __isl_take isl_schedule_node *node, __isl_keep isl_schedule_node *pos)
4265 : {
4266 : isl_union_set *universe;
4267 : isl_union_set *domain;
4268 : isl_union_map *ext;
4269 : int depth;
4270 : int anchored;
4271 : isl_space *space;
4272 : isl_schedule_node *res;
4273 : isl_schedule_tree *tree;
4274 :
4275 0 : anchored = isl_schedule_node_is_subtree_anchored(node);
4276 0 : if (anchored < 0)
4277 0 : return isl_schedule_node_free(node);
4278 0 : if (anchored)
4279 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_unsupported,
4280 : "cannot graft anchored tree with domain root",
4281 : return isl_schedule_node_free(node));
4282 :
4283 0 : depth = isl_schedule_node_get_schedule_depth(pos);
4284 0 : domain = isl_schedule_node_domain_get_domain(node);
4285 0 : space = isl_union_set_get_space(domain);
4286 0 : space = isl_space_set_from_params(space);
4287 0 : space = isl_space_add_dims(space, isl_dim_set, depth);
4288 0 : universe = isl_union_set_from_set(isl_set_universe(space));
4289 0 : ext = isl_union_map_from_domain_and_range(universe, domain);
4290 0 : res = isl_schedule_node_from_extension(ext);
4291 0 : node = isl_schedule_node_child(node, 0);
4292 0 : if (!node)
4293 0 : return isl_schedule_node_free(res);
4294 0 : if (!isl_schedule_tree_is_leaf(node->tree)) {
4295 0 : tree = isl_schedule_node_get_tree(node);
4296 0 : res = isl_schedule_node_child(res, 0);
4297 0 : res = isl_schedule_node_graft_tree(res, tree);
4298 0 : res = isl_schedule_node_parent(res);
4299 : }
4300 0 : isl_schedule_node_free(node);
4301 :
4302 0 : return res;
4303 : }
4304 :
4305 : /* Insert a node "graft" into the schedule tree of "node" such that it
4306 : * is executed before (if "before" is set) or after (if "before" is not set)
4307 : * the node that "node" points to.
4308 : * The root of "graft" may be either a domain or an extension node.
4309 : * In the latter case, the domain of the extension needs to correspond
4310 : * to the outer band nodes of "node".
4311 : * The elements of the domain or the range of the extension may not
4312 : * intersect with the domain elements that reach "node".
4313 : * The schedule tree of "graft" may not be anchored.
4314 : *
4315 : * The schedule tree of "node" is modified to include an extension node
4316 : * corresponding to the root node of "graft" as a child of the original
4317 : * parent of "node". The original node that "node" points to and the
4318 : * child of the root node of "graft" are attached to this extension node
4319 : * through a sequence, with appropriate filters and with the child
4320 : * of "graft" appearing before or after the original "node".
4321 : *
4322 : * If "node" already appears inside a sequence that is the child of
4323 : * an extension node and if the spaces of the new domain elements
4324 : * do not overlap with those of the original domain elements,
4325 : * then that extension node is extended with the new extension
4326 : * rather than introducing a new segment of extension and sequence nodes.
4327 : *
4328 : * Return a pointer to the same node in the modified tree that
4329 : * "node" pointed to in the original tree.
4330 : */
4331 0 : static __isl_give isl_schedule_node *isl_schedule_node_graft_before_or_after(
4332 : __isl_take isl_schedule_node *node, __isl_take isl_schedule_node *graft,
4333 : int before)
4334 : {
4335 0 : if (!node || !graft)
4336 : goto error;
4337 0 : if (check_insert(node) < 0)
4338 0 : goto error;
4339 :
4340 0 : if (isl_schedule_node_get_type(graft) == isl_schedule_node_domain)
4341 0 : graft = extension_from_domain(graft, node);
4342 :
4343 0 : if (!graft)
4344 0 : goto error;
4345 0 : if (isl_schedule_node_get_type(graft) != isl_schedule_node_extension)
4346 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
4347 : "expecting domain or extension as root of graft",
4348 : goto error);
4349 :
4350 0 : return graft_extension(node, graft, before);
4351 : error:
4352 0 : isl_schedule_node_free(node);
4353 0 : isl_schedule_node_free(graft);
4354 0 : return NULL;
4355 : }
4356 :
4357 : /* Insert a node "graft" into the schedule tree of "node" such that it
4358 : * is executed before the node that "node" points to.
4359 : * The root of "graft" may be either a domain or an extension node.
4360 : * In the latter case, the domain of the extension needs to correspond
4361 : * to the outer band nodes of "node".
4362 : * The elements of the domain or the range of the extension may not
4363 : * intersect with the domain elements that reach "node".
4364 : * The schedule tree of "graft" may not be anchored.
4365 : *
4366 : * Return a pointer to the same node in the modified tree that
4367 : * "node" pointed to in the original tree.
4368 : */
4369 0 : __isl_give isl_schedule_node *isl_schedule_node_graft_before(
4370 : __isl_take isl_schedule_node *node, __isl_take isl_schedule_node *graft)
4371 : {
4372 0 : return isl_schedule_node_graft_before_or_after(node, graft, 1);
4373 : }
4374 :
4375 : /* Insert a node "graft" into the schedule tree of "node" such that it
4376 : * is executed after the node that "node" points to.
4377 : * The root of "graft" may be either a domain or an extension node.
4378 : * In the latter case, the domain of the extension needs to correspond
4379 : * to the outer band nodes of "node".
4380 : * The elements of the domain or the range of the extension may not
4381 : * intersect with the domain elements that reach "node".
4382 : * The schedule tree of "graft" may not be anchored.
4383 : *
4384 : * Return a pointer to the same node in the modified tree that
4385 : * "node" pointed to in the original tree.
4386 : */
4387 0 : __isl_give isl_schedule_node *isl_schedule_node_graft_after(
4388 : __isl_take isl_schedule_node *node,
4389 : __isl_take isl_schedule_node *graft)
4390 : {
4391 0 : return isl_schedule_node_graft_before_or_after(node, graft, 0);
4392 : }
4393 :
4394 : /* Split the domain elements that reach "node" into those that satisfy
4395 : * "filter" and those that do not. Arrange for the first subset to be
4396 : * executed before or after the second subset, depending on the value
4397 : * of "before".
4398 : * Return a pointer to the tree corresponding to the second subset,
4399 : * except when this subset is empty in which case the original pointer
4400 : * is returned.
4401 : * If both subsets are non-empty, then a sequence node is introduced
4402 : * to impose the order. If the grandparent of the original node was
4403 : * itself a sequence, then the original child is replaced by two children
4404 : * in this sequence instead.
4405 : * The children in the sequence are copies of the original subtree,
4406 : * simplified with respect to their filters.
4407 : */
4408 0 : static __isl_give isl_schedule_node *isl_schedule_node_order_before_or_after(
4409 : __isl_take isl_schedule_node *node, __isl_take isl_union_set *filter,
4410 : int before)
4411 : {
4412 0 : enum isl_schedule_node_type ancestors[] =
4413 : { isl_schedule_node_filter, isl_schedule_node_sequence };
4414 0 : isl_union_set *node_domain, *node_filter = NULL, *parent_filter;
4415 : isl_schedule_node *node2;
4416 : isl_schedule_tree *tree1, *tree2;
4417 : int empty1, empty2;
4418 : int in_seq;
4419 :
4420 0 : if (!node || !filter)
4421 : goto error;
4422 0 : if (check_insert(node) < 0)
4423 0 : goto error;
4424 :
4425 0 : in_seq = has_ancestors(node, 2, ancestors);
4426 0 : if (in_seq < 0)
4427 0 : goto error;
4428 0 : node_domain = isl_schedule_node_get_domain(node);
4429 0 : filter = isl_union_set_gist(filter, isl_union_set_copy(node_domain));
4430 0 : node_filter = isl_union_set_copy(node_domain);
4431 0 : node_filter = isl_union_set_subtract(node_filter,
4432 : isl_union_set_copy(filter));
4433 0 : node_filter = isl_union_set_gist(node_filter, node_domain);
4434 0 : empty1 = isl_union_set_is_empty(filter);
4435 0 : empty2 = isl_union_set_is_empty(node_filter);
4436 0 : if (empty1 < 0 || empty2 < 0)
4437 : goto error;
4438 0 : if (empty1 || empty2) {
4439 0 : isl_union_set_free(filter);
4440 0 : isl_union_set_free(node_filter);
4441 0 : return node;
4442 : }
4443 :
4444 0 : if (in_seq) {
4445 0 : node = isl_schedule_node_parent(node);
4446 0 : parent_filter = isl_schedule_node_filter_get_filter(node);
4447 0 : node_filter = isl_union_set_intersect(node_filter,
4448 : isl_union_set_copy(parent_filter));
4449 0 : filter = isl_union_set_intersect(filter, parent_filter);
4450 : }
4451 :
4452 0 : node2 = isl_schedule_node_copy(node);
4453 0 : node = isl_schedule_node_gist(node, isl_union_set_copy(node_filter));
4454 0 : node2 = isl_schedule_node_gist(node2, isl_union_set_copy(filter));
4455 0 : tree1 = isl_schedule_node_get_tree(node);
4456 0 : tree2 = isl_schedule_node_get_tree(node2);
4457 0 : tree1 = isl_schedule_tree_insert_filter(tree1, node_filter);
4458 0 : tree2 = isl_schedule_tree_insert_filter(tree2, filter);
4459 0 : isl_schedule_node_free(node2);
4460 :
4461 0 : if (before) {
4462 0 : tree1 = isl_schedule_tree_sequence_pair(tree2, tree1);
4463 0 : node = graft_or_splice(node, tree1, 1);
4464 : } else {
4465 0 : tree1 = isl_schedule_tree_sequence_pair(tree1, tree2);
4466 0 : node = graft_or_splice(node, tree1, 0);
4467 : }
4468 :
4469 0 : return node;
4470 : error:
4471 0 : isl_schedule_node_free(node);
4472 0 : isl_union_set_free(filter);
4473 0 : isl_union_set_free(node_filter);
4474 0 : return NULL;
4475 : }
4476 :
4477 : /* Split the domain elements that reach "node" into those that satisfy
4478 : * "filter" and those that do not. Arrange for the first subset to be
4479 : * executed before the second subset.
4480 : * Return a pointer to the tree corresponding to the second subset,
4481 : * except when this subset is empty in which case the original pointer
4482 : * is returned.
4483 : */
4484 0 : __isl_give isl_schedule_node *isl_schedule_node_order_before(
4485 : __isl_take isl_schedule_node *node, __isl_take isl_union_set *filter)
4486 : {
4487 0 : return isl_schedule_node_order_before_or_after(node, filter, 1);
4488 : }
4489 :
4490 : /* Split the domain elements that reach "node" into those that satisfy
4491 : * "filter" and those that do not. Arrange for the first subset to be
4492 : * executed after the second subset.
4493 : * Return a pointer to the tree corresponding to the second subset,
4494 : * except when this subset is empty in which case the original pointer
4495 : * is returned.
4496 : */
4497 0 : __isl_give isl_schedule_node *isl_schedule_node_order_after(
4498 : __isl_take isl_schedule_node *node, __isl_take isl_union_set *filter)
4499 : {
4500 0 : return isl_schedule_node_order_before_or_after(node, filter, 0);
4501 : }
4502 :
4503 : /* Reset the user pointer on all identifiers of parameters and tuples
4504 : * in the schedule node "node".
4505 : */
4506 0 : __isl_give isl_schedule_node *isl_schedule_node_reset_user(
4507 : __isl_take isl_schedule_node *node)
4508 : {
4509 : isl_schedule_tree *tree;
4510 :
4511 0 : tree = isl_schedule_node_get_tree(node);
4512 0 : tree = isl_schedule_tree_reset_user(tree);
4513 0 : node = isl_schedule_node_graft_tree(node, tree);
4514 :
4515 0 : return node;
4516 : }
4517 :
4518 : /* Align the parameters of the schedule node "node" to those of "space".
4519 : */
4520 0 : __isl_give isl_schedule_node *isl_schedule_node_align_params(
4521 : __isl_take isl_schedule_node *node, __isl_take isl_space *space)
4522 : {
4523 : isl_schedule_tree *tree;
4524 :
4525 0 : tree = isl_schedule_node_get_tree(node);
4526 0 : tree = isl_schedule_tree_align_params(tree, space);
4527 0 : node = isl_schedule_node_graft_tree(node, tree);
4528 :
4529 0 : return node;
4530 : }
4531 :
4532 : /* Compute the pullback of schedule node "node"
4533 : * by the function represented by "upma".
4534 : * In other words, plug in "upma" in the iteration domains
4535 : * of schedule node "node".
4536 : * We currently do not handle expansion nodes.
4537 : *
4538 : * Note that this is only a helper function for
4539 : * isl_schedule_pullback_union_pw_multi_aff. In order to maintain consistency,
4540 : * this function should not be called on a single node without also
4541 : * calling it on all the other nodes.
4542 : */
4543 0 : __isl_give isl_schedule_node *isl_schedule_node_pullback_union_pw_multi_aff(
4544 : __isl_take isl_schedule_node *node,
4545 : __isl_take isl_union_pw_multi_aff *upma)
4546 : {
4547 : isl_schedule_tree *tree;
4548 :
4549 0 : tree = isl_schedule_node_get_tree(node);
4550 0 : tree = isl_schedule_tree_pullback_union_pw_multi_aff(tree, upma);
4551 0 : node = isl_schedule_node_graft_tree(node, tree);
4552 :
4553 0 : return node;
4554 : }
4555 :
4556 : /* Internal data structure for isl_schedule_node_expand.
4557 : * "tree" is the tree that needs to be plugged in in all the leaves.
4558 : * "domain" is the set of domain elements in the original leaves
4559 : * to which the tree applies.
4560 : */
4561 : struct isl_schedule_expand_data {
4562 : isl_schedule_tree *tree;
4563 : isl_union_set *domain;
4564 : };
4565 :
4566 : /* If "node" is a leaf, then plug in data->tree, simplifying it
4567 : * within its new context.
4568 : *
4569 : * If there are any domain elements at the leaf where the tree
4570 : * should not be plugged in (i.e., there are elements not in data->domain)
4571 : * then first extend the tree to only apply to the elements in data->domain
4572 : * by constructing a set node that selects data->tree for elements
4573 : * in data->domain and a leaf for the other elements.
4574 : */
4575 0 : static __isl_give isl_schedule_node *expand(__isl_take isl_schedule_node *node,
4576 : void *user)
4577 : {
4578 0 : struct isl_schedule_expand_data *data = user;
4579 : isl_schedule_tree *tree, *leaf;
4580 : isl_union_set *domain, *left;
4581 : isl_bool empty;
4582 :
4583 0 : if (isl_schedule_node_get_type(node) != isl_schedule_node_leaf)
4584 0 : return node;
4585 :
4586 0 : domain = isl_schedule_node_get_domain(node);
4587 0 : tree = isl_schedule_tree_copy(data->tree);
4588 :
4589 0 : left = isl_union_set_copy(domain);
4590 0 : left = isl_union_set_subtract(left, isl_union_set_copy(data->domain));
4591 0 : empty = isl_union_set_is_empty(left);
4592 0 : if (empty >= 0 && !empty) {
4593 0 : leaf = isl_schedule_node_get_leaf(node);
4594 0 : leaf = isl_schedule_tree_insert_filter(leaf, left);
4595 0 : left = isl_union_set_copy(data->domain);
4596 0 : tree = isl_schedule_tree_insert_filter(tree, left);
4597 0 : tree = isl_schedule_tree_set_pair(tree, leaf);
4598 : } else {
4599 0 : if (empty < 0)
4600 0 : node = isl_schedule_node_free(node);
4601 0 : isl_union_set_free(left);
4602 : }
4603 :
4604 0 : node = isl_schedule_node_graft_tree(node, tree);
4605 0 : node = isl_schedule_node_gist(node, domain);
4606 :
4607 0 : return node;
4608 : }
4609 :
4610 : /* Expand the tree rooted at "node" by extending all leaves
4611 : * with an expansion node with as child "tree".
4612 : * The expansion is determined by "contraction" and "domain".
4613 : * That is, the elements of "domain" are contracted according
4614 : * to "contraction". The expansion relation is then the inverse
4615 : * of "contraction" with its range intersected with "domain".
4616 : *
4617 : * Insert the appropriate expansion node on top of "tree" and
4618 : * then plug in the result in all leaves of "node".
4619 : */
4620 0 : __isl_give isl_schedule_node *isl_schedule_node_expand(
4621 : __isl_take isl_schedule_node *node,
4622 : __isl_take isl_union_pw_multi_aff *contraction,
4623 : __isl_take isl_union_set *domain,
4624 : __isl_take isl_schedule_tree *tree)
4625 : {
4626 : struct isl_schedule_expand_data data;
4627 : isl_union_map *expansion;
4628 : isl_union_pw_multi_aff *copy;
4629 :
4630 0 : if (!node || !contraction || !tree)
4631 0 : node = isl_schedule_node_free(node);
4632 :
4633 0 : copy = isl_union_pw_multi_aff_copy(contraction);
4634 0 : expansion = isl_union_map_from_union_pw_multi_aff(copy);
4635 0 : expansion = isl_union_map_reverse(expansion);
4636 0 : expansion = isl_union_map_intersect_range(expansion, domain);
4637 0 : data.domain = isl_union_map_domain(isl_union_map_copy(expansion));
4638 :
4639 0 : tree = isl_schedule_tree_insert_expansion(tree, contraction, expansion);
4640 0 : data.tree = tree;
4641 :
4642 0 : node = isl_schedule_node_map_descendant_bottom_up(node, &expand, &data);
4643 0 : isl_union_set_free(data.domain);
4644 0 : isl_schedule_tree_free(data.tree);
4645 0 : return node;
4646 : }
4647 :
4648 : /* Return the position of the subtree containing "node" among the children
4649 : * of "ancestor". "node" is assumed to be a descendant of "ancestor".
4650 : * In particular, both nodes should point to the same schedule tree.
4651 : *
4652 : * Return -1 on error.
4653 : */
4654 0 : int isl_schedule_node_get_ancestor_child_position(
4655 : __isl_keep isl_schedule_node *node,
4656 : __isl_keep isl_schedule_node *ancestor)
4657 : {
4658 : int n1, n2;
4659 : isl_schedule_tree *tree;
4660 :
4661 0 : if (!node || !ancestor)
4662 0 : return -1;
4663 :
4664 0 : if (node->schedule != ancestor->schedule)
4665 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
4666 : "not a descendant", return -1);
4667 :
4668 0 : n1 = isl_schedule_node_get_tree_depth(ancestor);
4669 0 : n2 = isl_schedule_node_get_tree_depth(node);
4670 :
4671 0 : if (n1 >= n2)
4672 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
4673 : "not a descendant", return -1);
4674 0 : tree = isl_schedule_tree_list_get_schedule_tree(node->ancestors, n1);
4675 0 : isl_schedule_tree_free(tree);
4676 0 : if (tree != ancestor->tree)
4677 0 : isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
4678 : "not a descendant", return -1);
4679 :
4680 0 : return node->child_pos[n1];
4681 : }
4682 :
4683 : /* Given two nodes that point to the same schedule tree, return their
4684 : * closest shared ancestor.
4685 : *
4686 : * Since the two nodes point to the same schedule, they share at least
4687 : * one ancestor, the root of the schedule. We move down from the root
4688 : * to the first ancestor where the respective children have a different
4689 : * child position. This is the requested ancestor.
4690 : * If there is no ancestor where the children have a different position,
4691 : * then one node is an ancestor of the other and then this node is
4692 : * the requested ancestor.
4693 : */
4694 0 : __isl_give isl_schedule_node *isl_schedule_node_get_shared_ancestor(
4695 : __isl_keep isl_schedule_node *node1,
4696 : __isl_keep isl_schedule_node *node2)
4697 : {
4698 : int i, n1, n2;
4699 :
4700 0 : if (!node1 || !node2)
4701 0 : return NULL;
4702 0 : if (node1->schedule != node2->schedule)
4703 0 : isl_die(isl_schedule_node_get_ctx(node1), isl_error_invalid,
4704 : "not part of same schedule", return NULL);
4705 0 : n1 = isl_schedule_node_get_tree_depth(node1);
4706 0 : n2 = isl_schedule_node_get_tree_depth(node2);
4707 0 : if (n2 < n1)
4708 0 : return isl_schedule_node_get_shared_ancestor(node2, node1);
4709 0 : if (n1 == 0)
4710 0 : return isl_schedule_node_copy(node1);
4711 0 : if (isl_schedule_node_is_equal(node1, node2))
4712 0 : return isl_schedule_node_copy(node1);
4713 :
4714 0 : for (i = 0; i < n1; ++i)
4715 0 : if (node1->child_pos[i] != node2->child_pos[i])
4716 0 : break;
4717 :
4718 0 : node1 = isl_schedule_node_copy(node1);
4719 0 : return isl_schedule_node_ancestor(node1, n1 - i);
4720 : }
4721 :
4722 : /* Print "node" to "p".
4723 : */
4724 0 : __isl_give isl_printer *isl_printer_print_schedule_node(
4725 : __isl_take isl_printer *p, __isl_keep isl_schedule_node *node)
4726 : {
4727 0 : if (!node)
4728 0 : return isl_printer_free(p);
4729 0 : return isl_printer_print_schedule_tree_mark(p, node->schedule->root,
4730 : isl_schedule_tree_list_n_schedule_tree(node->ancestors),
4731 : node->child_pos);
4732 : }
4733 :
4734 0 : void isl_schedule_node_dump(__isl_keep isl_schedule_node *node)
4735 : {
4736 : isl_ctx *ctx;
4737 : isl_printer *printer;
4738 :
4739 0 : if (!node)
4740 0 : return;
4741 :
4742 0 : ctx = isl_schedule_node_get_ctx(node);
4743 0 : printer = isl_printer_to_file(ctx, stderr);
4744 0 : printer = isl_printer_set_yaml_style(printer, ISL_YAML_STYLE_BLOCK);
4745 0 : printer = isl_printer_print_schedule_node(printer, node);
4746 :
4747 0 : isl_printer_free(printer);
4748 : }
4749 :
4750 : /* Return a string representation of "node".
4751 : * Print the schedule node in block format as it would otherwise
4752 : * look identical to the entire schedule.
4753 : */
4754 0 : __isl_give char *isl_schedule_node_to_str(__isl_keep isl_schedule_node *node)
4755 : {
4756 : isl_printer *printer;
4757 : char *s;
4758 :
4759 0 : if (!node)
4760 0 : return NULL;
4761 :
4762 0 : printer = isl_printer_to_str(isl_schedule_node_get_ctx(node));
4763 0 : printer = isl_printer_set_yaml_style(printer, ISL_YAML_STYLE_BLOCK);
4764 0 : printer = isl_printer_print_schedule_node(printer, node);
4765 0 : s = isl_printer_get_str(printer);
4766 0 : isl_printer_free(printer);
4767 :
4768 0 : return s;
4769 : }
|
