gaul / x86lint

Examine x86 machine code to find suboptimal encodings and sequences

x86lint

x86lint examines x86 machine code to find suboptimal encodings and sequences. For example, add eax, 1 can encode with either an 8- or 32-bit immediate:

83C0 01
81C0 01000000

Using the former can result in smaller and faster code. x86lint can help compiler writers generate better code and documents the complexity of x86.

Implemented analyses

• implicit EAX
  • 81C0 00010000 instead of 05 00010000 (ADD EAX, 0x100)
• missing LOCK prefix on CMPXCHG and XADD
• oversized immediates
  • 81C0 01000000 instead of 83C0 01 (ADD EAX, 1)
• strength-reduce AND with immediate to MOVZBL
• suboptimal CMP 0 83FF 00 instead of TEST 85C0
• suboptimal no-ops
  • multiple 90 instead of a single 60 90, etc.
• suboptimal zero register, see #7
  • MOV EAX, 0 instead of XOR EAX, EAX
• unnecessary REX prefix
  • XOR RAX, RAX 4831C0 instead of XOR EAX, EAX 31C0
  • 40C9 instead of C9 (LEAVE)
• unnecessary immediate
  • C1D0 01 instead of D1D0 (RCL EAX, 1)
• unneeded LOCK prefix on XCHG

Compilation

First install the Intel x86 encoder decoder:

git clone https://github.com/intelxed/xed.git xed
git clone https://github.com/intelxed/mbuild.git mbuild
cd xed
./mfile.py install --install-dir=kits/xed-install

Next build x86lint:

git clone https://github.com/gaul/x86lint.git x86lint
cd x86lint
XED_PATH=/path/to/xed make all

Usage

x86lint is intended to be part of compiler test suites which should #include "x86lint.h" and link libx86lint.a. It can also read arbitrary ELF executables via:

./x86lint /bin/ls

References

• Agner Fog optimization guide
• Intel instruction set reference
• Intel optimization manual
• Intel x86 encoder decoder - library to parse instructions

License

Copyright (C) 2018 Andrew Gaul

Licensed under the Apache License, Version 2.0

x86lint's Issues

`ROR r32, 31` vs. `ROL r32, 1`

ROR has double throughput due to the O flag adjustment:

https://twitter.com/InstLatX64/status/1617441326047395840

Overlarge branch displacements

Reference: https://maskray.me/blog/2024-04-27-clang-o0-output-branch-displacement-and-size-increase

Rename to x86lint

Unneeded SIB byte

Simple indirect references can elide the SIB byte:

C645 04 05           mov byte[ebp+4],5
C64465 04 05         mov byte[ebp+4],5
C64425 04 05         mov byte[ebp+4],5
C644A5 04 05         mov byte[ebp+4],5
C644E5 04 05         mov byte[ebp+4],5

From https://www.strchr.com/machine_code_redundancy.

Use upper half registers AH, BH, etc. for bitmask operations when possible

GCC can save a byte in some situations:

http://gallium.inria.fr/blog/intel-skylake-bug/#the-revelation

Unneeded LOCK prefix on XCHG

This is inherently atomic. Reference:

https://devblogs.microsoft.com/oldnewthing/20190131-00/?p=100845

Optimal no-ops

It is better to use fewer but longer no-ops to achieve padding. Some examples:

1:  90                             nop
2:  66 90                          data16 nop
3:  0F 1F 00                       nopl  %eax, (%rax)
4:  0F 1F 40 00                    nopl  %eax, (%rax)
5:  0F 1F 44 00 00                 nopl  %eax, (%rax,%rax,1)
6:  66 0F 1F 44 00 00              nopw  %ax,  (%rax,%rax,1)
7:  0F 1F 80 00 00 00 00           nopl  %eax, (%rax)
8:  0F 1F 84 00 00 00 00 00        nopl  %eax, (%rax,%rax,1)
9:  66 0F 1F 84 00 00 00 00 00     nopw  %ax,  (%rax,%rax,1)
10: 66 2E 0F 1F 84 00 00 00 00 00  nopw  %ax,  (%rax,%rax,1)

More recent processors support efficient 15-byte no-ops as well. References:

