diff options
| Commit | 002c541a9cdc84895a3459189270773d885e3e19 (patch) | |
|---|---|---|
| Author | 2018-11-17 15:30:41 +0200 | |
| Committer | 2018-11-17 15:30:41 +0200 | |
| Files | 3377835dd9a402ad94c66d116cf0126633956be2 | |
| IPL-002c541a9cdc84895a3459189270773d885e3e19.tar IPL-002c541a9cdc84895a3459189270773d885e3e19.tar.gz IPL-002c541a9cdc84895a3459189270773d885e3e19.zip | ||
| Parent | a2c53c44ff31d40030d45f9ce346413cd8fb815e (diff) | |
Slides/vm intro (#40)
* Started vm intro slides
* Added slides for machines
* finished vm intro slides
* Fixed warnings on Linux
* Added the slides to the contents
3 files changed, 428 insertions, 0 deletions
| -rw-r--r-- | JSImpl/test/empty.cpp | 57 | ||||
| -rw-r--r-- | website/content/post/contents.md | 3 | ||||
| -rw-r--r-- | website/content/slides/05_vm_intro/_index.md | 368 |
diff --git a/JSImpl/test/empty.cpp b/JSImpl/test/empty.cpp index 53d601d..2787b00 100644 --- a/JSImpl/test/empty.cpp +++ b/JSImpl/test/empty.cpp @@ -3,3 +3,60 @@ TEST(Empty, Empty) { } + +int get_op(int8_t *& PC) { + return *(PC++); +} +size_t get_arg(int8_t*& PC, int size) { + switch (size) { + case 0: + return *(PC++); + case 1: + return *(((unsigned short*&)PC)++); + case 2: + return *(((unsigned int*&)PC)++); + case 3: + return *(((size_t*&)PC)++); + } + return 0; +} + + +TEST(Pointer, byte) +{ + int8_t data[] = { 42, 0 }; + int8_t* PC = data; + ASSERT_EQ(42, get_op(PC)); + ASSERT_EQ(data + 1, PC); +} + +TEST(Pointer, int16) +{ + int8_t data[] = { 1, 42, 0, 3}; + int8_t* PC = data; + get_op(PC); + ASSERT_EQ(42U, get_arg(PC, 1)); + ASSERT_EQ(data + 3, PC); +} + +TEST(Pointer, int32) +{ + int8_t data[] = { 1, 42, 0, 3, 0, 1 }; + int8_t* PC = data; + get_op(PC); + ASSERT_EQ(0x0003002aU, get_arg(PC, 2)); + ASSERT_EQ(data + 5, PC); +} + + +TEST(Pointer, int64) +{ + int8_t data[] = { 1, 42, 0, 3, 0, 1, 0, 0, 0 }; + int8_t* PC = data; + get_op(PC); + ASSERT_EQ(0x010003002aU, get_arg(PC, 3)); + ASSERT_EQ(data + 9, PC); +} + + + diff --git a/website/content/post/contents.md b/website/content/post/contents.md index ec568e8..902caa9 100644 --- a/website/content/post/contents.md +++ b/website/content/post/contents.md @@ -22,3 +22,6 @@ Table of contents for the course. 0. Parser generators - [slides]({{< ref "/slides/04_parser_generators" >}}), [doc](https://github.com/SofiaCPP/IPL/blob/master/website/content/slides/04_parser_generators/_index.md) + +0. Intro to virtual machines - [slides]({{< ref "/slides/05_vm_intro" >}}), + [doc](https://github.com/SofiaCPP/IPL/blob/master/website/content/slides/05_vm_intro/_index.md) diff --git a/website/content/slides/05_vm_intro/_index.md b/website/content/slides/05_vm_intro/_index.md new file mode 100644 index 0000000..5ee5e73 --- /dev/null +++ b/website/content/slides/05_vm_intro/_index.md @@ -0,0 +1,368 @@ +--- +title: "Introduction to Virtual Machines" +date: 2018-11-07T17:45:53+03:00 +draft: false +outputs: ["Reveal"] +--- + +# Virtual Machines - Wikipedia + +> In computing, a virtual machine (VM) is an emulation of a computer system. +> Virtual machines are based on computer architectures and provide functionality +> of a physical computer. + +--- +# Virtual Machines - Wikipedia + +- system virtual machines - provide substitute for a real machine +- process virtual machines - allow executing of computer programs in a platform + independent environment + +> We will be looking only at the second type of virtual machines and VM will +> mean that for us. + +--- +# Virtual Machines + +- Implement a computational model +- Just like real machines AKA computers +- run on top of the real machine + +--- + +## Computational model + +- Regular Languages +- Context Free Languages +- *Everything that is computable* + +--- +## Computational model + +- Regular Expressions +- Pushdown automata +- Turing machines + +--- +### Turing machine + +- has infinite tape with cells +- each cells can hold one of finite number of values +- head that can read, write and move to the left and right +- finite set of states, one designated as starting state +- finite program that given (state, value) return the new (state, action, value) + +--- +### Turing machine operation + +1. starts with the initial state +2. Read the value at the head position +3. look up (state, value) in the table - if missing *HALT* +4. Set state to *new state*, write *new value* at the head position and move the + head left or right +5. Go to 2 + +--- +## From theory to practice + +- Infinite tapes are expensive +- Not great user experience to interact via checking the cells on the tape + +--- +Still computers and VMs are an implementations of Turing machines. + +The tape is not infinite :/ + +- less powerful +- we have to reuse the tape + +--- +### What is inside a machine + +1. Processor - implements the machine running algorithm + - reads, writes to the tape, moves the head and changes the current state +2. Memory - the tape, consists of cells of variable sizes filled with 0 and 1 + - almost always random accessible +3. Program - the state transition function/table + - resides in the memory - von Neumann architecture +4. Program Counter (PC) - the current state + +{{% note %}} + +All the fancy output like sound and graphics is writting at dedicated addresses +in memory. + +So to writting something on the screen, used to be write the bytes in +0xF000-0xFFFF and the hardware will just blit them on the screen. +Playing a sound - set some address to the frequency of the tone. + + +{{% /note %}} + +--- +#### How the machine works? + +1. Reads the instruction at PC +2. Decodes the instruction at PC +3. Modifies the memory according to the instruction +4. Moves PC to the next instruction +5. Go to 1 + +--- +### Instructions + +- CISC - Complex Instruction Set Computer + - one instruction can do a lot of operations +- RISC - Reduced Instruction Set Computer +- Register Memory - most operations can use both - registers and memory + addresses +- Register Register - most operations take place only between registers and + there are dedicated instructions that allow loading and storing data in memory + +--- +### Instructions + +- x86 - CISC, Register Memory + - the CPU actually runs microcode that is RISC ... +- ARM - RISC, Register Register + +--- +### Instructions + +- transfer data between registers and memory +- add, substract, multiply, divide values +- boolean operations on values +- change the PC +- call a subroutine + +--- +### Subroutines + +- not required by Turing machines +- but very useful, that are part of every machine + +- Stack for storing return addresses (at least) +- Stack Pointer (SP) + +--- +### "Real" vs Virtual Machine + +- the "real" machine is implemented in the hardware +- the operations of the machine are mapped 1:1 to the hardware actions +- these statements used to be true, not any more + +{{% note %}} +Out-of-order execution, branch prediction -> meltdown, spectre show that our +"machine" code runs on a virtual machine. +{{% /note %}} + +--- +## Virtual machines + +- Stack based +- Register based + +--- +### Stack based VM + +- all operations work with arguments on the stack + - operands are popped from the stack + - the result is pushed on the stack + +--- + + read // from input to top of stack + dup + loop: + push 1 + sub + dup + push 0 + jmpeq end + swap + dup -1 + add + swap + jmp loop + end: + pop + print // pop result and print + +--- + +- the instructions are smaller and the code is compact +- more code is required + +--- +### Register based VM + +- operations can work with registers + +--- + + read 0 + move 1, 0 + loop: + sub 0, 0, #1 + cmp 0, #0 + jmp end + add 1, 1, 0 + jmp loop + end: + print 1 + +--- + +- less code +- the instructions have arguments and can be larger + +--- + +#### Typing + +VMs can be statically or dynamically typed + +- certain registers / memory locations / instructios can work only on certain + argument types. + +--- +### From VM to a interpreter + +Implementing everything at the VM level would be too hard + +- interpreter = VM + runtime +- VM - control logic and computations +- runtime - language features and standard library + +--- +### Course future + +1. Implement a register based VM that works with numbers +2. Implement a runtime + 1. Strings + 2. Objects + 3. Arrays + 4. Functions + 5. Garbage Collector +3. Make JSImpl generate code for the VM + +--- +## Implementing a VM + +- register based +- still needs a stack for argument passing and keeping local variables + +--- +### Instruction set + +- choosing an instruction set is difficult + - performance + - speed + - energy consumption + - how easy it is to target that instruction set + +--- + +Fixed size instructions vs variable length instructions: + +- fixed size is easier to decode, but imposes restrictions and can be wasteful + +--- +### Instruction set + +We'll be doing varible length instructions + +> The instruction set is subject to change, so do not start the press (yet!). + +--- +### Instruction set + +Instructions will be between 1 and 25 bytes. + +- 6 bits for OpCode - we have up to 64 opcodes +- 2 bits - n - length of the arguments + - 2^n bytes per agrument + +--- +### Instruction set + +https://docs.google.com/spreadsheets/d/1Q90x60BF-7T0jqPngScsjlaGBXXHRx4tszwCTSRYUrA/edit?usp=sharing + +--- +### Calling convention + +1. push arguments on stack +2. call function +3. callee can access arguments from the stack with regiters + - 0 - count of arguments + - -1 - first argument + - -n - n-th argument +4. caller calls `ret reg`, which removes all locals and arguments and leaves + `reg` on top of the stack +5. caller pops the result from the stack + +--- +### How a program looks? + + function add_answer(x) { + return x + 42; + } + +--- + + func add + const 42 // goes to register 2 + add 2, -1, 2 + ret 2 + +--- +### Interpreter loop + +1. read the next instruction +2. decode the opcode and arguments + - move PC to the next instruction +3. execute the operation +4. go to 1 + +--- + + while (1) { + auto instruction = get_op(PC); + switch (instruction & 0x3F) { + case ADD: { + const auto size = (instruction >> 6); + const auto arg0 = get_arg(PC, size); + const auto arg1 = get_arg(PC, size); + const auto arg2 = get_arg(PC, size); + m_Stack[arg0] = m_Stack[arg1] + m_Stack[arg2]; + } + // ... + } + } + +--- + + int get_op(byte*& PC) { + return *(PC++); + } + size_t get_arg(byte*& PC, int size) { + switch (size) { + case 0: + return *(PC++); + case 1: + return *(((unsigned short*&)PC)++); + case 2: + return *(((unsigned int*&)PC)++); + case 3: + return *(((size_t*)PC&)++); + } + } + +--- +# Homework + +- implement a brainfuck interpreter +- implement a gcd in spasm + +--- +# ? |
