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