From patchwork Sat Jul 12 12:18:36 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Roman Gareev X-Patchwork-Id: 369301 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id A1906140115 for ; Sat, 12 Jul 2014 22:18:54 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:date:message-id:subject:from:to:cc:content-type; q=dns; s=default; b=h/K7nYYplPw/dqz28MhmFjWYbzcoxraUOQeZhqGio+j /0Wr7vWgAxEJ7wt7uMNzW5o2Bg/ElE/DsR1pxkWm6xrlcVy9w/NkPnRw2+Agi5G5 jH7WJ+coeU/2LsN6WNOnOhgTH3gAWYXM9tTXVgP1hv9zKrosQxykKv+V/jW+LIw8 = DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :mime-version:date:message-id:subject:from:to:cc:content-type; s=default; bh=TXfCVGmBgMdYh8MnNczzbrSF2Ws=; b=c0xFkzEsLLD6dmqw5 EHXq9ftZCV8d89rqq9tMXar1+Qvltx7BBuV/ENASHqHokgdY23qUGHOnjlGsSf+q bUmjyq4atiyuy9MumuYnWKj4O7JNafR3k6gSY9mvfguZgUATIUpLYw/Hre3XbVvn l00vOktb2e0bmG7V6TnZHUx4U8= Received: (qmail 3628 invoked by alias); 12 Jul 2014 12:18:45 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 3614 invoked by uid 89); 12 Jul 2014 12:18:44 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.6 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW, SPF_PASS autolearn=ham version=3.3.2 X-HELO: mail-pa0-f52.google.com Received: from mail-pa0-f52.google.com (HELO mail-pa0-f52.google.com) (209.85.220.52) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-SHA encrypted) ESMTPS; Sat, 12 Jul 2014 12:18:38 +0000 Received: by mail-pa0-f52.google.com with SMTP id eu11so2872848pac.25 for ; Sat, 12 Jul 2014 05:18:37 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.68.65.101 with SMTP id w5mr4923667pbs.5.1405167516864; Sat, 12 Jul 2014 05:18:36 -0700 (PDT) Received: by 10.70.128.74 with HTTP; Sat, 12 Jul 2014 05:18:36 -0700 (PDT) Date: Sat, 12 Jul 2014 18:18:36 +0600 Message-ID: Subject: [GSoC] generation of Gimple code from isl_ast_node_user From: Roman Gareev To: Tobias Grosser Cc: Mircea Namolaru , gcc-patches@gcc.gnu.org I've attached the patch, which contains generation of Gimple code from isl_ast_node_user. I think that it would be better to add motivation for the following line from the original source: if (GBB_BB (gbb) == ENTRY_BLOCK_PTR_FOR_FN (cfun)) { isl_ast_expr_free (user_expr); return next_e; } Do you know anything about this? --- Cheers, Roman Gareev. 2014-07-12 Roman Gareev gcc/ * graphite-isl-ast-to-gimple.c: Add inclusion of gimple-ssa.h, tree-into-ssa.h. (ivs_params_clear): Pass ivs_params_p ip instead of ivs_params &ip. (gcc_expression_from_isl_expression): Likewise. (gcc_expression_from_isl_ast_expr_id): Likewise. (binary_op_to_tree): Likewise. (ternary_op_to_tree): Likewise. (unary_op_to_tree): Likewise. (nary_op_to_tree): Likewise. (gcc_expression_from_isl_expr_op): Likewise. (graphite_create_new_loop): Likewise. (translate_isl_ast_for_loop): Pass ivs_params_p ip instead of ivs_params &ip. Add passing of bb_pbb_htab_type *bb_pbb_mapping. (translate_isl_ast_node_for): Likewise. (build_iv_mapping): New function. (mark_bb_with_pbb): Likewise. (translate_isl_ast_node_user): Likewise. (translate_isl_ast): Pass ivs_params_p ip instead of ivs_params &ip. Add passing of bb_pbb_htab_type *bb_pbb_mapping. (add_parameters_to_ivs_params): Pass ivs_params_p ip instead of ivs_params &ip. (scop_to_isl_ast): Likewise. (graphite_regenerate_ast_isl): Add passing of bb_pbb_htab_type *bb_pbb_mapping. * graphite-isl-ast-to-gimple.h: Add inclusion of the graphite-htab.h. * graphite.c (graphite_transform_loops): Add passing of &bb_pbb_mapping to graphite_regenerate_ast_isl. Index: gcc/graphite-isl-ast-to-gimple.c =================================================================== --- gcc/graphite-isl-ast-to-gimple.c (revision 212455) +++ gcc/graphite-isl-ast-to-gimple.c (working copy) @@ -51,11 +51,14 @@ #include "sese.h" #include "tree-ssa-loop-manip.h" #include "tree-scalar-evolution.h" +#include "gimple-ssa.h" +#include "tree-into-ssa.h" #include #ifdef HAVE_cloog #include "graphite-poly.h" #include "graphite-isl-ast-to-gimple.h" +#include "graphite-htab.h" /* This flag is set when an error occurred during the translation of ISL AST to Gimple. */ @@ -94,18 +97,21 @@ #endif } -/* IVS_PARAMS maps ISL's scattering and parameter identifiers +/* TREE_FROM_ISL_ID maps ISL's scattering and parameter identifiers to corresponding trees. */ -typedef std::map ivs_params; +typedef struct ivs_params { + std::map tree_from_isl_id; + sese region; +} *ivs_params_p; /* Free all memory allocated for ISL's identifiers. */ -void ivs_params_clear (ivs_params &ip) +void ivs_params_clear (ivs_params_p ip) { std::map::iterator it; - for (it = ip.begin (); - it != ip.end (); it++) + for (it = ip->tree_from_isl_id.begin (); + it != ip->tree_from_isl_id.end (); it++) { isl_id_free (it->first); } @@ -113,21 +119,21 @@ static tree gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *, - ivs_params &ip); + ivs_params_p ip); /* Return the tree variable that corresponds to the given isl ast identifier expression (an isl_ast_expr of type isl_ast_expr_id). */ static tree gcc_expression_from_isl_ast_expr_id (__isl_keep isl_ast_expr *expr_id, - ivs_params &ip) + ivs_params_p ip) { gcc_assert (isl_ast_expr_get_type (expr_id) == isl_ast_expr_id); isl_id *tmp_isl_id = isl_ast_expr_get_id (expr_id); std::map::iterator res; - res = ip.find (tmp_isl_id); + res = ip->tree_from_isl_id.find (tmp_isl_id); isl_id_free (tmp_isl_id); - gcc_assert (res != ip.end () && + gcc_assert (res != ip->tree_from_isl_id.end () && "Could not map isl_id to tree expression"); isl_ast_expr_free (expr_id); return res->second; @@ -158,7 +164,7 @@ type TYPE. */ static tree -binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip) +binary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params_p ip) { isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0); tree tree_lhs_expr = gcc_expression_from_isl_expression (type, arg_expr, ip); @@ -214,7 +220,7 @@ type TYPE. */ static tree -ternary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip) +ternary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params_p ip) { gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus); isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0); @@ -235,7 +241,7 @@ type TYPE. */ static tree -unary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip) +unary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params_p ip) { gcc_assert (isl_ast_expr_get_op_type (expr) == isl_ast_op_minus); isl_ast_expr *arg_expr = isl_ast_expr_get_op_arg (expr, 0); @@ -248,7 +254,7 @@ to a GCC expression tree of type TYPE. */ static tree -nary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params &ip) +nary_op_to_tree (tree type, __isl_take isl_ast_expr *expr, ivs_params_p ip) { enum tree_code op_code; switch (isl_ast_expr_get_op_type (expr)) @@ -283,7 +289,7 @@ static tree gcc_expression_from_isl_expr_op (tree type, __isl_take isl_ast_expr *expr, - ivs_params &ip) + ivs_params_p ip) { gcc_assert (isl_ast_expr_get_type (expr) == isl_ast_expr_op); switch (isl_ast_expr_get_op_type (expr)) @@ -334,7 +340,7 @@ static tree gcc_expression_from_isl_expression (tree type, __isl_take isl_ast_expr *expr, - ivs_params &ip) + ivs_params_p ip) { switch (isl_ast_expr_get_type (expr)) { @@ -365,7 +371,7 @@ static struct loop * graphite_create_new_loop (edge entry_edge, __isl_keep isl_ast_node *node_for, loop_p outer, tree type, tree lb, tree ub, - ivs_params &ip) + ivs_params_p ip) { isl_ast_expr *for_inc = isl_ast_node_for_get_inc (node_for); tree stride = gcc_expression_from_isl_expression (type, for_inc, ip); @@ -377,14 +383,15 @@ isl_ast_expr *for_iterator = isl_ast_node_for_get_iterator (node_for); isl_id *id = isl_ast_expr_get_id (for_iterator); - ip[id] = iv; + ip->tree_from_isl_id[id] = iv; isl_ast_expr_free (for_iterator); return loop; } static edge translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node, - edge next_e, ivs_params &ip); + edge next_e, bb_pbb_htab_type *bb_pbb_mapping, + ivs_params_p ip); /* Create the loop for a isl_ast_node_for. @@ -393,8 +400,8 @@ static edge translate_isl_ast_for_loop (loop_p context_loop, __isl_keep isl_ast_node *node_for, edge next_e, - tree type, tree lb, tree ub, - ivs_params &ip) + bb_pbb_htab_type *bb_pbb_mapping, tree type, + tree lb, tree ub, ivs_params_p ip) { gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for); struct loop *loop = graphite_create_new_loop (next_e, node_for, context_loop, @@ -408,7 +415,7 @@ /* Translate the body of the loop. */ isl_ast_node *for_body = isl_ast_node_for_get_body (node_for); - next_e = translate_isl_ast (loop, for_body, to_body, ip); + next_e = translate_isl_ast (loop, for_body, to_body, bb_pbb_mapping, ip); isl_ast_node_free (for_body); redirect_edge_succ_nodup (next_e, after); set_immediate_dominator (CDI_DOMINATORS, next_e->dest, next_e->src); @@ -460,7 +467,8 @@ case isl_ast_op_lt: { // (iterator < ub) => (iterator <= ub - 1) - isl_val *one = isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1); + isl_val *one = + isl_val_int_from_si (isl_ast_expr_get_ctx (for_cond), 1); isl_ast_expr *ub = isl_ast_expr_get_op_arg (for_cond, 1); res = isl_ast_expr_sub (ub, isl_ast_expr_from_val (one)); break; @@ -488,7 +496,7 @@ static edge graphite_create_new_loop_guard (edge entry_edge, __isl_keep isl_ast_node *node_for, tree *type, - tree *lb, tree *ub, ivs_params &ip) + tree *lb, tree *ub, ivs_params_p ip) { gcc_assert (isl_ast_node_get_type (node_for) == isl_ast_node_for); tree cond_expr; @@ -528,7 +536,8 @@ static edge translate_isl_ast_node_for (loop_p context_loop, __isl_keep isl_ast_node *node, - edge next_e, ivs_params &ip) + edge next_e, bb_pbb_htab_type *bb_pbb_mapping, + ivs_params_p ip) { gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_for); tree type, lb, ub; @@ -537,16 +546,96 @@ edge true_e = get_true_edge_from_guard_bb (next_e->dest); translate_isl_ast_for_loop (context_loop, node, true_e, - type, lb, ub, ip); + bb_pbb_mapping, type, lb, ub, ip); return last_e; } +/* Inserts in iv_map a tuple (OLD_LOOP->num, NEW_NAME) for the + induction variables of the loops around GBB in SESE. */ + +static void +build_iv_mapping (vec iv_map, gimple_bb_p gbb, + __isl_keep isl_ast_expr *user_expr, ivs_params_p ip) +{ + gcc_assert (isl_ast_expr_get_type (user_expr) == isl_ast_expr_op && + isl_ast_expr_get_op_type (user_expr) == isl_ast_op_call); + int i; + isl_ast_expr *arg_expr; + for (i = 1; i < isl_ast_expr_get_op_n_arg (user_expr); i++) + { + arg_expr = isl_ast_expr_get_op_arg (user_expr, i); + tree type = *graphite_expression_size_type; + tree t = gcc_expression_from_isl_expression (type, arg_expr, ip); + loop_p old_loop = gbb_loop_at_index (gbb, ip->region, i - 1); + iv_map[old_loop->num] = t; + } + +} + +/* Mark BB with it's relevant PBB via hashing table BB_PBB_MAPPING. */ + +static void +mark_bb_with_pbb (poly_bb_p pbb, basic_block bb, + bb_pbb_htab_type *bb_pbb_mapping) +{ + bool existed; + poly_bb_p &e = bb_pbb_mapping->get_or_insert (bb, &existed); + if (!existed) + e = pbb; +} + +/* Translates an isl_ast_node_user to Gimple. */ + +static edge +translate_isl_ast_node_user (__isl_keep isl_ast_node *node, + edge next_e, bb_pbb_htab_type *bb_pbb_mapping, + ivs_params_p ip) +{ + gcc_assert (isl_ast_node_get_type (node) == isl_ast_node_user); + int i, nb_loops; + basic_block new_bb; + isl_ast_expr *user_expr = isl_ast_node_user_get_expr (node); + isl_ast_expr *name_expr = isl_ast_expr_get_op_arg (user_expr, 0); + gcc_assert (isl_ast_expr_get_type (name_expr) == isl_ast_expr_id); + isl_id *name_id = isl_ast_expr_get_id (name_expr); + poly_bb_p pbb = (poly_bb_p) isl_id_get_user (name_id); + gcc_assert (pbb); + gimple_bb_p gbb = PBB_BLACK_BOX (pbb); + vec iv_map; + isl_ast_expr_free (name_expr); + isl_id_free (name_id); + + if (GBB_BB (gbb) == ENTRY_BLOCK_PTR_FOR_FN (cfun)) + { + isl_ast_expr_free (user_expr); + return next_e; + } + + nb_loops = number_of_loops (cfun); + iv_map.create (nb_loops); + for (i = 0; i < nb_loops; i++) + iv_map.quick_push (NULL_TREE); + + build_iv_mapping (iv_map, gbb, user_expr, ip); + isl_ast_expr_free (user_expr); + next_e = copy_bb_and_scalar_dependences (GBB_BB (gbb), ip->region, + next_e, iv_map, + &graphite_regenerate_error); + iv_map.release (); + new_bb = next_e->src; + mark_bb_with_pbb (pbb, new_bb, bb_pbb_mapping); + mark_virtual_operands_for_renaming (cfun); + update_ssa (TODO_update_ssa); + return next_e; +} + /* Translates an ISL AST node NODE to GCC representation in the context of a SESE. */ static edge translate_isl_ast (loop_p context_loop, __isl_keep isl_ast_node *node, - edge next_e, ivs_params &ip) + edge next_e, bb_pbb_htab_type *bb_pbb_mapping, + ivs_params_p ip) { switch (isl_ast_node_get_type (node)) { @@ -555,13 +644,13 @@ case isl_ast_node_for: return translate_isl_ast_node_for (context_loop, node, - next_e, ip); + next_e, bb_pbb_mapping, ip); case isl_ast_node_if: return next_e; case isl_ast_node_user: - return next_e; + return translate_isl_ast_node_user (node, next_e, bb_pbb_mapping, ip); case isl_ast_node_block: return next_e; @@ -587,7 +676,7 @@ /* Add ISL's parameter identifiers and corresponding.trees to ivs_params */ static void -add_parameters_to_ivs_params (scop_p scop, ivs_params &ip) +add_parameters_to_ivs_params (scop_p scop, ivs_params_p ip) { sese region = SCOP_REGION (scop); unsigned nb_parameters = isl_set_dim (scop->context, isl_dim_param); @@ -596,7 +685,7 @@ for (i = 0; i < nb_parameters; i++) { isl_id *tmp_id = isl_set_get_dim_id (scop->context, isl_dim_param, i); - ip[tmp_id] = SESE_PARAMS (region)[i]; + ip->tree_from_isl_id[tmp_id] = SESE_PARAMS (region)[i]; } } @@ -639,7 +728,7 @@ } static __isl_give isl_ast_node * -scop_to_isl_ast (scop_p scop, ivs_params &ip) +scop_to_isl_ast (scop_p scop, ivs_params_p ip) { /* Generate loop upper bounds that consist of the current loop iterator, an operator (< or <=) and an expression not involving the iterator. @@ -663,17 +752,18 @@ with ISL ASTs. Generation of GIMPLE code has to be completed. */ bool -graphite_regenerate_ast_isl (scop_p scop) +graphite_regenerate_ast_isl (scop_p scop, bb_pbb_htab_type *bb_pbb_mapping) { loop_p context_loop; sese region = SCOP_REGION (scop); ifsese if_region = NULL; isl_ast_node *root_node; - ivs_params ip; + struct ivs_params ip; + ip.region = region; timevar_push (TV_GRAPHITE_CODE_GEN); graphite_regenerate_error = false; - root_node = scop_to_isl_ast (scop, ip); + root_node = scop_to_isl_ast (scop, &ip); if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -696,7 +786,7 @@ context_loop = SESE_ENTRY (region)->src->loop_father; translate_isl_ast (context_loop, root_node, if_region->true_region->entry, - ip); + bb_pbb_mapping, &ip); graphite_verify (); scev_reset (); recompute_all_dominators (); @@ -709,7 +799,7 @@ free (if_region->region); free (if_region); - ivs_params_clear (ip); + ivs_params_clear (&ip); isl_ast_node_free (root_node); timevar_pop (TV_GRAPHITE_CODE_GEN); /* TODO: Add dump */ Index: gcc/graphite-isl-ast-to-gimple.h =================================================================== --- gcc/graphite-isl-ast-to-gimple.h (revision 212454) +++ gcc/graphite-isl-ast-to-gimple.h (working copy) @@ -21,6 +21,8 @@ #ifndef GCC_GRAPHITE_ISL_AST_TO_GIMPLE_H #define GCC_GRAPHITE_ISL_AST_TO_GIMPLE_H -extern bool graphite_regenerate_ast_isl (scop_p); +#include "graphite-htab.h" +extern bool graphite_regenerate_ast_isl (scop_p, bb_pbb_htab_type *); + #endif Index: gcc/graphite.c =================================================================== --- gcc/graphite.c (revision 212454) +++ gcc/graphite.c (working copy) @@ -301,7 +301,7 @@ if (POLY_SCOP_P (scop) && apply_poly_transforms (scop) && (((flag_graphite_code_gen == FGRAPHITE_CODE_GEN_ISL) - && graphite_regenerate_ast_isl (scop)) + && graphite_regenerate_ast_isl (scop, &bb_pbb_mapping)) || ((flag_graphite_code_gen == FGRAPHITE_CODE_GEN_CLOOG) && graphite_regenerate_ast_cloog (scop, &bb_pbb_mapping)))) need_cfg_cleanup_p = true;