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