Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/External/isl/isl_schedule.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2011      INRIA Saclay
3
 * Copyright 2012-2014 Ecole Normale Superieure
4
 * Copyright 2016      Sven Verdoolaege
5
 *
6
 * Use of this software is governed by the MIT license
7
 *
8
 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9
 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10
 * 91893 Orsay, France
11
 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
12
 */
13
14
#include <isl/ctx.h>
15
#include <isl_aff_private.h>
16
#include <isl/map.h>
17
#include <isl/set.h>
18
#include <isl/schedule.h>
19
#include <isl/schedule_node.h>
20
#include <isl_sort.h>
21
#include <isl_schedule_private.h>
22
#include <isl_schedule_tree.h>
23
#include <isl_schedule_node_private.h>
24
#include <isl_band_private.h>
25
26
/* Return a schedule encapsulating the given schedule tree.
27
 *
28
 * We currently only allow schedule trees with a domain or extension as root.
29
 *
30
 * The leaf field is initialized as a leaf node so that it can be
31
 * used to represent leaves in the constructed schedule.
32
 * The reference count is set to -1 since the isl_schedule_tree
33
 * should never be freed.  It is up to the (internal) users of
34
 * these leaves to ensure that they are only used while the schedule
35
 * is still alive.
36
 */
37
__isl_give isl_schedule *isl_schedule_from_schedule_tree(isl_ctx *ctx,
38
  __isl_take isl_schedule_tree *tree)
39
6.40k
{
40
6.40k
  enum isl_schedule_node_type type;
41
6.40k
  isl_schedule *schedule;
42
6.40k
43
6.40k
  if (!tree)
44
0
    return NULL;
45
6.40k
  type = isl_schedule_tree_get_type(tree);
46
6.40k
  if (type != isl_schedule_node_domain &&
47
24
      type != isl_schedule_node_extension)
48
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_unsupported,
49
6.40k
      "root of schedule tree should be a domain or extension",
50
6.40k
      goto error);
51
6.40k
52
6.40k
  
schedule = 6.40k
isl_calloc_type6.40k
(ctx, isl_schedule);
53
6.40k
  if (!schedule)
54
0
    goto error;
55
6.40k
56
6.40k
  schedule->ref = 1;
57
6.40k
  schedule->root = tree;
58
6.40k
  schedule->leaf = isl_schedule_tree_leaf(ctx);
59
6.40k
60
6.40k
  if (!schedule->leaf)
61
0
    return isl_schedule_free(schedule);
62
6.40k
  return schedule;
63
0
error:
64
0
  isl_schedule_tree_free(tree);
65
0
  return NULL;
66
6.40k
}
67
68
/* Return a pointer to a schedule with as single node
69
 * a domain node with the given domain.
70
 */
71
__isl_give isl_schedule *isl_schedule_from_domain(
72
  __isl_take isl_union_set *domain)
73
4.68k
{
74
4.68k
  isl_ctx *ctx;
75
4.68k
  isl_schedule_tree *tree;
76
4.68k
77
4.68k
  ctx = isl_union_set_get_ctx(domain);
78
4.68k
  tree = isl_schedule_tree_from_domain(domain);
79
4.68k
  return isl_schedule_from_schedule_tree(ctx, tree);
80
4.68k
}
81
82
/* Return a pointer to a schedule with as single node
83
 * a domain node with an empty domain.
84
 */
85
__isl_give isl_schedule *isl_schedule_empty(__isl_take isl_space *space)
86
2.43k
{
87
2.43k
  return isl_schedule_from_domain(isl_union_set_empty(space));
88
2.43k
}
89
90
/* Return a new reference to "sched".
91
 */
92
__isl_give isl_schedule *isl_schedule_copy(__isl_keep isl_schedule *sched)
93
70.8k
{
94
70.8k
  if (!sched)
95
0
    return NULL;
96
70.8k
97
70.8k
  sched->ref++;
98
70.8k
  return sched;
99
70.8k
}
100
101
/* Return an isl_schedule that is equal to "schedule" and that has only
102
 * a single reference.
103
 *
104
 * We only need and support this function when the schedule is represented
105
 * as a schedule tree.
106
 */
107
__isl_give isl_schedule *isl_schedule_cow(__isl_take isl_schedule *schedule)
108
6.32k
{
109
6.32k
  isl_ctx *ctx;
110
6.32k
  isl_schedule_tree *tree;
111
6.32k
112
6.32k
  if (!schedule)
113
0
    return NULL;
114
6.32k
  
if (6.32k
schedule->ref == 16.32k
)
115
5.55k
    return schedule;
116
778
117
778
  ctx = isl_schedule_get_ctx(schedule);
118
778
  if (!schedule->root)
119
0
    isl_die(ctx, isl_error_internal,
120
778
      "only for schedule tree based schedules",
121
778
      return isl_schedule_free(schedule));
122
778
  schedule->ref--;
123
778
  tree = isl_schedule_tree_copy(schedule->root);
124
778
  return isl_schedule_from_schedule_tree(ctx, tree);
125
6.32k
}
126
127
__isl_null isl_schedule *isl_schedule_free(__isl_take isl_schedule *sched)
128
76.8k
{
129
76.8k
  if (!sched)
130
373
    return NULL;
131
76.4k
132
76.4k
  
if (76.4k
--sched->ref > 076.4k
)
133
70.0k
    return NULL;
134
6.38k
135
6.38k
  isl_band_list_free(sched->band_forest);
136
6.38k
  isl_schedule_tree_free(sched->root);
137
6.38k
  isl_schedule_tree_free(sched->leaf);
138
6.38k
  free(sched);
139
6.38k
  return NULL;
140
6.38k
}
141
142
/* Replace the root of "schedule" by "tree".
143
 */
144
__isl_give isl_schedule *isl_schedule_set_root(
145
  __isl_take isl_schedule *schedule, __isl_take isl_schedule_tree *tree)
