2 * Copyright 2005-2007 Universiteit Leiden
3 * Copyright 2008-2009 Katholieke Universiteit Leuven
4 * Copyright 2010 INRIA Saclay
6 * Use of this software is governed by the GNU LGPLv2.1 license
8 * Written by Sven Verdoolaege, Leiden Institute of Advanced Computer Science,
9 * Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands
10 * and K.U.Leuven, Departement Computerwetenschappen, Celestijnenlaan 200A,
11 * B-3001 Leuven, Belgium
12 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
13 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
20 /* A private structure to keep track of a mapping together with
21 * a user-specified identifier and a boolean indicating whether
22 * the map represents a must or may access/dependence.
24 struct isl_labeled_map
{
30 /* A structure containing the input for dependence analysis:
32 * - n_must + n_may (<= max_source) sources
33 * - a function for determining the relative order of sources and sink
34 * The must sources are placed before the may sources.
36 struct isl_access_info
{
37 struct isl_labeled_map sink
;
38 isl_access_level_before level_before
;
42 struct isl_labeled_map source
[1];
45 /* A structure containing the output of dependence analysis:
46 * - n_source dependences
47 * - a wrapped subset of the sink for which definitely no source could be found
48 * - a wrapped subset of the sink for which possibly no source could be found
51 isl_set
*must_no_source
;
52 isl_set
*may_no_source
;
54 struct isl_labeled_map
*dep
;
57 /* Construct an isl_access_info structure and fill it up with
58 * the given data. The number of sources is set to 0.
60 __isl_give isl_access_info
*isl_access_info_alloc(__isl_take isl_map
*sink
,
61 void *sink_user
, isl_access_level_before fn
, int max_source
)
64 struct isl_access_info
*acc
;
69 ctx
= isl_map_get_ctx(sink
);
70 isl_assert(ctx
, max_source
>= 0, goto error
);
72 acc
= isl_alloc(ctx
, struct isl_access_info
,
73 sizeof(struct isl_access_info
) +
74 (max_source
- 1) * sizeof(struct isl_labeled_map
));
79 acc
->sink
.data
= sink_user
;
80 acc
->level_before
= fn
;
81 acc
->max_source
= max_source
;
91 /* Free the given isl_access_info structure.
93 void isl_access_info_free(__isl_take isl_access_info
*acc
)
99 isl_map_free(acc
->sink
.map
);
100 for (i
= 0; i
< acc
->n_must
+ acc
->n_may
; ++i
)
101 isl_map_free(acc
->source
[i
].map
);
105 /* Add another source to an isl_access_info structure, making
106 * sure the "must" sources are placed before the "may" sources.
107 * This function may be called at most max_source times on a
108 * given isl_access_info structure, with max_source as specified
109 * in the call to isl_access_info_alloc that constructed the structure.
111 __isl_give isl_access_info
*isl_access_info_add_source(
112 __isl_take isl_access_info
*acc
, __isl_take isl_map
*source
,
113 int must
, void *source_user
)
119 ctx
= isl_map_get_ctx(acc
->sink
.map
);
120 isl_assert(ctx
, acc
->n_must
+ acc
->n_may
< acc
->max_source
, goto error
);
124 acc
->source
[acc
->n_must
+ acc
->n_may
] =
125 acc
->source
[acc
->n_must
];
126 acc
->source
[acc
->n_must
].map
= source
;
127 acc
->source
[acc
->n_must
].data
= source_user
;
128 acc
->source
[acc
->n_must
].must
= 1;
131 acc
->source
[acc
->n_must
+ acc
->n_may
].map
= source
;
132 acc
->source
[acc
->n_must
+ acc
->n_may
].data
= source_user
;
133 acc
->source
[acc
->n_must
+ acc
->n_may
].must
= 0;
139 isl_map_free(source
);
140 isl_access_info_free(acc
);
144 /* A temporary structure used while sorting the accesses in an isl_access_info.
146 struct isl_access_sort_info
{
147 struct isl_map
*source_map
;
149 struct isl_access_info
*acc
;
152 /* Return -n, 0 or n (with n a positive value), depending on whether
153 * the source access identified by p1 should be sorted before, together
154 * or after that identified by p2.
156 * If p1 and p2 share a different number of levels with the sink,
157 * then the one with the lowest number of shared levels should be
159 * If they both share no levels, then the order is irrelevant.
160 * Otherwise, if p1 appears before p2, then it should be sorted first.
161 * For more generic initial schedules, it is possible that neither
162 * p1 nor p2 appears before the other, or at least not in any obvious way.
163 * We therefore also check if p2 appears before p1, in which case p2
164 * should be sorted first.
165 * If not, we try to order the two statements based on the description
166 * of the iteration domains. This results in an arbitrary, but fairly
169 static int access_sort_cmp(const void *p1
, const void *p2
)
171 const struct isl_access_sort_info
*i1
, *i2
;
174 i1
= (const struct isl_access_sort_info
*) p1
;
175 i2
= (const struct isl_access_sort_info
*) p2
;
177 level1
= i1
->acc
->level_before(i1
->source_data
, i1
->acc
->sink
.data
);
178 level2
= i2
->acc
->level_before(i2
->source_data
, i2
->acc
->sink
.data
);
180 if (level1
!= level2
|| !level1
)
181 return level1
- level2
;
183 level1
= i1
->acc
->level_before(i1
->source_data
, i2
->source_data
);
187 level2
= i1
->acc
->level_before(i2
->source_data
, i1
->source_data
);
191 h1
= isl_map_get_hash(i1
->source_map
);
192 h2
= isl_map_get_hash(i2
->source_map
);
193 return h1
> h2
? 1 : h1
< h2
? -1 : 0;
196 /* Sort the must source accesses in order of increasing number of shared
197 * levels with the sink access.
198 * Source accesses with the same number of shared levels are sorted
199 * in their textual order.
201 static __isl_give isl_access_info
*isl_access_info_sort_sources(
202 __isl_take isl_access_info
*acc
)
206 struct isl_access_sort_info
*array
;
210 if (acc
->n_must
<= 1)
213 ctx
= isl_map_get_ctx(acc
->sink
.map
);
214 array
= isl_alloc_array(ctx
, struct isl_access_sort_info
, acc
->n_must
);
218 for (i
= 0; i
< acc
->n_must
; ++i
) {
219 array
[i
].source_map
= acc
->source
[i
].map
;
220 array
[i
].source_data
= acc
->source
[i
].data
;
224 qsort(array
, acc
->n_must
, sizeof(struct isl_access_sort_info
),
227 for (i
= 0; i
< acc
->n_must
; ++i
) {
228 acc
->source
[i
].map
= array
[i
].source_map
;
229 acc
->source
[i
].data
= array
[i
].source_data
;
236 isl_access_info_free(acc
);
240 /* Initialize an empty isl_flow structure corresponding to a given
241 * isl_access_info structure.
242 * For each must access, two dependences are created (initialized
243 * to the empty relation), one for the resulting must dependences
244 * and one for the resulting may dependences. May accesses can
245 * only lead to may dependences, so only one dependence is created
247 * This function is private as isl_flow structures are only supposed
248 * to be created by isl_access_info_compute_flow.
250 static __isl_give isl_flow
*isl_flow_alloc(__isl_keep isl_access_info
*acc
)
254 struct isl_flow
*dep
;
259 ctx
= isl_map_get_ctx(acc
->sink
.map
);
260 dep
= isl_calloc_type(ctx
, struct isl_flow
);
264 dep
->dep
= isl_calloc_array(ctx
, struct isl_labeled_map
,
265 2 * acc
->n_must
+ acc
->n_may
);
269 dep
->n_source
= 2 * acc
->n_must
+ acc
->n_may
;
270 for (i
= 0; i
< acc
->n_must
; ++i
) {
272 dim
= isl_dim_join(isl_map_get_dim(acc
->source
[i
].map
),
273 isl_dim_reverse(isl_map_get_dim(acc
->sink
.map
)));
274 dep
->dep
[2 * i
].map
= isl_map_empty(dim
);
275 dep
->dep
[2 * i
+ 1].map
= isl_map_copy(dep
->dep
[2 * i
].map
);
276 dep
->dep
[2 * i
].data
= acc
->source
[i
].data
;
277 dep
->dep
[2 * i
+ 1].data
= acc
->source
[i
].data
;
278 dep
->dep
[2 * i
].must
= 1;
279 dep
->dep
[2 * i
+ 1].must
= 0;
280 if (!dep
->dep
[2 * i
].map
|| !dep
->dep
[2 * i
+ 1].map
)
283 for (i
= acc
->n_must
; i
< acc
->n_must
+ acc
->n_may
; ++i
) {
285 dim
= isl_dim_join(isl_map_get_dim(acc
->source
[i
].map
),
286 isl_dim_reverse(isl_map_get_dim(acc
->sink
.map
)));
287 dep
->dep
[acc
->n_must
+ i
].map
= isl_map_empty(dim
);
288 dep
->dep
[acc
->n_must
+ i
].data
= acc
->source
[i
].data
;
289 dep
->dep
[acc
->n_must
+ i
].must
= 0;
290 if (!dep
->dep
[acc
->n_must
+ i
].map
)
300 /* Iterate over all sources and for each resulting flow dependence
301 * that is not empty, call the user specfied function.
302 * The second argument in this function call identifies the source,
303 * while the third argument correspond to the final argument of
304 * the isl_flow_foreach call.
306 int isl_flow_foreach(__isl_keep isl_flow
*deps
,
307 int (*fn
)(__isl_take isl_map
*dep
, int must
, void *dep_user
, void *user
),
315 for (i
= 0; i
< deps
->n_source
; ++i
) {
316 if (isl_map_plain_is_empty(deps
->dep
[i
].map
))
318 if (fn(isl_map_copy(deps
->dep
[i
].map
), deps
->dep
[i
].must
,
319 deps
->dep
[i
].data
, user
) < 0)
326 /* Return a copy of the subset of the sink for which no source could be found.
328 __isl_give isl_map
*isl_flow_get_no_source(__isl_keep isl_flow
*deps
, int must
)
334 return isl_set_unwrap(isl_set_copy(deps
->must_no_source
));
336 return isl_set_unwrap(isl_set_copy(deps
->may_no_source
));
339 void isl_flow_free(__isl_take isl_flow
*deps
)
345 isl_set_free(deps
->must_no_source
);
346 isl_set_free(deps
->may_no_source
);
348 for (i
= 0; i
< deps
->n_source
; ++i
)
349 isl_map_free(deps
->dep
[i
].map
);
355 /* Return a map that enforces that the domain iteration occurs after
356 * the range iteration at the given level.
357 * If level is odd, then the domain iteration should occur after
358 * the target iteration in their shared level/2 outermost loops.
359 * In this case we simply need to enforce that these outermost
360 * loop iterations are the same.
361 * If level is even, then the loop iterator of the domain should
362 * be greater than the loop iterator of the range at the last
363 * of the level/2 shared loops, i.e., loop level/2 - 1.
365 static __isl_give isl_map
*after_at_level(struct isl_dim
*dim
, int level
)
367 struct isl_basic_map
*bmap
;
370 bmap
= isl_basic_map_equal(dim
, level
/2);
372 bmap
= isl_basic_map_more_at(dim
, level
/2 - 1);
374 return isl_map_from_basic_map(bmap
);
377 /* Compute the last iteration of must source j that precedes the sink
378 * at the given level for sink iterations in set_C.
379 * The subset of set_C for which no such iteration can be found is returned
382 static struct isl_map
*last_source(struct isl_access_info
*acc
,
383 struct isl_set
*set_C
,
384 int j
, int level
, struct isl_set
**empty
)
386 struct isl_map
*read_map
;
387 struct isl_map
*write_map
;
388 struct isl_map
*dep_map
;
389 struct isl_map
*after
;
390 struct isl_map
*result
;
392 read_map
= isl_map_copy(acc
->sink
.map
);
393 write_map
= isl_map_copy(acc
->source
[j
].map
);
394 write_map
= isl_map_reverse(write_map
);
395 dep_map
= isl_map_apply_range(read_map
, write_map
);
396 after
= after_at_level(isl_map_get_dim(dep_map
), level
);
397 dep_map
= isl_map_intersect(dep_map
, after
);
398 result
= isl_map_partial_lexmax(dep_map
, set_C
, empty
);
399 result
= isl_map_reverse(result
);
404 /* For a given mapping between iterations of must source j and iterations
405 * of the sink, compute the last iteration of must source k preceding
406 * the sink at level before_level for any of the sink iterations,
407 * but following the corresponding iteration of must source j at level
410 static struct isl_map
*last_later_source(struct isl_access_info
*acc
,
411 struct isl_map
*old_map
,
412 int j
, int before_level
,
413 int k
, int after_level
,
414 struct isl_set
**empty
)
417 struct isl_set
*set_C
;
418 struct isl_map
*read_map
;
419 struct isl_map
*write_map
;
420 struct isl_map
*dep_map
;
421 struct isl_map
*after_write
;
422 struct isl_map
*before_read
;
423 struct isl_map
*result
;
425 set_C
= isl_map_range(isl_map_copy(old_map
));
426 read_map
= isl_map_copy(acc
->sink
.map
);
427 write_map
= isl_map_copy(acc
->source
[k
].map
);
429 write_map
= isl_map_reverse(write_map
);
430 dep_map
= isl_map_apply_range(read_map
, write_map
);
431 dim
= isl_dim_join(isl_map_get_dim(acc
->source
[k
].map
),
432 isl_dim_reverse(isl_map_get_dim(acc
->source
[j
].map
)));
433 after_write
= after_at_level(dim
, after_level
);
434 after_write
= isl_map_apply_range(after_write
, old_map
);
435 after_write
= isl_map_reverse(after_write
);
436 dep_map
= isl_map_intersect(dep_map
, after_write
);
437 before_read
= after_at_level(isl_map_get_dim(dep_map
), before_level
);
438 dep_map
= isl_map_intersect(dep_map
, before_read
);
439 result
= isl_map_partial_lexmax(dep_map
, set_C
, empty
);
440 result
= isl_map_reverse(result
);
445 /* Given a shared_level between two accesses, return 1 if the
446 * the first can precede the second at the requested target_level.
447 * If the target level is odd, i.e., refers to a statement level
448 * dimension, then first needs to precede second at the requested
449 * level, i.e., shared_level must be equal to target_level.
450 * If the target level is odd, then the two loops should share
451 * at least the requested number of outer loops.
453 static int can_precede_at_level(int shared_level
, int target_level
)
455 if (shared_level
< target_level
)
457 if ((target_level
% 2) && shared_level
> target_level
)
462 /* Given a possible flow dependence temp_rel[j] between source j and the sink
463 * at level sink_level, remove those elements for which
464 * there is an iteration of another source k < j that is closer to the sink.
465 * The flow dependences temp_rel[k] are updated with the improved sources.
466 * Any improved source needs to precede the sink at the same level
467 * and needs to follow source j at the same or a deeper level.
468 * The lower this level, the later the execution date of source k.
469 * We therefore consider lower levels first.
471 * If temp_rel[j] is empty, then there can be no improvement and
472 * we return immediately.
474 static int intermediate_sources(__isl_keep isl_access_info
*acc
,
475 struct isl_map
**temp_rel
, int j
, int sink_level
)
478 int depth
= 2 * isl_map_dim(acc
->source
[j
].map
, isl_dim_in
) + 1;
480 if (isl_map_plain_is_empty(temp_rel
[j
]))
483 for (k
= j
- 1; k
>= 0; --k
) {
485 plevel
= acc
->level_before(acc
->source
[k
].data
, acc
->sink
.data
);
486 if (!can_precede_at_level(plevel
, sink_level
))
489 plevel2
= acc
->level_before(acc
->source
[j
].data
,
490 acc
->source
[k
].data
);
492 for (level
= sink_level
; level
<= depth
; ++level
) {
494 struct isl_set
*trest
;
495 struct isl_map
*copy
;
497 if (!can_precede_at_level(plevel2
, level
))
500 copy
= isl_map_copy(temp_rel
[j
]);
501 T
= last_later_source(acc
, copy
, j
, sink_level
, k
,
503 if (isl_map_plain_is_empty(T
)) {
508 temp_rel
[j
] = isl_map_intersect_range(temp_rel
[j
], trest
);
509 temp_rel
[k
] = isl_map_union_disjoint(temp_rel
[k
], T
);
516 /* Compute all iterations of may source j that precedes the sink at the given
517 * level for sink iterations in set_C.
519 static __isl_give isl_map
*all_sources(__isl_keep isl_access_info
*acc
,
520 __isl_take isl_set
*set_C
, int j
, int level
)
527 read_map
= isl_map_copy(acc
->sink
.map
);
528 read_map
= isl_map_intersect_domain(read_map
, set_C
);
529 write_map
= isl_map_copy(acc
->source
[acc
->n_must
+ j
].map
);
530 write_map
= isl_map_reverse(write_map
);
531 dep_map
= isl_map_apply_range(read_map
, write_map
);
532 after
= after_at_level(isl_map_get_dim(dep_map
), level
);
533 dep_map
= isl_map_intersect(dep_map
, after
);
535 return isl_map_reverse(dep_map
);
538 /* For a given mapping between iterations of must source k and iterations
539 * of the sink, compute the all iteration of may source j preceding
540 * the sink at level before_level for any of the sink iterations,
541 * but following the corresponding iteration of must source k at level
544 static __isl_give isl_map
*all_later_sources(__isl_keep isl_access_info
*acc
,
545 __isl_keep isl_map
*old_map
,
546 int j
, int before_level
, int k
, int after_level
)
553 isl_map
*after_write
;
554 isl_map
*before_read
;
556 set_C
= isl_map_range(isl_map_copy(old_map
));
557 read_map
= isl_map_copy(acc
->sink
.map
);
558 read_map
= isl_map_intersect_domain(read_map
, set_C
);
559 write_map
= isl_map_copy(acc
->source
[acc
->n_must
+ j
].map
);
561 write_map
= isl_map_reverse(write_map
);
562 dep_map
= isl_map_apply_range(read_map
, write_map
);
563 dim
= isl_dim_join(isl_map_get_dim(acc
->source
[acc
->n_must
+ j
].map
),
564 isl_dim_reverse(isl_map_get_dim(acc
->source
[k
].map
)));
565 after_write
= after_at_level(dim
, after_level
);
566 after_write
= isl_map_apply_range(after_write
, old_map
);
567 after_write
= isl_map_reverse(after_write
);
568 dep_map
= isl_map_intersect(dep_map
, after_write
);
569 before_read
= after_at_level(isl_map_get_dim(dep_map
), before_level
);
570 dep_map
= isl_map_intersect(dep_map
, before_read
);
571 return isl_map_reverse(dep_map
);
574 /* Given the must and may dependence relations for the must accesses
575 * for level sink_level, check if there are any accesses of may access j
576 * that occur in between and return their union.
577 * If some of these accesses are intermediate with respect to
578 * (previously thought to be) must dependences, then these
579 * must dependences are turned into may dependences.
581 static __isl_give isl_map
*all_intermediate_sources(
582 __isl_keep isl_access_info
*acc
, __isl_take isl_map
*map
,
583 struct isl_map
**must_rel
, struct isl_map
**may_rel
,
584 int j
, int sink_level
)
587 int depth
= 2 * isl_map_dim(acc
->source
[acc
->n_must
+ j
].map
,
590 for (k
= 0; k
< acc
->n_must
; ++k
) {
593 if (isl_map_plain_is_empty(may_rel
[k
]) &&
594 isl_map_plain_is_empty(must_rel
[k
]))
597 plevel
= acc
->level_before(acc
->source
[k
].data
,
598 acc
->source
[acc
->n_must
+ j
].data
);
600 for (level
= sink_level
; level
<= depth
; ++level
) {
605 if (!can_precede_at_level(plevel
, level
))
608 copy
= isl_map_copy(may_rel
[k
]);
609 T
= all_later_sources(acc
, copy
, j
, sink_level
, k
, level
);
610 map
= isl_map_union(map
, T
);
612 copy
= isl_map_copy(must_rel
[k
]);
613 T
= all_later_sources(acc
, copy
, j
, sink_level
, k
, level
);
614 ran
= isl_map_range(isl_map_copy(T
));
615 map
= isl_map_union(map
, T
);
616 may_rel
[k
] = isl_map_union_disjoint(may_rel
[k
],
617 isl_map_intersect_range(isl_map_copy(must_rel
[k
]),
619 T
= isl_map_from_domain_and_range(
621 isl_dim_domain(isl_map_get_dim(must_rel
[k
]))),
623 must_rel
[k
] = isl_map_subtract(must_rel
[k
], T
);
630 /* Compute dependences for the case where all accesses are "may"
631 * accesses, which boils down to computing memory based dependences.
632 * The generic algorithm would also work in this case, but it would
633 * be overkill to use it.
635 static __isl_give isl_flow
*compute_mem_based_dependences(
636 __isl_take isl_access_info
*acc
)
643 res
= isl_flow_alloc(acc
);
647 mustdo
= isl_map_domain(isl_map_copy(acc
->sink
.map
));
648 maydo
= isl_set_copy(mustdo
);
650 for (i
= 0; i
< acc
->n_may
; ++i
) {
657 plevel
= acc
->level_before(acc
->source
[i
].data
, acc
->sink
.data
);
658 is_before
= plevel
& 1;
661 dim
= isl_map_get_dim(res
->dep
[i
].map
);
663 before
= isl_map_lex_le_first(dim
, plevel
);
665 before
= isl_map_lex_lt_first(dim
, plevel
);
666 dep
= isl_map_apply_range(isl_map_copy(acc
->source
[i
].map
),
667 isl_map_reverse(isl_map_copy(acc
->sink
.map
)));
668 dep
= isl_map_intersect(dep
, before
);
669 mustdo
= isl_set_subtract(mustdo
,
670 isl_map_range(isl_map_copy(dep
)));
671 res
->dep
[i
].map
= isl_map_union(res
->dep
[i
].map
, dep
);
674 res
->may_no_source
= isl_set_subtract(maydo
, isl_set_copy(mustdo
));
675 res
->must_no_source
= mustdo
;
677 isl_access_info_free(acc
);
681 isl_access_info_free(acc
);
685 /* Compute dependences for the case where there is at least one
688 * The core algorithm considers all levels in which a source may precede
689 * the sink, where a level may either be a statement level or a loop level.
690 * The outermost statement level is 1, the first loop level is 2, etc...
691 * The algorithm basically does the following:
692 * for all levels l of the read access from innermost to outermost
693 * for all sources w that may precede the sink access at that level
694 * compute the last iteration of the source that precedes the sink access
696 * add result to possible last accesses at level l of source w
697 * for all sources w2 that we haven't considered yet at this level that may
698 * also precede the sink access
699 * for all levels l2 of w from l to innermost
700 * for all possible last accesses dep of w at l
701 * compute last iteration of w2 between the source and sink
703 * add result to possible last accesses at level l of write w2
704 * and replace possible last accesses dep by the remainder
707 * The above algorithm is applied to the must access. During the course
708 * of the algorithm, we keep track of sink iterations that still
709 * need to be considered. These iterations are split into those that
710 * haven't been matched to any source access (mustdo) and those that have only
711 * been matched to may accesses (maydo).
712 * At the end of each level, we also consider the may accesses.
713 * In particular, we consider may accesses that precede the remaining
714 * sink iterations, moving elements from mustdo to maydo when appropriate,
715 * and may accesses that occur between a must source and a sink of any
716 * dependences found at the current level, turning must dependences into
717 * may dependences when appropriate.
720 static __isl_give isl_flow
*compute_val_based_dependences(
721 __isl_take isl_access_info
*acc
)
725 isl_set
*mustdo
= NULL
;
726 isl_set
*maydo
= NULL
;
729 isl_map
**must_rel
= NULL
;
730 isl_map
**may_rel
= NULL
;
732 acc
= isl_access_info_sort_sources(acc
);
736 res
= isl_flow_alloc(acc
);
739 ctx
= isl_map_get_ctx(acc
->sink
.map
);
741 depth
= 2 * isl_map_dim(acc
->sink
.map
, isl_dim_in
) + 1;
742 mustdo
= isl_map_domain(isl_map_copy(acc
->sink
.map
));
743 maydo
= isl_set_empty_like(mustdo
);
744 if (!mustdo
|| !maydo
)
746 if (isl_set_plain_is_empty(mustdo
))
749 must_rel
= isl_alloc_array(ctx
, struct isl_map
*, acc
->n_must
);
750 may_rel
= isl_alloc_array(ctx
, struct isl_map
*, acc
->n_must
);
751 if (!must_rel
|| !may_rel
)
754 for (level
= depth
; level
>= 1; --level
) {
755 for (j
= acc
->n_must
-1; j
>=0; --j
) {
756 must_rel
[j
] = isl_map_empty_like(res
->dep
[j
].map
);
757 may_rel
[j
] = isl_map_copy(must_rel
[j
]);
760 for (j
= acc
->n_must
- 1; j
>= 0; --j
) {
762 struct isl_set
*rest
;
765 plevel
= acc
->level_before(acc
->source
[j
].data
,
767 if (!can_precede_at_level(plevel
, level
))
770 T
= last_source(acc
, mustdo
, j
, level
, &rest
);
771 must_rel
[j
] = isl_map_union_disjoint(must_rel
[j
], T
);
774 intermediate_sources(acc
, must_rel
, j
, level
);
776 T
= last_source(acc
, maydo
, j
, level
, &rest
);
777 may_rel
[j
] = isl_map_union_disjoint(may_rel
[j
], T
);
780 intermediate_sources(acc
, may_rel
, j
, level
);
782 if (isl_set_plain_is_empty(mustdo
) &&
783 isl_set_plain_is_empty(maydo
))
786 for (j
= j
- 1; j
>= 0; --j
) {
789 plevel
= acc
->level_before(acc
->source
[j
].data
,
791 if (!can_precede_at_level(plevel
, level
))
794 intermediate_sources(acc
, must_rel
, j
, level
);
795 intermediate_sources(acc
, may_rel
, j
, level
);
798 for (j
= 0; j
< acc
->n_may
; ++j
) {
803 plevel
= acc
->level_before(acc
->source
[acc
->n_must
+ j
].data
,
805 if (!can_precede_at_level(plevel
, level
))
808 T
= all_sources(acc
, isl_set_copy(maydo
), j
, level
);
809 res
->dep
[2 * acc
->n_must
+ j
].map
=
810 isl_map_union(res
->dep
[2 * acc
->n_must
+ j
].map
, T
);
811 T
= all_sources(acc
, isl_set_copy(mustdo
), j
, level
);
812 ran
= isl_map_range(isl_map_copy(T
));
813 res
->dep
[2 * acc
->n_must
+ j
].map
=
814 isl_map_union(res
->dep
[2 * acc
->n_must
+ j
].map
, T
);
815 mustdo
= isl_set_subtract(mustdo
, isl_set_copy(ran
));
816 maydo
= isl_set_union_disjoint(maydo
, ran
);
818 T
= res
->dep
[2 * acc
->n_must
+ j
].map
;
819 T
= all_intermediate_sources(acc
, T
, must_rel
, may_rel
,
821 res
->dep
[2 * acc
->n_must
+ j
].map
= T
;
824 for (j
= acc
->n_must
- 1; j
>= 0; --j
) {
825 res
->dep
[2 * j
].map
=
826 isl_map_union_disjoint(res
->dep
[2 * j
].map
,
828 res
->dep
[2 * j
+ 1].map
=
829 isl_map_union_disjoint(res
->dep
[2 * j
+ 1].map
,
833 if (isl_set_plain_is_empty(mustdo
) &&
834 isl_set_plain_is_empty(maydo
))
841 res
->must_no_source
= mustdo
;
842 res
->may_no_source
= maydo
;
843 isl_access_info_free(acc
);
846 isl_access_info_free(acc
);
848 isl_set_free(mustdo
);
855 /* Given a "sink" access, a list of n "source" accesses,
856 * compute for each iteration of the sink access
857 * and for each element accessed by that iteration,
858 * the source access in the list that last accessed the
859 * element accessed by the sink access before this sink access.
860 * Each access is given as a map from the loop iterators
861 * to the array indices.
862 * The result is a list of n relations between source and sink
863 * iterations and a subset of the domain of the sink access,
864 * corresponding to those iterations that access an element
865 * not previously accessed.
867 * To deal with multi-valued sink access relations, the sink iteration
868 * domain is first extended with dimensions that correspond to the data
869 * space. After the computation is finished, these extra dimensions are
870 * projected out again.
872 __isl_give isl_flow
*isl_access_info_compute_flow(__isl_take isl_access_info
*acc
)
875 struct isl_flow
*res
;
876 isl_map
*domain_map
= NULL
;
881 domain_map
= isl_map_domain_map(isl_map_copy(acc
->sink
.map
));
882 acc
->sink
.map
= isl_map_range_map(acc
->sink
.map
);
886 if (acc
->n_must
== 0)
887 res
= compute_mem_based_dependences(acc
);
889 res
= compute_val_based_dependences(acc
);
893 for (j
= 0; j
< res
->n_source
; ++j
) {
894 res
->dep
[j
].map
= isl_map_apply_range(res
->dep
[j
].map
,
895 isl_map_copy(domain_map
));
896 if (!res
->dep
[j
].map
)
899 if (!res
->must_no_source
|| !res
->may_no_source
)
902 isl_map_free(domain_map
);
905 isl_map_free(domain_map
);
906 isl_access_info_free(acc
);
909 isl_map_free(domain_map
);
915 /* Keep track of some information about a schedule for a given
916 * access. In particular, keep track of which dimensions
917 * have a constant value and of the actual constant values.
919 struct isl_sched_info
{
924 static void sched_info_free(__isl_take
struct isl_sched_info
*info
)
928 isl_vec_free(info
->cst
);
933 /* Extract information on the constant dimensions of the schedule
934 * for a given access. The "map" is of the form
938 * with S the schedule domain, D the iteration domain and A the data domain.
940 static __isl_give
struct isl_sched_info
*sched_info_alloc(
941 __isl_keep isl_map
*map
)
945 struct isl_sched_info
*info
;
951 dim
= isl_dim_unwrap(isl_dim_domain(isl_map_get_dim(map
)));
954 n
= isl_dim_size(dim
, isl_dim_in
);
957 ctx
= isl_map_get_ctx(map
);
958 info
= isl_alloc_type(ctx
, struct isl_sched_info
);
961 info
->is_cst
= isl_alloc_array(ctx
, int, n
);
962 info
->cst
= isl_vec_alloc(ctx
, n
);
963 if (!info
->is_cst
|| !info
->cst
)
966 for (i
= 0; i
< n
; ++i
)
967 info
->is_cst
[i
] = isl_map_plain_is_fixed(map
, isl_dim_in
, i
,
972 sched_info_free(info
);
976 struct isl_compute_flow_data
{
977 isl_union_map
*must_source
;
978 isl_union_map
*may_source
;
979 isl_union_map
*must_dep
;
980 isl_union_map
*may_dep
;
981 isl_union_map
*must_no_source
;
982 isl_union_map
*may_no_source
;
987 struct isl_sched_info
*sink_info
;
988 struct isl_sched_info
**source_info
;
989 isl_access_info
*accesses
;
992 static int count_matching_array(__isl_take isl_map
*map
, void *user
)
996 struct isl_compute_flow_data
*data
;
998 data
= (struct isl_compute_flow_data
*)user
;
1000 dim
= isl_dim_range(isl_map_get_dim(map
));
1002 eq
= isl_dim_equal(dim
, data
->dim
);
1015 static int collect_matching_array(__isl_take isl_map
*map
, void *user
)
1019 struct isl_sched_info
*info
;
1020 struct isl_compute_flow_data
*data
;
1022 data
= (struct isl_compute_flow_data
*)user
;
1024 dim
= isl_dim_range(isl_map_get_dim(map
));
1026 eq
= isl_dim_equal(dim
, data
->dim
);
1037 info
= sched_info_alloc(map
);
1038 data
->source_info
[data
->count
] = info
;
1040 data
->accesses
= isl_access_info_add_source(data
->accesses
,
1041 map
, data
->must
, info
);
1051 /* Determine the shared nesting level and the "textual order" of
1052 * the given accesses.
1054 * We first determine the minimal schedule dimension for both accesses.
1056 * If among those dimensions, we can find one where both have a fixed
1057 * value and if moreover those values are different, then the previous
1058 * dimension is the last shared nesting level and the textual order
1059 * is determined based on the order of the fixed values.
1060 * If no such fixed values can be found, then we set the shared
1061 * nesting level to the minimal schedule dimension, with no textual ordering.
1063 static int before(void *first
, void *second
)
1065 struct isl_sched_info
*info1
= first
;
1066 struct isl_sched_info
*info2
= second
;
1070 n1
= info1
->cst
->size
;
1071 n2
= info2
->cst
->size
;
1076 for (i
= 0; i
< n1
; ++i
) {
1077 if (!info1
->is_cst
[i
])
1079 if (!info2
->is_cst
[i
])
1081 if (isl_int_eq(info1
->cst
->el
[i
], info2
->cst
->el
[i
]))
1083 return 2 * i
+ isl_int_lt(info1
->cst
->el
[i
], info2
->cst
->el
[i
]);
1089 /* Given a sink access, look for all the source accesses that access
1090 * the same array and perform dataflow analysis on them using
1091 * isl_access_info_compute_flow.
1093 static int compute_flow(__isl_take isl_map
*map
, void *user
)
1097 struct isl_compute_flow_data
*data
;
1100 data
= (struct isl_compute_flow_data
*)user
;
1102 ctx
= isl_map_get_ctx(map
);
1104 data
->accesses
= NULL
;
1105 data
->sink_info
= NULL
;
1106 data
->source_info
= NULL
;
1108 data
->dim
= isl_dim_range(isl_map_get_dim(map
));
1110 if (isl_union_map_foreach_map(data
->must_source
,
1111 &count_matching_array
, data
) < 0)
1113 if (isl_union_map_foreach_map(data
->may_source
,
1114 &count_matching_array
, data
) < 0)
1117 data
->sink_info
= sched_info_alloc(map
);
1118 data
->source_info
= isl_calloc_array(ctx
, struct isl_sched_info
*,
1121 data
->accesses
= isl_access_info_alloc(isl_map_copy(map
),
1122 data
->sink_info
, &before
, data
->count
);
1123 if (!data
->sink_info
|| !data
->source_info
|| !data
->accesses
)
1127 if (isl_union_map_foreach_map(data
->must_source
,
1128 &collect_matching_array
, data
) < 0)
1131 if (isl_union_map_foreach_map(data
->may_source
,
1132 &collect_matching_array
, data
) < 0)
1135 flow
= isl_access_info_compute_flow(data
->accesses
);
1136 data
->accesses
= NULL
;
1141 data
->must_no_source
= isl_union_map_union(data
->must_no_source
,
1142 isl_union_map_from_map(isl_flow_get_no_source(flow
, 1)));
1143 data
->may_no_source
= isl_union_map_union(data
->may_no_source
,
1144 isl_union_map_from_map(isl_flow_get_no_source(flow
, 0)));
1146 for (i
= 0; i
< flow
->n_source
; ++i
) {
1148 dep
= isl_union_map_from_map(isl_map_copy(flow
->dep
[i
].map
));
1149 if (flow
->dep
[i
].must
)
1150 data
->must_dep
= isl_union_map_union(data
->must_dep
, dep
);
1152 data
->may_dep
= isl_union_map_union(data
->may_dep
, dep
);
1155 isl_flow_free(flow
);
1157 sched_info_free(data
->sink_info
);
1158 if (data
->source_info
) {
1159 for (i
= 0; i
< data
->count
; ++i
)
1160 sched_info_free(data
->source_info
[i
]);
1161 free(data
->source_info
);
1163 isl_dim_free(data
->dim
);
1168 isl_access_info_free(data
->accesses
);
1169 sched_info_free(data
->sink_info
);
1170 if (data
->source_info
) {
1171 for (i
= 0; i
< data
->count
; ++i
)
1172 sched_info_free(data
->source_info
[i
]);
1173 free(data
->source_info
);
1175 isl_dim_free(data
->dim
);
1181 /* Given a collection of "sink" and "source" accesses,
1182 * compute for each iteration of a sink access
1183 * and for each element accessed by that iteration,
1184 * the source access in the list that last accessed the
1185 * element accessed by the sink access before this sink access.
1186 * Each access is given as a map from the loop iterators
1187 * to the array indices.
1188 * The result is a relations between source and sink
1189 * iterations and a subset of the domain of the sink accesses,
1190 * corresponding to those iterations that access an element
1191 * not previously accessed.
1193 * We first prepend the schedule dimensions to the domain
1194 * of the accesses so that we can easily compare their relative order.
1195 * Then we consider each sink access individually in compute_flow.
1197 int isl_union_map_compute_flow(__isl_take isl_union_map
*sink
,
1198 __isl_take isl_union_map
*must_source
,
1199 __isl_take isl_union_map
*may_source
,
1200 __isl_take isl_union_map
*schedule
,
1201 __isl_give isl_union_map
**must_dep
, __isl_give isl_union_map
**may_dep
,
1202 __isl_give isl_union_map
**must_no_source
,
1203 __isl_give isl_union_map
**may_no_source
)
1206 isl_union_map
*range_map
= NULL
;
1207 struct isl_compute_flow_data data
;
1209 sink
= isl_union_map_align_params(sink
,
1210 isl_union_map_get_dim(must_source
));
1211 sink
= isl_union_map_align_params(sink
,
1212 isl_union_map_get_dim(may_source
));
1213 sink
= isl_union_map_align_params(sink
,
1214 isl_union_map_get_dim(schedule
));
1215 dim
= isl_union_map_get_dim(sink
);
1216 must_source
= isl_union_map_align_params(must_source
, isl_dim_copy(dim
));
1217 may_source
= isl_union_map_align_params(may_source
, isl_dim_copy(dim
));
1218 schedule
= isl_union_map_align_params(schedule
, isl_dim_copy(dim
));
1220 schedule
= isl_union_map_reverse(schedule
);
1221 range_map
= isl_union_map_range_map(schedule
);
1222 schedule
= isl_union_map_reverse(isl_union_map_copy(range_map
));
1223 sink
= isl_union_map_apply_domain(sink
, isl_union_map_copy(schedule
));
1224 must_source
= isl_union_map_apply_domain(must_source
,
1225 isl_union_map_copy(schedule
));
1226 may_source
= isl_union_map_apply_domain(may_source
, schedule
);
1228 data
.must_source
= must_source
;
1229 data
.may_source
= may_source
;
1230 data
.must_dep
= must_dep
?
1231 isl_union_map_empty(isl_dim_copy(dim
)) : NULL
;
1232 data
.may_dep
= may_dep
? isl_union_map_empty(isl_dim_copy(dim
)) : NULL
;
1233 data
.must_no_source
= must_no_source
?
1234 isl_union_map_empty(isl_dim_copy(dim
)) : NULL
;
1235 data
.may_no_source
= may_no_source
?
1236 isl_union_map_empty(isl_dim_copy(dim
)) : NULL
;
1240 if (isl_union_map_foreach_map(sink
, &compute_flow
, &data
) < 0)
1243 isl_union_map_free(sink
);
1244 isl_union_map_free(must_source
);
1245 isl_union_map_free(may_source
);
1248 data
.must_dep
= isl_union_map_apply_domain(data
.must_dep
,
1249 isl_union_map_copy(range_map
));
1250 data
.must_dep
= isl_union_map_apply_range(data
.must_dep
,
1251 isl_union_map_copy(range_map
));
1252 *must_dep
= data
.must_dep
;
1255 data
.may_dep
= isl_union_map_apply_domain(data
.may_dep
,
1256 isl_union_map_copy(range_map
));
1257 data
.may_dep
= isl_union_map_apply_range(data
.may_dep
,
1258 isl_union_map_copy(range_map
));
1259 *may_dep
= data
.may_dep
;
1261 if (must_no_source
) {
1262 data
.must_no_source
= isl_union_map_apply_domain(
1263 data
.must_no_source
, isl_union_map_copy(range_map
));
1264 *must_no_source
= data
.must_no_source
;
1266 if (may_no_source
) {
1267 data
.may_no_source
= isl_union_map_apply_domain(
1268 data
.may_no_source
, isl_union_map_copy(range_map
));
1269 *may_no_source
= data
.may_no_source
;
1272 isl_union_map_free(range_map
);
1276 isl_union_map_free(range_map
);
1277 isl_union_map_free(sink
);
1278 isl_union_map_free(must_source
);
1279 isl_union_map_free(may_source
);
1280 isl_union_map_free(data
.must_dep
);
1281 isl_union_map_free(data
.may_dep
);
1282 isl_union_map_free(data
.must_no_source
);
1283 isl_union_map_free(data
.may_no_source
);
1290 *must_no_source
= NULL
;
1292 *may_no_source
= NULL
;