Makefile.am: add gitversion.h to CLEANFILES
[ppcg.git] / grouping.c
blob30e6d5228323c7734d42a9febe8ca00bc84d9430
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/ctx.h>
10 #include <isl/id.h>
11 #include <isl/val.h>
12 #include <isl/space.h>
13 #include <isl/aff.h>
14 #include <isl/set.h>
15 #include <isl/map.h>
16 #include <isl/union_set.h>
17 #include <isl/union_map.h>
18 #include <isl/schedule.h>
19 #include <isl/schedule_node.h>
21 #include "ppcg.h"
23 /* Internal data structure for use during the detection of statements
24 * that can be grouped.
26 * "sc" contains the original schedule constraints (not a copy).
27 * The validity constraints of "sc" are adjusted based on the groups
28 * found so far.
29 * "dep" contains the intersection of the validity and the proximity
30 * constraints in "sc". It may be NULL if it has not been computed yet.
31 * "group_id" is the identifier for the next group that is extracted.
33 * "domain" is the set of statement instances that belong to any of the groups.
34 * "contraction" maps the elements of "domain" to the corresponding group
35 * instances.
36 * "schedule" schedules the statements in each group relatively to each other.
37 * These last three fields are NULL if no groups have been found so far.
39 struct ppcg_grouping {
40 isl_schedule_constraints *sc;
42 isl_union_map *dep;
43 int group_id;
45 isl_union_set *domain;
46 isl_union_pw_multi_aff *contraction;
47 isl_schedule *schedule;
50 /* Clear all memory allocated by "grouping".
52 static void ppcg_grouping_clear(struct ppcg_grouping *grouping)
54 isl_union_map_free(grouping->dep);
55 isl_union_set_free(grouping->domain);
56 isl_union_pw_multi_aff_free(grouping->contraction);
57 isl_schedule_free(grouping->schedule);
60 /* Compute the intersection of the proximity and validity dependences
61 * in grouping->sc and store the result in grouping->dep, unless
62 * this intersection has been computed before.
64 static isl_stat ppcg_grouping_compute_dep(struct ppcg_grouping *grouping)
66 isl_union_map *validity, *proximity;
68 if (grouping->dep)
69 return isl_stat_ok;
71 validity = isl_schedule_constraints_get_validity(grouping->sc);
72 proximity = isl_schedule_constraints_get_proximity(grouping->sc);
73 grouping->dep = isl_union_map_intersect(validity, proximity);
75 if (!grouping->dep)
76 return isl_stat_error;
78 return isl_stat_ok;
81 /* Information extracted from one or more consecutive leaves
82 * in the input schedule.
84 * "list" contains the sets of statement instances in the leaves,
85 * one element in the list for each original leaf.
86 * "domain" contains the union of the sets in "list".
87 * "prefix" contains the prefix schedule of these elements.
89 struct ppcg_grouping_leaf {
90 isl_union_set *domain;
91 isl_union_set_list *list;
92 isl_multi_union_pw_aff *prefix;
95 /* Free all memory allocated for "leaves".
97 static void ppcg_grouping_leaf_free(int n, struct ppcg_grouping_leaf leaves[n])
99 int i;
101 if (!leaves)
102 return;
104 for (i = 0; i < n; ++i) {
105 isl_union_set_free(leaves[i].domain);
106 isl_union_set_list_free(leaves[i].list);
107 isl_multi_union_pw_aff_free(leaves[i].prefix);
110 free(leaves);
113 /* Short-hand for retrieving the prefix schedule at "node"
114 * in the form of an isl_multi_union_pw_aff.
116 static __isl_give isl_multi_union_pw_aff *get_prefix(
117 __isl_keep isl_schedule_node *node)
119 return isl_schedule_node_get_prefix_schedule_multi_union_pw_aff(node);
122 /* Return an array of "n" elements with information extracted from
123 * the "n" children of "node" starting at "first", all of which
124 * are known to be filtered leaves.
126 struct ppcg_grouping_leaf *extract_leaves(__isl_keep isl_schedule_node *node,
127 int first, int n)
129 int i;
130 isl_ctx *ctx;
131 struct ppcg_grouping_leaf *leaves;
133 if (!node)
134 return NULL;
136 ctx = isl_schedule_node_get_ctx(node);
137 leaves = isl_calloc_array(ctx, struct ppcg_grouping_leaf, n);
138 if (!leaves)
139 return NULL;
141 for (i = 0; i < n; ++i) {
142 isl_schedule_node *child;
143 isl_union_set *domain;
145 child = isl_schedule_node_get_child(node, first + i);
146 child = isl_schedule_node_child(child, 0);
147 domain = isl_schedule_node_get_domain(child);
148 leaves[i].domain = isl_union_set_copy(domain);
149 leaves[i].list = isl_union_set_list_from_union_set(domain);
150 leaves[i].prefix = get_prefix(child);
151 isl_schedule_node_free(child);
154 return leaves;
157 /* Internal data structure used by merge_leaves.
159 * "src" and "dst" point to the two consecutive leaves that are
160 * under investigation for being merged.
161 * "merge" is initially set to 0 and is set to 1 as soon as
162 * it turns out that it is useful to merge the two leaves.
164 struct ppcg_merge_leaves_data {
165 int merge;
166 struct ppcg_grouping_leaf *src;
167 struct ppcg_grouping_leaf *dst;
170 /* Given a relation "map" between instances of two statements A and B,
171 * does it relate every instance of A (according to the domain of "src")
172 * to every instance of B (according to the domain of "dst")?
174 static isl_bool covers_src_and_dst(__isl_keep isl_map *map,
175 struct ppcg_grouping_leaf *src, struct ppcg_grouping_leaf *dst)
177 isl_space *space;
178 isl_set *set1, *set2;
179 isl_bool is_subset;
181 space = isl_space_domain(isl_map_get_space(map));
182 set1 = isl_union_set_extract_set(src->domain, space);
183 set2 = isl_map_domain(isl_map_copy(map));
184 is_subset = isl_set_is_subset(set1, set2);
185 isl_set_free(set1);
186 isl_set_free(set2);
187 if (is_subset < 0 || !is_subset)
188 return is_subset;
190 space = isl_space_range(isl_map_get_space(map));
191 set1 = isl_union_set_extract_set(dst->domain, space);
192 set2 = isl_map_range(isl_map_copy(map));
193 is_subset = isl_set_is_subset(set1, set2);
194 isl_set_free(set1);
195 isl_set_free(set2);
197 return is_subset;
200 /* Given a relation "map" between instances of two statements A and B,
201 * are pairs of related instances executed together in the input schedule?
202 * That is, is each pair of instances assigned the same value
203 * by the corresponding prefix schedules?
205 * In particular, select the subset of "map" that has pairs of elements
206 * with the same value for the prefix schedules and then check
207 * if "map" is still a subset of the result.
209 static isl_bool matches_prefix(__isl_keep isl_map *map,
210 struct ppcg_grouping_leaf *src, struct ppcg_grouping_leaf *dst)
212 isl_union_map *umap, *equal;
213 isl_multi_union_pw_aff *src_prefix, *dst_prefix, *prefix;
214 isl_bool is_subset;
216 src_prefix = isl_multi_union_pw_aff_copy(src->prefix);
217 dst_prefix = isl_multi_union_pw_aff_copy(dst->prefix);
218 prefix = isl_multi_union_pw_aff_union_add(src_prefix, dst_prefix);
220 umap = isl_union_map_from_map(isl_map_copy(map));
221 equal = isl_union_map_copy(umap);
222 equal = isl_union_map_eq_at_multi_union_pw_aff(equal, prefix);
224 is_subset = isl_union_map_is_subset(umap, equal);
226 isl_union_map_free(umap);
227 isl_union_map_free(equal);
229 return is_subset;
232 /* Given a set of validity and proximity schedule constraints "map"
233 * between statements in consecutive leaves in a valid schedule,
234 * should the two leaves be merged into one?
236 * In particular, the two are merged if the constraints form
237 * a bijection between every instance of the first statement and
238 * every instance of the second statement. Moreover, each
239 * pair of such dependent instances needs to be executed consecutively
240 * in the input schedule. That is, they need to be assigned
241 * the same value by their prefix schedules.
243 * What this means is that for each instance of the first statement
244 * there is exactly one instance of the second statement that
245 * is executed immediately after the instance of the first statement and
246 * that, moreover, both depends on this statement instance and
247 * should be brought as close as possible to this statement instance.
248 * In other words, it is both possible to execute the two instances
249 * together (according to the input schedule) and desirable to do so
250 * (according to the validity and proximity schedule constraints).
252 static isl_stat check_merge(__isl_take isl_map *map, void *user)
254 struct ppcg_merge_leaves_data *data = user;
255 isl_bool ok;
257 ok = covers_src_and_dst(map, data->src, data->dst);
258 if (ok >= 0 && ok)
259 ok = isl_map_is_bijective(map);
260 if (ok >= 0 && ok)
261 ok = matches_prefix(map, data->src, data->dst);
263 isl_map_free(map);
265 if (ok < 0)
266 return isl_stat_error;
267 if (!ok)
268 return isl_stat_ok;
270 data->merge = 1;
271 return isl_stat_error;
274 /* Merge the leaves at position "pos" and "pos + 1" in "leaves".
276 static isl_stat merge_pair(int n, struct ppcg_grouping_leaf leaves[n], int pos)
278 int i;
280 leaves[pos].domain = isl_union_set_union(leaves[pos].domain,
281 leaves[pos + 1].domain);
282 leaves[pos].list = isl_union_set_list_concat(leaves[pos].list,
283 leaves[pos + 1].list);
284 leaves[pos].prefix = isl_multi_union_pw_aff_union_add(
285 leaves[pos].prefix, leaves[pos + 1].prefix);
286 for (i = pos + 1; i + 1 < n; ++i)
287 leaves[i] = leaves[i + 1];
288 leaves[n - 1].domain = NULL;
289 leaves[n - 1].list = NULL;
290 leaves[n - 1].prefix = NULL;
292 if (!leaves[pos].domain || !leaves[pos].list || !leaves[pos].prefix)
293 return isl_stat_error;
295 return isl_stat_ok;
298 /* Merge pairs of consecutive leaves in "leaves" taking into account
299 * the intersection of validity and proximity schedule constraints "dep".
301 * If a leaf has been merged with the next leaf, then the combination
302 * is checked again for merging with the next leaf.
303 * That is, if the leaves are A, B and C, then B may not have been
304 * merged with C, but after merging A and B, it could still be useful
305 * to merge the combination AB with C.
307 * Two leaves A and B are merged if there are instances of at least
308 * one pair of statements, one statement in A and one B, such that
309 * the validity and proximity schedule constraints between them
310 * make them suitable for merging according to check_merge.
312 * Return the final number of leaves in the sequence, or -1 on error.
314 static int merge_leaves(int n, struct ppcg_grouping_leaf leaves[n],
315 __isl_keep isl_union_map *dep)
317 int i;
318 struct ppcg_merge_leaves_data data;
320 for (i = n - 1; i >= 0; --i) {
321 isl_union_map *dep_i;
322 isl_stat ok;
324 if (i + 1 >= n)
325 continue;
327 dep_i = isl_union_map_copy(dep);
328 dep_i = isl_union_map_intersect_domain(dep_i,
329 isl_union_set_copy(leaves[i].domain));
330 dep_i = isl_union_map_intersect_range(dep_i,
331 isl_union_set_copy(leaves[i + 1].domain));
332 data.merge = 0;
333 data.src = &leaves[i];
334 data.dst = &leaves[i + 1];
335 ok = isl_union_map_foreach_map(dep_i, &check_merge, &data);
336 isl_union_map_free(dep_i);
337 if (ok < 0 && !data.merge)
338 return -1;
339 if (!data.merge)
340 continue;
341 if (merge_pair(n, leaves, i) < 0)
342 return -1;
343 --n;
344 ++i;
347 return n;
350 /* Construct a schedule with "domain" as domain, that executes
351 * the elements of "list" in order (as a sequence).
353 static __isl_give isl_schedule *schedule_from_domain_and_list(
354 __isl_keep isl_union_set *domain, __isl_keep isl_union_set_list *list)
356 isl_schedule *schedule;
357 isl_schedule_node *node;
359 schedule = isl_schedule_from_domain(isl_union_set_copy(domain));
360 node = isl_schedule_get_root(schedule);
361 isl_schedule_free(schedule);
362 node = isl_schedule_node_child(node, 0);
363 list = isl_union_set_list_copy(list);
364 node = isl_schedule_node_insert_sequence(node, list);
365 schedule = isl_schedule_node_get_schedule(node);
366 isl_schedule_node_free(node);
368 return schedule;
371 /* Construct a unique identifier for a group in "grouping".
373 * The name is of the form G_n, with n the first value starting at
374 * grouping->group_id that does not result in an identifier
375 * that is already in use in the domain of the original schedule
376 * constraints.
378 static isl_id *construct_group_id(struct ppcg_grouping *grouping,
379 __isl_take isl_space *space)
381 isl_ctx *ctx;
382 isl_id *id;
383 isl_bool empty;
384 isl_union_set *domain;
386 if (!space)
387 return NULL;
389 ctx = isl_space_get_ctx(space);
390 domain = isl_schedule_constraints_get_domain(grouping->sc);
392 do {
393 char buffer[20];
394 isl_id *id;
395 isl_set *set;
397 snprintf(buffer, sizeof(buffer), "G_%d", grouping->group_id);
398 grouping->group_id++;
399 id = isl_id_alloc(ctx, buffer, NULL);
400 space = isl_space_set_tuple_id(space, isl_dim_set, id);
401 set = isl_union_set_extract_set(domain, isl_space_copy(space));
402 empty = isl_set_plain_is_empty(set);
403 isl_set_free(set);
404 } while (empty >= 0 && !empty);
406 if (empty < 0)
407 space = isl_space_free(space);
409 id = isl_space_get_tuple_id(space, isl_dim_set);
411 isl_space_free(space);
412 isl_union_set_free(domain);
414 return id;
417 /* Construct a contraction from "prefix" and "domain" for a new group
418 * in "grouping".
420 * The values of the prefix schedule "prefix" are used as instances
421 * of the new group. The identifier of the group is constructed
422 * in such a way that it does not conflict with those of earlier
423 * groups nor with statements in the domain of the original
424 * schedule constraints.
425 * The isl_multi_union_pw_aff "prefix" then simply needs to be
426 * converted to an isl_union_pw_multi_aff. However, this is not
427 * possible if "prefix" is zero-dimensional, so in this case,
428 * a contraction is constructed from "domain" instead.
430 static isl_union_pw_multi_aff *group_contraction_from_prefix_and_domain(
431 struct ppcg_grouping *grouping,
432 __isl_keep isl_multi_union_pw_aff *prefix,
433 __isl_keep isl_union_set *domain)
435 isl_id *id;
436 isl_space *space;
437 int dim;
439 space = isl_multi_union_pw_aff_get_space(prefix);
440 if (!space)
441 return NULL;
442 dim = isl_space_dim(space, isl_dim_set);
443 id = construct_group_id(grouping, space);
444 if (dim == 0) {
445 isl_multi_val *mv;
447 space = isl_multi_union_pw_aff_get_space(prefix);
448 space = isl_space_set_tuple_id(space, isl_dim_set, id);
449 mv = isl_multi_val_zero(space);
450 domain = isl_union_set_copy(domain);
451 return isl_union_pw_multi_aff_multi_val_on_domain(domain, mv);
453 prefix = isl_multi_union_pw_aff_copy(prefix);
454 prefix = isl_multi_union_pw_aff_set_tuple_id(prefix, isl_dim_out, id);
455 return isl_union_pw_multi_aff_from_multi_union_pw_aff(prefix);
458 /* Remove the validity schedule constraints from "sc" between
459 * statement instances that get contracted to the same group instance
460 * by the contraction described by "prefix" and "domain".
462 * The values of the prefix schedule "prefix" are used as instances
463 * of the new group. This means that validity schedule constraints
464 * between instances with the same prefix schedule value need to be removed.
465 * If "prefix" is zero-dimensional, then it does not contain any
466 * information about the domain. Instead, those schedule constraints
467 * are removed that connect pairs of instances in "domain".
469 static __isl_give isl_schedule_constraints *remove_group_validity(
470 __isl_take isl_schedule_constraints *sc,
471 __isl_keep isl_multi_union_pw_aff *prefix,
472 __isl_keep isl_union_set *domain)
474 int n;
475 isl_union_map *validity, *joined;
477 validity = isl_schedule_constraints_get_validity(sc);
478 joined = isl_union_map_copy(validity);
479 n = isl_multi_union_pw_aff_dim(prefix, isl_dim_out);
480 if (n == 0) {
481 joined = isl_union_map_intersect_domain(joined,
482 isl_union_set_copy(domain));
483 joined = isl_union_map_intersect_range(joined,
484 isl_union_set_copy(domain));
485 } else {
486 joined = isl_union_map_eq_at_multi_union_pw_aff(joined,
487 isl_multi_union_pw_aff_copy(prefix));
489 validity = isl_union_map_subtract(validity, joined);
490 sc = isl_schedule_constraints_set_validity(sc, validity);
491 return sc;
494 /* Extend "grouping" with groups corresponding to merged
495 * leaves in the list of potentially merged leaves "leaves".
497 * The "list" field of each element in "leaves" contains a list
498 * of the instances sets of the original leaves that have been
499 * merged into this element. If at least two of the original leaves
500 * have been merged into a given element, then add the corresponding
501 * group to "grouping" and remove validity schedule constraints
502 * between statement instances that get mapped to the same group instance.
503 * In particular, the domain is extended with the statement instances
504 * of the merged leaves, the contraction is extended with a mapping
505 * of these statement instances to instances of a new group and
506 * the schedule is extended with a schedule that executes
507 * the statement instances according to the order of the leaves
508 * in which they appear.
509 * Since the instances of the groups should already be scheduled apart
510 * in the schedule into which this schedule will be plugged in,
511 * the schedules of the individual groups are combined independently
512 * of each other (as a set).
514 static isl_stat add_groups(struct ppcg_grouping *grouping,
515 int n, struct ppcg_grouping_leaf leaves[n])
517 int i;
519 for (i = 0; i < n; ++i) {
520 int n_leaf;
521 isl_schedule *schedule;
522 isl_union_set *domain;
523 isl_union_pw_multi_aff *upma;
525 n_leaf = isl_union_set_list_n_union_set(leaves[i].list);
526 if (n_leaf < 0)
527 return isl_stat_error;
528 if (n_leaf <= 1)
529 continue;
530 schedule = schedule_from_domain_and_list(leaves[i].domain,
531 leaves[i].list);
532 upma = group_contraction_from_prefix_and_domain(grouping,
533 leaves[i].prefix, leaves[i].domain);
534 grouping->sc = remove_group_validity(grouping->sc,
535 leaves[i].prefix, leaves[i].domain);
537 domain = isl_union_set_copy(leaves[i].domain);
538 if (grouping->domain) {
539 domain = isl_union_set_union(domain, grouping->domain);
540 upma = isl_union_pw_multi_aff_union_add(upma,
541 grouping->contraction);
542 schedule = isl_schedule_set(schedule,
543 grouping->schedule);
545 grouping->domain = domain;
546 grouping->contraction = upma;
547 grouping->schedule = schedule;
549 if (!grouping->domain || !grouping->contraction ||
550 !grouping->schedule)
551 return isl_stat_error;
554 return isl_stat_ok;
557 /* Look for any pairs of consecutive leaves among the "n" children of "node"
558 * starting at "first" that should be merged together.
559 * Store the results in "grouping".
561 * First make sure the intersection of validity and proximity
562 * schedule constraints is available and extract the required
563 * information from the "n" leaves.
564 * Then try and merge consecutive leaves based on the validity
565 * and proximity constraints.
566 * If any pairs were successfully merged, then add groups
567 * corresponding to the merged leaves to "grouping".
569 static isl_stat group_subsequence(__isl_keep isl_schedule_node *node,
570 int first, int n, struct ppcg_grouping *grouping)
572 int n_merge;
573 struct ppcg_grouping_leaf *leaves;
575 if (ppcg_grouping_compute_dep(grouping) < 0)
576 return isl_stat_error;
578 leaves = extract_leaves(node, first, n);
579 if (!leaves)
580 return isl_stat_error;
582 n_merge = merge_leaves(n, leaves, grouping->dep);
583 if (n_merge >= 0 && n_merge < n &&
584 add_groups(grouping, n_merge, leaves) < 0)
585 return isl_stat_error;
587 ppcg_grouping_leaf_free(n, leaves);
589 return isl_stat_ok;
592 /* If "node" is a sequence, then check if it has any consecutive
593 * leaves that should be merged together and store the results
594 * in "grouping".
596 * In particular, call group_subsequence on each consecutive
597 * sequence of (filtered) leaves among the children of "node".
599 static isl_bool detect_groups(__isl_keep isl_schedule_node *node, void *user)
601 int i, n, first;
602 struct ppcg_grouping *grouping = user;
604 if (isl_schedule_node_get_type(node) != isl_schedule_node_sequence)
605 return isl_bool_true;
607 n = isl_schedule_node_n_children(node);
608 if (n < 0)
609 return isl_bool_error;
611 first = -1;
612 for (i = 0; i < n; ++i) {
613 isl_schedule_node *child;
614 enum isl_schedule_node_type type;
616 child = isl_schedule_node_get_child(node, i);
617 child = isl_schedule_node_child(child, 0);
618 type = isl_schedule_node_get_type(child);
619 isl_schedule_node_free(child);
621 if (first >= 0 && type != isl_schedule_node_leaf) {
622 if (group_subsequence(node, first, i - first,
623 grouping) < 0)
624 return isl_bool_error;
625 first = -1;
627 if (first < 0 && type == isl_schedule_node_leaf)
628 first = i;
630 if (first >= 0) {
631 if (group_subsequence(node, first, n - first, grouping) < 0)
632 return isl_bool_error;
635 return isl_bool_true;
638 /* Complete "grouping" to cover all statement instances in the domain
639 * of grouping->sc.
641 * In particular, grouping->domain is set to the full set of statement
642 * instances; group->contraction is extended with an identity
643 * contraction on the additional instances and group->schedule
644 * is extended with an independent schedule on those additional instances.
645 * In the extension of group->contraction, the additional instances
646 * are split into those belong to different statements and those
647 * that belong to some of the same statements. The first group
648 * is replaced by its universe in order to simplify the contraction extension.
650 static void complete_grouping(struct ppcg_grouping *grouping)
652 isl_union_set *domain, *left, *overlap;
653 isl_union_pw_multi_aff *upma;
654 isl_schedule *schedule;
656 domain = isl_schedule_constraints_get_domain(grouping->sc);
657 left = isl_union_set_subtract(isl_union_set_copy(domain),
658 isl_union_set_copy(grouping->domain));
659 schedule = isl_schedule_from_domain(isl_union_set_copy(left));
660 schedule = isl_schedule_set(schedule, grouping->schedule);
661 grouping->schedule = schedule;
663 overlap = isl_union_set_universe(grouping->domain);
664 grouping->domain = domain;
665 overlap = isl_union_set_intersect(isl_union_set_copy(left), overlap);
666 left = isl_union_set_subtract(left, isl_union_set_copy(overlap));
667 left = isl_union_set_universe(left);
668 left = isl_union_set_union(left, overlap);
669 upma = isl_union_set_identity_union_pw_multi_aff(left);
670 upma = isl_union_pw_multi_aff_union_add(upma, grouping->contraction);
671 grouping->contraction = upma;
674 /* Compute a schedule on the domain of "sc" that respects the schedule
675 * constraints in "sc".
677 * "schedule" is a known correct schedule that is used to combine
678 * groups of statements if options->group_chains is set.
679 * In particular, statements that are executed consecutively in a sequence
680 * in this schedule and where all instances of the second depend on
681 * the instance of the first that is executed in the same iteration
682 * of outer band nodes are grouped together into a single statement.
683 * The schedule constraints are then mapped to these groups of statements
684 * and the resulting schedule is expanded again to refer to the original
685 * statements.
687 __isl_give isl_schedule *ppcg_compute_schedule(
688 __isl_take isl_schedule_constraints *sc,
689 __isl_keep isl_schedule *schedule, struct ppcg_options *options)
691 struct ppcg_grouping grouping = { sc };
692 isl_union_pw_multi_aff *contraction;
693 isl_union_map *umap;
694 isl_schedule *res, *expansion;
696 if (!options->group_chains)
697 return isl_schedule_constraints_compute_schedule(sc);
699 grouping.group_id = 0;
700 if (isl_schedule_foreach_schedule_node_top_down(schedule,
701 &detect_groups, &grouping) < 0)
702 goto error;
703 if (!grouping.contraction) {
704 ppcg_grouping_clear(&grouping);
705 return isl_schedule_constraints_compute_schedule(grouping.sc);
707 complete_grouping(&grouping);
708 contraction = isl_union_pw_multi_aff_copy(grouping.contraction);
709 umap = isl_union_map_from_union_pw_multi_aff(contraction);
711 sc = isl_schedule_constraints_apply(grouping.sc, umap);
713 res = isl_schedule_constraints_compute_schedule(sc);
715 contraction = isl_union_pw_multi_aff_copy(grouping.contraction);
716 expansion = isl_schedule_copy(grouping.schedule);
717 res = isl_schedule_expand(res, contraction, expansion);
719 ppcg_grouping_clear(&grouping);
720 return res;
721 error:
722 ppcg_grouping_clear(&grouping);
723 isl_schedule_constraints_free(sc);
724 return NULL;