[thirdparty/gcc.git] / gcc / graphite-optimize-isl.c

/* A scheduling optimizer for Graphite
   Copyright (C) 2012-2015 Free Software Foundation, Inc.
   Contributed by Tobias Grosser <tobias@grosser.es>.

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

#define USES_ISL

#include "config.h"

#ifdef HAVE_isl

#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "cfghooks.h"
#include "tree.h"
#include "gimple.h"
#include "fold-const.h"
#include "gimple-iterator.h"
#include "tree-ssa-loop.h"
#include "cfgloop.h"
#include "tree-data-ref.h"
#include "params.h"
#include "dumpfile.h"

#include <isl/constraint.h>
#include <isl/set.h>
#include <isl/union_set.h>
#include <isl/map.h>
#include <isl/union_map.h>
#include <isl/schedule.h>
#include <isl/band.h>
#include <isl/aff.h>
#include <isl/options.h>
#include <isl/ctx.h>
#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
/* isl 0.15 or later.  */
#include <isl/schedule_node.h>
#include <isl/ast_build.h>
#endif

#include "graphite.h"

#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
/* isl 0.15 or later.  */

/* get_schedule_for_node_st - Improve schedule for the schedule node.
   Only Simple loop tiling is considered.  */

static __isl_give isl_schedule_node *
get_schedule_for_node_st (__isl_take isl_schedule_node *node, void *user)
{
  if (user)
    return node;

  if (isl_schedule_node_get_type (node) != isl_schedule_node_band
      || isl_schedule_node_n_children (node) != 1)
    return node;

  isl_space *space = isl_schedule_node_band_get_space (node);
  unsigned dims = isl_space_dim (space, isl_dim_set);
  isl_schedule_node *child = isl_schedule_node_get_child (node, 0);
  isl_schedule_node_type type = isl_schedule_node_get_type (child);
  isl_space_free (space);
  isl_schedule_node_free (child);

  if (type != isl_schedule_node_leaf)
    return node;

  if (dims <= 1 || !isl_schedule_node_band_get_permutable (node))
    {
      if (dump_file && dump_flags)
	fprintf (dump_file, "not tiled\n");
      return node;
    }

  /* Tile loops.  */
  space = isl_schedule_node_band_get_space (node);
  isl_multi_val *sizes = isl_multi_val_zero (space);
  long tile_size = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);
  isl_ctx *ctx = isl_schedule_node_get_ctx (node);

  for (unsigned i = 0; i < dims; i++)
    {
      sizes = isl_multi_val_set_val (sizes, i,
				     isl_val_int_from_si (ctx, tile_size));
      if (dump_file && dump_flags)
	fprintf (dump_file, "tiled by %ld\n", tile_size);
    }

  node = isl_schedule_node_band_tile (node, sizes);
  node = isl_schedule_node_child (node, 0);

  return node;
}

/* get_schedule_map_st - Improve the schedule by performing other loop
   optimizations. _st ending is for schedule tree version of this
   function (see get_schedule_map below for the band forest version).

   Do a depth-first post-order traversal of the nodes in a schedule
   tree and apply get_schedule_for_node_st on them to improve the schedule.
  */

static __isl_give isl_union_map *
get_schedule_map_st (__isl_keep isl_schedule *schedule)
{

  schedule = isl_schedule_map_schedule_node_bottom_up (schedule,
						       get_schedule_for_node_st,
						       NULL);
  isl_union_map *schedule_map = isl_schedule_get_map (schedule);
  return schedule_map;
}
#else

/* get_tile_map - Create a map that describes a n-dimensonal tiling.

   get_tile_map creates a map from a n-dimensional scattering space into an
   2*n-dimensional scattering space. The map describes a rectangular tiling.

   Example:
     SCHEDULE_DIMENSIONS = 2, PARAMETER_DIMENSIONS = 1, TILE_SIZE = 32

    tile_map := [p0] -> {[s0, s1] -> [t0, t1, s0, s1]:
			 t0 % 32 = 0 and t0 <= s0 < t0 + 32 and
			 t1 % 32 = 0 and t1 <= s1 < t1 + 32}

   Before tiling:

   for (i = 0; i < N; i++)
     for (j = 0; j < M; j++)
	S(i,j)

   After tiling:

   for (t_i = 0; t_i < N; i+=32)
     for (t_j = 0; t_j < M; j+=32)
	for (i = t_i; i < min(t_i + 32, N); i++)  | Unknown that N % 32 = 0
	  for (j = t_j; j < t_j + 32; j++)        |   Known that M % 32 = 0
	    S(i,j)
  */

