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