scop.c: access_collect_params: avoid using access relation
[pet.git] / skip.c
blobd5861702df346ce62fecf69b33ea39c92bb12ca1
1 #include "expr.h"
2 #include "loc.h"
3 #include "scop.h"
4 #include "skip.h"
5 #include "tree.h"
7 /* Do we need to construct a skip condition of the given type
8 * on an if statement, given that the if condition is non-affine?
10 * pet_scop_filter_skip can only handle the case where the if condition
11 * holds (the then branch) and the skip condition is universal.
12 * In any other case, we need to construct a new skip condition.
14 static int if_need_skip_non(struct pet_scop *scop_then,
15 struct pet_scop *scop_else, int have_else, enum pet_skip type)
17 if (have_else && scop_else && pet_scop_has_skip(scop_else, type))
18 return 1;
19 if (scop_then && pet_scop_has_skip(scop_then, type) &&
20 !pet_scop_has_universal_skip(scop_then, type))
21 return 1;
22 return 0;
25 /* Do we need to construct a skip condition of the given type
26 * on an if statement, given that the if condition is affine?
28 * There is no need to construct a new skip condition if all
29 * the skip conditions are affine.
31 static int if_need_skip_aff(struct pet_scop *scop_then,
32 struct pet_scop *scop_else, int have_else, enum pet_skip type)
34 if (scop_then && pet_scop_has_var_skip(scop_then, type))
35 return 1;
36 if (have_else && scop_else && pet_scop_has_var_skip(scop_else, type))
37 return 1;
38 return 0;
41 /* Do we need to construct a skip condition of the given type
42 * on an if statement?
44 static int if_need_skip(struct pet_scop *scop_then, struct pet_scop *scop_else,
45 int have_else, enum pet_skip type, int affine)
47 if (affine)
48 return if_need_skip_aff(scop_then, scop_else, have_else, type);
49 else
50 return if_need_skip_non(scop_then, scop_else, have_else, type);
53 /* Construct an affine expression pet_expr that evaluates
54 * to the constant "val" on "space".
56 static __isl_give pet_expr *universally(__isl_take isl_space *space, int val)
58 isl_ctx *ctx;
59 isl_local_space *ls;
60 isl_aff *aff;
61 isl_multi_pw_aff *mpa;
63 ctx = isl_space_get_ctx(space);
64 ls = isl_local_space_from_space(space);
65 aff = isl_aff_val_on_domain(ls, isl_val_int_from_si(ctx, val));
66 mpa = isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff));
68 return pet_expr_from_index(mpa);
71 /* Construct an affine expression pet_expr that evaluates
72 * to the constant 1 on "space".
74 static __isl_give pet_expr *universally_true(__isl_take isl_space *space)
76 return universally(space, 1);
79 /* Construct an affine expression pet_expr that evaluates
80 * to the constant 0 on "space".
82 static __isl_give pet_expr *universally_false(__isl_take isl_space *space)
84 return universally(space, 0);
87 /* Given an index expression "test_index" for the if condition,
88 * an index expression "skip_index" for the skip condition and
89 * scops for the then and else branches, construct a scop for
90 * computing "skip_index" within the context "pc".
92 * The computed scop contains a single statement that essentially does
94 * skip_index = test_cond ? skip_cond_then : skip_cond_else
96 * If the skip conditions of the then and/or else branch are not affine,
97 * then they need to be filtered by test_index.
98 * If they are missing, then this means the skip condition is false.
100 * Since we are constructing a skip condition for the if statement,
101 * the skip conditions on the then and else branches are removed.
103 static struct pet_scop *extract_skip_if(__isl_take isl_multi_pw_aff *test_index,
104 __isl_take isl_multi_pw_aff *skip_index,
105 struct pet_scop *scop_then, struct pet_scop *scop_else, int have_else,
106 enum pet_skip type, __isl_keep pet_context *pc, struct pet_state *state)
108 pet_expr *expr_then, *expr_else, *expr, *expr_skip;
109 pet_tree *tree;
110 struct pet_stmt *stmt;
111 struct pet_scop *scop;
112 isl_ctx *ctx;
113 isl_set *domain;
115 if (!scop_then)
116 goto error;
117 if (have_else && !scop_else)
118 goto error;
120 ctx = isl_multi_pw_aff_get_ctx(test_index);
122 if (pet_scop_has_skip(scop_then, type)) {
123 expr_then = pet_scop_get_skip_expr(scop_then, type);
124 pet_scop_reset_skip(scop_then, type);
125 if (!pet_expr_is_affine(expr_then))
126 expr_then = pet_expr_filter(expr_then,
127 isl_multi_pw_aff_copy(test_index), 1);
128 } else
129 expr_then = universally_false(pet_context_get_space(pc));
131 if (have_else && pet_scop_has_skip(scop_else, type)) {
132 expr_else = pet_scop_get_skip_expr(scop_else, type);
133 pet_scop_reset_skip(scop_else, type);
134 if (!pet_expr_is_affine(expr_else))
135 expr_else = pet_expr_filter(expr_else,
136 isl_multi_pw_aff_copy(test_index), 0);
137 } else
138 expr_else = universally_false(pet_context_get_space(pc));
140 expr = pet_expr_from_index(test_index);
141 expr = pet_expr_new_ternary(expr, expr_then, expr_else);
142 expr_skip = pet_expr_from_index(isl_multi_pw_aff_copy(skip_index));
143 expr_skip = pet_expr_access_set_write(expr_skip, 1);
144 expr_skip = pet_expr_access_set_read(expr_skip, 0);
145 expr = pet_expr_new_binary(1, pet_op_assign, expr_skip, expr);
146 domain = pet_context_get_domain(pc);
147 tree = pet_tree_new_expr(expr);
148 stmt = pet_stmt_from_pet_tree(isl_set_copy(domain),
149 state->n_stmt++, tree);
151 scop = pet_scop_from_pet_stmt(pet_context_get_space(pc), stmt);
152 scop = pet_scop_add_boolean_array(scop, domain, skip_index,
153 state->int_size);
155 return scop;
156 error:
157 isl_multi_pw_aff_free(test_index);
158 isl_multi_pw_aff_free(skip_index);
159 return NULL;
162 /* Is scop's skip_now condition equal to its skip_later condition?
163 * In particular, this means that it either has no skip_now condition
164 * or both a skip_now and a skip_later condition (that are equal to each other).
166 static int skip_equals_skip_later(struct pet_scop *scop)
168 int has_skip_now, has_skip_later;
169 int equal;
170 isl_multi_pw_aff *skip_now, *skip_later;
172 if (!scop)
173 return 0;
174 has_skip_now = pet_scop_has_skip(scop, pet_skip_now);
175 has_skip_later = pet_scop_has_skip(scop, pet_skip_later);
176 if (has_skip_now != has_skip_later)
177 return 0;
178 if (!has_skip_now)
179 return 1;
181 skip_now = pet_scop_get_skip(scop, pet_skip_now);
182 skip_later = pet_scop_get_skip(scop, pet_skip_later);
183 equal = isl_multi_pw_aff_is_equal(skip_now, skip_later);
184 isl_multi_pw_aff_free(skip_now);
185 isl_multi_pw_aff_free(skip_later);
187 return equal;
190 /* Drop the skip conditions of type pet_skip_later from scop1 and scop2.
192 static void drop_skip_later(struct pet_scop *scop1, struct pet_scop *scop2)
194 pet_scop_reset_skip(scop1, pet_skip_later);
195 pet_scop_reset_skip(scop2, pet_skip_later);
198 /* Do we need to construct any skip condition?
200 int pet_skip_info_has_skip(struct pet_skip_info *skip)
202 return skip->skip[pet_skip_now] || skip->skip[pet_skip_later];
205 /* Initialize a pet_skip_info_if structure based on the then and else branches
206 * and based on whether the if condition is affine or not.
208 void pet_skip_info_if_init(struct pet_skip_info *skip, isl_ctx *ctx,
209 struct pet_scop *scop_then, struct pet_scop *scop_else,
210 int have_else, int affine)
212 skip->ctx = ctx;
213 skip->type = have_else ? pet_skip_if_else : pet_skip_if;
214 skip->u.i.scop_then = scop_then;
215 skip->u.i.scop_else = scop_else;
217 skip->skip[pet_skip_now] =
218 if_need_skip(scop_then, scop_else, have_else, pet_skip_now, affine);
219 skip->equal = skip->skip[pet_skip_now] &&
220 skip_equals_skip_later(scop_then) &&
221 (!have_else || skip_equals_skip_later(scop_else));
222 skip->skip[pet_skip_later] = skip->skip[pet_skip_now] &&
223 !skip->equal &&
224 if_need_skip(scop_then, scop_else, have_else,
225 pet_skip_later, affine);
228 /* If we need to construct a skip condition of the given type,
229 * then do so now, within the context "pc".
231 * "mpa" represents the if condition.
233 static void pet_skip_info_if_extract_type(struct pet_skip_info *skip,
234 __isl_keep isl_multi_pw_aff *mpa, enum pet_skip type,
235 __isl_keep pet_context *pc, struct pet_state *state)
237 isl_space *space;
239 if (!skip->skip[type])
240 return;
242 space = pet_context_get_space(pc);
243 skip->index[type] = pet_create_test_index(space, state->n_test++);
244 skip->scop[type] = extract_skip_if(isl_multi_pw_aff_copy(mpa),
245 isl_multi_pw_aff_copy(skip->index[type]),
246 skip->u.i.scop_then, skip->u.i.scop_else,
247 skip->type == pet_skip_if_else, type,
248 pc, state);
251 /* Construct the required skip conditions within the context "pc",
252 * given the if condition "index".
254 void pet_skip_info_if_extract_index(struct pet_skip_info *skip,
255 __isl_keep isl_multi_pw_aff *index, __isl_keep pet_context *pc,
256 struct pet_state *state)
258 pet_skip_info_if_extract_type(skip, index, pet_skip_now, pc, state);
259 pet_skip_info_if_extract_type(skip, index, pet_skip_later, pc, state);
260 if (skip->equal)
261 drop_skip_later(skip->u.i.scop_then, skip->u.i.scop_else);
264 /* Construct the required skip conditions within the context "pc",
265 * given the if condition "cond".
267 void pet_skip_info_if_extract_cond(struct pet_skip_info *skip,
268 __isl_keep isl_pw_aff *cond, __isl_keep pet_context *pc,
269 struct pet_state *state)
271 isl_multi_pw_aff *test;
273 if (!skip->skip[pet_skip_now] && !skip->skip[pet_skip_later])
274 return;
276 test = isl_multi_pw_aff_from_pw_aff(isl_pw_aff_copy(cond));
277 pet_skip_info_if_extract_index(skip, test, pc, state);
278 isl_multi_pw_aff_free(test);
281 /* Add the computed skip condition of the give type to "main" and
282 * add the scop for computing the condition at the given offset.
284 * If equal is set, then we only computed a skip condition for pet_skip_now,
285 * but we also need to set it as main's pet_skip_later.
287 struct pet_scop *pet_skip_info_if_add_type(struct pet_skip_info *skip,
288 struct pet_scop *main, enum pet_skip type, int offset)
290 if (!skip->skip[type])
291 return main;
293 skip->scop[type] = pet_scop_prefix(skip->scop[type], offset);
294 main = pet_scop_add_par(skip->ctx, main, skip->scop[type]);
295 skip->scop[type] = NULL;
297 if (skip->equal)
298 main = pet_scop_set_skip(main, pet_skip_later,
299 isl_multi_pw_aff_copy(skip->index[type]));
301 main = pet_scop_set_skip(main, type, skip->index[type]);
302 skip->index[type] = NULL;
304 return main;
307 /* Add the computed skip conditions to "main" and
308 * add the scops for computing the conditions at the given offset.
310 struct pet_scop *pet_skip_info_if_add(struct pet_skip_info *skip,
311 struct pet_scop *scop, int offset)
313 scop = pet_skip_info_if_add_type(skip, scop, pet_skip_now, offset);
314 scop = pet_skip_info_if_add_type(skip, scop, pet_skip_later, offset);
316 return scop;
319 /* Do we need to construct a skip condition of the given type
320 * on a sequence of statements?
322 * There is no need to construct a new skip condition if only
323 * only of the two statements has a skip condition or if both
324 * of their skip conditions are affine.
326 * In principle we also don't need a new continuation variable if
327 * the continuation of scop2 is affine, but then we would need
328 * to allow more complicated forms of continuations.
330 static int seq_need_skip(struct pet_scop *scop1, struct pet_scop *scop2,
331 enum pet_skip type)
333 if (!scop1 || !pet_scop_has_skip(scop1, type))
334 return 0;
335 if (!scop2 || !pet_scop_has_skip(scop2, type))
336 return 0;
337 if (pet_scop_has_affine_skip(scop1, type) &&
338 pet_scop_has_affine_skip(scop2, type))
339 return 0;
340 return 1;
343 /* Construct a scop for computing the skip condition of the given type and
344 * with index expression "skip_index" for a sequence of two scops "scop1"
345 * and "scop2". Do so within the context "pc".
347 * The computed scop contains a single statement that essentially does
349 * skip_index = skip_cond_1 ? 1 : skip_cond_2
351 * or, in other words, skip_cond1 || skip_cond2.
352 * In this expression, skip_cond_2 is filtered to reflect that it is
353 * only evaluated when skip_cond_1 is false.
355 * The skip condition on scop1 is not removed because it still needs
356 * to be applied to scop2 when these two scops are combined.
358 static struct pet_scop *extract_skip_seq(
359 __isl_take isl_multi_pw_aff *skip_index,
360 struct pet_scop *scop1, struct pet_scop *scop2, enum pet_skip type,
361 __isl_keep pet_context *pc, struct pet_state *state)
363 pet_expr *expr1, *expr2, *expr, *expr_skip;
364 pet_tree *tree;
365 struct pet_stmt *stmt;
366 struct pet_scop *scop;
367 isl_ctx *ctx;
368 isl_set *domain;
370 if (!scop1 || !scop2)
371 goto error;
373 ctx = isl_multi_pw_aff_get_ctx(skip_index);
375 expr1 = pet_scop_get_skip_expr(scop1, type);
376 expr2 = pet_scop_get_skip_expr(scop2, type);
377 pet_scop_reset_skip(scop2, type);
379 expr2 = pet_expr_filter(expr2, pet_expr_access_get_index(expr1), 0);
381 expr = universally_true(pet_context_get_space(pc));
382 expr = pet_expr_new_ternary(expr1, expr, expr2);
383 expr_skip = pet_expr_from_index(isl_multi_pw_aff_copy(skip_index));
384 expr_skip = pet_expr_access_set_write(expr_skip, 1);
385 expr_skip = pet_expr_access_set_read(expr_skip, 0);
386 expr = pet_expr_new_binary(1, pet_op_assign, expr_skip, expr);
387 domain = pet_context_get_domain(pc);
388 tree = pet_tree_new_expr(expr);
389 stmt = pet_stmt_from_pet_tree(isl_set_copy(domain),
390 state->n_stmt++, tree);
392 scop = pet_scop_from_pet_stmt(pet_context_get_space(pc), stmt);
393 scop = pet_scop_add_boolean_array(scop, domain, skip_index,
394 state->int_size);
396 return scop;
397 error:
398 isl_multi_pw_aff_free(skip_index);
399 return NULL;
402 /* Initialize a pet_skip_info_seq structure based on
403 * on the two statements that are going to be combined.
405 void pet_skip_info_seq_init(struct pet_skip_info *skip, isl_ctx *ctx,
406 struct pet_scop *scop1, struct pet_scop *scop2)
408 skip->ctx = ctx;
409 skip->type = pet_skip_seq;
410 skip->u.s.scop1 = scop1;
411 skip->u.s.scop2 = scop2;
413 skip->skip[pet_skip_now] = seq_need_skip(scop1, scop2, pet_skip_now);
414 skip->equal = skip->skip[pet_skip_now] &&
415 skip_equals_skip_later(scop1) && skip_equals_skip_later(scop2);
416 skip->skip[pet_skip_later] = skip->skip[pet_skip_now] && !skip->equal &&
417 seq_need_skip(scop1, scop2, pet_skip_later);
420 /* If we need to construct a skip condition of the given type,
421 * then do so now, within the context "pc".
423 static void pet_skip_info_seq_extract_type(struct pet_skip_info *skip,
424 enum pet_skip type, __isl_keep pet_context *pc, struct pet_state *state)
426 isl_space *space;
428 if (!skip->skip[type])
429 return;
431 space = pet_context_get_space(pc);
432 skip->index[type] = pet_create_test_index(space, state->n_test++);
433 skip->scop[type] = extract_skip_seq(
434 isl_multi_pw_aff_copy(skip->index[type]),
435 skip->u.s.scop1, skip->u.s.scop2, type,
436 pc, state);
439 /* Construct the required skip conditions within the context "pc".
441 void pet_skip_info_seq_extract(struct pet_skip_info *skip,
442 __isl_keep pet_context *pc, struct pet_state *state)
444 pet_skip_info_seq_extract_type(skip, pet_skip_now, pc, state);
445 pet_skip_info_seq_extract_type(skip, pet_skip_later, pc, state);
446 if (skip->equal)
447 drop_skip_later(skip->u.s.scop1, skip->u.s.scop2);
450 /* Add the computed skip condition of the given type to "main" and
451 * add the scop for computing the condition at the given offset (the statement
452 * number). Within this offset, the condition is computed at position 1
453 * to ensure that it is computed after the corresponding statement.
455 * If equal is set, then we only computed a skip condition for pet_skip_now,
456 * but we also need to set it as main's pet_skip_later.
458 struct pet_scop *pet_skip_info_seq_add_type(struct pet_skip_info *skip,
459 struct pet_scop *main, enum pet_skip type, int offset)
461 if (!skip->skip[type])
462 return main;
464 skip->scop[type] = pet_scop_prefix(skip->scop[type], 1);
465 skip->scop[type] = pet_scop_prefix(skip->scop[type], offset);
466 main = pet_scop_add_par(skip->ctx, main, skip->scop[type]);
467 skip->scop[type] = NULL;
469 if (skip->equal)
470 main = pet_scop_set_skip(main, pet_skip_later,
471 isl_multi_pw_aff_copy(skip->index[type]));
473 main = pet_scop_set_skip(main, type, skip->index[type]);
474 skip->index[type] = NULL;
476 return main;
479 /* Add the computed skip conditions to "main" and
480 * add the scops for computing the conditions at the given offset.
482 struct pet_scop *pet_skip_info_seq_add(struct pet_skip_info *skip,
483 struct pet_scop *scop, int offset)
485 scop = pet_skip_info_seq_add_type(skip, scop, pet_skip_now, offset);
486 scop = pet_skip_info_seq_add_type(skip, scop, pet_skip_later, offset);
488 return scop;