ramo statico previsione/ottimizzazione GCC

Question

Si consideri il seguente programma C:

void bar(); 
void baz(); 

void foo(int a) { 
    if (a) { 
     bar(); 
    } 
    else { 
     baz(); 
    } 
} 

Sul mio computer x86-64-based, le istruzioni generate da GCC con il livello di ottimizzazione -O1 dà:

0: sub $0x8,%rsp 
4: test %edi,%edi 
6: je  14 <foo+0x14> 
8: mov $0x0,%eax 
d: callq 12 <foo+0x12> # relocation to bar 
12: jmp 1e <foo+0x1e> 
14: mov $0x0,%eax 
19: callq 1e <foo+0x1e> # relocation to baz 
1e: add $0x8,%rsp 
22: retq 

che, aggiungendo il parametro di ottimizzazione -freorder blocchi (incluso nel -O2) trasforma il codice in:

0: sub $0x8,%rsp 
4: test %edi,%edi 
6: jne 17 <foo+0x17> 
8: mov $0x0,%eax 
d: callq 12 <foo+0x12> # relocation to baz 
12: add $0x8,%rsp 
16: retq 
17: mov $0x0,%eax 
1c: callq 21 <foo+0x21> # relocation to bar 
21: add $0x8,%rsp 
25: retq 

ciò che è principalmente un cambiamento da salta uguale a a salto non uguale a. So che fino al Pentium 4, la previsione statica delle diramazioni su un ramo condizionale in avanti non è stata presa dal processore (sembra che la previsione statica sia diventata casuale su altri processori Intel), quindi immagino che questa ottimizzazione si occupi di questo.

Supponendo che e riferendosi alla versione JNE ottimizzato, vorrebbe dire che il blocco altro è infatti considerato più probabile eseguito rispetto alla se blocco nel flusso del programma.

Ma cosa significa esattamente? Poiché non v'è alcuna ipotesi sul un valore nella funzione foo dal compilatore, tale probabilità si basa solo su scritti del programmatore (che potrebbero in realtà hanno usato if (!a) invece di if (a) e chiamate di funzione invertiti).

Ciò significa che dovrebbe essere considerata una buona pratica per il trattamento di se blocchi condizionali come casi eccezionali (e non il normale flusso di esecuzione)?

Cioè:

if (!cond) { 
    // exceptional code 
} 
else { 
    // normal continuation 
} 

invece di:

if (cond) { 
    // normal continuation 
} 
else { 
    // exceptional code 
} 

(ovviamente, si potrebbe preferire usando istruzione return all'interno del blocco rilevante per limitare le dimensioni indentazione).

Answer 1

Una volta avevo una quantità significativa di azioni di ottimizzazione delle prestazioni su ARM (7,9). Era semplice C, compilatore abbastanza stupido (SDT AFAIR). Uno dei modi per risparmiare risorse della CPU era analizzare le filiali if e riscrivere la condizione if in modo che il flusso normale non interrompesse la sequenza di istruzioni lineari. Ciò ha avuto un effetto positivo sia a causa del blocco della previsione della CPU un utilizzo più efficiente e dell'uso più efficiente della cache del segmento di codice.

Penso che qui vediamo un'ottimizzazione molto vicina. Nel primo frammento di codice entrambi i rami portano alla rottura della sequenza normale (linea con lavel 6 per un ramo e per un altro). Nel secondo frammento vengono ordinate le istruzioni di un ramo fino a retq e un'altra sequenza di diramazioni ha un salto singolo (non peggiore di quanto non fosse nel primo frammento). Si prega di prestare attenzione alle 2 istruzioni retq.

Quindi, come posso vedere questo non è il problema di je o jne ma piuttosto questione di blocchi di riordino in modo da rami sono lineari sequenza di istruzioni con uno di loro è entrato senza alcun potere blocco jump e pieno previsione salvato.

Riguardo a "perché GCC preferisce un ramo a un altro" ... Vedo nella documentazione che questo può essere il risultato di una previsione di ramo statico (basata sulle chiamate all'interno dell'unità di traduzione?). Ad ogni modo consiglierei di giocare con __builtin_expect per avere una risposta più dettagliata.