llvm / llvm/llvm-project

Use `BLSR` fusions to break dependency chains even when intermediate expression value is consumed

Open
#160,756 1 comment 0 reactions 0 assignees View on GitHub
backend:X86
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

[Godbolt](https://c.godbo.lt/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,selection:(endColumn:1,endLineNumber:7,positionColumn:1,positionLineNumber:7,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:'%23include+%3Cstdint.h%3E%0A%0Auint64_t+foo(uint64_t+z)+%7B%0A++++uint64_t+w+%3D+z+-+1%3B%0A++++return+(z+%26+w)+*+w%3B%0A%7D%0A'),l:'5',n:'0',o:'C+source+%231',t:'0')),k:47.14192766144739,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:cclang_trunk,filters:(b:'0',binary:'1',binaryObject:'1',commentOnly:'0',debugCalls:'1',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1',verboseDemangling:'0'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,libs:!(),options:'-O3+--target%3Dx86_64-linux+-march%3Dznver5',overrides:!(),selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+x86-64+clang+(trunk)+(Editor+%231)',t:'0')),k:52.858072338552596,l:'4',m:100,n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4)

```c
#include

uint64_t foo(uint64_t z) {
uint64_t w = z - 1;
return (z & w) * w;
}
```

Emits:

```asm
foo:
lea rax, [rdi - 1]
and rdi, rax ; can't be computed in parallel with `lea`
imul rax, rdi
ret
```

I was expecting:

```asm
foo:
lea rax, [rdi - 1]
blsr rdi, rdi ; can be computed in parallel with `lea`
imul rax, rdi
ret
```

Contributor guide

Open the contributing guide

Research direction

Start with the linked Godbolt C reproducer and inspect the LLVM x86 code-generation path responsible for selecting BLSR for the `(z & (z - 1))` expression. Compare the emitted assembly with the expected sequence, and consider the work complete when the intermediate value remains usable while the BLSR operation can be scheduled in parallel with the subtraction.

Written by the indexing model from the issue text.

Assessment

Tech stack
c
Domain
compilers
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.