isl_union_access_info_compute_flow: handle coscheduled must-sources
[isl.git] / isl_flow.c
blobb66c514815ebfc7f38f109eaca304e47de232155
1 /*
2 * Copyright 2005-2007 Universiteit Leiden
3 * Copyright 2008-2009 Katholieke Universiteit Leuven
4 * Copyright 2010 INRIA Saclay
5 * Copyright 2012 Universiteit Leiden
6 * Copyright 2014 Ecole Normale Superieure
8 * Use of this software is governed by the MIT license
10 * Written by Sven Verdoolaege, Leiden Institute of Advanced Computer Science,
11 * Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands
12 * and K.U.Leuven, Departement Computerwetenschappen, Celestijnenlaan 200A,
13 * B-3001 Leuven, Belgium
14 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
15 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
16 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
19 #include <isl/set.h>
20 #include <isl/map.h>
21 #include <isl/union_set.h>
22 #include <isl/union_map.h>
23 #include <isl/flow.h>
24 #include <isl/schedule_node.h>
25 #include <isl_sort.h>
26 #include <isl/stream.h>
28 enum isl_restriction_type {
29 isl_restriction_type_empty,
30 isl_restriction_type_none,
31 isl_restriction_type_input,
32 isl_restriction_type_output
35 struct isl_restriction {
36 enum isl_restriction_type type;
38 isl_set *source;
39 isl_set *sink;
42 /* Create a restriction of the given type.
44 static __isl_give isl_restriction *isl_restriction_alloc(
45 __isl_take isl_map *source_map, enum isl_restriction_type type)
47 isl_ctx *ctx;
48 isl_restriction *restr;
50 if (!source_map)
51 return NULL;
53 ctx = isl_map_get_ctx(source_map);
54 restr = isl_calloc_type(ctx, struct isl_restriction);
55 if (!restr)
56 goto error;
58 restr->type = type;
60 isl_map_free(source_map);
61 return restr;
62 error:
63 isl_map_free(source_map);
64 return NULL;
67 /* Create a restriction that doesn't restrict anything.
69 __isl_give isl_restriction *isl_restriction_none(__isl_take isl_map *source_map)
71 return isl_restriction_alloc(source_map, isl_restriction_type_none);
74 /* Create a restriction that removes everything.
76 __isl_give isl_restriction *isl_restriction_empty(
77 __isl_take isl_map *source_map)
79 return isl_restriction_alloc(source_map, isl_restriction_type_empty);
82 /* Create a restriction on the input of the maximization problem
83 * based on the given source and sink restrictions.
85 __isl_give isl_restriction *isl_restriction_input(
86 __isl_take isl_set *source_restr, __isl_take isl_set *sink_restr)
88 isl_ctx *ctx;
89 isl_restriction *restr;
91 if (!source_restr || !sink_restr)
92 goto error;
94 ctx = isl_set_get_ctx(source_restr);
95 restr = isl_calloc_type(ctx, struct isl_restriction);
96 if (!restr)
97 goto error;
99 restr->type = isl_restriction_type_input;
100 restr->source = source_restr;
101 restr->sink = sink_restr;
103 return restr;
104 error:
105 isl_set_free(source_restr);
106 isl_set_free(sink_restr);
107 return NULL;
110 /* Create a restriction on the output of the maximization problem
111 * based on the given source restriction.
113 __isl_give isl_restriction *isl_restriction_output(
114 __isl_take isl_set *source_restr)
116 isl_ctx *ctx;
117 isl_restriction *restr;
119 if (!source_restr)
120 return NULL;
122 ctx = isl_set_get_ctx(source_restr);
123 restr = isl_calloc_type(ctx, struct isl_restriction);
124 if (!restr)
125 goto error;
127 restr->type = isl_restriction_type_output;
128 restr->source = source_restr;
130 return restr;
131 error:
132 isl_set_free(source_restr);
133 return NULL;
136 __isl_null isl_restriction *isl_restriction_free(
137 __isl_take isl_restriction *restr)
139 if (!restr)
140 return NULL;
142 isl_set_free(restr->source);
143 isl_set_free(restr->sink);
144 free(restr);
145 return NULL;
148 isl_ctx *isl_restriction_get_ctx(__isl_keep isl_restriction *restr)
150 return restr ? isl_set_get_ctx(restr->source) : NULL;
153 /* A private structure to keep track of a mapping together with
154 * a user-specified identifier and a boolean indicating whether
155 * the map represents a must or may access/dependence.
157 struct isl_labeled_map {
158 struct isl_map *map;
159 void *data;
160 int must;
163 typedef int (*isl_access_coscheduled)(void *first, void *second);
165 /* A structure containing the input for dependence analysis:
166 * - a sink
167 * - n_must + n_may (<= max_source) sources
168 * - a function for determining the relative order of sources and sink
169 * - an optional function "coscheduled" for determining whether sources
170 * may be coscheduled. If "coscheduled" is NULL, then the sources
171 * are assumed not to be coscheduled.
172 * The must sources are placed before the may sources.
174 * domain_map is an auxiliary map that maps the sink access relation
175 * to the domain of this access relation.
176 * This field is only needed when restrict_fn is set and
177 * the field itself is set by isl_access_info_compute_flow.
179 * restrict_fn is a callback that (if not NULL) will be called
180 * right before any lexicographical maximization.
182 struct isl_access_info {
183 isl_map *domain_map;
184 struct isl_labeled_map sink;
185 isl_access_level_before level_before;
186 isl_access_coscheduled coscheduled;
188 isl_access_restrict restrict_fn;
189 void *restrict_user;
191 int max_source;
192 int n_must;
193 int n_may;
194 struct isl_labeled_map source[1];
197 /* A structure containing the output of dependence analysis:
198 * - n_source dependences
199 * - a wrapped subset of the sink for which definitely no source could be found
200 * - a wrapped subset of the sink for which possibly no source could be found
202 struct isl_flow {
203 isl_set *must_no_source;
204 isl_set *may_no_source;
205 int n_source;
206 struct isl_labeled_map *dep;
209 /* Construct an isl_access_info structure and fill it up with
210 * the given data. The number of sources is set to 0.
212 __isl_give isl_access_info *isl_access_info_alloc(__isl_take isl_map *sink,
213 void *sink_user, isl_access_level_before fn, int max_source)
215 isl_ctx *ctx;
216 struct isl_access_info *acc;
218 if (!sink)
219 return NULL;
221 ctx = isl_map_get_ctx(sink);
222 isl_assert(ctx, max_source >= 0, goto error);
224 acc = isl_calloc(ctx, struct isl_access_info,
225 sizeof(struct isl_access_info) +
226 (max_source - 1) * sizeof(struct isl_labeled_map));
227 if (!acc)
228 goto error;
230 acc->sink.map = sink;
231 acc->sink.data = sink_user;
232 acc->level_before = fn;
233 acc->max_source = max_source;
234 acc->n_must = 0;
235 acc->n_may = 0;
237 return acc;
238 error:
239 isl_map_free(sink);
240 return NULL;
243 /* Free the given isl_access_info structure.
245 __isl_null isl_access_info *isl_access_info_free(
246 __isl_take isl_access_info *acc)
248 int i;
250 if (!acc)
251 return NULL;
252 isl_map_free(acc->domain_map);
253 isl_map_free(acc->sink.map);
254 for (i = 0; i < acc->n_must + acc->n_may; ++i)
255 isl_map_free(acc->source[i].map);
256 free(acc);
257 return NULL;
260 isl_ctx *isl_access_info_get_ctx(__isl_keep isl_access_info *acc)
262 return acc ? isl_map_get_ctx(acc->sink.map) : NULL;
265 __isl_give isl_access_info *isl_access_info_set_restrict(
266 __isl_take isl_access_info *acc, isl_access_restrict fn, void *user)
268 if (!acc)
269 return NULL;
270 acc->restrict_fn = fn;
271 acc->restrict_user = user;
272 return acc;
275 /* Add another source to an isl_access_info structure, making
276 * sure the "must" sources are placed before the "may" sources.
277 * This function may be called at most max_source times on a
278 * given isl_access_info structure, with max_source as specified
279 * in the call to isl_access_info_alloc that constructed the structure.
281 __isl_give isl_access_info *isl_access_info_add_source(
282 __isl_take isl_access_info *acc, __isl_take isl_map *source,
283 int must, void *source_user)
285 isl_ctx *ctx;
287 if (!acc)
288 goto error;
289 ctx = isl_map_get_ctx(acc->sink.map);
290 isl_assert(ctx, acc->n_must + acc->n_may < acc->max_source, goto error);
292 if (must) {
293 if (acc->n_may)
294 acc->source[acc->n_must + acc->n_may] =
295 acc->source[acc->n_must];
296 acc->source[acc->n_must].map = source;
297 acc->source[acc->n_must].data = source_user;
298 acc->source[acc->n_must].must = 1;
299 acc->n_must++;
300 } else {
301 acc->source[acc->n_must + acc->n_may].map = source;
302 acc->source[acc->n_must + acc->n_may].data = source_user;
303 acc->source[acc->n_must + acc->n_may].must = 0;
304 acc->n_may++;
307 return acc;
308 error:
309 isl_map_free(source);
310 isl_access_info_free(acc);
311 return NULL;
314 /* Return -n, 0 or n (with n a positive value), depending on whether
315 * the source access identified by p1 should be sorted before, together
316 * or after that identified by p2.
318 * If p1 appears before p2, then it should be sorted first.
319 * For more generic initial schedules, it is possible that neither
320 * p1 nor p2 appears before the other, or at least not in any obvious way.
321 * We therefore also check if p2 appears before p1, in which case p2
322 * should be sorted first.
323 * If not, we try to order the two statements based on the description
324 * of the iteration domains. This results in an arbitrary, but fairly
325 * stable ordering.
327 static int access_sort_cmp(const void *p1, const void *p2, void *user)
329 isl_access_info *acc = user;
330 const struct isl_labeled_map *i1, *i2;
331 int level1, level2;
332 uint32_t h1, h2;
333 i1 = (const struct isl_labeled_map *) p1;
334 i2 = (const struct isl_labeled_map *) p2;
336 level1 = acc->level_before(i1->data, i2->data);
337 if (level1 % 2)
338 return -1;
340 level2 = acc->level_before(i2->data, i1->data);
341 if (level2 % 2)
342 return 1;
344 h1 = isl_map_get_hash(i1->map);
345 h2 = isl_map_get_hash(i2->map);
346 return h1 > h2 ? 1 : h1 < h2 ? -1 : 0;
349 /* Sort the must source accesses in their textual order.
351 static __isl_give isl_access_info *isl_access_info_sort_sources(
352 __isl_take isl_access_info *acc)
354 if (!acc)
355 return NULL;
356 if (acc->n_must <= 1)
357 return acc;
359 if (isl_sort(acc->source, acc->n_must, sizeof(struct isl_labeled_map),
360 access_sort_cmp, acc) < 0)
361 return isl_access_info_free(acc);
363 return acc;
366 /* Align the parameters of the two spaces if needed and then call
367 * isl_space_join.
369 static __isl_give isl_space *space_align_and_join(__isl_take isl_space *left,
370 __isl_take isl_space *right)
372 isl_bool equal_params;
374 equal_params = isl_space_has_equal_params(left, right);
375 if (equal_params < 0)
376 goto error;
377 if (equal_params)
378 return isl_space_join(left, right);
380 left = isl_space_align_params(left, isl_space_copy(right));
381 right = isl_space_align_params(right, isl_space_copy(left));
382 return isl_space_join(left, right);
383 error:
384 isl_space_free(left);
385 isl_space_free(right);
386 return NULL;
389 /* Initialize an empty isl_flow structure corresponding to a given
390 * isl_access_info structure.
391 * For each must access, two dependences are created (initialized
392 * to the empty relation), one for the resulting must dependences
393 * and one for the resulting may dependences. May accesses can
394 * only lead to may dependences, so only one dependence is created
395 * for each of them.
396 * This function is private as isl_flow structures are only supposed
397 * to be created by isl_access_info_compute_flow.
399 static __isl_give isl_flow *isl_flow_alloc(__isl_keep isl_access_info *acc)
401 int i, n;
402 struct isl_ctx *ctx;
403 struct isl_flow *dep;
405 if (!acc)
406 return NULL;
408 ctx = isl_map_get_ctx(acc->sink.map);
409 dep = isl_calloc_type(ctx, struct isl_flow);
410 if (!dep)
411 return NULL;
413 n = 2 * acc->n_must + acc->n_may;
414 dep->dep = isl_calloc_array(ctx, struct isl_labeled_map, n);
415 if (n && !dep->dep)
416 goto error;
418 dep->n_source = n;
419 for (i = 0; i < acc->n_must; ++i) {
420 isl_space *dim;
421 dim = space_align_and_join(
422 isl_map_get_space(acc->source[i].map),
423 isl_space_reverse(isl_map_get_space(acc->sink.map)));
424 dep->dep[2 * i].map = isl_map_empty(dim);
425 dep->dep[2 * i + 1].map = isl_map_copy(dep->dep[2 * i].map);
426 dep->dep[2 * i].data = acc->source[i].data;
427 dep->dep[2 * i + 1].data = acc->source[i].data;
428 dep->dep[2 * i].must = 1;
429 dep->dep[2 * i + 1].must = 0;
430 if (!dep->dep[2 * i].map || !dep->dep[2 * i + 1].map)
431 goto error;
433 for (i = acc->n_must; i < acc->n_must + acc->n_may; ++i) {
434 isl_space *dim;
435 dim = space_align_and_join(
436 isl_map_get_space(acc->source[i].map),
437 isl_space_reverse(isl_map_get_space(acc->sink.map)));
438 dep->dep[acc->n_must + i].map = isl_map_empty(dim);
439 dep->dep[acc->n_must + i].data = acc->source[i].data;
440 dep->dep[acc->n_must + i].must = 0;
441 if (!dep->dep[acc->n_must + i].map)
442 goto error;
445 return dep;
446 error:
447 isl_flow_free(dep);
448 return NULL;
451 /* Iterate over all sources and for each resulting flow dependence
452 * that is not empty, call the user specfied function.
453 * The second argument in this function call identifies the source,
454 * while the third argument correspond to the final argument of
455 * the isl_flow_foreach call.
457 isl_stat isl_flow_foreach(__isl_keep isl_flow *deps,
458 isl_stat (*fn)(__isl_take isl_map *dep, int must, void *dep_user,
459 void *user),
460 void *user)
462 int i;
464 if (!deps)
465 return isl_stat_error;
467 for (i = 0; i < deps->n_source; ++i) {
468 if (isl_map_plain_is_empty(deps->dep[i].map))
469 continue;
470 if (fn(isl_map_copy(deps->dep[i].map), deps->dep[i].must,
471 deps->dep[i].data, user) < 0)
472 return isl_stat_error;
475 return isl_stat_ok;
478 /* Return a copy of the subset of the sink for which no source could be found.
480 __isl_give isl_map *isl_flow_get_no_source(__isl_keep isl_flow *deps, int must)
482 if (!deps)
483 return NULL;
485 if (must)
486 return isl_set_unwrap(isl_set_copy(deps->must_no_source));
487 else
488 return isl_set_unwrap(isl_set_copy(deps->may_no_source));
491 void isl_flow_free(__isl_take isl_flow *deps)
493 int i;
495 if (!deps)
496 return;
497 isl_set_free(deps->must_no_source);
498 isl_set_free(deps->may_no_source);
499 if (deps->dep) {
500 for (i = 0; i < deps->n_source; ++i)
501 isl_map_free(deps->dep[i].map);
502 free(deps->dep);
504 free(deps);
507 isl_ctx *isl_flow_get_ctx(__isl_keep isl_flow *deps)
509 return deps ? isl_set_get_ctx(deps->must_no_source) : NULL;
512 /* Return a map that enforces that the domain iteration occurs after
513 * the range iteration at the given level.
514 * If level is odd, then the domain iteration should occur after
515 * the target iteration in their shared level/2 outermost loops.
516 * In this case we simply need to enforce that these outermost
517 * loop iterations are the same.
518 * If level is even, then the loop iterator of the domain should
519 * be greater than the loop iterator of the range at the last
520 * of the level/2 shared loops, i.e., loop level/2 - 1.
522 static __isl_give isl_map *after_at_level(__isl_take isl_space *dim, int level)
524 struct isl_basic_map *bmap;
526 if (level % 2)
527 bmap = isl_basic_map_equal(dim, level/2);
528 else
529 bmap = isl_basic_map_more_at(dim, level/2 - 1);
531 return isl_map_from_basic_map(bmap);
534 /* Compute the partial lexicographic maximum of "dep" on domain "sink",
535 * but first check if the user has set acc->restrict_fn and if so
536 * update either the input or the output of the maximization problem
537 * with respect to the resulting restriction.
539 * Since the user expects a mapping from sink iterations to source iterations,
540 * whereas the domain of "dep" is a wrapped map, mapping sink iterations
541 * to accessed array elements, we first need to project out the accessed
542 * sink array elements by applying acc->domain_map.
543 * Similarly, the sink restriction specified by the user needs to be
544 * converted back to the wrapped map.
546 static __isl_give isl_map *restricted_partial_lexmax(
547 __isl_keep isl_access_info *acc, __isl_take isl_map *dep,
548 int source, __isl_take isl_set *sink, __isl_give isl_set **empty)
550 isl_map *source_map;
551 isl_restriction *restr;
552 isl_set *sink_domain;
553 isl_set *sink_restr;
554 isl_map *res;
556 if (!acc->restrict_fn)
557 return isl_map_partial_lexmax(dep, sink, empty);
559 source_map = isl_map_copy(dep);
560 source_map = isl_map_apply_domain(source_map,
561 isl_map_copy(acc->domain_map));
562 sink_domain = isl_set_copy(sink);
563 sink_domain = isl_set_apply(sink_domain, isl_map_copy(acc->domain_map));
564 restr = acc->restrict_fn(source_map, sink_domain,
565 acc->source[source].data, acc->restrict_user);
566 isl_set_free(sink_domain);
567 isl_map_free(source_map);
569 if (!restr)
570 goto error;
571 if (restr->type == isl_restriction_type_input) {
572 dep = isl_map_intersect_range(dep, isl_set_copy(restr->source));
573 sink_restr = isl_set_copy(restr->sink);
574 sink_restr = isl_set_apply(sink_restr,
575 isl_map_reverse(isl_map_copy(acc->domain_map)));
576 sink = isl_set_intersect(sink, sink_restr);
577 } else if (restr->type == isl_restriction_type_empty) {
578 isl_space *space = isl_map_get_space(dep);
579 isl_map_free(dep);
580 dep = isl_map_empty(space);
583 res = isl_map_partial_lexmax(dep, sink, empty);
585 if (restr->type == isl_restriction_type_output)
586 res = isl_map_intersect_range(res, isl_set_copy(restr->source));
588 isl_restriction_free(restr);
589 return res;
590 error:
591 isl_map_free(dep);
592 isl_set_free(sink);
593 *empty = NULL;
594 return NULL;
597 /* Compute the last iteration of must source j that precedes the sink
598 * at the given level for sink iterations in set_C.
599 * The subset of set_C for which no such iteration can be found is returned
600 * in *empty.
602 static struct isl_map *last_source(struct isl_access_info *acc,
603 struct isl_set *set_C,
604 int j, int level, struct isl_set **empty)
606 struct isl_map *read_map;
607 struct isl_map *write_map;
608 struct isl_map *dep_map;
609 struct isl_map *after;
610 struct isl_map *result;
612 read_map = isl_map_copy(acc->sink.map);
613 write_map = isl_map_copy(acc->source[j].map);
614 write_map = isl_map_reverse(write_map);
615 dep_map = isl_map_apply_range(read_map, write_map);
616 after = after_at_level(isl_map_get_space(dep_map), level);
617 dep_map = isl_map_intersect(dep_map, after);
618 result = restricted_partial_lexmax(acc, dep_map, j, set_C, empty);
619 result = isl_map_reverse(result);
621 return result;
624 /* For a given mapping between iterations of must source j and iterations
625 * of the sink, compute the last iteration of must source k preceding
626 * the sink at level before_level for any of the sink iterations,
627 * but following the corresponding iteration of must source j at level
628 * after_level.
630 static struct isl_map *last_later_source(struct isl_access_info *acc,
631 struct isl_map *old_map,
632 int j, int before_level,
633 int k, int after_level,
634 struct isl_set **empty)
636 isl_space *dim;
637 struct isl_set *set_C;
638 struct isl_map *read_map;
639 struct isl_map *write_map;
640 struct isl_map *dep_map;
641 struct isl_map *after_write;
642 struct isl_map *before_read;
643 struct isl_map *result;
645 set_C = isl_map_range(isl_map_copy(old_map));
646 read_map = isl_map_copy(acc->sink.map);
647 write_map = isl_map_copy(acc->source[k].map);
649 write_map = isl_map_reverse(write_map);
650 dep_map = isl_map_apply_range(read_map, write_map);
651 dim = space_align_and_join(isl_map_get_space(acc->source[k].map),
652 isl_space_reverse(isl_map_get_space(acc->source[j].map)));
653 after_write = after_at_level(dim, after_level);
654 after_write = isl_map_apply_range(after_write, old_map);
655 after_write = isl_map_reverse(after_write);
656 dep_map = isl_map_intersect(dep_map, after_write);
657 before_read = after_at_level(isl_map_get_space(dep_map), before_level);
658 dep_map = isl_map_intersect(dep_map, before_read);
659 result = restricted_partial_lexmax(acc, dep_map, k, set_C, empty);
660 result = isl_map_reverse(result);
662 return result;
665 /* Given a shared_level between two accesses, return 1 if the
666 * the first can precede the second at the requested target_level.
667 * If the target level is odd, i.e., refers to a statement level
668 * dimension, then first needs to precede second at the requested
669 * level, i.e., shared_level must be equal to target_level.
670 * If the target level is odd, then the two loops should share
671 * at least the requested number of outer loops.
673 static int can_precede_at_level(int shared_level, int target_level)
675 if (shared_level < target_level)
676 return 0;
677 if ((target_level % 2) && shared_level > target_level)
678 return 0;
679 return 1;
682 /* Given a possible flow dependence temp_rel[j] between source j and the sink
683 * at level sink_level, remove those elements for which
684 * there is an iteration of another source k < j that is closer to the sink.
685 * The flow dependences temp_rel[k] are updated with the improved sources.
686 * Any improved source needs to precede the sink at the same level
687 * and needs to follow source j at the same or a deeper level.
688 * The lower this level, the later the execution date of source k.
689 * We therefore consider lower levels first.
691 * If temp_rel[j] is empty, then there can be no improvement and
692 * we return immediately.
694 static int intermediate_sources(__isl_keep isl_access_info *acc,
695 struct isl_map **temp_rel, int j, int sink_level)
697 int k, level;
698 int depth = 2 * isl_map_dim(acc->source[j].map, isl_dim_in) + 1;
700 if (isl_map_plain_is_empty(temp_rel[j]))
701 return 0;
703 for (k = j - 1; k >= 0; --k) {
704 int plevel, plevel2;
705 plevel = acc->level_before(acc->source[k].data, acc->sink.data);
706 if (!can_precede_at_level(plevel, sink_level))
707 continue;
709 plevel2 = acc->level_before(acc->source[j].data,
710 acc->source[k].data);
712 for (level = sink_level; level <= depth; ++level) {
713 struct isl_map *T;
714 struct isl_set *trest;
715 struct isl_map *copy;
717 if (!can_precede_at_level(plevel2, level))
718 continue;
720 copy = isl_map_copy(temp_rel[j]);
721 T = last_later_source(acc, copy, j, sink_level, k,
722 level, &trest);
723 if (isl_map_plain_is_empty(T)) {
724 isl_set_free(trest);
725 isl_map_free(T);
726 continue;
728 temp_rel[j] = isl_map_intersect_range(temp_rel[j], trest);
729 temp_rel[k] = isl_map_union_disjoint(temp_rel[k], T);
733 return 0;
736 /* Compute all iterations of may source j that precedes the sink at the given
737 * level for sink iterations in set_C.
739 static __isl_give isl_map *all_sources(__isl_keep isl_access_info *acc,
740 __isl_take isl_set *set_C, int j, int level)
742 isl_map *read_map;
743 isl_map *write_map;
744 isl_map *dep_map;
745 isl_map *after;
747 read_map = isl_map_copy(acc->sink.map);
748 read_map = isl_map_intersect_domain(read_map, set_C);
749 write_map = isl_map_copy(acc->source[acc->n_must + j].map);
750 write_map = isl_map_reverse(write_map);
751 dep_map = isl_map_apply_range(read_map, write_map);
752 after = after_at_level(isl_map_get_space(dep_map), level);
753 dep_map = isl_map_intersect(dep_map, after);
755 return isl_map_reverse(dep_map);
758 /* For a given mapping between iterations of must source k and iterations
759 * of the sink, compute all iterations of may source j preceding
760 * the sink at level before_level for any of the sink iterations,
761 * but following the corresponding iteration of must source k at level
762 * after_level.
764 static __isl_give isl_map *all_later_sources(__isl_keep isl_access_info *acc,
765 __isl_take isl_map *old_map,
766 int j, int before_level, int k, int after_level)
768 isl_space *dim;
769 isl_set *set_C;
770 isl_map *read_map;
771 isl_map *write_map;
772 isl_map *dep_map;
773 isl_map *after_write;
774 isl_map *before_read;
776 set_C = isl_map_range(isl_map_copy(old_map));
777 read_map = isl_map_copy(acc->sink.map);
778 read_map = isl_map_intersect_domain(read_map, set_C);
779 write_map = isl_map_copy(acc->source[acc->n_must + j].map);
781 write_map = isl_map_reverse(write_map);
782 dep_map = isl_map_apply_range(read_map, write_map);
783 dim = isl_space_join(isl_map_get_space(acc->source[acc->n_must + j].map),
784 isl_space_reverse(isl_map_get_space(acc->source[k].map)));
785 after_write = after_at_level(dim, after_level);
786 after_write = isl_map_apply_range(after_write, old_map);
787 after_write = isl_map_reverse(after_write);
788 dep_map = isl_map_intersect(dep_map, after_write);
789 before_read = after_at_level(isl_map_get_space(dep_map), before_level);
790 dep_map = isl_map_intersect(dep_map, before_read);
791 return isl_map_reverse(dep_map);
794 /* Given the must and may dependence relations for the must accesses
795 * for level sink_level, check if there are any accesses of may access j
796 * that occur in between and return their union.
797 * If some of these accesses are intermediate with respect to
798 * (previously thought to be) must dependences, then these
799 * must dependences are turned into may dependences.
801 static __isl_give isl_map *all_intermediate_sources(
802 __isl_keep isl_access_info *acc, __isl_take isl_map *map,
803 struct isl_map **must_rel, struct isl_map **may_rel,
804 int j, int sink_level)
806 int k, level;
807 int depth = 2 * isl_map_dim(acc->source[acc->n_must + j].map,
808 isl_dim_in) + 1;
810 for (k = 0; k < acc->n_must; ++k) {
811 int plevel;
813 if (isl_map_plain_is_empty(may_rel[k]) &&
814 isl_map_plain_is_empty(must_rel[k]))
815 continue;
817 plevel = acc->level_before(acc->source[k].data,
818 acc->source[acc->n_must + j].data);
820 for (level = sink_level; level <= depth; ++level) {
821 isl_map *T;
822 isl_map *copy;
823 isl_set *ran;
825 if (!can_precede_at_level(plevel, level))
826 continue;
828 copy = isl_map_copy(may_rel[k]);
829 T = all_later_sources(acc, copy, j, sink_level, k, level);
830 map = isl_map_union(map, T);
832 copy = isl_map_copy(must_rel[k]);
833 T = all_later_sources(acc, copy, j, sink_level, k, level);
834 ran = isl_map_range(isl_map_copy(T));
835 map = isl_map_union(map, T);
836 may_rel[k] = isl_map_union_disjoint(may_rel[k],
837 isl_map_intersect_range(isl_map_copy(must_rel[k]),
838 isl_set_copy(ran)));
839 T = isl_map_from_domain_and_range(
840 isl_set_universe(
841 isl_space_domain(isl_map_get_space(must_rel[k]))),
842 ran);
843 must_rel[k] = isl_map_subtract(must_rel[k], T);
847 return map;
850 /* Given a dependence relation "old_map" between a must-source and the sink,
851 * return a subset of the dependences, augmented with instances
852 * of the source at position "pos" in "acc" that are coscheduled
853 * with the must-source and that access the same element.
854 * That is, if the input lives in a space T -> K, then the output
855 * lives in the space [T -> S] -> K, with S the space of source "pos", and
856 * the domain factor of the domain product is a subset of the input.
857 * The sources are considered to be coscheduled if they have the same values
858 * for the initial "depth" coordinates.
860 * First construct a dependence relation S -> K and a mapping
861 * between coscheduled sources T -> S.
862 * The second is combined with the original dependence relation T -> K
863 * to form a relation in T -> [S -> K], which is subsequently
864 * uncurried to [T -> S] -> K.
865 * This result is then intersected with the dependence relation S -> K
866 * to form the output.
868 static __isl_give isl_map *coscheduled_source(__isl_keep isl_access_info *acc,
869 __isl_keep isl_map *old_map, int pos, int depth)
871 isl_space *space;
872 isl_set *set_C;
873 isl_map *read_map;
874 isl_map *write_map;
875 isl_map *dep_map;
876 isl_map *equal;
877 isl_map *map;
879 set_C = isl_map_range(isl_map_copy(old_map));
880 read_map = isl_map_copy(acc->sink.map);
881 read_map = isl_map_intersect_domain(read_map, set_C);
882 write_map = isl_map_copy(acc->source[pos].map);
883 dep_map = isl_map_domain_product(write_map, read_map);
884 dep_map = isl_set_unwrap(isl_map_domain(dep_map));
885 space = isl_space_join(isl_map_get_space(old_map),
886 isl_space_reverse(isl_map_get_space(dep_map)));
887 equal = isl_map_from_basic_map(isl_basic_map_equal(space, depth));
888 map = isl_map_range_product(equal, isl_map_copy(old_map));
889 map = isl_map_uncurry(map);
890 map = isl_map_intersect_domain_factor_range(map, dep_map);
892 return map;
895 /* After the dependences derived from a must-source have been computed
896 * at a certain level, check if any of the sources of the must-dependences
897 * may be coscheduled with other sources.
898 * If they are any such sources, then there is no way of determining
899 * which of the sources actually comes last and the must-dependences
900 * need to be turned into may-dependences, while dependences from
901 * the other sources need to be added to the may-dependences as well.
902 * "acc" describes the sources and a callback for checking whether
903 * two sources may be coscheduled. If acc->coscheduled is NULL then
904 * the sources are assumed not to be coscheduled.
905 * "must_rel" and "may_rel" describe the must and may-dependence relations
906 * computed at the current level for the must-sources. Some of the dependences
907 * may be moved from "must_rel" to "may_rel".
908 * "flow" contains all dependences computed so far (apart from those
909 * in "must_rel" and "may_rel") and may be updated with additional
910 * dependences derived from may-sources.
912 * In particular, consider all the must-sources with a non-empty
913 * dependence relation in "must_rel". They are considered in reverse
914 * order because that is the order in which they are considered in the caller.
915 * If any of the must-sources are coscheduled, then the last one
916 * is the one that will have a corresponding dependence relation.
917 * For each must-source i, consider both all the previous must-sources
918 * and all the may-sources. If any of those may be coscheduled with
919 * must-source i, then compute the coscheduled instances that access
920 * the same memory elements. The result is a relation [T -> S] -> K.
921 * The projection onto T -> K is a subset of the must-dependence relation
922 * that needs to be turned into may-dependences.
923 * The projection onto S -> K needs to be added to the may-dependences
924 * of source S.
925 * Since a given must-source instance may be coscheduled with several
926 * other source instances, the dependences that need to be turned
927 * into may-dependences are first collected and only actually removed
928 * from the must-dependences after all other sources have been considered.
930 static __isl_give isl_flow *handle_coscheduled(__isl_keep isl_access_info *acc,
931 __isl_keep isl_map **must_rel, __isl_keep isl_map **may_rel,
932 __isl_take isl_flow *flow)
934 int i, j;
936 if (!acc->coscheduled)
937 return flow;
938 for (i = acc->n_must - 1; i >= 0; --i) {
939 isl_map *move;
941 if (isl_map_plain_is_empty(must_rel[i]))
942 continue;
943 move = isl_map_empty(isl_map_get_space(must_rel[i]));
944 for (j = i - 1; j >= 0; --j) {
945 int depth;
946 isl_map *map, *factor;
948 if (!acc->coscheduled(acc->source[i].data,
949 acc->source[j].data))
950 continue;
951 depth = acc->level_before(acc->source[i].data,
952 acc->source[j].data) / 2;
953 map = coscheduled_source(acc, must_rel[i], j, depth);
954 factor = isl_map_domain_factor_range(isl_map_copy(map));
955 may_rel[j] = isl_map_union(may_rel[j], factor);
956 map = isl_map_domain_factor_domain(map);
957 move = isl_map_union(move, map);
959 for (j = 0; j < acc->n_may; ++j) {
960 int depth, pos;
961 isl_map *map, *factor;
963 pos = acc->n_must + j;
964 if (!acc->coscheduled(acc->source[i].data,
965 acc->source[pos].data))
966 continue;
967 depth = acc->level_before(acc->source[i].data,
968 acc->source[pos].data) / 2;
969 map = coscheduled_source(acc, must_rel[i], pos, depth);
970 factor = isl_map_domain_factor_range(isl_map_copy(map));
971 pos = 2 * acc->n_must + j;
972 flow->dep[pos].map = isl_map_union(flow->dep[pos].map,
973 factor);
974 map = isl_map_domain_factor_domain(map);
975 move = isl_map_union(move, map);
977 must_rel[i] = isl_map_subtract(must_rel[i], isl_map_copy(move));
978 may_rel[i] = isl_map_union(may_rel[i], move);
981 return flow;
984 /* Compute dependences for the case where all accesses are "may"
985 * accesses, which boils down to computing memory based dependences.
986 * The generic algorithm would also work in this case, but it would
987 * be overkill to use it.
989 static __isl_give isl_flow *compute_mem_based_dependences(
990 __isl_keep isl_access_info *acc)
992 int i;
993 isl_set *mustdo;
994 isl_set *maydo;
995 isl_flow *res;
997 res = isl_flow_alloc(acc);
998 if (!res)
999 return NULL;
1001 mustdo = isl_map_domain(isl_map_copy(acc->sink.map));
1002 maydo = isl_set_copy(mustdo);
1004 for (i = 0; i < acc->n_may; ++i) {
1005 int plevel;
1006 int is_before;
1007 isl_space *dim;
1008 isl_map *before;
1009 isl_map *dep;
1011 plevel = acc->level_before(acc->source[i].data, acc->sink.data);
1012 is_before = plevel & 1;
1013 plevel >>= 1;
1015 dim = isl_map_get_space(res->dep[i].map);
1016 if (is_before)
1017 before = isl_map_lex_le_first(dim, plevel);
1018 else
1019 before = isl_map_lex_lt_first(dim, plevel);
1020 dep = isl_map_apply_range(isl_map_copy(acc->source[i].map),
1021 isl_map_reverse(isl_map_copy(acc->sink.map)));
1022 dep = isl_map_intersect(dep, before);
1023 mustdo = isl_set_subtract(mustdo,
1024 isl_map_range(isl_map_copy(dep)));
1025 res->dep[i].map = isl_map_union(res->dep[i].map, dep);
1028 res->may_no_source = isl_set_subtract(maydo, isl_set_copy(mustdo));
1029 res->must_no_source = mustdo;
1031 return res;
1034 /* Compute dependences for the case where there is at least one
1035 * "must" access.
1037 * The core algorithm considers all levels in which a source may precede
1038 * the sink, where a level may either be a statement level or a loop level.
1039 * The outermost statement level is 1, the first loop level is 2, etc...
1040 * The algorithm basically does the following:
1041 * for all levels l of the read access from innermost to outermost
1042 * for all sources w that may precede the sink access at that level
1043 * compute the last iteration of the source that precedes the sink access
1044 * at that level
1045 * add result to possible last accesses at level l of source w
1046 * for all sources w2 that we haven't considered yet at this level that may
1047 * also precede the sink access
1048 * for all levels l2 of w from l to innermost
1049 * for all possible last accesses dep of w at l
1050 * compute last iteration of w2 between the source and sink
1051 * of dep
1052 * add result to possible last accesses at level l of write w2
1053 * and replace possible last accesses dep by the remainder
1056 * The above algorithm is applied to the must access. During the course
1057 * of the algorithm, we keep track of sink iterations that still
1058 * need to be considered. These iterations are split into those that
1059 * haven't been matched to any source access (mustdo) and those that have only
1060 * been matched to may accesses (maydo).
1061 * At the end of each level, must-sources and may-sources that are coscheduled
1062 * with the sources of the must-dependences at that level are considered.
1063 * If any coscheduled instances are found, then corresponding may-dependences
1064 * are added and the original must-dependences are turned into may-dependences.
1065 * Afterwards, the may accesses that occur after must-dependence sources
1066 * are considered.
1067 * In particular, we consider may accesses that precede the remaining
1068 * sink iterations, moving elements from mustdo to maydo when appropriate,
1069 * and may accesses that occur between a must source and a sink of any
1070 * dependences found at the current level, turning must dependences into
1071 * may dependences when appropriate.
1074 static __isl_give isl_flow *compute_val_based_dependences(
1075 __isl_keep isl_access_info *acc)
1077 isl_ctx *ctx;
1078 isl_flow *res;
1079 isl_set *mustdo = NULL;
1080 isl_set *maydo = NULL;
1081 int level, j;
1082 int depth;
1083 isl_map **must_rel = NULL;
1084 isl_map **may_rel = NULL;
1086 if (!acc)
1087 return NULL;
1089 res = isl_flow_alloc(acc);
1090 if (!res)
1091 goto error;
1092 ctx = isl_map_get_ctx(acc->sink.map);
1094 depth = 2 * isl_map_dim(acc->sink.map, isl_dim_in) + 1;
1095 mustdo = isl_map_domain(isl_map_copy(acc->sink.map));
1096 maydo = isl_set_empty(isl_set_get_space(mustdo));
1097 if (!mustdo || !maydo)
1098 goto error;
1099 if (isl_set_plain_is_empty(mustdo))
1100 goto done;
1102 must_rel = isl_alloc_array(ctx, struct isl_map *, acc->n_must);
1103 may_rel = isl_alloc_array(ctx, struct isl_map *, acc->n_must);
1104 if (!must_rel || !may_rel)
1105 goto error;
1107 for (level = depth; level >= 1; --level) {
1108 for (j = acc->n_must-1; j >=0; --j) {
1109 isl_space *space;
1110 space = isl_map_get_space(res->dep[2 * j].map);
1111 must_rel[j] = isl_map_empty(space);
1112 may_rel[j] = isl_map_copy(must_rel[j]);
1115 for (j = acc->n_must - 1; j >= 0; --j) {
1116 struct isl_map *T;
1117 struct isl_set *rest;
1118 int plevel;
1120 plevel = acc->level_before(acc->source[j].data,
1121 acc->sink.data);
1122 if (!can_precede_at_level(plevel, level))
1123 continue;
1125 T = last_source(acc, mustdo, j, level, &rest);
1126 must_rel[j] = isl_map_union_disjoint(must_rel[j], T);
1127 mustdo = rest;
1129 intermediate_sources(acc, must_rel, j, level);
1131 T = last_source(acc, maydo, j, level, &rest);
1132 may_rel[j] = isl_map_union_disjoint(may_rel[j], T);
1133 maydo = rest;
1135 intermediate_sources(acc, may_rel, j, level);
1137 if (isl_set_plain_is_empty(mustdo) &&
1138 isl_set_plain_is_empty(maydo))
1139 break;
1141 for (j = j - 1; j >= 0; --j) {
1142 int plevel;
1144 plevel = acc->level_before(acc->source[j].data,
1145 acc->sink.data);
1146 if (!can_precede_at_level(plevel, level))
1147 continue;
1149 intermediate_sources(acc, must_rel, j, level);
1150 intermediate_sources(acc, may_rel, j, level);
1153 handle_coscheduled(acc, must_rel, may_rel, res);
1155 for (j = 0; j < acc->n_may; ++j) {
1156 int plevel;
1157 isl_map *T;
1158 isl_set *ran;
1160 plevel = acc->level_before(acc->source[acc->n_must + j].data,
1161 acc->sink.data);
1162 if (!can_precede_at_level(plevel, level))
1163 continue;
1165 T = all_sources(acc, isl_set_copy(maydo), j, level);
1166 res->dep[2 * acc->n_must + j].map =
1167 isl_map_union(res->dep[2 * acc->n_must + j].map, T);
1168 T = all_sources(acc, isl_set_copy(mustdo), j, level);
1169 ran = isl_map_range(isl_map_copy(T));
1170 res->dep[2 * acc->n_must + j].map =
1171 isl_map_union(res->dep[2 * acc->n_must + j].map, T);
1172 mustdo = isl_set_subtract(mustdo, isl_set_copy(ran));
1173 maydo = isl_set_union_disjoint(maydo, ran);
1175 T = res->dep[2 * acc->n_must + j].map;
1176 T = all_intermediate_sources(acc, T, must_rel, may_rel,
1177 j, level);
1178 res->dep[2 * acc->n_must + j].map = T;
1181 for (j = acc->n_must - 1; j >= 0; --j) {
1182 res->dep[2 * j].map =
1183 isl_map_union_disjoint(res->dep[2 * j].map,
1184 must_rel[j]);
1185 res->dep[2 * j + 1].map =
1186 isl_map_union_disjoint(res->dep[2 * j + 1].map,
1187 may_rel[j]);
1190 if (isl_set_plain_is_empty(mustdo) &&
1191 isl_set_plain_is_empty(maydo))
1192 break;
1195 free(must_rel);
1196 free(may_rel);
1197 done:
1198 res->must_no_source = mustdo;
1199 res->may_no_source = maydo;
1200 return res;
1201 error:
1202 isl_flow_free(res);
1203 isl_set_free(mustdo);
1204 isl_set_free(maydo);
1205 free(must_rel);
1206 free(may_rel);
1207 return NULL;
1210 /* Given a "sink" access, a list of n "source" accesses,
1211 * compute for each iteration of the sink access
1212 * and for each element accessed by that iteration,
1213 * the source access in the list that last accessed the
1214 * element accessed by the sink access before this sink access.
1215 * Each access is given as a map from the loop iterators
1216 * to the array indices.
1217 * The result is a list of n relations between source and sink
1218 * iterations and a subset of the domain of the sink access,
1219 * corresponding to those iterations that access an element
1220 * not previously accessed.
1222 * To deal with multi-valued sink access relations, the sink iteration
1223 * domain is first extended with dimensions that correspond to the data
1224 * space. However, these extra dimensions are not projected out again.
1225 * It is up to the caller to decide whether these dimensions should be kept.
1227 static __isl_give isl_flow *access_info_compute_flow_core(
1228 __isl_take isl_access_info *acc)
1230 struct isl_flow *res = NULL;
1232 if (!acc)
1233 return NULL;
1235 acc->sink.map = isl_map_range_map(acc->sink.map);
1236 if (!acc->sink.map)
1237 goto error;
1239 if (acc->n_must == 0)
1240 res = compute_mem_based_dependences(acc);
1241 else {
1242 acc = isl_access_info_sort_sources(acc);
1243 res = compute_val_based_dependences(acc);
1245 acc = isl_access_info_free(acc);
1246 if (!res)
1247 return NULL;
1248 if (!res->must_no_source || !res->may_no_source)
1249 goto error;
1250 return res;
1251 error:
1252 isl_access_info_free(acc);
1253 isl_flow_free(res);
1254 return NULL;
1257 /* Given a "sink" access, a list of n "source" accesses,
1258 * compute for each iteration of the sink access
1259 * and for each element accessed by that iteration,
1260 * the source access in the list that last accessed the
1261 * element accessed by the sink access before this sink access.
1262 * Each access is given as a map from the loop iterators
1263 * to the array indices.
1264 * The result is a list of n relations between source and sink
1265 * iterations and a subset of the domain of the sink access,
1266 * corresponding to those iterations that access an element
1267 * not previously accessed.
1269 * To deal with multi-valued sink access relations,
1270 * access_info_compute_flow_core extends the sink iteration domain
1271 * with dimensions that correspond to the data space. These extra dimensions
1272 * are projected out from the result of access_info_compute_flow_core.
1274 __isl_give isl_flow *isl_access_info_compute_flow(__isl_take isl_access_info *acc)
1276 int j;
1277 struct isl_flow *res;
1279 if (!acc)
1280 return NULL;
1282 acc->domain_map = isl_map_domain_map(isl_map_copy(acc->sink.map));
1283 res = access_info_compute_flow_core(acc);
1284 if (!res)
1285 return NULL;
1287 for (j = 0; j < res->n_source; ++j) {
1288 res->dep[j].map = isl_map_range_factor_domain(res->dep[j].map);
1289 if (!res->dep[j].map)
1290 goto error;
1293 return res;
1294 error:
1295 isl_flow_free(res);
1296 return NULL;
1300 /* Keep track of some information about a schedule for a given
1301 * access. In particular, keep track of which dimensions
1302 * have a constant value and of the actual constant values.
1304 struct isl_sched_info {
1305 int *is_cst;
1306 isl_vec *cst;
1309 static void sched_info_free(__isl_take struct isl_sched_info *info)
1311 if (!info)
1312 return;
1313 isl_vec_free(info->cst);
1314 free(info->is_cst);
1315 free(info);
1318 /* Extract information on the constant dimensions of the schedule
1319 * for a given access. The "map" is of the form
1321 * [S -> D] -> A
1323 * with S the schedule domain, D the iteration domain and A the data domain.
1325 static __isl_give struct isl_sched_info *sched_info_alloc(
1326 __isl_keep isl_map *map)
1328 isl_ctx *ctx;
1329 isl_space *dim;
1330 struct isl_sched_info *info;
1331 int i, n;
1333 if (!map)
1334 return NULL;
1336 dim = isl_space_unwrap(isl_space_domain(isl_map_get_space(map)));
1337 if (!dim)
1338 return NULL;
1339 n = isl_space_dim(dim, isl_dim_in);
1340 isl_space_free(dim);
1342 ctx = isl_map_get_ctx(map);
1343 info = isl_alloc_type(ctx, struct isl_sched_info);
1344 if (!info)
1345 return NULL;
1346 info->is_cst = isl_alloc_array(ctx, int, n);
1347 info->cst = isl_vec_alloc(ctx, n);
1348 if (n && (!info->is_cst || !info->cst))
1349 goto error;
1351 for (i = 0; i < n; ++i) {
1352 isl_val *v;
1354 v = isl_map_plain_get_val_if_fixed(map, isl_dim_in, i);
1355 if (!v)
1356 goto error;
1357 info->is_cst[i] = !isl_val_is_nan(v);
1358 if (info->is_cst[i])
1359 info->cst = isl_vec_set_element_val(info->cst, i, v);
1360 else
1361 isl_val_free(v);
1364 return info;
1365 error:
1366 sched_info_free(info);
1367 return NULL;
1370 /* The different types of access relations that isl_union_access_info
1371 * keeps track of.
1373 * "isl_access_sink" represents the sink accesses.
1374 * "isl_access_must_source" represents the definite source accesses.
1375 * "isl_access_may_source" represents the possible source accesses.
1377 * isl_access_sink is sometimes treated differently and
1378 * should therefore appear first.
1380 enum isl_access_type {
1381 isl_access_sink,
1382 isl_access_must_source,
1383 isl_access_may_source,
1384 isl_access_end
1387 /* This structure represents the input for a dependence analysis computation.
1389 * "access" contains the access relations.
1391 * "schedule" or "schedule_map" represents the execution order.
1392 * Exactly one of these fields should be NULL. The other field
1393 * determines the execution order.
1395 * The domains of these four maps refer to the same iteration spaces(s).
1396 * The ranges of the first three maps also refer to the same data space(s).
1398 * After a call to isl_union_access_info_introduce_schedule,
1399 * the "schedule_map" field no longer contains useful information.
1401 struct isl_union_access_info {
1402 isl_union_map *access[isl_access_end];
1404 isl_schedule *schedule;
1405 isl_union_map *schedule_map;
1408 /* Free "access" and return NULL.
1410 __isl_null isl_union_access_info *isl_union_access_info_free(
1411 __isl_take isl_union_access_info *access)
1413 enum isl_access_type i;
1415 if (!access)
1416 return NULL;
1418 for (i = isl_access_sink; i < isl_access_end; ++i)
1419 isl_union_map_free(access->access[i]);
1420 isl_schedule_free(access->schedule);
1421 isl_union_map_free(access->schedule_map);
1422 free(access);
1424 return NULL;
1427 /* Return the isl_ctx to which "access" belongs.
1429 isl_ctx *isl_union_access_info_get_ctx(__isl_keep isl_union_access_info *access)
1431 if (!access)
1432 return NULL;
1433 return isl_union_map_get_ctx(access->access[isl_access_sink]);
1436 /* Construct an empty (invalid) isl_union_access_info object.
1437 * The caller is responsible for setting the sink access relation and
1438 * initializing all the other fields, e.g., by calling
1439 * isl_union_access_info_init.
1441 static __isl_give isl_union_access_info *isl_union_access_info_alloc(
1442 isl_ctx *ctx)
1444 return isl_calloc_type(ctx, isl_union_access_info);
1447 /* Initialize all the fields of "info", except the sink access relation,
1448 * which is assumed to have been set by the caller.
1450 * By default, we use the schedule field of the isl_union_access_info,
1451 * but this may be overridden by a call
1452 * to isl_union_access_info_set_schedule_map.
1454 static __isl_give isl_union_access_info *isl_union_access_info_init(
1455 __isl_take isl_union_access_info *info)
1457 isl_space *space;
1458 isl_union_map *empty;
1459 enum isl_access_type i;
1461 if (!info)
1462 return NULL;
1463 if (!info->access[isl_access_sink])
1464 return isl_union_access_info_free(info);
1466 space = isl_union_map_get_space(info->access[isl_access_sink]);
1467 empty = isl_union_map_empty(isl_space_copy(space));
1468 for (i = isl_access_sink + 1; i < isl_access_end; ++i)
1469 if (!info->access[i])
1470 info->access[i] = isl_union_map_copy(empty);
1471 isl_union_map_free(empty);
1472 if (!info->schedule && !info->schedule_map)
1473 info->schedule = isl_schedule_empty(isl_space_copy(space));
1474 isl_space_free(space);
1476 for (i = isl_access_sink + 1; i < isl_access_end; ++i)
1477 if (!info->access[i])
1478 return isl_union_access_info_free(info);
1479 if (!info->schedule && !info->schedule_map)
1480 return isl_union_access_info_free(info);
1482 return info;
1485 /* Create a new isl_union_access_info with the given sink accesses and
1486 * and no other accesses or schedule information.
1488 __isl_give isl_union_access_info *isl_union_access_info_from_sink(
1489 __isl_take isl_union_map *sink)
1491 isl_ctx *ctx;
1492 isl_union_access_info *access;
1494 if (!sink)
1495 return NULL;
1496 ctx = isl_union_map_get_ctx(sink);
1497 access = isl_union_access_info_alloc(ctx);
1498 if (!access)
1499 goto error;
1500 access->access[isl_access_sink] = sink;
1501 return isl_union_access_info_init(access);
1502 error:
1503 isl_union_map_free(sink);
1504 return NULL;
1507 /* Replace the access relation of type "type" of "info" by "access".
1509 static __isl_give isl_union_access_info *isl_union_access_info_set(
1510 __isl_take isl_union_access_info *info,
1511 enum isl_access_type type, __isl_take isl_union_map *access)
1513 if (!info || !access)
1514 goto error;
1516 isl_union_map_free(info->access[type]);
1517 info->access[type] = access;
1519 return info;
1520 error:
1521 isl_union_access_info_free(info);
1522 isl_union_map_free(access);
1523 return NULL;
1526 /* Replace the definite source accesses of "access" by "must_source".
1528 __isl_give isl_union_access_info *isl_union_access_info_set_must_source(
1529 __isl_take isl_union_access_info *access,
1530 __isl_take isl_union_map *must_source)
1532 return isl_union_access_info_set(access, isl_access_must_source,
1533 must_source);
1536 /* Replace the possible source accesses of "access" by "may_source".
1538 __isl_give isl_union_access_info *isl_union_access_info_set_may_source(
1539 __isl_take isl_union_access_info *access,
1540 __isl_take isl_union_map *may_source)
1542 return isl_union_access_info_set(access, isl_access_may_source,
1543 may_source);
1546 /* Replace the schedule of "access" by "schedule".
1547 * Also free the schedule_map in case it was set last.
1549 __isl_give isl_union_access_info *isl_union_access_info_set_schedule(
1550 __isl_take isl_union_access_info *access,
1551 __isl_take isl_schedule *schedule)
1553 if (!access || !schedule)
1554 goto error;
1556 access->schedule_map = isl_union_map_free(access->schedule_map);
1557 isl_schedule_free(access->schedule);
1558 access->schedule = schedule;
1560 return access;
1561 error:
1562 isl_union_access_info_free(access);
1563 isl_schedule_free(schedule);
1564 return NULL;
1567 /* Replace the schedule map of "access" by "schedule_map".
1568 * Also free the schedule in case it was set last.
1570 __isl_give isl_union_access_info *isl_union_access_info_set_schedule_map(
1571 __isl_take isl_union_access_info *access,
1572 __isl_take isl_union_map *schedule_map)
1574 if (!access || !schedule_map)
1575 goto error;
1577 isl_union_map_free(access->schedule_map);
1578 access->schedule = isl_schedule_free(access->schedule);
1579 access->schedule_map = schedule_map;
1581 return access;
1582 error:
1583 isl_union_access_info_free(access);
1584 isl_union_map_free(schedule_map);
1585 return NULL;
1588 __isl_give isl_union_access_info *isl_union_access_info_copy(
1589 __isl_keep isl_union_access_info *access)
1591 isl_union_access_info *copy;
1592 enum isl_access_type i;
1594 if (!access)
1595 return NULL;
1596 copy = isl_union_access_info_from_sink(
1597 isl_union_map_copy(access->access[isl_access_sink]));
1598 for (i = isl_access_sink + 1; i < isl_access_end; ++i)
1599 copy = isl_union_access_info_set(copy, i,
1600 isl_union_map_copy(access->access[i]));
1601 if (access->schedule)
1602 copy = isl_union_access_info_set_schedule(copy,
1603 isl_schedule_copy(access->schedule));
1604 else
1605 copy = isl_union_access_info_set_schedule_map(copy,
1606 isl_union_map_copy(access->schedule_map));
1608 return copy;
1611 /* Print a key-value pair of a YAML mapping to "p",
1612 * with key "name" and value "umap".
1614 static __isl_give isl_printer *print_union_map_field(__isl_take isl_printer *p,
1615 const char *name, __isl_keep isl_union_map *umap)
1617 p = isl_printer_print_str(p, name);
1618 p = isl_printer_yaml_next(p);
1619 p = isl_printer_print_str(p, "\"");
1620 p = isl_printer_print_union_map(p, umap);
1621 p = isl_printer_print_str(p, "\"");
1622 p = isl_printer_yaml_next(p);
1624 return p;
1627 /* An enumeration of the various keys that may appear in a YAML mapping
1628 * of an isl_union_access_info object.
1629 * The keys for the access relation types are assumed to have the same values
1630 * as the access relation types in isl_access_type.
1632 enum isl_ai_key {
1633 isl_ai_key_error = -1,
1634 isl_ai_key_sink = isl_access_sink,
1635 isl_ai_key_must_source = isl_access_must_source,
1636 isl_ai_key_may_source = isl_access_may_source,
1637 isl_ai_key_schedule_map,
1638 isl_ai_key_schedule,
1639 isl_ai_key_end
1642 /* Textual representations of the YAML keys for an isl_union_access_info
1643 * object.
1645 static char *key_str[] = {
1646 [isl_ai_key_sink] = "sink",
1647 [isl_ai_key_must_source] = "must_source",
1648 [isl_ai_key_may_source] = "may_source",
1649 [isl_ai_key_schedule_map] = "schedule_map",
1650 [isl_ai_key_schedule] = "schedule",
1653 /* Print a key-value pair corresponding to the access relation of type "type"
1654 * of a YAML mapping of "info" to "p".
1656 * The sink access relation is always printed, but any other access relation
1657 * is only printed if it is non-empty.
1659 static __isl_give isl_printer *print_access_field(__isl_take isl_printer *p,
1660 __isl_keep isl_union_access_info *info, enum isl_access_type type)
1662 if (type != isl_access_sink) {
1663 isl_bool empty;
1665 empty = isl_union_map_is_empty(info->access[type]);
1666 if (empty < 0)
1667 return isl_printer_free(p);
1668 if (empty)
1669 return p;
1671 return print_union_map_field(p, key_str[type], info->access[type]);
1674 /* Print the information contained in "access" to "p".
1675 * The information is printed as a YAML document.
1677 __isl_give isl_printer *isl_printer_print_union_access_info(
1678 __isl_take isl_printer *p, __isl_keep isl_union_access_info *access)
1680 enum isl_access_type i;
1682 if (!access)
1683 return isl_printer_free(p);
1685 p = isl_printer_yaml_start_mapping(p);
1686 for (i = isl_access_sink; i < isl_access_end; ++i)
1687 p = print_access_field(p, access, i);
1688 if (access->schedule) {
1689 p = isl_printer_print_str(p, key_str[isl_ai_key_schedule]);
1690 p = isl_printer_yaml_next(p);
1691 p = isl_printer_print_schedule(p, access->schedule);
1692 p = isl_printer_yaml_next(p);
1693 } else {
1694 p = print_union_map_field(p, key_str[isl_ai_key_schedule_map],
1695 access->schedule_map);
1697 p = isl_printer_yaml_end_mapping(p);
1699 return p;
1702 /* Return a string representation of the information in "access".
1703 * The information is printed in flow format.
1705 __isl_give char *isl_union_access_info_to_str(
1706 __isl_keep isl_union_access_info *access)
1708 isl_printer *p;
1709 char *s;
1711 if (!access)
1712 return NULL;
1714 p = isl_printer_to_str(isl_union_access_info_get_ctx(access));
1715 p = isl_printer_set_yaml_style(p, ISL_YAML_STYLE_FLOW);
1716 p = isl_printer_print_union_access_info(p, access);
1717 s = isl_printer_get_str(p);
1718 isl_printer_free(p);
1720 return s;
1723 #undef KEY
1724 #define KEY enum isl_ai_key
1725 #undef KEY_ERROR
1726 #define KEY_ERROR isl_ai_key_error
1727 #undef KEY_END
1728 #define KEY_END isl_ai_key_end
1729 #include "extract_key.c"
1731 #undef BASE
1732 #define BASE union_map
1733 #include "read_in_string_templ.c"
1735 /* Read an isl_union_access_info object from "s".
1737 * Start off with an empty (invalid) isl_union_access_info object and
1738 * then fill up the fields based on the input.
1739 * The input needs to contain at least a description of the sink
1740 * access relation as well as some form of schedule.
1741 * The other access relations are set to empty relations
1742 * by isl_union_access_info_init if they are not specified in the input.
1744 __isl_give isl_union_access_info *isl_stream_read_union_access_info(
1745 isl_stream *s)
1747 isl_ctx *ctx;
1748 isl_union_access_info *info;
1749 int more;
1750 int sink_set = 0;
1751 int schedule_set = 0;
1753 if (isl_stream_yaml_read_start_mapping(s))
1754 return NULL;
1756 ctx = isl_stream_get_ctx(s);
1757 info = isl_union_access_info_alloc(ctx);
1758 while ((more = isl_stream_yaml_next(s)) > 0) {
1759 enum isl_ai_key key;
1760 isl_union_map *access, *schedule_map;
1761 isl_schedule *schedule;
1763 key = get_key(s);
1764 if (isl_stream_yaml_next(s) < 0)
1765 return isl_union_access_info_free(info);
1766 switch (key) {
1767 case isl_ai_key_end:
1768 case isl_ai_key_error:
1769 return isl_union_access_info_free(info);
1770 case isl_ai_key_sink:
1771 sink_set = 1;
1772 case isl_ai_key_must_source:
1773 case isl_ai_key_may_source:
1774 access = read_union_map(s);
1775 info = isl_union_access_info_set(info, key, access);
1776 if (!info)
1777 return NULL;
1778 break;
1779 case isl_ai_key_schedule_map:
1780 schedule_set = 1;
1781 schedule_map = read_union_map(s);
1782 info = isl_union_access_info_set_schedule_map(info,
1783 schedule_map);
1784 if (!info)
1785 return NULL;
1786 break;
1787 case isl_ai_key_schedule:
1788 schedule_set = 1;
1789 schedule = isl_stream_read_schedule(s);
1790 info = isl_union_access_info_set_schedule(info,
1791 schedule);
1792 if (!info)
1793 return NULL;
1794 break;
1797 if (more < 0)
1798 return isl_union_access_info_free(info);
1800 if (isl_stream_yaml_read_end_mapping(s) < 0) {
1801 isl_stream_error(s, NULL, "unexpected extra elements");
1802 return isl_union_access_info_free(info);
1805 if (!sink_set) {
1806 isl_stream_error(s, NULL, "no sink specified");
1807 return isl_union_access_info_free(info);
1810 if (!schedule_set) {
1811 isl_stream_error(s, NULL, "no schedule specified");
1812 return isl_union_access_info_free(info);
1815 return isl_union_access_info_init(info);
1818 /* Read an isl_union_access_info object from the file "input".
1820 __isl_give isl_union_access_info *isl_union_access_info_read_from_file(
1821 isl_ctx *ctx, FILE *input)
1823 isl_stream *s;
1824 isl_union_access_info *access;
1826 s = isl_stream_new_file(ctx, input);
1827 if (!s)
1828 return NULL;
1829 access = isl_stream_read_union_access_info(s);
1830 isl_stream_free(s);
1832 return access;
1835 /* Update the fields of "access" such that they all have the same parameters,
1836 * keeping in mind that the schedule_map field may be NULL and ignoring
1837 * the schedule field.
1839 static __isl_give isl_union_access_info *isl_union_access_info_align_params(
1840 __isl_take isl_union_access_info *access)
1842 isl_space *space;
1843 enum isl_access_type i;
1845 if (!access)
1846 return NULL;
1848 space = isl_union_map_get_space(access->access[isl_access_sink]);
1849 for (i = isl_access_sink + 1; i < isl_access_end; ++i)
1850 space = isl_space_align_params(space,
1851 isl_union_map_get_space(access->access[i]));
1852 if (access->schedule_map)
1853 space = isl_space_align_params(space,
1854 isl_union_map_get_space(access->schedule_map));
1855 for (i = isl_access_sink; i < isl_access_end; ++i)
1856 access->access[i] =
1857 isl_union_map_align_params(access->access[i],
1858 isl_space_copy(space));
1859 if (!access->schedule_map) {
1860 isl_space_free(space);
1861 } else {
1862 access->schedule_map =
1863 isl_union_map_align_params(access->schedule_map, space);
1864 if (!access->schedule_map)
1865 return isl_union_access_info_free(access);
1868 for (i = isl_access_sink; i < isl_access_end; ++i)
1869 if (!access->access[i])
1870 return isl_union_access_info_free(access);
1872 return access;
1875 /* Prepend the schedule dimensions to the iteration domains.
1877 * That is, if the schedule is of the form
1879 * D -> S
1881 * while the access relations are of the form
1883 * D -> A
1885 * then the updated access relations are of the form
1887 * [S -> D] -> A
1889 * The schedule map is also replaced by the map
1891 * [S -> D] -> D
1893 * that is used during the internal computation.
1894 * Neither the original schedule map nor this updated schedule map
1895 * are used after the call to this function.
1897 static __isl_give isl_union_access_info *
1898 isl_union_access_info_introduce_schedule(
1899 __isl_take isl_union_access_info *access)
1901 isl_union_map *sm;
1902 enum isl_access_type i;
1904 if (!access)
1905 return NULL;
1907 sm = isl_union_map_reverse(access->schedule_map);
1908 sm = isl_union_map_range_map(sm);
1909 for (i = isl_access_sink; i < isl_access_end; ++i)
1910 access->access[i] =
1911 isl_union_map_apply_range(isl_union_map_copy(sm),
1912 access->access[i]);
1913 access->schedule_map = sm;
1915 for (i = isl_access_sink; i < isl_access_end; ++i)
1916 if (!access->access[i])
1917 return isl_union_access_info_free(access);
1918 if (!access->schedule_map)
1919 return isl_union_access_info_free(access);
1921 return access;
1924 /* This structure represents the result of a dependence analysis computation.
1926 * "must_dep" represents the full definite dependences
1927 * "may_dep" represents the full non-definite dependences.
1928 * Both are of the form
1930 * [Source] -> [[Sink -> Data]]
1932 * (after the schedule dimensions have been projected out).
1933 * "must_no_source" represents the subset of the sink accesses for which
1934 * definitely no source was found.
1935 * "may_no_source" represents the subset of the sink accesses for which
1936 * possibly, but not definitely, no source was found.
1938 struct isl_union_flow {
1939 isl_union_map *must_dep;
1940 isl_union_map *may_dep;
1941 isl_union_map *must_no_source;
1942 isl_union_map *may_no_source;
1945 /* Return the isl_ctx to which "flow" belongs.
1947 isl_ctx *isl_union_flow_get_ctx(__isl_keep isl_union_flow *flow)
1949 return flow ? isl_union_map_get_ctx(flow->must_dep) : NULL;
1952 /* Free "flow" and return NULL.
1954 __isl_null isl_union_flow *isl_union_flow_free(__isl_take isl_union_flow *flow)
1956 if (!flow)
1957 return NULL;
1958 isl_union_map_free(flow->must_dep);
1959 isl_union_map_free(flow->may_dep);
1960 isl_union_map_free(flow->must_no_source);
1961 isl_union_map_free(flow->may_no_source);
1962 free(flow);
1963 return NULL;
1966 void isl_union_flow_dump(__isl_keep isl_union_flow *flow)
1968 if (!flow)
1969 return;
1971 fprintf(stderr, "must dependences: ");
1972 isl_union_map_dump(flow->must_dep);
1973 fprintf(stderr, "may dependences: ");
1974 isl_union_map_dump(flow->may_dep);
1975 fprintf(stderr, "must no source: ");
1976 isl_union_map_dump(flow->must_no_source);
1977 fprintf(stderr, "may no source: ");
1978 isl_union_map_dump(flow->may_no_source);
1981 /* Return the full definite dependences in "flow", with accessed elements.
1983 __isl_give isl_union_map *isl_union_flow_get_full_must_dependence(
1984 __isl_keep isl_union_flow *flow)
1986 if (!flow)
1987 return NULL;
1988 return isl_union_map_copy(flow->must_dep);
1991 /* Return the full possible dependences in "flow", including the definite
1992 * dependences, with accessed elements.
1994 __isl_give isl_union_map *isl_union_flow_get_full_may_dependence(
1995 __isl_keep isl_union_flow *flow)
1997 if (!flow)
1998 return NULL;
1999 return isl_union_map_union(isl_union_map_copy(flow->must_dep),
2000 isl_union_map_copy(flow->may_dep));
2003 /* Return the definite dependences in "flow", without the accessed elements.
2005 __isl_give isl_union_map *isl_union_flow_get_must_dependence(
2006 __isl_keep isl_union_flow *flow)
2008 isl_union_map *dep;
2010 if (!flow)
2011 return NULL;
2012 dep = isl_union_map_copy(flow->must_dep);
2013 return isl_union_map_range_factor_domain(dep);
2016 /* Return the possible dependences in "flow", including the definite
2017 * dependences, without the accessed elements.
2019 __isl_give isl_union_map *isl_union_flow_get_may_dependence(
2020 __isl_keep isl_union_flow *flow)
2022 isl_union_map *dep;
2024 if (!flow)
2025 return NULL;
2026 dep = isl_union_map_union(isl_union_map_copy(flow->must_dep),
2027 isl_union_map_copy(flow->may_dep));
2028 return isl_union_map_range_factor_domain(dep);
2031 /* Return the non-definite dependences in "flow".
2033 static __isl_give isl_union_map *isl_union_flow_get_non_must_dependence(
2034 __isl_keep isl_union_flow *flow)
2036 if (!flow)
2037 return NULL;
2038 return isl_union_map_copy(flow->may_dep);
2041 /* Return the subset of the sink accesses for which definitely
2042 * no source was found.
2044 __isl_give isl_union_map *isl_union_flow_get_must_no_source(
2045 __isl_keep isl_union_flow *flow)
2047 if (!flow)
2048 return NULL;
2049 return isl_union_map_copy(flow->must_no_source);
2052 /* Return the subset of the sink accesses for which possibly
2053 * no source was found, including those for which definitely
2054 * no source was found.
2056 __isl_give isl_union_map *isl_union_flow_get_may_no_source(
2057 __isl_keep isl_union_flow *flow)
2059 if (!flow)
2060 return NULL;
2061 return isl_union_map_union(isl_union_map_copy(flow->must_no_source),
2062 isl_union_map_copy(flow->may_no_source));
2065 /* Return the subset of the sink accesses for which possibly, but not
2066 * definitely, no source was found.
2068 static __isl_give isl_union_map *isl_union_flow_get_non_must_no_source(
2069 __isl_keep isl_union_flow *flow)
2071 if (!flow)
2072 return NULL;
2073 return isl_union_map_copy(flow->may_no_source);
2076 /* Create a new isl_union_flow object, initialized with empty
2077 * dependence relations and sink subsets.
2079 static __isl_give isl_union_flow *isl_union_flow_alloc(
2080 __isl_take isl_space *space)
2082 isl_ctx *ctx;
2083 isl_union_map *empty;
2084 isl_union_flow *flow;
2086 if (!space)
2087 return NULL;
2088 ctx = isl_space_get_ctx(space);
2089 flow = isl_alloc_type(ctx, isl_union_flow);
2090 if (!flow)
2091 goto error;
2093 empty = isl_union_map_empty(space);
2094 flow->must_dep = isl_union_map_copy(empty);
2095 flow->may_dep = isl_union_map_copy(empty);
2096 flow->must_no_source = isl_union_map_copy(empty);
2097 flow->may_no_source = empty;
2099 if (!flow->must_dep || !flow->may_dep ||
2100 !flow->must_no_source || !flow->may_no_source)
2101 return isl_union_flow_free(flow);
2103 return flow;
2104 error:
2105 isl_space_free(space);
2106 return NULL;
2109 /* Copy this isl_union_flow object.
2111 __isl_give isl_union_flow *isl_union_flow_copy(__isl_keep isl_union_flow *flow)
2113 isl_union_flow *copy;
2115 if (!flow)
2116 return NULL;
2118 copy = isl_union_flow_alloc(isl_union_map_get_space(flow->must_dep));
2120 if (!copy)
2121 return NULL;
2123 copy->must_dep = isl_union_map_union(copy->must_dep,
2124 isl_union_map_copy(flow->must_dep));
2125 copy->may_dep = isl_union_map_union(copy->may_dep,
2126 isl_union_map_copy(flow->may_dep));
2127 copy->must_no_source = isl_union_map_union(copy->must_no_source,
2128 isl_union_map_copy(flow->must_no_source));
2129 copy->may_no_source = isl_union_map_union(copy->may_no_source,
2130 isl_union_map_copy(flow->may_no_source));
2132 if (!copy->must_dep || !copy->may_dep ||
2133 !copy->must_no_source || !copy->may_no_source)
2134 return isl_union_flow_free(copy);
2136 return copy;
2139 /* Drop the schedule dimensions from the iteration domains in "flow".
2140 * In particular, the schedule dimensions have been prepended
2141 * to the iteration domains prior to the dependence analysis by
2142 * replacing the iteration domain D, by the wrapped map [S -> D].
2143 * Replace these wrapped maps by the original D.
2145 * In particular, the dependences computed by access_info_compute_flow_core
2146 * are of the form
2148 * [S -> D] -> [[S' -> D'] -> A]
2150 * The schedule dimensions are projected out by first currying the range,
2151 * resulting in
2153 * [S -> D] -> [S' -> [D' -> A]]
2155 * and then computing the factor range
2157 * D -> [D' -> A]
2159 static __isl_give isl_union_flow *isl_union_flow_drop_schedule(
2160 __isl_take isl_union_flow *flow)
2162 if (!flow)
2163 return NULL;
2165 flow->must_dep = isl_union_map_range_curry(flow->must_dep);
2166 flow->must_dep = isl_union_map_factor_range(flow->must_dep);
2167 flow->may_dep = isl_union_map_range_curry(flow->may_dep);
2168 flow->may_dep = isl_union_map_factor_range(flow->may_dep);
2169 flow->must_no_source =
2170 isl_union_map_domain_factor_range(flow->must_no_source);
2171 flow->may_no_source =
2172 isl_union_map_domain_factor_range(flow->may_no_source);
2174 if (!flow->must_dep || !flow->may_dep ||
2175 !flow->must_no_source || !flow->may_no_source)
2176 return isl_union_flow_free(flow);
2178 return flow;
2181 struct isl_compute_flow_data {
2182 isl_union_map *must_source;
2183 isl_union_map *may_source;
2184 isl_union_flow *flow;
2186 int count;
2187 int must;
2188 isl_space *dim;
2189 struct isl_sched_info *sink_info;
2190 struct isl_sched_info **source_info;
2191 isl_access_info *accesses;
2194 static isl_stat count_matching_array(__isl_take isl_map *map, void *user)
2196 int eq;
2197 isl_space *dim;
2198 struct isl_compute_flow_data *data;
2200 data = (struct isl_compute_flow_data *)user;
2202 dim = isl_space_range(isl_map_get_space(map));
2204 eq = isl_space_is_equal(dim, data->dim);
2206 isl_space_free(dim);
2207 isl_map_free(map);
2209 if (eq < 0)
2210 return isl_stat_error;
2211 if (eq)
2212 data->count++;
2214 return isl_stat_ok;
2217 static isl_stat collect_matching_array(__isl_take isl_map *map, void *user)
2219 int eq;
2220 isl_space *dim;
2221 struct isl_sched_info *info;
2222 struct isl_compute_flow_data *data;
2224 data = (struct isl_compute_flow_data *)user;
2226 dim = isl_space_range(isl_map_get_space(map));
2228 eq = isl_space_is_equal(dim, data->dim);
2230 isl_space_free(dim);
2232 if (eq < 0)
2233 goto error;
2234 if (!eq) {
2235 isl_map_free(map);
2236 return isl_stat_ok;
2239 info = sched_info_alloc(map);
2240 data->source_info[data->count] = info;
2242 data->accesses = isl_access_info_add_source(data->accesses,
2243 map, data->must, info);
2245 data->count++;
2247 return isl_stat_ok;
2248 error:
2249 isl_map_free(map);
2250 return isl_stat_error;
2253 /* Determine the shared nesting level and the "textual order" of
2254 * the given accesses.
2256 * We first determine the minimal schedule dimension for both accesses.
2258 * If among those dimensions, we can find one where both have a fixed
2259 * value and if moreover those values are different, then the previous
2260 * dimension is the last shared nesting level and the textual order
2261 * is determined based on the order of the fixed values.
2262 * If no such fixed values can be found, then we set the shared
2263 * nesting level to the minimal schedule dimension, with no textual ordering.
2265 static int before(void *first, void *second)
2267 struct isl_sched_info *info1 = first;
2268 struct isl_sched_info *info2 = second;
2269 int n1, n2;
2270 int i;
2272 n1 = isl_vec_size(info1->cst);
2273 n2 = isl_vec_size(info2->cst);
2275 if (n2 < n1)
2276 n1 = n2;
2278 for (i = 0; i < n1; ++i) {
2279 int r;
2280 int cmp;
2282 if (!info1->is_cst[i])
2283 continue;
2284 if (!info2->is_cst[i])
2285 continue;
2286 cmp = isl_vec_cmp_element(info1->cst, info2->cst, i);
2287 if (cmp == 0)
2288 continue;
2290 r = 2 * i + (cmp < 0);
2292 return r;
2295 return 2 * n1;
2298 /* Check if the given two accesses may be coscheduled.
2299 * If so, return 1. Otherwise return 0.
2301 * Two accesses may only be coscheduled if the fixed schedule
2302 * coordinates have the same values.
2304 static int coscheduled(void *first, void *second)
2306 struct isl_sched_info *info1 = first;
2307 struct isl_sched_info *info2 = second;
2308 int n1, n2;
2309 int i;
2311 n1 = isl_vec_size(info1->cst);
2312 n2 = isl_vec_size(info2->cst);
2314 if (n2 < n1)
2315 n1 = n2;
2317 for (i = 0; i < n1; ++i) {
2318 int cmp;
2320 if (!info1->is_cst[i])
2321 continue;
2322 if (!info2->is_cst[i])
2323 continue;
2324 cmp = isl_vec_cmp_element(info1->cst, info2->cst, i);
2325 if (cmp != 0)
2326 return 0;
2329 return 1;
2332 /* Given a sink access, look for all the source accesses that access
2333 * the same array and perform dataflow analysis on them using
2334 * isl_access_info_compute_flow_core.
2336 static isl_stat compute_flow(__isl_take isl_map *map, void *user)
2338 int i;
2339 isl_ctx *ctx;
2340 struct isl_compute_flow_data *data;
2341 isl_flow *flow;
2342 isl_union_flow *df;
2344 data = (struct isl_compute_flow_data *)user;
2345 df = data->flow;
2347 ctx = isl_map_get_ctx(map);
2349 data->accesses = NULL;
2350 data->sink_info = NULL;
2351 data->source_info = NULL;
2352 data->count = 0;
2353 data->dim = isl_space_range(isl_map_get_space(map));
2355 if (isl_union_map_foreach_map(data->must_source,
2356 &count_matching_array, data) < 0)
2357 goto error;
2358 if (isl_union_map_foreach_map(data->may_source,
2359 &count_matching_array, data) < 0)
2360 goto error;
2362 data->sink_info = sched_info_alloc(map);
2363 data->source_info = isl_calloc_array(ctx, struct isl_sched_info *,
2364 data->count);
2366 data->accesses = isl_access_info_alloc(isl_map_copy(map),
2367 data->sink_info, &before, data->count);
2368 if (!data->sink_info || (data->count && !data->source_info) ||
2369 !data->accesses)
2370 goto error;
2371 data->accesses->coscheduled = &coscheduled;
2372 data->count = 0;
2373 data->must = 1;
2374 if (isl_union_map_foreach_map(data->must_source,
2375 &collect_matching_array, data) < 0)
2376 goto error;
2377 data->must = 0;
2378 if (isl_union_map_foreach_map(data->may_source,
2379 &collect_matching_array, data) < 0)
2380 goto error;
2382 flow = access_info_compute_flow_core(data->accesses);
2383 data->accesses = NULL;
2385 if (!flow)
2386 goto error;
2388 df->must_no_source = isl_union_map_union(df->must_no_source,
2389 isl_union_map_from_map(isl_flow_get_no_source(flow, 1)));
2390 df->may_no_source = isl_union_map_union(df->may_no_source,
2391 isl_union_map_from_map(isl_flow_get_no_source(flow, 0)));
2393 for (i = 0; i < flow->n_source; ++i) {
2394 isl_union_map *dep;
2395 dep = isl_union_map_from_map(isl_map_copy(flow->dep[i].map));
2396 if (flow->dep[i].must)
2397 df->must_dep = isl_union_map_union(df->must_dep, dep);
2398 else
2399 df->may_dep = isl_union_map_union(df->may_dep, dep);
2402 isl_flow_free(flow);
2404 sched_info_free(data->sink_info);
2405 if (data->source_info) {
2406 for (i = 0; i < data->count; ++i)
2407 sched_info_free(data->source_info[i]);
2408 free(data->source_info);
2410 isl_space_free(data->dim);
2411 isl_map_free(map);
2413 return isl_stat_ok;
2414 error:
2415 isl_access_info_free(data->accesses);
2416 sched_info_free(data->sink_info);
2417 if (data->source_info) {
2418 for (i = 0; i < data->count; ++i)
2419 sched_info_free(data->source_info[i]);
2420 free(data->source_info);
2422 isl_space_free(data->dim);
2423 isl_map_free(map);
2425 return isl_stat_error;
2428 /* Remove the must accesses from the may accesses.
2430 * A must access always trumps a may access, so there is no need
2431 * for a must access to also be considered as a may access. Doing so
2432 * would only cost extra computations only to find out that
2433 * the duplicated may access does not make any difference.
2435 static __isl_give isl_union_access_info *isl_union_access_info_normalize(
2436 __isl_take isl_union_access_info *access)
2438 if (!access)
2439 return NULL;
2440 access->access[isl_access_may_source] =
2441 isl_union_map_subtract(access->access[isl_access_may_source],
2442 isl_union_map_copy(access->access[isl_access_must_source]));
2443 if (!access->access[isl_access_may_source])
2444 return isl_union_access_info_free(access);
2446 return access;
2449 /* Given a description of the "sink" accesses, the "source" accesses and
2450 * a schedule, compute for each instance of a sink access
2451 * and for each element accessed by that instance,
2452 * the possible or definite source accesses that last accessed the
2453 * element accessed by the sink access before this sink access
2454 * in the sense that there is no intermediate definite source access.
2456 * The must_no_source and may_no_source elements of the result
2457 * are subsets of access->sink. The elements must_dep and may_dep
2458 * map domain elements of access->{may,must)_source to
2459 * domain elements of access->sink.
2461 * This function is used when only the schedule map representation
2462 * is available.
2464 * We first prepend the schedule dimensions to the domain
2465 * of the accesses so that we can easily compare their relative order.
2466 * Then we consider each sink access individually in compute_flow.
2468 static __isl_give isl_union_flow *compute_flow_union_map(
2469 __isl_take isl_union_access_info *access)
2471 struct isl_compute_flow_data data;
2472 isl_union_map *sink;
2474 access = isl_union_access_info_align_params(access);
2475 access = isl_union_access_info_introduce_schedule(access);
2476 if (!access)
2477 return NULL;
2479 data.must_source = access->access[isl_access_must_source];
2480 data.may_source = access->access[isl_access_may_source];
2482 sink = access->access[isl_access_sink];
2483 data.flow = isl_union_flow_alloc(isl_union_map_get_space(sink));
2485 if (isl_union_map_foreach_map(sink, &compute_flow, &data) < 0)
2486 goto error;
2488 data.flow = isl_union_flow_drop_schedule(data.flow);
2490 isl_union_access_info_free(access);
2491 return data.flow;
2492 error:
2493 isl_union_access_info_free(access);
2494 isl_union_flow_free(data.flow);
2495 return NULL;
2498 /* A schedule access relation.
2500 * The access relation "access" is of the form [S -> D] -> A,
2501 * where S corresponds to the prefix schedule at "node".
2502 * "must" is only relevant for source accesses and indicates
2503 * whether the access is a must source or a may source.
2505 struct isl_scheduled_access {
2506 isl_map *access;
2507 int must;
2508 isl_schedule_node *node;
2511 /* Data structure for keeping track of individual scheduled sink and source
2512 * accesses when computing dependence analysis based on a schedule tree.
2514 * "n_sink" is the number of used entries in "sink"
2515 * "n_source" is the number of used entries in "source"
2517 * "set_sink", "must" and "node" are only used inside collect_sink_source,
2518 * to keep track of the current node and
2519 * of what extract_sink_source needs to do.
2521 struct isl_compute_flow_schedule_data {
2522 isl_union_access_info *access;
2524 int n_sink;
2525 int n_source;
2527 struct isl_scheduled_access *sink;
2528 struct isl_scheduled_access *source;
2530 int set_sink;
2531 int must;
2532 isl_schedule_node *node;
2535 /* Align the parameters of all sinks with all sources.
2537 * If there are no sinks or no sources, then no alignment is needed.
2539 static void isl_compute_flow_schedule_data_align_params(
2540 struct isl_compute_flow_schedule_data *data)
2542 int i;
2543 isl_space *space;
2545 if (data->n_sink == 0 || data->n_source == 0)
2546 return;
2548 space = isl_map_get_space(data->sink[0].access);
2550 for (i = 1; i < data->n_sink; ++i)
2551 space = isl_space_align_params(space,
2552 isl_map_get_space(data->sink[i].access));
2553 for (i = 0; i < data->n_source; ++i)
2554 space = isl_space_align_params(space,
2555 isl_map_get_space(data->source[i].access));
2557 for (i = 0; i < data->n_sink; ++i)
2558 data->sink[i].access =
2559 isl_map_align_params(data->sink[i].access,
2560 isl_space_copy(space));
2561 for (i = 0; i < data->n_source; ++i)
2562 data->source[i].access =
2563 isl_map_align_params(data->source[i].access,
2564 isl_space_copy(space));
2566 isl_space_free(space);
2569 /* Free all the memory referenced from "data".
2570 * Do not free "data" itself as it may be allocated on the stack.
2572 static void isl_compute_flow_schedule_data_clear(
2573 struct isl_compute_flow_schedule_data *data)
2575 int i;
2577 if (!data->sink)
2578 return;
2580 for (i = 0; i < data->n_sink; ++i) {
2581 isl_map_free(data->sink[i].access);
2582 isl_schedule_node_free(data->sink[i].node);
2585 for (i = 0; i < data->n_source; ++i) {
2586 isl_map_free(data->source[i].access);
2587 isl_schedule_node_free(data->source[i].node);
2590 free(data->sink);
2593 /* isl_schedule_foreach_schedule_node_top_down callback for counting
2594 * (an upper bound on) the number of sinks and sources.
2596 * Sinks and sources are only extracted at leaves of the tree,
2597 * so we skip the node if it is not a leaf.
2598 * Otherwise we increment data->n_sink and data->n_source with
2599 * the number of spaces in the sink and source access domains
2600 * that reach this node.
2602 static isl_bool count_sink_source(__isl_keep isl_schedule_node *node,
2603 void *user)
2605 struct isl_compute_flow_schedule_data *data = user;
2606 isl_union_set *domain;
2607 isl_union_map *umap;
2608 isl_bool r = isl_bool_false;
2610 if (isl_schedule_node_get_type(node) != isl_schedule_node_leaf)
2611 return isl_bool_true;
2613 domain = isl_schedule_node_get_universe_domain(node);
2615 umap = isl_union_map_copy(data->access->access[isl_access_sink]);
2616 umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(domain));
2617 data->n_sink += isl_union_map_n_map(umap);
2618 isl_union_map_free(umap);
2619 if (!umap)
2620 r = isl_bool_error;
2622 umap = isl_union_map_copy(data->access->access[isl_access_must_source]);
2623 umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(domain));
2624 data->n_source += isl_union_map_n_map(umap);
2625 isl_union_map_free(umap);
2626 if (!umap)
2627 r = isl_bool_error;
2629 umap = isl_union_map_copy(data->access->access[isl_access_may_source]);
2630 umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(domain));
2631 data->n_source += isl_union_map_n_map(umap);
2632 isl_union_map_free(umap);
2633 if (!umap)
2634 r = isl_bool_error;
2636 isl_union_set_free(domain);
2638 return r;
2641 /* Add a single scheduled sink or source (depending on data->set_sink)
2642 * with scheduled access relation "map", must property data->must and
2643 * schedule node data->node to the list of sinks or sources.
2645 static isl_stat extract_sink_source(__isl_take isl_map *map, void *user)
2647 struct isl_compute_flow_schedule_data *data = user;
2648 struct isl_scheduled_access *access;
2650 if (data->set_sink)
2651 access = data->sink + data->n_sink++;
2652 else
2653 access = data->source + data->n_source++;
2655 access->access = map;
2656 access->must = data->must;
2657 access->node = isl_schedule_node_copy(data->node);
2659 return isl_stat_ok;
2662 /* isl_schedule_foreach_schedule_node_top_down callback for collecting
2663 * individual scheduled source and sink accesses (taking into account
2664 * the domain of the schedule).
2666 * We only collect accesses at the leaves of the schedule tree.
2667 * We prepend the schedule dimensions at the leaf to the iteration
2668 * domains of the source and sink accesses and then extract
2669 * the individual accesses (per space).
2671 * In particular, if the prefix schedule at the node is of the form
2673 * D -> S
2675 * while the access relations are of the form
2677 * D -> A
2679 * then the updated access relations are of the form
2681 * [S -> D] -> A
2683 * Note that S consists of a single space such that introducing S
2684 * in the access relations does not increase the number of spaces.
2686 static isl_bool collect_sink_source(__isl_keep isl_schedule_node *node,
2687 void *user)
2689 struct isl_compute_flow_schedule_data *data = user;
2690 isl_union_map *prefix;
2691 isl_union_map *umap;
2692 isl_bool r = isl_bool_false;
2694 if (isl_schedule_node_get_type(node) != isl_schedule_node_leaf)
2695 return isl_bool_true;
2697 data->node = node;
2699 prefix = isl_schedule_node_get_prefix_schedule_relation(node);
2700 prefix = isl_union_map_reverse(prefix);
2701 prefix = isl_union_map_range_map(prefix);
2703 data->set_sink = 1;
2704 umap = isl_union_map_copy(data->access->access[isl_access_sink]);
2705 umap = isl_union_map_apply_range(isl_union_map_copy(prefix), umap);
2706 if (isl_union_map_foreach_map(umap, &extract_sink_source, data) < 0)
2707 r = isl_bool_error;
2708 isl_union_map_free(umap);
2710 data->set_sink = 0;
2711 data->must = 1;
2712 umap = isl_union_map_copy(data->access->access[isl_access_must_source]);
2713 umap = isl_union_map_apply_range(isl_union_map_copy(prefix), umap);
2714 if (isl_union_map_foreach_map(umap, &extract_sink_source, data) < 0)
2715 r = isl_bool_error;
2716 isl_union_map_free(umap);
2718 data->set_sink = 0;
2719 data->must = 0;
2720 umap = isl_union_map_copy(data->access->access[isl_access_may_source]);
2721 umap = isl_union_map_apply_range(isl_union_map_copy(prefix), umap);
2722 if (isl_union_map_foreach_map(umap, &extract_sink_source, data) < 0)
2723 r = isl_bool_error;
2724 isl_union_map_free(umap);
2726 isl_union_map_free(prefix);
2728 return r;
2731 /* isl_access_info_compute_flow callback for determining whether
2732 * the shared nesting level and the ordering within that level
2733 * for two scheduled accesses for use in compute_single_flow.
2735 * The tokens passed to this function refer to the leaves
2736 * in the schedule tree where the accesses take place.
2738 * If n is the shared number of loops, then we need to return
2739 * "2 * n + 1" if "first" precedes "second" inside the innermost
2740 * shared loop and "2 * n" otherwise.
2742 * The innermost shared ancestor may be the leaves themselves
2743 * if the accesses take place in the same leaf. Otherwise,
2744 * it is either a set node or a sequence node. Only in the case
2745 * of a sequence node do we consider one access to precede the other.
2747 static int before_node(void *first, void *second)
2749 isl_schedule_node *node1 = first;
2750 isl_schedule_node *node2 = second;
2751 isl_schedule_node *shared;
2752 int depth;
2753 int before = 0;
2755 shared = isl_schedule_node_get_shared_ancestor(node1, node2);
2756 if (!shared)
2757 return -1;
2759 depth = isl_schedule_node_get_schedule_depth(shared);
2760 if (isl_schedule_node_get_type(shared) == isl_schedule_node_sequence) {
2761 int pos1, pos2;
2763 pos1 = isl_schedule_node_get_ancestor_child_position(node1,
2764 shared);
2765 pos2 = isl_schedule_node_get_ancestor_child_position(node2,
2766 shared);
2767 before = pos1 < pos2;
2770 isl_schedule_node_free(shared);
2772 return 2 * depth + before;
2775 /* Check if the given two accesses may be coscheduled.
2776 * If so, return 1. Otherwise return 0.
2778 * Two accesses may only be coscheduled if they appear in the same leaf.
2780 static int coscheduled_node(void *first, void *second)
2782 isl_schedule_node *node1 = first;
2783 isl_schedule_node *node2 = second;
2785 return node1 == node2;
2788 /* Add the scheduled sources from "data" that access
2789 * the same data space as "sink" to "access".
2791 static __isl_give isl_access_info *add_matching_sources(
2792 __isl_take isl_access_info *access, struct isl_scheduled_access *sink,
2793 struct isl_compute_flow_schedule_data *data)
2795 int i;
2796 isl_space *space;
2798 space = isl_space_range(isl_map_get_space(sink->access));
2799 for (i = 0; i < data->n_source; ++i) {
2800 struct isl_scheduled_access *source;
2801 isl_space *source_space;
2802 int eq;
2804 source = &data->source[i];
2805 source_space = isl_map_get_space(source->access);
2806 source_space = isl_space_range(source_space);
2807 eq = isl_space_is_equal(space, source_space);
2808 isl_space_free(source_space);
2810 if (!eq)
2811 continue;
2812 if (eq < 0)
2813 goto error;
2815 access = isl_access_info_add_source(access,
2816 isl_map_copy(source->access), source->must, source->node);
2819 isl_space_free(space);
2820 return access;
2821 error:
2822 isl_space_free(space);
2823 isl_access_info_free(access);
2824 return NULL;
2827 /* Given a scheduled sink access relation "sink", compute the corresponding
2828 * dependences on the sources in "data" and add the computed dependences
2829 * to "uf".
2831 * The dependences computed by access_info_compute_flow_core are of the form
2833 * [S -> I] -> [[S' -> I'] -> A]
2835 * The schedule dimensions are projected out by first currying the range,
2836 * resulting in
2838 * [S -> I] -> [S' -> [I' -> A]]
2840 * and then computing the factor range
2842 * I -> [I' -> A]
2844 static __isl_give isl_union_flow *compute_single_flow(
2845 __isl_take isl_union_flow *uf, struct isl_scheduled_access *sink,
2846 struct isl_compute_flow_schedule_data *data)
2848 int i;
2849 isl_access_info *access;
2850 isl_flow *flow;
2851 isl_map *map;
2853 if (!uf)
2854 return NULL;
2856 access = isl_access_info_alloc(isl_map_copy(sink->access), sink->node,
2857 &before_node, data->n_source);
2858 if (access)
2859 access->coscheduled = &coscheduled_node;
2860 access = add_matching_sources(access, sink, data);
2862 flow = access_info_compute_flow_core(access);
2863 if (!flow)
2864 return isl_union_flow_free(uf);
2866 map = isl_map_domain_factor_range(isl_flow_get_no_source(flow, 1));
2867 uf->must_no_source = isl_union_map_union(uf->must_no_source,
2868 isl_union_map_from_map(map));
2869 map = isl_map_domain_factor_range(isl_flow_get_no_source(flow, 0));
2870 uf->may_no_source = isl_union_map_union(uf->may_no_source,
2871 isl_union_map_from_map(map));
2873 for (i = 0; i < flow->n_source; ++i) {
2874 isl_union_map *dep;
2876 map = isl_map_range_curry(isl_map_copy(flow->dep[i].map));
2877 map = isl_map_factor_range(map);
2878 dep = isl_union_map_from_map(map);
2879 if (flow->dep[i].must)
2880 uf->must_dep = isl_union_map_union(uf->must_dep, dep);
2881 else
2882 uf->may_dep = isl_union_map_union(uf->may_dep, dep);
2885 isl_flow_free(flow);
2887 return uf;
2890 /* Given a description of the "sink" accesses, the "source" accesses and
2891 * a schedule, compute for each instance of a sink access
2892 * and for each element accessed by that instance,
2893 * the possible or definite source accesses that last accessed the
2894 * element accessed by the sink access before this sink access
2895 * in the sense that there is no intermediate definite source access.
2896 * Only consider dependences between statement instances that belong
2897 * to the domain of the schedule.
2899 * The must_no_source and may_no_source elements of the result
2900 * are subsets of access->sink. The elements must_dep and may_dep
2901 * map domain elements of access->{may,must)_source to
2902 * domain elements of access->sink.
2904 * This function is used when a schedule tree representation
2905 * is available.
2907 * We extract the individual scheduled source and sink access relations
2908 * (taking into account the domain of the schedule) and
2909 * then compute dependences for each scheduled sink individually.
2911 static __isl_give isl_union_flow *compute_flow_schedule(
2912 __isl_take isl_union_access_info *access)
2914 struct isl_compute_flow_schedule_data data = { access };
2915 int i, n;
2916 isl_ctx *ctx;
2917 isl_space *space;
2918 isl_union_flow *flow;
2920 ctx = isl_union_access_info_get_ctx(access);
2922 data.n_sink = 0;
2923 data.n_source = 0;
2924 if (isl_schedule_foreach_schedule_node_top_down(access->schedule,
2925 &count_sink_source, &data) < 0)
2926 goto error;
2928 n = data.n_sink + data.n_source;
2929 data.sink = isl_calloc_array(ctx, struct isl_scheduled_access, n);
2930 if (n && !data.sink)
2931 goto error;
2932 data.source = data.sink + data.n_sink;
2934 data.n_sink = 0;
2935 data.n_source = 0;
2936 if (isl_schedule_foreach_schedule_node_top_down(access->schedule,
2937 &collect_sink_source, &data) < 0)
2938 goto error;
2940 space = isl_union_map_get_space(access->access[isl_access_sink]);
2941 flow = isl_union_flow_alloc(space);
2943 isl_compute_flow_schedule_data_align_params(&data);
2945 for (i = 0; i < data.n_sink; ++i)
2946 flow = compute_single_flow(flow, &data.sink[i], &data);
2948 isl_compute_flow_schedule_data_clear(&data);
2950 isl_union_access_info_free(access);
2951 return flow;
2952 error:
2953 isl_union_access_info_free(access);
2954 isl_compute_flow_schedule_data_clear(&data);
2955 return NULL;
2958 /* Given a description of the "sink" accesses, the "source" accesses and
2959 * a schedule, compute for each instance of a sink access
2960 * and for each element accessed by that instance,
2961 * the possible or definite source accesses that last accessed the
2962 * element accessed by the sink access before this sink access
2963 * in the sense that there is no intermediate definite source access.
2965 * The must_no_source and may_no_source elements of the result
2966 * are subsets of access->sink. The elements must_dep and may_dep
2967 * map domain elements of access->{may,must)_source to
2968 * domain elements of access->sink.
2970 * We check whether the schedule is available as a schedule tree
2971 * or a schedule map and call the corresponding function to perform
2972 * the analysis.
2974 __isl_give isl_union_flow *isl_union_access_info_compute_flow(
2975 __isl_take isl_union_access_info *access)
2977 access = isl_union_access_info_normalize(access);
2978 if (!access)
2979 return NULL;
2980 if (access->schedule)
2981 return compute_flow_schedule(access);
2982 else
2983 return compute_flow_union_map(access);
2986 /* Print the information contained in "flow" to "p".
2987 * The information is printed as a YAML document.
2989 __isl_give isl_printer *isl_printer_print_union_flow(
2990 __isl_take isl_printer *p, __isl_keep isl_union_flow *flow)
2992 isl_union_map *umap;
2994 if (!flow)
2995 return isl_printer_free(p);
2997 p = isl_printer_yaml_start_mapping(p);
2998 umap = isl_union_flow_get_full_must_dependence(flow);
2999 p = print_union_map_field(p, "must_dependence", umap);
3000 isl_union_map_free(umap);
3001 umap = isl_union_flow_get_full_may_dependence(flow);
3002 p = print_union_map_field(p, "may_dependence", umap);
3003 isl_union_map_free(umap);
3004 p = print_union_map_field(p, "must_no_source", flow->must_no_source);
3005 umap = isl_union_flow_get_may_no_source(flow);
3006 p = print_union_map_field(p, "may_no_source", umap);
3007 isl_union_map_free(umap);
3008 p = isl_printer_yaml_end_mapping(p);
3010 return p;
3013 /* Return a string representation of the information in "flow".
3014 * The information is printed in flow format.
3016 __isl_give char *isl_union_flow_to_str(__isl_keep isl_union_flow *flow)
3018 isl_printer *p;
3019 char *s;
3021 if (!flow)
3022 return NULL;
3024 p = isl_printer_to_str(isl_union_flow_get_ctx(flow));
3025 p = isl_printer_set_yaml_style(p, ISL_YAML_STYLE_FLOW);
3026 p = isl_printer_print_union_flow(p, flow);
3027 s = isl_printer_get_str(p);
3028 isl_printer_free(p);
3030 return s;
3033 /* Given a collection of "sink" and "source" accesses,
3034 * compute for each iteration of a sink access
3035 * and for each element accessed by that iteration,
3036 * the source access in the list that last accessed the
3037 * element accessed by the sink access before this sink access.
3038 * Each access is given as a map from the loop iterators
3039 * to the array indices.
3040 * The result is a relations between source and sink
3041 * iterations and a subset of the domain of the sink accesses,
3042 * corresponding to those iterations that access an element
3043 * not previously accessed.
3045 * We collect the inputs in an isl_union_access_info object,
3046 * call isl_union_access_info_compute_flow and extract
3047 * the outputs from the result.
3049 int isl_union_map_compute_flow(__isl_take isl_union_map *sink,
3050 __isl_take isl_union_map *must_source,
3051 __isl_take isl_union_map *may_source,
3052 __isl_take isl_union_map *schedule,
3053 __isl_give isl_union_map **must_dep, __isl_give isl_union_map **may_dep,
3054 __isl_give isl_union_map **must_no_source,
3055 __isl_give isl_union_map **may_no_source)
3057 isl_union_access_info *access;
3058 isl_union_flow *flow;
3060 access = isl_union_access_info_from_sink(sink);
3061 access = isl_union_access_info_set_must_source(access, must_source);
3062 access = isl_union_access_info_set_may_source(access, may_source);
3063 access = isl_union_access_info_set_schedule_map(access, schedule);
3064 flow = isl_union_access_info_compute_flow(access);
3066 if (must_dep)
3067 *must_dep = isl_union_flow_get_must_dependence(flow);
3068 if (may_dep)
3069 *may_dep = isl_union_flow_get_non_must_dependence(flow);
3070 if (must_no_source)
3071 *must_no_source = isl_union_flow_get_must_no_source(flow);
3072 if (may_no_source)
3073 *may_no_source = isl_union_flow_get_non_must_no_source(flow);
3075 isl_union_flow_free(flow);
3077 if ((must_dep && !*must_dep) || (may_dep && !*may_dep) ||
3078 (must_no_source && !*must_no_source) ||
3079 (may_no_source && !*may_no_source))
3080 goto error;
3082 return 0;
3083 error:
3084 if (must_dep)
3085 *must_dep = isl_union_map_free(*must_dep);
3086 if (may_dep)
3087 *may_dep = isl_union_map_free(*may_dep);
3088 if (must_no_source)
3089 *must_no_source = isl_union_map_free(*must_no_source);
3090 if (may_no_source)
3091 *may_no_source = isl_union_map_free(*may_no_source);
3092 return -1;