In particolare cosa fa un compilatore per ottimizzare in modo aggressivo il codice generato?

Ho letto le funzionalità di vari compilatori e mi sono imbattuto nel termine “ottimizzazione aggressiva” che molti compilatori hanno dichiarato di eseguire. LLVM, ad esempio, cita le seguenti funzioni di ottimizzazione in fase di compilazione:

  • Memoria / puntatore specifico
  • Loop trasforma
  • Flusso di dati
  • Aritmetica
  • Eliminazione del codice morto
  • inlining

Cosa significa in particolare? Supponiamo che tu abbia il seguente frammento di codice, come potresti ottimizzare il codice byte generato per essere eseguito più velocemente di quello generato dal compilatore? Sono particolarmente interessato all’ottimizzazione del bytecode di runtime a JIT come C #, Java e Flash. Questo è difficile perché il JIT supporta solo un sottoinsieme degli opcode che il processore di solito fa, il che limita la quantità di ottimizzazione che puoi fare. Tuttavia, sono interessato a vedere cosa è ansible ed esattamente quali trasformazioni potrebbero spingere i limiti della VM.

Blocco di codice fittizio:

for (i = 0; i > 16) - 10; }else{ out = ((in << 5) / 2) * 50 + 10; } dataOut[i] = out; } 

Approssimativo pseudo-codice generato dal compilatore, per una VM JIT basata su stack come Flash Player: (perdonami per eventuali errori, questo è interamente scritto a mano!)

 // i = 0 label: "forInit" push 0 writeTo "i" // while i > 16) - 10; push "in" push 2 divide push 16 rightshift push 10 minus writeTo "out" goto "ifEnd" // else label: ifPart2 // out = ((in << 5) / 2) * 50 + 10; push "in" push 5 leftshift push 2 divide push 50 multiply push 10 add writeTo "out" // dataOut[i] = out; label: ifEnd push "out" push "i" push "dataOut" writeProp // i++ push "i" increment writeTo "i" // while i < 100 goto "forStart" label: "forEnd" 

Ecco due semplici ottimizzazioni che un compilatore potrebbe fare:

 out = ((i / 2) >> 16) - 10; 

può essere ridotto a

 out = (i >> 17) - 10; 

e

 out = ((i << 5) / 2) * 50 + 10; 

può essere ridotto a

 out = (i << 4) * 50 + 10; 

Per rispondere alla tua domanda "come potresti ottimizzare il codice byte generato per essere eseguito più velocemente di quello generato dal compilatore?" Ecco un'altra versione del bytecode che ha alcune ottimizzazioni.

 // i = 0 label: "forInit" push 0 writeTo "i" // while i < 100 label: "forStart" push "i" push 100 jumpIfMoreThan "forEnd" // in = dataIn[i]; push "i" push "dataIn" readProp saveTo "in" // if ((in % 5) == 0) push "in" push 5 mod push 0 jumpIfNotEquals "ifPart2" label: ifPart1 // optimization: remove unnecessary /2 // out = ((in / 2) >> 16) - 10; push "in" push 17 rightshift push 10 minus // optimization: don't need out var since value on stack // dataOut[i] = out; push "i" push "dataOut" writeProp // optimization: avoid branch to common loop end // i++ push "i" increment writeTo "i" goto "forStart" // else label: ifPart2 // optimization: remove unnecessary /2 // out = ((in << 5) / 2) * 50 + 10; push "in" push 4 leftshift push 50 multiply push 10 add // optimization: don't need out var since value on stack // dataOut[i] = out; push "i" push "dataOut" writeProp // optimization: avoid branch to common loop end // i++ push "i" increment writeTo "i" goto "forStart" label: "forEnd" 

