Coverage Report

Created: 2017-08-18 19:41

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/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 || 0
!sink_restr0
)
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
3.55k
{
215
3.55k
  isl_ctx *ctx;
216
3.55k
  struct isl_access_info *acc;
217
3.55k
218
3.55k
  if (!sink)
219
0
    return NULL;
220
3.55k
221
3.55k
  ctx = isl_map_get_ctx(sink);
222
3.55k
  isl_assert(ctx, max_source >= 0, goto error);
223
3.55k
224
3.55k
  
acc = 3.55k
isl_calloc3.55k
(ctx, struct isl_access_info,
225
3.55k
      sizeof(struct isl_access_info) +
226
3.55k
      (max_source - 1) * sizeof(struct isl_labeled_map));
227
3.55k
  if (!acc)
228
0
    goto error;
229
3.55k
230
3.55k
  acc->sink.map = sink;
231
3.55k
  acc->sink.data = sink_user;
232
3.55k
  acc->level_before = fn;
233
3.55k
  acc->max_source = max_source;
234
3.55k
  acc->n_must = 0;
235
3.55k
  acc->n_may = 0;
236
3.55k
237
3.55k
  return acc;
238
3.55k
error:
239
0
  isl_map_free(sink);
240
3.55k
  return NULL;
241
3.55k
}
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
3.55k
{
248
3.55k
  int i;
249
3.55k
250
3.55k
  if (!acc)
251
0
    return NULL;
252
3.55k
  isl_map_free(acc->domain_map);
253
3.55k
  isl_map_free(acc->sink.map);
254
9.60k
  for (i = 0; 
i < acc->n_must + acc->n_may9.60k
;
++i6.05k
)
255
6.05k
    isl_map_free(acc->source[i].map);
256
3.55k
  free(acc);
257
3.55k
  return NULL;
258
3.55k
}
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
6.05k
{
285
6.05k
  isl_ctx *ctx;
286
6.05k
287
6.05k
  if (!acc)
288
0
    goto error;
289
6.05k
  ctx = isl_map_get_ctx(acc->sink.map);
290
6.05k
  isl_assert(ctx, acc->n_must + acc->n_may < acc->max_source, goto error);
291
6.05k
  
292
6.05k
  
if (6.05k
must6.05k
)
{5.45k
293
5.45k
    if (acc->n_may)
294
5.45k
      acc->source[acc->n_must + acc->n_may] =
295
5.45k
        acc->source[acc->n_must];
296
5.45k
    acc->source[acc->n_must].map = source;
297
5.45k
    acc->source[acc->n_must].data = source_user;
298
5.45k
    acc->source[acc->n_must].must = 1;
299
5.45k
    acc->n_must++;
300
6.05k
  } else {
301
600
    acc->source[acc->n_must + acc->n_may].map = source;
302
600
    acc->source[acc->n_must + acc->n_may].data = source_user;
303
600
    acc->source[acc->n_must + acc->n_may].must = 0;
304
600
    acc->n_may++;
305
6.05k
  }
306
6.05k
307
6.05k
  return acc;
308
6.05k
error:
309
0
  isl_map_free(source);
310
0
  isl_access_info_free(acc);
311
6.05k
  return NULL;
312
6.05k
}
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
3.40k
{
339
3.40k
  struct access_sort_info *sort_info = user;
340
3.40k
  isl_access_info *acc = sort_info->access_info;
341
3.40k
342
3.40k
  if (sort_info->error)
343
0
    return 0;
344
3.40k
345
3.40k
  const struct isl_labeled_map *i1, *i2;
346
3.40k
  int level1, level2;
347
3.40k
  uint32_t h1, h2;
348
3.40k
  i1 = (const struct isl_labeled_map *) p1;
349
3.40k
  i2 = (const struct isl_labeled_map *) p2;
350
3.40k
351
3.40k
  level1 = acc->level_before(i1->data, i2->data);
352
3.40k
  if (level1 < 0)
353
0
    goto error;
354
3.40k
  
if (3.40k
level1 % 23.40k
)
355
3.35k
    return -1;
356
3.40k
357
3.40k
  level2 = acc->level_before(i2->data, i1->data);
358
51
  if (level2 < 0)
359
0
    goto error;
360
51
  
if (51
level2 % 251
)
361
50
    return 1;
362
51
363
51
  h1 = isl_map_get_hash(i1->map);
364
1
  h2 = isl_map_get_hash(i2->map);
365
1
  return h1 > h2 ? 
11
:
h1 < h2 ? 0
-10
:
00
;
366
51
error:
367
0
  sort_info->error = 1;
368
51
  return 0;
369
3.40k
}
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
3.25k
{
376
3.25k
  struct access_sort_info sort_info;
377
3.25k
378
3.25k
  sort_info.access_info = acc;
379
3.25k
  sort_info.error = 0;
380
3.25k
381
3.25k
  if (!acc)
382
0
    return NULL;
383
3.25k
  
if (3.25k
acc->n_must <= 13.25k
)
384
2.12k
    return acc;
385
3.25k
386
1.12k
  
if (1.12k
isl_sort(acc->source, acc->n_must, sizeof(struct isl_labeled_map),1.12k
387
1.12k
        access_sort_cmp, &sort_info) < 0)
388
0
    return isl_access_info_free(acc);
389
1.12k
  
if (1.12k
sort_info.error1.12k
)
390
0
    return isl_access_info_free(acc);
391
1.12k
392
1.12k
  return acc;
393
3.25k
}
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
6.22k
{
401
6.22k
  isl_bool equal_params;
402
6.22k
403
6.22k
  equal_params = isl_space_has_equal_params(left, right);
404
6.22k
  if (equal_params < 0)
405
0
    goto error;
406
6.22k
  
if (6.22k
equal_params6.22k
)
407
6.22k
    return isl_space_join(left, right);
408
6.22k
409
6.22k
  left = isl_space_align_params(left, isl_space_copy(right));
410
0
  right = isl_space_align_params(right, isl_space_copy(left));
411
6.22k
  return isl_space_join(left, right);
412
6.22k
error:
413
0
  isl_space_free(left);
414
0
  isl_space_free(right);
415
6.22k
  return NULL;
416
6.22k
}
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
3.55k
{
430
3.55k
  int i, n;
431
3.55k
  struct isl_ctx *ctx;
432
3.55k
  struct isl_flow *dep;
433
3.55k
434
3.55k
  if (!acc)
435
0
    return NULL;
436
3.55k
437
3.55k
  ctx = isl_map_get_ctx(acc->sink.map);
438
3.55k
  dep = isl_calloc_type(ctx, struct isl_flow);
439
3.55k
  if (!dep)
440
0
    return NULL;
441
3.55k
442
3.55k
  n = 2 * acc->n_must + acc->n_may;
443
3.55k
  dep->dep = isl_calloc_array(ctx, struct isl_labeled_map, n);
444
3.55k
  if (
n && 3.55k
!dep->dep3.31k
)
445
0
    goto error;
446
3.55k
447
3.55k
  dep->n_source = n;
448
9.00k
  for (i = 0; 
i < acc->n_must9.00k
;
++i5.45k
)
{5.45k
449
5.45k
    isl_space *dim;
450
5.45k
    dim = space_align_and_join(
451
5.45k
      isl_map_get_space(acc->source[i].map),
452
5.45k
      isl_space_reverse(isl_map_get_space(acc->sink.map)));
453
5.45k
    dep->dep[2 * i].map = isl_map_empty(dim);
454
5.45k
    dep->dep[2 * i + 1].map = isl_map_copy(dep->dep[2 * i].map);
455
5.45k
    dep->dep[2 * i].data = acc->source[i].data;
456
5.45k
    dep->dep[2 * i + 1].data = acc->source[i].data;
457
5.45k
    dep->dep[2 * i].must = 1;
458
5.45k
    dep->dep[2 * i + 1].must = 0;
459
5.45k
    if (
!dep->dep[2 * i].map || 5.45k
!dep->dep[2 * i + 1].map5.45k
)
460
0
      goto error;
461
5.45k
  }
462
4.15k
  
for (i = acc->n_must; 3.55k
i < acc->n_must + acc->n_may4.15k
;
++i600
)
{600
463
600
    isl_space *dim;
464
600
    dim = space_align_and_join(
465
600
      isl_map_get_space(acc->source[i].map),
466
600
      isl_space_reverse(isl_map_get_space(acc->sink.map)));
467
600
    dep->dep[acc->n_must + i].map = isl_map_empty(dim);
468
600
    dep->dep[acc->n_must + i].data = acc->source[i].data;
469
600
    dep->dep[acc->n_must + i].must = 0;
470
600
    if (!dep->dep[acc->n_must + i].map)
471
0
      goto error;
472
3.55k
  }
473
3.55k
474
3.55k
  return dep;
475
3.55k
error:
476
0
  isl_flow_free(dep);
477
3.55k
  return NULL;
478
3.55k
}
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
6
{
491
6
  int i;
492
6
493
6
  if (!deps)
494
0
    return isl_stat_error;
495
6
496
21
  
for (i = 0; 6
i < deps->n_source21
;
++i15
)
{15
497
15
    if (isl_map_plain_is_empty(deps->dep[i].map))
498
3
      continue;
499
12
    
if (12
fn(isl_map_copy(deps->dep[i].map), deps->dep[i].must,12
500
12
        deps->dep[i].data, user) < 0)
501
0
      return isl_stat_error;
502
12
  }
503
6
504
6
  return isl_stat_ok;
505
6
}
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
7.09k
{
511
7.09k
  if (!deps)
512
0
    return NULL;
513
7.09k
  
514
7.09k
  
if (7.09k
must7.09k
)
515
3.54k
    return isl_set_unwrap(isl_set_copy(deps->must_no_source));
516
7.09k
  else
517
3.54k
    return isl_set_unwrap(isl_set_copy(deps->may_no_source));
518
7.09k
}
519
520
void isl_flow_free(__isl_take isl_flow *deps)
521
3.55k
{
522
3.55k
  int i;
523
3.55k
524
3.55k
  if (!deps)
525
0
    return;
526
3.55k
  isl_set_free(deps->must_no_source);
527
3.55k
  isl_set_free(deps->may_no_source);
528
3.55k
  if (
deps->dep3.55k
)
{3.55k
529
15.0k
    for (i = 0; 
i < deps->n_source15.0k
;
++i11.5k
)
530
11.5k
      isl_map_free(deps->dep[i].map);
531
3.55k
    free(deps->dep);
532
3.55k
  }
533
3.55k
  free(deps);
534
3.55k
}
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
13.8k
{
553
13.8k
  struct isl_basic_map *bmap;
554
13.8k
555
13.8k
  if (level % 2)
556
2.26k
    bmap = isl_basic_map_equal(dim, level/2);
557
13.8k
  else
558
11.5k
    bmap = isl_basic_map_more_at(dim, level/2 - 1);
559
13.8k
560
13.8k
  return isl_map_from_basic_map(bmap);
561
13.8k
}
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
10.4k
{
579
10.4k
  isl_map *source_map;
580
10.4k
  isl_restriction *restr;
581
10.4k
  isl_set *sink_domain;
582
10.4k
  isl_set *sink_restr;
583
10.4k
  isl_map *res;
584
10.4k
585
10.4k
  if (!acc->restrict_fn)
586
10.4k
    return isl_map_partial_lexmax(dep, sink, empty);
587
10.4k
588
10.4k
  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 (0
restr->type == isl_restriction_type_input0
)
{0
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 (0
restr->type == isl_restriction_type_empty0
)
{0
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
10.4k
}
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
10.2k
{
635
10.2k
  struct isl_map *read_map;
636
10.2k
  struct isl_map *write_map;
637
10.2k
  struct isl_map *dep_map;
638
10.2k
  struct isl_map *after;
639
10.2k
  struct isl_map *result;
640
10.2k
641
10.2k
  read_map = isl_map_copy(acc->sink.map);
642
10.2k
  write_map = isl_map_copy(acc->source[j].map);
643
10.2k
  write_map = isl_map_reverse(write_map);
644
10.2k
  dep_map = isl_map_apply_range(read_map, write_map);
645
10.2k
  after = after_at_level(isl_map_get_space(dep_map), level);
646
10.2k
  dep_map = isl_map_intersect(dep_map, after);
647
10.2k
  result = restricted_partial_lexmax(acc, dep_map, j, set_C, empty);
648
10.2k
  result = isl_map_reverse(result);
649
10.2k
650
10.2k
  return result;
651
10.2k
}
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
164
{
665
164
  isl_space *dim;
666
164
  struct isl_set *set_C;
667
164
  struct isl_map *read_map;
668
164
  struct isl_map *write_map;
669
164
  struct isl_map *dep_map;
670
164
  struct isl_map *after_write;
671
164
  struct isl_map *before_read;
672
164
  struct isl_map *result;
673
164
674
164
  set_C = isl_map_range(isl_map_copy(old_map));
675
164
  read_map = isl_map_copy(acc->sink.map);
676
164
  write_map = isl_map_copy(acc->source[k].map);
677
164
678
164
  write_map = isl_map_reverse(write_map);
679
164
  dep_map = isl_map_apply_range(read_map, write_map);
680
164
  dim = space_align_and_join(isl_map_get_space(acc->source[k].map),
681
164
        isl_space_reverse(isl_map_get_space(acc->source[j].map)));
682
164
  after_write = after_at_level(dim, after_level);
683
164
  after_write = isl_map_apply_range(after_write, old_map);
684
164
  after_write = isl_map_reverse(after_write);
685
164
  dep_map = isl_map_intersect(dep_map, after_write);
686
164
  before_read = after_at_level(isl_map_get_space(dep_map), before_level);
687
164
  dep_map = isl_map_intersect(dep_map, before_read);
688
164
  result = restricted_partial_lexmax(acc, dep_map, k, set_C, empty);
689
164
  result = isl_map_reverse(result);
690
164
691
164
  return result;
692
164
}
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
60.3k
{
704
60.3k
  if (shared_level < target_level)
705
48.0k
    return 0;
706
12.2k
  
if (12.2k
(target_level % 2) && 12.2k
shared_level > target_level6.78k
)
707
4.87k
    return 0;
708
7.37k
  return 1;
709
60.3k
}
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
11.0k
{
729
11.0k
  int k, level;
730
11.0k
  int depth = 2 * isl_map_dim(acc->source[j].map, isl_dim_in) + 1;
731
11.0k
732
11.0k
  if (isl_map_plain_is_empty(temp_rel[j]))
733
9.02k
    return isl_stat_ok;
734
11.0k
735
3.46k
  
for (k = j - 1; 1.99k
k >= 03.46k
;
--k1.47k
)
{1.47k
736
1.47k
    int plevel, plevel2;
737
1.47k
    plevel = acc->level_before(acc->source[k].data, acc->sink.data);
738
1.47k
    if (plevel < 0)
739
0
      return isl_stat_error;
740
1.47k
    
if (1.47k
!can_precede_at_level(plevel, sink_level)1.47k
)
741
889
      continue;
742
1.47k
743
1.47k
    plevel2 = acc->level_before(acc->source[j].data,
744
583
            acc->source[k].data);
745
583
    if (plevel2 < 0)
746
0
      return isl_stat_error;
747
583
748
5.89k
    
for (level = sink_level; 583
level <= depth5.89k
;
++level5.31k
)
{5.31k
749
5.31k
      struct isl_map *T;
750
5.31k
      struct isl_set *trest;
751
5.31k
      struct isl_map *copy;
752
5.31k
753
5.31k
      if (!can_precede_at_level(plevel2, level))
754
5.15k
        continue;
755
5.31k
756
5.31k
      copy = isl_map_copy(temp_rel[j]);
757
164
      T = last_later_source(acc, copy, j, sink_level, k,
758
164
                level, &trest);
759
164
      if (
isl_map_plain_is_empty(T)164
)
{148
760
148
        isl_set_free(trest);
761
148
        isl_map_free(T);
762
148
        continue;
763
164
      }
764
164
      temp_rel[j] = isl_map_intersect_range(temp_rel[j], trest);
765
16
      temp_rel[k] = isl_map_union_disjoint(temp_rel[k], T);
766
583
    }
767
1.99k
  }
768
1.99k
769
1.99k
  return isl_stat_ok;
770
11.0k
}
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
1.24k
{
778
1.24k
  isl_map *read_map;
779
1.24k
  isl_map *write_map;
780
1.24k
  isl_map *dep_map;
781
1.24k
  isl_map *after;
782
1.24k
783
1.24k
  read_map = isl_map_copy(acc->sink.map);
784
1.24k
  read_map = isl_map_intersect_domain(read_map, set_C);
785
1.24k
  write_map = isl_map_copy(acc->source[acc->n_must + j].map);
786
1.24k
  write_map = isl_map_reverse(write_map);
787
1.24k
  dep_map = isl_map_apply_range(read_map, write_map);
788
1.24k
  after = after_at_level(isl_map_get_space(dep_map), level);
789
1.24k
  dep_map = isl_map_intersect(dep_map, after);
790
1.24k
791
1.24k
  return isl_map_reverse(dep_map);
792
1.24k
}
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
984
{
804
984
  isl_space *dim;
805
984
  isl_set *set_C;
806
984
  isl_map *read_map;
807
984
  isl_map *write_map;
808
984
  isl_map *dep_map;
809
984
  isl_map *after_write;
810
984
  isl_map *before_read;
811
984
812
984
  set_C = isl_map_range(isl_map_copy(old_map));
813
984
  read_map = isl_map_copy(acc->sink.map);
814
984
  read_map = isl_map_intersect_domain(read_map, set_C);
815
984
  write_map = isl_map_copy(acc->source[acc->n_must + j].map);
816
984
817
984
  write_map = isl_map_reverse(write_map);
818
984
  dep_map = isl_map_apply_range(read_map, write_map);
819
984
  dim = isl_space_join(isl_map_get_space(acc->source[acc->n_must + j].map),
820
984
        isl_space_reverse(isl_map_get_space(acc->source[k].map)));
821
984
  after_write = after_at_level(dim, after_level);
822
984
  after_write = isl_map_apply_range(after_write, old_map);
823
984
  after_write = isl_map_reverse(after_write);
824
984
  dep_map = isl_map_intersect(dep_map, after_write);
825
984
  before_read = after_at_level(isl_map_get_space(dep_map), before_level);
826
984
  dep_map = isl_map_intersect(dep_map, before_read);
827
984
  return isl_map_reverse(dep_map);
828
984
}
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
622
{
842
622
  int k, level;
843
622
  int depth = 2 * isl_map_dim(acc->source[acc->n_must + j].map,
844
622
          isl_dim_in) + 1;
845
622
846
1.43k
  for (k = 0; 
k < acc->n_must1.43k
;
++k816
)
{816
847
816
    int plevel;
848
816
849
816
    if (isl_map_plain_is_empty(may_rel[k]) &&
850
759
        isl_map_plain_is_empty(must_rel[k]))
851
538
      continue;
852
816
853
816
    plevel = acc->level_before(acc->source[k].data,
854
278
          acc->source[acc->n_must + j].data);
855
278
    if (plevel < 0)
856
0
      return isl_map_free(map);
857
278
858
1.81k
    
for (level = sink_level; 278
level <= depth1.81k
;
++level1.53k
)
{1.53k
859
1.53k
      isl_map *T;
860
1.53k
      isl_map *copy;
861
1.53k
      isl_set *ran;
862
1.53k
863
1.53k
      if (!can_precede_at_level(plevel, level))
864
1.04k
        continue;
865
1.53k
866
1.53k
      copy = isl_map_copy(may_rel[k]);
867
492
      T = all_later_sources(acc, copy, j, sink_level, k, level);
868
492
      map = isl_map_union(map, T);
869
492
870
492
      copy = isl_map_copy(must_rel[k]);
871
492
      T = all_later_sources(acc, copy, j, sink_level, k, level);
872
492
      ran = isl_map_range(isl_map_copy(T));
873
492
      map = isl_map_union(map, T);
874
492
      may_rel[k] = isl_map_union_disjoint(may_rel[k],
875
492
          isl_map_intersect_range(isl_map_copy(must_rel[k]),
876
492
                isl_set_copy(ran)));
877
492
      T = isl_map_from_domain_and_range(
878
492
          isl_set_universe(
879
492
        isl_space_domain(isl_map_get_space(must_rel[k]))),
880
492
          ran);
881
492
      must_rel[k] = isl_map_subtract(must_rel[k], T);
882
492
    }
883
622
  }
884
622
885
622
  return map;
886
622
}
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
48
{
911
48
  isl_space *space;
912
48
  isl_set *set_C;
913
48
  isl_map *read_map;
914
48
  isl_map *write_map;
915
48
  isl_map *dep_map;
916
48
  isl_map *equal;
917
48
  isl_map *map;
918
48
919
48
  if (depth < 0)
920
0
    return NULL;
921
48
922
48
  set_C = isl_map_range(isl_map_copy(old_map));
923
48
  read_map = isl_map_copy(acc->sink.map);
924
48
  read_map = isl_map_intersect_domain(read_map, set_C);
925
48
  write_map = isl_map_copy(acc->source[pos].map);
926
48
  dep_map = isl_map_domain_product(write_map, read_map);
927
48
  dep_map = isl_set_unwrap(isl_map_domain(dep_map));
928
48
  space = isl_space_join(isl_map_get_space(old_map),
929
48
        isl_space_reverse(isl_map_get_space(dep_map)));
930
48
  equal = isl_map_from_basic_map(isl_basic_map_equal(space, depth));
931
48
  map = isl_map_range_product(equal, isl_map_copy(old_map));
932
48
  map = isl_map_uncurry(map);
933
48
  map = isl_map_intersect_domain_factor_range(map, dep_map);
934
48
935
48
  return map;
936
48
}
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
26.2k
{
977
26.2k
  int i, j;
978
26.2k
979
26.2k
  if (!acc->coscheduled)
980
30
    return flow;
981
73.9k
  
for (i = acc->n_must - 1; 26.1k
i >= 073.9k
;
--i47.7k
)
{47.7k
982
47.7k
    isl_map *move;
983
47.7k
984
47.7k
    if (isl_map_plain_is_empty(must_rel[i]))
985
45.8k
      continue;
986
47.7k
    move = isl_map_empty(isl_map_get_space(must_rel[i]));
987
3.37k
    for (j = i - 1; 
j >= 03.37k
;
--j1.45k
)
{1.45k
988
1.45k
      int depth;
989
1.45k
      isl_map *map, *factor;
990
1.45k
991
1.45k
      if (!acc->coscheduled(acc->source[i].data,
992
1.45k
            acc->source[j].data))
993
1.45k
        continue;
994
1.45k
      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
1.92k
    }
1002
2.22k
    for (j = 0; 
j < acc->n_may2.22k
;
++j293
)
{293
1003
293
      int depth, pos;
1004
293
      isl_map *map, *factor;
1005
293
1006
293
      pos = acc->n_must + j;
1007
293
      if (!acc->coscheduled(acc->source[i].data,
1008
293
            acc->source[pos].data))
1009
245
        continue;
1010
293
      depth = acc->level_before(acc->source[i].data,
1011
48
            acc->source[pos].data) / 2;
1012
48
      map = coscheduled_source(acc, must_rel[i], pos, depth);
1013
48
      factor = isl_map_domain_factor_range(isl_map_copy(map));
1014
48
      pos = 2 * acc->n_must + j;
1015
48
      flow->dep[pos].map = isl_map_union(flow->dep[pos].map,
1016
48
                  factor);
1017
48
      map = isl_map_domain_factor_domain(map);
1018
48
      move = isl_map_union(move, map);
1019
1.92k
    }
1020
1.92k
    must_rel[i] = isl_map_subtract(must_rel[i], isl_map_copy(move));
1021
1.92k
    may_rel[i] = isl_map_union(may_rel[i], move);
1022
26.1k
  }
1023
26.1k
1024
26.2k
  return flow;
1025
26.2k
}
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
302
{
1035
302
  int i;
1036
302
  isl_set *mustdo;
1037
302
  isl_set *maydo;
1038
302
  isl_flow *res;
1039
302
1040
302
  res = isl_flow_alloc(acc);
1041
302
  if (!res)
1042
0
    return NULL;
1043
302
1044
302
  mustdo = isl_map_domain(isl_map_copy(acc->sink.map));
1045
302
  maydo = isl_set_copy(mustdo);
1046
302
1047
382
  for (i = 0; 
i < acc->n_may382
;
++i80
)
{80
1048
80
    int plevel;
1049
80
    int is_before;
1050
80
    isl_space *dim;
1051
80
    isl_map *before;
1052
80
    isl_map *dep;
1053
80
1054
80
    plevel = acc->level_before(acc->source[i].data, acc->sink.data);
1055
80
    if (plevel < 0)
1056
0
      goto error;
1057
80
1058
80
    is_before = plevel & 1;
1059
80
    plevel >>= 1;
1060
80
1061
80
    dim = isl_map_get_space(res->dep[i].map);
1062
80
    if (is_before)
1063
10
      before = isl_map_lex_le_first(dim, plevel);
1064
80
    else
1065
70
      before = isl_map_lex_lt_first(dim, plevel);
1066
80
    dep = isl_map_apply_range(isl_map_copy(acc->source[i].map),
1067
80
      isl_map_reverse(isl_map_copy(acc->sink.map)));
1068
80
    dep = isl_map_intersect(dep, before);
1069
80
    mustdo = isl_set_subtract(mustdo,
1070
80
              isl_map_range(isl_map_copy(dep)));
1071
80
    res->dep[i].map = isl_map_union(res->dep[i].map, dep);
1072
302
  }
1073
302
1074
302
  res->may_no_source = isl_set_subtract(maydo, isl_set_copy(mustdo));
1075
302
  res->must_no_source = mustdo;
1076
302
1077
302
  return res;
1078
302
error:
1079
0
  isl_set_free(mustdo);
1080
0
  isl_set_free(maydo);
1081
0
  isl_flow_free(res);
1082
302
  return NULL;
1083
302
}
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
3.25k
{
1128
3.25k
  isl_ctx *ctx;
1129
3.25k
  isl_flow *res;
1130
3.25k
  isl_set *mustdo = NULL;
1131
3.25k
  isl_set *maydo = NULL;
1132
3.25k
  int level, j;
1133
3.25k
  int depth;
1134
3.25k
  isl_map **must_rel = NULL;
1135
3.25k
  isl_map **may_rel = NULL;
1136
3.25k
1137
3.25k
  if (!acc)
1138
0
    return NULL;
1139
3.25k
1140
3.25k
  res = isl_flow_alloc(acc);
1141
3.25k
  if (!res)
1142
0
    goto error;
1143
3.25k
  ctx = isl_map_get_ctx(acc->sink.map);
1144
3.25k
1145
3.25k
  depth = 2 * isl_map_dim(acc->sink.map, isl_dim_in) + 1;
1146
3.25k
  mustdo = isl_map_domain(isl_map_copy(acc->sink.map));
1147
3.25k
  maydo = isl_set_empty(isl_set_get_space(mustdo));
1148
3.25k
  if (
!mustdo || 3.25k
!maydo3.25k
)
1149
0
    goto error;
1150
3.25k
  
if (3.25k
isl_set_plain_is_empty(mustdo)3.25k
)
1151
0
    goto done;
1152
3.25k
1153
3.25k
  
must_rel = 3.25k
isl_calloc_array3.25k
(ctx, struct isl_map *, acc->n_must);
1154
3.25k
  may_rel = isl_calloc_array(ctx, struct isl_map *, acc->n_must);
1155
3.25k
  if (
!must_rel || 3.25k
!may_rel3.25k
)
1156
0
    goto error;
1157
3.25k
1158
28.9k
  
for (level = depth; 3.25k
level >= 128.9k
;
--level25.7k
)
{26.2k
1159
74.0k
    for (j = acc->n_must-1; 
j >=074.0k
;
--j47.8k
)
{47.8k
1160
47.8k
      isl_space *space;
1161
47.8k
      space = isl_map_get_space(res->dep[2 * j].map);
1162
47.8k
      must_rel[j] = isl_map_empty(space);
1163
47.8k
      may_rel[j] = isl_map_copy(must_rel[j]);
1164
47.8k
    }
1165
26.2k
1166
73.1k
    for (j = acc->n_must - 1; 
j >= 073.1k
;
--j46.9k
)
{47.4k
1167
47.4k
      struct isl_map *T;
1168
47.4k
      struct isl_set *rest;
1169
47.4k
      int plevel;
1170
47.4k
1171
47.4k
      plevel = acc->level_before(acc->source[j].data,
1172
47.4k
                 acc->sink.data);
1173
47.4k
      if (plevel < 0)
1174
0
        goto error;
1175
47.4k
      
if (47.4k
!can_precede_at_level(plevel, level)47.4k
)
1176
42.3k
        continue;
1177
47.4k
1178
47.4k
      T = last_source(acc, mustdo, j, level, &rest);
1179
5.13k
      must_rel[j] = isl_map_union_disjoint(must_rel[j], T);
1180
5.13k
      mustdo = rest;
1181
5.13k
1182
5.13k
      if (intermediate_sources(acc, must_rel, j, level) < 0)
1183
0
        goto error;
1184
5.13k
1185
5.13k
      T = last_source(acc, maydo, j, level, &rest);
1186
5.13k
      may_rel[j] = isl_map_union_disjoint(may_rel[j], T);
1187
5.13k
      maydo = rest;
1188
5.13k
1189
5.13k
      if (intermediate_sources(acc, may_rel, j, level) < 0)
1190
0
        goto error;
1191
5.13k
1192
5.13k
      
if (5.13k
isl_set_plain_is_empty(mustdo) &&5.13k
1193
521
          isl_set_plain_is_empty(maydo))
1194
473
        break;
1195
26.2k
    }
1196
26.5k
    
for (j = j - 1; 26.2k
j >= 026.5k
;
--j372
)
{372
1197
372
      int plevel;
1198
372
1199
372
      plevel = acc->level_before(acc->source[j].data,
1200
372
                 acc->sink.data);
1201
372
      if (plevel < 0)
1202
0
        goto error;
1203
372
      
if (372
!can_precede_at_level(plevel, level)372
)
1204
1
        continue;
1205
372
1206
371
      
if (371
intermediate_sources(acc, must_rel, j, level) < 0371
)
1207
0
        goto error;
1208
371
      
if (371
intermediate_sources(acc, may_rel, j, level) < 0371
)
1209
0
        goto error;
1210
26.2k
    }
1211
26.2k
1212
26.2k
    handle_coscheduled(acc, must_rel, may_rel, res);
1213
26.2k
1214
30.3k
    for (j = 0; 
j < acc->n_may30.3k
;
++j4.17k
)
{4.17k
1215
4.17k
      int plevel;
1216
4.17k
      isl_map *T;
1217
4.17k
      isl_set *ran;
1218
4.17k
1219
4.17k
      plevel = acc->level_before(acc->source[acc->n_must + j].data,
1220
4.17k
                 acc->sink.data);
1221
4.17k
      if (plevel < 0)
1222
0
        goto error;
1223
4.17k
      
if (4.17k
!can_precede_at_level(plevel, level)4.17k
)
1224
3.55k
        continue;
1225
4.17k
1226
4.17k
      T = all_sources(acc, isl_set_copy(maydo), j, level);
1227
622
      res->dep[2 * acc->n_must + j].map =
1228
622
          isl_map_union(res->dep[2 * acc->n_must + j].map, T);
1229
622
      T = all_sources(acc, isl_set_copy(mustdo), j, level);
1230
622
      ran = isl_map_range(isl_map_copy(T));
1231
622
      res->dep[2 * acc->n_must + j].map =
1232
622
          isl_map_union(res->dep[2 * acc->n_must + j].map, T);
1233
622
      mustdo = isl_set_subtract(mustdo, isl_set_copy(ran));
1234
622
      maydo = isl_set_union_disjoint(maydo, ran);
1235
622
1236
622
      T = res->dep[2 * acc->n_must + j].map;
1237
622
      T = all_intermediate_sources(acc, T, must_rel, may_rel,
1238
622
              j, level);
1239
622
      res->dep[2 * acc->n_must + j].map = T;
1240
26.2k
    }
1241
26.2k
1242
74.0k
    
for (j = acc->n_must - 1; 26.2k
j >= 074.0k
;
--j47.8k
)
{47.8k
1243
47.8k
      res->dep[2 * j].map =
1244
47.8k
        isl_map_union_disjoint(res->dep[2 * j].map,
1245
47.8k
                   must_rel[j]);
1246
47.8k
      res->dep[2 * j + 1].map =
1247
47.8k
        isl_map_union_disjoint(res->dep[2 * j + 1].map,
1248
47.8k
                   may_rel[j]);
1249
47.8k
    }
1250
26.2k
1251
26.2k
    if (isl_set_plain_is_empty(mustdo) &&
1252
611
        isl_set_plain_is_empty(maydo))
1253
473
      break;
1254
26.2k
  }
1255
3.25k
1256
3.25k
  free(must_rel);
1257
3.25k
  free(may_rel);
1258
3.25k
done:
1259
3.25k
  res->must_no_source = mustdo;
1260
3.25k
  res->may_no_source = maydo;
1261
3.25k
  return res;
1262
3.25k
error:
1263
0
  if (must_rel)
1264
0
    
for (j = 0; 0
j < acc->n_must0
;
++j0
)
1265
0
      isl_map_free(must_rel[j]);
1266
0
  if (may_rel)
1267
0
    
for (j = 0; 0
j < acc->n_must0
;
++j0
)
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
3.25k
  return NULL;
1275
3.25k
}
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
3.55k
{
1297
3.55k
  struct isl_flow *res = NULL;
1298
3.55k
1299
3.55k
  if (!acc)
1300
0
    return NULL;
1301
3.55k
1302
3.55k
  acc->sink.map = isl_map_range_map(acc->sink.map);
1303
3.55k
  if (!acc->sink.map)
1304
0
    goto error;
1305
3.55k
1306
3.55k
  
if (3.55k
acc->n_must == 03.55k
)
1307
302
    res = compute_mem_based_dependences(acc);
1308
3.55k
  else {
1309
3.25k
    acc = isl_access_info_sort_sources(acc);
1310
3.25k
    res = compute_val_based_dependences(acc);
1311
3.55k
  }
1312
3.55k
  acc = isl_access_info_free(acc);
1313
3.55k
  if (!res)
1314
0
    return NULL;
1315
3.55k
  
if (3.55k
!res->must_no_source || 3.55k
!res->may_no_source3.55k
)
1316
0
    goto error;
1317
3.55k
  return res;
1318
3.55k
error:
1319
0
  isl_access_info_free(acc);
1320
0
  isl_flow_free(res);
1321
3.55k
  return NULL;
1322
3.55k
}
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
6
{
1343
6
  int j;
1344
6
  struct isl_flow *res;
1345
6
1346
6
  if (!acc)
1347
0
    return NULL;
1348
6
1349
6
  acc->domain_map = isl_map_domain_map(isl_map_copy(acc->sink.map));
1350
6
  res = access_info_compute_flow_core(acc);
1351
6
  if (!res)
1352
0
    return NULL;
1353
6
1354
21
  
for (j = 0; 6
j < res->n_source21
;
++j15
)
{15
1355
15
    res->dep[j].map = isl_map_range_factor_domain(res->dep[j].map);
1356
15
    if (!res->dep[j].map)
1357
0
      goto error;
1358
15
  }
1359
6
1360
6
  return res;
1361
6
error:
1362
0
  isl_flow_free(res);
1363
6
  return NULL;
1364
6
}
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
400
{
1378
400
  if (!info)
1379
0
    return;
1380
400
  isl_vec_free(info->cst);
1381
400
  free(info->is_cst);
1382
400
  free(info);
1383
400
}
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
400
{
1395
400
  isl_ctx *ctx;
1396
400
  isl_space *dim;
1397
400
  struct isl_sched_info *info;
1398
400
  int i, n;
1399
400
1400
400
  if (!map)
1401
0
    return NULL;
1402
400
1403
400
  dim = isl_space_unwrap(isl_space_domain(isl_map_get_space(map)));
1404
400
  if (!dim)
1405
0
    return NULL;
1406
400
  n = isl_space_dim(dim, isl_dim_in);
1407
400
  isl_space_free(dim);
1408
400
1409
400
  ctx = isl_map_get_ctx(map);
1410
400
  info = isl_alloc_type(ctx, struct isl_sched_info);
1411
400
  if (!info)
1412
0
    return NULL;
1413
400
  
info->is_cst = 400
isl_alloc_array400
(ctx, int, n);
1414
400
  info->cst = isl_vec_alloc(ctx, n);
1415
400
  if (
n && 400
(!info->is_cst || 400
!info->cst400
))
1416
0
    goto error;
1417
400
1418
1.68k
  
for (i = 0; 400
i < n1.68k
;
++i1.28k
)
{1.28k
1419
1.28k
    isl_val *v;
1420
1.28k
1421
1.28k
    v = isl_map_plain_get_val_if_fixed(map, isl_dim_in, i);
1422
1.28k
    if (!v)
1423
0
      goto error;
1424
1.28k
    info->is_cst[i] = !isl_val_is_nan(v);
1425
1.28k
    if (info->is_cst[i])
1426
797
      info->cst = isl_vec_set_element_val(info->cst, i, v);
1427
1.28k
    else
1428
487
      isl_val_free(v);
1429
1.28k
  }
1430
400
1431
400
  return info;
1432
400
error:
1433
0
  sched_info_free(info);
1434
400
  return NULL;
1435
400
}
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
2.39k
{
1482
2.39k
  enum isl_access_type i;
1483
2.39k
1484
2.39k
  if (!access)
1485
75
    return NULL;
1486
2.39k
1487
11.5k
  
for (i = isl_access_sink; 2.31k
i < isl_access_end11.5k
;
++i9.26k
)
1488
9.26k
    isl_union_map_free(access->access[i]);
1489
2.31k
  isl_schedule_free(access->schedule);
1490
2.31k
  isl_union_map_free(access->schedule_map);
1491
2.31k
  free(access);
1492
2.31k
1493
2.39k
  return NULL;
1494
2.39k
}
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
2.23k
{
1500
2.23k
  if (!access)
1501
0
    return NULL;
1502
2.23k
  return isl_union_map_get_ctx(access->access[isl_access_sink]);
1503
2.23k
}
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
2.32k
{
1513
2.32k
  return isl_calloc_type(ctx, isl_union_access_info);
1514
2.32k
}
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
2.31k
{
1526
2.31k
  isl_space *space;
1527
2.31k
  isl_union_map *empty;
1528
2.31k
  enum isl_access_type i;
1529
2.31k
1530
2.31k
  if (!info)
1531
0
    return NULL;
1532
2.31k
  
if (2.31k
!info->access[isl_access_sink]2.31k
)
1533
0
    return isl_union_access_info_free(info);
1534
2.31k
1535
2.31k
  space = isl_union_map_get_space(info->access[isl_access_sink]);
1536
2.31k
  empty = isl_union_map_empty(isl_space_copy(space));
1537
9.26k
  for (i = isl_access_sink + 1; 
i < isl_access_end9.26k
;
++i6.94k
)
1538
6.94k
    
if (6.94k
!info->access[i]6.94k
)
1539
6.94k
      info->access[i] = isl_union_map_copy(empty);
1540
2.31k
  isl_union_map_free(empty);
1541
2.31k
  if (
!info->schedule && 2.31k
!info->schedule_map2.31k
)
1542
2.31k
    info->schedule = isl_schedule_empty(isl_space_copy(space));
1543
2.31k
  isl_space_free(space);
1544
2.31k
1545
9.26k
  for (i = isl_access_sink + 1; 
i < isl_access_end9.26k
;
++i6.94k
)
1546
6.94k
    
if (6.94k
!info->access[i]6.94k
)
1547
0
      return isl_union_access_info_free(info);
1548
2.31k
  
if (2.31k
!info->schedule && 2.31k
!info->schedule_map0
)
1549
0
    return isl_union_access_info_free(info);
1550
2.31k
1551
2.31k
  return info;
1552
2.31k
}
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
2.33k
{
1560
2.33k
  isl_ctx *ctx;
1561
2.33k
  isl_union_access_info *access;
1562
2.33k
1563
2.33k
  if (!sink)
1564
15
    return NULL;
1565
2.33k
  ctx = isl_union_map_get_ctx(sink);
1566
2.32k
  access = isl_union_access_info_alloc(ctx);
1567
2.32k
  if (!access)
1568
5
    goto error;
1569
2.32k
  access->access[isl_access_sink] = sink;
1570
2.32k
  return isl_union_access_info_init(access);
1571
2.32k
error:
1572
5
  isl_union_map_free(sink);
1573
2.32k
  return NULL;
1574
2.33k
}
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
6.96k
{
1582
6.96k
  if (
!info || 6.96k
!access6.92k
)
1583
35
    goto error;
1584
6.96k
1585
6.96k
  isl_union_map_free(info->access[type]);
1586
6.92k
  info->access[type] = access;
1587
6.92k
1588
6.96k
  return info;
1589
6.96k
error:
1590
35
  isl_union_access_info_free(info);
1591
35
  isl_union_map_free(access);
1592
6.96k
  return NULL;
1593
6.96k
}
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
4.62k
{
1601
4.62k
  return isl_union_access_info_set(access, isl_access_must_source,
1602
4.62k
          must_source);
1603
4.62k
}
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
2.33k
{
1611
2.33k
  return isl_union_access_info_set(access, isl_access_may_source,
1612
2.33k
          may_source);
1613
2.33k
}
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
4.63k
{
1628
4.63k
  if (!info)
1629
0
    return NULL;
1630
4.63k
  return isl_union_map_copy(info->access[type]);
1631
4.63k
}
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
2.31k
{
1638
2.31k
  return isl_union_access_info_get(info, isl_access_must_source);
1639
2.31k
}
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
2.31k
{
1654
2.31k
  return isl_union_access_info_get(info, isl_access_kill);
1655
2.31k
}
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
2.33k
{
1662
2.33k
  isl_bool empty;
1663
2.33k
1664
2.33k
  if (!info)
1665
20
    return isl_bool_error;
1666
2.33k
  empty = isl_union_map_is_empty(info->access[isl_access_kill]);
1667
2.33k
  return isl_bool_not(empty);
1668
2.33k
}
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
2.25k
{
1677
2.25k
  if (
!access || 2.25k
!schedule2.23k
)
1678
20
    goto error;
1679
2.25k
1680
2.25k
  access->schedule_map = isl_union_map_free(access->schedule_map);
1681
2.23k
  isl_schedule_free(access->schedule);
1682
2.23k
  access->schedule = schedule;
1683
2.23k
1684
2.25k
  return access;
1685
2.25k
error:
1686
20
  isl_union_access_info_free(access);
1687
20
  isl_schedule_free(schedule);
1688
2.25k
  return NULL;
1689
2.25k
}
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
81
{
1698
81
  if (
!access || 81
!schedule_map81
)
1699
0
    goto error;
1700
81
1701
81
  isl_union_map_free(access->schedule_map);
1702
81
  access->schedule = isl_schedule_free(access->schedule);
1703
81
  access->schedule_map = schedule_map;
1704
81
1705
81
  return access;
1706
81
error:
1707
0
  isl_union_access_info_free(access);
1708
0
  isl_union_map_free(schedule_map);
1709
81
  return NULL;
1710
81
}
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_end0
;
++i0
)
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_sink0
)
{0
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 (0
empty0
)
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_end0
;
++i0
)
1813
0
    p = print_access_field(p, access, i);
