Coverage Report

Created: 2018-04-23 18:20

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_flow.c
Line
Count
Source (jump to first uncovered line)
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
static __isl_give isl_restriction *isl_restriction_alloc(
47
  __isl_take isl_map *source_map, enum isl_restriction_type type)
48
0
{
49
0
  isl_ctx *ctx;
50
0
  isl_restriction *restr;
51
0
52
0
  if (!source_map)
53
0
    return NULL;
54
0
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
0
60
0
  restr->type = type;
61
0
62
0
  isl_map_free(source_map);
63
0
  return restr;
64
0
error:
65
0
  isl_map_free(source_map);
66
0
  return NULL;
67
0
}
68
69
/* Create a restriction that doesn't restrict anything.
70
 */
71
__isl_give isl_restriction *isl_restriction_none(__isl_take isl_map *source_map)
72
0
{
73
0
  return isl_restriction_alloc(source_map, isl_restriction_type_none);
74
0
}
75
76
/* Create a restriction that removes everything.
77
 */
78
__isl_give isl_restriction *isl_restriction_empty(
79
  __isl_take isl_map *source_map)
80
0
{
81
0
  return isl_restriction_alloc(source_map, isl_restriction_type_empty);
82
0
}
83
84
/* Create a restriction on the input of the maximization problem
85
 * based on the given source and sink restrictions.
86
 */
87
__isl_give isl_restriction *isl_restriction_input(
88
  __isl_take isl_set *source_restr, __isl_take isl_set *sink_restr)
89
0
{
90
0
  isl_ctx *ctx;
91
0
  isl_restriction *restr;
92
0
93
0
  if (!source_restr || !sink_restr)
94
0
    goto error;
95
0
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
0
101
0
  restr->type = isl_restriction_type_input;
102
0
  restr->source = source_restr;
103
0
  restr->sink = sink_restr;
104
0
105
0
  return restr;
106
0
error:
107
0
  isl_set_free(source_restr);
108
0
  isl_set_free(sink_restr);
109
0
  return NULL;
110
0
}
111
112
/* Create a restriction on the output of the maximization problem
113
 * based on the given source restriction.
114
 */
115
__isl_give isl_restriction *isl_restriction_output(
116
  __isl_take isl_set *source_restr)
117
0
{
118
0
  isl_ctx *ctx;
119
0
  isl_restriction *restr;
120
0
121
0
  if (!source_restr)
122
0
    return NULL;
123
0
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
0
129
0
  restr->type = isl_restriction_type_output;
130
0
  restr->source = source_restr;
131
0
132
0
  return restr;
133
0
error:
134
0
  isl_set_free(source_restr);
135
0
  return NULL;
136
0
}
137
138
__isl_null isl_restriction *isl_restriction_free(
139
  __isl_take isl_restriction *restr)
140
0
{
141
0
  if (!restr)
142
0
    return NULL;
143
0
144
0
  isl_set_free(restr->source);
145
0
  isl_set_free(restr->sink);
146
0
  free(restr);
147
0
  return NULL;
148
0
}
149
150
isl_ctx *isl_restriction_get_ctx(__isl_keep isl_restriction *restr)
151
0
{
152
0
  return restr ? isl_set_get_ctx(restr->source) : NULL;
153
0
}
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
__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
4.01k
{
217
4.01k
  isl_ctx *ctx;
218
4.01k
  struct isl_access_info *acc;
219
4.01k
220
4.01k
  if (!sink)
221
0
    return NULL;
222
4.01k
223
4.01k
  ctx = isl_map_get_ctx(sink);
224
4.01k
  isl_assert(ctx, max_source >= 0, goto error);
225
4.01k
226
4.01k
  acc = isl_calloc(ctx, struct isl_access_info,
227
4.01k
      sizeof(struct isl_access_info) +
228
4.01k
      (max_source - 1) * sizeof(struct isl_labeled_map));
229
4.01k
  if (!acc)
230
0
    goto error;
231
4.01k
232
4.01k
  acc->sink.map = sink;
233
4.01k
  acc->sink.data = sink_user;
234
4.01k
  acc->level_before = fn;
235
4.01k
  acc->max_source = max_source;
236
4.01k
  acc->n_must = 0;
237
4.01k
  acc->n_may = 0;
238
4.01k
239
4.01k
  return acc;
240
0
error:
241
0
  isl_map_free(sink);
242
0
  return NULL;
243
4.01k
}
244
245
/* Free the given isl_access_info structure.
246
 */
247
__isl_null isl_access_info *isl_access_info_free(
248
  __isl_take isl_access_info *acc)
249
4.01k
{
250
4.01k
  int i;
251
4.01k
252
4.01k
  if (!acc)
253
0
    return NULL;
254
4.01k
  isl_map_free(acc->domain_map);
255
4.01k
  isl_map_free(acc->sink.map);
256
10.9k
  for (i = 0; i < acc->n_must + acc->n_may; 
++i6.90k
)
257
6.90k
    isl_map_free(acc->source[i].map);
258
4.01k
  free(acc);
259
4.01k
  return NULL;
260
4.01k
}
261
262
isl_ctx *isl_access_info_get_ctx(__isl_keep isl_access_info *acc)
263
0
{
264
0
  return acc ? isl_map_get_ctx(acc->sink.map) : NULL;
265
0
}
266
267
__isl_give isl_access_info *isl_access_info_set_restrict(
268
  __isl_take isl_access_info *acc, isl_access_restrict fn, void *user)
269
0
{
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
0
}
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
__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
6.90k
{
287
6.90k
  isl_ctx *ctx;
288
6.90k
289
6.90k
  if (!acc)
290
0
    goto error;
291
6.90k
  ctx = isl_map_get_ctx(acc->sink.map);
292
6.90k
  isl_assert(ctx, acc->n_must + acc->n_may < acc->max_source, goto error);
293
6.90k
  
294
6.90k
  if (must) {
295
6.19k
    if (acc->n_may)
296
165
      acc->source[acc->n_must + acc->n_may] =
297
165
        acc->source[acc->n_must];
298
6.19k
    acc->source[acc->n_must].map = source;
299
6.19k
    acc->source[acc->n_must].data = source_user;
300
6.19k
    acc->source[acc->n_must].must = 1;
301
6.19k
    acc->n_must++;
302
6.19k
  } else {
303
703
    acc->source[acc->n_must + acc->n_may].map = source;
304
703
    acc->source[acc->n_must + acc->n_may].data = source_user;
305
703
    acc->source[acc->n_must + acc->n_may].must = 0;
306
703
    acc->n_may++;
307
703
  }
308
6.90k
309
6.90k
  return acc;
310
0
error:
311
0
  isl_map_free(source);
312
0
  isl_access_info_free(acc);
313
0
  return NULL;
314
6.90k
}
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
static int access_sort_cmp(const void *p1, const void *p2, void *user)
340
3.76k
{
341
3.76k
  struct access_sort_info *sort_info = user;
342
3.76k
  isl_access_info *acc = sort_info->access_info;
343
3.76k
344
3.76k
  if (sort_info->error)
345
0
    return 0;
346
3.76k
347
3.76k
  const struct isl_labeled_map *i1, *i2;
348
3.76k
  int level1, level2;
349
3.76k
  uint32_t h1, h2;
350
3.76k
  i1 = (const struct isl_labeled_map *) p1;
351
3.76k
  i2 = (const struct isl_labeled_map *) p2;
352
3.76k
353
3.76k
  level1 = acc->level_before(i1->data, i2->data);
354
3.76k
  if (level1 < 0)
355
0
    goto error;
356
3.76k
  if (level1 % 2)
357
3.71k
    return -1;
358
51
359
51
  level2 = acc->level_before(i2->data, i1->data);
360
51
  if (level2 < 0)
361
0
    goto error;
362
51
  if (level2 % 2)
363
50
    return 1;
364
1
365
1
  h1 = isl_map_get_hash(i1->map);
366
1
  h2 = isl_map_get_hash(i2->map);
367
1
  return h1 > h2 ? 1 : 
h1 < h2 0
?
-10
:
00
;
368
0
error:
369
0
  sort_info->error = 1;
370
0
  return 0;
371
1
}
372
373
/* Sort the must source accesses in their textual order.
374
 */
375
static __isl_give isl_access_info *isl_access_info_sort_sources(
376
  __isl_take isl_access_info *acc)
377
3.70k
{
378
3.70k
  struct access_sort_info sort_info;
379
3.70k
380
3.70k
  sort_info.access_info = acc;
381
3.70k
  sort_info.error = 0;
382
3.70k
383
3.70k
  if (!acc)
384
0
    return NULL;
385
3.70k
  if (acc->n_must <= 1)
386
2.41k
    return acc;
387
1.29k
388
1.29k
  if (isl_sort(acc->source, acc->n_must, sizeof(struct isl_labeled_map),
389
1.29k
        access_sort_cmp, &sort_info) < 0)
390
0
    return isl_access_info_free(acc);
391
1.29k
  if (sort_info.error)
392
0
    return isl_access_info_free(acc);
393
1.29k
394
1.29k
  return acc;
395
1.29k
}
396
397
/* Align the parameters of the two spaces if needed and then call
398
 * isl_space_join.
399
 */
400
static __isl_give isl_space *space_align_and_join(__isl_take isl_space *left,
401
  __isl_take isl_space *right)
402
7.15k
{
403
7.15k
  isl_bool equal_params;
404
7.15k
405
7.15k
  equal_params = isl_space_has_equal_params(left, right);
406
7.15k
  if (equal_params < 0)
407
0
    goto error;
408
7.15k
  if (equal_params)
409
7.15k
    return isl_space_join(left, right);
410
0
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
0
error:
415
0
  isl_space_free(left);
416
0
  isl_space_free(right);
417
0
  return NULL;
418
0
}
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
static __isl_give isl_flow *isl_flow_alloc(__isl_keep isl_access_info *acc)
431
4.01k
{
432
4.01k
  int i, n;
433
4.01k
  struct isl_ctx *ctx;
434
4.01k
  struct isl_flow *dep;
435
4.01k
436
4.01k
  if (!acc)
437
0
    return NULL;
438
4.01k
439
4.01k
  ctx = isl_map_get_ctx(acc->sink.map);
440
4.01k
  dep = isl_calloc_type(ctx, struct isl_flow);
441
4.01k
  if (!dep)
442
0
    return NULL;
443
4.01k
444
4.01k
  n = 2 * acc->n_must + acc->n_may;
445
4.01k
  dep->dep = isl_calloc_array(ctx, struct isl_labeled_map, n);
446
4.01k
  if (n && 
!dep->dep3.77k
)
447
0
    goto error;
448
4.01k
449
4.01k
  dep->n_source = n;
450
10.2k
  for (i = 0; i < acc->n_must; 
++i6.19k
) {
451
6.19k
    isl_space *dim;
452
6.19k
    dim = space_align_and_join(
453
6.19k
      isl_map_get_space(acc->source[i].map),
454
6.19k
      isl_space_reverse(isl_map_get_space(acc->sink.map)));
455
6.19k
    dep->dep[2 * i].map = isl_map_empty(dim);
456
6.19k
    dep->dep[2 * i + 1].map = isl_map_copy(dep->dep[2 * i].map);
457
6.19k
    dep->dep[2 * i].data = acc->source[i].data;
458
6.19k
    dep->dep[2 * i + 1].data = acc->source[i].data;
459
6.19k
    dep->dep[2 * i].must = 1;
460
6.19k
    dep->dep[2 * i + 1].must = 0;
461
6.19k
    if (!dep->dep[2 * i].map || !dep->dep[2 * i + 1].map)
462
0
      goto error;
463
6.19k
  }
464
4.72k
  
for (i = acc->n_must; 4.01k
i < acc->n_must + acc->n_may;
++i703
) {
465
703
    isl_space *dim;
466
703
    dim = space_align_and_join(
467
703
      isl_map_get_space(acc->source[i].map),
468
703
      isl_space_reverse(isl_map_get_space(acc->sink.map)));
469
703
    dep->dep[acc->n_must + i].map = isl_map_empty(dim);
470
703
    dep->dep[acc->n_must + i].data = acc->source[i].data;
471
703
    dep->dep[acc->n_must + i].must = 0;
472
703
    if (!dep->dep[acc->n_must + i].map)
473
0
      goto error;
474
703
  }
475
4.01k
476
4.01k
  return dep;
477
0
error:
478
0
  isl_flow_free(dep);
479
0
  return NULL;
480
4.01k
}
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
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
6
{
493
6
  int i;
494
6
495
6
  if (!deps)
496
0
    return isl_stat_error;
497
6
498
21
  
for (i = 0; 6
i < deps->n_source;
++i15
) {
499
15
    if (isl_map_plain_is_empty(deps->dep[i].map))
500
3
      continue;
501
12
    if (fn(isl_map_copy(deps->dep[i].map), deps->dep[i].must,
502
12
        deps->dep[i].data, user) < 0)
503
0
      return isl_stat_error;
504
12
  }
505
6
506
6
  return isl_stat_ok;
507
6
}
508
509
/* Return a copy of the subset of the sink for which no source could be found.
510
 */
