File: | polly/lib/External/isl/isl_ast_graft.c |
Warning: | line 605, column 4 Value stored to 'graft' is never read |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
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 BASEast_graft |
24 | #define BASEast_graft ast_graft |
25 | |
26 | #include <isl_list_templ.c> |
27 | |
28 | #undef BASEast_graft |
29 | #define BASEast_graft ast_graft |
30 | #include <print_templ.c> |
31 | |
32 | isl_ctx *isl_ast_graft_get_ctx(__isl_keep isl_ast_graft *graft) |
33 | { |
34 | if (!graft) |
35 | return NULL((void*)0); |
36 | return isl_basic_set_get_ctx(graft->enforced); |
37 | } |
38 | |
39 | __isl_give isl_ast_node *isl_ast_graft_get_node( |
40 | __isl_keep isl_ast_graft *graft) |
41 | { |
42 | return graft ? isl_ast_node_copy(graft->node) : NULL((void*)0); |
43 | } |
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 | { |
50 | isl_ctx *ctx; |
51 | isl_space *space; |
52 | isl_ast_graft *graft; |
53 | |
54 | if (!node) |
55 | return NULL((void*)0); |
56 | |
57 | ctx = isl_ast_node_get_ctx(node); |
58 | graft = isl_calloc_type(ctx, isl_ast_graft)((isl_ast_graft *)isl_calloc_or_die(ctx, 1, sizeof(isl_ast_graft ))); |
59 | if (!graft) |
60 | goto error; |
61 | |
62 | space = isl_ast_build_get_space(build, 1); |
63 | |
64 | graft->ref = 1; |
65 | graft->node = node; |
66 | graft->guard = isl_set_universe(isl_space_copy(space)); |
67 | graft->enforced = isl_basic_set_universe(space); |
68 | |
69 | if (!graft->guard || !graft->enforced) |
70 | return isl_ast_graft_free(graft); |
71 | |
72 | return graft; |
73 | error: |
74 | isl_ast_node_free(node); |
75 | return NULL((void*)0); |
76 | } |
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 | { |
85 | isl_ast_node *node; |
86 | |
87 | node = isl_ast_build_call_from_executed(build, executed); |
88 | |
89 | return isl_ast_graft_alloc(node, build); |
90 | } |
91 | |
92 | static __isl_give isl_ast_graft *isl_ast_graft_copy( |
93 | __isl_keep isl_ast_graft *graft) |
94 | { |
95 | if (!graft) |
96 | return NULL((void*)0); |
97 | |
98 | graft->ref++; |
99 | return graft; |
100 | } |
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 | { |
108 | int i, n; |
109 | int depth; |
110 | isl_ast_graft *graft_0; |
111 | int equal = 1; |
112 | int skip; |
113 | |
114 | graft_0 = isl_ast_graft_list_get_ast_graft(list, 0); |
115 | if (!graft_0) |
116 | return -1; |
117 | |
118 | depth = isl_ast_build_get_depth(build); |
119 | if (isl_set_dim(graft_0->guard, isl_dim_set) <= depth) |
120 | skip = 0; |
121 | else |
122 | skip = isl_set_involves_dims(graft_0->guard, |
123 | isl_dim_set, depth, 1); |
124 | if (skip < 0 || skip) { |
125 | isl_ast_graft_free(graft_0); |
126 | return skip < 0 ? -1 : 0; |
127 | } |
128 | |
129 | n = isl_ast_graft_list_n_ast_graft(list); |
130 | for (i = 1; i < n; ++i) { |
131 | isl_ast_graft *graft; |
132 | graft = isl_ast_graft_list_get_ast_graft(list, i); |
133 | if (!graft) |
134 | equal = -1; |
135 | else |
136 | equal = isl_set_is_equal(graft_0->guard, graft->guard); |
137 | isl_ast_graft_free(graft); |
138 | if (equal < 0 || !equal) |
139 | break; |
140 | } |
141 | |
142 | isl_ast_graft_free(graft_0); |
143 | |
144 | return equal; |
145 | } |
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 | { |
154 | int depth; |
155 | |
156 | depth = isl_ast_build_get_depth(build); |
157 | if (depth < isl_set_dim(guard, isl_dim_set)) { |
158 | guard = isl_set_remove_divs_involving_dims(guard, |
159 | isl_dim_set, depth, 1); |
160 | guard = isl_set_eliminate(guard, isl_dim_set, depth, 1); |
161 | guard = isl_set_compute_divs(guard); |
162 | } |
163 | |
164 | return guard; |
165 | } |
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 | { |
196 | int i, n; |
197 | int equal; |
198 | isl_ctx *ctx; |
199 | isl_set *guard; |
200 | isl_set_list *set_list; |
201 | isl_basic_set *hull; |
202 | |
203 | if (!list || !build) |
204 | return NULL((void*)0); |
205 | |
206 | n = isl_ast_graft_list_n_ast_graft(list); |
207 | if (n == 0) |
208 | return isl_set_universe(isl_ast_build_get_space(build, 1)); |
209 | |
210 | equal = equal_independent_guards(list, build); |
211 | if (equal < 0) |
212 | return NULL((void*)0); |
213 | |
214 | if (equal || n == 1) { |
215 | isl_ast_graft *graft_0; |
216 | |
217 | graft_0 = isl_ast_graft_list_get_ast_graft(list, 0); |
218 | if (!graft_0) |
219 | return NULL((void*)0); |
220 | guard = isl_set_copy(graft_0->guard); |
221 | if (!equal) |
222 | guard = hoist_guard(guard, build); |
223 | isl_ast_graft_free(graft_0); |
224 | return guard; |
225 | } |
226 | |
227 | ctx = isl_ast_build_get_ctx(build); |
228 | set_list = isl_set_list_alloc(ctx, n); |
229 | guard = isl_set_empty(isl_ast_build_get_space(build, 1)); |
230 | for (i = 0; i < n; ++i) { |
231 | isl_ast_graft *graft; |
232 | isl_basic_set *enforced; |
233 | isl_set *guard_i; |
234 | |
235 | graft = isl_ast_graft_list_get_ast_graft(list, i); |
236 | enforced = isl_ast_graft_get_enforced(graft); |
237 | guard_i = isl_set_copy(graft->guard); |
238 | isl_ast_graft_free(graft); |
239 | set_list = isl_set_list_add(set_list, isl_set_copy(guard_i)); |
240 | guard_i = isl_set_intersect(guard_i, |
241 | isl_set_from_basic_set(enforced)); |
242 | guard_i = isl_set_intersect(guard_i, |
243 | isl_ast_build_get_domain(build)); |
244 | guard = isl_set_union(guard, guard_i); |
245 | } |
246 | hull = isl_set_unshifted_simple_hull_from_set_list(guard, set_list); |
247 | guard = isl_set_from_basic_set(hull); |
248 | return hoist_guard(guard, build); |
249 | } |
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 | { |
278 | struct isl_insert_if_data data; |
279 | isl_ctx *ctx; |
280 | |
281 | ctx = isl_ast_build_get_ctx(build); |
282 | if (isl_options_get_ast_build_allow_or(ctx) || |
283 | isl_set_n_basic_set(guard) <= 1) { |
284 | isl_ast_node *if_node; |
285 | isl_ast_expr *expr; |
286 | |
287 | expr = isl_ast_build_expr_from_set_internal(build, guard); |
288 | |
289 | if_node = isl_ast_node_alloc_if(expr); |
290 | return isl_ast_node_if_set_then(if_node, node); |
291 | } |
292 | |
293 | guard = isl_set_make_disjoint(guard); |
294 | |
295 | data.list = isl_ast_node_list_alloc(ctx, 0); |
296 | data.node = node; |
297 | data.build = build; |
298 | if (isl_set_foreach_basic_set(guard, &insert_if, &data) < 0) |
299 | data.list = isl_ast_node_list_free(data.list); |
300 | |
301 | isl_set_free(guard); |
302 | isl_ast_node_free(data.node); |
303 | return isl_ast_node_alloc_block(data.list); |
304 | } |
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 | { |
311 | struct isl_insert_if_data *data = user; |
312 | isl_ast_node *node; |
313 | isl_set *set; |
314 | |
315 | set = isl_set_from_basic_set(bset); |
316 | node = isl_ast_node_copy(data->node); |
317 | node = ast_node_insert_if(node, set, data->build); |
318 | data->list = isl_ast_node_list_add(data->list, node); |
319 | |
320 | return isl_stat_ok; |
321 | } |
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 | { |
330 | int univ; |
331 | |
332 | if (!graft) |
333 | goto error; |
334 | |
335 | univ = isl_set_plain_is_universe(guard); |
336 | if (univ < 0) |
337 | goto error; |
338 | if (univ) { |
339 | isl_set_free(guard); |
340 | return graft; |
341 | } |
342 | |
343 | build = isl_ast_build_copy(build); |
344 | graft->node = ast_node_insert_if(graft->node, guard, build); |
345 | isl_ast_build_free(build); |
346 | |
347 | if (!graft->node) |
348 | return isl_ast_graft_free(graft); |
349 | |
350 | return graft; |
351 | error: |
352 | isl_set_free(guard); |
353 | return isl_ast_graft_free(graft); |
354 | } |
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 | { |
362 | if (!graft) |
363 | return NULL((void*)0); |
364 | |
365 | return insert_if_node(graft, isl_set_copy(graft->guard), build); |
366 | } |
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 | { |
373 | if (!graft || !enforced) |
374 | goto error; |
375 | |
376 | isl_basic_set_free(graft->enforced); |
377 | graft->enforced = enforced; |
378 | |
379 | return graft; |
380 | error: |
381 | isl_basic_set_free(enforced); |
382 | return isl_ast_graft_free(graft); |
383 | } |
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 | { |
392 | isl_basic_set *enforced_g; |
393 | |
394 | enforced_g = isl_ast_graft_get_enforced(graft); |
395 | if (depth < isl_basic_set_dim(enforced_g, isl_dim_set)) |
396 | enforced_g = isl_basic_set_eliminate(enforced_g, |
397 | isl_dim_set, depth, 1); |
398 | enforced_g = isl_basic_set_remove_unknown_divs(enforced_g); |
399 | enforced_g = isl_basic_set_align_params(enforced_g, |
400 | isl_basic_set_get_space(enforced)); |
401 | enforced = isl_basic_set_align_params(enforced, |
402 | isl_basic_set_get_space(enforced_g)); |
403 | enforced = isl_set_simple_hull(isl_basic_set_union(enforced, |
404 | enforced_g)); |
405 | |
406 | return enforced; |
407 | } |
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 | { |
419 | isl_ast_node_list *list; |
420 | |
421 | if (!*body) { |
422 | *body = node; |
423 | return; |
424 | } |
425 | |
426 | if ((*body)->type == isl_ast_node_block) { |
427 | list = isl_ast_node_block_get_children(*body); |
428 | isl_ast_node_free(*body); |
429 | } else |
430 | list = isl_ast_node_list_from_ast_node(*body); |
431 | list = isl_ast_node_list_add(list, node); |
432 | *body = isl_ast_node_alloc_block(list); |
433 | } |
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 | { |
447 | int n; |
448 | int depth; |
449 | isl_ast_graft *last; |
450 | isl_space *space; |
451 | isl_basic_set *enforced; |
452 | |
453 | if (!list || !graft) |
454 | goto error; |
455 | extend_body(body, isl_ast_node_copy(graft->node)); |
456 | if (!*body) |
457 | goto error; |
458 | |
459 | n = isl_ast_graft_list_n_ast_graft(list); |
460 | last = isl_ast_graft_list_get_ast_graft(list, n - 1); |
461 | |
462 | depth = isl_ast_build_get_depth(build); |
463 | space = isl_ast_build_get_space(build, 1); |
464 | enforced = isl_basic_set_empty(space); |
465 | enforced = update_enforced(enforced, last, depth); |
466 | enforced = update_enforced(enforced, graft, depth); |
467 | last = isl_ast_graft_set_enforced(last, enforced); |
468 | |
469 | list = isl_ast_graft_list_set_ast_graft(list, n - 1, last); |
470 | isl_ast_graft_free(graft); |
471 | return list; |
472 | error: |
473 | isl_ast_graft_free(graft); |
474 | return isl_ast_graft_list_free(list); |
475 | } |
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 | { |
485 | return graft_extend_body(list, &last_if->u.i.then, graft, build); |
486 | } |
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 | { |
496 | return graft_extend_body(list, &last_if->u.i.else_node, graft, build); |
497 | } |
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 | { |
516 | int i; |
517 | |
518 | for (i = first; i < n; ++i) { |
519 | isl_set_free(if_node[i].guard); |
520 | isl_set_free(if_node[i].complement); |
521 | } |
522 | |
523 | return first; |
524 | } |
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 | { |
546 | int i, j, n, n_if; |
547 | int allow_else; |
548 | isl_ctx *ctx; |
549 | isl_ast_graft_list *res; |
550 | struct isl_if_node *if_node = NULL((void*)0); |
551 | |
552 | if (!build || !list) |
553 | return isl_ast_graft_list_free(list); |
554 | |
555 | ctx = isl_ast_build_get_ctx(build); |
556 | n = isl_ast_graft_list_n_ast_graft(list); |
557 | |
558 | allow_else = isl_options_get_ast_build_allow_else(ctx); |
559 | |
560 | n_if = 0; |
561 | if (n > 1) { |
562 | if_node = isl_alloc_array(ctx, struct isl_if_node, n - 1)((struct isl_if_node *)isl_malloc_or_die(ctx, (n - 1)*sizeof( struct isl_if_node))); |
563 | if (!if_node) |
564 | return isl_ast_graft_list_free(list); |
565 | } |
566 | |
567 | res = isl_ast_graft_list_alloc(ctx, n); |
568 | |
569 | for (i = 0; i < n; ++i) { |
570 | isl_set *guard; |
571 | isl_ast_graft *graft; |
572 | int subset, found_then, found_else; |
573 | isl_ast_node *node; |
574 | |
575 | graft = isl_ast_graft_list_get_ast_graft(list, i); |
576 | if (!graft) |
577 | break; |
578 | subset = 0; |
579 | found_then = found_else = -1; |
580 | if (n_if > 0) { |
581 | isl_set *test; |
582 | test = isl_set_copy(graft->guard); |
583 | test = isl_set_intersect(test, |
584 | isl_set_copy(build->domain)); |
585 | for (j = n_if - 1; j >= 0; --j) { |
586 | subset = isl_set_is_subset(test, |
587 | if_node[j].guard); |
588 | if (subset < 0 || subset) { |
589 | found_then = j; |
590 | break; |
591 | } |
592 | if (!allow_else) |
593 | continue; |
594 | subset = isl_set_is_subset(test, |
595 | if_node[j].complement); |
596 | if (subset < 0 || subset) { |
597 | found_else = j; |
598 | break; |
599 | } |
600 | } |
601 | n_if = clear_if_nodes(if_node, j + 1, n_if); |
602 | isl_set_free(test); |
603 | } |
604 | if (subset < 0) { |
605 | graft = isl_ast_graft_free(graft); |
Value stored to 'graft' is never read | |
606 | break; |
607 | } |
608 | |
609 | guard = isl_set_copy(graft->guard); |
610 | if (found_then >= 0) |
611 | graft->guard = isl_set_gist(graft->guard, |
612 | isl_set_copy(if_node[found_then].guard)); |
613 | else if (found_else >= 0) |
614 | graft->guard = isl_set_gist(graft->guard, |
615 | isl_set_copy(if_node[found_else].complement)); |
616 | |
617 | node = graft->node; |
618 | if (!graft->guard) |
619 | graft = isl_ast_graft_free(graft); |
620 | graft = insert_pending_guard_node(graft, build); |
621 | if (graft && graft->node != node && i != n - 1) { |
622 | isl_set *set; |
623 | if_node[n_if].node = graft->node; |
624 | if_node[n_if].guard = guard; |
625 | if (found_then >= 0) |
626 | set = if_node[found_then].guard; |
627 | else if (found_else >= 0) |
628 | set = if_node[found_else].complement; |
629 | else |
630 | set = build->domain; |
631 | set = isl_set_copy(set); |
632 | set = isl_set_subtract(set, isl_set_copy(guard)); |
633 | if_node[n_if].complement = set; |
634 | n_if++; |
635 | } else |
636 | isl_set_free(guard); |
637 | if (!graft) |
638 | break; |
639 | |
640 | if (found_then >= 0) |
641 | res = extend_then(res, if_node[found_then].node, |
642 | graft, build); |
643 | else if (found_else >= 0) |
644 | res = extend_else(res, if_node[found_else].node, |
645 | graft, build); |
646 | else |
647 | res = isl_ast_graft_list_add(res, graft); |
648 | } |
649 | if (i < n) |
650 | res = isl_ast_graft_list_free(res); |
651 | |
652 | isl_ast_graft_list_free(list); |
653 | clear_if_nodes(if_node, 0, n_if); |
654 | free(if_node); |
655 | return res; |
656 | } |
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 | { |
666 | int i, n; |
667 | isl_set *universe; |
668 | |
669 | list = insert_pending_guard_nodes(list, build); |
670 | if (!list) |
671 | return NULL((void*)0); |
672 | |
673 | universe = isl_set_universe(isl_ast_build_get_space(build, 1)); |
674 | n = isl_ast_graft_list_n_ast_graft(list); |
675 | for (i = 0; i < n; ++i) { |
676 | isl_ast_graft *graft; |
677 | |
678 | graft = isl_ast_graft_list_get_ast_graft(list, i); |
679 | if (!graft) |
680 | break; |
681 | isl_set_free(graft->guard); |
682 | graft->guard = isl_set_copy(universe); |
683 | if (!graft->guard) |
684 | graft = isl_ast_graft_free(graft); |
685 | list = isl_ast_graft_list_set_ast_graft(list, i, graft); |
686 | } |
687 | isl_set_free(universe); |
688 | if (i < n) |
689 | return isl_ast_graft_list_free(list); |
690 | |
691 | return list; |
692 | } |
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 | { |
699 | int i, n; |
700 | isl_ctx *ctx; |
701 | isl_ast_node_list *node_list; |
702 | |
703 | if (!list) |
704 | return NULL((void*)0); |
705 | ctx = isl_ast_graft_list_get_ctx(list); |
706 | n = isl_ast_graft_list_n_ast_graft(list); |
707 | node_list = isl_ast_node_list_alloc(ctx, n); |
708 | for (i = 0; i < n; ++i) { |
709 | isl_ast_node *node; |
710 | isl_ast_graft *graft; |
711 | |
712 | graft = isl_ast_graft_list_get_ast_graft(list, i); |
713 | node = isl_ast_graft_get_node(graft); |
714 | node_list = isl_ast_node_list_add(node_list, node); |
715 | isl_ast_graft_free(graft); |
716 | } |
717 | |
718 | return node_list; |
719 | } |
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 | { |
730 | int i, n; |
731 | int depth; |
732 | isl_space *space; |
733 | isl_basic_set *enforced; |
734 | |
735 | if (!list) |
736 | return NULL((void*)0); |
737 | |
738 | space = isl_ast_build_get_space(build, 1); |
739 | enforced = isl_basic_set_empty(space); |
740 | |
741 | depth = isl_ast_build_get_depth(build); |
742 | n = isl_ast_graft_list_n_ast_graft(list); |
743 | for (i = 0; i < n; ++i) { |
744 | isl_ast_graft *graft; |
745 | |
746 | graft = isl_ast_graft_list_get_ast_graft(list, i); |
747 | enforced = update_enforced(enforced, graft, depth); |
748 | isl_ast_graft_free(graft); |
749 | } |
750 | |
751 | return enforced; |
752 | } |
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 | { |
765 | int is_universe; |
766 | |
767 | if (!graft) |
768 | goto error; |
769 | |
770 | is_universe = isl_set_plain_is_universe(guard); |
771 | if (is_universe < 0) |
772 | goto error; |
773 | if (is_universe) { |
774 | isl_set_free(guard); |
775 | return graft; |
776 | } |
777 | |
778 | graft->guard = isl_set_intersect(graft->guard, guard); |
779 | graft->guard = isl_set_gist(graft->guard, |
780 | isl_ast_build_get_generated(build)); |
781 | graft->guard = isl_set_coalesce(graft->guard); |
782 | if (!graft->guard) |
783 | return isl_ast_graft_free(graft); |
784 | |
785 | return graft; |
786 | error: |
787 | isl_set_free(guard); |
788 | return isl_ast_graft_free(graft); |
789 | } |
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 | { |
797 | int i, n; |
798 | |
799 | if (!list) |
800 | return NULL((void*)0); |
801 | |
802 | n = isl_ast_graft_list_n_ast_graft(list); |
803 | for (i = 0; i < n; ++i) { |
804 | isl_ast_graft *graft; |
805 | |
806 | graft = isl_ast_graft_list_get_ast_graft(list, i); |
807 | if (!graft) |
808 | break; |
809 | graft->guard = isl_set_gist(graft->guard, |
810 | isl_set_copy(context)); |
811 | if (!graft->guard) |
812 | graft = isl_ast_graft_free(graft); |
813 | list = isl_ast_graft_list_set_ast_graft(list, i, graft); |
814 | } |
815 | if (i < n) |
816 | return isl_ast_graft_list_free(list); |
817 | |
818 | return list; |
819 | } |
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 | { |
827 | list = gist_guards(list, context); |
828 | isl_set_free(context); |
829 | |
830 | return list; |
831 | } |
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 | { |
848 | isl_ast_build *guard_build; |
849 | isl_ast_node *node; |
850 | isl_ast_node_list *node_list; |
851 | isl_ast_graft *graft; |
852 | |
853 | guard_build = isl_ast_build_copy(sub_build); |
854 | guard_build = isl_ast_build_replace_pending_by_guard(guard_build, |
855 | isl_set_copy(guard)); |
856 | list = gist_guards(list, guard); |
857 | list = insert_pending_guard_nodes(list, guard_build); |
858 | isl_ast_build_free(guard_build); |
859 | |
860 | node_list = extract_node_list(list); |
861 | node = isl_ast_node_from_ast_node_list(node_list); |
862 | isl_ast_graft_list_free(list); |
863 | |
864 | graft = isl_ast_graft_alloc(node, build); |
865 | graft = store_guard(graft, guard, build); |
866 | graft = isl_ast_graft_enforce(graft, enforced); |
867 | |
868 | return graft; |
869 | } |
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 | { |
889 | isl_ast_graft *graft; |
890 | isl_basic_set *enforced; |
891 | isl_set *guard; |
892 | |
893 | if (!list) |
894 | return NULL((void*)0); |
895 | |
896 | enforced = isl_ast_graft_list_extract_shared_enforced(list, build); |
897 | guard = isl_ast_graft_list_extract_hoistable_guard(list, build); |
898 | graft = isl_ast_graft_alloc_from_children(list, guard, enforced, |
899 | build, build); |
900 | |
901 | return graft; |
902 | } |
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 | { |
912 | isl_ast_graft *graft; |
913 | |
914 | if (!list) |
915 | return NULL((void*)0); |
916 | if (isl_ast_graft_list_n_ast_graft(list) <= 1) |
917 | return list; |
918 | graft = ast_graft_list_fuse(list, build); |
919 | return isl_ast_graft_list_from_ast_graft(graft); |
920 | } |
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 | { |
929 | isl_ctx *ctx; |
930 | isl_ast_graft_list *list; |
931 | |
932 | ctx = isl_ast_build_get_ctx(build); |
933 | |
934 | list = isl_ast_graft_list_alloc(ctx, 2); |
935 | list = isl_ast_graft_list_add(list, graft1); |
936 | list = isl_ast_graft_list_add(list, graft2); |
937 | |
938 | return ast_graft_list_fuse(list, build); |
939 | } |
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 | { |
946 | if (!graft) |
947 | goto error; |
948 | |
949 | graft->node = isl_ast_node_for_set_body(node, graft->node); |
950 | if (!graft->node) |
951 | return isl_ast_graft_free(graft); |
952 | |
953 | return graft; |
954 | error: |
955 | isl_ast_node_free(node); |
956 | isl_ast_graft_free(graft); |
957 | return NULL((void*)0); |
958 | } |
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 | { |
965 | if (!graft) |
966 | goto error; |
967 | |
968 | graft->node = isl_ast_node_alloc_mark(mark, graft->node); |
969 | if (!graft->node) |
970 | return isl_ast_graft_free(graft); |
971 | |
972 | return graft; |
973 | error: |
974 | isl_id_free(mark); |
975 | isl_ast_graft_free(graft); |
976 | return NULL((void*)0); |
977 | } |
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 | { |
987 | isl_ast_node_list *node_list; |
988 | |
989 | list = insert_pending_guard_nodes(list, build); |
990 | node_list = extract_node_list(list); |
991 | isl_ast_graft_list_free(list); |
992 | |
993 | return isl_ast_node_from_ast_node_list(node_list); |
994 | } |
995 | |
996 | __isl_null isl_ast_graft *isl_ast_graft_free(__isl_take isl_ast_graft *graft) |
997 | { |
998 | if (!graft) |
999 | return NULL((void*)0); |
1000 | |
1001 | if (--graft->ref > 0) |
1002 | return NULL((void*)0); |
1003 | |
1004 | isl_ast_node_free(graft->node); |
1005 | isl_set_free(graft->guard); |
1006 | isl_basic_set_free(graft->enforced); |
1007 | free(graft); |
1008 | |
1009 | return NULL((void*)0); |
1010 | } |
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 | { |
1018 | if (!graft || !enforced) |
1019 | goto error; |
1020 | |
1021 | enforced = isl_basic_set_align_params(enforced, |
1022 | isl_basic_set_get_space(graft->enforced)); |
1023 | graft->enforced = isl_basic_set_align_params(graft->enforced, |
1024 | isl_basic_set_get_space(enforced)); |
1025 | graft->enforced = isl_basic_set_intersect(graft->enforced, enforced); |
1026 | if (!graft->enforced) |
1027 | return isl_ast_graft_free(graft); |
1028 | |
1029 | return graft; |
1030 | error: |
1031 | isl_basic_set_free(enforced); |
1032 | return isl_ast_graft_free(graft); |
1033 | } |
1034 | |
1035 | __isl_give isl_basic_set *isl_ast_graft_get_enforced( |
1036 | __isl_keep isl_ast_graft *graft) |
1037 | { |
1038 | return graft ? isl_basic_set_copy(graft->enforced) : NULL((void*)0); |
1039 | } |
1040 | |
1041 | __isl_give isl_set *isl_ast_graft_get_guard(__isl_keep isl_ast_graft *graft) |
1042 | { |
1043 | return graft ? isl_set_copy(graft->guard) : NULL((void*)0); |
1044 | } |
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 | { |
1052 | return store_guard(graft, guard, build); |
1053 | } |
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 | { |
1072 | isl_basic_set *enforced; |
1073 | |
1074 | if (!graft) |
1075 | return NULL((void*)0); |
1076 | |
1077 | if (product) { |
1078 | enforced = graft->enforced; |
1079 | enforced = isl_basic_map_domain(isl_basic_set_unwrap(enforced)); |
1080 | graft->enforced = enforced; |
1081 | graft->guard = isl_map_domain(isl_set_unwrap(graft->guard)); |
1082 | } else { |
1083 | graft->enforced = isl_basic_set_params(graft->enforced); |
1084 | graft->guard = isl_set_params(graft->guard); |
1085 | } |
1086 | graft->guard = isl_set_compute_divs(graft->guard); |
1087 | |
1088 | if (!graft->enforced || !graft->guard) |
1089 | return isl_ast_graft_free(graft); |
1090 | |
1091 | return graft; |
1092 | } |
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 | { |
1101 | int i, n; |
1102 | |
1103 | n = isl_ast_graft_list_n_ast_graft(list); |
1104 | for (i = 0; i < n; ++i) { |
1105 | isl_ast_graft *graft; |
1106 | |
1107 | graft = isl_ast_graft_list_get_ast_graft(list, i); |
1108 | graft = isl_ast_graft_unembed(graft, product); |
1109 | list = isl_ast_graft_list_set_ast_graft(list, i, graft); |
1110 | } |
1111 | |
1112 | return list; |
1113 | } |
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 | { |
1121 | isl_basic_set *enforced; |
1122 | |
1123 | if (!graft) |
1124 | return NULL((void*)0); |
1125 | |
1126 | enforced = graft->enforced; |
1127 | graft->enforced = isl_basic_set_preimage_multi_aff(enforced, |
1128 | isl_multi_aff_copy(ma)); |
1129 | graft->guard = isl_set_preimage_multi_aff(graft->guard, ma); |
1130 | |
1131 | if (!graft->enforced || !graft->guard) |
1132 | return isl_ast_graft_free(graft); |
1133 | |
1134 | return graft; |
1135 | } |
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 | { |
1143 | int i, n; |
1144 | |
1145 | n = isl_ast_graft_list_n_ast_graft(list); |
1146 | for (i = 0; i < n; ++i) { |
1147 | isl_ast_graft *graft; |
1148 | |
1149 | graft = isl_ast_graft_list_get_ast_graft(list, i); |
1150 | graft = isl_ast_graft_preimage_multi_aff(graft, |
1151 | isl_multi_aff_copy(ma)); |
1152 | list = isl_ast_graft_list_set_ast_graft(list, i, graft); |
1153 | } |
1154 | |
1155 | isl_multi_aff_free(ma); |
1156 | return list; |
1157 | } |
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 | { |
1164 | return isl_set_plain_cmp(a->guard, b->guard); |
1165 | } |
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 | { |
1172 | return isl_ast_graft_list_sort(list, &cmp_graft, NULL((void*)0)); |
1173 | } |
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 | { |
1202 | int i, j, first; |
1203 | |
1204 | if (!list1 || !list2 || !build) |
1205 | goto error; |
1206 | if (list2->n == 0) { |
1207 | isl_ast_graft_list_free(list2); |
1208 | return list1; |
1209 | } |
1210 | if (list1->n == 0) { |
1211 | isl_ast_graft_list_free(list1); |
1212 | return list2; |
1213 | } |
1214 | |
1215 | first = 0; |
1216 | for (i = 0; i < list2->n; ++i) { |
1217 | isl_ast_graft *graft; |
1218 | graft = isl_ast_graft_list_get_ast_graft(list2, i); |
1219 | if (!graft) |
1220 | break; |
1221 | |
1222 | for (j = list1->n; j >= 0; --j) { |
1223 | int cmp, disjoint; |
1224 | isl_ast_graft *graft_j; |
1225 | |
1226 | if (j == first) |
1227 | cmp = -1; |
1228 | else |
1229 | cmp = isl_set_plain_cmp(list1->p[j - 1]->guard, |
1230 | graft->guard); |
1231 | if (cmp > 0) { |
1232 | disjoint = isl_set_is_disjoint(graft->guard, |
1233 | list1->p[j - 1]->guard); |
1234 | if (disjoint < 0) { |
1235 | isl_ast_graft_free(graft); |
1236 | list1 = isl_ast_graft_list_free(list1); |
1237 | break; |
1238 | } |
1239 | if (!disjoint) |
1240 | cmp = -1; |
1241 | } |
1242 | if (cmp > 0) |
1243 | continue; |
1244 | if (cmp < 0) { |
1245 | list1 = isl_ast_graft_list_insert(list1, j, |
1246 | graft); |
1247 | break; |
1248 | } |
1249 | |
1250 | --j; |
1251 | |
1252 | graft_j = isl_ast_graft_list_get_ast_graft(list1, j); |
1253 | graft_j = isl_ast_graft_fuse(graft_j, graft, build); |
1254 | list1 = isl_ast_graft_list_set_ast_graft(list1, j, |
1255 | graft_j); |
1256 | break; |
1257 | } |
1258 | |
1259 | if (j < 0) { |
1260 | isl_ast_graft_free(graft); |
1261 | isl_die(isl_ast_build_get_ctx(build),do { isl_handle_error(isl_ast_build_get_ctx(build), isl_error_internal , "element failed to get inserted", "/build/llvm-toolchain-snapshot-10~+20200102111109+a2976c490da/polly/lib/External/isl/isl_ast_graft.c" , 1263); break; } while (0) |
1262 | isl_error_internal,do { isl_handle_error(isl_ast_build_get_ctx(build), isl_error_internal , "element failed to get inserted", "/build/llvm-toolchain-snapshot-10~+20200102111109+a2976c490da/polly/lib/External/isl/isl_ast_graft.c" , 1263); break; } while (0) |
1263 | "element failed to get inserted", break)do { isl_handle_error(isl_ast_build_get_ctx(build), isl_error_internal , "element failed to get inserted", "/build/llvm-toolchain-snapshot-10~+20200102111109+a2976c490da/polly/lib/External/isl/isl_ast_graft.c" , 1263); break; } while (0); |
1264 | } |
1265 | |
1266 | first = j + 1; |
1267 | if (!list1) |
1268 | break; |
1269 | } |
1270 | if (i < list2->n) |
1271 | list1 = isl_ast_graft_list_free(list1); |
1272 | isl_ast_graft_list_free(list2); |
1273 | |
1274 | return list1; |
1275 | error: |
1276 | isl_ast_graft_list_free(list1); |
1277 | isl_ast_graft_list_free(list2); |
1278 | return NULL((void*)0); |
1279 | } |
1280 | |
1281 | __isl_give isl_printer *isl_printer_print_ast_graft(__isl_take isl_printer *p, |
1282 | __isl_keep isl_ast_graft *graft) |
1283 | { |
1284 | if (!p) |
1285 | return NULL((void*)0); |
1286 | if (!graft) |
1287 | return isl_printer_free(p); |
1288 | |
1289 | p = isl_printer_print_str(p, "("); |
1290 | p = isl_printer_print_str(p, "guard: "); |
1291 | p = isl_printer_print_set(p, graft->guard); |
1292 | p = isl_printer_print_str(p, ", "); |
1293 | p = isl_printer_print_str(p, "enforced: "); |
1294 | p = isl_printer_print_basic_set(p, graft->enforced); |
1295 | p = isl_printer_print_str(p, ", "); |
1296 | p = isl_printer_print_str(p, "node: "); |
1297 | p = isl_printer_print_ast_node(p, graft->node); |
1298 | p = isl_printer_print_str(p, ")"); |
1299 | |
1300 | return p; |
1301 | } |