static isl_basic_map *
get_tile_map (isl_ctx *ctx, int schedule_dimensions, int tile_size)
{
  /* We construct

     tile_map := [p0] -> {[s0, s1] -> [t0, t1, p0, p1, a0, a1]:
			s0 = a0 * 32 and s0 = p0 and t0 <= p0 < t0 + 32 and
			s1 = a1 * 32 and s1 = p1 and t1 <= p1 < t1 + 32}

     and project out the auxilary dimensions a0 and a1.  */
  isl_space *space
    = isl_space_alloc (ctx, 0, schedule_dimensions, schedule_dimensions * 3);
  isl_basic_map *tile_map = isl_basic_map_universe (isl_space_copy (space));

  isl_local_space *local_space = isl_local_space_from_space (space);

  for (int x = 0; x < schedule_dimensions; x++)
    {
      int sX = x;
      int tX = x;
      int pX = schedule_dimensions + x;
      int aX = 2 * schedule_dimensions + x;

      isl_constraint *c;

      /* sX = aX * tile_size; */
      c = isl_equality_alloc (isl_local_space_copy (local_space));
      isl_constraint_set_coefficient_si (c, isl_dim_out, sX, 1);
      isl_constraint_set_coefficient_si (c, isl_dim_out, aX, -tile_size);
      tile_map = isl_basic_map_add_constraint (tile_map, c);

      /* pX = sX; */
      c = isl_equality_alloc (isl_local_space_copy (local_space));
      isl_constraint_set_coefficient_si (c, isl_dim_out, pX, 1);
      isl_constraint_set_coefficient_si (c, isl_dim_in, sX, -1);
      tile_map = isl_basic_map_add_constraint (tile_map, c);

      /* tX <= pX */
      c = isl_inequality_alloc (isl_local_space_copy (local_space));
      isl_constraint_set_coefficient_si (c, isl_dim_out, pX, 1);
      isl_constraint_set_coefficient_si (c, isl_dim_out, tX, -1);
      tile_map = isl_basic_map_add_constraint (tile_map, c);

      /* pX <= tX + (tile_size - 1) */
      c = isl_inequality_alloc (isl_local_space_copy (local_space));
      isl_constraint_set_coefficient_si (c, isl_dim_out, tX, 1);
      isl_constraint_set_coefficient_si (c, isl_dim_out, pX, -1);
      isl_constraint_set_constant_si (c, tile_size - 1);
      tile_map = isl_basic_map_add_constraint (tile_map, c);
    }

  /* Project out auxiliary dimensions.

     The auxiliary dimensions are transformed into existentially quantified
     ones.
     This reduces the number of visible scattering dimensions and allows isl
     to produces better code.  */
  tile_map =
      isl_basic_map_project_out (tile_map, isl_dim_out,
				 2 * schedule_dimensions, schedule_dimensions);
  isl_local_space_free (local_space);
  return tile_map;
}

/* get_schedule_for_band - Get the schedule for this BAND.

   Polly applies transformations like tiling on top of the isl calculated
   value.
   This can influence the number of scheduling dimension. The number of
   schedule dimensions is returned in DIMENSIONS.  */

static isl_union_map *
get_schedule_for_band (isl_band *band, int *dimensions)
{
  isl_union_map *partial_schedule;
  isl_ctx *ctx;
  isl_space *space;
  isl_basic_map *tile_map;
  isl_union_map *tile_umap;

  partial_schedule = isl_band_get_partial_schedule (band);
  *dimensions = isl_band_n_member (band);

  /* It does not make any sense to tile a band with just one dimension.  */
  if (*dimensions == 1)
    {
      if (dump_file && dump_flags)
	fprintf (dump_file, "not tiled\n");
      return partial_schedule;
    }

  if (dump_file && dump_flags)
    fprintf (dump_file, "tiled by %d\n",
	     PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE));

  ctx = isl_union_map_get_ctx (partial_schedule);
  space = isl_union_map_get_space (partial_schedule);

  tile_map = get_tile_map (ctx, *dimensions,
			   PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE));
  tile_umap = isl_union_map_from_map (isl_map_from_basic_map (tile_map));
  tile_umap = isl_union_map_align_params (tile_umap, space);
  *dimensions = 2 * *dimensions;

  return isl_union_map_apply_range (partial_schedule, tile_umap);
}


/* get_schedule_for_band_list - Get the scheduling map for a list of bands.

   We walk recursively the forest of bands to combine the schedules of the
   individual bands to the overall schedule.  In case tiling is requested,
   the individual bands are tiled.  */