146
6.32k
{
147
6.32k
  if (
!schedule || 6.32k
!tree6.32k
)
148
0
    goto error;
149
6.32k
  
if (6.32k
schedule->root == tree6.32k
) {
150
0
    isl_schedule_tree_free(tree);
151
0
    return schedule;
152
0
  }
153
6.32k
154
6.32k
  schedule = isl_schedule_cow(schedule);
155
6.32k
  if (!schedule)
156
0
    goto error;
157
6.32k
  isl_schedule_tree_free(schedule->root);
158
6.32k
  schedule->root = tree;
159
6.32k
160
6.32k
  return schedule;
161
0
error:
162
0
  isl_schedule_free(schedule);
163
0
  isl_schedule_tree_free(tree);
164
0
  return NULL;
165
6.32k
}
166
167
isl_ctx *isl_schedule_get_ctx(__isl_keep isl_schedule *schedule)
168
116k
{
169
116k
  return schedule ? isl_schedule_tree_get_ctx(schedule->leaf) : NULL;
170
116k
}
171
172
/* Return a pointer to the leaf of "schedule".
173
 */
174
__isl_keep isl_schedule_tree *isl_schedule_peek_leaf(
175
  __isl_keep isl_schedule *schedule)
176
19.8k
{
177
19.8k
  return schedule ? schedule->leaf : NULL;
178
19.8k
}
179
180
/* Are "schedule1" and "schedule2" obviously equal to each other?
181
 */
182
isl_bool isl_schedule_plain_is_equal(__isl_keep isl_schedule *schedule1,
183
  __isl_keep isl_schedule *schedule2)
184
0
{
185
0
  if (
!schedule1 || 0
!schedule20
)
186
0
    return isl_bool_error;
187
0
  
if (0
schedule1 == schedule20
)
188
0
    return isl_bool_true;
189
0
  return isl_schedule_tree_plain_is_equal(schedule1->root,
190
0
            schedule2->root);
191
0
}
192
193
/* Return the (parameter) space of the schedule, i.e., the space
194
 * of the root domain.
195
 */
196
__isl_give isl_space *isl_schedule_get_space(
197
  __isl_keep isl_schedule *schedule)
198
3.71k
{
199
3.71k
  enum isl_schedule_node_type type;
200
3.71k
  isl_space *space;
201
3.71k
  isl_union_set *domain;
202
3.71k
203
3.71k
  if (!schedule)
204
0
    return NULL;
205
3.71k
  
if (3.71k
!schedule->root3.71k
)
206
0
    isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid,
207
3.71k
      "schedule tree representation not available",
208
3.71k
      return NULL);
209
3.71k
  type = isl_schedule_tree_get_type(schedule->root);
210
3.71k
  if (type != isl_schedule_node_domain)
211
0
    isl_die(isl_schedule_get_ctx(schedule), isl_error_internal,
212
3.71k
      "root node not a domain node", return NULL);
213
3.71k
214
3.71k
  domain = isl_schedule_tree_domain_get_domain(schedule->root);
215
3.71k
  space = isl_union_set_get_space(domain);
216
3.71k
  isl_union_set_free(domain);
217
3.71k
218
3.71k
  return space;
219
3.71k
}
220
221
/* Return a pointer to the root of "schedule".
222
 */
223
__isl_give isl_schedule_node *isl_schedule_get_root(
224
  __isl_keep isl_schedule *schedule)
225
14.3k
{
226
14.3k
  isl_ctx *ctx;
227
14.3k
  isl_schedule_tree *tree;
228
14.3k
  isl_schedule_tree_list *ancestors;
229
14.3k
230
14.3k
  if (!schedule)
231
0
    return NULL;
232
14.3k
233
14.3k
  
if (14.3k
!schedule->root14.3k
)
234
0
    isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid,
235
14.3k
      "schedule tree representation not available",
236
14.3k
      return NULL);
237
14.3k
238
14.3k
  ctx = isl_schedule_get_ctx(schedule);
239
14.3k
  tree = isl_schedule_tree_copy(schedule->root);
240
14.3k
  schedule = isl_schedule_copy(schedule);
241
14.3k
  ancestors = isl_schedule_tree_list_alloc(ctx, 0);
242
14.3k
  return isl_schedule_node_alloc(schedule, tree, ancestors, NULL);
243
14.3k
}
244
245
/* Set max_out to the maximal number of output dimensions over
246
 * all maps.
247
 */
248
static isl_stat update_max_out(__isl_take isl_map *map, void *user)
249
4
{
250
4
  int *max_out = user;
251
4
  int n_out = isl_map_dim(map, isl_dim_out);
252
4
253
4
  if (n_out > *max_out)
254
4
    *max_out = n_out;
255
4
256
4
  isl_map_free(map);
257
4
  return isl_stat_ok;
258
4
}
259
260
/* Internal data structure for map_pad_range.
261
 *
262
 * "max_out" is the maximal schedule dimension.
263
 * "res" collects the results.
264
 */
265
struct isl_pad_schedule_map_data {
266
  int max_out;
267
  isl_union_map *res;
268
};
269
270
/* Pad the range of the given map with zeros to data->max_out and
271
 * then add the result to data->res.
272
 */
273
static isl_stat map_pad_range(__isl_take isl_map *map, void *user)
274
4
{
275
4
  struct isl_pad_schedule_map_data *data = user;
276
4
  int i;
277
4
  int n_out = isl_map_dim(map, isl_dim_out);
278
4
279
4
  map = isl_map_add_dims(map, isl_dim_out, data->max_out - n_out);
280
6
  for (i = n_out; 
i < data->max_out6
;
++i2
)
281
2
    map = isl_map_fix_si(map, isl_dim_out, i, 0);
282
4
283
4
  data->res = isl_union_map_add_map(data->res, map);
284
4
  if (!data->res)
285
0
    return isl_stat_error;
286
4
287
4
  return isl_stat_ok;
288
4
}
289
290
/* Pad the ranges of the maps in the union map with zeros such they all have
291
 * the same dimension.
292
 */
293
static __isl_give isl_union_map *pad_schedule_map(
294
  __isl_take isl_union_map *umap)
