llvm / llvm/llvm-project

[x86] Unnecessary `mov`, conditionally jumped to, that disrupts another block's fallthrough should be removed

Open
#195,597 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 code: [(Godbolt)](https://zig.godbo.lt/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:16,fontUsePx:'0',j:1,lang:zig,selection:(endColumn:38,endLineNumber:20,positionColumn:38,positionLineNumber:20,selectionStartColumn:38,selectionStartLineNumber:20,startColumn:38,startLineNumber:20),source:'export+fn+b64_decode_new(input_ptr:+%5B*%5Dconst+u8,+input_len:+usize,+output_ptr:+%5B*%5Du8,+output_len:+usize)+usize+%7B%0A++++var+cur_i+%3D+input_ptr%5B0..input_len%5D%3B%0A++++var+cur_o+%3D+output_ptr%5B0..output_len%5D%3B%0A%0A++++for+(0..input_len)+%7C_%7C+%7B%0A++++++++cur_o%5B0%5D+%3D+cur_i%5B0%5D%3B%0A++++++++cur_i+%3D+cur_i%5B1..%5D%3B%0A++++++++cur_o+%3D+cur_o%5B1..%5D%3B%0A++++%7D%0A%0A++++const+C:+u64+%3D+@bitCast(@as(%5B8%5Du8,+@splat(@as(u8,+0b00111111))))%3B%0A++++cur_o.ptr%5B0..8%5D.*+%3D+@bitCast(pdep(bzhi(~@as(u64,+0),+cur_o.len),+C))%3B%0A++++return+output_len%3B%0A%7D%0A%0Aconst+std+%3D+@import(%22std%22)%3B%0Aextern+fn+@%22llvm.x86.bmi.pdep.64%22(u64,+u64)+u64%3B%0Aextern+fn+@%22llvm.x86.bmi.bzhi.64%22(u64,+u64)+u64%3B%0Aconst+pdep+%3D+@%22llvm.x86.bmi.pdep.64%22%3B%0Aconst+bzhi+%3D+@%22llvm.x86.bmi.bzhi.64%22%3B'),l:'5',n:'0',o:'Zig+source+%231',t:'0')),k:51.147149890868484,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((g:!((h:compiler,i:(compiler:ztrunk,filters:(b:'0',binary:'1',binaryObject:'1',commentOnly:'0',debugCalls:'1',demangle:'0',directives:'0',execute:'0',intel:'0',libraryCode:'0',trim:'1',verboseDemangling:'0'),flagsViewOpen:'1',fontScale:17,fontUsePx:'0',j:1,lang:zig,libs:!(),options:'-O+ReleaseFast+-mcpu%3Dznver5+-target+x86_64-linux+-fomit-frame-pointer',overrides:!(),selection:(endColumn:25,endLineNumber:48,positionColumn:25,positionLineNumber:48,selectionStartColumn:25,selectionStartLineNumber:48,startColumn:25,startLineNumber:48),source:1),l:'5',n:'0',o:'+zig+trunk+(Editor+%231)',t:'0')),header:(),k:48.85285010913152,l:'4',m:50,n:'0',o:'',s:0,t:'0'),(g:!((h:ir,i:('-fno-discard-value-names':'0',compilerName:'zig+trunk',demangle-symbols:'0',editorid:1,filter-attributes:'0',filter-comments:'0',filter-debug-info:'0',filter-declarations:'1',filter-instruction-metadata:'0',filter-library-functions:'1',fontScale:14,fontUsePx:'0',j:1,selection:(endColumn:1,endLineNumber:99,positionColumn:1,positionLineNumber:99,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),show-optimized:'0',treeid:0,wrap:'1'),l:'5',n:'0',o:'LLVM+IR+Viewer+zig+trunk+(Editor+%231,+Compiler+%231)',t:'0')),header:(),l:'4',m:50,n:'0',o:'',s:0,t:'0')),k:48.85285010913152,l:'3',n:'0',o:'',t:'0')),l:'2',n:'0',o:'',t:'0')),version:4)