511
__isl_give isl_map *isl_flow_get_no_source(__isl_keep isl_flow *deps, int must)
512
8.02k
{
513
8.02k
  if (!deps)
514
0
    return NULL;
515
8.02k
  
516
8.02k
  if (must)
517
4.01k
    return isl_set_unwrap(isl_set_copy(deps->must_no_source));
518
4.01k
  else
519
4.01k
    return isl_set_unwrap(isl_set_copy(deps->may_no_source));
520
8.02k
}
521
522
void isl_flow_free(__isl_take isl_flow *deps)
523
4.01k
{
524
4.01k
  int i;
525
4.01k
526
4.01k
  if (!deps)
527
0
    return;
528
4.01k
  isl_set_free(deps->must_no_source);
529
4.01k
  isl_set_free(deps->may_no_source);
530
4.01k
  if (deps->dep) {
531
17.1k
    for (i = 0; i < deps->n_source; 
++i13.0k
)
532
13.0k
      isl_map_free(deps->dep[i].map);
533
4.01k
    free(deps->dep);
534
4.01k
  }
535
4.01k
  free(deps);
536
4.01k
}
537
538
isl_ctx *isl_flow_get_ctx(__isl_keep isl_flow *deps)
539
0
{
540
0
  return deps ? isl_set_get_ctx(deps->must_no_source) : NULL;
541
0
}
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
static __isl_give isl_map *after_at_level(__isl_take isl_space *dim, int level)
554
16.4k
{
555
16.4k
  struct isl_basic_map *bmap;
556
16.4k
557
16.4k
  if (level % 2)
558
2.77k
    bmap = isl_basic_map_equal(dim, level/2);
559
13.6k
  else
560
13.6k
    bmap = isl_basic_map_more_at(dim, level/2 - 1);
561
16.4k
562
16.4k
  return isl_map_from_basic_map(bmap);
563
16.4k
}
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
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
12.0k
{
581
12.0k
  isl_map *source_map;
582
12.0k
  isl_restriction *restr;
583
12.0k
  isl_set *sink_domain;
584
12.0k
  isl_set *sink_restr;
585
12.0k
  isl_map *res;
586
12.0k
587
12.0k
  if (!acc->restrict_fn)
588
12.0k
    return isl_map_partial_lexmax(dep, sink, empty);
589
0
590
0
  source_map = isl_map_copy(dep);
591
0
  source_map = isl_map_apply_domain(source_map,
592
0
              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
0
        acc->source[source].data, acc->restrict_user);
597
0
  isl_set_free(sink_domain);
598
0
  isl_map_free(source_map);
599
0
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
0
        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
0
  }
613
0
614
0
  res = isl_map_partial_lexmax(dep, sink, empty);
615
0
616
0
  if (restr->type == isl_restriction_type_output)
617
0
    res = isl_map_intersect_range(res, isl_set_copy(restr->source));
618
0
619
0
  isl_restriction_free(restr);
620
0
  return res;
621
0
error:
622
0
  isl_map_free(dep);
623
0
  isl_set_free(sink);
624
0
  *empty = NULL;
625
0
  return NULL;
626
0
}
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
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
11.7k
{
637
11.7k
  struct isl_map *read_map;
638
11.7k
  struct isl_map *write_map;
639
11.7k
  struct isl_map *dep_map;
640
11.7k
  struct isl_map *after;
641
11.7k
  struct isl_map *result;
642
11.7k
643
11.7k
  read_map = isl_map_copy(acc->sink.map);
644
11.7k
  write_map = isl_map_copy(acc->source[j].map);
645
11.7k
  write_map = isl_map_reverse(write_map);
646
11.7k
  dep_map = isl_map_apply_range(read_map, write_map);
647
11.7k
  after = after_at_level(isl_map_get_space(dep_map), level);
648
11.7k
  dep_map = isl_map_intersect(dep_map, after);
649
11.7k
  result = restricted_partial_lexmax(acc, dep_map, j, set_C, empty);
650
11.7k
  result = isl_map_reverse(result);
651
11.7k
652
11.7k
  return result;
653
11.7k
}
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
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
258
{
667
258
  isl_space *dim;
668
258
  struct isl_set *set_C;
669
258
  struct isl_map *read_map;
670
258
  struct isl_map *write_map;
671
258
  struct isl_map *dep_map;
672
258
  struct isl_map *after_write;
673
258
  struct isl_map *before_read;
674
258
  struct isl_map *result;
675
258
676
258
  set_C = isl_map_range(isl_map_copy(old_map));
677
258
  read_map = isl_map_copy(acc->sink.map);
678
258
  write_map = isl_map_copy(acc->source[k].map);
679
258
680
258
  write_map = isl_map_reverse(write_map);
681
258
  dep_map = isl_map_apply_range(read_map, write_map);
682
258
  dim = space_align_and_join(isl_map_get_space(acc->source[k].map),
683
258
        isl_space_reverse(isl_map_get_space(acc->source[j].map)));
684
258
  after_write = after_at_level(dim, after_level);
685
258
  after_write = isl_map_apply_range(after_write, old_map);
686
258
  after_write = isl_map_reverse(after_write);
687
258
  dep_map = isl_map_intersect(dep_map, after_write);
688
258
  before_read = after_at_level(isl_map_get_space(dep_map), before_level);
689
258
  dep_map = isl_map_intersect(dep_map, before_read);
690
258
  result = restricted_partial_lexmax(acc, dep_map, k, set_C, empty);
691
258
  result = isl_map_reverse(result);
692
258
693
258
  return result;
694
258
}
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
static int can_precede_at_level(int shared_level, int target_level)
705
67.2k
{
706
67.2k
  if (shared_level < target_level)
707
53.0k
    return 0;
708
14.2k
  if ((target_level % 2) && 
shared_level > target_level7.77k
)
709
5.58k
    return 0;
710
8.63k
  return 1;
711
8.63k
}
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
static isl_stat intermediate_sources(__isl_keep isl_access_info *acc,
729
  struct isl_map **temp_rel, int j, int sink_level)
