[밑바닥부터 만드는 컴퓨팅] 08장 가상 머신 2 : 프로그램 제어

개요

해당 내용은 ‘밑바닥부터 만드는 컴퓨팅 시스템’ 책의 8장 내용을 정리하였습니다.

1. 배경

고수준 언어로 프로그램을 작성할 떄는 고수준의 표현을 사용할 쉬 있습니다. 근의공식의 경우 x=-b+sqrt(power(b, 2)-4*a*c) 와 같이 나타낼 수 있습니다. 고수준 언어는 다음과 같은 특징이 있습니다.

1. sqrt나 power와 같은 고급 연산을 필요에 따라 정의할 수 있음
2. 이러한 서브루틴을 기본 연산자처럼 호출할 수 있음
3. 서브 루틴이 실행되고 나면 코드 내에 다음 명령으로 반환됨

이러한 특징이 있기 때문에 우리는 알고리즘을 작성할 때 한층 더 가까운 추상화 코드를 작성할 수 있습니다. 추상화 수준이 높아질수록 저수준에서 처리할 작업은 늘어납니다. 서브루틴 호출이 일어날 때 뒷단에서는 다음과 같은 처리가 필요합니다.

• 호출지에서 호출된 서브루틴으로 매개변수 전달
• 호출된 서브루틴을 실행하기 전에 호출자의 상태 저장
• 호출된 서브루틴의 지역 변수에 공간 할당
• 호출된 서브루틴을 실행하기 위해 점프
• 호출된 서브루틴의 결팟값을 호출자로 반환
• 값이 반환될 때, 호출된 서브루틴이 점유한 메모리 공간을 재활용
• 호출자의 상태를 복구
• 호출자 코드에서 이전에 점프했던 지점 바로 다음 코드를 실행하기 위해 점프

이러한 작업들은 고수준 언어를 해석하는 컴퍼일러에서 해결해줍니다.

1.1 프로그램 흐름 제어

컴퓨터 프로그램은 기본적으로 한 명령씩 순차적으로 실행합니다. 이러한 순차적 흐름은 가끔씩 분기 병령으로 끊기게 됩니다. (if, switch 등에 의한 분기) 저수준 프로그래밍에서는 분기 논리가 있을 때 goto destination 명령으로 프로그램의 특정 위치부터 실행을 지속하도록 하게 합니다. 위치 설정의 경우 여러가지 방법이 있지만, 일반적으로는 다음에 실행할 명령어의 물리적 주소를 지정하는 것이 일반적입니다.

다음은 if 문과 while 문의 제어 흐름 구조와 이를 의사 VM으로 변환한 코드입니다.

• if 문 제어 흐름 구조

  if (cond)
  s1
  else
  s2
  ...
  

• 의사 VM 코드

  VM code for computing ~(cond)
  if-goto L1
  VM code for executing s1
  goto L2
  label L1
  VM code for executing s2
  label L2
  ...
  

• while 제어 흐름 구조

  while(cond)
  s1 
  ...
  

• while 의사 VM 코드

  label L1
  M code for computing ~(cond)
  if-goto L2
  VM code for executing s1
  goto L1
  label L2
  ...
  

1.2 서브루틴 호출

프로그래밍 언어들마다 특정한 내장형 명령 집합이 있습니다. 이러한 기본적인 명령 집합을 프로그래머가 자유롭게 고수준 연산들로 확장 가능하다는 점이 현대 개발 언어의 핵심적인 추상화 원리입니다. 이처럼 정의된 고수준 연산 단위를 서브루틴(또는 프로시저, 함수 메서드 등)라고 부릅니다.

잘 설계된 프로그래밍 언어는 기본 내장형 멸령들과 유사하한 느낌을 갖습니다. 그렇기때문에 새로운 서브루틴을 구현하게 된다면 호출자 관점에서 기존의 멍령들고 비슷하게 보이는 게 이상적일 것입니다. 두 연산을 자연스럽게 결합해서 일관성 있고 읽기 쉬운 코드를 만들 수 있습니다.

서브루틴 호출시에 call 키워드가 쓰인다는 점을 제외하면 내장형 명령 호출과 사용자 정의 서브루틴 호출의 차이는 없습니다. 두 연산 모두 호출자가 인수를 설정해줘야 하며, 스택에서 인수가 삭제되고 반환값이 스택 최상단에 입력됩니다.

