File: | tools/polly/lib/External/isl/isl_union_map.c |
Warning: | line 1106, column 10 Use of memory after it is freed |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | /* | |||
2 | * Copyright 2010-2011 INRIA Saclay | |||
3 | * Copyright 2013-2014 Ecole Normale Superieure | |||
4 | * Copyright 2014 INRIA Rocquencourt | |||
5 | * Copyright 2016-2017 Sven Verdoolaege | |||
6 | * | |||
7 | * Use of this software is governed by the MIT license | |||
8 | * | |||
9 | * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France, | |||
10 | * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod, | |||
11 | * 91893 Orsay, France | |||
12 | * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt, | |||
13 | * B.P. 105 - 78153 Le Chesnay, France | |||
14 | */ | |||
15 | ||||
16 | #include <isl_map_private.h> | |||
17 | #include <isl_union_map_private.h> | |||
18 | #include <isl/ctx.h> | |||
19 | #include <isl/hash.h> | |||
20 | #include <isl_aff_private.h> | |||
21 | #include <isl/map.h> | |||
22 | #include <isl/set.h> | |||
23 | #include <isl_space_private.h> | |||
24 | #include <isl/union_set.h> | |||
25 | #include <isl_maybe_map.h> | |||
26 | ||||
27 | #include <bset_from_bmap.c> | |||
28 | #include <set_to_map.c> | |||
29 | #include <set_from_map.c> | |||
30 | #include <uset_to_umap.c> | |||
31 | #include <uset_from_umap.c> | |||
32 | #include <set_list_from_map_list_inl.c> | |||
33 | ||||
34 | /* Return the number of parameters of "umap", where "type" | |||
35 | * is required to be set to isl_dim_param. | |||
36 | */ | |||
37 | unsigned isl_union_map_dim(__isl_keep isl_union_map *umap, | |||
38 | enum isl_dim_type type) | |||
39 | { | |||
40 | if (!umap) | |||
41 | return 0; | |||
42 | ||||
43 | if (type != isl_dim_param) | |||
44 | isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,do { isl_handle_error(isl_union_map_get_ctx(umap), isl_error_invalid , "can only reference parameters", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_union_map.c" , 45); return 0; } while (0) | |||
45 | "can only reference parameters", return 0)do { isl_handle_error(isl_union_map_get_ctx(umap), isl_error_invalid , "can only reference parameters", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_union_map.c" , 45); return 0; } while (0); | |||
46 | ||||
47 | return isl_space_dim(umap->dim, type); | |||
48 | } | |||
49 | ||||
50 | /* Return the number of parameters of "uset", where "type" | |||
51 | * is required to be set to isl_dim_param. | |||
52 | */ | |||
53 | unsigned isl_union_set_dim(__isl_keep isl_union_setisl_union_map *uset, | |||
54 | enum isl_dim_type type) | |||
55 | { | |||
56 | return isl_union_map_dim(uset, type); | |||
57 | } | |||
58 | ||||
59 | /* Return the id of the specified dimension. | |||
60 | */ | |||
61 | __isl_give isl_id *isl_union_map_get_dim_id(__isl_keep isl_union_map *umap, | |||
62 | enum isl_dim_type type, unsigned pos) | |||
63 | { | |||
64 | if (!umap) | |||
65 | return NULL((void*)0); | |||
66 | ||||
67 | if (type != isl_dim_param) | |||
68 | isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,do { isl_handle_error(isl_union_map_get_ctx(umap), isl_error_invalid , "can only reference parameters", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_union_map.c" , 69); return ((void*)0); } while (0) | |||
69 | "can only reference parameters", return NULL)do { isl_handle_error(isl_union_map_get_ctx(umap), isl_error_invalid , "can only reference parameters", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_union_map.c" , 69); return ((void*)0); } while (0); | |||
70 | ||||
71 | return isl_space_get_dim_id(umap->dim, type, pos); | |||
72 | } | |||
73 | ||||
74 | /* Is this union set a parameter domain? | |||
75 | */ | |||
76 | isl_bool isl_union_set_is_params(__isl_keep isl_union_setisl_union_map *uset) | |||
77 | { | |||
78 | isl_setisl_map *set; | |||
79 | isl_bool params; | |||
80 | ||||
81 | if (!uset) | |||
82 | return isl_bool_error; | |||
83 | if (uset->table.n != 1) | |||
84 | return isl_bool_false; | |||
85 | ||||
86 | set = isl_set_from_union_set(isl_union_set_copy(uset)); | |||
87 | params = isl_set_is_params(set); | |||
88 | isl_set_free(set); | |||
89 | return params; | |||
90 | } | |||
91 | ||||
92 | /* Is this union map actually a parameter domain? | |||
93 | * Users should never call this function. Outside of isl, | |||
94 | * a union map can never be a parameter domain. | |||
95 | */ | |||
96 | isl_bool isl_union_map_is_params(__isl_keep isl_union_map *umap) | |||
97 | { | |||
98 | return isl_union_set_is_params(uset_from_umap(umap)); | |||
99 | } | |||
100 | ||||
101 | static __isl_give isl_union_map *isl_union_map_alloc( | |||
102 | __isl_take isl_space *space, int size) | |||
103 | { | |||
104 | isl_union_map *umap; | |||
105 | ||||
106 | space = isl_space_params(space); | |||
107 | if (!space) | |||
108 | return NULL((void*)0); | |||
109 | ||||
110 | umap = isl_calloc_type(space->ctx, isl_union_map)((isl_union_map *)isl_calloc_or_die(space->ctx, 1, sizeof( isl_union_map))); | |||
111 | if (!umap) { | |||
112 | isl_space_free(space); | |||
113 | return NULL((void*)0); | |||
114 | } | |||
115 | ||||
116 | umap->ref = 1; | |||
117 | umap->dim = space; | |||
118 | if (isl_hash_table_init(space->ctx, &umap->table, size) < 0) | |||
119 | return isl_union_map_free(umap); | |||
120 | ||||
121 | return umap; | |||
122 | } | |||
123 | ||||
124 | __isl_give isl_union_map *isl_union_map_empty(__isl_take isl_space *space) | |||
125 | { | |||
126 | return isl_union_map_alloc(space, 16); | |||
127 | } | |||
128 | ||||
129 | __isl_give isl_union_setisl_union_map *isl_union_set_empty(__isl_take isl_space *space) | |||
130 | { | |||
131 | return isl_union_map_empty(space); | |||
132 | } | |||
133 | ||||
134 | isl_ctx *isl_union_map_get_ctx(__isl_keep isl_union_map *umap) | |||
135 | { | |||
136 | return umap ? umap->dim->ctx : NULL((void*)0); | |||
137 | } | |||
138 | ||||
139 | isl_ctx *isl_union_set_get_ctx(__isl_keep isl_union_setisl_union_map *uset) | |||
140 | { | |||
141 | return uset ? uset->dim->ctx : NULL((void*)0); | |||
142 | } | |||
143 | ||||
144 | /* Return the space of "umap". | |||
145 | */ | |||
146 | __isl_keep isl_space *isl_union_map_peek_space(__isl_keep isl_union_map *umap) | |||
147 | { | |||
148 | return umap ? umap->dim : NULL((void*)0); | |||
149 | } | |||
150 | ||||
151 | __isl_give isl_space *isl_union_map_get_space(__isl_keep isl_union_map *umap) | |||
152 | { | |||
153 | return isl_space_copy(isl_union_map_peek_space(umap)); | |||
154 | } | |||
155 | ||||
156 | /* Return the position of the parameter with the given name | |||
157 | * in "umap". | |||
158 | * Return -1 if no such dimension can be found. | |||
159 | */ | |||
160 | int isl_union_map_find_dim_by_name(__isl_keep isl_union_map *umap, | |||
161 | enum isl_dim_type type, const char *name) | |||
162 | { | |||
163 | if (!umap) | |||
164 | return -1; | |||
165 | return isl_space_find_dim_by_name(umap->dim, type, name); | |||
166 | } | |||
167 | ||||
168 | __isl_give isl_space *isl_union_set_get_space(__isl_keep isl_union_setisl_union_map *uset) | |||
169 | { | |||
170 | return isl_union_map_get_space(uset); | |||
171 | } | |||
172 | ||||
173 | static isl_stat free_umap_entry(void **entry, void *user) | |||
174 | { | |||
175 | isl_map *map = *entry; | |||
176 | isl_map_free(map); | |||
177 | return isl_stat_ok; | |||
178 | } | |||
179 | ||||
180 | static isl_stat add_map(__isl_take isl_map *map, void *user) | |||
181 | { | |||
182 | isl_union_map **umap = (isl_union_map **)user; | |||
183 | ||||
184 | *umap = isl_union_map_add_map(*umap, map); | |||
185 | ||||
186 | return isl_stat_ok; | |||
187 | } | |||
188 | ||||
189 | __isl_give isl_union_map *isl_union_map_dup(__isl_keep isl_union_map *umap) | |||
190 | { | |||
191 | isl_union_map *dup; | |||
192 | ||||
193 | if (!umap) | |||
194 | return NULL((void*)0); | |||
195 | ||||
196 | dup = isl_union_map_empty(isl_space_copy(umap->dim)); | |||
197 | if (isl_union_map_foreach_map(umap, &add_map, &dup) < 0) | |||
198 | goto error; | |||
199 | return dup; | |||
200 | error: | |||
201 | isl_union_map_free(dup); | |||
202 | return NULL((void*)0); | |||
203 | } | |||
204 | ||||
205 | __isl_give isl_union_map *isl_union_map_cow(__isl_take isl_union_map *umap) | |||
206 | { | |||
207 | if (!umap) | |||
208 | return NULL((void*)0); | |||
209 | ||||
210 | if (umap->ref == 1) | |||
211 | return umap; | |||
212 | umap->ref--; | |||
213 | return isl_union_map_dup(umap); | |||
214 | } | |||
215 | ||||
216 | struct isl_union_align { | |||
217 | isl_reordering *exp; | |||
218 | isl_union_map *res; | |||
219 | }; | |||
220 | ||||
221 | static isl_stat align_entry(void **entry, void *user) | |||
222 | { | |||
223 | isl_map *map = *entry; | |||
224 | isl_reordering *exp; | |||
225 | struct isl_union_align *data = user; | |||
226 | ||||
227 | exp = isl_reordering_extend_space(isl_reordering_copy(data->exp), | |||
228 | isl_map_get_space(map)); | |||
229 | ||||
230 | data->res = isl_union_map_add_map(data->res, | |||
231 | isl_map_realign(isl_map_copy(map), exp)); | |||
232 | ||||
233 | return isl_stat_ok; | |||
234 | } | |||
235 | ||||
236 | /* Align the parameters of umap along those of model. | |||
237 | * The result has the parameters of model first, in the same order | |||
238 | * as they appear in model, followed by any remaining parameters of | |||
239 | * umap that do not appear in model. | |||
240 | */ | |||
241 | __isl_give isl_union_map *isl_union_map_align_params( | |||
242 | __isl_take isl_union_map *umap, __isl_take isl_space *model) | |||
243 | { | |||
244 | struct isl_union_align data = { NULL((void*)0), NULL((void*)0) }; | |||
245 | isl_bool equal_params; | |||
246 | ||||
247 | if (!umap || !model) | |||
248 | goto error; | |||
249 | ||||
250 | equal_params = isl_space_has_equal_params(umap->dim, model); | |||
251 | if (equal_params < 0) | |||
252 | goto error; | |||
253 | if (equal_params) { | |||
254 | isl_space_free(model); | |||
255 | return umap; | |||
256 | } | |||
257 | ||||
258 | data.exp = isl_parameter_alignment_reordering(umap->dim, model); | |||
259 | if (!data.exp) | |||
260 | goto error; | |||
261 | ||||
262 | data.res = isl_union_map_alloc(isl_reordering_get_space(data.exp), | |||
263 | umap->table.n); | |||
264 | if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, | |||
265 | &align_entry, &data) < 0) | |||
266 | goto error; | |||
267 | ||||
268 | isl_reordering_free(data.exp); | |||
269 | isl_union_map_free(umap); | |||
270 | isl_space_free(model); | |||
271 | return data.res; | |||
272 | error: | |||
273 | isl_reordering_free(data.exp); | |||
274 | isl_union_map_free(umap); | |||
275 | isl_union_map_free(data.res); | |||
276 | isl_space_free(model); | |||
277 | return NULL((void*)0); | |||
278 | } | |||
279 | ||||
280 | __isl_give isl_union_setisl_union_map *isl_union_set_align_params( | |||
281 | __isl_take isl_union_setisl_union_map *uset, __isl_take isl_space *model) | |||
282 | { | |||
283 | return isl_union_map_align_params(uset, model); | |||
284 | } | |||
285 | ||||
286 | __isl_give isl_union_map *isl_union_map_union(__isl_take isl_union_map *umap1, | |||
287 | __isl_take isl_union_map *umap2) | |||
288 | { | |||
289 | umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2)); | |||
290 | umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1)); | |||
291 | ||||
292 | umap1 = isl_union_map_cow(umap1); | |||
293 | ||||
294 | if (!umap1 || !umap2) | |||
295 | goto error; | |||
296 | ||||
297 | if (isl_union_map_foreach_map(umap2, &add_map, &umap1) < 0) | |||
298 | goto error; | |||
299 | ||||
300 | isl_union_map_free(umap2); | |||
301 | ||||
302 | return umap1; | |||
303 | error: | |||
304 | isl_union_map_free(umap1); | |||
305 | isl_union_map_free(umap2); | |||
306 | return NULL((void*)0); | |||
307 | } | |||
308 | ||||
309 | __isl_give isl_union_setisl_union_map *isl_union_set_union(__isl_take isl_union_setisl_union_map *uset1, | |||
310 | __isl_take isl_union_setisl_union_map *uset2) | |||
311 | { | |||
312 | return isl_union_map_union(uset1, uset2); | |||
313 | } | |||
314 | ||||
315 | __isl_give isl_union_map *isl_union_map_copy(__isl_keep isl_union_map *umap) | |||
316 | { | |||
317 | if (!umap) | |||
318 | return NULL((void*)0); | |||
319 | ||||
320 | umap->ref++; | |||
321 | return umap; | |||
322 | } | |||
323 | ||||
324 | __isl_give isl_union_setisl_union_map *isl_union_set_copy(__isl_keep isl_union_setisl_union_map *uset) | |||
325 | { | |||
326 | return isl_union_map_copy(uset); | |||
327 | } | |||
328 | ||||
329 | __isl_null isl_union_map *isl_union_map_free(__isl_take isl_union_map *umap) | |||
330 | { | |||
331 | if (!umap) | |||
332 | return NULL((void*)0); | |||
333 | ||||
334 | if (--umap->ref > 0) | |||
335 | return NULL((void*)0); | |||
336 | ||||
337 | isl_hash_table_foreach(umap->dim->ctx, &umap->table, | |||
338 | &free_umap_entry, NULL((void*)0)); | |||
339 | isl_hash_table_clear(&umap->table); | |||
340 | isl_space_free(umap->dim); | |||
341 | free(umap); | |||
342 | return NULL((void*)0); | |||
343 | } | |||
344 | ||||
345 | __isl_null isl_union_setisl_union_map *isl_union_set_free(__isl_take isl_union_setisl_union_map *uset) | |||
346 | { | |||
347 | return isl_union_map_free(uset); | |||
348 | } | |||
349 | ||||
350 | /* Do "umap" and "space" have the same parameters? | |||
351 | */ | |||
352 | isl_bool isl_union_map_space_has_equal_params(__isl_keep isl_union_map *umap, | |||
353 | __isl_keep isl_space *space) | |||
354 | { | |||
355 | isl_space *umap_space; | |||
356 | ||||
357 | umap_space = isl_union_map_peek_space(umap); | |||
358 | return isl_space_has_equal_params(umap_space, space); | |||
359 | } | |||
360 | ||||
361 | /* Do "uset" and "space" have the same parameters? | |||
362 | */ | |||
363 | isl_bool isl_union_set_space_has_equal_params(__isl_keep isl_union_setisl_union_map *uset, | |||
364 | __isl_keep isl_space *space) | |||
365 | { | |||
366 | return isl_union_map_space_has_equal_params(uset_to_umap(uset), space); | |||
367 | } | |||
368 | ||||
369 | static int has_space(const void *entry, const void *val) | |||
370 | { | |||
371 | isl_map *map = (isl_map *)entry; | |||
372 | isl_space *space = (isl_space *) val; | |||
373 | ||||
374 | return isl_space_is_equal(map->dim, space); | |||
375 | } | |||
376 | ||||
377 | __isl_give isl_union_map *isl_union_map_add_map(__isl_take isl_union_map *umap, | |||
378 | __isl_take isl_map *map) | |||
379 | { | |||
380 | uint32_t hash; | |||
381 | struct isl_hash_table_entry *entry; | |||
382 | isl_bool aligned; | |||
383 | ||||
384 | if (!map || !umap) | |||
385 | goto error; | |||
386 | ||||
387 | if (isl_map_plain_is_empty(map)) { | |||
388 | isl_map_free(map); | |||
389 | return umap; | |||
390 | } | |||
391 | ||||
392 | aligned = isl_map_space_has_equal_params(map, umap->dim); | |||
393 | if (aligned < 0) | |||
394 | goto error; | |||
395 | if (!aligned) { | |||
396 | umap = isl_union_map_align_params(umap, isl_map_get_space(map)); | |||
397 | map = isl_map_align_params(map, isl_union_map_get_space(umap)); | |||
398 | } | |||
399 | ||||
400 | umap = isl_union_map_cow(umap); | |||
401 | ||||
402 | if (!map || !umap) | |||
403 | goto error; | |||
404 | ||||
405 | hash = isl_space_get_hash(map->dim); | |||
406 | entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash, | |||
407 | &has_space, map->dim, 1); | |||
408 | if (!entry) | |||
409 | goto error; | |||
410 | ||||
411 | if (!entry->data) | |||
412 | entry->data = map; | |||
413 | else { | |||
414 | entry->data = isl_map_union(entry->data, isl_map_copy(map)); | |||
415 | if (!entry->data) | |||
416 | goto error; | |||
417 | isl_map_free(map); | |||
418 | } | |||
419 | ||||
420 | return umap; | |||
421 | error: | |||
422 | isl_map_free(map); | |||
423 | isl_union_map_free(umap); | |||
424 | return NULL((void*)0); | |||
425 | } | |||
426 | ||||
427 | __isl_give isl_union_setisl_union_map *isl_union_set_add_set(__isl_take isl_union_setisl_union_map *uset, | |||
428 | __isl_take isl_setisl_map *set) | |||
429 | { | |||
430 | return isl_union_map_add_map(uset, set_to_map(set)); | |||
431 | } | |||
432 | ||||
433 | __isl_give isl_union_map *isl_union_map_from_map(__isl_take isl_map *map) | |||
434 | { | |||
435 | isl_space *dim; | |||
436 | isl_union_map *umap; | |||
437 | ||||
438 | if (!map) | |||
439 | return NULL((void*)0); | |||
440 | ||||
441 | dim = isl_map_get_space(map); | |||
442 | dim = isl_space_params(dim); | |||
443 | umap = isl_union_map_empty(dim); | |||
444 | umap = isl_union_map_add_map(umap, map); | |||
445 | ||||
446 | return umap; | |||
447 | } | |||
448 | ||||
449 | __isl_give isl_union_setisl_union_map *isl_union_set_from_set(__isl_take isl_setisl_map *set) | |||
450 | { | |||
451 | return isl_union_map_from_map(set_to_map(set)); | |||
452 | } | |||
453 | ||||
454 | __isl_give isl_union_map *isl_union_map_from_basic_map( | |||
455 | __isl_take isl_basic_map *bmap) | |||
456 | { | |||
457 | return isl_union_map_from_map(isl_map_from_basic_map(bmap)); | |||
458 | } | |||
459 | ||||
460 | __isl_give isl_union_setisl_union_map *isl_union_set_from_basic_set( | |||
461 | __isl_take isl_basic_setisl_basic_map *bset) | |||
462 | { | |||
463 | return isl_union_map_from_basic_map(bset); | |||
464 | } | |||
465 | ||||
466 | struct isl_union_map_foreach_data | |||
467 | { | |||
468 | isl_stat (*fn)(__isl_take isl_map *map, void *user); | |||
469 | void *user; | |||
470 | }; | |||
471 | ||||
472 | static isl_stat call_on_copy(void **entry, void *user) | |||
473 | { | |||
474 | isl_map *map = *entry; | |||
475 | struct isl_union_map_foreach_data *data; | |||
476 | data = (struct isl_union_map_foreach_data *)user; | |||
477 | ||||
478 | return data->fn(isl_map_copy(map), data->user); | |||
479 | } | |||
480 | ||||
481 | int isl_union_map_n_map(__isl_keep isl_union_map *umap) | |||
482 | { | |||
483 | return umap ? umap->table.n : 0; | |||
484 | } | |||
485 | ||||
486 | int isl_union_set_n_set(__isl_keep isl_union_setisl_union_map *uset) | |||
487 | { | |||
488 | return uset ? uset->table.n : 0; | |||
489 | } | |||
490 | ||||
491 | isl_stat isl_union_map_foreach_map(__isl_keep isl_union_map *umap, | |||
492 | isl_stat (*fn)(__isl_take isl_map *map, void *user), void *user) | |||
493 | { | |||
494 | struct isl_union_map_foreach_data data = { fn, user }; | |||
495 | ||||
496 | if (!umap) | |||
497 | return isl_stat_error; | |||
498 | ||||
499 | return isl_hash_table_foreach(umap->dim->ctx, &umap->table, | |||
500 | &call_on_copy, &data); | |||
501 | } | |||
502 | ||||
503 | /* Internal data structure for isl_union_map_every_map. | |||
504 | * | |||
505 | * "test" is the user-specified callback function. | |||
506 | * "user" is the user-specified callback function argument. | |||
507 | * | |||
508 | * "failed" is initialized to 0 and set to 1 if "test" fails | |||
509 | * on any map. | |||
510 | */ | |||
511 | struct isl_union_map_every_data { | |||
512 | isl_bool (*test)(__isl_keep isl_map *map, void *user); | |||
513 | void *user; | |||
514 | int failed; | |||
515 | }; | |||
516 | ||||
517 | /* Call data->test on "map". | |||
518 | * If this fails, then set data->failed and abort. | |||
519 | */ | |||
520 | static isl_stat call_every(void **entry, void *user) | |||
521 | { | |||
522 | isl_map *map = *entry; | |||
523 | struct isl_union_map_every_data *data = user; | |||
524 | isl_bool r; | |||
525 | ||||
526 | r = data->test(map, data->user); | |||
527 | if (r < 0) | |||
528 | return isl_stat_error; | |||
529 | if (r) | |||
530 | return isl_stat_ok; | |||
531 | data->failed = 1; | |||
532 | return isl_stat_error; | |||
533 | } | |||
534 | ||||
535 | /* Does "test" succeed on every map in "umap"? | |||
536 | */ | |||
537 | isl_bool isl_union_map_every_map(__isl_keep isl_union_map *umap, | |||
538 | isl_bool (*test)(__isl_keep isl_map *map, void *user), void *user) | |||
539 | { | |||
540 | struct isl_union_map_every_data data = { test, user, 0 }; | |||
541 | isl_stat r; | |||
542 | ||||
543 | if (!umap) | |||
544 | return isl_bool_error; | |||
545 | ||||
546 | r = isl_hash_table_foreach(isl_union_map_get_ctx(umap), &umap->table, | |||
547 | &call_every, &data); | |||
548 | if (r >= 0) | |||
549 | return isl_bool_true; | |||
550 | if (data.failed) | |||
551 | return isl_bool_false; | |||
552 | return isl_bool_error; | |||
553 | } | |||
554 | ||||
555 | /* Add "map" to "list". | |||
556 | */ | |||
557 | static isl_stat add_list_map(__isl_take isl_map *map, void *user) | |||
558 | { | |||
559 | isl_map_list **list = user; | |||
560 | ||||
561 | *list = isl_map_list_add(*list, map); | |||
562 | ||||
563 | if (!*list) | |||
564 | return isl_stat_error; | |||
565 | return isl_stat_ok; | |||
566 | } | |||
567 | ||||
568 | /* Return the maps in "umap" as a list. | |||
569 | * | |||
570 | * First construct a list of the appropriate size and then add all the | |||
571 | * elements. | |||
572 | */ | |||
573 | __isl_give isl_map_list *isl_union_map_get_map_list( | |||
574 | __isl_keep isl_union_map *umap) | |||
575 | { | |||
576 | int n_maps; | |||
577 | isl_ctx *ctx; | |||
578 | isl_map_list *list; | |||
579 | ||||
580 | if (!umap) | |||
581 | return NULL((void*)0); | |||
582 | ctx = isl_union_map_get_ctx(umap); | |||
583 | n_maps = isl_union_map_n_map(umap); | |||
584 | list = isl_map_list_alloc(ctx, n_maps); | |||
585 | ||||
586 | if (isl_union_map_foreach_map(umap, &add_list_map, &list) < 0) | |||
587 | list = isl_map_list_free(list); | |||
588 | ||||
589 | return list; | |||
590 | } | |||
591 | ||||
592 | /* Return the sets in "uset" as a list. | |||
593 | */ | |||
594 | __isl_give isl_set_listisl_map_list *isl_union_set_get_set_list( | |||
595 | __isl_keep isl_union_setisl_union_map *uset) | |||
596 | { | |||
597 | return set_list_from_map_list( | |||
598 | isl_union_map_get_map_list(uset_to_umap(uset))); | |||
599 | } | |||
600 | ||||
601 | static isl_stat copy_map(void **entry, void *user) | |||
602 | { | |||
603 | isl_map *map = *entry; | |||
604 | isl_map **map_p = user; | |||
605 | ||||
606 | *map_p = isl_map_copy(map); | |||
607 | ||||
608 | return isl_stat_error; | |||
609 | } | |||
610 | ||||
611 | __isl_give isl_map *isl_map_from_union_map(__isl_take isl_union_map *umap) | |||
612 | { | |||
613 | isl_ctx *ctx; | |||
614 | isl_map *map = NULL((void*)0); | |||
615 | ||||
616 | if (!umap) | |||
617 | return NULL((void*)0); | |||
618 | ctx = isl_union_map_get_ctx(umap); | |||
619 | if (umap->table.n != 1) | |||
620 | isl_die(ctx, isl_error_invalid,do { isl_handle_error(ctx, isl_error_invalid, "union map needs to contain elements in exactly " "one space", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_union_map.c" , 622); goto error; } while (0) | |||
621 | "union map needs to contain elements in exactly "do { isl_handle_error(ctx, isl_error_invalid, "union map needs to contain elements in exactly " "one space", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_union_map.c" , 622); goto error; } while (0) | |||
622 | "one space", goto error)do { isl_handle_error(ctx, isl_error_invalid, "union map needs to contain elements in exactly " "one space", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_union_map.c" , 622); goto error; } while (0); | |||
623 | ||||
624 | isl_hash_table_foreach(ctx, &umap->table, ©_map, &map); | |||
625 | ||||
626 | isl_union_map_free(umap); | |||
627 | ||||
628 | return map; | |||
629 | error: | |||
630 | isl_union_map_free(umap); | |||
631 | return NULL((void*)0); | |||
632 | } | |||
633 | ||||
634 | __isl_give isl_setisl_map *isl_set_from_union_set(__isl_take isl_union_setisl_union_map *uset) | |||
635 | { | |||
636 | return isl_map_from_union_map(uset); | |||
637 | } | |||
638 | ||||
639 | /* Extract the map in "umap" that lives in the given space (ignoring | |||
640 | * parameters). | |||
641 | */ | |||
642 | __isl_give isl_map *isl_union_map_extract_map(__isl_keep isl_union_map *umap, | |||
643 | __isl_take isl_space *space) | |||
644 | { | |||
645 | uint32_t hash; | |||
646 | struct isl_hash_table_entry *entry; | |||
647 | ||||
648 | space = isl_space_drop_dims(space, isl_dim_param, | |||
649 | 0, isl_space_dim(space, isl_dim_param)); | |||
650 | space = isl_space_align_params(space, isl_union_map_get_space(umap)); | |||
651 | if (!umap || !space) | |||
652 | goto error; | |||
653 | ||||
654 | hash = isl_space_get_hash(space); | |||
655 | entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash, | |||
656 | &has_space, space, 0); | |||
657 | if (!entry) | |||
658 | return isl_map_empty(space); | |||
659 | isl_space_free(space); | |||
660 | return isl_map_copy(entry->data); | |||
661 | error: | |||
662 | isl_space_free(space); | |||
663 | return NULL((void*)0); | |||
664 | } | |||
665 | ||||
666 | __isl_give isl_setisl_map *isl_union_set_extract_set(__isl_keep isl_union_setisl_union_map *uset, | |||
667 | __isl_take isl_space *dim) | |||
668 | { | |||
669 | return set_from_map(isl_union_map_extract_map(uset, dim)); | |||
670 | } | |||
671 | ||||
672 | /* Check if umap contains a map in the given space. | |||
673 | */ | |||
674 | isl_bool isl_union_map_contains(__isl_keep isl_union_map *umap, | |||
675 | __isl_keep isl_space *space) | |||
676 | { | |||
677 | uint32_t hash; | |||
678 | struct isl_hash_table_entry *entry; | |||
679 | ||||
680 | if (!umap || !space) | |||
681 | return isl_bool_error; | |||
682 | ||||
683 | hash = isl_space_get_hash(space); | |||
684 | entry = isl_hash_table_find(umap->dim->ctx, &umap->table, hash, | |||
685 | &has_space, space, 0); | |||
686 | return !!entry; | |||
687 | } | |||
688 | ||||
689 | isl_bool isl_union_set_contains(__isl_keep isl_union_setisl_union_map *uset, | |||
690 | __isl_keep isl_space *space) | |||
691 | { | |||
692 | return isl_union_map_contains(uset, space); | |||
693 | } | |||
694 | ||||
695 | isl_stat isl_union_set_foreach_set(__isl_keep isl_union_setisl_union_map *uset, | |||
696 | isl_stat (*fn)(__isl_take isl_setisl_map *set, void *user), void *user) | |||
697 | { | |||
698 | return isl_union_map_foreach_map(uset, | |||
699 | (isl_stat(*)(__isl_take isl_map *, void*))fn, user); | |||
700 | } | |||
701 | ||||
702 | struct isl_union_set_foreach_point_data { | |||
703 | isl_stat (*fn)(__isl_take isl_point *pnt, void *user); | |||
704 | void *user; | |||
705 | }; | |||
706 | ||||
707 | static isl_stat foreach_point(__isl_take isl_setisl_map *set, void *user) | |||
708 | { | |||
709 | struct isl_union_set_foreach_point_data *data = user; | |||
710 | isl_stat r; | |||
711 | ||||
712 | r = isl_set_foreach_point(set, data->fn, data->user); | |||
713 | isl_set_free(set); | |||
714 | ||||
715 | return r; | |||
716 | } | |||
717 | ||||
718 | isl_stat isl_union_set_foreach_point(__isl_keep isl_union_setisl_union_map *uset, | |||
719 | isl_stat (*fn)(__isl_take isl_point *pnt, void *user), void *user) | |||
720 | { | |||
721 | struct isl_union_set_foreach_point_data data = { fn, user }; | |||
722 | return isl_union_set_foreach_set(uset, &foreach_point, &data); | |||
723 | } | |||
724 | ||||
725 | /* Data structure that specifies how gen_bin_op should | |||
726 | * construct results from the inputs. | |||
727 | * | |||
728 | * If "subtract" is set, then a map in the first input is copied to the result | |||
729 | * if there is no corresponding map in the second input. | |||
730 | * Otherwise, a map in the first input with no corresponding map | |||
731 | * in the second input is ignored. | |||
732 | * If "filter" is not NULL, then it specifies which maps in the first | |||
733 | * input may have a matching map in the second input. | |||
734 | * In particular, it makes sure that "match_space" can be called | |||
735 | * on the space of the map. | |||
736 | * "match_space" specifies how to transform the space of a map | |||
737 | * in the first input to the space of the corresponding map | |||
738 | * in the second input. | |||
739 | * "fn_map" specifies how the matching maps, one from each input, | |||
740 | * should be combined to form a map in the result. | |||
741 | */ | |||
742 | struct isl_bin_op_control { | |||
743 | int subtract; | |||
744 | isl_bool (*filter)(__isl_keep isl_map *map); | |||
745 | __isl_give isl_space *(*match_space)(__isl_take isl_space *space); | |||
746 | __isl_give isl_map *(*fn_map)(__isl_take isl_map *map1, | |||
747 | __isl_take isl_map *map2); | |||
748 | }; | |||
749 | ||||
750 | /* Internal data structure for gen_bin_op. | |||
751 | * "control" specifies how the maps in the result should be constructed. | |||
752 | * "umap2" is a pointer to the second argument. | |||
753 | * "res" collects the results. | |||
754 | */ | |||
755 | struct isl_union_map_gen_bin_data { | |||
756 | struct isl_bin_op_control *control; | |||
757 | isl_union_map *umap2; | |||
758 | isl_union_map *res; | |||
759 | }; | |||
760 | ||||
761 | /* Add a copy of "map" to "res" and return the result. | |||
762 | */ | |||
763 | static __isl_give isl_union_map *bin_add_map(__isl_take isl_union_map *res, | |||
764 | __isl_keep isl_map *map) | |||
765 | { | |||
766 | return isl_union_map_add_map(res, isl_map_copy(map)); | |||
767 | } | |||
768 | ||||
769 | /* Combine "map1" and "map2", add the result to "res" and return the result. | |||
770 | * Check whether the result is empty before adding it to "res". | |||
771 | */ | |||
772 | static __isl_give isl_union_map *bin_add_pair(__isl_take isl_union_map *res, | |||
773 | __isl_keep isl_map *map1, __isl_keep isl_map *map2, | |||
774 | struct isl_union_map_gen_bin_data *data) | |||
775 | { | |||
776 | isl_bool empty; | |||
777 | isl_map *map; | |||
778 | ||||
779 | map = data->control->fn_map(isl_map_copy(map1), isl_map_copy(map2)); | |||
780 | empty = isl_map_is_empty(map); | |||
781 | if (empty < 0 || empty) { | |||
782 | isl_map_free(map); | |||
783 | if (empty < 0) | |||
784 | return isl_union_map_free(res); | |||
785 | return res; | |||
786 | } | |||
787 | return isl_union_map_add_map(res, map); | |||
788 | } | |||
789 | ||||
790 | /* Dummy match_space function that simply returns the input space. | |||
791 | */ | |||
792 | static __isl_give isl_space *identity(__isl_take isl_space *space) | |||
793 | { | |||
794 | return space; | |||
795 | } | |||
796 | ||||
797 | /* Look for the map in data->umap2 that corresponds to "map", if any. | |||
798 | * Return (isl_bool_true, matching map) if there is one, | |||
799 | * (isl_bool_false, NULL) if there is no matching map and | |||
800 | * (isl_bool_error, NULL) on error. | |||
801 | * | |||
802 | * If not NULL, then data->control->filter specifies whether "map" | |||
803 | * can have any matching map. If so, | |||
804 | * data->control->match_space specifies which map in data->umap2 | |||
805 | * corresponds to "map". | |||
806 | */ | |||
807 | static __isl_keep isl_maybe_isl_map bin_try_get_match( | |||
808 | struct isl_union_map_gen_bin_data *data, __isl_keep isl_map *map) | |||
809 | { | |||
810 | uint32_t hash; | |||
811 | struct isl_hash_table_entry *entry2; | |||
812 | isl_space *space; | |||
813 | isl_maybe_isl_map res = { isl_bool_error, NULL((void*)0) }; | |||
814 | ||||
815 | if (data->control->filter) { | |||
816 | res.valid = data->control->filter(map); | |||
817 | if (res.valid < 0 || !res.valid) | |||
818 | return res; | |||
819 | res.valid = isl_bool_error; | |||
820 | } | |||
821 | ||||
822 | space = isl_map_get_space(map); | |||
823 | if (data->control->match_space != &identity) | |||
824 | space = data->control->match_space(space); | |||
825 | if (!space) | |||
826 | return res; | |||
827 | hash = isl_space_get_hash(space); | |||
828 | entry2 = isl_hash_table_find(isl_union_map_get_ctx(data->umap2), | |||
829 | &data->umap2->table, hash, | |||
830 | &has_space, space, 0); | |||
831 | isl_space_free(space); | |||
832 | res.valid = entry2 != NULL((void*)0); | |||
833 | if (entry2) | |||
834 | res.value = entry2->data; | |||
835 | ||||
836 | return res; | |||
837 | } | |||
838 | ||||
839 | /* isl_hash_table_foreach callback for gen_bin_op. | |||
840 | * Look for the map in data->umap2 that corresponds | |||
841 | * to the map that "entry" points to, apply the binary operation and | |||
842 | * add the result to data->res. | |||
843 | * | |||
844 | * If no corresponding map can be found, then the effect depends | |||
845 | * on data->control->subtract. If it is set, then the current map | |||
846 | * is added directly to the result. Otherwise, it is ignored. | |||
847 | */ | |||
848 | static isl_stat gen_bin_entry(void **entry, void *user) | |||
849 | { | |||
850 | struct isl_union_map_gen_bin_data *data = user; | |||
851 | isl_map *map = *entry; | |||
852 | isl_maybe_isl_map m; | |||
853 | ||||
854 | m = bin_try_get_match(data, map); | |||
855 | if (m.valid < 0) | |||
856 | return isl_stat_error; | |||
857 | if (!m.valid && !data->control->subtract) | |||
858 | return isl_stat_ok; | |||
859 | ||||
860 | if (!m.valid) | |||
861 | data->res = bin_add_map(data->res, map); | |||
862 | else | |||
863 | data->res = bin_add_pair(data->res, map, m.value, data); | |||
864 | if (!data->res) | |||
865 | return isl_stat_error; | |||
866 | ||||
867 | return isl_stat_ok; | |||
868 | } | |||
869 | ||||
870 | /* Apply a binary operation to "umap1" and "umap2" based on "control". | |||
871 | * Run over all maps in "umap1" and look for the corresponding map in "umap2" | |||
872 | * in gen_bin_entry. | |||
873 | */ | |||
874 | static __isl_give isl_union_map *gen_bin_op(__isl_take isl_union_map *umap1, | |||
875 | __isl_take isl_union_map *umap2, struct isl_bin_op_control *control) | |||
876 | { | |||
877 | struct isl_union_map_gen_bin_data data = { control, NULL((void*)0), NULL((void*)0) }; | |||
878 | ||||
879 | umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2)); | |||
880 | umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1)); | |||
881 | ||||
882 | if (!umap1 || !umap2) | |||
883 | goto error; | |||
884 | ||||
885 | data.umap2 = umap2; | |||
886 | data.res = isl_union_map_alloc(isl_space_copy(umap1->dim), | |||
887 | umap1->table.n); | |||
888 | if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table, | |||
889 | &gen_bin_entry, &data) < 0) | |||
890 | goto error; | |||
891 | ||||
892 | isl_union_map_free(umap1); | |||
893 | isl_union_map_free(umap2); | |||
894 | return data.res; | |||
895 | error: | |||
896 | isl_union_map_free(umap1); | |||
897 | isl_union_map_free(umap2); | |||
898 | isl_union_map_free(data.res); | |||
899 | return NULL((void*)0); | |||
900 | } | |||
901 | ||||
902 | __isl_give isl_union_map *isl_union_map_subtract( | |||
903 | __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) | |||
904 | { | |||
905 | struct isl_bin_op_control control = { | |||
906 | .subtract = 1, | |||
907 | .match_space = &identity, | |||
908 | .fn_map = &isl_map_subtract, | |||
909 | }; | |||
910 | ||||
911 | return gen_bin_op(umap1, umap2, &control); | |||
912 | } | |||
913 | ||||
914 | __isl_give isl_union_setisl_union_map *isl_union_set_subtract( | |||
915 | __isl_take isl_union_setisl_union_map *uset1, __isl_take isl_union_setisl_union_map *uset2) | |||
916 | { | |||
917 | return isl_union_map_subtract(uset1, uset2); | |||
918 | } | |||
919 | ||||
920 | struct isl_union_map_gen_bin_set_data { | |||
921 | isl_setisl_map *set; | |||
922 | isl_union_map *res; | |||
923 | }; | |||
924 | ||||
925 | static isl_stat intersect_params_entry(void **entry, void *user) | |||
926 | { | |||
927 | struct isl_union_map_gen_bin_set_data *data = user; | |||
928 | isl_map *map = *entry; | |||
929 | int empty; | |||
930 | ||||
931 | map = isl_map_copy(map); | |||
932 | map = isl_map_intersect_params(map, isl_set_copy(data->set)); | |||
933 | ||||
934 | empty = isl_map_is_empty(map); | |||
935 | if (empty < 0) { | |||
936 | isl_map_free(map); | |||
937 | return isl_stat_error; | |||
938 | } | |||
939 | ||||
940 | data->res = isl_union_map_add_map(data->res, map); | |||
941 | ||||
942 | return isl_stat_ok; | |||
943 | } | |||
944 | ||||
945 | static __isl_give isl_union_map *gen_bin_set_op(__isl_take isl_union_map *umap, | |||
946 | __isl_take isl_setisl_map *set, isl_stat (*fn)(void **, void *)) | |||
947 | { | |||
948 | struct isl_union_map_gen_bin_set_data data = { NULL((void*)0), NULL((void*)0) }; | |||
949 | ||||
950 | umap = isl_union_map_align_params(umap, isl_set_get_space(set)); | |||
951 | set = isl_set_align_params(set, isl_union_map_get_space(umap)); | |||
952 | ||||
953 | if (!umap || !set) | |||
954 | goto error; | |||
955 | ||||
956 | data.set = set; | |||
957 | data.res = isl_union_map_alloc(isl_space_copy(umap->dim), | |||
958 | umap->table.n); | |||
959 | if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, | |||
960 | fn, &data) < 0) | |||
961 | goto error; | |||
962 | ||||
963 | isl_union_map_free(umap); | |||
964 | isl_set_free(set); | |||
965 | return data.res; | |||
966 | error: | |||
967 | isl_union_map_free(umap); | |||
968 | isl_set_free(set); | |||
969 | isl_union_map_free(data.res); | |||
970 | return NULL((void*)0); | |||
971 | } | |||
972 | ||||
973 | /* Intersect "umap" with the parameter domain "set". | |||
974 | * | |||
975 | * If "set" does not have any constraints, then we can return immediately. | |||
976 | */ | |||
977 | __isl_give isl_union_map *isl_union_map_intersect_params( | |||
978 | __isl_take isl_union_map *umap, __isl_take isl_setisl_map *set) | |||
979 | { | |||
980 | int is_universe; | |||
981 | ||||
982 | is_universe = isl_set_plain_is_universe(set); | |||
983 | if (is_universe < 0) | |||
984 | goto error; | |||
985 | if (is_universe) { | |||
986 | isl_set_free(set); | |||
987 | return umap; | |||
988 | } | |||
989 | ||||
990 | return gen_bin_set_op(umap, set, &intersect_params_entry); | |||
991 | error: | |||
992 | isl_union_map_free(umap); | |||
993 | isl_set_free(set); | |||
994 | return NULL((void*)0); | |||
995 | } | |||
996 | ||||
997 | __isl_give isl_union_setisl_union_map *isl_union_set_intersect_params( | |||
998 | __isl_take isl_union_setisl_union_map *uset, __isl_take isl_setisl_map *set) | |||
999 | { | |||
1000 | return isl_union_map_intersect_params(uset, set); | |||
1001 | } | |||
1002 | ||||
1003 | static __isl_give isl_union_map *union_map_intersect_params( | |||
1004 | __isl_take isl_union_map *umap, __isl_take isl_union_setisl_union_map *uset) | |||
1005 | { | |||
1006 | return isl_union_map_intersect_params(umap, | |||
1007 | isl_set_from_union_set(uset)); | |||
1008 | } | |||
1009 | ||||
1010 | static __isl_give isl_union_map *union_map_gist_params( | |||
1011 | __isl_take isl_union_map *umap, __isl_take isl_union_setisl_union_map *uset) | |||
1012 | { | |||
1013 | return isl_union_map_gist_params(umap, isl_set_from_union_set(uset)); | |||
1014 | } | |||
1015 | ||||
1016 | struct isl_union_map_match_bin_data { | |||
1017 | isl_union_map *umap2; | |||
1018 | isl_union_map *res; | |||
1019 | __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*); | |||
1020 | }; | |||
1021 | ||||
1022 | static isl_stat match_bin_entry(void **entry, void *user) | |||
1023 | { | |||
1024 | struct isl_union_map_match_bin_data *data = user; | |||
1025 | uint32_t hash; | |||
1026 | struct isl_hash_table_entry *entry2; | |||
1027 | isl_map *map = *entry; | |||
1028 | int empty; | |||
1029 | ||||
1030 | hash = isl_space_get_hash(map->dim); | |||
1031 | entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table, | |||
1032 | hash, &has_space, map->dim, 0); | |||
1033 | if (!entry2) | |||
1034 | return isl_stat_ok; | |||
1035 | ||||
1036 | map = isl_map_copy(map); | |||
1037 | map = data->fn(map, isl_map_copy(entry2->data)); | |||
1038 | ||||
1039 | empty = isl_map_is_empty(map); | |||
1040 | if (empty < 0) { | |||
1041 | isl_map_free(map); | |||
1042 | return isl_stat_error; | |||
1043 | } | |||
1044 | if (empty) { | |||
1045 | isl_map_free(map); | |||
1046 | return isl_stat_ok; | |||
1047 | } | |||
1048 | ||||
1049 | data->res = isl_union_map_add_map(data->res, map); | |||
1050 | ||||
1051 | return isl_stat_ok; | |||
1052 | } | |||
1053 | ||||
1054 | static __isl_give isl_union_map *match_bin_op(__isl_take isl_union_map *umap1, | |||
1055 | __isl_take isl_union_map *umap2, | |||
1056 | __isl_give isl_map *(*fn)(__isl_take isl_map*, __isl_take isl_map*)) | |||
1057 | { | |||
1058 | struct isl_union_map_match_bin_data data = { NULL((void*)0), NULL((void*)0), fn }; | |||
1059 | ||||
1060 | umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2)); | |||
1061 | umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1)); | |||
1062 | ||||
1063 | if (!umap1 || !umap2) | |||
1064 | goto error; | |||
1065 | ||||
1066 | data.umap2 = umap2; | |||
1067 | data.res = isl_union_map_alloc(isl_space_copy(umap1->dim), | |||
1068 | umap1->table.n); | |||
1069 | if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table, | |||
1070 | &match_bin_entry, &data) < 0) | |||
1071 | goto error; | |||
1072 | ||||
1073 | isl_union_map_free(umap1); | |||
1074 | isl_union_map_free(umap2); | |||
1075 | return data.res; | |||
1076 | error: | |||
1077 | isl_union_map_free(umap1); | |||
1078 | isl_union_map_free(umap2); | |||
1079 | isl_union_map_free(data.res); | |||
1080 | return NULL((void*)0); | |||
1081 | } | |||
1082 | ||||
1083 | __isl_give isl_union_map *isl_union_map_intersect( | |||
1084 | __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) | |||
1085 | { | |||
1086 | return match_bin_op(umap1, umap2, &isl_map_intersect); | |||
1087 | } | |||
1088 | ||||
1089 | /* Compute the intersection of the two union_sets. | |||
1090 | * As a special case, if exactly one of the two union_sets | |||
1091 | * is a parameter domain, then intersect the parameter domain | |||
1092 | * of the other one with this set. | |||
1093 | */ | |||
1094 | __isl_give isl_union_setisl_union_map *isl_union_set_intersect( | |||
1095 | __isl_take isl_union_setisl_union_map *uset1, __isl_take isl_union_setisl_union_map *uset2) | |||
1096 | { | |||
1097 | int p1, p2; | |||
1098 | ||||
1099 | p1 = isl_union_set_is_params(uset1); | |||
| ||||
1100 | p2 = isl_union_set_is_params(uset2); | |||
1101 | if (p1 < 0 || p2 < 0) | |||
1102 | goto error; | |||
1103 | if (!p1 && p2) | |||
1104 | return union_map_intersect_params(uset1, uset2); | |||
1105 | if (p1 && !p2) | |||
1106 | return union_map_intersect_params(uset2, uset1); | |||
| ||||
1107 | return isl_union_map_intersect(uset1, uset2); | |||
1108 | error: | |||
1109 | isl_union_set_free(uset1); | |||
1110 | isl_union_set_free(uset2); | |||
1111 | return NULL((void*)0); | |||
1112 | } | |||
1113 | ||||
1114 | static isl_stat gist_params_entry(void **entry, void *user) | |||
1115 | { | |||
1116 | struct isl_union_map_gen_bin_set_data *data = user; | |||
1117 | isl_map *map = *entry; | |||
1118 | int empty; | |||
1119 | ||||
1120 | map = isl_map_copy(map); | |||
1121 | map = isl_map_gist_params(map, isl_set_copy(data->set)); | |||
1122 | ||||
1123 | empty = isl_map_is_empty(map); | |||
1124 | if (empty < 0) { | |||
1125 | isl_map_free(map); | |||
1126 | return isl_stat_error; | |||
1127 | } | |||
1128 | ||||
1129 | data->res = isl_union_map_add_map(data->res, map); | |||
1130 | ||||
1131 | return isl_stat_ok; | |||
1132 | } | |||
1133 | ||||
1134 | __isl_give isl_union_map *isl_union_map_gist_params( | |||
1135 | __isl_take isl_union_map *umap, __isl_take isl_setisl_map *set) | |||
1136 | { | |||
1137 | return gen_bin_set_op(umap, set, &gist_params_entry); | |||
1138 | } | |||
1139 | ||||
1140 | __isl_give isl_union_setisl_union_map *isl_union_set_gist_params( | |||
1141 | __isl_take isl_union_setisl_union_map *uset, __isl_take isl_setisl_map *set) | |||
1142 | { | |||
1143 | return isl_union_map_gist_params(uset, set); | |||
1144 | } | |||
1145 | ||||
1146 | __isl_give isl_union_map *isl_union_map_gist(__isl_take isl_union_map *umap, | |||
1147 | __isl_take isl_union_map *context) | |||
1148 | { | |||
1149 | return match_bin_op(umap, context, &isl_map_gist); | |||
1150 | } | |||
1151 | ||||
1152 | __isl_give isl_union_setisl_union_map *isl_union_set_gist(__isl_take isl_union_setisl_union_map *uset, | |||
1153 | __isl_take isl_union_setisl_union_map *context) | |||
1154 | { | |||
1155 | if (isl_union_set_is_params(context)) | |||
1156 | return union_map_gist_params(uset, context); | |||
1157 | return isl_union_map_gist(uset, context); | |||
1158 | } | |||
1159 | ||||
1160 | /* For each map in "umap", remove the constraints in the corresponding map | |||
1161 | * of "context". | |||
1162 | * Each map in "context" is assumed to consist of a single disjunct and | |||
1163 | * to have explicit representations for all local variables. | |||
1164 | */ | |||
1165 | __isl_give isl_union_map *isl_union_map_plain_gist( | |||
1166 | __isl_take isl_union_map *umap, __isl_take isl_union_map *context) | |||
1167 | { | |||
1168 | return match_bin_op(umap, context, &isl_map_plain_gist); | |||
1169 | } | |||
1170 | ||||
1171 | /* For each set in "uset", remove the constraints in the corresponding set | |||
1172 | * of "context". | |||
1173 | * Each set in "context" is assumed to consist of a single disjunct and | |||
1174 | * to have explicit representations for all local variables. | |||
1175 | */ | |||
1176 | __isl_give isl_union_setisl_union_map *isl_union_set_plain_gist( | |||
1177 | __isl_take isl_union_setisl_union_map *uset, __isl_take isl_union_setisl_union_map *context) | |||
1178 | { | |||
1179 | return isl_union_map_plain_gist(uset, context); | |||
1180 | } | |||
1181 | ||||
1182 | static __isl_give isl_map *lex_le_set(__isl_take isl_map *set1, | |||
1183 | __isl_take isl_map *set2) | |||
1184 | { | |||
1185 | return isl_set_lex_le_set(set_from_map(set1), set_from_map(set2)); | |||
1186 | } | |||
1187 | ||||
1188 | static __isl_give isl_map *lex_lt_set(__isl_take isl_map *set1, | |||
1189 | __isl_take isl_map *set2) | |||
1190 | { | |||
1191 | return isl_set_lex_lt_set(set_from_map(set1), set_from_map(set2)); | |||
1192 | } | |||
1193 | ||||
1194 | __isl_give isl_union_map *isl_union_set_lex_lt_union_set( | |||
1195 | __isl_take isl_union_setisl_union_map *uset1, __isl_take isl_union_setisl_union_map *uset2) | |||
1196 | { | |||
1197 | return match_bin_op(uset1, uset2, &lex_lt_set); | |||
1198 | } | |||
1199 | ||||
1200 | __isl_give isl_union_map *isl_union_set_lex_le_union_set( | |||
1201 | __isl_take isl_union_setisl_union_map *uset1, __isl_take isl_union_setisl_union_map *uset2) | |||
1202 | { | |||
1203 | return match_bin_op(uset1, uset2, &lex_le_set); | |||
1204 | } | |||
1205 | ||||
1206 | __isl_give isl_union_map *isl_union_set_lex_gt_union_set( | |||
1207 | __isl_take isl_union_setisl_union_map *uset1, __isl_take isl_union_setisl_union_map *uset2) | |||
1208 | { | |||
1209 | return isl_union_map_reverse(isl_union_set_lex_lt_union_set(uset2, uset1)); | |||
1210 | } | |||
1211 | ||||
1212 | __isl_give isl_union_map *isl_union_set_lex_ge_union_set( | |||
1213 | __isl_take isl_union_setisl_union_map *uset1, __isl_take isl_union_setisl_union_map *uset2) | |||
1214 | { | |||
1215 | return isl_union_map_reverse(isl_union_set_lex_le_union_set(uset2, uset1)); | |||
1216 | } | |||
1217 | ||||
1218 | __isl_give isl_union_map *isl_union_map_lex_gt_union_map( | |||
1219 | __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) | |||
1220 | { | |||
1221 | return isl_union_map_reverse(isl_union_map_lex_lt_union_map(umap2, umap1)); | |||
1222 | } | |||
1223 | ||||
1224 | __isl_give isl_union_map *isl_union_map_lex_ge_union_map( | |||
1225 | __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) | |||
1226 | { | |||
1227 | return isl_union_map_reverse(isl_union_map_lex_le_union_map(umap2, umap1)); | |||
1228 | } | |||
1229 | ||||
1230 | /* Intersect the domain of "umap" with "uset". | |||
1231 | */ | |||
1232 | static __isl_give isl_union_map *union_map_intersect_domain( | |||
1233 | __isl_take isl_union_map *umap, __isl_take isl_union_setisl_union_map *uset) | |||
1234 | { | |||
1235 | struct isl_bin_op_control control = { | |||
1236 | .match_space = &isl_space_domain, | |||
1237 | .fn_map = &isl_map_intersect_domain, | |||
1238 | }; | |||
1239 | ||||
1240 | return gen_bin_op(umap, uset, &control); | |||
1241 | } | |||
1242 | ||||
1243 | /* Intersect the domain of "umap" with "uset". | |||
1244 | * If "uset" is a parameters domain, then intersect the parameter | |||
1245 | * domain of "umap" with this set. | |||
1246 | */ | |||
1247 | __isl_give isl_union_map *isl_union_map_intersect_domain( | |||
1248 | __isl_take isl_union_map *umap, __isl_take isl_union_setisl_union_map *uset) | |||
1249 | { | |||
1250 | if (isl_union_set_is_params(uset)) | |||
1251 | return union_map_intersect_params(umap, uset); | |||
1252 | else | |||
1253 | return union_map_intersect_domain(umap, uset); | |||
1254 | } | |||
1255 | ||||
1256 | /* Remove the elements of "uset" from the domain of "umap". | |||
1257 | */ | |||
1258 | __isl_give isl_union_map *isl_union_map_subtract_domain( | |||
1259 | __isl_take isl_union_map *umap, __isl_take isl_union_setisl_union_map *dom) | |||
1260 | { | |||
1261 | struct isl_bin_op_control control = { | |||
1262 | .subtract = 1, | |||
1263 | .match_space = &isl_space_domain, | |||
1264 | .fn_map = &isl_map_subtract_domain, | |||
1265 | }; | |||
1266 | ||||
1267 | return gen_bin_op(umap, dom, &control); | |||
1268 | } | |||
1269 | ||||
1270 | /* Remove the elements of "uset" from the range of "umap". | |||
1271 | */ | |||
1272 | __isl_give isl_union_map *isl_union_map_subtract_range( | |||
1273 | __isl_take isl_union_map *umap, __isl_take isl_union_setisl_union_map *dom) | |||
1274 | { | |||
1275 | struct isl_bin_op_control control = { | |||
1276 | .subtract = 1, | |||
1277 | .match_space = &isl_space_range, | |||
1278 | .fn_map = &isl_map_subtract_range, | |||
1279 | }; | |||
1280 | ||||
1281 | return gen_bin_op(umap, dom, &control); | |||
1282 | } | |||
1283 | ||||
1284 | /* Compute the gist of "umap" with respect to the domain "uset". | |||
1285 | */ | |||
1286 | static __isl_give isl_union_map *union_map_gist_domain( | |||
1287 | __isl_take isl_union_map *umap, __isl_take isl_union_setisl_union_map *uset) | |||
1288 | { | |||
1289 | struct isl_bin_op_control control = { | |||
1290 | .match_space = &isl_space_domain, | |||
1291 | .fn_map = &isl_map_gist_domain, | |||
1292 | }; | |||
1293 | ||||
1294 | return gen_bin_op(umap, uset, &control); | |||
1295 | } | |||
1296 | ||||
1297 | /* Compute the gist of "umap" with respect to the domain "uset". | |||
1298 | * If "uset" is a parameters domain, then compute the gist | |||
1299 | * with respect to this parameter domain. | |||
1300 | */ | |||
1301 | __isl_give isl_union_map *isl_union_map_gist_domain( | |||
1302 | __isl_take isl_union_map *umap, __isl_take isl_union_setisl_union_map *uset) | |||
1303 | { | |||
1304 | if (isl_union_set_is_params(uset)) | |||
1305 | return union_map_gist_params(umap, uset); | |||
1306 | else | |||
1307 | return union_map_gist_domain(umap, uset); | |||
1308 | } | |||
1309 | ||||
1310 | /* Compute the gist of "umap" with respect to the range "uset". | |||
1311 | */ | |||
1312 | __isl_give isl_union_map *isl_union_map_gist_range( | |||
1313 | __isl_take isl_union_map *umap, __isl_take isl_union_setisl_union_map *uset) | |||
1314 | { | |||
1315 | struct isl_bin_op_control control = { | |||
1316 | .match_space = &isl_space_range, | |||
1317 | .fn_map = &isl_map_gist_range, | |||
1318 | }; | |||
1319 | ||||
1320 | return gen_bin_op(umap, uset, &control); | |||
1321 | } | |||
1322 | ||||
1323 | __isl_give isl_union_map *isl_union_map_intersect_range( | |||
1324 | __isl_take isl_union_map *umap, __isl_take isl_union_setisl_union_map *uset) | |||
1325 | { | |||
1326 | struct isl_bin_op_control control = { | |||
1327 | .match_space = &isl_space_range, | |||
1328 | .fn_map = &isl_map_intersect_range, | |||
1329 | }; | |||
1330 | ||||
1331 | return gen_bin_op(umap, uset, &control); | |||
1332 | } | |||
1333 | ||||
1334 | /* Intersect each map in "umap" in a space A -> [B -> C] | |||
1335 | * with the corresponding map in "factor" in the space A -> C and | |||
1336 | * collect the results. | |||
1337 | */ | |||
1338 | __isl_give isl_union_map *isl_union_map_intersect_range_factor_range( | |||
1339 | __isl_take isl_union_map *umap, __isl_take isl_union_map *factor) | |||
1340 | { | |||
1341 | struct isl_bin_op_control control = { | |||
1342 | .filter = &isl_map_range_is_wrapping, | |||
1343 | .match_space = &isl_space_range_factor_range, | |||
1344 | .fn_map = &isl_map_intersect_range_factor_range, | |||
1345 | }; | |||
1346 | ||||
1347 | return gen_bin_op(umap, factor, &control); | |||
1348 | } | |||
1349 | ||||
1350 | struct isl_union_map_bin_data { | |||
1351 | isl_union_map *umap2; | |||
1352 | isl_union_map *res; | |||
1353 | isl_map *map; | |||
1354 | isl_stat (*fn)(void **entry, void *user); | |||
1355 | }; | |||
1356 | ||||
1357 | static isl_stat apply_range_entry(void **entry, void *user) | |||
1358 | { | |||
1359 | struct isl_union_map_bin_data *data = user; | |||
1360 | isl_map *map2 = *entry; | |||
1361 | isl_bool empty; | |||
1362 | ||||
1363 | if (!isl_space_tuple_is_equal(data->map->dim, isl_dim_out, | |||
1364 | map2->dim, isl_dim_in)) | |||
1365 | return isl_stat_ok; | |||
1366 | ||||
1367 | map2 = isl_map_apply_range(isl_map_copy(data->map), isl_map_copy(map2)); | |||
1368 | ||||
1369 | empty = isl_map_is_empty(map2); | |||
1370 | if (empty < 0) { | |||
1371 | isl_map_free(map2); | |||
1372 | return isl_stat_error; | |||
1373 | } | |||
1374 | if (empty) { | |||
1375 | isl_map_free(map2); | |||
1376 | return isl_stat_ok; | |||
1377 | } | |||
1378 | ||||
1379 | data->res = isl_union_map_add_map(data->res, map2); | |||
1380 | ||||
1381 | return isl_stat_ok; | |||
1382 | } | |||
1383 | ||||
1384 | static isl_stat bin_entry(void **entry, void *user) | |||
1385 | { | |||
1386 | struct isl_union_map_bin_data *data = user; | |||
1387 | isl_map *map = *entry; | |||
1388 | ||||
1389 | data->map = map; | |||
1390 | if (isl_hash_table_foreach(data->umap2->dim->ctx, &data->umap2->table, | |||
1391 | data->fn, data) < 0) | |||
1392 | return isl_stat_error; | |||
1393 | ||||
1394 | return isl_stat_ok; | |||
1395 | } | |||
1396 | ||||
1397 | static __isl_give isl_union_map *bin_op(__isl_take isl_union_map *umap1, | |||
1398 | __isl_take isl_union_map *umap2, | |||
1399 | isl_stat (*fn)(void **entry, void *user)) | |||
1400 | { | |||
1401 | struct isl_union_map_bin_data data = { NULL((void*)0), NULL((void*)0), NULL((void*)0), fn }; | |||
1402 | ||||
1403 | umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2)); | |||
1404 | umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1)); | |||
1405 | ||||
1406 | if (!umap1 || !umap2) | |||
1407 | goto error; | |||
1408 | ||||
1409 | data.umap2 = umap2; | |||
1410 | data.res = isl_union_map_alloc(isl_space_copy(umap1->dim), | |||
1411 | umap1->table.n); | |||
1412 | if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table, | |||
1413 | &bin_entry, &data) < 0) | |||
1414 | goto error; | |||
1415 | ||||
1416 | isl_union_map_free(umap1); | |||
1417 | isl_union_map_free(umap2); | |||
1418 | return data.res; | |||
1419 | error: | |||
1420 | isl_union_map_free(umap1); | |||
1421 | isl_union_map_free(umap2); | |||
1422 | isl_union_map_free(data.res); | |||
1423 | return NULL((void*)0); | |||
1424 | } | |||
1425 | ||||
1426 | __isl_give isl_union_map *isl_union_map_apply_range( | |||
1427 | __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) | |||
1428 | { | |||
1429 | return bin_op(umap1, umap2, &apply_range_entry); | |||
1430 | } | |||
1431 | ||||
1432 | __isl_give isl_union_map *isl_union_map_apply_domain( | |||
1433 | __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) | |||
1434 | { | |||
1435 | umap1 = isl_union_map_reverse(umap1); | |||
1436 | umap1 = isl_union_map_apply_range(umap1, umap2); | |||
1437 | return isl_union_map_reverse(umap1); | |||
1438 | } | |||
1439 | ||||
1440 | __isl_give isl_union_setisl_union_map *isl_union_set_apply( | |||
1441 | __isl_take isl_union_setisl_union_map *uset, __isl_take isl_union_map *umap) | |||
1442 | { | |||
1443 | return isl_union_map_apply_range(uset, umap); | |||
1444 | } | |||
1445 | ||||
1446 | static isl_stat map_lex_lt_entry(void **entry, void *user) | |||
1447 | { | |||
1448 | struct isl_union_map_bin_data *data = user; | |||
1449 | isl_map *map2 = *entry; | |||
1450 | ||||
1451 | if (!isl_space_tuple_is_equal(data->map->dim, isl_dim_out, | |||
1452 | map2->dim, isl_dim_out)) | |||
1453 | return isl_stat_ok; | |||
1454 | ||||
1455 | map2 = isl_map_lex_lt_map(isl_map_copy(data->map), isl_map_copy(map2)); | |||
1456 | ||||
1457 | data->res = isl_union_map_add_map(data->res, map2); | |||
1458 | ||||
1459 | return isl_stat_ok; | |||
1460 | } | |||
1461 | ||||
1462 | __isl_give isl_union_map *isl_union_map_lex_lt_union_map( | |||
1463 | __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) | |||
1464 | { | |||
1465 | return bin_op(umap1, umap2, &map_lex_lt_entry); | |||
1466 | } | |||
1467 | ||||
1468 | static isl_stat map_lex_le_entry(void **entry, void *user) | |||
1469 | { | |||
1470 | struct isl_union_map_bin_data *data = user; | |||
1471 | isl_map *map2 = *entry; | |||
1472 | ||||
1473 | if (!isl_space_tuple_is_equal(data->map->dim, isl_dim_out, | |||
1474 | map2->dim, isl_dim_out)) | |||
1475 | return isl_stat_ok; | |||
1476 | ||||
1477 | map2 = isl_map_lex_le_map(isl_map_copy(data->map), isl_map_copy(map2)); | |||
1478 | ||||
1479 | data->res = isl_union_map_add_map(data->res, map2); | |||
1480 | ||||
1481 | return isl_stat_ok; | |||
1482 | } | |||
1483 | ||||
1484 | __isl_give isl_union_map *isl_union_map_lex_le_union_map( | |||
1485 | __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) | |||
1486 | { | |||
1487 | return bin_op(umap1, umap2, &map_lex_le_entry); | |||
1488 | } | |||
1489 | ||||
1490 | static isl_stat product_entry(void **entry, void *user) | |||
1491 | { | |||
1492 | struct isl_union_map_bin_data *data = user; | |||
1493 | isl_map *map2 = *entry; | |||
1494 | ||||
1495 | map2 = isl_map_product(isl_map_copy(data->map), isl_map_copy(map2)); | |||
1496 | ||||
1497 | data->res = isl_union_map_add_map(data->res, map2); | |||
1498 | ||||
1499 | return isl_stat_ok; | |||
1500 | } | |||
1501 | ||||
1502 | __isl_give isl_union_map *isl_union_map_product(__isl_take isl_union_map *umap1, | |||
1503 | __isl_take isl_union_map *umap2) | |||
1504 | { | |||
1505 | return bin_op(umap1, umap2, &product_entry); | |||
1506 | } | |||
1507 | ||||
1508 | static isl_stat set_product_entry(void **entry, void *user) | |||
1509 | { | |||
1510 | struct isl_union_map_bin_data *data = user; | |||
1511 | isl_setisl_map *set2 = *entry; | |||
1512 | ||||
1513 | set2 = isl_set_product(isl_set_copy(data->map), isl_set_copy(set2)); | |||
1514 | ||||
1515 | data->res = isl_union_set_add_set(data->res, set2); | |||
1516 | ||||
1517 | return isl_stat_ok; | |||
1518 | } | |||
1519 | ||||
1520 | __isl_give isl_union_setisl_union_map *isl_union_set_product(__isl_take isl_union_setisl_union_map *uset1, | |||
1521 | __isl_take isl_union_setisl_union_map *uset2) | |||
1522 | { | |||
1523 | return bin_op(uset1, uset2, &set_product_entry); | |||
1524 | } | |||
1525 | ||||
1526 | static isl_stat domain_product_entry(void **entry, void *user) | |||
1527 | { | |||
1528 | struct isl_union_map_bin_data *data = user; | |||
1529 | isl_map *map2 = *entry; | |||
1530 | ||||
1531 | if (!isl_space_tuple_is_equal(data->map->dim, isl_dim_out, | |||
1532 | map2->dim, isl_dim_out)) | |||
1533 | return isl_stat_ok; | |||
1534 | ||||
1535 | map2 = isl_map_domain_product(isl_map_copy(data->map), | |||
1536 | isl_map_copy(map2)); | |||
1537 | ||||
1538 | data->res = isl_union_map_add_map(data->res, map2); | |||
1539 | ||||
1540 | return isl_stat_ok; | |||
1541 | } | |||
1542 | ||||
1543 | /* Given two maps A -> B and C -> D, construct a map [A -> C] -> (B * D) | |||
1544 | */ | |||
1545 | __isl_give isl_union_map *isl_union_map_domain_product( | |||
1546 | __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) | |||
1547 | { | |||
1548 | return bin_op(umap1, umap2, &domain_product_entry); | |||
1549 | } | |||
1550 | ||||
1551 | static isl_stat range_product_entry(void **entry, void *user) | |||
1552 | { | |||
1553 | struct isl_union_map_bin_data *data = user; | |||
1554 | isl_map *map2 = *entry; | |||
1555 | ||||
1556 | if (!isl_space_tuple_is_equal(data->map->dim, isl_dim_in, | |||
1557 | map2->dim, isl_dim_in)) | |||
1558 | return isl_stat_ok; | |||
1559 | ||||
1560 | map2 = isl_map_range_product(isl_map_copy(data->map), | |||
1561 | isl_map_copy(map2)); | |||
1562 | ||||
1563 | data->res = isl_union_map_add_map(data->res, map2); | |||
1564 | ||||
1565 | return isl_stat_ok; | |||
1566 | } | |||
1567 | ||||
1568 | __isl_give isl_union_map *isl_union_map_range_product( | |||
1569 | __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) | |||
1570 | { | |||
1571 | return bin_op(umap1, umap2, &range_product_entry); | |||
1572 | } | |||
1573 | ||||
1574 | /* If data->map A -> B and "map2" C -> D have the same range space, | |||
1575 | * then add (A, C) -> (B * D) to data->res. | |||
1576 | */ | |||
1577 | static isl_stat flat_domain_product_entry(void **entry, void *user) | |||
1578 | { | |||
1579 | struct isl_union_map_bin_data *data = user; | |||
1580 | isl_map *map2 = *entry; | |||
1581 | ||||
1582 | if (!isl_space_tuple_is_equal(data->map->dim, isl_dim_out, | |||
1583 | map2->dim, isl_dim_out)) | |||
1584 | return isl_stat_ok; | |||
1585 | ||||
1586 | map2 = isl_map_flat_domain_product(isl_map_copy(data->map), | |||
1587 | isl_map_copy(map2)); | |||
1588 | ||||
1589 | data->res = isl_union_map_add_map(data->res, map2); | |||
1590 | ||||
1591 | return isl_stat_ok; | |||
1592 | } | |||
1593 | ||||
1594 | /* Given two maps A -> B and C -> D, construct a map (A, C) -> (B * D). | |||
1595 | */ | |||
1596 | __isl_give isl_union_map *isl_union_map_flat_domain_product( | |||
1597 | __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) | |||
1598 | { | |||
1599 | return bin_op(umap1, umap2, &flat_domain_product_entry); | |||
1600 | } | |||
1601 | ||||
1602 | static isl_stat flat_range_product_entry(void **entry, void *user) | |||
1603 | { | |||
1604 | struct isl_union_map_bin_data *data = user; | |||
1605 | isl_map *map2 = *entry; | |||
1606 | ||||
1607 | if (!isl_space_tuple_is_equal(data->map->dim, isl_dim_in, | |||
1608 | map2->dim, isl_dim_in)) | |||
1609 | return isl_stat_ok; | |||
1610 | ||||
1611 | map2 = isl_map_flat_range_product(isl_map_copy(data->map), | |||
1612 | isl_map_copy(map2)); | |||
1613 | ||||
1614 | data->res = isl_union_map_add_map(data->res, map2); | |||
1615 | ||||
1616 | return isl_stat_ok; | |||
1617 | } | |||
1618 | ||||
1619 | __isl_give isl_union_map *isl_union_map_flat_range_product( | |||
1620 | __isl_take isl_union_map *umap1, __isl_take isl_union_map *umap2) | |||
1621 | { | |||
1622 | return bin_op(umap1, umap2, &flat_range_product_entry); | |||
1623 | } | |||
1624 | ||||
1625 | /* Data structure that specifies how un_op should modify | |||
1626 | * the maps in the union map. | |||
1627 | * | |||
1628 | * If "inplace" is set, then the maps in the input union map | |||
1629 | * are modified in place. This means that "fn_map" should not | |||
1630 | * change the meaning of the map or that the union map only | |||
1631 | * has a single reference. | |||
1632 | * If "total" is set, then all maps need to be modified and | |||
1633 | * the results need to live in the same space. | |||
1634 | * Otherwise, a new union map is constructed to store the results. | |||
1635 | * If "filter" is not NULL, then only the input maps that satisfy "filter" | |||
1636 | * are taken into account. "filter_user" is passed as the second argument | |||
1637 | * to "filter". No filter can be set if "inplace" or | |||
1638 | * "total" is set. | |||
1639 | * "fn_map" specifies how the maps (selected by "filter") | |||
1640 | * should be transformed. | |||
1641 | */ | |||
1642 | struct isl_un_op_control { | |||
1643 | int inplace; | |||
1644 | int total; | |||
1645 | isl_bool (*filter)(__isl_keep isl_map *map, void *user); | |||
1646 | void *filter_user; | |||
1647 | __isl_give isl_map *(*fn_map)(__isl_take isl_map *map); | |||
1648 | }; | |||
1649 | ||||
1650 | /* Data structure for wrapping the data for un_op_filter_drop_user. | |||
1651 | * "filter" is the function that is being wrapped. | |||
1652 | */ | |||
1653 | struct isl_un_op_drop_user_data { | |||
1654 | isl_bool (*filter)(__isl_keep isl_map *map); | |||
1655 | }; | |||
1656 | ||||
1657 | /* Wrapper for isl_un_op_control filters that do not require | |||
1658 | * a second argument. | |||
1659 | * Simply call data->filter without the second argument. | |||
1660 | */ | |||
1661 | static isl_bool un_op_filter_drop_user(__isl_keep isl_map *map, void *user) | |||
1662 | { | |||
1663 | struct isl_un_op_drop_user_data *data = user; | |||
1664 | return data->filter(map); | |||
1665 | } | |||
1666 | ||||
1667 | /* Internal data structure for "un_op". | |||
1668 | * "control" specifies how the maps in the union map should be modified. | |||
1669 | * "res" collects the results. | |||
1670 | */ | |||
1671 | struct isl_union_map_un_data { | |||
1672 | struct isl_un_op_control *control; | |||
1673 | isl_union_map *res; | |||
1674 | }; | |||
1675 | ||||
1676 | /* isl_hash_table_foreach callback for un_op. | |||
1677 | * Handle the map that "entry" points to. | |||
1678 | * | |||
1679 | * If control->filter is set, then check if this map satisfies the filter. | |||
1680 | * If so (or if control->filter is not set), modify the map | |||
1681 | * by calling control->fn_map and either add the result to data->res or | |||
1682 | * replace the original entry by the result (if control->inplace is set). | |||
1683 | */ | |||
1684 | static isl_stat un_entry(void **entry, void *user) | |||
1685 | { | |||
1686 | struct isl_union_map_un_data *data = user; | |||
1687 | isl_map *map = *entry; | |||
1688 | ||||
1689 | if (data->control->filter) { | |||
1690 | isl_bool ok; | |||
1691 | ||||
1692 | ok = data->control->filter(map, data->control->filter_user); | |||
1693 | if (ok < 0) | |||
1694 | return isl_stat_error; | |||
1695 | if (!ok) | |||
1696 | return isl_stat_ok; | |||
1697 | } | |||
1698 | ||||
1699 | map = data->control->fn_map(isl_map_copy(map)); | |||
1700 | if (!map) | |||
1701 | return isl_stat_error; | |||
1702 | if (data->control->inplace) { | |||
1703 | isl_map_free(*entry); | |||
1704 | *entry = map; | |||
1705 | } else { | |||
1706 | data->res = isl_union_map_add_map(data->res, map); | |||
1707 | if (!data->res) | |||
1708 | return isl_stat_error; | |||
1709 | } | |||
1710 | ||||
1711 | return isl_stat_ok; | |||
1712 | } | |||
1713 | ||||
1714 | /* Modify the maps in "umap" based on "control". | |||
1715 | * If control->inplace is set, then modify the maps in "umap" in-place. | |||
1716 | * Otherwise, create a new union map to hold the results. | |||
1717 | * If control->total is set, then perform an inplace computation | |||
1718 | * if "umap" is only referenced once. Otherwise, create a new union map | |||
1719 | * to store the results. | |||
1720 | */ | |||
1721 | static __isl_give isl_union_map *un_op(__isl_take isl_union_map *umap, | |||
1722 | struct isl_un_op_control *control) | |||
1723 | { | |||
1724 | struct isl_union_map_un_data data = { control }; | |||
1725 | ||||
1726 | if (!umap) | |||
1727 | return NULL((void*)0); | |||
1728 | if ((control->inplace || control->total) && control->filter) | |||
1729 | isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,do { isl_handle_error(isl_union_map_get_ctx(umap), isl_error_invalid , "inplace/total modification cannot be filtered", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_union_map.c" , 1731); return isl_union_map_free(umap); } while (0) | |||
1730 | "inplace/total modification cannot be filtered",do { isl_handle_error(isl_union_map_get_ctx(umap), isl_error_invalid , "inplace/total modification cannot be filtered", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_union_map.c" , 1731); return isl_union_map_free(umap); } while (0) | |||
1731 | return isl_union_map_free(umap))do { isl_handle_error(isl_union_map_get_ctx(umap), isl_error_invalid , "inplace/total modification cannot be filtered", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_union_map.c" , 1731); return isl_union_map_free(umap); } while (0); | |||
1732 | ||||
1733 | if (control->total && umap->ref == 1) | |||
1734 | control->inplace = 1; | |||
1735 | if (control->inplace) { | |||
1736 | data.res = umap; | |||
1737 | } else { | |||
1738 | isl_space *space; | |||
1739 | ||||
1740 | space = isl_union_map_get_space(umap); | |||
1741 | data.res = isl_union_map_alloc(space, umap->table.n); | |||
1742 | } | |||
1743 | if (isl_hash_table_foreach(isl_union_map_get_ctx(umap), | |||
1744 | &umap->table, &un_entry, &data) < 0) | |||
1745 | data.res = isl_union_map_free(data.res); | |||
1746 | ||||
1747 | if (control->inplace) | |||
1748 | return data.res; | |||
1749 | isl_union_map_free(umap); | |||
1750 | return data.res; | |||
1751 | } | |||
1752 | ||||
1753 | __isl_give isl_union_map *isl_union_map_from_range( | |||
1754 | __isl_take isl_union_setisl_union_map *uset) | |||
1755 | { | |||
1756 | struct isl_un_op_control control = { | |||
1757 | .fn_map = &isl_map_from_range, | |||
1758 | }; | |||
1759 | return un_op(uset, &control); | |||
1760 | } | |||
1761 | ||||
1762 | __isl_give isl_union_map *isl_union_map_from_domain( | |||
1763 | __isl_take isl_union_setisl_union_map *uset) | |||
1764 | { | |||
1765 | return isl_union_map_reverse(isl_union_map_from_range(uset)); | |||
1766 | } | |||
1767 | ||||
1768 | __isl_give isl_union_map *isl_union_map_from_domain_and_range( | |||
1769 | __isl_take isl_union_setisl_union_map *domain, __isl_take isl_union_setisl_union_map *range) | |||
1770 | { | |||
1771 | return isl_union_map_apply_range(isl_union_map_from_domain(domain), | |||
1772 | isl_union_map_from_range(range)); | |||
1773 | } | |||
1774 | ||||
1775 | /* Modify the maps in "umap" by applying "fn" on them. | |||
1776 | * "fn" should apply to all maps in "umap" and should not modify the space. | |||
1777 | */ | |||
1778 | static __isl_give isl_union_map *total(__isl_take isl_union_map *umap, | |||
1779 | __isl_give isl_map *(*fn)(__isl_take isl_map *)) | |||
1780 | { | |||
1781 | struct isl_un_op_control control = { | |||
1782 | .total = 1, | |||
1783 | .fn_map = fn, | |||
1784 | }; | |||
1785 | ||||
1786 | return un_op(umap, &control); | |||
1787 | } | |||
1788 | ||||
1789 | /* Compute the affine hull of "map" and return the result as an isl_map. | |||
1790 | */ | |||
1791 | static __isl_give isl_map *isl_map_affine_hull_map(__isl_take isl_map *map) | |||
1792 | { | |||
1793 | return isl_map_from_basic_map(isl_map_affine_hull(map)); | |||
1794 | } | |||
1795 | ||||
1796 | __isl_give isl_union_map *isl_union_map_affine_hull( | |||
1797 | __isl_take isl_union_map *umap) | |||
1798 | { | |||
1799 | return total(umap, &isl_map_affine_hull_map); | |||
1800 | } | |||
1801 | ||||
1802 | __isl_give isl_union_setisl_union_map *isl_union_set_affine_hull( | |||
1803 | __isl_take isl_union_setisl_union_map *uset) | |||
1804 | { | |||
1805 | return isl_union_map_affine_hull(uset); | |||
1806 | } | |||
1807 | ||||
1808 | /* Wrapper around isl_set_combined_lineality_space | |||
1809 | * that returns the combined lineality space in the form of an isl_set | |||
1810 | * instead of an isl_basic_set. | |||
1811 | */ | |||
1812 | static __isl_give isl_setisl_map *combined_lineality_space(__isl_take isl_setisl_map *set) | |||
1813 | { | |||
1814 | return isl_set_from_basic_set(isl_set_combined_lineality_space(set)); | |||
1815 | } | |||
1816 | ||||
1817 | /* For each set in "uset", compute the (linear) hull | |||
1818 | * of the lineality spaces of its basic sets and | |||
1819 | * collect and return the results. | |||
1820 | */ | |||
1821 | __isl_give isl_union_setisl_union_map *isl_union_set_combined_lineality_space( | |||
1822 | __isl_take isl_union_setisl_union_map *uset) | |||
1823 | { | |||
1824 | struct isl_un_op_control control = { | |||
1825 | .fn_map = &combined_lineality_space, | |||
1826 | }; | |||
1827 | return un_op(uset, &control); | |||
1828 | } | |||
1829 | ||||
1830 | /* Compute the polyhedral hull of "map" and return the result as an isl_map. | |||
1831 | */ | |||
1832 | static __isl_give isl_map *isl_map_polyhedral_hull_map(__isl_take isl_map *map) | |||
1833 | { | |||
1834 | return isl_map_from_basic_map(isl_map_polyhedral_hull(map)); | |||
1835 | } | |||
1836 | ||||
1837 | __isl_give isl_union_map *isl_union_map_polyhedral_hull( | |||
1838 | __isl_take isl_union_map *umap) | |||
1839 | { | |||
1840 | return total(umap, &isl_map_polyhedral_hull_map); | |||
1841 | } | |||
1842 | ||||
1843 | __isl_give isl_union_setisl_union_map *isl_union_set_polyhedral_hull( | |||
1844 | __isl_take isl_union_setisl_union_map *uset) | |||
1845 | { | |||
1846 | return isl_union_map_polyhedral_hull(uset); | |||
1847 | } | |||
1848 | ||||
1849 | /* Compute a superset of the convex hull of "map" that is described | |||
1850 | * by only translates of the constraints in the constituents of "map" and | |||
1851 | * return the result as an isl_map. | |||
1852 | */ | |||
1853 | static __isl_give isl_map *isl_map_simple_hull_map(__isl_take isl_map *map) | |||
1854 | { | |||
1855 | return isl_map_from_basic_map(isl_map_simple_hull(map)); | |||
1856 | } | |||
1857 | ||||
1858 | __isl_give isl_union_map *isl_union_map_simple_hull( | |||
1859 | __isl_take isl_union_map *umap) | |||
1860 | { | |||
1861 | return total(umap, &isl_map_simple_hull_map); | |||
1862 | } | |||
1863 | ||||
1864 | __isl_give isl_union_setisl_union_map *isl_union_set_simple_hull( | |||
1865 | __isl_take isl_union_setisl_union_map *uset) | |||
1866 | { | |||
1867 | return isl_union_map_simple_hull(uset); | |||
1868 | } | |||
1869 | ||||
1870 | static __isl_give isl_union_map *inplace(__isl_take isl_union_map *umap, | |||
1871 | __isl_give isl_map *(*fn)(__isl_take isl_map *)) | |||
1872 | { | |||
1873 | struct isl_un_op_control control = { | |||
1874 | .inplace = 1, | |||
1875 | .fn_map = fn, | |||
1876 | }; | |||
1877 | ||||
1878 | return un_op(umap, &control); | |||
1879 | } | |||
1880 | ||||
1881 | /* Remove redundant constraints in each of the basic maps of "umap". | |||
1882 | * Since removing redundant constraints does not change the meaning | |||
1883 | * or the space, the operation can be performed in-place. | |||
1884 | */ | |||
1885 | __isl_give isl_union_map *isl_union_map_remove_redundancies( | |||
1886 | __isl_take isl_union_map *umap) | |||
1887 | { | |||
1888 | return inplace(umap, &isl_map_remove_redundancies); | |||
1889 | } | |||
1890 | ||||
1891 | /* Remove redundant constraints in each of the basic sets of "uset". | |||
1892 | */ | |||
1893 | __isl_give isl_union_setisl_union_map *isl_union_set_remove_redundancies( | |||
1894 | __isl_take isl_union_setisl_union_map *uset) | |||
1895 | { | |||
1896 | return isl_union_map_remove_redundancies(uset); | |||
1897 | } | |||
1898 | ||||
1899 | __isl_give isl_union_map *isl_union_map_coalesce( | |||
1900 | __isl_take isl_union_map *umap) | |||
1901 | { | |||
1902 | return inplace(umap, &isl_map_coalesce); | |||
1903 | } | |||
1904 | ||||
1905 | __isl_give isl_union_setisl_union_map *isl_union_set_coalesce( | |||
1906 | __isl_take isl_union_setisl_union_map *uset) | |||
1907 | { | |||
1908 | return isl_union_map_coalesce(uset); | |||
1909 | } | |||
1910 | ||||
1911 | __isl_give isl_union_map *isl_union_map_detect_equalities( | |||
1912 | __isl_take isl_union_map *umap) | |||
1913 | { | |||
1914 | return inplace(umap, &isl_map_detect_equalities); | |||
1915 | } | |||
1916 | ||||
1917 | __isl_give isl_union_setisl_union_map *isl_union_set_detect_equalities( | |||
1918 | __isl_take isl_union_setisl_union_map *uset) | |||
1919 | { | |||
1920 | return isl_union_map_detect_equalities(uset); | |||
1921 | } | |||
1922 | ||||
1923 | __isl_give isl_union_map *isl_union_map_compute_divs( | |||
1924 | __isl_take isl_union_map *umap) | |||
1925 | { | |||
1926 | return inplace(umap, &isl_map_compute_divs); | |||
1927 | } | |||
1928 | ||||
1929 | __isl_give isl_union_setisl_union_map *isl_union_set_compute_divs( | |||
1930 | __isl_take isl_union_setisl_union_map *uset) | |||
1931 | { | |||
1932 | return isl_union_map_compute_divs(uset); | |||
1933 | } | |||
1934 | ||||
1935 | __isl_give isl_union_map *isl_union_map_lexmin( | |||
1936 | __isl_take isl_union_map *umap) | |||
1937 | { | |||
1938 | return total(umap, &isl_map_lexmin); | |||
1939 | } | |||
1940 | ||||
1941 | __isl_give isl_union_setisl_union_map *isl_union_set_lexmin( | |||
1942 | __isl_take isl_union_setisl_union_map *uset) | |||
1943 | { | |||
1944 | return isl_union_map_lexmin(uset); | |||
1945 | } | |||
1946 | ||||
1947 | __isl_give isl_union_map *isl_union_map_lexmax( | |||
1948 | __isl_take isl_union_map *umap) | |||
1949 | { | |||
1950 | return total(umap, &isl_map_lexmax); | |||
1951 | } | |||
1952 | ||||
1953 | __isl_give isl_union_setisl_union_map *isl_union_set_lexmax( | |||
1954 | __isl_take isl_union_setisl_union_map *uset) | |||
1955 | { | |||
1956 | return isl_union_map_lexmax(uset); | |||
1957 | } | |||
1958 | ||||
1959 | /* Return the universe in the space of "map". | |||
1960 | */ | |||
1961 | static __isl_give isl_map *universe(__isl_take isl_map *map) | |||
1962 | { | |||
1963 | isl_space *space; | |||
1964 | ||||
1965 | space = isl_map_get_space(map); | |||
1966 | isl_map_free(map); | |||
1967 | return isl_map_universe(space); | |||
1968 | } | |||
1969 | ||||
1970 | __isl_give isl_union_map *isl_union_map_universe(__isl_take isl_union_map *umap) | |||
1971 | { | |||
1972 | struct isl_un_op_control control = { | |||
1973 | .fn_map = &universe, | |||
1974 | }; | |||
1975 | return un_op(umap, &control); | |||
1976 | } | |||
1977 | ||||
1978 | __isl_give isl_union_setisl_union_map *isl_union_set_universe(__isl_take isl_union_setisl_union_map *uset) | |||
1979 | { | |||
1980 | return isl_union_map_universe(uset); | |||
1981 | } | |||
1982 | ||||
1983 | __isl_give isl_union_map *isl_union_map_reverse(__isl_take isl_union_map *umap) | |||
1984 | { | |||
1985 | struct isl_un_op_control control = { | |||
1986 | .fn_map = &isl_map_reverse, | |||
1987 | }; | |||
1988 | return un_op(umap, &control); | |||
1989 | } | |||
1990 | ||||
1991 | /* Compute the parameter domain of the given union map. | |||
1992 | */ | |||
1993 | __isl_give isl_setisl_map *isl_union_map_params(__isl_take isl_union_map *umap) | |||
1994 | { | |||
1995 | struct isl_un_op_control control = { | |||
1996 | .fn_map = &isl_map_params, | |||
1997 | }; | |||
1998 | int empty; | |||
1999 | ||||
2000 | empty = isl_union_map_is_empty(umap); | |||
2001 | if (empty < 0) | |||
2002 | goto error; | |||
2003 | if (empty) { | |||
2004 | isl_space *space; | |||
2005 | space = isl_union_map_get_space(umap); | |||
2006 | isl_union_map_free(umap); | |||
2007 | return isl_set_empty(space); | |||
2008 | } | |||
2009 | return isl_set_from_union_set(un_op(umap, &control)); | |||
2010 | error: | |||
2011 | isl_union_map_free(umap); | |||
2012 | return NULL((void*)0); | |||
2013 | } | |||
2014 | ||||
2015 | /* Compute the parameter domain of the given union set. | |||
2016 | */ | |||
2017 | __isl_give isl_setisl_map *isl_union_set_params(__isl_take isl_union_setisl_union_map *uset) | |||
2018 | { | |||
2019 | return isl_union_map_params(uset); | |||
2020 | } | |||
2021 | ||||
2022 | __isl_give isl_union_setisl_union_map *isl_union_map_domain(__isl_take isl_union_map *umap) | |||
2023 | { | |||
2024 | struct isl_un_op_control control = { | |||
2025 | .fn_map = &isl_map_domain, | |||
2026 | }; | |||
2027 | return un_op(umap, &control); | |||
2028 | } | |||
2029 | ||||
2030 | __isl_give isl_union_setisl_union_map *isl_union_map_range(__isl_take isl_union_map *umap) | |||
2031 | { | |||
2032 | struct isl_un_op_control control = { | |||
2033 | .fn_map = &isl_map_range, | |||
2034 | }; | |||
2035 | return un_op(umap, &control); | |||
2036 | } | |||
2037 | ||||
2038 | __isl_give isl_union_map *isl_union_map_domain_map( | |||
2039 | __isl_take isl_union_map *umap) | |||
2040 | { | |||
2041 | struct isl_un_op_control control = { | |||
2042 | .fn_map = &isl_map_domain_map, | |||
2043 | }; | |||
2044 | return un_op(umap, &control); | |||
2045 | } | |||
2046 | ||||
2047 | /* Construct an isl_pw_multi_aff that maps "map" to its domain and | |||
2048 | * add the result to "res". | |||
2049 | */ | |||
2050 | static isl_stat domain_map_upma(__isl_take isl_map *map, void *user) | |||
2051 | { | |||
2052 | isl_union_pw_multi_aff **res = user; | |||
2053 | isl_multi_aff *ma; | |||
2054 | isl_pw_multi_aff *pma; | |||
2055 | ||||
2056 | ma = isl_multi_aff_domain_map(isl_map_get_space(map)); | |||
2057 | pma = isl_pw_multi_aff_alloc(isl_map_wrap(map), ma); | |||
2058 | *res = isl_union_pw_multi_aff_add_pw_multi_aff(*res, pma); | |||
2059 | ||||
2060 | return *res ? isl_stat_ok : isl_stat_error; | |||
2061 | ||||
2062 | } | |||
2063 | ||||
2064 | /* Return an isl_union_pw_multi_aff that maps a wrapped copy of "umap" | |||
2065 | * to its domain. | |||
2066 | */ | |||
2067 | __isl_give isl_union_pw_multi_aff *isl_union_map_domain_map_union_pw_multi_aff( | |||
2068 | __isl_take isl_union_map *umap) | |||
2069 | { | |||
2070 | isl_union_pw_multi_aff *res; | |||
2071 | ||||
2072 | res = isl_union_pw_multi_aff_empty(isl_union_map_get_space(umap)); | |||
2073 | if (isl_union_map_foreach_map(umap, &domain_map_upma, &res) < 0) | |||
2074 | res = isl_union_pw_multi_aff_free(res); | |||
2075 | ||||
2076 | isl_union_map_free(umap); | |||
2077 | return res; | |||
2078 | } | |||
2079 | ||||
2080 | __isl_give isl_union_map *isl_union_map_range_map( | |||
2081 | __isl_take isl_union_map *umap) | |||
2082 | { | |||
2083 | struct isl_un_op_control control = { | |||
2084 | .fn_map = &isl_map_range_map, | |||
2085 | }; | |||
2086 | return un_op(umap, &control); | |||
2087 | } | |||
2088 | ||||
2089 | /* Given a collection of wrapped maps of the form A[B -> C], | |||
2090 | * return the collection of maps A[B -> C] -> B. | |||
2091 | */ | |||
2092 | __isl_give isl_union_map *isl_union_set_wrapped_domain_map( | |||
2093 | __isl_take isl_union_setisl_union_map *uset) | |||
2094 | { | |||
2095 | struct isl_un_op_drop_user_data data = { &isl_set_is_wrapping }; | |||
2096 | struct isl_un_op_control control = { | |||
2097 | .filter = &un_op_filter_drop_user, | |||
2098 | .filter_user = &data, | |||
2099 | .fn_map = &isl_set_wrapped_domain_map, | |||
2100 | }; | |||
2101 | return un_op(uset, &control); | |||
2102 | } | |||
2103 | ||||
2104 | /* Does "map" relate elements from the same space? | |||
2105 | */ | |||
2106 | static isl_bool equal_tuples(__isl_keep isl_map *map, void *user) | |||
2107 | { | |||
2108 | return isl_space_tuple_is_equal(map->dim, isl_dim_in, | |||
2109 | map->dim, isl_dim_out); | |||
2110 | } | |||
2111 | ||||
2112 | __isl_give isl_union_setisl_union_map *isl_union_map_deltas(__isl_take isl_union_map *umap) | |||
2113 | { | |||
2114 | struct isl_un_op_control control = { | |||
2115 | .filter = &equal_tuples, | |||
2116 | .fn_map = &isl_map_deltas, | |||
2117 | }; | |||
2118 | return un_op(umap, &control); | |||
2119 | } | |||
2120 | ||||
2121 | __isl_give isl_union_map *isl_union_map_deltas_map( | |||
2122 | __isl_take isl_union_map *umap) | |||
2123 | { | |||
2124 | struct isl_un_op_control control = { | |||
2125 | .filter = &equal_tuples, | |||
2126 | .fn_map = &isl_map_deltas_map, | |||
2127 | }; | |||
2128 | return un_op(umap, &control); | |||
2129 | } | |||
2130 | ||||
2131 | __isl_give isl_union_map *isl_union_set_identity(__isl_take isl_union_setisl_union_map *uset) | |||
2132 | { | |||
2133 | struct isl_un_op_control control = { | |||
2134 | .fn_map = &isl_set_identity, | |||
2135 | }; | |||
2136 | return un_op(uset, &control); | |||
2137 | } | |||
2138 | ||||
2139 | /* Construct an identity isl_pw_multi_aff on "set" and add it to *res. | |||
2140 | */ | |||
2141 | static isl_stat identity_upma(__isl_take isl_setisl_map *set, void *user) | |||
2142 | { | |||
2143 | isl_union_pw_multi_aff **res = user; | |||
2144 | isl_space *space; | |||
2145 | isl_pw_multi_aff *pma; | |||
2146 | ||||
2147 | space = isl_space_map_from_set(isl_set_get_space(set)); | |||
2148 | pma = isl_pw_multi_aff_identity(space); | |||
2149 | pma = isl_pw_multi_aff_intersect_domain(pma, set); | |||
2150 | *res = isl_union_pw_multi_aff_add_pw_multi_aff(*res, pma); | |||
2151 | ||||
2152 | return *res ? isl_stat_ok : isl_stat_error; | |||
2153 | } | |||
2154 | ||||
2155 | /* Return an identity function on "uset" in the form | |||
2156 | * of an isl_union_pw_multi_aff. | |||
2157 | */ | |||
2158 | __isl_give isl_union_pw_multi_aff *isl_union_set_identity_union_pw_multi_aff( | |||
2159 | __isl_take isl_union_setisl_union_map *uset) | |||
2160 | { | |||
2161 | isl_union_pw_multi_aff *res; | |||
2162 | ||||
2163 | res = isl_union_pw_multi_aff_empty(isl_union_set_get_space(uset)); | |||
2164 | if (isl_union_set_foreach_set(uset, &identity_upma, &res) < 0) | |||
2165 | res = isl_union_pw_multi_aff_free(res); | |||
2166 | ||||
2167 | isl_union_set_free(uset); | |||
2168 | return res; | |||
2169 | } | |||
2170 | ||||
2171 | /* For each map in "umap" of the form [A -> B] -> C, | |||
2172 | * construct the map A -> C and collect the results. | |||
2173 | */ | |||
2174 | __isl_give isl_union_map *isl_union_map_domain_factor_domain( | |||
2175 | __isl_take isl_union_map *umap) | |||
2176 | { | |||
2177 | struct isl_un_op_drop_user_data data = { &isl_map_domain_is_wrapping }; | |||
2178 | struct isl_un_op_control control = { | |||
2179 | .filter = &un_op_filter_drop_user, | |||
2180 | .filter_user = &data, | |||
2181 | .fn_map = &isl_map_domain_factor_domain, | |||
2182 | }; | |||
2183 | return un_op(umap, &control); | |||
2184 | } | |||
2185 | ||||
2186 | /* For each map in "umap" of the form [A -> B] -> C, | |||
2187 | * construct the map B -> C and collect the results. | |||
2188 | */ | |||
2189 | __isl_give isl_union_map *isl_union_map_domain_factor_range( | |||
2190 | __isl_take isl_union_map *umap) | |||
2191 | { | |||
2192 | struct isl_un_op_drop_user_data data = { &isl_map_domain_is_wrapping }; | |||
2193 | struct isl_un_op_control control = { | |||
2194 | .filter = &un_op_filter_drop_user, | |||
2195 | .filter_user = &data, | |||
2196 | .fn_map = &isl_map_domain_factor_range, | |||
2197 | }; | |||
2198 | return un_op(umap, &control); | |||
2199 | } | |||
2200 | ||||
2201 | /* For each map in "umap" of the form A -> [B -> C], | |||
2202 | * construct the map A -> B and collect the results. | |||
2203 | */ | |||
2204 | __isl_give isl_union_map *isl_union_map_range_factor_domain( | |||
2205 | __isl_take isl_union_map *umap) | |||
2206 | { | |||
2207 | struct isl_un_op_drop_user_data data = { &isl_map_range_is_wrapping }; | |||
2208 | struct isl_un_op_control control = { | |||
2209 | .filter = &un_op_filter_drop_user, | |||
2210 | .filter_user = &data, | |||
2211 | .fn_map = &isl_map_range_factor_domain, | |||
2212 | }; | |||
2213 | return un_op(umap, &control); | |||
2214 | } | |||
2215 | ||||
2216 | /* For each map in "umap" of the form A -> [B -> C], | |||
2217 | * construct the map A -> C and collect the results. | |||
2218 | */ | |||
2219 | __isl_give isl_union_map *isl_union_map_range_factor_range( | |||
2220 | __isl_take isl_union_map *umap) | |||
2221 | { | |||
2222 | struct isl_un_op_drop_user_data data = { &isl_map_range_is_wrapping }; | |||
2223 | struct isl_un_op_control control = { | |||
2224 | .filter = &un_op_filter_drop_user, | |||
2225 | .filter_user = &data, | |||
2226 | .fn_map = &isl_map_range_factor_range, | |||
2227 | }; | |||
2228 | return un_op(umap, &control); | |||
2229 | } | |||
2230 | ||||
2231 | /* For each map in "umap" of the form [A -> B] -> [C -> D], | |||
2232 | * construct the map A -> C and collect the results. | |||
2233 | */ | |||
2234 | __isl_give isl_union_map *isl_union_map_factor_domain( | |||
2235 | __isl_take isl_union_map *umap) | |||
2236 | { | |||
2237 | struct isl_un_op_drop_user_data data = { &isl_map_is_product }; | |||
2238 | struct isl_un_op_control control = { | |||
2239 | .filter = &un_op_filter_drop_user, | |||
2240 | .filter_user = &data, | |||
2241 | .fn_map = &isl_map_factor_domain, | |||
2242 | }; | |||
2243 | return un_op(umap, &control); | |||
2244 | } | |||
2245 | ||||
2246 | /* For each map in "umap" of the form [A -> B] -> [C -> D], | |||
2247 | * construct the map B -> D and collect the results. | |||
2248 | */ | |||
2249 | __isl_give isl_union_map *isl_union_map_factor_range( | |||
2250 | __isl_take isl_union_map *umap) | |||
2251 | { | |||
2252 | struct isl_un_op_drop_user_data data = { &isl_map_is_product }; | |||
2253 | struct isl_un_op_control control = { | |||
2254 | .filter = &un_op_filter_drop_user, | |||
2255 | .filter_user = &data, | |||
2256 | .fn_map = &isl_map_factor_range, | |||
2257 | }; | |||
2258 | return un_op(umap, &control); | |||
2259 | } | |||
2260 | ||||
2261 | __isl_give isl_union_map *isl_union_set_unwrap(__isl_take isl_union_setisl_union_map *uset) | |||
2262 | { | |||
2263 | struct isl_un_op_drop_user_data data = { &isl_set_is_wrapping }; | |||
2264 | struct isl_un_op_control control = { | |||
2265 | .filter = &un_op_filter_drop_user, | |||
2266 | .filter_user = &data, | |||
2267 | .fn_map = &isl_set_unwrap, | |||
2268 | }; | |||
2269 | return un_op(uset, &control); | |||
2270 | } | |||
2271 | ||||
2272 | __isl_give isl_union_setisl_union_map *isl_union_map_wrap(__isl_take isl_union_map *umap) | |||
2273 | { | |||
2274 | struct isl_un_op_control control = { | |||
2275 | .fn_map = &isl_map_wrap, | |||
2276 | }; | |||
2277 | return un_op(umap, &control); | |||
2278 | } | |||
2279 | ||||
2280 | struct isl_union_map_is_subset_data { | |||
2281 | isl_union_map *umap2; | |||
2282 | isl_bool is_subset; | |||
2283 | }; | |||
2284 | ||||
2285 | static isl_stat is_subset_entry(void **entry, void *user) | |||
2286 | { | |||
2287 | struct isl_union_map_is_subset_data *data = user; | |||
2288 | uint32_t hash; | |||
2289 | struct isl_hash_table_entry *entry2; | |||
2290 | isl_map *map = *entry; | |||
2291 | ||||
2292 | hash = isl_space_get_hash(map->dim); | |||
2293 | entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table, | |||
2294 | hash, &has_space, map->dim, 0); | |||
2295 | if (!entry2) { | |||
2296 | int empty = isl_map_is_empty(map); | |||
2297 | if (empty < 0) | |||
2298 | return isl_stat_error; | |||
2299 | if (empty) | |||
2300 | return isl_stat_ok; | |||
2301 | data->is_subset = 0; | |||
2302 | return isl_stat_error; | |||
2303 | } | |||
2304 | ||||
2305 | data->is_subset = isl_map_is_subset(map, entry2->data); | |||
2306 | if (data->is_subset < 0 || !data->is_subset) | |||
2307 | return isl_stat_error; | |||
2308 | ||||
2309 | return isl_stat_ok; | |||
2310 | } | |||
2311 | ||||
2312 | isl_bool isl_union_map_is_subset(__isl_keep isl_union_map *umap1, | |||
2313 | __isl_keep isl_union_map *umap2) | |||
2314 | { | |||
2315 | struct isl_union_map_is_subset_data data = { NULL((void*)0), isl_bool_true }; | |||
2316 | ||||
2317 | umap1 = isl_union_map_copy(umap1); | |||
2318 | umap2 = isl_union_map_copy(umap2); | |||
2319 | umap1 = isl_union_map_align_params(umap1, isl_union_map_get_space(umap2)); | |||
2320 | umap2 = isl_union_map_align_params(umap2, isl_union_map_get_space(umap1)); | |||
2321 | ||||
2322 | if (!umap1 || !umap2) | |||
2323 | goto error; | |||
2324 | ||||
2325 | data.umap2 = umap2; | |||
2326 | if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table, | |||
2327 | &is_subset_entry, &data) < 0 && | |||
2328 | data.is_subset) | |||
2329 | goto error; | |||
2330 | ||||
2331 | isl_union_map_free(umap1); | |||
2332 | isl_union_map_free(umap2); | |||
2333 | ||||
2334 | return data.is_subset; | |||
2335 | error: | |||
2336 | isl_union_map_free(umap1); | |||
2337 | isl_union_map_free(umap2); | |||
2338 | return isl_bool_error; | |||
2339 | } | |||
2340 | ||||
2341 | isl_bool isl_union_set_is_subset(__isl_keep isl_union_setisl_union_map *uset1, | |||
2342 | __isl_keep isl_union_setisl_union_map *uset2) | |||
2343 | { | |||
2344 | return isl_union_map_is_subset(uset1, uset2); | |||
2345 | } | |||
2346 | ||||
2347 | isl_bool isl_union_map_is_equal(__isl_keep isl_union_map *umap1, | |||
2348 | __isl_keep isl_union_map *umap2) | |||
2349 | { | |||
2350 | isl_bool is_subset; | |||
2351 | ||||
2352 | if (!umap1 || !umap2) | |||
2353 | return isl_bool_error; | |||
2354 | is_subset = isl_union_map_is_subset(umap1, umap2); | |||
2355 | if (is_subset != isl_bool_true) | |||
2356 | return is_subset; | |||
2357 | is_subset = isl_union_map_is_subset(umap2, umap1); | |||
2358 | return is_subset; | |||
2359 | } | |||
2360 | ||||
2361 | isl_bool isl_union_set_is_equal(__isl_keep isl_union_setisl_union_map *uset1, | |||
2362 | __isl_keep isl_union_setisl_union_map *uset2) | |||
2363 | { | |||
2364 | return isl_union_map_is_equal(uset1, uset2); | |||
2365 | } | |||
2366 | ||||
2367 | isl_bool isl_union_map_is_strict_subset(__isl_keep isl_union_map *umap1, | |||
2368 | __isl_keep isl_union_map *umap2) | |||
2369 | { | |||
2370 | isl_bool is_subset; | |||
2371 | ||||
2372 | if (!umap1 || !umap2) | |||
2373 | return isl_bool_error; | |||
2374 | is_subset = isl_union_map_is_subset(umap1, umap2); | |||
2375 | if (is_subset != isl_bool_true) | |||
2376 | return is_subset; | |||
2377 | is_subset = isl_union_map_is_subset(umap2, umap1); | |||
2378 | if (is_subset == isl_bool_error) | |||
2379 | return is_subset; | |||
2380 | return !is_subset; | |||
2381 | } | |||
2382 | ||||
2383 | isl_bool isl_union_set_is_strict_subset(__isl_keep isl_union_setisl_union_map *uset1, | |||
2384 | __isl_keep isl_union_setisl_union_map *uset2) | |||
2385 | { | |||
2386 | return isl_union_map_is_strict_subset(uset1, uset2); | |||
2387 | } | |||
2388 | ||||
2389 | /* Internal data structure for isl_union_map_is_disjoint. | |||
2390 | * umap2 is the union map with which we are comparing. | |||
2391 | * is_disjoint is initialized to 1 and is set to 0 as soon | |||
2392 | * as the union maps turn out not to be disjoint. | |||
2393 | */ | |||
2394 | struct isl_union_map_is_disjoint_data { | |||
2395 | isl_union_map *umap2; | |||
2396 | isl_bool is_disjoint; | |||
2397 | }; | |||
2398 | ||||
2399 | /* Check if "map" is disjoint from data->umap2 and abort | |||
2400 | * the search if it is not. | |||
2401 | */ | |||
2402 | static isl_stat is_disjoint_entry(void **entry, void *user) | |||
2403 | { | |||
2404 | struct isl_union_map_is_disjoint_data *data = user; | |||
2405 | uint32_t hash; | |||
2406 | struct isl_hash_table_entry *entry2; | |||
2407 | isl_map *map = *entry; | |||
2408 | ||||
2409 | hash = isl_space_get_hash(map->dim); | |||
2410 | entry2 = isl_hash_table_find(data->umap2->dim->ctx, &data->umap2->table, | |||
2411 | hash, &has_space, map->dim, 0); | |||
2412 | if (!entry2) | |||
2413 | return isl_stat_ok; | |||
2414 | ||||
2415 | data->is_disjoint = isl_map_is_disjoint(map, entry2->data); | |||
2416 | if (data->is_disjoint < 0 || !data->is_disjoint) | |||
2417 | return isl_stat_error; | |||
2418 | ||||
2419 | return isl_stat_ok; | |||
2420 | } | |||
2421 | ||||
2422 | /* Are "umap1" and "umap2" disjoint? | |||
2423 | */ | |||
2424 | isl_bool isl_union_map_is_disjoint(__isl_keep isl_union_map *umap1, | |||
2425 | __isl_keep isl_union_map *umap2) | |||
2426 | { | |||
2427 | struct isl_union_map_is_disjoint_data data = { NULL((void*)0), isl_bool_true }; | |||
2428 | ||||
2429 | umap1 = isl_union_map_copy(umap1); | |||
2430 | umap2 = isl_union_map_copy(umap2); | |||
2431 | umap1 = isl_union_map_align_params(umap1, | |||
2432 | isl_union_map_get_space(umap2)); | |||
2433 | umap2 = isl_union_map_align_params(umap2, | |||
2434 | isl_union_map_get_space(umap1)); | |||
2435 | ||||
2436 | if (!umap1 || !umap2) | |||
2437 | goto error; | |||
2438 | ||||
2439 | data.umap2 = umap2; | |||
2440 | if (isl_hash_table_foreach(umap1->dim->ctx, &umap1->table, | |||
2441 | &is_disjoint_entry, &data) < 0 && | |||
2442 | data.is_disjoint) | |||
2443 | goto error; | |||
2444 | ||||
2445 | isl_union_map_free(umap1); | |||
2446 | isl_union_map_free(umap2); | |||
2447 | ||||
2448 | return data.is_disjoint; | |||
2449 | error: | |||
2450 | isl_union_map_free(umap1); | |||
2451 | isl_union_map_free(umap2); | |||
2452 | return isl_bool_error; | |||
2453 | } | |||
2454 | ||||
2455 | /* Are "uset1" and "uset2" disjoint? | |||
2456 | */ | |||
2457 | isl_bool isl_union_set_is_disjoint(__isl_keep isl_union_setisl_union_map *uset1, | |||
2458 | __isl_keep isl_union_setisl_union_map *uset2) | |||
2459 | { | |||
2460 | return isl_union_map_is_disjoint(uset1, uset2); | |||
2461 | } | |||
2462 | ||||
2463 | static isl_stat sample_entry(void **entry, void *user) | |||
2464 | { | |||
2465 | isl_basic_map **sample = (isl_basic_map **)user; | |||
2466 | isl_map *map = *entry; | |||
2467 | ||||
2468 | *sample = isl_map_sample(isl_map_copy(map)); | |||
2469 | if (!*sample) | |||
2470 | return isl_stat_error; | |||
2471 | if (!isl_basic_map_plain_is_empty(*sample)) | |||
2472 | return isl_stat_error; | |||
2473 | return isl_stat_ok; | |||
2474 | } | |||
2475 | ||||
2476 | __isl_give isl_basic_map *isl_union_map_sample(__isl_take isl_union_map *umap) | |||
2477 | { | |||
2478 | isl_basic_map *sample = NULL((void*)0); | |||
2479 | ||||
2480 | if (!umap) | |||
2481 | return NULL((void*)0); | |||
2482 | ||||
2483 | if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, | |||
2484 | &sample_entry, &sample) < 0 && | |||
2485 | !sample) | |||
2486 | goto error; | |||
2487 | ||||
2488 | if (!sample) | |||
2489 | sample = isl_basic_map_empty(isl_union_map_get_space(umap)); | |||
2490 | ||||
2491 | isl_union_map_free(umap); | |||
2492 | ||||
2493 | return sample; | |||
2494 | error: | |||
2495 | isl_union_map_free(umap); | |||
2496 | return NULL((void*)0); | |||
2497 | } | |||
2498 | ||||
2499 | __isl_give isl_basic_setisl_basic_map *isl_union_set_sample(__isl_take isl_union_setisl_union_map *uset) | |||
2500 | { | |||
2501 | return bset_from_bmap(isl_union_map_sample(uset)); | |||
2502 | } | |||
2503 | ||||
2504 | /* Return an element in "uset" in the form of an isl_point. | |||
2505 | * Return a void isl_point if "uset" is empty. | |||
2506 | */ | |||
2507 | __isl_give isl_point *isl_union_set_sample_point(__isl_take isl_union_setisl_union_map *uset) | |||
2508 | { | |||
2509 | return isl_basic_set_sample_point(isl_union_set_sample(uset)); | |||
2510 | } | |||
2511 | ||||
2512 | struct isl_forall_data { | |||
2513 | isl_bool res; | |||
2514 | isl_bool (*fn)(__isl_keep isl_map *map); | |||
2515 | }; | |||
2516 | ||||
2517 | static isl_stat forall_entry(void **entry, void *user) | |||
2518 | { | |||
2519 | struct isl_forall_data *data = user; | |||
2520 | isl_map *map = *entry; | |||
2521 | ||||
2522 | data->res = data->fn(map); | |||
2523 | if (data->res < 0) | |||
2524 | return isl_stat_error; | |||
2525 | ||||
2526 | if (!data->res) | |||
2527 | return isl_stat_error; | |||
2528 | ||||
2529 | return isl_stat_ok; | |||
2530 | } | |||
2531 | ||||
2532 | static isl_bool union_map_forall(__isl_keep isl_union_map *umap, | |||
2533 | isl_bool (*fn)(__isl_keep isl_map *map)) | |||
2534 | { | |||
2535 | struct isl_forall_data data = { isl_bool_true, fn }; | |||
2536 | ||||
2537 | if (!umap) | |||
2538 | return isl_bool_error; | |||
2539 | ||||
2540 | if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, | |||
2541 | &forall_entry, &data) < 0 && data.res) | |||
2542 | return isl_bool_error; | |||
2543 | ||||
2544 | return data.res; | |||
2545 | } | |||
2546 | ||||
2547 | struct isl_forall_user_data { | |||
2548 | isl_bool res; | |||
2549 | isl_bool (*fn)(__isl_keep isl_map *map, void *user); | |||
2550 | void *user; | |||
2551 | }; | |||
2552 | ||||
2553 | static isl_stat forall_user_entry(void **entry, void *user) | |||
2554 | { | |||
2555 | struct isl_forall_user_data *data = user; | |||
2556 | isl_map *map = *entry; | |||
2557 | ||||
2558 | data->res = data->fn(map, data->user); | |||
2559 | if (data->res < 0) | |||
2560 | return isl_stat_error; | |||
2561 | ||||
2562 | if (!data->res) | |||
2563 | return isl_stat_error; | |||
2564 | ||||
2565 | return isl_stat_ok; | |||
2566 | } | |||
2567 | ||||
2568 | /* Check if fn(map, user) returns true for all maps "map" in umap. | |||
2569 | */ | |||
2570 | static isl_bool union_map_forall_user(__isl_keep isl_union_map *umap, | |||
2571 | isl_bool (*fn)(__isl_keep isl_map *map, void *user), void *user) | |||
2572 | { | |||
2573 | struct isl_forall_user_data data = { isl_bool_true, fn, user }; | |||
2574 | ||||
2575 | if (!umap) | |||
2576 | return isl_bool_error; | |||
2577 | ||||
2578 | if (isl_hash_table_foreach(umap->dim->ctx, &umap->table, | |||
2579 | &forall_user_entry, &data) < 0 && data.res) | |||
2580 | return isl_bool_error; | |||
2581 | ||||
2582 | return data.res; | |||
2583 | } | |||
2584 | ||||
2585 | /* Is "umap" obviously empty? | |||
2586 | */ | |||
2587 | isl_bool isl_union_map_plain_is_empty(__isl_keep isl_union_map *umap) | |||
2588 | { | |||
2589 | if (!umap) | |||
2590 | return isl_bool_error; | |||
2591 | return isl_union_map_n_map(umap) == 0; | |||
2592 | } | |||
2593 | ||||
2594 | isl_bool isl_union_map_is_empty(__isl_keep isl_union_map *umap) | |||
2595 | { | |||
2596 | return union_map_forall(umap, &isl_map_is_empty); | |||
2597 | } | |||
2598 | ||||
2599 | isl_bool isl_union_set_is_empty(__isl_keep isl_union_setisl_union_map *uset) | |||
2600 | { | |||
2601 | return isl_union_map_is_empty(uset); | |||
2602 | } | |||
2603 | ||||
2604 | static isl_bool is_subset_of_identity(__isl_keep isl_map *map) | |||
2605 | { | |||
2606 | isl_bool is_subset; | |||
2607 | isl_space *dim; | |||
2608 | isl_map *id; | |||
2609 | ||||
2610 | if (!map) | |||
2611 | return isl_bool_error; | |||
2612 | ||||
2613 | if (!isl_space_tuple_is_equal(map->dim, isl_dim_in, | |||
2614 | map->dim, isl_dim_out)) | |||
2615 | return isl_bool_false; | |||
2616 | ||||
2617 | dim = isl_map_get_space(map); | |||
2618 | id = isl_map_identity(dim); | |||
2619 | ||||
2620 | is_subset = isl_map_is_subset(map, id); | |||
2621 | ||||
2622 | isl_map_free(id); | |||
2623 | ||||
2624 | return is_subset; | |||
2625 | } | |||
2626 | ||||
2627 | /* Given an isl_union_map that consists of a single map, check | |||
2628 | * if it is single-valued. | |||
2629 | */ | |||
2630 | static isl_bool single_map_is_single_valued(__isl_keep isl_union_map *umap) | |||
2631 | { | |||
2632 | isl_map *map; | |||
2633 | isl_bool sv; | |||
2634 | ||||
2635 | umap = isl_union_map_copy(umap); | |||
2636 | map = isl_map_from_union_map(umap); | |||
2637 | sv = isl_map_is_single_valued(map); | |||
2638 | isl_map_free(map); | |||
2639 | ||||
2640 | return sv; | |||
2641 | } | |||
2642 | ||||
2643 | /* Internal data structure for single_valued_on_domain. | |||
2644 | * | |||
2645 | * "umap" is the union map to be tested. | |||
2646 | * "sv" is set to 1 as long as "umap" may still be single-valued. | |||
2647 | */ | |||
2648 | struct isl_union_map_is_sv_data { | |||
2649 | isl_union_map *umap; | |||
2650 | isl_bool sv; | |||
2651 | }; | |||
2652 | ||||
2653 | /* Check if the data->umap is single-valued on "set". | |||
2654 | * | |||
2655 | * If data->umap consists of a single map on "set", then test it | |||
2656 | * as an isl_map. | |||
2657 | * | |||
2658 | * Otherwise, compute | |||
2659 | * | |||
2660 | * M \circ M^-1 | |||
2661 | * | |||
2662 | * check if the result is a subset of the identity mapping and | |||
2663 | * store the result in data->sv. | |||
2664 | * | |||
2665 | * Terminate as soon as data->umap has been determined not to | |||
2666 | * be single-valued. | |||
2667 | */ | |||
2668 | static isl_stat single_valued_on_domain(__isl_take isl_setisl_map *set, void *user) | |||
2669 | { | |||
2670 | struct isl_union_map_is_sv_data *data = user; | |||
2671 | isl_union_map *umap, *test; | |||
2672 | ||||
2673 | umap = isl_union_map_copy(data->umap); | |||
2674 | umap = isl_union_map_intersect_domain(umap, | |||
2675 | isl_union_set_from_set(set)); | |||
2676 | ||||
2677 | if (isl_union_map_n_map(umap) == 1) { | |||
2678 | data->sv = single_map_is_single_valued(umap); | |||
2679 | isl_union_map_free(umap); | |||
2680 | } else { | |||
2681 | test = isl_union_map_reverse(isl_union_map_copy(umap)); | |||
2682 | test = isl_union_map_apply_range(test, umap); | |||
2683 | ||||
2684 | data->sv = union_map_forall(test, &is_subset_of_identity); | |||
2685 | ||||
2686 | isl_union_map_free(test); | |||
2687 | } | |||
2688 | ||||
2689 | if (data->sv < 0 || !data->sv) | |||
2690 | return isl_stat_error; | |||
2691 | return isl_stat_ok; | |||
2692 | } | |||
2693 | ||||
2694 | /* Check if the given map is single-valued. | |||
2695 | * | |||
2696 | * If the union map consists of a single map, then test it as an isl_map. | |||
2697 | * Otherwise, check if the union map is single-valued on each of its | |||
2698 | * domain spaces. | |||
2699 | */ | |||
2700 | isl_bool isl_union_map_is_single_valued(__isl_keep isl_union_map *umap) | |||
2701 | { | |||
2702 | isl_union_map *universe; | |||
2703 | isl_union_setisl_union_map *domain; | |||
2704 | struct isl_union_map_is_sv_data data; | |||
2705 | ||||
2706 | if (isl_union_map_n_map(umap) == 1) | |||
2707 | return single_map_is_single_valued(umap); | |||
2708 | ||||
2709 | universe = isl_union_map_universe(isl_union_map_copy(umap)); | |||
2710 | domain = isl_union_map_domain(universe); | |||
2711 | ||||
2712 | data.sv = isl_bool_true; | |||
2713 | data.umap = umap; | |||
2714 | if (isl_union_set_foreach_set(domain, | |||
2715 | &single_valued_on_domain, &data) < 0 && data.sv) | |||
2716 | data.sv = isl_bool_error; | |||
2717 | isl_union_set_free(domain); | |||
2718 | ||||
2719 | return data.sv; | |||
2720 | } | |||
2721 | ||||
2722 | isl_bool isl_union_map_is_injective(__isl_keep isl_union_map *umap) | |||
2723 | { | |||
2724 | isl_bool in; | |||
2725 | ||||
2726 | umap = isl_union_map_copy(umap); | |||
2727 | umap = isl_union_map_reverse(umap); | |||
2728 | in = isl_union_map_is_single_valued(umap); | |||
2729 | isl_union_map_free(umap); | |||
2730 | ||||
2731 | return in; | |||
2732 | } | |||
2733 | ||||
2734 | /* Is "map" obviously not an identity relation because | |||
2735 | * it maps elements from one space to another space? | |||
2736 | * Update *non_identity accordingly. | |||
2737 | * | |||
2738 | * In particular, if the domain and range spaces are the same, | |||
2739 | * then the map is not considered to obviously not be an identity relation. | |||
2740 | * Otherwise, the map is considered to obviously not be an identity relation | |||
2741 | * if it is is non-empty. | |||
2742 | * | |||
2743 | * If "map" is determined to obviously not be an identity relation, | |||
2744 | * then the search is aborted. | |||
2745 | */ | |||
2746 | static isl_stat map_plain_is_not_identity(__isl_take isl_map *map, void *user) | |||
2747 | { | |||
2748 | isl_bool *non_identity = user; | |||
2749 | isl_bool equal; | |||
2750 | isl_space *space; | |||
2751 | ||||
2752 | space = isl_map_get_space(map); | |||
2753 | equal = isl_space_tuple_is_equal(space, isl_dim_in, space, isl_dim_out); | |||
2754 | if (equal >= 0 && !equal) | |||
2755 | *non_identity = isl_bool_not(isl_map_is_empty(map)); | |||
2756 | else | |||
2757 | *non_identity = isl_bool_not(equal); | |||
2758 | isl_space_free(space); | |||
2759 | isl_map_free(map); | |||
2760 | ||||
2761 | if (*non_identity < 0 || *non_identity) | |||
2762 | return isl_stat_error; | |||
2763 | ||||
2764 | return isl_stat_ok; | |||
2765 | } | |||
2766 | ||||
2767 | /* Is "umap" obviously not an identity relation because | |||
2768 | * it maps elements from one space to another space? | |||
2769 | * | |||
2770 | * As soon as a map has been found that maps elements to a different space, | |||
2771 | * non_identity is changed and the search is aborted. | |||
2772 | */ | |||
2773 | static isl_bool isl_union_map_plain_is_not_identity( | |||
2774 | __isl_keep isl_union_map *umap) | |||
2775 | { | |||
2776 | isl_bool non_identity; | |||
2777 | ||||
2778 | non_identity = isl_bool_false; | |||
2779 | if (isl_union_map_foreach_map(umap, &map_plain_is_not_identity, | |||
2780 | &non_identity) < 0 && | |||
2781 | non_identity == isl_bool_false) | |||
2782 | return isl_bool_error; | |||
2783 | ||||
2784 | return non_identity; | |||
2785 | } | |||
2786 | ||||
2787 | /* Does "map" only map elements to themselves? | |||
2788 | * Update *identity accordingly. | |||
2789 | * | |||
2790 | * If "map" is determined not to be an identity relation, | |||
2791 | * then the search is aborted. | |||
2792 | */ | |||
2793 | static isl_stat map_is_identity(__isl_take isl_map *map, void *user) | |||
2794 | { | |||
2795 | isl_bool *identity = user; | |||
2796 | ||||
2797 | *identity = isl_map_is_identity(map); | |||
2798 | isl_map_free(map); | |||
2799 | ||||
2800 | if (*identity < 0 || !*identity) | |||
2801 | return isl_stat_error; | |||
2802 | ||||
2803 | return isl_stat_ok; | |||
2804 | } | |||
2805 | ||||
2806 | /* Does "umap" only map elements to themselves? | |||
2807 | * | |||
2808 | * First check if there are any maps that map elements to different spaces. | |||
2809 | * If not, then check that all the maps (between identical spaces) | |||
2810 | * are identity relations. | |||
2811 | */ | |||
2812 | isl_bool isl_union_map_is_identity(__isl_keep isl_union_map *umap) | |||
2813 | { | |||
2814 | isl_bool non_identity; | |||
2815 | isl_bool identity; | |||
2816 | ||||
2817 | non_identity = isl_union_map_plain_is_not_identity(umap); | |||
2818 | if (non_identity < 0 || non_identity) | |||
2819 | return isl_bool_not(non_identity); | |||
2820 | ||||
2821 | identity = isl_bool_true; | |||
2822 | if (isl_union_map_foreach_map(umap, &map_is_identity, &identity) < 0 && | |||
2823 | identity == isl_bool_true) | |||
2824 | return isl_bool_error; | |||
2825 | ||||
2826 | return identity; | |||
2827 | } | |||
2828 | ||||
2829 | /* Represents a map that has a fixed value (v) for one of its | |||
2830 | * range dimensions. | |||
2831 | * The map in this structure is not reference counted, so it | |||
2832 | * is only valid while the isl_union_map from which it was | |||
2833 | * obtained is still alive. | |||
2834 | */ | |||
2835 | struct isl_fixed_map { | |||
2836 | isl_int v; | |||
2837 | isl_map *map; | |||
2838 | }; | |||
2839 | ||||
2840 | static struct isl_fixed_map *alloc_isl_fixed_map_array(isl_ctx *ctx, | |||
2841 | int n) | |||
2842 | { | |||
2843 | int i; | |||
2844 | struct isl_fixed_map *v; | |||
2845 | ||||
2846 | v = isl_calloc_array(ctx, struct isl_fixed_map, n)((struct isl_fixed_map *)isl_calloc_or_die(ctx, n, sizeof(struct isl_fixed_map))); | |||
2847 | if (!v) | |||
2848 | return NULL((void*)0); | |||
2849 | for (i = 0; i < n; ++i) | |||
2850 | isl_int_init(v[i].v)isl_sioimath_init((v[i].v)); | |||
2851 | return v; | |||
2852 | } | |||
2853 | ||||
2854 | static void free_isl_fixed_map_array(struct isl_fixed_map *v, int n) | |||
2855 | { | |||
2856 | int i; | |||
2857 | ||||
2858 | if (!v) | |||
2859 | return; | |||
2860 | for (i = 0; i < n; ++i) | |||
2861 | isl_int_clear(v[i].v)isl_sioimath_clear((v[i].v)); | |||
2862 | free(v); | |||
2863 | } | |||
2864 | ||||
2865 | /* Compare the "v" field of two isl_fixed_map structs. | |||
2866 | */ | |||
2867 | static int qsort_fixed_map_cmp(const void *p1, const void *p2) | |||
2868 | { | |||
2869 | const struct isl_fixed_map *e1 = (const struct isl_fixed_map *) p1; | |||
2870 | const struct isl_fixed_map *e2 = (const struct isl_fixed_map *) p2; | |||
2871 | ||||
2872 | return isl_int_cmp(e1->v, e2->v)isl_sioimath_cmp(*(e1->v), *(e2->v)); | |||
2873 | } | |||
2874 | ||||
2875 | /* Internal data structure used while checking whether all maps | |||
2876 | * in a union_map have a fixed value for a given output dimension. | |||
2877 | * v is the list of maps, with the fixed value for the dimension | |||
2878 | * n is the number of maps considered so far | |||
2879 | * pos is the output dimension under investigation | |||
2880 | */ | |||
2881 | struct isl_fixed_dim_data { | |||
2882 | struct isl_fixed_map *v; | |||
2883 | int n; | |||
2884 | int pos; | |||
2885 | }; | |||
2886 | ||||
2887 | static isl_bool fixed_at_pos(__isl_keep isl_map *map, void *user) | |||
2888 | { | |||
2889 | struct isl_fixed_dim_data *data = user; | |||
2890 | ||||
2891 | data->v[data->n].map = map; | |||
2892 | return isl_map_plain_is_fixed(map, isl_dim_out, data->pos, | |||
2893 | &data->v[data->n++].v); | |||
2894 | } | |||
2895 | ||||
2896 | static isl_bool plain_injective_on_range(__isl_take isl_union_map *umap, | |||
2897 | int first, int n_range); | |||
2898 | ||||
2899 | /* Given a list of the maps, with their fixed values at output dimension "pos", | |||
2900 | * check whether the ranges of the maps form an obvious partition. | |||
2901 | * | |||
2902 | * We first sort the maps according to their fixed values. | |||
2903 | * If all maps have a different value, then we know the ranges form | |||
2904 | * a partition. | |||
2905 | * Otherwise, we collect the maps with the same fixed value and | |||
2906 | * check whether each such collection is obviously injective | |||
2907 | * based on later dimensions. | |||
2908 | */ | |||
2909 | static int separates(struct isl_fixed_map *v, int n, | |||
2910 | __isl_take isl_space *dim, int pos, int n_range) | |||
2911 | { | |||
2912 | int i; | |||
2913 | ||||
2914 | if (!v) | |||
2915 | goto error; | |||
2916 | ||||
2917 | qsort(v, n, sizeof(*v), &qsort_fixed_map_cmp); | |||
2918 | ||||
2919 | for (i = 0; i + 1 < n; ++i) { | |||
2920 | int j, k; | |||
2921 | isl_union_map *part; | |||
2922 | int injective; | |||
2923 | ||||
2924 | for (j = i + 1; j < n; ++j) | |||
2925 | if (isl_int_ne(v[i].v, v[j].v)(isl_sioimath_cmp(*(v[i].v), *(v[j].v)) != 0)) | |||
2926 | break; | |||
2927 | ||||
2928 | if (j == i + 1) | |||
2929 | continue; | |||
2930 | ||||
2931 | part = isl_union_map_alloc(isl_space_copy(dim), j - i); | |||
2932 | for (k = i; k < j; ++k) | |||
2933 | part = isl_union_map_add_map(part, | |||
2934 | isl_map_copy(v[k].map)); | |||
2935 | ||||
2936 | injective = plain_injective_on_range(part, pos + 1, n_range); | |||
2937 | if (injective < 0) | |||
2938 | goto error; | |||
2939 | if (!injective) | |||
2940 | break; | |||
2941 | ||||
2942 | i = j - 1; | |||
2943 | } | |||
2944 | ||||
2945 | isl_space_free(dim); | |||
2946 | free_isl_fixed_map_array(v, n); | |||
2947 | return i + 1 >= n; | |||
2948 | error: | |||
2949 | isl_space_free(dim); | |||
2950 | free_isl_fixed_map_array(v, n); | |||
2951 | return -1; | |||
2952 | } | |||
2953 | ||||
2954 | /* Check whether the maps in umap have obviously distinct ranges. | |||
2955 | * In particular, check for an output dimension in the range | |||
2956 | * [first,n_range) for which all maps have a fixed value | |||
2957 | * and then check if these values, possibly along with fixed values | |||
2958 | * at later dimensions, entail distinct ranges. | |||
2959 | */ | |||
2960 | static isl_bool plain_injective_on_range(__isl_take isl_union_map *umap, | |||
2961 | int first, int n_range) | |||
2962 | { | |||
2963 | isl_ctx *ctx; | |||
2964 | int n; | |||
2965 | struct isl_fixed_dim_data data = { NULL((void*)0) }; | |||
2966 | ||||
2967 | ctx = isl_union_map_get_ctx(umap); | |||
2968 | ||||
2969 | n = isl_union_map_n_map(umap); | |||
2970 | if (!umap) | |||
2971 | goto error; | |||
2972 | ||||
2973 | if (n <= 1) { | |||
2974 | isl_union_map_free(umap); | |||
2975 | return isl_bool_true; | |||
2976 | } | |||
2977 | ||||
2978 | if (first >= n_range) { | |||
2979 | isl_union_map_free(umap); | |||
2980 | return isl_bool_false; | |||
2981 | } | |||
2982 | ||||
2983 | data.v = alloc_isl_fixed_map_array(ctx, n); | |||
2984 | if (!data.v) | |||
2985 | goto error; | |||
2986 | ||||
2987 | for (data.pos = first; data.pos < n_range; ++data.pos) { | |||
2988 | isl_bool fixed; | |||
2989 | int injective; | |||
2990 | isl_space *dim; | |||
2991 | ||||
2992 | data.n = 0; | |||
2993 | fixed = union_map_forall_user(umap, &fixed_at_pos, &data); | |||
2994 | if (fixed < 0) | |||
2995 | goto error; | |||
2996 | if (!fixed) | |||
2997 | continue; | |||
2998 | dim = isl_union_map_get_space(umap); | |||
2999 | injective = separates(data.v, n, dim, data.pos, n_range); | |||
3000 | isl_union_map_free(umap); | |||
3001 | return injective; | |||
3002 | } | |||
3003 | ||||
3004 | free_isl_fixed_map_array(data.v, n); | |||
3005 | isl_union_map_free(umap); | |||
3006 | ||||
3007 | return isl_bool_false; | |||
3008 | error: | |||
3009 | free_isl_fixed_map_array(data.v, n); | |||
3010 | isl_union_map_free(umap); | |||
3011 | return isl_bool_error; | |||
3012 | } | |||
3013 | ||||
3014 | /* Check whether the maps in umap that map to subsets of "ran" | |||
3015 | * have obviously distinct ranges. | |||
3016 | */ | |||
3017 | static isl_bool plain_injective_on_range_wrap(__isl_keep isl_setisl_map *ran, | |||
3018 | void *user) | |||
3019 | { | |||
3020 | isl_union_map *umap = user; | |||
3021 | ||||
3022 | umap = isl_union_map_copy(umap); | |||
3023 | umap = isl_union_map_intersect_range(umap, | |||
3024 | isl_union_set_from_set(isl_set_copy(ran))); | |||
3025 | return plain_injective_on_range(umap, 0, isl_set_dim(ran, isl_dim_set)); | |||
3026 | } | |||
3027 | ||||
3028 | /* Check if the given union_map is obviously injective. | |||
3029 | * | |||
3030 | * In particular, we first check if all individual maps are obviously | |||
3031 | * injective and then check if all the ranges of these maps are | |||
3032 | * obviously disjoint. | |||
3033 | */ | |||
3034 | isl_bool isl_union_map_plain_is_injective(__isl_keep isl_union_map *umap) | |||
3035 | { | |||
3036 | isl_bool in; | |||
3037 | isl_union_map *univ; | |||
3038 | isl_union_setisl_union_map *ran; | |||
3039 | ||||
3040 | in = union_map_forall(umap, &isl_map_plain_is_injective); | |||
3041 | if (in < 0) | |||
3042 | return isl_bool_error; | |||
3043 | if (!in) | |||
3044 | return isl_bool_false; | |||
3045 | ||||
3046 | univ = isl_union_map_universe(isl_union_map_copy(umap)); | |||
3047 | ran = isl_union_map_range(univ); | |||
3048 | ||||
3049 | in = union_map_forall_user(ran, &plain_injective_on_range_wrap, umap); | |||
3050 | ||||
3051 | isl_union_set_free(ran); | |||
3052 | ||||
3053 | return in; | |||
3054 | } | |||
3055 | ||||
3056 | isl_bool isl_union_map_is_bijective(__isl_keep isl_union_map *umap) | |||
3057 | { | |||
3058 | isl_bool sv; | |||
3059 | ||||
3060 | sv = isl_union_map_is_single_valued(umap); | |||
3061 | if (sv < 0 || !sv) | |||
3062 | return sv; | |||
3063 | ||||
3064 | return isl_union_map_is_injective(umap); | |||
3065 | } | |||
3066 | ||||
3067 | __isl_give isl_union_map *isl_union_map_zip(__isl_take isl_union_map *umap) | |||
3068 | { | |||
3069 | struct isl_un_op_drop_user_data data = { &isl_map_can_zip }; | |||
3070 | struct isl_un_op_control control = { | |||
3071 | .filter = &un_op_filter_drop_user, | |||
3072 | .filter_user = &data, | |||
3073 | .fn_map = &isl_map_zip, | |||
3074 | }; | |||
3075 | return un_op(umap, &control); | |||
3076 | } | |||
3077 | ||||
3078 | /* Given a union map, take the maps of the form A -> (B -> C) and | |||
3079 | * return the union of the corresponding maps (A -> B) -> C. | |||
3080 | */ | |||
3081 | __isl_give isl_union_map *isl_union_map_uncurry(__isl_take isl_union_map *umap) | |||
3082 | { | |||
3083 | struct isl_un_op_drop_user_data data = { &isl_map_can_uncurry }; | |||
3084 | struct isl_un_op_control control = { | |||
3085 | .filter = &un_op_filter_drop_user, | |||
3086 | .filter_user = &data, | |||
3087 | .fn_map = &isl_map_uncurry, | |||
3088 | }; | |||
3089 | return un_op(umap, &control); | |||
3090 | } | |||
3091 | ||||
3092 | /* Given a union map, take the maps of the form (A -> B) -> C and | |||
3093 | * return the union of the corresponding maps A -> (B -> C). | |||
3094 | */ | |||
3095 | __isl_give isl_union_map *isl_union_map_curry(__isl_take isl_union_map *umap) | |||
3096 | { | |||
3097 | struct isl_un_op_drop_user_data data = { &isl_map_can_curry }; | |||
3098 | struct isl_un_op_control control = { | |||
3099 | .filter = &un_op_filter_drop_user, | |||
3100 | .filter_user = &data, | |||
3101 | .fn_map = &isl_map_curry, | |||
3102 | }; | |||
3103 | return un_op(umap, &control); | |||
3104 | } | |||
3105 | ||||
3106 | /* Given a union map, take the maps of the form A -> ((B -> C) -> D) and | |||
3107 | * return the union of the corresponding maps A -> (B -> (C -> D)). | |||
3108 | */ | |||
3109 | __isl_give isl_union_map *isl_union_map_range_curry( | |||
3110 | __isl_take isl_union_map *umap) | |||
3111 | { | |||
3112 | struct isl_un_op_drop_user_data data = { &isl_map_can_range_curry }; | |||
3113 | struct isl_un_op_control control = { | |||
3114 | .filter = &un_op_filter_drop_user, | |||
3115 | .filter_user = &data, | |||
3116 | .fn_map = &isl_map_range_curry, | |||
3117 | }; | |||
3118 | return un_op(umap, &control); | |||
3119 | } | |||
3120 | ||||
3121 | __isl_give isl_union_setisl_union_map *isl_union_set_lift(__isl_take isl_union_setisl_union_map *uset) | |||
3122 | { | |||
3123 | struct isl_un_op_control control = { | |||
3124 | .fn_map = &isl_set_lift, | |||
3125 | }; | |||
3126 | return un_op(uset, &control); | |||
3127 | } | |||
3128 | ||||
3129 | static isl_stat coefficients_entry(void **entry, void *user) | |||
3130 | { | |||
3131 | isl_setisl_map *set = *entry; | |||
3132 | isl_union_setisl_union_map **res = user; | |||
3133 | ||||
3134 | set = isl_set_copy(set); | |||
3135 | set = isl_set_from_basic_set(isl_set_coefficients(set)); | |||
3136 | *res = isl_union_set_add_set(*res, set); | |||
3137 | ||||
3138 | return isl_stat_ok; | |||
3139 | } | |||
3140 | ||||
3141 | __isl_give isl_union_setisl_union_map *isl_union_set_coefficients( | |||
3142 | __isl_take isl_union_setisl_union_map *uset) | |||
3143 | { | |||
3144 | isl_ctx *ctx; | |||
3145 | isl_space *dim; | |||
3146 | isl_union_setisl_union_map *res; | |||
3147 | ||||
3148 | if (!uset) | |||
3149 | return NULL((void*)0); | |||
3150 | ||||
3151 | ctx = isl_union_set_get_ctx(uset); | |||
3152 | dim = isl_space_set_alloc(ctx, 0, 0); | |||
3153 | res = isl_union_map_alloc(dim, uset->table.n); | |||
3154 | if (isl_hash_table_foreach(uset->dim->ctx, &uset->table, | |||
3155 | &coefficients_entry, &res) < 0) | |||
3156 | goto error; | |||
3157 | ||||
3158 | isl_union_set_free(uset); | |||
3159 | return res; | |||
3160 | error: | |||
3161 | isl_union_set_free(uset); | |||
3162 | isl_union_set_free(res); | |||
3163 | return NULL((void*)0); | |||
3164 | } | |||
3165 | ||||
3166 | static isl_stat solutions_entry(void **entry, void *user) | |||
3167 | { | |||
3168 | isl_setisl_map *set = *entry; | |||
3169 | isl_union_setisl_union_map **res = user; | |||
3170 | ||||
3171 | set = isl_set_copy(set); | |||
3172 | set = isl_set_from_basic_set(isl_set_solutions(set)); | |||
3173 | if (!*res) | |||
3174 | *res = isl_union_set_from_set(set); | |||
3175 | else | |||
3176 | *res = isl_union_set_add_set(*res, set); | |||
3177 | ||||
3178 | if (!*res) | |||
3179 | return isl_stat_error; | |||
3180 | ||||
3181 | return isl_stat_ok; | |||
3182 | } | |||
3183 | ||||
3184 | __isl_give isl_union_setisl_union_map *isl_union_set_solutions( | |||
3185 | __isl_take isl_union_setisl_union_map *uset) | |||
3186 | { | |||
3187 | isl_union_setisl_union_map *res = NULL((void*)0); | |||
3188 | ||||
3189 | if (!uset) | |||
3190 | return NULL((void*)0); | |||
3191 | ||||
3192 | if (uset->table.n == 0) { | |||
3193 | res = isl_union_set_empty(isl_union_set_get_space(uset)); | |||
3194 | isl_union_set_free(uset); | |||
3195 | return res; | |||
3196 | } | |||
3197 | ||||
3198 | if (isl_hash_table_foreach(uset->dim->ctx, &uset->table, | |||
3199 | &solutions_entry, &res) < 0) | |||
3200 | goto error; | |||
3201 | ||||
3202 | isl_union_set_free(uset); | |||
3203 | return res; | |||
3204 | error: | |||
3205 | isl_union_set_free(uset); | |||
3206 | isl_union_set_free(res); | |||
3207 | return NULL((void*)0); | |||
3208 | } | |||
3209 | ||||
3210 | /* Is the domain space of "map" equal to "space"? | |||
3211 | */ | |||
3212 | static int domain_match(__isl_keep isl_map *map, __isl_keep isl_space *space) | |||
3213 | { | |||
3214 | return isl_space_tuple_is_equal(map->dim, isl_dim_in, | |||
3215 | space, isl_dim_out); | |||
3216 | } | |||
3217 | ||||
3218 | /* Is the range space of "map" equal to "space"? | |||
3219 | */ | |||
3220 | static int range_match(__isl_keep isl_map *map, __isl_keep isl_space *space) | |||
3221 | { | |||
3222 | return isl_space_tuple_is_equal(map->dim, isl_dim_out, | |||
3223 | space, isl_dim_out); | |||
3224 | } | |||
3225 | ||||
3226 | /* Is the set space of "map" equal to "space"? | |||
3227 | */ | |||
3228 | static int set_match(__isl_keep isl_map *map, __isl_keep isl_space *space) | |||
3229 | { | |||
3230 | return isl_space_tuple_is_equal(map->dim, isl_dim_set, | |||
3231 | space, isl_dim_out); | |||
3232 | } | |||
3233 | ||||
3234 | /* Internal data structure for preimage_pw_multi_aff. | |||
3235 | * | |||
3236 | * "pma" is the function under which the preimage should be taken. | |||
3237 | * "space" is the space of "pma". | |||
3238 | * "res" collects the results. | |||
3239 | * "fn" computes the preimage for a given map. | |||
3240 | * "match" returns true if "fn" can be called. | |||
3241 | */ | |||
3242 | struct isl_union_map_preimage_data { | |||
3243 | isl_space *space; | |||
3244 | isl_pw_multi_aff *pma; | |||
3245 | isl_union_map *res; | |||
3246 | int (*match)(__isl_keep isl_map *map, __isl_keep isl_space *space); | |||
3247 | __isl_give isl_map *(*fn)(__isl_take isl_map *map, | |||
3248 | __isl_take isl_pw_multi_aff *pma); | |||
3249 | }; | |||
3250 | ||||
3251 | /* Call data->fn to compute the preimage of the domain or range of *entry | |||
3252 | * under the function represented by data->pma, provided the domain/range | |||
3253 | * space of *entry matches the target space of data->pma | |||
3254 | * (as given by data->match), and add the result to data->res. | |||
3255 | */ | |||
3256 | static isl_stat preimage_entry(void **entry, void *user) | |||
3257 | { | |||
3258 | int m; | |||
3259 | isl_map *map = *entry; | |||
3260 | struct isl_union_map_preimage_data *data = user; | |||
3261 | isl_bool empty; | |||
3262 | ||||
3263 | m = data->match(map, data->space); | |||
3264 | if (m < 0) | |||
3265 | return isl_stat_error; | |||
3266 | if (!m) | |||
3267 | return isl_stat_ok; | |||
3268 | ||||
3269 | map = isl_map_copy(map); | |||
3270 | map = data->fn(map, isl_pw_multi_aff_copy(data->pma)); | |||
3271 | ||||
3272 | empty = isl_map_is_empty(map); | |||
3273 | if (empty < 0 || empty) { | |||
3274 | isl_map_free(map); | |||
3275 | return empty < 0 ? isl_stat_error : isl_stat_ok; | |||
3276 | } | |||
3277 | ||||
3278 | data->res = isl_union_map_add_map(data->res, map); | |||
3279 | ||||
3280 | return isl_stat_ok; | |||
3281 | } | |||
3282 | ||||
3283 | /* Compute the preimage of the domain or range of "umap" under the function | |||
3284 | * represented by "pma". | |||
3285 | * In other words, plug in "pma" in the domain or range of "umap". | |||
3286 | * The function "fn" performs the actual preimage computation on a map, | |||
3287 | * while "match" determines to which maps the function should be applied. | |||
3288 | */ | |||
3289 | static __isl_give isl_union_map *preimage_pw_multi_aff( | |||
3290 | __isl_take isl_union_map *umap, __isl_take isl_pw_multi_aff *pma, | |||
3291 | int (*match)(__isl_keep isl_map *map, __isl_keep isl_space *space), | |||
3292 | __isl_give isl_map *(*fn)(__isl_take isl_map *map, | |||
3293 | __isl_take isl_pw_multi_aff *pma)) | |||
3294 | { | |||
3295 | isl_ctx *ctx; | |||
3296 | isl_space *space; | |||
3297 | struct isl_union_map_preimage_data data; | |||
3298 | ||||
3299 | umap = isl_union_map_align_params(umap, | |||
3300 | isl_pw_multi_aff_get_space(pma)); | |||
3301 | pma = isl_pw_multi_aff_align_params(pma, isl_union_map_get_space(umap)); | |||
3302 | ||||
3303 | if (!umap || !pma) | |||
3304 | goto error; | |||
3305 | ||||
3306 | ctx = isl_union_map_get_ctx(umap); | |||
3307 | space = isl_union_map_get_space(umap); | |||
3308 | data.space = isl_pw_multi_aff_get_space(pma); | |||
3309 | data.pma = pma; | |||
3310 | data.res = isl_union_map_alloc(space, umap->table.n); | |||
3311 | data.match = match; | |||
3312 | data.fn = fn; | |||
3313 | if (isl_hash_table_foreach(ctx, &umap->table, &preimage_entry, | |||
3314 | &data) < 0) | |||
3315 | data.res = isl_union_map_free(data.res); | |||
3316 | ||||
3317 | isl_space_free(data.space); | |||
3318 | isl_union_map_free(umap); | |||
3319 | isl_pw_multi_aff_free(pma); | |||
3320 | return data.res; | |||
3321 | error: | |||
3322 | isl_union_map_free(umap); | |||
3323 | isl_pw_multi_aff_free(pma); | |||
3324 | return NULL((void*)0); | |||
3325 | } | |||
3326 | ||||
3327 | /* Compute the preimage of the domain of "umap" under the function | |||
3328 | * represented by "pma". | |||
3329 | * In other words, plug in "pma" in the domain of "umap". | |||
3330 | * The result contains maps that live in the same spaces as the maps of "umap" | |||
3331 | * with domain space equal to the target space of "pma", | |||
3332 | * except that the domain has been replaced by the domain space of "pma". | |||
3333 | */ | |||
3334 | __isl_give isl_union_map *isl_union_map_preimage_domain_pw_multi_aff( | |||
3335 | __isl_take isl_union_map *umap, __isl_take isl_pw_multi_aff *pma) | |||
3336 | { | |||
3337 | return preimage_pw_multi_aff(umap, pma, &domain_match, | |||
3338 | &isl_map_preimage_domain_pw_multi_aff); | |||
3339 | } | |||
3340 | ||||
3341 | /* Compute the preimage of the range of "umap" under the function | |||
3342 | * represented by "pma". | |||
3343 | * In other words, plug in "pma" in the range of "umap". | |||
3344 | * The result contains maps that live in the same spaces as the maps of "umap" | |||
3345 | * with range space equal to the target space of "pma", | |||
3346 | * except that the range has been replaced by the domain space of "pma". | |||
3347 | */ | |||
3348 | __isl_give isl_union_map *isl_union_map_preimage_range_pw_multi_aff( | |||
3349 | __isl_take isl_union_map *umap, __isl_take isl_pw_multi_aff *pma) | |||
3350 | { | |||
3351 | return preimage_pw_multi_aff(umap, pma, &range_match, | |||
3352 | &isl_map_preimage_range_pw_multi_aff); | |||
3353 | } | |||
3354 | ||||
3355 | /* Compute the preimage of "uset" under the function represented by "pma". | |||
3356 | * In other words, plug in "pma" in "uset". | |||
3357 | * The result contains sets that live in the same spaces as the sets of "uset" | |||
3358 | * with space equal to the target space of "pma", | |||
3359 | * except that the space has been replaced by the domain space of "pma". | |||
3360 | */ | |||
3361 | __isl_give isl_union_setisl_union_map *isl_union_set_preimage_pw_multi_aff( | |||
3362 | __isl_take isl_union_setisl_union_map *uset, __isl_take isl_pw_multi_aff *pma) | |||
3363 | { | |||
3364 | return preimage_pw_multi_aff(uset, pma, &set_match, | |||
3365 | &isl_set_preimage_pw_multi_aff); | |||
3366 | } | |||
3367 | ||||
3368 | /* Compute the preimage of the domain of "umap" under the function | |||
3369 | * represented by "ma". | |||
3370 | * In other words, plug in "ma" in the domain of "umap". | |||
3371 | * The result contains maps that live in the same spaces as the maps of "umap" | |||
3372 | * with domain space equal to the target space of "ma", | |||
3373 | * except that the domain has been replaced by the domain space of "ma". | |||
3374 | */ | |||
3375 | __isl_give isl_union_map *isl_union_map_preimage_domain_multi_aff( | |||
3376 | __isl_take isl_union_map *umap, __isl_take isl_multi_aff *ma) | |||
3377 | { | |||
3378 | return isl_union_map_preimage_domain_pw_multi_aff(umap, | |||
3379 | isl_pw_multi_aff_from_multi_aff(ma)); | |||
3380 | } | |||
3381 | ||||
3382 | /* Compute the preimage of the range of "umap" under the function | |||
3383 | * represented by "ma". | |||
3384 | * In other words, plug in "ma" in the range of "umap". | |||
3385 | * The result contains maps that live in the same spaces as the maps of "umap" | |||
3386 | * with range space equal to the target space of "ma", | |||
3387 | * except that the range has been replaced by the domain space of "ma". | |||
3388 | */ | |||
3389 | __isl_give isl_union_map *isl_union_map_preimage_range_multi_aff( | |||
3390 | __isl_take isl_union_map *umap, __isl_take isl_multi_aff *ma) | |||
3391 | { | |||
3392 | return isl_union_map_preimage_range_pw_multi_aff(umap, | |||
3393 | isl_pw_multi_aff_from_multi_aff(ma)); | |||
3394 | } | |||
3395 | ||||
3396 | /* Compute the preimage of "uset" under the function represented by "ma". | |||
3397 | * In other words, plug in "ma" in "uset". | |||
3398 | * The result contains sets that live in the same spaces as the sets of "uset" | |||
3399 | * with space equal to the target space of "ma", | |||
3400 | * except that the space has been replaced by the domain space of "ma". | |||
3401 | */ | |||
3402 | __isl_give isl_union_map *isl_union_set_preimage_multi_aff( | |||
3403 | __isl_take isl_union_setisl_union_map *uset, __isl_take isl_multi_aff *ma) | |||
3404 | { | |||
3405 | return isl_union_set_preimage_pw_multi_aff(uset, | |||
3406 | isl_pw_multi_aff_from_multi_aff(ma)); | |||
3407 | } | |||
3408 | ||||
3409 | /* Internal data structure for preimage_multi_pw_aff. | |||
3410 | * | |||
3411 | * "mpa" is the function under which the preimage should be taken. | |||
3412 | * "space" is the space of "mpa". | |||
3413 | * "res" collects the results. | |||
3414 | * "fn" computes the preimage for a given map. | |||
3415 | * "match" returns true if "fn" can be called. | |||
3416 | */ | |||
3417 | struct isl_union_map_preimage_mpa_data { | |||
3418 | isl_space *space; | |||
3419 | isl_multi_pw_aff *mpa; | |||
3420 | isl_union_map *res; | |||
3421 | int (*match)(__isl_keep isl_map *map, __isl_keep isl_space *space); | |||
3422 | __isl_give isl_map *(*fn)(__isl_take isl_map *map, | |||
3423 | __isl_take isl_multi_pw_aff *mpa); | |||
3424 | }; | |||
3425 | ||||
3426 | /* Call data->fn to compute the preimage of the domain or range of *entry | |||
3427 | * under the function represented by data->mpa, provided the domain/range | |||
3428 | * space of *entry matches the target space of data->mpa | |||
3429 | * (as given by data->match), and add the result to data->res. | |||
3430 | */ | |||
3431 | static isl_stat preimage_mpa_entry(void **entry, void *user) | |||
3432 | { | |||
3433 | int m; | |||
3434 | isl_map *map = *entry; | |||
3435 | struct isl_union_map_preimage_mpa_data *data = user; | |||
3436 | isl_bool empty; | |||
3437 | ||||
3438 | m = data->match(map, data->space); | |||
3439 | if (m < 0) | |||
3440 | return isl_stat_error; | |||
3441 | if (!m) | |||
3442 | return isl_stat_ok; | |||
3443 | ||||
3444 | map = isl_map_copy(map); | |||
3445 | map = data->fn(map, isl_multi_pw_aff_copy(data->mpa)); | |||
3446 | ||||
3447 | empty = isl_map_is_empty(map); | |||
3448 | if (empty < 0 || empty) { | |||
3449 | isl_map_free(map); | |||
3450 | return empty < 0 ? isl_stat_error : isl_stat_ok; | |||
3451 | } | |||
3452 | ||||
3453 | data->res = isl_union_map_add_map(data->res, map); | |||
3454 | ||||
3455 | return isl_stat_ok; | |||
3456 | } | |||
3457 | ||||
3458 | /* Compute the preimage of the domain or range of "umap" under the function | |||
3459 | * represented by "mpa". | |||
3460 | * In other words, plug in "mpa" in the domain or range of "umap". | |||
3461 | * The function "fn" performs the actual preimage computation on a map, | |||
3462 | * while "match" determines to which maps the function should be applied. | |||
3463 | */ | |||
3464 | static __isl_give isl_union_map *preimage_multi_pw_aff( | |||
3465 | __isl_take isl_union_map *umap, __isl_take isl_multi_pw_aff *mpa, | |||
3466 | int (*match)(__isl_keep isl_map *map, __isl_keep isl_space *space), | |||
3467 | __isl_give isl_map *(*fn)(__isl_take isl_map *map, | |||
3468 | __isl_take isl_multi_pw_aff *mpa)) | |||
3469 | { | |||
3470 | isl_ctx *ctx; | |||
3471 | isl_space *space; | |||
3472 | struct isl_union_map_preimage_mpa_data data; | |||
3473 | ||||
3474 | umap = isl_union_map_align_params(umap, | |||
3475 | isl_multi_pw_aff_get_space(mpa)); | |||
3476 | mpa = isl_multi_pw_aff_align_params(mpa, isl_union_map_get_space(umap)); | |||
3477 | ||||
3478 | if (!umap || !mpa) | |||
3479 | goto error; | |||
3480 | ||||
3481 | ctx = isl_union_map_get_ctx(umap); | |||
3482 | space = isl_union_map_get_space(umap); | |||
3483 | data.space = isl_multi_pw_aff_get_space(mpa); | |||
3484 | data.mpa = mpa; | |||
3485 | data.res = isl_union_map_alloc(space, umap->table.n); | |||
3486 | data.match = match; | |||
3487 | data.fn = fn; | |||
3488 | if (isl_hash_table_foreach(ctx, &umap->table, &preimage_mpa_entry, | |||
3489 | &data) < 0) | |||
3490 | data.res = isl_union_map_free(data.res); | |||
3491 | ||||
3492 | isl_space_free(data.space); | |||
3493 | isl_union_map_free(umap); | |||
3494 | isl_multi_pw_aff_free(mpa); | |||
3495 | return data.res; | |||
3496 | error: | |||
3497 | isl_union_map_free(umap); | |||
3498 | isl_multi_pw_aff_free(mpa); | |||
3499 | return NULL((void*)0); | |||
3500 | } | |||
3501 | ||||
3502 | /* Compute the preimage of the domain of "umap" under the function | |||
3503 | * represented by "mpa". | |||
3504 | * In other words, plug in "mpa" in the domain of "umap". | |||
3505 | * The result contains maps that live in the same spaces as the maps of "umap" | |||
3506 | * with domain space equal to the target space of "mpa", | |||
3507 | * except that the domain has been replaced by the domain space of "mpa". | |||
3508 | */ | |||
3509 | __isl_give isl_union_map *isl_union_map_preimage_domain_multi_pw_aff( | |||
3510 | __isl_take isl_union_map *umap, __isl_take isl_multi_pw_aff *mpa) | |||
3511 | { | |||
3512 | return preimage_multi_pw_aff(umap, mpa, &domain_match, | |||
3513 | &isl_map_preimage_domain_multi_pw_aff); | |||
3514 | } | |||
3515 | ||||
3516 | /* Internal data structure for preimage_upma. | |||
3517 | * | |||
3518 | * "umap" is the map of which the preimage should be computed. | |||
3519 | * "res" collects the results. | |||
3520 | * "fn" computes the preimage for a given piecewise multi-affine function. | |||
3521 | */ | |||
3522 | struct isl_union_map_preimage_upma_data { | |||
3523 | isl_union_map *umap; | |||
3524 | isl_union_map *res; | |||
3525 | __isl_give isl_union_map *(*fn)(__isl_take isl_union_map *umap, | |||
3526 | __isl_take isl_pw_multi_aff *pma); | |||
3527 | }; | |||
3528 | ||||
3529 | /* Call data->fn to compute the preimage of the domain or range of data->umap | |||
3530 | * under the function represented by pma and add the result to data->res. | |||
3531 | */ | |||
3532 | static isl_stat preimage_upma(__isl_take isl_pw_multi_aff *pma, void *user) | |||
3533 | { | |||
3534 | struct isl_union_map_preimage_upma_data *data = user; | |||
3535 | isl_union_map *umap; | |||
3536 | ||||
3537 | umap = isl_union_map_copy(data->umap); | |||
3538 | umap = data->fn(umap, pma); | |||
3539 | data->res = isl_union_map_union(data->res, umap); | |||
3540 | ||||
3541 | return data->res ? isl_stat_ok : isl_stat_error; | |||
3542 | } | |||
3543 | ||||
3544 | /* Compute the preimage of the domain or range of "umap" under the function | |||
3545 | * represented by "upma". | |||
3546 | * In other words, plug in "upma" in the domain or range of "umap". | |||
3547 | * The function "fn" performs the actual preimage computation | |||
3548 | * on a piecewise multi-affine function. | |||
3549 | */ | |||
3550 | static __isl_give isl_union_map *preimage_union_pw_multi_aff( | |||
3551 | __isl_take isl_union_map *umap, | |||
3552 | __isl_take isl_union_pw_multi_aff *upma, | |||
3553 | __isl_give isl_union_map *(*fn)(__isl_take isl_union_map *umap, | |||
3554 | __isl_take isl_pw_multi_aff *pma)) | |||
3555 | { | |||
3556 | struct isl_union_map_preimage_upma_data data; | |||
3557 | ||||
3558 | data.umap = umap; | |||
3559 | data.res = isl_union_map_empty(isl_union_map_get_space(umap)); | |||
3560 | data.fn = fn; | |||
3561 | if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma, | |||
3562 | &preimage_upma, &data) < 0) | |||
3563 | data.res = isl_union_map_free(data.res); | |||
3564 | ||||
3565 | isl_union_map_free(umap); | |||
3566 | isl_union_pw_multi_aff_free(upma); | |||
3567 | ||||
3568 | return data.res; | |||
3569 | } | |||
3570 | ||||
3571 | /* Compute the preimage of the domain of "umap" under the function | |||
3572 | * represented by "upma". | |||
3573 | * In other words, plug in "upma" in the domain of "umap". | |||
3574 | * The result contains maps that live in the same spaces as the maps of "umap" | |||
3575 | * with domain space equal to one of the target spaces of "upma", | |||
3576 | * except that the domain has been replaced by one of the domain spaces that | |||
3577 | * correspond to that target space of "upma". | |||
3578 | */ | |||
3579 | __isl_give isl_union_map *isl_union_map_preimage_domain_union_pw_multi_aff( | |||
3580 | __isl_take isl_union_map *umap, | |||
3581 | __isl_take isl_union_pw_multi_aff *upma) | |||
3582 | { | |||
3583 | return preimage_union_pw_multi_aff(umap, upma, | |||
3584 | &isl_union_map_preimage_domain_pw_multi_aff); | |||
3585 | } | |||
3586 | ||||
3587 | /* Compute the preimage of the range of "umap" under the function | |||
3588 | * represented by "upma". | |||
3589 | * In other words, plug in "upma" in the range of "umap". | |||
3590 | * The result contains maps that live in the same spaces as the maps of "umap" | |||
3591 | * with range space equal to one of the target spaces of "upma", | |||
3592 | * except that the range has been replaced by one of the domain spaces that | |||
3593 | * correspond to that target space of "upma". | |||
3594 | */ | |||
3595 | __isl_give isl_union_map *isl_union_map_preimage_range_union_pw_multi_aff( | |||
3596 | __isl_take isl_union_map *umap, | |||
3597 | __isl_take isl_union_pw_multi_aff *upma) | |||
3598 | { | |||
3599 | return preimage_union_pw_multi_aff(umap, upma, | |||
3600 | &isl_union_map_preimage_range_pw_multi_aff); | |||
3601 | } | |||
3602 | ||||
3603 | /* Compute the preimage of "uset" under the function represented by "upma". | |||
3604 | * In other words, plug in "upma" in the range of "uset". | |||
3605 | * The result contains sets that live in the same spaces as the sets of "uset" | |||
3606 | * with space equal to one of the target spaces of "upma", | |||
3607 | * except that the space has been replaced by one of the domain spaces that | |||
3608 | * correspond to that target space of "upma". | |||
3609 | */ | |||
3610 | __isl_give isl_union_setisl_union_map *isl_union_set_preimage_union_pw_multi_aff( | |||
3611 | __isl_take isl_union_setisl_union_map *uset, | |||
3612 | __isl_take isl_union_pw_multi_aff *upma) | |||
3613 | { | |||
3614 | return preimage_union_pw_multi_aff(uset, upma, | |||
3615 | &isl_union_set_preimage_pw_multi_aff); | |||
3616 | } | |||
3617 | ||||
3618 | /* Reset the user pointer on all identifiers of parameters and tuples | |||
3619 | * of the spaces of "umap". | |||
3620 | */ | |||
3621 | __isl_give isl_union_map *isl_union_map_reset_user( | |||
3622 | __isl_take isl_union_map *umap) | |||
3623 | { | |||
3624 | umap = isl_union_map_cow(umap); | |||
3625 | if (!umap) | |||
3626 | return NULL((void*)0); | |||
3627 | umap->dim = isl_space_reset_user(umap->dim); | |||
3628 | if (!umap->dim) | |||
3629 | return isl_union_map_free(umap); | |||
3630 | return total(umap, &isl_map_reset_user); | |||
3631 | } | |||
3632 | ||||
3633 | /* Reset the user pointer on all identifiers of parameters and tuples | |||
3634 | * of the spaces of "uset". | |||
3635 | */ | |||
3636 | __isl_give isl_union_setisl_union_map *isl_union_set_reset_user( | |||
3637 | __isl_take isl_union_setisl_union_map *uset) | |||
3638 | { | |||
3639 | return isl_union_map_reset_user(uset); | |||
3640 | } | |||
3641 | ||||
3642 | /* Remove all existentially quantified variables and integer divisions | |||
3643 | * from "umap" using Fourier-Motzkin elimination. | |||
3644 | */ | |||
3645 | __isl_give isl_union_map *isl_union_map_remove_divs( | |||
3646 | __isl_take isl_union_map *umap) | |||
3647 | { | |||
3648 | return total(umap, &isl_map_remove_divs); | |||
3649 | } | |||
3650 | ||||
3651 | /* Remove all existentially quantified variables and integer divisions | |||
3652 | * from "uset" using Fourier-Motzkin elimination. | |||
3653 | */ | |||
3654 | __isl_give isl_union_setisl_union_map *isl_union_set_remove_divs( | |||
3655 | __isl_take isl_union_setisl_union_map *uset) | |||
3656 | { | |||
3657 | return isl_union_map_remove_divs(uset); | |||
3658 | } | |||
3659 | ||||
3660 | /* Internal data structure for isl_union_map_project_out. | |||
3661 | * "type", "first" and "n" are the arguments for the isl_map_project_out | |||
3662 | * call. | |||
3663 | * "res" collects the results. | |||
3664 | */ | |||
3665 | struct isl_union_map_project_out_data { | |||
3666 | enum isl_dim_type type; | |||
3667 | unsigned first; | |||
3668 | unsigned n; | |||
3669 | ||||
3670 | isl_union_map *res; | |||
3671 | }; | |||
3672 | ||||
3673 | /* Turn the data->n dimensions of type data->type, starting at data->first | |||
3674 | * into existentially quantified variables and add the result to data->res. | |||
3675 | */ | |||
3676 | static isl_stat project_out(__isl_take isl_map *map, void *user) | |||
3677 | { | |||
3678 | struct isl_union_map_project_out_data *data = user; | |||
3679 | ||||
3680 | map = isl_map_project_out(map, data->type, data->first, data->n); | |||
3681 | data->res = isl_union_map_add_map(data->res, map); | |||
3682 | ||||
3683 | return isl_stat_ok; | |||
3684 | } | |||
3685 | ||||
3686 | /* Turn the "n" dimensions of type "type", starting at "first" | |||
3687 | * into existentially quantified variables. | |||
3688 | * Since the space of an isl_union_map only contains parameters, | |||
3689 | * type is required to be equal to isl_dim_param. | |||
3690 | */ | |||
3691 | __isl_give isl_union_map *isl_union_map_project_out( | |||
3692 | __isl_take isl_union_map *umap, | |||
3693 | enum isl_dim_type type, unsigned first, unsigned n) | |||
3694 | { | |||
3695 | isl_space *space; | |||
3696 | struct isl_union_map_project_out_data data = { type, first, n }; | |||
3697 | ||||
3698 | if (!umap) | |||
3699 | return NULL((void*)0); | |||
3700 | ||||
3701 | if (type != isl_dim_param) | |||
3702 | isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,do { isl_handle_error(isl_union_map_get_ctx(umap), isl_error_invalid , "can only project out parameters", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_union_map.c" , 3704); return isl_union_map_free(umap); } while (0) | |||
3703 | "can only project out parameters",do { isl_handle_error(isl_union_map_get_ctx(umap), isl_error_invalid , "can only project out parameters", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_union_map.c" , 3704); return isl_union_map_free(umap); } while (0) | |||
3704 | return isl_union_map_free(umap))do { isl_handle_error(isl_union_map_get_ctx(umap), isl_error_invalid , "can only project out parameters", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_union_map.c" , 3704); return isl_union_map_free(umap); } while (0); | |||
3705 | ||||
3706 | space = isl_union_map_get_space(umap); | |||
3707 | space = isl_space_drop_dims(space, type, first, n); | |||
3708 | data.res = isl_union_map_empty(space); | |||
3709 | if (isl_union_map_foreach_map(umap, &project_out, &data) < 0) | |||
3710 | data.res = isl_union_map_free(data.res); | |||
3711 | ||||
3712 | isl_union_map_free(umap); | |||
3713 | ||||
3714 | return data.res; | |||
3715 | } | |||
3716 | ||||
3717 | /* Project out all parameters from "umap" by existentially quantifying | |||
3718 | * over them. | |||
3719 | */ | |||
3720 | __isl_give isl_union_map *isl_union_map_project_out_all_params( | |||
3721 | __isl_take isl_union_map *umap) | |||
3722 | { | |||
3723 | unsigned n; | |||
3724 | ||||
3725 | if (!umap) | |||
3726 | return NULL((void*)0); | |||
3727 | n = isl_union_map_dim(umap, isl_dim_param); | |||
3728 | return isl_union_map_project_out(umap, isl_dim_param, 0, n); | |||
3729 | } | |||
3730 | ||||
3731 | /* Turn the "n" dimensions of type "type", starting at "first" | |||
3732 | * into existentially quantified variables. | |||
3733 | * Since the space of an isl_union_set only contains parameters, | |||
3734 | * "type" is required to be equal to isl_dim_param. | |||
3735 | */ | |||
3736 | __isl_give isl_union_setisl_union_map *isl_union_set_project_out( | |||
3737 | __isl_take isl_union_setisl_union_map *uset, | |||
3738 | enum isl_dim_type type, unsigned first, unsigned n) | |||
3739 | { | |||
3740 | return isl_union_map_project_out(uset, type, first, n); | |||
3741 | } | |||
3742 | ||||
3743 | /* Internal data structure for isl_union_map_involves_dims. | |||
3744 | * "first" and "n" are the arguments for the isl_map_involves_dims calls. | |||
3745 | */ | |||
3746 | struct isl_union_map_involves_dims_data { | |||
3747 | unsigned first; | |||
3748 | unsigned n; | |||
3749 | }; | |||
3750 | ||||
3751 | /* Does "map" _not_ involve the data->n parameters starting at data->first? | |||
3752 | */ | |||
3753 | static isl_bool map_excludes(__isl_keep isl_map *map, void *user) | |||
3754 | { | |||
3755 | struct isl_union_map_involves_dims_data *data = user; | |||
3756 | isl_bool involves; | |||
3757 | ||||
3758 | involves = isl_map_involves_dims(map, | |||
3759 | isl_dim_param, data->first, data->n); | |||
3760 | if (involves < 0) | |||
3761 | return isl_bool_error; | |||
3762 | return !involves; | |||
3763 | } | |||
3764 | ||||
3765 | /* Does "umap" involve any of the n parameters starting at first? | |||
3766 | * "type" is required to be set to isl_dim_param. | |||
3767 | * | |||
3768 | * "umap" involves any of those parameters if any of its maps | |||
3769 | * involve the parameters. In other words, "umap" does not | |||
3770 | * involve any of the parameters if all its maps to not | |||
3771 | * involve the parameters. | |||
3772 | */ | |||
3773 | isl_bool isl_union_map_involves_dims(__isl_keep isl_union_map *umap, | |||
3774 | enum isl_dim_type type, unsigned first, unsigned n) | |||
3775 | { | |||
3776 | struct isl_union_map_involves_dims_data data = { first, n }; | |||
3777 | isl_bool excludes; | |||
3778 | ||||
3779 | if (type != isl_dim_param) | |||
3780 | isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,do { isl_handle_error(isl_union_map_get_ctx(umap), isl_error_invalid , "can only reference parameters", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_union_map.c" , 3781); return isl_bool_error; } while (0) | |||
3781 | "can only reference parameters", return isl_bool_error)do { isl_handle_error(isl_union_map_get_ctx(umap), isl_error_invalid , "can only reference parameters", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_union_map.c" , 3781); return isl_bool_error; } while (0); | |||
3782 | ||||
3783 | excludes = union_map_forall_user(umap, &map_excludes, &data); | |||
3784 | ||||
3785 | if (excludes < 0) | |||
3786 | return isl_bool_error; | |||
3787 | ||||
3788 | return !excludes; | |||
3789 | } | |||
3790 | ||||
3791 | /* Internal data structure for isl_union_map_reset_range_space. | |||
3792 | * "range" is the space from which to set the range space. | |||
3793 | * "res" collects the results. | |||
3794 | */ | |||
3795 | struct isl_union_map_reset_range_space_data { | |||
3796 | isl_space *range; | |||
3797 | isl_union_map *res; | |||
3798 | }; | |||
3799 | ||||
3800 | /* Replace the range space of "map" by the range space of data->range and | |||
3801 | * add the result to data->res. | |||
3802 | */ | |||
3803 | static isl_stat reset_range_space(__isl_take isl_map *map, void *user) | |||
3804 | { | |||
3805 | struct isl_union_map_reset_range_space_data *data = user; | |||
3806 | isl_space *space; | |||
3807 | ||||
3808 | space = isl_map_get_space(map); | |||
3809 | space = isl_space_domain(space); | |||
3810 | space = isl_space_extend_domain_with_range(space, | |||
3811 | isl_space_copy(data->range)); | |||
3812 | map = isl_map_reset_space(map, space); | |||
3813 | data->res = isl_union_map_add_map(data->res, map); | |||
3814 | ||||
3815 | return data->res ? isl_stat_ok : isl_stat_error; | |||
3816 | } | |||
3817 | ||||
3818 | /* Replace the range space of all the maps in "umap" by | |||
3819 | * the range space of "space". | |||
3820 | * | |||
3821 | * This assumes that all maps have the same output dimension. | |||
3822 | * This function should therefore not be made publicly available. | |||
3823 | * | |||
3824 | * Since the spaces of the maps change, so do their hash value. | |||
3825 | * We therefore need to create a new isl_union_map. | |||
3826 | */ | |||
3827 | __isl_give isl_union_map *isl_union_map_reset_range_space( | |||
3828 | __isl_take isl_union_map *umap, __isl_take isl_space *space) | |||
3829 | { | |||
3830 | struct isl_union_map_reset_range_space_data data = { space }; | |||
3831 | ||||
3832 | data.res = isl_union_map_empty(isl_union_map_get_space(umap)); | |||
3833 | if (isl_union_map_foreach_map(umap, &reset_range_space, &data) < 0) | |||
3834 | data.res = isl_union_map_free(data.res); | |||
3835 | ||||
3836 | isl_space_free(space); | |||
3837 | isl_union_map_free(umap); | |||
3838 | return data.res; | |||
3839 | } | |||
3840 | ||||
3841 | /* Check that "umap" and "space" have the same number of parameters. | |||
3842 | */ | |||
3843 | static isl_stat check_union_map_space_equal_dim(__isl_keep isl_union_map *umap, | |||
3844 | __isl_keep isl_space *space) | |||
3845 | { | |||
3846 | unsigned dim1, dim2; | |||
3847 | ||||
3848 | if (!umap || !space) | |||
3849 | return isl_stat_error; | |||
3850 | dim1 = isl_union_map_dim(umap, isl_dim_param); | |||
3851 | dim2 = isl_space_dim(space, isl_dim_param); | |||
3852 | if (dim1 == dim2) | |||
3853 | return isl_stat_ok; | |||
3854 | isl_die(isl_union_map_get_ctx(umap), isl_error_invalid,do { isl_handle_error(isl_union_map_get_ctx(umap), isl_error_invalid , "number of parameters does not match", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_union_map.c" , 3855); return isl_stat_error; } while (0) | |||
3855 | "number of parameters does not match", return isl_stat_error)do { isl_handle_error(isl_union_map_get_ctx(umap), isl_error_invalid , "number of parameters does not match", "/build/llvm-toolchain-snapshot-9~svn362543/tools/polly/lib/External/isl/isl_union_map.c" , 3855); return isl_stat_error; } while (0); | |||
3856 | } | |||
3857 | ||||
3858 | /* Internal data structure for isl_union_map_reset_equal_dim_space. | |||
3859 | * "space" is the target space. | |||
3860 | * "res" collects the results. | |||
3861 | */ | |||
3862 | struct isl_union_map_reset_params_data { | |||
3863 | isl_space *space; | |||
3864 | isl_union_map *res; | |||
3865 | }; | |||
3866 | ||||
3867 | /* Replace the parameters of "map" by those of data->space and | |||
3868 | * add the result to data->res. | |||
3869 | */ | |||
3870 | static isl_stat reset_params(__isl_take isl_map *map, void *user) | |||
3871 | { | |||
3872 | struct isl_union_map_reset_params_data *data = user; | |||
3873 | isl_space *space; | |||
3874 | ||||
3875 | space = isl_map_get_space(map); | |||
3876 | space = isl_space_replace_params(space, data->space); | |||
3877 | map = isl_map_reset_equal_dim_space(map, space); | |||
3878 | data->res = isl_union_map_add_map(data->res, map); | |||
3879 | ||||
3880 | return data->res ? isl_stat_ok : isl_stat_error; | |||
3881 | } | |||
3882 | ||||
3883 | /* Replace the space of "umap" by "space", without modifying | |||
3884 | * the dimension of "umap", i.e., the number of parameters of "umap". | |||
3885 | * | |||
3886 | * Since the hash values of the maps in the union map depend | |||
3887 | * on the parameters, a new union map needs to be constructed. | |||
3888 | */ | |||
3889 | __isl_give isl_union_map *isl_union_map_reset_equal_dim_space( | |||
3890 | __isl_take isl_union_map *umap, __isl_take isl_space *space) | |||
3891 | { | |||
3892 | struct isl_union_map_reset_params_data data = { space }; | |||
3893 | isl_bool equal; | |||
3894 | isl_space *umap_space; | |||
3895 | ||||
3896 | umap_space = isl_union_map_peek_space(umap); | |||
3897 | equal = isl_space_is_equal(umap_space, space); | |||
3898 | if (equal < 0) | |||
3899 | goto error; | |||
3900 | if (equal) { | |||
3901 | isl_space_free(space); | |||
3902 | return umap; | |||
3903 | } | |||
3904 | if (check_union_map_space_equal_dim(umap, space) < 0) | |||
3905 | goto error; | |||
3906 | ||||
3907 | data.res = isl_union_map_empty(isl_space_copy(space)); | |||
3908 | if (isl_union_map_foreach_map(umap, &reset_params, &data) < 0) | |||
3909 | data.res = isl_union_map_free(data.res); | |||
3910 | ||||
3911 | isl_space_free(space); | |||
3912 | isl_union_map_free(umap); | |||
3913 | return data.res; | |||
3914 | error: | |||
3915 | isl_union_map_free(umap); | |||
3916 | isl_space_free(space); | |||
3917 | return NULL((void*)0); | |||
3918 | } | |||
3919 | ||||
3920 | /* Internal data structure for isl_union_map_order_at_multi_union_pw_aff. | |||
3921 | * "mupa" is the function from which the isl_multi_pw_affs are extracted. | |||
3922 | * "order" is applied to the extracted isl_multi_pw_affs that correspond | |||
3923 | * to the domain and the range of each map. | |||
3924 | * "res" collects the results. | |||
3925 | */ | |||
3926 | struct isl_union_order_at_data { | |||
3927 | isl_multi_union_pw_aff *mupa; | |||
3928 | __isl_give isl_map *(*order)(__isl_take isl_multi_pw_aff *mpa1, | |||
3929 | __isl_take isl_multi_pw_aff *mpa2); | |||
3930 | isl_union_map *res; | |||
3931 | }; | |||
3932 | ||||
3933 | /* Intersect "map" with the result of applying data->order to | |||
3934 | * the functions in data->mupa that apply to the domain and the range | |||
3935 | * of "map" and add the result to data->res. | |||
3936 | */ | |||
3937 | static isl_stat order_at(__isl_take isl_map *map, void *user) | |||
3938 | { | |||
3939 | struct isl_union_order_at_data *data = user; | |||
3940 | isl_space *space; | |||
3941 | isl_multi_pw_aff *mpa1, *mpa2; | |||
3942 | isl_map *order; | |||
3943 | ||||
3944 | space = isl_space_domain(isl_map_get_space(map)); | |||
3945 | mpa1 = isl_multi_union_pw_aff_extract_multi_pw_aff(data->mupa, space); | |||
3946 | space = isl_space_range(isl_map_get_space(map)); | |||
3947 | mpa2 = isl_multi_union_pw_aff_extract_multi_pw_aff(data->mupa, space); | |||
3948 | order = data->order(mpa1, mpa2); | |||
3949 | map = isl_map_intersect(map, order); | |||
3950 | data->res = isl_union_map_add_map(data->res, map); | |||
3951 | ||||
3952 | return data->res ? isl_stat_ok : isl_stat_error; | |||
3953 | } | |||
3954 | ||||
3955 | /* If "mupa" has a non-trivial explicit domain, then intersect | |||
3956 | * domain and range of "umap" with this explicit domain. | |||
3957 | * If the explicit domain only describes constraints on the parameters, | |||
3958 | * then the intersection only needs to be performed once. | |||
3959 | */ | |||
3960 | static __isl_give isl_union_map *intersect_explicit_domain( | |||
3961 | __isl_take isl_union_map *umap, __isl_keep isl_multi_union_pw_aff *mupa) | |||
3962 | { | |||
3963 | isl_bool non_trivial, is_params; | |||
3964 | isl_union_setisl_union_map *dom; | |||
3965 | ||||
3966 | non_trivial = isl_multi_union_pw_aff_has_non_trivial_domain(mupa); | |||
3967 | if (non_trivial < 0) | |||
3968 | return isl_union_map_free(umap); | |||
3969 | if (!non_trivial) | |||
3970 | return umap; | |||
3971 | mupa = isl_multi_union_pw_aff_copy(mupa); | |||
3972 | dom = isl_multi_union_pw_aff_domain(mupa); | |||
3973 | is_params = isl_union_set_is_params(dom); | |||
3974 | if (is_params < 0) { | |||
3975 | isl_union_set_free(dom); | |||
3976 | return isl_union_map_free(umap); | |||
3977 | } | |||
3978 | if (is_params) { | |||
3979 | isl_setisl_map *set; | |||
3980 | ||||
3981 | set = isl_union_set_params(dom); | |||
3982 | umap = isl_union_map_intersect_params(umap, set); | |||
3983 | return umap; | |||
3984 | } | |||
3985 | umap = isl_union_map_intersect_domain(umap, isl_union_set_copy(dom)); | |||
3986 | umap = isl_union_map_intersect_range(umap, dom); | |||
3987 | return umap; | |||
3988 | } | |||
3989 | ||||
3990 | /* Intersect each map in "umap" with the result of calling "order" | |||
3991 | * on the functions is "mupa" that apply to the domain and the range | |||
3992 | * of the map. | |||
3993 | */ | |||
3994 | static __isl_give isl_union_map *isl_union_map_order_at_multi_union_pw_aff( | |||
3995 | __isl_take isl_union_map *umap, __isl_take isl_multi_union_pw_aff *mupa, | |||
3996 | __isl_give isl_map *(*order)(__isl_take isl_multi_pw_aff *mpa1, | |||
3997 | __isl_take isl_multi_pw_aff *mpa2)) | |||
3998 | { | |||
3999 | struct isl_union_order_at_data data; | |||
4000 | ||||
4001 | umap = isl_union_map_align_params(umap, | |||
4002 | isl_multi_union_pw_aff_get_space(mupa)); | |||
4003 | mupa = isl_multi_union_pw_aff_align_params(mupa, | |||
4004 | isl_union_map_get_space(umap)); | |||
4005 | umap = intersect_explicit_domain(umap, mupa); | |||
4006 | data.mupa = mupa; | |||
4007 | data.order = order; | |||
4008 | data.res = isl_union_map_empty(isl_union_map_get_space(umap)); | |||
4009 | if (isl_union_map_foreach_map(umap, &order_at, &data) < 0) | |||
4010 | data.res = isl_union_map_free(data.res); | |||
4011 | ||||
4012 | isl_multi_union_pw_aff_free(mupa); | |||
4013 | isl_union_map_free(umap); | |||
4014 | return data.res; | |||
4015 | } | |||
4016 | ||||
4017 | /* Return the subset of "umap" where the domain and the range | |||
4018 | * have equal "mupa" values. | |||
4019 | */ | |||
4020 | __isl_give isl_union_map *isl_union_map_eq_at_multi_union_pw_aff( | |||
4021 | __isl_take isl_union_map *umap, | |||
4022 | __isl_take isl_multi_union_pw_aff *mupa) | |||
4023 | { | |||
4024 | return isl_union_map_order_at_multi_union_pw_aff(umap, mupa, | |||
4025 | &isl_multi_pw_aff_eq_map); | |||
4026 | } | |||
4027 | ||||
4028 | /* Return the subset of "umap" where the domain has a lexicographically | |||
4029 | * smaller "mupa" value than the range. | |||
4030 | */ | |||
4031 | __isl_give isl_union_map *isl_union_map_lex_lt_at_multi_union_pw_aff( | |||
4032 | __isl_take isl_union_map *umap, | |||
4033 | __isl_take isl_multi_union_pw_aff *mupa) | |||
4034 | { | |||
4035 | return isl_union_map_order_at_multi_union_pw_aff(umap, mupa, | |||
4036 | &isl_multi_pw_aff_lex_lt_map); | |||
4037 | } | |||
4038 | ||||
4039 | /* Return the subset of "umap" where the domain has a lexicographically | |||
4040 | * greater "mupa" value than the range. | |||
4041 | */ | |||
4042 | __isl_give isl_union_map *isl_union_map_lex_gt_at_multi_union_pw_aff( | |||
4043 | __isl_take isl_union_map *umap, | |||
4044 | __isl_take isl_multi_union_pw_aff *mupa) | |||
4045 | { | |||
4046 | return isl_union_map_order_at_multi_union_pw_aff(umap, mupa, | |||
4047 | &isl_multi_pw_aff_lex_gt_map); | |||
4048 | } | |||
4049 | ||||
4050 | /* Return the union of the elements in the list "list". | |||
4051 | */ | |||
4052 | __isl_give isl_union_setisl_union_map *isl_union_set_list_union( | |||
4053 | __isl_take isl_union_set_listisl_union_map_list *list) | |||
4054 | { | |||
4055 | int i, n; | |||
4056 | isl_ctx *ctx; | |||
4057 | isl_space *space; | |||
4058 | isl_union_setisl_union_map *res; | |||
4059 | ||||
4060 | if (!list) | |||
4061 | return NULL((void*)0); | |||
4062 | ||||
4063 | ctx = isl_union_set_list_get_ctx(list); | |||
4064 | space = isl_space_params_alloc(ctx, 0); | |||
4065 | res = isl_union_set_empty(space); | |||
4066 | ||||
4067 | n = isl_union_set_list_n_union_set(list); | |||
4068 | for (i = 0; i < n; ++i) { | |||
4069 | isl_union_setisl_union_map *uset_i; | |||
4070 | ||||
4071 | uset_i = isl_union_set_list_get_union_set(list, i); | |||
4072 | res = isl_union_set_union(res, uset_i); | |||
4073 | } | |||
4074 | ||||
4075 | isl_union_set_list_free(list); | |||
4076 | return res; | |||
4077 | } | |||
4078 | ||||
4079 | /* Update *hash with the hash value of "map". | |||
4080 | */ | |||
4081 | static isl_stat add_hash(__isl_take isl_map *map, void *user) | |||
4082 | { | |||
4083 | uint32_t *hash = user; | |||
4084 | uint32_t map_hash; | |||
4085 | ||||
4086 | map_hash = isl_map_get_hash(map); | |||
4087 | isl_hash_hash(*hash, map_hash)do { do { *hash *= 16777619; *hash ^= (map_hash) & 0xFF; } while(0); do { *hash *= 16777619; *hash ^= ((map_hash) >> 8) & 0xFF; } while(0); do { *hash *= 16777619; *hash ^= ( (map_hash) >> 16) & 0xFF; } while(0); do { *hash *= 16777619; *hash ^= ((map_hash) >> 24) & 0xFF; } while (0); } while(0); | |||
4088 | ||||
4089 | isl_map_free(map); | |||
4090 | return isl_stat_ok; | |||
4091 | } | |||
4092 | ||||
4093 | /* Return a hash value that digests "umap". | |||
4094 | */ | |||
4095 | uint32_t isl_union_map_get_hash(__isl_keep isl_union_map *umap) | |||
4096 | { | |||
4097 | uint32_t hash; | |||
4098 | ||||
4099 | if (!umap) | |||
4100 | return 0; | |||
4101 | ||||
4102 | hash = isl_hash_init()(2166136261u); | |||
4103 | if (isl_union_map_foreach_map(umap, &add_hash, &hash) < 0) | |||
4104 | return 0; | |||
4105 | ||||
4106 | return hash; | |||
4107 | } | |||
4108 | ||||
4109 | /* Return a hash value that digests "uset". | |||
4110 | */ | |||
4111 | uint32_t isl_union_set_get_hash(__isl_keep isl_union_setisl_union_map *uset) | |||
4112 | { | |||
4113 | return isl_union_map_get_hash(uset); | |||
4114 | } | |||
4115 | ||||
4116 | /* Add the number of basic sets in "set" to "n". | |||
4117 | */ | |||
4118 | static isl_stat add_n(__isl_take isl_setisl_map *set, void *user) | |||
4119 | { | |||
4120 | int *n = user; | |||
4121 | ||||
4122 | *n += isl_set_n_basic_set(set); | |||
4123 | isl_set_free(set); | |||
4124 | ||||
4125 | return isl_stat_ok; | |||
4126 | } | |||
4127 | ||||
4128 | /* Return the total number of basic sets in "uset". | |||
4129 | */ | |||
4130 | int isl_union_set_n_basic_set(__isl_keep isl_union_setisl_union_map *uset) | |||
4131 | { | |||
4132 | int n = 0; | |||
4133 | ||||
4134 | if (isl_union_set_foreach_set(uset, &add_n, &n) < 0) | |||
4135 | return -1; | |||
4136 | ||||
4137 | return n; | |||
4138 | } | |||
4139 | ||||
4140 | /* Add the basic sets in "set" to "list". | |||
4141 | */ | |||
4142 | static isl_stat add_list(__isl_take isl_setisl_map *set, void *user) | |||
4143 | { | |||
4144 | isl_basic_set_listisl_basic_map_list **list = user; | |||
4145 | isl_basic_set_listisl_basic_map_list *list_i; | |||
4146 | ||||
4147 | list_i = isl_set_get_basic_set_list(set); | |||
4148 | *list = isl_basic_set_list_concat(*list, list_i); | |||
4149 | isl_set_free(set); | |||
4150 | ||||
4151 | if (!*list) | |||
4152 | return isl_stat_error; | |||
4153 | return isl_stat_ok; | |||
4154 | } | |||
4155 | ||||
4156 | /* Return a list containing all the basic sets in "uset". | |||
4157 | * | |||
4158 | * First construct a list of the appropriate size and | |||
4159 | * then add all the elements. | |||
4160 | */ | |||
4161 | __isl_give isl_basic_set_listisl_basic_map_list *isl_union_set_get_basic_set_list( | |||
4162 | __isl_keep isl_union_setisl_union_map *uset) | |||
4163 | { | |||
4164 | int n; | |||
4165 | isl_ctx *ctx; | |||
4166 | isl_basic_set_listisl_basic_map_list *list; | |||
4167 | ||||
4168 | if (!uset) | |||
4169 | return NULL((void*)0); | |||
4170 | ctx = isl_union_set_get_ctx(uset); | |||
4171 | n = isl_union_set_n_basic_set(uset); | |||
4172 | if (n < 0) | |||
4173 | return NULL((void*)0); | |||
4174 | list = isl_basic_set_list_alloc(ctx, n); | |||
4175 | if (isl_union_set_foreach_set(uset, &add_list, &list) < 0) | |||
4176 | list = isl_basic_set_list_free(list); | |||
4177 | ||||
4178 | return list; | |||
4179 | } | |||
4180 | ||||
4181 | /* Internal data structure for isl_union_map_remove_map_if. | |||
4182 | * "fn" and "user" are the arguments to isl_union_map_remove_map_if. | |||
4183 | */ | |||
4184 | struct isl_union_map_remove_map_if_data { | |||
4185 | isl_bool (*fn)(__isl_keep isl_map *map, void *user); | |||
4186 | void *user; | |||
4187 | }; | |||
4188 | ||||
4189 | /* isl_un_op_control filter that negates the result of data->fn | |||
4190 | * called on "map". | |||
4191 | */ | |||
4192 | static isl_bool not(__isl_keep isl_map *map, void *user) | |||
4193 | { | |||
4194 | struct isl_union_map_remove_map_if_data *data = user; | |||
4195 | ||||
4196 | return isl_bool_not(data->fn(map, data->user)); | |||
4197 | } | |||
4198 | ||||
4199 | /* Dummy isl_un_op_control transformation callback that | |||
4200 | * simply returns the input. | |||
4201 | */ | |||
4202 | static __isl_give isl_map *map_id(__isl_take isl_map *map) | |||
4203 | { | |||
4204 | return map; | |||
4205 | } | |||
4206 | ||||
4207 | /* Call "fn" on every map in "umap" and remove those maps | |||
4208 | * for which the callback returns true. | |||
4209 | * | |||
4210 | * Use un_op to keep only those maps that are not filtered out, | |||
4211 | * applying an identity transformation on them. | |||
4212 | */ | |||
4213 | __isl_give isl_union_map *isl_union_map_remove_map_if( | |||
4214 | __isl_take isl_union_map *umap, | |||
4215 | isl_bool (*fn)(__isl_keep isl_map *map, void *user), void *user) | |||
4216 | { | |||
4217 | struct isl_union_map_remove_map_if_data data = { fn, user }; | |||
4218 | struct isl_un_op_control control = { | |||
4219 | .filter = ¬, | |||
4220 | .filter_user = &data, | |||
4221 | .fn_map = &map_id, | |||
4222 | }; | |||
4223 | return un_op(umap, &control); | |||
4224 | } |