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.h>
14 #include <isl_union_macro.h>
15
16 /* A union of expressions defined over different domain spaces.
17 * "space" describes the parameters.
18 * The entries of "table" are keyed on the domain space of the entry
19 * (ignoring parameters).
20 */
21 struct UNION {
22 int ref;
23 #ifdef HAS_TYPE
24 enum isl_fold type;
25 #endif
26 isl_space *space;
27
28 struct isl_hash_table table;
29 };
30
31 /* Return the number of base expressions in "u".
32 */
FN(FN (UNION,n),BASE)33 isl_size FN(FN(UNION,n),BASE)(__isl_keep UNION *u)
34 {
35 return u ? u->table.n : isl_size_error;
36 }
37
S(UNION,foreach_data)38 S(UNION,foreach_data)
39 {
40 isl_stat (*fn)(__isl_take PART *part, void *user);
41 void *user;
42 };
43
FN(UNION,call_on_copy)44 static isl_stat FN(UNION,call_on_copy)(void **entry, void *user)
45 {
46 PART *part = *entry;
47 S(UNION,foreach_data) *data = (S(UNION,foreach_data) *)user;
48
49 part = FN(PART,copy)(part);
50 if (!part)
51 return isl_stat_error;
52 return data->fn(part, data->user);
53 }
54
FN(FN (UNION,foreach),BASE)55 isl_stat FN(FN(UNION,foreach),BASE)(__isl_keep UNION *u,
56 isl_stat (*fn)(__isl_take PART *part, void *user), void *user)
57 {
58 S(UNION,foreach_data) data = { fn, user };
59
60 if (!u)
61 return isl_stat_error;
62
63 return isl_hash_table_foreach(u->space->ctx, &u->table,
64 &FN(UNION,call_on_copy), &data);
65 }
66
67 /* Is the domain space of "entry" equal to the domain of "space",
68 * ignoring parameters?
69 */
FN(UNION,has_same_domain_space_tuples)70 static isl_bool FN(UNION,has_same_domain_space_tuples)(const void *entry,
71 const void *val)
72 {
73 PART *part = (PART *)entry;
74 isl_space *space = (isl_space *) val;
75
76 if (isl_space_is_set(space))
77 return isl_space_is_set(part->dim);
78
79 return isl_space_tuple_is_equal(part->dim, isl_dim_in,
80 space, isl_dim_in);
81 }
82
83 /* Return the entry, if any, in "u" that lives in "space".
84 * If "reserve" is set, then an entry is created if it does not exist yet.
85 * Return NULL on error and isl_hash_table_entry_none if no entry was found.
86 * Note that when "reserve" is set, the function will never return
87 * isl_hash_table_entry_none.
88 *
89 * First look for the entry (if any) with the same domain space.
90 * If it exists, then check if the range space also matches.
91 */
FN(UNION,find_part_entry)92 static struct isl_hash_table_entry *FN(UNION,find_part_entry)(
93 __isl_keep UNION *u, __isl_keep isl_space *space, int reserve)
94 {
95 isl_ctx *ctx;
96 uint32_t hash;
97 struct isl_hash_table_entry *entry;
98 isl_bool equal;
99 PART *part;
100
101 if (!u || !space)
102 return NULL;
103
104 ctx = FN(UNION,get_ctx)(u);
105 hash = isl_space_get_tuple_domain_hash(space);
106 entry = isl_hash_table_find(ctx, &u->table, hash,
107 &FN(UNION,has_same_domain_space_tuples), space, reserve);
108 if (!entry || entry == isl_hash_table_entry_none)
109 return entry;
110 if (reserve && !entry->data)
111 return entry;
112 part = entry->data;
113 equal = isl_space_tuple_is_equal(part->dim, isl_dim_out,
114 space, isl_dim_out);
115 if (equal < 0)
116 return NULL;
117 if (equal)
118 return entry;
119 if (!reserve)
120 return isl_hash_table_entry_none;
121 isl_die(FN(UNION,get_ctx)(u), isl_error_invalid,
122 "union expression can only contain a single "
123 "expression over a given domain", return NULL);
124 }
125
126 /* Remove "part_entry" from the hash table of "u".
127 */
FN(UNION,remove_part_entry)128 static __isl_give UNION *FN(UNION,remove_part_entry)(__isl_take UNION *u,
129 struct isl_hash_table_entry *part_entry)
130 {
131 isl_ctx *ctx;
132
133 if (!u || !part_entry)
134 return FN(UNION,free)(u);
135
136 FN(PART,free)(part_entry->data);
137 ctx = FN(UNION,get_ctx)(u);
138 isl_hash_table_remove(ctx, &u->table, part_entry);
139
140 return u;
141 }
142
143 /* Check that the domain of "part" is disjoint from the domain of the entries
144 * in "u" that are defined on the same domain space, but have a different
145 * target space.
146 * Since a UNION with a single entry per domain space is not allowed
147 * to contain two entries with the same domain space, there cannot be
148 * any such other entry.
149 */
FN(UNION,check_disjoint_domain_other)150 static isl_stat FN(UNION,check_disjoint_domain_other)(__isl_keep UNION *u,
151 __isl_keep PART *part)
152 {
153 return isl_stat_ok;
154 }
155
156 /* Check that the domain of "part1" is disjoint from the domain of "part2".
157 * This check is performed before "part2" is added to a UNION to ensure
158 * that the UNION expression remains a function.
159 * Since a UNION with a single entry per domain space is not allowed
160 * to contain two entries with the same domain space, fail unconditionally.
161 */
FN(UNION,check_disjoint_domain)162 static isl_stat FN(UNION,check_disjoint_domain)(__isl_keep PART *part1,
163 __isl_keep PART *part2)
164 {
165 isl_die(FN(PART,get_ctx)(part1), isl_error_invalid,
166 "additional part should live on separate space",
167 return isl_stat_error);
168 }
169
170 /* Call "fn" on each part entry of "u".
171 */
FN(UNION,foreach_inplace)172 static isl_stat FN(UNION,foreach_inplace)(__isl_keep UNION *u,
173 isl_stat (*fn)(void **part, void *user), void *user)
174 {
175 isl_ctx *ctx;
176
177 if (!u)
178 return isl_stat_error;
179 ctx = FN(UNION,get_ctx)(u);
180 return isl_hash_table_foreach(ctx, &u->table, fn, user);
181 }
182
183 static isl_bool FN(PART,has_domain_space_tuples)(__isl_keep PART *part,
184 __isl_keep isl_space *space);
185
186 /* Do the tuples of "space" correspond to those of the domain of "part"?
187 * That is, is the domain space of "part" equal to "space", ignoring parameters?
188 */
FN(UNION,has_domain_space_tuples)189 static isl_bool FN(UNION,has_domain_space_tuples)(const void *entry,
190 const void *val)
191 {
192 PART *part = (PART *)entry;
193 isl_space *space = (isl_space *) val;
194
195 return FN(PART,has_domain_space_tuples)(part, space);
196 }
197
198 /* Call "fn" on each part of "u" that has domain space "space".
199 *
200 * Since each entry is defined over a different domain space,
201 * simply look for an entry with the given domain space and
202 * call "fn" on the corresponding part if there is one.
203 */
FN(UNION,foreach_on_domain)204 isl_stat FN(UNION,foreach_on_domain)(__isl_keep UNION *u,
205 __isl_keep isl_space *space,
206 isl_stat (*fn)(__isl_take PART *part, void *user), void *user)
207 {
208 uint32_t hash;
209 struct isl_hash_table_entry *entry;
210
211 if (!u || !space)
212 return isl_stat_error;
213 hash = isl_space_get_tuple_hash(space);
214 entry = isl_hash_table_find(FN(UNION,get_ctx)(u), &u->table,
215 hash, &FN(UNION,has_domain_space_tuples),
216 space, 0);
217 if (!entry)
218 return isl_stat_error;
219 if (entry == isl_hash_table_entry_none)
220 return isl_stat_ok;
221 return fn(FN(PART,copy)(entry->data), user);
222 }
223
FN(UNION,free_u_entry)224 static isl_stat FN(UNION,free_u_entry)(void **entry, void *user)
225 {
226 PART *part = *entry;
227 FN(PART,free)(part);
228 return isl_stat_ok;
229 }
230
231 #include <isl_union_templ.c>
232