From: spop Date: Wed, 12 Aug 2009 14:30:06 +0000 (+0000) Subject: Reimplement interchange heuristic. X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=commitdiff_plain;h=80020e9d6bb1ddd0897a520f1ade531332ab1421 Reimplement interchange heuristic. 2009-08-11 Sebastian Pop Pranav Garg * graphite-interchange.c (gather_access_strides): Removed. (ppl_max_for_le): New. (build_linearized_memory_access): New. (memory_stride_in_loop): New. (pbb_interchange_profitable_p): Reimplemented. * graphite-ppl.h (ppl_new_id_map): New. (ppl_interchange): New. * testsuite/gcc.dg/graphite/interchange-6.c: XFAILed. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@150692 138bc75d-0d04-0410-961f-82ee72b054a4 --- diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 3daa25474ee..5c40f970e75 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,4 +1,15 @@ 2009-08-12 Sebastian Pop + Pranav Garg + + * graphite-interchange.c (gather_access_strides): Removed. + (ppl_max_for_le): New. + (build_linearized_memory_access): New. + (memory_stride_in_loop): New. + (pbb_interchange_profitable_p): Reimplemented. + * graphite-ppl.h (ppl_new_id_map): New. + (ppl_interchange): New. + +2009-08-12 Sebastian Pop * graphite-interchange.c (compute_subscript): Removed. (compute_array_size_cstr): Removed. diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite index cf6790813b3..a5fc5387fa3 100644 --- a/gcc/ChangeLog.graphite +++ b/gcc/ChangeLog.graphite @@ -1,4 +1,17 @@ 2009-08-11 Sebastian Pop + Pranav Garg + + * graphite-interchange.c (gather_access_strides): Removed. + (ppl_max_for_le): New. + (build_linearized_memory_access): New. + (memory_stride_in_loop): New. + (pbb_interchange_profitable_p): Reimplemented. + * graphite-ppl.h (ppl_new_id_map): New. + (ppl_interchange): New. + + * testsuite/gcc.dg/graphite/interchange-6.c: XFAILed. + +2009-08-11 Sebastian Pop * graphite-interchange.c (compute_subscript): Removed. (compute_array_size_cstr): Removed. diff --git a/gcc/graphite-interchange.c b/gcc/graphite-interchange.c index af87ffb1ad2..c9da69be76e 100644 --- a/gcc/graphite-interchange.c +++ b/gcc/graphite-interchange.c @@ -53,47 +53,251 @@ along with GCC; see the file COPYING3. If not see #include "graphite.h" #include "graphite-poly.h" -/* Computes ACCESS_STRIDES, the sum of all the strides of PDR at - LOOP_DEPTH. */ +/* Return in RES the maximum of the linear expression LE on polyhedron PS. */ static void -gather_access_strides (poly_dr_p pdr ATTRIBUTE_UNUSED, - graphite_dim_t loop_depth ATTRIBUTE_UNUSED, - Value access_strides ATTRIBUTE_UNUSED) +ppl_max_for_le (ppl_Pointset_Powerset_C_Polyhedron_t ps, + ppl_Linear_Expression_t le, Value res) { - /* Empty for now. */ + ppl_Coefficient_t num, denom; + Value dv, nv; + int maximum; + + value_init (nv); + value_init (dv); + ppl_new_Coefficient (&num); + ppl_new_Coefficient (&denom); + ppl_Pointset_Powerset_C_Polyhedron_maximize (ps, le, num, denom, &maximum); + + if (maximum) + { + ppl_Coefficient_to_mpz_t (num, nv); + ppl_Coefficient_to_mpz_t (denom, dv); + value_division (res, nv, dv); + } + + value_clear (nv); + value_clear (dv); + ppl_delete_Coefficient (num); + ppl_delete_Coefficient (denom); +} + +/* Builds a linear expression, of dimension DIM, representing PDR's + memory access: + + L = r_{n}*r_{n-1}*...*r_{1}*s_{0} + ... + r_{n}*s_{n-1} + s_{n}. + + For an array A[10][20] with two subscript locations s0 and s1, the + linear memory access is 20 * s0 + s1: a stride of 1 in subscript s0 + corresponds to a memory stride of 20. */ + +static ppl_Linear_Expression_t +build_linearized_memory_access (poly_dr_p pdr) +{ + ppl_Linear_Expression_t res; + ppl_Linear_Expression_t le; + ppl_dimension_type i; + ppl_dimension_type first = pdr_subscript_dim (pdr, 0); + ppl_dimension_type last = pdr_subscript_dim (pdr, PDR_NB_SUBSCRIPTS (pdr)); + Value size, sub_size; + graphite_dim_t dim = pdr_dim (pdr); + + ppl_new_Linear_Expression_with_dimension (&res, dim); + + value_init (size); + value_set_si (size, 1); + value_init (sub_size); + value_set_si (sub_size, 1); + + for (i = last - 1; i >= first; i--) + { + ppl_set_coef_gmp (res, i, size); + + ppl_new_Linear_Expression_with_dimension (&le, dim); + ppl_set_coef (le, i, 1); + ppl_max_for_le (PDR_ACCESSES (pdr), le, sub_size); + value_multiply (size, size, sub_size); + ppl_delete_Linear_Expression (le); + } + + value_clear (sub_size); + value_clear (size); + return res; } -/* Returns true when it is profitable to interchange loop at depth1 - and loop at depth2 with depth1 < depth2 for the polyhedral black - box PBB. */ +/* Set STRIDE to the stride of PDR in memory by advancing by one in + loop DEPTH. */ + +static void +memory_stride_in_loop (Value stride, graphite_dim_t depth, poly_dr_p pdr) +{ + ppl_Linear_Expression_t le, lma; + ppl_Constraint_t new_cstr; + ppl_Pointset_Powerset_C_Polyhedron_t p1, p2; + graphite_dim_t nb_subscripts = PDR_NB_SUBSCRIPTS (pdr); + ppl_dimension_type i, *map; + ppl_dimension_type dim = pdr_dim (pdr); + ppl_dimension_type dim_i = pdr_iterator_dim (pdr, depth); + ppl_dimension_type dim_k = dim; + ppl_dimension_type dim_L1 = dim + nb_subscripts + 1; + ppl_dimension_type dim_L2 = dim + nb_subscripts + 2; + ppl_dimension_type new_dim = dim + nb_subscripts + 3; + + /* Add new dimensions to the polyhedron corresponding to + k, s0', s1',..., L1, and L2. These new variables are at + dimensions dim, dim + 1,... of the polyhedron P1 respectively. */ + ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron + (&p1, PDR_ACCESSES (pdr)); + ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed + (p1, nb_subscripts + 3); + + lma = build_linearized_memory_access (pdr); + ppl_set_coef (lma, dim_L1, -1); + ppl_new_Constraint (&new_cstr, lma, PPL_CONSTRAINT_TYPE_EQUAL); + ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p1, new_cstr); + + /* Build P2. */ + ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron + (&p2, p1); + map = ppl_new_id_map (new_dim); + ppl_interchange (map, dim_L1, dim_L2); + ppl_interchange (map, dim_i, dim_k); + for (i = 0; i < PDR_NB_SUBSCRIPTS (pdr); i++) + ppl_interchange (map, pdr_subscript_dim (pdr, i), dim + i + 1); + ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (p2, map, new_dim); + free (map); + + /* Add constraint k = i + 1. */ + ppl_new_Linear_Expression_with_dimension (&le, new_dim); + ppl_set_coef (le, dim_i, 1); + ppl_set_coef (le, dim_k, -1); + ppl_set_inhomogeneous (le, 1); + ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL); + ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p2, new_cstr); + ppl_delete_Linear_Expression (le); + ppl_delete_Constraint (new_cstr); + + /* P1 = P1 inter P2. */ + ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, p2); + ppl_delete_Pointset_Powerset_C_Polyhedron (p2); + + /* Maximise the expression L2 - L1. */ + ppl_new_Linear_Expression_with_dimension (&le, new_dim); + ppl_set_coef (le, dim_L2, 1); + ppl_set_coef (le, dim_L1, -1); + ppl_max_for_le (p1, le, stride); + ppl_delete_Linear_Expression (le); +} + + +/* Returns true when it is profitable to interchange loop at DEPTH1 + and loop at DEPTH2 with DEPTH1 < DEPTH2 for PBB. + + Example: + + | int a[100][100]; + | + | int + | foo (int N) + | { + | int j; + | int i; + | + | for (i = 0; i < N; i++) + | for (j = 0; j < N; j++) + | a[j][2 * i] += 1; + | + | return a[N][12]; + | } + + The data access A[j][i] is described like this: + + | i j N a s0 s1 1 + | 0 0 0 1 0 0 -5 = 0 + | 0 -1 0 0 1 0 0 = 0 + |-2 0 0 0 0 1 0 = 0 + | 0 0 0 0 1 0 0 >= 0 + | 0 0 0 0 0 1 0 >= 0 + | 0 0 0 0 -1 0 100 >= 0 + | 0 0 0 0 0 -1 100 >= 0 + + The linearized memory access L to A[100][100] is: + + | i j N a s0 s1 1 + | 0 0 0 0 100 1 0 + + Next, to measure the impact of iterating once in loop "i", we build + a maximization problem: first, we add to DR accesses the dimensions + k, s2, s3, L1 = 100 * s0 + s1, L2, and D1: polyhedron P1. + + | i j N a s0 s1 k s2 s3 L1 L2 D1 1 + | 0 0 0 1 0 0 0 0 0 0 0 0 -5 = 0 alias = 5 + | 0 -1 0 0 1 0 0 0 0 0 0 0 0 = 0 s0 = j + |-2 0 0 0 0 1 0 0 0 0 0 0 0 = 0 s1 = 2 * i + | 0 0 0 0 1 0 0 0 0 0 0 0 0 >= 0 + | 0 0 0 0 0 1 0 0 0 0 0 0 0 >= 0 + | 0 0 0 0 -1 0 0 0 0 0 0 0 100 >= 0 + | 0 0 0 0 0 -1 0 0 0 0 0 0 100 >= 0 + | 0 0 0 0 100 1 0 0 0 -1 0 0 0 = 0 L1 = 100 * s0 + s1 + + Then, we generate the polyhedron P2 by interchanging the dimensions + (s0, s2), (s1, s3), (L1, L2), (i0, i) + + | i j N a s0 s1 k s2 s3 L1 L2 D1 1 + | 0 0 0 1 0 0 0 0 0 0 0 0 -5 = 0 alias = 5 + | 0 -1 0 0 0 0 0 1 0 0 0 0 0 = 0 s2 = j + | 0 0 0 0 0 0 -2 0 1 0 0 0 0 = 0 s3 = 2 * k + | 0 0 0 0 0 0 0 1 0 0 0 0 0 >= 0 + | 0 0 0 0 0 0 0 0 1 0 0 0 0 >= 0 + | 0 0 0 0 0 0 0 -1 0 0 0 0 100 >= 0 + | 0 0 0 0 0 0 0 0 -1 0 0 0 100 >= 0 + | 0 0 0 0 0 0 0 100 1 0 -1 0 0 = 0 L2 = 100 * s2 + s3 + + then we add to P2 the equality k = i + 1: + + |-1 0 0 0 0 0 1 0 0 0 0 0 -1 = 0 k = i + 1 + + and finally we maximize the expression "D1 = max (P1 inter P2, L2 - L1)". + + For determining the impact of one iteration on loop "j", we + interchange (k, j), we add "k = j + 1", and we compute D2 the + maximal value of the difference. + + Finally, the profitability test is D1 < D2: if in the outer loop + the strides are smaller than in the inner loop, then it is + profitable to interchange the loops at DEPTH1 and DEPTH2. */ static bool -pbb_interchange_profitable_p (graphite_dim_t depth1, graphite_dim_t depth2, poly_bb_p pbb) +pbb_interchange_profitable_p (graphite_dim_t depth1, graphite_dim_t depth2, + poly_bb_p pbb) { int i; poly_dr_p pdr; - Value access_strides1, access_strides2; + Value d1, d2, s; bool res; gcc_assert (depth1 < depth2); - value_init (access_strides1); - value_init (access_strides2); - - value_set_si (access_strides1, 0); - value_set_si (access_strides2, 0); + value_init (d1); + value_set_si (d1, 0); + value_init (d2); + value_set_si (d2, 0); + value_init (s); for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++) { - gather_access_strides (pdr, depth1, access_strides1); - gather_access_strides (pdr, depth2, access_strides2); + memory_stride_in_loop (s, depth1, pdr); + value_addto (d1, d1, s); + + memory_stride_in_loop (s, depth2, pdr); + value_addto (d2, d2, s); } - res = value_lt (access_strides1, access_strides2); + res = value_lt (d1, d2); - value_clear (access_strides1); - value_clear (access_strides2); + value_clear (d1); + value_clear (d2); + value_clear (s); return res; } diff --git a/gcc/graphite-ppl.h b/gcc/graphite-ppl.h index 8a23c93cc0f..cfa31ec0803 100644 --- a/gcc/graphite-ppl.h +++ b/gcc/graphite-ppl.h @@ -129,5 +129,31 @@ value_max (Value res, Value v1, Value v2) value_assign (res, v1); } +/* Builds a new identity map for dimension DIM. */ + +static inline ppl_dimension_type * +ppl_new_id_map (ppl_dimension_type dim) +{ + ppl_dimension_type *map, i; + + map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim); + + for (i = 0; i < dim; i++) + map[i] = i; + + return map; +} + +/* Builds an interchange of dimensions A and B in MAP. */ + +static inline void +ppl_interchange (ppl_dimension_type *map, + ppl_dimension_type a, + ppl_dimension_type b) +{ + map[a] = b; + map[b] = a; +} + #endif diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 141036a1437..408ec9443c4 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,4 +1,9 @@ 2009-08-12 Sebastian Pop + Pranav Garg + + * testsuite/gcc.dg/graphite/interchange-6.c: XFAILed. + +2009-08-12 Sebastian Pop * gcc.dg/graphite/interchange-9.c: New. diff --git a/gcc/testsuite/gcc.dg/graphite/interchange-6.c b/gcc/testsuite/gcc.dg/graphite/interchange-6.c index 64a18653f90..0197aecbd01 100644 --- a/gcc/testsuite/gcc.dg/graphite/interchange-6.c +++ b/gcc/testsuite/gcc.dg/graphite/interchange-6.c @@ -13,5 +13,5 @@ int medium_loop_interchange(int A[100][200]) return A[1][1]; } -/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" } } */ +/* { dg-final { scan-tree-dump-times "will be interchanged" 1 "graphite" { xfail *-*-* } } } */ /* { dg-final { cleanup-tree-dump "graphite" } } */