From fedb64a1a9980d30cfb991594967b5f39a30ecbe Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Thu, 5 Jan 2012 17:46:27 +0100 Subject: [PATCH] support break and continue To be able to handle breaks and continues, we keep track of the condition under which subsequent statements in the current loop iteration or any statement in later loop iterations should not be executed. These "skip" conditions may be either affine constraints or they may be represented by the value of a virtual array. The conditions, when introduced by a break or continue statement, start out as universal constraints and get modified when the statement is embedded in an if statement and/or combined with other statements. These modified skip conditions may require the introduction of additional virtual arrays to represent the combination of the skip conditions. Signed-off-by: Sven Verdoolaege --- scan.cc | 774 ++++++++++++++++++++++++++++++++++++++++++++- scan.h | 2 + scop.c | 412 +++++++++++++++++++++++- scop.h | 23 +- tests/break.c | 14 + tests/break.scop | 44 +++ tests/break2.c | 16 + tests/break2.scop | 45 +++ tests/break3.c | 16 + tests/break3.scop | 82 +++++ tests/break4.c | 30 ++ tests/break4.scop | 651 ++++++++++++++++++++++++++++++++++++++ tests/break5.c | 20 ++ tests/break5.scop | 47 +++ tests/continue.c | 14 + tests/continue.scop | 45 +++ tests/continue2.c | 24 ++ tests/continue2.scop | 279 ++++++++++++++++ tests/continue3.c | 19 ++ tests/continue3.scop | 186 +++++++++++ tests/continue4.c | 19 ++ tests/continue4.scop | 154 +++++++++ tests/continue5.c | 19 ++ tests/continue5.scop | 138 ++++++++ tests/unsigned_break1.c | 14 + tests/unsigned_break1.scop | 40 +++ tests/unsigned_break2.c | 17 + tests/unsigned_break2.scop | 77 +++++ tests/while_break.c | 34 ++ tests/while_break.scop | 280 ++++++++++++++++ 30 files changed, 3512 insertions(+), 23 deletions(-) create mode 100644 tests/break.c create mode 100644 tests/break.scop create mode 100644 tests/break2.c create mode 100644 tests/break2.scop create mode 100644 tests/break3.c create mode 100644 tests/break3.scop create mode 100644 tests/break4.c create mode 100644 tests/break4.scop create mode 100644 tests/break5.c create mode 100644 tests/break5.scop create mode 100644 tests/continue.c create mode 100644 tests/continue.scop create mode 100644 tests/continue2.c create mode 100644 tests/continue2.scop create mode 100644 tests/continue3.c create mode 100644 tests/continue3.scop create mode 100644 tests/continue4.c create mode 100644 tests/continue4.scop create mode 100644 tests/continue5.c create mode 100644 tests/continue5.scop create mode 100644 tests/unsigned_break1.c create mode 100644 tests/unsigned_break1.scop create mode 100644 tests/unsigned_break2.c create mode 100644 tests/unsigned_break2.scop create mode 100644 tests/while_break.c create mode 100644 tests/while_break.scop diff --git a/scan.cc b/scan.cc index 08c8d26..d98d6f7 100644 --- a/scan.cc +++ b/scan.cc @@ -1867,19 +1867,57 @@ static __isl_give isl_set *embed(__isl_take isl_set *set, return set; } +/* Return those elements in the space of "cond" that come after + * (based on "sign") an element in "cond". + */ +static __isl_give isl_set *after(__isl_take isl_set *cond, int sign) +{ + isl_map *previous_to_this; + + if (sign > 0) + previous_to_this = isl_map_lex_lt(isl_set_get_space(cond)); + else + previous_to_this = isl_map_lex_gt(isl_set_get_space(cond)); + + cond = isl_set_apply(cond, previous_to_this); + + return cond; +} + /* Create the infinite iteration domain * * { [id] : id >= 0 } * + * If "scop" has an affine skip of type pet_skip_later, + * then remove those iterations i that have an earlier iteration + * where the skip condition is satisfied, meaning that iteration i + * is not executed. + * Since we are dealing with a loop without loop iterator, + * the skip condition cannot refer to the current loop iterator and + * so effectively, the returned set is of the form + * + * { [0]; [id] : id >= 1 and not skip } */ -static __isl_give isl_set *infinite_domain(__isl_take isl_id *id) +static __isl_give isl_set *infinite_domain(__isl_take isl_id *id, + struct pet_scop *scop) { isl_ctx *ctx = isl_id_get_ctx(id); isl_set *domain; + isl_set *skip; domain = isl_set_nat_universe(isl_space_set_alloc(ctx, 0, 1)); domain = isl_set_set_dim_id(domain, isl_dim_set, 0, id); + if (!pet_scop_has_affine_skip(scop, pet_skip_later)) + return domain; + + skip = pet_scop_get_skip(scop, pet_skip_later); + skip = isl_set_fix_si(skip, isl_dim_set, 0, 1); + skip = isl_set_params(skip); + skip = embed(skip, isl_id_copy(id)); + skip = isl_set_intersect(skip , isl_set_copy(domain)); + domain = isl_set_subtract(domain, after(skip, 1)); + return domain; } @@ -1896,6 +1934,34 @@ static __isl_give isl_map *identity_map(__isl_keep isl_set *domain) return id; } +/* Add a filter to "scop" that imposes that it is only executed + * when "break_access" has a zero value for all previous iterations + * of "domain". + * + * The input "break_access" has a zero-dimensional domain and range. + */ +static struct pet_scop *scop_add_break(struct pet_scop *scop, + __isl_take isl_map *break_access, __isl_take isl_set *domain, int sign) +{ + isl_ctx *ctx = isl_set_get_ctx(domain); + isl_id *id_test; + isl_map *prev; + + id_test = isl_map_get_tuple_id(break_access, isl_dim_out); + break_access = isl_map_add_dims(break_access, isl_dim_in, 1); + break_access = isl_map_add_dims(break_access, isl_dim_out, 1); + break_access = isl_map_intersect_range(break_access, domain); + break_access = isl_map_set_tuple_id(break_access, isl_dim_out, id_test); + if (sign > 0) + prev = isl_map_lex_gt_first(isl_map_get_space(break_access), 1); + else + prev = isl_map_lex_lt_first(isl_map_get_space(break_access), 1); + break_access = isl_map_intersect(break_access, prev); + scop = pet_scop_filter(scop, break_access, 0); + + return scop; +} + /* Construct a pet_scop for an infinite loop around the given body. * * We extract a pet_scop for the body and then embed it in a loop with @@ -1906,22 +1972,38 @@ static __isl_give isl_map *identity_map(__isl_keep isl_set *domain) * and schedule * * { [t] -> [t] } + * + * If the body contains any break, then it is taken into + * account in infinite_domain (if the skip condition is affine) + * or in scop_add_break (if the skip condition is not affine). */ struct pet_scop *PetScan::extract_infinite_loop(Stmt *body) { isl_id *id; isl_set *domain; isl_map *ident; + isl_map *access; struct pet_scop *scop; + bool has_var_break; scop = extract(body); if (!scop) return NULL; id = isl_id_alloc(ctx, "t", NULL); - domain = infinite_domain(isl_id_copy(id)); + domain = infinite_domain(isl_id_copy(id), scop); ident = identity_map(domain); - scop = pet_scop_embed(scop, domain, isl_map_copy(ident), ident, id); + + has_var_break = pet_scop_has_var_skip(scop, pet_skip_later); + if (has_var_break) + access = pet_scop_get_skip_map(scop, pet_skip_later); + + scop = pet_scop_embed(scop, isl_set_copy(domain), + isl_map_copy(ident), ident, id); + if (has_var_break) + scop = scop_add_break(scop, access, domain, 1); + else + isl_set_free(domain); return scop; } @@ -2076,7 +2158,7 @@ static struct pet_scop *scop_add_while(struct pet_scop *scop_cond, test_access = isl_map_intersect(test_access, prev); scop_cond = pet_scop_filter(scop_cond, test_access, 1); - return pet_scop_add(ctx, scop_cond, scop_body); + return pet_scop_add_seq(ctx, scop_cond, scop_body); } /* Check if the while loop is of the form @@ -2098,6 +2180,10 @@ static struct pet_scop *scop_add_while(struct pet_scop *scop_cond, * The context of the scop representing the body is dropped * because we don't know how many times the body will be executed, * if at all. + * + * If the body contains any break, then it is taken into + * account in infinite_domain (if the skip condition is affine) + * or in scop_add_break (if the skip condition is not affine). */ struct pet_scop *PetScan::extract(WhileStmt *stmt) { @@ -2108,6 +2194,8 @@ struct pet_scop *PetScan::extract(WhileStmt *stmt) isl_map *ident; isl_pw_aff *pa; struct pet_scop *scop, *scop_body; + bool has_var_break; + isl_map *break_access; cond = stmt->getCond(); if (!cond) { @@ -2124,22 +2212,33 @@ struct pet_scop *PetScan::extract(WhileStmt *stmt) return NULL; } - id = isl_id_alloc(ctx, "t", NULL); - domain = infinite_domain(isl_id_copy(id)); - ident = identity_map(domain); - test_access = create_test_access(ctx, n_test++); scop = extract_non_affine_condition(cond, isl_map_copy(test_access)); scop = scop_add_array(scop, test_access, ast_context); + scop_body = extract(stmt->getBody()); + + id = isl_id_alloc(ctx, "t", NULL); + domain = infinite_domain(isl_id_copy(id), scop_body); + ident = identity_map(domain); + + has_var_break = pet_scop_has_var_skip(scop_body, pet_skip_later); + if (has_var_break) + break_access = pet_scop_get_skip_map(scop_body, pet_skip_later); + scop = pet_scop_prefix(scop, 0); scop = pet_scop_embed(scop, isl_set_copy(domain), isl_map_copy(ident), isl_map_copy(ident), isl_id_copy(id)); - scop_body = extract(stmt->getBody()); scop_body = pet_scop_reset_context(scop_body); scop_body = pet_scop_prefix(scop_body, 1); scop_body = pet_scop_embed(scop_body, isl_set_copy(domain), isl_map_copy(ident), ident, id); + if (has_var_break) { + scop = scop_add_break(scop, isl_map_copy(break_access), + isl_set_copy(domain), 1); + scop_body = scop_add_break(scop_body, break_access, + isl_set_copy(domain), 1); + } scop = scop_add_while(scop, scop_body, test_access, domain, 1); return scop; @@ -2484,6 +2583,14 @@ static bool has_nested(__isl_keep isl_pw_aff *pa) * can be evaluated. * If the loop condition is non-affine, then we only consider validity * of the initial value. + * + * If the body contains any break, then we keep track of it in "skip" + * (if the skip condition is affine) or it is handled in scop_add_break + * (if the skip condition is not affine). + * Note that the affine break condition needs to be considered with + * respect to previous iterations in the virtual domain (if any) + * and that the domain needs to be kept virtual if there is a non-affine + * break condition. */ struct pet_scop *PetScan::extract_for(ForStmt *stmt) { @@ -2496,6 +2603,7 @@ struct pet_scop *PetScan::extract_for(ForStmt *stmt) isl_set *domain; isl_map *sched; isl_set *cond = NULL; + isl_set *skip = NULL; isl_id *id; struct pet_scop *scop, *scop_cond = NULL; assigned_value_cache cache(assigned_value); @@ -2505,6 +2613,8 @@ struct pet_scop *PetScan::extract_for(ForStmt *stmt) bool is_simple; bool is_virtual; bool keep_virtual = false; + bool has_affine_break; + bool has_var_break; isl_map *wrap = NULL; isl_pw_aff *pa, *pa_inc, *init_val; isl_set *valid_init; @@ -2512,7 +2622,7 @@ struct pet_scop *PetScan::extract_for(ForStmt *stmt) isl_set *valid_cond_init; isl_set *valid_cond_next; isl_set *valid_inc; - isl_map *test_access = NULL; + isl_map *test_access = NULL, *break_access = NULL; int stmt_id; if (!stmt->getInit() && !stmt->getCond() && !stmt->getInc()) @@ -2569,6 +2679,19 @@ struct pet_scop *PetScan::extract_for(ForStmt *stmt) scop = extract(stmt->getBody()); + has_affine_break = scop && + pet_scop_has_affine_skip(scop, pet_skip_later); + if (has_affine_break) { + skip = pet_scop_get_skip(scop, pet_skip_later); + skip = isl_set_fix_si(skip, isl_dim_set, 0, 1); + skip = isl_set_params(skip); + } + has_var_break = scop && pet_scop_has_var_skip(scop, pet_skip_later); + if (has_var_break) { + break_access = pet_scop_get_skip_map(scop, pet_skip_later); + keep_virtual = true; + } + if (pa && !is_nested_allowed(pa, scop)) { isl_pw_aff_free(pa); pa = NULL; @@ -2594,6 +2717,7 @@ struct pet_scop *PetScan::extract_for(ForStmt *stmt) } cond = embed(cond, isl_id_copy(id)); + skip = embed(skip, isl_id_copy(id)); valid_cond = isl_set_coalesce(valid_cond); valid_cond = embed(valid_cond, isl_id_copy(id)); valid_inc = embed(valid_inc, isl_id_copy(id)); @@ -2622,6 +2746,7 @@ struct pet_scop *PetScan::extract_for(ForStmt *stmt) wrap = compute_wrapping(isl_set_get_space(cond), iv); rev_wrap = isl_map_reverse(isl_map_copy(wrap)); cond = isl_set_apply(cond, isl_map_copy(rev_wrap)); + skip = isl_set_apply(skip, isl_map_copy(rev_wrap)); valid_cond = isl_set_apply(valid_cond, isl_map_copy(rev_wrap)); valid_inc = isl_set_apply(valid_inc, rev_wrap); } @@ -2631,6 +2756,11 @@ struct pet_scop *PetScan::extract_for(ForStmt *stmt) cond = valid_for_each_iteration(cond, isl_set_copy(domain), inc); domain = isl_set_intersect(domain, cond); + if (has_affine_break) { + skip = isl_set_intersect(skip , isl_set_copy(domain)); + skip = after(skip, isl_int_sgn(inc)); + domain = isl_set_subtract(domain, skip); + } domain = isl_set_set_dim_id(domain, isl_dim_set, 0, isl_id_copy(id)); space = isl_space_from_domain(isl_set_get_space(domain)); space = isl_space_add_dims(space, isl_dim_out, 1); @@ -2659,6 +2789,9 @@ struct pet_scop *PetScan::extract_for(ForStmt *stmt) isl_map_copy(sched), isl_map_copy(wrap), isl_id_copy(id)); scop = pet_scop_embed(scop, isl_set_copy(domain), sched, wrap, id); scop = resolve_nested(scop); + if (has_var_break) + scop = scop_add_break(scop, break_access, isl_set_copy(domain), + isl_int_sgn(inc)); if (test_access) { scop = scop_add_while(scop_cond, scop, test_access, domain, isl_int_sgn(inc)); @@ -3409,11 +3542,20 @@ static bool is_assigned(pet_expr *expr, pet_scop *scop) /* Are all nested access parameters in "pa" allowed given "scop". * In particular, is none of them written by anywhere inside "scop". + * + * If "scop" has any skip conditions, then no nested access parameters + * are allowed. In particular, if there is any nested access in a guard + * for a piece of code containing a "continue", then we want to introduce + * a separate statement for evaluating this guard so that we can express + * that the result is false for all previous iterations. */ bool PetScan::is_nested_allowed(__isl_keep isl_pw_aff *pa, pet_scop *scop) { int nparam; + if (!scop) + return true; + nparam = isl_pw_aff_dim(pa, isl_dim_param); for (int i = 0; i < nparam; ++i) { Expr *nested; @@ -3426,6 +3568,11 @@ bool PetScan::is_nested_allowed(__isl_keep isl_pw_aff *pa, pet_scop *scop) continue; } + if (pet_scop_has_skip(scop, pet_skip_now)) { + isl_id_free(id); + return false; + } + nested = (Expr *) isl_id_get_user(id); expr = extract_expr(nested); allowed = expr && expr->type == pet_expr_access && @@ -3441,6 +3588,332 @@ bool PetScan::is_nested_allowed(__isl_keep isl_pw_aff *pa, pet_scop *scop) return true; } +/* Do we need to construct a skip condition of the given type + * on an if statement, given that the if condition is non-affine? + * + * pet_scop_filter_skip can only handle the case where the if condition + * holds (the then branch) and the skip condition is universal. + * In any other case, we need to construct a new skip condition. + */ +static bool need_skip(struct pet_scop *scop_then, struct pet_scop *scop_else, + bool have_else, enum pet_skip type) +{ + if (have_else && scop_else && pet_scop_has_skip(scop_else, type)) + return true; + if (scop_then && pet_scop_has_skip(scop_then, type) && + !pet_scop_has_universal_skip(scop_then, type)) + return true; + return false; +} + +/* Do we need to construct a skip condition of the given type + * on an if statement, given that the if condition is affine? + * + * There is no need to construct a new skip condition if all + * the skip conditions are affine. + */ +static bool need_skip_aff(struct pet_scop *scop_then, + struct pet_scop *scop_else, bool have_else, enum pet_skip type) +{ + if (scop_then && pet_scop_has_var_skip(scop_then, type)) + return true; + if (have_else && scop_else && pet_scop_has_var_skip(scop_else, type)) + return true; + return false; +} + +/* Do we need to construct a skip condition of the given type + * on an if statement? + */ +static bool need_skip(struct pet_scop *scop_then, struct pet_scop *scop_else, + bool have_else, enum pet_skip type, bool affine) +{ + if (affine) + return need_skip_aff(scop_then, scop_else, have_else, type); + else + return need_skip(scop_then, scop_else, have_else, type); +} + +/* Construct an affine expression pet_expr that is evaluates + * to the constant "val". + */ +static struct pet_expr *universally(isl_ctx *ctx, int val) +{ + isl_space *space; + isl_map *map; + + space = isl_space_alloc(ctx, 0, 0, 1); + map = isl_map_universe(space); + map = isl_map_fix_si(map, isl_dim_out, 0, val); + + return pet_expr_from_access(map); +} + +/* Construct an affine expression pet_expr that is evaluates + * to the constant 1. + */ +static struct pet_expr *universally_true(isl_ctx *ctx) +{ + return universally(ctx, 1); +} + +/* Construct an affine expression pet_expr that is evaluates + * to the constant 0. + */ +static struct pet_expr *universally_false(isl_ctx *ctx) +{ + return universally(ctx, 0); +} + +/* Given an access relation "test_access" for the if condition, + * an access relation "skip_access" for the skip condition and + * scops for the then and else branches, construct a scop for + * computing "skip_access". + * + * The computed scop contains a single statement that essentially does + * + * skip_cond = test_cond ? skip_cond_then : skip_cond_else + * + * If the skip conditions of the then and/or else branch are not affine, + * then they need to be filtered by test_access. + * If they are missing, then this means the skip condition is false. + * + * Since we are constructing a skip condition for the if statement, + * the skip conditions on the then and else branches are removed. + */ +static struct pet_scop *extract_skip(PetScan *scan, + __isl_take isl_map *test_access, __isl_take isl_map *skip_access, + struct pet_scop *scop_then, struct pet_scop *scop_else, bool have_else, + enum pet_skip type) +{ + struct pet_expr *expr_then, *expr_else, *expr, *expr_skip; + struct pet_stmt *stmt; + struct pet_scop *scop; + isl_ctx *ctx = scan->ctx; + + if (!scop_then) + goto error; + if (have_else && !scop_else) + goto error; + + if (pet_scop_has_skip(scop_then, type)) { + expr_then = pet_scop_get_skip_expr(scop_then, type); + pet_scop_reset_skip(scop_then, type); + if (!pet_expr_is_affine(expr_then)) + expr_then = pet_expr_filter(expr_then, + isl_map_copy(test_access), 1); + } else + expr_then = universally_false(ctx); + + if (have_else && pet_scop_has_skip(scop_else, type)) { + expr_else = pet_scop_get_skip_expr(scop_else, type); + pet_scop_reset_skip(scop_else, type); + if (!pet_expr_is_affine(expr_else)) + expr_else = pet_expr_filter(expr_else, + isl_map_copy(test_access), 0); + } else + expr_else = universally_false(ctx); + + expr = pet_expr_from_access(test_access); + expr = pet_expr_new_ternary(ctx, expr, expr_then, expr_else); + expr_skip = pet_expr_from_access(isl_map_copy(skip_access)); + if (expr_skip) { + expr_skip->acc.write = 1; + expr_skip->acc.read = 0; + } + expr = pet_expr_new_binary(ctx, pet_op_assign, expr_skip, expr); + stmt = pet_stmt_from_pet_expr(ctx, -1, NULL, scan->n_stmt++, expr); + + scop = pet_scop_from_pet_stmt(ctx, stmt); + scop = scop_add_array(scop, skip_access, scan->ast_context); + isl_map_free(skip_access); + + return scop; +error: + isl_map_free(test_access); + isl_map_free(skip_access); + return NULL; +} + +/* Is scop's skip_now condition equal to its skip_later condition? + * In particular, this means that it either has no skip_now condition + * or both a skip_now and a skip_later condition (that are equal to each other). + */ +static bool skip_equals_skip_later(struct pet_scop *scop) +{ + int has_skip_now, has_skip_later; + int equal; + isl_set *skip_now, *skip_later; + + if (!scop) + return false; + has_skip_now = pet_scop_has_skip(scop, pet_skip_now); + has_skip_later = pet_scop_has_skip(scop, pet_skip_later); + if (has_skip_now != has_skip_later) + return false; + if (!has_skip_now) + return true; + + skip_now = pet_scop_get_skip(scop, pet_skip_now); + skip_later = pet_scop_get_skip(scop, pet_skip_later); + equal = isl_set_is_equal(skip_now, skip_later); + isl_set_free(skip_now); + isl_set_free(skip_later); + + return equal; +} + +/* Drop the skip conditions of type pet_skip_later from scop1 and scop2. + */ +static void drop_skip_later(struct pet_scop *scop1, struct pet_scop *scop2) +{ + pet_scop_reset_skip(scop1, pet_skip_later); + pet_scop_reset_skip(scop2, pet_skip_later); +} + +/* Structure that handles the construction of skip conditions. + * + * scop_then and scop_else represent the then and else branches + * of the if statement + * + * skip[type] is true if we need to construct a skip condition of that type + * equal is set if the skip conditions of types pet_skip_now and pet_skip_later + * are equal to each other + * access[type] is the virtual array representing the skip condition + * scop[type] is a scop for computing the skip condition + */ +struct pet_skip_info { + isl_ctx *ctx; + + bool skip[2]; + bool equal; + isl_map *access[2]; + struct pet_scop *scop[2]; + + pet_skip_info(isl_ctx *ctx) : ctx(ctx) {} + + operator bool() { return skip[pet_skip_now] || skip[pet_skip_later]; } +}; + +/* Structure that handles the construction of skip conditions on if statements. + * + * scop_then and scop_else represent the then and else branches + * of the if statement + */ +struct pet_skip_info_if : public pet_skip_info { + struct pet_scop *scop_then, *scop_else; + bool have_else; + + pet_skip_info_if(isl_ctx *ctx, struct pet_scop *scop_then, + struct pet_scop *scop_else, bool have_else, bool affine); + void extract(PetScan *scan, __isl_keep isl_map *access, + enum pet_skip type); + void extract(PetScan *scan, __isl_keep isl_map *access); + void extract(PetScan *scan, __isl_keep isl_pw_aff *cond); + struct pet_scop *add(struct pet_scop *scop, enum pet_skip type, + int offset); + struct pet_scop *add(struct pet_scop *scop, int offset); +}; + +/* Initialize a pet_skip_info_if structure based on the then and else branches + * and based on whether the if condition is affine or not. + */ +pet_skip_info_if::pet_skip_info_if(isl_ctx *ctx, struct pet_scop *scop_then, + struct pet_scop *scop_else, bool have_else, bool affine) : + pet_skip_info(ctx), scop_then(scop_then), scop_else(scop_else), + have_else(have_else) +{ + skip[pet_skip_now] = + need_skip(scop_then, scop_else, have_else, pet_skip_now, affine); + equal = skip[pet_skip_now] && skip_equals_skip_later(scop_then) && + (!have_else || skip_equals_skip_later(scop_else)); + skip[pet_skip_later] = skip[pet_skip_now] && !equal && + need_skip(scop_then, scop_else, have_else, pet_skip_later, affine); +} + +/* If we need to construct a skip condition of the given type, + * then do so now. + * + * "map" represents the if condition. + */ +void pet_skip_info_if::extract(PetScan *scan, __isl_keep isl_map *map, + enum pet_skip type) +{ + if (!skip[type]) + return; + + access[type] = create_test_access(isl_map_get_ctx(map), scan->n_test++); + scop[type] = extract_skip(scan, isl_map_copy(map), + isl_map_copy(access[type]), + scop_then, scop_else, have_else, type); +} + +/* Construct the required skip conditions, given the if condition "map". + */ +void pet_skip_info_if::extract(PetScan *scan, __isl_keep isl_map *map) +{ + extract(scan, map, pet_skip_now); + extract(scan, map, pet_skip_later); + if (equal) + drop_skip_later(scop_then, scop_else); +} + +/* Construct the required skip conditions, given the if condition "cond". + */ +void pet_skip_info_if::extract(PetScan *scan, __isl_keep isl_pw_aff *cond) +{ + isl_set *test_set; + isl_map *test; + + if (!skip[pet_skip_now] && !skip[pet_skip_later]) + return; + + test_set = isl_set_from_pw_aff(isl_pw_aff_copy(cond)); + test = isl_map_from_range(test_set); + extract(scan, test); + isl_map_free(test); +} + +/* Add the computed skip condition of the give type to "main" and + * add the scop for computing the condition at the given offset. + * + * If equal is set, then we only computed a skip condition for pet_skip_now, + * but we also need to set it as main's pet_skip_later. + */ +struct pet_scop *pet_skip_info_if::add(struct pet_scop *main, + enum pet_skip type, int offset) +{ + isl_set *skip_set; + + if (!skip[type]) + return main; + + skip_set = isl_map_range(access[type]); + access[type] = NULL; + scop[type] = pet_scop_prefix(scop[type], offset); + main = pet_scop_add_par(ctx, main, scop[type]); + scop[type] = NULL; + + if (equal) + main = pet_scop_set_skip(main, pet_skip_later, + isl_set_copy(skip_set)); + + main = pet_scop_set_skip(main, type, skip_set); + + return main; +} + +/* Add the computed skip conditions to "main" and + * add the scops for computing the conditions at the given offset. + */ +struct pet_scop *pet_skip_info_if::add(struct pet_scop *scop, int offset) +{ + scop = add(scop, pet_skip_now, offset); + scop = add(scop, pet_skip_later, offset); + + return scop; +} + /* Construct a pet_scop for a non-affine if statement. * * We create a separate statement that writes the result @@ -3451,6 +3924,12 @@ bool PetScan::is_nested_allowed(__isl_keep isl_pw_aff *pa, pet_scop *scop) * to be zero is added to the iteration domains of the else branch, if any. * We adjust the schedules to ensure that the virtual scalar is written * before it is read. + * + * If there are any breaks or continues in the then and/or else + * branches, then we may have to compute a new skip condition. + * This is handled using a pet_skip_info_if object. + * On initialization, the object checks if skip conditions need + * to be computed. If so, it does so in "extract" and adds them in "add". */ struct pet_scop *PetScan::extract_non_affine_if(Expr *cond, struct pet_scop *scop_then, struct pet_scop *scop_else, @@ -3466,17 +3945,22 @@ struct pet_scop *PetScan::extract_non_affine_if(Expr *cond, n_stmt = save_n_stmt; scop = scop_add_array(scop, test_access, ast_context); + pet_skip_info_if skip(ctx, scop_then, scop_else, have_else, false); + skip.extract(this, test_access); + scop = pet_scop_prefix(scop, 0); scop_then = pet_scop_prefix(scop_then, 1); scop_then = pet_scop_filter(scop_then, isl_map_copy(test_access), 1); if (have_else) { scop_else = pet_scop_prefix(scop_else, 1); scop_else = pet_scop_filter(scop_else, test_access, 0); - scop_then = pet_scop_add(ctx, scop_then, scop_else); + scop_then = pet_scop_add_par(ctx, scop_then, scop_else); } else isl_map_free(test_access); - scop = pet_scop_add(ctx, scop, scop_then); + scop = pet_scop_add_seq(ctx, scop, scop_then); + + scop = skip.add(scop, 2); return scop; } @@ -3508,10 +3992,16 @@ struct pet_scop *PetScan::extract_non_affine_if(Expr *cond, * * If the condition is not affine, then the scop is created in * extract_non_affine_if. + * + * If there are any breaks or continues in the then and/or else + * branches, then we may have to compute a new skip condition. + * This is handled using a pet_skip_info_if object. + * On initialization, the object checks if skip conditions need + * to be computed. If so, it does so in "extract" and adds them in "add". */ struct pet_scop *PetScan::extract(IfStmt *stmt) { - struct pet_scop *scop_then, *scop_else, *scop; + struct pet_scop *scop_then, *scop_else = NULL, *scop; isl_pw_aff *cond; int stmt_id; isl_set *set; @@ -3559,6 +4049,10 @@ struct pet_scop *PetScan::extract(IfStmt *stmt) if (!cond) cond = extract_condition(stmt->getCond()); + + pet_skip_info_if skip(ctx, scop_then, scop_else, stmt->getElse(), true); + skip.extract(this, cond); + valid = isl_pw_aff_domain(isl_pw_aff_copy(cond)); set = isl_pw_aff_non_zero_set(cond); scop = pet_scop_restrict(scop_then, isl_set_copy(set)); @@ -3566,12 +4060,16 @@ struct pet_scop *PetScan::extract(IfStmt *stmt) if (stmt->getElse()) { set = isl_set_subtract(isl_set_copy(valid), set); scop_else = pet_scop_restrict(scop_else, set); - scop = pet_scop_add(ctx, scop, scop_else); + scop = pet_scop_add_par(ctx, scop, scop_else); } else isl_set_free(set); scop = resolve_nested(scop); scop = pet_scop_restrict_context(scop, valid); + if (skip) + scop = pet_scop_prefix(scop, 0); + scop = skip.add(scop, 1); + return scop; } @@ -3594,6 +4092,58 @@ struct pet_scop *PetScan::extract(LabelStmt *stmt) return extract(sub, extract_expr(cast(sub)), label); } +/* Construct a pet_scop for a continue statement. + * + * We simply create an empty scop with a universal pet_skip_now + * skip condition. This skip condition will then be taken into + * account by the enclosing loop construct, possibly after + * being incorporated into outer skip conditions. + */ +struct pet_scop *PetScan::extract(ContinueStmt *stmt) +{ + pet_scop *scop; + isl_space *space; + isl_set *set; + + scop = pet_scop_empty(ctx); + if (!scop) + return NULL; + + space = isl_space_set_alloc(ctx, 0, 1); + set = isl_set_universe(space); + set = isl_set_fix_si(set, isl_dim_set, 0, 1); + scop = pet_scop_set_skip(scop, pet_skip_now, set); + + return scop; +} + +/* Construct a pet_scop for a break statement. + * + * We simply create an empty scop with both a universal pet_skip_now + * skip condition and a universal pet_skip_later skip condition. + * These skip conditions will then be taken into + * account by the enclosing loop construct, possibly after + * being incorporated into outer skip conditions. + */ +struct pet_scop *PetScan::extract(BreakStmt *stmt) +{ + pet_scop *scop; + isl_space *space; + isl_set *set; + + scop = pet_scop_empty(ctx); + if (!scop) + return NULL; + + space = isl_space_set_alloc(ctx, 0, 1); + set = isl_set_universe(space); + set = isl_set_fix_si(set, isl_dim_set, 0, 1); + scop = pet_scop_set_skip(scop, pet_skip_now, isl_set_copy(set)); + scop = pet_scop_set_skip(scop, pet_skip_later, set); + + return scop; +} + /* Try and construct a pet_scop corresponding to "stmt". */ struct pet_scop *PetScan::extract(Stmt *stmt) @@ -3612,6 +4162,10 @@ struct pet_scop *PetScan::extract(Stmt *stmt) return extract(cast(stmt)); case Stmt::LabelStmtClass: return extract(cast(stmt)); + case Stmt::ContinueStmtClass: + return extract(cast(stmt)); + case Stmt::BreakStmtClass: + return extract(cast(stmt)); default: unsupported(stmt); } @@ -3619,8 +4173,188 @@ struct pet_scop *PetScan::extract(Stmt *stmt) return NULL; } +/* Do we need to construct a skip condition of the given type + * on a sequence of statements? + * + * There is no need to construct a new skip condition if only + * only of the two statements has a skip condition or if both + * of their skip conditions are affine. + * + * In principle we also don't need a new continuation variable if + * the continuation of scop2 is affine, but then we would need + * to allow more complicated forms of continuations. + */ +static bool need_skip_seq(struct pet_scop *scop1, struct pet_scop *scop2, + enum pet_skip type) +{ + if (!scop1 || !pet_scop_has_skip(scop1, type)) + return false; + if (!scop2 || !pet_scop_has_skip(scop2, type)) + return false; + if (pet_scop_has_affine_skip(scop1, type) && + pet_scop_has_affine_skip(scop2, type)) + return false; + return true; +} + +/* Construct a scop for computing the skip condition of the given type and + * with access relation "skip_access" for a sequence of two scops "scop1" + * and "scop2". + * + * The computed scop contains a single statement that essentially does + * + * skip_cond = skip_cond_1 ? 1 : skip_cond_2 + * + * or, in other words, skip_cond1 || skip_cond2. + * In this expression, skip_cond_2 is filtered to reflect that it is + * only evaluated when skip_cond_1 is false. + * + * The skip condition on scop1 is not removed because it still needs + * to be applied to scop2 when these two scops are combined. + */ +static struct pet_scop *extract_skip_seq(PetScan *ps, + __isl_take isl_map *skip_access, + struct pet_scop *scop1, struct pet_scop *scop2, enum pet_skip type) +{ + isl_map *access; + struct pet_expr *expr1, *expr2, *expr, *expr_skip; + struct pet_stmt *stmt; + struct pet_scop *scop; + isl_ctx *ctx = ps->ctx; + + if (!scop1 || !scop2) + goto error; + + expr1 = pet_scop_get_skip_expr(scop1, type); + expr2 = pet_scop_get_skip_expr(scop2, type); + pet_scop_reset_skip(scop2, type); + + expr2 = pet_expr_filter(expr2, isl_map_copy(expr1->acc.access), 0); + + expr = universally_true(ctx); + expr = pet_expr_new_ternary(ctx, expr1, expr, expr2); + expr_skip = pet_expr_from_access(isl_map_copy(skip_access)); + if (expr_skip) { + expr_skip->acc.write = 1; + expr_skip->acc.read = 0; + } + expr = pet_expr_new_binary(ctx, pet_op_assign, expr_skip, expr); + stmt = pet_stmt_from_pet_expr(ctx, -1, NULL, ps->n_stmt++, expr); + + scop = pet_scop_from_pet_stmt(ctx, stmt); + scop = scop_add_array(scop, skip_access, ps->ast_context); + isl_map_free(skip_access); + + return scop; +error: + isl_map_free(skip_access); + return NULL; +} + +/* Structure that handles the construction of skip conditions + * on sequences of statements. + * + * scop1 and scop2 represent the two statements that are combined + */ +struct pet_skip_info_seq : public pet_skip_info { + struct pet_scop *scop1, *scop2; + + pet_skip_info_seq(isl_ctx *ctx, struct pet_scop *scop1, + struct pet_scop *scop2); + void extract(PetScan *scan, enum pet_skip type); + void extract(PetScan *scan); + struct pet_scop *add(struct pet_scop *scop, enum pet_skip type, + int offset); + struct pet_scop *add(struct pet_scop *scop, int offset); +}; + +/* Initialize a pet_skip_info_seq structure based on + * on the two statements that are going to be combined. + */ +pet_skip_info_seq::pet_skip_info_seq(isl_ctx *ctx, struct pet_scop *scop1, + struct pet_scop *scop2) : pet_skip_info(ctx), scop1(scop1), scop2(scop2) +{ + skip[pet_skip_now] = need_skip_seq(scop1, scop2, pet_skip_now); + equal = skip[pet_skip_now] && skip_equals_skip_later(scop1) && + skip_equals_skip_later(scop2); + skip[pet_skip_later] = skip[pet_skip_now] && !equal && + need_skip_seq(scop1, scop2, pet_skip_later); +} + +/* If we need to construct a skip condition of the given type, + * then do so now. + */ +void pet_skip_info_seq::extract(PetScan *scan, enum pet_skip type) +{ + if (!skip[type]) + return; + + access[type] = create_test_access(ctx, scan->n_test++); + scop[type] = extract_skip_seq(scan, isl_map_copy(access[type]), + scop1, scop2, type); +} + +/* Construct the required skip conditions. + */ +void pet_skip_info_seq::extract(PetScan *scan) +{ + extract(scan, pet_skip_now); + extract(scan, pet_skip_later); + if (equal) + drop_skip_later(scop1, scop2); +} + +/* Add the computed skip condition of the give type to "main" and + * add the scop for computing the condition at the given offset (the statement + * number). Within this offset, the condition is computed at position 1 + * to ensure that it is computed after the corresponding statement. + * + * If equal is set, then we only computed a skip condition for pet_skip_now, + * but we also need to set it as main's pet_skip_later. + */ +struct pet_scop *pet_skip_info_seq::add(struct pet_scop *main, + enum pet_skip type, int offset) +{ + isl_set *skip_set; + + if (!skip[type]) + return main; + + skip_set = isl_map_range(access[type]); + access[type] = NULL; + scop[type] = pet_scop_prefix(scop[type], 1); + scop[type] = pet_scop_prefix(scop[type], offset); + main = pet_scop_add_par(ctx, main, scop[type]); + scop[type] = NULL; + + if (equal) + main = pet_scop_set_skip(main, pet_skip_later, + isl_set_copy(skip_set)); + + main = pet_scop_set_skip(main, type, skip_set); + + return main; +} + +/* Add the computed skip conditions to "main" and + * add the scops for computing the conditions at the given offset. + */ +struct pet_scop *pet_skip_info_seq::add(struct pet_scop *scop, int offset) +{ + scop = add(scop, pet_skip_now, offset); + scop = add(scop, pet_skip_later, offset); + + return scop; +} + /* Try and construct a pet_scop corresponding to (part of) * a sequence of statements. + * + * If there are any breaks or continues in the individual statements, + * then we may have to compute a new skip condition. + * This is handled using a pet_skip_info_seq object. + * On initialization, the object checks if skip conditions need + * to be computed. If so, it does so in "extract" and adds them in "add". */ struct pet_scop *PetScan::extract(StmtRange stmt_range) { @@ -3633,22 +4367,30 @@ struct pet_scop *PetScan::extract(StmtRange stmt_range) for (i = stmt_range.first, j = 0; i != stmt_range.second; ++i, ++j) { Stmt *child = *i; struct pet_scop *scop_i; + scop_i = extract(child); if (scop && partial) { pet_scop_free(scop_i); break; } + pet_skip_info_seq skip(ctx, scop, scop_i); + skip.extract(this); + if (skip) + scop_i = pet_scop_prefix(scop_i, 0); scop_i = pet_scop_prefix(scop_i, j); if (options->autodetect) { if (scop_i) - scop = pet_scop_add(ctx, scop, scop_i); + scop = pet_scop_add_seq(ctx, scop, scop_i); else partial_range = true; if (scop->n_stmt != 0 && !scop_i) partial = true; } else { - scop = pet_scop_add(ctx, scop, scop_i); + scop = pet_scop_add_seq(ctx, scop, scop_i); } + + scop = skip.add(scop, j); + if (partial) break; } diff --git a/scan.h b/scan.h index 7e56930..d18e62c 100644 --- a/scan.h +++ b/scan.h @@ -101,6 +101,8 @@ private: struct pet_scop *extract(clang::WhileStmt *stmt); struct pet_scop *extract(clang::CompoundStmt *stmt); struct pet_scop *extract(clang::LabelStmt *stmt); + struct pet_scop *extract(clang::ContinueStmt *stmt); + struct pet_scop *extract(clang::BreakStmt *stmt); struct pet_scop *extract(clang::Stmt *stmt, struct pet_expr *expr, __isl_take isl_id *label = NULL); diff --git a/scop.c b/scop.c index cb04ae4..c36bad2 100644 --- a/scop.c +++ b/scop.c @@ -70,6 +70,28 @@ static char *op_str[] = { [pet_op_address_of] = "&" }; +/* pet_scop with extra information that is only used during parsing. + * + * In particular, we keep track of conditions under which we want + * to skip the rest of the current loop iteration (skip[pet_skip_now]) + * and of conditions under which we want to skip subsequent + * loop iterations (skip[pet_skip_later]). + * + * The conditions are represented either by a variable, which + * is assumed to attain values zero and one, or by a boolean affine + * expression. The condition holds if the variable has value one + * or if the affine expression has value one (typically for only + * part of the parameter space). + * + * A missing condition (skip[type] == NULL) means that we don't want + * to skip anything. + */ +struct pet_scop_ext { + struct pet_scop scop; + + isl_set *skip[2]; +}; + const char *pet_op_str(enum pet_op_type op) { return op_str[op]; @@ -646,9 +668,12 @@ void pet_array_dump(struct pet_array *array) array->live_out ? "live-out" : ""); } +/* Alloc a pet_scop structure, with extra room for information that + * is only used during parsing. + */ struct pet_scop *pet_scop_alloc(isl_ctx *ctx) { - return isl_calloc_type(ctx, struct pet_scop); + return &isl_calloc_type(ctx, struct pet_scop_ext)->scop; } /* Construct a pet_scop with room for n statements. @@ -785,10 +810,98 @@ error: return NULL; } -/* Construct a pet_scop that contains the arrays and the statements - * in "scop1" and "scop2". +/* Does "set" represent an element of an unnamed space, i.e., + * does it represent an affine expression? + */ +static int set_is_affine(__isl_keep isl_set *set) +{ + int has_id; + + has_id = isl_set_has_tuple_id(set); + if (has_id < 0) + return -1; + + return !has_id; +} + +/* Combine ext1->skip[type] and ext2->skip[type] into ext->skip[type]. + * ext may be equal to either ext1 or ext2. + * + * The two skips that need to be combined are assumed to be affine expressions. + * + * We need to skip in ext if we need to skip in either ext1 or ext2. + * We don't need to skip in ext if we don't need to skip in both ext1 and ext2. */ -struct pet_scop *pet_scop_add(isl_ctx *ctx, struct pet_scop *scop1, +static struct pet_scop_ext *combine_skips(struct pet_scop_ext *ext, + struct pet_scop_ext *ext1, struct pet_scop_ext *ext2, + enum pet_skip type) +{ + isl_set *set, *skip1, *skip2; + + if (!ext) + return NULL; + if (!ext1->skip[type] && !ext2->skip[type]) + return ext; + if (!ext1->skip[type]) { + if (ext == ext2) + return ext; + ext->skip[type] = ext2->skip[type]; + ext2->skip[type] = NULL; + return ext; + } + if (!ext2->skip[type]) { + if (ext == ext1) + return ext; + ext->skip[type] = ext1->skip[type]; + ext1->skip[type] = NULL; + return ext; + } + + if (!set_is_affine(ext1->skip[type]) || + !set_is_affine(ext2->skip[type])) + isl_die(isl_set_get_ctx(ext1->skip[type]), isl_error_internal, + "can only combine affine skips", + return pet_scop_free(&ext->scop)); + + skip1 = isl_set_copy(ext1->skip[type]); + skip2 = isl_set_copy(ext2->skip[type]); + set = isl_set_intersect( + isl_set_fix_si(isl_set_copy(skip1), isl_dim_set, 0, 0), + isl_set_fix_si(isl_set_copy(skip2), isl_dim_set, 0, 0)); + set = isl_set_union(set, isl_set_fix_si(skip1, isl_dim_set, 0, 1)); + set = isl_set_union(set, isl_set_fix_si(skip2, isl_dim_set, 0, 1)); + set = isl_set_coalesce(set); + isl_set_free(ext1->skip[type]); + ext1->skip[type] = NULL; + isl_set_free(ext2->skip[type]); + ext2->skip[type] = NULL; + ext->skip[type] = set; + if (!ext->skip[type]) + return pet_scop_free(&ext->scop); + + return ext; +} + +/* Combine scop1->skip[type] and scop2->skip[type] into scop->skip[type], + * where type takes on the values pet_skip_now and pet_skip_later. + * scop may be equal to either scop1 or scop2. + */ +static struct pet_scop *scop_combine_skips(struct pet_scop *scop, + struct pet_scop *scop1, struct pet_scop *scop2) +{ + struct pet_scop_ext *ext = (struct pet_scop_ext *) scop; + struct pet_scop_ext *ext1 = (struct pet_scop_ext *) scop1; + struct pet_scop_ext *ext2 = (struct pet_scop_ext *) scop2; + + ext = combine_skips(ext, ext1, ext2, pet_skip_now); + ext = combine_skips(ext, ext1, ext2, pet_skip_later); + return &ext->scop; +} + +/* Construct a pet_scop that contains the arrays, statements and + * skip information in "scop1" and "scop2". + */ +static struct pet_scop *pet_scop_add(isl_ctx *ctx, struct pet_scop *scop1, struct pet_scop *scop2) { int i; @@ -798,11 +911,13 @@ struct pet_scop *pet_scop_add(isl_ctx *ctx, struct pet_scop *scop1, goto error; if (scop1->n_stmt == 0) { + scop2 = scop_combine_skips(scop2, scop1, scop2); pet_scop_free(scop1); return scop2; } if (scop2->n_stmt == 0) { + scop1 = scop_combine_skips(scop1, scop1, scop2); pet_scop_free(scop2); return scop1; } @@ -839,6 +954,7 @@ struct pet_scop *pet_scop_add(isl_ctx *ctx, struct pet_scop *scop1, scop = pet_scop_restrict_context(scop, isl_set_copy(scop1->context)); scop = pet_scop_restrict_context(scop, isl_set_copy(scop2->context)); + scop = scop_combine_skips(scop, scop1, scop2); pet_scop_free(scop1); pet_scop_free(scop2); @@ -849,9 +965,67 @@ error: return NULL; } +/* Apply the skip condition "skip" to "scop". + * That is, make sure "scop" is not executed when the condition holds. + * + * If "skip" is an affine expression, we add the conditions under + * which the expression is zero to the iteration domains. + * Otherwise, we add a filter on the variable attaining the value zero. + */ +static struct pet_scop *restrict_skip(struct pet_scop *scop, + __isl_take isl_set *skip) +{ + isl_map *skip_map; + int is_aff; + + if (!scop || !skip) + goto error; + + is_aff = set_is_affine(skip); + if (is_aff < 0) + goto error; + + if (!is_aff) + return pet_scop_filter(scop, isl_map_from_range(skip), 0); + + skip = isl_set_fix_si(skip, isl_dim_set, 0, 0); + scop = pet_scop_restrict(scop, isl_set_params(skip)); + + return scop; +error: + isl_set_free(skip); + return pet_scop_free(scop); +} + +/* Construct a pet_scop that contains the arrays, statements and + * skip information in "scop1" and "scop2", where the two scops + * are executed "in sequence". That is, breaks and continues + * in scop1 have an effect on scop2. + */ +struct pet_scop *pet_scop_add_seq(isl_ctx *ctx, struct pet_scop *scop1, + struct pet_scop *scop2) +{ + if (scop1 && pet_scop_has_skip(scop1, pet_skip_now)) + scop2 = restrict_skip(scop2, + pet_scop_get_skip(scop1, pet_skip_now)); + return pet_scop_add(ctx, scop1, scop2); +} + +/* Construct a pet_scop that contains the arrays, statements and + * skip information in "scop1" and "scop2", where the two scops + * are executed "in parallel". That is, any break or continue + * in scop1 has no effect on scop2. + */ +struct pet_scop *pet_scop_add_par(isl_ctx *ctx, struct pet_scop *scop1, + struct pet_scop *scop2) +{ + return pet_scop_add(ctx, scop1, scop2); +} + void *pet_scop_free(struct pet_scop *scop) { int i; + struct pet_scop_ext *ext = (struct pet_scop_ext *) scop; if (!scop) return NULL; @@ -865,6 +1039,8 @@ void *pet_scop_free(struct pet_scop *scop) for (i = 0; i < scop->n_stmt; ++i) pet_stmt_free(scop->stmts[i]); free(scop->stmts); + isl_set_free(ext->skip[pet_skip_now]); + isl_set_free(ext->skip[pet_skip_later]); free(scop); return NULL; } @@ -872,6 +1048,7 @@ void *pet_scop_free(struct pet_scop *scop) void pet_scop_dump(struct pet_scop *scop) { int i; + struct pet_scop_ext *ext = (struct pet_scop_ext *) scop; if (!scop) return; @@ -882,6 +1059,12 @@ void pet_scop_dump(struct pet_scop *scop) pet_array_dump(scop->arrays[i]); for (i = 0; i < scop->n_stmt; ++i) pet_stmt_dump(scop->stmts[i]); + + if (ext->skip[0]) { + fprintf(stderr, "skip\n"); + isl_set_dump(ext->skip[0]); + isl_set_dump(ext->skip[1]); + } } /* Return 1 if the two pet_arrays are equivalent. @@ -1317,6 +1500,10 @@ static __isl_give isl_set *context_embed(__isl_take isl_set *context, * "iv_map" maps a possibly virtual iterator to the real iterator. * That is, it maps the iterator used in "dom" and the domain of "sched" * to the iterator that some of the parameters in "scop" may refer to. + * + * Any skip conditions within the loop have no effect outside of the loop. + * The caller is responsible for making sure skip[pet_skip_later] has been + * taken into account. */ struct pet_scop *pet_scop_embed(struct pet_scop *scop, __isl_take isl_set *dom, __isl_take isl_map *sched, __isl_take isl_map *iv_map, @@ -1327,6 +1514,9 @@ struct pet_scop *pet_scop_embed(struct pet_scop *scop, __isl_take isl_set *dom, if (!scop) goto error; + pet_scop_reset_skip(scop, pet_skip_now); + pet_scop_reset_skip(scop, pet_skip_later); + scop->context = context_embed(scop->context, dom, iv_map, id); if (!scop->context) goto error; @@ -1375,7 +1565,47 @@ error: return pet_stmt_free(stmt); } -/* Add extra conditions on the parameters to all iteration domains. +/* Add extra conditions to scop->skip[type]. + * + * The new skip condition only holds if it held before + * and the condition is true. It does not hold if it did not hold + * before or the condition is false. + * + * The skip condition is assumed to be an affine expression. + */ +static struct pet_scop *pet_scop_restrict_skip(struct pet_scop *scop, + enum pet_skip type, __isl_keep isl_set *cond) +{ + struct pet_scop_ext *ext = (struct pet_scop_ext *) scop; + isl_set *skip; + isl_set *set; + + if (!scop) + return NULL; + if (!ext->skip[type]) + return scop; + + if (!set_is_affine(ext->skip[type])) + isl_die(isl_set_get_ctx(ext->skip[type]), isl_error_internal, + "can only resrict affine skips", + return pet_scop_free(scop)); + + skip = ext->skip[type]; + skip = isl_set_intersect_params(skip, isl_set_copy(cond)); + set = isl_set_from_params(isl_set_copy(cond)); + set = isl_set_complement(set); + set = isl_set_add_dims(set, isl_dim_set, 1); + set = isl_set_fix_si(set, isl_dim_set, 0, 0); + skip = isl_set_union(skip, set); + ext->skip[type] = skip; + if (!ext->skip[type]) + return pet_scop_free(scop); + + return scop; +} + +/* Add extra conditions on the parameters to all iteration domains + * and skip conditions. * * A parameter value is valid for the result if it was valid * for the original scop and satisfies "cond" or if it does @@ -1387,6 +1617,9 @@ struct pet_scop *pet_scop_restrict(struct pet_scop *scop, { int i; + scop = pet_scop_restrict_skip(scop, pet_skip_now, cond); + scop = pet_scop_restrict_skip(scop, pet_skip_later, cond); + if (!scop) goto error; @@ -1592,6 +1825,170 @@ error: return pet_stmt_free(stmt); } +/* Does "scop" have a skip condition of the given "type"? + */ +int pet_scop_has_skip(struct pet_scop *scop, enum pet_skip type) +{ + struct pet_scop_ext *ext = (struct pet_scop_ext *) scop; + + if (!scop) + return -1; + return ext->skip[type] != NULL; +} + +/* Does "scop" have a skip condition of the given "type" that + * is an affine expression? + */ +int pet_scop_has_affine_skip(struct pet_scop *scop, enum pet_skip type) +{ + struct pet_scop_ext *ext = (struct pet_scop_ext *) scop; + + if (!scop) + return -1; + if (!ext->skip[type]) + return 0; + return set_is_affine(ext->skip[type]); +} + +/* Does "scop" have a skip condition of the given "type" that + * is not an affine expression? + */ +int pet_scop_has_var_skip(struct pet_scop *scop, enum pet_skip type) +{ + struct pet_scop_ext *ext = (struct pet_scop_ext *) scop; + int aff; + + if (!scop) + return -1; + if (!ext->skip[type]) + return 0; + aff = set_is_affine(ext->skip[type]); + if (aff < 0) + return -1; + return !aff; +} + +/* Does "scop" have a skip condition of the given "type" that + * is affine and holds on the entire domain? + */ +int pet_scop_has_universal_skip(struct pet_scop *scop, enum pet_skip type) +{ + struct pet_scop_ext *ext = (struct pet_scop_ext *) scop; + isl_set *set; + int is_aff; + int is_univ; + + is_aff = pet_scop_has_affine_skip(scop, type); + if (is_aff < 0 || !is_aff) + return is_aff; + + set = isl_set_copy(ext->skip[type]); + set = isl_set_fix_si(set, isl_dim_set, 0, 1); + set = isl_set_params(set); + is_univ = isl_set_plain_is_universe(set); + isl_set_free(set); + + return is_univ; +} + +/* Replace scop->skip[type] by "skip". + */ +struct pet_scop *pet_scop_set_skip(struct pet_scop *scop, + enum pet_skip type, __isl_take isl_set *skip) +{ + struct pet_scop_ext *ext = (struct pet_scop_ext *) scop; + + if (!scop || !skip) + goto error; + + isl_set_free(ext->skip[type]); + ext->skip[type] = skip; + + return scop; +error: + isl_set_free(skip); + return pet_scop_free(scop); +} + +/* Return a copy of scop->skip[type]. + */ +__isl_give isl_set *pet_scop_get_skip(struct pet_scop *scop, + enum pet_skip type) +{ + struct pet_scop_ext *ext = (struct pet_scop_ext *) scop; + + if (!scop) + return NULL; + + return isl_set_copy(ext->skip[type]); +} + +/* Return a map to the skip condition of the given type. + */ +__isl_give isl_map *pet_scop_get_skip_map(struct pet_scop *scop, + enum pet_skip type) +{ + return isl_map_from_range(pet_scop_get_skip(scop, type)); +} + +/* Return an access pet_expr corresponding to the skip condition + * of the given type. + */ +struct pet_expr *pet_scop_get_skip_expr(struct pet_scop *scop, + enum pet_skip type) +{ + return pet_expr_from_access(pet_scop_get_skip_map(scop, type)); +} + +/* Drop the the skip condition scop->skip[type]. + */ +void pet_scop_reset_skip(struct pet_scop *scop, enum pet_skip type) +{ + struct pet_scop_ext *ext = (struct pet_scop_ext *) scop; + + if (!scop) + return; + + isl_set_free(ext->skip[type]); + ext->skip[type] = NULL; +} + +/* Make the skip condition (if any) depend on the value of "test" being + * equal to "satisfied". + * + * We only support the case where the original skip condition is universal, + * i.e., where skipping is unconditional, and where satisfied == 1. + * In this case, the skip condition is changed to skip only when + * "test" is equal to one. + */ +static struct pet_scop *pet_scop_filter_skip(struct pet_scop *scop, + enum pet_skip type, __isl_keep isl_map *test, int satisfied) +{ + int is_univ = 0; + + if (!scop) + return NULL; + if (!pet_scop_has_skip(scop, type)) + return scop; + + if (satisfied) + is_univ = pet_scop_has_universal_skip(scop, type); + if (is_univ < 0) + return pet_scop_free(scop); + if (satisfied && is_univ) { + scop = pet_scop_set_skip(scop, type, + isl_map_range(isl_map_copy(test))); + if (!scop) + return NULL; + } else { + isl_die(isl_map_get_ctx(test), isl_error_internal, + "skip expression cannot be filtered", + return pet_scop_free(scop)); + } + + return scop; +} + /* Make all statements in "scop" depend on the value of "test" * being equal to "satisfied" by adjusting their domains. */ @@ -1600,7 +1997,10 @@ struct pet_scop *pet_scop_filter(struct pet_scop *scop, { int i; - if (!scop) + scop = pet_scop_filter_skip(scop, pet_skip_now, test, satisfied); + scop = pet_scop_filter_skip(scop, pet_skip_later, test, satisfied); + + if (!scop || !test) goto error; for (i = 0; i < scop->n_stmt; ++i) { diff --git a/scop.h b/scop.h index 317023f..df3367f 100644 --- a/scop.h +++ b/scop.h @@ -9,6 +9,11 @@ extern "C" { #endif +/* Do we want to skip the rest of the current loop iteration (pet_skip_now) + * or subsequent loop iterations (pet_skip_later)? + */ +enum pet_skip { pet_skip_now = 0, pet_skip_later = 1 }; + const char *pet_type_str(enum pet_expr_type type); enum pet_expr_type pet_str_type(const char *str); @@ -45,7 +50,9 @@ struct pet_stmt *pet_stmt_prefix(struct pet_stmt *stmt, int pos); struct pet_scop *pet_scop_from_pet_stmt(isl_ctx *ctx, struct pet_stmt *stmt); struct pet_scop *pet_scop_alloc(isl_ctx *ctx); struct pet_scop *pet_scop_empty(isl_ctx *ctx); -struct pet_scop *pet_scop_add(isl_ctx *ctx, struct pet_scop *scop1, +struct pet_scop *pet_scop_add_seq(isl_ctx *ctx, struct pet_scop *scop1, + struct pet_scop *scop2); +struct pet_scop *pet_scop_add_par(isl_ctx *ctx, struct pet_scop *scop1, struct pet_scop *scop2); int pet_scop_is_equal(struct pet_scop *scop1, struct pet_scop *scop2); @@ -77,6 +84,20 @@ struct pet_expr *pet_expr_foreach_access(struct pet_expr *expr, int pet_scop_writes(struct pet_scop *scop, __isl_keep isl_id *id); +int pet_scop_has_skip(struct pet_scop *scop, enum pet_skip type); +int pet_scop_has_affine_skip(struct pet_scop *scop, enum pet_skip type); +int pet_scop_has_universal_skip(struct pet_scop *scop, enum pet_skip type); +int pet_scop_has_var_skip(struct pet_scop *scop, enum pet_skip type); +struct pet_scop *pet_scop_set_skip(struct pet_scop *scop, + enum pet_skip type, __isl_take isl_set *skip); +__isl_give isl_set *pet_scop_get_skip(struct pet_scop *scop, + enum pet_skip type); +__isl_give isl_map *pet_scop_get_skip_map(struct pet_scop *scop, + enum pet_skip type); +struct pet_expr *pet_scop_get_skip_expr(struct pet_scop *scop, + enum pet_skip type); +void pet_scop_reset_skip(struct pet_scop *scop, enum pet_skip type); + #if defined(__cplusplus) } #endif diff --git a/tests/break.c b/tests/break.c new file mode 100644 index 0000000..70cf6e7 --- /dev/null +++ b/tests/break.c @@ -0,0 +1,14 @@ +void foo() +{ + int i, j, a[100]; + +#pragma scop + for (i = 0; i < 100; ++i) + for (j = 0; j < 100; ++j) { + a[i] = 0; + if (i == j) + break; + a[i] = i + j; + } +#pragma endscop +} diff --git a/tests/break.scop b/tests/break.scop new file mode 100644 index 0000000..045b7dd --- /dev/null +++ b/tests/break.scop @@ -0,0 +1,44 @@ +context: '{ : }' +arrays: +- context: '{ : }' + extent: '{ a[i0] : i0 >= 0 and i0 <= 99 }' + element_type: int + element_size: 4 +statements: +- line: 8 + domain: '{ S_0[i, j] : j >= 0 and j <= i and i <= 99 }' + schedule: '{ S_0[i, j] -> [0, i, j, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_0[i, j] -> a[i] }' + read: 0 + write: 1 + - type: access + relation: '{ S_0[i, j] -> [0] }' + read: 1 + write: 0 +- line: 11 + domain: '{ S_1[i, j] : j >= 0 and j <= -1 + i and i <= 99 }' + schedule: '{ S_1[i, j] -> [0, i, j, 2] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_1[i, j] -> a[i] }' + read: 0 + write: 1 + - type: binary + operation: + + arguments: + - type: access + relation: '{ S_1[i, j] -> [i] }' + read: 1 + write: 0 + - type: access + relation: '{ S_1[i, j] -> [j] }' + read: 1 + write: 0 diff --git a/tests/break2.c b/tests/break2.c new file mode 100644 index 0000000..7ba8282 --- /dev/null +++ b/tests/break2.c @@ -0,0 +1,16 @@ +void foo() +{ + int i, j, a[100]; + +#pragma scop + for (i = 0; i < 100; ++i) + for (j = 0; j < 100; ++j) { + a[i] = 0; + if (i < 10) + continue; + if (i == j) + break; + a[i] = i + j; + } +#pragma endscop +} diff --git a/tests/break2.scop b/tests/break2.scop new file mode 100644 index 0000000..c496cfd --- /dev/null +++ b/tests/break2.scop @@ -0,0 +1,45 @@ +context: '{ : }' +arrays: +- context: '{ : }' + extent: '{ a[i0] : i0 >= 0 and i0 <= 99 }' + element_type: int + element_size: 4 +statements: +- line: 8 + domain: '{ S_0[i, j] : (j >= 0 and j <= i and i <= 99) or (j <= 99 and j >= 1 + + i and i >= 0 and i <= 9) }' + schedule: '{ S_0[i, j] -> [0, i, j, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_0[i, j] -> a[i] }' + read: 0 + write: 1 + - type: access + relation: '{ S_0[i, j] -> [0] }' + read: 1 + write: 0 +- line: 13 + domain: '{ S_1[i, j] : j >= 0 and i >= 10 and j <= -1 + i and i <= 99 }' + schedule: '{ S_1[i, j] -> [0, i, j, 3] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_1[i, j] -> a[i] }' + read: 0 + write: 1 + - type: binary + operation: + + arguments: + - type: access + relation: '{ S_1[i, j] -> [i] }' + read: 1 + write: 0 + - type: access + relation: '{ S_1[i, j] -> [j] }' + read: 1 + write: 0 diff --git a/tests/break3.c b/tests/break3.c new file mode 100644 index 0000000..d93f282 --- /dev/null +++ b/tests/break3.c @@ -0,0 +1,16 @@ +int f(); + +void foo() +{ + int i, j, a[100]; + +#pragma scop + for (i = 0; i < 100; ++i) + for (j = 0; j < 100; ++j) { + a[i] = 0; + if (f()) + break; + a[i] = i + j; + } +#pragma endscop +} diff --git a/tests/break3.scop b/tests/break3.scop new file mode 100644 index 0000000..44046a9 --- /dev/null +++ b/tests/break3.scop @@ -0,0 +1,82 @@ +context: '{ : }' +arrays: +- context: '{ : }' + extent: '{ __pet_test_0[i, j] : j >= 0 and j <= 99 and i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ a[i0] : i0 >= 0 and i0 <= 99 }' + element_type: int + element_size: 4 +statements: +- line: 10 + domain: '{ [S_0[i, j] -> [0]] : i >= 0 and i <= 99 and j >= 0 and j <= 99 }' + schedule: '{ S_0[i, j] -> [0, i, j, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_0[i, j] -> a[i] }' + read: 0 + write: 1 + - type: access + relation: '{ S_0[i, j] -> [0] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_0[i, j] -> __pet_test_0[i, o1] : o1 >= 0 and o1 <= -1 + j }' + read: 1 + write: 0 +- line: 11 + domain: '{ [S_1[i, j] -> [0]] : i >= 0 and i <= 99 and j >= 0 and j <= 99 }' + schedule: '{ S_1[i, j] -> [0, i, j, 1, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_1[i, j] -> __pet_test_0[i, j] }' + read: 0 + write: 1 + - type: call + name: f + arguments: + - type: access + relation: '{ S_1[i, j] -> __pet_test_0[i, o1] : o1 >= 0 and o1 <= -1 + j }' + read: 1 + write: 0 +- line: 13 + domain: '{ [S_2[i, j] -> [0, 0]] : i >= 0 and i <= 99 and j >= 0 and j <= 99 }' + schedule: '{ S_2[i, j] -> [0, i, j, 2] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_2[i, j] -> a[i] }' + read: 0 + write: 1 + - type: binary + operation: + + arguments: + - type: access + relation: '{ S_2[i, j] -> [i] }' + read: 1 + write: 0 + - type: access + relation: '{ S_2[i, j] -> [j] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_2[i, j] -> __pet_test_0[i, o1] : o1 >= 0 and o1 <= -1 + j }' + read: 1 + write: 0 + - type: access + relation: '{ S_2[i, j] -> __pet_test_0[i, j] }' + read: 1 + write: 0 diff --git a/tests/break4.c b/tests/break4.c new file mode 100644 index 0000000..7645428 --- /dev/null +++ b/tests/break4.c @@ -0,0 +1,30 @@ +int f(); + +void foo() +{ + int i, j, a[100]; + +#pragma scop + for (i = 0; i < 100; ++i) + for (j = 0; j < 100; ++j) { + a[i] = 0; + if (j > 80) { + if (f()) + break; + } + if (f()) { + if (f()) + break; + a[i] = 1; + if (f()) + continue; + else + a[i] = 2; + a[i] = 3; + } + if (f()) + break; + a[i] = i + j; + } +#pragma endscop +} diff --git a/tests/break4.scop b/tests/break4.scop new file mode 100644 index 0000000..2836716 --- /dev/null +++ b/tests/break4.scop @@ -0,0 +1,651 @@ +context: '{ : }' +arrays: +- context: '{ : }' + extent: '{ __pet_test_0[i, j] : j >= 0 and j <= 99 and i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ __pet_test_1[i, j] : j >= 0 and j <= 99 and i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ __pet_test_5[i, j] : j >= 0 and j <= 99 and i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ __pet_test_2[i, j] : j >= 0 and j <= 99 and i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ __pet_test_3[i, j] : j >= 0 and j <= 99 and i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ __pet_test_4[i, j] : j >= 0 and j <= 99 and i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ __pet_test_6[i, j] : j >= 0 and j <= 99 and i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ __pet_test_7[i, j] : j >= 0 and j <= 99 and i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ __pet_test_8[i, j] : j >= 0 and j <= 99 and i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ __pet_test_9[i, j] : j >= 0 and j <= 99 and i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ __pet_test_10[i, j] : j >= 0 and j <= 99 and i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ __pet_test_11[i, j] : j >= 0 and j <= 99 and i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ __pet_test_12[i, j] : j >= 0 and j <= 99 and i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ a[i0] : i0 >= 0 and i0 <= 99 }' + element_type: int + element_size: 4 +statements: +- line: 10 + domain: '{ [S_0[i, j] -> [0]] : i >= 0 and i <= 99 and j >= 0 and j <= 99 }' + schedule: '{ S_0[i, j] -> [0, i, j, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_0[i, j] -> a[i] }' + read: 0 + write: 1 + - type: access + relation: '{ S_0[i, j] -> [0] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_0[i, j] -> __pet_test_12[i, o1] : o1 >= 0 and o1 <= -1 + j }' + read: 1 + write: 0 +- line: 12 + domain: '{ [S_1[i, j] -> [0]] : i >= 0 and i <= 99 and j >= 81 and j <= 99 }' + schedule: '{ S_1[i, j] -> [0, i, j, 1, 0, 0, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_1[i, j] -> __pet_test_0[i, j] }' + read: 0 + write: 1 + - type: call + name: f + arguments: + - type: access + relation: '{ S_1[i, j] -> __pet_test_12[i, o1] : o1 >= 0 and o1 <= -1 + j }' + read: 1 + write: 0 +- line: -1 + domain: '{ [S_2[i, j] -> [0]] : i >= 0 and i <= 99 and j >= 0 and j <= 99 }' + schedule: '{ S_2[i, j] -> [0, i, j, 1, 1] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_2[i, j] -> __pet_test_1[i, j] }' + read: 0 + write: 1 + - type: ternary + arguments: + - type: access + relation: '{ S_2[i, j] -> [1] : j >= 81; S_2[i, j] -> [0] : j <= 80 }' + read: 1 + write: 0 + - type: access + relation: '{ S_2[i, j] -> __pet_test_0[i, j] : j >= 81 }' + read: 1 + write: 0 + - type: access + relation: '{ S_2[i, j] -> [0] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_2[i, j] -> __pet_test_12[i, o1] : o1 >= 0 and o1 <= -1 + j }' + read: 1 + write: 0 +- line: 15 + domain: '{ [S_3[i, j] -> [0, 0]] : i >= 0 and i <= 99 and j >= 0 and j <= 99 }' + schedule: '{ S_3[i, j] -> [0, i, j, 2, 0, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_3[i, j] -> __pet_test_5[i, j] }' + read: 0 + write: 1 + - type: call + name: f + arguments: + - type: access + relation: '{ S_3[i, j] -> __pet_test_12[i, o1] : o1 >= 0 and o1 <= -1 + j }' + read: 1 + write: 0 + - type: access + relation: '{ S_3[i, j] -> __pet_test_1[i, j] }' + read: 1 + write: 0 +- line: 16 + domain: '{ [S_4[i, j] -> [0, 0, 1]] : i >= 0 and i <= 99 and j >= 0 and j <= 99 + }' + schedule: '{ S_4[i, j] -> [0, i, j, 2, 0, 1, 0, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_4[i, j] -> __pet_test_2[i, j] }' + read: 0 + write: 1 + - type: call + name: f + arguments: + - type: access + relation: '{ S_4[i, j] -> __pet_test_12[i, o1] : o1 >= 0 and o1 <= -1 + j }' + read: 1 + write: 0 + - type: access + relation: '{ S_4[i, j] -> __pet_test_1[i, j] }' + read: 1 + write: 0 + - type: access + relation: '{ S_4[i, j] -> __pet_test_5[i, j] }' + read: 1 + write: 0 +- line: 18 + domain: '{ [S_5[i, j] -> [0, 0, 1, 0]] : i >= 0 and i <= 99 and j >= 0 and j <= + 99 }' + schedule: '{ S_5[i, j] -> [0, i, j, 2, 0, 1, 1] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_5[i, j] -> a[i] }' + read: 0 + write: 1 + - type: access + relation: '{ S_5[i, j] -> [1] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_5[i, j] -> __pet_test_12[i, o1] : o1 >= 0 and o1 <= -1 + j }' + read: 1 + write: 0 + - type: access + relation: '{ S_5[i, j] -> __pet_test_1[i, j] }' + read: 1 + write: 0 + - type: access + relation: '{ S_5[i, j] -> __pet_test_5[i, j] }' + read: 1 + write: 0 + - type: access + relation: '{ S_5[i, j] -> __pet_test_2[i, j] }' + read: 1 + write: 0 +- line: 19 + domain: '{ [S_6[i, j] -> [0, 0, 1, 0]] : i >= 0 and i <= 99 and j >= 0 and j <= + 99 }' + schedule: '{ S_6[i, j] -> [0, i, j, 2, 0, 1, 2, 0, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_6[i, j] -> __pet_test_3[i, j] }' + read: 0 + write: 1 + - type: call + name: f + arguments: + - type: access + relation: '{ S_6[i, j] -> __pet_test_12[i, o1] : o1 >= 0 and o1 <= -1 + j }' + read: 1 + write: 0 + - type: access + relation: '{ S_6[i, j] -> __pet_test_1[i, j] }' + read: 1 + write: 0 + - type: access + relation: '{ S_6[i, j] -> __pet_test_5[i, j] }' + read: 1 + write: 0 + - type: access + relation: '{ S_6[i, j] -> __pet_test_2[i, j] }' + read: 1 + write: 0 +- line: 22 + domain: '{ [S_7[i, j] -> [0, 0, 1, 0, 0]] : i >= 0 and i <= 99 and j >= 0 and j + <= 99 }' + schedule: '{ S_7[i, j] -> [0, i, j, 2, 0, 1, 2, 0, 1] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_7[i, j] -> a[i] }' + read: 0 + write: 1 + - type: access + relation: '{ S_7[i, j] -> [2] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_7[i, j] -> __pet_test_12[i, o1] : o1 >= 0 and o1 <= -1 + j }' + read: 1 + write: 0 + - type: access + relation: '{ S_7[i, j] -> __pet_test_1[i, j] }' + read: 1 + write: 0 + - type: access + relation: '{ S_7[i, j] -> __pet_test_5[i, j] }' + read: 1 + write: 0 + - type: access + relation: '{ S_7[i, j] -> __pet_test_2[i, j] }' + read: 1 + write: 0 + - type: access + relation: '{ S_7[i, j] -> __pet_test_3[i, j] }' + read: 1 + write: 0 +- line: -1 + domain: '{ [S_8[i, j] -> [0, 0, 1]] : i >= 0 and i <= 99 and j >= 0 and j <= 99 + }' + schedule: '{ S_8[i, j] -> [0, i, j, 2, 0, 1, 2, 1] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_8[i, j] -> __pet_test_4[i, j] }' + read: 0 + write: 1 + - type: ternary + arguments: + - type: access + relation: '{ S_8[i, j] -> __pet_test_2[i, j] }' + read: 1 + write: 0 + - type: access + relation: '{ S_8[i, j] -> [1] }' + read: 1 + write: 0 + - type: access + relation: '{ [S_8[i, j] -> [0]] -> __pet_test_3[i, j] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_8[i, j] -> __pet_test_2[i, j] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_8[i, j] -> __pet_test_12[i, o1] : o1 >= 0 and o1 <= -1 + j }' + read: 1 + write: 0 + - type: access + relation: '{ S_8[i, j] -> __pet_test_1[i, j] }' + read: 1 + write: 0 + - type: access + relation: '{ S_8[i, j] -> __pet_test_5[i, j] }' + read: 1 + write: 0 +- line: 23 + domain: '{ [S_9[i, j] -> [0, 0, 1, 0]] : i >= 0 and i <= 99 and j >= 0 and j <= + 99 }' + schedule: '{ S_9[i, j] -> [0, i, j, 2, 0, 1, 3] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_9[i, j] -> a[i] }' + read: 0 + write: 1 + - type: access + relation: '{ S_9[i, j] -> [3] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_9[i, j] -> __pet_test_12[i, o1] : o1 >= 0 and o1 <= -1 + j }' + read: 1 + write: 0 + - type: access + relation: '{ S_9[i, j] -> __pet_test_1[i, j] }' + read: 1 + write: 0 + - type: access + relation: '{ S_9[i, j] -> __pet_test_5[i, j] }' + read: 1 + write: 0 + - type: access + relation: '{ S_9[i, j] -> __pet_test_4[i, j] }' + read: 1 + write: 0 +- line: -1 + domain: '{ [S_10[i, j] -> [0, 0]] : i >= 0 and i <= 99 and j >= 0 and j <= 99 }' + schedule: '{ S_10[i, j] -> [0, i, j, 2, 0, 2] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_10[i, j] -> __pet_test_6[i, j] }' + read: 0 + write: 1 + - type: ternary + arguments: + - type: access + relation: '{ S_10[i, j] -> __pet_test_5[i, j] }' + read: 1 + write: 0 + - type: access + relation: '{ [S_10[i, j] -> [1]] -> __pet_test_4[i, j] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_10[i, j] -> __pet_test_5[i, j] }' + read: 1 + write: 0 + - type: access + relation: '{ S_10[i, j] -> [0] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_10[i, j] -> __pet_test_12[i, o1] : o1 >= 0 and o1 <= -1 + j }' + read: 1 + write: 0 + - type: access + relation: '{ S_10[i, j] -> __pet_test_1[i, j] }' + read: 1 + write: 0 +- line: -1 + domain: '{ [S_11[i, j] -> [0, 0]] : i >= 0 and i <= 99 and j >= 0 and j <= 99 }' + schedule: '{ S_11[i, j] -> [0, i, j, 2, 0, 2] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_11[i, j] -> __pet_test_7[i, j] }' + read: 0 + write: 1 + - type: ternary + arguments: + - type: access + relation: '{ S_11[i, j] -> __pet_test_5[i, j] }' + read: 1 + write: 0 + - type: access + relation: '{ [S_11[i, j] -> [1]] -> __pet_test_2[i, j] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_11[i, j] -> __pet_test_5[i, j] }' + read: 1 + write: 0 + - type: access + relation: '{ S_11[i, j] -> [0] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_11[i, j] -> __pet_test_12[i, o1] : o1 >= 0 and o1 <= -1 + j }' + read: 1 + write: 0 + - type: access + relation: '{ S_11[i, j] -> __pet_test_1[i, j] }' + read: 1 + write: 0 +- line: -1 + domain: '{ [S_12[i, j] -> [0]] : i >= 0 and i <= 99 and j >= 0 and j <= 99 }' + schedule: '{ S_12[i, j] -> [0, i, j, 2, 1] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_12[i, j] -> __pet_test_8[i, j] }' + read: 0 + write: 1 + - type: ternary + arguments: + - type: access + relation: '{ S_12[i, j] -> __pet_test_1[i, j] }' + read: 1 + write: 0 + - type: access + relation: '{ S_12[i, j] -> [1] }' + read: 1 + write: 0 + - type: access + relation: '{ [S_12[i, j] -> [0]] -> __pet_test_6[i, j] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_12[i, j] -> __pet_test_1[i, j] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_12[i, j] -> __pet_test_12[i, o1] : o1 >= 0 and o1 <= -1 + j }' + read: 1 + write: 0 +- line: -1 + domain: '{ [S_13[i, j] -> [0]] : i >= 0 and i <= 99 and j >= 0 and j <= 99 }' + schedule: '{ S_13[i, j] -> [0, i, j, 2, 1] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_13[i, j] -> __pet_test_9[i, j] }' + read: 0 + write: 1 + - type: ternary + arguments: + - type: access + relation: '{ S_13[i, j] -> __pet_test_1[i, j] }' + read: 1 + write: 0 + - type: access + relation: '{ S_13[i, j] -> [1] }' + read: 1 + write: 0 + - type: access + relation: '{ [S_13[i, j] -> [0]] -> __pet_test_7[i, j] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_13[i, j] -> __pet_test_1[i, j] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_13[i, j] -> __pet_test_12[i, o1] : o1 >= 0 and o1 <= -1 + j }' + read: 1 + write: 0 +- line: 25 + domain: '{ [S_14[i, j] -> [0, 0]] : i >= 0 and i <= 99 and j >= 0 and j <= 99 }' + schedule: '{ S_14[i, j] -> [0, i, j, 3, 0, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_14[i, j] -> __pet_test_10[i, j] }' + read: 0 + write: 1 + - type: call + name: f + arguments: + - type: access + relation: '{ S_14[i, j] -> __pet_test_12[i, o1] : o1 >= 0 and o1 <= -1 + j }' + read: 1 + write: 0 + - type: access + relation: '{ S_14[i, j] -> __pet_test_8[i, j] }' + read: 1 + write: 0 +- line: -1 + domain: '{ [S_15[i, j] -> [0]] : i >= 0 and i <= 99 and j >= 0 and j <= 99 }' + schedule: '{ S_15[i, j] -> [0, i, j, 3, 1] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_15[i, j] -> __pet_test_11[i, j] }' + read: 0 + write: 1 + - type: ternary + arguments: + - type: access + relation: '{ S_15[i, j] -> __pet_test_8[i, j] }' + read: 1 + write: 0 + - type: access + relation: '{ S_15[i, j] -> [1] }' + read: 1 + write: 0 + - type: access + relation: '{ [S_15[i, j] -> [0]] -> __pet_test_10[i, j] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_15[i, j] -> __pet_test_8[i, j] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_15[i, j] -> __pet_test_12[i, o1] : o1 >= 0 and o1 <= -1 + j }' + read: 1 + write: 0 +- line: -1 + domain: '{ [S_16[i, j] -> [0]] : i >= 0 and i <= 99 and j >= 0 and j <= 99 }' + schedule: '{ S_16[i, j] -> [0, i, j, 3, 1] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_16[i, j] -> __pet_test_12[i, j] }' + read: 0 + write: 1 + - type: ternary + arguments: + - type: access + relation: '{ S_16[i, j] -> __pet_test_9[i, j] }' + read: 1 + write: 0 + - type: access + relation: '{ S_16[i, j] -> [1] }' + read: 1 + write: 0 + - type: access + relation: '{ [S_16[i, j] -> [0]] -> __pet_test_10[i, j] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_16[i, j] -> __pet_test_9[i, j] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_16[i, j] -> __pet_test_12[i, o1] : o1 >= 0 and o1 <= -1 + j }' + read: 1 + write: 0 +- line: 27 + domain: '{ [S_17[i, j] -> [0, 0]] : i >= 0 and i <= 99 and j >= 0 and j <= 99 }' + schedule: '{ S_17[i, j] -> [0, i, j, 4] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_17[i, j] -> a[i] }' + read: 0 + write: 1 + - type: binary + operation: + + arguments: + - type: access + relation: '{ S_17[i, j] -> [i] }' + read: 1 + write: 0 + - type: access + relation: '{ S_17[i, j] -> [j] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_17[i, j] -> __pet_test_12[i, o1] : o1 >= 0 and o1 <= -1 + j }' + read: 1 + write: 0 + - type: access + relation: '{ S_17[i, j] -> __pet_test_11[i, j] }' + read: 1 + write: 0 diff --git a/tests/break5.c b/tests/break5.c new file mode 100644 index 0000000..7bb643f --- /dev/null +++ b/tests/break5.c @@ -0,0 +1,20 @@ +void foo() +{ + int i, j, a[100]; + +#pragma scop + for (i = 0; i < 100; ++i) + for (j = 0; j < 100; ++j) { + a[i] = 0; + if (i < 10) + continue; + if (i == j) + break; + if (j > 60) + continue; + if (i + j >= 150) + break; + a[i] = i + j; + } +#pragma endscop +} diff --git a/tests/break5.scop b/tests/break5.scop new file mode 100644 index 0000000..6e4c523 --- /dev/null +++ b/tests/break5.scop @@ -0,0 +1,47 @@ +context: '{ : }' +arrays: +- context: '{ : }' + extent: '{ a[i0] : i0 >= 0 and i0 <= 99 }' + element_type: int + element_size: 4 +statements: +- line: 8 + domain: '{ S_0[i, j] : (j >= 0 and j <= i and i <= 99 and j <= 150 - i) or (j <= + 99 and j >= 1 + i and i >= 0 and i <= 9) or (j >= 151 - i and j <= i and i <= + 89) }' + schedule: '{ S_0[i, j] -> [0, i, j, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_0[i, j] -> a[i] }' + read: 0 + write: 1 + - type: access + relation: '{ S_0[i, j] -> [0] }' + read: 1 + write: 0 +- line: 17 + domain: '{ S_1[i, j] : j >= 0 and j <= 60 and i >= 10 and j <= -1 + i and i <= 99 + and j <= 149 - i }' + schedule: '{ S_1[i, j] -> [0, i, j, 5] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_1[i, j] -> a[i] }' + read: 0 + write: 1 + - type: binary + operation: + + arguments: + - type: access + relation: '{ S_1[i, j] -> [i] }' + read: 1 + write: 0 + - type: access + relation: '{ S_1[i, j] -> [j] }' + read: 1 + write: 0 diff --git a/tests/continue.c b/tests/continue.c new file mode 100644 index 0000000..d4ac067 --- /dev/null +++ b/tests/continue.c @@ -0,0 +1,14 @@ +void foo() +{ + int i, j, a[100]; + +#pragma scop + for (i = 0; i < 100; ++i) + for (j = 0; j < 100; ++j) { + a[i] = 0; + if (i == j) + continue; + a[i] = i + j; + } +#pragma endscop +} diff --git a/tests/continue.scop b/tests/continue.scop new file mode 100644 index 0000000..37ea589 --- /dev/null +++ b/tests/continue.scop @@ -0,0 +1,45 @@ +context: '{ : }' +arrays: +- context: '{ : }' + extent: '{ a[i0] : i0 >= 0 and i0 <= 99 }' + element_type: int + element_size: 4 +statements: +- line: 8 + domain: '{ S_0[i, j] : j >= 0 and j <= 99 and i >= 0 and i <= 99 }' + schedule: '{ S_0[i, j] -> [0, i, j, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_0[i, j] -> a[i] }' + read: 0 + write: 1 + - type: access + relation: '{ S_0[i, j] -> [0] }' + read: 1 + write: 0 +- line: 11 + domain: '{ S_1[i, j] : (j <= 99 and j >= 1 + i and i >= 0) or (j >= 0 and j <= -1 + + i and i <= 99) }' + schedule: '{ S_1[i, j] -> [0, i, j, 2] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_1[i, j] -> a[i] }' + read: 0 + write: 1 + - type: binary + operation: + + arguments: + - type: access + relation: '{ S_1[i, j] -> [i] }' + read: 1 + write: 0 + - type: access + relation: '{ S_1[i, j] -> [j] }' + read: 1 + write: 0 diff --git a/tests/continue2.c b/tests/continue2.c new file mode 100644 index 0000000..8665371 --- /dev/null +++ b/tests/continue2.c @@ -0,0 +1,24 @@ +int f(void); + +void foo() +{ + int i, j, a[100]; + +#pragma scop + for (i = 0; i < 100; ++i) { + if (i < 60) { + if (a[i] > 5) { + j = f(); + if (j == 0) + continue; + a[i] = i; + } else + a[i] = 0; + j = f(); + } else + a[i] = i; + j = f(); + a[i] = a[i] + 1; + } +#pragma endscop +} diff --git a/tests/continue2.scop b/tests/continue2.scop new file mode 100644 index 0000000..7b0e9b6 --- /dev/null +++ b/tests/continue2.scop @@ -0,0 +1,279 @@ +context: '{ : }' +arrays: +- context: '{ : }' + extent: '{ __pet_test_1[i] : i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ __pet_test_0[i] : i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ __pet_test_2[i] : i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ __pet_test_3[i] : i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ j[] }' + element_type: int + element_size: 4 +- context: '{ : }' + extent: '{ a[i0] : i0 >= 0 and i0 <= 99 }' + element_type: int + element_size: 4 +statements: +- line: 10 + domain: '{ S_0[i] : i >= 0 and i <= 59 }' + schedule: '{ S_0[i] -> [0, i, 0, 0, 0, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_0[i] -> __pet_test_1[i] }' + read: 0 + write: 1 + - type: binary + operation: '>' + arguments: + - type: access + relation: '{ S_0[i] -> a[i] }' + read: 1 + write: 0 + - type: access + relation: '{ S_0[i] -> [5] }' + read: 1 + write: 0 +- line: 11 + domain: '{ [S_1[i] -> [1]] : i >= 0 and i <= 59 }' + schedule: '{ S_1[i] -> [0, i, 0, 0, 0, 1, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_1[i] -> j[] }' + read: 0 + write: 1 + - type: call + name: f + arguments: + - type: access + relation: '{ S_1[i] -> __pet_test_1[i] }' + read: 1 + write: 0 +- line: 12 + domain: '{ [S_2[i] -> [1]] : i >= 0 and i <= 59 }' + schedule: '{ S_2[i] -> [0, i, 0, 0, 0, 1, 1, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_2[i] -> __pet_test_0[i] }' + read: 0 + write: 1 + - type: binary + operation: == + arguments: + - type: access + relation: '{ S_2[i] -> j[] }' + read: 1 + write: 0 + - type: access + relation: '{ S_2[i] -> [0] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_2[i] -> __pet_test_1[i] }' + read: 1 + write: 0 +- line: 14 + domain: '{ [S_3[i] -> [1, 0]] : i >= 0 and i <= 59 }' + schedule: '{ S_3[i] -> [0, i, 0, 0, 0, 1, 2] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_3[i] -> a[i] }' + read: 0 + write: 1 + - type: access + relation: '{ S_3[i] -> [i] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_3[i] -> __pet_test_1[i] }' + read: 1 + write: 0 + - type: access + relation: '{ S_3[i] -> __pet_test_0[i] }' + read: 1 + write: 0 +- line: 16 + domain: '{ [S_4[i] -> [0]] : i >= 0 and i <= 59 }' + schedule: '{ S_4[i] -> [0, i, 0, 0, 0, 1] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_4[i] -> a[i] }' + read: 0 + write: 1 + - type: access + relation: '{ S_4[i] -> [0] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_4[i] -> __pet_test_1[i] }' + read: 1 + write: 0 +- line: -1 + domain: '{ S_5[i] : i >= 0 and i <= 59 }' + schedule: '{ S_5[i] -> [0, i, 0, 0, 0, 2] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_5[i] -> __pet_test_2[i] }' + read: 0 + write: 1 + - type: ternary + arguments: + - type: access + relation: '{ S_5[i] -> __pet_test_1[i] }' + read: 1 + write: 0 + - type: access + relation: '{ [S_5[i] -> [1]] -> __pet_test_0[i] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_5[i] -> __pet_test_1[i] }' + read: 1 + write: 0 + - type: access + relation: '{ S_5[i] -> [0] }' + read: 1 + write: 0 +- line: 17 + domain: '{ [S_6[i] -> [0]] : i >= 0 and i <= 59 }' + schedule: '{ S_6[i] -> [0, i, 0, 0, 1] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_6[i] -> j[] }' + read: 0 + write: 1 + - type: call + name: f + arguments: + - type: access + relation: '{ S_6[i] -> __pet_test_2[i] }' + read: 1 + write: 0 +- line: 19 + domain: '{ S_7[i] : i >= 60 and i <= 99 }' + schedule: '{ S_7[i] -> [0, i, 0, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_7[i] -> a[i] }' + read: 0 + write: 1 + - type: access + relation: '{ S_7[i] -> [i] }' + read: 1 + write: 0 +- line: -1 + domain: '{ S_8[i] : i >= 0 and i <= 99 }' + schedule: '{ S_8[i] -> [0, i, 0, 1] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_8[i] -> __pet_test_3[i] }' + read: 0 + write: 1 + - type: ternary + arguments: + - type: access + relation: '{ S_8[i] -> [1] : i <= 59; S_8[i] -> [0] : i >= 60 }' + read: 1 + write: 0 + - type: access + relation: '{ S_8[i] -> __pet_test_2[i] : i <= 59 }' + read: 1 + write: 0 + - type: access + relation: '{ S_8[i] -> [0] }' + read: 1 + write: 0 +- line: 20 + domain: '{ [S_9[i] -> [0]] : i >= 0 and i <= 99 }' + schedule: '{ S_9[i] -> [0, i, 1] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_9[i] -> j[] }' + read: 0 + write: 1 + - type: call + name: f + arguments: + - type: access + relation: '{ S_9[i] -> __pet_test_3[i] }' + read: 1 + write: 0 +- line: 21 + domain: '{ [S_10[i] -> [0]] : i >= 0 and i <= 99 }' + schedule: '{ S_10[i] -> [0, i, 2] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_10[i] -> a[i] }' + read: 0 + write: 1 + - type: binary + operation: + + arguments: + - type: access + relation: '{ S_10[i] -> a[i] }' + read: 1 + write: 0 + - type: access + relation: '{ S_10[i] -> [1] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_10[i] -> __pet_test_3[i] }' + read: 1 + write: 0 diff --git a/tests/continue3.c b/tests/continue3.c new file mode 100644 index 0000000..1ca2249 --- /dev/null +++ b/tests/continue3.c @@ -0,0 +1,19 @@ +int f(void); + +void foo() +{ + int i, j, a[100]; + +#pragma scop + for (i = 0; i < 100; ++i) { + j = f(); + if (j == 0) + continue; + a[i] = i; + j = f(); + if (j == 0) + continue; + a[i] = a[i] + 1; + } +#pragma endscop +} diff --git a/tests/continue3.scop b/tests/continue3.scop new file mode 100644 index 0000000..0b94505 --- /dev/null +++ b/tests/continue3.scop @@ -0,0 +1,186 @@ +context: '{ : }' +arrays: +- context: '{ : }' + extent: '{ __pet_test_0[i] : i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ __pet_test_1[i] : i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ __pet_test_2[i] : i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ j[] }' + element_type: int + element_size: 4 +- context: '{ : }' + extent: '{ a[i0] : i0 >= 0 and i0 <= 99 }' + element_type: int + element_size: 4 +statements: +- line: 9 + domain: '{ S_0[i] : i >= 0 and i <= 99 }' + schedule: '{ S_0[i] -> [0, i, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_0[i] -> j[] }' + read: 0 + write: 1 + - type: call + name: f +- line: 10 + domain: '{ S_1[i] : i >= 0 and i <= 99 }' + schedule: '{ S_1[i] -> [0, i, 1, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_1[i] -> __pet_test_0[i] }' + read: 0 + write: 1 + - type: binary + operation: == + arguments: + - type: access + relation: '{ S_1[i] -> j[] }' + read: 1 + write: 0 + - type: access + relation: '{ S_1[i] -> [0] }' + read: 1 + write: 0 +- line: 12 + domain: '{ [S_2[i] -> [0]] : i >= 0 and i <= 99 }' + schedule: '{ S_2[i] -> [0, i, 2] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_2[i] -> a[i] }' + read: 0 + write: 1 + - type: access + relation: '{ S_2[i] -> [i] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_2[i] -> __pet_test_0[i] }' + read: 1 + write: 0 +- line: 13 + domain: '{ [S_3[i] -> [0]] : i >= 0 and i <= 99 }' + schedule: '{ S_3[i] -> [0, i, 3] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_3[i] -> j[] }' + read: 0 + write: 1 + - type: call + name: f + arguments: + - type: access + relation: '{ S_3[i] -> __pet_test_0[i] }' + read: 1 + write: 0 +- line: 14 + domain: '{ [S_4[i] -> [0]] : i >= 0 and i <= 99 }' + schedule: '{ S_4[i] -> [0, i, 4, 0, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_4[i] -> __pet_test_1[i] }' + read: 0 + write: 1 + - type: binary + operation: == + arguments: + - type: access + relation: '{ S_4[i] -> j[] }' + read: 1 + write: 0 + - type: access + relation: '{ S_4[i] -> [0] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_4[i] -> __pet_test_0[i] }' + read: 1 + write: 0 +- line: -1 + domain: '{ S_5[i] : i >= 0 and i <= 99 }' + schedule: '{ S_5[i] -> [0, i, 4, 1] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_5[i] -> __pet_test_2[i] }' + read: 0 + write: 1 + - type: ternary + arguments: + - type: access + relation: '{ S_5[i] -> __pet_test_0[i] }' + read: 1 + write: 0 + - type: access + relation: '{ S_5[i] -> [1] }' + read: 1 + write: 0 + - type: access + relation: '{ [S_5[i] -> [0]] -> __pet_test_1[i] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_5[i] -> __pet_test_0[i] }' + read: 1 + write: 0 +- line: 16 + domain: '{ [S_6[i] -> [0]] : i >= 0 and i <= 99 }' + schedule: '{ S_6[i] -> [0, i, 5] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_6[i] -> a[i] }' + read: 0 + write: 1 + - type: binary + operation: + + arguments: + - type: access + relation: '{ S_6[i] -> a[i] }' + read: 1 + write: 0 + - type: access + relation: '{ S_6[i] -> [1] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_6[i] -> __pet_test_2[i] }' + read: 1 + write: 0 diff --git a/tests/continue4.c b/tests/continue4.c new file mode 100644 index 0000000..a2ac69e --- /dev/null +++ b/tests/continue4.c @@ -0,0 +1,19 @@ +int f(void); + +void foo() +{ + int i, j, a[100]; + +#pragma scop + for (i = 0; i < 100; ++i) { + j = f(); + if (j == 0) + continue; + a[i] = i; + j = f(); + if (i == 57) + continue; + a[i] = a[i] + 1; + } +#pragma endscop +} diff --git a/tests/continue4.scop b/tests/continue4.scop new file mode 100644 index 0000000..ff5e77e --- /dev/null +++ b/tests/continue4.scop @@ -0,0 +1,154 @@ +context: '{ : }' +arrays: +- context: '{ : }' + extent: '{ __pet_test_0[i] : i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ __pet_test_1[i] : i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ j[] }' + element_type: int + element_size: 4 +- context: '{ : }' + extent: '{ a[i0] : i0 >= 0 and i0 <= 99 }' + element_type: int + element_size: 4 +statements: +- line: 9 + domain: '{ S_0[i] : i >= 0 and i <= 99 }' + schedule: '{ S_0[i] -> [0, i, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_0[i] -> j[] }' + read: 0 + write: 1 + - type: call + name: f +- line: 10 + domain: '{ S_1[i] : i >= 0 and i <= 99 }' + schedule: '{ S_1[i] -> [0, i, 1, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_1[i] -> __pet_test_0[i] }' + read: 0 + write: 1 + - type: binary + operation: == + arguments: + - type: access + relation: '{ S_1[i] -> j[] }' + read: 1 + write: 0 + - type: access + relation: '{ S_1[i] -> [0] }' + read: 1 + write: 0 +- line: 12 + domain: '{ [S_2[i] -> [0]] : i >= 0 and i <= 99 }' + schedule: '{ S_2[i] -> [0, i, 2] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_2[i] -> a[i] }' + read: 0 + write: 1 + - type: access + relation: '{ S_2[i] -> [i] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_2[i] -> __pet_test_0[i] }' + read: 1 + write: 0 +- line: 13 + domain: '{ [S_3[i] -> [0]] : i >= 0 and i <= 99 }' + schedule: '{ S_3[i] -> [0, i, 3] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_3[i] -> j[] }' + read: 0 + write: 1 + - type: call + name: f + arguments: + - type: access + relation: '{ S_3[i] -> __pet_test_0[i] }' + read: 1 + write: 0 +- line: -1 + domain: '{ S_4[i] : i >= 0 and i <= 99 }' + schedule: '{ S_4[i] -> [0, i, 4, 1] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_4[i] -> __pet_test_1[i] }' + read: 0 + write: 1 + - type: ternary + arguments: + - type: access + relation: '{ S_4[i] -> __pet_test_0[i] }' + read: 1 + write: 0 + - type: access + relation: '{ S_4[i] -> [1] }' + read: 1 + write: 0 + - type: access + relation: '{ [S_4[i] -> [0]] -> [0] : i <= 56 or i >= 58; [S_4[57] -> [0]] + -> [1] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_4[i] -> __pet_test_0[i] }' + read: 1 + write: 0 +- line: 16 + domain: '{ [S_5[i] -> [0]] : i >= 0 and i <= 99 }' + schedule: '{ S_5[i] -> [0, i, 5] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_5[i] -> a[i] }' + read: 0 + write: 1 + - type: binary + operation: + + arguments: + - type: access + relation: '{ S_5[i] -> a[i] }' + read: 1 + write: 0 + - type: access + relation: '{ S_5[i] -> [1] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_5[i] -> __pet_test_1[i] }' + read: 1 + write: 0 diff --git a/tests/continue5.c b/tests/continue5.c new file mode 100644 index 0000000..18a125a --- /dev/null +++ b/tests/continue5.c @@ -0,0 +1,19 @@ +int f(void); + +void foo() +{ + int i, j, a[100]; + +#pragma scop + for (i = 0; i < 100; ++i) { + j = f(); + if (i == 57) + continue; + a[i] = i; + j = f(); + if (j == 0) + continue; + a[i] = a[i] + 1; + } +#pragma endscop +} diff --git a/tests/continue5.scop b/tests/continue5.scop new file mode 100644 index 0000000..90f7979 --- /dev/null +++ b/tests/continue5.scop @@ -0,0 +1,138 @@ +context: '{ : }' +arrays: +- context: '{ : }' + extent: '{ __pet_test_0[i] : i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ __pet_test_1[i] : i >= 0 and i <= 99 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ j[] }' + element_type: int + element_size: 4 +- context: '{ : }' + extent: '{ a[i0] : i0 >= 0 and i0 <= 99 }' + element_type: int + element_size: 4 +statements: +- line: 9 + domain: '{ S_0[i] : i >= 0 and i <= 99 }' + schedule: '{ S_0[i] -> [0, i, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_0[i] -> j[] }' + read: 0 + write: 1 + - type: call + name: f +- line: 12 + domain: '{ S_1[i] : (i >= 58 and i <= 99) or (i >= 0 and i <= 56) }' + schedule: '{ S_1[i] -> [0, i, 2] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_1[i] -> a[i] }' + read: 0 + write: 1 + - type: access + relation: '{ S_1[i] -> [i] }' + read: 1 + write: 0 +- line: 13 + domain: '{ S_2[i] : (i >= 58 and i <= 99) or (i >= 0 and i <= 56) }' + schedule: '{ S_2[i] -> [0, i, 3] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_2[i] -> j[] }' + read: 0 + write: 1 + - type: call + name: f +- line: 14 + domain: '{ S_3[i] : (i >= 58 and i <= 99) or (i >= 0 and i <= 56) }' + schedule: '{ S_3[i] -> [0, i, 4, 0, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_3[i] -> __pet_test_0[i] }' + read: 0 + write: 1 + - type: binary + operation: == + arguments: + - type: access + relation: '{ S_3[i] -> j[] }' + read: 1 + write: 0 + - type: access + relation: '{ S_3[i] -> [0] }' + read: 1 + write: 0 +- line: -1 + domain: '{ S_4[i] : i >= 0 and i <= 99 }' + schedule: '{ S_4[i] -> [0, i, 4, 1] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_4[i] -> __pet_test_1[i] }' + read: 0 + write: 1 + - type: ternary + arguments: + - type: access + relation: '{ S_4[i] -> [0] : i <= 56 or i >= 58; S_4[57] -> [1] }' + read: 1 + write: 0 + - type: access + relation: '{ S_4[i] -> [1] }' + read: 1 + write: 0 + - type: access + relation: '{ S_4[i] -> __pet_test_0[i] : i >= 58 or i <= 56 }' + read: 1 + write: 0 +- line: 16 + domain: '{ [S_5[i] -> [0]] : i >= 0 and i <= 99 }' + schedule: '{ S_5[i] -> [0, i, 5] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_5[i] -> a[i] }' + read: 0 + write: 1 + - type: binary + operation: + + arguments: + - type: access + relation: '{ S_5[i] -> a[i] }' + read: 1 + write: 0 + - type: access + relation: '{ S_5[i] -> [1] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_5[i] -> __pet_test_1[i] }' + read: 1 + write: 0 diff --git a/tests/unsigned_break1.c b/tests/unsigned_break1.c new file mode 100644 index 0000000..0c66ba1 --- /dev/null +++ b/tests/unsigned_break1.c @@ -0,0 +1,14 @@ +void foo() +{ + unsigned char k; + int a; + +#pragma scop + for (k = 252; (k % 9) <= 5; ++k) { + a = 5; + if (k == 1) + break; + a = 6; + } +#pragma endscop +} diff --git a/tests/unsigned_break1.scop b/tests/unsigned_break1.scop new file mode 100644 index 0000000..197df24 --- /dev/null +++ b/tests/unsigned_break1.scop @@ -0,0 +1,40 @@ +context: '{ : }' +arrays: +- context: '{ : }' + extent: '{ a[] }' + element_type: int + element_size: 4 +statements: +- line: 8 + domain: '{ S_0[k] : exists (e0 = [(507 - k)/256]: k >= 0 and k <= 255 and 256e0 + <= 257 - k and 256e0 >= 252 - k) }' + schedule: '{ S_0[k] -> [0, o1, 0] : exists (e0 = [(k - o1)/256]: 256e0 = k - o1 + and o1 >= 252 and k <= 255 and k >= 0 and o1 <= 257) }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_0[k] -> a[] }' + read: 0 + write: 1 + - type: access + relation: '{ S_0[k] -> [5] }' + read: 1 + write: 0 +- line: 11 + domain: '{ S_1[k] : k <= 255 and k >= 252; S_1[0] }' + schedule: '{ S_1[k] -> [0, o1, 2] : exists (e0 = [(k - o1)/256]: 256e0 = k - o1 + and o1 >= 252 and k <= 255 and k >= 0 and o1 <= 257) }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_1[k] -> a[] }' + read: 0 + write: 1 + - type: access + relation: '{ S_1[k] -> [6] }' + read: 1 + write: 0 diff --git a/tests/unsigned_break2.c b/tests/unsigned_break2.c new file mode 100644 index 0000000..093584d --- /dev/null +++ b/tests/unsigned_break2.c @@ -0,0 +1,17 @@ +int f(); + +void foo() +{ + unsigned char k; + int a; + +#pragma scop + for (k = 252; (k % 9) <= 5; ++k) { + if (k != 1) + a = 5; + if (f()) + break; + a = k; + } +#pragma endscop +} diff --git a/tests/unsigned_break2.scop b/tests/unsigned_break2.scop new file mode 100644 index 0000000..8bbc755 --- /dev/null +++ b/tests/unsigned_break2.scop @@ -0,0 +1,77 @@ +context: '{ : }' +arrays: +- context: '{ : }' + extent: '{ __pet_test_0[k] : k >= 252 and k <= 261 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '{ a[] }' + element_type: int + element_size: 4 +statements: +- line: 11 + domain: '{ [S_0[k] -> [0]] : exists (e0 = [(257 - k)/256]: k >= 252 and k <= 261 + and 256e0 <= 255 - k and 256e0 >= 2 - k); [S_0[256] -> [0]] }' + schedule: '{ S_0[k] -> [0, k, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_0[k] -> a[] }' + read: 0 + write: 1 + - type: access + relation: '{ S_0[k] -> [5] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_0[k] -> __pet_test_0[o0] : o0 >= 252 and o0 <= -1 + k }' + read: 1 + write: 0 +- line: 12 + domain: '{ [S_1[k] -> [0]] : k >= 252 and k <= 261 }' + schedule: '{ S_1[k] -> [0, k, 1, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_1[k] -> __pet_test_0[k] }' + read: 0 + write: 1 + - type: call + name: f + arguments: + - type: access + relation: '{ S_1[k] -> __pet_test_0[o0] : o0 >= 252 and o0 <= -1 + k }' + read: 1 + write: 0 +- line: 14 + domain: '{ [S_2[k] -> [0, 0]] : k >= 252 and k <= 261 }' + schedule: '{ S_2[k] -> [0, k, 2] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_2[k] -> a[] }' + read: 0 + write: 1 + - type: access + relation: '{ S_2[k] -> [o0] : exists (e0 = [(-k + o0)/256]: 256e0 = -k + o0 + and o0 <= 255 and o0 >= 0) }' + read: 1 + write: 0 + arguments: + - type: access + relation: '{ S_2[k] -> __pet_test_0[o0] : o0 >= 252 and o0 <= -1 + k }' + read: 1 + write: 0 + - type: access + relation: '{ S_2[k] -> __pet_test_0[k] }' + read: 1 + write: 0 diff --git a/tests/while_break.c b/tests/while_break.c new file mode 100644 index 0000000..e1a9477 --- /dev/null +++ b/tests/while_break.c @@ -0,0 +1,34 @@ +int f(); + +void foo(int N) +{ + int i; + int a; + +#pragma scop + while (1) { + a = 5; + if (N) + break; + a = 6; + } + while (1) { + a = 5; + if (f()) + break; + a = 6; + } + while (f()) { + a = 5; + if (N) + break; + a = 6; + } + while (f()) { + a = 5; + if (f()) + break; + a = 6; + } +#pragma endscop +} diff --git a/tests/while_break.scop b/tests/while_break.scop new file mode 100644 index 0000000..184d0f6 --- /dev/null +++ b/tests/while_break.scop @@ -0,0 +1,280 @@ +context: '[N] -> { : N <= 2147483647 and N >= -2147483648 }' +arrays: +- context: '{ : }' + extent: '[N] -> { __pet_test_0[t] : t >= 0 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '[N] -> { __pet_test_1[t] : N = 0 and t >= 1; __pet_test_1[0] }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '[N] -> { __pet_test_2[t] : t >= 0 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '[N] -> { __pet_test_3[t] : t >= 0 }' + value_bounds: '{ [i0] : i0 >= 0 and i0 <= 1 }' + element_type: int + element_size: 4 + uniquely_defined: 1 +- context: '{ : }' + extent: '[N] -> { a[] }' + element_type: int + element_size: 4 +statements: +- line: 10 + domain: '[N] -> { S_0[t] : N = 0 and t >= 1; S_0[0] }' + schedule: '{ S_0[t] -> [0, t, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '[N] -> { S_0[t] -> a[] }' + read: 0 + write: 1 + - type: access + relation: '[N] -> { S_0[t] -> [5] }' + read: 1 + write: 0 +- line: 13 + domain: '[N] -> { S_1[t] : N = 0 and t >= 1; S_1[0] : N = 0 }' + schedule: '{ S_1[t] -> [0, t, 2] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '[N] -> { S_1[t] -> a[] }' + read: 0 + write: 1 + - type: access + relation: '[N] -> { S_1[t] -> [6] }' + read: 1 + write: 0 +- line: 16 + domain: '[N] -> { [S_2[t] -> [0]] : t >= 0 }' + schedule: '{ S_2[t] -> [1, t, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '[N] -> { S_2[t] -> a[] }' + read: 0 + write: 1 + - type: access + relation: '[N] -> { S_2[t] -> [5] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '[N] -> { S_2[t] -> __pet_test_0[o0] : o0 <= -1 + t and o0 >= 0 }' + read: 1 + write: 0 +- line: 17 + domain: '[N] -> { [S_3[t] -> [0]] : t >= 0 }' + schedule: '{ S_3[t] -> [1, t, 1, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '[N] -> { S_3[t] -> __pet_test_0[t] }' + read: 0 + write: 1 + - type: call + name: f + arguments: + - type: access + relation: '[N] -> { S_3[t] -> __pet_test_0[o0] : o0 <= -1 + t and o0 >= 0 }' + read: 1 + write: 0 +- line: 19 + domain: '[N] -> { [S_4[t] -> [0, 0]] : t >= 0 }' + schedule: '{ S_4[t] -> [1, t, 2] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '[N] -> { S_4[t] -> a[] }' + read: 0 + write: 1 + - type: access + relation: '[N] -> { S_4[t] -> [6] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '[N] -> { S_4[t] -> __pet_test_0[o0] : o0 <= -1 + t and o0 >= 0 }' + read: 1 + write: 0 + - type: access + relation: '[N] -> { S_4[t] -> __pet_test_0[t] }' + read: 1 + write: 0 +- line: 21 + domain: '[N] -> { [S_5[t] -> [1]] : N = 0 and t >= 1; [S_5[0] -> [1]] }' + schedule: '{ S_5[t] -> [2, t, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '[N] -> { S_5[t] -> __pet_test_1[t] }' + read: 0 + write: 1 + - type: call + name: f + arguments: + - type: access + relation: '[N] -> { S_5[t] -> __pet_test_1[o0] : N = 0 and o0 <= -1 + t and o0 + >= 1; S_5[t] -> __pet_test_1[0] : t >= 1 }' + read: 1 + write: 0 +- line: 22 + domain: '[N] -> { [S_6[t] -> [1]] : N = 0 and t >= 1; [S_6[0] -> [1]] }' + schedule: '{ S_6[t] -> [2, t, 1, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '[N] -> { S_6[t] -> a[] }' + read: 0 + write: 1 + - type: access + relation: '[N] -> { S_6[t] -> [5] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '[N] -> { S_6[t] -> __pet_test_1[o0] : N = 0 and o0 <= t and o0 >= 1; + S_6[t] -> __pet_test_1[0] }' + read: 1 + write: 0 +- line: 25 + domain: '[N] -> { [S_7[t] -> [1]] : N = 0 and t >= 1; [S_7[0] -> [1]] : N = 0 }' + schedule: '{ S_7[t] -> [2, t, 1, 2] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '[N] -> { S_7[t] -> a[] }' + read: 0 + write: 1 + - type: access + relation: '[N] -> { S_7[t] -> [6] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '[N] -> { S_7[t] -> __pet_test_1[o0] : o0 <= t and o0 >= 1; S_7[t] -> + __pet_test_1[0] }' + read: 1 + write: 0 +- line: 27 + domain: '[N] -> { [S_8[t] -> [1, 0]] : t >= 0 }' + schedule: '{ S_8[t] -> [3, t, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '[N] -> { S_8[t] -> __pet_test_2[t] }' + read: 0 + write: 1 + - type: call + name: f + arguments: + - type: access + relation: '[N] -> { S_8[t] -> __pet_test_2[o0] : o0 <= -1 + t and o0 >= 0 }' + read: 1 + write: 0 + - type: access + relation: '[N] -> { S_8[t] -> __pet_test_3[o0] : o0 <= -1 + t and o0 >= 0 }' + read: 1 + write: 0 +- line: 28 + domain: '[N] -> { [S_9[t] -> [1, 0]] : t >= 0 }' + schedule: '{ S_9[t] -> [3, t, 1, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '[N] -> { S_9[t] -> a[] }' + read: 0 + write: 1 + - type: access + relation: '[N] -> { S_9[t] -> [5] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '[N] -> { S_9[t] -> __pet_test_2[o0] : o0 <= t and o0 >= 0 }' + read: 1 + write: 0 + - type: access + relation: '[N] -> { S_9[t] -> __pet_test_3[o0] : o0 <= -1 + t and o0 >= 0 }' + read: 1 + write: 0 +- line: 29 + domain: '[N] -> { [S_10[t] -> [1, 0]] : t >= 0 }' + schedule: '{ S_10[t] -> [3, t, 1, 1, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '[N] -> { S_10[t] -> __pet_test_3[t] }' + read: 0 + write: 1 + - type: call + name: f + arguments: + - type: access + relation: '[N] -> { S_10[t] -> __pet_test_2[o0] : o0 <= t and o0 >= 0 }' + read: 1 + write: 0 + - type: access + relation: '[N] -> { S_10[t] -> __pet_test_3[o0] : o0 <= -1 + t and o0 >= 0 }' + read: 1 + write: 0 +- line: 31 + domain: '[N] -> { [S_11[t] -> [1, 0, 0]] : t >= 0 }' + schedule: '{ S_11[t] -> [3, t, 1, 2] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '[N] -> { S_11[t] -> a[] }' + read: 0 + write: 1 + - type: access + relation: '[N] -> { S_11[t] -> [6] }' + read: 1 + write: 0 + arguments: + - type: access + relation: '[N] -> { S_11[t] -> __pet_test_2[o0] : o0 <= t and o0 >= 0 }' + read: 1 + write: 0 + - type: access + relation: '[N] -> { S_11[t] -> __pet_test_3[o0] : o0 <= -1 + t and o0 >= 0 }' + read: 1 + write: 0 + - type: access + relation: '[N] -> { S_11[t] -> __pet_test_3[t] }' + read: 1 + write: 0 -- 2.11.4.GIT