diff options
Diffstat (limited to 'gcc/graphite.h')
| -rw-r--r-- | gcc/graphite.h | 516 |
1 files changed, 516 insertions, 0 deletions
diff --git a/gcc/graphite.h b/gcc/graphite.h new file mode 100644 index 00000000000..1a3cf6ccc65 --- /dev/null +++ b/gcc/graphite.h @@ -0,0 +1,516 @@ +/* Gimple Represented as Polyhedra. + Copyright (C) 2006, 2007, 2008 Free Software Foundation, Inc. + Contributed by Sebastian Pop <sebastian.pop@inria.fr>. + +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 "tree-data-ref.h" + +typedef struct graphite_bb *graphite_bb_p; +DEF_VEC_P(graphite_bb_p); +DEF_VEC_ALLOC_P (graphite_bb_p, heap); + +DEF_VEC_P(scop_p); +DEF_VEC_ALLOC_P (scop_p, heap); + +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); + +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 a additional condition (2i <= 8). + + TODO: Add this 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; +}; + +#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 + +/* 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); +} + +/* Returns the corresponding loop iterator index for a gimple loop. */ + +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 +{ + unsigned int loop_num; + unsigned int loop_position; /* The column that represents this loop. */ + CloogLoop *cloog_loop; +}; + +typedef struct name_tree +{ + tree t; + const char *name; + struct loop* loop; +} *name_tree; + +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 +{ + edge entry, exit; +} *sese; + +#define SESE_ENTRY(S) (S->entry) +#define SESE_EXIT(S) (S->exit) + +/* 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; + + /* 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; + + /* Set for a basic block index when it belongs to this SCOP. */ + bitmap bbs_b; + + lambda_vector static_schedule; + + /* Parameters used within the SCOP. */ + VEC (name_tree, heap) *params; + + /* A collection of old induction variables*/ + VEC (name_tree, heap) *old_ivs; + + /* Loops completely contained in the SCOP. */ + bitmap loops; + VEC (loop_p, heap) *loop_nest; + + /* ??? It looks like a global mapping loop_id -> cloog_loop would work. */ + htab_t loop2cloog_loop; + + /* CLooG representation of this SCOP. */ + CloogProgram *program; +}; + +#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_STATIC_SCHEDULE(S) S->static_schedule +#define SCOP_LOOPS(S) S->loops +#define SCOP_LOOP_NEST(S) S->loop_nest +#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 + +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_loop_vec (graphite_bb_p gb); +extern void debug_oldivs (scop_p); + +typedef VEC(name_tree, heap) **loop_iv_stack; +extern void loop_iv_stack_debug (loop_iv_stack); + + +/* Return the number of gimple loops contained in SCOP. */ + +static inline int +scop_nb_loops (scop_p scop) +{ + return VEC_length (loop_p, SCOP_LOOP_NEST (scop)); +} + +/* Returns the number of parameters for SCOP. */ + +static inline unsigned +scop_nb_params (scop_p scop) +{ + return VEC_length (name_tree, SCOP_PARAMS (scop)); +} + +/* Return the dimension of the domains for SCOP. */ + +static inline int +scop_dim_domain (scop_p scop) +{ + return scop_nb_loops (scop) + scop_nb_params (scop) + 1; +} + +/* Return the dimension of the domains for GB. */ + +static inline int +gbb_dim_domain (graphite_bb_p gb) +{ + return scop_dim_domain (GBB_SCOP (gb)); +} + +/* Returns the dimensionality of a loop iteration domain for a given + loop, identified by LOOP_NUM, with respect to SCOP. */ + +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); + + tmp.loop_num = loop_num; + slot = (struct loop_to_cloog_loop_str *) htab_find (tab, &tmp); + + /* 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; + + return cloog_domain_dim (cloog_loop_domain (slot->cloog_loop)) + 2; +} + +/* Returns the dimensionality of an enclosing loop iteration domain + with respect to enclosing SCoP for a given data reference REF. */ + +static inline int +ref_nb_loops (data_reference_p ref) +{ + return loop_domain_dim (loop_containing_stmt (DR_STMT (ref))->num, DR_SCOP (ref)); +} + +/* 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. */ + +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); +} + +/* Checks, if SCOP contains LOOP. */ + +static inline bool +scop_contains_loop (scop_p scop, struct loop *loop) +{ + return bitmap_bit_p (SCOP_LOOPS (scop), loop->num); +} + +/* Returns the index of LOOP in the domain matrix for the SCOP. */ + +static inline int +scop_loop_index (scop_p scop, struct loop *loop) +{ + 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 the index of innermost loop that contains the basic block + GBB. */ + +static inline int +gbb_inner_most_loop_index (scop_p scop, graphite_bb_p gb) +{ + return scop_loop_index(scop, gbb_loop (gb)); +} + +/* Return the outermost loop that contains the loop LOOP. The outer + loops are searched until a sibling for the outer loop is found. */ + +static struct loop * +outer_most_loop_1 (scop_p scop, struct loop* loop, struct loop* current_outer) +{ + return (!scop_contains_loop (scop, loop)) ? current_outer : + (loop->next != NULL) ? loop : + outer_most_loop_1 (scop, loop_outer (loop), loop); +} + +/* Return the outermost loop that contains the loop LOOP. */ + +static struct loop * +outer_most_loop (scop_p scop, struct loop *loop) +{ + return outer_most_loop_1 (scop, loop, NULL); +} + +/* Return the index of the outermost loop that contains the basic + block BB. */ + +static inline int +gbb_outer_most_loop_index (scop_p scop, graphite_bb_p gb) +{ + return scop_loop_index (scop, outer_most_loop (scop, gbb_loop (gb))); +} + +/* Return the loop depth of LOOP in SCOP. */ + +static inline unsigned int +scop_gimple_loop_depth (scop_p scop, loop_p loop) +{ + unsigned int depth = 0; + + loop = loop_outer (loop); + + while (scop_contains_loop (scop, loop)) + { + depth++; + loop = loop_outer (loop); + } + + return depth; +} + +/* Associate a POLYHEDRON dependence description to two data + references A and B. */ +struct data_dependence_polyhedron +{ + struct data_reference *a; + struct data_reference *b; + bool reversed_p; + bool loop_carried; /*TODO:konrad get rid of this, make level signed */ + signed level; + CloogDomain *polyhedron; +}; + +#define RDGE_DDP(E) ((struct data_dependence_polyhedron*) ((E)->data)) + +typedef struct data_dependence_polyhedron *ddp_p; + +DEF_VEC_P(ddp_p); +DEF_VEC_ALLOC_P(ddp_p,heap); + |