llvm / llvm/llvm-project

[LSR] loop-reduce introduces redundant IV on RISC-V

Open
#194,871 3 comments 0 reactions 0 assignees View on GitHub
backend: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:
Image

GCC:
Image

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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.