Coverage Report

Created: 2019-04-21 11:35

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_schedule_tree.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2013-2014 Ecole Normale Superieure
3
 * Copyright 2014      INRIA Rocquencourt
4
 * Copyright 2016      INRIA Paris
5
 *
6
 * Use of this software is governed by the MIT license
7
 *
8
 * Written by Sven Verdoolaege,
9
 * Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
10
 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
11
 * B.P. 105 - 78153 Le Chesnay, France
12
 * and Centre de Recherche Inria de Paris, 2 rue Simone Iff - Voie DQ12,
13
 * CS 42112, 75589 Paris Cedex 12, France
14
 */
15
16
#include <isl/id.h>
17
#include <isl/val.h>
18
#include <isl/space.h>
19
#include <isl/map.h>
20
#include <isl_schedule_band.h>
21
#include <isl_schedule_private.h>
22
23
#undef EL
24
#define EL isl_schedule_tree
25
26
#include <isl_list_templ.h>
27
28
#undef BASE
29
#define BASE schedule_tree
30
31
#include <isl_list_templ.c>
32
33
/* Is "tree" the leaf of a schedule tree?
34
 */
35
int isl_schedule_tree_is_leaf(__isl_keep isl_schedule_tree *tree)
36
34.3k
{
37
34.3k
  return isl_schedule_tree_get_type(tree) == isl_schedule_node_leaf;
38
34.3k
}
39
40
/* Create a new schedule tree of type "type".
41
 * The caller is responsible for filling in the type specific fields and
42
 * the children.
43
 *
44
 * By default, the single node tree does not have any anchored nodes.
45
 * The caller is responsible for updating the anchored field if needed.
46
 */
47
static __isl_give isl_schedule_tree *isl_schedule_tree_alloc(isl_ctx *ctx,
48
  enum isl_schedule_node_type type)
49
13.6k
{
50
13.6k
  isl_schedule_tree *tree;
51
13.6k
52
13.6k
  if (type == isl_schedule_node_error)
53
0
    return NULL;
54
13.6k
55
13.6k
  tree = isl_calloc_type(ctx, isl_schedule_tree);
56
13.6k
  if (!tree)
57
0
    return NULL;
58
13.6k
59
13.6k
  tree->ref = 1;
60
13.6k
  tree->ctx = ctx;
61
13.6k
  isl_ctx_ref(ctx);
62
13.6k
  tree->type = type;
63
13.6k
  tree->anchored = 0;
64
13.6k
65
13.6k
  return tree;
66
13.6k
}
67
68
/* Return a fresh copy of "tree".
69
 */
70
__isl_take isl_schedule_tree *isl_schedule_tree_dup(
71
  __isl_keep isl_schedule_tree *tree)
72
6.56k
{
73
6.56k
  isl_ctx *ctx;
74
6.56k
  isl_schedule_tree *dup;
75
6.56k
76
6.56k
  if (!tree)
77
0
    return NULL;
78
6.56k
79
6.56k
  ctx = isl_schedule_tree_get_ctx(tree);
80
6.56k
  dup = isl_schedule_tree_alloc(ctx, tree->type);
81
6.56k
  if (!dup)
82
0
    return NULL;
83
6.56k
84
6.56k
  switch (tree->type) {
85
6.56k
  case isl_schedule_node_error:
86
0
    isl_die(ctx, isl_error_internal,
87
0
      "allocation should have failed",
88
0
      return isl_schedule_tree_free(dup));
89
1.20k
  case isl_schedule_node_band:
90
1.20k
    dup->band = isl_schedule_band_copy(tree->band);
91
1.20k
    if (!dup->band)
92
0
      return isl_schedule_tree_free(dup);
93
1.20k
    break;
94
1.20k
  case isl_schedule_node_context:
95
0
    dup->context = isl_set_copy(tree->context);
96
0
    if (!dup->context)
97
0
      return isl_schedule_tree_free(dup);
98
0
    break;
99
2.31k
  case isl_schedule_node_domain:
100
2.31k
    dup->domain = isl_union_set_copy(tree->domain);
101
2.31k
    if (!dup->domain)
102
0
      return isl_schedule_tree_free(dup);
103
2.31k
    break;
104
2.31k
  case isl_schedule_node_expansion:
105
2
    dup->contraction =
106
2
      isl_union_pw_multi_aff_copy(tree->contraction);
107
2
    dup->expansion = isl_union_map_copy(tree->expansion);
108
2
    if (!dup->contraction || !dup->expansion)
109
0
      return isl_schedule_tree_free(dup);
110
2
    break;
111
15
  case isl_schedule_node_extension:
112
15
    dup->extension = isl_union_map_copy(tree->extension);
113
15
    if (!dup->extension)
114
0
      return isl_schedule_tree_free(dup);
115
15
    break;
116
1.64k
  case isl_schedule_node_filter:
117
1.64k
    dup->filter = isl_union_set_copy(tree->filter);
118
1.64k
    if (!dup->filter)
119
0
      return isl_schedule_tree_free(dup);
120
1.64k
    break;
121
1.64k
  case isl_schedule_node_guard:
122
0
    dup->guard = isl_set_copy(tree->guard);
123
0
    if (!dup->guard)
124
0
      return isl_schedule_tree_free(dup);
125
0
    break;
126
347
  case isl_schedule_node_mark:
127
347
    dup->mark = isl_id_copy(tree->mark);
128
347
    if (!dup->mark)
129
0
      return isl_schedule_tree_free(dup);
130
347
    break;
131
1.03k
  case isl_schedule_node_leaf:
132
1.03k
  case isl_schedule_node_sequence:
133
1.03k
  case isl_schedule_node_set:
134
1.03k
    break;
135
6.56k
  }
136
6.56k
137
6.56k
  if (tree->children) {
138
4.65k
    dup->children = isl_schedule_tree_list_copy(tree->children);
139
4.65k
    if (!dup->children)
140
0
      return isl_schedule_tree_free(dup);
141
6.56k
  }
142
6.56k
  dup->anchored = tree->anchored;
143
6.56k
144
6.56k
  return dup;
145
6.56k
}
146
147
/* Return an isl_schedule_tree that is equal to "tree" and that has only
148
 * a single reference.
149
 */
150
__isl_give isl_schedule_tree *isl_schedule_tree_cow(
151
  __isl_take isl_schedule_tree *tree)
152
8.85k
{
153
8.85k
  if (!tree)
154
0
    return NULL;
155
8.85k
156
8.85k
  if (tree->ref == 1)
157
2.28k
    return tree;
158
6.56k
  tree->ref--;
159
6.56k
  return isl_schedule_tree_dup(tree);
160
6.56k
}
161
162
/* Return a new reference to "tree".
163
 */
164
__isl_give isl_schedule_tree *isl_schedule_tree_copy(
165
  __isl_keep isl_schedule_tree *tree)
166
219k
{
167
219k
  if (!tree)
168
0
    return NULL;
169
219k
170
219k
  tree->ref++;
171
219k
  return tree;
172
219k
}
173
174
/* Free "tree" and return NULL.
175
 */
176
__isl_null isl_schedule_tree *isl_schedule_tree_free(
177
  __isl_take isl_schedule_tree *tree)
178
227k
{
179
227k
  if (!tree)
180
0
    return NULL;
181
227k
  if (--tree->ref > 0)
182
213k
    return NULL;
183
13.6k
184
13.6k
  switch (tree->type) {
185
13.6k
  case isl_schedule_node_band:
186
1.92k
    isl_schedule_band_free(tree->band);
187
1.92k
    break;
188
13.6k
  case isl_schedule_node_context:
189
0
    isl_set_free(tree->context);
190
0
    break;
191
13.6k
  case isl_schedule_node_domain:
192
4.32k
    isl_union_set_free(tree->domain);
193
4.32k
    break;
194
13.6k
  case isl_schedule_node_expansion:
195
5
    isl_union_pw_multi_aff_free(tree->contraction);
196
5
    isl_union_map_free(tree->expansion);
197
5
    break;
198
13.6k
  case isl_schedule_node_extension:
199
27
    isl_union_map_free(tree->extension);
200
27
    break;
201
13.6k
  case isl_schedule_node_filter:
202
2.35k
    isl_union_set_free(tree->filter);
203
2.35k
    break;
204
13.6k
  case isl_schedule_node_guard:
205
0
    isl_set_free(tree->guard);
206
0
    break;
207
13.6k
  case isl_schedule_node_mark:
208
392
    isl_id_free(tree->mark);
209
392
    break;
210
13.6k
  case isl_schedule_node_sequence:
211
4.64k
  case isl_schedule_node_set:
212
4.64k
  case isl_schedule_node_error:
213
4.64k
  case isl_schedule_node_leaf:
214
4.64k
    break;
215
13.6k
  }
216
13.6k
  isl_schedule_tree_list_free(tree->children);
217
13.6k
  isl_ctx_deref(tree->ctx);
218
13.6k
  free(tree);
219
13.6k
220
13.6k
  return NULL;
221
13.6k
}
222
223
/* Create and return a new leaf schedule tree.
224
 */
225
__isl_give isl_schedule_tree *isl_schedule_tree_leaf(isl_ctx *ctx)
226
3.18k
{
227
3.18k
  return isl_schedule_tree_alloc(ctx, isl_schedule_node_leaf);
228
3.18k
}
229
230
/* Create a new band schedule tree referring to "band"
231
 * with no children.
232
 */
233
__isl_give isl_schedule_tree *isl_schedule_tree_from_band(
234
  __isl_take isl_schedule_band *band)
235
722
{
236
722
  isl_ctx *ctx;
237
722
  isl_schedule_tree *tree;
238
722
239
722
  if (!band)
240
0
    return NULL;
241
722
242
722
  ctx = isl_schedule_band_get_ctx(band);
243
722
  tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_band);
244
722
  if (!tree)
245
0
    goto error;
246
722
247
722
  tree->band = band;
248
722
  tree->anchored = isl_schedule_band_is_anchored(band);
249
722
250
722
  return tree;
251
0
error:
252
0
  isl_schedule_band_free(band);
253
0
  return NULL;
254
722
}
255
256
/* Create a new context schedule tree with the given context and no children.
257
 * Since the context references the outer schedule dimension,
258
 * the tree is anchored.
259
 */
260
__isl_give isl_schedule_tree *isl_schedule_tree_from_context(
261
  __isl_take isl_set *context)
262
0
{
263
0
  isl_ctx *ctx;
264
0
  isl_schedule_tree *tree;
265
0
266
0
  if (!context)
267
0
    return NULL;
268
0
269
0
  ctx = isl_set_get_ctx(context);
270
0
  tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_context);
271
0
  if (!tree)
272
0
    goto error;
273
0
274
0
  tree->context = context;
275
0
  tree->anchored = 1;
276
0
277
0
  return tree;
278
0
error:
279
0
  isl_set_free(context);
280
0
  return NULL;
281
0
}
282
283
/* Create a new domain schedule tree with the given domain and no children.
284
 */
285
__isl_give isl_schedule_tree *isl_schedule_tree_from_domain(
286
  __isl_take isl_union_set *domain)
287
2.00k
{
288
2.00k
  isl_ctx *ctx;
289
2.00k
  isl_schedule_tree *tree;
290
2.00k
291
2.00k
  if (!domain)
292
0
    return NULL;
293
2.00k
294
2.00k
  ctx = isl_union_set_get_ctx(domain);
295
2.00k
  tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_domain);
296
2.00k
  if (!tree)
297
0
    goto error;
298
2.00k
299
2.00k
  tree->domain = domain;
300
2.00k
301
2.00k
  return tree;
302
0
error:
303
0
  isl_union_set_free(domain);
304
0
  return NULL;
305
2.00k
}
306
307
/* Create a new expansion schedule tree with the given contraction and
308
 * expansion and no children.
309
 */
310
__isl_give isl_schedule_tree *isl_schedule_tree_from_expansion(
311
  __isl_take isl_union_pw_multi_aff *contraction,
312
  __isl_take isl_union_map *expansion)
313
3
{
314
3
  isl_ctx *ctx;
315
3
  isl_schedule_tree *tree;
316
3
317
3
  if (!contraction || !expansion)
318
0
    goto error;
319
3
320
3
  ctx = isl_union_map_get_ctx(expansion);
321
3
  tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_expansion);
322
3
  if (!tree)
323
0
    goto error;
324
3
325
3
  tree->contraction = contraction;
326
3
  tree->expansion = expansion;
327
3
328
3
  return tree;
329
0
error:
330
0
  isl_union_pw_multi_aff_free(contraction);
331
0
  isl_union_map_free(expansion);
332
0
  return NULL;
333
3
}
334
335
/* Create a new extension schedule tree with the given extension and
336
 * no children.
337
 * Since the domain of the extension refers to the outer schedule dimension,
338
 * the tree is anchored.
339
 */
340
__isl_give isl_schedule_tree *isl_schedule_tree_from_extension(
341
  __isl_take isl_union_map *extension)
342
12
{
343
12
  isl_ctx *ctx;
344
12
  isl_schedule_tree *tree;
345
12
346
12
  if (!extension)
347
0
    return NULL;
348
12
349
12
  ctx = isl_union_map_get_ctx(extension);
350
12
  tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_extension);
351
12
  if (!tree)
352
0
    goto error;
353
12
354
12
  tree->extension = extension;
355
12
  tree->anchored = 1;
356
12
357
12
  return tree;
358
0
error:
359
0
  isl_union_map_free(extension);
360
0
  return NULL;
361
12
}
362
363
/* Create a new filter schedule tree with the given filter and no children.
364
 */
365
__isl_give isl_schedule_tree *isl_schedule_tree_from_filter(
366
  __isl_take isl_union_set *filter)
367
705
{
368
705
  isl_ctx *ctx;
369
705
  isl_schedule_tree *tree;
370
705
371
705
  if (!filter)
372
0
    return NULL;
373
705
374
705
  ctx = isl_union_set_get_ctx(filter);
375
705
  tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_filter);
376
705
  if (!tree)
377
0
    goto error;
378
705
379
705
  tree->filter = filter;
380
705
381
705
  return tree;
382
0
error:
383
0
  isl_union_set_free(filter);
384
0
  return NULL;
385
705
}
386
387
/* Create a new guard schedule tree with the given guard and no children.
388
 * Since the guard references the outer schedule dimension,
389
 * the tree is anchored.
390
 */
391
__isl_give isl_schedule_tree *isl_schedule_tree_from_guard(
392
  __isl_take isl_set *guard)
393
0
{
394
0
  isl_ctx *ctx;
395
0
  isl_schedule_tree *tree;
396
0
397
0
  if (!guard)
398
0
    return NULL;
399
0
400
0
  ctx = isl_set_get_ctx(guard);
401
0
  tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_guard);
