NandToTetris : 가상머신2-제어 (밑바닥부터 만드는 컴퓨팅 시스템)

런타임 시스템

모든 컴퓨터 시스템은 런타임 시스템 모델을 정의해야합니다.

프로그램 실행을 시작하는 방법, 프로그램 종료시 수행해야하는 작업,

한 함수에서 다른 함수로 인수를 전달하는 방법, 실행 중인 함수에 메모리 리소스를 할당하는 방법, 더 이상 필요없는 메모리를 해제하는 방법 등, 모든 필수적인 질문들에 대한 정의가 필요합니다.

 

핵 플랫폼에서는 이 문제들을 HACK 플랫폼의 표준 맵핑과 함께 VM 언어 명세로 다룹니다.

명세에 따라 vm 번역기를 개발하면 최종적으로 실행 가능한 런타임을 구현 할 수 있습니다.

특히 vm 번역기는 vm명령 (push, pop, add)등을 어셈블리 명령어로 번역할 뿐 아니라, 위에서 언급한 모든 질문들에 대한 대답을 어셈블리어로 만들 수 있습니다.

고수준 마법

위와 같은 수식은 고수준 언어를 이용하면 실제 수직과 거의 유사한 형태로 만들 수 있습니다.

뿐만아니라 if와 같은 분기문을 이용해서 더 고수준의 논리를 적용 할 수도 있습니다.

하지만 컴파일러 및 vm 에서는 저수준에서 분기 명령 및 함수 호출-반환 명령을 구현해야합니다.

함수

모듈식 프로그래밍의 기본 단위로서, 특정 기능을 수행하도록 서로를 호출 할 수 있는 독립적인 프로그래밍 단위를 말합니다.

solve라는 함수는 sqrt() 함수를 호출하고 또 sqrt()는 power() 함수를 호출 할 수 있습니다.

어떤 경우에는 재귀적으로 깊이 들어갈수도 있습니다.

 

일반적으로 호출하는 함수 (caller)는, 호출 받는 함수를 콜리 (callee)에게 인수를 전달하고, 호출되는 함수가 실행을 완료 할 때 까지 실행을 일시 중단합니다.

콜리는 전달받은 인수를 활용하여 무언가를 실행하거나, 계산한 후 다음 호출자에게 값을 반환합니다.

 

말로만 들으면 간단하게 끝날 것 같지만,

한 함수가 다른 함수를 호출할 때마다 아래와 같은 추가작업(overhead)들이 필요합니다.

 

콜러가 콜리 호출 시 발생하는 오버헤드

- 콜리가 실행을 마친 후 제어를 반환해야하는 주소 저장

- 콜러의 메모리 자원 저장

- 콜리에서 필요한 메모리 자원 할당하기

- 콜러가 전달한 인수를 콜리에서 사용할 수 있도록 만들어야함

- 콜리 코드를 시작

 

 콜리가 값 반환시 발생하는 오버해드

- 콜리의 리턴 값을 콜러에서 사용할 수 있도록 만들어야함

- 콜리가 사용했던 메모리 자원 반납

- 콜리 연산 전, 콜러를 멈출 때 저장했던 메모리 자원 복원

- 이전에 저장해둔 반환 주소 되찾기

- 반환 주소부터 콜러의 코드 다시 시작

분기

저수준 프로그래밍에서 분기는 goto destination 명령으로 실행됩니다.

목적기 (destination)에는 여러 형식이 있지만, 가장 기초적인건 다음에 실행될 실제 메모리의 주소입니다.

 

저수준 언어에서 코드 내 특정 위치에 기호 레이블을 설정 할 수 있는 레이블 지시문이 있다면,

실제 메모리에 바인딩 되는 기호 레이블을 지정하는 방식으로 나름대로 추상적인 지정도 가능합니다.

 

핵 플랫폼에서 만드는 vm언어에서는 label symbol이라는 구문으로 레이블 지시문을 사용 할 수 있습니다.

vm언어에서는 무조건 분기 (unconditional branching), 조건부 분기 (conditional branching) 두가지가 존재합니다.

vm언어에서는 불 표현식을 스택에 넣는 방식으로 조건을 지정합니다.

예를 들어 if (n<100) goto LOOP를 push n, push 100, lt, if-goto LOOP로 번역합니다.

 

무조건 분기 (unconditional branching)

  - goto symbol 명령으로 수행

  - 코드에서 label symbol바로 다음 명령으로 점프해서 그 명령을 실행하라는 뜻

 

조건부 분기  (conditional branching)

  - if-goto symbol몀령으로 수행

  - 스택의 최상위 값을 pop하여, 그 값이 true이면 label symbol 명령의 바로 다음 명령으로 점프해 그 명령을 실행하고, false면 코드에서 바로 다음 명령을 실행하라는 뜻

