Coverage Report

Created: 2017-08-18 19:41

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