5 /* Do we need to construct a skip condition of the given type
6 * on an if statement, given that the if condition is non-affine?
8 * pet_scop_filter_skip can only handle the case where the if condition
9 * holds (the then branch) and the skip condition is universal.
10 * In any other case, we need to construct a new skip condition.
12 static int if_need_skip_non(struct pet_scop
*scop_then
,
13 struct pet_scop
*scop_else
, int have_else
, enum pet_skip type
)
15 if (have_else
&& scop_else
&& pet_scop_has_skip(scop_else
, type
))
17 if (scop_then
&& pet_scop_has_skip(scop_then
, type
) &&
18 !pet_scop_has_universal_skip(scop_then
, type
))
23 /* Do we need to construct a skip condition of the given type
24 * on an if statement, given that the if condition is affine?
26 * There is no need to construct a new skip condition if all
27 * the skip conditions are affine.
29 static int if_need_skip_aff(struct pet_scop
*scop_then
,
30 struct pet_scop
*scop_else
, int have_else
, enum pet_skip type
)
32 if (scop_then
&& pet_scop_has_var_skip(scop_then
, type
))
34 if (have_else
&& scop_else
&& pet_scop_has_var_skip(scop_else
, type
))
39 /* Do we need to construct a skip condition of the given type
42 static int if_need_skip(struct pet_scop
*scop_then
, struct pet_scop
*scop_else
,
43 int have_else
, enum pet_skip type
, int affine
)
46 return if_need_skip_aff(scop_then
, scop_else
, have_else
, type
);
48 return if_need_skip_non(scop_then
, scop_else
, have_else
, type
);
51 /* Construct an affine expression pet_expr that evaluates
52 * to the constant "val".
54 static __isl_give pet_expr
*universally(isl_ctx
*ctx
, int val
)
58 isl_multi_pw_aff
*mpa
;
60 ls
= isl_local_space_from_space(isl_space_set_alloc(ctx
, 0, 0));
61 aff
= isl_aff_val_on_domain(ls
, isl_val_int_from_si(ctx
, val
));
62 mpa
= isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
64 return pet_expr_from_index(mpa
);
67 /* Construct an affine expression pet_expr that evaluates
70 static __isl_give pet_expr
*universally_true(isl_ctx
*ctx
)
72 return universally(ctx
, 1);
75 /* Construct an affine expression pet_expr that evaluates
78 static __isl_give pet_expr
*universally_false(isl_ctx
*ctx
)
80 return universally(ctx
, 0);
83 /* Given an index expression "test_index" for the if condition,
84 * an index expression "skip_index" for the skip condition and
85 * scops for the then and else branches, construct a scop for
86 * computing "skip_index".
88 * The computed scop contains a single statement that essentially does
90 * skip_index = test_cond ? skip_cond_then : skip_cond_else
92 * If the skip conditions of the then and/or else branch are not affine,
93 * then they need to be filtered by test_index.
94 * If they are missing, then this means the skip condition is false.
96 * Since we are constructing a skip condition for the if statement,
97 * the skip conditions on the then and else branches are removed.
99 static struct pet_scop
*extract_skip_if(__isl_take isl_multi_pw_aff
*test_index
,
100 __isl_take isl_multi_pw_aff
*skip_index
,
101 struct pet_scop
*scop_then
, struct pet_scop
*scop_else
, int have_else
,
102 enum pet_skip type
, int int_size
, int *n_stmt
)
104 pet_expr
*expr_then
, *expr_else
, *expr
, *expr_skip
;
105 struct pet_stmt
*stmt
;
106 struct pet_scop
*scop
;
111 if (have_else
&& !scop_else
)
114 ctx
= isl_multi_pw_aff_get_ctx(test_index
);
116 if (pet_scop_has_skip(scop_then
, type
)) {
117 expr_then
= pet_scop_get_skip_expr(scop_then
, type
);
118 pet_scop_reset_skip(scop_then
, type
);
119 if (!pet_expr_is_affine(expr_then
))
120 expr_then
= pet_expr_filter(expr_then
,
121 isl_multi_pw_aff_copy(test_index
), 1);
123 expr_then
= universally_false(ctx
);
125 if (have_else
&& pet_scop_has_skip(scop_else
, type
)) {
126 expr_else
= pet_scop_get_skip_expr(scop_else
, type
);
127 pet_scop_reset_skip(scop_else
, type
);
128 if (!pet_expr_is_affine(expr_else
))
129 expr_else
= pet_expr_filter(expr_else
,
130 isl_multi_pw_aff_copy(test_index
), 0);
132 expr_else
= universally_false(ctx
);
134 expr
= pet_expr_from_index(test_index
);
135 expr
= pet_expr_new_ternary(expr
, expr_then
, expr_else
);
136 expr_skip
= pet_expr_from_index(isl_multi_pw_aff_copy(skip_index
));
137 expr_skip
= pet_expr_access_set_write(expr_skip
, 1);
138 expr_skip
= pet_expr_access_set_read(expr_skip
, 0);
139 expr
= pet_expr_new_binary(1, pet_op_assign
, expr_skip
, expr
);
140 stmt
= pet_stmt_from_pet_expr(-1, NULL
, (*n_stmt
)++, expr
);
142 scop
= pet_scop_from_pet_stmt(ctx
, stmt
);
143 scop
= pet_scop_add_boolean_array(scop
, skip_index
, int_size
);
147 isl_multi_pw_aff_free(test_index
);
148 isl_multi_pw_aff_free(skip_index
);
152 /* Is scop's skip_now condition equal to its skip_later condition?
153 * In particular, this means that it either has no skip_now condition
154 * or both a skip_now and a skip_later condition (that are equal to each other).
156 static int skip_equals_skip_later(struct pet_scop
*scop
)
158 int has_skip_now
, has_skip_later
;
160 isl_multi_pw_aff
*skip_now
, *skip_later
;
164 has_skip_now
= pet_scop_has_skip(scop
, pet_skip_now
);
165 has_skip_later
= pet_scop_has_skip(scop
, pet_skip_later
);
166 if (has_skip_now
!= has_skip_later
)
171 skip_now
= pet_scop_get_skip(scop
, pet_skip_now
);
172 skip_later
= pet_scop_get_skip(scop
, pet_skip_later
);
173 equal
= isl_multi_pw_aff_is_equal(skip_now
, skip_later
);
174 isl_multi_pw_aff_free(skip_now
);
175 isl_multi_pw_aff_free(skip_later
);
180 /* Drop the skip conditions of type pet_skip_later from scop1 and scop2.
182 static void drop_skip_later(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
184 pet_scop_reset_skip(scop1
, pet_skip_later
);
185 pet_scop_reset_skip(scop2
, pet_skip_later
);
188 /* Do we need to construct any skip condition?
190 int pet_skip_info_has_skip(struct pet_skip_info
*skip
)
192 return skip
->skip
[pet_skip_now
] || skip
->skip
[pet_skip_later
];
195 /* Initialize a pet_skip_info_if structure based on the then and else branches
196 * and based on whether the if condition is affine or not.
198 void pet_skip_info_if_init(struct pet_skip_info
*skip
, isl_ctx
*ctx
,
199 struct pet_scop
*scop_then
, struct pet_scop
*scop_else
,
200 int have_else
, int affine
)
203 skip
->type
= have_else
? pet_skip_if_else
: pet_skip_if
;
204 skip
->u
.i
.scop_then
= scop_then
;
205 skip
->u
.i
.scop_else
= scop_else
;
207 skip
->skip
[pet_skip_now
] =
208 if_need_skip(scop_then
, scop_else
, have_else
, pet_skip_now
, affine
);
209 skip
->equal
= skip
->skip
[pet_skip_now
] &&
210 skip_equals_skip_later(scop_then
) &&
211 (!have_else
|| skip_equals_skip_later(scop_else
));
212 skip
->skip
[pet_skip_later
] = skip
->skip
[pet_skip_now
] &&
214 if_need_skip(scop_then
, scop_else
, have_else
,
215 pet_skip_later
, affine
);
218 /* If we need to construct a skip condition of the given type,
221 * "mpa" represents the if condition.
223 static void pet_skip_info_if_extract_type(struct pet_skip_info
*skip
,
224 __isl_keep isl_multi_pw_aff
*mpa
, enum pet_skip type
,
225 int int_size
, int *n_stmt
, int *n_test
)
227 if (!skip
->skip
[type
])
230 skip
->index
[type
] = pet_create_test_index(skip
->ctx
, (*n_test
)++);
231 skip
->scop
[type
] = extract_skip_if(isl_multi_pw_aff_copy(mpa
),
232 isl_multi_pw_aff_copy(skip
->index
[type
]),
233 skip
->u
.i
.scop_then
, skip
->u
.i
.scop_else
,
234 skip
->type
== pet_skip_if_else
, type
,
238 /* Construct the required skip conditions, given the if condition "index".
240 void pet_skip_info_if_extract_index(struct pet_skip_info
*skip
,
241 __isl_keep isl_multi_pw_aff
*index
,
242 int int_size
, int *n_stmt
, int *n_test
)
244 pet_skip_info_if_extract_type(skip
, index
, pet_skip_now
,
245 int_size
, n_stmt
, n_test
);
246 pet_skip_info_if_extract_type(skip
, index
, pet_skip_later
,
247 int_size
, n_stmt
, n_test
);
249 drop_skip_later(skip
->u
.i
.scop_then
, skip
->u
.i
.scop_else
);
252 /* Construct the required skip conditions, given the if condition "cond".
254 void pet_skip_info_if_extract_cond(struct pet_skip_info
*skip
,
255 __isl_keep isl_pw_aff
*cond
, int int_size
, int *n_stmt
, int *n_test
)
257 isl_multi_pw_aff
*test
;
259 if (!skip
->skip
[pet_skip_now
] && !skip
->skip
[pet_skip_later
])
262 test
= isl_multi_pw_aff_from_pw_aff(isl_pw_aff_copy(cond
));
263 pet_skip_info_if_extract_index(skip
, test
, int_size
, n_stmt
, n_test
);
264 isl_multi_pw_aff_free(test
);
267 /* Add the computed skip condition of the give type to "main" and
268 * add the scop for computing the condition at the given offset.
270 * If equal is set, then we only computed a skip condition for pet_skip_now,
271 * but we also need to set it as main's pet_skip_later.
273 struct pet_scop
*pet_skip_info_if_add_type(struct pet_skip_info
*skip
,
274 struct pet_scop
*main
, enum pet_skip type
, int offset
)
276 if (!skip
->skip
[type
])
279 skip
->scop
[type
] = pet_scop_prefix(skip
->scop
[type
], offset
);
280 main
= pet_scop_add_par(skip
->ctx
, main
, skip
->scop
[type
]);
281 skip
->scop
[type
] = NULL
;
284 main
= pet_scop_set_skip(main
, pet_skip_later
,
285 isl_multi_pw_aff_copy(skip
->index
[type
]));
287 main
= pet_scop_set_skip(main
, type
, skip
->index
[type
]);
288 skip
->index
[type
] = NULL
;
293 /* Add the computed skip conditions to "main" and
294 * add the scops for computing the conditions at the given offset.
296 struct pet_scop
*pet_skip_info_if_add(struct pet_skip_info
*skip
,
297 struct pet_scop
*scop
, int offset
)
299 scop
= pet_skip_info_if_add_type(skip
, scop
, pet_skip_now
, offset
);
300 scop
= pet_skip_info_if_add_type(skip
, scop
, pet_skip_later
, offset
);
305 /* Do we need to construct a skip condition of the given type
306 * on a sequence of statements?
308 * There is no need to construct a new skip condition if only
309 * only of the two statements has a skip condition or if both
310 * of their skip conditions are affine.
312 * In principle we also don't need a new continuation variable if
313 * the continuation of scop2 is affine, but then we would need
314 * to allow more complicated forms of continuations.
316 static int seq_need_skip(struct pet_scop
*scop1
, struct pet_scop
*scop2
,
319 if (!scop1
|| !pet_scop_has_skip(scop1
, type
))
321 if (!scop2
|| !pet_scop_has_skip(scop2
, type
))
323 if (pet_scop_has_affine_skip(scop1
, type
) &&
324 pet_scop_has_affine_skip(scop2
, type
))
329 /* Construct a scop for computing the skip condition of the given type and
330 * with index expression "skip_index" for a sequence of two scops "scop1"
333 * The computed scop contains a single statement that essentially does
335 * skip_index = skip_cond_1 ? 1 : skip_cond_2
337 * or, in other words, skip_cond1 || skip_cond2.
338 * In this expression, skip_cond_2 is filtered to reflect that it is
339 * only evaluated when skip_cond_1 is false.
341 * The skip condition on scop1 is not removed because it still needs
342 * to be applied to scop2 when these two scops are combined.
344 static struct pet_scop
*extract_skip_seq(
345 __isl_take isl_multi_pw_aff
*skip_index
,
346 struct pet_scop
*scop1
, struct pet_scop
*scop2
, enum pet_skip type
,
347 int int_size
, int *n_stmt
)
349 pet_expr
*expr1
, *expr2
, *expr
, *expr_skip
;
350 struct pet_stmt
*stmt
;
351 struct pet_scop
*scop
;
354 if (!scop1
|| !scop2
)
357 ctx
= isl_multi_pw_aff_get_ctx(skip_index
);
359 expr1
= pet_scop_get_skip_expr(scop1
, type
);
360 expr2
= pet_scop_get_skip_expr(scop2
, type
);
361 pet_scop_reset_skip(scop2
, type
);
363 expr2
= pet_expr_filter(expr2
, pet_expr_access_get_index(expr1
), 0);
365 expr
= universally_true(ctx
);
366 expr
= pet_expr_new_ternary(expr1
, expr
, expr2
);
367 expr_skip
= pet_expr_from_index(isl_multi_pw_aff_copy(skip_index
));
368 expr_skip
= pet_expr_access_set_write(expr_skip
, 1);
369 expr_skip
= pet_expr_access_set_read(expr_skip
, 0);
370 expr
= pet_expr_new_binary(1, pet_op_assign
, expr_skip
, expr
);
371 stmt
= pet_stmt_from_pet_expr(-1, NULL
, (*n_stmt
)++, expr
);
373 scop
= pet_scop_from_pet_stmt(ctx
, stmt
);
374 scop
= pet_scop_add_boolean_array(scop
, skip_index
, int_size
);
378 isl_multi_pw_aff_free(skip_index
);
382 /* Initialize a pet_skip_info_seq structure based on
383 * on the two statements that are going to be combined.
385 void pet_skip_info_seq_init(struct pet_skip_info
*skip
, isl_ctx
*ctx
,
386 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
389 skip
->type
= pet_skip_seq
;
390 skip
->u
.s
.scop1
= scop1
;
391 skip
->u
.s
.scop2
= scop2
;
393 skip
->skip
[pet_skip_now
] = seq_need_skip(scop1
, scop2
, pet_skip_now
);
394 skip
->equal
= skip
->skip
[pet_skip_now
] &&
395 skip_equals_skip_later(scop1
) && skip_equals_skip_later(scop2
);
396 skip
->skip
[pet_skip_later
] = skip
->skip
[pet_skip_now
] && !skip
->equal
&&
397 seq_need_skip(scop1
, scop2
, pet_skip_later
);
400 /* If we need to construct a skip condition of the given type,
403 static void pet_skip_info_seq_extract_type(struct pet_skip_info
*skip
,
404 enum pet_skip type
, int int_size
, int *n_stmt
, int *n_test
)
406 if (!skip
->skip
[type
])
409 skip
->index
[type
] = pet_create_test_index(skip
->ctx
, (*n_test
)++);
410 skip
->scop
[type
] = extract_skip_seq(
411 isl_multi_pw_aff_copy(skip
->index
[type
]),
412 skip
->u
.s
.scop1
, skip
->u
.s
.scop2
, type
,
416 /* Construct the required skip conditions.
418 void pet_skip_info_seq_extract(struct pet_skip_info
*skip
,
419 int int_size
, int *n_stmt
, int *n_test
)
421 pet_skip_info_seq_extract_type(skip
, pet_skip_now
,
422 int_size
, n_stmt
, n_test
);
423 pet_skip_info_seq_extract_type(skip
, pet_skip_later
,
424 int_size
, n_stmt
, n_test
);
426 drop_skip_later(skip
->u
.s
.scop1
, skip
->u
.s
.scop2
);
429 /* Add the computed skip condition of the given type to "main" and
430 * add the scop for computing the condition at the given offset (the statement
431 * number). Within this offset, the condition is computed at position 1
432 * to ensure that it is computed after the corresponding statement.
434 * If equal is set, then we only computed a skip condition for pet_skip_now,
435 * but we also need to set it as main's pet_skip_later.
437 struct pet_scop
*pet_skip_info_seq_add_type(struct pet_skip_info
*skip
,
438 struct pet_scop
*main
, enum pet_skip type
, int offset
)
440 if (!skip
->skip
[type
])
443 skip
->scop
[type
] = pet_scop_prefix(skip
->scop
[type
], 1);
444 skip
->scop
[type
] = pet_scop_prefix(skip
->scop
[type
], offset
);
445 main
= pet_scop_add_par(skip
->ctx
, main
, skip
->scop
[type
]);
446 skip
->scop
[type
] = NULL
;
449 main
= pet_scop_set_skip(main
, pet_skip_later
,
450 isl_multi_pw_aff_copy(skip
->index
[type
]));
452 main
= pet_scop_set_skip(main
, type
, skip
->index
[type
]);
453 skip
->index
[type
] = NULL
;
458 /* Add the computed skip conditions to "main" and
459 * add the scops for computing the conditions at the given offset.
461 struct pet_scop
*pet_skip_info_seq_add(struct pet_skip_info
*skip
,
462 struct pet_scop
*scop
, int offset
)
464 scop
= pet_skip_info_seq_add_type(skip
, scop
, pet_skip_now
, offset
);
465 scop
= pet_skip_info_seq_add_type(skip
, scop
, pet_skip_later
, offset
);