Coverage Report

Created: 2018-02-20 12:54

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_ast_graft.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2012      Ecole Normale Superieure
3
 * Copyright 2014      INRIA Rocquencourt
4
 *
5
 * Use of this software is governed by the MIT license
6
 *
7
 * Written by Sven Verdoolaege,
8
 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
9
 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
10
 * B.P. 105 - 78153 Le Chesnay, France
11
 */
12
13
#include <isl/space.h>
14
#include <isl_ast_private.h>
15
#include <isl_ast_build_expr.h>
16
#include <isl_ast_build_private.h>
17
#include <isl_ast_graft_private.h>
18
19
static __isl_give isl_ast_graft *isl_ast_graft_copy(
20
  __isl_keep isl_ast_graft *graft);
21
22
#undef BASE
23
#define BASE ast_graft
24
25
#include <isl_list_templ.c>
26
27
#undef BASE
28
#define BASE ast_graft
29
#include <print_templ.c>
30
31
isl_ctx *isl_ast_graft_get_ctx(__isl_keep isl_ast_graft *graft)
32
2.87k
{
33
2.87k
  if (!graft)
34
0
    return NULL;
35
2.87k
  return isl_basic_set_get_ctx(graft->enforced);
36
2.87k
}
37
38
__isl_give isl_ast_node *isl_ast_graft_get_node(
39
  __isl_keep isl_ast_graft *graft)
40
5.88k
{
41
5.88k
  return graft ? isl_ast_node_copy(graft->node) : NULL;
42
5.88k
}
43
44
/* Create a graft for "node" with no guards and no enforced conditions.
45
 */
46
__isl_give isl_ast_graft *isl_ast_graft_alloc(
47
  __isl_take isl_ast_node *node, __isl_keep isl_ast_build *build)
48
6.06k
{
49
6.06k
  isl_ctx *ctx;
50
6.06k
  isl_space *space;
51
6.06k
  isl_ast_graft *graft;
52
6.06k
53
6.06k
  if (!node)
54
0
    return NULL;
55
6.06k
56
6.06k
  ctx = isl_ast_node_get_ctx(node);
57
6.06k
  graft = isl_calloc_type(ctx, isl_ast_graft);
58
6.06k
  if (!graft)
59
0
    goto error;
60
6.06k
61
6.06k
  space = isl_ast_build_get_space(build, 1);
62
6.06k
63
6.06k
  graft->ref = 1;
64
6.06k
  graft->node = node;
65
6.06k
  graft->guard = isl_set_universe(isl_space_copy(space));
66
6.06k
  graft->enforced = isl_basic_set_universe(space);
67
6.06k
68
6.06k
  if (!graft->guard || !graft->enforced)
69
0
    return isl_ast_graft_free(graft);
70
6.06k
71
6.06k
  return graft;
72
0
error:
73
0
  isl_ast_node_free(node);
74
0
  return NULL;
75
6.06k
}
76
77
/* Create a graft with no guards and no enforced conditions
78
 * encapsulating a call to the domain element specified by "executed".
79
 * "executed" is assumed to be single-valued.
80
 */
81
__isl_give isl_ast_graft *isl_ast_graft_alloc_domain(
82
  __isl_take isl_map *executed, __isl_keep isl_ast_build *build)
83
2.15k
{
84
2.15k
  isl_ast_node *node;
85
2.15k
86
2.15k
  node = isl_ast_build_call_from_executed(build, executed);
87
2.15k
88
2.15k
  return isl_ast_graft_alloc(node, build);
89
2.15k
}
90
91
static __isl_give isl_ast_graft *isl_ast_graft_copy(
92
  __isl_keep isl_ast_graft *graft)
93
38.3k
{
94
38.3k
  if (!graft)
95
0
    return NULL;
96
38.3k
97
38.3k
  graft->ref++;
98
38.3k
  return graft;
99
38.3k
}
100
101
/* Do all the grafts in "list" have the same guard and is this guard
102
 * independent of the current depth?
103
 */
104
static int equal_independent_guards(__isl_keep isl_ast_graft_list *list,
105
  __isl_keep isl_ast_build *build)
106
3.90k
{
107
3.90k
  int i, n;
108
3.90k
  int depth;
109
3.90k
  isl_ast_graft *graft_0;
110
3.90k
  int equal = 1;
111
3.90k
  int skip;
112
3.90k
113
3.90k
  graft_0 = isl_ast_graft_list_get_ast_graft(list, 0);
114
3.90k
  if (!graft_0)
115
0
    return -1;
116
3.90k
117
3.90k
  depth = isl_ast_build_get_depth(build);
118
3.90k
  if (isl_set_dim(graft_0->guard, isl_dim_set) <= depth)
119
24
    skip = 0;
120
3.88k
  else
121
3.88k
    skip = isl_set_involves_dims(graft_0->guard,
122
3.88k
            isl_dim_set, depth, 1);
123
3.90k
  if (skip < 0 || skip) {
124
17
    isl_ast_graft_free(graft_0);
125
17
    return skip < 0 ? 
-10
: 0;
126
17
  }
127
3.89k
128
3.89k
  n = isl_ast_graft_list_n_ast_graft(list);
129
5.26k
  for (i = 1; i < n; 
++i1.37k
) {
130
1.42k
    isl_ast_graft *graft;
131
1.42k
    graft = isl_ast_graft_list_get_ast_graft(list, i);
132
1.42k
    if (!graft)
133
0
      equal = -1;
134
1.42k
    else
135
1.42k
      equal = isl_set_is_equal(graft_0->guard, graft->guard);
136
1.42k
    isl_ast_graft_free(graft);
137
1.42k
    if (equal < 0 || !equal)
138
46
      break;
139
1.42k
  }
140
3.89k
141
3.89k
  isl_ast_graft_free(graft_0);
142
3.89k
143
3.89k
  return equal;
144
3.89k
}
145
146
/* Hoist "guard" out of the current level (given by "build").
147
 *
148
 * In particular, eliminate the dimension corresponding to the current depth.
149
 */
150
static __isl_give isl_set *hoist_guard(__isl_take isl_set *guard,
151
  __isl_keep isl_ast_build *build)
