7-1. Virtual Machine I : Stack Arithmetic - [밑바닥부터 만드는 컴퓨팅 시스템]

이 장의 목표는 객체지향 고수준 언어의 컴파일러_compiler를 만드는 것을 준비하는 것이다!
고수준의 프로그램을 중간 코드(10-11장)로 만들고, 중간 코드를 기계어로 번역(7-8장)한다. 이는 70s에 등장한 오래된 개념이지만, C#과 Java같은 언어에 채택되어 현재까지도 사용되고 있다.

기본개념

플랫폼이 아닌 가상머신(VM)에서 실행가능한 중간코드를 만드는 것이다. VM은 컴퓨터상에서 구현가능한 추상적인 컴퓨터이다. 이를 통해 코드 이동성_code transportability를 확보할 수 있다. (동일한 코드를 수정하지 않거나, 약간의 수정만으로도 여러 플랫폼이나 환경에서 이용이 가능한 상태) VM구현에는 SW인터프리터, 특수목적 HW, VM프로그램으로 특정 플랫폼 기계어로 번역 등이 있다.

자바 가상 머신 (JVM; java virtual machine)을 모델로, 일반적인 VM 아키텍처를 공부해보고 구현해보자. VM 모델에는 VM프로그램 작성용 언어인 VM 모델이 있다. 우리가 고우할 VM언어는 4가지 종류의 명령으로 구성되어 있다. 산술, 메모리접근, 흐름제어, 서브루틴 호출. 이를 2개의 장으로 나누어 공부해보자.

7장에서는 산술과 메모리접근을 기계어로 번역하는 기본 VM 번역기를 만들고, 8장에서 흐름제어나 서브루틴 호출 기능을 추가한다. 이는 10-11장에서 만들 컴파일러의 백엔드_backend가 될 것이다.

VM은 1930s의 엘런튜링에서부터 전해지는 Computer Science의 기본개념이다. 하위코드 호환성, 자바 아키텍쳐, .Net 프레임워크 모두가 VM의 실용적인 예시이다. 간단한 VM을 만들어보며 내부구조를 이해해보자.

이 장에서 또한 스택 처리_stack processing에 대해 공부해보자. 매우 다용도의 스택 데이터 구조 활용 예를 살펴볼 수 있을 것이다.

배경

가상머신 패러다임

고수준의 언어가 컴퓨터에서 실행되려면 기계어로 번역하는 컴파일_compilation 과정을 거쳐야한다. 다양한 언어는 그에 대응하는 컴파일러를 각각 가져야 한다.
기계종속성을 없애기위해 컴파일러는 2가지 동작을 한다.

1. 고수준의 언어를 분석_parse하여 중간처리단계로 번역한다.
2. 중간 처리 단계를 대상 HW의 기계어로 번역한다.
   파스칼의 P_Code, JVM의 bytecode, .Net의 CLR에서 실행되는 intermediate language가 그 예시이다.
   VM언어의 개념은 아래와 같은 장점을 가진다.

• VM의 구현부를 수정하면 여러 플랫폼의 컴파일러를 쉽게 개발하여 효율적이다.
• 여러 컴파일러와 같은 VM 백엔드를 공유하여 코드공유 및 상호운용이 쉬워진다.
• 모듈성 덕에 VM구현이 개선되면 많은 SW가 동시에 개선될 수 있다.

스택 머신 모델 Stack Machine Model

VM의 언어를 구현하는 방법론은 여러가지가 있다. 이들을 구현하는 핵심기준 중 하나는 "VM연산의 피연산자와 결괏값을 어디에 저장하는가?"이다. 우리는 JVM과 같은 방식인스택 데이터구조에 저장하는 방식인스택머신모델을 사용할 것이다.

스택머신모델에서 산술명령은 스택의 top에서 피연산자를 pop하고 그 결과를 top에 다시 push한다. 다른 명령은 top과 지정된 메모리주소 사이에 데이터가 이동된다. 이 스택을 통해 산술/논리연산이 가능하고, 어떤 프로그래밍 언어로 작성해도 동일한 작동을 하도록 번역이 가능하다.

기본 스택연산

스택은 Push와 Pop을 기본연산으로 삼는 추상 데이터구조이다. Push를 통해 1개의 데이터원소가 스택의 최상단에 추가되고, 원래 최상단에 있던 원소는 새로 추가된 원소 아래에 위치한다. Pop은 스택의 최상단에 위치한 데이터 1개를 꺼내고 스택에서 삭제하고, 바로 아래에 있던 원소를 최상단에 두는 연산이다. 따라서 스택구조는 후입선출 저장방식_Last In First Out이다.

