Bug Summary

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