-/* Gimple Represented as Polyhedra.
- Copyright (C) 2006, 2007, 2008 Free Software Foundation, Inc.
- Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
+/* Graphite polyhedral representation.
+ Copyright (C) 2009-2020 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.
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
-#ifndef GCC_GRAPHITE_H
-#define GCC_GRAPHITE_H
+#ifndef GCC_GRAPHITE_POLY_H
+#define GCC_GRAPHITE_POLY_H
-#include "tree-data-ref.h"
+#include "sese.h"
+#include <isl/options.h>
+#include <isl/ctx.h>
+#include <isl/val.h>
+#include <isl/set.h>
+#include <isl/union_set.h>
+#include <isl/map.h>
+#include <isl/union_map.h>
+#include <isl/aff.h>
+#include <isl/constraint.h>
+#include <isl/flow.h>
+#include <isl/ilp.h>
+#include <isl/schedule.h>
+#include <isl/ast_build.h>
+#include <isl/schedule_node.h>
+#include <isl/id.h>
+#include <isl/space.h>
-typedef struct graphite_bb *graphite_bb_p;
-DEF_VEC_P(graphite_bb_p);
-DEF_VEC_ALLOC_P (graphite_bb_p, heap);
+typedef struct poly_dr *poly_dr_p;
-DEF_VEC_P(scop_p);
-DEF_VEC_ALLOC_P (scop_p, heap);
+typedef struct poly_bb *poly_bb_p;
-static inline int scop_nb_loops (scop_p scop);
-static inline unsigned scop_nb_params (scop_p scop);
-static inline bool scop_contains_loop (scop_p scop, struct loop *loop);
+typedef struct scop *scop_p;
-typedef struct graphite_bb
-{
- basic_block bb;
- scop_p scop;
-
- /* The static schedule contains the textual order for every loop layer.
-
- Example:
-
- S0
- for (i ...)
- {
- S1
- for (j ...)
- {
- S2
- S3
- }
- S4
- }
- S5
- for (k ...)
- {
- S6
- S7
- for (l ...)
- {
- S8
- }
- S9
- }
- S10
-
- Schedules:
-
- | Depth
- BB | 0 1 2
- ------------
- S0 | 0
- S1 | 1, 0
- S2 | 1, 1, 0
- S3 | 1, 1, 1
- S4 | 1, 2
- S5 | 2
- S6 | 3, 0
- S7 | 3, 1
- S8 | 3, 2, 0
- S9 | 3, 3
- S10| 4
-
- Normalization rules:
- - One SCoP can never contain two bbs with the same schedule timestamp.
- - All bbs at the same loop depth have a consecutive ordering (no gaps). */
- lambda_vector static_schedule;
-
- /* The iteration domain of this bb. It contains this columns:
- - In/Eq: If this line is a equation or inequation.
- - For every loop iterator one column.
- - One column for every parameter in this SCoP.
- - The constant column to add integers to the (in)equations.
-
- 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)eq i j k a b 1
-
- 1 1 0 0 -1 7 -8 # i >= a - 7b + 8
- 1 -1 0 0 3 13 20 # i <= 3a + 13b + 20
- 1 0 1 0 0 0 -2 # j >= 2
- 1 2 -1 0 0 0 5 # j <= 2i + 5
- 1 0 0 1 0 0 0 # k >= 0
- 1 0 0 -1 0 0 5 # k <= 5
-
- The number of loop iterators may change and is not connected to the
- number of loops, that surrounded this bb in the gimple code. */
- CloogMatrix *domain;
-
- /* Lists containing the restrictions of the conditional statements
- dominating this bb. This bb can only be executed, if all conditions
- are true.
-
- Example:
-
- for (i = 0; i <= 20; i++)
- {
- A
-
- if (2i <= 8)
- B
- }
-
- So for B there is an additional condition (2i <= 8).
-
- TODO: Add these restrictions to the domain matrix.
-
- List of COND_EXPR and SWITCH_EXPR. A COND_EXPR is true only if the
- corresponding element in CONDITION_CASES is not NULL_TREE. For a
- SWITCH_EXPR the corresponding element in CONDITION_CASES is a
- CASE_LABEL_EXPR. */
- VEC (gimple, heap) *conditions;
- VEC (gimple, heap) *condition_cases;
-
- /* LOOPS contains for every column in the graphite domain the corresponding
- gimple loop. If there exists no corresponding gimple loop LOOPS contains
- NULL.
-
- Example:
-
- Original code:
-
- for (i = 0; i <= 20; i++)
- for (j = 5; j <= 10; j++)
- A
-
- Original domain:
-
- (I)eq i j 1
- 1 1 0 0 # i >= 0
- 1 -1 0 20 # i <= 20
- 1 0 1 0 # j >= 0
- 1 0 -1 10 # j <= 10
-
- Original loops vector:
- 0 1
- Loop i Loop j
-
- After some changes (Exchange i and j, strip-mine i):
-
- Domain:
-
- (I)eq j ii i k 1
- 1 0 0 1 0 0 # i >= 0
- 1 0 0 -1 0 20 # i <= 20
- 1 1 0 0 0 0 # j >= 0
- 1 -1 0 0 0 10 # j <= 10
- 1 0 -1 1 0 0 # ii <= i
- 1 0 1 -1 0 1 # ii + 1 >= i
- 1 0 -1 0 2 0 # ii <= 2k
- 1 0 1 0 -2 0 # ii >= 2k
-
- Iterator vector:
- 0 1 2 3
- Loop j NULL Loop i NULL
-
- Means the original loop i is now at column two of the domain and
- loop j in the original loop nest is now at column 0. Column 1 and
- 3 are emtpy. */
- VEC (loop_p, heap) *loops;
-
- lambda_vector compressed_alpha_matrix;
- CloogMatrix *dynamic_schedule;
- VEC (data_reference_p, heap) *data_refs;
- htab_t cloog_iv_types;
-} *gbb_p;
-
-#define GBB_BB(GBB) GBB->bb
-#define GBB_SCOP(GBB) GBB->scop
-#define GBB_STATIC_SCHEDULE(GBB) GBB->static_schedule
-#define GBB_DATA_REFS(GBB) GBB->data_refs
-#define GBB_ALPHA(GBB) GBB->compressed_alpha_matrix
-#define GBB_DYNAMIC_SCHEDULE(GBB) GBB->dynamic_schedule
-#define GBB_DOMAIN(GBB) GBB->domain
-#define GBB_CONDITIONS(GBB) GBB->conditions
-#define GBB_CONDITION_CASES(GBB) GBB->condition_cases
-#define GBB_LOOPS(GBB) GBB->loops
-#define GBB_CLOOG_IV_TYPES(GBB) GBB->cloog_iv_types
-
-/* Return the loop that contains the basic block GBB. */
-
-static inline struct loop *
-gbb_loop (struct graphite_bb *gbb)
-{
- return GBB_BB (gbb)->loop_father;
-}
-
-/* Calculate the number of loops around GB in the current SCOP. Only
- works if GBB_DOMAIN is built. */
-
-static inline int
-gbb_nb_loops (const struct graphite_bb *gb)
-{
- scop_p scop = GBB_SCOP (gb);
-
- if (GBB_DOMAIN (gb) == NULL)
- return 0;
-
- return GBB_DOMAIN (gb)->NbColumns - scop_nb_params (scop) - 2;
-}
-
-/* Returns the gimple loop, that corresponds to the loop_iterator_INDEX.
- If there is no corresponding gimple loop, we return NULL. */
-
-static inline loop_p
-gbb_loop_at_index (graphite_bb_p gb, int index)
-{
- return VEC_index (loop_p, GBB_LOOPS (gb), index);
-}
+typedef unsigned graphite_dim_t;
-/* Returns the index of LOOP in the loop nest around GB. */
+static inline graphite_dim_t scop_nb_params (scop_p);
-static inline int
-gbb_loop_index (graphite_bb_p gb, loop_p loop)
-{
- int i;
- loop_p l;
-
- for (i = 0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, l); i++)
- if (loop == l)
- return i;
-
- gcc_unreachable();
-}
-
-struct loop_to_cloog_loop_str
+/* A data reference can write or read some memory or we
+ just know it may write some memory. */
+enum poly_dr_type
{
- unsigned int loop_num;
- unsigned int loop_position; /* The column that represents this loop. */
- CloogLoop *cloog_loop;
+ PDR_READ,
+ /* PDR_MAY_READs are represented using PDR_READS. This does not
+ limit the expressiveness. */
+ PDR_WRITE,
+ PDR_MAY_WRITE
};
-typedef struct name_tree
+struct poly_dr
{
- tree t;
- const char *name;
- struct loop *loop;
-} *name_tree;
+ /* An identifier for this PDR. */
+ int id;
-DEF_VEC_P(name_tree);
-DEF_VEC_ALLOC_P (name_tree, heap);
-
-/* A Single Entry, Single Exit region is a part of the CFG delimited
- by two edges. */
-typedef struct sese
-{
- /* Single ENTRY and single EXIT from the SESE region. */
- edge entry, exit;
+ /* The number of data refs identical to this one in the PBB. */
+ int nb_refs;
- /* REGION_BASIC_BLOCKS contains the set of all the basic blocks
- belonging to the SESE region. */
- struct pointer_set_t *region_basic_blocks;
-
- /* An SSA_NAME version is flagged in the LIVEOUT bitmap if the
- SSA_NAME is defined inside and used outside the SESE region. */
- bitmap liveout;
-
- /* The overall number of SSA_NAME versions used to index LIVEIN. */
- int num_ver;
-
- /* For each SSA_NAME version VER in LIVEOUT, LIVEIN[VER] contains
- the set of basic blocks indices that contain a use of VER. */
- bitmap *livein;
-} *sese;
-
-#define SESE_ENTRY(S) (S->entry)
-#define SESE_EXIT(S) (S->exit)
-#define SESE_REGION_BBS(S) (S->region_basic_blocks)
-#define SESE_LIVEOUT(S) (S->liveout)
-#define SESE_LIVEIN(S) (S->livein)
-#define SESE_LIVEIN_VER(S, I) (S->livein[I])
-#define SESE_NUM_VER(S) (S->num_ver)
-
-extern sese new_sese (edge, edge);
-extern void free_sese (sese);
-extern void sese_build_livein_liveouts (sese);
-
-/* 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 region;
+ /* A pointer to the gimple stmt containing this reference. */
+ gimple *stmt;
- /* All the basic blocks in this scop. They have extra information
- attached to them, in the graphite_bb structure. */
- VEC (graphite_bb_p, heap) *bbs;
+ /* A pointer to the PBB that contains this data reference. */
+ poly_bb_p pbb;
- /* Set for a basic block index when it belongs to this SCOP. */
- bitmap bbs_b;
+ enum poly_dr_type type;
- lambda_vector static_schedule;
+ /* The access polyhedron contains the polyhedral space this data
+ reference will access.
- /* Parameters used within the SCOP. */
- VEC (name_tree, heap) *params;
+ The polyhedron contains these dimensions:
- /* A collection of old induction variables*/
- VEC (name_tree, heap) *old_ivs;
+ - The alias set (a):
+ Every memory access is classified in at least one alias set.
- /* Loops completely contained in the SCOP. */
- bitmap loops;
- VEC (loop_p, heap) *loop_nest;
+ - The subscripts (s_0, ..., s_n):
+ The memory is accessed using zero or more subscript dimensions.
- /* ??? It looks like a global mapping loop_id -> cloog_loop would work. */
- htab_t loop2cloog_loop;
+ - The iteration domain (variables and parameters)
- /* Cloog representation of this scop. */
- CloogProgram *program;
+ Do not hardcode the dimensions. Use the following accessor functions:
+ - pdr_alias_set_dim
+ - pdr_subscript_dim
+ - pdr_iterator_dim
+ - pdr_parameter_dim
- /* Are we allowed to add more params? This is for debugging purpose. We
- can only add new params before generating the bb domains, otherwise they
- become invalid. */
- bool add_params;
+ Example:
- /* LIVEOUT_RENAMES registers the rename mapping that has to be
- applied after code generation. */
- htab_t liveout_renames;
+ | 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 SCOP_BBS(S) S->bbs
-#define SCOP_BBS_B(S) S->bbs_b
-#define SCOP_REGION(S) S->region
-/* SCOP_ENTRY bb dominates all the bbs of the scop. SCOP_EXIT bb
- post-dominates all the bbs of the scop. SCOP_EXIT potentially
- contains non affine data accesses, side effect statements or
- difficult constructs, and thus is not considered part of the scop,
- but just a boundary. SCOP_ENTRY is considered part of the scop. */
-#define SCOP_ENTRY(S) (SESE_ENTRY (SCOP_REGION (S))->dest)
-#define SCOP_EXIT(S) (SESE_EXIT (SCOP_REGION (S))->dest)
-#define SCOP_REGION_BBS(S) (SESE_REGION_BBS (SCOP_REGION (S)))
-#define SCOP_STATIC_SCHEDULE(S) S->static_schedule
-#define SCOP_LOOPS(S) S->loops
-#define SCOP_LOOP_NEST(S) S->loop_nest
-#define SCOP_ADD_PARAMS(S) S->add_params
-#define SCOP_PARAMS(S) S->params
-#define SCOP_OLDIVS(S) S->old_ivs
-#define SCOP_PROG(S) S->program
-#define SCOP_LOOP2CLOOG_LOOP(S) S->loop2cloog_loop
-#define SCOP_LOOPS_MAPPING(S) S->loops_mapping
-#define SCOP_LIVEOUT_RENAMES(S) S->liveout_renames
-
-extern void debug_scop (scop_p, int);
-extern void debug_scops (int);
-extern void print_graphite_bb (FILE *, graphite_bb_p, int, int);
-extern void debug_gbb (graphite_bb_p, int);
-extern void dot_scop (scop_p);
-extern void dot_all_scops (void);
-extern void debug_clast_stmt (struct clast_stmt *);
-extern void debug_rename_map (htab_t);
-extern void debug_ivtype_map (htab_t);
-extern void debug_loop_vec (graphite_bb_p);
-extern void debug_oldivs (scop_p);
-extern void debug_value (Value);
-
-/* Describes the type of an iv stack entry. */
-typedef enum {
- iv_stack_entry_unknown = 0,
- iv_stack_entry_iv,
- iv_stack_entry_const
-} iv_stack_entry_kind;
-
-/* Data contained in an iv stack entry. */
-typedef union iv_stack_entry_data_union
-{
- name_tree iv;
- tree constant;
-} iv_stack_entry_data;
-
-/* Datatype for loop iv stack entry. */
-typedef struct iv_stack_entry_struct
-{
- iv_stack_entry_kind kind;
- iv_stack_entry_data data;
-} iv_stack_entry;
+#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)
-typedef iv_stack_entry *iv_stack_entry_p;
+void new_poly_dr (poly_bb_p, gimple *, enum poly_dr_type,
+ isl_map *, isl_set *);
+void debug_pdr (poly_dr_p);
+void print_pdr (FILE *, poly_dr_p);
-DEF_VEC_P(iv_stack_entry_p);
-DEF_VEC_ALLOC_P(iv_stack_entry_p,heap);
-
-typedef VEC(iv_stack_entry_p, heap) **loop_iv_stack;
-extern void debug_loop_iv_stack (loop_iv_stack);
-
-/* Return the old induction variable of the LOOP that is in normal
- form in SCOP. */
-
-static inline tree
-oldiv_for_loop (scop_p scop, loop_p loop)
+static inline bool
+pdr_read_p (poly_dr_p pdr)
{
- int i;
- name_tree iv;
-
- if (!loop)
- return NULL_TREE;
-
- for (i = 0; VEC_iterate (name_tree, SCOP_OLDIVS (scop), i, iv); i++)
- if (iv->loop == loop)
- return iv->t;
-
- return NULL_TREE;
+ return PDR_TYPE (pdr) == PDR_READ;
}
-/* Return the number of gimple loops contained in SCOP. */
+/* Returns true when PDR is a "write". */
-static inline int
-scop_nb_loops (scop_p scop)
+static inline bool
+pdr_write_p (poly_dr_p pdr)
{
- return VEC_length (loop_p, SCOP_LOOP_NEST (scop));
+ return PDR_TYPE (pdr) == PDR_WRITE;
}
-/* Returns the number of parameters for SCOP. */
+/* Returns true when PDR is a "may write". */
-static inline unsigned
-scop_nb_params (scop_p scop)
+static inline bool
+pdr_may_write_p (poly_dr_p pdr)
{
- return VEC_length (name_tree, SCOP_PARAMS (scop));
+ return PDR_TYPE (pdr) == PDR_MAY_WRITE;
}
-/* Return the dimension of the domains for SCOP. */
+/* POLY_BB represents a blackbox in the polyhedral model. */
-static inline int
-scop_dim_domain (scop_p scop)
+struct poly_bb
{
- return scop_nb_loops (scop) + scop_nb_params (scop) + 1;
-}
-
-/* Return the dimension of the domains for GB. */
+ /* Pointer to a basic block or a statement in the compiler. */
+ gimple_poly_bb_p black_box;
-static inline int
-gbb_dim_domain (graphite_bb_p gb)
-{
- return scop_dim_domain (GBB_SCOP (gb));
-}
+ /* Pointer to the SCOP containing this PBB. */
+ scop_p scop;
-/* Returns the dimensionality of a loop iteration domain for a given
- loop, identified by LOOP_NUM, with respect to SCOP. */
+ /* The iteration domain of this bb. The layout of this polyhedron
+ is I|G with I the iteration domain, G the context parameters.
-static inline int
-loop_domain_dim (unsigned int loop_num, scop_p scop)
-{
- struct loop_to_cloog_loop_str tmp, *slot;
- htab_t tab = SCOP_LOOP2CLOOG_LOOP (scop);
+ Example:
- tmp.loop_num = loop_num;
- slot = (struct loop_to_cloog_loop_str *) htab_find (tab, &tmp);
+ 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)
- /* The loop containing the entry of the scop is not always part of
- the SCoP, and it is not registered in SCOP_LOOP2CLOOG_LOOP. */
- if (!slot)
- return scop_nb_params (scop) + 2;
+ Loop iterators: i, j, k
+ Parameters: a, b
- return cloog_domain_dim (cloog_loop_domain (slot->cloog_loop)) + 2;
-}
+ | i >= a - 7b + 8
+ | i <= 3a + 13b + 20
+ | j >= 2
+ | j <= 2i + 5
+ | k >= 0
+ | k <= 5
-/* Returns the dimensionality of a loop iteration vector in a loop
- iteration domain for a given loop (identified by LOOP_NUM) with
- respect to SCOP. */
+ 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;
+ isl_set *iterators;
-static inline int
-loop_iteration_vector_dim (unsigned int loop_num, scop_p scop)
-{
- return loop_domain_dim (loop_num, scop) - 2 - scop_nb_params (scop);
-}
+ /* The data references we access. */
+ vec<poly_dr_p> drs;
-/* Checks, if SCOP contains LOOP. */
+ /* The last basic block generated for this pbb. */
+ basic_block new_bb;
+};
-static inline bool
-scop_contains_loop (scop_p scop, struct loop *loop)
+#define PBB_BLACK_BOX(PBB) ((gimple_poly_bb_p) PBB->black_box)
+#define PBB_SCOP(PBB) (PBB->scop)
+#define PBB_DRS(PBB) (PBB->drs)
+
+extern poly_bb_p new_poly_bb (scop_p, gimple_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 print_isl_schedule (FILE *, isl_schedule *);
+extern void debug_isl_schedule (isl_schedule *);
+extern void print_isl_ast (FILE *, isl_ast_node *);
+extern void debug_isl_ast (isl_ast_node *);
+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 void debug_gmp_value (mpz_t);
+extern void debug_scop_pbb (scop_p scop, int i);
+extern void print_schedule_ast (FILE *, __isl_keep isl_schedule *, scop_p);
+extern void debug_schedule_ast (__isl_keep isl_schedule *, scop_p);
+
+/* The basic block of the PBB. */
+
+static inline basic_block
+pbb_bb (poly_bb_p pbb)
{
- return bitmap_bit_p (SCOP_LOOPS (scop), loop->num);
+ return GBB_BB (PBB_BLACK_BOX (pbb));
}
-/* Returns the index of LOOP in the domain matrix for the SCOP. */
-
static inline int
-scop_loop_index (scop_p scop, struct loop *loop)
+pbb_index (poly_bb_p pbb)
{
- unsigned i;
- struct loop *l;
-
- gcc_assert (scop_contains_loop (scop, loop));
-
- for (i = 0; VEC_iterate (loop_p, SCOP_LOOP_NEST (scop), i, l); i++)
- if (l == loop)
- return i;
-
- gcc_unreachable();
+ return pbb_bb (pbb)->index;
}
-/* Return the index of innermost loop that contains the basic block
- GBB. */
+/* The loop of the PBB. */
-static inline int
-gbb_inner_most_loop_index (scop_p scop, graphite_bb_p gb)
+static inline loop_p
+pbb_loop (poly_bb_p pbb)
{
- return scop_loop_index(scop, gbb_loop (gb));
+ return gbb_loop (PBB_BLACK_BOX (pbb));
}
-/* Return the outermost loop that contains the loop LOOP. The outer
- loops are searched until a sibling for the outer loop is found. */
+/* The scop that contains the PDR. */
-static struct loop *
-outer_most_loop_1 (scop_p scop, struct loop* loop, struct loop* current_outer)
+static inline scop_p
+pdr_scop (poly_dr_p pdr)
{
- return (!scop_contains_loop (scop, loop)) ? current_outer :
- (loop->next != NULL) ? loop :
- outer_most_loop_1 (scop, loop_outer (loop), loop);
+ return PBB_SCOP (PDR_PBB (pdr));
}
-/* Return the outermost loop that contains the loop LOOP. */
+/* Set black box of PBB to BLACKBOX. */
-static struct loop *
-outer_most_loop (scop_p scop, struct loop *loop)
+static inline void
+pbb_set_black_box (poly_bb_p pbb, gimple_poly_bb_p black_box)
{
- return outer_most_loop_1 (scop, loop, NULL);
+ pbb->black_box = black_box;
}
-/* Return the index of the outermost loop that contains the basic
- block BB. */
+/* A helper structure to keep track of data references, polyhedral BBs, and
+ alias sets. */
-static inline int
-gbb_outer_most_loop_index (scop_p scop, graphite_bb_p gb)
+struct dr_info
{
- return scop_loop_index (scop, outer_most_loop (scop, gbb_loop (gb)));
-}
-
-/* Return the loop depth of LOOP in SCOP. */
+ 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) {}
+};
-static inline unsigned int
-scop_gimple_loop_depth (scop_p scop, loop_p loop)
+/* A SCOP is a Static Control Part of the program, simple enough to be
+ represented in polyhedral form. */
+struct scop
{
- unsigned int depth = 0;
+ /* A SCOP is defined as a SESE region. */
+ sese_info_p scop_info;
- loop = loop_outer (loop);
+ /* Number of parameters in SCoP. */
+ graphite_dim_t nb_params;
- while (scop_contains_loop (scop, loop))
- {
- depth++;
- loop = loop_outer (loop);
- }
+ /* The maximum alias set as assigned to drs by build_alias_sets. */
+ unsigned max_alias_set;
- return depth;
-}
+ /* 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;
-/* Static inline function prototypes. */
+ /* All the data references in this scop. */
+ vec<dr_info> drs;
-static inline unsigned scop_nb_params (scop_p scop);
+ /* The context describes known restrictions concerning the parameters
+ and relations in between the parameters.
-/* Returns true when BB is in SCOP. */
+ void f (int8_t a, uint_16_t b) {
+ c = 2 a + b;
+ ...
+ }
-static inline bool
-bb_in_scop_p (basic_block bb, scop_p scop)
-{
- return bitmap_bit_p (SCOP_BBS_B (scop), bb->index);
-}
+ Here we can add these restrictions to the context:
-/* Returns true when LOOP is in SCOP. */
+ -128 >= a >= 127
+ 0 >= b >= 65,535
+ c = 2a + b */
+ isl_set *param_context;
-static inline bool
-loop_in_scop_p (struct loop *loop, scop_p scop)
-{
- return (bb_in_scop_p (loop->header, scop)
- && bb_in_scop_p (loop->latch, scop));
-}
+ /* The context used internally by isl. */
+ isl_ctx *isl_context;
-/* Calculate the number of loops around LOOP in the SCOP. */
+ /* SCoP original schedule. */
+ isl_schedule *original_schedule;
-static inline int
-nb_loops_around_loop_in_scop (struct loop *l, scop_p scop)
-{
- int d = 0;
+ /* SCoP transformed schedule. */
+ isl_schedule *transformed_schedule;
- for (; loop_in_scop_p (l, scop); d++, l = loop_outer (l));
+ /* The data dependence relation among the data references in this scop. */
+ isl_union_map *dependence;
+};
- return d;
-}
+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 bool apply_poly_transforms (scop_p);
-/* Calculate the number of loops around GB in the current SCOP. */
+/* Set the region of SCOP to REGION. */
-static inline int
-nb_loops_around_gb (graphite_bb_p gb)
+static inline void
+scop_set_region (scop_p scop, sese_info_p region)
{
- return nb_loops_around_loop_in_scop (gbb_loop (gb), GBB_SCOP (gb));
+ scop->scop_info = region;
}
-/* Returns the dimensionality of an enclosing loop iteration domain
- with respect to enclosing SCoP for a given data reference REF. The
- returned dimensionality is homogeneous (depth of loop nest + number
- of SCoP parameters + const). */
+/* Returns the number of parameters for SCOP. */
-static inline int
-ref_nb_loops (data_reference_p ref)
+static inline graphite_dim_t
+scop_nb_params (scop_p scop)
{
- loop_p loop = loop_containing_stmt (DR_STMT (ref));
- scop_p scop = DR_SCOP (ref);
+ return scop->nb_params;
+}
- return nb_loops_around_loop_in_scop (loop, scop) + scop_nb_params (scop) + 2;
+/* 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;
}
-#endif /* GCC_GRAPHITE_H */
+extern void 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 tree cached_scalar_evolution_in_region (const sese_l &, loop_p, tree);
+extern void dot_all_sese (FILE *, vec<sese_l> &);
+extern void dot_sese (sese_l &);
+extern void dot_cfg ();
+
+#endif