1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
| /*
* Copyright 2010 INRIA Saclay
* Copyright 2013 Ecole Normale Superieure
*
* Use of this software is governed by the MIT license
*
* Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
* Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
* 91893 Orsay, France
* and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
*/
#include <isl_hash_private.h>
#include <isl_union_macro.h>
/* A union of expressions defined over different domain spaces.
* "space" describes the parameters.
* The entries of "table" are keyed on the domain space of the entry.
*/
struct UNION {
int ref;
#ifdef HAS_TYPE
enum isl_fold type;
#endif
isl_space *space;
struct isl_hash_table table;
};
/* Return the number of base expressions in "u".
*/
int FN(FN(UNION,n),BASE)(__isl_keep UNION *u)
{
return u ? u->table.n : 0;
}
S(UNION,foreach_data)
{
isl_stat (*fn)(__isl_take PART *part, void *user);
void *user;
};
static isl_stat FN(UNION,call_on_copy)(void **entry, void *user)
{
PART *part = *entry;
S(UNION,foreach_data) *data = (S(UNION,foreach_data) *)user;
part = FN(PART,copy)(part);
if (!part)
return isl_stat_error;
return data->fn(part, data->user);
}
isl_stat FN(FN(UNION,foreach),BASE)(__isl_keep UNION *u,
isl_stat (*fn)(__isl_take PART *part, void *user), void *user)
{
S(UNION,foreach_data) data = { fn, user };
if (!u)
return isl_stat_error;
return isl_hash_table_foreach(u->space->ctx, &u->table,
&FN(UNION,call_on_copy), &data);
}
/* Is the domain space of "entry" equal to the domain of "space"?
*/
static int FN(UNION,has_same_domain_space)(const void *entry, const void *val)
{
PART *part = (PART *)entry;
isl_space *space = (isl_space *) val;
if (isl_space_is_set(space))
return isl_space_is_set(part->dim);
return isl_space_tuple_is_equal(part->dim, isl_dim_in,
space, isl_dim_in);
}
/* Return the entry, if any, in "u" that lives in "space".
* If "reserve" is set, then an entry is created if it does not exist yet.
* Return NULL on error and isl_hash_table_entry_none if no entry was found.
* Note that when "reserve" is set, the function will never return
* isl_hash_table_entry_none.
*
* First look for the entry (if any) with the same domain space.
* If it exists, then check if the range space also matches.
*/
static struct isl_hash_table_entry *FN(UNION,find_part_entry)(
__isl_keep UNION *u, __isl_keep isl_space *space, int reserve)
{
isl_ctx *ctx;
uint32_t hash;
struct isl_hash_table_entry *entry;
isl_bool equal;
PART *part;
if (!u || !space)
return NULL;
ctx = FN(UNION,get_ctx)(u);
hash = isl_space_get_domain_hash(space);
entry = isl_hash_table_find(ctx, &u->table, hash,
&FN(UNION,has_same_domain_space), space, reserve);
if (!entry)
return reserve ? NULL : isl_hash_table_entry_none;
if (reserve && !entry->data)
return entry;
part = entry->data;
equal = isl_space_tuple_is_equal(part->dim, isl_dim_out,
space, isl_dim_out);
if (equal < 0)
return NULL;
if (equal)
return entry;
if (!reserve)
return isl_hash_table_entry_none;
isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
"union expression can only contain a single "
"expression over a given domain", return NULL);
}
/* Remove "part_entry" from the hash table of "u".
*/
static __isl_give UNION *FN(UNION,remove_part_entry)(__isl_take UNION *u,
struct isl_hash_table_entry *part_entry)
{
isl_ctx *ctx;
if (!u || !part_entry)
return FN(UNION,free)(u);
ctx = FN(UNION,get_ctx)(u);
isl_hash_table_remove(ctx, &u->table, part_entry);
FN(PART,free)(part_entry->data);
return u;
}
/* Check that the domain of "part" is disjoint from the domain of the entries
* in "u" that are defined on the same domain space, but have a different
* target space.
* Since a UNION with a single entry per domain space is not allowed
* to contain two entries with the same domain space, there cannot be
* any such other entry.
*/
static isl_stat FN(UNION,check_disjoint_domain_other)(__isl_keep UNION *u,
__isl_keep PART *part)
{
return isl_stat_ok;
}
/* Check that the domain of "part1" is disjoint from the domain of "part2".
* This check is performed before "part2" is added to a UNION to ensure
* that the UNION expression remains a function.
* Since a UNION with a single entry per domain space is not allowed
* to contain two entries with the same domain space, fail unconditionally.
*/
static isl_stat FN(UNION,check_disjoint_domain)(__isl_keep PART *part1,
__isl_keep PART *part2)
{
isl_die(FN(PART,get_ctx)(part1), isl_error_invalid,
"additional part should live on separate space",
return isl_stat_error);
}
/* Call "fn" on each part entry of "u".
*/
static isl_stat FN(UNION,foreach_inplace)(__isl_keep UNION *u,
isl_stat (*fn)(void **part, void *user), void *user)
{
isl_ctx *ctx;
if (!u)
return isl_stat_error;
ctx = FN(UNION,get_ctx)(u);
return isl_hash_table_foreach(ctx, &u->table, fn, user);
}
/* Does "u" have a single reference?
* That is, can we change "u" inplace?
*/
static isl_bool FN(UNION,has_single_reference)(__isl_keep UNION *u)
{
if (!u)
return isl_bool_error;
return u->ref == 1;
}
static isl_stat FN(UNION,free_u_entry)(void **entry, void *user)
{
PART *part = *entry;
FN(PART,free)(part);
return isl_stat_ok;
}
#include <isl_union_templ.c>
|