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