스택은 기존의 메모리 접근방식과 다르다.

• 값에 접근해 가져와도 데이터가 유지되는 메모리와 달리 Pop을 하면 데이터가 삭제된다.
• 값을 기록하면 기존 데이터를 덮어씌워버리는 메모리와 달리 Push를 하면 기존 데이터를 보존하고 최상단에 값이 추가된다.

스택구조는 1개의 스택배열과 최상단의 원소 바로 위 주소를 가리키는 스택 포인터 SP_stack pointer를 통해 구현한다. Push 명령은 sp의 위치에 값을 저장하고 sp++을 수행한다. Pop 명령은 --sp 명령을 수행하고 sp의 위치의 값을 반환한다.

이 스택모델은 VM의 모든 산술 및 논리연산을 처리하거나 서브루틴 호출 및 메모리 할당에 활용된다.

스택산술 Stack Arithmetic

피연산자를 스택에서 Pop한 뒤, 필요한 연산을 수행하고 결과를 다시 스택에 Push하는 방식으로 간단히 구현된다.

d=(2-x)*(y+5)
push 2 -> push x -> sub(stack의 맨 위 두 값을 sub) -> push y -> push 5 -> add -> mult -> pop d

if(x>7)or(y=8)then
push x -> push 7 -> lt -> push y -> push 8 -> eq -> or (top에 T/F 저장)

고수준의 산술표현식 또는 불 표현식을 스택 명령으로 번역하는 컴파일러를 만들 수 있다. (10-11장!) 이를 위해 명령들의 명세를 정하고 Hack에서 구현해보자.

---

VM명세 1부

이 VM은 스택기반으로 모든 연산이 스택 위에서 이루어진다. 또, 함수기반으로 VM프로그램이 함수(라고 칭해지는 작은 VM프로그램들)로 구성된다.
VM언어는 16Bit 크기의 데이터 타입 1개와 4가지 종류의 명령으로 구성된다.

• 산술 명령 : Stack에서 산술/논리연산을 수행
• 메모리 접근 명령: Stack과 가상메모리 세그먼트 사이에 데이터를 주고받음
• 프로그램 흐름 명령 : 조건/무조건 분기 연산을 수행
• 함수 호출 명령 : 함수를 호출하고 결과를 반환

프로그램 및 명령구조

VM 프로그램은 .vm 확장자의 1개 이상의 파일로 구성되어있고, 이는 1개 이상의 함수로 구성된다. (= 프로그램, 클래스, 메서드) .vm 파일의 각 행은 하나의 VM명령이 되며 아래 중 하나의 형식을 가진다.

1. Command
2. Command arg
3. Command arg1 arg2

산술/논리명령

이 VM언어에는 9개의 스택기반 산술,논리명령들이 있다. 이중에서 7개는 2항명령(스택에서 2개의 데이터를 pop하여 2항 함수_binary function을 연산하고 결과를 스택에 push)이고 2개는 단항명령(스택에서 1개의 데이터를 pop하여 단항 함수_unary function를 계산하고 결과를 스택에 push)이다. 명령들은 남은 스택의 데이터를 건드리지 않음을 알 수 있다.

명령	반환 값 (Pop한 이후)	설명
add	x+y	정수 덧셈
sub	x-y	정수 뺄셈
neg	-y	산술 부정
eq	true if x = y else false	같음
gt	true if x > y else false	초과
lt	true if x < y else false	미만
and	x and y	비트단위
or	x or y	비트단위
not	not y	비트단위

eq, gt, lt는 return type 이 Boolean이다. true는 -1(0xFFFF), false는 0(0x0000)으로 반환된다.

메모리 접근 명령

우리가 만들 VM은 8개의 가상메모리 세그먼트_ VM segment 들을 조작하는 메모리접근 명령을 수행한다.

세그먼트	목적	설명
argument	함수의 인수를 저장	함수입력시 VM이 동적할당.
local	함수의 지역변수를 저장	함수입력시 VM이 동적할당 + 0으로 초기화.
static	.vm 한 파일 내에 모든 함수가 공유하는 정적변수를 저장	각 .vm파일에 대해 VM이 동적할당.
constant	0-32767 범위 내의 모든 상수를 갖는 pseudo-segment	VM의 에뮬레이트 프로그램 내의 모든 함수가 접근가능.
this/that	다목적 세그먼트. heap 내 서로 다른 영역에 대응하도록 설정가능	모든 VM함수는 heap상에서 선택된 영역 조작에 이 세그먼트를 사용가능.
pointer	this/that의 기준 주소값을 가진 2개의 입력 세그먼트	모든 VM함수는 pointer 0 (or 1)을 특정주소로 설정가능. 이로 this/that 세그먼트가 그 주소에서 시작하는 heap영역으로 정렬된다.
temp	일반용도의 임시변수를 갖는 고정 8-입력 세그먼트	VM 함수 내에서 모든 목적으로 사용가능. 프로그램의 모든 함수가 공유함.

