> On Tue, Oct 03, 2023 at 11:41:01AM +0000, Tamar Christina wrote:
> > > We have stablesort method instead of qsort but that would require
> > > consistent ordering in the vector (std::sort doesn't ensure stable
> > > sorting either).
> > >
> > > If it is a non-issue, the patch is ok with the above nits fixed.
> > > Otherwise perhaps we'd need to push in the first loop into the vector (but
> that
> > >       if (!phi_arg_map.get (arg))
> > > 	args.quick_push (arg);
> > >       phi_arg_map.get_or_insert (arg).safe_push (i); in there was
> > > quite inefficient, better would be
> > >       bool existed;
> > >       phi_arg_map.get_or_insert (arg, &existed).safe_push (i);
> > >       if (!existed)
> > > 	args.safe_push (ifcvt_arg_entry { arg, 0, 0, vNULL }); or something
> > > similar), plus use stablesort.  Or add another compared member which
> > > would be the first position.
> >
> > Hmm the problem here is that it would make the second loop that fills
> > in the len quadratic as it has to search for arg in the list.  I
> > suppose I could push a pointer to the struct instead of `i` in the
> > hashmap and the element into args and update the pointer as we go along?
> Would that work?
> 
> Only if the second loop traverses the hashmap elements and for each tries to
> find the corresponding vector element.
> If instead you do what you've done before in the second loop, walk the vector
> and for each arg in there lookup phi_args_map.get (v.arg) (but please just
> once, vanilla trunk looks it up twice in
>       for (int index : phi_arg_map.get (args[i]))
>         {
>           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 (); ), then I don't think
> it would be quadratic.

Fair enough, here's the updated patch. It should address all the concerns
and clean up the code 😊

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..635fce7a69af254dbc5aa9f829e6a053671d1d2c 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,25 @@ gen_phi_nest_statement (gphi *phi, gimple_stmt_iterator *gsi,
   return lhs;
 }
 
+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 +2218,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.  */
+  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);
     }
 
-  /* 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 (auto arg : unique_args)
     {
       unsigned int len = 0;
-      for (int index : phi_arg_map.get (args[i]))
+      vec<int> *indices = phi_arg_map.get (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.safe_push ({ arg, len, occur, indices });
     }
 
+  unique_args.release ();
   /* 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 +2280,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 +2297,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))

> 
> 	Jakub