From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2066) id 73A00389683E; Mon, 31 May 2021 06:04:09 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 73A00389683E Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Jiu Fu Guo To: gcc-cvs@gcc.gnu.org Subject: [gcc(refs/users/guojiufu/heads/personal-branch)] Use fast type for loop idx X-Act-Checkin: gcc X-Git-Author: Jiufu Guo X-Git-Refname: refs/users/guojiufu/heads/personal-branch X-Git-Oldrev: 291bcf3c8d45c29288ecf73be62e613411d0ab08 X-Git-Newrev: fe3ff943d605b91cd2a32cc770b49117e1c3e19f Message-Id: <20210531060409.73A00389683E@sourceware.org> Date: Mon, 31 May 2021 06:04:09 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 31 May 2021 06:04:09 -0000 https://gcc.gnu.org/g:fe3ff943d605b91cd2a32cc770b49117e1c3e19f commit fe3ff943d605b91cd2a32cc770b49117e1c3e19f Author: Jiufu Guo Date: Thu May 20 14:26:25 2021 +0800 Use fast type for loop idx Diff: --- gcc/tree-ssa-loop-split.c | 166 +++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 151 insertions(+), 15 deletions(-) diff --git a/gcc/tree-ssa-loop-split.c b/gcc/tree-ssa-loop-split.c index 4a48e27fb8b..43fd709302d 100644 --- a/gcc/tree-ssa-loop-split.c +++ b/gcc/tree-ssa-loop-split.c @@ -1599,7 +1599,7 @@ split_loop_on_cond (struct loop *loop) Return NULL_TREE, if overflow/wrap will not happen. */ static tree -get_wrap_assumption (class loop *loop, edge *exit) +get_wrap_assumption (class loop *loop, edge *exit, gphi **idx_phi) { int i; edge e; @@ -1644,14 +1644,16 @@ get_wrap_assumption (class loop *loop, edge *exit) if (code != NE_EXPR && code != LT_EXPR && code != LE_EXPR) continue; + /* Check if idx is a valid SSA. */ + if (TREE_CODE (idx) != SSA_NAME) + continue; + /* Filter conversion from idx. */ - tree cmp_idx = idx; + int inc_cnt = 0; tree small_type = TREE_TYPE (idx); tree large_type = small_type; - gimple *stmt = NULL; - if (TREE_CODE (idx) == SSA_NAME) - stmt = SSA_NAME_DEF_STMT (idx); - while (stmt && is_gimple_assign (stmt) + gimple *stmt = SSA_NAME_DEF_STMT (idx); + while (is_gimple_assign (stmt) && flow_bb_inside_loop_p (loop, gimple_bb (stmt))) { enum tree_code code = gimple_assign_rhs_code (stmt); @@ -1670,7 +1672,14 @@ get_wrap_assumption (class loop *loop, edge *exit) } else if (PLUS_EXPR == code && integer_onep (gimple_assign_rhs2 (stmt))) - idx = gimple_assign_rhs1 (stmt); + { + idx = gimple_assign_rhs1 (stmt); + + /* At most one increament stmt. */ + inc_cnt++; + if (inc_cnt > 1) + break; + } else break; @@ -1679,6 +1688,11 @@ get_wrap_assumption (class loop *loop, edge *exit) stmt = SSA_NAME_DEF_STMT (idx); } + /* At last it should a PHI which is iv. */ + if (gimple_code (stmt) != GIMPLE_PHI) + continue; + *idx_phi = as_a (stmt); + /* Check if idx is iv with base and step. */ affine_iv iv; tree iv_niters = NULL_TREE; @@ -1716,6 +1730,121 @@ get_wrap_assumption (class loop *loop, edge *exit) return NULL_TREE; } +/* Update the idx and bnd with faster type for no wrap/oveflow loop. */ + +static bool +update_idx_bnd_type (class loop *loop, gimple *last, gphi *idx_phi) +{ + /* Filter type conversion + i = phi (b, n) + .. + n0 = ik + 1 + n1 = (type)n0 + if (i != bnd) or if (n != bnd) + .. + n = ()nl */ + auto convert_src = [&loop](tree idx) -> gimple * { + gimple *stmt = SSA_NAME_DEF_STMT (idx); + while (is_gimple_assign (stmt) + && flow_bb_inside_loop_p (loop, gimple_bb (stmt))) + { + if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))) + idx = gimple_assign_rhs1 (stmt); + else + break; + + if (TREE_CODE (idx) != SSA_NAME) + break; + stmt = SSA_NAME_DEF_STMT (idx); + } + return stmt; + }; + + /* Get increase statement. */ + edge latch_e = loop_latch_edge (loop); + tree next = PHI_ARG_DEF_FROM_EDGE (idx_phi, latch_e); + gimple *inc_stmt = convert_src (next); + if (!is_gimple_assign (inc_stmt) + || gimple_assign_rhs_code (inc_stmt) != PLUS_EXPR + || !flow_bb_inside_loop_p (loop, gimple_bb (inc_stmt))) + return false; + + /* Check gcond stmt for bnd and idx/next. */ + gcond *gc = as_a (last); + tree bnd = gimple_cond_rhs (gc); + tree idx = gimple_cond_lhs (gc); + bool inv = false; + if (expr_invariant_in_loop_p (loop, idx)) + { + inv = true; + std::swap (idx, bnd); + } + + gimple *stmt = convert_src (idx); + bool cmp_next = stmt == inc_stmt; + + /* Use sizetype as machine fast type, ok for all targets? */ + tree fast_type = sizetype; + + /* New base and new bound. */ + edge pre_e = loop_preheader_edge (loop); + tree base = PHI_ARG_DEF_FROM_EDGE (idx_phi, pre_e); + tree new_base = fold_convert (fast_type, base); + tree new_bnd = fold_convert (fast_type, bnd); + gimple_seq seq = NULL; + new_base = force_gimple_operand (new_base, &seq, true, NULL_TREE); + if (seq) + gsi_insert_seq_on_edge_immediate (pre_e, seq); + seq = NULL; + new_bnd = force_gimple_operand (new_bnd, &seq, true, NULL_TREE); + if (seq) + gsi_insert_seq_on_edge_immediate (pre_e, seq); + + /* new_i = phi (new_b, new_n) + new_n = new_i + 1 */ + basic_block bb = gimple_bb (idx_phi); + const char *name = "idx"; + tree new_idx = make_temp_ssa_name (fast_type, NULL, name); + tree new_next = make_temp_ssa_name (fast_type, NULL, name); + gphi *newphi = create_phi_node (new_idx, bb); + add_phi_arg (newphi, new_base, pre_e, UNKNOWN_LOCATION); + add_phi_arg (newphi, new_next, latch_e, UNKNOWN_LOCATION); + + /* New increase stmt. */ + tree step = gimple_assign_rhs2 (inc_stmt); + gcc_assert (TREE_CODE (step) == INTEGER_CST); + step = fold_convert (fast_type, step); + new_idx = PHI_RESULT (newphi); + gimple *new_inc = gimple_build_assign (new_next, PLUS_EXPR, new_idx, step); + gimple_stmt_iterator gsi = gsi_for_stmt (inc_stmt); + gsi_insert_before (&gsi, new_inc, GSI_SAME_STMT); + + /* Update gcond. */ + tree cmp_idx = cmp_next ? new_next : new_idx; + gimple_cond_set_lhs (gc, inv ? new_bnd : cmp_idx); + gimple_cond_set_rhs (gc, inv ? cmp_idx : new_bnd); + update_stmt (gc); + + tree type = TREE_TYPE (next); + stmt = gimple_build_assign (next, fold_convert (type, new_next)); + gsi = gsi_for_stmt (inc_stmt); + gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); + + gsi = gsi_for_stmt (inc_stmt); + gsi_remove (&gsi, true); + + idx = PHI_RESULT (idx_phi); + type = TREE_TYPE (idx); + stmt = gimple_build_assign (idx, fold_convert (type, new_idx)); + gsi = gsi_start_bb (bb); + gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); + + gsi = gsi_for_stmt (idx_phi); + gsi_remove (&gsi, true); + + return true; +} + /* Split out a new loop which would not wrap/overflow, under the guard that WRAP_ASSUMPTION will not be true. */ @@ -1730,11 +1859,12 @@ split_wrap_boundary (class loop *loop, edge e, tree no_wrap_cond) /* Version the loop. */ initialize_original_copy_tables (); basic_block cond_bb; - loop_version (loop, no_wrap_cond, &cond_bb, - profile_probability::very_likely (), - profile_probability::very_unlikely (), - profile_probability::very_likely (), - profile_probability::very_unlikely (), true); + class loop *loop1 + = loop_version (loop, no_wrap_cond, &cond_bb, + profile_probability::very_likely (), + profile_probability::very_unlikely (), + profile_probability::very_likely (), + profile_probability::very_unlikely (), true); free_original_copy_tables (); /* Insert the statements that feed COND. */ @@ -1804,9 +1934,15 @@ split_loop_on_wrap (class loop *loop) free (bbs); edge e; - tree nowrap_assumption = get_wrap_assumption (loop, &e); - if (nowrap_assumption && split_wrap_boundary (loop, e, nowrap_assumption)) - return true; + gphi *idx_phi; + tree assumption = get_wrap_assumption (loop, &e, &idx_phi); + + if (assumption && split_wrap_boundary (loop, e, assumption)) + { + // rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); + update_idx_bnd_type (loop, last_stmt (e->src), idx_phi); + return true; + } return false; }