[llvm-bugs] [Bug 46402] New: Missed opportunities for combining or eliminating sequential branches

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=46402

            Bug ID: 46402
           Summary: Missed opportunities for combining or eliminating
                    sequential branches
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Common Code Generator Code
          Assignee: unassignedbugs at nondot.org
          Reporter: khuey at kylehuey.com
                CC: llvm-bugs at lists.llvm.org

Created attachment 23635
  --> https://bugs.llvm.org/attachment.cgi?id=23635&action=edit
LLVM IR for jb X, je X and unconsolidated bounds checks.

I'm filing in this in the CodeGen component because it seems like peephole
optimizer should catch at least some of this this, but it may be that this
belongs elsewhere.

Using the latest nightly rustc (which is on LLVM 10), I see code sequences like

_ZN5x11rb8protocol3xkb21LatchLockStateRequest17try_parse_request17hb503842b081124b2E:
        movq    %rdi, %rax
        shrq    $40, %rsi
        cmpb    $5, %sil
        jne     .LBB4888_13
        cmpq    $2, %rcx
        jb      .LBB4888_16
        je      .LBB4888_16
        cmpq    $3, %rcx
        je      .LBB4888_16
        cmpq    $4, %rcx
        je      .LBB4888_16
        cmpb    $0, 4(%rdx)
        setne   %sil
        cmpq    $5, %rcx
        je      .LBB4888_16
        movb    5(%rdx), %dil
        cmpb    $4, %dil
        jae     .LBB4888_13
        cmpq    $6, %rcx
        je      .LBB4888_16
        cmpq    $7, %rcx
        je      .LBB4888_16
        cmpq    $8, %rcx
        je      .LBB4888_16
        cmpq    $9, %rcx
        je      .LBB4888_16
        andq    $-2, %rcx
        cmpq    $10, %rcx
        jne     .LBB4888_12
.LBB4888_16:
        movb    $0, 1(%rax)
        movb    $1, %cl
        movb    %cl, (%rax)
        retq
.LBB4888_13:
        movb    $1, 1(%rax)
        movb    $1, %cl
        movb    %cl, (%rax)
        retq
.LBB4888_12:
        movzwl  (%rdx), %ecx
        movb    2(%rdx), %r8b
        movb    3(%rdx), %r9b
        movb    6(%rdx), %r10b
        cmpb    $0, 9(%rdx)
        movzwl  10(%rdx), %edx
        movw    %cx, 2(%rax)
        movw    %dx, 4(%rax)
        movb    %r8b, 6(%rax)
        movb    %r9b, 7(%rax)
        movb    %sil, 8(%rax)
        movb    %dil, 9(%rax)
        movb    %r10b, 10(%rax)
        setne   11(%rax)
        xorl    %ecx, %ecx
        movb    %cl, (%rax)
        retq

There's at least two missed opportunities to optimize branches here. The first
trivial one is that the adjacent `jb X; je X` could be combined into a single
`jbe X`.

The second, more complicated but bigger win is that a number of these branches
checking %rcx could be consolidated. At each point where we check %rcx all
values lower than the current comparison value have already been rules out. So
every one of those branches is not just a `je LBB4888_16` but effectively a
`jbe LBB4888_16`. If the compiler could figure that out it could remove
adjacent ones just leaving the last branch to LBB4888_16 in each sequence.
Identifying that would remove at least 50% of the branches in this function.

The LLVM IR that rustc produces for this function (as taken with llvm-extract)
is attached.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20200619/74c57b13/attachment-0001.html>