[thirdparty/gcc.git] / gcc / graphite.h

/* Graphite polyhedral representation.
   Copyright (C) 2009-2015 Free Software Foundation, Inc.
   Contributed by Sebastian Pop <sebastian.pop@amd.com> and
   Tobias Grosser <grosser@fim.uni-passau.de>.

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

#ifndef GCC_GRAPHITE_POLY_H
#define GCC_GRAPHITE_POLY_H

#include "sese.h"

#ifndef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
  /* isl 0.14.  */
# define isl_stat int
# define isl_stat_ok 0
#endif

typedef struct poly_dr *poly_dr_p;

typedef struct poly_bb *poly_bb_p;

typedef struct scop *scop_p;

typedef unsigned graphite_dim_t;

static inline graphite_dim_t scop_nb_params (scop_p);

/* A data reference can write or read some memory or we
   just know it may write some memory.  */
enum poly_dr_type
{
  PDR_READ,
  /* PDR_MAY_READs are represented using PDR_READS.  This does not
     limit the expressiveness.  */
  PDR_WRITE,
  PDR_MAY_WRITE
};

struct poly_dr
{
  /* An identifier for this PDR.  */
  int id;

  /* The number of data refs identical to this one in the PBB.  */
  int nb_refs;

  /* A pointer to the gimple stmt containing this reference.  */
  gimple *stmt;

  /* A pointer to the PBB that contains this data reference.  */
  poly_bb_p pbb;

  enum poly_dr_type type;

  /* The access polyhedron contains the polyhedral space this data
     reference will access.

     The polyhedron contains these dimensions:

     - The alias set (a):
     Every memory access is classified in at least one alias set.

     - The subscripts (s_0, ..., s_n):
     The memory is accessed using zero or more subscript dimensions.

     - The iteration domain (variables and parameters)

     Do not hardcode the dimensions.  Use the following accessor functions:
     - pdr_alias_set_dim
     - pdr_subscript_dim
     - pdr_iterator_dim
     - pdr_parameter_dim

     Example:

     | int A[1335][123];
     | int *p = malloc ();
     |
     | k = ...
     | for i
     |   {
     |     if (unknown_function ())
     |       p = A;
     |       ... = p[?][?];
     | 	   for j
     |       A[i][j+k] = m;
     |   }

     The data access A[i][j+k] in alias set "5" is described like this:

     | i   j   k   a  s0  s1   1
     | 0   0   0   1   0   0  -5     =  0
     |-1   0   0   0   1   0   0     =  0
     | 0  -1  -1   0   0   1   0     =  0
     | 0   0   0   0   1   0   0     >= 0  # The last four lines describe the
     | 0   0   0   0   0   1   0     >= 0  # array size.
     | 0   0   0   0  -1   0 1335    >= 0
     | 0   0   0   0   0  -1 123     >= 0

     The pointer "*p" in alias set "5" and "7" is described as a union of
     polyhedron:


     | i   k   a  s0   1
     | 0   0   1   0  -5   =  0
     | 0   0   0   1   0   >= 0

     "or"

     | i   k   a  s0   1
     | 0   0   1   0  -7   =  0
     | 0   0   0   1   0   >= 0

     "*p" accesses all of the object allocated with 'malloc'.

     The scalar data access "m" is represented as an array with zero subscript
     dimensions.

     | i   j   k   a   1
     | 0   0   0  -1   15  = 0

     The difference between the graphite internal format for access data and
     the OpenSop format is in the order of columns.
     Instead of having:

     | i   j   k   a  s0  s1   1
     | 0   0   0   1   0   0  -5     =  0
     |-1   0   0   0   1   0   0     =  0
     | 0  -1  -1   0   0   1   0     =  0
     | 0   0   0   0   1   0   0     >= 0  # The last four lines describe the
     | 0   0   0   0   0   1   0     >= 0  # array size.
     | 0   0   0   0  -1   0 1335    >= 0
     | 0   0   0   0   0  -1 123     >= 0

     In OpenScop we have:

     | a  s0  s1   i   j   k   1
     | 1   0   0   0   0   0  -5     =  0
     | 0   1   0  -1   0   0   0     =  0
     | 0   0   1   0  -1  -1   0     =  0
     | 0   1   0   0   0   0   0     >= 0  # The last four lines describe the
     | 0   0   1   0   0   0   0     >= 0  # array size.
     | 0  -1   0   0   0   0 1335    >= 0
     | 0   0  -1   0   0   0 123     >= 0

     The OpenScop access function is printed as follows:

     | 1  # The number of disjunct components in a union of access functions.
     | R C O I L P  # Described bellow.
     | a  s0  s1   i   j   k   1
     | 1   0   0   0   0   0  -5     =  0
     | 0   1   0  -1   0   0   0     =  0
     | 0   0   1   0  -1  -1   0     =  0
     | 0   1   0   0   0   0   0     >= 0  # The last four lines describe the
     | 0   0   1   0   0   0   0     >= 0  # array size.
     | 0  -1   0   0   0   0 1335    >= 0
     | 0   0  -1   0   0   0 123     >= 0

     Where:
     - R: Number of rows.
     - C: Number of columns.
     - O: Number of output dimensions = alias set + number of subscripts.
     - I: Number of input dimensions (iterators).
     - L: Number of local (existentially quantified) dimensions.
     - P: Number of parameters.

     In the example, the vector "R C O I L P" is "7 7 3 2 0 1".  */
  isl_map *accesses;
  isl_set *subscript_sizes;
};

