Cosa può fare un compilatore con le informazioni di diramazione?

Question

Su un Pentium moderno non è più possibile dare suggerimenti di ramificazione al processore che sembra. Supponendo che un compilatore di profili come gcc con ottimizzazione guidata dal profilo ottenga informazioni sul probabile comportamento di ramificazione, cosa può fare per produrre codice che verrà eseguito più rapidamente?

L'unica opzione che conosco è spostare rami improbabili alla fine di una funzione. C'è niente altro?

Aggiornamento .

http://download.intel.com/products/processor/manual/325462.pdf del volume 2 bis, sezione 2.1.1 dice

"prefissi Branch suggerimento (2EH, 3EH) consentono a un programma per dare un suggerimento per il processore sul percorso di codice più probabile per un ramo. Usare questi prefissi solo con istruzioni condizionali di ramo (Jcc). Altro uso di prefissi di suggerimento di ramo e/o altri codici opzionali indefiniti con le istruzioni di Intel 64 o IA-32 è riservato, tale uso può causare un comportamento imprevedibile di ".

Non so se questi hanno comunque alcun effetto.

D'altra parte sezione 3.4.1. . Di http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf dice

" compilatori generano codice che migliora l'efficienza di predizione dei salti in processori Intel Intel C++ compilatore esegue ciò:

• codice tenuta e dati su pagine separate
• utilizzando condizionale sposta le istruzioni per eliminare le diramazioni
• codice di generazione coerente con l'algoritmo di predizione di ramo statico
• inlining ove appropriato
• srotolando se il numero di iterazioni è prevedibile

Con ottimizzazione del profilo-guida, il compilatore può porre dei blocchi di base per eliminare rami per la maggior percorsi eseguite frequentemente di una funzione o almeno migliorarne la prevedibilità. La previsione della filiale deve essere non essere un problema al livello sorgente. Per ulteriori informazioni, consultare la documentazione del compilatore Intel C++. "

http://cache-www.intel.com/cd/00/00/40/60/406096_406096.pdf dice in 'Miglioramenti di prestazioni con PGO'

" PGO funziona meglio per il codice con molti rami eseguiti spesso difficili da prevedere in fase di compilazione. Un esempio è il codice con controllo degli errori intensivo in cui le condizioni di errore sono false per la maggior parte delle volte . Il codice di errorhandling (a freddo) eseguito raramente può essere riposizionato in modo che il ramo venga raramente previsto in modo errato. Minimizzare codice freddo intercalati nel codice eseguito frequentemente (caldo) migliora cache istruzioni comportamento ".

Answer 1

Se è chiaro che un ciclo è raramente inserito, o che normalmente itera pochissime volte, quindi il compilatore potrebbe evitarne lo svolgimento della loop, poiché così facendo si può aggiungere molta complessità dannosa per gestire le condizioni dei bordi (iterazioni di numero dispari, ecc.).In questi casi, la vettorizzazione, in particolare, dovrebbe essere evitata.

Il compilatore può riorganizzare i test annidati, in modo che quello che più frequentemente risulta in una scorciatoia possa essere utilizzato per evitare di eseguire un test su qualcosa con una velocità di trasmissione del 50%.

L'allocazione del registro può essere ottimizzata per evitare che si verifichi una perdita di registro di blocco di blocco raramente utilizzata nel caso comune.

Questi sono solo alcuni esempi. Sono sicuro che ce ne sono altri a cui non ho pensato.

Answer 2

In cima alla mia testa, hai due opzioni.

Opzione 1: informa il compilatore dei suggerimenti e lascia che il compilatore organizzi il codice in modo appropriato. Ad esempio, GCC supporta i seguenti ...

__builtin_expect((long)!!(x), 1L) /* GNU C to indicate that <x> will likely be TRUE */ 
__builtin_expect((long)!!(x), 0L) /* GNU C to indicate that <x> will likely be FALSE */ 

Se li mettete in forma macro come ...

#if <some condition to indicate support> 
    #define LIKELY(x) __builtin_expect((long)!!(x), 1L) 
    #define UNLIKELY(x) __builtin_expect((long)!!(x), 0L) 
#else 
    #define LIKELY(x) (x) 
    #define UNLIKELY(x) (x) 
#endif 

... ora è possibile usarli come ...

if (LIKELY (x != 0)) { 
    /* DO SOMETHING */ 
} else { 
    /* DO SOMETHING ELSE */ 
} 

