/* Heuristics and transform for loop blocking and strip mining on polyhedral representation. Copyright (C) 2009-2014 Free Software Foundation, Inc. Contributed by Sebastian Pop and Pranav Garg . This file is part of GCC. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see . */ #include "config.h" #ifdef HAVE_cloog #include #include #include #include #include #include #endif #include "system.h" #include "coretypes.h" #include "tree.h" #include "basic-block.h" #include "tree-ssa-alias.h" #include "internal-fn.h" #include "gimple-expr.h" #include "is-a.h" #include "gimple.h" #include "gimple-iterator.h" #include "tree-ssa-loop.h" #include "dumpfile.h" #include "cfgloop.h" #include "tree-chrec.h" #include "tree-data-ref.h" #include "sese.h" #ifdef HAVE_cloog #include "graphite-poly.h" /* Strip mines with a factor STRIDE the scattering (time) dimension around PBB at depth TIME_DEPTH. The following example comes from the wiki page: http://gcc.gnu.org/wiki/Graphite/Strip_mine The strip mine of a loop with a tile of 64 can be obtained with a scattering function as follows: $ cat ./albert_strip_mine.cloog # language: C c # parameter {n | n >= 0} 1 3 # n 1 1 1 0 1 n 1 # Number of statements: 1 # {i | 0 <= i <= n} 2 4 # i n 1 1 1 0 0 1 -1 1 0 0 0 0 1 i 1 # Scattering functions 3 6 # NEW OLD i n 1 1 -64 0 1 0 0 1 64 0 -1 0 63 0 0 1 -1 0 0 1 NEW OLD #the output of CLooG is like this: #$ cloog ./albert_strip_mine.cloog # for (NEW=0;NEW<=floord(n,64);NEW++) { # for (OLD=max(64*NEW,0);OLD<=min(64*NEW+63,n);OLD++) { # S1(i = OLD) ; # } # } */ static void pbb_strip_mine_time_depth (poly_bb_p pbb, int time_depth, int stride) { isl_space *d; isl_constraint *c; int iter, strip; /* STRIP is the dimension that iterates with stride STRIDE. */ /* ITER is the dimension that enumerates single iterations inside one strip that has at most STRIDE iterations. */ strip = time_depth; iter = strip + 2; pbb->transformed = isl_map_insert_dims (pbb->transformed, isl_dim_out, strip, 2); /* Lower bound of the striped loop. */ d = isl_map_get_space (pbb->transformed); c = isl_inequality_alloc (isl_local_space_from_space (d)); c = isl_constraint_set_coefficient_si (c, isl_dim_out, strip, -stride); c = isl_constraint_set_coefficient_si (c, isl_dim_out, iter, 1); pbb->transformed = isl_map_add_constraint (pbb->transformed, c); /* Upper bound of the striped loop. */ d = isl_map_get_space (pbb->transformed); c = isl_inequality_alloc (isl_local_space_from_space (d)); c = isl_constraint_set_coefficient_si (c, isl_dim_out, strip, stride); c = isl_constraint_set_coefficient_si (c, isl_dim_out, iter, -1); c = isl_constraint_set_constant_si (c, stride - 1); pbb->transformed = isl_map_add_constraint (pbb->transformed, c); /* Static scheduling for ITER level. This is mandatory to keep the 2d + 1 canonical scheduling format. */ d = isl_map_get_space (pbb->transformed); c = isl_equality_alloc (isl_local_space_from_space (d)); c = isl_constraint_set_coefficient_si (c, isl_dim_out, strip + 1, 1); pbb->transformed = isl_map_add_constraint (pbb->transformed, c); } /* Returns true when strip mining with STRIDE of the loop LST is profitable. */ static bool lst_strip_mine_profitable_p (lst_p lst, int stride) { mpz_t niter, strip_stride; bool res; gcc_assert (LST_LOOP_P (lst)); mpz_init (strip_stride); mpz_init (niter); mpz_set_si (strip_stride, stride); lst_niter_for_loop (lst, niter); res = (mpz_cmp (niter, strip_stride) > 0); mpz_clear (strip_stride); mpz_clear (niter); return res; } /* Strip-mines all the loops of LST with STRIDE. Return the number of loops strip-mined. */ static int lst_do_strip_mine_loop (lst_p lst, int depth, int stride) { int i; lst_p l; poly_bb_p pbb; if (!lst) return 0; if (LST_LOOP_P (lst)) { int res = 0; FOR_EACH_VEC_ELT (LST_SEQ (lst), i, l) res += lst_do_strip_mine_loop (l, depth, stride); return res; } pbb = LST_PBB (lst); pbb_strip_mine_time_depth (pbb, psct_dynamic_dim (pbb, depth), stride); return 1; } /* Strip-mines all the loops of LST with STRIDE. When STRIDE is zero, read the stride from the PARAM_LOOP_BLOCK_TILE_SIZE. Return the number of strip-mined loops. Strip mining transforms a loop | for (i = 0; i < N; i++) | S (i); into the following loop nest: | for (k = 0; k < N; k += STRIDE) | for (j = 0; j < STRIDE; j++) | S (i = k + j); */ static int lst_do_strip_mine (lst_p lst, int stride) { int i; lst_p l; int res = 0; int depth; if (!stride) stride = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE); if (!lst || !LST_LOOP_P (lst)) return false; FOR_EACH_VEC_ELT (LST_SEQ (lst), i, l) res += lst_do_strip_mine (l, stride); depth = lst_depth (lst); if (depth >= 0 && lst_strip_mine_profitable_p (lst, stride)) { res += lst_do_strip_mine_loop (lst, lst_depth (lst), stride); lst_add_loop_under_loop (lst); } return res; } /* Strip mines all the loops in SCOP. Returns the number of strip-mined loops. */ int scop_do_strip_mine (scop_p scop, int stride) { return lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), stride); } /* Loop blocks all the loops in SCOP. Returns true when we manage to block some loops. */ bool scop_do_block (scop_p scop) { store_scattering (scop); /* If we don't strip mine at least two loops, or not interchange loops, the strip mine alone will not be profitable, and the transform is not a loop blocking: so revert the transform. */ if (lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop), 0) < 2 || scop_do_interchange (scop) == 0) { restore_scattering (scop); return false; } if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "SCoP will be loop blocked.\n"); return true; } #endif