1 /*
2 * Copyright 2011 Leiden University. All rights reserved.
3 * Copyright 2012-2014 Ecole Normale Superieure. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
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.
16 *
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.
28 *
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.
33 */
34
35 #include "context.h"
36 #include "expr.h"
37 #include "expr_arg.h"
38
39 /* Equate the arguments "pos1" and "pos2" of the access expression "expr".
40 *
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".
45 */
equate_arg(__isl_take pet_expr * expr,int pos1,int pos2)46 static __isl_give pet_expr *equate_arg(__isl_take pet_expr *expr, int pos1,
47 int pos2)
48 {
49 int in;
50 isl_space *space;
51 isl_multi_aff *ma;
52
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));
62
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);
67
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);
76
77 return expr;
78 }
79
80 /* Remove all arguments of the access expression "expr" that are duplicates
81 * of earlier arguments.
82 */
pet_expr_remove_duplicate_args(__isl_take pet_expr * expr)83 __isl_give pet_expr *pet_expr_remove_duplicate_args(__isl_take pet_expr *expr)
84 {
85 int i, j;
86
87 if (!expr)
88 return NULL;
89 if (expr->n_arg < 2)
90 return expr;
91
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;
101 }
102
103 return expr;
104 }
105
106 /* Insert argument "arg" at position "pos" in the arguments
107 * of access expression "expr".
108 *
109 * Besides actually inserting the argument, we also need to make
110 * sure that we adjust the references to the original arguments.
111 *
112 * If "expr" has no arguments to start with, then its domain is of the form
113 *
114 * S[i]
115 *
116 * otherwise, it is of the form
117 *
118 * [S[i] -> [args]]
119 *
120 * In the first case, we compute the pullback over
121 *
122 * [S[i] -> [arg]] -> S[i]
123 *
124 * In the second case, we compute the pullback over
125 *
126 * [S[i] -> [args_before_pos,arg,args_after_pos]] -> [S[i] -> [args]]
127 */
pet_expr_insert_arg(__isl_take pet_expr * expr,int pos,__isl_take pet_expr * arg)128 __isl_give pet_expr *pet_expr_insert_arg(__isl_take pet_expr *expr, int pos,
129 __isl_take pet_expr *arg)
130 {
131 int i, n;
132 isl_space *space;
133 isl_multi_aff *ma;
134
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);
140
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);
145
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);
150
151 space = pet_expr_access_get_domain_space(expr);
152 space = isl_space_from_domain(space);
153 space = isl_space_add_dims(space, isl_dim_out, n + 1);
154
155 if (n == 0) {
156 ma = isl_multi_aff_domain_map(space);
157 } else {
158 isl_multi_aff *ma2, *proj;
159
160 ma = isl_multi_aff_domain_map(isl_space_copy(space));
161 ma2 = isl_multi_aff_range_map(space);
162 space = isl_space_range(isl_multi_aff_get_space(ma2));
163 proj = isl_multi_aff_project_out_map(space,
164 isl_dim_set, pos, 1);
165 ma2 = isl_multi_aff_pullback_multi_aff(proj, ma2);
166 ma = isl_multi_aff_range_product(ma, ma2);
167 }
168
169 expr = pet_expr_access_pullback_multi_aff(expr, ma);
170
171 return expr;
172 error:
173 pet_expr_free(expr);
174 pet_expr_free(arg);
175 return NULL;
176 }
177
178 /* Remove the argument at position "pos" in the arguments
179 * of access expression "expr", making sure it is not referenced
180 * from the index expression.
181 * "dim" is the dimension of the iteration domain.
182 *
183 * Besides actually removing the argument, we also need to make sure that
184 * we eliminate any reference from the access relation (if any) and that
185 * we adjust the references to the remaining arguments.
186 *
187 * If "expr" has a single argument, then we compute the pullback over
188 *
189 * S[i] -> [S[i] -> [arg]]
190 *
191 * Otherwise, we compute the pullback over
192 *
193 * [S[i] -> [args]] -> [S[i] -> [args_before_pos,args_after_pos]]
194 */
pet_expr_access_project_out_arg(__isl_take pet_expr * expr,int dim,int pos)195 __isl_give pet_expr *pet_expr_access_project_out_arg(__isl_take pet_expr *expr,
196 int dim, int pos)
197 {
198 int i, n;
199 isl_bool involves;
200 isl_space *space, *dom, *ran;
201 isl_multi_aff *ma1, *ma2;
202 enum pet_expr_access_type type;
203 isl_map *map;
204 isl_union_map *umap;
205
206 expr = pet_expr_cow(expr);
207 if (!expr)
208 return NULL;
209 if (expr->type != pet_expr_access)
210 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
211 "not an access pet_expr", return pet_expr_free(expr));
212 n = pet_expr_get_n_arg(expr);
213 if (pos < 0 || pos >= n)
214 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
215 "position out of bounds", return pet_expr_free(expr));
216
217 involves = isl_multi_pw_aff_involves_dims(expr->acc.index,
218 isl_dim_in, dim + pos, 1);
219 if (involves < 0)
220 return pet_expr_free(expr);
221 if (involves)
222 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
223 "cannot project out", return pet_expr_free(expr));
224 space = isl_multi_pw_aff_get_domain_space(expr->acc.index);
225 map = isl_map_identity(isl_space_map_from_set(space));
226 map = isl_map_eliminate(map, isl_dim_out, dim + pos, 1);
227 umap = isl_union_map_from_map(map);
228 for (type = pet_expr_access_begin; type < pet_expr_access_end; ++type) {
229 if (!expr->acc.access[type])
230 continue;
231 expr->acc.access[type] =
232 isl_union_map_apply_domain(expr->acc.access[type],
233 isl_union_map_copy(umap));
234 if (!expr->acc.access[type])
235 break;
236 }
237 isl_union_map_free(umap);
238 if (!expr->acc.index || type < pet_expr_access_end)
239 return pet_expr_free(expr);
240
241 space = isl_multi_pw_aff_get_domain_space(expr->acc.index);
242 space = isl_space_unwrap(space);
243 dom = isl_space_map_from_set(isl_space_domain(isl_space_copy(space)));
244 ma1 = isl_multi_aff_identity(dom);
245 if (n == 1) {
246 ma2 = isl_multi_aff_zero(space);
247 ma1 = isl_multi_aff_range_product(ma1, ma2);
248 } else {
249 ran = isl_space_map_from_set(isl_space_range(space));
250 ma2 = isl_multi_aff_identity(ran);
251 ma2 = isl_multi_aff_drop_dims(ma2, isl_dim_in, pos, 1);
252 ma1 = isl_multi_aff_product(ma1, ma2);
253 }
254
255 expr = pet_expr_access_pullback_multi_aff(expr, ma1);
256 if (!expr)
257 return NULL;
258 pet_expr_free(expr->args[pos]);
259 for (i = pos; i + 1 < n; ++i)
260 expr->args[i] = expr->args[i + 1];
261 expr->n_arg = n - 1;
262
263 return expr;
264 }
265
266 /* Plug in "value" for the argument at position "pos" of "expr".
267 *
268 * The input "value" is of the form
269 *
270 * S[i] -> [value(i)]
271 *
272 * while the index expression of "expr" has domain
273 *
274 * [S[i] -> [args]]
275 *
276 * We therefore first pullback "value" to this domain, resulting in
277 *
278 * [S[i] -> [args]] -> [value(i)]
279 *
280 * Then we compute the pullback of "expr" over
281 *
282 * [S[i] -> [args]] -> [S[i] -> [args_before_pos,value(i),args_after_pos]]
283 *
284 * and drop the now redundant argument at position "pos".
285 */
plug_in(__isl_take pet_expr * expr,int pos,__isl_take isl_pw_aff * value)286 static __isl_give pet_expr *plug_in(__isl_take pet_expr *expr, int pos,
287 __isl_take isl_pw_aff *value)
288 {
289 int n_in;
290 isl_space *space;
291 isl_multi_aff *ma;
292 isl_multi_pw_aff *mpa;
293
294 space = isl_multi_pw_aff_get_space(expr->acc.index);
295 space = isl_space_unwrap(isl_space_domain(space));
296 n_in = isl_space_dim(space, isl_dim_in);
297 ma = isl_multi_aff_domain_map(space);
298 value = isl_pw_aff_pullback_multi_aff(value, ma);
299
300 space = isl_multi_pw_aff_get_space(expr->acc.index);
301 space = isl_space_map_from_set(isl_space_domain(space));
302 mpa = isl_multi_pw_aff_identity(space);
303 mpa = isl_multi_pw_aff_set_pw_aff(mpa, n_in + pos, value);
304
305 expr = pet_expr_access_pullback_multi_pw_aff(expr, mpa);
306 expr = pet_expr_access_project_out_arg(expr, n_in, pos);
307
308 return expr;
309 }
310
311 /* Given that the argument of "expr" at position "pos" is a sum
312 * of two expressions, replace references to this argument by the sum
313 * of references to the two expressions.
314 * "dim" is the dimension of the iteration domain.
315 *
316 * That is, replace
317 *
318 * [S[i] -> [args]] -> [f(i,args_before_pos,arg_pos,args_after_pos)]
319 *
320 * by
321 *
322 * [S[i] -> [args_before_pos,arg0,arg1,args_after_pos]] ->
323 * [f(i, args_before_pos, arg0 + arg1, args_after_pos)]
324 *
325 * where arg0 and arg1 refer to the arguments of the sum expression
326 * that the original arg_pos referred to.
327 *
328 * We introduce (an unreferenced) arg1 and replace arg_pos by arg0
329 * in the arguments and then we compute the pullback over
330 *
331 * [S[i] -> [args_before_pos,arg0,arg1,args_after_pos]] ->
332 * [S[i] -> [args_before_pos,arg0+arg1,arg1,args_after_pos]]
333 */
splice_sum(__isl_take pet_expr * expr,int dim,int pos)334 static __isl_give pet_expr *splice_sum(__isl_take pet_expr *expr, int dim,
335 int pos)
336 {
337 isl_space *space;
338 pet_expr *arg;
339 isl_multi_aff *ma;
340 isl_aff *aff1, *aff2;
341
342 arg = expr->args[pos];
343 expr = pet_expr_insert_arg(expr, pos + 1, pet_expr_get_arg(arg, 1));
344 expr = pet_expr_set_arg(expr, pos, pet_expr_get_arg(arg, 0));
345 if (!expr)
346 return NULL;
347
348 space = isl_multi_pw_aff_get_space(expr->acc.index);
349 space = isl_space_map_from_set(isl_space_domain(space));
350 ma = isl_multi_aff_identity(space);
351 aff1 = isl_multi_aff_get_aff(ma, dim + pos);
352 aff2 = isl_multi_aff_get_aff(ma, dim + pos + 1);
353 aff1 = isl_aff_add(aff1, aff2);
354 ma = isl_multi_aff_set_aff(ma, dim + pos, aff1);
355
356 expr = pet_expr_access_pullback_multi_aff(expr, ma);
357
358 return expr;
359 }
360
361 /* Try and integrate the arguments of "expr" into the index expression
362 * of "expr" by trying to convert the arguments to affine expressions.
363 * "pc" is the context in which the affine expressions are created.
364 *
365 * For example, given an access expression with index expression
366 *
367 * [S[i] -> [arg0]] -> A[arg0]
368 *
369 * where the first argument is itself an access to a variable "i"
370 * that is assigned the value
371 *
372 * S[i] -> [i]
373 *
374 * by "pc", this value is plugged into
375 * the index expression of "expr", resulting in
376 *
377 * [i] -> { S[] -> A[i] }
378 * S[i] -> A[i]
379 *
380 *
381 * In particular, we first remove duplicate arguments so that we
382 * only need to convert a given expression once.
383 *
384 * Then we try and convert the arguments to affine expressions and
385 * (if successful) we plug them into the index expression.
386 *
387 * Occasionally, we may be unable to convert an entire argument, while
388 * we could convert a sub-argument. In particular, this may happen
389 * if the top-level argument is an addition of two expressions
390 * of which only one can be converted to an affine expression.
391 * We therefore replace a reference to a "+" argument by the sum
392 * of references to the summands.
393 */
pet_expr_access_plug_in_args(__isl_take pet_expr * expr,__isl_keep pet_context * pc)394 __isl_give pet_expr *pet_expr_access_plug_in_args(__isl_take pet_expr *expr,
395 __isl_keep pet_context *pc)
396 {
397 int i, n;
398
399 expr = pet_expr_remove_duplicate_args(expr);
400 if (!expr)
401 return NULL;
402 if (expr->type != pet_expr_access)
403 isl_die(pet_expr_get_ctx(expr), isl_error_invalid,
404 "not an access pet_expr", return pet_expr_free(expr));
405
406 n = pet_expr_get_n_arg(expr);
407 if (n == 0)
408 return expr;
409
410 for (i = n - 1; expr && i >= 0; --i) {
411 isl_pw_aff *pa;
412 pet_expr *arg = expr->args[i];
413
414 pa = pet_expr_extract_affine(arg, pc);
415 if (!pa)
416 return pet_expr_free(expr);
417 if (!isl_pw_aff_involves_nan(pa)) {
418 expr = plug_in(expr, i, pa);
419 continue;
420 }
421 isl_pw_aff_free(pa);
422
423 if (pet_expr_get_type(arg) == pet_expr_op &&
424 pet_expr_op_get_type(arg) == pet_op_add) {
425 int dim = pet_context_dim(pc);
426 expr = splice_sum(expr, dim, i);
427 i += 2;
428 }
429 }
430
431 return expr;
432 }
433
434 /* A wrapper around pet_expr_access_plug_in_args for use
435 * as a pet_expr_map_access callback.
436 */
plug_in_args(__isl_take pet_expr * expr,void * user)437 static __isl_give pet_expr *plug_in_args(__isl_take pet_expr *expr, void *user)
438 {
439 struct pet_context *pc = user;
440 return pet_expr_access_plug_in_args(expr, pc);
441 }
442
443 /* For each access subexpression of "expr", try and integrate its arguments in
444 * its index expression by trying to convert the arguments
445 * to affine expressions.
446 * "pc" is the context in which the affine expressions are created.
447 */
pet_expr_plug_in_args(__isl_take pet_expr * expr,__isl_keep pet_context * pc)448 __isl_give pet_expr *pet_expr_plug_in_args(__isl_take pet_expr *expr,
449 __isl_keep pet_context *pc)
450 {
451 return pet_expr_map_access(expr, &plug_in_args, pc);
452 }
453