?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_ast_build_set_loop_bounds: extract out update of pending and generated
[isl.git] / isl_union_templ.c
blob56d068fb1d2d4af05eb0bc74fae4a2dca4ef56ba
1 /*
2 * Copyright 2010 INRIA Saclay
3 * Copyright 2013 Ecole Normale Superieure
4 *
5 * Use of this software is governed by the MIT license
6 *
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
9 * 91893 Orsay, France
10 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
11 */
12
13 #include <isl_hash_private.h>
14
15 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
16 #define FN(TYPE,NAME) xFN(TYPE,NAME)
17 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
18 #define S(TYPE,NAME) xS(TYPE,NAME)
19
20 /* A union of expressions defined over different domain spaces.
21 * "space" describes the parameters.
22 * The entries of "table" are keyed on the domain space of the entry.
23 */
24 struct UNION {
25 int ref;
26 #ifdef HAS_TYPE
27 enum isl_fold type;
28 #endif
29 isl_space *space;
30
31 struct isl_hash_table table;
32 };
33
34 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u);
35
36 isl_ctx *FN(UNION,get_ctx)(__isl_keep UNION *u)
37 {
38 return u ? u->space->ctx : NULL;
39 }
40
41 __isl_give isl_space *FN(UNION,get_space)(__isl_keep UNION *u)
42 {
43 if (!u)
44 return NULL;
45 return isl_space_copy(u->space);
46 }
47
48 /* Return the number of parameters of "u", where "type"
49 * is required to be set to isl_dim_param.
50 */
51 unsigned FN(UNION,dim)(__isl_keep UNION *u, enum isl_dim_type type)
52 {
53 if (!u)
54 return 0;
55
56 if (type != isl_dim_param)
57 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
58 "can only reference parameters", return 0);
59
60 return isl_space_dim(u->space, type);
61 }
62
63 /* Return the position of the parameter with the given name
64 * in "u".
65 * Return -1 if no such dimension can be found.
66 */
67 int FN(UNION,find_dim_by_name)(__isl_keep UNION *u, enum isl_dim_type type,
68 const char *name)
69 {
70 if (!u)
71 return -1;
72 return isl_space_find_dim_by_name(u->space, type, name);
73 }
74
75 #ifdef HAS_TYPE
76 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *dim,
77 enum isl_fold type, int size)
78 #else
79 static __isl_give UNION *FN(UNION,alloc)(__isl_take isl_space *dim, int size)
80 #endif
81 {
82 UNION *u;
83
84 dim = isl_space_params(dim);
85 if (!dim)
86 return NULL;
87
88 u = isl_calloc_type(dim->ctx, UNION);
89 if (!u)
90 goto error;
91
92 u->ref = 1;
93 #ifdef HAS_TYPE
94 u->type = type;
95 #endif
96 u->space = dim;
97 if (isl_hash_table_init(dim->ctx, &u->table, size) < 0)
98 return FN(UNION,free)(u);
99
100 return u;
101 error:
102 isl_space_free(dim);
103 return NULL;
104 }
105
106 #ifdef HAS_TYPE
107 __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *dim, enum isl_fold type)
108 {
109 return FN(UNION,alloc)(dim, type, 16);
110 }
111 #else
112 __isl_give UNION *FN(UNION,ZERO)(__isl_take isl_space *dim)
113 {
114 return FN(UNION,alloc)(dim, 16);
115 }
116 #endif
117
118 __isl_give UNION *FN(UNION,copy)(__isl_keep UNION *u)
119 {
120 if (!u)
121 return NULL;
122
123 u->ref++;
124 return u;
125 }
126
127 /* Return the number of base expressions in "u".
128 */
129 int FN(FN(UNION,n),PARTS)(__isl_keep UNION *u)
130 {
131 return u ? u->table.n : 0;
132 }
133
134 S(UNION,foreach_data)
135 {
136 isl_stat (*fn)(__isl_take PART *part, void *user);
137 void *user;
138 };
139
140 static isl_stat FN(UNION,call_on_copy)(void **entry, void *user)
141 {
142 PART *part = *entry;
143 S(UNION,foreach_data) *data = (S(UNION,foreach_data) *)user;
144
145 return data->fn(FN(PART,copy)(part), data->user);
146 }
147
148 isl_stat FN(FN(UNION,foreach),PARTS)(__isl_keep UNION *u,
149 isl_stat (*fn)(__isl_take PART *part, void *user), void *user)
150 {
151 S(UNION,foreach_data) data = { fn, user };
152
153 if (!u)
154 return isl_stat_error;
155
156 return isl_hash_table_foreach(u->space->ctx, &u->table,
157 &FN(UNION,call_on_copy), &data);
158 }
159
160 /* This function is not currently used by isl_aff.c.
161 */
162 static int FN(UNION,has_domain_space)(const void *entry, const void *val)
163 __attribute__ ((unused));
164
165 /* Is the domain space of "entry" equal to "space"?
166 */
167 static int FN(UNION,has_domain_space)(const void *entry, const void *val)
168 {
169 PART *part = (PART *)entry;
170 isl_space *space = (isl_space *) val;
171
172 if (isl_space_is_params(space))
173 return isl_space_is_set(part->dim);
174
175 return isl_space_tuple_is_equal(part->dim, isl_dim_in,
176 space, isl_dim_set);
177 }
178
179 /* Is the domain space of "entry" equal to the domain of "space"?
180 */
181 static int FN(UNION,has_same_domain_space)(const void *entry, const void *val)
182 {
183 PART *part = (PART *)entry;
184 isl_space *space = (isl_space *) val;
185
186 if (isl_space_is_set(space))
187 return isl_space_is_set(part->dim);
188
189 return isl_space_tuple_is_equal(part->dim, isl_dim_in,
190 space, isl_dim_in);
191 }
192
193 /* Return the entry, if any, in "u" that lives in "space".
194 * If "reserve" is set, then an entry is created if it does not exist yet.
195 * Return NULL on error and isl_hash_table_entry_none if no entry was found.
196 * Note that when "reserve" is set, the function will never return
197 * isl_hash_table_entry_none.
198 *
199 * First look for the entry (if any) with the same domain space.
200 * If it exists, then check if the range space also matches.
201 */
202 static struct isl_hash_table_entry *FN(UNION,find_part_entry)(
203 __isl_keep UNION *u, __isl_keep isl_space *space, int reserve)
204 {
205 isl_ctx *ctx;
206 uint32_t hash;
207 struct isl_hash_table_entry *entry;
208 isl_bool equal;
209 isl_space *domain;
210 PART *part;
211
212 if (!u)
213 return NULL;
214
215 ctx = FN(UNION,get_ctx)(u);
216 domain = isl_space_domain(isl_space_copy(space));
217 if (!domain)
218 return NULL;
219 hash = isl_space_get_hash(domain);
220 isl_space_free(domain);
221 entry = isl_hash_table_find(ctx, &u->table, hash,
222 &FN(UNION,has_same_domain_space), space, reserve);
223 if (!entry)
224 return reserve ? NULL : isl_hash_table_entry_none;
225 if (reserve && !entry->data)
226 return entry;
227 part = entry->data;
228 equal = isl_space_tuple_is_equal(part->dim, isl_dim_out,
229 space, isl_dim_out);
230 if (equal < 0)
231 return NULL;
232 if (equal)
233 return entry;
234 if (!reserve)
235 return isl_hash_table_entry_none;
236 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
237 "union expression can only contain a single "
238 "expression over a given domain", return NULL);
239 }
240
241 /* Extract the element of "u" living in "space" (ignoring parameters).
242 *
243 * Return the ZERO element if "u" does not contain any element
244 * living in "space".
245 */
246 __isl_give PART *FN(FN(UNION,extract),PARTS)(__isl_keep UNION *u,
247 __isl_take isl_space *space)
248 {
249 struct isl_hash_table_entry *entry;
250
251 if (!u || !space)
252 goto error;
253 if (!isl_space_match(u->space, isl_dim_param, space, isl_dim_param)) {
254 space = isl_space_drop_dims(space, isl_dim_param,
255 0, isl_space_dim(space, isl_dim_param));
256 space = isl_space_align_params(space,
257 FN(UNION,get_space)(u));
258 if (!space)
259 goto error;
260 }
261
262 entry = FN(UNION,find_part_entry)(u, space, 0);
263 if (!entry)
264 goto error;
265 if (entry == isl_hash_table_entry_none)
266 #ifdef HAS_TYPE
267 return FN(PART,ZERO)(space, u->type);
268 #else
269 return FN(PART,ZERO)(space);
270 #endif
271 isl_space_free(space);
272 return FN(PART,copy)(entry->data);
273 error:
274 isl_space_free(space);
275 return NULL;
276 }
277
278 /* Add "part" to "u".
279 * If "disjoint" is set, then "u" is not allowed to already have
280 * a part that is defined on the same space as "part".
281 * Otherwise, compute the union sum of "part" and the part in "u"
282 * defined on the same space.
283 */
284 static __isl_give UNION *FN(UNION,add_part_generic)(__isl_take UNION *u,
285 __isl_take PART *part, int disjoint)
286 {
287 int empty;
288 struct isl_hash_table_entry *entry;
289
290 if (!part)
291 goto error;
292
293 empty = FN(PART,IS_ZERO)(part);
294 if (empty < 0)
295 goto error;
296 if (empty) {
297 FN(PART,free)(part);
298 return u;
299 }
300
301 u = FN(UNION,align_params)(u, FN(PART,get_space)(part));
302 part = FN(PART,align_params)(part, FN(UNION,get_space)(u));
303
304 u = FN(UNION,cow)(u);
305
306 if (!u)
307 goto error;
308
309 entry = FN(UNION,find_part_entry)(u, part->dim, 1);
310 if (!entry)
311 goto error;
312
313 if (!entry->data)
314 entry->data = part;
315 else {
316 if (disjoint)
317 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
318 "additional part should live on separate "
319 "space", goto error);
320 entry->data = FN(PART,union_add_)(entry->data,
321 FN(PART,copy)(part));
322 if (!entry->data)
323 goto error;
324 empty = FN(PART,IS_ZERO)(part);
325 if (empty < 0)
326 goto error;
327 if (empty) {
328 FN(PART,free)(entry->data);
329 isl_hash_table_remove(u->space->ctx, &u->table, entry);
330 }
331 FN(PART,free)(part);
332 }
333
334 return u;
335 error:
336 FN(PART,free)(part);
337 FN(UNION,free)(u);
338 return NULL;
339 }
340
341 /* Add "part" to "u", where "u" is assumed not to already have
342 * a part that is defined on the same space as "part".
343 */
344 __isl_give UNION *FN(FN(UNION,add),PARTS)(__isl_take UNION *u,
345 __isl_take PART *part)
346 {
347 return FN(UNION,add_part_generic)(u, part, 1);
348 }
349
350 static isl_stat FN(UNION,add_part)(__isl_take PART *part, void *user)
351 {
352 UNION **u = (UNION **)user;
353
354 *u = FN(FN(UNION,add),PARTS)(*u, part);
355
356 return isl_stat_ok;
357 }
358
359 __isl_give UNION *FN(UNION,dup)(__isl_keep UNION *u)
360 {
361 UNION *dup;
362
363 if (!u)
364 return NULL;
365
366 #ifdef HAS_TYPE
367 dup = FN(UNION,ZERO)(isl_space_copy(u->space), u->type);
368 #else
369 dup = FN(UNION,ZERO)(isl_space_copy(u->space));
370 #endif
371 if (FN(FN(UNION,foreach),PARTS)(u, &FN(UNION,add_part), &dup) < 0)
372 goto error;
373 return dup;
374 error:
375 FN(UNION,free)(dup);
376 return NULL;
377 }
378
379 __isl_give UNION *FN(UNION,cow)(__isl_take UNION *u)
380 {
381 if (!u)
382 return NULL;
383
384 if (u->ref == 1)
385 return u;
386 u->ref--;
387 return FN(UNION,dup)(u);
388 }
389
390 static isl_stat FN(UNION,free_u_entry)(void **entry, void *user)
391 {
392 PART *part = *entry;
393 FN(PART,free)(part);
394 return isl_stat_ok;
395 }
396
397 __isl_null UNION *FN(UNION,free)(__isl_take UNION *u)
398 {
399 if (!u)
400 return NULL;
401
402 if (--u->ref > 0)
403 return NULL;
404
405 isl_hash_table_foreach(u->space->ctx, &u->table,
406 &FN(UNION,free_u_entry), NULL);
407 isl_hash_table_clear(&u->table);
408 isl_space_free(u->space);
409 free(u);
410 return NULL;
411 }
412
413 S(UNION,align) {
414 isl_reordering *exp;
415 UNION *res;
416 };
417
418 static isl_stat FN(UNION,align_entry)(__isl_take PART *part, void *user)
419 {
420 isl_reordering *exp;
421 S(UNION,align) *data = user;
422
423 exp = isl_reordering_extend_space(isl_reordering_copy(data->exp),
424 FN(PART,get_domain_space)(part));
425
426 data->res = FN(FN(UNION,add),PARTS)(data->res,
427 FN(PART,realign_domain)(part, exp));
428
429 return isl_stat_ok;
430 }
431
432 /* Reorder the parameters of "u" according to the given reordering.
433 */
434 static __isl_give UNION *FN(UNION,realign_domain)(__isl_take UNION *u,
435 __isl_take isl_reordering *r)
436 {
437 S(UNION,align) data = { NULL, NULL };
438
439 if (!u || !r)
440 goto error;
441
442 #ifdef HAS_TYPE
443 data.res = FN(UNION,alloc)(isl_space_copy(r->dim), u->type, u->table.n);
444 #else
445 data.res = FN(UNION,alloc)(isl_space_copy(r->dim), u->table.n);
446 #endif
447 data.exp = r;
448 if (FN(FN(UNION,foreach),PARTS)(u, &FN(UNION,align_entry), &data) < 0)
449 data.res = FN(UNION,free)(data.res);
450
451 isl_reordering_free(data.exp);
452 FN(UNION,free)(u);
453 return data.res;
454 error:
455 FN(UNION,free)(u);
456 isl_reordering_free(r);
457 return NULL;
458 }
459
460 /* Align the parameters of "u" to those of "model".
461 */
462 __isl_give UNION *FN(UNION,align_params)(__isl_take UNION *u,
463 __isl_take isl_space *model)
464 {
465 isl_reordering *r;
466
467 if (!u || !model)
468 goto error;
469
470 if (isl_space_match(u->space, isl_dim_param, model, isl_dim_param)) {
471 isl_space_free(model);
472 return u;
473 }
474
475 model = isl_space_params(model);
476 r = isl_parameter_alignment_reordering(u->space, model);
477 isl_space_free(model);
478
479 return FN(UNION,realign_domain)(u, r);
480 error:
481 isl_space_free(model);
482 FN(UNION,free)(u);
483 return NULL;
484 }
485
486 /* Add "part" to *u, taking the union sum if "u" already has
487 * a part defined on the same space as "part".
488 */
489 static isl_stat FN(UNION,union_add_part)(__isl_take PART *part, void *user)
490 {
491 UNION **u = (UNION **)user;
492
493 *u = FN(UNION,add_part_generic)(*u, part, 0);
494
495 return isl_stat_ok;
496 }
497
498 /* Compute the sum of "u1" and "u2" on the union of their domains,
499 * with the actual sum on the shared domain and
500 * the defined expression on the symmetric difference of the domains.
501 *
502 * This is an internal function that is exposed under different
503 * names depending on whether the base expressions have a zero default
504 * value.
505 * If they do, then this function is called "add".
506 * Otherwise, it is called "union_add".
507 */
508 static __isl_give UNION *FN(UNION,union_add_)(__isl_take UNION *u1,
509 __isl_take UNION *u2)
510 {
511 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
512 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
513
514 u1 = FN(UNION,cow)(u1);
515
516 if (!u1 || !u2)
517 goto error;
518
519 if (FN(FN(UNION,foreach),PARTS)(u2, &FN(UNION,union_add_part), &u1) < 0)
520 goto error;
521
522 FN(UNION,free)(u2);
523
524 return u1;
525 error:
526 FN(UNION,free)(u1);
527 FN(UNION,free)(u2);
528 return NULL;
529 }
530
531 __isl_give UNION *FN(FN(UNION,from),PARTS)(__isl_take PART *part)
532 {
533 isl_space *dim;
534 UNION *u;
535
536 if (!part)
537 return NULL;
538
539 dim = FN(PART,get_space)(part);
540 dim = isl_space_drop_dims(dim, isl_dim_in, 0, isl_space_dim(dim, isl_dim_in));
541 dim = isl_space_drop_dims(dim, isl_dim_out, 0, isl_space_dim(dim, isl_dim_out));
542 #ifdef HAS_TYPE
543 u = FN(UNION,ZERO)(dim, part->type);
544 #else
545 u = FN(UNION,ZERO)(dim);
546 #endif
547 u = FN(FN(UNION,add),PARTS)(u, part);
548
549 return u;
550 }
551
552 S(UNION,match_bin_data) {
553 UNION *u2;
554 UNION *res;
555 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *);
556 };
557
558 /* Check if data->u2 has an element living in the same space as *entry.
559 * If so, call data->fn on the two elements and add the result to
560 * data->res.
561 */
562 static isl_stat FN(UNION,match_bin_entry)(void **entry, void *user)
563 {
564 S(UNION,match_bin_data) *data = user;
565 struct isl_hash_table_entry *entry2;
566 isl_space *space;
567 PART *part = *entry;
568 PART *part2;
569
570 space = FN(PART,get_space)(part);
571 entry2 = FN(UNION,find_part_entry)(data->u2, space, 0);
572 isl_space_free(space);
573 if (!entry2)
574 return isl_stat_error;
575 if (entry2 == isl_hash_table_entry_none)
576 return isl_stat_ok;
577
578 part2 = entry2->data;
579 if (!isl_space_tuple_is_equal(part->dim, isl_dim_out,
580 part2->dim, isl_dim_out))
581 isl_die(FN(UNION,get_ctx)(data->u2), isl_error_invalid,
582 "entries should have the same range space",
583 return isl_stat_error);
584
585 part = FN(PART, copy)(part);
586 part = data->fn(part, FN(PART, copy)(entry2->data));
587
588 data->res = FN(FN(UNION,add),PARTS)(data->res, part);
589 if (!data->res)
590 return isl_stat_error;
591
592 return isl_stat_ok;
593 }
594
595 /* This function is currently only used from isl_polynomial.c
596 * and not from isl_fold.c.
597 */
598 static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
599 __isl_take UNION *u2,
600 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
601 __attribute__ ((unused));
602 /* For each pair of elements in "u1" and "u2" living in the same space,
603 * call "fn" and collect the results.
604 */
605 static __isl_give UNION *FN(UNION,match_bin_op)(__isl_take UNION *u1,
606 __isl_take UNION *u2,
607 __isl_give PART *(*fn)(__isl_take PART *, __isl_take PART *))
608 {
609 S(UNION,match_bin_data) data = { NULL, NULL, fn };
610
611 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
612 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
613
614 if (!u1 || !u2)
615 goto error;
616
617 data.u2 = u2;
618 #ifdef HAS_TYPE
619 data.res = FN(UNION,alloc)(isl_space_copy(u1->space), u1->type,
620 u1->table.n);
621 #else
622 data.res = FN(UNION,alloc)(isl_space_copy(u1->space), u1->table.n);
623 #endif
624 if (isl_hash_table_foreach(u1->space->ctx, &u1->table,
625 &FN(UNION,match_bin_entry), &data) < 0)
626 goto error;
627
628 FN(UNION,free)(u1);
629 FN(UNION,free)(u2);
630 return data.res;
631 error:
632 FN(UNION,free)(u1);
633 FN(UNION,free)(u2);
634 FN(UNION,free)(data.res);
635 return NULL;
636 }
637
638 /* Compute the sum of "u1" and "u2".
639 *
640 * If the base expressions have a default zero value, then the sum
641 * is computed on the union of the domains of "u1" and "u2".
642 * Otherwise, it is computed on their shared domains.
643 */
644 __isl_give UNION *FN(UNION,add)(__isl_take UNION *u1, __isl_take UNION *u2)
645 {
646 #if DEFAULT_IS_ZERO
647 return FN(UNION,union_add_)(u1, u2);
648 #else
649 return FN(UNION,match_bin_op)(u1, u2, &FN(PART,add));
650 #endif
651 }
652
653 #ifndef NO_SUB
654 /* Subtract "u2" from "u1" and return the result.
655 */
656 __isl_give UNION *FN(UNION,sub)(__isl_take UNION *u1, __isl_take UNION *u2)
657 {
658 return FN(UNION,match_bin_op)(u1, u2, &FN(PART,sub));
659 }
660 #endif
661
662 S(UNION,any_set_data) {
663 isl_set *set;
664 UNION *res;
665 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
666 };
667
668 static isl_stat FN(UNION,any_set_entry)(void **entry, void *user)
669 {
670 S(UNION,any_set_data) *data = user;
671 PW *pw = *entry;
672
673 pw = FN(PW,copy)(pw);
674 pw = data->fn(pw, isl_set_copy(data->set));
675
676 data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
677 if (!data->res)
678 return isl_stat_error;
679
680 return isl_stat_ok;
681 }
682
683 /* Update each element of "u" by calling "fn" on the element and "set".
684 */
685 static __isl_give UNION *FN(UNION,any_set_op)(__isl_take UNION *u,
686 __isl_take isl_set *set,
687 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
688 {
689 S(UNION,any_set_data) data = { NULL, NULL, fn };
690
691 u = FN(UNION,align_params)(u, isl_set_get_space(set));
692 set = isl_set_align_params(set, FN(UNION,get_space)(u));
693
694 if (!u || !set)
695 goto error;
696
697 data.set = set;
698 #ifdef HAS_TYPE
699 data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->type,
700 u->table.n);
701 #else
702 data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->table.n);
703 #endif
704 if (isl_hash_table_foreach(u->space->ctx, &u->table,
705 &FN(UNION,any_set_entry), &data) < 0)
706 goto error;
707
708 FN(UNION,free)(u);
709 isl_set_free(set);
710 return data.res;
711 error:
712 FN(UNION,free)(u);
713 isl_set_free(set);
714 FN(UNION,free)(data.res);
715 return NULL;
716 }
717
718 /* Intersect the domain of "u" with the parameter domain "context".
719 */
720 __isl_give UNION *FN(UNION,intersect_params)(__isl_take UNION *u,
721 __isl_take isl_set *set)
722 {
723 return FN(UNION,any_set_op)(u, set, &FN(PW,intersect_params));
724 }
725
726 /* Compute the gist of the domain of "u" with respect to
727 * the parameter domain "context".
728 */
729 __isl_give UNION *FN(UNION,gist_params)(__isl_take UNION *u,
730 __isl_take isl_set *set)
731 {
732 return FN(UNION,any_set_op)(u, set, &FN(PW,gist_params));
733 }
734
735 S(UNION,match_domain_data) {
736 isl_union_set *uset;
737 UNION *res;
738 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*);
739 };
740
741 static int FN(UNION,set_has_dim)(const void *entry, const void *val)
742 {
743 isl_set *set = (isl_set *)entry;
744 isl_space *dim = (isl_space *)val;
745
746 return isl_space_is_equal(set->dim, dim);
747 }
748
749 /* Find the set in data->uset that lives in the same space as the domain
750 * of *entry, apply data->fn to *entry and this set (if any), and add
751 * the result to data->res.
752 */
753 static isl_stat FN(UNION,match_domain_entry)(void **entry, void *user)
754 {
755 S(UNION,match_domain_data) *data = user;
756 uint32_t hash;
757 struct isl_hash_table_entry *entry2;
758 PW *pw = *entry;
759 isl_space *space;
760
761 space = FN(PW,get_domain_space)(pw);
762 hash = isl_space_get_hash(space);
763 entry2 = isl_hash_table_find(data->uset->dim->ctx, &data->uset->table,
764 hash, &FN(UNION,set_has_dim), space, 0);
765 isl_space_free(space);
766 if (!entry2)
767 return isl_stat_ok;
768
769 pw = FN(PW,copy)(pw);
770 pw = data->fn(pw, isl_set_copy(entry2->data));
771
772 data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
773 if (!data->res)
774 return isl_stat_error;
775
776 return isl_stat_ok;
777 }
778
779 /* Apply fn to each pair of PW in u and set in uset such that
780 * the set lives in the same space as the domain of PW
781 * and collect the results.
782 */
783 static __isl_give UNION *FN(UNION,match_domain_op)(__isl_take UNION *u,
784 __isl_take isl_union_set *uset,
785 __isl_give PW *(*fn)(__isl_take PW*, __isl_take isl_set*))
786 {
787 S(UNION,match_domain_data) data = { NULL, NULL, fn };
788
789 u = FN(UNION,align_params)(u, isl_union_set_get_space(uset));
790 uset = isl_union_set_align_params(uset, FN(UNION,get_space)(u));
791
792 if (!u || !uset)
793 goto error;
794
795 data.uset = uset;
796 #ifdef HAS_TYPE
797 data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->type,
798 u->table.n);
799 #else
800 data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->table.n);
801 #endif
802 if (isl_hash_table_foreach(u->space->ctx, &u->table,
803 &FN(UNION,match_domain_entry), &data) < 0)
804 goto error;
805
806 FN(UNION,free)(u);
807 isl_union_set_free(uset);
808 return data.res;
809 error:
810 FN(UNION,free)(u);
811 isl_union_set_free(uset);
812 FN(UNION,free)(data.res);
813 return NULL;
814 }
815
816 /* Intersect the domain of "u" with "uset".
817 * If "uset" is a parameters domain, then intersect the parameter
818 * domain of "u" with this set.
819 */
820 __isl_give UNION *FN(UNION,intersect_domain)(__isl_take UNION *u,
821 __isl_take isl_union_set *uset)
822 {
823 if (isl_union_set_is_params(uset))
824 return FN(UNION,intersect_params)(u,
825 isl_set_from_union_set(uset));
826 return FN(UNION,match_domain_op)(u, uset, &FN(PW,intersect_domain));
827 }
828
829 /* Internal data structure for isl_union_*_subtract_domain.
830 * uset is the set that needs to be removed from the domain.
831 * res collects the results.
832 */
833 S(UNION,subtract_domain_data) {
834 isl_union_set *uset;
835 UNION *res;
836 };
837
838 /* Take the set (which may be empty) in data->uset that lives
839 * in the same space as the domain of "pw", subtract it from the domain
840 * of "pw" and add the result to data->res.
841 */
842 static isl_stat FN(UNION,subtract_domain_entry)(__isl_take PW *pw, void *user)
843 {
844 S(UNION,subtract_domain_data) *data = user;
845 isl_space *space;
846 isl_set *set;
847
848 space = FN(PW,get_domain_space)(pw);
849 set = isl_union_set_extract_set(data->uset, space);
850 pw = FN(PW,subtract_domain)(pw, set);
851 data->res = FN(FN(UNION,add),PARTS)(data->res, pw);
852
853 return isl_stat_ok;
854 }
855
856 /* Subtract "uset' from the domain of "u".
857 */
858 __isl_give UNION *FN(UNION,subtract_domain)(__isl_take UNION *u,
859 __isl_take isl_union_set *uset)
860 {
861 S(UNION,subtract_domain_data) data;
862
863 if (!u || !uset)
864 goto error;
865
866 data.uset = uset;
867 #ifdef HAS_TYPE
868 data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->type,
869 u->table.n);
870 #else
871 data.res = FN(UNION,alloc)(isl_space_copy(u->space), u->table.n);
872 #endif
873 if (FN(FN(UNION,foreach),PARTS)(u,
874 &FN(UNION,subtract_domain_entry), &data) < 0)
875 data.res = FN(UNION,free)(data.res);
876
877 FN(UNION,free)(u);
878 isl_union_set_free(uset);
879 return data.res;
880 error:
881 FN(UNION,free)(u);
882 isl_union_set_free(uset);
883 return NULL;
884 }
885
886 __isl_give UNION *FN(UNION,gist)(__isl_take UNION *u,
887 __isl_take isl_union_set *uset)
888 {
889 if (isl_union_set_is_params(uset))
890 return FN(UNION,gist_params)(u, isl_set_from_union_set(uset));
891 return FN(UNION,match_domain_op)(u, uset, &FN(PW,gist));
892 }
893
894 #ifndef NO_EVAL
895 __isl_give isl_val *FN(UNION,eval)(__isl_take UNION *u,
896 __isl_take isl_point *pnt)
897 {
898 uint32_t hash;
899 struct isl_hash_table_entry *entry;
900 isl_space *space;
901 isl_val *v;
902
903 if (!u || !pnt)
904 goto error;
905
906 space = isl_space_copy(pnt->dim);
907 if (!space)
908 goto error;
909 hash = isl_space_get_hash(space);
910 entry = isl_hash_table_find(u->space->ctx, &u->table,
911 hash, &FN(UNION,has_domain_space),
912 space, 0);
913 isl_space_free(space);
914 if (!entry) {
915 v = isl_val_zero(isl_point_get_ctx(pnt));
916 isl_point_free(pnt);
917 } else {
918 v = FN(PART,eval)(FN(PART,copy)(entry->data), pnt);
919 }
920 FN(UNION,free)(u);
921 return v;
922 error:
923 FN(UNION,free)(u);
924 isl_point_free(pnt);
925 return NULL;
926 }
927 #endif
928
929 /* Coalesce an entry in a UNION. Coalescing is performed in-place.
930 * Since the UNION may have several references, the entry is only
931 * replaced if the coalescing is successful.
932 */
933 static isl_stat FN(UNION,coalesce_entry)(void **entry, void *user)
934 {
935 PART **part_p = (PART **) entry;
936 PART *part;
937
938 part = FN(PART,copy)(*part_p);
939 part = FN(PW,coalesce)(part);
940 if (!part)
941 return isl_stat_error;
942 FN(PART,free)(*part_p);
943 *part_p = part;
944
945 return isl_stat_ok;
946 }
947
948 __isl_give UNION *FN(UNION,coalesce)(__isl_take UNION *u)
949 {
950 if (!u)
951 return NULL;
952
953 if (isl_hash_table_foreach(u->space->ctx, &u->table,
954 &FN(UNION,coalesce_entry), NULL) < 0)
955 goto error;
956
957 return u;
958 error:
959 FN(UNION,free)(u);
960 return NULL;
961 }
962
963 static isl_stat FN(UNION,domain_entry)(__isl_take PART *part, void *user)
964 {
965 isl_union_set **uset = (isl_union_set **)user;
966
967 *uset = isl_union_set_add_set(*uset, FN(PART,domain)(part));
968
969 return isl_stat_ok;
970 }
971
972 __isl_give isl_union_set *FN(UNION,domain)(__isl_take UNION *u)
973 {
974 isl_union_set *uset;
975
976 uset = isl_union_set_empty(FN(UNION,get_space)(u));
977 if (FN(FN(UNION,foreach),PARTS)(u, &FN(UNION,domain_entry), &uset) < 0)
978 goto error;
979
980 FN(UNION,free)(u);
981
982 return uset;
983 error:
984 isl_union_set_free(uset);
985 FN(UNION,free)(u);
986 return NULL;
987 }
988
989 static isl_stat FN(UNION,mul_isl_int_entry)(void **entry, void *user)
990 {
991 PW **pw = (PW **)entry;
992 isl_int *v = user;
993
994 *pw = FN(PW,mul_isl_int)(*pw, *v);
995 if (!*pw)
996 return isl_stat_error;
997
998 return isl_stat_ok;
999 }
1000
1001 __isl_give UNION *FN(UNION,mul_isl_int)(__isl_take UNION *u, isl_int v)
1002 {
1003 if (isl_int_is_one(v))
1004 return u;
1005
1006 if (DEFAULT_IS_ZERO && u && isl_int_is_zero(v)) {
1007 UNION *zero;
1008 isl_space *dim = FN(UNION,get_space)(u);
1009 #ifdef HAS_TYPE
1010 zero = FN(UNION,ZERO)(dim, u->type);
1011 #else
1012 zero = FN(UNION,ZERO)(dim);
1013 #endif
1014 FN(UNION,free)(u);
1015 return zero;
1016 }
1017
1018 u = FN(UNION,cow)(u);
1019 if (!u)
1020 return NULL;
1021
1022 #ifdef HAS_TYPE
1023 if (isl_int_is_neg(v))
1024 u->type = isl_fold_type_negate(u->type);
1025 #endif
1026 if (isl_hash_table_foreach(u->space->ctx, &u->table,
1027 &FN(UNION,mul_isl_int_entry), &v) < 0)
1028 goto error;
1029
1030 return u;
1031 error:
1032 FN(UNION,free)(u);
1033 return NULL;
1034 }
1035
1036 /* Multiply *entry by the isl_val "user".
1037 *
1038 * Return 0 on success and -1 on error.
1039 */
1040 static isl_stat FN(UNION,scale_val_entry)(void **entry, void *user)
1041 {
1042 PW **pw = (PW **)entry;
1043 isl_val *v = user;
1044
1045 *pw = FN(PW,scale_val)(*pw, isl_val_copy(v));
1046 if (!*pw)
1047 return isl_stat_error;
1048
1049 return isl_stat_ok;
1050 }
1051
1052 /* Multiply "u" by "v" and return the result.
1053 */
1054 __isl_give UNION *FN(UNION,scale_val)(__isl_take UNION *u,
1055 __isl_take isl_val *v)
1056 {
1057 if (!u || !v)
1058 goto error;
1059 if (isl_val_is_one(v)) {
1060 isl_val_free(v);
1061 return u;
1062 }
1063
1064 if (DEFAULT_IS_ZERO && u && isl_val_is_zero(v)) {
1065 UNION *zero;
1066 isl_space *space = FN(UNION,get_space)(u);
1067 #ifdef HAS_TYPE
1068 zero = FN(UNION,ZERO)(space, u->type);
1069 #else
1070 zero = FN(UNION,ZERO)(space);
1071 #endif
1072 FN(UNION,free)(u);
1073 isl_val_free(v);
1074 return zero;
1075 }
1076
1077 if (!isl_val_is_rat(v))
1078 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1079 "expecting rational factor", goto error);
1080
1081 u = FN(UNION,cow)(u);
1082 if (!u)
1083 return NULL;
1084
1085 #ifdef HAS_TYPE
1086 if (isl_val_is_neg(v))
1087 u->type = isl_fold_type_negate(u->type);
1088 #endif
1089 if (isl_hash_table_foreach(u->space->ctx, &u->table,
1090 &FN(UNION,scale_val_entry), v) < 0)
1091 goto error;
1092
1093 isl_val_free(v);
1094 return u;
1095 error:
1096 isl_val_free(v);
1097 FN(UNION,free)(u);
1098 return NULL;
1099 }
1100
1101 /* Divide *entry by the isl_val "user".
1102 *
1103 * Return 0 on success and -1 on error.
1104 */
1105 static isl_stat FN(UNION,scale_down_val_entry)(void **entry, void *user)
1106 {
1107 PW **pw = (PW **)entry;
1108 isl_val *v = user;
1109
1110 *pw = FN(PW,scale_down_val)(*pw, isl_val_copy(v));
1111 if (!*pw)
1112 return isl_stat_error;
1113
1114 return isl_stat_ok;
1115 }
1116
1117 /* Divide "u" by "v" and return the result.
1118 */
1119 __isl_give UNION *FN(UNION,scale_down_val)(__isl_take UNION *u,
1120 __isl_take isl_val *v)
1121 {
1122 if (!u || !v)
1123 goto error;
1124 if (isl_val_is_one(v)) {
1125 isl_val_free(v);
1126 return u;
1127 }
1128
1129 if (!isl_val_is_rat(v))
1130 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1131 "expecting rational factor", goto error);
1132 if (isl_val_is_zero(v))
1133 isl_die(isl_val_get_ctx(v), isl_error_invalid,
1134 "cannot scale down by zero", goto error);
1135
1136 u = FN(UNION,cow)(u);
1137 if (!u)
1138 return NULL;
1139
1140 #ifdef HAS_TYPE
1141 if (isl_val_is_neg(v))
1142 u->type = isl_fold_type_negate(u->type);
1143 #endif
1144 if (isl_hash_table_foreach(FN(UNION,get_ctx)(u), &u->table,
1145 &FN(UNION,scale_down_val_entry), v) < 0)
1146 goto error;
1147
1148 isl_val_free(v);
1149 return u;
1150 error:
1151 isl_val_free(v);
1152 FN(UNION,free)(u);
1153 return NULL;
1154 }
1155
1156 S(UNION,plain_is_equal_data)
1157 {
1158 UNION *u2;
1159 isl_bool is_equal;
1160 };
1161
1162 static isl_stat FN(UNION,plain_is_equal_entry)(void **entry, void *user)
1163 {
1164 S(UNION,plain_is_equal_data) *data = user;
1165 struct isl_hash_table_entry *entry2;
1166 PW *pw = *entry;
1167
1168 entry2 = FN(UNION,find_part_entry)(data->u2, pw->dim, 0);
1169 if (!entry2 || entry2 == isl_hash_table_entry_none) {
1170 if (!entry2)
1171 data->is_equal = isl_bool_error;
1172 else
1173 data->is_equal = isl_bool_false;
1174 return isl_stat_error;
1175 }
1176
1177 data->is_equal = FN(PW,plain_is_equal)(pw, entry2->data);
1178 if (data->is_equal < 0 || !data->is_equal)
1179 return isl_stat_error;
1180
1181 return isl_stat_ok;
1182 }
1183
1184 isl_bool FN(UNION,plain_is_equal)(__isl_keep UNION *u1, __isl_keep UNION *u2)
1185 {
1186 S(UNION,plain_is_equal_data) data = { NULL, isl_bool_true };
1187
1188 if (!u1 || !u2)
1189 return isl_bool_error;
1190 if (u1 == u2)
1191 return isl_bool_true;
1192 if (u1->table.n != u2->table.n)
1193 return isl_bool_false;
1194
1195 u1 = FN(UNION,copy)(u1);
1196 u2 = FN(UNION,copy)(u2);
1197 u1 = FN(UNION,align_params)(u1, FN(UNION,get_space)(u2));
1198 u2 = FN(UNION,align_params)(u2, FN(UNION,get_space)(u1));
1199 if (!u1 || !u2)
1200 goto error;
1201
1202 data.u2 = u2;
1203 if (isl_hash_table_foreach(u1->space->ctx, &u1->table,
1204 &FN(UNION,plain_is_equal_entry), &data) < 0 &&
1205 data.is_equal)
1206 goto error;
1207
1208 FN(UNION,free)(u1);
1209 FN(UNION,free)(u2);
1210
1211 return data.is_equal;
1212 error:
1213 FN(UNION,free)(u1);
1214 FN(UNION,free)(u2);
1215 return isl_bool_error;
1216 }
1217
1218 #ifndef NO_NEG
1219 /* Replace *entry by its opposite.
1220 *
1221 * Return 0 on success and -1 on error.
1222 */
1223 static isl_stat FN(UNION,neg_entry)(void **entry, void *user)
1224 {
1225 PW **pw = (PW **) entry;
1226
1227 *pw = FN(PW,neg)(*pw);
1228
1229 return *pw ? isl_stat_ok : isl_stat_error;
1230 }
1231
1232 /* Return the opposite of "u".
1233 */
1234 __isl_give UNION *FN(UNION,neg)(__isl_take UNION *u)
1235 {
1236 u = FN(UNION,cow)(u);
1237 if (!u)
1238 return NULL;
1239
1240 if (isl_hash_table_foreach(u->space->ctx, &u->table,
1241 &FN(UNION,neg_entry), NULL) < 0)
1242 return FN(UNION,free)(u);
1243
1244 return u;
1245 }
1246 #endif
1247
1248 /* Internal data structure for isl_union_*_drop_dims.
1249 * type, first and n are passed to isl_*_drop_dims.
1250 * res collects the results.
1251 */
1252 S(UNION,drop_dims_data) {
1253 enum isl_dim_type type;
1254 unsigned first;
1255 unsigned n;
1256
1257 UNION *res;
1258 };
1259
1260 /* Drop the parameters specified by "data" from "part" and
1261 * add the results to data->res.
1262 */
1263 static isl_stat FN(UNION,drop_dims_entry)(__isl_take PART *part, void *user)
1264 {
1265 S(UNION,drop_dims_data) *data = user;
1266
1267 part = FN(PART,drop_dims)(part, data->type, data->first, data->n);
1268 data->res = FN(FN(UNION,add),PARTS)(data->res, part);
1269 if (!data->res)
1270 return isl_stat_error;
1271
1272 return isl_stat_ok;
1273 }
1274
1275 /* Drop the specified parameters from "u".
1276 * That is, type is required to be isl_dim_param.
1277 */
1278 __isl_give UNION *FN(UNION,drop_dims)( __isl_take UNION *u,
1279 enum isl_dim_type type, unsigned first, unsigned n)
1280 {
1281 isl_space *space;
1282 S(UNION,drop_dims_data) data = { type, first, n };
1283
1284 if (!u)
1285 return NULL;
1286
1287 if (type != isl_dim_param)
1288 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1289 "can only project out parameters",
1290 return FN(UNION,free)(u));
1291
1292 space = FN(UNION,get_space)(u);
1293 space = isl_space_drop_dims(space, type, first, n);
1294 #ifdef HAS_TYPE
1295 data.res = FN(UNION,alloc)(space, u->type, u->table.n);
1296 #else
1297 data.res = FN(UNION,alloc)(space, u->table.n);
1298 #endif
1299 if (FN(FN(UNION,foreach),PARTS)(u,
1300 &FN(UNION,drop_dims_entry), &data) < 0)
1301 data.res = FN(UNION,free)(data.res);
1302
1303 FN(UNION,free)(u);
1304
1305 return data.res;
1306 }
1307
1308 /* Internal data structure for isl_union_*_set_dim_name.
1309 * pos is the position of the parameter that needs to be renamed.
1310 * s is the new name.
1311 * res collects the results.
1312 */
1313 S(UNION,set_dim_name_data) {
1314 unsigned pos;
1315 const char *s;
1316
1317 UNION *res;
1318 };
1319
1320 /* Change the name of the parameter at position data->pos of "part" to data->s
1321 * and add the result to data->res.
1322 */
1323 static isl_stat FN(UNION,set_dim_name_entry)(__isl_take PART *part, void *user)
1324 {
1325 S(UNION,set_dim_name_data) *data = user;
1326
1327 part = FN(PART,set_dim_name)(part, isl_dim_param, data->pos, data->s);
1328 data->res = FN(FN(UNION,add),PARTS)(data->res, part);
1329 if (!data->res)
1330 return isl_stat_error;
1331
1332 return isl_stat_ok;
1333 }
1334
1335 /* Change the name of the parameter at position "pos" to "s".
1336 * That is, type is required to be isl_dim_param.
1337 */
1338 __isl_give UNION *FN(UNION,set_dim_name)(__isl_take UNION *u,
1339 enum isl_dim_type type, unsigned pos, const char *s)
1340 {
1341 S(UNION,set_dim_name_data) data = { pos, s };
1342 isl_space *space;
1343
1344 if (!u)
1345 return NULL;
1346
1347 if (type != isl_dim_param)
1348 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
1349 "can only set parameter names",
1350 return FN(UNION,free)(u));
1351
1352 space = FN(UNION,get_space)(u);
1353 space = isl_space_set_dim_name(space, type, pos, s);
1354 #ifdef HAS_TYPE
1355 data.res = FN(UNION,alloc)(space, u->type, u->table.n);
1356 #else
1357 data.res = FN(UNION,alloc)(space, u->table.n);
1358 #endif
1359
1360 if (FN(FN(UNION,foreach),PARTS)(u,
1361 &FN(UNION,set_dim_name_entry), &data) < 0)
1362 data.res = FN(UNION,free)(data.res);
1363
1364 FN(UNION,free)(u);
1365
1366 return data.res;
1367 }
1368
1369 /* Reset the user pointer on all identifiers of parameters and tuples
1370 * of the space of "part" and add the result to *res.
1371 */
1372 static isl_stat FN(UNION,reset_user_entry)(__isl_take PART *part, void *user)
1373 {
1374 UNION **res = user;
1375
1376 part = FN(PART,reset_user)(part);
1377 *res = FN(FN(UNION,add),PARTS)(*res, part);
1378 if (!*res)
1379 return isl_stat_error;
1380
1381 return isl_stat_ok;
1382 }
1383
1384 /* Reset the user pointer on all identifiers of parameters and tuples
1385 * of the spaces of "u".
1386 */
1387 __isl_give UNION *FN(UNION,reset_user)(__isl_take UNION *u)
1388 {
1389 isl_space *space;
1390 UNION *res;
1391
1392 if (!u)
1393 return NULL;
1394
1395 space = FN(UNION,get_space)(u);
1396 space = isl_space_reset_user(space);
1397 #ifdef HAS_TYPE
1398 res = FN(UNION,alloc)(space, u->type, u->table.n);
1399 #else
1400 res = FN(UNION,alloc)(space, u->table.n);
1401 #endif
1402 if (FN(FN(UNION,foreach),PARTS)(u,
1403 &FN(UNION,reset_user_entry), &res) < 0)
1404 res = FN(UNION,free)(res);
1405
1406 FN(UNION,free)(u);
1407
1408 return res;
1409 }
Integer set library