Come sarebbe il codice byte della macchina da registro per questo codice?

6

Spero che questo tipo di domande non sia fuori tema su questo sito.

Finalmente riesco a capire cosa sia una macchina basata sullo stack e come compilare il codice per questo. Ad esempio, il seguente codice: 2 * 5 + 1 verrà compilato in questo bytecode:

push 2
push 5
mult
push 1
add

Tuttavia, quello che voglio capire sono le differenze fondamentali tra la compilazione per una macchina basata su stack e la compilazione per una macchina basata su registri.

Fondamentalmente voglio vedere come dovrebbe apparire il bytecode di una macchina di registro, al contrario del bytecode di una macchina stack.

Per capire questo, vorrei chiederti di mostrarmi come sarebbe il codice bytec per l'espressione sopra, per una macchina di registro. Cioè in che modo: 2 * 5 + 1 verrà compilato in

    
posta Aviv Cohn 01.08.2014 - 00:55
fonte

3 risposte

11

Il registro di macchina bytecode viene spesso in modulo a tre indirizzi , cioè, parla delle relazioni del flusso di dati tra registri, e le operazioni prendono registri di destinazione espliciti. Quindi un set di istruzioni di base può assomigliare a questo:

set register, constant
mul out, in1, in2
add out, in1, in2

Potresti assumere che tu abbia un numero infinito di registri r0 , r1 , ecc. e riscrivi questo in modulo SSA :

set r0, 2       // int r0 = 2;
set r1, 5       // int r1 = 5;
mul r2, r0, r1  // int r2 = r0 * r1;
set r3, 1       // int r3 = 1;
add r4, r2, r3  // int r4 = r2 + r3;

Quindi varie analisi e ottimizzazioni diventano facili. Puoi riutilizzare i registri che non sono più attivi:

set r0, 2       // int r0 = 2;
set r1, 5       // int r1 = 5;
mul r0, r0, r1  // r0 *= r1;
set r1, 1       // r1 = 1;
add r0, r0, r1  // r0 += r1;

Puoi anche consentire alle istruzioni di prendere costanti immediate, anziché caricare tutto in registri:

set r0, 2      // int r0 = 2;
mul r0, r0, 5  // r0 *= 5;
add r0, r0, 1  // r0 += 1;

Quando lo fai, noti una somiglianza con architetture di registro esistenti come x86, e in effetti puoi eseguire allocare i registri per mappare il tuo registratore virtuale su hardware reale:

mov eax, 2
mul eax, 5
add eax, 1

In entrambi i casi, il bytecode è una rappresentazione piatta di un grafico di flusso di dati e controllo:

+---+
| 2 |
+---+
  r0
  |
  | +---+
  | | 5 |
  | +---+
  |   r1
  |   |
+-------+
|   ×   |
+-------+
  r2
  |
  | +---+
  | | 1 |
  | +---+
  |   r3
  |   |
+-------+
|   +   |
+-------+
  r4
  |

Nella notazione dello stack, ciascuna operazione di stack corrisponde a una riga di questo diagramma e la larghezza del diagramma in qualsiasi punto corrisponde alla profondità massima dello stack in quel punto. Nel modulo SSA, ciascun registro corrisponde a un punto nel grafico in cui viene prodotto un valore. Sono semplicemente strutture diverse per parlare della stessa cosa.

    
risposta data 01.08.2014 - 02:38
fonte
9

Fortunatamente, ci sono una varietà di macchine registrate reali ben conosciute che puoi guardare. Ad esempio, il codice x86 per quanto sopra potrebbe essere:

mov eax, 2
mul eax, 5
add eax, 1

(Nella notazione Intel x86, la destinazione è l'operando di sinistra.)

    
risposta data 01.08.2014 - 01:09
fonte
-2

In realtà non hai bisogno di una moltiplicazione per fare 2 * 5. Per moltiplicare qualsiasi numero con una potenza di 2, usa invece il turno di sinistra. Ma supponiamo che tu debba davvero fare un moltiplicare, il risultato dipende dal numero di operandi che un'istruzione ha in quell'architettura e se questa ha un'istruzione di moltiplicazione immediata o meno.

Ad esempio in un computer con 1 operando o architettura dell'accumulatore è possibile farlo in questo modo

load 2   # load accumulator with 2
mult 5   # multiply accumulator with 5
add  1

Nelle architetture a 2 operandi:

move r0, 2
mult r0, 5
add  r0, 1

Questa è l'idea per un set di istruzioni astratte. Le vere architetture potrebbero non supportare tutte queste operazioni e potresti aver bisogno di più istruzioni per riuscirci. Ad esempio 8051 è un'architettura dell'accumulatore, ma non ha un'istruzione moltiplicata per costante, quindi è necessaria un'ulteriore istruzione:

MOV A, #2
MOV B, #5
MUL AB
INC A

In AVR per ottenere il risultato in R0 puoi fare come questo

ldi R2, 2
ldi R3, 5
mul R2, R3
inc R0

In MIPS dove la maggior parte delle istruzioni ha 3 operandi (ma i multipli hanno solo 2 operandi) puoi fare come questo

addi $t0, $zero, 2    # t0 = 2
addi $t1, $zero, 5    # t1 = 5
mult $t0, $t1         # {hi, lo} = t0*t1
mfhi $a0              # high part, maybe unneccessary
mflo $t2              # t2 = LOW(t0*t1)
addi $t2, $t2, 1      # t2 = t0*t1 + 1

In x86 hai molta più scelta. Originariamente la moltiplicazione in x86 ha solo 1 operando e deve essere ottenuta tramite l'ax dell'accumulatore

mov ax, 2
mov bx, 5
mul bx
inc ax

Puoi anche usare 3-operando imul per abbreviare il programma

mov  eax, 2
imul eax, eax, 5
inc  eax

O ancora più breve utilizzando LEA istruzione:

mov rax, 5
lea rax, [rax + rax + 1] ; or possibly lea rax, [rax*2 + 1] although I'm not sure about the syntax
; or
mov rax, 2
lea rax, [rax + rax*4 + 1] ; rax = rax*5 + 1
    
risposta data 01.08.2014 - 07:29
fonte

Leggi altre domande sui tag