Ho anche lavorato su questo, l’elenco completo delle trasformazioni che LLVM esegue , organizzato sotto le intestazioni:

  • Rimozione del codice morto
    • Eliminazione di codici morti aggressivi
    • Eliminazione del codice morto
    • Eliminazione di argomenti morti
    • Eliminazione del tipo morto
    • Eliminazione delle istruzioni morte
    • Dead Store Elimination
    • Dead Global Elimination
    • Elimina i loop morti
  • Rimozione dei dati indesiderati
    • Rimuovi tutti i simboli da un modulo
    • Elimina le informazioni di debug per i simboli non utilizzati
    • Prototipi di funzioni inutilizzate della striscia
    • Elimina tutti gli intrinsec di llvm.dbg.declare
    • Striscia tutti i simboli, eccetto i simboli dbg, da un modulo
    • Unisci duplicati di costanti globali
    • Rimuovi le informazioni di gestione delle eccezioni non utilizzate
  • Funzioni di allineamento
    • Unisci funzioni
    • Inliner parziale
    • Integrazione delle funzioni / Inlining
  • Ottimizzazione del loop
    • Passo modulo SSA chiuso a loop
    • Loop Invariant Code Motion
    • Estrai loop in nuove funzioni
    • Estrai al massimo un loop in una nuova funzione
    • Loop Forza Riduzione
    • Ruota i cicli
    • Canonicalizzare i loop naturali
    • Srotolare i loop
    • Loop non attivi
  • Varie
    • Promuovere gli argomenti ‘di riferimento’ con gli scalari
    • Combina le istruzioni per formare istruzioni vettoriali all’interno dei blocchi di base
    • Posizionamento del blocco di base guidato da profilo
    • Rompere i bordi critici in CFG
    • Ottimizza per la generazione del codice
    • Semplice propagazione costante
    • Deduce gli attributi della funzione
    • Global Variable Optimizer
    • Numerazione dei valori globali
    • Canonicalizza le variabili di induzione
    • Inserire la strumentazione per il profilo del bordo
    • Inserire la strumentazione ottimale per il profilo del bordo
    • Combina istruzioni ridondanti
    • Internalize Global Symbols
    • Propagazione costante interprocedurale
    • Propagazione costante condizionale spregevole interprocedurale
    • Salta la filettatura
    • Bassa intrinseca atomica alla forma non atomica
    • Abbassare invocare e rilassarsi, per generatori di codice senza sforzo
    • Lower SwitchInst alle filiali
    • Promuovi la memoria da registrare
    • MemCpy Optimization
    • Unifica i nodes di uscita della funzione
    • Riassociare espressioni
    • Diminuisci tutti i valori per impilare gli slot
    • Sostituzione scalare degli aggregati (DT)
    • Propagazione costante condizionale sparsa
    • Semplifica le chiamate alle librerie note
    • Semplificare il CFG
    • Codice che affonda
    • Promuovi argomenti sret a più valori ret
    • Eliminazione chiamata di coda
    • Duplicazione della coda

Sebbene questo non risponda alla tua domanda, ho trovato le seguenti trasformazioni che un compilatore C ++ esegue per ottimizzare il codice macchina generato:

  • Riduzione dell’intensità — le variabili di iterazione utilizzate come indici di dati vengono incrementate ad una velocità corrispondente alla dimensione dell’unità di dati
  • Paremeters nascosti — una funzione che restituisce una struttura effettivamente la scrive in un’area puntata da un parametro nascosto
  • Divisione intera — alcuni fornaci possono essere utilizzati per valutare la divisione intera in modo più efficiente nel caso di un divisore noto
  • Condizioni di galleggiamento — una condizione in virgola mobile viene trasformata in una sequenza complessa di istruzioni che impostano e interrogano lo stato di virgola mobile
  • Matematica complessa — una moltiplicazione o divisione complessa viene trasformata in una chiamata di libreria
  • Routine native : un’operazione memcpy (), memset (), strcmp () o strlen () viene trasformata in rep mov, rep sto, rep zcmp o rep zscas
  • Cortocircuito — una condizione complessa viene valutata in un albero di blocchi di base
  • Ambiguità sindacale — le informazioni vengono perse riguardo a quale membro di un’unione è destinato
  • Copia frammentazione — grandi valori double o aggregati vengono copiati parola per parola
  • Prova frammentazione — una condizione su un valore intero lungo è composta da test separati sulle singole parole di quel valore
  • Cambia frammentazione — un’istruzione switch viene sostituita da un nido di condizioni su un valore
  • Loop Header Copy — un loop è aumentato con una condizione che decide se inserire il ciclo
  • Loop Unrolling — un ciclo viene sostituito da copie replicate del corpo del loop
  • Funzione Inline — una chiamata di funzione viene sostituita da una copia del corpo della funzione