Gentile introduzione a JIT e compilazione dinamica / generazione di codice

Question

Le basi ingannevolmente semplici della generazione di codice dinamico all'interno di un framework C / C ++ sono già state trattate in un'altra domanda . Ci sono delle introduzioni delicate nell'argomento con esempi di codice?

I miei occhi iniziano a sanguinare fissando compilatori JIT open source altamente intricati quando le mie esigenze sono molto più modeste.

Esistono buoni testi sull'argomento che non assumono un dottorato in informatica? Sto cercando modelli ben usurati, cose a cui prestare attenzione, considerazioni sulle prestazioni, ecc. Le risorse elettroniche o basate su alberi possono essere ugualmente preziose. Puoi assumere una conoscenza pratica del linguaggio assembly (non solo x86).

Answer 1

Beh, uno schema che ho usato negli emulatori è simile a questo:

typedef void (*code_ptr)();
unsigned long instruction_pointer = entry_point;
std::map<unsigned long, code_ptr> code_map;


void execute_block() {
    code_ptr f;
    std::map<unsigned long, void *>::iterator it = code_map.find(instruction_pointer);
    if(it != code_map.end()) {
        f = it->second
    } else {
        f = generate_code_block();
        code_map[instruction_pointer] = f;
    }
    f();
    instruction_pointer = update_instruction_pointer();
}

void execute() {
    while(true) {
        execute_block();
    }
}

Questa è una semplificazione, ma l'idea è lì. Fondamentalmente, ogni volta che viene chiesto al motore di eseguire un "blocco di base" (di solito un tutto fino al successivo controllo del flusso operativo o l'intera funzione possibile), lo cercherà per vedere se è già stato creato. In tal caso, eseguilo, altrimenti crealo, aggiungilo e quindi eseguilo.

risciacquo ripetizione :)

Per quanto riguarda la generazione del codice, questo diventa un po 'complicato, ma l'idea è quella di emettere una corretta funzione "quot". che fa il lavoro del tuo blocco di base nel contesto della tua VM.

MODIFICA: nota che non ho dimostrato alcuna ottimizzazione, ma hai chiesto una "introduzione delicata"

EDIT 2: ho dimenticato di menzionare uno degli acceleratori più immediatamente produttivi che puoi implementare con questo schema. Fondamentalmente, se non non rimuovi mai un blocco dal tuo albero (puoi aggirarlo se lo fai ma è molto più semplice se non lo fai mai), allora puoi " concatenare " blocchi insieme per evitare le ricerche. Ecco il concetto. Ogni volta che ritorni da f () e stai per fare il " update_instruction_pointer " ;, se il blocco appena eseguito termina in una chiamata, in un salto incondizionato o non termina affatto nel controllo del flusso, puoi " fixup " ; le sue istruzioni ret con un jmp diretto al blocco successivo verranno eseguite (perché sarà sempre la stessa) se l'hai già emesso. Questo lo rende quindi in esecuzione sempre più spesso nella VM e sempre meno in " execute_block " la funzione.

Answer 2

Non sono a conoscenza di alcuna fonte specificamente correlata alle JIT, ma immagino che sia un po 'come un normale compilatore, solo più semplice se non sei preoccupato per le prestazioni.

Il modo più semplice è iniziare con un interprete di macchine virtuali. Quindi, per ciascuna istruzione VM, genera il codice assembly che l'interprete avrebbe eseguito.

Per andare oltre, immagino che analizzeresti i codici byte della VM e li convertiresti in una sorta di forma intermedia adatta (tre codici indirizzo? SSA?) e quindi ottimizzi e generi codice come in qualsiasi altro compilatore.

Per una macchina virtuale basata su stack, può essere utile tenere traccia della "corrente" profondità dello stack mentre traduci i codici byte in forma intermedia e tratta ogni posizione dello stack come una variabile. Ad esempio, se pensi che l'attuale profondità dello stack sia 4 e vedi un "push" istruzione, potresti generare un incarico a " stack_variable_5 " e incrementare un contatore di stack di tempo di compilazione o qualcosa del genere. Un " aggiungi " quando la profondità dello stack è 5 potrebbe generare il codice " stack_variable_4 = stack_variable_4 + stack_variable_5 " e decrementa il contatore della pila dei tempi di compilazione.

È anche possibile tradurre il codice basato su stack in alberi di sintassi. Mantenere uno stack in fase di compilazione. Ogni "push" l'istruzione provoca una rappresentazione della cosa che viene spinta per essere memorizzata nello stack. Gli operatori creano nodi dell'albero di sintassi che includono i loro operandi. Ad esempio, " X Y + " potrebbe far sì che lo stack contenga " var (X) " ;, quindi " var (X) var (Y) " e poi il plus fa apparire entrambi i riferimenti var e spinge " plus (var (X), var (Y)) " ;.

Answer 3

Procuratevi una copia del libro di Joel Pobar su Rotor (quando uscirà) e approfondite la fonte < SSCLI . Attenzione, la follia è dentro :)