402
0
  if (!tree)
403
0
    goto error;
404
0
405
0
  tree->guard = guard;
406
0
  tree->anchored = 1;
407
0
408
0
  return tree;
409
0
error:
410
0
  isl_set_free(guard);
411
0
  return NULL;
412
0
}
413
414
/* Create a new mark schedule tree with the given mark identifier and
415
 * no children.
416
 */
417
__isl_give isl_schedule_tree *isl_schedule_tree_from_mark(
418
  __isl_take isl_id *mark)
419
45
{
420
45
  isl_ctx *ctx;
421
45
  isl_schedule_tree *tree;
422
45
423
45
  if (!mark)
424
0
    return NULL;
425
45
426
45
  ctx = isl_id_get_ctx(mark);
427
45
  tree = isl_schedule_tree_alloc(ctx, isl_schedule_node_mark);
428
45
  if (!tree)
429
0
    goto error;
430
45
431
45
  tree->mark = mark;
432
45
433
45
  return tree;
434
0
error:
435
0
  isl_id_free(mark);
436
0
  return NULL;
437
45
}
438
439
/* Does "tree" have any node that depends on its position
440
 * in the complete schedule tree?
441
 */
442
isl_bool isl_schedule_tree_is_subtree_anchored(
443
  __isl_keep isl_schedule_tree *tree)
444
1.36k
{
445
1.36k
  return tree ? tree->anchored : 
isl_bool_error0
;
446
1.36k
}
447
448
/* Does the root node of "tree" depend on its position in the complete
449
 * schedule tree?
450
 * Band nodes may be anchored depending on the associated AST build options.
451
 * Context, extension and guard nodes are always anchored.
452
 */
453
int isl_schedule_tree_is_anchored(__isl_keep isl_schedule_tree *tree)
454
6.29k
{
455
6.29k
  if (!tree)
456
0
    return -1;
457
6.29k
458
6.29k
  switch (isl_schedule_tree_get_type(tree)) {
459
6.29k
  case isl_schedule_node_error:
460
0
    return -1;
461
6.29k
  case isl_schedule_node_band:
462
995
    return isl_schedule_band_is_anchored(tree->band);
463
6.29k
  case isl_schedule_node_context:
464
21
  case isl_schedule_node_extension:
465
21
  case isl_schedule_node_guard:
466
21
    return 1;
467
5.28k
  case isl_schedule_node_domain:
468
5.28k
  case isl_schedule_node_expansion:
469
5.28k
  case isl_schedule_node_filter:
470
5.28k
  case isl_schedule_node_leaf:
471
5.28k
  case isl_schedule_node_mark:
472
5.28k
  case isl_schedule_node_sequence:
473
5.28k
  case isl_schedule_node_set:
474
5.28k
    return 0;
475
0
  }
476
0
477
0
  isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
478
0
    "unhandled case", return -1);
479
0
}
480
481
/* Update the anchored field of "tree" based on whether the root node
482
 * itself in anchored and the anchored fields of the children.
483
 *
484
 * This function should be called whenever the children of a tree node
485
 * are changed or the anchoredness of the tree root itself changes.
486
 */
487
__isl_give isl_schedule_tree *isl_schedule_tree_update_anchored(
488
  __isl_take isl_schedule_tree *tree)
489
6.25k
{
490
6.25k
  int i, n;
491
6.25k
  int anchored;
492
6.25k
493
6.25k
  if (!tree)
494
0
    return NULL;
495
6.25k
496
6.25k
  anchored = isl_schedule_tree_is_anchored(tree);
497
6.25k
  if (anchored < 0)
498
0
    return isl_schedule_tree_free(tree);
499
6.25k
500
6.25k
  n = isl_schedule_tree_list_n_schedule_tree(tree->children);
501
22.0k
  for (i = 0; !anchored && 
i < n21.7k
;
++i15.8k
) {
502
15.8k
    isl_schedule_tree *child;
503
15.8k
504
15.8k
    child = isl_schedule_tree_get_child(tree, i);
505
15.8k
    if (!child)
506
0
      return isl_schedule_tree_free(tree);
507
15.8k
    anchored = child->anchored;
508
15.8k
    isl_schedule_tree_free(child);
509
15.8k
  }
510
6.25k
511
6.25k
  if (anchored == tree->anchored)
512
6.18k
    return tree;
513
70
  tree = isl_schedule_tree_cow(tree);
514
70
  if (!tree)
515
0
    return NULL;
516
70
  tree->anchored = anchored;
517
70
  return tree;
518
70
}
519
520
/* Create a new tree of the given type (isl_schedule_node_sequence or
521
 * isl_schedule_node_set) with the given children.
522
 */
523
__isl_give isl_schedule_tree *isl_schedule_tree_from_children(
524
  enum isl_schedule_node_type type,
525
  __isl_take isl_schedule_tree_list *list)
526
438
{
527
438
  isl_ctx *ctx;
528
438
  isl_schedule_tree *tree;
529
438
530
438
  if (!list)
531
0
    return NULL;
532
438
533
438
  ctx = isl_schedule_tree_list_get_ctx(list);
534
438
  tree = isl_schedule_tree_alloc(ctx, type);
535
438
  if (!tree)
536
0
    goto error;
537
438
538
438
  tree->children = list;
539
438
  tree = isl_schedule_tree_update_anchored(tree);
540
438
541
438
  return tree;
542
0
error:
543
0
  isl_schedule_tree_list_free(list);
544
0
  return NULL;
545
438
}
546
547
/* Construct a tree with a root node of type "type" and as children
548
 * "tree1" and "tree2".
549
 * If the root of one (or both) of the input trees is itself of type "type",
550
 * then the tree is replaced by its children.
551
 */
552
__isl_give isl_schedule_tree *isl_schedule_tree_from_pair(
553
  enum isl_schedule_node_type type, __isl_take isl_schedule_tree *tree1,
554
  __isl_take isl_schedule_tree *tree2)
555
379
{
556
379
  isl_ctx *ctx;
557
379
  isl_schedule_tree_list *list;
558
379
559
379
  if (!tree1 || !tree2)
560
0
    goto error;
561
379
562
379
  ctx = isl_schedule_tree_get_ctx(tree1);
563
379
  if (isl_schedule_tree_get_type(tree1) == type) {
564
182
    list = isl_schedule_tree_list_copy(tree1->children);
565
182
    isl_schedule_tree_free(tree1);
566
197
  } else {
567
197
    list = isl_schedule_tree_list_alloc(ctx, 2);
568
197
    list = isl_schedule_tree_list_add(list, tree1);
569
197
  }
570
379
  if (isl_schedule_tree_get_type(tree2) == type) {
571
0
    isl_schedule_tree_list *children;
572
0
573
0
    children = isl_schedule_tree_list_copy(tree2->children);
574
0
    list = isl_schedule_tree_list_concat(list, children);
575
0
    isl_schedule_tree_free(tree2);
576
379
  } else {
577
379
    list = isl_schedule_tree_list_add(list, tree2);
578
379
  }
579
379
580
379
  return isl_schedule_tree_from_children(type, list);
581
0
error:
582
0
  isl_schedule_tree_free(tree1);
583
0
  isl_schedule_tree_free(tree2);
584
0
  return NULL;
585
379
}
586
587
/* Construct a tree with a sequence root node and as children
588
 * "tree1" and "tree2".
589
 * If the root of one (or both) of the input trees is itself a sequence,
590
 * then the tree is replaced by its children.
591
 */
592
__isl_give isl_schedule_tree *isl_schedule_tree_sequence_pair(
593
  __isl_take isl_schedule_tree *tree1,
594
  __isl_take isl_schedule_tree *tree2)
595
6
{
596
6
  return isl_schedule_tree_from_pair(isl_schedule_node_sequence,
597
6
            tree1, tree2);
598
6
}
599
600
/* Construct a tree with a set root node and as children
601
 * "tree1" and "tree2".
602
 * If the root of one (or both) of the input trees is itself a set,
603
 * then the tree is replaced by its children.
604
 */
605
__isl_give isl_schedule_tree *isl_schedule_tree_set_pair(
606
  __isl_take isl_schedule_tree *tree1,
607
  __isl_take isl_schedule_tree *tree2)
608
0
{
609
0
  return isl_schedule_tree_from_pair(isl_schedule_node_set, tree1, tree2);
610
0
}
611
612
/* Return the isl_ctx to which "tree" belongs.
613
 */
614
isl_ctx *isl_schedule_tree_get_ctx(__isl_keep isl_schedule_tree *tree)
615
43.3k
{
616
43.3k
  return tree ? tree->ctx : NULL;
617
43.3k
}
618
619
/* Return the type of the root of the tree or isl_schedule_node_error
620
 * on error.
621
 */
622
enum isl_schedule_node_type isl_schedule_tree_get_type(
623
  __isl_keep isl_schedule_tree *tree)
624
98.7k
{
625
98.7k
  return tree ? tree->type : 
isl_schedule_node_error0
;
626
98.7k
}
627
628
/* Are "tree1" and "tree2" obviously equal to each other?
629
 */
630
isl_bool isl_schedule_tree_plain_is_equal(__isl_keep isl_schedule_tree *tree1,
631
  __isl_keep isl_schedule_tree *tree2)
632
0
{
633
0
  isl_bool equal;
634
0
  int i, n;
635
0
636
0
  if (!tree1 || !tree2)
637
0
    return isl_bool_error;
638
0
  if (tree1 == tree2)
639
0
    return isl_bool_true;
640
0
  if (tree1->type != tree2->type)
641
0
    return isl_bool_false;
642
0
643
0
  switch (tree1->type) {
644
0
  case isl_schedule_node_band:
645
0
    equal = isl_schedule_band_plain_is_equal(tree1->band,
646
0
              tree2->band);
647
0
    break;
648
0
  case isl_schedule_node_context:
649
0
    equal = isl_set_is_equal(tree1->context, tree2->context);
650
0
    break;
651
0
  case isl_schedule_node_domain:
652
0
    equal = isl_union_set_is_equal(tree1->domain, tree2->domain);
653
0
    break;
654
0
  case isl_schedule_node_expansion:
655
0
    equal = isl_union_map_is_equal(tree1->expansion,
656
0
            tree2->expansion);
657
0
    if (equal >= 0 && equal)
658
0
      equal = isl_union_pw_multi_aff_plain_is_equal(
659
0
            tree1->contraction, tree2->contraction);
660
0
    break;
661
0
  case isl_schedule_node_extension:
662
0
    equal = isl_union_map_is_equal(tree1->extension,
663
0
            tree2->extension);
664
0
    break;
665
0
  case isl_schedule_node_filter:
666
0
    equal = isl_union_set_is_equal(tree1->filter, tree2->filter);
667
0
    break;
668
0
  case isl_schedule_node_guard:
669
0
    equal = isl_set_is_equal(tree1->guard, tree2->guard);
670
0
    break;
671
0
  case isl_schedule_node_mark:
672
0
    equal = tree1->mark == tree2->mark;
673
0
    break;
674
0
  case isl_schedule_node_leaf:
675
0
  case isl_schedule_node_sequence:
676
0
  case isl_schedule_node_set:
677
0
    equal = isl_bool_true;
678
0
    break;
679
0
  case isl_schedule_node_error:
680
0
    equal = isl_bool_error;
681
0
    break;
682
0
  }
683
0
684
0
  if (equal < 0 || !equal)
685
0
    return equal;
686
0
687
0
  n = isl_schedule_tree_n_children(tree1);
688
0
  if (n != isl_schedule_tree_n_children(tree2))
689
0
    return isl_bool_false;
690
0
  for (i = 0; i < n; ++i) {
691
0
    isl_schedule_tree *child1, *child2;
692
0
693
0
    child1 = isl_schedule_tree_get_child(tree1, i);
694
0
    child2 = isl_schedule_tree_get_child(tree2, i);
695
0
    equal = isl_schedule_tree_plain_is_equal(child1, child2);
696
0
    isl_schedule_tree_free(child1);
697
0
    isl_schedule_tree_free(child2);
698
0
699
0
    if (equal < 0 || !equal)
700
0
      return equal;
701
0
  }
702
0
703
0
  return isl_bool_true;
704
0
}
705
706
/* Does "tree" have any children, other than an implicit leaf.
707
 */
708
int isl_schedule_tree_has_children(__isl_keep isl_schedule_tree *tree)
709
17.0k
{
710
17.0k
  if (!tree)
711
0
    return -1;
712
17.0k
713
17.0k
  return tree->children != NULL;
714
17.0k
}
715
716
/* Return the number of children of "tree", excluding implicit leaves.
717
 */
718
int isl_schedule_tree_n_children(__isl_keep isl_schedule_tree *tree)
719
680
{
720
680
  if (!tree)
721
0
    return -1;
722
680
723
680
  return isl_schedule_tree_list_n_schedule_tree(tree->children);
724
680
}
725
726
/* Return a copy of the (explicit) child at position "pos" of "tree".
727
 */
728
__isl_give isl_schedule_tree *isl_schedule_tree_get_child(
729
  __isl_keep isl_schedule_tree *tree, int pos)
730
26.3k
{
731
26.3k
  if (!tree)
732
0
    return NULL;
733
26.3k
  if (!tree->children)
734
26.3k
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_internal,
735
26.3k
      "schedule tree has no explicit children", return NULL);
736
26.3k
  return isl_schedule_tree_list_get_schedule_tree(tree->children, pos);
737
26.3k
}
738
739
/* Return a copy of the (explicit) child at position "pos" of "tree" and
740
 * free "tree".
741
 */
742
__isl_give isl_schedule_tree *isl_schedule_tree_child(
743
  __isl_take isl_schedule_tree *tree, int pos)
744
397
{
745
397
  isl_schedule_tree *child;
746
397
747
397
  child = isl_schedule_tree_get_child(tree, pos);
748
397
  isl_schedule_tree_free(tree);
749
397
  return child;
750
397
}
751
752
/* Remove all (explicit) children from "tree".
753
 */
754
__isl_give isl_schedule_tree *isl_schedule_tree_reset_children(
755
  __isl_take isl_schedule_tree *tree)
756
53
{
757
53
  tree = isl_schedule_tree_cow(tree);
758
53
  if (!tree)
759
0
    return NULL;
760
53
  tree->children = isl_schedule_tree_list_free(tree->children);
761
53
  return tree;
762
53
}
763
764
/* Remove the child at position "pos" from the children of "tree".
765
 * If there was only one child to begin with, then remove all children.
766
 */
767
__isl_give isl_schedule_tree *isl_schedule_tree_drop_child(
768
  __isl_take isl_schedule_tree *tree, int pos)
