Lecture 15: LM code from high level language /* Simple Program */ external int get_int(); external void put_int(); int sum; clear_sum() { sum=0; int step=2; main() { register int i; static int count; clear_sum(); count = get_int(); for (i=0; i<count; i+=step) sum += i; put_int(sum); External declarations Uninitialized global variable Initialized global variable Register local variable Static local variable Memory Allocation Stack Heap SS sum: uninitialized global count: uninitialized local static Data 하드디스크에저장된실행파일 step: initialized global 0: constant Text
다음은앞의 source program 을 target code 를 LM 로하여 compile 한것이다. 여기서 MOV 는 LD, ST, MOVE 를합한형태의 mnemonic code 인데 LM 기계어가새로정의된것은아니고단순히 assembly language 차원에서정의된것이다. 이를 <1xx>, <2xx> 등으로번역할수있는 smart assembler 가있다고가정한다. // Simple Program SIMPLE START 0 ETDEF SUM LEARSUM STEP MAIN ETREF GET_INT PUT_INT FIRST MOV SP, #STK_TM We have a smart assembler! ALL MAIN O HEAP RESDO 500 STK_TM EQU $ SUM RESDO 1 int sum; LEARSUM MOV A, =0 MOV SUM, A sum = 0; STEP DO 2 int step=2; MAIN ALL LEARSUM clear_sum(); ALL GET_INT MOV OUNT, A count = get_int(); MOV, =0 register int i; i=0; FORLOOP MOV A, SUM for ( ) ADD A, MOV SUM, A sum += i; ADD, STEP i += step; MOV, OUNT SU, JP FORLOOP i < count MOV A, SUM ALL PUT_INT put_int(sum); OUNT RESDO 1 static int count; END FIRST 이 code 는프로그램과데이터가섞여있으므로메모리를 segment 별로관리하는것을어렵게한다. 따라서
// Simple Program SIMPLE START 0 ETDEF SUM LEARSUM STEP MAIN ETREF GET_INT PUT_INT USE TET // (A) FIRST MOV SP, #STK_TM We have a smart assembler! ALL MAIN O USE DATA USE SS USE STAK // () HEAP RESDO 500 STK_TM EQU $ USE SS // () SUM RESDO 1 int sum; USE TET // (D) LEARSUM MOV A, =0 MOV SUM, A sum=0; USE DATA // (E) STEP DO 2 int step=2; USE TET // (F) MAIN ALL LEARSUM clear_sum(); ALL GET_INT MOV OUNT, A count=getint(); MOV, =0 register int i; i=0; FORLOOP MOV A, SUM for ( ) ADD A, MOV SUM, A sum += i; ADD, STEP i += step; MOV, OUNT SU, JP FORLOOP i < count MOV A, SUM ALL PUT_INT put_int(sum) USE SS // (G) OUNT RESDO 1 static int counter; USE DATA // (H) LTORG END FIRST
After Loading to Memory FIRST LEARSUM MAIN FORLOOP (A) (D) (F) TET STEP (E) =0 (H) SUM () OUNT (G) HEAP DATA SS HDD () STAK STK_TM SP After execution of the first instruction
Static lass Symbol 의 Memory Allocation /* Simple Program 2 */ external int get_int(); external int put_int(); int sum; add_two 는이모듈밖에서는정의되지않는다. static int add_two(int a, int b) { return a+b; step 은이모듈밖에서는정의되지않는다. static int step=2; main() { register int i; ount 는 main 에서만보이는지역 static int count; 변수이지만 main 이끝난후에도값을유지한다. sum=0; count = get_int(); for(i=0; i<count; i+=step) sum = add_two(sum,i); put_int(sum); Global symbol (function, variable) 을 static class 로하면해당 module 안으로 scope 가한정된다. 즉다른 module 에서는이 symbol 의존재를모른다. Local variable 을 static class 로하면 scope 는그대로 local 이지만 life time 은 global variable 과같이프로그램의종료까지연장된다.
Activation Record. P for add_two Return Addr to main sum i P for main Return Addr to FIRST P for first (null) SP P 각함수호출을위한 activation record 는현재의 register 가가리키는곳에서시작한다. 따라서호출된함수를위한 argument 들은바로아래에저장된 Return Address 를감안할때 %4, %6. %8 순으로저장되어있다. %-2, %-4, 등위쪽은 local auto variable 을위한공간이다. 이 auto variable 들은함수가 return 될때 "MOV SP, " 에의해서소멸되어버린다. 그리고 local auto variable 위의공간은 register 를 save 하는등의임시목적으로활용된다. temporary location.. local auto variables.. previous P return address urrent P arguments 각 activation record 의 ase 들은 register 를시작으로하여 linked list 를형성하여함수가 return 된후에돌아갈환경을기억하고있다. 각함수를호출하기전에는그함수를위한 argument 를역순으로 stack 에 push 하여전달하고 return 값은 A register 를통해서전달한다. Return 된후에는 Stack Pointer 를조정하여 push 된 argument 를제거한다.
SIMPLE2 START 0 ETREF GET_INT PUT_INT ETDEF SUM MAIN USE TET FIRST MOV SP, #STK_TM MOV, =0 ALL MAIN O USE DATA USE SS USE STAK HEAP RESDO 100 STK_TM EQU $ USE SS SUM RESDO 1 ADD_TWO 와 STEP 은 static 이므로제외된다. HEAP STK_TM SP ADD_TWO USE TET PUSH MOV, SP PUSH PUSH save registers MOV,%4 get the first argument ADD,%6 get the second argument MOV A, return the result via A register restore registers MOV SP, USE DATA STEP DO 2 각함수에서는시작할때모든 register 를 save 하였다가끝날때다시 restore 함으로서함수안에서 register 의사용을자유롭게한다. 그런데, SP 는 activation record 와관련된특수목적이있고, A 는 return value 를담기로하였으므로, 만 save/restore 하면된다. 함수안에서 A,, SP register 를임시로사용할때는극도로주의가필요하다.
MAIN USE TET PUSH MOV, SP MOV A, =0 MOV SUM, A ALL GET_INT MOV OUNT, A MOV, =0 i=0; FORLOOP PUSH push i MOV A, SUM 함수에서 return 된후 argument 를 push sum 제거하기위한것이다 ALL ADD_TWO ADD SP, =4 adjust SP MOV SUM, A sum = add_two(sum,i); ADD, STEP i+=step; MP, OUNT i - count JN FORLOOP i < count MOV A, SUM ALL PUT_INT ADD SP, =2 adjust SP MOV SP, USE SS OUNT RESDO 1 USE DATA LTORG END FIRST OUNT 는 main 의 local variable 이지만 life time 을연장하기위해서 SS block 으로 allocation 된다.
Local auto variable 의 memory allocation /* Simple Program 2 */ external int get_int(); external int put_int(); int sum; int add_two(int a, int b) { int tmp; tmp = a+b; return tmp; local auto variable stack 영역에자리잡는다. static step=2; main() { register int i; static int count; sum=0; count = get_int(); for(i=0; i<count; i+=step) sum = add_two(sum,i); put_int(sum); 새로운 activation record 를준비한다. SP tmp %-2 P old P Return Addr argument 1 %4 argument 2 %6 urrent activation record USE TET ADD_TWO PUSH SNAP11 MOV, SP SNAP12 SU SP, =2 for the local auto variable tmp SNAP13 PUSH PUSH 사용된 activation record 를제거한다. Argument 는그대로남아있으므로 return 된후 SP 를 adjust 하여제거한다. MOV,%4 get the first argument ADD,%6 get the second argument MOV %-2, store the result to tmp MOV A, %-2 return the result via A register MOV SP, SNAP14 SNAP15 SP P tmp old P Return Addr argument 1 argument 2 another old P %-2 urrent activation record
앞의 ADD_TWO 를다음과같이호출한다면 // x = add_two(1,2); MOV A, =2 push the second argument SNAP1 MOV A, =1 push the first argument SNAP2 ALL ADD_TWO SNAP3 ADD SP, =4 adjust SP to remove arguments SNAP4 At SNAP1 (push the second argument) SP: 2 : RA %-2 %4 At SNAP2 (push the first argument) 1 SP: 2 : RA %-2 %4
At ADD_TWO (after ALL ADD_TWO) ALL 에의해 push 됨 1 SP: 2 : RA %-2 %4 At SNAP11 (after PUSH ) 1 SP: 2 : RA %-2 %4 이전 activation record 를기억하기위함
At SNAP12 (after MOV, SP) 1 %4 SP: 2 %6 activation record 새로형성됨 가 : RA At SNAP13 (after SU SP, =2) %-2 local auto variable tmp 1 %4 새로형성된 activation SP: 2 %6 record 에 local variable 을위한공간을만듬 : RA
At SNAP14 (after MOV SP, ) tmp is removed 1 %4 우선 local variable 들을 SP: 2 %6 제거함 : RA At SNAP15 (after ) 1 SP: 2 : RA %-2 %4 Pop 을통해서이전 activation record 로돌아감아직 return address 와 argument 들은남아있음
At SNAP3 (after ) 1 SP: 2 : RA Return addr is poped %-2 %4 에의해서 이 pop 되므로 SP 가한칸아래를가리킴을주의할것 At SNAP4 (after ADD SP, =4) 1 SP: 2 : RA %-2 %4 Arguments are removed. 최종적으로 argument 들을 stack 에서제거하여 top 에있던 activation record 를완전히제거함
여러가지함수의호출 /* A example of three function calls */ external void put_int(); SP a %-4 b %-2 P Old P RA // argument 는없고 local auto variable 이 2 개 static int func_one() { int a=1; int b=2; return fun_two(a,b,3) + 4; // 3 개의 argument static int func_two(int x, int y, int z) { return func_three(x+y,z)+5; // 2 개의 argumrnt 와 2 개의 local variable int func_three(int x, int y) { int a=6; int b; b = x+y; return a+b; main() { int r; r = func_one(); put_int(r); Local variable a,b 는각각 %-4, %-2 로 reference 된다. P,SP Old P RA x %4 y %6 z %8 Argument x,y,z 는각각 %4,%6,%8 로 reference 된다. SP a %-4 b %-2 P Old P RA x %4 y %6 Argument x,y 는 %4,%6 으로 local variable a,b 는 %-4, %-2 로 reference 된다.
THREE START 0 ETDEF ETREF MAIN FUN_THREE PUT_INT USE TET FIRST MOV SP, #STK_TM MOV, =0 ALL MAIN O USE DATA USE SS USE STAK HEAP RESO 500 STK_TM EQU $ MAIN SNAP1 PUSH MOV, SP SU SP, =2 int r; PUSH PUSH save registers SNAP1-2 ALL FUN_ONE MOV %-2, A r = func_one(); MOV A, %-2 ALL PUT_INT put_print(r); ADD SP, =2 SP %-2 r of main 0 SP 0 FUN_ONE 의 argument 가아니라 temporary location 으로사용한것임 %-2 r of main restore registers MOV SP,
FUN_ONE SNAP2 PUSH MOV, SP SU SP, =4 int a; int b; PUSH PUSH MOV A, =1 MOV %-4, A a=1; MOV A, =2 MOV %-2, A b=2; SP %-4 a of func_one %-2 b of func_one r of main 0 MOV A, =3 push 3 MOV A, %-2 push b MOV A, %-4 push a ALL FUN_TWO RA2 ADD SP, =6 ADD A, =4 MOV SP,
FUN_TWO SNAP3 PUSH MOV, SP PUSH PUSH MOV A, %8 push z MOV A, %4 ADD A, %6 push x+y ALL FUN_THREE RA3 SNAP6 ADD SP, =4 SNAP7 ADD A, =5,SP Old RA2 1(a) %4 x of func_two 2(b) %6 y of func_two 3 %8 z of func_two 1 a of func_one 2 b of func_one Old r of main 0 MOV SP, SP Old RA2 1(a) %4 x of func_two 2(b) %6 y of func_two 3 %8 z of func_two 1 a of func_one 2 b of func_one Old r of main 0 SP 3(x+y) x of func three 3(z) y of func_three Old RA2 1(a) %4 x of func_two 2(b) %6 y of func_two 3 %8 z of func_two 1 a of func_one 2 b of func_one Old r of main 0
FUN_THREE PUSH MOV, SP SU SP, =4 int a; int b; SNAP4 PUSH PUSH SNAP5 MOV A, =6 MOV %-4, A a=6; MOV A, %4 x ADD A, %6 +y MOV %-2, A b = x+y; MOV A, %-4 ADD A, %-2 a+b MOV SP, SP %-4 a of func_three %-2 b of func_three Old RA3 3(x+y) %4 x of func three 3(z) %6 y of func_three Old RA2 1(a) x of func_two 2(b) y of func_two 3 z of func_two 1 a of func_one 2 b of func_one Old r of main 0 USE DATA LTORG END FIRST SP RA3 3(x+y) x of func three 3(z) y of func_three Old RA2 1(a) %4 x of func_two 2(b) %6 y of func_two 3 %8 z of func_two 1 a of func_one 2 b of func_one Old r of main 0
Pointer 의처리및 Recursive Function /* Recursive Function */ external int GET_INT(); external PUT_INT(); int sum; rec_add(int *pcount, int n) { int result; (*pcount)++; if (n==0) return 0; else { result = n + rec_add(pcount, n-1); return result; SP result %-2 P old P RA pcount %4 n %6 Argument pcount, n 은각각 %4, %6 으로 local variable result 는 %-2 로 reference 된다. int count=0; main() { register int n; sum=0; n=get_int(); PUT_INT(rec_add(&count,n)); PUT_INT(count); 이함수가몇번호출되었는지센다
OUNT 0 DATA lock // Recursive Function RE START 0 ETDEF SUM RE_ADD OUNT MAIN ETREF GET_INT PUT_INT USE TET FIRST MOV SP, #STK_TM MOV, =0 ALL MAIN O USE DATA USE SS USE STAK HEAP RESO 500 STK_TM EQU $ USE SS SUM RESDO 1 RE_ADD SNAP2 USE TET PUSH MOV, SP SU SP, =2 PUSH PUSH SP %-2 result of rec_add Old OUNT %4 pcount of rec_add 2(n) %6 n of rec_add 0 The first call of rec add OUNT 1 DATA lock SP %-2 result of rec_add Old RA2 OUNT %4 pcount of rec_add 1(n-1) %6 n of rec_add result of rec_add Old OUNT pcount of rec_add 2(n) n of rec_add 0 The second call of rec_add MOV, %4 MOV A, * ADD A, =1 MOV *, A, (*pcount)++ MOV A, %6 MP A, =0 n==0? JNE ELSE MOV SP, RT_THEN return 0; OUNT 2 DATA lock SP %-2 result of rec_add Old RA2 OUNT %4 pcount of rec_add 0(n-1) %6 n of rec_add result of rec_add Old RA2 OUNT pcount of rec_add 1(n-1) n of rec_add result of rec_add Old OUNT pcount of rec_add 2(n) n of rec_add The third call of rec_add
ELSE SU A, =1 n-1 MOV A, %4 pcount ALL RE_ADD RA2 ADD SP, =4 adjust SP SNAP3 ADD A, %6 n + rec_add(...) MOV %-2, A result = MOV A, %-2 RT_ELSE MOV SP, OUNT 3 DATA lock SP %-2 result of rec_add Old RA2 OUNT %4 pcount of rec_add 1(n-1) %6 n of rec_add result of rec_add Old OUNT pcount of rec_add 2(n) n of rec_add 0 A: 0 Return from RT_THEN OUNT 3 DATA lock SP Old OUNT 2(n) 0 %-2 result of rec_add %4 pcount of rec_add %6 n of rec_add A: 1(1+0) Return from RT_ELSE
USE DATA OUNT DO 0 SP 0 USE TET MAIN PUSH MOV, SP OUNT 0 DATA lock SNAP1 PUSH PUSH SP OUNT 2(n) MOV A, =0 MOV SUM, A sum=0; 0 ALL GET_INT n=get_int(); GET_INT() 에서 2 를입력받아 n=2 에서 push n 시작했다면 PUSH #OUNT push &count SNAP1-2 ALL RE_ADD ADD SP, =4 adjust SP (two argument) SNAP4 ALL PUT_INT put_int( ) ADD SP, =2 MOV A, OUNT ALL PUT_INT put_int(count) ADD SP, =2 OUNT 3 DATA lock MOV SP, USE DATA LTORG END FIRST SP 0 A: 3(1+2) Return from RT_ELSE
Array 및 dynamic memory allocation /* A sample program for pointer and malloc*/ external void put_int(); int *TINY_ALLO(int size) { /* see the LM ode */ int *func(int *pcount, int x[]) { int* pa; int d=x[0]; int s=x[1]; SP pa %-6 d %-4 s %-2 P old P Return Addr pcount %4 x %6 x[i] 는 *(x+i) 로 reference 된다. *pcount++; pa = TINY_ALLO(2*s); pa[0] = d; pa[s-1] = d+2; return pa; main() { int *pcount; int a[2]; int *r; pcount = TINY_ALLO(2); *pcount=0; a[0]=1; a[1]=2; r = func(pcount,a); SP pcount %-8 a[0] %-6 a[1] %-4 r %-2 P old P P Return Addr a 는 array a[2] 의시작주소를나타내는데 global variable 과는달리따로 label 이없으므로현재 register 의값을기준으로하여계산해낸다. 즉 () 6 이 int a[2] 의시작주소이다.
POINTER START 0 ETDEF TINY_ALLO MAIN FUN USE TET FIRST MOV SP, #STK_TM MOV, =0 ALL MAIN O USE DATA USE SS USE STAK HEAP DO FREE initialize Heap pointer FREE RESDO 499 STK_TM EQU $ TINY_ALLO PUSH MOV, SP PUSH PUSH MOV A, HEAP return start address of an allocated block MOV, %4 ADD, A HEAP + size MOV HEAP, adjust free pointer for further allocations MOV SP, HEAP Free block Return this address Adjust free pointer SP STK_TM
MAIN SNAP1 PUSH MOV, SP SU SP, =8 PUSH PUSH MOV A, =2 push 2 ALL TINY_ALLO ADD SP, =2 MOV %-8, A pcount = TINY_ALLO(2); SNAP2-1 MOV, %-8 MOV A, =0 MOV *, A *pcount=0; MOV, =0 MOV A, =1 a[0]=1; MOV %@-6, A MOV, =2 DO integer! MOV A, =2 MOV %@-6, A a[1]=2 MOV A, SU A, =6 SNAP2-2 MOV A, %-8 ALL FUN push a push pcount HEAP FREE FREE SP %-8 pcount of main %-6 a[2] of main 0 HEAP H2 H1 0 *pcount H2 %-2 r of main HEAP H2 H1 *pcount H2 SP H1 0 A H1 %-8 pcount of main %-6 a[2] of main %-2 r of main SP 6 a H1 %-8 pcount of main -6 1 %-6 a[2] of main 2 %-2 r of main 0
SNAP6 ADD SP, =4 SNAP7 MOV %-2, A r = func(); SNAP8 MOV SP, HEAP H4 H1 1 *pcount H2 1 pa[0] H3 3 pa[1] H4 SP H1 pcount of func a a of func H1 %-8 pcount of main 1 %-6 a[2] of main 2 %-2 r of main 0 A H2 HEAP H4 H1 1 *pcount H2 1 pa[0] H3 3 pa[1] H4 SP H1 pcount of main 1 a[0] of main 2 a[1] of main H2 r of main 0 HEAP H4 H1 1 *pcount H2 1 pa[0] H3 3 pa[1] H4 SP H1 %-8 pcount of main 1 %-6 a[2] of main 2 %-2 r of main 0 A H2
HEAP H2 H1 0 *pcount H2 FUN SNAP3 PUSH MOV, SP SU SP, =6 PUSH PUSH MOV, %6 MOV A, * MOV %-4A d=x[0]; ADD, =2 DO integer! MOV A, * MOV %-2A s=x[1]; MOV, %4 MOV A, * ADD A, =1 MOV *, A *pcount++; SP %-6 pa of func %-4 d of func %-2 s of func Old H1 %4 pcount of func a %6 a of func H1 pcount of main 1 a[0] of main 2 a[1] of main r of main 0 HEAP H4 H1 1 *pcount H2 pa[0] H3 pa[1] H4 MOV A, %-2 ADD A, A 2 * s push 2*s ALL TINY_ALLO ADD SP, =2 MOV %-6, A pa= SNAP4 MOV A, %-4 MOV, %-6 MOV *, A pa[0]=d; ADD A, =2 d+2 ADD, %-2 ADD, %-2 pa+2*s SU, =2 pa+2(s-1) MOV *, A pa[s-1]=d+2; MOV A, %-6 return pa SP H2 %-6 pa of func 1 %-4 d of func 2 %-2 s of func Old H1 a %4 pcount of func %6 a of func H1 pcount of main 1 a[0] of main 2 a[1] of main r of main 0 SNAP5 MOV SP, USE DATA LTORG END FIRST HEAP H4 H1 1 *pcount H2 1 pa[0] H3 3 pa[1] H4 SP H1 pcount of func a a of func H1 %-8 pcount of main 1 %-6 a[2] of main 2 %-2 r of main 0