assembly - ¿Por qué el compilador de Intel prefiere NEG+ADD sobre SUB?

x86 micro-optimization

Question

Al examinar la salida de varios compiladores para una variedad de fragmentos de código, noté que el compilador de C de Intel (ICC) tiene una fuerte tendencia a preferir emitir un par de instrucciones NEG + ADD donde otros compiladores usarían una sola instrucción SUB .

Como un ejemplo simple, considere el siguiente código C:

uint64_t Mod3(uint64_t value)
{
    return (value % 3);
}

ICC traduce esto al siguiente código de máquina (independientemente del nivel de optimización):

mov       rcx, 0xaaaaaaaaaaaaaaab
mov       rax, rdi
mul       rcx
shr       rdx, 1
lea       rsi, QWORD PTR [rdx+rdx*2]
neg       rsi                            ; /  equivalent to:
add       rdi, rsi                       ; /    sub  rdi, rsi
mov       rax, rdi
ret         

Mientras que otros compiladores (incluidos MSVC, GCC y Clang) generarán código esencialmente equivalente, excepto que la secuencia NEG + ADD se reemplaza por una única instrucción SUB .

Como dije, esto no es solo una peculiaridad de cómo ICC compila este fragmento en particular. Es un patrón que he observado repetidamente cuando analizo el desmontaje de operaciones aritméticas. Normalmente no pensaría mucho sobre esto, excepto que se sabe que ICC es un compilador de optimización bastante bueno y lo desarrollan personas que tienen información privilegiada sobre sus microprocesadores.

¿Podría haber algo que Intel sepa sobre la implementación de la instrucción SUB en sus procesadores que lo hace más óptimo para descomponerlo en instrucciones NEG + ADD ? El uso de instrucciones estilo RISC que decodifican en μops más simples es un consejo de optimización bien conocido para las microarquitecturas modernas, por lo que es posible que SUB se descomponga internamente en NEG individuales y ADD , y que en realidad sea más eficiente para el decodificador frontal para usar estas instrucciones "más simples"? Las CPU modernas son complicadas , por lo que todo es posible.

Sin embargo, las exhaustivas tablas de instrucciones de Agner Fog confirman mi intuición de que esto es en realidad una pesimización. SUB es igual de eficiente que ADD en todos los procesadores, por lo que la instrucción NEG requerida adicional solo sirve para desacelerar las cosas.

También ejecuté las dos secuencias a través del propio analizador de código de arquitectura de Intel para analizar el rendimiento. Aunque los recuentos de ciclos exactos y las conexiones de puertos varían de una microarquitectura a otra, un solo SUB parece ser superior en todos los aspectos desde Nehalem hasta Broadwell. Aquí están los dos informes generados por la herramienta para Haswell:

SUB

Intel(R) Architecture Code Analyzer Version - 2.2 build:356c3b8 (Tue, 13 Dec 2016 16:25:20 +0200) Binary Format - 64Bit Architecture - HSW Analysis Type - Throughput Throughput Analysis Report -------------------------- Block Throughput: 1.85 Cycles Throughput Bottleneck: Dependency chains (possibly between iterations) Port Binding In Cycles Per Iteration: --------------------------------------------------------------------------------------- | Port | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 | --------------------------------------------------------------------------------------- | Cycles | 1.0 0.0 | 1.5 | 0.0 0.0 | 0.0 0.0 | 0.0 | 1.8 | 1.7 | 0.0 | --------------------------------------------------------------------------------------- | Num Of | Ports pressure in cycles | | | Uops | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 | | --------------------------------------------------------------------------------- | 1 | 0.1 | 0.2 | | | | 0.3 | 0.4 | | CP | mov rax, 0xaaaaaaaaaaaaaaab | 2 | | 1.0 | | | | | 1.0 | | CP | mul rcx | 1 | 0.9 | | | | | | 0.1 | | CP | shr rdx, 0x1 | 1 | | | | | | 1.0 | | | CP | lea rax, ptr [rdx+rdx*2] | 1 | | 0.3 | | | | 0.4 | 0.2 | | CP | sub rcx, rax | 1* | | | | | | | | | | mov rax, rcx Total Num Of Uops: 7 NEG + ADD