메모리접근 명령

모든 메모리 세그컨트는 2개의 동일한 명령으로 접근 가능하다.

• push segment index : segment[index]값을 stack에 push
• pop segement index : stack의 top의 값을 pop하여 segment[index]에 저장

예를 들어 push argument 2 -> pop local 1 명령은 3번째 인수를 2번째 지역변수에 저장하라는 의미!

Push, pop으로 명시적으로 관리되는 8개의 메모리 세그먼트 외에도, 내부적으로 Stack과 Heap 구조를 관리한다. VM 명령에 따라 백그라운드에서 상태가 변한다. (직접 조작하지 않음)

• Stack : VM 연산의 작업메모리로 사용. 한 세그먼트에서 다른 세그먼트로 값이 스택을 거쳐 이동. 중심적인 역할을 맡고있으나 VM연산에서 직접 Stack을 언급하지는 않는다.
• Heap : 객체와 배열데이터를 저장하는 RAM영역의 명칭. VM명령으로 이들을 조작할 수 있다.

프로그램의 흐름과 함수 호출 명령

8장에서 자세하게 다루겠지만, 먼저 6개의 명령을 알아보자.

프로그램 흐름 명령

• label symbol : Label 선언
• goto symbol : 무조건 분기
• if-goto symbol : 조건분기

함수호출명령

• function functionName nLocals : 함수선언, 함수 지역변수의 개수 지정
• call functionName nArgs : 함수호출, 함수 인수 개수 지정
• return : 호출함수로 제어 되돌리기

Jack-VM-Hack 플랫폼의 프로그램 요소들

여러개의 Jack 언어 클래스 파일

<Compiler>

VM파일로 각각 번역 (여러개의 파일)

<VM 번역기>

Hack 어셈블리 파일 (1개의 파일)

<어셈블러>

Hack 2진 파일

VM번역기를 통해 생성된 어셈블리 프로그램은 2가지 주요한 작업을 담당한다.

1. VM함수 또는 파일의 가상메모리 세그먼트와 내부스택을 에뮬레이션한다.
2. VM명령을 플랫폼에서 실행한다. (기계명령어로 메모리를 조작하여 실행)

배열처리

배열은 index가 매겨진 객체들의 집합이다. 10개의 정수로 구성된 bar이라는 배열을 생성, 초기화했고 배열의 시작주소가 4315에 매핑되었다고 가정해보자. bar[2] = 19를 연산하려명 VM에서는 어떻게 구현해야할까? C언어에서는 *(bar+2)=19라는 방법으로 구현을 하는데, VM에서도 같은 방식으로 구현이 된다.

push local 0        // bar의 시작주소
push constant 2
add    
pop pointer 1        // bar + 2을 that에 저장
push constant 19    
pop that 0            // that + 0 주소에 19를 저장

객체 처리

고수준의 프로그래머의 관점으로 객체_object는 데이터(필드+속성)와 코드(관련 메서드)를 캡슐화한 개체이다. 그러나 실제구현에서 보자면 객체 인스턴스는 객체의 필드값들을 나타내는 수로 직렬화_serialize된 RAM상의 데이터로써 배열처리와 객체처리는 매우 유사하다.

예를 들어, 공을 다루는 프로그램을 만든다고 해보자. ball 객체의 특성을 x, y, radius, color라는 정수필드가 있다고 가정하자. b라는 ball 객체를 생성할 때 내부에서 이 객체를 표현하는 방법은 무엇일까? 새로운 객체를 생성할 때 마다 객체의 크기를 word 단위로 계산하고 OS는 충분한 메모리공간을 RAM에서 찾아 할당한다.

객체b와 정수r이 이 함수의 인수로 전달된다고 할 때 b.radius = r을 구현한 코드가 아래와 같다.

push argument 0
pop pointer 0    // argument 1(b)을 that에 저장
push argument 1    // argument 2(r)을 stack에 넣고 
pop this 2        // b[2]에 저장 (radius)

그럼 컴파일러는 b.radius = 17을 VM으로 어떻게 번역을 할까? 또한 3번째에 radius 필드가 있음을 어떻게 알까? 이에 대해서는 11장에서 공부해보자! 이번 장과 다음 장에서는 VM번역 까지만 공부를 하게된당!