r1.dvi

Size: px

Start display at page:

Download "r1.dvi"

ぜんぺいふじがわ
5 years ago
Views:

1 / 1 / 2 / 3 Lisp 4 5 ( ) 1 (5 1 ) ? 0 1 (bit sequence) (binary system)

2 ( ) ( )? ( 1) r r r3 1: (memory) (address) CPU (instruction) 1 1 (program) (stored program) (Neuman architecture) 1.2 CPU ( ) JavaScript ( 2) ( (code) ) 1 : : 2

3 2: load X add Y store Z stop X: 3 Y: 5 Z: 0 load ( X ) (Acc) add ( Y ) Acc store ( Z ) 2 Acc 1 stop X Y Z X Y (8 ) Z (assembly language) (assembler) 0 1 CPU CPU (machine language) 3

4 2 ( ) 4 ( ) Acc 0 ( ) X Y Z X Y Y load X store Z sub Y ifp Skip load Y store Z Skip: stop X: 3 Y: 5 Z: 0 sub X Acc Z Acc Y X OK Skip (ifp Acc ) 1 Y Acc Z Skip ( ) 1 a. 5 A B C D E Z : 1, 2, 3, 4, 5 15 (16 F) b. A 5 Z : 4 20 (16 14) c. 3 A B C 3 Z : 3, 6, (low level language) CPU 4

5 ? A B C Acc 1 (Idx) load loadx Idx iload 0 Loop: loadx Data ifz End add Sum store Sum iadd 1 jump Loop End: stop Sum: 0 Data: Data iload Idx ( 0) load Acc Idx 0 Data 0 ( 0 ) End Acc Sum iadd Idx 1 jump Loop Data 0 End Sum ( 1) ( ) a. (0 ) : : 15 b. 2 ( 0 ) 2 ( ) : 3 5 : 15 c. (0 ) : : -2 3 ifz zero ifnz not zero ifp positive ifn negative 4 2 (add sub mul load) 2 5

6 1: nop 00,01 stop 02,03 load 04,05 Acc loadx 06,07 ( / Idx ) store 08,09 Acc storex 0a,0b ( Idx ) add 0c,0d Acc sub 0e,0f Acc iload 10,11 Idx iadd 12,13 Idx isub 14,15 Idx ifz 16,17 Acc 0 ifnz 18,19 Acc 0 ifp 1a,1b Acc 0 ifn 1c,1d Acc 0 jump 1e,1f neg 20,21 Acc 1.4 CPU CPU (1 100 ) CPU? 10G( ) AMD64 ( ).globl main main: movl loop: subl jg ret $ , %eax $1, %eax loop.globl main main movl %rax 1G( ) 2 subl 1 3 jg 0 loop subl jg 1G ret ( Unix ) test.s ( Emacs ).s ( % ) % gcc test.s ( ) % time./a.out real 0m0.511s user 0m0.504s CPU 6

7 sys % 0m0.001s 0.5 2G(20 ) CPU 1 4G(40 ) = CPU? ( ) VLSI (digital revolution) 1-3 gcc 1 ( ) a. CPU 1 b. 2 ( 2 ) c. (%eax) subq.globl main main: movl loop: subl jg ret.data mem:.long 0 $ , mem $1, mem loop 1.5 : AMD64 AMD64 Acc Idx 2 7

8 AMD ( ) 3 rax ax ah al eax ah ch dh bh al cl dl bl ax cx dx bx sp bp si di eax ecx edx ebx esp ebp esi edi r8d rax rcx rcx rcx rsp rbp rsi rdi r8 r15d r15 3: AMD64 AMD64 ( ) (%rsp) (%rbp) ( ) CPU (high leve languages) 5 C #include <stdio.h> int main() { int x, y; printf("x> "); scanf("%d", &x); printf("y> "); scanf("%d", &y); while(x!= y) { if(x > y) { x = x - y; else { y = y - x; printf("%d\n", x); 1-4? 5 CPU 8

