2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2013 Ecole Normale Superieure. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above
13 * copyright notice, this list of conditions and the following
14 * disclaimer in the documentation and/or other materials provided
15 * with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY LEIDEN UNIVERSITY ''AS IS'' AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL LEIDEN UNIVERSITY OR
21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
24 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 * The views and conclusions contained in the software and documentation
30 * are those of the authors and should not be interpreted as
31 * representing official policies, either expressed or implied, of
37 #include <isl/ast_build.h>
41 /* Internal data structure for pet_stmt_build_ast_exprs.
43 * "build" is used to construct an AST expression from an index expression.
44 * "fn_index" is used to transform the index expression prior to
45 * the construction of the AST expression.
46 * "fn_expr" is used to transform the constructed AST expression.
47 * "ref2expr" collects the results.
49 struct pet_build_ast_expr_data
{
51 __isl_give isl_multi_pw_aff
*(*fn_index
)(
52 __isl_take isl_multi_pw_aff
*mpa
, __isl_keep isl_id
*id
,
55 __isl_give isl_ast_expr
*(*fn_expr
)(__isl_take isl_ast_expr
*expr
,
56 __isl_keep isl_id
*id
, void *user
);
58 isl_id_to_ast_expr
*ref2expr
;
61 /* Given an index expression "index" with nested expressions, replace
62 * those nested expressions by parameters. The identifiers
63 * of those parameters reference the corresponding arguments
64 * of "expr". The same identifiers are used in
65 * pet_expr_build_nested_ast_exprs.
67 * In particular, if "index" is of the form
69 * { [domain -> [e_1, ..., e_n]] -> array[f(e_1, ..., e_n)] }
71 * then we construct the expression
73 * [p_1, ..., p_n] -> { domain -> array[f(p_1, ..., p_n)] }
76 static __isl_give isl_multi_pw_aff
*parametrize_nested_exprs(
77 __isl_take isl_multi_pw_aff
*index
, struct pet_expr
*expr
)
81 isl_space
*space
, *space2
;
83 isl_multi_aff
*ma
, *ma2
;
85 ctx
= isl_multi_pw_aff_get_ctx(index
);
86 space
= isl_multi_pw_aff_get_domain_space(index
);
87 space
= isl_space_unwrap(space
);
89 space2
= isl_space_domain(isl_space_copy(space
));
90 ma
= isl_multi_aff_identity(isl_space_map_from_set(space2
));
92 space
= isl_space_insert_dims(space
, isl_dim_param
, 0,
94 for (i
= 0; i
< expr
->n_arg
; ++i
) {
95 isl_id
*id
= isl_id_alloc(ctx
, NULL
, expr
->args
[i
]);
97 space
= isl_space_set_dim_id(space
, isl_dim_param
, i
, id
);
99 space2
= isl_space_domain(isl_space_copy(space
));
100 ls
= isl_local_space_from_space(space2
);
101 ma2
= isl_multi_aff_zero(space
);
102 for (i
= 0; i
< expr
->n_arg
; ++i
) {
104 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
106 ma2
= isl_multi_aff_set_aff(ma2
, i
, aff
);
108 isl_local_space_free(ls
);
110 ma
= isl_multi_aff_range_product(ma
, ma2
);
112 return isl_multi_pw_aff_pullback_multi_aff(index
, ma
);
115 static __isl_give isl_ast_expr
*pet_expr_build_ast_expr(struct pet_expr
*expr
,
116 struct pet_build_ast_expr_data
*data
);
118 /* Construct an associative array from identifiers for the nested
119 * expressions of "expr" to the corresponding isl_ast_expr.
120 * The identifiers reference the corresponding arguments of "expr".
121 * The same identifiers are used in parametrize_nested_exprs.
123 static __isl_give isl_id_to_ast_expr
*pet_expr_build_nested_ast_exprs(
124 struct pet_expr
*expr
, struct pet_build_ast_expr_data
*data
)
127 isl_ctx
*ctx
= isl_ast_build_get_ctx(data
->build
);
128 isl_id_to_ast_expr
*id2expr
;
130 id2expr
= isl_id_to_ast_expr_alloc(ctx
, expr
->n_arg
);
132 for (i
= 0; i
< expr
->n_arg
; ++i
) {
133 isl_id
*id
= isl_id_alloc(ctx
, NULL
, expr
->args
[i
]);
134 isl_ast_expr
*ast_expr
;
136 ast_expr
= pet_expr_build_ast_expr(expr
->args
[i
], data
);
137 id2expr
= isl_id_to_ast_expr_set(id2expr
, id
, ast_expr
);
143 /* Construct an AST expression from an access expression.
145 * If the expression has any arguments, we first convert those
146 * to AST expressions and replace the references to those arguments
147 * in the index expression by parameters.
149 * Then we apply the index transformation if any was provided by the user.
151 * If the "access" is actually an affine expression, we print is as such.
152 * Otherwise, we print a proper access.
154 * If the original expression had any arguments, then they are plugged in now.
156 * Finally, we apply an AST transformation on the result, if any was provided
159 static __isl_give isl_ast_expr
*pet_expr_build_ast_expr(struct pet_expr
*expr
,
160 struct pet_build_ast_expr_data
*data
)
163 isl_multi_pw_aff
*mpa
;
164 isl_ast_expr
*ast_expr
;
165 isl_id_to_ast_expr
*id2expr
;
166 isl_ast_build
*build
= data
->build
;
170 if (expr
->type
!= pet_expr_access
)
171 isl_die(isl_ast_build_get_ctx(build
), isl_error_invalid
,
172 "not an access expression", return NULL
);
174 mpa
= isl_multi_pw_aff_copy(expr
->acc
.index
);
176 if (expr
->n_arg
> 0) {
177 mpa
= parametrize_nested_exprs(mpa
, expr
);
178 id2expr
= pet_expr_build_nested_ast_exprs(expr
, data
);
182 mpa
= data
->fn_index(mpa
, expr
->acc
.ref_id
, data
->user_index
);
183 mpa
= isl_multi_pw_aff_coalesce(mpa
);
185 if (!pet_expr_is_affine(expr
)) {
186 ast_expr
= isl_ast_build_access_from_multi_pw_aff(build
, mpa
);
188 pa
= isl_multi_pw_aff_get_pw_aff(mpa
, 0);
189 ast_expr
= isl_ast_build_expr_from_pw_aff(build
, pa
);
190 isl_multi_pw_aff_free(mpa
);
193 ast_expr
= isl_ast_expr_substitute_ids(ast_expr
, id2expr
);
195 ast_expr
= data
->fn_expr(ast_expr
, expr
->acc
.ref_id
,
201 /* Construct an AST expression from the access expression "expr" and
202 * add the mapping from reference identifier to AST expression to
205 static int add_access(struct pet_expr
*expr
, void *user
)
207 struct pet_build_ast_expr_data
*data
= user
;
209 isl_ast_expr
*ast_expr
;
211 ast_expr
= pet_expr_build_ast_expr(expr
, data
);
213 id
= isl_id_copy(expr
->acc
.ref_id
);
214 data
->ref2expr
= isl_id_to_ast_expr_set(data
->ref2expr
, id
, ast_expr
);
219 /* Construct an associative array from reference identifiers of
220 * access expressions in "stmt" to the corresponding isl_ast_expr.
221 * Each index expression is first transformed through "fn_index"
222 * (if not NULL). Then an AST expression is generated using "build".
223 * Finally, the AST expression is transformed using "fn_expr"
226 __isl_give isl_id_to_ast_expr
*pet_stmt_build_ast_exprs(struct pet_stmt
*stmt
,
227 __isl_keep isl_ast_build
*build
,
228 __isl_give isl_multi_pw_aff
*(*fn_index
)(
229 __isl_take isl_multi_pw_aff
*mpa
, __isl_keep isl_id
*id
,
230 void *user
), void *user_index
,
231 __isl_give isl_ast_expr
*(*fn_expr
)(__isl_take isl_ast_expr
*expr
,
232 __isl_keep isl_id
*id
, void *user
), void *user_expr
)
234 struct pet_build_ast_expr_data data
=
235 { build
, fn_index
, user_index
, fn_expr
, user_expr
};
241 ctx
= isl_ast_build_get_ctx(build
);
242 data
.ref2expr
= isl_id_to_ast_expr_alloc(ctx
, 0);
243 if (pet_expr_foreach_access_expr(stmt
->body
, &add_access
, &data
) < 0)
244 data
.ref2expr
= isl_id_to_ast_expr_free(data
.ref2expr
);
246 return data
.ref2expr
;
249 /* Print the access expression "expr" to "p".
251 * We look up the corresponding isl_ast_expr in "ref2expr"
252 * and print that to "p".
254 static __isl_give isl_printer
*print_access(__isl_take isl_printer
*p
,
255 struct pet_expr
*expr
, __isl_keep isl_id_to_ast_expr
*ref2expr
)
257 isl_ast_expr
*ast_expr
;
260 if (!isl_id_to_ast_expr_has(ref2expr
, expr
->acc
.ref_id
))
261 isl_die(isl_printer_get_ctx(p
), isl_error_internal
,
262 "missing expression", return isl_printer_free(p
));
264 ast_expr
= isl_id_to_ast_expr_get(ref2expr
,
265 isl_id_copy(expr
->acc
.ref_id
));
266 is_access
= isl_ast_expr_get_type(ast_expr
) == isl_ast_expr_op
&&
267 isl_ast_expr_get_op_type(ast_expr
) == isl_ast_op_access
;
269 p
= isl_printer_print_str(p
, "(");
270 p
= isl_printer_print_ast_expr(p
, ast_expr
);
272 p
= isl_printer_print_str(p
, ")");
273 isl_ast_expr_free(ast_expr
);
278 /* Is "op" a postfix operator?
280 static int is_postfix(enum pet_op_type op
)
283 case pet_op_post_inc
:
284 case pet_op_post_dec
:
291 /* Print "expr" to "p".
293 * If "outer" is set, then we are printing the outer expression statement.
295 * The access subexpressions are replaced by the isl_ast_expr
296 * associated to its reference identifier in "ref2expr".
298 static __isl_take isl_printer
*print_pet_expr(__isl_take isl_printer
*p
,
299 struct pet_expr
*expr
, int outer
,
300 __isl_keep isl_id_to_ast_expr
*ref2expr
)
304 switch (expr
->type
) {
305 case pet_expr_double
:
306 p
= isl_printer_print_str(p
, expr
->d
.s
);
308 case pet_expr_access
:
309 p
= print_access(p
, expr
, ref2expr
);
313 p
= isl_printer_print_str(p
, "(");
314 if (!is_postfix(expr
->op
))
315 p
= isl_printer_print_str(p
, pet_op_str(expr
->op
));
316 p
= print_pet_expr(p
, expr
->args
[pet_un_arg
], 0, ref2expr
);
317 if (is_postfix(expr
->op
))
318 p
= isl_printer_print_str(p
, pet_op_str(expr
->op
));
320 p
= isl_printer_print_str(p
, ")");
322 case pet_expr_binary
:
324 p
= isl_printer_print_str(p
, "(");
325 p
= print_pet_expr(p
, expr
->args
[pet_bin_lhs
], 0,
327 p
= isl_printer_print_str(p
, " ");
328 p
= isl_printer_print_str(p
, pet_op_str(expr
->op
));
329 p
= isl_printer_print_str(p
, " ");
330 p
= print_pet_expr(p
, expr
->args
[pet_bin_rhs
], 0,
333 p
= isl_printer_print_str(p
, ")");
335 case pet_expr_ternary
:
337 p
= isl_printer_print_str(p
, "(");
338 p
= print_pet_expr(p
, expr
->args
[pet_ter_cond
], 0,
340 p
= isl_printer_print_str(p
, " ? ");
341 p
= print_pet_expr(p
, expr
->args
[pet_ter_true
], 0,
343 p
= isl_printer_print_str(p
, " : ");
344 p
= print_pet_expr(p
, expr
->args
[pet_ter_false
], 0,
347 p
= isl_printer_print_str(p
, ")");
350 p
= isl_printer_print_str(p
, expr
->name
);
351 p
= isl_printer_print_str(p
, "(");
352 for (i
= 0; i
< expr
->n_arg
; ++i
) {
354 p
= isl_printer_print_str(p
, ", ");
355 p
= print_pet_expr(p
, expr
->args
[i
], 1, ref2expr
);
357 p
= isl_printer_print_str(p
, ")");
361 p
= isl_printer_print_str(p
, "(");
362 p
= isl_printer_print_str(p
, "(");
363 p
= isl_printer_print_str(p
, expr
->type_name
);
364 p
= isl_printer_print_str(p
, ") ");
365 p
= print_pet_expr(p
, expr
->args
[0], 0, ref2expr
);
367 p
= isl_printer_print_str(p
, ")");
374 /* Print "stmt" to "p".
376 * The access expressions in "stmt" are replaced by the isl_ast_expr
377 * associated to its reference identifier in "ref2expr".
379 __isl_give isl_printer
*pet_stmt_print_body(struct pet_stmt
*stmt
,
380 __isl_take isl_printer
*p
, __isl_keep isl_id_to_ast_expr
*ref2expr
)
383 return isl_printer_free(p
);
384 p
= isl_printer_start_line(p
);
385 p
= print_pet_expr(p
, stmt
->body
, 1, ref2expr
);
386 p
= isl_printer_print_str(p
, ";");
387 p
= isl_printer_end_line(p
);