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