Questo lascia libero al compilatore di organizzare i rami in base agli algoritmi di previsione dei rami statici e/o se il processore e il compilatore lo supportano, per utilizzare le istruzioni che indicano quale ramo è più probabile che venga prelevato.

Opzione n. 2: utilizzare la matematica per evitare diramazioni.

if (a < b) 
    y = C; 
else 
    y = D; 

Questo potrebbe essere riscritto come ...

x = -(a < b); /* x = -1 if a < b, x = 0 if a >= b */ 
x &= (C - D); /* x = C - D if a < b, x = 0 if a >= b */ 
x += D;   /* x = C if a < b, x = D if a >= b */ 

Spero che questo aiuti.

Answer 3

È in grado di eseguire la ricaduta (ovvero il caso in cui un ramo non viene utilizzato) il percorso più utilizzato. Questo ha due grandi effetti:

1. solo 1 ramo può essere preso per ciclo di clock, o su alcuni processori, anche per 2 orologi, quindi se ci sono altri rami (di solito ci sono, più il codice che conta è in un ciclo), un ramo preso è una cattiva notizia, un ramo non preso meno.
2. quando il predittore di ramo è errato, il codice che deve eseguire è più probabile che si trovi nella cache del codice (o nella cache di μop, dove applicabile). Se non lo fosse, sarebbe stato un doppio colpo di testa riavviare la pipeline e in attesa di un errore di cache. Questo è meno di un problema nella maggior parte dei loop, poiché è probabile che entrambi i lati del ramo si trovino nella cache, ma entrano in gioco in grandi loop e altri codici.

Può anche decidere se effettuare una conversione se basata su dati migliori rispetto a un'ipotesi euristica. Se le conversioni potrebbero sembrare "sempre una buona idea", ma non lo sono, sono solo "spesso una buona idea". Se il ramo nell'implementazione della ramificazione è molto ben previsto, il codice convertito in se può essere più lento.

Answer 4

ci sono due possibili fonti per le informazioni desiderate:

1. C'è Intel 64 e manuale (3 volumi) IA-32 Architetture dello sviluppatore di software.Questo è un enorme lavoro che si è evoluto per decenni. È il miglior riferimento che conosca su molti argomenti, compreso il punto di virgola mobile. In questo caso, si desidera controllare il volume 2, il riferimento alle istruzioni.
2. C'è il Manuale di riferimento per l'ottimizzazione dell'architettura Intel 64 e IA-32. Questo ti dirà in termini brevi cosa aspettarsi da ogni microarchitettura.

Ora, non so cosa intendi con un processore "Pentium moderno", questo è il 2013, giusto? Non ci sono più Pentium ...

Il set di istruzioni supporta il dire al processore se si prevede che il ramo venga preso o non preso da un prefisso alle istruzioni di ramo condizionale (come JC, JZ, ecc.) . Vedere il volume 2A di (1), sezione 2.1.1 (della versione I) Prefissi delle istruzioni. Vi sono i prefissi 2E e 3E per non essere presi e presi rispettivamente.

Sul fatto che questi prefissi abbiano effettivamente alcun effetto, se possiamo ottenere quell'informazione, sarà sul Manuale di riferimento di ottimizzazione, la sezione per la microarchitettura desiderata (e sono sicuro che non sarà il Pentium) .

Oltre a utilizzare quelli, c'è una sezione intera sul manuale di riferimento di ottimizzazione su tale argomento, che è sezione 3.4.1 (della versione che ho).

Non ha senso riprodurlo qui, dal momento che è possibile scaricare il manuale gratuitamente. In breve:

• Eliminare i rami utilizzando istruzioni condizionali (cmov, SETcc),
• Consideriamo l'algoritmo di predizione statica (3.4.1.3),
• Inlining
• Loop srotolando

Inoltre, alcuni compilatori, GCC, ad esempio, anche quando CMOV non è possibile, spesso eseguono l'aritmetica bit a bit per selezionare una delle due cose distinte calcolate, evitando così i rami. Lo fa particolarmente con le istruzioni SSE durante la vettorizzazione dei loop.

Fondamentalmente, le condizioni statiche sono:

• rami Incondizionate sono previsti per essere prese (... tipo di expectable ...)
• rami indiretti si prevede di non adottare (a causa di un dati dipendenza)
• condizionali all'indietro sono previsti da prendere (buono per loop)
• Forward condizionali sono predetti da non prendere

Probabilmente vorrai leggere l'intera sezione 3.4.1.