2 * Copyright 2010 INRIA Saclay
4 * Use of this software is governed by the GNU LGPLv2.1 license
6 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
7 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
11 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
12 #define FN(TYPE,NAME) xFN(TYPE,NAME)
13 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
14 #define S(TYPE,NAME) xS(TYPE,NAME)
23 struct isl_hash_table table
;
26 __isl_give UNION
*FN(UNION
,cow
)(__isl_take UNION
*u
);
28 isl_ctx
*FN(UNION
,get_ctx
)(__isl_keep UNION
*u
)
30 return u
? u
->dim
->ctx
: NULL
;
33 __isl_give isl_space
*FN(UNION
,get_space
)(__isl_keep UNION
*u
)
37 return isl_space_copy(u
->dim
);
41 static __isl_give UNION
*FN(UNION
,alloc
)(__isl_take isl_space
*dim
,
42 enum isl_fold type
, int size
)
44 static __isl_give UNION
*FN(UNION
,alloc
)(__isl_take isl_space
*dim
, int size
)
49 dim
= isl_space_params(dim
);
53 u
= isl_calloc_type(dim
->ctx
, UNION
);
62 if (isl_hash_table_init(dim
->ctx
, &u
->table
, size
) < 0)
73 __isl_give UNION
*FN(UNION
,ZERO
)(__isl_take isl_space
*dim
, enum isl_fold type
)
75 return FN(UNION
,alloc
)(dim
, type
, 16);
78 __isl_give UNION
*FN(UNION
,ZERO
)(__isl_take isl_space
*dim
)
80 return FN(UNION
,alloc
)(dim
, 16);
84 __isl_give UNION
*FN(UNION
,copy
)(__isl_keep UNION
*u
)
95 int (*fn
)(__isl_take PART
*part
, void *user
);
99 static int call_on_copy(void **entry
, void *user
)
102 S(UNION
,foreach_data
) *data
= (S(UNION
,foreach_data
) *)user
;
104 return data
->fn(FN(PART
,copy
)(part
), data
->user
);
107 int FN(FN(UNION
,foreach
),PARTS
)(__isl_keep UNION
*u
,
108 int (*fn
)(__isl_take PART
*part
, void *user
), void *user
)
110 S(UNION
,foreach_data
) data
= { fn
, user
};
115 return isl_hash_table_foreach(u
->dim
->ctx
, &u
->table
,
116 &call_on_copy
, &data
);
119 static int has_dim(const void *entry
, const void *val
)
121 PART
*part
= (PART
*)entry
;
122 isl_space
*dim
= (isl_space
*)val
;
124 return isl_space_is_equal(part
->dim
, dim
);
127 __isl_give PART
*FN(FN(UNION
,extract
),PARTS
)(__isl_keep UNION
*u
,
128 __isl_take isl_space
*dim
)
131 struct isl_hash_table_entry
*entry
;
136 hash
= isl_space_get_hash(dim
);
137 entry
= isl_hash_table_find(u
->dim
->ctx
, &u
->table
, hash
,
141 return FN(PART
,ZERO
)(dim
, u
->type
);
143 return FN(PART
,ZERO
)(dim
);
146 return FN(PART
,copy
)(entry
->data
);
152 __isl_give UNION
*FN(FN(UNION
,add
),PARTS
)(__isl_take UNION
*u
,
153 __isl_take PART
*part
)
156 struct isl_hash_table_entry
*entry
;
161 if (DEFAULT_IS_ZERO
&& FN(PART
,IS_ZERO
)(part
)) {
166 u
= FN(UNION
,cow
)(u
);
171 isl_assert(u
->dim
->ctx
, isl_space_match(part
->dim
, isl_dim_param
, u
->dim
,
172 isl_dim_param
), goto error
);
174 hash
= isl_space_get_hash(part
->dim
);
175 entry
= isl_hash_table_find(u
->dim
->ctx
, &u
->table
, hash
,
176 &has_dim
, part
->dim
, 1);
183 entry
->data
= FN(PART
,add
)(entry
->data
, FN(PART
,copy
)(part
));
187 if (DEFAULT_IS_ZERO
&& FN(PART
,IS_ZERO
)(entry
->data
)) {
188 FN(PART
,free
)(entry
->data
);
189 isl_hash_table_remove(u
->dim
->ctx
, &u
->table
, entry
);
200 static int add_part(__isl_take PART
*part
, void *user
)
202 UNION
**u
= (UNION
**)user
;
204 *u
= FN(FN(UNION
,add
),PARTS
)(*u
, part
);
209 __isl_give UNION
*FN(UNION
,dup
)(__isl_keep UNION
*u
)
217 dup
= FN(UNION
,ZERO
)(isl_space_copy(u
->dim
), u
->type
);
219 dup
= FN(UNION
,ZERO
)(isl_space_copy(u
->dim
));
221 if (FN(FN(UNION
,foreach
),PARTS
)(u
, &add_part
, &dup
) < 0)
229 __isl_give UNION
*FN(UNION
,cow
)(__isl_take UNION
*u
)
237 return FN(UNION
,dup
)(u
);
240 static int free_u_entry(void **entry
, void *user
)
247 void *FN(UNION
,free
)(__isl_take UNION
*u
)
255 isl_hash_table_foreach(u
->dim
->ctx
, &u
->table
, &free_u_entry
, NULL
);
256 isl_hash_table_clear(&u
->table
);
257 isl_space_free(u
->dim
);
268 static int align_entry(__isl_take PART
*part
, void *user
)
271 S(UNION
,align
) *data
= user
;
273 exp
= isl_reordering_extend_space(isl_reordering_copy(data
->exp
),
274 FN(PART
,get_domain_space
)(part
));
276 data
->res
= FN(FN(UNION
,add
),PARTS
)(data
->res
,
277 FN(PART
,realign_domain
)(part
, exp
));
282 static int align_entry(__isl_take PART
*part
, void *user
)
285 S(UNION
,align
) *data
= user
;
287 exp
= isl_reordering_extend_space(isl_reordering_copy(data
->exp
),
288 FN(PART
,get_space
)(part
));
290 data
->res
= FN(FN(UNION
,add
),PARTS
)(data
->res
,
291 FN(PART
,realign
)(part
, exp
));
297 __isl_give UNION
*FN(UNION
,align_params
)(__isl_take UNION
*u
,
298 __isl_take isl_space
*model
)
300 S(UNION
,align
) data
= { NULL
, NULL
};
305 if (isl_space_match(u
->dim
, isl_dim_param
, model
, isl_dim_param
)) {
306 isl_space_free(model
);
310 data
.exp
= isl_parameter_alignment_reordering(u
->dim
, model
);
315 data
.res
= FN(UNION
,alloc
)(isl_space_copy(data
.exp
->dim
),
316 u
->type
, u
->table
.n
);
318 data
.res
= FN(UNION
,alloc
)(isl_space_copy(data
.exp
->dim
), u
->table
.n
);
320 if (FN(FN(UNION
,foreach
),PARTS
)(u
, &align_entry
, &data
) < 0)
323 isl_reordering_free(data
.exp
);
325 isl_space_free(model
);
328 isl_reordering_free(data
.exp
);
330 FN(UNION
,free
)(data
.res
);
331 isl_space_free(model
);
335 __isl_give UNION
*FN(UNION
,add
)(__isl_take UNION
*u1
, __isl_take UNION
*u2
)
337 u1
= FN(UNION
,align_params
)(u1
, FN(UNION
,get_space
)(u2
));
338 u2
= FN(UNION
,align_params
)(u2
, FN(UNION
,get_space
)(u1
));
340 u1
= FN(UNION
,cow
)(u1
);
345 if (FN(FN(UNION
,foreach
),PARTS
)(u2
, &add_part
, &u1
) < 0)
357 __isl_give UNION
*FN(FN(UNION
,from
),PARTS
)(__isl_take PART
*part
)
365 dim
= FN(PART
,get_space
)(part
);
366 dim
= isl_space_drop_dims(dim
, isl_dim_in
, 0, isl_space_dim(dim
, isl_dim_in
));
367 dim
= isl_space_drop_dims(dim
, isl_dim_out
, 0, isl_space_dim(dim
, isl_dim_out
));
369 u
= FN(UNION
,ZERO
)(dim
, part
->type
);
371 u
= FN(UNION
,ZERO
)(dim
);
373 u
= FN(FN(UNION
,add
),PARTS
)(u
, part
);
378 S(UNION
,match_bin_data
) {
383 /* This function is currently only used from isl_polynomial.c
384 * and not from isl_fold.c.
386 static __isl_give UNION
*match_bin_op(__isl_take UNION
*u1
,
387 __isl_take UNION
*u2
,
388 int (*fn
)(void **, void *)) __attribute__ ((unused
));
389 static __isl_give UNION
*match_bin_op(__isl_take UNION
*u1
,
390 __isl_take UNION
*u2
, int (*fn
)(void **, void *))
392 S(UNION
,match_bin_data
) data
= { NULL
, NULL
};
394 u1
= FN(UNION
,align_params
)(u1
, FN(UNION
,get_space
)(u2
));
395 u2
= FN(UNION
,align_params
)(u2
, FN(UNION
,get_space
)(u1
));
402 data
.res
= FN(UNION
,alloc
)(isl_space_copy(u1
->dim
), u1
->type
, u1
->table
.n
);
404 data
.res
= FN(UNION
,alloc
)(isl_space_copy(u1
->dim
), u1
->table
.n
);
406 if (isl_hash_table_foreach(u1
->dim
->ctx
, &u1
->table
, fn
, &data
) < 0)
415 FN(UNION
,free
)(data
.res
);
419 S(UNION
,any_set_data
) {
422 __isl_give PW
*(*fn
)(__isl_take PW
*, __isl_take isl_set
*);
425 static int any_set_entry(void **entry
, void *user
)
427 S(UNION
,any_set_data
) *data
= user
;
430 pw
= FN(PW
,copy
)(pw
);
431 pw
= data
->fn(pw
, isl_set_copy(data
->set
));
433 if (DEFAULT_IS_ZERO
) {
436 empty
= FN(PW
,IS_ZERO
)(pw
);
447 data
->res
= FN(FN(UNION
,add
),PARTS
)(data
->res
, pw
);
452 /* Update each element of "u" by calling "fn" on the element and "set".
454 static __isl_give UNION
*any_set_op(__isl_take UNION
*u
,
455 __isl_take isl_set
*set
,
456 __isl_give PW
*(*fn
)(__isl_take PW
*, __isl_take isl_set
*))
458 S(UNION
,any_set_data
) data
= { NULL
, NULL
, fn
};
460 u
= FN(UNION
,align_params
)(u
, isl_set_get_space(set
));
461 set
= isl_set_align_params(set
, FN(UNION
,get_space
)(u
));
468 data
.res
= FN(UNION
,alloc
)(isl_space_copy(u
->dim
), u
->type
, u
->table
.n
);
470 data
.res
= FN(UNION
,alloc
)(isl_space_copy(u
->dim
), u
->table
.n
);
472 if (isl_hash_table_foreach(u
->dim
->ctx
, &u
->table
,
473 &any_set_entry
, &data
) < 0)
482 FN(UNION
,free
)(data
.res
);
486 /* Intersect the domain of "u" with the parameter domain "context".
488 __isl_give UNION
*FN(UNION
,intersect_params
)(__isl_take UNION
*u
,
489 __isl_take isl_set
*set
)
491 return any_set_op(u
, set
, &FN(PW
,intersect_params
));
494 /* Compute the gist of the domain of "u" with respect to
495 * the parameter domain "context".
497 __isl_give UNION
*FN(UNION
,gist_params
)(__isl_take UNION
*u
,
498 __isl_take isl_set
*set
)
500 return any_set_op(u
, set
, &FN(PW
,gist_params
));
503 S(UNION
,match_domain_data
) {
506 __isl_give PW
*(*fn
)(__isl_take PW
*, __isl_take isl_set
*);
509 static int set_has_dim(const void *entry
, const void *val
)
511 isl_set
*set
= (isl_set
*)entry
;
512 isl_space
*dim
= (isl_space
*)val
;
514 return isl_space_is_equal(set
->dim
, dim
);
517 /* Find the set in data->uset that live in the same space as the domain
518 * of *entry, apply data->fn to *entry and this set (if any), and add
519 * the result to data->res.
521 static int match_domain_entry(void **entry
, void *user
)
523 S(UNION
,match_domain_data
) *data
= user
;
525 struct isl_hash_table_entry
*entry2
;
529 space
= FN(PW
,get_domain_space
)(pw
);
530 hash
= isl_space_get_hash(space
);
531 entry2
= isl_hash_table_find(data
->uset
->dim
->ctx
, &data
->uset
->table
,
532 hash
, &set_has_dim
, space
, 0);
533 isl_space_free(space
);
537 pw
= FN(PW
,copy
)(pw
);
538 pw
= data
->fn(pw
, isl_set_copy(entry2
->data
));
540 if (DEFAULT_IS_ZERO
) {
543 empty
= FN(PW
,IS_ZERO
)(pw
);
554 data
->res
= FN(FN(UNION
,add
),PARTS
)(data
->res
, pw
);
559 /* Apply fn to each pair of PW in u and set in uset such that
560 * the set lives in the same space as the domain of PW
561 * and collect the results.
563 static __isl_give UNION
*match_domain_op(__isl_take UNION
*u
,
564 __isl_take isl_union_set
*uset
,
565 __isl_give PW
*(*fn
)(__isl_take PW
*, __isl_take isl_set
*))
567 S(UNION
,match_domain_data
) data
= { NULL
, NULL
, fn
};
569 u
= FN(UNION
,align_params
)(u
, isl_union_set_get_space(uset
));
570 uset
= isl_union_set_align_params(uset
, FN(UNION
,get_space
)(u
));
577 data
.res
= FN(UNION
,alloc
)(isl_space_copy(u
->dim
), u
->type
, u
->table
.n
);
579 data
.res
= FN(UNION
,alloc
)(isl_space_copy(u
->dim
), u
->table
.n
);
581 if (isl_hash_table_foreach(u
->dim
->ctx
, &u
->table
,
582 &match_domain_entry
, &data
) < 0)
586 isl_union_set_free(uset
);
590 isl_union_set_free(uset
);
591 FN(UNION
,free
)(data
.res
);
595 /* Intersect the domain of "u" with "uset".
596 * If "uset" is a parameters domain, then intersect the parameter
597 * domain of "u" with this set.
599 __isl_give UNION
*FN(UNION
,intersect_domain
)(__isl_take UNION
*u
,
600 __isl_take isl_union_set
*uset
)
602 if (isl_union_set_is_params(uset
))
603 return FN(UNION
,intersect_params
)(u
,
604 isl_set_from_union_set(uset
));
605 return match_domain_op(u
, uset
, &FN(PW
,intersect_domain
));
608 __isl_give UNION
*FN(UNION
,gist
)(__isl_take UNION
*u
,
609 __isl_take isl_union_set
*uset
)
611 if (isl_union_set_is_params(uset
))
612 return FN(UNION
,gist_params
)(u
, isl_set_from_union_set(uset
));
613 return match_domain_op(u
, uset
, &FN(PW
,gist
));
617 __isl_give isl_qpolynomial
*FN(UNION
,eval
)(__isl_take UNION
*u
,
618 __isl_take isl_point
*pnt
)
621 struct isl_hash_table_entry
*entry
;
628 space
= isl_space_copy(pnt
->dim
);
629 space
= isl_space_from_domain(space
);
630 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
633 hash
= isl_space_get_hash(space
);
634 entry
= isl_hash_table_find(u
->dim
->ctx
, &u
->table
,
635 hash
, &has_dim
, space
, 0);
636 isl_space_free(space
);
638 qp
= isl_qpolynomial_zero_on_domain(isl_space_copy(pnt
->dim
));
641 qp
= FN(PART
,eval
)(FN(PART
,copy
)(entry
->data
), pnt
);
652 static int coalesce_entry(void **entry
, void *user
)
654 PW
**pw
= (PW
**)entry
;
656 *pw
= FN(PW
,coalesce
)(*pw
);
663 __isl_give UNION
*FN(UNION
,coalesce
)(__isl_take UNION
*u
)
668 if (isl_hash_table_foreach(u
->dim
->ctx
, &u
->table
,
669 &coalesce_entry
, NULL
) < 0)
678 static int domain(__isl_take PART
*part
, void *user
)
680 isl_union_set
**uset
= (isl_union_set
**)user
;
682 *uset
= isl_union_set_add_set(*uset
, FN(PART
,domain
)(part
));
687 __isl_give isl_union_set
*FN(UNION
,domain
)(__isl_take UNION
*u
)
691 uset
= isl_union_set_empty(FN(UNION
,get_space
)(u
));
692 if (FN(FN(UNION
,foreach
),PARTS
)(u
, &domain
, &uset
) < 0)
699 isl_union_set_free(uset
);
704 static int mul_isl_int(void **entry
, void *user
)
706 PW
**pw
= (PW
**)entry
;
709 *pw
= FN(PW
,mul_isl_int
)(*pw
, *v
);
716 __isl_give UNION
*FN(UNION
,mul_isl_int
)(__isl_take UNION
*u
, isl_int v
)
718 if (isl_int_is_one(v
))
721 if (DEFAULT_IS_ZERO
&& u
&& isl_int_is_zero(v
)) {
723 isl_space
*dim
= FN(UNION
,get_space
)(u
);
725 zero
= FN(UNION
,ZERO
)(dim
, u
->type
);
727 zero
= FN(UNION
,ZERO
)(dim
);
733 u
= FN(UNION
,cow
)(u
);
738 if (isl_int_is_neg(v
))
739 u
->type
= isl_fold_type_negate(u
->type
);
741 if (isl_hash_table_foreach(u
->dim
->ctx
, &u
->table
, &mul_isl_int
, v
) < 0)
750 S(UNION
,plain_is_equal_data
)
756 static int plain_is_equal_entry(void **entry
, void *user
)
758 S(UNION
,plain_is_equal_data
) *data
= user
;
760 struct isl_hash_table_entry
*entry2
;
763 hash
= isl_space_get_hash(pw
->dim
);
764 entry2
= isl_hash_table_find(data
->u2
->dim
->ctx
, &data
->u2
->table
,
765 hash
, &has_dim
, pw
->dim
, 0);
771 data
->is_equal
= FN(PW
,plain_is_equal
)(pw
, entry2
->data
);
772 if (data
->is_equal
< 0 || !data
->is_equal
)
778 int FN(UNION
,plain_is_equal
)(__isl_keep UNION
*u1
, __isl_keep UNION
*u2
)
780 S(UNION
,plain_is_equal_data
) data
= { NULL
, 1 };
786 if (u1
->table
.n
!= u2
->table
.n
)
789 u1
= FN(UNION
,copy
)(u1
);
790 u2
= FN(UNION
,copy
)(u2
);
791 u1
= FN(UNION
,align_params
)(u1
, FN(UNION
,get_space
)(u2
));
792 u2
= FN(UNION
,align_params
)(u2
, FN(UNION
,get_space
)(u1
));
797 if (isl_hash_table_foreach(u1
->dim
->ctx
, &u1
->table
,
798 &plain_is_equal_entry
, &data
) < 0 &&
805 return data
.is_equal
;