2 * Copyright 2010 INRIA Saclay
3 * Copyright 2013 Ecole Normale Superieure
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
16 #include "has_single_reference_templ.c"
18 __isl_give UNION
*FN(UNION
,cow
)(__isl_take UNION
*u
);
20 isl_ctx
*FN(UNION
,get_ctx
)(__isl_keep UNION
*u
)
22 return u
? u
->space
->ctx
: NULL
;
25 /* Return the space of "u".
27 static __isl_keep isl_space
*FN(UNION
,peek_space
)(__isl_keep UNION
*u
)
34 /* Return a copy of the space of "u".
36 __isl_give isl_space
*FN(UNION
,get_space
)(__isl_keep UNION
*u
)
38 return isl_space_copy(FN(UNION
,peek_space
)(u
));
41 /* Return the number of parameters of "u", where "type"
42 * is required to be set to isl_dim_param.
44 isl_size
FN(UNION
,dim
)(__isl_keep UNION
*u
, enum isl_dim_type type
)
47 return isl_size_error
;
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
);
53 return isl_space_dim(u
->space
, type
);
56 /* Return the position of the parameter with the given name
58 * Return -1 if no such dimension can be found.
60 int FN(UNION
,find_dim_by_name
)(__isl_keep UNION
*u
, enum isl_dim_type type
,
65 return isl_space_find_dim_by_name(u
->space
, type
, name
);
70 static __isl_give UNION
*FN(UNION
,alloc
)(__isl_take isl_space
*space
71 OPT_TYPE_PARAM
, int size
)
75 space
= isl_space_params(space
);
79 u
= isl_calloc_type(space
->ctx
, UNION
);
84 OPT_SET_TYPE(u
->, type
);
86 if (isl_hash_table_init(space
->ctx
, &u
->table
, size
) < 0)
87 return FN(UNION
,free
)(u
);
91 isl_space_free(space
);
95 /* Create an empty/zero union without specifying any parameters.
97 __isl_give UNION
*FN(FN(UNION
,ZERO
),ctx
)(isl_ctx
*ctx OPT_TYPE_PARAM
)
101 space
= isl_space_unit(ctx
);
102 return FN(FN(UNION
,ZERO
),space
)(space
OPT_TYPE_ARG(NO_LOC
));
105 __isl_give UNION
*FN(FN(UNION
,ZERO
),space
)(__isl_take isl_space
*space
108 return FN(UNION
,alloc
)(space
OPT_TYPE_ARG(NO_LOC
), 16);
111 /* This is an alternative name for the function above.
113 __isl_give UNION
*FN(UNION
,ZERO
)(__isl_take isl_space
*space OPT_TYPE_PARAM
)
115 return FN(FN(UNION
,ZERO
),space
)(space
OPT_TYPE_ARG(NO_LOC
));
118 __isl_give UNION
*FN(UNION
,copy
)(__isl_keep UNION
*u
)
127 /* Extract the element of "u" living in "space" (ignoring parameters).
129 * Return the ZERO element if "u" does not contain any element
132 __isl_give PART
*FN(FN(UNION
,extract
),BASE
)(__isl_keep UNION
*u
,
133 __isl_take isl_space
*space
)
135 struct isl_hash_table_entry
*entry
;
137 space
= isl_space_replace_params(space
, FN(UNION
,peek_space
)(u
));
139 entry
= FN(UNION
,find_part_entry
)(u
, space
, 0);
142 if (entry
== isl_hash_table_entry_none
)
143 return FN(PART
,ZERO
)(space
OPT_TYPE_ARG(u
->));
144 isl_space_free(space
);
145 return FN(PART
,copy
)(entry
->data
);
147 isl_space_free(space
);
151 /* Add "part" to "u".
152 * If "disjoint" is set, then "u" is not allowed to already have
153 * a part that is defined over a domain that overlaps with the domain
155 * Otherwise, compute the union sum of "part" and the part in "u"
156 * defined on the same space.
158 static __isl_give UNION
*FN(UNION
,add_part_generic
)(__isl_take UNION
*u
,
159 __isl_take PART
*part
, int disjoint
)
162 struct isl_hash_table_entry
*entry
;
167 empty
= FN(PART
,IS_ZERO
)(part
);
175 u
= FN(UNION
,align_params
)(u
, FN(PART
,get_space
)(part
));
176 part
= FN(PART
,align_params
)(part
, FN(UNION
,get_space
)(u
));
178 u
= FN(UNION
,cow
)(u
);
183 if (FN(UNION
,check_disjoint_domain_other
)(u
, part
) < 0)
185 entry
= FN(UNION
,find_part_entry
)(u
, part
->dim
, 1);
193 FN(UNION
,check_disjoint_domain
)(entry
->data
, part
) < 0)
195 entry
->data
= FN(PART
,union_add_
)(entry
->data
,
196 FN(PART
,copy
)(part
));
199 empty
= FN(PART
,IS_ZERO
)(part
);
203 u
= FN(UNION
,remove_part_entry
)(u
, entry
);
214 /* Add "part" to "u", where "u" is assumed not to already have
215 * a part that is defined on the same space as "part".
217 __isl_give UNION
*FN(FN(UNION
,add
),BASE
)(__isl_take UNION
*u
,
218 __isl_take PART
*part
)
220 return FN(UNION
,add_part_generic
)(u
, part
, 1);
223 /* Allocate a UNION with the same type (if any) and the same size as "u" and
224 * with space "space".
226 static __isl_give UNION
*FN(UNION
,alloc_same_size_on_space
)(__isl_keep UNION
*u
,
227 __isl_take isl_space
*space
)
231 return FN(UNION
,alloc
)(space
OPT_TYPE_ARG(u
->), u
->table
.n
);
233 isl_space_free(space
);
237 /* Allocate a UNION with the same space, the same type (if any) and
238 * the same size as "u".
240 static __isl_give UNION
*FN(UNION
,alloc_same_size
)(__isl_keep UNION
*u
)
242 return FN(UNION
,alloc_same_size_on_space
)(u
, FN(UNION
,get_space
)(u
));
245 /* Data structure that specifies how isl_union_*_transform
246 * should modify the base expressions in the union expression.
248 * If "inplace" is set, then the base expression in the input union
249 * are modified in place. This means that "fn" should not
250 * change the meaning of the union or that the union only
251 * has a single reference.
252 * If "space" is not NULL, then a new union is created in this space.
253 * If "filter" is not NULL, then only the base expressions that satisfy "filter"
254 * are taken into account.
255 * "fn" is applied to each entry in the input.
256 * "fn_user" is passed as the second argument to "fn".
258 S(UNION
,transform_control
) {
261 isl_bool (*filter
)(__isl_keep PART
*part
);
262 __isl_give PART
*(*fn
)(__isl_take PART
*part
, void *user
);
266 /* Internal data structure for isl_union_*_transform_space.
267 * "control" specifies how the base expressions should be modified.
268 * "res" collects the results (if control->inplace is not set).
270 S(UNION
,transform_data
)
272 S(UNION
,transform_control
) *control
;
276 /* Apply control->fn to "part" and add the result to data->res or
277 * place it back into the input union if control->inplace is set.
279 static isl_stat
FN(UNION
,transform_entry
)(void **entry
, void *user
)
281 S(UNION
,transform_data
) *data
= (S(UNION
,transform_data
) *)user
;
284 if (data
->control
->filter
) {
287 handle
= data
->control
->filter(part
);
289 return isl_stat_error
;
294 if (!data
->control
->inplace
)
295 part
= FN(PART
,copy
)(part
);
296 part
= data
->control
->fn(part
, data
->control
->fn_user
);
297 if (data
->control
->inplace
)
300 data
->res
= FN(FN(UNION
,add
),BASE
)(data
->res
, part
);
301 if (!part
|| !data
->res
)
302 return isl_stat_error
;
307 /* Return a UNION that is obtained by modifying "u" according to "control".
309 static __isl_give UNION
*FN(UNION
,transform
)(__isl_take UNION
*u
,
310 S(UNION
,transform_control
) *control
)
312 S(UNION
,transform_data
) data
= { control
};
315 if (control
->inplace
) {
319 space
= isl_space_copy(control
->space
);
321 space
= FN(UNION
,get_space
)(u
);
322 data
.res
= FN(UNION
,alloc_same_size_on_space
)(u
, space
);
324 if (FN(UNION
,foreach_inplace
)(u
, &FN(UNION
,transform_entry
), &data
) < 0)
325 data
.res
= FN(UNION
,free
)(data
.res
);
326 if (!control
->inplace
)
331 /* Return a UNION living in "space" that is otherwise obtained by modifying "u"
332 * according to "control".
334 static __isl_give UNION
*FN(UNION
,transform_space
)(__isl_take UNION
*u
,
335 __isl_take isl_space
*space
, S(UNION
,transform_control
) *control
)
338 return FN(UNION
,free
)(u
);
339 control
->space
= space
;
340 u
= FN(UNION
,transform
)(u
, control
);
341 isl_space_free(space
);
345 /* Update "u" by applying "fn" to each entry.
346 * This operation is assumed not to change the number of entries nor
347 * the spaces of the entries.
349 * If there is only one reference to "u", then change "u" inplace.
350 * Otherwise, create a new UNION from "u" and discard the original.
352 static __isl_give UNION
*FN(UNION
,transform_inplace
)(__isl_take UNION
*u
,
353 __isl_give PART
*(*fn
)(__isl_take PART
*part
, void *user
), void *user
)
355 S(UNION
,transform_control
) control
= { .fn
= fn
, .fn_user
= user
};
358 single_ref
= FN(UNION
,has_single_reference
)(u
);
360 return FN(UNION
,free
)(u
);
363 return FN(UNION
,transform
)(u
, &control
);
366 /* An isl_union_*_transform callback for use in isl_union_*_dup
367 * that simply returns "part".
369 static __isl_give PART
*FN(UNION
,copy_part
)(__isl_take PART
*part
, void *user
)
374 __isl_give UNION
*FN(UNION
,dup
)(__isl_keep UNION
*u
)
376 S(UNION
,transform_control
) control
= { .fn
= &FN(UNION
,copy_part
) };
378 u
= FN(UNION
,copy
)(u
);
379 return FN(UNION
,transform
)(u
, &control
);
382 __isl_give UNION
*FN(UNION
,cow
)(__isl_take UNION
*u
)
390 return FN(UNION
,dup
)(u
);
393 __isl_null UNION
*FN(UNION
,free
)(__isl_take UNION
*u
)
401 isl_hash_table_foreach(u
->space
->ctx
, &u
->table
,
402 &FN(UNION
,free_u_entry
), NULL
);
403 isl_hash_table_clear(&u
->table
);
404 isl_space_free(u
->space
);
409 static __isl_give PART
*FN(UNION
,align_entry
)(__isl_take PART
*part
, void *user
)
411 isl_reordering
*exp
= user
;
413 exp
= isl_reordering_extend_space(isl_reordering_copy(exp
),
414 FN(PART
,get_domain_space
)(part
));
415 return FN(PART
,realign_domain
)(part
, exp
);
418 /* Reorder the parameters of "u" according to the given reordering.
420 static __isl_give UNION
*FN(UNION
,realign_domain
)(__isl_take UNION
*u
,
421 __isl_take isl_reordering
*r
)
423 S(UNION
,transform_control
) control
= {
424 .fn
= &FN(UNION
,align_entry
),
432 space
= isl_reordering_get_space(r
);
433 u
= FN(UNION
,transform_space
)(u
, space
, &control
);
434 isl_reordering_free(r
);
438 isl_reordering_free(r
);
442 /* Align the parameters of "u" to those of "model".
444 __isl_give UNION
*FN(UNION
,align_params
)(__isl_take UNION
*u
,
445 __isl_take isl_space
*model
)
447 isl_bool equal_params
;
453 equal_params
= isl_space_has_equal_params(u
->space
, model
);
454 if (equal_params
< 0)
457 isl_space_free(model
);
461 r
= isl_parameter_alignment_reordering(u
->space
, model
);
462 isl_space_free(model
);
464 return FN(UNION
,realign_domain
)(u
, r
);
466 isl_space_free(model
);
471 /* Add "part" to *u, taking the union sum if "u" already has
472 * a part defined on the same space as "part".
474 static isl_stat
FN(UNION
,union_add_part
)(__isl_take PART
*part
, void *user
)
476 UNION
**u
= (UNION
**)user
;
478 *u
= FN(UNION
,add_part_generic
)(*u
, part
, 0);
483 /* Compute the sum of "u1" and "u2" on the union of their domains,
484 * with the actual sum on the shared domain and
485 * the defined expression on the symmetric difference of the domains.
487 * This is an internal function that is exposed under different
488 * names depending on whether the base expressions have a zero default
490 * If they do, then this function is called "add".
491 * Otherwise, it is called "union_add".
493 static __isl_give UNION
*FN(UNION
,union_add_
)(__isl_take UNION
*u1
,
494 __isl_take UNION
*u2
)
496 u1
= FN(UNION
,align_params
)(u1
, FN(UNION
,get_space
)(u2
));
497 u2
= FN(UNION
,align_params
)(u2
, FN(UNION
,get_space
)(u1
));
499 u1
= FN(UNION
,cow
)(u1
);
504 if (FN(FN(UNION
,foreach
),BASE
)(u2
, &FN(UNION
,union_add_part
), &u1
) < 0)
516 __isl_give UNION
*FN(FN(UNION
,from
),BASE
)(__isl_take PART
*part
)
524 space
= FN(PART
,get_space
)(part
);
525 space
= isl_space_drop_dims(space
, isl_dim_in
, 0,
526 isl_space_dim(space
, isl_dim_in
));
527 space
= isl_space_drop_dims(space
, isl_dim_out
, 0,
528 isl_space_dim(space
, isl_dim_out
));
529 u
= FN(UNION
,ZERO
)(space
OPT_TYPE_ARG(part
->));
530 u
= FN(FN(UNION
,add
),BASE
)(u
, part
);
535 S(UNION
,match_bin_data
) {
538 __isl_give PART
*(*fn
)(__isl_take PART
*, __isl_take PART
*);
541 /* Check if data->u2 has an element living in the same space as "part".
542 * If so, call data->fn on the two elements and add the result to
545 static isl_stat
FN(UNION
,match_bin_entry
)(__isl_take PART
*part
, void *user
)
547 S(UNION
,match_bin_data
) *data
= user
;
548 struct isl_hash_table_entry
*entry2
;
552 space
= FN(PART
,get_space
)(part
);
553 entry2
= FN(UNION
,find_part_entry
)(data
->u2
, space
, 0);
554 isl_space_free(space
);
557 if (entry2
== isl_hash_table_entry_none
) {
562 part2
= entry2
->data
;
563 if (!isl_space_tuple_is_equal(part
->dim
, isl_dim_out
,
564 part2
->dim
, isl_dim_out
))
565 isl_die(FN(UNION
,get_ctx
)(data
->u2
), isl_error_invalid
,
566 "entries should have the same range space",
569 part
= data
->fn(part
, FN(PART
, copy
)(entry2
->data
));
571 data
->res
= FN(FN(UNION
,add
),BASE
)(data
->res
, part
);
573 return isl_stat_error
;
578 return isl_stat_error
;
581 /* This function is currently only used from isl_polynomial.c
582 * and not from isl_fold.c.
584 static __isl_give UNION
*FN(UNION
,match_bin_op
)(__isl_take UNION
*u1
,
585 __isl_take UNION
*u2
,
586 __isl_give PART
*(*fn
)(__isl_take PART
*, __isl_take PART
*))
587 __attribute__ ((unused
));
588 /* For each pair of elements in "u1" and "u2" living in the same space,
589 * call "fn" and collect the results.
591 static __isl_give UNION
*FN(UNION
,match_bin_op
)(__isl_take UNION
*u1
,
592 __isl_take UNION
*u2
,
593 __isl_give PART
*(*fn
)(__isl_take PART
*, __isl_take PART
*))
595 S(UNION
,match_bin_data
) data
= { NULL
, NULL
, fn
};
597 u1
= FN(UNION
,align_params
)(u1
, FN(UNION
,get_space
)(u2
));
598 u2
= FN(UNION
,align_params
)(u2
, FN(UNION
,get_space
)(u1
));
604 data
.res
= FN(UNION
,alloc_same_size
)(u1
);
605 if (FN(FN(UNION
,foreach
),BASE
)(u1
,
606 &FN(UNION
,match_bin_entry
), &data
) < 0)
615 FN(UNION
,free
)(data
.res
);
619 /* Compute the sum of "u1" and "u2".
621 * If the base expressions have a default zero value, then the sum
622 * is computed on the union of the domains of "u1" and "u2".
623 * Otherwise, it is computed on their shared domains.
625 __isl_give UNION
*FN(UNION
,add
)(__isl_take UNION
*u1
, __isl_take UNION
*u2
)
628 return FN(UNION
,union_add_
)(u1
, u2
);
630 return FN(UNION
,match_bin_op
)(u1
, u2
, &FN(PART
,add
));
635 /* Subtract "u2" from "u1" and return the result.
637 __isl_give UNION
*FN(UNION
,sub
)(__isl_take UNION
*u1
, __isl_take UNION
*u2
)
639 return FN(UNION
,match_bin_op
)(u1
, u2
, &FN(PART
,sub
));
643 S(UNION
,any_set_data
) {
645 __isl_give PW
*(*fn
)(__isl_take PW
*, __isl_take isl_set
*);
648 static __isl_give PART
*FN(UNION
,any_set_entry
)(__isl_take PART
*part
,
651 S(UNION
,any_set_data
) *data
= user
;
653 return data
->fn(part
, isl_set_copy(data
->set
));
656 /* Update each element of "u" by calling "fn" on the element and "set".
658 static __isl_give UNION
*FN(UNION
,any_set_op
)(__isl_take UNION
*u
,
659 __isl_take isl_set
*set
,
660 __isl_give PW
*(*fn
)(__isl_take PW
*, __isl_take isl_set
*))
662 S(UNION
,any_set_data
) data
= { NULL
, fn
};
663 S(UNION
,transform_control
) control
= {
664 .fn
= &FN(UNION
,any_set_entry
),
668 u
= FN(UNION
,align_params
)(u
, isl_set_get_space(set
));
669 set
= isl_set_align_params(set
, FN(UNION
,get_space
)(u
));
675 u
= FN(UNION
,transform
)(u
, &control
);
684 /* Intersect the domain of "u" with the parameter domain "context".
686 __isl_give UNION
*FN(UNION
,intersect_params
)(__isl_take UNION
*u
,
687 __isl_take isl_set
*set
)
689 return FN(UNION
,any_set_op
)(u
, set
, &FN(PW
,intersect_params
));
692 /* Compute the gist of the domain of "u" with respect to
693 * the parameter domain "context".
695 __isl_give UNION
*FN(UNION
,gist_params
)(__isl_take UNION
*u
,
696 __isl_take isl_set
*set
)
698 return FN(UNION
,any_set_op
)(u
, set
, &FN(PW
,gist_params
));
701 /* Data structure that specifies how isl_union_*_match_domain_op
702 * should combine its arguments.
704 * If "filter" is not NULL, then only parts that pass the given
705 * filter are considered for matching.
706 * "fn" is applied to each part in the union and each corresponding
707 * set in the union set, i.e., such that the set lives in the same space
708 * as the domain of the part.
709 * If "match_space" is not NULL, then the set extracted from the union set
710 * does not live in the same space as the domain of the part,
711 * but rather in the space that results from calling "match_space"
712 * on this domain space.
714 S(UNION
,match_domain_control
) {
715 isl_bool (*filter
)(__isl_keep PART
*part
);
716 __isl_give isl_space
*(*match_space
)(__isl_take isl_space
*space
);
717 __isl_give PW
*(*fn
)(__isl_take PW
*, __isl_take isl_set
*);
720 S(UNION
,match_domain_data
) {
723 S(UNION
,match_domain_control
) *control
;
726 static isl_bool
FN(UNION
,set_has_space
)(const void *entry
, const void *val
)
728 isl_set
*set
= (isl_set
*)entry
;
729 isl_space
*space
= (isl_space
*)val
;
731 return isl_space_is_equal(set
->dim
, space
);
734 /* Find the set in data->uset that lives in the same space as the domain
735 * of "part", apply data->fn to *entry and this set (if any), and add
736 * the result to data->res.
738 static isl_stat
FN(UNION
,match_domain_entry
)(__isl_take PART
*part
, void *user
)
740 S(UNION
,match_domain_data
) *data
= user
;
742 struct isl_hash_table_entry
*entry2
;
743 isl_space
*space
, *uset_space
;
745 if (data
->control
->filter
) {
746 isl_bool pass
= data
->control
->filter(part
);
747 if (pass
< 0 || !pass
) {
749 return pass
< 0 ? isl_stat_error
: isl_stat_ok
;
753 uset_space
= isl_union_set_peek_space(data
->uset
);
754 space
= FN(PART
,get_domain_space
)(part
);
755 if (data
->control
->match_space
)
756 space
= data
->control
->match_space(space
);
757 space
= isl_space_replace_params(space
, uset_space
);
758 hash
= isl_space_get_hash(space
);
759 entry2
= isl_hash_table_find(data
->uset
->dim
->ctx
, &data
->uset
->table
,
760 hash
, &FN(UNION
,set_has_space
), space
, 0);
761 isl_space_free(space
);
762 if (!entry2
|| entry2
== isl_hash_table_entry_none
) {
764 return isl_stat_non_null(entry2
);
767 part
= data
->control
->fn(part
, isl_set_copy(entry2
->data
));
769 data
->res
= FN(FN(UNION
,add
),BASE
)(data
->res
, part
);
771 return isl_stat_error
;
776 /* Combine "u" and "uset" according to "control"
777 * and collect the results.
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
)
782 S(UNION
,match_domain_data
) data
= { NULL
, NULL
, control
};
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)
794 isl_union_set_free(uset
);
798 isl_union_set_free(uset
);
799 FN(UNION
,free
)(data
.res
);
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.
807 __isl_give UNION
*FN(UNION
,intersect_domain
)(__isl_take UNION
*u
,
808 __isl_take isl_union_set
*uset
)
810 S(UNION
,match_domain_control
) control
= {
811 .fn
= &FN(PW
,intersect_domain
),
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
);
820 /* Is the domain of "pw" a wrapped relation?
822 static isl_bool
FN(PW
,domain_is_wrapping
)(__isl_keep PW
*pw
)
824 return isl_space_domain_is_wrapping(FN(PW
,peek_space
)(pw
));
827 /* Intersect the domain of the wrapped relation inside the domain of "u"
830 __isl_give UNION
*FN(UNION
,intersect_domain_wrapped_domain
)(__isl_take UNION
*u
,
831 __isl_take isl_union_set
*uset
)
833 S(UNION
,match_domain_control
) control
= {
834 .filter
= &FN(PART
,domain_is_wrapping
),
835 .match_space
= &isl_space_factor_domain
,
836 .fn
= &FN(PW
,intersect_domain_wrapped_domain
),
839 return FN(UNION
,match_domain_op
)(u
, uset
, &control
);
842 /* Intersect the range of the wrapped relation inside the domain of "u"
845 __isl_give UNION
*FN(UNION
,intersect_domain_wrapped_range
)(__isl_take UNION
*u
,
846 __isl_take isl_union_set
*uset
)
848 S(UNION
,match_domain_control
) control
= {
849 .filter
= &FN(PART
,domain_is_wrapping
),
850 .match_space
= &isl_space_factor_range
,
851 .fn
= &FN(PW
,intersect_domain_wrapped_range
),
854 return FN(UNION
,match_domain_op
)(u
, uset
, &control
);
857 /* Take the set (which may be empty) in data->uset that lives
858 * in the same space as the domain of "pw", subtract it from the domain
859 * of "part" and return the result.
861 static __isl_give PART
*FN(UNION
,subtract_domain_entry
)(__isl_take PART
*part
,
864 isl_union_set
*uset
= user
;
868 space
= FN(PART
,get_domain_space
)(part
);
869 set
= isl_union_set_extract_set(uset
, space
);
870 return FN(PART
,subtract_domain
)(part
, set
);
873 /* Subtract "uset" from the domain of "u".
875 __isl_give UNION
*FN(UNION
,subtract_domain
)(__isl_take UNION
*u
,
876 __isl_take isl_union_set
*uset
)
878 S(UNION
,transform_control
) control
= {
879 .fn
= &FN(UNION
,subtract_domain_entry
),
883 u
= FN(UNION
,transform
)(u
, &control
);
884 isl_union_set_free(uset
);
888 __isl_give UNION
*FN(UNION
,gist
)(__isl_take UNION
*u
,
889 __isl_take isl_union_set
*uset
)
891 S(UNION
,match_domain_control
) control
= {
895 if (isl_union_set_is_params(uset
))
896 return FN(UNION
,gist_params
)(u
, isl_set_from_union_set(uset
));
897 return FN(UNION
,match_domain_op
)(u
, uset
, &control
);
900 /* Coalesce an entry in a UNION. Coalescing is performed in-place.
901 * Since the UNION may have several references, the entry is only
902 * replaced if the coalescing is successful.
904 static isl_stat
FN(UNION
,coalesce_entry
)(void **entry
, void *user
)
906 PART
**part_p
= (PART
**) entry
;
909 part
= FN(PART
,copy
)(*part_p
);
910 part
= FN(PW
,coalesce
)(part
);
912 return isl_stat_error
;
913 FN(PART
,free
)(*part_p
);
919 __isl_give UNION
*FN(UNION
,coalesce
)(__isl_take UNION
*u
)
921 if (FN(UNION
,foreach_inplace
)(u
, &FN(UNION
,coalesce_entry
), NULL
) < 0)
930 static isl_stat
FN(UNION
,domain_entry
)(__isl_take PART
*part
, void *user
)
932 isl_union_set
**uset
= (isl_union_set
**)user
;
934 *uset
= isl_union_set_add_set(*uset
, FN(PART
,domain
)(part
));
939 __isl_give isl_union_set
*FN(UNION
,domain
)(__isl_take UNION
*u
)
943 uset
= isl_union_set_empty(FN(UNION
,get_space
)(u
));
944 if (FN(FN(UNION
,foreach
),BASE
)(u
, &FN(UNION
,domain_entry
), &uset
) < 0)
951 isl_union_set_free(uset
);
957 /* Negate the type of "u".
959 static __isl_give UNION
*FN(UNION
,negate_type
)(__isl_take UNION
*u
)
961 u
= FN(UNION
,cow
)(u
);
964 u
->type
= isl_fold_type_negate(u
->type
);
968 /* Negate the type of "u".
969 * Since "u" does not have a type, do nothing.
971 static __isl_give UNION
*FN(UNION
,negate_type
)(__isl_take UNION
*u
)
977 /* Multiply "part" by the isl_val "user" and return the result.
979 static __isl_give PART
*FN(UNION
,scale_val_entry
)(__isl_take PART
*part
,
984 return FN(PART
,scale_val
)(part
, isl_val_copy(v
));
987 /* Multiply "u" by "v" and return the result.
989 __isl_give UNION
*FN(UNION
,scale_val
)(__isl_take UNION
*u
,
990 __isl_take isl_val
*v
)
994 if (isl_val_is_one(v
)) {
999 if (DEFAULT_IS_ZERO
&& u
&& isl_val_is_zero(v
)) {
1001 isl_space
*space
= FN(UNION
,get_space
)(u
);
1002 zero
= FN(UNION
,ZERO
)(space
OPT_TYPE_ARG(u
->));
1008 if (!isl_val_is_rat(v
))
1009 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1010 "expecting rational factor", goto error
);
1012 u
= FN(UNION
,transform_inplace
)(u
, &FN(UNION
,scale_val_entry
), v
);
1013 if (isl_val_is_neg(v
))
1014 u
= FN(UNION
,negate_type
)(u
);
1024 /* Divide "part" by the isl_val "user" and return the result.
1026 static __isl_give PART
*FN(UNION
,scale_down_val_entry
)(__isl_take PART
*part
,
1031 return FN(PART
,scale_down_val
)(part
, isl_val_copy(v
));
1034 /* Divide "u" by "v" and return the result.
1036 __isl_give UNION
*FN(UNION
,scale_down_val
)(__isl_take UNION
*u
,
1037 __isl_take isl_val
*v
)
1041 if (isl_val_is_one(v
)) {
1046 if (!isl_val_is_rat(v
))
1047 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1048 "expecting rational factor", goto error
);
1049 if (isl_val_is_zero(v
))
1050 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1051 "cannot scale down by zero", goto error
);
1053 u
= FN(UNION
,transform_inplace
)(u
, &FN(UNION
,scale_down_val_entry
), v
);
1054 if (isl_val_is_neg(v
))
1055 u
= FN(UNION
,negate_type
)(u
);
1065 S(UNION
,plain_is_equal_data
)
1071 static isl_stat
FN(UNION
,plain_is_equal_entry
)(void **entry
, void *user
)
1073 S(UNION
,plain_is_equal_data
) *data
= user
;
1074 struct isl_hash_table_entry
*entry2
;
1077 entry2
= FN(UNION
,find_part_entry
)(data
->u2
, pw
->dim
, 0);
1078 if (!entry2
|| entry2
== isl_hash_table_entry_none
) {
1080 data
->is_equal
= isl_bool_error
;
1082 data
->is_equal
= isl_bool_false
;
1083 return isl_stat_error
;
1086 data
->is_equal
= FN(PW
,plain_is_equal
)(pw
, entry2
->data
);
1087 if (data
->is_equal
< 0 || !data
->is_equal
)
1088 return isl_stat_error
;
1093 isl_bool
FN(UNION
,plain_is_equal
)(__isl_keep UNION
*u1
, __isl_keep UNION
*u2
)
1095 S(UNION
,plain_is_equal_data
) data
= { NULL
, isl_bool_true
};
1099 return isl_bool_error
;
1101 return isl_bool_true
;
1102 if (u1
->table
.n
!= u2
->table
.n
)
1103 return isl_bool_false
;
1104 n1
= FN(FN(UNION
,n
),BASE
)(u1
);
1105 n2
= FN(FN(UNION
,n
),BASE
)(u2
);
1106 if (n1
< 0 || n2
< 0)
1107 return isl_bool_error
;
1109 return isl_bool_false
;
1111 u1
= FN(UNION
,copy
)(u1
);
1112 u2
= FN(UNION
,copy
)(u2
);
1113 u1
= FN(UNION
,align_params
)(u1
, FN(UNION
,get_space
)(u2
));
1114 u2
= FN(UNION
,align_params
)(u2
, FN(UNION
,get_space
)(u1
));
1119 if (FN(UNION
,foreach_inplace
)(u1
,
1120 &FN(UNION
,plain_is_equal_entry
), &data
) < 0 &&
1127 return data
.is_equal
;
1131 return isl_bool_error
;
1134 /* Check whether the element that "entry" points to involves any NaNs and
1135 * store the result in *nan.
1136 * Abort as soon as one such element has been found.
1138 static isl_stat
FN(UNION
,involves_nan_entry
)(void **entry
, void *user
)
1140 isl_bool
*nan
= user
;
1143 *nan
= FN(PW
,involves_nan
)(pw
);
1144 if (*nan
< 0 || !nan
)
1145 return isl_stat_error
;
1150 /* Does "u" involve any NaNs?
1152 isl_bool
FN(UNION
,involves_nan
)(__isl_keep UNION
*u
)
1154 isl_bool nan
= isl_bool_false
;
1157 return isl_bool_error
;
1159 if (FN(UNION
,foreach_inplace
)(u
,
1160 &FN(UNION
,involves_nan_entry
), &nan
) < 0 &&
1162 return isl_bool_error
;
1167 /* Internal data structure for isl_union_*_drop_dims.
1168 * type, first and n are passed to isl_*_drop_dims.
1170 S(UNION
,drop_dims_data
) {
1171 enum isl_dim_type type
;
1176 /* Drop the parameters specified by "data" from "part" and return the result.
1178 static __isl_give PART
*FN(UNION
,drop_dims_entry
)(__isl_take PART
*part
,
1181 S(UNION
,drop_dims_data
) *data
= user
;
1183 return FN(PART
,drop_dims
)(part
, data
->type
, data
->first
, data
->n
);
1186 /* Drop the specified parameters from "u".
1187 * That is, type is required to be isl_dim_param.
1189 __isl_give UNION
*FN(UNION
,drop_dims
)( __isl_take UNION
*u
,
1190 enum isl_dim_type type
, unsigned first
, unsigned n
)
1193 S(UNION
,drop_dims_data
) data
= { type
, first
, n
};
1194 S(UNION
,transform_control
) control
= {
1195 .fn
= &FN(UNION
,drop_dims_entry
),
1202 if (type
!= isl_dim_param
)
1203 isl_die(FN(UNION
,get_ctx
)(u
), isl_error_invalid
,
1204 "can only project out parameters",
1205 return FN(UNION
,free
)(u
));
1207 space
= FN(UNION
,get_space
)(u
);
1208 space
= isl_space_drop_dims(space
, type
, first
, n
);
1209 return FN(UNION
,transform_space
)(u
, space
, &control
);
1212 /* Internal data structure for isl_union_*_set_dim_name.
1213 * pos is the position of the parameter that needs to be renamed.
1214 * s is the new name.
1216 S(UNION
,set_dim_name_data
) {
1221 /* Change the name of the parameter at position data->pos of "part" to data->s
1222 * and return the result.
1224 static __isl_give PART
*FN(UNION
,set_dim_name_entry
)(__isl_take PART
*part
,
1227 S(UNION
,set_dim_name_data
) *data
= user
;
1229 return FN(PART
,set_dim_name
)(part
, isl_dim_param
, data
->pos
, data
->s
);
1232 /* Change the name of the parameter at position "pos" to "s".
1233 * That is, type is required to be isl_dim_param.
1235 __isl_give UNION
*FN(UNION
,set_dim_name
)(__isl_take UNION
*u
,
1236 enum isl_dim_type type
, unsigned pos
, const char *s
)
1238 S(UNION
,set_dim_name_data
) data
= { pos
, s
};
1239 S(UNION
,transform_control
) control
= {
1240 .fn
= &FN(UNION
,set_dim_name_entry
),
1248 if (type
!= isl_dim_param
)
1249 isl_die(FN(UNION
,get_ctx
)(u
), isl_error_invalid
,
1250 "can only set parameter names",
1251 return FN(UNION
,free
)(u
));
1253 space
= FN(UNION
,get_space
)(u
);
1254 space
= isl_space_set_dim_name(space
, type
, pos
, s
);
1255 return FN(UNION
,transform_space
)(u
, space
, &control
);
1258 /* Reset the user pointer on all identifiers of parameters and tuples
1259 * of the space of "part" and return the result.
1261 static __isl_give PART
*FN(UNION
,reset_user_entry
)(__isl_take PART
*part
,
1264 return FN(PART
,reset_user
)(part
);
1267 /* Reset the user pointer on all identifiers of parameters and tuples
1268 * of the spaces of "u".
1270 __isl_give UNION
*FN(UNION
,reset_user
)(__isl_take UNION
*u
)
1272 S(UNION
,transform_control
) control
= {
1273 .fn
= &FN(UNION
,reset_user_entry
),
1277 space
= FN(UNION
,get_space
)(u
);
1278 space
= isl_space_reset_user(space
);
1279 return FN(UNION
,transform_space
)(u
, space
, &control
);
1282 /* Add the base expression held by "entry" to "list".
1284 static isl_stat
FN(UNION
,add_to_list
)(void **entry
, void *user
)
1287 LIST(PART
) **list
= user
;
1289 *list
= FN(LIST(PART
),add
)(*list
, FN(PART
,copy
)(pw
));
1291 return isl_stat_error
;
1296 /* Return a list containing all the base expressions in "u".
1298 * First construct a list of the appropriate size and
1299 * then add all the elements.
1301 __isl_give
LIST(PART
) *FN(FN(UNION
,get
),LIST(BASE
))(__isl_keep UNION
*u
)
1308 n
= FN(FN(UNION
,n
),BASE
)(u
);
1311 list
= FN(LIST(PART
),alloc
)(FN(UNION
,get_ctx(u
)), n
);
1312 if (FN(UNION
,foreach_inplace
)(u
, &FN(UNION
,add_to_list
), &list
) < 0)
1313 return FN(LIST(PART
),free
)(list
);