Coverage Report

Created: 2017-11-21 16:49

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