730
12.5k
{
731
12.5k
  int k, level;
732
12.5k
  int depth = 2 * isl_map_dim(acc->source[j].map, isl_dim_in) + 1;
733
12.5k
734
12.5k
  if (isl_map_plain_is_empty(temp_rel[j]))
735
10.0k
    return isl_stat_ok;
736
2.46k
737
4.10k
  
for (k = j - 1; 2.46k
k >= 0;
--k1.64k
) {
738
1.64k
    int plevel, plevel2;
739
1.64k
    plevel = acc->level_before(acc->source[k].data, acc->sink.data);
740
1.64k
    if (plevel < 0)
741
0
      return isl_stat_error;
742
1.64k
    if (!can_precede_at_level(plevel, sink_level))
743
955
      continue;
744
686
745
686
    plevel2 = acc->level_before(acc->source[j].data,
746
686
            acc->source[k].data);
747
686
    if (plevel2 < 0)
748
0
      return isl_stat_error;
749
686
750
6.61k
    
for (level = sink_level; 686
level <= depth;
++level5.92k
) {
751
5.92k
      struct isl_map *T;
752
5.92k
      struct isl_set *trest;
753
5.92k
      struct isl_map *copy;
754
5.92k
755
5.92k
      if (!can_precede_at_level(plevel2, level))
756
5.66k
        continue;
757
258
758
258
      copy = isl_map_copy(temp_rel[j]);
759
258
      T = last_later_source(acc, copy, j, sink_level, k,
760
258
                level, &trest);
761
258
      if (isl_map_plain_is_empty(T)) {
762
230
        isl_set_free(trest);
763
230
        isl_map_free(T);
764
230
        continue;
765
230
      }
766
28
      temp_rel[j] = isl_map_intersect_range(temp_rel[j], trest);
767
28
      temp_rel[k] = isl_map_union_disjoint(temp_rel[k], T);
768
28
    }
769
686
  }
770
2.46k
771
2.46k
  return isl_stat_ok;
772
2.46k
}
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
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
1.50k
{
780
1.50k
  isl_map *read_map;
781
1.50k
  isl_map *write_map;
782
1.50k
  isl_map *dep_map;
783
1.50k
  isl_map *after;
784
1.50k
785
1.50k
  read_map = isl_map_copy(acc->sink.map);
786
1.50k
  read_map = isl_map_intersect_domain(read_map, set_C);
787
1.50k
  write_map = isl_map_copy(acc->source[acc->n_must + j].map);
788
1.50k
  write_map = isl_map_reverse(write_map);
789
1.50k
  dep_map = isl_map_apply_range(read_map, write_map);
790
1.50k
  after = after_at_level(isl_map_get_space(dep_map), level);
791
1.50k
  dep_map = isl_map_intersect(dep_map, after);
792
1.50k
793
1.50k
  return isl_map_reverse(dep_map);
794
1.50k
}
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
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
1.32k
{
806
1.32k
  isl_space *dim;
807
1.32k
  isl_set *set_C;
808
1.32k
  isl_map *read_map;
809
1.32k
  isl_map *write_map;
810
1.32k
  isl_map *dep_map;
811
1.32k
  isl_map *after_write;
812
1.32k
  isl_map *before_read;
813
1.32k
814
1.32k
  set_C = isl_map_range(isl_map_copy(old_map));
815
1.32k
  read_map = isl_map_copy(acc->sink.map);
816
1.32k
  read_map = isl_map_intersect_domain(read_map, set_C);
817
1.32k
  write_map = isl_map_copy(acc->source[acc->n_must + j].map);
818
1.32k
819
1.32k
  write_map = isl_map_reverse(write_map);
820
1.32k
  dep_map = isl_map_apply_range(read_map, write_map);
821
1.32k
  dim = isl_space_join(isl_map_get_space(acc->source[acc->n_must + j].map),
822
1.32k
        isl_space_reverse(isl_map_get_space(acc->source[k].map)));
823
1.32k
  after_write = after_at_level(dim, after_level);
824
1.32k
  after_write = isl_map_apply_range(after_write, old_map);
825
1.32k
  after_write = isl_map_reverse(after_write);
826
1.32k
  dep_map = isl_map_intersect(dep_map, after_write);
827
1.32k
  before_read = after_at_level(isl_map_get_space(dep_map), before_level);
828
1.32k
  dep_map = isl_map_intersect(dep_map, before_read);
829
1.32k
  return isl_map_reverse(dep_map);
830
1.32k
}
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
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
750
{
844
750
  int k, level;
845
750
  int depth = 2 * isl_map_dim(acc->source[acc->n_must + j].map,
846
750
          isl_dim_in) + 1;
847
750
848
1.71k
  for (k = 0; k < acc->n_must; 
++k968
) {
849
968
    int plevel;
850
968
851
968
    if (isl_map_plain_is_empty(may_rel[k]) &&
852
968
        
isl_map_plain_is_empty(must_rel[k])887
)
853
596
      continue;
854
372
855
372
    plevel = acc->level_before(acc->source[k].data,
856
372
          acc->source[acc->n_must + j].data);
857
372
    if (plevel < 0)
858
0
      return isl_map_free(map);
859
372
860
2.41k
    
for (level = sink_level; 372
level <= depth;
++level2.04k
) {
861
2.04k
      isl_map *T;
862
2.04k
      isl_map *copy;
863
2.04k
      isl_set *ran;
864
2.04k
865
2.04k
      if (!can_precede_at_level(plevel, level))
866
1.38k
        continue;
867
664
868
664
      copy = isl_map_copy(may_rel[k]);
869
664
      T = all_later_sources(acc, copy, j, sink_level, k, level);
870
664
      map = isl_map_union(map, T);
871
664
872
664
      copy = isl_map_copy(must_rel[k]);
873
664
      T = all_later_sources(acc, copy, j, sink_level, k, level);
874
664
      ran = isl_map_range(isl_map_copy(T));
875
664
      map = isl_map_union(map, T);
876
664
      may_rel[k] = isl_map_union_disjoint(may_rel[k],
877
664
          isl_map_intersect_range(isl_map_copy(must_rel[k]),
878
664
                isl_set_copy(ran)));
879
664
      T = isl_map_from_domain_and_range(
880
664
          isl_set_universe(
881
664
        isl_space_domain(isl_map_get_space(must_rel[k]))),
882
664
          ran);
883
664
      must_rel[k] = isl_map_subtract(must_rel[k], T);
884
664
    }
885
372
  }
886
750
887
750
  return map;
888
750
}
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
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
50
{
913
50
  isl_space *space;
914
50
  isl_set *set_C;
915
50
  isl_map *read_map;
916
50
  isl_map *write_map;
917
50
  isl_map *dep_map;
918
50
  isl_map *equal;
919
50
  isl_map *map;
920
50
921
50
  if (depth < 0)
922
0
    return NULL;
923
50
924
50
  set_C = isl_map_range(isl_map_copy(old_map));
925
50
  read_map = isl_map_copy(acc->sink.map);
926
50
  read_map = isl_map_intersect_domain(read_map, set_C);
927
50
  write_map = isl_map_copy(acc->source[pos].map);
928
50
  dep_map = isl_map_domain_product(write_map, read_map);
929
50
  dep_map = isl_set_unwrap(isl_map_domain(dep_map));
930
50
  space = isl_space_join(isl_map_get_space(old_map),
931
50
        isl_space_reverse(isl_map_get_space(dep_map)));
932
50
  equal = isl_map_from_basic_map(isl_basic_map_equal(space, depth));
933
50
  map = isl_map_range_product(equal, isl_map_copy(old_map));
934
50
  map = isl_map_uncurry(map);
935
50
  map = isl_map_intersect_domain_factor_range(map, dep_map);
936
50
937
50
  return map;
938
50
}
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
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
29.3k
{
979
29.3k
  int i, j;
980
29.3k
981
29.3k
  if (!acc->coscheduled)
982
30
    return flow;
983
82.0k
  
for (i = acc->n_must - 1; 29.3k
i >= 0;
--i52.7k
) {
984
52.7k
    isl_map *move;
985
52.7k
986
52.7k
    if (isl_map_plain_is_empty(must_rel[i]))
987
50.4k
      continue;
988
2.36k
    move = isl_map_empty(isl_map_get_space(must_rel[i]));
989
3.97k
    for (j = i - 1; j >= 0; 
--j1.61k
) {
990
1.61k
      int depth;
991
1.61k
      isl_map *map, *factor;
992
1.61k
993
1.61k
      if (!acc->coscheduled(acc->source[i].data,
994
1.61k
            acc->source[j].data))
995
1.61k
        continue;
996
0
      depth = acc->level_before(acc->source[i].data,
997
0
            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
0
    }
1004
2.75k
    for (j = 0; j < acc->n_may; 
++j389
) {
1005
389
      int depth, pos;
1006
389
      isl_map *map, *factor;
1007
389
1008
389
      pos = acc->n_must + j;
1009
389
      if (!acc->coscheduled(acc->source[i].data,
1010
389
            acc->source[pos].data))
1011
339
        continue;
1012
50
      depth = acc->level_before(acc->source[i].data,
1013
50
            acc->source[pos].data) / 2;
1014
50
      map = coscheduled_source(acc, must_rel[i], pos, depth);
1015
50
      factor = isl_map_domain_factor_range(isl_map_copy(map));
1016
50
      pos = 2 * acc->n_must + j;
1017
50
      flow->dep[pos].map = isl_map_union(flow->dep[pos].map,
1018
50
                  factor);
1019
50
      map = isl_map_domain_factor_domain(map);
1020
50
      move = isl_map_union(move, map);
1021
50
    }
1022
2.36k
    must_rel[i] = isl_map_subtract(must_rel[i], isl_map_copy(move));
1023
2.36k
    may_rel[i] = isl_map_union(may_rel[i], move);
1024
2.36k
  }
1025
29.3k
1026
29.3k
  return flow;
1027
29.3k
}
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
static __isl_give isl_flow *compute_mem_based_dependences(
1035
  __isl_keep isl_access_info *acc)
1036
310
{
1037
310
  int i;
1038
310
  isl_set *mustdo;
1039
310
  isl_set *maydo;
1040
310
  isl_flow *res;
1041
310
1042
310
  res = isl_flow_alloc(acc);
1043
310
  if (!res)
1044
0
    return NULL;
1045
310
1046
310
  mustdo = isl_map_domain(isl_map_copy(acc->sink.map));
1047
310
  maydo = isl_set_copy(mustdo);
1048
310
1049
393
  for (i = 0; i < acc->n_may; 
++i83
) {
1050
83
    int plevel;
1051
83
    int is_before;
1052
83
    isl_space *dim;
1053
83
    isl_map *before;
1054
83
    isl_map *dep;
1055
83
1056
83
    plevel = acc->level_before(acc->source[i].data, acc->sink.data);
1057
83
    if (plevel < 0)
1058
0
      goto error;
1059
83
1060
83
    is_before = plevel & 1;
1061
83
    plevel >>= 1;
1062
83
1063
83
    dim = isl_map_get_space(res->dep[i].map);
1064
83
    if (is_before)
1065
10
      before = isl_map_lex_le_first(dim, plevel);
1066
73
    else
1067
73
      before = isl_map_lex_lt_first(dim, plevel);
1068
83
    dep = isl_map_apply_range(isl_map_copy(acc->source[i].map),
1069
83
      isl_map_reverse(isl_map_copy(acc->sink.map)));
1070
83
    dep = isl_map_intersect(dep, before);
1071
83
    mustdo = isl_set_subtract(mustdo,
1072
83
              isl_map_range(isl_map_copy(dep)));
1073
83
    res->dep[i].map = isl_map_union(res->dep[i].map, dep);
1074
83
  }
1075
310
1076
310
  res->may_no_source = isl_set_subtract(maydo, isl_set_copy(mustdo));
1077
310
  res->must_no_source = mustdo;
1078
310
1079
310
  return res;
1080
0
error:
1081
0
  isl_set_free(mustdo);
1082
0
  isl_set_free(maydo);
1083
0
  isl_flow_free(res);
1084
0
  return NULL;
1085
310
}
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
static __isl_give isl_flow *compute_val_based_dependences(
1128
  __isl_keep isl_access_info *acc)
1129
3.70k
{
1130
3.70k
  isl_ctx *ctx;
1131
3.70k
  isl_flow *res;
1132
3.70k
  isl_set *mustdo = NULL;
1133
3.70k
  isl_set *maydo = NULL;
1134
3.70k
  int level, j;
1135
3.70k
  int depth;
1136
3.70k
  isl_map **must_rel = NULL;
1137
3.70k
  isl_map **may_rel = NULL;
1138
3.70k
1139
3.70k
  if (!acc)
1140
0
    return NULL;
1141
3.70k
1142
3.70k
  res = isl_flow_alloc(acc);
1143
3.70k
  if (!res)
1144
0
    goto error;
1145
3.70k
  ctx = isl_map_get_ctx(acc->sink.map);
1146
3.70k
1147
3.70k
  depth = 2 * isl_map_dim(acc->sink.map, isl_dim_in) + 1;
1148
3.70k
  mustdo = isl_map_domain(isl_map_copy(acc->sink.map));
1149
3.70k
  maydo = isl_set_empty(isl_set_get_space(mustdo));
1150
3.70k
  if (!mustdo || !maydo)
1151
0
    goto error;
1152
3.70k
  if (isl_set_plain_is_empty(mustdo))
1153
0
    goto done;
1154
3.70k
1155
3.70k
  must_rel = isl_calloc_array(ctx, struct isl_map *, acc->n_must);
1156
3.70k
  may_rel = isl_calloc_array(ctx, struct isl_map *, acc->n_must);
1157
3.70k
  if (!must_rel || !may_rel)
1158
0
    goto error;
1159
3.70k
1160
32.4k
  
for (level = depth; 3.70k
level >= 1;
--level28.7k
) {
1161
82.1k
    for (j = acc->n_must-1; j >=0; 
--j52.8k
) {
1162
52.8k
      isl_space *space;
1163
52.8k
      space = isl_map_get_space(res->dep[2 * j].map);
1164
52.8k
      must_rel[j] = isl_map_empty(space);
1165
52.8k
      may_rel[j] = isl_map_copy(must_rel[j]);
1166
52.8k
    }
1167
29.3k
1168
81.1k
    for (j = acc->n_must - 1; j >= 0; 
--j51.8k
) {
1169
52.4k
      struct isl_map *T;
1170
52.4k
      struct isl_set *rest;
1171
52.4k
      int plevel;
1172
52.4k
1173
52.4k
      plevel = acc->level_before(acc->source[j].data,
1174
52.4k
                 acc->sink.data);
1175
52.4k
      if (plevel < 0)
1176
0
        goto error;
1177
52.4k
      if (!can_precede_at_level(plevel, level))
1178
46.5k
        continue;
1179
5.89k
1180
5.89k
      T = last_source(acc, mustdo, j, level, &rest);
1181
5.89k
      must_rel[j] = isl_map_union_disjoint(must_rel[j], T);
1182
5.89k
      mustdo = rest;
1183
5.89k
1184
5.89k
      if (intermediate_sources(acc, must_rel, j, level) < 0)
1185
0
        goto error;
1186
5.89k
1187
5.89k
      T = last_source(acc, maydo, j, level, &rest);
1188
5.89k
      may_rel[j] = isl_map_union_disjoint(may_rel[j], T);
1189
5.89k
      maydo = rest;
1190
5.89k
1191
5.89k
      if (intermediate_sources(acc, may_rel, j, level) < 0)
1192
0
        goto error;
1193
5.89k
1194
5.89k
      if (isl_set_plain_is_empty(mustdo) &&
1195
5.89k
          
isl_set_plain_is_empty(maydo)664
)
1196
588
        break;
1197
5.89k
    }
1198
29.7k
    
for (j = j - 1; 29.3k
j >= 0;
--j388
) {
1199
388
      int plevel;
1200
388
1201
388
      plevel = acc->level_before(acc->source[j].data,
1202
388
                 acc->sink.data);
1203
388
      if (plevel < 0)
1204
0
        goto error;
1205
388
      if (!can_precede_at_level(plevel, level))
1206
11
        continue;
1207
377
1208
377
      if (intermediate_sources(acc, must_rel, j, level) < 0)
1209
0
        goto error;
1210
377
      if (intermediate_sources(acc, may_rel, j, level) < 0)
1211
0
        goto error;
1212
377
    }
1213
29.3k
1214
29.3k
    handle_coscheduled(acc, must_rel, may_rel, res);
1215
29.3k
1216
34.2k
    for (j = 0; j < acc->n_may; 
++j4.87k
) {
1217
4.87k
      int plevel;
1218
4.87k
      isl_map *T;
1219
4.87k
      isl_set *ran;
1220
4.87k
1221
4.87k
      plevel = acc->level_before(acc->source[acc->n_must + j].data,
1222
4.87k
                 acc->sink.data);
1223
4.87k
      if (plevel < 0)
1224
0
        goto error;
1225
4.87k
      if (!can_precede_at_level(plevel, level))
1226
4.12k
        continue;
1227
750
1228
750
      T = all_sources(acc, isl_set_copy(maydo), j, level);
1229
750
      res->dep[2 * acc->n_must + j].map =
1230
750
          isl_map_union(res->dep[2 * acc->n_must + j].map, T);
1231
750
      T = all_sources(acc, isl_set_copy(mustdo), j, level);
1232
750
      ran = isl_map_range(isl_map_copy(T));
1233
750
      res->dep[2 * acc->n_must + j].map =
1234
750
          isl_map_union(res->dep[2 * acc->n_must + j].map, T);
1235
750
      mustdo = isl_set_subtract(mustdo, isl_set_copy(ran));
1236
750
      maydo = isl_set_union_disjoint(maydo, ran);
1237
750
1238
750
      T = res->dep[2 * acc->n_must + j].map;
1239
750
      T = all_intermediate_sources(acc, T, must_rel, may_rel,
1240
750
              j, level);
1241
750
      res->dep[2 * acc->n_must + j].map = T;
1242
750
    }
1243
29.3k
1244
82.1k
    
for (j = acc->n_must - 1; 29.3k
j >= 0;
--j52.8k
) {
1245
52.8k
      res->dep[2 * j].map =
1246
52.8k
        isl_map_union_disjoint(res->dep[2 * j].map,
1247
52.8k
                   must_rel[j]);
1248
52.8k
      res->dep[2 * j + 1].map =
1249
52.8k
        isl_map_union_disjoint(res->dep[2 * j + 1].map,
1250
52.8k
                   may_rel[j]);
1251
52.8k
    }
1252
29.3k
1253
29.3k
    if (isl_set_plain_is_empty(mustdo) &&
1254
29.3k
        
isl_set_plain_is_empty(maydo)805
)
1255
588
      break;
1256
29.3k
  }
1257
3.70k
1258
3.70k
  free(must_rel);
1259
3.70k
  free(may_rel);
1260
3.70k
done:
1261
3.70k
  res->must_no_source = mustdo;
1262
3.70k
  res->may_no_source = maydo;
1263
3.70k
  return res;
1264
0
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
3.70k
}
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
static __isl_give isl_flow *access_info_compute_flow_core(
1297
  __isl_take isl_access_info *acc)
1298
4.01k
{
1299
4.01k
  struct isl_flow *res = NULL;
1300
4.01k
1301
4.01k
  if (!acc)
1302
0
    return NULL;
1303
4.01k
1304
4.01k
  acc->sink.map = isl_map_range_map(acc->sink.map);
1305
4.01k
  if (!acc->sink.map)
1306
0
    goto error;
1307
4.01k
1308
4.01k
  if (acc->n_must == 0)
1309
310
    res = compute_mem_based_dependences(acc);
1310
3.70k
  else {
1311
3.70k
    acc = isl_access_info_sort_sources(acc);
1312
3.70k
    res = compute_val_based_dependences(acc);
1313
3.70k
  }
1314
4.01k
  acc = isl_access_info_free(acc);
1315
4.01k
  if (!res)
1316
0
    return NULL;
1317
4.01k
  if (!res->must_no_source || !res->may_no_source)
1318
0
    goto error;
1319
4.01k
  return res;
1320
0
error:
1321
0
  isl_access_info_free(acc);
1322
0
  isl_flow_free(res);
1323
0
  return NULL;
1324
4.01k
}
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
__isl_give isl_flow *isl_access_info_compute_flow(__isl_take isl_access_info *acc)
1344
6
{
1345
6
  int j;
1346
6
  struct isl_flow *res;
1347
6
1348
6
  if (!acc)
1349
0
    return NULL;
1350
6
1351
6
  acc->domain_map = isl_map_domain_map(isl_map_copy(acc->sink.map));
1352
6
  res = access_info_compute_flow_core(acc);
1353
6
  if (!res)
1354
0
    return NULL;
1355
6
1356
21
  
for (j = 0; 6
j < res->n_source;
++j15
) {
1357
15
    res->dep[j].map = isl_map_range_factor_domain(res->dep[j].map);
1358
15
    if (!res->dep[j].map)
1359
0
      goto error;
1360
15
  }
1361
6
1362
6
  return res;
1363
0
error:
1364
0
  isl_flow_free(res);
1365
0
  return NULL;
1366
6
}
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
static void sched_info_free(__isl_take struct isl_sched_info *info)
1379
400
{
1380
400
  if (!info)
1381
0
    return;
1382
400
  isl_vec_free(info->cst);
1383
400
  free(info->is_cst);
1384
400
  free(info);
1385
400
}
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
static __isl_give struct isl_sched_info *sched_info_alloc(
1395
  __isl_keep isl_map *map)
1396
400
{
1397
400
  isl_ctx *ctx;
1398
400
  isl_space *dim;
1399
400
  struct isl_sched_info *info;
1400
400
  int i, n;
1401
400
1402
400
  if (!map)
1403
0
    return NULL;
1404
400
1405
400
  dim = isl_space_unwrap(isl_space_domain(isl_map_get_space(map)));
1406
400
  if (!dim)
1407
0
    return NULL;
1408
400
  n = isl_space_dim(dim, isl_dim_in);
1409
400
  isl_space_free(dim);
1410
400
1411
400
  ctx = isl_map_get_ctx(map);
1412
400
  info = isl_alloc_type(ctx, struct isl_sched_info);
1413
400
  if (!info)
1414
0
    return NULL;
1415
400
  info->is_cst = isl_alloc_array(ctx, int, n);
1416
400
  info->cst = isl_vec_alloc(ctx, n);
1417
400
  if (n && (!info->is_cst || !info->cst))
1418
0
    goto error;
1419
400
1420
1.68k
  
for (i = 0; 400
i < n;
++i1.28k
) {
1421
1.28k
    isl_val *v;
1422
1.28k
1423
1.28k
    v = isl_map_plain_get_val_if_fixed(map, isl_dim_in, i);
1424
1.28k
    if (!v)
1425
0
      goto error;
1426
1.28k
    info->is_cst[i] = !isl_val_is_nan(v);
1427
1.28k
    if (info->is_cst[i])
1428
797
      info->cst = isl_vec_set_element_val(info->cst, i, v);
1429
487
    else
1430
487
      isl_val_free(v);
1431
1.28k
  }
1432
400
1433
400
  return info;
1434
0
error:
1435
0
  sched_info_free(info);
1436
0
  return NULL;
1437
400
}
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
__isl_null isl_union_access_info *isl_union_access_info_free(
1482
  __isl_take isl_union_access_info *access)
1483
2.56k
{
1484
2.56k
  enum isl_access_type i;
1485
2.56k
1486
2.56k
  if (!access)
1487
90
    return NULL;
1488
2.47k
1489
12.3k
  
for (i = isl_access_sink; 2.47k
i < isl_access_end;
++i9.90k
)
1490
9.90k
    isl_union_map_free(access->access[i]);
1491
2.47k
  isl_schedule_free(access->schedule);
1492
2.47k
  isl_union_map_free(access->schedule_map);
1493
2.47k
  free(access);
1494
2.47k
1495
2.47k
  return NULL;
1496
2.47k
}
1497
1498
/* Return the isl_ctx to which "access" belongs.
1499
 */
1500
isl_ctx *isl_union_access_info_get_ctx(__isl_keep isl_union_access_info *access)
1501
2.39k
{
1502
2.39k
  if (!access)
1503
0
    return NULL;
1504
2.39k
  return isl_union_map_get_ctx(access->access[isl_access_sink]);
1505
2.39k
}
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
static __isl_give isl_union_access_info *isl_union_access_info_alloc(
1513
  isl_ctx *ctx)
1514
2.48k
{
1515
2.48k
  return isl_calloc_type(ctx, isl_union_access_info);
1516
2.48k
}
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
static __isl_give isl_union_access_info *isl_union_access_info_init(
1526
  __isl_take isl_union_access_info *info)
1527
2.47k
{
1528
2.47k
  isl_space *space;
1529
2.47k
  isl_union_map *empty;
1530
2.47k
  enum isl_access_type i;
1531
2.47k
1532
2.47k
  if (!info)
1533
0
    return NULL;
1534
2.47k
  if (!info->access[isl_access_sink])
1535
0
    return isl_union_access_info_free(info);
1536
2.47k
1537
2.47k
  space = isl_union_map_get_space(info->access[isl_access_sink]);
1538
2.47k
  empty = isl_union_map_empty(isl_space_copy(space));
1539
9.90k
  for (i = isl_access_sink + 1; i < isl_access_end; 
++i7.42k
)
1540
7.42k
    if (!info->access[i])
1541
7.42k
      info->access[i] = isl_union_map_copy(empty);
1542
2.47k
  isl_union_map_free(empty);
1543
2.47k
  if (!info->schedule && !info->schedule_map)
1544
2.47k
    info->schedule = isl_schedule_empty(isl_space_copy(space));
1545
2.47k
  isl_space_free(space);
1546
2.47k
1547
9.90k
  for (i = isl_access_sink + 1; i < isl_access_end; 
++i7.42k
)
1548
7.42k
    if (!info->access[i])
1549
0
      return isl_union_access_info_free(info);
1550
2.47k
  if (!info->schedule && 
!info->schedule_map0
)
1551
0
    return isl_union_access_info_free(info);
1552
2.47k
1553
2.47k
  return info;
1554
2.47k
}
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
__isl_give isl_union_access_info *isl_union_access_info_from_sink(
1560
  __isl_take isl_union_map *sink)
1561
2.49k
{
1562
2.49k
  isl_ctx *ctx;
1563
2.49k
  isl_union_access_info *access;
1564
2.49k
1565
2.49k
  if (!sink)
1566
18
    return NULL;
1567
2.48k
  ctx = isl_union_map_get_ctx(sink);
1568
2.48k
  access = isl_union_access_info_alloc(ctx);
1569
2.48k
  if (!access)
1570
6
    goto error;
1571
2.47k
  access->access[isl_access_sink] = sink;
1572
2.47k
  return isl_union_access_info_init(access);
1573
6
error:
1574
6
  isl_union_map_free(sink);
1575
6
  return NULL;
1576
2.47k
}
1577
1578
/* Replace the access relation of type "type" of "info" by "access".
1579
 */
1580
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
7.44k
{
1584
7.44k
  if (!info || 
!access7.40k
)
1585
42
    goto error;
1586
7.40k
1587
7.40k
  isl_union_map_free(info->access[type]);
1588
7.40k
  info->access[type] = access;
1589
7.40k
1590
7.40k
  return info;
1591
42
error:
1592
42
  isl_union_access_info_free(info);
1593
42
  isl_union_map_free(access);
1594
42
  return NULL;
1595
7.40k
}
1596
1597
/* Replace the definite source accesses of "access" by "must_source".
1598
 */
1599
__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
4.95k
{
1603
4.95k
  return isl_union_access_info_set(access, isl_access_must_source,
1604
4.95k
          must_source);
1605
4.95k
}
1606
1607
/* Replace the possible source accesses of "access" by "may_source".
1608
 */
1609
__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
2.49k
{
1613
2.49k
  return isl_union_access_info_set(access, isl_access_may_source,
1614
2.49k
          may_source);
1615
2.49k
}
1616
1617
/* Replace the kills of "info" by "kill".
1618
 */
1619
__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
0
{
1622
0
  return isl_union_access_info_set(info, isl_access_kill, kill);
1623
0
}
1624
1625
/* Return the access relation of type "type" of "info".
1626
 */
1627
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
4.95k
{
1630
4.95k
  if (!info)
1631
0
    return NULL;
1632
4.95k
  return isl_union_map_copy(info->access[type]);
1633
4.95k
}
1634
1635
/* Return the definite source accesses of "info".
1636
 */
1637
__isl_give isl_union_map *isl_union_access_info_get_must_source(
1638
  __isl_keep isl_union_access_info *info)
1639
2.47k
{
1640
2.47k
  return isl_union_access_info_get(info, isl_access_must_source);
1641
2.47k
}
1642
1643
/* Return the possible source accesses of "info".
1644
 */
1645
__isl_give isl_union_map *isl_union_access_info_get_may_source(
1646
  __isl_keep isl_union_access_info *info)
1647
0
{
1648
0
  return isl_union_access_info_get(info, isl_access_may_source);
1649
0
}
1650
1651
/* Return the kills of "info".
1652
 */
1653
__isl_give isl_union_map *isl_union_access_info_get_kill(
1654
  __isl_keep isl_union_access_info *info)
1655
2.47k
{
1656
2.47k
  return isl_union_access_info_get(info, isl_access_kill);
1657
2.47k
}
1658
1659
/* Does "info" specify any kills?
1660
 */
1661
static isl_bool isl_union_access_has_kill(
1662
  __isl_keep isl_union_access_info *info)
1663
2.49k
{
1664
2.49k
  isl_bool empty;
1665
2.49k
1666
2.49k
  if (!info)
1667
24
    return isl_bool_error;
1668
2.47k
  empty = isl_union_map_is_empty(info->access[isl_access_kill]);
1669
2.47k
  return isl_bool_not(empty);
1670
2.47k
}
1671
1672
/* Replace the schedule of "access" by "schedule".
1673
 * Also free the schedule_map in case it was set last.
1674
 */
1675
__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
2.41k
{
1679
2.41k
  if (!access || 
!schedule2.39k
)
1680
24
    goto error;
1681
2.39k
1682
2.39k
  access->schedule_map = isl_union_map_free(access->schedule_map);
1683
2.39k
  isl_schedule_free(access->schedule);
1684
2.39k
  access->schedule = schedule;
1685
2.39k
1686
2.39k
  return access;
1687
24
error:
1688
24
  isl_union_access_info_free(access);
1689
24
  isl_schedule_free(schedule);
1690
24
  return NULL;
1691
2.39k
}
1692
1693
/* Replace the schedule map of "access" by "schedule_map".
1694
 * Also free the schedule in case it was set last.
1695
 */
1696
__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
81
{
1700
81
  if (!access || !schedule_map)
1701
0
    goto error;
1702
81
1703
81
  isl_union_map_free(access->schedule_map);
1704
81
  access->schedule = isl_schedule_free(access->schedule);
1705
81
  access->schedule_map = schedule_map;
1706
81
1707
81
  return access;
1708
0
error:
1709
0
  isl_union_access_info_free(access);
1710
0
  isl_union_map_free(schedule_map);
1711
0
  return NULL;
1712
81
}
1713
1714
__isl_give isl_union_access_info *isl_union_access_info_copy(
1715
  __isl_keep isl_union_access_info *access)
1716
0
{
1717
0
  isl_union_access_info *copy;
1718
0
  enum isl_access_type i;
1719
0
1720
0
  if (!access)
1721
0
    return NULL;
1722
0
  copy = isl_union_access_info_from_sink(
1723
0
        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
0
          isl_union_map_copy(access->access[i]));
1727
0
  if (access->schedule)
1728
0
    copy = isl_union_access_info_set_schedule(copy,
1729
0
        isl_schedule_copy(access->schedule));
1730
0
  else
1731
0
    copy = isl_union_access_info_set_schedule_map(copy,
1732
0
        isl_union_map_copy(access->schedule_map));
1733
0
1734
0
  return copy;
1735
0
}
1736
1737
/* Print a key-value pair of a YAML mapping to "p",
1738
 * with key "name" and value "umap".
1739
 */
1740
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
0
{
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
0
1750
0
  return p;
1751
0
}
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
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
0
{
1790
0
  if (type != isl_access_sink) {
1791
0
    isl_bool empty;
1792
0
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
0
  }
1799
0
  return print_union_map_field(p, key_str[type], info->access[type]);
1800
0
}
1801
1802
/* Print the information contained in "access" to "p".
1803
 * The information is printed as a YAML document.
1804
 */
1805
__isl_give isl_printer *isl_printer_print_union_access_info(
1806
  __isl_take isl_printer *p, __isl_keep isl_union_access_info *access)
1807
0
{
1808
0
  enum isl_access_type i;
1809
0
1810
0
  if (!access)
1811
0
    return isl_printer_free(p);
1812
0
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
0
  } else {
1822
0
    p = print_union_map_field(p, key_str[isl_ai_key_schedule_map],
1823
0
            access->schedule_map);
1824
0
  }
1825
0
  p = isl_printer_yaml_end_mapping(p);
1826
0
1827
0
  return p;
1828
0
}
1829
1830
/* Return a string representation of the information in "access".
1831
 * The information is printed in flow format.
1832
 */