295
2
{
296
2
  struct isl_pad_schedule_map_data data;
297
2
298
2
  if (!umap)
299
0
    return NULL;
300
2
  
if (2
isl_union_map_n_map(umap) <= 12
)
301
0
    return umap;
302
2
303
2
  data.max_out = 0;
304
2
  if (isl_union_map_foreach_map(umap, &update_max_out, &data.max_out) < 0)
305
0
    return isl_union_map_free(umap);
306
2
307
2
  data.res = isl_union_map_empty(isl_union_map_get_space(umap));
308
2
  if (isl_union_map_foreach_map(umap, &map_pad_range, &data) < 0)
309
0
    data.res = isl_union_map_free(data.res);
310
2
311
2
  isl_union_map_free(umap);
312
2
  return data.res;
313
2
}
314
315
/* Return the domain of the root domain node of "schedule".
316
 */
317
__isl_give isl_union_set *isl_schedule_get_domain(
318
  __isl_keep isl_schedule *schedule)
319
1.55k
{
320
1.55k
  if (!schedule)
321
0
    return NULL;
322
1.55k
  
if (1.55k
!schedule->root1.55k
)
323
0
    isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid,
324
1.55k
      "schedule tree representation not available",
325
1.55k
      return NULL);
326
1.55k
  return isl_schedule_tree_domain_get_domain(schedule->root);
327
1.55k
}
328
329
/* Traverse all nodes of "sched" in depth first preorder.
330
 *
331
 * If "fn" returns -1 on any of the nodes, then the traversal is aborted.
332
 * If "fn" returns 0 on any of the nodes, then the subtree rooted
333
 * at that node is skipped.
334
 *
335
 * Return 0 on success and -1 on failure.
336
 */
337
isl_stat isl_schedule_foreach_schedule_node_top_down(
338
  __isl_keep isl_schedule *sched,
339
  isl_bool (*fn)(__isl_keep isl_schedule_node *node, void *user),
340
  void *user)
341
6.21k
{
342
6.21k
  isl_schedule_node *node;
343
6.21k
  isl_stat r;
344
6.21k
345
6.21k
  if (!sched)
346
0
    return isl_stat_error;
347
6.21k
348
6.21k
  node = isl_schedule_get_root(sched);
349
6.21k
  r = isl_schedule_node_foreach_descendant_top_down(node, fn, user);
350
6.21k
  isl_schedule_node_free(node);
351
6.21k
352
6.21k
  return r;
353
6.21k
}
354
355
/* Traverse the node of "sched" in depth first postorder,
356
 * allowing the user to modify the visited node.
357
 * The traversal continues from the node returned by the callback function.
358
 * It is the responsibility of the user to ensure that this does not
359
 * lead to an infinite loop.  It is safest to always return a pointer
360
 * to the same position (same ancestors and child positions) as the input node.
361
 */
362
__isl_give isl_schedule *isl_schedule_map_schedule_node_bottom_up(
363
  __isl_take isl_schedule *schedule,
364
  __isl_give isl_schedule_node *(*fn)(
365
    __isl_take isl_schedule_node *node, void *user), void *user)
366
146
{
367
146
  isl_schedule_node *node;
368
146
369
146
  node = isl_schedule_get_root(schedule);
370
146
  isl_schedule_free(schedule);
371
146
372
146
  node = isl_schedule_node_map_descendant_bottom_up(node, fn, user);
373
146
  schedule = isl_schedule_node_get_schedule(node);
374
146
  isl_schedule_node_free(node);
375
146
376
146
  return schedule;
377
146
}
378
379
/* Wrapper around isl_schedule_node_reset_user for use as
380
 * an isl_schedule_map_schedule_node_bottom_up callback.
381
 */
382
static __isl_give isl_schedule_node *reset_user(
383
  __isl_take isl_schedule_node *node, void *user)
384
0
{
385
0
  return isl_schedule_node_reset_user(node);
386
0
}
387
388
/* Reset the user pointer on all identifiers of parameters and tuples
389
 * in the schedule "schedule".
390
 */
391
__isl_give isl_schedule *isl_schedule_reset_user(
392
  __isl_take isl_schedule *schedule)
393
0
{
394
0
  return isl_schedule_map_schedule_node_bottom_up(schedule, &reset_user,
395
0
              NULL);
396
0
}
397
398
/* Wrapper around isl_schedule_node_align_params for use as
399
 * an isl_schedule_map_schedule_node_bottom_up callback.
400
 */
401
static __isl_give isl_schedule_node *align_params(
402
  __isl_take isl_schedule_node *node, void *user)
403
0
{
404
0
  isl_space *space = user;
405
0
406
0
  return isl_schedule_node_align_params(node, isl_space_copy(space));
407
0
}
408
409
/* Align the parameters of all nodes in schedule "schedule"
410
 * to those of "space".
411
 */
412
__isl_give isl_schedule *isl_schedule_align_params(
413
  __isl_take isl_schedule *schedule, __isl_take isl_space *space)
414
0
{
415
0
  schedule = isl_schedule_map_schedule_node_bottom_up(schedule,
416
0
                &align_params, space);
417
0
  isl_space_free(space);
418
0
  return schedule;
419
0
}
420
421
/* Wrapper around isl_schedule_node_pullback_union_pw_multi_aff for use as
422
 * an isl_schedule_map_schedule_node_bottom_up callback.
423
 */
424
static __isl_give isl_schedule_node *pullback_upma(
425
  __isl_take isl_schedule_node *node, void *user)
426
1.03k
{
427
1.03k
  isl_union_pw_multi_aff *upma = user;
428
1.03k
429
1.03k
  return isl_schedule_node_pullback_union_pw_multi_aff(node,
430
1.03k
          isl_union_pw_multi_aff_copy(upma));
431
1.03k
}
432
433
/* Compute the pullback of "schedule" by the function represented by "upma".
434
 * In other words, plug in "upma" in the iteration domains of "schedule".
435
 *
436
 * The schedule tree is not allowed to contain any expansion nodes.
437
 */
438
__isl_give isl_schedule *isl_schedule_pullback_union_pw_multi_aff(
439
  __isl_take isl_schedule *schedule,
440
  __isl_take isl_union_pw_multi_aff *upma)
441
146
{
442
146
  schedule = isl_schedule_map_schedule_node_bottom_up(schedule,
443
146
            &pullback_upma, upma);
444
146
  isl_union_pw_multi_aff_free(upma);
445
146
  return schedule;
446
146
}
447
448
/* Expand the schedule "schedule" by extending all leaves
449
 * with an expansion node with as subtree the tree of "expansion".
450
 * The expansion of the expansion node is determined by "contraction"
451
 * and the domain of "expansion".  That is, the domain of "expansion"
452
 * is contracted according to "contraction".
453
 *
454
 * Call isl_schedule_node_expand after extracting the required
455
 * information from "expansion".
456
 */