152
63
{
153
63
  int depth;
154
63
155
63
  depth = isl_ast_build_get_depth(build);
156
63
  if (depth < isl_set_dim(guard, isl_dim_set)) {
157
57
    guard = isl_set_remove_divs_involving_dims(guard,
158
57
            isl_dim_set, depth, 1);
159
57
    guard = isl_set_eliminate(guard, isl_dim_set, depth, 1);
160
57
    guard = isl_set_compute_divs(guard);
161
57
  }
162
63
163
63
  return guard;
164
63
}
165
166
/* Extract a common guard from the grafts in "list" that can be hoisted
167
 * out of the current level.  If no such guard can be found, then return
168
 * a universal set.
169
 *
170
 * If all the grafts in the list have the same guard and if this guard
171
 * is independent of the current level, then it can be hoisted out.
172
 * If there is only one graft in the list and if its guard
173
 * depends on the current level, then we eliminate this level and
174
 * return the result.
175
 *
176
 * Otherwise, we return the unshifted simple hull of the guards.
177
 * In order to be able to hoist as many constraints as possible,
178
 * but at the same time avoid hoisting constraints that did not
179
 * appear in the guards in the first place, we intersect the guards
180
 * with all the information that is available (i.e., the domain
181
 * from the build and the enforced constraints of the graft) and
182
 * compute the unshifted hull of the result using only constraints
183
 * from the original guards.
184
 * In particular, intersecting the guards with other known information
185
 * allows us to hoist guards that are only explicit is some of
186
 * the grafts and implicit in the others.
187
 *
188
 * The special case for equal guards is needed in case those guards
189
 * are non-convex.  Taking the simple hull would remove information
190
 * and would not allow for these guards to be hoisted completely.
191
 */
192
__isl_give isl_set *isl_ast_graft_list_extract_hoistable_guard(
193
  __isl_keep isl_ast_graft_list *list, __isl_keep isl_ast_build *build)
194
3.90k
{
195
3.90k
  int i, n;
196
3.90k
  int equal;
197
3.90k
  isl_ctx *ctx;
198
3.90k
  isl_set *guard;
199
3.90k
  isl_set_list *set_list;
200
3.90k
  isl_basic_set *hull;
201
3.90k
202
3.90k
  if (!list || !build)
203
0
    return NULL;
204
3.90k
205
3.90k
  n = isl_ast_graft_list_n_ast_graft(list);
206
3.90k
  if (n == 0)
207
0
    return isl_set_universe(isl_ast_build_get_space(build, 1));
208
3.90k
209
3.90k
  equal = equal_independent_guards(list, build);
210
3.90k
  if (equal < 0)
211
0
    return NULL;
212
3.90k
213
3.90k
  if (equal || 
n == 163
) {
214
3.84k
    isl_ast_graft *graft_0;
215
3.84k
216
3.84k
    graft_0 = isl_ast_graft_list_get_ast_graft(list, 0);
217
3.84k
    if (!graft_0)
218
0
      return NULL;
219
3.84k
    guard = isl_set_copy(graft_0->guard);
220
3.84k
    if (!equal)
221
0
      guard = hoist_guard(guard, build);
222
3.84k
    isl_ast_graft_free(graft_0);
223
3.84k
    return guard;
224
3.84k
  }
225
63
226
63
  ctx = isl_ast_build_get_ctx(build);
227
63
  set_list = isl_set_list_alloc(ctx, n);
228
63
  guard = isl_set_empty(isl_ast_build_get_space(build, 1));
229
396
  for (i = 0; i < n; 
++i333
) {
230
333
    isl_ast_graft *graft;
231
333
    isl_basic_set *enforced;
232
333
    isl_set *guard_i;
233
333
234
333
    graft = isl_ast_graft_list_get_ast_graft(list, i);
235
333
    enforced = isl_ast_graft_get_enforced(graft);
236
333
    guard_i = isl_set_copy(graft->guard);
237
333
    isl_ast_graft_free(graft);
238
333
    set_list = isl_set_list_add(set_list, isl_set_copy(guard_i));
239
333
    guard_i = isl_set_intersect(guard_i,
240
333
              isl_set_from_basic_set(enforced));
241
333
    guard_i = isl_set_intersect(guard_i,
242
333
              isl_ast_build_get_domain(build));
243
333
    guard = isl_set_union(guard, guard_i);
244
333
  }
245
63
  hull = isl_set_unshifted_simple_hull_from_set_list(guard, set_list);
246
63
  guard = isl_set_from_basic_set(hull);
247
63
  return hoist_guard(guard, build);
248
63
}
249
250
/* Internal data structure used inside insert_if.
251
 *
252
 * list is the list of guarded nodes created by each call to insert_if.
253
 * node is the original node that is guarded by insert_if.
254
 * build is the build in which the AST is constructed.
255
 */
256
struct isl_insert_if_data {
257
  isl_ast_node_list *list;
258
  isl_ast_node *node;
259
  isl_ast_build *build;
260
};
261
262
static isl_stat insert_if(__isl_take isl_basic_set *bset, void *user);
263
264
/* Insert an if node around "node" testing the condition encoded
265
 * in guard "guard".
266
 *
267
 * If the user does not want any disjunctions in the if conditions
268
 * and if "guard" does involve a disjunction, then we make the different
269
 * disjuncts disjoint and insert an if node corresponding to each disjunct
270
 * around a copy of "node".  The result is then a block node containing
271
 * this sequence of guarded copies of "node".
272
 */
273
static __isl_give isl_ast_node *ast_node_insert_if(
274
  __isl_take isl_ast_node *node, __isl_take isl_set *guard,
275
  __isl_keep isl_ast_build *build)
276
195
{
277
195
  struct isl_insert_if_data data;
278
195
  isl_ctx *ctx;
279
195
280
195
  ctx = isl_ast_build_get_ctx(build);
281
195
  if (isl_options_get_ast_build_allow_or(ctx) ||
282
195
      
isl_set_n_basic_set(guard) <= 10
) {
283
195
    isl_ast_node *if_node;
284
195
    isl_ast_expr *expr;
285
195
286
195
    expr = isl_ast_build_expr_from_set_internal(build, guard);
287
195
288
195
    if_node = isl_ast_node_alloc_if(expr);
289
195
    return isl_ast_node_if_set_then(if_node, node);
290
195
  }
291
0
292
0
  guard = isl_set_make_disjoint(guard);
293
0
294
0
  data.list = isl_ast_node_list_alloc(ctx, 0);
295
0
  data.node = node;
296
0
  data.build = build;
297
0
  if (isl_set_foreach_basic_set(guard, &insert_if, &data) < 0)
298
0
    data.list = isl_ast_node_list_free(data.list);
299
0
300
0
  isl_set_free(guard);
301
0
  isl_ast_node_free(data.node);
302
0
  return isl_ast_node_alloc_block(data.list);
303
0
}
304
305
/* Insert an if node around a copy of "data->node" testing the condition
306
 * encoded in guard "bset" and add the result to data->list.
307
 */
308
static isl_stat insert_if(__isl_take isl_basic_set *bset, void *user)
309
0
{
310
0
  struct isl_insert_if_data *data = user;
311
0
  isl_ast_node *node;
312
0
  isl_set *set;
313
0
314
0
  set = isl_set_from_basic_set(bset);
315
0
  node = isl_ast_node_copy(data->node);
316
0
  node = ast_node_insert_if(node, set, data->build);
317
0
  data->list = isl_ast_node_list_add(data->list, node);
318
0
319
0
  return isl_stat_ok;
320
0
}
321
322
/* Insert an if node around graft->node testing the condition encoded
323
 * in guard "guard", assuming guard involves any conditions.
324
 */
