?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
pip.c: remove spurious include
[isl.git] / isl_union_templ.c
blobd16ccd94aa3ff35a5f7171472a4b44066f082a06
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 isl_ctx *FN(UNION,get_ctx)(__isl_keep UNION *u)
21 {
22 return u ? u->space->ctx : NULL;
23 }
24
25 /* Return the space of "u".
26 */
27 static __isl_keep isl_space *FN(UNION,peek_space)(__isl_keep UNION *u)
28 {
29 if (!u)
30 return NULL;
31 return u->space;
32 }
33
34 /* Return a copy of the space of "u".
35 */
36 __isl_give isl_space *FN(UNION,get_space)(__isl_keep UNION *u)
37 {
38 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 isl_size FN(UNION,dim)(__isl_keep UNION *u, enum isl_dim_type type)
45 {
46 if (!u)
47 return isl_size_error;
48
49 if (type != isl_dim_param)
50 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
51 "can only reference parameters", return isl_size_error);
52
53 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 int FN(UNION,find_dim_by_name)(__isl_keep UNION *u, enum isl_dim_type type,
61 const char *name)
62 {
63 if (!u)
64 return -1;
65 return isl_space_find_dim_by_name(u->space, type, name);
66 }
67
68 #include "opt_type.h"
69
70 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *space
71 OPT_TYPE_PARAM, int size)
72 {
73 UNION *u;
74
75 space = isl_space_params(space);
76 if (!space)
77 return NULL;
78
79 u = isl_calloc_type(space->ctx, UNION);
80 if (!u)
81 goto error;
82
83 u->ref = 1;
84 OPT_SET_TYPE(u->, type);
85 u->space = space;
86 if (isl_hash_table_init(space->ctx, &u->table, size) < 0)
87 return FN(UNION,free)(u);
88
89 return u;
90 error:
91 isl_space_free(space);
92 return NULL;
93 }
94
95 /* Create an empty/zero union without specifying any parameters.
96 */
97 __isl_give UNION *FN(FN(UNION,ZERO),ctx)(isl_ctx *ctx OPT_TYPE_PARAM)
98 {
99 isl_space *space;
100
101 space = isl_space_unit(ctx);
102 return FN(FN(UNION,ZERO),space)(space OPT_TYPE_ARG(NO_LOC));
103 }
104
105 __isl_give UNION *FN(FN(UNION,ZERO),space)(__isl_take isl_space *space
106 OPT_TYPE_PARAM)
107 {
108 return FN(UNION,alloc)(space OPT_TYPE_ARG(NO_LOC), 16);
109 }
110
111 /* This is an alternative name for the function above.
112 */
113 __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *space OPT_TYPE_PARAM)
114 {
115 return FN(FN(UNION,ZERO),space)(space OPT_TYPE_ARG(NO_LOC));
116 }
117
118 __isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u)
119 {
120 if (!u)
121 return NULL;
122
123 u->ref++;
124 return u;
125 }
126
127 /* Do the tuples of "space" correspond to those of the domain of "part"?
128 * That is, is the domain space of "part" equal to "space", ignoring parameters?
129 */
130 static isl_bool FN(PART,has_domain_space_tuples)(__isl_keep PART *part,
131 __isl_keep isl_space *space)
132 {
133 return isl_space_has_domain_tuples(space, FN(PART,peek_space)(part));
134 }
135
136 /* Extract the element of "u" living in "space" (ignoring parameters).
137 *
138 * Return the ZERO element if "u" does not contain any element
139 * living in "space".
140 */
141 __isl_give PART *FN(FN(UNION,extract),BASE)(__isl_keep UNION *u,
142 __isl_take isl_space *space)
143 {
144 struct isl_hash_table_entry *entry;
145
146 entry = FN(UNION,find_part_entry)(u, space, 0);
147 if (!entry)
148 goto error;
149 if (entry == isl_hash_table_entry_none)
150 return FN(PART,ZERO)(space OPT_TYPE_ARG(u->));
151 isl_space_free(space);
152 return FN(PART,copy)(entry->data);
153 error:
154 isl_space_free(space);
155 return NULL;
156 }
157
158 /* Add "part" to "u".
159 * If "disjoint" is set, then "u" is not allowed to already have
160 * a part that is defined over a domain that overlaps with the domain
161 * of "part".
162 * Otherwise, compute the union sum of "part" and the part in "u"
163 * defined on the same space.
164 */
165 static __isl_give UNION *FN(UNION,add_part_generic)(__isl_take UNION *u,
166 __isl_take PART *part, int disjoint)
167 {
168 int empty;
169 struct isl_hash_table_entry *entry;
170
171 if (!part)
172 goto error;
173
174 empty = FN(PART,IS_ZERO)(part);
175 if (empty < 0)
176 goto error;
177 if (empty) {
178 FN(PART,free)(part);
179 return u;
180 }
181
182 u = FN(UNION,align_params)(u, FN(PART,get_space)(part));
183 part = FN(PART,align_params)(part, FN(UNION,get_space)(u));
184
185 u = FN(UNION,cow)(u);
186
187 if (!u)
188 goto error;
189
190 if (FN(UNION,check_disjoint_domain_other)(u, part) < 0)
191 goto error;
192 entry = FN(UNION,find_part_entry)(u, part->dim, 1);
193 if (!entry)
194 goto error;
195
196 if (!entry->data)
197 entry->data = part;
198 else {
199 if (disjoint &&
200 FN(UNION,check_disjoint_domain)(entry->data, part) < 0)
201 goto error;
202 entry->data = FN(PART,union_add_)(entry->data,
203 FN(PART,copy)(part));
204 if (!entry->data)
205 goto error;
206 empty = FN(PART,IS_ZERO)(part);
207 if (empty < 0)
208 goto error;
209 if (empty)
210 u = FN(UNION,remove_part_entry)(u, entry);
211 FN(PART,free)(part);
212 }
213
214 return u;
215 error:
216 FN(PART,free)(part);
217 FN(UNION,free)(u);
218 return NULL;
219 }
220
221 /* Add "part" to "u", where "u" is assumed not to already have
222 * a part that is defined on the same space as "part".
223 */
224 __isl_give UNION *FN(FN(UNION,add),BASE)(__isl_take UNION *u,
225 __isl_take PART *part)
226 {
227 return FN(UNION,add_part_generic)(u, part, 1);
228 }
229
230 /* Allocate a UNION with the same type (if any) and the same size as "u" and
231 * with space "space".
232 */
233 static __isl_give UNION *FN(UNION,alloc_same_size_on_space)(__isl_keep UNION *u,
234 __isl_take isl_space *space)
235 {
236 if (!u)
237 goto error;
238 return FN(UNION,alloc)(space OPT_TYPE_ARG(u->), u->table.n);
239 error:
240 isl_space_free(space);
241 return NULL;
242 }
243
244 /* Allocate a UNION with the same space, the same type (if any) and
245 * the same size as "u".
246 */
247 static __isl_give UNION *FN(UNION,alloc_same_size)(__isl_keep UNION *u)
248 {
249 return FN(UNION,alloc_same_size_on_space)(u, FN(UNION,get_space)(u));
250 }
251
252 /* Data structure that specifies how isl_union_*_transform
253 * should modify the base expressions in the union expression.
254 *
255 * If "inplace" is set, then the base expression in the input union
256 * are modified in place. This means that "fn" should not
257 * change the meaning of the union or that the union only
258 * has a single reference.
259 * If "space" is not NULL, then a new union is created in this space.
260 * If "filter" is not NULL, then only the base expressions that satisfy "filter"
261 * are taken into account.
262 * "filter_user" is passed as the second argument to "filter".
263 * If "fn" it not NULL, then it is applied to each entry in the input.
264 * "fn_user" is passed as the second argument to "fn".
265 */
266 S(UNION,transform_control) {
267 int inplace;
268 isl_space *space;
269 isl_bool (*filter)(__isl_keep PART *part, void *user);
270 void *filter_user;
271 __isl_give PART *(*fn)(__isl_take PART *part, void *user);
272 void *fn_user;
273 };
274
275 /* Internal data structure for isl_union_*_transform_space.
276 * "control" specifies how the base expressions should be modified.
277 * "res" collects the results (if control->inplace is not set).
278 */
279 S(UNION,transform_data)
280 {
281 S(UNION,transform_control) *control;
282 UNION *res;
283 };
284
285 /* Apply control->fn to "part" and add the result to data->res or
286 * place it back into the input union if control->inplace is set.
287 */
288 static isl_stat FN(UNION,transform_entry)(void **entry, void *user)
289 {
290 S(UNION,transform_data) *data = (S(UNION,transform_data) *)user;
291 S(UNION,transform_control) *control = data->control;
292 PART *part = *entry;
293
294 if (control->filter) {
295 isl_bool handle;
296
297 handle = control->filter(part, control->filter_user);
298 if (handle < 0)
299 return isl_stat_error;
300 if (!handle)
301 return isl_stat_ok;
302 }
303
304 if (!control->inplace)
305 part = FN(PART,copy)(part);
306 if (control->fn)
307 part = control->fn(part, control->fn_user);
308 if (control->inplace)
309 *entry = part;
310 else
311 data->res = FN(FN(UNION,add),BASE)(data->res, part);
312 if (!part || !data->res)
313 return isl_stat_error;
314
315 return isl_stat_ok;
316 }
317
318 /* Return a UNION that is obtained by modifying "u" according to "control".
319 */
320 static __isl_give UNION *FN(UNION,transform)(__isl_take UNION *u,
321 S(UNION,transform_control) *control)
322 {
323 S(UNION,transform_data) data = { control };
324 isl_space *space;
325
326 if (control->inplace) {
327 data.res = u;
328 } else {
329 if (control->space)
330 space = isl_space_copy(control->space);
331 else
332 space = FN(UNION,get_space)(u);
333 data.res = FN(UNION,alloc_same_size_on_space)(u, space);
334 }
335 if (FN(UNION,foreach_inplace)(u, &FN(UNION,transform_entry), &data) < 0)
336 data.res = FN(UNION,free)(data.res);
337 if (!control->inplace)
338 FN(UNION,free)(u);
339 return data.res;
340 }
341
342 /* Return a UNION living in "space" that is otherwise obtained by modifying "u"
343 * according to "control".
344 */
345 static __isl_give UNION *FN(UNION,transform_space)(__isl_take UNION *u,
346 __isl_take isl_space *space, S(UNION,transform_control) *control)
347 {
348 if (!space)
349 return FN(UNION,free)(u);
350 control->space = space;
351 u = FN(UNION,transform)(u, control);
352 isl_space_free(space);
353 return u;
354 }
355
356 /* Update "u" by applying "fn" to each entry.
357 * This operation is assumed not to change the number of entries nor
358 * the spaces of the entries.
359 *
360 * If there is only one reference to "u", then change "u" inplace.
361 * Otherwise, create a new UNION from "u" and discard the original.
362 */
363 static __isl_give UNION *FN(UNION,transform_inplace)(__isl_take UNION *u,
364 __isl_give PART *(*fn)(__isl_take PART *part, void *user), void *user)
365 {
366 S(UNION,transform_control) control = { .fn = fn, .fn_user = user };
367 isl_bool single_ref;
368
369 single_ref = FN(UNION,has_single_reference)(u);
370 if (single_ref < 0)
371 return FN(UNION,free)(u);
372 if (single_ref)
373 control.inplace = 1;
374 return FN(UNION,transform)(u, &control);
375 }
376
377 /* An isl_union_*_transform callback for use in isl_union_*_dup
378 * that simply returns "part".
379 */
380 static __isl_give PART *FN(UNION,copy_part)(__isl_take PART *part, void *user)
381 {
382 return part;
383 }
384
385 __isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u)
386 {
387 S(UNION,transform_control) control = { .fn = &FN(UNION,copy_part) };
388
389 u = FN(UNION,copy)(u);
390 return FN(UNION,transform)(u, &control);
391 }
392
393 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u)
394 {
395 if (!u)
396 return NULL;
397
398 if (u->ref == 1)
399 return u;
400 u->ref--;
401 return FN(UNION,dup)(u);
402 }
403
404 __isl_null UNION *FN(UNION,free)(__isl_take UNION *u)
405 {
406 if (!u)
407 return NULL;
408
409 if (--u->ref > 0)
410 return NULL;
411
412 isl_hash_table_foreach(u->space->ctx, &u->table,
413 &FN(UNION,free_u_entry), NULL);
414 isl_hash_table_clear(&u->table);
415 isl_space_free(u->space);
416 free(u);
417 return NULL;
418 }
419
420 static __isl_give PART *FN(UNION,align_entry)(__isl_take PART *part, void *user)
421 {
422 isl_reordering *exp = user;
423
424 exp = isl_reordering_extend_space(isl_reordering_copy(exp),
425 FN(PART,get_domain_space)(part));
426 return FN(PART,realign_domain)(part, exp);
427 }
428
429 /* Reorder the parameters of "u" according to the given reordering.
430 */
431 static __isl_give UNION *FN(UNION,realign_domain)(__isl_take UNION *u,
432 __isl_take isl_reordering *r)
433 {
434 S(UNION,transform_control) control = {
435 .fn = &FN(UNION,align_entry),
436 .fn_user = r,
437 };
438 isl_space *space;
439
440 if (!u || !r)
441 goto error;
442
443 space = isl_reordering_get_space(r);
444 u = FN(UNION,transform_space)(u, space, &control);
445 isl_reordering_free(r);
446 return u;
447 error:
448 FN(UNION,free)(u);
449 isl_reordering_free(r);
450 return NULL;
451 }
452
453 /* Align the parameters of "u" to those of "model".
454 */
455 __isl_give UNION *FN(UNION,align_params)(__isl_take UNION *u,
456 __isl_take isl_space *model)
457 {
458 isl_bool equal_params;
459 isl_reordering *r;
460
461 if (!u || !model)
462 goto error;
463
464 equal_params = isl_space_has_equal_params(u->space, model);
465 if (equal_params < 0)
466 goto error;
467 if (equal_params) {
468 isl_space_free(model);
469 return u;
470 }
471
472 r = isl_parameter_alignment_reordering(u->space, model);
473 isl_space_free(model);
474
475 return FN(UNION,realign_domain)(u, r);
476 error:
477 isl_space_free(model);
478 FN(UNION,free)(u);
479 return NULL;
480 }
481
482 /* Add "part" to *u, taking the union sum if "u" already has
483 * a part defined on the same space as "part".
484 */
485 static isl_stat FN(UNION,union_add_part)(__isl_take PART *part, void *user)
486 {
487 UNION **u = (UNION **)user;
488
489 *u = FN(UNION,add_part_generic)(*u, part, 0);
490
491 return isl_stat_ok;
492 }
493
494 /* Compute the sum of "u1" and "u2" on the union of their domains,
495 * with the actual sum on the shared domain and
496 * the defined expression on the symmetric difference of the domains.
497 *
498 * This is an internal function that is exposed under different
499 * names depending on whether the base expressions have a zero default
500 * value.
501 * If they do, then this function is called "add".
502 * Otherwise, it is called "union_add".
503 */
504 static __isl_give UNION *FN(UNION,union_add_)(__isl_take UNION *u1,
505 __isl_take UNION *u2)
506 {
507 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
508 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
509
510 u1 = FN(UNION,cow)(u1);
511
512 if (!u1 || !u2)
513 goto error;
514
515 if (FN(FN(UNION,foreach),BASE)(u2, &FN(UNION,union_add_part), &u1) < 0)
516 goto error;
517
518 FN(UNION,free)(u2);
519
520 return u1;
521 error:
522 FN(UNION,free)(u1);
523 FN(UNION,free)(u2);
524 return NULL;
525 }
526
527 __isl_give UNION *FN(FN(UNION,from),BASE)(__isl_take PART *part)
528 {
529 isl_space *space;
530 UNION *u;
531
532 if (!part)
533 return NULL;
534
535 space = FN(PART,get_space)(part);
536 space = isl_space_drop_dims(space, isl_dim_in, 0,
537 isl_space_dim(space, isl_dim_in));
538 space = isl_space_drop_dims(space, isl_dim_out, 0,
539 isl_space_dim(space, isl_dim_out));
540 u = FN(UNION,ZERO)(space OPT_TYPE_ARG(part->));
541 u = FN(FN(UNION,add),BASE)(u, part);
542
543 return u;
544 }
545
546 /* This function performs the same operation as isl_union_pw_*_from_pw_*,
547 * but is considered as a function on an isl_pw_* when exported.
548 */
549 __isl_give UNION *FN(FN(PART,to_union),BASE)(__isl_take PART *part)
550 {
551 return FN(FN(UNION,from),BASE)(part);
552 }
553
554 S(UNION,match_bin_data) {
555 UNION *u2;
556 UNION *res;
557 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *);
558 };
559
560 /* Check if data->u2 has an element living in the same space as "part".
561 * If so, call data->fn on the two elements and add the result to
562 * data->res.
563 */
564 static isl_stat FN(UNION,match_bin_entry)(__isl_take PART *part, void *user)
565 {
566 S(UNION,match_bin_data) *data = user;
567 struct isl_hash_table_entry *entry2;
568 isl_space *space;
569 PART *part2;
570
571 space = FN(PART,get_space)(part);
572 entry2 = FN(UNION,find_part_entry)(data->u2, space, 0);
573 isl_space_free(space);
574 if (!entry2)
575 goto error;
576 if (entry2 == isl_hash_table_entry_none) {
577 FN(PART,free)(part);
578 return isl_stat_ok;
579 }
580
581 part2 = entry2->data;
582 if (!isl_space_tuple_is_equal(part->dim, isl_dim_out,
583 part2->dim, isl_dim_out))
584 isl_die(FN(UNION,get_ctx)(data->u2), isl_error_invalid,
585 "entries should have the same range space",
586 goto error);
587
588 part = data->fn(part, FN(PART, copy)(entry2->data));
589
590 data->res = FN(FN(UNION,add),BASE)(data->res, part);
591 if (!data->res)
592 return isl_stat_error;
593
594 return isl_stat_ok;
595 error:
596 FN(PART,free)(part);
597 return isl_stat_error;
598 }
599
600 /* This function is currently only used from isl_polynomial.c
601 * and not from isl_fold.c.
602 */
603 static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
604 __isl_take UNION *u2,
605 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
606 __attribute__ ((unused));
607 /* For each pair of elements in "u1" and "u2" living in the same space,
608 * call "fn" and collect the results.
609 */
610 static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
611 __isl_take UNION *u2,
612 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
613 {
614 S(UNION,match_bin_data) data = { NULL, NULL, fn };
615
616 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
617 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
618
619 if (!u1 || !u2)
620 goto error;
621
622 data.u2 = u2;
623 data.res = FN(UNION,alloc_same_size)(u1);
624 if (FN(FN(UNION,foreach),BASE)(u1,
625 &FN(UNION,match_bin_entry), &data) < 0)
626 goto error;
627
628 FN(UNION,free)(u1);
629 FN(UNION,free)(u2);
630 return data.res;
631 error:
632 FN(UNION,free)(u1);
633 FN(UNION,free)(u2);
634 FN(UNION,free)(data.res);
635 return NULL;
636 }
637
638 /* Compute the sum of "u1" and "u2".
639 *
640 * If the base expressions have a default zero value, then the sum
641 * is computed on the union of the domains of "u1" and "u2".
642 * Otherwise, it is computed on their shared domains.
643 */
644 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
645 {
646 #if DEFAULT_IS_ZERO
647 return FN(UNION,union_add_)(u1, u2);
648 #else
649 return FN(UNION,match_bin_op)(u1, u2, &FN(PART,add));
650 #endif
651 }
652
653 #ifndef NO_SUB
654 /* Subtract "u2" from "u1" and return the result.
655 */
656 __isl_give UNION *FN(UNION,sub)(__isl_take UNION *u1, __isl_take UNION *u2)
657 {
658 return FN(UNION,match_bin_op)(u1, u2, &FN(PART,sub));
659 }
660 #endif
661
662 S(UNION,any_set_data) {
663 isl_set *set;
664 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
665 };
666
667 static __isl_give PART *FN(UNION,any_set_entry)(__isl_take PART *part,
668 void *user)
669 {
670 S(UNION,any_set_data) *data = user;
671
672 return data->fn(part, isl_set_copy(data->set));
673 }
674
675 /* Update each element of "u" by calling "fn" on the element and "set".
676 */
677 static __isl_give UNION *FN(UNION,any_set_op)(__isl_take UNION *u,
678 __isl_take isl_set *set,
679 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
680 {
681 S(UNION,any_set_data) data = { NULL, fn };
682 S(UNION,transform_control) control = {
683 .fn = &FN(UNION,any_set_entry),
684 .fn_user = &data,
685 };
686
687 u = FN(UNION,align_params)(u, isl_set_get_space(set));
688 set = isl_set_align_params(set, FN(UNION,get_space)(u));
689
690 if (!u || !set)
691 goto error;
692
693 data.set = set;
694 u = FN(UNION,transform)(u, &control);
695 isl_set_free(set);
696 return u;
697 error:
698 FN(UNION,free)(u);
699 isl_set_free(set);
700 return NULL;
701 }
702
703 /* Intersect the domain of "u" with the parameter domain "context".
704 */
705 __isl_give UNION *FN(UNION,intersect_params)(__isl_take UNION *u,
706 __isl_take isl_set *set)
707 {
708 return FN(UNION,any_set_op)(u, set, &FN(PW,intersect_params));
709 }
710
711 /* Compute the gist of the domain of "u" with respect to
712 * the parameter domain "context".
713 */
714 __isl_give UNION *FN(UNION,gist_params)(__isl_take UNION *u,
715 __isl_take isl_set *set)
716 {
717 return FN(UNION,any_set_op)(u, set, &FN(PW,gist_params));
718 }
719
720 /* Data structure that specifies how isl_union_*_match_domain_op
721 * should combine its arguments.
722 *
723 * If "filter" is not NULL, then only parts that pass the given
724 * filter are considered for matching.
725 * "fn" is applied to each part in the union and each corresponding
726 * set in the union set, i.e., such that the set lives in the same space
727 * as the domain of the part.
728 * If "match_space" is not NULL, then the set extracted from the union set
729 * does not live in the same space as the domain of the part,
730 * but rather in the space that results from calling "match_space"
731 * on this domain space.
732 */
733 S(UNION,match_domain_control) {
734 isl_bool (*filter)(__isl_keep PART *part);
735 __isl_give isl_space *(*match_space)(__isl_take isl_space *space);
736 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
737 };
738
739 S(UNION,match_domain_data) {
740 isl_union_set *uset;
741 UNION *res;
742 S(UNION,match_domain_control) *control;
743 };
744
745 /* Find the set in data->uset that lives in the same space as the domain
746 * of "part" (ignoring parameters), apply data->fn to *entry and this set
747 * (if any), and add the result to data->res.
748 */
749 static isl_stat FN(UNION,match_domain_entry)(__isl_take PART *part, void *user)
750 {
751 S(UNION,match_domain_data) *data = user;
752 struct isl_hash_table_entry *entry2;
753 isl_space *space;
754
755 if (data->control->filter) {
756 isl_bool pass = data->control->filter(part);
757 if (pass < 0 || !pass) {
758 FN(PART,free)(part);
759 return pass < 0 ? isl_stat_error : isl_stat_ok;
760 }
761 }
762
763 space = FN(PART,get_domain_space)(part);
764 if (data->control->match_space)
765 space = data->control->match_space(space);
766 entry2 = isl_union_set_find_entry(data->uset, space, 0);
767 isl_space_free(space);
768 if (!entry2 || entry2 == isl_hash_table_entry_none) {
769 FN(PART,free)(part);
770 return isl_stat_non_null(entry2);
771 }
772
773 part = data->control->fn(part, isl_set_copy(entry2->data));
774
775 data->res = FN(FN(UNION,add),BASE)(data->res, part);
776 if (!data->res)
777 return isl_stat_error;
778
779 return isl_stat_ok;
780 }
781
782 /* Combine "u" and "uset" according to "control"
783 * and collect the results.
784 */
785 static __isl_give UNION *FN(UNION,match_domain_op)(__isl_take UNION *u,
786 __isl_take isl_union_set *uset, S(UNION,match_domain_control) *control)
787 {
788 S(UNION,match_domain_data) data = { NULL, NULL, control };
789
790 if (!u || !uset)
791 goto error;
792
793 data.uset = uset;
794 data.res = FN(UNION,alloc_same_size)(u);
795 if (FN(FN(UNION,foreach),BASE)(u,
796 &FN(UNION,match_domain_entry), &data) < 0)
797 goto error;
798
799 FN(UNION,free)(u);
800 isl_union_set_free(uset);
801 return data.res;
802 error:
803 FN(UNION,free)(u);
804 isl_union_set_free(uset);
805 FN(UNION,free)(data.res);
806 return NULL;
807 }
808
809 /* Intersect the domain of "u" with "uset".
810 * If "uset" is a parameters domain, then intersect the parameter
811 * domain of "u" with this set.
812 */
813 __isl_give UNION *FN(UNION,intersect_domain_union_set)(__isl_take UNION *u,
814 __isl_take isl_union_set *uset)
815 {
816 S(UNION,match_domain_control) control = {
817 .fn = &FN(PW,intersect_domain),
818 };
819
820 if (isl_union_set_is_params(uset))
821 return FN(UNION,intersect_params)(u,
822 isl_set_from_union_set(uset));
823 return FN(UNION,match_domain_op)(u, uset, &control);
824 }
825
826 /* This is an alternative name for the function above.
827 */
828 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
829 __isl_take isl_union_set *uset)
830 {
831 return FN(UNION,intersect_domain_union_set)(u, uset);
832 }
833
834 /* Return true if this part should be kept.
835 *
836 * In particular, it should be kept if its domain space
837 * corresponds to "space".
838 */
839 static isl_bool FN(UNION,select_entry)(__isl_keep PART *part, void *user)
840 {
841 isl_space *space = user;
842
843 return FN(PW,has_domain_space_tuples)(part, space);
844 }
845
846 /* Remove any not element in "space" from the domain of "u".
847 *
848 * In particular, select any part of the function defined
849 * on this domain space.
850 */
851 __isl_give UNION *FN(UNION,intersect_domain_space)(__isl_take UNION *u,
852 __isl_take isl_space *space)
853 {
854 S(UNION,transform_control) control = {
855 .filter = &FN(UNION,select_entry),
856 .filter_user = space,
857 };
858
859 u = FN(UNION,transform)(u, &control);
860 isl_space_free(space);
861 return u;
862 }
863
864 /* Is the domain of "pw" a wrapped relation?
865 */
866 static isl_bool FN(PW,domain_is_wrapping)(__isl_keep PW *pw)
867 {
868 return isl_space_domain_is_wrapping(FN(PW,peek_space)(pw));
869 }
870
871 /* Intersect the domain of the wrapped relation inside the domain of "u"
872 * with "uset".
873 */
874 __isl_give UNION *FN(UNION,intersect_domain_wrapped_domain)(__isl_take UNION *u,
875 __isl_take isl_union_set *uset)
876 {
877 S(UNION,match_domain_control) control = {
878 .filter = &FN(PART,domain_is_wrapping),
879 .match_space = &isl_space_factor_domain,
880 .fn = &FN(PW,intersect_domain_wrapped_domain),
881 };
882
883 return FN(UNION,match_domain_op)(u, uset, &control);
884 }
885
886 /* Intersect the range of the wrapped relation inside the domain of "u"
887 * with "uset".
888 */
889 __isl_give UNION *FN(UNION,intersect_domain_wrapped_range)(__isl_take UNION *u,
890 __isl_take isl_union_set *uset)
891 {
892 S(UNION,match_domain_control) control = {
893 .filter = &FN(PART,domain_is_wrapping),
894 .match_space = &isl_space_factor_range,
895 .fn = &FN(PW,intersect_domain_wrapped_range),
896 };
897
898 return FN(UNION,match_domain_op)(u, uset, &control);
899 }
900
901 /* Take the set (which may be empty) in data->uset that lives
902 * in the same space as the domain of "pw", subtract it from the domain
903 * of "part" and return the result.
904 */
905 static __isl_give PART *FN(UNION,subtract_domain_entry)(__isl_take PART *part,
906 void *user)
907 {
908 isl_union_set *uset = user;
909 isl_space *space;
910 isl_set *set;
911
912 space = FN(PART,get_domain_space)(part);
913 set = isl_union_set_extract_set(uset, space);
914 return FN(PART,subtract_domain)(part, set);
915 }
916
917 /* Subtract "uset" from the domain of "u".
918 */
919 __isl_give UNION *FN(UNION,subtract_domain_union_set)(__isl_take UNION *u,
920 __isl_take isl_union_set *uset)
921 {
922 S(UNION,transform_control) control = {
923 .fn = &FN(UNION,subtract_domain_entry),
924 .fn_user = uset,
925 };
926
927 u = FN(UNION,transform)(u, &control);
928 isl_union_set_free(uset);
929 return u;
930 }
931
932 /* This is an alternative name for the function above.
933 */
934 __isl_give UNION *FN(UNION,subtract_domain)(__isl_take UNION *u,
935 __isl_take isl_union_set *uset)
936 {
937 return FN(UNION,subtract_domain_union_set)(u, uset);
938 }
939
940 /* Return true if this part should be kept.
941 *
942 * In particular, it should be kept if its domain space
943 * does not correspond to "space".
944 */
945 static isl_bool FN(UNION,filter_out_entry)(__isl_keep PART *part, void *user)
946 {
947 isl_space *space = user;
948
949 return isl_bool_not(FN(PW,has_domain_space_tuples)(part, space));
950 }
951
952 /* Remove any element in "space" from the domain of "u".
953 *
954 * In particular, filter out any part of the function defined
955 * on this domain space.
956 */
957 __isl_give UNION *FN(UNION,subtract_domain_space)(__isl_take UNION *u,
958 __isl_take isl_space *space)
959 {
960 S(UNION,transform_control) control = {
961 .filter = &FN(UNION,filter_out_entry),
962 .filter_user = space,
963 };
964
965 u = FN(UNION,transform)(u, &control);
966 isl_space_free(space);
967 return u;
968 }
969
970 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
971 __isl_take isl_union_set *uset)
972 {
973 S(UNION,match_domain_control) control = {
974 .fn = &FN(PW,gist),
975 };
976
977 if (isl_union_set_is_params(uset))
978 return FN(UNION,gist_params)(u, isl_set_from_union_set(uset));
979 return FN(UNION,match_domain_op)(u, uset, &control);
980 }
981
982 /* Coalesce an entry in a UNION. Coalescing is performed in-place.
983 * Since the UNION may have several references, the entry is only
984 * replaced if the coalescing is successful.
985 */
986 static isl_stat FN(UNION,coalesce_entry)(void **entry, void *user)
987 {
988 PART **part_p = (PART **) entry;
989 PART *part;
990
991 part = FN(PART,copy)(*part_p);
992 part = FN(PW,coalesce)(part);
993 if (!part)
994 return isl_stat_error;
995 FN(PART,free)(*part_p);
996 *part_p = part;
997
998 return isl_stat_ok;
999 }
1000
1001 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
1002 {
1003 if (FN(UNION,foreach_inplace)(u, &FN(UNION,coalesce_entry), NULL) < 0)
1004 goto error;
1005
1006 return u;
1007 error:
1008 FN(UNION,free)(u);
1009 return NULL;
1010 }
1011
1012 static isl_stat FN(UNION,domain_entry)(__isl_take PART *part, void *user)
1013 {
1014 isl_union_set **uset = (isl_union_set **)user;
1015
1016 *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
1017
1018 return isl_stat_ok;
1019 }
1020
1021 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
1022 {
1023 isl_union_set *uset;
1024
1025 uset = isl_union_set_empty(FN(UNION,get_space)(u));
1026 if (FN(FN(UNION,foreach),BASE)(u, &FN(UNION,domain_entry), &uset) < 0)
1027 goto error;
1028
1029 FN(UNION,free)(u);
1030
1031 return uset;
1032 error:
1033 isl_union_set_free(uset);
1034 FN(UNION,free)(u);
1035 return NULL;
1036 }
1037
1038 #ifdef HAS_TYPE
1039 /* Negate the type of "u".
1040 */
1041 static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u)
1042 {
1043 u = FN(UNION,cow)(u);
1044 if (!u)
1045 return NULL;
1046 u->type = isl_fold_type_negate(u->type);
1047 return u;
1048 }
1049 #else
1050 /* Negate the type of "u".
1051 * Since "u" does not have a type, do nothing.
1052 */
1053 static __isl_give UNION *FN(UNION,negate_type)(__isl_take UNION *u)
1054 {
1055 return u;
1056 }
1057 #endif
1058
1059 /* Multiply "part" by the isl_val "user" and return the result.
1060 */
1061 static __isl_give PART *FN(UNION,scale_val_entry)(__isl_take PART *part,
1062 void *user)
1063 {
1064 isl_val *v = user;
1065
1066 return FN(PART,scale_val)(part, isl_val_copy(v));
1067 }
1068
1069 /* Multiply "u" by "v" and return the result.
1070 */
1071 __isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u,
1072 __isl_take isl_val *v)
1073 {
1074 if (!u || !v)
1075 goto error;
1076 if (isl_val_is_one(v)) {
1077 isl_val_free(v);
1078 return u;
1079 }
1080
1081 if (DEFAULT_IS_ZERO && u && isl_val_is_zero(v)) {
1082 UNION *zero;
1083 isl_space *space = FN(UNION,get_space)(u);
1084 zero = FN(UNION,ZERO)(space OPT_TYPE_ARG(u->));
1085 FN(UNION,free)(u);
1086 isl_val_free(v);
1087 return zero;
1088 }
1089
1090 if (!isl_val_is_rat(v))
1091 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1092 "expecting rational factor", goto error);
1093
1094 u = FN(UNION,transform_inplace)(u, &FN(UNION,scale_val_entry), v);
1095 if (isl_val_is_neg(v))
1096 u = FN(UNION,negate_type)(u);
1097
1098 isl_val_free(v);
1099 return u;
1100 error:
1101 isl_val_free(v);
1102 FN(UNION,free)(u);
1103 return NULL;
1104 }
1105
1106 /* Divide "part" by the isl_val "user" and return the result.
1107 */
1108 static __isl_give PART *FN(UNION,scale_down_val_entry)(__isl_take PART *part,
1109 void *user)
1110 {
1111 isl_val *v = user;
1112
1113 return FN(PART,scale_down_val)(part, isl_val_copy(v));
1114 }
1115
1116 /* Divide "u" by "v" and return the result.
1117 */
1118 __isl_give UNION *FN(UNION,scale_down_val)(__isl_take UNION *u,
1119 __isl_take isl_val *v)
1120 {
1121 if (!u || !v)
1122 goto error;
1123 if (isl_val_is_one(v)) {
1124 isl_val_free(v);
1125 return u;
1126 }
1127
1128 if (!isl_val_is_rat(v))
1129 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1130 "expecting rational factor", goto error);
1131 if (isl_val_is_zero(v))
1132 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1133 "cannot scale down by zero", goto error);
1134
1135 u = FN(UNION,transform_inplace)(u, &FN(UNION,scale_down_val_entry), v);
1136 if (isl_val_is_neg(v))
1137 u = FN(UNION,negate_type)(u);
1138
1139 isl_val_free(v);
1140 return u;
1141 error:
1142 isl_val_free(v);
1143 FN(UNION,free)(u);
1144 return NULL;
1145 }
1146
1147 /* Internal data structure for isl_union_*_every_*.
1148 *
1149 * "test" is the user-specified callback function.
1150 * "user" is the user-specified callback function argument.
1151 *
1152 * "res" is the final result, initialized to isl_bool_true.
1153 */
1154 S(UNION,every_data) {
1155 isl_bool (*test)(__isl_keep PW *pw, void *user);
1156 void *user;
1157
1158 isl_bool res;
1159 };
1160
1161 /* Call data->test on the piecewise expression at *entry,
1162 * updating the result in data->res.
1163 * Abort if this result is no longer isl_bool_true.
1164 */
1165 static isl_stat FN(UNION,every_entry)(void **entry, void *user)
1166 {
1167 S(UNION,every_data) *data = user;
1168 PW *pw = *entry;
1169
1170 data->res = data->test(pw, data->user);
1171 if (data->res < 0 || !data->res)
1172 return isl_stat_error;
1173
1174 return isl_stat_ok;
1175 }
1176
1177 /* Does "test" succeed on every piecewise expression in "u"?
1178 */
1179 isl_bool FN(FN(UNION,every),BASE)(__isl_keep UNION *u,
1180 isl_bool (*test)(__isl_keep PW *pw, void *user), void *user)
1181 {
1182 S(UNION,every_data) data = { test, user };
1183
1184 data.res = isl_bool_true;
1185 if (FN(UNION,foreach_inplace)(u, &FN(UNION,every_entry), &data) < 0 &&
1186 data.res == isl_bool_true)
1187 return isl_bool_error;
1188
1189 return data.res;
1190 }
1191
1192 S(UNION,plain_is_equal_data)
1193 {
1194 UNION *u2;
1195 };
1196
1197 static isl_bool FN(UNION,plain_is_equal_el)(__isl_keep PW *pw, void *user)
1198 {
1199 S(UNION,plain_is_equal_data) *data = user;
1200 struct isl_hash_table_entry *entry;
1201
1202 entry = FN(UNION,find_part_entry)(data->u2, pw->dim, 0);
1203 if (!entry)
1204 return isl_bool_error;
1205 if (entry == isl_hash_table_entry_none)
1206 return isl_bool_false;
1207
1208 return FN(PW,plain_is_equal)(pw, entry->data);
1209 }
1210
1211 isl_bool FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2)
1212 {
1213 S(UNION,plain_is_equal_data) data;
1214 isl_size n1, n2;
1215 isl_bool is_equal;
1216
1217 if (!u1 || !u2)
1218 return isl_bool_error;
1219 if (u1 == u2)
1220 return isl_bool_true;
1221 if (u1->table.n != u2->table.n)
1222 return isl_bool_false;
1223 n1 = FN(FN(UNION,n),BASE)(u1);
1224 n2 = FN(FN(UNION,n),BASE)(u2);
1225 if (n1 < 0 || n2 < 0)
1226 return isl_bool_error;
1227 if (n1 != n2)
1228 return isl_bool_false;
1229
1230 u1 = FN(UNION,copy)(u1);
1231 u2 = FN(UNION,copy)(u2);
1232 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
1233 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
1234 if (!u1 || !u2)
1235 goto error;
1236
1237 data.u2 = u2;
1238 is_equal = FN(FN(UNION,every),BASE)(u1,
1239 &FN(UNION,plain_is_equal_el), &data);
1240
1241 FN(UNION,free)(u1);
1242 FN(UNION,free)(u2);
1243
1244 return is_equal;
1245 error:
1246 FN(UNION,free)(u1);
1247 FN(UNION,free)(u2);
1248 return isl_bool_error;
1249 }
1250
1251 /* An isl_union_*_every_* callback that checks whether "pw"
1252 * does not involve any NaNs.
1253 */
1254 static isl_bool FN(UNION,no_nan_el)(__isl_keep PW *pw, void *user)
1255 {
1256 return isl_bool_not(FN(PW,involves_nan)(pw));
1257 }
1258
1259 /* Does "u" involve any NaNs?
1260 */
1261 isl_bool FN(UNION,involves_nan)(__isl_keep UNION *u)
1262 {
1263 isl_bool no_nan;
1264
1265 no_nan = FN(FN(UNION,every),BASE)(u, &FN(UNION,no_nan_el), NULL);
1266
1267 return isl_bool_not(no_nan);
1268 }
1269
1270 /* Internal data structure for isl_union_*_drop_dims.
1271 * type, first and n are passed to isl_*_drop_dims.
1272 */
1273 S(UNION,drop_dims_data) {
1274 enum isl_dim_type type;
1275 unsigned first;
1276 unsigned n;
1277 };
1278
1279 /* Drop the parameters specified by "data" from "part" and return the result.
1280 */
1281 static __isl_give PART *FN(UNION,drop_dims_entry)(__isl_take PART *part,
1282 void *user)
1283 {
1284 S(UNION,drop_dims_data) *data = user;
1285
1286 return FN(PART,drop_dims)(part, data->type, data->first, data->n);
1287 }
1288
1289 /* Drop the specified parameters from "u".
1290 * That is, type is required to be isl_dim_param.
1291 */
1292 __isl_give UNION *FN(UNION,drop_dims)( __isl_take UNION *u,
1293 enum isl_dim_type type, unsigned first, unsigned n)
1294 {
1295 isl_space *space;
1296 S(UNION,drop_dims_data) data = { type, first, n };
1297 S(UNION,transform_control) control = {
1298 .fn = &FN(UNION,drop_dims_entry),
1299 .fn_user = &data,
1300 };
1301
1302 if (!u)
1303 return NULL;
1304
1305 if (type != isl_dim_param)
1306 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1307 "can only project out parameters",
1308 return FN(UNION,free)(u));
1309
1310 space = FN(UNION,get_space)(u);
1311 space = isl_space_drop_dims(space, type, first, n);
1312 return FN(UNION,transform_space)(u, space, &control);
1313 }
1314
1315 /* Internal data structure for isl_union_*_set_dim_name.
1316 * pos is the position of the parameter that needs to be renamed.
1317 * s is the new name.
1318 */
1319 S(UNION,set_dim_name_data) {
1320 unsigned pos;
1321 const char *s;
1322 };
1323
1324 /* Change the name of the parameter at position data->pos of "part" to data->s
1325 * and return the result.
1326 */
1327 static __isl_give PART *FN(UNION,set_dim_name_entry)(__isl_take PART *part,
1328 void *user)
1329 {
1330 S(UNION,set_dim_name_data) *data = user;
1331
1332 return FN(PART,set_dim_name)(part, isl_dim_param, data->pos, data->s);
1333 }
1334
1335 /* Change the name of the parameter at position "pos" to "s".
1336 * That is, type is required to be isl_dim_param.
1337 */
1338 __isl_give UNION *FN(UNION,set_dim_name)(__isl_take UNION *u,
1339 enum isl_dim_type type, unsigned pos, const char *s)
1340 {
1341 S(UNION,set_dim_name_data) data = { pos, s };
1342 S(UNION,transform_control) control = {
1343 .fn = &FN(UNION,set_dim_name_entry),
1344 .fn_user = &data,
1345 };
1346 isl_space *space;
1347
1348 if (!u)
1349 return NULL;
1350
1351 if (type != isl_dim_param)
1352 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1353 "can only set parameter names",
1354 return FN(UNION,free)(u));
1355
1356 space = FN(UNION,get_space)(u);
1357 space = isl_space_set_dim_name(space, type, pos, s);
1358 return FN(UNION,transform_space)(u, space, &control);
1359 }
1360
1361 /* Reset the user pointer on all identifiers of parameters and tuples
1362 * of the space of "part" and return the result.
1363 */
1364 static __isl_give PART *FN(UNION,reset_user_entry)(__isl_take PART *part,
1365 void *user)
1366 {
1367 return FN(PART,reset_user)(part);
1368 }
1369
1370 /* Reset the user pointer on all identifiers of parameters and tuples
1371 * of the spaces of "u".
1372 */
1373 __isl_give UNION *FN(UNION,reset_user)(__isl_take UNION *u)
1374 {
1375 S(UNION,transform_control) control = {
1376 .fn = &FN(UNION,reset_user_entry),
1377 };
1378 isl_space *space;
1379
1380 space = FN(UNION,get_space)(u);
1381 space = isl_space_reset_user(space);
1382 return FN(UNION,transform_space)(u, space, &control);
1383 }
1384
1385 /* Add the base expression held by "entry" to "list".
1386 */
1387 static isl_stat FN(UNION,add_to_list)(void **entry, void *user)
1388 {
1389 PW *pw = *entry;
1390 LIST(PART) **list = user;
1391
1392 *list = FN(LIST(PART),add)(*list, FN(PART,copy)(pw));
1393 if (!*list)
1394 return isl_stat_error;
1395
1396 return isl_stat_ok;
1397 }
1398
1399 /* Return a list containing all the base expressions in "u".
1400 *
1401 * First construct a list of the appropriate size and
1402 * then add all the elements.
1403 */
1404 __isl_give LIST(PART) *FN(FN(UNION,get),LIST(BASE))(__isl_keep UNION *u)
1405 {
1406 isl_size n;
1407 LIST(PART) *list;
1408
1409 if (!u)
1410 return NULL;
1411 n = FN(FN(UNION,n),BASE)(u);
1412 if (n < 0)
1413 return NULL;
1414 list = FN(LIST(PART),alloc)(FN(UNION,get_ctx(u)), n);
1415 if (FN(UNION,foreach_inplace)(u, &FN(UNION,add_to_list), &list) < 0)
1416 return FN(LIST(PART),free)(list);
1417
1418 return list;
1419 }
Integer set library