457
__isl_give isl_schedule *isl_schedule_expand(__isl_take isl_schedule *schedule,
458
  __isl_take isl_union_pw_multi_aff *contraction,
459
  __isl_take isl_schedule *expansion)
460
0
{
461
0
  isl_union_set *domain;
462
0
  isl_schedule_node *node;
463
0
  isl_schedule_tree *tree;
464
0
465
0
  domain = isl_schedule_get_domain(expansion);
466
0
467
0
  node = isl_schedule_get_root(expansion);
468
0
  node = isl_schedule_node_child(node, 0);
469
0
  tree = isl_schedule_node_get_tree(node);
470
0
  isl_schedule_node_free(node);
471
0
  isl_schedule_free(expansion);
472
0
473
0
  node = isl_schedule_get_root(schedule);
474
0
  isl_schedule_free(schedule);
475
0
  node = isl_schedule_node_expand(node, contraction, domain, tree);
476
0
  schedule = isl_schedule_node_get_schedule(node);
477
0
  isl_schedule_node_free(node);
478
0
479
0
  return schedule;
480
0
}
481
482
/* Intersect the domain of the schedule "schedule" with "domain".
483
 * The root of "schedule" is required to be a domain node.
484
 */
485
__isl_give isl_schedule *isl_schedule_intersect_domain(
486
  __isl_take isl_schedule *schedule, __isl_take isl_union_set *domain)
487
3.02k
{
488
3.02k
  enum isl_schedule_node_type root_type;
489
3.02k
  isl_schedule_node *node;
490
3.02k
491
3.02k
  if (
!schedule || 3.02k
!domain3.02k
)
492
0
    goto error;
493
3.02k
494
3.02k
  root_type = isl_schedule_tree_get_type(schedule->root);
495
3.02k
  if (root_type != isl_schedule_node_domain)
496
0
    isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid,
497
3.02k
      "root node must be a domain node", goto error);
498
3.02k
499
3.02k
  node = isl_schedule_get_root(schedule);
500
3.02k
  isl_schedule_free(schedule);
501
3.02k
  node = isl_schedule_node_domain_intersect_domain(node, domain);
502
3.02k
  schedule = isl_schedule_node_get_schedule(node);
503
3.02k
  isl_schedule_node_free(node);
504
3.02k
505
3.02k
  return schedule;
506
0
error:
507
0
  isl_schedule_free(schedule);
508
0
  isl_union_set_free(domain);
509
0
  return NULL;
510
3.02k
}
511
512
/* Replace the domain of the schedule "schedule" with the gist
513
 * of the original domain with respect to the parameter domain "context".
514
 */
515
__isl_give isl_schedule *isl_schedule_gist_domain_params(
516
  __isl_take isl_schedule *schedule, __isl_take isl_set *context)
517
1.10k
{
518
1.10k
  enum isl_schedule_node_type root_type;
519
1.10k
  isl_schedule_node *node;
520
1.10k
521
1.10k
  if (
!schedule || 1.10k
!context1.10k
)
522
0
    goto error;
523
1.10k
524
1.10k
  root_type = isl_schedule_tree_get_type(schedule->root);
525
1.10k
  if (root_type != isl_schedule_node_domain)
526
0
    isl_die(isl_schedule_get_ctx(schedule), isl_error_invalid,
527
1.10k
      "root node must be a domain node", goto error);
528
1.10k
529
1.10k
  node = isl_schedule_get_root(schedule);
530
1.10k
  isl_schedule_free(schedule);
531
1.10k
  node = isl_schedule_node_domain_gist_params(node, context);
532
1.10k
  schedule = isl_schedule_node_get_schedule(node);
533
1.10k
  isl_schedule_node_free(node);
534
1.10k
535
1.10k
  return schedule;
536
0
error:
537
0
  isl_schedule_free(schedule);
538
0
  isl_set_free(context);
539
0
  return NULL;
540
1.10k
}
541
542
/* Return an isl_union_map representation of the schedule.
543
 * If we still have access to the schedule tree, then we return
544
 * an isl_union_map corresponding to the subtree schedule of the child
545
 * of the root domain node.  That is, we do not intersect the domain
546
 * of the returned isl_union_map with the domain constraints.
547
 * Otherwise, we must have removed it because we created a band forest.
548
 * If so, we extract the isl_union_map from the forest.
549
 * This reconstructed schedule map
550
 * then needs to be padded with zeros to unify the schedule space
551
 * since the result of isl_band_list_get_suffix_schedule may not have
552
 * a unified schedule space.
553
 */
554
__isl_give isl_union_map *isl_schedule_get_map(__isl_keep isl_schedule *sched)
555
1.45k
{
556
1.45k
  enum isl_schedule_node_type type;
557
1.45k
  isl_schedule_node *node;
558
1.45k
  isl_union_map *umap;
559
1.45k
560
1.45k
  if (!sched)
561
0
    return NULL;
562
1.45k
563
1.45k
  
if (1.45k
sched->root1.45k
) {
564
1.45k
    type = isl_schedule_tree_get_type(sched->root);
565
1.45k
    if (type != isl_schedule_node_domain)
566
0
      isl_die(isl_schedule_get_ctx(sched), isl_error_internal,
567
1.45k
        "root node not a domain node", return NULL);
568
1.45k
569
1.45k
    node = isl_schedule_get_root(sched);
570
1.45k
    node = isl_schedule_node_child(node, 0);
571
1.45k
    umap = isl_schedule_node_get_subtree_schedule_union_map(node);
572
1.45k
    isl_schedule_node_free(node);
573
1.45k
574
1.45k
    return umap;
575
2
  }
576
2
577
2
  umap = isl_band_list_get_suffix_schedule(sched->band_forest);
578
2
  return pad_schedule_map(umap);
579
2
}
580
581
static __isl_give isl_band_list *construct_band_list(
582
  __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain,
583
  __isl_keep isl_band *parent);
