回复：[RFC] ifcvt: Account for parallelism when cos ting noce sequences

Hi Maxim Kuvyrkov

> 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?

Thanks.  That is close, but it considers both dependency depth and
the number of instructions at each level.
For each instruction, the loop finds earlier instructions whose
destinations are used by its source and places it one level after the
deepest producer.  Independent instructions remain at the same level.
The cost is then calculated for each level using the available
parallelism and summed across all levels.  I will add a comment
explaining this.

> 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. 

Yes, that is correct.  The check could only handle an all-debug
sequence.  I have removed it from the updated draft.

> 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

I instrumented the draft and built all SPEC CPU2017 Integer rate
benchmarks on RISC-V.  I have not collected data for other targets yet.

The analysis succeeded in 16,947 of 30,120 invocations (56.26%).
These calls came from 423 compiler processes.  Among the successful
analyses, 15,024 cases (88.65%) produced a lower cost.

The parallel_cost / serial_cost histogram, using successful analyses
as the denominator, is:
  1.0 >= ratio > 0.8: 1,955 (11.54%)
  0.8 >= ratio > 0.6: 8,017 (47.31%)
  0.6 >= ratio > 0.4: 6,820 (40.24%)
  0.4 >= ratio > 0.2:   155 ( 0.91%)
  0.2 >= ratio > 0.0:     0 ( 0.00%)

Regards,
Wang Jue