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