x86 Instrucción MUL de VS 2008/2010

¿Los conjuros modernos (2008/2010) de Visual Studio o Visual C ++ Express producirán instrucciones MULM de x86 (multiplicación sin signo) en el código comstackdo? Parece que no puedo encontrar un ejemplo en el que aparezcan en código comstackdo, incluso cuando se usan tipos sin firmar.

Si VS no comstack utilizando MUL, ¿hay alguna razón por la cual?

imul (signed) y mul (unsigned) tienen un formulario de un solo operando que hace edx:eax = eax * src . es decir, 32x32b => 64b multiplicación completa (o 64x64b => 128b).

286 agregaron un imul dest(reg), src(reg/mem), immediate forma imul dest(reg), src(reg/mem), immediate , y 386 agregaron una forma imul r32, r/m32 , ambas de las cuales solo computan la mitad inferior del resultado. (Enlace desde la wiki de la etiqueta x86 ).

Al multiplicar dos valores de 32 bits, los 32 bits menos significativos del resultado son los mismos, independientemente de que los valores estén firmados o no. En otras palabras, la diferencia entre una multiplicación con signo y sin signo se vuelve aparente solo si se mira la mitad “superior” del resultado, qué imul / mul un solo operando pone en edx y dos o tres imul operando no se imul ninguna parte. Por lo tanto, las formas multi-operandos de imul se pueden usar en valores firmados y sin firmar, y no hubo necesidad de que Intel agregue nuevas formas de mul también. (Podrían haber hecho multi-operando mul sinónimo de imul , pero eso haría que el desensamblaje no coincida con la fuente).

En C, los resultados de las operaciones aritméticas tienen el mismo tipo que los operandos (después de la promoción de enteros para tipos enteros estrechos). Si multiplicas dos int juntos, obtienes un int , no long long : la “mitad superior” no se retiene. Por lo tanto, el comstackdor de C solo necesita lo que imul proporciona, y dado que imul es más fácil de usar que mul , el comstackdor de C usa imul para evitar que se necesiten instrucciones de mov para que los datos entren y salgan de eax .

Como segundo paso, dado que los comstackdores de C usan la forma de múltiples operandos de imul mucho, Intel y AMD invierten esfuerzos para hacerlo lo más rápido posible. Solo escribe un registro de salida, no e/rdx:e/rax , por lo que las CPU pudieron optimizarlo más fácilmente que la forma de un solo operando. Esto hace que imul sea ​​aún más atractivo.

La forma de un solo operando de mul / imul es útil al implementar la aritmética de números grandes. En C, en el modo de 32 bits, debe obtener algunas mul multiplicando los valores unsigned long long juntos. Pero, según el comstackdor y el sistema operativo, esos mul múltiples pueden estar ocultos en alguna función dedicada, por lo que no necesariamente los verás. En el modo de 64 bits, long long tiene solo 64 bits, no 128, y el comstackdor simplemente usará imul .

Hay tres tipos diferentes de instrucciones de multiplicación en x86. El primero es MUL reg , que realiza una multiplicación sin signo de EAX por reg y coloca el resultado (de 64 bits) en EDX:EAX . El segundo es IMUL reg , que hace lo mismo con un multiplicado firmado. El tercer tipo es IMUL reg1, reg2 (multiplica reg1 con reg2 y almacena el resultado de 32 bits en reg1) o IMUL reg1, reg2, imm (multiplica reg2 por imm y almacena el resultado de 32 bits en reg1).

Como en C, las multiplicaciones de dos valores de 32 bits producen resultados de 32 bits, los comstackdores normalmente usan el tercer tipo (lo firmado no importa, los 32 bits bajos coinciden entre multiplicaciones de 32×32 con signo y sin signo). VC ++ generará las versiones “largas multiplicaciones” de MUL / IMUL si realmente usa los resultados completos de 64 bits, por ejemplo aquí:

 unsigned long long prod(unsigned int a, unsigned int b) { return (unsigned long long) a * b; } 

Las versiones de 2-operandos (y 3-operandos) de IMUL son más rápidas que las versiones de un solo operando simplemente porque no producen un resultado completo de 64 bits. Los multiplicadores anchos son grandes y lentos; es mucho más fácil construir un multiplicador más pequeño y sintetizar multiplicaciones largas utilizando Microcode si es necesario. Además, MUL / IMUL escribe dos registros, que de nuevo generalmente se resuelven dividiéndolo en varias instrucciones internamente: es mucho más fácil para el hardware de reordenamiento de instrucciones hacer un seguimiento de dos instrucciones dependientes que cada uno escribe un registro (la mayoría de las instrucciones x86 se parecen a eso internamente) ) de lo que es para realizar un seguimiento de una instrucción que escribe dos.