325
static __isl_give isl_ast_graft *insert_if_node(
326
  __isl_take isl_ast_graft *graft, __isl_take isl_set *guard,
327
  __isl_keep isl_ast_build *build)
328
6.06k
{
329
6.06k
  int univ;
330
6.06k
331
6.06k
  if (!graft)
332
0
    goto error;
333
6.06k
334
6.06k
  univ = isl_set_plain_is_universe(guard);
335
6.06k
  if (univ < 0)
336
0
    goto error;
337
6.06k
  if (univ) {
338
5.86k
    isl_set_free(guard);
339
5.86k
    return graft;
340
5.86k
  }
341
195
342
195
  build = isl_ast_build_copy(build);
343
195
  graft->node = ast_node_insert_if(graft->node, guard, build);
344
195
  isl_ast_build_free(build);
345
195
346
195
  if (!graft->node)
347
0
    return isl_ast_graft_free(graft);
348
195
349
195
  return graft;
350
0
error:
351
0
  isl_set_free(guard);
352
0
  return isl_ast_graft_free(graft);
353
195
}
354
355
/* Insert an if node around graft->node testing the condition encoded
356
 * in graft->guard, assuming graft->guard involves any conditions.
357
 */
358
static __isl_give isl_ast_graft *insert_pending_guard_node(
359
  __isl_take isl_ast_graft *graft, __isl_keep isl_ast_build *build)
360
6.06k
{
361
6.06k
  if (!graft)
362
0
    return NULL;
363
6.06k
364
6.06k
  return insert_if_node(graft, isl_set_copy(graft->guard), build);
365
6.06k
}
366
367
/* Replace graft->enforced by "enforced".
368
 */
369
__isl_give isl_ast_graft *isl_ast_graft_set_enforced(
370
  __isl_take isl_ast_graft *graft, __isl_take isl_basic_set *enforced)
371
173
{
372
173
  if (!graft || !enforced)
373
0
    goto error;
374
173
375
173
  isl_basic_set_free(graft->enforced);
376
173
  graft->enforced = enforced;
377
173
378
173
  return graft;
379
0
error:
380
0
  isl_basic_set_free(enforced);
381
0
  return isl_ast_graft_free(graft);
382
173
}
383
384
/* Update "enforced" such that it only involves constraints that are
385
 * also enforced by "graft".
386
 */
387
static __isl_give isl_basic_set *update_enforced(
388
  __isl_take isl_basic_set *enforced, __isl_keep isl_ast_graft *graft,
389
  int depth)
390
5.83k
{
391
5.83k
  isl_basic_set *enforced_g;
392
5.83k
393
5.83k
  enforced_g = isl_ast_graft_get_enforced(graft);
394
5.83k
  if (depth < isl_basic_set_dim(enforced_g, isl_dim_set))
395
5.67k
    enforced_g = isl_basic_set_eliminate(enforced_g,
396
5.67k
              isl_dim_set, depth, 1);
397
5.83k
  enforced_g = isl_basic_set_remove_unknown_divs(enforced_g);
398
5.83k
  enforced_g = isl_basic_set_align_params(enforced_g,
399
5.83k
        isl_basic_set_get_space(enforced));
400
5.83k
  enforced = isl_basic_set_align_params(enforced,
401
5.83k
        isl_basic_set_get_space(enforced_g));
402
5.83k
  enforced = isl_set_simple_hull(isl_basic_set_union(enforced,
403
5.83k
            enforced_g));
404
5.83k
405
5.83k
  return enforced;
406
5.83k
}
407
408
/* Extend the node at *body with node.
409
 *
410
 * If body points to the else branch, then *body may still be NULL.
411
 * If so, we simply attach node to this else branch.
412
 * Otherwise, we attach a list containing the statements already
413
 * attached at *body followed by node.
414
 */
415
static void extend_body(__isl_keep isl_ast_node **body,
416
  __isl_take isl_ast_node *node)
417
173
{
418
173
  isl_ast_node_list *list;
419
173
420
173
  if  (!*body) {
421
29
    *body = node;
422
29
    return;
423
29
  }
424
144
425
144
  if ((*body)->type == isl_ast_node_block) {
426
83
    list = isl_ast_node_block_get_children(*body);
427
83
    isl_ast_node_free(*body);
428
83
  } else
429
61
    list = isl_ast_node_list_from_ast_node(*body);
430
144
  list = isl_ast_node_list_add(list, node);
431
144
  *body = isl_ast_node_alloc_block(list);
432
144
}
433
434
/* Merge "graft" into the last graft of "list".
435
 * body points to the then or else branch of an if node in that last graft.
436
 *
437
 * We attach graft->node to this branch and update the enforced
438
 * set of the last graft of "list" to take into account the enforced
439
 * set of "graft".
440
 */
441
static __isl_give isl_ast_graft_list *graft_extend_body(
442
  __isl_take isl_ast_graft_list *list,
443
  __isl_keep isl_ast_node **body, __isl_take isl_ast_graft *graft,
444
  __isl_keep isl_ast_build *build)
445
173
{
446
173
  int n;
447
173
  int depth;
448
173
  isl_ast_graft *last;
449
173
  isl_space *space;
450
173
  isl_basic_set *enforced;
451
173
452
173
  if (!list || !graft)
453
0
    goto error;
454
173
  extend_body(body, isl_ast_node_copy(graft->node));
455
173
  if (!*body)
456
0
    goto error;
457
173
458
173
  n = isl_ast_graft_list_n_ast_graft(list);
459
173
  last = isl_ast_graft_list_get_ast_graft(list, n - 1);
460
173
461
173
  depth = isl_ast_build_get_depth(build);
462
173
  space = isl_ast_build_get_space(build, 1);
463
173
  enforced = isl_basic_set_empty(space);
464
173
  enforced = update_enforced(enforced, last, depth);
465
173
  enforced = update_enforced(enforced, graft, depth);
466
173
  last = isl_ast_graft_set_enforced(last, enforced);
467
173
468
173
  list = isl_ast_graft_list_set_ast_graft(list, n - 1, last);
469
173
  isl_ast_graft_free(graft);
470
173
  return list;
471
0
error:
472
0
  isl_ast_graft_free(graft);
473
0
  return isl_ast_graft_list_free(list);
474
173
}
475
476
/* Merge "graft" into the last graft of "list", attaching graft->node
477
 * to the then branch of "last_if".
478
 */
479
static __isl_give isl_ast_graft_list *extend_then(
480
  __isl_take isl_ast_graft_list *list,
481
  __isl_keep isl_ast_node *last_if, __isl_take isl_ast_graft *graft,
482
  __isl_keep isl_ast_build *build)
483
139
{
484
139
  return graft_extend_body(list, &last_if->u.i.then, graft, build);
485
139
}
486
487
/* Merge "graft" into the last graft of "list", attaching graft->node
488
 * to the else branch of "last_if".
489
 */
