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;