| Message ID | 1444239710-26682-1-git-send-email-s.pop@samsung.com |
|---|---|
| State | New |
| Headers | show |
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.k7@samsung.com> > Sebastian Pop <s.pop@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 >
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)
2015-10-06 Aditya Kumar <aditya.k7@samsung.com> Sebastian Pop <s.pop@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(-)