[x86] Improved CMP/Jcc redundancy stripping and related fixes
Summary
This merge request improves the TEST/Jcc/TEST
set of optimisations by looking further ahead (under -O3
and above) to remove or convert more redundant CMP/Jcc and TEST/Jcc pairs. This is done by noting that they have a deterministic result due to the presence of near-identical pairs appearing earlier in the code (and whose operands have the same value).
Additionally, some related oversights and improvements have been fixed in regards to register tracking, especially with the FLAGS (e.g. RegModifiedByInstruction(NR_DEFAULTFLAGS, ...)
returned False on IMUL and IDIV instructions when they actually leave the flags in an undefined state).
System
- Processor architecture: i386, x86_64
What is the current bug behavior?
N/A
What is the behavior after applying this patch?
-
(I)MUL
and(I)DIV
instructions are more accurately handled when it comes to register tracking (not just the FLAGS register, but all registers). - Under
-O3
and above, more TEST/Jcc and CMP/Jcc pairs will be removed.
Relevant logs and/or screenshots
Under -O2, x86_64-win64, the sle
unit showcases the improved IMUL handling - before:
.section .text.n_sle$_$slegpb$longint$longint$double$double$double$double$longint_$$_decomp$longint$longint,"ax"
...
.seh_endprologue
movq %rcx,%rax
leal -1(%r8d),%edx
imull -28(%rcx),%edx
movl %edx,-24(%rax)
...
After - the optimisations in OptPass1MOV
can now see that %rax and %rcx are not affected by the 2-operand IMUL instruction and so can optimise the two MOV instructions:
.section .text.n_sle$_$slegpb$longint$longint$double$double$double$double$longint_$$_decomp$longint$longint,"ax"
...
.seh_endprologue
leal -1(%r8d),%edx
imull -28(%rcx),%edx
movl %edx,-24(%rcx)
...
Under -O4, x86_64-win64, aoptobj
shows several instances of the improved TEST/Jcc/TEST
optimisations - before:
...
.Lj43:
testq %rsi,%rsi
je .Lj27
cmpb $19,32(%rsi)
je .Lj42
testq %rsi,%rsi
je .Lj27
movzbl 32(%rsi),%edx
movl $14271372,%eax
...
After - note that even though the FLAGS get overwritten, because %rsi hasn't changed value, the second branch to .Lj27
cannot possibly be taken because it would have branched at the first .Lj27
:
...
.Lj43:
testq %rsi,%rsi
je .Lj27
cmpb $19,32(%rsi)
je .Lj42
movzbl 32(%rsi),%edx
movl $14271372,%eax
...
avltree
has an instance where a label is removed and the removal of the TEST/Jcc pair results in cascade of additional optimisation - before:
.section .text.n_avl_tree$_$tavltree_$_writereporttostream$tstream_$$_writestr$ansistring,"ax"
.balign 16,0x90
.globl AVL_TREE$_$TAVLTREE_$_WRITEREPORTTOSTREAM$TSTREAM_$$_WRITESTR$ANSISTRING
AVL_TREE$_$TAVLTREE_$_WRITEREPORTTOSTREAM$TSTREAM_$$_WRITESTR$ANSISTRING:
.Lc451:
.seh_proc AVL_TREE$_$TAVLTREE_$_WRITEREPORTTOSTREAM$TSTREAM_$$_WRITESTR$ANSISTRING
leaq -40(%rsp),%rsp
.Lc452:
.seh_stackalloc 40
.seh_endprologue
movq %rcx,%rax
testq %rdx,%rdx
je .Lj613
movq %rdx,%r8
testq %rdx,%rdx
je .Lj646
movq -8(%rdx),%r8
.Lj646:
movq 32(%rcx),%rcx
movq (%rcx),%rax
call *264(%rax)
.Lj613:
nop
leaq 40(%rsp),%rsp
.Lc453:
ret
.seh_endproc
After - je .Lj646
can never logically branch, so it and the preceding TEST instruction are removed, along with .Lj646
as there are no longer any references to it; OptPass1MOV
then simplifies the two MOV instructions either side of the TEST/Jcc pair:
.section .text.n_avl_tree$_$tavltree_$_writereporttostream$tstream_$$_writestr$ansistring,"ax"
.balign 16,0x90
.globl AVL_TREE$_$TAVLTREE_$_WRITEREPORTTOSTREAM$TSTREAM_$$_WRITESTR$ANSISTRING
AVL_TREE$_$TAVLTREE_$_WRITEREPORTTOSTREAM$TSTREAM_$$_WRITESTR$ANSISTRING:
.Lc451:
.seh_proc AVL_TREE$_$TAVLTREE_$_WRITEREPORTTOSTREAM$TSTREAM_$$_WRITESTR$ANSISTRING
leaq -40(%rsp),%rsp
.Lc452:
.seh_stackalloc 40
.seh_endprologue
movq %rcx,%rax
testq %rdx,%rdx
je .Lj613
movq -8(%rdx),%r8
movq 32(%rcx),%rcx
movq (%rcx),%rax
call *264(%rax)
.Lj613:
nop
leaq 40(%rsp),%rsp
.Lc453:
ret
.seh_endproc
cfileutl
has a more subtle one:
...
movq -8(%r12),%r12
testq %r12,%r12
je .Lj234
movq %r12,%r13
testq %r12,%r12 ; <-- Only this instruction gets removed.
jle .Lj240
xorl %r14d,%r14d
.p2align 4,,10
.p2align 3
.Lj241:
...
In this case, the jump is not removed because the second condition is different and not a subset of the first one. However, the FLAGS are guaranteed to have not changed in between, so the TEST instruction can be removed.
The classes
unit has an example where a conditional jump gets converted to an unconditional one due to the condition being an exact inverse - before:
...
.Lj6031:
testq %rax,%rax
je .Lj6036
movl 144(%rsi),%edx
cmpl 144(%rax),%edx
jne .Lj6034
testq %rax,%rax
jne .Lj6035
.Lj6036:
...
After:
...
.Lj6031:
testq %rax,%rax
je .Lj6036
movl 144(%rsi),%edx
cmpl 144(%rax),%edx
jne .Lj6034
jmp .Lj6035
.Lj6036:
...
For another IMUL tracking improvement under -O4 in sysutils
- before:
...
movl %edx,%r9d
imull $100,%r8d,%eax
leal (%eax,%ecx),%r8d
cmpl $10,%r10d
jnb .Lj7062
addl $3,%r10d
jmp .Lj7063
.p2align 4,,10
.p2align 3
.Lj7062:
subl $9,%r10d
addl $1,%r8d
.Lj7063:
movw %r8w,(%rbx)
movw %r10w,(%rsi)
movw %r9w,(%rdi)
.Lj7056:
...
After - OptPass1MOV
is able to look so far ahead, and beyond the jumps and labels, and see that %r9d and %edx have the same value throughout this entire block and so can replace %r9w with %dx at the end and remove the first MOV:
...
imull $100,%r8d,%eax
leal (%eax,%ecx),%r8d
cmpl $10,%r10d
jnb .Lj7062
addl $3,%r10d
jmp .Lj7063
.p2align 4,,10
.p2align 3
.Lj7062:
subl $9,%r10d
addl $1,%r8d
.Lj7063:
movw %r8w,(%rbx)
movw %r10w,(%rsi)
movw %dx,(%rdi)
.Lj7056:
...