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>
43 /* Internal data structure for pet_stmt_build_ast_exprs.
45 * "build" is used to construct an AST expression from an index expression.
46 * "fn_index" is used to transform the index expression prior to
47 * the construction of the AST expression.
48 * "fn_expr" is used to transform the constructed AST expression.
49 * "ref2expr" collects the results.
51 struct pet_build_ast_expr_data
{
53 __isl_give isl_multi_pw_aff
*(*fn_index
)(
54 __isl_take isl_multi_pw_aff
*mpa
, __isl_keep isl_id
*id
,
57 __isl_give isl_ast_expr
*(*fn_expr
)(__isl_take isl_ast_expr
*expr
,
58 __isl_keep isl_id
*id
, void *user
);
60 isl_id_to_ast_expr
*ref2expr
;
63 /* Given an index expression "index" with nested expressions, replace
64 * those nested expressions by parameters. The identifiers
65 * of those parameters reference the corresponding arguments
66 * of "expr". The same identifiers are used in
67 * pet_expr_build_nested_ast_exprs.
69 * In particular, if "index" is of the form
71 * { [domain -> [e_1, ..., e_n]] -> array[f(e_1, ..., e_n)] }
73 * then we construct the expression
75 * [p_1, ..., p_n] -> { domain -> array[f(p_1, ..., p_n)] }
78 static __isl_give isl_multi_pw_aff
*parametrize_nested_exprs(
79 __isl_take isl_multi_pw_aff
*index
, __isl_keep pet_expr
*expr
)
83 isl_space
*space
, *space2
;
85 isl_multi_aff
*ma
, *ma2
;
87 ctx
= isl_multi_pw_aff_get_ctx(index
);
88 space
= isl_multi_pw_aff_get_domain_space(index
);
89 space
= isl_space_unwrap(space
);
91 space2
= isl_space_domain(isl_space_copy(space
));
92 ma
= isl_multi_aff_identity(isl_space_map_from_set(space2
));
94 space
= isl_space_insert_dims(space
, isl_dim_param
, 0,
96 for (i
= 0; i
< expr
->n_arg
; ++i
) {
97 isl_id
*id
= isl_id_alloc(ctx
, NULL
, expr
->args
[i
]);
99 space
= isl_space_set_dim_id(space
, isl_dim_param
, i
, id
);
101 space2
= isl_space_domain(isl_space_copy(space
));
102 ls
= isl_local_space_from_space(space2
);
103 ma2
= isl_multi_aff_zero(space
);
104 for (i
= 0; i
< expr
->n_arg
; ++i
) {
106 aff
= isl_aff_var_on_domain(isl_local_space_copy(ls
),
108 ma2
= isl_multi_aff_set_aff(ma2
, i
, aff
);
110 isl_local_space_free(ls
);
112 ma
= isl_multi_aff_range_product(ma
, ma2
);
114 return isl_multi_pw_aff_pullback_multi_aff(index
, ma
);
117 static __isl_give isl_ast_expr
*pet_expr_build_ast_expr(
118 __isl_keep pet_expr
*expr
, struct pet_build_ast_expr_data
*data
);
120 /* Construct an associative array from identifiers for the nested
121 * expressions of "expr" to the corresponding isl_ast_expr.
122 * The identifiers reference the corresponding arguments of "expr".
123 * The same identifiers are used in parametrize_nested_exprs.
125 static __isl_give isl_id_to_ast_expr
*pet_expr_build_nested_ast_exprs(
126 __isl_keep pet_expr
*expr
, struct pet_build_ast_expr_data
*data
)
129 isl_ctx
*ctx
= isl_ast_build_get_ctx(data
->build
);
130 isl_id_to_ast_expr
*id2expr
;
132 id2expr
= isl_id_to_ast_expr_alloc(ctx
, expr
->n_arg
);
134 for (i
= 0; i
< expr
->n_arg
; ++i
) {
135 isl_id
*id
= isl_id_alloc(ctx
, NULL
, expr
->args
[i
]);
136 isl_ast_expr
*ast_expr
;
138 ast_expr
= pet_expr_build_ast_expr(expr
->args
[i
], data
);
139 id2expr
= isl_id_to_ast_expr_set(id2expr
, id
, ast_expr
);
145 /* Construct an AST expression from an access expression.
147 * If the expression has any arguments, we first convert those
148 * to AST expressions and replace the references to those arguments
149 * in the index expression by parameters.
151 * Then we apply the index transformation if any was provided by the user.
153 * If the "access" is actually an affine expression, we print is as such.
154 * Otherwise, we print a proper access.
156 * If the original expression had any arguments, then they are plugged in now.
158 * Finally, we apply an AST transformation on the result, if any was provided
161 static __isl_give isl_ast_expr
*pet_expr_build_ast_expr(
162 __isl_keep pet_expr
*expr
, struct pet_build_ast_expr_data
*data
)
165 isl_multi_pw_aff
*mpa
;
166 isl_ast_expr
*ast_expr
;
167 isl_id_to_ast_expr
*id2expr
;
168 isl_ast_build
*build
= data
->build
;
172 if (expr
->type
!= pet_expr_access
)
173 isl_die(isl_ast_build_get_ctx(build
), isl_error_invalid
,
174 "not an access expression", return NULL
);
176 mpa
= isl_multi_pw_aff_copy(expr
->acc
.index
);
178 if (expr
->n_arg
> 0) {
179 mpa
= parametrize_nested_exprs(mpa
, expr
);
180 id2expr
= pet_expr_build_nested_ast_exprs(expr
, data
);
184 mpa
= data
->fn_index(mpa
, expr
->acc
.ref_id
, data
->user_index
);
185 mpa
= isl_multi_pw_aff_coalesce(mpa
);
187 if (!pet_expr_is_affine(expr
)) {
188 ast_expr
= isl_ast_build_access_from_multi_pw_aff(build
, mpa
);
190 pa
= isl_multi_pw_aff_get_pw_aff(mpa
, 0);
191 ast_expr
= isl_ast_build_expr_from_pw_aff(build
, pa
);
192 isl_multi_pw_aff_free(mpa
);
195 ast_expr
= isl_ast_expr_substitute_ids(ast_expr
, id2expr
);
197 ast_expr
= data
->fn_expr(ast_expr
, expr
->acc
.ref_id
,
203 /* Construct an AST expression from the access expression "expr" and
204 * add the mapping from reference identifier to AST expression to
207 static int add_access(__isl_keep pet_expr
*expr
, void *user
)
209 struct pet_build_ast_expr_data
*data
= user
;
211 isl_ast_expr
*ast_expr
;
213 ast_expr
= pet_expr_build_ast_expr(expr
, data
);
215 id
= isl_id_copy(expr
->acc
.ref_id
);
216 data
->ref2expr
= isl_id_to_ast_expr_set(data
->ref2expr
, id
, ast_expr
);
221 /* Construct an associative array from reference identifiers of
222 * access expressions in "stmt" to the corresponding isl_ast_expr.
223 * Each index expression is first transformed through "fn_index"
224 * (if not NULL). Then an AST expression is generated using "build".
225 * Finally, the AST expression is transformed using "fn_expr"
228 __isl_give isl_id_to_ast_expr
*pet_stmt_build_ast_exprs(struct pet_stmt
*stmt
,
229 __isl_keep isl_ast_build
*build
,
230 __isl_give isl_multi_pw_aff
*(*fn_index
)(
231 __isl_take isl_multi_pw_aff
*mpa
, __isl_keep isl_id
*id
,
232 void *user
), void *user_index
,
233 __isl_give isl_ast_expr
*(*fn_expr
)(__isl_take isl_ast_expr
*expr
,
234 __isl_keep isl_id
*id
, void *user
), void *user_expr
)
236 struct pet_build_ast_expr_data data
=
237 { build
, fn_index
, user_index
, fn_expr
, user_expr
};
243 ctx
= isl_ast_build_get_ctx(build
);
244 data
.ref2expr
= isl_id_to_ast_expr_alloc(ctx
, 0);
245 if (pet_expr_foreach_access_expr(stmt
->body
, &add_access
, &data
) < 0)
246 data
.ref2expr
= isl_id_to_ast_expr_free(data
.ref2expr
);
248 return data
.ref2expr
;
251 /* Print the access expression "expr" to "p".
253 * We look up the corresponding isl_ast_expr in "ref2expr"
254 * and print that to "p".
256 static __isl_give isl_printer
*print_access(__isl_take isl_printer
*p
,
257 __isl_keep pet_expr
*expr
, __isl_keep isl_id_to_ast_expr
*ref2expr
)
259 isl_ast_expr
*ast_expr
;
262 if (!isl_id_to_ast_expr_has(ref2expr
, expr
->acc
.ref_id
))
263 isl_die(isl_printer_get_ctx(p
), isl_error_internal
,
264 "missing expression", return isl_printer_free(p
));
266 ast_expr
= isl_id_to_ast_expr_get(ref2expr
,
267 isl_id_copy(expr
->acc
.ref_id
));
268 is_access
= isl_ast_expr_get_type(ast_expr
) == isl_ast_expr_op
&&
269 isl_ast_expr_get_op_type(ast_expr
) == isl_ast_op_access
;
271 p
= isl_printer_print_str(p
, "(");
272 p
= isl_printer_print_ast_expr(p
, ast_expr
);
274 p
= isl_printer_print_str(p
, ")");
275 isl_ast_expr_free(ast_expr
);
280 /* Is "op" a postfix operator?
282 static int is_postfix(enum pet_op_type op
)
285 case pet_op_post_inc
:
286 case pet_op_post_dec
:
293 static __isl_give isl_printer
*print_pet_expr(__isl_take isl_printer
*p
,
294 __isl_keep pet_expr
*expr
, int outer
,
295 __isl_keep isl_id_to_ast_expr
*ref2expr
);
297 /* Print operation expression "expr" to "p".
299 * The access subexpressions are replaced by the isl_ast_expr
300 * associated to its reference identifier in "ref2expr".
302 static __isl_give isl_printer
*print_op(__isl_take isl_printer
*p
,
303 __isl_keep pet_expr
*expr
, __isl_keep isl_id_to_ast_expr
*ref2expr
)
305 switch (expr
->n_arg
) {
307 if (!is_postfix(expr
->op
))
308 p
= isl_printer_print_str(p
, pet_op_str(expr
->op
));
309 p
= print_pet_expr(p
, expr
->args
[pet_un_arg
], 0, ref2expr
);
310 if (is_postfix(expr
->op
))
311 p
= isl_printer_print_str(p
, pet_op_str(expr
->op
));
314 p
= print_pet_expr(p
, expr
->args
[pet_bin_lhs
], 0,
316 p
= isl_printer_print_str(p
, " ");
317 p
= isl_printer_print_str(p
, pet_op_str(expr
->op
));
318 p
= isl_printer_print_str(p
, " ");
319 p
= print_pet_expr(p
, expr
->args
[pet_bin_rhs
], 0,
323 p
= print_pet_expr(p
, expr
->args
[pet_ter_cond
], 0,
325 p
= isl_printer_print_str(p
, " ? ");
326 p
= print_pet_expr(p
, expr
->args
[pet_ter_true
], 0,
328 p
= isl_printer_print_str(p
, " : ");
329 p
= print_pet_expr(p
, expr
->args
[pet_ter_false
], 0,
337 /* Print "expr" to "p".
339 * If "outer" is set, then we are printing the outer expression statement.
341 * The access subexpressions are replaced by the isl_ast_expr
342 * associated to its reference identifier in "ref2expr".
344 static __isl_give isl_printer
*print_pet_expr(__isl_take isl_printer
*p
,
345 __isl_keep pet_expr
*expr
, int outer
,
346 __isl_keep isl_id_to_ast_expr
*ref2expr
)
350 switch (expr
->type
) {
352 p
= isl_printer_free(p
);
355 p
= isl_printer_print_val(p
, expr
->i
);
357 case pet_expr_double
:
358 p
= isl_printer_print_str(p
, expr
->d
.s
);
360 case pet_expr_access
:
361 p
= print_access(p
, expr
, ref2expr
);
365 p
= isl_printer_print_str(p
, "(");
366 p
= print_op(p
, expr
, ref2expr
);
368 p
= isl_printer_print_str(p
, ")");
371 p
= isl_printer_print_str(p
, expr
->name
);
372 p
= isl_printer_print_str(p
, "(");
373 for (i
= 0; i
< expr
->n_arg
; ++i
) {
375 p
= isl_printer_print_str(p
, ", ");
376 p
= print_pet_expr(p
, expr
->args
[i
], 1, ref2expr
);
378 p
= isl_printer_print_str(p
, ")");
382 p
= isl_printer_print_str(p
, "(");
383 p
= isl_printer_print_str(p
, "(");
384 p
= isl_printer_print_str(p
, expr
->type_name
);
385 p
= isl_printer_print_str(p
, ") ");
386 p
= print_pet_expr(p
, expr
->args
[0], 0, ref2expr
);
388 p
= isl_printer_print_str(p
, ")");
395 /* Print "stmt" to "p".
397 * The access expressions in "stmt" are replaced by the isl_ast_expr
398 * associated to its reference identifier in "ref2expr".
400 * If the statement is an assume statement, then we print nothing.
402 __isl_give isl_printer
*pet_stmt_print_body(struct pet_stmt
*stmt
,
403 __isl_take isl_printer
*p
, __isl_keep isl_id_to_ast_expr
*ref2expr
)
406 return isl_printer_free(p
);
407 if (pet_stmt_is_assume(stmt
))
409 p
= isl_printer_start_line(p
);
410 p
= print_pet_expr(p
, stmt
->body
, 1, ref2expr
);
411 p
= isl_printer_print_str(p
, ";");
412 p
= isl_printer_end_line(p
);
417 /* Copy the contents of "input" from offset "start" to "end" to "output".
419 int copy(FILE *input
, FILE *output
, long start
, long end
)
425 fseek(input
, 0, SEEK_END
);
429 fseek(input
, start
, SEEK_SET
);
431 while (start
< end
) {
435 n
= fread(buffer
, 1, n
, input
);
438 m
= fwrite(buffer
, 1, n
, output
);