584
585
/* Construct an isl_band structure from the given schedule tree node,
586
 * which may be either a band node or a leaf node.
587
 * In the latter case, construct a zero-dimensional band.
588
 * "domain" is the universe set of the domain elements that reach "node".
589
 * "parent" is the parent isl_band of the isl_band constructed
590
 * by this function.
591
 *
592
 * In case of a band node, we copy the properties (except tilability,
593
 * which is implicit in an isl_band) to the isl_band.
594
 * We assume that the band node is not zero-dimensional.
595
 * If the child of the band node is not a leaf node,
596
 * then we extract the children of the isl_band from this child.
597
 */
598
static __isl_give isl_band *construct_band(__isl_take isl_schedule_node *node,
599
  __isl_take isl_union_set *domain, __isl_keep isl_band *parent)
600
4
{
601
4
  int i;
602
4
  isl_ctx *ctx;
603
4
  isl_band *band = NULL;
604
4
  isl_multi_union_pw_aff *mupa;
605
4
606
4
  if (
!node || 4
!domain4
)
607
0
    goto error;
608
4
609
4
  ctx = isl_schedule_node_get_ctx(node);
610
4
  band = isl_band_alloc(ctx);
611
4
  if (!band)
612
0
    goto error;
613
4
614
4
  band->schedule = node->schedule;
615
4
  band->parent = parent;
616
4
617
4
  if (
isl_schedule_node_get_type(node) == isl_schedule_node_leaf4
) {
618
0
    band->n = 0;
619
0
    band->pma = isl_union_pw_multi_aff_from_domain(domain);
620
0
    isl_schedule_node_free(node);
621
0
    return band;
622
0
  }
623
4
624
4
  band->n = isl_schedule_node_band_n_member(node);
625
4
  if (band->n == 0)
626
0
    isl_die(ctx, isl_error_unsupported,
627
4
      "zero-dimensional band nodes not supported",
628
4
      goto error);
629
4
  
band->coincident = 4
isl_alloc_array4
(ctx, int, band->n);
630
4
  if (
band->n && 4
!band->coincident4
)
631
0
    goto error;
632
10
  
for (i = 0; 4
i < band->n10
;
++i6
)
633
6
    band->coincident[i] =
634
6
      isl_schedule_node_band_member_get_coincident(node, i);
635
4
  mupa = isl_schedule_node_band_get_partial_schedule(node);
636
4
  band->pma = isl_union_pw_multi_aff_from_multi_union_pw_aff(mupa);
637
4
  if (!band->pma)
638
0
    goto error;
639
4
640
4
  node = isl_schedule_node_child(node, 0);
641
4
  if (
isl_schedule_node_get_type(node) == isl_schedule_node_leaf4
) {
642
4
    isl_schedule_node_free(node);
643
4
    isl_union_set_free(domain);
644
4
    return band;
645
4
  }
646
0
647
0
  band->children = construct_band_list(node, domain, band);
648
0
  if (!band->children)
649
0
    return isl_band_free(band);
650
0
651
0
  return band;
652
0
error:
653
0
  isl_union_set_free(domain);
654
0
  isl_schedule_node_free(node);
655
0
  isl_band_free(band);
656
0
  return NULL;
657
4
}
658
659
/* Construct a list of isl_band structures from the children of "node".
660
 * "node" itself is a sequence or set node, so that each of the child nodes
661
 * is a filter node and the list returned by node_construct_band_list
662
 * consists of a single element.
663
 * "domain" is the universe set of the domain elements that reach "node".
664
 * "parent" is the parent isl_band of the isl_band structures constructed
665
 * by this function.
666
 */
667
static __isl_give isl_band_list *construct_band_list_from_children(
668
  __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain,
669
  __isl_keep isl_band *parent)
670
2
{
671
2
  int i, n;
672
2
  isl_ctx *ctx;
673
2
  isl_band_list *list;
674
2
675
2
  n = isl_schedule_node_n_children(node);
676
2
677
2
  ctx = isl_schedule_node_get_ctx(node);
678
2
  list = isl_band_list_alloc(ctx, 0);
679
6
  for (i = 0; 
i < n6
;
++i4
) {
680
4
    isl_schedule_node *child;
681
4
    isl_band_list *list_i;
682
4
683
4
    child = isl_schedule_node_get_child(node, i);
684
4
    list_i = construct_band_list(child, isl_union_set_copy(domain),
685
4
            parent);
686
4
    list = isl_band_list_concat(list, list_i);
687
4
  }
688
2
689
2
  isl_union_set_free(domain);
690
2
  isl_schedule_node_free(node);
691
2
692
2
  return list;
693
2
}
694
695
/* Construct an isl_band structure from the given sequence node
696
 * (or set node that is treated as a sequence node).
697
 * A single-dimensional band is created with as schedule for each of
698
 * filters of the children, the corresponding child position.
699
 * "domain" is the universe set of the domain elements that reach "node".
700
 * "parent" is the parent isl_band of the isl_band constructed
701
 * by this function.
702
 */
703
static __isl_give isl_band_list *construct_band_list_sequence(
704
  __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain,
705
  __isl_keep isl_band *parent)
