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