[LSR] loop-reduce introduces redundant IV on RISC-V
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
I noticed this performance gap between LLVM and GCC on this benchmark linked below:
https://cc-perf.igalia.com/db_default/v4/nts/profile/246/468/467
I've attached images of the relevant basic block below.
LLVM:
GCC:
LLVM is performing an additional 5% cycles because of an extra `addi` instruction. Specifically, for this snippet of code:
```C
for( i = 1 ; i <= m-1 ; i++ )
{
u = (double)i * x;
w = u * u;
s = s + w*(w*(w*(w*(w*(B6*w+B5)+B4)+B3)+B2)+B1)+one;
}
```
LLVM introduced a *down counter*. So it decrements from `m-1` to `1`, but it also needs the `i` value so it has the `i++` addition instruction. GCC is simply just doing the `i++` and then branches if `i` is not equal to `m` (`bne`).
I've narrowed this down to the `loop-reduce` pass. This is the IR before and after the loop-reduce pass.
```llvm
; Loop:
for.body: ; preds = %for.body, %entry
%s.071 = phi double [ 0.000000e+00, %entry ], [ %add, %for.body ]
%i.070 = phi i64 [ 1, %entry ], [ %inc, %for.body ]
%conv7 = uitofp nneg i64 %i.070 to double
%mul8 = fmul double %div, %conv7
%mul9 = fmul double %mul8, %mul8
%11 = tail call double @llvm.fmuladd.f64(double %4, double %mul9, double %5)
%12 = tail call double @llvm.fmuladd.f64(double %mul9, double %11, double %6)
%13 = tail call double @llvm.fmuladd.f64(double %mul9, double %12, double %7)
%14 = tail call double @llvm.fmuladd.f64(double %mul9, double %13, double %8)
%15 = tail call double @llvm.fmuladd.f64(double %mul9, double %14, double %9)
%16 = tail call double @llvm.fmuladd.f64(double %mul9, double %15, double %s.071)
%add = fadd double %10, %16
%inc = add nuw nsw i64 %i.070, 1
%exitcond.not = icmp eq i64 %inc, 156250000
br i1 %exitcond.not, label %for.end, label %for.body, !llvm.loop !14
```
```llvm
; Loop:
for.body: ; preds = %for.body, %entry
%lsr.iv = phi i64 [ %lsr.iv.next, %for.body ], [ 156249999, %entry ]
%s.071 = phi double [ 0.000000e+00, %entry ], [ %add, %for.body ]
%i.070 = phi i64 [ 1, %entry ], [ %inc, %for.body ]
%conv7 = uitofp nneg i64 %i.070 to double
%mul8 = fmul double %div, %conv7
%mul9 = fmul double %mul8, %mul8
%11 = tail call double @llvm.fmuladd.f64(double %4, double %mul9, double %5)
%12 = tail call double @llvm.fmuladd.f64(double %mul9, double %11, double %6)
%13 = tail call double @llvm.fmuladd.f64(double %mul9, double %12, double %7)
%14 = tail call double @llvm.fmuladd.f64(double %mul9, double %13, double %8)
%15 = tail call double @llvm.fmuladd.f64(double %mul9, double %14, double %9)
%16 = tail call double @llvm.fmuladd.f64(double %mul9, double %15, double %s.071)
%add = fadd double %10, %16
%inc = add nuw nsw i64 %i.070, 1
%lsr.iv.next = add nsw i64 %lsr.iv, -1
%exitcond.not = icmp eq i64 %lsr.iv.next, 0
br i1 %exitcond.not, label %for.end, label %for.body, !llvm.loop !14
```
From the debug logs, these are the winning formulas.
```
The chosen solution requires 2 instructions 2 regs, with addrec cost 2, plus 2 setup cost:
LSR Use: Kind=ICmpZero, Offsets={0}, all-fixups-unconditional
reg({156249999,+,-1}<%for.body>)
LSR Use: Kind=Basic, Offsets={0}, all-fixups-unconditional
reg({1,+,1}<%for.body>)
```
Here is a godbolt link:
https://godbolt.org/z/5W8Tvresa
I noticed that without the RISC-V triple, LSR does not introduce the redundant counter.
https://godbolt.org/z/dGnrob5G7
Looking at the debug logs, the non RISCV target can generate this formula
```
The chosen solution requires 2 instructions 1 reg, with addrec cost 1, plus 29 imm cost, plus 1 setup cost:
LSR Use: Kind=ICmpZero, Offsets={0}, all-fixups-unconditional
-156250000 + reg({1,+,1}<%for.body>)
LSR Use: Kind=Basic, Offsets={0}, all-fixups-unconditional
reg({1,+,1}<%for.body>)
```
The closest formula generated by RISC-V is as follows:
```
LSR Use: Kind=ICmpZero, Offsets={0}, all-fixups-unconditional
...
-1 + reg(-156249999) + 1*reg({1,+,1}<%for.body>)
```
I believe `GenerateCrossUseConstantOffsets` is responsible for generating this formula. Since -156250000 doesn't fit in RISC-V's 12-bit immediate field, `isLegalUse` and `isLegalAddImmediate` fail, causing `GenerateCrossUseConstantOffsets` to generate the split `-1 + reg(-156249999)` form instead.
This discourse link may include more info but I believe I summarized the key points in this issue.
https://discourse.llvm.org/t/lsr-question-on-collectfixups-function/90598/5
Contributor guide
Assessment
This issue has not been assessed yet.