MSCP 52011
Introduction to Computer Systems
Virtual Machines Virtual Machine Language
Conventional Compilation a.k.a. Direct Compilation
Need n*m compilers
2- Tier Compilation
need n+m translators
1st Compilation Stage (compiler)
Depends only on the details of the source language
2nd Compilation Stage (virtual machine translator)
Depends only on the details of the target platform (i.e., the machine language of the platform)
High-level code
if (m>0)
t = sqrt(m/(b*g))
else t=0
Scope
VM code Assembly
push m @SP push A=M constant 0 M=D lt @SP if-goto end M=M+1 push m @LCL push b D=M push g @0 function D=D+A mult 2 @R13 function div M=D
2 @SP function AM=M-1 sqrt 1 D=M
. @R13 . A=M . M=D
@SP . . .
Machine code
0000000000000000
1000011000010000
1110001100001000
0100000000000000
1110110000010000
0000000000010001
1110001100001000
0000000000010001
1111110000100000
1110111010001000
0000000000010001
1111110000010000
0000000000100000
1110000010010000
0000000000010001
1110001100001000
0000000000010000
1111110010011000
. . .
Intermediate Code
• interface between the two stages of compilation
• must be general enough to handle lots of high- level-language and machine-language pairs
• can be modeled as the language of an abstract machine
• turns programming languages into “write-once, run-anywhere” languages
Java Virtual Machine
• commonly used virtual machine
• intermediate language is called “bytecode”
• developed by Sun, licensed by Oracle
• can be compiled and run by application launcher (java) or interpreted (JVM runtime)
• many languages compile to java byte code
Common Language Runtime (CLR)
• virtual machine component of .NET framework
• c# compiles to CLR code • developed by Microsoft
Stack-oriented Machine
Typical operation:
1. poptopmostvaluesxandyfromthestack 2. computethevalueoff(x,y)
3. pushresultontostack
unary operations are similar, but with x and f(x)
Impact: operands are replaced with the result of the operation
All arithmetic and Boolean operations implemented this way (add, sub, gt, neg, not…ALU ops)
Review of Stacks
The stack machine
• Arithmetic/logical commands • Memory segment commands • Branching commands
• Function commands
high level program
compiler
VM code
target hardware
Stack machine manipulated by:
VM implementation
Our VM Language
Program flow commands
label (declaration)
goto (label)
if-goto (label) Next
week
function (declaration) call (a function) return (from a function)
Function calling commands
Arithmetic / Boolean commands
add
sub
neg
eq
gt
lt
and
or
not
Memory access commands
pop segment i push segmenti
Today
Your task: implement this on the Hack platform
DataTypes
Single 16-bit data type that can be used as: • integer: -32,768 to 32,767
• boolean: 0 (false) or -1 (true)
• pointer: 0 to 24k
High level: x = 17 + 19 compile VM level: push 17 push 19
add pop x
High level language is an abstraction implemented by the stack machine
The stack machine is an abstraction implemented by what we are working on today
add
worksheet: sub
worksheet: neg
worksheet: gt
Memory access overview: push
before
after
LIFO
Memory access overview: pop
before
after
LIFO
Arithmetic Computation
Boolean Evaluation
Arithmetic & Boolean Commands
Memory Access
Modern programming languages have different kinds of variables:
•
static variables
• •
• •
Class level
•
field variables (object properties) Method level:
local variables argument variables
Our VM
Uses virtual memory segments:
local, argument this, that,
pinter, temp, static, constant
At the VM level there’s no need to differentiate among the different roles of these segments; that’s the compiler’s job. To the VM, as segment is a segment is a segment.
Memory segments and commands
Virtual Memory Segments
● local
● argument ● this
● that
● constant ● static
● pointer
● temp
Memory commands
● push segment i ● pop segment i
Abstract view of segments
Note: In this context, push and pop are relative to the SP not the memory segment (eg. heap)
push to stack (from segment); pop (from stack) to segment
Virtual Machine Implementation on Hack: Memory
Source code (Jack)
class Foo {
static int s1, s2;
function int bar (int x, int y) {
Compiled VM Code
…
push static 0
…
push argument 1
} pop local 2 }…
var int a, b, c; …… let c = s1 + y; add ……
Memory segments pop
push
syntax: push / pop segment i
examples:
•push constant 17
•pop local 2
•push argument 3
•pop static 5
•…
Virtual Machine Implementation on Hack: Memory
The challenge:
1. map the VM constructs onto the host RAM
2. given this mapping, figure out how to implement each VM command using assembly commands that operate on the RAM
Virtual Machine
Implementation
on Hack: Memory
local, argument, Mapped on the stack.
this, that
Mapped on the heap.
The base address of these segments are kept in LCL, ARG, THIS, THAT.
Access to the i-th entry of a segment is implemented by accessing the segment’s (base + i) word in RAM.
Virtual Machine
Implementation
on Hack: Memory
static
Static variable number j in VM file f is implemented by the assembly language symbol f.j
Example: in file Ball, static 2 would be referred to in the assembly language as ball.2
The assembler maps such symbols to RAM starting from address 16.
Virtual Machine Implementation on Hack: Memory
constant
Truly a virtual segment.
Access to constant i is implemented by supplying the constant i
Virtual Machine Implementation on Hack: Memory
pointer
Used to align this and that with memory blocks on the heap
Implementation
SimpleAdd.vm example push constant 7
push constant 10
add
Suggested Implementation: Parser
Suggested Implementation: CodeWriter
Implementation
Before fingers hit keyboard:
● Know assembly
● Build generic assembly sequences for all VM commands
Conventions:
● VM files (xxx.vm) will contain sets of functions
● Functions within the same VM file will share a static variables (xxx.j) but have
unique argument, local, this, that and pointer segments (virtual segments)
● temp and constant segments are shared
● Each static variable j in VM file xxx.vm is translated into assembly symbol xxx.j.
The subsequent assembly process will be allocated RAM for these (you already
built that)
● Each label b command in a VM function f should generate a globally unique
symbol “f.b” where f is the function name and b is the label symbol within the VM function’s code. When translating to goto b, and if-goto b VM commands into the target language, the full label f.b must be used instead of b
● Each VM function f should generate a symbol “f” that refers to its entry point in the instruction memory of the target computer
● return-address: a unique label, this identifies the place in the target platform’s memory of the command following a function call