6 /* Do we need to construct a skip condition of the given type
7 * on an if statement, given that the if condition is non-affine?
9 * pet_scop_filter_skip can only handle the case where the if condition
10 * holds (the then branch) and the skip condition is universal.
11 * In any other case, we need to construct a new skip condition.
13 static int if_need_skip_non(struct pet_scop
*scop_then
,
14 struct pet_scop
*scop_else
, int have_else
, enum pet_skip type
)
16 if (have_else
&& scop_else
&& pet_scop_has_skip(scop_else
, type
))
18 if (scop_then
&& pet_scop_has_skip(scop_then
, type
) &&
19 !pet_scop_has_universal_skip(scop_then
, type
))
24 /* Do we need to construct a skip condition of the given type
25 * on an if statement, given that the if condition is affine?
27 * There is no need to construct a new skip condition if all
28 * the skip conditions are affine.
30 static int if_need_skip_aff(struct pet_scop
*scop_then
,
31 struct pet_scop
*scop_else
, int have_else
, enum pet_skip type
)
33 if (scop_then
&& pet_scop_has_var_skip(scop_then
, type
))
35 if (have_else
&& scop_else
&& pet_scop_has_var_skip(scop_else
, type
))
40 /* Do we need to construct a skip condition of the given type
43 static int if_need_skip(struct pet_scop
*scop_then
, struct pet_scop
*scop_else
,
44 int have_else
, enum pet_skip type
, int affine
)
47 return if_need_skip_aff(scop_then
, scop_else
, have_else
, type
);
49 return if_need_skip_non(scop_then
, scop_else
, have_else
, type
);
52 /* Construct an affine expression pet_expr that evaluates
53 * to the constant "val".
55 static __isl_give pet_expr
*universally(isl_ctx
*ctx
, int val
)
59 isl_multi_pw_aff
*mpa
;
61 ls
= isl_local_space_from_space(isl_space_set_alloc(ctx
, 0, 0));
62 aff
= isl_aff_val_on_domain(ls
, isl_val_int_from_si(ctx
, val
));
63 mpa
= isl_multi_pw_aff_from_pw_aff(isl_pw_aff_from_aff(aff
));
65 return pet_expr_from_index(mpa
);
68 /* Construct an affine expression pet_expr that evaluates
71 static __isl_give pet_expr
*universally_true(isl_ctx
*ctx
)
73 return universally(ctx
, 1);
76 /* Construct an affine expression pet_expr that evaluates
79 static __isl_give pet_expr
*universally_false(isl_ctx
*ctx
)
81 return universally(ctx
, 0);
84 /* Given an index expression "test_index" for the if condition,
85 * an index expression "skip_index" for the skip condition and
86 * scops for the then and else branches, construct a scop for
87 * computing "skip_index".
89 * The computed scop contains a single statement that essentially does
91 * skip_index = test_cond ? skip_cond_then : skip_cond_else
93 * If the skip conditions of the then and/or else branch are not affine,
94 * then they need to be filtered by test_index.
95 * If they are missing, then this means the skip condition is false.
97 * Since we are constructing a skip condition for the if statement,
98 * the skip conditions on the then and else branches are removed.
100 static struct pet_scop
*extract_skip_if(__isl_take isl_multi_pw_aff
*test_index
,
101 __isl_take isl_multi_pw_aff
*skip_index
,
102 struct pet_scop
*scop_then
, struct pet_scop
*scop_else
, int have_else
,
103 enum pet_skip type
, struct pet_state
*state
)
105 pet_expr
*expr_then
, *expr_else
, *expr
, *expr_skip
;
106 struct pet_stmt
*stmt
;
107 struct pet_scop
*scop
;
113 if (have_else
&& !scop_else
)
116 ctx
= isl_multi_pw_aff_get_ctx(test_index
);
118 if (pet_scop_has_skip(scop_then
, type
)) {
119 expr_then
= pet_scop_get_skip_expr(scop_then
, type
);
120 pet_scop_reset_skip(scop_then
, type
);
121 if (!pet_expr_is_affine(expr_then
))
122 expr_then
= pet_expr_filter(expr_then
,
123 isl_multi_pw_aff_copy(test_index
), 1);
125 expr_then
= universally_false(ctx
);
127 if (have_else
&& pet_scop_has_skip(scop_else
, type
)) {
128 expr_else
= pet_scop_get_skip_expr(scop_else
, type
);
129 pet_scop_reset_skip(scop_else
, type
);
130 if (!pet_expr_is_affine(expr_else
))
131 expr_else
= pet_expr_filter(expr_else
,
132 isl_multi_pw_aff_copy(test_index
), 0);
134 expr_else
= universally_false(ctx
);
136 expr
= pet_expr_from_index(test_index
);
137 expr
= pet_expr_new_ternary(expr
, expr_then
, expr_else
);
138 expr_skip
= pet_expr_from_index(isl_multi_pw_aff_copy(skip_index
));
139 expr_skip
= pet_expr_access_set_write(expr_skip
, 1);
140 expr_skip
= pet_expr_access_set_read(expr_skip
, 0);
141 expr
= pet_expr_new_binary(1, pet_op_assign
, expr_skip
, expr
);
142 domain
= isl_set_universe(isl_space_set_alloc(ctx
, 0, 0));
143 stmt
= pet_stmt_from_pet_expr(domain
, &pet_loc_dummy
, NULL
,
144 state
->n_stmt
++, expr
);
146 scop
= pet_scop_from_pet_stmt(ctx
, stmt
);
147 scop
= pet_scop_add_boolean_array(scop
, skip_index
, state
->int_size
);
151 isl_multi_pw_aff_free(test_index
);
152 isl_multi_pw_aff_free(skip_index
);
156 /* Is scop's skip_now condition equal to its skip_later condition?
157 * In particular, this means that it either has no skip_now condition
158 * or both a skip_now and a skip_later condition (that are equal to each other).
160 static int skip_equals_skip_later(struct pet_scop
*scop
)
162 int has_skip_now
, has_skip_later
;
164 isl_multi_pw_aff
*skip_now
, *skip_later
;
168 has_skip_now
= pet_scop_has_skip(scop
, pet_skip_now
);
169 has_skip_later
= pet_scop_has_skip(scop
, pet_skip_later
);
170 if (has_skip_now
!= has_skip_later
)
175 skip_now
= pet_scop_get_skip(scop
, pet_skip_now
);
176 skip_later
= pet_scop_get_skip(scop
, pet_skip_later
);
177 equal
= isl_multi_pw_aff_is_equal(skip_now
, skip_later
);
178 isl_multi_pw_aff_free(skip_now
);
179 isl_multi_pw_aff_free(skip_later
);
184 /* Drop the skip conditions of type pet_skip_later from scop1 and scop2.
186 static void drop_skip_later(struct pet_scop
*scop1
, struct pet_scop
*scop2
)
188 pet_scop_reset_skip(scop1
, pet_skip_later
);
189 pet_scop_reset_skip(scop2
, pet_skip_later
);
192 /* Do we need to construct any skip condition?
194 int pet_skip_info_has_skip(struct pet_skip_info
*skip
)
196 return skip
->skip
[pet_skip_now
] || skip
->skip
[pet_skip_later
];
199 /* Initialize a pet_skip_info_if structure based on the then and else branches
200 * and based on whether the if condition is affine or not.
202 void pet_skip_info_if_init(struct pet_skip_info
*skip
, isl_ctx
*ctx
,
203 struct pet_scop
*scop_then
, struct pet_scop
*scop_else
,
204 int have_else
, int affine
)
207 skip
->type
= have_else
? pet_skip_if_else
: pet_skip_if
;
208 skip
->u
.i
.scop_then
= scop_then
;
209 skip
->u
.i
.scop_else
= scop_else
;
211 skip
->skip
[pet_skip_now
] =
212 if_need_skip(scop_then
, scop_else
, have_else
, pet_skip_now
, affine
);
213 skip
->equal
= skip
->skip
[pet_skip_now
] &&
214 skip_equals_skip_later(scop_then
) &&
215 (!have_else
|| skip_equals_skip_later(scop_else
));
216 skip
->skip
[pet_skip_later
] = skip
->skip
[pet_skip_now
] &&
218 if_need_skip(scop_then
, scop_else
, have_else
,
219 pet_skip_later
, affine
);
222 /* If we need to construct a skip condition of the given type,
225 * "mpa" represents the if condition.
227 static void pet_skip_info_if_extract_type(struct pet_skip_info
*skip
,
228 __isl_keep isl_multi_pw_aff
*mpa
, enum pet_skip type
,
229 struct pet_state
*state
)
233 if (!skip
->skip
[type
])
236 space
= isl_space_set_alloc(skip
->ctx
, 0, 0);
237 skip
->index
[type
] = pet_create_test_index(space
, state
->n_test
++);
238 skip
->scop
[type
] = extract_skip_if(isl_multi_pw_aff_copy(mpa
),
239 isl_multi_pw_aff_copy(skip
->index
[type
]),
240 skip
->u
.i
.scop_then
, skip
->u
.i
.scop_else
,
241 skip
->type
== pet_skip_if_else
, type
, state
);
244 /* Construct the required skip conditions, given the if condition "index".
246 void pet_skip_info_if_extract_index(struct pet_skip_info
*skip
,
247 __isl_keep isl_multi_pw_aff
*index
, struct pet_state
*state
)
249 pet_skip_info_if_extract_type(skip
, index
, pet_skip_now
, state
);
250 pet_skip_info_if_extract_type(skip
, index
, pet_skip_later
, state
);
252 drop_skip_later(skip
->u
.i
.scop_then
, skip
->u
.i
.scop_else
);
255 /* Construct the required skip conditions, given the if condition "cond".
257 void pet_skip_info_if_extract_cond(struct pet_skip_info
*skip
,
258 __isl_keep isl_pw_aff
*cond
, struct pet_state
*state
)
260 isl_multi_pw_aff
*test
;
262 if (!skip
->skip
[pet_skip_now
] && !skip
->skip
[pet_skip_later
])
265 test
= isl_multi_pw_aff_from_pw_aff(isl_pw_aff_copy(cond
));
266 pet_skip_info_if_extract_index(skip
, test
, state
);
267 isl_multi_pw_aff_free(test
);
270 /* Add the computed skip condition of the give type to "main" and
271 * add the scop for computing the condition at the given offset.
273 * If equal is set, then we only computed a skip condition for pet_skip_now,
274 * but we also need to set it as main's pet_skip_later.
276 struct pet_scop
*pet_skip_info_if_add_type(struct pet_skip_info
*skip
,
277 struct pet_scop
*main
, enum pet_skip type
, int offset
)
279 if (!skip
->skip
[type
])
282 skip
->scop
[type
] = pet_scop_prefix(skip
->scop
[type
], offset
);
283 main
= pet_scop_add_par(skip
->ctx
, main
, skip
->scop
[type
]);
284 skip
->scop
[type
] = NULL
;
287 main
= pet_scop_set_skip(main
, pet_skip_later
,
288 isl_multi_pw_aff_copy(skip
->index
[type
]));
290 main
= pet_scop_set_skip(main
, type
, skip
->index
[type
]);
291 skip
->index
[type
] = NULL
;
296 /* Add the computed skip conditions to "main" and
297 * add the scops for computing the conditions at the given offset.
299 struct pet_scop
*pet_skip_info_if_add(struct pet_skip_info
*skip
,
300 struct pet_scop
*scop
, int offset
)
302 scop
= pet_skip_info_if_add_type(skip
, scop
, pet_skip_now
, offset
);
303 scop
= pet_skip_info_if_add_type(skip
, scop
, pet_skip_later
, offset
);
308 /* Do we need to construct a skip condition of the given type
309 * on a sequence of statements?
311 * There is no need to construct a new skip condition if only
312 * only of the two statements has a skip condition or if both
313 * of their skip conditions are affine.
315 * In principle we also don't need a new continuation variable if
316 * the continuation of scop2 is affine, but then we would need
317 * to allow more complicated forms of continuations.
319 static int seq_need_skip(struct pet_scop
*scop1
, struct pet_scop
*scop2
,
322 if (!scop1
|| !pet_scop_has_skip(scop1
, type
))
324 if (!scop2
|| !pet_scop_has_skip(scop2
, type
))
326 if (pet_scop_has_affine_skip(scop1
, type
) &&
327 pet_scop_has_affine_skip(scop2
, type
))
332 /* Construct a scop for computing the skip condition of the given type and
333 * with index expression "skip_index" for a sequence of two scops "scop1"
336 * The computed scop contains a single statement that essentially does
338 * skip_index = skip_cond_1 ? 1 : skip_cond_2
340 * or, in other words, skip_cond1 || skip_cond2.
341 * In this expression, skip_cond_2 is filtered to reflect that it is
342 * only evaluated when skip_cond_1 is false.
344 * The skip condition on scop1 is not removed because it still needs
345 * to be applied to scop2 when these two scops are combined.
347 static struct pet_scop
*extract_skip_seq(
348 __isl_take isl_multi_pw_aff
*skip_index
,
349 struct pet_scop
*scop1
, struct pet_scop
*scop2
, enum pet_skip type
,
350 struct pet_state
*state
)
352 pet_expr
*expr1
, *expr2
, *expr
, *expr_skip
;
353 struct pet_stmt
*stmt
;
354 struct pet_scop
*scop
;
358 if (!scop1
|| !scop2
)
361 ctx
= isl_multi_pw_aff_get_ctx(skip_index
);
363 expr1
= pet_scop_get_skip_expr(scop1
, type
);
364 expr2
= pet_scop_get_skip_expr(scop2
, type
);
365 pet_scop_reset_skip(scop2
, type
);
367 expr2
= pet_expr_filter(expr2
, pet_expr_access_get_index(expr1
), 0);
369 expr
= universally_true(ctx
);
370 expr
= pet_expr_new_ternary(expr1
, expr
, expr2
);
371 expr_skip
= pet_expr_from_index(isl_multi_pw_aff_copy(skip_index
));
372 expr_skip
= pet_expr_access_set_write(expr_skip
, 1);
373 expr_skip
= pet_expr_access_set_read(expr_skip
, 0);
374 expr
= pet_expr_new_binary(1, pet_op_assign
, expr_skip
, expr
);
375 domain
= isl_set_universe(isl_space_set_alloc(ctx
, 0, 0));
376 stmt
= pet_stmt_from_pet_expr(domain
, &pet_loc_dummy
, NULL
,
377 state
->n_stmt
++, expr
);
379 scop
= pet_scop_from_pet_stmt(ctx
, stmt
);
380 scop
= pet_scop_add_boolean_array(scop
, skip_index
, state
->int_size
);
384 isl_multi_pw_aff_free(skip_index
);
388 /* Initialize a pet_skip_info_seq structure based on
389 * on the two statements that are going to be combined.
391 void pet_skip_info_seq_init(struct pet_skip_info
*skip
, isl_ctx
*ctx
,
392 struct pet_scop
*scop1
, struct pet_scop
*scop2
)
395 skip
->type
= pet_skip_seq
;
396 skip
->u
.s
.scop1
= scop1
;
397 skip
->u
.s
.scop2
= scop2
;
399 skip
->skip
[pet_skip_now
] = seq_need_skip(scop1
, scop2
, pet_skip_now
);
400 skip
->equal
= skip
->skip
[pet_skip_now
] &&
401 skip_equals_skip_later(scop1
) && skip_equals_skip_later(scop2
);
402 skip
->skip
[pet_skip_later
] = skip
->skip
[pet_skip_now
] && !skip
->equal
&&
403 seq_need_skip(scop1
, scop2
, pet_skip_later
);
406 /* If we need to construct a skip condition of the given type,
409 static void pet_skip_info_seq_extract_type(struct pet_skip_info
*skip
,
410 enum pet_skip type
, struct pet_state
*state
)
414 if (!skip
->skip
[type
])
417 space
= isl_space_set_alloc(skip
->ctx
, 0, 0);
418 skip
->index
[type
] = pet_create_test_index(space
, state
->n_test
++);
419 skip
->scop
[type
] = extract_skip_seq(
420 isl_multi_pw_aff_copy(skip
->index
[type
]),
421 skip
->u
.s
.scop1
, skip
->u
.s
.scop2
, type
, state
);
424 /* Construct the required skip conditions.
426 void pet_skip_info_seq_extract(struct pet_skip_info
*skip
,
427 struct pet_state
*state
)
429 pet_skip_info_seq_extract_type(skip
, pet_skip_now
, state
);
430 pet_skip_info_seq_extract_type(skip
, pet_skip_later
, state
);
432 drop_skip_later(skip
->u
.s
.scop1
, skip
->u
.s
.scop2
);
435 /* Add the computed skip condition of the given type to "main" and
436 * add the scop for computing the condition at the given offset (the statement
437 * number). Within this offset, the condition is computed at position 1
438 * to ensure that it is computed after the corresponding statement.
440 * If equal is set, then we only computed a skip condition for pet_skip_now,
441 * but we also need to set it as main's pet_skip_later.
443 struct pet_scop
*pet_skip_info_seq_add_type(struct pet_skip_info
*skip
,
444 struct pet_scop
*main
, enum pet_skip type
, int offset
)
446 if (!skip
->skip
[type
])
449 skip
->scop
[type
] = pet_scop_prefix(skip
->scop
[type
], 1);
450 skip
->scop
[type
] = pet_scop_prefix(skip
->scop
[type
], offset
);
451 main
= pet_scop_add_par(skip
->ctx
, main
, skip
->scop
[type
]);
452 skip
->scop
[type
] = NULL
;
455 main
= pet_scop_set_skip(main
, pet_skip_later
,
456 isl_multi_pw_aff_copy(skip
->index
[type
]));
458 main
= pet_scop_set_skip(main
, type
, skip
->index
[type
]);
459 skip
->index
[type
] = NULL
;
464 /* Add the computed skip conditions to "main" and
465 * add the scops for computing the conditions at the given offset.
467 struct pet_scop
*pet_skip_info_seq_add(struct pet_skip_info
*skip
,
468 struct pet_scop
*scop
, int offset
)
470 scop
= pet_skip_info_seq_add_type(skip
, scop
, pet_skip_now
, offset
);
471 scop
= pet_skip_info_seq_add_type(skip
, scop
, pet_skip_later
, offset
);