Lo sviluppo di un compilatore è un compito molto difficile. Ma, fortunatamente, con l'evoluzione di progetti come LLVM, la soluzione di questo problema diventa significativamente più semplice, consentendo anche a un programmatore solitario di creare un nuovo linguaggio, vicino per prestazioni al C. Lavorare con LLVM è complicato dal fatto che questo sistema è rappresentato da un'enorme quantità di codice, fornito di scarsa documentazione. Per cercare di correggere questo difetto, l'autore del materiale, il cui articolo stiamo pubblicando oggi, intende dimostrare esempi di codice scritti in Go e mostrare come vengono tradotti prima in , e poi — in LLVM IR utilizzando il compilatore . Il codice Go SSA e LLVM IR è stato leggermente modificato, con l'eliminazione di quanto non pertinente per le spiegazioni fornite qui, al fine di rendere tali spiegazioni più comprensibili.
Primo esempio
La prima funzione che intendo analizzare qui rappresenta un semplice meccanismo per sommare numeri:
func myAdd(a, b int) int{
return a + b
}Questa funzione è molto semplice, e probabilmente non c'è nulla di più semplice. Viene tradotta nel seguente codice Go SSA:
func myAdd(a int, b int) int:
entry:
t0 = a + b int
return t0In questa rappresentazione della funzione, i suggerimenti sui tipi di dati sono posizionati a destra, e nella maggior parte dei casi si può anche ignorarli.
Questo piccolo esempio consente già di vedere l'essenza di uno degli aspetti di SSA. Infatti, durante la conversione del codice nella forma SSA, ogni espressione viene divisa nelle parti più elementari da cui è composta. Nel nostro caso, il comando return a + b, in effetti, rappresenta due operazioni: l'addizione di due numeri e il ritorno del risultato.
Inoltre, qui si possono vedere anche i blocchi di base del programma; nel codice fornito c'è solo un blocco — il blocco di ingresso (entry block). Ne parleremo più nel dettaglio più avanti.
Il codice Go SSA si traduce 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 generale, non è cambiata. Il codice LLVM IR è leggermente più potente del codice Go SSA e assomiglia al C. Qui, nella dichiarazione della funzione, prima viene fornita la descrizione del tipo di dato restituito, il tipo dell'argomento è specificato prima del nome dell'argomento. Inoltre, per facilitare l'analisi IR, prima dei nomi delle entità globali si trova il simbolo @, mentre prima dei nomi locali si trova il simbolo % (la funzione è anch'essa considerata un'entità globale).
Una delle peculiarità di questo codice, a cui prestare attenzione, è che la decisione su come rappresentare il tipo Go int, che può essere rappresentato da un valore a 32 bit o 64 bit a seconda del compilatore e dell'obiettivo di compilazione, viene presa al momento della creazione del codice LLVM IR. Questa è una delle molte ragioni per cui il codice LLVM IR non è, come molti pensano, indipendente dalla piattaforma. Tale codice, creato per una piattaforma, non può semplicemente essere preso e compilato per un'altra piattaforma (a meno che non si affronti la questione ).
Un altro aspetto interessante da notare è che il tipo i64 non è un intero con segno: è neutro in termini di rappresentazione del segno del numero. A seconda dell'istruzione, può rappresentare numeri sia con segno che senza segno. Nel caso della rappresentazione dell'operazione di somma, questo non ha importanza, pertanto non c'è differenza nel lavorare con numeri con segno o senza segno. Qui vorrei sottolineare che nel linguaggio C il sovraccarico di una variabile intera con segno porta a un comportamento indefinito, quindi il frontend Clang aggiunge un flag all'operazione nsw (no signed wrap), che indica a LLVM che può assumere che durante la somma non si verifichi mai un sovraccarico.
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) ha bisogno, dopo l'esecuzione della somma, di un'operazione di estensione del segno per rimanere nell'intervallo i16. Per questo motivo, spesso si rivela più efficace eseguire operazioni intere tenendo conto delle dimensioni dei registri della macchina.
Ciò che accade successivamente con questo codice IR non ci interessa particolarmente al momento. Il codice viene ottimizzato (ma nel caso di un esempio così semplice come il nostro, non viene ottimizzato nulla) e poi viene trasformato in codice macchina.
Secondo esempio
Il prossimo esempio che esamineremo sarà un po' più complesso. In particolare, si tratta 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 si possono già notare più strutture tipiche per la rappresentazione del codice in forma SSA. Probabilmente, la caratteristica più evidente di questo codice è il fatto che non ci sono comandi strutturati per il controllo del flusso di calcolo. Solo i salti condizionali e incondizionali sono presenti per gestire il flusso di calcolo, e se si considera questo comando come un comando di gestione del flusso, il comando di ritorno.
In realtà, è importante notare che il programma non è suddiviso in blocchi utilizzando 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 finiscono con istruzioni di completamento del blocco base, per esempio — return e jump.
Un'altra interessante particolarità di questo codice è l'istruzione phi. Questa istruzione è piuttosto insolita, e potrebbe richiedere del tempo per comprenderla. Ricorda che — è l'abbreviazione di Static Single Assignment. Questa è una rappresentazione intermedia del codice utilizzata dai compilatori, in cui ad ogni variabile viene assegnato un valore una sola volta. È particolarmente adatta per esprimere funzioni semplici, come la nostra funzione myAdd, mostrata sopra, ma non è adatta per funzioni più complesse — come quella discussa in questa sezione sum. In particolare, durante l'esecuzione di un ciclo, cambiano le variabili i e n.
SSA elude il vincolo di assegnazione singola dei valori delle variabili utilizzando la cosiddetta istruzione phi (il cui nome è derivato dall'alfabeto greco). Infatti, per formare una rappresentazione SSA del codice per linguaggi come C, è necessario ricorrere a qualche trucco. Il risultato di questa istruzione è il valore attuale della variabile (i o n), mentre come parametri si utilizza una lista 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 (di ingresso), allora t0 è una costante 0, mentre se il blocco di base precedente era for.body, allora bisogna prendere il valore t6 da quel blocco. Tutto ciò può sembrare piuttosto misterioso, ma grazie a questo meccanismo il funzionamento di SSA è garantito. Da un punto di vista umano, tutto questo complica la comprensione del codice, ma il fatto che ogni valore venga assegnato una sola volta semplifica notevolmente molte ottimizzazioni.
Si noti che se si sta scrivendo un proprio compilatore, di solito non si ha a che fare con queste cose. Anche Clang non genera tutte queste istruzioni phi, utilizza un meccanismo alloca che ricorda il lavoro con normali variabili locali. Poi, durante il passaggio di ottimizzazione di LLVM, chiamato , le istruzioni alloca vengono trasformate nella forma SSA. TinyGo, tuttavia, riceve dati da Go SSA, che, comodamente, sono già stati trasformati nella forma SSA.
Un'altra novità del frammento di codice intermedio considerato è che l'accesso agli elementi di uno slice per indice è rappresentato 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). Nell'esempio con la funzione myAdd Non è stato usato nulla di simile. Ora, una volta comprese queste peculiarità, diamo un'occhiata a come apparirà questo codice una volta trasformato nella forma LLVM IR:
definisci i64 @somma(i64* %ptr, i64 %len, i64 p) {
entry:
br label %for.loop
for.loop: ; predicatori = %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: ; predicatori = %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: ; predicatori = %for.loop
ret i64 %0
} Qui, come in precedenza, possiamo vedere la stessa struttura, che include altre costrizioni sintattiche. Ad esempio, nelle chiamate phi i valori e le etichette sono stati scambiati. Tuttavia, qui c'è qualcosa di cui vale la pena prestare particolare attenzione.
Per cominciare, qui possiamo osservare una firma di funzione completamente diversa. LLVM non supporta gli slice, di conseguenza, come ottimizzazione, il compilatore TinyGo, che ha generato questo codice intermedio, ha suddiviso la descrizione di questa struttura dati in parti. Potrebbe rappresentare tre elementi di uno slice (ptr, len e cap) sotto forma di struttura (struct), ma rappresentarli come tre entità separate consente di eseguire alcune ottimizzazioni. Altri compilatori potrebbero rappresentare lo slice in altro modo, a seconda delle convenzioni di chiamata delle funzioni della piattaforma di destinazione.
Un'altra caratteristica interessante di questo codice è l'utilizzo dell'istruzione getelementptr (spesso abbreviata in GEP).
Questa istruzione lavora con i puntatori ed è utilizzata per ottenere il puntatore a un elemento dello slice. Ad esempio, mettiamola a confronto 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 dereferencing. Calcola solo un nuovo puntatore, basandosi 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 interessante caratteristica di questo codice intermedio è l'uso dell'istruzione icmp. Questa è un'istruzione di uso generale, utilizzata per implementare il confronto di numeri interi. Il risultato dell'esecuzione di questa istruzione è sempre un valore di tipo i1 — valore booleano. In questo caso, il confronto avviene utilizzando la parola chiave slt (signed less than), poiché stiamo confrontando due numeri, precedentemente rappresentati dal tipo int. Se confrontassimo due numeri interi senza segno, quindi come istruzione utilizzeremmo icmp, e la parola chiave usata nel confronto sarebbe ult. Per confrontare numeri in virgola mobile viene utilizzata un'altra istruzione, fcmp, che funziona in modo simile.
Conclusioni
Ritengo che in questo materiale abbia trattato le caratteristiche più importanti di LLVM IR. Certo, c'è ancora molto da esplorare. In particolare, nella rappresentazione intermedia del codice possono essere presenti molte annotazioni che consentono di considerare durante i passaggi di ottimizzazione determinate caratteristiche del codice, note al compilatore, che non possono essere espresse in altro modo in IR. Ad esempio, c'è 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à richiamata dall'esterno dell'unità di compilazione attuale. Questo consente di effettuare molte ottimizzazioni interprocedurali interessanti, come la rimozione di argomenti non utilizzati.
Puoi leggere i dettagli su LLVM in , a cui farai spesso riferimento mentre sviluppi il tuo compilatore basato su LLVM. Ecco , che tratta dello sviluppo di un compilatore per un linguaggio molto semplice. Entrambe queste fonti ti saranno utili per la creazione del tuo compilatore.
Gentili lettori! Stai utilizzando LLVM?
Fonte: habr.com
