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