분기처리 예시

x와 y에 대한 함수가 있습니다. (sum = sum + x, y times)

while문에 조건을 이용하면 간단하지만 vm 코드에서는 vm의 분기명령인 goto, if-goto, lable을 이용해 루프를 구현합니다.

 

함수

위 사진의 vm코드쪽을 보면 push나 sub같은 명령어들은 이제 익숙하지만 call Math.multiply라는 함수를 호출하는 명령어가 등장합니다.

앞서 구현했던 ALU에 곱셈은 없기에 핵 컴퓨터에서 곱셈연산을 하기위해선 Math.multiply라는 운영체제의 함수가 필요합니다.

vm언어는 운영체제와 인터페이스가 가능합니다!

함수는 자신만의 작업스택과 메모리 세그먼트를 사용합니다.

예시

함수는 일반적으로 지역(local)변수와 인수(argument)변수들을 사용합니다.

메모리 세그먼트는 함수가 실행 될 때 할당되었다가, 함수가 반환될 때 반납되어야 합니다.

런타임동안 각 함수 호출들은 다른 호출과 독립적으로 실행되어야하고, 자신만의 스택과 지역 변수 및 인수 변수를 유지 및 관리해야합니다.

 

먼저 main함수는 3,8,5를 스택에 넣고 mult 2 함수를 실행합니다. 

 

mult 2 함수는 실행되면 자신만의 독립적인 스택공간들을 가집니다.

함수의 0번줄 : argument세그먼트에 스택에 들어있던 2개의 인수 8,5가져오고, local 세그먼트는 인수를 2개로 받았기에 2개의 공간을 0으로 초기화 합니다.

함수의 1~4번줄 : 함수는 push constant 0, pop local 0, push constant 1, pop local 1 명령을 실행해 로컬 세그먼트를 0,1로 초기화 시킵니다. 

함수의 7~8번줄 : 함수는 local 1의 값과 argument 1의 값을 함수의 private 스택에 추가합니다. 

 

이후 연산이 수행되고

마지막에 20번줄에서 push local 0명령어를 통해 연산된 값 40을 함수의 private 스택에 추가합니다.

그 후 값은 caller로 반환되어 main함수의 스택에 값 40이 들어갑니다.

 

다른 예제도 간단하게 확인해 보겠습니다.

 

아래 예제에서는 main -> hypot -> mult 순서대로 함수가 호출되는데 이렇게 프로그램에 실행에 관련된 모든 함수를 개념적으로 가리키기 위해 이와같은 상황 및 함수들의 관계를 콜링 체인 (calling chain)이라고 부릅니다.

 

main 함수가 hypot을 실행하면 hypot 함수에 기존 stack에 있던 인자 3,4가 hypot 함수의 stack에 들어갑니다.

이후 hypot함수는 인자로 들어온 x(3)을 함수의 private 스택에 2번 넣고 mult 함소를 호출합니다.

 

mult함수에서는 local 세그먼트의 인덱스를 sum, i로 표기하고

16 ~ 19번 명령을 통해 초기화합니다.

연산이 수행되고 36번줄에서 확인해보면 multi함수의 private 스택에는 연산결과 9를 확인 할 수 있고 이 값은 hypot로 반환됩니다.

이후 hypot 함수의 private 스택에는 mult의 결과값인 9가 남고, 이후 yy도 동일하게 하여 9,16을 만듭니다.

 

Function Call And Return

함수가 호출될때와 종료될때에 대해 알아보겠습니다.

1. Sets arg

caller에서 함수를 호출하면 stack에는 먼저 callee로 전달될 인수(argument)들이 필요합니다.

현재 작업하고있는 스택의 바로 아래서부터 callee가 필요한 인수만큼 만큼 argument들의 주소가 할당됩니다.

 

2. Saves the caller's frame

callee가 호출되면 caller는 작업하던 상태를 보관하고 callee로 넘어가야합니다.

그 와중에 callee는 callee의 지역 변수, 매개변수, this, that과 같은 포인터가 사용되는데 이때 caller의 정보들에 덮어씌우면 안되기에

caller만의 정보를 저장해 두어야 한다. 이때 caller의 정보를 스택에 쌓아두는데 이 값들을 모두 합쳐 프레임이라고 부릅니다.

3. Jumps to execute callee

위와같은 작업이 끝나면 callee로 이동합니다.

 

이제 callee에서 어떤일이 일어나는지 알아보겠습니다.

1. Sets up the local segment of the called function

호출된 함수에 대한 지역 변수 세그면트(LCL)를 생성하고 값을 초기화 합니다. 

2. Retuen

함수에 정의된 작업이 끝나면 응답을 반환해야합니다.