1833
__isl_give char *isl_union_access_info_to_str(
1834
  __isl_keep isl_union_access_info *access)
1835
0
{
1836
0
  isl_printer *p;
1837
0
  char *s;
1838
0
1839
0
  if (!access)
1840
0
    return NULL;
1841
0
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
0
1848
0
  return s;
1849
0
}
1850
1851
#undef KEY
1852
0
#define KEY enum isl_ai_key
1853
#undef KEY_ERROR
1854
0
#define KEY_ERROR isl_ai_key_error
1855
#undef KEY_END
1856
0
#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
__isl_give isl_union_access_info *isl_stream_read_union_access_info(
1873
  isl_stream *s)
1874
0
{
1875
0
  isl_ctx *ctx;
1876
0
  isl_union_access_info *info;
1877
0
  int more;
1878
0
  int sink_set = 0;
1879
0
  int schedule_set = 0;
1880
0
1881
0
  if (isl_stream_yaml_read_start_mapping(s))
1882
0
    return NULL;
1883
0
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
0
    enum isl_ai_key key;
1888
0
    isl_union_map *access, *schedule_map;
1889
0
    isl_schedule *schedule;
1890
0
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
0
    case isl_ai_key_end:
1896
0
    case isl_ai_key_error:
1897
0
      return isl_union_access_info_free(info);
1898
0
    case isl_ai_key_sink:
1899
0
      sink_set = 1;
1900
0
    case isl_ai_key_must_source:
1901
0
    case isl_ai_key_may_source:
1902
0
    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
0
    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
0
                schedule_map);
