X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-data-ref.h;h=0f12962fc93ca6f5cab901289655cb7794ccd804;hb=40879ac688ceebe14852be576c3c2e140795a971;hp=dfce23309f57451bd634224b3cebe028fd16a756;hpb=37545e54d978946dc4941bf46ab1b6ee6ff0f082;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-data-ref.h b/gcc/tree-data-ref.h index dfce23309f5..0f12962fc93 100644 --- a/gcc/tree-data-ref.h +++ b/gcc/tree-data-ref.h @@ -1,5 +1,5 @@ -/* Data references and dependences detectors. - Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 +/* Data references and dependences detectors. + Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc. Contributed by Sebastian Pop @@ -23,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" @@ -32,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 @@ -79,7 +78,7 @@ struct indices { /* The object. */ tree base_object; - + /* A list of chrecs. Access functions of the indices. */ VEC(tree,heap) *access_fns; }; @@ -96,7 +95,18 @@ struct dr_alias bitmap vops; }; -typedef struct scop *scop_p; +/* 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 @@ -112,7 +122,7 @@ typedef struct scop *scop_p; | loop_2 | a[i+3][2*j+n-1] - if "i" varies in loop_1 and "j" varies in loop_2, the access + 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 @@ -165,7 +175,7 @@ struct data_reference { /* A pointer to the statement that contains this DR. */ gimple stmt; - + /* A pointer to the memory reference. */ tree ref; @@ -184,21 +194,18 @@ struct data_reference /* Alias information for the data reference. */ struct dr_alias alias; - /* The SCoP in which the data reference was analyzed. */ - scop_p scop; - /* Matrix representation for the data access functions. */ struct access_matrix *access_matrix; }; -#define DR_SCOP(DR) (DR)->scop #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 @@ -212,9 +219,9 @@ 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, @@ -258,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 @@ -284,23 +291,23 @@ DEF_VEC_ALLOC_P (subscript_p, heap); struct data_dependence_relation { - + struct data_reference *a; struct data_reference *b; /* 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. */ @@ -379,14 +386,15 @@ DEF_VEC_O (data_ref_loc); DEF_VEC_ALLOC_O (data_ref_loc, heap); bool get_references_in_stmt (gimple, VEC (data_ref_loc, heap) **); -bool dr_analyze_innermost (struct data_reference *); +bool dr_analyze_innermost (struct data_reference *, struct loop *); 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 *, +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); @@ -395,13 +403,15 @@ 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) *); @@ -409,16 +419,57 @@ extern void free_data_ref (data_reference_p); extern void free_data_refs (VEC (data_reference_p, heap) *); extern bool find_data_references_in_stmt (struct loop *, gimple, VEC (data_reference_p, heap) **); -struct data_reference *create_data_ref (struct loop *, tree, gimple, bool); +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 struct data_dependence_relation *initialize_data_dependence_relation + (struct data_reference *, struct data_reference *, VEC (loop_p, heap) *); +extern void compute_self_dependence (struct data_dependence_relation *); 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 stmt_simple_memref_p (struct loop *, gimple, tree); + const struct data_reference *, bool); +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. */ @@ -443,7 +494,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)); } @@ -462,6 +513,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 @@ -507,29 +574,28 @@ 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 *, 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; @@ -547,7 +613,10 @@ typedef struct rdg_edge #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 *); @@ -568,9 +637,22 @@ index_in_loop_nest (int var, VEC (loop_p, heap) *loop_nest) } 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 (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. */ @@ -582,14 +664,6 @@ 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) *); -void lambda_collect_parameters (VEC (data_reference_p, heap) *, - VEC (tree, heap) **); -bool lambda_compute_access_matrices (VEC (data_reference_p, heap) *, - VEC (tree, heap) *, VEC (loop_p, heap) *); - /* In tree-data-ref.c */ void split_constant_offset (tree , tree *, tree *); @@ -607,4 +681,86 @@ 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 */