Bug Summary

File:polly/lib/External/isl/isl_schedule_node.c
Location:line 1646, column 2
Description:Value stored to 'ctx' is never read

Annotated Source Code

1/*
2 * Copyright 2013-2014 Ecole Normale Superieure
3 * Copyright 2014 INRIA Rocquencourt
4 *
5 * Use of this software is governed by the MIT license
6 *
7 * Written by Sven Verdoolaege,
8 * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
9 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
10 * B.P. 105 - 78153 Le Chesnay, France
11 */
12
13#include <isl/set.h>
14#include <isl_schedule_band.h>
15#include <isl_schedule_private.h>
16#include <isl_schedule_node_private.h>
17
18/* Create a new schedule node in the given schedule, point at the given
19 * tree with given ancestors and child positions.
20 * "child_pos" may be NULL if there are no ancestors.
21 */
22__isl_give isl_schedule_node *isl_schedule_node_alloc(
23 __isl_take isl_schedule *schedule, __isl_take isl_schedule_tree *tree,
24 __isl_take isl_schedule_tree_list *ancestors, int *child_pos)
25{
26 isl_ctx *ctx;
27 isl_schedule_node *node;
28 int i, n;
29
30 if (!schedule || !tree || !ancestors)
31 goto error;
32 n = isl_schedule_tree_list_n_schedule_tree(ancestors);
33 if (n > 0 && !child_pos)
34 goto error;
35 ctx = isl_schedule_get_ctx(schedule);
36 node = isl_calloc_type(ctx, isl_schedule_node)((isl_schedule_node *)isl_calloc_or_die(ctx, 1, sizeof(isl_schedule_node
)));
37 if (!node)
38 goto error;
39 node->ref = 1;
40 node->schedule = schedule;
41 node->tree = tree;
42 node->ancestors = ancestors;
43 node->child_pos = isl_alloc_array(ctx, int, n)((int *)isl_malloc_or_die(ctx, (n)*sizeof(int)));
44 if (n && !node->child_pos)
45 return isl_schedule_node_free(node);
46 for (i = 0; i < n; ++i)
47 node->child_pos[i] = child_pos[i];
48
49 return node;
50error:
51 isl_schedule_free(schedule);
52 isl_schedule_tree_free(tree);
53 isl_schedule_tree_list_free(ancestors);
54 return NULL((void*)0);
55}
56
57/* Return a pointer to the root of a schedule tree with as single
58 * node a domain node with the given domain.
59 */
60__isl_give isl_schedule_node *isl_schedule_node_from_domain(
61 __isl_take isl_union_set *domain)
62{
63 isl_schedule *schedule;
64 isl_schedule_node *node;
65
66 schedule = isl_schedule_from_domain(domain);
67 node = isl_schedule_get_root(schedule);
68 isl_schedule_free(schedule);
69
70 return node;
71}
72
73/* Return the isl_ctx to which "node" belongs.
74 */
75isl_ctx *isl_schedule_node_get_ctx(__isl_keep isl_schedule_node *node)
76{
77 return node ? isl_schedule_get_ctx(node->schedule) : NULL((void*)0);
78}
79
80/* Return a pointer to the leaf of the schedule into which "node" points.
81 *
82 * Even though these leaves are not reference counted, we still
83 * indicate that this function does not return a copy.
84 */
85__isl_keep isl_schedule_tree *isl_schedule_node_peek_leaf(
86 __isl_keep isl_schedule_node *node)
87{
88 return node ? isl_schedule_peek_leaf(node->schedule) : NULL((void*)0);
89}
90
91/* Return a pointer to the leaf of the schedule into which "node" points.
92 *
93 * Even though these leaves are not reference counted, we still
94 * return a "copy" of the leaf here such that it can still be "freed"
95 * by the user.
96 */
97__isl_give isl_schedule_tree *isl_schedule_node_get_leaf(
98 __isl_keep isl_schedule_node *node)
99{
100 return isl_schedule_tree_copy(isl_schedule_node_peek_leaf(node));
101}
102
103/* Return the type of the node or isl_schedule_node_error on error.
104 */
105enum isl_schedule_node_type isl_schedule_node_get_type(
106 __isl_keep isl_schedule_node *node)
107{
108 return node ? isl_schedule_tree_get_type(node->tree)
109 : isl_schedule_node_error;
110}
111
112/* Return the type of the parent of "node" or isl_schedule_node_error on error.
113 */
114enum isl_schedule_node_type isl_schedule_node_get_parent_type(
115 __isl_keep isl_schedule_node *node)
116{
117 int pos;
118 int has_parent;
119 isl_schedule_tree *parent;
120 enum isl_schedule_node_type type;
121
122 if (!node)
123 return isl_schedule_node_error;
124 has_parent = isl_schedule_node_has_parent(node);
125 if (has_parent < 0)
126 return isl_schedule_node_error;
127 if (!has_parent)
128 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "node has no parent", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 129); return isl_schedule_node_error; } while (0)
129 "node has no parent", return isl_schedule_node_error)do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "node has no parent", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 129); return isl_schedule_node_error; } while (0);
130
131 pos = isl_schedule_tree_list_n_schedule_tree(node->ancestors) - 1;
132 parent = isl_schedule_tree_list_get_schedule_tree(node->ancestors, pos);
133 type = isl_schedule_tree_get_type(parent);
134 isl_schedule_tree_free(parent);
135
136 return type;
137}
138
139/* Return a copy of the subtree that this node points to.
140 */
141__isl_give isl_schedule_tree *isl_schedule_node_get_tree(
142 __isl_keep isl_schedule_node *node)
143{
144 if (!node)
145 return NULL((void*)0);
146
147 return isl_schedule_tree_copy(node->tree);
148}
149
150/* Return a copy of the schedule into which "node" points.
151 */
152__isl_give isl_schedule *isl_schedule_node_get_schedule(
153 __isl_keep isl_schedule_node *node)
154{
155 if (!node)
156 return NULL((void*)0);
157 return isl_schedule_copy(node->schedule);
158}
159
160/* Return a fresh copy of "node".
161 */
162__isl_take isl_schedule_node *isl_schedule_node_dup(
163 __isl_keep isl_schedule_node *node)
164{
165 if (!node)
166 return NULL((void*)0);
167
168 return isl_schedule_node_alloc(isl_schedule_copy(node->schedule),
169 isl_schedule_tree_copy(node->tree),
170 isl_schedule_tree_list_copy(node->ancestors),
171 node->child_pos);
172}
173
174/* Return an isl_schedule_node that is equal to "node" and that has only
175 * a single reference.
176 */
177__isl_give isl_schedule_node *isl_schedule_node_cow(
178 __isl_take isl_schedule_node *node)
179{
180 if (!node)
181 return NULL((void*)0);
182
183 if (node->ref == 1)
184 return node;
185 node->ref--;
186 return isl_schedule_node_dup(node);
187}
188
189/* Return a new reference to "node".
190 */
191__isl_give isl_schedule_node *isl_schedule_node_copy(
192 __isl_keep isl_schedule_node *node)
193{
194 if (!node)
195 return NULL((void*)0);
196
197 node->ref++;
198 return node;
199}
200
201/* Free "node" and return NULL.
202 *
203 * Since the node may point to a leaf of its schedule, which
204 * point to a field inside the schedule, we need to make sure
205 * we free the tree before freeing the schedule.
206 */
207__isl_null isl_schedule_node *isl_schedule_node_free(
208 __isl_take isl_schedule_node *node)
209{
210 if (!node)
211 return NULL((void*)0);
212 if (--node->ref > 0)
213 return NULL((void*)0);
214
215 isl_schedule_tree_list_free(node->ancestors);
216 free(node->child_pos);
217 isl_schedule_tree_free(node->tree);
218 isl_schedule_free(node->schedule);
219 free(node);
220
221 return NULL((void*)0);
222}
223
224/* Do "node1" and "node2" point to the same position in the same
225 * schedule?
226 */
227int isl_schedule_node_is_equal(__isl_keep isl_schedule_node *node1,
228 __isl_keep isl_schedule_node *node2)
229{
230 int i, n1, n2;
231
232 if (!node1 || !node2)
233 return -1;
234 if (node1 == node2)
235 return 1;
236 if (node1->schedule != node2->schedule)
237 return 0;
238
239 n1 = isl_schedule_node_get_tree_depth(node1);
240 n2 = isl_schedule_node_get_tree_depth(node2);
241 if (n1 != n2)
242 return 0;
243 for (i = 0; i < n1; ++i)
244 if (node1->child_pos[i] != node2->child_pos[i])
245 return 0;
246
247 return 1;
248}
249
250/* Return the number of outer schedule dimensions of "node"
251 * in its schedule tree.
252 *
253 * Return -1 on error.
254 */
255int isl_schedule_node_get_schedule_depth(__isl_keep isl_schedule_node *node)
256{
257 int i, n;
258 int depth = 0;
259
260 if (!node)
261 return -1;
262
263 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
264 for (i = n - 1; i >= 0; --i) {
265 isl_schedule_tree *tree;
266
267 tree = isl_schedule_tree_list_get_schedule_tree(
268 node->ancestors, i);
269 if (!tree)
270 return -1;
271 if (tree->type == isl_schedule_node_band)
272 depth += isl_schedule_tree_band_n_member(tree);
273 isl_schedule_tree_free(tree);
274 }
275
276 return depth;
277}
278
279/* Internal data structure for
280 * isl_schedule_node_get_prefix_schedule_union_pw_multi_aff
281 *
282 * "initialized" is set if the filter field has been initialized.
283 * If "universe_domain" is not set, then the collected filter is intersected
284 * with the the domain of the root domain node.
285 * "universe_filter" is set if we are only collecting the universes of filters
286 * "collect_prefix" is set if we are collecting prefixes.
287 * "filter" collects all outer filters and is NULL until "initialized" is set.
288 * "prefix" collects all outer band partial schedules (if "collect_prefix"
289 * is set). If it is used, then it is initialized by the caller
290 * of collect_filter_prefix to a zero-dimensional function.
291 */
292struct isl_schedule_node_get_filter_prefix_data {
293 int initialized;
294 int universe_domain;
295 int universe_filter;
296 int collect_prefix;
297 isl_union_set *filter;
298 isl_multi_union_pw_aff *prefix;
299};
300
301/* Update "data" based on the tree node "tree" in case "data" has
302 * not been initialized yet.
303 *
304 * Return 0 on success and -1 on error.
305 *
306 * If "tree" is a filter, then we set data->filter to this filter
307 * (or its universe).
308 * If "tree" is a domain, then this means we have reached the root
309 * of the schedule tree without being able to extract any information.
310 * We therefore initialize data->filter to the universe of the domain,
311 * or the domain itself if data->universe_domain is not set.
312 * If "tree" is a band with at least one member, then we set data->filter
313 * to the universe of the schedule domain and replace the zero-dimensional
314 * data->prefix by the band schedule (if data->collect_prefix is set).
315 */
316static int collect_filter_prefix_init(__isl_keep isl_schedule_tree *tree,
317 struct isl_schedule_node_get_filter_prefix_data *data)
318{
319 enum isl_schedule_node_type type;
320 isl_multi_union_pw_aff *mupa;
321 isl_union_set *filter;
322
323 type = isl_schedule_tree_get_type(tree);
324 switch (type) {
325 case isl_schedule_node_error:
326 return -1;
327 case isl_schedule_node_context:
328 case isl_schedule_node_leaf:
329 case isl_schedule_node_sequence:
330 case isl_schedule_node_set:
331 return 0;
332 case isl_schedule_node_domain:
333 filter = isl_schedule_tree_domain_get_domain(tree);
334 if (data->universe_domain)
335 filter = isl_union_set_universe(filter);
336 data->filter = filter;
337 break;
338 case isl_schedule_node_band:
339 if (isl_schedule_tree_band_n_member(tree) == 0)
340 return 0;
341 mupa = isl_schedule_tree_band_get_partial_schedule(tree);
342 if (data->collect_prefix) {
343 isl_multi_union_pw_aff_free(data->prefix);
344 mupa = isl_multi_union_pw_aff_reset_tuple_id(mupa,
345 isl_dim_set);
346 data->prefix = isl_multi_union_pw_aff_copy(mupa);
347 }
348 filter = isl_multi_union_pw_aff_domain(mupa);
349 filter = isl_union_set_universe(filter);
350 data->filter = filter;
351 break;
352 case isl_schedule_node_filter:
353 filter = isl_schedule_tree_filter_get_filter(tree);
354 if (data->universe_filter)
355 filter = isl_union_set_universe(filter);
356 data->filter = filter;
357 break;
358 }
359
360 if ((data->collect_prefix && !data->prefix) || !data->filter)
361 return -1;
362
363 data->initialized = 1;
364
365 return 0;
366}
367
368/* Update "data" based on the tree node "tree" in case "data" has
369 * already been initialized.
370 *
371 * Return 0 on success and -1 on error.
372 *
373 * If "tree" is a domain and data->universe_domain is not set, then
374 * intersect data->filter with the domain.
375 * If "tree" is a filter, then we intersect data->filter with this filter
376 * (or its universe).
377 * If "tree" is a band with at least one member and data->collect_prefix
378 * is set, then we extend data->prefix with the band schedule.
379 */
380static int collect_filter_prefix_update(__isl_keep isl_schedule_tree *tree,
381 struct isl_schedule_node_get_filter_prefix_data *data)
382{
383 enum isl_schedule_node_type type;
384 isl_multi_union_pw_aff *mupa;
385 isl_union_set *filter;
386
387 type = isl_schedule_tree_get_type(tree);
388 switch (type) {
389 case isl_schedule_node_error:
390 return -1;
391 case isl_schedule_node_context:
392 case isl_schedule_node_leaf:
393 case isl_schedule_node_sequence:
394 case isl_schedule_node_set:
395 break;
396 case isl_schedule_node_domain:
397 if (data->universe_domain)
398 break;
399 filter = isl_schedule_tree_domain_get_domain(tree);
400 data->filter = isl_union_set_intersect(data->filter, filter);
401 break;
402 case isl_schedule_node_band:
403 if (isl_schedule_tree_band_n_member(tree) == 0)
404 break;
405 if (!data->collect_prefix)
406 break;
407 mupa = isl_schedule_tree_band_get_partial_schedule(tree);
408 data->prefix = isl_multi_union_pw_aff_flat_range_product(mupa,
409 data->prefix);
410 if (!data->prefix)
411 return -1;
412 break;
413 case isl_schedule_node_filter:
414 filter = isl_schedule_tree_filter_get_filter(tree);
415 if (data->universe_filter)
416 filter = isl_union_set_universe(filter);
417 data->filter = isl_union_set_intersect(data->filter, filter);
418 if (!data->filter)
419 return -1;
420 break;
421 }
422
423 return 0;
424}
425
426/* Collect filter and/or prefix information from the elements
427 * in "list" (which represent the ancestors of a node).
428 * Store the results in "data".
429 *
430 * Return 0 on success and -1 on error.
431 *
432 * We traverse the list from innermost ancestor (last element)
433 * to outermost ancestor (first element), calling collect_filter_prefix_init
434 * on each node as long as we have not been able to extract any information
435 * yet and collect_filter_prefix_update afterwards.
436 * On successful return, data->initialized will be set since the outermost
437 * ancestor is a domain node, which always results in an initialization.
438 */
439static int collect_filter_prefix(__isl_keep isl_schedule_tree_list *list,
440 struct isl_schedule_node_get_filter_prefix_data *data)
441{
442 int i, n;
443
444 data->initialized = 0;
445 data->filter = NULL((void*)0);
446
447 if (!list)
448 return -1;
449
450 n = isl_schedule_tree_list_n_schedule_tree(list);
451 for (i = n - 1; i >= 0; --i) {
452 isl_schedule_tree *tree;
453 int r;
454
455 tree = isl_schedule_tree_list_get_schedule_tree(list, i);
456 if (!tree)
457 return -1;
458 if (!data->initialized)
459 r = collect_filter_prefix_init(tree, data);
460 else
461 r = collect_filter_prefix_update(tree, data);
462 isl_schedule_tree_free(tree);
463 if (r < 0)
464 return -1;
465 }
466
467 return 0;
468}
469
470/* Return the concatenation of the partial schedules of all outer band
471 * nodes of "node" interesected with all outer filters
472 * as an isl_union_pw_multi_aff.
473 *
474 * If "node" is pointing at the root of the schedule tree, then
475 * there are no domain elements reaching the current node, so
476 * we return an empty result.
477 *
478 * We collect all the filters and partial schedules in collect_filter_prefix.
479 * The partial schedules are collected as an isl_multi_union_pw_aff.
480 * If this isl_multi_union_pw_aff is zero-dimensional, then it does not
481 * contain any domain information, so we construct the isl_union_pw_multi_aff
482 * result as a zero-dimensional function on the collected filter.
483 * Otherwise, we convert the isl_multi_union_pw_aff to
484 * an isl_multi_union_pw_aff and intersect the domain with the filter.
485 */
486__isl_give isl_union_pw_multi_aff *
487isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(
488 __isl_keep isl_schedule_node *node)
489{
490 isl_space *space;
491 isl_union_pw_multi_aff *prefix;
492 struct isl_schedule_node_get_filter_prefix_data data;
493
494 if (!node)
495 return NULL((void*)0);
496
497 space = isl_schedule_get_space(node->schedule);
498 if (node->tree == node->schedule->root)
499 return isl_union_pw_multi_aff_empty(space);
500
501 space = isl_space_set_from_params(space);
502 data.universe_domain = 1;
503 data.universe_filter = 0;
504 data.collect_prefix = 1;
505 data.prefix = isl_multi_union_pw_aff_zero(space);
506
507 if (collect_filter_prefix(node->ancestors, &data) < 0)
508 data.prefix = isl_multi_union_pw_aff_free(data.prefix);
509
510 if (data.prefix &&
511 isl_multi_union_pw_aff_dim(data.prefix, isl_dim_set) == 0) {
512 isl_multi_union_pw_aff_free(data.prefix);
513 prefix = isl_union_pw_multi_aff_from_domain(data.filter);
514 } else {
515 prefix =
516 isl_union_pw_multi_aff_from_multi_union_pw_aff(data.prefix);
517 prefix = isl_union_pw_multi_aff_intersect_domain(prefix,
518 data.filter);
519 }
520
521 return prefix;
522}
523
524/* Return the concatenation of the partial schedules of all outer band
525 * nodes of "node" interesected with all outer filters
526 * as an isl_union_map.
527 */
528__isl_give isl_union_map *isl_schedule_node_get_prefix_schedule_union_map(
529 __isl_keep isl_schedule_node *node)
530{
531 isl_union_pw_multi_aff *upma;
532
533 upma = isl_schedule_node_get_prefix_schedule_union_pw_multi_aff(node);
534 return isl_union_map_from_union_pw_multi_aff(upma);
535}
536
537/* Return the domain elements that reach "node".
538 *
539 * If "node" is pointing at the root of the schedule tree, then
540 * there are no domain elements reaching the current node, so
541 * we return an empty result.
542 *
543 * Otherwise, we collect all filters reaching the node,
544 * intersected with the root domain in collect_filter_prefix.
545 */
546__isl_give isl_union_set *isl_schedule_node_get_domain(
547 __isl_keep isl_schedule_node *node)
548{
549 struct isl_schedule_node_get_filter_prefix_data data;
550
551 if (!node)
552 return NULL((void*)0);
553
554 if (node->tree == node->schedule->root) {
555 isl_space *space;
556
557 space = isl_schedule_get_space(node->schedule);
558 return isl_union_set_empty(space);
559 }
560
561 data.universe_domain = 0;
562 data.universe_filter = 0;
563 data.collect_prefix = 0;
564 data.prefix = NULL((void*)0);
565
566 if (collect_filter_prefix(node->ancestors, &data) < 0)
567 data.filter = isl_union_set_free(data.filter);
568
569 return data.filter;
570}
571
572/* Return the union of universe sets of the domain elements that reach "node".
573 *
574 * If "node" is pointing at the root of the schedule tree, then
575 * there are no domain elements reaching the current node, so
576 * we return an empty result.
577 *
578 * Otherwise, we collect the universes of all filters reaching the node
579 * in collect_filter_prefix.
580 */
581__isl_give isl_union_set *isl_schedule_node_get_universe_domain(
582 __isl_keep isl_schedule_node *node)
583{
584 struct isl_schedule_node_get_filter_prefix_data data;
585
586 if (!node)
587 return NULL((void*)0);
588
589 if (node->tree == node->schedule->root) {
590 isl_space *space;
591
592 space = isl_schedule_get_space(node->schedule);
593 return isl_union_set_empty(space);
594 }
595
596 data.universe_domain = 1;
597 data.universe_filter = 1;
598 data.collect_prefix = 0;
599 data.prefix = NULL((void*)0);
600
601 if (collect_filter_prefix(node->ancestors, &data) < 0)
602 data.filter = isl_union_set_free(data.filter);
603
604 return data.filter;
605}
606
607/* Return the subtree schedule of "node".
608 *
609 * Since isl_schedule_tree_get_subtree_schedule_union_map does not handle
610 * trees that do not contain any schedule information, we first
611 * move down to the first relevant descendant and handle leaves ourselves.
612 */
613__isl_give isl_union_map *isl_schedule_node_get_subtree_schedule_union_map(
614 __isl_keep isl_schedule_node *node)
615{
616 isl_schedule_tree *tree, *leaf;
617 isl_union_map *umap;
618
619 tree = isl_schedule_node_get_tree(node);
620 leaf = isl_schedule_node_peek_leaf(node);
621 tree = isl_schedule_tree_first_schedule_descendant(tree, leaf);
622 if (!tree)
623 return NULL((void*)0);
624 if (tree == leaf) {
625 isl_union_set *domain;
626 domain = isl_schedule_node_get_universe_domain(node);
627 isl_schedule_tree_free(tree);
628 return isl_union_map_from_domain(domain);
629 }
630
631 umap = isl_schedule_tree_get_subtree_schedule_union_map(tree);
632 isl_schedule_tree_free(tree);
633 return umap;
634}
635
636/* Return the number of ancestors of "node" in its schedule tree.
637 */
638int isl_schedule_node_get_tree_depth(__isl_keep isl_schedule_node *node)
639{
640 if (!node)
641 return -1;
642 return isl_schedule_tree_list_n_schedule_tree(node->ancestors);
643}
644
645/* Does "node" have a parent?
646 *
647 * That is, does it point to any node of the schedule other than the root?
648 */
649int isl_schedule_node_has_parent(__isl_keep isl_schedule_node *node)
650{
651 if (!node)
652 return -1;
653 if (!node->ancestors)
654 return -1;
655
656 return isl_schedule_tree_list_n_schedule_tree(node->ancestors) != 0;
657}
658
659/* Return the position of "node" among the children of its parent.
660 */
661int isl_schedule_node_get_child_position(__isl_keep isl_schedule_node *node)
662{
663 int n;
664 int has_parent;
665
666 if (!node)
667 return -1;
668 has_parent = isl_schedule_node_has_parent(node);
669 if (has_parent < 0)
670 return -1;
671 if (!has_parent)
672 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "node has no parent", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 673); return -1; } while (0)
673 "node has no parent", return -1)do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "node has no parent", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 673); return -1; } while (0);
674
675 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
676 return node->child_pos[n - 1];
677}
678
679/* Does the parent (if any) of "node" have any children with a smaller child
680 * position than this one?
681 */
682int isl_schedule_node_has_previous_sibling(__isl_keep isl_schedule_node *node)
683{
684 int n;
685 int has_parent;
686
687 if (!node)
688 return -1;
689 has_parent = isl_schedule_node_has_parent(node);
690 if (has_parent < 0 || !has_parent)
691 return has_parent;
692
693 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
694
695 return node->child_pos[n - 1] > 0;
696}
697
698/* Does the parent (if any) of "node" have any children with a greater child
699 * position than this one?
700 */
701int isl_schedule_node_has_next_sibling(__isl_keep isl_schedule_node *node)
702{
703 int n, n_child;
704 int has_parent;
705 isl_schedule_tree *tree;
706
707 if (!node)
708 return -1;
709 has_parent = isl_schedule_node_has_parent(node);
710 if (has_parent < 0 || !has_parent)
711 return has_parent;
712
713 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
714 tree = isl_schedule_tree_list_get_schedule_tree(node->ancestors, n - 1);
715 if (!tree)
716 return -1;
717 n_child = isl_schedule_tree_list_n_schedule_tree(tree->children);
718 isl_schedule_tree_free(tree);
719
720 return node->child_pos[n - 1] + 1 < n_child;
721}
722
723/* Does "node" have any children?
724 *
725 * Any node other than the leaf nodes is considered to have at least
726 * one child, even if the corresponding isl_schedule_tree does not
727 * have any children.
728 */
729int isl_schedule_node_has_children(__isl_keep isl_schedule_node *node)
730{
731 if (!node)
732 return -1;
733 return !isl_schedule_tree_is_leaf(node->tree);
734}
735
736/* Return the number of children of "node"?
737 *
738 * Any node other than the leaf nodes is considered to have at least
739 * one child, even if the corresponding isl_schedule_tree does not
740 * have any children. That is, the number of children of "node" is
741 * only zero if its tree is the explicit empty tree. Otherwise,
742 * if the isl_schedule_tree has any children, then it is equal
743 * to the number of children of "node". If it has zero children,
744 * then "node" still has a leaf node as child.
745 */
746int isl_schedule_node_n_children(__isl_keep isl_schedule_node *node)
747{
748 int n;
749
750 if (!node)
751 return -1;
752
753 if (isl_schedule_tree_is_leaf(node->tree))
754 return 0;
755
756 n = isl_schedule_tree_n_children(node->tree);
757 if (n == 0)
758 return 1;
759
760 return n;
761}
762
763/* Move the "node" pointer to the ancestor of the given generation
764 * of the node it currently points to, where generation 0 is the node
765 * itself and generation 1 is its parent.
766 */
767__isl_give isl_schedule_node *isl_schedule_node_ancestor(
768 __isl_take isl_schedule_node *node, int generation)
769{
770 int n;
771 isl_schedule_tree *tree;
772
773 if (!node)
774 return NULL((void*)0);
775 if (generation == 0)
776 return node;
777 n = isl_schedule_node_get_tree_depth(node);
778 if (n < 0)
779 return isl_schedule_node_free(node);
780 if (generation < 0 || generation > n)
781 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "generation out of bounds", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 783); return isl_schedule_node_free(node); } while (0)
782 "generation out of bounds",do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "generation out of bounds", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 783); return isl_schedule_node_free(node); } while (0)
783 return isl_schedule_node_free(node))do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "generation out of bounds", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 783); return isl_schedule_node_free(node); } while (0);
784 node = isl_schedule_node_cow(node);
785 if (!node)
786 return NULL((void*)0);
787
788 tree = isl_schedule_tree_list_get_schedule_tree(node->ancestors,
789 n - generation);
790 isl_schedule_tree_free(node->tree);
791 node->tree = tree;
792 node->ancestors = isl_schedule_tree_list_drop(node->ancestors,
793 n - generation, generation);
794 if (!node->ancestors || !node->tree)
795 return isl_schedule_node_free(node);
796
797 return node;
798}
799
800/* Move the "node" pointer to the parent of the node it currently points to.
801 */
802__isl_give isl_schedule_node *isl_schedule_node_parent(
803 __isl_take isl_schedule_node *node)
804{
805 if (!node)
806 return NULL((void*)0);
807 if (!isl_schedule_node_has_parent(node))
808 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "node has no parent", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 810); return isl_schedule_node_free(node); } while (0)
809 "node has no parent",do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "node has no parent", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 810); return isl_schedule_node_free(node); } while (0)
810 return isl_schedule_node_free(node))do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "node has no parent", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 810); return isl_schedule_node_free(node); } while (0);
811 return isl_schedule_node_ancestor(node, 1);
812}
813
814/* Move the "node" pointer to the root of its schedule tree.
815 */
816__isl_give isl_schedule_node *isl_schedule_node_root(
817 __isl_take isl_schedule_node *node)
818{
819 int n;
820
821 if (!node)
822 return NULL((void*)0);
823 n = isl_schedule_node_get_tree_depth(node);
824 if (n < 0)
825 return isl_schedule_node_free(node);
826 return isl_schedule_node_ancestor(node, n);
827}
828
829/* Move the "node" pointer to the child at position "pos" of the node
830 * it currently points to.
831 */
832__isl_give isl_schedule_node *isl_schedule_node_child(
833 __isl_take isl_schedule_node *node, int pos)
834{
835 int n;
836 isl_ctx *ctx;
837 isl_schedule_tree *tree;
838 int *child_pos;
839
840 node = isl_schedule_node_cow(node);
841 if (!node)
842 return NULL((void*)0);
843 if (!isl_schedule_node_has_children(node))
844 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "node has no children", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 846); return isl_schedule_node_free(node); } while (0)
845 "node has no children",do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "node has no children", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 846); return isl_schedule_node_free(node); } while (0)
846 return isl_schedule_node_free(node))do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "node has no children", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 846); return isl_schedule_node_free(node); } while (0);
847
848 ctx = isl_schedule_node_get_ctx(node);
849 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
850 child_pos = isl_realloc_array(ctx, node->child_pos, int, n + 1)((int *)isl_realloc_or_die(ctx, node->child_pos, (n + 1)*sizeof
(int)));
851 if (!child_pos)
852 return isl_schedule_node_free(node);
853 node->child_pos = child_pos;
854 node->child_pos[n] = pos;
855
856 node->ancestors = isl_schedule_tree_list_add(node->ancestors,
857 isl_schedule_tree_copy(node->tree));
858 tree = node->tree;
859 if (isl_schedule_tree_has_children(tree))
860 tree = isl_schedule_tree_get_child(tree, pos);
861 else
862 tree = isl_schedule_node_get_leaf(node);
863 isl_schedule_tree_free(node->tree);
864 node->tree = tree;
865
866 if (!node->tree || !node->ancestors)
867 return isl_schedule_node_free(node);
868
869 return node;
870}
871
872/* Move the "node" pointer to the first child of the node
873 * it currently points to.
874 */
875__isl_give isl_schedule_node *isl_schedule_node_first_child(
876 __isl_take isl_schedule_node *node)
877{
878 return isl_schedule_node_child(node, 0);
879}
880
881/* Move the "node" pointer to the child of this node's parent in
882 * the previous child position.
883 */
884__isl_give isl_schedule_node *isl_schedule_node_previous_sibling(
885 __isl_take isl_schedule_node *node)
886{
887 int n;
888 isl_schedule_tree *parent, *tree;
889
890 node = isl_schedule_node_cow(node);
891 if (!node)
892 return NULL((void*)0);
893 if (!isl_schedule_node_has_previous_sibling(node))
894 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "node has no previous sibling", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 896); return isl_schedule_node_free(node); } while (0)
895 "node has no previous sibling",do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "node has no previous sibling", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 896); return isl_schedule_node_free(node); } while (0)
896 return isl_schedule_node_free(node))do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "node has no previous sibling", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 896); return isl_schedule_node_free(node); } while (0);
897
898 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
899 parent = isl_schedule_tree_list_get_schedule_tree(node->ancestors,
900 n - 1);
901 if (!parent)
902 return isl_schedule_node_free(node);
903 node->child_pos[n - 1]--;
904 tree = isl_schedule_tree_list_get_schedule_tree(parent->children,
905 node->child_pos[n - 1]);
906 isl_schedule_tree_free(parent);
907 if (!tree)
908 return isl_schedule_node_free(node);
909 isl_schedule_tree_free(node->tree);
910 node->tree = tree;
911
912 return node;
913}
914
915/* Move the "node" pointer to the child of this node's parent in
916 * the next child position.
917 */
918__isl_give isl_schedule_node *isl_schedule_node_next_sibling(
919 __isl_take isl_schedule_node *node)
920{
921 int n;
922 isl_schedule_tree *parent, *tree;
923
924 node = isl_schedule_node_cow(node);
925 if (!node)
926 return NULL((void*)0);
927 if (!isl_schedule_node_has_next_sibling(node))
928 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "node has no next sibling", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 930); return isl_schedule_node_free(node); } while (0)
929 "node has no next sibling",do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "node has no next sibling", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 930); return isl_schedule_node_free(node); } while (0)
930 return isl_schedule_node_free(node))do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "node has no next sibling", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 930); return isl_schedule_node_free(node); } while (0);
931
932 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
933 parent = isl_schedule_tree_list_get_schedule_tree(node->ancestors,
934 n - 1);
935 if (!parent)
936 return isl_schedule_node_free(node);
937 node->child_pos[n - 1]++;
938 tree = isl_schedule_tree_list_get_schedule_tree(parent->children,
939 node->child_pos[n - 1]);
940 isl_schedule_tree_free(parent);
941 if (!tree)
942 return isl_schedule_node_free(node);
943 isl_schedule_tree_free(node->tree);
944 node->tree = tree;
945
946 return node;
947}
948
949/* Return a copy to the child at position "pos" of "node".
950 */
951__isl_give isl_schedule_node *isl_schedule_node_get_child(
952 __isl_keep isl_schedule_node *node, int pos)
953{
954 return isl_schedule_node_child(isl_schedule_node_copy(node), pos);
955}
956
957/* Traverse the descendant of "node" in depth-first order, including
958 * "node" itself. Call "enter" whenever a node is entered and "leave"
959 * whenever a node is left. The callback "enter" is responsible
960 * for moving to the deepest initial subtree of its argument that
961 * should be traversed.
962 */
963static __isl_give isl_schedule_node *traverse(
964 __isl_take isl_schedule_node *node,
965 __isl_give isl_schedule_node *(*enter)(
966 __isl_take isl_schedule_node *node, void *user),
967 __isl_give isl_schedule_node *(*leave)(
968 __isl_take isl_schedule_node *node, void *user),
969 void *user)
970{
971 int depth;
972
973 if (!node)
974 return NULL((void*)0);
975
976 depth = isl_schedule_node_get_tree_depth(node);
977 do {
978 node = enter(node, user);
979 node = leave(node, user);
980 while (node && isl_schedule_node_get_tree_depth(node) > depth &&
981 !isl_schedule_node_has_next_sibling(node)) {
982 node = isl_schedule_node_parent(node);
983 node = leave(node, user);
984 }
985 if (node && isl_schedule_node_get_tree_depth(node) > depth)
986 node = isl_schedule_node_next_sibling(node);
987 } while (node && isl_schedule_node_get_tree_depth(node) > depth);
988
989 return node;
990}
991
992/* Internal data structure for isl_schedule_node_foreach_descendant.
993 *
994 * "fn" is the user-specified callback function.
995 * "user" is the user-specified argument for the callback.
996 */
997struct isl_schedule_node_preorder_data {
998 int (*fn)(__isl_keep isl_schedule_node *node, void *user);
999 void *user;
1000};
1001
1002/* Callback for "traverse" to enter a node and to move
1003 * to the deepest initial subtree that should be traversed
1004 * for use in a preorder visit.
1005 *
1006 * If the user callback returns a negative value, then we abort
1007 * the traversal. If this callback returns zero, then we skip
1008 * the subtree rooted at the current node. Otherwise, we move
1009 * down to the first child and repeat the process until a leaf
1010 * is reached.
1011 */
1012static __isl_give isl_schedule_node *preorder_enter(
1013 __isl_take isl_schedule_node *node, void *user)
1014{
1015 struct isl_schedule_node_preorder_data *data = user;
1016
1017 if (!node)
1018 return NULL((void*)0);
1019
1020 do {
1021 int r;
1022
1023 r = data->fn(node, data->user);
1024 if (r < 0)
1025 return isl_schedule_node_free(node);
1026 if (r == 0)
1027 return node;
1028 } while (isl_schedule_node_has_children(node) &&
1029 (node = isl_schedule_node_first_child(node)) != NULL((void*)0));
1030
1031 return node;
1032}
1033
1034/* Callback for "traverse" to leave a node
1035 * for use in a preorder visit.
1036 * Since we already visited the node when we entered it,
1037 * we do not need to do anything here.
1038 */
1039static __isl_give isl_schedule_node *preorder_leave(
1040 __isl_take isl_schedule_node *node, void *user)
1041{
1042 return node;
1043}
1044
1045/* Traverse the descendants of "node" (including the node itself)
1046 * in depth first preorder.
1047 *
1048 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1049 * If "fn" returns 0 on any of the nodes, then the subtree rooted
1050 * at that node is skipped.
1051 *
1052 * Return 0 on success and -1 on failure.
1053 */
1054int isl_schedule_node_foreach_descendant(__isl_keep isl_schedule_node *node,
1055 int (*fn)(__isl_keep isl_schedule_node *node, void *user), void *user)
1056{
1057 struct isl_schedule_node_preorder_data data = { fn, user };
1058
1059 node = isl_schedule_node_copy(node);
1060 node = traverse(node, &preorder_enter, &preorder_leave, &data);
1061 isl_schedule_node_free(node);
1062
1063 return node ? 0 : -1;
1064}
1065
1066/* Internal data structure for isl_schedule_node_map_descendant.
1067 *
1068 * "fn" is the user-specified callback function.
1069 * "user" is the user-specified argument for the callback.
1070 */
1071struct isl_schedule_node_postorder_data {
1072 __isl_give isl_schedule_node *(*fn)(__isl_take isl_schedule_node *node,
1073 void *user);
1074 void *user;
1075};
1076
1077/* Callback for "traverse" to enter a node and to move
1078 * to the deepest initial subtree that should be traversed
1079 * for use in a postorder visit.
1080 *
1081 * Since we are performing a postorder visit, we only need
1082 * to move to the deepest initial leaf here.
1083 */
1084static __isl_give isl_schedule_node *postorder_enter(
1085 __isl_take isl_schedule_node *node, void *user)
1086{
1087 while (node && isl_schedule_node_has_children(node))
1088 node = isl_schedule_node_first_child(node);
1089
1090 return node;
1091}
1092
1093/* Callback for "traverse" to leave a node
1094 * for use in a postorder visit.
1095 *
1096 * Since we are performing a postorder visit, we need
1097 * to call the user callback here.
1098 */
1099static __isl_give isl_schedule_node *postorder_leave(
1100 __isl_take isl_schedule_node *node, void *user)
1101{
1102 struct isl_schedule_node_postorder_data *data = user;
1103
1104 return data->fn(node, data->user);
1105}
1106
1107/* Traverse the descendants of "node" (including the node itself)
1108 * in depth first postorder, allowing the user to modify the visited node.
1109 * The traversal continues from the node returned by the callback function.
1110 * It is the responsibility of the user to ensure that this does not
1111 * lead to an infinite loop. It is safest to always return a pointer
1112 * to the same position (same ancestors and child positions) as the input node.
1113 */
1114__isl_give isl_schedule_node *isl_schedule_node_map_descendant(
1115 __isl_take isl_schedule_node *node,
1116 __isl_give isl_schedule_node *(*fn)(__isl_take isl_schedule_node *node,
1117 void *user), void *user)
1118{
1119 struct isl_schedule_node_postorder_data data = { fn, user };
1120
1121 return traverse(node, &postorder_enter, &postorder_leave, &data);
1122}
1123
1124/* Traverse the ancestors of "node" from the root down to and including
1125 * the parent of "node", calling "fn" on each of them.
1126 *
1127 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
1128 *
1129 * Return 0 on success and -1 on failure.
1130 */
1131int isl_schedule_node_foreach_ancestor_top_down(
1132 __isl_keep isl_schedule_node *node,
1133 int (*fn)(__isl_keep isl_schedule_node *node, void *user), void *user)
1134{
1135 int i, n;
1136
1137 if (!node)
1138 return -1;
1139
1140 n = isl_schedule_node_get_tree_depth(node);
1141 for (i = 0; i < n; ++i) {
1142 isl_schedule_node *ancestor;
1143 int r;
1144
1145 ancestor = isl_schedule_node_copy(node);
1146 ancestor = isl_schedule_node_ancestor(ancestor, n - i);
1147 r = fn(ancestor, user);
1148 isl_schedule_node_free(ancestor);
1149 if (r < 0)
1150 return -1;
1151 }
1152
1153 return 0;
1154}
1155
1156/* Is any node in the subtree rooted at "node" anchored?
1157 * That is, do any of these nodes reference the outer band nodes?
1158 */
1159int isl_schedule_node_is_subtree_anchored(__isl_keep isl_schedule_node *node)
1160{
1161 if (!node)
1162 return -1;
1163 return isl_schedule_tree_is_subtree_anchored(node->tree);
1164}
1165
1166/* Return the number of members in the given band node.
1167 */
1168unsigned isl_schedule_node_band_n_member(__isl_keep isl_schedule_node *node)
1169{
1170 return node ? isl_schedule_tree_band_n_member(node->tree) : 0;
1171}
1172
1173/* Is the band member at position "pos" of the band node "node"
1174 * marked coincident?
1175 */
1176int isl_schedule_node_band_member_get_coincident(
1177 __isl_keep isl_schedule_node *node, int pos)
1178{
1179 if (!node)
1180 return -1;
1181 return isl_schedule_tree_band_member_get_coincident(node->tree, pos);
1182}
1183
1184/* Mark the band member at position "pos" the band node "node"
1185 * as being coincident or not according to "coincident".
1186 */
1187__isl_give isl_schedule_node *isl_schedule_node_band_member_set_coincident(
1188 __isl_take isl_schedule_node *node, int pos, int coincident)
1189{
1190 int c;
1191 isl_schedule_tree *tree;
1192
1193 if (!node)
1194 return NULL((void*)0);
1195 c = isl_schedule_node_band_member_get_coincident(node, pos);
1196 if (c == coincident)
1197 return node;
1198
1199 tree = isl_schedule_tree_copy(node->tree);
1200 tree = isl_schedule_tree_band_member_set_coincident(tree, pos,
1201 coincident);
1202 node = isl_schedule_node_graft_tree(node, tree);
1203
1204 return node;
1205}
1206
1207/* Is the band node "node" marked permutable?
1208 */
1209int isl_schedule_node_band_get_permutable(__isl_keep isl_schedule_node *node)
1210{
1211 if (!node)
1212 return -1;
1213
1214 return isl_schedule_tree_band_get_permutable(node->tree);
1215}
1216
1217/* Mark the band node "node" permutable or not according to "permutable"?
1218 */
1219__isl_give isl_schedule_node *isl_schedule_node_band_set_permutable(
1220 __isl_take isl_schedule_node *node, int permutable)
1221{
1222 isl_schedule_tree *tree;
1223
1224 if (!node)
1225 return NULL((void*)0);
1226 if (isl_schedule_node_band_get_permutable(node) == permutable)
1227 return node;
1228
1229 tree = isl_schedule_tree_copy(node->tree);
1230 tree = isl_schedule_tree_band_set_permutable(tree, permutable);
1231 node = isl_schedule_node_graft_tree(node, tree);
1232
1233 return node;
1234}
1235
1236/* Return the schedule space of the band node.
1237 */
1238__isl_give isl_space *isl_schedule_node_band_get_space(
1239 __isl_keep isl_schedule_node *node)
1240{
1241 if (!node)
1242 return NULL((void*)0);
1243
1244 return isl_schedule_tree_band_get_space(node->tree);
1245}
1246
1247/* Return the schedule of the band node in isolation.
1248 */
1249__isl_give isl_multi_union_pw_aff *isl_schedule_node_band_get_partial_schedule(
1250 __isl_keep isl_schedule_node *node)
1251{
1252 if (!node)
1253 return NULL((void*)0);
1254
1255 return isl_schedule_tree_band_get_partial_schedule(node->tree);
1256}
1257
1258/* Return the schedule of the band node in isolation in the form of
1259 * an isl_union_map.
1260 *
1261 * If the band does not have any members, then we construct a universe map
1262 * with the universe of the domain elements reaching the node as domain.
1263 * Otherwise, we extract an isl_multi_union_pw_aff representation and
1264 * convert that to an isl_union_map.
1265 */
1266__isl_give isl_union_map *isl_schedule_node_band_get_partial_schedule_union_map(
1267 __isl_keep isl_schedule_node *node)
1268{
1269 isl_multi_union_pw_aff *mupa;
1270
1271 if (!node)
1272 return NULL((void*)0);
1273
1274 if (isl_schedule_node_get_type(node) != isl_schedule_node_band)
1275 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "not a band node", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1276); return ((void*)0); } while (0)
1276 "not a band node", return NULL)do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "not a band node", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1276); return ((void*)0); } while (0);
1277 if (isl_schedule_node_band_n_member(node) == 0) {
1278 isl_union_set *domain;
1279
1280 domain = isl_schedule_node_get_universe_domain(node);
1281 return isl_union_map_from_domain(domain);
1282 }
1283
1284 mupa = isl_schedule_node_band_get_partial_schedule(node);
1285 return isl_union_map_from_multi_union_pw_aff(mupa);
1286}
1287
1288/* Return the loop AST generation type for the band member of band node "node"
1289 * at position "pos".
1290 */
1291enum isl_ast_loop_type isl_schedule_node_band_member_get_ast_loop_type(
1292 __isl_keep isl_schedule_node *node, int pos)
1293{
1294 if (!node)
1295 return isl_ast_loop_error;
1296
1297 return isl_schedule_tree_band_member_get_ast_loop_type(node->tree, pos);
1298}
1299
1300/* Set the loop AST generation type for the band member of band node "node"
1301 * at position "pos" to "type".
1302 */
1303__isl_give isl_schedule_node *isl_schedule_node_band_member_set_ast_loop_type(
1304 __isl_take isl_schedule_node *node, int pos,
1305 enum isl_ast_loop_type type)
1306{
1307 isl_schedule_tree *tree;
1308
1309 if (!node)
1310 return NULL((void*)0);
1311
1312 tree = isl_schedule_tree_copy(node->tree);
1313 tree = isl_schedule_tree_band_member_set_ast_loop_type(tree, pos, type);
1314 return isl_schedule_node_graft_tree(node, tree);
1315}
1316
1317/* Return the loop AST generation type for the band member of band node "node"
1318 * at position "pos" for the isolated part.
1319 */
1320enum isl_ast_loop_type isl_schedule_node_band_member_get_isolate_ast_loop_type(
1321 __isl_keep isl_schedule_node *node, int pos)
1322{
1323 if (!node)
1324 return isl_ast_loop_error;
1325
1326 return isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1327 node->tree, pos);
1328}
1329
1330/* Set the loop AST generation type for the band member of band node "node"
1331 * at position "pos" for the isolated part to "type".
1332 */
1333__isl_give isl_schedule_node *
1334isl_schedule_node_band_member_set_isolate_ast_loop_type(
1335 __isl_take isl_schedule_node *node, int pos,
1336 enum isl_ast_loop_type type)
1337{
1338 isl_schedule_tree *tree;
1339
1340 if (!node)
1341 return NULL((void*)0);
1342
1343 tree = isl_schedule_tree_copy(node->tree);
1344 tree = isl_schedule_tree_band_member_set_isolate_ast_loop_type(tree,
1345 pos, type);
1346 return isl_schedule_node_graft_tree(node, tree);
1347}
1348
1349/* Return the AST build options associated to band node "node".
1350 */
1351__isl_give isl_union_set *isl_schedule_node_band_get_ast_build_options(
1352 __isl_keep isl_schedule_node *node)
1353{
1354 if (!node)
1355 return NULL((void*)0);
1356
1357 return isl_schedule_tree_band_get_ast_build_options(node->tree);
1358}
1359
1360/* Replace the AST build options associated to band node "node" by "options".
1361 */
1362__isl_give isl_schedule_node *isl_schedule_node_band_set_ast_build_options(
1363 __isl_take isl_schedule_node *node, __isl_take isl_union_set *options)
1364{
1365 isl_schedule_tree *tree;
1366
1367 if (!node || !options)
1368 goto error;
1369
1370 tree = isl_schedule_tree_copy(node->tree);
1371 tree = isl_schedule_tree_band_set_ast_build_options(tree, options);
1372 return isl_schedule_node_graft_tree(node, tree);
1373error:
1374 isl_schedule_node_free(node);
1375 isl_union_set_free(options);
1376 return NULL((void*)0);
1377}
1378
1379/* Make sure that that spaces of "node" and "mv" are the same.
1380 * Return -1 on error, reporting the error to the user.
1381 */
1382static int check_space_multi_val(__isl_keep isl_schedule_node *node,
1383 __isl_keep isl_multi_val *mv)
1384{
1385 isl_space *node_space, *mv_space;
1386 int equal;
1387
1388 node_space = isl_schedule_node_band_get_space(node);
1389 mv_space = isl_multi_val_get_space(mv);
1390 equal = isl_space_tuple_is_equal(node_space, isl_dim_set,
1391 mv_space, isl_dim_set);
1392 isl_space_free(mv_space);
1393 isl_space_free(node_space);
1394 if (equal < 0)
1395 return -1;
1396 if (!equal)
1397 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "spaces don't match", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1398); return -1; } while (0)
1398 "spaces don't match", return -1)do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "spaces don't match", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1398); return -1; } while (0);
1399
1400 return 0;
1401}
1402
1403/* Multiply the partial schedule of the band node "node"
1404 * with the factors in "mv".
1405 */
1406__isl_give isl_schedule_node *isl_schedule_node_band_scale(
1407 __isl_take isl_schedule_node *node, __isl_take isl_multi_val *mv)
1408{
1409 isl_schedule_tree *tree;
1410 int anchored;
1411
1412 if (!node || !mv)
1413 goto error;
1414 if (check_space_multi_val(node, mv) < 0)
1415 goto error;
1416 anchored = isl_schedule_node_is_subtree_anchored(node);
1417 if (anchored < 0)
1418 goto error;
1419 if (anchored)
1420 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot scale band node with anchored subtree", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1422); goto error; } while (0)
1421 "cannot scale band node with anchored subtree",do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot scale band node with anchored subtree", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1422); goto error; } while (0)
1422 goto error)do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot scale band node with anchored subtree", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1422); goto error; } while (0);
1423
1424 tree = isl_schedule_node_get_tree(node);
1425 tree = isl_schedule_tree_band_scale(tree, mv);
1426 return isl_schedule_node_graft_tree(node, tree);
1427error:
1428 isl_multi_val_free(mv);
1429 isl_schedule_node_free(node);
1430 return NULL((void*)0);
1431}
1432
1433/* Divide the partial schedule of the band node "node"
1434 * by the factors in "mv".
1435 */
1436__isl_give isl_schedule_node *isl_schedule_node_band_scale_down(
1437 __isl_take isl_schedule_node *node, __isl_take isl_multi_val *mv)
1438{
1439 isl_schedule_tree *tree;
1440 int anchored;
1441
1442 if (!node || !mv)
1443 goto error;
1444 if (check_space_multi_val(node, mv) < 0)
1445 goto error;
1446 anchored = isl_schedule_node_is_subtree_anchored(node);
1447 if (anchored < 0)
1448 goto error;
1449 if (anchored)
1450 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot scale down band node with anchored subtree", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1452); goto error; } while (0)
1451 "cannot scale down band node with anchored subtree",do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot scale down band node with anchored subtree", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1452); goto error; } while (0)
1452 goto error)do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot scale down band node with anchored subtree", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1452); goto error; } while (0);
1453
1454 tree = isl_schedule_node_get_tree(node);
1455 tree = isl_schedule_tree_band_scale_down(tree, mv);
1456 return isl_schedule_node_graft_tree(node, tree);
1457error:
1458 isl_multi_val_free(mv);
1459 isl_schedule_node_free(node);
1460 return NULL((void*)0);
1461}
1462
1463/* Tile "node" with tile sizes "sizes".
1464 *
1465 * The current node is replaced by two nested nodes corresponding
1466 * to the tile dimensions and the point dimensions.
1467 *
1468 * Return a pointer to the outer (tile) node.
1469 *
1470 * If any of the descendants of "node" depend on the set of outer band nodes,
1471 * then we refuse to tile the node.
1472 *
1473 * If the scale tile loops option is set, then the tile loops
1474 * are scaled by the tile sizes. If the shift point loops option is set,
1475 * then the point loops are shifted to start at zero.
1476 * In particular, these options affect the tile and point loop schedules
1477 * as follows
1478 *
1479 * scale shift original tile point
1480 *
1481 * 0 0 i floor(i/s) i
1482 * 1 0 i s * floor(i/s) i
1483 * 0 1 i floor(i/s) i - s * floor(i/s)
1484 * 1 1 i s * floor(i/s) i - s * floor(i/s)
1485 */
1486__isl_give isl_schedule_node *isl_schedule_node_band_tile(
1487 __isl_take isl_schedule_node *node, __isl_take isl_multi_val *sizes)
1488{
1489 isl_schedule_tree *tree;
1490 int anchored;
1491
1492 if (!node || !sizes)
1493 goto error;
1494 anchored = isl_schedule_node_is_subtree_anchored(node);
1495 if (anchored < 0)
1496 goto error;
1497 if (anchored)
1498 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot tile band node with anchored subtree", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1500); goto error; } while (0)
1499 "cannot tile band node with anchored subtree",do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot tile band node with anchored subtree", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1500); goto error; } while (0)
1500 goto error)do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot tile band node with anchored subtree", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1500); goto error; } while (0);
1501
1502 if (check_space_multi_val(node, sizes) < 0)
1503 goto error;
1504
1505 tree = isl_schedule_node_get_tree(node);
1506 tree = isl_schedule_tree_band_tile(tree, sizes);
1507 return isl_schedule_node_graft_tree(node, tree);
1508error:
1509 isl_multi_val_free(sizes);
1510 isl_schedule_node_free(node);
1511 return NULL((void*)0);
1512}
1513
1514/* Move the band node "node" down to all the leaves in the subtree
1515 * rooted at "node".
1516 * Return a pointer to the node in the resulting tree that is in the same
1517 * position as the node pointed to by "node" in the original tree.
1518 *
1519 * If the node only has a leaf child, then nothing needs to be done.
1520 * Otherwise, the child of the node is removed and the result is
1521 * appended to all the leaves in the subtree rooted at the original child.
1522 * The original node is then replaced by the result of this operation.
1523 *
1524 * If any of the nodes in the subtree rooted at "node" depend on
1525 * the set of outer band nodes then we refuse to sink the band node.
1526 */
1527__isl_give isl_schedule_node *isl_schedule_node_band_sink(
1528 __isl_take isl_schedule_node *node)
1529{
1530 enum isl_schedule_node_type type;
1531 isl_schedule_tree *tree, *child;
1532 int anchored;
1533
1534 if (!node)
1535 return NULL((void*)0);
1536
1537 type = isl_schedule_node_get_type(node);
1538 if (type != isl_schedule_node_band)
1539 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "not a band node", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1540); isl_schedule_node_free(node); } while (0)
1540 "not a band node", isl_schedule_node_free(node))do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "not a band node", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1540); isl_schedule_node_free(node); } while (0);
1541 anchored = isl_schedule_node_is_subtree_anchored(node);
1542 if (anchored < 0)
1543 return isl_schedule_node_free(node);
1544 if (anchored)
1545 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot sink band node in anchored subtree", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1547); isl_schedule_node_free(node); } while (0)
1546 "cannot sink band node in anchored subtree",do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot sink band node in anchored subtree", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1547); isl_schedule_node_free(node); } while (0)
1547 isl_schedule_node_free(node))do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot sink band node in anchored subtree", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1547); isl_schedule_node_free(node); } while (0);
1548 if (isl_schedule_tree_n_children(node->tree) == 0)
1549 return node;
1550
1551 tree = isl_schedule_node_get_tree(node);
1552 child = isl_schedule_tree_get_child(tree, 0);
1553 tree = isl_schedule_tree_reset_children(tree);
1554 tree = isl_schedule_tree_append_to_leaves(child, tree);
1555
1556 return isl_schedule_node_graft_tree(node, tree);
1557}
1558
1559/* Split "node" into two nested band nodes, one with the first "pos"
1560 * dimensions and one with the remaining dimensions.
1561 * The schedules of the two band nodes live in anonymous spaces.
1562 */
1563__isl_give isl_schedule_node *isl_schedule_node_band_split(
1564 __isl_take isl_schedule_node *node, int pos)
1565{
1566 isl_schedule_tree *tree;
1567
1568 tree = isl_schedule_node_get_tree(node);
1569 tree = isl_schedule_tree_band_split(tree, pos);
1570 return isl_schedule_node_graft_tree(node, tree);
1571}
1572
1573/* Return the context of the context node "node".
1574 */
1575__isl_give isl_set *isl_schedule_node_context_get_context(
1576 __isl_keep isl_schedule_node *node)
1577{
1578 if (!node)
1579 return NULL((void*)0);
1580
1581 return isl_schedule_tree_context_get_context(node->tree);
1582}
1583
1584/* Return the domain of the domain node "node".
1585 */
1586__isl_give isl_union_set *isl_schedule_node_domain_get_domain(
1587 __isl_keep isl_schedule_node *node)
1588{
1589 if (!node)
1590 return NULL((void*)0);
1591
1592 return isl_schedule_tree_domain_get_domain(node->tree);
1593}
1594
1595/* Return the filter of the filter node "node".
1596 */
1597__isl_give isl_union_set *isl_schedule_node_filter_get_filter(
1598 __isl_keep isl_schedule_node *node)
1599{
1600 if (!node)
1601 return NULL((void*)0);
1602
1603 return isl_schedule_tree_filter_get_filter(node->tree);
1604}
1605
1606/* Replace the filter of filter node "node" by "filter".
1607 */
1608__isl_give isl_schedule_node *isl_schedule_node_filter_set_filter(
1609 __isl_take isl_schedule_node *node, __isl_take isl_union_set *filter)
1610{
1611 isl_schedule_tree *tree;
1612
1613 if (!node || !filter)
1614 goto error;
1615
1616 tree = isl_schedule_tree_copy(node->tree);
1617 tree = isl_schedule_tree_filter_set_filter(tree, filter);
1618 return isl_schedule_node_graft_tree(node, tree);
1619error:
1620 isl_schedule_node_free(node);
1621 isl_union_set_free(filter);
1622 return NULL((void*)0);
1623}
1624
1625/* Update the ancestors of "node" to point to the tree that "node"
1626 * now points to.
1627 * That is, replace the child in the original parent that corresponds
1628 * to the current tree position by node->tree and continue updating
1629 * the ancestors in the same way until the root is reached.
1630 *
1631 * If "node" originally points to a leaf of the schedule tree, then make sure
1632 * that in the end it points to a leaf in the updated schedule tree.
1633 */
1634static __isl_give isl_schedule_node *update_ancestors(
1635 __isl_take isl_schedule_node *node)
1636{
1637 int i, n;
1638 int is_leaf;
1639 isl_ctx *ctx;
1640 isl_schedule_tree *tree;
1641
1642 node = isl_schedule_node_cow(node);
1643 if (!node)
1644 return NULL((void*)0);
1645
1646 ctx = isl_schedule_node_get_ctx(node);
Value stored to 'ctx' is never read
1647 n = isl_schedule_tree_list_n_schedule_tree(node->ancestors);
1648 tree = isl_schedule_tree_copy(node->tree);
1649
1650 for (i = n - 1; i >= 0; --i) {
1651 isl_schedule_tree *parent;
1652
1653 parent = isl_schedule_tree_list_get_schedule_tree(
1654 node->ancestors, i);
1655 parent = isl_schedule_tree_replace_child(parent,
1656 node->child_pos[i], tree);
1657 node->ancestors = isl_schedule_tree_list_set_schedule_tree(
1658 node->ancestors, i, isl_schedule_tree_copy(parent));
1659
1660 tree = parent;
1661 }
1662
1663 is_leaf = isl_schedule_tree_is_leaf(node->tree);
1664 node->schedule = isl_schedule_set_root(node->schedule, tree);
1665 if (is_leaf) {
1666 isl_schedule_tree_free(node->tree);
1667 node->tree = isl_schedule_node_get_leaf(node);
1668 }
1669
1670 if (!node->schedule || !node->ancestors)
1671 return isl_schedule_node_free(node);
1672
1673 return node;
1674}
1675
1676/* Replace the subtree that "pos" points to by "tree", updating
1677 * the ancestors to maintain a consistent state.
1678 */
1679__isl_give isl_schedule_node *isl_schedule_node_graft_tree(
1680 __isl_take isl_schedule_node *pos, __isl_take isl_schedule_tree *tree)
1681{
1682 if (!tree || !pos)
1683 goto error;
1684 if (pos->tree == tree) {
1685 isl_schedule_tree_free(tree);
1686 return pos;
1687 }
1688
1689 pos = isl_schedule_node_cow(pos);
1690 if (!pos)
1691 goto error;
1692
1693 isl_schedule_tree_free(pos->tree);
1694 pos->tree = tree;
1695
1696 return update_ancestors(pos);
1697error:
1698 isl_schedule_node_free(pos);
1699 isl_schedule_tree_free(tree);
1700 return NULL((void*)0);
1701}
1702
1703/* Make sure we can insert a node between "node" and its parent.
1704 * Return -1 on error, reporting the reason why we cannot insert a node.
1705 */
1706static int check_insert(__isl_keep isl_schedule_node *node)
1707{
1708 int has_parent;
1709 enum isl_schedule_node_type type;
1710
1711 has_parent = isl_schedule_node_has_parent(node);
1712 if (has_parent < 0)
1713 return -1;
1714 if (!has_parent)
1715 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot insert node outside of root", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1716); return -1; } while (0)
1716 "cannot insert node outside of root", return -1)do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot insert node outside of root", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1716); return -1; } while (0);
1717
1718 type = isl_schedule_node_get_parent_type(node);
1719 if (type == isl_schedule_node_error)
1720 return -1;
1721 if (type == isl_schedule_node_set || type == isl_schedule_node_sequence)
1722 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot insert node between set or sequence node " "and its filter children"
, "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1724); return -1; } while (0)
1723 "cannot insert node between set or sequence node "do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot insert node between set or sequence node " "and its filter children"
, "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1724); return -1; } while (0)
1724 "and its filter children", return -1)do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot insert node between set or sequence node " "and its filter children"
, "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1724); return -1; } while (0);
1725
1726 return 0;
1727}
1728
1729/* Insert a band node with partial schedule "mupa" between "node" and
1730 * its parent.
1731 * Return a pointer to the new band node.
1732 *
1733 * If any of the nodes in the subtree rooted at "node" depend on
1734 * the set of outer band nodes then we refuse to insert the band node.
1735 */
1736__isl_give isl_schedule_node *isl_schedule_node_insert_partial_schedule(
1737 __isl_take isl_schedule_node *node,
1738 __isl_take isl_multi_union_pw_aff *mupa)
1739{
1740 int anchored;
1741 isl_schedule_band *band;
1742 isl_schedule_tree *tree;
1743
1744 if (check_insert(node) < 0)
1745 node = isl_schedule_node_free(node);
1746 anchored = isl_schedule_node_is_subtree_anchored(node);
1747 if (anchored < 0)
1748 goto error;
1749 if (anchored)
1750 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot insert band node in anchored subtree", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1752); goto error; } while (0)
1751 "cannot insert band node in anchored subtree",do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot insert band node in anchored subtree", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1752); goto error; } while (0)
1752 goto error)do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot insert band node in anchored subtree", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1752); goto error; } while (0);
1753
1754 tree = isl_schedule_node_get_tree(node);
1755 band = isl_schedule_band_from_multi_union_pw_aff(mupa);
1756 tree = isl_schedule_tree_insert_band(tree, band);
1757 node = isl_schedule_node_graft_tree(node, tree);
1758
1759 return node;
1760error:
1761 isl_schedule_node_free(node);
1762 isl_multi_union_pw_aff_free(mupa);
1763 return NULL((void*)0);
1764}
1765
1766/* Insert a context node with context "context" between "node" and its parent.
1767 * Return a pointer to the new context node.
1768 */
1769__isl_give isl_schedule_node *isl_schedule_node_insert_context(
1770 __isl_take isl_schedule_node *node, __isl_take isl_set *context)
1771{
1772 isl_schedule_tree *tree;
1773
1774 if (check_insert(node) < 0)
1775 node = isl_schedule_node_free(node);
1776
1777 tree = isl_schedule_node_get_tree(node);
1778 tree = isl_schedule_tree_insert_context(tree, context);
1779 node = isl_schedule_node_graft_tree(node, tree);
1780
1781 return node;
1782}
1783
1784/* Insert a filter node with filter "filter" between "node" and its parent.
1785 * Return a pointer to the new filter node.
1786 */
1787__isl_give isl_schedule_node *isl_schedule_node_insert_filter(
1788 __isl_take isl_schedule_node *node, __isl_take isl_union_set *filter)
1789{
1790 isl_schedule_tree *tree;
1791
1792 if (check_insert(node) < 0)
1793 node = isl_schedule_node_free(node);
1794
1795 tree = isl_schedule_node_get_tree(node);
1796 tree = isl_schedule_tree_insert_filter(tree, filter);
1797 node = isl_schedule_node_graft_tree(node, tree);
1798
1799 return node;
1800}
1801
1802/* Attach the current subtree of "node" to a sequence of filter tree nodes
1803 * with filters described by "filters", attach this sequence
1804 * of filter tree nodes as children to a new tree of type "type" and
1805 * replace the original subtree of "node" by this new tree.
1806 */
1807static __isl_give isl_schedule_node *isl_schedule_node_insert_children(
1808 __isl_take isl_schedule_node *node,
1809 enum isl_schedule_node_type type,
1810 __isl_take isl_union_set_list *filters)
1811{
1812 int i, n;
1813 isl_ctx *ctx;
1814 isl_schedule_tree *tree;
1815 isl_schedule_tree_list *list;
1816
1817 if (check_insert(node) < 0)
1818 node = isl_schedule_node_free(node);
1819
1820 if (!node || !filters)
1821 goto error;
1822
1823 ctx = isl_schedule_node_get_ctx(node);
1824 n = isl_union_set_list_n_union_set(filters);
1825 list = isl_schedule_tree_list_alloc(ctx, n);
1826 for (i = 0; i < n; ++i) {
1827 isl_schedule_tree *tree;
1828 isl_union_set *filter;
1829
1830 tree = isl_schedule_node_get_tree(node);
1831 filter = isl_union_set_list_get_union_set(filters, i);
1832 tree = isl_schedule_tree_insert_filter(tree, filter);
1833 list = isl_schedule_tree_list_add(list, tree);
1834 }
1835 tree = isl_schedule_tree_from_children(type, list);
1836 node = isl_schedule_node_graft_tree(node, tree);
1837
1838 isl_union_set_list_free(filters);
1839 return node;
1840error:
1841 isl_union_set_list_free(filters);
1842 isl_schedule_node_free(node);
1843 return NULL((void*)0);
1844}
1845
1846/* Insert a sequence node with child filters "filters" between "node" and
1847 * its parent. That is, the tree that "node" points to is attached
1848 * to each of the child nodes of the filter nodes.
1849 * Return a pointer to the new sequence node.
1850 */
1851__isl_give isl_schedule_node *isl_schedule_node_insert_sequence(
1852 __isl_take isl_schedule_node *node,
1853 __isl_take isl_union_set_list *filters)
1854{
1855 return isl_schedule_node_insert_children(node,
1856 isl_schedule_node_sequence, filters);
1857}
1858
1859/* Insert a set node with child filters "filters" between "node" and
1860 * its parent. That is, the tree that "node" points to is attached
1861 * to each of the child nodes of the filter nodes.
1862 * Return a pointer to the new set node.
1863 */
1864__isl_give isl_schedule_node *isl_schedule_node_insert_set(
1865 __isl_take isl_schedule_node *node,
1866 __isl_take isl_union_set_list *filters)
1867{
1868 return isl_schedule_node_insert_children(node,
1869 isl_schedule_node_set, filters);
1870}
1871
1872/* Remove "node" from its schedule tree and return a pointer
1873 * to the leaf at the same position in the updated schedule tree.
1874 *
1875 * It is not allowed to remove the root of a schedule tree or
1876 * a child of a set or sequence node.
1877 */
1878__isl_give isl_schedule_node *isl_schedule_node_cut(
1879 __isl_take isl_schedule_node *node)
1880{
1881 isl_schedule_tree *leaf;
1882 enum isl_schedule_node_type parent_type;
1883
1884 if (!node)
1885 return NULL((void*)0);
1886 if (!isl_schedule_node_has_parent(node))
1887 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot cut root", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1888); return isl_schedule_node_free(node); } while (0)
1888 "cannot cut root", return isl_schedule_node_free(node))do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot cut root", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1888); return isl_schedule_node_free(node); } while (0);
1889
1890 parent_type = isl_schedule_node_get_parent_type(node);
1891 if (parent_type == isl_schedule_node_set ||
1892 parent_type == isl_schedule_node_sequence)
1893 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot cut child of set or sequence", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1895); return isl_schedule_node_free(node); } while (0)
1894 "cannot cut child of set or sequence",do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot cut child of set or sequence", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1895); return isl_schedule_node_free(node); } while (0)
1895 return isl_schedule_node_free(node))do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot cut child of set or sequence", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1895); return isl_schedule_node_free(node); } while (0);
1896
1897 leaf = isl_schedule_node_get_leaf(node);
1898 return isl_schedule_node_graft_tree(node, leaf);
1899}
1900
1901/* Remove a single node from the schedule tree, attaching the child
1902 * of "node" directly to its parent.
1903 * Return a pointer to this former child or to the leaf the position
1904 * of the original node if there was no child.
1905 * It is not allowed to remove the root of a schedule tree,
1906 * a set or sequence node, a child of a set or sequence node or
1907 * a band node with an anchored subtree.
1908 */
1909__isl_give isl_schedule_node *isl_schedule_node_delete(
1910 __isl_take isl_schedule_node *node)
1911{
1912 int n;
1913 isl_schedule_tree *tree;
1914 enum isl_schedule_node_type type;
1915
1916 if (!node)
1917 return NULL((void*)0);
1918
1919 if (isl_schedule_node_get_tree_depth(node) == 0)
1920 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot delete root node", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1922); return isl_schedule_node_free(node); } while (0)
1921 "cannot delete root node",do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot delete root node", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1922); return isl_schedule_node_free(node); } while (0)
1922 return isl_schedule_node_free(node))do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot delete root node", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1922); return isl_schedule_node_free(node); } while (0);
1923 n = isl_schedule_node_n_children(node);
1924 if (n != 1)
1925 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "can only delete node with a single child", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1927); return isl_schedule_node_free(node); } while (0)
1926 "can only delete node with a single child",do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "can only delete node with a single child", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1927); return isl_schedule_node_free(node); } while (0)
1927 return isl_schedule_node_free(node))do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "can only delete node with a single child", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1927); return isl_schedule_node_free(node); } while (0);
1928 type = isl_schedule_node_get_parent_type(node);
1929 if (type == isl_schedule_node_sequence || type == isl_schedule_node_set)
1930 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot delete child of set or sequence", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1932); return isl_schedule_node_free(node); } while (0)
1931 "cannot delete child of set or sequence",do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot delete child of set or sequence", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1932); return isl_schedule_node_free(node); } while (0)
1932 return isl_schedule_node_free(node))do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot delete child of set or sequence", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1932); return isl_schedule_node_free(node); } while (0);
1933 if (isl_schedule_node_get_type(node) == isl_schedule_node_band) {
1934 int anchored;
1935
1936 anchored = isl_schedule_node_is_subtree_anchored(node);
1937 if (anchored < 0)
1938 return isl_schedule_node_free(node);
1939 if (anchored)
1940 isl_die(isl_schedule_node_get_ctx(node),do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot delete band node with anchored subtree", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1943); return isl_schedule_node_free(node); } while (0)
1941 isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot delete band node with anchored subtree", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1943); return isl_schedule_node_free(node); } while (0)
1942 "cannot delete band node with anchored subtree",do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot delete band node with anchored subtree", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1943); return isl_schedule_node_free(node); } while (0)
1943 return isl_schedule_node_free(node))do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "cannot delete band node with anchored subtree", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 1943); return isl_schedule_node_free(node); } while (0);
1944 }
1945
1946 tree = isl_schedule_node_get_tree(node);
1947 if (!tree || isl_schedule_tree_has_children(tree)) {
1948 tree = isl_schedule_tree_child(tree, 0);
1949 } else {
1950 isl_schedule_tree_free(tree);
1951 tree = isl_schedule_node_get_leaf(node);
1952 }
1953 node = isl_schedule_node_graft_tree(node, tree);
1954
1955 return node;
1956}
1957
1958/* Compute the gist of the given band node with respect to "context".
1959 */
1960__isl_give isl_schedule_node *isl_schedule_node_band_gist(
1961 __isl_take isl_schedule_node *node, __isl_take isl_union_set *context)
1962{
1963 isl_schedule_tree *tree;
1964
1965 tree = isl_schedule_node_get_tree(node);
1966 tree = isl_schedule_tree_band_gist(tree, context);
1967 return isl_schedule_node_graft_tree(node, tree);
1968}
1969
1970/* Internal data structure for isl_schedule_node_gist.
1971 * "filters" contains an element for each outer filter node
1972 * with respect to the current position, each representing
1973 * the intersection of the previous element and the filter on the filter node.
1974 * The first element in the original context passed to isl_schedule_node_gist.
1975 */
1976struct isl_node_gist_data {
1977 isl_union_set_list *filters;
1978};
1979
1980/* Can we finish gisting at this node?
1981 * That is, is the filter on the current filter node a subset of
1982 * the original context passed to isl_schedule_node_gist?
1983 */
1984static int gist_done(__isl_keep isl_schedule_node *node,
1985 struct isl_node_gist_data *data)
1986{
1987 isl_union_set *filter, *outer;
1988 int subset;
1989
1990 filter = isl_schedule_node_filter_get_filter(node);
1991 outer = isl_union_set_list_get_union_set(data->filters, 0);
1992 subset = isl_union_set_is_subset(filter, outer);
1993 isl_union_set_free(outer);
1994 isl_union_set_free(filter);
1995
1996 return subset;
1997}
1998
1999/* Callback for "traverse" to enter a node and to move
2000 * to the deepest initial subtree that should be traversed
2001 * by isl_schedule_node_gist.
2002 *
2003 * The "filters" list is extended by one element each time
2004 * we come across a filter node by the result of intersecting
2005 * the last element in the list with the filter on the filter node.
2006 *
2007 * If the filter on the current filter node is a subset of
2008 * the original context passed to isl_schedule_node_gist,
2009 * then there is no need to go into its subtree since it cannot
2010 * be further simplified by the context. The "filters" list is
2011 * still extended for consistency, but the actual value of the
2012 * added element is immaterial since it will not be used.
2013 *
2014 * Otherwise, the filter on the current filter node is replaced by
2015 * the gist of the original filter with respect to the intersection
2016 * of the original context with the intermediate filters.
2017 *
2018 * If the new element in the "filters" list is empty, then no elements
2019 * can reach the descendants of the current filter node. The subtree
2020 * underneath the filter node is therefore removed.
2021 */
2022static __isl_give isl_schedule_node *gist_enter(
2023 __isl_take isl_schedule_node *node, void *user)
2024{
2025 struct isl_node_gist_data *data = user;
2026
2027 do {
2028 isl_union_set *filter, *inner;
2029 int done, empty;
2030 int n;
2031
2032 switch (isl_schedule_node_get_type(node)) {
2033 case isl_schedule_node_error:
2034 return isl_schedule_node_free(node);
2035 case isl_schedule_node_band:
2036 case isl_schedule_node_context:
2037 case isl_schedule_node_domain:
2038 case isl_schedule_node_leaf:
2039 case isl_schedule_node_sequence:
2040 case isl_schedule_node_set:
2041 continue;
2042 case isl_schedule_node_filter:
2043 break;
2044 }
2045 done = gist_done(node, data);
2046 filter = isl_schedule_node_filter_get_filter(node);
2047 if (done < 0 || done) {
2048 data->filters = isl_union_set_list_add(data->filters,
2049 filter);
2050 if (done < 0)
2051 return isl_schedule_node_free(node);
2052 return node;
2053 }
2054 n = isl_union_set_list_n_union_set(data->filters);
2055 inner = isl_union_set_list_get_union_set(data->filters, n - 1);
2056 filter = isl_union_set_gist(filter, isl_union_set_copy(inner));
2057 node = isl_schedule_node_filter_set_filter(node,
2058 isl_union_set_copy(filter));
2059 filter = isl_union_set_intersect(filter, inner);
2060 empty = isl_union_set_is_empty(filter);
2061 data->filters = isl_union_set_list_add(data->filters, filter);
2062 if (empty < 0)
2063 return isl_schedule_node_free(node);
2064 if (!empty)
2065 continue;
2066 node = isl_schedule_node_child(node, 0);
2067 node = isl_schedule_node_cut(node);
2068 node = isl_schedule_node_parent(node);
2069 return node;
2070 } while (isl_schedule_node_has_children(node) &&
2071 (node = isl_schedule_node_first_child(node)) != NULL((void*)0));
2072
2073 return node;
2074}
2075
2076/* Callback for "traverse" to leave a node for isl_schedule_node_gist.
2077 *
2078 * In particular, if the current node is a filter node, then we remove
2079 * the element on the "filters" list that was added when we entered
2080 * the node. There is no need to compute any gist here, since we
2081 * already did that when we entered the node.
2082 *
2083 * If the current node is a band node, then we compute the gist of
2084 * the band node with respect to the intersection of the original context
2085 * and the intermediate filters.
2086 *
2087 * If the current node is a sequence or set node, then some of
2088 * the filter children may have become empty and so they are removed.
2089 * If only one child is left, then the set or sequence node along with
2090 * the single remaining child filter is removed. The filter can be
2091 * removed because the filters on a sequence or set node are supposed
2092 * to partition the incoming domain instances.
2093 * In principle, it should then be impossible for there to be zero
2094 * remaining children, but should this happen, we replace the entire
2095 * subtree with an empty filter.
2096 */
2097static __isl_give isl_schedule_node *gist_leave(
2098 __isl_take isl_schedule_node *node, void *user)
2099{
2100 struct isl_node_gist_data *data = user;
2101 isl_schedule_tree *tree;
2102 int i, n;
2103 isl_union_set *filter;
2104
2105 switch (isl_schedule_node_get_type(node)) {
2106 case isl_schedule_node_error:
2107 return isl_schedule_node_free(node);
2108 case isl_schedule_node_filter:
2109 n = isl_union_set_list_n_union_set(data->filters);
2110 data->filters = isl_union_set_list_drop(data->filters,
2111 n - 1, 1);
2112 break;
2113 case isl_schedule_node_band:
2114 n = isl_union_set_list_n_union_set(data->filters);
2115 filter = isl_union_set_list_get_union_set(data->filters, n - 1);
2116 node = isl_schedule_node_band_gist(node, filter);
2117 break;
2118 case isl_schedule_node_set:
2119 case isl_schedule_node_sequence:
2120 tree = isl_schedule_node_get_tree(node);
2121 n = isl_schedule_tree_n_children(tree);
2122 for (i = n - 1; i >= 0; --i) {
2123 isl_schedule_tree *child;
2124 isl_union_set *filter;
2125 int empty;
2126
2127 child = isl_schedule_tree_get_child(tree, i);
2128 filter = isl_schedule_tree_filter_get_filter(child);
2129 empty = isl_union_set_is_empty(filter);
2130 isl_union_set_free(filter);
2131 isl_schedule_tree_free(child);
2132 if (empty < 0)
2133 tree = isl_schedule_tree_free(tree);
2134 else if (empty)
2135 tree = isl_schedule_tree_drop_child(tree, i);
2136 }
2137 n = isl_schedule_tree_n_children(tree);
2138 node = isl_schedule_node_graft_tree(node, tree);
2139 if (n == 1) {
2140 node = isl_schedule_node_delete(node);
2141 node = isl_schedule_node_delete(node);
2142 } else if (n == 0) {
2143 isl_space *space;
2144
2145 filter =
2146 isl_union_set_list_get_union_set(data->filters, 0);
2147 space = isl_union_set_get_space(filter);
2148 isl_union_set_free(filter);
2149 filter = isl_union_set_empty(space);
2150 node = isl_schedule_node_cut(node);
2151 node = isl_schedule_node_insert_filter(node, filter);
2152 }
2153 break;
2154 case isl_schedule_node_context:
2155 case isl_schedule_node_domain:
2156 case isl_schedule_node_leaf:
2157 break;
2158 }
2159
2160 return node;
2161}
2162
2163/* Compute the gist of the subtree at "node" with respect to
2164 * the reaching domain elements in "context".
2165 * In particular, compute the gist of all band and filter nodes
2166 * in the subtree with respect to "context". Children of set or sequence
2167 * nodes that end up with an empty filter are removed completely.
2168 *
2169 * We keep track of the intersection of "context" with all outer filters
2170 * of the current node within the subtree in the final element of "filters".
2171 * Initially, this list contains the single element "context" and it is
2172 * extended or shortened each time we enter or leave a filter node.
2173 */
2174__isl_give isl_schedule_node *isl_schedule_node_gist(
2175 __isl_take isl_schedule_node *node, __isl_take isl_union_set *context)
2176{
2177 struct isl_node_gist_data data;
2178
2179 data.filters = isl_union_set_list_from_union_set(context);
2180 node = traverse(node, &gist_enter, &gist_leave, &data);
2181 isl_union_set_list_free(data.filters);
2182 return node;
2183}
2184
2185/* Intersect the domain of domain node "node" with "domain".
2186 *
2187 * If the domain of "node" is already a subset of "domain",
2188 * then nothing needs to be changed.
2189 *
2190 * Otherwise, we replace the domain of the domain node by the intersection
2191 * and simplify the subtree rooted at "node" with respect to this intersection.
2192 */
2193__isl_give isl_schedule_node *isl_schedule_node_domain_intersect_domain(
2194 __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain)
2195{
2196 isl_schedule_tree *tree;
2197 isl_union_set *uset;
2198 int is_subset;
2199
2200 if (!node || !domain)
2201 goto error;
2202
2203 uset = isl_schedule_tree_domain_get_domain(node->tree);
2204 is_subset = isl_union_set_is_subset(uset, domain);
2205 isl_union_set_free(uset);
2206 if (is_subset < 0)
2207 goto error;
2208 if (is_subset) {
2209 isl_union_set_free(domain);
2210 return node;
2211 }
2212
2213 tree = isl_schedule_tree_copy(node->tree);
2214 uset = isl_schedule_tree_domain_get_domain(tree);
2215 uset = isl_union_set_intersect(uset, domain);
2216 tree = isl_schedule_tree_domain_set_domain(tree,
2217 isl_union_set_copy(uset));
2218 node = isl_schedule_node_graft_tree(node, tree);
2219
2220 node = isl_schedule_node_child(node, 0);
2221 node = isl_schedule_node_gist(node, uset);
2222 node = isl_schedule_node_parent(node);
2223
2224 return node;
2225error:
2226 isl_schedule_node_free(node);
2227 isl_union_set_free(domain);
2228 return NULL((void*)0);
2229}
2230
2231/* Reset the user pointer on all identifiers of parameters and tuples
2232 * in the schedule node "node".
2233 */
2234__isl_give isl_schedule_node *isl_schedule_node_reset_user(
2235 __isl_take isl_schedule_node *node)
2236{
2237 isl_schedule_tree *tree;
2238
2239 tree = isl_schedule_node_get_tree(node);
2240 tree = isl_schedule_tree_reset_user(tree);
2241 node = isl_schedule_node_graft_tree(node, tree);
2242
2243 return node;
2244}
2245
2246/* Align the parameters of the schedule node "node" to those of "space".
2247 */
2248__isl_give isl_schedule_node *isl_schedule_node_align_params(
2249 __isl_take isl_schedule_node *node, __isl_take isl_space *space)
2250{
2251 isl_schedule_tree *tree;
2252
2253 tree = isl_schedule_node_get_tree(node);
2254 tree = isl_schedule_tree_align_params(tree, space);
2255 node = isl_schedule_node_graft_tree(node, tree);
2256
2257 return node;
2258}
2259
2260/* Compute the pullback of schedule node "node"
2261 * by the function represented by "upma".
2262 * In other words, plug in "upma" in the iteration domains
2263 * of schedule node "node".
2264 *
2265 * Note that this is only a helper function for
2266 * isl_schedule_pullback_union_pw_multi_aff. In order to maintain consistency,
2267 * this function should not be called on a single node without also
2268 * calling it on all the other nodes.
2269 */
2270__isl_give isl_schedule_node *isl_schedule_node_pullback_union_pw_multi_aff(
2271 __isl_take isl_schedule_node *node,
2272 __isl_take isl_union_pw_multi_aff *upma)
2273{
2274 isl_schedule_tree *tree;
2275
2276 tree = isl_schedule_node_get_tree(node);
2277 tree = isl_schedule_tree_pullback_union_pw_multi_aff(tree, upma);
2278 node = isl_schedule_node_graft_tree(node, tree);
2279
2280 return node;
2281}
2282
2283/* Return the position of the subtree containing "node" among the children
2284 * of "ancestor". "node" is assumed to be a descendant of "ancestor".
2285 * In particular, both nodes should point to the same schedule tree.
2286 *
2287 * Return -1 on error.
2288 */
2289int isl_schedule_node_get_ancestor_child_position(
2290 __isl_keep isl_schedule_node *node,
2291 __isl_keep isl_schedule_node *ancestor)
2292{
2293 int n1, n2;
2294 isl_schedule_tree *tree;
2295
2296 if (!node || !ancestor)
2297 return -1;
2298
2299 if (node->schedule != ancestor->schedule)
2300 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "not a descendant", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 2301); return -1; } while (0)
2301 "not a descendant", return -1)do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "not a descendant", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 2301); return -1; } while (0);
2302
2303 n1 = isl_schedule_node_get_tree_depth(ancestor);
2304 n2 = isl_schedule_node_get_tree_depth(node);
2305
2306 if (n1 >= n2)
2307 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "not a descendant", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 2308); return -1; } while (0)
2308 "not a descendant", return -1)do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "not a descendant", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 2308); return -1; } while (0);
2309 tree = isl_schedule_tree_list_get_schedule_tree(node->ancestors, n1);
2310 isl_schedule_tree_free(tree);
2311 if (tree != ancestor->tree)
2312 isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "not a descendant", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 2313); return -1; } while (0)
2313 "not a descendant", return -1)do { isl_handle_error(isl_schedule_node_get_ctx(node), isl_error_invalid
, "not a descendant", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 2313); return -1; } while (0);
2314
2315 return node->child_pos[n1];
2316}
2317
2318/* Given two nodes that point to the same schedule tree, return their
2319 * closest shared ancestor.
2320 *
2321 * Since the two nodes point to the same schedule, they share at least
2322 * one ancestor, the root of the schedule. We move down from the root
2323 * to the first ancestor where the respective children have a different
2324 * child position. This is the requested ancestor.
2325 * If there is no ancestor where the children have a different position,
2326 * then one node is an ancestor of the other and then this node is
2327 * the requested ancestor.
2328 */
2329__isl_give isl_schedule_node *isl_schedule_node_get_shared_ancestor(
2330 __isl_keep isl_schedule_node *node1,
2331 __isl_keep isl_schedule_node *node2)
2332{
2333 int i, n1, n2;
2334
2335 if (!node1 || !node2)
2336 return NULL((void*)0);
2337 if (node1->schedule != node2->schedule)
2338 isl_die(isl_schedule_node_get_ctx(node1), isl_error_invalid,do { isl_handle_error(isl_schedule_node_get_ctx(node1), isl_error_invalid
, "not part of same schedule", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 2339); return ((void*)0); } while (0)
2339 "not part of same schedule", return NULL)do { isl_handle_error(isl_schedule_node_get_ctx(node1), isl_error_invalid
, "not part of same schedule", "/tmp/buildd/llvm-toolchain-snapshot-3.7~svn233527/polly/lib/External/isl/isl_schedule_node.c"
, 2339); return ((void*)0); } while (0);
2340 n1 = isl_schedule_node_get_tree_depth(node1);
2341 n2 = isl_schedule_node_get_tree_depth(node2);
2342 if (n2 < n1)
2343 return isl_schedule_node_get_shared_ancestor(node2, node1);
2344 if (n1 == 0)
2345 return isl_schedule_node_copy(node1);
2346 if (isl_schedule_node_is_equal(node1, node2))
2347 return isl_schedule_node_copy(node1);
2348
2349 for (i = 0; i < n1; ++i)
2350 if (node1->child_pos[i] != node2->child_pos[i])
2351 break;
2352
2353 node1 = isl_schedule_node_copy(node1);
2354 return isl_schedule_node_ancestor(node1, n1 - i);
2355}
2356
2357/* Print "node" to "p".
2358 */
2359__isl_give isl_printer *isl_printer_print_schedule_node(
2360 __isl_take isl_printer *p, __isl_keep isl_schedule_node *node)
2361{
2362 if (!node)
2363 return isl_printer_free(p);
2364 return isl_printer_print_schedule_tree_mark(p, node->schedule->root,
2365 isl_schedule_tree_list_n_schedule_tree(node->ancestors),
2366 node->child_pos);
2367}
2368
2369void isl_schedule_node_dump(__isl_keep isl_schedule_node *node)
2370{
2371 isl_ctx *ctx;
2372 isl_printer *printer;
2373
2374 if (!node)
2375 return;
2376
2377 ctx = isl_schedule_node_get_ctx(node);
2378 printer = isl_printer_to_file(ctx, stderrstderr);
2379 printer = isl_printer_set_yaml_style(printer, ISL_YAML_STYLE_BLOCK0);
2380 printer = isl_printer_print_schedule_node(printer, node);
2381
2382 isl_printer_free(printer);
2383}