> -----Original Message-----
> From: Jakub Jelinek <jakub@redhat.com>
> Sent: Monday, October 2, 2023 2:21 PM
> To: Tamar Christina <Tamar.Christina@arm.com>
> Cc: gcc-patches@gcc.gnu.org; nd <nd@arm.com>; jwakely@redhat.com
> Subject: Re: [PATCH]middle-end: Recursively check
> is_trivially_copyable_or_pair in vec.h
> 
> On Mon, Oct 02, 2023 at 01:38:53PM +0100, Tamar Christina wrote:
> > Hi All,
> >
> > I recently committed a patch that uses a nested std::pair in the second
> argument.
> > It temporarily adds a second ranking variable for sorting and then later drops
> it.
> >
> > This hits the newly added assert in vec.h.  This assert made some
> > relaxation for std::pair but doesn't allow this case through.  The
> > patch allows a recursive std::pair in the second argument which fixes
> bootstrap.
> 
> I must say I still don't understand why using a struct ifcvt_arg_entry { tree arg;
> unsigned len, occur; }; with comments describing what the members mean
> wouldn't be a better fix, in the sorting function what exactly means
> x{1,2}.second.first and x{1,2}.second.second isn't easily understandable,
> neither from the identifiers nor from any comments.
> Seems because you use 2 separate vectors, one with just tree elements and
> another with those tree elements + 2 unsigned values cached from it for the
> sorting purpose and then rewrite the original tree vector after sorting, I don't
> really see why nested std::pair would be a better match for it than a named
> structure.  Furthermore, why populate args first, then compute the extra 2
> integers in another loop pushing to argsKV and finally overwrite args with
> sorted values?  Can't the first loop push tree with the 2 integers already?
> what is the point of not using this structure later on when both args and
> argsKV vectors are live until the end of the same function?
> Can't you either pass that argsKV to others, having just one vector, or at least
> release the other vector when you don't really need it?
> Formatting style, swap? arg1 : arg0 isn't correctly formatted, missing space
> before ?.
> 
> Also, ArgEntry is CamelCase which we (usually) don't use in GCC and
> additionally doesn't seem to be unique enough for ODR purposes.
> Ditto argsKV.
> 

Hi All,

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 (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 a8c915913aed267edfb3ebd2c530aeca7cf51832..f7037bd42494b3982d2efd593ba276812b8d2f4f 100644
--- a/gcc/tree-if-conv.cc
+++ b/gcc/tree-if-conv.cc
@@ -1927,11 +1927,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;
@@ -1941,11 +1962,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))
 	{
@@ -2010,22 +2031,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_");
@@ -2045,6 +2065,25 @@ gen_phi_nest_statement (gphi *phi, gimple_stmt_iterator *gsi,
   return lhs;
 }
 
+static int
+cmp_arg_entry (const void *p1, const void *p2)
+{
+  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.
 
@@ -2167,61 +2206,53 @@ predicate_scalar_phi (gphi *phi, gimple_stmt_iterator *gsi)
   /* Create hashmap for PHI node which contain vector of argument indexes
      having the same value.  */
   bool swap = false;
-  hash_map<tree_operand_hash, auto_vec<int> > phi_arg_map;
+  hash_map<tree_operand_hash, 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);
       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 entry : phi_arg_map)
     {
       unsigned int len = 0;
-      for (int index : phi_arg_map.get (args[i]))
+      for (int index : entry.second)
 	{
 	  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 = entry.second.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 ({ entry.first, len, occur, entry.second });
     }
 
   /* 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.qsort (cmp_arg_entry);
 
   /* 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)
@@ -2235,8 +2266,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.  */
@@ -2252,8 +2283,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))