1913
0
      if (!info)
1914
0
        return NULL;
1915
0
      break;
1916
0
    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
0
                schedule);
1921
0
      if (!info)
1922
0
        return NULL;
1923
0
      break;
1924
0
    }
1925
0
  }
1926
0
  if (more < 0)
1927
0
    return isl_union_access_info_free(info);
1928
0
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
0
  }
1933
0
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
0
  }
1938
0
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
0
  }
1943
0
1944
0
  return isl_union_access_info_init(info);
1945
0
}
1946
1947
/* Read an isl_union_access_info object from the file "input".
1948
 */
1949
__isl_give isl_union_access_info *isl_union_access_info_read_from_file(
1950
  isl_ctx *ctx, FILE *input)
1951
0
{
1952
0
  isl_stream *s;
1953
0
  isl_union_access_info *access;
1954
0
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
0
1961
0
  return access;
1962
0
}
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
static __isl_give isl_union_access_info *isl_union_access_info_align_params(
1969
  __isl_take isl_union_access_info *access)
1970
81
{
1971
81
  isl_space *space;
1972
81
  enum isl_access_type i;
1973
81
1974
81
  if (!access)
1975
0
    return NULL;
1976
81
1977
81
  space = isl_union_map_get_space(access->access[isl_access_sink]);
1978
324
  for (i = isl_access_sink + 1; i < isl_access_end; 
++i243
)
1979
243
    space = isl_space_align_params(space,
1980
243
        isl_union_map_get_space(access->access[i]));
1981
81
  if (access->schedule_map)
1982
81
    space = isl_space_align_params(space,
1983
81
        isl_union_map_get_space(access->schedule_map));
1984
405
  for (i = isl_access_sink; i < isl_access_end; 
++i324
)
1985
324
    access->access[i] =
1986
324
      isl_union_map_align_params(access->access[i],
1987
324
              isl_space_copy(space));
1988
81
  if (!access->schedule_map) {
1989
0
    isl_space_free(space);
1990
81
  } else {
1991
81
    access->schedule_map =
1992
81
        isl_union_map_align_params(access->schedule_map, space);
1993
81
    if (!access->schedule_map)
1994
0
      return isl_union_access_info_free(access);
1995
81
  }
1996
81
1997
405
  
for (i = isl_access_sink; 81
i < isl_access_end;
++i324
)
1998
324
    if (!access->access[i])
1999
0
      return isl_union_access_info_free(access);
2000
81
2001
81
  return access;
2002
81
}
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
isl_union_access_info_introduce_schedule(
2028
  __isl_take isl_union_access_info *access)
2029
81
{
2030
81
  isl_union_map *sm;
2031
81
  enum isl_access_type i;
2032
81
2033
81
  if (!access)
2034
0
    return NULL;
2035
81
2036
81
  sm = isl_union_map_reverse(access->schedule_map);
2037
81
  sm = isl_union_map_range_map(sm);
2038
405
  for (i = isl_access_sink; i < isl_access_end; 
++i324
)
2039
324
    access->access[i] =
2040
324
      isl_union_map_apply_range(isl_union_map_copy(sm),
2041
324
            access->access[i]);
2042
81
  access->schedule_map = sm;
2043
81
2044
405
  for (i = isl_access_sink; i < isl_access_end; 
++i324
)
2045
324
    if (!access->access[i])
2046
0
      return isl_union_access_info_free(access);
2047
81
  if (!access->schedule_map)
2048
0
    return isl_union_access_info_free(access);
2049
81
2050
81
  return access;
2051
81
}
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
isl_ctx *isl_union_flow_get_ctx(__isl_keep isl_union_flow *flow)
2077
0
{
2078
0
  return flow ? isl_union_map_get_ctx(flow->must_dep) : NULL;
2079
0
}
2080
2081
/* Free "flow" and return NULL.
2082
 */
2083
__isl_null isl_union_flow *isl_union_flow_free(__isl_take isl_union_flow *flow)
2084
2.49k
{
2085
2.49k
  if (!flow)
2086
24
    return NULL;
2087
2.47k
  isl_union_map_free(flow->must_dep);
2088
2.47k
  isl_union_map_free(flow->may_dep);
2089
2.47k
  isl_union_map_free(flow->must_no_source);
2090
2.47k
  isl_union_map_free(flow->may_no_source);
2091
2.47k
  free(flow);
2092
2.47k
  return NULL;
2093
2.47k
}
2094
2095
void isl_union_flow_dump(__isl_keep isl_union_flow *flow)
2096
0
{
2097
0
  if (!flow)
2098
0
    return;
2099
0
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
0
}
2109
2110
/* Return the full definite dependences in "flow", with accessed elements.
2111
 */
2112
__isl_give isl_union_map *isl_union_flow_get_full_must_dependence(
2113
  __isl_keep isl_union_flow *flow)
2114
0
{
2115
0
  if (!flow)
2116
0
    return NULL;
2117
0
  return isl_union_map_copy(flow->must_dep);
2118
0
}
2119
2120
/* Return the full possible dependences in "flow", including the definite
2121
 * dependences, with accessed elements.
2122
 */
2123
__isl_give isl_union_map *isl_union_flow_get_full_may_dependence(
2124
  __isl_keep isl_union_flow *flow)
2125
598
{
2126
598
  if (!flow)
2127
6
    return NULL;
2128
592
  return isl_union_map_union(isl_union_map_copy(flow->must_dep),
2129
592
            isl_union_map_copy(flow->may_dep));
2130
592
}
2131
2132
/* Return the definite dependences in "flow", without the accessed elements.
2133
 */
