X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fgraphite.h;h=1007e9af4109ac937b3b5c782682da3708d2d97d;hb=c011be898ad4e1d9462d344adde7f87df8d1486f;hp=a2700655ea44e52445e9723fb879cad386503c8e;hpb=cfaf579ddfaec5cb9bc5d220eadd212786138f3d;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/graphite.h b/gcc/graphite.h index a2700655ea4..1007e9af410 100644 --- a/gcc/graphite.h +++ b/gcc/graphite.h @@ -21,556 +21,4 @@ along with GCC; see the file COPYING3. If not see #ifndef GCC_GRAPHITE_H #define GCC_GRAPHITE_H -#include "tree-data-ref.h" - -int ref_nb_loops (data_reference_p); - -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); - -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; -} - -int nb_loops_around_gb (graphite_bb_p); - -/* 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 index of LOOP in the loop nest around GB. */ - -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 -{ - /* Single ENTRY and single EXIT from the SESE region. */ - edge entry, exit; - - /* 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; - - /* All the basic blocks in this scop that contain memory references - and that will be represented as statements in the polyhedral - representation. */ - VEC (graphite_bb_p, heap) *bbs; - - 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; - - /* 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; - - /* LIVEOUT_RENAMES registers the rename mapping that has to be - applied after code generation. */ - htab_t liveout_renames; -}; - -#define SCOP_BBS(S) S->bbs -#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); - -/* 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; - -typedef iv_stack_entry *iv_stack_entry_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) -{ - 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 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 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; -} - #endif /* GCC_GRAPHITE_H */