Qual è la procedura comune quando si producono target di salto in bytecode?

Non tutte le macchine virtuali utilizzano un codice byte lineare. Se il codice byte forma una struttura di dati del grafico, l'operazione condizionale può fare riferimento direttamente a tutti i rami e non devono essere calcolati obiettivi di salto espliciti (in effetti, il concetto di una destinazione di salto è in qualche modo privo di senso con un tale codice byte). Ho usato questo approccio in alcune implementazioni linguistiche giocattolo.

La maggior parte dei codici byte "reali" utilizza un approccio multi-pass per calcolare gli obiettivi di salto. Iniziamo a visualizzare la struttura del codice byte di cui abbiamo bisogno:

    ,-------------------------.
   |                          v
branch, then-branch..., jump, else-branch..., end
                          |                   ^ 
                          '-------------------'

C'è un codice operativo ramificato che può continuare direttamente con il ramo then o saltare nel ramo else. Alla fine del ramo allora, un salto incondizionato punta alla fine.

Quando emettiamo il codice byte, possiamo emettere il ramo e saltare le istruzioni con valori fittizi , e poi tornare indietro per correggerli in seguito:

branch, then-branch..., jump, else-branch..., end
   |                      |
   v                      v
  ???                    ???

Una volta che il codice byte viene emesso, sappiamo con precisione quanto tempo è il ramo allora e il ramo else. Possiamo quindi sovrascrivere tutti i salti con il loro target corretto. In pseudcode:

compile_conditional(cond, then, else):
   compile(cond)
   branch = emit(branch, null)

   compile_all(then)
   jump = emit(jump, null)

   branch.target = current_location

   compile_all(else)

   jump.target = current_location

Invece dei bersagli assoluti di solito preferiresti i salti relativi in modo che il codice byte possa essere spostato liberamente.

Il codice CPython a cui ti sei collegato fa qualcosa del genere: i target di salto sono compilati prima del salto in modo che il bersaglio sia conosciuto. Il trucco è che prima genera un elenco collegato di blocchi di base (simile al grafico del codice byte sopra menzionato). Ogni salto prende di mira un blocco di base. Il blocco contiene quindi tutte le istruzioni. Abbiamo un blocco di base per la fine, un blocco per il ramo else e un blocco per il ramo then (vedi compiler_if() ). Un assembly pass assemble_jump_offsets() quindi scorre attraverso i blocchi e calcola gli offset di blocco nel codice byte. Una volta fatto, possiamo scorrere tutte le istruzioni in tutti i blocchi e aggiornare le istruzioni di salto con un target relativo.

Uso una routine che valuta un dato AST per la ramificazione su un'etichetta desiderata (con un valore booleano che indica il normale o l'inversione della condizione di salto).

