Bug Summary

File:tools/polly/lib/External/isl/isl_schedule_node.c
Warning:line 4103, column 11
Use of memory after it is freed

Annotated Source Code

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