계산식 나무로 만들기
초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.
16비트 덧셈 글에서는 a + b처럼 연산이 하나인 식을
옮겼습니다. short c = a - b + 1;처럼 연산이 여럿 섞인 줄은 어떤 명령어로
옮기면 될까요?
a - b + 1처럼 값과 연산을 엮은 것을 식(expression)이라 합니다. 컴파일러는
식을 트리(tree)로 바꿉니다. +나 - 같은 연산이 노드가 되고, 그 연산의
왼쪽 값과 오른쪽 값이 자식이 됩니다. 괄호로 묶은 부분은 서브트리 하나가 됩니다.
괄호를 넣어 a - (b + 1)로 바꿔 봅시다.
short c = a - b + 1;을 맨 아래부터 계산해 봅시다.
ADDI R0, 1과 ADCI R1, 0입니다. 위 8비트에는 올림만 보탭니다.식 끝의 1을 d로 바꿔 봅시다. ADDI·ADCI가 LOAD·ADD·LOAD·ADC 네 줄이 됩니다.
레지스터 넷으로는 값을 둘(R1:R0, R3:R2)만 들 수 있습니다. 왼쪽 자식은 부모와 같은 짝에 둡니다. 오른쪽 자식을 계산하는 동안 왼쪽 값을 들고 있어야 하니 오른쪽 자식은 다음 짝을 씁니다.
트리 옆의 R1:R0, R3:R2가 그 값이 놓일 레지스터입니다. 괄호 안을 계산하는 동안 R3:R2를 씁니다.
a - (b - c)에서는 a가 R1:R0에서, b가 R3:R2에서 기다리니 c를 가져올 레지스터가
없습니다.
R1을 메모리의 임시 칸 tmp1에 내려놓고, 빈 R1로 c를 가져와 b에서 뺀 뒤 tmp1을 다시 R1로 가져옵니다. 이렇게 레지스터 값을 메모리에 내려놓는 것을 스필(spill)이라 합니다.
명령어에서 R1을 tmp1에 내려놓고 다시 가져오는 두 줄을 찾아봅시다.
다음 글에서는 자주 쓰는 변수를 레지스터에 두어 메모리를 덜 오가게 해 주는 레지스터 할당을 살펴봅시다.
다음 식을 이 글의 컴파일러로 옮길 때 스필이 생기는 것은?