#define PDR_ID(PDR) (PDR->id)
#define PDR_NB_REFS(PDR) (PDR->nb_refs)
#define PDR_PBB(PDR) (PDR->pbb)
#define PDR_TYPE(PDR) (PDR->type)
#define PDR_ACCESSES(PDR) (NULL)

void new_poly_dr (poly_bb_p, gimple *, enum poly_dr_type,
		  isl_map *, isl_set *);
void free_poly_dr (poly_dr_p);
void debug_pdr (poly_dr_p);
void print_pdr (FILE *, poly_dr_p);

static inline bool
pdr_read_p (poly_dr_p pdr)
{
  return PDR_TYPE (pdr) == PDR_READ;
}

/* Returns true when PDR is a "write".  */

static inline bool
pdr_write_p (poly_dr_p pdr)
{
  return PDR_TYPE (pdr) == PDR_WRITE;
}

/* Returns true when PDR is a "may write".  */

static inline bool
pdr_may_write_p (poly_dr_p pdr)
{
  return PDR_TYPE (pdr) == PDR_MAY_WRITE;
}

/* POLY_BB represents a blackbox in the polyhedral model.  */

struct poly_bb
{
  /* Pointer to a basic block or a statement in the compiler.  */
  gimple_poly_bb_p black_box;

  /* Pointer to the SCOP containing this PBB.  */
  scop_p scop;

  /* The iteration domain of this bb.  The layout of this polyhedron
     is I|G with I the iteration domain, G the context parameters.

     Example:

     for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++)
       for (j = 2; j <= 2*i + 5; j++)
         for (k = 0; k <= 5; k++)
           S (i,j,k)

     Loop iterators: i, j, k
     Parameters: a, b

     | i >=  a -  7b +  8
     | i <= 3a + 13b + 20
     | j >= 2
     | j <= 2i + 5
     | k >= 0
     | k <= 5

     The number of variables in the DOMAIN may change and is not
     related to the number of loops in the original code.  */
  isl_set *domain;

  /* The data references we access.  */
  vec<poly_dr_p> drs;

  /* The original scattering.  */
  isl_map *schedule;

  /* The transformed scattering.  */
  isl_map *transformed;

  /* A copy of the transformed scattering.  */
  isl_map *saved;

  /* True when this PBB contains only a reduction statement.  */
  bool is_reduction;

  /* The last basic block generated for this pbb.  */
  basic_block new_bb;
};

#define PBB_BLACK_BOX(PBB) ((gimple_poly_bb_p) PBB->black_box)
#define PBB_SCOP(PBB) (PBB->scop)
#define PBB_DRS(PBB) (PBB->drs)
#define PBB_IS_REDUCTION(PBB) (PBB->is_reduction)