De acuerdo con http://gmplib.org/~tege/x86-timing.pdf , la instrucción IMUL tiene una latencia más baja y un mayor rendimiento (si estoy leyendo la tabla correctamente). Quizás VS simplemente está usando la instrucción más rápida (suponiendo que IMUL y MUL siempre producen la misma salida).

No tengo Visual Studio a mano, así que traté de obtener algo más con GCC. También siempre obtengo alguna variación de IMUL .

Esta:

 unsigned int func(unsigned int a, unsigned int b) { return a * b; } 

Se une a esto (con -O2):

 _func: LFB2: pushq %rbp LCFI0: movq %rsp, %rbp LCFI1: movl %esi, %eax imull %edi, %eax movzbl %al, %eax leave ret 

Mi intuición me dice que el comstackdor eligió IMUL arbitrariamente (o el que fuera más rápido de los dos), ya que los bits serán los mismos ya sea que use un MUL sin firmar o un IMUL firmado. Cualquier multiplicación de enteros de 32 bits será de 64 bits que abarca dos registros, EDX:EAX . El desbordamiento entra en EDX que esencialmente se ignora, ya que solo nos importa el resultado de 32 bits en EAX . Usar IMUL se extenderá a EDX según sea necesario, pero nuevamente, no nos importa, ya que solo estamos interesados ​​en el resultado de 32 bits.

Inmediatamente después de ver esta pregunta, encontré MULQ en mi código generado al dividir.

El código completo está convirtiendo un gran número binario en trozos de mil millones para que se pueda convertir fácilmente en una cadena.

Código C ++:

 for_each(TempVec.rbegin(), TempVec.rend(), [&](Short & Num){ Remainder <<= 32; Remainder += Num; Num = Remainder / 1000000000; Remainder %= 1000000000;//equivalent to Remainder %= DecimalConvert }); 

Asamblea generada optimizada

 00007FF7715B18E8 lea r9,[rsi-4] 00007FF7715B18EC mov r13,12E0BE826D694B2Fh 00007FF7715B18F6 nop word ptr [rax+rax] 00007FF7715B1900 shl r8,20h 00007FF7715B1904 mov eax,dword ptr [r9] 00007FF7715B1907 add r8,rax 00007FF7715B190A mov rax,r13 00007FF7715B190D mul rax,r8 00007FF7715B1910 mov rcx,r8 00007FF7715B1913 sub rcx,rdx 00007FF7715B1916 shr rcx,1 00007FF7715B1919 add rcx,rdx 00007FF7715B191C shr rcx,1Dh 00007FF7715B1920 imul rax,rcx,3B9ACA00h 00007FF7715B1927 sub r8,rax 00007FF7715B192A mov dword ptr [r9],ecx 00007FF7715B192D lea r9,[r9-4] 00007FF7715B1931 lea rax,[r9+4] 00007FF7715B1935 cmp rax,r14 00007FF7715B1938 jne NumToString+0D0h (07FF7715B1900h) 

Observe la instrucción MUL 5 líneas hacia abajo. Este código generado es extremadamente poco intuitivo, lo sé, de hecho no se parece en nada al código comstackdo, pero DIV es extremadamente lento ~ 25 ciclos para un div de 32 bits, y ~ 75 según este gráfico en PC modernas en comparación con MUL o IMUL (alrededor 3 o 4 ciclos) por lo que tiene sentido tratar de deshacerse de DIV incluso si tiene que agregar todo tipo de instrucciones adicionales.

No entiendo completamente la optimización aquí, pero si desea ver una explicación racional y matemática del uso del tiempo de comstackción y la multiplicación para dividir las constantes, consulte este documento .

Este es un ejemplo de cómo el comstackdor utiliza el rendimiento y la capacidad de la multiplicación no reducida de 64 por 64 bits sin mostrar ningún signo del codificador de c ++.

Como ya se explicó, C / C ++ no hace word*word to double-word operaciones de word*word to double-word , que es para lo que es mejor la instrucción mul . Pero hay casos en los que desea word*word to double-word lo que necesita una extensión para C / C ++.

GCC, Clang e ICC brindan un tipo incorporado __int128 que puede usar para obtener indirectamente la instrucción mul .

Con MSVC proporciona el _umul128 intrínseco (al menos VS 2010) que genera la instrucción mul . Con esto intrínseco junto con el intrínseco _addcarry_u64 , podría construir su propio tipo de __int128 eficiente con __int128 .