490
static __isl_give isl_ast_graft_list *extend_else(
491
  __isl_take isl_ast_graft_list *list,
492
  __isl_keep isl_ast_node *last_if, __isl_take isl_ast_graft *graft,
493
  __isl_keep isl_ast_build *build)
494
34
{
495
34
  return graft_extend_body(list, &last_if->u.i.else_node, graft, build);
496
34
}
497
498
/* This data structure keeps track of an if node.
499
 *
500
 * "node" is the actual if-node
501
 * "guard" is the original, non-simplified guard of the node
502
 * "complement" is the complement of "guard" in the context of outer if nodes
503
 */
504
struct isl_if_node {
505
  isl_ast_node *node;
506
  isl_set *guard;
507
  isl_set *complement;
508
};
509
510
/* Given a list of "n" if nodes, clear those starting at "first"
511
 * and return "first" (i.e., the updated size of the array).
512
 */
513
static int clear_if_nodes(struct isl_if_node *if_node, int first, int n)
514
4.56k
{
515
4.56k
  int i;
516
4.56k
517
4.67k
  for (i = first; i < n; 
++i113
) {
518
113
    isl_set_free(if_node[i].guard);
519
113
    isl_set_free(if_node[i].complement);
520
113
  }
521
4.56k
522
4.56k
  return first;
523
4.56k
}
524
525
/* For each graft in "list",
526
 * insert an if node around graft->node testing the condition encoded
527
 * in graft->guard, assuming graft->guard involves any conditions.
528
 *
529
 * We keep track of a list of generated if nodes that can be extended
530
 * without changing the order of the elements in "list".
531
 * If the guard of a graft is a subset of either the guard or its complement
532
 * of one of those if nodes, then the node
533
 * of the new graft is inserted into the then or else branch of the last graft
534
 * and the current graft is discarded.
535
 * The guard of the node is then simplified based on the conditions
536
 * enforced at that then or else branch.
537
 * Otherwise, the current graft is appended to the list.
538
 *
539
 * We only construct else branches if allowed by the user.
540
 */
541
static __isl_give isl_ast_graft_list *insert_pending_guard_nodes(
542
  __isl_take isl_ast_graft_list *list,
543
  __isl_keep isl_ast_build *build)
544
4.36k
{
545
4.36k
  int i, j, n, n_if;
546
4.36k
  int allow_else;
547
4.36k
  isl_ctx *ctx;
548
4.36k
  isl_ast_graft_list *res;
549
4.36k
  struct isl_if_node *if_node = NULL;
550
4.36k
551
4.36k
  if (!build || !list)
552
0
    return isl_ast_graft_list_free(list);
553
4.36k
554
4.36k
  ctx = isl_ast_build_get_ctx(build);
555
4.36k
  n = isl_ast_graft_list_n_ast_graft(list);
556
4.36k
557
4.36k
  allow_else = isl_options_get_ast_build_allow_else(ctx);
558
4.36k
559
4.36k
  n_if = 0;
560
4.36k
  if (n > 1) {
561
321
    if_node = isl_alloc_array(ctx, struct isl_if_node, n - 1);
562
321
    if (!if_node)
563
0
      return isl_ast_graft_list_free(list);
564
4.36k
  }
565
4.36k
566
4.36k
  res = isl_ast_graft_list_alloc(ctx, n);
567
4.36k
568
10.4k
  for (i = 0; i < n; 
++i6.06k
) {
569
6.06k
    isl_set *guard;
570
6.06k
    isl_ast_graft *graft;
571
6.06k
    int subset, found_then, found_else;
572
6.06k
    isl_ast_node *node;
573
6.06k
574
6.06k
    graft = isl_ast_graft_list_get_ast_graft(list, i);
575
6.06k
    if (!graft)
576
0
      break;
577
6.06k
    subset = 0;
578
6.06k
    found_then = found_else = -1;
579
6.06k
    if (n_if > 0) {
580
200
      isl_set *test;
581
200
      test = isl_set_copy(graft->guard);
582
200
      test = isl_set_intersect(test,
583
200
            isl_set_copy(build->domain));
584
232
      for (j = n_if - 1; j >= 0; 
--j32
) {
585
205
        subset = isl_set_is_subset(test,
586
205
              if_node[j].guard);
587
205
        if (subset < 0 || subset) {
588
139
          found_then = j;
589
139
          break;
590
139
        }
591
66
        if (!allow_else)
592
0
          continue;
593
66
        subset = isl_set_is_subset(test,
594
66
              if_node[j].complement);
595
66
        if (subset < 0 || subset) {
596
34
          found_else = j;
597
34
          break;
598
34
        }
599
66
      }
600
200
      n_if = clear_if_nodes(if_node, j + 1, n_if);
601
200
      isl_set_free(test);
602
200
    }
603
6.06k
    if (subset < 0) {
604
0
      graft = isl_ast_graft_free(graft);
605
0
      break;
606
0
    }
607
6.06k
608
6.06k
    guard = isl_set_copy(graft->guard);
609
6.06k
    if (found_then >= 0)
610
139
      graft->guard = isl_set_gist(graft->guard,
611
139
        isl_set_copy(if_node[found_then].guard));
612
5.92k
    else if (found_else >= 0)
613
34
      graft->guard = isl_set_gist(graft->guard,
614
34
        isl_set_copy(if_node[found_else].complement));
615
6.06k
616
6.06k
    node = graft->node;
617
6.06k
    if (!graft->guard)
618
0
      graft = isl_ast_graft_free(graft);
619
6.06k
    graft = insert_pending_guard_node(graft, build);
620
6.06k
    if (graft && graft->node != node && 
i != n - 1195
) {
621
113
      isl_set *set;
622
113
      if_node[n_if].node = graft->node;
623
113
      if_node[n_if].guard = guard;
624
113
      if (found_then >= 0)
625
38
        set = if_node[found_then].guard;
626
75
      else if (found_else >= 0)
627
5
        set = if_node[found_else].complement;
628
70
      else
629
70
        set = build->domain;
630
113
      set = isl_set_copy(set);
631
113
      set = isl_set_subtract(set, isl_set_copy(guard));
632
113
      if_node[n_if].complement = set;
633
113
      n_if++;
634
113
    } else
635
5.94k
      isl_set_free(guard);
636
6.06k
    if (!graft)
637
0
      break;
638
6.06k
639
6.06k
    if (found_then >= 0)
640
139
      res = extend_then(res, if_node[found_then].node,
641
139
            graft, build);
642
5.92k
    else if (found_else >= 0)
643
34
      res = extend_else(res, if_node[found_else].node,
644
34
            graft, build);
645
5.88k
    else
646
5.88k
      res = isl_ast_graft_list_add(res, graft);
647
6.06k
  }
648
4.36k
  if (i < n)
649
0
    res = isl_ast_graft_list_free(res);
650
4.36k
651
4.36k
  isl_ast_graft_list_free(list);
652
4.36k
  clear_if_nodes(if_node, 0, n_if);
653
4.36k
  free(if_node);
654
4.36k
  return res;
655
4.36k
}
656
657
/* For each graft in "list",
658
 * insert an if node around graft->node testing the condition encoded
659
 * in graft->guard, assuming graft->guard involves any conditions.
660
 * Subsequently remove the guards from the grafts.
661
 */
