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.
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
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.
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.
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
42 #include "scop_plus.h"
46 using namespace clang
;
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.
53 * If any of the subfields is anonymous, then add its subfields as well.
55 static void collect_direct_sub_arrays(ValueDecl
*decl
,
56 __isl_keep isl_id_list
*ancestors
, array_desc_set
&arrays
)
59 QualType type
= decl
->getType();
61 RecordDecl::field_iterator it
;
63 type
= pet_clang_base_type(type
);
64 record
= pet_clang_record_decl(type
);
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();
71 isl_id_list
*extended
;
74 collect_direct_sub_arrays(field
, ancestors
, arrays
);
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
);
84 /* Add the sequence of nested array declarations "list" to "arrays".
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
90 static void add_with_siblings(__isl_take isl_id_list
*list
,
91 array_desc_set
&arrays
)
95 arrays
.insert(isl_id_list_copy(list
));
97 n
= isl_id_list_n_id(list
);
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
);
107 collect_direct_sub_arrays(decl
, list
, arrays
);
109 isl_id_list_free(list
);
112 /* Construct a sequence of nested array declarations containing
113 * a single element corresponding to the tuple identifier
114 * of the set space "space".
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.
121 static __isl_give isl_id_list
*extract_list_from_tuple_id(
122 __isl_keep isl_space
*space
)
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
);
131 ctx
= isl_space_get_ctx(space
);
132 return isl_id_list_alloc(ctx
, 0);
135 /* Construct a sequence of nested array declarations corresponding
136 * to the accessed data space "space".
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.
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.
149 static __isl_give isl_id_list
*extract_list(__isl_keep isl_space
*space
)
154 if (!isl_space_is_wrapping(space
))
155 return extract_list_from_tuple_id(space
);
156 space
= isl_space_unwrap(isl_space_copy(space
));
157 range
= isl_space_range(isl_space_copy(space
));
158 list
= extract_list(range
);
159 isl_space_free(range
);
160 space
= isl_space_domain(space
);
161 list
= isl_id_list_concat(extract_list(space
), list
);
162 isl_space_free(space
);
166 /* Extract one or more sequences of declarations from the accessed
167 * data space "space" and add them to "arrays".
169 * If "space" represents an array access, then the extracted sequence
170 * contains a single element corresponding to the array declaration.
171 * Otherwise, if "space" represents a member access, then the extracted
172 * sequences contain an element for the outer array of structures and
173 * for each nested array or scalar. If such a sequence is constructed
174 * corresponding to a given member access, then such sequences are
175 * also constructed for the other members in the same structure.
177 * If the array being accessed has a NULL ValueDecl, then it
178 * is a virtual scalar. We don't need to collect such scalars
179 * because they are added to the scop of the statement writing
180 * to the scalar. extract_list returns an empty list for
183 * If the sequence corresponding to "space" already appears
184 * in "arrays", then its siblings have already been added as well,
185 * so there is nothing left to do.
187 static isl_stat
space_collect_arrays(__isl_take isl_space
*space
, void *user
)
189 array_desc_set
*arrays
= (array_desc_set
*) user
;
193 list
= extract_list(space
);
194 n
= isl_id_list_n_id(list
);
195 if (n
> 0 && arrays
->find(list
) == arrays
->end())
196 add_with_siblings(list
, *arrays
);
198 isl_id_list_free(list
);
199 isl_space_free(space
);
204 /* Extract one or more sequences of declarations from the access expression
205 * "expr" and add them to "arrays".
207 static void access_collect_arrays(__isl_keep pet_expr
*expr
,
208 array_desc_set
&arrays
)
210 if (pet_expr_is_affine(expr
))
213 pet_expr_access_foreach_data_space(expr
,
214 &space_collect_arrays
, &arrays
);
217 static void expr_collect_arrays(__isl_keep pet_expr
*expr
,
218 array_desc_set
&arrays
)
225 n
= pet_expr_get_n_arg(expr
);
226 for (int i
= 0; i
< n
; ++i
) {
229 arg
= pet_expr_get_arg(expr
, i
);
230 expr_collect_arrays(arg
, arrays
);
234 if (pet_expr_get_type(expr
) == pet_expr_access
)
235 access_collect_arrays(expr
, arrays
);
238 /* Wrapper around access_collect_arrays for use as a callback function
239 * to pet_tree_foreach_access_expr.
241 static int access_collect_wrap(__isl_keep pet_expr
*expr
, void *user
)
243 array_desc_set
*arrays
= (array_desc_set
*) user
;
245 access_collect_arrays(expr
, *arrays
);
250 static void stmt_collect_arrays(struct pet_stmt
*stmt
,
251 array_desc_set
&arrays
)
256 for (unsigned i
= 0; i
< stmt
->n_arg
; ++i
)
257 expr_collect_arrays(stmt
->args
[i
], arrays
);
259 pet_tree_foreach_access_expr(stmt
->body
, &access_collect_wrap
, &arrays
);
262 /* Collect the set of all accessed arrays (or scalars) in "scop",
263 * except those that already appear in scop->arrays,
264 * and put them in "arrays".
266 * Each accessed array is represented by a sequence of nested
267 * array declarations, one for the outer array of structures
268 * and one for each member access.
270 * The arrays that already appear in scop->arrays are assumed
271 * to be simple arrays, represented by a sequence of a single element.
273 void pet_scop_collect_arrays(struct pet_scop
*scop
,
274 array_desc_set
&arrays
)
279 for (int i
= 0; i
< scop
->n_stmt
; ++i
)
280 stmt_collect_arrays(scop
->stmts
[i
], arrays
);
282 for (int i
= 0; i
< scop
->n_array
; ++i
) {
284 isl_id_list
*ancestors
;
286 isl_id
*id
= isl_set_get_tuple_id(scop
->arrays
[i
]->extent
);
287 decl
= pet_id_get_decl(id
);
294 ancestors
= isl_id_list_from_id(id
);
295 arrays
.erase(ancestors
);
296 isl_id_list_free(ancestors
);