X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Ftree-data-ref.h;h=5e668cbaf4322fe5129ba8599a1db68b1c5be7ad;hp=2d23dce82075ae773e36b47cffcbf0ca1e6d07b1;hb=c127dd86af4a31150d186e0febf6992215184ce4;hpb=fa7637bd157d64d2520105c9dfb3932c13f067e8 diff --git a/gcc/tree-data-ref.h b/gcc/tree-data-ref.h index 2d23dce8207..5e668cbaf43 100644 --- a/gcc/tree-data-ref.h +++ b/gcc/tree-data-ref.h @@ -1,12 +1,12 @@ /* Data references and dependences detectors. - Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc. + Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc. Contributed by Sebastian Pop 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 2, or (at your option) any later +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 @@ -15,58 +15,85 @@ 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 COPYING. If not, write to the Free -Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA -02110-1301, USA. */ +along with GCC; see the file COPYING3. If not see +. */ #ifndef GCC_TREE_DATA_REF_H #define GCC_TREE_DATA_REF_H +#include "graphds.h" #include "lambda.h" +#include "omega.h" +#include "tree-chrec.h" /* - The first location accessed by data-ref in the loop is the address of data-ref's - base (BASE_ADDRESS) plus the initial offset from the base. We divide the initial offset - into two parts: loop invariant offset (OFFSET) and constant offset (INIT). - STEP is the stride of data-ref in the loop in bytes. + innermost_loop_behavior describes the evolution of the address of the memory + reference in the innermost enclosing loop. The address is expressed as + BASE + STEP * # of iteration, and base is further decomposed as the base + pointer (BASE_ADDRESS), loop invariant offset (OFFSET) and + constant offset (INIT). Examples, in loop nest + + for (i = 0; i < 100; i++) + for (j = 3; j < 100; j++) Example 1 Example 2 - data-ref a[j].b[i][j] a + x + 16B (a is int*) + data-ref a[j].b[i][j] *(p + x + 16B + 4B * j) - First location info: - base_address &a a - offset j_0*D_j + i_0*D_i x - init C_b + C_a 16 - step D_j 4 - access_fn NULL {16, +, 1} - Base object info: - base_object a NULL - access_fn NULL + innermost_loop_behavior + base_address &a p + offset i * D_i x + init 3 * D_j + offsetof (b) 28 + step D_j 4 */ -struct first_location_in_loop +struct innermost_loop_behavior { tree base_address; tree offset; tree init; tree step; - /* Access function related to first location in the loop. */ - VEC(tree,heap) *access_fns; + + /* Alignment information. ALIGNED_TO is set to the largest power of two + that divides OFFSET. */ + tree aligned_to; }; -struct base_object_info +/* Describes the evolutions of indices of the memory reference. The indices + are indices of the ARRAY_REFs and the operands of INDIRECT_REFs. + For ARRAY_REFs, BASE_OBJECT is the reference with zeroed indices + (note that this reference does not have to be valid, if zero does not + belong to the range of the array; hence it is not recommended to use + BASE_OBJECT in any code generation). For INDIRECT_REFs, the address is + set to the loop-invariant part of the address of the object, except for + the constant offset. For the examples above, + + base_object: a[0].b[0][0] *(p + x + 4B * j_0) + indices: {j_0, +, 1}_2 {16, +, 4}_2 + {i_0, +, 1}_1 + {j_0, +, 1}_2 +*/ + +struct indices { /* The object. */ tree base_object; - /* A list of chrecs. Access functions related to BASE_OBJECT. */ + /* A list of chrecs. Access functions of the indices. */ VEC(tree,heap) *access_fns; }; -enum data_ref_type { - ARRAY_REF_TYPE, - POINTER_REF_TYPE +struct dr_alias +{ + /* The alias information that should be used for new pointers to this + location. SYMBOL_TAG is either a DECL or a SYMBOL_MEMORY_TAG. */ + tree symbol_tag; + struct ptr_info_def *ptr_info; + + /* The set of virtual operands corresponding to this memory reference, + serving as a description of the alias information for the memory + reference. This could be eliminated if we had alias oracle. */ + bitmap vops; }; struct data_reference @@ -74,67 +101,23 @@ struct data_reference /* A pointer to the statement that contains this DR. */ tree stmt; - /* A pointer to the ARRAY_REF node. */ + /* A pointer to the memory reference. */ tree ref; /* Auxiliary info specific to a pass. */ - int aux; + void *aux; /* True when the data reference is in RHS of a stmt. */ bool is_read; - /* First location accessed by the data-ref in the loop. */ - struct first_location_in_loop first_location; + /* Behavior of the memory reference in the innermost loop. */ + struct innermost_loop_behavior innermost; - /* Base object related info. */ - struct base_object_info object_info; + /* Decomposition to indices for alias analysis. */ + struct indices indices; - /* Aliasing information. This field represents the symbol that - should be aliased by a pointer holding the address of this data - reference. If the original data reference was a pointer - dereference, then this field contains the memory tag that should - be used by the new vector-pointer. */ - tree memtag; - struct ptr_info_def *ptr_info; - subvar_t subvars; - - /* Alignment information. - MISALIGNMENT is the offset of the data-reference from its base in bytes. - ALIGNED_TO is the maximum data-ref's alignment. - - Example 1, - for i - for (j = 3; j < N; j++) - a[j].b[i][j] = 0; - - For a[j].b[i][j], the offset from base (calculated in get_inner_reference() - will be 'i * C_i + j * C_j + C'. - We try to substitute the variables of the offset expression - with initial_condition of the corresponding access_fn in the loop. - 'i' cannot be substituted, since its access_fn in the inner loop is i. 'j' - will be substituted with 3. - - Example 2 - for (j = 3; j < N; j++) - a[j].b[5][j] = 0; - - Here the offset expression (j * C_j + C) will not contain variables after - substitution of j=3 (3*C_j + C). - - Misalignment can be calculated only if all the variables can be - substituted with constants, otherwise, we record maximum possible alignment - in ALIGNED_TO. In Example 1, since 'i' cannot be substituted, - MISALIGNMENT will be NULL_TREE, and the biggest divider of C_i (a power of - 2) will be recorded in ALIGNED_TO. - - In Example 2, MISALIGNMENT will be the value of 3*C_j + C in bytes, and - ALIGNED_TO will be NULL_TREE. - */ - tree misalignment; - tree aligned_to; - - /* The type of the data-ref. */ - enum data_ref_type type; + /* Alias information for the data reference. */ + struct dr_alias alias; }; typedef struct data_reference *data_reference_p; @@ -143,41 +126,19 @@ DEF_VEC_ALLOC_P (data_reference_p, heap); #define DR_STMT(DR) (DR)->stmt #define DR_REF(DR) (DR)->ref -#define DR_BASE_OBJECT(DR) (DR)->object_info.base_object -#define DR_TYPE(DR) (DR)->type -#define DR_ACCESS_FNS(DR)\ - (DR_TYPE(DR) == ARRAY_REF_TYPE ? \ - (DR)->object_info.access_fns : (DR)->first_location.access_fns) +#define DR_BASE_OBJECT(DR) (DR)->indices.base_object +#define DR_ACCESS_FNS(DR) (DR)->indices.access_fns #define DR_ACCESS_FN(DR, I) VEC_index (tree, DR_ACCESS_FNS (DR), I) #define DR_NUM_DIMENSIONS(DR) VEC_length (tree, DR_ACCESS_FNS (DR)) #define DR_IS_READ(DR) (DR)->is_read -#define DR_BASE_ADDRESS(DR) (DR)->first_location.base_address -#define DR_OFFSET(DR) (DR)->first_location.offset -#define DR_INIT(DR) (DR)->first_location.init -#define DR_STEP(DR) (DR)->first_location.step -#define DR_MEMTAG(DR) (DR)->memtag -#define DR_ALIGNED_TO(DR) (DR)->aligned_to -#define DR_OFFSET_MISALIGNMENT(DR) (DR)->misalignment -#define DR_PTR_INFO(DR) (DR)->ptr_info -#define DR_SUBVARS(DR) (DR)->subvars - -#define DR_ACCESS_FNS_ADDR(DR) \ - (DR_TYPE(DR) == ARRAY_REF_TYPE ? \ - &((DR)->object_info.access_fns) : &((DR)->first_location.access_fns)) -#define DR_SET_ACCESS_FNS(DR, ACC_FNS) \ -{ \ - if (DR_TYPE(DR) == ARRAY_REF_TYPE) \ - (DR)->object_info.access_fns = ACC_FNS; \ - else \ - (DR)->first_location.access_fns = ACC_FNS; \ -} -#define DR_FREE_ACCESS_FNS(DR) \ -{ \ - if (DR_TYPE(DR) == ARRAY_REF_TYPE) \ - VEC_free (tree, heap, (DR)->object_info.access_fns); \ - else \ - VEC_free (tree, heap, (DR)->first_location.access_fns); \ -} +#define DR_BASE_ADDRESS(DR) (DR)->innermost.base_address +#define DR_OFFSET(DR) (DR)->innermost.offset +#define DR_INIT(DR) (DR)->innermost.init +#define DR_STEP(DR) (DR)->innermost.step +#define DR_SYMBOL_TAG(DR) (DR)->alias.symbol_tag +#define DR_PTR_INFO(DR) (DR)->alias.ptr_info +#define DR_VOPS(DR) (DR)->alias.vops +#define DR_ALIGNED_TO(DR) (DR)->innermost.aligned_to enum data_dependence_direction { dir_positive, @@ -190,6 +151,29 @@ enum data_dependence_direction { dir_independent }; +/* The description of the grid of iterations that overlap. At most + two loops are considered at the same time just now, hence at most + two functions are needed. For each of the functions, we store + the vector of coefficients, f[0] + x * f[1] + y * f[2] + ..., + where x, y, ... are variables. */ + +#define MAX_DIM 2 + +/* Special values of N. */ +#define NO_DEPENDENCE 0 +#define NOT_KNOWN (MAX_DIM + 1) +#define CF_NONTRIVIAL_P(CF) ((CF)->n != NO_DEPENDENCE && (CF)->n != NOT_KNOWN) +#define CF_NOT_KNOWN_P(CF) ((CF)->n == NOT_KNOWN) +#define CF_NO_DEPENDENCE_P(CF) ((CF)->n == NO_DEPENDENCE) + +typedef VEC (tree, heap) *affine_fn; + +typedef struct +{ + unsigned n; + affine_fn fns[MAX_DIM]; +} conflict_function; + /* What is a subscript? Given two array accesses a subscript is the tuple composed of the access functions for a given dimension. Example: Given A[f1][f2][f3] and B[g1][g2][g3], there are three @@ -201,8 +185,8 @@ struct subscript { /* A description of the iterations for which the elements are accessed twice. */ - tree conflicting_iterations_in_a; - tree conflicting_iterations_in_b; + conflict_function *conflicting_iterations_in_a; + conflict_function *conflicting_iterations_in_b; /* This field stores the information about the iteration domain validity of the dependence relation. */ @@ -224,10 +208,6 @@ DEF_VEC_ALLOC_P (subscript_p, heap); #define SUB_LAST_CONFLICT(SUB) SUB->last_conflict #define SUB_DISTANCE(SUB) SUB->distance -typedef struct loop *loop_p; -DEF_VEC_P(loop_p); -DEF_VEC_ALLOC_P (loop_p, heap); - /* A data_dependence_relation represents a relation between two data_references A and B. */ @@ -241,6 +221,10 @@ struct data_dependence_relation a distance vector. */ bool affine_p; + /* Set to true when the dependence relation is on the same data + access. */ + bool self_reference_p; + /* A "yes/no/maybe" field for the dependence relation: - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence @@ -262,11 +246,18 @@ struct data_dependence_relation /* The analyzed loop nest. */ VEC (loop_p, heap) *loop_nest; + /* An index in loop_nest for the innermost loop that varies for + this data dependence relation. */ + unsigned inner_loop; + /* The classic direction vector. */ VEC (lambda_vector, heap) *dir_vects; /* The classic distance vector. */ VEC (lambda_vector, heap) *dist_vects; + + /* Is the dependence reversed with respect to the lexicographic order? */ + bool reversed_p; }; typedef struct data_dependence_relation *ddr_p; @@ -285,6 +276,8 @@ DEF_VEC_ALLOC_P(ddr_p,heap); /* The size of the direction/distance vectors: the number of loops in the loop nest. */ #define DDR_NB_LOOPS(DDR) (VEC_length (loop_p, DDR_LOOP_NEST (DDR))) +#define DDR_INNER_LOOP(DDR) DDR->inner_loop +#define DDR_SELF_REFERENCE(DDR) DDR->self_reference_p #define DDR_DIST_VECTS(DDR) ((DDR)->dist_vects) #define DDR_DIR_VECTS(DDR) ((DDR)->dir_vects) @@ -296,6 +289,7 @@ DEF_VEC_ALLOC_P(ddr_p,heap); VEC_index (lambda_vector, DDR_DIR_VECTS (DDR), I) #define DDR_DIST_VECT(DDR, I) \ VEC_index (lambda_vector, DDR_DIST_VECTS (DDR), I) +#define DDR_REVERSED_P(DDR) DDR->reversed_p @@ -314,8 +308,7 @@ DEF_VEC_O (data_ref_loc); DEF_VEC_ALLOC_O (data_ref_loc, heap); bool get_references_in_stmt (tree, VEC (data_ref_loc, heap) **); -extern tree find_data_references_in_loop (struct loop *, - VEC (data_reference_p, heap) **); +void dr_analyze_innermost (struct data_reference *); extern void compute_data_dependences_for_loop (struct loop *, bool, VEC (data_reference_p, heap) **, VEC (ddr_p, heap) **); @@ -331,13 +324,142 @@ extern void debug_data_dependence_relation (struct data_dependence_relation *); extern void dump_data_dependence_relation (FILE *, struct data_dependence_relation *); extern void dump_data_dependence_relations (FILE *, VEC (ddr_p, heap) *); +extern void debug_data_dependence_relations (VEC (ddr_p, heap) *); extern void dump_data_dependence_direction (FILE *, enum data_dependence_direction); extern void free_dependence_relation (struct data_dependence_relation *); extern void free_dependence_relations (VEC (ddr_p, heap) *); +extern void free_data_ref (data_reference_p); extern void free_data_refs (VEC (data_reference_p, heap) *); -extern struct data_reference *analyze_array (tree, tree, bool); +struct data_reference *create_data_ref (struct loop *, tree, tree, bool); +bool find_loop_nest (struct loop *, VEC (loop_p, heap) **); +void compute_all_dependences (VEC (data_reference_p, heap) *, + VEC (ddr_p, heap) **, VEC (loop_p, heap) *, bool); + +/* Return true when the DDR contains two data references that have the + same access functions. */ + +static inline bool +same_access_functions (const struct data_dependence_relation *ddr) +{ + unsigned i; + + for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++) + if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i), + DR_ACCESS_FN (DDR_B (ddr), i))) + return false; + + return true; +} + +/* Return true when DDR is an anti-dependence relation. */ + +static inline bool +ddr_is_anti_dependent (ddr_p ddr) +{ + return (DDR_ARE_DEPENDENT (ddr) == NULL_TREE + && DR_IS_READ (DDR_A (ddr)) + && !DR_IS_READ (DDR_B (ddr)) + && !same_access_functions (ddr)); +} + +/* Return true when DEPENDENCE_RELATIONS contains an anti-dependence. */ + +static inline bool +ddrs_have_anti_deps (VEC (ddr_p, heap) *dependence_relations) +{ + unsigned i; + ddr_p ddr; + + for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++) + if (ddr_is_anti_dependent (ddr)) + return true; + + return false; +} + +/* Return the dependence level for the DDR relation. */ + +static inline unsigned +ddr_dependence_level (ddr_p ddr) +{ + unsigned vector; + unsigned level = 0; + + if (DDR_DIST_VECTS (ddr)) + level = dependence_level (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr)); + + for (vector = 1; vector < DDR_NUM_DIST_VECTS (ddr); vector++) + level = MIN (level, dependence_level (DDR_DIST_VECT (ddr, vector), + DDR_NB_LOOPS (ddr))); + return level; +} + + + +/* A Reduced Dependence Graph (RDG) vertex representing a statement. */ +typedef struct rdg_vertex +{ + /* The statement represented by this vertex. */ + tree stmt; + + /* True when the statement contains a write to memory. */ + bool has_mem_write; + + /* True when the statement contains a read from memory. */ + bool has_mem_reads; +} *rdg_vertex_p; + +#define RDGV_STMT(V) ((struct rdg_vertex *) ((V)->data))->stmt +#define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write +#define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads +#define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I])) +#define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I])) +#define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I])) + +void dump_rdg_vertex (FILE *, struct graph *, int); +void debug_rdg_vertex (struct graph *, int); +void dump_rdg_component (FILE *, struct graph *, int, bitmap); +void debug_rdg_component (struct graph *, int); +void dump_rdg (FILE *, struct graph *); +void debug_rdg (struct graph *); +void dot_rdg (struct graph *); +int rdg_vertex_for_stmt (struct graph *, tree); +/* Data dependence type. */ + +enum rdg_dep_type +{ + /* Read After Write (RAW). */ + flow_dd = 'f', + + /* Write After Read (WAR). */ + anti_dd = 'a', + + /* Write After Write (WAW). */ + output_dd = 'o', + + /* Read After Read (RAR). */ + input_dd = 'i' +}; + +/* Dependence information attached to an edge of the RDG. */ + +typedef struct rdg_edge +{ + /* Type of the dependence. */ + enum rdg_dep_type type; + + /* Levels of the dependence: the depth of the loops that + carry the dependence. */ + unsigned level; +} *rdg_edge_p; + +#define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type +#define RDGE_LEVEL(E) ((struct rdg_edge *) ((E)->data))->level + +struct graph *build_rdg (struct loop *); +void free_rdg (struct graph *); /* Return the index of the variable VAR in the LOOP_NEST array. */ @@ -355,7 +477,25 @@ index_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest) return var_index; } +void stores_from_loop (struct loop *, VEC (tree, heap) **); +void remove_similar_memory_refs (VEC (tree, heap) **); +bool rdg_defs_used_in_other_loops_p (struct graph *, int); +bool have_similar_memory_accesses (tree, tree); + +/* Determines whether RDG vertices V1 and V2 access to similar memory + locations, in which case they have to be in the same partition. */ + +static inline bool +rdg_has_similar_memory_accesses (struct graph *rdg, int v1, int v2) +{ + return have_similar_memory_accesses (RDG_STMT (rdg, v1), + RDG_STMT (rdg, v2)); +} + /* In lambda-code.c */ bool lambda_transform_legal_p (lambda_trans_matrix, int, VEC (ddr_p, heap) *); +/* In tree-data-refs.c */ +void split_constant_offset (tree , tree *, tree *); + #endif /* GCC_TREE_DATA_REF_H */