static isl_union_map *
get_schedule_for_band_list (isl_band_list *band_list)
{
  int num_bands, i;
  isl_union_map *schedule;
  isl_ctx *ctx;

  ctx = isl_band_list_get_ctx (band_list);
  num_bands = isl_band_list_n_band (band_list);
  schedule = isl_union_map_empty (isl_space_params_alloc (ctx, 0));

  for (i = 0; i < num_bands; i++)
    {
      isl_band *band;
      isl_union_map *partial_schedule;
      int schedule_dimensions;
      isl_space *space;

      band = isl_band_list_get_band (band_list, i);
      partial_schedule = get_schedule_for_band (band, &schedule_dimensions);
      space = isl_union_map_get_space (partial_schedule);

      if (isl_band_has_children (band))
	{
	  isl_band_list *children = isl_band_get_children (band);
	  isl_union_map *suffixSchedule
	    = get_schedule_for_band_list (children);
	  partial_schedule
	    = isl_union_map_flat_range_product (partial_schedule,
						suffixSchedule);
	  isl_band_list_free (children);
	}

      schedule = isl_union_map_union (schedule, partial_schedule);

      isl_band_free (band);
      isl_space_free (space);
    }

  return schedule;
}

static isl_union_map *
get_schedule_map (isl_schedule *schedule)
{
  isl_band_list *bandList = isl_schedule_get_band_forest (schedule);
  isl_union_map *schedule_map = get_schedule_for_band_list (bandList);
  isl_band_list_free (bandList);
  return schedule_map;
}
#endif

static isl_stat
get_single_map (__isl_take isl_map *map, void *user)
{
  isl_map **single_map = (isl_map **)user;
  *single_map = map;
  return isl_stat_ok;
}

static void
apply_schedule_map_to_scop (scop_p scop, isl_union_map *schedule_map)
{
  int i;
  poly_bb_p pbb;

  FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
    {
      isl_set *domain = isl_set_copy (pbb->domain);
      isl_map *stmt_schedule;

      isl_union_map *stmt_band
	= isl_union_map_intersect_domain (isl_union_map_copy (schedule_map),
					  isl_union_set_from_set (domain));
      isl_union_map_foreach_map (stmt_band, get_single_map, &stmt_schedule);
      isl_map_free (pbb->transformed);
      pbb->transformed = stmt_schedule;
      isl_union_map_free (stmt_band);
    }
}

static isl_union_set *
scop_get_domains (scop_p scop ATTRIBUTE_UNUSED)
{
  int i;
  poly_bb_p pbb;
  isl_space *space = isl_set_get_space (scop->param_context);
  isl_union_set *res = isl_union_set_empty (space);

  FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
    res = isl_union_set_add_set (res, isl_set_copy (pbb->domain));

  return res;
}

static const int CONSTANT_BOUND = 20;

/* Compute the schedule for SCOP based on its parameters, domain and set of
   constraints.  Then apply the schedule to SCOP.  */

bool
optimize_isl (scop_p scop)
{
  int old_max_operations = isl_ctx_get_max_operations (scop->isl_context);
  int max_operations = PARAM_VALUE (PARAM_MAX_ISL_OPERATIONS);
  if (max_operations)
    isl_ctx_set_max_operations (scop->isl_context, max_operations);
  isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_CONTINUE);

  isl_union_set *domain = scop_get_domains (scop);
  isl_union_map *dependences = scop_get_dependences (scop);
  dependences
    = isl_union_map_gist_domain (dependences, isl_union_set_copy (domain));
  dependences
    = isl_union_map_gist_range (dependences, isl_union_set_copy (domain));
  isl_union_map *validity = dependences;
  isl_union_map *proximity = isl_union_map_copy (validity);

  isl_options_set_schedule_max_constant_term (scop->isl_context, CONSTANT_BOUND);
  isl_options_set_schedule_maximize_band_depth (scop->isl_context, 1);
#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
  /* isl 0.15 or later.  */
  isl_options_set_schedule_serialize_sccs (scop->isl_context, 0);
  isl_options_set_schedule_maximize_band_depth (scop->isl_context, 1);
  isl_options_set_schedule_max_constant_term (scop->isl_context, 20);
  isl_options_set_schedule_max_coefficient (scop->isl_context, 20);
  isl_options_set_tile_scale_tile_loops (scop->isl_context, 0);
  isl_options_set_coalesce_bounded_wrapping (scop->isl_context, 1);
  isl_options_set_ast_build_exploit_nested_bounds (scop->isl_context, 1);
  isl_options_set_ast_build_atomic_upper_bound (scop->isl_context, 1);
#else
  isl_options_set_schedule_fuse (scop->isl_context, ISL_SCHEDULE_FUSE_MIN);