662
__isl_give isl_ast_graft_list *isl_ast_graft_list_insert_pending_guard_nodes(
663
  __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build)
664
0
{
665
0
  int i, n;
666
0
  isl_set *universe;
667
0
668
0
  list = insert_pending_guard_nodes(list, build);
669
0
  if (!list)
670
0
    return NULL;
671
0
672
0
  universe = isl_set_universe(isl_ast_build_get_space(build, 1));
673
0
  n = isl_ast_graft_list_n_ast_graft(list);
674
0
  for (i = 0; i < n; ++i) {
675
0
    isl_ast_graft *graft;
676
0
677
0
    graft = isl_ast_graft_list_get_ast_graft(list, i);
678
0
    if (!graft)
679
0
      break;
680
0
    isl_set_free(graft->guard);
681
0
    graft->guard = isl_set_copy(universe);
682
0
    if (!graft->guard)
683
0
      graft = isl_ast_graft_free(graft);
684
0
    list = isl_ast_graft_list_set_ast_graft(list, i, graft);
685
0
  }
686
0
  isl_set_free(universe);
687
0
  if (i < n)
688
0
    return isl_ast_graft_list_free(list);
689
0
690
0
  return list;
691
0
}
692
693
/* Collect the nodes contained in the grafts in "list" in a node list.
694
 */
695
static __isl_give isl_ast_node_list *extract_node_list(
696
  __isl_keep isl_ast_graft_list *list)
697
4.36k
{
698
4.36k
  int i, n;
699
4.36k
  isl_ctx *ctx;
700
4.36k
  isl_ast_node_list *node_list;
701
4.36k
702
4.36k
  if (!list)
703
0
    return NULL;
704
4.36k
  ctx = isl_ast_graft_list_get_ctx(list);
705
4.36k
  n = isl_ast_graft_list_n_ast_graft(list);
706
4.36k
  node_list = isl_ast_node_list_alloc(ctx, n);
707
10.2k
  for (i = 0; i < n; 
++i5.88k
) {
708
5.88k
    isl_ast_node *node;
709
5.88k
    isl_ast_graft *graft;
710
5.88k
711
5.88k
    graft = isl_ast_graft_list_get_ast_graft(list, i);
712
5.88k
    node = isl_ast_graft_get_node(graft);
713
5.88k
    node_list = isl_ast_node_list_add(node_list, node);
714
5.88k
    isl_ast_graft_free(graft);
715
5.88k
  }
716
4.36k
717
4.36k
  return node_list;
718
4.36k
}
719
720
/* Look for shared enforced constraints by all the elements in "list"
721
 * on outer loops (with respect to the current depth) and return the result.
722
 *
723
 * If there are no elements in "list", then return the empty set.
724
 */
725
__isl_give isl_basic_set *isl_ast_graft_list_extract_shared_enforced(
726
  __isl_keep isl_ast_graft_list *list,
727
  __isl_keep isl_ast_build *build)
728
3.90k
{
729
3.90k
  int i, n;
730
3.90k
  int depth;
731
3.90k
  isl_space *space;
732
3.90k
  isl_basic_set *enforced;
733
3.90k
734
3.90k
  if (!list)
735
0
    return NULL;
736
3.90k
737
3.90k
  space = isl_ast_build_get_space(build, 1);
738
3.90k
  enforced = isl_basic_set_empty(space);
739
3.90k
740
3.90k
  depth = isl_ast_build_get_depth(build);
741
3.90k
  n = isl_ast_graft_list_n_ast_graft(list);
742
9.39k
  for (i = 0; i < n; 
++i5.49k
) {
743
5.49k
    isl_ast_graft *graft;
744
5.49k
745
5.49k
    graft = isl_ast_graft_list_get_ast_graft(list, i);
746
5.49k
    enforced = update_enforced(enforced, graft, depth);
747
5.49k
    isl_ast_graft_free(graft);
748
5.49k
  }
749
3.90k
750
3.90k
  return enforced;
751
3.90k
}
752
753
/* Record "guard" in "graft" so that it will be enforced somewhere
754
 * up the tree.  If the graft already has a guard, then it may be partially
755
 * redundant in combination with the new guard and in the context
756
 * the generated constraints of "build".  In fact, the new guard
757
 * may in itself have some redundant constraints.
758
 * We therefore (re)compute the gist of the intersection
759
 * and coalesce the result.
760
 */
761
static __isl_give isl_ast_graft *store_guard(__isl_take isl_ast_graft *graft,
762
  __isl_take isl_set *guard, __isl_keep isl_ast_build *build)
763
6.06k
{
764
6.06k
  int is_universe;
765
6.06k
766
6.06k
  if (!graft)
767
0
    goto error;
768
6.06k
769
6.06k
  is_universe = isl_set_plain_is_universe(guard);
770
6.06k
  if (is_universe < 0)
771
0
    goto error;
772
6.06k
  if (is_universe) {
773
5.01k
    isl_set_free(guard);
774
5.01k
    return graft;
775
5.01k
  }
776
1.05k
777
1.05k
  graft->guard = isl_set_intersect(graft->guard, guard);
778
1.05k
  graft->guard = isl_set_gist(graft->guard,
779
1.05k
            isl_ast_build_get_generated(build));
780
1.05k
  graft->guard = isl_set_coalesce(graft->guard);
781
1.05k
  if (!graft->guard)
782
0
    return isl_ast_graft_free(graft);
783
1.05k
784
1.05k
  return graft;
785
0
error:
786
0
  isl_set_free(guard);
787
0
  return isl_ast_graft_free(graft);
788
1.05k
}
789
790
/* For each graft in "list", replace its guard with the gist with
791
 * respect to "context".
792
 */
793
static __isl_give isl_ast_graft_list *gist_guards(
794
  __isl_take isl_ast_graft_list *list, __isl_keep isl_set *context)
795
3.91k
{
796
3.91k
  int i, n;
797
3.91k
798
3.91k
  if (!list)
799
0
    return NULL;
800
3.91k
801
3.91k
  n = isl_ast_graft_list_n_ast_graft(list);
802
9.41k
  for (i = 0; i < n; 
++i5.50k
) {
803
5.50k
    isl_ast_graft *graft;
804
5.50k
805
5.50k
    graft = isl_ast_graft_list_get_ast_graft(list, i);
806
5.50k
    if (!graft)
807
0
      break;
808
5.50k
    graft->guard = isl_set_gist(graft->guard,
809
5.50k
            isl_set_copy(context));
810
5.50k
    if (!graft->guard)
811
0
      graft = isl_ast_graft_free(graft);
812
5.50k
    list = isl_ast_graft_list_set_ast_graft(list, i, graft);
813
5.50k
  }
814
3.91k
  if (i < n)
815
0
    return isl_ast_graft_list_free(list);
816
3.91k
817
3.91k
  return list;
818
3.91k
}
819
820
/* For each graft in "list", replace its guard with the gist with
821
 * respect to "context".
822
 */
