X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fgraphite-interchange.c;h=cb4d32cc0d2f7d7734f1124bdc6c5c0fc4f95ccf;hb=16d17f31e8f374acefaac0f2b8f5b2a0c5fab8d2;hp=d4bc232ed161b60127f37b755302152283917a3b;hpb=673c512eedd5f8ead06667c114013635ca67933d;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/graphite-interchange.c b/gcc/graphite-interchange.c index d4bc232ed16..cb4d32cc0d2 100644 --- a/gcc/graphite-interchange.c +++ b/gcc/graphite-interchange.c @@ -1,7 +1,7 @@ /* Interchange heuristics and transform for loop interchange on polyhedral representation. - Copyright (C) 2009 Free Software Foundation, Inc. + Copyright (C) 2009, 2010 Free Software Foundation, Inc. Contributed by Sebastian Pop and Harsha Jagasia . @@ -23,34 +23,17 @@ along with GCC; see the file COPYING3. If not see #include "config.h" #include "system.h" #include "coretypes.h" -#include "tm.h" -#include "ggc.h" -#include "tree.h" -#include "rtl.h" -#include "output.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 "value-prof.h" -#include "pointer-set.h" -#include "gimple.h" -#include "params.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" /* Builds a linear expression, of dimension DIM, representing PDR's @@ -78,15 +61,15 @@ build_linearized_memory_access (ppl_dimension_type offset, poly_dr_p pdr) 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; + mpz_t size, sub_size; graphite_dim_t dim = offset + 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); + mpz_init (size); + mpz_set_si (size, 1); + mpz_init (sub_size); + mpz_set_si (sub_size, 1); for (i = last - 1; i >= first; i--) { @@ -95,12 +78,12 @@ build_linearized_memory_access (ppl_dimension_type offset, poly_dr_p pdr) ppl_new_Linear_Expression_with_dimension (&le, dim - offset); ppl_set_coef (le, i, 1); ppl_max_for_le_pointset (PDR_ACCESSES (pdr), le, sub_size); - value_multiply (size, size, sub_size); + mpz_mul (size, size, sub_size); ppl_delete_Linear_Expression (le); } - value_clear (sub_size); - value_clear (size); + mpz_clear (sub_size); + mpz_clear (size); return res; } @@ -196,7 +179,7 @@ build_partial_difference (ppl_Pointset_Powerset_C_Polyhedron_t *p, the loop at DEPTH. */ static void -memory_stride_in_loop (Value stride, graphite_dim_t depth, poly_dr_p pdr) +pdr_stride_in_loop (mpz_t stride, graphite_dim_t depth, poly_dr_p pdr) { ppl_dimension_type time_depth; ppl_Linear_Expression_t le, lma; @@ -319,9 +302,15 @@ memory_stride_in_loop (Value stride, graphite_dim_t depth, poly_dr_p pdr) if (dump_file && (dump_flags & TDF_DETAILS)) { + char *str; + void (*gmp_free) (void *, size_t); + fprintf (dump_file, "\nStride in BB_%d, DR_%d, depth %d:", pbb_index (pbb), PDR_ID (pdr), (int) depth); - value_print (dump_file, " %s ", stride); + str = mpz_get_str (0, 10, stride); + fprintf (dump_file, " %s ", str); + mp_get_memory_functions (NULL, NULL, &gmp_free); + (*gmp_free) (str, strlen (str) + 1); } ppl_delete_Pointset_Powerset_C_Polyhedron (p1); @@ -329,34 +318,54 @@ memory_stride_in_loop (Value stride, graphite_dim_t depth, poly_dr_p pdr) ppl_delete_Linear_Expression (le); } -/* Sets STRIDES to the sum of all the strides of the data references accessed */ + +/* Sets STRIDES to the sum of all the strides of the data references + accessed in LOOP at DEPTH. */ static void -memory_strides_in_loop_depth (poly_bb_p pbb, graphite_dim_t depth, Value strides) +memory_strides_in_loop_1 (lst_p loop, graphite_dim_t depth, mpz_t strides) { - int i; + int i, j; + lst_p l; poly_dr_p pdr; - Value s, n; + mpz_t s, n; - value_set_si (strides, 0); - value_init (s); - value_init (n); + mpz_init (s); + mpz_init (n); - for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++) - { - value_set_si (n, PDR_NB_REFS (pdr)); + FOR_EACH_VEC_ELT (lst_p, LST_SEQ (loop), j, l) + if (LST_LOOP_P (l)) + memory_strides_in_loop_1 (l, depth, strides); + else + FOR_EACH_VEC_ELT (poly_dr_p, PBB_DRS (LST_PBB (l)), i, pdr) + { + pdr_stride_in_loop (s, depth, pdr); + mpz_set_si (n, PDR_NB_REFS (pdr)); + mpz_mul (s, s, n); + mpz_add (strides, strides, s); + } - memory_stride_in_loop (s, depth, pdr); - value_multiply (s, s, n); - value_addto (strides, strides, s); - } + mpz_clear (s); + mpz_clear (n); +} + +/* Sets STRIDES to the sum of all the strides of the data references + accessed in LOOP at DEPTH. */ - value_clear (s); - value_clear (n); +static void +memory_strides_in_loop (lst_p loop, graphite_dim_t depth, mpz_t strides) +{ + if (mpz_cmp_si (loop->memory_strides, -1) == 0) + { + mpz_set_si (strides, 0); + memory_strides_in_loop_1 (loop, depth, strides); + } + else + mpz_set (strides, loop->memory_strides); } -/* Returns true when it is profitable to interchange time dimensions DEPTH1 - and DEPTH2 with DEPTH1 < DEPTH2 for PBB. +/* Return true when the interchange of loops LOOP1 and LOOP2 is + profitable. Example: @@ -437,24 +446,23 @@ memory_strides_in_loop_depth (poly_bb_p pbb, graphite_dim_t depth, Value strides 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) +lst_interchange_profitable_p (lst_p nest, int depth1, int depth2) { - Value d1, d2; + mpz_t d1, d2; bool res; gcc_assert (depth1 < depth2); - value_init (d1); - value_init (d2); + mpz_init (d1); + mpz_init (d2); - memory_strides_in_loop_depth (pbb, depth1, d1); - memory_strides_in_loop_depth (pbb, depth2, d2); + memory_strides_in_loop (nest, depth1, d1); + memory_strides_in_loop (nest, depth2, d2); - res = value_lt (d1, d2); + res = mpz_cmp (d1, d2) < 0; - value_clear (d1); - value_clear (d2); + mpz_clear (d1); + mpz_clear (d2); return res; } @@ -500,47 +508,13 @@ lst_apply_interchange (lst_p lst, int depth1, int depth2) int i; lst_p l; - for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) + FOR_EACH_VEC_ELT (lst_p, LST_SEQ (lst), i, l) lst_apply_interchange (l, depth1, depth2); } else pbb_interchange_loop_depths (depth1, depth2, LST_PBB (lst)); } -/* Return true when the interchange of loops at depths DEPTH1 and - DEPTH2 to all the statements below LST is profitable. */ - -static bool -lst_interchange_profitable_p (lst_p lst, int depth1, int depth2) -{ - if (!lst) - return false; - - if (LST_LOOP_P (lst)) - { - int i; - lst_p l; - bool res = false; - - for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++) - { - bool profitable = lst_interchange_profitable_p (l, depth1, depth2); - - if (profitable && !LST_LOOP_P (lst) - && dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, - "Interchanging loops at depths %d and %d is profitable for stmt_%d.\n", - depth1, depth2, pbb_index (LST_PBB (lst))); - - res |= profitable; - } - - return res; - } - else - return pbb_interchange_profitable_p (depth1, depth2, LST_PBB (lst)); -} - /* Return true when the nest starting at LOOP1 and ending on LOOP2 is perfect: i.e. there are no sequence of statements. */ @@ -587,44 +561,49 @@ lst_perfect_nestify (lst_p loop1, lst_p loop2, lst_p *before, lst_remove_all_before_excluding_pbb (*nest, last, false); if (lst_empty_p (*before)) - *before = NULL; + { + free_lst (*before); + *before = NULL; + } if (lst_empty_p (*after)) - *after = NULL; + { + free_lst (*after); + *after = NULL; + } if (lst_empty_p (*nest)) - *nest = NULL; + { + free_lst (*nest); + *nest = NULL; + } } /* Try to interchange LOOP1 with LOOP2 for all the statements of the body of LOOP2. LOOP1 contains LOOP2. Return true if it did the - interchange. CREATED_LOOP_BEFORE/CREATED_LOOP_AFTER are set to - true if the loop distribution created a loop before/after LOOP1. */ + interchange. */ static bool -lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2, - lst_p *before, lst_p *nest, lst_p *after) +lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2) { int depth1 = lst_depth (loop1); int depth2 = lst_depth (loop2); lst_p transformed; - *before = NULL; - *after = NULL; - *nest = NULL; + lst_p before = NULL, nest = NULL, after = NULL; + + if (!lst_perfectly_nested_p (loop1, loop2)) + lst_perfect_nestify (loop1, loop2, &before, &nest, &after); if (!lst_interchange_profitable_p (loop2, depth1, depth2)) return false; - if (!lst_perfectly_nested_p (loop1, loop2)) - lst_perfect_nestify (loop1, loop2, before, nest, after); - lst_apply_interchange (loop2, depth1, depth2); /* Sync the transformed LST information and the PBB scatterings before using the scatterings in the data dependence analysis. */ - if (*before || *nest || *after) + if (before || nest || after) { transformed = lst_substitute_3 (SCOP_TRANSFORMED_SCHEDULE (scop), loop1, - *before, *nest, *after); + before, nest, after); lst_update_scattering (transformed); free_lst (transformed); } @@ -637,12 +616,12 @@ lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2, depth1, depth2); /* Transform the SCOP_TRANSFORMED_SCHEDULE of the SCOP. */ - lst_insert_in_sequence (*before, loop1, true); - lst_insert_in_sequence (*after, loop1, false); + lst_insert_in_sequence (before, loop1, true); + lst_insert_in_sequence (after, loop1, false); - if (*nest) + if (nest) { - lst_replace (loop1, *nest); + lst_replace (loop1, nest); free_lst (loop1); } @@ -650,42 +629,13 @@ lst_try_interchange_loops (scop_p scop, lst_p loop1, lst_p loop2, } /* Undo the transform. */ + free_lst (before); + free_lst (nest); + free_lst (after); lst_apply_interchange (loop2, depth2, depth1); - *before = NULL; - *after = NULL; - *nest = NULL; return false; } -static bool lst_interchange_select_inner (scop_p, lst_p, int, lst_p); - -/* Try to interchange loop OUTER of LST_SEQ (OUTER_FATHER) with all - the loop INNER and with all the loops contained in the body of - INNER. Return true if it did interchanged some loops. */ - -static bool -lst_try_interchange (scop_p scop, lst_p outer_father, int outer, lst_p inner) -{ - lst_p before, nest, after; - bool res; - lst_p loop1 = VEC_index (lst_p, LST_SEQ (outer_father), outer); - lst_p loop2 = inner; - - gcc_assert (LST_LOOP_P (loop1) - && LST_LOOP_P (loop2)); - - res = lst_try_interchange_loops (scop, loop1, loop2, &before, &nest, &after); - - if (before) - res |= lst_interchange_select_inner (scop, outer_father, outer, before); - else if (nest) - res |= lst_interchange_select_inner (scop, outer_father, outer, nest); - else - res |= lst_interchange_select_inner (scop, outer_father, outer, loop2); - - return res; -} - /* Selects the inner loop in LST_SEQ (INNER_FATHER) to be interchanged with the loop OUTER in LST_SEQ (OUTER_FATHER). */ @@ -693,9 +643,8 @@ static bool lst_interchange_select_inner (scop_p scop, lst_p outer_father, int outer, lst_p inner_father) { - lst_p l; - bool res = false; int inner; + lst_p loop1, loop2; gcc_assert (outer_father && LST_LOOP_P (outer_father) @@ -703,54 +652,58 @@ lst_interchange_select_inner (scop_p scop, lst_p outer_father, int outer, && inner_father && LST_LOOP_P (inner_father)); - for (inner = 0; VEC_iterate (lst_p, LST_SEQ (inner_father), inner, l); inner++) - if (LST_LOOP_P (l)) - res |= lst_try_interchange (scop, outer_father, outer, l); + loop1 = VEC_index (lst_p, LST_SEQ (outer_father), outer); - return res; + FOR_EACH_VEC_ELT (lst_p, LST_SEQ (inner_father), inner, loop2) + if (LST_LOOP_P (loop2) + && (lst_try_interchange_loops (scop, loop1, loop2) + || lst_interchange_select_inner (scop, outer_father, outer, loop2))) + return true; + + return false; } /* Interchanges all the loops of LOOP and the loops of its body that - are considered profitable to interchange. Return true if it did - interchanged some loops. OUTER is the index in LST_SEQ (LOOP) that + are considered profitable to interchange. Return the number of + interchanged loops. OUTER is the index in LST_SEQ (LOOP) that points to the next outer loop to be considered for interchange. */ -static bool +static int lst_interchange_select_outer (scop_p scop, lst_p loop, int outer) { lst_p l; - bool res = false; + int res = 0; int i = 0; lst_p father; if (!loop || !LST_LOOP_P (loop)) - return false; + return 0; father = LST_LOOP_FATHER (loop); if (father) { - res = lst_interchange_select_inner (scop, father, outer, loop); - - if (VEC_length (lst_p, LST_SEQ (father)) <= (unsigned) outer) - return res; - - loop = VEC_index (lst_p, LST_SEQ (father), outer); + while (lst_interchange_select_inner (scop, father, outer, loop)) + { + res++; + loop = VEC_index (lst_p, LST_SEQ (father), outer); + } } if (LST_LOOP_P (loop)) - for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l); i++) + FOR_EACH_VEC_ELT (lst_p, LST_SEQ (loop), i, l) if (LST_LOOP_P (l)) - res |= lst_interchange_select_outer (scop, l, i); + res += lst_interchange_select_outer (scop, l, i); return res; } -/* Interchanges all the loop depths that are considered profitable for SCOP. */ +/* Interchanges all the loop depths that are considered profitable for + SCOP. Return the number of interchanged loops. */ -bool +int scop_do_interchange (scop_p scop) { - bool res = lst_interchange_select_outer + int res = lst_interchange_select_outer (scop, SCOP_TRANSFORMED_SCHEDULE (scop), 0); lst_update_scattering (SCOP_TRANSFORMED_SCHEDULE (scop));