Hi everyone,

I've noticed a bit of a deep potential optimisation for faster code:

    jne     .Lj1806
    movb    $13,-40(%rbp)
    cmpq    $0,-32(%rbp)
    je      .Lj1798
    ...
.Lj1806:
    movb    $1,-40(%rbp)
.Lj1798:
    cmpb    $1,-40(%rbp)
    jne     .Lj1812

If you analyse the jumps and stack values carefully (which could be considered registers for sake of simplicity), you can make an assumption and shortcut a jump in the program flow:

- Prior to "je .Lj1798", the value of -40(%rbp) is set to 13.
- If the program flow jumps here, "cmp $1,-40(%rbp)" sets flags such that "jne .Lj1812" will definitely branch, because -40(%rbp) is equal to 13 and not 1.
- Therefore, the original "je .Lj1798" branch can be redirected to "je .Lj1812"

In other words:

    jne     .Lj1806
    movb    $13,-40(%rbp)
    cmpq    $0,-32(%rbp)
    je      .Lj1812
    ...
.Lj1806:
    movb    $1,-40(%rbp)
.Lj1798:
    cmpb    $1,-40(%rbp)
    jne     .Lj1812

This block behaves exactly the same way, but we've removed a comparison and a conditional jump from the program flow, which will almost certainly result in a speed increase due to fewer instructions being executed and less pressure on the branch predictor.

The question and challenge here though... how could one implement this kind of assembly-level data-flow analysis? Stopping at "je .Lj1812" jumping to the label and then looking ahead to see "cmpb $1,-40(%rbp); jne .Lj1812" is expensive enough, but then also looking backwards to find a matching MOV instruction is even more expensive.  Similarly, looking forward from "movb $13,-40(%rbp)" and analysing every conditional jump you come across is rather prohibitive too.  If that is hard enough, look at the block of code from aasmcpu.s with the ... filled in:

    movb    $13,-40(%rbp)
    cmpq    $0,-32(%rbp)
    je      .Lj1798
    movq    -16(%rbp),%rcx
    call    AASMCPU$_$TAICPU_$__$$_INSEND$$LONGINT     movslq  %eax,%rax
    movq    -8(%rbp),%rdx
    movq    24(%rdx),%rdx
    subq    56(%rdx),%rax
    movzbl  -63(%rbp),%edx
    subq    %rdx,%rax
    subq    %rax,-24(%rbp)
    jmp     .Lj1798
    .p2align 4,,10
    .p2align 3
.Lj1806:
    movb    $1,-40(%rbp)
.Lj1798:
    cmpb    $1,-40(%rbp)
    jne     .Lj1812

(Note that the "cmpb $1,-40(%rbp)" instruction is caused by an optimisation that I'm currently developing and won't appear as such yet
- it currently appears as "movzbl -40(%rbp),%eax; cmpl $1,%eax")

The same logic applies to "jmp .Lj1798", in that -40(%rbp) is still equal to 13 and can be redirected to "jmp .Lj1812" (assuming AASMCPU$_$TAICPU_$__$$_INSEND$$LONGINT isn't malformed).  In fact, for this particular procedure, every jump to .Lj1798 sets -40(%rbp) to something other than 1 almost immediately prior; it only gets set to 1 immediately after label .Lj1806, so logically, .Lj1798 could become a dead label, and then "movb $1,-40(%rbp); cmpb $1,-40(%rbp)" are now adjacent and deterministic, meaning the "jne .Lj1812" will never branch and can be removed.  But putting that aside for the moment, how can one track the value of -40(%rbp) through all those instructions to the jump, especially through a call?

Of course, it could probably be brute-forced, but that could easily be on the order of O(n²) if not worse.  Some conservative assumptions can be made to terminate a search early, like if %rbp or %rsp (whichever is applicable) changes value or a write to general memory occurs (unless it's the stack), since the register that's dereferenced could easily be made to equal the stack pointer.

Let theorycrafting begin!

Gareth aka. Kit