769
81
{
770
81
  int n;
771
81
772
81
  tree = isl_schedule_tree_cow(tree);
773
81
  if (!tree)
774
0
    return NULL;
775
81
776
81
  if (!isl_schedule_tree_has_children(tree))
777
81
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
778
81
      "tree does not have any explicit children",
779
81
      return isl_schedule_tree_free(tree));
780
81
  n = isl_schedule_tree_list_n_schedule_tree(tree->children);
781
81
  if (pos < 0 || pos >= n)
782
81
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
783
81
      "position out of bounds",
784
81
      return isl_schedule_tree_free(tree));
785
81
  if (n == 1)
786
0
    return isl_schedule_tree_reset_children(tree);
787
81
788
81
  tree->children = isl_schedule_tree_list_drop(tree->children, pos, 1);
789
81
  if (!tree->children)
790
0
    return isl_schedule_tree_free(tree);
791
81
792
81
  return tree;
793
81
}
794
795
/* Replace the child at position "pos" of "tree" by "child".
796
 *
797
 * If the new child is a leaf, then it is not explicitly
798
 * recorded in the list of children.  Instead, the list of children
799
 * (which is assumed to have only one element) is removed.
800
 * Note that the children of set and sequence nodes are always
801
 * filters, so they cannot be replaced by empty trees.
802
 */
803
__isl_give isl_schedule_tree *isl_schedule_tree_replace_child(
804
  __isl_take isl_schedule_tree *tree, int pos,
805
  __isl_take isl_schedule_tree *child)
806
6.47k
{
807
6.47k
  tree = isl_schedule_tree_cow(tree);
808
6.47k
  if (!tree || !child)
809
0
    goto error;
810
6.47k
811
6.47k
  if (isl_schedule_tree_is_leaf(child)) {
812
664
    isl_schedule_tree_free(child);
813
664
    if (!tree->children && 
pos == 0612
)
814
612
      return tree;
815
52
    if (isl_schedule_tree_n_children(tree) != 1)
816
52
      
isl_die0
(isl_schedule_tree_get_ctx(tree),
817
52
        isl_error_internal,
818
52
        "can only replace single child by leaf",
819
52
        goto error);
820
52
    return isl_schedule_tree_reset_children(tree);
821
5.80k
  }
822
5.80k
823
5.80k
  if (!tree->children && 
pos == 01.37k
)
824
1.37k
    tree->children =
825
1.37k
      isl_schedule_tree_list_from_schedule_tree(child);
826
4.43k
  else
827
4.43k
    tree->children = isl_schedule_tree_list_set_schedule_tree(
828
4.43k
        tree->children, pos, child);
829
5.80k
830
5.80k
  if (!tree->children)
831
0
    return isl_schedule_tree_free(tree);
832
5.80k
  tree = isl_schedule_tree_update_anchored(tree);
833
5.80k
834
5.80k
  return tree;
835
0
error:
836
0
  isl_schedule_tree_free(tree);
837
0
  isl_schedule_tree_free(child);
838
0
  return NULL;
839
5.80k
}
840
841
/* Replace the (explicit) children of "tree" by "children"?
842
 */
843
__isl_give isl_schedule_tree *isl_schedule_tree_set_children(
844
  __isl_take isl_schedule_tree *tree,
845
  __isl_take isl_schedule_tree_list *children)
846
1
{
847
1
  tree = isl_schedule_tree_cow(tree);
848
1
  if (!tree || !children)
849
0
    goto error;
850
1
  isl_schedule_tree_list_free(tree->children);
851
1
  tree->children = children;
852
1
  return tree;
853
0
error:
854
0
  isl_schedule_tree_free(tree);
855
0
  isl_schedule_tree_list_free(children);
856
0
  return NULL;
857
1
}
858
859
/* Create a new band schedule tree referring to "band"
860
 * with "tree" as single child.
861
 */
862
__isl_give isl_schedule_tree *isl_schedule_tree_insert_band(
863
  __isl_take isl_schedule_tree *tree, __isl_take isl_schedule_band *band)
864
722
{
865
722
  isl_schedule_tree *res;
866
722
867
722
  res = isl_schedule_tree_from_band(band);
868
722
  return isl_schedule_tree_replace_child(res, 0, tree);
869
722
}
870
871
/* Create a new context schedule tree with the given context and
872
 * with "tree" as single child.
873
 */
874
__isl_give isl_schedule_tree *isl_schedule_tree_insert_context(
875
  __isl_take isl_schedule_tree *tree, __isl_take isl_set *context)
876
0
{
877
0
  isl_schedule_tree *res;
878
0
879
0
  res = isl_schedule_tree_from_context(context);
880
0
  return isl_schedule_tree_replace_child(res, 0, tree);
881
0
}
882
883
/* Create a new domain schedule tree with the given domain and
884
 * with "tree" as single child.
885
 */
886
__isl_give isl_schedule_tree *isl_schedule_tree_insert_domain(
887
  __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *domain)
888
373
{
889
373
  isl_schedule_tree *res;
890
373
891
373
  res = isl_schedule_tree_from_domain(domain);
892
373
  return isl_schedule_tree_replace_child(res, 0, tree);
893
373
}
894
895
/* Create a new expansion schedule tree with the given contraction and
896
 * expansion and with "tree" as single child.
897
 */
898
__isl_give isl_schedule_tree *isl_schedule_tree_insert_expansion(
899
  __isl_take isl_schedule_tree *tree,
900
  __isl_take isl_union_pw_multi_aff *contraction,
901
  __isl_take isl_union_map *expansion)
902
3
{
903
3
  isl_schedule_tree *res;
904
3
905
3
  res = isl_schedule_tree_from_expansion(contraction, expansion);
906
3
  return isl_schedule_tree_replace_child(res, 0, tree);
907
3
}
908
909
/* Create a new extension schedule tree with the given extension and
910
 * with "tree" as single child.
911
 */
912
__isl_give isl_schedule_tree *isl_schedule_tree_insert_extension(
913
  __isl_take isl_schedule_tree *tree, __isl_take isl_union_map *extension)
914
6
{
915
6
  isl_schedule_tree *res;
916
6
917
6
  res = isl_schedule_tree_from_extension(extension);
918
6
  return isl_schedule_tree_replace_child(res, 0, tree);
919
6
}
920
921
/* Create a new filter schedule tree with the given filter and single child.
922
 *
923
 * If the root of "tree" is itself a filter node, then the two
924
 * filter nodes are merged into one node.
925
 */
926
__isl_give isl_schedule_tree *isl_schedule_tree_insert_filter(
927
  __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter)
928
1.14k
{
929
1.14k
  isl_schedule_tree *res;
930
1.14k
931
1.14k
  if (isl_schedule_tree_get_type(tree) == isl_schedule_node_filter) {
932
873
    isl_union_set *tree_filter;
933
873
934
873
    tree_filter = isl_schedule_tree_filter_get_filter(tree);
935
873
    tree_filter = isl_union_set_intersect(tree_filter, filter);
936
873
    tree = isl_schedule_tree_filter_set_filter(tree, tree_filter);
937
873
    return tree;
938
873
  }
939
275
940
275
  res = isl_schedule_tree_from_filter(filter);
941
275
  return isl_schedule_tree_replace_child(res, 0, tree);
942
275
}
943
944
/* Insert a filter node with filter set "filter"
945
 * in each of the children of "tree".
946
 */
947
__isl_give isl_schedule_tree *isl_schedule_tree_children_insert_filter(
948
  __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter)
949
182
{
950
182
  int i, n;
951
182
952
182
  if (!tree || !filter)
953
0
    goto error;
954
182
955
182
  n = isl_schedule_tree_n_children(tree);
956
1.05k
  for (i = 0; i < n; 
++i873
) {
957
873
    isl_schedule_tree *child;
958
873
959
873
    child = isl_schedule_tree_get_child(tree, i);
960
873
    child = isl_schedule_tree_insert_filter(child,
961
873
                isl_union_set_copy(filter));
962
873
    tree = isl_schedule_tree_replace_child(tree, i, child);
963
873
  }
964
182
965
182
  isl_union_set_free(filter);
966
182
  return tree;
967
0
error:
968
0
  isl_union_set_free(filter);
969
0
  isl_schedule_tree_free(tree);
970
0
  return NULL;
971
182
}
972
973
/* Create a new guard schedule tree with the given guard and
974
 * with "tree" as single child.
975
 */
976
__isl_give isl_schedule_tree *isl_schedule_tree_insert_guard(
977
  __isl_take isl_schedule_tree *tree, __isl_take isl_set *guard)
978
0
{
979
0
  isl_schedule_tree *res;
980
0
981
0
  res = isl_schedule_tree_from_guard(guard);
982
0
  return isl_schedule_tree_replace_child(res, 0, tree);
983
0
}
984
985
/* Create a new mark schedule tree with the given mark identifier and
986
 * single child.
987
 */
988
__isl_give isl_schedule_tree *isl_schedule_tree_insert_mark(
989
  __isl_take isl_schedule_tree *tree, __isl_take isl_id *mark)
990
45
{
991
45
  isl_schedule_tree *res;
992
45
993
45
  res = isl_schedule_tree_from_mark(mark);
994
45
  return isl_schedule_tree_replace_child(res, 0, tree);
995
45
}
996
997
/* Return the number of members in the band tree root.
998
 */
999
unsigned isl_schedule_tree_band_n_member(__isl_keep isl_schedule_tree *tree)
1000
20.6k
{
1001
20.6k
  if (!tree)
1002
0
    return 0;
1003
20.6k
1004
20.6k
  if (tree->type != isl_schedule_node_band)
1005
20.6k
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1006
20.6k
      "not a band node", return 0);
1007
20.6k
1008
20.6k
  return isl_schedule_band_n_member(tree->band);
1009
20.6k
}
1010
1011
/* Is the band member at position "pos" of the band tree root
1012
 * marked coincident?
1013
 */
1014
isl_bool isl_schedule_tree_band_member_get_coincident(
1015
  __isl_keep isl_schedule_tree *tree, int pos)
1016
457
{
1017
457
  if (!tree)
1018
0
    return isl_bool_error;
1019
457
1020
457
  if (tree->type != isl_schedule_node_band)
1021
457
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1022
457
      "not a band node", return isl_bool_error);
1023
457
1024
457
  return isl_schedule_band_member_get_coincident(tree->band, pos);
1025
457
}
1026
1027
/* Mark the given band member as being coincident or not
1028
 * according to "coincident".
1029
 */
1030
__isl_give isl_schedule_tree *isl_schedule_tree_band_member_set_coincident(
1031
  __isl_take isl_schedule_tree *tree, int pos, int coincident)
1032
119
{
1033
119
  if (!tree)
1034
0
    return NULL;
1035
119
  if (tree->type != isl_schedule_node_band)
1036
119
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1037
119
      "not a band node", return isl_schedule_tree_free(tree));
1038
119
  if (isl_schedule_tree_band_member_get_coincident(tree, pos) ==
1039
119
                    coincident)
1040
0
    return tree;
1041
119
  tree = isl_schedule_tree_cow(tree);
1042
119
  if (!tree)
1043
0
    return NULL;
1044
119
1045
119
  tree->band = isl_schedule_band_member_set_coincident(tree->band, pos,
1046
119
              coincident);
1047
119
  if (!tree->band)
1048
0
    return isl_schedule_tree_free(tree);
1049
119
  return tree;
1050
119
}
1051
1052
/* Is the band tree root marked permutable?
1053
 */
1054
isl_bool isl_schedule_tree_band_get_permutable(
1055
  __isl_keep isl_schedule_tree *tree)
1056
376
{
1057
376
  if (!tree)
1058
0
    return isl_bool_error;
1059
376
1060
376
  if (tree->type != isl_schedule_node_band)
1061
376
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1062
376
      "not a band node", return isl_bool_error);
1063
376
1064
376
  return isl_schedule_band_get_permutable(tree->band);
1065
376
}
1066
1067
/* Mark the band tree root permutable or not according to "permutable"?
1068
 */
1069
__isl_give isl_schedule_tree *isl_schedule_tree_band_set_permutable(
1070
  __isl_take isl_schedule_tree *tree, int permutable)
1071
105
{
1072
105
  if (!tree)
1073
0
    return NULL;
1074
105
  if (tree->type != isl_schedule_node_band)
1075
105
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1076
105
      "not a band node", return isl_schedule_tree_free(tree));
1077
105
  if (isl_schedule_tree_band_get_permutable(tree) == permutable)
1078
0
    return tree;
1079
105
  tree = isl_schedule_tree_cow(tree);
1080
105
  if (!tree)
1081
0
    return NULL;
1082
105
1083
105
  tree->band = isl_schedule_band_set_permutable(tree->band, permutable);
1084
105
  if (!tree->band)
1085
0
    return isl_schedule_tree_free(tree);
1086
105
  return tree;
1087
105
}
1088
1089
/* Return the schedule space of the band tree root.
1090
 */
1091
__isl_give isl_space *isl_schedule_tree_band_get_space(
1092
  __isl_keep isl_schedule_tree *tree)
1093
91
{
1094
91
  if (!tree)
1095
0
    return NULL;
1096
91
1097
91
  if (tree->type != isl_schedule_node_band)
1098
91
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1099
91
      "not a band node", return NULL);
1100
91
1101
91
  return isl_schedule_band_get_space(tree->band);
1102
91
}
1103
1104
/* Intersect the domain of the band schedule of the band tree root
1105
 * with "domain".
1106
 */
1107
__isl_give isl_schedule_tree *isl_schedule_tree_band_intersect_domain(
1108
  __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *domain)
1109
2
{
1110
2
  if (!tree || !domain)
1111
0
    goto error;
1112
2
1113
2
  if (tree->type != isl_schedule_node_band)
1114
2
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1115
2
      "not a band node", goto error);
1116
2
1117
2
  tree->band = isl_schedule_band_intersect_domain(tree->band, domain);
1118
2
  if (!tree->band)
1119
0
    return isl_schedule_tree_free(tree);
1120
2
1121
2
  return tree;
1122
0
error:
1123
0
  isl_schedule_tree_free(tree);
1124
0
  isl_union_set_free(domain);
1125
0
  return NULL;
1126
2
}
1127
1128
/* Return the schedule of the band tree root in isolation.
1129
 */
1130
__isl_give isl_multi_union_pw_aff *isl_schedule_tree_band_get_partial_schedule(
1131
  __isl_keep isl_schedule_tree *tree)
1132
2.22k
{
1133
2.22k
  if (!tree)
1134
0
    return NULL;
1135
2.22k
1136
2.22k
  if (tree->type != isl_schedule_node_band)
1137
2.22k
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1138
2.22k
      "not a band node", return NULL);
1139
2.22k
1140
2.22k
  return isl_schedule_band_get_partial_schedule(tree->band);
1141
2.22k
}
1142
1143
/* Replace the schedule of the band tree root by "schedule".
1144
 */
