Perché GCC genera un assemblaggio così radicalmente diverso per quasi lo stesso codice C?

Question

Durante la scrittura di una funzione ottimizzata ftol ho trovato un comportamento molto strano in GCC 4.6.1. Lascia che ti mostri il codice prima (per chiarezza ho segnato le differenze):

fast_trunc_one, C:

int fast_trunc_one(int i) { 
    int mantissa, exponent, sign, r; 

    mantissa = (i & 0x07fffff) | 0x800000; 
    exponent = 150 - ((i >> 23) & 0xff); 
    sign = i & 0x80000000; 

    if (exponent < 0) { 
     r = mantissa << -exponent;      /* diff */ 
    } else { 
     r = mantissa >> exponent;      /* diff */ 
    } 

    return (r^-sign) + sign;       /* diff */ 
} 

fast_trunc_two, C:

int fast_trunc_two(int i) { 
    int mantissa, exponent, sign, r; 

    mantissa = (i & 0x07fffff) | 0x800000; 
    exponent = 150 - ((i >> 23) & 0xff); 
    sign = i & 0x80000000; 

    if (exponent < 0) { 
     r = (mantissa << -exponent)^-sign;    /* diff */ 
    } else { 
     r = (mantissa >> exponent)^-sign;    /* diff */ 
    } 

    return r + sign;          /* diff */ 
} 

Sembra lo stesso diritto? Bene, GCC non è d'accordo. Dopo la compilazione con gcc -O3 -S -Wall -o test.s test.c questo è l'output montaggio:

fast_trunc_one, generato:

_fast_trunc_one: 
LFB0: 
    .cfi_startproc 
    movl 4(%esp), %eax 
    movl $150, %ecx 
    movl %eax, %edx 
    andl $8388607, %edx 
    sarl $23, %eax 
    orl $8388608, %edx 
    andl $255, %eax 
    subl %eax, %ecx 
    movl %edx, %eax 
    sarl %cl, %eax 
    testl %ecx, %ecx 
    js L5 
    rep 
    ret 
    .p2align 4,,7 
L5: 
    negl %ecx 
    movl %edx, %eax 
    sall %cl, %eax 
    ret 
    .cfi_endproc 

fast_trunc_two, generato:

_fast_trunc_two: 
LFB1: 
    .cfi_startproc 
    pushl %ebx 
    .cfi_def_cfa_offset 8 
    .cfi_offset 3, -8 
    movl 8(%esp), %eax 
    movl $150, %ecx 
    movl %eax, %ebx 
    movl %eax, %edx 
    sarl $23, %ebx 
    andl $8388607, %edx 
    andl $255, %ebx 
    orl $8388608, %edx 
    andl $-2147483648, %eax 
    subl %ebx, %ecx 
    js L9 
    sarl %cl, %edx 
    movl %eax, %ecx 
    negl %ecx 
    xorl %ecx, %edx 
    addl %edx, %eax 
    popl %ebx 
    .cfi_remember_state 
    .cfi_def_cfa_offset 4 
    .cfi_restore 3 
    ret 
    .p2align 4,,7 
L9: 
    .cfi_restore_state 
    negl %ecx 
    sall %cl, %edx 
    movl %eax, %ecx 
    negl %ecx 
    xorl %ecx, %edx 
    addl %edx, %eax 
    popl %ebx 
    .cfi_restore 3 
    .cfi_def_cfa_offset 4 
    ret 
    .cfi_endproc 

Questo è un estremo differenza . Anche questo si presenta sul profilo, fast_trunc_one è circa il 30% più veloce di fast_trunc_two. Ora la mia domanda: che cosa sta causando questo?

Answer 1

Aggiornato per la sincronizzazione con modifica del PO

Con armeggiare con il codice, sono riuscito a vedere come GCC ottimizza il primo caso.

Prima di poter capire perché sono così diversi, prima dobbiamo capire come GCC ottimizza fast_trunc_one().

crediate o no, fast_trunc_one() sono ottimizzate a questo:

int fast_trunc_one(int i) { 
    int mantissa, exponent; 

    mantissa = (i & 0x07fffff) | 0x800000; 
    exponent = 150 - ((i >> 23) & 0xff); 

    if (exponent < 0) { 
     return (mantissa << -exponent);    /* diff */ 
    } else { 
     return (mantissa >> exponent);    /* diff */ 
    } 
} 

