Quali sono alcuni suggerimenti per ottimizzare il codice assembly generato da un compilatore?

Question

Attualmente sto scrivendo uno compiler e sembra che ci siano alcuni problemi nel portarlo al codice di output che viene eseguito in un intervallo di tempo decente.

Una breve panoramica del compilatore:

7 Elementi è un compilatore che mira a compilare il codice 7 Elementi direttamente in codice macchina per il target architettura/piattaforma. Attualmente 7Basic genera un assembly x86 dato un file sorgente.

Il problema è che il codice assembly generato dal compilatore è lento e inefficiente.

Ad esempio, il codice this (che si compila fino al codice di assemblaggio this) impiega circa 80,47 volte più a lungo rispetto a the equivalent C code.

Parte del problema è che il compilatore genera codice come il seguente:

push eax 
push 5000000 
pop ebx 
pop eax 

Anziché il più logico:

mov ebx,5000000 

... che compie la stessa cosa.

La mia domanda è: quali sono alcune tecniche per evitare questo tipo di problema? Il parser utilizza fondamentalmente la ricorsione per analizzare le espressioni, quindi il codice generato riflette questo.

Answer 1

Una tecnica è denominata peephole optimisation. Ciò richiede un approccio iterativo per la pulizia del codice assembly. In sostanza si scansiona il codice assembly, osservando solo due o tre istruzioni alla volta e si vede se è possibile ridurle in qualcosa di più semplice. Ad esempio,

push eax  ; 1 
push 5000000 ; 2 
pop ebx   ; 3 
pop eax   ; 4 

Il primo passo sarebbe guardare le linee 2 e 3, e sostituirlo con:

push eax  ; 1 
mov ebx,5000000 ; 2a 
pop eax   ; 4 

In secondo luogo, si potrebbe considerare di 1 e 4, e se eax non viene toccata nel istruzioni mezzo, rimuovere entrambi, lasciando ciò che si vuole:

mov ebx,5000000 ; 2a 

Answer 2

si potrebbe prendere in considerazione la generazione di codice C, piuttosto che di montaggio e poi lasciare che un compilatore C (ad esempio, gcc) gestire il codice g enerazione per te. Non ha senso provare a reinventare la ruota.

Answer 3

Ci sono diversi motivi per cui un particolare generatore di codice può emettere la sequenza di istruzioni che si elenca. Il più probabile è che il generatore di codice che stai usando non stia tentando molto di emettere un codice ottimale.

Questo schema di codice emesso mi suggerisce che il generatore di codice non sa che l'x86 ha istruzioni "mov immediate" che incorporano direttamente il valore costante nel flusso di istruzioni. La codifica x86 per opcode con valori immediati può essere un po 'complicata (byte R/M di lunghezza variabile), ma è già necessaria se si desidera utilizzare molte delle istruzioni x86.

Questo codice emesso suggerisce anche che il generatore di codice non sappia che EAX non viene modificato dalle istruzioni EBX. Questo sembra che il codegen sia basato su template piuttosto che su una logica discreta.

Questo tipo di codegen si verifica quando la rappresentazione intermedia interna delle operazioni del compilatore non è sufficientemente dettagliata per rappresentare tutti gli aspetti dell'architettura di destinazione. Ciò è particolarmente vero se l'architettura del generatore di codice è stata originariamente progettata per un set di istruzioni RISC ma è stata riutilizzata per emettere le istruzioni x86. L'architettura RISC tende ad avere pochissime e molto semplici operazioni di caricamento, memorizzazione e funzionamento di reg/reg, mentre il set di istruzioni x86 si è evoluto organicamente per decenni per includere un'ampia varietà di opcode che operano direttamente sulla memoria, costanti incorporate nelle istruzioni, e un intero casino di altre cose. Se la rappresentazione intermedia del compilatore (graph di espressione) è cablata per RISC, sarà difficile farla ingurgitare l'ampia varietà e sottigliezze di x86.

Answer 4

Sto prendendo un corso di compilatore al momento. Ho fatto grandi progressi nell'implementare codice efficiente, ma dovresti esaminare il libro del drago. È un rito di passaggio. Dovresti dare un'occhiata al codice del libro di Jeremy Bennett, Introduzione alle tecniche di compilazione: un primo corso con ANSI C, LEX e YACC. Il libro in sé è molto difficile da trovare, ma è possibile scaricare il codice sorgente del compilatore libero da

http://www.jeremybennett.com/publications/download.html

Il file generatore di codice (cg.c) ha alcune funzioni per la generazione di codice abbastanza ottimizzato. La lingua di destinazione non è i386, ma dovresti considerare come descrive i registri e tiene traccia di dove sono memorizzate le voci della tabella dei simboli. Il suo gruppo di uscita potrebbe essere ulteriormente ottimizzato, ma fornisce un'ottima base per la produzione di codice che potrebbe competere con l'output di gcc -S per alcuni aspetti.

Un'ottimizzazione generale sarebbe quella di sottrarre il puntatore dello stack allo spazio di riserva per tutte le variabili locali e temporanee all'immissione di una funzione. Quindi basta fare riferimento agli offset invece di spingere/scoppiare continuamente.

Ad esempio, se il codice intermedio è un elenco di quadrupli, è sufficiente eseguirlo tramite iteratore per ciascuna funzione e tenere traccia dell'offset massimo. Quindi emettere la linea per sottrarre la quantità di spazio sulla pila. Ciò elimina la necessità di spingere tante variabili avanti e indietro. Per rimuovere la necessità di visualizzarli, puoi semplicemente spostare il loro valore dal loro offset in pila in un registro. Ciò migliorerà significativamente le prestazioni.

Answer 5

Le ottimizzazioni degli spioncini aiuteranno, ma un problema ovvio è che il compilatore non esegue l'allocazione dei registri!

http://en.wikipedia.org/wiki/Register_allocation

Se si desidera ottenere gravi livelli di prestazione, si sta facendo di dover guardare in quella. Può essere fatto in un solo passaggio se lo fai avidamente "al volo".