Bug Summary

File:tools/polly/lib/External/isl/isl_schedule_node.c
Location:line 1930, column 13
Description:Use of memory after it is freed

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