706
2
{
707
2
  int i, n;
708
2
  isl_ctx *ctx;
709
2
  isl_band *band = NULL;
710
2
  isl_space *space;
711
2
  isl_union_pw_multi_aff *upma;
712
2
713
2
  if (
!node || 2
!domain2
)
714
0
    goto error;
715
2
716
2
  ctx = isl_schedule_node_get_ctx(node);
717
2
  band = isl_band_alloc(ctx);
718
2
  if (!band)
719
0
    goto error;
720
2
721
2
  band->schedule = node->schedule;
722
2
  band->parent = parent;
723
2
  band->n = 1;
724
2
  band->coincident = isl_calloc_array(ctx, int, band->n);
725
2
  if (!band->coincident)
726
0
    goto error;
727
2
728
2
  n = isl_schedule_node_n_children(node);
729
2
  space = isl_union_set_get_space(domain);
730
2
  upma = isl_union_pw_multi_aff_empty(isl_space_copy(space));
731
2
732
2
  space = isl_space_set_from_params(space);
733
2
  space = isl_space_add_dims(space, isl_dim_set, 1);
734
2
735
6
  for (i = 0; 
i < n6
;
++i4
) {
736
4
    isl_schedule_node *child;
737
4
    isl_union_set *filter;
738
4
    isl_val *v;
739
4
    isl_val_list *vl;
740
4
    isl_multi_val *mv;
741
4
    isl_union_pw_multi_aff *upma_i;
742
4
743
4
    child = isl_schedule_node_get_child(node, i);
744
4
    filter = isl_schedule_node_filter_get_filter(child);
745
4
    isl_schedule_node_free(child);
746
4
    filter = isl_union_set_intersect(filter,
747
4
            isl_union_set_copy(domain));
748
4
    v = isl_val_int_from_si(ctx, i);
749
4
    vl = isl_val_list_from_val(v);
750
4
    mv = isl_multi_val_from_val_list(isl_space_copy(space), vl);
751
4
    upma_i = isl_union_pw_multi_aff_multi_val_on_domain(filter, mv);
752
4
    upma = isl_union_pw_multi_aff_union_add(upma, upma_i);
753
4
  }
754
2
755
2
  isl_space_free(space);
756
2
757
2
  band->pma = upma;
758
2
  if (!band->pma)
759
0
    goto error;
760
2
761
2
  band->children = construct_band_list_from_children(node, domain, band);
762
2
  if (!band->children)
763
0
    band = isl_band_free(band);
764
2
  return isl_band_list_from_band(band);
765
0
error:
766
0
  isl_union_set_free(domain);
767
0
  isl_schedule_node_free(node);
768
0
  isl_band_free(band);
769
0
  return NULL;
770
2
}
771
772
/* Construct a list of isl_band structures from "node" depending
773
 * on the type of "node".
774
 * "domain" is the universe set of the domain elements that reach "node".
775
 * "parent" is the parent isl_band of the isl_band structures constructed
776
 * by this function.
777
 *
778
 * If schedule_separate_components is set then set nodes are treated
779
 * as sequence nodes.  Otherwise, we directly extract an (implicitly
780
 * parallel) list of isl_band structures.
781
 *
782
 * If "node" is a filter, then "domain" is updated by the filter.
783
 */
784
static __isl_give isl_band_list *construct_band_list(
785
  __isl_take isl_schedule_node *node, __isl_take isl_union_set *domain,
786
  __isl_keep isl_band *parent)
787
10
{
788
10
  enum isl_schedule_node_type type;
789
10
  isl_ctx *ctx;
790
10
  isl_band *band;
791
10
  isl_band_list *list;
792
10
  isl_union_set *filter;
793
10
794
10
  if (
!node || 10
!domain10
)
795
0
    goto error;
796
10
797
10
  type = isl_schedule_node_get_type(node);
798
10
  switch (type) {
799
0
  case isl_schedule_node_error:
800
0
    goto error;
801
0
  case isl_schedule_node_context:
802
0
    isl_die(isl_schedule_node_get_ctx(node), isl_error_unsupported,
803
0
      "context nodes not supported", goto error);
804
0
  case isl_schedule_node_domain:
805
0
    isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
806
0
      "internal domain nodes not allowed", goto error);
807
0
  case isl_schedule_node_expansion:
808
0
    isl_die(isl_schedule_node_get_ctx(node), isl_error_unsupported,
809
0
      "expansion nodes not supported", goto error);
810
0
  case isl_schedule_node_extension:
811
0
    isl_die(isl_schedule_node_get_ctx(node), isl_error_unsupported,
812
0
      "extension nodes not supported", goto error);
813
4
  case isl_schedule_node_filter:
814
4
    filter = isl_schedule_node_filter_get_filter(node);
815
4
    domain = isl_union_set_intersect(domain, filter);
816
4
    node = isl_schedule_node_child(node, 0);
817
4
    return construct_band_list(node, domain, parent);
818
0
  case isl_schedule_node_guard:
819
0
    isl_die(isl_schedule_node_get_ctx(node), isl_error_unsupported,
820
0
      "guard nodes not supported", goto error);
821
0
  case isl_schedule_node_mark:
822
0
    isl_die(isl_schedule_node_get_ctx(node), isl_error_unsupported,
823
0
      "mark nodes not supported", goto error);
824
2
  case isl_schedule_node_set:
825
2
    ctx = isl_schedule_node_get_ctx(node);
826
2
    if (isl_options_get_schedule_separate_components(ctx))
827
2
      return construct_band_list_sequence(node, domain,
828
2
                  parent);
829
2
    else
830
0
      return construct_band_list_from_children(node, domain,
831
0
                  parent);
832
0
  case isl_schedule_node_sequence:
833
0
    return construct_band_list_sequence(node, domain, parent);
834
4
  case isl_schedule_node_leaf:
835
4
  case isl_schedule_node_band:
836
4
    band = construct_band(node, domain, parent);
837
4
    list = isl_band_list_from_band(band);
838
4
    break;
839
4
  }
840
4
841
4
  return list;
842
0
error:
843
0
  isl_union_set_free(domain);
844
0
  isl_schedule_node_free(node);
845
0
  return NULL;
846
10
}
847
848
/* Return the roots of a band forest representation of the schedule.
849
 * The band forest is constructed from the schedule tree,
850
 * but once such a band forest is
851
 * constructed, we forget about the original schedule tree since
852
 * the user may modify the schedule through the band forest.
853
 */
854
__isl_give isl_band_list *isl_schedule_get_band_forest(
855
  __isl_keep isl_schedule *schedule)
856
2
{
857
2
  isl_schedule_node *node;
858
2
  isl_union_set *domain;
859
2
860
2
  if (!schedule)
861
0
    return NULL;
862
2
  
if (2
schedule->root2
) {
863
2
    node = isl_schedule_get_root(schedule);
864
2
    domain = isl_schedule_node_domain_get_domain(node);
865
2
    domain = isl_union_set_universe(domain);
866
2
    node = isl_schedule_node_child(node, 0);
867
2
868
2
    schedule->band_forest = construct_band_list(node, domain, NULL);
869
2
    schedule->root = isl_schedule_tree_free(schedule->root);
870
2
  }
871
2
  return isl_band_list_dup(schedule->band_forest);
872
2
}
873
874
/* Call "fn" on each band in the schedule in depth-first post-order.
875
 */
