Sviluppare un compilatore è un compito molto difficile. Ma, fortunatamente, con lo sviluppo di progetti come LLVM, la soluzione a questo problema è notevolmente semplificata, il che consente anche a un singolo programmatore di creare un nuovo linguaggio vicino in termini di prestazioni a C. Lavorare con LLVM è complicato dal fatto che questo Il sistema è rappresentato da un'enorme quantità di codice, corredato di poca documentazione. Per cercare di correggere questa lacuna, l'autore del materiale, la cui traduzione pubblichiamo oggi, mostrerà esempi di codice scritto in Go e mostrerà come vengono prima tradotti in e quindi in LLVM IR utilizzando il compilatore . Il codice Go SSA e LLVM IR è stato leggermente modificato per rimuovere cose che non sono rilevanti per le spiegazioni fornite qui, in modo da rendere le spiegazioni più comprensibili.
Primo esempio
La prima funzione che esaminerò qui è un semplice meccanismo per aggiungere numeri:
func myAdd(a, b int) int{
return a + b
}Questa funzione è molto semplice e, forse, niente potrebbe essere più semplice. Si traduce nel seguente codice Go SSA:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0Con questa visualizzazione, i suggerimenti sul tipo di dati vengono posizionati a destra e nella maggior parte dei casi possono essere ignorati.
Questo piccolo esempio ti permette già di vedere l'essenza di un aspetto dell'SSA. Ossia, quando si converte il codice in forma SSA, ogni espressione viene scomposta nelle parti più elementari di cui è composta. Nel nostro caso, il comando return a + b, infatti, rappresenta due operazioni: sommare due numeri e restituire il risultato.
Inoltre, qui puoi vedere i blocchi base del programma; in questo codice c'è solo un blocco: il blocco di ingresso. Parleremo più approfonditamente dei blocchi di seguito.
Il codice Go SSA si converte facilmente in LLVM IR:
define i64 @myAdd(i64 %a, i64 %b) {
entry:
%0 = add i64 %a, %b
ret i64 %0
}
Ciò che puoi notare è che sebbene qui vengano utilizzate strutture sintattiche diverse, la struttura della funzione è sostanzialmente invariata. Il codice IR LLVM è un po' più forte del codice Go SSA, simile a C. Qui, nella dichiarazione della funzione, prima c'è una descrizione del tipo di dati che restituisce, il tipo di argomento è indicato prima del nome dell'argomento. Inoltre, per semplificare l'analisi IR, i nomi delle entità globali sono preceduti dal simbolo @, e prima dei nomi locali c'è un simbolo % (anche una funzione è considerata un'entità globale).
Una cosa da notare su questo codice è la decisione sulla rappresentazione del tipo di Go int, che può essere rappresentato come un valore a 32 o 64 bit, a seconda del compilatore e della destinazione della compilazione, viene accettato quando LLVM genera il codice IR. Questo è uno dei tanti motivi per cui il codice IR LLVM non è, come molti pensano, indipendente dalla piattaforma. Tale codice, creato per una piattaforma, non può essere semplicemente preso e compilato per un'altra piattaforma (a meno che tu non sia adatto a risolvere questo problema ).
Un altro punto interessante degno di nota è il tipo i64 non è un numero intero con segno: è neutro in termini di rappresentazione del segno del numero. A seconda dell'istruzione, può rappresentare sia numeri con segno che senza segno. Nel caso della rappresentazione dell'operazione di addizione, ciò non ha importanza, quindi non c'è differenza nel lavorare con numeri con segno o senza segno. Qui vorrei notare che nel linguaggio C, l'overflow di una variabile intera con segno porta a un comportamento indefinito, quindi il frontend Clang aggiunge un flag all'operazione nsw (nessun avvolgimento firmato), che indica a LLVM che può presumere che l'addizione non trabocchi mai.
Questo potrebbe essere importante per alcune ottimizzazioni. Ad esempio, aggiungendo due valori i16 su una piattaforma a 32 bit (con registri a 32 bit) richiede, dopo l'aggiunta, un'operazione di espansione del segno per rimanere nel range i16. Per questo motivo, spesso è più efficiente eseguire operazioni su numeri interi in base alle dimensioni dei registri della macchina.
Quello che succederà dopo con questo codice IR non ci interessa particolarmente adesso. Il codice viene ottimizzato (ma nel caso di un esempio semplice come il nostro, non viene ottimizzato nulla) e poi convertito in codice macchina.
Secondo esempio
Il prossimo esempio che vedremo sarà un po' più complicato. Stiamo cioè parlando di una funzione che somma una fetta 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 convertito 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 altre costruzioni tipiche per rappresentare il codice nel modulo SSA. Forse la caratteristica più ovvia di questo codice è il fatto che non esistono comandi strutturati di controllo del flusso. Per controllare il flusso dei calcoli, ci sono solo salti condizionali e incondizionati e, se consideriamo questo comando come un comando per controllare il flusso, un comando di ritorno.
Qui infatti bisogna prestare attenzione al fatto che il programma non è suddiviso in blocchi tramite parentesi graffe (come nella famiglia di linguaggi C). È diviso da etichette, che ricordano i linguaggi assembly, e presentato sotto forma di blocchi di base. In SSA, i blocchi di base sono definiti come sequenze contigue di codice che iniziano con un'etichetta e terminano con istruzioni di completamento del blocco di base, come − return и jump.
Un altro dettaglio interessante di questo codice è rappresentato dall'istruzione phi. Le istruzioni sono piuttosto insolite e potrebbe richiedere del tempo per essere comprese. ricordati che è l'abbreviazione di Static Single Assignment. Questa è una rappresentazione intermedia del codice utilizzato dai compilatori, in cui a ciascuna variabile viene assegnato un valore una sola volta. Questo è ottimo per esprimere funzioni semplici come la nostra funzione myAddmostrato sopra, ma non è adatto per funzioni più complesse come quella discussa in questa sezione sum. In particolare, le variabili cambiano durante l'esecuzione del ciclo i и n.
SSA aggira la restrizione sull'assegnazione di valori variabili una volta utilizzando una cosiddetta istruzione phi (il suo nome è preso dall'alfabeto greco). Il fatto è che per generare la rappresentazione SSA del codice per linguaggi come C, è necessario ricorrere ad alcuni trucchi. Il risultato della chiamata di questa istruzione è il valore corrente della variabile (i o n) e come parametri viene utilizzato un elenco di blocchi di base. Ad esempio, considera questa istruzione:
t0 = phi [entry: 0:int, for.body: t6] #n
Il suo significato è il seguente: se il blocco base precedente era un blocco entry (ingresso), quindi t0 è una costante 0e se il blocco base precedente era for.body, allora devi prendere il valore t6 da questo blocco. Tutto ciò può sembrare abbastanza misterioso, ma questo meccanismo è ciò che fa funzionare la SSA. Dal punto di vista umano, tutto ciò rende il codice difficile da comprendere, ma il fatto che ogni valore venga assegnato una sola volta rende molte ottimizzazioni molto più semplici.
Tieni presente che se scrivi il tuo compilatore, di solito non dovrai occuparti di questo genere di cose. Anche Clang non genera tutte queste istruzioni phi, utilizza un meccanismo alloca (è come lavorare con variabili locali ordinarie). Quindi, quando si esegue un passaggio di ottimizzazione LLVM chiamato , Istruzioni alloca convertito nel modulo SSA. TinyGo, tuttavia, riceve input da Go SSA, che, convenientemente, è già convertito nel formato SSA.
Un'altra innovazione del frammento di codice intermedio in esame è che l'accesso agli elementi slice tramite indice è rappresentato sotto forma di un'operazione di calcolo dell'indirizzo e di un'operazione di dereferenziazione del puntatore risultante. Qui puoi vedere l'aggiunta diretta di costanti al codice IR (ad esempio - 1:int). Nell'esempio con la funzione myAdd questo non è stato utilizzato. Ora che abbiamo eliminato queste funzionalità, diamo un'occhiata a cosa diventa questo codice quando viene convertito nel modulo IR LLVM:
define i64 @sum(i64* %ptr, i64 %len, i64 %cap) {
entry:
br label %for.loop
for.loop: ; preds = %for.body, %entry
%0 = phi i64 [ 0, %entry ], [ %5, %deref.next ]
%1 = phi i64 [ 0, %entry ], [ %6, %deref.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 strutture sintattiche. Ad esempio, nelle chiamate phi valori ed etichette scambiati. Tuttavia, c'è qualcosa a cui vale la pena prestare particolare attenzione.
Per cominciare, qui puoi vedere una firma della funzione completamente diversa. LLVM non supporta le sezioni e di conseguenza, come ottimizzazione, il compilatore TinyGo che ha generato questo codice intermedio ha diviso la descrizione di questa struttura dati in parti. Potrebbe rappresentare tre elementi fetta (ptr, len и cap) come struttura (struct), ma rappresentarli come tre entità separate consente alcune ottimizzazioni. Altri compilatori possono rappresentare la sezione in altri modi, a seconda delle convenzioni di chiamata delle funzioni della piattaforma di destinazione.
Un'altra caratteristica interessante di questo codice è l'uso dell'istruzione getelementptr (spesso abbreviato in GEP).
Questa istruzione funziona con i puntatori e viene utilizzata per ottenere un puntatore a un elemento slice. Ad esempio confrontiamolo 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 sono le istruzioni getelementptr non effettua operazioni di dereferenziazione. Calcola semplicemente un nuovo puntatore in base a quello esistente. Possono essere prese come istruzioni mul и add a livello hardware. Puoi leggere ulteriori informazioni sulle istruzioni GEP .
Un'altra caratteristica interessante di questo codice intermedio è l'uso dell'istruzione icmp. Questa è un'istruzione di scopo generale utilizzata per implementare confronti tra numeri interi. Il risultato di questa istruzione è sempre un valore di tipo i1 — valore logico. In questo caso, il confronto viene effettuato utilizzando la parola chiave slt (con segno minore di), poiché stiamo confrontando due numeri precedentemente rappresentati dal tipo int. Se stessimo confrontando due numeri interi senza segno, allora useremmo icmpe la parola chiave utilizzata nel confronto sarebbe ult. Per confrontare i numeri in virgola mobile, viene utilizzata un'altra istruzione, fcmp, che funziona in modo simile.
Risultati di
Credo che in questo materiale ho trattato le caratteristiche più importanti di LLVM IR. Naturalmente qui c'è molto di più. In particolare, la rappresentazione intermedia del codice può contenere molte annotazioni che permettono ai passaggi di ottimizzazione di tenere conto di alcune caratteristiche del codice note al compilatore e che non possono essere altrimenti espresse in IR. Ad esempio, questa è una bandiera inbounds Istruzioni GEP o flag nsw и nuw, che può essere aggiunto alle istruzioni add. Lo stesso vale per la parola chiave private, indicando all'ottimizzatore che la funzione che contrassegna non verrà referenziata dall'esterno dell'unità di compilazione corrente. Ciò consente molte ottimizzazioni interprocedurali interessanti come l'eliminazione degli argomenti inutilizzati.
Puoi leggere ulteriori informazioni su LLVM in , a cui farai riferimento spesso durante lo sviluppo del tuo compilatore basato su LLVM. Qui , che mira allo sviluppo di un compilatore per un linguaggio molto semplice. Entrambe queste fonti di informazioni ti saranno utili durante la creazione del tuo compilatore.
Cari lettori! Stai utilizzando LLVM?
Fonte: habr.com