1 /*
2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2013 Ecole Normale Superieure. All rights reserved.
4 * Copyright 2017 Sven Verdoolaege. All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following
15 * disclaimer in the documentation and/or other materials provided
16 * with the distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
19 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
21 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
22 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
25 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 *
30 * The views and conclusions contained in the software and documentation
31 * are those of the authors and should not be interpreted as
32 * representing official policies, either expressed or implied, of
33 * Leiden University.
34 */
35
36 #include <set>
37 #include <vector>
38
39 #include "clang.h"
40 #include "expr.h"
41 #include "id.h"
42 #include "scop_plus.h"
43 #include "tree.h"
44
45 using namespace std;
46 using namespace clang;
47
48 /* Add the sequence of nested arrays of structures of the direct
49 * subfields of the record type represented by "ancestors"
50 * to "arrays". The final element in the sequence is guaranteed
51 * to refer to a record type.
52 *
53 * If any of the subfields is anonymous, then add its subfields as well.
54 */
collect_direct_sub_arrays(ValueDecl * decl,__isl_keep isl_id_list * ancestors,array_desc_set & arrays)55 static void collect_direct_sub_arrays(ValueDecl *decl,
56 __isl_keep isl_id_list *ancestors, array_desc_set &arrays)
57 {
58 isl_ctx *ctx;
59 QualType type = decl->getType();
60 RecordDecl *record;
61 RecordDecl::field_iterator it;
62
63 type = pet_clang_base_type(type);
64 record = pet_clang_record_decl(type);
65
66 ctx = isl_id_list_get_ctx(ancestors);
67 for (it = record->field_begin(); it != record->field_end(); ++it) {
68 FieldDecl *field = *it;
69 bool anonymous = field->isAnonymousStructOrUnion();
70 isl_id *id;
71 isl_id_list *extended;
72
73 if (anonymous) {
74 collect_direct_sub_arrays(field, ancestors, arrays);
75 continue;
76 }
77 extended = isl_id_list_copy(ancestors);
78 id = pet_id_from_decl(ctx, field);
79 extended = isl_id_list_add(extended, id);
80 arrays.insert(extended);
81 }
82 }
83
84 /* Add the sequence of nested array declarations "list" to "arrays".
85 *
86 * If "list" represents a member access (i.e., the list has at least
87 * two elements), then also add the other members in each of its
88 * outer arrays.
89 */
add_with_siblings(__isl_take isl_id_list * list,array_desc_set & arrays)90 static void add_with_siblings(__isl_take isl_id_list *list,
91 array_desc_set &arrays)
92 {
93 int n;
94
95 arrays.insert(isl_id_list_copy(list));
96
97 n = isl_id_list_n_id(list);
98 while (n > 1) {
99 isl_id *id;
100 ValueDecl *decl;
101
102 list = isl_id_list_drop(list, --n, 1);
103 arrays.insert(isl_id_list_copy(list));
104 id = isl_id_list_get_id(list, n - 1);
105 decl = pet_id_get_decl(id);
106 isl_id_free(id);
107 collect_direct_sub_arrays(decl, list, arrays);
108 }
109 isl_id_list_free(list);
110 }
111
112 /* Construct a sequence of nested array declarations containing
113 * a single element corresponding to the tuple identifier
114 * of the set space "space".
115 *
116 * If the array being accessed has a NULL ValueDecl, then it
117 * is a virtual scalar. These do not need to be collected
118 * because they are added to the scop of the statement writing
119 * to the scalar. Return an empty list instead.
120 */
extract_list_from_tuple_id(__isl_keep isl_space * space)121 static __isl_give isl_id_list *extract_list_from_tuple_id(
122 __isl_keep isl_space *space)
123 {
124 isl_ctx *ctx;
125 isl_id *id;
126
127 id = isl_space_get_tuple_id(space, isl_dim_set);
128 if (pet_id_get_decl(id))
129 return isl_id_list_from_id(id);
130 isl_id_free(id);
131 ctx = isl_space_get_ctx(space);
132 return isl_id_list_alloc(ctx, 0);
133 }
134
135 /* Construct a sequence of nested array declarations corresponding
136 * to the accessed data space "space".
137 *
138 * If "space" represents an array access, then the extracted sequence
139 * contains a single element corresponding to the array declaration.
140 * Otherwise, if "space" represents a member access, then the extracted
141 * sequence contains an element for the outer array of structures and
142 * for each nested array or scalar.
143 *
144 * If the array being accessed has a NULL ValueDecl, then it
145 * is a virtual scalar. These do not need to be collected
146 * because they are added to the scop of the statement writing
147 * to the scalar. Return an empty list instead.
148 */
extract_list(__isl_keep isl_space * space)149 static __isl_give isl_id_list *extract_list(__isl_keep isl_space *space)
150 {
151 isl_bool is_wrapping;
152 isl_space *range;
153 isl_id_list *list;
154
155 is_wrapping = isl_space_is_wrapping(space);
156 if (is_wrapping < 0)
157 return NULL;
158 if (!is_wrapping)
159 return extract_list_from_tuple_id(space);
160 space = isl_space_unwrap(isl_space_copy(space));
161 range = isl_space_range(isl_space_copy(space));
162 list = extract_list(range);
163 isl_space_free(range);
164 space = isl_space_domain(space);
165 list = isl_id_list_concat(extract_list(space), list);
166 isl_space_free(space);
167 return list;
168 }
169
170 /* Extract one or more sequences of declarations from the accessed
171 * data space "space" and add them to "arrays".
172 *
173 * If "space" represents an array access, then the extracted sequence
174 * contains a single element corresponding to the array declaration.
175 * Otherwise, if "space" represents a member access, then the extracted
176 * sequences contain an element for the outer array of structures and
177 * for each nested array or scalar. If such a sequence is constructed
178 * corresponding to a given member access, then such sequences are
179 * also constructed for the other members in the same structure.
180 *
181 * If the array being accessed has a NULL ValueDecl, then it
182 * is a virtual scalar. We don't need to collect such scalars
183 * because they are added to the scop of the statement writing
184 * to the scalar. extract_list returns an empty list for
185 * such arrays.
186 *
187 * If the sequence corresponding to "space" already appears
188 * in "arrays", then its siblings have already been added as well,
189 * so there is nothing left to do.
190 */
space_collect_arrays(__isl_take isl_space * space,void * user)191 static isl_stat space_collect_arrays(__isl_take isl_space *space, void *user)
192 {
193 array_desc_set *arrays = (array_desc_set *) user;
194 int n;
195 isl_id_list *list;
196
197 list = extract_list(space);
198 n = isl_id_list_n_id(list);
199 if (n > 0 && arrays->find(list) == arrays->end())
200 add_with_siblings(list, *arrays);
201 else
202 isl_id_list_free(list);
203 isl_space_free(space);
204
205 return isl_stat_ok;
206 }
207
208 /* Extract one or more sequences of declarations from the access expression
209 * "expr" and add them to "arrays".
210 */
access_collect_arrays(__isl_keep pet_expr * expr,array_desc_set & arrays)211 static void access_collect_arrays(__isl_keep pet_expr *expr,
212 array_desc_set &arrays)
213 {
214 if (pet_expr_is_affine(expr))
215 return;
216
217 pet_expr_access_foreach_data_space(expr,
218 &space_collect_arrays, &arrays);
219 }
220
expr_collect_arrays(__isl_keep pet_expr * expr,array_desc_set & arrays)221 static void expr_collect_arrays(__isl_keep pet_expr *expr,
222 array_desc_set &arrays)
223 {
224 int n;
225
226 if (!expr)
227 return;
228
229 n = pet_expr_get_n_arg(expr);
230 for (int i = 0; i < n; ++i) {
231 pet_expr *arg;
232
233 arg = pet_expr_get_arg(expr, i);
234 expr_collect_arrays(arg, arrays);
235 pet_expr_free(arg);
236 }
237
238 if (pet_expr_get_type(expr) == pet_expr_access)
239 access_collect_arrays(expr, arrays);
240 }
241
242 /* Wrapper around access_collect_arrays for use as a callback function
243 * to pet_tree_foreach_access_expr.
244 */
access_collect_wrap(__isl_keep pet_expr * expr,void * user)245 static int access_collect_wrap(__isl_keep pet_expr *expr, void *user)
246 {
247 array_desc_set *arrays = (array_desc_set *) user;
248
249 access_collect_arrays(expr, *arrays);
250
251 return 0;
252 }
253
stmt_collect_arrays(struct pet_stmt * stmt,array_desc_set & arrays)254 static void stmt_collect_arrays(struct pet_stmt *stmt,
255 array_desc_set &arrays)
256 {
257 if (!stmt)
258 return;
259
260 for (unsigned i = 0; i < stmt->n_arg; ++i)
261 expr_collect_arrays(stmt->args[i], arrays);
262
263 pet_tree_foreach_access_expr(stmt->body, &access_collect_wrap, &arrays);
264 }
265
266 /* Collect the set of all accessed arrays (or scalars) in "scop",
267 * except those that already appear in scop->arrays,
268 * and put them in "arrays".
269 *
270 * Each accessed array is represented by a sequence of nested
271 * array declarations, one for the outer array of structures
272 * and one for each member access.
273 *
274 * The arrays that already appear in scop->arrays are assumed
275 * to be simple arrays, represented by a sequence of a single element.
276 */
pet_scop_collect_arrays(struct pet_scop * scop,array_desc_set & arrays)277 void pet_scop_collect_arrays(struct pet_scop *scop,
278 array_desc_set &arrays)
279 {
280 if (!scop)
281 return;
282
283 for (int i = 0; i < scop->n_stmt; ++i)
284 stmt_collect_arrays(scop->stmts[i], arrays);
285
286 for (int i = 0; i < scop->n_array; ++i) {
287 ValueDecl *decl;
288 isl_id_list *ancestors;
289
290 isl_id *id = isl_set_get_tuple_id(scop->arrays[i]->extent);
291 decl = pet_id_get_decl(id);
292
293 if (!decl) {
294 isl_id_free(id);
295 continue;
296 }
297
298 ancestors = isl_id_list_from_id(id);
299 arrays.erase(ancestors);
300 isl_id_list_free(ancestors);
301 }
302 }
303