x86_64: IMUL è più veloce di 2x SHL + 2x ADD?

Question

Se si guarda alla assemblea prodotto da Visual Studio (2015U2) in modalità /O2 (release) ho visto che questo pezzo 'ottimizzato a mano' di codice C si traduce di nuovo in una moltiplicazione:

int64_t calc(int64_t a) { 
    return (a << 6) + (a << 16) - a; 
} 

Assembly:

imul  rdx,qword ptr [a],1003Fh 

quindi mi chiedevo se questo è davvero più veloce di farlo nel modo in cui è scritto, qualcosa di simile:

mov   rbx,qword ptr [a] 
    mov   rax,rbx 
    shl   rax,6 
    mov   rcx,rbx 
    shl   rcx,10h 
    add   rax,rcx 
    sub   rax,rbx 

Ho sempre avuto l'impressione che la moltiplicazione sia sempre più lenta di alcuni turni/aggiunte? Non è più così con i moderni processori Intel x86_64?

Answer 1

Esatto, le moderne CPU x86 (in particolare Intel) hanno moltiplicatori ad alte prestazioni.
imul r, r/m e imul r, r/m, imm sono entrambi a 3 cicli di latenza, uno per 1c throughput su Intel SnB-family e AMD Ryzen, anche per dimensioni di operando a 64 bit.

Sulla famiglia AMD Bulldozer, ha una latenza 4c o 6c e una per 2c o una per 4c velocità effettiva. (I tempi più lenti per la dimensione dell'operando a 64 bit).

Dati da Agner Fog's instruction tables. Vedi anche altre cose nel tag wiki x86.

---

Il bilancio transistor nelle CPU moderna è abbastanza enorme, e permette per la quantità di parallelismo hardware necessario per fare un po '64 si moltiplicano con una tale bassa latenza. (It takes a lot of adders per creare un large fast multiplier).

Essendo limitato dal budget di alimentazione, non dal budget del transistor, significa che è possibile avere hardware dedicato per molte funzioni diverse, a condizione che non possano essere tutte attivate contemporaneamente (https://en.wikipedia.org/wiki/Dark_silicon). per esempio. non è possibile saturare l'unità pext/pdep, il moltiplicatore intero e le unità FMA vettoriali contemporaneamente in una CPU Intel, poiché molte di esse si trovano sulle stesse porte di esecuzione.

Il fatto divertente: imul r64 è anche 3c, quindi è possibile ottenere un risultato di moltiplicazione completo 64 * 64 => 128b in 3 cicli. imul r32 è una latenza 4c e un extra-uop, comunque. La mia ipotesi è che il ciclo extra-uop stia dividendo il risultato a 64 bit dal normale moltiplicatore a 64 bit in due metà a 32 bit.

---

compilatori in genere ottimizzare la latenza per, e in genere non sanno come ottimizzare brevi catene di dipendenza indipendenti per il throughput vs. catene di dipendenza ciclo-trasportato lungo questo collo di bottiglia sulla latenza.

gcc e clang3.8 e utilizzare successivamente fino a due istruzioni LEA anziché imul r, r/m, imm. Penso che gcc userà imul se l'alternativa è 3 o più istruzioni (escluso mov), comunque.

Questa è una scelta di ottimizzazione ragionevole, poiché una catena di distribuzione di 3 istruzioni sarebbe della stessa lunghezza di una imul su Intel. L'uso di due istruzioni a 1 ciclo spende un extra-uop per ridurre la latenza di 1 ciclo.

clang3.7 e precedenti tende a favorire imul tranne che per moltiplicatori che richiedono solo un singolo LEA o uno spostamento. Quindi clang molto recentemente cambiato per ottimizzare la latenza invece del throughput per moltiplicarsi per piccole costanti. (O forse per altri motivi, come non competere con altre cose che sono solo sulla stessa porta del moltiplicatore.)

ad es. this code on the Godbolt compiler explorer:

int foo (int a) { return a * 63; } 
    # gcc 6.1 -O3 -march=haswell (and clang actually does the same here) 
    mov  eax, edi # tmp91, a 
    sal  eax, 6 # tmp91, 
    sub  eax, edi # tmp92, a 
    ret 

clang3.8 e poi fa lo stesso codice.