Hi, The patch cleans up the function to build scop's basic blocks and the function that gathers the conditions under which a basic block is executed. We remove one traversal of the dominator tree.
This refactoring was triggered by the need of a vec<bb> of all the basic blocks in a region. We will use that vector in a patch that removes the out-of-ssa translation of scalar dependences: we will iterate through the basic blocks of a region to record scalar dependences crossing bbs or going out of the region. The patch passes bootstrap and regtest on x86_64-linux. Sebastian Pop wrote: > 2015-10-06 Aditya Kumar <aditya...@samsung.com> > Sebastian Pop <s....@samsung.com> > > * graphite-dependences.c (scop_get_dependences): Do not use > SCOP_BBS. > * graphite-isl-ast-to-gimple.c (get_max_schedule_dimensions): > Same. > (generate_isl_schedule): Same. > * graphite-optimize-isl.c (scop_get_domains): Same. > (apply_schedule_map_to_scop): Same. > * graphite-poly.c (print_iteration_domains): Same. > (remove_gbbs_in_scop): Same. > (new_scop): Same. > (free_scop): Same. > (print_scop): Same. > * graphite-poly.h (struct scop): Rename bbs to pbbs. > (SCOP_BBS): Remove. > * graphite-scop-detection.c (compare_bb_depths): Remove. > (graphite_sort_dominated_info): Remove. > (try_generate_gimple_bb): Move out of scop_detection. > (all_non_dominated_preds_marked_p): Remove. > (build_scop_bbs_1): Remove. > (build_scop_bbs): Remove. > (nb_pbbs_in_loops): Do not use SCOP_BBS. > (find_scop_parameters): Same. > (sese_dom_walker): Rename gather_bbs. > (before_dom_children): Call try_generate_gimple_bb and > collect gbb > and pbb. > (build_scops): Call gather_bbs. > * graphite-sese-to-poly.c (build_scop_scattering): Do not use > SCOP_BBS. > (add_conditions_to_constraints): Same. > (build_scop_iteration_domain): Same. > (build_scop_drs): Same. > (new_pbb_from_pbb): Same. > * sese.c (new_sese_info): Create bbs. > * sese.h (struct sese_info_t): Add bbs. > --- > gcc/graphite-dependences.c | 2 +- > gcc/graphite-isl-ast-to-gimple.c | 4 +- > gcc/graphite-optimize-isl.c | 4 +- > gcc/graphite-poly.c | 14 +-- > gcc/graphite-poly.h | 3 +- > gcc/graphite-scop-detection.c | 231 > ++++++++++----------------------------- > gcc/graphite-sese-to-poly.c | 19 ++-- > gcc/sese.c | 1 + > gcc/sese.h | 3 + > 9 files changed, 83 insertions(+), 198 deletions(-) > > diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c > index 8829cb4..e879429 100644 > --- a/gcc/graphite-dependences.c > +++ b/gcc/graphite-dependences.c > @@ -335,7 +335,7 @@ scop_get_dependences (scop_p scop) > isl_union_map *dependences; > > if (!scop->must_raw) > - compute_deps (scop, SCOP_BBS (scop), > + compute_deps (scop, scop->pbbs, > &scop->must_raw, &scop->may_raw, > &scop->must_raw_no_source, &scop->may_raw_no_source, > &scop->must_war, &scop->may_war, > diff --git a/gcc/graphite-isl-ast-to-gimple.c > b/gcc/graphite-isl-ast-to-gimple.c > index f4e7edf..2f2e2ba 100644 > --- a/gcc/graphite-isl-ast-to-gimple.c > +++ b/gcc/graphite-isl-ast-to-gimple.c > @@ -940,7 +940,7 @@ int get_max_schedule_dimensions (scop_p scop) > poly_bb_p pbb; > int schedule_dims = 0; > > - FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) > + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) > { > int pbb_schedule_dims = isl_map_dim (pbb->transformed, isl_dim_out); > if (pbb_schedule_dims > schedule_dims) > @@ -987,7 +987,7 @@ generate_isl_schedule (scop_p scop) > isl_union_map *schedule_isl = > isl_union_map_empty (isl_set_get_space (scop->param_context)); > > - FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) > + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) > { > /* Dead code elimination: when the domain of a PBB is empty, > don't generate code for the PBB. */ > diff --git a/gcc/graphite-optimize-isl.c b/gcc/graphite-optimize-isl.c > index 2bae417..090bc01 100644 > --- a/gcc/graphite-optimize-isl.c > +++ b/gcc/graphite-optimize-isl.c > @@ -58,7 +58,7 @@ scop_get_domains (scop_p scop ATTRIBUTE_UNUSED) > isl_space *space = isl_set_get_space (scop->param_context); > isl_union_set *res = isl_union_set_empty (space); > > - FOR_EACH_VEC_ELT (scop->bbs, i, pbb) > + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) > res = isl_union_set_add_set (res, isl_set_copy (pbb->domain)); > > return res; > @@ -270,7 +270,7 @@ apply_schedule_map_to_scop (scop_p scop, isl_union_map > *schedule_map) > int i; > poly_bb_p pbb; > > - FOR_EACH_VEC_ELT (scop->bbs, i, pbb) > + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) > { > isl_set *domain = isl_set_copy (pbb->domain); > isl_map *stmt_schedule; > diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c > index 39e7aa4..84ecee0 100644 > --- a/gcc/graphite-poly.c > +++ b/gcc/graphite-poly.c > @@ -87,7 +87,7 @@ print_iteration_domains (FILE *file, scop_p scop, int > verbosity) > int i; > poly_bb_p pbb; > > - FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) > + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) > print_iteration_domain (file, pbb, verbosity); > } > > @@ -294,7 +294,7 @@ remove_gbbs_in_scop (scop_p scop) > int i; > poly_bb_p pbb; > > - FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) > + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) > free_gimple_poly_bb (PBB_BLACK_BOX (pbb)); > } > > @@ -320,7 +320,7 @@ new_scop (edge entry, edge exit) > scop->must_waw_no_source = NULL; > scop->may_waw_no_source = NULL; > scop_set_region (scop, region); > - SCOP_BBS (scop).create (3); > + scop->pbbs.create (3); > POLY_SCOP_P (scop) = false; > scop->drs.create (3); > > @@ -338,10 +338,10 @@ free_scop (scop_p scop) > remove_gbbs_in_scop (scop); > free_sese_info (SCOP_REGION (scop)); > > - FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) > + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) > free_poly_bb (pbb); > > - SCOP_BBS (scop).release (); > + scop->pbbs.release (); > > isl_set_free (scop->param_context); > isl_union_map_free (scop->must_raw); > @@ -625,9 +625,9 @@ print_scop (FILE *file, scop_p scop, int verbosity) > if (verbosity > 0) > fprintf (file, "# Number of statements\n"); > > - fprintf (file, "%d\n", SCOP_BBS (scop).length ()); > + fprintf (file, "%d\n", scop->pbbs.length ()); > > - FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) > + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) > print_pbb (file, pbb, verbosity); > > fprintf (file, "#)\n"); > diff --git a/gcc/graphite-poly.h b/gcc/graphite-poly.h > index 977f97e..e477439 100644 > --- a/gcc/graphite-poly.h > +++ b/gcc/graphite-poly.h > @@ -415,7 +415,7 @@ struct scop > /* All the basic blocks in this scop that contain memory references > and that will be represented as statements in the polyhedral > representation. */ > - vec<poly_bb_p> bbs; > + vec<poly_bb_p> pbbs; > > /* All the data references in this scop. */ > vec<dr_info> drs; > @@ -451,7 +451,6 @@ struct scop > bool poly_scop_p; > }; > > -#define SCOP_BBS(S) (S->bbs) > #define SCOP_REGION(S) (S->region) > #define SCOP_CONTEXT(S) (NULL) > #define POLY_SCOP_P(S) (S->poly_scop_p) > diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c > index 43e03a6..6c0987d 100644 > --- a/gcc/graphite-scop-detection.c > +++ b/gcc/graphite-scop-detection.c > @@ -113,34 +113,6 @@ same_close_phi_node (gphi *p1, gphi *p2) > gimple_phi_arg_def (p2, 0), 0); > } > > -/* Compare the depth of two basic_block's P1 and P2. */ > - > -static int > -compare_bb_depths (const void *p1, const void *p2) > -{ > - const_basic_block const bb1 = *(const_basic_block const *)p1; > - const_basic_block const bb2 = *(const_basic_block const *)p2; > - int d1 = loop_depth (bb1->loop_father); > - int d2 = loop_depth (bb2->loop_father); > - > - if (d1 < d2) > - return 1; > - > - if (d1 > d2) > - return -1; > - > - return 0; > -} > - > -/* Sort the basic blocks from DOM such that the first are the ones at > - a deepest loop level. */ > - > -static void > -graphite_sort_dominated_info (vec<basic_block> dom) > -{ > - dom.qsort (compare_bb_depths); > -} > - > static void make_close_phi_nodes_unique (basic_block bb); > > /* Remove the close phi node at GSI and replace its rhs with the rhs > @@ -509,25 +481,6 @@ public: > > static bool can_represent_loop (loop_p loop, sese_l scop); > > - /* Generates a polyhedral black box only if the bb contains interesting > - information. */ > - > - static gimple_poly_bb_p try_generate_gimple_bb (scop_p scop, basic_block > bb); > - > - /* Returns true if all predecessors of BB, that are not dominated by BB, > are > - marked in MAP. The predecessors dominated by BB are loop latches and > will > - be handled after BB. */ > - > - static bool all_non_dominated_preds_marked_p (basic_block bb, sbitmap map); > - > - /* Recursive helper function for build_scops_bbs. */ > - > - static void build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block > bb); > - > - /* Gather the basic blocks belonging to the SCOP. */ > - > - static void build_scop_bbs (scop_p scop); > - > /* Returns the number of pbbs that are in loops contained in SCOP. */ > > static int nb_pbbs_in_loops (scop_p scop); > @@ -1519,102 +1472,6 @@ scop_detection::loop_body_is_valid_scop (loop_p loop, > sese_l scop) const > return true; > } > > -/* Generates a polyhedral black box only if the bb contains interesting > - information. */ > - > -gimple_poly_bb_p > -scop_detection::try_generate_gimple_bb (scop_p scop, basic_block bb) > -{ > - vec<data_reference_p> drs; > - drs.create (5); > - sese_l region = scop->region->region; > - loop_p nest = outermost_loop_in_sese (region, bb); > - > - loop_p loop = bb->loop_father; > - if (!loop_in_sese_p (loop, region)) > - loop = nest; > - > - gimple_stmt_iterator gsi; > - for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) > - { > - gimple *stmt = gsi_stmt (gsi); > - if (is_gimple_debug (stmt)) > - continue; > - > - graphite_find_data_references_in_stmt (nest, loop, stmt, &drs); > - } > - > - return new_gimple_poly_bb (bb, drs); > -} > - > -/* Returns true if all predecessors of BB, that are not dominated by BB, are > - marked in MAP. The predecessors dominated by BB are loop latches and will > - be handled after BB. */ > - > -bool > -scop_detection::all_non_dominated_preds_marked_p (basic_block bb, sbitmap > map) > -{ > - edge e; > - edge_iterator ei; > - > - FOR_EACH_EDGE (e, ei, bb->preds) > - if (!bitmap_bit_p (map, e->src->index) > - && !dominated_by_p (CDI_DOMINATORS, e->src, bb)) > - return false; > - > - return true; > -} > - > -/* Recursive helper function for build_scops_bbs. */ > - > -void > -scop_detection::build_scop_bbs_1 (scop_p scop, sbitmap visited, basic_block > bb) > -{ > - if (bitmap_bit_p (visited, bb->index) > - || !bb_in_sese_p (bb, scop->region->region)) > - return; > - > - poly_bb_p pbb = new_poly_bb (scop, try_generate_gimple_bb (scop, bb)); > - SCOP_BBS (scop).safe_push (pbb); > - bitmap_set_bit (visited, bb->index); > - > - vec<basic_block> dom = get_dominated_by (CDI_DOMINATORS, bb); > - > - if (!dom.exists ()) > - return; > - > - graphite_sort_dominated_info (dom); > - > - while (!dom.is_empty ()) > - { > - int i; > - basic_block dom_bb; > - > - FOR_EACH_VEC_ELT (dom, i, dom_bb) > - if (all_non_dominated_preds_marked_p (dom_bb, visited)) > - { > - build_scop_bbs_1 (scop, visited, dom_bb); > - dom.unordered_remove (i); > - break; > - } > - } > - > - dom.release (); > -} > - > -/* Gather the basic blocks belonging to the SCOP. */ > - > -void > -scop_detection::build_scop_bbs (scop_p scop) > -{ > - sbitmap visited = sbitmap_alloc (last_basic_block_for_fn (cfun)); > - sese_l region = scop->region->region; > - > - bitmap_clear (visited); > - build_scop_bbs_1 (scop, visited, region.entry->dest); > - sbitmap_free (visited); > -} > - > /* Returns the number of pbbs that are in loops contained in SCOP. */ > > int > @@ -1624,7 +1481,7 @@ scop_detection::nb_pbbs_in_loops (scop_p scop) > poly_bb_p pbb; > int res = 0; > > - FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) > + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) > if (loop_in_sese_p (gbb_loop (PBB_BLACK_BOX (pbb)), > scop->region->region)) > res++; > > @@ -1783,28 +1640,57 @@ find_scop_parameters (scop_p scop) > > /* Find the parameters used in data accesses. */ > poly_bb_p pbb; > - FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) > + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) > find_params_in_bb (region, PBB_BLACK_BOX (pbb)); > > int nbp = sese_nb_params (region); > scop_set_nb_params (scop, nbp); > } > > -class sese_dom_walker : public dom_walker > +/* Generates a polyhedral black box only if the bb contains interesting > + information. */ > + > +static gimple_poly_bb_p > +try_generate_gimple_bb (scop_p scop, basic_block bb) > +{ > + vec<data_reference_p> drs; > + drs.create (5); > + sese_l region = scop->region->region; > + loop_p nest = outermost_loop_in_sese (region, bb); > + > + loop_p loop = bb->loop_father; > + if (!loop_in_sese_p (loop, region)) > + loop = nest; > + > + gimple_stmt_iterator gsi; > + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) > + { > + gimple *stmt = gsi_stmt (gsi); > + if (is_gimple_debug (stmt)) > + continue; > + > + graphite_find_data_references_in_stmt (nest, loop, stmt, &drs); > + } > + > + return new_gimple_poly_bb (bb, drs); > +} > + > +/* Gather BBs and conditions for a SCOP. */ > +class gather_bbs : public dom_walker > { > public: > - sese_dom_walker (cdi_direction, sese_l); > + gather_bbs (cdi_direction, scop_p); > > virtual void before_dom_children (basic_block); > virtual void after_dom_children (basic_block); > > private: > - auto_vec<gimple *, 3> m_conditions, m_cases; > - sese_l m_region; > + auto_vec<gimple *, 3> conditions, cases; > + scop_p scop; > }; > } > -sese_dom_walker::sese_dom_walker (cdi_direction direction, sese_l region) > - : dom_walker (direction), m_region (region) > +gather_bbs::gather_bbs (cdi_direction direction, scop_p scop) > + : dom_walker (direction), scop (scop) > { > } > > @@ -1812,50 +1698,48 @@ sese_dom_walker::sese_dom_walker (cdi_direction > direction, sese_l region) > blocks. */ > > void > -sese_dom_walker::before_dom_children (basic_block bb) > +gather_bbs::before_dom_children (basic_block bb) > { > - gimple_poly_bb_p gbb; > - gcond *stmt; > - > - if (!bb_in_sese_p (bb, m_region)) > + if (!bb_in_sese_p (bb, scop->region->region)) > return; > > - stmt = single_pred_cond_non_loop_exit (bb); > + gcond *stmt = single_pred_cond_non_loop_exit (bb); > > if (stmt) > { > edge e = single_pred_edge (bb); > > - m_conditions.safe_push (stmt); > + conditions.safe_push (stmt); > > if (e->flags & EDGE_TRUE_VALUE) > - m_cases.safe_push (stmt); > + cases.safe_push (stmt); > else > - m_cases.safe_push (NULL); > + cases.safe_push (NULL); > } > > - gbb = gbb_from_bb (bb); > + scop->region->bbs.safe_push (bb); > > - if (gbb) > - { > - GBB_CONDITIONS (gbb) = m_conditions.copy (); > - GBB_CONDITION_CASES (gbb) = m_cases.copy (); > - } > + gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb); > + GBB_CONDITIONS (gbb) = conditions.copy (); > + GBB_CONDITION_CASES (gbb) = cases.copy (); > + > + poly_bb_p pbb = new_poly_bb (scop, gbb); > + scop->pbbs.safe_push (pbb); > } > > /* Call-back for dom_walk executed after visiting the dominated > blocks. */ > > void > -sese_dom_walker::after_dom_children (basic_block bb) > +gather_bbs::after_dom_children (basic_block bb) > { > - if (!bb_in_sese_p (bb, m_region)) > + if (!bb_in_sese_p (bb, scop->region->region)) > return; > > if (single_pred_cond_non_loop_exit (bb)) > { > - m_conditions.pop (); > - m_cases.pop (); > + conditions.pop (); > + cases.pop (); > } > } > > @@ -1881,7 +1765,9 @@ build_scops (vec<scop_p> *scops) > { > scop_p scop = new_scop (s.entry, s.exit); > > - sb.build_scop_bbs (scop); > + /* Record all basic blocks and their conditions in REGION. */ > + gather_bbs (CDI_DOMINATORS, scop).walk (cfun->cfg->x_entry_block_ptr); > + > /* Do not optimize a scop containing only PBBs that do not belong > to any loops. */ > if (sb.nb_pbbs_in_loops (scop) == 0) > @@ -1892,9 +1778,6 @@ build_scops (vec<scop_p> *scops) > } > > build_sese_loop_nests (scop->region); > - /* Record all conditions in REGION. */ > - sese_dom_walker (CDI_DOMINATORS, scop->region->region).walk > - (cfun->cfg->x_entry_block_ptr); > > find_scop_parameters (scop); > graphite_dim_t max_dim = PARAM_VALUE > (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS); > diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c > index c9a2964..261e67d 100644 > --- a/gcc/graphite-sese-to-poly.c > +++ b/gcc/graphite-sese-to-poly.c > @@ -329,7 +329,7 @@ build_scop_scattering (scop_p scop) > > int i; > poly_bb_p pbb; > - FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) > + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) > { > gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb); > int prefix = 0; > @@ -808,7 +808,7 @@ add_conditions_to_constraints (scop_p scop) > int i; > poly_bb_p pbb; > > - FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) > + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) > add_conditions_to_domain (pbb); > } > > @@ -904,7 +904,7 @@ build_scop_iteration_domain (scop_p scop) > isl_set_copy (scop->param_context), doms); > > poly_bb_p pbb; > - FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) > + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) > { > loop = pbb_loop (pbb); > > @@ -1138,17 +1138,17 @@ build_scop_drs (scop_p scop) > > /* Remove all the PBBs that do not have data references: these basic > blocks are not handled in the polyhedral representation. */ > - for (i = 0; SCOP_BBS (scop).iterate (i, &pbb); i++) > + for (i = 0; scop->pbbs.iterate (i, &pbb); i++) > if (GBB_DATA_REFS (PBB_BLACK_BOX (pbb)).is_empty ()) > { > free_gimple_poly_bb (PBB_BLACK_BOX (pbb)); > free_poly_bb (pbb); > - SCOP_BBS (scop).ordered_remove (i); > + scop->pbbs.ordered_remove (i); > i--; > } > > data_reference_p dr; > - FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb) > + FOR_EACH_VEC_ELT (scop->pbbs, i, pbb) > if (pbb) > FOR_EACH_VEC_ELT (GBB_DATA_REFS (PBB_BLACK_BOX (pbb)), j, dr) > scop->drs.safe_push (dr_info (dr, -1, pbb)); > @@ -1248,11 +1248,10 @@ new_pbb_from_pbb (scop_p scop, poly_bb_p pbb, > basic_block bb) > gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb); > gimple_poly_bb_p gbb1 = new_gimple_poly_bb (bb, drs); > poly_bb_p pbb1 = new_poly_bb (scop, gbb1); > - int index, n = SCOP_BBS (scop).length (); > + int index, n = scop->pbbs.length (); > > - /* The INDEX of PBB in SCOP_BBS. */ > for (index = 0; index < n; index++) > - if (SCOP_BBS (scop)[index] == pbb) > + if (scop->pbbs[index] == pbb) > break; > > pbb1->domain = isl_set_copy (pbb->domain); > @@ -1262,7 +1261,7 @@ new_pbb_from_pbb (scop_p scop, poly_bb_p pbb, > basic_block bb) > GBB_PBB (gbb1) = pbb1; > GBB_CONDITIONS (gbb1) = GBB_CONDITIONS (gbb).copy (); > GBB_CONDITION_CASES (gbb1) = GBB_CONDITION_CASES (gbb).copy (); > - SCOP_BBS (scop).safe_insert (index + 1, pbb1); > + scop->pbbs.safe_insert (index + 1, pbb1); > } > > /* Insert on edge E the assignment "RES := EXPR". */ > diff --git a/gcc/sese.c b/gcc/sese.c > index 6bb1322..aa19c68 100644 > --- a/gcc/sese.c > +++ b/gcc/sese.c > @@ -265,6 +265,7 @@ new_sese_info (edge entry, edge exit) > SESE_LOOP_NEST (region).create (3); > SESE_PARAMS (region).create (3); > region->parameter_rename_map = new parameter_rename_map_t; > + region->bbs.create (3); > > return region; > } > diff --git a/gcc/sese.h b/gcc/sese.h > index 2cda5e1..d429d58 100644 > --- a/gcc/sese.h > +++ b/gcc/sese.h > @@ -78,6 +78,9 @@ typedef struct sese_info_t > /* Loops completely contained in this SESE. */ > bitmap loops; > vec<loop_p> loop_nest; > + > + /* Basic blocks contained in this SESE. */ > + vec<basic_block> bbs; > } *sese_info_p; > > #define SESE_PARAMS(S) (S->params) > -- > 2.1.0.243.g30d45f7 >