From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 51648 invoked by alias); 15 Jan 2016 17:16:06 -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 51549 invoked by uid 89); 15 Jan 2016 17:16:05 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=0.1 required=5.0 tests=AWL,BAYES_50,FREEMAIL_FROM,RCVD_IN_DNSWL_LOW,SPF_PASS,UNSUBSCRIBE_BODY autolearn=no version=3.3.2 spammy=validity, 544, UD:wikipedia.org, Apply X-HELO: mail-oi0-f66.google.com Received: from mail-oi0-f66.google.com (HELO mail-oi0-f66.google.com) (209.85.218.66) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES128-GCM-SHA256 encrypted) ESMTPS; Fri, 15 Jan 2016 17:15:03 +0000 Received: by mail-oi0-f66.google.com with SMTP id x140so9245641oif.1 for ; Fri, 15 Jan 2016 09:15:00 -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=kfqGK6pviMwvPzt8Oo/t/unw97h3uuKu+mr4NU6sVF8=; b=Ck5IIkvOf4ZckQOoMgW9blBP5IIqHRr9ULN9xEZ84WOG+2OYdc7Ny88ZIoOS1DQisC xtsNU1K7gXFkFc7NMUqfvMUR+v6lh2+NWqtXvjO7E33d0CcRVctjaKCSFS42spqU66jB /647wwhJC6juXAQ45QxiRHOchKEBoRHkW1fvyAt7E8P9oHafXRs364heSrAy3H7ubeW/ oDMcRfrEv7hs0176q7txfMLyFdxDU1xw4M3GwJYQhj//2w4dzOA+F+2Td7678vFD8cjq mlvwmN9I/nwgjKVw34UZdWiDz5zemnNscCGdK6OHLDTtD3RSRkeIUqg1cuzMXjpAm8uP Sxlw== X-Gm-Message-State: ALoCoQkhQcI3yxe4t/F3YWidHCW5MzbSkGawYgFVYWjYFklsLjh+bf2ZDPDIBEb5oeQ5O16QcL8A+6UiWd1aoSbdE5x6CxSlmA== X-Received: by 10.202.108.69 with SMTP id h66mr8061481oic.67.1452878098008; Fri, 15 Jan 2016 09:14:58 -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 r63sm6618774oia.13.2016.01.15.09.14.56 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Fri, 15 Jan 2016 09:14:56 -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, Sebastian Pop Subject: [PATCH 12/15] new scop schedule. Date: Fri, 15 Jan 2016 17:16:00 -0000 Message-Id: <1452878086-19297-12-git-send-email-sebpop@gmail.com> In-Reply-To: <1452878086-19297-1-git-send-email-sebpop@gmail.com> References: <1452878086-19297-1-git-send-email-sebpop@gmail.com> X-SW-Source: 2016-01/txt/msg01111.txt.bz2 From: Sebastian Pop * 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::print_isl_ast_node): Removed. (translate_isl_ast_to_gimple::get_max_schedule_dimensions): Remove. (translate_isl_ast_to_gimple::extend_schedule): Remove. (translate_isl_ast_to_gimple::generate_isl_schedule): Remove. (translate_isl_ast_to_gimple::set_options): Remove. (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 (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/testsuite * gcc.dg/graphite/block-0.c: Adjust pattern. * gcc.dg/graphite/block-1.c: Same. * gcc.dg/graphite/block-5.c: Same. * gcc.dg/graphite/block-6.c: Same. * gcc.dg/graphite/block-pr47654.c: Same. * gcc.dg/graphite/interchange-0.c: Same. * gcc.dg/graphite/interchange-10.c: Same. * gcc.dg/graphite/interchange-12.c: Same. * gcc.dg/graphite/interchange-14.c: Same. * gcc.dg/graphite/interchange-15.c: Same. * gcc.dg/graphite/interchange-5.c: Same. * gcc.dg/graphite/interchange-6.c: Same. * gcc.dg/graphite/interchange-8.c: Same. * gcc.dg/graphite/interchange-mvt.c: Same. * gcc.dg/graphite/pr35356-1.c: Same. * gcc.dg/graphite/scop-10.c (int toto): Same. * gcc.dg/graphite/uns-block-1.c: Same. * gcc.dg/graphite/uns-interchange-12.c: Same. * gcc.dg/graphite/uns-interchange-14.c: Same. * gcc.dg/graphite/uns-interchange-15.c: Same. * gcc.dg/graphite/uns-interchange-mvt.c: Same. * gfortran.dg/graphite/interchange-3.f90: Same. * gfortran.dg/graphite/pr14741.f90: Same. --- gcc/graphite-dependences.c | 169 +++---- gcc/graphite-isl-ast-to-gimple.c | 232 ++------- gcc/graphite-optimize-isl.c | 83 +++- gcc/graphite-poly.c | 115 ++--- gcc/graphite-scop-detection.c | 15 - gcc/graphite-sese-to-poly.c | 531 +++++++++++++-------- gcc/graphite.h | 41 +- gcc/sese.c | 34 ++ gcc/sese.h | 7 +- gcc/testsuite/gcc.dg/graphite/block-0.c | 2 +- gcc/testsuite/gcc.dg/graphite/block-1.c | 2 +- gcc/testsuite/gcc.dg/graphite/block-5.c | 3 +- gcc/testsuite/gcc.dg/graphite/block-6.c | 2 +- gcc/testsuite/gcc.dg/graphite/block-pr47654.c | 2 +- gcc/testsuite/gcc.dg/graphite/interchange-0.c | 2 +- gcc/testsuite/gcc.dg/graphite/interchange-10.c | 2 +- gcc/testsuite/gcc.dg/graphite/interchange-12.c | 3 +- gcc/testsuite/gcc.dg/graphite/interchange-14.c | 3 +- gcc/testsuite/gcc.dg/graphite/interchange-15.c | 2 +- gcc/testsuite/gcc.dg/graphite/interchange-5.c | 2 +- gcc/testsuite/gcc.dg/graphite/interchange-6.c | 2 +- gcc/testsuite/gcc.dg/graphite/interchange-8.c | 3 +- gcc/testsuite/gcc.dg/graphite/interchange-mvt.c | 2 +- gcc/testsuite/gcc.dg/graphite/pr35356-1.c | 3 +- gcc/testsuite/gcc.dg/graphite/scop-10.c | 2 +- gcc/testsuite/gcc.dg/graphite/uns-block-1.c | 2 +- gcc/testsuite/gcc.dg/graphite/uns-interchange-12.c | 3 +- gcc/testsuite/gcc.dg/graphite/uns-interchange-14.c | 3 +- gcc/testsuite/gcc.dg/graphite/uns-interchange-15.c | 2 +- .../gcc.dg/graphite/uns-interchange-mvt.c | 2 +- .../gfortran.dg/graphite/interchange-3.f90 | 2 +- gcc/testsuite/gfortran.dg/graphite/pr14741.f90 | 2 +- 32 files changed, 613 insertions(+), 667 deletions(-) diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c index ae08059..161e019 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,26 +168,6 @@ scop_get_may_writes (scop_p scop, vec pbbs) return isl_union_map_coalesce (res); } -/* Returns all the original schedules in SCOP. */ - -static isl_union_map * -scop_get_original_schedule (scop_p scop, vec pbbs) -{ - int i; - poly_bb_p pbb; - 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) - { - res = isl_union_map_add_map - (res, constrain_domain (isl_map_copy (pbb->schedule), - isl_set_copy (pbb->domain))); - } - - return isl_union_map_coalesce (res); -} - /* Helper function used on each MAP of a isl_union_map. Computes the maximal output dimension. */ @@ -303,34 +289,20 @@ carries_deps (__isl_keep isl_union_map *schedule, return res; } -/* Compute the original data dependences in SCOP for all the reads and - writes in PBBS. */ - -static void -compute_deps (scop_p scop, vec pbbs, - isl_union_map **must_raw, - isl_union_map **may_raw, - isl_union_map **must_raw_no_source, - isl_union_map **may_raw_no_source, - isl_union_map **must_war, - isl_union_map **may_war, - isl_union_map **must_war_no_source, - isl_union_map **may_war_no_source, - isl_union_map **must_waw, - isl_union_map **may_waw, - isl_union_map **must_waw_no_source, - isl_union_map **may_waw_no_source) +/* 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) { - 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 *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); + if (scop->dependence) + return; - isl_space *space = isl_union_map_get_space (all_writes); - isl_union_map *empty = isl_union_map_empty (space); - isl_union_map *original = scop_get_original_schedule (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); if (dump_file) { @@ -357,57 +329,40 @@ compute_deps (scop_p scop, vec pbbs, print_isl_union_map (dump_file, must_writes); fprintf (dump_file, " may_writes: "); print_isl_union_map (dump_file, may_writes); - fprintf (dump_file, " all_writes: "); - print_isl_union_map (dump_file, all_writes); fprintf (dump_file, ")\n"); } - isl_union_map_compute_flow (isl_union_map_copy (reads), - isl_union_map_copy (must_writes), - isl_union_map_copy (may_writes), - isl_union_map_copy (original), - must_raw, may_raw, must_raw_no_source, - may_raw_no_source); - isl_union_map_compute_flow (isl_union_map_copy (all_writes), - reads, empty, - isl_union_map_copy (original), - must_war, may_war, must_war_no_source, - may_war_no_source); - isl_union_map_compute_flow (all_writes, must_writes, may_writes, - original, - must_waw, may_waw, must_waw_no_source, - may_waw_no_source); -} - -isl_union_map * -scop_get_dependences (scop_p scop) -{ - if (scop->dependence) - return scop->dependence; - - /* The original dependence relations: - RAW are read after write dependences, - WAR are write after read dependences, - WAW are write after write dependences. */ - isl_union_map *must_raw = NULL, *may_raw = NULL, *must_raw_no_source = NULL, - *may_raw_no_source = NULL, *must_war = NULL, *may_war = NULL, - *must_war_no_source = NULL, *may_war_no_source = NULL, *must_waw = NULL, - *may_waw = NULL, *must_waw_no_source = NULL, *may_waw_no_source = NULL; - - compute_deps (scop, scop->pbbs, - &must_raw, &may_raw, - &must_raw_no_source, &may_raw_no_source, - &must_war, &may_war, - &must_war_no_source, &may_war_no_source, - &must_waw, &may_waw, - &must_waw_no_source, &may_waw_no_source); - - isl_union_map *dependences = must_raw; - dependences = isl_union_map_union (dependences, must_war); - dependences = isl_union_map_union (dependences, must_waw); - dependences = isl_union_map_union (dependences, may_raw); - dependences = isl_union_map_union (dependences, may_war); - dependences = isl_union_map_union (dependences, may_waw); + 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) @@ -417,15 +372,7 @@ scop_get_dependences (scop_p scop) fprintf (dump_file, ")\n"); } - isl_union_map_free (must_raw_no_source); - isl_union_map_free (may_raw_no_source); - isl_union_map_free (must_war_no_source); - isl_union_map_free (may_war_no_source); - isl_union_map_free (must_waw_no_source); - isl_union_map_free (may_waw_no_source); - scop->dependence = dependences; - return dependences; } #endif /* HAVE_isl */ diff --git a/gcc/graphite-isl-ast-to-gimple.c b/gcc/graphite-isl-ast-to-gimple.c index a196419..2823d22 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 (); @@ -117,7 +117,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) @@ -135,6 +135,26 @@ 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); +} + enum phi_node_kind { unknown_phi, @@ -285,40 +305,13 @@ 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); - /* 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); - - /* 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); - - /* 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); + /* Generate isl AST from schedule of SCOP. */ + __isl_give isl_ast_node * scop_to_isl_ast (scop_p scop); /* 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 @@ -474,11 +467,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 @@ -1365,7 +1353,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"); } @@ -3052,20 +3040,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 @@ -3094,83 +3068,6 @@ translate_isl_ast_to_gimple::generate_isl_context (scop_p scop) return isl_ast_build_from_context (context_isl); } -/* Get the maximal number of schedule dimensions in the scop SCOP. */ - -int -translate_isl_ast_to_gimple::get_max_schedule_dimensions (scop_p scop) -{ - int i; - poly_bb_p pbb; - int schedule_dims = 0; - - FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) - { - int pbb_schedule_dims = isl_map_dim (pbb->transformed, isl_dim_out); - if (pbb_schedule_dims > schedule_dims) - schedule_dims = pbb_schedule_dims; - } - - return schedule_dims; -} - -/* 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 * -translate_isl_ast_to_gimple::extend_schedule (__isl_take isl_map *schedule, - int nb_schedule_dims) -{ - int tmp_dims = isl_map_dim (schedule, isl_dim_out); - schedule = - isl_map_add_dims (schedule, isl_dim_out, nb_schedule_dims - tmp_dims); - isl_val *zero = - isl_val_int_from_si (isl_map_get_ctx (schedule), 0); - int i; - for (i = tmp_dims; i < nb_schedule_dims; i++) - { - schedule - = isl_map_fix_val (schedule, isl_dim_out, i, isl_val_copy (zero)); - } - isl_val_free (zero); - return schedule; -} - -/* Generates a schedule, which specifies an order used to - visit elements in a domain. */ - -__isl_give isl_union_map * -translate_isl_ast_to_gimple::generate_isl_schedule (scop_p scop) -{ - int nb_schedule_dims = get_max_schedule_dimensions (scop); - int i; - poly_bb_p pbb; - isl_union_map *schedule_isl = - isl_union_map_empty (isl_set_get_space (scop->param_context)); - - FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) - { - /* Dead code elimination: when the domain of a PBB is empty, - don't generate code for the PBB. */ - if (isl_set_is_empty (pbb->domain)) - continue; - - isl_map *bb_schedule = isl_map_copy (pbb->transformed); - bb_schedule = isl_map_intersect_domain (bb_schedule, - isl_set_copy (pbb->domain)); - bb_schedule = extend_schedule (bb_schedule, nb_schedule_dims); - bb_schedule = isl_map_coalesce (bb_schedule); - schedule_isl - = isl_union_map_union (schedule_isl, - isl_union_map_from_map (bb_schedule)); - schedule_isl = isl_union_map_coalesce (schedule_isl); - } - 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) @@ -3188,63 +3085,28 @@ ast_build_before_for (__isl_keep isl_ast_build *build, void *user) return id; } -/* Set the separate option for all dimensions. - This helps to reduce control overhead. */ - -__isl_give isl_ast_build * -translate_isl_ast_to_gimple::set_options (__isl_take isl_ast_build *control, - __isl_keep isl_union_map *schedule) -{ - isl_ctx *ctx = isl_union_map_get_ctx (schedule); - isl_space *range_space = isl_space_set_alloc (ctx, 0, 1); - range_space = - isl_space_set_tuple_name (range_space, isl_dim_set, "separate"); - isl_union_set *range = - isl_union_set_from_set (isl_set_universe (range_space)); - isl_union_set *domain = isl_union_map_range (isl_union_map_copy (schedule)); - domain = isl_union_set_universe (domain); - isl_union_map *options = isl_union_map_from_domain_and_range (domain, range); - return isl_ast_build_set_options (control, options); -} - -/* Generate isl AST from schedule of SCOP. Also, collects IVS_PARAMS in IP. */ +/* Generate isl AST from schedule of SCOP. */ __isl_give isl_ast_node * -translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop, ivs_params &ip) +translate_isl_ast_to_gimple::scop_to_isl_ast (scop_p scop) { - /* 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, true); - - add_parameters_to_ivs_params (scop, ip); + gcc_assert (scop->transformed_schedule); - if (scop->schedule) - { - /* Set the separate option to reduce control flow overhead. */ - isl_schedule *schedule = isl_schedule_map_schedule_node_bottom_up - (scop->schedule, set_separate_option, NULL); - isl_ast_build *context_isl = generate_isl_context (scop); - isl_ast_node *ast_isl = isl_ast_build_node_from_schedule - (context_isl, schedule); - isl_ast_build_free (context_isl); - return ast_isl; - } - - /* graphite-identity, or parallelize. */ - isl_union_map *schedule_isl = generate_isl_schedule (scop); + /* 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); - context_isl = set_options (context_isl, schedule_isl); + if (flag_loop_parallelize_all) { - isl_union_map *dependence = scop_get_dependences (scop); + scop_get_dependences (scop); context_isl = isl_ast_build_set_before_each_for (context_isl, ast_build_before_for, - dependence); + scop->dependence); } - isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule - (context_isl, schedule_isl); + + isl_ast_node *ast_isl = isl_ast_build_node_from_schedule + (context_isl, schedule); isl_ast_build_free (context_isl); return ast_isl; } @@ -3266,12 +3128,20 @@ graphite_regenerate_ast_isl (scop_p scop) ivs_params ip; timevar_push (TV_GRAPHITE_CODE_GEN); - root_node = t.scop_to_isl_ast (scop, ip); + t.add_parameters_to_ivs_params (scop, ip); + root_node = t.scop_to_isl_ast (scop); - if (dump_file && (dump_flags & TDF_DETAILS)) + if (dump_file) { - fprintf (dump_file, "AST generated by isl: \n"); - t.print_isl_ast_node (dump_file, root_node, scop->isl_context); + 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); + fprintf (dump_file, "[scheduler] AST generated by isl:\n"); + print_isl_ast (dump_file, root_node); } recompute_all_dominators (); @@ -3293,8 +3163,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 diff --git a/gcc/graphite-optimize-isl.c b/gcc/graphite-optimize-isl.c index 306f91c..f385c77 100644 --- a/gcc/graphite-optimize-isl.c +++ b/gcc/graphite-optimize-isl.c @@ -56,7 +56,7 @@ scop_get_domains (scop_p scop) /* 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); @@ -66,57 +66,88 @@ optimize_isl (scop_p scop) isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_CONTINUE); isl_union_set *domain = scop_get_domains (scop); + + /* Simplify the dependences on the domain. */ scop_get_dependences (scop); - scop->dependence - = isl_union_map_gist_domain (scop->dependence, isl_union_set_copy (domain)); - scop->dependence - = isl_union_map_gist_range (scop->dependence, isl_union_set_copy (domain)); - isl_union_map *validity = isl_union_map_copy (scop->dependence); + 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 *schedule_constraints; - schedule_constraints = isl_schedule_constraints_on_domain (domain); - schedule_constraints - = isl_schedule_constraints_set_proximity (schedule_constraints, - proximity); - schedule_constraints - = isl_schedule_constraints_set_validity (schedule_constraints, - isl_union_map_copy (validity)); - schedule_constraints - = isl_schedule_constraints_set_coincidence (schedule_constraints, - 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); - isl_schedule *schedule - = isl_schedule_constraints_compute_schedule (schedule_constraints); + scop->transformed_schedule = isl_schedule_constraints_compute_schedule (sc); 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 (!schedule || isl_ctx_last_error (scop->isl_context) == isl_error_quota) + 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); - if (schedule) - isl_schedule_free (schedule); return false; } - scop->schedule = schedule; + 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 (dump_file) + if (same_schedule) { - fprintf (dump_file, "isl end schedule:\n"); - print_isl_schedule (dump_file, scop->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; +} + #endif /* HAVE_isl */ diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c index de7515a..c1dd5ce 100644 --- a/gcc/graphite-poly.c +++ b/gcc/graphite-poly.c @@ -86,23 +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) -{ - if (flag_loop_nest_optimize && optimize_isl (scop)) - return true; - - 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; -} - /* 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. */ @@ -137,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); @@ -153,9 +136,7 @@ new_poly_bb (scop_p scop, gimple_poly_bb_p black_box) poly_bb_p pbb = XNEW (struct poly_bb); pbb->domain = NULL; - pbb->schedule = NULL; - pbb->transformed = NULL; - pbb->saved = NULL; + pbb->iterators = NULL; PBB_SCOP (pbb) = scop; pbb_set_black_box (pbb, black_box); PBB_DRS (pbb).create (3); @@ -166,16 +147,16 @@ 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); - isl_map_free (pbb->schedule); - isl_map_free (pbb->transformed); - isl_map_free (pbb->saved); + isl_set_free (pbb->iterators); + pbb->domain = NULL; + pbb->iterators = NULL; if (PBB_DRS (pbb).exists ()) FOR_EACH_VEC_ELT (PBB_DRS (pbb), i, pdr) @@ -246,7 +227,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)); @@ -277,7 +258,8 @@ new_scop (edge entry, edge exit) sese_info_p region = new_sese_info (entry, exit); scop_p s = XNEW (struct scop); - s->schedule = NULL; + s->original_schedule = NULL; + s->transformed_schedule = NULL; s->param_context = NULL; scop_set_region (s, region); s->pbbs.create (3); @@ -305,7 +287,13 @@ free_scop (scop_p scop) isl_set_free (scop->param_context); isl_union_map_free (scop->dependence); + isl_schedule_free (scop->original_schedule); + isl_schedule_free (scop->transformed_schedule); + + scop->param_context = NULL; scop->dependence = NULL; + scop->original_schedule = NULL; + scop->transformed_schedule = NULL; XDELETE (scop); } @@ -530,7 +518,7 @@ 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); p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK); @@ -540,13 +528,13 @@ print_isl_set (FILE *f, isl_set *set) } 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); p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK); @@ -556,13 +544,13 @@ print_isl_map (FILE *f, isl_map *map) } 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); p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK); @@ -579,7 +567,7 @@ debug_isl_union_map (isl_union_map *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); @@ -588,13 +576,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); @@ -603,13 +591,13 @@ 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); } void -print_isl_schedule (FILE *f, isl_schedule *s) +print_isl_schedule (FILE *f, __isl_keep isl_schedule *s) { isl_printer *p = isl_printer_to_file (the_isl_ctx, f); p = isl_printer_set_yaml_style (p, ISL_YAML_STYLE_BLOCK); @@ -624,41 +612,26 @@ debug_isl_schedule (isl_schedule *s) print_isl_schedule (stderr, s); } -/* Returns the number of iterations RES of the loop around PBB at - time(scattering) dimension TIME_DEPTH. */ - 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 f035e0d..8dfb20a 100644 --- a/gcc/graphite-scop-detection.c +++ b/gcc/graphite-scop-detection.c @@ -522,21 +522,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 abf18a7..885e0b7 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -77,151 +77,6 @@ isl_id_for_pbb (scop_p s, poly_bb_p pbb) return isl_id_alloc (s->isl_context, name, pbb); } -/* Converts the STATIC_SCHEDULE of PBB into a scattering polyhedron. - We generate SCATTERING_DIMENSIONS scattering dimensions. - - The scattering polyhedron consists of these dimensions: scattering, - loop_iterators, parameters. - - Example: - - | scattering_dimensions = 5 - | nb_iterators = 1 - | scop_nb_params = 2 - | - | Schedule: - | i - | 4 5 - | - | Scattering polyhedron: - | - | scattering: {s1, s2, s3, s4, s5} - | loop_iterators: {i} - | parameters: {p1, p2} - | - | s1 s2 s3 s4 s5 i p1 p2 1 - | 1 0 0 0 0 0 0 0 -4 = 0 - | 0 1 0 0 0 -1 0 0 0 = 0 - | 0 0 1 0 0 0 0 0 -5 = 0 */ - -static void -build_pbb_scattering_polyhedrons (isl_aff *static_sched, - poly_bb_p pbb) -{ - isl_val *val; - - int scattering_dimensions = isl_set_dim (pbb->domain, isl_dim_set) * 2 + 1; - - isl_space *dc = isl_set_get_space (pbb->domain); - isl_space *dm = isl_space_add_dims (isl_space_from_domain (dc), - isl_dim_out, scattering_dimensions); - pbb->schedule = isl_map_universe (dm); - - for (int i = 0; i < scattering_dimensions; i++) - { - /* Textual order inside this loop. */ - if ((i % 2) == 0) - { - isl_constraint *c = isl_equality_alloc - (isl_local_space_from_space (isl_map_get_space (pbb->schedule))); - - val = isl_aff_get_coefficient_val (static_sched, isl_dim_in, i / 2); - gcc_assert (val && isl_val_is_int (val)); - - val = isl_val_neg (val); - c = isl_constraint_set_constant_val (c, val); - c = isl_constraint_set_coefficient_si (c, isl_dim_out, i, 1); - pbb->schedule = isl_map_add_constraint (pbb->schedule, c); - } - - /* Iterations of this loop. */ - else /* if ((i % 2) == 1) */ - { - int loop = (i - 1) / 2; - pbb->schedule = isl_map_equate (pbb->schedule, isl_dim_in, loop, - isl_dim_out, i); - } - } - - /* Simplify the original schedule. */ - pbb->schedule = isl_map_coalesce (pbb->schedule); - - /* At the beginning, set the transformed schedule to the original. */ - pbb->transformed = isl_map_copy (pbb->schedule); -} - -/* Build for BB the static schedule. - - The static schedule is a Dewey numbering of the abstract syntax - tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification - - The following example informally defines the static schedule: - - A - for (i: ...) - { - for (j: ...) - { - B - C - } - - for (k: ...) - { - D - E - } - } - F - - Static schedules for A to F: - - DEPTH - 0 1 2 - A 0 - B 1 0 0 - C 1 0 1 - D 1 1 0 - E 1 1 1 - F 2 -*/ - -static void -build_scop_scattering (scop_p scop) -{ - gimple_poly_bb_p previous_gbb = NULL; - isl_space *dc = isl_set_get_space (scop->param_context); - isl_aff *static_sched; - - dc = isl_space_add_dims (dc, isl_dim_set, number_of_loops (cfun)); - static_sched = isl_aff_zero_on_domain (isl_local_space_from_space (dc)); - - /* We have to start schedules at 0 on the first component and - because we cannot compare_prefix_loops against a previous loop, - prefix will be equal to zero, and that index will be - incremented before copying. */ - static_sched = isl_aff_add_coefficient_si (static_sched, isl_dim_in, 0, -1); - - int i; - poly_bb_p pbb; - FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) - { - gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb); - int prefix = 0; - - if (previous_gbb) - prefix = nb_common_loops (scop->scop_info->region, previous_gbb, gbb); - - previous_gbb = gbb; - - static_sched = isl_aff_add_coefficient_si (static_sched, isl_dim_in, - prefix, 1); - build_pbb_scattering_polyhedrons (static_sched, pbb); - } - - isl_aff_free (static_sched); -} - static isl_pw_aff *extract_affine (scop_p, tree, __isl_take isl_space *space); /* Extract an affine expression from the chain of recurrence E. */ @@ -440,10 +295,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 +305,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 +339,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 +357,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 +375,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 @@ -628,6 +447,29 @@ add_param_constraints (scop_p scop, graphite_dim_t p) } } +/* Assign dimension for each parameter in SCOP and add constraints for the + parameters. */ + +static void +build_scop_context (scop_p scop) +{ + sese_info_p region = scop->scop_info; + unsigned nbp = sese_nb_params (region); + isl_space *space = isl_space_set_alloc (scop->isl_context, nbp, 0); + + unsigned i; + tree e; + FOR_EACH_VEC_ELT (region->params, i, e) + space = isl_space_set_dim_id (space, isl_dim_param, i, + isl_id_for_ssa_name (scop, e)); + + scop->param_context = isl_set_universe (space); + + graphite_dim_t p; + for (p = 0; p < nbp; p++) + add_param_constraints (scop, p); +} + /* Add a constrain to the ACCESSES polyhedron for the alias set of data reference DR. ACCESSP_NB_DIMS is the dimension of the ACCESSES polyhedron, DOM_NB_DIMS is the dimension of the iteration @@ -898,6 +740,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 +774,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 +869,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 +884,12 @@ build_iteration_domains (scop_p scop, __isl_keep isl_set *context, int index, loop_p loop = pbb_loop (pbb); if (current == loop) { + pbb->iterators = isl_set_copy (domain); 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,28 +919,283 @@ build_iteration_domains (scop_p scop, __isl_keep isl_set *context, int index, return i; } +/* Return true when loop A is nested in loop B. */ -/* Assign dimension for each parameter in SCOP and add constraints for the - parameters. */ +static bool +nested_in (loop_p a, loop_p b) +{ + return b == find_common_loop (a, b); +} -static void -build_scop_context (scop_p scop) +/* Return the loop at a specific SCOP->pbbs[*INDEX]. */ +static loop_p +loop_at (scop_p scop, int *index) { - sese_info_p region = scop->scop_info; - unsigned nbp = sese_nb_params (region); - isl_space *space = isl_space_set_alloc (scop->isl_context, nbp, 0); + return pbb_loop (scop->pbbs[*index]); +} - unsigned i; - tree e; - FOR_EACH_VEC_ELT (region->params, i, e) - space = isl_space_set_dim_id (space, isl_dim_param, i, - isl_id_for_ssa_name (scop, e)); +/* Return the index of any pbb belonging to loop or a subloop of A. */ - scop->param_context = isl_set_universe (space); +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; +} - graphite_dim_t p; - for (p = 0; p < nbp; p++) - add_param_constraints (scop, p); +/* 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; } /* Builds the polyhedral representation for a SESE region. */ @@ -1097,11 +1210,7 @@ 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); - build_scop_scattering (scop); - return true; + return build_original_schedule (scop); } #endif /* HAVE_isl */ diff --git a/gcc/graphite.h b/gcc/graphite.h index 7f8a273..7bafd09 100644 --- a/gcc/graphite.h +++ b/gcc/graphite.h @@ -200,7 +200,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); @@ -259,19 +258,11 @@ 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; + isl_set *iterators; /* The data references we access. */ vec drs; - /* The original scattering. */ - isl_map *schedule; - - /* The transformed scattering. */ - isl_map *transformed; - - /* A copy of the transformed scattering. */ - isl_map *saved; - /* The last basic block generated for this pbb. */ basic_block new_bb; }; @@ -281,8 +272,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); @@ -306,18 +295,17 @@ 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. */ @@ -417,8 +405,11 @@ struct scop /* The context used internally by isl. */ isl_ctx *isl_context; - /* SCoP final schedule. */ - isl_schedule *schedule; + /* SCoP original schedule. */ + isl_schedule *original_schedule; + + /* SCoP transformed schedule. */ + isl_schedule *transformed_schedule; /* The data dependence relation among the data references in this scop. */ isl_union_map *dependence; @@ -428,10 +419,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. */ @@ -458,9 +445,6 @@ 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); - bool carries_deps (__isl_keep isl_union_map *schedule, __isl_keep isl_union_map *deps, @@ -468,9 +452,10 @@ 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 scop_get_dependences (scop_p scop); 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 2ecff7d..9ea46c7f 100644 --- a/gcc/sese.c +++ b/gcc/sese.c @@ -581,3 +581,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 f481524..e70ebd1 100644 --- a/gcc/sese.h +++ b/gcc/sese.h @@ -42,6 +42,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 @@ -203,7 +208,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/block-0.c b/gcc/testsuite/gcc.dg/graphite/block-0.c index 0a278f8..4baf79c 100644 --- a/gcc/testsuite/gcc.dg/graphite/block-0.c +++ b/gcc/testsuite/gcc.dg/graphite/block-0.c @@ -42,4 +42,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/block-1.c b/gcc/testsuite/gcc.dg/graphite/block-1.c index 2758404..03a5f83 100644 --- a/gcc/testsuite/gcc.dg/graphite/block-1.c +++ b/gcc/testsuite/gcc.dg/graphite/block-1.c @@ -45,4 +45,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/block-5.c b/gcc/testsuite/gcc.dg/graphite/block-5.c index 28a0192..95f08c7 100644 --- a/gcc/testsuite/gcc.dg/graphite/block-5.c +++ b/gcc/testsuite/gcc.dg/graphite/block-5.c @@ -54,4 +54,5 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/block-6.c b/gcc/testsuite/gcc.dg/graphite/block-6.c index 8902a17..0418a34 100644 --- a/gcc/testsuite/gcc.dg/graphite/block-6.c +++ b/gcc/testsuite/gcc.dg/graphite/block-6.c @@ -49,4 +49,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/block-pr47654.c b/gcc/testsuite/gcc.dg/graphite/block-pr47654.c index 2027a3f..c4ffca3 100644 --- a/gcc/testsuite/gcc.dg/graphite/block-pr47654.c +++ b/gcc/testsuite/gcc.dg/graphite/block-pr47654.c @@ -21,4 +21,4 @@ main () return 0; } -/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-0.c b/gcc/testsuite/gcc.dg/graphite/interchange-0.c index f655e84..3f398ca 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-0.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-0.c @@ -46,4 +46,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "2" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-10.c b/gcc/testsuite/gcc.dg/graphite/interchange-10.c index 825aafd..4f6be65 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-10.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-10.c @@ -46,4 +46,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-12.c b/gcc/testsuite/gcc.dg/graphite/interchange-12.c index 7cdbabe..0012d56 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-12.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-12.c @@ -53,4 +53,5 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-14.c b/gcc/testsuite/gcc.dg/graphite/interchange-14.c index 617659c..917e679 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-14.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-14.c @@ -54,4 +54,5 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-15.c b/gcc/testsuite/gcc.dg/graphite/interchange-15.c index 3696f41..8e147ad 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-15.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-15.c @@ -48,4 +48,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "2" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-5.c b/gcc/testsuite/gcc.dg/graphite/interchange-5.c index 4410a17..e578e17 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-5.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-5.c @@ -46,4 +46,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "2" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-6.c b/gcc/testsuite/gcc.dg/graphite/interchange-6.c index c4500cb..9760ed3 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-6.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-6.c @@ -47,4 +47,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "2" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-8.c b/gcc/testsuite/gcc.dg/graphite/interchange-8.c index 9df7258..c623a32 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-8.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-8.c @@ -82,4 +82,5 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "codegen error: reverting back to the original code" "1" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c b/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c index b43131c..ec6a983 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c @@ -58,4 +58,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "2" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/pr35356-1.c b/gcc/testsuite/gcc.dg/graphite/pr35356-1.c index 89e6994..1c13a69 100644 --- a/gcc/testsuite/gcc.dg/graphite/pr35356-1.c +++ b/gcc/testsuite/gcc.dg/graphite/pr35356-1.c @@ -34,4 +34,5 @@ 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-times "if \\\(P_9 >= P_10 \\\+ 1 && P_10 >= 0\\\) \\\{" "2" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/scop-10.c b/gcc/testsuite/gcc.dg/graphite/scop-10.c index 39ed5d7..ac2c7f9 100644 --- a/gcc/testsuite/gcc.dg/graphite/scop-10.c +++ b/gcc/testsuite/gcc.dg/graphite/scop-10.c @@ -17,7 +17,7 @@ int toto() b[i+j] = b[i+j-1] + 2; a[i][i] = 2; } - + for (k = 1; k < 100; k++) b[i+k] = b[i+k-5] + 2; } diff --git a/gcc/testsuite/gcc.dg/graphite/uns-block-1.c b/gcc/testsuite/gcc.dg/graphite/uns-block-1.c index 5b61eea..19f358d 100644 --- a/gcc/testsuite/gcc.dg/graphite/uns-block-1.c +++ b/gcc/testsuite/gcc.dg/graphite/uns-block-1.c @@ -45,4 +45,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/uns-interchange-12.c b/gcc/testsuite/gcc.dg/graphite/uns-interchange-12.c index a53c98e..2b957f5 100644 --- a/gcc/testsuite/gcc.dg/graphite/uns-interchange-12.c +++ b/gcc/testsuite/gcc.dg/graphite/uns-interchange-12.c @@ -54,4 +54,5 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/uns-interchange-14.c b/gcc/testsuite/gcc.dg/graphite/uns-interchange-14.c index 1e180c6..960e7ae 100644 --- a/gcc/testsuite/gcc.dg/graphite/uns-interchange-14.c +++ b/gcc/testsuite/gcc.dg/graphite/uns-interchange-14.c @@ -55,4 +55,5 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/uns-interchange-15.c b/gcc/testsuite/gcc.dg/graphite/uns-interchange-15.c index adac7d4..5c5597f 100644 --- a/gcc/testsuite/gcc.dg/graphite/uns-interchange-15.c +++ b/gcc/testsuite/gcc.dg/graphite/uns-interchange-15.c @@ -49,4 +49,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "2" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/uns-interchange-mvt.c b/gcc/testsuite/gcc.dg/graphite/uns-interchange-mvt.c index 04f5b7d..153fc8e 100644 --- a/gcc/testsuite/gcc.dg/graphite/uns-interchange-mvt.c +++ b/gcc/testsuite/gcc.dg/graphite/uns-interchange-mvt.c @@ -59,4 +59,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "2" "graphite" } } */ +/* { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "2" "graphite" } } */ diff --git a/gcc/testsuite/gfortran.dg/graphite/interchange-3.f90 b/gcc/testsuite/gfortran.dg/graphite/interchange-3.f90 index a66ddfd..192c5b2 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" } } diff --git a/gcc/testsuite/gfortran.dg/graphite/pr14741.f90 b/gcc/testsuite/gfortran.dg/graphite/pr14741.f90 index 50c2e79..057e57e 100644 --- a/gcc/testsuite/gfortran.dg/graphite/pr14741.f90 +++ b/gcc/testsuite/gfortran.dg/graphite/pr14741.f90 @@ -24,4 +24,4 @@ SUBROUTINE mult(A,B,C,N) ENDDO END SUBROUTINE mult -! { dg-final { scan-tree-dump-times "isl AST to Gimple succeeded" "1" "graphite" } } +! { dg-final { scan-tree-dump-times "isl optimized schedule is identical to the original schedule" "1" "graphite" } } -- 2.5.0