extern poly_bb_p new_poly_bb (scop_p, gimple_poly_bb_p);
extern void free_poly_bb (poly_bb_p);
extern void debug_loop_vec (poly_bb_p);
extern void print_pbb_domain (FILE *, poly_bb_p);
extern void print_pbb (FILE *, poly_bb_p);
extern void print_scop_context (FILE *, scop_p);
extern void print_scop (FILE *, scop_p);
extern void debug_pbb_domain (poly_bb_p);
extern void debug_pbb (poly_bb_p);
extern void print_pdrs (FILE *, poly_bb_p);
extern void debug_pdrs (poly_bb_p);
extern void debug_scop_context (scop_p);
extern void debug_scop (scop_p);
extern void print_scop_params (FILE *, scop_p);
extern void debug_scop_params (scop_p);
extern void print_iteration_domain (FILE *, poly_bb_p);
extern void print_iteration_domains (FILE *, scop_p);
extern void debug_iteration_domain (poly_bb_p);
extern void debug_iteration_domains (scop_p);
extern void print_isl_set (FILE *, isl_set *);
extern void print_isl_map (FILE *, isl_map *);
extern void print_isl_union_map (FILE *, isl_union_map *);
extern void print_isl_aff (FILE *, isl_aff *);
extern void print_isl_constraint (FILE *, isl_constraint *);
extern void debug_isl_set (isl_set *);
extern void debug_isl_map (isl_map *);
extern void debug_isl_union_map (isl_union_map *);
extern void debug_isl_aff (isl_aff *);
extern void debug_isl_constraint (isl_constraint *);
extern int scop_do_interchange (scop_p);
extern int scop_do_strip_mine (scop_p, int);
extern bool scop_do_block (scop_p);
extern bool flatten_all_loops (scop_p);
extern bool optimize_isl (scop_p);
extern void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, mpz_t);
extern void debug_gmp_value (mpz_t);

/* The basic block of the PBB.  */

static inline basic_block
pbb_bb (poly_bb_p pbb)
{
  return GBB_BB (PBB_BLACK_BOX (pbb));
}

static inline int
pbb_index (poly_bb_p pbb)
{
  return pbb_bb (pbb)->index;
}

/* The loop of the PBB.  */

static inline loop_p
pbb_loop (poly_bb_p pbb)
{
  return gbb_loop (PBB_BLACK_BOX (pbb));
}

/* The scop that contains the PDR.  */

static inline scop_p
pdr_scop (poly_dr_p pdr)
{
  return PBB_SCOP (PDR_PBB (pdr));
}

/* Set black box of PBB to BLACKBOX.  */

static inline void
pbb_set_black_box (poly_bb_p pbb, gimple_poly_bb_p black_box)
{
  pbb->black_box = black_box;
}

/* A helper structure to keep track of data references, polyhedral BBs, and
   alias sets.  */

struct dr_info
{
  enum {
    invalid_alias_set = -1
  };
  /* The data reference.  */
  data_reference_p dr;

  /* The polyhedral BB containing this DR.  */
  poly_bb_p pbb;

  /* ALIAS_SET is the SCC number assigned by a graph_dfs of the alias graph.
     -1 is an invalid alias set.  */
  int alias_set;

  /* Construct a DR_INFO from a data reference DR, an ALIAS_SET, and a PBB.  */
  dr_info (data_reference_p dr, poly_bb_p pbb,
	   int alias_set = invalid_alias_set)
    : dr (dr), pbb (pbb), alias_set (alias_set) {}
};

/* A SCOP is a Static Control Part of the program, simple enough to be
   represented in polyhedral form.  */
struct scop
{
  /* A SCOP is defined as a SESE region.  */
  sese_info_p scop_info;

  /* Number of parameters in SCoP.  */
  graphite_dim_t nb_params;

  /* All the basic blocks in this scop that contain memory references
     and that will be represented as statements in the polyhedral
     representation.  */
  vec<poly_bb_p> pbbs;

  /* All the data references in this scop.  */
  vec<dr_info> drs;

  /* The context describes known restrictions concerning the parameters
     and relations in between the parameters.

  void f (int8_t a, uint_16_t b) {
    c = 2 a + b;
    ...
  }

  Here we can add these restrictions to the context:

  -128 >= a >= 127
     0 >= b >= 65,535
     c = 2a + b  */
  isl_set *param_context;

  /* The context used internally by ISL.  */
  isl_ctx *isl_context;

  /* The original dependence relations:
     RAW are read after write dependences,
     WAR are write after read dependences,
     WAW are write after write dependences.  */
  isl_union_map *must_raw, *may_raw, *must_raw_no_source, *may_raw_no_source,
    *must_war, *may_war, *must_war_no_source, *may_war_no_source,
    *must_waw, *may_waw, *must_waw_no_source, *may_waw_no_source;
};

extern scop_p new_scop (edge, edge);
extern void free_scop (scop_p);
extern gimple_poly_bb_p new_gimple_poly_bb (basic_block, vec<data_reference_p>,
					    vec<scalar_use>, vec<tree>);
extern void free_gimple_poly_bb (gimple_poly_bb_p);
extern void print_generated_program (FILE *, scop_p);
extern void debug_generated_program (scop_p);
extern int unify_scattering_dimensions (scop_p);
extern bool apply_poly_transforms (scop_p);