#endif

  isl_schedule *schedule
    = isl_union_set_compute_schedule (domain, validity, proximity);
  isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_ABORT);

  isl_ctx_reset_operations (scop->isl_context);
  isl_ctx_set_max_operations (scop->isl_context, old_max_operations);
  if (!schedule || isl_ctx_last_error (scop->isl_context) == isl_error_quota)
    {
      if (dump_file && dump_flags)
	fprintf (dump_file, "isl timed out --param max-isl-operations=%d\n",
		 max_operations);
      if (schedule)
	isl_schedule_free (schedule);
      return false;
    }

#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
  /* isl 0.15 or later.  */
  isl_union_map *schedule_map = get_schedule_map_st (schedule);
#else
  isl_union_map *schedule_map = get_schedule_map (schedule);
#endif
  apply_schedule_map_to_scop (scop, schedule_map);

  isl_schedule_free (schedule);
  isl_union_map_free (schedule_map);
  return true;
}

#endif /* HAVE_isl */
Commit	Line	Data
b60cc080	1	/* A scheduling optimizer for Graphite
5624e564	2	Copyright (C) 2012-2015 Free Software Foundation, Inc.
b60cc080 TG	3	Contributed by Tobias Grosser <tobias@grosser.es>.
	4
	5	This file is part of GCC.
	6
	7	GCC is free software; you can redistribute it and/or modify
	8	it under the terms of the GNU General Public License as published by
	9	the Free Software Foundation; either version 3, or (at your option)
	10	any later version.
	11
	12	GCC is distributed in the hope that it will be useful,
	13	but WITHOUT ANY WARRANTY; without even the implied warranty of
	14	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	15	GNU General Public License for more details.
	16
	17	You should have received a copy of the GNU General Public License
	18	along with GCC; see the file COPYING3. If not see
	19	<http://www.gnu.org/licenses/>. */
	20
4d776011 DE	21	#define USES_ISL
4d776011 DE	22
b60cc080 TG	23	#include "config.h"
b60cc080 TG	24
eae1a5d4	25	#ifdef HAVE_isl
4d776011 DE	26
	27	#include "system.h"
	28	#include "coretypes.h"
	29	#include "backend.h"
	30	#include "cfghooks.h"
	31	#include "tree.h"
	32	#include "gimple.h"
	33	#include "fold-const.h"
	34	#include "gimple-iterator.h"
	35	#include "tree-ssa-loop.h"
	36	#include "cfgloop.h"
	37	#include "tree-data-ref.h"
	38	#include "params.h"
	39	#include "dumpfile.h"
4bc190dc	40
32400032	41	#include <isl/constraint.h>
b60cc080	42	#include <isl/set.h>
32400032	43	#include <isl/union_set.h>
b60cc080 TG	44	#include <isl/map.h>
	45	#include <isl/union_map.h>
	46	#include <isl/schedule.h>
	47	#include <isl/band.h>
	48	#include <isl/aff.h>
	49	#include <isl/options.h>
6b3ebcdd	50	#include <isl/ctx.h>
5affe17f	51	#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
560d18d3	52	/* isl 0.15 or later. */
5affe17f	53	#include <isl/schedule_node.h>
d57ad2bf	54	#include <isl/ast_build.h>
5affe17f	55	#endif
b60cc080	56
cf98f0f4	57	#include "graphite.h"
b60cc080	58
5affe17f	59	#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
560d18d3	60	/* isl 0.15 or later. */
5affe17f AZ	61
	62	/* get_schedule_for_node_st - Improve schedule for the schedule node.
	63	Only Simple loop tiling is considered. */
	64
	65	static __isl_give isl_schedule_node *
	66	get_schedule_for_node_st (__isl_take isl_schedule_node node, void user)
b60cc080	67	{
5affe17f AZ	68	if (user)
5affe17f AZ	69	return node;
b60cc080	70
5affe17f AZ	71	if (isl_schedule_node_get_type (node) != isl_schedule_node_band
	72	\|\| isl_schedule_node_n_children (node) != 1)
	73	return node;
	74
	75	isl_space *space = isl_schedule_node_band_get_space (node);
	76	unsigned dims = isl_space_dim (space, isl_dim_set);
	77	isl_schedule_node *child = isl_schedule_node_get_child (node, 0);
	78	isl_schedule_node_type type = isl_schedule_node_get_type (child);
	79	isl_space_free (space);
	80	isl_schedule_node_free (child);
	81
	82	if (type != isl_schedule_node_leaf)
	83	return node;
	84
	85	if (dims <= 1 \|\| !isl_schedule_node_band_get_permutable (node))
	86	{
	87	if (dump_file && dump_flags)
	88	fprintf (dump_file, "not tiled\n");
	89	return node;
	90	}
	91
	92	/* Tile loops. */
	93	space = isl_schedule_node_band_get_space (node);
	94	isl_multi_val *sizes = isl_multi_val_zero (space);
	95	long tile_size = PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE);
	96	isl_ctx *ctx = isl_schedule_node_get_ctx (node);
	97
	98	for (unsigned i = 0; i < dims; i++)
	99	{
	100	sizes = isl_multi_val_set_val (sizes, i,
	101	isl_val_int_from_si (ctx, tile_size));
	102	if (dump_file && dump_flags)
	103	fprintf (dump_file, "tiled by %ld\n", tile_size);
	104	}
	105
	106	node = isl_schedule_node_band_tile (node, sizes);
	107	node = isl_schedule_node_child (node, 0);