Ciò produce lo stesso assieme esatta dell'originale fast_trunc_one() - Registrazione nomi e tutto.

Si noti che non ci sono xor s nell'assieme per fast_trunc_one(). Questo è ciò che ha dato via per me.

---

In che modo?

---

Fase 1:sign = -sign

In primo luogo, diamo uno sguardo alla variabile sign. Dal sign = i & 0x80000000;, ci sono solo due possibili valori che può prendere sign:

• sign = 0
• sign = 0x80000000

Ora riconoscere che in entrambi i casi, sign == -sign.Pertanto, quando cambio il codice originale di questo:

int fast_trunc_one(int i) { 
    int mantissa, exponent, sign, r; 

    mantissa = (i & 0x07fffff) | 0x800000; 
    exponent = 150 - ((i >> 23) & 0xff); 
    sign = i & 0x80000000; 

    if (exponent < 0) { 
     r = mantissa << -exponent; 
    } else { 
     r = mantissa >> exponent; 
    } 

    return (r^sign) + sign; 
} 

Produce stesso assembly esatta dell'originale fast_trunc_one(). Ti risparmierò l'assemblaggio, ma è identico - registra i nomi e tutto il resto.

---

Fase 2: riduzione teorico: x + (y^x) = y

sign può assumere solo due valori, 0 o 0x80000000.

• Quando x = 0, quindi x + (y^x) = y quindi banale stive.
• L'aggiunta e lo xoring di 0x80000000 sono gli stessi. Capovolge il segno. Pertanto x + (y^x) = y contiene anche quando x = 0x80000000.

Pertanto, x + (y^x) riduce a y. E il codice semplifica a questo:

int fast_trunc_one(int i) { 
    int mantissa, exponent, sign, r; 

    mantissa = (i & 0x07fffff) | 0x800000; 
    exponent = 150 - ((i >> 23) & 0xff); 
    sign = i & 0x80000000; 

    if (exponent < 0) { 
     r = (mantissa << -exponent); 
    } else { 
     r = (mantissa >> exponent); 
    } 

    return r; 
} 

Ancora una volta, questo compila per la stessa identica di assemblaggio - registrazione nomi e tutti.

---

Questa versione sopra, infine, si riduce a questo:

int fast_trunc_one(int i) { 
    int mantissa, exponent; 

    mantissa = (i & 0x07fffff) | 0x800000; 
    exponent = 150 - ((i >> 23) & 0xff); 

    if (exponent < 0) { 
     return (mantissa << -exponent);    /* diff */ 
    } else { 
     return (mantissa >> exponent);    /* diff */ 
    } 
} 

che è più o meno esattamente quello che GCC genera nell'assieme.

---

Quindi perché il compilatore non ottimizza fast_trunc_two() nella stessa cosa?

La parte chiave in fast_trunc_one() è l'ottimizzazione x + (y^x) = y. In fast_trunc_two() l'espressione x + (y^x) viene suddivisa in tutto il ramo.

Sospetto che possa essere sufficiente per confondere GCC per non effettuare questa ottimizzazione. (Si dovrebbe issare il ^ -sign dal ramo e unirlo al r + sign alla fine.)

Ad esempio, questo produce lo stesso assieme come fast_trunc_one():

int fast_trunc_two(int i) { 
    int mantissa, exponent, sign, r; 

    mantissa = (i & 0x07fffff) | 0x800000; 
    exponent = 150 - ((i >> 23) & 0xff); 
    sign = i & 0x80000000; 

    if (exponent < 0) { 
     r = ((mantissa << -exponent)^-sign) + sign;    /* diff */ 
    } else { 
     r = ((mantissa >> exponent)^-sign) + sign;    /* diff */ 
    } 

    return r;          /* diff */ 
} 

Answer 2

Questa è la natura compilatori. Supponendo che prenderanno il percorso più veloce o migliore, è abbastanza falso. Chiunque sottintenda che tu non debba fare nulla per il tuo codice per ottimizzarlo perché i "compilatori moderni" riempiono lo spazio vuoto, fanno il lavoro migliore, fanno il codice più veloce, ecc. In realtà ho visto gcc peggiorare da 3.x a 4. x sul braccio almeno. 4.x potrebbe aver raggiunto il 3.x da questo punto, ma presto ha prodotto un codice più lento. Con la pratica puoi imparare come scrivere il tuo codice in modo che il compilatore non debba lavorare così duramente e di conseguenza produrre risultati più coerenti e attesi.