power 와 같은 서브루틴은 보통 지역변수를 임시 저장소로 활용합니다. 지역변수는 서브루틴 시작부터 return 시점까지 메모리에 유효하며, return 이후에는 메모리 공간이 해제됩니다. 만약 서브루틴 안에 서브루틴을 호출하는 구조가 여러번 반복된다면 중첩되는 상황이 점점 복잡해지게 됩니다. 이렇게 되면 서브루틴 안에서 새로운 서브루틴을 호출한다면, 그 서브루틴이 끝나야 기존의 서브루틴을 진행한다는 특징이 있습니다. 이는 후입선출 구조인 스택의 구조와 맞아떨어지게 됩니다. 아래의 그림은 서브루틴 내부에서 서브루틴을 호출하는 구조가 여러번 반복되었을 때에 대한 스택 구조를 나타낸 그림입니다.

2. VM 명세 2부

이번 장에서는 7장의 기초 VM 명세에 프로그램 흐름 제어 명령과 함수 호출 명령을 추가해서 전체 VM 명세를 완성하는 것을 목표로 합니다.

2.1 프로그램 흐름 제어 명령

제작하는 VM 언어에는 세가지 프로그램 흐름 제어 명령이 있습니다.

2.1.1 lable lable

이 명령은 함수코드의 위치에 레이블을 붙입니다. 프로그램 내 다른 지접에서는 레이블이 표시된 위치로만 점프 가능합니다. 레이블의 유효 범위는 레이블이 정의된 함수 내부까지입니다.

2.1.2 goto lable

이 명령은 무조건 분기 명령으로 lable 부터 실행하라는 명령입니다. 점프할 위치는 같은 함수 내에 있어야 합니다.

2.1.3 if-goto lable

이 명령은 조건 문기 명령입니다. 스택의 최상단 값을 꺼내서 그 값이 0이 아니면 lable 로 표시된 위치에서 실행을 계속하고, 값이 0이면 프로그램 다음 령명을 실행합니다. 점프할 위치는 같은 함수 내에 있어야 합니다.

2.2 함수 호출 명령

함수는 전역적으로 호출할 때 쓰이는 기호로 된 이름이 있습니다. 함수 이름의 범위는 전역적입니다. 즉, 모든 파일 내의 함수 이름들이 공유되며, 그 함수 이름으로 서로 호출할 수 있습니다. 이 VM 언어에서는 세종류의 함수 관련 명령이 있습니다.

2.2.1 function f n

해당 위치부터 이름이 ⨍ 고 지역변수가 n개인 함수가 시작됩니다.

2.2.2 call f m

함수 ⨍ 를 호출합니다. 이때 호출자가 스택에 m개의 인수를 push 했다는 사실도 같이 전달됩니다.

2.2.3 return

호출한 함수로 반환됩니다.

2.3 함수 호출 규약

함수를 호출하고 반환되는 이벤트는 호출하는 함수와 호출되는 함수의 두 관점에서 볼 수 있습니다.

• 호출하는 함수 관점
  • 함수를 호출하기 전에 호출자는 필요한 수의 인수를 스택에 push 해야 함
  • 다음으로 호출자는 call 명령으로 함수를 불러옴
  • 호출된 함수가 반환된 후에는, 호출자가 호출하기 전에 push 한 인수들은 스택에서 사라지고 반환값이 스택 최상단에 있게 됨
  • 호출된 함수가 반환된 후에, 호출자의 메모리 세그먼트들은 호출 전과 동일하며, temp 세그먼트는 미정의 상태임
• 호출되는 함수 관점
• 호출된 함수가 실행을 시작할 때 argument 세그먼트는 호출자가 넘겨준 실제 인수 값으로 초기화되며, local 변수 세그먼트는 할당되고 0으로 초기화됨
• 호출된 함수가 바라보는 static 세그먼트는 그 함수가 속하는 VM 파일의 static 세그먼트로 설정되며, 작업 스택은 비어있음
• this, that, pointer, temp 세그먼트들은 시작 전에는 미정의 상태임
• 반환되기 전에 호출된 함수는 값을 하나 스택에 push해야함

2.4 초기화

VM 프로그램은 고수준 프로그램을 컴파일한 결과로 나온 VM 함수들의 모음입니다. VM 이 실행될 때는 항상 Sys.init이라는 인수 없는 VM 함수를 먼저 실행하게 됩니다. 이 함수는 사용자 프로그램의 메인 함수를 호출합니다. 따라서 VM 코드를 생성하는 컴파일러는 프로그램 번역시 Sys.init 함수가 있는지 확인해야 합니다.