File: | tools/polly/lib/External/isl/isl_schedule_node.c |
Warning: | line 4170, column 2 Use of memory after it is freed |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
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; | |||
54 | error: | |||
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 | */ | |||
102 | isl_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 | */ | |||
125 | enum 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 | */ | |||
134 | enum 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-9~svn362543/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-9~svn362543/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) | |||
227 | return NULL((void*)0); | |||
228 | if (--node->ref > 0) | |||
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); | |||
236 | ||||
237 | return NULL((void*)0); | |||
238 | } | |||
239 | ||||
240 | /* Do "node1" and "node2" point to the same position in the same | |||
241 | * schedule? | |||
242 | */ | |||
243 | isl_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 | */ | |||
271 | int 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 | */ | |||
308 | struct 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 | ||||
317 | static 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 | */ | |||
328 | static 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 | */ | |||
392 | static 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 | */ | |||
440 | static 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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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 | */ | |||
514 | static 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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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 | */ | |||
605 | static 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 * | |||
656 | isl_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 * | |||
708 | isl_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 | */ | |||
929 | int 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 | */ | |||
940 | isl_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 | */ | |||
952 | int 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-9~svn362543/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-9~svn362543/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 | */ | |||
973 | isl_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 | */ | |||
993 | isl_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 | */ | |||
1021 | isl_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 | */ | |||
1038 | int 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-9~svn362543/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-9~svn362543/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-9~svn362543/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) | |||
1098 | return NULL((void*)0); | |||
1099 | if (!isl_schedule_node_has_parent(node)) | |||
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-9~svn362543/tools/polly/lib/External/isl/isl_schedule_node.c" , 1102); return isl_schedule_node_free(node); } while (0) | |||
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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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 | */ | |||
1255 | static __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 | */ | |||
1289 | struct 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 | */ | |||
1304 | static __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 | */ | |||
1331 | static __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 | */ | |||
1347 | isl_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 | */ | |||
1369 | struct 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 | */ | |||
1379 | static 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 | */ | |||
1395 | isl_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 | */ | |||
1416 | struct 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 | */ | |||
1429 | static __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 | */ | |||
1444 | static __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 | */ | |||
1476 | isl_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 | */ | |||
1505 | isl_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 | */ | |||
1515 | unsigned 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 | */ | |||
1523 | isl_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 | */ | |||
1556 | isl_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-9~svn362543/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-9~svn362543/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 | */ | |||
1639 | enum 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 | */ | |||
1668 | enum 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 * | |||
1682 | isl_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); | |||
1721 | error: | |||
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 | */ | |||
1744 | static 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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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); | |||
1789 | error: | |||
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-9~svn362543/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-9~svn362543/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-9~svn362543/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); | |||
1819 | error: | |||
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-9~svn362543/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-9~svn362543/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-9~svn362543/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); | |||
1849 | error: | |||
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 | */ | |||
1858 | static 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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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); | |||
1904 | error: | |||
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-9~svn362543/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-9~svn362543/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-9~svn362543/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); | |||
1955 | error: | |||
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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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 * | |||
2079 | isl_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); | |||
2093 | error: | |||
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); | |||
2124 | error: | |||
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); | |||
2154 | error: | |||
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; | |||
2186 | error: | |||
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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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; | |||
2237 | error: | |||
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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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 | */ | |||
2304 | static __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)); | |||
2378 | error: | |||
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 | */ | |||
2387 | static 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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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; | |||
2441 | error: | |||
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 | */ | |||
2570 | static __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; | |||
2608 | error: | |||
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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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 | */ | |||
2746 | struct 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 | */ | |||
2763 | static 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 | */ | |||
2790 | static __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 | */ | |||
2836 | static __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 | */ | |||
2857 | static __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-9~svn362543/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-9~svn362543/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-9~svn362543/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 | */ | |||
2928 | static __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-9~svn362543/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-9~svn362543/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-9~svn362543/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 | */ | |||
2967 | static __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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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 | */ | |||
3030 | static __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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/tools/polly/lib/External/isl/isl_schedule_node.c" , 3194); return isl_schedule_node_free(node); } while (0); | |||
3195 | ||||
3196 | return node; | |||
3197 | error: | |||
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 | */ | |||
3224 | struct 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 | */ | |||
3236 | static __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 | */ | |||
3275 | static __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 | */ | |||
3305 | static __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 | */ | |||
3330 | static 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 | */ | |||
3377 | static __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 | */ | |||
3465 | static __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; | |||
3600 | error: | |||
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; | |||
3625 | error: | |||
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 | */ | |||
3637 | struct 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 | */ | |||
3656 | static __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 | */ | |||
3723 | static __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 | */ | |||
3810 | struct 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 | */ | |||
3829 | static __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 | */ | |||
3902 | static __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 | */ | |||
3990 | static 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 | */ | |||
4025 | static 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); | |||
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 | */ | |||
4058 | static __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-9~svn362543/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-9~svn362543/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-9~svn362543/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 | */ | |||
4094 | static __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-9~svn362543/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-9~svn362543/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-9~svn362543/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 | */ | |||
4137 | static __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) | |||
4149 | goto error; | |||
4150 | if (in_ext) { | |||
4151 | int disjoint; | |||
4152 | ||||
4153 | disjoint = is_disjoint_extension(node, extension); | |||
4154 | if (disjoint < 0) | |||
4155 | goto error; | |||
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; | |||
4169 | error: | |||
4170 | isl_schedule_node_free(node); | |||
| ||||
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 | */ | |||
4182 | static __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 | */ | |||
4219 | static __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); | |||
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 | */ | |||
4263 | static __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-9~svn362543/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-9~svn362543/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-9~svn362543/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 | */ | |||
4331 | static __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) | |||
4336 | goto error; | |||
4337 | if (check_insert(node) < 0) | |||
4338 | goto error; | |||
4339 | ||||
4340 | if (isl_schedule_node_get_type(graft) == isl_schedule_node_domain) | |||
4341 | graft = extension_from_domain(graft, node); | |||
4342 | ||||
4343 | if (!graft) | |||
4344 | goto error; | |||
4345 | if (isl_schedule_node_get_type(graft) != isl_schedule_node_extension) | |||
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-9~svn362543/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-9~svn362543/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-9~svn362543/tools/polly/lib/External/isl/isl_schedule_node.c" , 4348); goto error; } while (0); | |||
4349 | ||||
4350 | return graft_extension(node, graft, before); | |||
4351 | error: | |||
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); | |||
| ||||
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 | */ | |||
4408 | static __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; | |||
4470 | error: | |||
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 | */ | |||
4561 | struct 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 | */ | |||
4575 | static __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 | */ | |||
4654 | int 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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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-9~svn362543/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 | ||||
4734 | void 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 | } |