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