Subversion Repositories openrisc_2011-10-31

/* Heuristics and transform for loop blocking and strip mining on

   polyhedral representation.

   Copyright (C) 2009 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"

#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"

#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"

/* 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

   1

   i

   1 # Scattering functions

   3 6

   #  NEW  OLD    i    n    1

   1  -64    0    1    0    0

   1   64    0   -1    0   63

   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 bool

pbb_strip_mine_time_depth (poly_bb_p pbb, int time_depth, int stride)

{

  ppl_dimension_type iter, dim, strip;

  ppl_Polyhedron_t res = PBB_TRANSFORMED_SCATTERING (pbb);

  /* 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;

  psct_add_scattering_dimension (pbb, strip);

  psct_add_scattering_dimension (pbb, strip + 1);

  ppl_Polyhedron_space_dimension (res, &dim);

  /* Lower bound of the striped loop.  */

  {

    ppl_Constraint_t new_cstr;

    ppl_Linear_Expression_t expr;

    ppl_new_Linear_Expression_with_dimension (&expr, dim);

    ppl_set_coef (expr, strip, -1 * stride);

    ppl_set_coef (expr, iter, 1);

    ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);

    ppl_delete_Linear_Expression (expr);

    ppl_Polyhedron_add_constraint (res, new_cstr);

    ppl_delete_Constraint (new_cstr);

  }

  /* Upper bound of the striped loop.  */

  {

    ppl_Constraint_t new_cstr;

    ppl_Linear_Expression_t expr;

    ppl_new_Linear_Expression_with_dimension (&expr, dim);

    ppl_set_coef (expr, strip, stride);

    ppl_set_coef (expr, iter, -1);

    ppl_set_inhomogeneous (expr, stride - 1);

    ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);

    ppl_delete_Linear_Expression (expr);

    ppl_Polyhedron_add_constraint (res, new_cstr);

    ppl_delete_Constraint (new_cstr);

  }

  /* Static scheduling for ITER level.

     This is mandatory to keep the 2d + 1 canonical scheduling format.  */

  {

    ppl_Constraint_t new_cstr;

    ppl_Linear_Expression_t expr;

    ppl_new_Linear_Expression_with_dimension (&expr, dim);

    ppl_set_coef (expr, strip + 1, 1);

    ppl_set_inhomogeneous (expr, 0);

    ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);

    ppl_delete_Linear_Expression (expr);

    ppl_Polyhedron_add_constraint (res, new_cstr);

    ppl_delete_Constraint (new_cstr);

  }

  return true;

}

/* Returns true when strip mining with STRIDE of the loop around PBB

   at DEPTH is profitable.  */

static bool

pbb_strip_mine_profitable_p (poly_bb_p pbb,

                             graphite_dim_t depth,

                             int stride)

{

  Value niter, strip_stride;

  bool res;

  value_init (strip_stride);

  value_init (niter);

  value_set_si (strip_stride, stride);

  pbb_number_of_iterations_at_time (pbb, psct_dynamic_dim (pbb, depth), niter);

  res = value_gt (niter, strip_stride);

  value_clear (strip_stride);

  value_clear (niter);

  return res;

}

/* Strip-mines all the loops of LST that are considered profitable to

   strip-mine.  Return true if it did strip-mined some loops.  */

static bool

lst_do_strip_mine_loop (lst_p lst, int depth)

{

  int i;

  lst_p l;

  int stride = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);

  poly_bb_p pbb;

  if (!lst)

    return false;

  if (LST_LOOP_P (lst))

    {

      bool res = false;

      for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)

        res |= lst_do_strip_mine_loop (l, depth);

      return res;

    }

  pbb = LST_PBB (lst);

  return pbb_strip_mine_time_depth (pbb, psct_dynamic_dim (pbb, depth),

                                    stride);

}

/* Strip-mines all the loops of LST that are considered profitable to

   strip-mine.  Return true if it did strip-mined some loops.  */

static bool

lst_do_strip_mine (lst_p lst)

{

  int i;

  lst_p l;

  bool res = false;

  int stride = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);

  int depth;

  if (!lst

      || !LST_LOOP_P (lst))

    return false;

  for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)

    res |= lst_do_strip_mine (l);

  depth = lst_depth (lst);

  if (depth >= 0

      && pbb_strip_mine_profitable_p (LST_PBB (lst_find_first_pbb (lst)),

                                      depth, stride))

    {

      res |= lst_do_strip_mine_loop (lst, lst_depth (lst));

      lst_add_loop_under_loop (lst);

    }

  return res;

}

/* Strip mines all the loops in SCOP.  Nothing profitable in all this:

   this is just a driver function.  */

bool

scop_do_strip_mine (scop_p scop)

{

  bool transform_done = false;

  store_scattering (scop);

  transform_done = lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop));

  if (!transform_done)

    return false;

  if (!graphite_legal_transform (scop))

    {

      restore_scattering (scop);

      return false;

    }

  return transform_done;

}

/* Loop blocks all the loops in SCOP.  Returns true when we manage to

   block some loops.  */

bool

scop_do_block (scop_p scop)

{

  bool strip_mined = false;

  bool interchanged = false;

  store_scattering (scop);

  strip_mined = lst_do_strip_mine (SCOP_TRANSFORMED_SCHEDULE (scop));

  interchanged = scop_do_interchange (scop);

  /* If we don't interchange loops, then the strip mine is not

     profitable, and the transform is not a loop blocking.  */

  if (!interchanged

      || !graphite_legal_transform (scop))

    {

      restore_scattering (scop);

      return false;

    }

  else if (strip_mined && interchanged

           && dump_file && (dump_flags & TDF_DETAILS))

    fprintf (dump_file, "SCoP will be loop blocked.\n");

  return strip_mined || interchanged;

}

#endif