From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 123404 invoked by alias); 25 Jan 2016 22:09:45 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 122715 invoked by uid 89); 25 Jan 2016 22:09:44 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=0.2 required=5.0 tests=AWL,BAYES_50,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,SPF_PASS,UNSUBSCRIBE_BODY autolearn=no version=3.3.2 spammy=USER, Static, Map, *prefix X-HELO: mail-ob0-f195.google.com Received: from mail-ob0-f195.google.com (HELO mail-ob0-f195.google.com) (209.85.214.195) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Mon, 25 Jan 2016 22:08:41 +0000 Received: by mail-ob0-f195.google.com with SMTP id x5so10318932obg.1 for ; Mon, 25 Jan 2016 14:08:41 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:sender:from:to:cc:subject:date:message-id :in-reply-to:references; bh=nuQWxgN4nL2XCAlsks/yZMnB7AV4JAsUF/8lcZ75U+I=; b=Jafp9zZA/mh79DNrFqtbhJ8rPJlyU7XkR45lTzeE1zBxV3j1hh6P6NN3Do+oGJvMBE Syy4WqBP14pL/zFoe49uEaoj0aMUJy6If0ldEZE3iNpuarjAFYutVzYx/Ah73bELOIJk bp20MKqqgb2AQklP4hpad49ho2qdeadO78+m6uxi1utF6+yFmtXpv8FVVMhmf0NMy87l Uwnt+aISBrS3q5nDhMN8ynsVWdnixIHrINpnHFxErQoofD0yBfzX7GQljt6HNpjdbEka PYjtrgfLtXVyoSIlyXxtBczHCZHs9YHGwcWOBWFNI42pQm5KqwrjUXQGHc/Qf1WZxt3p ZBfQ== X-Gm-Message-State: AG10YOQe0T5quutt+vhYWE4ytxJYAbI+xJfxuMISwgOby9uU5mFRLOJ9TegTC6flfZ+FuA== X-Received: by 10.182.125.129 with SMTP id mq1mr15076176obb.7.1453759719446; Mon, 25 Jan 2016 14:08:39 -0800 (PST) Received: from bo.sarc.sas (65-36-6-125.static.grandenetworks.net. [65.36.6.125]) by smtp.gmail.com with ESMTPSA id f8sm8558018obs.3.2016.01.25.14.08.38 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Mon, 25 Jan 2016 14:08:38 -0800 (PST) From: Sebastian Pop X-Google-Original-From: Sebastian Pop To: gcc-patches@gcc.gnu.org Cc: hiraditya@msn.com, sebpop@gmail.com, richard.guenther@gmail.com Subject: [PATCH 3/3] new scop schedule for isl-0.15 Date: Mon, 25 Jan 2016 22:09:00 -0000 Message-Id: <1453759715-23784-3-git-send-email-sebpop@gmail.com> In-Reply-To: <1453759715-23784-1-git-send-email-sebpop@gmail.com> References: <1453759715-23784-1-git-send-email-sebpop@gmail.com> X-SW-Source: 2016-01/txt/msg01930.txt.bz2 Keep unchanged the implementation for isl-0.14. * graphite-poly.c (apply_poly_transforms): Simplify. (print_isl_set): Use more readable format: ISL_YAML_STYLE_BLOCK. (print_isl_map): Same. (print_isl_union_map): Same. (print_isl_schedule): New. (debug_isl_schedule): New. * graphite-dependences.c (scop_get_reads): Do not call isl_union_map_add_map that is undocumented isl functionality. (scop_get_must_writes): Same. (scop_get_may_writes): Same. (scop_get_original_schedule): Remove. (scop_get_dependences): Do not call isl_union_map_compute_flow that is deprecated in isl 0.15. Instead, use isl_union_access_* interface. (compute_deps): Remove. * graphite-isl-ast-to-gimple.c (print_schedule_ast): New. (debug_schedule_ast): New. (translate_isl_ast_to_gimple::scop_to_isl_ast): Call set_separate_option. (graphite_regenerate_ast_isl): Add dump. (translate_isl_ast_to_gimple::scop_to_isl_ast): Generate code from scop->transformed_schedule. (graphite_regenerate_ast_isl): Add more dump. * graphite-optimize-isl.c (optimize_isl): Set scop->transformed_schedule. Check whether schedules are equal. (apply_poly_transforms): Move here. * graphite-poly.c (apply_poly_transforms): ... from here. (free_poly_bb): Static. (free_scop): Static. (pbb_number_of_iterations_at_time): Remove. (print_isl_ast): New. (debug_isl_ast): New. (debug_scop_pbb): New. * graphite-scop-detection.c (print_edge): Move. (print_sese): Move. * graphite-sese-to-poly.c (build_pbb_scattering_polyhedrons): Remove. (build_scop_scattering): Remove. (create_pw_aff_from_tree): Assert instead of bailing out. (add_condition_to_pbb): Remove unused code, do not fail. (add_conditions_to_domain): Same. (add_conditions_to_constraints): Remove. (build_scop_context): New. (add_iter_domain_dimension): New. (build_iteration_domains): Initialize pbb->iterators. Call add_conditions_to_domain. (nested_in): New. (loop_at): New. (index_outermost_in_loop): New. (index_pbb_in_loop): New. (outermost_pbb_in): New. (add_in_sequence): New. (add_outer_projection): New. (outer_projection_mupa): New. (add_loop_schedule): New. (build_schedule_pbb): New. (build_schedule_loop): New. (embed_in_surrounding_loops): New. (build_schedule_loop_nest): New. (build_original_schedule): New. (build_poly_scop): Call build_original_schedule. * graphite.h: Declare print_isl_schedule and debug_isl_schedule. (free_poly_dr): Remove. (struct poly_bb): Add iterators. Remove schedule, transformed, saved. (free_poly_bb): Remove. (debug_loop_vec): Remove. (print_isl_ast): Declare. (debug_isl_ast): Declare. (scop_do_interchange): Remove. (scop_do_strip_mine): Remove. (scop_do_block): Remove. (flatten_all_loops): Remove. (optimize_isl): Remove. (pbb_number_of_iterations_at_time): Remove. (debug_scop_pbb): Declare. (print_schedule_ast): Declare. (debug_schedule_ast): Declare. (struct scop): Remove schedule. Add original_schedule, transformed_schedule. (free_gimple_poly_bb): Remove. (print_generated_program): Remove. (debug_generated_program): Remove. (unify_scattering_dimensions): Remove. * sese.c (print_edge): ... here. (print_sese): ... here. (debug_edge): ... here. (debug_sese): ... here. * sese.h (print_edge): Declare. (print_sese): Declare. (dump_edge): Declare. (dump_sese): Declare. --- gcc/graphite-dependences.c | 123 ++++++- gcc/graphite-isl-ast-to-gimple.c | 203 +++++++----- gcc/graphite-optimize-isl.c | 177 +++++++--- gcc/graphite-poly.c | 154 +++++---- gcc/graphite-scop-detection.c | 15 - gcc/graphite-sese-to-poly.c | 365 ++++++++++++++++++--- gcc/graphite.h | 48 +-- gcc/sese.c | 34 ++ gcc/sese.h | 7 +- gcc/testsuite/gcc.dg/graphite/pr35356-1.c | 2 +- .../gfortran.dg/graphite/interchange-3.f90 | 2 +- 11 files changed, 836 insertions(+), 294 deletions(-) diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c index 0544700..f9d5bc3 100644 --- a/gcc/graphite-dependences.c +++ b/gcc/graphite-dependences.c @@ -66,7 +66,7 @@ add_pdr_constraints (poly_dr_p pdr, poly_bb_p pbb) /* Returns all the memory reads in SCOP. */ static isl_union_map * -scop_get_reads (scop_p scop, vec pbbs) +scop_get_reads (scop_p scop) { int i, j; poly_bb_p pbb; @@ -74,7 +74,7 @@ scop_get_reads (scop_p scop, vec pbbs) isl_space *space = isl_set_get_space (scop->param_context); isl_union_map *res = isl_union_map_empty (space); - FOR_EACH_VEC_ELT (pbbs, i, pbb) + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) { FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr) if (pdr_read_p (pdr)) @@ -84,7 +84,9 @@ scop_get_reads (scop_p scop, vec pbbs) fprintf (dump_file, "Adding read to depedence graph: "); print_pdr (dump_file, pdr); } - res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb)); + isl_union_map *um + = isl_union_map_from_map (add_pdr_constraints (pdr, pbb)); + res = isl_union_map_union (res, um); if (dump_file) { fprintf (dump_file, "Reads depedence graph: "); @@ -99,7 +101,7 @@ scop_get_reads (scop_p scop, vec pbbs) /* Returns all the memory must writes in SCOP. */ static isl_union_map * -scop_get_must_writes (scop_p scop, vec pbbs) +scop_get_must_writes (scop_p scop) { int i, j; poly_bb_p pbb; @@ -107,7 +109,7 @@ scop_get_must_writes (scop_p scop, vec pbbs) isl_space *space = isl_set_get_space (scop->param_context); isl_union_map *res = isl_union_map_empty (space); - FOR_EACH_VEC_ELT (pbbs, i, pbb) + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) { FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr) if (pdr_write_p (pdr)) @@ -117,7 +119,9 @@ scop_get_must_writes (scop_p scop, vec pbbs) fprintf (dump_file, "Adding must write to depedence graph: "); print_pdr (dump_file, pdr); } - res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb)); + isl_union_map *um + = isl_union_map_from_map (add_pdr_constraints (pdr, pbb)); + res = isl_union_map_union (res, um); if (dump_file) { fprintf (dump_file, "Must writes depedence graph: "); @@ -132,7 +136,7 @@ scop_get_must_writes (scop_p scop, vec pbbs) /* Returns all the memory may writes in SCOP. */ static isl_union_map * -scop_get_may_writes (scop_p scop, vec pbbs) +scop_get_may_writes (scop_p scop) { int i, j; poly_bb_p pbb; @@ -140,7 +144,7 @@ scop_get_may_writes (scop_p scop, vec pbbs) isl_space *space = isl_set_get_space (scop->param_context); isl_union_map *res = isl_union_map_empty (space); - FOR_EACH_VEC_ELT (pbbs, i, pbb) + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) { FOR_EACH_VEC_ELT (PBB_DRS (pbb), j, pdr) if (pdr_may_write_p (pdr)) @@ -150,7 +154,9 @@ scop_get_may_writes (scop_p scop, vec pbbs) fprintf (dump_file, "Adding may write to depedence graph: "); print_pdr (dump_file, pdr); } - res = isl_union_map_add_map (res, add_pdr_constraints (pdr, pbb)); + isl_union_map *um + = isl_union_map_from_map (add_pdr_constraints (pdr, pbb)); + res = isl_union_map_union (res, um); if (dump_file) { fprintf (dump_file, "May writes depedence graph: "); @@ -162,6 +168,7 @@ scop_get_may_writes (scop_p scop, vec pbbs) return isl_union_map_coalesce (res); } +#ifndef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS /* Returns all the original schedules in SCOP. */ static isl_union_map * @@ -181,6 +188,7 @@ scop_get_original_schedule (scop_p scop, vec pbbs) return isl_union_map_coalesce (res); } +#endif /* Helper function used on each MAP of a isl_union_map. Computes the maximal output dimension. */ @@ -303,6 +311,95 @@ carries_deps (__isl_keep isl_union_map *schedule, return res; } +#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS +/* Compute the dependence relations for the SCOP: + RAW are read after write dependences, + WAR are write after read dependences, + WAW are write after write dependences. */ + +void +scop_get_dependences (scop_p scop) +{ + if (scop->dependence) + return; + + isl_union_map *reads = scop_get_reads (scop); + isl_union_map *must_writes = scop_get_must_writes (scop); + isl_union_map *may_writes = scop_get_may_writes (scop); + + if (dump_file) + { + fprintf (dump_file, "\n--- Documentation for datarefs dump: ---\n"); + fprintf (dump_file, "Statements on the iteration domain are mapped to" + " array references.\n"); + fprintf (dump_file, " To read the following data references:\n\n"); + fprintf (dump_file, " S_5[i0] -> [106] : i0 >= 0 and i0 <= 3\n"); + fprintf (dump_file, " S_8[i0] -> [1, i0] : i0 >= 0 and i0 <= 3\n\n"); + + fprintf (dump_file, " S_5[i0] is the dynamic instance of statement" + " bb_5 in a loop that accesses all iterations 0 <= i0 <= 3.\n"); + fprintf (dump_file, " [1, i0] is a 'memref' with alias set 1" + " and first subscript access i0.\n"); + fprintf (dump_file, " [106] is a 'scalar reference' which is the sum of" + " SSA_NAME_VERSION 6" + " and --param graphite-max-arrays-per-scop=100\n"); + fprintf (dump_file, "-----------------------\n\n"); + + fprintf (dump_file, "data references (\n"); + fprintf (dump_file, " reads: "); + print_isl_union_map (dump_file, reads); + fprintf (dump_file, " must_writes: "); + print_isl_union_map (dump_file, must_writes); + fprintf (dump_file, " may_writes: "); + print_isl_union_map (dump_file, may_writes); + fprintf (dump_file, ")\n"); + } + + gcc_assert (scop->original_schedule); + + isl_union_access_info *ai; + ai = isl_union_access_info_from_sink (isl_union_map_copy (reads)); + ai = isl_union_access_info_set_must_source (ai, isl_union_map_copy (must_writes)); + ai = isl_union_access_info_set_may_source (ai, may_writes); + ai = isl_union_access_info_set_schedule + (ai, isl_schedule_copy (scop->original_schedule)); + isl_union_flow *flow = isl_union_access_info_compute_flow (ai); + isl_union_map *raw = isl_union_flow_get_must_dependence (flow); + isl_union_flow_free (flow); + + ai = isl_union_access_info_from_sink (isl_union_map_copy (must_writes)); + ai = isl_union_access_info_set_must_source (ai, must_writes); + ai = isl_union_access_info_set_may_source (ai, reads); + ai = isl_union_access_info_set_schedule + (ai, isl_schedule_copy (scop->original_schedule)); + flow = isl_union_access_info_compute_flow (ai); + + isl_union_map *waw = isl_union_flow_get_must_dependence (flow); + isl_union_map *war = isl_union_flow_get_may_dependence (flow); + war = isl_union_map_subtract (war, isl_union_map_copy (waw)); + isl_union_flow_free (flow); + + raw = isl_union_map_coalesce (raw); + waw = isl_union_map_coalesce (waw); + war = isl_union_map_coalesce (war); + + isl_union_map *dependences = raw; + dependences = isl_union_map_union (dependences, war); + dependences = isl_union_map_union (dependences, waw); + dependences = isl_union_map_coalesce (dependences); + + if (dump_file) + { + fprintf (dump_file, "data dependences (\n"); + print_isl_union_map (dump_file, dependences); + fprintf (dump_file, ")\n"); + } + + scop->dependence = dependences; +} + +#else + /* Compute the original data dependences in SCOP for all the reads and writes in PBBS. */ @@ -321,9 +418,9 @@ compute_deps (scop_p scop, vec pbbs, isl_union_map **must_waw_no_source, isl_union_map **may_waw_no_source) { - isl_union_map *reads = scop_get_reads (scop, pbbs); - isl_union_map *must_writes = scop_get_must_writes (scop, pbbs); - isl_union_map *may_writes = scop_get_may_writes (scop, pbbs); + isl_union_map *reads = scop_get_reads (scop); + isl_union_map *must_writes = scop_get_must_writes (scop); + isl_union_map *may_writes = scop_get_may_writes (scop); isl_union_map *all_writes = isl_union_map_union (isl_union_map_copy (must_writes), isl_union_map_copy (may_writes)); all_writes = isl_union_map_coalesce (all_writes); @@ -428,4 +525,6 @@ scop_get_dependences (scop_p scop) return dependences; } +#endif /* HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS */ + #endif /* HAVE_isl */ diff --git a/gcc/graphite-isl-ast-to-gimple.c b/gcc/graphite-isl-ast-to-gimple.c index 562cee0..0f58503 100644 --- a/gcc/graphite-isl-ast-to-gimple.c +++ b/gcc/graphite-isl-ast-to-gimple.c @@ -105,7 +105,7 @@ typedef std::map ivs_params; /* Free all memory allocated for isl's identifiers. */ -void ivs_params_clear (ivs_params &ip) +static void ivs_params_clear (ivs_params &ip) { std::map::iterator it; for (it = ip.begin (); @@ -119,7 +119,7 @@ void ivs_params_clear (ivs_params &ip) /* Set the "separate" option for the schedule node. */ -static __isl_give isl_schedule_node * +static isl_schedule_node * set_separate_option (__isl_take isl_schedule_node *node, void *user) { if (user) @@ -136,6 +136,27 @@ set_separate_option (__isl_take isl_schedule_node *node, void *user) return node; } + +/* Print SCHEDULE under an AST form on file F. */ + +void +print_schedule_ast (FILE *f, __isl_keep isl_schedule *schedule, scop_p scop) +{ + isl_set *set = isl_set_params (isl_set_copy (scop->param_context)); + isl_ast_build *context = isl_ast_build_from_context (set); + isl_ast_node *ast + = isl_ast_build_node_from_schedule (context, isl_schedule_copy (schedule)); + isl_ast_build_free (context); + print_isl_ast (f, ast); + isl_ast_node_free (ast); +} + +DEBUG_FUNCTION void +debug_schedule_ast (__isl_keep isl_schedule *s, scop_p scop) +{ + print_schedule_ast (stderr, s, scop); +} + #endif enum phi_node_kind @@ -288,48 +309,50 @@ class translate_isl_ast_to_gimple void add_parameters_to_ivs_params (scop_p scop, ivs_params &ip); - /* Get the maximal number of schedule dimensions in the scop SCOP. */ - - int get_max_schedule_dimensions (scop_p scop); - /* Generates a build, which specifies the constraints on the parameters. */ __isl_give isl_ast_build *generate_isl_context (scop_p scop); +#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS + /* Generate isl AST from schedule of SCOP. */ + __isl_give isl_ast_node * scop_to_isl_ast (scop_p scop); +#else + /* Get the maximal number of schedule dimensions in the scop SCOP. */ + int get_max_schedule_dimensions (scop_p scop); + /* Extend the schedule to NB_SCHEDULE_DIMS schedule dimensions. For schedules with different dimensionality, the isl AST generator can not define an order and will just randomly choose an order. The solution to this problem is to extend all schedules to the maximal number of schedule dimensions (using '0's for the remaining values). */ - __isl_give isl_map *extend_schedule (__isl_take isl_map *schedule, int nb_schedule_dims); /* Generates a schedule, which specifies an order used to visit elements in a domain. */ - __isl_give isl_union_map *generate_isl_schedule (scop_p scop); -#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS - /* Set the "separate" option for all schedules. This helps reducing control - overhead. */ - - __isl_give isl_schedule * - set_options_for_schedule_tree (__isl_take isl_schedule *schedule); -#endif - /* Set the separate option for all dimensions. This helps to reduce control overhead. */ - - __isl_give isl_ast_build * set_options (__isl_take isl_ast_build *control, - __isl_keep isl_union_map *schedule); + __isl_give isl_ast_build *set_options (__isl_take isl_ast_build *control, + __isl_keep isl_union_map *schedule); /* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in IP. */ + __isl_give isl_ast_node *scop_to_isl_ast (scop_p scop, ivs_params &ip); - __isl_give isl_ast_node * scop_to_isl_ast (scop_p scop, ivs_params &ip); - + /* Prints NODE to FILE. */ + void print_isl_ast_node (FILE *file, __isl_keep isl_ast_node *node, + __isl_keep isl_ctx *ctx) const + { + isl_printer *prn = isl_printer_to_file (ctx, file); + prn = isl_printer_set_output_format (prn, ISL_FORMAT_C); + prn = isl_printer_print_ast_node (prn, node); + prn = isl_printer_print_str (prn, "\n"); + isl_printer_free (prn); + } +#endif /* Return true if RENAME (defined in BB) is a valid use in NEW_BB. The definition should flow into use, and the use should respect the loop-closed @@ -485,11 +508,6 @@ class translate_isl_ast_to_gimple bool codegen_error_p () const { return codegen_error; } - /* Prints NODE to FILE. */ - - void print_isl_ast_node (FILE *file, __isl_keep isl_ast_node *node, - __isl_keep isl_ctx *ctx) const; - /* Return true when OP is a constant tree. */ bool is_constant (tree op) const @@ -1389,7 +1407,7 @@ is_valid_rename (tree rename, basic_block def_bb, basic_block use_bb, { if (dump_file) { - fprintf (dump_file, "[codegen] rename not in loop closed ssa:"); + fprintf (dump_file, "[codegen] rename not in loop closed ssa: "); print_generic_expr (dump_file, rename, 0); fprintf (dump_file, "\n"); } @@ -3110,20 +3128,6 @@ translate_isl_ast_to_gimple::translate_pending_phi_nodes () } } -/* Prints NODE to FILE. */ - -void -translate_isl_ast_to_gimple::print_isl_ast_node (FILE *file, - __isl_keep isl_ast_node *node, - __isl_keep isl_ctx *ctx) const -{ - isl_printer *prn = isl_printer_to_file (ctx, file); - prn = isl_printer_set_output_format (prn, ISL_FORMAT_C); - prn = isl_printer_print_ast_node (prn, node); - prn = isl_printer_print_str (prn, "\n"); - isl_printer_free (prn); -} - /* Add isl's parameter identifiers and corresponding trees to ivs_params. */ void @@ -3152,6 +3156,52 @@ translate_isl_ast_to_gimple::generate_isl_context (scop_p scop) return isl_ast_build_from_context (context_isl); } +/* This method is executed before the construction of a for node. */ +__isl_give isl_id * +ast_build_before_for (__isl_keep isl_ast_build *build, void *user) +{ + isl_union_map *dependences = (isl_union_map *) user; + ast_build_info *for_info = XNEW (struct ast_build_info); + isl_union_map *schedule = isl_ast_build_get_schedule (build); + isl_space *schedule_space = isl_ast_build_get_schedule_space (build); + int dimension = isl_space_dim (schedule_space, isl_dim_out); + for_info->is_parallelizable = + !carries_deps (schedule, dependences, dimension); + isl_union_map_free (schedule); + isl_space_free (schedule_space); + isl_id *id = isl_id_alloc (isl_ast_build_get_ctx (build), "", for_info); + return id; +} + +#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS + +/* Generate isl AST from schedule of SCOP. */ + +__isl_give isl_ast_node * +translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop) +{ + gcc_assert (scop->transformed_schedule); + + /* Set the separate option to reduce control flow overhead. */ + isl_schedule *schedule = isl_schedule_map_schedule_node_bottom_up + (isl_schedule_copy (scop->transformed_schedule), set_separate_option, NULL); + isl_ast_build *context_isl = generate_isl_context (scop); + + if (flag_loop_parallelize_all) + { + scop_get_dependences (scop); + context_isl = + isl_ast_build_set_before_each_for (context_isl, ast_build_before_for, + scop->dependence); + } + + isl_ast_node *ast_isl = isl_ast_build_node_from_schedule + (context_isl, schedule); + isl_ast_build_free (context_isl); + return ast_isl; +} + +#else /* Get the maximal number of schedule dimensions in the scop SCOP. */ int @@ -3229,36 +3279,6 @@ translate_isl_ast_to_gimple::generate_isl_schedule (scop_p scop) return schedule_isl; } -/* This method is executed before the construction of a for node. */ -__isl_give isl_id * -ast_build_before_for (__isl_keep isl_ast_build *build, void *user) -{ - isl_union_map *dependences = (isl_union_map *) user; - ast_build_info *for_info = XNEW (struct ast_build_info); - isl_union_map *schedule = isl_ast_build_get_schedule (build); - isl_space *schedule_space = isl_ast_build_get_schedule_space (build); - int dimension = isl_space_dim (schedule_space, isl_dim_out); - for_info->is_parallelizable = - !carries_deps (schedule, dependences, dimension); - isl_union_map_free (schedule); - isl_space_free (schedule_space); - isl_id *id = isl_id_alloc (isl_ast_build_get_ctx (build), "", for_info); - return id; -} - -#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS -/* Set the separate option for all schedules. This helps reducing control - overhead. */ - -__isl_give isl_schedule * -translate_isl_ast_to_gimple::set_options_for_schedule_tree -(__isl_take isl_schedule *schedule) -{ - return isl_schedule_map_schedule_node_bottom_up - (schedule, set_separate_option, NULL); -} -#endif - /* Set the separate option for all dimensions. This helps to reduce control overhead. */ @@ -3283,7 +3303,6 @@ translate_isl_ast_to_gimple::set_options (__isl_take isl_ast_build *control, __isl_give isl_ast_node * translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop, ivs_params &ip) { - isl_ast_node *ast_isl = NULL; /* Generate loop upper bounds that consist of the current loop iterator, an operator (< or <=) and an expression not involving the iterator. If this option is not set, then the current loop iterator may appear several times @@ -3302,23 +3321,18 @@ translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop, ivs_params &ip) dependence); } -#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS + isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl, + schedule_isl); if (scop->schedule) { - scop->schedule = set_options_for_schedule_tree (scop->schedule); - ast_isl = isl_ast_build_node_from_schedule (context_isl, scop->schedule); - isl_union_map_free(schedule_isl); + isl_schedule_free (scop->schedule); + scop->schedule = NULL; } - else - ast_isl = isl_ast_build_ast_from_schedule (context_isl, schedule_isl); -#else - ast_isl = isl_ast_build_ast_from_schedule (context_isl, schedule_isl); - isl_schedule_free (scop->schedule); -#endif isl_ast_build_free (context_isl); return ast_isl; } +#endif /* Copy def from sese REGION to the newly created TO_REGION. TR is defined by DEF_STMT. GSI points to entry basic block of the TO_REGION. */ @@ -3401,12 +3415,26 @@ graphite_regenerate_ast_isl (scop_p scop) ivs_params ip; timevar_push (TV_GRAPHITE_CODE_GEN); +#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS + t.add_parameters_to_ivs_params (scop, ip); + root_node = t.scop_to_isl_ast (scop); +#else root_node = t.scop_to_isl_ast (scop, ip); +#endif if (dump_file && (dump_flags & TDF_DETAILS)) { - fprintf (dump_file, "AST generated by isl: \n"); - t.print_isl_ast_node (dump_file, root_node, scop->isl_context); +#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS + fprintf (dump_file, "[scheduler] original schedule:\n"); + print_isl_schedule (dump_file, scop->original_schedule); + fprintf (dump_file, "[scheduler] isl transformed schedule:\n"); + print_isl_schedule (dump_file, scop->transformed_schedule); + + fprintf (dump_file, "[scheduler] original ast:\n"); + print_schedule_ast (dump_file, scop->original_schedule, scop); +#endif + fprintf (dump_file, "[scheduler] AST generated by isl:\n"); + print_isl_ast (dump_file, root_node); } recompute_all_dominators (); @@ -3431,8 +3459,8 @@ graphite_regenerate_ast_isl (scop_p scop) if (t.codegen_error_p ()) { if (dump_file) - fprintf (dump_file, "[codegen] unsuccessful," - " reverting back to the original code.\n"); + fprintf (dump_file, "codegen error: " + "reverting back to the original code.\n"); set_ifsese_condition (if_region, integer_zero_node); } else @@ -3452,6 +3480,9 @@ graphite_regenerate_ast_isl (scop_p scop) scev_reset (); recompute_all_dominators (); graphite_verify (); + + if (dump_file) + fprintf (dump_file, "[codegen] isl AST to Gimple succeeded.\n"); } else { diff --git a/gcc/graphite-optimize-isl.c b/gcc/graphite-optimize-isl.c index fe8a71a..d1620d5 100644 --- a/gcc/graphite-optimize-isl.c +++ b/gcc/graphite-optimize-isl.c @@ -92,24 +92,120 @@ get_schedule_for_node_st (__isl_take isl_schedule_node *node, void *user) return node; } -/* get_schedule_map_st - Improve the schedule by performing other loop - optimizations. _st ending is for schedule tree version of this - function (see get_schedule_map below for the band forest version). +static isl_union_set * +scop_get_domains (scop_p scop) +{ + int i; + poly_bb_p pbb; + isl_space *space = isl_set_get_space (scop->param_context); + isl_union_set *res = isl_union_set_empty (space); - Do a depth-first post-order traversal of the nodes in a schedule - tree and apply get_schedule_for_node_st on them to improve the schedule. - */ + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) + res = isl_union_set_add_set (res, isl_set_copy (pbb->domain)); + + return res; +} + +/* Compute the schedule for SCOP based on its parameters, domain and set of + constraints. Then apply the schedule to SCOP. */ -static __isl_give isl_union_map * -get_schedule_map_st (__isl_keep isl_schedule *schedule) +static bool +optimize_isl (scop_p scop) { + int old_max_operations = isl_ctx_get_max_operations (scop->isl_context); + int max_operations = PARAM_VALUE (PARAM_MAX_ISL_OPERATIONS); + if (max_operations) + isl_ctx_set_max_operations (scop->isl_context, max_operations); + isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_CONTINUE); - schedule = isl_schedule_map_schedule_node_bottom_up (schedule, - get_schedule_for_node_st, - NULL); - isl_union_map *schedule_map = isl_schedule_get_map (schedule); - return schedule_map; + isl_union_set *domain = scop_get_domains (scop); + + /* Simplify the dependences on the domain. */ + scop_get_dependences (scop); + isl_union_map *dependences + = isl_union_map_gist_domain (isl_union_map_copy (scop->dependence), + isl_union_set_copy (domain)); + isl_union_map *validity + = isl_union_map_gist_range (dependences, isl_union_set_copy (domain)); + + /* FIXME: proximity should not be validity. */ + isl_union_map *proximity = isl_union_map_copy (validity); + + isl_schedule_constraints *sc = isl_schedule_constraints_on_domain (domain); + sc = isl_schedule_constraints_set_proximity (sc, proximity); + sc = isl_schedule_constraints_set_validity (sc, isl_union_map_copy (validity)); + sc = isl_schedule_constraints_set_coincidence (sc, validity); + + isl_options_set_schedule_serialize_sccs (scop->isl_context, 0); + isl_options_set_schedule_maximize_band_depth (scop->isl_context, 1); + isl_options_set_schedule_max_constant_term (scop->isl_context, 20); + isl_options_set_schedule_max_coefficient (scop->isl_context, 20); + isl_options_set_tile_scale_tile_loops (scop->isl_context, 0); + /* Generate loop upper bounds that consist of the current loop iterator, an + operator (< or <=) and an expression not involving the iterator. If this + option is not set, then the current loop iterator may appear several times + in the upper bound. See the isl manual for more details. */ + isl_options_set_ast_build_atomic_upper_bound (scop->isl_context, 1); + + scop->transformed_schedule = isl_schedule_constraints_compute_schedule (sc); + scop->transformed_schedule = + isl_schedule_map_schedule_node_bottom_up (scop->transformed_schedule, + get_schedule_for_node_st, NULL); + isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_ABORT); + + isl_ctx_reset_operations (scop->isl_context); + isl_ctx_set_max_operations (scop->isl_context, old_max_operations); + if (!scop->transformed_schedule + || isl_ctx_last_error (scop->isl_context) == isl_error_quota) + { + if (dump_file && dump_flags) + fprintf (dump_file, "isl timed out --param max-isl-operations=%d\n", + max_operations); + return false; + } + + gcc_assert (scop->original_schedule); + isl_union_map *original = isl_schedule_get_map (scop->original_schedule); + isl_union_map *transformed = isl_schedule_get_map (scop->transformed_schedule); + bool same_schedule = isl_union_map_is_equal (original, transformed); + isl_union_map_free (original); + isl_union_map_free (transformed); + + if (same_schedule) + { + if (dump_file) + { + fprintf (dump_file, "[scheduler] isl optimized schedule is " + "identical to the original schedule.\n"); + print_schedule_ast (dump_file, scop->original_schedule, scop); + } + isl_schedule_free (scop->transformed_schedule); + scop->transformed_schedule = isl_schedule_copy (scop->original_schedule); + return false; + } + + return true; +} + +/* Apply graphite transformations to all the basic blocks of SCOP. */ + +bool +apply_poly_transforms (scop_p scop) +{ + if (flag_loop_nest_optimize) + return optimize_isl (scop); + + if (!flag_graphite_identity && !flag_loop_parallelize_all) + return false; + + /* Generate code even if we did not apply any real transformation. + This also allows to check the performance for the identity + transformation: GIMPLE -> GRAPHITE -> GIMPLE. */ + gcc_assert (scop->original_schedule); + scop->transformed_schedule = isl_schedule_copy (scop->original_schedule); + return true; } + #else /* get_tile_map - Create a map that describes a n-dimensonal tiling. @@ -304,7 +400,6 @@ get_schedule_map (isl_schedule *schedule) isl_band_list_free (band_list); return schedule_map; } -#endif static isl_stat get_single_map (__isl_take isl_map *map, void *user) @@ -350,12 +445,10 @@ scop_get_domains (scop_p scop) return res; } -static const int CONSTANT_BOUND = 20; - /* Compute the schedule for SCOP based on its parameters, domain and set of constraints. Then apply the schedule to SCOP. */ -bool +static bool optimize_isl (scop_p scop) { int old_max_operations = isl_ctx_get_max_operations (scop->isl_context); @@ -373,24 +466,10 @@ optimize_isl (scop_p scop) isl_union_map *validity = isl_union_map_copy (scop->dependence); isl_union_map *proximity = isl_union_map_copy (validity); - isl_options_set_schedule_max_constant_term (scop->isl_context, CONSTANT_BOUND); - isl_options_set_schedule_maximize_band_depth (scop->isl_context, 1); -#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS - /* isl 0.15 or later. */ - isl_options_set_schedule_serialize_sccs (scop->isl_context, 0); - isl_options_set_schedule_maximize_band_depth (scop->isl_context, 1); - isl_options_set_schedule_max_constant_term (scop->isl_context, 20); - isl_options_set_schedule_max_coefficient (scop->isl_context, 20); - isl_options_set_tile_scale_tile_loops (scop->isl_context, 0); - isl_options_set_coalesce_bounded_wrapping (scop->isl_context, 1); - isl_options_set_ast_build_exploit_nested_bounds (scop->isl_context, 1); - isl_options_set_ast_build_atomic_upper_bound (scop->isl_context, 1); -#else isl_options_set_schedule_fuse (scop->isl_context, ISL_SCHEDULE_FUSE_MIN); -#endif - isl_schedule *schedule = isl_union_set_compute_schedule (domain, validity, proximity); + isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_ABORT); isl_ctx_reset_operations (scop->isl_context); @@ -405,20 +484,38 @@ optimize_isl (scop_p scop) return false; } - /* Attach the schedule to scop so that it can be used in code generation. - schedule freeing will occur in code generation. */ scop->schedule = schedule; -#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS - /* isl 0.15 or later. */ - isl_union_map *schedule_map = get_schedule_map_st (schedule); -#else isl_union_map *schedule_map = get_schedule_map (schedule); -#endif apply_schedule_map_to_scop (scop, schedule_map); - isl_union_map_free (schedule_map); + + if (dump_file) + { + fprintf (dump_file, "isl end schedule:\n"); + print_isl_schedule (dump_file, scop->schedule); + } + return true; } +/* Apply graphite transformations to all the basic blocks of SCOP. */ + +bool +apply_poly_transforms (scop_p scop) +{ + if (flag_loop_nest_optimize) + return optimize_isl (scop); + + if (!flag_graphite_identity && !flag_loop_parallelize_all) + return false; + + /* Generate code even if we did not apply any real transformation. + This also allows to check the performance for the identity + transformation: GIMPLE -> GRAPHITE -> GIMPLE. */ + return true; +} + +#endif /* HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS */ + #endif /* HAVE_isl */ diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c index efa39bf..4c3f550 100644 --- a/gcc/graphite-poly.c +++ b/gcc/graphite-poly.c @@ -86,28 +86,6 @@ debug_iteration_domains (scop_p scop) print_iteration_domains (stderr, scop); } -/* Apply graphite transformations to all the basic blocks of SCOP. */ - -bool -apply_poly_transforms (scop_p scop) -{ - bool transform_done = false; - - /* Generate code even if we did not apply any real transformation. - This also allows to check the performance for the identity - transformation: GIMPLE -> GRAPHITE -> GIMPLE. */ - if (flag_graphite_identity) - transform_done = true; - - if (flag_loop_parallelize_all) - transform_done = true; - - if (flag_loop_nest_optimize) - transform_done |= optimize_isl (scop); - - return transform_done; -} - /* Create a new polyhedral data reference and add it to PBB. It is defined by its ACCESSES, its TYPE, and the number of subscripts NB_SUBSCRIPTS. */ @@ -142,7 +120,7 @@ new_poly_dr (poly_bb_p pbb, gimple *stmt, enum poly_dr_type type, /* Free polyhedral data reference PDR. */ -void +static void free_poly_dr (poly_dr_p pdr) { isl_map_free (pdr->accesses); @@ -158,9 +136,13 @@ new_poly_bb (scop_p scop, gimple_poly_bb_p black_box) poly_bb_p pbb = XNEW (struct poly_bb); pbb->domain = NULL; +#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS + pbb->iterators = NULL; +#else pbb->schedule = NULL; pbb->transformed = NULL; pbb->saved = NULL; +#endif PBB_SCOP (pbb) = scop; pbb_set_black_box (pbb, black_box); PBB_DRS (pbb).create (3); @@ -171,16 +153,25 @@ new_poly_bb (scop_p scop, gimple_poly_bb_p black_box) /* Free polyhedral black box. */ -void +static void free_poly_bb (poly_bb_p pbb) { int i; poly_dr_p pdr; isl_set_free (pbb->domain); + pbb->domain = NULL; +#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS + isl_set_free (pbb->iterators); + pbb->iterators = NULL; +#else isl_map_free (pbb->schedule); + pbb->schedule = NULL; isl_map_free (pbb->transformed); + pbb->transformed = NULL; isl_map_free (pbb->saved); + pbb->saved = NULL; +#endif if (PBB_DRS (pbb).exists ()) FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr) @@ -251,7 +242,7 @@ new_gimple_poly_bb (basic_block bb, vec drs, /* Frees GBB. */ -void +static void free_gimple_poly_bb (gimple_poly_bb_p gbb) { free_data_refs (GBB_DATA_REFS (gbb)); @@ -282,7 +273,12 @@ new_scop (edge entry, edge exit) sese_info_p region = new_sese_info (entry, exit); scop_p s = XNEW (struct scop); +#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS + s->original_schedule = NULL; + s->transformed_schedule = NULL; +#else s->schedule = NULL; +#endif s->param_context = NULL; scop_set_region (s, region); s->pbbs.create (3); @@ -309,8 +305,17 @@ free_scop (scop_p scop) scop->drs.release (); isl_set_free (scop->param_context); + scop->param_context = NULL; isl_union_map_free (scop->dependence); scop->dependence = NULL; +#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS + isl_schedule_free (scop->original_schedule); + scop->original_schedule = NULL; + isl_schedule_free (scop->transformed_schedule); + scop->transformed_schedule = NULL; +#else + +#endif XDELETE (scop); } @@ -535,53 +540,61 @@ debug_scop_params (scop_p scop) extern isl_ctx *the_isl_ctx; void -print_isl_set (FILE *f, isl_set *set) +print_isl_set (FILE *f, __isl_keep isl_set *set) { isl_printer *p = isl_printer_to_file (the_isl_ctx, f); +#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS + p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK); +#endif p = isl_printer_print_set (p, set); p = isl_printer_print_str (p, "\n"); isl_printer_free (p); } DEBUG_FUNCTION void -debug_isl_set (isl_set *set) +debug_isl_set (__isl_keep isl_set *set) { print_isl_set (stderr, set); } void -print_isl_map (FILE *f, isl_map *map) +print_isl_map (FILE *f, __isl_keep isl_map *map) { isl_printer *p = isl_printer_to_file (the_isl_ctx, f); +#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS + p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK); +#endif p = isl_printer_print_map (p, map); p = isl_printer_print_str (p, "\n"); isl_printer_free (p); } DEBUG_FUNCTION void -debug_isl_map (isl_map *map) +debug_isl_map (__isl_keep isl_map *map) { print_isl_map (stderr, map); } void -print_isl_union_map (FILE *f, isl_union_map *map) +print_isl_union_map (FILE *f, __isl_keep isl_union_map *map) { isl_printer *p = isl_printer_to_file (the_isl_ctx, f); +#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS + p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK); +#endif p = isl_printer_print_union_map (p, map); p = isl_printer_print_str (p, "\n"); isl_printer_free (p); } DEBUG_FUNCTION void -debug_isl_union_map (isl_union_map *map) +debug_isl_union_map (__isl_keep isl_union_map *map) { print_isl_union_map (stderr, map); } - void -print_isl_aff (FILE *f, isl_aff *aff) +print_isl_aff (FILE *f, __isl_keep isl_aff *aff) { isl_printer *p = isl_printer_to_file (the_isl_ctx, f); p = isl_printer_print_aff (p, aff); @@ -590,13 +603,13 @@ print_isl_aff (FILE *f, isl_aff *aff) } DEBUG_FUNCTION void -debug_isl_aff (isl_aff *aff) +debug_isl_aff (__isl_keep isl_aff *aff) { print_isl_aff (stderr, aff); } void -print_isl_constraint (FILE *f, isl_constraint *c) +print_isl_constraint (FILE *f, __isl_keep isl_constraint *c) { isl_printer *p = isl_printer_to_file (the_isl_ctx, f); p = isl_printer_print_constraint (p, c); @@ -605,46 +618,49 @@ print_isl_constraint (FILE *f, isl_constraint *c) } DEBUG_FUNCTION void -debug_isl_constraint (isl_constraint *c) +debug_isl_constraint (__isl_keep isl_constraint *c) { print_isl_constraint (stderr, c); } -/* Returns the number of iterations RES of the loop around PBB at - time(scattering) dimension TIME_DEPTH. */ +void +print_isl_schedule (FILE *f, __isl_keep isl_schedule *s) +{ + isl_printer *p = isl_printer_to_file (the_isl_ctx, f); +#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS + p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK); +#endif + p = isl_printer_print_schedule (p, s); + p = isl_printer_print_str (p, "\n"); + isl_printer_free (p); +} + +DEBUG_FUNCTION void +debug_isl_schedule (__isl_keep isl_schedule *s) +{ + print_isl_schedule (stderr, s); +} void -pbb_number_of_iterations_at_time (poly_bb_p pbb, - graphite_dim_t time_depth, - mpz_t res) -{ - isl_set *transdomain; - isl_space *dc; - isl_aff *aff; - isl_val *isllb, *islub; - - /* Map the iteration domain through the current scatter, and work - on the resulting set. */ - transdomain = isl_set_apply (isl_set_copy (pbb->domain), - isl_map_copy (pbb->transformed)); - - /* Select the time_depth' dimension via an affine expression. */ - dc = isl_set_get_space (transdomain); - aff = isl_aff_zero_on_domain (isl_local_space_from_space (dc)); - aff = isl_aff_set_coefficient_si (aff, isl_dim_in, time_depth, 1); - - /* And find the min/max for that function. */ - /* XXX isl check results? */ - isllb = isl_set_min_val (transdomain, aff); - islub = isl_set_max_val (transdomain, aff); - - islub = isl_val_sub (islub, isllb); - islub = isl_val_add_ui (islub, 1); - isl_val_get_num_gmp (islub, res); - - isl_val_free (islub); - isl_aff_free (aff); - isl_set_free (transdomain); +print_isl_ast (FILE *file, __isl_keep isl_ast_node *n) +{ + isl_printer *prn = isl_printer_to_file (the_isl_ctx, file); + prn = isl_printer_set_output_format (prn, ISL_FORMAT_C); + prn = isl_printer_print_ast_node (prn, n); + prn = isl_printer_print_str (prn, "\n"); + isl_printer_free (prn); +} + +DEBUG_FUNCTION void +debug_isl_ast (isl_ast_node *n) +{ + print_isl_ast (stderr, n); +} + +DEBUG_FUNCTION void +debug_scop_pbb (scop_p scop, int i) +{ + debug_pbb (scop->pbbs[i]); } #endif /* HAVE_isl */ diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c index d026d4f..03b1c49 100644 --- a/gcc/graphite-scop-detection.c +++ b/gcc/graphite-scop-detection.c @@ -533,21 +533,6 @@ public: static edge get_nearest_pdom_with_single_exit (basic_block dom); - - /* Pretty printers. */ - - static void print_edge (FILE *file, const_edge e) - { - fprintf (file, "edge (bb_%d, bb_%d)", e->src->index, e->dest->index); - } - - static void print_sese (FILE *file, sese_l s) - { - fprintf (file, "(entry_"); print_edge (file, s.entry); - fprintf (file, ", exit_"); print_edge (file, s.exit); - fprintf (file, ")\n"); - } - /* Merge scops at same loop depth and returns the new sese. Returns a new SESE when merge was successful, INVALID_SESE otherwise. */ diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index 92ab2f9..b62789f8 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -77,6 +77,7 @@ isl_id_for_pbb (scop_p s, poly_bb_p pbb) return isl_id_alloc (s->isl_context, name, pbb); } +#ifndef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS /* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron. We generate SCATTERING_DIMENSIONS scattering dimensions. @@ -221,6 +222,7 @@ build_scop_scattering (scop_p scop) isl_aff_free (static_sched); } +#endif static isl_pw_aff *extract_affine (scop_p, tree, __isl_take isl_space *space); @@ -440,10 +442,7 @@ create_pw_aff_from_tree (poly_bb_p pbb, tree t) t = scalar_evolution_in_region (scop->scop_info->region, pbb_loop (pbb), t); - /* Bail out as we do not know the scev. */ - if (chrec_contains_undetermined (t)) - return NULL; - + gcc_assert (!chrec_contains_undetermined (t)); gcc_assert (!automatically_generated_chrec_p (t)); return extract_affine (scop, t, isl_set_get_space (pbb->domain)); @@ -453,19 +452,11 @@ create_pw_aff_from_tree (poly_bb_p pbb, tree t) operator. This allows us to invert the condition or to handle inequalities. */ -static bool +static void add_condition_to_pbb (poly_bb_p pbb, gcond *stmt, enum tree_code code) { isl_pw_aff *lhs = create_pw_aff_from_tree (pbb, gimple_cond_lhs (stmt)); - if (!lhs) - return false; - isl_pw_aff *rhs = create_pw_aff_from_tree (pbb, gimple_cond_rhs (stmt)); - if (!rhs) - { - isl_pw_aff_free (lhs); - return false; - } isl_set *cond; switch (code) @@ -495,20 +486,17 @@ add_condition_to_pbb (poly_bb_p pbb, gcond *stmt, enum tree_code code) break; default: - isl_pw_aff_free (lhs); - isl_pw_aff_free (rhs); - return true; + gcc_unreachable (); } cond = isl_set_coalesce (cond); cond = isl_set_set_tuple_id (cond, isl_set_get_tuple_id (pbb->domain)); pbb->domain = isl_set_coalesce (isl_set_intersect (pbb->domain, cond)); - return true; } /* Add conditions to the domain of PBB. */ -static bool +static void add_conditions_to_domain (poly_bb_p pbb) { unsigned int i; @@ -516,7 +504,7 @@ add_conditions_to_domain (poly_bb_p pbb) gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb); if (GBB_CONDITIONS (gbb).is_empty ()) - return true; + return; FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt) switch (gimple_code (stmt)) @@ -534,36 +522,14 @@ add_conditions_to_domain (poly_bb_p pbb) if (!GBB_CONDITION_CASES (gbb)[i]) code = invert_tree_comparison (code, false); - if (!add_condition_to_pbb (pbb, cond_stmt, code)) - return false; + add_condition_to_pbb (pbb, cond_stmt, code); break; } - case GIMPLE_SWITCH: - /* Switch statements are not supported right now - fall through. */ - default: gcc_unreachable (); break; } - - return true; -} - -/* Traverses all the GBBs of the SCOP and add their constraints to the - iteration domains. */ - -static bool -add_conditions_to_constraints (scop_p scop) -{ - int i; - poly_bb_p pbb; - - FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) - if (!add_conditions_to_domain (pbb)) - return false; - - return true; } /* Add constraints on the possible values of parameter P from the type @@ -898,6 +864,19 @@ build_scop_drs (scop_p scop) build_poly_sr (pbb); } +/* Add to the iteration DOMAIN one extra dimension for LOOP->num. */ + +static isl_set * +add_iter_domain_dimension (__isl_take isl_set *domain, loop_p loop, scop_p scop) +{ + int loop_index = isl_set_dim (domain, isl_dim_set); + domain = isl_set_add_dims (domain, isl_dim_set, 1); + char name[50]; + snprintf (name, sizeof(name), "i%d", loop->num); + isl_id *label = isl_id_alloc (scop->isl_context, name, NULL); + return isl_set_set_dim_id (domain, isl_dim_set, loop_index, label); +} + /* Add constraints to DOMAIN for each loop from LOOP up to CONTEXT. */ static isl_set * @@ -919,7 +898,7 @@ add_loop_constraints (scop_p scop, __isl_take isl_set *domain, loop_p loop, if (dump_file) fprintf (dump_file, "[sese-to-poly] adding one extra dimension to the " "domain for loop_%d.\n", loop->num); - domain = isl_set_add_dims (domain, isl_dim_set, 1); + domain = add_iter_domain_dimension (domain, loop, scop); isl_space *space = isl_set_get_space (domain); /* 0 <= loop_i */ @@ -1014,8 +993,8 @@ add_loop_constraints (scop_p scop, __isl_take isl_set *domain, loop_p loop, /* Builds the original iteration domains for each pbb in the SCOP. */ static int -build_iteration_domains (scop_p scop, __isl_keep isl_set *context, int index, - loop_p context_loop) +build_iteration_domains (scop_p scop, __isl_keep isl_set *context, + int index, loop_p context_loop) { loop_p current = pbb_loop (scop->pbbs[index]); isl_set *domain = isl_set_copy (context); @@ -1029,9 +1008,14 @@ build_iteration_domains (scop_p scop, __isl_keep isl_set *context, int index, loop_p loop = pbb_loop (pbb); if (current == loop) { +#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS + pbb->iterators = isl_set_copy (domain); +#endif pbb->domain = isl_set_copy (domain); pbb->domain = isl_set_set_tuple_id (pbb->domain, isl_id_for_pbb (scop, pbb)); + add_conditions_to_domain (pbb); + if (dump_file) { fprintf (dump_file, "[sese-to-poly] set pbb_%d->domain: ", @@ -1061,7 +1045,6 @@ build_iteration_domains (scop_p scop, __isl_keep isl_set *context, int index, return i; } - /* Assign dimension for each parameter in SCOP and add constraints for the parameters. */ @@ -1085,6 +1068,289 @@ build_scop_context (scop_p scop) add_param_constraints (scop, p); } +#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS + +/* Return true when loop A is nested in loop B. */ + +static bool +nested_in (loop_p a, loop_p b) +{ + return b == find_common_loop (a, b); +} + +/* Return the loop at a specific SCOP->pbbs[*INDEX]. */ +static loop_p +loop_at (scop_p scop, int *index) +{ + return pbb_loop (scop->pbbs[*index]); +} + +/* Return the index of any pbb belonging to loop or a subloop of A. */ + +static int +index_outermost_in_loop (loop_p a, scop_p scop) +{ + int i, outermost = -1; + int last_depth = -1; + poly_bb_p pbb; + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) + if (nested_in (pbb_loop (pbb), a) + && (last_depth == -1 + || last_depth > (int) loop_depth (pbb_loop (pbb)))) + { + outermost = i; + last_depth = loop_depth (pbb_loop (pbb)); + } + return outermost; +} + +/* Return the index of any pbb belonging to loop or a subloop of A. */ + +static int +index_pbb_in_loop (loop_p a, scop_p scop) +{ + int i; + poly_bb_p pbb; + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) + if (pbb_loop (pbb) == a) + return i; + return -1; +} + +static poly_bb_p +outermost_pbb_in (loop_p loop, scop_p scop) +{ + int x = index_pbb_in_loop (loop, scop); + if (x == -1) + x = index_outermost_in_loop (loop, scop); + return scop->pbbs[x]; +} + +static isl_schedule * +add_in_sequence (__isl_take isl_schedule *a, __isl_take isl_schedule *b) +{ + gcc_assert (a || b); + + if (!a) + return b; + + if (!b) + return a; + + return isl_schedule_sequence (a, b); +} + +struct map_to_dimension_data { + int n; + isl_union_pw_multi_aff *res; +}; + +/* Create a function that maps the elements of SET to its N-th dimension and add + it to USER->res. */ + +static isl_stat +add_outer_projection (__isl_take isl_set *set, void *user) +{ + struct map_to_dimension_data *data = (struct map_to_dimension_data *) user; + int dim = isl_set_dim (set, isl_dim_set); + isl_space *space = isl_set_get_space (set); + + gcc_assert (dim >= data->n); + isl_pw_multi_aff *pma + = isl_pw_multi_aff_project_out_map (space, isl_dim_set, data->n, + dim - data->n); + data->res = isl_union_pw_multi_aff_add_pw_multi_aff (data->res, pma); + + isl_set_free (set); + return isl_stat_ok; +} + +/* Return SET in which all inner dimensions above N are removed. */ + +static isl_multi_union_pw_aff * +outer_projection_mupa (__isl_take isl_union_set *set, int n) +{ + gcc_assert (n >= 0); + gcc_assert (set); + gcc_assert (!isl_union_set_is_empty (set)); + + isl_space *space = isl_union_set_get_space (set); + isl_union_pw_multi_aff *pwaff = isl_union_pw_multi_aff_empty (space); + + struct map_to_dimension_data data = {n, pwaff}; + + if (isl_union_set_foreach_set (set, &add_outer_projection, &data) < 0) + data.res = isl_union_pw_multi_aff_free (data.res); + + isl_union_set_free (set); + return isl_multi_union_pw_aff_from_union_pw_multi_aff (data.res); +} + +/* Embed SCHEDULE in the constraints of the LOOP domain. */ + +static isl_schedule * +add_loop_schedule (__isl_take isl_schedule *schedule, loop_p loop, + scop_p scop) +{ + poly_bb_p pbb = outermost_pbb_in (loop, scop); + isl_set *iterators = pbb->iterators; + + int empty = isl_set_is_empty (iterators); + if (empty < 0 || empty) + return empty < 0 ? isl_schedule_free (schedule) : schedule; + + isl_space *space = isl_set_get_space (iterators); + int loop_index = isl_space_dim (space, isl_dim_set) - 1; + + loop_p ploop = pbb_loop (pbb); + while (loop != ploop) + { + --loop_index; + ploop = loop_outer (ploop); + } + + isl_local_space *ls = isl_local_space_from_space (space); + isl_aff *aff = isl_aff_var_on_domain (ls, isl_dim_set, loop_index); + isl_multi_aff *prefix = isl_multi_aff_from_aff (aff); + char name[50]; + snprintf (name, sizeof(name), "L_%d", loop->num); + isl_id *label = isl_id_alloc (isl_schedule_get_ctx (schedule), + name, NULL); + prefix = isl_multi_aff_set_tuple_id (prefix, isl_dim_out, label); + + int n = isl_multi_aff_dim (prefix, isl_dim_in); + isl_union_set *domain = isl_schedule_get_domain (schedule); + isl_multi_union_pw_aff *mupa = outer_projection_mupa (domain, n); + mupa = isl_multi_union_pw_aff_apply_multi_aff (mupa, prefix); + return isl_schedule_insert_partial_schedule (schedule, mupa); +} + +/* Build schedule for the pbb at INDEX. */ + +static isl_schedule * +build_schedule_pbb (scop_p scop, int *index) +{ + poly_bb_p pbb = scop->pbbs[*index]; + ++*index; + isl_set *domain = isl_set_copy (pbb->domain); + isl_union_set *ud = isl_union_set_from_set (domain); + return isl_schedule_from_domain (ud); +} + +static isl_schedule *build_schedule_loop_nest (scop_p, int *, loop_p); + +/* Build the schedule of the loop containing the SCOP pbb at INDEX. */ + +static isl_schedule * +build_schedule_loop (scop_p scop, int *index) +{ + int max = scop->pbbs.length (); + gcc_assert (*index < max); + loop_p loop = loop_at (scop, index); + + isl_schedule *s = NULL; + while (nested_in (loop_at (scop, index), loop)) + { + if (loop == loop_at (scop, index)) + s = add_in_sequence (s, build_schedule_pbb (scop, index)); + else + s = add_in_sequence (s, build_schedule_loop_nest (scop, index, loop)); + + if (*index == max) + break; + } + + return add_loop_schedule (s, loop, scop); +} + +/* S is the schedule of the loop LOOP. Embed the schedule S in all outer loops. + When CONTEXT_LOOP is null, embed the schedule in all loops contained in the + SCOP surrounding LOOP. When CONTEXT_LOOP is non null, only embed S in the + maximal loop nest contained within CONTEXT_LOOP. */ + +static isl_schedule * +embed_in_surrounding_loops (__isl_take isl_schedule *s, scop_p scop, + loop_p loop, int *index, loop_p context_loop) +{ + loop_p outer = loop_outer (loop); + sese_l region = scop->scop_info->region; + if (context_loop == outer + || !loop_in_sese_p (outer, region)) + return s; + + int max = scop->pbbs.length (); + if (*index == max + || (context_loop && !nested_in (loop_at (scop, index), context_loop)) + || (!context_loop + && !loop_in_sese_p (find_common_loop (outer, loop_at (scop, index)), + region))) + return embed_in_surrounding_loops (add_loop_schedule (s, outer, scop), + scop, outer, index, context_loop); + + bool a_pbb; + while ((a_pbb = (outer == loop_at (scop, index))) + || nested_in (loop_at (scop, index), outer)) + { + if (a_pbb) + s = add_in_sequence (s, build_schedule_pbb (scop, index)); + else + s = add_in_sequence (s, build_schedule_loop (scop, index)); + + if (*index == max) + break; + } + + /* We reached the end of the OUTER loop: embed S in OUTER. */ + return embed_in_surrounding_loops (add_loop_schedule (s, outer, scop), scop, + outer, index, context_loop); +} + +/* Build schedule for the full loop nest containing the pbb at INDEX. When + CONTEXT_LOOP is null, build the schedule of all loops contained in the SCOP + surrounding the pbb. When CONTEXT_LOOP is non null, only build the maximal loop + nest contained within CONTEXT_LOOP. */ + +static isl_schedule * +build_schedule_loop_nest (scop_p scop, int *index, loop_p context_loop) +{ + gcc_assert (*index != (int) scop->pbbs.length ()); + + loop_p loop = loop_at (scop, index); + isl_schedule *s = build_schedule_loop (scop, index); + return embed_in_surrounding_loops (s, scop, loop, index, context_loop); +} + +/* Build the schedule of the SCOP. */ + +static bool +build_original_schedule (scop_p scop) +{ + int i = 0; + int n = scop->pbbs.length (); + while (i < n) + { + poly_bb_p pbb = scop->pbbs[i]; + isl_schedule *s = NULL; + if (!loop_in_sese_p (pbb_loop (pbb), scop->scop_info->region)) + s = build_schedule_pbb (scop, &i); + else + s = build_schedule_loop_nest (scop, &i, NULL); + + scop->original_schedule = add_in_sequence (scop->original_schedule, s); + } + + if (dump_file) + { + fprintf (dump_file, "[sese-to-poly] original schedule:\n"); + print_isl_schedule (dump_file, scop->original_schedule); + } + if (!scop->original_schedule) + return false; + return true; +} + +#endif + /* Builds the polyhedral representation for a SESE region. */ bool @@ -1097,11 +1363,12 @@ build_poly_scop (scop_p scop) while (i < n) i = build_iteration_domains (scop, scop->param_context, i, NULL); - if (!add_conditions_to_constraints (scop)) - return false; - build_scop_drs (scop); +#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS + build_original_schedule (scop); +#else build_scop_scattering (scop); +#endif return true; } #endif /* HAVE_isl */ diff --git a/gcc/graphite.h b/gcc/graphite.h index 2f36ded..578fa1a 100644 --- a/gcc/graphite.h +++ b/gcc/graphite.h @@ -209,7 +209,6 @@ struct poly_dr void new_poly_dr (poly_bb_p, gimple *, enum poly_dr_type, isl_map *, isl_set *); -void free_poly_dr (poly_dr_p); void debug_pdr (poly_dr_p); void print_pdr (FILE *, poly_dr_p); @@ -268,10 +267,9 @@ struct poly_bb The number of variables in the DOMAIN may change and is not related to the number of loops in the original code. */ isl_set *domain; - - /* The data references we access. */ - vec drs; - +#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS + isl_set *iterators; +#else /* The original scattering. */ isl_map *schedule; @@ -280,6 +278,10 @@ struct poly_bb /* A copy of the transformed scattering. */ isl_map *saved; +#endif + + /* The data references we access. */ + vec drs; /* The last basic block generated for this pbb. */ basic_block new_bb; @@ -290,8 +292,6 @@ struct poly_bb #define PBB_DRS(PBB) (PBB->drs) extern poly_bb_p new_poly_bb (scop_p, gimple_poly_bb_p); -extern void free_poly_bb (poly_bb_p); -extern void debug_loop_vec (poly_bb_p); extern void print_pbb_domain (FILE *, poly_bb_p); extern void print_pbb (FILE *, poly_bb_p); extern void print_scop_context (FILE *, scop_p); @@ -313,18 +313,19 @@ extern void print_isl_map (FILE *, isl_map *); extern void print_isl_union_map (FILE *, isl_union_map *); extern void print_isl_aff (FILE *, isl_aff *); extern void print_isl_constraint (FILE *, isl_constraint *); +extern void print_isl_schedule (FILE *, isl_schedule *); +extern void debug_isl_schedule (isl_schedule *); +extern void print_isl_ast (FILE *, isl_ast_node *); +extern void debug_isl_ast (isl_ast_node *); extern void debug_isl_set (isl_set *); extern void debug_isl_map (isl_map *); extern void debug_isl_union_map (isl_union_map *); extern void debug_isl_aff (isl_aff *); extern void debug_isl_constraint (isl_constraint *); -extern int scop_do_interchange (scop_p); -extern int scop_do_strip_mine (scop_p, int); -extern bool scop_do_block (scop_p); -extern bool flatten_all_loops (scop_p); -extern bool optimize_isl (scop_p); -extern void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, mpz_t); extern void debug_gmp_value (mpz_t); +extern void debug_scop_pbb (scop_p scop, int i); +extern void print_schedule_ast (FILE *, __isl_keep isl_schedule *, scop_p); +extern void debug_schedule_ast (__isl_keep isl_schedule *, scop_p); /* The basic block of the PBB. */ @@ -424,8 +425,16 @@ struct scop /* The context used internally by isl. */ isl_ctx *isl_context; +#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS + /* SCoP original schedule. */ + isl_schedule *original_schedule; + + /* SCoP transformed schedule. */ + isl_schedule *transformed_schedule; +#else /* SCoP final schedule. */ isl_schedule *schedule; +#endif /* The data dependence relation among the data references in this scop. */ isl_union_map *dependence; @@ -435,10 +444,6 @@ extern scop_p new_scop (edge, edge); extern void free_scop (scop_p); extern gimple_poly_bb_p new_gimple_poly_bb (basic_block, vec, vec, vec); -extern void free_gimple_poly_bb (gimple_poly_bb_p); -extern void print_generated_program (FILE *, scop_p); -extern void debug_generated_program (scop_p); -extern int unify_scattering_dimensions (scop_p); extern bool apply_poly_transforms (scop_p); /* Set the region of SCOP to REGION. */ @@ -465,8 +470,11 @@ scop_set_nb_params (scop_p scop, graphite_dim_t nb_params) scop->nb_params = nb_params; } -isl_union_map * -scop_get_dependences (scop_p scop); +#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS +extern void scop_get_dependences (scop_p scop); +#else +extern isl_union_map *scop_get_dependences (scop_p scop); +#endif bool carries_deps (__isl_keep isl_union_map *schedule, @@ -475,9 +483,9 @@ carries_deps (__isl_keep isl_union_map *schedule, extern bool build_poly_scop (scop_p); extern bool graphite_regenerate_ast_isl (scop_p); - extern void build_scops (vec *); extern void dot_all_sese (FILE *, vec &); extern void dot_sese (sese_l &); extern void dot_cfg (); + #endif diff --git a/gcc/sese.c b/gcc/sese.c index 3b43142..08ea47d 100644 --- a/gcc/sese.c +++ b/gcc/sese.c @@ -585,3 +585,37 @@ scalar_evolution_in_region (const sese_l ®ion, loop_p loop, tree t) return instantiate_scev (before, loop, t); } + +/* Pretty print edge E to FILE. */ + +void +print_edge (FILE *file, const_edge e) +{ + fprintf (file, "edge (bb_%d, bb_%d)", e->src->index, e->dest->index); +} + +/* Pretty print sese S to FILE. */ + +void +print_sese (FILE *file, const sese_l &s) +{ + fprintf (file, "(entry_"); print_edge (file, s.entry); + fprintf (file, ", exit_"); print_edge (file, s.exit); + fprintf (file, ")\n"); +} + +/* Pretty print edge E to STDERR. */ + +DEBUG_FUNCTION void +debug_edge (const_edge e) +{ + print_edge (stderr, e); +} + +/* Pretty print sese S to STDERR. */ + +DEBUG_FUNCTION void +debug_sese (const sese_l &s) +{ + print_sese (stderr, s); +} diff --git a/gcc/sese.h b/gcc/sese.h index 28996cd..c2fe79e 100644 --- a/gcc/sese.h +++ b/gcc/sese.h @@ -43,6 +43,11 @@ struct sese_l edge exit; }; +void print_edge (FILE *file, const_edge e); +void print_sese (FILE *file, const sese_l &s); +void dump_edge (const_edge e); +void dump_sese (const sese_l &); + /* Get the entry of an sese S. */ static inline basic_block @@ -207,7 +212,7 @@ loop_in_sese_p (struct loop *loop, const sese_l ®ion) loop_2 is completely contained -> depth 1 */ static inline unsigned int -sese_loop_depth (sese_l ®ion, loop_p loop) +sese_loop_depth (const sese_l ®ion, loop_p loop) { unsigned int depth = 0; diff --git a/gcc/testsuite/gcc.dg/graphite/pr35356-1.c b/gcc/testsuite/gcc.dg/graphite/pr35356-1.c index 89e6994..649302b 100644 --- a/gcc/testsuite/gcc.dg/graphite/pr35356-1.c +++ b/gcc/testsuite/gcc.dg/graphite/pr35356-1.c @@ -34,4 +34,4 @@ if (n >= k + 1 && k >= 0) { */ -/* { dg-final { scan-tree-dump-times "if \\\(P_9 >= P_10 \\\+ 1 && P_10 >= 0\\\) \\\{" 1 "graphite" } } */ +/* { dg-final { scan-tree-dump "if \\\(P_9 >= P_10 \\\+ 1 && P_10 >= 0\\\) \\\{" "graphite" } } */ diff --git a/gcc/testsuite/gfortran.dg/graphite/interchange-3.f90 b/gcc/testsuite/gfortran.dg/graphite/interchange-3.f90 index a66ddfd..f20eaa9 100644 --- a/gcc/testsuite/gfortran.dg/graphite/interchange-3.f90 +++ b/gcc/testsuite/gfortran.dg/graphite/interchange-3.f90 @@ -24,4 +24,4 @@ Program FOO end Program FOO -! { dg-final { scan-tree-dump-times "unsuccessful, reverting back to the original code." "1" "graphite" } } +! { dg-final { scan-tree-dump-times "codegen error: reverting back to the original code." "1" "graphite" } } -- 2.5.0