llvm / llvm/llvm-project

[X86] Failure to shift-in one bits via `shld`

Open
#168,862 2 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

[Zig Godbolt](https://zig.godbo.lt/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:zig,selection:(endColumn:2,endLineNumber:11,positionColumn:1,positionLineNumber:5,selectionStartColumn:2,selectionStartLineNumber:11,startColumn:1,startLineNumber:5),source:'export+fn+shift_in_ones(a:+u64,+c:+u8)+u64+%7B%0A++++return+~(~a+%3C%3C+@truncate(c))%3B%0A%7D%0A%0Aexport+fn+shld(a:+u64,+b:+u64,+c:+u8)+u64+%7B%0A++++return+@truncate(@as(u128,+@bitCast(%5B2%5Du64%7B+a,+b+%7D))+%3C%3C+@as(u6,+@truncate(c))+%3E%3E+64)%3B%0A%7D%0A%0Aexport+fn+shift_in_ones_2(a:+u64,+c:+u8)+u64+%7B%0A++++return+shld(~@as(u64,+0),+a,+c)%3B%0A%7D%0A%0Aexport+fn+shift_in_ones_3(a:+u64,+c:+u8)+u64+%7B%0A++++return+shld_asm(~@as(u64,+0),+a,+c)%3B%0A%7D%0A%0Apub+fn+shld_asm(low:+u64,+high:+u64,+shift_amt:+u8)+u64+%7B%0A++++var+ret:+u64+%3D+high%3B%0A++++asm+(%22shldq+%25%5Bcnt%5D,+%25%5Bsrc%5D,+%25%5Bret%5D%22%0A++++++++:+%5Bret%5D+%22%2Br%22+(ret),%0A++++++++:+%5Bsrc%5D+%22r%22+(low),%0A++++++++++%5Bcnt%5D+%22%7Bcl%7D%22+(shift_amt),%0A++++++++:+.%7B+.cc+%3D+true+%7D)%3B%0A++++return+ret%3B%0A%7D'),l:'5',n:'0',o:'Zig+source+%231',t:'0')),k:55.575874538014034,l:'4',m:100,n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:ztrunk,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:2,lang:zig,libs:!(),options:'-O+ReleaseFast+-target+x86_64-linux+-mcpu%3Dicelake_server+-fomit-frame-pointer',overrides:!(),selection:(endColumn:12,endLineNumber:27,positionColumn:1,positionLineNumber:21,selectionStartColumn:12,selectionStartLineNumber:27,startColumn:1,startLineNumber:21),source:1),l:'5',n:'0',o:'+zig+trunk+(Editor+%231)',t:'0')),header:(),k:44.42412546198598,l:'4',m:100.00000000000001,n:'0',o:'',s:0,t:'0')),l:'2',m:100,n:'0',o:'',t:'0')),version:4)

Attempt 1:

```zig
export fn shift_in_ones(a: u64, c: u8) u64 {
return ~(~a << @truncate(c));
}
```

```asm
shift_in_ones:
not rdi
shlx rax, rdi, rsi
not rax
ret
```

Attempt 2:

```zig
export fn shld(a: u64, b: u64, c: u8) u64 {
return @truncate(@as(u128, @bitCast([2]u64{ a, b })) << @as(u6, @truncate(c)) >> 64);
}

export fn shift_in_ones_2(a: u64, c: u8) u64 {
return shld(~@as(u64, 0), a, c);
}
```

```asm
shld:
mov ecx, edx
mov rax, rsi
shld rax, rdi, cl
ret

shift_in_ones_2: ; for some reason inlining makes us not see that this a `shld`?
shlx rcx, rdi, rsi
and sil, 63
not sil
movabs rax, 9223372036854775807
shrx rax, rax, rsi
or rax, rcx
ret
```

Should be:

```asm
shift_in_ones:
mov ecx, esi
mov rax, rdi
mov rdx, -1
shld rax, rdx, cl
ret
```

Contributor guide

Open the contributing guide

Research direction

Start with the Zig Godbolt reproducer and compare the generated assembly for shift_in_ones, shld, and shift_in_ones_2 against the expected shld sequence shown in the issue. Trace the compiler's handling of the inlined shift-in-ones pattern; done means the relevant function recognizes the pattern and emits the expected x86 shld form.

Written by the indexing model from the issue text.

Assessment

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.