In pseudo codice, (sto provando a trasmettere l'algoritmo, non uno stile di codifica). Genererò il codice per l'istruzione if come segue:

void generateCodeForIfStatement ( ifNode ) {
    var targetForFalseCondition = generateLabel ();
    generateConditionalTestAndBranch ( ifNode.conditionalExpression, 
                                       targetForFalseCondition,
                                       false );
    generateCodeForStatement ( ifNode.thenPart );
    if ( ! ifNode.hasElsePart () ) {
        placeLabelHere ( targetForFalseCondition );
    }
    else {
        var targetAfterElse = generateLabel ();
        jumpTo ( targetAfterElse );
        placeLabelHere ( targetForFalseCondition );
        generateCodeForStatement ( ifNode.elsePart );
        placeLabelHere ( targetAfterElse );
    }
}

Questo gestisce sia if-then che if-then-else . L'espressione condizionale viene valutata e deve diramarsi alla parte else (o almeno attorno alla parte then se la parte else è assente) se l'espressione restituisce false. Pertanto, passiamo false a generateConditionalTestAndBranch per il parametro jumpIfTrue , per far ripartire le cose.

Abbiamo anche bisogno di avere una capacità per generare un'etichetta forward - cioè dobbiamo usare l'etichetta ora, ma è in una posizione ancora sconosciuta / non definita; quindi per essere in grado di posizionarlo (definirne la posizione) nel codice generato più tardi, quando lo sappiamo. Spero che tu possa vederlo nello pseudo codice.

Più in dettaglio, ogni volta che un'etichetta non ancora definita viene utilizzata in un'istruzione generata, l'istruzione associata al codice byte può essere inserita in un elenco in modo che più tardi, quando viene definita la posizione dell'etichetta, tale elenco (di istruzioni) sia fixed up (questa è la parte in cui gli operandi target della diramazione (forward) vengono tradotti dalle etichette, in quanto le etichette alla fine scompaiono dal codice macchina / byte finale), senza necessariamente utilizzare un passaggio sul codice generato.

(Se sono disponibili istruzioni di dimensioni variabili per i rami (ad esempio una breve istruzione per una breve distanza o una lunga istruzione per una lunga distanza), allora c'è l'opportunità di ottimizzare le dimensioni delle istruzioni di branca per i rami in avanti.)

Successivamente, questo valutatore di espressioni condizionali genera una sequenza di istruzioni di test e rami che va al parametro jumpTarget specificato quando la condizione restituisce true, e cade attraverso qualsiasi codice che viene (viene posto) dopo quando il condizione restituisce false .

void generateConditionalTestAndBranch ( AST conditionalExpression,                      
                                       BranchTarget jumpTarget, 
                                       bool jumpOnTrue ) {
    switch ( conditionalExpression.nodeType ) {
        ...
        case "!" :
            generateConditionalTestAndBranch ( ast.child, target, ! jumpOnTrue );
            break;
        case "&&" :
            if ( jumpOnTrue )
                generateTestAndJumpAround ( ast, target, jumpOnTrue );
            else
                generateTestAndJumpThru ( ast, target, jumpOnTrue );
            break;
        case "||" :
            if ( jumpOnTrue )
                generateTestAndJumpThru ( ast, target, jumpOnTrue );
            else
                generateTestAndJumpAround ( ast, target, jumpOnTrue );
           break;
        ...
    }
}

Come puoi vedere, quando hai un operatore ! , il codice inverte semplicemente il flag jumpIfTrue e continua a valutare il resto.

&& e || hanno anche una valutazione di cortocircuito che introduce rami e condizioni nidificate (espressioni) e sembrano molto simili tra loro; questo come sono correlati (ad esempio da demorgan). Ognuno di essi valuta il figlio sinistro e il figlio destro in un contesto dato il valore corrente di jumpIfTrue .

Infine, di seguito sono riportate le semplici funzioni di supporto per la valutazione del cortocircuito condivisa da && e || . Ovviamente, questi helper sono progettati per supportare la composizione di && , || e ! espressioni, invertendo la direzione di salto secondo necessità.

void generateTestAndJumpThru ( AST binaryNode, BranchTarget target, bool jumpIfTrue ) {
    generateConditionalTestAndBranch ( binaryNode.leftChild, target, jumpIfTrue );
    generateConditionalTestAndBranch ( binaryNode.rightChild, target, jumpIfTrue );
}

Per valutare if ( a && b ) , abbiamo bisogno di diramazione alla parte else se si valuta su false, quindi testiamo a e diramo alla parte else se è false, quindi test b e diramazione al else parte se è false.

void generateTestAndJumpAround ( AST binaryNode, BranchTarget target, bool jumpIfTrue ) {
    var around = generateLabel ();
    generateConditionalTestAndBranch ( binaryNode.leftChild, around, ! jumpIfTrue );
    generateConditionalTestAndBranch ( binaryNode.rightChild, target, jumpIfTrue );
    placeLabelHere ( around );
}

Per valutare if ( a || b ) , dobbiamo passare alla parte else entrambi sono falsi, quindi testiamo prima a , e se è vero possiamo saltare la valutazione di b . Nel caso in cui a sia falso andiamo a testare b , e se anche questo è falso, andiamo alla parte else.

Inoltre, quando l'unica (o la prima) affermazione della parte o della parte else è un'istruzione break, continue, return o goto, ci sono ulteriori ottimizzazioni di generazione del codice che possono essere facilmente eseguite qui (per rinuncia ai rami ai rami, in alternativa quelli possono essere ripuliti più tardi).