Re: RISC-V: Add divmod instruction support

["Maciej W. Rozycki" <macro@orcam.me.uk>]

On Mon, 20 Feb 2023, Alexander Monakov wrote:

> > >  That's the kind of stuff I'd expect to happen at the tree level though,
> > > before expand.
> > 
> > The GIMPLE pass forming divmod could indeed choose to emit the
> > div + mul/sub sequence instead if an actual divmod pattern isn't available.
> > It could even generate some fake mul/sub/mod RTXen to cost the two
> > variants against each other but I seriously doubt any uarch that implements
> > division/modulo has a slower mul/sub.
> 
> Making a correct decision requires knowing to which degree the divider is
> pipelined, and costs won't properly reflect that. If the divider accepts
> a new div/mod instruction every couple of cycles, it's faster to just issue
> a div followed by a mod with the same operands.

 I guess there exist microarchitectures that have their divider pipelined, 
but I haven't come across one.  I think division is not an operation that 
is commonly optimised for in hw RTL, whether integer or FP, not at least 
in embedded applications, and given the nature of the operation I believe 
it would be particularly costly in terms of silicon.  I've seen latencies 
and repeat rates of up to 50 quoted in CPU documentation even for 32-bit 
integer division while multiplication had a latency of 5 and a repeat rate 
of 1 (i.e. fully pipelined) for the same microarchitecture.

 So (taking the data dependency into account) the latency of a DIV + MOD 
operation would be 100 for said microarchitecture (and the same repeat 
rate), while a DIV + MUL/SUB sequence would have a latency of 56 and a 
repeat rate of 50.  Quite an improvement.

> Therefore I think in this case it's fair for GIMPLE level to just check if
> the divmod pattern is available, and let the target do the fine tuning via
> the divmod expander.

 Hmm, we have DFA scheduling available that is supposed to give latencies 
and repeat rates for individual operations.  Wouldn't it be possible to 
get hold of this information?

 If we cannot make use of this information at the GIMPLE level (which I'd 
consider regrettable), then I think that maybe we need a target hook to 
say division is cheap that would prevent a DIV + MOD to DIV + MUL/SUB 
transformation from happening, perhaps off by default.  I think it would 
be regrettable too if every backend for targets/subtargets that do not 
have a hardware DIVMOD operation (e.g. MIPS has one at certain ISA levels 
only) or a pipelined division would have to code the transformation by 
hand.

> It would make sense for tree-ssa-mathopts to emit div + mul/sub when neither
> 'divmod' nor 'mod' patterns are available, because RTL expansion will do the
> same, just later, and we'll rely on RTL CSE to clean up the redundant div.

 That as well.

> But RISC-V has both 'div' and 'mod', so as I tried to explain in the first
> paragraph we should let the target decide.

 Still I think it would be best if RISC-V ought to supply a divmod pattern 
only where fused DIV/MOD execution is present in the microarchitecture.

  Maciej