From: Tamar Christina <Tamar.Christina@arm.com>
To: Jakub Jelinek <jakub@redhat.com>
Cc: "gcc-patches@gcc.gnu.org" <gcc-patches@gcc.gnu.org>,
nd <nd@arm.com>, "jwakely@redhat.com" <jwakely@redhat.com>
Subject: RE: [PATCH]middle-end: Recursively check is_trivially_copyable_or_pair in vec.h
Date: Fri, 6 Oct 2023 02:23:06 +0000 [thread overview]
Message-ID: <VI1PR08MB5325D2898E3FBED916C22D1BFFC9A@VI1PR08MB5325.eurprd08.prod.outlook.com> (raw)
In-Reply-To: <ZR7EyesA9dBfVMsx@tucnak>
[-- Attachment #1: Type: text/plain, Size: 10860 bytes --]
>
> On Thu, Oct 05, 2023 at 02:01:40PM +0000, Tamar Christina wrote:
> > gcc/ChangeLog:
> >
> > * 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.
>
> > - /* 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. */
> > + auto_vec<tree> unique_args (num_args);
> > 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);
> > + unique_args.quick_push (arg);
> > phi_arg_map.get_or_insert (arg).safe_push (i);
> > }
>
> I meant instead of using another vector (unique_args) just do
> args.quick_push ({ arg, 0, 0, NULL });
> above (to avoid needing another allocation etc.).
>
Arggs.. Sorry I completely misunderstood what you meant.. It should be fixed now.
Also realized I forgot to comment the compare function as you asked before.
--
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.
Bootstrapped Regtested on aarch64-none-linux-gnu, x86_64-linux-gnu
and no issues.
Ok for master?
Thanks,
Tamar
gcc/ChangeLog:
* 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.
--- inline copy of patch ---
diff --git a/gcc/tree-if-conv.cc b/gcc/tree-if-conv.cc
index f76e0d8f2e6e0f59073fa8484b0b2c7a6cdc9783..a0c11cf5e30b1127166e1a51371f6521a22c45f2 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
<L18>:;
*/
-#define INCLUDE_ALGORITHM
#include "config.h"
#include "system.h"
#include "coretypes.h"
@@ -1937,11 +1936,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 <int> *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<int> *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;
@@ -1951,11 +1971,11 @@ gen_phi_arg_condition (gphi *phi, vec<int> *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))
{
@@ -2020,22 +2040,21 @@ gen_phi_arg_condition (gphi *phi, vec<int> *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<tree_operand_hash, auto_vec<int>> &phi_arg_map,
- gimple **res_stmt, tree lhs0, vec<tree> &args,
- unsigned idx)
+ gimple **res_stmt, tree lhs0,
+ vec<struct ifcvt_arg_entry> &args, unsigned idx)
{
if (idx == args.length ())
- return args[idx - 1];
+ return args[idx - 1].arg;
- vec<int> *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_");
@@ -2055,6 +2074,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.
@@ -2180,58 +2229,55 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi)
hash_map<tree_operand_hash, auto_vec<int> > phi_arg_map;
unsigned int num_args = gimple_phi_num_args (phi);
/* Vector of different PHI argument values. */
- auto_vec<tree> args (num_args);
+ auto_vec<ifcvt_arg_entry_t> 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 <tree, std::pair <unsigned, unsigned>> ArgEntry;
- auto_vec<ArgEntry> 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<int> *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<int> *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)
@@ -2245,8 +2291,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. */
@@ -2262,8 +2308,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))
[-- Attachment #2: rb17797.patch --]
[-- Type: application/octet-stream, Size: 8770 bytes --]
diff --git a/gcc/tree-if-conv.cc b/gcc/tree-if-conv.cc
index f76e0d8f2e6e0f59073fa8484b0b2c7a6cdc9783..a0c11cf5e30b1127166e1a51371f6521a22c45f2 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
<L18>:;
*/
-#define INCLUDE_ALGORITHM
#include "config.h"
#include "system.h"
#include "coretypes.h"
@@ -1937,11 +1936,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 <int> *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<int> *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;
@@ -1951,11 +1971,11 @@ gen_phi_arg_condition (gphi *phi, vec<int> *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))
{
@@ -2020,22 +2040,21 @@ gen_phi_arg_condition (gphi *phi, vec<int> *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<tree_operand_hash, auto_vec<int>> &phi_arg_map,
- gimple **res_stmt, tree lhs0, vec<tree> &args,
- unsigned idx)
+ gimple **res_stmt, tree lhs0,
+ vec<struct ifcvt_arg_entry> &args, unsigned idx)
{
if (idx == args.length ())
- return args[idx - 1];
+ return args[idx - 1].arg;
- vec<int> *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_");
@@ -2055,6 +2074,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.
@@ -2180,58 +2229,55 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi)
hash_map<tree_operand_hash, auto_vec<int> > phi_arg_map;
unsigned int num_args = gimple_phi_num_args (phi);
/* Vector of different PHI argument values. */
- auto_vec<tree> args (num_args);
+ auto_vec<ifcvt_arg_entry_t> 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 <tree, std::pair <unsigned, unsigned>> ArgEntry;
- auto_vec<ArgEntry> 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<int> *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<int> *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)
@@ -2245,8 +2291,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. */
@@ -2262,8 +2308,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))
next prev parent reply other threads:[~2023-10-06 2:23 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-10-02 12:38 Tamar Christina
2023-10-02 13:21 ` Jakub Jelinek
2023-10-02 13:28 ` Tamar Christina
2023-10-03 10:27 ` Tamar Christina
2023-10-03 11:01 ` Jakub Jelinek
2023-10-03 11:41 ` Tamar Christina
2023-10-03 11:52 ` Jakub Jelinek
2023-10-05 14:01 ` Tamar Christina
2023-10-05 14:14 ` Jakub Jelinek
2023-10-06 2:23 ` Tamar Christina [this message]
2023-10-06 6:38 ` Jakub Jelinek
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=VI1PR08MB5325D2898E3FBED916C22D1BFFC9A@VI1PR08MB5325.eurprd08.prod.outlook.com \
--to=tamar.christina@arm.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=jakub@redhat.com \
--cc=jwakely@redhat.com \
--cc=nd@arm.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).