From b3c3e43f352fda26cc9c00fcf6fc2c226dce421a Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Fri, 17 Oct 2014 15:30:38 +0200 Subject: [PATCH] add support for __pencil_kill This statement allows the user to explicitly mark (part of) arrays dead, meaning that the user certifies that no data can flow through the marked array elements from a statement instance executed before the kill instance to a statement instance executed after the kill instance. Signed-off-by: Sven Verdoolaege --- pet.cc | 3 +- scan.cc | 8 ++- tests/kill.c | 16 ++++++ tests/kill.scop | 157 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ tree2scop.c | 121 +++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 303 insertions(+), 2 deletions(-) create mode 100644 tests/kill.c create mode 100644 tests/kill.scop diff --git a/pet.cc b/pet.cc index 5aae4de..94636f2 100644 --- a/pet.cc +++ b/pet.cc @@ -695,7 +695,8 @@ static const char *ResourceDir = CLANG_PREFIX "/lib/clang/" CLANG_VERSION_STRING; static const char *implicit_functions[] = { - "min", "max", "intMod", "intCeil", "intFloor", "ceild", "floord" + "min", "max", "intMod", "intCeil", "intFloor", "ceild", "floord", + "__pencil_kill" }; static bool is_implicit(const IdentifierInfo *ident) diff --git a/scan.cc b/scan.cc index bc61e54..e6298d2 100644 --- a/scan.cc +++ b/scan.cc @@ -925,6 +925,10 @@ FunctionDecl *PetScan::get_summary_function(CallExpr *call) * * In the special case of a "call" to __pencil_assume, * construct an assume expression instead. + * + * In the case of a "call" to __pencil_kill, the arguments + * are neither read nor written (only killed), so there + * is no need to check for writes to these arguments. */ __isl_give pet_expr *PetScan::extract_expr(CallExpr *expr) { @@ -932,6 +936,7 @@ __isl_give pet_expr *PetScan::extract_expr(CallExpr *expr) FunctionDecl *fd; string name; unsigned n_arg; + bool is_kill; fd = expr->getDirectCallee(); if (!fd) { @@ -944,6 +949,7 @@ __isl_give pet_expr *PetScan::extract_expr(CallExpr *expr) if (n_arg == 1 && name == "__pencil_assume") return extract_assume(expr->getArg(0)); + is_kill = name == "__pencil_kill"; res = pet_expr_new_call(ctx, name.c_str(), n_arg); if (!res) @@ -952,7 +958,7 @@ __isl_give pet_expr *PetScan::extract_expr(CallExpr *expr) for (int i = 0; i < n_arg; ++i) { Expr *arg = expr->getArg(i); res = pet_expr_set_arg(res, i, - PetScan::extract_argument(fd, i, arg, 1)); + PetScan::extract_argument(fd, i, arg, !is_kill)); } fd = get_summary_function(expr); diff --git a/tests/kill.c b/tests/kill.c new file mode 100644 index 0000000..edc88b3 --- /dev/null +++ b/tests/kill.c @@ -0,0 +1,16 @@ +void foo(int n, int A[n], int C[n]) +{ + int t; + int B[n]; + int D[n][n]; +#pragma scop + __pencil_kill(C); + for (int i = 0; i < n; ++i) { + t = A[i]; + B[i] = t; + C[i] = B[i]; + __pencil_kill(t, B[i], D[i]); + } + __pencil_kill(A); +#pragma endscop +} diff --git a/tests/kill.scop b/tests/kill.scop new file mode 100644 index 0000000..981c1c8 --- /dev/null +++ b/tests/kill.scop @@ -0,0 +1,157 @@ +start: 71 +end: 243 +indent: "\t" +context: '[n] -> { : n >= 0 and n <= 2147483647 }' +arrays: +- context: '{ : }' + extent: '[n] -> { A[i0] : i0 >= 0 }' + element_type: int + element_size: 4 +- context: '[n] -> { : n >= 0 }' + extent: '[n] -> { B[i0] : i0 <= -1 + n and i0 >= 0 }' + element_type: int + element_size: 4 +- context: '{ : }' + extent: '[n] -> { C[i0] : i0 >= 0 }' + element_type: int + element_size: 4 +- context: '[n] -> { : n >= 0 }' + extent: '[n] -> { D[i0, i1] : i0 >= 0 and i0 <= -1 + n and i1 <= -1 + n and i1 >= + 0 }' + element_type: int + element_size: 4 +- context: '{ : }' + extent: '[n] -> { t[] }' + element_type: int + element_size: 4 +statements: +- line: 7 + domain: '[n] -> { S_0[] }' + schedule: '{ S_0[] -> [0] }' + body: + type: expression + expr: + type: op + operation: kill + arguments: + - type: access + killed: '[n] -> { S_0[] -> C[o0] : o0 >= 0 }' + index: '[n] -> { S_0[] -> C[] }' + depth: 1 + reference: __pet_ref_0 + kill: 1 +- line: 9 + domain: '[n] -> { S_1[i] : i <= -1 + n and i >= 0 }' + schedule: '[n] -> { S_1[i] -> [1, i, 0] }' + body: + type: expression + expr: + type: op + operation: = + arguments: + - type: access + index: '[n] -> { S_1[i] -> t[] }' + reference: __pet_ref_1 + read: 0 + write: 1 + - type: access + index: '[n] -> { S_1[i] -> A[(i)] }' + reference: __pet_ref_2 + read: 1 + write: 0 +- line: 10 + domain: '[n] -> { S_2[i] : i <= -1 + n and i >= 0 }' + schedule: '[n] -> { S_2[i] -> [1, i, 1] }' + body: + type: expression + expr: + type: op + operation: = + arguments: + - type: access + index: '[n] -> { S_2[i] -> B[(i)] }' + reference: __pet_ref_3 + read: 0 + write: 1 + - type: access + index: '[n] -> { S_2[i] -> t[] }' + reference: __pet_ref_4 + read: 1 + write: 0 +- line: 11 + domain: '[n] -> { S_3[i] : i <= -1 + n and i >= 0 }' + schedule: '[n] -> { S_3[i] -> [1, i, 2] }' + body: + type: expression + expr: + type: op + operation: = + arguments: + - type: access + index: '[n] -> { S_3[i] -> C[(i)] }' + reference: __pet_ref_5 + read: 0 + write: 1 + - type: access + index: '[n] -> { S_3[i] -> B[(i)] }' + reference: __pet_ref_6 + read: 1 + write: 0 +- line: 12 + domain: '[n] -> { S_4[i] : i <= -1 + n and i >= 0 }' + schedule: '[n] -> { S_4[i] -> [1, i, 3] }' + body: + type: expression + expr: + type: op + operation: kill + arguments: + - type: access + killed: '[n] -> { S_4[i] -> t[] }' + index: '[n] -> { S_4[i] -> t[] }' + reference: __pet_ref_7 + kill: 1 +- line: 12 + domain: '[n] -> { S_5[i] : i <= -1 + n and i >= 0 }' + schedule: '[n] -> { S_5[i] -> [1, i, 3] }' + body: + type: expression + expr: + type: op + operation: kill + arguments: + - type: access + killed: '[n] -> { S_5[i] -> B[i] }' + index: '[n] -> { S_5[i] -> B[(i)] }' + reference: __pet_ref_8 + kill: 1 +- line: 12 + domain: '[n] -> { S_6[i] : i <= -1 + n and i >= 0 }' + schedule: '[n] -> { S_6[i] -> [1, i, 3] }' + body: + type: expression + expr: + type: op + operation: kill + arguments: + - type: access + killed: '[n] -> { S_6[i] -> D[i, o1] : o1 >= 0 and o1 <= -1 + n }' + index: '[n] -> { S_6[i] -> D[(i)] }' + depth: 2 + reference: __pet_ref_9 + kill: 1 +- line: 14 + domain: '[n] -> { S_7[] }' + schedule: '{ S_7[] -> [2] }' + body: + type: expression + expr: + type: op + operation: kill + arguments: + - type: access + killed: '[n] -> { S_7[] -> A[o0] : o0 >= 0 }' + index: '[n] -> { S_7[] -> A[] }' + depth: 1 + reference: __pet_ref_10 + kill: 1 diff --git a/tree2scop.c b/tree2scop.c index ae0a210..b6ef4b3 100644 --- a/tree2scop.c +++ b/tree2scop.c @@ -32,6 +32,8 @@ * Leiden University. */ +#include + #include #include "aff.h" @@ -245,11 +247,130 @@ static struct pet_scop *scop_from_decl(__isl_keep pet_tree *tree, return scop; } +/* Does "tree" represent a kill statement? + * That is, is it an expression statement that "calls" __pencil_kill? + */ +static int is_pencil_kill(__isl_keep pet_tree *tree) +{ + pet_expr *expr; + const char *name; + + if (!tree) + return -1; + if (tree->type != pet_tree_expr) + return 0; + expr = tree->u.e.expr; + if (pet_expr_get_type(expr) != pet_expr_call) + return 0; + name = pet_expr_call_get_name(expr); + if (!name) + return -1; + return !strcmp(name, "__pencil_kill"); +} + +/* Add a kill to "scop" that kills what is accessed by + * the access expression "expr". + * + * If the access expression has any arguments (after evaluation + * in the context of "pc"), then we ignore it, since we cannot + * tell which elements are definitely killed. + * + * Otherwise, we extend the index expression to the dimension + * of the accessed array and intersect with the extent of the array and + * add a kill expression that kills these array elements is added to "scop". + */ +static struct pet_scop *scop_add_kill(struct pet_scop *scop, + __isl_take pet_expr *expr, __isl_take pet_loc *loc, + __isl_keep pet_context *pc, struct pet_state *state) +{ + int dim1, dim2; + isl_id *id; + isl_multi_pw_aff *index; + isl_map *map; + pet_expr *kill; + struct pet_array *array; + struct pet_scop *scop_i; + + expr = pet_context_evaluate_expr(pc, expr); + if (!expr) + goto error; + if (expr->n_arg != 0) { + pet_expr_free(expr); + return scop; + } + array = extract_array(expr, pc, state); + if (!array) + goto error; + index = pet_expr_access_get_index(expr); + pet_expr_free(expr); + map = isl_map_from_multi_pw_aff(isl_multi_pw_aff_copy(index)); + id = isl_map_get_tuple_id(map, isl_dim_out); + dim1 = isl_set_dim(array->extent, isl_dim_set); + dim2 = isl_map_dim(map, isl_dim_out); + map = isl_map_add_dims(map, isl_dim_out, dim1 - dim2); + map = isl_map_set_tuple_id(map, isl_dim_out, id); + map = isl_map_intersect_range(map, isl_set_copy(array->extent)); + pet_array_free(array); + kill = pet_expr_kill_from_access_and_index(map, index); + scop_i = scop_from_evaluated_expr(kill, state->n_stmt++, loc, pc); + scop = pet_scop_add_par(state->ctx, scop, scop_i); + + return scop; +error: + pet_expr_free(expr); + return pet_scop_free(scop); +} + +/* For each argument of the __pencil_kill call in "tree" that + * represents an access, add a kill statement to "scop" killing the accessed + * elements. + */ +static struct pet_scop *scop_from_pencil_kill(__isl_keep pet_tree *tree, + __isl_keep pet_context *pc, struct pet_state *state) +{ + pet_expr *call; + struct pet_scop *scop; + int i, n; + + call = tree->u.e.expr; + + scop = pet_scop_empty(pet_context_get_space(pc)); + + n = pet_expr_get_n_arg(call); + for (i = 0; i < n; ++i) { + pet_expr *arg; + pet_loc *loc; + + arg = pet_expr_get_arg(call, i); + if (!arg) + return pet_scop_free(scop); + if (pet_expr_get_type(arg) != pet_expr_access) { + pet_expr_free(arg); + continue; + } + loc = pet_tree_get_loc(tree); + scop = scop_add_kill(scop, arg, loc, pc, state); + } + + return scop; +} + /* Construct a pet_scop for an expression statement within the context "pc". + * + * If the expression calls __pencil_kill, then it needs to be converted + * into zero or more kill statements. + * Otherwise, a scop is extracted directly from the tree. */ static struct pet_scop *scop_from_tree_expr(__isl_keep pet_tree *tree, __isl_keep pet_context *pc, struct pet_state *state) { + int is_kill; + + is_kill = is_pencil_kill(tree); + if (is_kill < 0) + return NULL; + if (is_kill) + return scop_from_pencil_kill(tree, pc, state); return scop_from_unevaluated_tree(pet_tree_copy(tree), state->n_stmt++, pc); } -- 2.11.4.GIT