Line data Source code
1 : /*
2 : * Copyright 2010 INRIA Saclay
3 : * Copyright 2013 Ecole Normale Superieure
4 : *
5 : * Use of this software is governed by the MIT license
6 : *
7 : * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 : * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
9 : * 91893 Orsay, France
10 : * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
11 : */
12 :
13 : #undef TYPE
14 : #define TYPE UNION
15 : static
16 : #include "has_single_reference_templ.c"
17 :
18 : __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u);
19 :
20 0 : isl_ctx *FN(UNION,get_ctx)(__isl_keep UNION *u)
21 : {
22 0 : return u ? u->space->ctx : NULL;
23 : }
24 :
25 : /* Return the space of "u".
26 : */
27 0 : static __isl_keep isl_space *FN(UNION,peek_space)(__isl_keep UNION *u)
28 : {
29 0 : if (!u)
30 0 : return NULL;
31 0 : return u->space;
32 : }
33 :
34 : /* Return a copy of the space of "u".
35 : */
36 0 : __isl_give isl_space *FN(UNION,get_space)(__isl_keep UNION *u)
37 : {
38 0 : return isl_space_copy(FN(UNION,peek_space)(u));
39 : }
40 :
41 : /* Return the number of parameters of "u", where "type"
42 : * is required to be set to isl_dim_param.
43 : */
44 0 : unsigned FN(UNION,dim)(__isl_keep UNION *u, enum isl_dim_type type)
45 : {
46 0 : if (!u)
47 0 : return 0;
48 :
49 0 : if (type != isl_dim_param)
50 0 : isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
51 : "can only reference parameters", return 0);
52 :
53 0 : return isl_space_dim(u->space, type);
54 : }
55 :
56 : /* Return the position of the parameter with the given name
57 : * in "u".
58 : * Return -1 if no such dimension can be found.
59 : */
60 0 : int FN(UNION,find_dim_by_name)(__isl_keep UNION *u, enum isl_dim_type type,
61 : const char *name)
62 : {
63 0 : if (!u)
64 0 : return -1;
65 0 : return isl_space_find_dim_by_name(u->space, type, name);
66 : }
67 :
68 : #ifdef HAS_TYPE
69 0 : static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *dim,
70 : enum isl_fold type, int size)
71 : #else
72 0 : static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *dim, int size)
73 : #endif
74 : {
75 : UNION *u;
76 :
77 0 : dim = isl_space_params(dim);
78 0 : if (!dim)
79 0 : return NULL;
80 :
81 0 : u = isl_calloc_type(dim->ctx, UNION);
82 0 : if (!u)
83 0 : goto error;
84 :
85 0 : u->ref = 1;
86 : #ifdef HAS_TYPE
87 0 : u->type = type;
88 : #endif
89 0 : u->space = dim;
90 0 : if (isl_hash_table_init(dim->ctx, &u->table, size) < 0)
91 0 : return FN(UNION,free)(u);
92 :
93 0 : return u;
94 : error:
95 0 : isl_space_free(dim);
96 0 : return NULL;
97 : }
98 :
99 : #ifdef HAS_TYPE
100 0 : __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *dim, enum isl_fold type)
101 : {
102 0 : return FN(UNION,alloc)(dim, type, 16);
103 : }
104 : #else
105 0 : __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *dim)
106 : {
107 0 : return FN(UNION,alloc)(dim, 16);
108 : }
109 : #endif
110 :
111 0 : __isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u)
112 : {
113 0 : if (!u)
114 0 : return NULL;
115 :
116 0 : u->ref++;
117 0 : return u;
118 : }
119 :
120 : /* Extract the element of "u" living in "space" (ignoring parameters).
121 : *
122 : * Return the ZERO element if "u" does not contain any element
123 : * living in "space".
124 : */
125 0 : __isl_give PART *FN(FN(UNION,extract),BASE)(__isl_keep UNION *u,
126 : __isl_take isl_space *space)
127 : {
128 : struct isl_hash_table_entry *entry;
129 :
130 0 : space = isl_space_replace_params(space, FN(UNION,peek_space)(u));
131 :
132 0 : entry = FN(UNION,find_part_entry)(u, space, 0);
133 0 : if (!entry)
134 0 : goto error;
135 0 : if (entry == isl_hash_table_entry_none)
136 : #ifdef HAS_TYPE
137 0 : return FN(PART,ZERO)(space, u->type);
138 : #else
139 0 : return FN(PART,ZERO)(space);
140 : #endif
141 0 : isl_space_free(space);
142 0 : return FN(PART,copy)(entry->data);
143 : error:
144 0 : isl_space_free(space);
145 0 : return NULL;
146 : }
147 :
148 : /* Add "part" to "u".
149 : * If "disjoint" is set, then "u" is not allowed to already have
150 : * a part that is defined over a domain that overlaps with the domain
151 : * of "part".
152 : * Otherwise, compute the union sum of "part" and the part in "u"
153 : * defined on the same space.
154 : */
155 0 : static __isl_give UNION *FN(UNION,add_part_generic)(__isl_take UNION *u,
156 : __isl_take PART *part, int disjoint)
157 : {
158 : int empty;
159 : struct isl_hash_table_entry *entry;
160 :
161 0 : if (!part)
162 0 : goto error;
163 :
164 0 : empty = FN(PART,IS_ZERO)(part);
165 0 : if (empty < 0)
166 0 : goto error;
167 0 : if (empty) {
168 0 : FN(PART,free)(part);
169 0 : return u;
170 : }
171 :
172 0 : u = FN(UNION,align_params)(u, FN(PART,get_space)(part));
173 0 : part = FN(PART,align_params)(part, FN(UNION,get_space)(u));
174 :
175 0 : u = FN(UNION,cow)(u);
176 :
177 0 : if (!u)
178 0 : goto error;
179 :
180 0 : if (FN(UNION,check_disjoint_domain_other)(u, part) < 0)
181 0 : goto error;
182 0 : entry = FN(UNION,find_part_entry)(u, part->dim, 1);
183 0 : if (!entry)
184 0 : goto error;
185 :
186 0 : if (!entry->data)
187 0 : entry->data = part;
188 : else {
189 0 : if (disjoint &&
190 0 : FN(UNION,check_disjoint_domain)(entry->data, part) < 0)
191 0 : goto error;
192 0 : entry->data = FN(PART,union_add_)(entry->data,
193 : FN(PART,copy)(part));
194 0 : if (!entry->data)
195 0 : goto error;
196 0 : empty = FN(PART,IS_ZERO)(part);
197 0 : if (empty < 0)
198 0 : goto error;
199 0 : if (empty)
200 0 : u = FN(UNION,remove_part_entry)(u, entry);
201 0 : FN(PART,free)(part);
202 : }
203 :
204 0 : return u;
205 : error:
206 0 : FN(PART,free)(part);
207 0 : FN(UNION,free)(u);
208 0 : return NULL;
209 : }
210 :
211 : /* Add "part" to "u", where "u" is assumed not to already have
212 : * a part that is defined on the same space as "part".
213 : */
214 0 : __isl_give UNION *FN(FN(UNION,add),BASE)(__isl_take UNION *u,
215 : __isl_take PART *part)
216 : {
217 0 : return FN(UNION,add_part_generic)(u, part, 1);
218 : }
219 :
220 : #ifdef HAS_TYPE
221 : /* Allocate a UNION with the same type and the same size as "u" and
222 : * with space "space".
223 : */
224 0 : static __isl_give UNION *FN(UNION,alloc_same_size_on_space)(__isl_keep UNION *u,
225 : __isl_take isl_space *space)
226 : {
227 0 : if (!u)
228 0 : goto error;
229 0 : return FN(UNION,alloc)(space, u->type, u->table.n);
230 : error:
231 0 : isl_space_free(space);
232 0 : return NULL;
233 : }
234 : #else
235 : /* Allocate a UNION with the same size as "u" and with space "space".
236 : */
237 0 : static __isl_give UNION *FN(UNION,alloc_same_size_on_space)(__isl_keep UNION *u,
238 : __isl_take isl_space *space)
239 : {
240 0 : if (!u)
241 0 : goto error;
242 0 : return FN(UNION,alloc)(space, u->table.n);
243 : error:
244 0 : isl_space_free(space);
245 0 : return NULL;
246 : }
247 : #endif
248 :
249 : /* Allocate a UNION with the same space, the same type (if any) and
250 : * the same size as "u".
251 : */
252 0 : static __isl_give UNION *FN(UNION,alloc_same_size)(__isl_keep UNION *u)
253 : {
254 0 : return FN(UNION,alloc_same_size_on_space)(u, FN(UNION,get_space)(u));
255 : }
256 :
257 : /* Internal data structure for isl_union_*_transform_space.
258 : * "fn' is applied to each entry in the input.
259 : * "res" collects the results.
260 : */
261 : S(UNION,transform_data)
262 : {
263 : __isl_give PART *(*fn)(__isl_take PART *part, void *user);
264 : void *user;
265 :
266 : UNION *res;
267 : };
268 :
269 : /* Apply data->fn to "part" and add the result to data->res.
270 : */
271 0 : static isl_stat FN(UNION,transform_entry)(__isl_take PART *part, void *user)
272 : {
273 0 : S(UNION,transform_data) *data = (S(UNION,transform_data) *)user;
274 :
275 0 : part = data->fn(part, data->user);
276 0 : data->res = FN(FN(UNION,add),BASE)(data->res, part);
277 0 : if (!data->res)
278 0 : return isl_stat_error;
279 :
280 0 : return isl_stat_ok;
281 : }
282 :
283 : /* Return a UNION living in "space" that is obtained by applying "fn"
284 : * to each of the entries in "u".
285 : */
286 0 : static __isl_give UNION *FN(UNION,transform_space)(__isl_take UNION *u,
287 : isl_space *space,
288 : __isl_give PART *(*fn)(__isl_take PART *part, void *user), void *user)
289 : {
290 0 : S(UNION,transform_data) data = { fn, user };
291 :
292 0 : data.res = FN(UNION,alloc_same_size_on_space)(u, space);
293 0 : if (FN(FN(UNION,foreach),BASE)(u,
294 : &FN(UNION,transform_entry), &data) < 0)
295 0 : data.res = FN(UNION,free)(data.res);
296 0 : FN(UNION,free)(u);
297 0 : return data.res;
298 : }
299 :
300 : /* Return a UNION that lives in the same space as "u" and that is obtained
301 : * by applying "fn" to each of the entries in "u".
302 : */
303 0 : static __isl_give UNION *FN(UNION,transform)(__isl_take UNION *u,
304 : __isl_give PART *(*fn)(__isl_take PART *part, void *user), void *user)
305 : {
306 0 : return FN(UNION,transform_space)(u, FN(UNION,get_space)(u), fn, user);
307 : }
308 :
309 : /* Apply data->fn to *part and store the result back into *part.
310 : */
311 0 : static isl_stat FN(UNION,transform_inplace_entry)(void **part, void *user)
312 : {
313 0 : S(UNION,transform_data) *data = (S(UNION,transform_data) *) user;
314 :
315 0 : *part = data->fn(*part, data->user);
316 0 : if (!*part)
317 0 : return isl_stat_error;
318 0 : return isl_stat_ok;
319 : }
320 :
321 : /* Update "u" by applying "fn" to each entry.
322 : * This operation is assumed not to change the number of entries nor
323 : * the spaces of the entries.
324 : *
325 : * If there is only one reference to "u", then change "u" inplace.
326 : * Otherwise, create a new UNION from "u" and discard the original.
327 : */
328 0 : static __isl_give UNION *FN(UNION,transform_inplace)(__isl_take UNION *u,
329 : __isl_give PART *(*fn)(__isl_take PART *part, void *user), void *user)
330 : {
331 : isl_bool single_ref;
332 :
333 0 : single_ref = FN(UNION,has_single_reference)(u);
334 0 : if (single_ref < 0)
335 0 : return FN(UNION,free)(u);
336 0 : if (single_ref) {
337 0 : S(UNION,transform_data) data = { fn, user };
338 0 : if (FN(UNION,foreach_inplace)(u,
339 : &FN(UNION,transform_inplace_entry), &data) < 0)
340 0 : return FN(UNION,free)(u);
341 0 : return u;
342 : }
343 0 : return FN(UNION,transform)(u, fn, user);
344 : }
345 :
346 : /* An isl_union_*_transform callback for use in isl_union_*_dup
347 : * that simply returns "part".
348 : */
349 0 : static __isl_give PART *FN(UNION,copy_part)(__isl_take PART *part, void *user)
350 : {
351 0 : return part;
352 : }
353 :
354 0 : __isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u)
355 : {
356 0 : u = FN(UNION,copy)(u);
357 0 : return FN(UNION,transform)(u, &FN(UNION,copy_part), NULL);
358 : }
359 :
360 0 : __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u)
361 : {
362 0 : if (!u)
363 0 : return NULL;
364 :
365 0 : if (u->ref == 1)
366 0 : return u;
367 0 : u->ref--;
368 0 : return FN(UNION,dup)(u);
369 : }
370 :
371 0 : __isl_null UNION *FN(UNION,free)(__isl_take UNION *u)
372 : {
373 0 : if (!u)
374 0 : return NULL;
375 :
376 0 : if (--u->ref > 0)
377 0 : return NULL;
378 :
379 0 : isl_hash_table_foreach(u->space->ctx, &u->table,
380 : &FN(UNION,free_u_entry), NULL);
381 0 : isl_hash_table_clear(&u->table);
382 0 : isl_space_free(u->space);
383 0 : free(u);
384 0 : return NULL;
385 : }
386 :
387 0 : static __isl_give PART *FN(UNION,align_entry)(__isl_take PART *part, void *user)
388 : {
389 0 : isl_reordering *exp = user;
390 :
391 0 : exp = isl_reordering_extend_space(isl_reordering_copy(exp),
392 : FN(PART,get_domain_space)(part));
393 0 : return FN(PART,realign_domain)(part, exp);
394 : }
395 :
396 : /* Reorder the parameters of "u" according to the given reordering.
397 : */
398 0 : static __isl_give UNION *FN(UNION,realign_domain)(__isl_take UNION *u,
399 : __isl_take isl_reordering *r)
400 : {
401 : isl_space *space;
402 :
403 0 : if (!u || !r)
404 : goto error;
405 :
406 0 : space = isl_reordering_get_space(r);
407 0 : u = FN(UNION,transform_space)(u, space, &FN(UNION,align_entry), r);
408 0 : isl_reordering_free(r);
409 0 : return u;
410 : error:
411 0 : FN(UNION,free)(u);
412 0 : isl_reordering_free(r);
413 0 : return NULL;
414 : }
415 :
416 : /* Align the parameters of "u" to those of "model".
417 : */
418 0 : __isl_give UNION *FN(UNION,align_params)(__isl_take UNION *u,
419 : __isl_take isl_space *model)
420 : {
421 : isl_bool equal_params;
422 : isl_reordering *r;
423 :
424 0 : if (!u || !model)
425 : goto error;
426 :
427 0 : equal_params = isl_space_has_equal_params(u->space, model);
428 0 : if (equal_params < 0)
429 0 : goto error;
430 0 : if (equal_params) {
431 0 : isl_space_free(model);
432 0 : return u;
433 : }
434 :
435 0 : r = isl_parameter_alignment_reordering(u->space, model);
436 0 : isl_space_free(model);
437 :
438 0 : return FN(UNION,realign_domain)(u, r);
439 : error:
440 0 : isl_space_free(model);
441 0 : FN(UNION,free)(u);
442 0 : return NULL;
443 : }
444 :
445 : /* Add "part" to *u, taking the union sum if "u" already has
446 : * a part defined on the same space as "part".
447 : */
448 0 : static isl_stat FN(UNION,union_add_part)(__isl_take PART *part, void *user)
449 : {
450 0 : UNION **u = (UNION **)user;
451 :
452 0 : *u = FN(UNION,add_part_generic)(*u, part, 0);
453 :
454 0 : return isl_stat_ok;
455 : }
456 :
457 : /* Compute the sum of "u1" and "u2" on the union of their domains,
458 : * with the actual sum on the shared domain and
459 : * the defined expression on the symmetric difference of the domains.
460 : *
461 : * This is an internal function that is exposed under different
462 : * names depending on whether the base expressions have a zero default
463 : * value.
464 : * If they do, then this function is called "add".
465 : * Otherwise, it is called "union_add".
466 : */
467 0 : static __isl_give UNION *FN(UNION,union_add_)(__isl_take UNION *u1,
468 : __isl_take UNION *u2)
469 : {
470 0 : u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
471 0 : u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
472 :
473 0 : u1 = FN(UNION,cow)(u1);
474 :
475 0 : if (!u1 || !u2)
476 : goto error;
477 :
478 0 : if (FN(FN(UNION,foreach),BASE)(u2, &FN(UNION,union_add_part), &u1) < 0)
479 0 : goto error;
480 :
481 0 : FN(UNION,free)(u2);
482 :
483 0 : return u1;
484 : error:
485 0 : FN(UNION,free)(u1);
486 0 : FN(UNION,free)(u2);
487 0 : return NULL;
488 : }
489 :
490 0 : __isl_give UNION *FN(FN(UNION,from),BASE)(__isl_take PART *part)
491 : {
492 : isl_space *dim;
493 : UNION *u;
494 :
495 0 : if (!part)
496 0 : return NULL;
497 :
498 0 : dim = FN(PART,get_space)(part);
499 0 : dim = isl_space_drop_dims(dim, isl_dim_in, 0, isl_space_dim(dim, isl_dim_in));
500 0 : dim = isl_space_drop_dims(dim, isl_dim_out, 0, isl_space_dim(dim, isl_dim_out));
501 : #ifdef HAS_TYPE
502 0 : u = FN(UNION,ZERO)(dim, part->type);
503 : #else
504 0 : u = FN(UNION,ZERO)(dim);
505 : #endif
506 0 : u = FN(FN(UNION,add),BASE)(u, part);
507 :
508 0 : return u;
509 : }
510 :
511 : S(UNION,match_bin_data) {
512 : UNION *u2;
513 : UNION *res;
514 : __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *);
515 : };
516 :
517 : /* Check if data->u2 has an element living in the same space as "part".
518 : * If so, call data->fn on the two elements and add the result to
519 : * data->res.
520 : */
521 0 : static isl_stat FN(UNION,match_bin_entry)(__isl_take PART *part, void *user)
522 : {
523 0 : S(UNION,match_bin_data) *data = user;
524 : struct isl_hash_table_entry *entry2;
525 : isl_space *space;
526 : PART *part2;
527 :
528 0 : space = FN(PART,get_space)(part);
529 0 : entry2 = FN(UNION,find_part_entry)(data->u2, space, 0);
530 0 : isl_space_free(space);
531 0 : if (!entry2)
532 0 : goto error;
533 0 : if (entry2 == isl_hash_table_entry_none) {
534 0 : FN(PART,free)(part);
535 0 : return isl_stat_ok;
536 : }
537 :
538 0 : part2 = entry2->data;
539 0 : if (!isl_space_tuple_is_equal(part->dim, isl_dim_out,
540 : part2->dim, isl_dim_out))
541 0 : isl_die(FN(UNION,get_ctx)(data->u2), isl_error_invalid,
542 : "entries should have the same range space",
543 : goto error);
544 :
545 0 : part = data->fn(part, FN(PART, copy)(entry2->data));
546 :
547 0 : data->res = FN(FN(UNION,add),BASE)(data->res, part);
548 0 : if (!data->res)
549 0 : return isl_stat_error;
550 :
551 0 : return isl_stat_ok;
552 : error:
553 0 : FN(PART,free)(part);
554 0 : return isl_stat_error;
555 : }
556 :
557 : /* This function is currently only used from isl_polynomial.c
558 : * and not from isl_fold.c.
559 : */
560 : static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
561 : __isl_take UNION *u2,
562 : __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
563 : __attribute__ ((unused));
564 : /* For each pair of elements in "u1" and "u2" living in the same space,
565 : * call "fn" and collect the results.
566 : */
567 0 : static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
568 : __isl_take UNION *u2,
569 : __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
570 : {
571 0 : S(UNION,match_bin_data) data = { NULL, NULL, fn };
572 :
573 0 : u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
574 0 : u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
575 :
576 0 : if (!u1 || !u2)
577 : goto error;
578 :
579 0 : data.u2 = u2;
580 0 : data.res = FN(UNION,alloc_same_size)(u1);
581 0 : if (FN(FN(UNION,foreach),BASE)(u1,
582 : &FN(UNION,match_bin_entry), &data) < 0)
583 0 : goto error;
584 :
585 0 : FN(UNION,free)(u1);
586 0 : FN(UNION,free)(u2);
587 0 : return data.res;
588 : error:
589 0 : FN(UNION,free)(u1);
590 0 : FN(UNION,free)(u2);
591 0 : FN(UNION,free)(data.res);
592 0 : return NULL;
593 : }
594 :
595 : /* Compute the sum of "u1" and "u2".
596 : *
597 : * If the base expressions have a default zero value, then the sum
598 : * is computed on the union of the domains of "u1" and "u2".
599 : * Otherwise, it is computed on their shared domains.
600 : */
601 0 : __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
602 : {
603 : #if DEFAULT_IS_ZERO
604 0 : return FN(UNION,union_add_)(u1, u2);
605 : #else
606 0 : return FN(UNION,match_bin_op)(u1, u2, &FN(PART,add));
607 : #endif
608 : }
609 :
610 : #ifndef NO_SUB
611 : /* Subtract "u2" from "u1" and return the result.
612 : */
613 0 : __isl_give UNION *FN(UNION,sub)(__isl_take UNION *u1, __isl_take UNION *u2)
614 : {
615 0 : return FN(UNION,match_bin_op)(u1, u2, &FN(PART,sub));
616 : }
617 : #endif
618 :
619 : S(UNION,any_set_data) {
620 : isl_set *set;
621 : __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
622 : };
623 :
624 0 : static __isl_give PART *FN(UNION,any_set_entry)(__isl_take PART *part,
625 : void *user)
626 : {
627 0 : S(UNION,any_set_data) *data = user;
628 :
629 0 : return data->fn(part, isl_set_copy(data->set));
630 : }
631 :
632 : /* Update each element of "u" by calling "fn" on the element and "set".
633 : */
634 0 : static __isl_give UNION *FN(UNION,any_set_op)(__isl_take UNION *u,
635 : __isl_take isl_set *set,
636 : __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
637 : {
638 0 : S(UNION,any_set_data) data = { NULL, fn };
639 :
640 0 : u = FN(UNION,align_params)(u, isl_set_get_space(set));
641 0 : set = isl_set_align_params(set, FN(UNION,get_space)(u));
642 :
643 0 : if (!u || !set)
644 : goto error;
645 :
646 0 : data.set = set;
647 0 : u = FN(UNION,transform)(u, &FN(UNION,any_set_entry), &data);
648 0 : isl_set_free(set);
649 0 : return u;
650 : error:
651 0 : FN(UNION,free)(u);
652 0 : isl_set_free(set);
653 0 : return NULL;
654 : }
655 :
656 : /* Intersect the domain of "u" with the parameter domain "context".
657 : */
658 0 : __isl_give UNION *FN(UNION,intersect_params)(__isl_take UNION *u,
659 : __isl_take isl_set *set)
660 : {
661 0 : return FN(UNION,any_set_op)(u, set, &FN(PW,intersect_params));
662 : }
663 :
664 : /* Compute the gist of the domain of "u" with respect to
665 : * the parameter domain "context".
666 : */
667 0 : __isl_give UNION *FN(UNION,gist_params)(__isl_take UNION *u,
668 : __isl_take isl_set *set)
669 : {
670 0 : return FN(UNION,any_set_op)(u, set, &FN(PW,gist_params));
671 : }
672 :
673 : S(UNION,match_domain_data) {
674 : isl_union_set *uset;
675 : UNION *res;
676 : __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
677 : };
678 :
679 0 : static int FN(UNION,set_has_dim)(const void *entry, const void *val)
680 : {
681 0 : isl_set *set = (isl_set *)entry;
682 0 : isl_space *dim = (isl_space *)val;
683 :
684 0 : return isl_space_is_equal(set->dim, dim);
685 : }
686 :
687 : /* Find the set in data->uset that lives in the same space as the domain
688 : * of "part", apply data->fn to *entry and this set (if any), and add
689 : * the result to data->res.
690 : */
691 0 : static isl_stat FN(UNION,match_domain_entry)(__isl_take PART *part, void *user)
692 : {
693 0 : S(UNION,match_domain_data) *data = user;
694 : uint32_t hash;
695 : struct isl_hash_table_entry *entry2;
696 : isl_space *space;
697 :
698 0 : space = FN(PART,get_domain_space)(part);
699 0 : hash = isl_space_get_hash(space);
700 0 : entry2 = isl_hash_table_find(data->uset->dim->ctx, &data->uset->table,
701 : hash, &FN(UNION,set_has_dim), space, 0);
702 0 : isl_space_free(space);
703 0 : if (!entry2) {
704 0 : FN(PART,free)(part);
705 0 : return isl_stat_ok;
706 : }
707 :
708 0 : part = data->fn(part, isl_set_copy(entry2->data));
709 :
710 0 : data->res = FN(FN(UNION,add),BASE)(data->res, part);
711 0 : if (!data->res)
712 0 : return isl_stat_error;
713 :
714 0 : return isl_stat_ok;
715 : }
716 :
717 : /* Apply fn to each pair of PW in u and set in uset such that
718 : * the set lives in the same space as the domain of PW
719 : * and collect the results.
720 : */
721 0 : static __isl_give UNION *FN(UNION,match_domain_op)(__isl_take UNION *u,
722 : __isl_take isl_union_set *uset,
723 : __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
724 : {
725 0 : S(UNION,match_domain_data) data = { NULL, NULL, fn };
726 :
727 0 : u = FN(UNION,align_params)(u, isl_union_set_get_space(uset));
728 0 : uset = isl_union_set_align_params(uset, FN(UNION,get_space)(u));
729 :
730 0 : if (!u || !uset)
731 : goto error;
732 :
733 0 : data.uset = uset;
734 0 : data.res = FN(UNION,alloc_same_size)(u);
735 0 : if (FN(FN(UNION,foreach),BASE)(u,
736 : &FN(UNION,match_domain_entry), &data) < 0)
737 0 : goto error;
738 :
739 0 : FN(UNION,free)(u);
740 0 : isl_union_set_free(uset);
741 0 : return data.res;
742 : error:
743 0 : FN(UNION,free)(u);
744 0 : isl_union_set_free(uset);
745 0 : FN(UNION,free)(data.res);
746 0 : return NULL;
747 : }
748 :
749 : /* Intersect the domain of "u" with "uset".
750 : * If "uset" is a parameters domain, then intersect the parameter
751 : * domain of "u" with this set.
752 : */
753 0 : __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
754 : __isl_take isl_union_set *uset)
755 : {
756 0 : if (isl_union_set_is_params(uset))
757 0 : return FN(UNION,intersect_params)(u,
758 : isl_set_from_union_set(uset));
759 0 : return FN(UNION,match_domain_op)(u, uset, &FN(PW,intersect_domain));
760 : }
761 :
762 : /* Take the set (which may be empty) in data->uset that lives
763 : * in the same space as the domain of "pw", subtract it from the domain
764 : * of "part" and return the result.
765 : */
766 0 : static __isl_give PART *FN(UNION,subtract_domain_entry)(__isl_take PART *part,
767 : void *user)
768 : {
769 0 : isl_union_set *uset = user;
770 : isl_space *space;
771 : isl_set *set;
772 :
773 0 : space = FN(PART,get_domain_space)(part);
774 0 : set = isl_union_set_extract_set(uset, space);
775 0 : return FN(PART,subtract_domain)(part, set);
776 : }
777 :
778 : /* Subtract "uset' from the domain of "u".
779 : */
780 0 : __isl_give UNION *FN(UNION,subtract_domain)(__isl_take UNION *u,
781 : __isl_take isl_union_set *uset)
782 : {
783 0 : u = FN(UNION,transform)(u, &FN(UNION,subtract_domain_entry), uset);
784 0 : isl_union_set_free(uset);
785 0 : return u;
786 : }
787 :
788 0 : __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
789 : __isl_take isl_union_set *uset)
790 : {
791 0 : if (isl_union_set_is_params(uset))
792 0 : return FN(UNION,gist_params)(u, isl_set_from_union_set(uset));
793 0 : return FN(UNION,match_domain_op)(u, uset, &FN(PW,gist));
794 : }
795 :
796 : /* Coalesce an entry in a UNION. Coalescing is performed in-place.
797 : * Since the UNION may have several references, the entry is only
798 : * replaced if the coalescing is successful.
799 : */
800 0 : static isl_stat FN(UNION,coalesce_entry)(void **entry, void *user)
801 : {
802 0 : PART **part_p = (PART **) entry;
803 : PART *part;
804 :
805 0 : part = FN(PART,copy)(*part_p);
806 0 : part = FN(PW,coalesce)(part);
807 0 : if (!part)
808 0 : return isl_stat_error;
809 0 : FN(PART,free)(*part_p);
810 0 : *part_p = part;
811 :
812 0 : return isl_stat_ok;
813 : }
814 :
815 0 : __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
816 : {
817 0 : if (FN(UNION,foreach_inplace)(u, &FN(UNION,coalesce_entry), NULL) < 0)
818 0 : goto error;
819 :
820 0 : return u;
821 : error:
822 0 : FN(UNION,free)(u);
823 0 : return NULL;
824 : }
825 :
826 0 : static isl_stat FN(UNION,domain_entry)(__isl_take PART *part, void *user)
827 : {
828 0 : isl_union_set **uset = (isl_union_set **)user;
829 :
830 0 : *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
831 :
832 0 : return isl_stat_ok;
833 : }
834 :
835 0 : __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
836 : {
837 : isl_union_set *uset;
838 :
839 0 : uset = isl_union_set_empty(FN(UNION,get_space)(u));
840 0 : if (FN(FN(UNION,foreach),BASE)(u, &FN(UNION,domain_entry), &uset) < 0)
841 0 : goto error;
842 :
843 0 : FN(UNION,free)(u);
844 :
845 0 : return uset;
846 : error:
847 0 : isl_union_set_free(uset);
848 0 : FN(UNION,free)(u);
849 0 : return NULL;
850 : }
851 :
852 : #ifdef HAS_TYPE
853 : /* Negate the type of "u".
854 : */
855 0 : static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u)
856 : {
857 0 : u = FN(UNION,cow)(u);
858 0 : if (!u)
859 0 : return NULL;
860 0 : u->type = isl_fold_type_negate(u->type);
861 0 : return u;
862 : }
863 : #else
864 : /* Negate the type of "u".
865 : * Since "u" does not have a type, do nothing.
866 : */
867 0 : static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u)
868 : {
869 0 : return u;
870 : }
871 : #endif
872 :
873 : /* Multiply "part" by the isl_val "user" and return the result.
874 : */
875 0 : static __isl_give PART *FN(UNION,scale_val_entry)(__isl_take PART *part,
876 : void *user)
877 : {
878 0 : isl_val *v = user;
879 :
880 0 : return FN(PART,scale_val)(part, isl_val_copy(v));
881 : }
882 :
883 : /* Multiply "u" by "v" and return the result.
884 : */
885 0 : __isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u,
886 : __isl_take isl_val *v)
887 : {
888 0 : if (!u || !v)
889 : goto error;
890 0 : if (isl_val_is_one(v)) {
891 0 : isl_val_free(v);
892 0 : return u;
893 : }
894 :
895 0 : if (DEFAULT_IS_ZERO && u && isl_val_is_zero(v)) {
896 : UNION *zero;
897 0 : isl_space *space = FN(UNION,get_space)(u);
898 : #ifdef HAS_TYPE
899 0 : zero = FN(UNION,ZERO)(space, u->type);
900 : #else
901 0 : zero = FN(UNION,ZERO)(space);
902 : #endif
903 0 : FN(UNION,free)(u);
904 0 : isl_val_free(v);
905 0 : return zero;
906 : }
907 :
908 0 : if (!isl_val_is_rat(v))
909 0 : isl_die(isl_val_get_ctx(v), isl_error_invalid,
910 : "expecting rational factor", goto error);
911 :
912 0 : u = FN(UNION,transform_inplace)(u, &FN(UNION,scale_val_entry), v);
913 0 : if (isl_val_is_neg(v))
914 0 : u = FN(UNION,negate_type)(u);
915 :
916 0 : isl_val_free(v);
917 0 : return u;
918 : error:
919 0 : isl_val_free(v);
920 0 : FN(UNION,free)(u);
921 0 : return NULL;
922 : }
923 :
924 : /* Divide "part" by the isl_val "user" and return the result.
925 : */
926 0 : static __isl_give PART *FN(UNION,scale_down_val_entry)(__isl_take PART *part,
927 : void *user)
928 : {
929 0 : isl_val *v = user;
930 :
931 0 : return FN(PART,scale_down_val)(part, isl_val_copy(v));
932 : }
933 :
934 : /* Divide "u" by "v" and return the result.
935 : */
936 0 : __isl_give UNION *FN(UNION,scale_down_val)(__isl_take UNION *u,
937 : __isl_take isl_val *v)
938 : {
939 0 : if (!u || !v)
940 : goto error;
941 0 : if (isl_val_is_one(v)) {
942 0 : isl_val_free(v);
943 0 : return u;
944 : }
945 :
946 0 : if (!isl_val_is_rat(v))
947 0 : isl_die(isl_val_get_ctx(v), isl_error_invalid,
948 : "expecting rational factor", goto error);
949 0 : if (isl_val_is_zero(v))
950 0 : isl_die(isl_val_get_ctx(v), isl_error_invalid,
951 : "cannot scale down by zero", goto error);
952 :
953 0 : u = FN(UNION,transform_inplace)(u, &FN(UNION,scale_down_val_entry), v);
954 0 : if (isl_val_is_neg(v))
955 0 : u = FN(UNION,negate_type)(u);
956 :
957 0 : isl_val_free(v);
958 0 : return u;
959 : error:
960 0 : isl_val_free(v);
961 0 : FN(UNION,free)(u);
962 0 : return NULL;
963 : }
964 :
965 : S(UNION,plain_is_equal_data)
966 : {
967 : UNION *u2;
968 : isl_bool is_equal;
969 : };
970 :
971 0 : static isl_stat FN(UNION,plain_is_equal_entry)(void **entry, void *user)
972 : {
973 0 : S(UNION,plain_is_equal_data) *data = user;
974 : struct isl_hash_table_entry *entry2;
975 0 : PW *pw = *entry;
976 :
977 0 : entry2 = FN(UNION,find_part_entry)(data->u2, pw->dim, 0);
978 0 : if (!entry2 || entry2 == isl_hash_table_entry_none) {
979 0 : if (!entry2)
980 0 : data->is_equal = isl_bool_error;
981 : else
982 0 : data->is_equal = isl_bool_false;
983 0 : return isl_stat_error;
984 : }
985 :
986 0 : data->is_equal = FN(PW,plain_is_equal)(pw, entry2->data);
987 0 : if (data->is_equal < 0 || !data->is_equal)
988 0 : return isl_stat_error;
989 :
990 0 : return isl_stat_ok;
991 : }
992 :
993 0 : isl_bool FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2)
994 : {
995 0 : S(UNION,plain_is_equal_data) data = { NULL, isl_bool_true };
996 : int n1, n2;
997 :
998 0 : if (!u1 || !u2)
999 0 : return isl_bool_error;
1000 0 : if (u1 == u2)
1001 0 : return isl_bool_true;
1002 0 : if (u1->table.n != u2->table.n)
1003 0 : return isl_bool_false;
1004 0 : n1 = FN(FN(UNION,n),BASE)(u1);
1005 0 : n2 = FN(FN(UNION,n),BASE)(u2);
1006 0 : if (n1 < 0 || n2 < 0)
1007 0 : return isl_bool_error;
1008 0 : if (n1 != n2)
1009 0 : return isl_bool_false;
1010 :
1011 0 : u1 = FN(UNION,copy)(u1);
1012 0 : u2 = FN(UNION,copy)(u2);
1013 0 : u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
1014 0 : u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
1015 0 : if (!u1 || !u2)
1016 : goto error;
1017 :
1018 0 : data.u2 = u2;
1019 0 : if (FN(UNION,foreach_inplace)(u1,
1020 0 : &FN(UNION,plain_is_equal_entry), &data) < 0 &&
1021 0 : data.is_equal)
1022 0 : goto error;
1023 :
1024 0 : FN(UNION,free)(u1);
1025 0 : FN(UNION,free)(u2);
1026 :
1027 0 : return data.is_equal;
1028 : error:
1029 0 : FN(UNION,free)(u1);
1030 0 : FN(UNION,free)(u2);
1031 0 : return isl_bool_error;
1032 : }
1033 :
1034 : /* Check whether the element that "entry" points to involves any NaNs and
1035 : * store the result in *nan.
1036 : * Abort as soon as one such element has been found.
1037 : */
1038 0 : static isl_stat FN(UNION,involves_nan_entry)(void **entry, void *user)
1039 : {
1040 0 : isl_bool *nan = user;
1041 0 : PW *pw = *entry;
1042 :
1043 0 : *nan = FN(PW,involves_nan)(pw);
1044 0 : if (*nan < 0 || !nan)
1045 0 : return isl_stat_error;
1046 :
1047 0 : return isl_stat_ok;
1048 : }
1049 :
1050 : /* Does "u" involve any NaNs?
1051 : */
1052 0 : isl_bool FN(UNION,involves_nan)(__isl_keep UNION *u)
1053 : {
1054 0 : isl_bool nan = isl_bool_false;
1055 :
1056 0 : if (!u)
1057 0 : return isl_bool_error;
1058 :
1059 0 : if (FN(UNION,foreach_inplace)(u,
1060 0 : &FN(UNION,involves_nan_entry), &nan) < 0 &&
1061 0 : !nan)
1062 0 : return isl_bool_error;
1063 :
1064 0 : return nan;
1065 : }
1066 :
1067 : /* Internal data structure for isl_union_*_drop_dims.
1068 : * type, first and n are passed to isl_*_drop_dims.
1069 : */
1070 : S(UNION,drop_dims_data) {
1071 : enum isl_dim_type type;
1072 : unsigned first;
1073 : unsigned n;
1074 : };
1075 :
1076 : /* Drop the parameters specified by "data" from "part" and return the result.
1077 : */
1078 0 : static __isl_give PART *FN(UNION,drop_dims_entry)(__isl_take PART *part,
1079 : void *user)
1080 : {
1081 0 : S(UNION,drop_dims_data) *data = user;
1082 :
1083 0 : return FN(PART,drop_dims)(part, data->type, data->first, data->n);
1084 : }
1085 :
1086 : /* Drop the specified parameters from "u".
1087 : * That is, type is required to be isl_dim_param.
1088 : */
1089 0 : __isl_give UNION *FN(UNION,drop_dims)( __isl_take UNION *u,
1090 : enum isl_dim_type type, unsigned first, unsigned n)
1091 : {
1092 : isl_space *space;
1093 0 : S(UNION,drop_dims_data) data = { type, first, n };
1094 :
1095 0 : if (!u)
1096 0 : return NULL;
1097 :
1098 0 : if (type != isl_dim_param)
1099 0 : isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1100 : "can only project out parameters",
1101 : return FN(UNION,free)(u));
1102 :
1103 0 : space = FN(UNION,get_space)(u);
1104 0 : space = isl_space_drop_dims(space, type, first, n);
1105 0 : return FN(UNION,transform_space)(u, space, &FN(UNION,drop_dims_entry),
1106 : &data);
1107 : }
1108 :
1109 : /* Internal data structure for isl_union_*_set_dim_name.
1110 : * pos is the position of the parameter that needs to be renamed.
1111 : * s is the new name.
1112 : */
1113 : S(UNION,set_dim_name_data) {
1114 : unsigned pos;
1115 : const char *s;
1116 : };
1117 :
1118 : /* Change the name of the parameter at position data->pos of "part" to data->s
1119 : * and return the result.
1120 : */
1121 0 : static __isl_give PART *FN(UNION,set_dim_name_entry)(__isl_take PART *part,
1122 : void *user)
1123 : {
1124 0 : S(UNION,set_dim_name_data) *data = user;
1125 :
1126 0 : return FN(PART,set_dim_name)(part, isl_dim_param, data->pos, data->s);
1127 : }
1128 :
1129 : /* Change the name of the parameter at position "pos" to "s".
1130 : * That is, type is required to be isl_dim_param.
1131 : */
1132 0 : __isl_give UNION *FN(UNION,set_dim_name)(__isl_take UNION *u,
1133 : enum isl_dim_type type, unsigned pos, const char *s)
1134 : {
1135 0 : S(UNION,set_dim_name_data) data = { pos, s };
1136 : isl_space *space;
1137 :
1138 0 : if (!u)
1139 0 : return NULL;
1140 :
1141 0 : if (type != isl_dim_param)
1142 0 : isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1143 : "can only set parameter names",
1144 : return FN(UNION,free)(u));
1145 :
1146 0 : space = FN(UNION,get_space)(u);
1147 0 : space = isl_space_set_dim_name(space, type, pos, s);
1148 0 : return FN(UNION,transform_space)(u, space,
1149 : &FN(UNION,set_dim_name_entry), &data);
1150 : }
1151 :
1152 : /* Reset the user pointer on all identifiers of parameters and tuples
1153 : * of the space of "part" and return the result.
1154 : */
1155 0 : static __isl_give PART *FN(UNION,reset_user_entry)(__isl_take PART *part,
1156 : void *user)
1157 : {
1158 0 : return FN(PART,reset_user)(part);
1159 : }
1160 :
1161 : /* Reset the user pointer on all identifiers of parameters and tuples
1162 : * of the spaces of "u".
1163 : */
1164 0 : __isl_give UNION *FN(UNION,reset_user)(__isl_take UNION *u)
1165 : {
1166 : isl_space *space;
1167 :
1168 0 : space = FN(UNION,get_space)(u);
1169 0 : space = isl_space_reset_user(space);
1170 0 : return FN(UNION,transform_space)(u, space, &FN(UNION,reset_user_entry),
1171 : NULL);
1172 : }
1173 :
1174 : /* Add the base expression held by "entry" to "list".
1175 : */
1176 0 : static isl_stat FN(UNION,add_to_list)(void **entry, void *user)
1177 : {
1178 0 : PW *pw = *entry;
1179 0 : LIST(PART) **list = user;
1180 :
1181 0 : *list = FN(LIST(PART),add)(*list, FN(PART,copy)(pw));
1182 0 : if (!*list)
1183 0 : return isl_stat_error;
1184 :
1185 0 : return isl_stat_ok;
1186 : }
1187 :
1188 : /* Return a list containing all the base expressions in "u".
1189 : *
1190 : * First construct a list of the appropriate size and
1191 : * then add all the elements.
1192 : */
1193 0 : __isl_give LIST(PART) *FN(FN(UNION,get),LIST(BASE))(__isl_keep UNION *u)
1194 : {
1195 : int n;
1196 : LIST(PART) *list;
1197 :
1198 0 : if (!u)
1199 0 : return NULL;
1200 0 : n = FN(FN(UNION,n),BASE)(u);
1201 0 : if (n < 0)
1202 0 : return NULL;
1203 0 : list = FN(LIST(PART),alloc)(FN(UNION,get_ctx(u)), n);
1204 0 : if (FN(UNION,foreach_inplace)(u, &FN(UNION,add_to_list), &list) < 0)
1205 0 : return FN(LIST(PART),free)(list);
1206 :
1207 0 : return list;
1208 : }
|
