Coverage Report

Created: 2017-11-21 16:49

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