/* Set the region of SCOP to REGION.  */

static inline void
scop_set_region (scop_p scop, sese_info_p region)
{
  scop->scop_info = region;
}

/* Returns the number of parameters for SCOP.  */

static inline graphite_dim_t
scop_nb_params (scop_p scop)
{
  return scop->nb_params;
}

/* Set the number of params of SCOP to NB_PARAMS.  */

static inline void
scop_set_nb_params (scop_p scop, graphite_dim_t nb_params)
{
  scop->nb_params = nb_params;
}

isl_union_map *
scop_get_dependences (scop_p scop);

bool
carries_deps (__isl_keep isl_union_map *schedule,
	      __isl_keep isl_union_map *deps,
	      int depth);

extern bool build_poly_scop (scop_p);
extern bool graphite_regenerate_ast_isl (scop_p);

extern void build_scops (vec<scop_p> *);
extern void dot_all_sese (FILE *, vec<sese_l> &);
extern void dot_sese (sese_l &);
extern void dot_cfg ();
#endif
Commit	Line	Data
2abae5f1	1	/* Graphite polyhedral representation.
5624e564	2	Copyright (C) 2009-2015 Free Software Foundation, Inc.
2abae5f1 SP	3	Contributed by Sebastian Pop <sebastian.pop@amd.com> and
	4	Tobias Grosser <grosser@fim.uni-passau.de>.
	5
	6	This file is part of GCC.
	7
	8	GCC is free software; you can redistribute it and/or modify
	9	it under the terms of the GNU General Public License as published by
	10	the Free Software Foundation; either version 3, or (at your option)
	11	any later version.
	12
	13	GCC is distributed in the hope that it will be useful,
	14	but WITHOUT ANY WARRANTY; without even the implied warranty of
	15	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	16	GNU General Public License for more details.
	17
	18	You should have received a copy of the GNU General Public License
	19	along with GCC; see the file COPYING3. If not see
	20	<http://www.gnu.org/licenses/>. */
	21
	22	#ifndef GCC_GRAPHITE_POLY_H
	23	#define GCC_GRAPHITE_POLY_H
	24
9c358739 AM	25	#include "sese.h"
9c358739 AM	26
32400032	27	#ifndef HAVE_ISL_OPTIONS_SET_SCHEDULE_SERIALIZE_SCCS
560d18d3	28	/* isl 0.14. */
32400032 MF	29	# define isl_stat int
	30	# define isl_stat_ok 0
	31	#endif
	32
2abae5f1	33	typedef struct poly_dr *poly_dr_p;
2abae5f1 SP	34
2abae5f1 SP	35	typedef struct poly_bb *poly_bb_p;
2abae5f1 SP	36
2abae5f1 SP	37	typedef struct scop *scop_p;
2abae5f1	38
33ad93b9	39	typedef unsigned graphite_dim_t;
2abae5f1	40
2abae5f1 SP	41	static inline graphite_dim_t scop_nb_params (scop_p);
	42
	43	/* A data reference can write or read some memory or we
	44	just know it may write some memory. */
