path: root/gcc/graphite-blocking.c

/* Heuristics and transform for loop blocking and strip mining on
   polyhedral representation.

   Copyright (C) 2009-2015 Free Software Foundation, Inc.
   Contributed by Sebastian Pop <sebastian.pop@amd.com> and
   Pranav Garg  <pranav.garg2107@gmail.com>.

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
<http://www.gnu.org/licenses/>.  */

#include "config.h"

#ifdef HAVE_isl
#include <isl/set.h>
#include <isl/map.h>
#include <isl/union_map.h>
#include <isl/constraint.h>
#endif

#include "system.h"
#include "coretypes.h"
#include "alias.h"
#include "symtab.h"
#include "options.h"
#include "tree.h"
#include "fold-const.h"
#include "predict.h"
#include "tm.h"
#include "hard-reg-set.h"
#include "function.h"
#include "dominance.h"
#include "basic-block.h"
#include "tree-ssa-alias.h"
#include "internal-fn.h"
#include "gimple-expr.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_isl
#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