Virtual Machines

Representations

Goal: Translate Expression

function {

local_vars = [],

constants = [1, 2, None],

instructions = [

load_const 0

load_const 1

add

return

]

}

f = fun() {

return 1 + 2;

}

Example

Translate:

​

​

​

1 + 2

Example

Translate:

​

​

​

1 + 2

Translation: Variable Reference

// Description: load value of local variable and push onto operand stack

// Mnemonic: load_local i

// Operand 0: index of local variable to read

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

LoadLocal,

​

// Description: load value of global variable

// Mnemonic: load_global i

// Operand 0: index of name of global variable in enclosing function's names list // Stack: S => S :: global_value_of(f.names[i])

LoadGlobal

Virtual Machine

x = 1;

f = fun(y) {

return x + y;

};

f(1);

Organization/Representation: Goals

• Match design of the source languages
• Examples: types that are first class in the language (None, integer, bools, closures) are typically first class in the vm

​

• Efficiency
• Reify static information about the source language and semantics
• Leverage static information for performance

​

• Flexibility
• Support changes in source language with limited changes in VM
• Support different source languages

Data Organization (Interpreter)

​

​

​

​

​

• How did you access z? (local)
• How did you access f? (field)
• How did you access x? (global/free)
• How did you access y? (free)

x = 1;

f = fun(y) {

g = fun(z) {

return x + y + z.f;

};

g({f : y + 1});

};

f(x + 1);

Record { f : 1 }

Heap

Closure{ p : }

Closure{ p : }

Organization: Naming/Addressing

Symbol Tables

• Key Concept in Compilation

​

• Compiler uses symbol tables to determine scope statically

​

• Basic Operation: Lookup
• Given a string, find a descriptor
• For dynamic languages, the descriptor is primarily about scope
• For static languages it often includes also type information
• Typical Implementation: hierarchical hash tables

Hierarchy In Symbol Tables

• Hierarchy comes from nested scopes
• In static OO languages it can also come from inheritance.

​

• Lookup Proceeds Up Hierarchy Until Descriptor is Found

​

• In our context, the symbol table is a static version of the stack frames that are used at runtime

Definitions

• Global
• A variable in the outermost frame

​

• Local
• A variable defined in this frame

​

• Free
• A variable that is neither global nor local

​

• Referenced
• A variable referenced by a nested frame

Symbol Table

​

​

​

​

​

​

​

​

Statically (in the compiler) compute for each scope

• Globals (tag variable as “global”)
• Locals (tag variable as “local”)
• Referenced (tag variable as “ref”)

​

​

x = 1;

f = fun(y) {

g = fun (z) {

return x + y + z;

};

return g;

};

f(2)(3);

Symbol Table

​

​

​

​

​

​

​

​

Statically (in the compiler) compute for each scope

• Globals (tag variable as “global”)
• Locals (tag variable as “local”)
• Referenced (tag variable as “ref”)

​

​

x = 1;

f = fun(y) {

g = fun (z) {

return x + y + z;

};

return g;

};

f(2)(3);

Symbol Table

​

​

​

​

​

​

​

​

Statically (in the compiler) compute for each scope

• Globals (tag variable as “global”)
• Locals (tag variable as “local”)
• Referenced (tag variable as “ref”)

​

​

x = 1;

f = fun(y) {

g = fun (z) {

return x + y + z;

};

return g;

};

f(2)(3);

Symbol Table

​

​

​

​

​

​

​

​

Statically (in the compiler) compute for each scope

• Globals (tag variable as “global”)
• Locals (tag variable as “local”)
• Referenced (tag variable as “ref”)

​

​

x = 1;

f = fun(y) {

g = fun (z) {

return x + y + z;

};

return g;

};

f(2)(3);

Code Generation

• Global Variable
• Generate load_global

​

• Local Variable
• Generate load_local

​

• Referenced
• Either load_local or push_ref, load_ref could work

​

• Free
• Access via reference, push_ref, load_ref

Example:

function {

functions = [ ],

constants = [None, 0, 1],

names = [x, f],

instructions = [

load_const 2

store_global 0

load_const 1

load_func 0

alloc_closure

store_global 1

load_global 1

load_const 2

call 1

pop

load_const 0

return

]

}

function {

local_vars = [y],

constants = [None],

names = [x]

instructions = [

load_global 0

load_local 0

add

return

]

}

x = 1;

f = fun(y) {

return x + y;

};

f(1);

Efficient Representations (bytecode and other low-level) representations leverage static information about the program to enable and enforce efficient encodings of the program’s execution

Organization: Naming/Addressing

Locals as Maps

void Frame::store(vector<Bucket*> frame, string name, Value* val)

{

uint64_t h = hash(name);

Bucket* bucket = frame[h % frame.size()];

Bucket* b = new Bucket(bucket, name, val);

frame[h % frame.size()] = b;

}

fun()

{

x = 1;

y = 2;

z = 3;

};

Value* Frame::lookup(vector<Bucket*> frame, string name)

{

uint64_t h = hash(name);

Bucket* bucket = frame[h % frame.size()];

return bucket->find(name);

}

Locals as Arrays

​

​

​

​

​

​

​

• Set of names is static

fun()

{

x = 1;

y = 2;

z = 3;

};

function {

local_vars = [x, y, z],

constants = [1, 2, 3]

instructions = [

load_const 0

store_local 0

load_const 1

store_local 1

load_const 2

store_local 2

]}

void Frame::store(vector<Value *> frame, uint64_t index, Value *val)

{

frame[index] = val;

}

Value* Frame::lookup(vector<Value *> frame, uint64_t index)

{

return frame[index];

}

Free Variables

​

​

​

​

​

• How did you access x? (global/free)
• How did you access y? (free)
• Each may require expensive pointer chasing
• Nearest definition can be statically determined