```zig
export fn b64_decode_new(input_ptr: [*]const u8, input_len: usize, output_ptr: [*]u8, output_len: usize) usize {
var cur_i = input_ptr[0..input_len];
var cur_o = output_ptr[0..output_len];

for (0..input_len) |_| {
cur_o[0] = cur_i[0];
cur_i = cur_i[1..];
cur_o = cur_o[1..];
}

const C: u64 = @bitCast(@as([8]u8, @splat(@as(u8, 0b00111111))));
cur_o.ptr[0..8].* = @bitCast(pdep(bzhi(~@as(u64, 0), cur_o.len), C));
return output_len;
}

const std = @import("std");
extern fn @"llvm.x86.bmi.pdep.64"(u64, u64) u64;
extern fn @"llvm.x86.bmi.bzhi.64"(u64, u64) u64;
const pdep = @"llvm.x86.bmi.pdep.64";
const bzhi = @"llvm.x86.bmi.bzhi.64";
```

LLVM version: [(Godbolt)](https://llvm.godbo.lt/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaPECAMzwBtMA7AQwFtMQByARg9KtQYEAysib0QXACx8BBAKoBnTAAUAHpwAMvAFYTStJg1C1aANxakl9ZATwDKjdAGFUtAK4sGexwBk8DTAA5DwAjTGIQAE5I0gAHVAVCOwYXd089eMTbAT8A4JYwiOjLTGtshiECJmICVI8vLhKy5Mrqglyg0PC9BSqauvTG3raO/MKJAEpLVDdiZHYOAAEQgDZJAH0sNCx1gIB3AGoAUgBmABEDsTwmBQO8NYOIWIIyO7XSA%2BfX%2B8kpz5eDotMKpWLF6AA6VYbLYYTC7TB7I4aACCSORWwMxEwb0kgJM5nBqgAHCtISw8ODYlhYuC1hAfh8fhNLrQ8MAGAcuGi0RjqtifnizCxCSSyRSQgAvBAUukMnHMq7sznclFYGgBO6CcLMWg4wHA0EQqGbTDbOH7J4AhgCBhuEwHLFMdACWgATxZbI5XAOomes0wCgg1oCzKOACYAKwaRkPcMRxr/YgHYO2%2B17YiETAu92Kr0%2Bph%2BrGB4OYUORsMx3FYgizALoY6Rk7MtwMZhsdDrJ3oJO5znHADsACE0dhBMRXSA0QcGxHwdaCMdzndkCxYgdMABHPVxhMaKcHEJJvDeuNz1AED4GMK6uPYWhKS9Ma8zgAqCEYlKx76d4RVyLfH6xF%2BmA/hE%2B5xqoLxMJmSanBchj1gKO4fP24GRricHLquBx2guSGRgmRL7oedwnuhj7PnGAEMOCmCxHQn6YN%2BWCvFepSvu%2BNFAUxIEsXOCJ/tRjHMeE/F7JOKLTnGLbEK4tDrDBi7wQwiGxgRHwALREZJB5JmxN6RtRgmcRJyJSZG97EOCeCmEpnzStuEaDjOlnWaY/GQR8VGcccEZnF5TkzjJckKQQ4ReYZnHCbxon7L5ZxobOCiyUw4IaGlJwrHZsQOV8vnOXG0YcYBwGgWJ8UBQV5b9hFEbUfFiXgslqCpRoJxcBlEbZblAJHIFcYVsVXGlXxcV9f5%2BUzmGRK1fV42JV1mG0C1iEzYmM5NSlaUZSsHy9lyOm9CQ/JEjOEYfHlp7Na17WdXtrJKgdZkzllmHAJgYX0Gwgh5Xga2XZGm0tdtbW7XqT3mRG/Z2e9n2YN9BC/f9vWA9dGUdW153g4lp1LStdzI7BkZg/t%2B5HViBMzoTM41R6j2JZEMMfaU8OMIjAJ/RdKNJVt6Wg5WBxholXAaEzcMI0jXNEzzwNtRjJxYwKQs6TuJ5LstToE1LM4xHTXpk0QFN/TOXAJgD8ZFaTKsEWGYssxLHPU1dvM7QLJzCycdtfWzkvrc7su3ZjbvCxh6v45zfs2/dnrKodhsnSb0iR/GJzR/T1vxotS6w/bPuO9r/uta7eqSMLr3Z8z3s/fnydAzd8uKw8pcZ1w0N45rEfm1wWNW895MJzutNdyTD36y3uMV%2BLedHk7qMu/zeoRsLjNvZXrPVzPBdzwHDcC0vGdhqL7erVv8Zrb30795TA1FV3usX1NasXDnVfs5vtdo3zmUCysiVhrbq8p4by1h/XmgcFY/z/p7Y%2BIDzZhgTA/K%2BxsBqp2Tv/NOY9noDVDs/NeDt37mzriDb%2BepUIHyzrgoBb9YHcyIXLO6pC/7lwuBrE%2BaCk6IPjtfcsYM4E91HrHLB1Uvbr2oZ3Whn9i4Cm0kIiM00RH4JodLOh4DG64hkZDVyNkPILkwl2bcFlkpuU0homcDAYJzhXDSNuS48BWPXFufCEYtHuQCJ5A4e4dIkWPGYixDArHglpvpGcd4lDgmWqgWIwJCDghkhpWgyAFAKCYBRdi3lGB/lCZgcJqBInRIILEhgxB4mJOSaZTRASWAYDPLo2x9jNwGIjJBYg0EwqvE8c9bxZFnGVOqfOVJBkIxZJyXk1QhABlDVovRWg0VQLGQ/HRBi3ERJgQznQnaUyGL%2BEIN1PAft%2BqRiKuk4aPFQIVUmgNWmt57zZIiVEsZBS4kJKSUwBqazP6qM2TM7ZtSLg5T2ZdA5cjZpRWWTFWCflKpTTWtcsJdz8mFOKc85JbzOl6SfGkyKCzpnzJoos2g5SZz4usm03ZjkqoRmJX44EF5Jn4vOX1ZyRysV4umbMliqLIYKHmKYd6a5AG52AeI5RkjQZfOsuY2lTiqVtMStyzAvK6KSBsZQwVYjZ4y3rp1cVPyBZxhlb%2BA%2BK8w4dw1fKxVsQMGCMvlw5B5Zdbm3NXy5VVqIZErZdSyCdl9HSo9W0j4br9V%2BtEgE%2Bcdk7HYQaU45prTwruq2W0nRxEjzdINVZUN54Jmwtubk%2B5MT4UPKzSyr5mSbkjLzQUgthBCVxidUq5hBwX6iN9oQj5DcdWSr1ZGNNSavHosopGYZVaCClrhbm/JNbAbIteZhf5%2ByKV1tiJIMG2by0IuHQyoF01apDvHQ8xFJSXmcpnCcI%2BS4FBuBCI01BO5k0HGCdm0d7BGptu2tOslgKKWDVvGOd040oWnmnTustG75rvK2rOdK77Z0OSQkCm9g7f2bopae4DY7Rk7LA7I9qdkqh0HzPaAUix8TCmJKSEI5JIRShlJIekDwNIJicUQyD4TSlMAmIlE4AClx4d1KIQjDxiNChFORyjVI6K0lo049qAtJARihpIU9RJlP9kiMp09Jxogcbjsda9g1W1gIxqxl5rr9zVmvdyfsCUUQ8lNJibEphUB4HrEJgkNwL1sHpN6a0LY1Rli42iDgUwCUcAjLwLwHAtCkFQJwHwPgABqABZA4ABJAASgcBQMw5jYnDO1XgBBNBBamAAaxAPGQJkguArCJGGSI/Y5MRkiCsGIIXJDhaK9FzgvAFAgGjIVyLQXSBwFgEgNAq46DhQoBAcb0zugmBsMQFsJW%2BB0Dab1iAIROshH8NUCc3BeA7eYOOAA8iEbQpoBs8FIONhGJ2GBuk61gEIbhgBODEPeTg12sAsEMMAcQg3SD4CxDYGyAZOvAlNG4MKX3eD%2BE%2Bp11kh49suCwJ1l4eAWCw9IKYcIIQEiYDOPDP7rIjBFamFQAwwAFDxbwAiE7USIvXf4IIEQYh2BSBkIIRQKh1CA90I0AwZOSP6DwCEXrkApiRPKL1jgGkTuew0iwZAsQ3BwQlAwXHxAwvRa1xmLAEuIBTCsJd5IDgVIDC8JIaMvh/CdAKN0KGcQEhJAEJbkA1vndZGSKMLoEQncm9BwIVo/RXD1B6CzIPFQ%2BjtDt2MboQwY/u8TyMOPfvJjTFmPMDPIWdcRaizFjg96EmPBeMt5kEBcCEBIA2dqEwCvk9Kx7ok4JIxEnav2DQ6Frcyba7wLHItoz594IXnrfXSADa0BMYLnAwwdcB6PifjecfhESPYSQQA%3D%3D%3D)

```llvm
@b64_decode_new = alias i64 (ptr, i64, ptr, i64), ptr @example.b64_decode_new

declare i64 @llvm.x86.bmi.pdep.64(i64, i64) align 1

declare i64 @llvm.x86.bmi.bzhi.64(i64, i64) align 1

define internal i64 @example.b64_decode_new(ptr nonnull readonly align 1 captures(none) %0, i64 %1, ptr nonnull writeonly align 1 captures(none) %2, i64 returned %3) unnamed_addr align 1 {
Entry:
%.not = icmp eq i64 %1, 0
br i1 %.not, label %Else, label %Then.preheader

Then.preheader:
%xtraiter = and i64 %1, 7
%4 = icmp ult i64 %1, 8
br i1 %4, label %Then.epil.preheader, label %Then.preheader.new

Then.preheader.new:
%unroll_iter = and i64 %1, -8
br label %Then

Then:
%lsr.iv = phi i64 [ %lsr.iv.next, %Then ], [ %unroll_iter, %Then.preheader.new ]
%.sroa.0.036 = phi ptr [ %0, %Then.preheader.new ], [ %27, %Then ]
%.sroa.031.035 = phi ptr [ %2, %Then.preheader.new ], [ %28, %Then ]
%5 = load i8, ptr %.sroa.0.036, align 1
store i8 %5, ptr %.sroa.031.035, align 1
%6 = getelementptr i8, ptr %.sroa.0.036, i64 1
%7 = getelementptr i8, ptr %.sroa.031.035, i64 1
%8 = load i8, ptr %6, align 1
store i8 %8, ptr %7, align 1
%9 = getelementptr i8, ptr %.sroa.0.036, i64 2
%10 = getelementptr i8, ptr %.sroa.031.035, i64 2
%11 = load i8, ptr %9, align 1
store i8 %11, ptr %10, align 1
%12 = getelementptr i8, ptr %.sroa.0.036, i64 3
%13 = getelementptr i8, ptr %.sroa.031.035, i64 3
%14 = load i8, ptr %12, align 1
store i8 %14, ptr %13, align 1
%15 = getelementptr i8, ptr %.sroa.0.036, i64 4
%16 = getelementptr i8, ptr %.sroa.031.035, i64 4
%17 = load i8, ptr %15, align 1
store i8 %17, ptr %16, align 1
%18 = getelementptr i8, ptr %.sroa.0.036, i64 5
%19 = getelementptr i8, ptr %.sroa.031.035, i64 5
%20 = load i8, ptr %18, align 1
store i8 %20, ptr %19, align 1
%21 = getelementptr i8, ptr %.sroa.0.036, i64 6
%22 = getelementptr i8, ptr %.sroa.031.035, i64 6
%23 = load i8, ptr %21, align 1
store i8 %23, ptr %22, align 1
%24 = getelementptr i8, ptr %.sroa.0.036, i64 7
%25 = getelementptr i8, ptr %.sroa.031.035, i64 7
%26 = load i8, ptr %24, align 1
store i8 %26, ptr %25, align 1
%27 = getelementptr i8, ptr %.sroa.0.036, i64 8
%28 = getelementptr i8, ptr %.sroa.031.035, i64 8
%lsr.iv.next = add i64 %lsr.iv, -8
%niter.ncmp.7 = icmp eq i64 %lsr.iv.next, 0
br i1 %niter.ncmp.7, label %Else.loopexit.unr-lcssa, label %Then

Else.loopexit.unr-lcssa:
%lcmp.mod.not = icmp eq i64 %xtraiter, 0
br i1 %lcmp.mod.not, label %Else.loopexit, label %Then.epil.preheader

Then.epil.preheader:
%.sroa.0.036.epil.init = phi ptr [ %0, %Then.preheader ], [ %27, %Else.loopexit.unr-lcssa ]
%.sroa.031.035.epil.init = phi ptr [ %2, %Then.preheader ], [ %28, %Else.loopexit.unr-lcssa ]
br label %Then.epil

Then.epil:
%epil.iter = phi i64 [ %epil.iter.next, %Then.epil ], [ 0, %Then.epil.preheader ]
%scevgep = getelementptr i8, ptr %.sroa.0.036.epil.init, i64 %epil.iter
%scevgep47 = getelementptr i8, ptr %.sroa.031.035.epil.init, i64 %epil.iter
%29 = load i8, ptr %scevgep, align 1
store i8 %29, ptr %scevgep47, align 1
%epil.iter.next = add i64 %epil.iter, 1
%epil.iter.cmp.not = icmp eq i64 %xtraiter, %epil.iter.next
br i1 %epil.iter.cmp.not, label %Else.loopexit.loopexit, label %Then.epil

Else.loopexit.loopexit:
%scevgep46 = getelementptr i8, ptr %.sroa.031.035.epil.init, i64 %epil.iter.next
br label %Else.loopexit

Else.loopexit:
%.lcssa = phi ptr [ %scevgep46, %Else.loopexit.loopexit ], [ %28, %Else.loopexit.unr-lcssa ]
%30 = sub i64 %3, %1
br label %Else

Else:
%.sroa.031.0.lcssa = phi ptr [ %2, %Entry ], [ %.lcssa, %Else.loopexit ]
%.sroa.5.0.lcssa = phi i64 [ %3, %Entry ], [ %30, %Else.loopexit ]
%31 = tail call i64 @llvm.x86.bmi.bzhi.64(i64 -1, i64 %.sroa.5.0.lcssa)
%32 = tail call i64 @llvm.x86.bmi.pdep.64(i64 %31, i64 4557430888798830399)
store i64 %32, ptr %.sroa.031.0.lcssa, align 1
ret i64 %3
}

declare void @llvm.assume(i1 noundef) #2
```

Emit:

```asm
example.b64_decode_new: # @example.b64_decode_new
mov rax, rcx
test rsi, rsi
je .LBB0_1
mov ecx, esi
and ecx, 7
cmp rsi, 8
jb .LBB0_6
mov r8, rsi
and r8, -8
neg r8
.LBB0_4: # %Then
movzx r9d, byte ptr [rdi]
mov byte ptr [rdx], r9b
movzx r9d, byte ptr [rdi + 1]
mov byte ptr [rdx + 1], r9b
movzx r9d, byte ptr [rdi + 2]
mov byte ptr [rdx + 2], r9b
movzx r9d, byte ptr [rdi + 3]
mov byte ptr [rdx + 3], r9b
movzx r9d, byte ptr [rdi + 4]
mov byte ptr [rdx + 4], r9b
movzx r9d, byte ptr [rdi + 5]
mov byte ptr [rdx + 5], r9b
movzx r9d, byte ptr [rdi + 6]
mov byte ptr [rdx + 6], r9b
movzx r9d, byte ptr [rdi + 7]
add rdi, 8
mov byte ptr [rdx + 7], r9b
add rdx, 8
add r8, 8
jne .LBB0_4
test rcx, rcx
je .LBB0_9
.LBB0_6: # %Then.epil.preheader
xor r8d, r8d
.LBB0_7: # %Then.epil
movzx r9d, byte ptr [rdi + r8]
mov byte ptr [rdx + r8], r9b
inc r8
cmp rcx, r8
jne .LBB0_7
add rdx, r8
.LBB0_9: # %Else.loopexit
mov rcx, rax
sub rcx, rsi
- jmp .LBB0_10
.LBB0_1:
- mov rcx, rax
.LBB0_10: # %Else
mov rsi, -1
movabs rdi, 4557430888798830399
bzhi rcx, rsi, rcx
pdep rcx, rcx, rdi
mov qword ptr [rdx], rcx
ret
b64_decode_new = example.b64_decode_new
```

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.