Intel(R) Architecture Code Analyzer Version - 2.2 build:356c3b8 (Tue, 13 Dec 2016 16:25:20 +0200)
Binary Format - 64Bit
Architecture  - HSW
Analysis Type - Throughput

Throughput Analysis Report
--------------------------
Block Throughput: 2.15 Cycles       Throughput Bottleneck: Dependency chains (possibly between iterations)

Port Binding In Cycles Per Iteration:
---------------------------------------------------------------------------------------
|  Port  |  0   -  DV  |  1   |  2   -  D   |  3   -  D   |  4   |  5   |  6   |  7   |
---------------------------------------------------------------------------------------
| Cycles | 1.1    0.0  | 2.0  | 0.0    0.0  | 0.0    0.0  | 0.0  | 2.0  | 2.0  | 0.0  |
---------------------------------------------------------------------------------------

| Num Of |                    Ports pressure in cycles                     |    |
|  Uops  |  0  - DV  |  1  |  2  -  D  |  3  -  D  |  4  |  5  |  6  |  7  |    |
---------------------------------------------------------------------------------
|   1    | 0.1       | 0.9 |           |           |     | 0.1 | 0.1 |     |    | mov rax, 0xaaaaaaaaaaaaaaab
|   2    |           | 1.0 |           |           |     |     | 1.0 |     | CP | mul rcx
|   1    | 1.0       |     |           |           |     |     |     |     | CP | shr rdx, 0x1
|   1    |           |     |           |           |     | 1.0 |     |     | CP | lea rax, ptr [rdx+rdx*2]
|   1    |           | 0.1 |           |           |     | 0.8 | 0.1 |     | CP | neg rax
|   1    | 0.1       |     |           |           |     | 0.1 | 0.9 |     | CP | add rcx, rax
|   1*   |           |     |           |           |     |     |     |     |    | mov rax, rcx
Total Num Of Uops: 8

Entonces, hasta donde puedo decir, NEG + ADD aumenta el tamaño del código, aumenta el número de μops, aumenta la presión para los puertos de ejecución y aumenta el número de ciclos, lo que resulta en una disminución neta en el rendimiento en comparación con SUB . Entonces, ¿por qué el compilador de Intel está haciendo esto?

¿Es esto solo una peculiaridad del generador de código que se debe informar como un defecto, o me falta algo de mérito en mi análisis?

Answer 1

Extrañamente tengo una respuesta simple: porque ICC no es óptimo.

Cuando escribe su propio compilador, comienza con un conjunto básico de códigos de operación: NOP , MOV , ADD ... hasta 10 códigos de operación. No usa SUB por un tiempo porque podría ser reemplazado fácilmente por: ADD NEGgative operand . NEG no es básico también, ya que podría ser reemplazado por: XOR FFFF...; ADD 1 XOR FFFF...; ADD 1 .

Por lo tanto, implementa un direccionamiento bastante complejo basado en bits de tipos y tamaños de operandos. Lo hace por una sola instrucción de código máquina (por ejemplo, ADD ) y planea usarlo más para la mayoría de las otras instrucciones. ¡Pero en este momento su compañero de trabajo termina la implementación del cálculo óptimo del resto sin el uso de SUB ! Imagínense: ya se llama "Óptimo_Mod", por lo que echan de menos algo inóptimo dentro, no porque seas un tipo malo y odies a AMD, sino porque ya lo ves, ya se lo llama óptimo, optimizado.

Intel Compiler es bastante bueno en general, pero tiene un largo historial de versiones, por lo que puede comportarse de manera extraña en algunos casos excepcionales. Sugiero que informe a Intel sobre este problema y mire lo que sucederá.