823
__isl_give isl_ast_graft_list *isl_ast_graft_list_gist_guards(
824
  __isl_take isl_ast_graft_list *list, __isl_take isl_set *context)
825
7
{
826
7
  list = gist_guards(list, context);
827
7
  isl_set_free(context);
828
7
829
7
  return list;
830
7
}
831
832
/* Allocate a graft in "build" based on the list of grafts in "sub_build".
833
 * "guard" and "enforced" are the guard and enforced constraints
834
 * of the allocated graft.  The guard is used to simplify the guards
835
 * of the elements in "list".
836
 *
837
 * The node is initialized to either a block containing the nodes of "children"
838
 * or, if there is only a single child, the node of that child.
839
 * If the current level requires a for node, it should be inserted by
840
 * a subsequent call to isl_ast_graft_insert_for.
841
 */
842
__isl_give isl_ast_graft *isl_ast_graft_alloc_from_children(
843
  __isl_take isl_ast_graft_list *list, __isl_take isl_set *guard,
844
  __isl_take isl_basic_set *enforced, __isl_keep isl_ast_build *build,
845
  __isl_keep isl_ast_build *sub_build)
846
3.90k
{
847
3.90k
  isl_ast_build *guard_build;
848
3.90k
  isl_ast_node *node;
849
3.90k
  isl_ast_node_list *node_list;
850
3.90k
  isl_ast_graft *graft;
851
3.90k
852
3.90k
  guard_build = isl_ast_build_copy(sub_build);
853
3.90k
  guard_build = isl_ast_build_replace_pending_by_guard(guard_build,
854
3.90k
            isl_set_copy(guard));
855
3.90k
  list = gist_guards(list, guard);
856
3.90k
  list = insert_pending_guard_nodes(list, guard_build);
857
3.90k
  isl_ast_build_free(guard_build);
858
3.90k
859
3.90k
  node_list = extract_node_list(list);
860
3.90k
  node = isl_ast_node_from_ast_node_list(node_list);
861
3.90k
  isl_ast_graft_list_free(list);
862
3.90k
863
3.90k
  graft = isl_ast_graft_alloc(node, build);
864
3.90k
  graft = store_guard(graft, guard, build);
865
3.90k
  graft = isl_ast_graft_enforce(graft, enforced);
866
3.90k
867
3.90k
  return graft;
868
3.90k
}
869
870
/* Combine the grafts in the list into a single graft.
871
 *
872
 * The guard is initialized to the shared guard of the list elements (if any),
873
 * provided it does not depend on the current dimension.
874
 * The guards in the elements are then simplified with respect to the
875
 * hoisted guard and materialized as if nodes around the contained AST nodes
876
 * in the context of "sub_build".
877
 *
878
 * The enforced set is initialized to the simple hull of the enforced sets
879
 * of the elements, provided the ast_build_exploit_nested_bounds option is set
880
 * or the new graft will be used at the same level.
881
 *
882
 * The node is initialized to either a block containing the nodes of "list"
883
 * or, if there is only a single element, the node of that element.
884
 */
885
static __isl_give isl_ast_graft *ast_graft_list_fuse(
886
  __isl_take isl_ast_graft_list *list, __isl_keep isl_ast_build *build)
887
49
{
888
49
  isl_ast_graft *graft;
889
49
  isl_basic_set *enforced;
890
49
  isl_set *guard;
891
49
892
49
  if (!list)
893
0
    return NULL;
894
49
895
49
  enforced = isl_ast_graft_list_extract_shared_enforced(list, build);
896
49
  guard = isl_ast_graft_list_extract_hoistable_guard(list, build);
897
49
  graft = isl_ast_graft_alloc_from_children(list, guard, enforced,
898
49
                build, build);
899
49
900
49
  return graft;
901
49
}
902
903
/* Combine the grafts in the list into a single graft.
904
 * Return a list containing this single graft.
905
 * If the original list is empty, then return an empty list.
906
 */
907
__isl_give isl_ast_graft_list *isl_ast_graft_list_fuse(
908
  __isl_take isl_ast_graft_list *list,
909
  __isl_keep isl_ast_build *build)
910
1.00k
{
911
1.00k
  isl_ast_graft *graft;
912
1.00k
913
1.00k
  if (!list)
914
0
    return NULL;
915
1.00k
  if (isl_ast_graft_list_n_ast_graft(list) <= 1)
916
983
    return list;
917
25
  graft = ast_graft_list_fuse(list, build);
918
25
  return isl_ast_graft_list_from_ast_graft(graft);
919
25
}
920
921
/* Combine the two grafts into a single graft.
922
 * Return a list containing this single graft.
923
 */
924
static __isl_give isl_ast_graft *isl_ast_graft_fuse(
925
  __isl_take isl_ast_graft *graft1, __isl_take isl_ast_graft *graft2,
926
  __isl_keep isl_ast_build *build)
927
24
{
928
24
  isl_ctx *ctx;
929
24
  isl_ast_graft_list *list;
930
24
931
24
  ctx = isl_ast_build_get_ctx(build);
932
24
933
24
  list = isl_ast_graft_list_alloc(ctx, 2);
934
24
  list = isl_ast_graft_list_add(list, graft1);
935
24
  list = isl_ast_graft_list_add(list, graft2);
936
24
937
24
  return ast_graft_list_fuse(list, build);
938
24
}
939
940
/* Insert a for node enclosing the current graft->node.
941
 */
942
__isl_give isl_ast_graft *isl_ast_graft_insert_for(
943
  __isl_take isl_ast_graft *graft, __isl_take isl_ast_node *node)
944
699
{
945
699
  if (!graft)
946
0
    goto error;
947
699
948
699
  graft->node = isl_ast_node_for_set_body(node, graft->node);
949
699
  if (!graft->node)
950
0
    return isl_ast_graft_free(graft);
951
699
952
699
  return graft;
953
0
error:
954
0
  isl_ast_node_free(node);
955
0
  isl_ast_graft_free(graft);
956
0
  return NULL;
957
699
}
958
959
/* Insert a mark governing the current graft->node.
960
 */
961
__isl_give isl_ast_graft *isl_ast_graft_insert_mark(
962
  __isl_take isl_ast_graft *graft, __isl_take isl_id *mark)
963
154
{
964
154
  if (!graft)
965
0
    goto error;
966
154
967
154
  graft->node = isl_ast_node_alloc_mark(mark, graft->node);
968
154
  if (!graft->node)
969
0
    return isl_ast_graft_free(graft);
970
154
971
154
  return graft;
972
0
error:
973
0
  isl_id_free(mark);
974
0
  isl_ast_graft_free(graft);
975
0
  return NULL;
976
154
}
977
978
/* Represent the graft list as an AST node.
979
 * This operation drops the information about guards in the grafts, so
980
 * if there are any pending guards, then they are materialized as if nodes.
981
 */