1145
__isl_give isl_schedule_tree *isl_schedule_tree_band_set_partial_schedule(
1146
  __isl_take isl_schedule_tree *tree,
1147
  __isl_take isl_multi_union_pw_aff *schedule)
1148
2
{
1149
2
  tree = isl_schedule_tree_cow(tree);
1150
2
  if (!tree || !schedule)
1151
0
    goto error;
1152
2
1153
2
  if (tree->type != isl_schedule_node_band)
1154
2
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1155
2
      "not a band node", return NULL);
1156
2
  tree->band = isl_schedule_band_set_partial_schedule(tree->band,
1157
2
                schedule);
1158
2
1159
2
  return tree;
1160
0
error:
1161
0
  isl_schedule_tree_free(tree);
1162
0
  isl_multi_union_pw_aff_free(schedule);
1163
0
  return NULL;
1164
2
}
1165
1166
/* Return the loop AST generation type for the band member
1167
 * of the band tree root at position "pos".
1168
 */
1169
enum isl_ast_loop_type isl_schedule_tree_band_member_get_ast_loop_type(
1170
  __isl_keep isl_schedule_tree *tree, int pos)
1171
240
{
1172
240
  if (!tree)
1173
0
    return isl_ast_loop_error;
1174
240
1175
240
  if (tree->type != isl_schedule_node_band)
1176
240
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1177
240
      "not a band node", return isl_ast_loop_error);
1178
240
1179
240
  return isl_schedule_band_member_get_ast_loop_type(tree->band, pos);
1180
240
}
1181
1182
/* Set the loop AST generation type for the band member of the band tree root
1183
 * at position "pos" to "type".
1184
 */
1185
__isl_give isl_schedule_tree *isl_schedule_tree_band_member_set_ast_loop_type(
1186
  __isl_take isl_schedule_tree *tree, int pos,
1187
  enum isl_ast_loop_type type)
1188
0
{
1189
0
  tree = isl_schedule_tree_cow(tree);
1190
0
  if (!tree)
1191
0
    return NULL;
1192
0
1193
0
  if (tree->type != isl_schedule_node_band)
1194
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1195
0
      "not a band node", return isl_schedule_tree_free(tree));
1196
0
1197
0
  tree->band = isl_schedule_band_member_set_ast_loop_type(tree->band,
1198
0
                pos, type);
1199
0
  if (!tree->band)
1200
0
    return isl_schedule_tree_free(tree);
1201
0
1202
0
  return tree;
1203
0
}
1204
1205
/* Return the loop AST generation type for the band member
1206
 * of the band tree root at position "pos" for the isolated part.
1207
 */
1208
enum isl_ast_loop_type isl_schedule_tree_band_member_get_isolate_ast_loop_type(
1209
  __isl_keep isl_schedule_tree *tree, int pos)
1210
321
{
1211
321
  if (!tree)
1212
0
    return isl_ast_loop_error;
1213
321
1214
321
  if (tree->type != isl_schedule_node_band)
1215
321
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1216
321
      "not a band node", return isl_ast_loop_error);
1217
321
1218
321
  return isl_schedule_band_member_get_isolate_ast_loop_type(tree->band,
1219
321
                  pos);
1220
321
}
1221
1222
/* Set the loop AST generation type for the band member of the band tree root
1223
 * at position "pos" for the isolated part to "type".
1224
 */
1225
__isl_give isl_schedule_tree *
1226
isl_schedule_tree_band_member_set_isolate_ast_loop_type(
1227
  __isl_take isl_schedule_tree *tree, int pos,
1228
  enum isl_ast_loop_type type)
1229
0
{
1230
0
  tree = isl_schedule_tree_cow(tree);
1231
0
  if (!tree)
1232
0
    return NULL;
1233
0
1234
0
  if (tree->type != isl_schedule_node_band)
1235
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1236
0
      "not a band node", return isl_schedule_tree_free(tree));
1237
0
1238
0
  tree->band = isl_schedule_band_member_set_isolate_ast_loop_type(
1239
0
              tree->band, pos, type);
1240
0
  if (!tree->band)
1241
0
    return isl_schedule_tree_free(tree);
1242
0
1243
0
  return tree;
1244
0
}
1245
1246
/* Return the AST build options associated to the band tree root.
1247
 */
1248
__isl_give isl_union_set *isl_schedule_tree_band_get_ast_build_options(
1249
  __isl_keep isl_schedule_tree *tree)
1250
0
{
1251
0
  if (!tree)
1252
0
    return NULL;
1253
0
1254
0
  if (tree->type != isl_schedule_node_band)
1255
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1256
0
      "not a band node", return NULL);
1257
0
1258
0
  return isl_schedule_band_get_ast_build_options(tree->band);
1259
0
}
1260
1261
/* Replace the AST build options associated to band tree root by "options".
1262
 * Updated the anchored field if the anchoredness of the root node itself
1263
 * changes.
1264
 */
1265
__isl_give isl_schedule_tree *isl_schedule_tree_band_set_ast_build_options(
1266
  __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *options)
1267
20
{
1268
20
  int was_anchored;
1269
20
1270
20
  tree = isl_schedule_tree_cow(tree);
1271
20
  if (!tree || !options)
1272
0
    goto error;
1273
20
1274
20
  if (tree->type != isl_schedule_node_band)
1275
20
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1276
20
      "not a band node", goto error);
1277
20
1278
20
  was_anchored = isl_schedule_tree_is_anchored(tree);
1279
20
  tree->band = isl_schedule_band_set_ast_build_options(tree->band,
1280
20
                options);
1281
20
  if (!tree->band)
1282
0
    return isl_schedule_tree_free(tree);
1283
20
  if (isl_schedule_tree_is_anchored(tree) != was_anchored)
1284
10
    tree = isl_schedule_tree_update_anchored(tree);
1285
20
1286
20
  return tree;
1287
0
error:
1288
0
  isl_schedule_tree_free(tree);
1289
0
  isl_union_set_free(options);
1290
0
  return NULL;
1291
20
}
1292
1293
/* Return the "isolate" option associated to the band tree root of "tree",
1294
 * which is assumed to appear at schedule depth "depth".
1295
 */
1296
__isl_give isl_set *isl_schedule_tree_band_get_ast_isolate_option(
1297
  __isl_keep isl_schedule_tree *tree, int depth)
1298
611
{
1299
611
  if (!tree)
1300
0
    return NULL;
1301
611
1302
611
  if (tree->type != isl_schedule_node_band)
1303
611
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1304
611
      "not a band node", return NULL);
1305
611
1306
611
  return isl_schedule_band_get_ast_isolate_option(tree->band, depth);
1307
611
}
1308
1309
/* Return the context of the context tree root.
1310
 */
1311
__isl_give isl_set *isl_schedule_tree_context_get_context(
1312
  __isl_keep isl_schedule_tree *tree)
1313
0
{
1314
0
  if (!tree)
1315
0
    return NULL;
1316
0
1317
0
  if (tree->type != isl_schedule_node_context)
1318
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1319
0
      "not a context node", return NULL);
1320
0
1321
0
  return isl_set_copy(tree->context);
1322
0
}
1323
1324
/* Return the domain of the domain tree root.
1325
 */
1326
__isl_give isl_union_set *isl_schedule_tree_domain_get_domain(
1327
  __isl_keep isl_schedule_tree *tree)
1328
5.24k
{
1329
5.24k
  if (!tree)
1330
0
    return NULL;
1331
5.24k
1332
5.24k
  if (tree->type != isl_schedule_node_domain)
1333
5.24k
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1334
5.24k
      "not a domain node", return NULL);
1335
5.24k
1336
5.24k
  return isl_union_set_copy(tree->domain);
1337
5.24k
}
1338
1339
/* Replace the domain of domain tree root "tree" by "domain".
1340
 */
1341
__isl_give isl_schedule_tree *isl_schedule_tree_domain_set_domain(
1342
  __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *domain)
1343
449
{
1344
449
  tree = isl_schedule_tree_cow(tree);
1345
449
  if (!tree || !domain)
1346
0
    goto error;
1347
449
1348
449
  if (tree->type != isl_schedule_node_domain)
1349
449
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1350
449
      "not a domain node", goto error);
1351
449
1352
449
  isl_union_set_free(tree->domain);
1353
449
  tree->domain = domain;
1354
449
1355
449
  return tree;
1356
0
error:
1357
0
  isl_schedule_tree_free(tree);
1358
0
  isl_union_set_free(domain);
1359
0
  return NULL;
1360
449
}
1361
1362
/* Return the contraction of the expansion tree root.
1363
 */
1364
__isl_give isl_union_pw_multi_aff *isl_schedule_tree_expansion_get_contraction(
1365
  __isl_keep isl_schedule_tree *tree)
1366
8
{
1367
8
  if (!tree)
1368
0
    return NULL;
1369
8
1370
8
  if (tree->type != isl_schedule_node_expansion)
1371
8
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1372
8
      "not an expansion node", return NULL);
1373
8
1374
8
  return isl_union_pw_multi_aff_copy(tree->contraction);
1375
8
}
1376
1377
/* Return the expansion of the expansion tree root.
1378
 */
1379
__isl_give isl_union_map *isl_schedule_tree_expansion_get_expansion(
1380
  __isl_keep isl_schedule_tree *tree)
1381
13
{
1382
13
  if (!tree)
1383
0
    return NULL;
1384
13
1385
13
  if (tree->type != isl_schedule_node_expansion)
1386
13
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1387
13
      "not an expansion node", return NULL);
1388
13
1389
13
  return isl_union_map_copy(tree->expansion);
1390
13
}
1391
1392
/* Replace the contraction and the expansion of the expansion tree root "tree"
1393
 * by "contraction" and "expansion".
1394
 */
1395
__isl_give isl_schedule_tree *
1396
isl_schedule_tree_expansion_set_contraction_and_expansion(
1397
  __isl_take isl_schedule_tree *tree,
1398
  __isl_take isl_union_pw_multi_aff *contraction,
1399
  __isl_take isl_union_map *expansion)
1400
1
{
1401
1
  tree = isl_schedule_tree_cow(tree);
1402
1
  if (!tree || !contraction || !expansion)
1403
0
    goto error;
1404
1
1405
1
  if (tree->type != isl_schedule_node_expansion)
1406
1
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1407
1
      "not an expansion node", return NULL);
1408
1
1409
1
  isl_union_pw_multi_aff_free(tree->contraction);
1410
1
  tree->contraction = contraction;
1411
1
  isl_union_map_free(tree->expansion);
1412
1
  tree->expansion = expansion;
1413
1
1414
1
  return tree;
1415
0
error:
1416
0
  isl_schedule_tree_free(tree);
1417
0
  isl_union_pw_multi_aff_free(contraction);
1418
0
  isl_union_map_free(expansion);
1419
0
  return NULL;
1420
1
}
1421
1422
/* Return the extension of the extension tree root.
1423
 */
1424
__isl_give isl_union_map *isl_schedule_tree_extension_get_extension(
1425
  __isl_take isl_schedule_tree *tree)
1426
18
{
1427
18
  if (!tree)
1428
0
    return NULL;
1429
18
1430
18
  if (tree->type != isl_schedule_node_extension)
1431
18
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1432
18
      "not an extension node", return NULL);
1433
18
1434
18
  return isl_union_map_copy(tree->extension);
1435
18
}
1436
1437
/* Replace the extension of extension tree root "tree" by "extension".
1438
 */
1439
__isl_give isl_schedule_tree *isl_schedule_tree_extension_set_extension(
1440
  __isl_take isl_schedule_tree *tree, __isl_take isl_union_map *extension)
1441
0
{
1442
0
  tree = isl_schedule_tree_cow(tree);
1443
0
  if (!tree || !extension)
1444
0
    goto error;
1445
0
1446
0
  if (tree->type != isl_schedule_node_extension)
1447
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1448
0
      "not an extension node", return NULL);
1449
0
  isl_union_map_free(tree->extension);
1450
0
  tree->extension = extension;
1451
0
1452
0
  return tree;
1453
0
error:
1454
0
  isl_schedule_tree_free(tree);
1455
0
  isl_union_map_free(extension);
1456
0
  return NULL;
1457
0
}
1458
1459
/* Return the filter of the filter tree root.
1460
 */
1461
__isl_give isl_union_set *isl_schedule_tree_filter_get_filter(
1462
  __isl_keep isl_schedule_tree *tree)
1463
6.37k
{
1464
6.37k
  if (!tree)
1465
0
    return NULL;
1466
6.37k
1467
6.37k
  if (tree->type != isl_schedule_node_filter)
1468
6.37k
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1469
6.37k
      "not a filter node", return NULL);
1470
6.37k
1471
6.37k
  return isl_union_set_copy(tree->filter);
1472
6.37k
}
1473
1474
/* Replace the filter of the filter tree root by "filter".
1475
 */
1476
__isl_give isl_schedule_tree *isl_schedule_tree_filter_set_filter(
1477
  __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *filter)
1478
1.11k
{
1479
1.11k
  tree = isl_schedule_tree_cow(tree);
1480
1.11k
  if (!tree || !filter)
1481
0
    goto error;
1482
1.11k
1483
1.11k
  if (tree->type != isl_schedule_node_filter)
1484
1.11k
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1485
1.11k
      "not a filter node", return NULL);
1486
1.11k
1487
1.11k
  isl_union_set_free(tree->filter);
1488
1.11k
  tree->filter = filter;
1489
1.11k
1490
1.11k
  return tree;
1491
0
error:
1492
0
  isl_schedule_tree_free(tree);
1493
0
  isl_union_set_free(filter);
1494
0
  return NULL;
1495
1.11k
}
1496
1497
/* Return the guard of the guard tree root.
1498
 */
1499
__isl_give isl_set *isl_schedule_tree_guard_get_guard(
1500
  __isl_take isl_schedule_tree *tree)
1501
0
{
1502
0
  if (!tree)
1503
0
    return NULL;
1504
0
1505
0
  if (tree->type != isl_schedule_node_guard)
1506
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1507
0
      "not a guard node", return NULL);
1508
0
1509
0
  return isl_set_copy(tree->guard);
1510
0
}
1511
1512
/* Return the mark identifier of the mark tree root "tree".
1513
 */
1514
__isl_give isl_id *isl_schedule_tree_mark_get_id(
1515
  __isl_keep isl_schedule_tree *tree)
1516
48
{
1517
48
  if (!tree)
1518
0
    return NULL;
1519
48
1520
48
  if (tree->type != isl_schedule_node_mark)
1521
48
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1522
48
      "not a mark node", return NULL);
1523
48
1524
48
  return isl_id_copy(tree->mark);
1525
48
}
1526
1527
/* Set dim to the range dimension of "map" and abort the search.
1528
 */
