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
18 /* A private structure to keep track of a mapping together with
19 * a user-specified identifier and a boolean indicating whether
20 * the map represents a must or may access/dependence.
22 struct isl_labeled_map
{
28 /* A structure containing the input for dependence analysis:
30 * - n_must + n_may (<= max_source) sources
31 * - a function for determining the relative order of sources and sink
32 * The must sources are placed before the may sources.
34 struct isl_access_info
{
35 struct isl_labeled_map sink
;
36 isl_access_level_before level_before
;
40 struct isl_labeled_map source
[1];
43 /* A structure containing the output of dependence analysis:
44 * - n_source dependences
45 * - a subset of the sink for which definitely no source could be found
46 * - a subset of the sink for which possibly no source could be found
49 isl_set
*must_no_source
;
50 isl_set
*may_no_source
;
52 struct isl_labeled_map
*dep
;
55 /* Construct an isl_access_info structure and fill it up with
56 * the given data. The number of sources is set to 0.
58 __isl_give isl_access_info
*isl_access_info_alloc(__isl_take isl_map
*sink
,
59 void *sink_user
, isl_access_level_before fn
, int max_source
)
62 struct isl_access_info
*acc
;
67 ctx
= isl_map_get_ctx(sink
);
68 isl_assert(ctx
, max_source
>= 0, goto error
);
70 acc
= isl_alloc(ctx
, struct isl_access_info
,
71 sizeof(struct isl_access_info
) +
72 (max_source
- 1) * sizeof(struct isl_labeled_map
));
77 acc
->sink
.data
= sink_user
;
78 acc
->level_before
= fn
;
79 acc
->max_source
= max_source
;
89 /* Free the given isl_access_info structure.
91 void isl_access_info_free(__isl_take isl_access_info
*acc
)
97 isl_map_free(acc
->sink
.map
);
98 for (i
= 0; i
< acc
->n_must
+ acc
->n_may
; ++i
)
99 isl_map_free(acc
->source
[i
].map
);
103 /* Add another source to an isl_access_info structure, making
104 * sure the "must" sources are placed before the "may" sources.
105 * This function may be called at most max_source times on a
106 * given isl_access_info structure, with max_source as specified
107 * in the call to isl_access_info_alloc that constructed the structure.
109 __isl_give isl_access_info
*isl_access_info_add_source(
110 __isl_take isl_access_info
*acc
, __isl_take isl_map
*source
,
111 int must
, void *source_user
)
117 ctx
= isl_map_get_ctx(acc
->sink
.map
);
118 isl_assert(ctx
, acc
->n_must
+ acc
->n_may
< acc
->max_source
, goto error
);
122 acc
->source
[acc
->n_must
+ acc
->n_may
] =
123 acc
->source
[acc
->n_must
];
124 acc
->source
[acc
->n_must
].map
= source
;
125 acc
->source
[acc
->n_must
].data
= source_user
;
126 acc
->source
[acc
->n_must
].must
= 1;
129 acc
->source
[acc
->n_must
+ acc
->n_may
].map
= source
;
130 acc
->source
[acc
->n_must
+ acc
->n_may
].data
= source_user
;
131 acc
->source
[acc
->n_must
+ acc
->n_may
].must
= 0;
137 isl_map_free(source
);
138 isl_access_info_free(acc
);
142 /* A temporary structure used while sorting the accesses in an isl_access_info.
144 struct isl_access_sort_info
{
145 struct isl_map
*source_map
;
147 struct isl_access_info
*acc
;
150 /* Return -n, 0 or n (with n a positive value), depending on whether
151 * the source access identified by p1 should be sorted before, together
152 * or after that identified by p2.
154 * If p1 and p2 share a different number of levels with the sink,
155 * then the one with the lowest number of shared levels should be
157 * If they both share no levels, then the order is irrelevant.
158 * Otherwise, if p1 appears before p2, then it should be sorted first.
160 static int access_sort_cmp(const void *p1
, const void *p2
)
162 const struct isl_access_sort_info
*i1
, *i2
;
164 i1
= (const struct isl_access_sort_info
*) p1
;
165 i2
= (const struct isl_access_sort_info
*) p2
;
167 level1
= i1
->acc
->level_before(i1
->source_data
, i1
->acc
->sink
.data
);
168 level2
= i2
->acc
->level_before(i2
->source_data
, i2
->acc
->sink
.data
);
170 if (level1
!= level2
|| !level1
)
171 return level1
- level2
;
173 level1
= i1
->acc
->level_before(i1
->source_data
, i2
->source_data
);
175 return (level1
% 2) ? -1 : 1;
178 /* Sort the must source accesses in order of increasing number of shared
179 * levels with the sink access.
180 * Source accesses with the same number of shared levels are sorted
181 * in their textual order.
183 static __isl_give isl_access_info
*isl_access_info_sort_sources(
184 __isl_take isl_access_info
*acc
)
188 struct isl_access_sort_info
*array
;
192 if (acc
->n_must
<= 1)
195 ctx
= isl_map_get_ctx(acc
->sink
.map
);
196 array
= isl_alloc_array(ctx
, struct isl_access_sort_info
, acc
->n_must
);
200 for (i
= 0; i
< acc
->n_must
; ++i
) {
201 array
[i
].source_map
= acc
->source
[i
].map
;
202 array
[i
].source_data
= acc
->source
[i
].data
;
206 qsort(array
, acc
->n_must
, sizeof(struct isl_access_sort_info
),
209 for (i
= 0; i
< acc
->n_must
; ++i
) {
210 acc
->source
[i
].map
= array
[i
].source_map
;
211 acc
->source
[i
].data
= array
[i
].source_data
;
218 isl_access_info_free(acc
);
222 /* Initialize an empty isl_flow structure corresponding to a given
223 * isl_access_info structure.
224 * For each must access, two dependences are created (initialized
225 * to the empty relation), one for the resulting must dependences
226 * and one for the resulting may dependences. May accesses can
227 * only lead to may dependences, so only one dependence is created
229 * This function is private as isl_flow structures are only supposed
230 * to be created by isl_access_info_compute_flow.
232 static __isl_give isl_flow
*isl_flow_alloc(__isl_keep isl_access_info
*acc
)
236 struct isl_flow
*dep
;
241 ctx
= isl_map_get_ctx(acc
->sink
.map
);
242 dep
= isl_calloc_type(ctx
, struct isl_flow
);
246 dep
->dep
= isl_calloc_array(ctx
, struct isl_labeled_map
,
247 2 * acc
->n_must
+ acc
->n_may
);
251 dep
->n_source
= 2 * acc
->n_must
+ acc
->n_may
;
252 for (i
= 0; i
< acc
->n_must
; ++i
) {
254 dim
= isl_dim_join(isl_map_get_dim(acc
->source
[i
].map
),
255 isl_dim_reverse(isl_map_get_dim(acc
->sink
.map
)));
256 dep
->dep
[2 * i
].map
= isl_map_empty(dim
);
257 dep
->dep
[2 * i
+ 1].map
= isl_map_copy(dep
->dep
[2 * i
].map
);
258 dep
->dep
[2 * i
].data
= acc
->source
[i
].data
;
259 dep
->dep
[2 * i
+ 1].data
= acc
->source
[i
].data
;
260 dep
->dep
[2 * i
].must
= 1;
261 dep
->dep
[2 * i
+ 1].must
= 0;
262 if (!dep
->dep
[2 * i
].map
|| !dep
->dep
[2 * i
+ 1].map
)
265 for (i
= acc
->n_must
; i
< acc
->n_must
+ acc
->n_may
; ++i
) {
267 dim
= isl_dim_join(isl_map_get_dim(acc
->source
[i
].map
),
268 isl_dim_reverse(isl_map_get_dim(acc
->sink
.map
)));
269 dep
->dep
[acc
->n_must
+ i
].map
= isl_map_empty(dim
);
270 dep
->dep
[acc
->n_must
+ i
].data
= acc
->source
[i
].data
;
271 dep
->dep
[acc
->n_must
+ i
].must
= 0;
272 if (!dep
->dep
[acc
->n_must
+ i
].map
)
282 /* Iterate over all sources and for each resulting flow dependence
283 * that is not empty, call the user specfied function.
284 * The second argument in this function call identifies the source,
285 * while the third argument correspond to the final argument of
286 * the isl_flow_foreach call.
288 int isl_flow_foreach(__isl_keep isl_flow
*deps
,
289 int (*fn
)(__isl_take isl_map
*dep
, int must
, void *dep_user
, void *user
),
297 for (i
= 0; i
< deps
->n_source
; ++i
) {
298 if (isl_map_fast_is_empty(deps
->dep
[i
].map
))
300 if (fn(isl_map_copy(deps
->dep
[i
].map
), deps
->dep
[i
].must
,
301 deps
->dep
[i
].data
, user
) < 0)
308 /* Return a copy of the subset of the sink for which no source could be found.
310 __isl_give isl_set
*isl_flow_get_no_source(__isl_keep isl_flow
*deps
, int must
)
316 return isl_set_copy(deps
->must_no_source
);
318 return isl_set_copy(deps
->may_no_source
);
321 void isl_flow_free(__isl_take isl_flow
*deps
)
327 isl_set_free(deps
->must_no_source
);
328 isl_set_free(deps
->may_no_source
);
330 for (i
= 0; i
< deps
->n_source
; ++i
)
331 isl_map_free(deps
->dep
[i
].map
);
337 /* Return a map that enforces that the domain iteration occurs after
338 * the range iteration at the given level.
339 * If level is odd, then the domain iteration should occur after
340 * the target iteration in their shared level/2 outermost loops.
341 * In this case we simply need to enforce that these outermost
342 * loop iterations are the same.
343 * If level is even, then the loop iterator of the domain should
344 * be greater than the loop iterator of the range at the last
345 * of the level/2 shared loops, i.e., loop level/2 - 1.
347 static __isl_give isl_map
*after_at_level(struct isl_dim
*dim
, int level
)
349 struct isl_basic_map
*bmap
;
352 bmap
= isl_basic_map_equal(dim
, level
/2);
354 bmap
= isl_basic_map_more_at(dim
, level
/2 - 1);
356 return isl_map_from_basic_map(bmap
);
359 /* Compute the last iteration of must source j that precedes the sink
360 * at the given level for sink iterations in set_C.
361 * The subset of set_C for which no such iteration can be found is returned
364 static struct isl_map
*last_source(struct isl_access_info
*acc
,
365 struct isl_set
*set_C
,
366 int j
, int level
, struct isl_set
**empty
)
368 struct isl_map
*read_map
;
369 struct isl_map
*write_map
;
370 struct isl_map
*dep_map
;
371 struct isl_map
*after
;
372 struct isl_map
*result
;
374 read_map
= isl_map_copy(acc
->sink
.map
);
375 write_map
= isl_map_copy(acc
->source
[j
].map
);
376 write_map
= isl_map_reverse(write_map
);
377 dep_map
= isl_map_apply_range(read_map
, write_map
);
378 after
= after_at_level(isl_map_get_dim(dep_map
), level
);
379 dep_map
= isl_map_intersect(dep_map
, after
);
380 result
= isl_map_partial_lexmax(dep_map
, set_C
, empty
);
381 result
= isl_map_reverse(result
);
386 /* For a given mapping between iterations of must source j and iterations
387 * of the sink, compute the last iteration of must source k preceding
388 * the sink at level before_level for any of the sink iterations,
389 * but following the corresponding iteration of must source j at level
392 static struct isl_map
*last_later_source(struct isl_access_info
*acc
,
393 struct isl_map
*old_map
,
394 int j
, int before_level
,
395 int k
, int after_level
,
396 struct isl_set
**empty
)
399 struct isl_set
*set_C
;
400 struct isl_map
*read_map
;
401 struct isl_map
*write_map
;
402 struct isl_map
*dep_map
;
403 struct isl_map
*after_write
;
404 struct isl_map
*before_read
;
405 struct isl_map
*result
;
407 set_C
= isl_map_range(isl_map_copy(old_map
));
408 read_map
= isl_map_copy(acc
->sink
.map
);
409 write_map
= isl_map_copy(acc
->source
[k
].map
);
411 write_map
= isl_map_reverse(write_map
);
412 dep_map
= isl_map_apply_range(read_map
, write_map
);
413 dim
= isl_dim_join(isl_map_get_dim(acc
->source
[k
].map
),
414 isl_dim_reverse(isl_map_get_dim(acc
->source
[j
].map
)));
415 after_write
= after_at_level(dim
, after_level
);
416 after_write
= isl_map_apply_range(after_write
, old_map
);
417 after_write
= isl_map_reverse(after_write
);
418 dep_map
= isl_map_intersect(dep_map
, after_write
);
419 before_read
= after_at_level(isl_map_get_dim(dep_map
), before_level
);
420 dep_map
= isl_map_intersect(dep_map
, before_read
);
421 result
= isl_map_partial_lexmax(dep_map
, set_C
, empty
);
422 result
= isl_map_reverse(result
);
427 /* Given a shared_level between two accesses, return 1 if the
428 * the first can precede the second at the requested target_level.
429 * If the target level is odd, i.e., refers to a statement level
430 * dimension, then first needs to precede second at the requested
431 * level, i.e., shared_level must be equal to target_level.
432 * If the target level is odd, then the two loops should share
433 * at least the requested number of outer loops.
435 static int can_precede_at_level(int shared_level
, int target_level
)
437 if (shared_level
< target_level
)
439 if ((target_level
% 2) && shared_level
> target_level
)
444 /* Given a possible flow dependence temp_rel[j] between source j and the sink
445 * at level sink_level, remove those elements for which
446 * there is an iteration of another source k < j that is closer to the sink.
447 * The flow dependences temp_rel[k] are updated with the improved sources.
448 * Any improved source needs to precede the sink at the same level
449 * and needs to follow source j at the same or a deeper level.
450 * The lower this level, the later the execution date of source k.
451 * We therefore consider lower levels first.
453 * If temp_rel[j] is empty, then there can be no improvement and
454 * we return immediately.
456 static int intermediate_sources(__isl_keep isl_access_info
*acc
,
457 struct isl_map
**temp_rel
, int j
, int sink_level
)
460 int depth
= 2 * isl_map_dim(acc
->source
[j
].map
, isl_dim_in
) + 1;
462 if (isl_map_fast_is_empty(temp_rel
[j
]))
465 for (k
= j
- 1; k
>= 0; --k
) {
467 plevel
= acc
->level_before(acc
->source
[k
].data
, acc
->sink
.data
);
468 if (!can_precede_at_level(plevel
, sink_level
))
471 plevel2
= acc
->level_before(acc
->source
[j
].data
,
472 acc
->source
[k
].data
);
474 for (level
= sink_level
; level
<= depth
; ++level
) {
476 struct isl_set
*trest
;
477 struct isl_map
*copy
;
479 if (!can_precede_at_level(plevel2
, level
))
482 copy
= isl_map_copy(temp_rel
[j
]);
483 T
= last_later_source(acc
, copy
, j
, sink_level
, k
,
485 if (isl_map_fast_is_empty(T
)) {
490 temp_rel
[j
] = isl_map_intersect_range(temp_rel
[j
], trest
);
491 temp_rel
[k
] = isl_map_union_disjoint(temp_rel
[k
], T
);
498 /* Compute all iterations of may source j that precedes the sink at the given
499 * level for sink iterations in set_C.
501 static __isl_give isl_map
*all_sources(__isl_keep isl_access_info
*acc
,
502 __isl_take isl_set
*set_C
, int j
, int level
)
509 read_map
= isl_map_copy(acc
->sink
.map
);
510 read_map
= isl_map_intersect_domain(read_map
, set_C
);
511 write_map
= isl_map_copy(acc
->source
[acc
->n_must
+ j
].map
);
512 write_map
= isl_map_reverse(write_map
);
513 dep_map
= isl_map_apply_range(read_map
, write_map
);
514 after
= after_at_level(isl_map_get_dim(dep_map
), level
);
515 dep_map
= isl_map_intersect(dep_map
, after
);
517 return isl_map_reverse(dep_map
);
520 /* For a given mapping between iterations of must source k and iterations
521 * of the sink, compute the all iteration of may source j preceding
522 * the sink at level before_level for any of the sink iterations,
523 * but following the corresponding iteration of must source k at level
526 static __isl_give isl_map
*all_later_sources(__isl_keep isl_access_info
*acc
,
527 __isl_keep isl_map
*old_map
,
528 int j
, int before_level
, int k
, int after_level
)
535 isl_map
*after_write
;
536 isl_map
*before_read
;
538 set_C
= isl_map_range(isl_map_copy(old_map
));
539 read_map
= isl_map_copy(acc
->sink
.map
);
540 read_map
= isl_map_intersect_domain(read_map
, set_C
);
541 write_map
= isl_map_copy(acc
->source
[acc
->n_must
+ j
].map
);
543 write_map
= isl_map_reverse(write_map
);
544 dep_map
= isl_map_apply_range(read_map
, write_map
);
545 dim
= isl_dim_join(isl_map_get_dim(acc
->source
[acc
->n_must
+ j
].map
),
546 isl_dim_reverse(isl_map_get_dim(acc
->source
[k
].map
)));
547 after_write
= after_at_level(dim
, after_level
);
548 after_write
= isl_map_apply_range(after_write
, old_map
);
549 after_write
= isl_map_reverse(after_write
);
550 dep_map
= isl_map_intersect(dep_map
, after_write
);
551 before_read
= after_at_level(isl_map_get_dim(dep_map
), before_level
);
552 dep_map
= isl_map_intersect(dep_map
, before_read
);
553 return isl_map_reverse(dep_map
);
556 /* Given the must and may dependence relations for the must accesses
557 * for level sink_level, check if there are any accesses of may access j
558 * that occur in between and return their union.
559 * If some of these accesses are intermediate with respect to
560 * (previously thought to be) must dependences, then these
561 * must dependences are turned into may dependences.
563 static __isl_give isl_map
*all_intermediate_sources(
564 __isl_keep isl_access_info
*acc
, __isl_take isl_map
*map
,
565 struct isl_map
**must_rel
, struct isl_map
**may_rel
,
566 int j
, int sink_level
)
569 int depth
= 2 * isl_map_dim(acc
->source
[acc
->n_must
+ j
].map
,
572 for (k
= 0; k
< acc
->n_must
; ++k
) {
575 if (isl_map_fast_is_empty(may_rel
[k
]) &&
576 isl_map_fast_is_empty(must_rel
[k
]))
579 plevel
= acc
->level_before(acc
->source
[k
].data
,
580 acc
->source
[acc
->n_must
+ j
].data
);
582 for (level
= sink_level
; level
<= depth
; ++level
) {
587 if (!can_precede_at_level(plevel
, level
))
590 copy
= isl_map_copy(may_rel
[k
]);
591 T
= all_later_sources(acc
, copy
, j
, sink_level
, k
, level
);
592 map
= isl_map_union(map
, T
);
594 copy
= isl_map_copy(must_rel
[k
]);
595 T
= all_later_sources(acc
, copy
, j
, sink_level
, k
, level
);
596 ran
= isl_map_range(isl_map_copy(T
));
597 map
= isl_map_union(map
, T
);
598 may_rel
[k
] = isl_map_union_disjoint(may_rel
[k
],
599 isl_map_intersect_range(isl_map_copy(must_rel
[k
]),
601 T
= isl_map_from_domain_and_range(
603 isl_dim_domain(isl_map_get_dim(must_rel
[k
]))),
605 must_rel
[k
] = isl_map_subtract(must_rel
[k
], T
);
612 /* Compute dependences for the case where all accesses are "may"
613 * accesses, which boils down to computing memory based dependences.
614 * The generic algorithm would also work in this case, but it would
615 * be overkill to use it.
617 static __isl_give isl_flow
*compute_mem_based_dependences(
618 __isl_take isl_access_info
*acc
)
625 res
= isl_flow_alloc(acc
);
629 mustdo
= isl_map_domain(isl_map_copy(acc
->sink
.map
));
630 maydo
= isl_set_copy(mustdo
);
632 for (i
= 0; i
< acc
->n_may
; ++i
) {
639 plevel
= acc
->level_before(acc
->source
[i
].data
, acc
->sink
.data
);
640 is_before
= plevel
& 1;
643 dim
= isl_map_get_dim(res
->dep
[i
].map
);
645 before
= isl_map_lex_le_first(dim
, plevel
);
647 before
= isl_map_lex_lt_first(dim
, plevel
);
648 dep
= isl_map_apply_range(isl_map_copy(acc
->source
[i
].map
),
649 isl_map_reverse(isl_map_copy(acc
->sink
.map
)));
650 dep
= isl_map_intersect(dep
, before
);
651 mustdo
= isl_set_subtract(mustdo
,
652 isl_map_range(isl_map_copy(dep
)));
653 res
->dep
[i
].map
= isl_map_union(res
->dep
[i
].map
, dep
);
656 res
->may_no_source
= isl_set_subtract(maydo
, isl_set_copy(mustdo
));
657 res
->must_no_source
= mustdo
;
659 isl_access_info_free(acc
);
663 isl_access_info_free(acc
);
667 /* Compute dependences for the case where there is at least one
670 * The core algorithm considers all levels in which a source may precede
671 * the sink, where a level may either be a statement level or a loop level.
672 * The outermost statement level is 1, the first loop level is 2, etc...
673 * The algorithm basically does the following:
674 * for all levels l of the read access from innermost to outermost
675 * for all sources w that may precede the sink access at that level
676 * compute the last iteration of the source that precedes the sink access
678 * add result to possible last accesses at level l of source w
679 * for all sources w2 that we haven't considered yet at this level that may
680 * also precede the sink access
681 * for all levels l2 of w from l to innermost
682 * for all possible last accesses dep of w at l
683 * compute last iteration of w2 between the source and sink
685 * add result to possible last accesses at level l of write w2
686 * and replace possible last accesses dep by the remainder
689 * The above algorithm is applied to the must access. During the course
690 * of the algorithm, we keep track of sink iterations that still
691 * need to be considered. These iterations are split into those that
692 * haven't been matched to any source access (mustdo) and those that have only
693 * been matched to may accesses (maydo).
694 * At the end of each level, we also consider the may accesses.
695 * In particular, we consider may accesses that precede the remaining
696 * sink iterations, moving elements from mustdo to maydo when appropriate,
697 * and may accesses that occur between a must source and a sink of any
698 * dependences found at the current level, turning must dependences into
699 * may dependences when appropriate.
702 static __isl_give isl_flow
*compute_val_based_dependences(
703 __isl_take isl_access_info
*acc
)
707 isl_set
*mustdo
= NULL
;
708 isl_set
*maydo
= NULL
;
711 isl_map
**must_rel
= NULL
;
712 isl_map
**may_rel
= NULL
;
714 acc
= isl_access_info_sort_sources(acc
);
718 res
= isl_flow_alloc(acc
);
721 ctx
= isl_map_get_ctx(acc
->sink
.map
);
723 depth
= 2 * isl_map_dim(acc
->sink
.map
, isl_dim_in
) + 1;
724 mustdo
= isl_map_domain(isl_map_copy(acc
->sink
.map
));
725 maydo
= isl_set_empty_like(mustdo
);
726 if (!mustdo
|| !maydo
)
728 if (isl_set_fast_is_empty(mustdo
))
731 must_rel
= isl_alloc_array(ctx
, struct isl_map
*, acc
->n_must
);
732 may_rel
= isl_alloc_array(ctx
, struct isl_map
*, acc
->n_must
);
733 if (!must_rel
|| !may_rel
)
736 for (level
= depth
; level
>= 1; --level
) {
737 for (j
= acc
->n_must
-1; j
>=0; --j
) {
738 must_rel
[j
] = isl_map_empty_like(res
->dep
[j
].map
);
739 may_rel
[j
] = isl_map_copy(must_rel
[j
]);
742 for (j
= acc
->n_must
- 1; j
>= 0; --j
) {
744 struct isl_set
*rest
;
747 plevel
= acc
->level_before(acc
->source
[j
].data
,
749 if (!can_precede_at_level(plevel
, level
))
752 T
= last_source(acc
, mustdo
, j
, level
, &rest
);
753 must_rel
[j
] = isl_map_union_disjoint(must_rel
[j
], T
);
756 intermediate_sources(acc
, must_rel
, j
, level
);
758 T
= last_source(acc
, maydo
, j
, level
, &rest
);
759 may_rel
[j
] = isl_map_union_disjoint(may_rel
[j
], T
);
762 intermediate_sources(acc
, may_rel
, j
, level
);
764 if (isl_set_fast_is_empty(mustdo
) &&
765 isl_set_fast_is_empty(maydo
))
768 for (j
= j
- 1; j
>= 0; --j
) {
771 plevel
= acc
->level_before(acc
->source
[j
].data
,
773 if (!can_precede_at_level(plevel
, level
))
776 intermediate_sources(acc
, must_rel
, j
, level
);
777 intermediate_sources(acc
, may_rel
, j
, level
);
780 for (j
= 0; j
< acc
->n_may
; ++j
) {
785 plevel
= acc
->level_before(acc
->source
[acc
->n_must
+ j
].data
,
787 if (!can_precede_at_level(plevel
, level
))
790 T
= all_sources(acc
, isl_set_copy(maydo
), j
, level
);
791 res
->dep
[2 * acc
->n_must
+ j
].map
=
792 isl_map_union(res
->dep
[2 * acc
->n_must
+ j
].map
, T
);
793 T
= all_sources(acc
, isl_set_copy(mustdo
), j
, level
);
794 ran
= isl_map_range(isl_map_copy(T
));
795 res
->dep
[2 * acc
->n_must
+ j
].map
=
796 isl_map_union(res
->dep
[2 * acc
->n_must
+ j
].map
, T
);
797 mustdo
= isl_set_subtract(mustdo
, isl_set_copy(ran
));
798 maydo
= isl_set_union_disjoint(maydo
, ran
);
800 T
= res
->dep
[2 * acc
->n_must
+ j
].map
;
801 T
= all_intermediate_sources(acc
, T
, must_rel
, may_rel
,
803 res
->dep
[2 * acc
->n_must
+ j
].map
= T
;
806 for (j
= acc
->n_must
- 1; j
>= 0; --j
) {
807 res
->dep
[2 * j
].map
=
808 isl_map_union_disjoint(res
->dep
[2 * j
].map
,
810 res
->dep
[2 * j
+ 1].map
=
811 isl_map_union_disjoint(res
->dep
[2 * j
+ 1].map
,
815 if (isl_set_fast_is_empty(mustdo
) &&
816 isl_set_fast_is_empty(maydo
))
823 res
->must_no_source
= mustdo
;
824 res
->may_no_source
= maydo
;
825 isl_access_info_free(acc
);
828 isl_access_info_free(acc
);
830 isl_set_free(mustdo
);
837 /* Given a "sink" access, a list of n "source" accesses,
838 * compute for each iteration of the sink access
839 * and for each element accessed by that iteration,
840 * the source access in the list that last accessed the
841 * element accessed by the sink access before this sink access.
842 * Each access is given as a map from the loop iterators
843 * to the array indices.
844 * The result is a list of n relations between source and sink
845 * iterations and a subset of the domain of the sink access,
846 * corresponding to those iterations that access an element
847 * not previously accessed.
849 * To deal with multi-valued sink access relations, the sink iteration
850 * domain is first extended with dimensions that correspond to the data
851 * space. After the computation is finished, these extra dimensions are
852 * projected out again.
854 __isl_give isl_flow
*isl_access_info_compute_flow(__isl_take isl_access_info
*acc
)
857 struct isl_flow
*res
;
858 isl_map
*domain_map
= NULL
;
863 domain_map
= isl_map_domain_map(isl_map_copy(acc
->sink
.map
));
864 acc
->sink
.map
= isl_map_range_map(acc
->sink
.map
);
868 if (acc
->n_must
== 0)
869 res
= compute_mem_based_dependences(acc
);
871 res
= compute_val_based_dependences(acc
);
875 for (j
= 0; j
< res
->n_source
; ++j
) {
876 res
->dep
[j
].map
= isl_map_apply_range(res
->dep
[j
].map
,
877 isl_map_copy(domain_map
));
878 if (!res
->dep
[j
].map
)
881 res
->must_no_source
= isl_set_apply(res
->must_no_source
,
882 isl_map_copy(domain_map
));
883 res
->may_no_source
= isl_set_apply(res
->may_no_source
,
884 isl_map_copy(domain_map
));
885 if (!res
->must_no_source
|| !res
->may_no_source
)
888 isl_map_free(domain_map
);
891 isl_map_free(domain_map
);
892 isl_access_info_free(acc
);
895 isl_map_free(domain_map
);
901 struct isl_compute_flow_data
{
902 isl_union_map
*must_source
;
903 isl_union_map
*may_source
;
904 isl_union_map
*must_dep
;
905 isl_union_map
*may_dep
;
906 isl_union_set
*must_no_source
;
907 isl_union_set
*may_no_source
;
913 isl_dim
**source_dim
;
914 isl_access_info
*accesses
;
917 static int count_matching_array(__isl_take isl_map
*map
, void *user
)
921 struct isl_compute_flow_data
*data
;
923 data
= (struct isl_compute_flow_data
*)user
;
925 dim
= isl_dim_range(isl_map_get_dim(map
));
927 eq
= isl_dim_equal(dim
, data
->dim
);
940 static int collect_matching_array(__isl_take isl_map
*map
, void *user
)
944 struct isl_compute_flow_data
*data
;
946 data
= (struct isl_compute_flow_data
*)user
;
948 dim
= isl_dim_range(isl_map_get_dim(map
));
950 eq
= isl_dim_equal(dim
, data
->dim
);
961 dim
= isl_dim_unwrap(isl_dim_domain(isl_map_get_dim(map
)));
962 data
->source_dim
[data
->count
] = dim
;
964 data
->accesses
= isl_access_info_add_source(data
->accesses
,
965 map
, data
->must
, dim
);
975 static int before(void *first
, void *second
)
977 isl_dim
*dim1
= first
;
978 isl_dim
*dim2
= second
;
981 n1
= isl_dim_size(dim1
, isl_dim_in
);
982 n2
= isl_dim_size(dim2
, isl_dim_in
);
987 return 2 * n1
+ (dim1
< dim2
);
990 /* Given a sink access, look for all the source accesses that access
991 * the same array and perform dataflow analysis on them using
992 * isl_access_info_compute_flow.
994 static int compute_flow(__isl_take isl_map
*map
, void *user
)
998 struct isl_compute_flow_data
*data
;
1001 data
= (struct isl_compute_flow_data
*)user
;
1003 ctx
= isl_map_get_ctx(map
);
1005 data
->accesses
= NULL
;
1006 data
->sink_dim
= NULL
;
1007 data
->source_dim
= NULL
;
1009 data
->dim
= isl_dim_range(isl_map_get_dim(map
));
1011 if (isl_union_map_foreach_map(data
->must_source
,
1012 &count_matching_array
, data
) < 0)
1014 if (isl_union_map_foreach_map(data
->may_source
,
1015 &count_matching_array
, data
) < 0)
1018 data
->sink_dim
= isl_dim_unwrap(isl_dim_domain(isl_map_get_dim(map
)));
1019 data
->source_dim
= isl_calloc_array(ctx
, isl_dim
*, data
->count
);
1021 data
->accesses
= isl_access_info_alloc(isl_map_copy(map
),
1022 data
->sink_dim
, &before
, data
->count
);
1025 if (isl_union_map_foreach_map(data
->must_source
,
1026 &collect_matching_array
, data
) < 0)
1029 if (isl_union_map_foreach_map(data
->may_source
,
1030 &collect_matching_array
, data
) < 0)
1033 flow
= isl_access_info_compute_flow(data
->accesses
);
1034 data
->accesses
= NULL
;
1039 data
->must_no_source
= isl_union_set_union(data
->must_no_source
,
1040 isl_union_set_from_set(isl_set_copy(flow
->must_no_source
)));
1041 data
->may_no_source
= isl_union_set_union(data
->may_no_source
,
1042 isl_union_set_from_set(isl_set_copy(flow
->may_no_source
)));
1044 for (i
= 0; i
< flow
->n_source
; ++i
) {
1046 dep
= isl_union_map_from_map(isl_map_copy(flow
->dep
[i
].map
));
1047 if (flow
->dep
[i
].must
)
1048 data
->must_dep
= isl_union_map_union(data
->must_dep
, dep
);
1050 data
->may_dep
= isl_union_map_union(data
->may_dep
, dep
);
1053 isl_flow_free(flow
);
1055 isl_dim_free(data
->sink_dim
);
1056 if (data
->source_dim
) {
1057 for (i
= 0; i
< data
->count
; ++i
)
1058 isl_dim_free(data
->source_dim
[i
]);
1059 free(data
->source_dim
);
1061 isl_dim_free(data
->dim
);
1066 isl_access_info_free(data
->accesses
);
1067 isl_dim_free(data
->sink_dim
);
1068 if (data
->source_dim
) {
1069 for (i
= 0; i
< data
->count
; ++i
)
1070 isl_dim_free(data
->source_dim
[i
]);
1071 free(data
->source_dim
);
1073 isl_dim_free(data
->dim
);
1079 /* Given a collection of "sink" and "source" accesses,
1080 * compute for each iteration of a sink access
1081 * and for each element accessed by that iteration,
1082 * the source access in the list that last accessed the
1083 * element accessed by the sink access before this sink access.
1084 * Each access is given as a map from the loop iterators
1085 * to the array indices.
1086 * The result is a relations between source and sink
1087 * iterations and a subset of the domain of the sink accesses,
1088 * corresponding to those iterations that access an element
1089 * not previously accessed.
1091 * We first prepend the schedule dimensions to the domain
1092 * of the accesses so that we can easily compare their relative order.
1093 * Then we consider each sink access individually in compute_flow.
1095 int isl_union_map_compute_flow(__isl_take isl_union_map
*sink
,
1096 __isl_take isl_union_map
*must_source
,
1097 __isl_take isl_union_map
*may_source
,
1098 __isl_take isl_union_map
*schedule
,
1099 __isl_give isl_union_map
**must_dep
, __isl_give isl_union_map
**may_dep
,
1100 __isl_give isl_union_set
**must_no_source
,
1101 __isl_give isl_union_set
**may_no_source
)
1104 isl_union_map
*range_map
= NULL
;
1105 struct isl_compute_flow_data data
;
1107 sink
= isl_union_map_align_params(sink
,
1108 isl_union_map_get_dim(must_source
));
1109 sink
= isl_union_map_align_params(sink
,
1110 isl_union_map_get_dim(may_source
));
1111 sink
= isl_union_map_align_params(sink
,
1112 isl_union_map_get_dim(schedule
));
1113 dim
= isl_union_map_get_dim(sink
);
1114 must_source
= isl_union_map_align_params(must_source
, isl_dim_copy(dim
));
1115 may_source
= isl_union_map_align_params(may_source
, isl_dim_copy(dim
));
1116 schedule
= isl_union_map_align_params(schedule
, isl_dim_copy(dim
));
1118 schedule
= isl_union_map_reverse(schedule
);
1119 range_map
= isl_union_map_range_map(schedule
);
1120 schedule
= isl_union_map_reverse(isl_union_map_copy(range_map
));
1121 sink
= isl_union_map_apply_domain(sink
, isl_union_map_copy(schedule
));
1122 must_source
= isl_union_map_apply_domain(must_source
,
1123 isl_union_map_copy(schedule
));
1124 may_source
= isl_union_map_apply_domain(may_source
, schedule
);
1126 data
.must_source
= must_source
;
1127 data
.may_source
= may_source
;
1128 data
.must_dep
= must_dep
?
1129 isl_union_map_empty(isl_dim_copy(dim
)) : NULL
;
1130 data
.may_dep
= may_dep
? isl_union_map_empty(isl_dim_copy(dim
)) : NULL
;
1131 data
.must_no_source
= must_no_source
?
1132 isl_union_set_empty(isl_dim_copy(dim
)) : NULL
;
1133 data
.may_no_source
= may_no_source
?
1134 isl_union_set_empty(isl_dim_copy(dim
)) : NULL
;
1138 if (isl_union_map_foreach_map(sink
, &compute_flow
, &data
) < 0)
1141 isl_union_map_free(sink
);
1142 isl_union_map_free(must_source
);
1143 isl_union_map_free(may_source
);
1146 data
.must_dep
= isl_union_map_apply_domain(data
.must_dep
,
1147 isl_union_map_copy(range_map
));
1148 data
.must_dep
= isl_union_map_apply_range(data
.must_dep
,
1149 isl_union_map_copy(range_map
));
1150 *must_dep
= data
.must_dep
;
1153 data
.may_dep
= isl_union_map_apply_domain(data
.may_dep
,
1154 isl_union_map_copy(range_map
));
1155 data
.may_dep
= isl_union_map_apply_range(data
.may_dep
,
1156 isl_union_map_copy(range_map
));
1157 *may_dep
= data
.may_dep
;
1159 if (must_no_source
) {
1160 data
.must_no_source
= isl_union_set_apply(data
.must_no_source
,
1161 isl_union_map_copy(range_map
));
1162 *must_no_source
= data
.must_no_source
;
1164 if (may_no_source
) {
1165 data
.may_no_source
= isl_union_set_apply(data
.may_no_source
,
1166 isl_union_map_copy(range_map
));
1167 *may_no_source
= data
.may_no_source
;
1170 isl_union_map_free(range_map
);
1174 isl_union_map_free(range_map
);
1175 isl_union_map_free(sink
);
1176 isl_union_map_free(must_source
);
1177 isl_union_map_free(may_source
);
1178 isl_union_map_free(data
.must_dep
);
1179 isl_union_map_free(data
.may_dep
);
1180 isl_union_set_free(data
.must_no_source
);
1181 isl_union_set_free(data
.may_no_source
);
1188 *must_no_source
= NULL
;
1190 *may_no_source
= NULL
;