From 2c85578ee04ab63d698ce5e1b9d5aca8fb988bd7 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Fri, 12 Aug 2011 08:51:26 +0200 Subject: [PATCH] allow declaration of iterator in for loops Signed-off-by: Sven Verdoolaege --- scan.cc | 108 ++++++++++++++++++++++++++++++---------- scan.h | 7 ++- tests/iterator_declaration.c | 10 ++++ tests/iterator_declaration.scop | 21 ++++++++ 4 files changed, 119 insertions(+), 27 deletions(-) create mode 100644 tests/iterator_declaration.c create mode 100644 tests/iterator_declaration.scop diff --git a/scan.cc b/scan.cc index dd97edb..35ff190 100644 --- a/scan.cc +++ b/scan.cc @@ -738,7 +738,7 @@ static bool is_max(Expr *expr, Expr *&lhs, Expr *&rhs) } /* Extract a set of values satisfying the comparison "LHS op RHS" - * "comp" is the original expression that "LHS op RHS" is derived from + * "comp" is the original statement that "LHS op RHS" is derived from * and is used for diagnostics. * * If the comparison is of the form @@ -756,7 +756,7 @@ static bool is_max(Expr *expr, Expr *&lhs, Expr *&rhs) * this optimization can be removed. */ __isl_give isl_set *PetScan::extract_comparison(BinaryOperatorKind op, - Expr *LHS, Expr *RHS, Expr *comp) + Expr *LHS, Expr *RHS, Stmt *comp) { isl_pw_aff *lhs; isl_pw_aff *rhs; @@ -1166,34 +1166,42 @@ struct pet_expr *PetScan::extract_expr(Expr *expr) return NULL; } -/* Extract the initialization part of a for loop. - * The initialization is required to be an assignment. - * Return this assignment operator. +/* Check if the given initialization statement is an assignment. + * If so, return that assignment. Otherwise return NULL. */ -BinaryOperator *PetScan::extract_initialization(ForStmt *stmt) +BinaryOperator *PetScan::initialization_assignment(Stmt *init) { - Stmt *init = stmt->getInit(); BinaryOperator *ass; - if (!init) { - unsupported(stmt); + if (init->getStmtClass() != Stmt::BinaryOperatorClass) return NULL; - } - - if (init->getStmtClass() != Stmt::BinaryOperatorClass) { - unsupported(init); - return NULL; - } ass = cast(init); - if (ass->getOpcode() != BO_Assign) { - unsupported(init); + if (ass->getOpcode() != BO_Assign) return NULL; - } return ass; } +/* Check if the given initialization statement is a declaration + * of a single variable. + * If so, return that declaration. Otherwise return NULL. + */ +Decl *PetScan::initialization_declaration(Stmt *init) +{ + DeclStmt *decl; + + if (init->getStmtClass() != Stmt::DeclStmtClass) + return NULL; + + decl = cast(init); + + if (!decl->isSingleDecl()) + return NULL; + + return decl->getSingleDecl(); +} + /* Given the assignment operator in the initialization of a for loop, * extract the induction variable, i.e., the (integer)variable being * assigned. @@ -1223,6 +1231,31 @@ ValueDecl *PetScan::extract_induction_variable(BinaryOperator *init) return decl; } +/* Given the initialization statement of a for loop and the single + * declaration in this initialization statement, + * extract the induction variable, i.e., the (integer) variable being + * declared. + */ +VarDecl *PetScan::extract_induction_variable(Stmt *init, Decl *decl) +{ + VarDecl *vd; + + vd = cast(decl); + + const QualType type = vd->getType(); + if (!type->isIntegerType()) { + unsupported(init); + return NULL; + } + + if (!vd->getInit()) { + unsupported(init); + return NULL; + } + + return vd; +} + /* Check that op is of the form iv++ or iv--. * "inc" is accordingly set to 1 or -1. */ @@ -1635,6 +1668,10 @@ static __isl_give isl_map *compute_wrapping(__isl_take isl_dim *dim, * * for (i = init; condition; --i) * + * The initialization of the for loop should either be an assignment + * to an integer variable, or a declaration of such a variable with + * initialization. + * * We extract a pet_scop for the body and then embed it in a loop with * iteration domain and schedule * @@ -1679,7 +1716,10 @@ static __isl_give isl_map *compute_wrapping(__isl_take isl_dim *dim, */ struct pet_scop *PetScan::extract_for(ForStmt *stmt) { - BinaryOperator *init; + BinaryOperator *ass; + Decl *decl; + Stmt *init; + Expr *lhs, *rhs; ValueDecl *iv; isl_dim *dim; isl_set *domain; @@ -1697,12 +1737,30 @@ struct pet_scop *PetScan::extract_for(ForStmt *stmt) if (!stmt->getInit() && !stmt->getCond() && !stmt->getInc()) return extract_infinite_for(stmt); - init = PetScan::extract_initialization(stmt); - if (!init) + init = stmt->getInit(); + if (!init) { + unsupported(stmt); return NULL; - iv = extract_induction_variable(init); - if (!iv) + } + if ((ass = initialization_assignment(init)) != NULL) { + iv = extract_induction_variable(ass); + if (!iv) + return NULL; + lhs = ass->getLHS(); + rhs = ass->getRHS(); + } else if ((decl = initialization_declaration(init)) != NULL) { + VarDecl *var = extract_induction_variable(init, decl); + if (!var) + return NULL; + iv = var; + rhs = var->getInit(); + lhs = DeclRefExpr::Create(iv->getASTContext(), + var->getQualifierLoc(), iv, var->getInnerLocStart(), + var->getType(), VK_LValue); + } else { + unsupported(stmt->getInit()); return NULL; + } isl_int_init(inc); if (!check_increment(stmt, iv, inc)) { @@ -1721,9 +1779,9 @@ struct pet_scop *PetScan::extract_for(ForStmt *stmt) is_one = isl_int_is_one(inc) || isl_int_is_negone(inc); if (is_one) domain = extract_comparison(isl_int_is_pos(inc) ? BO_GE : BO_LE, - init->getLHS(), init->getRHS(), init); + lhs, rhs, init); else { - isl_pw_aff *lb = extract_affine(init->getRHS()); + isl_pw_aff *lb = extract_affine(rhs); domain = strided_domain(isl_id_copy(id), lb, inc); } diff --git a/scan.h b/scan.h index 3bf2157..915c6a9 100644 --- a/scan.h +++ b/scan.h @@ -77,8 +77,11 @@ private: struct pet_scop *extract(clang::Stmt *stmt, struct pet_expr *expr); - clang::BinaryOperator *extract_initialization(clang::ForStmt *stmt); + clang::BinaryOperator *initialization_assignment(clang::Stmt *init); + clang::Decl *initialization_declaration(clang::Stmt *init); clang::ValueDecl *extract_induction_variable(clang::BinaryOperator *stmt); + clang::VarDecl *extract_induction_variable(clang::Stmt *init, + clang::Decl *stmt); bool check_unary_increment(clang::UnaryOperator *op, clang::ValueDecl *iv, isl_int &inc); bool check_binary_increment(clang::BinaryOperator *op, @@ -138,7 +141,7 @@ private: __isl_give isl_set *extract_condition(clang::Expr *expr); __isl_give isl_set *extract_comparison(clang::BinaryOperator *expr); __isl_give isl_set *extract_comparison(clang::BinaryOperatorKind op, - clang::Expr *LHS, clang::Expr *RHS, clang::Expr *comp); + clang::Expr *LHS, clang::Expr *RHS, clang::Stmt *comp); __isl_give isl_set *extract_boolean(clang::BinaryOperator *expr); __isl_give isl_set *extract_boolean(clang::UnaryOperator *expr); diff --git a/tests/iterator_declaration.c b/tests/iterator_declaration.c new file mode 100644 index 0000000..76f6322 --- /dev/null +++ b/tests/iterator_declaration.c @@ -0,0 +1,10 @@ +void foo(int N) +{ + int i; + int a[N]; + +#pragma scop + for (int i = 0; i < N; i += 1) + a[i] = i; +#pragma endscop +} diff --git a/tests/iterator_declaration.scop b/tests/iterator_declaration.scop new file mode 100644 index 0000000..278a627 --- /dev/null +++ b/tests/iterator_declaration.scop @@ -0,0 +1,21 @@ +context: '[N] -> { [] : N >= 0 }' +arrays: +- context: '[N] -> { [] : N >= 0 }' + extent: '[N] -> { a[i0] : i0 >= 0 and i0 <= -1 + N }' + element_type: int +statements: +- line: 8 + domain: '[N] -> { S_0[i] : i >= 0 and i <= -1 + N }' + schedule: '[N] -> { S_0[i] -> [0, i] }' + body: + type: binary + operation: = + arguments: + - type: access + relation: '[N] -> { S_0[i] -> a[i] }' + read: 0 + write: 1 + - type: access + relation: '[N] -> { S_0[i] -> [i] }' + read: 1 + write: 0 -- 2.11.4.GIT