b60cc080	108
5affe17f	109	return node;
b60cc080 TG	110	}
b60cc080 TG	111
5affe17f AZ	112	/* get_schedule_map_st - Improve the schedule by performing other loop
	113	optimizations. _st ending is for schedule tree version of this
	114	function (see get_schedule_map below for the band forest version).
	115
	116	Do a depth-first post-order traversal of the nodes in a schedule
	117	tree and apply get_schedule_for_node_st on them to improve the schedule.
	118	*/
	119
	120	static __isl_give isl_union_map *
	121	get_schedule_map_st (__isl_keep isl_schedule *schedule)
	122	{
	123
	124	schedule = isl_schedule_map_schedule_node_bottom_up (schedule,
	125	get_schedule_for_node_st,
	126	NULL);
	127	isl_union_map *schedule_map = isl_schedule_get_map (schedule);
	128	return schedule_map;
	129	}
	130	#else
	131
ec62c373 AK	132	/* get_tile_map - Create a map that describes a n-dimensonal tiling.
	133
	134	get_tile_map creates a map from a n-dimensional scattering space into an
b60cc080	135	2*n-dimensional scattering space. The map describes a rectangular tiling.
ec62c373	136
b60cc080	137	Example:
ec62c373 AK	138	SCHEDULE_DIMENSIONS = 2, PARAMETER_DIMENSIONS = 1, TILE_SIZE = 32
	139
	140	tile_map := [p0] -> {[s0, s1] -> [t0, t1, s0, s1]:
	141	t0 % 32 = 0 and t0 <= s0 < t0 + 32 and
	142	t1 % 32 = 0 and t1 <= s1 < t1 + 32}
	143
b60cc080	144	Before tiling:
ec62c373	145
b60cc080 TG	146	for (i = 0; i < N; i++)
b60cc080 TG	147	for (j = 0; j < M; j++)
ec62c373 AK	148	S(i,j)
ec62c373 AK	149
b60cc080	150	After tiling:
ec62c373	151
b60cc080 TG	152	for (t_i = 0; t_i < N; i+=32)
b60cc080 TG	153	for (t_j = 0; t_j < M; j+=32)
ec62c373 AK	154	for (i = t_i; i < min(t_i + 32, N); i++) \| Unknown that N % 32 = 0
	155	for (j = t_j; j < t_j + 32; j++) \| Known that M % 32 = 0
	156	S(i,j)
	157	*/
	158