• https://stackoverflow.com/a/12564044/2800111
• https://bugzilla.mozilla.org/show_bug.cgi?id=1568450#c8
• https://github.com/llvm/llvm-project/blob/2463239777bfb41f63bb50d3eb931719612ddd0a/llvm/lib/Target/X86/MCTargetDesc/X86AsmBackend.cpp#L341-L347

Suboptimal zero register should consider flags

Some sequences like the following:

YDIS: cmp byte ptr [rbx+rdx*1-0x1], 0x2f
YDIS: mov ecx, 0x0
YDIS: cmovz eax, ecx

use mov, ecx, 0x0 instead of xor ecx, ecx because the former preserves the flags and the latter does not. Could x86lint do a limited multi-instruction analysis to avoid these false positives?

MOVZBL and MOVZWL can replace AND with immediates 0xFF and 0xFFFF

Instead of:

movl    %edi, %eax
andl    $255, %eax

prefer

movzbl    %dil, %eax

Note that AND is the same length as MOVZBL but the latter has a more flexible destination register.

Suggested by Martin Möhrmann.

SUB EAX, -128 can be shorter than ADD EAX, 128

SUB EAX, -128 can use a one-byte immediate while ADD EAX, 128 must use 4-bytes. GCC generates these when adding 127, 128, and 129 to a int32_t:

        addl    $127, %eax
        subl    $-128, %eax
        addl    $129, %eax

Suggested by Martin Möhrmann.

Division by constants

Can replace division by constants with magic multiplication:

https://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html

Nonsense instructions

Look for MOV RAX, RAX, etc. Need to be careful about true no-ops.

Unneeded zero offset

Indirect loads with zero offset do not need an immediate:

013E                 add dword[esi],edi
017E 00              add dword[esi+00],edi
01BE 00000000        add dword[esi+00000000],edi

From https://www.strchr.com/machine_code_redundancy.

Look at binary visualization

http://binvis.io/ draws some interesting visuals -- maybe a way to look at register usage, immediates, AVX, etc.?

Unintentional use of x87

This is speculative, but I have noticed unexpected use of x87 floating-point on x86-64 where I assumed that SSE would be more efficient since few programs take advantage of 80-bit precision. Also I wonder if there is an overhead for task-switching the additional registers or power usage for using these legacy instructions?

Unintentional use of SSE

Some code unintentionally uses SSE:

unsigned int fp_func(unsigned int x) { return x * 0.8; }
unsigned int int_func(unsigned int x) { return x * 10 / 8; }

The integer version is shorter and more efficient:

$ gcc -O2 -S -o - foo.c | as -al
...
   9 0000 89FF           movl %edi,%edi
  10 0002 660FEFC0       pxor %xmm0,%xmm0
  11 0006 F2480F2A       cvtsi2sdq %rdi,%xmm0
  11      C7
  12 000b F20F5905       mulsd .LC0(%rip),%xmm0
  12      00000000 
  13 0013 F2480F2C       cvttsd2siq %xmm0,%rax
  13      C0
  14 0018 C3             ret
...
  24 0020 8D04BF         leal (%rdi,%rdi,4),%eax
  25 0023 01C0           addl %eax,%eax
  26 0025 C1E803         shrl $3,%eax
  27 0028 C3             ret
...
  33                    .LC0:
  34 0000 9A999999       .long -1717986918
  35 0004 9999E93F       .long 1072273817

Investigate macro-op fusion

https://en.wikichip.org/wiki/macro-operation_fusion#x86

Integration with sampling profilers

This would identify specific hotspots that could benefit from optimization. Does perf have the ability to dump machine code? x86lint would need some extension to read non-ELF output.

Multiply by constants

Can replace with LEA in some situations.

Ensure alignment for jump targets

Should be 16-byte alignment.

Unnecessary movslq

cltq can replace movslq %eax, %rax.

INC vs. ADD RAX, 1 and DEC vs. SUB RAX, 1

This has some nuance since INC and DEC partially update flags but these can be the same speed but smaller than ADD RAX, 1 and SUB RAX, 1 on modern CPUs:

https://stackoverflow.com/a/36510865

and much faster on one AMD variant:

https://msrc-blog.microsoft.com/2021/01/11/building-faster-amd64-memset-routines/#post-12548:~:text=Mysterious%20AMD%2DFX%208100%20Perf%20Regression