Coverage Report

Created: 2018-04-24 22:41

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