callee는 리턴값을 argument[0]에 저장합니다. (이렇게 하면 callee의 리턴값이 caller의 스택 가장 위에 들어가게 됩니다.)

이후 sp를 arg + 1로 조정해서, caller가 함수를 호출했던 반환 주소로 돌아갑니다.

 

그후 caller의 LCL, ARG, THIS, THAT을 복구합니다. (이 과정에서 callee의 LCL과 ARG는 사라짐)

마지막으로 return address로 jump합니다.

Global Stack (전역 스택)

위에서 하나의 caller와 callee를 살펴보았는데, 프로그램은 무수히 많은 caller와 callee쌍이 존재합니다.

이 모든 정보들 또한 stack에 존재하는데 이 스택을 Global Stack이라고 부릅니다.

Global Stack에서 현재 실행 중인 caller와 callee들을 block이라고 합니다.

callee가 종료되고 caller가 실행 되면서, 기존에 frame들과, callee에서 사용했던 값들은 이후 caller가 실행되며 값들이 덮어씌우면서 재사용 됩니다.

 

예제

고수준 코드를 컴파일하게 되면 vm코드가 생성됩니다.

그 과정에서 어떻게 스택이 사용되는지 알아보겠습니다.

vm코드를 순서대로 따라가 보면

push 3을 해서 global stack에 3이 들어갑니다.

 

이후 call factorical 명령이 실행되어 argument[0]이 3을 바라보게 하고,

main함수의 frame들을 저장합니다.

 

이제 f(3)의 명령어들이 실행됩니다.

push argument 0 (n) , push constant 1을 비교(eq)합니다.

같지 않기에 BASECASE로 이동하지 않습니다.

 

push argument 0 (n), push argument 0 (n), push constant 1, sub 가 실행되면서

stack에 3,2가 들어갑니다.

 

이제 f(2)가 호출됩니다.

새로운 callee가 생성됨에 따라, global stack에는 f(3)의 frame이 추가됩니다.

f(2)의 argument 세그먼트도 새롭게 생성됩니다.

 

f(2)는 f(3)과 argument만 다른 상태로 동일한 적업을 수행하고,

스택에 f(2)의 프레임, f(1)의 argument를 생성하며 f(1)이 시작됩니다.

 

하지만 f(1)에서는 eq명령에 따라 BASECASE로 jump되고 push constatn 1 명령이 실행되고 f(1)함수가 반환됩니다.

argument[0]에 f(1)의 리턴값(1)이 복사됩니다. f(2)와 f(3)도 동일하게 반환되면서 main함수는 최종 리턴값을 얻게됩니다.

 

vm 머신 정리

우리의 vm모델은 스택기반입니다.

push/pop 명령을 통해 스택과 메모리 세그만트 사이에 데이터를 전송하고, 분기와 함수를 이용하여 산술 및 논리 연산을 수행합니다.

vm번역기는 컴파일러가 생성한 vm언어들을 어셈블리어로 변경하는 프로그램입니다. (FileName.vm -> FileName.asm)

RAM에 지정된 메모리를 이용해서 vm의 스택을 표현하며, RAM 블록의 밑바닥은 고정된 기본 주소가 되고, 최상단은 스택에 따라 변화하게 됩니다.

따라서 고정 주소(stackbase)가 주어지면, 스택의 최상단 값 바로 뒤의 RAM 주소를 추적하는 스택포인터 (sp)를 통해 스택을 관리합니다. (push x 명령은 RAM[SP] = x, SP++, pop x명령은 SP-, x = RAM[SP] 와 같은 의사코드로 구현 가능)

 

vm프로그램은 잭과 같은 고수준 프로그램 언어로 생성되며,

잭 컴파일러를 적용하면 Test.jack 클래스의 파일들은 -> Test.vm으로 번역됩니다.

 

컴파일 이후 Main.jack 파일 내의 bar라는 이름의 생성자, 함수, 메서드들은 vm함수로 번역되며 vm함수는 전역적입니다.

그렇기에 함수의 이름은 Test.FuncName 처럼 고유한 이름이 됩니다.

 

프로그램의 진입점은 반드시 Main.jack이어야 하고, 이 파일에서 vm함수 하나는 이름이 Main.main이 됩니다.

vm프로그램이 실행을 시작할 때, 항상 실행되는 첫 번째 함수는 인수가 없는 Sys.init이라는 함수로 os의 일부분입니다.

이 os함수는 사용자 프로그램에서 진입점이 되는 함수를 호출하도록 되어있습니다.

Sys.init은 잭 프로그램에서는 Main.main을 호출합니다.

RAM활용

vm에서 RAM을 활용하는 방식은 아래와 같습니다.

