From 7af3821eabd6bdb7030d8121f0093b1b168e6709 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Tue, 17 Apr 2012 09:57:35 +0200 Subject: [PATCH] add support for (single) declarations For every declaration, we record that the declared variable was declared somewhere inside the scop and we introduce a kill statement at the location of the declaration. This allows users who perform dataflow analysis to stop looking for sources before the declaration. If the declaration appears inside a block, we also add a kill statement at the end of the block. This signals to the same users that the value of the variable will not be used after the block. Otherwise, we mark the variable as being exposed to the outside of the scop. In autodetect mode, we skip declarations in the outer scope. We do this to avoid autodetecting scops containing only declarations. Signed-off-by: Sven Verdoolaege --- emit.c | 5 ++ include/pet.h | 6 ++ parse.c | 4 + scan.cc | 171 +++++++++++++++++++++++++++++++++++++-- scan.h | 14 +++- scop.c | 22 ++++- scop.h | 1 + tests/decl.c | 15 ++++ tests/decl.scop | 100 +++++++++++++++++++++++ tests/forward_substitution3.c | 10 +++ tests/forward_substitution3.scop | 101 +++++++++++++++++++++++ 11 files changed, 437 insertions(+), 12 deletions(-) create mode 100644 tests/decl.c create mode 100644 tests/decl.scop create mode 100644 tests/forward_substitution3.c create mode 100644 tests/forward_substitution3.scop diff --git a/emit.c b/emit.c index e2371f3..ac70e2d 100644 --- a/emit.c +++ b/emit.c @@ -165,6 +165,11 @@ static int emit_array(yaml_emitter_t *emitter, struct pet_array *array) return -1; } + if (array->declared && emit_named_int(emitter, "declared", 1) < 0) + return -1; + if (array->exposed && emit_named_int(emitter, "exposed", 1) < 0) + return -1; + if (!yaml_mapping_end_event_initialize(&event)) return -1; if (!yaml_emitter_emit(emitter, &event)) diff --git a/include/pet.h b/include/pet.h index 3938c45..e4068fb 100644 --- a/include/pet.h +++ b/include/pet.h @@ -55,6 +55,7 @@ enum pet_op_type { pet_op_pre_inc, pet_op_pre_dec, pet_op_address_of, + pet_op_kill, pet_op_last }; @@ -151,6 +152,9 @@ struct pet_stmt { * if uniquely_defined is set then the array is written by a single access * such that any element that is ever read * is known to be assigned exactly once before the read + * + * declared is set if the array was declared somewhere inside the scop. + * exposed is set if the declared array is visible outside the scop. */ struct pet_array { isl_set *context; @@ -160,6 +164,8 @@ struct pet_array { int element_size; int live_out; int uniquely_defined; + int declared; + int exposed; }; /* The context describes the set of parameter values for which diff --git a/parse.c b/parse.c index 859015b..53684b3 100644 --- a/parse.c +++ b/parse.c @@ -149,6 +149,10 @@ static struct pet_array *extract_array(isl_ctx *ctx, yaml_document_t *document, "uniquely_defined")) array->uniquely_defined = extract_int(ctx, document, value); + if (!strcmp((char *) key->data.scalar.value, "declared")) + array->declared = extract_int(ctx, document, value); + if (!strcmp((char *) key->data.scalar.value, "exposed")) + array->exposed = extract_int(ctx, document, value); } return array; diff --git a/scan.cc b/scan.cc index 3935b03..2f3de08 100644 --- a/scan.cc +++ b/scan.cc @@ -892,7 +892,18 @@ static QualType base_type(QualType qt) */ __isl_give isl_map *PetScan::extract_access(DeclRefExpr *expr) { - ValueDecl *decl = expr->getDecl(); + return extract_access(expr->getDecl()); +} + +/* Extract an access relation from a variable. + * If the variable has name "A" and its type corresponds to an + * array of depth d, then the returned access relation is of the + * form + * + * { [] -> A[i_1,...,i_d] } + */ +__isl_give isl_map *PetScan::extract_access(ValueDecl *decl) +{ int depth = array_depth(decl->getType().getTypePtr()); isl_id *id = isl_id_alloc(ctx, decl->getName().str().c_str(), decl); isl_space *dim = isl_space_alloc(ctx, 0, 0, depth); @@ -1450,6 +1461,71 @@ struct pet_expr *PetScan::extract_expr(BinaryOperator *expr) return pet_expr_new_binary(ctx, op, lhs, rhs); } +/* Construct a pet_scop with a single statement killing the entire + * array "array". + */ +struct pet_scop *PetScan::kill(Stmt *stmt, struct pet_array *array) +{ + isl_map *access; + struct pet_expr *expr; + + if (!array) + return NULL; + access = isl_map_from_range(isl_set_copy(array->extent)); + expr = pet_expr_kill_from_access(access); + return extract(stmt, expr); +} + +/* Construct a pet_scop for a (single) variable declaration. + * + * The scop contains the variable being declared (as an array) + * and a statement killing the array. + * + * If the variable is initialized in the AST, then the scop + * also contains an assignment to the variable. + */ +struct pet_scop *PetScan::extract(DeclStmt *stmt) +{ + Decl *decl; + VarDecl *vd; + struct pet_expr *lhs, *rhs, *pe; + struct pet_scop *scop_decl, *scop; + struct pet_array *array; + + if (!stmt->isSingleDecl()) { + unsupported(stmt); + return NULL; + } + + decl = stmt->getSingleDecl(); + vd = cast(decl); + + array = extract_array(ctx, vd); + if (array) + array->declared = 1; + scop_decl = kill(stmt, array); + scop_decl = pet_scop_add_array(scop_decl, array); + + if (!vd->getInit()) + return scop_decl; + + lhs = pet_expr_from_access(extract_access(vd)); + rhs = extract_expr(vd->getInit()); + + mark_write(lhs); + assign(lhs, vd->getInit()); + + pe = pet_expr_new_binary(ctx, pet_op_assign, lhs, rhs); + scop = extract(stmt, pe); + + scop_decl = pet_scop_prefix(scop_decl, 0); + scop = pet_scop_prefix(scop, 1); + + scop = pet_scop_add_seq(ctx, scop_decl, scop); + + return scop; +} + /* Construct a pet_expr representing a conditional operation. * * We first try to extract the condition as an affine expression. @@ -2835,9 +2911,9 @@ struct pet_scop *PetScan::extract_for(ForStmt *stmt) return scop; } -struct pet_scop *PetScan::extract(CompoundStmt *stmt) +struct pet_scop *PetScan::extract(CompoundStmt *stmt, bool skip_declarations) { - return extract(stmt->children()); + return extract(stmt->children(), true, skip_declarations); } /* Does parameter "pos" of "map" refer to a nested access? @@ -4169,8 +4245,12 @@ struct pet_scop *PetScan::extract(BreakStmt *stmt) } /* Try and construct a pet_scop corresponding to "stmt". + * + * If "stmt" is a compound statement, then "skip_declarations" + * indicates whether we should skip initial declarations in the + * compound statement. */ -struct pet_scop *PetScan::extract(Stmt *stmt) +struct pet_scop *PetScan::extract(Stmt *stmt, bool skip_declarations) { if (isa(stmt)) return extract(stmt, extract_expr(cast(stmt))); @@ -4183,13 +4263,15 @@ struct pet_scop *PetScan::extract(Stmt *stmt) case Stmt::IfStmtClass: return extract(cast(stmt)); case Stmt::CompoundStmtClass: - return extract(cast(stmt)); + return extract(cast(stmt), skip_declarations); case Stmt::LabelStmtClass: return extract(cast(stmt)); case Stmt::ContinueStmtClass: return extract(cast(stmt)); case Stmt::BreakStmtClass: return extract(cast(stmt)); + case Stmt::DeclStmtClass: + return extract(cast(stmt)); default: unsupported(stmt); } @@ -4371,27 +4453,87 @@ struct pet_scop *pet_skip_info_seq::add(struct pet_scop *scop, int offset) return scop; } +/* Extract a clone of the kill statement in "scop". + * "scop" is expected to have been created from a DeclStmt + * and should have the kill as its first statement. + */ +struct pet_stmt *PetScan::extract_kill(struct pet_scop *scop) +{ + struct pet_expr *kill; + struct pet_stmt *stmt; + isl_map *access; + + if (!scop) + return NULL; + if (scop->n_stmt < 1) + isl_die(ctx, isl_error_internal, + "expecting at least one statement", return NULL); + stmt = scop->stmts[0]; + if (stmt->body->type != pet_expr_unary || + stmt->body->op != pet_op_kill) + isl_die(ctx, isl_error_internal, + "expecting kill statement", return NULL); + + access = isl_map_copy(stmt->body->args[0]->acc.access); + access = isl_map_reset_tuple_id(access, isl_dim_in); + kill = pet_expr_kill_from_access(access); + return pet_stmt_from_pet_expr(ctx, stmt->line, NULL, n_stmt++, kill); +} + +/* Mark all arrays in "scop" as being exposed. + */ +static struct pet_scop *mark_exposed(struct pet_scop *scop) +{ + if (!scop) + return NULL; + for (int i = 0; i < scop->n_array; ++i) + scop->arrays[i]->exposed = 1; + return scop; +} + /* Try and construct a pet_scop corresponding to (part of) * a sequence of statements. * + * "block" is set if the sequence respresents the children of + * a compound statement. + * "skip_declarations" is set if we should skip initial declarations + * in the 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". + * + * If "block" is set, then we need to insert kill statements at + * the end of the block for any array that has been declared by + * one of the statements in the sequence. Each of these declarations + * results in the construction of a kill statement at the place + * of the declaration, so we simply collect duplicates of + * those kill statements and append these duplicates to the constructed scop. + * + * If "block" is not set, then any array declared by one of the statements + * in the sequence is marked as being exposed. */ -struct pet_scop *PetScan::extract(StmtRange stmt_range) +struct pet_scop *PetScan::extract(StmtRange stmt_range, bool block, + bool skip_declarations) { pet_scop *scop; StmtIterator i; int j; bool partial_range = false; + set kills; + set::iterator it; scop = pet_scop_empty(ctx); for (i = stmt_range.first, j = 0; i != stmt_range.second; ++i, ++j) { Stmt *child = *i; struct pet_scop *scop_i; + if (skip_declarations && + child->getStmtClass() == Stmt::DeclStmtClass) + continue; + scop_i = extract(child); if (scop && partial) { pet_scop_free(scop_i); @@ -4401,6 +4543,12 @@ struct pet_scop *PetScan::extract(StmtRange stmt_range) skip.extract(this); if (skip) scop_i = pet_scop_prefix(scop_i, 0); + if (scop_i && child->getStmtClass() == Stmt::DeclStmtClass) { + if (block) + kills.insert(extract_kill(scop_i)); + else + scop_i = mark_exposed(scop_i); + } scop_i = pet_scop_prefix(scop_i, j); if (options->autodetect) { if (scop_i) @@ -4419,6 +4567,13 @@ struct pet_scop *PetScan::extract(StmtRange stmt_range) break; } + for (it = kills.begin(); it != kills.end(); ++it) { + pet_scop *scop_j; + scop_j = pet_scop_from_pet_stmt(ctx, *it); + scop_j = pet_scop_prefix(scop_j, j); + scop = pet_scop_add_seq(ctx, scop, scop_j); + } + if (scop && partial_range) partial = true; @@ -4474,7 +4629,7 @@ struct pet_scop *PetScan::scan(Stmt *stmt) break; } - return extract(StmtRange(start, end)); + return extract(StmtRange(start, end), false, false); } /* Set the size of index "pos" of "array" to "size". @@ -4734,7 +4889,7 @@ struct pet_scop *PetScan::scan(FunctionDecl *fd) stmt = fd->getBody(); if (options->autodetect) - scop = extract(stmt); + scop = extract(stmt, true); else scop = scan(stmt); scop = pet_scop_detect_parameter_accesses(scop); diff --git a/scan.h b/scan.h index b2b98e6..0c1e2c6 100644 --- a/scan.h +++ b/scan.h @@ -99,17 +99,24 @@ private: struct pet_scop *scop_then, struct pet_scop *scop_else, bool have_else, int stmt_id); - struct pet_scop *extract(clang::Stmt *stmt); - struct pet_scop *extract(clang::StmtRange stmt_range); + struct pet_scop *kill(clang::Stmt *stmt, struct pet_array *array); + + struct pet_scop *extract(clang::Stmt *stmt, + bool skip_declarations = false); + struct pet_scop *extract(clang::StmtRange stmt_range, bool block, + bool skip_declarations); struct pet_scop *extract(clang::IfStmt *stmt); struct pet_scop *extract(clang::WhileStmt *stmt); - struct pet_scop *extract(clang::CompoundStmt *stmt); + struct pet_scop *extract(clang::CompoundStmt *stmt, + bool skip_declarations = false); 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::DeclStmt *expr); struct pet_scop *extract(clang::Stmt *stmt, struct pet_expr *expr, __isl_take isl_id *label = NULL); + struct pet_stmt *extract_kill(struct pet_scop *scop); clang::BinaryOperator *initialization_assignment(clang::Stmt *init); clang::Decl *initialization_declaration(clang::Stmt *init); @@ -158,6 +165,7 @@ private: __isl_give isl_map *extract_access(clang::Expr *expr); __isl_give isl_map *extract_access(clang::ImplicitCastExpr *expr); __isl_give isl_map *extract_access(clang::DeclRefExpr *expr); + __isl_give isl_map *extract_access(clang::ValueDecl *decl); __isl_give isl_map *extract_access(clang::IntegerLiteral *expr); int extract_int(clang::Expr *expr, isl_int *v); diff --git a/scop.c b/scop.c index 034f414..fda228d 100644 --- a/scop.c +++ b/scop.c @@ -68,7 +68,8 @@ static char *op_str[] = { [pet_op_post_dec] = "--", [pet_op_pre_inc] = "++", [pet_op_pre_dec] = "--", - [pet_op_address_of] = "&" + [pet_op_address_of] = "&", + [pet_op_kill] = "kill" }; /* pet_scop with extra information that is only used during parsing. @@ -156,6 +157,21 @@ error: return NULL; } +/* Construct a pet_expr that kills the elements specified by "access". + */ +struct pet_expr *pet_expr_kill_from_access(__isl_take isl_map *access) +{ + isl_ctx *ctx; + struct pet_expr *expr; + + ctx = isl_map_get_ctx(access); + expr = pet_expr_from_access(access); + if (!expr) + return NULL; + expr->acc.read = 0; + return pet_expr_new_unary(ctx, pet_op_kill, expr); +} + /* Construct a unary pet_expr that performs "op" on "arg". */ struct pet_expr *pet_expr_new_unary(isl_ctx *ctx, enum pet_op_type op, @@ -1092,6 +1108,10 @@ int pet_array_is_equal(struct pet_array *array1, struct pet_array *array2) return 0; if (array1->uniquely_defined != array2->uniquely_defined) return 0; + if (array1->declared != array2->declared) + return 0; + if (array1->exposed != array2->exposed) + return 0; return 1; } diff --git a/scop.h b/scop.h index aa6719b..c06c928 100644 --- a/scop.h +++ b/scop.h @@ -20,6 +20,7 @@ enum pet_expr_type pet_str_type(const char *str); enum pet_op_type pet_str_op(const char *str); struct pet_expr *pet_expr_from_access(__isl_take isl_map *access); +struct pet_expr *pet_expr_kill_from_access(__isl_take isl_map *access); struct pet_expr *pet_expr_new_unary(isl_ctx *ctx, enum pet_op_type op, struct pet_expr *arg); struct pet_expr *pet_expr_new_binary(isl_ctx *ctx, enum pet_op_type op, diff --git a/tests/decl.c b/tests/decl.c new file mode 100644 index 0000000..7aa7348 --- /dev/null +++ b/tests/decl.c @@ -0,0 +1,15 @@ +void matmul(int M, int N, int K, float A[M][K], float B[K][N], float C[M][N]) +{ + int i, j, k; + +#pragma scop + for (i = 0; i < M; i++) + for (j = 0; j < N; j++) { + C[i][j] = 0; + for (k = 0; k < K; k++) { + float t = A[i][k] * B[k][j]; + C[i][j] += t; + } + } +#pragma endscop +} diff --git a/tests/decl.scop b/tests/decl.scop new file mode 100644 index 0000000..056c8ed --- /dev/null +++ b/tests/decl.scop @@ -0,0 +1,100 @@ +context: '[N, K, M] -> { : K >= 0 and N >= 0 and N <= 2147483647 and K <= 2147483647 + and M <= 2147483647 and M >= -2147483648 }' +arrays: +- context: '{ : }' + extent: '[N, K, M] -> { t[] }' + element_type: float + element_size: 4 + declared: 1 +- context: '[K] -> { : K >= 0 }' + extent: '[N, K, M] -> { A[i0, i1] : i1 >= 0 and i0 >= 0 and i1 <= -1 + K }' + element_type: float + element_size: 4 +- context: '[N] -> { : N >= 0 }' + extent: '[N, K, M] -> { B[i0, i1] : i1 >= 0 and i1 <= -1 + N and i0 >= 0 }' + element_type: float + element_size: 4 +- context: '[N] -> { : N >= 0 }' + extent: '[N, K, M] -> { C[i0, i1] : i1 >= 0 and i1 <= -1 + N and i0 >= 0 }' + element_type: float + element_size: 4 +statements: +- line: 8 + domain: '[N, K, M] -> { S_0[i, j] : i >= 0 and i <= -1 + M and j >= 0 and j <= -1 + + N }' + schedule: '[N, M] -> { S_0[i, j] -> [0, i, j, 0] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '[N, K, M] -> { S_0[i, j] -> C[i, j] }' + read: 0 + write: 1 + - type: access + relation: '[N, K, M] -> { S_0[i, j] -> [0] }' + read: 1 + write: 0 +- line: 10 + domain: '[N, K, M] -> { S_1[i, j, k] : k >= 0 and j >= 0 and j <= -1 + N and k <= + -1 + K and i >= 0 and i <= -1 + M }' + schedule: '[K, N, M] -> { S_1[i, j, k] -> [0, i, j, 1, k, 0, 0] }' + body: + type: unary + operation: kill + arguments: + - type: access + relation: '[N, K, M] -> { S_1[i, j, k] -> t[] }' + read: 0 + write: 0 +- line: 10 + domain: '[N, K, M] -> { S_2[i, j, k] : k >= 0 and j >= 0 and j <= -1 + N and k <= + -1 + K and i >= 0 and i <= -1 + M }' + schedule: '[K, N, M] -> { S_2[i, j, k] -> [0, i, j, 1, k, 0, 1] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '[N, K, M] -> { S_2[i, j, k] -> t[] }' + read: 0 + write: 1 + - type: binary + operation: '*' + arguments: + - type: access + relation: '[N, K, M] -> { S_2[i, j, k] -> A[i, k] }' + read: 1 + write: 0 + - type: access + relation: '[N, K, M] -> { S_2[i, j, k] -> B[k, j] }' + read: 1 + write: 0 +- line: 11 + domain: '[N, K, M] -> { S_4[i, j, k] : k >= 0 and j >= 0 and j <= -1 + N and k <= + -1 + K and i >= 0 and i <= -1 + M }' + schedule: '[K, N, M] -> { S_4[i, j, k] -> [0, i, j, 1, k, 1] }' + body: + type: binary + operation: += + arguments: + - type: access + relation: '[N, K, M] -> { S_4[i, j, k] -> C[i, j] }' + read: 1 + write: 1 + - type: access + relation: '[N, K, M] -> { S_4[i, j, k] -> t[] }' + read: 1 + write: 0 +- line: 10 + domain: '[N, K, M] -> { S_3[i, j, k] : k >= 0 and j >= 0 and j <= -1 + N and k <= + -1 + K and i >= 0 and i <= -1 + M }' + schedule: '[K, N, M] -> { S_3[i, j, k] -> [0, i, j, 1, k, 2] }' + body: + type: unary + operation: kill + arguments: + - type: access + relation: '[N, K, M] -> { S_3[i, j, k] -> t[] }' + read: 0 + write: 0 diff --git a/tests/forward_substitution3.c b/tests/forward_substitution3.c new file mode 100644 index 0000000..6c0aee7 --- /dev/null +++ b/tests/forward_substitution3.c @@ -0,0 +1,10 @@ +void foo() +{ + int a[10]; +#pragma scop + int b = 1; + int c = b; + b = 2; + a[c] = 5; +#pragma endscop +} diff --git a/tests/forward_substitution3.scop b/tests/forward_substitution3.scop new file mode 100644 index 0000000..b60c444 --- /dev/null +++ b/tests/forward_substitution3.scop @@ -0,0 +1,101 @@ +context: '{ : }' +arrays: +- context: '{ : }' + extent: '{ b[] }' + element_type: int + element_size: 4 + declared: 1 + exposed: 1 +- context: '{ : }' + extent: '{ c[] }' + element_type: int + element_size: 4 + declared: 1 + exposed: 1 +- context: '{ : }' + extent: '{ a[i0] : i0 >= 0 and i0 <= 9 }' + element_type: int + element_size: 4 +statements: +- line: 5 + domain: '{ S_0[] }' + schedule: '{ S_0[] -> [0, 0] }' + body: + type: unary + operation: kill + arguments: + - type: access + relation: '{ S_0[] -> b[] }' + read: 0 + write: 0 +- line: 5 + domain: '{ S_1[] }' + schedule: '{ S_1[] -> [0, 1] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_1[] -> b[] }' + read: 0 + write: 1 + - type: access + relation: '{ S_1[] -> [1] }' + read: 1 + write: 0 +- line: 6 + domain: '{ S_2[] }' + schedule: '{ S_2[] -> [1, 0] }' + body: + type: unary + operation: kill + arguments: + - type: access + relation: '{ S_2[] -> c[] }' + read: 0 + write: 0 +- line: 6 + domain: '{ S_3[] }' + schedule: '{ S_3[] -> [1, 1] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_3[] -> c[] }' + read: 0 + write: 1 + - type: access + relation: '{ S_3[] -> b[] }' + read: 1 + write: 0 +- line: 7 + domain: '{ S_4[] }' + schedule: '{ S_4[] -> [2] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_4[] -> b[] }' + read: 0 + write: 1 + - type: access + relation: '{ S_4[] -> [2] }' + read: 1 + write: 0 +- line: 8 + domain: '{ S_5[] }' + schedule: '{ S_5[] -> [3] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '{ S_5[] -> a[1] }' + read: 0 + write: 1 + - type: access + relation: '{ S_5[] -> [5] }' + read: 1 + write: 0 -- 2.11.4.GIT