Mercurial > hg > CbC > CbC_gcc
diff gcc/graphite-dependences.c @ 67:f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
author | nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 22 Mar 2011 17:18:12 +0900 |
parents | b7f97abdc517 |
children | 04ced10e8804 |
line wrap: on
line diff
--- a/gcc/graphite-dependences.c Tue May 25 18:58:51 2010 +0900 +++ b/gcc/graphite-dependences.c Tue Mar 22 17:18:12 2011 +0900 @@ -22,68 +22,20 @@ #include "config.h" #include "system.h" #include "coretypes.h" -#include "tm.h" -#include "ggc.h" -#include "tree.h" -#include "rtl.h" -#include "basic-block.h" -#include "diagnostic.h" #include "tree-flow.h" -#include "toplev.h" #include "tree-dump.h" -#include "timevar.h" #include "cfgloop.h" #include "tree-chrec.h" #include "tree-data-ref.h" #include "tree-scalar-evolution.h" -#include "tree-pass.h" -#include "domwalk.h" -#include "pointer-set.h" -#include "gimple.h" +#include "sese.h" #ifdef HAVE_cloog -#include "cloog/cloog.h" #include "ppl_c.h" -#include "sese.h" #include "graphite-ppl.h" -#include "graphite.h" #include "graphite-poly.h" #include "graphite-dependences.h" - -/* Returns a new polyhedral Data Dependence Relation (DDR). SOURCE is - the source data reference, SINK is the sink data reference. When - the Data Dependence Polyhedron DDP is not NULL or not empty, SOURCE - and SINK are in dependence as described by DDP. */ - -static poly_ddr_p -new_poly_ddr (poly_dr_p source, poly_dr_p sink, - ppl_Pointset_Powerset_C_Polyhedron_t ddp, - bool original_scattering_p) -{ - poly_ddr_p pddr = XNEW (struct poly_ddr); - - PDDR_SOURCE (pddr) = source; - PDDR_SINK (pddr) = sink; - PDDR_DDP (pddr) = ddp; - PDDR_ORIGINAL_SCATTERING_P (pddr) = original_scattering_p; - - if (!ddp || ppl_Pointset_Powerset_C_Polyhedron_is_empty (ddp)) - PDDR_KIND (pddr) = no_dependence; - else - PDDR_KIND (pddr) = has_dependence; - - return pddr; -} - -/* Free the poly_ddr_p P. */ - -void -free_poly_ddr (void *p) -{ - poly_ddr_p pddr = (poly_ddr_p) p; - ppl_delete_Pointset_Powerset_C_Polyhedron (PDDR_DDP (pddr)); - free (pddr); -} +#include "graphite-cloog-util.h" /* Comparison function for poly_ddr hash table. */ @@ -194,6 +146,7 @@ fprintf (file, "\n dependence polyhedron (\n"); print_dependence_polyhedron_layout (file, pddr); ppl_print_powerset_matrix (file, PDDR_DDP (pddr)); + ppl_io_fprint_Pointset_Powerset_C_Polyhedron (file, PDDR_DDP (pddr)); fprintf (file, ")\n"); } @@ -202,7 +155,7 @@ /* Prints to STDERR the poly_ddr_p PDDR. */ -void +DEBUG_FUNCTION void debug_pddr (poly_ddr_p pddr) { print_pddr (stderr, pddr); @@ -347,7 +300,9 @@ /* Builds scheduling inequality constraints: when DIRECTION is 1 builds a GE constraint, 0 builds an EQ constraint, - -1 builds a LE constraint. */ + -1 builds a LE constraint. + DIM is the dimension of the scheduling space. + POS and POS + OFFSET are the dimensions that are related. */ static ppl_Pointset_Powerset_C_Polyhedron_t build_pairwise_scheduling (graphite_dim_t dim, @@ -358,23 +313,28 @@ ppl_Pointset_Powerset_C_Polyhedron_t res; ppl_Polyhedron_t equalities; ppl_Constraint_t cstr; + graphite_dim_t a = pos; + graphite_dim_t b = pos + offset; ppl_new_C_Polyhedron_from_space_dimension (&equalities, dim, 0); switch (direction) { - case -1: - cstr = ppl_build_relation (dim, pos, pos + offset, 1, + case 1: + /* Builds "a + 1 <= b. */ + cstr = ppl_build_relation (dim, a, b, 1, PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL); break; case 0: - cstr = ppl_build_relation (dim, pos, pos + offset, 0, + /* Builds "a = b. */ + cstr = ppl_build_relation (dim, a, b, 0, PPL_CONSTRAINT_TYPE_EQUAL); break; - case 1: - cstr = ppl_build_relation (dim, pos, pos + offset, -1, + case -1: + /* Builds "a >= b + 1. */ + cstr = ppl_build_relation (dim, a, b, -1, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); break; @@ -417,7 +377,7 @@ lex = build_pairwise_scheduling (dim, 0, offset, direction); ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag); - if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (lex)) + if (!ppl_powerset_is_empty (lex)) ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex); ppl_delete_Pointset_Powerset_C_Polyhedron (lex); @@ -430,10 +390,13 @@ ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (bag, sceq); ppl_delete_Pointset_Powerset_C_Polyhedron (sceq); + if (ppl_powerset_is_empty (bag)) + break; + lex = build_pairwise_scheduling (dim, i + 1, offset, direction); ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag); - if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (lex)) + if (!ppl_powerset_is_empty (lex)) ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex); ppl_delete_Pointset_Powerset_C_Polyhedron (lex); @@ -458,8 +421,8 @@ relation, from PDR2 to PDR1. */ static ppl_Pointset_Powerset_C_Polyhedron_t -dependence_polyhedron_1 (poly_dr_p pdr1, poly_dr_p pdr2, - int direction, bool original_scattering_p) +dependence_polyhedron (poly_dr_p pdr1, poly_dr_p pdr2, + int direction, bool original_scattering_p) { poly_bb_p pbb1 = PDR_PBB (pdr1); poly_bb_p pbb2 = PDR_PBB (pdr2); @@ -479,6 +442,7 @@ ppl_Pointset_Powerset_C_Polyhedron_t res; ppl_Pointset_Powerset_C_Polyhedron_t idr1, idr2; ppl_Pointset_Powerset_C_Polyhedron_t sc1, sc2, dreq; + ppl_Pointset_Powerset_C_Polyhedron_t lex; gcc_assert (PBB_SCOP (pbb1) == PBB_SCOP (pbb2)); @@ -512,16 +476,14 @@ ppl_delete_Pointset_Powerset_C_Polyhedron (idr2); ppl_delete_Pointset_Powerset_C_Polyhedron (dreq); - if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (res)) - { - ppl_Pointset_Powerset_C_Polyhedron_t lex = - build_lexicographical_constraint (res, dim, MIN (tdim1, tdim2), + if (ppl_powerset_is_empty (res)) + return NULL; + + lex = build_lexicographical_constraint (res, dim, MIN (tdim1, tdim2), tdim1 + ddim1, direction); - ppl_delete_Pointset_Powerset_C_Polyhedron (res); - res = lex; - } + ppl_delete_Pointset_Powerset_C_Polyhedron (res); - return res; + return lex; } /* Build the dependence polyhedron for data references PDR1 and PDR2. @@ -532,12 +494,12 @@ relation, from PDR2 to PDR1. */ static poly_ddr_p -dependence_polyhedron (poly_dr_p pdr1, poly_dr_p pdr2, - int direction, bool original_scattering_p) +new_poly_ddr (poly_dr_p pdr1, poly_dr_p pdr2, + int direction, bool original_scattering_p) { PTR *x = NULL; poly_ddr_p res; - ppl_Pointset_Powerset_C_Polyhedron_t ddp; + bool may_alias; /* Return the PDDR from the cache if it already has been computed. */ if (original_scattering_p) @@ -554,28 +516,50 @@ return (poly_ddr_p) *x; } - 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) - || !poly_drs_may_alias_p (pdr1, pdr2)) - ddp = NULL; - else - ddp = dependence_polyhedron_1 (pdr1, pdr2, direction, - original_scattering_p); + res = XNEW (struct poly_ddr); + PDDR_SOURCE (res) = pdr1; + PDDR_SINK (res) = pdr2; + PDDR_DDP (res) = NULL; + PDDR_ORIGINAL_SCATTERING_P (res) = original_scattering_p; + PDDR_KIND (res) = unknown_dependence; - res = new_poly_ddr (pdr1, pdr2, ddp, original_scattering_p); + may_alias = poly_drs_may_alias_p (pdr1, pdr2); if (!(pdr_read_p (pdr1) && pdr_read_p (pdr2)) && PDR_BASE_OBJECT_SET (pdr1) != PDR_BASE_OBJECT_SET (pdr2) - && poly_drs_may_alias_p (pdr1, pdr2)) + && may_alias) PDDR_KIND (res) = unknown_dependence; + else if (!(pdr_read_p (pdr1) && pdr_read_p (pdr2)) + && same_pdr_p (pdr1, pdr2) + && may_alias) + { + PDDR_DDP (res) = dependence_polyhedron (pdr1, pdr2, direction, + original_scattering_p); + if (PDDR_DDP (res)) + PDDR_KIND (res) = has_dependence; + else + PDDR_KIND (res) = no_dependence; + } + else + PDDR_KIND (res) = no_dependence; + if (original_scattering_p) *x = res; return res; } +/* Free the data dependence relation poly_ddr_p P. */ + +void +free_poly_ddr (void *p) +{ + poly_ddr_p pddr = (poly_ddr_p) p; + ppl_delete_Pointset_Powerset_C_Polyhedron (PDDR_DDP (pddr)); + free (pddr); +} + /* Return true when the data dependence relation between the data references PDR1 belonging to PBB1 and PDR2 is part of a reduction. */ @@ -586,11 +570,12 @@ int i; poly_dr_p pdr; - for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr); i++) - if (PDR_TYPE (pdr) == PDR_WRITE) - break; + FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), i, pdr) + if (PDR_TYPE (pdr) == PDR_WRITE + && same_pdr_p (pdr, pdr1) && same_pdr_p (pdr, pdr2)) + return true; - return same_pdr_p (pdr, pdr1) && same_pdr_p (pdr, pdr2); + return false; } /* Return true when the data dependence relation between the data @@ -635,7 +620,7 @@ we get an empty intersection when the transform is legal: i.e. the transform should reverse no dependences, and so PT, the reversed transformed PDDR, should have no constraint from PO. */ - opddr = dependence_polyhedron (pdr1, pdr2, 1, true); + opddr = new_poly_ddr (pdr1, pdr2, 1, true); if (PDDR_KIND (opddr) == unknown_dependence) return false; @@ -646,7 +631,7 @@ if (pddr_is_empty (opddr)) return true; - tpddr = dependence_polyhedron (pdr1, pdr2, -1, false); + tpddr = new_poly_ddr (pdr1, pdr2, -1, false); if (PDDR_KIND (tpddr) == unknown_dependence) { @@ -685,7 +670,7 @@ ppl_insert_dimensions_pointset (pt, otdim1 + ttdim1 + ddim1, otdim2); ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp, pt); - is_empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (po_temp); + is_empty_p = ppl_powerset_is_empty (po_temp); ppl_delete_Pointset_Powerset_C_Polyhedron (po_temp); free_poly_ddr (tpddr); @@ -723,8 +708,8 @@ if (reduction_ddr_p (pbb1, pbb2)) return true; - for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++) - for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++) + FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), i, pdr1) + FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), j, pdr2) if (!graphite_legal_transform_dr (pdr1, pdr2)) return false; @@ -742,8 +727,8 @@ timevar_push (TV_GRAPHITE_DATA_DEPS); - for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++) - for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++) + FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1) + FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2) if (!graphite_legal_transform_bb (pbb1, pbb2)) { timevar_pop (TV_GRAPHITE_DATA_DEPS); @@ -767,7 +752,7 @@ graphite_dim_t ddim1 = pbb_dim_iter_domain (PDR_PBB (pdr1)); ppl_dimension_type dim; bool empty_p; - poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false); + poly_ddr_p pddr = new_poly_ddr (pdr1, pdr2, 1, false); if (PDDR_KIND (pddr) == unknown_dependence) { @@ -786,7 +771,7 @@ eqpp = build_pairwise_scheduling (dim, level, tdim1 + ddim1, 1); ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp, po); - empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (eqpp); + empty_p = ppl_powerset_is_empty (eqpp); ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp); free_poly_ddr (pddr); @@ -804,8 +789,8 @@ timevar_push (TV_GRAPHITE_DATA_DEPS); - for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++) - for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++) + FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), i, pdr1) + FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), j, pdr2) if (graphite_carried_dependence_level_k (pdr1, pdr2, level)) { timevar_pop (TV_GRAPHITE_DATA_DEPS); @@ -816,52 +801,28 @@ return false; } -/* Pretty print to FILE all the original data dependences of SCoP in - DOT format. */ +/* When ORIG is true, pretty print to FILE all the original data + dependences of SCoP in DOT format, otherwise print the transformed + data deps. */ static void -dot_original_deps_stmt_1 (FILE *file, scop_p scop) +dot_deps_stmt_2 (FILE *file, scop_p scop, bool orig) { int i, j, k, l; poly_bb_p pbb1, pbb2; poly_dr_p pdr1, pdr2; - for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++) - for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++) + FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1) + FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2) { - for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++) - for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++) - if (!pddr_is_empty (dependence_polyhedron (pdr1, pdr2, 1, true))) - { - fprintf (file, "OS%d -> OS%d\n", - pbb_index (pbb1), pbb_index (pbb2)); - goto done; - } - done:; - } -} - -/* Pretty print to FILE all the transformed data dependences of SCoP in - DOT format. */ - -static void -dot_transformed_deps_stmt_1 (FILE *file, scop_p scop) -{ - int i, j, k, l; - poly_bb_p pbb1, pbb2; - poly_dr_p pdr1, pdr2; - - for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++) - for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++) - { - for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++) - for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++) + FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), k, pdr1) + FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), l, pdr2) { - poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false); + poly_ddr_p pddr = new_poly_ddr (pdr1, pdr2, 1, orig); if (!pddr_is_empty (pddr)) { - fprintf (file, "TS%d -> TS%d\n", + fprintf (file, orig ? "OS%d -> OS%d\n" : "TS%d -> TS%d\n", pbb_index (pbb1), pbb_index (pbb2)); free_poly_ddr (pddr); @@ -874,7 +835,6 @@ } } - /* Pretty print to FILE all the data dependences of SCoP in DOT format. */ @@ -883,51 +843,33 @@ { fputs ("digraph all {\n", file); - dot_original_deps_stmt_1 (file, scop); - dot_transformed_deps_stmt_1 (file, scop); + dot_deps_stmt_2 (file, scop, true); + dot_deps_stmt_2 (file, scop, false); fputs ("}\n\n", file); } -/* Pretty print to FILE all the original data dependences of SCoP in - DOT format. */ +/* When ORIG is true, pretty print to FILE all the original data + dependences of SCoP in DOT format, otherwise print the transformed + data deps. */ static void -dot_original_deps (FILE *file, scop_p scop) +dot_deps_2 (FILE *file, scop_p scop, bool orig) { int i, j, k, l; poly_bb_p pbb1, pbb2; poly_dr_p pdr1, pdr2; - for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++) - for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++) - for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++) - for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++) - if (!pddr_is_empty (dependence_polyhedron (pdr1, pdr2, 1, true))) - fprintf (file, "OS%d_D%d -> OS%d_D%d\n", - pbb_index (pbb1), PDR_ID (pdr1), - pbb_index (pbb2), PDR_ID (pdr2)); -} - -/* Pretty print to FILE all the transformed data dependences of SCoP in - DOT format. */ - -static void -dot_transformed_deps (FILE *file, scop_p scop) -{ - int i, j, k, l; - poly_bb_p pbb1, pbb2; - poly_dr_p pdr1, pdr2; - - for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++) - for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++) - for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++) - for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++) - { - poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false); + FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), i, pbb1) + FOR_EACH_VEC_ELT (poly_bb_p, SCOP_BBS (scop), j, pbb2) + FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb1), k, pdr1) + FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (pbb2), l, pdr2) + { + poly_ddr_p pddr = new_poly_ddr (pdr1, pdr2, 1, orig); if (!pddr_is_empty (pddr)) - fprintf (file, "TS%d_D%d -> TS%d_D%d\n", + fprintf (file, orig + ? "OS%d_D%d -> OS%d_D%d\n" : "TS%d_D%d -> TS%d_D%d\n", pbb_index (pbb1), PDR_ID (pdr1), pbb_index (pbb2), PDR_ID (pdr2)); @@ -943,28 +885,27 @@ { fputs ("digraph all {\n", file); - dot_original_deps (file, scop); - dot_transformed_deps (file, scop); + dot_deps_2 (file, scop, true); + dot_deps_2 (file, scop, false); fputs ("}\n\n", file); } /* Display all the data dependences in SCoP using dotty. */ -void +DEBUG_FUNCTION void dot_deps (scop_p scop) { /* When debugging, enable the following code. This cannot be used in production compilers because it calls "system". */ #if 0 - int x; FILE *stream = fopen ("/tmp/scopdeps.dot", "w"); gcc_assert (stream); dot_deps_1 (stream, scop); fclose (stream); - x = system ("dotty /tmp/scopdeps.dot"); + system ("dotty /tmp/scopdeps.dot &"); #else dot_deps_1 (stderr, scop); #endif @@ -972,20 +913,19 @@ /* Display all the statement dependences in SCoP using dotty. */ -void +DEBUG_FUNCTION void dot_deps_stmt (scop_p scop) { /* When debugging, enable the following code. This cannot be used in production compilers because it calls "system". */ #if 0 - int x; FILE *stream = fopen ("/tmp/scopdeps.dot", "w"); gcc_assert (stream); dot_deps_stmt_1 (stream, scop); fclose (stream); - x = system ("dotty /tmp/scopdeps.dot"); + system ("dotty /tmp/scopdeps.dot &"); #else dot_deps_stmt_1 (stderr, scop); #endif