pet_scop_from_pet_tree: create statements directly from expression trees
[pet.git] / expr_arg.c
blob49820b454f284f173e98e64f057dda208e2c1495
1 /*
2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2014 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
7 * are met:
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
32 * Leiden University.
35 #include "context.h"
36 #include "expr.h"
37 #include "expr_arg.h"
39 /* Equate the arguments "pos1" and "pos2" of the access expression "expr".
41 * We may assume that "pos1" is smaller than "pos2".
42 * We replace all references to the argument at position "pos2"
43 * to references to the argument at position "pos1" (leaving all other
44 * variables untouched) and then drop argument "pos2".
46 static __isl_give pet_expr *equate_arg(__isl_take pet_expr *expr, int pos1,
47 int pos2)
49 int in;
50 isl_space *space;
51 isl_multi_aff *ma;
53 if (!expr)
54 return NULL;
55 if (pos1 == pos2)
56 return expr;
57 if (pos1 > pos2)
58 return equate_arg(expr, pos2, pos1);
59 if (pos1 < 0 || pos2 >= expr->n_arg)
60 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
61 "position out of bounds", return pet_expr_free(expr));
63 space = isl_multi_pw_aff_get_domain_space(expr->acc.index);
64 space = isl_space_unwrap(space);
65 in = isl_space_dim(space, isl_dim_in);
66 isl_space_free(space);
68 pos1 += in;
69 pos2 += in;
70 space = isl_multi_pw_aff_get_domain_space(expr->acc.index);
71 space = isl_space_map_from_set(space);
72 ma = isl_multi_aff_identity(space);
73 ma = isl_multi_aff_set_aff(ma, pos2, isl_multi_aff_get_aff(ma, pos1));
74 expr = pet_expr_access_pullback_multi_aff(expr, ma);
75 expr = pet_expr_access_project_out_arg(expr, in, pos2 - in);
77 return expr;
80 /* Remove all arguments of the access expression "expr" that are duplicates
81 * of earlier arguments.
83 __isl_give pet_expr *pet_expr_remove_duplicate_args(__isl_take pet_expr *expr)
85 int i, j;
87 if (!expr)
88 return NULL;
89 if (expr->n_arg < 2)
90 return expr;
92 for (i = expr->n_arg - 1; i >= 0; --i) {
93 for (j = 0; j < i; ++j)
94 if (pet_expr_is_equal(expr->args[i], expr->args[j]))
95 break;
96 if (j >= i)
97 continue;
98 expr = equate_arg(expr, j, i);
99 if (!expr)
100 return NULL;
103 return expr;
106 /* Insert argument "arg" at position "pos" in the arguments
107 * of access expression "expr".
109 * Besides actually inserting the argument, we also need to make
110 * sure that we adjust the references to the original arguments.
112 * If "expr" has no arguments to start with, then its domain is of the form
114 * S[i]
116 * otherwise, it is of the form
118 * [S[i] -> [args]]
120 * In the first case, we compute the pullback over
122 * [S[i] -> [arg]] -> S[i]
124 * In the second case, we compute the pullback over
126 * [S[i] -> [args_before_pos,arg,args_after_pos]] -> [S[i] -> [args]]
128 __isl_give pet_expr *pet_expr_insert_arg(__isl_take pet_expr *expr, int pos,
129 __isl_take pet_expr *arg)
131 int i, n;
132 isl_space *space;
133 isl_multi_aff *ma;
135 if (!expr || !arg)
136 goto error;
137 if (expr->type != pet_expr_access)
138 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
139 "not an access pet_expr", goto error);
141 n = pet_expr_get_n_arg(expr);
142 if (pos < 0 || pos > n)
143 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
144 "position out of bounds", goto error);
146 expr = pet_expr_set_n_arg(expr, n + 1);
147 for (i = n; i > pos; --i)
148 pet_expr_set_arg(expr, i, pet_expr_get_arg(expr, i - 1));
149 expr = pet_expr_set_arg(expr, pos, arg);
151 space = isl_space_domain(isl_multi_pw_aff_get_space(expr->acc.index));
152 if (isl_space_is_wrapping(space))
153 space = isl_space_domain(isl_space_unwrap(space));
154 space = isl_space_from_domain(space);
155 space = isl_space_add_dims(space, isl_dim_out, n + 1);
157 if (n == 0) {
158 ma = isl_multi_aff_domain_map(space);
159 } else {
160 isl_multi_aff *ma2, *proj;
162 ma = isl_multi_aff_domain_map(isl_space_copy(space));
163 ma2 = isl_multi_aff_range_map(space);
164 space = isl_space_range(isl_multi_aff_get_space(ma2));
165 proj = isl_multi_aff_project_out_map(space,
166 isl_dim_set, pos, 1);
167 ma2 = isl_multi_aff_pullback_multi_aff(proj, ma2);
168 ma = isl_multi_aff_range_product(ma, ma2);
171 expr = pet_expr_access_pullback_multi_aff(expr, ma);
173 return expr;
174 error:
175 pet_expr_free(expr);
176 pet_expr_free(arg);
177 return NULL;
180 /* Remove the argument at position "pos" in the arguments
181 * of access expression "expr", making sure it is not referenced
182 * from the index expression.
183 * "dim" is the dimension of the iteration domain.
185 * Besides actually removing the argument, we also need to make sure that
186 * we eliminate any reference from the access relation and that
187 * we adjust the references to the remaining arguments.
189 * If "expr" has a single argument, then we compute the pullback over
191 * S[i] -> [S[i] -> [arg]]
193 * Otherwise, we compute the pullback over
195 * [S[i] -> [args]] -> [S[i] -> [args_before_pos,args_after_pos]]
197 __isl_give pet_expr *pet_expr_access_project_out_arg(__isl_take pet_expr *expr,
198 int dim, int pos)
200 int i, n;
201 isl_space *space, *dom, *ran;
202 isl_multi_aff *ma1, *ma2;
204 expr = pet_expr_cow(expr);
205 if (!expr)
206 return NULL;
207 if (expr->type != pet_expr_access)
208 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
209 "not an access pet_expr", return pet_expr_free(expr));
210 n = pet_expr_get_n_arg(expr);
211 if (pos < 0 || pos >= n)
212 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
213 "position out of bounds", return pet_expr_free(expr));
215 if (isl_multi_pw_aff_involves_dims(expr->acc.index,
216 isl_dim_in, dim + pos, 1))
217 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
218 "cannot project out", return pet_expr_free(expr));
219 expr->acc.access = isl_map_eliminate(expr->acc.access,
220 isl_dim_in, dim + pos, 1);
221 if (!expr->acc.access || !expr->acc.index)
222 return pet_expr_free(expr);
224 space = isl_multi_pw_aff_get_domain_space(expr->acc.index);
225 space = isl_space_unwrap(space);
226 dom = isl_space_map_from_set(isl_space_domain(isl_space_copy(space)));
227 ma1 = isl_multi_aff_identity(dom);
228 if (n == 1) {
229 ma2 = isl_multi_aff_zero(space);
230 ma1 = isl_multi_aff_range_product(ma1, ma2);
231 } else {
232 ran = isl_space_map_from_set(isl_space_range(space));
233 ma2 = isl_multi_aff_identity(ran);
234 ma2 = isl_multi_aff_drop_dims(ma2, isl_dim_in, pos, 1);
235 ma1 = isl_multi_aff_product(ma1, ma2);
238 expr = pet_expr_access_pullback_multi_aff(expr, ma1);
239 if (!expr)
240 return NULL;
241 pet_expr_free(expr->args[pos]);
242 for (i = pos; i + 1 < n; ++i)
243 expr->args[i] = expr->args[i + 1];
244 expr->n_arg = n - 1;
246 return expr;
249 /* Plug in "value" for the argument at position "pos" of "expr".
251 * The input "value" is of the form
253 * S[i] -> [value(i)]
255 * while the index expression of "expr" has domain
257 * [S[i] -> [args]]
259 * We therefore first pullback "value" to this domain, resulting in
261 * [S[i] -> [args]] -> [value(i)]
263 * Then we compute the pullback of "expr" over
265 * [S[i] -> [args]] -> [S[i] -> [args_before_pos,value(i),args_after_pos]]
267 * and drop the now redundant argument at position "pos".
269 static __isl_give pet_expr *plug_in(__isl_take pet_expr *expr, int pos,
270 __isl_take isl_pw_aff *value)
272 int n_in;
273 isl_space *space;
274 isl_multi_aff *ma;
275 isl_multi_pw_aff *mpa;
277 space = isl_multi_pw_aff_get_space(expr->acc.index);
278 space = isl_space_unwrap(isl_space_domain(space));
279 n_in = isl_space_dim(space, isl_dim_in);
280 ma = isl_multi_aff_domain_map(space);
281 value = isl_pw_aff_pullback_multi_aff(value, ma);
283 space = isl_multi_pw_aff_get_space(expr->acc.index);
284 space = isl_space_map_from_set(isl_space_domain(space));
285 mpa = isl_multi_pw_aff_identity(space);
286 mpa = isl_multi_pw_aff_set_pw_aff(mpa, n_in + pos, value);
288 expr = pet_expr_access_pullback_multi_pw_aff(expr, mpa);
289 expr = pet_expr_access_project_out_arg(expr, n_in, pos);
291 return expr;
294 /* Given that the argument of "expr" at position "pos" is a sum
295 * of two expressions, replace references to this argument by the sum
296 * of references to the two expressions.
297 * "dim" is the dimension of the iteration domain.
299 * That is, replace
301 * [S[i] -> [args]] -> [f(i,args_before_pos,arg_pos,args_after_pos)]
303 * by
305 * [S[i] -> [args_before_pos,arg0,arg1,args_after_pos]] ->
306 * [f(i, args_before_pos, arg0 + arg1, args_after_pos)]
308 * where arg0 and arg1 refer to the arguments of the sum expression
309 * that the original arg_pos referred to.
311 * We introduce (an unreferenced) arg1 and replace arg_pos by arg0
312 * in the arguments and then we compute the pullback over
314 * [S[i] -> [args_before_pos,arg0,arg1,args_after_pos]] ->
315 * [S[i] -> [args_before_pos,arg0+arg1,arg1,args_after_pos]]
317 static __isl_give pet_expr *splice_sum(__isl_take pet_expr *expr, int dim,
318 int pos)
320 isl_space *space;
321 pet_expr *arg;
322 isl_multi_aff *ma;
323 isl_aff *aff1, *aff2;
325 arg = expr->args[pos];
326 expr = pet_expr_insert_arg(expr, pos + 1, pet_expr_get_arg(arg, 1));
327 expr = pet_expr_set_arg(expr, pos, pet_expr_get_arg(arg, 0));
328 if (!expr)
329 return NULL;
331 space = isl_multi_pw_aff_get_space(expr->acc.index);
332 space = isl_space_map_from_set(isl_space_domain(space));
333 ma = isl_multi_aff_identity(space);
334 aff1 = isl_multi_aff_get_aff(ma, dim + pos);
335 aff2 = isl_multi_aff_get_aff(ma, dim + pos + 1);
336 aff1 = isl_aff_add(aff1, aff2);
337 ma = isl_multi_aff_set_aff(ma, dim + pos, aff1);
339 expr = pet_expr_access_pullback_multi_aff(expr, ma);
341 return expr;
344 /* Try and integrate the arguments of "expr" into the index expression
345 * of "expr" by trying to convert the arguments to affine expressions.
346 * "pc" is the context in which the affine expressions are created.
348 * For example, given an access expression with index expression
350 * [S[i] -> [arg0]] -> A[arg0]
352 * where the first argument is itself an access to a variable "i"
353 * that is assigned the value
355 * S[i] -> [i]
357 * by "pc", this value is plugged into
358 * the index expression of "expr", resulting in
360 * [i] -> { S[] -> A[i] }
361 * S[i] -> A[i]
364 * In particular, we first remove duplicate arguments so that we
365 * only need to convert a given expression once.
367 * Then we try and convert the arguments to affine expressions and
368 * (if successful) we plug them into the index expression.
370 * Occasionally, we may be unable to convert an entire argument, while
371 * we could convert a sub-argument. In particular, this may happen
372 * if the top-level argument is an addition of two expressions
373 * of which only one can be converted to an affine expression.
374 * We therefore replace a reference to a "+" argument by the sum
375 * of references to the summands.
377 __isl_give pet_expr *pet_expr_access_plug_in_args(__isl_take pet_expr *expr,
378 __isl_keep pet_context *pc)
380 int i, n;
382 expr = pet_expr_remove_duplicate_args(expr);
383 if (!expr)
384 return NULL;
385 if (expr->type != pet_expr_access)
386 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
387 "not an access pet_expr", return pet_expr_free(expr));
389 n = pet_expr_get_n_arg(expr);
390 if (n == 0)
391 return expr;
393 for (i = n - 1; expr && i >= 0; --i) {
394 isl_pw_aff *pa;
395 pet_expr *arg = expr->args[i];
397 pa = pet_expr_extract_affine(arg, pc);
398 if (!pa)
399 return pet_expr_free(expr);
400 if (!isl_pw_aff_involves_nan(pa)) {
401 expr = plug_in(expr, i, pa);
402 continue;
404 isl_pw_aff_free(pa);
406 if (pet_expr_get_type(arg) == pet_expr_op &&
407 pet_expr_op_get_type(arg) == pet_op_add) {
408 int dim = pet_context_dim(pc);
409 expr = splice_sum(expr, dim, i);
410 i += 2;
414 return expr;
417 /* A wrapper around pet_expr_access_plug_in_args for use
418 * as a pet_expr_map_access callback.
420 static __isl_give pet_expr *plug_in_args(__isl_take pet_expr *expr, void *user)
422 struct pet_context *pc = user;
423 return pet_expr_access_plug_in_args(expr, pc);
426 /* For each access subexpression of "expr", try and integrate its arguments in
427 * its index expression by trying to convert the arguments
428 * to affine expressions.
429 * "pc" is the context in which the affine expressions are created.
431 __isl_give pet_expr *pet_expr_plug_in_args(__isl_take pet_expr *expr,
432 __isl_keep pet_context *pc)
434 return pet_expr_map_access(expr, &plug_in_args, pc);