1529
static isl_stat set_range_dim(__isl_take isl_map *map, void *user)
1530
1.89k
{
1531
1.89k
  int *dim = user;
1532
1.89k
1533
1.89k
  *dim = isl_map_dim(map, isl_dim_out);
1534
1.89k
  isl_map_free(map);
1535
1.89k
1536
1.89k
  return isl_stat_error;
1537
1.89k
}
1538
1539
/* Return the dimension of the range of "umap".
1540
 * "umap" is assumed not to be empty and
1541
 * all maps inside "umap" are assumed to have the same range.
1542
 *
1543
 * We extract the range dimension from the first map in "umap".
1544
 */
1545
static int range_dim(__isl_keep isl_union_map *umap)
1546
1.89k
{
1547
1.89k
  int dim = -1;
1548
1.89k
1549
1.89k
  if (!umap)
1550
0
    return -1;
1551
1.89k
  if (isl_union_map_n_map(umap) == 0)
1552
1.89k
    
isl_die0
(isl_union_map_get_ctx(umap), isl_error_internal,
1553
1.89k
      "unexpected empty input", return -1);
1554
1.89k
1555
1.89k
  isl_union_map_foreach_map(umap, &set_range_dim, &dim);
1556
1.89k
1557
1.89k
  return dim;
1558
1.89k
}
1559
1560
/* Append an "extra" number of zeros to the range of "umap" and
1561
 * return the result.
1562
 */
1563
static __isl_give isl_union_map *append_range(__isl_take isl_union_map *umap,
1564
  int extra)
1565
711
{
1566
711
  isl_union_set *dom;
1567
711
  isl_space *space;
1568
711
  isl_multi_val *mv;
1569
711
  isl_union_pw_multi_aff *suffix;
1570
711
  isl_union_map *universe;
1571
711
  isl_union_map *suffix_umap;
1572
711
1573
711
  universe = isl_union_map_universe(isl_union_map_copy(umap));
1574
711
  dom = isl_union_map_domain(universe);
1575
711
  space = isl_union_set_get_space(dom);
1576
711
  space = isl_space_set_from_params(space);
1577
711
  space = isl_space_add_dims(space, isl_dim_set, extra);
1578
711
  mv = isl_multi_val_zero(space);
1579
711
1580
711
  suffix = isl_union_pw_multi_aff_multi_val_on_domain(dom, mv);
1581
711
  suffix_umap = isl_union_map_from_union_pw_multi_aff(suffix);
1582
711
  umap = isl_union_map_flat_range_product(umap, suffix_umap);
1583
711
1584
711
  return umap;
1585
711
}
1586
1587
/* Should we skip the root of "tree" while looking for the first
1588
 * descendant with schedule information?
1589
 * That is, is it impossible to derive any information about
1590
 * the iteration domain from this node?
1591
 *
1592
 * We do not want to skip leaf or error nodes because there is
1593
 * no point in looking any deeper from these nodes.
1594
 * We can only extract partial iteration domain information
1595
 * from an extension node, but extension nodes are not supported
1596
 * by the caller and it will error out on them.
1597
 */
1598
static int domain_less(__isl_keep isl_schedule_tree *tree)
1599
531
{
1600
531
  enum isl_schedule_node_type type;
1601
531
1602
531
  type = isl_schedule_tree_get_type(tree);
1603
531
  switch (type) {
1604
531
  case isl_schedule_node_band:
1605
391
    return isl_schedule_tree_band_n_member(tree) == 0;
1606
531
  case isl_schedule_node_context:
1607
4
  case isl_schedule_node_guard:
1608
4
  case isl_schedule_node_mark:
1609
4
    return 1;
1610
136
  case isl_schedule_node_leaf:
1611
136
  case isl_schedule_node_error:
1612
136
  case isl_schedule_node_domain:
1613
136
  case isl_schedule_node_expansion:
1614
136
  case isl_schedule_node_extension:
1615
136
  case isl_schedule_node_filter:
1616
136
  case isl_schedule_node_set:
1617
136
  case isl_schedule_node_sequence:
1618
136
    return 0;
1619
0
  }
1620
0
1621
0
  isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1622
0
    "unhandled case", return 0);
1623
0
}
1624
1625
/* Move down to the first descendant of "tree" that contains any schedule
1626
 * information or return "leaf" if there is no such descendant.
1627
 */
1628
__isl_give isl_schedule_tree *isl_schedule_tree_first_schedule_descendant(
1629
  __isl_take isl_schedule_tree *tree, __isl_keep isl_schedule_tree *leaf)
1630
527
{
1631
531
  while (domain_less(tree)) {
1632
4
    if (!isl_schedule_tree_has_children(tree)) {
1633
0
      isl_schedule_tree_free(tree);
1634
0
      return isl_schedule_tree_copy(leaf);
1635
0
    }
1636
4
    tree = isl_schedule_tree_child(tree, 0);
1637
4
  }
1638
527
1639
527
  return tree;
1640
527
}
1641
1642
static __isl_give isl_union_map *subtree_schedule_extend(
1643
  __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer);
1644
1645
/* Extend the schedule map "outer" with the subtree schedule
1646
 * of the (single) child of "tree", if any.
1647
 *
1648
 * If "tree" does not have any descendants (apart from those that
1649
 * do not carry any schedule information), then we simply return "outer".
1650
 * Otherwise, we extend the schedule map "outer" with the subtree schedule
1651
 * of the single child.
1652
 */
1653
static __isl_give isl_union_map *subtree_schedule_extend_child(
1654
  __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer)
1655
3.10k
{
1656
3.10k
  isl_schedule_tree *child;
1657
3.10k
  isl_union_map *res;
1658
3.10k
1659
3.10k
  if (!tree)
1660
0
    return isl_union_map_free(outer);
1661
3.10k
  if (!isl_schedule_tree_has_children(tree))
1662
2.01k
    return outer;
1663
1.09k
  child = isl_schedule_tree_get_child(tree, 0);
1664
1.09k
  if (!child)
1665
0
    return isl_union_map_free(outer);
1666
1.09k
  res = subtree_schedule_extend(child, outer);
1667
1.09k
  isl_schedule_tree_free(child);
1668
1.09k
  return res;
1669
1.09k
}
1670
1671
/* Extract the parameter space from one of the children of "tree",
1672
 * which are assumed to be filters.
1673
 */
1674
static __isl_give isl_space *extract_space_from_filter_child(
1675
  __isl_keep isl_schedule_tree *tree)
1676
125
{
1677
125
  isl_space *space;
1678
125
  isl_union_set *dom;
1679
125
  isl_schedule_tree *child;
1680
125
1681
125
  child = isl_schedule_tree_list_get_schedule_tree(tree->children, 0);
1682
125
  dom = isl_schedule_tree_filter_get_filter(child);
1683
125
  space = isl_union_set_get_space(dom);
1684
125
  isl_union_set_free(dom);
1685
125
  isl_schedule_tree_free(child);
1686
125
1687
125
  return space;
1688
125
}
1689
1690
/* Extend the schedule map "outer" with the subtree schedule
1691
 * of a set or sequence node.
1692
 *
1693
 * The schedule for the set or sequence node itself is composed of
1694
 * pieces of the form
1695
 *
1696
 *  filter -> []
1697
 *
1698
 * or
1699
 *
1700
 *  filter -> [index]
1701
 *
1702
 * The first form is used if there is only a single child or
1703
 * if the current node is a set node and the schedule_separate_components
1704
 * option is not set.
1705
 *
1706
 * Each of the pieces above is extended with the subtree schedule of
1707
 * the child of the corresponding filter, if any, padded with zeros
1708
 * to ensure that all pieces have the same range dimension.
1709
 */
1710
static __isl_give isl_union_map *subtree_schedule_extend_from_children(
1711
  __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer)
1712
400
{
1713
400
  int i, n;
1714
400
  int dim;
1715
400
  int separate;
1716
400
  isl_ctx *ctx;
1717
400
  isl_val *v = NULL;
1718
400
  isl_multi_val *mv;
1719
400
  isl_space *space;
1720
400
  isl_union_map *umap;
1721
400
1722
400
  if (!tree)
1723
0
    return NULL;
1724
400
1725
400
  ctx = isl_schedule_tree_get_ctx(tree);
1726
400
  if (!tree->children)
1727
400
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1728
400
      "missing children", return NULL);
1729
400
  n = isl_schedule_tree_list_n_schedule_tree(tree->children);
1730
400
  if (n == 0)
1731
400
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1732
400
      "missing children", return NULL);
1733
400
1734
400
  separate = n > 1 && (tree->type == isl_schedule_node_sequence ||
1735
400
          
isl_options_get_schedule_separate_components(ctx)10
);
1736
400
1737
400
  space = isl_space_params_alloc(ctx, 0);
1738
400
1739
400
  umap = isl_union_map_empty(isl_space_copy(space));
1740
400
  space = isl_space_set_from_params(space);
1741
400
  if (separate) {
1742
400
    space = isl_space_add_dims(space, isl_dim_set, 1);
1743
400
    v = isl_val_zero(ctx);
1744
400
  }
1745
400
  mv = isl_multi_val_zero(space);
1746
400
1747
400
  dim = isl_multi_val_dim(mv, isl_dim_set);
1748
2.29k
  for (i = 0; i < n; 
++i1.89k
) {
1749
1.89k
    isl_multi_val *mv_copy;
1750
1.89k
    isl_union_pw_multi_aff *upma;
1751
1.89k
    isl_union_map *umap_i;
1752
1.89k
    isl_union_set *dom;
1753
1.89k
    isl_schedule_tree *child;
1754
1.89k
    int dim_i;
1755
1.89k
    int empty;
1756
1.89k
1757
1.89k
    child = isl_schedule_tree_list_get_schedule_tree(
1758
1.89k
              tree->children, i);
1759
1.89k
    dom = isl_schedule_tree_filter_get_filter(child);
1760
1.89k
1761
1.89k
    if (separate) {
1762
1.89k
      mv = isl_multi_val_set_val(mv, 0, isl_val_copy(v));
1763
1.89k
      v = isl_val_add_ui(v, 1);
1764
1.89k
    }
1765
1.89k
    mv_copy = isl_multi_val_copy(mv);
1766
1.89k
    space = isl_union_set_get_space(dom);
1767
1.89k
    mv_copy = isl_multi_val_align_params(mv_copy, space);
1768
1.89k
    upma = isl_union_pw_multi_aff_multi_val_on_domain(dom, mv_copy);
1769
1.89k
    umap_i = isl_union_map_from_union_pw_multi_aff(upma);
1770
1.89k
    umap_i = isl_union_map_flat_range_product(
1771
1.89k
              isl_union_map_copy(outer), umap_i);
1772
1.89k
    umap_i = subtree_schedule_extend_child(child, umap_i);
1773
1.89k
    isl_schedule_tree_free(child);
1774
1.89k
1775
1.89k
    empty = isl_union_map_is_empty(umap_i);
1776
1.89k
    if (empty < 0)
1777
0
      umap_i = isl_union_map_free(umap_i);
1778
1.89k
    else if (empty) {
1779
0
      isl_union_map_free(umap_i);
1780
0
      continue;
1781
0
    }
1782
1.89k
1783
1.89k
    dim_i = range_dim(umap_i);
1784
1.89k
    if (dim_i < 0) {
1785
0
      umap = isl_union_map_free(umap);
1786
1.89k
    } else if (dim < dim_i) {
1787
519
      umap = append_range(umap, dim_i - dim);
1788
519
      dim = dim_i;
1789
1.37k
    } else if (dim_i < dim) {
1790
192
      umap_i = append_range(umap_i, dim - dim_i);
1791
192
    }
1792
1.89k
    umap = isl_union_map_union(umap, umap_i);
1793
1.89k
  }
1794
400
1795
400
  isl_val_free(v);
1796
400
  isl_multi_val_free(mv);
1797
400
  isl_union_map_free(outer);
1798
400
1799
400
  return umap;
1800
400
}
1801
1802
/* Extend the schedule map "outer" with the subtree schedule of "tree".
1803
 *
1804
 * If the root of the tree is a set or a sequence, then we extend
1805
 * the schedule map in subtree_schedule_extend_from_children.
1806
 * Otherwise, we extend the schedule map with the partial schedule
1807
 * corresponding to the root of the tree and then continue with
1808
 * the single child of this root.
1809
 * In the special case of an expansion, the schedule map is "extended"
1810
 * by applying the expansion to the domain of the schedule map.
1811
 */
1812
static __isl_give isl_union_map *subtree_schedule_extend(
1813
  __isl_keep isl_schedule_tree *tree, __isl_take isl_union_map *outer)
1814
1.60k
{
1815
1.60k
  isl_multi_union_pw_aff *mupa;
1816
1.60k
  isl_union_map *umap;
1817
1.60k
  isl_union_set *domain;
1818
1.60k
1819
1.60k
  if (!tree)
1820
0
    return NULL;
1821
1.60k
1822
1.60k
  switch (tree->type) {
1823
1.60k
  case isl_schedule_node_error:
1824
0
    return isl_union_map_free(outer);
1825
1.60k
  case isl_schedule_node_extension:
1826
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1827
0
      "cannot construct subtree schedule of tree "
1828
0
      "with extension nodes",
1829
0
      return isl_union_map_free(outer));
1830
21
  case isl_schedule_node_context:
1831
21
  case isl_schedule_node_guard:
1832
21
  case isl_schedule_node_mark:
1833
21
    return subtree_schedule_extend_child(tree, outer);
1834
1.18k
  case isl_schedule_node_band:
1835
1.18k
    if (isl_schedule_tree_band_n_member(tree) == 0)
1836
0
      return subtree_schedule_extend_child(tree, outer);
1837
1.18k
    mupa = isl_schedule_band_get_partial_schedule(tree->band);
1838
1.18k
    umap = isl_union_map_from_multi_union_pw_aff(mupa);
1839
1.18k
    outer = isl_union_map_flat_range_product(outer, umap);
1840
1.18k
    umap = subtree_schedule_extend_child(tree, outer);
1841
1.18k
    break;
1842
1.18k
  case isl_schedule_node_domain:
1843
0
    domain = isl_schedule_tree_domain_get_domain(tree);
1844
0
    umap = isl_union_map_from_domain(domain);
1845
0
    outer = isl_union_map_flat_range_product(outer, umap);
1846
0
    umap = subtree_schedule_extend_child(tree, outer);
1847
0
    break;
1848
1.18k
  case isl_schedule_node_expansion:
1849
2
    umap = isl_schedule_tree_expansion_get_expansion(tree);
1850
2
    outer = isl_union_map_apply_domain(outer, umap);
1851
2
    umap = subtree_schedule_extend_child(tree, outer);
1852
2
    break;
1853
1.18k
  case isl_schedule_node_filter:
1854
0
    domain = isl_schedule_tree_filter_get_filter(tree);
1855
0
    umap = isl_union_map_from_domain(domain);
1856
0
    outer = isl_union_map_flat_range_product(outer, umap);
1857
0
    umap = subtree_schedule_extend_child(tree, outer);
1858
0
    break;
1859
1.18k
  case isl_schedule_node_leaf:
1860
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1861
0
      "leaf node should be handled by caller", return NULL);