Il bug qui è le vostre aspettative su ciò che verrà prodotto, non su ciò che è stato effettivamente prodotto. Se vuoi che il compilatore generi lo stesso output, alimentalo con lo stesso input.Non è matematicamente uguale, non è lo stesso, ma in realtà è lo stesso, non ci sono percorsi diversi, nessuna condivisione o distribuzione di operazioni da una versione all'altra. Questo è un buon esercizio per capire come scrivere il codice e vedere cosa fanno i compilatori con esso. Non commettere l'errore di presupporre che poiché una versione di gcc per un target del processore un giorno ha prodotto un determinato risultato che è una regola per tutti i compilatori e tutto il codice. Devi usare molti compilatori e molti obiettivi per avere un'idea di cosa sta succedendo.

gcc è piuttosto brutto, vi invito a guardare dietro le quinte, a guardare il coraggio di gcc, provare ad aggiungere un obiettivo o modificare qualcosa da soli. E 'a mala pena tenuto insieme da nastro adesivo e cavo di sicurezza. Una riga aggiuntiva di codice aggiunta o rimossa in punti critici e si sgretola. Il fatto che abbia prodotto codice utilizzabile è qualcosa di cui essere contenti, invece di preoccuparsi del perché non ha soddisfatto altre aspettative.

hai visto quali diverse versioni di gcc producono? 3.xe 4.x in particolare 4.5 vs 4.6 vs 4.7, ecc.? e per diversi processori di destinazione, x86, arm, mips, ecc o diversi tipi di x86 se questo è il compilatore nativo che usi, 32 bit vs 64 bit, ecc.? E poi llvm (clang) per obiettivi diversi?

Mystical ha svolto un lavoro eccellente nel processo di pensiero necessario per risolvere il problema dell'analisi/ottimizzazione del codice, aspettandosi che un compilatore possa venire a conoscenza di ciò che è, beh, non previsto da alcun "compilatore moderno".

Senza entrare nelle proprietà di matematica, il codice di questa forma

if (exponent < 0) { 
    r = mantissa << -exponent;      /* diff */ 
} else { 
    r = mantissa >> exponent;      /* diff */ 
} 
return (r^-sign) + sign;       /* diff */ 

sta per portare al compilatore di A: la sua attuazione in quella forma, effettuare l'if-then-else poi convergere su codice comune per finire e tornare. oppure B: salva un ramo poiché questa è la fine della coda della funzione. Inoltre non preoccuparti di usare o salvare r.

if (exponent < 0) { 
    return((mantissa << -exponent)^-sign)+sign; 
} else { 
    return((mantissa << -exponent)^-sign)+sign; 
} 

Poi si può entrare come Mistico ha sottolineato la variabile segno scompare tutti insieme per il codice come scritto. Non mi aspetterei che il compilatore vedesse la variabile del segno andare via, quindi avresti dovuto farlo tu stesso e non costringere il compilatore a cercare di capirlo.

Questa è un'opportunità perfetta per scavare nel codice sorgente di gcc. Sembra che tu abbia trovato un caso in cui l'ottimizzatore ha visto una cosa in un caso e un'altra in un altro caso. Quindi fai il passo successivo e vedi se non riesci a ottenere gcc per vedere quel caso. Ogni ottimizzazione è lì perché alcuni individui o gruppi hanno riconosciuto l'ottimizzazione e intenzionalmente l'hanno messa lì. Per questa ottimizzazione essere lì e lavorare ogni volta che qualcuno deve metterlo lì (e poi testarlo, e poi mantenerlo nel futuro).

Sicuramente non dare per scontato che meno codice è più veloce e più codice è più lento, è molto facile da creare e trovare esempi di ciò che non è vero. Potrebbe accadere più spesso che meno codice sia più veloce di più codice. Come ho dimostrato dall'inizio, è possibile creare più codice per salvare la ramificazione in quel caso o il ciclo, ecc. E avere il risultato netto un codice più veloce.

La linea di fondo si alimenta con una fonte diversa dal compilatore e si aspettava gli stessi risultati. Il problema non è l'output del compilatore ma le aspettative dell'utente. È abbastanza facile dimostrare per un particolare compilatore e processore, l'aggiunta di una riga di codice che rende l'intera funzione notevolmente più lenta. Ad esempio perché cambia a = b + 2; a a = b + c + 2; causa _fill_in_the_blank_compiler_name_ genera un codice radicalmente diverso e più lento? Ovviamente la risposta è che il compilatore ha ricevuto un codice diverso sull'input, quindi è perfettamente valido per il compilatore generare output diversi.(ancora meglio quando si scambiano due righe di codice non correlate e l'output cambia radicalmente) Non esiste una relazione attesa tra la complessità e la dimensione dell'input per la complessità e la dimensione dell'output. Feed qualcosa di simile in clang:

for(ra=0;ra<20;ra++) dummy(ra); 

Ha prodotto da qualche parte tra 60-100 linee di assemblatore. Ha srotolato il ciclo. Non ho contato le righe, se ci pensate, deve aggiungere, copiare il risultato nell'input alla chiamata di funzione, effettuare la chiamata di funzione, minimo tre operazioni. quindi a seconda dell'obiettivo che è probabilmente 60 istruzioni almeno, 80 se quattro per ciclo, 100 se cinque per ciclo, ecc.

Answer 3

Mysticial ha già dato una grande spiegazione, ma ho pensato di aggiungere, FWIW, che non c'è davvero nulla di fondamentale sul perché un compilatore farebbe l'ottimizzazione per l'uno e non l'altro.

clang compilatore LLVM, per esempio, fornisce lo stesso codice per entrambe le funzioni (eccetto il nome della funzione), dando:

_fast_trunc_two:      ## @fast_trunc_one 
     movl %edi, %edx 
     andl $-2147483648, %edx  ## imm = 0xFFFFFFFF80000000 
     movl %edi, %esi 
     andl $8388607, %esi   ## imm = 0x7FFFFF 
     orl  $8388608, %esi   ## imm = 0x800000 
     shrl $23, %edi 
     movzbl %dil, %eax 
     movl $150, %ecx 
     subl %eax, %ecx 
     js  LBB0_1 
     shrl %cl, %esi 
     jmp  LBB0_3 
LBB0_1:         ## %if.then 
     negl %ecx 
     shll %cl, %esi 
LBB0_3:         ## %if.end 
     movl %edx, %eax 
     negl %eax 
     xorl %esi, %eax 
     addl %edx, %eax 
     ret 

Questo codice non è breve come la prima versione gcc dall'OP , ma non tanto quanto il secondo.

codice da un altro compilatore (che non farò il nome), la compilazione per x86_64, produce questo per entrambe le funzioni:

fast_trunc_one: 
     movl  %edi, %ecx   
     shrl  $23, %ecx   
     movl  %edi, %eax   
     movzbl %cl, %edx   
     andl  $8388607, %eax  
     negl  %edx    
     orl  $8388608, %eax  
     addl  $150, %edx   
     movl  %eax, %esi   
     movl  %edx, %ecx   
     andl  $-2147483648, %edi 
     negl  %ecx    
     movl  %edi, %r8d   
     shll  %cl, %esi   
     negl  %r8d    
     movl  %edx, %ecx   
     shrl  %cl, %eax   
     testl  %edx, %edx   
     cmovl  %esi, %eax   
     xorl  %r8d, %eax   
     addl  %edi, %eax   
     ret       

che è affascinante in quanto calcola entrambi i lati del if e poi utilizza un mossa condizionale alla fine per scegliere quella giusta.

L'Open64 compilatore genera il seguente:

fast_trunc_one: 
    movl %edi,%r9d     
    sarl $23,%r9d     
    movzbl %r9b,%r9d     
    addl $-150,%r9d     
    movl %edi,%eax     
    movl %r9d,%r8d     
    andl $8388607,%eax    
    negl %r8d      
    orl $8388608,%eax    
    testl %r8d,%r8d     
    jl .LBB2_fast_trunc_one   
    movl %r8d,%ecx     
    movl %eax,%edx     
    sarl %cl,%edx     
.Lt_0_1538: 
    andl $-2147483648,%edi   
    movl %edi,%eax     
    negl %eax      
    xorl %edx,%eax     
    addl %edi,%eax     
    ret        
    .p2align 5,,31 
.LBB2_fast_trunc_one: 
    movl %r9d,%ecx     
    movl %eax,%edx     
    shll %cl,%edx     
    jmp .Lt_0_1538     

e simili, ma non identici, il codice per fast_trunc_two.

In ogni caso, quando si tratta di ottimizzazione, è una lotteria - è quello che è ... Non è sempre facile sapere perché il codice viene compilato in un modo particolare.