982
__isl_give isl_ast_node *isl_ast_node_from_graft_list(
983
  __isl_take isl_ast_graft_list *list,
984
  __isl_keep isl_ast_build *build)
985
453
{
986
453
  isl_ast_node_list *node_list;
987
453
988
453
  list = insert_pending_guard_nodes(list, build);
989
453
  node_list = extract_node_list(list);
990
453
  isl_ast_graft_list_free(list);
991
453
992
453
  return isl_ast_node_from_ast_node_list(node_list);
993
453
}
994
995
void *isl_ast_graft_free(__isl_take isl_ast_graft *graft)
996
44.4k
{
997
44.4k
  if (!graft)
998
0
    return NULL;
999
44.4k
1000
44.4k
  if (--graft->ref > 0)
1001
38.3k
    return NULL;
1002
6.06k
1003
6.06k
  isl_ast_node_free(graft->node);
1004
6.06k
  isl_set_free(graft->guard);
1005
6.06k
  isl_basic_set_free(graft->enforced);
1006
6.06k
  free(graft);
1007
6.06k
1008
6.06k
  return NULL;
1009
6.06k
}
1010
1011
/* Record that the grafted tree enforces
1012
 * "enforced" by intersecting graft->enforced with "enforced".
1013
 */
1014
__isl_give isl_ast_graft *isl_ast_graft_enforce(
1015
  __isl_take isl_ast_graft *graft, __isl_take isl_basic_set *enforced)
1016
4.60k
{
1017
4.60k
  if (!graft || !enforced)
1018
0
    goto error;
1019
4.60k
1020
4.60k
  enforced = isl_basic_set_align_params(enforced,
1021
4.60k
        isl_basic_set_get_space(graft->enforced));
1022
4.60k
  graft->enforced = isl_basic_set_align_params(graft->enforced,
1023
4.60k
        isl_basic_set_get_space(enforced));
1024
4.60k
  graft->enforced = isl_basic_set_intersect(graft->enforced, enforced);
1025
4.60k
  if (!graft->enforced)
1026
0
    return isl_ast_graft_free(graft);
1027
4.60k
1028
4.60k
  return graft;
1029
0
error:
1030
0
  isl_basic_set_free(enforced);
1031
0
  return isl_ast_graft_free(graft);
1032
4.60k
}
1033
1034
__isl_give isl_basic_set *isl_ast_graft_get_enforced(
1035
  __isl_keep isl_ast_graft *graft)
1036
6.17k
{
1037
6.17k
  return graft ? isl_basic_set_copy(graft->enforced) : NULL;
1038
6.17k
}
1039
1040
__isl_give isl_set *isl_ast_graft_get_guard(__isl_keep isl_ast_graft *graft)
1041
0
{
1042
0
  return graft ? isl_set_copy(graft->guard) : NULL;
1043
0
}
1044
1045
/* Record that "guard" needs to be inserted in "graft".
1046
 */
1047
__isl_give isl_ast_graft *isl_ast_graft_add_guard(
1048
  __isl_take isl_ast_graft *graft,
1049
  __isl_take isl_set *guard, __isl_keep isl_ast_build *build)
1050
2.16k
{
1051
2.16k
  return store_guard(graft, guard, build);
1052
2.16k
}
1053
1054
/* Reformulate the "graft", which was generated in the context
1055
 * of an inner code generation, in terms of the outer code generation
1056
 * AST build.
1057
 *
1058
 * If "product" is set, then the domain of the inner code generation build is
1059
 *
1060
 *  [O -> S]
1061
 *
1062
 * with O the domain of the outer code generation build.
1063
 * We essentially need to project out S.
1064
 *
1065
 * If "product" is not set, then we need to project the domains onto
1066
 * their parameter spaces.
1067
 */
1068
__isl_give isl_ast_graft *isl_ast_graft_unembed(__isl_take isl_ast_graft *graft,
1069
  int product)
1070
734
{
1071
734
  isl_basic_set *enforced;
1072
734
1073
734
  if (!graft)
1074
0
    return NULL;
1075
734
1076
734
  if (product) {
1077
726
    enforced = graft->enforced;
1078
726
    enforced = isl_basic_map_domain(isl_basic_set_unwrap(enforced));
1079
726
    graft->enforced = enforced;
1080
726
    graft->guard = isl_map_domain(isl_set_unwrap(graft->guard));
1081
726
  } else {
1082
8
    graft->enforced = isl_basic_set_params(graft->enforced);
1083
8
    graft->guard = isl_set_params(graft->guard);
1084
8
  }
1085
734
  graft->guard = isl_set_compute_divs(graft->guard);
1086
734
1087
734
  if (!graft->enforced || !graft->guard)
1088
0
    return isl_ast_graft_free(graft);
1089
734
1090
734
  return graft;
1091
734
}
1092
1093
/* Reformulate the grafts in "list", which were generated in the context
1094
 * of an inner code generation, in terms of the outer code generation
1095
 * AST build.
1096
 */
1097
__isl_give isl_ast_graft_list *isl_ast_graft_list_unembed(
1098
  __isl_take isl_ast_graft_list *list, int product)
1099
623
{
1100
623
  int i, n;
1101
623
1102
623
  n = isl_ast_graft_list_n_ast_graft(list);
1103
1.35k
  for (i = 0; i < n; 
++i734
) {
1104
734
    isl_ast_graft *graft;
1105
734
1106
734
    graft = isl_ast_graft_list_get_ast_graft(list, i);
1107
734
    graft = isl_ast_graft_unembed(graft, product);
1108
734
    list = isl_ast_graft_list_set_ast_graft(list, i, graft);
1109
734
  }
1110
623
1111
623
  return list;
1112
623
}
1113
1114
/* Compute the preimage of "graft" under the function represented by "ma".
1115
 * In other words, plug in "ma" in "enforced" and "guard" fields of "graft".
1116
 */
1117
__isl_give isl_ast_graft *isl_ast_graft_preimage_multi_aff(
1118
  __isl_take isl_ast_graft *graft, __isl_take isl_multi_aff *ma)
1119
3
{
1120
3
  isl_basic_set *enforced;
1121
3
1122
3
  if (!graft)
1123
0
    return NULL;
1124
3
1125
3
  enforced = graft->enforced;
1126
3
  graft->enforced = isl_basic_set_preimage_multi_aff(enforced,
1127
3
            isl_multi_aff_copy(ma));
1128
3
  graft->guard = isl_set_preimage_multi_aff(graft->guard, ma);
1129
3
1130
3
  if (!graft->enforced || !graft->guard)
1131
0
    return isl_ast_graft_free(graft);
1132
3
1133
3
  return graft;
1134
3
}
1135
1136
/* Compute the preimage of all the grafts in "list" under
1137
 * the function represented by "ma".
1138
 */
