Lo sviluppo di un compilatore è un compito molto complesso. Fortunatamente, con l'avvento di progetti come LLVM, risolvere questo problema è diventato molto più semplice, permettendo anche a un singolo programmatore di creare un nuovo linguaggio che può competere in termini di prestazioni con C. Lavorare con LLVM è complicato dal fatto che questo sistema è rappresentato da un'enorme quantità di codice fornito con scarse documentazioni. Per cercare di mitigare questo problema, l'autore del materiale, il cui testo stiamo pubblicando oggi, intende mostrare esempi di codice scritti in Go e illustrare come vengono tradotti prima in , e poi in LLVM IR utilizzando il compilatore . Il codice Go SSA e LLVM IR è stato leggermente modificato, rimuovendo ciò che non era pertinente alle spiegazioni fornite, al fine di rendere tali spiegazioni più comprensibili.
Primo esempio
La prima funzione che intendo analizzare qui consiste in un semplice meccanismo per sommare numeri:
func myAdd(a, b int) int{
return a + b
}Questa funzione è molto semplice e, probabilmente, non esiste nulla di più semplice. Viene tradotta nel seguente codice Go SSA:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Con questa rappresentazione della funzione, i suggerimenti sui tipi di dati sono posizionati a destra; nella maggior parte dei casi, si possono ignorare.
Questo piccolo esempio permette già di vedere la sostanza di uno degli aspetti del SSA. In particolare, quando il codice viene trasformato nella forma SSA, ogni espressione è scomposta nelle sue parti più elementari. Nel nostro caso, il comando return a + b, di fatto, rappresenta due operazioni: sommare due numeri e restituire il risultato.
Inoltre, qui possiamo vedere anche i blocchi di base del programma; in questo codice c'è solo un blocco: il blocco di ingresso (entry block). Ne parleremo più in dettaglio più avanti.
Il codice Go SSA si trasforma facilmente in LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
} Si può notare che, sebbene qui vengano utilizzate altre costruzioni sintattiche, la struttura della funzione, in gran parte, è rimasta invariata. Il codice LLVM IR è leggermente più complesso del codice Go SSA, somigliando al C. Qui, nell'annuncio della funzione, viene prima descritto il tipo di dato restituito, mentre il tipo dell'argomento è indicato prima del nome dell'argomento. Inoltre, per semplificare il parsing dell'IR, un simbolo precede i nomi delle entità globali @, mentre un simbolo precede i nomi locali % (anche la funzione è considerata un'entità globale).
Una delle caratteristiche di questo codice a cui prestare attenzione è che la decisione sulla rappresentazione del tipo Go -int, che può essere rappresentato con un valore a 32 o 64 bit, a seconda del compilatore e dell'obiettivo della compilazione, viene presa durante la creazione del codice LLVM IR. Questa è una delle molte ragioni per cui il codice LLVM IR non è, come molti pensano, indipendente dalla piattaforma. Questo tipo di codice, creato per una piattaforma, non può essere semplicemente preso e compilato per un'altra piattaforma (a meno che non si affronti il problema ).
Un altro aspetto interessante da notare è che il tipo i64 non è un numero intero con segno: è neutro per quanto riguarda la rappresentazione del segno del numero. A seconda delle istruzioni, può rappresentare sia numeri con segno che numeri senza segno. Nel caso dell'operazione di somma, ciò non ha importanza, quindi qui non ci sono differenze nell'elaborazione di numeri con segno o senza segno. È importante notare che nel linguaggio C il sovraccarico di una variabile intera con segno porta a comportamenti indefiniti, quindi il front-end Clang aggiunge un flag all'operazione nsw (no signed wrap), che indica a LLVM che può assumere che non ci sia mai un sovraccarico durante la somma.
Questo può essere importante per alcune ottimizzazioni. Ad esempio, la somma di due valori i16 su una piattaforma a 32 bit (con registri a 32 bit) richiede, dopo l'esecuzione della somma, un'operazione di estensione del segno, per rimanere nell'intervallo i16. Per questo motivo, spesso risulta più efficiente eseguire operazioni intere tenendo conto delle dimensioni dei registri della macchina.
Quello che accade successivamente con questo codice IR non ci interessa particolarmente in questo momento. Il codice viene ottimizzato (ma nel caso di un esempio così semplice come il nostro, non c'è nulla da ottimizzare) e poi viene convertito in codice macchina.
Secondo esempio
Il prossimo esempio che considereremo sarà un po' più complesso. In particolare, parleremo di una funzione che somma uno slice di numeri interi:
func sum(numbers []int) int {
n := 0
for i := 0; i < len(numbers); i++ {
n += numbers[i]
}
return n
}Questo codice viene trasformato nel seguente codice Go SSA:
func sum(numbers []int) int:
entry:
jump for.loop
for.loop:
t0 = phi [entry: 0:int, for.body: t6] #n int
t1 = phi [entry: 0:int, for.body: t7] #i int
t2 = len(numbers) int
t3 = t1 < t2 bool
if t3 goto for.body else for.done
for.body:
t4 = &numbers[t1] *int
t5 = *t4 int
t6 = t0 + t5 int
t7 = t1 + 1:int int
jump for.loop
for.done:
return t0Qui puoi già vedere più strutture caratteristiche per la rappresentazione del codice in forma SSA. Probabilmente, la caratteristica più evidente di questo codice è il fatto che non ci sono comandi strutturati di controllo del flusso di calcolo. Per il controllo del flusso di calcolo ci sono solo salti condizionali e incondizionati, e, se consideriamo questo comando come un comando di controllo del flusso, il comando di ritorno.
In realtà, qui si può notare che il programma non è suddiviso in blocchi utilizzando le parentesi graffe (come nei linguaggi della famiglia C). È diviso in etichette, il che ricorda i linguaggi assembly, ed è presentato sotto forma di blocchi base. Nei SSA, i blocchi base sono sequenze continue di codice che iniziano con un’etichetta e terminano con istruzioni di completamento del blocco base, per esempio — return e jump.
Un'altra interessante caratteristica di questo codice è rappresentata dall'istruzione phi. Questa istruzione è piuttosto insolita, e può richiedere del tempo per essere compresa. Ricorda che — è l'acronimo di Static Single Assignment. Si tratta di una rappresentazione intermedia del codice utilizzata dai compilatori, in cui a ciascuna variabile viene assegnato un valore solo una volta. Questo è ideale per esprimere funzioni semplici, come la nostra funzione myAdd, mostrata sopra, ma non è adatta per funzioni più complesse, come la funzione trattata in questa sezione sum. In particolare, durante l'esecuzione di un ciclo si modificano le variabili i e n.
SSA elude il vincolo di assegnazione singola dei valori delle variabili mediante l'uso della cosiddetta istruzione phi (il cui nome è preso dall'alfabeto greco). Infatti, per poter formare una rappresentazione SSA del codice per linguaggi come il C, è necessario ricorrere a qualche astuzia. Il risultato della chiamata a questa istruzione è il valore attuale della variabile (i o n), e come parametri utilizza un elenco di blocchi di base. Ad esempio, consideriamo la seguente istruzione:
t0 = phi [entry: 0:int, for.body: t6] #n Il suo significato è il seguente: se il blocco di base precedente era il blocco entry (d'ingresso), allora t0 è una costante 0, e se il blocco di base precedente era for.body, devi prendere il valore t6 da questo blocco. Tutto questo può sembrare piuttosto misterioso, ma grazie a questo meccanismo si garantisce il funzionamento di SSA. Dal punto di vista umano, tutto ciò complica la comprensione del codice, ma il fatto che ogni valore venga assegnato solo una volta semplifica notevolmente molte ottimizzazioni.
Si noti che se stai scrivendo il tuo compilatore, di solito non devi affrontare questioni simili. Anche Clang non genera tutte queste istruzioni phi, utilizza il meccanismo alloca (somiglia al lavoro con normali variabili locali). Poi, durante un passaggio di ottimizzazione LLVM chiamato , le istruzioni alloca vengono trasformate in forma SSA. TinyGo, tuttavia, riceve input da Go SSA, che, convenientemente, è già stato convertito in forma SSA.
Un'altra innovazione del frammento di codice intermedio considerato è che l'accesso agli elementi di uno slice per indice è presentato come un'operazione di calcolo dell'indirizzo e un'operazione di dereferenziazione del puntatore ottenuto. Qui si può vedere anche l'aggiunta diretta di costanti nel codice IR (ad esempio — 1:int). Nel caso della funzione myAdd Non è stato utilizzato nulla di simile. Ora, dopo aver compreso queste peculiarità, diamo uno sguardo a come si trasformerà questo codice nella forma LLVM IR:
definire i64 @somma(i64* %ptr, i64 %len, i64 p) {
entry:
br label %for.loop
for.loop: ; preds = %for.body, %entry
%0 = phi i64 [ 0, %entry ], [ %5, ref.next ]
%1 = phi i64 [ 0, %entry ], [ %6, ref.next ]
%2 = icmp slt i64 %1, %len
br i1 %2, label %for.body, label %for.done
for.body: ; preds = %for.loop
%3 = getelementptr i64, i64* %ptr, i64 %1
%4 = load i64, i64* %3
%5 = add i64 %0, %4
%6 = add i64 %1, 1
br label %for.loop
for.done: ; preds = %for.loop
ret i64 %0
} Qui, come prima, possiamo vedere la stessa struttura, che include altre costruzioni sintattiche. Ad esempio, nelle chiamate phi i valori e le etichette sono stati scambiati. Tuttavia, qui c'è anche qualcosa a cui vale la pena prestare particolare attenzione.
Per cominciare, qui possiamo vedere una firma di funzione completamente diversa. LLVM non supporta gli slice, quindi, come ottimizzazione, il compilatore TinyGo, che ha prodotto questo codice intermedio, ha suddiviso la descrizione di questa struttura dati in parti. Avrebbe potuto rappresentare tre elementi dello slice (ptr, len e cap) in forma di struttura (struct), ma rappresentarli come tre entità separate consente di eseguire alcune ottimizzazioni. Altri compilatori possono rappresentare uno slice in modo diverso, a seconda delle convenzioni di chiamata della funzione della piattaforma di destinazione.
Un'altra caratteristica interessante di questo codice è l'uso dell'istruzione getelementptr (spesso abbreviata in GEP).
Questa istruzione lavora con i puntatori e viene utilizzata per ottenere un puntatore a un elemento dello slice. Ad esempio, confrontiamola con il seguente codice scritto in C:
int* sliceptr(int *ptr, int index) {
return &ptr[index];
}O con il seguente, equivalente a questo:
int* sliceptr(int *ptr, int index) {
return ptr + index;
} La cosa più importante qui è che l'istruzione getelementptr non esegue operazioni di dereferenziazione. Calcola semplicemente un nuovo puntatore basato su quello esistente. Può essere vista come un'istruzione mul e add a livello hardware. Maggiori dettagli sull'istruzione GEP possono essere letti .
Un'altra caratteristica interessante di questo codice intermedio riguarda l'uso dell'istruzione icmp. Questa è un'istruzione generica utilizzata per implementare il confronto di numeri interi. L'esito di questa istruzione è sempre un valore di tipo i1 — valore booleano. In questo caso, il confronto viene effettuato utilizzando la parola chiave slt (signed less than), poiché stiamo confrontando due numeri, precedentemente rappresentati come tipo -int. Se confrontassimo due numeri interi senza segno, utilizzeremmo icmp, mentre la parola chiave utilizzata per il confronto sarebbe ult. Per confrontare i numeri in virgola mobile si utilizza un'altra istruzione, fcmp, che funziona in modo simile.
Risultati
Ritengo che in questo materiale abbia trattato le caratteristiche più importanti dell'LLVM IR. Naturalmente, ci sono ancora moltissime altre cose. In particolare, nella rappresentazione intermedia del codice possono essere presenti molte annotazioni, che consentono di considerare nelle ottimizzazioni determinate caratteristiche del codice conosciute dal compilatore, che non possono essere espresse in altro modo nell'IR. Ad esempio, questo è il flag inbounds dell'istruzione GEP, o i flag nsw e nuw, che possono essere aggiunti all'istruzione add. Lo stesso vale per la parola chiave private, che indica all'ottimizzatore che la funzione contrassegnata non sarà referenziata al di fuori dell'unità di compilazione corrente. Questo consente di eseguire varie interessanti ottimizzazioni interprocedurali, come la rimozione degli argomenti non utilizzati.
Puoi leggere ulteriori dettagli su LLVM in , che consulterai spesso mentre sviluppi il tuo compilatore basato su LLVM. Ecco , in cui si discute la creazione di un compilatore per un linguaggio molto semplice. Entrambe queste fonti di informazioni saranno utili per la realizzazione del tuo compilatore.
Gentili lettori! Stai utilizzando LLVM?
Fonte: habr.com