1862
400
  case isl_schedule_node_set:
1863
400
  case isl_schedule_node_sequence:
1864
400
    umap = subtree_schedule_extend_from_children(tree, outer);
1865
400
    break;
1866
1.58k
  }
1867
1.58k
1868
1.58k
  return umap;
1869
1.58k
}
1870
1871
static __isl_give isl_union_set *initial_domain(
1872
  __isl_keep isl_schedule_tree *tree);
1873
1874
/* Extract a universe domain from the children of the tree root "tree",
1875
 * which is a set or sequence, meaning that its children are filters.
1876
 * In particular, return the union of the universes of the filters.
1877
 */
1878
static __isl_give isl_union_set *initial_domain_from_children(
1879
  __isl_keep isl_schedule_tree *tree)
1880
125
{
1881
125
  int i, n;
1882
125
  isl_space *space;
1883
125
  isl_union_set *domain;
1884
125
1885
125
  if (!tree->children)
1886
125
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1887
125
      "missing children", return NULL);
1888
125
  n = isl_schedule_tree_list_n_schedule_tree(tree->children);
1889
125
  if (n == 0)
1890
125
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1891
125
      "missing children", return NULL);
1892
125
1893
125
  space = extract_space_from_filter_child(tree);
1894
125
  domain = isl_union_set_empty(space);
1895
125
1896
1.02k
  for (i = 0; i < n; 
++i896
) {
1897
896
    isl_schedule_tree *child;
1898
896
    isl_union_set *domain_i;
1899
896
1900
896
    child = isl_schedule_tree_get_child(tree, i);
1901
896
    domain_i = initial_domain(child);
1902
896
    domain = isl_union_set_union(domain, domain_i);
1903
896
    isl_schedule_tree_free(child);
1904
896
  }
1905
125
1906
125
  return domain;
1907
125
}
1908
1909
/* Extract a universe domain from the tree root "tree".
1910
 * The caller is responsible for making sure that this node
1911
 * would not be skipped by isl_schedule_tree_first_schedule_descendant
1912
 * and that it is not a leaf node.
1913
 */
1914
static __isl_give isl_union_set *initial_domain(
1915
  __isl_keep isl_schedule_tree *tree)
1916
1.41k
{
1917
1.41k
  isl_multi_union_pw_aff *mupa;
1918
1.41k
  isl_union_set *domain;
1919
1.41k
  isl_union_map *exp;
1920
1.41k
1921
1.41k
  if (!tree)
1922
0
    return NULL;
1923
1.41k
1924
1.41k
  switch (tree->type) {
1925
1.41k
  case isl_schedule_node_error:
1926
0
    return NULL;
1927
1.41k
  case isl_schedule_node_context:
1928
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1929
0
      "context node should be handled by caller",
1930
0
      return NULL);
1931
0
  case isl_schedule_node_guard:
1932
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1933
0
      "guard node should be handled by caller",
1934
0
      return NULL);
1935
0
  case isl_schedule_node_mark:
1936
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1937
0
      "mark node should be handled by caller",
1938
0
      return NULL);
1939
0
  case isl_schedule_node_extension:
1940
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
1941
0
      "cannot construct subtree schedule of tree "
1942
0
      "with extension nodes", return NULL);
1943
391
  case isl_schedule_node_band:
1944
391
    if (isl_schedule_tree_band_n_member(tree) == 0)
1945
391
      
isl_die0
(isl_schedule_tree_get_ctx(tree),
1946
391
        isl_error_internal,
1947
391
        "0D band should be handled by caller",
1948
391
        return NULL);
1949
391
    mupa = isl_schedule_band_get_partial_schedule(tree->band);
1950
391
    domain = isl_multi_union_pw_aff_domain(mupa);
1951
391
    domain = isl_union_set_universe(domain);
1952
391
    break;
1953
391
  case isl_schedule_node_domain:
1954
0
    domain = isl_schedule_tree_domain_get_domain(tree);
1955
0
    domain = isl_union_set_universe(domain);
1956
0
    break;
1957
391
  case isl_schedule_node_expansion:
1958
0
    exp = isl_schedule_tree_expansion_get_expansion(tree);
1959
0
    exp = isl_union_map_universe(exp);
1960
0
    domain = isl_union_map_domain(exp);
1961
0
    break;
1962
896
  case isl_schedule_node_filter:
1963
896
    domain = isl_schedule_tree_filter_get_filter(tree);
1964
896
    domain = isl_union_set_universe(domain);
1965
896
    break;
1966
391
  case isl_schedule_node_leaf:
1967
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
1968
0
      "leaf node should be handled by caller", return NULL);
1969
125
  case isl_schedule_node_set:
1970
125
  case isl_schedule_node_sequence:
1971
125
    domain = initial_domain_from_children(tree);
1972
125
    break;
1973
1.41k
  }
1974
1.41k
1975
1.41k
  return domain;
1976
1.41k
}
1977
1978
/* Return the subtree schedule of a node that contains some schedule
1979
 * information, i.e., a node that would not be skipped by
1980
 * isl_schedule_tree_first_schedule_descendant and that is not a leaf.
1981
 *
1982
 * If the tree contains any expansions, then the returned subtree
1983
 * schedule is formulated in terms of the expanded domains.
1984
 * The tree is not allowed to contain any extension nodes.
1985
 *
1986
 * We start with an initial zero-dimensional subtree schedule based
1987
 * on the domain information in the root node and then extend it
1988
 * based on the schedule information in the root node and its descendants.
1989
 */
1990
__isl_give isl_union_map *isl_schedule_tree_get_subtree_schedule_union_map(
1991
  __isl_keep isl_schedule_tree *tree)
1992
516
{
1993
516
  isl_union_set *domain;
1994
516
  isl_union_map *umap;
1995
516
1996
516
  domain = initial_domain(tree);
1997
516
  umap = isl_union_map_from_domain(domain);
1998
516
  return subtree_schedule_extend(tree, umap);
1999
516
}
2000
2001
/* Multiply the partial schedule of the band root node of "tree"
2002
 * with the factors in "mv".
2003
 */
2004
__isl_give isl_schedule_tree *isl_schedule_tree_band_scale(
2005
  __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv)
2006
0
{
2007
0
  if (!tree || !mv)
2008
0
    goto error;
2009
0
  if (tree->type != isl_schedule_node_band)
2010
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2011
0
      "not a band node", goto error);
2012
0
2013
0
  tree = isl_schedule_tree_cow(tree);
2014
0
  if (!tree)
2015
0
    goto error;
2016
0
2017
0
  tree->band = isl_schedule_band_scale(tree->band, mv);
2018
0
  if (!tree->band)
2019
0
    return isl_schedule_tree_free(tree);
2020
0
2021
0
  return tree;
2022
0
error:
2023
0
  isl_schedule_tree_free(tree);
2024
0
  isl_multi_val_free(mv);
2025
0
  return NULL;
2026
0
}
2027
2028
/* Divide the partial schedule of the band root node of "tree"
2029
 * by the factors in "mv".
2030
 */
2031
__isl_give isl_schedule_tree *isl_schedule_tree_band_scale_down(
2032
  __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv)
2033
0
{
2034
0
  if (!tree || !mv)
2035
0
    goto error;
2036
0
  if (tree->type != isl_schedule_node_band)
2037
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2038
0
      "not a band node", goto error);
2039
0
2040
0
  tree = isl_schedule_tree_cow(tree);
2041
0
  if (!tree)
2042
0
    goto error;
2043
0
2044
0
  tree->band = isl_schedule_band_scale_down(tree->band, mv);
2045
0
  if (!tree->band)
2046
0
    return isl_schedule_tree_free(tree);
2047
0
2048
0
  return tree;
2049
0
error:
2050
0
  isl_schedule_tree_free(tree);
2051
0
  isl_multi_val_free(mv);
2052
0
  return NULL;
2053
0
}
2054
2055
/* Reduce the partial schedule of the band root node of "tree"
2056
 * modulo the factors in "mv".
2057
 */
2058
__isl_give isl_schedule_tree *isl_schedule_tree_band_mod(
2059
  __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *mv)
2060
0
{
2061
0
  if (!tree || !mv)
2062
0
    goto error;
2063
0
  if (tree->type != isl_schedule_node_band)
2064
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2065
0
      "not a band node", goto error);
2066
0
2067
0
  tree = isl_schedule_tree_cow(tree);
2068
0
  if (!tree)
2069
0
    goto error;
2070
0
2071
0
  tree->band = isl_schedule_band_mod(tree->band, mv);
2072
0
  if (!tree->band)
2073
0
    return isl_schedule_tree_free(tree);
2074
0
2075
0
  return tree;
2076
0
error:
2077
0
  isl_schedule_tree_free(tree);
2078
0
  isl_multi_val_free(mv);
2079
0
  return NULL;
2080
0
}
2081
2082
/* Shift the partial schedule of the band root node of "tree" by "shift".
2083
 */
2084
__isl_give isl_schedule_tree *isl_schedule_tree_band_shift(
2085
  __isl_take isl_schedule_tree *tree,
2086
  __isl_take isl_multi_union_pw_aff *shift)
2087
0
{
2088
0
  if (!tree || !shift)
2089
0
    goto error;
2090
0
  if (tree->type != isl_schedule_node_band)
2091
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2092
0
      "not a band node", goto error);
2093
0
2094
0
  tree = isl_schedule_tree_cow(tree);
2095
0
  if (!tree)
2096
0
    goto error;
2097
0
2098
0
  tree->band = isl_schedule_band_shift(tree->band, shift);
2099
0
  if (!tree->band)
2100
0
    return isl_schedule_tree_free(tree);
2101
0
2102
0
  return tree;
2103
0
error:
2104
0
  isl_schedule_tree_free(tree);
2105
0
  isl_multi_union_pw_aff_free(shift);
2106
0
  return NULL;
2107
0
}
2108
2109
/* Given two trees with sequence roots, replace the child at position
2110
 * "pos" of "tree" with the children of "child".
2111
 */
2112
__isl_give isl_schedule_tree *isl_schedule_tree_sequence_splice(
2113
  __isl_take isl_schedule_tree *tree, int pos,
2114
  __isl_take isl_schedule_tree *child)
2115
0
{
2116
0
  int n;
2117
0
  isl_schedule_tree_list *list1, *list2;
2118
0
2119
0
  tree = isl_schedule_tree_cow(tree);
2120
0
  if (!tree || !child)
2121
0
    goto error;
2122
0
  if (isl_schedule_tree_get_type(tree) != isl_schedule_node_sequence)
2123
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2124
0
      "not a sequence node", goto error);
2125
0
  n = isl_schedule_tree_n_children(tree);
2126
0
  if (pos < 0 || pos >= n)
2127
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2128
0
      "position out of bounds", goto error);
2129
0
  if (isl_schedule_tree_get_type(child) != isl_schedule_node_sequence)
2130
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2131
0
      "not a sequence node", goto error);
2132
0
2133
0
  list1 = isl_schedule_tree_list_copy(tree->children);
2134
0
  list1 = isl_schedule_tree_list_drop(list1, pos, n - pos);
2135
0
  list2 = isl_schedule_tree_list_copy(tree->children);
2136
0
  list2 = isl_schedule_tree_list_drop(list2, 0, pos + 1);
2137
0
  list1 = isl_schedule_tree_list_concat(list1,
2138
0
        isl_schedule_tree_list_copy(child->children));
2139
0
  list1 = isl_schedule_tree_list_concat(list1, list2);
2140
0
2141
0
  isl_schedule_tree_free(tree);
2142
0
  isl_schedule_tree_free(child);
2143
0
  return isl_schedule_tree_from_children(isl_schedule_node_sequence,
2144
0
            list1);
2145
0
error:
2146
0
  isl_schedule_tree_free(tree);
2147
0
  isl_schedule_tree_free(child);
2148
0
  return NULL;
2149
0
}
2150
2151
/* Tile the band root node of "tree" with tile sizes "sizes".
2152
 *
2153
 * We duplicate the band node, change the schedule of one of them
2154
 * to the tile schedule and the other to the point schedule and then
2155
 * attach the point band as a child to the tile band.
2156
 */
2157
__isl_give isl_schedule_tree *isl_schedule_tree_band_tile(
2158
  __isl_take isl_schedule_tree *tree, __isl_take isl_multi_val *sizes)
2159
25
{
2160
25
  isl_schedule_tree *child = NULL;
2161
25
2162
25
  if (!tree || !sizes)
2163
0
    goto error;
2164
25
  if (tree->type != isl_schedule_node_band)
2165
25
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2166
25
      "not a band node", goto error);
2167
25
2168
25
  child = isl_schedule_tree_copy(tree);
2169
25
  tree = isl_schedule_tree_cow(tree);
2170
25
  child = isl_schedule_tree_cow(child);
2171
25
  if (!tree || !child)
2172
0
    goto error;
2173
25
2174
25
  tree->band = isl_schedule_band_tile(tree->band,
2175
25
              isl_multi_val_copy(sizes));
2176
25
  if (!tree->band)
2177
0
    goto error;
2178
25
  child->band = isl_schedule_band_point(child->band, tree->band, sizes);
2179
25
  if (!child->band)
2180
0
    child = isl_schedule_tree_free(child);
2181
25
2182
25
  tree = isl_schedule_tree_replace_child(tree, 0, child);
2183
25
2184
25
  return tree;
2185
0
error:
2186
0
  isl_schedule_tree_free(child);
2187
0
  isl_schedule_tree_free(tree);
2188
0
  isl_multi_val_free(sizes);
2189
0
  return NULL;
2190
25
}
2191
2192
/* Given an isolate AST generation option "isolate" for a band of size pos + n,
2193
 * return the corresponding option for a band covering the first "pos"
2194
 * members.
2195
 *
2196
 * The input isolate option is of the form
2197
 *
2198
 *  isolate[[flattened outer bands] -> [pos; n]]
2199
 *
2200
 * The output isolate option is of the form
2201
 *
2202
 *  isolate[[flattened outer bands] -> [pos]]
2203
 */
2204
static __isl_give isl_set *isolate_initial(__isl_keep isl_set *isolate,
2205
  int pos, int n)