Closure{ p : }

Closure{ p : }

Heap

x = 1;

f = fun(y) {

g = fun(z) {

return x + y + z;

};

return g;

};

f(2)(3);

Free Variables (Faster)

​

​

​

​

​

• Introduce references
• A pointer to a piece of data.

Closure{ p : }

Closure{ p : }

Heap

x = 1;

f = fun(y) {

g = fun(z) {

return x + y + z;

};

return g;

};

f(2)(3);

Reference{ }

Free Variables (Faster)

​

​

​

​

​

​

• Statically resolve frame and pass�pointer to data variable references

x = 1;

f = fun(y) {

g = fun(z) {

return x + y + z;

};

return g;

};

f(2)(3);

Heap

Closure{ [ ]}

Reference{ }

Closure{ p : }

Free Variables (Faster)

x = 1;

f = fun(y) {

g = fun(z) {

return x + y + z;

};

return g;

};

f(2)(3);

Heap

Closure{ [ ]}

Reference{ }

Closure{ p : }

​

​

​

​

​

​

• Statically resolve frame and pass�pointer to data variable references�(no more parent pointer)

Free Variables (Faster)

x = 1;

f = fun(y) {

g = fun(z) {

return x + y + z;

};

return g;

};

f(2)(3);

Heap

Closure{ [ ]}

Reference{ }

Closure{ p : }

​

​

​

​

​

​

• Statically resolve frame and pass�pointer to data variable references�(no more parent pointer)

Free Variables (Faster)

x = 1;

f = fun(y) {

g = fun(z) {

return x + y + z;

};

return g;

};

f(2)(3);

Heap

Closure{ [ ]}

Closure{ [ ] }

Reference{ }

​

​

​

​

​

​

• Statically resolve frame and pass�pointer to data variable references�(no more parent pointer)

Free Variables (Faster)

x = 1;

f = fun(y) {

g = fun(z) {

return x + y + z;

};

return g;

};

f(2)(3);

Heap

Closure{ [ ]}

Closure{ [ ] }

Reference{ }

function {

local_vars = [z],

free_vars = [y]

names = [x]

instructions = [

load_global 0

push_ref 0

load_ref

add

load_local 0

add

return

]}

Code Gen

function {

local_vars = [z],

free_vars = [y]

names = [x]

instructions = [

load_global 0

push_ref 0

load_ref

add

load_local 0

add

return

]}

x = 1;

f = fun(y) {

g = fun(z) {

return x + y + z;

};

return g;

};

f(2)(3);

function {

functions = [ ],

local_vars = [y, g],

local_ref_vars [y],

free_vars = []

names = []

instructions = [

load_func 0

push_ref 0

alloc_closure 1

store_local 1

load_local 1

return

]}

g (from previous slide)

f

Conclusion

Efficient Representations (bytecode and other low-level) representations leverage static information about the program to enable and enforce efficient encodings of the program’s execution

Records as Maps

​

​

​

​

​

​

​

• Can we do better?

​

​

​

​

​

​

​

fun() {

r = {

x : 1;

};

}

function

{

local_vars = [r],

constants = [1],

names = [x]

instructions = [

alloc_record

dup

load_const 0

field_store 0

store_local 0

]}

Significant Impact of Dynamic Behavior

• Dynamic Language
• Records/Objects can add or subtract fields

​

​

​

​

​

​

​

• Static Language (C++/Java)
• Objects have statically determined set of fields
• Objects layouts are static arrays with efficient access

​

​

fun() {

r = {

x : 1;

};

}

f = fun(y) {

r = {

x : 1;

};

​

r[y] = 2;

};

f(input());

Records: Maps (Revisited)

​

​

​

​

​

​

​

• Can we do better?
• Field access name is static and constant
• Note: different instruction (r[x]) for dynamic names

​

​

​

​

​

​

​

fun() {

r = {

x : 1;

};

}

function

{

local_vars = [r],

constants = [1],

names = [x]

instructions = [

alloc_record

dup

load_const 0

field_store 0

store_local 0

]}

Records: Maps (Revisited)

​

​

​

​

​

​

​

• Can we do better?

​

​

​

​

​

​

​

fun() {

r = {

x : 1;

};

}

function

{

local_vars = [r],

constants = [1],

names = [x]

instructions = [

alloc_record

dup

load_const 0

field_store 0

store_local 0

]}

Value* Frame::lookup(vector<Bucket*> frame, string name)

​

{

uint64_t h = hash(name);

Bucket* bucket = frame[h % frame.size()];

return bucket->find(name);

}

void Frame::store(vector<Bucket*> frame, string name, Value* val)

​

{

uint64_t h = hash(name);

Bucket* bucket = frame[h % frame.size()];

Bucket* b = new Bucket(bucket, name, val);

frame[h % frame.size()] = b;

}

Records: Maps (Revisited)

​

​

​

​

​

​

​

• Can we do better?

​

​

​

​

​

​

​

fun() {

r = {

x : 1;

};

}

function

{

local_vars = [r],

constants = [1],

names = [x]

instructions = [

alloc_record

dup

load_const 0

field_store 0

store_local 0

]}

Value* Frame::lookup(vector<Bucket*> frame, uint64_t h,

string name)

{

​

Bucket* bucket = frame[h % frame.size()];

return bucket->find(name);

}

void Frame::store(vector<Bucket*> frame, string name, uint64_t h,

Value* val)

{

uint64_t h = hash(name);

Bucket* bucket = frame[h % frame.size()];

Bucket* b = new Bucket(bucket, name, val);

frame[h % frame.size()] = b;

}

​

​

​

​

​

​

​

​

• Precompute static computations

​

​

​

​

​

​

​