Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

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