876
int isl_schedule_foreach_band(__isl_keep isl_schedule *sched,
877
  int (*fn)(__isl_keep isl_band *band, void *user), void *user)
878
0
{
879
0
  int r;
880
0
  isl_band_list *forest;
881
0
882
0
  if (!sched)
883
0
    return -1;
884
0
885
0
  forest = isl_schedule_get_band_forest(sched);
886
0
  r = isl_band_list_foreach_band(forest, fn, user);
887
0
  isl_band_list_free(forest);
888
0
889
0
  return r;
890
0
}
891
892
static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
893
  __isl_keep isl_band_list *list);
894
895
static __isl_give isl_printer *print_band(__isl_take isl_printer *p,
896
  __isl_keep isl_band *band)
897
0
{
898
0
  isl_band_list *children;
899
0
900
0
  p = isl_printer_start_line(p);
901
0
  p = isl_printer_print_union_pw_multi_aff(p, band->pma);
902
0
  p = isl_printer_end_line(p);
903
0
904
0
  if (!isl_band_has_children(band))
905
0
    return p;
906
0
907
0
  children = isl_band_get_children(band);
908
0
909
0
  p = isl_printer_indent(p, 4);
910
0
  p = print_band_list(p, children);
911
0
  p = isl_printer_indent(p, -4);
912
0
913
0
  isl_band_list_free(children);
914
0
915
0
  return p;
916
0
}
917
918
static __isl_give isl_printer *print_band_list(__isl_take isl_printer *p,
919
  __isl_keep isl_band_list *list)
920
0
{
921
0
  int i, n;
922
0
923
0
  n = isl_band_list_n_band(list);
924
0
  for (i = 0; 
i < n0
;
++i0
) {
925
0
    isl_band *band;
926
0
    band = isl_band_list_get_band(list, i);
927
0
    p = print_band(p, band);
928
0
    isl_band_free(band);
929
0
  }
930
0
931
0
  return p;
932
0
}
933
934
/* Insert a band node with partial schedule "partial" between the domain
935
 * root node of "schedule" and its single child.
936
 * Return a pointer to the updated schedule.
937
 *
938
 * If any of the nodes in the tree depend on the set of outer band nodes
939
 * then we refuse to insert the band node.
940
 */
941
__isl_give isl_schedule *isl_schedule_insert_partial_schedule(
942
  __isl_take isl_schedule *schedule,
943
  __isl_take isl_multi_union_pw_aff *partial)
944
1.65k
{
945
1.65k
  isl_schedule_node *node;
946
1.65k
  int anchored;
947
1.65k
948
1.65k
  node = isl_schedule_get_root(schedule);
949
1.65k
  isl_schedule_free(schedule);
950
1.65k
  if (!node)
951
0
    goto error;
952
1.65k
  
if (1.65k
isl_schedule_node_get_type(node) != isl_schedule_node_domain1.65k
)
953
0
    isl_die(isl_schedule_node_get_ctx(node), isl_error_internal,
954
1.65k
      "root node not a domain node", goto error);
955
1.65k
956
1.65k
  node = isl_schedule_node_child(node, 0);
957
1.65k
  anchored = isl_schedule_node_is_subtree_anchored(node);
958
1.65k
  if (anchored < 0)
959
0
    goto error;
960
1.65k
  
if (1.65k
anchored1.65k
)
961
0
    isl_die(isl_schedule_node_get_ctx(node), isl_error_invalid,
962
1.65k
      "cannot insert band node in anchored subtree",
963
1.65k
      goto error);
964
1.65k
  node = isl_schedule_node_insert_partial_schedule(node, partial);
965
1.65k
966
1.65k
  schedule = isl_schedule_node_get_schedule(node);
967
1.65k
  isl_schedule_node_free(node);
968
1.65k
969
1.65k
  return schedule;
970
0
error:
971
0
  isl_schedule_node_free(node);
972
0
  isl_multi_union_pw_aff_free(partial);
973
0
  return NULL;
974
1.65k
}
975
976
/* Insert a context node with constraints "context" between the domain
977
 * root node of "schedule" and its single child.
978
 * Return a pointer to the updated schedule.
979
 */
980
__isl_give isl_schedule *isl_schedule_insert_context(
981
  __isl_take isl_schedule *schedule, __isl_take isl_set *context)
982
0
{
983
0
  isl_schedule_node *node;
984
0
985
0
  node = isl_schedule_get_root(schedule);
986
0
  isl_schedule_free(schedule);
987
0
  node = isl_schedule_node_child(node, 0);
988
0
  node = isl_schedule_node_insert_context(node, context);
989
0
  schedule = isl_schedule_node_get_schedule(node);
990
0
  isl_schedule_node_free(node);
991
0
992
0
  return schedule;
993
0
}
994
995
/* Insert a guard node with constraints "guard" between the domain
996
 * root node of "schedule" and its single child.
997
 * Return a pointer to the updated schedule.
998
 */
999
__isl_give isl_schedule *isl_schedule_insert_guard(
1000
  __isl_take isl_schedule *schedule, __isl_take isl_set *guard)
1001
0
{
1002
0
  isl_schedule_node *node;
1003
0
1004
0
  node = isl_schedule_get_root(schedule);
1005
0
  isl_schedule_free(schedule);
1006
0
  node = isl_schedule_node_child(node, 0);
1007
0
  node = isl_schedule_node_insert_guard(node, guard);
1008
0
  schedule = isl_schedule_node_get_schedule(node);
1009
0
  isl_schedule_node_free(node);
1010
0
1011
0
  return schedule;
1012
0
}
1013
1014
/* Return a tree with as top-level node a filter corresponding to "filter" and
1015
 * as child, the (single) child of "tree".
1016
 * However, if this single child is of type "type", then the filter is inserted
1017
 * in the children of this single child instead.
1018
 */
1019
static __isl_give isl_schedule_tree *insert_filter_in_child_of_type(
1020
  __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter,
1021
  enum isl_schedule_node_type type)
