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