b60cc080	159	static isl_basic_map *
ec62c373	160	get_tile_map (isl_ctx *ctx, int schedule_dimensions, int tile_size)
b60cc080	161	{
b60cc080 TG	162	/* We construct
b60cc080 TG	163
ec62c373 AK	164	tile_map := [p0] -> {[s0, s1] -> [t0, t1, p0, p1, a0, a1]:
	165	s0 = a0 * 32 and s0 = p0 and t0 <= p0 < t0 + 32 and
	166	s1 = a1 * 32 and s1 = p1 and t1 <= p1 < t1 + 32}
b60cc080 TG	167
b60cc080 TG	168	and project out the auxilary dimensions a0 and a1. */
ec62c373 AK	169	isl_space *space
	170	= isl_space_alloc (ctx, 0, schedule_dimensions, schedule_dimensions * 3);
	171	isl_basic_map *tile_map = isl_basic_map_universe (isl_space_copy (space));
b60cc080	172
ec62c373	173	isl_local_space *local_space = isl_local_space_from_space (space);
b60cc080	174
ec62c373	175	for (int x = 0; x < schedule_dimensions; x++)
b60cc080 TG	176	{
	177	int sX = x;
	178	int tX = x;
ec62c373 AK	179	int pX = schedule_dimensions + x;
ec62c373 AK	180	int aX = 2 * schedule_dimensions + x;
b60cc080 TG	181
	182	isl_constraint *c;
	183
ec62c373 AK	184	/* sX = aX * tile_size; */
ec62c373 AK	185	c = isl_equality_alloc (isl_local_space_copy (local_space));
c3284718	186	isl_constraint_set_coefficient_si (c, isl_dim_out, sX, 1);
ec62c373 AK	187	isl_constraint_set_coefficient_si (c, isl_dim_out, aX, -tile_size);
ec62c373 AK	188	tile_map = isl_basic_map_add_constraint (tile_map, c);
b60cc080 TG	189
b60cc080 TG	190	/* pX = sX; */
ec62c373	191	c = isl_equality_alloc (isl_local_space_copy (local_space));
c3284718 RS	192	isl_constraint_set_coefficient_si (c, isl_dim_out, pX, 1);
c3284718 RS	193	isl_constraint_set_coefficient_si (c, isl_dim_in, sX, -1);
ec62c373	194	tile_map = isl_basic_map_add_constraint (tile_map, c);
b60cc080 TG	195
b60cc080 TG	196	/* tX <= pX */
ec62c373	197	c = isl_inequality_alloc (isl_local_space_copy (local_space));
c3284718 RS	198	isl_constraint_set_coefficient_si (c, isl_dim_out, pX, 1);
c3284718 RS	199	isl_constraint_set_coefficient_si (c, isl_dim_out, tX, -1);
ec62c373	200	tile_map = isl_basic_map_add_constraint (tile_map, c);
b60cc080	201
ec62c373 AK	202	/* pX <= tX + (tile_size - 1) */
ec62c373 AK	203	c = isl_inequality_alloc (isl_local_space_copy (local_space));
c3284718 RS	204	isl_constraint_set_coefficient_si (c, isl_dim_out, tX, 1);
c3284718 RS	205	isl_constraint_set_coefficient_si (c, isl_dim_out, pX, -1);
ec62c373 AK	206	isl_constraint_set_constant_si (c, tile_size - 1);
ec62c373 AK	207	tile_map = isl_basic_map_add_constraint (tile_map, c);
b60cc080 TG	208	}
b60cc080 TG	209
688010ba	210	/* Project out auxiliary dimensions.
b60cc080	211
ec62c373 AK	212	The auxiliary dimensions are transformed into existentially quantified
	213	ones.
	214	This reduces the number of visible scattering dimensions and allows isl
b60cc080	215	to produces better code. */
ec62c373 AK	216	tile_map =
	217	isl_basic_map_project_out (tile_map, isl_dim_out,
	218	2 * schedule_dimensions, schedule_dimensions);
	219	isl_local_space_free (local_space);
	220	return tile_map;
b60cc080 TG	221	}
b60cc080 TG	222
ec62c373 AK	223	/* get_schedule_for_band - Get the schedule for this BAND.
	224
	225	Polly applies transformations like tiling on top of the isl calculated
	226	value.
b60cc080	227	This can influence the number of scheduling dimension. The number of
ec62c373	228	schedule dimensions is returned in DIMENSIONS. */
b60cc080 TG	229
b60cc080 TG	230	static isl_union_map *
ec62c373	231	get_schedule_for_band (isl_band band, int dimensions)
b60cc080	232	{
ec62c373	233	isl_union_map *partial_schedule;
b60cc080	234	isl_ctx *ctx;
ec62c373 AK	235	isl_space *space;
	236	isl_basic_map *tile_map;
	237	isl_union_map *tile_umap;
b60cc080	238
ec62c373 AK	239	partial_schedule = isl_band_get_partial_schedule (band);
ec62c373 AK	240	*dimensions = isl_band_n_member (band);
b60cc080	241
b60cc080	242	/* It does not make any sense to tile a band with just one dimension. */
ec62c373	243	if (*dimensions == 1)
d6bb5ccf SP	244	{
	245	if (dump_file && dump_flags)
	246	fprintf (dump_file, "not tiled\n");
ec62c373	247	return partial_schedule;
d6bb5ccf SP	248	}
	249
	250	if (dump_file && dump_flags)
	251	fprintf (dump_file, "tiled by %d\n",
	252	PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE));
b60cc080	253
ec62c373 AK	254	ctx = isl_union_map_get_ctx (partial_schedule);
ec62c373 AK	255	space = isl_union_map_get_space (partial_schedule);
b60cc080	256
ec62c373 AK	257	tile_map = get_tile_map (ctx, *dimensions,
	258	PARAM_VALUE (PARAM_LOOP_BLOCK_TILE_SIZE));
	259	tile_umap = isl_union_map_from_map (isl_map_from_basic_map (tile_map));
	260	tile_umap = isl_union_map_align_params (tile_umap, space);
	261	dimensions = 2 *dimensions;