세그먼트의 기본 주소들은 각각 LCL, ARG, THIS, THAT레지스터에 저장됩니다.

이 세그먼트에 접근하려면 push segument Name i라는 명령이 필요한데 이는 (base+i)RAM주소로 접근하라는 어셈블리 코드로 변경되어야 합니다.

부트스트랩 코드

핵 플랫폼에서는 RAM이 256부터 매핑되고, 실행을 시작하는 첫 vm함수가 OS함수인 Sys.init이어야 한다고 규정합니다.

ROM[0]주소에 SP=256이 실행되고 이후 call Sys.init 명령어가 실행됩니다.

운영체제의 일부인 Sys.init함수는 응용프로그램의 main함수를 호출하고 무한루프에 들어가게됩니다.

그리고 이 작업으로 번역된 vm프로그램이 실행됩니다.

프로그램 구조

책에서는 vm번역기는 3가지 모듈 VMTranslator, Parser, CodeWriter로 구현하기를 권장한다고 말합니다.

VMTranslator

Parser와 CodeWriter를 이용해서 번역 과정을 수행하는 메인 프로그램입니다.

입력 소스 파일명에 .vm파일을 받아 해당 파일을 파싱하기 위한 Parser모듈을 생성하고 번역된 어셈블리 명령어들을 출력할 기록파일 .asm을 만듭니다.

이후 파일 내 vm명령어들을 반복하는 루프를 실행해 명령을 번역합니다.

 

Parser

vm 파일의 파싱(구문 분석) 처리, 이 모듈은 vm 명령을 읽고 명령을 다양한 구성 성분으로 분석하고,

그 성분들에 편리하게 접근 하도록 도와줍니다. (분기 및 함수명령을 포함한 모든 vm명령을 처리)

간단하게 말하면 vm코드 파일을 읽고, 명령을 해석합니다 

 

예를들어 아래와 같은 명령어가 있다면 'push constant 10' 같은 vm코드가 들어오면 명령유형 (push), 첫번째 인자 (constant), 두번쨰 인자 (10)을 CodeWriter에 전달합니다.

 

CodeWriter

파싱된 vm명령을 핵 어셈블리 코드로 변환합니다.

예를 들어 writePushPop (C_PUSH, 'local',2)를 호출하면 push local 2라는 vm명령을 구현하는 어셈블리 명령어들이 생성되어야 합니다.

함수 호출과 반환

함수를 호출하고, 함수를 반환받는 이벤트에서는 호출자(caller)의 관점과 피호출자(callee)의 관점이 있습니다.

두 관점 보두 call, function, return 명령어 처리에 기대되는 동작과 책임이 존재합니다.

call은 호출자의 스택을 프레임에 저장하고, 피호출자 실행으로 점프하는 코드를 실행합니다.

function은 피호출자의 지역변수를 초기화합니다.

return은 반환값을 호출자의 스택 최상단에 복사하고, 호출자의 세그먼트 포인터를 복원 후, 반환 주소 다음부터 실행하도록 점프하는 코드를 실행합니다.

 

vm번역기가 사용하는 특수기호 목록

SP와 LCL, ARG, THIS, THAT은 익숙하기에 생락하구..

R13-15s : 임시 저장용 레지스터. 보통 리턴 주소나 임시 데이터 저장 등에 사용됩니다.

Xxx.i : Xxx.vm 파일의 i번째 정적 변수는 어셈블리어에서 Xxx.i로 변환됩니다.

functionName : 함수 시작 지점을 나타냅니다.

functionName$ret.i : 함수에서 i번째 리턴 후 시작될 위치를 나타냅니다.

functionName$label : 함수 내부의 특정 위치를 나타냅니다. (조건문에서 분기할 때 사용)

vm코드 예시

function Main.main 0  

  push constant 3    
  push constant 4    
  call Multiply 2    // 프레임 및 리턴주소(Main.main$ret.1) 생성

  call CheckEven 1   // 프레임 및 리턴주소(Main.main$ret.2) 생성

  goto Main$End      // 프로그램 종료

function Multiply 0  
  push argument 0    
  push argument 1    
  mul                
  return             // (Main.main$ret.1)로 이동

// CheckEven 함수 (짝수 판별)
function CheckEven 0  
  push argument 0    
  push constant 2    
  mod                
  if-goto Main$Failure  // 나머지가 0이 아니면 실패 (홀수)
  goto Main$Success     // 나머지가 0이면 성공 (짝수)

// 성공 label
(Main$Success)   
  label Main$Success
  // 여기서 성공 처리
  goto Main$End

// 실패 label
(Main$Failure)   
  label Main$Failure
  // 여기서 실패 처리
  goto Main$End

// 프로그램 종료 label
(Main$End)  
  label Main$End