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_dim
*FN(UNION
,get_dim
)(__isl_keep UNION
*u
)
37 return isl_dim_copy(u
->dim
);
41 static __isl_give UNION
*FN(UNION
,alloc
)(__isl_take isl_dim
*dim
,
42 enum isl_fold type
, int size
)
44 static __isl_give UNION
*FN(UNION
,alloc
)(__isl_take isl_dim
*dim
, int size
)
52 u
= isl_calloc_type(dim
->ctx
, UNION
);
61 if (isl_hash_table_init(dim
->ctx
, &u
->table
, size
) < 0)
72 __isl_give UNION
*FN(UNION
,zero
)(__isl_take isl_dim
*dim
, enum isl_fold type
)
74 return FN(UNION
,alloc
)(dim
, type
, 16);
77 __isl_give UNION
*FN(UNION
,zero
)(__isl_take isl_dim
*dim
)
79 return FN(UNION
,alloc
)(dim
, 16);
83 __isl_give UNION
*FN(UNION
,copy
)(__isl_keep UNION
*u
)
94 int (*fn
)(__isl_take PART
*part
, void *user
);
98 static int call_on_copy(void **entry
, void *user
)
101 S(UNION
,foreach_data
) *data
= (S(UNION
,foreach_data
) *)user
;
103 return data
->fn(FN(PART
,copy
)(part
), data
->user
);
106 int FN(FN(UNION
,foreach
),PARTS
)(__isl_keep UNION
*u
,
107 int (*fn
)(__isl_take PART
*part
, void *user
), void *user
)
109 S(UNION
,foreach_data
) data
= { fn
, user
};
114 return isl_hash_table_foreach(u
->dim
->ctx
, &u
->table
,
115 &call_on_copy
, &data
);
118 static int has_dim(const void *entry
, const void *val
)
120 PART
*part
= (PART
*)entry
;
121 isl_dim
*dim
= (isl_dim
*)val
;
123 return isl_dim_equal(part
->dim
, dim
);
126 __isl_give PART
*FN(FN(UNION
,extract
),PARTS
)(__isl_keep UNION
*u
,
127 __isl_take isl_dim
*dim
)
130 struct isl_hash_table_entry
*entry
;
135 hash
= isl_dim_get_hash(dim
);
136 entry
= isl_hash_table_find(u
->dim
->ctx
, &u
->table
, hash
,
140 return FN(PART
,zero
)(dim
, u
->type
);
142 return FN(PART
,zero
)(dim
);
145 return FN(PART
,copy
)(entry
->data
);
151 __isl_give UNION
*FN(FN(UNION
,add
),PARTS
)(__isl_take UNION
*u
,
152 __isl_take PART
*part
)
155 struct isl_hash_table_entry
*entry
;
160 if (FN(PART
,is_zero
)(part
)) {
165 u
= FN(UNION
,cow
)(u
);
170 isl_assert(u
->dim
->ctx
, isl_dim_match(part
->dim
, isl_dim_param
, u
->dim
,
171 isl_dim_param
), goto error
);
173 hash
= isl_dim_get_hash(part
->dim
);
174 entry
= isl_hash_table_find(u
->dim
->ctx
, &u
->table
, hash
,
175 &has_dim
, part
->dim
, 1);
182 entry
->data
= FN(PART
,add
)(entry
->data
, FN(PART
,copy
)(part
));
186 if (FN(PART
,is_zero
)(entry
->data
)) {
187 FN(PART
,free
)(entry
->data
);
188 isl_hash_table_remove(u
->dim
->ctx
, &u
->table
, entry
);
199 static int add_part(__isl_take PART
*part
, void *user
)
201 UNION
**u
= (UNION
**)user
;
203 *u
= FN(FN(UNION
,add
),PARTS
)(*u
, part
);
208 __isl_give UNION
*FN(UNION
,dup
)(__isl_keep UNION
*u
)
216 dup
= FN(UNION
,zero
)(isl_dim_copy(u
->dim
), u
->type
);
218 dup
= FN(UNION
,zero
)(isl_dim_copy(u
->dim
));
220 if (FN(FN(UNION
,foreach
),PARTS
)(u
, &add_part
, &dup
) < 0)
228 __isl_give UNION
*FN(UNION
,cow
)(__isl_take UNION
*u
)
236 return FN(UNION
,dup
)(u
);
239 static int free_u_entry(void **entry
, void *user
)
246 void FN(UNION
,free
)(__isl_take UNION
*u
)
254 isl_hash_table_foreach(u
->dim
->ctx
, &u
->table
, &free_u_entry
, NULL
);
255 isl_hash_table_clear(&u
->table
);
256 isl_dim_free(u
->dim
);
265 static int align_entry(__isl_take PART
*part
, void *user
)
268 S(UNION
,align
) *data
= user
;
270 exp
= isl_reordering_extend_dim(isl_reordering_copy(data
->exp
),
271 FN(PART
,get_dim
)(part
));
273 data
->res
= FN(FN(UNION
,add
),PARTS
)(data
->res
,
274 FN(PART
,realign
)(part
, exp
));
279 __isl_give UNION
*FN(UNION
,align_params
)(__isl_take UNION
*u
,
280 __isl_take isl_dim
*model
)
282 S(UNION
,align
) data
= { NULL
, NULL
};
287 if (isl_dim_match(u
->dim
, isl_dim_param
, model
, isl_dim_param
)) {
292 data
.exp
= isl_parameter_alignment_reordering(u
->dim
, model
);
297 data
.res
= FN(UNION
,alloc
)(isl_dim_copy(data
.exp
->dim
),
298 u
->type
, u
->table
.n
);
300 data
.res
= FN(UNION
,alloc
)(isl_dim_copy(data
.exp
->dim
), u
->table
.n
);
302 if (FN(FN(UNION
,foreach
),PARTS
)(u
, &align_entry
, &data
) < 0)
305 isl_reordering_free(data
.exp
);
310 isl_reordering_free(data
.exp
);
312 FN(UNION
,free
)(data
.res
);
317 __isl_give UNION
*FN(UNION
,add
)(__isl_take UNION
*u1
, __isl_take UNION
*u2
)
319 u1
= FN(UNION
,align_params
)(u1
, FN(UNION
,get_dim
)(u2
));
320 u2
= FN(UNION
,align_params
)(u2
, FN(UNION
,get_dim
)(u1
));
322 u1
= FN(UNION
,cow
)(u1
);
327 if (FN(FN(UNION
,foreach
),PARTS
)(u2
, &add_part
, &u1
) < 0)
339 __isl_give UNION
*FN(FN(UNION
,from
),PARTS
)(__isl_take PART
*part
)
347 dim
= FN(PART
,get_dim
)(part
);
348 dim
= isl_dim_drop(dim
, isl_dim_in
, 0, isl_dim_size(dim
, isl_dim_in
));
349 dim
= isl_dim_drop(dim
, isl_dim_out
, 0, isl_dim_size(dim
, isl_dim_out
));
351 u
= FN(UNION
,zero
)(dim
, part
->type
);
353 u
= FN(UNION
,zero
)(dim
);
355 u
= FN(FN(UNION
,add
),PARTS
)(u
, part
);
360 S(UNION
,match_bin_data
) {
365 /* This function is currently only used from isl_polynomial.c
366 * and not from isl_fold.c.
368 static __isl_give UNION
*match_bin_op(__isl_take UNION
*u1
,
369 __isl_take UNION
*u2
,
370 int (*fn
)(void **, void *)) __attribute__ ((unused
));
371 static __isl_give UNION
*match_bin_op(__isl_take UNION
*u1
,
372 __isl_take UNION
*u2
, int (*fn
)(void **, void *))
374 S(UNION
,match_bin_data
) data
= { NULL
, NULL
};
376 u1
= FN(UNION
,align_params
)(u1
, FN(UNION
,get_dim
)(u2
));
377 u2
= FN(UNION
,align_params
)(u2
, FN(UNION
,get_dim
)(u1
));
384 data
.res
= FN(UNION
,alloc
)(isl_dim_copy(u1
->dim
), u1
->type
, u1
->table
.n
);
386 data
.res
= FN(UNION
,alloc
)(isl_dim_copy(u1
->dim
), u1
->table
.n
);
388 if (isl_hash_table_foreach(u1
->dim
->ctx
, &u1
->table
, fn
, &data
) < 0)
397 FN(UNION
,free
)(data
.res
);
401 S(UNION
,match_set_data
) {
404 __isl_give PW
*(*fn
)(__isl_take PW
*, __isl_take isl_set
*);
407 static int set_has_dim(const void *entry
, const void *val
)
409 isl_set
*set
= (isl_set
*)entry
;
410 isl_dim
*dim
= (isl_dim
*)val
;
412 return isl_dim_equal(set
->dim
, dim
);
415 static int match_set_entry(void **entry
, void *user
)
417 S(UNION
,match_set_data
) *data
= user
;
419 struct isl_hash_table_entry
*entry2
;
423 hash
= isl_dim_get_hash(pw
->dim
);
424 entry2
= isl_hash_table_find(data
->uset
->dim
->ctx
, &data
->uset
->table
,
425 hash
, &set_has_dim
, pw
->dim
, 0);
429 pw
= FN(PW
,copy
)(pw
);
430 pw
= data
->fn(pw
, isl_set_copy(entry2
->data
));
432 empty
= FN(PW
,is_zero
)(pw
);
442 data
->res
= FN(FN(UNION
,add
),PARTS
)(data
->res
, pw
);
447 static __isl_give UNION
*match_set_op(__isl_take UNION
*u
,
448 __isl_take isl_union_set
*uset
,
449 __isl_give PW
*(*fn
)(__isl_take PW
*, __isl_take isl_set
*))
451 S(UNION
,match_set_data
) data
= { NULL
, NULL
, fn
};
453 u
= FN(UNION
,align_params
)(u
, isl_union_set_get_dim(uset
));
454 uset
= isl_union_set_align_params(uset
, FN(UNION
,get_dim
)(u
));
461 data
.res
= FN(UNION
,alloc
)(isl_dim_copy(u
->dim
), u
->type
, u
->table
.n
);
463 data
.res
= FN(UNION
,alloc
)(isl_dim_copy(u
->dim
), u
->table
.n
);
465 if (isl_hash_table_foreach(u
->dim
->ctx
, &u
->table
,
466 &match_set_entry
, &data
) < 0)
470 isl_union_set_free(uset
);
474 isl_union_set_free(uset
);
475 FN(UNION
,free
)(data
.res
);
479 __isl_give UNION
*FN(UNION
,intersect_domain
)(__isl_take UNION
*u
,
480 __isl_take isl_union_set
*uset
)
482 return match_set_op(u
, uset
, &FN(PW
,intersect_domain
));
485 __isl_give UNION
*FN(UNION
,gist
)(__isl_take UNION
*u
,
486 __isl_take isl_union_set
*uset
)
488 return match_set_op(u
, uset
, &FN(PW
,gist
));
491 __isl_give isl_qpolynomial
*FN(UNION
,eval
)(__isl_take UNION
*u
,
492 __isl_take isl_point
*pnt
)
495 struct isl_hash_table_entry
*entry
;
501 hash
= isl_dim_get_hash(pnt
->dim
);
502 entry
= isl_hash_table_find(u
->dim
->ctx
, &u
->table
,
503 hash
, &has_dim
, pnt
->dim
, 0);
505 qp
= isl_qpolynomial_zero(isl_dim_copy(pnt
->dim
));
508 qp
= FN(PART
,eval
)(FN(PART
,copy
)(entry
->data
), pnt
);
518 static int coalesce_entry(void **entry
, void *user
)
520 PW
**pw
= (PW
**)entry
;
522 *pw
= FN(PW
,coalesce
)(*pw
);
529 __isl_give UNION
*FN(UNION
,coalesce
)(__isl_take UNION
*u
)
534 if (isl_hash_table_foreach(u
->dim
->ctx
, &u
->table
,
535 &coalesce_entry
, NULL
) < 0)
544 static int domain(__isl_take PART
*part
, void *user
)
546 isl_union_set
**uset
= (isl_union_set
**)user
;
548 *uset
= isl_union_set_add_set(*uset
, FN(PART
,domain
)(part
));
553 __isl_give isl_union_set
*FN(UNION
,domain
)(__isl_take UNION
*u
)
557 uset
= isl_union_set_empty(FN(UNION
,get_dim
)(u
));
558 if (FN(FN(UNION
,foreach
),PARTS
)(u
, &domain
, &uset
) < 0)
565 isl_union_set_free(uset
);
570 static int mul_isl_int(void **entry
, void *user
)
572 PW
**pw
= (PW
**)entry
;
575 *pw
= FN(PW
,mul_isl_int
)(*pw
, *v
);
582 __isl_give UNION
*FN(UNION
,mul_isl_int
)(__isl_take UNION
*u
, isl_int v
)
584 if (isl_int_is_one(v
))
587 if (u
&& isl_int_is_zero(v
)) {
589 isl_dim
*dim
= FN(UNION
,get_dim
)(u
);
591 zero
= FN(UNION
,zero
)(dim
, u
->type
);
593 zero
= FN(UNION
,zero
)(dim
);
599 u
= FN(UNION
,cow
)(u
);
604 if (isl_int_is_neg(v
))
605 u
->type
= isl_fold_type_negate(u
->type
);
607 if (isl_hash_table_foreach(u
->dim
->ctx
, &u
->table
, &mul_isl_int
, v
) < 0)