2134
__isl_give isl_union_map *isl_union_flow_get_must_dependence(
2135
  __isl_keep isl_union_flow *flow)
2136
687
{
2137
687
  isl_union_map *dep;
2138
687
2139
687
  if (!flow)
2140
6
    return NULL;
2141
681
  dep = isl_union_map_copy(flow->must_dep);
2142
681
  return isl_union_map_range_factor_domain(dep);
2143
681
}
2144
2145
/* Return the possible dependences in "flow", including the definite
2146
 * dependences, without the accessed elements.
2147
 */
2148
__isl_give isl_union_map *isl_union_flow_get_may_dependence(
2149
  __isl_keep isl_union_flow *flow)
2150
1.21k
{
2151
1.21k
  isl_union_map *dep;
2152
1.21k
2153
1.21k
  if (!flow)
2154
12
    return NULL;
2155
1.20k
  dep = isl_union_map_union(isl_union_map_copy(flow->must_dep),
2156
1.20k
            isl_union_map_copy(flow->may_dep));
2157
1.20k
  return isl_union_map_range_factor_domain(dep);
2158
1.20k
}
2159
2160
/* Return the non-definite dependences in "flow".
2161
 */
2162
static __isl_give isl_union_map *isl_union_flow_get_non_must_dependence(
2163
  __isl_keep isl_union_flow *flow)
2164
41
{
2165
41
  if (!flow)
2166
0
    return NULL;
2167
41
  return isl_union_map_copy(flow->may_dep);
2168
41
}
2169
2170
/* Return the subset of the sink accesses for which definitely
2171
 * no source was found.
2172
 */
2173
__isl_give isl_union_map *isl_union_flow_get_must_no_source(
2174
  __isl_keep isl_union_flow *flow)
2175
0
{
2176
0
  if (!flow)
2177
0
    return NULL;
2178
0
  return isl_union_map_copy(flow->must_no_source);
2179
0
}
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
__isl_give isl_union_map *isl_union_flow_get_may_no_source(
2186
  __isl_keep isl_union_flow *flow)
2187
0
{
2188
0
  if (!flow)
2189
0
    return NULL;
2190
0
  return isl_union_map_union(isl_union_map_copy(flow->must_no_source),
2191
0
            isl_union_map_copy(flow->may_no_source));
2192
0
}
2193
2194
/* Return the subset of the sink accesses for which possibly, but not
2195
 * definitely, no source was found.
2196
 */
2197
static __isl_give isl_union_map *isl_union_flow_get_non_must_no_source(
2198
  __isl_keep isl_union_flow *flow)
2199
0
{
2200
0
  if (!flow)
2201
0
    return NULL;
2202
0
  return isl_union_map_copy(flow->may_no_source);
2203
0
}
2204
2205
/* Create a new isl_union_flow object, initialized with empty
2206
 * dependence relations and sink subsets.
2207
 */
2208
static __isl_give isl_union_flow *isl_union_flow_alloc(
2209
  __isl_take isl_space *space)
2210
2.47k
{
2211
2.47k
  isl_ctx *ctx;
2212
2.47k
  isl_union_map *empty;
2213
2.47k
  isl_union_flow *flow;
2214
2.47k
2215
2.47k
  if (!space)
2216
0
    return NULL;
2217
2.47k
  ctx = isl_space_get_ctx(space);
2218
2.47k
  flow = isl_alloc_type(ctx, isl_union_flow);
2219
2.47k
  if (!flow)
2220
0
    goto error;
2221
2.47k
2222
2.47k
  empty = isl_union_map_empty(space);
2223
2.47k
  flow->must_dep = isl_union_map_copy(empty);
2224
2.47k
  flow->may_dep = isl_union_map_copy(empty);
2225
2.47k
  flow->must_no_source = isl_union_map_copy(empty);
2226
2.47k
  flow->may_no_source = empty;
2227
2.47k
2228
2.47k
  if (!flow->must_dep || !flow->may_dep ||
2229
2.47k
      !flow->must_no_source || !flow->may_no_source)
2230
0
    return isl_union_flow_free(flow);
2231
2.47k
2232
2.47k
  return flow;
2233
0
error:
2234
0
  isl_space_free(space);
2235
0
  return NULL;
2236
2.47k
}
2237
2238
/* Copy this isl_union_flow object.
2239
 */
2240
__isl_give isl_union_flow *isl_union_flow_copy(__isl_keep isl_union_flow *flow)
2241
0
{
2242
0
  isl_union_flow *copy;
2243
0
2244
0
  if (!flow)
2245
0
    return NULL;
2246
0
2247
0
  copy = isl_union_flow_alloc(isl_union_map_get_space(flow->must_dep));
2248
0
2249
0
  if (!copy)
2250
0
    return NULL;
2251
0
2252
0
  copy->must_dep = isl_union_map_union(copy->must_dep,
2253
0
    isl_union_map_copy(flow->must_dep));
2254
0
  copy->may_dep = isl_union_map_union(copy->may_dep,
2255
0
    isl_union_map_copy(flow->may_dep));
2256
0
  copy->must_no_source = isl_union_map_union(copy->must_no_source,
2257
0
    isl_union_map_copy(flow->must_no_source));
2258
0
  copy->may_no_source = isl_union_map_union(copy->may_no_source,
2259
0
    isl_union_map_copy(flow->may_no_source));
2260
0
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
0
2265
0
  return copy;
2266
0
}
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
static __isl_give isl_union_flow *isl_union_flow_drop_schedule(
2289
  __isl_take isl_union_flow *flow)
2290
81
{
2291
81
  if (!flow)
2292
0
    return NULL;
2293
81
2294
81
  flow->must_dep = isl_union_map_range_curry(flow->must_dep);
2295
81
  flow->must_dep = isl_union_map_factor_range(flow->must_dep);
2296
81
  flow->may_dep = isl_union_map_range_curry(flow->may_dep);
2297
81
  flow->may_dep = isl_union_map_factor_range(flow->may_dep);
2298
81
  flow->must_no_source =
2299
81
    isl_union_map_domain_factor_range(flow->must_no_source);
2300
81
  flow->may_no_source =
2301
81
    isl_union_map_domain_factor_range(flow->may_no_source);
2302
81
2303
81
  if (!flow->must_dep || !flow->may_dep ||
2304
81
      !flow->must_no_source || !flow->may_no_source)
2305
0
    return isl_union_flow_free(flow);
2306
81
2307
81
  return flow;
2308
81
}
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
static isl_stat count_matching_array(__isl_take isl_map *map, void *user)
2324
380
{
2325
380
  int eq;
2326
380
  isl_space *dim;
2327
380
  struct isl_compute_flow_data *data;
2328
380
2329
380
  data = (struct isl_compute_flow_data *)user;
2330
380
2331
380
  dim = isl_space_range(isl_map_get_space(map));
2332
380
2333
380
  eq = isl_space_is_equal(dim, data->dim);
2334
380
2335
380
  isl_space_free(dim);
2336
380
  isl_map_free(map);
2337
380
2338
380
  if (eq < 0)
2339
0
    return isl_stat_error;
2340
380
  if (eq)
2341
274
    data->count++;
2342
380
2343
380
  return isl_stat_ok;
2344
380
}
2345
2346
static isl_stat collect_matching_array(__isl_take isl_map *map, void *user)
2347
380
{
2348
380
  int eq;
2349
380
  isl_space *dim;
2350
380
  struct isl_sched_info *info;
2351
380
  struct isl_compute_flow_data *data;
2352
380
2353
380
  data = (struct isl_compute_flow_data *)user;
2354
380
2355
380
  dim = isl_space_range(isl_map_get_space(map));
2356
380
2357
380
  eq = isl_space_is_equal(dim, data->dim);
2358
380
2359
380
  isl_space_free(dim);
2360
380
2361
380
  if (eq < 0)
2362
0
    goto error;
2363
380
  if (!eq) {
2364
106
    isl_map_free(map);
2365
106
    return isl_stat_ok;
2366
106
  }
2367
274
2368
274
  info = sched_info_alloc(map);
2369
274
  data->source_info[data->count] = info;
2370
274
2371
274
  data->accesses = isl_access_info_add_source(data->accesses,
2372
274
                map, data->must, info);
2373
274
2374
274
  data->count++;
2375
274
2376
274
  return isl_stat_ok;
2377
0
error:
2378
0
  isl_map_free(map);
2379
0
  return isl_stat_error;
2380
274
}
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
static int before(void *first, void *second)
2395
3.60k
{
2396
3.60k
  struct isl_sched_info *info1 = first;
2397
3.60k
  struct isl_sched_info *info2 = second;
2398
3.60k
  int n1, n2;
2399
3.60k
  int i;
2400
3.60k
2401
3.60k
  n1 = isl_vec_size(info1->cst);
2402
3.60k
  n2 = isl_vec_size(info2->cst);
2403
3.60k
2404
3.60k
  if (n2 < n1)
2405
160
    n1 = n2;
2406
3.60k
2407
10.5k
  for (i = 0; i < n1; 
++i6.97k
) {
2408
8.95k
    int r;
2409
8.95k
    int cmp;
2410
8.95k
2411
8.95k
    if (!info1->is_cst[i])
2412
3.12k
      continue;
2413
5.83k
    if (!info2->is_cst[i])
2414
0
      continue;
2415
5.83k
    cmp = isl_vec_cmp_element(info1->cst, info2->cst, i);
2416
5.83k
    if (cmp == 0)
2417
3.84k
      continue;
2418
1.98k
2419
1.98k
    r = 2 * i + (cmp < 0);
2420
1.98k
2421
1.98k
    return r;
2422
1.98k
  }
2423
3.60k
2424
3.60k
  
return 2 * n11.61k
;
2425
3.60k
}
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
static int coscheduled(void *first, void *second)
2434
44
{
2435
44
  struct isl_sched_info *info1 = first;
2436
44
  struct isl_sched_info *info2 = second;
2437
44
  int n1, n2;
2438
44
  int i;
2439
44
2440
44
  n1 = isl_vec_size(info1->cst);
2441
44
  n2 = isl_vec_size(info2->cst);
2442
44
2443
44
  if (n2 < n1)
2444
8
    n1 = n2;
2445
44
2446
80
  for (i = 0; i < n1; 
++i36
) {
2447
76
    int cmp;
2448
76
2449
76
    if (!info1->is_cst[i])
2450
18
      continue;
2451
58
    if (!info2->is_cst[i])
2452
0
      continue;
2453
58
    cmp = isl_vec_cmp_element(info1->cst, info2->cst, i);
2454
58
    if (cmp != 0)
2455
40
      return 0;
2456
58
  }
2457
44
2458
44
  
return 14
;
2459
44
}
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
static isl_stat compute_flow(__isl_take isl_map *map, void *user)
2466
126
{
2467
126
  int i;
2468
126
  isl_ctx *ctx;
2469
126
  struct isl_compute_flow_data *data;
2470
126
  isl_flow *flow;
2471
126
  isl_union_flow *df;
2472
126
2473
126
  data = (struct isl_compute_flow_data *)user;
2474
126
  df = data->flow;
2475
126
2476
126
  ctx = isl_map_get_ctx(map);
2477
126
2478
126
  data->accesses = NULL;
2479
126
  data->sink_info = NULL;
2480
126
  data->source_info = NULL;
2481
126
  data->count = 0;
2482
126
  data->dim = isl_space_range(isl_map_get_space(map));
2483
126
2484
126
  if (isl_union_map_foreach_map(data->must_source,
2485
126
          &count_matching_array, data) < 0)
2486
0
    goto error;
2487
126
  if (isl_union_map_foreach_map(data->may_source,
2488
126
          &count_matching_array, data) < 0)
2489
0
    goto error;
2490
126
2491
126
  data->sink_info = sched_info_alloc(map);
2492
126
  data->source_info = isl_calloc_array(ctx, struct isl_sched_info *,
2493
126
               data->count);
2494
126
2495
126
  data->accesses = isl_access_info_alloc(isl_map_copy(map),
2496
126
        data->sink_info, &before, data->count);
2497
126
  if (!data->sink_info || (data->count && 
!data->source_info122
) ||
2498
126
      !data->accesses)
2499
0
    goto error;
2500
126
  data->accesses->coscheduled = &coscheduled;
2501
126
  data->count = 0;
2502
126
  data->must = 1;
2503
126
  if (isl_union_map_foreach_map(data->must_source,
2504
126
          &collect_matching_array, data) < 0)
2505
0
    goto error;
2506
126
  data->must = 0;
2507
126
  if (isl_union_map_foreach_map(data->may_source,
2508
126
          &collect_matching_array, data) < 0)
2509
0
    goto error;
2510
126
2511
126
  flow = access_info_compute_flow_core(data->accesses);
2512
126
  data->accesses = NULL;
2513
126
2514
126
  if (!flow)
2515
0
    goto error;
2516
126
2517
126
  df->must_no_source = isl_union_map_union(df->must_no_source,
2518
126
        isl_union_map_from_map(isl_flow_get_no_source(flow, 1)));
2519
126
  df->may_no_source = isl_union_map_union(df->may_no_source,
2520
126
        isl_union_map_from_map(isl_flow_get_no_source(flow, 0)));
2521
126
2522
598
  for (i = 0; i < flow->n_source; 
++i472
) {
2523
472
    isl_union_map *dep;
2524
472
    dep = isl_union_map_from_map(isl_map_copy(flow->dep[i].map));
2525
472
    if (flow->dep[i].must)
2526
198
      df->must_dep = isl_union_map_union(df->must_dep, dep);
2527
274
    else
2528
274
      df->may_dep = isl_union_map_union(df->may_dep, dep);
2529
472
  }
2530
126
2531
126
  isl_flow_free(flow);
2532
126
2533
126
  sched_info_free(data->sink_info);
2534
126
  if (data->source_info) {
2535
400
    for (i = 0; i < data->count; 
++i274
)
2536
274
      sched_info_free(data->source_info[i]);
2537
126
    free(data->source_info);
2538
126
  }
2539
126
  isl_space_free(data->dim);
2540
126
  isl_map_free(map);
2541
126
2542
126
  return isl_stat_ok;
2543
0
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
0
  }
