llvm / llvm/llvm-project

Missing folding opportunities after tail duplication

Open
#216,284 0 comments 0 reactions 0 assignees View on GitHub
llvm:optimizations missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

https://godbolt.org/z/YP9xxeeda

AArch64 output contains code like:

```asm
lsl w8, w8, wzr
orr w8, w8, wzr
```

Similar foldable code exists in the x64 output too.

Loop unroller unrolls this loop shares the block for the `else` branch instead of duplicating it, generating

```llvm
cleanup: ; preds = %for.body.4, %for.body.3, %for.body.2, %for.body.1, %for.body
%shift.022.lcssa = phi i32 [ 0, %for.body ], [ 7, %for.body.1 ], [ 14, %for.body.2 ], [ 21, %for.body.3 ], [ 28, %for.body.4 ]
%result.021.lcssa = phi i32 [ 0, %for.body ], [ %and2, %for.body.1 ], [ %or.1, %for.body.2 ], [ %or.2, %for.body.3 ], [ %or.3, %for.body.4 ]
%conv.lcssa = phi i32 [ %conv, %for.body ], [ %conv.1, %for.body.1 ], [ %conv.2, %for.body.2 ], [ %conv.3, %for.body.3 ], [ %conv.4, %for.body.4 ]
%incdec.ptr.lcssa = phi ptr [ %incdec.ptr, %for.body ], [ %incdec.ptr.1, %for.body.1 ], [ %incdec.ptr.2, %for.body.2 ], [ %incdec.ptr.3, %for.body.3 ], [ %incdec.ptr.4, %for.body.4 ]
%shl3 = shl i32 %conv.lcssa, %shift.022.lcssa
%or4 = or i32 %shl3, %result.021.lcssa
store i32 %or4, ptr %value, align 4, !tbaa !10
br label %cleanup5
```

This block is then gets duplicated in the predecessors by the block placement pass. Before block placement:

```llvm
bb.2:
; predecessors: %bb.1
successors: %bb.3(0x80000000); %bb.3(100.00%)
liveins: $w8, $x0, $x2
$w10 = MOVZWi 0, 0
$w9 = MOVZWi 0, 0

bb.3.cleanup:
; predecessors: %bb.2, %bb.6, %bb.9, %bb.12, %bb.15
liveins: $w8, $w9, $w10, $x0, $x2
renamable $w8 = LSLVWr killed renamable $w8, killed renamable $w10
$w8 = ORRWrs killed renamable $w8, killed renamable $w9, 0
STRWui killed renamable $w8, killed renamable $x2, 0 :: (store (s32) into %ir.value, !tbaa !10)
RET undef $lr, implicit $x0
```

After:

```llvm
bb.2:
; predecessors: %bb.1
liveins: $w8, $x0, $x2
$w10 = MOVZWi 0, 0
$w9 = MOVZWi 0, 0
renamable $w8 = LSLVWr killed renamable $w8, killed renamable $w10
$w8 = ORRWrs killed renamable $w8, killed renamable $w9, 0
STRWui killed renamable $w8, killed renamable $x2, 0 :: (store (s32) into %ir.value, !tbaa !10)
RET undef $lr, implicit $x0
```

This pass is quite late though and there's nothing after it that can simplify this to eliminate those useless `orr` and `lsl`.

Contributor guide

Open the contributing guide

Research direction

Begin with the Godbolt reproducer and compare the loop-unroller output with the machine code before and after the block placement pass. Trace the cleanup block through those passes and confirm completion when the redundant LSLVWr and ORRWrs are no longer emitted in the AArch64 output, with the analogous x64 case also addressed.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
52/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.