From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1984) id F38FC385841B; Wed, 18 Oct 2023 08:55:01 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org F38FC385841B DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1697619302; bh=/xuOcoXdbdY5y/Hek+sCfpf4eBbQZQqOs90JVg0p8yM=; h=From:To:Subject:Date:From; b=K3xF2m9mGEmACAovC+8YJia1YR4V4Squ0yNUUWXlLDuFKb0uY/M57p8VoRqmjWqWr DWUar1xwQhs2w6ZHnfb4oOgQnv8B/Xq7L+Xx5umcy8GfSgqgJOgGsOePwjsPH34ey6 v347BzLEVnTTWpdEYavvADPkAuCw9/qdhCEJRors= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Tamar Christina To: gcc-cvs@gcc.gnu.org Subject: [gcc r14-4716] ifcvt: rewrite args handling to remove lookups X-Act-Checkin: gcc X-Git-Author: Tamar Christina X-Git-Refname: refs/heads/master X-Git-Oldrev: 04227acbe9e6c60d1e314a6b4f2d949c07f30baa X-Git-Newrev: dd28f90c95378bf8ebb82a3dfdf24a6ad190877a Message-Id: <20231018085501.F38FC385841B@sourceware.org> Date: Wed, 18 Oct 2023 08:55:01 +0000 (GMT) List-Id: https://gcc.gnu.org/g:dd28f90c95378bf8ebb82a3dfdf24a6ad190877a commit r14-4716-gdd28f90c95378bf8ebb82a3dfdf24a6ad190877a Author: Tamar Christina Date: Wed Oct 18 09:49:36 2023 +0100 ifcvt: rewrite args handling to remove lookups This refactors the code to remove the args cache and index lookups in favor of a single structure. It also again, removes the use of std::sort as previously requested but avoids the new asserts in trunk. gcc/ChangeLog: PR tree-optimization/109154 * tree-if-conv.cc (INCLUDE_ALGORITHM): Remove. (typedef struct ifcvt_arg_entry): New. (cmp_arg_entry): New. (gen_phi_arg_condition, gen_phi_nest_statement, predicate_scalar_phi): Use them. Diff: --- gcc/tree-if-conv.cc | 130 +++++++++++++++++++++++++++++++++++----------------- 1 file changed, 88 insertions(+), 42 deletions(-) diff --git a/gcc/tree-if-conv.cc b/gcc/tree-if-conv.cc index edce842db940..c381d14b8013 100644 --- a/gcc/tree-if-conv.cc +++ b/gcc/tree-if-conv.cc @@ -80,7 +80,6 @@ along with GCC; see the file COPYING3. If not see :; */ -#define INCLUDE_ALGORITHM #include "config.h" #include "system.h" #include "coretypes.h" @@ -1932,11 +1931,32 @@ gen_simplified_condition (tree cond, scalar_cond_masked_set_type &cond_set) return cond; } +/* Structure used to track meta-data on PHI arguments used to generate + most efficient comparison sequence to slatten a PHI node. */ + +typedef struct ifcvt_arg_entry +{ + /* The PHI node argument value. */ + tree arg; + + /* The number of compares required to reach this PHI node from start of the + BB being if-converted. */ + unsigned num_compares; + + /* The number of times this PHI node argument appears in the current PHI + node. */ + unsigned occurs; + + /* The indices at which this PHI arg occurs inside the PHI node. */ + vec *indexes; +} ifcvt_arg_entry_t; + /* Produce condition for all occurrences of ARG in PHI node. Set *INVERT as to whether the condition is inverted. */ static tree -gen_phi_arg_condition (gphi *phi, vec *occur, gimple_stmt_iterator *gsi, +gen_phi_arg_condition (gphi *phi, ifcvt_arg_entry_t &arg, + gimple_stmt_iterator *gsi, scalar_cond_masked_set_type &cond_set, bool *invert) { int len; @@ -1946,11 +1966,11 @@ gen_phi_arg_condition (gphi *phi, vec *occur, gimple_stmt_iterator *gsi, edge e; *invert = false; - len = occur->length (); + len = arg.indexes->length (); gcc_assert (len > 0); for (i = 0; i < len; i++) { - e = gimple_phi_arg_edge (phi, (*occur)[i]); + e = gimple_phi_arg_edge (phi, (*arg.indexes)[i]); c = bb_predicate (e->src); if (is_true_predicate (c)) { @@ -2015,22 +2035,21 @@ gen_phi_arg_condition (gphi *phi, vec *occur, gimple_stmt_iterator *gsi, static tree gen_phi_nest_statement (gphi *phi, gimple_stmt_iterator *gsi, scalar_cond_masked_set_type &cond_set, tree type, - hash_map> &phi_arg_map, - gimple **res_stmt, tree lhs0, vec &args, - unsigned idx) + gimple **res_stmt, tree lhs0, + vec &args, unsigned idx) { if (idx == args.length ()) - return args[idx - 1]; + return args[idx - 1].arg; - vec *indexes = phi_arg_map.get (args[idx - 1]); bool invert; - tree cond = gen_phi_arg_condition (phi, indexes, gsi, cond_set, &invert); - tree arg1 = gen_phi_nest_statement (phi, gsi, cond_set, type, phi_arg_map, - res_stmt, lhs0, args, idx + 1); + tree cond = gen_phi_arg_condition (phi, args[idx - 1], gsi, cond_set, + &invert); + tree arg1 = gen_phi_nest_statement (phi, gsi, cond_set, type, res_stmt, lhs0, + args, idx + 1); unsigned prev = idx; unsigned curr = prev - 1; - tree arg0 = args[curr]; + tree arg0 = args[curr].arg; tree rhs, lhs; if (idx > 1) lhs = make_temp_ssa_name (type, NULL, "_ifc_"); @@ -2050,6 +2069,36 @@ gen_phi_nest_statement (gphi *phi, gimple_stmt_iterator *gsi, return lhs; } +/* When flattening a PHI node we have a choice of which conditions to test to + for all the paths from the start of the dominator block of the BB with the + PHI node. If the PHI node has X arguments we have to only test X - 1 + conditions as the last one is implicit. It does matter which conditions we + test first. We should test the shortest condition first (distance here is + measures in the number of logical operators in the condition) and the + longest one last. This allows us to skip testing the most expensive + condition. To accomplish this we need to sort the conditions. P1 and P2 + are sorted first based on the number of logical operations (num_compares) + and then by how often they occur in the PHI node. */ + +static int +cmp_arg_entry (const void *p1, const void *p2, void * /* data. */) +{ + const ifcvt_arg_entry sval1 = *(const ifcvt_arg_entry *)p1; + const ifcvt_arg_entry sval2 = *(const ifcvt_arg_entry *)p2; + + if (sval1.num_compares < sval2.num_compares) + return -1; + else if (sval1.num_compares > sval2.num_compares) + return 1; + + if (sval1.occurs < sval2.occurs) + return -1; + else if (sval1.occurs > sval2.occurs) + return 1; + + return 0; +} + /* Replace a scalar PHI node with a COND_EXPR using COND as condition. This routine can handle PHI nodes with more than two arguments. @@ -2175,58 +2224,55 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) hash_map > phi_arg_map; unsigned int num_args = gimple_phi_num_args (phi); /* Vector of different PHI argument values. */ - auto_vec args (num_args); + auto_vec args; - /* Compute phi_arg_map. */ + /* Compute phi_arg_map, determine the list of unique PHI args and the indices + where they are in the PHI node. The indices will be used to determine + the conditions to apply and their complexity. */ for (i = 0; i < num_args; i++) { tree arg; arg = gimple_phi_arg_def (phi, i); if (!phi_arg_map.get (arg)) - args.quick_push (arg); + args.safe_push ({ arg, 0, 0, NULL }); phi_arg_map.get_or_insert (arg).safe_push (i); } - /* Determine element with max number of occurrences and complexity. Looking at only - number of occurrences as a measure for complexity isn't enough as all usages can - be unique but the comparisons to reach the PHI node differ per branch. */ - typedef std::pair > ArgEntry; - auto_vec argsKV; - for (i = 0; i < args.length (); i++) + /* Determine element with max number of occurrences and complexity. Looking + at only number of occurrences as a measure for complexity isn't enough as + all usages can be unique but the comparisons to reach the PHI node differ + per branch. */ + for (unsigned i = 0; i < args.length (); i++) { unsigned int len = 0; - for (int index : phi_arg_map.get (args[i])) + vec *indices = phi_arg_map.get (args[i].arg); + for (int index : *indices) { edge e = gimple_phi_arg_edge (phi, index); len += get_bb_num_predicate_stmts (e->src); } - unsigned occur = phi_arg_map.get (args[i])->length (); + unsigned occur = indices->length (); if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "Ranking %d as len=%d, idx=%d\n", i, len, occur); - argsKV.safe_push ({ args[i], { len, occur }}); + args[i].num_compares = len; + args[i].occurs = occur; + args[i].indexes = indices; } /* Sort elements based on rankings ARGS. */ - std::sort(argsKV.begin(), argsKV.end(), [](const ArgEntry &left, - const ArgEntry &right) { - return left.second < right.second; - }); - - for (i = 0; i < args.length (); i++) - args[i] = argsKV[i].first; + args.stablesort (cmp_arg_entry, NULL); /* Handle one special case when number of arguments with different values is equal 2 and one argument has the only occurrence. Such PHI can be handled as if would have only 2 arguments. */ - if (args.length () == 2 && phi_arg_map.get (args[0])->length () == 1) + if (args.length () == 2 + && args[0].indexes->length () == 1) { - vec *indexes; - indexes = phi_arg_map.get (args[0]); - index0 = (*indexes)[0]; - arg0 = args[0]; - arg1 = args[1]; + index0 = (*args[0].indexes)[0]; + arg0 = args[0].arg; + arg1 = args[1].arg; e = gimple_phi_arg_edge (phi, index0); cond = bb_predicate (e->src); if (TREE_CODE (cond) == TRUTH_NOT_EXPR) @@ -2240,8 +2286,8 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) if (!(is_cond_scalar_reduction (phi, &reduc, arg0 , arg1, &op0, &op1, true, &has_nop, &nop_reduc))) rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond), - swap? arg1 : arg0, - swap? arg0 : arg1); + swap ? arg1 : arg0, + swap ? arg0 : arg1); else { /* Convert reduction stmt into vectorizable form. */ @@ -2257,8 +2303,8 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi) { /* Common case. */ tree type = TREE_TYPE (gimple_phi_result (phi)); - gen_phi_nest_statement (phi, gsi, cond_set, type, phi_arg_map, - &new_stmt, res, args, 1); + gen_phi_nest_statement (phi, gsi, cond_set, type, &new_stmt, res, + args, 1); } if (dump_file && (dump_flags & TDF_DETAILS))