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
13 #include <isl_hash_private.h>
14 #include <isl_union_macro.h>
16 /* A union of expressions defined over different domain spaces.
17 * "space" describes the parameters.
18 * The entries of "table" are keyed on the domain space of the entry.
27 struct isl_hash_table table
;
30 __isl_give UNION
*FN(UNION
,cow
)(__isl_take UNION
*u
);
32 isl_ctx
*FN(UNION
,get_ctx
)(__isl_keep UNION
*u
)
34 return u
? u
->space
->ctx
: NULL
;
37 __isl_give isl_space
*FN(UNION
,get_space
)(__isl_keep UNION
*u
)
41 return isl_space_copy(u
->space
);
44 /* Return the number of parameters of "u", where "type"
45 * is required to be set to isl_dim_param.
47 unsigned FN(UNION
,dim
)(__isl_keep UNION
*u
, enum isl_dim_type type
)
52 if (type
!= isl_dim_param
)
53 isl_die(FN(UNION
,get_ctx
)(u
), isl_error_invalid
,
54 "can only reference parameters", return 0);
56 return isl_space_dim(u
->space
, type
);
59 /* Return the position of the parameter with the given name
61 * Return -1 if no such dimension can be found.
63 int FN(UNION
,find_dim_by_name
)(__isl_keep UNION
*u
, enum isl_dim_type type
,
68 return isl_space_find_dim_by_name(u
->space
, type
, name
);
72 static __isl_give UNION
*FN(UNION
,alloc
)(__isl_take isl_space
*dim
,
73 enum isl_fold type
, int size
)
75 static __isl_give UNION
*FN(UNION
,alloc
)(__isl_take isl_space
*dim
, int size
)
80 dim
= isl_space_params(dim
);
84 u
= isl_calloc_type(dim
->ctx
, UNION
);
93 if (isl_hash_table_init(dim
->ctx
, &u
->table
, size
) < 0)
94 return FN(UNION
,free
)(u
);
103 __isl_give UNION
*FN(UNION
,ZERO
)(__isl_take isl_space
*dim
, enum isl_fold type
)
105 return FN(UNION
,alloc
)(dim
, type
, 16);
108 __isl_give UNION
*FN(UNION
,ZERO
)(__isl_take isl_space
*dim
)
110 return FN(UNION
,alloc
)(dim
, 16);
114 __isl_give UNION
*FN(UNION
,copy
)(__isl_keep UNION
*u
)
123 /* Return the number of base expressions in "u".
125 int FN(FN(UNION
,n
),PARTS
)(__isl_keep UNION
*u
)
127 return u
? u
->table
.n
: 0;
130 S(UNION
,foreach_data
)
132 isl_stat (*fn
)(__isl_take PART
*part
, void *user
);
136 static isl_stat
FN(UNION
,call_on_copy
)(void **entry
, void *user
)
139 S(UNION
,foreach_data
) *data
= (S(UNION
,foreach_data
) *)user
;
141 part
= FN(PART
,copy
)(part
);
143 return isl_stat_error
;
144 return data
->fn(part
, data
->user
);
147 isl_stat
FN(FN(UNION
,foreach
),PARTS
)(__isl_keep UNION
*u
,
148 isl_stat (*fn
)(__isl_take PART
*part
, void *user
), void *user
)
150 S(UNION
,foreach_data
) data
= { fn
, user
};
153 return isl_stat_error
;
155 return isl_hash_table_foreach(u
->space
->ctx
, &u
->table
,
156 &FN(UNION
,call_on_copy
), &data
);
159 /* Is the domain space of "entry" equal to the domain of "space"?
161 static int FN(UNION
,has_same_domain_space
)(const void *entry
, const void *val
)
163 PART
*part
= (PART
*)entry
;
164 isl_space
*space
= (isl_space
*) val
;
166 if (isl_space_is_set(space
))
167 return isl_space_is_set(part
->dim
);
169 return isl_space_tuple_is_equal(part
->dim
, isl_dim_in
,
173 /* Return the entry, if any, in "u" that lives in "space".
174 * If "reserve" is set, then an entry is created if it does not exist yet.
175 * Return NULL on error and isl_hash_table_entry_none if no entry was found.
176 * Note that when "reserve" is set, the function will never return
177 * isl_hash_table_entry_none.
179 * First look for the entry (if any) with the same domain space.
180 * If it exists, then check if the range space also matches.
182 static struct isl_hash_table_entry
*FN(UNION
,find_part_entry
)(
183 __isl_keep UNION
*u
, __isl_keep isl_space
*space
, int reserve
)
187 struct isl_hash_table_entry
*entry
;
194 ctx
= FN(UNION
,get_ctx
)(u
);
195 hash
= isl_space_get_domain_hash(space
);
196 entry
= isl_hash_table_find(ctx
, &u
->table
, hash
,
197 &FN(UNION
,has_same_domain_space
), space
, reserve
);
199 return reserve
? NULL
: isl_hash_table_entry_none
;
200 if (reserve
&& !entry
->data
)
203 equal
= isl_space_tuple_is_equal(part
->dim
, isl_dim_out
,
210 return isl_hash_table_entry_none
;
211 isl_die(FN(UNION
,get_ctx
)(u
), isl_error_invalid
,
212 "union expression can only contain a single "
213 "expression over a given domain", return NULL
);
216 /* Remove "part_entry" from the hash table of "u".
218 static __isl_give UNION
*FN(UNION
,remove_part_entry
)(__isl_take UNION
*u
,
219 struct isl_hash_table_entry
*part_entry
)
223 if (!u
|| !part_entry
)
224 return FN(UNION
,free
)(u
);
226 ctx
= FN(UNION
,get_ctx
)(u
);
227 isl_hash_table_remove(ctx
, &u
->table
, part_entry
);
228 FN(PART
,free
)(part_entry
->data
);
233 /* Extract the element of "u" living in "space" (ignoring parameters).
235 * Return the ZERO element if "u" does not contain any element
238 __isl_give PART
*FN(FN(UNION
,extract
),PARTS
)(__isl_keep UNION
*u
,
239 __isl_take isl_space
*space
)
241 struct isl_hash_table_entry
*entry
;
245 if (!isl_space_match(u
->space
, isl_dim_param
, space
, isl_dim_param
)) {
246 space
= isl_space_drop_dims(space
, isl_dim_param
,
247 0, isl_space_dim(space
, isl_dim_param
));
248 space
= isl_space_align_params(space
,
249 FN(UNION
,get_space
)(u
));
254 entry
= FN(UNION
,find_part_entry
)(u
, space
, 0);
257 if (entry
== isl_hash_table_entry_none
)
259 return FN(PART
,ZERO
)(space
, u
->type
);
261 return FN(PART
,ZERO
)(space
);
263 isl_space_free(space
);
264 return FN(PART
,copy
)(entry
->data
);
266 isl_space_free(space
);
270 /* Check that the domain of "part" is disjoint from the domain of the entries
271 * in "u" that are defined on the same domain space, but have a different
273 * Since a UNION is currently not allowed to contain two entries
274 * with the same domain space, there cannot be any such other entry.
276 static isl_stat
FN(UNION
,check_disjoint_domain_other
)(__isl_keep UNION
*u
,
277 __isl_keep PART
*part
)
282 /* Check that the domain of "part1" is disjoint from the domain of "part2".
283 * This check is performed before "part2" is added to a UNION to ensure
284 * that the UNION expression remains a function.
285 * Since a UNION is currently not allowed to contain two entries
286 * with the same domain space, fail unconditionally.
288 static isl_stat
FN(UNION
,check_disjoint_domain
)(__isl_keep PART
*part1
,
289 __isl_keep PART
*part2
)
291 isl_die(FN(PART
,get_ctx
)(part1
), isl_error_invalid
,
292 "additional part should live on separate space",
293 return isl_stat_error
);
296 /* Add "part" to "u".
297 * If "disjoint" is set, then "u" is not allowed to already have
298 * a part that is defined over a domain that overlaps with the domain
300 * Otherwise, compute the union sum of "part" and the part in "u"
301 * defined on the same space.
303 static __isl_give UNION
*FN(UNION
,add_part_generic
)(__isl_take UNION
*u
,
304 __isl_take PART
*part
, int disjoint
)
307 struct isl_hash_table_entry
*entry
;
312 empty
= FN(PART
,IS_ZERO
)(part
);
320 u
= FN(UNION
,align_params
)(u
, FN(PART
,get_space
)(part
));
321 part
= FN(PART
,align_params
)(part
, FN(UNION
,get_space
)(u
));
323 u
= FN(UNION
,cow
)(u
);
328 if (FN(UNION
,check_disjoint_domain_other
)(u
, part
) < 0)
330 entry
= FN(UNION
,find_part_entry
)(u
, part
->dim
, 1);
338 FN(UNION
,check_disjoint_domain
)(entry
->data
, part
) < 0)
340 entry
->data
= FN(PART
,union_add_
)(entry
->data
,
341 FN(PART
,copy
)(part
));
344 empty
= FN(PART
,IS_ZERO
)(part
);
348 u
= FN(UNION
,remove_part_entry
)(u
, entry
);
359 /* Add "part" to "u", where "u" is assumed not to already have
360 * a part that is defined on the same space as "part".
362 __isl_give UNION
*FN(FN(UNION
,add
),PARTS
)(__isl_take UNION
*u
,
363 __isl_take PART
*part
)
365 return FN(UNION
,add_part_generic
)(u
, part
, 1);
369 /* Allocate a UNION with the same type and the same size as "u" and
370 * with space "space".
372 static __isl_give UNION
*FN(UNION
,alloc_same_size_on_space
)(__isl_keep UNION
*u
,
373 __isl_take isl_space
*space
)
376 space
= isl_space_free(space
);
377 return FN(UNION
,alloc
)(space
, u
->type
, u
->table
.n
);
380 /* Allocate a UNION with the same size as "u" and with space "space".
382 static __isl_give UNION
*FN(UNION
,alloc_same_size_on_space
)(__isl_keep UNION
*u
,
383 __isl_take isl_space
*space
)
386 space
= isl_space_free(space
);
387 return FN(UNION
,alloc
)(space
, u
->table
.n
);
391 /* Allocate a UNION with the same space, the same type (if any) and
392 * the same size as "u".
394 static __isl_give UNION
*FN(UNION
,alloc_same_size
)(__isl_keep UNION
*u
)
396 return FN(UNION
,alloc_same_size_on_space
)(u
, FN(UNION
,get_space
)(u
));
399 /* Call "fn" on each part entry of "u".
401 static isl_stat
FN(UNION
,foreach_inplace
)(__isl_keep UNION
*u
,
402 isl_stat (*fn
)(void **part
, void *user
), void *user
)
407 return isl_stat_error
;
408 ctx
= FN(UNION
,get_ctx
)(u
);
409 return isl_hash_table_foreach(ctx
, &u
->table
, fn
, user
);
412 /* Does "u" have a single reference?
413 * That is, can we change "u" inplace?
415 static isl_bool
FN(UNION
,has_single_reference
)(__isl_keep UNION
*u
)
418 return isl_bool_error
;
422 /* Internal data structure for isl_union_*_transform_space.
423 * "fn' is applied to each entry in the input.
424 * "res" collects the results.
426 S(UNION
,transform_data
)
428 __isl_give PART
*(*fn
)(__isl_take PART
*part
, void *user
);
434 /* Apply data->fn to "part" and add the result to data->res.
436 static isl_stat
FN(UNION
,transform_entry
)(__isl_take PART
*part
, void *user
)
438 S(UNION
,transform_data
) *data
= (S(UNION
,transform_data
) *)user
;
440 part
= data
->fn(part
, data
->user
);
441 data
->res
= FN(FN(UNION
,add
),PARTS
)(data
->res
, part
);
443 return isl_stat_error
;
448 /* Return a UNION living in "space" that is obtained by applying "fn"
449 * to each of the entries in "u".
451 static __isl_give UNION
*FN(UNION
,transform_space
)(__isl_take UNION
*u
,
453 __isl_give PART
*(*fn
)(__isl_take PART
*part
, void *user
), void *user
)
455 S(UNION
,transform_data
) data
= { fn
, user
};
457 data
.res
= FN(UNION
,alloc_same_size_on_space
)(u
, space
);
458 if (FN(FN(UNION
,foreach
),PARTS
)(u
,
459 &FN(UNION
,transform_entry
), &data
) < 0)
460 data
.res
= FN(UNION
,free
)(data
.res
);
465 /* Return a UNION that lives in the same space as "u" and that is obtained
466 * by applying "fn" to each of the entries in "u".
468 static __isl_give UNION
*FN(UNION
,transform
)(__isl_take UNION
*u
,
469 __isl_give PART
*(*fn
)(__isl_take PART
*part
, void *user
), void *user
)
471 return FN(UNION
,transform_space
)(u
, FN(UNION
,get_space
)(u
), fn
, user
);
474 /* Apply data->fn to *part and store the result back into *part.
476 static isl_stat
FN(UNION
,transform_inplace_entry
)(void **part
, void *user
)
478 S(UNION
,transform_data
) *data
= (S(UNION
,transform_data
) *) user
;
480 *part
= data
->fn(*part
, data
->user
);
482 return isl_stat_error
;
486 /* Update "u" by applying "fn" to each entry.
487 * This operation is assumed not to change the number of entries nor
488 * the spaces of the entries.
490 * If there is only one reference to "u", then change "u" inplace.
491 * Otherwise, create a new UNION from "u" and discard the original.
493 static __isl_give UNION
*FN(UNION
,transform_inplace
)(__isl_take UNION
*u
,
494 __isl_give PART
*(*fn
)(__isl_take PART
*part
, void *user
), void *user
)
498 single_ref
= FN(UNION
,has_single_reference
)(u
);
500 return FN(UNION
,free
)(u
);
502 S(UNION
,transform_data
) data
= { fn
, user
};
503 if (FN(UNION
,foreach_inplace
)(u
,
504 &FN(UNION
,transform_inplace_entry
), &data
) < 0)
505 return FN(UNION
,free
)(u
);
508 return FN(UNION
,transform
)(u
, fn
, user
);
511 /* An isl_union_*_transform callback for use in isl_union_*_dup
512 * that simply returns "part".
514 static __isl_give PART
*FN(UNION
,copy_part
)(__isl_take PART
*part
, void *user
)
519 __isl_give UNION
*FN(UNION
,dup
)(__isl_keep UNION
*u
)
521 u
= FN(UNION
,copy
)(u
);
522 return FN(UNION
,transform
)(u
, &FN(UNION
,copy_part
), NULL
);
525 __isl_give UNION
*FN(UNION
,cow
)(__isl_take UNION
*u
)
533 return FN(UNION
,dup
)(u
);
536 static isl_stat
FN(UNION
,free_u_entry
)(void **entry
, void *user
)
543 __isl_null UNION
*FN(UNION
,free
)(__isl_take UNION
*u
)
551 isl_hash_table_foreach(u
->space
->ctx
, &u
->table
,
552 &FN(UNION
,free_u_entry
), NULL
);
553 isl_hash_table_clear(&u
->table
);
554 isl_space_free(u
->space
);
559 static __isl_give PART
*FN(UNION
,align_entry
)(__isl_take PART
*part
, void *user
)
561 isl_reordering
*exp
= user
;
563 exp
= isl_reordering_extend_space(isl_reordering_copy(exp
),
564 FN(PART
,get_domain_space
)(part
));
565 return FN(PART
,realign_domain
)(part
, exp
);
568 /* Reorder the parameters of "u" according to the given reordering.
570 static __isl_give UNION
*FN(UNION
,realign_domain
)(__isl_take UNION
*u
,
571 __isl_take isl_reordering
*r
)
578 space
= isl_space_copy(r
->dim
);
579 u
= FN(UNION
,transform_space
)(u
, space
, &FN(UNION
,align_entry
), r
);
580 isl_reordering_free(r
);
584 isl_reordering_free(r
);
588 /* Align the parameters of "u" to those of "model".
590 __isl_give UNION
*FN(UNION
,align_params
)(__isl_take UNION
*u
,
591 __isl_take isl_space
*model
)
598 if (isl_space_match(u
->space
, isl_dim_param
, model
, isl_dim_param
)) {
599 isl_space_free(model
);
603 model
= isl_space_params(model
);
604 r
= isl_parameter_alignment_reordering(u
->space
, model
);
605 isl_space_free(model
);
607 return FN(UNION
,realign_domain
)(u
, r
);
609 isl_space_free(model
);
614 /* Add "part" to *u, taking the union sum if "u" already has
615 * a part defined on the same space as "part".
617 static isl_stat
FN(UNION
,union_add_part
)(__isl_take PART
*part
, void *user
)
619 UNION
**u
= (UNION
**)user
;
621 *u
= FN(UNION
,add_part_generic
)(*u
, part
, 0);
626 /* Compute the sum of "u1" and "u2" on the union of their domains,
627 * with the actual sum on the shared domain and
628 * the defined expression on the symmetric difference of the domains.
630 * This is an internal function that is exposed under different
631 * names depending on whether the base expressions have a zero default
633 * If they do, then this function is called "add".
634 * Otherwise, it is called "union_add".
636 static __isl_give UNION
*FN(UNION
,union_add_
)(__isl_take UNION
*u1
,
637 __isl_take UNION
*u2
)
639 u1
= FN(UNION
,align_params
)(u1
, FN(UNION
,get_space
)(u2
));
640 u2
= FN(UNION
,align_params
)(u2
, FN(UNION
,get_space
)(u1
));
642 u1
= FN(UNION
,cow
)(u1
);
647 if (FN(FN(UNION
,foreach
),PARTS
)(u2
, &FN(UNION
,union_add_part
), &u1
) < 0)
659 __isl_give UNION
*FN(FN(UNION
,from
),PARTS
)(__isl_take PART
*part
)
667 dim
= FN(PART
,get_space
)(part
);
668 dim
= isl_space_drop_dims(dim
, isl_dim_in
, 0, isl_space_dim(dim
, isl_dim_in
));
669 dim
= isl_space_drop_dims(dim
, isl_dim_out
, 0, isl_space_dim(dim
, isl_dim_out
));
671 u
= FN(UNION
,ZERO
)(dim
, part
->type
);
673 u
= FN(UNION
,ZERO
)(dim
);
675 u
= FN(FN(UNION
,add
),PARTS
)(u
, part
);
680 S(UNION
,match_bin_data
) {
683 __isl_give PART
*(*fn
)(__isl_take PART
*, __isl_take PART
*);
686 /* Check if data->u2 has an element living in the same space as "part".
687 * If so, call data->fn on the two elements and add the result to
690 static isl_stat
FN(UNION
,match_bin_entry
)(__isl_take PART
*part
, void *user
)
692 S(UNION
,match_bin_data
) *data
= user
;
693 struct isl_hash_table_entry
*entry2
;
697 space
= FN(PART
,get_space
)(part
);
698 entry2
= FN(UNION
,find_part_entry
)(data
->u2
, space
, 0);
699 isl_space_free(space
);
702 if (entry2
== isl_hash_table_entry_none
) {
707 part2
= entry2
->data
;
708 if (!isl_space_tuple_is_equal(part
->dim
, isl_dim_out
,
709 part2
->dim
, isl_dim_out
))
710 isl_die(FN(UNION
,get_ctx
)(data
->u2
), isl_error_invalid
,
711 "entries should have the same range space",
714 part
= data
->fn(part
, FN(PART
, copy
)(entry2
->data
));
716 data
->res
= FN(FN(UNION
,add
),PARTS
)(data
->res
, part
);
718 return isl_stat_error
;
723 return isl_stat_error
;
726 /* This function is currently only used from isl_polynomial.c
727 * and not from isl_fold.c.
729 static __isl_give UNION
*FN(UNION
,match_bin_op
)(__isl_take UNION
*u1
,
730 __isl_take UNION
*u2
,
731 __isl_give PART
*(*fn
)(__isl_take PART
*, __isl_take PART
*))
732 __attribute__ ((unused
));
733 /* For each pair of elements in "u1" and "u2" living in the same space,
734 * call "fn" and collect the results.
736 static __isl_give UNION
*FN(UNION
,match_bin_op
)(__isl_take UNION
*u1
,
737 __isl_take UNION
*u2
,
738 __isl_give PART
*(*fn
)(__isl_take PART
*, __isl_take PART
*))
740 S(UNION
,match_bin_data
) data
= { NULL
, NULL
, fn
};
742 u1
= FN(UNION
,align_params
)(u1
, FN(UNION
,get_space
)(u2
));
743 u2
= FN(UNION
,align_params
)(u2
, FN(UNION
,get_space
)(u1
));
749 data
.res
= FN(UNION
,alloc_same_size
)(u1
);
750 if (FN(FN(UNION
,foreach
),PARTS
)(u1
,
751 &FN(UNION
,match_bin_entry
), &data
) < 0)
760 FN(UNION
,free
)(data
.res
);
764 /* Compute the sum of "u1" and "u2".
766 * If the base expressions have a default zero value, then the sum
767 * is computed on the union of the domains of "u1" and "u2".
768 * Otherwise, it is computed on their shared domains.
770 __isl_give UNION
*FN(UNION
,add
)(__isl_take UNION
*u1
, __isl_take UNION
*u2
)
773 return FN(UNION
,union_add_
)(u1
, u2
);
775 return FN(UNION
,match_bin_op
)(u1
, u2
, &FN(PART
,add
));
780 /* Subtract "u2" from "u1" and return the result.
782 __isl_give UNION
*FN(UNION
,sub
)(__isl_take UNION
*u1
, __isl_take UNION
*u2
)
784 return FN(UNION
,match_bin_op
)(u1
, u2
, &FN(PART
,sub
));
788 S(UNION
,any_set_data
) {
790 __isl_give PW
*(*fn
)(__isl_take PW
*, __isl_take isl_set
*);
793 static __isl_give PART
*FN(UNION
,any_set_entry
)(__isl_take PART
*part
,
796 S(UNION
,any_set_data
) *data
= user
;
798 return data
->fn(part
, isl_set_copy(data
->set
));
801 /* Update each element of "u" by calling "fn" on the element and "set".
803 static __isl_give UNION
*FN(UNION
,any_set_op
)(__isl_take UNION
*u
,
804 __isl_take isl_set
*set
,
805 __isl_give PW
*(*fn
)(__isl_take PW
*, __isl_take isl_set
*))
807 S(UNION
,any_set_data
) data
= { NULL
, fn
};
809 u
= FN(UNION
,align_params
)(u
, isl_set_get_space(set
));
810 set
= isl_set_align_params(set
, FN(UNION
,get_space
)(u
));
816 u
= FN(UNION
,transform
)(u
, &FN(UNION
,any_set_entry
), &data
);
825 /* Intersect the domain of "u" with the parameter domain "context".
827 __isl_give UNION
*FN(UNION
,intersect_params
)(__isl_take UNION
*u
,
828 __isl_take isl_set
*set
)
830 return FN(UNION
,any_set_op
)(u
, set
, &FN(PW
,intersect_params
));
833 /* Compute the gist of the domain of "u" with respect to
834 * the parameter domain "context".
836 __isl_give UNION
*FN(UNION
,gist_params
)(__isl_take UNION
*u
,
837 __isl_take isl_set
*set
)
839 return FN(UNION
,any_set_op
)(u
, set
, &FN(PW
,gist_params
));
842 S(UNION
,match_domain_data
) {
845 __isl_give PW
*(*fn
)(__isl_take PW
*, __isl_take isl_set
*);
848 static int FN(UNION
,set_has_dim
)(const void *entry
, const void *val
)
850 isl_set
*set
= (isl_set
*)entry
;
851 isl_space
*dim
= (isl_space
*)val
;
853 return isl_space_is_equal(set
->dim
, dim
);
856 /* Find the set in data->uset that lives in the same space as the domain
857 * of "part", apply data->fn to *entry and this set (if any), and add
858 * the result to data->res.
860 static isl_stat
FN(UNION
,match_domain_entry
)(__isl_take PART
*part
, void *user
)
862 S(UNION
,match_domain_data
) *data
= user
;
864 struct isl_hash_table_entry
*entry2
;
867 space
= FN(PART
,get_domain_space
)(part
);
868 hash
= isl_space_get_hash(space
);
869 entry2
= isl_hash_table_find(data
->uset
->dim
->ctx
, &data
->uset
->table
,
870 hash
, &FN(UNION
,set_has_dim
), space
, 0);
871 isl_space_free(space
);
877 part
= data
->fn(part
, isl_set_copy(entry2
->data
));
879 data
->res
= FN(FN(UNION
,add
),PARTS
)(data
->res
, part
);
881 return isl_stat_error
;
886 /* Apply fn to each pair of PW in u and set in uset such that
887 * the set lives in the same space as the domain of PW
888 * and collect the results.
890 static __isl_give UNION
*FN(UNION
,match_domain_op
)(__isl_take UNION
*u
,
891 __isl_take isl_union_set
*uset
,
892 __isl_give PW
*(*fn
)(__isl_take PW
*, __isl_take isl_set
*))
894 S(UNION
,match_domain_data
) data
= { NULL
, NULL
, fn
};
896 u
= FN(UNION
,align_params
)(u
, isl_union_set_get_space(uset
));
897 uset
= isl_union_set_align_params(uset
, FN(UNION
,get_space
)(u
));
903 data
.res
= FN(UNION
,alloc_same_size
)(u
);
904 if (FN(FN(UNION
,foreach
),PARTS
)(u
,
905 &FN(UNION
,match_domain_entry
), &data
) < 0)
909 isl_union_set_free(uset
);
913 isl_union_set_free(uset
);
914 FN(UNION
,free
)(data
.res
);
918 /* Intersect the domain of "u" with "uset".
919 * If "uset" is a parameters domain, then intersect the parameter
920 * domain of "u" with this set.
922 __isl_give UNION
*FN(UNION
,intersect_domain
)(__isl_take UNION
*u
,
923 __isl_take isl_union_set
*uset
)
925 if (isl_union_set_is_params(uset
))
926 return FN(UNION
,intersect_params
)(u
,
927 isl_set_from_union_set(uset
));
928 return FN(UNION
,match_domain_op
)(u
, uset
, &FN(PW
,intersect_domain
));
931 /* Take the set (which may be empty) in data->uset that lives
932 * in the same space as the domain of "pw", subtract it from the domain
933 * of "part" and return the result.
935 static __isl_give PART
*FN(UNION
,subtract_domain_entry
)(__isl_take PART
*part
,
938 isl_union_set
*uset
= user
;
942 space
= FN(PART
,get_domain_space
)(part
);
943 set
= isl_union_set_extract_set(uset
, space
);
944 return FN(PART
,subtract_domain
)(part
, set
);
947 /* Subtract "uset' from the domain of "u".
949 __isl_give UNION
*FN(UNION
,subtract_domain
)(__isl_take UNION
*u
,
950 __isl_take isl_union_set
*uset
)
952 u
= FN(UNION
,transform
)(u
, &FN(UNION
,subtract_domain_entry
), uset
);
953 isl_union_set_free(uset
);
957 __isl_give UNION
*FN(UNION
,gist
)(__isl_take UNION
*u
,
958 __isl_take isl_union_set
*uset
)
960 if (isl_union_set_is_params(uset
))
961 return FN(UNION
,gist_params
)(u
, isl_set_from_union_set(uset
));
962 return FN(UNION
,match_domain_op
)(u
, uset
, &FN(PW
,gist
));
965 /* Coalesce an entry in a UNION. Coalescing is performed in-place.
966 * Since the UNION may have several references, the entry is only
967 * replaced if the coalescing is successful.
969 static isl_stat
FN(UNION
,coalesce_entry
)(void **entry
, void *user
)
971 PART
**part_p
= (PART
**) entry
;
974 part
= FN(PART
,copy
)(*part_p
);
975 part
= FN(PW
,coalesce
)(part
);
977 return isl_stat_error
;
978 FN(PART
,free
)(*part_p
);
984 __isl_give UNION
*FN(UNION
,coalesce
)(__isl_take UNION
*u
)
986 if (FN(UNION
,foreach_inplace
)(u
, &FN(UNION
,coalesce_entry
), NULL
) < 0)
995 static isl_stat
FN(UNION
,domain_entry
)(__isl_take PART
*part
, void *user
)
997 isl_union_set
**uset
= (isl_union_set
**)user
;
999 *uset
= isl_union_set_add_set(*uset
, FN(PART
,domain
)(part
));
1004 __isl_give isl_union_set
*FN(UNION
,domain
)(__isl_take UNION
*u
)
1006 isl_union_set
*uset
;
1008 uset
= isl_union_set_empty(FN(UNION
,get_space
)(u
));
1009 if (FN(FN(UNION
,foreach
),PARTS
)(u
, &FN(UNION
,domain_entry
), &uset
) < 0)
1016 isl_union_set_free(uset
);
1022 /* Negate the type of "u".
1024 static __isl_give UNION
*FN(UNION
,negate_type
)(__isl_take UNION
*u
)
1026 u
= FN(UNION
,cow
)(u
);
1029 u
->type
= isl_fold_type_negate(u
->type
);
1033 /* Negate the type of "u".
1034 * Since "u" does not have a type, do nothing.
1036 static __isl_give UNION
*FN(UNION
,negate_type
)(__isl_take UNION
*u
)
1042 static __isl_give PART
*FN(UNION
,mul_isl_int_entry
)(__isl_take PART
*part
,
1047 return FN(PW
,mul_isl_int
)(part
, *v
);
1050 __isl_give UNION
*FN(UNION
,mul_isl_int
)(__isl_take UNION
*u
, isl_int v
)
1052 if (isl_int_is_one(v
))
1055 if (DEFAULT_IS_ZERO
&& u
&& isl_int_is_zero(v
)) {
1057 isl_space
*dim
= FN(UNION
,get_space
)(u
);
1059 zero
= FN(UNION
,ZERO
)(dim
, u
->type
);
1061 zero
= FN(UNION
,ZERO
)(dim
);
1067 u
= FN(UNION
,transform_inplace
)(u
, &FN(UNION
,mul_isl_int_entry
), &v
);
1068 if (isl_int_is_neg(v
))
1069 u
= FN(UNION
,negate_type
)(u
);
1074 /* Multiply "part" by the isl_val "user" and return the result.
1076 static __isl_give PART
*FN(UNION
,scale_val_entry
)(__isl_take PART
*part
,
1081 return FN(PART
,scale_val
)(part
, isl_val_copy(v
));
1084 /* Multiply "u" by "v" and return the result.
1086 __isl_give UNION
*FN(UNION
,scale_val
)(__isl_take UNION
*u
,
1087 __isl_take isl_val
*v
)
1091 if (isl_val_is_one(v
)) {
1096 if (DEFAULT_IS_ZERO
&& u
&& isl_val_is_zero(v
)) {
1098 isl_space
*space
= FN(UNION
,get_space
)(u
);
1100 zero
= FN(UNION
,ZERO
)(space
, u
->type
);
1102 zero
= FN(UNION
,ZERO
)(space
);
1109 if (!isl_val_is_rat(v
))
1110 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1111 "expecting rational factor", goto error
);
1113 u
= FN(UNION
,transform_inplace
)(u
, &FN(UNION
,scale_val_entry
), v
);
1114 if (isl_val_is_neg(v
))
1115 u
= FN(UNION
,negate_type
)(u
);
1125 /* Divide "part" by the isl_val "user" and return the result.
1127 static __isl_give PART
*FN(UNION
,scale_down_val_entry
)(__isl_take PART
*part
,
1132 return FN(PART
,scale_down_val
)(part
, isl_val_copy(v
));
1135 /* Divide "u" by "v" and return the result.
1137 __isl_give UNION
*FN(UNION
,scale_down_val
)(__isl_take UNION
*u
,
1138 __isl_take isl_val
*v
)
1142 if (isl_val_is_one(v
)) {
1147 if (!isl_val_is_rat(v
))
1148 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1149 "expecting rational factor", goto error
);
1150 if (isl_val_is_zero(v
))
1151 isl_die(isl_val_get_ctx(v
), isl_error_invalid
,
1152 "cannot scale down by zero", goto error
);
1154 u
= FN(UNION
,transform_inplace
)(u
, &FN(UNION
,scale_down_val_entry
), v
);
1155 if (isl_val_is_neg(v
))
1156 u
= FN(UNION
,negate_type
)(u
);
1166 S(UNION
,plain_is_equal_data
)
1172 static isl_stat
FN(UNION
,plain_is_equal_entry
)(void **entry
, void *user
)
1174 S(UNION
,plain_is_equal_data
) *data
= user
;
1175 struct isl_hash_table_entry
*entry2
;
1178 entry2
= FN(UNION
,find_part_entry
)(data
->u2
, pw
->dim
, 0);
1179 if (!entry2
|| entry2
== isl_hash_table_entry_none
) {
1181 data
->is_equal
= isl_bool_error
;
1183 data
->is_equal
= isl_bool_false
;
1184 return isl_stat_error
;
1187 data
->is_equal
= FN(PW
,plain_is_equal
)(pw
, entry2
->data
);
1188 if (data
->is_equal
< 0 || !data
->is_equal
)
1189 return isl_stat_error
;
1194 isl_bool
FN(UNION
,plain_is_equal
)(__isl_keep UNION
*u1
, __isl_keep UNION
*u2
)
1196 S(UNION
,plain_is_equal_data
) data
= { NULL
, isl_bool_true
};
1200 return isl_bool_error
;
1202 return isl_bool_true
;
1203 if (u1
->table
.n
!= u2
->table
.n
)
1204 return isl_bool_false
;
1205 n1
= FN(FN(UNION
,n
),PARTS
)(u1
);
1206 n2
= FN(FN(UNION
,n
),PARTS
)(u2
);
1207 if (n1
< 0 || n2
< 0)
1208 return isl_bool_error
;
1210 return isl_bool_false
;
1212 u1
= FN(UNION
,copy
)(u1
);
1213 u2
= FN(UNION
,copy
)(u2
);
1214 u1
= FN(UNION
,align_params
)(u1
, FN(UNION
,get_space
)(u2
));
1215 u2
= FN(UNION
,align_params
)(u2
, FN(UNION
,get_space
)(u1
));
1220 if (FN(UNION
,foreach_inplace
)(u1
,
1221 &FN(UNION
,plain_is_equal_entry
), &data
) < 0 &&
1228 return data
.is_equal
;
1232 return isl_bool_error
;
1235 /* Internal data structure for isl_union_*_drop_dims.
1236 * type, first and n are passed to isl_*_drop_dims.
1238 S(UNION
,drop_dims_data
) {
1239 enum isl_dim_type type
;
1244 /* Drop the parameters specified by "data" from "part" and return the result.
1246 static __isl_give PART
*FN(UNION
,drop_dims_entry
)(__isl_take PART
*part
,
1249 S(UNION
,drop_dims_data
) *data
= user
;
1251 return FN(PART
,drop_dims
)(part
, data
->type
, data
->first
, data
->n
);
1254 /* Drop the specified parameters from "u".
1255 * That is, type is required to be isl_dim_param.
1257 __isl_give UNION
*FN(UNION
,drop_dims
)( __isl_take UNION
*u
,
1258 enum isl_dim_type type
, unsigned first
, unsigned n
)
1261 S(UNION
,drop_dims_data
) data
= { type
, first
, n
};
1266 if (type
!= isl_dim_param
)
1267 isl_die(FN(UNION
,get_ctx
)(u
), isl_error_invalid
,
1268 "can only project out parameters",
1269 return FN(UNION
,free
)(u
));
1271 space
= FN(UNION
,get_space
)(u
);
1272 space
= isl_space_drop_dims(space
, type
, first
, n
);
1273 return FN(UNION
,transform_space
)(u
, space
, &FN(UNION
,drop_dims_entry
),
1277 /* Internal data structure for isl_union_*_set_dim_name.
1278 * pos is the position of the parameter that needs to be renamed.
1279 * s is the new name.
1281 S(UNION
,set_dim_name_data
) {
1286 /* Change the name of the parameter at position data->pos of "part" to data->s
1287 * and return the result.
1289 static __isl_give PART
*FN(UNION
,set_dim_name_entry
)(__isl_take PART
*part
,
1292 S(UNION
,set_dim_name_data
) *data
= user
;
1294 return FN(PART
,set_dim_name
)(part
, isl_dim_param
, data
->pos
, data
->s
);
1297 /* Change the name of the parameter at position "pos" to "s".
1298 * That is, type is required to be isl_dim_param.
1300 __isl_give UNION
*FN(UNION
,set_dim_name
)(__isl_take UNION
*u
,
1301 enum isl_dim_type type
, unsigned pos
, const char *s
)
1303 S(UNION
,set_dim_name_data
) data
= { pos
, s
};
1309 if (type
!= isl_dim_param
)
1310 isl_die(FN(UNION
,get_ctx
)(u
), isl_error_invalid
,
1311 "can only set parameter names",
1312 return FN(UNION
,free
)(u
));
1314 space
= FN(UNION
,get_space
)(u
);
1315 space
= isl_space_set_dim_name(space
, type
, pos
, s
);
1316 return FN(UNION
,transform_space
)(u
, space
,
1317 &FN(UNION
,set_dim_name_entry
), &data
);
1320 /* Reset the user pointer on all identifiers of parameters and tuples
1321 * of the space of "part" and return the result.
1323 static __isl_give PART
*FN(UNION
,reset_user_entry
)(__isl_take PART
*part
,
1326 return FN(PART
,reset_user
)(part
);
1329 /* Reset the user pointer on all identifiers of parameters and tuples
1330 * of the spaces of "u".
1332 __isl_give UNION
*FN(UNION
,reset_user
)(__isl_take UNION
*u
)
1336 space
= FN(UNION
,get_space
)(u
);
1337 space
= isl_space_reset_user(space
);
1338 return FN(UNION
,transform_space
)(u
, space
, &FN(UNION
,reset_user_entry
),