1 of 37

Virtual Machines

Syntax-Directed Translation

2 of 37

Syntax-Directed Translation

fun(y) {

x = y + 2;

};

function {

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

load_const 1

add

store_local 1

load_const 0

return

]

}

function __function_1 (y) : {

%x = alloca int64_t

%0 = %y

%1 = 2

%2 = add %0 %1

store %x %2

%3 = 0

return %3

}

__function_1 :

sub 8 %rsp

mov %rsp %rbp

mov (%rbp, 2, 8) %rax

mov 2 %rcx

add %rcx %rax

mov %rax (%rbp)

mov 0 %rax

ret

High-Level

VM

Low-Level

VM

Machine Code

Language

3 of 37

Syntax-Directed Translation

The translation to virtual machine instructions must do the following

Break complex expressions into sequences of simple instructions
Associate variable names with explicit storage locations
Make control flow explicit through jumps

Translation

AST -> CFG + Instructions

4 of 37

Simple Language

(sequential composition)�(if-then-else)

(loop)

(assignment)

5 of 37

AST (Parsing)

x > 1

x > 10

x = x – 1

x = x – 2

while

if

while(x > 1) {

if (x > 10) {

x = x – 2;

} else {

x = x – 1;

}

e

s

e

s1

s2

6 of 37

Control Flow Graph: an alternative program representation.

while(x > 1) {

if (x > 10) {

x = x – 2;

} else {

x = x – 1;

}

x > 1

x > 10

x = x - 1

x = x - 2

True

False

True

CFG

7 of 37

Control Flow Graph: an alternative program representation.

x > 1

x > 10

x = x - 1

x = x - 2

True

False

True

AST

CFG

x > 1

x > 10

x = x – 1

x = x – 2

while

if

e

s

e

s1

s2

Execution model: recursion

Execution model: iteration

8 of 37

CFG Formally

9 of 37

Syntax-Direct Translation

x > 1

x > 10

x = x - 1

x = x - 2

True

False

True

AST

CFG

x > 1

x > 10

x = x – 1

x = x – 2

while

if

e

s

e

s1

s2

10 of 37

Goal: Translate Expression

function {

local_vars = [],

constants = [1, 2, None],

instructions = [

load_const 0

load_const 1

add

return

]

}

f = fun() {

return 1 + 2;

}

11 of 37

Inference Rules for Translation

Semantics:

Translation:

12 of 37

Step 1: Generating Basic Blocks

Define the translation for control-flow-free constructs

Meaning: the term translates to a basic block

13 of 37

Simple Language: E has no control flow

(sequential composition)�(if-then-else)

(loop)

(assignment)

14 of 37

Translation: Integer Constant

// Description: push a constant onto the operand stack

// Mnemonic: load_const i

// Operand 0: index of constant in enclosing function's list of constants

// Stack: S => S :: f.constants()[i]

LoadConst,

Where does i come from?

15 of 37

Generating Basic Blocks

Define the translation for control-flow-free constructs

Meaning: the term translates to a basic block

16 of 37

Generating Basic Blocks

Define the translation for control-flow-free constructs

Meaning: with a list of constants, the term translates to a list of constants and a basic block

17 of 37

Translation: Load Constant

// Description: push a constant onto the operand stack

// Mnemonic: load_const i

// Operand 0: index of constant in enclosing function's list of constants

// Stack: S => S :: f.constants()[i]

LoadConst,

18 of 37

Allocating a Constant

19 of 37

Translation: Variable reference

20 of 37

MITScript Virtual Machine

function {

functions = [ ],

constants = [None, 0, 1],

names = [f],

instructions = [

load_const 1

load_func 0

alloc_closure

store_global 0

load_global 0

load_const 2

call 1

pop

load_const 0

return

]}

function {

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

load_const 1

add

store_local 1

load_const 0

return

]

}

f = fun(y) {

x = y + 2;

};

f(1);

We’ll come back to this later!

21 of 37

Translation: Unary Minus

// Description: computes the unary minus of the integer operation

// Mnemonic: neg

// Operand 0: N/A

// Operand 1: value

// Stack: S :: operand 1 => S:: - operand 1�Neg,

22 of 37

Observation

Our translation rules are very similar to the rules of our semantics

Semantics:

Translation:

23 of 37

Plus

// Description: implements addition (as given in the semantics of Assignment #2)

// Mnemonic: add

// Operand 0: N/A

// Operand 1: right value

// Operand 2: left value

// Result: value of the operation as specified by the semantics of Assignment #2

// Stack: S:: operand 2 :: operand 1 => S :: op(operand 2, operand 1)

Add,

24 of 37

Goal: Translate Expression

function {

local_vars = [],

constants = [1, 2, None],

instructions = [

load_const 0

load_const 1

add

return

]

}

f = fun() {

return 1 + 2;

}

25 of 37

Example

Translate:

1 + 2

26 of 37

Example

Translate:

1 + 2

27 of 37

Example

Translate:

1 + 2

28 of 37

Goal: Translate Statements

function {

local_vars = [],

constants = [1, 2, None],

instructions = [

load_const 0

load_const 1

add

return

]

}

f = fun() {

return 1 + 2;

}

29 of 37

Inference Rules for Translation

Semantics:

Translation:

30 of 37

Translation

while (x > 1) {

if (x > 10) {

x = x – 2;

} else {

x = x – 1;

}

x > 1

x > 10

x = x - 1

x = x - 2

True

False

True

CFG

31 of 37

Sequential Composition: (missing constants!)

32 of 37

Translation

while (x > 1) {

if (x > 10) {

x = x – 2;

} else {

x = x – 1;

}

x > 1

x > 10

x = x - 1

x = x - 2

True

False

True

CFG

33 of 37

If statement: (missing constants!)

34 of 37

Translation

while (x > 1) {

if (x > 10) {

x = x – 2;

} else {

x = x – 1;

}

x > 1

x > 10

x = x - 1

x = x - 2

True

False

True

CFG

35 of 37

While statement: (missing constants!)

36 of 37

Inference Rules for Translation

Semantics:

Translation:

37 of 37

MITScript Virtual Machine

function {

functions = [ ],

constants = [None, 0, 1],

names = [f],

instructions = [

load_const 1

load_func 0

alloc_closure

store_global 0

load_global 0

load_const 2

call 1

pop

load_const 0

return

]}

function {

local_vars = [y, x],

constants = [None, 2],

instructions = [

load_local 0

load_const 1

add

store_local 1

load_const 0

return

]

}

f = fun(y) {

x = y + 2;

};

f(1);