From 7009b073c56b40b280408c0ab69957651372c42e Mon Sep 17 00:00:00 2001 From: Sebastian Pop Date: Mon, 28 Sep 2015 17:30:09 +0000 Subject: [PATCH] Redesign Graphite scop detection Redesign Graphite scop detection for faster compiler time and detecting more SCoPs. Existing algorithm for SCoP detection in graphite was based on dominator tree where a tree (CFG) traversal was required for analyzing an SESE. The tree traversal is linear in the number of basic blocks and SCoP detection is (probably) linear in number of instructions. That algorithm utilized a generic infrastructure of SESE which does not directly represent loops. With regards to graphite framework, we are only interested in subtrees with loops. The new algorithm is geared towards tree traversal on loop structure. The algorithm is linear in number of loops which is faster than the previous algorithm. Briefly, we start the traversal at a loop-nest and analyze it recursively for validity. Once a valid loop is found we find a valid adjacent loop. If an adjacent loop is found and is valid, we merge both loop nests otherwise we form a SCoP from the previous loop nest, and resume the algorithm from the adjacent loop nest. The data structure to represent an SESE is an ordered pair of edges (entry, exit). The new algoritm can extend a SCoP in both the directions. With this approach, the number of instructions to be analyzed for validity reduces to a minimal set. We start by analyzing those statements which are inside a loop, because validity of those statements is necessary for the validity of loop. The statements outside the loop nest can be just excluded from the SESE if they are not valid. This patch depends on: https://gcc.gnu.org/ml/gcc-patches/2015-09/msg02024.html Passes (c,c++,fortran) regtest and bootstrap. gcc/ChangeLog: 2015-09-27 Aditya Kumar Sebastian Pop * graphite-optimize-isl.c (optimize_isl): * graphite-scop-detection.c (struct sese_l): New type. (get_entry_bb): API for getting entry bb of SESE. (get_exit_bb): API for getting exit bb of SESE. (class debug_printer): New type. Simple printer in debug mode. (trivially_empty_bb_p): New. Return true when BB is empty or contains only debug instructions. (graphite_can_represent_expr): Call scalar_evoution_in_region instead of analyze_scalar_evolution. Pass in scop instead of only the scop entry. (stmt_has_simple_data_refs_p): Pass in scop instead of only the scop entry. (stmt_simple_for_scop_p): Same. (harmful_stmt_in_bb): Same. (graphite_can_represent_loop): Deleted. (struct scopdet_info): Deleted. (scopdet_basic_block_info): Deleted. (build_scops_1): Deleted. (bb_in_sd_region): Deleted. (find_single_entry_edge): Deleted. (find_single_exit_edge): Deleted. (create_single_entry_edge): Deleted. (sd_region_without_exit): Deleted. (create_single_exit_edge): Deleted. (unmark_exit_edges): Deleted. (mark_exit_edges): Deleted. (create_sese_edges): Deleted. (build_graphite_scops): Deleted. (canonicalize_loop_closed_ssa): Recompute all dominators at the end. (build_scops): Use the new scop_builder to build scops. (dot_all_scops_1): Use the new pretty printer. Print loop father as well. (loop_body_is_valid_scop): New. Return true if loop body is a valid scop. (class scop_builder): New. Builds SCoPs for polyhedral optimizatios. (scop_builder): New. Constructor. (static sese_l invalid_sese): sese_l with invalid edges. (get_sese): Get an sese (from a loop) if possible, invalid_sese otherwise. (get_nearest_dom_with_single_entry): Get nearest dominator of a basic_block with single entry. Return NULL if we get to the beginning of a function. (get_nearest_pdom_with_single_exit): Get nearest post-dominator of a basic_block with single exit. Return NULL if we get to the beginning of a function. (print_sese): Pretty-print SESE. (merge_sese): Merge two SESEs if possible and return the new SESE. (build_scop_depth): Start building the SCoP within a loop nest. (build_scop_breadth): Start building the SCoP at a single loop depth. Merge adjacent SESEs if valid. (can_represent_loop_1): Returns true if Graphite can represent loop inside SCoP. Helper for can_represent_loop. (can_represent_loop): Returns true if Graphite can represent LOOP and all its nested loops in SCoP. (loop_is_valid_scop): Returns true if LOOP and all its nests constitute a valid SCoP. (region_has_one_loop): Returns true of a region has only one loop. (add_scop): Add SCoP to the list of valid scops. Removes an already existing scop if it intersects with or subsumed by this one. (harmful_stmt_in_region): Returns true if SCoP has any statment which cannot be represented by Graphite. (subsumes): Returns true of SCoP S1 subsumes SCoP S2. (remove_subscops): Remove any SCoP from the list of already found SCoPs, if subsumed by S1. (intersects): Return true if region bounded by SCoPs S1 and S2 intersect. (remove_intersecting_scops): Remove any SCoP which intersects with S1. * graphite.c (print_graphite_scop_statistics): (print_graphite_statistics): Print SCoP info while debugging. (graphite_initialize): Early exit in case number of loops in a function is less than PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION or basic blocks are more than PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION. (graphite_finalize): * params.def: Add PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION. * sese.h (sese_loop_depth): Remove unnecessary gcc_assert. (recompute_all_dominators): Recalculate POST_DOMINATORS. * tree-cfg.c (print_loops): Print the function name while printing loops. gcc/testsuite/ChangeLog: 2015-09-27 Aditya Kumar Sebastian Pop * gcc.dg/graphite/block-1.c: Modified to match the pattern. * gcc.dg/graphite/block-3.c: Same. * gcc.dg/graphite/block-4.c: Same. * gcc.dg/graphite/block-5.c: Same. * gcc.dg/graphite/block-6.c: Same. * gcc.dg/graphite/block-7.c: Same. * gcc.dg/graphite/block-8.c: Same. * gcc.dg/graphite/block-pr47654.c: Same. * gcc.dg/graphite/interchange-0.c: Same. * gcc.dg/graphite/interchange-1.c: Same. * gcc.dg/graphite/interchange-10.c: Same. * gcc.dg/graphite/interchange-11.c: Same. * gcc.dg/graphite/interchange-12.c: Same. * gcc.dg/graphite/interchange-13.c: Same. * gcc.dg/graphite/interchange-14.c: Same. * gcc.dg/graphite/interchange-15.c: Same. * gcc.dg/graphite/interchange-3.c: Same. * gcc.dg/graphite/interchange-4.c: Same. * gcc.dg/graphite/interchange-5.c: Same. * gcc.dg/graphite/interchange-6.c: Same. * gcc.dg/graphite/interchange-7.c: Same. * gcc.dg/graphite/interchange-8.c: Same. * gcc.dg/graphite/interchange-9.c: Same. * gcc.dg/graphite/interchange-mvt.c: Same. * gcc.dg/graphite/pr35356-1.c (foo): Same. * gcc.dg/graphite/pr35356-3.c: Same. * gcc.dg/graphite/pr37485.c: Same. * gcc/testsuite/gcc.dg/graphite/run-id-pr67700-1.c: New test case. * gcc.dg/graphite/scop-1.c (int toto): Modified to match the pattern. * gcc.dg/graphite/scop-11.c: Same. * gcc.dg/graphite/scop-5.c: Same. * gcc.dg/graphite/uns-block-1.c: Same. * gcc.dg/graphite/uns-interchange-9.c: Same. * gfortran.dg/graphite/block-1.f90: Same. * gfortran.dg/graphite/interchange-3.f90: Same. * gfortran.dg/graphite/pr14741.f90: Same. From-SVN: r228215 --- gcc/ChangeLog | 90 +- gcc/graphite-optimize-isl.c | 2 +- gcc/graphite-scop-detection.c | 1527 +++++++---------- gcc/graphite.c | 46 +- gcc/params.def | 7 + gcc/sese.h | 8 +- gcc/testsuite/ChangeLog | 41 + gcc/testsuite/gcc.dg/graphite/block-1.c | 2 +- gcc/testsuite/gcc.dg/graphite/block-3.c | 2 +- gcc/testsuite/gcc.dg/graphite/block-4.c | 2 +- gcc/testsuite/gcc.dg/graphite/block-5.c | 2 +- gcc/testsuite/gcc.dg/graphite/block-6.c | 2 +- gcc/testsuite/gcc.dg/graphite/block-7.c | 2 +- gcc/testsuite/gcc.dg/graphite/block-8.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-1.c | 2 +- .../gcc.dg/graphite/interchange-10.c | 2 +- .../gcc.dg/graphite/interchange-11.c | 2 +- .../gcc.dg/graphite/interchange-12.c | 2 +- .../gcc.dg/graphite/interchange-13.c | 2 +- .../gcc.dg/graphite/interchange-14.c | 2 +- .../gcc.dg/graphite/interchange-15.c | 2 +- gcc/testsuite/gcc.dg/graphite/interchange-3.c | 2 +- gcc/testsuite/gcc.dg/graphite/interchange-4.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-7.c | 2 +- gcc/testsuite/gcc.dg/graphite/interchange-8.c | 2 +- gcc/testsuite/gcc.dg/graphite/interchange-9.c | 2 +- .../gcc.dg/graphite/interchange-mvt.c | 2 +- gcc/testsuite/gcc.dg/graphite/pr35356-1.c | 10 +- gcc/testsuite/gcc.dg/graphite/pr35356-3.c | 2 +- gcc/testsuite/gcc.dg/graphite/pr37485.c | 4 +- .../gcc.dg/graphite/run-id-pr67700-1.c | 48 + gcc/testsuite/gcc.dg/graphite/scop-1.c | 6 +- gcc/testsuite/gcc.dg/graphite/scop-11.c | 26 +- gcc/testsuite/gcc.dg/graphite/scop-5.c | 2 +- gcc/testsuite/gcc.dg/graphite/uns-block-1.c | 2 +- .../gcc.dg/graphite/uns-interchange-9.c | 2 +- .../gfortran.dg/graphite/block-1.f90 | 4 +- gcc/testsuite/gfortran.dg/graphite/block-2.f | 3 +- .../gfortran.dg/graphite/interchange-3.f90 | 2 +- .../gfortran.dg/graphite/pr14741.f90 | 3 +- gcc/tree-cfg.c | 1 + 45 files changed, 905 insertions(+), 979 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/graphite/run-id-pr67700-1.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index b7721444a16..ccfd4a8252f 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,89 @@ +2015-09-28 Aditya Kumar + Sebastian Pop + + * graphite-optimize-isl.c (optimize_isl): Use ISL_SCHEDULE_FUSE_MAX. + * graphite-scop-detection.c (struct sese_l): New type. + (get_entry_bb): API for getting entry bb of SESE. + (get_exit_bb): API for getting exit bb of SESE. + (class debug_printer): New type. Simple printer in debug mode. + (trivially_empty_bb_p): New. Return true when BB is empty or + contains only debug instructions. + (graphite_can_represent_expr): Call scalar_evoution_in_region + instead of analyze_scalar_evolution. Pass in scop instead of only + the scop entry. + (stmt_has_simple_data_refs_p): Pass in scop instead of only the + scop entry. + (stmt_simple_for_scop_p): Same. + (harmful_stmt_in_bb): Same. + (graphite_can_represent_loop): Deleted. + (struct scopdet_info): Deleted. + (scopdet_basic_block_info): Deleted. + (build_scops_1): Deleted. + (bb_in_sd_region): Deleted. + (find_single_entry_edge): Deleted. + (find_single_exit_edge): Deleted. + (create_single_entry_edge): Deleted. + (sd_region_without_exit): Deleted. + (create_single_exit_edge): Deleted. + (unmark_exit_edges): Deleted. + (mark_exit_edges): Deleted. + (create_sese_edges): Deleted. + (build_graphite_scops): Deleted. + (canonicalize_loop_closed_ssa): Recompute all dominators at the + end. + (build_scops): Use the new scop_builder to build scops. + (dot_all_scops_1): Use the new pretty printer. Print loop father + as well. + (loop_body_is_valid_scop): New. Return true if loop body is a + valid scop. + (class scop_builder): New. Builds SCoPs for polyhedral + optimizations. + (scop_builder): New constructor. + (static sese_l invalid_sese): sese_l with invalid edges. + (get_sese): Get an sese (from a loop) if possible, invalid_sese + otherwise. + (get_nearest_dom_with_single_entry): Get nearest dominator of a + basic_block with single entry. Return NULL if we get to the + beginning of a function. + (get_nearest_pdom_with_single_exit): Get nearest post-dominator of + a basic_block with single exit. Return NULL if we get to the + beginning of a function. + (print_sese): Pretty-print SESE. + (merge_sese): Merge two SESEs if possible and return the new SESE. + (build_scop_depth): Start building the SCoP within a loop nest. + (build_scop_breadth): Start building the SCoP at a single loop + depth. Merge adjacent SESEs if valid. + (can_represent_loop_1): Returns true if Graphite can represent + loop inside SCoP. Helper for can_represent_loop. + (can_represent_loop): Returns true if Graphite can represent LOOP + and all its nested loops in SCoP. + (loop_is_valid_scop): Returns true if LOOP and all its nests + constitute a valid SCoP. + (region_has_one_loop): Returns true of a region has only one loop. + (add_scop): Add SCoP to the list of valid scops. Removes an + already existing scop if it intersects with or subsumed by this + one. + (harmful_stmt_in_region): Returns true if SCoP has any statment + which cannot be represented by Graphite. + (subsumes): Returns true of SCoP S1 subsumes SCoP S2. + (remove_subscops): Remove any SCoP from the list of already found + SCoPs, if subsumed by S1. + (intersects): Return true if region bounded by SCoPs S1 and S2 + intersect. + (remove_intersecting_scops): Remove any SCoP which intersects with + S1. + * graphite.c (print_graphite_scop_statistics): + (print_graphite_statistics): Print SCoP info while debugging. + (graphite_initialize): Early exit in case number of loops in a + function is less than PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION or + basic blocks are more than PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION. + (graphite_finalize): + * params.def: Add PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION. + * sese.h (sese_loop_depth): Remove unnecessary gcc_assert. + (recompute_all_dominators): Recalculate POST_DOMINATORS. + * tree-cfg.c (print_loops): Print the function name while printing + loops. + 2015-09-28 Aditya Kumar Sebastian Pop @@ -11,8 +97,8 @@ 2015-09-28 David Wohlferd - * doc/extend.texi (Asm Labels): Break out text for data vs - functions. + * doc/extend.texi (Asm Labels): Break out text for data vs + functions. 2015-09-28 Jiong Wang diff --git a/gcc/graphite-optimize-isl.c b/gcc/graphite-optimize-isl.c index bd13978f42d..4b821741afb 100644 --- a/gcc/graphite-optimize-isl.c +++ b/gcc/graphite-optimize-isl.c @@ -329,7 +329,7 @@ optimize_isl (scop_p scop) #ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS isl_options_set_schedule_serialize_sccs (scop->ctx, 1); #else - isl_options_set_schedule_fuse (scop->ctx, ISL_SCHEDULE_FUSE_MIN); + isl_options_set_schedule_fuse (scop->ctx, ISL_SCHEDULE_FUSE_MAX); #endif #ifdef HAVE_ISL_SCHED_CONSTRAINTS_COMPUTE_SCHEDULE diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c index 7c0dc21b01b..a498ddcdbfc 100644 --- a/gcc/graphite-scop-detection.c +++ b/gcc/graphite-scop-detection.c @@ -34,6 +34,7 @@ along with GCC; see the file COPYING3. If not see #include "coretypes.h" #include "backend.h" #include "cfghooks.h" +#include "params.h" #include "tree.h" #include "gimple.h" #include "ssa.h" @@ -53,108 +54,83 @@ along with GCC; see the file COPYING3. If not see #include "graphite-scop-detection.h" #include "gimple-pretty-print.h" -/* Forward declarations. */ -static void make_close_phi_nodes_unique (basic_block); +/* Lightweight representation of sese for scop detection. + TODO: Make all this as a constant_edge. */ +struct sese_l +{ + sese_l (edge e, edge x) + : entry (e), exit (x) + { } -/* The type of the analyzed basic block. */ + operator bool () const + { + return entry && exit; + } -enum gbb_type { - GBB_UNKNOWN, - GBB_LOOP_SING_EXIT_HEADER, - GBB_LOOP_MULT_EXIT_HEADER, - GBB_LOOP_EXIT, - GBB_COND_HEADER, - GBB_SIMPLE, - GBB_LAST + edge entry; + edge exit; }; -/* Detect the type of BB. Loop headers are only marked, if they are - new. This means their loop_father is different to LAST_LOOP. - Otherwise they are treated like any other bb and their type can be - any other type. */ - -static gbb_type -get_bb_type (basic_block bb, struct loop *last_loop) +/* APIs for getting entry/exit of an sese. */ +static basic_block +get_entry_bb (edge e) { - vec dom; - int nb_dom; - struct loop *loop = bb->loop_father; - - /* Check, if we entry into a new loop. */ - if (loop != last_loop) - { - if (single_exit (loop) != NULL) - return GBB_LOOP_SING_EXIT_HEADER; - else if (loop->num != 0) - return GBB_LOOP_MULT_EXIT_HEADER; - else - return GBB_COND_HEADER; - } - - dom = get_dominated_by (CDI_DOMINATORS, bb); - nb_dom = dom.length (); - dom.release (); - - if (nb_dom == 0) - return GBB_LAST; - - if (nb_dom == 1 && single_succ_p (bb)) - return GBB_SIMPLE; - - return GBB_COND_HEADER; + return e->dest; } -/* A SCoP detection region, defined using bbs as borders. - - All control flow touching this region, comes in passing basic_block - ENTRY and leaves passing basic_block EXIT. By using bbs instead of - edges for the borders we are able to represent also regions that do - not have a single entry or exit edge. - - But as they have a single entry basic_block and a single exit - basic_block, we are able to generate for every sd_region a single - entry and exit edge. - - 1 2 - \ / - 3 <- entry - | - 4 - / \ This region contains: {3, 4, 5, 6, 7, 8} - 5 6 - | | - 7 8 - \ / - 9 <- exit */ - +static basic_block +get_exit_bb (edge e) +{ + return e->src; +} -struct sd_region +class debug_printer { - /* The entry bb dominates all bbs in the sd_region. It is part of - the region. */ - basic_block entry; +private: + FILE *dump_file; +public: + void set_dump_file (FILE *f) + { + gcc_assert (f); + dump_file = f; + } - /* The exit bb postdominates all bbs in the sd_region, but is not - part of the region. */ - basic_block exit; -}; + friend debug_printer &operator<<(debug_printer &output, int i) + { + fprintf (output.dump_file, "%d", i); + return output; + } + friend debug_printer &operator<<(debug_printer &output, const char *s) + { + fprintf (output.dump_file, "%s", s); + return output; + } +} dp; +#define DEBUG_PRINT(args) do \ + { \ + if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \ + } while (0); -/* Moves the scops from SOURCE to TARGET and clean up SOURCE. */ +/* Return true if BB is empty, contains only DEBUG_INSNs. */ -static void -move_sd_regions (vec *source, vec *target) +static bool +trivially_empty_bb_p (basic_block bb) { - sd_region *s; - int i; + gimple_stmt_iterator gsi; - FOR_EACH_VEC_ELT (*source, i, s) - target->safe_push (*s); + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + if (gimple_code (gsi_stmt (gsi)) != GIMPLE_DEBUG) + return false; - source->release (); + return true; } + +/* Forward declarations. */ +static void make_close_phi_nodes_unique (basic_block); + /* Something like "n * m" is not allowed. */ static bool @@ -267,36 +243,34 @@ graphite_can_represent_scev (tree scev) /* Return true when EXPR can be represented in the polyhedral model. - This means an expression can be represented, if it is linear with - respect to the loops and the strides are non parametric. - LOOP is the place where the expr will be evaluated. SCOP_ENTRY defines the - entry of the region we analyse. */ + This means an expression can be represented, if it is linear with respect to + the loops and the strides are non parametric. LOOP is the place where the + expr will be evaluated. SCOP defines the region we analyse. */ static bool -graphite_can_represent_expr (basic_block scop_entry, loop_p loop, - tree expr) +graphite_can_represent_expr (sese_l scop, loop_p loop, tree expr) { - tree scev = analyze_scalar_evolution (loop, expr); - - scev = instantiate_scev (scop_entry, loop, scev); - + sese region = new_sese (scop.entry, scop.exit); + tree scev = scalar_evolution_in_region (region, loop, expr); + free_sese (region); return graphite_can_represent_scev (scev); } -/* Return true if the data references of STMT can be represented by - Graphite. */ +/* Return true if the data references of STMT can be represented by Graphite. + We try to analyze the data references in a loop contained in the SCOP. */ static bool -stmt_has_simple_data_refs_p (loop_p outermost_loop ATTRIBUTE_UNUSED, - gimple *stmt) +stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt) { data_reference_p dr; int j; bool res = true; vec drs = vNULL; loop_p outer; + loop_p loop_around_scop = get_entry_bb (scop.entry)->loop_father; - for (outer = loop_containing_stmt (stmt); outer; outer = loop_outer (outer)) + for (outer = loop_containing_stmt (stmt); outer && outer != loop_around_scop; + outer = loop_outer (outer)) { graphite_find_data_references_in_stmt (outer, loop_containing_stmt (stmt), @@ -330,19 +304,18 @@ stmt_has_simple_data_refs_p (loop_p outermost_loop ATTRIBUTE_UNUSED, return res; } -/* Return true only when STMT is simple enough for being handled by - Graphite. This depends on SCOP_ENTRY, as the parameters are - initialized relatively to this basic block, the linear functions - are initialized to OUTERMOST_LOOP and BB is the place where we try - to evaluate the STMT. */ +/* Return true only when STMT is simple enough for being handled by Graphite. + This depends on SCOP, as the parameters are initialized relatively to + this basic block, the linear functions are initialized based on the outermost + loop containing STMT inside the SCOP. BB is the place where we try to + evaluate the STMT. */ static bool -stmt_simple_for_scop_p (basic_block scop_entry, loop_p outermost_loop, - gimple *stmt, basic_block bb) +stmt_simple_for_scop_p (sese_l scop, gimple *stmt, basic_block bb) { loop_p loop = bb->loop_father; - gcc_assert (scop_entry); + gcc_assert (scop); /* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects. Calls have side-effects, except those to const or pure @@ -352,28 +325,20 @@ stmt_simple_for_scop_p (basic_block scop_entry, loop_p outermost_loop, && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE))) || (gimple_code (stmt) == GIMPLE_ASM)) { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "[scop-detection-fail] "); - fprintf (dump_file, "Graphite cannot handle this stmt:\n"); - print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS); - } - + DEBUG_PRINT (dp << "[scop-detection-fail] " + << "Graphite cannot handle this stmt:\n"; + print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS)); return false; } if (is_gimple_debug (stmt)) return true; - if (!stmt_has_simple_data_refs_p (outermost_loop, stmt)) + if (!stmt_has_simple_data_refs_p (scop, stmt)) { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "[scop-detection-fail] "); - fprintf (dump_file, "Graphite cannot handle data-refs in stmt:\n"); - print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS); - } - + DEBUG_PRINT (dp << "[scop-detection-fail] " + << "Graphite cannot handle data-refs in stmt:\n"; + print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS);); return false; } @@ -395,30 +360,22 @@ stmt_simple_for_scop_p (basic_block scop_entry, loop_p outermost_loop, || code == EQ_EXPR || code == NE_EXPR)) { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "[scop-detection-fail] "); - fprintf (dump_file, "Graphite cannot handle cond stmt:\n"); - print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS); - } - + DEBUG_PRINT (dp << "[scop-detection-fail] " + << "Graphite cannot handle cond stmt:\n"; + print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS)); return false; } for (unsigned i = 0; i < 2; ++i) { tree op = gimple_op (stmt, i); - if (!graphite_can_represent_expr (scop_entry, loop, op) + if (!graphite_can_represent_expr (scop, loop, op) /* We can only constrain on integer type. */ || (TREE_CODE (TREE_TYPE (op)) != INTEGER_TYPE)) { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "[scop-detection-fail] "); - fprintf (dump_file, "Graphite cannot represent stmt:\n"); - print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS); - } - + DEBUG_PRINT (dp << "[scop-detection-fail] " + << "Graphite cannot represent stmt:\n"; + print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS)); return false; } } @@ -432,764 +389,30 @@ stmt_simple_for_scop_p (basic_block scop_entry, loop_p outermost_loop, default: /* These nodes cut a new scope. */ - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "[scop-detection-fail] "); - fprintf (dump_file, "Gimple stmt not handled in Graphite:\n"); - print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS); - } + DEBUG_PRINT (dp << "[scop-detection-fail] " + << "Gimple stmt not handled in Graphite:\n"; + print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS)); return false; } return false; } -/* Returns the statement of BB that contains a harmful operation: that +/* Return true when BB contains a harmful operation for a scop: that can be a function call with side effects, the induction variables - are not linear with respect to SCOP_ENTRY, etc. The current open - scop should end before this statement. The evaluation is limited using - OUTERMOST_LOOP as outermost loop that may change. */ + are not linear with respect to SCOP, etc. The current open + scop should end before this statement. */ -static gimple * -harmful_stmt_in_bb (basic_block scop_entry, loop_p outer_loop, basic_block bb) +static bool +harmful_stmt_in_bb (sese_l scop, basic_block bb) { gimple_stmt_iterator gsi; for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) - if (!stmt_simple_for_scop_p (scop_entry, outer_loop, gsi_stmt (gsi), bb)) - return gsi_stmt (gsi); - - return NULL; -} - -/* Return true if LOOP can be represented in the polyhedral - representation. This is evaluated taking SCOP_ENTRY and - OUTERMOST_LOOP in mind. */ - -static bool -graphite_can_represent_loop (basic_block scop_entry, loop_p loop) -{ - tree niter; - struct tree_niter_desc niter_desc; - - if (!loop_nest_has_data_refs (loop)) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "[scop-detection-fail] "); - fprintf (dump_file, "Loop %d does not have any data reference.\n", - loop->num); - } - return false; - } - - /* FIXME: For the moment, graphite cannot be used on loops that - iterate using induction variables that wrap. */ - - return number_of_iterations_exit (loop, single_exit (loop), &niter_desc, false) - && niter_desc.control.no_overflow - && (niter = number_of_latch_executions (loop)) - && !chrec_contains_undetermined (niter) - && graphite_can_represent_expr (scop_entry, loop, niter); -} - -/* Store information needed by scopdet_* functions. */ - -struct scopdet_info -{ - /* Exit of the open scop would stop if the current BB is harmful. */ - basic_block exit; - - /* Where the next scop would start if the current BB is harmful. */ - basic_block next; - - /* The bb or one of its children contains open loop exits. That means - loop exit nodes that are not surrounded by a loop dominated by bb. */ - bool exits; - - /* The bb or one of its children contains only structures we can handle. */ - bool difficult; -}; - -static struct scopdet_info build_scops_1 (basic_block, loop_p, - vec *, loop_p); - -/* Calculates BB infos. If bb is difficult we add valid SCoPs dominated by BB - to SCOPS. TYPE is the gbb_type of BB. */ - -static struct scopdet_info -scopdet_basic_block_info (basic_block bb, loop_p outermost_loop, - vec *scops, gbb_type type) -{ - loop_p loop = bb->loop_father; - struct scopdet_info result; - gimple *stmt; - - /* XXX: ENTRY_BLOCK_PTR could be optimized in later steps. */ - basic_block entry_block = ENTRY_BLOCK_PTR_FOR_FN (cfun); - stmt = harmful_stmt_in_bb (entry_block, outermost_loop, bb); - result.difficult = (stmt != NULL); - result.exit = NULL; - - switch (type) - { - case GBB_LAST: - result.next = NULL; - result.exits = false; - - /* Mark bbs terminating a SESE region difficult, if they start - a condition or if the block it exits to cannot be split - with make_forwarder_block. */ - if (!single_succ_p (bb) - || bb_has_abnormal_pred (single_succ (bb))) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "[scop-detection-fail] "); - fprintf (dump_file, "BB %d cannot be part of a scop.\n", - bb->index); - } - - result.difficult = true; - } - else - result.exit = single_succ (bb); - - break; - - case GBB_SIMPLE: - result.next = single_succ (bb); - result.exits = false; - result.exit = single_succ (bb); - break; - - case GBB_LOOP_SING_EXIT_HEADER: - { - auto_vec regions; - struct scopdet_info sinfo; - edge exit_e = single_exit (loop); - - sinfo = build_scops_1 (bb, outermost_loop, ®ions, loop); - - if (!graphite_can_represent_loop (entry_block, loop)) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "[scop-detection-fail] "); - fprintf (dump_file, "Graphite cannot represent loop %d.\n", - loop->num); - } - result.difficult = true; - } - - result.difficult |= sinfo.difficult; - - /* Try again with another loop level. */ - if (result.difficult - && loop_depth (outermost_loop) + 1 == loop_depth (loop)) - { - outermost_loop = loop; - - regions.release (); - regions.create (3); - - sinfo = scopdet_basic_block_info (bb, outermost_loop, scops, type); - - result = sinfo; - result.difficult = true; - - if (sinfo.difficult) - move_sd_regions (®ions, scops); - else - { - sd_region open_scop; - open_scop.entry = bb; - open_scop.exit = exit_e->dest; - scops->safe_push (open_scop); - regions.release (); - } - } - else - { - result.exit = exit_e->dest; - result.next = exit_e->dest; - - /* If we do not dominate result.next, remove it. It's either - the exit block, or another bb dominates it and will - call the scop detection for this bb. */ - if (!dominated_by_p (CDI_DOMINATORS, result.next, bb)) - result.next = NULL; - - if (exit_e->src->loop_father != loop) - result.next = NULL; - - result.exits = false; - - if (result.difficult) - move_sd_regions (®ions, scops); - else - regions.release (); - } - - break; - } - - case GBB_LOOP_MULT_EXIT_HEADER: - { - /* XXX: For now we just do not join loops with multiple exits. If the - exits lead to the same bb it may be possible to join the loop. */ - auto_vec regions; - vec exits = get_loop_exit_edges (loop); - edge e; - int i; - build_scops_1 (bb, loop, ®ions, loop); - - /* Scan the code dominated by this loop. This means all bbs, that are - are dominated by a bb in this loop, but are not part of this loop. - - The easiest case: - - The loop exit destination is dominated by the exit sources. - - TODO: We miss here the more complex cases: - - The exit destinations are dominated by another bb inside - the loop. - - The loop dominates bbs, that are not exit destinations. */ - FOR_EACH_VEC_ELT (exits, i, e) - if (e->src->loop_father == loop - && dominated_by_p (CDI_DOMINATORS, e->dest, e->src)) - { - if (loop_outer (outermost_loop)) - outermost_loop = loop_outer (outermost_loop); - - /* Pass loop_outer to recognize e->dest as loop header in - build_scops_1. */ - if (e->dest->loop_father->header == e->dest) - build_scops_1 (e->dest, outermost_loop, ®ions, - loop_outer (e->dest->loop_father)); - else - build_scops_1 (e->dest, outermost_loop, ®ions, - e->dest->loop_father); - } - - result.next = NULL; - result.exit = NULL; - result.difficult = true; - result.exits = false; - move_sd_regions (®ions, scops); - exits.release (); - break; - } - case GBB_COND_HEADER: - { - auto_vec regions; - struct scopdet_info sinfo; - vec dominated; - int i; - basic_block dom_bb; - basic_block last_exit = NULL; - edge e; - result.exits = false; - - /* First check the successors of BB, and check if it is - possible to join the different branches. */ - FOR_EACH_VEC_SAFE_ELT (bb->succs, i, e) - { - /* Ignore loop exits. They will be handled after the loop - body. */ - if (loop_exits_to_bb_p (loop, e->dest)) - { - result.exits = true; - continue; - } - - /* Do not follow edges that lead to the end of the - conditions block. For example, in - - | 0 - | /|\ - | 1 2 | - | | | | - | 3 4 | - | \|/ - | 6 - - the edge from 0 => 6. Only check if all paths lead to - the same node 6. */ - - if (!single_pred_p (e->dest)) - { - /* Check, if edge leads directly to the end of this - condition. */ - if (!last_exit) - last_exit = e->dest; - - if (e->dest != last_exit) - result.difficult = true; - - continue; - } - - if (!dominated_by_p (CDI_DOMINATORS, e->dest, bb)) - { - result.difficult = true; - continue; - } - - sinfo = build_scops_1 (e->dest, outermost_loop, ®ions, loop); - - result.exits |= sinfo.exits; - result.difficult |= sinfo.difficult; - - /* Checks, if all branches end at the same point. - If that is true, the condition stays joinable. - Have a look at the example above. */ - if (sinfo.exit) - { - if (!last_exit) - last_exit = sinfo.exit; - - if (sinfo.exit != last_exit) - result.difficult = true; - } - else - result.difficult = true; - } - - if (!last_exit) - result.difficult = true; - - /* Join the branches of the condition if possible. */ - if (!result.exits && !result.difficult) - { - /* Only return a next pointer if we dominate this pointer. - Otherwise it will be handled by the bb dominating it. */ - if (dominated_by_p (CDI_DOMINATORS, last_exit, bb) - && last_exit != bb) - result.next = last_exit; - else - result.next = NULL; - - result.exit = last_exit; - - regions.release (); - break; - } - - /* Scan remaining bbs dominated by BB. */ - dominated = get_dominated_by (CDI_DOMINATORS, bb); - - FOR_EACH_VEC_ELT (dominated, i, dom_bb) - { - /* Ignore loop exits: they will be handled after the loop body. */ - if (loop_depth (find_common_loop (loop, dom_bb->loop_father)) - < loop_depth (loop)) - { - result.exits = true; - continue; - } - - /* Ignore the bbs processed above. */ - if (single_pred_p (dom_bb) && single_pred (dom_bb) == bb) - continue; - - if (loop_depth (loop) > loop_depth (dom_bb->loop_father)) - sinfo = build_scops_1 (dom_bb, outermost_loop, ®ions, - loop_outer (loop)); - else - sinfo = build_scops_1 (dom_bb, outermost_loop, ®ions, loop); - - result.exits |= sinfo.exits; - result.difficult = true; - result.exit = NULL; - } - - dominated.release (); - - result.next = NULL; - move_sd_regions (®ions, scops); - - break; - } - - default: - gcc_unreachable (); - } - - return result; -} - -/* Starting from CURRENT we walk the dominance tree and add new sd_regions to - SCOPS. The analyse if a sd_region can be handled is based on the value - of OUTERMOST_LOOP. Only loops inside OUTERMOST loops may change. LOOP - is the loop in which CURRENT is handled. - - TODO: These functions got a little bit big. They definitely should be cleaned - up. */ - -static struct scopdet_info -build_scops_1 (basic_block current, loop_p outermost_loop, - vec *scops, loop_p loop) -{ - bool in_scop = false; - sd_region open_scop; - struct scopdet_info sinfo; - - /* Initialize result. */ - struct scopdet_info result; - result.exits = false; - result.difficult = false; - result.next = NULL; - result.exit = NULL; - open_scop.entry = NULL; - open_scop.exit = NULL; - sinfo.exit = NULL; - - /* Loop over the dominance tree. If we meet a difficult bb, close - the current SCoP. Loop and condition header start a new layer, - and can only be added if all bbs in deeper layers are simple. */ - while (current != NULL) - { - sinfo = scopdet_basic_block_info (current, outermost_loop, scops, - get_bb_type (current, loop)); - - if (!in_scop && !(sinfo.exits || sinfo.difficult)) - { - open_scop.entry = current; - open_scop.exit = NULL; - in_scop = true; - } - else if (in_scop && (sinfo.exits || sinfo.difficult)) - { - open_scop.exit = current; - scops->safe_push (open_scop); - in_scop = false; - } - - result.difficult |= sinfo.difficult; - result.exits |= sinfo.exits; - - current = sinfo.next; - } - - /* Try to close open_scop, if we are still in an open SCoP. */ - if (in_scop) - { - open_scop.exit = sinfo.exit; - gcc_assert (open_scop.exit); - if (open_scop.entry != open_scop.exit) - scops->safe_push (open_scop); - else - { - sinfo.difficult = true; - sinfo.exits = false; - sinfo.exit = NULL; - } - } - - result.exit = sinfo.exit; - return result; -} - -/* Checks if a bb is contained in REGION. */ - -static bool -bb_in_sd_region (basic_block bb, sd_region *region) -{ - return bb_in_region (bb, region->entry, region->exit); -} - -/* Returns the single entry edge of REGION, if it does not exits NULL. */ - -static edge -find_single_entry_edge (sd_region *region) -{ - edge e; - edge_iterator ei; - edge entry = NULL; - - FOR_EACH_EDGE (e, ei, region->entry->preds) - if (!bb_in_sd_region (e->src, region)) - { - if (entry) - { - entry = NULL; - break; - } - - else - entry = e; - } - - return entry; -} - -/* Returns the single exit edge of REGION, if it does not exits NULL. */ - -static edge -find_single_exit_edge (sd_region *region) -{ - edge e; - edge_iterator ei; - edge exit = NULL; - - FOR_EACH_EDGE (e, ei, region->exit->preds) - if (bb_in_sd_region (e->src, region)) - { - if (exit) - { - exit = NULL; - break; - } - - else - exit = e; - } - - return exit; -} - -/* Create a single entry edge for REGION. */ - -static void -create_single_entry_edge (sd_region *region) -{ - if (find_single_entry_edge (region)) - return; - - /* There are multiple predecessors for bb_3 - - | 1 2 - | | / - | |/ - | 3 <- entry - | |\ - | | | - | 4 ^ - | | | - | |/ - | 5 - - There are two edges (1->3, 2->3), that point from outside into the region, - and another one (5->3), a loop latch, lead to bb_3. - - We split bb_3. - - | 1 2 - | | / - | |/ - |3.0 - | |\ (3.0 -> 3.1) = single entry edge - |3.1 | <- entry - | | | - | | | - | 4 ^ - | | | - | |/ - | 5 - - If the loop is part of the SCoP, we have to redirect the loop latches. - - | 1 2 - | | / - | |/ - |3.0 - | | (3.0 -> 3.1) = entry edge - |3.1 <- entry - | |\ - | | | - | 4 ^ - | | | - | |/ - | 5 */ - - if (region->entry->loop_father->header != region->entry - || dominated_by_p (CDI_DOMINATORS, - loop_latch_edge (region->entry->loop_father)->src, - region->exit)) - { - edge forwarder = split_block_after_labels (region->entry); - region->entry = forwarder->dest; - } - else - /* This case is never executed, as the loop headers seem always to have a - single edge pointing from outside into the loop. */ - gcc_unreachable (); - - gcc_checking_assert (find_single_entry_edge (region)); -} - -/* Check if the sd_region, mentioned in EDGE, has no exit bb. */ - -static bool -sd_region_without_exit (edge e) -{ - sd_region *r = (sd_region *) e->aux; - - if (r) - return r->exit == NULL; - else - return false; -} - -/* Create a single exit edge for REGION. */ - -static void -create_single_exit_edge (sd_region *region) -{ - edge e; - edge_iterator ei; - edge forwarder = NULL; - basic_block exit; - - /* We create a forwarder bb (5) for all edges leaving this region - (3->5, 4->5). All other edges leading to the same bb, are moved - to a new bb (6). If these edges where part of another region (2->5) - we update the region->exit pointer, of this region. - - To identify which edge belongs to which region we depend on the e->aux - pointer in every edge. It points to the region of the edge or to NULL, - if the edge is not part of any region. - - 1 2 3 4 1->5 no region, 2->5 region->exit = 5, - \| |/ 3->5 region->exit = NULL, 4->5 region->exit = NULL - 5 <- exit - - changes to - - 1 2 3 4 1->6 no region, 2->6 region->exit = 6, - | | \/ 3->5 no region, 4->5 no region, - | | 5 - \| / 5->6 region->exit = 6 - 6 - - Now there is only a single exit edge (5->6). */ - exit = region->exit; - region->exit = NULL; - forwarder = make_forwarder_block (exit, &sd_region_without_exit, NULL); - - /* Unmark the edges, that are no longer exit edges. */ - FOR_EACH_EDGE (e, ei, forwarder->src->preds) - if (e->aux) - e->aux = NULL; - - /* Mark the new exit edge. */ - single_succ_edge (forwarder->src)->aux = region; - - /* Update the exit bb of all regions, where exit edges lead to - forwarder->dest. */ - FOR_EACH_EDGE (e, ei, forwarder->dest->preds) - if (e->aux) - ((sd_region *) e->aux)->exit = forwarder->dest; - - gcc_checking_assert (find_single_exit_edge (region)); -} - -/* Unmark the exit edges of all REGIONS. - See comment in "create_single_exit_edge". */ - -static void -unmark_exit_edges (vec regions) -{ - int i; - sd_region *s; - edge e; - edge_iterator ei; - - FOR_EACH_VEC_ELT (regions, i, s) - FOR_EACH_EDGE (e, ei, s->exit->preds) - e->aux = NULL; -} - - -/* Mark the exit edges of all REGIONS. - See comment in "create_single_exit_edge". */ - -static void -mark_exit_edges (vec regions) -{ - int i; - sd_region *s; - edge e; - edge_iterator ei; - - FOR_EACH_VEC_ELT (regions, i, s) - FOR_EACH_EDGE (e, ei, s->exit->preds) - if (bb_in_sd_region (e->src, s)) - e->aux = s; -} - -/* Create for all scop regions a single entry and a single exit edge. */ - -static void -create_sese_edges (vec regions) -{ - int i; - sd_region *s; - - FOR_EACH_VEC_ELT (regions, i, s) - create_single_entry_edge (s); - - mark_exit_edges (regions); - - FOR_EACH_VEC_ELT (regions, i, s) - /* Don't handle multiple edges exiting the function. */ - if (!find_single_exit_edge (s) - && s->exit != EXIT_BLOCK_PTR_FOR_FN (cfun)) - create_single_exit_edge (s); - - unmark_exit_edges (regions); - - calculate_dominance_info (CDI_DOMINATORS); - fix_loop_structure (NULL); - -#ifdef ENABLE_CHECKING - verify_loop_structure (); - verify_ssa (false, true); -#endif -} - -/* Create graphite SCoPs from an array of scop detection REGIONS. */ - -static void -build_graphite_scops (vec regions, - vec *scops) -{ - int i; - sd_region *s; - - FOR_EACH_VEC_ELT (regions, i, s) - { - edge entry = find_single_entry_edge (s); - edge exit = find_single_exit_edge (s); - scop_p scop; - - if (!exit) - continue; - - sese sese_reg = new_sese (entry, exit); - scop = new_scop (sese_reg); - - build_sese_loop_nests (sese_reg); - - /* Scops with one or no loops are not interesting. */ - if (SESE_LOOP_NEST (sese_reg).length () > 1) - scops->safe_push (scop); - else if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "Discarded scop: %d loops\n", - SESE_LOOP_NEST (sese_reg).length ()); - - /* Are there overlapping SCoPs? */ -#ifdef ENABLE_CHECKING - { - int j; - sd_region *s2; + if (!stmt_simple_for_scop_p (scop, gsi_stmt (gsi), bb)) + return true; - FOR_EACH_VEC_ELT (regions, j, s2) - if (s != s2) - gcc_assert (!bb_in_sd_region (s->entry, s2)); - } -#endif - } + return false; } /* Returns true when P1 and P2 are close phis with the same @@ -1275,6 +498,7 @@ canonicalize_loop_closed_ssa (loop_p loop) if (single_pred_p (bb)) { e = split_block_after_labels (bb); + DEBUG_PRINT (dp << "\nSplitting bb_" << bb->index); make_close_phi_nodes_unique (e->src); } else @@ -1283,6 +507,9 @@ canonicalize_loop_closed_ssa (loop_p loop) basic_block close = split_edge (e); e = single_succ_edge (close); + DEBUG_PRINT (dp << "\nSplitting edge (" + << e->src->index << "," << e->dest->index + << ")\n"); for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) { @@ -1316,7 +543,7 @@ canonicalize_loop_closed_ssa (loop_p loop) /* The code above does not properly handle changes in the post dominance information (yet). */ - free_dominance_info (CDI_POST_DOMINATORS); + recompute_all_dominators (); } /* Converts the current loop closed SSA form to a canonical form @@ -1360,29 +587,6 @@ canonicalize_loop_closed_ssa_form (void) #endif } -/* Find Static Control Parts (SCoP) in the current function and pushes - them to SCOPS. */ - -void -build_scops (vec *scops) -{ - struct loop *loop = current_loops->tree_root; - auto_vec regions; - - canonicalize_loop_closed_ssa_form (); - build_scops_1 (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)), - ENTRY_BLOCK_PTR_FOR_FN (cfun)->loop_father, - ®ions, loop); - create_sese_edges (regions); - build_graphite_scops (regions, scops); - - regions.release (); - - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, "\nnumber of SCoPs: %d\n", - scops ? scops->length () : 0); -} - /* Pretty print to FILE all the SCoPs in DOT format and mark them with different colors. If there are not enough colors, paint the remaining SCoPs in gray. @@ -1500,6 +704,8 @@ dot_all_scops_1 (FILE *file, vec scops) else fprintf (file, " %d ", bb->index); + fprintf (file, "{lp_%d}", bb->loop_father->num); + if (!bb_in_sese_p (bb,region)) fprintf (file, ")"); @@ -1511,7 +717,8 @@ dot_all_scops_1 (FILE *file, vec scops) if (!part_of_scop) { fprintf (file, " "); - fprintf (file, " %d \n", bb->index); + fprintf (file, " %d {lp_%d} \n", + bb->index, bb->loop_father->num); } fprintf (file, " >, shape=box, style=\"setlinewidth(0)\"]\n"); } @@ -1576,4 +783,512 @@ dot_scop (scop_p scop) #endif } +/* Return true when the body of LOOP has statements that can be represented as a + valid scop. */ + +static bool +loop_body_is_valid_scop (loop_p loop, sese_l scop) +{ + if (!loop_nest_has_data_refs (loop)) + { + DEBUG_PRINT (dp << "[scop-detection-fail] loop_" + << loop->num << "does not have any data reference.\n"); + return false; + } + + basic_block *bbs = get_loop_body (loop); + for (unsigned i = 0; i < loop->num_nodes; i++) + { + basic_block bb = bbs[i]; + + if (harmful_stmt_in_bb (scop, bb)) + return false; + } + free (bbs); + return true; +} + +/* Build the maximal scop containing LOOP(s) and add it to SCOPS. */ + +class scop_builder +{ + public: + scop_builder (vec *s) + : scops (s) + { } + + static sese_l invalid_sese; + + sese_l get_sese (loop_p loop) + { + if (!loop) + return invalid_sese; + + if (!loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)) + return invalid_sese; + edge scop_end = single_exit (loop); + if (!scop_end) + return invalid_sese; + edge scop_begin = loop_preheader_edge (loop); + sese_l s (scop_begin, scop_end); + return s; + } + + static edge + get_nearest_dom_with_single_entry (basic_block dom) + { + if (!dom->preds) + return NULL; + /* If e1->src dominates e2->src then e1->src will also dominate dom. */ + if (dom->preds->length () == 2) + { + edge e1 = (*dom->preds)[0]; + edge e2 = (*dom->preds)[1]; + if (dominated_by_p (CDI_DOMINATORS, e2->src, e1->src)) + return e1; + if (dominated_by_p (CDI_DOMINATORS, e1->src, e2->src)) + return e2; + } + + while (dom->preds->length () != 1) + { + if (dom->preds->length () < 1) + return NULL; + dom = get_immediate_dominator (CDI_DOMINATORS, dom); + if (!dom->preds) + return NULL; + } + return (*dom->preds)[0]; + } + + static edge + get_nearest_pdom_with_single_exit (basic_block dom) + { + if (!dom->succs) + return NULL; + if (dom->succs->length () == 2) + { + edge e1 = (*dom->succs)[0]; + edge e2 = (*dom->succs)[1]; + if (dominated_by_p (CDI_POST_DOMINATORS, e2->dest, e1->dest)) + return e1; + if (dominated_by_p (CDI_POST_DOMINATORS, e1->dest, e2->dest)) + return e2; + } + + while (dom->succs->length () != 1) + { + if (dom->succs->length () < 1) + return NULL; + dom = get_immediate_dominator (CDI_POST_DOMINATORS, dom); + if (!dom->succs) + return NULL; + } + return (*dom->succs)[0]; + } + + /* Print S to FILE. */ + + static void + print_sese (FILE *file, sese_l s) + { + fprintf (file, "(entry_edge (bb_%d, bb_%d), exit_edge (bb_%d, bb_%d))\n", + s.entry->src->index, s.entry->dest->index, + s.exit->src->index, s.exit->dest->index); + } + + /* Merge scops at same loop depth and returns the new sese. + TODO: Free the already allocated sese's first and second, or reuse. + Returns SECOND when first is NULL. SECOND cannot be NULL. + Frees up SECOND and returns a new SESE when merge was successful. + */ + + static sese_l + merge_sese (sese_l first, sese_l second) + { + /* In the trivial case first/second may be NULL. */ + if (!first) + return second; + if (!second) + return first; + + DEBUG_PRINT (dp << "[try-merging-sese] s1: "; + print_sese (dump_file, first); + dp << "[try-merging-sese] s2: "; + print_sese (dump_file, second)); + + /* Assumption: Both the sese's should be at the same loop depth or one scop + should subsume the other like in case of nested loops. */ + + /* Find the common dominators for entry, + and common post-dominators for the exit. */ + basic_block dom = nearest_common_dominator (CDI_DOMINATORS, + get_entry_bb (first.entry), + get_entry_bb (second.entry)); + + + edge entry = get_nearest_dom_with_single_entry (dom); + if (!entry) + return invalid_sese; + + basic_block pdom = nearest_common_dominator (CDI_POST_DOMINATORS, + get_exit_bb (first.exit), + get_exit_bb (second.exit)); + pdom = nearest_common_dominator (CDI_POST_DOMINATORS, dom, pdom); + + edge exit = get_nearest_pdom_with_single_exit (pdom); + if (!exit) + return invalid_sese; + + sese_l combined (entry, exit); + + /* FIXME: We could iterate to find the dom which dominates pdom, and pdom + which post-dominates dom, until it stabilizes. Also, ENTRY->SRC and + EXIT->DEST should be in the same loop nest. */ + if (!dominated_by_p (CDI_DOMINATORS, pdom, dom) + || loop_depth (entry->src->loop_father) + != loop_depth (exit->dest->loop_father)) + return invalid_sese; + + /* For now we just want to bail out when exit does not post-dominate entry. + TODO: We might just add a basic_block at the exit to make exit + post-dominate entry (the entrire region). */ + if (!dominated_by_p (CDI_POST_DOMINATORS, get_entry_bb (entry), + get_exit_bb (exit)) + || !dominated_by_p (CDI_DOMINATORS, get_exit_bb (exit), + get_entry_bb (entry))) + { + DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n"); + return invalid_sese; + } + + /* FIXME: We should remove this piece of code once + canonicalize_loop_closed_ssa has been removed, because that function + adds a BB with single exit. */ + if (!trivially_empty_bb_p (get_exit_bb (combined.exit))) + { + /* Find the first empty succ (with single exit) of combined.exit. */ + basic_block imm_succ = combined.exit->dest; + if (single_succ_p (imm_succ) && trivially_empty_bb_p (imm_succ)) + combined.exit = single_succ_edge (imm_succ); + else + { + DEBUG_PRINT (dp << "\n[scop-detection-fail] Discarding SCoP because " + << "no single exit (empty succ) for sese exit"; + print_sese (dump_file, combined)); + return invalid_sese; + } + } + + /* Analyze all the BBs in new sese. */ + if (harmful_stmt_in_region (combined)) + return invalid_sese; + + DEBUG_PRINT (dp << "[merged-sese] s1: "; + print_sese (dump_file, combined)); + + return combined; + } + + /* Build scop outer->inner if possible. */ + sese_l + build_scop_depth (sese_l s, loop_p loop) + { + if (!loop) + return s; + + DEBUG_PRINT (dp << "\n[Depth loop_" << loop->num << "]"); + s = build_scop_depth (s, loop->inner); + + sese_l s2 = merge_sese (s, get_sese (loop)); + if (!s2) + { + /* s might be a valid scop, so return it and start analyzing from the + adjacent loop. */ + build_scop_depth (invalid_sese, loop->next); + return s; + } + + if (!loop_is_valid_scop (loop, s2)) + return build_scop_depth (invalid_sese, loop->next); + + return build_scop_breadth (s2, loop); + } + + /* If loop and loop->next are valid scops, try to merge them. */ + + sese_l + build_scop_breadth (sese_l s1, loop_p loop) + { + if (!loop) + return s1; + DEBUG_PRINT (dp << "\n[Breadth loop_" << loop->num << "]"); + gcc_assert (s1); + + loop_p l = loop; + sese_l s2 = build_scop_depth (invalid_sese, l->next); + if (!s2) + { + if (s1) + add_scop (s1); + return s1; + } + + sese_l combined = merge_sese (s1, s2); + + if (combined) + s1 = combined; + else + add_scop (s2); + + if (s1) + add_scop (s1); + return s1; + } + + /* Returns true when Graphite can represent LOOP in SCOP. + FIXME: For the moment, graphite cannot be used on loops that iterate using + induction variables that wrap. */ + static bool + can_represent_loop_1 (loop_p loop, sese_l scop) + { + tree niter; + struct tree_niter_desc niter_desc; + + return single_exit (loop) + && number_of_iterations_exit (loop, single_exit (loop), &niter_desc, false) + && niter_desc.control.no_overflow + && (niter = number_of_latch_executions (loop)) + && !chrec_contains_undetermined (niter) + && graphite_can_represent_expr (scop, loop, niter); + } + + /* Return true when all the loops within LOOP can be represented by + Graphite. */ + + static bool + can_represent_loop (loop_p loop, sese_l scop) + { + if (!can_represent_loop_1 (loop, scop)) + return false; + if (loop->inner && !can_represent_loop (loop->inner, scop)) + return false; + if (loop->next && !can_represent_loop (loop->next, scop)) + return false; + + return true; + } + + /* Return true when LOOP is a valid scop, that is a Static Control Part, a + region of code that can be represented in the polyhedral model. SCOP + defines the region we analyse. */ + + static bool + loop_is_valid_scop (loop_p loop, sese_l scop) + { + if (!scop) + return false; + + if (!can_represent_loop (loop, scop)) + { + DEBUG_PRINT (dp << "[scop-detection-fail] cannot represent loop_" + << loop->num << "\n"); + return false; + } + + if (loop_body_is_valid_scop (loop, scop)) + { + DEBUG_PRINT (dp << "[valid-scop] loop_" + << loop->num << "is a valid scop.\n"); + return true; + } + return false; + } + + /* Return true when BEGIN is the preheader edge of a loop with a single exit + END. */ + + static bool + region_has_one_loop (sese_l s) + { + edge begin = s.entry; + edge end = s.exit; + /* Check for a single perfectly nested loop. */ + if (begin->dest->loop_father->inner) + return false; + + /* Otherwise, check whether we have adjacent loops. */ + return begin->dest->loop_father == end->src->loop_father; + } + + /* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */ + + void + add_scop (sese_l s) + { + gcc_assert (s); + edge scop_begin = s.entry; + edge scop_end = s.exit; + + /* Do not add scops with only one loop. */ + if (region_has_one_loop (s)) + { + DEBUG_PRINT (dp << "\n[scop-detection-fail] Discarding one loop SCoP"; + print_sese (dump_file, s)); + return; + } + + if (get_exit_bb (scop_end) == EXIT_BLOCK_PTR_FOR_FN (cfun)) + { + DEBUG_PRINT (dp << "\n[scop-detection-fail] " + << "Discarding SCoP exiting to return"; + print_sese (dump_file, s)); + return; + } + + sese sese_reg = new_sese (scop_begin, scop_end); + scop_p newscop = new_scop (sese_reg); + + /* Remove all the scops which are subsumed by s. */ + remove_subscops (newscop); + + /* Replace this with split-intersecting scops. */ + remove_intersecting_scops (newscop); + + scops->safe_push (newscop); + DEBUG_PRINT (dp << "\nAdding SCoP "; print_sese (dump_file, s)); + } + + /* Return true when a statement in SCOP cannot be represented by Graphite. + The assumptions are that L1 dominates L2, and SCOP->entry dominates L1. + Limit the number of bbs between adjacent loops to + PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */ + + static bool + harmful_stmt_in_region (sese_l scop) + { + basic_block exit_bb = get_exit_bb (scop.exit); + basic_block entry_bb = get_entry_bb (scop.entry); + + DEBUG_PRINT (dp << "\n[checking-harmful-bbs] "; + print_sese (dump_file, scop)); + gcc_assert (dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb)); + + int depth = bb_dom_dfs_in (CDI_DOMINATORS, exit_bb) + - bb_dom_dfs_in (CDI_DOMINATORS, entry_bb); + + gcc_assert (depth >0); + + vec dom = get_dominated_to_depth (CDI_DOMINATORS, + entry_bb, depth); + int i; + basic_block bb; + FOR_EACH_VEC_ELT (dom, i, bb) + { + DEBUG_PRINT (dp << "\nVisiting bb_" << bb->index); + + /* We don't want to analyze any bb outside sese. */ + if (!dominated_by_p (CDI_POST_DOMINATORS, bb, exit_bb)) + continue; + + if (harmful_stmt_in_bb (scop, bb)) + return true; + } + + return false; + } + + /* Returns true if S1 subsumes/surrounds S2. */ + static bool + subsumes (scop_p s1, scop_p s2) + { + if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2->region->entry), + get_entry_bb (s1->region->entry)) + && dominated_by_p (CDI_POST_DOMINATORS, get_entry_bb (s2->region->exit), + get_entry_bb (s1->region->exit))) + return true; + return false; + } + + /* TODO: Maybe vec can be made as vec so that it consumes + less memory and later push only the relevant scops to vec . */ + void + remove_subscops (scop_p s1) + { + int j; + scop_p s2; + FOR_EACH_VEC_ELT_REVERSE (*scops, j, s2) + { + if (subsumes (s1, s2)) + { + DEBUG_PRINT (dp << "\nRemoving sub-SCoP"; + print_sese (dump_file, + sese_l (s2->region->entry, s2->region->exit))); + scops->unordered_remove (j); + } + } + } + + /* Returns true if S1 intersects with S2. Since we already know that S1 does + not subsume S2 or vice-versa, we only check for entry bbs. */ + + static bool + intersects (scop_p s1, scop_p s2) + { + if (dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2->region->entry), + get_entry_bb (s1->region->entry)) + && !dominated_by_p (CDI_DOMINATORS, get_entry_bb (s2->region->entry), + get_exit_bb (s1->region->exit))) + return true; + if ((s1->region->exit == s2->region->entry) + || (s2->region->exit == s1->region->entry)) + return true; + + return false; + } + + /* Remove one of the scops when it intersects with any other. */ + + void + remove_intersecting_scops (scop_p s1) + { + int j; + scop_p s2; + FOR_EACH_VEC_ELT_REVERSE (*scops, j, s2) + { + if (intersects (s1, s2)) + { + DEBUG_PRINT (dp << "\nRemoving intersecting SCoP"; + print_sese (dump_file, sese_l (s2->region->entry, + s2->region->exit)); + dp << "Intersects with:"; + print_sese (dump_file, sese_l (s1->region->entry, + s1->region->exit))); + scops->unordered_remove (j); + } + } + } + + private: + vec *scops; +}; + +sese_l scop_builder::invalid_sese (NULL, NULL); + +/* Find Static Control Parts (SCoP) in the current function and pushes + them to SCOPS. */ + +void +build_scops (vec *scops) +{ + if (dump_file) + dp.set_dump_file (dump_file); + + canonicalize_loop_closed_ssa_form (); + + scop_builder s (scops); + s.build_scop_depth (scop_builder::invalid_sese, current_loops->tree_root); + DEBUG_PRINT (dp << "number of SCoPs: " << (scops ? scops->length () : 0);); +} + #endif /* HAVE_isl */ diff --git a/gcc/graphite.c b/gcc/graphite.c index 36b97a71e3f..a957d93a3ec 100644 --- a/gcc/graphite.c +++ b/gcc/graphite.c @@ -47,6 +47,7 @@ along with GCC; see the file COPYING3. If not see #include "cfgloop.h" #include "tree-pass.h" #include "params.h" +#include "pretty-print.h" #ifdef HAVE_isl #include "cfghooks.h" @@ -168,6 +169,16 @@ print_graphite_scop_statistics (FILE* file, scop_p scop) } } + fprintf (file, "\nFunction Name: %s\n", current_function_name ()); + + edge scop_begin = scop->region->entry; + edge scop_end = scop->region->exit; + + fprintf (file, "\nSCoP (entry_edge (bb_%d, bb_%d), ", + scop_begin->src->index, scop_begin->dest->index); + fprintf (file, "exit_edge (bb_%d, bb_%d))", + scop_end->src->index, scop_end->dest->index); + fprintf (file, "\nSCoP statistics ("); fprintf (file, "BBS:%ld, ", n_bbs); fprintf (file, "LOOPS:%ld, ", n_loops); @@ -191,6 +202,10 @@ print_graphite_statistics (FILE* file, vec scops) FOR_EACH_VEC_ELT (scops, i, scop) print_graphite_scop_statistics (file, scop); + + /* Print the loop structure. */ + print_loops (file, 2); + print_loops (file, 3); } /* Initialize graphite: when there are no loops returns false. */ @@ -198,14 +213,30 @@ print_graphite_statistics (FILE* file, vec scops) static bool graphite_initialize (isl_ctx *ctx) { - if (number_of_loops (cfun) <= 1 + int min_loops = PARAM_VALUE (PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION); + int max_bbs = PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION); + int nbbs = n_basic_blocks_for_fn (cfun); + int nloops = number_of_loops (cfun); + + if (nloops <= min_loops /* FIXME: This limit on the number of basic blocks of a function should be removed when the SCOP detection is faster. */ - || (n_basic_blocks_for_fn (cfun) > - PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION))) + || (nbbs > max_bbs)) { if (dump_file && (dump_flags & TDF_DETAILS)) - print_global_statistics (dump_file); + { + if (nloops <= min_loops) + fprintf (dump_file, "\nFunction does not have enough loops: " + "PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION = %d.\n", + min_loops); + + else if (nbbs > max_bbs) + fprintf (dump_file, "\nFunction has too many basic blocks: " + "PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION = %d.\n", max_bbs); + + fprintf (dump_file, "\nnumber of SCoPs: 0\n"); + print_global_statistics (dump_file); + } isl_ctx_free (ctx); return false; @@ -216,7 +247,10 @@ graphite_initialize (isl_ctx *ctx) initialize_original_copy_tables (); if (dump_file && dump_flags) - dump_function_to_file (current_function_decl, dump_file, dump_flags); + { + dump_function_to_file (current_function_decl, dump_file, dump_flags); + print_loops (dump_file, 3); + } return true; } @@ -227,8 +261,10 @@ graphite_initialize (isl_ctx *ctx) static void graphite_finalize (bool need_cfg_cleanup_p) { + free_dominance_info (CDI_POST_DOMINATORS); if (need_cfg_cleanup_p) { + free_dominance_info (CDI_DOMINATORS); scev_reset (); cleanup_tree_cfg (); profile_status_for_fn (cfun) = PROFILE_ABSENT; diff --git a/gcc/params.def b/gcc/params.def index 34e2025f3d2..3f919928156 100644 --- a/gcc/params.def +++ b/gcc/params.def @@ -844,6 +844,13 @@ DEFPARAM (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION, "maximum number of basic blocks per function to be analyzed by Graphite", 100, 0, 0) +/* Maximal number of basic blocks in the functions analyzed by Graphite. */ + +DEFPARAM (PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION, + "graphite-min-loops-per-function", + "minimal number of loops per function to be analyzed by Graphite", + 2, 0, 0) + DEFPARAM (PARAM_MAX_ISL_OPERATIONS, "max-isl-operations", "maximum number of ISL operations, 0 means unlimited", diff --git a/gcc/sese.h b/gcc/sese.h index 0d13d87d2fc..1a26fa836e7 100644 --- a/gcc/sese.h +++ b/gcc/sese.h @@ -172,11 +172,6 @@ sese_loop_depth (sese region, loop_p loop) { unsigned int depth = 0; - gcc_assert ((!loop_in_sese_p (loop, region) - && (SESE_ENTRY_BB (region)->loop_father == loop - || SESE_EXIT (region)->src->loop_father == loop)) - || loop_in_sese_p (loop, region)); - while (loop_in_sese_p (loop, region)) { depth++; @@ -263,6 +258,9 @@ recompute_all_dominators (void) mark_irreducible_loops (); free_dominance_info (CDI_DOMINATORS); calculate_dominance_info (CDI_DOMINATORS); + + free_dominance_info (CDI_POST_DOMINATORS); + calculate_dominance_info (CDI_POST_DOMINATORS); } typedef struct gimple_bb diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index bee7aedf77d..da9954dd703 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,44 @@ +2015-09-28 Aditya Kumar + Sebastian Pop + + * gcc/testsuite/gcc.dg/graphite/run-id-pr67700-1.c: New test case. + * gcc.dg/graphite/block-1.c: Modified to match the pattern. + * gcc.dg/graphite/block-3.c: Same. + * gcc.dg/graphite/block-4.c: Same. + * gcc.dg/graphite/block-5.c: Same. + * gcc.dg/graphite/block-6.c: Same. + * gcc.dg/graphite/block-7.c: Same. + * gcc.dg/graphite/block-8.c: Same. + * gcc.dg/graphite/block-pr47654.c: Same. + * gcc.dg/graphite/interchange-0.c: Same. + * gcc.dg/graphite/interchange-1.c: Same. + * gcc.dg/graphite/interchange-10.c: Same. + * gcc.dg/graphite/interchange-11.c: Same. + * gcc.dg/graphite/interchange-12.c: Same. + * gcc.dg/graphite/interchange-13.c: Same. + * gcc.dg/graphite/interchange-14.c: Same. + * gcc.dg/graphite/interchange-15.c: Same. + * gcc.dg/graphite/interchange-3.c: Same. + * gcc.dg/graphite/interchange-4.c: Same. + * gcc.dg/graphite/interchange-5.c: Same. + * gcc.dg/graphite/interchange-6.c: Same. + * gcc.dg/graphite/interchange-7.c: Same. + * gcc.dg/graphite/interchange-8.c: Same. + * gcc.dg/graphite/interchange-9.c: Same. + * gcc.dg/graphite/interchange-mvt.c: Same. + * gcc.dg/graphite/pr35356-1.c: Same. + * gcc.dg/graphite/pr35356-3.c: Same. + * gcc.dg/graphite/pr37485.c: Same. + * gcc.dg/graphite/scop-1.c: Same. + * gcc.dg/graphite/scop-11.c: Same. + * gcc.dg/graphite/scop-5.c: Same. + * gcc.dg/graphite/uns-block-1.c: Same. + * gcc.dg/graphite/uns-interchange-9.c: Same. + * gfortran.dg/graphite/block-1.f90: Same. + * gfortran.dg/graphite/interchange-3.f90: Same. + * gfortran.dg/graphite/pr14741.f90: Same. + * gfortran.dg/graphite/block-2.f: Same. + 2015-09-28 Aditya Kumar Sebastian Pop diff --git a/gcc/testsuite/gcc.dg/graphite/block-1.c b/gcc/testsuite/gcc.dg/graphite/block-1.c index bb81a95d421..b8ac3acf9ac 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 "tiled by" 6 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/block-3.c b/gcc/testsuite/gcc.dg/graphite/block-3.c index fd0e661696a..08bdb23e9e9 100644 --- a/gcc/testsuite/gcc.dg/graphite/block-3.c +++ b/gcc/testsuite/gcc.dg/graphite/block-3.c @@ -58,4 +58,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "tiled by" 3 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/block-4.c b/gcc/testsuite/gcc.dg/graphite/block-4.c index 744b481eaf0..0deaec14e7a 100644 --- a/gcc/testsuite/gcc.dg/graphite/block-4.c +++ b/gcc/testsuite/gcc.dg/graphite/block-4.c @@ -57,4 +57,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "tiled by" 7 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/block-5.c b/gcc/testsuite/gcc.dg/graphite/block-5.c index 2f4b2f503b0..97bf410dcf6 100644 --- a/gcc/testsuite/gcc.dg/graphite/block-5.c +++ b/gcc/testsuite/gcc.dg/graphite/block-5.c @@ -53,4 +53,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "tiled by" 4 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/block-6.c b/gcc/testsuite/gcc.dg/graphite/block-6.c index 36e9783d151..a6a5ba7d7de 100644 --- a/gcc/testsuite/gcc.dg/graphite/block-6.c +++ b/gcc/testsuite/gcc.dg/graphite/block-6.c @@ -48,4 +48,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "tiled by" 4 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/block-7.c b/gcc/testsuite/gcc.dg/graphite/block-7.c index 8b54e267078..4e5c5760fad 100644 --- a/gcc/testsuite/gcc.dg/graphite/block-7.c +++ b/gcc/testsuite/gcc.dg/graphite/block-7.c @@ -54,4 +54,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "tiled by" 6 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/block-8.c b/gcc/testsuite/gcc.dg/graphite/block-8.c index d3fdf849d59..298db85460d 100644 --- a/gcc/testsuite/gcc.dg/graphite/block-8.c +++ b/gcc/testsuite/gcc.dg/graphite/block-8.c @@ -55,4 +55,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "tiled by" 7 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/block-pr47654.c b/gcc/testsuite/gcc.dg/graphite/block-pr47654.c index a7453c5e9a6..6d53ef42cb4 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 "tiled by" 1 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-0.c b/gcc/testsuite/gcc.dg/graphite/interchange-0.c index 2ea8f017b8e..d56be46d484 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 "tiled by" 2 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-1.c b/gcc/testsuite/gcc.dg/graphite/interchange-1.c index 2c58ac21e98..97110079efe 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-1.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-1.c @@ -49,4 +49,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "tiled by" 3 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-10.c b/gcc/testsuite/gcc.dg/graphite/interchange-10.c index 9d486448d08..e2ad2984342 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 "tiled by" 6 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-11.c b/gcc/testsuite/gcc.dg/graphite/interchange-11.c index 4f6918dc691..77106180a00 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-11.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-11.c @@ -46,4 +46,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "tiled by" 3 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-12.c b/gcc/testsuite/gcc.dg/graphite/interchange-12.c index 9d5e04c882b..482bea46c03 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-12.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-12.c @@ -53,4 +53,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "tiled by" 5 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-13.c b/gcc/testsuite/gcc.dg/graphite/interchange-13.c index c9ea048e482..37422a7c75b 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-13.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-13.c @@ -50,4 +50,4 @@ main (void) } -/* { dg-final { scan-tree-dump-times "tiled by" 3 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-14.c b/gcc/testsuite/gcc.dg/graphite/interchange-14.c index 151bfe71f1f..ca4dedc2760 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-14.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-14.c @@ -54,4 +54,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "tiled by" 6 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-15.c b/gcc/testsuite/gcc.dg/graphite/interchange-15.c index 0b6829f14cf..7410f29da50 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 "tiled by" 4 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-3.c b/gcc/testsuite/gcc.dg/graphite/interchange-3.c index ebdeef7ea8e..1d63ea84bf9 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-3.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-3.c @@ -47,4 +47,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "tiled by" 3 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-4.c b/gcc/testsuite/gcc.dg/graphite/interchange-4.c index 9a50e7a0833..e2887d5cbe3 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-4.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-4.c @@ -46,4 +46,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "tiled by" 3 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-5.c b/gcc/testsuite/gcc.dg/graphite/interchange-5.c index 339e3b75f94..e5aaa642d8e 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 "tiled by" 2 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-6.c b/gcc/testsuite/gcc.dg/graphite/interchange-6.c index 78f358e9ed2..7257c29dba8 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 "tiled by" 2 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-7.c b/gcc/testsuite/gcc.dg/graphite/interchange-7.c index e53d30e8cfe..f231b878ba2 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-7.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-7.c @@ -46,4 +46,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "tiled by" 3 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-8.c b/gcc/testsuite/gcc.dg/graphite/interchange-8.c index c5e714175a0..d7059107038 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-8.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-8.c @@ -82,4 +82,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "tiled by" 6 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-9.c b/gcc/testsuite/gcc.dg/graphite/interchange-9.c index 44a5452213e..690fa1e48d6 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-9.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-9.c @@ -44,4 +44,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "tiled by" 4 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c b/gcc/testsuite/gcc.dg/graphite/interchange-mvt.c index bfa5c63b9d1..c6543ec457c 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 "tiled by" 7 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/pr35356-1.c b/gcc/testsuite/gcc.dg/graphite/pr35356-1.c index 7f0e8246e03..6d82579d4e1 100644 --- a/gcc/testsuite/gcc.dg/graphite/pr35356-1.c +++ b/gcc/testsuite/gcc.dg/graphite/pr35356-1.c @@ -24,6 +24,14 @@ foo (int bar, int n, int k) | if (k >= 0 && k < n) | a[k] = bar; + Check that this text is produced: + +ISL AST generated by ISL: +if (n >= k + 1 && k >= 0) { + S_6(k); + S_11(k); +} + */ -/* { dg-final { scan-tree-dump-times "loop_1" 0 "graphite" } } */ +/* { dg-final { scan-tree-dump-times "if \\\(n >= k \\\+ 1 && k >= 0\\\) \\\{" 1 "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/pr35356-3.c b/gcc/testsuite/gcc.dg/graphite/pr35356-3.c index a9dd3361f01..f2827a2bb6d 100644 --- a/gcc/testsuite/gcc.dg/graphite/pr35356-3.c +++ b/gcc/testsuite/gcc.dg/graphite/pr35356-3.c @@ -36,4 +36,4 @@ match (void) "Y[winner].y > 0". This could be fixed when we will use predicates for such cases. */ -/* { dg-final { scan-tree-dump-times "loop_1" 0 "graphite" { xfail *-*-* } } } */ +/* { dg-final { scan-tree-dump-times "loop_1" 0 "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/pr37485.c b/gcc/testsuite/gcc.dg/graphite/pr37485.c index 47138d303af..c6d4f924113 100644 --- a/gcc/testsuite/gcc.dg/graphite/pr37485.c +++ b/gcc/testsuite/gcc.dg/graphite/pr37485.c @@ -1,4 +1,4 @@ -/* { dg-options "-O2 -floop-block -ffast-math -fdump-tree-graphite-all" } */ +/* { dg-options "-O2 -floop-block -ffast-math" } */ typedef unsigned char UChar; typedef int Int32; @@ -30,5 +30,3 @@ void fallbackSort ( UInt32* fmap, } AssertH ( j < 256, 1005 ); } - -/* { dg-final { scan-tree-dump-times "tiled by" 4 "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/run-id-pr67700-1.c b/gcc/testsuite/gcc.dg/graphite/run-id-pr67700-1.c new file mode 100644 index 00000000000..e0db2561e7d --- /dev/null +++ b/gcc/testsuite/gcc.dg/graphite/run-id-pr67700-1.c @@ -0,0 +1,48 @@ +#include +#include + +struct type *obj; +struct type { + int elem1[81]; +}; + +enum fpmath_unit +{ + FPMATH_387 = 1, + FPMATH_SSE = 2 +}; + +struct gcc_options +{ + enum fpmath_unit x_ix86_fpmath; +}; + +struct gcc_options global_options; + +void foo(void) +{ + int pos = 0; + int i; + if (!((global_options.x_ix86_fpmath & FPMATH_SSE) != 0)) + for (i = 8; i <= 15; i++) + (obj->elem1) [pos++] = i; + for (i = 45; i <= 52; i++) + (obj->elem1) [pos++] = i; + if (((global_options.x_ix86_fpmath & FPMATH_SSE) != 0)) + for (i = 8; i <= 15; i++) + (obj->elem1) [pos++] = i; + for (i = 29; i <= 36; i++) + (obj->elem1) [pos++] = i; +} + +int main() +{ + int i; + obj = (struct type*) malloc (sizeof (struct type)); + for (i = 0; i <= 80; i++) + obj->elem1[i] = 0; + foo(); + assert (obj->elem1[8] == 45); + return 0; +} + diff --git a/gcc/testsuite/gcc.dg/graphite/scop-1.c b/gcc/testsuite/gcc.dg/graphite/scop-1.c index a569065d095..f8f1bf908f1 100644 --- a/gcc/testsuite/gcc.dg/graphite/scop-1.c +++ b/gcc/testsuite/gcc.dg/graphite/scop-1.c @@ -1,6 +1,6 @@ void bar (void); -int toto() +int toto () { int i, j, k; int a[101][100]; @@ -16,12 +16,12 @@ int toto() bar (); for (j = 1; j < 100; j++) - a[j][i] = a[j+1][i-1] + 2; + a[j][i] = a[j+1][i-1] + 3; b[i] = a[i-1][i] + 2; for (j = 1; j < 100; j++) - a[j][i] = a[j+1][i-1] + 2; + a[j][i] = a[j+1][i-1] + 4; } return a[3][5] + b[1]; diff --git a/gcc/testsuite/gcc.dg/graphite/scop-11.c b/gcc/testsuite/gcc.dg/graphite/scop-11.c index 97fe5393b37..801e54f9961 100644 --- a/gcc/testsuite/gcc.dg/graphite/scop-11.c +++ b/gcc/testsuite/gcc.dg/graphite/scop-11.c @@ -1,25 +1,17 @@ void bar (); -int toto() +int toto (int i, int b) { - int i,j, b; + int j; int a[100]; - if (i == 20) - { - for (j = 0; j <= 20; j++) - a[j] = b + i; - b = 3; - } - else - { - if (i == 30) - { - for (j = 0; j <= 20; j++) - a[j] = b + i; - b = 5; - } - } + for (j = 0; j <= 20; j++) + a[j] = b + i; + + if (a[12] == 23) + b = 3; + else + b = 1; for (j = 0; j <= 20; j++) a[j] = b + i; diff --git a/gcc/testsuite/gcc.dg/graphite/scop-5.c b/gcc/testsuite/gcc.dg/graphite/scop-5.c index 8309257554c..5ecaaeed383 100644 --- a/gcc/testsuite/gcc.dg/graphite/scop-5.c +++ b/gcc/testsuite/gcc.dg/graphite/scop-5.c @@ -33,4 +33,4 @@ int toto() return a[b]; } -/* { dg-final { scan-tree-dump-times "number of SCoPs: 2" 1 "graphite"} } */ +/* { dg-final { scan-tree-dump-times "number of SCoPs: 1" 1 "graphite"} } */ diff --git a/gcc/testsuite/gcc.dg/graphite/uns-block-1.c b/gcc/testsuite/gcc.dg/graphite/uns-block-1.c index 64ca761c40c..3bc7c127d76 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 "tiled by" 5 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gcc.dg/graphite/uns-interchange-9.c b/gcc/testsuite/gcc.dg/graphite/uns-interchange-9.c index 601169ec39e..ff712140350 100644 --- a/gcc/testsuite/gcc.dg/graphite/uns-interchange-9.c +++ b/gcc/testsuite/gcc.dg/graphite/uns-interchange-9.c @@ -45,4 +45,4 @@ main (void) return 0; } -/* { dg-final { scan-tree-dump-times "tiled by" 3 "graphite" } } */ +/* { dg-final { scan-tree-dump "tiled by" "graphite" } } */ diff --git a/gcc/testsuite/gfortran.dg/graphite/block-1.f90 b/gcc/testsuite/gfortran.dg/graphite/block-1.f90 index 253efd74a0a..237bd1ed6f8 100644 --- a/gcc/testsuite/gfortran.dg/graphite/block-1.f90 +++ b/gcc/testsuite/gfortran.dg/graphite/block-1.f90 @@ -7,6 +7,4 @@ c=0.d0 end subroutine matrix_multiply -! { dg-final { scan-tree-dump-times "number of SCoPs: 1" 1 "graphite" { xfail *-*-* } } } -! { dg-final { scan-tree-dump-times "will be loop blocked" 1 "graphite" { xfail *-*-* } } } - +! { dg-final { scan-tree-dump-times "number of SCoPs: 1" 1 "graphite"} } diff --git a/gcc/testsuite/gfortran.dg/graphite/block-2.f b/gcc/testsuite/gfortran.dg/graphite/block-2.f index 5cc1445ea41..d7ca40f704f 100644 --- a/gcc/testsuite/gfortran.dg/graphite/block-2.f +++ b/gcc/testsuite/gfortran.dg/graphite/block-2.f @@ -16,5 +16,4 @@ RETURN END -! { dg-final { scan-tree-dump-times "number of SCoPs: 2" 1 "graphite" { xfail *-*-* } } } -! { dg-final { scan-tree-dump-times "will be loop blocked" 2 "graphite" { xfail *-*-* } } } +! { dg-final { scan-tree-dump-times "number of SCoPs: 2" 1 "graphite" } } diff --git a/gcc/testsuite/gfortran.dg/graphite/interchange-3.f90 b/gcc/testsuite/gfortran.dg/graphite/interchange-3.f90 index d401638ccc8..9c373324ec0 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 "tiled by" 5 "graphite" } } +! { dg-final { scan-tree-dump "tiled by" "graphite" } } diff --git a/gcc/testsuite/gfortran.dg/graphite/pr14741.f90 b/gcc/testsuite/gfortran.dg/graphite/pr14741.f90 index 4dfdd077fcf..e40262f1288 100644 --- a/gcc/testsuite/gfortran.dg/graphite/pr14741.f90 +++ b/gcc/testsuite/gfortran.dg/graphite/pr14741.f90 @@ -24,5 +24,4 @@ SUBROUTINE mult(A,B,C,N) ENDDO END SUBROUTINE mult -! { dg-final { scan-tree-dump-times "number of SCoPs: 1" 1 "graphite" { xfail *-*-* } } } -! { dg-final { scan-tree-dump-times "will be loop blocked" 1 "graphite" { xfail *-*-* } } } +! { dg-final { scan-tree-dump "tiled by" "graphite" } } diff --git a/gcc/tree-cfg.c b/gcc/tree-cfg.c index 807d96f8f76..712d8cc9633 100644 --- a/gcc/tree-cfg.c +++ b/gcc/tree-cfg.c @@ -7646,6 +7646,7 @@ print_loops (FILE *file, int verbosity) basic_block bb; bb = ENTRY_BLOCK_PTR_FOR_FN (cfun); + fprintf (file, "\nLoops in function: %s\n", current_function_name ()); if (bb && bb->loop_father) print_loop_and_siblings (file, bb->loop_father, 0, verbosity); } -- 2.30.2