llvm / llvm/llvm-project

[FMF] Missed optimization: integer-derived no-NaN fact not used for ordered fcmp lowering

Open
#199,893 3 comments 0 reactions 0 assignees View on GitHub
llvm:instcombine missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

When looking at SPEC CPU 2017 with LLVM, I found a possible missed optimization in `benchspec/CPU/538.imagick_r/src/magick/gem.c`, function `ConvertRGBToHSB`, which could be extracted and compiled alone as:

```c
typedef unsigned short Quantum;
static const double QuantumScale = 1.0/65535.0;
void ConvertRGBToHSB(Quantum red, Quantum green, Quantum blue,
double *hue, double *saturation, double *brightness) {
double b, delta, g, max, min, r;
*hue=0.0; *saturation=0.0; *brightness=0.0;
r=(double) red; g=(double) green; b=(double) blue;
min=r < g ? r : g; if (b < min) min=b;
max=r > g ? r : g; if (b > max) max=b;
if (max == 0.0) return;
delta=max-min;
*saturation=delta/max;
*brightness=QuantumScale*max;
if (delta == 0.0) return;
if (r == max) *hue=(g-b)/delta;
else if (g == max) *hue=2.0+(b-r)/delta;
else *hue=4.0+(r-g)/delta;
*hue/=6.0;
if (*hue < 0.0) *hue+=1.0;
}

```

The LLVM IR and x86 asm with O3 are like: https://godbolt.org/z/11o6zjsaK.

The relevant source line is:

```C
if (delta == 0.0) return;
```

In the generated LLVM IR this becomes:
```LLVM IR
%23 = fcmp oeq double %20, 0.000000e+00, !dbg !66
```

and X86 lowers it as:

```assembly
ucomisd xmm3, xmm5
jne .LBB0_2
jnp .LBB0_8
```

Here `delta` is derived from `unsigned short` inputs by `uitofp`, min/max selection, and `delta = max - min`. Therefore `r`, `g`, `b`, `min`, `max`, and `delta` are finite and never NaN. The compare therefore has a no-NaN operand fact in this context.

However, this fact is not exposed on the final fcmp, so X86 conservatively lowers the ordered equality test with an unordered/parity branch. If I manually mark the compare as:

```LLVM IR
%23 = fcmp nnan oeq double %20, 0.000000e+00
```

then X86 already emits the simpler branch shape with the unordered/parity arm removed: https://godbolt.org/z/d7h9vc4Wv, which becomes:

```assembly
ucomisd xmm3, xmm5
je .LBB0_8
```

So this does not seem to require a new X86 lowering rule. The missing piece appears to be preserving or exposing the no-NaN fact from the integer-derived min/max/delta chain to the final compare.

A slightly modified example shows that this is not only a one-branch effect. If the same `delta == 0.0` compare result has multiple users:

```c
typedef unsigned short Quantum;
static const double QuantumScale = 1.0 / 65535.0;

int hsb_multi(Quantum red, Quantum green, Quantum blue,
double *sat, double *bright, int *a, int *b, int *v) {
double r = (double)red;
double g = (double)green;
double bl = (double)blue;

double min = r < g ? r : g;
if (bl < min) min = bl;

double max = r > g ? r : g;
if (bl > max) max = bl;

if (max == 0.0) return 0;

double delta = max - min;
*sat = delta / max;
*bright = QuantumScale * max;

int c = (delta == 0.0);
// add multiple usages of the comparison result
if (c) *a = 10; else *a = 20;
*v = c ? 123 : 456;
if (c) *b = 30; else *b = 40;
return c ? 1 : 2;
}

```

The resulting LLVM IR and x86 assembly for current LLVM are like: https://godbolt.org/z/fd547rMjG.

Again, delta is never NaN for the same source-level reason. In current LLVM, without the nnan fact on the compare, X86 materializes ordered equality using the parity flag:

```
ucomisd
setnp
sete
and
...
cmovne ...
cmovne ...
cmovne ...
```

and then uses that result for the downstream conditional moves.

If I add nnan only to the same fcmp: https://godbolt.org/z/r3o9eaWTh, the parity handling disappears, and the downstream uses are driven by the simpler equality/non-equality condition:
```
ucomisd
...
cmove ...
cmove ...
setne
cmove ...
```

Contributor guide

Open the contributing guide

Research direction

Start by reproducing the extracted ConvertRGBToHSB example from benchspec/CPU/538.imagick_r/src/magick/gem.c and comparing the linked LLVM IR and X86 output with the manually added nnan versions. Read the relevant LLVM floating-point fact propagation and X86 lowering paths. Done means the no-NaN fact reaches the delta equality compare and the generated output no longer needs unordered/parity handling, including the multi-user hsb_multi case.

Written by the indexing model from the issue text.

Assessment

Tech stack
c
Domain
compilers
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.