update pet for support for recent clangs
[ppcg.git] / grouping.c
blob944285077b6d56e22f4bd7853ca629bdba141b4d
1 /*
2 * Copyright 2016 Sven Verdoolaege
4 * Use of this software is governed by the MIT license
6 * Written by Sven Verdoolaege.
7 */
9 #include <isl/aff.h>
10 #include <isl/union_set.h>
11 #include <isl/union_map.h>
12 #include <isl/schedule.h>
13 #include <isl/schedule_node.h>
15 #include "ppcg.h"
17 /* Internal data structure for use during the detection of statements
18 * that can be grouped.
20 * "sc" contains the original schedule constraints (not a copy).
21 * "dep" contains the intersection of the validity and the proximity
22 * constraints in "sc". It may be NULL if it has not been computed yet.
23 * "group_id" is the identifier for the next group that is extracted.
25 * "domain" is the set of statement instances that belong to any of the groups.
26 * "contraction" maps the elements of "domain" to the corresponding group
27 * instances.
28 * "schedule" schedules the statements in each group relatively to each other.
29 * These last three fields are NULL if no groups have been found so far.
31 struct ppcg_grouping {
32 isl_schedule_constraints *sc;
34 isl_union_map *dep;
35 int group_id;
37 isl_union_set *domain;
38 isl_union_pw_multi_aff *contraction;
39 isl_schedule *schedule;
42 /* Clear all memory allocated by "grouping".
44 static void ppcg_grouping_clear(struct ppcg_grouping *grouping)
46 isl_union_map_free(grouping->dep);
47 isl_union_set_free(grouping->domain);
48 isl_union_pw_multi_aff_free(grouping->contraction);
49 isl_schedule_free(grouping->schedule);
52 /* Compute the intersection of the proximity and validity dependences
53 * in grouping->sc and store the result in grouping->dep, unless
54 * this intersection has been computed before.
56 static isl_stat ppcg_grouping_compute_dep(struct ppcg_grouping *grouping)
58 isl_union_map *validity, *proximity;
60 if (grouping->dep)
61 return isl_stat_ok;
63 validity = isl_schedule_constraints_get_validity(grouping->sc);
64 proximity = isl_schedule_constraints_get_proximity(grouping->sc);
65 grouping->dep = isl_union_map_intersect(validity, proximity);
67 if (!grouping->dep)
68 return isl_stat_error;
70 return isl_stat_ok;
73 /* Information extracted from one or more consecutive leaves
74 * in the input schedule.
76 * "list" contains the sets of statement instances in the leaves,
77 * one element in the list for each original leaf.
78 * "domain" contains the union of the sets in "list".
79 * "prefix" contains the prefix schedule of these elements.
81 struct ppcg_grouping_leaf {
82 isl_union_set *domain;
83 isl_union_set_list *list;
84 isl_multi_union_pw_aff *prefix;
87 /* Free all memory allocated for "leaves".
89 static void ppcg_grouping_leaf_free(int n, struct ppcg_grouping_leaf leaves[n])
91 int i;
93 if (!leaves)
94 return;
96 for (i = 0; i < n; ++i) {
97 isl_union_set_free(leaves[i].domain);
98 isl_union_set_list_free(leaves[i].list);
99 isl_multi_union_pw_aff_free(leaves[i].prefix);
102 free(leaves);
105 /* Short-hand for retrieving the prefix schedule at "node"
106 * in the form of an isl_multi_union_pw_aff.
108 static __isl_give isl_multi_union_pw_aff *get_prefix(
109 __isl_keep isl_schedule_node *node)
111 return isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(node);
114 /* Return an array of "n" elements with information extracted from
115 * the "n" children of "node" starting at "first", all of which
116 * are known to be filtered leaves.
118 struct ppcg_grouping_leaf *extract_leaves(__isl_keep isl_schedule_node *node,
119 int first, int n)
121 int i;
122 isl_ctx *ctx;
123 struct ppcg_grouping_leaf *leaves;
125 if (!node)
126 return NULL;
128 ctx = isl_schedule_node_get_ctx(node);
129 leaves = isl_calloc_array(ctx, struct ppcg_grouping_leaf, n);
130 if (!leaves)
131 return NULL;
133 for (i = 0; i < n; ++i) {
134 isl_schedule_node *child;
135 isl_union_set *domain;
137 child = isl_schedule_node_get_child(node, first + i);
138 child = isl_schedule_node_child(child, 0);
139 domain = isl_schedule_node_get_domain(child);
140 leaves[i].domain = isl_union_set_copy(domain);
141 leaves[i].list = isl_union_set_list_from_union_set(domain);
142 leaves[i].prefix = get_prefix(child);
143 isl_schedule_node_free(child);
146 return leaves;
149 /* Internal data structure used by merge_leaves.
151 * "src" and "dst" point to the two consecutive leaves that are
152 * under investigation for being merged.
153 * "merge" is initially set to 0 and is set to 1 as soon as
154 * it turns out that it is useful to merge the two leaves.
156 struct ppcg_merge_leaves_data {
157 int merge;
158 struct ppcg_grouping_leaf *src;
159 struct ppcg_grouping_leaf *dst;
162 /* Given a relation "map" between instances of two statements A and B,
163 * does it relate every instance of A (according to the domain of "src")
164 * to every instance of B (according to the domain of "dst")?
166 static isl_bool covers_src_and_dst(__isl_keep isl_map *map,
167 struct ppcg_grouping_leaf *src, struct ppcg_grouping_leaf *dst)
169 isl_space *space;
170 isl_set *set1, *set2;
171 isl_bool is_subset;
173 space = isl_space_domain(isl_map_get_space(map));
174 set1 = isl_union_set_extract_set(src->domain, space);
175 set2 = isl_map_domain(isl_map_copy(map));
176 is_subset = isl_set_is_subset(set1, set2);
177 isl_set_free(set1);
178 isl_set_free(set2);
179 if (is_subset < 0 || !is_subset)
180 return is_subset;
182 space = isl_space_range(isl_map_get_space(map));
183 set1 = isl_union_set_extract_set(dst->domain, space);
184 set2 = isl_map_range(isl_map_copy(map));
185 is_subset = isl_set_is_subset(set1, set2);
186 isl_set_free(set1);
187 isl_set_free(set2);
189 return is_subset;
192 /* Given a relation "map" between instances of two statements A and B,
193 * are pairs of related instances executed together in the input schedule?
194 * That is, is each pair of instances assigned the same value
195 * by the corresponding prefix schedules?
197 * In particular, select the subset of "map" that has pairs of elements
198 * with the same value for the prefix schedules and then check
199 * if "map" is still a subset of the result.
201 static isl_bool matches_prefix(__isl_keep isl_map *map,
202 struct ppcg_grouping_leaf *src, struct ppcg_grouping_leaf *dst)
204 isl_union_map *umap, *equal;
205 isl_multi_union_pw_aff *src_prefix, *dst_prefix, *prefix;
206 isl_bool is_subset;
208 src_prefix = isl_multi_union_pw_aff_copy(src->prefix);
209 dst_prefix = isl_multi_union_pw_aff_copy(dst->prefix);
210 prefix = isl_multi_union_pw_aff_union_add(src_prefix, dst_prefix);
212 umap = isl_union_map_from_map(isl_map_copy(map));
213 equal = isl_union_map_copy(umap);
214 equal = isl_union_map_eq_at_multi_union_pw_aff(equal, prefix);
216 is_subset = isl_union_map_is_subset(umap, equal);
218 isl_union_map_free(umap);
219 isl_union_map_free(equal);
221 return is_subset;
224 /* Given a set of validity and proximity schedule constraints "map"
225 * between statements in consecutive leaves in a valid schedule,
226 * should the two leaves be merged into one?
228 * In particular, the two are merged if the constraints form
229 * a bijection between every instance of the first statement and
230 * every instance of the second statement. Moreover, each
231 * pair of such dependent instances needs to be executed consecutively
232 * in the input schedule. That is, they need to be assigned
233 * the same value by their prefix schedules.
235 * What this means is that for each instance of the first statement
236 * there is exactly one instance of the second statement that
237 * is executed immediately after the instance of the first statement and
238 * that, moreover, both depends on this statement instance and
239 * should be brought as close as possible to this statement instance.
240 * In other words, it is both possible to execute the two instances
241 * together (according to the input schedule) and desirable to do so
242 * (according to the validity and proximity schedule constraints).
244 static isl_stat check_merge(__isl_take isl_map *map, void *user)
246 struct ppcg_merge_leaves_data *data = user;
247 isl_bool ok;
249 ok = covers_src_and_dst(map, data->src, data->dst);
250 if (ok >= 0 && ok)
251 ok = isl_map_is_bijective(map);
252 if (ok >= 0 && ok)
253 ok = matches_prefix(map, data->src, data->dst);
255 isl_map_free(map);
257 if (ok < 0)
258 return isl_stat_error;
259 if (!ok)
260 return isl_stat_ok;
262 data->merge = 1;
263 return isl_stat_error;
266 /* Merge the leaves at position "pos" and "pos + 1" in "leaves".
268 static isl_stat merge_pair(int n, struct ppcg_grouping_leaf leaves[n], int pos)
270 int i;
272 leaves[pos].domain = isl_union_set_union(leaves[pos].domain,
273 leaves[pos + 1].domain);
274 leaves[pos].list = isl_union_set_list_concat(leaves[pos].list,
275 leaves[pos + 1].list);
276 leaves[pos].prefix = isl_multi_union_pw_aff_union_add(
277 leaves[pos].prefix, leaves[pos + 1].prefix);
278 for (i = pos + 1; i + 1 < n; ++i)
279 leaves[i] = leaves[i + 1];
280 leaves[n - 1].domain = NULL;
281 leaves[n - 1].list = NULL;
282 leaves[n - 1].prefix = NULL;
284 if (!leaves[pos].domain || !leaves[pos].list || !leaves[pos].prefix)
285 return isl_stat_error;
287 return isl_stat_ok;
290 /* Merge pairs of consecutive leaves in "leaves" taking into account
291 * the intersection of validity and proximity schedule constraints "dep".
293 * If a leaf has been merged with the next leaf, then the combination
294 * is checked again for merging with the next leaf.
295 * That is, if the leaves are A, B and C, then B may not have been
296 * merged with C, but after merging A and B, it could still be useful
297 * to merge the combination AB with C.
299 * Two leaves A and B are merged if there are instances of at least
300 * one pair of statements, one statement in A and one B, such that
301 * the validity and proximity schedule constraints between them
302 * make them suitable for merging according to check_merge.
304 * Return the final number of leaves in the sequence, or -1 on error.
306 static int merge_leaves(int n, struct ppcg_grouping_leaf leaves[n],
307 __isl_keep isl_union_map *dep)
309 int i;
310 struct ppcg_merge_leaves_data data;
312 for (i = n - 1; i >= 0; --i) {
313 isl_union_map *dep_i;
314 isl_stat ok;
316 if (i + 1 >= n)
317 continue;
319 dep_i = isl_union_map_copy(dep);
320 dep_i = isl_union_map_intersect_domain(dep_i,
321 isl_union_set_copy(leaves[i].domain));
322 dep_i = isl_union_map_intersect_range(dep_i,
323 isl_union_set_copy(leaves[i + 1].domain));
324 data.merge = 0;
325 data.src = &leaves[i];
326 data.dst = &leaves[i + 1];
327 ok = isl_union_map_foreach_map(dep_i, &check_merge, &data);
328 isl_union_map_free(dep_i);
329 if (ok < 0 && !data.merge)
330 return -1;
331 if (!data.merge)
332 continue;
333 if (merge_pair(n, leaves, i) < 0)
334 return -1;
335 --n;
336 ++i;
339 return n;
342 /* Construct a schedule with "domain" as domain, that executes
343 * the elements of "list" in order (as a sequence).
345 static __isl_give isl_schedule *schedule_from_domain_and_list(
346 __isl_keep isl_union_set *domain, __isl_keep isl_union_set_list *list)
348 isl_schedule *schedule;
349 isl_schedule_node *node;
351 schedule = isl_schedule_from_domain(isl_union_set_copy(domain));
352 node = isl_schedule_get_root(schedule);
353 isl_schedule_free(schedule);
354 node = isl_schedule_node_child(node, 0);
355 list = isl_union_set_list_copy(list);
356 node = isl_schedule_node_insert_sequence(node, list);
357 schedule = isl_schedule_node_get_schedule(node);
358 isl_schedule_node_free(node);
360 return schedule;
363 /* Construct a unique identifier for a group in "grouping".
365 * The name is of the form G_n, with n the first value starting at
366 * grouping->group_id that does not result in an identifier
367 * that is already in use in the domain of the original schedule
368 * constraints.
370 static isl_id *construct_group_id(struct ppcg_grouping *grouping,
371 __isl_take isl_space *space)
373 isl_ctx *ctx;
374 isl_id *id;
375 isl_bool empty;
376 isl_union_set *domain;
378 if (!space)
379 return NULL;
381 ctx = isl_space_get_ctx(space);
382 domain = isl_schedule_constraints_get_domain(grouping->sc);
384 do {
385 char buffer[20];
386 isl_id *id;
387 isl_set *set;
389 snprintf(buffer, sizeof(buffer), "G_%d", grouping->group_id);
390 grouping->group_id++;
391 id = isl_id_alloc(ctx, buffer, NULL);
392 space = isl_space_set_tuple_id(space, isl_dim_set, id);
393 set = isl_union_set_extract_set(domain, isl_space_copy(space));
394 empty = isl_set_plain_is_empty(set);
395 isl_set_free(set);
396 } while (empty >= 0 && !empty);
398 if (empty < 0)
399 space = isl_space_free(space);
401 id = isl_space_get_tuple_id(space, isl_dim_set);
403 isl_space_free(space);
404 isl_union_set_free(domain);
406 return id;
409 /* Construct a contraction from "prefix" and "domain" for a new group
410 * in "grouping".
412 * The values of the prefix schedule "prefix" are used as instances
413 * of the new group. The identifier of the group is constructed
414 * in such a way that it does not conflict with those of earlier
415 * groups nor with statements in the domain of the original
416 * schedule constraints.
417 * The isl_multi_union_pw_aff "prefix" then simply needs to be
418 * converted to an isl_union_pw_multi_aff. However, this is not
419 * possible if "prefix" is zero-dimensional, so in this case,
420 * a contraction is constructed from "domain" instead.
422 static isl_union_pw_multi_aff *group_contraction_from_prefix_and_domain(
423 struct ppcg_grouping *grouping,
424 __isl_keep isl_multi_union_pw_aff *prefix,
425 __isl_keep isl_union_set *domain)
427 isl_id *id;
428 isl_space *space;
429 int dim;
431 space = isl_multi_union_pw_aff_get_space(prefix);
432 if (!space)
433 return NULL;
434 dim = isl_space_dim(space, isl_dim_set);
435 id = construct_group_id(grouping, space);
436 if (dim == 0) {
437 isl_multi_val *mv;
439 space = isl_multi_union_pw_aff_get_space(prefix);
440 space = isl_space_set_tuple_id(space, isl_dim_set, id);
441 mv = isl_multi_val_zero(space);
442 domain = isl_union_set_copy(domain);
443 return isl_union_pw_multi_aff_multi_val_on_domain(domain, mv);
445 prefix = isl_multi_union_pw_aff_copy(prefix);
446 prefix = isl_multi_union_pw_aff_set_tuple_id(prefix, isl_dim_out, id);
447 return isl_union_pw_multi_aff_from_multi_union_pw_aff(prefix);
450 /* Extend "grouping" with groups corresponding to merged
451 * leaves in the list of potentially merged leaves "leaves".
453 * The "list" field of each element in "leaves" contains a list
454 * of the instances sets of the original leaves that have been
455 * merged into this element. If at least two of the original leaves
456 * have been merged into a given element, then add the corresponding
457 * group to "grouping".
458 * In particular, the domain is extended with the statement instances
459 * of the merged leaves, the contraction is extended with a mapping
460 * of these statement instances to instances of a new group and
461 * the schedule is extended with a schedule that executes
462 * the statement instances according to the order of the leaves
463 * in which they appear.
464 * Since the instances of the groups should already be scheduled apart
465 * in the schedule into which this schedule will be plugged in,
466 * the schedules of the individual groups are combined independently
467 * of each other (as a set).
469 static isl_stat add_groups(struct ppcg_grouping *grouping,
470 int n, struct ppcg_grouping_leaf leaves[n])
472 int i;
474 for (i = 0; i < n; ++i) {
475 int n_leaf;
476 isl_schedule *schedule;
477 isl_union_set *domain;
478 isl_union_pw_multi_aff *upma;
480 n_leaf = isl_union_set_list_n_union_set(leaves[i].list);
481 if (n_leaf < 0)
482 return isl_stat_error;
483 if (n_leaf <= 1)
484 continue;
485 schedule = schedule_from_domain_and_list(leaves[i].domain,
486 leaves[i].list);
487 upma = group_contraction_from_prefix_and_domain(grouping,
488 leaves[i].prefix, leaves[i].domain);
490 domain = isl_union_set_copy(leaves[i].domain);
491 if (grouping->domain) {
492 domain = isl_union_set_union(domain, grouping->domain);
493 upma = isl_union_pw_multi_aff_union_add(upma,
494 grouping->contraction);
495 schedule = isl_schedule_set(schedule,
496 grouping->schedule);
498 grouping->domain = domain;
499 grouping->contraction = upma;
500 grouping->schedule = schedule;
502 if (!grouping->domain || !grouping->contraction ||
503 !grouping->schedule)
504 return isl_stat_error;
507 return isl_stat_ok;
510 /* Look for any pairs of consecutive leaves among the "n" children of "node"
511 * starting at "first" that should be merged together.
512 * Store the results in "grouping".
514 * First make sure the intersection of validity and proximity
515 * schedule constraints is available and extract the required
516 * information from the "n" leaves.
517 * Then try and merge consecutive leaves based on the validity
518 * and proximity constraints.
519 * If any pairs were successfully merged, then add groups
520 * corresponding to the merged leaves to "grouping".
522 static isl_stat group_subsequence(__isl_keep isl_schedule_node *node,
523 int first, int n, struct ppcg_grouping *grouping)
525 int n_merge;
526 struct ppcg_grouping_leaf *leaves;
528 if (ppcg_grouping_compute_dep(grouping) < 0)
529 return isl_stat_error;
531 leaves = extract_leaves(node, first, n);
532 if (!leaves)
533 return isl_stat_error;
535 n_merge = merge_leaves(n, leaves, grouping->dep);
536 if (n_merge >= 0 && n_merge < n &&
537 add_groups(grouping, n_merge, leaves) < 0)
538 return isl_stat_error;
540 ppcg_grouping_leaf_free(n, leaves);
542 return isl_stat_ok;
545 /* If "node" is a sequence, then check if it has any consecutive
546 * leaves that should be merged together and store the results
547 * in "grouping".
549 * In particular, call group_subsequence on each consecutive
550 * sequence of (filtered) leaves among the children of "node".
552 static isl_bool detect_groups(__isl_keep isl_schedule_node *node, void *user)
554 int i, n, first;
555 isl_bool has_only_leaves;
556 struct ppcg_grouping *grouping = user;
558 if (isl_schedule_node_get_type(node) != isl_schedule_node_sequence)
559 return isl_bool_true;
561 n = isl_schedule_node_n_children(node);
562 if (n < 0)
563 return isl_bool_error;
565 first = -1;
566 for (i = 0; i < n; ++i) {
567 isl_schedule_node *child;
568 enum isl_schedule_node_type type;
570 child = isl_schedule_node_get_child(node, i);
571 child = isl_schedule_node_child(child, 0);
572 type = isl_schedule_node_get_type(child);
573 isl_schedule_node_free(child);
575 if (first >= 0 && type != isl_schedule_node_leaf) {
576 if (group_subsequence(node, first, i - first,
577 grouping) < 0)
578 return isl_bool_error;
579 first = -1;
581 if (first < 0 && type == isl_schedule_node_leaf)
582 first = i;
584 if (first >= 0) {
585 if (group_subsequence(node, first, n - first, grouping) < 0)
586 return isl_bool_error;
589 return isl_bool_true;
592 /* Complete "grouping" to cover all statement instances in the domain
593 * of grouping->sc.
595 * In particular, grouping->domain is set to the full set of statement
596 * instances; group->contraction is extended with an identity
597 * contraction on the additional instances and group->schedule
598 * is extended with an independent schedule on those additional instances.
599 * In the extension of group->contraction, the additional instances
600 * are split into those belong to different statements and those
601 * that belong to some of the same statements. The first group
602 * is replaced by its universe in order to simplify the contraction extension.
604 static void complete_grouping(struct ppcg_grouping *grouping)
606 isl_union_set *domain, *left, *overlap;
607 isl_union_pw_multi_aff *upma;
608 isl_schedule *schedule;
610 domain = isl_schedule_constraints_get_domain(grouping->sc);
611 left = isl_union_set_subtract(isl_union_set_copy(domain),
612 isl_union_set_copy(grouping->domain));
613 schedule = isl_schedule_from_domain(isl_union_set_copy(left));
614 schedule = isl_schedule_set(schedule, grouping->schedule);
615 grouping->schedule = schedule;
617 overlap = isl_union_set_universe(grouping->domain);
618 grouping->domain = domain;
619 overlap = isl_union_set_intersect(isl_union_set_copy(left), overlap);
620 left = isl_union_set_subtract(left, isl_union_set_copy(overlap));
621 left = isl_union_set_universe(left);
622 left = isl_union_set_union(left, overlap);
623 upma = isl_union_set_identity_union_pw_multi_aff(left);
624 upma = isl_union_pw_multi_aff_union_add(upma, grouping->contraction);
625 grouping->contraction = upma;
628 /* Compute a schedule on the domain of "sc" that respects the schedule
629 * constraints in "sc".
631 * "schedule" is a known correct schedule that is used to combine
632 * groups of statements if options->group_chains is set.
633 * In particular, statements that are executed consecutively in a sequence
634 * in this schedule and where all instances of the second depend on
635 * the instance of the first that is executed in the same iteration
636 * of outer band nodes are grouped together into a single statement.
637 * The schedule constraints are then mapped to these groups of statements
638 * and the resulting schedule is expanded again to refer to the original
639 * statements.
641 __isl_give isl_schedule *ppcg_compute_schedule(
642 __isl_take isl_schedule_constraints *sc,
643 __isl_keep isl_schedule *schedule, struct ppcg_options *options)
645 struct ppcg_grouping grouping = { sc };
646 isl_union_pw_multi_aff *contraction;
647 isl_union_map *umap;
648 isl_schedule *res, *expansion;
650 if (!options->group_chains)
651 return isl_schedule_constraints_compute_schedule(sc);
653 grouping.group_id = 0;
654 if (isl_schedule_foreach_schedule_node_top_down(schedule,
655 &detect_groups, &grouping) < 0)
656 goto error;
657 if (!grouping.contraction) {
658 ppcg_grouping_clear(&grouping);
659 return isl_schedule_constraints_compute_schedule(sc);
661 complete_grouping(&grouping);
662 contraction = isl_union_pw_multi_aff_copy(grouping.contraction);
663 umap = isl_union_map_from_union_pw_multi_aff(contraction);
665 sc = isl_schedule_constraints_apply(sc, umap);
667 res = isl_schedule_constraints_compute_schedule(sc);
669 contraction = isl_union_pw_multi_aff_copy(grouping.contraction);
670 expansion = isl_schedule_copy(grouping.schedule);
671 res = isl_schedule_expand(res, contraction, expansion);
673 ppcg_grouping_clear(&grouping);
674 return res;
675 error:
676 ppcg_grouping_clear(&grouping);
677 isl_schedule_constraints_free(sc);
678 return NULL;