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 */
21struct 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 */
33isl_size FN(FN(UNION,n),BASE)(__isl_keep UNION *u)
34{
35 return u ? u->table.n : isl_size_error;
36}
37
38S(UNION,foreach_data)
39{
40 isl_stat (*fn)(__isl_take PART *part, void *user);
41 void *user;
42};
43
44static 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)(pw: part);
50 if (!part)
51 return isl_stat_error;
52 return data->fn(part, data->user);
53}
54
55isl_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(ctx: u->space->ctx, table: &u->table,
64 fn: &FN(UNION,call_on_copy), user: &data);
65}
66
67/* Is the domain space of "entry" equal to the domain of "space",
68 * ignoring parameters?
69 */
70static 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(space: part->dim);
78
79 return isl_space_tuple_is_equal(space1: part->dim, type1: isl_dim_in,
80 space2: space, type2: 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 */
92static 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)(upa: u);
105 hash = isl_space_get_tuple_domain_hash(space);
106 entry = isl_hash_table_find(ctx, table: &u->table, key_hash: hash,
107 eq: &FN(UNION,has_same_domain_space_tuples), val: 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(space1: part->dim, type1: isl_dim_out,
114 space2: space, type2: 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 */
128static __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)(upa: u);
135
136 FN(PART,free)(pw: part_entry->data);
137 ctx = FN(UNION,get_ctx)(upa: u);
138 isl_hash_table_remove(ctx, table: &u->table, entry: 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 */
150static 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 */
162static 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 */
172static 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)(upa: u);
180 return isl_hash_table_foreach(ctx, table: &u->table, fn, user);
181}
182
183static 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 */
189static 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 */
204isl_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)(upa: u), table: &u->table,
215 key_hash: hash, eq: &FN(UNION,has_domain_space_tuples),
216 val: space, reserve: 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)(pw: entry->data), user);
222}
223
224static isl_stat FN(UNION,free_u_entry)(void **entry, void *user)
225{
226 PART *part = *entry;
227 FN(PART,free)(pw: part);
228 return isl_stat_ok;
229}
230
231#include <isl_union_templ.c>
232

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