Website Summary Files Commits Branches @commit @diff @stats
diff options
context:
space:
mode:
Commit002c541a9cdc84895a3459189270773d885e3e19 (patch)
Author
 dtrendafilov <trendafilov.dn@gmail.com>
2018-11-17 15:30:41 +0200
Committer
 GitHub <noreply@github.com>
2018-11-17 15:30:41 +0200
Files3377835dd9a402ad94c66d116cf0126633956be2
IPL-002c541a9cdc84895a3459189270773d885e3e19.tar
IPL-002c541a9cdc84895a3459189270773d885e3e19.tar.gz
IPL-002c541a9cdc84895a3459189270773d885e3e19.zip
Parenta2c53c44ff31d40030d45f9ce346413cd8fb815e (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.cpp57
-rw-r--r--website/content/post/contents.md3
-rw-r--r--website/content/slides/05_vm_intro/_index.md368
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
+
+---
+# ?