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 /* Initialize an empty isl_flow structure corresponding to a given
246 * isl_access_info structure.
247 * For each must access, two dependences are created (initialized
248 * to the empty relation), one for the resulting must dependences
249 * and one for the resulting may dependences. May accesses can
250 * only lead to may dependences, so only one dependence is created
252 * This function is private as isl_flow structures are only supposed
253 * to be created by isl_access_info_compute_flow.
255 static __isl_give isl_flow
*isl_flow_alloc(__isl_keep isl_access_info
*acc
)
259 struct isl_flow
*dep
;
264 ctx
= isl_map_get_ctx(acc
->sink
.map
);
265 dep
= isl_calloc_type(ctx
, struct isl_flow
);
269 dep
->dep
= isl_calloc_array(ctx
, struct isl_labeled_map
,
270 2 * acc
->n_must
+ acc
->n_may
);
274 dep
->n_source
= 2 * acc
->n_must
+ acc
->n_may
;
275 for (i
= 0; i
< acc
->n_must
; ++i
) {
277 dim
= isl_dim_join(isl_map_get_dim(acc
->source
[i
].map
),
278 isl_dim_reverse(isl_map_get_dim(acc
->sink
.map
)));
279 dep
->dep
[2 * i
].map
= isl_map_empty(dim
);
280 dep
->dep
[2 * i
+ 1].map
= isl_map_copy(dep
->dep
[2 * i
].map
);
281 dep
->dep
[2 * i
].data
= acc
->source
[i
].data
;
282 dep
->dep
[2 * i
+ 1].data
= acc
->source
[i
].data
;
283 dep
->dep
[2 * i
].must
= 1;
284 dep
->dep
[2 * i
+ 1].must
= 0;
285 if (!dep
->dep
[2 * i
].map
|| !dep
->dep
[2 * i
+ 1].map
)
288 for (i
= acc
->n_must
; i
< acc
->n_must
+ acc
->n_may
; ++i
) {
290 dim
= isl_dim_join(isl_map_get_dim(acc
->source
[i
].map
),
291 isl_dim_reverse(isl_map_get_dim(acc
->sink
.map
)));
292 dep
->dep
[acc
->n_must
+ i
].map
= isl_map_empty(dim
);
293 dep
->dep
[acc
->n_must
+ i
].data
= acc
->source
[i
].data
;
294 dep
->dep
[acc
->n_must
+ i
].must
= 0;
295 if (!dep
->dep
[acc
->n_must
+ i
].map
)
305 /* Iterate over all sources and for each resulting flow dependence
306 * that is not empty, call the user specfied function.
307 * The second argument in this function call identifies the source,
308 * while the third argument correspond to the final argument of
309 * the isl_flow_foreach call.
311 int isl_flow_foreach(__isl_keep isl_flow
*deps
,
312 int (*fn
)(__isl_take isl_map
*dep
, int must
, void *dep_user
, void *user
),
320 for (i
= 0; i
< deps
->n_source
; ++i
) {
321 if (isl_map_plain_is_empty(deps
->dep
[i
].map
))
323 if (fn(isl_map_copy(deps
->dep
[i
].map
), deps
->dep
[i
].must
,
324 deps
->dep
[i
].data
, user
) < 0)
331 /* Return a copy of the subset of the sink for which no source could be found.
333 __isl_give isl_map
*isl_flow_get_no_source(__isl_keep isl_flow
*deps
, int must
)
339 return isl_set_unwrap(isl_set_copy(deps
->must_no_source
));
341 return isl_set_unwrap(isl_set_copy(deps
->may_no_source
));
344 void isl_flow_free(__isl_take isl_flow
*deps
)
350 isl_set_free(deps
->must_no_source
);
351 isl_set_free(deps
->may_no_source
);
353 for (i
= 0; i
< deps
->n_source
; ++i
)
354 isl_map_free(deps
->dep
[i
].map
);
360 isl_ctx
*isl_flow_get_ctx(__isl_keep isl_flow
*deps
)
362 return deps
? isl_set_get_ctx(deps
->must_no_source
) : NULL
;
365 /* Return a map that enforces that the domain iteration occurs after
366 * the range iteration at the given level.
367 * If level is odd, then the domain iteration should occur after
368 * the target iteration in their shared level/2 outermost loops.
369 * In this case we simply need to enforce that these outermost
370 * loop iterations are the same.
371 * If level is even, then the loop iterator of the domain should
372 * be greater than the loop iterator of the range at the last
373 * of the level/2 shared loops, i.e., loop level/2 - 1.
375 static __isl_give isl_map
*after_at_level(struct isl_dim
*dim
, int level
)
377 struct isl_basic_map
*bmap
;
380 bmap
= isl_basic_map_equal(dim
, level
/2);
382 bmap
= isl_basic_map_more_at(dim
, level
/2 - 1);
384 return isl_map_from_basic_map(bmap
);
387 /* Compute the last iteration of must source j that precedes the sink
388 * at the given level for sink iterations in set_C.
389 * The subset of set_C for which no such iteration can be found is returned
392 static struct isl_map
*last_source(struct isl_access_info
*acc
,
393 struct isl_set
*set_C
,
394 int j
, int level
, struct isl_set
**empty
)
396 struct isl_map
*read_map
;
397 struct isl_map
*write_map
;
398 struct isl_map
*dep_map
;
399 struct isl_map
*after
;
400 struct isl_map
*result
;
402 read_map
= isl_map_copy(acc
->sink
.map
);
403 write_map
= isl_map_copy(acc
->source
[j
].map
);
404 write_map
= isl_map_reverse(write_map
);
405 dep_map
= isl_map_apply_range(read_map
, write_map
);
406 after
= after_at_level(isl_map_get_dim(dep_map
), level
);
407 dep_map
= isl_map_intersect(dep_map
, after
);
408 result
= isl_map_partial_lexmax(dep_map
, set_C
, empty
);
409 result
= isl_map_reverse(result
);
414 /* For a given mapping between iterations of must source j and iterations
415 * of the sink, compute the last iteration of must source k preceding
416 * the sink at level before_level for any of the sink iterations,
417 * but following the corresponding iteration of must source j at level
420 static struct isl_map
*last_later_source(struct isl_access_info
*acc
,
421 struct isl_map
*old_map
,
422 int j
, int before_level
,
423 int k
, int after_level
,
424 struct isl_set
**empty
)
427 struct isl_set
*set_C
;
428 struct isl_map
*read_map
;
429 struct isl_map
*write_map
;
430 struct isl_map
*dep_map
;
431 struct isl_map
*after_write
;
432 struct isl_map
*before_read
;
433 struct isl_map
*result
;
435 set_C
= isl_map_range(isl_map_copy(old_map
));
436 read_map
= isl_map_copy(acc
->sink
.map
);
437 write_map
= isl_map_copy(acc
->source
[k
].map
);
439 write_map
= isl_map_reverse(write_map
);
440 dep_map
= isl_map_apply_range(read_map
, write_map
);
441 dim
= isl_dim_join(isl_map_get_dim(acc
->source
[k
].map
),
442 isl_dim_reverse(isl_map_get_dim(acc
->source
[j
].map
)));
443 after_write
= after_at_level(dim
, after_level
);
444 after_write
= isl_map_apply_range(after_write
, old_map
);
445 after_write
= isl_map_reverse(after_write
);
446 dep_map
= isl_map_intersect(dep_map
, after_write
);
447 before_read
= after_at_level(isl_map_get_dim(dep_map
), before_level
);
448 dep_map
= isl_map_intersect(dep_map
, before_read
);
449 result
= isl_map_partial_lexmax(dep_map
, set_C
, empty
);
450 result
= isl_map_reverse(result
);
455 /* Given a shared_level between two accesses, return 1 if the
456 * the first can precede the second at the requested target_level.
457 * If the target level is odd, i.e., refers to a statement level
458 * dimension, then first needs to precede second at the requested
459 * level, i.e., shared_level must be equal to target_level.
460 * If the target level is odd, then the two loops should share
461 * at least the requested number of outer loops.
463 static int can_precede_at_level(int shared_level
, int target_level
)
465 if (shared_level
< target_level
)
467 if ((target_level
% 2) && shared_level
> target_level
)
472 /* Given a possible flow dependence temp_rel[j] between source j and the sink
473 * at level sink_level, remove those elements for which
474 * there is an iteration of another source k < j that is closer to the sink.
475 * The flow dependences temp_rel[k] are updated with the improved sources.
476 * Any improved source needs to precede the sink at the same level
477 * and needs to follow source j at the same or a deeper level.
478 * The lower this level, the later the execution date of source k.
479 * We therefore consider lower levels first.
481 * If temp_rel[j] is empty, then there can be no improvement and
482 * we return immediately.
484 static int intermediate_sources(__isl_keep isl_access_info
*acc
,
485 struct isl_map
**temp_rel
, int j
, int sink_level
)
488 int depth
= 2 * isl_map_dim(acc
->source
[j
].map
, isl_dim_in
) + 1;
490 if (isl_map_plain_is_empty(temp_rel
[j
]))
493 for (k
= j
- 1; k
>= 0; --k
) {
495 plevel
= acc
->level_before(acc
->source
[k
].data
, acc
->sink
.data
);
496 if (!can_precede_at_level(plevel
, sink_level
))
499 plevel2
= acc
->level_before(acc
->source
[j
].data
,
500 acc
->source
[k
].data
);
502 for (level
= sink_level
; level
<= depth
; ++level
) {
504 struct isl_set
*trest
;
505 struct isl_map
*copy
;
507 if (!can_precede_at_level(plevel2
, level
))
510 copy
= isl_map_copy(temp_rel
[j
]);
511 T
= last_later_source(acc
, copy
, j
, sink_level
, k
,
513 if (isl_map_plain_is_empty(T
)) {
518 temp_rel
[j
] = isl_map_intersect_range(temp_rel
[j
], trest
);
519 temp_rel
[k
] = isl_map_union_disjoint(temp_rel
[k
], T
);
526 /* Compute all iterations of may source j that precedes the sink at the given
527 * level for sink iterations in set_C.
529 static __isl_give isl_map
*all_sources(__isl_keep isl_access_info
*acc
,
530 __isl_take isl_set
*set_C
, int j
, int level
)
537 read_map
= isl_map_copy(acc
->sink
.map
);
538 read_map
= isl_map_intersect_domain(read_map
, set_C
);
539 write_map
= isl_map_copy(acc
->source
[acc
->n_must
+ j
].map
);
540 write_map
= isl_map_reverse(write_map
);
541 dep_map
= isl_map_apply_range(read_map
, write_map
);
542 after
= after_at_level(isl_map_get_dim(dep_map
), level
);
543 dep_map
= isl_map_intersect(dep_map
, after
);
545 return isl_map_reverse(dep_map
);
548 /* For a given mapping between iterations of must source k and iterations
549 * of the sink, compute the all iteration of may source j preceding
550 * the sink at level before_level for any of the sink iterations,
551 * but following the corresponding iteration of must source k at level
554 static __isl_give isl_map
*all_later_sources(__isl_keep isl_access_info
*acc
,
555 __isl_keep isl_map
*old_map
,
556 int j
, int before_level
, int k
, int after_level
)
563 isl_map
*after_write
;
564 isl_map
*before_read
;
566 set_C
= isl_map_range(isl_map_copy(old_map
));
567 read_map
= isl_map_copy(acc
->sink
.map
);
568 read_map
= isl_map_intersect_domain(read_map
, set_C
);
569 write_map
= isl_map_copy(acc
->source
[acc
->n_must
+ j
].map
);
571 write_map
= isl_map_reverse(write_map
);
572 dep_map
= isl_map_apply_range(read_map
, write_map
);
573 dim
= isl_dim_join(isl_map_get_dim(acc
->source
[acc
->n_must
+ j
].map
),
574 isl_dim_reverse(isl_map_get_dim(acc
->source
[k
].map
)));
575 after_write
= after_at_level(dim
, after_level
);
576 after_write
= isl_map_apply_range(after_write
, old_map
);
577 after_write
= isl_map_reverse(after_write
);
578 dep_map
= isl_map_intersect(dep_map
, after_write
);
579 before_read
= after_at_level(isl_map_get_dim(dep_map
), before_level
);
580 dep_map
= isl_map_intersect(dep_map
, before_read
);
581 return isl_map_reverse(dep_map
);
584 /* Given the must and may dependence relations for the must accesses
585 * for level sink_level, check if there are any accesses of may access j
586 * that occur in between and return their union.
587 * If some of these accesses are intermediate with respect to
588 * (previously thought to be) must dependences, then these
589 * must dependences are turned into may dependences.
591 static __isl_give isl_map
*all_intermediate_sources(
592 __isl_keep isl_access_info
*acc
, __isl_take isl_map
*map
,
593 struct isl_map
**must_rel
, struct isl_map
**may_rel
,
594 int j
, int sink_level
)
597 int depth
= 2 * isl_map_dim(acc
->source
[acc
->n_must
+ j
].map
,
600 for (k
= 0; k
< acc
->n_must
; ++k
) {
603 if (isl_map_plain_is_empty(may_rel
[k
]) &&
604 isl_map_plain_is_empty(must_rel
[k
]))
607 plevel
= acc
->level_before(acc
->source
[k
].data
,
608 acc
->source
[acc
->n_must
+ j
].data
);
610 for (level
= sink_level
; level
<= depth
; ++level
) {
615 if (!can_precede_at_level(plevel
, level
))
618 copy
= isl_map_copy(may_rel
[k
]);
619 T
= all_later_sources(acc
, copy
, j
, sink_level
, k
, level
);
620 map
= isl_map_union(map
, T
);
622 copy
= isl_map_copy(must_rel
[k
]);
623 T
= all_later_sources(acc
, copy
, j
, sink_level
, k
, level
);
624 ran
= isl_map_range(isl_map_copy(T
));
625 map
= isl_map_union(map
, T
);
626 may_rel
[k
] = isl_map_union_disjoint(may_rel
[k
],
627 isl_map_intersect_range(isl_map_copy(must_rel
[k
]),
629 T
= isl_map_from_domain_and_range(
631 isl_dim_domain(isl_map_get_dim(must_rel
[k
]))),
633 must_rel
[k
] = isl_map_subtract(must_rel
[k
], T
);
640 /* Compute dependences for the case where all accesses are "may"
641 * accesses, which boils down to computing memory based dependences.
642 * The generic algorithm would also work in this case, but it would
643 * be overkill to use it.
645 static __isl_give isl_flow
*compute_mem_based_dependences(
646 __isl_take isl_access_info
*acc
)
653 res
= isl_flow_alloc(acc
);
657 mustdo
= isl_map_domain(isl_map_copy(acc
->sink
.map
));
658 maydo
= isl_set_copy(mustdo
);
660 for (i
= 0; i
< acc
->n_may
; ++i
) {
667 plevel
= acc
->level_before(acc
->source
[i
].data
, acc
->sink
.data
);
668 is_before
= plevel
& 1;
671 dim
= isl_map_get_dim(res
->dep
[i
].map
);
673 before
= isl_map_lex_le_first(dim
, plevel
);
675 before
= isl_map_lex_lt_first(dim
, plevel
);
676 dep
= isl_map_apply_range(isl_map_copy(acc
->source
[i
].map
),
677 isl_map_reverse(isl_map_copy(acc
->sink
.map
)));
678 dep
= isl_map_intersect(dep
, before
);
679 mustdo
= isl_set_subtract(mustdo
,
680 isl_map_range(isl_map_copy(dep
)));
681 res
->dep
[i
].map
= isl_map_union(res
->dep
[i
].map
, dep
);
684 res
->may_no_source
= isl_set_subtract(maydo
, isl_set_copy(mustdo
));
685 res
->must_no_source
= mustdo
;
687 isl_access_info_free(acc
);
691 isl_access_info_free(acc
);
695 /* Compute dependences for the case where there is at least one
698 * The core algorithm considers all levels in which a source may precede
699 * the sink, where a level may either be a statement level or a loop level.
700 * The outermost statement level is 1, the first loop level is 2, etc...
701 * The algorithm basically does the following:
702 * for all levels l of the read access from innermost to outermost
703 * for all sources w that may precede the sink access at that level
704 * compute the last iteration of the source that precedes the sink access
706 * add result to possible last accesses at level l of source w
707 * for all sources w2 that we haven't considered yet at this level that may
708 * also precede the sink access
709 * for all levels l2 of w from l to innermost
710 * for all possible last accesses dep of w at l
711 * compute last iteration of w2 between the source and sink
713 * add result to possible last accesses at level l of write w2
714 * and replace possible last accesses dep by the remainder
717 * The above algorithm is applied to the must access. During the course
718 * of the algorithm, we keep track of sink iterations that still
719 * need to be considered. These iterations are split into those that
720 * haven't been matched to any source access (mustdo) and those that have only
721 * been matched to may accesses (maydo).
722 * At the end of each level, we also consider the may accesses.
723 * In particular, we consider may accesses that precede the remaining
724 * sink iterations, moving elements from mustdo to maydo when appropriate,
725 * and may accesses that occur between a must source and a sink of any
726 * dependences found at the current level, turning must dependences into
727 * may dependences when appropriate.
730 static __isl_give isl_flow
*compute_val_based_dependences(
731 __isl_take isl_access_info
*acc
)
735 isl_set
*mustdo
= NULL
;
736 isl_set
*maydo
= NULL
;
739 isl_map
**must_rel
= NULL
;
740 isl_map
**may_rel
= NULL
;
742 acc
= isl_access_info_sort_sources(acc
);
746 res
= isl_flow_alloc(acc
);
749 ctx
= isl_map_get_ctx(acc
->sink
.map
);
751 depth
= 2 * isl_map_dim(acc
->sink
.map
, isl_dim_in
) + 1;
752 mustdo
= isl_map_domain(isl_map_copy(acc
->sink
.map
));
753 maydo
= isl_set_empty_like(mustdo
);
754 if (!mustdo
|| !maydo
)
756 if (isl_set_plain_is_empty(mustdo
))
759 must_rel
= isl_alloc_array(ctx
, struct isl_map
*, acc
->n_must
);
760 may_rel
= isl_alloc_array(ctx
, struct isl_map
*, acc
->n_must
);
761 if (!must_rel
|| !may_rel
)
764 for (level
= depth
; level
>= 1; --level
) {
765 for (j
= acc
->n_must
-1; j
>=0; --j
) {
766 must_rel
[j
] = isl_map_empty_like(res
->dep
[j
].map
);
767 may_rel
[j
] = isl_map_copy(must_rel
[j
]);
770 for (j
= acc
->n_must
- 1; j
>= 0; --j
) {
772 struct isl_set
*rest
;
775 plevel
= acc
->level_before(acc
->source
[j
].data
,
777 if (!can_precede_at_level(plevel
, level
))
780 T
= last_source(acc
, mustdo
, j
, level
, &rest
);
781 must_rel
[j
] = isl_map_union_disjoint(must_rel
[j
], T
);
784 intermediate_sources(acc
, must_rel
, j
, level
);
786 T
= last_source(acc
, maydo
, j
, level
, &rest
);
787 may_rel
[j
] = isl_map_union_disjoint(may_rel
[j
], T
);
790 intermediate_sources(acc
, may_rel
, j
, level
);
792 if (isl_set_plain_is_empty(mustdo
) &&
793 isl_set_plain_is_empty(maydo
))
796 for (j
= j
- 1; j
>= 0; --j
) {
799 plevel
= acc
->level_before(acc
->source
[j
].data
,
801 if (!can_precede_at_level(plevel
, level
))
804 intermediate_sources(acc
, must_rel
, j
, level
);
805 intermediate_sources(acc
, may_rel
, j
, level
);
808 for (j
= 0; j
< acc
->n_may
; ++j
) {
813 plevel
= acc
->level_before(acc
->source
[acc
->n_must
+ j
].data
,
815 if (!can_precede_at_level(plevel
, level
))
818 T
= all_sources(acc
, isl_set_copy(maydo
), j
, level
);
819 res
->dep
[2 * acc
->n_must
+ j
].map
=
820 isl_map_union(res
->dep
[2 * acc
->n_must
+ j
].map
, T
);
821 T
= all_sources(acc
, isl_set_copy(mustdo
), j
, level
);
822 ran
= isl_map_range(isl_map_copy(T
));
823 res
->dep
[2 * acc
->n_must
+ j
].map
=
824 isl_map_union(res
->dep
[2 * acc
->n_must
+ j
].map
, T
);
825 mustdo
= isl_set_subtract(mustdo
, isl_set_copy(ran
));
826 maydo
= isl_set_union_disjoint(maydo
, ran
);
828 T
= res
->dep
[2 * acc
->n_must
+ j
].map
;
829 T
= all_intermediate_sources(acc
, T
, must_rel
, may_rel
,
831 res
->dep
[2 * acc
->n_must
+ j
].map
= T
;
834 for (j
= acc
->n_must
- 1; j
>= 0; --j
) {
835 res
->dep
[2 * j
].map
=
836 isl_map_union_disjoint(res
->dep
[2 * j
].map
,
838 res
->dep
[2 * j
+ 1].map
=
839 isl_map_union_disjoint(res
->dep
[2 * j
+ 1].map
,
843 if (isl_set_plain_is_empty(mustdo
) &&
844 isl_set_plain_is_empty(maydo
))
851 res
->must_no_source
= mustdo
;
852 res
->may_no_source
= maydo
;
853 isl_access_info_free(acc
);
856 isl_access_info_free(acc
);
858 isl_set_free(mustdo
);
865 /* Given a "sink" access, a list of n "source" accesses,
866 * compute for each iteration of the sink access
867 * and for each element accessed by that iteration,
868 * the source access in the list that last accessed the
869 * element accessed by the sink access before this sink access.
870 * Each access is given as a map from the loop iterators
871 * to the array indices.
872 * The result is a list of n relations between source and sink
873 * iterations and a subset of the domain of the sink access,
874 * corresponding to those iterations that access an element
875 * not previously accessed.
877 * To deal with multi-valued sink access relations, the sink iteration
878 * domain is first extended with dimensions that correspond to the data
879 * space. After the computation is finished, these extra dimensions are
880 * projected out again.
882 __isl_give isl_flow
*isl_access_info_compute_flow(__isl_take isl_access_info
*acc
)
885 struct isl_flow
*res
;
886 isl_map
*domain_map
= NULL
;
891 domain_map
= isl_map_domain_map(isl_map_copy(acc
->sink
.map
));
892 acc
->sink
.map
= isl_map_range_map(acc
->sink
.map
);
896 if (acc
->n_must
== 0)
897 res
= compute_mem_based_dependences(acc
);
899 res
= compute_val_based_dependences(acc
);
903 for (j
= 0; j
< res
->n_source
; ++j
) {
904 res
->dep
[j
].map
= isl_map_apply_range(res
->dep
[j
].map
,
905 isl_map_copy(domain_map
));
906 if (!res
->dep
[j
].map
)
909 if (!res
->must_no_source
|| !res
->may_no_source
)
912 isl_map_free(domain_map
);
915 isl_map_free(domain_map
);
916 isl_access_info_free(acc
);
919 isl_map_free(domain_map
);
925 /* Keep track of some information about a schedule for a given
926 * access. In particular, keep track of which dimensions
927 * have a constant value and of the actual constant values.
929 struct isl_sched_info
{
934 static void sched_info_free(__isl_take
struct isl_sched_info
*info
)
938 isl_vec_free(info
->cst
);
943 /* Extract information on the constant dimensions of the schedule
944 * for a given access. The "map" is of the form
948 * with S the schedule domain, D the iteration domain and A the data domain.
950 static __isl_give
struct isl_sched_info
*sched_info_alloc(
951 __isl_keep isl_map
*map
)
955 struct isl_sched_info
*info
;
961 dim
= isl_dim_unwrap(isl_dim_domain(isl_map_get_dim(map
)));
964 n
= isl_dim_size(dim
, isl_dim_in
);
967 ctx
= isl_map_get_ctx(map
);
968 info
= isl_alloc_type(ctx
, struct isl_sched_info
);
971 info
->is_cst
= isl_alloc_array(ctx
, int, n
);
972 info
->cst
= isl_vec_alloc(ctx
, n
);
973 if (!info
->is_cst
|| !info
->cst
)
976 for (i
= 0; i
< n
; ++i
)
977 info
->is_cst
[i
] = isl_map_plain_is_fixed(map
, isl_dim_in
, i
,
982 sched_info_free(info
);
986 struct isl_compute_flow_data
{
987 isl_union_map
*must_source
;
988 isl_union_map
*may_source
;
989 isl_union_map
*must_dep
;
990 isl_union_map
*may_dep
;
991 isl_union_map
*must_no_source
;
992 isl_union_map
*may_no_source
;
997 struct isl_sched_info
*sink_info
;
998 struct isl_sched_info
**source_info
;
999 isl_access_info
*accesses
;
1002 static int count_matching_array(__isl_take isl_map
*map
, void *user
)
1006 struct isl_compute_flow_data
*data
;
1008 data
= (struct isl_compute_flow_data
*)user
;
1010 dim
= isl_dim_range(isl_map_get_dim(map
));
1012 eq
= isl_dim_equal(dim
, data
->dim
);
1025 static int collect_matching_array(__isl_take isl_map
*map
, void *user
)
1029 struct isl_sched_info
*info
;
1030 struct isl_compute_flow_data
*data
;
1032 data
= (struct isl_compute_flow_data
*)user
;
1034 dim
= isl_dim_range(isl_map_get_dim(map
));
1036 eq
= isl_dim_equal(dim
, data
->dim
);
1047 info
= sched_info_alloc(map
);
1048 data
->source_info
[data
->count
] = info
;
1050 data
->accesses
= isl_access_info_add_source(data
->accesses
,
1051 map
, data
->must
, info
);
1061 /* Determine the shared nesting level and the "textual order" of
1062 * the given accesses.
1064 * We first determine the minimal schedule dimension for both accesses.
1066 * If among those dimensions, we can find one where both have a fixed
1067 * value and if moreover those values are different, then the previous
1068 * dimension is the last shared nesting level and the textual order
1069 * is determined based on the order of the fixed values.
1070 * If no such fixed values can be found, then we set the shared
1071 * nesting level to the minimal schedule dimension, with no textual ordering.
1073 static int before(void *first
, void *second
)
1075 struct isl_sched_info
*info1
= first
;
1076 struct isl_sched_info
*info2
= second
;
1080 n1
= info1
->cst
->size
;
1081 n2
= info2
->cst
->size
;
1086 for (i
= 0; i
< n1
; ++i
) {
1087 if (!info1
->is_cst
[i
])
1089 if (!info2
->is_cst
[i
])
1091 if (isl_int_eq(info1
->cst
->el
[i
], info2
->cst
->el
[i
]))
1093 return 2 * i
+ isl_int_lt(info1
->cst
->el
[i
], info2
->cst
->el
[i
]);
1099 /* Given a sink access, look for all the source accesses that access
1100 * the same array and perform dataflow analysis on them using
1101 * isl_access_info_compute_flow.
1103 static int compute_flow(__isl_take isl_map
*map
, void *user
)
1107 struct isl_compute_flow_data
*data
;
1110 data
= (struct isl_compute_flow_data
*)user
;
1112 ctx
= isl_map_get_ctx(map
);
1114 data
->accesses
= NULL
;
1115 data
->sink_info
= NULL
;
1116 data
->source_info
= NULL
;
1118 data
->dim
= isl_dim_range(isl_map_get_dim(map
));
1120 if (isl_union_map_foreach_map(data
->must_source
,
1121 &count_matching_array
, data
) < 0)
1123 if (isl_union_map_foreach_map(data
->may_source
,
1124 &count_matching_array
, data
) < 0)
1127 data
->sink_info
= sched_info_alloc(map
);
1128 data
->source_info
= isl_calloc_array(ctx
, struct isl_sched_info
*,
1131 data
->accesses
= isl_access_info_alloc(isl_map_copy(map
),
1132 data
->sink_info
, &before
, data
->count
);
1133 if (!data
->sink_info
|| !data
->source_info
|| !data
->accesses
)
1137 if (isl_union_map_foreach_map(data
->must_source
,
1138 &collect_matching_array
, data
) < 0)
1141 if (isl_union_map_foreach_map(data
->may_source
,
1142 &collect_matching_array
, data
) < 0)
1145 flow
= isl_access_info_compute_flow(data
->accesses
);
1146 data
->accesses
= NULL
;
1151 data
->must_no_source
= isl_union_map_union(data
->must_no_source
,
1152 isl_union_map_from_map(isl_flow_get_no_source(flow
, 1)));
1153 data
->may_no_source
= isl_union_map_union(data
->may_no_source
,
1154 isl_union_map_from_map(isl_flow_get_no_source(flow
, 0)));
1156 for (i
= 0; i
< flow
->n_source
; ++i
) {
1158 dep
= isl_union_map_from_map(isl_map_copy(flow
->dep
[i
].map
));
1159 if (flow
->dep
[i
].must
)
1160 data
->must_dep
= isl_union_map_union(data
->must_dep
, dep
);
1162 data
->may_dep
= isl_union_map_union(data
->may_dep
, dep
);
1165 isl_flow_free(flow
);
1167 sched_info_free(data
->sink_info
);
1168 if (data
->source_info
) {
1169 for (i
= 0; i
< data
->count
; ++i
)
1170 sched_info_free(data
->source_info
[i
]);
1171 free(data
->source_info
);
1173 isl_dim_free(data
->dim
);
1178 isl_access_info_free(data
->accesses
);
1179 sched_info_free(data
->sink_info
);
1180 if (data
->source_info
) {
1181 for (i
= 0; i
< data
->count
; ++i
)
1182 sched_info_free(data
->source_info
[i
]);
1183 free(data
->source_info
);
1185 isl_dim_free(data
->dim
);
1191 /* Given a collection of "sink" and "source" accesses,
1192 * compute for each iteration of a sink access
1193 * and for each element accessed by that iteration,
1194 * the source access in the list that last accessed the
1195 * element accessed by the sink access before this sink access.
1196 * Each access is given as a map from the loop iterators
1197 * to the array indices.
1198 * The result is a relations between source and sink
1199 * iterations and a subset of the domain of the sink accesses,
1200 * corresponding to those iterations that access an element
1201 * not previously accessed.
1203 * We first prepend the schedule dimensions to the domain
1204 * of the accesses so that we can easily compare their relative order.
1205 * Then we consider each sink access individually in compute_flow.
1207 int isl_union_map_compute_flow(__isl_take isl_union_map
*sink
,
1208 __isl_take isl_union_map
*must_source
,
1209 __isl_take isl_union_map
*may_source
,
1210 __isl_take isl_union_map
*schedule
,
1211 __isl_give isl_union_map
**must_dep
, __isl_give isl_union_map
**may_dep
,
1212 __isl_give isl_union_map
**must_no_source
,
1213 __isl_give isl_union_map
**may_no_source
)
1216 isl_union_map
*range_map
= NULL
;
1217 struct isl_compute_flow_data data
;
1219 sink
= isl_union_map_align_params(sink
,
1220 isl_union_map_get_dim(must_source
));
1221 sink
= isl_union_map_align_params(sink
,
1222 isl_union_map_get_dim(may_source
));
1223 sink
= isl_union_map_align_params(sink
,
1224 isl_union_map_get_dim(schedule
));
1225 dim
= isl_union_map_get_dim(sink
);
1226 must_source
= isl_union_map_align_params(must_source
, isl_dim_copy(dim
));
1227 may_source
= isl_union_map_align_params(may_source
, isl_dim_copy(dim
));
1228 schedule
= isl_union_map_align_params(schedule
, isl_dim_copy(dim
));
1230 schedule
= isl_union_map_reverse(schedule
);
1231 range_map
= isl_union_map_range_map(schedule
);
1232 schedule
= isl_union_map_reverse(isl_union_map_copy(range_map
));
1233 sink
= isl_union_map_apply_domain(sink
, isl_union_map_copy(schedule
));
1234 must_source
= isl_union_map_apply_domain(must_source
,
1235 isl_union_map_copy(schedule
));
1236 may_source
= isl_union_map_apply_domain(may_source
, schedule
);
1238 data
.must_source
= must_source
;
1239 data
.may_source
= may_source
;
1240 data
.must_dep
= must_dep
?
1241 isl_union_map_empty(isl_dim_copy(dim
)) : NULL
;
1242 data
.may_dep
= may_dep
? isl_union_map_empty(isl_dim_copy(dim
)) : NULL
;
1243 data
.must_no_source
= must_no_source
?
1244 isl_union_map_empty(isl_dim_copy(dim
)) : NULL
;
1245 data
.may_no_source
= may_no_source
?
1246 isl_union_map_empty(isl_dim_copy(dim
)) : NULL
;
1250 if (isl_union_map_foreach_map(sink
, &compute_flow
, &data
) < 0)
1253 isl_union_map_free(sink
);
1254 isl_union_map_free(must_source
);
1255 isl_union_map_free(may_source
);
1258 data
.must_dep
= isl_union_map_apply_domain(data
.must_dep
,
1259 isl_union_map_copy(range_map
));
1260 data
.must_dep
= isl_union_map_apply_range(data
.must_dep
,
1261 isl_union_map_copy(range_map
));
1262 *must_dep
= data
.must_dep
;
1265 data
.may_dep
= isl_union_map_apply_domain(data
.may_dep
,
1266 isl_union_map_copy(range_map
));
1267 data
.may_dep
= isl_union_map_apply_range(data
.may_dep
,
1268 isl_union_map_copy(range_map
));
1269 *may_dep
= data
.may_dep
;
1271 if (must_no_source
) {
1272 data
.must_no_source
= isl_union_map_apply_domain(
1273 data
.must_no_source
, isl_union_map_copy(range_map
));
1274 *must_no_source
= data
.must_no_source
;
1276 if (may_no_source
) {
1277 data
.may_no_source
= isl_union_map_apply_domain(
1278 data
.may_no_source
, isl_union_map_copy(range_map
));
1279 *may_no_source
= data
.may_no_source
;
1282 isl_union_map_free(range_map
);
1286 isl_union_map_free(range_map
);
1287 isl_union_map_free(sink
);
1288 isl_union_map_free(must_source
);
1289 isl_union_map_free(may_source
);
1290 isl_union_map_free(data
.must_dep
);
1291 isl_union_map_free(data
.may_dep
);
1292 isl_union_map_free(data
.must_no_source
);
1293 isl_union_map_free(data
.may_no_source
);
1300 *must_no_source
= NULL
;
1302 *may_no_source
= NULL
;