1 /*
2 * Copyright 2010 INRIA Saclay
3 * Copyright 2013 Ecole Normale Superieure
4 * Copyright 2015 INRIA Paris-Rocquencourt
5 *
6 * Use of this software is governed by the MIT license
7 *
8 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * 91893 Orsay, France
11 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
12 * and INRIA Paris-Rocquencourt, Domaine de Voluceau, Rocquenqourt, B.P. 105,
13 * 78153 Le Chesnay Cedex France
14 */
15
16 #include <isl/hash.h>
17 #include <isl_union_macro.h>
18
19 /* A group of expressions defined over the same domain space "domain_space".
20 * The entries of "part_table" are the individual expressions,
21 * keyed on the entire space of the expression.
22 *
23 * Each UNION has its own groups, so there can only ever be a single
24 * reference to each group.
25 */
S(UNION,group)26 S(UNION,group) {
27 isl_space *domain_space;
28 struct isl_hash_table part_table;
29 };
30
31 /* A union of expressions defined over different disjoint domains.
32 * "space" describes the parameters.
33 * The entries of "table" are keyed on the domain space of the entry and
34 * contain groups of expressions that are defined over the same domain space.
35 */
36 struct UNION {
37 int ref;
38 isl_space *space;
39
40 struct isl_hash_table table;
41 };
42
43 /* Internal data structure for isl_union_*_foreach_group.
44 * "fn" is the function that needs to be called on each group.
45 */
S(UNION,foreach_group_data)46 S(UNION,foreach_group_data)
47 {
48 isl_stat (*fn)(__isl_keep S(UNION,group) *group, void *user);
49 void *user;
50 };
51
52 /* Call data->fn on the group stored at *entry.
53 */
FN(UNION,call_on_group)54 static isl_stat FN(UNION,call_on_group)(void **entry, void *user)
55 {
56 S(UNION,group) *group = *entry;
57 S(UNION,foreach_group_data) *data;
58
59 data = (S(UNION,foreach_group_data) *) user;
60 return data->fn(group, data->user);
61 }
62
63 /* Call "fn" on each group of expressions in "u".
64 */
FN(UNION,foreach_group)65 static isl_stat FN(UNION,foreach_group)(__isl_keep UNION *u,
66 isl_stat (*fn)(__isl_keep S(UNION,group) *group, void *user),
67 void *user)
68 {
69 S(UNION,foreach_group_data) data = { fn, user };
70
71 if (!u)
72 return isl_stat_error;
73
74 return isl_hash_table_foreach(u->space->ctx, &u->table,
75 &FN(UNION,call_on_group), &data);
76 }
77
78 /* A isl_union_*_foreach_group callback for counting the total number
79 * of expressions in a UNION. Add the number of expressions in "group"
80 * to *n.
81 */
FN(UNION,count_part)82 static isl_stat FN(UNION,count_part)(__isl_keep S(UNION,group) *group,
83 void *user)
84 {
85 int *n = user;
86
87 if (!group)
88 return isl_stat_error;
89
90 *n += group->part_table.n;
91 return isl_stat_ok;
92 }
93
94 /* Return the number of base expressions in "u".
95 */
FN(FN (UNION,n),BASE)96 isl_size FN(FN(UNION,n),BASE)(__isl_keep UNION *u)
97 {
98 int n;
99
100 n = 0;
101 if (FN(UNION,foreach_group)(u, &FN(UNION,count_part), &n) < 0)
102 return isl_size_error;
103 return n;
104 }
105
106 /* Free an entry in a group of expressions.
107 * Each entry in such a group is a single expression.
108 */
FN(UNION,free_group_entry)109 static isl_stat FN(UNION,free_group_entry)(void **entry, void *user)
110 {
111 PART *part = *entry;
112
113 FN(PART,free)(part);
114 return isl_stat_ok;
115 }
116
117 /* Free all memory allocated for "group" and return NULL.
118 */
S(UNION,group)119 static __isl_null S(UNION,group) *FN(UNION,group_free)(
120 __isl_take S(UNION,group) *group)
121 {
122 isl_ctx *ctx;
123
124 if (!group)
125 return NULL;
126
127 ctx = isl_space_get_ctx(group->domain_space);
128 isl_hash_table_foreach(ctx, &group->part_table,
129 &FN(UNION,free_group_entry), NULL);
130 isl_hash_table_clear(&group->part_table);
131 isl_space_free(group->domain_space);
132 free(group);
133 return NULL;
134 }
135
136 /* Allocate a group of expressions defined over the same domain space
137 * with domain space "domain_space" and initial size "size".
138 */
S(UNION,group)139 static __isl_give S(UNION,group) *FN(UNION,group_alloc)(
140 __isl_take isl_space *domain_space, int size)
141 {
142 isl_ctx *ctx;
143 S(UNION,group) *group;
144
145 if (!domain_space)
146 return NULL;
147 ctx = isl_space_get_ctx(domain_space);
148 group = isl_calloc_type(ctx, S(UNION,group));
149 if (!group)
150 goto error;
151 group->domain_space = domain_space;
152 if (isl_hash_table_init(ctx, &group->part_table, size) < 0)
153 return FN(UNION,group_free)(group);
154
155 return group;
156 error:
157 isl_space_free(domain_space);
158 return NULL;
159 }
160
161 /* Is the space of "entry" equal to "space"?
162 */
FN(UNION,has_space)163 static isl_bool FN(UNION,has_space)(const void *entry, const void *val)
164 {
165 PART *part = (PART *) entry;
166 isl_space *space = (isl_space *) val;
167
168 return isl_space_is_equal(part->dim, space);
169 }
170
171 /* Return a group equal to "group", but with a single reference.
172 * Since all groups have only a single reference, simply return "group".
173 */
S(UNION,group)174 static __isl_give S(UNION,group) *FN(UNION,group_cow)(
175 __isl_take S(UNION,group) *group)
176 {
177 return group;
178 }
179
S(UNION,foreach_data)180 S(UNION,foreach_data)
181 {
182 isl_stat (*fn)(__isl_take PART *part, void *user);
183 void *user;
184 };
185
FN(UNION,call_on_copy)186 static isl_stat FN(UNION,call_on_copy)(void **entry, void *user)
187 {
188 PART *part = *entry;
189 S(UNION,foreach_data) *data = (S(UNION,foreach_data) *) user;
190
191 part = FN(PART,copy)(part);
192 if (!part)
193 return isl_stat_error;
194 return data->fn(part, data->user);
195 }
196
197 /* Call data->fn on a copy of each expression in "group".
198 */
FN(UNION,group_call_on_copy)199 static isl_stat FN(UNION,group_call_on_copy)(__isl_keep S(UNION,group) *group,
200 void *user)
201 {
202 isl_ctx *ctx;
203
204 if (!group)
205 return isl_stat_error;
206
207 ctx = isl_space_get_ctx(group->domain_space);
208 return isl_hash_table_foreach(ctx, &group->part_table,
209 &FN(UNION,call_on_copy), user);
210 }
211
FN(FN (UNION,foreach),BASE)212 isl_stat FN(FN(UNION,foreach),BASE)(__isl_keep UNION *u,
213 isl_stat (*fn)(__isl_take PART *part, void *user), void *user)
214 {
215 S(UNION,foreach_data) data = { fn, user };
216
217 if (!u)
218 return isl_stat_error;
219
220 return FN(UNION,foreach_group)(u, &FN(UNION,group_call_on_copy), &data);
221 }
222
223 /* Is the domain space of the group of expressions at "entry"
224 * equal to that of "space"?
225 */
FN(UNION,group_has_same_domain_space)226 static isl_bool FN(UNION,group_has_same_domain_space)(const void *entry,
227 const void *val)
228 {
229 S(UNION,group) *group = (S(UNION,group) *) entry;
230 isl_space *space = (isl_space *) val;
231
232 return isl_space_is_domain_internal(group->domain_space, space);
233 }
234
235 /* Return the entry, if any, in "u" that lives in "space".
236 * If "reserve" is set, then an entry is created if it does not exist yet.
237 * Return NULL on error and isl_hash_table_entry_none if no entry was found.
238 * Note that when "reserve" is set, the function will never return
239 * isl_hash_table_entry_none.
240 *
241 * First look for the group of expressions with the same domain space,
242 * creating one if needed.
243 * Then look for the expression living in the specified space in that group.
244 */
FN(UNION,find_part_entry)245 static struct isl_hash_table_entry *FN(UNION,find_part_entry)(
246 __isl_keep UNION *u, __isl_keep isl_space *space, int reserve)
247 {
248 isl_ctx *ctx;
249 uint32_t hash;
250 struct isl_hash_table_entry *group_entry;
251 S(UNION,group) *group;
252
253 if (!u || !space)
254 return NULL;
255
256 ctx = FN(UNION,get_ctx)(u);
257 hash = isl_space_get_domain_hash(space);
258 group_entry = isl_hash_table_find(ctx, &u->table, hash,
259 &FN(UNION,group_has_same_domain_space), space, reserve);
260 if (!group_entry || group_entry == isl_hash_table_entry_none)
261 return group_entry;
262 if (reserve && !group_entry->data) {
263 isl_space *domain = isl_space_domain(isl_space_copy(space));
264 group = FN(UNION,group_alloc)(domain, 1);
265 group_entry->data = group;
266 } else {
267 group = group_entry->data;
268 if (reserve)
269 group = FN(UNION,group_cow)(group);
270 }
271 if (!group)
272 return NULL;
273 hash = isl_space_get_hash(space);
274 return isl_hash_table_find(ctx, &group->part_table, hash,
275 &FN(UNION,has_space), space, reserve);
276 }
277
278 /* Remove "part_entry" from the hash table of "u".
279 *
280 * First look the group_entry in "u" holding the group that
281 * contains "part_entry". Remove "part_entry" from that group.
282 * If the group becomes empty, then also remove the group_entry from "u".
283 */
FN(UNION,remove_part_entry)284 static __isl_give UNION *FN(UNION,remove_part_entry)(__isl_take UNION *u,
285 struct isl_hash_table_entry *part_entry)
286 {
287 isl_ctx *ctx;
288 uint32_t hash;
289 isl_space *space;
290 PART *part;
291 struct isl_hash_table_entry *group_entry;
292 S(UNION,group) *group;
293
294 if (!u || !part_entry)
295 return FN(UNION,free)(u);
296
297 part = part_entry->data;
298 ctx = FN(UNION,get_ctx)(u);
299 space = FN(PART,peek_space)(part);
300 hash = isl_space_get_domain_hash(space);
301 group_entry = isl_hash_table_find(ctx, &u->table, hash,
302 &FN(UNION,group_has_same_domain_space), space, 0);
303 if (!group_entry)
304 return FN(UNION,free)(u);
305 if (group_entry == isl_hash_table_entry_none)
306 isl_die(ctx, isl_error_internal, "missing group",
307 return FN(UNION,free)(u));
308 group = group_entry->data;
309 isl_hash_table_remove(ctx, &group->part_table, part_entry);
310 FN(PART,free)(part);
311
312 if (group->part_table.n != 0)
313 return u;
314
315 isl_hash_table_remove(ctx, &u->table, group_entry);
316 FN(UNION,group_free)(group);
317
318 return u;
319 }
320
321 /* Are the domains of "part1" and "part2" disjoint?
322 */
FN(UNION,disjoint_domain)323 static isl_bool FN(UNION,disjoint_domain)(__isl_keep PART *part1,
324 __isl_keep PART *part2)
325 {
326 isl_set *dom1, *dom2;
327 isl_bool disjoint;
328
329 if (!part1 || !part2)
330 return isl_bool_error;
331 dom1 = FN(PART,domain)(FN(PART,copy)(part1));
332 dom2 = FN(PART,domain)(FN(PART,copy)(part2));
333 disjoint = isl_set_is_disjoint(dom1, dom2);
334 isl_set_free(dom1);
335 isl_set_free(dom2);
336
337 return disjoint;
338 }
339
340 /* Check that the expression at *entry has a domain that is disjoint
341 * from that of "part", unless they also have the same target space.
342 */
FN(UNION,check_disjoint_domain_entry)343 static isl_stat FN(UNION,check_disjoint_domain_entry)(void **entry, void *user)
344 {
345 PART *part = user;
346 PART *other = *entry;
347 isl_bool equal;
348 isl_bool disjoint;
349
350 equal = isl_space_is_equal(part->dim, other->dim);
351 if (equal < 0)
352 return isl_stat_error;
353 if (equal)
354 return isl_stat_ok;
355
356 disjoint = FN(UNION,disjoint_domain)(part, other);
357 if (disjoint < 0)
358 return isl_stat_error;
359 if (!disjoint)
360 isl_die(FN(PART,get_ctx)(part), isl_error_invalid,
361 "overlapping domain with other part",
362 return isl_stat_error);
363 return isl_stat_ok;
364 }
365
366 /* Check that the domain of "part" is disjoint from the domain of the entries
367 * in "u" that are defined on the same domain space, but have a different
368 * target space.
369 * If there is no group of expressions in "u" with the same domain space,
370 * then everything is fine. Otherwise, check the individual expressions
371 * in that group.
372 */
FN(UNION,check_disjoint_domain_other)373 static isl_stat FN(UNION,check_disjoint_domain_other)(__isl_keep UNION *u,
374 __isl_keep PART *part)
375 {
376 isl_ctx *ctx;
377 uint32_t hash;
378 isl_space *space;
379 struct isl_hash_table_entry *group_entry;
380 S(UNION,group) *group;
381
382 if (!u || !part)
383 return isl_stat_error;
384 ctx = FN(UNION,get_ctx)(u);
385 space = FN(PART,peek_space)(part);
386 hash = isl_space_get_domain_hash(space);
387 group_entry = isl_hash_table_find(ctx, &u->table, hash,
388 &FN(UNION,group_has_same_domain_space), space, 0);
389 if (!group_entry)
390 return isl_stat_error;
391 if (group_entry == isl_hash_table_entry_none)
392 return isl_stat_ok;
393 group = group_entry->data;
394 return isl_hash_table_foreach(ctx, &group->part_table,
395 &FN(UNION,check_disjoint_domain_entry), part);
396 }
397
398 /* Check that the domain of "part1" is disjoint from the domain of "part2".
399 * This check is performed before "part2" is added to a UNION to ensure
400 * that the UNION expression remains a function.
401 */
FN(UNION,check_disjoint_domain)402 static isl_stat FN(UNION,check_disjoint_domain)(__isl_keep PART *part1,
403 __isl_keep PART *part2)
404 {
405 isl_bool disjoint;
406
407 disjoint = FN(UNION,disjoint_domain)(part1, part2);
408 if (disjoint < 0)
409 return isl_stat_error;
410 if (!disjoint)
411 isl_die(FN(PART,get_ctx)(part1), isl_error_invalid,
412 "domain of additional part should be disjoint",
413 return isl_stat_error);
414 return isl_stat_ok;
415 }
416
417 /* Internal data structure for isl_union_*_foreach_inplace.
418 * "fn" is the function that needs to be called on each entry.
419 */
S(UNION,foreach_inplace_data)420 S(UNION,foreach_inplace_data)
421 {
422 isl_stat (*fn)(void **entry, void *user);
423 void *user;
424 };
425
426 /* isl_union_*_foreach_group callback for calling data->fn on
427 * each part entry in the group.
428 */
FN(UNION,group_call_inplace)429 static isl_stat FN(UNION,group_call_inplace)(__isl_keep S(UNION,group) *group,
430 void *user)
431 {
432 isl_ctx *ctx;
433 S(UNION,foreach_inplace_data) *data;
434
435 if (!group)
436 return isl_stat_error;
437
438 data = (S(UNION,foreach_inplace_data) *) user;
439 ctx = isl_space_get_ctx(group->domain_space);
440 return isl_hash_table_foreach(ctx, &group->part_table,
441 data->fn, data->user);
442 }
443
444 /* Call "fn" on each part entry of "u".
445 */
FN(UNION,foreach_inplace)446 static isl_stat FN(UNION,foreach_inplace)(__isl_keep UNION *u,
447 isl_stat (*fn)(void **part, void *user), void *user)
448 {
449 S(UNION,foreach_inplace_data) data = { fn, user };
450
451 return FN(UNION,foreach_group)(u, &FN(UNION,group_call_inplace), &data);
452 }
453
FN(UNION,free_u_entry)454 static isl_stat FN(UNION,free_u_entry)(void **entry, void *user)
455 {
456 S(UNION,group) *group = *entry;
457 FN(UNION,group_free)(group);
458 return isl_stat_ok;
459 }
460
461 /* Does "u" have an obviously empty definition domain?
462 */
FN(UNION,plain_is_empty)463 isl_bool FN(UNION,plain_is_empty)(__isl_take UNION *u)
464 {
465 if (!u)
466 return isl_bool_error;
467 return isl_bool_ok(u->table.n == 0);
468 }
469
470 /* Set "single" to true if this group of expressions
471 * contains an expression living in exactly one space.
472 */
FN(UNION,group_single_space)473 static isl_stat FN(UNION,group_single_space)(__isl_keep S(UNION,group) *group,
474 void *user)
475 {
476 isl_bool *single = user;
477
478 if (!group)
479 return isl_stat_error;
480 *single = isl_bool_ok(group->part_table.n == 1);
481 return isl_stat_ok;
482 }
483
484 /* Can this union expression be converted to a single base expression?
485 * That is, does it contain a base expression in exactly one space?
486 * In particular, is only one domain space involved and
487 * is only a single expression associated to that domain?
488 */
FN(FN (UNION,isa),BASE)489 isl_bool FN(FN(UNION,isa),BASE)(__isl_take UNION *u)
490 {
491 isl_bool single;
492
493 if (!u)
494 return isl_bool_error;
495 if (u->table.n != 1)
496 return isl_bool_false;
497 if (FN(UNION,foreach_group)(u,
498 &FN(UNION,group_single_space), &single) < 0)
499 return isl_bool_error;
500 return single;
501 }
502
503 /* Callback for isl_union_*_foreach_inplace call
504 * on a union expression with a single base expression.
505 * Store that base expression in "user".
506 * This callback should only be called once
507 * for any given isl_union_*_foreach_inplace call.
508 */
FN(UNION,extract_part)509 static isl_stat FN(UNION,extract_part)(void **entry, void *user)
510 {
511 PART **part_p = user;
512 PART *part = *entry;
513
514 if (*part_p)
515 isl_die(FN(PART,get_ctx)(part), isl_error_internal,
516 "more than one part", return isl_stat_error);
517 *part_p = FN(PART,copy)(part);
518 if (!*part_p)
519 return isl_stat_error;
520 return isl_stat_ok;
521 }
522
523 /* Convert the union expression to its single base expression.
524 */
FN(FN (UNION,as),BASE)525 __isl_give PART *FN(FN(UNION,as),BASE)(__isl_take UNION *u)
526 {
527 isl_bool has_single_space;
528 PART *part = NULL;
529
530 has_single_space = FN(FN(UNION,isa),BASE)(u);
531 if (has_single_space < 0)
532 goto error;
533 if (!has_single_space)
534 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
535 "expecting elements in exactly one space",
536 goto error);
537 if (FN(UNION,foreach_inplace)(u, &FN(UNION,extract_part), &part) < 0)
538 part = FN(PART,free)(part);
539 FN(UNION,free)(u);
540 return part;
541 error:
542 FN(UNION,free)(u);
543 return NULL;
544 }
545
546 #include <isl_union_templ.c>
547