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 */
26S(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 */
37struct 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 */
47S(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 */
55static 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 */
66static 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(ctx: u->space->ctx, table: &u->table,
76 fn: &FN(UNION,call_on_group), user: &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 */
83static 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 */
97isl_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: &FN(UNION,count_part), user: &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 */
110static isl_stat FN(UNION,free_group_entry)(void **entry, void *user)
111{
112 PART *part = *entry;
113
114 FN(PART,free)(pw: part);
115 return isl_stat_ok;
116}
117
118/* Free all memory allocated for "group" and return NULL.
119 */
120static __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(space: group->domain_space);
129 isl_hash_table_foreach(ctx, table: &group->part_table,
130 fn: &FN(UNION,free_group_entry), NULL);
131 isl_hash_table_clear(table: &group->part_table);
132 isl_space_free(space: group->domain_space);
133 free(ptr: 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 */
140static __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(space: 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, table: &group->part_table, min_size: size) < 0)
154 return FN(UNION,group_free)(group);
155
156 return group;
157error:
158 isl_space_free(space: domain_space);
159 return NULL;
160}
161
162/* Is the space of "entry" equal to "space", ignoring parameters?
163 */
164static 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)(pw: part);
171 return isl_space_has_equal_tuples(space1: part_space, space2: 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 */
177static __isl_give S(UNION,group) *FN(UNION,group_cow)(
178 __isl_take S(UNION,group) *group)
179{
180 return group;
181}
182
183S(UNION,foreach_data)
184{
185 isl_stat (*fn)(__isl_take PART *part, void *user);
186 void *user;
187};
188
189static 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)(pw: 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 */
202static 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(space: group->domain_space);
211 return isl_hash_table_foreach(ctx, table: &group->part_table,
212 fn: &FN(UNION,call_on_copy), user);
213}
214
215isl_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: &FN(UNION,group_call_on_copy), user: &data);
224}
225
226/* Is the domain space of the group of expressions at "entry"
227 * equal to that of "space", ignoring parameters?
228 */
229static 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(space1: group->domain_space, space2: 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 */
248static 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)(upma: u);
260 hash = isl_space_get_tuple_domain_hash(space);
261 group_entry = isl_hash_table_find(ctx, table: &u->table, key_hash: hash,
262 eq: &FN(UNION,group_has_same_domain_space_tuples), val: 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(space: isl_space_copy(space));
267 group = FN(UNION,group_alloc)(domain_space: domain, size: 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, table: &group->part_table, key_hash: hash,
278 eq: &FN(UNION,has_space_tuples), val: 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 */
287static __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)(upma: u);
299
300 part = part_entry->data;
301 ctx = FN(UNION,get_ctx)(upma: u);
302 space = FN(PART,peek_space)(pw: part);
303 hash = isl_space_get_tuple_domain_hash(space);
304 group_entry = isl_hash_table_find(ctx, table: &u->table, key_hash: hash,
305 eq: &FN(UNION,group_has_same_domain_space_tuples), val: space, reserve: 0);
306 if (!group_entry)
307 return FN(UNION,free)(upma: 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, table: &group->part_table, entry: part_entry);
313 FN(PART,free)(pw: part);
314
315 if (group->part_table.n != 0)
316 return u;
317
318 isl_hash_table_remove(ctx, table: &u->table, entry: group_entry);
319 FN(UNION,group_free)(group);
320
321 return u;
322}
323
324/* Are the domains of "part1" and "part2" disjoint?
325 */
326static 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)(pw: part1));
335 dom2 = FN(PART,domain)(FN(PART,copy)(pw: part2));
336 disjoint = isl_set_is_disjoint(set1: dom1, set2: dom2);
337 isl_set_free(set: dom1);
338 isl_set_free(set: 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 */
346static 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(space1: part->dim, space2: 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)(part1: part, part2: 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 */
376static 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)(upma: u);
388 space = FN(PART,peek_space)(pw: part);
389 hash = isl_space_get_tuple_domain_hash(space);
390 group_entry = isl_hash_table_find(ctx, table: &u->table, key_hash: hash,
391 eq: &FN(UNION,group_has_same_domain_space_tuples), val: space, reserve: 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, table: &group->part_table,
398 fn: &FN(UNION,check_disjoint_domain_entry), user: 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 */
405static 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 */
423S(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 */
432static 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(space: group->domain_space);
443 return isl_hash_table_foreach(ctx, table: &group->part_table,
444 fn: data->fn, user: data->user);
445}
446
447/* Call "fn" on each part entry of "u".
448 */
449static 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: &FN(UNION,group_call_inplace), user: &data);
455}
456
457static 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 */
466isl_bool FN(UNION,plain_is_empty)(__isl_take UNION *u)
467{
468 if (!u)
469 return isl_bool_error;
470 return isl_bool_ok(b: 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 */
476static 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(b: 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 */
492isl_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: &FN(UNION,group_single_space), user: &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 */
512static 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)(pw: 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 */
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: &FN(UNION,extract_part), user: &part) < 0)
541 part = FN(PART,free)(pw: part);
542 FN(UNION,free)(upma: u);
543 return part;
544error:
545 FN(UNION,free)(upma: u);
546 return NULL;
547}
548
549#include <isl_union_templ.c>
550

source code of polly/lib/External/isl/isl_union_multi.c