Line data Source code
1 : /*
2 : * Copyright 2005-2007 Universiteit Leiden
3 : * Copyright 2008-2009 Katholieke Universiteit Leuven
4 : * Copyright 2010 INRIA Saclay
5 : * Copyright 2012 Universiteit Leiden
6 : * Copyright 2014 Ecole Normale Superieure
7 : *
8 : * Use of this software is governed by the MIT license
9 : *
10 : * Written by Sven Verdoolaege, Leiden Institute of Advanced Computer Science,
11 : * Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands
12 : * and K.U.Leuven, Departement Computerwetenschappen, Celestijnenlaan 200A,
13 : * B-3001 Leuven, Belgium
14 : * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
15 : * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
16 : * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
17 : */
18 :
19 : #include <isl/val.h>
20 : #include <isl/space.h>
21 : #include <isl/set.h>
22 : #include <isl/map.h>
23 : #include <isl/union_set.h>
24 : #include <isl/union_map.h>
25 : #include <isl/flow.h>
26 : #include <isl/schedule_node.h>
27 : #include <isl_sort.h>
28 : #include <isl/stream.h>
29 :
30 : enum isl_restriction_type {
31 : isl_restriction_type_empty,
32 : isl_restriction_type_none,
33 : isl_restriction_type_input,
34 : isl_restriction_type_output
35 : };
36 :
37 : struct isl_restriction {
38 : enum isl_restriction_type type;
39 :
40 : isl_set *source;
41 : isl_set *sink;
42 : };
43 :
44 : /* Create a restriction of the given type.
45 : */
46 0 : static __isl_give isl_restriction *isl_restriction_alloc(
47 : __isl_take isl_map *source_map, enum isl_restriction_type type)
48 : {
49 : isl_ctx *ctx;
50 : isl_restriction *restr;
51 :
52 0 : if (!source_map)
53 0 : return NULL;
54 :
55 0 : ctx = isl_map_get_ctx(source_map);
56 0 : restr = isl_calloc_type(ctx, struct isl_restriction);
57 0 : if (!restr)
58 0 : goto error;
59 :
60 0 : restr->type = type;
61 :
62 0 : isl_map_free(source_map);
63 0 : return restr;
64 : error:
65 0 : isl_map_free(source_map);
66 0 : return NULL;
67 : }
68 :
69 : /* Create a restriction that doesn't restrict anything.
70 : */
71 0 : __isl_give isl_restriction *isl_restriction_none(__isl_take isl_map *source_map)
72 : {
73 0 : return isl_restriction_alloc(source_map, isl_restriction_type_none);
74 : }
75 :
76 : /* Create a restriction that removes everything.
77 : */
78 0 : __isl_give isl_restriction *isl_restriction_empty(
79 : __isl_take isl_map *source_map)
80 : {
81 0 : return isl_restriction_alloc(source_map, isl_restriction_type_empty);
82 : }
83 :
84 : /* Create a restriction on the input of the maximization problem
85 : * based on the given source and sink restrictions.
86 : */
87 0 : __isl_give isl_restriction *isl_restriction_input(
88 : __isl_take isl_set *source_restr, __isl_take isl_set *sink_restr)
89 : {
90 : isl_ctx *ctx;
91 : isl_restriction *restr;
92 :
93 0 : if (!source_restr || !sink_restr)
94 : goto error;
95 :
96 0 : ctx = isl_set_get_ctx(source_restr);
97 0 : restr = isl_calloc_type(ctx, struct isl_restriction);
98 0 : if (!restr)
99 0 : goto error;
100 :
101 0 : restr->type = isl_restriction_type_input;
102 0 : restr->source = source_restr;
103 0 : restr->sink = sink_restr;
104 :
105 0 : return restr;
106 : error:
107 0 : isl_set_free(source_restr);
108 0 : isl_set_free(sink_restr);
109 0 : return NULL;
110 : }
111 :
112 : /* Create a restriction on the output of the maximization problem
113 : * based on the given source restriction.
114 : */
115 0 : __isl_give isl_restriction *isl_restriction_output(
116 : __isl_take isl_set *source_restr)
117 : {
118 : isl_ctx *ctx;
119 : isl_restriction *restr;
120 :
121 0 : if (!source_restr)
122 0 : return NULL;
123 :
124 0 : ctx = isl_set_get_ctx(source_restr);
125 0 : restr = isl_calloc_type(ctx, struct isl_restriction);
126 0 : if (!restr)
127 0 : goto error;
128 :
129 0 : restr->type = isl_restriction_type_output;
130 0 : restr->source = source_restr;
131 :
132 0 : return restr;
133 : error:
134 0 : isl_set_free(source_restr);
135 0 : return NULL;
136 : }
137 :
138 0 : __isl_null isl_restriction *isl_restriction_free(
139 : __isl_take isl_restriction *restr)
140 : {
141 0 : if (!restr)
142 0 : return NULL;
143 :
144 0 : isl_set_free(restr->source);
145 0 : isl_set_free(restr->sink);
146 0 : free(restr);
147 0 : return NULL;
148 : }
149 :
150 0 : isl_ctx *isl_restriction_get_ctx(__isl_keep isl_restriction *restr)
151 : {
152 0 : return restr ? isl_set_get_ctx(restr->source) : NULL;
153 : }
154 :
155 : /* A private structure to keep track of a mapping together with
156 : * a user-specified identifier and a boolean indicating whether
157 : * the map represents a must or may access/dependence.
158 : */
159 : struct isl_labeled_map {
160 : struct isl_map *map;
161 : void *data;
162 : int must;
163 : };
164 :
165 : typedef int (*isl_access_coscheduled)(void *first, void *second);
166 :
167 : /* A structure containing the input for dependence analysis:
168 : * - a sink
169 : * - n_must + n_may (<= max_source) sources
170 : * - a function for determining the relative order of sources and sink
171 : * - an optional function "coscheduled" for determining whether sources
172 : * may be coscheduled. If "coscheduled" is NULL, then the sources
173 : * are assumed not to be coscheduled.
174 : * The must sources are placed before the may sources.
175 : *
176 : * domain_map is an auxiliary map that maps the sink access relation
177 : * to the domain of this access relation.
178 : * This field is only needed when restrict_fn is set and
179 : * the field itself is set by isl_access_info_compute_flow.
180 : *
181 : * restrict_fn is a callback that (if not NULL) will be called
182 : * right before any lexicographical maximization.
183 : */
184 : struct isl_access_info {
185 : isl_map *domain_map;
186 : struct isl_labeled_map sink;
187 : isl_access_level_before level_before;
188 : isl_access_coscheduled coscheduled;
189 :
190 : isl_access_restrict restrict_fn;
191 : void *restrict_user;
192 :
193 : int max_source;
194 : int n_must;
195 : int n_may;
196 : struct isl_labeled_map source[1];
197 : };
198 :
199 : /* A structure containing the output of dependence analysis:
200 : * - n_source dependences
201 : * - a wrapped subset of the sink for which definitely no source could be found
202 : * - a wrapped subset of the sink for which possibly no source could be found
203 : */
204 : struct isl_flow {
205 : isl_set *must_no_source;
206 : isl_set *may_no_source;
207 : int n_source;
208 : struct isl_labeled_map *dep;
209 : };
210 :
211 : /* Construct an isl_access_info structure and fill it up with
212 : * the given data. The number of sources is set to 0.
213 : */
214 0 : __isl_give isl_access_info *isl_access_info_alloc(__isl_take isl_map *sink,
215 : void *sink_user, isl_access_level_before fn, int max_source)
216 : {
217 : isl_ctx *ctx;
218 : struct isl_access_info *acc;
219 :
220 0 : if (!sink)
221 0 : return NULL;
222 :
223 0 : ctx = isl_map_get_ctx(sink);
224 0 : isl_assert(ctx, max_source >= 0, goto error);
225 :
226 0 : acc = isl_calloc(ctx, struct isl_access_info,
227 : sizeof(struct isl_access_info) +
228 : (max_source - 1) * sizeof(struct isl_labeled_map));
229 0 : if (!acc)
230 0 : goto error;
231 :
232 0 : acc->sink.map = sink;
233 0 : acc->sink.data = sink_user;
234 0 : acc->level_before = fn;
235 0 : acc->max_source = max_source;
236 0 : acc->n_must = 0;
237 0 : acc->n_may = 0;
238 :
239 0 : return acc;
240 : error:
241 0 : isl_map_free(sink);
242 0 : return NULL;
243 : }
244 :
245 : /* Free the given isl_access_info structure.
246 : */
247 0 : __isl_null isl_access_info *isl_access_info_free(
248 : __isl_take isl_access_info *acc)
249 : {
250 : int i;
251 :
252 0 : if (!acc)
253 0 : return NULL;
254 0 : isl_map_free(acc->domain_map);
255 0 : isl_map_free(acc->sink.map);
256 0 : for (i = 0; i < acc->n_must + acc->n_may; ++i)
257 0 : isl_map_free(acc->source[i].map);
258 0 : free(acc);
259 0 : return NULL;
260 : }
261 :
262 0 : isl_ctx *isl_access_info_get_ctx(__isl_keep isl_access_info *acc)
263 : {
264 0 : return acc ? isl_map_get_ctx(acc->sink.map) : NULL;
265 : }
266 :
267 0 : __isl_give isl_access_info *isl_access_info_set_restrict(
268 : __isl_take isl_access_info *acc, isl_access_restrict fn, void *user)
269 : {
270 0 : if (!acc)
271 0 : return NULL;
272 0 : acc->restrict_fn = fn;
273 0 : acc->restrict_user = user;
274 0 : return acc;
275 : }
276 :
277 : /* Add another source to an isl_access_info structure, making
278 : * sure the "must" sources are placed before the "may" sources.
279 : * This function may be called at most max_source times on a
280 : * given isl_access_info structure, with max_source as specified
281 : * in the call to isl_access_info_alloc that constructed the structure.
282 : */
283 0 : __isl_give isl_access_info *isl_access_info_add_source(
284 : __isl_take isl_access_info *acc, __isl_take isl_map *source,
285 : int must, void *source_user)
286 : {
287 : isl_ctx *ctx;
288 :
289 0 : if (!acc)
290 0 : goto error;
291 0 : ctx = isl_map_get_ctx(acc->sink.map);
292 0 : isl_assert(ctx, acc->n_must + acc->n_may < acc->max_source, goto error);
293 :
294 0 : if (must) {
295 0 : if (acc->n_may)
296 0 : acc->source[acc->n_must + acc->n_may] =
297 0 : acc->source[acc->n_must];
298 0 : acc->source[acc->n_must].map = source;
299 0 : acc->source[acc->n_must].data = source_user;
300 0 : acc->source[acc->n_must].must = 1;
301 0 : acc->n_must++;
302 : } else {
303 0 : acc->source[acc->n_must + acc->n_may].map = source;
304 0 : acc->source[acc->n_must + acc->n_may].data = source_user;
305 0 : acc->source[acc->n_must + acc->n_may].must = 0;
306 0 : acc->n_may++;
307 : }
308 :
309 0 : return acc;
310 : error:
311 0 : isl_map_free(source);
312 0 : isl_access_info_free(acc);
313 0 : return NULL;
314 : }
315 :
316 : /* A helper struct carrying the isl_access_info and an error condition.
317 : */
318 : struct access_sort_info {
319 : isl_access_info *access_info;
320 : int error;
321 : };
322 :
323 : /* Return -n, 0 or n (with n a positive value), depending on whether
324 : * the source access identified by p1 should be sorted before, together
325 : * or after that identified by p2.
326 : *
327 : * If p1 appears before p2, then it should be sorted first.
328 : * For more generic initial schedules, it is possible that neither
329 : * p1 nor p2 appears before the other, or at least not in any obvious way.
330 : * We therefore also check if p2 appears before p1, in which case p2
331 : * should be sorted first.
332 : * If not, we try to order the two statements based on the description
333 : * of the iteration domains. This results in an arbitrary, but fairly
334 : * stable ordering.
335 : *
336 : * In case of an error, sort_info.error is set to true and all elements are
337 : * reported to be equal.
338 : */
339 0 : static int access_sort_cmp(const void *p1, const void *p2, void *user)
340 : {
341 0 : struct access_sort_info *sort_info = user;
342 0 : isl_access_info *acc = sort_info->access_info;
343 :
344 0 : if (sort_info->error)
345 0 : return 0;
346 :
347 : const struct isl_labeled_map *i1, *i2;
348 : int level1, level2;
349 : uint32_t h1, h2;
350 0 : i1 = (const struct isl_labeled_map *) p1;
351 0 : i2 = (const struct isl_labeled_map *) p2;
352 :
353 0 : level1 = acc->level_before(i1->data, i2->data);
354 0 : if (level1 < 0)
355 0 : goto error;
356 0 : if (level1 % 2)
357 0 : return -1;
358 :
359 0 : level2 = acc->level_before(i2->data, i1->data);
360 0 : if (level2 < 0)
361 0 : goto error;
362 0 : if (level2 % 2)
363 0 : return 1;
364 :
365 0 : h1 = isl_map_get_hash(i1->map);
366 0 : h2 = isl_map_get_hash(i2->map);
367 0 : return h1 > h2 ? 1 : h1 < h2 ? -1 : 0;
368 : error:
369 0 : sort_info->error = 1;
370 0 : return 0;
371 : }
372 :
373 : /* Sort the must source accesses in their textual order.
374 : */
375 0 : static __isl_give isl_access_info *isl_access_info_sort_sources(
376 : __isl_take isl_access_info *acc)
377 : {
378 : struct access_sort_info sort_info;
379 :
380 0 : sort_info.access_info = acc;
381 0 : sort_info.error = 0;
382 :
383 0 : if (!acc)
384 0 : return NULL;
385 0 : if (acc->n_must <= 1)
386 0 : return acc;
387 :
388 0 : if (isl_sort(acc->source, acc->n_must, sizeof(struct isl_labeled_map),
389 : access_sort_cmp, &sort_info) < 0)
390 0 : return isl_access_info_free(acc);
391 0 : if (sort_info.error)
392 0 : return isl_access_info_free(acc);
393 :
394 0 : return acc;
395 : }
396 :
397 : /* Align the parameters of the two spaces if needed and then call
398 : * isl_space_join.
399 : */
400 0 : static __isl_give isl_space *space_align_and_join(__isl_take isl_space *left,
401 : __isl_take isl_space *right)
402 : {
403 : isl_bool equal_params;
404 :
405 0 : equal_params = isl_space_has_equal_params(left, right);
406 0 : if (equal_params < 0)
407 0 : goto error;
408 0 : if (equal_params)
409 0 : return isl_space_join(left, right);
410 :
411 0 : left = isl_space_align_params(left, isl_space_copy(right));
412 0 : right = isl_space_align_params(right, isl_space_copy(left));
413 0 : return isl_space_join(left, right);
414 : error:
415 0 : isl_space_free(left);
416 0 : isl_space_free(right);
417 0 : return NULL;
418 : }
419 :
420 : /* Initialize an empty isl_flow structure corresponding to a given
421 : * isl_access_info structure.
422 : * For each must access, two dependences are created (initialized
423 : * to the empty relation), one for the resulting must dependences
424 : * and one for the resulting may dependences. May accesses can
425 : * only lead to may dependences, so only one dependence is created
426 : * for each of them.
427 : * This function is private as isl_flow structures are only supposed
428 : * to be created by isl_access_info_compute_flow.
429 : */
430 0 : static __isl_give isl_flow *isl_flow_alloc(__isl_keep isl_access_info *acc)
431 : {
432 : int i, n;
433 : struct isl_ctx *ctx;
434 : struct isl_flow *dep;
435 :
436 0 : if (!acc)
437 0 : return NULL;
438 :
439 0 : ctx = isl_map_get_ctx(acc->sink.map);
440 0 : dep = isl_calloc_type(ctx, struct isl_flow);
441 0 : if (!dep)
442 0 : return NULL;
443 :
444 0 : n = 2 * acc->n_must + acc->n_may;
445 0 : dep->dep = isl_calloc_array(ctx, struct isl_labeled_map, n);
446 0 : if (n && !dep->dep)
447 0 : goto error;
448 :
449 0 : dep->n_source = n;
450 0 : for (i = 0; i < acc->n_must; ++i) {
451 : isl_space *dim;
452 0 : dim = space_align_and_join(
453 0 : isl_map_get_space(acc->source[i].map),
454 0 : isl_space_reverse(isl_map_get_space(acc->sink.map)));
455 0 : dep->dep[2 * i].map = isl_map_empty(dim);
456 0 : dep->dep[2 * i + 1].map = isl_map_copy(dep->dep[2 * i].map);
457 0 : dep->dep[2 * i].data = acc->source[i].data;
458 0 : dep->dep[2 * i + 1].data = acc->source[i].data;
459 0 : dep->dep[2 * i].must = 1;
460 0 : dep->dep[2 * i + 1].must = 0;
461 0 : if (!dep->dep[2 * i].map || !dep->dep[2 * i + 1].map)
462 : goto error;
463 : }
464 0 : for (i = acc->n_must; i < acc->n_must + acc->n_may; ++i) {
465 : isl_space *dim;
466 0 : dim = space_align_and_join(
467 0 : isl_map_get_space(acc->source[i].map),
468 0 : isl_space_reverse(isl_map_get_space(acc->sink.map)));
469 0 : dep->dep[acc->n_must + i].map = isl_map_empty(dim);
470 0 : dep->dep[acc->n_must + i].data = acc->source[i].data;
471 0 : dep->dep[acc->n_must + i].must = 0;
472 0 : if (!dep->dep[acc->n_must + i].map)
473 0 : goto error;
474 : }
475 :
476 0 : return dep;
477 : error:
478 0 : isl_flow_free(dep);
479 0 : return NULL;
480 : }
481 :
482 : /* Iterate over all sources and for each resulting flow dependence
483 : * that is not empty, call the user specfied function.
484 : * The second argument in this function call identifies the source,
485 : * while the third argument correspond to the final argument of
486 : * the isl_flow_foreach call.
487 : */
488 0 : isl_stat isl_flow_foreach(__isl_keep isl_flow *deps,
489 : isl_stat (*fn)(__isl_take isl_map *dep, int must, void *dep_user,
490 : void *user),
491 : void *user)
492 : {
493 : int i;
494 :
495 0 : if (!deps)
496 0 : return isl_stat_error;
497 :
498 0 : for (i = 0; i < deps->n_source; ++i) {
499 0 : if (isl_map_plain_is_empty(deps->dep[i].map))
500 0 : continue;
501 0 : if (fn(isl_map_copy(deps->dep[i].map), deps->dep[i].must,
502 0 : deps->dep[i].data, user) < 0)
503 0 : return isl_stat_error;
504 : }
505 :
506 0 : return isl_stat_ok;
507 : }
508 :
509 : /* Return a copy of the subset of the sink for which no source could be found.
510 : */
511 0 : __isl_give isl_map *isl_flow_get_no_source(__isl_keep isl_flow *deps, int must)
512 : {
513 0 : if (!deps)
514 0 : return NULL;
515 :
516 0 : if (must)
517 0 : return isl_set_unwrap(isl_set_copy(deps->must_no_source));
518 : else
519 0 : return isl_set_unwrap(isl_set_copy(deps->may_no_source));
520 : }
521 :
522 0 : void isl_flow_free(__isl_take isl_flow *deps)
523 : {
524 : int i;
525 :
526 0 : if (!deps)
527 0 : return;
528 0 : isl_set_free(deps->must_no_source);
529 0 : isl_set_free(deps->may_no_source);
530 0 : if (deps->dep) {
531 0 : for (i = 0; i < deps->n_source; ++i)
532 0 : isl_map_free(deps->dep[i].map);
533 0 : free(deps->dep);
534 : }
535 0 : free(deps);
536 : }
537 :
538 0 : isl_ctx *isl_flow_get_ctx(__isl_keep isl_flow *deps)
539 : {
540 0 : return deps ? isl_set_get_ctx(deps->must_no_source) : NULL;
541 : }
542 :
543 : /* Return a map that enforces that the domain iteration occurs after
544 : * the range iteration at the given level.
545 : * If level is odd, then the domain iteration should occur after
546 : * the target iteration in their shared level/2 outermost loops.
547 : * In this case we simply need to enforce that these outermost
548 : * loop iterations are the same.
549 : * If level is even, then the loop iterator of the domain should
550 : * be greater than the loop iterator of the range at the last
551 : * of the level/2 shared loops, i.e., loop level/2 - 1.
552 : */
553 0 : static __isl_give isl_map *after_at_level(__isl_take isl_space *dim, int level)
554 : {
555 : struct isl_basic_map *bmap;
556 :
557 0 : if (level % 2)
558 0 : bmap = isl_basic_map_equal(dim, level/2);
559 : else
560 0 : bmap = isl_basic_map_more_at(dim, level/2 - 1);
561 :
562 0 : return isl_map_from_basic_map(bmap);
563 : }
564 :
565 : /* Compute the partial lexicographic maximum of "dep" on domain "sink",
566 : * but first check if the user has set acc->restrict_fn and if so
567 : * update either the input or the output of the maximization problem
568 : * with respect to the resulting restriction.
569 : *
570 : * Since the user expects a mapping from sink iterations to source iterations,
571 : * whereas the domain of "dep" is a wrapped map, mapping sink iterations
572 : * to accessed array elements, we first need to project out the accessed
573 : * sink array elements by applying acc->domain_map.
574 : * Similarly, the sink restriction specified by the user needs to be
575 : * converted back to the wrapped map.
576 : */
577 0 : static __isl_give isl_map *restricted_partial_lexmax(
578 : __isl_keep isl_access_info *acc, __isl_take isl_map *dep,
579 : int source, __isl_take isl_set *sink, __isl_give isl_set **empty)
580 : {
581 : isl_map *source_map;
582 : isl_restriction *restr;
583 : isl_set *sink_domain;
584 : isl_set *sink_restr;
585 : isl_map *res;
586 :
587 0 : if (!acc->restrict_fn)
588 0 : return isl_map_partial_lexmax(dep, sink, empty);
589 :
590 0 : source_map = isl_map_copy(dep);
591 0 : source_map = isl_map_apply_domain(source_map,
592 : isl_map_copy(acc->domain_map));
593 0 : sink_domain = isl_set_copy(sink);
594 0 : sink_domain = isl_set_apply(sink_domain, isl_map_copy(acc->domain_map));
595 0 : restr = acc->restrict_fn(source_map, sink_domain,
596 : acc->source[source].data, acc->restrict_user);
597 0 : isl_set_free(sink_domain);
598 0 : isl_map_free(source_map);
599 :
600 0 : if (!restr)
601 0 : goto error;
602 0 : if (restr->type == isl_restriction_type_input) {
603 0 : dep = isl_map_intersect_range(dep, isl_set_copy(restr->source));
604 0 : sink_restr = isl_set_copy(restr->sink);
605 0 : sink_restr = isl_set_apply(sink_restr,
606 : isl_map_reverse(isl_map_copy(acc->domain_map)));
607 0 : sink = isl_set_intersect(sink, sink_restr);
608 0 : } else if (restr->type == isl_restriction_type_empty) {
609 0 : isl_space *space = isl_map_get_space(dep);
610 0 : isl_map_free(dep);
611 0 : dep = isl_map_empty(space);
612 : }
613 :
614 0 : res = isl_map_partial_lexmax(dep, sink, empty);
615 :
616 0 : if (restr->type == isl_restriction_type_output)
617 0 : res = isl_map_intersect_range(res, isl_set_copy(restr->source));
618 :
619 0 : isl_restriction_free(restr);
620 0 : return res;
621 : error:
622 0 : isl_map_free(dep);
623 0 : isl_set_free(sink);
624 0 : *empty = NULL;
625 0 : return NULL;
626 : }
627 :
628 : /* Compute the last iteration of must source j that precedes the sink
629 : * at the given level for sink iterations in set_C.
630 : * The subset of set_C for which no such iteration can be found is returned
631 : * in *empty.
632 : */
633 0 : static struct isl_map *last_source(struct isl_access_info *acc,
634 : struct isl_set *set_C,
635 : int j, int level, struct isl_set **empty)
636 : {
637 : struct isl_map *read_map;
638 : struct isl_map *write_map;
639 : struct isl_map *dep_map;
640 : struct isl_map *after;
641 : struct isl_map *result;
642 :
643 0 : read_map = isl_map_copy(acc->sink.map);
644 0 : write_map = isl_map_copy(acc->source[j].map);
645 0 : write_map = isl_map_reverse(write_map);
646 0 : dep_map = isl_map_apply_range(read_map, write_map);
647 0 : after = after_at_level(isl_map_get_space(dep_map), level);
648 0 : dep_map = isl_map_intersect(dep_map, after);
649 0 : result = restricted_partial_lexmax(acc, dep_map, j, set_C, empty);
650 0 : result = isl_map_reverse(result);
651 :
652 0 : return result;
653 : }
654 :
655 : /* For a given mapping between iterations of must source j and iterations
656 : * of the sink, compute the last iteration of must source k preceding
657 : * the sink at level before_level for any of the sink iterations,
658 : * but following the corresponding iteration of must source j at level
659 : * after_level.
660 : */
661 0 : static struct isl_map *last_later_source(struct isl_access_info *acc,
662 : struct isl_map *old_map,
663 : int j, int before_level,
664 : int k, int after_level,
665 : struct isl_set **empty)
666 : {
667 : isl_space *dim;
668 : struct isl_set *set_C;
669 : struct isl_map *read_map;
670 : struct isl_map *write_map;
671 : struct isl_map *dep_map;
672 : struct isl_map *after_write;
673 : struct isl_map *before_read;
674 : struct isl_map *result;
675 :
676 0 : set_C = isl_map_range(isl_map_copy(old_map));
677 0 : read_map = isl_map_copy(acc->sink.map);
678 0 : write_map = isl_map_copy(acc->source[k].map);
679 :
680 0 : write_map = isl_map_reverse(write_map);
681 0 : dep_map = isl_map_apply_range(read_map, write_map);
682 0 : dim = space_align_and_join(isl_map_get_space(acc->source[k].map),
683 0 : isl_space_reverse(isl_map_get_space(acc->source[j].map)));
684 0 : after_write = after_at_level(dim, after_level);
685 0 : after_write = isl_map_apply_range(after_write, old_map);
686 0 : after_write = isl_map_reverse(after_write);
687 0 : dep_map = isl_map_intersect(dep_map, after_write);
688 0 : before_read = after_at_level(isl_map_get_space(dep_map), before_level);
689 0 : dep_map = isl_map_intersect(dep_map, before_read);
690 0 : result = restricted_partial_lexmax(acc, dep_map, k, set_C, empty);
691 0 : result = isl_map_reverse(result);
692 :
693 0 : return result;
694 : }
695 :
696 : /* Given a shared_level between two accesses, return 1 if the
697 : * the first can precede the second at the requested target_level.
698 : * If the target level is odd, i.e., refers to a statement level
699 : * dimension, then first needs to precede second at the requested
700 : * level, i.e., shared_level must be equal to target_level.
701 : * If the target level is odd, then the two loops should share
702 : * at least the requested number of outer loops.
703 : */
704 0 : static int can_precede_at_level(int shared_level, int target_level)
705 : {
706 0 : if (shared_level < target_level)
707 0 : return 0;
708 0 : if ((target_level % 2) && shared_level > target_level)
709 0 : return 0;
710 0 : return 1;
711 : }
712 :
713 : /* Given a possible flow dependence temp_rel[j] between source j and the sink
714 : * at level sink_level, remove those elements for which
715 : * there is an iteration of another source k < j that is closer to the sink.
716 : * The flow dependences temp_rel[k] are updated with the improved sources.
717 : * Any improved source needs to precede the sink at the same level
718 : * and needs to follow source j at the same or a deeper level.
719 : * The lower this level, the later the execution date of source k.
720 : * We therefore consider lower levels first.
721 : *
722 : * If temp_rel[j] is empty, then there can be no improvement and
723 : * we return immediately.
724 : *
725 : * This function returns isl_stat_ok in case it was executed successfully and
726 : * isl_stat_error in case of errors during the execution of this function.
727 : */
728 0 : static isl_stat intermediate_sources(__isl_keep isl_access_info *acc,
729 : struct isl_map **temp_rel, int j, int sink_level)
730 : {
731 : int k, level;
732 0 : int depth = 2 * isl_map_dim(acc->source[j].map, isl_dim_in) + 1;
733 :
734 0 : if (isl_map_plain_is_empty(temp_rel[j]))
735 0 : return isl_stat_ok;
736 :
737 0 : for (k = j - 1; k >= 0; --k) {
738 : int plevel, plevel2;
739 0 : plevel = acc->level_before(acc->source[k].data, acc->sink.data);
740 0 : if (plevel < 0)
741 0 : return isl_stat_error;
742 0 : if (!can_precede_at_level(plevel, sink_level))
743 0 : continue;
744 :
745 0 : plevel2 = acc->level_before(acc->source[j].data,
746 : acc->source[k].data);
747 0 : if (plevel2 < 0)
748 0 : return isl_stat_error;
749 :
750 0 : for (level = sink_level; level <= depth; ++level) {
751 : struct isl_map *T;
752 : struct isl_set *trest;
753 : struct isl_map *copy;
754 :
755 0 : if (!can_precede_at_level(plevel2, level))
756 0 : continue;
757 :
758 0 : copy = isl_map_copy(temp_rel[j]);
759 0 : T = last_later_source(acc, copy, j, sink_level, k,
760 : level, &trest);
761 0 : if (isl_map_plain_is_empty(T)) {
762 0 : isl_set_free(trest);
763 0 : isl_map_free(T);
764 0 : continue;
765 : }
766 0 : temp_rel[j] = isl_map_intersect_range(temp_rel[j], trest);
767 0 : temp_rel[k] = isl_map_union_disjoint(temp_rel[k], T);
768 : }
769 : }
770 :
771 0 : return isl_stat_ok;
772 : }
773 :
774 : /* Compute all iterations of may source j that precedes the sink at the given
775 : * level for sink iterations in set_C.
776 : */
777 0 : static __isl_give isl_map *all_sources(__isl_keep isl_access_info *acc,
778 : __isl_take isl_set *set_C, int j, int level)
779 : {
780 : isl_map *read_map;
781 : isl_map *write_map;
782 : isl_map *dep_map;
783 : isl_map *after;
784 :
785 0 : read_map = isl_map_copy(acc->sink.map);
786 0 : read_map = isl_map_intersect_domain(read_map, set_C);
787 0 : write_map = isl_map_copy(acc->source[acc->n_must + j].map);
788 0 : write_map = isl_map_reverse(write_map);
789 0 : dep_map = isl_map_apply_range(read_map, write_map);
790 0 : after = after_at_level(isl_map_get_space(dep_map), level);
791 0 : dep_map = isl_map_intersect(dep_map, after);
792 :
793 0 : return isl_map_reverse(dep_map);
794 : }
795 :
796 : /* For a given mapping between iterations of must source k and iterations
797 : * of the sink, compute all iterations of may source j preceding
798 : * the sink at level before_level for any of the sink iterations,
799 : * but following the corresponding iteration of must source k at level
800 : * after_level.
801 : */
802 0 : static __isl_give isl_map *all_later_sources(__isl_keep isl_access_info *acc,
803 : __isl_take isl_map *old_map,
804 : int j, int before_level, int k, int after_level)
805 : {
806 : isl_space *dim;
807 : isl_set *set_C;
808 : isl_map *read_map;
809 : isl_map *write_map;
810 : isl_map *dep_map;
811 : isl_map *after_write;
812 : isl_map *before_read;
813 :
814 0 : set_C = isl_map_range(isl_map_copy(old_map));
815 0 : read_map = isl_map_copy(acc->sink.map);
816 0 : read_map = isl_map_intersect_domain(read_map, set_C);
817 0 : write_map = isl_map_copy(acc->source[acc->n_must + j].map);
818 :
819 0 : write_map = isl_map_reverse(write_map);
820 0 : dep_map = isl_map_apply_range(read_map, write_map);
821 0 : dim = isl_space_join(isl_map_get_space(acc->source[acc->n_must + j].map),
822 0 : isl_space_reverse(isl_map_get_space(acc->source[k].map)));
823 0 : after_write = after_at_level(dim, after_level);
824 0 : after_write = isl_map_apply_range(after_write, old_map);
825 0 : after_write = isl_map_reverse(after_write);
826 0 : dep_map = isl_map_intersect(dep_map, after_write);
827 0 : before_read = after_at_level(isl_map_get_space(dep_map), before_level);
828 0 : dep_map = isl_map_intersect(dep_map, before_read);
829 0 : return isl_map_reverse(dep_map);
830 : }
831 :
832 : /* Given the must and may dependence relations for the must accesses
833 : * for level sink_level, check if there are any accesses of may access j
834 : * that occur in between and return their union.
835 : * If some of these accesses are intermediate with respect to
836 : * (previously thought to be) must dependences, then these
837 : * must dependences are turned into may dependences.
838 : */
839 0 : static __isl_give isl_map *all_intermediate_sources(
840 : __isl_keep isl_access_info *acc, __isl_take isl_map *map,
841 : struct isl_map **must_rel, struct isl_map **may_rel,
842 : int j, int sink_level)
843 : {
844 : int k, level;
845 0 : int depth = 2 * isl_map_dim(acc->source[acc->n_must + j].map,
846 0 : isl_dim_in) + 1;
847 :
848 0 : for (k = 0; k < acc->n_must; ++k) {
849 : int plevel;
850 :
851 0 : if (isl_map_plain_is_empty(may_rel[k]) &&
852 0 : isl_map_plain_is_empty(must_rel[k]))
853 0 : continue;
854 :
855 0 : plevel = acc->level_before(acc->source[k].data,
856 0 : acc->source[acc->n_must + j].data);
857 0 : if (plevel < 0)
858 0 : return isl_map_free(map);
859 :
860 0 : for (level = sink_level; level <= depth; ++level) {
861 : isl_map *T;
862 : isl_map *copy;
863 : isl_set *ran;
864 :
865 0 : if (!can_precede_at_level(plevel, level))
866 0 : continue;
867 :
868 0 : copy = isl_map_copy(may_rel[k]);
869 0 : T = all_later_sources(acc, copy, j, sink_level, k, level);
870 0 : map = isl_map_union(map, T);
871 :
872 0 : copy = isl_map_copy(must_rel[k]);
873 0 : T = all_later_sources(acc, copy, j, sink_level, k, level);
874 0 : ran = isl_map_range(isl_map_copy(T));
875 0 : map = isl_map_union(map, T);
876 0 : may_rel[k] = isl_map_union_disjoint(may_rel[k],
877 0 : isl_map_intersect_range(isl_map_copy(must_rel[k]),
878 : isl_set_copy(ran)));
879 0 : T = isl_map_from_domain_and_range(
880 : isl_set_universe(
881 0 : isl_space_domain(isl_map_get_space(must_rel[k]))),
882 : ran);
883 0 : must_rel[k] = isl_map_subtract(must_rel[k], T);
884 : }
885 : }
886 :
887 0 : return map;
888 : }
889 :
890 : /* Given a dependence relation "old_map" between a must-source and the sink,
891 : * return a subset of the dependences, augmented with instances
892 : * of the source at position "pos" in "acc" that are coscheduled
893 : * with the must-source and that access the same element.
894 : * That is, if the input lives in a space T -> K, then the output
895 : * lives in the space [T -> S] -> K, with S the space of source "pos", and
896 : * the domain factor of the domain product is a subset of the input.
897 : * The sources are considered to be coscheduled if they have the same values
898 : * for the initial "depth" coordinates.
899 : *
900 : * First construct a dependence relation S -> K and a mapping
901 : * between coscheduled sources T -> S.
902 : * The second is combined with the original dependence relation T -> K
903 : * to form a relation in T -> [S -> K], which is subsequently
904 : * uncurried to [T -> S] -> K.
905 : * This result is then intersected with the dependence relation S -> K
906 : * to form the output.
907 : *
908 : * In case a negative depth is given, NULL is returned to indicate an error.
909 : */
910 0 : static __isl_give isl_map *coscheduled_source(__isl_keep isl_access_info *acc,
911 : __isl_keep isl_map *old_map, int pos, int depth)
912 : {
913 : isl_space *space;
914 : isl_set *set_C;
915 : isl_map *read_map;
916 : isl_map *write_map;
917 : isl_map *dep_map;
918 : isl_map *equal;
919 : isl_map *map;
920 :
921 0 : if (depth < 0)
922 0 : return NULL;
923 :
924 0 : set_C = isl_map_range(isl_map_copy(old_map));
925 0 : read_map = isl_map_copy(acc->sink.map);
926 0 : read_map = isl_map_intersect_domain(read_map, set_C);
927 0 : write_map = isl_map_copy(acc->source[pos].map);
928 0 : dep_map = isl_map_domain_product(write_map, read_map);
929 0 : dep_map = isl_set_unwrap(isl_map_domain(dep_map));
930 0 : space = isl_space_join(isl_map_get_space(old_map),
931 : isl_space_reverse(isl_map_get_space(dep_map)));
932 0 : equal = isl_map_from_basic_map(isl_basic_map_equal(space, depth));
933 0 : map = isl_map_range_product(equal, isl_map_copy(old_map));
934 0 : map = isl_map_uncurry(map);
935 0 : map = isl_map_intersect_domain_factor_range(map, dep_map);
936 :
937 0 : return map;
938 : }
939 :
940 : /* After the dependences derived from a must-source have been computed
941 : * at a certain level, check if any of the sources of the must-dependences
942 : * may be coscheduled with other sources.
943 : * If they are any such sources, then there is no way of determining
944 : * which of the sources actually comes last and the must-dependences
945 : * need to be turned into may-dependences, while dependences from
946 : * the other sources need to be added to the may-dependences as well.
947 : * "acc" describes the sources and a callback for checking whether
948 : * two sources may be coscheduled. If acc->coscheduled is NULL then
949 : * the sources are assumed not to be coscheduled.
950 : * "must_rel" and "may_rel" describe the must and may-dependence relations
951 : * computed at the current level for the must-sources. Some of the dependences
952 : * may be moved from "must_rel" to "may_rel".
953 : * "flow" contains all dependences computed so far (apart from those
954 : * in "must_rel" and "may_rel") and may be updated with additional
955 : * dependences derived from may-sources.
956 : *
957 : * In particular, consider all the must-sources with a non-empty
958 : * dependence relation in "must_rel". They are considered in reverse
959 : * order because that is the order in which they are considered in the caller.
960 : * If any of the must-sources are coscheduled, then the last one
961 : * is the one that will have a corresponding dependence relation.
962 : * For each must-source i, consider both all the previous must-sources
963 : * and all the may-sources. If any of those may be coscheduled with
964 : * must-source i, then compute the coscheduled instances that access
965 : * the same memory elements. The result is a relation [T -> S] -> K.
966 : * The projection onto T -> K is a subset of the must-dependence relation
967 : * that needs to be turned into may-dependences.
968 : * The projection onto S -> K needs to be added to the may-dependences
969 : * of source S.
970 : * Since a given must-source instance may be coscheduled with several
971 : * other source instances, the dependences that need to be turned
972 : * into may-dependences are first collected and only actually removed
973 : * from the must-dependences after all other sources have been considered.
974 : */
975 0 : static __isl_give isl_flow *handle_coscheduled(__isl_keep isl_access_info *acc,
976 : __isl_keep isl_map **must_rel, __isl_keep isl_map **may_rel,
977 : __isl_take isl_flow *flow)
978 : {
979 : int i, j;
980 :
981 0 : if (!acc->coscheduled)
982 0 : return flow;
983 0 : for (i = acc->n_must - 1; i >= 0; --i) {
984 : isl_map *move;
985 :
986 0 : if (isl_map_plain_is_empty(must_rel[i]))
987 0 : continue;
988 0 : move = isl_map_empty(isl_map_get_space(must_rel[i]));
989 0 : for (j = i - 1; j >= 0; --j) {
990 : int depth;
991 : isl_map *map, *factor;
992 :
993 0 : if (!acc->coscheduled(acc->source[i].data,
994 : acc->source[j].data))
995 0 : continue;
996 0 : depth = acc->level_before(acc->source[i].data,
997 : acc->source[j].data) / 2;
998 0 : map = coscheduled_source(acc, must_rel[i], j, depth);
999 0 : factor = isl_map_domain_factor_range(isl_map_copy(map));
1000 0 : may_rel[j] = isl_map_union(may_rel[j], factor);
1001 0 : map = isl_map_domain_factor_domain(map);
1002 0 : move = isl_map_union(move, map);
1003 : }
1004 0 : for (j = 0; j < acc->n_may; ++j) {
1005 : int depth, pos;
1006 : isl_map *map, *factor;
1007 :
1008 0 : pos = acc->n_must + j;
1009 0 : if (!acc->coscheduled(acc->source[i].data,
1010 : acc->source[pos].data))
1011 0 : continue;
1012 0 : depth = acc->level_before(acc->source[i].data,
1013 : acc->source[pos].data) / 2;
1014 0 : map = coscheduled_source(acc, must_rel[i], pos, depth);
1015 0 : factor = isl_map_domain_factor_range(isl_map_copy(map));
1016 0 : pos = 2 * acc->n_must + j;
1017 0 : flow->dep[pos].map = isl_map_union(flow->dep[pos].map,
1018 : factor);
1019 0 : map = isl_map_domain_factor_domain(map);
1020 0 : move = isl_map_union(move, map);
1021 : }
1022 0 : must_rel[i] = isl_map_subtract(must_rel[i], isl_map_copy(move));
1023 0 : may_rel[i] = isl_map_union(may_rel[i], move);
1024 : }
1025 :
1026 0 : return flow;
1027 : }
1028 :
1029 : /* Compute dependences for the case where all accesses are "may"
1030 : * accesses, which boils down to computing memory based dependences.
1031 : * The generic algorithm would also work in this case, but it would
1032 : * be overkill to use it.
1033 : */
1034 0 : static __isl_give isl_flow *compute_mem_based_dependences(
1035 : __isl_keep isl_access_info *acc)
1036 : {
1037 : int i;
1038 : isl_set *mustdo;
1039 : isl_set *maydo;
1040 : isl_flow *res;
1041 :
1042 0 : res = isl_flow_alloc(acc);
1043 0 : if (!res)
1044 0 : return NULL;
1045 :
1046 0 : mustdo = isl_map_domain(isl_map_copy(acc->sink.map));
1047 0 : maydo = isl_set_copy(mustdo);
1048 :
1049 0 : for (i = 0; i < acc->n_may; ++i) {
1050 : int plevel;
1051 : int is_before;
1052 : isl_space *dim;
1053 : isl_map *before;
1054 : isl_map *dep;
1055 :
1056 0 : plevel = acc->level_before(acc->source[i].data, acc->sink.data);
1057 0 : if (plevel < 0)
1058 0 : goto error;
1059 :
1060 0 : is_before = plevel & 1;
1061 0 : plevel >>= 1;
1062 :
1063 0 : dim = isl_map_get_space(res->dep[i].map);
1064 0 : if (is_before)
1065 0 : before = isl_map_lex_le_first(dim, plevel);
1066 : else
1067 0 : before = isl_map_lex_lt_first(dim, plevel);
1068 0 : dep = isl_map_apply_range(isl_map_copy(acc->source[i].map),
1069 0 : isl_map_reverse(isl_map_copy(acc->sink.map)));
1070 0 : dep = isl_map_intersect(dep, before);
1071 0 : mustdo = isl_set_subtract(mustdo,
1072 : isl_map_range(isl_map_copy(dep)));
1073 0 : res->dep[i].map = isl_map_union(res->dep[i].map, dep);
1074 : }
1075 :
1076 0 : res->may_no_source = isl_set_subtract(maydo, isl_set_copy(mustdo));
1077 0 : res->must_no_source = mustdo;
1078 :
1079 0 : return res;
1080 : error:
1081 0 : isl_set_free(mustdo);
1082 0 : isl_set_free(maydo);
1083 0 : isl_flow_free(res);
1084 0 : return NULL;
1085 : }
1086 :
1087 : /* Compute dependences for the case where there is at least one
1088 : * "must" access.
1089 : *
1090 : * The core algorithm considers all levels in which a source may precede
1091 : * the sink, where a level may either be a statement level or a loop level.
1092 : * The outermost statement level is 1, the first loop level is 2, etc...
1093 : * The algorithm basically does the following:
1094 : * for all levels l of the read access from innermost to outermost
1095 : * for all sources w that may precede the sink access at that level
1096 : * compute the last iteration of the source that precedes the sink access
1097 : * at that level
1098 : * add result to possible last accesses at level l of source w
1099 : * for all sources w2 that we haven't considered yet at this level that may
1100 : * also precede the sink access
1101 : * for all levels l2 of w from l to innermost
1102 : * for all possible last accesses dep of w at l
1103 : * compute last iteration of w2 between the source and sink
1104 : * of dep
1105 : * add result to possible last accesses at level l of write w2
1106 : * and replace possible last accesses dep by the remainder
1107 : *
1108 : *
1109 : * The above algorithm is applied to the must access. During the course
1110 : * of the algorithm, we keep track of sink iterations that still
1111 : * need to be considered. These iterations are split into those that
1112 : * haven't been matched to any source access (mustdo) and those that have only
1113 : * been matched to may accesses (maydo).
1114 : * At the end of each level, must-sources and may-sources that are coscheduled
1115 : * with the sources of the must-dependences at that level are considered.
1116 : * If any coscheduled instances are found, then corresponding may-dependences
1117 : * are added and the original must-dependences are turned into may-dependences.
1118 : * Afterwards, the may accesses that occur after must-dependence sources
1119 : * are considered.
1120 : * In particular, we consider may accesses that precede the remaining
1121 : * sink iterations, moving elements from mustdo to maydo when appropriate,
1122 : * and may accesses that occur between a must source and a sink of any
1123 : * dependences found at the current level, turning must dependences into
1124 : * may dependences when appropriate.
1125 : *
1126 : */
1127 0 : static __isl_give isl_flow *compute_val_based_dependences(
1128 : __isl_keep isl_access_info *acc)
1129 : {
1130 : isl_ctx *ctx;
1131 : isl_flow *res;
1132 0 : isl_set *mustdo = NULL;
1133 0 : isl_set *maydo = NULL;
1134 : int level, j;
1135 : int depth;
1136 0 : isl_map **must_rel = NULL;
1137 0 : isl_map **may_rel = NULL;
1138 :
1139 0 : if (!acc)
1140 0 : return NULL;
1141 :
1142 0 : res = isl_flow_alloc(acc);
1143 0 : if (!res)
1144 0 : goto error;
1145 0 : ctx = isl_map_get_ctx(acc->sink.map);
1146 :
1147 0 : depth = 2 * isl_map_dim(acc->sink.map, isl_dim_in) + 1;
1148 0 : mustdo = isl_map_domain(isl_map_copy(acc->sink.map));
1149 0 : maydo = isl_set_empty(isl_set_get_space(mustdo));
1150 0 : if (!mustdo || !maydo)
1151 : goto error;
1152 0 : if (isl_set_plain_is_empty(mustdo))
1153 0 : goto done;
1154 :
1155 0 : must_rel = isl_calloc_array(ctx, struct isl_map *, acc->n_must);
1156 0 : may_rel = isl_calloc_array(ctx, struct isl_map *, acc->n_must);
1157 0 : if (!must_rel || !may_rel)
1158 : goto error;
1159 :
1160 0 : for (level = depth; level >= 1; --level) {
1161 0 : for (j = acc->n_must-1; j >=0; --j) {
1162 : isl_space *space;
1163 0 : space = isl_map_get_space(res->dep[2 * j].map);
1164 0 : must_rel[j] = isl_map_empty(space);
1165 0 : may_rel[j] = isl_map_copy(must_rel[j]);
1166 : }
1167 :
1168 0 : for (j = acc->n_must - 1; j >= 0; --j) {
1169 : struct isl_map *T;
1170 : struct isl_set *rest;
1171 : int plevel;
1172 :
1173 0 : plevel = acc->level_before(acc->source[j].data,
1174 : acc->sink.data);
1175 0 : if (plevel < 0)
1176 0 : goto error;
1177 0 : if (!can_precede_at_level(plevel, level))
1178 0 : continue;
1179 :
1180 0 : T = last_source(acc, mustdo, j, level, &rest);
1181 0 : must_rel[j] = isl_map_union_disjoint(must_rel[j], T);
1182 0 : mustdo = rest;
1183 :
1184 0 : if (intermediate_sources(acc, must_rel, j, level) < 0)
1185 0 : goto error;
1186 :
1187 0 : T = last_source(acc, maydo, j, level, &rest);
1188 0 : may_rel[j] = isl_map_union_disjoint(may_rel[j], T);
1189 0 : maydo = rest;
1190 :
1191 0 : if (intermediate_sources(acc, may_rel, j, level) < 0)
1192 0 : goto error;
1193 :
1194 0 : if (isl_set_plain_is_empty(mustdo) &&
1195 0 : isl_set_plain_is_empty(maydo))
1196 0 : break;
1197 : }
1198 0 : for (j = j - 1; j >= 0; --j) {
1199 : int plevel;
1200 :
1201 0 : plevel = acc->level_before(acc->source[j].data,
1202 : acc->sink.data);
1203 0 : if (plevel < 0)
1204 0 : goto error;
1205 0 : if (!can_precede_at_level(plevel, level))
1206 0 : continue;
1207 :
1208 0 : if (intermediate_sources(acc, must_rel, j, level) < 0)
1209 0 : goto error;
1210 0 : if (intermediate_sources(acc, may_rel, j, level) < 0)
1211 0 : goto error;
1212 : }
1213 :
1214 0 : handle_coscheduled(acc, must_rel, may_rel, res);
1215 :
1216 0 : for (j = 0; j < acc->n_may; ++j) {
1217 : int plevel;
1218 : isl_map *T;
1219 : isl_set *ran;
1220 :
1221 0 : plevel = acc->level_before(acc->source[acc->n_must + j].data,
1222 : acc->sink.data);
1223 0 : if (plevel < 0)
1224 0 : goto error;
1225 0 : if (!can_precede_at_level(plevel, level))
1226 0 : continue;
1227 :
1228 0 : T = all_sources(acc, isl_set_copy(maydo), j, level);
1229 0 : res->dep[2 * acc->n_must + j].map =
1230 0 : isl_map_union(res->dep[2 * acc->n_must + j].map, T);
1231 0 : T = all_sources(acc, isl_set_copy(mustdo), j, level);
1232 0 : ran = isl_map_range(isl_map_copy(T));
1233 0 : res->dep[2 * acc->n_must + j].map =
1234 0 : isl_map_union(res->dep[2 * acc->n_must + j].map, T);
1235 0 : mustdo = isl_set_subtract(mustdo, isl_set_copy(ran));
1236 0 : maydo = isl_set_union_disjoint(maydo, ran);
1237 :
1238 0 : T = res->dep[2 * acc->n_must + j].map;
1239 0 : T = all_intermediate_sources(acc, T, must_rel, may_rel,
1240 : j, level);
1241 0 : res->dep[2 * acc->n_must + j].map = T;
1242 : }
1243 :
1244 0 : for (j = acc->n_must - 1; j >= 0; --j) {
1245 0 : res->dep[2 * j].map =
1246 0 : isl_map_union_disjoint(res->dep[2 * j].map,
1247 0 : must_rel[j]);
1248 0 : res->dep[2 * j + 1].map =
1249 0 : isl_map_union_disjoint(res->dep[2 * j + 1].map,
1250 0 : may_rel[j]);
1251 : }
1252 :
1253 0 : if (isl_set_plain_is_empty(mustdo) &&
1254 0 : isl_set_plain_is_empty(maydo))
1255 0 : break;
1256 : }
1257 :
1258 0 : free(must_rel);
1259 0 : free(may_rel);
1260 : done:
1261 0 : res->must_no_source = mustdo;
1262 0 : res->may_no_source = maydo;
1263 0 : return res;
1264 : error:
1265 0 : if (must_rel)
1266 0 : for (j = 0; j < acc->n_must; ++j)
1267 0 : isl_map_free(must_rel[j]);
1268 0 : if (may_rel)
1269 0 : for (j = 0; j < acc->n_must; ++j)
1270 0 : isl_map_free(may_rel[j]);
1271 0 : isl_flow_free(res);
1272 0 : isl_set_free(mustdo);
1273 0 : isl_set_free(maydo);
1274 0 : free(must_rel);
1275 0 : free(may_rel);
1276 0 : return NULL;
1277 : }
1278 :
1279 : /* Given a "sink" access, a list of n "source" accesses,
1280 : * compute for each iteration of the sink access
1281 : * and for each element accessed by that iteration,
1282 : * the source access in the list that last accessed the
1283 : * element accessed by the sink access before this sink access.
1284 : * Each access is given as a map from the loop iterators
1285 : * to the array indices.
1286 : * The result is a list of n relations between source and sink
1287 : * iterations and a subset of the domain of the sink access,
1288 : * corresponding to those iterations that access an element
1289 : * not previously accessed.
1290 : *
1291 : * To deal with multi-valued sink access relations, the sink iteration
1292 : * domain is first extended with dimensions that correspond to the data
1293 : * space. However, these extra dimensions are not projected out again.
1294 : * It is up to the caller to decide whether these dimensions should be kept.
1295 : */
1296 0 : static __isl_give isl_flow *access_info_compute_flow_core(
1297 : __isl_take isl_access_info *acc)
1298 : {
1299 0 : struct isl_flow *res = NULL;
1300 :
1301 0 : if (!acc)
1302 0 : return NULL;
1303 :
1304 0 : acc->sink.map = isl_map_range_map(acc->sink.map);
1305 0 : if (!acc->sink.map)
1306 0 : goto error;
1307 :
1308 0 : if (acc->n_must == 0)
1309 0 : res = compute_mem_based_dependences(acc);
1310 : else {
1311 0 : acc = isl_access_info_sort_sources(acc);
1312 0 : res = compute_val_based_dependences(acc);
1313 : }
1314 0 : acc = isl_access_info_free(acc);
1315 0 : if (!res)
1316 0 : return NULL;
1317 0 : if (!res->must_no_source || !res->may_no_source)
1318 : goto error;
1319 0 : return res;
1320 : error:
1321 0 : isl_access_info_free(acc);
1322 0 : isl_flow_free(res);
1323 0 : return NULL;
1324 : }
1325 :
1326 : /* Given a "sink" access, a list of n "source" accesses,
1327 : * compute for each iteration of the sink access
1328 : * and for each element accessed by that iteration,
1329 : * the source access in the list that last accessed the
1330 : * element accessed by the sink access before this sink access.
1331 : * Each access is given as a map from the loop iterators
1332 : * to the array indices.
1333 : * The result is a list of n relations between source and sink
1334 : * iterations and a subset of the domain of the sink access,
1335 : * corresponding to those iterations that access an element
1336 : * not previously accessed.
1337 : *
1338 : * To deal with multi-valued sink access relations,
1339 : * access_info_compute_flow_core extends the sink iteration domain
1340 : * with dimensions that correspond to the data space. These extra dimensions
1341 : * are projected out from the result of access_info_compute_flow_core.
1342 : */
1343 0 : __isl_give isl_flow *isl_access_info_compute_flow(__isl_take isl_access_info *acc)
1344 : {
1345 : int j;
1346 : struct isl_flow *res;
1347 :
1348 0 : if (!acc)
1349 0 : return NULL;
1350 :
1351 0 : acc->domain_map = isl_map_domain_map(isl_map_copy(acc->sink.map));
1352 0 : res = access_info_compute_flow_core(acc);
1353 0 : if (!res)
1354 0 : return NULL;
1355 :
1356 0 : for (j = 0; j < res->n_source; ++j) {
1357 0 : res->dep[j].map = isl_map_range_factor_domain(res->dep[j].map);
1358 0 : if (!res->dep[j].map)
1359 0 : goto error;
1360 : }
1361 :
1362 0 : return res;
1363 : error:
1364 0 : isl_flow_free(res);
1365 0 : return NULL;
1366 : }
1367 :
1368 :
1369 : /* Keep track of some information about a schedule for a given
1370 : * access. In particular, keep track of which dimensions
1371 : * have a constant value and of the actual constant values.
1372 : */
1373 : struct isl_sched_info {
1374 : int *is_cst;
1375 : isl_vec *cst;
1376 : };
1377 :
1378 0 : static void sched_info_free(__isl_take struct isl_sched_info *info)
1379 : {
1380 0 : if (!info)
1381 0 : return;
1382 0 : isl_vec_free(info->cst);
1383 0 : free(info->is_cst);
1384 0 : free(info);
1385 : }
1386 :
1387 : /* Extract information on the constant dimensions of the schedule
1388 : * for a given access. The "map" is of the form
1389 : *
1390 : * [S -> D] -> A
1391 : *
1392 : * with S the schedule domain, D the iteration domain and A the data domain.
1393 : */
1394 0 : static __isl_give struct isl_sched_info *sched_info_alloc(
1395 : __isl_keep isl_map *map)
1396 : {
1397 : isl_ctx *ctx;
1398 : isl_space *dim;
1399 : struct isl_sched_info *info;
1400 : int i, n;
1401 :
1402 0 : if (!map)
1403 0 : return NULL;
1404 :
1405 0 : dim = isl_space_unwrap(isl_space_domain(isl_map_get_space(map)));
1406 0 : if (!dim)
1407 0 : return NULL;
1408 0 : n = isl_space_dim(dim, isl_dim_in);
1409 0 : isl_space_free(dim);
1410 :
1411 0 : ctx = isl_map_get_ctx(map);
1412 0 : info = isl_alloc_type(ctx, struct isl_sched_info);
1413 0 : if (!info)
1414 0 : return NULL;
1415 0 : info->is_cst = isl_alloc_array(ctx, int, n);
1416 0 : info->cst = isl_vec_alloc(ctx, n);
1417 0 : if (n && (!info->is_cst || !info->cst))
1418 : goto error;
1419 :
1420 0 : for (i = 0; i < n; ++i) {
1421 : isl_val *v;
1422 :
1423 0 : v = isl_map_plain_get_val_if_fixed(map, isl_dim_in, i);
1424 0 : if (!v)
1425 0 : goto error;
1426 0 : info->is_cst[i] = !isl_val_is_nan(v);
1427 0 : if (info->is_cst[i])
1428 0 : info->cst = isl_vec_set_element_val(info->cst, i, v);
1429 : else
1430 0 : isl_val_free(v);
1431 : }
1432 :
1433 0 : return info;
1434 : error:
1435 0 : sched_info_free(info);
1436 0 : return NULL;
1437 : }
1438 :
1439 : /* The different types of access relations that isl_union_access_info
1440 : * keeps track of.
1441 :
1442 : * "isl_access_sink" represents the sink accesses.
1443 : * "isl_access_must_source" represents the definite source accesses.
1444 : * "isl_access_may_source" represents the possible source accesses.
1445 : * "isl_access_kill" represents the kills.
1446 : *
1447 : * isl_access_sink is sometimes treated differently and
1448 : * should therefore appear first.
1449 : */
1450 : enum isl_access_type {
1451 : isl_access_sink,
1452 : isl_access_must_source,
1453 : isl_access_may_source,
1454 : isl_access_kill,
1455 : isl_access_end
1456 : };
1457 :
1458 : /* This structure represents the input for a dependence analysis computation.
1459 : *
1460 : * "access" contains the access relations.
1461 : *
1462 : * "schedule" or "schedule_map" represents the execution order.
1463 : * Exactly one of these fields should be NULL. The other field
1464 : * determines the execution order.
1465 : *
1466 : * The domains of these four maps refer to the same iteration spaces(s).
1467 : * The ranges of the first three maps also refer to the same data space(s).
1468 : *
1469 : * After a call to isl_union_access_info_introduce_schedule,
1470 : * the "schedule_map" field no longer contains useful information.
1471 : */
1472 : struct isl_union_access_info {
1473 : isl_union_map *access[isl_access_end];
1474 :
1475 : isl_schedule *schedule;
1476 : isl_union_map *schedule_map;
1477 : };
1478 :
1479 : /* Free "access" and return NULL.
1480 : */
1481 0 : __isl_null isl_union_access_info *isl_union_access_info_free(
1482 : __isl_take isl_union_access_info *access)
1483 : {
1484 : enum isl_access_type i;
1485 :
1486 0 : if (!access)
1487 0 : return NULL;
1488 :
1489 0 : for (i = isl_access_sink; i < isl_access_end; ++i)
1490 0 : isl_union_map_free(access->access[i]);
1491 0 : isl_schedule_free(access->schedule);
1492 0 : isl_union_map_free(access->schedule_map);
1493 0 : free(access);
1494 :
1495 0 : return NULL;
1496 : }
1497 :
1498 : /* Return the isl_ctx to which "access" belongs.
1499 : */
1500 0 : isl_ctx *isl_union_access_info_get_ctx(__isl_keep isl_union_access_info *access)
1501 : {
1502 0 : if (!access)
1503 0 : return NULL;
1504 0 : return isl_union_map_get_ctx(access->access[isl_access_sink]);
1505 : }
1506 :
1507 : /* Construct an empty (invalid) isl_union_access_info object.
1508 : * The caller is responsible for setting the sink access relation and
1509 : * initializing all the other fields, e.g., by calling
1510 : * isl_union_access_info_init.
1511 : */
1512 0 : static __isl_give isl_union_access_info *isl_union_access_info_alloc(
1513 : isl_ctx *ctx)
1514 : {
1515 0 : return isl_calloc_type(ctx, isl_union_access_info);
1516 : }
1517 :
1518 : /* Initialize all the fields of "info", except the sink access relation,
1519 : * which is assumed to have been set by the caller.
1520 : *
1521 : * By default, we use the schedule field of the isl_union_access_info,
1522 : * but this may be overridden by a call
1523 : * to isl_union_access_info_set_schedule_map.
1524 : */
1525 0 : static __isl_give isl_union_access_info *isl_union_access_info_init(
1526 : __isl_take isl_union_access_info *info)
1527 : {
1528 : isl_space *space;
1529 : isl_union_map *empty;
1530 : enum isl_access_type i;
1531 :
1532 0 : if (!info)
1533 0 : return NULL;
1534 0 : if (!info->access[isl_access_sink])
1535 0 : return isl_union_access_info_free(info);
1536 :
1537 0 : space = isl_union_map_get_space(info->access[isl_access_sink]);
1538 0 : empty = isl_union_map_empty(isl_space_copy(space));
1539 0 : for (i = isl_access_sink + 1; i < isl_access_end; ++i)
1540 0 : if (!info->access[i])
1541 0 : info->access[i] = isl_union_map_copy(empty);
1542 0 : isl_union_map_free(empty);
1543 0 : if (!info->schedule && !info->schedule_map)
1544 0 : info->schedule = isl_schedule_empty(isl_space_copy(space));
1545 0 : isl_space_free(space);
1546 :
1547 0 : for (i = isl_access_sink + 1; i < isl_access_end; ++i)
1548 0 : if (!info->access[i])
1549 0 : return isl_union_access_info_free(info);
1550 0 : if (!info->schedule && !info->schedule_map)
1551 0 : return isl_union_access_info_free(info);
1552 :
1553 0 : return info;
1554 : }
1555 :
1556 : /* Create a new isl_union_access_info with the given sink accesses and
1557 : * and no other accesses or schedule information.
1558 : */
1559 0 : __isl_give isl_union_access_info *isl_union_access_info_from_sink(
1560 : __isl_take isl_union_map *sink)
1561 : {
1562 : isl_ctx *ctx;
1563 : isl_union_access_info *access;
1564 :
1565 0 : if (!sink)
1566 0 : return NULL;
1567 0 : ctx = isl_union_map_get_ctx(sink);
1568 0 : access = isl_union_access_info_alloc(ctx);
1569 0 : if (!access)
1570 0 : goto error;
1571 0 : access->access[isl_access_sink] = sink;
1572 0 : return isl_union_access_info_init(access);
1573 : error:
1574 0 : isl_union_map_free(sink);
1575 0 : return NULL;
1576 : }
1577 :
1578 : /* Replace the access relation of type "type" of "info" by "access".
1579 : */
1580 0 : static __isl_give isl_union_access_info *isl_union_access_info_set(
1581 : __isl_take isl_union_access_info *info,
1582 : enum isl_access_type type, __isl_take isl_union_map *access)
1583 : {
1584 0 : if (!info || !access)
1585 : goto error;
1586 :
1587 0 : isl_union_map_free(info->access[type]);
1588 0 : info->access[type] = access;
1589 :
1590 0 : return info;
1591 : error:
1592 0 : isl_union_access_info_free(info);
1593 0 : isl_union_map_free(access);
1594 0 : return NULL;
1595 : }
1596 :
1597 : /* Replace the definite source accesses of "access" by "must_source".
1598 : */
1599 0 : __isl_give isl_union_access_info *isl_union_access_info_set_must_source(
1600 : __isl_take isl_union_access_info *access,
1601 : __isl_take isl_union_map *must_source)
1602 : {
1603 0 : return isl_union_access_info_set(access, isl_access_must_source,
1604 : must_source);
1605 : }
1606 :
1607 : /* Replace the possible source accesses of "access" by "may_source".
1608 : */
1609 0 : __isl_give isl_union_access_info *isl_union_access_info_set_may_source(
1610 : __isl_take isl_union_access_info *access,
1611 : __isl_take isl_union_map *may_source)
1612 : {
1613 0 : return isl_union_access_info_set(access, isl_access_may_source,
1614 : may_source);
1615 : }
1616 :
1617 : /* Replace the kills of "info" by "kill".
1618 : */
1619 0 : __isl_give isl_union_access_info *isl_union_access_info_set_kill(
1620 : __isl_take isl_union_access_info *info, __isl_take isl_union_map *kill)
1621 : {
1622 0 : return isl_union_access_info_set(info, isl_access_kill, kill);
1623 : }
1624 :
1625 : /* Return the access relation of type "type" of "info".
1626 : */
1627 0 : static __isl_give isl_union_map *isl_union_access_info_get(
1628 : __isl_keep isl_union_access_info *info, enum isl_access_type type)
1629 : {
1630 0 : if (!info)
1631 0 : return NULL;
1632 0 : return isl_union_map_copy(info->access[type]);
1633 : }
1634 :
1635 : /* Return the definite source accesses of "info".
1636 : */
1637 0 : __isl_give isl_union_map *isl_union_access_info_get_must_source(
1638 : __isl_keep isl_union_access_info *info)
1639 : {
1640 0 : return isl_union_access_info_get(info, isl_access_must_source);
1641 : }
1642 :
1643 : /* Return the possible source accesses of "info".
1644 : */
1645 0 : __isl_give isl_union_map *isl_union_access_info_get_may_source(
1646 : __isl_keep isl_union_access_info *info)
1647 : {
1648 0 : return isl_union_access_info_get(info, isl_access_may_source);
1649 : }
1650 :
1651 : /* Return the kills of "info".
1652 : */
1653 0 : __isl_give isl_union_map *isl_union_access_info_get_kill(
1654 : __isl_keep isl_union_access_info *info)
1655 : {
1656 0 : return isl_union_access_info_get(info, isl_access_kill);
1657 : }
1658 :
1659 : /* Does "info" specify any kills?
1660 : */
1661 0 : static isl_bool isl_union_access_has_kill(
1662 : __isl_keep isl_union_access_info *info)
1663 : {
1664 : isl_bool empty;
1665 :
1666 0 : if (!info)
1667 0 : return isl_bool_error;
1668 0 : empty = isl_union_map_is_empty(info->access[isl_access_kill]);
1669 0 : return isl_bool_not(empty);
1670 : }
1671 :
1672 : /* Replace the schedule of "access" by "schedule".
1673 : * Also free the schedule_map in case it was set last.
1674 : */
1675 0 : __isl_give isl_union_access_info *isl_union_access_info_set_schedule(
1676 : __isl_take isl_union_access_info *access,
1677 : __isl_take isl_schedule *schedule)
1678 : {
1679 0 : if (!access || !schedule)
1680 : goto error;
1681 :
1682 0 : access->schedule_map = isl_union_map_free(access->schedule_map);
1683 0 : isl_schedule_free(access->schedule);
1684 0 : access->schedule = schedule;
1685 :
1686 0 : return access;
1687 : error:
1688 0 : isl_union_access_info_free(access);
1689 0 : isl_schedule_free(schedule);
1690 0 : return NULL;
1691 : }
1692 :
1693 : /* Replace the schedule map of "access" by "schedule_map".
1694 : * Also free the schedule in case it was set last.
1695 : */
1696 0 : __isl_give isl_union_access_info *isl_union_access_info_set_schedule_map(
1697 : __isl_take isl_union_access_info *access,
1698 : __isl_take isl_union_map *schedule_map)
1699 : {
1700 0 : if (!access || !schedule_map)
1701 : goto error;
1702 :
1703 0 : isl_union_map_free(access->schedule_map);
1704 0 : access->schedule = isl_schedule_free(access->schedule);
1705 0 : access->schedule_map = schedule_map;
1706 :
1707 0 : return access;
1708 : error:
1709 0 : isl_union_access_info_free(access);
1710 0 : isl_union_map_free(schedule_map);
1711 0 : return NULL;
1712 : }
1713 :
1714 0 : __isl_give isl_union_access_info *isl_union_access_info_copy(
1715 : __isl_keep isl_union_access_info *access)
1716 : {
1717 : isl_union_access_info *copy;
1718 : enum isl_access_type i;
1719 :
1720 0 : if (!access)
1721 0 : return NULL;
1722 0 : copy = isl_union_access_info_from_sink(
1723 : isl_union_map_copy(access->access[isl_access_sink]));
1724 0 : for (i = isl_access_sink + 1; i < isl_access_end; ++i)
1725 0 : copy = isl_union_access_info_set(copy, i,
1726 : isl_union_map_copy(access->access[i]));
1727 0 : if (access->schedule)
1728 0 : copy = isl_union_access_info_set_schedule(copy,
1729 : isl_schedule_copy(access->schedule));
1730 : else
1731 0 : copy = isl_union_access_info_set_schedule_map(copy,
1732 : isl_union_map_copy(access->schedule_map));
1733 :
1734 0 : return copy;
1735 : }
1736 :
1737 : /* Print a key-value pair of a YAML mapping to "p",
1738 : * with key "name" and value "umap".
1739 : */
1740 0 : static __isl_give isl_printer *print_union_map_field(__isl_take isl_printer *p,
1741 : const char *name, __isl_keep isl_union_map *umap)
1742 : {
1743 0 : p = isl_printer_print_str(p, name);
1744 0 : p = isl_printer_yaml_next(p);
1745 0 : p = isl_printer_print_str(p, "\"");
1746 0 : p = isl_printer_print_union_map(p, umap);
1747 0 : p = isl_printer_print_str(p, "\"");
1748 0 : p = isl_printer_yaml_next(p);
1749 :
1750 0 : return p;
1751 : }
1752 :
1753 : /* An enumeration of the various keys that may appear in a YAML mapping
1754 : * of an isl_union_access_info object.
1755 : * The keys for the access relation types are assumed to have the same values
1756 : * as the access relation types in isl_access_type.
1757 : */
1758 : enum isl_ai_key {
1759 : isl_ai_key_error = -1,
1760 : isl_ai_key_sink = isl_access_sink,
1761 : isl_ai_key_must_source = isl_access_must_source,
1762 : isl_ai_key_may_source = isl_access_may_source,
1763 : isl_ai_key_kill = isl_access_kill,
1764 : isl_ai_key_schedule_map,
1765 : isl_ai_key_schedule,
1766 : isl_ai_key_end
1767 : };
1768 :
1769 : /* Textual representations of the YAML keys for an isl_union_access_info
1770 : * object.
1771 : */
1772 : static char *key_str[] = {
1773 : [isl_ai_key_sink] = "sink",
1774 : [isl_ai_key_must_source] = "must_source",
1775 : [isl_ai_key_may_source] = "may_source",
1776 : [isl_ai_key_kill] = "kill",
1777 : [isl_ai_key_schedule_map] = "schedule_map",
1778 : [isl_ai_key_schedule] = "schedule",
1779 : };
1780 :
1781 : /* Print a key-value pair corresponding to the access relation of type "type"
1782 : * of a YAML mapping of "info" to "p".
1783 : *
1784 : * The sink access relation is always printed, but any other access relation
1785 : * is only printed if it is non-empty.
1786 : */
1787 0 : static __isl_give isl_printer *print_access_field(__isl_take isl_printer *p,
1788 : __isl_keep isl_union_access_info *info, enum isl_access_type type)
1789 : {
1790 0 : if (type != isl_access_sink) {
1791 : isl_bool empty;
1792 :
1793 0 : empty = isl_union_map_is_empty(info->access[type]);
1794 0 : if (empty < 0)
1795 0 : return isl_printer_free(p);
1796 0 : if (empty)
1797 0 : return p;
1798 : }
1799 0 : return print_union_map_field(p, key_str[type], info->access[type]);
1800 : }
1801 :
1802 : /* Print the information contained in "access" to "p".
1803 : * The information is printed as a YAML document.
1804 : */
1805 0 : __isl_give isl_printer *isl_printer_print_union_access_info(
1806 : __isl_take isl_printer *p, __isl_keep isl_union_access_info *access)
1807 : {
1808 : enum isl_access_type i;
1809 :
1810 0 : if (!access)
1811 0 : return isl_printer_free(p);
1812 :
1813 0 : p = isl_printer_yaml_start_mapping(p);
1814 0 : for (i = isl_access_sink; i < isl_access_end; ++i)
1815 0 : p = print_access_field(p, access, i);
1816 0 : if (access->schedule) {
1817 0 : p = isl_printer_print_str(p, key_str[isl_ai_key_schedule]);
1818 0 : p = isl_printer_yaml_next(p);
1819 0 : p = isl_printer_print_schedule(p, access->schedule);
1820 0 : p = isl_printer_yaml_next(p);
1821 : } else {
1822 0 : p = print_union_map_field(p, key_str[isl_ai_key_schedule_map],
1823 : access->schedule_map);
1824 : }
1825 0 : p = isl_printer_yaml_end_mapping(p);
1826 :
1827 0 : return p;
1828 : }
1829 :
1830 : /* Return a string representation of the information in "access".
1831 : * The information is printed in flow format.
1832 : */
1833 0 : __isl_give char *isl_union_access_info_to_str(
1834 : __isl_keep isl_union_access_info *access)
1835 : {
1836 : isl_printer *p;
1837 : char *s;
1838 :
1839 0 : if (!access)
1840 0 : return NULL;
1841 :
1842 0 : p = isl_printer_to_str(isl_union_access_info_get_ctx(access));
1843 0 : p = isl_printer_set_yaml_style(p, ISL_YAML_STYLE_FLOW);
1844 0 : p = isl_printer_print_union_access_info(p, access);
1845 0 : s = isl_printer_get_str(p);
1846 0 : isl_printer_free(p);
1847 :
1848 0 : return s;
1849 : }
1850 :
1851 : #undef KEY
1852 : #define KEY enum isl_ai_key
1853 : #undef KEY_ERROR
1854 : #define KEY_ERROR isl_ai_key_error
1855 : #undef KEY_END
1856 : #define KEY_END isl_ai_key_end
1857 : #include "extract_key.c"
1858 :
1859 : #undef BASE
1860 : #define BASE union_map
1861 : #include "read_in_string_templ.c"
1862 :
1863 : /* Read an isl_union_access_info object from "s".
1864 : *
1865 : * Start off with an empty (invalid) isl_union_access_info object and
1866 : * then fill up the fields based on the input.
1867 : * The input needs to contain at least a description of the sink
1868 : * access relation as well as some form of schedule.
1869 : * The other access relations are set to empty relations
1870 : * by isl_union_access_info_init if they are not specified in the input.
1871 : */
1872 0 : __isl_give isl_union_access_info *isl_stream_read_union_access_info(
1873 : isl_stream *s)
1874 : {
1875 : isl_ctx *ctx;
1876 : isl_union_access_info *info;
1877 : int more;
1878 0 : int sink_set = 0;
1879 0 : int schedule_set = 0;
1880 :
1881 0 : if (isl_stream_yaml_read_start_mapping(s))
1882 0 : return NULL;
1883 :
1884 0 : ctx = isl_stream_get_ctx(s);
1885 0 : info = isl_union_access_info_alloc(ctx);
1886 0 : while ((more = isl_stream_yaml_next(s)) > 0) {
1887 : enum isl_ai_key key;
1888 : isl_union_map *access, *schedule_map;
1889 : isl_schedule *schedule;
1890 :
1891 0 : key = get_key(s);
1892 0 : if (isl_stream_yaml_next(s) < 0)
1893 0 : return isl_union_access_info_free(info);
1894 0 : switch (key) {
1895 : case isl_ai_key_end:
1896 : case isl_ai_key_error:
1897 0 : return isl_union_access_info_free(info);
1898 : case isl_ai_key_sink:
1899 0 : sink_set = 1;
1900 : case isl_ai_key_must_source:
1901 : case isl_ai_key_may_source:
1902 : case isl_ai_key_kill:
1903 0 : access = read_union_map(s);
1904 0 : info = isl_union_access_info_set(info, key, access);
1905 0 : if (!info)
1906 0 : return NULL;
1907 0 : break;
1908 : case isl_ai_key_schedule_map:
1909 0 : schedule_set = 1;
1910 0 : schedule_map = read_union_map(s);
1911 0 : info = isl_union_access_info_set_schedule_map(info,
1912 : schedule_map);
1913 0 : if (!info)
1914 0 : return NULL;
1915 0 : break;
1916 : case isl_ai_key_schedule:
1917 0 : schedule_set = 1;
1918 0 : schedule = isl_stream_read_schedule(s);
1919 0 : info = isl_union_access_info_set_schedule(info,
1920 : schedule);
1921 0 : if (!info)
1922 0 : return NULL;
1923 0 : break;
1924 : }
1925 : }
1926 0 : if (more < 0)
1927 0 : return isl_union_access_info_free(info);
1928 :
1929 0 : if (isl_stream_yaml_read_end_mapping(s) < 0) {
1930 0 : isl_stream_error(s, NULL, "unexpected extra elements");
1931 0 : return isl_union_access_info_free(info);
1932 : }
1933 :
1934 0 : if (!sink_set) {
1935 0 : isl_stream_error(s, NULL, "no sink specified");
1936 0 : return isl_union_access_info_free(info);
1937 : }
1938 :
1939 0 : if (!schedule_set) {
1940 0 : isl_stream_error(s, NULL, "no schedule specified");
1941 0 : return isl_union_access_info_free(info);
1942 : }
1943 :
1944 0 : return isl_union_access_info_init(info);
1945 : }
1946 :
1947 : /* Read an isl_union_access_info object from the file "input".
1948 : */
1949 0 : __isl_give isl_union_access_info *isl_union_access_info_read_from_file(
1950 : isl_ctx *ctx, FILE *input)
1951 : {
1952 : isl_stream *s;
1953 : isl_union_access_info *access;
1954 :
1955 0 : s = isl_stream_new_file(ctx, input);
1956 0 : if (!s)
1957 0 : return NULL;
1958 0 : access = isl_stream_read_union_access_info(s);
1959 0 : isl_stream_free(s);
1960 :
1961 0 : return access;
1962 : }
1963 :
1964 : /* Update the fields of "access" such that they all have the same parameters,
1965 : * keeping in mind that the schedule_map field may be NULL and ignoring
1966 : * the schedule field.
1967 : */
1968 0 : static __isl_give isl_union_access_info *isl_union_access_info_align_params(
1969 : __isl_take isl_union_access_info *access)
1970 : {
1971 : isl_space *space;
1972 : enum isl_access_type i;
1973 :
1974 0 : if (!access)
1975 0 : return NULL;
1976 :
1977 0 : space = isl_union_map_get_space(access->access[isl_access_sink]);
1978 0 : for (i = isl_access_sink + 1; i < isl_access_end; ++i)
1979 0 : space = isl_space_align_params(space,
1980 : isl_union_map_get_space(access->access[i]));
1981 0 : if (access->schedule_map)
1982 0 : space = isl_space_align_params(space,
1983 : isl_union_map_get_space(access->schedule_map));
1984 0 : for (i = isl_access_sink; i < isl_access_end; ++i)
1985 0 : access->access[i] =
1986 0 : isl_union_map_align_params(access->access[i],
1987 : isl_space_copy(space));
1988 0 : if (!access->schedule_map) {
1989 0 : isl_space_free(space);
1990 : } else {
1991 0 : access->schedule_map =
1992 0 : isl_union_map_align_params(access->schedule_map, space);
1993 0 : if (!access->schedule_map)
1994 0 : return isl_union_access_info_free(access);
1995 : }
1996 :
1997 0 : for (i = isl_access_sink; i < isl_access_end; ++i)
1998 0 : if (!access->access[i])
1999 0 : return isl_union_access_info_free(access);
2000 :
2001 0 : return access;
2002 : }
2003 :
2004 : /* Prepend the schedule dimensions to the iteration domains.
2005 : *
2006 : * That is, if the schedule is of the form
2007 : *
2008 : * D -> S
2009 : *
2010 : * while the access relations are of the form
2011 : *
2012 : * D -> A
2013 : *
2014 : * then the updated access relations are of the form
2015 : *
2016 : * [S -> D] -> A
2017 : *
2018 : * The schedule map is also replaced by the map
2019 : *
2020 : * [S -> D] -> D
2021 : *
2022 : * that is used during the internal computation.
2023 : * Neither the original schedule map nor this updated schedule map
2024 : * are used after the call to this function.
2025 : */
2026 : static __isl_give isl_union_access_info *
2027 0 : isl_union_access_info_introduce_schedule(
2028 : __isl_take isl_union_access_info *access)
2029 : {
2030 : isl_union_map *sm;
2031 : enum isl_access_type i;
2032 :
2033 0 : if (!access)
2034 0 : return NULL;
2035 :
2036 0 : sm = isl_union_map_reverse(access->schedule_map);
2037 0 : sm = isl_union_map_range_map(sm);
2038 0 : for (i = isl_access_sink; i < isl_access_end; ++i)
2039 0 : access->access[i] =
2040 0 : isl_union_map_apply_range(isl_union_map_copy(sm),
2041 : access->access[i]);
2042 0 : access->schedule_map = sm;
2043 :
2044 0 : for (i = isl_access_sink; i < isl_access_end; ++i)
2045 0 : if (!access->access[i])
2046 0 : return isl_union_access_info_free(access);
2047 0 : if (!access->schedule_map)
2048 0 : return isl_union_access_info_free(access);
2049 :
2050 0 : return access;
2051 : }
2052 :
2053 : /* This structure represents the result of a dependence analysis computation.
2054 : *
2055 : * "must_dep" represents the full definite dependences
2056 : * "may_dep" represents the full non-definite dependences.
2057 : * Both are of the form
2058 : *
2059 : * [Source] -> [[Sink -> Data]]
2060 : *
2061 : * (after the schedule dimensions have been projected out).
2062 : * "must_no_source" represents the subset of the sink accesses for which
2063 : * definitely no source was found.
2064 : * "may_no_source" represents the subset of the sink accesses for which
2065 : * possibly, but not definitely, no source was found.
2066 : */
2067 : struct isl_union_flow {
2068 : isl_union_map *must_dep;
2069 : isl_union_map *may_dep;
2070 : isl_union_map *must_no_source;
2071 : isl_union_map *may_no_source;
2072 : };
2073 :
2074 : /* Return the isl_ctx to which "flow" belongs.
2075 : */
2076 0 : isl_ctx *isl_union_flow_get_ctx(__isl_keep isl_union_flow *flow)
2077 : {
2078 0 : return flow ? isl_union_map_get_ctx(flow->must_dep) : NULL;
2079 : }
2080 :
2081 : /* Free "flow" and return NULL.
2082 : */
2083 0 : __isl_null isl_union_flow *isl_union_flow_free(__isl_take isl_union_flow *flow)
2084 : {
2085 0 : if (!flow)
2086 0 : return NULL;
2087 0 : isl_union_map_free(flow->must_dep);
2088 0 : isl_union_map_free(flow->may_dep);
2089 0 : isl_union_map_free(flow->must_no_source);
2090 0 : isl_union_map_free(flow->may_no_source);
2091 0 : free(flow);
2092 0 : return NULL;
2093 : }
2094 :
2095 0 : void isl_union_flow_dump(__isl_keep isl_union_flow *flow)
2096 : {
2097 0 : if (!flow)
2098 0 : return;
2099 :
2100 0 : fprintf(stderr, "must dependences: ");
2101 0 : isl_union_map_dump(flow->must_dep);
2102 0 : fprintf(stderr, "may dependences: ");
2103 0 : isl_union_map_dump(flow->may_dep);
2104 0 : fprintf(stderr, "must no source: ");
2105 0 : isl_union_map_dump(flow->must_no_source);
2106 0 : fprintf(stderr, "may no source: ");
2107 0 : isl_union_map_dump(flow->may_no_source);
2108 : }
2109 :
2110 : /* Return the full definite dependences in "flow", with accessed elements.
2111 : */
2112 0 : __isl_give isl_union_map *isl_union_flow_get_full_must_dependence(
2113 : __isl_keep isl_union_flow *flow)
2114 : {
2115 0 : if (!flow)
2116 0 : return NULL;
2117 0 : return isl_union_map_copy(flow->must_dep);
2118 : }
2119 :
2120 : /* Return the full possible dependences in "flow", including the definite
2121 : * dependences, with accessed elements.
2122 : */
2123 0 : __isl_give isl_union_map *isl_union_flow_get_full_may_dependence(
2124 : __isl_keep isl_union_flow *flow)
2125 : {
2126 0 : if (!flow)
2127 0 : return NULL;
2128 0 : return isl_union_map_union(isl_union_map_copy(flow->must_dep),
2129 : isl_union_map_copy(flow->may_dep));
2130 : }
2131 :
2132 : /* Return the definite dependences in "flow", without the accessed elements.
2133 : */
2134 0 : __isl_give isl_union_map *isl_union_flow_get_must_dependence(
2135 : __isl_keep isl_union_flow *flow)
2136 : {
2137 : isl_union_map *dep;
2138 :
2139 0 : if (!flow)
2140 0 : return NULL;
2141 0 : dep = isl_union_map_copy(flow->must_dep);
2142 0 : return isl_union_map_range_factor_domain(dep);
2143 : }
2144 :
2145 : /* Return the possible dependences in "flow", including the definite
2146 : * dependences, without the accessed elements.
2147 : */
2148 0 : __isl_give isl_union_map *isl_union_flow_get_may_dependence(
2149 : __isl_keep isl_union_flow *flow)
2150 : {
2151 : isl_union_map *dep;
2152 :
2153 0 : if (!flow)
2154 0 : return NULL;
2155 0 : dep = isl_union_map_union(isl_union_map_copy(flow->must_dep),
2156 : isl_union_map_copy(flow->may_dep));
2157 0 : return isl_union_map_range_factor_domain(dep);
2158 : }
2159 :
2160 : /* Return the non-definite dependences in "flow".
2161 : */
2162 0 : static __isl_give isl_union_map *isl_union_flow_get_non_must_dependence(
2163 : __isl_keep isl_union_flow *flow)
2164 : {
2165 0 : if (!flow)
2166 0 : return NULL;
2167 0 : return isl_union_map_copy(flow->may_dep);
2168 : }
2169 :
2170 : /* Return the subset of the sink accesses for which definitely
2171 : * no source was found.
2172 : */
2173 0 : __isl_give isl_union_map *isl_union_flow_get_must_no_source(
2174 : __isl_keep isl_union_flow *flow)
2175 : {
2176 0 : if (!flow)
2177 0 : return NULL;
2178 0 : return isl_union_map_copy(flow->must_no_source);
2179 : }
2180 :
2181 : /* Return the subset of the sink accesses for which possibly
2182 : * no source was found, including those for which definitely
2183 : * no source was found.
2184 : */
2185 0 : __isl_give isl_union_map *isl_union_flow_get_may_no_source(
2186 : __isl_keep isl_union_flow *flow)
2187 : {
2188 0 : if (!flow)
2189 0 : return NULL;
2190 0 : return isl_union_map_union(isl_union_map_copy(flow->must_no_source),
2191 : isl_union_map_copy(flow->may_no_source));
2192 : }
2193 :
2194 : /* Return the subset of the sink accesses for which possibly, but not
2195 : * definitely, no source was found.
2196 : */
2197 0 : static __isl_give isl_union_map *isl_union_flow_get_non_must_no_source(
2198 : __isl_keep isl_union_flow *flow)
2199 : {
2200 0 : if (!flow)
2201 0 : return NULL;
2202 0 : return isl_union_map_copy(flow->may_no_source);
2203 : }
2204 :
2205 : /* Create a new isl_union_flow object, initialized with empty
2206 : * dependence relations and sink subsets.
2207 : */
2208 0 : static __isl_give isl_union_flow *isl_union_flow_alloc(
2209 : __isl_take isl_space *space)
2210 : {
2211 : isl_ctx *ctx;
2212 : isl_union_map *empty;
2213 : isl_union_flow *flow;
2214 :
2215 0 : if (!space)
2216 0 : return NULL;
2217 0 : ctx = isl_space_get_ctx(space);
2218 0 : flow = isl_alloc_type(ctx, isl_union_flow);
2219 0 : if (!flow)
2220 0 : goto error;
2221 :
2222 0 : empty = isl_union_map_empty(space);
2223 0 : flow->must_dep = isl_union_map_copy(empty);
2224 0 : flow->may_dep = isl_union_map_copy(empty);
2225 0 : flow->must_no_source = isl_union_map_copy(empty);
2226 0 : flow->may_no_source = empty;
2227 :
2228 0 : if (!flow->must_dep || !flow->may_dep ||
2229 0 : !flow->must_no_source || !flow->may_no_source)
2230 0 : return isl_union_flow_free(flow);
2231 :
2232 0 : return flow;
2233 : error:
2234 0 : isl_space_free(space);
2235 0 : return NULL;
2236 : }
2237 :
2238 : /* Copy this isl_union_flow object.
2239 : */
2240 0 : __isl_give isl_union_flow *isl_union_flow_copy(__isl_keep isl_union_flow *flow)
2241 : {
2242 : isl_union_flow *copy;
2243 :
2244 0 : if (!flow)
2245 0 : return NULL;
2246 :
2247 0 : copy = isl_union_flow_alloc(isl_union_map_get_space(flow->must_dep));
2248 :
2249 0 : if (!copy)
2250 0 : return NULL;
2251 :
2252 0 : copy->must_dep = isl_union_map_union(copy->must_dep,
2253 : isl_union_map_copy(flow->must_dep));
2254 0 : copy->may_dep = isl_union_map_union(copy->may_dep,
2255 : isl_union_map_copy(flow->may_dep));
2256 0 : copy->must_no_source = isl_union_map_union(copy->must_no_source,
2257 : isl_union_map_copy(flow->must_no_source));
2258 0 : copy->may_no_source = isl_union_map_union(copy->may_no_source,
2259 : isl_union_map_copy(flow->may_no_source));
2260 :
2261 0 : if (!copy->must_dep || !copy->may_dep ||
2262 0 : !copy->must_no_source || !copy->may_no_source)
2263 0 : return isl_union_flow_free(copy);
2264 :
2265 0 : return copy;
2266 : }
2267 :
2268 : /* Drop the schedule dimensions from the iteration domains in "flow".
2269 : * In particular, the schedule dimensions have been prepended
2270 : * to the iteration domains prior to the dependence analysis by
2271 : * replacing the iteration domain D, by the wrapped map [S -> D].
2272 : * Replace these wrapped maps by the original D.
2273 : *
2274 : * In particular, the dependences computed by access_info_compute_flow_core
2275 : * are of the form
2276 : *
2277 : * [S -> D] -> [[S' -> D'] -> A]
2278 : *
2279 : * The schedule dimensions are projected out by first currying the range,
2280 : * resulting in
2281 : *
2282 : * [S -> D] -> [S' -> [D' -> A]]
2283 : *
2284 : * and then computing the factor range
2285 : *
2286 : * D -> [D' -> A]
2287 : */
2288 0 : static __isl_give isl_union_flow *isl_union_flow_drop_schedule(
2289 : __isl_take isl_union_flow *flow)
2290 : {
2291 0 : if (!flow)
2292 0 : return NULL;
2293 :
2294 0 : flow->must_dep = isl_union_map_range_curry(flow->must_dep);
2295 0 : flow->must_dep = isl_union_map_factor_range(flow->must_dep);
2296 0 : flow->may_dep = isl_union_map_range_curry(flow->may_dep);
2297 0 : flow->may_dep = isl_union_map_factor_range(flow->may_dep);
2298 0 : flow->must_no_source =
2299 0 : isl_union_map_domain_factor_range(flow->must_no_source);
2300 0 : flow->may_no_source =
2301 0 : isl_union_map_domain_factor_range(flow->may_no_source);
2302 :
2303 0 : if (!flow->must_dep || !flow->may_dep ||
2304 0 : !flow->must_no_source || !flow->may_no_source)
2305 0 : return isl_union_flow_free(flow);
2306 :
2307 0 : return flow;
2308 : }
2309 :
2310 : struct isl_compute_flow_data {
2311 : isl_union_map *must_source;
2312 : isl_union_map *may_source;
2313 : isl_union_flow *flow;
2314 :
2315 : int count;
2316 : int must;
2317 : isl_space *dim;
2318 : struct isl_sched_info *sink_info;
2319 : struct isl_sched_info **source_info;
2320 : isl_access_info *accesses;
2321 : };
2322 :
2323 0 : static isl_stat count_matching_array(__isl_take isl_map *map, void *user)
2324 : {
2325 : int eq;
2326 : isl_space *dim;
2327 : struct isl_compute_flow_data *data;
2328 :
2329 0 : data = (struct isl_compute_flow_data *)user;
2330 :
2331 0 : dim = isl_space_range(isl_map_get_space(map));
2332 :
2333 0 : eq = isl_space_is_equal(dim, data->dim);
2334 :
2335 0 : isl_space_free(dim);
2336 0 : isl_map_free(map);
2337 :
2338 0 : if (eq < 0)
2339 0 : return isl_stat_error;
2340 0 : if (eq)
2341 0 : data->count++;
2342 :
2343 0 : return isl_stat_ok;
2344 : }
2345 :
2346 0 : static isl_stat collect_matching_array(__isl_take isl_map *map, void *user)
2347 : {
2348 : int eq;
2349 : isl_space *dim;
2350 : struct isl_sched_info *info;
2351 : struct isl_compute_flow_data *data;
2352 :
2353 0 : data = (struct isl_compute_flow_data *)user;
2354 :
2355 0 : dim = isl_space_range(isl_map_get_space(map));
2356 :
2357 0 : eq = isl_space_is_equal(dim, data->dim);
2358 :
2359 0 : isl_space_free(dim);
2360 :
2361 0 : if (eq < 0)
2362 0 : goto error;
2363 0 : if (!eq) {
2364 0 : isl_map_free(map);
2365 0 : return isl_stat_ok;
2366 : }
2367 :
2368 0 : info = sched_info_alloc(map);
2369 0 : data->source_info[data->count] = info;
2370 :
2371 0 : data->accesses = isl_access_info_add_source(data->accesses,
2372 : map, data->must, info);
2373 :
2374 0 : data->count++;
2375 :
2376 0 : return isl_stat_ok;
2377 : error:
2378 0 : isl_map_free(map);
2379 0 : return isl_stat_error;
2380 : }
2381 :
2382 : /* Determine the shared nesting level and the "textual order" of
2383 : * the given accesses.
2384 : *
2385 : * We first determine the minimal schedule dimension for both accesses.
2386 : *
2387 : * If among those dimensions, we can find one where both have a fixed
2388 : * value and if moreover those values are different, then the previous
2389 : * dimension is the last shared nesting level and the textual order
2390 : * is determined based on the order of the fixed values.
2391 : * If no such fixed values can be found, then we set the shared
2392 : * nesting level to the minimal schedule dimension, with no textual ordering.
2393 : */
2394 0 : static int before(void *first, void *second)
2395 : {
2396 0 : struct isl_sched_info *info1 = first;
2397 0 : struct isl_sched_info *info2 = second;
2398 : int n1, n2;
2399 : int i;
2400 :
2401 0 : n1 = isl_vec_size(info1->cst);
2402 0 : n2 = isl_vec_size(info2->cst);
2403 :
2404 0 : if (n2 < n1)
2405 0 : n1 = n2;
2406 :
2407 0 : for (i = 0; i < n1; ++i) {
2408 : int r;
2409 : int cmp;
2410 :
2411 0 : if (!info1->is_cst[i])
2412 0 : continue;
2413 0 : if (!info2->is_cst[i])
2414 0 : continue;
2415 0 : cmp = isl_vec_cmp_element(info1->cst, info2->cst, i);
2416 0 : if (cmp == 0)
2417 0 : continue;
2418 :
2419 0 : r = 2 * i + (cmp < 0);
2420 :
2421 0 : return r;
2422 : }
2423 :
2424 0 : return 2 * n1;
2425 : }
2426 :
2427 : /* Check if the given two accesses may be coscheduled.
2428 : * If so, return 1. Otherwise return 0.
2429 : *
2430 : * Two accesses may only be coscheduled if the fixed schedule
2431 : * coordinates have the same values.
2432 : */
2433 0 : static int coscheduled(void *first, void *second)
2434 : {
2435 0 : struct isl_sched_info *info1 = first;
2436 0 : struct isl_sched_info *info2 = second;
2437 : int n1, n2;
2438 : int i;
2439 :
2440 0 : n1 = isl_vec_size(info1->cst);
2441 0 : n2 = isl_vec_size(info2->cst);
2442 :
2443 0 : if (n2 < n1)
2444 0 : n1 = n2;
2445 :
2446 0 : for (i = 0; i < n1; ++i) {
2447 : int cmp;
2448 :
2449 0 : if (!info1->is_cst[i])
2450 0 : continue;
2451 0 : if (!info2->is_cst[i])
2452 0 : continue;
2453 0 : cmp = isl_vec_cmp_element(info1->cst, info2->cst, i);
2454 0 : if (cmp != 0)
2455 0 : return 0;
2456 : }
2457 :
2458 0 : return 1;
2459 : }
2460 :
2461 : /* Given a sink access, look for all the source accesses that access
2462 : * the same array and perform dataflow analysis on them using
2463 : * isl_access_info_compute_flow_core.
2464 : */
2465 0 : static isl_stat compute_flow(__isl_take isl_map *map, void *user)
2466 : {
2467 : int i;
2468 : isl_ctx *ctx;
2469 : struct isl_compute_flow_data *data;
2470 : isl_flow *flow;
2471 : isl_union_flow *df;
2472 :
2473 0 : data = (struct isl_compute_flow_data *)user;
2474 0 : df = data->flow;
2475 :
2476 0 : ctx = isl_map_get_ctx(map);
2477 :
2478 0 : data->accesses = NULL;
2479 0 : data->sink_info = NULL;
2480 0 : data->source_info = NULL;
2481 0 : data->count = 0;
2482 0 : data->dim = isl_space_range(isl_map_get_space(map));
2483 :
2484 0 : if (isl_union_map_foreach_map(data->must_source,
2485 : &count_matching_array, data) < 0)
2486 0 : goto error;
2487 0 : if (isl_union_map_foreach_map(data->may_source,
2488 : &count_matching_array, data) < 0)
2489 0 : goto error;
2490 :
2491 0 : data->sink_info = sched_info_alloc(map);
2492 0 : data->source_info = isl_calloc_array(ctx, struct isl_sched_info *,
2493 : data->count);
2494 :
2495 0 : data->accesses = isl_access_info_alloc(isl_map_copy(map),
2496 0 : data->sink_info, &before, data->count);
2497 0 : if (!data->sink_info || (data->count && !data->source_info) ||
2498 0 : !data->accesses)
2499 : goto error;
2500 0 : data->accesses->coscheduled = &coscheduled;
2501 0 : data->count = 0;
2502 0 : data->must = 1;
2503 0 : if (isl_union_map_foreach_map(data->must_source,
2504 : &collect_matching_array, data) < 0)
2505 0 : goto error;
2506 0 : data->must = 0;
2507 0 : if (isl_union_map_foreach_map(data->may_source,
2508 : &collect_matching_array, data) < 0)
2509 0 : goto error;
2510 :
2511 0 : flow = access_info_compute_flow_core(data->accesses);
2512 0 : data->accesses = NULL;
2513 :
2514 0 : if (!flow)
2515 0 : goto error;
2516 :
2517 0 : df->must_no_source = isl_union_map_union(df->must_no_source,
2518 : isl_union_map_from_map(isl_flow_get_no_source(flow, 1)));
2519 0 : df->may_no_source = isl_union_map_union(df->may_no_source,
2520 : isl_union_map_from_map(isl_flow_get_no_source(flow, 0)));
2521 :
2522 0 : for (i = 0; i < flow->n_source; ++i) {
2523 : isl_union_map *dep;
2524 0 : dep = isl_union_map_from_map(isl_map_copy(flow->dep[i].map));
2525 0 : if (flow->dep[i].must)
2526 0 : df->must_dep = isl_union_map_union(df->must_dep, dep);
2527 : else
2528 0 : df->may_dep = isl_union_map_union(df->may_dep, dep);
2529 : }
2530 :
2531 0 : isl_flow_free(flow);
2532 :
2533 0 : sched_info_free(data->sink_info);
2534 0 : if (data->source_info) {
2535 0 : for (i = 0; i < data->count; ++i)
2536 0 : sched_info_free(data->source_info[i]);
2537 0 : free(data->source_info);
2538 : }
2539 0 : isl_space_free(data->dim);
2540 0 : isl_map_free(map);
2541 :
2542 0 : return isl_stat_ok;
2543 : error:
2544 0 : isl_access_info_free(data->accesses);
2545 0 : sched_info_free(data->sink_info);
2546 0 : if (data->source_info) {
2547 0 : for (i = 0; i < data->count; ++i)
2548 0 : sched_info_free(data->source_info[i]);
2549 0 : free(data->source_info);
2550 : }
2551 0 : isl_space_free(data->dim);
2552 0 : isl_map_free(map);
2553 :
2554 0 : return isl_stat_error;
2555 : }
2556 :
2557 : /* Add the kills of "info" to the must-sources.
2558 : */
2559 : static __isl_give isl_union_access_info *
2560 0 : isl_union_access_info_add_kill_to_must_source(
2561 : __isl_take isl_union_access_info *info)
2562 : {
2563 : isl_union_map *must, *kill;
2564 :
2565 0 : must = isl_union_access_info_get_must_source(info);
2566 0 : kill = isl_union_access_info_get_kill(info);
2567 0 : must = isl_union_map_union(must, kill);
2568 0 : return isl_union_access_info_set_must_source(info, must);
2569 : }
2570 :
2571 : /* Drop dependences from "flow" that purely originate from kills.
2572 : * That is, only keep those dependences that originate from
2573 : * the original must-sources "must" and/or the original may-sources "may".
2574 : * In particular, "must" contains the must-sources from before
2575 : * the kills were added and "may" contains the may-source from before
2576 : * the kills were removed.
2577 : *
2578 : * The dependences are of the form
2579 : *
2580 : * Source -> [Sink -> Data]
2581 : *
2582 : * Only those dependences are kept where the Source -> Data part
2583 : * is a subset of the original may-sources or must-sources.
2584 : * Of those, only the must-dependences that intersect with the must-sources
2585 : * remain must-dependences.
2586 : * If there is some overlap between the may-sources and the must-sources,
2587 : * then the may-dependences and must-dependences may also overlap.
2588 : * This should be fine since the may-dependences are only kept
2589 : * disjoint from the must-dependences for the isl_union_map_compute_flow
2590 : * interface. This interface does not support kills, so it will
2591 : * not end up calling this function.
2592 : */
2593 0 : static __isl_give isl_union_flow *isl_union_flow_drop_kill_source(
2594 : __isl_take isl_union_flow *flow, __isl_take isl_union_map *must,
2595 : __isl_take isl_union_map *may)
2596 : {
2597 : isl_union_map *move;
2598 :
2599 0 : if (!flow)
2600 0 : goto error;
2601 0 : move = isl_union_map_copy(flow->must_dep);
2602 0 : move = isl_union_map_intersect_range_factor_range(move,
2603 : isl_union_map_copy(may));
2604 0 : may = isl_union_map_union(may, isl_union_map_copy(must));
2605 0 : flow->may_dep = isl_union_map_intersect_range_factor_range(
2606 : flow->may_dep, may);
2607 0 : flow->must_dep = isl_union_map_intersect_range_factor_range(
2608 : flow->must_dep, must);
2609 0 : flow->may_dep = isl_union_map_union(flow->may_dep, move);
2610 0 : if (!flow->must_dep || !flow->may_dep)
2611 0 : return isl_union_flow_free(flow);
2612 :
2613 0 : return flow;
2614 : error:
2615 0 : isl_union_map_free(must);
2616 0 : isl_union_map_free(may);
2617 0 : return NULL;
2618 : }
2619 :
2620 : /* Remove the must accesses from the may accesses.
2621 : *
2622 : * A must access always trumps a may access, so there is no need
2623 : * for a must access to also be considered as a may access. Doing so
2624 : * would only cost extra computations only to find out that
2625 : * the duplicated may access does not make any difference.
2626 : */
2627 0 : static __isl_give isl_union_access_info *isl_union_access_info_normalize(
2628 : __isl_take isl_union_access_info *access)
2629 : {
2630 0 : if (!access)
2631 0 : return NULL;
2632 0 : access->access[isl_access_may_source] =
2633 0 : isl_union_map_subtract(access->access[isl_access_may_source],
2634 : isl_union_map_copy(access->access[isl_access_must_source]));
2635 0 : if (!access->access[isl_access_may_source])
2636 0 : return isl_union_access_info_free(access);
2637 :
2638 0 : return access;
2639 : }
2640 :
2641 : /* Given a description of the "sink" accesses, the "source" accesses and
2642 : * a schedule, compute for each instance of a sink access
2643 : * and for each element accessed by that instance,
2644 : * the possible or definite source accesses that last accessed the
2645 : * element accessed by the sink access before this sink access
2646 : * in the sense that there is no intermediate definite source access.
2647 : *
2648 : * The must_no_source and may_no_source elements of the result
2649 : * are subsets of access->sink. The elements must_dep and may_dep
2650 : * map domain elements of access->{may,must)_source to
2651 : * domain elements of access->sink.
2652 : *
2653 : * This function is used when only the schedule map representation
2654 : * is available.
2655 : *
2656 : * We first prepend the schedule dimensions to the domain
2657 : * of the accesses so that we can easily compare their relative order.
2658 : * Then we consider each sink access individually in compute_flow.
2659 : */
2660 0 : static __isl_give isl_union_flow *compute_flow_union_map(
2661 : __isl_take isl_union_access_info *access)
2662 : {
2663 : struct isl_compute_flow_data data;
2664 : isl_union_map *sink;
2665 :
2666 0 : access = isl_union_access_info_align_params(access);
2667 0 : access = isl_union_access_info_introduce_schedule(access);
2668 0 : if (!access)
2669 0 : return NULL;
2670 :
2671 0 : data.must_source = access->access[isl_access_must_source];
2672 0 : data.may_source = access->access[isl_access_may_source];
2673 :
2674 0 : sink = access->access[isl_access_sink];
2675 0 : data.flow = isl_union_flow_alloc(isl_union_map_get_space(sink));
2676 :
2677 0 : if (isl_union_map_foreach_map(sink, &compute_flow, &data) < 0)
2678 0 : goto error;
2679 :
2680 0 : data.flow = isl_union_flow_drop_schedule(data.flow);
2681 :
2682 0 : isl_union_access_info_free(access);
2683 0 : return data.flow;
2684 : error:
2685 0 : isl_union_access_info_free(access);
2686 0 : isl_union_flow_free(data.flow);
2687 0 : return NULL;
2688 : }
2689 :
2690 : /* A schedule access relation.
2691 : *
2692 : * The access relation "access" is of the form [S -> D] -> A,
2693 : * where S corresponds to the prefix schedule at "node".
2694 : * "must" is only relevant for source accesses and indicates
2695 : * whether the access is a must source or a may source.
2696 : */
2697 : struct isl_scheduled_access {
2698 : isl_map *access;
2699 : int must;
2700 : isl_schedule_node *node;
2701 : };
2702 :
2703 : /* Data structure for keeping track of individual scheduled sink and source
2704 : * accesses when computing dependence analysis based on a schedule tree.
2705 : *
2706 : * "n_sink" is the number of used entries in "sink"
2707 : * "n_source" is the number of used entries in "source"
2708 : *
2709 : * "set_sink", "must" and "node" are only used inside collect_sink_source,
2710 : * to keep track of the current node and
2711 : * of what extract_sink_source needs to do.
2712 : */
2713 : struct isl_compute_flow_schedule_data {
2714 : isl_union_access_info *access;
2715 :
2716 : int n_sink;
2717 : int n_source;
2718 :
2719 : struct isl_scheduled_access *sink;
2720 : struct isl_scheduled_access *source;
2721 :
2722 : int set_sink;
2723 : int must;
2724 : isl_schedule_node *node;
2725 : };
2726 :
2727 : /* Align the parameters of all sinks with all sources.
2728 : *
2729 : * If there are no sinks or no sources, then no alignment is needed.
2730 : */
2731 0 : static void isl_compute_flow_schedule_data_align_params(
2732 : struct isl_compute_flow_schedule_data *data)
2733 : {
2734 : int i;
2735 : isl_space *space;
2736 :
2737 0 : if (data->n_sink == 0 || data->n_source == 0)
2738 0 : return;
2739 :
2740 0 : space = isl_map_get_space(data->sink[0].access);
2741 :
2742 0 : for (i = 1; i < data->n_sink; ++i)
2743 0 : space = isl_space_align_params(space,
2744 0 : isl_map_get_space(data->sink[i].access));
2745 0 : for (i = 0; i < data->n_source; ++i)
2746 0 : space = isl_space_align_params(space,
2747 0 : isl_map_get_space(data->source[i].access));
2748 :
2749 0 : for (i = 0; i < data->n_sink; ++i)
2750 0 : data->sink[i].access =
2751 0 : isl_map_align_params(data->sink[i].access,
2752 : isl_space_copy(space));
2753 0 : for (i = 0; i < data->n_source; ++i)
2754 0 : data->source[i].access =
2755 0 : isl_map_align_params(data->source[i].access,
2756 : isl_space_copy(space));
2757 :
2758 0 : isl_space_free(space);
2759 : }
2760 :
2761 : /* Free all the memory referenced from "data".
2762 : * Do not free "data" itself as it may be allocated on the stack.
2763 : */
2764 0 : static void isl_compute_flow_schedule_data_clear(
2765 : struct isl_compute_flow_schedule_data *data)
2766 : {
2767 : int i;
2768 :
2769 0 : if (!data->sink)
2770 0 : return;
2771 :
2772 0 : for (i = 0; i < data->n_sink; ++i) {
2773 0 : isl_map_free(data->sink[i].access);
2774 0 : isl_schedule_node_free(data->sink[i].node);
2775 : }
2776 :
2777 0 : for (i = 0; i < data->n_source; ++i) {
2778 0 : isl_map_free(data->source[i].access);
2779 0 : isl_schedule_node_free(data->source[i].node);
2780 : }
2781 :
2782 0 : free(data->sink);
2783 : }
2784 :
2785 : /* isl_schedule_foreach_schedule_node_top_down callback for counting
2786 : * (an upper bound on) the number of sinks and sources.
2787 : *
2788 : * Sinks and sources are only extracted at leaves of the tree,
2789 : * so we skip the node if it is not a leaf.
2790 : * Otherwise we increment data->n_sink and data->n_source with
2791 : * the number of spaces in the sink and source access domains
2792 : * that reach this node.
2793 : */
2794 0 : static isl_bool count_sink_source(__isl_keep isl_schedule_node *node,
2795 : void *user)
2796 : {
2797 0 : struct isl_compute_flow_schedule_data *data = user;
2798 : isl_union_set *domain;
2799 : isl_union_map *umap;
2800 0 : isl_bool r = isl_bool_false;
2801 :
2802 0 : if (isl_schedule_node_get_type(node) != isl_schedule_node_leaf)
2803 0 : return isl_bool_true;
2804 :
2805 0 : domain = isl_schedule_node_get_universe_domain(node);
2806 :
2807 0 : umap = isl_union_map_copy(data->access->access[isl_access_sink]);
2808 0 : umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(domain));
2809 0 : data->n_sink += isl_union_map_n_map(umap);
2810 0 : isl_union_map_free(umap);
2811 0 : if (!umap)
2812 0 : r = isl_bool_error;
2813 :
2814 0 : umap = isl_union_map_copy(data->access->access[isl_access_must_source]);
2815 0 : umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(domain));
2816 0 : data->n_source += isl_union_map_n_map(umap);
2817 0 : isl_union_map_free(umap);
2818 0 : if (!umap)
2819 0 : r = isl_bool_error;
2820 :
2821 0 : umap = isl_union_map_copy(data->access->access[isl_access_may_source]);
2822 0 : umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(domain));
2823 0 : data->n_source += isl_union_map_n_map(umap);
2824 0 : isl_union_map_free(umap);
2825 0 : if (!umap)
2826 0 : r = isl_bool_error;
2827 :
2828 0 : isl_union_set_free(domain);
2829 :
2830 0 : return r;
2831 : }
2832 :
2833 : /* Add a single scheduled sink or source (depending on data->set_sink)
2834 : * with scheduled access relation "map", must property data->must and
2835 : * schedule node data->node to the list of sinks or sources.
2836 : */
2837 0 : static isl_stat extract_sink_source(__isl_take isl_map *map, void *user)
2838 : {
2839 0 : struct isl_compute_flow_schedule_data *data = user;
2840 : struct isl_scheduled_access *access;
2841 :
2842 0 : if (data->set_sink)
2843 0 : access = data->sink + data->n_sink++;
2844 : else
2845 0 : access = data->source + data->n_source++;
2846 :
2847 0 : access->access = map;
2848 0 : access->must = data->must;
2849 0 : access->node = isl_schedule_node_copy(data->node);
2850 :
2851 0 : return isl_stat_ok;
2852 : }
2853 :
2854 : /* isl_schedule_foreach_schedule_node_top_down callback for collecting
2855 : * individual scheduled source and sink accesses (taking into account
2856 : * the domain of the schedule).
2857 : *
2858 : * We only collect accesses at the leaves of the schedule tree.
2859 : * We prepend the schedule dimensions at the leaf to the iteration
2860 : * domains of the source and sink accesses and then extract
2861 : * the individual accesses (per space).
2862 : *
2863 : * In particular, if the prefix schedule at the node is of the form
2864 : *
2865 : * D -> S
2866 : *
2867 : * while the access relations are of the form
2868 : *
2869 : * D -> A
2870 : *
2871 : * then the updated access relations are of the form
2872 : *
2873 : * [S -> D] -> A
2874 : *
2875 : * Note that S consists of a single space such that introducing S
2876 : * in the access relations does not increase the number of spaces.
2877 : */
2878 0 : static isl_bool collect_sink_source(__isl_keep isl_schedule_node *node,
2879 : void *user)
2880 : {
2881 0 : struct isl_compute_flow_schedule_data *data = user;
2882 : isl_union_map *prefix;
2883 : isl_union_map *umap;
2884 0 : isl_bool r = isl_bool_false;
2885 :
2886 0 : if (isl_schedule_node_get_type(node) != isl_schedule_node_leaf)
2887 0 : return isl_bool_true;
2888 :
2889 0 : data->node = node;
2890 :
2891 0 : prefix = isl_schedule_node_get_prefix_schedule_relation(node);
2892 0 : prefix = isl_union_map_reverse(prefix);
2893 0 : prefix = isl_union_map_range_map(prefix);
2894 :
2895 0 : data->set_sink = 1;
2896 0 : umap = isl_union_map_copy(data->access->access[isl_access_sink]);
2897 0 : umap = isl_union_map_apply_range(isl_union_map_copy(prefix), umap);
2898 0 : if (isl_union_map_foreach_map(umap, &extract_sink_source, data) < 0)
2899 0 : r = isl_bool_error;
2900 0 : isl_union_map_free(umap);
2901 :
2902 0 : data->set_sink = 0;
2903 0 : data->must = 1;
2904 0 : umap = isl_union_map_copy(data->access->access[isl_access_must_source]);
2905 0 : umap = isl_union_map_apply_range(isl_union_map_copy(prefix), umap);
2906 0 : if (isl_union_map_foreach_map(umap, &extract_sink_source, data) < 0)
2907 0 : r = isl_bool_error;
2908 0 : isl_union_map_free(umap);
2909 :
2910 0 : data->set_sink = 0;
2911 0 : data->must = 0;
2912 0 : umap = isl_union_map_copy(data->access->access[isl_access_may_source]);
2913 0 : umap = isl_union_map_apply_range(isl_union_map_copy(prefix), umap);
2914 0 : if (isl_union_map_foreach_map(umap, &extract_sink_source, data) < 0)
2915 0 : r = isl_bool_error;
2916 0 : isl_union_map_free(umap);
2917 :
2918 0 : isl_union_map_free(prefix);
2919 :
2920 0 : return r;
2921 : }
2922 :
2923 : /* isl_access_info_compute_flow callback for determining whether
2924 : * the shared nesting level and the ordering within that level
2925 : * for two scheduled accesses for use in compute_single_flow.
2926 : *
2927 : * The tokens passed to this function refer to the leaves
2928 : * in the schedule tree where the accesses take place.
2929 : *
2930 : * If n is the shared number of loops, then we need to return
2931 : * "2 * n + 1" if "first" precedes "second" inside the innermost
2932 : * shared loop and "2 * n" otherwise.
2933 : *
2934 : * The innermost shared ancestor may be the leaves themselves
2935 : * if the accesses take place in the same leaf. Otherwise,
2936 : * it is either a set node or a sequence node. Only in the case
2937 : * of a sequence node do we consider one access to precede the other.
2938 : */
2939 0 : static int before_node(void *first, void *second)
2940 : {
2941 0 : isl_schedule_node *node1 = first;
2942 0 : isl_schedule_node *node2 = second;
2943 : isl_schedule_node *shared;
2944 : int depth;
2945 0 : int before = 0;
2946 :
2947 0 : shared = isl_schedule_node_get_shared_ancestor(node1, node2);
2948 0 : if (!shared)
2949 0 : return -1;
2950 :
2951 0 : depth = isl_schedule_node_get_schedule_depth(shared);
2952 0 : if (isl_schedule_node_get_type(shared) == isl_schedule_node_sequence) {
2953 : int pos1, pos2;
2954 :
2955 0 : pos1 = isl_schedule_node_get_ancestor_child_position(node1,
2956 : shared);
2957 0 : pos2 = isl_schedule_node_get_ancestor_child_position(node2,
2958 : shared);
2959 0 : before = pos1 < pos2;
2960 : }
2961 :
2962 0 : isl_schedule_node_free(shared);
2963 :
2964 0 : return 2 * depth + before;
2965 : }
2966 :
2967 : /* Check if the given two accesses may be coscheduled.
2968 : * If so, return 1. Otherwise return 0.
2969 : *
2970 : * Two accesses may only be coscheduled if they appear in the same leaf.
2971 : */
2972 0 : static int coscheduled_node(void *first, void *second)
2973 : {
2974 0 : isl_schedule_node *node1 = first;
2975 0 : isl_schedule_node *node2 = second;
2976 :
2977 0 : return node1 == node2;
2978 : }
2979 :
2980 : /* Add the scheduled sources from "data" that access
2981 : * the same data space as "sink" to "access".
2982 : */
2983 0 : static __isl_give isl_access_info *add_matching_sources(
2984 : __isl_take isl_access_info *access, struct isl_scheduled_access *sink,
2985 : struct isl_compute_flow_schedule_data *data)
2986 : {
2987 : int i;
2988 : isl_space *space;
2989 :
2990 0 : space = isl_space_range(isl_map_get_space(sink->access));
2991 0 : for (i = 0; i < data->n_source; ++i) {
2992 : struct isl_scheduled_access *source;
2993 : isl_space *source_space;
2994 : int eq;
2995 :
2996 0 : source = &data->source[i];
2997 0 : source_space = isl_map_get_space(source->access);
2998 0 : source_space = isl_space_range(source_space);
2999 0 : eq = isl_space_is_equal(space, source_space);
3000 0 : isl_space_free(source_space);
3001 :
3002 0 : if (!eq)
3003 0 : continue;
3004 0 : if (eq < 0)
3005 0 : goto error;
3006 :
3007 0 : access = isl_access_info_add_source(access,
3008 0 : isl_map_copy(source->access), source->must, source->node);
3009 : }
3010 :
3011 0 : isl_space_free(space);
3012 0 : return access;
3013 : error:
3014 0 : isl_space_free(space);
3015 0 : isl_access_info_free(access);
3016 0 : return NULL;
3017 : }
3018 :
3019 : /* Given a scheduled sink access relation "sink", compute the corresponding
3020 : * dependences on the sources in "data" and add the computed dependences
3021 : * to "uf".
3022 : *
3023 : * The dependences computed by access_info_compute_flow_core are of the form
3024 : *
3025 : * [S -> I] -> [[S' -> I'] -> A]
3026 : *
3027 : * The schedule dimensions are projected out by first currying the range,
3028 : * resulting in
3029 : *
3030 : * [S -> I] -> [S' -> [I' -> A]]
3031 : *
3032 : * and then computing the factor range
3033 : *
3034 : * I -> [I' -> A]
3035 : */
3036 0 : static __isl_give isl_union_flow *compute_single_flow(
3037 : __isl_take isl_union_flow *uf, struct isl_scheduled_access *sink,
3038 : struct isl_compute_flow_schedule_data *data)
3039 : {
3040 : int i;
3041 : isl_access_info *access;
3042 : isl_flow *flow;
3043 : isl_map *map;
3044 :
3045 0 : if (!uf)
3046 0 : return NULL;
3047 :
3048 0 : access = isl_access_info_alloc(isl_map_copy(sink->access), sink->node,
3049 : &before_node, data->n_source);
3050 0 : if (access)
3051 0 : access->coscheduled = &coscheduled_node;
3052 0 : access = add_matching_sources(access, sink, data);
3053 :
3054 0 : flow = access_info_compute_flow_core(access);
3055 0 : if (!flow)
3056 0 : return isl_union_flow_free(uf);
3057 :
3058 0 : map = isl_map_domain_factor_range(isl_flow_get_no_source(flow, 1));
3059 0 : uf->must_no_source = isl_union_map_union(uf->must_no_source,
3060 : isl_union_map_from_map(map));
3061 0 : map = isl_map_domain_factor_range(isl_flow_get_no_source(flow, 0));
3062 0 : uf->may_no_source = isl_union_map_union(uf->may_no_source,
3063 : isl_union_map_from_map(map));
3064 :
3065 0 : for (i = 0; i < flow->n_source; ++i) {
3066 : isl_union_map *dep;
3067 :
3068 0 : map = isl_map_range_curry(isl_map_copy(flow->dep[i].map));
3069 0 : map = isl_map_factor_range(map);
3070 0 : dep = isl_union_map_from_map(map);
3071 0 : if (flow->dep[i].must)
3072 0 : uf->must_dep = isl_union_map_union(uf->must_dep, dep);
3073 : else
3074 0 : uf->may_dep = isl_union_map_union(uf->may_dep, dep);
3075 : }
3076 :
3077 0 : isl_flow_free(flow);
3078 :
3079 0 : return uf;
3080 : }
3081 :
3082 : /* Given a description of the "sink" accesses, the "source" accesses and
3083 : * a schedule, compute for each instance of a sink access
3084 : * and for each element accessed by that instance,
3085 : * the possible or definite source accesses that last accessed the
3086 : * element accessed by the sink access before this sink access
3087 : * in the sense that there is no intermediate definite source access.
3088 : * Only consider dependences between statement instances that belong
3089 : * to the domain of the schedule.
3090 : *
3091 : * The must_no_source and may_no_source elements of the result
3092 : * are subsets of access->sink. The elements must_dep and may_dep
3093 : * map domain elements of access->{may,must)_source to
3094 : * domain elements of access->sink.
3095 : *
3096 : * This function is used when a schedule tree representation
3097 : * is available.
3098 : *
3099 : * We extract the individual scheduled source and sink access relations
3100 : * (taking into account the domain of the schedule) and
3101 : * then compute dependences for each scheduled sink individually.
3102 : */
3103 0 : static __isl_give isl_union_flow *compute_flow_schedule(
3104 : __isl_take isl_union_access_info *access)
3105 : {
3106 0 : struct isl_compute_flow_schedule_data data = { access };
3107 : int i, n;
3108 : isl_ctx *ctx;
3109 : isl_space *space;
3110 : isl_union_flow *flow;
3111 :
3112 0 : ctx = isl_union_access_info_get_ctx(access);
3113 :
3114 0 : data.n_sink = 0;
3115 0 : data.n_source = 0;
3116 0 : if (isl_schedule_foreach_schedule_node_top_down(access->schedule,
3117 : &count_sink_source, &data) < 0)
3118 0 : goto error;
3119 :
3120 0 : n = data.n_sink + data.n_source;
3121 0 : data.sink = isl_calloc_array(ctx, struct isl_scheduled_access, n);
3122 0 : if (n && !data.sink)
3123 0 : goto error;
3124 0 : data.source = data.sink + data.n_sink;
3125 :
3126 0 : data.n_sink = 0;
3127 0 : data.n_source = 0;
3128 0 : if (isl_schedule_foreach_schedule_node_top_down(access->schedule,
3129 : &collect_sink_source, &data) < 0)
3130 0 : goto error;
3131 :
3132 0 : space = isl_union_map_get_space(access->access[isl_access_sink]);
3133 0 : flow = isl_union_flow_alloc(space);
3134 :
3135 0 : isl_compute_flow_schedule_data_align_params(&data);
3136 :
3137 0 : for (i = 0; i < data.n_sink; ++i)
3138 0 : flow = compute_single_flow(flow, &data.sink[i], &data);
3139 :
3140 0 : isl_compute_flow_schedule_data_clear(&data);
3141 :
3142 0 : isl_union_access_info_free(access);
3143 0 : return flow;
3144 : error:
3145 0 : isl_union_access_info_free(access);
3146 0 : isl_compute_flow_schedule_data_clear(&data);
3147 0 : return NULL;
3148 : }
3149 :
3150 : /* Given a description of the "sink" accesses, the "source" accesses and
3151 : * a schedule, compute for each instance of a sink access
3152 : * and for each element accessed by that instance,
3153 : * the possible or definite source accesses that last accessed the
3154 : * element accessed by the sink access before this sink access
3155 : * in the sense that there is no intermediate definite source access.
3156 : *
3157 : * The must_no_source and may_no_source elements of the result
3158 : * are subsets of access->sink. The elements must_dep and may_dep
3159 : * map domain elements of access->{may,must)_source to
3160 : * domain elements of access->sink.
3161 : *
3162 : * If any kills have been specified, then they are treated as
3163 : * must-sources internally. Any dependence that purely derives
3164 : * from an original kill is removed from the output.
3165 : *
3166 : * We check whether the schedule is available as a schedule tree
3167 : * or a schedule map and call the corresponding function to perform
3168 : * the analysis.
3169 : */
3170 0 : __isl_give isl_union_flow *isl_union_access_info_compute_flow(
3171 : __isl_take isl_union_access_info *access)
3172 : {
3173 : isl_bool has_kill;
3174 0 : isl_union_map *must = NULL, *may = NULL;
3175 : isl_union_flow *flow;
3176 :
3177 0 : has_kill = isl_union_access_has_kill(access);
3178 0 : if (has_kill < 0)
3179 0 : goto error;
3180 0 : if (has_kill) {
3181 0 : must = isl_union_access_info_get_must_source(access);
3182 0 : may = isl_union_access_info_get_may_source(access);
3183 : }
3184 0 : access = isl_union_access_info_add_kill_to_must_source(access);
3185 0 : access = isl_union_access_info_normalize(access);
3186 0 : if (!access)
3187 0 : goto error;
3188 0 : if (access->schedule)
3189 0 : flow = compute_flow_schedule(access);
3190 : else
3191 0 : flow = compute_flow_union_map(access);
3192 0 : if (has_kill)
3193 0 : flow = isl_union_flow_drop_kill_source(flow, must, may);
3194 0 : return flow;
3195 : error:
3196 0 : isl_union_access_info_free(access);
3197 0 : isl_union_map_free(must);
3198 0 : isl_union_map_free(may);
3199 0 : return NULL;
3200 : }
3201 :
3202 : /* Print the information contained in "flow" to "p".
3203 : * The information is printed as a YAML document.
3204 : */
3205 0 : __isl_give isl_printer *isl_printer_print_union_flow(
3206 : __isl_take isl_printer *p, __isl_keep isl_union_flow *flow)
3207 : {
3208 : isl_union_map *umap;
3209 :
3210 0 : if (!flow)
3211 0 : return isl_printer_free(p);
3212 :
3213 0 : p = isl_printer_yaml_start_mapping(p);
3214 0 : umap = isl_union_flow_get_full_must_dependence(flow);
3215 0 : p = print_union_map_field(p, "must_dependence", umap);
3216 0 : isl_union_map_free(umap);
3217 0 : umap = isl_union_flow_get_full_may_dependence(flow);
3218 0 : p = print_union_map_field(p, "may_dependence", umap);
3219 0 : isl_union_map_free(umap);
3220 0 : p = print_union_map_field(p, "must_no_source", flow->must_no_source);
3221 0 : umap = isl_union_flow_get_may_no_source(flow);
3222 0 : p = print_union_map_field(p, "may_no_source", umap);
3223 0 : isl_union_map_free(umap);
3224 0 : p = isl_printer_yaml_end_mapping(p);
3225 :
3226 0 : return p;
3227 : }
3228 :
3229 : /* Return a string representation of the information in "flow".
3230 : * The information is printed in flow format.
3231 : */
3232 0 : __isl_give char *isl_union_flow_to_str(__isl_keep isl_union_flow *flow)
3233 : {
3234 : isl_printer *p;
3235 : char *s;
3236 :
3237 0 : if (!flow)
3238 0 : return NULL;
3239 :
3240 0 : p = isl_printer_to_str(isl_union_flow_get_ctx(flow));
3241 0 : p = isl_printer_set_yaml_style(p, ISL_YAML_STYLE_FLOW);
3242 0 : p = isl_printer_print_union_flow(p, flow);
3243 0 : s = isl_printer_get_str(p);
3244 0 : isl_printer_free(p);
3245 :
3246 0 : return s;
3247 : }
3248 :
3249 : /* Given a collection of "sink" and "source" accesses,
3250 : * compute for each iteration of a sink access
3251 : * and for each element accessed by that iteration,
3252 : * the source access in the list that last accessed the
3253 : * element accessed by the sink access before this sink access.
3254 : * Each access is given as a map from the loop iterators
3255 : * to the array indices.
3256 : * The result is a relations between source and sink
3257 : * iterations and a subset of the domain of the sink accesses,
3258 : * corresponding to those iterations that access an element
3259 : * not previously accessed.
3260 : *
3261 : * We collect the inputs in an isl_union_access_info object,
3262 : * call isl_union_access_info_compute_flow and extract
3263 : * the outputs from the result.
3264 : */
3265 0 : int isl_union_map_compute_flow(__isl_take isl_union_map *sink,
3266 : __isl_take isl_union_map *must_source,
3267 : __isl_take isl_union_map *may_source,
3268 : __isl_take isl_union_map *schedule,
3269 : __isl_give isl_union_map **must_dep, __isl_give isl_union_map **may_dep,
3270 : __isl_give isl_union_map **must_no_source,
3271 : __isl_give isl_union_map **may_no_source)
3272 : {
3273 : isl_union_access_info *access;
3274 : isl_union_flow *flow;
3275 :
3276 0 : access = isl_union_access_info_from_sink(sink);
3277 0 : access = isl_union_access_info_set_must_source(access, must_source);
3278 0 : access = isl_union_access_info_set_may_source(access, may_source);
3279 0 : access = isl_union_access_info_set_schedule_map(access, schedule);
3280 0 : flow = isl_union_access_info_compute_flow(access);
3281 :
3282 0 : if (must_dep)
3283 0 : *must_dep = isl_union_flow_get_must_dependence(flow);
3284 0 : if (may_dep)
3285 0 : *may_dep = isl_union_flow_get_non_must_dependence(flow);
3286 0 : if (must_no_source)
3287 0 : *must_no_source = isl_union_flow_get_must_no_source(flow);
3288 0 : if (may_no_source)
3289 0 : *may_no_source = isl_union_flow_get_non_must_no_source(flow);
3290 :
3291 0 : isl_union_flow_free(flow);
3292 :
3293 0 : if ((must_dep && !*must_dep) || (may_dep && !*may_dep) ||
3294 0 : (must_no_source && !*must_no_source) ||
3295 0 : (may_no_source && !*may_no_source))
3296 : goto error;
3297 :
3298 0 : return 0;
3299 : error:
3300 0 : if (must_dep)
3301 0 : *must_dep = isl_union_map_free(*must_dep);
3302 0 : if (may_dep)
3303 0 : *may_dep = isl_union_map_free(*may_dep);
3304 0 : if (must_no_source)
3305 0 : *must_no_source = isl_union_map_free(*must_no_source);
3306 0 : if (may_no_source)
3307 0 : *may_no_source = isl_union_map_free(*may_no_source);
3308 0 : return -1;
3309 : }
|