1022
1.83k
{
1023
1.83k
  if (
!isl_schedule_tree_has_children(tree)1.83k
) {
1024
1.03k
    isl_schedule_tree_free(tree);
1025
1.03k
    return isl_schedule_tree_from_filter(filter);
1026
0
  } else {
1027
804
    tree = isl_schedule_tree_child(tree, 0);
1028
804
  }
1029
1.83k
1030
804
  
if (804
isl_schedule_tree_get_type(tree) == type804
)
1031
399
    tree = isl_schedule_tree_children_insert_filter(tree, filter);
1032
804
  else
1033
405
    tree = isl_schedule_tree_insert_filter(tree, filter);
1034
804
1035
804
  return tree;
1036
1.83k
}
1037
1038
/* Construct a schedule that combines the schedules "schedule1" and "schedule2"
1039
 * with a top-level node (underneath the domain node) of type "type",
1040
 * either isl_schedule_node_sequence or isl_schedule_node_set.
1041
 * The domains of the two schedules are assumed to be disjoint.
1042
 *
1043
 * The new schedule has as domain the union of the domains of the two
1044
 * schedules.  The child of the domain node is a node of type "type"
1045
 * with two filters corresponding to the domains of the input schedules.
1046
 * If one (or both) of the top-level nodes of the two schedules is itself
1047
 * of type "type", then the filter is pushed into the children of that
1048
 * node and the sequence of set is flattened.
1049
 */
1050
__isl_give isl_schedule *isl_schedule_pair(enum isl_schedule_node_type type,
1051
  __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2)
1052
917
{
1053
917
  int disjoint;
1054
917
  isl_ctx *ctx;
1055
917
  enum isl_schedule_node_type root_type;
1056
917
  isl_schedule_tree *tree1, *tree2;
1057
917
  isl_union_set *filter1, *filter2, *domain;
1058
917
1059
917
  if (
!schedule1 || 917
!schedule2917
)
1060
0
    goto error;
1061
917
1062
917
  root_type = isl_schedule_tree_get_type(schedule1->root);
1063
917
  if (root_type != isl_schedule_node_domain)
1064
0
    isl_die(isl_schedule_get_ctx(schedule1), isl_error_internal,
1065
917
      "root node not a domain node", goto error);
1066
917
  root_type = isl_schedule_tree_get_type(schedule2->root);
1067
917
  if (root_type != isl_schedule_node_domain)
1068
0
    isl_die(isl_schedule_get_ctx(schedule1), isl_error_internal,
1069
917
      "root node not a domain node", goto error);
1070
917
1071
917
  ctx = isl_schedule_get_ctx(schedule1);
1072
917
  tree1 = isl_schedule_tree_copy(schedule1->root);
1073
917
  filter1 = isl_schedule_tree_domain_get_domain(tree1);
1074
917
  tree2 = isl_schedule_tree_copy(schedule2->root);
1075
917
  filter2 = isl_schedule_tree_domain_get_domain(tree2);
1076
917
1077
917
  isl_schedule_free(schedule1);
1078
917
  isl_schedule_free(schedule2);
1079
917
1080
917
  disjoint = isl_union_set_is_disjoint(filter1, filter2);
1081
917
  if (disjoint < 0)
1082
0
    filter1 = isl_union_set_free(filter1);
1083
917
  if (!disjoint)
1084
0
    isl_die(ctx, isl_error_invalid,
1085
917
      "schedule domains not disjoint",
1086
917
      filter1 = isl_union_set_free(filter1));
1087
917
1088
917
  domain = isl_union_set_union(isl_union_set_copy(filter1),
1089
917
            isl_union_set_copy(filter2));
1090
917
  filter1 = isl_union_set_gist(filter1, isl_union_set_copy(domain));
1091
917
  filter2 = isl_union_set_gist(filter2, isl_union_set_copy(domain));
1092
917
1093
917
  tree1 = insert_filter_in_child_of_type(tree1, filter1, type);
1094
917
  tree2 = insert_filter_in_child_of_type(tree2, filter2, type);
1095
917
1096
917
  tree1 = isl_schedule_tree_from_pair(type, tree1, tree2);
1097
917
  tree1 = isl_schedule_tree_insert_domain(tree1, domain);
1098
917
1099
917
  return isl_schedule_from_schedule_tree(ctx, tree1);
1100
0
error:
1101
0
  isl_schedule_free(schedule1);
1102
0
  isl_schedule_free(schedule2);
1103
0
  return NULL;
1104
917
}
1105
1106
/* Construct a schedule that combines the schedules "schedule1" and "schedule2"
1107
 * through a sequence node.
1108
 * The domains of the input schedules are assumed to be disjoint.
1109
 */
1110
__isl_give isl_schedule *isl_schedule_sequence(
1111
  __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2)
1112
917
{
1113
917
  return isl_schedule_pair(isl_schedule_node_sequence,
1114
917
        schedule1, schedule2);
1115
917
}
1116
1117
/* Construct a schedule that combines the schedules "schedule1" and "schedule2"
1118
 * through a set node.
1119
 * The domains of the input schedules are assumed to be disjoint.
1120
 */
1121
__isl_give isl_schedule *isl_schedule_set(
1122
  __isl_take isl_schedule *schedule1, __isl_take isl_schedule *schedule2)
1123
0
{
1124
0
  return isl_schedule_pair(isl_schedule_node_set, schedule1, schedule2);
1125
0
}
1126
1127
/* Print "schedule" to "p".
1128
 *
1129
 * If "schedule" was created from a schedule tree, then we print
1130
 * the schedule tree representation.  Otherwise, we print
1131
 * the band forest representation.
1132
 */
1133
__isl_give isl_printer *isl_printer_print_schedule(__isl_take isl_printer *p,
1134
  __isl_keep isl_schedule *schedule)
1135
0
{
1136
0
  isl_band_list *forest;
1137
0
1138
0
  if (!schedule)
1139
0
    return isl_printer_free(p);
1140
0
1141
0
  
if (0
schedule->root0
)
1142
0
    return isl_printer_print_schedule_tree(p, schedule->root);
1143
0
1144
0
  forest = isl_schedule_get_band_forest(schedule);
1145
0
1146
0
  p = print_band_list(p, forest);
1147
0
1148
0
  isl_band_list_free(forest);
1149
0
1150
0
  return p;
1151
0
}
1152
1153
#undef BASE
1154
#define BASE schedule
1155
#include <print_templ_yaml.c>