diff options
| -rw-r--r-- | gcc/ChangeLog | 24 | ||||
| -rw-r--r-- | gcc/Makefile.in | 2 | ||||
| -rw-r--r-- | gcc/lambda-code.c | 196 | ||||
| -rw-r--r-- | gcc/lambda.h | 6 | ||||
| -rw-r--r-- | gcc/tree-chrec.h | 6 | ||||
| -rw-r--r-- | gcc/tree-data-ref.c | 28 | ||||
| -rw-r--r-- | gcc/tree-data-ref.h | 78 | ||||
| -rw-r--r-- | gcc/tree-loop-linear.c | 23 |
8 files changed, 341 insertions, 22 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 9a3e9bb..ba15ab5 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,27 @@ +2008-05-20 Jan Sjodin <jan.sjodin@amd.com> + Sebastian Pop <sebastian.pop@amd.com> + + * tree-loop-linear.c (gather_interchange_stats): Look in the access matrix, + and never look at the tree representation of the memory accesses. + (linear_transform_loops): Computes parameters and access matrices. + * tree-data-ref.c (compute_data_dependences_for_loop): Returns false when fails. + (access_matrix_get_index_for_parameter): New. + * tree-data-ref.h (struct access_matrix): New. + (AM_LOOP_NEST_NUM, AM_NB_INDUCTION_VARS, AM_PARAMETERS, AM_MATRIX, + AM_NB_PARAMETERS, AM_CONST_COLUMN_INDEX, AM_NB_COLUMNS, + AM_GET_SUBSCRIPT_ACCESS_VECTOR, AM_GET_ACCESS_MATRIX_ELEMENT, + am_vector_index_for_loop): New. + (struct data_reference): Add field access_matrix. + (DR_ACCESS_MATRIX): New. + (compute_data_dependences_for_loop): Update declaration. + (lambda_collect_parameters, lambda_compute_access_matrices): Declared. + * lambda.h (lambda_vector_vec_p): Declared. + * lambda-code.c: Depend on pointer-set.h. + (lambda_collect_parameters_from_af, lambda_collect_parameters, + av_for_af_base, av_for_af, build_access_matrix, + lambda_compute_access_matrices): New. + * Makefile.in (lambda-code.o): Depend on pointer-set.h. + 2008-05-20 Joseph Myers <joseph@codesourcery.com> * doc/install.texi2html: Generate gcc-vers.texi in $DESTDIR not diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 56d2aed..0d88228 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -2885,7 +2885,7 @@ lambda-code.o: lambda-code.c $(LAMBDA_H) $(GGC_H) $(SYSTEM_H) $(CONFIG_H) \ $(TM_H) $(OPTABS_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) \ $(DIAGNOSTIC_H) $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) \ $(TREE_DATA_REF_H) $(SCEV_H) $(EXPR_H) coretypes.h $(TARGET_H) \ - tree-chrec.h tree-pass.h vec.h vecprim.h $(OBSTACK_H) + tree-chrec.h tree-pass.h vec.h vecprim.h $(OBSTACK_H) pointer-set.h params.o : params.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(PARAMS_H) toplev.h pointer-set.o: pointer-set.c pointer-set.h $(CONFIG_H) $(SYSTEM_H) hooks.o: hooks.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(HOOKS_H) diff --git a/gcc/lambda-code.c b/gcc/lambda-code.c index dc656d3..7075911 100644 --- a/gcc/lambda-code.c +++ b/gcc/lambda-code.c @@ -42,6 +42,7 @@ #include "vec.h" #include "lambda.h" #include "vecprim.h" +#include "pointer-set.h" /* This loop nest code generation is based on non-singular matrix math. @@ -2641,3 +2642,198 @@ lambda_transform_legal_p (lambda_trans_matrix trans, } return true; } + + +/* Collects parameters from affine function ACCESS_FUNCTION, and push + them in PARAMETERS. */ + +static void +lambda_collect_parameters_from_af (tree access_function, + struct pointer_set_t *param_set, + VEC (tree, heap) **parameters) +{ + if (access_function == NULL) + return; + + if (TREE_CODE (access_function) == SSA_NAME + && pointer_set_contains (param_set, access_function) == 0) + { + pointer_set_insert (param_set, access_function); + VEC_safe_push (tree, heap, *parameters, access_function); + } + else + { + int i, num_operands = tree_operand_length (access_function); + + for (i = 0; i < num_operands; i++) + lambda_collect_parameters_from_af (TREE_OPERAND (access_function, i), + param_set, parameters); + } +} + +/* Collects parameters from DATAREFS, and push them in PARAMETERS. */ + +void +lambda_collect_parameters (VEC (data_reference_p, heap) *datarefs, + VEC (tree, heap) **parameters) +{ + unsigned i, j; + struct pointer_set_t *parameter_set = pointer_set_create (); + data_reference_p data_reference; + + for (i = 0; VEC_iterate (data_reference_p, datarefs, i, data_reference); i++) + for (j = 0; j < DR_NUM_DIMENSIONS (data_reference); j++) + lambda_collect_parameters_from_af (DR_ACCESS_FN (data_reference, j), + parameter_set, parameters); +} + +/* Translates BASE_EXPR to vector CY. AM is needed for inferring + indexing positions in the data access vector. CST is the analyzed + integer constant. */ + +static bool +av_for_af_base (tree base_expr, lambda_vector cy, struct access_matrix *am, + int cst) +{ + bool result = true; + + switch (TREE_CODE (base_expr)) + { + case INTEGER_CST: + /* Constant part. */ + cy[AM_CONST_COLUMN_INDEX (am)] += int_cst_value (base_expr) * cst; + return true; + + case SSA_NAME: + { + int param_index = + access_matrix_get_index_for_parameter (base_expr, am); + + if (param_index >= 0) + { + cy[param_index] = cst + cy[param_index]; + return true; + } + + return false; + } + + case PLUS_EXPR: + return av_for_af_base (TREE_OPERAND (base_expr, 0), cy, am, cst) + && av_for_af_base (TREE_OPERAND (base_expr, 1), cy, am, cst); + + case MINUS_EXPR: + return av_for_af_base (TREE_OPERAND (base_expr, 0), cy, am, cst) + && av_for_af_base (TREE_OPERAND (base_expr, 1), cy, am, -1 * cst); + + case MULT_EXPR: + if (TREE_CODE (TREE_OPERAND (base_expr, 0)) == INTEGER_CST) + result = av_for_af_base (TREE_OPERAND (base_expr, 1), + cy, am, cst * + int_cst_value (TREE_OPERAND (base_expr, 0))); + else if (TREE_CODE (TREE_OPERAND (base_expr, 1)) == INTEGER_CST) + result = av_for_af_base (TREE_OPERAND (base_expr, 0), + cy, am, cst * + int_cst_value (TREE_OPERAND (base_expr, 1))); + else + result = false; + + return result; + + case NEGATE_EXPR: + return av_for_af_base (TREE_OPERAND (base_expr, 0), cy, am, -1 * cst); + + default: + return false; + } + + return result; +} + +/* Translates ACCESS_FUN to vector CY. AM is needed for inferring + indexing positions in the data access vector. */ + +static bool +av_for_af (tree access_fun, lambda_vector cy, struct access_matrix *am) +{ + switch (TREE_CODE (access_fun)) + { + case POLYNOMIAL_CHREC: + { + tree left = CHREC_LEFT (access_fun); + tree right = CHREC_RIGHT (access_fun); + unsigned var; + + if (TREE_CODE (right) != INTEGER_CST) + return false; + + var = am_vector_index_for_loop (am, CHREC_VARIABLE (access_fun)); + cy[var] = int_cst_value (right); + + if (TREE_CODE (left) == POLYNOMIAL_CHREC) + return av_for_af (left, cy, am); + else + return av_for_af_base (left, cy, am, 1); + } + + case INTEGER_CST: + /* Constant part. */ + return av_for_af_base (access_fun, cy, am, 1); + + default: + return false; + } +} + +/* Initializes the access matrix for DATA_REFERENCE. */ + +static bool +build_access_matrix (data_reference_p data_reference, + VEC (tree, heap) *parameters, int loop_nest_num) +{ + struct access_matrix *am = GGC_NEW (struct access_matrix); + unsigned i, ndim = DR_NUM_DIMENSIONS (data_reference); + struct loop *loop = bb_for_stmt (DR_STMT (data_reference))->loop_father; + unsigned nb_induction_vars = loop_depth (loop) - loop_nest_num + 1; + unsigned lambda_nb_columns; + lambda_vector_vec_p matrix; + + AM_LOOP_NEST_NUM (am) = loop_nest_num; + AM_NB_INDUCTION_VARS (am) = nb_induction_vars; + AM_PARAMETERS (am) = parameters; + + lambda_nb_columns = AM_NB_COLUMNS (am); + matrix = VEC_alloc (lambda_vector, heap, lambda_nb_columns); + AM_MATRIX (am) = matrix; + + for (i = 0; i < ndim; i++) + { + lambda_vector access_vector = lambda_vector_new (lambda_nb_columns); + tree access_function = DR_ACCESS_FN (data_reference, i); + + if (!av_for_af (access_function, access_vector, am)) + return false; + + VEC_safe_push (lambda_vector, heap, matrix, access_vector); + } + + DR_ACCESS_MATRIX (data_reference) = am; + return true; +} + +/* Returns false when one of the access matrices cannot be built. */ + +bool +lambda_compute_access_matrices (VEC (data_reference_p, heap) *datarefs, + VEC (tree, heap) *parameters, + int loop_nest_num) +{ + data_reference_p dataref; + unsigned ix; + + for (ix = 0; VEC_iterate (data_reference_p, datarefs, ix, dataref); ix++) + if (!build_access_matrix (dataref, parameters, loop_nest_num)) + return false; + + return true; +} diff --git a/gcc/lambda.h b/gcc/lambda.h index 641b3bc..40e8502 100644 --- a/gcc/lambda.h +++ b/gcc/lambda.h @@ -28,10 +28,13 @@ along with GCC; see the file COPYING3. If not see 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); +typedef VEC(lambda_vector, heap) *lambda_vector_vec_p; +DEF_VEC_P (lambda_vector_vec_p); +DEF_VEC_ALLOC_P (lambda_vector_vec_p, heap); + /* An integer matrix. A matrix consists of m vectors of length n (IE all vectors are the same length). */ typedef lambda_vector *lambda_matrix; @@ -487,4 +490,3 @@ dependence_level (lambda_vector dist_vect, int length) } #endif /* LAMBDA_H */ - diff --git a/gcc/tree-chrec.h b/gcc/tree-chrec.h index a924692..7f240c6 100644 --- a/gcc/tree-chrec.h +++ b/gcc/tree-chrec.h @@ -201,8 +201,10 @@ evolution_function_is_affine_p (const_tree chrec) switch (TREE_CODE (chrec)) { case POLYNOMIAL_CHREC: - if (evolution_function_is_invariant_p (CHREC_LEFT (chrec), CHREC_VARIABLE (chrec)) - && evolution_function_is_invariant_p (CHREC_RIGHT (chrec), CHREC_VARIABLE (chrec))) + if (evolution_function_is_invariant_p (CHREC_LEFT (chrec), + CHREC_VARIABLE (chrec)) + && evolution_function_is_invariant_p (CHREC_RIGHT (chrec), + CHREC_VARIABLE (chrec))) return true; else return false; diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c index 7554549..bf9516c 100644 --- a/gcc/tree-data-ref.c +++ b/gcc/tree-data-ref.c @@ -4180,18 +4180,20 @@ find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest) return true; } -/* Given a loop nest LOOP, the following vectors are returned: +/* Returns true when the data dependences have been computed, false otherwise. + Given a loop nest LOOP, the following vectors are returned: DATAREFS is initialized to all the array elements contained in this loop, DEPENDENCE_RELATIONS contains the relations between the data references. Compute read-read and self relations if COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE. */ -void +bool compute_data_dependences_for_loop (struct loop *loop, bool compute_self_and_read_read_dependences, VEC (data_reference_p, heap) **datarefs, VEC (ddr_p, heap) **dependence_relations) { + bool res = true; VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3); memset (&dependence_stats, 0, sizeof (dependence_stats)); @@ -4209,6 +4211,7 @@ compute_data_dependences_for_loop (struct loop *loop, chrec_dont_know. */ ddr = initialize_data_dependence_relation (NULL, NULL, vloops); VEC_safe_push (ddr_p, heap, *dependence_relations, ddr); + res = false; } else compute_all_dependences (*datarefs, dependence_relations, vloops, @@ -4260,7 +4263,9 @@ compute_data_dependences_for_loop (struct loop *loop, dependence_stats.num_miv_independent); fprintf (dump_file, "Number of miv tests unimplemented: %d\n", dependence_stats.num_miv_unimplemented); - } + } + + return res; } /* Entry point (for testing only). Analyze all the data references @@ -5032,3 +5037,20 @@ remove_similar_memory_refs (VEC (tree, heap) **stmts) htab_delete (seen); } +/* Returns the index of PARAMETER in the parameters vector of the + ACCESS_MATRIX. If PARAMETER does not exist return -1. */ + +int +access_matrix_get_index_for_parameter (tree parameter, + struct access_matrix *access_matrix) +{ + int i; + VEC (tree,heap) *lambda_parameters = AM_PARAMETERS (access_matrix); + tree lambda_parameter; + + for (i = 0; VEC_iterate (tree, lambda_parameters, i, lambda_parameter); i++) + if (lambda_parameter == parameter) + return i + AM_NB_INDUCTION_VARS (access_matrix); + + return -1; +} diff --git a/gcc/tree-data-ref.h b/gcc/tree-data-ref.h index 5e668cb..c1672eb 100644 --- a/gcc/tree-data-ref.h +++ b/gcc/tree-data-ref.h @@ -96,6 +96,63 @@ struct dr_alias bitmap vops; }; +/* 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 +{ + int loop_nest_num; + int nb_induction_vars; + VEC (tree, heap) *parameters; + VEC (lambda_vector, heap) *matrix; +}; + +#define AM_LOOP_NEST_NUM(M) (M)->loop_nest_num +#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) +{ + gcc_assert (loop_num >= AM_LOOP_NEST_NUM (access_matrix)); + return loop_num - AM_LOOP_NEST_NUM (access_matrix); +} + +int access_matrix_get_index_for_parameter (tree, struct access_matrix *); + struct data_reference { /* A pointer to the statement that contains this DR. */ @@ -118,11 +175,10 @@ struct data_reference /* 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 @@ -139,6 +195,11 @@ DEF_VEC_ALLOC_P (data_reference_p, heap); #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 +#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, @@ -309,7 +370,7 @@ 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, +extern bool compute_data_dependences_for_loop (struct loop *, bool, VEC (data_reference_p, heap) **, VEC (ddr_p, heap) **); extern void print_direction_vector (FILE *, lambda_vector, int); @@ -493,7 +554,12 @@ rdg_has_similar_memory_accesses (struct graph *rdg, int v1, int v2) } /* In lambda-code.c */ -bool lambda_transform_legal_p (lambda_trans_matrix, int, VEC (ddr_p, heap) *); +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) *, int); /* In tree-data-refs.c */ void split_constant_offset (tree , tree *, tree *); diff --git a/gcc/tree-loop-linear.c b/gcc/tree-loop-linear.c index 806d9e6..f58bd11 100644 --- a/gcc/tree-loop-linear.c +++ b/gcc/tree-loop-linear.c @@ -146,19 +146,17 @@ gather_interchange_stats (VEC (ddr_p, heap) *dependence_relations, for (it = 0; it < DR_NUM_DIMENSIONS (dr); it++, ref = TREE_OPERAND (ref, 0)) { - tree chrec = DR_ACCESS_FN (dr, it); - tree tstride = evolution_part_in_loop_num (chrec, loop->num); + int num = am_vector_index_for_loop (DR_ACCESS_MATRIX (dr), loop->num); + int istride = AM_GET_ACCESS_MATRIX_ELEMENT (DR_ACCESS_MATRIX (dr), it, num); tree array_size = TYPE_SIZE (TREE_TYPE (ref)); double_int dstride; - if (tstride == NULL_TREE - || array_size == NULL_TREE - || TREE_CODE (tstride) != INTEGER_CST + if (array_size == NULL_TREE || TREE_CODE (array_size) != INTEGER_CST) continue; dstride = double_int_mul (tree_to_double_int (array_size), - tree_to_double_int (tstride)); + shwi_to_double_int (istride)); (*access_strides) = double_int_add (*access_strides, dstride); } } @@ -320,6 +318,7 @@ linear_transform_loops (void) loop_iterator li; VEC(tree,heap) *oldivs = NULL; VEC(tree,heap) *invariants = NULL; + VEC(tree,heap) *lambda_parameters = NULL; VEC(tree,heap) *remove_ivs = VEC_alloc (tree, heap, 3); struct loop *loop_nest; tree oldiv_stmt; @@ -330,6 +329,7 @@ linear_transform_loops (void) unsigned int depth = 0; VEC (ddr_p, heap) *dependence_relations; VEC (data_reference_p, heap) *datarefs; + lambda_loopnest before, after; lambda_trans_matrix trans; struct obstack lambda_obstack; @@ -341,11 +341,18 @@ linear_transform_loops (void) VEC_truncate (tree, oldivs, 0); VEC_truncate (tree, invariants, 0); + VEC_truncate (tree, lambda_parameters, 0); datarefs = VEC_alloc (data_reference_p, heap, 10); dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10); - compute_data_dependences_for_loop (loop_nest, true, &datarefs, - &dependence_relations); + if (!compute_data_dependences_for_loop (loop_nest, true, &datarefs, + &dependence_relations)) + continue; + + lambda_collect_parameters (datarefs, &lambda_parameters); + if (!lambda_compute_access_matrices (datarefs, lambda_parameters, + loop_nest->num)) + continue; if (dump_file && (dump_flags & TDF_DETAILS)) dump_ddrs (dump_file, dependence_relations); |