2206
8
{
2207
8
  isl_id *id;
2208
8
  isl_map *map;
2209
8
2210
8
  isolate = isl_set_copy(isolate);
2211
8
  id = isl_set_get_tuple_id(isolate);
2212
8
  map = isl_set_unwrap(isolate);
2213
8
  map = isl_map_project_out(map, isl_dim_out, pos, n);
2214
8
  isolate = isl_map_wrap(map);
2215
8
  isolate = isl_set_set_tuple_id(isolate, id);
2216
8
2217
8
  return isolate;
2218
8
}
2219
2220
/* Given an isolate AST generation option "isolate" for a band of size pos + n,
2221
 * return the corresponding option for a band covering the final "n"
2222
 * members within a band covering the first "pos" members.
2223
 *
2224
 * The input isolate option is of the form
2225
 *
2226
 *  isolate[[flattened outer bands] -> [pos; n]]
2227
 *
2228
 * The output isolate option is of the form
2229
 *
2230
 *  isolate[[flattened outer bands; pos] -> [n]]
2231
 *
2232
 *
2233
 * The range is first split into
2234
 *
2235
 *  isolate[[flattened outer bands] -> [[pos] -> [n]]]
2236
 *
2237
 * and then the first pos members are moved to the domain
2238
 *
2239
 *  isolate[[[flattened outer bands] -> [pos]] -> [n]]
2240
 *
2241
 * after which the domain is flattened to obtain the desired output.
2242
 */
2243
static __isl_give isl_set *isolate_final(__isl_keep isl_set *isolate,
2244
  int pos, int n)
2245
8
{
2246
8
  isl_id *id;
2247
8
  isl_space *space;
2248
8
  isl_multi_aff *ma1, *ma2;
2249
8
  isl_map *map;
2250
8
2251
8
  isolate = isl_set_copy(isolate);
2252
8
  id = isl_set_get_tuple_id(isolate);
2253
8
  map = isl_set_unwrap(isolate);
2254
8
  space = isl_space_range(isl_map_get_space(map));
2255
8
  ma1 = isl_multi_aff_project_out_map(isl_space_copy(space),
2256
8
               isl_dim_set, pos, n);
2257
8
  ma2 = isl_multi_aff_project_out_map(space, isl_dim_set, 0, pos);
2258
8
  ma1 = isl_multi_aff_range_product(ma1, ma2);
2259
8
  map = isl_map_apply_range(map, isl_map_from_multi_aff(ma1));
2260
8
  map = isl_map_uncurry(map);
2261
8
  map = isl_map_flatten_domain(map);
2262
8
  isolate = isl_map_wrap(map);
2263
8
  isolate = isl_set_set_tuple_id(isolate, id);
2264
8
2265
8
  return isolate;
2266
8
}
2267
2268
/* Split the band root node of "tree" into two nested band nodes,
2269
 * one with the first "pos" dimensions and
2270
 * one with the remaining dimensions.
2271
 * The tree is itself positioned at schedule depth "depth".
2272
 *
2273
 * The loop AST generation type options and the isolate option
2274
 * are split over the two band nodes.
2275
 */
2276
__isl_give isl_schedule_tree *isl_schedule_tree_band_split(
2277
  __isl_take isl_schedule_tree *tree, int pos, int depth)
2278
8
{
2279
8
  int n;
2280
8
  isl_set *isolate, *tree_isolate, *child_isolate;
2281
8
  isl_schedule_tree *child;
2282
8
2283
8
  if (!tree)
2284
0
    return NULL;
2285
8
  if (tree->type != isl_schedule_node_band)
2286
8
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2287
8
      "not a band node", return isl_schedule_tree_free(tree));
2288
8
2289
8
  n = isl_schedule_tree_band_n_member(tree);
2290
8
  if (pos < 0 || pos > n)
2291
8
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2292
8
      "position out of bounds",
2293
8
      return isl_schedule_tree_free(tree));
2294
8
2295
8
  child = isl_schedule_tree_copy(tree);
2296
8
  tree = isl_schedule_tree_cow(tree);
2297
8
  child = isl_schedule_tree_cow(child);
2298
8
  if (!tree || !child)
2299
0
    goto error;
2300
8
2301
8
  isolate = isl_schedule_tree_band_get_ast_isolate_option(tree, depth);
2302
8
  tree_isolate = isolate_initial(isolate, pos, n - pos);
2303
8
  child_isolate = isolate_final(isolate, pos, n - pos);
2304
8
  child->band = isl_schedule_band_drop(child->band, 0, pos);
2305
8
  child->band = isl_schedule_band_replace_ast_build_option(child->band,
2306
8
          isl_set_copy(isolate), child_isolate);
2307
8
  tree->band = isl_schedule_band_drop(tree->band, pos, n - pos);
2308
8
  tree->band = isl_schedule_band_replace_ast_build_option(tree->band,
2309
8
          isl_set_copy(isolate), tree_isolate);
2310
8
  isl_set_free(isolate);
2311
8
  if (!child->band || !tree->band)
2312
0
    goto error;
2313
8
2314
8
  tree = isl_schedule_tree_replace_child(tree, 0, child);
2315
8
2316
8
  return tree;
2317
0
error:
2318
0
  isl_schedule_tree_free(child);
2319
0
  isl_schedule_tree_free(tree);
2320
0
  return NULL;
2321
8
}
2322
2323
/* Attach "tree2" at each of the leaves of "tree1".
2324
 *
2325
 * If "tree1" does not have any explicit children, then make "tree2"
2326
 * its single child.  Otherwise, attach "tree2" to the leaves of
2327
 * each of the children of "tree1".
2328
 */
2329
__isl_give isl_schedule_tree *isl_schedule_tree_append_to_leaves(
2330
  __isl_take isl_schedule_tree *tree1,
2331
  __isl_take isl_schedule_tree *tree2)
2332
1
{
2333
1
  int i, n;
2334
1
2335
1
  if (!tree1 || !tree2)
2336
0
    goto error;
2337
1
  n = isl_schedule_tree_n_children(tree1);
2338
1
  if (n == 0) {
2339
1
    isl_schedule_tree_list *list;
2340
1
    list = isl_schedule_tree_list_from_schedule_tree(tree2);
2341
1
    tree1 = isl_schedule_tree_set_children(tree1, list);
2342
1
    return tree1;
2343
1
  }
2344
0
  for (i = 0; i < n; ++i) {
2345
0
    isl_schedule_tree *child;
2346
0
2347
0
    child = isl_schedule_tree_get_child(tree1, i);
2348
0
    child = isl_schedule_tree_append_to_leaves(child,
2349
0
          isl_schedule_tree_copy(tree2));
2350
0
    tree1 = isl_schedule_tree_replace_child(tree1, i, child);
2351
0
  }
2352
0
2353
0
  isl_schedule_tree_free(tree2);
2354
0
  return tree1;
2355
0
error:
2356
0
  isl_schedule_tree_free(tree1);
2357
0
  isl_schedule_tree_free(tree2);
2358
0
  return NULL;
2359
0
}
2360
2361
/* Reset the user pointer on all identifiers of parameters and tuples
2362
 * in the root of "tree".
2363
 */
2364
__isl_give isl_schedule_tree *isl_schedule_tree_reset_user(
2365
  __isl_take isl_schedule_tree *tree)
2366
0
{
2367
0
  if (isl_schedule_tree_is_leaf(tree))
2368
0
    return tree;
2369
0
2370
0
  tree = isl_schedule_tree_cow(tree);
2371
0
  if (!tree)
2372
0
    return NULL;
2373
0
2374
0
  switch (tree->type) {
2375
0
  case isl_schedule_node_error:
2376
0
    return isl_schedule_tree_free(tree);
2377
0
  case isl_schedule_node_band:
2378
0
    tree->band = isl_schedule_band_reset_user(tree->band);
2379
0
    if (!tree->band)
2380
0
      return isl_schedule_tree_free(tree);
2381
0
    break;
2382
0
  case isl_schedule_node_context:
2383
0
    tree->context = isl_set_reset_user(tree->context);
2384
0
    if (!tree->context)
2385
0
      return isl_schedule_tree_free(tree);
2386
0
    break;
2387
0
  case isl_schedule_node_domain:
2388
0
    tree->domain = isl_union_set_reset_user(tree->domain);
2389
0
    if (!tree->domain)
2390
0
      return isl_schedule_tree_free(tree);
2391
0
    break;
2392
0
  case isl_schedule_node_expansion:
2393
0
    tree->contraction =
2394
0
      isl_union_pw_multi_aff_reset_user(tree->contraction);
2395
0
    tree->expansion = isl_union_map_reset_user(tree->expansion);
2396
0
    if (!tree->contraction || !tree->expansion)
2397
0
      return isl_schedule_tree_free(tree);
2398
0
    break;
2399
0
  case isl_schedule_node_extension:
2400
0
    tree->extension = isl_union_map_reset_user(tree->extension);
2401
0
    if (!tree->extension)
2402
0
      return isl_schedule_tree_free(tree);
2403
0
    break;
2404
0
  case isl_schedule_node_filter:
2405
0
    tree->filter = isl_union_set_reset_user(tree->filter);
2406
0
    if (!tree->filter)
2407
0
      return isl_schedule_tree_free(tree);
2408
0
    break;
2409
0
  case isl_schedule_node_guard:
2410
0
    tree->guard = isl_set_reset_user(tree->guard);
2411
0
    if (!tree->guard)
2412
0
      return isl_schedule_tree_free(tree);
2413
0
    break;
2414
0
  case isl_schedule_node_leaf:
2415
0
  case isl_schedule_node_mark:
2416
0
  case isl_schedule_node_sequence:
2417
0
  case isl_schedule_node_set:
2418
0
    break;
2419
0
  }
2420
0
2421
0
  return tree;
2422
0
}
2423
2424
/* Align the parameters of the root of "tree" to those of "space".
2425
 */
2426
__isl_give isl_schedule_tree *isl_schedule_tree_align_params(
2427
  __isl_take isl_schedule_tree *tree, __isl_take isl_space *space)
2428
0
{
2429
0
  if (!space)
2430
0
    goto error;
2431
0
2432
0
  if (isl_schedule_tree_is_leaf(tree)) {
2433
0
    isl_space_free(space);
2434
0
    return tree;
2435
0
  }
2436
0
2437
0
  tree = isl_schedule_tree_cow(tree);
2438
0
  if (!tree)
2439
0
    goto error;
2440
0
2441
0
  switch (tree->type) {
2442
0
  case isl_schedule_node_error:
2443
0
    goto error;
2444
0
  case isl_schedule_node_band:
2445
0
    tree->band = isl_schedule_band_align_params(tree->band, space);
2446
0
    if (!tree->band)
2447
0
      return isl_schedule_tree_free(tree);
2448
0
    break;
2449
0
  case isl_schedule_node_context:
2450
0
    tree->context = isl_set_align_params(tree->context, space);
2451
0
    if (!tree->context)
2452
0
      return isl_schedule_tree_free(tree);
2453
0
    break;
2454
0
  case isl_schedule_node_domain:
2455
0
    tree->domain = isl_union_set_align_params(tree->domain, space);
2456
0
    if (!tree->domain)
2457
0
      return isl_schedule_tree_free(tree);
2458
0
    break;
2459
0
  case isl_schedule_node_expansion:
2460
0
    tree->contraction =
2461
0
      isl_union_pw_multi_aff_align_params(tree->contraction,
2462
0
              isl_space_copy(space));
2463
0
    tree->expansion = isl_union_map_align_params(tree->expansion,
2464
0
                space);
2465
0
    if (!tree->contraction || !tree->expansion)
2466
0
      return isl_schedule_tree_free(tree);
2467
0
    break;
2468
0
  case isl_schedule_node_extension:
2469
0
    tree->extension = isl_union_map_align_params(tree->extension,
2470
0
                space);
2471
0
    if (!tree->extension)
2472
0
      return isl_schedule_tree_free(tree);
2473
0
    break;
2474
0
  case isl_schedule_node_filter:
2475
0
    tree->filter = isl_union_set_align_params(tree->filter, space);
2476
0
    if (!tree->filter)
2477
0
      return isl_schedule_tree_free(tree);
2478
0
    break;
2479
0
  case isl_schedule_node_guard:
2480
0
    tree->guard = isl_set_align_params(tree->guard, space);
2481
0
    if (!tree->guard)
2482
0
      return isl_schedule_tree_free(tree);
2483
0
    break;
2484
0
  case isl_schedule_node_leaf:
2485
0
  case isl_schedule_node_mark:
2486
0
  case isl_schedule_node_sequence:
2487
0
  case isl_schedule_node_set:
2488
0
    isl_space_free(space);
2489
0
    break;
2490
0
  }
2491
0
2492
0
  return tree;
2493
0
error:
2494
0
  isl_space_free(space);
2495
0
  isl_schedule_tree_free(tree);
2496
0
  return NULL;
2497
0
}
2498
2499
/* Does "tree" involve the iteration domain?
2500
 * That is, does it need to be modified
2501
 * by isl_schedule_tree_pullback_union_pw_multi_aff?
2502
 */
2503
static int involves_iteration_domain(__isl_keep isl_schedule_tree *tree)
2504
238
{
2505
238
  if (!tree)
2506
0
    return -1;
2507
238
2508
238
  switch (tree->type) {
2509
238
  case isl_schedule_node_error:
2510
0
    return -1;
2511
238
  case isl_schedule_node_band:
2512
154
  case isl_schedule_node_domain:
2513
154
  case isl_schedule_node_expansion:
2514
154
  case isl_schedule_node_extension:
2515
154
  case isl_schedule_node_filter:
2516
154
    return 1;
2517
154
  case isl_schedule_node_context:
2518
84
  case isl_schedule_node_leaf:
2519
84
  case isl_schedule_node_guard:
2520
84
  case isl_schedule_node_mark:
2521
84
  case isl_schedule_node_sequence:
2522
84
  case isl_schedule_node_set:
2523
84
    return 0;
2524
0
  }
2525
0
2526
0
  isl_die(isl_schedule_tree_get_ctx(tree), isl_error_internal,
2527
0
    "unhandled case", return -1);
2528
0
}
2529
2530
/* Compute the pullback of the root node of "tree" by the function
2531
 * represented by "upma".
2532
 * In other words, plug in "upma" in the iteration domains of
2533
 * the root node of "tree".
2534
 * We currently do not handle expansion nodes.
2535
 *
2536
 * We first check if the root node involves any iteration domains.
2537
 * If so, we handle the specific cases.
2538
 */
2539
__isl_give isl_schedule_tree *isl_schedule_tree_pullback_union_pw_multi_aff(
2540
  __isl_take isl_schedule_tree *tree,
2541
  __isl_take isl_union_pw_multi_aff *upma)