b60cc080	262
ec62c373	263	return isl_union_map_apply_range (partial_schedule, tile_umap);
b60cc080 TG	264	}
b60cc080 TG	265
b60cc080	266
ec62c373	267	/* get_schedule_for_band_list - Get the scheduling map for a list of bands.
a5e5ea0c	268
b60cc080	269	We walk recursively the forest of bands to combine the schedules of the
ec62c373	270	individual bands to the overall schedule. In case tiling is requested,
a5e5ea0c	271	the individual bands are tiled. */
cf16e6ef	272
b60cc080	273	static isl_union_map *
ec62c373	274	get_schedule_for_band_list (isl_band_list *band_list)
b60cc080	275	{
ec62c373 AK	276	int num_bands, i;
ec62c373 AK	277	isl_union_map *schedule;
b60cc080 TG	278	isl_ctx *ctx;
b60cc080 TG	279
ec62c373 AK	280	ctx = isl_band_list_get_ctx (band_list);
	281	num_bands = isl_band_list_n_band (band_list);
	282	schedule = isl_union_map_empty (isl_space_params_alloc (ctx, 0));
b60cc080	283
ec62c373	284	for (i = 0; i < num_bands; i++)
b60cc080	285	{
ec62c373 AK	286	isl_band *band;
	287	isl_union_map *partial_schedule;
	288	int schedule_dimensions;
	289	isl_space *space;
b60cc080	290
ec62c373 AK	291	band = isl_band_list_get_band (band_list, i);
	292	partial_schedule = get_schedule_for_band (band, &schedule_dimensions);
	293	space = isl_union_map_get_space (partial_schedule);
b60cc080	294
ec62c373	295	if (isl_band_has_children (band))
b60cc080	296	{
ec62c373 AK	297	isl_band_list *children = isl_band_get_children (band);
	298	isl_union_map *suffixSchedule
	299	= get_schedule_for_band_list (children);
	300	partial_schedule
	301	= isl_union_map_flat_range_product (partial_schedule,
	302	suffixSchedule);
	303	isl_band_list_free (children);
b60cc080	304	}
a5e5ea0c	305
ec62c373	306	schedule = isl_union_map_union (schedule, partial_schedule);
b60cc080	307
ec62c373 AK	308	isl_band_free (band);
ec62c373 AK	309	isl_space_free (space);
b60cc080 TG	310	}
b60cc080 TG	311
ec62c373	312	return schedule;
b60cc080 TG	313	}
	314
	315	static isl_union_map *
ec62c373	316	get_schedule_map (isl_schedule *schedule)
b60cc080	317	{
ec62c373 AK	318	isl_band_list *bandList = isl_schedule_get_band_forest (schedule);
	319	isl_union_map *schedule_map = get_schedule_for_band_list (bandList);
	320	isl_band_list_free (bandList);
	321	return schedule_map;
b60cc080	322	}
5affe17f	323	#endif
b60cc080	324
32400032	325	static isl_stat
ec62c373	326	get_single_map (__isl_take isl_map map, void user)
b60cc080	327	{
ec62c373 AK	328	isl_map single_map = (isl_map )user;
ec62c373 AK	329	*single_map = map;
32400032	330	return isl_stat_ok;
b60cc080 TG	331	}
	332
	333	static void
a5e5ea0c	334	apply_schedule_map_to_scop (scop_p scop, isl_union_map *schedule_map)
b60cc080 TG	335	{
	336	int i;
	337	poly_bb_p pbb;
	338
b0b5710c	339	FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
b60cc080 TG	340	{
b60cc080 TG	341	isl_set *domain = isl_set_copy (pbb->domain);
ec62c373	342	isl_map *stmt_schedule;
b60cc080	343
ec62c373 AK	344	isl_union_map *stmt_band
	345	= isl_union_map_intersect_domain (isl_union_map_copy (schedule_map),
	346	isl_union_set_from_set (domain));
	347	isl_union_map_foreach_map (stmt_band, get_single_map, &stmt_schedule);
a5e5ea0c	348	isl_map_free (pbb->transformed);
ec62c373 AK	349	pbb->transformed = stmt_schedule;
ec62c373 AK	350	isl_union_map_free (stmt_band);
b60cc080 TG	351	}
	352	}
	353