2551
0
  isl_space_free(data->dim);
2552
0
  isl_map_free(map);
2553
0
2554
0
  return isl_stat_error;
2555
126
}
2556
2557
/* Add the kills of "info" to the must-sources.
2558
 */
2559
static __isl_give isl_union_access_info *
2560
isl_union_access_info_add_kill_to_must_source(
2561
  __isl_take isl_union_access_info *info)
2562
2.47k
{
2563
2.47k
  isl_union_map *must, *kill;
2564
2.47k
2565
2.47k
  must = isl_union_access_info_get_must_source(info);
2566
2.47k
  kill = isl_union_access_info_get_kill(info);
2567
2.47k
  must = isl_union_map_union(must, kill);
2568
2.47k
  return isl_union_access_info_set_must_source(info, must);
2569
2.47k
}
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
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
0
{
2597
0
  isl_union_map *move;
2598
0
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
0
        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
0
        flow->may_dep, may);
2607
0
  flow->must_dep = isl_union_map_intersect_range_factor_range(
2608
0
        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
0
2613
0
  return flow;
2614
0
error:
2615
0
  isl_union_map_free(must);
2616
0
  isl_union_map_free(may);
2617
0
  return NULL;
2618
0
}
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
static __isl_give isl_union_access_info *isl_union_access_info_normalize(
2628
  __isl_take isl_union_access_info *access)
2629
2.47k
{
2630
2.47k
  if (!access)
2631
0
    return NULL;
2632
2.47k
  access->access[isl_access_may_source] =
2633
2.47k
    isl_union_map_subtract(access->access[isl_access_may_source],
2634
2.47k
        isl_union_map_copy(access->access[isl_access_must_source]));
2635
2.47k
  if (!access->access[isl_access_may_source])
2636
0
    return isl_union_access_info_free(access);
2637
2.47k
2638
2.47k
  return access;
2639
2.47k
}
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
static __isl_give isl_union_flow *compute_flow_union_map(
2661
  __isl_take isl_union_access_info *access)
2662
81
{
2663
81
  struct isl_compute_flow_data data;
2664
81
  isl_union_map *sink;
2665
81
2666
81
  access = isl_union_access_info_align_params(access);
2667
81
  access = isl_union_access_info_introduce_schedule(access);
2668
81
  if (!access)
2669
0
    return NULL;
2670
81
2671
81
  data.must_source = access->access[isl_access_must_source];
2672
81
  data.may_source = access->access[isl_access_may_source];
2673
81
2674
81
  sink = access->access[isl_access_sink];
2675
81
  data.flow = isl_union_flow_alloc(isl_union_map_get_space(sink));
2676
81
2677
81
  if (isl_union_map_foreach_map(sink, &compute_flow, &data) < 0)
2678
0
    goto error;
2679
81
2680
81
  data.flow = isl_union_flow_drop_schedule(data.flow);
2681
81
2682
81
  isl_union_access_info_free(access);
2683
81
  return data.flow;
2684
0
error:
2685
0
  isl_union_access_info_free(access);
2686
0
  isl_union_flow_free(data.flow);
2687
0
  return NULL;
2688
81
}
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
static void isl_compute_flow_schedule_data_align_params(
2732
  struct isl_compute_flow_schedule_data *data)
2733
2.39k
{
2734
2.39k
  int i;
2735
2.39k
  isl_space *space;
2736
2.39k
2737
2.39k
  if (data->n_sink == 0 || 
data->n_source == 02.16k
)
2738
237
    return;
2739
2.15k
2740
2.15k
  space = isl_map_get_space(data->sink[0].access);
2741
2.15k
2742
3.87k
  for (i = 1; i < data->n_sink; 
++i1.72k
)
2743
1.72k
    space = isl_space_align_params(space,
2744
1.72k
        isl_map_get_space(data->sink[i].access));
2745
6.97k
  for (i = 0; i < data->n_source; 
++i4.81k
)
2746
4.81k
    space = isl_space_align_params(space,
2747
4.81k
        isl_map_get_space(data->source[i].access));
2748
2.15k
2749
6.03k
  for (i = 0; i < data->n_sink; 
++i3.87k
)
2750
3.87k
    data->sink[i].access =
2751
3.87k
      isl_map_align_params(data->sink[i].access,
2752
3.87k
              isl_space_copy(space));
2753
6.97k
  for (i = 0; i < data->n_source; 
++i4.81k
)
2754
4.81k
    data->source[i].access =
2755
4.81k
      isl_map_align_params(data->source[i].access,
2756
4.81k
              isl_space_copy(space));
2757
2.15k
2758
2.15k
  isl_space_free(space);
2759
2.15k
}
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
static void isl_compute_flow_schedule_data_clear(
2765
  struct isl_compute_flow_schedule_data *data)
2766
2.39k
{
2767
2.39k
  int i;
2768
2.39k
2769
2.39k
  if (!data->sink)
2770
0
    return;
2771
2.39k
2772
6.28k
  
for (i = 0; 2.39k
i < data->n_sink;
++i3.88k
) {
2773
3.88k
    isl_map_free(data->sink[i].access);
2774
3.88k
    isl_schedule_node_free(data->sink[i].node);
2775
3.88k
  }
2776
2.39k
2777
7.51k
  for (i = 0; i < data->n_source; 
++i5.11k
) {
2778
5.11k
    isl_map_free(data->source[i].access);
2779
5.11k
    isl_schedule_node_free(data->source[i].node);
2780
5.11k
  }
2781
2.39k
2782
2.39k
  free(data->sink);
2783
2.39k
}
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
static isl_bool count_sink_source(__isl_keep isl_schedule_node *node,
2795
  void *user)
2796
13.4k
{
2797
13.4k
  struct isl_compute_flow_schedule_data *data = user;
2798
13.4k
  isl_union_set *domain;
2799
13.4k
  isl_union_map *umap;
2800
13.4k
  isl_bool r = isl_bool_false;
2801
13.4k
2802
13.4k
  if (isl_schedule_node_get_type(node) != isl_schedule_node_leaf)
2803
9.42k
    return isl_bool_true;
2804
3.98k
2805
3.98k
  domain = isl_schedule_node_get_universe_domain(node);
2806
3.98k
2807
3.98k
  umap = isl_union_map_copy(data->access->access[isl_access_sink]);
2808
3.98k
  umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(domain));
2809
3.98k
  data->n_sink += isl_union_map_n_map(umap);
2810
3.98k
  isl_union_map_free(umap);
2811
3.98k
  if (!umap)
2812
0
    r = isl_bool_error;
2813
3.98k
2814
3.98k
  umap = isl_union_map_copy(data->access->access[isl_access_must_source]);
2815
3.98k
  umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(domain));
2816
3.98k
  data->n_source += isl_union_map_n_map(umap);
2817
3.98k
  isl_union_map_free(umap);
2818
3.98k
  if (!umap)
2819
0
    r = isl_bool_error;
2820
3.98k
2821
3.98k
  umap = isl_union_map_copy(data->access->access[isl_access_may_source]);
2822
3.98k
  umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(domain));
2823
3.98k
  data->n_source += isl_union_map_n_map(umap);
2824
3.98k
  isl_union_map_free(umap);
2825
3.98k
  if (!umap)
2826
0
    r = isl_bool_error;
2827
3.98k
2828
3.98k
  isl_union_set_free(domain);
2829
3.98k
2830
3.98k
  return r;
2831
3.98k
}
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
static isl_stat extract_sink_source(__isl_take isl_map *map, void *user)
2838
9.00k
{
2839
9.00k
  struct isl_compute_flow_schedule_data *data = user;
2840
9.00k
  struct isl_scheduled_access *access;
2841
9.00k
2842
9.00k
  if (data->set_sink)
2843
3.88k
    access = data->sink + data->n_sink++;
2844
5.11k
  else
2845
5.11k
    access = data->source + data->n_source++;
2846
9.00k
2847
9.00k
  access->access = map;
2848
9.00k
  access->must = data->must;
2849
9.00k
  access->node = isl_schedule_node_copy(data->node);
2850
9.00k
2851
9.00k
  return isl_stat_ok;
2852
9.00k
}
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
static isl_bool collect_sink_source(__isl_keep isl_schedule_node *node,
2879
  void *user)