e6dec0fb	45	enum poly_dr_type
2abae5f1 SP	46	{
2abae5f1 SP	47	PDR_READ,
d8eeb078 SP	48	/* PDR_MAY_READs are represented using PDR_READS. This does not
d8eeb078 SP	49	limit the expressiveness. */
2abae5f1 SP	50	PDR_WRITE,
	51	PDR_MAY_WRITE
	52	};
	53
	54	struct poly_dr
	55	{
afae0207 SP	56	/* An identifier for this PDR. */
	57	int id;
	58
7bd2a8a7 SP	59	/* The number of data refs identical to this one in the PBB. */
	60	int nb_refs;
	61
65b016eb AK	62	/* A pointer to the gimple stmt containing this reference. */
65b016eb AK	63	gimple *stmt;
2abae5f1 SP	64
	65	/* A pointer to the PBB that contains this data reference. */
	66	poly_bb_p pbb;
	67
e6dec0fb	68	enum poly_dr_type type;
2abae5f1 SP	69
	70	/* The access polyhedron contains the polyhedral space this data
	71	reference will access.
	72
	73	The polyhedron contains these dimensions:
	74
1825f9a2 LF	75	- The alias set (a):
1825f9a2 LF	76	Every memory access is classified in at least one alias set.
2abae5f1	77
1825f9a2 LF	78	- The subscripts (s_0, ..., s_n):
1825f9a2 LF	79	The memory is accessed using zero or more subscript dimensions.
2abae5f1	80
1825f9a2	81	- The iteration domain (variables and parameters)
2abae5f1 SP	82
	83	Do not hardcode the dimensions. Use the following accessor functions:
	84	- pdr_alias_set_dim
	85	- pdr_subscript_dim
	86	- pdr_iterator_dim
	87	- pdr_parameter_dim
	88
	89	Example:
	90
	91	\| int A[1335][123];
	92	\| int *p = malloc ();
	93	\|
	94	\| k = ...
	95	\| for i
	96	\| {
	97	\| if (unknown_function ())
	98	\| p = A;
	99	\| ... = p[?][?];
	100	\| for j
25d7cc15	101	\| A[i][j+k] = m;
2abae5f1 SP	102	\| }
	103
	104	The data access A[i][j+k] in alias set "5" is described like this:
	105
25d7cc15	106	\| i j k a s0 s1 1
2abae5f1 SP	107	\| 0 0 0 1 0 0 -5 = 0
	108	\|-1 0 0 0 1 0 0 = 0
	109	\| 0 -1 -1 0 0 1 0 = 0
66096911 SP	110	\| 0 0 0 0 1 0 0 >= 0 # The last four lines describe the
66096911 SP	111	\| 0 0 0 0 0 1 0 >= 0 # array size.
2abae5f1 SP	112	\| 0 0 0 0 -1 0 1335 >= 0
	113	\| 0 0 0 0 0 -1 123 >= 0
	114
	115	The pointer "*p" in alias set "5" and "7" is described as a union of
	116	polyhedron:
	117
	118
25d7cc15	119	\| i k a s0 1
2abae5f1 SP	120	\| 0 0 1 0 -5 = 0
	121	\| 0 0 0 1 0 >= 0
	122
	123	"or"
	124
25d7cc15	125	\| i k a s0 1
2abae5f1 SP	126	\| 0 0 1 0 -7 = 0
	127	\| 0 0 0 1 0 >= 0
	128
	129	"*p" accesses all of the object allocated with 'malloc'.
	130
	131	The scalar data access "m" is represented as an array with zero subscript
	132	dimensions.
	133
	134	\| i j k a 1
ae403f5a RB	135	\| 0 0 0 -1 15 = 0
	136
	137	The difference between the graphite internal format for access data and
	138	the OpenSop format is in the order of columns.
	139	Instead of having:
	140
	141	\| i j k a s0 s1 1
	142	\| 0 0 0 1 0 0 -5 = 0
	143	\|-1 0 0 0 1 0 0 = 0
	144	\| 0 -1 -1 0 0 1 0 = 0
	145	\| 0 0 0 0 1 0 0 >= 0 # The last four lines describe the
	146	\| 0 0 0 0 0 1 0 >= 0 # array size.
	147	\| 0 0 0 0 -1 0 1335 >= 0
	148	\| 0 0 0 0 0 -1 123 >= 0
	149
	150	In OpenScop we have:
	151
	152	\| a s0 s1 i j k 1
	153	\| 1 0 0 0 0 0 -5 = 0
	154	\| 0 1 0 -1 0 0 0 = 0
	155	\| 0 0 1 0 -1 -1 0 = 0
	156	\| 0 1 0 0 0 0 0 >= 0 # The last four lines describe the
	157	\| 0 0 1 0 0 0 0 >= 0 # array size.
	158	\| 0 -1 0 0 0 0 1335 >= 0
	159	\| 0 0 -1 0 0 0 123 >= 0
	160
	161	The OpenScop access function is printed as follows:
	162
	163	\| 1 # The number of disjunct components in a union of access functions.
	164	\| R C O I L P # Described bellow.
	165	\| a s0 s1 i j k 1
	166	\| 1 0 0 0 0 0 -5 = 0
	167	\| 0 1 0 -1 0 0 0 = 0
	168	\| 0 0 1 0 -1 -1 0 = 0
	169	\| 0 1 0 0 0 0 0 >= 0 # The last four lines describe the
	170	\| 0 0 1 0 0 0 0 >= 0 # array size.
	171	\| 0 -1 0 0 0 0 1335 >= 0
	172	\| 0 0 -1 0 0 0 123 >= 0
	173
	174	Where:
	175	- R: Number of rows.
	176	- C: Number of columns.
	177	- O: Number of output dimensions = alias set + number of subscripts.
	178	- I: Number of input dimensions (iterators).
	179	- L: Number of local (existentially quantified) dimensions.
	180	- P: Number of parameters.
	181
	182	In the example, the vector "R C O I L P" is "7 7 3 2 0 1". */
33ad93b9	183	isl_map *accesses;
24757752	184	isl_set *subscript_sizes;
2abae5f1 SP	185	};
2abae5f1 SP	186
afae0207	187	#define PDR_ID(PDR) (PDR->id)
7bd2a8a7	188	#define PDR_NB_REFS(PDR) (PDR->nb_refs)
2abae5f1 SP	189	#define PDR_PBB(PDR) (PDR->pbb)
2abae5f1 SP	190	#define PDR_TYPE(PDR) (PDR->type)
33ad93b9	191	#define PDR_ACCESSES(PDR) (NULL)
2abae5f1	192
65b016eb AK	193	void new_poly_dr (poly_bb_p, gimple *, enum poly_dr_type,
65b016eb AK	194	isl_map , isl_set );
2abae5f1	195	void free_poly_dr (poly_dr_p);
5c24066b AK	196	void debug_pdr (poly_dr_p);
5c24066b AK	197	void print_pdr (FILE *, poly_dr_p);
d8eeb078 SP	198
	199	static inline bool
	200	pdr_read_p (poly_dr_p pdr)
	201	{
	202	return PDR_TYPE (pdr) == PDR_READ;
	203	}
	204
	205	/* Returns true when PDR is a "write". */
	206
	207	static inline bool
	208	pdr_write_p (poly_dr_p pdr)
	209	{
	210	return PDR_TYPE (pdr) == PDR_WRITE;
	211	}
	212
	213	/* Returns true when PDR is a "may write". */
	214
	215	static inline bool
	216	pdr_may_write_p (poly_dr_p pdr)
	217	{
	218	return PDR_TYPE (pdr) == PDR_MAY_WRITE;
	219	}
	220