2542
238
{
2543
238
  int involves;
2544
238
2545
238
  if (!tree || !upma)
2546
0
    goto error;
2547
238
2548
238
  involves = involves_iteration_domain(tree);
2549
238
  if (involves < 0)
2550
0
    goto error;
2551
238
  if (!involves) {
2552
84
    isl_union_pw_multi_aff_free(upma);
2553
84
    return tree;
2554
84
  }
2555
154
2556
154
  tree = isl_schedule_tree_cow(tree);
2557
154
  if (!tree)
2558
0
    goto error;
2559
154
2560
154
  if (tree->type == isl_schedule_node_band) {
2561
70
    tree->band = isl_schedule_band_pullback_union_pw_multi_aff(
2562
70
                  tree->band, upma);
2563
70
    if (!tree->band)
2564
0
      return isl_schedule_tree_free(tree);
2565
84
  } else if (tree->type == isl_schedule_node_domain) {
2566
33
    tree->domain =
2567
33
      isl_union_set_preimage_union_pw_multi_aff(tree->domain,
2568
33
                  upma);
2569
33
    if (!tree->domain)
2570
0
      return isl_schedule_tree_free(tree);
2571
51
  } else if (tree->type == isl_schedule_node_expansion) {
2572
0
    isl_die(isl_schedule_tree_get_ctx(tree), isl_error_unsupported,
2573
0
      "cannot pullback expansion node", goto error);
2574
51
  } else if (tree->type == isl_schedule_node_extension) {
2575
0
    tree->extension =
2576
0
      isl_union_map_preimage_range_union_pw_multi_aff(
2577
0
          tree->extension, upma);
2578
0
    if (!tree->extension)
2579
0
      return isl_schedule_tree_free(tree);
2580
51
  } else if (tree->type == isl_schedule_node_filter) {
2581
51
    tree->filter =
2582
51
      isl_union_set_preimage_union_pw_multi_aff(tree->filter,
2583
51
                  upma);
2584
51
    if (!tree->filter)
2585
0
      return isl_schedule_tree_free(tree);
2586
154
  }
2587
154
2588
154
  return tree;
2589
0
error:
2590
0
  isl_union_pw_multi_aff_free(upma);
2591
0
  isl_schedule_tree_free(tree);
2592
0
  return NULL;
2593
154
}
2594
2595
/* Compute the gist of the band tree root with respect to "context".
2596
 */
2597
__isl_give isl_schedule_tree *isl_schedule_tree_band_gist(
2598
  __isl_take isl_schedule_tree *tree, __isl_take isl_union_set *context)
2599
140
{
2600
140
  if (!tree)
2601
0
    return NULL;
2602
140
  if (tree->type != isl_schedule_node_band)
2603
140
    
isl_die0
(isl_schedule_tree_get_ctx(tree), isl_error_invalid,
2604
140
      "not a band node", goto error);
2605
140
  tree = isl_schedule_tree_cow(tree);
2606
140
  if (!tree)
2607
0
    goto error;
2608
140
2609
140
  tree->band = isl_schedule_band_gist(tree->band, context);
2610
140
  if (!tree->band)
2611
0
    return isl_schedule_tree_free(tree);
2612
140
  return tree;
2613
0
error:
2614
0
  isl_union_set_free(context);
2615
0
  isl_schedule_tree_free(tree);
2616
0
  return NULL;
2617
140
}
2618
2619
/* Are any members in "band" marked coincident?
2620
 */
2621
static int any_coincident(__isl_keep isl_schedule_band *band)
2622
0
{
2623
0
  int i, n;
2624
0
2625
0
  n = isl_schedule_band_n_member(band);
2626
0
  for (i = 0; i < n; ++i)
2627
0
    if (isl_schedule_band_member_get_coincident(band, i))
2628
0
      return 1;
2629
0
2630
0
  return 0;
2631
0
}
2632
2633
/* Print the band node "band" to "p".
2634
 *
2635
 * The permutable and coincident properties are only printed if they
2636
 * are different from the defaults.
2637
 * The coincident property is always printed in YAML flow style.
2638
 */
2639
static __isl_give isl_printer *print_tree_band(__isl_take isl_printer *p,
2640
  __isl_keep isl_schedule_band *band)
2641
0
{
2642
0
  isl_union_set *options;
2643
0
  int empty;
2644
0
2645
0
  p = isl_printer_print_str(p, "schedule");
2646
0
  p = isl_printer_yaml_next(p);
2647
0
  p = isl_printer_print_str(p, "\"");
2648
0
  p = isl_printer_print_multi_union_pw_aff(p, band->mupa);
2649
0
  p = isl_printer_print_str(p, "\"");
2650
0
  if (isl_schedule_band_get_permutable(band)) {
2651
0
    p = isl_printer_yaml_next(p);
2652
0
    p = isl_printer_print_str(p, "permutable");
2653
0
    p = isl_printer_yaml_next(p);
2654
0
    p = isl_printer_print_int(p, 1);
2655
0
  }
2656
0
  if (any_coincident(band)) {
2657
0
    int i, n;
2658
0
    int style;
2659
0
2660
0
    p = isl_printer_yaml_next(p);
2661
0
    p = isl_printer_print_str(p, "coincident");
2662
0
    p = isl_printer_yaml_next(p);
2663
0
    style = isl_printer_get_yaml_style(p);
2664
0
    p = isl_printer_set_yaml_style(p, ISL_YAML_STYLE_FLOW);
2665
0
    p = isl_printer_yaml_start_sequence(p);
2666
0
    n = isl_schedule_band_n_member(band);
2667
0
    for (i = 0; i < n; ++i) {
2668
0
      p = isl_printer_print_int(p,
2669
0
          isl_schedule_band_member_get_coincident(band, i));
2670
0
      p = isl_printer_yaml_next(p);
2671
0
    }
2672
0
    p = isl_printer_yaml_end_sequence(p);
2673
0
    p = isl_printer_set_yaml_style(p, style);
2674
0
  }
2675
0
  options = isl_schedule_band_get_ast_build_options(band);
2676
0
  empty = isl_union_set_is_empty(options);
2677
0
  if (empty < 0)
2678
0
    p = isl_printer_free(p);
2679
0
  if (!empty) {
2680
0
    p = isl_printer_yaml_next(p);
2681
0
    p = isl_printer_print_str(p, "options");
2682
0
    p = isl_printer_yaml_next(p);
2683
0
    p = isl_printer_print_str(p, "\"");
2684
0
    p = isl_printer_print_union_set(p, options);
2685
0
    p = isl_printer_print_str(p, "\"");
2686
0
  }
2687
0
  isl_union_set_free(options);
2688
0
2689
0
  return p;
2690
0
}
2691
2692
/* Print "tree" to "p".
2693
 *
2694
 * If "n_ancestor" is non-negative, then "child_pos" contains the child
2695
 * positions of a descendant of the current node that should be marked
2696
 * (by the comment "YOU ARE HERE").  In particular, if "n_ancestor"
2697
 * is zero, then the current node should be marked.
2698
 * The marking is only printed in YAML block format.
2699
 *
2700
 * Implicit leaf nodes are not printed, except if they correspond
2701
 * to the node that should be marked.
2702
 */
2703
__isl_give isl_printer *isl_printer_print_schedule_tree_mark(
2704
  __isl_take isl_printer *p, __isl_keep isl_schedule_tree *tree,
2705
  int n_ancestor, int *child_pos)
2706
0
{
2707
0
  int i, n;
2708
0
  int sequence = 0;
2709
0
  int block;
2710
0
2711
0
  block = isl_printer_get_yaml_style(p) == ISL_YAML_STYLE_BLOCK;
2712
0
2713
0
  p = isl_printer_yaml_start_mapping(p);
2714
0
  if (n_ancestor == 0 && block) {
2715
0
    p = isl_printer_print_str(p, "# YOU ARE HERE");
2716
0
    p = isl_printer_end_line(p);
2717
0
    p = isl_printer_start_line(p);
2718
0
  }
2719
0
  switch (tree->type) {
2720
0
  case isl_schedule_node_error:
2721
0
    p = isl_printer_print_str(p, "ERROR");
2722
0
    break;
2723
0
  case isl_schedule_node_leaf:
2724
0
    p = isl_printer_print_str(p, "leaf");
2725
0
    break;
2726
0
  case isl_schedule_node_sequence:
2727
0
    p = isl_printer_print_str(p, "sequence");
2728
0
    sequence = 1;
2729
0
    break;
2730
0
  case isl_schedule_node_set:
2731
0
    p = isl_printer_print_str(p, "set");
2732
0
    sequence = 1;
2733
0
    break;
2734
0
  case isl_schedule_node_context:
2735
0
    p = isl_printer_print_str(p, "context");
2736
0
    p = isl_printer_yaml_next(p);
2737
0
    p = isl_printer_print_str(p, "\"");
2738
0
    p = isl_printer_print_set(p, tree->context);
2739
0
    p = isl_printer_print_str(p, "\"");
2740
0
    break;
2741
0
  case isl_schedule_node_domain:
2742
0
    p = isl_printer_print_str(p, "domain");
2743
0
    p = isl_printer_yaml_next(p);
2744
0
    p = isl_printer_print_str(p, "\"");
2745
0
    p = isl_printer_print_union_set(p, tree->domain);
2746
0
    p = isl_printer_print_str(p, "\"");
2747
0
    break;
2748
0
  case isl_schedule_node_expansion:
2749
0
    p = isl_printer_print_str(p, "contraction");
2750
0
    p = isl_printer_yaml_next(p);
2751
0
    p = isl_printer_print_str(p, "\"");
2752
0
    p = isl_printer_print_union_pw_multi_aff(p, tree->contraction);
2753
0
    p = isl_printer_print_str(p, "\"");
2754
0
    p = isl_printer_yaml_next(p);
2755
0
    p = isl_printer_print_str(p, "expansion");
2756
0
    p = isl_printer_yaml_next(p);
2757
0
    p = isl_printer_print_str(p, "\"");
2758
0
    p = isl_printer_print_union_map(p, tree->expansion);
2759
0
    p = isl_printer_print_str(p, "\"");
2760
0
    break;
2761
0
  case isl_schedule_node_extension:
2762
0
    p = isl_printer_print_str(p, "extension");
2763
0
    p = isl_printer_yaml_next(p);
2764
0
    p = isl_printer_print_str(p, "\"");
2765
0
    p = isl_printer_print_union_map(p, tree->extension);
2766
0
    p = isl_printer_print_str(p, "\"");
2767
0
    break;
2768
0
  case isl_schedule_node_filter:
2769
0
    p = isl_printer_print_str(p, "filter");
2770
0
    p = isl_printer_yaml_next(p);
2771
0
    p = isl_printer_print_str(p, "\"");
2772
0
    p = isl_printer_print_union_set(p, tree->filter);
2773
0
    p = isl_printer_print_str(p, "\"");
2774
0
    break;
2775
0
  case isl_schedule_node_guard:
2776
0
    p = isl_printer_print_str(p, "guard");
2777
0
    p = isl_printer_yaml_next(p);
2778
0
    p = isl_printer_print_str(p, "\"");
2779
0
    p = isl_printer_print_set(p, tree->guard);
2780
0
    p = isl_printer_print_str(p, "\"");
2781
0
    break;
2782
0
  case isl_schedule_node_mark:
2783
0
    p = isl_printer_print_str(p, "mark");
2784
0
    p = isl_printer_yaml_next(p);
2785
0
    p = isl_printer_print_str(p, "\"");
2786
0
    p = isl_printer_print_str(p, isl_id_get_name(tree->mark));
2787
0
    p = isl_printer_print_str(p, "\"");
2788
0
    break;
2789
0
  case isl_schedule_node_band:
2790
0
    p = print_tree_band(p, tree->band);
2791
0
    break;
2792
0
  }
2793
0
  p = isl_printer_yaml_next(p);
2794
0
2795
0
  if (!tree->children) {
2796
0
    if (n_ancestor > 0 && block) {
2797
0
      isl_schedule_tree *leaf;
2798
0
2799
0
      p = isl_printer_print_str(p, "child");
2800
0
      p = isl_printer_yaml_next(p);
2801
0
      leaf = isl_schedule_tree_leaf(isl_printer_get_ctx(p));
2802
0
      p = isl_printer_print_schedule_tree_mark(p,
2803
0
          leaf, 0, NULL);
2804
0
      isl_schedule_tree_free(leaf);
2805
0
      p = isl_printer_yaml_next(p);
2806
0
    }
2807
0
    return isl_printer_yaml_end_mapping(p);
2808
0
  }
2809
0
2810
0
  if (sequence) {
2811
0
    p = isl_printer_yaml_start_sequence(p);
2812
0
  } else {
2813
0
    p = isl_printer_print_str(p, "child");
2814
0
    p = isl_printer_yaml_next(p);
2815
0
  }
2816
0
2817
0
  n = isl_schedule_tree_list_n_schedule_tree(tree->children);
2818
0
  for (i = 0; i < n; ++i) {
2819
0
    isl_schedule_tree *t;
2820
0
2821
0
    t = isl_schedule_tree_get_child(tree, i);
2822
0
    if (n_ancestor > 0 && child_pos[0] == i)
2823
0
      p = isl_printer_print_schedule_tree_mark(p, t,
2824
0
            n_ancestor - 1, child_pos + 1);
2825
0
    else
2826
0
      p = isl_printer_print_schedule_tree_mark(p, t,
2827
0
            -1, NULL);
2828
0
    isl_schedule_tree_free(t);
2829
0
2830
0
    p = isl_printer_yaml_next(p);
2831
0
  }
2832
0
2833
0
  if (sequence)
2834
0
    p = isl_printer_yaml_end_sequence(p);
2835
0
  p = isl_printer_yaml_end_mapping(p);
2836
0
2837
0
  return p;
2838
0
}
2839
2840
/* Print "tree" to "p".
2841
 */
2842
__isl_give isl_printer *isl_printer_print_schedule_tree(
2843
  __isl_take isl_printer *p, __isl_keep isl_schedule_tree *tree)
2844
0
{
2845
0
  return isl_printer_print_schedule_tree_mark(p, tree, -1, NULL);
2846
0
}
2847
2848
void isl_schedule_tree_dump(__isl_keep isl_schedule_tree *tree)
2849
0
{
2850
0
  isl_ctx *ctx;
2851
0
  isl_printer *printer;
2852
0
2853
0
  if (!tree)
2854
0
    return;
2855
0
2856
0
  ctx = isl_schedule_tree_get_ctx(tree);
2857
0
  printer = isl_printer_to_file(ctx, stderr);
2858
0
  printer = isl_printer_set_yaml_style(printer, ISL_YAML_STYLE_BLOCK);
2859
0
  printer = isl_printer_print_schedule_tree(printer, tree);
2860
0
2861
0
  isl_printer_free(printer);
2862
0
}