5affe17f AZ	354	static isl_union_set *
	355	scop_get_domains (scop_p scop ATTRIBUTE_UNUSED)
	356	{
	357	int i;
	358	poly_bb_p pbb;
	359	isl_space *space = isl_set_get_space (scop->param_context);
	360	isl_union_set *res = isl_union_set_empty (space);
	361
	362	FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
	363	res = isl_union_set_add_set (res, isl_set_copy (pbb->domain));
	364
4c1ca083	365	return res;
5affe17f AZ	366	}
5affe17f AZ	367
b60cc080 TG	368	static const int CONSTANT_BOUND = 20;
b60cc080 TG	369
cf16e6ef AK	370	/* Compute the schedule for SCOP based on its parameters, domain and set of
	371	constraints. Then apply the schedule to SCOP. */
	372
b60cc080 TG	373	bool
	374	optimize_isl (scop_p scop)
	375	{
8e4dc590	376	int old_max_operations = isl_ctx_get_max_operations (scop->isl_context);
6b3ebcdd SP	377	int max_operations = PARAM_VALUE (PARAM_MAX_ISL_OPERATIONS);
6b3ebcdd SP	378	if (max_operations)
8e4dc590	379	isl_ctx_set_max_operations (scop->isl_context, max_operations);
8e4dc590	380	isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_CONTINUE);
b60cc080	381
6b3ebcdd SP	382	isl_union_set *domain = scop_get_domains (scop);
6b3ebcdd SP	383	isl_union_map *dependences = scop_get_dependences (scop);
ec62c373 AK	384	dependences
	385	= isl_union_map_gist_domain (dependences, isl_union_set_copy (domain));
	386	dependences
	387	= isl_union_map_gist_range (dependences, isl_union_set_copy (domain));
6b3ebcdd SP	388	isl_union_map *validity = dependences;
6b3ebcdd SP	389	isl_union_map *proximity = isl_union_map_copy (validity);
b60cc080	390
8e4dc590 AK	391	isl_options_set_schedule_max_constant_term (scop->isl_context, CONSTANT_BOUND);
8e4dc590 AK	392	isl_options_set_schedule_maximize_band_depth (scop->isl_context, 1);
32400032	393	#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
560d18d3	394	/* isl 0.15 or later. */
d57ad2bf	395	isl_options_set_schedule_serialize_sccs (scop->isl_context, 0);
40856c71	396	isl_options_set_schedule_maximize_band_depth (scop->isl_context, 1);
d57ad2bf AK	397	isl_options_set_schedule_max_constant_term (scop->isl_context, 20);
	398	isl_options_set_schedule_max_coefficient (scop->isl_context, 20);
	399	isl_options_set_tile_scale_tile_loops (scop->isl_context, 0);
	400	isl_options_set_coalesce_bounded_wrapping (scop->isl_context, 1);
	401	isl_options_set_ast_build_exploit_nested_bounds (scop->isl_context, 1);
	402	isl_options_set_ast_build_atomic_upper_bound (scop->isl_context, 1);
32400032	403	#else
cbe7b229	404	isl_options_set_schedule_fuse (scop->isl_context, ISL_SCHEDULE_FUSE_MIN);
32400032	405	#endif
797d8858	406
6b3ebcdd SP	407	isl_schedule *schedule
6b3ebcdd SP	408	= isl_union_set_compute_schedule (domain, validity, proximity);
8e4dc590	409	isl_options_set_on_error (scop->isl_context, ISL_ON_ERROR_ABORT);
b60cc080	410
8e4dc590 AK	411	isl_ctx_reset_operations (scop->isl_context);
	412	isl_ctx_set_max_operations (scop->isl_context, old_max_operations);
	413	if (!schedule \|\| isl_ctx_last_error (scop->isl_context) == isl_error_quota)
6b3ebcdd SP	414	{
6b3ebcdd SP	415	if (dump_file && dump_flags)
560d18d3	416	fprintf (dump_file, "isl timed out --param max-isl-operations=%d\n",
6b3ebcdd SP	417	max_operations);
	418	if (schedule)
	419	isl_schedule_free (schedule);
	420	return false;
	421	}
b60cc080	422
5affe17f	423	#ifdef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
560d18d3	424	/* isl 0.15 or later. */
5affe17f AZ	425	isl_union_map *schedule_map = get_schedule_map_st (schedule);
5affe17f AZ	426	#else
ec62c373	427	isl_union_map *schedule_map = get_schedule_map (schedule);
5affe17f	428	#endif
0171d98d	429	apply_schedule_map_to_scop (scop, schedule_map);
b60cc080	430
0171d98d AK	431	isl_schedule_free (schedule);
	432	isl_union_map_free (schedule_map);
	433	return true;
b60cc080 TG	434	}
b60cc080 TG	435
ec62c373	436	#endif /* HAVE_isl */