pet_expr_access_set_access: set read/write on non-empty access relation
[pet.git] / expr_arg.c
blobebea83b03e36643e533d6c4ca8124238e26f38b3
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 (if any) 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;
203 enum pet_expr_access_type type;
204 isl_map *map;
205 isl_union_map *umap;
207 expr = pet_expr_cow(expr);
208 if (!expr)
209 return NULL;
210 if (expr->type != pet_expr_access)
211 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
212 "not an access pet_expr", return pet_expr_free(expr));
213 n = pet_expr_get_n_arg(expr);
214 if (pos < 0 || pos >= n)
215 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
216 "position out of bounds", return pet_expr_free(expr));
218 if (isl_multi_pw_aff_involves_dims(expr->acc.index,
219 isl_dim_in, dim + pos, 1))
220 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
221 "cannot project out", return pet_expr_free(expr));
222 space = isl_multi_pw_aff_get_domain_space(expr->acc.index);
223 map = isl_map_identity(isl_space_map_from_set(space));
224 map = isl_map_eliminate(map, isl_dim_out, dim + pos, 1);
225 umap = isl_union_map_from_map(map);
226 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
227 if (!expr->acc.access[type])
228 continue;
229 expr->acc.access[type] =
230 isl_union_map_apply_domain(expr->acc.access[type],
231 isl_union_map_copy(umap));
232 if (!expr->acc.access[type])
233 break;
235 isl_union_map_free(umap);
236 if (!expr->acc.index || type < pet_expr_access_end)
237 return pet_expr_free(expr);
239 space = isl_multi_pw_aff_get_domain_space(expr->acc.index);
240 space = isl_space_unwrap(space);
241 dom = isl_space_map_from_set(isl_space_domain(isl_space_copy(space)));
242 ma1 = isl_multi_aff_identity(dom);
243 if (n == 1) {
244 ma2 = isl_multi_aff_zero(space);
245 ma1 = isl_multi_aff_range_product(ma1, ma2);
246 } else {
247 ran = isl_space_map_from_set(isl_space_range(space));
248 ma2 = isl_multi_aff_identity(ran);
249 ma2 = isl_multi_aff_drop_dims(ma2, isl_dim_in, pos, 1);
250 ma1 = isl_multi_aff_product(ma1, ma2);
253 expr = pet_expr_access_pullback_multi_aff(expr, ma1);
254 if (!expr)
255 return NULL;
256 pet_expr_free(expr->args[pos]);
257 for (i = pos; i + 1 < n; ++i)
258 expr->args[i] = expr->args[i + 1];
259 expr->n_arg = n - 1;
261 return expr;
264 /* Plug in "value" for the argument at position "pos" of "expr".
266 * The input "value" is of the form
268 * S[i] -> [value(i)]
270 * while the index expression of "expr" has domain
272 * [S[i] -> [args]]
274 * We therefore first pullback "value" to this domain, resulting in
276 * [S[i] -> [args]] -> [value(i)]
278 * Then we compute the pullback of "expr" over
280 * [S[i] -> [args]] -> [S[i] -> [args_before_pos,value(i),args_after_pos]]
282 * and drop the now redundant argument at position "pos".
284 static __isl_give pet_expr *plug_in(__isl_take pet_expr *expr, int pos,
285 __isl_take isl_pw_aff *value)
287 int n_in;
288 isl_space *space;
289 isl_multi_aff *ma;
290 isl_multi_pw_aff *mpa;
292 space = isl_multi_pw_aff_get_space(expr->acc.index);
293 space = isl_space_unwrap(isl_space_domain(space));
294 n_in = isl_space_dim(space, isl_dim_in);
295 ma = isl_multi_aff_domain_map(space);
296 value = isl_pw_aff_pullback_multi_aff(value, ma);
298 space = isl_multi_pw_aff_get_space(expr->acc.index);
299 space = isl_space_map_from_set(isl_space_domain(space));
300 mpa = isl_multi_pw_aff_identity(space);
301 mpa = isl_multi_pw_aff_set_pw_aff(mpa, n_in + pos, value);
303 expr = pet_expr_access_pullback_multi_pw_aff(expr, mpa);
304 expr = pet_expr_access_project_out_arg(expr, n_in, pos);
306 return expr;
309 /* Given that the argument of "expr" at position "pos" is a sum
310 * of two expressions, replace references to this argument by the sum
311 * of references to the two expressions.
312 * "dim" is the dimension of the iteration domain.
314 * That is, replace
316 * [S[i] -> [args]] -> [f(i,args_before_pos,arg_pos,args_after_pos)]
318 * by
320 * [S[i] -> [args_before_pos,arg0,arg1,args_after_pos]] ->
321 * [f(i, args_before_pos, arg0 + arg1, args_after_pos)]
323 * where arg0 and arg1 refer to the arguments of the sum expression
324 * that the original arg_pos referred to.
326 * We introduce (an unreferenced) arg1 and replace arg_pos by arg0
327 * in the arguments and then we compute the pullback over
329 * [S[i] -> [args_before_pos,arg0,arg1,args_after_pos]] ->
330 * [S[i] -> [args_before_pos,arg0+arg1,arg1,args_after_pos]]
332 static __isl_give pet_expr *splice_sum(__isl_take pet_expr *expr, int dim,
333 int pos)
335 isl_space *space;
336 pet_expr *arg;
337 isl_multi_aff *ma;
338 isl_aff *aff1, *aff2;
340 arg = expr->args[pos];
341 expr = pet_expr_insert_arg(expr, pos + 1, pet_expr_get_arg(arg, 1));
342 expr = pet_expr_set_arg(expr, pos, pet_expr_get_arg(arg, 0));
343 if (!expr)
344 return NULL;
346 space = isl_multi_pw_aff_get_space(expr->acc.index);
347 space = isl_space_map_from_set(isl_space_domain(space));
348 ma = isl_multi_aff_identity(space);
349 aff1 = isl_multi_aff_get_aff(ma, dim + pos);
350 aff2 = isl_multi_aff_get_aff(ma, dim + pos + 1);
351 aff1 = isl_aff_add(aff1, aff2);
352 ma = isl_multi_aff_set_aff(ma, dim + pos, aff1);
354 expr = pet_expr_access_pullback_multi_aff(expr, ma);
356 return expr;
359 /* Try and integrate the arguments of "expr" into the index expression
360 * of "expr" by trying to convert the arguments to affine expressions.
361 * "pc" is the context in which the affine expressions are created.
363 * For example, given an access expression with index expression
365 * [S[i] -> [arg0]] -> A[arg0]
367 * where the first argument is itself an access to a variable "i"
368 * that is assigned the value
370 * S[i] -> [i]
372 * by "pc", this value is plugged into
373 * the index expression of "expr", resulting in
375 * [i] -> { S[] -> A[i] }
376 * S[i] -> A[i]
379 * In particular, we first remove duplicate arguments so that we
380 * only need to convert a given expression once.
382 * Then we try and convert the arguments to affine expressions and
383 * (if successful) we plug them into the index expression.
385 * Occasionally, we may be unable to convert an entire argument, while
386 * we could convert a sub-argument. In particular, this may happen
387 * if the top-level argument is an addition of two expressions
388 * of which only one can be converted to an affine expression.
389 * We therefore replace a reference to a "+" argument by the sum
390 * of references to the summands.
392 __isl_give pet_expr *pet_expr_access_plug_in_args(__isl_take pet_expr *expr,
393 __isl_keep pet_context *pc)
395 int i, n;
397 expr = pet_expr_remove_duplicate_args(expr);
398 if (!expr)
399 return NULL;
400 if (expr->type != pet_expr_access)
401 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
402 "not an access pet_expr", return pet_expr_free(expr));
404 n = pet_expr_get_n_arg(expr);
405 if (n == 0)
406 return expr;
408 for (i = n - 1; expr && i >= 0; --i) {
409 isl_pw_aff *pa;
410 pet_expr *arg = expr->args[i];
412 pa = pet_expr_extract_affine(arg, pc);
413 if (!pa)
414 return pet_expr_free(expr);
415 if (!isl_pw_aff_involves_nan(pa)) {
416 expr = plug_in(expr, i, pa);
417 continue;
419 isl_pw_aff_free(pa);
421 if (pet_expr_get_type(arg) == pet_expr_op &&
422 pet_expr_op_get_type(arg) == pet_op_add) {
423 int dim = pet_context_dim(pc);
424 expr = splice_sum(expr, dim, i);
425 i += 2;
429 return expr;
432 /* A wrapper around pet_expr_access_plug_in_args for use
433 * as a pet_expr_map_access callback.
435 static __isl_give pet_expr *plug_in_args(__isl_take pet_expr *expr, void *user)
437 struct pet_context *pc = user;
438 return pet_expr_access_plug_in_args(expr, pc);
441 /* For each access subexpression of "expr", try and integrate its arguments in
442 * its index expression by trying to convert the arguments
443 * to affine expressions.
444 * "pc" is the context in which the affine expressions are created.
446 __isl_give pet_expr *pet_expr_plug_in_args(__isl_take pet_expr *expr,
447 __isl_keep pet_context *pc)
449 return pet_expr_map_access(expr, &plug_in_args, pc);