From d2552094b8c0a8aaa92d831ee3de2a72cc20d642 Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Wed, 27 Sep 2017 11:09:41 +0000 Subject: [PATCH] invoke.texi (graphite-max-bbs-per-function): Remove. 2017-09-27 Richard Biener * doc/invoke.texi (graphite-max-bbs-per-function): Remove. (graphite-max-nb-scop-params): Document special value zero. * domwalk.h (dom_walker::STOP): New symbolical constant. (dom_walker::dom_walker): Add optional parameter for bb to RPO mapping. (dom_walker::~dom_walker): Declare. (dom_walker::before_dom_children): Document STOP return value. (dom_walker::m_user_bb_to_rpo): New member. (dom_walker::m_bb_to_rpo): Likewise. * domwalk.c (dom_walker::dom_walker): Compute bb to RPO mapping here if not provided by the user. (dom_walker::~dom_walker): Free bb to RPO mapping if not provided by the user. (dom_walker::STOP): Define. (dom_walker::walk): Do not compute bb to RPO mapping here. Support STOP return value from before_dom_children to stop walking. * graphite-optimize-isl.c (optimize_isl): If the schedule is the same still generate code if -fgraphite-identity or -floop-parallelize-all are given. * graphite-scop-detection.c: Include cfganal.h. (gather_bbs::gather_bbs): Get and pass through bb to RPO mapping. (gather_bbs::before_dom_children): Return STOP for BBs not in the region. (build_scops): Compute bb to RPO mapping and pass it to the domwalk. Treat --param graphite-max-nb-scop-params=0 as not limiting the number of params. * graphite.c (graphite_initialize): Remove limit on the number of basic-blocks in a function. * params.def (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION): Remove. (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS): Adjust to documented default value of 10. From-SVN: r253226 --- gcc/ChangeLog | 36 ++++++++++++++++++ gcc/doc/invoke.texi | 10 ++--- gcc/domwalk.c | 72 ++++++++++++++++++++++------------- gcc/domwalk.h | 19 +++++++-- gcc/graphite-optimize-isl.c | 2 +- gcc/graphite-scop-detection.c | 25 ++++++++---- gcc/graphite.c | 11 +----- gcc/params.def | 9 +---- 8 files changed, 121 insertions(+), 63 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 340e1e8855d..8d2edda74ee 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,39 @@ +2017-09-27 Richard Biener + + * doc/invoke.texi (graphite-max-bbs-per-function): Remove. + (graphite-max-nb-scop-params): Document special value zero. + * domwalk.h (dom_walker::STOP): New symbolical constant. + (dom_walker::dom_walker): Add optional parameter for bb to + RPO mapping. + (dom_walker::~dom_walker): Declare. + (dom_walker::before_dom_children): Document STOP return value. + (dom_walker::m_user_bb_to_rpo): New member. + (dom_walker::m_bb_to_rpo): Likewise. + * domwalk.c (dom_walker::dom_walker): Compute bb to RPO + mapping here if not provided by the user. + (dom_walker::~dom_walker): Free bb to RPO mapping if not + provided by the user. + (dom_walker::STOP): Define. + (dom_walker::walk): Do not compute bb to RPO mapping here. + Support STOP return value from before_dom_children to stop + walking. + * graphite-optimize-isl.c (optimize_isl): If the schedule + is the same still generate code if -fgraphite-identity + or -floop-parallelize-all are given. + * graphite-scop-detection.c: Include cfganal.h. + (gather_bbs::gather_bbs): Get and pass through bb to RPO + mapping. + (gather_bbs::before_dom_children): Return STOP for BBs + not in the region. + (build_scops): Compute bb to RPO mapping and pass it to + the domwalk. Treat --param graphite-max-nb-scop-params=0 + as not limiting the number of params. + * graphite.c (graphite_initialize): Remove limit on the + number of basic-blocks in a function. + * params.def (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION): Remove. + (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS): Adjust to documented + default value of 10. + 2017-09-26 Michael Meissner * config/rs6000/vsx.md (peephole for optimizing move SF to GPR): diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 5e39c0efeb9..f862b7f8c99 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -10512,13 +10512,9 @@ sequence pairs. This option only applies when using @item graphite-max-nb-scop-params To avoid exponential effects in the Graphite loop transforms, the number of parameters in a Static Control Part (SCoP) is bounded. The -default value is 10 parameters. A variable whose value is unknown at -compilation time and defined outside a SCoP is a parameter of the SCoP. - -@item graphite-max-bbs-per-function -To avoid exponential effects in the detection of SCoPs, the size of -the functions analyzed by Graphite is bounded. The default value is -100 basic blocks. +default value is 10 parameters, a value of zero can be used to lift +the bound. A variable whose value is unknown at compilation time and +defined outside a SCoP is a parameter of the SCoP. @item loop-block-tile-size Loop blocking or strip mining transforms, enabled with diff --git a/gcc/domwalk.c b/gcc/domwalk.c index ff6604e5686..102a2936ba4 100644 --- a/gcc/domwalk.c +++ b/gcc/domwalk.c @@ -174,13 +174,29 @@ sort_bbs_postorder (basic_block *bbs, int n) If SKIP_UNREACHBLE_BLOCKS is true, then we need to set EDGE_EXECUTABLE on every edge in the CFG. */ dom_walker::dom_walker (cdi_direction direction, - bool skip_unreachable_blocks) + bool skip_unreachable_blocks, + int *bb_index_to_rpo) : m_dom_direction (direction), m_skip_unreachable_blocks (skip_unreachable_blocks), - m_unreachable_dom (NULL) + m_user_bb_to_rpo (bb_index_to_rpo != NULL), + m_unreachable_dom (NULL), + m_bb_to_rpo (bb_index_to_rpo) { + /* Compute the basic-block index to RPO mapping if not provided by + the user. */ + if (! m_bb_to_rpo && direction == CDI_DOMINATORS) + { + int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); + int postorder_num = pre_and_rev_post_order_compute (NULL, postorder, + true); + m_bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun)); + for (int i = 0; i < postorder_num; ++i) + m_bb_to_rpo[postorder[i]] = i; + free (postorder); + } + /* If we are not skipping unreachable blocks, then there is nothing - to do. */ + further to do. */ if (!m_skip_unreachable_blocks) return; @@ -194,6 +210,14 @@ dom_walker::dom_walker (cdi_direction direction, } } +/* Destructor. */ + +dom_walker::~dom_walker () +{ + if (! m_user_bb_to_rpo) + free (m_bb_to_rpo); +} + /* Return TRUE if BB is reachable, false otherwise. */ bool @@ -254,6 +278,8 @@ dom_walker::propagate_unreachable_to_edges (basic_block bb, m_unreachable_dom = bb; } +const edge dom_walker::STOP = (edge)-1; + /* Recursively walk the dominator tree. BB is the basic block we are currently visiting. */ @@ -264,17 +290,7 @@ dom_walker::walk (basic_block bb) basic_block *worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) * 2); int sp = 0; - int *postorder, postorder_num; - - if (m_dom_direction == CDI_DOMINATORS) - { - postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); - postorder_num = pre_and_rev_post_order_compute (NULL, postorder, true); - bb_postorder = XNEWVEC (int, last_basic_block_for_fn (cfun)); - for (int i = 0; i < postorder_num; ++i) - bb_postorder[postorder[i]] = i; - free (postorder); - } + bb_postorder = m_bb_to_rpo; while (true) { @@ -283,13 +299,14 @@ dom_walker::walk (basic_block bb) || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) || bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) { + edge taken_edge = NULL; /* Callback for subclasses to do custom things before we have walked the dominator children, but before we walk statements. */ if (this->bb_reachable (cfun, bb)) { - edge taken_edge = before_dom_children (bb); - if (taken_edge) + taken_edge = before_dom_children (bb); + if (taken_edge && taken_edge != STOP) { edge_iterator ei; edge e; @@ -306,12 +323,17 @@ dom_walker::walk (basic_block bb) worklist[sp++] = bb; worklist[sp++] = NULL; - int saved_sp = sp; - for (dest = first_dom_son (m_dom_direction, bb); - dest; dest = next_dom_son (m_dom_direction, dest)) - worklist[sp++] = dest; - if (sp - saved_sp > 1 && m_dom_direction == CDI_DOMINATORS) - sort_bbs_postorder (&worklist[saved_sp], sp - saved_sp); + /* If the callback returned NONE then we are supposed to + stop and not even propagate EDGE_EXECUTABLE further. */ + if (taken_edge != STOP) + { + int saved_sp = sp; + for (dest = first_dom_son (m_dom_direction, bb); + dest; dest = next_dom_son (m_dom_direction, dest)) + worklist[sp++] = dest; + if (sp - saved_sp > 1 && m_dom_direction == CDI_DOMINATORS) + sort_bbs_postorder (&worklist[saved_sp], sp - saved_sp); + } } /* NULL is used to mark pop operations in the recursion stack. */ while (sp > 0 && !worklist[sp - 1]) @@ -331,10 +353,6 @@ dom_walker::walk (basic_block bb) else break; } - if (m_dom_direction == CDI_DOMINATORS) - { - free (bb_postorder); - bb_postorder = NULL; - } + bb_postorder = NULL; free (worklist); } diff --git a/gcc/domwalk.h b/gcc/domwalk.h index 4b9f70ac703..6ac93eb06ad 100644 --- a/gcc/domwalk.h +++ b/gcc/domwalk.h @@ -30,14 +30,22 @@ along with GCC; see the file COPYING3. If not see class dom_walker { public: + static const edge STOP; + /* Use SKIP_UNREACHBLE_BLOCKS = true when your client can discover that some edges are not executable. If a client can discover that a COND, SWITCH or GOTO has a static target in the before_dom_children callback, the taken edge should be returned. The generic walker will clear EDGE_EXECUTABLE on all - edges it can determine are not executable. */ - dom_walker (cdi_direction direction, bool skip_unreachable_blocks = false); + edges it can determine are not executable. + + You can provide a mapping of basic-block index to RPO if you + have that readily available or you do multiple walks. */ + dom_walker (cdi_direction direction, bool skip_unreachable_blocks = false, + int *bb_index_to_rpo = NULL); + + ~dom_walker (); /* Walk the dominator tree. */ void walk (basic_block); @@ -48,7 +56,10 @@ public: edges, NULL otherwise. When skipping unreachable blocks, the walker uses the taken edge information to clear EDGE_EXECUTABLE on the other edges, exposing unreachable blocks. A NULL return value means all - outgoing edges should still be considered executable. */ + outgoing edges should still be considered executable. A return value + of STOP means to stop the domwalk from processing dominated blocks from + here. This can be used to process a SEME region only (note domwalk + will still do work linear in function size). */ virtual edge before_dom_children (basic_block) { return NULL; } /* Function to call after the recursive walk of the dominator children. */ @@ -61,7 +72,9 @@ private: dominator tree. */ const ENUM_BITFIELD (cdi_direction) m_dom_direction : 2; bool m_skip_unreachable_blocks; + bool m_user_bb_to_rpo; basic_block m_unreachable_dom; + int *m_bb_to_rpo; /* Query whether or not the given block is reachable or not. */ bool bb_reachable (struct function *, basic_block); diff --git a/gcc/graphite-optimize-isl.c b/gcc/graphite-optimize-isl.c index dbf10ead1ca..2f3c4fc533f 100644 --- a/gcc/graphite-optimize-isl.c +++ b/gcc/graphite-optimize-isl.c @@ -189,7 +189,7 @@ optimize_isl (scop_p scop) 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 flag_graphite_identity || flag_loop_parallelize_all; } return true; diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c index 90156bbbe76..3b1492fbfa8 100644 --- a/gcc/graphite-scop-detection.c +++ b/gcc/graphite-scop-detection.c @@ -48,6 +48,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-pass.h" #include "tree-ssa-propagate.h" #include "gimple-pretty-print.h" +#include "cfganal.h" #include "graphite.h" class debug_printer @@ -1544,7 +1545,7 @@ build_alias_set (scop_p scop) class gather_bbs : public dom_walker { public: - gather_bbs (cdi_direction, scop_p); + gather_bbs (cdi_direction, scop_p, int *); virtual edge before_dom_children (basic_block); virtual void after_dom_children (basic_block); @@ -1554,8 +1555,8 @@ private: scop_p scop; }; } -gather_bbs::gather_bbs (cdi_direction direction, scop_p scop) - : dom_walker (direction), scop (scop) +gather_bbs::gather_bbs (cdi_direction direction, scop_p scop, int *bb_to_rpo) + : dom_walker (direction, false, bb_to_rpo), scop (scop) { } @@ -1589,7 +1590,7 @@ gather_bbs::before_dom_children (basic_block bb) { sese_info_p region = scop->scop_info; if (!bb_in_sese_p (bb, region->region)) - return NULL; + return dom_walker::STOP; record_loop_in_sese (bb, region); @@ -1708,6 +1709,15 @@ build_scops (vec *scops) /* Now create scops from the lightweight SESEs. */ vec scops_l = sb.get_scops (); + + /* Domwalk needs a bb to RPO mapping. Compute it once here. */ + int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun)); + int postorder_num = pre_and_rev_post_order_compute (NULL, postorder, true); + int *bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun)); + for (int i = 0; i < postorder_num; ++i) + bb_to_rpo[postorder[i]] = i; + free (postorder); + int i; sese_l *s; FOR_EACH_VEC_ELT (scops_l, i, s) @@ -1715,7 +1725,7 @@ build_scops (vec *scops) scop_p scop = new_scop (s->entry, s->exit); /* Record all basic blocks and their conditions in REGION. */ - gather_bbs (CDI_DOMINATORS, scop).walk (s->entry->dest); + gather_bbs (CDI_DOMINATORS, scop, bb_to_rpo).walk (s->entry->dest); /* domwalk does not fulfil our code-generations constraints on the order of pbb which is to produce sth like execution order, delaying @@ -1757,8 +1767,8 @@ build_scops (vec *scops) find_scop_parameters (scop); graphite_dim_t max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS); - - if (scop_nb_params (scop) > max_dim) + if (max_dim > 0 + && scop_nb_params (scop) > max_dim) { DEBUG_PRINT (dp << "[scop-detection-fail] too many parameters: " << scop_nb_params (scop) @@ -1771,6 +1781,7 @@ build_scops (vec *scops) scops->safe_push (scop); } + free (bb_to_rpo); DEBUG_PRINT (dp << "number of SCoPs: " << (scops ? scops->length () : 0);); } diff --git a/gcc/graphite.c b/gcc/graphite.c index 6713df62514..0bdcc28cba8 100644 --- a/gcc/graphite.c +++ b/gcc/graphite.c @@ -218,14 +218,9 @@ static bool graphite_initialize (void) { 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. */ - || (nbbs > max_bbs)) + if (nloops <= min_loops) { if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -234,10 +229,6 @@ graphite_initialize (void) "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); } diff --git a/gcc/params.def b/gcc/params.def index 860e79e3209..136f9270366 100644 --- a/gcc/params.def +++ b/gcc/params.def @@ -873,14 +873,7 @@ DEFPARAM (PARAM_LOOP_BLOCK_TILE_SIZE, DEFPARAM (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS, "graphite-max-nb-scop-params", "maximum number of parameters in a SCoP.", - 7, 0, 0) - -/* Maximal number of basic blocks in the functions analyzed by Graphite. */ - -DEFPARAM (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION, - "graphite-max-bbs-per-function", - "maximum number of basic blocks per function to be analyzed by Graphite.", - 100, 0, 0) + 10, 0, 0) /* Maximal number of array references in a scop. */ -- 2.30.2