From 1de6a873129a16012941fb75d8c2a1bbde736690 Mon Sep 17 00:00:00 2001 From: Ira Rosen Date: Wed, 29 Dec 2004 13:16:07 +0000 Subject: [PATCH] re PR tree-optimization/18179 (vectorizer: wrong alignment/step/initial-address computed for struct accesses) 2004-12-29 Ira Rosen PR tree-optimization/18179 * tree-vectorizer.h (struct _stmt_vec_info): Add new fields: initial_offset, step, misalignment and base_aligned_p and macros to access them. * tree-vectorizer.c (vect_analyze_offset_expr): New function. (new_stmt_vec_info): Initialize the new fields of stmt_vec_info. (vect_create_data_ref_ptr): Fix printings. From-SVN: r92701 --- gcc/ChangeLog | 13 ++- gcc/tree-vectorizer.c | 197 +++++++++++++++++++++++++++++++++++++++++- gcc/tree-vectorizer.h | 54 ++++++++---- 3 files changed, 242 insertions(+), 22 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 984db9a97c05..df492c52e544 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,6 +1,17 @@ 2004-12-29 Ira Rosen - PR tree-optimization/18179 + PR tree-optimization/18179 + * tree-vectorizer.h (struct _stmt_vec_info): Add new fields: + initial_offset, step, misalignment and base_aligned_p and macros + to access them. + * tree-vectorizer.c (vect_analyze_offset_expr): New function. + (new_stmt_vec_info): Initialize the new fields of stmt_vec_info. + + (vect_create_data_ref_ptr): Fix printings. + +2004-12-29 Ira Rosen + + PR tree-optimization/18179 * tree-vectorizer.c (vect_get_symbl_and_dr): Reorganize. Add memtag retrieval. (vect_analyze_data_refs): Remove memtag retrieval. diff --git a/gcc/tree-vectorizer.c b/gcc/tree-vectorizer.c index ab9acf7e6de5..70af3e48fba5 100644 --- a/gcc/tree-vectorizer.c +++ b/gcc/tree-vectorizer.c @@ -232,6 +232,8 @@ static tree vect_compute_array_ref_alignment static tree vect_get_ptr_offset (tree, tree, tree *); static tree vect_get_symbl_and_dr (tree, tree, bool, loop_vec_info, struct data_reference **); +static bool vect_analyze_offset_expr (tree, struct loop *, tree, tree *, + tree *, tree *); /* Utility functions for the code transformation. */ static tree vect_create_destination_var (tree, tree); @@ -1139,6 +1141,10 @@ new_stmt_vec_info (tree stmt, struct loop *loop) STMT_VINFO_DATA_REF (res) = NULL; STMT_VINFO_MEMTAG (res) = NULL; STMT_VINFO_VECT_DR_BASE (res) = NULL; + STMT_VINFO_VECT_INIT_OFFSET (res) = NULL_TREE; + STMT_VINFO_VECT_STEP (res) = NULL_TREE; + STMT_VINFO_VECT_BASE_ALIGNED_P (res) = false; + STMT_VINFO_VECT_MISALIGNMENT (res) = NULL_TREE; return res; } @@ -1338,6 +1344,189 @@ vect_get_ptr_offset (tree ref ATTRIBUTE_UNUSED, } +/* Function vect_analyze_offset_expr + + Given an offset expression EXPR received from get_inner_reference, analyze + it and create an expression for INITIAL_OFFSET by substituting the variables + of EXPR with initial_condition of the corresponding access_fn in the loop. + E.g., + for i + for (j = 3; j < N; j++) + a[j].b[i][j] = 0; + + For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be + subsituted, since its access_fn in the inner loop is i. 'j' will be + substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where + C` = 3 * C_j + C. + + Compute MISALIGN (the misalignment of the data reference initial access from + its base) if possible. Misalignment can be calculated only if all the + variables can be substitued with constants, or if a variable is multiplied + by a multiple of VECTYPE_ALIGNMENT. In the above example, since 'i' cannot + be substituted, MISALIGN will be NULL_TREE in case that C_i is not a multiple + of VECTYPE_ALIGNMENT, and C` otherwise. (We perform MISALIGN modulo + VECTYPE_ALIGNMENT computation in the caller of this function). + + STEP is an evolution of the data reference in this loop in bytes. + In the above example, STEP is C_j. + + Return FALSE, if the analysis fails, e.g., there is no access_fn for a + variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN and STEP) + are NULL_TREEs. Otherwise, return TRUE. + +*/ + +static bool +vect_analyze_offset_expr (tree expr, + struct loop *loop, + tree vectype_alignment, + tree *initial_offset, + tree *misalign, + tree *step) +{ + tree oprnd0; + tree oprnd1; + tree left_offset = size_zero_node; + tree right_offset = size_zero_node; + tree left_misalign = size_zero_node; + tree right_misalign = size_zero_node; + tree left_step = size_zero_node; + tree right_step = size_zero_node; + enum tree_code code; + tree init, evolution, def_stmt; + + STRIP_NOPS (expr); + + *step = NULL_TREE; + *misalign = NULL_TREE; + *initial_offset = NULL_TREE; + + /* Stop conditions: + 1. Constant. */ + if (TREE_CONSTANT (expr)) + { + *initial_offset = fold_convert (sizetype, expr); + *misalign = fold_convert (sizetype, expr); + *step = size_zero_node; + return true; + } + + /* 2. Variable. Try to substitute with initial_condition of the corresponding + access_fn in the current loop. */ + if (SSA_VAR_P (expr)) + { + tree access_fn = analyze_scalar_evolution (loop, expr); + + if (access_fn == chrec_dont_know) + /* No access_fn. */ + return false; + + init = initial_condition_in_loop_num (access_fn, loop->num); + if (init == expr) + { + def_stmt = SSA_NAME_DEF_STMT (init); + if (def_stmt + && !IS_EMPTY_STMT (def_stmt) + && flow_bb_inside_loop_p (loop, bb_for_stmt (def_stmt))) + /* Not enough information: may be not loop invariant. + E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its + initial_condition is D, but it depends on i - loop's induction + variable. */ + return false; + } + + evolution = evolution_part_in_loop_num (access_fn, loop->num); + if (evolution && TREE_CODE (evolution) != INTEGER_CST) + /* Evolution is not constant. */ + return false; + + if (TREE_CONSTANT (init)) + *misalign = fold_convert (sizetype, init); + else + /* Not constant, misalignment cannot be calculated. */ + *misalign = NULL_TREE; + + *initial_offset = fold_convert (sizetype, init); + + *step = evolution ? fold_convert (sizetype, evolution) : size_zero_node; + return true; + } + + /* Recursive computation. */ + oprnd0 = TREE_OPERAND (expr, 0); + oprnd1 = TREE_OPERAND (expr, 1); + + if (!vect_analyze_offset_expr (oprnd0, loop, vectype_alignment, &left_offset, + &left_misalign, &left_step) + || !vect_analyze_offset_expr (oprnd1, loop, vectype_alignment, + &right_offset, &right_misalign, &right_step)) + return false; + + /* The type of the operation: plus, minus or mult. */ + code = TREE_CODE (expr); + switch (code) + { + case MULT_EXPR: + if (!TREE_CONSTANT (right_offset)) + /* RIGHT_OFFSET can be not constant. For example, for arrays of variable + sized types. + FORNOW: We don't support such cases. */ + return false; + + /* Misalignment computation. */ + if (SSA_VAR_P (left_offset)) + { + /* If the left side contains variable that cannot be substituted with + constant, we check if the right side is a multiple of ALIGNMENT. */ + if (integer_zerop (size_binop (TRUNC_MOD_EXPR, right_offset, + vectype_alignment))) + *misalign = size_zero_node; + else + /* If the remainder is not zero or the right side isn't constant, we + can't compute misalignment. */ + *misalign = NULL_TREE; + } + else + { + /* The left operand was successfully substituted with constant. */ + if (left_misalign) + /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is + NULL_TREE. */ + *misalign = size_binop (code, left_misalign, right_misalign); + else + *misalign = NULL_TREE; + } + + /* Step calculation. */ + /* Multiply the step by the right operand. */ + *step = size_binop (MULT_EXPR, left_step, right_offset); + break; + + case PLUS_EXPR: + case MINUS_EXPR: + /* Combine the recursive calculations for step and misalignment. */ + *step = size_binop (code, left_step, right_step); + + if (left_misalign && right_misalign) + *misalign = size_binop (code, left_misalign, right_misalign); + else + *misalign = NULL_TREE; + + break; + + default: + gcc_unreachable (); + } + + /* Compute offset. */ + *initial_offset = fold_convert (sizetype, + fold (build2 (code, TREE_TYPE (left_offset), + left_offset, + right_offset))); + return true; +} + + /* Function vect_get_base_and_bit_offset Return the BASE of the data reference EXPR. @@ -1885,13 +2074,13 @@ vect_create_data_ref_ptr (tree stmt, block_stmt_iterator *bsi, tree offset, fprintf (dump_file, "create array_ref of type: "); print_generic_expr (dump_file, vectype, TDF_SLIM); if (TREE_CODE (data_ref_base) == VAR_DECL) - fprintf (dump_file, "vectorizing a one dimensional array ref: "); + fprintf (dump_file, "\nvectorizing a one dimensional array ref: "); else if (TREE_CODE (data_ref_base) == ARRAY_REF) - fprintf (dump_file, "vectorizing a multidimensional array ref: "); + fprintf (dump_file, "\nvectorizing a multidimensional array ref: "); else if (TREE_CODE (data_ref_base) == COMPONENT_REF) - fprintf (dump_file, "vectorizing a record based array ref: "); + fprintf (dump_file, "\nvectorizing a record based array ref: "); else if (TREE_CODE (data_ref_base) == SSA_NAME) - fprintf (dump_file, "vectorizing a pointer ref: "); + fprintf (dump_file, "\nvectorizing a pointer ref: "); print_generic_expr (dump_file, base_name, TDF_SLIM); } diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h index 20563afc625b..642e3848fa9e 100644 --- a/gcc/tree-vectorizer.h +++ b/gcc/tree-vectorizer.h @@ -85,26 +85,46 @@ typedef struct _stmt_vec_info { /* Aliasing information. */ tree memtag; - /* Data reference base. This field holds the entire invariant part of the - data-reference (with respect to the relevant loop), as opposed to the - field DR_BASE of the STMT_VINFO_DATA_REF struct, which holds only the - initial base; e.g: - REF BR_BASE VECT_DR_BASE - a[i] a a - a[i][j] a a[i] */ - tree vect_dr_base; + /** The following fields are used to store the information about + data-reference. {base + initial_offset} is the first location accessed by + data-ref in the loop, and step is the stride of data-ref in the loop; + e.g.: + + Example 1 Example 2 + data-ref a[j].b[i][j] a + 4B (a is int*) + + base a a + initial_offset j_0*D_j + i_0*D_i + C 4 + step D_j 4 + + **/ + /* The above base, offset and step. */ + tree base; + tree initial_offset; + tree step; + + /* Alignment information. Whether the base of the data-reference is aligned + to vectype. */ + bool base_aligned_p; + /* Alignment information. The offset of the data-reference from its base + in bytes. */ + tree misalignment; } *stmt_vec_info; /* Access Functions. */ -#define STMT_VINFO_TYPE(S) (S)->type -#define STMT_VINFO_STMT(S) (S)->stmt -#define STMT_VINFO_LOOP(S) (S)->loop -#define STMT_VINFO_RELEVANT_P(S) (S)->relevant -#define STMT_VINFO_VECTYPE(S) (S)->vectype -#define STMT_VINFO_VEC_STMT(S) (S)->vectorized_stmt -#define STMT_VINFO_DATA_REF(S) (S)->data_ref_info -#define STMT_VINFO_MEMTAG(S) (S)->memtag -#define STMT_VINFO_VECT_DR_BASE(S) (S)->vect_dr_base +#define STMT_VINFO_TYPE(S) (S)->type +#define STMT_VINFO_STMT(S) (S)->stmt +#define STMT_VINFO_LOOP(S) (S)->loop +#define STMT_VINFO_RELEVANT_P(S) (S)->relevant +#define STMT_VINFO_VECTYPE(S) (S)->vectype +#define STMT_VINFO_VEC_STMT(S) (S)->vectorized_stmt +#define STMT_VINFO_DATA_REF(S) (S)->data_ref_info +#define STMT_VINFO_MEMTAG(S) (S)->memtag +#define STMT_VINFO_VECT_DR_BASE(S) (S)->base +#define STMT_VINFO_VECT_INIT_OFFSET(S) (S)->initial_offset +#define STMT_VINFO_VECT_STEP(S) (S)->step +#define STMT_VINFO_VECT_BASE_ALIGNED_P(S) (S)->base_aligned_p +#define STMT_VINFO_VECT_MISALIGNMENT(S) (S)->misalignment static inline void set_stmt_info (stmt_ann_t ann, stmt_vec_info stmt_info); static inline stmt_vec_info vinfo_for_stmt (tree stmt); -- 2.43.5