2880
13.4k
{
2881
13.4k
  struct isl_compute_flow_schedule_data *data = user;
2882
13.4k
  isl_union_map *prefix;
2883
13.4k
  isl_union_map *umap;
2884
13.4k
  isl_bool r = isl_bool_false;
2885
13.4k
2886
13.4k
  if (isl_schedule_node_get_type(node) != isl_schedule_node_leaf)
2887
9.42k
    return isl_bool_true;
2888
3.98k
2889
3.98k
  data->node = node;
2890
3.98k
2891
3.98k
  prefix = isl_schedule_node_get_prefix_schedule_relation(node);
2892
3.98k
  prefix = isl_union_map_reverse(prefix);
2893
3.98k
  prefix = isl_union_map_range_map(prefix);
2894
3.98k
2895
3.98k
  data->set_sink = 1;
2896
3.98k
  umap = isl_union_map_copy(data->access->access[isl_access_sink]);
2897
3.98k
  umap = isl_union_map_apply_range(isl_union_map_copy(prefix), umap);
2898
3.98k
  if (isl_union_map_foreach_map(umap, &extract_sink_source, data) < 0)
2899
0
    r = isl_bool_error;
2900
3.98k
  isl_union_map_free(umap);
2901
3.98k
2902
3.98k
  data->set_sink = 0;
2903
3.98k
  data->must = 1;
2904
3.98k
  umap = isl_union_map_copy(data->access->access[isl_access_must_source]);
2905
3.98k
  umap = isl_union_map_apply_range(isl_union_map_copy(prefix), umap);
2906
3.98k
  if (isl_union_map_foreach_map(umap, &extract_sink_source, data) < 0)
2907
0
    r = isl_bool_error;
2908
3.98k
  isl_union_map_free(umap);
2909
3.98k
2910
3.98k
  data->set_sink = 0;
2911
3.98k
  data->must = 0;
2912
3.98k
  umap = isl_union_map_copy(data->access->access[isl_access_may_source]);
2913
3.98k
  umap = isl_union_map_apply_range(isl_union_map_copy(prefix), umap);
2914
3.98k
  if (isl_union_map_foreach_map(umap, &extract_sink_source, data) < 0)
2915
0
    r = isl_bool_error;
2916
3.98k
  isl_union_map_free(umap);
2917
3.98k
2918
3.98k
  isl_union_map_free(prefix);
2919
3.98k
2920
3.98k
  return r;
2921
3.98k
}
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
static int before_node(void *first, void *second)
2940
60.6k
{
2941
60.6k
  isl_schedule_node *node1 = first;
2942
60.6k
  isl_schedule_node *node2 = second;
2943
60.6k
  isl_schedule_node *shared;
2944
60.6k
  int depth;
2945
60.6k
  int before = 0;
2946
60.6k
2947
60.6k
  shared = isl_schedule_node_get_shared_ancestor(node1, node2);
2948
60.6k
  if (!shared)
2949
0
    return -1;
2950
60.6k
2951
60.6k
  depth = isl_schedule_node_get_schedule_depth(shared);
2952
60.6k
  if (isl_schedule_node_get_type(shared) == isl_schedule_node_sequence) {
2953
32.1k
    int pos1, pos2;
2954
32.1k
2955
32.1k
    pos1 = isl_schedule_node_get_ancestor_child_position(node1,
2956
32.1k
                    shared);
2957
32.1k
    pos2 = isl_schedule_node_get_ancestor_child_position(node2,
2958
32.1k
                    shared);
2959
32.1k
    before = pos1 < pos2;
2960
32.1k
  }
2961
60.6k
2962
60.6k
  isl_schedule_node_free(shared);
2963
60.6k
2964
60.6k
  return 2 * depth + before;
2965
60.6k
}
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
static int coscheduled_node(void *first, void *second)
2973
1.95k
{
2974
1.95k
  isl_schedule_node *node1 = first;
2975
1.95k
  isl_schedule_node *node2 = second;
2976
1.95k
2977
1.95k
  return node1 == node2;
2978
1.95k
}
2979
2980
/* Add the scheduled sources from "data" that access
2981
 * the same data space as "sink" to "access".
2982
 */
2983
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
3.88k
{
2987
3.88k
  int i;
2988
3.88k
  isl_space *space;
2989
3.88k
2990
3.88k
  space = isl_space_range(isl_map_get_space(sink->access));
2991
17.5k
  for (i = 0; i < data->n_source; 
++i13.6k
) {
2992
13.6k
    struct isl_scheduled_access *source;
2993
13.6k
    isl_space *source_space;
2994
13.6k
    int eq;
2995
13.6k
2996
13.6k
    source = &data->source[i];
2997
13.6k
    source_space = isl_map_get_space(source->access);
2998
13.6k
    source_space = isl_space_range(source_space);
2999
13.6k
    eq = isl_space_is_equal(space, source_space);
3000
13.6k
    isl_space_free(source_space);
3001
13.6k
3002
13.6k
    if (!eq)
3003
7.05k
      continue;
3004
6.61k
    if (eq < 0)
3005
0
      goto error;
3006
6.61k
3007
6.61k
    access = isl_access_info_add_source(access,
3008
6.61k
        isl_map_copy(source->access), source->must, source->node);
3009
6.61k
  }
3010
3.88k
3011
3.88k
  isl_space_free(space);
3012
3.88k
  return access;
3013
0
error:
3014
0
  isl_space_free(space);
3015
0
  isl_access_info_free(access);
3016
0
  return NULL;
3017
3.88k
}
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
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
3.88k
{
3040
3.88k
  int i;
3041
3.88k
  isl_access_info *access;
3042
3.88k
  isl_flow *flow;
3043
3.88k
  isl_map *map;
3044
3.88k
3045
3.88k
  if (!uf)
3046
0
    return NULL;
3047
3.88k
3048
3.88k
  access = isl_access_info_alloc(isl_map_copy(sink->access), sink->node,
3049
3.88k
          &before_node, data->n_source);
3050
3.88k
  if (access)
3051
3.88k
    access->coscheduled = &coscheduled_node;
3052
3.88k
  access = add_matching_sources(access, sink, data);
3053
3.88k
3054
3.88k
  flow = access_info_compute_flow_core(access);
3055
3.88k
  if (!flow)
3056
0
    return isl_union_flow_free(uf);
3057
3.88k
3058
3.88k
  map = isl_map_domain_factor_range(isl_flow_get_no_source(flow, 1));
3059
3.88k
  uf->must_no_source = isl_union_map_union(uf->must_no_source,
3060
3.88k
            isl_union_map_from_map(map));
3061
3.88k
  map = isl_map_domain_factor_range(isl_flow_get_no_source(flow, 0));
3062
3.88k
  uf->may_no_source = isl_union_map_union(uf->may_no_source,
3063
3.88k
            isl_union_map_from_map(map));
3064
3.88k
3065
16.4k
  for (i = 0; i < flow->n_source; 
++i12.6k
) {
3066
12.6k
    isl_union_map *dep;
3067
12.6k
3068
12.6k
    map = isl_map_range_curry(isl_map_copy(flow->dep[i].map));
3069
12.6k
    map = isl_map_factor_range(map);
3070
12.6k
    dep = isl_union_map_from_map(map);
3071
12.6k
    if (flow->dep[i].must)
3072
5.99k
      uf->must_dep = isl_union_map_union(uf->must_dep, dep);
3073
6.61k
    else
3074
6.61k
      uf->may_dep = isl_union_map_union(uf->may_dep, dep);
3075
12.6k
  }
3076
3.88k
3077
3.88k
  isl_flow_free(flow);
3078
3.88k
3079
3.88k
  return uf;
3080
3.88k
}
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
static __isl_give isl_union_flow *compute_flow_schedule(
3104
  __isl_take isl_union_access_info *access)
3105
2.39k
{
3106
2.39k
  struct isl_compute_flow_schedule_data data = { access };
3107
2.39k
  int i, n;
3108
2.39k
  isl_ctx *ctx;
3109
2.39k
  isl_space *space;
3110
2.39k
  isl_union_flow *flow;
3111
2.39k
3112
2.39k
  ctx = isl_union_access_info_get_ctx(access);
3113
2.39k
3114
2.39k
  data.n_sink = 0;
3115
2.39k
  data.n_source = 0;
3116
2.39k
  if (isl_schedule_foreach_schedule_node_top_down(access->schedule,
3117
2.39k
            &count_sink_source, &data) < 0)
3118
0
    goto error;
3119
2.39k
3120
2.39k
  n = data.n_sink + data.n_source;
3121
2.39k
  data.sink = isl_calloc_array(ctx, struct isl_scheduled_access, n);
3122
2.39k
  if (n && !data.sink)
3123
0
    goto error;
3124
2.39k
  data.source = data.sink + data.n_sink;
3125
2.39k
3126
2.39k
  data.n_sink = 0;
3127
2.39k
  data.n_source = 0;
3128
2.39k
  if (isl_schedule_foreach_schedule_node_top_down(access->schedule,
3129
2.39k
              &collect_sink_source, &data) < 0)
3130
0
    goto error;
3131
2.39k
3132
2.39k
  space = isl_union_map_get_space(access->access[isl_access_sink]);
3133
2.39k
  flow = isl_union_flow_alloc(space);
3134
2.39k
3135
2.39k
  isl_compute_flow_schedule_data_align_params(&data);
3136
2.39k
3137
6.28k
  for (i = 0; i < data.n_sink; 
++i3.88k
)
3138
3.88k
    flow = compute_single_flow(flow, &data.sink[i], &data);
3139
2.39k
3140
2.39k
  isl_compute_flow_schedule_data_clear(&data);
3141
2.39k
3142
2.39k
  isl_union_access_info_free(access);
3143
2.39k
  return flow;
3144
0
error:
3145
0
  isl_union_access_info_free(access);
3146
0
  isl_compute_flow_schedule_data_clear(&data);
3147
0
  return NULL;
3148
2.39k
}
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
__isl_give isl_union_flow *isl_union_access_info_compute_flow(
3171
  __isl_take isl_union_access_info *access)
3172
2.49k
{
3173
2.49k
  isl_bool has_kill;
3174
2.49k
  isl_union_map *must = NULL, *may = NULL;
3175
2.49k
  isl_union_flow *flow;
3176
2.49k
3177
2.49k
  has_kill = isl_union_access_has_kill(access);
3178
2.49k
  if (has_kill < 0)
3179
24
    goto error;
3180
2.47k
  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
0
  }
3184
2.47k
  access = isl_union_access_info_add_kill_to_must_source(access);
3185
2.47k
  access = isl_union_access_info_normalize(access);
3186
2.47k
  if (!access)
3187
0
    goto error;
3188
2.47k
  if (access->schedule)
3189
2.39k
    flow = compute_flow_schedule(access);
3190
81
  else
3191
81
    flow = compute_flow_union_map(access);
3192
2.47k
  if (has_kill)
3193
0
    flow = isl_union_flow_drop_kill_source(flow, must, may);
3194
2.47k
  return flow;
3195
24
error:
3196
24
  isl_union_access_info_free(access);
3197
24
  isl_union_map_free(must);
3198
24
  isl_union_map_free(may);
3199
24
  return NULL;
3200
2.47k
}
3201
3202
/* Print the information contained in "flow" to "p".
3203
 * The information is printed as a YAML document.
3204
 */
3205
__isl_give isl_printer *isl_printer_print_union_flow(
3206
  __isl_take isl_printer *p, __isl_keep isl_union_flow *flow)
3207
0
{
3208
0
  isl_union_map *umap;
3209
0
3210
0
  if (!flow)
3211
0
    return isl_printer_free(p);
3212
0
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
0
3226
0
  return p;
3227
0
}
3228
3229
/* Return a string representation of the information in "flow".
3230
 * The information is printed in flow format.
3231
 */
3232
__isl_give char *isl_union_flow_to_str(__isl_keep isl_union_flow *flow)
3233
0
{
3234
0
  isl_printer *p;
3235
0
  char *s;
3236
0
3237
0
  if (!flow)
3238
0
    return NULL;
3239
0
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
0
3246
0
  return s;
3247
0
}
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
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
81
{
3273
81
  isl_union_access_info *access;
3274
81
  isl_union_flow *flow;
3275
81
3276
81
  access = isl_union_access_info_from_sink(sink);
3277
81
  access = isl_union_access_info_set_must_source(access, must_source);
3278
81
  access = isl_union_access_info_set_may_source(access, may_source);
3279
81
  access = isl_union_access_info_set_schedule_map(access, schedule);
3280
81
  flow = isl_union_access_info_compute_flow(access);
3281
81
3282
81
  if (must_dep)
3283
81
    *must_dep = isl_union_flow_get_must_dependence(flow);
3284
81
  if (may_dep)
3285
41
    *may_dep = isl_union_flow_get_non_must_dependence(flow);
3286
81
  if (must_no_source)
3287
0
    *must_no_source = isl_union_flow_get_must_no_source(flow);
3288
81
  if (may_no_source)
3289
0
    *may_no_source = isl_union_flow_get_non_must_no_source(flow);
3290
81
3291
81
  isl_union_flow_free(flow);
3292
81
3293
81
  if ((must_dep && !*must_dep) || (may_dep && 
!*may_dep41
) ||
3294
81
      (must_no_source && 
!*must_no_source0
) ||
3295
81
      (may_no_source && 
!*may_no_source0
))
3296
0
    goto error;
3297
81
3298
81
  return 0;
3299
0
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
81
}