Re: [RFC] ifcvt: Account for parallelism when costing noce sequences

> On Aug 13, 2026, at 01:07, Kyrylo Tkachov <[email protected]> wrote:
> 
> Hello,
> 
>> On 12 Aug 2026, at 12:39, wangjue <[email protected]> wrote:
>> 
>> From: juewang <[email protected]>
>> 
>> seq_cost treats every instruction in a replacement sequence as serial.
>> For superscalar targets this can overestimate the cost of independent
>> register operations and reject profitable if-conversion.
>> 
> 
> I like the idea, and it makes sense.
> One thing I’ve been hitting with my if-conversion work recently is that if-conversion increasing the dependency chain length is what’s hurting wide cores. Adding more instructions that can go parallel is not a problem otherwise.

Hi Jue, [please correct me if I guessed your first name wrong]

I've also reviewed this, and it generally looks good to me.  Some questions and comments below.

> 
>> Estimate the dependency level of simple, single-cycle register operations
>> and cost each level using the target issue rate.  Keep the existing serial
>> cost for size optimization and for sequences that need resource or alias
>> analysis.
>> 
> 
> I notice that mips has a pretty elaborate mips_seq_time mechanism. I wouldn’t advocate using it, just found it interesting when looking around.
> 
>> gcc/ChangeLog:
>> 
>> * ifcvt.cc (noce_parallel_cost_node): New.
>> (noce_parallel_seq_cost): New.
>> (default_noce_conversion_profitable_p): Use it.
>> ---
>> gcc/ifcvt.cc | 70 +++++++++++++++++++++++++++++++++++++++++++++++++++-
>> 1 file changed, 69 insertions(+), 1 deletion(-)
>> 
>> diff --git a/gcc/ifcvt.cc b/gcc/ifcvt.cc
>> index 5ea25f8fbe7..25874f006e6 100644
>> --- a/gcc/ifcvt.cc
>> +++ b/gcc/ifcvt.cc
>> @@ -803,6 +803,74 @@ noce_reversed_cond_code (struct noce_if_info *if_info)
>>  return reversed_comparison_code (if_info->cond, if_info->jump);
>> }
>> 
>> +/* A destination and its dependency level in a noce sequence.  */
>> +
>> +struct noce_parallel_cost_node
>> +{
>> +  rtx dest;
>> +  unsigned int level;
>> +};
>> +
>> +/* Estimate the cost of SEQ using the target issue rate for independent,
>> +   single-cycle register operations.  */
>> +
>> +static unsigned int
>> +noce_parallel_seq_cost (rtx_insn *seq, bool speed_p)
>> +{
>> +  unsigned int serial_cost = seq_cost (seq, speed_p);
>> +
>> +  if (!speed_p)
>> +    return serial_cost;
>> +
>> +  unsigned int issue_rate = targetm.sched.issue_rate ();
> 
> You first need to check that targetm.sched.issue_rate is non-null.
> I wonder if the schedule issue_rate is too coarse. The midend also uses reassociation width as an estimate of CPU parallelism. On aarch64 at least we describe different widths for int, fp, and vector reassociation.
> Have you considered using that hook instead?
> Thanks,
> Kyrill
> 
>> +  if (issue_rate <= 1)
>> +    return serial_cost;
>> +
>> +  auto_vec<noce_parallel_cost_node> nodes;
>> +  auto_vec<unsigned int> insns_per_level;
>> +
>> +  for (rtx_insn *insn = seq; insn; insn = NEXT_INSN (insn))
>> +    {
>> +      if (!NONDEBUG_INSN_P (insn))
>> + continue;
>> +
>> +      rtx set = single_set (insn);
>> +      if (!set)
>> + return serial_cost;
>> +
>> +      rtx dest = SET_DEST (set);
>> +      rtx src = SET_SRC (set);
>> +
>> +      if (!REG_P (dest)
>> +  || contains_mem_rtx_p (src)
>> +  || side_effects_p (src)
>> +  || may_trap_p (src)
>> +  || set_rtx_cost (set, speed_p) != COSTS_N_INSNS (1))
>> + return serial_cost;
>> +
>> +      unsigned int level = 0;
>> +      for (unsigned int i = 0; i < nodes.length (); ++i)
>> + if (reg_overlap_mentioned_p (nodes[i].dest, src))
>> +  level = MAX (level, nodes[i].level + 1);
>> +
>> +      if (insns_per_level.length () <= level)
>> + insns_per_level.safe_grow_cleared (level + 1, true);
>> +      ++insns_per_level[level];
>> +
>> +      noce_parallel_cost_node node = { dest, level };
>> +      nodes.safe_push (node);
>> +    }

Could you, please, add comments as to what the above loop analyzes?  After staring at it for 5 minutes I'm /guessing/ that it searches for the longest chain of instructions that set/use the same register?  And then use the cost of the longest chain as the "parallel" cost of the whole sequence?

>> +
>> +  if (nodes.is_empty ())
>> +    return serial_cost;

If I'm reading the code right, the only way "nodes" can be empty AND we reached the above point is when all insns in the sequence are DEBUG_INSN.  If that's correct, I would appreciate a comment that the above is a corner-case check. 

>> +
>> +  unsigned int parallel_cost = 0;
>> +  for (unsigned int i = 0; i < insns_per_level.length (); ++i)
>> +    parallel_cost += COSTS_N_INSNS (CEIL (insns_per_level[i], issue_rate));
>> +
>> +  return MIN (serial_cost, parallel_cost);

It would be interesting to have two data points here:
1. How often (percentage) the above analysis succeeds and we calculate parallel_cost.
E.g., is it
- "parallel_cost calculation is successful in 10% of noce_parallel_seq_cost() invocations."
or is it
- "parallel_cost calculation is successful in .1% of noce_parallel_seq_cost() invocations." 
?

2. What is the histogram of how far parallel_cost is from serial_cost?
E.g., something like this:
- 1.0 >= parallel_cost/serial_cost > 0.8: 50% probability
- 0.8 >= parallel_cost/serial_cost > 0.6: 25% probability
- 0.6 >= parallel_cost/serial_cost > 0.4: 15% probability
- 0.4 >= parallel_cost/serial_cost > 0.2:  8% probability
- 0.2 >= parallel_cost/serial_cost > 0.0:  2% probability

Having these data points (from, e.g., SPEC CPU or GCC bootstrap builds) will set expectations for the future, when the next developer guesses whether it's OK that parallel_cost is calculated only in 0.0001% of invocations.

Thanks!

--
Maxim Kuvyrkov
Garden City Compilers