2abae5f1 SP	221	/* POLY_BB represents a blackbox in the polyhedral model. */
	222
	223	struct poly_bb
	224	{
a1954f72	225	/* Pointer to a basic block or a statement in the compiler. */
8e4dc590	226	gimple_poly_bb_p black_box;
2abae5f1	227
a1954f72	228	/* Pointer to the SCOP containing this PBB. */
2abae5f1 SP	229	scop_p scop;
2abae5f1 SP	230
aa52513e SP	231	/* The iteration domain of this bb. The layout of this polyhedron
	232	is I\|G with I the iteration domain, G the context parameters.
	233
2abae5f1 SP	234	Example:
	235
	236	for (i = a - 7b + 8; i <= 3a + 13*b + 20; i++)
	237	for (j = 2; j <= 2*i + 5; j++)
	238	for (k = 0; k <= 5; k++)
	239	S (i,j,k)
	240
	241	Loop iterators: i, j, k
	242	Parameters: a, b
	243
	244	\| i >= a - 7b + 8
	245	\| i <= 3a + 13b + 20
	246	\| j >= 2
	247	\| j <= 2i + 5
	248	\| k >= 0
	249	\| k <= 5
	250
	251	The number of variables in the DOMAIN may change and is not
	252	related to the number of loops in the original code. */
33ad93b9	253	isl_set *domain;
2abae5f1 SP	254
2abae5f1 SP	255	/* The data references we access. */
9771b263	256	vec<poly_dr_p> drs;
2abae5f1	257
f4648ed1	258	/* The original scattering. */
33ad93b9	259	isl_map *schedule;
2abae5f1	260
f4648ed1	261	/* The transformed scattering. */
33ad93b9	262	isl_map *transformed;
2abae5f1	263
f4648ed1	264	/* A copy of the transformed scattering. */
33ad93b9	265	isl_map *saved;
a0dd1440 SP	266
	267	/* True when this PBB contains only a reduction statement. */
	268	bool is_reduction;
65b016eb AK	269
	270	/* The last basic block generated for this pbb. */
	271	basic_block new_bb;
2abae5f1 SP	272	};
2abae5f1 SP	273
65ef70d6	274	#define PBB_BLACK_BOX(PBB) ((gimple_poly_bb_p) PBB->black_box)
2abae5f1	275	#define PBB_SCOP(PBB) (PBB->scop)
2abae5f1	276	#define PBB_DRS(PBB) (PBB->drs)
a0dd1440	277	#define PBB_IS_REDUCTION(PBB) (PBB->is_reduction)
2abae5f1	278
8e4dc590	279	extern poly_bb_p new_poly_bb (scop_p, gimple_poly_bb_p);
2abae5f1 SP	280	extern void free_poly_bb (poly_bb_p);
2abae5f1 SP	281	extern void debug_loop_vec (poly_bb_p);
5c24066b AK	282	extern void print_pbb_domain (FILE *, poly_bb_p);
	283	extern void print_pbb (FILE *, poly_bb_p);
	284	extern void print_scop_context (FILE *, scop_p);
	285	extern void print_scop (FILE *, scop_p);
	286	extern void debug_pbb_domain (poly_bb_p);
	287	extern void debug_pbb (poly_bb_p);
	288	extern void print_pdrs (FILE *, poly_bb_p);
	289	extern void debug_pdrs (poly_bb_p);
	290	extern void debug_scop_context (scop_p);
	291	extern void debug_scop (scop_p);
	292	extern void print_scop_params (FILE *, scop_p);
	293	extern void debug_scop_params (scop_p);
	294	extern void print_iteration_domain (FILE *, poly_bb_p);
	295	extern void print_iteration_domains (FILE *, scop_p);
	296	extern void debug_iteration_domain (poly_bb_p);
	297	extern void debug_iteration_domains (scop_p);
