From ae11f03bac138ee5e7c74c96bf4b4ec91daa419a Mon Sep 17 00:00:00 2001 From: spop Date: Wed, 25 Nov 2009 04:48:51 +0000 Subject: [PATCH] 2009-09-17 Li Feng PR middle-end/41118 * graphite-dependences.c (poly_drs_may_alias_p): Adjust definition. (pddr_original_scattering): Make sure 2 pdr2 in the same base object set. (graphite_carried_dependence_level_k): Ditto. * graphite-poly.c (new_poly_dr): Add init of PDR_BASE_OBJECT_SET. * graphite-poly.h (struct poly_dr): Add member dr_base_object_set. (new_poly_dr): Adjust declaration. * graphite-sese-to-poly.c (free_data_refs_aux): New. (free_gimple_bb): Added free_data_refs_aux. (build_poly_dr): Add dr_base_object_set. (partition_drs_to_sets): New. (dr_same_base_object_p): New. (build_alias_set_for_drs): New. (build_base_object_set_for_drs): New. (build_scop_drs): Add build_base_obj_set_for_drs. * graphite-sese-to-poly.h: Added #define for alias set number index and base object set index. * libgomp/testsuite/libgomp.graphite/force-parallel-6.c: Refine tests. * libgomp/testsuite/libgomp.graphite/pr4118.c: New. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@154549 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog.graphite | 22 +++++++ gcc/graphite-dependences.c | 20 +++++-- gcc/graphite-poly.c | 3 +- gcc/graphite-poly.h | 17 ++++-- gcc/graphite-sese-to-poly.c | 67 +++++++++++++++++----- gcc/graphite-sese-to-poly.h | 3 + .../testsuite/libgomp.graphite/force-parallel-6.c | 2 +- 7 files changed, 108 insertions(+), 26 deletions(-) diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite index 10afccd..e4b5931 100644 --- a/gcc/ChangeLog.graphite +++ b/gcc/ChangeLog.graphite @@ -1,3 +1,25 @@ +2009-09-17 Li Feng + + PR middle-end/41118 + * graphite-dependences.c (poly_drs_may_alias_p): Adjust definition. + (pddr_original_scattering): Make sure 2 pdr2 in the same base object set. + (graphite_carried_dependence_level_k): Ditto. + * graphite-poly.c (new_poly_dr): Add init of PDR_BASE_OBJECT_SET. + * graphite-poly.h (struct poly_dr): Add member dr_base_object_set. + (new_poly_dr): Adjust declaration. + * graphite-sese-to-poly.c (free_data_refs_aux): New. + (free_gimple_bb): Added free_data_refs_aux. + (build_poly_dr): Add dr_base_object_set. + (partition_drs_to_sets): New. + (dr_same_base_object_p): New. + (build_alias_set_for_drs): New. + (build_base_object_set_for_drs): New. + (build_scop_drs): Add build_base_obj_set_for_drs. + * graphite-sese-to-poly.h: Added #define for alias set number index and + base object set index. + * libgomp/testsuite/libgomp.graphite/force-parallel-6.c: Refine tests. + * libgomp/testsuite/libgomp.graphite/pr4118.c: New. + 2009-09-16 Alexander Monakov * graphite-sese-to-poly.c (pdr_add_data_dimensions): Add bounds only diff --git a/gcc/graphite-dependences.c b/gcc/graphite-dependences.c index 7fce3b3..f7b8c73 100644 --- a/gcc/graphite-dependences.c +++ b/gcc/graphite-dependences.c @@ -494,8 +494,12 @@ dependence_polyhedron (poly_bb_p pbb1, poly_bb_p pbb2, return res; } +static bool +poly_drs_may_alias_p (poly_dr_p pdr1, poly_dr_p pdr2); + /* Returns the PDDR corresponding to the original schedule, or NULL if - the dependence relation is empty. */ + the dependence relation is empty or unknown (Can't judge dependency + under polyhedral model. */ static poly_ddr_p pddr_original_scattering (poly_bb_p pbb1, poly_bb_p pbb2, @@ -507,8 +511,9 @@ pddr_original_scattering (poly_bb_p pbb1, poly_bb_p pbb2, ppl_Polyhedron_t so1 = PBB_ORIGINAL_SCATTERING (pbb1); ppl_Polyhedron_t so2 = PBB_ORIGINAL_SCATTERING (pbb2); - if (PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2) - || (pdr_read_p (pdr1) && pdr_read_p (pdr2))) + if ((pdr_read_p (pdr1) && pdr_read_p (pdr2)) + || PDR_BASE_OBJECT_SET (pdr1) != PDR_BASE_OBJECT_SET (pdr2) + || PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2)) return NULL; pddr = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, so1, so2, @@ -706,14 +711,19 @@ graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2, ppl_dimension_type dim; bool empty_p; poly_ddr_p pddr; + int obj_base_set1 = PDR_BASE_OBJECT_SET (pdr1); + int obj_base_set2 = PDR_BASE_OBJECT_SET (pdr2); - if ((PDR_TYPE (pdr1) == PDR_READ && PDR_TYPE (pdr2) == PDR_READ) + if ((pdr_read_p (pdr1) && pdr_read_p (pdr2)) || !poly_drs_may_alias_p (pdr1, pdr2)) return false; - if (PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2)) + if (obj_base_set1 != obj_base_set2) return true; + if (PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2)) + return false; + pddr = dependence_polyhedron (pbb1, pbb2, d1, d2, pdr1, pdr2, so1, so2, true, false); diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c index 535912a..e06bb6d 100644 --- a/gcc/graphite-poly.c +++ b/gcc/graphite-poly.c @@ -307,7 +307,7 @@ pbb_remove_duplicate_pdrs (poly_bb_p pbb) NB_SUBSCRIPTS. */ void -new_poly_dr (poly_bb_p pbb, +new_poly_dr (poly_bb_p pbb, int dr_base_object_set, ppl_Pointset_Powerset_C_Polyhedron_t accesses, enum poly_dr_type type, void *cdr, graphite_dim_t nb_subscripts) { @@ -315,6 +315,7 @@ new_poly_dr (poly_bb_p pbb, poly_dr_p pdr = XNEW (struct poly_dr); PDR_ID (pdr) = id++; + PDR_BASE_OBJECT_SET (pdr) = dr_base_object_set; PDR_NB_REFS (pdr) = 1; PDR_PBB (pdr) = pbb; PDR_ACCESSES (pdr) = accesses; diff --git a/gcc/graphite-poly.h b/gcc/graphite-poly.h index 7fe1113..a96d5c2 100644 --- a/gcc/graphite-poly.h +++ b/gcc/graphite-poly.h @@ -72,13 +72,13 @@ struct poly_dr The polyhedron contains these dimensions: - - The alias set (a): - Every memory access is classified in at least one alias set. + - The alias set (a): + Every memory access is classified in at least one alias set. - - The subscripts (s_0, ..., s_n): - The memory is accessed using zero or more subscript dimensions. + - The subscripts (s_0, ..., s_n): + The memory is accessed using zero or more subscript dimensions. - - The iteration domain (variables and parameters) + - The iteration domain (variables and parameters) Do not hardcode the dimensions. Use the following accessor functions: - pdr_alias_set_dim @@ -135,6 +135,10 @@ struct poly_dr | 0 0 0 -1 15 = 0 */ ppl_Pointset_Powerset_C_Polyhedron_t accesses; + /* Data reference's base object set number, we must assure 2 pdrs are in the + same base object set before dependency checking. */ + int dr_base_object_set; + /* The number of subscripts. */ graphite_dim_t nb_subscripts; }; @@ -145,9 +149,10 @@ struct poly_dr #define PDR_PBB(PDR) (PDR->pbb) #define PDR_TYPE(PDR) (PDR->type) #define PDR_ACCESSES(PDR) (PDR->accesses) +#define PDR_BASE_OBJECT_SET(PDR) (PDR->dr_base_object_set) #define PDR_NB_SUBSCRIPTS(PDR) (PDR->nb_subscripts) -void new_poly_dr (poly_bb_p, ppl_Pointset_Powerset_C_Polyhedron_t, +void new_poly_dr (poly_bb_p, int, ppl_Pointset_Powerset_C_Polyhedron_t, enum poly_dr_type, void *, graphite_dim_t); void free_poly_dr (poly_dr_p); void debug_pdr (poly_dr_p); diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c index fff25f1..e2c9cf8 100644 --- a/gcc/graphite-sese-to-poly.c +++ b/gcc/graphite-sese-to-poly.c @@ -282,6 +282,20 @@ new_gimple_bb (basic_block bb, VEC (data_reference_p, heap) *drs) return gbb; } +static void +free_data_refs_aux (VEC (data_reference_p, heap) *datarefs) +{ + unsigned int i; + struct data_reference *dr; + + for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) + if (!dr->aux) + { + free (dr->aux); + dr->aux = NULL; + } +} + /* Frees GBB. */ static void @@ -290,6 +304,7 @@ free_gimple_bb (struct gimple_bb *gbb) if (GBB_CLOOG_IV_TYPES (gbb)) htab_delete (GBB_CLOOG_IV_TYPES (gbb)); + free_data_refs_aux (GBB_DATA_REFS (gbb)); free_data_refs (GBB_DATA_REFS (gbb)); VEC_free (gimple, heap, GBB_CONDITIONS (gbb)); @@ -1546,11 +1561,7 @@ pdr_add_alias_set (ppl_Polyhedron_t accesses, data_reference_p dr, int alias_set_num = 0; if (dr->aux != NULL) - { - alias_set_num = *((int *)(dr->aux)); - free (dr->aux); - dr->aux = NULL; - } + alias_set_num = ((int *)(dr->aux))[ALIAS_SET_INDEX]; ppl_new_Linear_Expression_with_dimension (&alias, accessp_nb_dims); @@ -1675,6 +1686,7 @@ build_poly_dr (data_reference_p dr, poly_bb_p pbb) ppl_Pointset_Powerset_C_Polyhedron_t accesses_ps; ppl_dimension_type dom_nb_dims; ppl_dimension_type accessp_nb_dims; + int dr_base_object_set; ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb), &dom_nb_dims); @@ -1689,14 +1701,17 @@ build_poly_dr (data_reference_p dr, poly_bb_p pbb) ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&accesses_ps, accesses); ppl_delete_Polyhedron (accesses); - new_poly_dr (pbb, accesses_ps, DR_IS_READ (dr) ? PDR_READ : PDR_WRITE, dr, - DR_NUM_DIMENSIONS (dr)); -} -/* Group each data reference in DRS with it's alias set num. */ + dr_base_object_set = ((int *)(dr->aux))[BASE_OBJECT_SET_INDEX]; + + new_poly_dr (pbb, dr_base_object_set, accesses_ps, DR_IS_READ (dr) ? PDR_READ : PDR_WRITE, + dr, DR_NUM_DIMENSIONS (dr)); +} static void -build_alias_set_for_drs (VEC (data_reference_p, heap) **drs) +partition_drs_to_sets (VEC (data_reference_p, heap) **drs, int choice, + bool (* edge_exist_p) (const struct data_reference *, + const struct data_reference *)) { int num_vertex = VEC_length (data_reference_p, *drs); struct graph *g = new_graph (num_vertex); @@ -1707,7 +1722,7 @@ build_alias_set_for_drs (VEC (data_reference_p, heap) **drs) for (i = 0; VEC_iterate (data_reference_p, *drs, i, dr1); i++) for (j = i+1; VEC_iterate (data_reference_p, *drs, j, dr2); j++) - if (dr_may_alias_p (dr1, dr2)) + if ((*edge_exist_p) (dr1, dr2)) { add_edge (g, i, j); add_edge (g, j, i); @@ -1722,14 +1737,38 @@ build_alias_set_for_drs (VEC (data_reference_p, heap) **drs) for (i = 0; i < g->n_vertices; i++) { data_reference_p dr = VEC_index (data_reference_p, *drs, i); - dr->aux = XNEW (int); - *((int *)(dr->aux)) = g->vertices[i].component + 1; + if (!dr->aux) + dr->aux = XNEWVEC (int, 2); + ((int *)(dr->aux))[choice] = g->vertices[i].component + 1; } free (queue); free_graph (g); } +static bool +dr_same_base_object_p (const struct data_reference *dr1, + const struct data_reference *dr2) +{ + return operand_equal_p (DR_BASE_OBJECT (dr1), DR_BASE_OBJECT (dr2), 0); +} + +/* Group each data reference in DRS with it's alias set num. */ + +static void +build_alias_set_for_drs (VEC (data_reference_p, heap) **drs) +{ + partition_drs_to_sets (drs, ALIAS_SET_INDEX, dr_may_alias_p); +} + +/* Group each data reference in DRS with it's base object set num. */ + +static void +build_base_obj_set_for_drs (VEC (data_reference_p, heap) **drs) +{ + partition_drs_to_sets (drs, BASE_OBJECT_SET_INDEX, dr_same_base_object_p); +} + /* Build the data references for PBB. */ static void @@ -1761,6 +1800,8 @@ build_scop_drs (scop_p scop) } build_alias_set_for_drs (&drs); + build_base_obj_set_for_drs (&drs); + VEC_free (data_reference_p, heap, drs); for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++) diff --git a/gcc/graphite-sese-to-poly.h b/gcc/graphite-sese-to-poly.h index d6df07f..9379c14 100644 --- a/gcc/graphite-sese-to-poly.h +++ b/gcc/graphite-sese-to-poly.h @@ -21,6 +21,9 @@ along with GCC; see the file COPYING3. If not see #ifndef GCC_GRAPHITE_SESE_TO_POLY_H #define GCC_GRAPHITE_SESE_TO_POLY_H +#define ALIAS_SET_INDEX 0 +#define BASE_OBJECT_SET_INDEX 1 + bool build_poly_scop (scop_p); void check_poly_representation (scop_p); diff --git a/libgomp/testsuite/libgomp.graphite/force-parallel-6.c b/libgomp/testsuite/libgomp.graphite/force-parallel-6.c index e961fc0..dcaaf48 100644 --- a/libgomp/testsuite/libgomp.graphite/force-parallel-6.c +++ b/libgomp/testsuite/libgomp.graphite/force-parallel-6.c @@ -31,7 +31,7 @@ int main(void) } /* Check that parallel code generation part make the right answer. */ -/* { dg-final { scan-tree-dump-times "1 loops carried no dependency" 2 "graphite" } } */ +/* { dg-final { scan-tree-dump-times "1 loops carried no dependency" 1 "graphite" } } */ /* { dg-final { cleanup-tree-dump "graphite" } } */ /* { dg-final { scan-tree-dump-times "loopfn.0" 5 "optimized" } } */ /* { dg-final { cleanup-tree-dump "parloops" } } */ -- 2.7.4