| /* Data References Analysis and Manipulation Utilities for Vectorization. |
| Copyright (C) 2003-2021 Free Software Foundation, Inc. |
| Contributed by Dorit Naishlos <dorit@il.ibm.com> |
| and Ira Rosen <irar@il.ibm.com> |
| |
| 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 3, or (at your option) any later |
| version. |
| |
| GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
| WARRANTY; without even the implied warranty of MERCHANTABILITY or |
| 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 COPYING3. If not see |
| <http://www.gnu.org/licenses/>. */ |
| |
| #include "config.h" |
| #include "system.h" |
| #include "coretypes.h" |
| #include "backend.h" |
| #include "target.h" |
| #include "rtl.h" |
| #include "tree.h" |
| #include "gimple.h" |
| #include "predict.h" |
| #include "memmodel.h" |
| #include "tm_p.h" |
| #include "ssa.h" |
| #include "optabs-tree.h" |
| #include "cgraph.h" |
| #include "dumpfile.h" |
| #include "alias.h" |
| #include "fold-const.h" |
| #include "stor-layout.h" |
| #include "tree-eh.h" |
| #include "gimplify.h" |
| #include "gimple-iterator.h" |
| #include "gimplify-me.h" |
| #include "tree-ssa-loop-ivopts.h" |
| #include "tree-ssa-loop-manip.h" |
| #include "tree-ssa-loop.h" |
| #include "cfgloop.h" |
| #include "tree-scalar-evolution.h" |
| #include "tree-vectorizer.h" |
| #include "expr.h" |
| #include "builtins.h" |
| #include "tree-cfg.h" |
| #include "tree-hash-traits.h" |
| #include "vec-perm-indices.h" |
| #include "internal-fn.h" |
| |
| /* Return true if load- or store-lanes optab OPTAB is implemented for |
| COUNT vectors of type VECTYPE. NAME is the name of OPTAB. */ |
| |
| static bool |
| vect_lanes_optab_supported_p (const char *name, convert_optab optab, |
| tree vectype, unsigned HOST_WIDE_INT count) |
| { |
| machine_mode mode, array_mode; |
| bool limit_p; |
| |
| mode = TYPE_MODE (vectype); |
| if (!targetm.array_mode (mode, count).exists (&array_mode)) |
| { |
| poly_uint64 bits = count * GET_MODE_BITSIZE (mode); |
| limit_p = !targetm.array_mode_supported_p (mode, count); |
| if (!int_mode_for_size (bits, limit_p).exists (&array_mode)) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "no array mode for %s[%wu]\n", |
| GET_MODE_NAME (mode), count); |
| return false; |
| } |
| } |
| |
| if (convert_optab_handler (optab, array_mode, mode) == CODE_FOR_nothing) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "cannot use %s<%s><%s>\n", name, |
| GET_MODE_NAME (array_mode), GET_MODE_NAME (mode)); |
| return false; |
| } |
| |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "can use %s<%s><%s>\n", name, GET_MODE_NAME (array_mode), |
| GET_MODE_NAME (mode)); |
| |
| return true; |
| } |
| |
| |
| /* Return the smallest scalar part of STMT_INFO. |
| This is used to determine the vectype of the stmt. We generally set the |
| vectype according to the type of the result (lhs). For stmts whose |
| result-type is different than the type of the arguments (e.g., demotion, |
| promotion), vectype will be reset appropriately (later). Note that we have |
| to visit the smallest datatype in this function, because that determines the |
| VF. If the smallest datatype in the loop is present only as the rhs of a |
| promotion operation - we'd miss it. |
| Such a case, where a variable of this datatype does not appear in the lhs |
| anywhere in the loop, can only occur if it's an invariant: e.g.: |
| 'int_x = (int) short_inv', which we'd expect to have been optimized away by |
| invariant motion. However, we cannot rely on invariant motion to always |
| take invariants out of the loop, and so in the case of promotion we also |
| have to check the rhs. |
| LHS_SIZE_UNIT and RHS_SIZE_UNIT contain the sizes of the corresponding |
| types. */ |
| |
| tree |
| vect_get_smallest_scalar_type (stmt_vec_info stmt_info, |
| HOST_WIDE_INT *lhs_size_unit, |
| HOST_WIDE_INT *rhs_size_unit) |
| { |
| tree scalar_type = gimple_expr_type (stmt_info->stmt); |
| HOST_WIDE_INT lhs, rhs; |
| |
| /* During the analysis phase, this function is called on arbitrary |
| statements that might not have scalar results. */ |
| if (!tree_fits_uhwi_p (TYPE_SIZE_UNIT (scalar_type))) |
| return scalar_type; |
| |
| lhs = rhs = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (scalar_type)); |
| |
| gassign *assign = dyn_cast <gassign *> (stmt_info->stmt); |
| if (assign |
| && (gimple_assign_cast_p (assign) |
| || gimple_assign_rhs_code (assign) == DOT_PROD_EXPR |
| || gimple_assign_rhs_code (assign) == WIDEN_SUM_EXPR |
| || gimple_assign_rhs_code (assign) == WIDEN_MULT_EXPR |
| || gimple_assign_rhs_code (assign) == WIDEN_LSHIFT_EXPR |
| || gimple_assign_rhs_code (assign) == WIDEN_PLUS_EXPR |
| || gimple_assign_rhs_code (assign) == WIDEN_MINUS_EXPR |
| || gimple_assign_rhs_code (assign) == FLOAT_EXPR)) |
| { |
| tree rhs_type = TREE_TYPE (gimple_assign_rhs1 (assign)); |
| |
| rhs = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (rhs_type)); |
| if (rhs < lhs) |
| scalar_type = rhs_type; |
| } |
| else if (gcall *call = dyn_cast <gcall *> (stmt_info->stmt)) |
| { |
| unsigned int i = 0; |
| if (gimple_call_internal_p (call)) |
| { |
| internal_fn ifn = gimple_call_internal_fn (call); |
| if (internal_load_fn_p (ifn) || internal_store_fn_p (ifn)) |
| /* gimple_expr_type already picked the type of the loaded |
| or stored data. */ |
| i = ~0U; |
| else if (internal_fn_mask_index (ifn) == 0) |
| i = 1; |
| } |
| if (i < gimple_call_num_args (call)) |
| { |
| tree rhs_type = TREE_TYPE (gimple_call_arg (call, i)); |
| if (tree_fits_uhwi_p (TYPE_SIZE_UNIT (rhs_type))) |
| { |
| rhs = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (rhs_type)); |
| if (rhs < lhs) |
| scalar_type = rhs_type; |
| } |
| } |
| } |
| |
| *lhs_size_unit = lhs; |
| *rhs_size_unit = rhs; |
| return scalar_type; |
| } |
| |
| |
| /* Insert DDR into LOOP_VINFO list of ddrs that may alias and need to be |
| tested at run-time. Return TRUE if DDR was successfully inserted. |
| Return false if versioning is not supported. */ |
| |
| static opt_result |
| vect_mark_for_runtime_alias_test (ddr_p ddr, loop_vec_info loop_vinfo) |
| { |
| class loop *loop = LOOP_VINFO_LOOP (loop_vinfo); |
| |
| if ((unsigned) param_vect_max_version_for_alias_checks == 0) |
| return opt_result::failure_at (vect_location, |
| "will not create alias checks, as" |
| " --param vect-max-version-for-alias-checks" |
| " == 0\n"); |
| |
| opt_result res |
| = runtime_alias_check_p (ddr, loop, |
| optimize_loop_nest_for_speed_p (loop)); |
| if (!res) |
| return res; |
| |
| LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo).safe_push (ddr); |
| return opt_result::success (); |
| } |
| |
| /* Record that loop LOOP_VINFO needs to check that VALUE is nonzero. */ |
| |
| static void |
| vect_check_nonzero_value (loop_vec_info loop_vinfo, tree value) |
| { |
| vec<tree> checks = LOOP_VINFO_CHECK_NONZERO (loop_vinfo); |
| for (unsigned int i = 0; i < checks.length(); ++i) |
| if (checks[i] == value) |
| return; |
| |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "need run-time check that %T is nonzero\n", |
| value); |
| LOOP_VINFO_CHECK_NONZERO (loop_vinfo).safe_push (value); |
| } |
| |
| /* Return true if we know that the order of vectorized DR_INFO_A and |
| vectorized DR_INFO_B will be the same as the order of DR_INFO_A and |
| DR_INFO_B. At least one of the accesses is a write. */ |
| |
| static bool |
| vect_preserves_scalar_order_p (dr_vec_info *dr_info_a, dr_vec_info *dr_info_b) |
| { |
| stmt_vec_info stmtinfo_a = dr_info_a->stmt; |
| stmt_vec_info stmtinfo_b = dr_info_b->stmt; |
| |
| /* Single statements are always kept in their original order. */ |
| if (!STMT_VINFO_GROUPED_ACCESS (stmtinfo_a) |
| && !STMT_VINFO_GROUPED_ACCESS (stmtinfo_b)) |
| return true; |
| |
| /* STMT_A and STMT_B belong to overlapping groups. All loads are |
| emitted at the position of the first scalar load. |
| Stores in a group are emitted at the position of the last scalar store. |
| Compute that position and check whether the resulting order matches |
| the current one. */ |
| stmt_vec_info il_a = DR_GROUP_FIRST_ELEMENT (stmtinfo_a); |
| if (il_a) |
| { |
| if (DR_IS_WRITE (STMT_VINFO_DATA_REF (stmtinfo_a))) |
| for (stmt_vec_info s = DR_GROUP_NEXT_ELEMENT (il_a); s; |
| s = DR_GROUP_NEXT_ELEMENT (s)) |
| il_a = get_later_stmt (il_a, s); |
| else /* DR_IS_READ */ |
| for (stmt_vec_info s = DR_GROUP_NEXT_ELEMENT (il_a); s; |
| s = DR_GROUP_NEXT_ELEMENT (s)) |
| if (get_later_stmt (il_a, s) == il_a) |
| il_a = s; |
| } |
| else |
| il_a = stmtinfo_a; |
| stmt_vec_info il_b = DR_GROUP_FIRST_ELEMENT (stmtinfo_b); |
| if (il_b) |
| { |
| if (DR_IS_WRITE (STMT_VINFO_DATA_REF (stmtinfo_b))) |
| for (stmt_vec_info s = DR_GROUP_NEXT_ELEMENT (il_b); s; |
| s = DR_GROUP_NEXT_ELEMENT (s)) |
| il_b = get_later_stmt (il_b, s); |
| else /* DR_IS_READ */ |
| for (stmt_vec_info s = DR_GROUP_NEXT_ELEMENT (il_b); s; |
| s = DR_GROUP_NEXT_ELEMENT (s)) |
| if (get_later_stmt (il_b, s) == il_b) |
| il_b = s; |
| } |
| else |
| il_b = stmtinfo_b; |
| bool a_after_b = (get_later_stmt (stmtinfo_a, stmtinfo_b) == stmtinfo_a); |
| return (get_later_stmt (il_a, il_b) == il_a) == a_after_b; |
| } |
| |
| /* A subroutine of vect_analyze_data_ref_dependence. Handle |
| DDR_COULD_BE_INDEPENDENT_P ddr DDR that has a known set of dependence |
| distances. These distances are conservatively correct but they don't |
| reflect a guaranteed dependence. |
| |
| Return true if this function does all the work necessary to avoid |
| an alias or false if the caller should use the dependence distances |
| to limit the vectorization factor in the usual way. LOOP_DEPTH is |
| the depth of the loop described by LOOP_VINFO and the other arguments |
| are as for vect_analyze_data_ref_dependence. */ |
| |
| static bool |
| vect_analyze_possibly_independent_ddr (data_dependence_relation *ddr, |
| loop_vec_info loop_vinfo, |
| int loop_depth, unsigned int *max_vf) |
| { |
| class loop *loop = LOOP_VINFO_LOOP (loop_vinfo); |
| lambda_vector dist_v; |
| unsigned int i; |
| FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v) |
| { |
| int dist = dist_v[loop_depth]; |
| if (dist != 0 && !(dist > 0 && DDR_REVERSED_P (ddr))) |
| { |
| /* If the user asserted safelen >= DIST consecutive iterations |
| can be executed concurrently, assume independence. |
| |
| ??? An alternative would be to add the alias check even |
| in this case, and vectorize the fallback loop with the |
| maximum VF set to safelen. However, if the user has |
| explicitly given a length, it's less likely that that |
| would be a win. */ |
| if (loop->safelen >= 2 && abs_hwi (dist) <= loop->safelen) |
| { |
| if ((unsigned int) loop->safelen < *max_vf) |
| *max_vf = loop->safelen; |
| LOOP_VINFO_NO_DATA_DEPENDENCIES (loop_vinfo) = false; |
| continue; |
| } |
| |
| /* For dependence distances of 2 or more, we have the option |
| of limiting VF or checking for an alias at runtime. |
| Prefer to check at runtime if we can, to avoid limiting |
| the VF unnecessarily when the bases are in fact independent. |
| |
| Note that the alias checks will be removed if the VF ends up |
| being small enough. */ |
| dr_vec_info *dr_info_a = loop_vinfo->lookup_dr (DDR_A (ddr)); |
| dr_vec_info *dr_info_b = loop_vinfo->lookup_dr (DDR_B (ddr)); |
| return (!STMT_VINFO_GATHER_SCATTER_P (dr_info_a->stmt) |
| && !STMT_VINFO_GATHER_SCATTER_P (dr_info_b->stmt) |
| && vect_mark_for_runtime_alias_test (ddr, loop_vinfo)); |
| } |
| } |
| return true; |
| } |
| |
| |
| /* Function vect_analyze_data_ref_dependence. |
| |
| FIXME: I needed to change the sense of the returned flag. |
| |
| Return FALSE if there (might) exist a dependence between a memory-reference |
| DRA and a memory-reference DRB. When versioning for alias may check a |
| dependence at run-time, return TRUE. Adjust *MAX_VF according to |
| the data dependence. */ |
| |
| static opt_result |
| vect_analyze_data_ref_dependence (struct data_dependence_relation *ddr, |
| loop_vec_info loop_vinfo, |
| unsigned int *max_vf) |
| { |
| unsigned int i; |
| class loop *loop = LOOP_VINFO_LOOP (loop_vinfo); |
| struct data_reference *dra = DDR_A (ddr); |
| struct data_reference *drb = DDR_B (ddr); |
| dr_vec_info *dr_info_a = loop_vinfo->lookup_dr (dra); |
| dr_vec_info *dr_info_b = loop_vinfo->lookup_dr (drb); |
| stmt_vec_info stmtinfo_a = dr_info_a->stmt; |
| stmt_vec_info stmtinfo_b = dr_info_b->stmt; |
| lambda_vector dist_v; |
| unsigned int loop_depth; |
| |
| /* In loop analysis all data references should be vectorizable. */ |
| if (!STMT_VINFO_VECTORIZABLE (stmtinfo_a) |
| || !STMT_VINFO_VECTORIZABLE (stmtinfo_b)) |
| gcc_unreachable (); |
| |
| /* Independent data accesses. */ |
| if (DDR_ARE_DEPENDENT (ddr) == chrec_known) |
| return opt_result::success (); |
| |
| if (dra == drb |
| || (DR_IS_READ (dra) && DR_IS_READ (drb))) |
| return opt_result::success (); |
| |
| /* We do not have to consider dependences between accesses that belong |
| to the same group, unless the stride could be smaller than the |
| group size. */ |
| if (DR_GROUP_FIRST_ELEMENT (stmtinfo_a) |
| && (DR_GROUP_FIRST_ELEMENT (stmtinfo_a) |
| == DR_GROUP_FIRST_ELEMENT (stmtinfo_b)) |
| && !STMT_VINFO_STRIDED_P (stmtinfo_a)) |
| return opt_result::success (); |
| |
| /* Even if we have an anti-dependence then, as the vectorized loop covers at |
| least two scalar iterations, there is always also a true dependence. |
| As the vectorizer does not re-order loads and stores we can ignore |
| the anti-dependence if TBAA can disambiguate both DRs similar to the |
| case with known negative distance anti-dependences (positive |
| distance anti-dependences would violate TBAA constraints). */ |
| if (((DR_IS_READ (dra) && DR_IS_WRITE (drb)) |
| || (DR_IS_WRITE (dra) && DR_IS_READ (drb))) |
| && !alias_sets_conflict_p (get_alias_set (DR_REF (dra)), |
| get_alias_set (DR_REF (drb)))) |
| return opt_result::success (); |
| |
| /* Unknown data dependence. */ |
| if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) |
| { |
| /* If user asserted safelen consecutive iterations can be |
| executed concurrently, assume independence. */ |
| if (loop->safelen >= 2) |
| { |
| if ((unsigned int) loop->safelen < *max_vf) |
| *max_vf = loop->safelen; |
| LOOP_VINFO_NO_DATA_DEPENDENCIES (loop_vinfo) = false; |
| return opt_result::success (); |
| } |
| |
| if (STMT_VINFO_GATHER_SCATTER_P (stmtinfo_a) |
| || STMT_VINFO_GATHER_SCATTER_P (stmtinfo_b)) |
| return opt_result::failure_at |
| (stmtinfo_a->stmt, |
| "versioning for alias not supported for: " |
| "can't determine dependence between %T and %T\n", |
| DR_REF (dra), DR_REF (drb)); |
| |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, stmtinfo_a->stmt, |
| "versioning for alias required: " |
| "can't determine dependence between %T and %T\n", |
| DR_REF (dra), DR_REF (drb)); |
| |
| /* Add to list of ddrs that need to be tested at run-time. */ |
| return vect_mark_for_runtime_alias_test (ddr, loop_vinfo); |
| } |
| |
| /* Known data dependence. */ |
| if (DDR_NUM_DIST_VECTS (ddr) == 0) |
| { |
| /* If user asserted safelen consecutive iterations can be |
| executed concurrently, assume independence. */ |
| if (loop->safelen >= 2) |
| { |
| if ((unsigned int) loop->safelen < *max_vf) |
| *max_vf = loop->safelen; |
| LOOP_VINFO_NO_DATA_DEPENDENCIES (loop_vinfo) = false; |
| return opt_result::success (); |
| } |
| |
| if (STMT_VINFO_GATHER_SCATTER_P (stmtinfo_a) |
| || STMT_VINFO_GATHER_SCATTER_P (stmtinfo_b)) |
| return opt_result::failure_at |
| (stmtinfo_a->stmt, |
| "versioning for alias not supported for: " |
| "bad dist vector for %T and %T\n", |
| DR_REF (dra), DR_REF (drb)); |
| |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, stmtinfo_a->stmt, |
| "versioning for alias required: " |
| "bad dist vector for %T and %T\n", |
| DR_REF (dra), DR_REF (drb)); |
| /* Add to list of ddrs that need to be tested at run-time. */ |
| return vect_mark_for_runtime_alias_test (ddr, loop_vinfo); |
| } |
| |
| loop_depth = index_in_loop_nest (loop->num, DDR_LOOP_NEST (ddr)); |
| |
| if (DDR_COULD_BE_INDEPENDENT_P (ddr) |
| && vect_analyze_possibly_independent_ddr (ddr, loop_vinfo, |
| loop_depth, max_vf)) |
| return opt_result::success (); |
| |
| FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v) |
| { |
| int dist = dist_v[loop_depth]; |
| |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "dependence distance = %d.\n", dist); |
| |
| if (dist == 0) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "dependence distance == 0 between %T and %T\n", |
| DR_REF (dra), DR_REF (drb)); |
| |
| /* When we perform grouped accesses and perform implicit CSE |
| by detecting equal accesses and doing disambiguation with |
| runtime alias tests like for |
| .. = a[i]; |
| .. = a[i+1]; |
| a[i] = ..; |
| a[i+1] = ..; |
| *p = ..; |
| .. = a[i]; |
| .. = a[i+1]; |
| where we will end up loading { a[i], a[i+1] } once, make |
| sure that inserting group loads before the first load and |
| stores after the last store will do the right thing. |
| Similar for groups like |
| a[i] = ...; |
| ... = a[i]; |
| a[i+1] = ...; |
| where loads from the group interleave with the store. */ |
| if (!vect_preserves_scalar_order_p (dr_info_a, dr_info_b)) |
| return opt_result::failure_at (stmtinfo_a->stmt, |
| "READ_WRITE dependence" |
| " in interleaving.\n"); |
| |
| if (loop->safelen < 2) |
| { |
| tree indicator = dr_zero_step_indicator (dra); |
| if (!indicator || integer_zerop (indicator)) |
| return opt_result::failure_at (stmtinfo_a->stmt, |
| "access also has a zero step\n"); |
| else if (TREE_CODE (indicator) != INTEGER_CST) |
| vect_check_nonzero_value (loop_vinfo, indicator); |
| } |
| continue; |
| } |
| |
| if (dist > 0 && DDR_REVERSED_P (ddr)) |
| { |
| /* If DDR_REVERSED_P the order of the data-refs in DDR was |
| reversed (to make distance vector positive), and the actual |
| distance is negative. */ |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "dependence distance negative.\n"); |
| /* When doing outer loop vectorization, we need to check if there is |
| a backward dependence at the inner loop level if the dependence |
| at the outer loop is reversed. See PR81740. */ |
| if (nested_in_vect_loop_p (loop, stmtinfo_a) |
| || nested_in_vect_loop_p (loop, stmtinfo_b)) |
| { |
| unsigned inner_depth = index_in_loop_nest (loop->inner->num, |
| DDR_LOOP_NEST (ddr)); |
| if (dist_v[inner_depth] < 0) |
| return opt_result::failure_at (stmtinfo_a->stmt, |
| "not vectorized, dependence " |
| "between data-refs %T and %T\n", |
| DR_REF (dra), DR_REF (drb)); |
| } |
| /* Record a negative dependence distance to later limit the |
| amount of stmt copying / unrolling we can perform. |
| Only need to handle read-after-write dependence. */ |
| if (DR_IS_READ (drb) |
| && (STMT_VINFO_MIN_NEG_DIST (stmtinfo_b) == 0 |
| || STMT_VINFO_MIN_NEG_DIST (stmtinfo_b) > (unsigned)dist)) |
| STMT_VINFO_MIN_NEG_DIST (stmtinfo_b) = dist; |
| continue; |
| } |
| |
| unsigned int abs_dist = abs (dist); |
| if (abs_dist >= 2 && abs_dist < *max_vf) |
| { |
| /* The dependence distance requires reduction of the maximal |
| vectorization factor. */ |
| *max_vf = abs_dist; |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "adjusting maximal vectorization factor to %i\n", |
| *max_vf); |
| } |
| |
| if (abs_dist >= *max_vf) |
| { |
| /* Dependence distance does not create dependence, as far as |
| vectorization is concerned, in this case. */ |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "dependence distance >= VF.\n"); |
| continue; |
| } |
| |
| return opt_result::failure_at (stmtinfo_a->stmt, |
| "not vectorized, possible dependence " |
| "between data-refs %T and %T\n", |
| DR_REF (dra), DR_REF (drb)); |
| } |
| |
| return opt_result::success (); |
| } |
| |
| /* Function vect_analyze_data_ref_dependences. |
| |
| Examine all the data references in the loop, and make sure there do not |
| exist any data dependences between them. Set *MAX_VF according to |
| the maximum vectorization factor the data dependences allow. */ |
| |
| opt_result |
| vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo, |
| unsigned int *max_vf) |
| { |
| unsigned int i; |
| struct data_dependence_relation *ddr; |
| |
| DUMP_VECT_SCOPE ("vect_analyze_data_ref_dependences"); |
| |
| if (!LOOP_VINFO_DDRS (loop_vinfo).exists ()) |
| { |
| LOOP_VINFO_DDRS (loop_vinfo) |
| .create (LOOP_VINFO_DATAREFS (loop_vinfo).length () |
| * LOOP_VINFO_DATAREFS (loop_vinfo).length ()); |
| /* We do not need read-read dependences. */ |
| bool res = compute_all_dependences (LOOP_VINFO_DATAREFS (loop_vinfo), |
| &LOOP_VINFO_DDRS (loop_vinfo), |
| LOOP_VINFO_LOOP_NEST (loop_vinfo), |
| false); |
| gcc_assert (res); |
| } |
| |
| LOOP_VINFO_NO_DATA_DEPENDENCIES (loop_vinfo) = true; |
| |
| /* For epilogues we either have no aliases or alias versioning |
| was applied to original loop. Therefore we may just get max_vf |
| using VF of original loop. */ |
| if (LOOP_VINFO_EPILOGUE_P (loop_vinfo)) |
| *max_vf = LOOP_VINFO_ORIG_MAX_VECT_FACTOR (loop_vinfo); |
| else |
| FOR_EACH_VEC_ELT (LOOP_VINFO_DDRS (loop_vinfo), i, ddr) |
| { |
| opt_result res |
| = vect_analyze_data_ref_dependence (ddr, loop_vinfo, max_vf); |
| if (!res) |
| return res; |
| } |
| |
| return opt_result::success (); |
| } |
| |
| |
| /* Function vect_slp_analyze_data_ref_dependence. |
| |
| Return TRUE if there (might) exist a dependence between a memory-reference |
| DRA and a memory-reference DRB for VINFO. When versioning for alias |
| may check a dependence at run-time, return FALSE. Adjust *MAX_VF |
| according to the data dependence. */ |
| |
| static bool |
| vect_slp_analyze_data_ref_dependence (vec_info *vinfo, |
| struct data_dependence_relation *ddr) |
| { |
| struct data_reference *dra = DDR_A (ddr); |
| struct data_reference *drb = DDR_B (ddr); |
| dr_vec_info *dr_info_a = vinfo->lookup_dr (dra); |
| dr_vec_info *dr_info_b = vinfo->lookup_dr (drb); |
| |
| /* We need to check dependences of statements marked as unvectorizable |
| as well, they still can prohibit vectorization. */ |
| |
| /* Independent data accesses. */ |
| if (DDR_ARE_DEPENDENT (ddr) == chrec_known) |
| return false; |
| |
| if (dra == drb) |
| return false; |
| |
| /* Read-read is OK. */ |
| if (DR_IS_READ (dra) && DR_IS_READ (drb)) |
| return false; |
| |
| /* If dra and drb are part of the same interleaving chain consider |
| them independent. */ |
| if (STMT_VINFO_GROUPED_ACCESS (dr_info_a->stmt) |
| && (DR_GROUP_FIRST_ELEMENT (dr_info_a->stmt) |
| == DR_GROUP_FIRST_ELEMENT (dr_info_b->stmt))) |
| return false; |
| |
| /* Unknown data dependence. */ |
| if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "can't determine dependence between %T and %T\n", |
| DR_REF (dra), DR_REF (drb)); |
| } |
| else if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "determined dependence between %T and %T\n", |
| DR_REF (dra), DR_REF (drb)); |
| |
| return true; |
| } |
| |
| |
| /* Analyze dependences involved in the transform of SLP NODE. STORES |
| contain the vector of scalar stores of this instance if we are |
| disambiguating the loads. */ |
| |
| static bool |
| vect_slp_analyze_node_dependences (vec_info *vinfo, slp_tree node, |
| vec<stmt_vec_info> stores, |
| stmt_vec_info last_store_info) |
| { |
| /* This walks over all stmts involved in the SLP load/store done |
| in NODE verifying we can sink them up to the last stmt in the |
| group. */ |
| if (DR_IS_WRITE (STMT_VINFO_DATA_REF (SLP_TREE_REPRESENTATIVE (node)))) |
| { |
| stmt_vec_info last_access_info = vect_find_last_scalar_stmt_in_slp (node); |
| for (unsigned k = 0; k < SLP_TREE_SCALAR_STMTS (node).length (); ++k) |
| { |
| stmt_vec_info access_info |
| = vect_orig_stmt (SLP_TREE_SCALAR_STMTS (node)[k]); |
| if (access_info == last_access_info) |
| continue; |
| data_reference *dr_a = STMT_VINFO_DATA_REF (access_info); |
| ao_ref ref; |
| bool ref_initialized_p = false; |
| for (gimple_stmt_iterator gsi = gsi_for_stmt (access_info->stmt); |
| gsi_stmt (gsi) != last_access_info->stmt; gsi_next (&gsi)) |
| { |
| gimple *stmt = gsi_stmt (gsi); |
| if (! gimple_vuse (stmt)) |
| continue; |
| |
| /* If we couldn't record a (single) data reference for this |
| stmt we have to resort to the alias oracle. */ |
| stmt_vec_info stmt_info = vinfo->lookup_stmt (stmt); |
| data_reference *dr_b = STMT_VINFO_DATA_REF (stmt_info); |
| if (!dr_b) |
| { |
| /* We are moving a store - this means |
| we cannot use TBAA for disambiguation. */ |
| if (!ref_initialized_p) |
| ao_ref_init (&ref, DR_REF (dr_a)); |
| if (stmt_may_clobber_ref_p_1 (stmt, &ref, false) |
| || ref_maybe_used_by_stmt_p (stmt, &ref, false)) |
| return false; |
| continue; |
| } |
| |
| bool dependent = false; |
| /* If we run into a store of this same instance (we've just |
| marked those) then delay dependence checking until we run |
| into the last store because this is where it will have |
| been sunk to (and we verify if we can do that as well). */ |
| if (gimple_visited_p (stmt)) |
| { |
| if (stmt_info != last_store_info) |
| continue; |
| unsigned i; |
| stmt_vec_info store_info; |
| FOR_EACH_VEC_ELT (stores, i, store_info) |
| { |
| data_reference *store_dr |
| = STMT_VINFO_DATA_REF (store_info); |
| ddr_p ddr = initialize_data_dependence_relation |
| (dr_a, store_dr, vNULL); |
| dependent |
| = vect_slp_analyze_data_ref_dependence (vinfo, ddr); |
| free_dependence_relation (ddr); |
| if (dependent) |
| break; |
| } |
| } |
| else |
| { |
| ddr_p ddr = initialize_data_dependence_relation (dr_a, |
| dr_b, vNULL); |
| dependent = vect_slp_analyze_data_ref_dependence (vinfo, ddr); |
| free_dependence_relation (ddr); |
| } |
| if (dependent) |
| return false; |
| } |
| } |
| } |
| else /* DR_IS_READ */ |
| { |
| stmt_vec_info first_access_info |
| = vect_find_first_scalar_stmt_in_slp (node); |
| for (unsigned k = 0; k < SLP_TREE_SCALAR_STMTS (node).length (); ++k) |
| { |
| stmt_vec_info access_info |
| = vect_orig_stmt (SLP_TREE_SCALAR_STMTS (node)[k]); |
| if (access_info == first_access_info) |
| continue; |
| data_reference *dr_a = STMT_VINFO_DATA_REF (access_info); |
| ao_ref ref; |
| bool ref_initialized_p = false; |
| for (gimple_stmt_iterator gsi = gsi_for_stmt (access_info->stmt); |
| gsi_stmt (gsi) != first_access_info->stmt; gsi_prev (&gsi)) |
| { |
| gimple *stmt = gsi_stmt (gsi); |
| if (! gimple_vdef (stmt)) |
| continue; |
| |
| /* If we couldn't record a (single) data reference for this |
| stmt we have to resort to the alias oracle. */ |
| stmt_vec_info stmt_info = vinfo->lookup_stmt (stmt); |
| data_reference *dr_b = STMT_VINFO_DATA_REF (stmt_info); |
| if (!dr_b) |
| { |
| /* We are hoisting a load - this means we can use |
| TBAA for disambiguation. */ |
| if (!ref_initialized_p) |
| ao_ref_init (&ref, DR_REF (dr_a)); |
| if (stmt_may_clobber_ref_p_1 (stmt, &ref, true)) |
| return false; |
| continue; |
| } |
| |
| bool dependent = false; |
| /* If we run into a store of this same instance (we've just |
| marked those) then delay dependence checking until we run |
| into the last store because this is where it will have |
| been sunk to (and we verify if we can do that as well). */ |
| if (gimple_visited_p (stmt)) |
| { |
| if (stmt_info != last_store_info) |
| continue; |
| unsigned i; |
| stmt_vec_info store_info; |
| FOR_EACH_VEC_ELT (stores, i, store_info) |
| { |
| data_reference *store_dr |
| = STMT_VINFO_DATA_REF (store_info); |
| ddr_p ddr = initialize_data_dependence_relation |
| (dr_a, store_dr, vNULL); |
| dependent |
| = vect_slp_analyze_data_ref_dependence (vinfo, ddr); |
| free_dependence_relation (ddr); |
| if (dependent) |
| break; |
| } |
| } |
| else |
| { |
| ddr_p ddr = initialize_data_dependence_relation (dr_a, |
| dr_b, vNULL); |
| dependent = vect_slp_analyze_data_ref_dependence (vinfo, ddr); |
| free_dependence_relation (ddr); |
| } |
| if (dependent) |
| return false; |
| } |
| } |
| } |
| return true; |
| } |
| |
| |
| /* Function vect_analyze_data_ref_dependences. |
| |
| Examine all the data references in the basic-block, and make sure there |
| do not exist any data dependences between them. Set *MAX_VF according to |
| the maximum vectorization factor the data dependences allow. */ |
| |
| bool |
| vect_slp_analyze_instance_dependence (vec_info *vinfo, slp_instance instance) |
| { |
| DUMP_VECT_SCOPE ("vect_slp_analyze_instance_dependence"); |
| |
| /* The stores of this instance are at the root of the SLP tree. */ |
| slp_tree store = SLP_INSTANCE_TREE (instance); |
| if (! STMT_VINFO_DATA_REF (SLP_TREE_REPRESENTATIVE (store))) |
| store = NULL; |
| |
| /* Verify we can sink stores to the vectorized stmt insert location. */ |
| stmt_vec_info last_store_info = NULL; |
| if (store) |
| { |
| if (! vect_slp_analyze_node_dependences (vinfo, store, vNULL, NULL)) |
| return false; |
| |
| /* Mark stores in this instance and remember the last one. */ |
| last_store_info = vect_find_last_scalar_stmt_in_slp (store); |
| for (unsigned k = 0; k < SLP_TREE_SCALAR_STMTS (store).length (); ++k) |
| gimple_set_visited (SLP_TREE_SCALAR_STMTS (store)[k]->stmt, true); |
| } |
| |
| bool res = true; |
| |
| /* Verify we can sink loads to the vectorized stmt insert location, |
| special-casing stores of this instance. */ |
| slp_tree load; |
| unsigned int i; |
| FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (instance), i, load) |
| if (! vect_slp_analyze_node_dependences (vinfo, load, |
| store |
| ? SLP_TREE_SCALAR_STMTS (store) |
| : vNULL, last_store_info)) |
| { |
| res = false; |
| break; |
| } |
| |
| /* Unset the visited flag. */ |
| if (store) |
| for (unsigned k = 0; k < SLP_TREE_SCALAR_STMTS (store).length (); ++k) |
| gimple_set_visited (SLP_TREE_SCALAR_STMTS (store)[k]->stmt, false); |
| |
| return res; |
| } |
| |
| /* Record the base alignment guarantee given by DRB, which occurs |
| in STMT_INFO. */ |
| |
| static void |
| vect_record_base_alignment (vec_info *vinfo, stmt_vec_info stmt_info, |
| innermost_loop_behavior *drb) |
| { |
| bool existed; |
| innermost_loop_behavior *&entry |
| = vinfo->base_alignments.get_or_insert (drb->base_address, &existed); |
| if (!existed || entry->base_alignment < drb->base_alignment) |
| { |
| entry = drb; |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "recording new base alignment for %T\n" |
| " alignment: %d\n" |
| " misalignment: %d\n" |
| " based on: %G", |
| drb->base_address, |
| drb->base_alignment, |
| drb->base_misalignment, |
| stmt_info->stmt); |
| } |
| } |
| |
| /* If the region we're going to vectorize is reached, all unconditional |
| data references occur at least once. We can therefore pool the base |
| alignment guarantees from each unconditional reference. Do this by |
| going through all the data references in VINFO and checking whether |
| the containing statement makes the reference unconditionally. If so, |
| record the alignment of the base address in VINFO so that it can be |
| used for all other references with the same base. */ |
| |
| void |
| vect_record_base_alignments (vec_info *vinfo) |
| { |
| loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo); |
| class loop *loop = loop_vinfo ? LOOP_VINFO_LOOP (loop_vinfo) : NULL; |
| data_reference *dr; |
| unsigned int i; |
| FOR_EACH_VEC_ELT (vinfo->shared->datarefs, i, dr) |
| { |
| dr_vec_info *dr_info = vinfo->lookup_dr (dr); |
| stmt_vec_info stmt_info = dr_info->stmt; |
| if (!DR_IS_CONDITIONAL_IN_STMT (dr) |
| && STMT_VINFO_VECTORIZABLE (stmt_info) |
| && !STMT_VINFO_GATHER_SCATTER_P (stmt_info)) |
| { |
| vect_record_base_alignment (vinfo, stmt_info, &DR_INNERMOST (dr)); |
| |
| /* If DR is nested in the loop that is being vectorized, we can also |
| record the alignment of the base wrt the outer loop. */ |
| if (loop && nested_in_vect_loop_p (loop, stmt_info)) |
| vect_record_base_alignment |
| (vinfo, stmt_info, &STMT_VINFO_DR_WRT_VEC_LOOP (stmt_info)); |
| } |
| } |
| } |
| |
| /* Return the target alignment for the vectorized form of DR_INFO. */ |
| |
| static poly_uint64 |
| vect_calculate_target_alignment (dr_vec_info *dr_info) |
| { |
| tree vectype = STMT_VINFO_VECTYPE (dr_info->stmt); |
| return targetm.vectorize.preferred_vector_alignment (vectype); |
| } |
| |
| /* Function vect_compute_data_ref_alignment |
| |
| Compute the misalignment of the data reference DR_INFO. |
| |
| Output: |
| 1. DR_MISALIGNMENT (DR_INFO) is defined. |
| |
| FOR NOW: No analysis is actually performed. Misalignment is calculated |
| only for trivial cases. TODO. */ |
| |
| static void |
| vect_compute_data_ref_alignment (vec_info *vinfo, dr_vec_info *dr_info) |
| { |
| stmt_vec_info stmt_info = dr_info->stmt; |
| vec_base_alignments *base_alignments = &vinfo->base_alignments; |
| loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo); |
| class loop *loop = NULL; |
| tree ref = DR_REF (dr_info->dr); |
| tree vectype = STMT_VINFO_VECTYPE (stmt_info); |
| |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "vect_compute_data_ref_alignment:\n"); |
| |
| if (loop_vinfo) |
| loop = LOOP_VINFO_LOOP (loop_vinfo); |
| |
| /* Initialize misalignment to unknown. */ |
| SET_DR_MISALIGNMENT (dr_info, DR_MISALIGNMENT_UNKNOWN); |
| |
| if (STMT_VINFO_GATHER_SCATTER_P (stmt_info)) |
| return; |
| |
| innermost_loop_behavior *drb = vect_dr_behavior (vinfo, dr_info); |
| bool step_preserves_misalignment_p; |
| |
| poly_uint64 vector_alignment |
| = exact_div (vect_calculate_target_alignment (dr_info), BITS_PER_UNIT); |
| DR_TARGET_ALIGNMENT (dr_info) = vector_alignment; |
| |
| /* If the main loop has peeled for alignment we have no way of knowing |
| whether the data accesses in the epilogues are aligned. We can't at |
| compile time answer the question whether we have entered the main loop or |
| not. Fixes PR 92351. */ |
| if (loop_vinfo) |
| { |
| loop_vec_info orig_loop_vinfo = LOOP_VINFO_ORIG_LOOP_INFO (loop_vinfo); |
| if (orig_loop_vinfo |
| && LOOP_VINFO_PEELING_FOR_ALIGNMENT (orig_loop_vinfo) != 0) |
| return; |
| } |
| |
| unsigned HOST_WIDE_INT vect_align_c; |
| if (!vector_alignment.is_constant (&vect_align_c)) |
| return; |
| |
| /* No step for BB vectorization. */ |
| if (!loop) |
| { |
| gcc_assert (integer_zerop (drb->step)); |
| step_preserves_misalignment_p = true; |
| } |
| |
| /* In case the dataref is in an inner-loop of the loop that is being |
| vectorized (LOOP), we use the base and misalignment information |
| relative to the outer-loop (LOOP). This is ok only if the misalignment |
| stays the same throughout the execution of the inner-loop, which is why |
| we have to check that the stride of the dataref in the inner-loop evenly |
| divides by the vector alignment. */ |
| else if (nested_in_vect_loop_p (loop, stmt_info)) |
| { |
| step_preserves_misalignment_p |
| = (DR_STEP_ALIGNMENT (dr_info->dr) % vect_align_c) == 0; |
| |
| if (dump_enabled_p ()) |
| { |
| if (step_preserves_misalignment_p) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "inner step divides the vector alignment.\n"); |
| else |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "inner step doesn't divide the vector" |
| " alignment.\n"); |
| } |
| } |
| |
| /* Similarly we can only use base and misalignment information relative to |
| an innermost loop if the misalignment stays the same throughout the |
| execution of the loop. As above, this is the case if the stride of |
| the dataref evenly divides by the alignment. */ |
| else |
| { |
| poly_uint64 vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo); |
| step_preserves_misalignment_p |
| = multiple_p (DR_STEP_ALIGNMENT (dr_info->dr) * vf, vect_align_c); |
| |
| if (!step_preserves_misalignment_p && dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "step doesn't divide the vector alignment.\n"); |
| } |
| |
| unsigned int base_alignment = drb->base_alignment; |
| unsigned int base_misalignment = drb->base_misalignment; |
| |
| /* Calculate the maximum of the pooled base address alignment and the |
| alignment that we can compute for DR itself. */ |
| innermost_loop_behavior **entry = base_alignments->get (drb->base_address); |
| if (entry && base_alignment < (*entry)->base_alignment) |
| { |
| base_alignment = (*entry)->base_alignment; |
| base_misalignment = (*entry)->base_misalignment; |
| } |
| |
| if (drb->offset_alignment < vect_align_c |
| || !step_preserves_misalignment_p |
| /* We need to know whether the step wrt the vectorized loop is |
| negative when computing the starting misalignment below. */ |
| || TREE_CODE (drb->step) != INTEGER_CST) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Unknown alignment for access: %T\n", ref); |
| return; |
| } |
| |
| if (base_alignment < vect_align_c) |
| { |
| unsigned int max_alignment; |
| tree base = get_base_for_alignment (drb->base_address, &max_alignment); |
| if (max_alignment < vect_align_c |
| || !vect_can_force_dr_alignment_p (base, |
| vect_align_c * BITS_PER_UNIT)) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "can't force alignment of ref: %T\n", ref); |
| return; |
| } |
| |
| /* Force the alignment of the decl. |
| NOTE: This is the only change to the code we make during |
| the analysis phase, before deciding to vectorize the loop. */ |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "force alignment of %T\n", ref); |
| |
| dr_info->base_decl = base; |
| dr_info->base_misaligned = true; |
| base_misalignment = 0; |
| } |
| poly_int64 misalignment |
| = base_misalignment + wi::to_poly_offset (drb->init).force_shwi (); |
| |
| /* If this is a backward running DR then first access in the larger |
| vectype actually is N-1 elements before the address in the DR. |
| Adjust misalign accordingly. */ |
| if (tree_int_cst_sgn (drb->step) < 0) |
| /* PLUS because STEP is negative. */ |
| misalignment += ((TYPE_VECTOR_SUBPARTS (vectype) - 1) |
| * -TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (vectype)))); |
| |
| unsigned int const_misalignment; |
| if (!known_misalignment (misalignment, vect_align_c, &const_misalignment)) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Non-constant misalignment for access: %T\n", ref); |
| return; |
| } |
| |
| SET_DR_MISALIGNMENT (dr_info, const_misalignment); |
| |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "misalign = %d bytes of ref %T\n", |
| DR_MISALIGNMENT (dr_info), ref); |
| |
| return; |
| } |
| |
| /* Return whether DR_INFO, which is related to DR_PEEL_INFO in |
| that it only differs in DR_INIT, is aligned if DR_PEEL_INFO |
| is made aligned via peeling. */ |
| |
| static bool |
| vect_dr_aligned_if_related_peeled_dr_is (dr_vec_info *dr_info, |
| dr_vec_info *dr_peel_info) |
| { |
| if (multiple_p (DR_TARGET_ALIGNMENT (dr_peel_info), |
| DR_TARGET_ALIGNMENT (dr_info))) |
| { |
| poly_offset_int diff |
| = (wi::to_poly_offset (DR_INIT (dr_peel_info->dr)) |
| - wi::to_poly_offset (DR_INIT (dr_info->dr))); |
| if (known_eq (diff, 0) |
| || multiple_p (diff, DR_TARGET_ALIGNMENT (dr_info))) |
| return true; |
| } |
| return false; |
| } |
| |
| /* Return whether DR_INFO is aligned if DR_PEEL_INFO is made |
| aligned via peeling. */ |
| |
| static bool |
| vect_dr_aligned_if_peeled_dr_is (dr_vec_info *dr_info, |
| dr_vec_info *dr_peel_info) |
| { |
| if (!operand_equal_p (DR_BASE_ADDRESS (dr_info->dr), |
| DR_BASE_ADDRESS (dr_peel_info->dr), 0) |
| || !operand_equal_p (DR_OFFSET (dr_info->dr), |
| DR_OFFSET (dr_peel_info->dr), 0) |
| || !operand_equal_p (DR_STEP (dr_info->dr), |
| DR_STEP (dr_peel_info->dr), 0)) |
| return false; |
| |
| return vect_dr_aligned_if_related_peeled_dr_is (dr_info, dr_peel_info); |
| } |
| |
| /* Function vect_update_misalignment_for_peel. |
| Sets DR_INFO's misalignment |
| - to 0 if it has the same alignment as DR_PEEL_INFO, |
| - to the misalignment computed using NPEEL if DR_INFO's salignment is known, |
| - to -1 (unknown) otherwise. |
| |
| DR_INFO - the data reference whose misalignment is to be adjusted. |
| DR_PEEL_INFO - the data reference whose misalignment is being made |
| zero in the vector loop by the peel. |
| NPEEL - the number of iterations in the peel loop if the misalignment |
| of DR_PEEL_INFO is known at compile time. */ |
| |
| static void |
| vect_update_misalignment_for_peel (dr_vec_info *dr_info, |
| dr_vec_info *dr_peel_info, int npeel) |
| { |
| /* If dr_info is aligned of dr_peel_info is, then mark it so. */ |
| if (vect_dr_aligned_if_peeled_dr_is (dr_info, dr_peel_info)) |
| { |
| SET_DR_MISALIGNMENT (dr_info, 0); |
| return; |
| } |
| |
| unsigned HOST_WIDE_INT alignment; |
| if (DR_TARGET_ALIGNMENT (dr_info).is_constant (&alignment) |
| && known_alignment_for_access_p (dr_info) |
| && known_alignment_for_access_p (dr_peel_info)) |
| { |
| int misal = DR_MISALIGNMENT (dr_info); |
| misal += npeel * TREE_INT_CST_LOW (DR_STEP (dr_info->dr)); |
| misal &= alignment - 1; |
| SET_DR_MISALIGNMENT (dr_info, misal); |
| return; |
| } |
| |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, "Setting misalignment " \ |
| "to unknown (-1).\n"); |
| SET_DR_MISALIGNMENT (dr_info, DR_MISALIGNMENT_UNKNOWN); |
| } |
| |
| /* Return true if alignment is relevant for DR_INFO. */ |
| |
| static bool |
| vect_relevant_for_alignment_p (dr_vec_info *dr_info) |
| { |
| stmt_vec_info stmt_info = dr_info->stmt; |
| |
| if (!STMT_VINFO_RELEVANT_P (stmt_info)) |
| return false; |
| |
| /* For interleaving, only the alignment of the first access matters. */ |
| if (STMT_VINFO_GROUPED_ACCESS (stmt_info) |
| && DR_GROUP_FIRST_ELEMENT (stmt_info) != stmt_info) |
| return false; |
| |
| /* Scatter-gather and invariant accesses continue to address individual |
| scalars, so vector-level alignment is irrelevant. */ |
| if (STMT_VINFO_GATHER_SCATTER_P (stmt_info) |
| || integer_zerop (DR_STEP (dr_info->dr))) |
| return false; |
| |
| /* Strided accesses perform only component accesses, alignment is |
| irrelevant for them. */ |
| if (STMT_VINFO_STRIDED_P (stmt_info) |
| && !STMT_VINFO_GROUPED_ACCESS (stmt_info)) |
| return false; |
| |
| return true; |
| } |
| |
| /* Given an memory reference EXP return whether its alignment is less |
| than its size. */ |
| |
| static bool |
| not_size_aligned (tree exp) |
| { |
| if (!tree_fits_uhwi_p (TYPE_SIZE (TREE_TYPE (exp)))) |
| return true; |
| |
| return (tree_to_uhwi (TYPE_SIZE (TREE_TYPE (exp))) |
| > get_object_alignment (exp)); |
| } |
| |
| /* Function vector_alignment_reachable_p |
| |
| Return true if vector alignment for DR_INFO is reachable by peeling |
| a few loop iterations. Return false otherwise. */ |
| |
| static bool |
| vector_alignment_reachable_p (dr_vec_info *dr_info) |
| { |
| stmt_vec_info stmt_info = dr_info->stmt; |
| tree vectype = STMT_VINFO_VECTYPE (stmt_info); |
| |
| if (STMT_VINFO_GROUPED_ACCESS (stmt_info)) |
| { |
| /* For interleaved access we peel only if number of iterations in |
| the prolog loop ({VF - misalignment}), is a multiple of the |
| number of the interleaved accesses. */ |
| int elem_size, mis_in_elements; |
| |
| /* FORNOW: handle only known alignment. */ |
| if (!known_alignment_for_access_p (dr_info)) |
| return false; |
| |
| poly_uint64 nelements = TYPE_VECTOR_SUBPARTS (vectype); |
| poly_uint64 vector_size = GET_MODE_SIZE (TYPE_MODE (vectype)); |
| elem_size = vector_element_size (vector_size, nelements); |
| mis_in_elements = DR_MISALIGNMENT (dr_info) / elem_size; |
| |
| if (!multiple_p (nelements - mis_in_elements, DR_GROUP_SIZE (stmt_info))) |
| return false; |
| } |
| |
| /* If misalignment is known at the compile time then allow peeling |
| only if natural alignment is reachable through peeling. */ |
| if (known_alignment_for_access_p (dr_info) && !aligned_access_p (dr_info)) |
| { |
| HOST_WIDE_INT elmsize = |
| int_cst_value (TYPE_SIZE_UNIT (TREE_TYPE (vectype))); |
| if (dump_enabled_p ()) |
| { |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "data size = %wd. misalignment = %d.\n", elmsize, |
| DR_MISALIGNMENT (dr_info)); |
| } |
| if (DR_MISALIGNMENT (dr_info) % elmsize) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "data size does not divide the misalignment.\n"); |
| return false; |
| } |
| } |
| |
| if (!known_alignment_for_access_p (dr_info)) |
| { |
| tree type = TREE_TYPE (DR_REF (dr_info->dr)); |
| bool is_packed = not_size_aligned (DR_REF (dr_info->dr)); |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "Unknown misalignment, %snaturally aligned\n", |
| is_packed ? "not " : ""); |
| return targetm.vectorize.vector_alignment_reachable (type, is_packed); |
| } |
| |
| return true; |
| } |
| |
| |
| /* Calculate the cost of the memory access represented by DR_INFO. */ |
| |
| static void |
| vect_get_data_access_cost (vec_info *vinfo, dr_vec_info *dr_info, |
| unsigned int *inside_cost, |
| unsigned int *outside_cost, |
| stmt_vector_for_cost *body_cost_vec, |
| stmt_vector_for_cost *prologue_cost_vec) |
| { |
| stmt_vec_info stmt_info = dr_info->stmt; |
| loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo); |
| int ncopies; |
| |
| if (PURE_SLP_STMT (stmt_info)) |
| ncopies = 1; |
| else |
| ncopies = vect_get_num_copies (loop_vinfo, STMT_VINFO_VECTYPE (stmt_info)); |
| |
| if (DR_IS_READ (dr_info->dr)) |
| vect_get_load_cost (vinfo, stmt_info, ncopies, true, inside_cost, |
| outside_cost, prologue_cost_vec, body_cost_vec, false); |
| else |
| vect_get_store_cost (vinfo,stmt_info, ncopies, inside_cost, body_cost_vec); |
| |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "vect_get_data_access_cost: inside_cost = %d, " |
| "outside_cost = %d.\n", *inside_cost, *outside_cost); |
| } |
| |
| |
| typedef struct _vect_peel_info |
| { |
| dr_vec_info *dr_info; |
| int npeel; |
| unsigned int count; |
| } *vect_peel_info; |
| |
| typedef struct _vect_peel_extended_info |
| { |
| vec_info *vinfo; |
| struct _vect_peel_info peel_info; |
| unsigned int inside_cost; |
| unsigned int outside_cost; |
| } *vect_peel_extended_info; |
| |
| |
| /* Peeling hashtable helpers. */ |
| |
| struct peel_info_hasher : free_ptr_hash <_vect_peel_info> |
| { |
| static inline hashval_t hash (const _vect_peel_info *); |
| static inline bool equal (const _vect_peel_info *, const _vect_peel_info *); |
| }; |
| |
| inline hashval_t |
| peel_info_hasher::hash (const _vect_peel_info *peel_info) |
| { |
| return (hashval_t) peel_info->npeel; |
| } |
| |
| inline bool |
| peel_info_hasher::equal (const _vect_peel_info *a, const _vect_peel_info *b) |
| { |
| return (a->npeel == b->npeel); |
| } |
| |
| |
| /* Insert DR_INFO into peeling hash table with NPEEL as key. */ |
| |
| static void |
| vect_peeling_hash_insert (hash_table<peel_info_hasher> *peeling_htab, |
| loop_vec_info loop_vinfo, dr_vec_info *dr_info, |
| int npeel) |
| { |
| struct _vect_peel_info elem, *slot; |
| _vect_peel_info **new_slot; |
| bool supportable_dr_alignment |
| = vect_supportable_dr_alignment (loop_vinfo, dr_info, true); |
| |
| elem.npeel = npeel; |
| slot = peeling_htab->find (&elem); |
| if (slot) |
| slot->count++; |
| else |
| { |
| slot = XNEW (struct _vect_peel_info); |
| slot->npeel = npeel; |
| slot->dr_info = dr_info; |
| slot->count = 1; |
| new_slot = peeling_htab->find_slot (slot, INSERT); |
| *new_slot = slot; |
| } |
| |
| if (!supportable_dr_alignment |
| && unlimited_cost_model (LOOP_VINFO_LOOP (loop_vinfo))) |
| slot->count += VECT_MAX_COST; |
| } |
| |
| |
| /* Traverse peeling hash table to find peeling option that aligns maximum |
| number of data accesses. */ |
| |
| int |
| vect_peeling_hash_get_most_frequent (_vect_peel_info **slot, |
| _vect_peel_extended_info *max) |
| { |
| vect_peel_info elem = *slot; |
| |
| if (elem->count > max->peel_info.count |
| || (elem->count == max->peel_info.count |
| && max->peel_info.npeel > elem->npeel)) |
| { |
| max->peel_info.npeel = elem->npeel; |
| max->peel_info.count = elem->count; |
| max->peel_info.dr_info = elem->dr_info; |
| } |
| |
| return 1; |
| } |
| |
| /* Get the costs of peeling NPEEL iterations for LOOP_VINFO, checking |
| data access costs for all data refs. If UNKNOWN_MISALIGNMENT is true, |
| we assume DR0_INFO's misalignment will be zero after peeling. */ |
| |
| static void |
| vect_get_peeling_costs_all_drs (loop_vec_info loop_vinfo, |
| dr_vec_info *dr0_info, |
| unsigned int *inside_cost, |
| unsigned int *outside_cost, |
| stmt_vector_for_cost *body_cost_vec, |
| stmt_vector_for_cost *prologue_cost_vec, |
| unsigned int npeel, |
| bool unknown_misalignment) |
| { |
| vec<data_reference_p> datarefs = LOOP_VINFO_DATAREFS (loop_vinfo); |
| unsigned i; |
| data_reference *dr; |
| |
| FOR_EACH_VEC_ELT (datarefs, i, dr) |
| { |
| dr_vec_info *dr_info = loop_vinfo->lookup_dr (dr); |
| if (!vect_relevant_for_alignment_p (dr_info)) |
| continue; |
| |
| int save_misalignment; |
| save_misalignment = DR_MISALIGNMENT (dr_info); |
| if (npeel == 0) |
| ; |
| else if (unknown_misalignment && dr_info == dr0_info) |
| SET_DR_MISALIGNMENT (dr_info, 0); |
| else |
| vect_update_misalignment_for_peel (dr_info, dr0_info, npeel); |
| vect_get_data_access_cost (loop_vinfo, dr_info, inside_cost, outside_cost, |
| body_cost_vec, prologue_cost_vec); |
| SET_DR_MISALIGNMENT (dr_info, save_misalignment); |
| } |
| } |
| |
| /* Traverse peeling hash table and calculate cost for each peeling option. |
| Find the one with the lowest cost. */ |
| |
| int |
| vect_peeling_hash_get_lowest_cost (_vect_peel_info **slot, |
| _vect_peel_extended_info *min) |
| { |
| vect_peel_info elem = *slot; |
| int dummy; |
| unsigned int inside_cost = 0, outside_cost = 0; |
| loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (min->vinfo); |
| stmt_vector_for_cost prologue_cost_vec, body_cost_vec, |
| epilogue_cost_vec; |
| |
| prologue_cost_vec.create (2); |
| body_cost_vec.create (2); |
| epilogue_cost_vec.create (2); |
| |
| vect_get_peeling_costs_all_drs (loop_vinfo, elem->dr_info, &inside_cost, |
| &outside_cost, &body_cost_vec, |
| &prologue_cost_vec, elem->npeel, false); |
| |
| body_cost_vec.release (); |
| |
| outside_cost += vect_get_known_peeling_cost |
| (loop_vinfo, elem->npeel, &dummy, |
| &LOOP_VINFO_SCALAR_ITERATION_COST (loop_vinfo), |
| &prologue_cost_vec, &epilogue_cost_vec); |
| |
| /* Prologue and epilogue costs are added to the target model later. |
| These costs depend only on the scalar iteration cost, the |
| number of peeling iterations finally chosen, and the number of |
| misaligned statements. So discard the information found here. */ |
| prologue_cost_vec.release (); |
| epilogue_cost_vec.release (); |
| |
| if (inside_cost < min->inside_cost |
| || (inside_cost == min->inside_cost |
| && outside_cost < min->outside_cost)) |
| { |
| min->inside_cost = inside_cost; |
| min->outside_cost = outside_cost; |
| min->peel_info.dr_info = elem->dr_info; |
| min->peel_info.npeel = elem->npeel; |
| min->peel_info.count = elem->count; |
| } |
| |
| return 1; |
| } |
| |
| |
| /* Choose best peeling option by traversing peeling hash table and either |
| choosing an option with the lowest cost (if cost model is enabled) or the |
| option that aligns as many accesses as possible. */ |
| |
| static struct _vect_peel_extended_info |
| vect_peeling_hash_choose_best_peeling (hash_table<peel_info_hasher> *peeling_htab, |
| loop_vec_info loop_vinfo) |
| { |
| struct _vect_peel_extended_info res; |
| |
| res.peel_info.dr_info = NULL; |
| res.vinfo = loop_vinfo; |
| |
| if (!unlimited_cost_model (LOOP_VINFO_LOOP (loop_vinfo))) |
| { |
| res.inside_cost = INT_MAX; |
| res.outside_cost = INT_MAX; |
| peeling_htab->traverse <_vect_peel_extended_info *, |
| vect_peeling_hash_get_lowest_cost> (&res); |
| } |
| else |
| { |
| res.peel_info.count = 0; |
| peeling_htab->traverse <_vect_peel_extended_info *, |
| vect_peeling_hash_get_most_frequent> (&res); |
| res.inside_cost = 0; |
| res.outside_cost = 0; |
| } |
| |
| return res; |
| } |
| |
| /* Return true if the new peeling NPEEL is supported. */ |
| |
| static bool |
| vect_peeling_supportable (loop_vec_info loop_vinfo, dr_vec_info *dr0_info, |
| unsigned npeel) |
| { |
| unsigned i; |
| struct data_reference *dr = NULL; |
| vec<data_reference_p> datarefs = LOOP_VINFO_DATAREFS (loop_vinfo); |
| enum dr_alignment_support supportable_dr_alignment; |
| |
| /* Ensure that all data refs can be vectorized after the peel. */ |
| FOR_EACH_VEC_ELT (datarefs, i, dr) |
| { |
| int save_misalignment; |
| |
| if (dr == dr0_info->dr) |
| continue; |
| |
| dr_vec_info *dr_info = loop_vinfo->lookup_dr (dr); |
| if (!vect_relevant_for_alignment_p (dr_info)) |
| continue; |
| |
| save_misalignment = DR_MISALIGNMENT (dr_info); |
| vect_update_misalignment_for_peel (dr_info, dr0_info, npeel); |
| supportable_dr_alignment |
| = vect_supportable_dr_alignment (loop_vinfo, dr_info, false); |
| SET_DR_MISALIGNMENT (dr_info, save_misalignment); |
| |
| if (!supportable_dr_alignment) |
| return false; |
| } |
| |
| return true; |
| } |
| |
| /* Compare two data-references DRA and DRB to group them into chunks |
| with related alignment. */ |
| |
| static int |
| dr_align_group_sort_cmp (const void *dra_, const void *drb_) |
| { |
| data_reference_p dra = *(data_reference_p *)const_cast<void *>(dra_); |
| data_reference_p drb = *(data_reference_p *)const_cast<void *>(drb_); |
| int cmp; |
| |
| /* Stabilize sort. */ |
| if (dra == drb) |
| return 0; |
| |
| /* Ordering of DRs according to base. */ |
| cmp = data_ref_compare_tree (DR_BASE_ADDRESS (dra), |
| DR_BASE_ADDRESS (drb)); |
| if (cmp != 0) |
| return cmp; |
| |
| /* And according to DR_OFFSET. */ |
| cmp = data_ref_compare_tree (DR_OFFSET (dra), DR_OFFSET (drb)); |
| if (cmp != 0) |
| return cmp; |
| |
| /* And after step. */ |
| cmp = data_ref_compare_tree (DR_STEP (dra), DR_STEP (drb)); |
| if (cmp != 0) |
| return cmp; |
| |
| /* Then sort after DR_INIT. In case of identical DRs sort after stmt UID. */ |
| cmp = data_ref_compare_tree (DR_INIT (dra), DR_INIT (drb)); |
| if (cmp == 0) |
| return gimple_uid (DR_STMT (dra)) < gimple_uid (DR_STMT (drb)) ? -1 : 1; |
| return cmp; |
| } |
| |
| /* Function vect_enhance_data_refs_alignment |
| |
| This pass will use loop versioning and loop peeling in order to enhance |
| the alignment of data references in the loop. |
| |
| FOR NOW: we assume that whatever versioning/peeling takes place, only the |
| original loop is to be vectorized. Any other loops that are created by |
| the transformations performed in this pass - are not supposed to be |
| vectorized. This restriction will be relaxed. |
| |
| This pass will require a cost model to guide it whether to apply peeling |
| or versioning or a combination of the two. For example, the scheme that |
| intel uses when given a loop with several memory accesses, is as follows: |
| choose one memory access ('p') which alignment you want to force by doing |
| peeling. Then, either (1) generate a loop in which 'p' is aligned and all |
| other accesses are not necessarily aligned, or (2) use loop versioning to |
| generate one loop in which all accesses are aligned, and another loop in |
| which only 'p' is necessarily aligned. |
| |
| ("Automatic Intra-Register Vectorization for the Intel Architecture", |
| Aart J.C. Bik, Milind Girkar, Paul M. Grey and Ximmin Tian, International |
| Journal of Parallel Programming, Vol. 30, No. 2, April 2002.) |
| |
| Devising a cost model is the most critical aspect of this work. It will |
| guide us on which access to peel for, whether to use loop versioning, how |
| many versions to create, etc. The cost model will probably consist of |
| generic considerations as well as target specific considerations (on |
| powerpc for example, misaligned stores are more painful than misaligned |
| loads). |
| |
| Here are the general steps involved in alignment enhancements: |
| |
| -- original loop, before alignment analysis: |
| for (i=0; i<N; i++){ |
| x = q[i]; # DR_MISALIGNMENT(q) = unknown |
| p[i] = y; # DR_MISALIGNMENT(p) = unknown |
| } |
| |
| -- After vect_compute_data_refs_alignment: |
| for (i=0; i<N; i++){ |
| x = q[i]; # DR_MISALIGNMENT(q) = 3 |
| p[i] = y; # DR_MISALIGNMENT(p) = unknown |
| } |
| |
| -- Possibility 1: we do loop versioning: |
| if (p is aligned) { |
| for (i=0; i<N; i++){ # loop 1A |
| x = q[i]; # DR_MISALIGNMENT(q) = 3 |
| p[i] = y; # DR_MISALIGNMENT(p) = 0 |
| } |
| } |
| else { |
| for (i=0; i<N; i++){ # loop 1B |
| x = q[i]; # DR_MISALIGNMENT(q) = 3 |
| p[i] = y; # DR_MISALIGNMENT(p) = unaligned |
| } |
| } |
| |
| -- Possibility 2: we do loop peeling: |
| for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized). |
| x = q[i]; |
| p[i] = y; |
| } |
| for (i = 3; i < N; i++){ # loop 2A |
| x = q[i]; # DR_MISALIGNMENT(q) = 0 |
| p[i] = y; # DR_MISALIGNMENT(p) = unknown |
| } |
| |
| -- Possibility 3: combination of loop peeling and versioning: |
| for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized). |
| x = q[i]; |
| p[i] = y; |
| } |
| if (p is aligned) { |
| for (i = 3; i<N; i++){ # loop 3A |
| x = q[i]; # DR_MISALIGNMENT(q) = 0 |
| p[i] = y; # DR_MISALIGNMENT(p) = 0 |
| } |
| } |
| else { |
| for (i = 3; i<N; i++){ # loop 3B |
| x = q[i]; # DR_MISALIGNMENT(q) = 0 |
| p[i] = y; # DR_MISALIGNMENT(p) = unaligned |
| } |
| } |
| |
| These loops are later passed to loop_transform to be vectorized. The |
| vectorizer will use the alignment information to guide the transformation |
| (whether to generate regular loads/stores, or with special handling for |
| misalignment). */ |
| |
| opt_result |
| vect_enhance_data_refs_alignment (loop_vec_info loop_vinfo) |
| { |
| class loop *loop = LOOP_VINFO_LOOP (loop_vinfo); |
| enum dr_alignment_support supportable_dr_alignment; |
| dr_vec_info *first_store = NULL; |
| dr_vec_info *dr0_info = NULL; |
| struct data_reference *dr; |
| unsigned int i; |
| bool do_peeling = false; |
| bool do_versioning = false; |
| unsigned int npeel = 0; |
| bool one_misalignment_known = false; |
| bool one_misalignment_unknown = false; |
| bool one_dr_unsupportable = false; |
| dr_vec_info *unsupportable_dr_info = NULL; |
| unsigned int mis, dr0_same_align_drs = 0, first_store_same_align_drs = 0; |
| hash_table<peel_info_hasher> peeling_htab (1); |
| |
| DUMP_VECT_SCOPE ("vect_enhance_data_refs_alignment"); |
| |
| /* Reset data so we can safely be called multiple times. */ |
| LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo).truncate (0); |
| LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) = 0; |
| |
| if (LOOP_VINFO_DATAREFS (loop_vinfo).is_empty ()) |
| return opt_result::success (); |
| |
| /* Sort the vector of datarefs so DRs that have the same or dependent |
| alignment are next to each other. */ |
| auto_vec<data_reference_p> datarefs |
| = LOOP_VINFO_DATAREFS (loop_vinfo).copy (); |
| datarefs.qsort (dr_align_group_sort_cmp); |
| |
| /* Compute the number of DRs that become aligned when we peel |
| a dataref so it becomes aligned. */ |
| auto_vec<unsigned> n_same_align_refs (datarefs.length ()); |
| n_same_align_refs.quick_grow_cleared (datarefs.length ()); |
| unsigned i0; |
| for (i0 = 0; i0 < datarefs.length (); ++i0) |
| if (DR_BASE_ADDRESS (datarefs[i0])) |
| break; |
| for (i = i0 + 1; i <= datarefs.length (); ++i) |
| { |
| if (i == datarefs.length () |
| || !operand_equal_p (DR_BASE_ADDRESS (datarefs[i0]), |
| DR_BASE_ADDRESS (datarefs[i]), 0) |
| || !operand_equal_p (DR_OFFSET (datarefs[i0]), |
| DR_OFFSET (datarefs[i]), 0) |
| || !operand_equal_p (DR_STEP (datarefs[i0]), |
| DR_STEP (datarefs[i]), 0)) |
| { |
| /* The subgroup [i0, i-1] now only differs in DR_INIT and |
| possibly DR_TARGET_ALIGNMENT. Still the whole subgroup |
| will get known misalignment if we align one of the refs |
| with the largest DR_TARGET_ALIGNMENT. */ |
| for (unsigned j = i0; j < i; ++j) |
| { |
| dr_vec_info *dr_infoj = loop_vinfo->lookup_dr (datarefs[j]); |
| for (unsigned k = i0; k < i; ++k) |
| { |
| if (k == j) |
| continue; |
| dr_vec_info *dr_infok = loop_vinfo->lookup_dr (datarefs[k]); |
| if (vect_dr_aligned_if_related_peeled_dr_is (dr_infok, |
| dr_infoj)) |
| n_same_align_refs[j]++; |
| } |
| } |
| i0 = i; |
| } |
| } |
| |
| /* While cost model enhancements are expected in the future, the high level |
| view of the code at this time is as follows: |
| |
| A) If there is a misaligned access then see if peeling to align |
| this access can make all data references satisfy |
| vect_supportable_dr_alignment. If so, update data structures |
| as needed and return true. |
| |
| B) If peeling wasn't possible and there is a data reference with an |
| unknown misalignment that does not satisfy vect_supportable_dr_alignment |
| then see if loop versioning checks can be used to make all data |
| references satisfy vect_supportable_dr_alignment. If so, update |
| data structures as needed and return true. |
| |
| C) If neither peeling nor versioning were successful then return false if |
| any data reference does not satisfy vect_supportable_dr_alignment. |
| |
| D) Return true (all data references satisfy vect_supportable_dr_alignment). |
| |
| Note, Possibility 3 above (which is peeling and versioning together) is not |
| being done at this time. */ |
| |
| /* (1) Peeling to force alignment. */ |
| |
| /* (1.1) Decide whether to perform peeling, and how many iterations to peel: |
| Considerations: |
| + How many accesses will become aligned due to the peeling |
| - How many accesses will become unaligned due to the peeling, |
| and the cost of misaligned accesses. |
| - The cost of peeling (the extra runtime checks, the increase |
| in code size). */ |
| |
| FOR_EACH_VEC_ELT (datarefs, i, dr) |
| { |
| dr_vec_info *dr_info = loop_vinfo->lookup_dr (dr); |
| if (!vect_relevant_for_alignment_p (dr_info)) |
| continue; |
| |
| stmt_vec_info stmt_info = dr_info->stmt; |
| supportable_dr_alignment |
| = vect_supportable_dr_alignment (loop_vinfo, dr_info, true); |
| do_peeling = vector_alignment_reachable_p (dr_info); |
| if (do_peeling) |
| { |
| if (known_alignment_for_access_p (dr_info)) |
| { |
| unsigned int npeel_tmp = 0; |
| bool negative = tree_int_cst_compare (DR_STEP (dr), |
| size_zero_node) < 0; |
| |
| /* If known_alignment_for_access_p then we have set |
| DR_MISALIGNMENT which is only done if we know it at compiler |
| time, so it is safe to assume target alignment is constant. |
| */ |
| unsigned int target_align = |
| DR_TARGET_ALIGNMENT (dr_info).to_constant (); |
| unsigned int dr_size = vect_get_scalar_dr_size (dr_info); |
| mis = (negative |
| ? DR_MISALIGNMENT (dr_info) |
| : -DR_MISALIGNMENT (dr_info)); |
| if (DR_MISALIGNMENT (dr_info) != 0) |
| npeel_tmp = (mis & (target_align - 1)) / dr_size; |
| |
| /* For multiple types, it is possible that the bigger type access |
| will have more than one peeling option. E.g., a loop with two |
| types: one of size (vector size / 4), and the other one of |
| size (vector size / 8). Vectorization factor will 8. If both |
| accesses are misaligned by 3, the first one needs one scalar |
| iteration to be aligned, and the second one needs 5. But the |
| first one will be aligned also by peeling 5 scalar |
| iterations, and in that case both accesses will be aligned. |
| Hence, except for the immediate peeling amount, we also want |
| to try to add full vector size, while we don't exceed |
| vectorization factor. |
| We do this automatically for cost model, since we calculate |
| cost for every peeling option. */ |
| poly_uint64 nscalars = npeel_tmp; |
| if (unlimited_cost_model (LOOP_VINFO_LOOP (loop_vinfo))) |
| { |
| poly_uint64 vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo); |
| nscalars = (STMT_SLP_TYPE (stmt_info) |
| ? vf * DR_GROUP_SIZE (stmt_info) : vf); |
| } |
| |
| /* Save info about DR in the hash table. Also include peeling |
| amounts according to the explanation above. */ |
| while (known_le (npeel_tmp, nscalars)) |
| { |
| vect_peeling_hash_insert (&peeling_htab, loop_vinfo, |
| dr_info, npeel_tmp); |
| npeel_tmp += MAX (1, target_align / dr_size); |
| } |
| |
| one_misalignment_known = true; |
| } |
| else |
| { |
| /* If we don't know any misalignment values, we prefer |
| peeling for data-ref that has the maximum number of data-refs |
| with the same alignment, unless the target prefers to align |
| stores over load. */ |
| unsigned same_align_drs = n_same_align_refs[i]; |
| if (!dr0_info |
| || dr0_same_align_drs < same_align_drs) |
| { |
| dr0_same_align_drs = same_align_drs; |
| dr0_info = dr_info; |
| } |
| /* For data-refs with the same number of related |
| accesses prefer the one where the misalign |
| computation will be invariant in the outermost loop. */ |
| else if (dr0_same_align_drs == same_align_drs) |
| { |
| class loop *ivloop0, *ivloop; |
| ivloop0 = outermost_invariant_loop_for_expr |
| (loop, DR_BASE_ADDRESS (dr0_info->dr)); |
| ivloop = outermost_invariant_loop_for_expr |
| (loop, DR_BASE_ADDRESS (dr)); |
| if ((ivloop && !ivloop0) |
| || (ivloop && ivloop0 |
| && flow_loop_nested_p (ivloop, ivloop0))) |
| dr0_info = dr_info; |
| } |
| |
| one_misalignment_unknown = true; |
| |
| /* Check for data refs with unsupportable alignment that |
| can be peeled. */ |
| if (!supportable_dr_alignment) |
| { |
| one_dr_unsupportable = true; |
| unsupportable_dr_info = dr_info; |
| } |
| |
| if (!first_store && DR_IS_WRITE (dr)) |
| { |
| first_store = dr_info; |
| first_store_same_align_drs = same_align_drs; |
| } |
| } |
| } |
| else |
| { |
| if (!aligned_access_p (dr_info)) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "vector alignment may not be reachable\n"); |
| break; |
| } |
| } |
| } |
| |
| /* Check if we can possibly peel the loop. */ |
| if (!vect_can_advance_ivs_p (loop_vinfo) |
| || !slpeel_can_duplicate_loop_p (loop, single_exit (loop)) |
| || loop->inner) |
| do_peeling = false; |
| |
| struct _vect_peel_extended_info peel_for_known_alignment; |
| struct _vect_peel_extended_info peel_for_unknown_alignment; |
| struct _vect_peel_extended_info best_peel; |
| |
| peel_for_unknown_alignment.inside_cost = INT_MAX; |
| peel_for_unknown_alignment.outside_cost = INT_MAX; |
| peel_for_unknown_alignment.peel_info.count = 0; |
| |
| if (do_peeling |
| && one_misalignment_unknown) |
| { |
| /* Check if the target requires to prefer stores over loads, i.e., if |
| misaligned stores are more expensive than misaligned loads (taking |
| drs with same alignment into account). */ |
| unsigned int load_inside_cost = 0; |
| unsigned int load_outside_cost = 0; |
| unsigned int store_inside_cost = 0; |
| unsigned int store_outside_cost = 0; |
| unsigned int estimated_npeels = vect_vf_for_cost (loop_vinfo) / 2; |
| |
| stmt_vector_for_cost dummy; |
| dummy.create (2); |
| vect_get_peeling_costs_all_drs (loop_vinfo, dr0_info, |
| &load_inside_cost, |
| &load_outside_cost, |
| &dummy, &dummy, estimated_npeels, true); |
| dummy.release (); |
| |
| if (first_store) |
| { |
| dummy.create (2); |
| vect_get_peeling_costs_all_drs (loop_vinfo, first_store, |
| &store_inside_cost, |
| &store_outside_cost, |
| &dummy, &dummy, |
| estimated_npeels, true); |
| dummy.release (); |
| } |
| else |
| { |
| store_inside_cost = INT_MAX; |
| store_outside_cost = INT_MAX; |
| } |
| |
| if (load_inside_cost > store_inside_cost |
| || (load_inside_cost == store_inside_cost |
| && load_outside_cost > store_outside_cost)) |
| { |
| dr0_info = first_store; |
| dr0_same_align_drs = first_store_same_align_drs; |
| peel_for_unknown_alignment.inside_cost = store_inside_cost; |
| peel_for_unknown_alignment.outside_cost = store_outside_cost; |
| } |
| else |
| { |
| peel_for_unknown_alignment.inside_cost = load_inside_cost; |
| peel_for_unknown_alignment.outside_cost = load_outside_cost; |
| } |
| |
| stmt_vector_for_cost prologue_cost_vec, epilogue_cost_vec; |
| prologue_cost_vec.create (2); |
| epilogue_cost_vec.create (2); |
| |
| int dummy2; |
| peel_for_unknown_alignment.outside_cost += vect_get_known_peeling_cost |
| (loop_vinfo, estimated_npeels, &dummy2, |
| &LOOP_VINFO_SCALAR_ITERATION_COST (loop_vinfo), |
| &prologue_cost_vec, &epilogue_cost_vec); |
| |
| prologue_cost_vec.release (); |
| epilogue_cost_vec.release (); |
| |
| peel_for_unknown_alignment.peel_info.count = dr0_same_align_drs + 1; |
| } |
| |
| peel_for_unknown_alignment.peel_info.npeel = 0; |
| peel_for_unknown_alignment.peel_info.dr_info = dr0_info; |
| |
| best_peel = peel_for_unknown_alignment; |
| |
| peel_for_known_alignment.inside_cost = INT_MAX; |
| peel_for_known_alignment.outside_cost = INT_MAX; |
| peel_for_known_alignment.peel_info.count = 0; |
| peel_for_known_alignment.peel_info.dr_info = NULL; |
| |
| if (do_peeling && one_misalignment_known) |
| { |
| /* Peeling is possible, but there is no data access that is not supported |
| unless aligned. So we try to choose the best possible peeling from |
| the hash table. */ |
| peel_for_known_alignment = vect_peeling_hash_choose_best_peeling |
| (&peeling_htab, loop_vinfo); |
| } |
| |
| /* Compare costs of peeling for known and unknown alignment. */ |
| if (peel_for_known_alignment.peel_info.dr_info != NULL |
| && peel_for_unknown_alignment.inside_cost |
| >= peel_for_known_alignment.inside_cost) |
| { |
| best_peel = peel_for_known_alignment; |
| |
| /* If the best peeling for known alignment has NPEEL == 0, perform no |
| peeling at all except if there is an unsupportable dr that we can |
| align. */ |
| if (best_peel.peel_info.npeel == 0 && !one_dr_unsupportable) |
| do_peeling = false; |
| } |
| |
| /* If there is an unsupportable data ref, prefer this over all choices so far |
| since we'd have to discard a chosen peeling except when it accidentally |
| aligned the unsupportable data ref. */ |
| if (one_dr_unsupportable) |
| dr0_info = unsupportable_dr_info; |
| else if (do_peeling) |
| { |
| /* Calculate the penalty for no peeling, i.e. leaving everything as-is. |
| TODO: Use nopeel_outside_cost or get rid of it? */ |
| unsigned nopeel_inside_cost = 0; |
| unsigned nopeel_outside_cost = 0; |
| |
| stmt_vector_for_cost dummy; |
| dummy.create (2); |
| vect_get_peeling_costs_all_drs (loop_vinfo, NULL, &nopeel_inside_cost, |
| &nopeel_outside_cost, &dummy, &dummy, |
| 0, false); |
| dummy.release (); |
| |
| /* Add epilogue costs. As we do not peel for alignment here, no prologue |
| costs will be recorded. */ |
| stmt_vector_for_cost prologue_cost_vec, epilogue_cost_vec; |
| prologue_cost_vec.create (2); |
| epilogue_cost_vec.create (2); |
| |
| int dummy2; |
| nopeel_outside_cost += vect_get_known_peeling_cost |
| (loop_vinfo, 0, &dummy2, |
| &LOOP_VINFO_SCALAR_ITERATION_COST (loop_vinfo), |
| &prologue_cost_vec, &epilogue_cost_vec); |
| |
| prologue_cost_vec.release (); |
| epilogue_cost_vec.release (); |
| |
| npeel = best_peel.peel_info.npeel; |
| dr0_info = best_peel.peel_info.dr_info; |
| |
| /* If no peeling is not more expensive than the best peeling we |
| have so far, don't perform any peeling. */ |
| if (nopeel_inside_cost <= best_peel.inside_cost) |
| do_peeling = false; |
| } |
| |
| if (do_peeling) |
| { |
| stmt_vec_info stmt_info = dr0_info->stmt; |
| if (known_alignment_for_access_p (dr0_info)) |
| { |
| bool negative = tree_int_cst_compare (DR_STEP (dr0_info->dr), |
| size_zero_node) < 0; |
| if (!npeel) |
| { |
| /* Since it's known at compile time, compute the number of |
| iterations in the peeled loop (the peeling factor) for use in |
| updating DR_MISALIGNMENT values. The peeling factor is the |
| vectorization factor minus the misalignment as an element |
| count. */ |
| mis = (negative |
| ? DR_MISALIGNMENT (dr0_info) |
| : -DR_MISALIGNMENT (dr0_info)); |
| /* If known_alignment_for_access_p then we have set |
| DR_MISALIGNMENT which is only done if we know it at compiler |
| time, so it is safe to assume target alignment is constant. |
| */ |
| unsigned int target_align = |
| DR_TARGET_ALIGNMENT (dr0_info).to_constant (); |
| npeel = ((mis & (target_align - 1)) |
| / vect_get_scalar_dr_size (dr0_info)); |
| } |
| |
| /* For interleaved data access every iteration accesses all the |
| members of the group, therefore we divide the number of iterations |
| by the group size. */ |
| if (STMT_VINFO_GROUPED_ACCESS (stmt_info)) |
| npeel /= DR_GROUP_SIZE (stmt_info); |
| |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "Try peeling by %d\n", npeel); |
| } |
| |
| /* Ensure that all datarefs can be vectorized after the peel. */ |
| if (!vect_peeling_supportable (loop_vinfo, dr0_info, npeel)) |
| do_peeling = false; |
| |
| /* Check if all datarefs are supportable and log. */ |
| if (do_peeling && known_alignment_for_access_p (dr0_info) && npeel == 0) |
| return opt_result::success (); |
| |
| /* Cost model #1 - honor --param vect-max-peeling-for-alignment. */ |
| if (do_peeling) |
| { |
| unsigned max_allowed_peel |
| = param_vect_max_peeling_for_alignment; |
| if (flag_vect_cost_model <= VECT_COST_MODEL_CHEAP) |
| max_allowed_peel = 0; |
| if (max_allowed_peel != (unsigned)-1) |
| { |
| unsigned max_peel = npeel; |
| if (max_peel == 0) |
| { |
| poly_uint64 target_align = DR_TARGET_ALIGNMENT (dr0_info); |
| unsigned HOST_WIDE_INT target_align_c; |
| if (target_align.is_constant (&target_align_c)) |
| max_peel = |
| target_align_c / vect_get_scalar_dr_size (dr0_info) - 1; |
| else |
| { |
| do_peeling = false; |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "Disable peeling, max peels set and vector" |
| " alignment unknown\n"); |
| } |
| } |
| if (max_peel > max_allowed_peel) |
| { |
| do_peeling = false; |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "Disable peeling, max peels reached: %d\n", max_peel); |
| } |
| } |
| } |
| |
| /* Cost model #2 - if peeling may result in a remaining loop not |
| iterating enough to be vectorized then do not peel. Since this |
| is a cost heuristic rather than a correctness decision, use the |
| most likely runtime value for variable vectorization factors. */ |
| if (do_peeling |
| && LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)) |
| { |
| unsigned int assumed_vf = vect_vf_for_cost (loop_vinfo); |
| unsigned int max_peel = npeel == 0 ? assumed_vf - 1 : npeel; |
| if ((unsigned HOST_WIDE_INT) LOOP_VINFO_INT_NITERS (loop_vinfo) |
| < assumed_vf + max_peel) |
| do_peeling = false; |
| } |
| |
| if (do_peeling) |
| { |
| /* (1.2) Update the DR_MISALIGNMENT of each data reference DR_i. |
| If the misalignment of DR_i is identical to that of dr0 then set |
| DR_MISALIGNMENT (DR_i) to zero. If the misalignment of DR_i and |
| dr0 are known at compile time then increment DR_MISALIGNMENT (DR_i) |
| by the peeling factor times the element size of DR_i (MOD the |
| vectorization factor times the size). Otherwise, the |
| misalignment of DR_i must be set to unknown. */ |
| FOR_EACH_VEC_ELT (datarefs, i, dr) |
| if (dr != dr0_info->dr) |
| { |
| dr_vec_info *dr_info = loop_vinfo->lookup_dr (dr); |
| if (!vect_relevant_for_alignment_p (dr_info)) |
| continue; |
| |
| vect_update_misalignment_for_peel (dr_info, dr0_info, npeel); |
| } |
| |
| LOOP_VINFO_UNALIGNED_DR (loop_vinfo) = dr0_info; |
| if (npeel) |
| LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) = npeel; |
| else |
| LOOP_VINFO_PEELING_FOR_ALIGNMENT (loop_vinfo) |
| = DR_MISALIGNMENT (dr0_info); |
| SET_DR_MISALIGNMENT (dr0_info, 0); |
| if (dump_enabled_p ()) |
| { |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "Alignment of access forced using peeling.\n"); |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "Peeling for alignment will be applied.\n"); |
| } |
| |
| /* The inside-loop cost will be accounted for in vectorizable_load |
| and vectorizable_store correctly with adjusted alignments. |
| Drop the body_cst_vec on the floor here. */ |
| return opt_result::success (); |
| } |
| } |
| |
| /* (2) Versioning to force alignment. */ |
| |
| /* Try versioning if: |
| 1) optimize loop for speed and the cost-model is not cheap |
| 2) there is at least one unsupported misaligned data ref with an unknown |
| misalignment, and |
| 3) all misaligned data refs with a known misalignment are supported, and |
| 4) the number of runtime alignment checks is within reason. */ |
| |
| do_versioning |
| = (optimize_loop_nest_for_speed_p (loop) |
| && !loop->inner /* FORNOW */ |
| && flag_vect_cost_model > VECT_COST_MODEL_CHEAP); |
| |
| if (do_versioning) |
| { |
| FOR_EACH_VEC_ELT (datarefs, i, dr) |
| { |
| dr_vec_info *dr_info = loop_vinfo->lookup_dr (dr); |
| if (aligned_access_p (dr_info) |
| || !vect_relevant_for_alignment_p (dr_info)) |
| continue; |
| |
| stmt_vec_info stmt_info = dr_info->stmt; |
| if (STMT_VINFO_STRIDED_P (stmt_info)) |
| { |
| do_versioning = false; |
| break; |
| } |
| |
| supportable_dr_alignment |
| = vect_supportable_dr_alignment (loop_vinfo, dr_info, false); |
| |
| if (!supportable_dr_alignment) |
| { |
| int mask; |
| tree vectype; |
| |
| if (known_alignment_for_access_p (dr_info) |
| || LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo).length () |
| >= (unsigned) param_vect_max_version_for_alignment_checks) |
| { |
| do_versioning = false; |
| break; |
| } |
| |
| vectype = STMT_VINFO_VECTYPE (stmt_info); |
| gcc_assert (vectype); |
| |
| /* At present we don't support versioning for alignment |
| with variable VF, since there's no guarantee that the |
| VF is a power of two. We could relax this if we added |
| a way of enforcing a power-of-two size. */ |
| unsigned HOST_WIDE_INT size; |
| if (!GET_MODE_SIZE (TYPE_MODE (vectype)).is_constant (&size)) |
| { |
| do_versioning = false; |
| break; |
| } |
| |
| /* Forcing alignment in the first iteration is no good if |
| we don't keep it across iterations. For now, just disable |
| versioning in this case. |
| ?? We could actually unroll the loop to achieve the required |
| overall step alignment, and forcing the alignment could be |
| done by doing some iterations of the non-vectorized loop. */ |
| if (!multiple_p (LOOP_VINFO_VECT_FACTOR (loop_vinfo) |
| * DR_STEP_ALIGNMENT (dr), |
| DR_TARGET_ALIGNMENT (dr_info))) |
| { |
| do_versioning = false; |
| break; |
| } |
| |
| /* The rightmost bits of an aligned address must be zeros. |
| Construct the mask needed for this test. For example, |
| GET_MODE_SIZE for the vector mode V4SI is 16 bytes so the |
| mask must be 15 = 0xf. */ |
| mask = size - 1; |
| |
| /* FORNOW: use the same mask to test all potentially unaligned |
| references in the loop. */ |
| if (LOOP_VINFO_PTR_MASK (loop_vinfo) |
| && LOOP_VINFO_PTR_MASK (loop_vinfo) != mask) |
| { |
| do_versioning = false; |
| break; |
| } |
| |
| LOOP_VINFO_PTR_MASK (loop_vinfo) = mask; |
| LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo).safe_push (stmt_info); |
| } |
| } |
| |
| /* Versioning requires at least one misaligned data reference. */ |
| if (!LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)) |
| do_versioning = false; |
| else if (!do_versioning) |
| LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo).truncate (0); |
| } |
| |
| if (do_versioning) |
| { |
| vec<stmt_vec_info> may_misalign_stmts |
| = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo); |
| stmt_vec_info stmt_info; |
| |
| /* It can now be assumed that the data references in the statements |
| in LOOP_VINFO_MAY_MISALIGN_STMTS will be aligned in the version |
| of the loop being vectorized. */ |
| FOR_EACH_VEC_ELT (may_misalign_stmts, i, stmt_info) |
| { |
| dr_vec_info *dr_info = STMT_VINFO_DR_INFO (stmt_info); |
| SET_DR_MISALIGNMENT (dr_info, 0); |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "Alignment of access forced using versioning.\n"); |
| } |
| |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "Versioning for alignment will be applied.\n"); |
| |
| /* Peeling and versioning can't be done together at this time. */ |
| gcc_assert (! (do_peeling && do_versioning)); |
| |
| return opt_result::success (); |
| } |
| |
| /* This point is reached if neither peeling nor versioning is being done. */ |
| gcc_assert (! (do_peeling || do_versioning)); |
| |
| return opt_result::success (); |
| } |
| |
| |
| /* Function vect_analyze_data_refs_alignment |
| |
| Analyze the alignment of the data-references in the loop. |
| Return FALSE if a data reference is found that cannot be vectorized. */ |
| |
| opt_result |
| vect_analyze_data_refs_alignment (loop_vec_info loop_vinfo) |
| { |
| DUMP_VECT_SCOPE ("vect_analyze_data_refs_alignment"); |
| |
| vec<data_reference_p> datarefs = LOOP_VINFO_DATAREFS (loop_vinfo); |
| struct data_reference *dr; |
| unsigned int i; |
| |
| vect_record_base_alignments (loop_vinfo); |
| FOR_EACH_VEC_ELT (datarefs, i, dr) |
| { |
| dr_vec_info *dr_info = loop_vinfo->lookup_dr (dr); |
| if (STMT_VINFO_VECTORIZABLE (dr_info->stmt)) |
| vect_compute_data_ref_alignment (loop_vinfo, dr_info); |
| } |
| |
| return opt_result::success (); |
| } |
| |
| |
| /* Analyze alignment of DRs of stmts in NODE. */ |
| |
| static bool |
| vect_slp_analyze_node_alignment (vec_info *vinfo, slp_tree node) |
| { |
| /* We vectorize from the first scalar stmt in the node unless |
| the node is permuted in which case we start from the first |
| element in the group. */ |
| stmt_vec_info first_stmt_info = SLP_TREE_SCALAR_STMTS (node)[0]; |
| dr_vec_info *first_dr_info = STMT_VINFO_DR_INFO (first_stmt_info); |
| if (SLP_TREE_LOAD_PERMUTATION (node).exists ()) |
| first_stmt_info = DR_GROUP_FIRST_ELEMENT (first_stmt_info); |
| |
| /* We need to commit to a vector type for the group now. */ |
| if (is_a <bb_vec_info> (vinfo) |
| && !vect_update_shared_vectype (first_stmt_info, SLP_TREE_VECTYPE (node))) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "desired vector type conflicts with earlier one " |
| "for %G", first_stmt_info->stmt); |
| return false; |
| } |
| |
| dr_vec_info *dr_info = STMT_VINFO_DR_INFO (first_stmt_info); |
| vect_compute_data_ref_alignment (vinfo, dr_info); |
| /* In several places we need alignment of the first element anyway. */ |
| if (dr_info != first_dr_info) |
| vect_compute_data_ref_alignment (vinfo, first_dr_info); |
| |
| /* For creating the data-ref pointer we need alignment of the |
| first element as well. */ |
| first_stmt_info |
| = vect_stmt_to_vectorize (vect_find_first_scalar_stmt_in_slp (node)); |
| if (first_stmt_info != SLP_TREE_SCALAR_STMTS (node)[0]) |
| { |
| first_dr_info = STMT_VINFO_DR_INFO (first_stmt_info); |
| if (dr_info != first_dr_info) |
| vect_compute_data_ref_alignment (vinfo, first_dr_info); |
| } |
| |
| return true; |
| } |
| |
| /* Function vect_slp_analyze_instance_alignment |
| |
| Analyze the alignment of the data-references in the SLP instance. |
| Return FALSE if a data reference is found that cannot be vectorized. */ |
| |
| bool |
| vect_slp_analyze_instance_alignment (vec_info *vinfo, |
| slp_instance instance) |
| { |
| DUMP_VECT_SCOPE ("vect_slp_analyze_instance_alignment"); |
| |
| slp_tree node; |
| unsigned i; |
| FOR_EACH_VEC_ELT (SLP_INSTANCE_LOADS (instance), i, node) |
| if (! vect_slp_analyze_node_alignment (vinfo, node)) |
| return false; |
| |
| node = SLP_INSTANCE_TREE (instance); |
| if (STMT_VINFO_DATA_REF (SLP_TREE_REPRESENTATIVE (node)) |
| && ! vect_slp_analyze_node_alignment |
| (vinfo, SLP_INSTANCE_TREE (instance))) |
| return false; |
| |
| return true; |
| } |
| |
| |
| /* Analyze groups of accesses: check that DR_INFO belongs to a group of |
| accesses of legal size, step, etc. Detect gaps, single element |
| interleaving, and other special cases. Set grouped access info. |
| Collect groups of strided stores for further use in SLP analysis. |
| Worker for vect_analyze_group_access. */ |
| |
| static bool |
| vect_analyze_group_access_1 (vec_info *vinfo, dr_vec_info *dr_info) |
| { |
| data_reference *dr = dr_info->dr; |
| tree step = DR_STEP (dr); |
| tree scalar_type = TREE_TYPE (DR_REF (dr)); |
| HOST_WIDE_INT type_size = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (scalar_type)); |
| stmt_vec_info stmt_info = dr_info->stmt; |
| loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo); |
| bb_vec_info bb_vinfo = dyn_cast <bb_vec_info> (vinfo); |
| HOST_WIDE_INT dr_step = -1; |
| HOST_WIDE_INT groupsize, last_accessed_element = 1; |
| bool slp_impossible = false; |
| |
| /* For interleaving, GROUPSIZE is STEP counted in elements, i.e., the |
| size of the interleaving group (including gaps). */ |
| if (tree_fits_shwi_p (step)) |
| { |
| dr_step = tree_to_shwi (step); |
| /* Check that STEP is a multiple of type size. Otherwise there is |
| a non-element-sized gap at the end of the group which we |
| cannot represent in DR_GROUP_GAP or DR_GROUP_SIZE. |
| ??? As we can handle non-constant step fine here we should |
| simply remove uses of DR_GROUP_GAP between the last and first |
| element and instead rely on DR_STEP. DR_GROUP_SIZE then would |
| simply not include that gap. */ |
| if ((dr_step % type_size) != 0) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "Step %T is not a multiple of the element size" |
| " for %T\n", |
| step, DR_REF (dr)); |
| return false; |
| } |
| groupsize = absu_hwi (dr_step) / type_size; |
| } |
| else |
| groupsize = 0; |
| |
| /* Not consecutive access is possible only if it is a part of interleaving. */ |
| if (!DR_GROUP_FIRST_ELEMENT (stmt_info)) |
| { |
| /* Check if it this DR is a part of interleaving, and is a single |
| element of the group that is accessed in the loop. */ |
| |
| /* Gaps are supported only for loads. STEP must be a multiple of the type |
| size. */ |
| if (DR_IS_READ (dr) |
| && (dr_step % type_size) == 0 |
| && groupsize > 0 |
| /* This could be UINT_MAX but as we are generating code in a very |
| inefficient way we have to cap earlier. |
| See PR91403 for example. */ |
| && groupsize <= 4096) |
| { |
| DR_GROUP_FIRST_ELEMENT (stmt_info) = stmt_info; |
| DR_GROUP_SIZE (stmt_info) = groupsize; |
| DR_GROUP_GAP (stmt_info) = groupsize - 1; |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "Detected single element interleaving %T" |
| " step %T\n", |
| DR_REF (dr), step); |
| |
| return true; |
| } |
| |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "not consecutive access %G", stmt_info->stmt); |
| |
| if (bb_vinfo) |
| { |
| /* Mark the statement as unvectorizable. */ |
| STMT_VINFO_VECTORIZABLE (stmt_info) = false; |
| return true; |
| } |
| |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, "using strided accesses\n"); |
| STMT_VINFO_STRIDED_P (stmt_info) = true; |
| return true; |
| } |
| |
| if (DR_GROUP_FIRST_ELEMENT (stmt_info) == stmt_info) |
| { |
| /* First stmt in the interleaving chain. Check the chain. */ |
| stmt_vec_info next = DR_GROUP_NEXT_ELEMENT (stmt_info); |
| struct data_reference *data_ref = dr; |
| unsigned int count = 1; |
| tree prev_init = DR_INIT (data_ref); |
| HOST_WIDE_INT diff, gaps = 0; |
| |
| /* By construction, all group members have INTEGER_CST DR_INITs. */ |
| while (next) |
| { |
| /* We never have the same DR multiple times. */ |
| gcc_assert (tree_int_cst_compare (DR_INIT (data_ref), |
| DR_INIT (STMT_VINFO_DATA_REF (next))) != 0); |
| |
| data_ref = STMT_VINFO_DATA_REF (next); |
| |
| /* All group members have the same STEP by construction. */ |
| gcc_checking_assert (operand_equal_p (DR_STEP (data_ref), step, 0)); |
| |
| /* Check that the distance between two accesses is equal to the type |
| size. Otherwise, we have gaps. */ |
| diff = (TREE_INT_CST_LOW (DR_INIT (data_ref)) |
| - TREE_INT_CST_LOW (prev_init)) / type_size; |
| if (diff != 1) |
| { |
| /* FORNOW: SLP of accesses with gaps is not supported. */ |
| slp_impossible = true; |
| if (DR_IS_WRITE (data_ref)) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "interleaved store with gaps\n"); |
| return false; |
| } |
| |
| gaps += diff - 1; |
| } |
| |
| last_accessed_element += diff; |
| |
| /* Store the gap from the previous member of the group. If there is no |
| gap in the access, DR_GROUP_GAP is always 1. */ |
| DR_GROUP_GAP (next) = diff; |
| |
| prev_init = DR_INIT (data_ref); |
| next = DR_GROUP_NEXT_ELEMENT (next); |
| /* Count the number of data-refs in the chain. */ |
| count++; |
| } |
| |
| if (groupsize == 0) |
| groupsize = count + gaps; |
| |
| /* This could be UINT_MAX but as we are generating code in a very |
| inefficient way we have to cap earlier. See PR78699 for example. */ |
| if (groupsize > 4096) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "group is too large\n"); |
| return false; |
| } |
| |
| /* Check that the size of the interleaving is equal to count for stores, |
| i.e., that there are no gaps. */ |
| if (groupsize != count |
| && !DR_IS_READ (dr)) |
| { |
| groupsize = count; |
| STMT_VINFO_STRIDED_P (stmt_info) = true; |
| } |
| |
| /* If there is a gap after the last load in the group it is the |
| difference between the groupsize and the last accessed |
| element. |
| When there is no gap, this difference should be 0. */ |
| DR_GROUP_GAP (stmt_info) = groupsize - last_accessed_element; |
| |
| DR_GROUP_SIZE (stmt_info) = groupsize; |
| if (dump_enabled_p ()) |
| { |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "Detected interleaving "); |
| if (DR_IS_READ (dr)) |
| dump_printf (MSG_NOTE, "load "); |
| else if (STMT_VINFO_STRIDED_P (stmt_info)) |
| dump_printf (MSG_NOTE, "strided store "); |
| else |
| dump_printf (MSG_NOTE, "store "); |
| dump_printf (MSG_NOTE, "of size %u\n", |
| (unsigned)groupsize); |
| dump_printf_loc (MSG_NOTE, vect_location, "\t%G", stmt_info->stmt); |
| next = DR_GROUP_NEXT_ELEMENT (stmt_info); |
| while (next) |
| { |
| if (DR_GROUP_GAP (next) != 1) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "\t<gap of %d elements>\n", |
| DR_GROUP_GAP (next) - 1); |
| dump_printf_loc (MSG_NOTE, vect_location, "\t%G", next->stmt); |
| next = DR_GROUP_NEXT_ELEMENT (next); |
| } |
| if (DR_GROUP_GAP (stmt_info) != 0) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "\t<gap of %d elements>\n", |
| DR_GROUP_GAP (stmt_info)); |
| } |
| |
| /* SLP: create an SLP data structure for every interleaving group of |
| stores for further analysis in vect_analyse_slp. */ |
| if (DR_IS_WRITE (dr) && !slp_impossible) |
| { |
| if (loop_vinfo) |
| LOOP_VINFO_GROUPED_STORES (loop_vinfo).safe_push (stmt_info); |
| if (bb_vinfo) |
| BB_VINFO_GROUPED_STORES (bb_vinfo).safe_push (stmt_info); |
| } |
| } |
| |
| return true; |
| } |
| |
| /* Analyze groups of accesses: check that DR_INFO belongs to a group of |
| accesses of legal size, step, etc. Detect gaps, single element |
| interleaving, and other special cases. Set grouped access info. |
| Collect groups of strided stores for further use in SLP analysis. */ |
| |
| static bool |
| vect_analyze_group_access (vec_info *vinfo, dr_vec_info *dr_info) |
| { |
| if (!vect_analyze_group_access_1 (vinfo, dr_info)) |
| { |
| /* Dissolve the group if present. */ |
| stmt_vec_info stmt_info = DR_GROUP_FIRST_ELEMENT (dr_info->stmt); |
| while (stmt_info) |
| { |
| stmt_vec_info next = DR_GROUP_NEXT_ELEMENT (stmt_info); |
| DR_GROUP_FIRST_ELEMENT (stmt_info) = NULL; |
| DR_GROUP_NEXT_ELEMENT (stmt_info) = NULL; |
| stmt_info = next; |
| } |
| return false; |
| } |
| return true; |
| } |
| |
| /* Analyze the access pattern of the data-reference DR_INFO. |
| In case of non-consecutive accesses call vect_analyze_group_access() to |
| analyze groups of accesses. */ |
| |
| static bool |
| vect_analyze_data_ref_access (vec_info *vinfo, dr_vec_info *dr_info) |
| { |
| data_reference *dr = dr_info->dr; |
| tree step = DR_STEP (dr); |
| tree scalar_type = TREE_TYPE (DR_REF (dr)); |
| stmt_vec_info stmt_info = dr_info->stmt; |
| loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo); |
| class loop *loop = NULL; |
| |
| if (STMT_VINFO_GATHER_SCATTER_P (stmt_info)) |
| return true; |
| |
| if (loop_vinfo) |
| loop = LOOP_VINFO_LOOP (loop_vinfo); |
| |
| if (loop_vinfo && !step) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "bad data-ref access in loop\n"); |
| return false; |
| } |
| |
| /* Allow loads with zero step in inner-loop vectorization. */ |
| if (loop_vinfo && integer_zerop (step)) |
| { |
| DR_GROUP_FIRST_ELEMENT (stmt_info) = NULL; |
| if (!nested_in_vect_loop_p (loop, stmt_info)) |
| return DR_IS_READ (dr); |
| /* Allow references with zero step for outer loops marked |
| with pragma omp simd only - it guarantees absence of |
| loop-carried dependencies between inner loop iterations. */ |
| if (loop->safelen < 2) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "zero step in inner loop of nest\n"); |
| return false; |
| } |
| } |
| |
| if (loop && nested_in_vect_loop_p (loop, stmt_info)) |
| { |
| /* Interleaved accesses are not yet supported within outer-loop |
| vectorization for references in the inner-loop. */ |
| DR_GROUP_FIRST_ELEMENT (stmt_info) = NULL; |
| |
| /* For the rest of the analysis we use the outer-loop step. */ |
| step = STMT_VINFO_DR_STEP (stmt_info); |
| if (integer_zerop (step)) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "zero step in outer loop.\n"); |
| return DR_IS_READ (dr); |
| } |
| } |
| |
| /* Consecutive? */ |
| if (TREE_CODE (step) == INTEGER_CST) |
| { |
| HOST_WIDE_INT dr_step = TREE_INT_CST_LOW (step); |
| if (!tree_int_cst_compare (step, TYPE_SIZE_UNIT (scalar_type)) |
| || (dr_step < 0 |
| && !compare_tree_int (TYPE_SIZE_UNIT (scalar_type), -dr_step))) |
| { |
| /* Mark that it is not interleaving. */ |
| DR_GROUP_FIRST_ELEMENT (stmt_info) = NULL; |
| return true; |
| } |
| } |
| |
| if (loop && nested_in_vect_loop_p (loop, stmt_info)) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "grouped access in outer loop.\n"); |
| return false; |
| } |
| |
| |
| /* Assume this is a DR handled by non-constant strided load case. */ |
| if (TREE_CODE (step) != INTEGER_CST) |
| return (STMT_VINFO_STRIDED_P (stmt_info) |
| && (!STMT_VINFO_GROUPED_ACCESS (stmt_info) |
| || vect_analyze_group_access (vinfo, dr_info))); |
| |
| /* Not consecutive access - check if it's a part of interleaving group. */ |
| return vect_analyze_group_access (vinfo, dr_info); |
| } |
| |
| typedef std::pair<data_reference_p, int> data_ref_pair; |
| |
| /* Compare two data-references DRA and DRB to group them into chunks |
| suitable for grouping. */ |
| |
| static int |
| dr_group_sort_cmp (const void *dra_, const void *drb_) |
| { |
| data_ref_pair dra_pair = *(data_ref_pair *)const_cast<void *>(dra_); |
| data_ref_pair drb_pair = *(data_ref_pair *)const_cast<void *>(drb_); |
| data_reference_p dra = dra_pair.first; |
| data_reference_p drb = drb_pair.first; |
| int cmp; |
| |
| /* Stabilize sort. */ |
| if (dra == drb) |
| return 0; |
| |
| /* DRs in different basic-blocks never belong to the same group. */ |
| int bb_index1 = gimple_bb (DR_STMT (dra))->index; |
| int bb_index2 = gimple_bb (DR_STMT (drb))->index; |
| if (bb_index1 != bb_index2) |
| return bb_index1 < bb_index2 ? -1 : 1; |
| |
| /* Different group IDs lead never belong to the same group. */ |
| if (dra_pair.second != drb_pair.second) |
| return dra_pair.second < drb_pair.second ? -1 : 1; |
| |
| /* Ordering of DRs according to base. */ |
| cmp = data_ref_compare_tree (DR_BASE_ADDRESS (dra), |
| DR_BASE_ADDRESS (drb)); |
| if (cmp != 0) |
| return cmp; |
| |
| /* And according to DR_OFFSET. */ |
| cmp = data_ref_compare_tree (DR_OFFSET (dra), DR_OFFSET (drb)); |
| if (cmp != 0) |
| return cmp; |
| |
| /* Put reads before writes. */ |
| if (DR_IS_READ (dra) != DR_IS_READ (drb)) |
| return DR_IS_READ (dra) ? -1 : 1; |
| |
| /* Then sort after access size. */ |
| cmp = data_ref_compare_tree (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))), |
| TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb)))); |
| if (cmp != 0) |
| return cmp; |
| |
| /* And after step. */ |
| cmp = data_ref_compare_tree (DR_STEP (dra), DR_STEP (drb)); |
| if (cmp != 0) |
| return cmp; |
| |
| /* Then sort after DR_INIT. In case of identical DRs sort after stmt UID. */ |
| cmp = data_ref_compare_tree (DR_INIT (dra), DR_INIT (drb)); |
| if (cmp == 0) |
| return gimple_uid (DR_STMT (dra)) < gimple_uid (DR_STMT (drb)) ? -1 : 1; |
| return cmp; |
| } |
| |
| /* If OP is the result of a conversion, return the unconverted value, |
| otherwise return null. */ |
| |
| static tree |
| strip_conversion (tree op) |
| { |
| if (TREE_CODE (op) != SSA_NAME) |
| return NULL_TREE; |
| gimple *stmt = SSA_NAME_DEF_STMT (op); |
| if (!is_gimple_assign (stmt) |
| || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))) |
| return NULL_TREE; |
| return gimple_assign_rhs1 (stmt); |
| } |
| |
| /* Return true if vectorizable_* routines can handle statements STMT1_INFO |
| and STMT2_INFO being in a single group. When ALLOW_SLP_P, masked loads can |
| be grouped in SLP mode. */ |
| |
| static bool |
| can_group_stmts_p (stmt_vec_info stmt1_info, stmt_vec_info stmt2_info, |
| bool allow_slp_p) |
| { |
| if (gimple_assign_single_p (stmt1_info->stmt)) |
| return gimple_assign_single_p (stmt2_info->stmt); |
| |
| gcall *call1 = dyn_cast <gcall *> (stmt1_info->stmt); |
| if (call1 && gimple_call_internal_p (call1)) |
| { |
| /* Check for two masked loads or two masked stores. */ |
| gcall *call2 = dyn_cast <gcall *> (stmt2_info->stmt); |
| if (!call2 || !gimple_call_internal_p (call2)) |
| return false; |
| internal_fn ifn = gimple_call_internal_fn (call1); |
| if (ifn != IFN_MASK_LOAD && ifn != IFN_MASK_STORE) |
| return false; |
| if (ifn != gimple_call_internal_fn (call2)) |
| return false; |
| |
| /* Check that the masks are the same. Cope with casts of masks, |
| like those created by build_mask_conversion. */ |
| tree mask1 = gimple_call_arg (call1, 2); |
| tree mask2 = gimple_call_arg (call2, 2); |
| if (!operand_equal_p (mask1, mask2, 0) |
| && (ifn == IFN_MASK_STORE || !allow_slp_p)) |
| { |
| mask1 = strip_conversion (mask1); |
| if (!mask1) |
| return false; |
| mask2 = strip_conversion (mask2); |
| if (!mask2) |
| return false; |
| if (!operand_equal_p (mask1, mask2, 0)) |
| return false; |
| } |
| return true; |
| } |
| |
| return false; |
| } |
| |
| /* Function vect_analyze_data_ref_accesses. |
| |
| Analyze the access pattern of all the data references in the loop. |
| |
| FORNOW: the only access pattern that is considered vectorizable is a |
| simple step 1 (consecutive) access. |
| |
| FORNOW: handle only arrays and pointer accesses. */ |
| |
| opt_result |
| vect_analyze_data_ref_accesses (vec_info *vinfo, |
| vec<int> *dataref_groups) |
| { |
| unsigned int i; |
| vec<data_reference_p> datarefs = vinfo->shared->datarefs; |
| |
| DUMP_VECT_SCOPE ("vect_analyze_data_ref_accesses"); |
| |
| if (datarefs.is_empty ()) |
| return opt_result::success (); |
| |
| /* Sort the array of datarefs to make building the interleaving chains |
| linear. Don't modify the original vector's order, it is needed for |
| determining what dependencies are reversed. */ |
| vec<data_ref_pair> datarefs_copy; |
| datarefs_copy.create (datarefs.length ()); |
| for (unsigned i = 0; i < datarefs.length (); i++) |
| { |
| int group_id = dataref_groups ? (*dataref_groups)[i] : 0; |
| datarefs_copy.quick_push (data_ref_pair (datarefs[i], group_id)); |
| } |
| datarefs_copy.qsort (dr_group_sort_cmp); |
| hash_set<stmt_vec_info> to_fixup; |
| |
| /* Build the interleaving chains. */ |
| for (i = 0; i < datarefs_copy.length () - 1;) |
| { |
| data_reference_p dra = datarefs_copy[i].first; |
| int dra_group_id = datarefs_copy[i].second; |
| dr_vec_info *dr_info_a = vinfo->lookup_dr (dra); |
| stmt_vec_info stmtinfo_a = dr_info_a->stmt; |
| stmt_vec_info lastinfo = NULL; |
| if (!STMT_VINFO_VECTORIZABLE (stmtinfo_a) |
| || STMT_VINFO_GATHER_SCATTER_P (stmtinfo_a)) |
| { |
| ++i; |
| continue; |
| } |
| for (i = i + 1; i < datarefs_copy.length (); ++i) |
| { |
| data_reference_p drb = datarefs_copy[i].first; |
| int drb_group_id = datarefs_copy[i].second; |
| dr_vec_info *dr_info_b = vinfo->lookup_dr (drb); |
| stmt_vec_info stmtinfo_b = dr_info_b->stmt; |
| if (!STMT_VINFO_VECTORIZABLE (stmtinfo_b) |
| || STMT_VINFO_GATHER_SCATTER_P (stmtinfo_b)) |
| break; |
| |
| /* ??? Imperfect sorting (non-compatible types, non-modulo |
| accesses, same accesses) can lead to a group to be artificially |
| split here as we don't just skip over those. If it really |
| matters we can push those to a worklist and re-iterate |
| over them. The we can just skip ahead to the next DR here. */ |
| |
| /* DRs in a different BBs should not be put into the same |
| interleaving group. */ |
| int bb_index1 = gimple_bb (DR_STMT (dra))->index; |
| int bb_index2 = gimple_bb (DR_STMT (drb))->index; |
| if (bb_index1 != bb_index2) |
| break; |
| |
| if (dra_group_id != drb_group_id) |
| break; |
| |
| /* Check that the data-refs have same first location (except init) |
| and they are both either store or load (not load and store, |
| not masked loads or stores). */ |
| if (DR_IS_READ (dra) != DR_IS_READ (drb) |
| || data_ref_compare_tree (DR_BASE_ADDRESS (dra), |
| DR_BASE_ADDRESS (drb)) != 0 |
| || data_ref_compare_tree (DR_OFFSET (dra), DR_OFFSET (drb)) != 0 |
| || !can_group_stmts_p (stmtinfo_a, stmtinfo_b, true)) |
| break; |
| |
| /* Check that the data-refs have the same constant size. */ |
| tree sza = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))); |
| tree szb = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))); |
| if (!tree_fits_uhwi_p (sza) |
| || !tree_fits_uhwi_p (szb) |
| || !tree_int_cst_equal (sza, szb)) |
| break; |
| |
| /* Check that the data-refs have the same step. */ |
| if (data_ref_compare_tree (DR_STEP (dra), DR_STEP (drb)) != 0) |
| break; |
| |
| /* Check the types are compatible. |
| ??? We don't distinguish this during sorting. */ |
| if (!types_compatible_p (TREE_TYPE (DR_REF (dra)), |
| TREE_TYPE (DR_REF (drb)))) |
| break; |
| |
| /* Check that the DR_INITs are compile-time constants. */ |
| if (TREE_CODE (DR_INIT (dra)) != INTEGER_CST |
| || TREE_CODE (DR_INIT (drb)) != INTEGER_CST) |
| break; |
| |
| /* Different .GOMP_SIMD_LANE calls still give the same lane, |
| just hold extra information. */ |
| if (STMT_VINFO_SIMD_LANE_ACCESS_P (stmtinfo_a) |
| && STMT_VINFO_SIMD_LANE_ACCESS_P (stmtinfo_b) |
| && data_ref_compare_tree (DR_INIT (dra), DR_INIT (drb)) == 0) |
| break; |
| |
| /* Sorting has ensured that DR_INIT (dra) <= DR_INIT (drb). */ |
| HOST_WIDE_INT init_a = TREE_INT_CST_LOW (DR_INIT (dra)); |
| HOST_WIDE_INT init_b = TREE_INT_CST_LOW (DR_INIT (drb)); |
| HOST_WIDE_INT init_prev |
| = TREE_INT_CST_LOW (DR_INIT (datarefs_copy[i-1].first)); |
| gcc_assert (init_a <= init_b |
| && init_a <= init_prev |
| && init_prev <= init_b); |
| |
| /* Do not place the same access in the interleaving chain twice. */ |
| if (init_b == init_prev) |
| { |
| gcc_assert (gimple_uid (DR_STMT (datarefs_copy[i-1].first)) |
| < gimple_uid (DR_STMT (drb))); |
| /* Simply link in duplicates and fix up the chain below. */ |
| } |
| else |
| { |
| /* If init_b == init_a + the size of the type * k, we have an |
| interleaving, and DRA is accessed before DRB. */ |
| HOST_WIDE_INT type_size_a = tree_to_uhwi (sza); |
| if (type_size_a == 0 |
| || (init_b - init_a) % type_size_a != 0) |
| break; |
| |
| /* If we have a store, the accesses are adjacent. This splits |
| groups into chunks we support (we don't support vectorization |
| of stores with gaps). */ |
| if (!DR_IS_READ (dra) && init_b - init_prev != type_size_a) |
| break; |
| |
| /* If the step (if not zero or non-constant) is smaller than the |
| difference between data-refs' inits this splits groups into |
| suitable sizes. */ |
| if (tree_fits_shwi_p (DR_STEP (dra))) |
| { |
| unsigned HOST_WIDE_INT step |
| = absu_hwi (tree_to_shwi (DR_STEP (dra))); |
| if (step != 0 |
| && step <= (unsigned HOST_WIDE_INT)(init_b - init_a)) |
| break; |
| } |
| } |
| |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| DR_IS_READ (dra) |
| ? "Detected interleaving load %T and %T\n" |
| : "Detected interleaving store %T and %T\n", |
| DR_REF (dra), DR_REF (drb)); |
| |
| /* Link the found element into the group list. */ |
| if (!DR_GROUP_FIRST_ELEMENT (stmtinfo_a)) |
| { |
| DR_GROUP_FIRST_ELEMENT (stmtinfo_a) = stmtinfo_a; |
| lastinfo = stmtinfo_a; |
| } |
| DR_GROUP_FIRST_ELEMENT (stmtinfo_b) = stmtinfo_a; |
| DR_GROUP_NEXT_ELEMENT (lastinfo) = stmtinfo_b; |
| lastinfo = stmtinfo_b; |
| |
| STMT_VINFO_SLP_VECT_ONLY (stmtinfo_a) |
| = !can_group_stmts_p (stmtinfo_a, stmtinfo_b, false); |
| |
| if (dump_enabled_p () && STMT_VINFO_SLP_VECT_ONLY (stmtinfo_a)) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "Load suitable for SLP vectorization only.\n"); |
| |
| if (init_b == init_prev |
| && !to_fixup.add (DR_GROUP_FIRST_ELEMENT (stmtinfo_a)) |
| && dump_enabled_p ()) |
| dump_printf_loc (MSG_NOTE, vect_location, |
| "Queuing group with duplicate access for fixup\n"); |
| } |
| } |
| |
| /* Fixup groups with duplicate entries by splitting it. */ |
| while (1) |
| { |
| hash_set<stmt_vec_info>::iterator it = to_fixup.begin (); |
| if (!(it != to_fixup.end ())) |
| break; |
| stmt_vec_info grp = *it; |
| to_fixup.remove (grp); |
| |
| /* Find the earliest duplicate group member. */ |
| unsigned first_duplicate = -1u; |
| stmt_vec_info next, g = grp; |
| while ((next = DR_GROUP_NEXT_ELEMENT (g))) |
| { |
| if (tree_int_cst_equal (DR_INIT (STMT_VINFO_DR_INFO (next)->dr), |
| DR_INIT (STMT_VINFO_DR_INFO (g)->dr)) |
| && gimple_uid (STMT_VINFO_STMT (next)) < first_duplicate) |
| first_duplicate = gimple_uid (STMT_VINFO_STMT (next)); |
| g = next; |
| } |
| if (first_duplicate == -1U) |
| continue; |
| |
| /* Then move all stmts after the first duplicate to a new group. |
| Note this is a heuristic but one with the property that *it |
| is fixed up completely. */ |
| g = grp; |
| stmt_vec_info newgroup = NULL, ng = grp; |
| while ((next = DR_GROUP_NEXT_ELEMENT (g))) |
| { |
| if (gimple_uid (STMT_VINFO_STMT (next)) >= first_duplicate) |
| { |
| DR_GROUP_NEXT_ELEMENT (g) = DR_GROUP_NEXT_ELEMENT (next); |
| if (!newgroup) |
| newgroup = next; |
| else |
| DR_GROUP_NEXT_ELEMENT (ng) = next; |
| ng = next; |
| DR_GROUP_FIRST_ELEMENT (ng) = newgroup; |
| } |
| else |
| g = DR_GROUP_NEXT_ELEMENT (g); |
| } |
| DR_GROUP_NEXT_ELEMENT (ng) = NULL; |
| |
| /* Fixup the new group which still may contain duplicates. */ |
| to_fixup.add (newgroup); |
| } |
| |
| data_ref_pair *dr_pair; |
| FOR_EACH_VEC_ELT (datarefs_copy, i, dr_pair) |
| { |
| dr_vec_info *dr_info = vinfo->lookup_dr (dr_pair->first); |
| if (STMT_VINFO_VECTORIZABLE (dr_info->stmt) |
| && !vect_analyze_data_ref_access (vinfo, dr_info)) |
| { |
| if (dump_enabled_p ()) |
| dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, |
| "not vectorized: complicated access pattern.\n"); |
| |
| if (is_a <bb_vec_info> (vinfo)) |
| { |
| /* Mark the statement as not vectorizable. */ |
| STMT_VINFO_VECTORIZABLE (dr_info-> |