33ad93b9 RG	298	extern void print_isl_set (FILE , isl_set );
33ad93b9 RG	299	extern void print_isl_map (FILE , isl_map );
ea17c0fe	300	extern void print_isl_union_map (FILE , isl_union_map );
33ad93b9 RG	301	extern void print_isl_aff (FILE , isl_aff );
	302	extern void print_isl_constraint (FILE , isl_constraint );
	303	extern void debug_isl_set (isl_set *);
	304	extern void debug_isl_map (isl_map *);
ea17c0fe	305	extern void debug_isl_union_map (isl_union_map *);
33ad93b9 RG	306	extern void debug_isl_aff (isl_aff *);
33ad93b9 RG	307	extern void debug_isl_constraint (isl_constraint *);
cec11ec4 SP	308	extern int scop_do_interchange (scop_p);
cec11ec4 SP	309	extern int scop_do_strip_mine (scop_p, int);
25e20d33	310	extern bool scop_do_block (scop_p);
98af4c9f	311	extern bool flatten_all_loops (scop_p);
c3284718	312	extern bool optimize_isl (scop_p);
e262fdda	313	extern void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, mpz_t);
33ad93b9	314	extern void debug_gmp_value (mpz_t);
2abae5f1	315
03922af3	316	/* The basic block of the PBB. */
072edf07	317
03922af3 SP	318	static inline basic_block
	319	pbb_bb (poly_bb_p pbb)
	320	{
	321	return GBB_BB (PBB_BLACK_BOX (pbb));
	322	}
	323
afae0207 SP	324	static inline int
	325	pbb_index (poly_bb_p pbb)
	326	{
03922af3	327	return pbb_bb (pbb)->index;
afae0207 SP	328	}
afae0207 SP	329
d48e288d SP	330	/* The loop of the PBB. */
	331
	332	static inline loop_p
	333	pbb_loop (poly_bb_p pbb)
	334	{
	335	return gbb_loop (PBB_BLACK_BOX (pbb));
	336	}
	337
2abae5f1 SP	338	/* The scop that contains the PDR. */
2abae5f1 SP	339
afae0207 SP	340	static inline scop_p
afae0207 SP	341	pdr_scop (poly_dr_p pdr)
2abae5f1 SP	342	{
	343	return PBB_SCOP (PDR_PBB (pdr));
	344	}
	345
	346	/* Set black box of PBB to BLACKBOX. */
	347
	348	static inline void
8e4dc590	349	pbb_set_black_box (poly_bb_p pbb, gimple_poly_bb_p black_box)
2abae5f1 SP	350	{
	351	pbb->black_box = black_box;
	352	}
	353
