Tips for golfing in x86/x64 machine code

Question

I noticed that there's no such question, so here it is:

Do you have general tips for golfing in x86/x64 machine code? If the tip only applies to a certain environment or calling convention, please specify that in your answer.

Please only one tip per answer (see here).

Answer 1

Use shr for first occurrence lookup tables

Often times you need to do something like this to check whether a byte has been encountered:

bool found[256]={false};
for (uint8_t x : data) {
    // Check for first occurrence
    if (!found[x]) {
        // mark it as encountered
        found[x] = true;
        // do something
        func(x);
    }
}

There is a very easy way to do this in x86, and that is via shr.

Setup

Setting it up is easy thanks to push -1 which can create a block of 1 bits. I use x86_64 here, but it is the same on x86.

You can switch it to rep stos if you have that set up, but it isn't worth it to set up just for that loop.

        push    TABLE_SIZE/8
        pop     rcx
.Lpush_loop:
        push    -1
        loop    .Lpush_loop

Usage

shr will both mark the occurrence and indicate that it was unique by setting OF.

.Lloop:
        lodsb # example

        # 3 bytes (2 bytes if you use RDI/RBX/RBP/RSI or a register src)
        shr     byte ptr [rsp + rax]
        # OF == first occurrence
        jno     .Lfound

.Lfirst_occurrence:
        ...
.Lfound:
        loop    .Lloop # example

Magic.

See my answer for Type uniqchars! where I thoroughly explain it.

Answer 2

Align Registers to by Power of 2 Value with or/inc

Say you want to aligned a pointer for a load. I.e saying aligning for xmm load:

This is a pretty common idiom:

addq $16, %rdi   // 4b
andq $-16, %rdi  // 4b

A cheaper way:

orq $15, %rdi    // 4b
incq %rdi        // 3b

If your pointer is in RAX, the special 2-byte op al, imm8 no-modrm encoding is useful. Writing a byte or word register leaves the upper bytes untouched. On older Intel CPUs (before Sandybridge) this can cause a partial-register stall, but even for performance it's safe on modern CPUs.

or  $0xf, %al     // 2b   (leave upper bytes untouched)
inc %rax          // 3b   (carry into the upper bytes is possible)

or  $0xf, %dl     // 3b
inc %rdx          // 3b

or  $0xf, %dil    // 4b  REX + opcode + modrm + imm8
inc %rdi          // 3b  no savings

Also works with and $0xf0, %al to round down to the previous alignment boundary.

---

Also worth noting the or alone will round to value minus 1 so it can be used to keep address offsets in imm8 short encoding range i.e:

andq $-16, %rdi
// Stuff on (%rdi)[0, 79]
vmovdqa 80(%rdi), %xmm0

vs.

orq $15, %rdi
// Stuff on -15(%rdi)[0, 79]
vmovdqa 65(%rdi), %xmm0
# vmovdqa 80 - 15(%rdi), %xmm0   # same thing, but with the -15 in the asm source

Answer 3

pop ax and throw a value from stack

pop eax

push word 0; push word 8

push dword 8

push dword 9999

push word 0
push word 9999

Answer 4

AND to clear memory

0:  c7 01 00 00 00 00       mov    DWORD PTR [ecx],0x0
6:  31 c0 89 01             xor    eax,eax / mov DWORD PTR [ecx],eax
a:  83 21 00                and    DWORD PTR [ecx],0x0 

Answer 5

You can fetch sequential objects from the stack by setting esi to esp, and performing a sequence of lodsd/xchg reg, eax.