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 isl_ctx
*isl_access_info_get_ctx(__isl_keep isl_access_info
*acc
)
107 return acc
? isl_map_get_ctx(acc
->sink
.map
) : NULL
;
110 /* Add another source to an isl_access_info structure, making
111 * sure the "must" sources are placed before the "may" sources.
112 * This function may be called at most max_source times on a
113 * given isl_access_info structure, with max_source as specified
114 * in the call to isl_access_info_alloc that constructed the structure.
116 __isl_give isl_access_info
*isl_access_info_add_source(
117 __isl_take isl_access_info
*acc
, __isl_take isl_map
*source
,
118 int must
, void *source_user
)
124 ctx
= isl_map_get_ctx(acc
->sink
.map
);
125 isl_assert(ctx
, acc
->n_must
+ acc
->n_may
< acc
->max_source
, goto error
);
129 acc
->source
[acc
->n_must
+ acc
->n_may
] =
130 acc
->source
[acc
->n_must
];
131 acc
->source
[acc
->n_must
].map
= source
;
132 acc
->source
[acc
->n_must
].data
= source_user
;
133 acc
->source
[acc
->n_must
].must
= 1;
136 acc
->source
[acc
->n_must
+ acc
->n_may
].map
= source
;
137 acc
->source
[acc
->n_must
+ acc
->n_may
].data
= source_user
;
138 acc
->source
[acc
->n_must
+ acc
->n_may
].must
= 0;
144 isl_map_free(source
);
145 isl_access_info_free(acc
);
149 /* A temporary structure used while sorting the accesses in an isl_access_info.
151 struct isl_access_sort_info
{
152 struct isl_map
*source_map
;
154 struct isl_access_info
*acc
;
157 /* Return -n, 0 or n (with n a positive value), depending on whether
158 * the source access identified by p1 should be sorted before, together
159 * or after that identified by p2.
161 * If p1 and p2 share a different number of levels with the sink,
162 * then the one with the lowest number of shared levels should be
164 * If they both share no levels, then the order is irrelevant.
165 * Otherwise, if p1 appears before p2, then it should be sorted first.
166 * For more generic initial schedules, it is possible that neither
167 * p1 nor p2 appears before the other, or at least not in any obvious way.
168 * We therefore also check if p2 appears before p1, in which case p2
169 * should be sorted first.
170 * If not, we try to order the two statements based on the description
171 * of the iteration domains. This results in an arbitrary, but fairly
174 static int access_sort_cmp(const void *p1
, const void *p2
)
176 const struct isl_access_sort_info
*i1
, *i2
;
179 i1
= (const struct isl_access_sort_info
*) p1
;
180 i2
= (const struct isl_access_sort_info
*) p2
;
182 level1
= i1
->acc
->level_before(i1
->source_data
, i1
->acc
->sink
.data
);
183 level2
= i2
->acc
->level_before(i2
->source_data
, i2
->acc
->sink
.data
);
185 if (level1
!= level2
|| !level1
)
186 return level1
- level2
;
188 level1
= i1
->acc
->level_before(i1
->source_data
, i2
->source_data
);
192 level2
= i1
->acc
->level_before(i2
->source_data
, i1
->source_data
);
196 h1
= isl_map_get_hash(i1
->source_map
);
197 h2
= isl_map_get_hash(i2
->source_map
);
198 return h1
> h2
? 1 : h1
< h2
? -1 : 0;
201 /* Sort the must source accesses in order of increasing number of shared
202 * levels with the sink access.
203 * Source accesses with the same number of shared levels are sorted
204 * in their textual order.
206 static __isl_give isl_access_info
*isl_access_info_sort_sources(
207 __isl_take isl_access_info
*acc
)
211 struct isl_access_sort_info
*array
;
215 if (acc
->n_must
<= 1)
218 ctx
= isl_map_get_ctx(acc
->sink
.map
);
219 array
= isl_alloc_array(ctx
, struct isl_access_sort_info
, acc
->n_must
);
223 for (i
= 0; i
< acc
->n_must
; ++i
) {
224 array
[i
].source_map
= acc
->source
[i
].map
;
225 array
[i
].source_data
= acc
->source
[i
].data
;
229 qsort(array
, acc
->n_must
, sizeof(struct isl_access_sort_info
),
232 for (i
= 0; i
< acc
->n_must
; ++i
) {
233 acc
->source
[i
].map
= array
[i
].source_map
;
234 acc
->source
[i
].data
= array
[i
].source_data
;
241 isl_access_info_free(acc
);
245 /* Align the parameters of the two spaces if needed and then call
248 static __isl_give isl_space
*space_align_and_join(__isl_take isl_space
*left
,
249 __isl_take isl_space
*right
)
251 if (isl_space_match(left
, isl_dim_param
, right
, isl_dim_param
))
252 return isl_space_join(left
, right
);
254 left
= isl_space_align_params(left
, isl_space_copy(right
));
255 right
= isl_space_align_params(right
, isl_space_copy(left
));
256 return isl_space_join(left
, right
);
259 /* Initialize an empty isl_flow structure corresponding to a given
260 * isl_access_info structure.
261 * For each must access, two dependences are created (initialized
262 * to the empty relation), one for the resulting must dependences
263 * and one for the resulting may dependences. May accesses can
264 * only lead to may dependences, so only one dependence is created
266 * This function is private as isl_flow structures are only supposed
267 * to be created by isl_access_info_compute_flow.
269 static __isl_give isl_flow
*isl_flow_alloc(__isl_keep isl_access_info
*acc
)
273 struct isl_flow
*dep
;
278 ctx
= isl_map_get_ctx(acc
->sink
.map
);
279 dep
= isl_calloc_type(ctx
, struct isl_flow
);
283 dep
->dep
= isl_calloc_array(ctx
, struct isl_labeled_map
,
284 2 * acc
->n_must
+ acc
->n_may
);
288 dep
->n_source
= 2 * acc
->n_must
+ acc
->n_may
;
289 for (i
= 0; i
< acc
->n_must
; ++i
) {
291 dim
= space_align_and_join(
292 isl_map_get_space(acc
->source
[i
].map
),
293 isl_space_reverse(isl_map_get_space(acc
->sink
.map
)));
294 dep
->dep
[2 * i
].map
= isl_map_empty(dim
);
295 dep
->dep
[2 * i
+ 1].map
= isl_map_copy(dep
->dep
[2 * i
].map
);
296 dep
->dep
[2 * i
].data
= acc
->source
[i
].data
;
297 dep
->dep
[2 * i
+ 1].data
= acc
->source
[i
].data
;
298 dep
->dep
[2 * i
].must
= 1;
299 dep
->dep
[2 * i
+ 1].must
= 0;
300 if (!dep
->dep
[2 * i
].map
|| !dep
->dep
[2 * i
+ 1].map
)
303 for (i
= acc
->n_must
; i
< acc
->n_must
+ acc
->n_may
; ++i
) {
305 dim
= isl_space_join(isl_map_get_space(acc
->source
[i
].map
),
306 isl_space_reverse(isl_map_get_space(acc
->sink
.map
)));
307 dep
->dep
[acc
->n_must
+ i
].map
= isl_map_empty(dim
);
308 dep
->dep
[acc
->n_must
+ i
].data
= acc
->source
[i
].data
;
309 dep
->dep
[acc
->n_must
+ i
].must
= 0;
310 if (!dep
->dep
[acc
->n_must
+ i
].map
)
320 /* Iterate over all sources and for each resulting flow dependence
321 * that is not empty, call the user specfied function.
322 * The second argument in this function call identifies the source,
323 * while the third argument correspond to the final argument of
324 * the isl_flow_foreach call.
326 int isl_flow_foreach(__isl_keep isl_flow
*deps
,
327 int (*fn
)(__isl_take isl_map
*dep
, int must
, void *dep_user
, void *user
),
335 for (i
= 0; i
< deps
->n_source
; ++i
) {
336 if (isl_map_plain_is_empty(deps
->dep
[i
].map
))
338 if (fn(isl_map_copy(deps
->dep
[i
].map
), deps
->dep
[i
].must
,
339 deps
->dep
[i
].data
, user
) < 0)
346 /* Return a copy of the subset of the sink for which no source could be found.
348 __isl_give isl_map
*isl_flow_get_no_source(__isl_keep isl_flow
*deps
, int must
)
354 return isl_set_unwrap(isl_set_copy(deps
->must_no_source
));
356 return isl_set_unwrap(isl_set_copy(deps
->may_no_source
));
359 void isl_flow_free(__isl_take isl_flow
*deps
)
365 isl_set_free(deps
->must_no_source
);
366 isl_set_free(deps
->may_no_source
);
368 for (i
= 0; i
< deps
->n_source
; ++i
)
369 isl_map_free(deps
->dep
[i
].map
);
375 isl_ctx
*isl_flow_get_ctx(__isl_keep isl_flow
*deps
)
377 return deps
? isl_set_get_ctx(deps
->must_no_source
) : NULL
;
380 /* Return a map that enforces that the domain iteration occurs after
381 * the range iteration at the given level.
382 * If level is odd, then the domain iteration should occur after
383 * the target iteration in their shared level/2 outermost loops.
384 * In this case we simply need to enforce that these outermost
385 * loop iterations are the same.
386 * If level is even, then the loop iterator of the domain should
387 * be greater than the loop iterator of the range at the last
388 * of the level/2 shared loops, i.e., loop level/2 - 1.
390 static __isl_give isl_map
*after_at_level(__isl_take isl_space
*dim
, int level
)
392 struct isl_basic_map
*bmap
;
395 bmap
= isl_basic_map_equal(dim
, level
/2);
397 bmap
= isl_basic_map_more_at(dim
, level
/2 - 1);
399 return isl_map_from_basic_map(bmap
);
402 /* Compute the last iteration of must source j that precedes the sink
403 * at the given level for sink iterations in set_C.
404 * The subset of set_C for which no such iteration can be found is returned
407 static struct isl_map
*last_source(struct isl_access_info
*acc
,
408 struct isl_set
*set_C
,
409 int j
, int level
, struct isl_set
**empty
)
411 struct isl_map
*read_map
;
412 struct isl_map
*write_map
;
413 struct isl_map
*dep_map
;
414 struct isl_map
*after
;
415 struct isl_map
*result
;
417 read_map
= isl_map_copy(acc
->sink
.map
);
418 write_map
= isl_map_copy(acc
->source
[j
].map
);
419 write_map
= isl_map_reverse(write_map
);
420 dep_map
= isl_map_apply_range(read_map
, write_map
);
421 after
= after_at_level(isl_map_get_space(dep_map
), level
);
422 dep_map
= isl_map_intersect(dep_map
, after
);
423 result
= isl_map_partial_lexmax(dep_map
, set_C
, empty
);
424 result
= isl_map_reverse(result
);
429 /* For a given mapping between iterations of must source j and iterations
430 * of the sink, compute the last iteration of must source k preceding
431 * the sink at level before_level for any of the sink iterations,
432 * but following the corresponding iteration of must source j at level
435 static struct isl_map
*last_later_source(struct isl_access_info
*acc
,
436 struct isl_map
*old_map
,
437 int j
, int before_level
,
438 int k
, int after_level
,
439 struct isl_set
**empty
)
442 struct isl_set
*set_C
;
443 struct isl_map
*read_map
;
444 struct isl_map
*write_map
;
445 struct isl_map
*dep_map
;
446 struct isl_map
*after_write
;
447 struct isl_map
*before_read
;
448 struct isl_map
*result
;
450 set_C
= isl_map_range(isl_map_copy(old_map
));
451 read_map
= isl_map_copy(acc
->sink
.map
);
452 write_map
= isl_map_copy(acc
->source
[k
].map
);
454 write_map
= isl_map_reverse(write_map
);
455 dep_map
= isl_map_apply_range(read_map
, write_map
);
456 dim
= space_align_and_join(isl_map_get_space(acc
->source
[k
].map
),
457 isl_space_reverse(isl_map_get_space(acc
->source
[j
].map
)));
458 after_write
= after_at_level(dim
, after_level
);
459 after_write
= isl_map_apply_range(after_write
, old_map
);
460 after_write
= isl_map_reverse(after_write
);
461 dep_map
= isl_map_intersect(dep_map
, after_write
);
462 before_read
= after_at_level(isl_map_get_space(dep_map
), before_level
);
463 dep_map
= isl_map_intersect(dep_map
, before_read
);
464 result
= isl_map_partial_lexmax(dep_map
, set_C
, empty
);
465 result
= isl_map_reverse(result
);
470 /* Given a shared_level between two accesses, return 1 if the
471 * the first can precede the second at the requested target_level.
472 * If the target level is odd, i.e., refers to a statement level
473 * dimension, then first needs to precede second at the requested
474 * level, i.e., shared_level must be equal to target_level.
475 * If the target level is odd, then the two loops should share
476 * at least the requested number of outer loops.
478 static int can_precede_at_level(int shared_level
, int target_level
)
480 if (shared_level
< target_level
)
482 if ((target_level
% 2) && shared_level
> target_level
)
487 /* Given a possible flow dependence temp_rel[j] between source j and the sink
488 * at level sink_level, remove those elements for which
489 * there is an iteration of another source k < j that is closer to the sink.
490 * The flow dependences temp_rel[k] are updated with the improved sources.
491 * Any improved source needs to precede the sink at the same level
492 * and needs to follow source j at the same or a deeper level.
493 * The lower this level, the later the execution date of source k.
494 * We therefore consider lower levels first.
496 * If temp_rel[j] is empty, then there can be no improvement and
497 * we return immediately.
499 static int intermediate_sources(__isl_keep isl_access_info
*acc
,
500 struct isl_map
**temp_rel
, int j
, int sink_level
)
503 int depth
= 2 * isl_map_dim(acc
->source
[j
].map
, isl_dim_in
) + 1;
505 if (isl_map_plain_is_empty(temp_rel
[j
]))
508 for (k
= j
- 1; k
>= 0; --k
) {
510 plevel
= acc
->level_before(acc
->source
[k
].data
, acc
->sink
.data
);
511 if (!can_precede_at_level(plevel
, sink_level
))
514 plevel2
= acc
->level_before(acc
->source
[j
].data
,
515 acc
->source
[k
].data
);
517 for (level
= sink_level
; level
<= depth
; ++level
) {
519 struct isl_set
*trest
;
520 struct isl_map
*copy
;
522 if (!can_precede_at_level(plevel2
, level
))
525 copy
= isl_map_copy(temp_rel
[j
]);
526 T
= last_later_source(acc
, copy
, j
, sink_level
, k
,
528 if (isl_map_plain_is_empty(T
)) {
533 temp_rel
[j
] = isl_map_intersect_range(temp_rel
[j
], trest
);
534 temp_rel
[k
] = isl_map_union_disjoint(temp_rel
[k
], T
);
541 /* Compute all iterations of may source j that precedes the sink at the given
542 * level for sink iterations in set_C.
544 static __isl_give isl_map
*all_sources(__isl_keep isl_access_info
*acc
,
545 __isl_take isl_set
*set_C
, int j
, int level
)
552 read_map
= isl_map_copy(acc
->sink
.map
);
553 read_map
= isl_map_intersect_domain(read_map
, set_C
);
554 write_map
= isl_map_copy(acc
->source
[acc
->n_must
+ j
].map
);
555 write_map
= isl_map_reverse(write_map
);
556 dep_map
= isl_map_apply_range(read_map
, write_map
);
557 after
= after_at_level(isl_map_get_space(dep_map
), level
);
558 dep_map
= isl_map_intersect(dep_map
, after
);
560 return isl_map_reverse(dep_map
);
563 /* For a given mapping between iterations of must source k and iterations
564 * of the sink, compute the all iteration of may source j preceding
565 * the sink at level before_level for any of the sink iterations,
566 * but following the corresponding iteration of must source k at level
569 static __isl_give isl_map
*all_later_sources(__isl_keep isl_access_info
*acc
,
570 __isl_keep isl_map
*old_map
,
571 int j
, int before_level
, int k
, int after_level
)
578 isl_map
*after_write
;
579 isl_map
*before_read
;
581 set_C
= isl_map_range(isl_map_copy(old_map
));
582 read_map
= isl_map_copy(acc
->sink
.map
);
583 read_map
= isl_map_intersect_domain(read_map
, set_C
);
584 write_map
= isl_map_copy(acc
->source
[acc
->n_must
+ j
].map
);
586 write_map
= isl_map_reverse(write_map
);
587 dep_map
= isl_map_apply_range(read_map
, write_map
);
588 dim
= isl_space_join(isl_map_get_space(acc
->source
[acc
->n_must
+ j
].map
),
589 isl_space_reverse(isl_map_get_space(acc
->source
[k
].map
)));
590 after_write
= after_at_level(dim
, after_level
);
591 after_write
= isl_map_apply_range(after_write
, old_map
);
592 after_write
= isl_map_reverse(after_write
);
593 dep_map
= isl_map_intersect(dep_map
, after_write
);
594 before_read
= after_at_level(isl_map_get_space(dep_map
), before_level
);
595 dep_map
= isl_map_intersect(dep_map
, before_read
);
596 return isl_map_reverse(dep_map
);
599 /* Given the must and may dependence relations for the must accesses
600 * for level sink_level, check if there are any accesses of may access j
601 * that occur in between and return their union.
602 * If some of these accesses are intermediate with respect to
603 * (previously thought to be) must dependences, then these
604 * must dependences are turned into may dependences.
606 static __isl_give isl_map
*all_intermediate_sources(
607 __isl_keep isl_access_info
*acc
, __isl_take isl_map
*map
,
608 struct isl_map
**must_rel
, struct isl_map
**may_rel
,
609 int j
, int sink_level
)
612 int depth
= 2 * isl_map_dim(acc
->source
[acc
->n_must
+ j
].map
,
615 for (k
= 0; k
< acc
->n_must
; ++k
) {
618 if (isl_map_plain_is_empty(may_rel
[k
]) &&
619 isl_map_plain_is_empty(must_rel
[k
]))
622 plevel
= acc
->level_before(acc
->source
[k
].data
,
623 acc
->source
[acc
->n_must
+ j
].data
);
625 for (level
= sink_level
; level
<= depth
; ++level
) {
630 if (!can_precede_at_level(plevel
, level
))
633 copy
= isl_map_copy(may_rel
[k
]);
634 T
= all_later_sources(acc
, copy
, j
, sink_level
, k
, level
);
635 map
= isl_map_union(map
, T
);
637 copy
= isl_map_copy(must_rel
[k
]);
638 T
= all_later_sources(acc
, copy
, j
, sink_level
, k
, level
);
639 ran
= isl_map_range(isl_map_copy(T
));
640 map
= isl_map_union(map
, T
);
641 may_rel
[k
] = isl_map_union_disjoint(may_rel
[k
],
642 isl_map_intersect_range(isl_map_copy(must_rel
[k
]),
644 T
= isl_map_from_domain_and_range(
646 isl_space_domain(isl_map_get_space(must_rel
[k
]))),
648 must_rel
[k
] = isl_map_subtract(must_rel
[k
], T
);
655 /* Compute dependences for the case where all accesses are "may"
656 * accesses, which boils down to computing memory based dependences.
657 * The generic algorithm would also work in this case, but it would
658 * be overkill to use it.
660 static __isl_give isl_flow
*compute_mem_based_dependences(
661 __isl_take isl_access_info
*acc
)
668 res
= isl_flow_alloc(acc
);
672 mustdo
= isl_map_domain(isl_map_copy(acc
->sink
.map
));
673 maydo
= isl_set_copy(mustdo
);
675 for (i
= 0; i
< acc
->n_may
; ++i
) {
682 plevel
= acc
->level_before(acc
->source
[i
].data
, acc
->sink
.data
);
683 is_before
= plevel
& 1;
686 dim
= isl_map_get_space(res
->dep
[i
].map
);
688 before
= isl_map_lex_le_first(dim
, plevel
);
690 before
= isl_map_lex_lt_first(dim
, plevel
);
691 dep
= isl_map_apply_range(isl_map_copy(acc
->source
[i
].map
),
692 isl_map_reverse(isl_map_copy(acc
->sink
.map
)));
693 dep
= isl_map_intersect(dep
, before
);
694 mustdo
= isl_set_subtract(mustdo
,
695 isl_map_range(isl_map_copy(dep
)));
696 res
->dep
[i
].map
= isl_map_union(res
->dep
[i
].map
, dep
);
699 res
->may_no_source
= isl_set_subtract(maydo
, isl_set_copy(mustdo
));
700 res
->must_no_source
= mustdo
;
702 isl_access_info_free(acc
);
706 isl_access_info_free(acc
);
710 /* Compute dependences for the case where there is at least one
713 * The core algorithm considers all levels in which a source may precede
714 * the sink, where a level may either be a statement level or a loop level.
715 * The outermost statement level is 1, the first loop level is 2, etc...
716 * The algorithm basically does the following:
717 * for all levels l of the read access from innermost to outermost
718 * for all sources w that may precede the sink access at that level
719 * compute the last iteration of the source that precedes the sink access
721 * add result to possible last accesses at level l of source w
722 * for all sources w2 that we haven't considered yet at this level that may
723 * also precede the sink access
724 * for all levels l2 of w from l to innermost
725 * for all possible last accesses dep of w at l
726 * compute last iteration of w2 between the source and sink
728 * add result to possible last accesses at level l of write w2
729 * and replace possible last accesses dep by the remainder
732 * The above algorithm is applied to the must access. During the course
733 * of the algorithm, we keep track of sink iterations that still
734 * need to be considered. These iterations are split into those that
735 * haven't been matched to any source access (mustdo) and those that have only
736 * been matched to may accesses (maydo).
737 * At the end of each level, we also consider the may accesses.
738 * In particular, we consider may accesses that precede the remaining
739 * sink iterations, moving elements from mustdo to maydo when appropriate,
740 * and may accesses that occur between a must source and a sink of any
741 * dependences found at the current level, turning must dependences into
742 * may dependences when appropriate.
745 static __isl_give isl_flow
*compute_val_based_dependences(
746 __isl_take isl_access_info
*acc
)
750 isl_set
*mustdo
= NULL
;
751 isl_set
*maydo
= NULL
;
754 isl_map
**must_rel
= NULL
;
755 isl_map
**may_rel
= NULL
;
757 acc
= isl_access_info_sort_sources(acc
);
761 res
= isl_flow_alloc(acc
);
764 ctx
= isl_map_get_ctx(acc
->sink
.map
);
766 depth
= 2 * isl_map_dim(acc
->sink
.map
, isl_dim_in
) + 1;
767 mustdo
= isl_map_domain(isl_map_copy(acc
->sink
.map
));
768 maydo
= isl_set_empty_like(mustdo
);
769 if (!mustdo
|| !maydo
)
771 if (isl_set_plain_is_empty(mustdo
))
774 must_rel
= isl_alloc_array(ctx
, struct isl_map
*, acc
->n_must
);
775 may_rel
= isl_alloc_array(ctx
, struct isl_map
*, acc
->n_must
);
776 if (!must_rel
|| !may_rel
)
779 for (level
= depth
; level
>= 1; --level
) {
780 for (j
= acc
->n_must
-1; j
>=0; --j
) {
781 must_rel
[j
] = isl_map_empty_like(res
->dep
[j
].map
);
782 may_rel
[j
] = isl_map_copy(must_rel
[j
]);
785 for (j
= acc
->n_must
- 1; j
>= 0; --j
) {
787 struct isl_set
*rest
;
790 plevel
= acc
->level_before(acc
->source
[j
].data
,
792 if (!can_precede_at_level(plevel
, level
))
795 T
= last_source(acc
, mustdo
, j
, level
, &rest
);
796 must_rel
[j
] = isl_map_union_disjoint(must_rel
[j
], T
);
799 intermediate_sources(acc
, must_rel
, j
, level
);
801 T
= last_source(acc
, maydo
, j
, level
, &rest
);
802 may_rel
[j
] = isl_map_union_disjoint(may_rel
[j
], T
);
805 intermediate_sources(acc
, may_rel
, j
, level
);
807 if (isl_set_plain_is_empty(mustdo
) &&
808 isl_set_plain_is_empty(maydo
))
811 for (j
= j
- 1; j
>= 0; --j
) {
814 plevel
= acc
->level_before(acc
->source
[j
].data
,
816 if (!can_precede_at_level(plevel
, level
))
819 intermediate_sources(acc
, must_rel
, j
, level
);
820 intermediate_sources(acc
, may_rel
, j
, level
);
823 for (j
= 0; j
< acc
->n_may
; ++j
) {
828 plevel
= acc
->level_before(acc
->source
[acc
->n_must
+ j
].data
,
830 if (!can_precede_at_level(plevel
, level
))
833 T
= all_sources(acc
, isl_set_copy(maydo
), j
, level
);
834 res
->dep
[2 * acc
->n_must
+ j
].map
=
835 isl_map_union(res
->dep
[2 * acc
->n_must
+ j
].map
, T
);
836 T
= all_sources(acc
, isl_set_copy(mustdo
), j
, level
);
837 ran
= isl_map_range(isl_map_copy(T
));
838 res
->dep
[2 * acc
->n_must
+ j
].map
=
839 isl_map_union(res
->dep
[2 * acc
->n_must
+ j
].map
, T
);
840 mustdo
= isl_set_subtract(mustdo
, isl_set_copy(ran
));
841 maydo
= isl_set_union_disjoint(maydo
, ran
);
843 T
= res
->dep
[2 * acc
->n_must
+ j
].map
;
844 T
= all_intermediate_sources(acc
, T
, must_rel
, may_rel
,
846 res
->dep
[2 * acc
->n_must
+ j
].map
= T
;
849 for (j
= acc
->n_must
- 1; j
>= 0; --j
) {
850 res
->dep
[2 * j
].map
=
851 isl_map_union_disjoint(res
->dep
[2 * j
].map
,
853 res
->dep
[2 * j
+ 1].map
=
854 isl_map_union_disjoint(res
->dep
[2 * j
+ 1].map
,
858 if (isl_set_plain_is_empty(mustdo
) &&
859 isl_set_plain_is_empty(maydo
))
866 res
->must_no_source
= mustdo
;
867 res
->may_no_source
= maydo
;
868 isl_access_info_free(acc
);
871 isl_access_info_free(acc
);
873 isl_set_free(mustdo
);
880 /* Given a "sink" access, a list of n "source" accesses,
881 * compute for each iteration of the sink access
882 * and for each element accessed by that iteration,
883 * the source access in the list that last accessed the
884 * element accessed by the sink access before this sink access.
885 * Each access is given as a map from the loop iterators
886 * to the array indices.
887 * The result is a list of n relations between source and sink
888 * iterations and a subset of the domain of the sink access,
889 * corresponding to those iterations that access an element
890 * not previously accessed.
892 * To deal with multi-valued sink access relations, the sink iteration
893 * domain is first extended with dimensions that correspond to the data
894 * space. After the computation is finished, these extra dimensions are
895 * projected out again.
897 __isl_give isl_flow
*isl_access_info_compute_flow(__isl_take isl_access_info
*acc
)
900 struct isl_flow
*res
;
901 isl_map
*domain_map
= NULL
;
906 domain_map
= isl_map_domain_map(isl_map_copy(acc
->sink
.map
));
907 acc
->sink
.map
= isl_map_range_map(acc
->sink
.map
);
911 if (acc
->n_must
== 0)
912 res
= compute_mem_based_dependences(acc
);
914 res
= compute_val_based_dependences(acc
);
918 for (j
= 0; j
< res
->n_source
; ++j
) {
919 res
->dep
[j
].map
= isl_map_apply_range(res
->dep
[j
].map
,
920 isl_map_copy(domain_map
));
921 if (!res
->dep
[j
].map
)
924 if (!res
->must_no_source
|| !res
->may_no_source
)
927 isl_map_free(domain_map
);
930 isl_map_free(domain_map
);
931 isl_access_info_free(acc
);
934 isl_map_free(domain_map
);
940 /* Keep track of some information about a schedule for a given
941 * access. In particular, keep track of which dimensions
942 * have a constant value and of the actual constant values.
944 struct isl_sched_info
{
949 static void sched_info_free(__isl_take
struct isl_sched_info
*info
)
953 isl_vec_free(info
->cst
);
958 /* Extract information on the constant dimensions of the schedule
959 * for a given access. The "map" is of the form
963 * with S the schedule domain, D the iteration domain and A the data domain.
965 static __isl_give
struct isl_sched_info
*sched_info_alloc(
966 __isl_keep isl_map
*map
)
970 struct isl_sched_info
*info
;
976 dim
= isl_space_unwrap(isl_space_domain(isl_map_get_space(map
)));
979 n
= isl_space_dim(dim
, isl_dim_in
);
982 ctx
= isl_map_get_ctx(map
);
983 info
= isl_alloc_type(ctx
, struct isl_sched_info
);
986 info
->is_cst
= isl_alloc_array(ctx
, int, n
);
987 info
->cst
= isl_vec_alloc(ctx
, n
);
988 if (!info
->is_cst
|| !info
->cst
)
991 for (i
= 0; i
< n
; ++i
)
992 info
->is_cst
[i
] = isl_map_plain_is_fixed(map
, isl_dim_in
, i
,
997 sched_info_free(info
);
1001 struct isl_compute_flow_data
{
1002 isl_union_map
*must_source
;
1003 isl_union_map
*may_source
;
1004 isl_union_map
*must_dep
;
1005 isl_union_map
*may_dep
;
1006 isl_union_map
*must_no_source
;
1007 isl_union_map
*may_no_source
;
1012 struct isl_sched_info
*sink_info
;
1013 struct isl_sched_info
**source_info
;
1014 isl_access_info
*accesses
;
1017 static int count_matching_array(__isl_take isl_map
*map
, void *user
)
1021 struct isl_compute_flow_data
*data
;
1023 data
= (struct isl_compute_flow_data
*)user
;
1025 dim
= isl_space_range(isl_map_get_space(map
));
1027 eq
= isl_space_is_equal(dim
, data
->dim
);
1029 isl_space_free(dim
);
1040 static int collect_matching_array(__isl_take isl_map
*map
, void *user
)
1044 struct isl_sched_info
*info
;
1045 struct isl_compute_flow_data
*data
;
1047 data
= (struct isl_compute_flow_data
*)user
;
1049 dim
= isl_space_range(isl_map_get_space(map
));
1051 eq
= isl_space_is_equal(dim
, data
->dim
);
1053 isl_space_free(dim
);
1062 info
= sched_info_alloc(map
);
1063 data
->source_info
[data
->count
] = info
;
1065 data
->accesses
= isl_access_info_add_source(data
->accesses
,
1066 map
, data
->must
, info
);
1076 /* Determine the shared nesting level and the "textual order" of
1077 * the given accesses.
1079 * We first determine the minimal schedule dimension for both accesses.
1081 * If among those dimensions, we can find one where both have a fixed
1082 * value and if moreover those values are different, then the previous
1083 * dimension is the last shared nesting level and the textual order
1084 * is determined based on the order of the fixed values.
1085 * If no such fixed values can be found, then we set the shared
1086 * nesting level to the minimal schedule dimension, with no textual ordering.
1088 static int before(void *first
, void *second
)
1090 struct isl_sched_info
*info1
= first
;
1091 struct isl_sched_info
*info2
= second
;
1095 n1
= info1
->cst
->size
;
1096 n2
= info2
->cst
->size
;
1101 for (i
= 0; i
< n1
; ++i
) {
1102 if (!info1
->is_cst
[i
])
1104 if (!info2
->is_cst
[i
])
1106 if (isl_int_eq(info1
->cst
->el
[i
], info2
->cst
->el
[i
]))
1108 return 2 * i
+ isl_int_lt(info1
->cst
->el
[i
], info2
->cst
->el
[i
]);
1114 /* Given a sink access, look for all the source accesses that access
1115 * the same array and perform dataflow analysis on them using
1116 * isl_access_info_compute_flow.
1118 static int compute_flow(__isl_take isl_map
*map
, void *user
)
1122 struct isl_compute_flow_data
*data
;
1125 data
= (struct isl_compute_flow_data
*)user
;
1127 ctx
= isl_map_get_ctx(map
);
1129 data
->accesses
= NULL
;
1130 data
->sink_info
= NULL
;
1131 data
->source_info
= NULL
;
1133 data
->dim
= isl_space_range(isl_map_get_space(map
));
1135 if (isl_union_map_foreach_map(data
->must_source
,
1136 &count_matching_array
, data
) < 0)
1138 if (isl_union_map_foreach_map(data
->may_source
,
1139 &count_matching_array
, data
) < 0)
1142 data
->sink_info
= sched_info_alloc(map
);
1143 data
->source_info
= isl_calloc_array(ctx
, struct isl_sched_info
*,
1146 data
->accesses
= isl_access_info_alloc(isl_map_copy(map
),
1147 data
->sink_info
, &before
, data
->count
);
1148 if (!data
->sink_info
|| !data
->source_info
|| !data
->accesses
)
1152 if (isl_union_map_foreach_map(data
->must_source
,
1153 &collect_matching_array
, data
) < 0)
1156 if (isl_union_map_foreach_map(data
->may_source
,
1157 &collect_matching_array
, data
) < 0)
1160 flow
= isl_access_info_compute_flow(data
->accesses
);
1161 data
->accesses
= NULL
;
1166 data
->must_no_source
= isl_union_map_union(data
->must_no_source
,
1167 isl_union_map_from_map(isl_flow_get_no_source(flow
, 1)));
1168 data
->may_no_source
= isl_union_map_union(data
->may_no_source
,
1169 isl_union_map_from_map(isl_flow_get_no_source(flow
, 0)));
1171 for (i
= 0; i
< flow
->n_source
; ++i
) {
1173 dep
= isl_union_map_from_map(isl_map_copy(flow
->dep
[i
].map
));
1174 if (flow
->dep
[i
].must
)
1175 data
->must_dep
= isl_union_map_union(data
->must_dep
, dep
);
1177 data
->may_dep
= isl_union_map_union(data
->may_dep
, dep
);
1180 isl_flow_free(flow
);
1182 sched_info_free(data
->sink_info
);
1183 if (data
->source_info
) {
1184 for (i
= 0; i
< data
->count
; ++i
)
1185 sched_info_free(data
->source_info
[i
]);
1186 free(data
->source_info
);
1188 isl_space_free(data
->dim
);
1193 isl_access_info_free(data
->accesses
);
1194 sched_info_free(data
->sink_info
);
1195 if (data
->source_info
) {
1196 for (i
= 0; i
< data
->count
; ++i
)
1197 sched_info_free(data
->source_info
[i
]);
1198 free(data
->source_info
);
1200 isl_space_free(data
->dim
);
1206 /* Given a collection of "sink" and "source" accesses,
1207 * compute for each iteration of a sink access
1208 * and for each element accessed by that iteration,
1209 * the source access in the list that last accessed the
1210 * element accessed by the sink access before this sink access.
1211 * Each access is given as a map from the loop iterators
1212 * to the array indices.
1213 * The result is a relations between source and sink
1214 * iterations and a subset of the domain of the sink accesses,
1215 * corresponding to those iterations that access an element
1216 * not previously accessed.
1218 * We first prepend the schedule dimensions to the domain
1219 * of the accesses so that we can easily compare their relative order.
1220 * Then we consider each sink access individually in compute_flow.
1222 int isl_union_map_compute_flow(__isl_take isl_union_map
*sink
,
1223 __isl_take isl_union_map
*must_source
,
1224 __isl_take isl_union_map
*may_source
,
1225 __isl_take isl_union_map
*schedule
,
1226 __isl_give isl_union_map
**must_dep
, __isl_give isl_union_map
**may_dep
,
1227 __isl_give isl_union_map
**must_no_source
,
1228 __isl_give isl_union_map
**may_no_source
)
1231 isl_union_map
*range_map
= NULL
;
1232 struct isl_compute_flow_data data
;
1234 sink
= isl_union_map_align_params(sink
,
1235 isl_union_map_get_space(must_source
));
1236 sink
= isl_union_map_align_params(sink
,
1237 isl_union_map_get_space(may_source
));
1238 sink
= isl_union_map_align_params(sink
,
1239 isl_union_map_get_space(schedule
));
1240 dim
= isl_union_map_get_space(sink
);
1241 must_source
= isl_union_map_align_params(must_source
, isl_space_copy(dim
));
1242 may_source
= isl_union_map_align_params(may_source
, isl_space_copy(dim
));
1243 schedule
= isl_union_map_align_params(schedule
, isl_space_copy(dim
));
1245 schedule
= isl_union_map_reverse(schedule
);
1246 range_map
= isl_union_map_range_map(schedule
);
1247 schedule
= isl_union_map_reverse(isl_union_map_copy(range_map
));
1248 sink
= isl_union_map_apply_domain(sink
, isl_union_map_copy(schedule
));
1249 must_source
= isl_union_map_apply_domain(must_source
,
1250 isl_union_map_copy(schedule
));
1251 may_source
= isl_union_map_apply_domain(may_source
, schedule
);
1253 data
.must_source
= must_source
;
1254 data
.may_source
= may_source
;
1255 data
.must_dep
= must_dep
?
1256 isl_union_map_empty(isl_space_copy(dim
)) : NULL
;
1257 data
.may_dep
= may_dep
? isl_union_map_empty(isl_space_copy(dim
)) : NULL
;
1258 data
.must_no_source
= must_no_source
?
1259 isl_union_map_empty(isl_space_copy(dim
)) : NULL
;
1260 data
.may_no_source
= may_no_source
?
1261 isl_union_map_empty(isl_space_copy(dim
)) : NULL
;
1263 isl_space_free(dim
);
1265 if (isl_union_map_foreach_map(sink
, &compute_flow
, &data
) < 0)
1268 isl_union_map_free(sink
);
1269 isl_union_map_free(must_source
);
1270 isl_union_map_free(may_source
);
1273 data
.must_dep
= isl_union_map_apply_domain(data
.must_dep
,
1274 isl_union_map_copy(range_map
));
1275 data
.must_dep
= isl_union_map_apply_range(data
.must_dep
,
1276 isl_union_map_copy(range_map
));
1277 *must_dep
= data
.must_dep
;
1280 data
.may_dep
= isl_union_map_apply_domain(data
.may_dep
,
1281 isl_union_map_copy(range_map
));
1282 data
.may_dep
= isl_union_map_apply_range(data
.may_dep
,
1283 isl_union_map_copy(range_map
));
1284 *may_dep
= data
.may_dep
;
1286 if (must_no_source
) {
1287 data
.must_no_source
= isl_union_map_apply_domain(
1288 data
.must_no_source
, isl_union_map_copy(range_map
));
1289 *must_no_source
= data
.must_no_source
;
1291 if (may_no_source
) {
1292 data
.may_no_source
= isl_union_map_apply_domain(
1293 data
.may_no_source
, isl_union_map_copy(range_map
));
1294 *may_no_source
= data
.may_no_source
;
1297 isl_union_map_free(range_map
);
1301 isl_union_map_free(range_map
);
1302 isl_union_map_free(sink
);
1303 isl_union_map_free(must_source
);
1304 isl_union_map_free(may_source
);
1305 isl_union_map_free(data
.must_dep
);
1306 isl_union_map_free(data
.may_dep
);
1307 isl_union_map_free(data
.must_no_source
);
1308 isl_union_map_free(data
.may_no_source
);
1315 *must_no_source
= NULL
;
1317 *may_no_source
= NULL
;