09fefdad AK	354	/* A helper structure to keep track of data references, polyhedral BBs, and
	355	alias sets. */
	356
	357	struct dr_info
	358	{
caf5b4df AK	359	enum {
	360	invalid_alias_set = -1
	361	};
09fefdad AK	362	/* The data reference. */
	363	data_reference_p dr;
	364
09fefdad AK	365	/* The polyhedral BB containing this DR. */
	366	poly_bb_p pbb;
	367
caf5b4df AK	368	/* ALIAS_SET is the SCC number assigned by a graph_dfs of the alias graph.
	369	-1 is an invalid alias set. */
	370	int alias_set;
	371
09fefdad	372	/* Construct a DR_INFO from a data reference DR, an ALIAS_SET, and a PBB. */
caf5b4df AK	373	dr_info (data_reference_p dr, poly_bb_p pbb,
	374	int alias_set = invalid_alias_set)
	375	: dr (dr), pbb (pbb), alias_set (alias_set) {}
09fefdad AK	376	};
09fefdad AK	377
2abae5f1 SP	378	/* A SCOP is a Static Control Part of the program, simple enough to be
	379	represented in polyhedral form. */
	380	struct scop
	381	{
	382	/* A SCOP is defined as a SESE region. */
d37fc3aa	383	sese_info_p scop_info;
2abae5f1 SP	384
	385	/* Number of parameters in SCoP. */
	386	graphite_dim_t nb_params;
	387
	388	/* All the basic blocks in this scop that contain memory references
	389	and that will be represented as statements in the polyhedral
	390	representation. */
b0b5710c	391	vec<poly_bb_p> pbbs;
2abae5f1	392
09fefdad AK	393	/* All the data references in this scop. */
	394	vec<dr_info> drs;
	395
2abae5f1 SP	396	/* The context describes known restrictions concerning the parameters
	397	and relations in between the parameters.
	398
	399	void f (int8_t a, uint_16_t b) {
	400	c = 2 a + b;
	401	...
	402	}
	403
	404	Here we can add these restrictions to the context:
	405
	406	-128 >= a >= 127
	407	0 >= b >= 65,535
	408	c = 2a + b */
8e4dc590	409	isl_set *param_context;
33ad93b9 RG	410
33ad93b9 RG	411	/* The context used internally by ISL. */
8e4dc590	412	isl_ctx *isl_context;
33ad93b9 RG	413
	414	/* The original dependence relations:
	415	RAW are read after write dependences,
	416	WAR are write after read dependences,
	417	WAW are write after write dependences. */
	418	isl_union_map must_raw, may_raw, must_raw_no_source, may_raw_no_source,
	419	must_war, may_war, must_war_no_source, may_war_no_source,
	420	must_waw, may_waw, must_waw_no_source, may_waw_no_source;
2abae5f1 SP	421	};
2abae5f1 SP	422
87ccab5d	423	extern scop_p new_scop (edge, edge);
2abae5f1	424	extern void free_scop (scop_p);
65b016eb AK	425	extern gimple_poly_bb_p new_gimple_poly_bb (basic_block, vec<data_reference_p>,
65b016eb AK	426	vec<scalar_use>, vec<tree>);
87ccab5d	427	extern void free_gimple_poly_bb (gimple_poly_bb_p);
2abae5f1 SP	428	extern void print_generated_program (FILE *, scop_p);
2abae5f1 SP	429	extern void debug_generated_program (scop_p);
2abae5f1 SP	430	extern int unify_scattering_dimensions (scop_p);
2abae5f1 SP	431	extern bool apply_poly_transforms (scop_p);
2abae5f1 SP	432
	433	/* Set the region of SCOP to REGION. */
	434
	435	static inline void
bafcb153	436	scop_set_region (scop_p scop, sese_info_p region)
2abae5f1	437	{
d37fc3aa	438	scop->scop_info = region;
2abae5f1 SP	439	}
	440
	441	/* Returns the number of parameters for SCOP. */
	442
	443	static inline graphite_dim_t
	444	scop_nb_params (scop_p scop)
	445	{
	446	return scop->nb_params;
	447	}
	448
	449	/* Set the number of params of SCOP to NB_PARAMS. */
	450
	451	static inline void
	452	scop_set_nb_params (scop_p scop, graphite_dim_t nb_params)
	453	{
	454	scop->nb_params = nb_params;
	455	}
	456
574921c2 RG	457	isl_union_map *
	458	scop_get_dependences (scop_p scop);
	459
	460	bool
	461	carries_deps (__isl_keep isl_union_map *schedule,
	462	__isl_keep isl_union_map *deps,
	463	int depth);
	464
cf98f0f4 AK	465	extern bool build_poly_scop (scop_p);
	466	extern bool graphite_regenerate_ast_isl (scop_p);
	467
	468	extern void build_scops (vec<scop_p> *);
15256e28 AK	469	extern void dot_all_sese (FILE *, vec<sese_l> &);
	470	extern void dot_sese (sese_l &);
	471	extern void dot_cfg ();
2abae5f1	472	#endif