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