9 CPU CPU ( ) CPU ( ) CPU CPU CPU CPU while if ( 4) while(x!= y) { BODY cmpl... je.lx.ly BODY if(x > y) { BODY1 else { BODY2 cmpl... jl.lx BODY1 jmp.ly jmp.ly.lx.lx BODY2.Ly 4: C 1-5 C a. else if do-while switch b. c. C 2.2 CPU? (C Java )? ( ) 9

10 1-6 C ( ) a. b. 2 c CPU call ( ) ret 2 5 call call ret ret.addr. stack %rsp larger address (AMD64) 5: call ret call 8 ( ) ret 4 ( ) AMD ( ) ( 6) 6 call ret 6 OS 10

11 adjust sp after call chain bp new frame rsp before call ret.addr ret.addr rbp rsp ret.addr rbp lower frame rsp rbp lower frame rsp rbp lower frame lower frame return restore bp restore sp 6: call/ret sub: pushq %rbp %rbp movq %rsp, %rbp %rbp %rsp subq $, %rsp %rsp ( ) addq $, %rsp %rsp popq %rbp %rbp ret / 2.4 ( ) IA32(32 ) AMD64 ( ) %rdi / %edi 1 %rsi / %esi 2 %rdx / %edx 3 %rcx / %ecx 4 %rax / %eax 2 addasm().globl addasm addasm: movq %rdi,%rax addq %rsi,%rax ret 1 %rax( ) 2 7 / main

12 #include <stdio.h> int addasm(); main() { printf("%d\n", addasm(5, 3)); (C ) a. (rorl) (roll) C b. ( ) c. b setjmp/longjmp 3.1 asm gcc asm asm directive C #include <stdio.h> sub1(int x) { printf("sub1. %d\n", x); //asm("jmp tmp"); sub2(int y) { //asm("tmp:"); printf("sub2. %d\n", y); main() { sub1(99); printf("main.\n"); sub2(88); return 0; asm ( ) sub1. 99 main. sub2. 88? ( ) 12

13 sub1. 99 sub2. 99 main. sub2. 88? gcc -S :-) A B C D call A return call A D %rsp call B C return call B C global goto ret.addr C ret.addr B global exit stack unwinding call D return call D ret.addr A A %rsp nomal exit global exit current: D current: A 7: (D) (A) ( 7 ) C++ Java C D A (?) ( ) A ( 7 ) (1)A (2) C (1) setjmp (2) longjmp #include <stdio.h> #include <setjmp.h> 13

14 jmp_buf buf; sub2() { printf("sub2.\n"); longjmp(buf, 1); sub1() { printf("sub1 entry.\n"); sub2(); printf("sub1 exit.\n"); main() { printf("main entry.\n"); if(setjmp(buf) == 0) { sub1(); printf("main exit.\n"); setjmp.h buf setjmp longjmp? setjmp setjmp setjmp 0 setjmp 0 0 main entry. sub1 entry. sub2. main exit. sub1 exit. sub2 main setjmp 0 longjmp 2 0 (0 1 ) setjmp setjmp/longjmp main longjmp sub2 setjmp main longjmp 1-9 asm main sub2 main 1-10 setjmp/longjmp 14

15 a. longjmp sub1 b. longjmp main c. sub2 setjmp main longjump d ( ) single thread multithread 8: 1 N 1 1 ( 8 ) 1 ( 8 ) 2 1 CPU( CPU ) 1 CPU( CPU ) CPU ( ) CPU 15

16 ( ) CPU OS ( ) 100 stack[0] stack[1] stack[2] 4096 main buf[0] buf[1] buf[2] use[0] use[1] use[2] cur count 2 9: main 9 setjmp/longjmp buf ( ) 9 cur 8 9 main 16

17 count (main ) #include <stdio.h> #include <setjmp.h> #define MAXTHREAD 100 #define STACKSIZE 4096 int stack[maxthread][stacksize]; jmp_buf buf[maxthread]; int use[maxthread]; int cur = 0, count = 0; call cur use 1 count %eax %esp %ebp call use 0 count use 0 ( ) _call(int (*func)(), int *stk, int id) { cur = id; use[cur] = 1; ++count; asm("movq %rsi,%rsp"); asm("callq *%rdi"); use[cur] = 0; --count; gt_yield(); // NO RETURN gt create 1 use 0 call call gt_create(int (*func)()) { int i; for(i = 0; i < MAXTHREAD; ++i) { if(!use[i]) _call(func, &stack[i][stacksize-16], i); // NO RETURN gt yield setjmp buf ( )cur use 1 ( ) ( ) buf longjump setjmp 1 1 gt yield 10 STACKSIZE 16 (64 ) :-) ( ) 10 17

18 gt_yield() { /*printf("switch from %d ", cur);*/ if(setjmp(buf[cur]) == 0) { do { cur = (cur+1) % MAXTHREAD; while(!use[cur]); /*printf("to %d \n", cur);*/ longjmp(buf[cur], 1); API func func2 1 2 func1() { int i; for(i = 0; i < 10; ++i) { printf("func1 %d\n", i); gt_yield(); func2() { int i; for(i = 0; i < 10; ++i) { printf("func2 %d\n", i); gt_yield(); gt_yield(); main() { printf("main enter.\n"); use[0] = 1; ++count; if(setjmp(buf[0]) == 0) gt_create(func1); if(setjmp(buf[0]) == 0) gt_create(func2); while(count > 1) gt_yield(); printf("main exit.\n"); return 0; main 0 use 1 count 1 2 ( setjmp ) 1 ( ) 1-11 a b. 20 c d. 18

() () (parse tree) ( (( ) * 50) ) ( ( NUM 10 + NUM 30 ) * NUM 50 ) ( * ) ( + ) NUM 50 NUM NUM (abstract syntax tree, AST) ( (( ) * 5

() () (parse tree) ( (( ) * 50) ) ( ( NUM 10 + NUM 30 ) * NUM 50 ) ( * ) ( + ) NUM 50 NUM NUM (abstract syntax tree, AST) ( (( ) * 5 3 lex yacc http://www.cs.info.mie-u.ac.jp/~toshi/lectures/compiler/ 2018 6 1 () () (parse tree) ( ((10 + 30) * 50) ) ( ( NUM 10 + NUM 30 ) * NUM 50 ) ( * ) ( + ) NUM 50 NUM NUM 10 30 (abstract syntax tree,