X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-data-ref.h;h=0588136cb8d452dba3af49b4080e1866195156f2;hb=3c22998f4c0674917268a089372ccff3cd67489f;hp=b24fd63095f37d6d37ded6f85f0b4dc1100753cb;hpb=801c5610886591ce60ea92d2073a0f8cf2caea31;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-data-ref.h b/gcc/tree-data-ref.h index b24fd63095f..0588136cb8d 100644 --- a/gcc/tree-data-ref.h +++ b/gcc/tree-data-ref.h @@ -1,5 +1,6 @@ -/* Data references and dependences detectors. - Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc. +/* Data references and dependences detectors. + Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 + Free Software Foundation, Inc. Contributed by Sebastian Pop This file is part of GCC. @@ -22,7 +23,6 @@ along with GCC; see the file COPYING3. If not see #define GCC_TREE_DATA_REF_H #include "graphds.h" -#include "lambda.h" #include "omega.h" #include "tree-chrec.h" @@ -31,14 +31,14 @@ along with GCC; see the file COPYING3. If not see 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 - + 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] *(p + x + 16B + 4B * j) - + innermost_loop_behavior base_address &a p @@ -78,7 +78,7 @@ struct indices { /* The object. */ tree base_object; - + /* A list of chrecs. Access functions of the indices. */ VEC(tree,heap) *access_fns; }; @@ -87,8 +87,6 @@ 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; - subvar_t subvars; struct ptr_info_def *ptr_info; /* The set of virtual operands corresponding to this memory reference, @@ -97,11 +95,87 @@ struct dr_alias bitmap vops; }; +/* An integer vector. A vector formally consists of an element of a vector + space. A vector space is a set that is closed under vector addition + and scalar multiplication. In this vector space, an element is a list of + integers. */ +typedef int *lambda_vector; +DEF_VEC_P(lambda_vector); +DEF_VEC_ALLOC_P(lambda_vector,heap); +DEF_VEC_ALLOC_P(lambda_vector,gc); + +/* An integer matrix. A matrix consists of m vectors of length n (IE + all vectors are the same length). */ +typedef lambda_vector *lambda_matrix; + +/* Each vector of the access matrix represents a linear access + function for a subscript. First elements correspond to the + leftmost indices, ie. for a[i][j] the first vector corresponds to + the subscript in "i". The elements of a vector are relative to + the loop nests in which the data reference is considered, + i.e. the vector is relative to the SCoP that provides the context + in which this data reference occurs. + + For example, in + + | loop_1 + | loop_2 + | a[i+3][2*j+n-1] + + if "i" varies in loop_1 and "j" varies in loop_2, the access + matrix with respect to the loop nest {loop_1, loop_2} is: + + | loop_1 loop_2 param_n cst + | 1 0 0 3 + | 0 2 1 -1 + + whereas the access matrix with respect to loop_2 considers "i" as + a parameter: + + | loop_2 param_i param_n cst + | 0 1 0 3 + | 2 0 1 -1 +*/ +struct access_matrix +{ + VEC (loop_p, heap) *loop_nest; + int nb_induction_vars; + VEC (tree, heap) *parameters; + VEC (lambda_vector, gc) *matrix; +}; + +#define AM_LOOP_NEST(M) (M)->loop_nest +#define AM_NB_INDUCTION_VARS(M) (M)->nb_induction_vars +#define AM_PARAMETERS(M) (M)->parameters +#define AM_MATRIX(M) (M)->matrix +#define AM_NB_PARAMETERS(M) (VEC_length (tree, AM_PARAMETERS(M))) +#define AM_CONST_COLUMN_INDEX(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M)) +#define AM_NB_COLUMNS(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M) + 1) +#define AM_GET_SUBSCRIPT_ACCESS_VECTOR(M, I) VEC_index (lambda_vector, AM_MATRIX (M), I) +#define AM_GET_ACCESS_MATRIX_ELEMENT(M, I, J) AM_GET_SUBSCRIPT_ACCESS_VECTOR (M, I)[J] + +/* Return the column in the access matrix of LOOP_NUM. */ + +static inline int +am_vector_index_for_loop (struct access_matrix *access_matrix, int loop_num) +{ + int i; + loop_p l; + + for (i = 0; VEC_iterate (loop_p, AM_LOOP_NEST (access_matrix), i, l); i++) + if (l->num == loop_num) + return i; + + gcc_unreachable(); +} + +int access_matrix_get_index_for_parameter (tree, struct access_matrix *); + struct data_reference { /* A pointer to the statement that contains this DR. */ - tree stmt; - + gimple stmt; + /* A pointer to the memory reference. */ tree ref; @@ -114,38 +188,40 @@ struct data_reference /* Behavior of the memory reference in the innermost loop. */ struct innermost_loop_behavior innermost; - /* Decomposition to indices for alias analysis. */ + /* Subscripts of this data reference. */ struct indices indices; /* Alias information for the data reference. */ struct dr_alias alias; -}; -typedef struct data_reference *data_reference_p; -DEF_VEC_P(data_reference_p); -DEF_VEC_ALLOC_P (data_reference_p, heap); + /* Matrix representation for the data access functions. */ + struct access_matrix *access_matrix; +}; #define DR_STMT(DR) (DR)->stmt #define DR_REF(DR) (DR)->ref #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_NUM_DIMENSIONS(DR) VEC_length (tree, DR_ACCESS_FNS (DR)) #define DR_IS_READ(DR) (DR)->is_read +#define DR_IS_WRITE(DR) (!DR_IS_READ (DR)) #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_SUBVARS(DR) (DR)->alias.subvars -#define DR_VOPS(DR) (DR)->alias.vops #define DR_ALIGNED_TO(DR) (DR)->innermost.aligned_to +#define DR_ACCESS_MATRIX(DR) (DR)->access_matrix + +typedef struct data_reference *data_reference_p; +DEF_VEC_P(data_reference_p); +DEF_VEC_ALLOC_P (data_reference_p, heap); enum data_dependence_direction { - dir_positive, - dir_negative, - dir_equal, + dir_positive, + dir_negative, + dir_equal, dir_positive_or_negative, dir_positive_or_equal, dir_negative_or_equal, @@ -189,11 +265,11 @@ struct subscript accessed twice. */ 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. */ tree last_conflict; - + /* Distance from the iteration that access a conflicting element in A to the iteration that access this same conflicting element in B. The distance is a tree scalar expression, i.e. a constant or a @@ -215,27 +291,23 @@ DEF_VEC_ALLOC_P (subscript_p, heap); struct data_dependence_relation { - + struct data_reference *a; struct data_reference *b; - /* When the dependence relation is affine, it can be represented by - a distance vector. */ - bool affine_p; - /* A "yes/no/maybe" field for the dependence relation: - + - when "ARE_DEPENDENT == NULL_TREE", there exist a dependence relation between A and B, and the description of this relation is given in the SUBSCRIPTS array, - + - when "ARE_DEPENDENT == chrec_known", there is no dependence and SUBSCRIPTS is empty, - + - when "ARE_DEPENDENT == chrec_dont_know", there may be a dependence, but the analyzer cannot be more specific. */ tree are_dependent; - + /* For each subscript in the dependence test, there is an element in this array. This is the attribute that labels the edge A->B of the data_dependence_relation. */ @@ -244,18 +316,26 @@ 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; + /* An index in loop_nest for the innermost loop that varies for + this data dependence relation. */ + unsigned inner_loop; + /* Is the dependence reversed with respect to the lexicographic order? */ bool reversed_p; + + /* When the dependence relation is affine, it can be represented by + a distance vector. */ + bool affine_p; + + /* Set to true when the dependence relation is on the same data + access. */ + bool self_reference_p; }; typedef struct data_dependence_relation *ddr_p; @@ -275,6 +355,7 @@ DEF_VEC_ALLOC_P(ddr_p,heap); 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) @@ -304,11 +385,17 @@ typedef struct data_ref_loc_d 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) **); -void dr_analyze_innermost (struct data_reference *); -extern void compute_data_dependences_for_loop (struct loop *, bool, +bool get_references_in_stmt (gimple, VEC (data_ref_loc, heap) **); +bool dr_analyze_innermost (struct data_reference *); +extern bool compute_data_dependences_for_loop (struct loop *, bool, + VEC (loop_p, heap) **, VEC (data_reference_p, heap) **, VEC (ddr_p, heap) **); +extern bool compute_data_dependences_for_bb (basic_block, bool, + VEC (data_reference_p, heap) **, + VEC (ddr_p, heap) **); +extern tree find_data_references_in_loop (struct loop *, + VEC (data_reference_p, heap) **); extern void print_direction_vector (FILE *, lambda_vector, int); extern void print_dir_vectors (FILE *, VEC (lambda_vector, heap) *, int); extern void print_dist_vectors (FILE *, VEC (lambda_vector, heap) *, int); @@ -316,22 +403,70 @@ extern void dump_subscript (FILE *, struct subscript *); extern void dump_ddrs (FILE *, VEC (ddr_p, heap) *); extern void dump_dist_dir_vectors (FILE *, VEC (ddr_p, heap) *); extern void dump_data_reference (FILE *, struct data_reference *); +extern void debug_data_reference (struct data_reference *); extern void dump_data_references (FILE *, VEC (data_reference_p, heap) *); +extern void debug_data_references (VEC (data_reference_p, heap) *); extern void debug_data_dependence_relation (struct data_dependence_relation *); -extern void dump_data_dependence_relation (FILE *, +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 *, +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) *); -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); +extern bool find_data_references_in_stmt (struct loop *, gimple, + VEC (data_reference_p, heap) **); +extern bool graphite_find_data_references_in_stmt (loop_p, loop_p, gimple, + VEC (data_reference_p, heap) **); +struct data_reference *create_data_ref (loop_p, loop_p, tree, gimple, bool); +extern bool find_loop_nest (struct loop *, VEC (loop_p, heap) **); +extern void compute_all_dependences (VEC (data_reference_p, heap) *, + VEC (ddr_p, heap) **, VEC (loop_p, heap) *, + bool); +extern tree find_data_references_in_bb (struct loop *, basic_block, + VEC (data_reference_p, heap) **); + +extern void create_rdg_vertices (struct graph *, VEC (gimple, heap) *); +extern bool dr_may_alias_p (const struct data_reference *, + const struct data_reference *); +extern bool dr_equal_offsets_p (struct data_reference *, + struct data_reference *); + + +/* Return true when the base objects of data references A and B are + the same memory object. */ + +static inline bool +same_data_refs_base_objects (data_reference_p a, data_reference_p b) +{ + return DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b) + && operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0); +} + +/* Return true when the data references A and B are accessing the same + memory object with the same access functions. */ + +static inline bool +same_data_refs (data_reference_p a, data_reference_p b) +{ + unsigned int i; + + /* The references are exactly the same. */ + if (operand_equal_p (DR_REF (a), DR_REF (b), 0)) + return true; + + if (!same_data_refs_base_objects (a, b)) + return false; + + for (i = 0; i < DR_NUM_DIMENSIONS (a); i++) + if (!eq_evolutions_p (DR_ACCESS_FN (a, i), DR_ACCESS_FN (b, i))) + return false; + + return true; +} /* Return true when the DDR contains two data references that have the same access functions. */ @@ -356,7 +491,7 @@ 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)) + && DR_IS_WRITE (DDR_B (ddr)) && !same_access_functions (ddr)); } @@ -375,6 +510,22 @@ ddrs_have_anti_deps (VEC (ddr_p, heap) *dependence_relations) return false; } +/* Returns the dependence level for a vector DIST of size LENGTH. + LEVEL = 0 means a lexicographic dependence, i.e. a dependence due + to the sequence of statements, not carried by any loop. */ + +static inline unsigned +dependence_level (lambda_vector dist_vect, int length) +{ + int i; + + for (i = 0; i < length; i++) + if (dist_vect[i] != 0) + return i + 1; + + return 0; +} + /* Return the dependence level for the DDR relation. */ static inline unsigned @@ -398,7 +549,7 @@ ddr_dependence_level (ddr_p ddr) typedef struct rdg_vertex { /* The statement represented by this vertex. */ - tree stmt; + gimple stmt; /* True when the statement contains a write to memory. */ bool has_mem_write; @@ -420,42 +571,50 @@ 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); +int rdg_vertex_for_stmt (struct graph *, gimple); /* Data dependence type. */ -enum rdg_dep_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', - + output_dd = 'o', + /* Read After Read (RAR). */ - input_dd = 'i' + input_dd = 'i' }; /* Dependence information attached to an edge of the RDG. */ -typedef struct rdg_edge +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. */ + /* Levels of the dependence: the depth of the loops that carry the + dependence. */ unsigned level; + + /* Dependence relation between data dependences, NULL when one of + the vertices is a scalar. */ + ddr_p relation; } *rdg_edge_p; #define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type #define RDGE_LEVEL(E) ((struct rdg_edge *) ((E)->data))->level +#define RDGE_RELATION(E) ((struct rdg_edge *) ((E)->data))->relation -struct graph *build_rdg (struct loop *); +struct graph *build_rdg (struct loop *, + VEC (loop_p, heap) **, + VEC (ddr_p, heap) **, + VEC (data_reference_p, heap) **); +struct graph *build_empty_rdg (int); void free_rdg (struct graph *); /* Return the index of the variable VAR in the LOOP_NEST array. */ @@ -474,10 +633,23 @@ 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) **); +void stores_from_loop (struct loop *, VEC (gimple, heap) **); +void stores_zero_from_loop (struct loop *, VEC (gimple, heap) **); +void remove_similar_memory_refs (VEC (gimple, heap) **); bool rdg_defs_used_in_other_loops_p (struct graph *, int); -bool have_similar_memory_accesses (tree, tree); +bool have_similar_memory_accesses (gimple, gimple); +bool stmt_with_adjacent_zero_store_dr_p (gimple); + +/* Returns true when STRIDE is equal in absolute value to the size of + the unit type of TYPE. */ + +static inline bool +stride_of_unit_type_p (tree stride, tree type) +{ + return tree_int_cst_equal (fold_unary (ABS_EXPR, TREE_TYPE (stride), + stride), + TYPE_SIZE_UNIT (type)); +} /* Determines whether RDG vertices V1 and V2 access to similar memory locations, in which case they have to be in the same partition. */ @@ -489,10 +661,103 @@ rdg_has_similar_memory_accesses (struct graph *rdg, int v1, int v2) 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 */ +/* In tree-data-ref.c */ void split_constant_offset (tree , tree *, tree *); +/* Strongly connected components of the reduced data dependence graph. */ + +typedef struct rdg_component +{ + int num; + VEC (int, heap) *vertices; +} *rdgc; + +DEF_VEC_P (rdgc); +DEF_VEC_ALLOC_P (rdgc, heap); + +DEF_VEC_P (bitmap); +DEF_VEC_ALLOC_P (bitmap, heap); + +/* Compute the greatest common divisor of a VECTOR of SIZE numbers. */ + +static inline int +lambda_vector_gcd (lambda_vector vector, int size) +{ + int i; + int gcd1 = 0; + + if (size > 0) + { + gcd1 = vector[0]; + for (i = 1; i < size; i++) + gcd1 = gcd (gcd1, vector[i]); + } + return gcd1; +} + +/* Allocate a new vector of given SIZE. */ + +static inline lambda_vector +lambda_vector_new (int size) +{ + return (lambda_vector) ggc_alloc_cleared_atomic (sizeof (int) * size); +} + +/* Clear out vector VEC1 of length SIZE. */ + +static inline void +lambda_vector_clear (lambda_vector vec1, int size) +{ + memset (vec1, 0, size * sizeof (*vec1)); +} + +/* Returns true when the vector V is lexicographically positive, in + other words, when the first nonzero element is positive. */ + +static inline bool +lambda_vector_lexico_pos (lambda_vector v, + unsigned n) +{ + unsigned i; + for (i = 0; i < n; i++) + { + if (v[i] == 0) + continue; + if (v[i] < 0) + return false; + if (v[i] > 0) + return true; + } + return true; +} + +/* Return true if vector VEC1 of length SIZE is the zero vector. */ + +static inline bool +lambda_vector_zerop (lambda_vector vec1, int size) +{ + int i; + for (i = 0; i < size; i++) + if (vec1[i] != 0) + return false; + return true; +} + +/* Allocate a matrix of M rows x N cols. */ + +static inline lambda_matrix +lambda_matrix_new (int m, int n, struct obstack *lambda_obstack) +{ + lambda_matrix mat; + int i; + + mat = (lambda_matrix) obstack_alloc (lambda_obstack, + sizeof (lambda_vector *) * m); + + for (i = 0; i < m; i++) + mat[i] = lambda_vector_new (n); + + return mat; +} + #endif /* GCC_TREE_DATA_REF_H */