04 - Algunas estructuras de control. Trucos de aritmética
Switch-case
https://godbolt.org/z/W6ere1bd9
#include <stdio.h>
void f (int a)
{
switch (a)
{
case 0: printf ("zero\n"); break;
case 1: printf ("one\n"); break;
case 2: printf ("two\n"); break;
case 3: printf ("three\n"); break;
case 4: printf ("four\n"); break;
default: printf ("something unknown\n"); break;
};
};
Se convierte en un jump table, en vez de multiples if-elseifs. En un jump table usamos el valor de la variable como desplazamiento para acceder la dirección a la que queremos brincar.
.LC0:
.string "zero"
.LC1:
.string "one"
.LC2:
.string "two"
.LC3:
.string "three"
.LC4:
.string "four"
.LC5:
.string "something unknown"
f(int):
push rbp
mov rbp, rsp
sub rsp, 16
mov DWORD PTR [rbp-4], edi
cmp DWORD PTR [rbp-4], 4
ja .L2
mov eax, DWORD PTR [rbp-4]
mov rax, QWORD PTR .L4[0+rax*8]
jmp rax
.L4:
.quad .L8
.quad .L7
.quad .L6
.quad .L5
.quad .L3
.L8:
mov edi, OFFSET FLAT:.LC0
call puts
jmp .L9
.L7:
mov edi, OFFSET FLAT:.LC1
call puts
jmp .L9
.L6:
mov edi, OFFSET FLAT:.LC2
call puts
jmp .L9
.L5:
mov edi, OFFSET FLAT:.LC3
call puts
jmp .L9
.L3:
mov edi, OFFSET FLAT:.LC4
call puts
jmp .L9
.L2:
mov edi, OFFSET FLAT:.LC5
call puts
nop
.L9:
nop
leave
ret
Usando else ifs quedaría algo así:
g(int):
push rbp
mov rbp, rsp
sub rsp, 16
mov DWORD PTR [rbp-4], edi
cmp DWORD PTR [rbp-4], 0
jne .L11
mov edi, OFFSET FLAT:.LC0
call puts
jmp .L17
.L11:
cmp DWORD PTR [rbp-4], 1
jne .L13
mov edi, OFFSET FLAT:.LC1
call puts
jmp .L17
.L13:
cmp DWORD PTR [rbp-4], 2
jne .L14
mov edi, OFFSET FLAT:.LC2
call puts
jmp .L17
.L14:
cmp DWORD PTR [rbp-4], 3
jne .L15
mov edi, OFFSET FLAT:.LC3
call puts
jmp .L17
.L15:
cmp DWORD PTR [rbp-4], 4
jne .L16
mov edi, OFFSET FLAT:.LC4
call puts
jmp .L17
.L16:
mov edi, OFFSET FLAT:.LC5
call puts
.L17:
nop
leave
ret
For loop
#include <stdio.h>
void foo(int i){
printf ("%d\n", i);
};
int main() {
int i;
for (i=0; i<5; i++)
foo(i);
return 0;
};
Con la opción -O0 utiliza una variable local para llevar cuenta de la i.
.LC0:
.string "%d\n"
foo(int):
push rbp
mov rbp, rsp
sub rsp, 16
mov DWORD PTR [rbp-4], edi
mov eax, DWORD PTR [rbp-4]
mov esi, eax
mov edi, OFFSET FLAT:.LC0
mov eax, 0
call printf
nop
leave
ret
main:
push rbp
mov rbp, rsp
sub rsp, 16
mov DWORD PTR [rbp-4], 0
jmp .L3
.L4:
mov eax, DWORD PTR [rbp-4]
mov edi, eax
call foo(int)
add DWORD PTR [rbp-4], 1
.L3:
cmp DWORD PTR [rbp-4], 4
jle .L4
mov eax, 0
leave
ret
Con la opción -O2 hace uso de un registro para llevar cuenta de la i e incorpora la invocación del printf dentro de main (en vez de invocar a foo). Tampoco hace la comparación inicial contra 5.
.LC0:
.string "%d\n"
foo(int):
mov esi, edi
xor eax, eax
mov edi, OFFSET FLAT:.LC0
jmp printf
main:
push rbx
xor ebx, ebx
.L4:
mov esi, ebx
mov edi, OFFSET FLAT:.LC0
xor eax, eax
add ebx, 1
call printf
cmp ebx, 5
jne .L4
xor eax, eax
pop rbx
ret
En este caso, el compilador no sabe de antemano los valores que tendrán a y b por lo tanto debe hacer la comparación inicial. Nota que mueve el printf al main y maneja el contador y el límite usando registros (ebx y ebp).
void foo(int a, int b){
for (int i=a; i<b; i++)
printf ("%d\n", i);
};
int main() {
int i,j;
scanf("%d", &i);
scanf("%d", &j);
foo(i,j);
return 0;
};
.LC1:
.string "%d"
main:
push rbp
mov edi, OFFSET FLAT:.LC1
xor eax, eax
push rbx
sub rsp, 24
lea rsi, [rsp+8]
call __isoc99_scanf
lea rsi, [rsp+12]
mov edi, OFFSET FLAT:.LC1
xor eax, eax
call __isoc99_scanf
mov ebp, DWORD PTR [rsp+12]
mov ebx, DWORD PTR [rsp+8]
cmp ebp, ebx
jle .L11
.L12:
mov esi, ebx
mov edi, OFFSET FLAT:.LC0
xor eax, eax
add ebx, 1
call printf
cmp ebp, ebx
jne .L12
.L11:
add rsp, 24
xor eax, eax
pop rbx
pop rbp
ret
A veces, si la cantidad de vueltas es pequeña, el compilador hace loop unwinding
void foo(int a, int b){
for (int i=a; i<b; i++)
printf ("%d\n", i);
};
int main() {
foo(5,7);
return 0;
};
main:
sub rsp, 8
mov esi, 5
mov edi, OFFSET FLAT:.LC0
xor eax, eax
call printf
mov esi, 6
mov edi, OFFSET FLAT:.LC0
xor eax, eax
call printf
xor eax, eax
add rsp, 8
ret
void my_memcpy ( char* dst, char* src, unsigned int cnt)
{
unsigned int i;
for (i=0; i<cnt; i++)
dst[i]=src[i];
};
Usando -O1
my_memcpy(char*, char*, unsigned int):
test edx, edx
je .L1
mov edx, edx
mov eax, 0
.L3:
movzx ecx, BYTE PTR [rsi+rax]
mov BYTE PTR [rdi+rax], cl
add rax, 1
cmp rax, rdx
jne .L3
.L1:
ret
Usado -Os
my_memcpy(char*, char*, unsigned int):
xor eax, eax
.L2:
cmp eax, edx
jnb .L5
mov cl, BYTE PTR [rsi+rax]
mov BYTE PTR [rdi+rax], cl
inc rax
jmp .L2
.L5:
ret
Usando -O3
my_memcpy(char*, char*, unsigned int):
mov rcx, rdi
mov eax, edx
test edx, edx
je .L1
lea edx, [rdx-1]
cmp edx, 6
jbe .L3
lea r8, [rsi+1]
sub rdi, r8
cmp rdi, 14
ja .L24
.L3:
mov edx, eax
xor eax, eax
.L9:
movzx edi, BYTE PTR [rsi+rax]
mov BYTE PTR [rcx+rax], dil
add rax, 1
cmp rdx, rax
jne .L9
.L1:
ret
.L24:
mov edi, eax
cmp edx, 14
jbe .L11
shr edi, 4
xor edx, edx
sal rdi, 4
.L5:
movdqu xmm0, XMMWORD PTR [rsi+rdx]
movups XMMWORD PTR [rcx+rdx], xmm0
add rdx, 16
cmp rdx, rdi
jne .L5
mov edx, eax
and edx, -16
test al, 15
je .L1
mov edi, eax
sub edi, edx
lea r8d, [rdi-1]
cmp r8d, 6
jbe .L7
.L4:
mov r8d, edx
mov r9, QWORD PTR [rsi+r8]
mov QWORD PTR [rcx+r8], r9
mov r8d, edi
and r8d, -8
add edx, r8d
and edi, 7
je .L1
.L7:
mov edi, edx
movzx r8d, BYTE PTR [rsi+rdi]
mov BYTE PTR [rcx+rdi], r8b
lea edi, [rdx+1]
cmp edi, eax
jnb .L1
movzx r8d, BYTE PTR [rsi+rdi]
mov BYTE PTR [rcx+rdi], r8b
lea edi, [rdx+2]
cmp edi, eax
jnb .L1
movzx r8d, BYTE PTR [rsi+rdi]
mov BYTE PTR [rcx+rdi], r8b
lea edi, [rdx+3]
cmp edi, eax
jnb .L1
movzx r8d, BYTE PTR [rsi+rdi]
mov BYTE PTR [rcx+rdi], r8b
lea edi, [rdx+4]
cmp edi, eax
jnb .L1
movzx r8d, BYTE PTR [rsi+rdi]
mov BYTE PTR [rcx+rdi], r8b
lea edi, [rdx+5]
cmp edi, eax
jnb .L1
movzx r8d, BYTE PTR [rsi+rdi]
add edx, 6
mov BYTE PTR [rcx+rdi], r8b
cmp edx, eax
jnb .L1
movzx eax, BYTE PTR [rsi+rdx]
mov BYTE PTR [rcx+rdx], al
ret
.L11:
xor edx, edx
jmp .L4
https://www.chessprogramming.org/X86-64
Menciona sobre los registros MMX (64-bits/cu), SSS (128-bits/cu), AVX (256-bits/cu, https://en.wikipedia.org/wiki/Advanced_Vector_Extensions) y AVX-512 (512-bit) (solo en Xeon Phi)
Si compilas usando la opción -march="sandybridge" el compilador utilizará los registros ymm y sus instrucciones!
vmovdqu xmm1, XMMWORD PTR [rsi+rax]
vinsertf128 ymm0, ymm1, XMMWORD PTR [rsi+16+rax], 0x1
vmovdqu XMMWORD PTR [rcx+rax], xmm0
vextractf128 XMMWORD PTR [rcx+16+rax], ymm0, 0x1
Aritmética
Multiplicación por constante
unsigned int bah(unsigned int n) {
return n*2;
};
bah(unsigned int):
lea eax, [rdi+rdi]
ret
unsigned int bah(unsigned int n) {
return n*3;
};
bah(unsigned int):
lea eax, [rdi+rdi*2]
ret
Por cuánto se está "multiplicando" en este caso
bah(unsigned int):
lea eax, [rdi+rdi*2]
add eax, eax
ret
Y este:
bah(unsigned int):
lea eax, [rdi+rdi*2]
lea eax, [rdi+rax*4]
ret
Este se multiplica por lo mismo que el anterior pero fue obtenido usando -O0
bah(unsigned int):
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-4], edi
mov edx, DWORD PTR [rbp-4]
mov eax, edx
add eax, eax
add eax, edx
sal eax, 2
add eax, edx
pop rbp
ret
División por constante
unsigned int bah(unsigned int n) {
return n/4;
};
bah(unsigned int):
mov eax, edi
shr eax, 2
ret
unsigned int bah(unsigned int n) {
return n/5;
};
bah(unsigned int):
mov eax, edi
mov edx, 3435973837
imul rax, rdx
shr rax, 34
ret
Porque 3435973837 / 2^34 = 0.20000000001 = 1/5
unsigned int bah(unsigned int n) {
return n/17;
};
bah(unsigned int):
mov eax, edi
mov edx, 4042322161
imul rax, rdx
shr rax, 36
ret
Porque
En la sección Division by constant en https://en.wikipedia.org/wiki/Division_algorithm puedes ver una explicación sencilla de cómo convertir una división en una multiplicación seguida de shift.
En escencia, dividir por es equivalente a multiplicar por . Así que convertimos a en una fracción equivalente tal que sea una potencia de 2 (para que lo podamos hacer por shifts). Si enconces si escoges la como una potencia de 2, puedes calcular resolviendo .
Por ejemplo, para .
Si escoges , entonces:
Modulo por constante
is equivalent to .
Porque, si A = B * cociente + residuo, entonces
y
unsigned int bah(unsigned int n) {
return n%3;
};
bah(unsigned int):
mov eax, edi
mov edx, 2863311531
imul rax, rdx
shr rax, 33
lea edx, [rax+rax*2]
mov eax, edi
sub eax, edx
ret
(edi * 1/3)*3 - edi = remainder
Si tu intención es ocupar el mínimo espacio y compilas con -Os, pagarás el precio en rendimiento pues el código resultante incluye a div (que requiere significativamente más ciclos que mul). Puedes ver detalles de ciclos en https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html
bah(unsigned int):
mov eax, edi
mov ecx, 3
xor edx, edx
div ecx
mov eax, edx
ret
Updates
Creo que el código de clang que realiza la síntesis de divisiones está en https://codebrowser.dev/llvm/llvm/lib/Transforms/Scalar/DivRemPairs.cpp.html
https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html -freciprocal-math
https://opensource.apple.com/source/clang/clang-600.0.51/src/lib/Transforms/Utils/IntegerDivision.cpp.auto.html - Here we have some code generation but I believe it is not for constant values.
/tmp/llvm-project/llvm/lib/Target/X86 X86ISelLowering.cpp 24607: // Enable estimate codegen with 1 refinement step for vector division. 24608: // Scalar division estimates are disabled because they break too much 24639:/// If we have at least two divisions that use the same divisor, convert to 24641:/// CPU if a division's cost is not at least twice the cost of a multiplication. 24642:/// This is because we still need one division to calculate the reciprocal and 24644:/// original divisions. 33785: // division/remainder by constant optimize it. 58554: // Integer division on x86 is expensive. However, when aggressively optimizing 58557: // The exception to this is vector division. Since x86 doesn't have vector 58558: // integer division, leaving the division as-is is a loss even in terms of