[gcc r14-4716] ifcvt: rewrite args handling to remove lookups

[gcc r14-4716] ifcvt: rewrite args handling to remove lookups

[Tamar Christina]

https://gcc.gnu.org/g:dd28f90c95378bf8ebb82a3dfdf24a6ad190877a

commit r14-4716-gdd28f90c95378bf8ebb82a3dfdf24a6ad190877a
Author: Tamar Christina <tamar.christina@arm.com>
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
      <L18>:;
 */
 
-#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 <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;
@@ -1946,11 +1966,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))
 	{
@@ -2015,22 +2035,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_");
@@ -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<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)
@@ -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))