From patchwork Wed Jun 7 12:47:01 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "juzhe.zhong@rivai.ai" X-Patchwork-Id: 70728 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id AA2623857019 for ; Wed, 7 Jun 2023 12:47:43 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtpbg153.qq.com (smtpbg153.qq.com [13.245.218.24]) by sourceware.org (Postfix) with ESMTPS id F2ED73858C54 for ; Wed, 7 Jun 2023 12:47:14 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org F2ED73858C54 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=rivai.ai Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=rivai.ai X-QQ-mid: bizesmtp64t1686142024t4za7xzc Received: from rios-cad5.localdomain ( [58.60.1.11]) by bizesmtp.qq.com (ESMTP) with id ; Wed, 07 Jun 2023 20:47:03 +0800 (CST) X-QQ-SSF: 01400000000000F0S000000A0000000 X-QQ-FEAT: OtIeQkg1QQGkYpx3LnvgoVH4kutqVVwaHADU7Zs8KAT9lK9Eh0ysRI/cPj5XU PSyrLu2gPBNJoTV3PMT4MwmndOAbf8YjNHQB7E3ZKGfuYzACXIE64jhp1Kx/qVyimkBqtVs rsK+CQlUAM+KKKeonbiP2OecSEl/TqNstwqFwH+NKnz2b/L7exoQA8+F9+y6dXturFFDqTG f4sOPQF22nYU1I5N9uXxdApEe6oVRW4lAs2Im3vxsNYMGHX24XkGoju/aUA3sJG6NsCLo5X k2ThCEzoXQ9wWp0BQ9godWvk5IL/C3xZMqCU000cTqfFM7tMMGi29mffjPs38734zVH1TUD JYORbxkeIbpqHOimKTKBjy7iFiw85OSatIH6I9/+yo/A8J3mFheoUmxWC5lcGk54yPMh+t6 BIFjP9/Od1ouMv41/HNbaw== X-QQ-GoodBg: 2 X-BIZMAIL-ID: 6798115588522020380 From: juzhe.zhong@rivai.ai To: gcc-patches@gcc.gnu.org Cc: rguenther@suse.de, richard.sandiford@arm.com, Ju-Zhe Zhong Subject: [PATCH V4] VECT: Add SELECT_VL support Date: Wed, 7 Jun 2023 20:47:01 +0800 Message-Id: <20230607124701.2367809-1-juzhe.zhong@rivai.ai> X-Mailer: git-send-email 2.36.3 MIME-Version: 1.0 X-QQ-SENDSIZE: 520 Feedback-ID: bizesmtp:rivai.ai:qybglogicsvrgz:qybglogicsvrgz7a-one-0 X-Spam-Status: No, score=-12.1 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_STATUS, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H5, RCVD_IN_MSPIKE_WL, SPF_HELO_PASS, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" From: Ju-Zhe Zhong Co-authored-by: Richard Sandiford Co-authored-by: Richard Biener This patch address comments from Richard && Richi and rebase to trunk. This patch is adding SELECT_VL middle-end support allow target have target dependent optimization in case of length calculation. This patch is inspired by RVV ISA and LLVM: https://reviews.llvm.org/D99750 The SELECT_VL is same behavior as LLVM "get_vector_length" with these following properties: 1. Only apply on single-rgroup. 2. non SLP. 3. adjust loop control IV. 4. adjust data reference IV. 5. allow non-vf elements processing in non-final iteration Code: # void vvaddint32(size_t n, const int*x, const int*y, int*z) # { for (size_t i=0; i Co-authored-by: Richard Biener --- gcc/doc/md.texi | 22 ++++++++++ gcc/internal-fn.def | 1 + gcc/optabs.def | 1 + gcc/tree-vect-loop-manip.cc | 32 ++++++++++---- gcc/tree-vect-loop.cc | 72 ++++++++++++++++++++++++++++++ gcc/tree-vect-stmts.cc | 87 ++++++++++++++++++++++++++++++++----- gcc/tree-vectorizer.h | 6 +++ 7 files changed, 202 insertions(+), 19 deletions(-) diff --git a/gcc/doc/md.texi b/gcc/doc/md.texi index 6a435eb4461..95f7fe1f802 100644 --- a/gcc/doc/md.texi +++ b/gcc/doc/md.texi @@ -4974,6 +4974,28 @@ for (i = 1; i < operand3; i++) operand0[i] = operand0[i - 1] && (operand1 + i < operand2); @end smallexample +@cindex @code{select_vl@var{m}} instruction pattern +@item @code{select_vl@var{m}} +Set operand 0 to the number of scalar iterations that should be handled +by one iteration of a vector loop. Operand 1 is the total number of +scalar iterations that the loop needs to process and operand 2 is a +maximum bound on the result (also known as the maximum ``vectorization +factor''). + +The maximum value of operand 0 is given by: +@smallexample +operand0 = MIN (operand1, operand2) +@end smallexample +However, targets might choose a lower value than this, based on +target-specific criteria. Each iteration of the vector loop might +therefore process a different number of scalar iterations, which in turn +means that induction variables will have a variable step. Because of +this, it is generally not useful to define this instruction if it will +always calculate the maximum value. + +This optab is only useful on targets that implement @samp{len_load_@var{m}} +and/or @samp{len_store_@var{m}}. + @cindex @code{check_raw_ptrs@var{m}} instruction pattern @item @samp{check_raw_ptrs@var{m}} Check whether, given two pointers @var{a} and @var{b} and a length @var{len}, diff --git a/gcc/internal-fn.def b/gcc/internal-fn.def index 3ac9d82aace..5d638de6d06 100644 --- a/gcc/internal-fn.def +++ b/gcc/internal-fn.def @@ -177,6 +177,7 @@ DEF_INTERNAL_OPTAB_FN (VEC_SET, 0, vec_set, vec_set) DEF_INTERNAL_OPTAB_FN (LEN_STORE, 0, len_store, len_store) DEF_INTERNAL_OPTAB_FN (WHILE_ULT, ECF_CONST | ECF_NOTHROW, while_ult, while) +DEF_INTERNAL_OPTAB_FN (SELECT_VL, ECF_CONST | ECF_NOTHROW, select_vl, binary) DEF_INTERNAL_OPTAB_FN (CHECK_RAW_PTRS, ECF_CONST | ECF_NOTHROW, check_raw_ptrs, check_ptrs) DEF_INTERNAL_OPTAB_FN (CHECK_WAR_PTRS, ECF_CONST | ECF_NOTHROW, diff --git a/gcc/optabs.def b/gcc/optabs.def index 6c064ff4993..f31b69c5d85 100644 --- a/gcc/optabs.def +++ b/gcc/optabs.def @@ -488,3 +488,4 @@ OPTAB_DC (vec_series_optab, "vec_series$a", VEC_SERIES) OPTAB_D (vec_shl_insert_optab, "vec_shl_insert_$a") OPTAB_D (len_load_optab, "len_load_$a") OPTAB_D (len_store_optab, "len_store_$a") +OPTAB_D (select_vl_optab, "select_vl$a") diff --git a/gcc/tree-vect-loop-manip.cc b/gcc/tree-vect-loop-manip.cc index 3f735945e67..1c8100c1a1c 100644 --- a/gcc/tree-vect-loop-manip.cc +++ b/gcc/tree-vect-loop-manip.cc @@ -534,7 +534,7 @@ vect_set_loop_controls_directly (class loop *loop, loop_vec_info loop_vinfo, _10 = (unsigned long) count_12(D); ... # ivtmp_9 = PHI - _36 = MIN_EXPR ; + _36 = (MIN_EXPR | SELECT_VL) ; ... vect__4.8_28 = .LEN_LOAD (_17, 32B, _36, 0); ... @@ -549,15 +549,28 @@ vect_set_loop_controls_directly (class loop *loop, loop_vec_info loop_vinfo, tree step = rgc->controls.length () == 1 ? rgc->controls[0] : make_ssa_name (iv_type); /* Create decrement IV. */ - create_iv (nitems_total, MINUS_EXPR, nitems_step, NULL_TREE, loop, - &incr_gsi, insert_after, &index_before_incr, - &index_after_incr); - gimple_seq_add_stmt (header_seq, gimple_build_assign (step, MIN_EXPR, - index_before_incr, - nitems_step)); + if (LOOP_VINFO_USING_SELECT_VL_P (loop_vinfo)) + { + create_iv (nitems_total, MINUS_EXPR, step, NULL_TREE, loop, &incr_gsi, + insert_after, &index_before_incr, &index_after_incr); + tree len = gimple_build (header_seq, IFN_SELECT_VL, iv_type, + index_before_incr, nitems_step); + gimple_seq_add_stmt (header_seq, gimple_build_assign (step, len)); + } + else + { + create_iv (nitems_total, MINUS_EXPR, nitems_step, NULL_TREE, loop, + &incr_gsi, insert_after, &index_before_incr, + &index_after_incr); + gimple_seq_add_stmt (header_seq, + gimple_build_assign (step, MIN_EXPR, + index_before_incr, + nitems_step)); + } *iv_step = step; *compare_step = nitems_step; - return index_before_incr; + return LOOP_VINFO_USING_SELECT_VL_P (loop_vinfo) ? index_after_incr + : index_before_incr; } /* Create increment IV. */ @@ -888,7 +901,8 @@ vect_set_loop_condition_partial_vectors (class loop *loop, /* Get a boolean result that tells us whether to iterate. */ edge exit_edge = single_exit (loop); gcond *cond_stmt; - if (LOOP_VINFO_USING_DECREMENTING_IV_P (loop_vinfo)) + if (LOOP_VINFO_USING_DECREMENTING_IV_P (loop_vinfo) + && !LOOP_VINFO_USING_SELECT_VL_P (loop_vinfo)) { gcc_assert (compare_step); tree_code code = (exit_edge->flags & EDGE_TRUE_VALUE) ? LE_EXPR : GT_EXPR; diff --git a/gcc/tree-vect-loop.cc b/gcc/tree-vect-loop.cc index 5b7a0da0034..ace9e759f5b 100644 --- a/gcc/tree-vect-loop.cc +++ b/gcc/tree-vect-loop.cc @@ -974,6 +974,7 @@ _loop_vec_info::_loop_vec_info (class loop *loop_in, vec_info_shared *shared) can_use_partial_vectors_p (param_vect_partial_vector_usage != 0), using_partial_vectors_p (false), using_decrementing_iv_p (false), + using_select_vl_p (false), epil_using_partial_vectors_p (false), partial_load_store_bias (0), peeling_for_gaps (false), @@ -2737,6 +2738,77 @@ start_over: LOOP_VINFO_VECT_FACTOR (loop_vinfo)))) LOOP_VINFO_USING_DECREMENTING_IV_P (loop_vinfo) = true; + /* If a loop uses length controls and has a decrementing loop control IV, + we will normally pass that IV through a MIN_EXPR to calcaluate the + basis for the length controls. E.g. in a loop that processes one + element per scalar iteration, the number of elements would be + MIN_EXPR , where N is the number of scalar iterations left. + + This MIN_EXPR approach allows us to use pointer IVs with an invariant + step, since only the final iteration of the vector loop can have + inactive lanes. + + However, some targets have a dedicated instruction for calculating the + preferred length, given the total number of elements that still need to + be processed. This is encapsulated in the SELECT_VL internal function. + + If the target supports SELECT_VL, we can use it instead of MIN_EXPR + to determine the basis for the length controls. However, unlike the + MIN_EXPR calculation, the SELECT_VL calculation can decide to make + lanes inactive in any iteration of the vector loop, not just the last + iteration. This SELECT_VL approach therefore requires us to use pointer + IVs with variable steps. + + Once we've decided how many elements should be processed by one + iteration of the vector loop, we need to populate the rgroup controls. + If a loop has multiple rgroups, we need to make sure that those rgroups + "line up" (that is, they must be consistent about which elements are + active and which aren't). This is done by vect_adjust_loop_lens_control. + + In principle, it would be possible to use vect_adjust_loop_lens_control + on either the result of a MIN_EXPR or the result of a SELECT_VL. + However: + + (1) In practice, it only makes sense to use SELECT_VL when a vector + operation will be controlled directly by the result. It is not + worth using SELECT_VL if it would only be the input to other + calculations. + + (2) If we use SELECT_VL for an rgroup that has N controls, each associated + pointer IV will need N updates by a variable amount (N-1 updates + within the iteration and 1 update to move to the next iteration). + + Because of this, we prefer to use the MIN_EXPR approach whenever there + is more than one length control. + + In addition, SELECT_VL always operates to a granularity of 1 unit. + If we wanted to use it to control an SLP operation on N consecutive + elements, we would need to make the SELECT_VL inputs measure scalar + iterations (rather than elements) and then multiply the SELECT_VL + result by N. But using SELECT_VL this way is inefficient because + of (1) above. + + 2. We don't apply SELECT_VL on single-rgroup when both (1) and (2) are + satisfied: + + (1). LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo) is true. + (2). LOOP_VINFO_VECT_FACTOR (loop_vinfo).is_constant () is true. + + Since SELECT_VL (variable step) will make SCEV analysis failed and then + we will fail to gain benefits of following unroll optimizations. We prefer + using the MIN_EXPR approach in this situation. */ + if (LOOP_VINFO_USING_DECREMENTING_IV_P (loop_vinfo)) + { + tree iv_type = LOOP_VINFO_RGROUP_IV_TYPE (loop_vinfo); + if (direct_internal_fn_supported_p (IFN_SELECT_VL, iv_type, + OPTIMIZE_FOR_SPEED) + && LOOP_VINFO_LENS (loop_vinfo).length () == 1 + && LOOP_VINFO_LENS (loop_vinfo)[0].factor == 1 && !slp + && (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo) + || !LOOP_VINFO_VECT_FACTOR (loop_vinfo).is_constant ())) + LOOP_VINFO_USING_SELECT_VL_P (loop_vinfo) = true; + } + /* If we're vectorizing an epilogue loop, the vectorized loop either needs to be able to handle fewer than VF scalars, or needs to have a lower VF than the main loop. */ diff --git a/gcc/tree-vect-stmts.cc b/gcc/tree-vect-stmts.cc index c7e4e71d3c5..e914ea94f00 100644 --- a/gcc/tree-vect-stmts.cc +++ b/gcc/tree-vect-stmts.cc @@ -3148,6 +3148,53 @@ vect_get_data_ptr_increment (vec_info *vinfo, return iv_step; } +/* Prepare the pointer IVs which needs to be updated by a variable amount. + Such variable amount is the outcome of .SELECT_VL. In this case, we can + allow each iteration process the flexible number of elements as long as + the number <= vf elments. + + Return data reference according to SELECT_VL. + If new statements are needed, insert them before GSI. */ + +static tree +vect_get_loop_variant_data_ptr_increment ( + vec_info *vinfo, tree aggr_type, gimple_stmt_iterator *gsi, + vec_loop_lens *loop_lens, dr_vec_info *dr_info, + vect_memory_access_type memory_access_type) +{ + loop_vec_info loop_vinfo = dyn_cast (vinfo); + tree step = vect_dr_behavior (vinfo, dr_info)->step; + + /* TODO: We don't support gather/scatter or load_lanes/store_lanes for pointer + IVs are updated by variable amount but we will support them in the future. + */ + gcc_assert (memory_access_type != VMAT_GATHER_SCATTER + && memory_access_type != VMAT_LOAD_STORE_LANES); + + /* When we support SELECT_VL pattern, we dynamic adjust + the memory address by .SELECT_VL result. + + The result of .SELECT_VL is the number of elements to + be processed of each iteration. So the memory address + adjustment operation should be: + + addr = addr + .SELECT_VL (ARG..) * step; + */ + gimple *ptr_incr; + tree loop_len + = vect_get_loop_len (loop_vinfo, gsi, loop_lens, 1, aggr_type, 0, 0); + tree len_type = TREE_TYPE (loop_len); + /* Since the outcome of .SELECT_VL is element size, we should adjust + it into bytesize so that it can be used in address pointer variable + amount IVs adjustment. */ + tree tmp = fold_build2 (MULT_EXPR, len_type, loop_len, + wide_int_to_tree (len_type, wi::to_widest (step))); + tree bump = make_temp_ssa_name (len_type, NULL, "ivtmp"); + gassign *assign = gimple_build_assign (bump, tmp); + gsi_insert_before (gsi, assign, GSI_SAME_STMT); + return bump; +} + /* Check and perform vectorization of BUILT_IN_BSWAP{16,32,64,128}. */ static bool @@ -8655,11 +8702,21 @@ vectorizable_store (vec_info *vinfo, slp_node, &gs_info, &dataref_ptr, &vec_offsets); else - dataref_ptr - = vect_create_data_ref_ptr (vinfo, first_stmt_info, aggr_type, - simd_lane_access_p ? loop : NULL, - offset, &dummy, gsi, &ptr_incr, - simd_lane_access_p, bump); + { + if (loop_lens && LOOP_VINFO_USING_SELECT_VL_P (loop_vinfo) + && memory_access_type != VMAT_INVARIANT) + bump = vect_get_loop_variant_data_ptr_increment ( + vinfo, aggr_type, gsi, loop_lens, dr_info, + memory_access_type); + + if (j != 0) + gcc_assert (!LOOP_VINFO_USING_SELECT_VL_P (loop_vinfo)); + dataref_ptr + = vect_create_data_ref_ptr (vinfo, first_stmt_info, aggr_type, + simd_lane_access_p ? loop : NULL, + offset, &dummy, gsi, &ptr_incr, + simd_lane_access_p, bump); + } } else { @@ -10046,11 +10103,21 @@ vectorizable_load (vec_info *vinfo, &vec_offsets); } else - dataref_ptr - = vect_create_data_ref_ptr (vinfo, first_stmt_info, aggr_type, - at_loop, - offset, &dummy, gsi, &ptr_incr, - simd_lane_access_p, bump); + { + if (loop_lens && LOOP_VINFO_USING_SELECT_VL_P (loop_vinfo) + && memory_access_type != VMAT_INVARIANT) + bump = vect_get_loop_variant_data_ptr_increment ( + vinfo, aggr_type, gsi, loop_lens, dr_info, + memory_access_type); + + if (j != 0) + gcc_assert (!LOOP_VINFO_USING_SELECT_VL_P (loop_vinfo)); + dataref_ptr + = vect_create_data_ref_ptr (vinfo, first_stmt_info, aggr_type, + at_loop, offset, &dummy, gsi, + &ptr_incr, simd_lane_access_p, + bump); + } if (mask) vec_mask = vec_masks[0]; } diff --git a/gcc/tree-vectorizer.h b/gcc/tree-vectorizer.h index 1e44f8542d7..af25d20bd7e 100644 --- a/gcc/tree-vectorizer.h +++ b/gcc/tree-vectorizer.h @@ -825,6 +825,11 @@ public: (b) can iterate more than once. */ bool using_decrementing_iv_p; + /* True if we've decided to use output of select_vl to adjust IV of + both loop control and data reference pointer. This is only true + for single-rgroup control. */ + bool using_select_vl_p; + /* True if we've decided to use partially-populated vectors for the epilogue of loop. */ bool epil_using_partial_vectors_p; @@ -898,6 +903,7 @@ public: #define LOOP_VINFO_CAN_USE_PARTIAL_VECTORS_P(L) (L)->can_use_partial_vectors_p #define LOOP_VINFO_USING_PARTIAL_VECTORS_P(L) (L)->using_partial_vectors_p #define LOOP_VINFO_USING_DECREMENTING_IV_P(L) (L)->using_decrementing_iv_p +#define LOOP_VINFO_USING_SELECT_VL_P(L) (L)->using_select_vl_p #define LOOP_VINFO_EPIL_USING_PARTIAL_VECTORS_P(L) \ (L)->epil_using_partial_vectors_p #define LOOP_VINFO_PARTIAL_LOAD_STORE_BIAS(L) (L)->partial_load_store_bias