On Tue, Oct 03, 2023 at 10:27:16AM +0000, Tamar Christina wrote:
> +/* Structure used to track meta-data on PHI arguments used to generate
> + most efficient comparison sequence to slatten a PHI node. */
^^^ typo (at least, never heard
of this word, and wiktionary doesn't know it either (except for
Dannish/Swedish))
> @@ -2045,6 +2065,25 @@ gen_phi_nest_statement (gphi *phi,
> gimple_stmt_iterator *gsi,
> return lhs;
> }
>
Perhaps add a short function comment here?
> +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;
> +}
> +
> @@ -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);
I admit I don't know what you're using the args vector later on for and
whether its ordering affects code generation, but because you qsort it I
assume it does. My worry is that a hash_map traversal might not be the same
order on all hosts and similarly qsort doesn't achieve stable sorting
in case num_compares and occurrs members are equal for two or more different
arguments. Can that ever happen? 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.
Jakub
