llvm / llvm/llvm-project

[X86] Attrocious code when using a multiple of the index of the most significant bit.

Open
#175,394 6 comments 0 reactions 0 assignees View on GitHub
backend:X86 missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

I have been looking at some cases of bad code generation around `llvm.ctlz` with x86. One case that is particularly badly handled is if an integer multiple of the index of the most significant bit is used.

C code:
```
static inline int findFirstBit(int i) { return 31 - __builtin_clz(i); }

int getFloatOffset(int pattern) { return findFirstBit(pattern) * 4; }
int getDoubleOffset(int pattern) { return findFirstBit(pattern) * 8; }
```

LLVM Bitcode before the backend:
```
define dso_local noundef range(i32 0, 125) i32 @getFloatOffset(int)(i32 noundef %pattern) local_unnamed_addr {
entry:
%0 = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 %pattern, i1 true)
%sub.i = shl nuw nsw i32 %0, 2
%mul = xor i32 %sub.i, 124
ret i32 %mul
}

define dso_local noundef range(i32 0, 249) i32 @getDoubleOffset(int)(i32 noundef %pattern) local_unnamed_addr {
entry:
%0 = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 %pattern, i1 true)
%sub.i = shl nuw nsw i32 %0, 3
%mul = xor i32 %sub.i, 248
ret i32 %mul
}
```

LLVM is trying to be smart about the XOR. Doesn't help if you try outsmart it with "31 - x".

Now as a result, the assembly becomes attrocious:
```
getFloatOffset(int):
bsr eax, edi
xor eax, 31
shl eax, 2
xor eax, 124
ret

getDoubleOffset(int):
bsr eax, edi
xor eax, 31
xor eax, 31 ; Are you serious?
shl eax, 3
ret
```

When compiling for AVX2, the compiler uses `lzcnt` which makes it look a bit less bad but `bsr` would be best still.

This issue seems related although the case is a bit different: https://github.com/llvm/llvm-project/issues/150954.

Contributor guide

Open the contributing guide

Research direction

Reproduce the two C examples through the x86 backend, comparing the shown LLVM IR with the bsr and lzcnt assembly for regular x86 and AVX2. Start by tracing x86 handling of llvm.ctlz and the index-multiplication patterns; done means the generated code no longer contains redundant XOR operations while preserving the reported behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
c
Domain
compilers, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.