diff options
Diffstat (limited to 'gcc/tree-vect-data-refs.c')
| -rw-r--r-- | gcc/tree-vect-data-refs.c | 230 |
1 files changed, 216 insertions, 14 deletions
diff --git a/gcc/tree-vect-data-refs.c b/gcc/tree-vect-data-refs.c index 177729006e8..60f2539b3c0 100644 --- a/gcc/tree-vect-data-refs.c +++ b/gcc/tree-vect-data-refs.c @@ -51,6 +51,7 @@ along with GCC; see the file COPYING3. If not see #include "builtins.h" #include "params.h" #include "tree-cfg.h" +#include "tree-hash-traits.h" /* Return true if load- or store-lanes optab OPTAB is implemented for COUNT vectors of type VECTYPE. NAME is the name of OPTAB. */ @@ -160,6 +161,60 @@ vect_mark_for_runtime_alias_test (ddr_p ddr, loop_vec_info loop_vinfo) } +/* 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, int *max_vf) +{ + struct 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 (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. */ + return vect_mark_for_runtime_alias_test (ddr, loop_vinfo); + } + } + return true; +} + + /* Function vect_analyze_data_ref_dependence. Return TRUE if there (might) exist a dependence between a memory-reference @@ -305,6 +360,12 @@ vect_analyze_data_ref_dependence (struct data_dependence_relation *ddr, } 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 false; + FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v) { int dist = dist_v[loop_depth]; @@ -647,6 +708,69 @@ vect_slp_analyze_instance_dependence (slp_instance instance) return res; } +/* Record in VINFO the base alignment guarantee given by DRB. STMT is + the statement that contains DRB, which is useful for recording in the + dump file. */ + +static void +vect_record_base_alignment (vec_info *vinfo, gimple *stmt, + 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 "); + dump_generic_expr (MSG_NOTE, TDF_SLIM, drb->base_address); + dump_printf (MSG_NOTE, "\n"); + dump_printf_loc (MSG_NOTE, vect_location, + " alignment: %d\n", drb->base_alignment); + dump_printf_loc (MSG_NOTE, vect_location, + " misalignment: %d\n", drb->base_misalignment); + dump_printf_loc (MSG_NOTE, vect_location, + " based on: "); + dump_gimple_stmt (MSG_NOTE, TDF_SLIM, stmt, 0); + } + } +} + +/* 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); + struct loop *loop = loop_vinfo ? LOOP_VINFO_LOOP (loop_vinfo) : NULL; + data_reference *dr; + unsigned int i; + FOR_EACH_VEC_ELT (vinfo->datarefs, i, dr) + if (!DR_IS_CONDITIONAL_IN_STMT (dr)) + { + gimple *stmt = DR_STMT (dr); + vect_record_base_alignment (vinfo, stmt, &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)) + { + stmt_vec_info stmt_info = vinfo_for_stmt (stmt); + vect_record_base_alignment + (vinfo, stmt, &STMT_VINFO_DR_WRT_VEC_LOOP (stmt_info)); + } + } +} + /* Function vect_compute_data_ref_alignment Compute the misalignment of the data reference DR. @@ -664,6 +788,7 @@ vect_compute_data_ref_alignment (struct data_reference *dr) { gimple *stmt = DR_STMT (dr); stmt_vec_info stmt_info = vinfo_for_stmt (stmt); + vec_base_alignments *base_alignments = &stmt_info->vinfo->base_alignments; loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info); struct loop *loop = NULL; tree ref = DR_REF (dr); @@ -732,6 +857,15 @@ vect_compute_data_ref_alignment (struct data_reference *dr) unsigned int base_misalignment = drb->base_misalignment; unsigned HOST_WIDE_INT vector_alignment = TYPE_ALIGN_UNIT (vectype); + /* 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 < vector_alignment || !step_preserves_misalignment_p /* We need to know whether the step wrt the vectorized loop is @@ -2052,8 +2186,7 @@ vect_find_same_alignment_drs (struct data_dependence_relation *ddr) if (dra == drb) return; - if (!operand_equal_p (DR_BASE_OBJECT (dra), DR_BASE_OBJECT (drb), - OEP_ADDRESS_OF) + if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0) || !operand_equal_p (DR_OFFSET (dra), DR_OFFSET (drb), 0) || !operand_equal_p (DR_STEP (dra), DR_STEP (drb), 0)) return; @@ -2111,6 +2244,7 @@ vect_analyze_data_refs_alignment (loop_vec_info vinfo) vec<data_reference_p> datarefs = vinfo->datarefs; struct data_reference *dr; + vect_record_base_alignments (vinfo); FOR_EACH_VEC_ELT (datarefs, i, dr) { stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr)); @@ -2878,6 +3012,44 @@ vect_no_alias_p (struct data_reference *a, struct data_reference *b, return false; } +/* Return true if the minimum nonzero dependence distance for loop LOOP_DEPTH + in DDR is >= VF. */ + +static bool +dependence_distance_ge_vf (data_dependence_relation *ddr, + unsigned int loop_depth, unsigned HOST_WIDE_INT vf) +{ + if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE + || DDR_NUM_DIST_VECTS (ddr) == 0) + return false; + + /* If the dependence is exact, we should have limited the VF instead. */ + gcc_checking_assert (DDR_COULD_BE_INDEPENDENT_P (ddr)); + + unsigned int i; + lambda_vector dist_v; + FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v) + { + HOST_WIDE_INT dist = dist_v[loop_depth]; + if (dist != 0 + && !(dist > 0 && DDR_REVERSED_P (ddr)) + && (unsigned HOST_WIDE_INT) abs_hwi (dist) < vf) + return false; + } + + if (dump_enabled_p ()) + { + dump_printf_loc (MSG_NOTE, vect_location, + "dependence distance between "); + dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (DDR_A (ddr))); + dump_printf (MSG_NOTE, " and "); + dump_generic_expr (MSG_NOTE, TDF_SLIM, DR_REF (DDR_B (ddr))); + dump_printf (MSG_NOTE, " is >= VF\n"); + } + + return true; +} + /* Function vect_prune_runtime_alias_test_list. Prune a list of ddrs to be tested at run-time by versioning for alias. @@ -2888,10 +3060,14 @@ vect_no_alias_p (struct data_reference *a, struct data_reference *b, bool vect_prune_runtime_alias_test_list (loop_vec_info loop_vinfo) { - vec<ddr_p> may_alias_ddrs = - LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo); - vec<dr_with_seg_len_pair_t>& comp_alias_ddrs = - LOOP_VINFO_COMP_ALIAS_DDRS (loop_vinfo); + typedef pair_hash <tree_operand_hash, tree_operand_hash> tree_pair_hash; + hash_set <tree_pair_hash> compared_objects; + + vec<ddr_p> may_alias_ddrs = LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo); + vec<dr_with_seg_len_pair_t> &comp_alias_ddrs + = LOOP_VINFO_COMP_ALIAS_DDRS (loop_vinfo); + vec<vec_object_pair> &check_unequal_addrs + = LOOP_VINFO_CHECK_UNEQUAL_ADDRS (loop_vinfo); int vect_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo); tree scalar_loop_iters = LOOP_VINFO_NITERS (loop_vinfo); @@ -2908,6 +3084,10 @@ vect_prune_runtime_alias_test_list (loop_vec_info loop_vinfo) comp_alias_ddrs.create (may_alias_ddrs.length ()); + unsigned int loop_depth + = index_in_loop_nest (LOOP_VINFO_LOOP (loop_vinfo)->num, + LOOP_VINFO_LOOP_NEST (loop_vinfo)); + /* First, we collect all data ref pairs for aliasing checks. */ FOR_EACH_VEC_ELT (may_alias_ddrs, i, ddr) { @@ -2917,6 +3097,29 @@ vect_prune_runtime_alias_test_list (loop_vec_info loop_vinfo) tree segment_length_a, segment_length_b; gimple *stmt_a, *stmt_b; + /* Ignore the alias if the VF we chose ended up being no greater + than the dependence distance. */ + if (dependence_distance_ge_vf (ddr, loop_depth, vect_factor)) + continue; + + if (DDR_OBJECT_A (ddr)) + { + vec_object_pair new_pair (DDR_OBJECT_A (ddr), DDR_OBJECT_B (ddr)); + if (!compared_objects.add (new_pair)) + { + if (dump_enabled_p ()) + { + dump_printf_loc (MSG_NOTE, vect_location, "checking that "); + dump_generic_expr (MSG_NOTE, TDF_SLIM, new_pair.first); + dump_printf (MSG_NOTE, " and "); + dump_generic_expr (MSG_NOTE, TDF_SLIM, new_pair.second); + dump_printf (MSG_NOTE, " have different addresses\n"); + } + LOOP_VINFO_CHECK_UNEQUAL_ADDRS (loop_vinfo).safe_push (new_pair); + } + continue; + } + dr_a = DDR_A (ddr); stmt_a = DR_STMT (DDR_A (ddr)); dr_group_first_a = GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_a)); @@ -2978,11 +3181,13 @@ vect_prune_runtime_alias_test_list (loop_vec_info loop_vinfo) prune_runtime_alias_test_list (&comp_alias_ddrs, (unsigned HOST_WIDE_INT) vect_factor); + + unsigned int count = (comp_alias_ddrs.length () + + check_unequal_addrs.length ()); dump_printf_loc (MSG_NOTE, vect_location, "improved number of alias checks from %d to %d\n", - may_alias_ddrs.length (), comp_alias_ddrs.length ()); - if ((int) comp_alias_ddrs.length () > - PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS)) + may_alias_ddrs.length (), count); + if ((int) count > PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS)) { if (dump_enabled_p ()) dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, @@ -2993,10 +3198,6 @@ vect_prune_runtime_alias_test_list (loop_vec_info loop_vinfo) return false; } - /* All alias checks have been resolved at compilation time. */ - if (!comp_alias_ddrs.length ()) - LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo).truncate (0); - return true; } @@ -3309,7 +3510,8 @@ again: { struct data_reference *newdr = create_data_ref (NULL, loop_containing_stmt (stmt), - DR_REF (dr), stmt, maybe_scatter ? false : true); + DR_REF (dr), stmt, !maybe_scatter, + DR_IS_CONDITIONAL_IN_STMT (dr)); gcc_assert (newdr != NULL && DR_REF (newdr)); if (DR_BASE_ADDRESS (newdr) && DR_OFFSET (newdr) |