1139
__isl_give isl_ast_graft_list *isl_ast_graft_list_preimage_multi_aff(
1140
  __isl_take isl_ast_graft_list *list, __isl_take isl_multi_aff *ma)
1141
3
{
1142
3
  int i, n;
1143
3
1144
3
  n = isl_ast_graft_list_n_ast_graft(list);
1145
6
  for (i = 0; i < n; 
++i3
) {
1146
3
    isl_ast_graft *graft;
1147
3
1148
3
    graft = isl_ast_graft_list_get_ast_graft(list, i);
1149
3
    graft = isl_ast_graft_preimage_multi_aff(graft,
1150
3
                isl_multi_aff_copy(ma));
1151
3
    list = isl_ast_graft_list_set_ast_graft(list, i, graft);
1152
3
  }
1153
3
1154
3
  isl_multi_aff_free(ma);
1155
3
  return list;
1156
3
}
1157
1158
/* Compare two grafts based on their guards.
1159
 */
1160
static int cmp_graft(__isl_keep isl_ast_graft *a, __isl_keep isl_ast_graft *b,
1161
  void *user)
1162
20
{
1163
20
  return isl_set_plain_cmp(a->guard, b->guard);
1164
20
}
1165
1166
/* Order the elements in "list" based on their guards.
1167
 */
1168
__isl_give isl_ast_graft_list *isl_ast_graft_list_sort_guard(
1169
  __isl_take isl_ast_graft_list *list)
1170
28
{
1171
28
  return isl_ast_graft_list_sort(list, &cmp_graft, NULL);
1172
28
}
1173
1174
/* Merge the given two lists into a single list of grafts,
1175
 * merging grafts with the same guard into a single graft.
1176
 *
1177
 * "list2" has been sorted using isl_ast_graft_list_sort.
1178
 * "list1" may be the result of a previous call to isl_ast_graft_list_merge
1179
 * and may therefore not be completely sorted.
1180
 *
1181
 * The elements in "list2" need to be executed after those in "list1",
1182
 * but if the guard of a graft in "list2" is disjoint from the guards
1183
 * of some final elements in "list1", then it can be moved up to before
1184
 * those final elements.
1185
 *
1186
 * In particular, we look at each element g of "list2" in turn
1187
 * and move it up beyond elements of "list1" that would be sorted
1188
 * after g as long as each of these elements has a guard that is disjoint
1189
 * from that of g.
1190
 *
1191
 * We do not allow the second or any later element of "list2" to be moved
1192
 * before a previous elements of "list2" even if the reason that
1193
 * that element didn't move up further was that its guard was not disjoint
1194
 * from that of the previous element in "list1".
1195
 */
1196
__isl_give isl_ast_graft_list *isl_ast_graft_list_merge(
1197
  __isl_take isl_ast_graft_list *list1,
1198
  __isl_take isl_ast_graft_list *list2,
1199
  __isl_keep isl_ast_build *build)
1200
160
{
1201
160
  int i, j, first;
1202
160
1203
160
  if (!list1 || !list2 || !build)
1204
0
    goto error;
1205
160
  if (list2->n == 0) {
1206
0
    isl_ast_graft_list_free(list2);
1207
0
    return list1;
1208
0
  }
1209
160
  if (list1->n == 0) {
1210
114
    isl_ast_graft_list_free(list1);
1211
114
    return list2;
1212
114
  }
1213
46
1214
46
  first = 0;
1215
93
  for (i = 0; i < list2->n; 
++i47
) {
1216
47
    isl_ast_graft *graft;
1217
47
    graft = isl_ast_graft_list_get_ast_graft(list2, i);
1218
47
    if (!graft)
1219
0
      break;
1220
47
1221
49
    
for (j = list1->n; 47
j >= 0;
--j2
) {
1222
49
      int cmp, disjoint;
1223
49
      isl_ast_graft *graft_j;
1224
49
1225
49
      if (j == first)
1226
2
        cmp = -1;
1227
47
      else
1228
47
        cmp = isl_set_plain_cmp(list1->p[j - 1]->guard,
1229
47
              graft->guard);
1230
49
      if (cmp > 0) {
1231
9
        disjoint = isl_set_is_disjoint(graft->guard,
1232
9
              list1->p[j - 1]->guard);
1233
9
        if (disjoint < 0) {
1234
0
          isl_ast_graft_free(graft);
1235
0
          list1 = isl_ast_graft_list_free(list1);
1236
0
          break;
1237
0
        }
1238
9
        if (!disjoint)
1239
7
          cmp = -1;
1240
9
      }
1241
49
      if (cmp > 0)
1242
2
        continue;
1243
47
      if (cmp < 0) {
1244
23
        list1 = isl_ast_graft_list_insert(list1, j,
1245
23
                graft);
1246
23
        break;
1247
23
      }
1248
24
1249
24
      --j;
1250
24
1251
24
      graft_j = isl_ast_graft_list_get_ast_graft(list1, j);
1252
24
      graft_j = isl_ast_graft_fuse(graft_j, graft, build);
1253
24
      list1 = isl_ast_graft_list_set_ast_graft(list1, j,
1254
24
                graft_j);
1255
24
      break;
1256
24
    }
1257
47
1258
47
    if (j < 0) {
1259
0
      isl_ast_graft_free(graft);
1260
0
      isl_die(isl_ast_build_get_ctx(build),
1261
0
        isl_error_internal,
1262
0
        "element failed to get inserted", break);
1263
0
    }
1264
47
1265
47
    first = j + 1;
1266
47
    if (!list1)
1267
0
      break;
1268
47
  }
1269
46
  if (i < list2->n)
1270
0
    list1 = isl_ast_graft_list_free(list1);
1271
46
  isl_ast_graft_list_free(list2);
1272
46
1273
46
  return list1;
1274
0
error:
1275
0
  isl_ast_graft_list_free(list1);
1276
0
  isl_ast_graft_list_free(list2);
1277
0
  return NULL;
1278
46
}
1279
1280
__isl_give isl_printer *isl_printer_print_ast_graft(__isl_take isl_printer *p,
1281
  __isl_keep isl_ast_graft *graft)
1282
0
{
1283
0
  if (!p)
1284
0
    return NULL;
1285
0
  if (!graft)
1286
0
    return isl_printer_free(p);
1287
0
1288
0
  p = isl_printer_print_str(p, "(");
1289
0
  p = isl_printer_print_str(p, "guard: ");
1290
0
  p = isl_printer_print_set(p, graft->guard);
1291
0
  p = isl_printer_print_str(p, ", ");
1292
0
  p = isl_printer_print_str(p, "enforced: ");
1293
0
  p = isl_printer_print_basic_set(p, graft->enforced);
1294
0
  p = isl_printer_print_str(p, ", ");
1295
0
  p = isl_printer_print_str(p, "node: ");
1296
0
  p = isl_printer_print_ast_node(p, graft->node);
1297
0
  p = isl_printer_print_str(p, ")");
1298
0
1299
0
  return p;
1300
0
}