Compiler 8 - Code Generation

 Memory layout
상기한 배열과 Activation record 등은 그렇다면 어떻게 메모리에 저장될까.
메모리 영역은 code와 data를 저장하는 곳으로 크게 구분할 수 있다. data 영역은 다시 global variable, activation record, dynamically allocated data 등을 저장하는 곳으로 나누어진다.

이 때, global variable은 모든 함수에서 접근 가능해야 하므로 임의의 함수의 activation record에 포함되면 안된다. (왜냐하면 실행 완료된 함수의 AR은 stack에서 pop되므로 해당 변수를 더 이상 접근할 수 없게 되므로)
따라서 global data들은 code의 바로 위 statically allocated space에 저장된다.

AR의 경우, 앞서 배운 것 처럼 stack에 저장되며 high to low memory address로 grow한다. 따라서 activation record를 위한 stack은 할당받은 가장 높은 메모리 주소부터 시작해 낮은 주소로 쌓아진다.

마지막으로 dynamically allocated data는 컴파일 시간이 아니라 런타임 중에 메모리가 할당되는 것들이다. 따라서 컴파일러는 이들 변수의 크기를 알 수 없으므로 AR에 포함할 수 없다. 또한 사용자가 할당한 메모리 공간은 free하기 전까지 다른 scope까지 유지될 수 있다. 그래서 이는 stack과 반대로 global data의 바로 위부터 heap으로 설정하여 low to high로 쌓아가진다.
stack과 heap이 겹치게 되면(overlapped), 중대한 오류가 발생하고 stack overflow 에러가 발생하게 된다.

컴파일러는 이런 runtime environment와 intermediate representation instruction을 assembly language로 변환하게 된다. (code generation) - MIPS assembly

MIPS(look back of CA)
memory load / store, arithmetic instruction using register as operand 등으로 구성되어 있다. 따라서 레지스터는 메모리에 저장된 값을 가져와 CPU의 연산을 하는 장소가 된다. 해당 연산 값은 다시 메모리에 저장되게 된다.
메모리 레이아웃은 컴파일 때 모두 결정되므로 register 연산에서 메모리의 어디를 봐야 원하는 데이터를 가져올 수 있는지 알 수 있다. (저장할 때도 마찬가지)

lw $r1 offset($r2)
sw $r1 offset($r2)
r2의 주소에서 offset만큼 떨어진 곳의 메모리 주소에 저장된 값을 r1에 가져옴/ r1의 값을 해당 주소에 저장. (r2는 base address라 한다.)

add $r1 $r2 $r3 // $r1=$r2+$r3
mul, div, sub....

seq $r1 $r2 $r3 // $r1 = ($r2 == $r3) , set equal
sne(set not equal), sgt(set greater than) ,sge, slt, sle ....

li $r1 immediate // $r1 = immediate (some constant number)
addi $r1 $r2 immediate // $r1 = $r2 + immediate
subi, multi ... seqi, slti ..... (모두 immediate value와 비교, 연산)

이런 기초적인 어셈블리 연산을 통해 우리는 HLL를 LLL로 변환할 수 있다.
예를 들어 a=b+c라는 라인이 있다면, 해당 라인을 실행하고 있는 함수의 AR이 stack의 top에 있을 것이고, stack pointer $sp가 해당 stack의 top을 가리키고 있을 것이다. 따라서 각 변수의 offset을 안다면, $sp+offset을 통해 해당 메모리 주소에 접근할 수 있고 이들을 레지스터로 가져와 연산하고 다시 저장하면 된다. (왜냐하면 AR의 structure는 모두 컴파일 때 결정되었으므로 각 변수에 대한 offset을 모두 알고 있다) 이런 과정을 통해 assembly language로 동일한 연산을 나타낼 수 있다.
code에는 while, if, goto와 같은 conditional branch instruction도 필요하다.

j label // goto label
beq $r1 $r2 lable // $r1 == $r2 라면 goto label
bne, bgt, bge, blt, ble ....
beqz $r1 label // if $r1 ==0 goto label
beqi $r1 immediate label // if $r1 ==0 goto label

이들을 통해 조건이 포함된 TAC를 assembly로 변환할 수 있다.

function calls, constructing AR
함수 호출의 경우, return 값을 저장하고 parameter를 저장하고 control link(caller function의 AR의 start address)를 연결하는 작업이 필요하다. 각각에 대해 stack pointer를 4byte씩 아래로 내려주어야 한다. (stack은 아래로 자라므로 따라서 subi $sp $sp 4가 각 단계마다 삽입되어야 한다.)
그리고 $ra 에 저장되어 있는 return address(리턴 값이 저장된 곳)와 함수 내부의 local variable의 공간까지 할당해주고 나면 이를 통해 함수의 AR이 stack에 푸쉬되게 된다.

그리고 해당 함수의 AR을 하여 결과를 얻고 나면, $sp는 다시 이전 함수의 top을 가리키고(진행을 완료한 함수의 AR pop) $ra 등 machine status를 회복하고 return address로 가서 원래 하던 일을 계속 진행하게 된다.

그러나 이런 방식으로 TAC를 assembly로 변환하게 되면 유한한 컴퓨터 자원을 지나치게 낭비하게 된다. (필요 없는 레지스터의 복사 등) 따라서 이들은 better register allocation을 통해 개선할 수 있다.

어쨋든 가장 중요한 것은 runtime environment를 compile time에 얻고, 이를 바탕으로 AR을 구축하고 런타임에 프로그램을 실행할 수 있다는 것이다.