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

source code of polly/lib/External/isl/isl_union_templ.c