[BUG REPORT] Divider Module Performance Bug: EarlyOut Fails to Skip Iterations When Divisor Exceeds Dividend

Type of Issue: Bug Report

Impact: Performance

Development Phase: Proposal

Current Behavior
The current EarlyOut logic in the divider is as follows:
```

if (cfg.divEarlyOut) {
val align = 1 << log2Floor(cfg.divUnroll max cfg.divEarlyOutGranularity)
val alignMask = ~((align-1).U(log2Ceil(w).W))
val divisorMSB = Log2(divisor(w-1,0), w) & alignMask
val dividendMSB = Log2(remainder(w-1,0), w) | ~alignMask

val eOutPos = ~(dividendMSB - divisorMSB) // ISSUE HERE!
val eOut = count === 0.U && !divby0 && eOutPos >= align.U
when (eOut) {
remainder := remainder(w-1,0) << eOutPos
count := eOutPos >> log2Floor(cfg.divUnroll)
}
}
```
During performance testing, I observed that the Boom core performs poorly when executing use cases with a large number of remainder instructions. One reason is that when using the rem instruction, if the divisor exceeds the dividend, the divider's execution delay increases to 67-69 cycles. After debugging, I found that the EarlyOut logic does not account for cases where the divisor's MSB (Most Significant Bit) exceeds the dividend's MSB. In such cases, eOutPos (the number of iterations to skip) becomes a very small positive number. For example, if the dividend is 3 and the divisor is 4, eOutPos becomes 1, meaning only one iteration is skipped. However, in this scenario, the divider should directly skip the entire division process.

Potential Solution
I modified the code to address this issue:
```

if (cfg.divEarlyOut) {
val align = 1 << log2Floor(cfg.divUnroll max cfg.divEarlyOutGranularity)
val alignMask = ~((align-1).U(log2Ceil(w).W))
val divisorMSB = Log2(divisor(w-1,0), w) & alignMask
val dividendMSB = Log2(remainder(w-1,0), w) | ~alignMask
// ## Divider Bug Fix ##
val divisorGTdividend = divisorMSB > dividendMSB
val eOutPos = Mux(divisorGTdividend, (w).U, ~(dividendMSB - divisorMSB))
// val eOutPos = ~(dividendMSB - divisorMSB)
val eOut = count === 0.U && !divby0 && eOutPos >= align.U
when (eOut) {
remainder := remainder(w-1,0) << eOutPos
count := eOutPos >> log2Floor(cfg.divUnroll)
}
}
```
With this fix, the divider now correctly skips the division process in such cases, and the performance of related use cases has improved by 10-15%. Please let me know if this modification is correct or if there are better optimization strategies.

Environment
Master branch on Chipyard
Evaluating performance using the Boom core
Boom's unit instance uses the divider from Rocket-Chip
Use Case for Changing the Behavior
This issue is triggered when using remainder or division instructions, specifically when the dividend's MSB is less than the divisor's MSB. In such cases, the EarlyOut logic fails to activate, leading to degraded divider performance.

Start from the divider EarlyOut logic shown in the issue and trace how remainder and division instructions use it in Rocket-Chip. Compare the proposed divisor-greater-than-dividend handling with the existing iteration and remainder behavior, then validate the affected cases and measure whether the divider latency improves.

Written by the indexing model from the issue text.