1814
0
  if (
access->schedule0
)
{0
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)) > 00
)
{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 (0
more < 00
)
1925
0
    return isl_union_access_info_free(info);
1926
0
1927
0
  
if (0
isl_stream_yaml_read_end_mapping(s) < 00
)
{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 (0
!sink_set0
)
{0
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 (0
!schedule_set0
)
{0
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
81
{
1969
81
  isl_space *space;
1970
81
  enum isl_access_type i;
1971
81
1972
81
  if (!access)
1973
0
    return NULL;
1974
81
1975
81
  space = isl_union_map_get_space(access->access[isl_access_sink]);
1976
324
  for (i = isl_access_sink + 1; 
i < isl_access_end324
;
++i243
)
1977
243
    space = isl_space_align_params(space,
1978
243
        isl_union_map_get_space(access->access[i]));
1979
81
  if (access->schedule_map)
1980
81
    space = isl_space_align_params(space,
1981
81
        isl_union_map_get_space(access->schedule_map));
1982
405
  for (i = isl_access_sink; 
i < isl_access_end405
;
++i324
)
1983
324
    access->access[i] =
1984
324
      isl_union_map_align_params(access->access[i],
1985
324
              isl_space_copy(space));
1986
81
  if (
!access->schedule_map81
)
{0
1987
0
    isl_space_free(space);
1988
81
  } else {
1989
81
    access->schedule_map =
1990
81
        isl_union_map_align_params(access->schedule_map, space);
1991
81
    if (!access->schedule_map)
1992
0
      return isl_union_access_info_free(access);
1993
81
  }
1994
81
1995
405
  
for (i = isl_access_sink; 81
i < isl_access_end405
;
++i324
)
1996
324
    
if (324
!access->access[i]324
)
1997
0
      return isl_union_access_info_free(access);
1998
81
1999
81
  return access;
2000
81
}
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
81
{
2028
81
  isl_union_map *sm;
2029
81
  enum isl_access_type i;
2030
81
2031
81
  if (!access)
2032
0
    return NULL;
2033
81
2034
81
  sm = isl_union_map_reverse(access->schedule_map);
2035
81
  sm = isl_union_map_range_map(sm);
2036
405
  for (i = isl_access_sink; 
i < isl_access_end405
;
++i324
)
2037
324
    access->access[i] =
2038
324
      isl_union_map_apply_range(isl_union_map_copy(sm),
2039
324
            access->access[i]);
2040
81
  access->schedule_map = sm;
2041
81
2042
405
  for (i = isl_access_sink; 
i < isl_access_end405
;
++i324
)
2043
324
    
if (324
!access->access[i]324
)
2044
0
      return isl_union_access_info_free(access);
2045
81
  
if (81
!access->schedule_map81
)
2046
0
    return isl_union_access_info_free(access);
2047
81
2048
81
  return access;
2049
81
}
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
2.33k
{
2083
2.33k
  if (!flow)
2084
20
    return NULL;
2085
2.33k
  isl_union_map_free(flow->must_dep);
2086
2.31k
  isl_union_map_free(flow->may_dep);
2087
2.31k
  isl_union_map_free(flow->must_no_source);
2088
2.31k
  isl_union_map_free(flow->may_no_source);
2089
2.31k
  free(flow);
2090
2.33k
  return NULL;
2091
2.33k
}
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
557
{
2124
557
  if (!flow)
2125
5
    return NULL;
2126
557
  return isl_union_map_union(isl_union_map_copy(flow->must_dep),
2127
557
            isl_union_map_copy(flow->may_dep));
2128
557
}
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
646
{
2135
646
  isl_union_map *dep;
2136
646
2137
646
  if (!flow)
2138
5
    return NULL;
2139
646
  dep = isl_union_map_copy(flow->must_dep);
2140
646
  return isl_union_map_range_factor_domain(dep);
2141
646
}
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
1.13k
{
2149
1.13k
  isl_union_map *dep;
2150
1.13k
2151
1.13k
  if (!flow)
2152
10
    return NULL;
2153
1.13k
  dep = isl_union_map_union(isl_union_map_copy(flow->must_dep),
2154
1.12k
            isl_union_map_copy(flow->may_dep));
2155
1.13k
  return isl_union_map_range_factor_domain(dep);
2156
1.13k
}
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
41
{
2163
41
  if (!flow)
2164
0
    return NULL;
2165
41
  return isl_union_map_copy(flow->may_dep);
2166
41
}
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
2.31k
{
2209
2.31k
  isl_ctx *ctx;
2210
2.31k
  isl_union_map *empty;
2211
2.31k
  isl_union_flow *flow;
2212
2.31k
2213
2.31k
  if (!space)
2214
0
    return NULL;
2215
2.31k
  ctx = isl_space_get_ctx(space);
2216
2.31k
  flow = isl_alloc_type(ctx, isl_union_flow);
2217
2.31k
  if (!flow)
2218
0
    goto error;
2219
2.31k
2220
2.31k
  empty = isl_union_map_empty(space);
2221
2.31k
  flow->must_dep = isl_union_map_copy(empty);
2222
2.31k
  flow->may_dep = isl_union_map_copy(empty);
2223
2.31k
  flow->must_no_source = isl_union_map_copy(empty);
2224
2.31k
  flow->may_no_source = empty;
2225
2.31k
2226
2.31k
  if (
!flow->must_dep || 2.31k
!flow->may_dep2.31k
||
2227
2.31k
      
!flow->must_no_source2.31k
||
!flow->may_no_source2.31k
)
2228
0
    return isl_union_flow_free(flow);
2229
2.31k
2230
2.31k
  return flow;
2231
2.31k
error:
2232
0
  isl_space_free(space);
2233
2.31k
  return NULL;
2234
2.31k
}
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 || 0
!copy->may_dep0
||
2260
0
      
!copy->must_no_source0
||
!copy->may_no_source0
)
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
81
{
2289
81
  if (!flow)
2290
0
    return NULL;
2291
81
2292
81
  flow->must_dep = isl_union_map_range_curry(flow->must_dep);
2293
81
  flow->must_dep = isl_union_map_factor_range(flow->must_dep);
2294
81
  flow->may_dep = isl_union_map_range_curry(flow->may_dep);
2295
81
  flow->may_dep = isl_union_map_factor_range(flow->may_dep);
2296
81
  flow->must_no_source =
2297
81
    isl_union_map_domain_factor_range(flow->must_no_source);
2298
81
  flow->may_no_source =
2299
81
    isl_union_map_domain_factor_range(flow->may_no_source);
2300
81
2301
81
  if (
!flow->must_dep || 81
!flow->may_dep81
||
2302
81
      
!flow->must_no_source81
||
!flow->may_no_source81
)
2303
0
    return isl_union_flow_free(flow);
2304
81
2305
81
  return flow;
2306
81
}
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
380
{
2323
380
  int eq;
2324
380
  isl_space *dim;
2325
380
  struct isl_compute_flow_data *data;
2326
380
2327
380
  data = (struct isl_compute_flow_data *)user;
2328
380
2329
380
  dim = isl_space_range(isl_map_get_space(map));
2330
380
2331
380
  eq = isl_space_is_equal(dim, data->dim);
2332
380
2333
380
  isl_space_free(dim);
2334
380
  isl_map_free(map);
2335
380
2336
380
  if (eq < 0)
2337
0
    return isl_stat_error;
2338
380
  
if (380
eq380
)
2339
274
    data->count++;
2340
380
2341
380
  return isl_stat_ok;
2342
380
}
2343
2344
static isl_stat collect_matching_array(__isl_take isl_map *map, void *user)
2345
380
{
2346
380
  int eq;
2347
380
  isl_space *dim;
2348
380
  struct isl_sched_info *info;
2349
380
  struct isl_compute_flow_data *data;
2350
380
2351
380
  data = (struct isl_compute_flow_data *)user;
2352
380
2353
380
  dim = isl_space_range(isl_map_get_space(map));
2354
380
2355
380
  eq = isl_space_is_equal(dim, data->dim);
2356
380
2357
380
  isl_space_free(dim);
2358
380
2359
380
  if (eq < 0)
2360
0
    goto error;
2361
380
  
if (380
!eq380
)
{106
2362
106
    isl_map_free(map);
2363
106
    return isl_stat_ok;
2364
380
  }
2365
380
2366
380
  info = sched_info_alloc(map);
2367
274
  data->source_info[data->count] = info;
2368
274
2369
274
  data->accesses = isl_access_info_add_source(data->accesses,
2370
274
                map, data->must, info);
2371
274
2372
274
  data->count++;
2373
274
2374
380
  return isl_stat_ok;
2375
380
error:
2376
0
  isl_map_free(map);
2377
380
  return isl_stat_error;
2378
380
}
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
3.60k
{
2394
3.60k
  struct isl_sched_info *info1 = first;
2395
3.60k
  struct isl_sched_info *info2 = second;
2396
3.60k
  int n1, n2;
2397
3.60k
  int i;
2398
3.60k
2399
3.60k
  n1 = isl_vec_size(info1->cst);
2400
3.60k
  n2 = isl_vec_size(info2->cst);
2401
3.60k
2402
3.60k
  if (n2 < n1)
2403
160
    n1 = n2;
2404
3.60k
2405
10.5k
  for (i = 0; 
i < n110.5k
;
++i6.97k
)
{8.95k
2406
8.95k
    int r;
2407
8.95k
    int cmp;
2408
8.95k
2409
8.95k
    if (!info1->is_cst[i])
2410
3.12k
      continue;
2411
5.83k
    
if (5.83k
!info2->is_cst[i]5.83k
)
2412
0
      continue;
2413
5.83k
    cmp = isl_vec_cmp_element(info1->cst, info2->cst, i);
2414
5.83k
    if (cmp == 0)
2415
3.84k
      continue;
2416
5.83k
2417
5.83k
    r = 2 * i + (cmp < 0);
2418
1.98k
2419
5.83k
    return r;
2420
5.83k
  }
2421
3.60k
2422
1.61k
  return 2 * n1;
2423
3.60k
}
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
44
{
2433
44
  struct isl_sched_info *info1 = first;
2434
44
  struct isl_sched_info *info2 = second;
2435
44
  int n1, n2;
2436
44
  int i;
2437
44
2438
44
  n1 = isl_vec_size(info1->cst);
2439
44
  n2 = isl_vec_size(info2->cst);
2440
44
2441
44
  if (n2 < n1)
2442
8
    n1 = n2;
2443
44
2444
80
  for (i = 0; 
i < n180
;
++i36
)
{76
2445
76
    int cmp;
2446
76
2447
76
    if (!info1->is_cst[i])
2448
18
      continue;
2449
58
    
if (58
!info2->is_cst[i]58
)
2450
0
      continue;
2451
58
    cmp = isl_vec_cmp_element(info1->cst, info2->cst, i);
2452
58
    if (cmp != 0)
2453
40
      return 0;
2454
58
  }
2455
44
2456
4
  return 1;
2457
44
}
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
126
{
2465
126
  int i;
2466
126
  isl_ctx *ctx;
2467
126
  struct isl_compute_flow_data *data;
2468
126
  isl_flow *flow;
2469
126
  isl_union_flow *df;
2470
126
2471
126
  data = (struct isl_compute_flow_data *)user;
2472
126
  df = data->flow;
2473
126
2474
126
  ctx = isl_map_get_ctx(map);
2475
126
2476
126
  data->accesses = NULL;
2477
126
  data->sink_info = NULL;
2478
126
  data->source_info = NULL;
2479
126
  data->count = 0;
2480
126
  data->dim = isl_space_range(isl_map_get_space(map));
2481
126
2482
126
  if (isl_union_map_foreach_map(data->must_source,
2483
126
          &count_matching_array, data) < 0)
2484
0
    goto error;
2485
126
  
if (126
isl_union_map_foreach_map(data->may_source,126
2486
126
          &count_matching_array, data) < 0)
2487
0
    goto error;
2488
126
2489
126
  data->sink_info = sched_info_alloc(map);
2490
126
  data->source_info = isl_calloc_array(ctx, struct isl_sched_info *,
2491
126
               data->count);
2492
126
2493
126
  data->accesses = isl_access_info_alloc(isl_map_copy(map),
2494
126
        data->sink_info, &before, data->count);
2495
126
  if (
!data->sink_info || 126
(data->count && 126
!data->source_info122
) ||
2496
126
      !data->accesses)
2497
0
    goto error;
2498
126
  data->accesses->coscheduled = &coscheduled;
2499
126
  data->count = 0;
2500
126
  data->must = 1;
2501
126
  if (isl_union_map_foreach_map(data->must_source,
2502
126
          &collect_matching_array, data) < 0)
2503
0
    goto error;
2504
126
  data->must = 0;
2505
126
  if (isl_union_map_foreach_map(data->may_source,
2506
126
          &collect_matching_array, data) < 0)
2507
0
    goto error;
2508
126
2509
126
  flow = access_info_compute_flow_core(data->accesses);
2510
126
  data->accesses = NULL;
2511
126
2512
126
  if (!flow)
2513
0
    goto error;
2514
126
2515
126
  df->must_no_source = isl_union_map_union(df->must_no_source,
2516
126
        isl_union_map_from_map(isl_flow_get_no_source(flow, 1)));
2517
126
  df->may_no_source = isl_union_map_union(df->may_no_source,
2518
126
        isl_union_map_from_map(isl_flow_get_no_source(flow, 0)));
2519
126
2520
598
  for (i = 0; 
i < flow->n_source598
;
++i472
)
{472
2521
472
    isl_union_map *dep;
2522
472
    dep = isl_union_map_from_map(isl_map_copy(flow->dep[i].map));
2523
472
    if (flow->dep[i].must)
2524
198
      df->must_dep = isl_union_map_union(df->must_dep, dep);
2525
472
    else
2526
274
      df->may_dep = isl_union_map_union(df->may_dep, dep);
2527
472
  }
2528
126
2529
126
  isl_flow_free(flow);
2530
126
2531
126
  sched_info_free(data->sink_info);
2532
126
  if (
data->source_info126
)
{126
2533
400
    for (i = 0; 
i < data->count400
;
++i274
)
2534
274
      sched_info_free(data->source_info[i]);
2535
126
    free(data->source_info);
2536
126
  }
2537
126
  isl_space_free(data->dim);
2538
126
  isl_map_free(map);
2539
126
2540
126
  return isl_stat_ok;
2541
126
error:
2542
0
  isl_access_info_free(data->accesses);
2543
0
  sched_info_free(data->sink_info);
2544
0
  if (
data->source_info0
)
{0
2545
0
    for (i = 0; 
i < data->count0
;
++i0
)
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
126
  return isl_stat_error;
2553
126
}
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
2.31k
{
2561
2.31k
  isl_union_map *must, *kill;
2562
2.31k
2563
2.31k
  must = isl_union_access_info_get_must_source(info);
2564
2.31k
  kill = isl_union_access_info_get_kill(info);
2565
2.31k
  must = isl_union_map_union(must, kill);
2566
2.31k
  return isl_union_access_info_set_must_source(info, must);
2567
2.31k
}
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 || 0
!flow->may_dep0
)
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
2.31k
{
2628
2.31k
  if (!access)
2629
0
    return NULL;
2630
2.31k
  access->access[isl_access_may_source] =
2631
2.31k
    isl_union_map_subtract(access->access[isl_access_may_source],
2632
2.31k
        isl_union_map_copy(access->access[isl_access_must_source]));
2633
2.31k
  if (!access->access[isl_access_may_source])
2634
0
    return isl_union_access_info_free(access);
2635
2.31k
2636
2.31k
  return access;
2637
2.31k
}
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
81
{
2661
81
  struct isl_compute_flow_data data;
2662
81
  isl_union_map *sink;
2663
81
2664
81
  access = isl_union_access_info_align_params(access);
2665
81
  access = isl_union_access_info_introduce_schedule(access);
2666
81
  if (!access)
2667
0
    return NULL;
2668
81
2669
81
  data.must_source = access->access[isl_access_must_source];
2670
81
  data.may_source = access->access[isl_access_may_source];
2671
81
2672
81
  sink = access->access[isl_access_sink];
2673
81
  data.flow = isl_union_flow_alloc(isl_union_map_get_space(sink));
2674
81
2675
81
  if (isl_union_map_foreach_map(sink, &compute_flow, &data) < 0)
2676
0
    goto error;
2677
81
2678
81
  data.flow = isl_union_flow_drop_schedule(data.flow);
2679
81
2680
81
  isl_union_access_info_free(access);
2681
81
  return data.flow;
2682
81
error:
2683
0
  isl_union_access_info_free(access);
2684
0
  isl_union_flow_free(data.flow);
2685
81
  return NULL;
2686
81
}
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
2.23k
{
2732
2.23k
  int i;
2733
2.23k
  isl_space *space;
2734
2.23k
2735
2.23k
  if (
data->n_sink == 0 || 2.23k
data->n_source == 02.02k
)
2736
211
    return;
2737
2.23k
2738
2.23k
  space = isl_map_get_space(data->sink[0].access);
2739
2.02k
2740
3.41k
  for (i = 1; 
i < data->n_sink3.41k
;
++i1.39k
)
2741
2.02k
    space = isl_space_align_params(space,
2742
2.02k
        isl_map_get_space(data->sink[i].access));
2743
6.24k
  for (i = 0; 
i < data->n_source6.24k
;
++i4.22k
)
2744
4.22k
    space = isl_space_align_params(space,
2745
4.22k
        isl_map_get_space(data->source[i].access));
2746
2.02k
2747
5.43k
  for (i = 0; 
i < data->n_sink5.43k
;
++i3.41k
)
2748
3.41k
    data->sink[i].access =
2749
3.41k
      isl_map_align_params(data->sink[i].access,
2750
3.41k
              isl_space_copy(space));
2751
6.24k
  for (i = 0; 
i < data->n_source6.24k
;
++i4.22k
)
2752
4.22k
    data->source[i].access =
2753
4.22k
      isl_map_align_params(data->source[i].access,
2754
4.22k
              isl_space_copy(space));
2755
2.02k
2756
2.02k
  isl_space_free(space);
2757
2.23k
}
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
2.23k
{
2765
2.23k
  int i;
2766
2.23k
2767
2.23k
  if (!data->sink)
2768
0
    return;
2769
2.23k
2770
5.65k
  
for (i = 0; 2.23k
i < data->n_sink5.65k
;
++i3.42k
)
{3.42k
2771
3.42k
    isl_map_free(data->sink[i].access);
2772
3.42k
    isl_schedule_node_free(data->sink[i].node);
2773
3.42k
  }
2774
2.23k
2775
6.71k
  for (i = 0; 
i < data->n_source6.71k
;
++i4.48k
)
{4.48k
2776
4.48k
    isl_map_free(data->source[i].access);
2777
4.48k
    isl_schedule_node_free(data->source[i].node);
2778
4.48k
  }
2779
2.23k
2780
2.23k
  free(data->sink);
2781
2.23k
}
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
11.5k
{
2795
11.5k
  struct isl_compute_flow_schedule_data *data = user;
2796
11.5k
  isl_union_set *domain;
2797
11.5k
  isl_union_map *umap;
2798
11.5k
  isl_bool r = isl_bool_false;
2799
11.5k
2800
11.5k
  if (isl_schedule_node_get_type(node) != isl_schedule_node_leaf)
2801
8.12k
    return isl_bool_true;
2802
11.5k
2803
11.5k
  domain = isl_schedule_node_get_universe_domain(node);
2804
3.37k
2805
3.37k
  umap = isl_union_map_copy(data->access->access[isl_access_sink]);
2806
3.37k
  umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(domain));
2807
3.37k
  data->n_sink += isl_union_map_n_map(umap);
2808
3.37k
  isl_union_map_free(umap);
2809
3.37k
  if (!umap)
2810
0
    r = isl_bool_error;
2811
3.37k
2812
3.37k
  umap = isl_union_map_copy(data->access->access[isl_access_must_source]);
2813
3.37k
  umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(domain));
2814
3.37k
  data->n_source += isl_union_map_n_map(umap);
2815
3.37k
  isl_union_map_free(umap);
2816
3.37k
  if (!umap)
2817
0
    r = isl_bool_error;
2818
3.37k
2819
3.37k
  umap = isl_union_map_copy(data->access->access[isl_access_may_source]);
2820
3.37k
  umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(domain));
2821
3.37k
  data->n_source += isl_union_map_n_map(umap);
2822
3.37k
  isl_union_map_free(umap);
2823
3.37k
  if (!umap)
2824
0
    r = isl_bool_error;
2825
3.37k
2826
3.37k
  isl_union_set_free(domain);
2827
3.37k
2828
11.5k
  return r;
2829
11.5k
}
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
7.90k
{
2837
7.90k
  struct isl_compute_flow_schedule_data *data = user;
2838
7.90k
  struct isl_scheduled_access *access;
2839
7.90k
2840
7.90k
  if (data->set_sink)
2841
3.42k
    access = data->sink + data->n_sink++;
2842
7.90k
  else
2843
4.48k
    access = data->source + data->n_source++;
2844
7.90k
2845
7.90k
  access->access = map;
2846
7.90k
  access->must = data->must;
2847
7.90k
  access->node = isl_schedule_node_copy(data->node);
2848
7.90k
2849
7.90k
  return isl_stat_ok;
2850
7.90k
}
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
11.5k
{
2879
11.5k
  struct isl_compute_flow_schedule_data *data = user;
2880
11.5k
  isl_union_map *prefix;
2881
11.5k
  isl_union_map *umap;
2882
11.5k
  isl_bool r = isl_bool_false;
2883
11.5k
2884
11.5k
  if (isl_schedule_node_get_type(node) != isl_schedule_node_leaf)
2885
8.12k
    return isl_bool_true;
2886
11.5k
2887
11.5k
  data->node = node;
2888
3.37k
2889
3.37k
  prefix = isl_schedule_node_get_prefix_schedule_relation(node);
2890
3.37k
  prefix = isl_union_map_reverse(prefix);
2891
3.37k
  prefix = isl_union_map_range_map(prefix);
2892
3.37k
2893
3.37k
  data->set_sink = 1;
2894
3.37k
  umap = isl_union_map_copy(data->access->access[isl_access_sink]);
2895
3.37k
  umap = isl_union_map_apply_range(isl_union_map_copy(prefix), umap);
2896
3.37k
  if (isl_union_map_foreach_map(umap, &extract_sink_source, data) < 0)
2897
0
    r = isl_bool_error;
2898
3.37k
  isl_union_map_free(umap);
2899
3.37k
2900
3.37k
  data->set_sink = 0;
2901
3.37k
  data->must = 1;
2902
3.37k
  umap = isl_union_map_copy(data->access->access[isl_access_must_source]);
2903
3.37k
  umap = isl_union_map_apply_range(isl_union_map_copy(prefix), umap);
2904
3.37k
  if (isl_union_map_foreach_map(umap, &extract_sink_source, data) < 0)
2905
0
    r = isl_bool_error;
2906
3.37k
  isl_union_map_free(umap);
2907
3.37k
2908
3.37k
  data->set_sink = 0;
2909
3.37k
  data->must = 0;
2910
3.37k
  umap = isl_union_map_copy(data->access->access[isl_access_may_source]);
2911
3.37k
  umap = isl_union_map_apply_range(isl_union_map_copy(prefix), umap);
2912
3.37k
  if (isl_union_map_foreach_map(umap, &extract_sink_source, data) < 0)
2913
0
    r = isl_bool_error;
2914
3.37k
  isl_union_map_free(umap);
2915
3.37k
2916
3.37k
  isl_union_map_free(prefix);
2917
3.37k
2918
11.5k
  return r;
2919
11.5k
}
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
54.2k
{
2939
54.2k
  isl_schedule_node *node1 = first;
2940
54.2k
  isl_schedule_node *node2 = second;
2941
54.2k
  isl_schedule_node *shared;
2942
54.2k
  int depth;
2943
54.2k
  int before = 0;
2944
54.2k
2945
54.2k
  shared = isl_schedule_node_get_shared_ancestor(node1, node2);
2946
54.2k
  if (!shared)
2947
0
    return -1;
2948
54.2k
2949
54.2k
  depth = isl_schedule_node_get_schedule_depth(shared);
2950
54.2k
  if (
isl_schedule_node_get_type(shared) == isl_schedule_node_sequence54.2k
)
{28.7k
2951
28.7k
    int pos1, pos2;
2952
28.7k
2953
28.7k
    pos1 = isl_schedule_node_get_ancestor_child_position(node1,
2954
28.7k
                    shared);
2955
28.7k
    pos2 = isl_schedule_node_get_ancestor_child_position(node2,
2956
28.7k
                    shared);
2957
28.7k
    before = pos1 < pos2;
2958
54.2k
  }
2959
54.2k
2960
54.2k
  isl_schedule_node_free(shared);
2961
54.2k
2962
54.2k
  return 2 * depth + before;
2963
54.2k
}
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
1.69k
{
2972
1.69k
  isl_schedule_node *node1 = first;
2973
1.69k
  isl_schedule_node *node2 = second;
2974
1.69k
2975
1.69k
  return node1 == node2;
2976
1.69k
}
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
3.42k
{
2985
3.42k
  int i;
2986
3.42k
  isl_space *space;
2987
3.42k
2988
3.42k
  space = isl_space_range(isl_map_get_space(sink->access));
2989
14.0k
  for (i = 0; 
i < data->n_source14.0k
;
++i10.6k
)
{10.6k
2990
10.6k
    struct isl_scheduled_access *source;
2991
10.6k
    isl_space *source_space;
2992
10.6k
    int eq;
2993
10.6k
2994
10.6k
    source = &data->source[i];
2995
10.6k
    source_space = isl_map_get_space(source->access);
2996
10.6k
    source_space = isl_space_range(source_space);
2997
10.6k
    eq = isl_space_is_equal(space, source_space);
2998
10.6k
    isl_space_free(source_space);
2999
10.6k
3000
10.6k
    if (!eq)
3001
4.89k
      continue;
3002
5.77k
    
if (5.77k
eq < 05.77k
)
3003
0
      goto error;
3004
5.77k
3005
5.77k
    access = isl_access_info_add_source(access,
3006
5.77k
        isl_map_copy(source->access), source->must, source->node);
3007
5.77k
  }
3008
3.42k
3009
3.42k
  isl_space_free(space);
3010
3.42k
  return access;
3011
3.42k
error:
3012
0
  isl_space_free(space);
3013
0
  isl_access_info_free(access);
3014
3.42k
  return NULL;
3015
3.42k
}
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
3.42k
{
3038
3.42k
  int i;
3039
3.42k
  isl_access_info *access;
3040
3.42k
  isl_flow *flow;
3041
3.42k
  isl_map *map;
3042
3.42k
3043
3.42k
  if (!uf)
3044
0
    return NULL;
3045
3.42k
3046
3.42k
  access = isl_access_info_alloc(isl_map_copy(sink->access), sink->node,
3047
3.42k
          &before_node, data->n_source);
3048
3.42k
  if (access)
3049
3.42k
    access->coscheduled = &coscheduled_node;
3050
3.42k
  access = add_matching_sources(access, sink, data);
3051
3.42k
3052
3.42k
  flow = access_info_compute_flow_core(access);
3053
3.42k
  if (!flow)
3054
0
    return isl_union_flow_free(uf);
3055
3.42k
3056
3.42k
  map = isl_map_domain_factor_range(isl_flow_get_no_source(flow, 1));
3057
3.42k
  uf->must_no_source = isl_union_map_union(uf->must_no_source,
3058
3.42k
            isl_union_map_from_map(map));
3059
3.42k
  map = isl_map_domain_factor_range(isl_flow_get_no_source(flow, 0));
3060
3.42k
  uf->may_no_source = isl_union_map_union(uf->may_no_source,
3061
3.42k
            isl_union_map_from_map(map));
3062
3.42k
3063
14.4k
  for (i = 0; 
i < flow->n_source14.4k
;
++i11.0k
)
{11.0k
3064
11.0k
    isl_union_map *dep;
3065
11.0k
3066
11.0k
    map = isl_map_range_curry(isl_map_copy(flow->dep[i].map));
3067
11.0k
    map = isl_map_factor_range(map);
3068
11.0k
    dep = isl_union_map_from_map(map);
3069
11.0k
    if (flow->dep[i].must)
3070
5.25k
      uf->must_dep = isl_union_map_union(uf->must_dep, dep);
3071
11.0k
    else
3072
5.77k
      uf->may_dep = isl_union_map_union(uf->may_dep, dep);
3073
11.0k
  }
3074
3.42k
3075
3.42k
  isl_flow_free(flow);
3076
3.42k
3077
3.42k
  return uf;
3078
3.42k
}
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
2.23k
{
3104
2.23k
  struct isl_compute_flow_schedule_data data = { access };
3105
2.23k
  int i, n;
3106
2.23k
  isl_ctx *ctx;
3107
2.23k
  isl_space *space;
3108
2.23k
  isl_union_flow *flow;
3109
2.23k
3110
2.23k
  ctx = isl_union_access_info_get_ctx(access);
3111
2.23k
3112
2.23k
  data.n_sink = 0;
3113
2.23k
  data.n_source = 0;
3114
2.23k
  if (isl_schedule_foreach_schedule_node_top_down(access->schedule,
3115
2.23k
            &count_sink_source, &data) < 0)
3116
0
    goto error;
3117
2.23k
3118
2.23k
  n = data.n_sink + data.n_source;
3119
2.23k
  data.sink = isl_calloc_array(ctx, struct isl_scheduled_access, n);
3120
2.23k
  if (
n && 2.23k
!data.sink2.23k
)
3121
0
    goto error;
3122
2.23k
  data.source = data.sink + data.n_sink;
3123
2.23k
3124
2.23k
  data.n_sink = 0;
3125
2.23k
  data.n_source = 0;
3126
2.23k
  if (isl_schedule_foreach_schedule_node_top_down(access->schedule,
3127
2.23k
              &collect_sink_source, &data) < 0)
3128
0
    goto error;
3129
2.23k
3130
2.23k
  space = isl_union_map_get_space(access->access[isl_access_sink]);
3131
2.23k
  flow = isl_union_flow_alloc(space);
3132
2.23k
3133
2.23k
  isl_compute_flow_schedule_data_align_params(&data);
3134
2.23k
3135
5.65k
  for (i = 0; 
i < data.n_sink5.65k
;
++i3.42k
)
3136
3.42k
    flow = compute_single_flow(flow, &data.sink[i], &data);
3137
2.23k
3138
2.23k
  isl_compute_flow_schedule_data_clear(&data);
3139
2.23k
3140
2.23k
  isl_union_access_info_free(access);
3141
2.23k
  return flow;
3142
2.23k
error:
3143
0
  isl_union_access_info_free(access);
3144
0
  isl_compute_flow_schedule_data_clear(&data);
3145
2.23k
  return NULL;
3146
2.23k
}
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
2.33k
{
3171
2.33k
  isl_bool has_kill;
3172
2.33k
  isl_union_map *must = NULL, *may = NULL;
3173
2.33k
  isl_union_flow *flow;
3174
2.33k
3175
2.33k
  has_kill = isl_union_access_has_kill(access);
3176
2.33k
  if (has_kill < 0)
3177
20
    goto error;
3178
2.31k
  
if (2.31k
has_kill2.31k
)
{0
3179
0
    must = isl_union_access_info_get_must_source(access);
3180
0
    may = isl_union_access_info_get_may_source(access);
3181
2.31k
  }
3182
2.31k
  access = isl_union_access_info_add_kill_to_must_source(access);
3183
2.31k
  access = isl_union_access_info_normalize(access);
3184
2.31k
  if (!access)
3185
0
    goto error;
3186
2.31k
  
if (2.31k
access->schedule2.31k
)
3187
2.23k
    flow = compute_flow_schedule(access);
3188
2.31k
  else
3189
81
    flow = compute_flow_union_map(access);
3190
2.31k
  if (has_kill)
3191
0
    flow = isl_union_flow_drop_kill_source(flow, must, may);
3192
2.31k
  return flow;
3193
2.31k
error:
3194
20
  isl_union_access_info_free(access);
3195
20
  isl_union_map_free(must);
3196
20
  isl_union_map_free(may);
3197
2.31k
  return NULL;
3198
2.33k
}
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
81
{
3271
81
  isl_union_access_info *access;
3272
81
  isl_union_flow *flow;
3273
81
3274
81
  access = isl_union_access_info_from_sink(sink);
3275
81
  access = isl_union_access_info_set_must_source(access, must_source);
3276
81
  access = isl_union_access_info_set_may_source(access, may_source);
3277
81
  access = isl_union_access_info_set_schedule_map(access, schedule);
3278
81
  flow = isl_union_access_info_compute_flow(access);
3279
81
3280
81
  if (must_dep)
3281
81
    *must_dep = isl_union_flow_get_must_dependence(flow);
3282
81
  if (may_dep)
3283
41
    *may_dep = isl_union_flow_get_non_must_dependence(flow);
3284
81
  if (must_no_source)
3285
0
    *must_no_source = isl_union_flow_get_must_no_source(flow);
3286
81
  if (may_no_source)
3287
0
    *may_no_source = isl_union_flow_get_non_must_no_source(flow);
3288
81
3289
81
  isl_union_flow_free(flow);
3290
81
3291
81
  if (
(must_dep && 81
!*must_dep81
) ||
(may_dep && 81
!*may_dep41
) ||
3292
81
      
(must_no_source && 81
!*must_no_source0
) ||
3293
81
      
(may_no_source && 81
!*may_no_source0
))
3294
0
    goto error;
3295
81
3296
81
  return 0;
3297
81
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
81
  return -1;
3307
81
}