중간 표현(IR)이 실제로 어떤 모습인지, 스택 기반/레지스터 기반 IR 예제와 분기·finally 같은 제어 흐름이 IR에서 어떻게 평탄화되는지 살펴본다.
중간 표현(IR)은 소스 코드에서 대상 머신에서의 실행으로 가는 중간 단계 언어로 사용된다. 중간 표현을 사용하는 이유에 대한 내 글에서는 IR이 무엇이고 어떻게 쓰는지 설명했다. 여기서는 예제를 통해 IR이 실제로 어떻게 생겼는지 보여주려 한다. 이 수준의 IR을 이해하면 컴파일러와 가상 머신을 구현하는 이야기를 할 때 도움이 된다.
이 글에서는 “머신”이라는 말을 많이 쓸 것이다. 간단히 말해 “추상 머신”은 명령 집합과 그 동작을 정의하는 이론적 구성물이다. “가상 머신”은 특정 “추상 머신”의 코드를 실행할 수 있는 소프트웨어다. 그리고 하드웨어는 가상 머신(또는 저수준 추상 머신)의 코드를 실제로 실행할 수 있는 물리적 머신이다.
IR을 이해하려면 간단한 고수준 예제를 가져와 IR로 변환해 보는 게 가장 좋다. 예제가 이해 가능하도록 단순한 언어를 사용해 단순한 IR로 변환해 보겠다. 실제 언어와 IR은 금방 복잡해진다.
결과를 계산하고 출력하는 간단한 함수형 언어를 생각해 보자. 아래 예제로 시작한다:
5 + 7
이 코드는 5와 7의 합인 값 12를 출력한다.
중간 표현은 대상으로 하는 추상 머신에 따라 다양한 형태가 될 수 있다. 핵심적인 차이 중 하나는 시스템이 표현식 평가를 어떻게 처리하느냐에 있다. 이제 스택 기반, 그리고 레지스터 기반 접근이 이 코드를 어떻게 처리하는지 살펴보자.
스택은 값을 push/pop 할 수 있는 메모리 영역이다. 이 추상 머신을 대상으로 하는 IR은 표현식의 결과를 저장하기 위해 스택을 사용한다.
이 IR은 우리의 예제를 다음처럼 표현할 수 있다:
push 5 push 7 add
push 명령은 값을 스택에 올린다. add 명령은 스택에서 두 값을 꺼내 합을 계산한 뒤, 그 결과를 다시 스택에 올린다. 프로그램이 끝나면 스택의 맨 위 값을 콘솔에 출력한다.
아래 코드를 각 단계에서의 스택 상태와 함께 보자.
// [] <-- 스택, 처음엔 비어 있음 push 5 // [5] push 7 // [5, 7] add // [12] // 머신이 스택 맨 위 값 "12"를 출력
스택 기반 가상 머신은 구현하기 쉽다. 단순한 루프와 switch 문으로 위 스타일의 IR을 실행할 수 있다. 우리는 추상 머신(코드의 규칙과 연산을 정의하는 이론적 구성물)에서의 동작으로 IR을 정의한다. 가상 머신은 이 코드를 실행할 수 있는 “현실의” 무언가다. 이 단순한 IR에서는 추상 머신의 규칙을 직접 구현할 수 있다. 그래서 추가 변환 없이 이 IR을 그대로 사용할 수 있다.
스택 대신 모든 표현식을 명시적으로 추적하는 방법도 있다. 이는 머신에 이름이 붙은 레지스터가 무한히 있다고 가정하는 것과 비슷하다. 실제 머신은 무한 레지스터를 갖지 않지만, 추상화로는 유용하다.
같은 코드를 레지스터 기반 IR로 나타내면 다음과 같다:
%a = 5 %b = 7 %c = add %a %b @result %c
레지스터 기반 머신에서는 모든 값을 어떤 “레지스터”에 할당해야 한다. 레지스터는 상수 값이나 단순 표현식을 가리키는 이름일 뿐이다.
@result는 특별한 것을 나타내므로 %와 다른 기호를 쓰겠다. 많은 레지스터 기반 머신의 한 특징은 레지스터가 한 번만 사용된다는 것이다. 레지스터가 무한히 있으니 재사용할 필요가 없다. 따라서 @result는 레지스터가 아니라, 어떤 값을 출력할지 머신에 알려주는 방법이다.
물론 어떤 하드웨어도 이런 계산 모델을 직접 지원하지 않는다. 또한 이런 IR을 그대로 사용하는 가상 머신을 작성하는 것도 까다롭고 비효율적이다. 이 IR은 실행 전에 추가 변환이 필요하다.
힙과 호출 개념을 도입한 다른 예제를 보자. 그리고 이에 대응하는 스택 머신/레지스터 머신 IR을 보겠다. 이 예제에서는 값을 “영구적으로” 저장할 힙(heap) 개념을 도입한다. 또한 기본 출력 동작을 제거했으므로 명시적으로 print 함수를 호출해야 한다. 그리고 이 개념으로 자연스럽게 들어가기 위해 기본적인 타입도 도입한다.
a: Integer = 5 a += 7 print( a )
아래는 스택 기반 IR이며, 각 단계에서 스택의 내용도 함께 표시했다.
// a: Integer = 5 allocate_integer @a push_integer 5 // [5] pop_integer_to @a // []
// a += 7 push_integer_from @a // [5] push_integer 7 // [5, 7] add_integer // [12] pop_integer_to @a // []
// print( a ) push_integer_from @a // [12] call print // eventually -> []
이 코드에서 보듯, 고수준 표현식은 스택을 중심으로 하는 단계별 연산으로 축소되었다. print 함수 호출조차 인자를 “잃어버렸고”, 대신 인자가 스택에 push 된 다음 인자 없는 call이 실행된다.
같은 코드를 레지스터 기반 IR로 나타내면 다음과 같다.
// a : Integer = 5 allocate_integer @a %ra = 5 store_integer_to @a %ra
// a += 7 %rb = load_integer_from @a %rc = 7 %rd = add_integer %rb %rd store_integer_to @a %rd
// print( a ) %re = load_integer_from @a call (Integer) print %re
이 형태는 LLVM이 IR로 사용하는 것과 비슷하다. LLVM은 잘 정의된 IR을 가진 컴파일러 툴체인이다. % 기호는 레지스터를 뜻하며, 이 머신에서는 레지스터가 무한히 있다고 가정한다. 최적화기는 종종 이 형태의 입력을 선호한다. 값과 표현식 사이의 관계가 그래프 구조를 이루므로, 스택보다 재배치가 쉽기 때문이다.
마지막 줄 call (Integer) print %re에서 (Integer) 부분은 호출하는 함수의 인자 시그니처다. 우리는 추상 머신이 적절한 호출 규약(calling convention)을 만들 것이라 가정한다. 어떤 머신은 레지스터를 쓰고, 어떤 머신은 스택을 쓰며, 어떤 머신은 둘을 섞어 쓴다. 이 부분은 같은 하드웨어 위에서도 운영체제마다 다르다. 따라서 IR에 넣기보다는 최종 변환 단계에 맡기는 것이 좋은 세부 사항이다.
실제로는 현실의 머신과 가상 머신 모두 레지스터, 스택, 힙 영역을 함께 갖는다. 중간 표현이 어떤 접근을 택할지는 IR의 목표와, 문제가 생길 지점을 어디에 두고 싶은지에 달려 있다. 스택 기반이지만 자바의 VM 내 JIT 컴파일러는 레지스터 기반 머신에 맞춰 최적화할 수 있고, 레지스터 기반이지만 LLVM도 혼합 레지스터/스택 머신으로 빠르게 변환하는 JIT을 갖고 있다.
이후부터는 레지스터 기반 IR을 사용하겠다. 처음엔 복잡해 보이지만, 실행 흐름과 표현식 값의 흐름을 보기에는 더 쉽다.
많은 툴체인은 소스 코드로부터 이 형식을 출력하게 해 준다. 예를 들어 “emitting LLVM IR”로 검색해 보라. 아주, 아주 단순한 파일로 실험해 IR을 출력해 보라. 최적화를 켜면 소스가 어떻게 변환됐는지 알아보기 어려우니 최적화는 꺼 두는 게 좋다.
분기(branch)는 언어에서 흔한 기능이다. IR에서도 흔한 특징이 “평탄화(flattening)”다. 소스 언어는 조건문이나 루프에 붙은 중첩 블록으로 구조를 표현한다. 그런데 어느 시점에는 이런 구조가 사라져야 한다. IR에서는 그 중첩 구간들이 라벨이 붙은 순차 명령의 나열로 평탄화되어 나타나는 것을 보게 된다.
이 예제에서는 조건부 부분에 집중하기 위해 일부 준비 코드를 생략하겠다.
if a > 5: b = 1
IR로 변환:
%r1 = cmp_integer_gt @a 5
branch %r1 label_true label_false
label_true: assign_integer @b 1 jump label_end
label_false: jump label_end
label_end: ...
이는 LLVM IR과 유사한 형태다. 라벨은 코드 블록을 도입한다. 모든 코드 블록은 완결되어 있으며, 마지막 명령은 return 문이거나 branch 문(분기문)이다. 한 블록에는 분기문이 하나만 있을 수 있다. 즉 블록의 순서는 중요하지 않다. 레지스터처럼 이들은 그래프를 형성한다. 이는 최적화를 적용하기에 좋은 형태다.
또한 label_false가 label_end로 점프만 하고 아무 것도 하지 않는다는 점에 주목하라. 대신 branch 문에서 label_end를 직접 지정할 수도 있었다. 곧 이것이 왜 도움이 되는지 보게 될 것이다.
옛날 어셈블러 코드를 본 적이 있거나, 자바 바이트코드에 익숙하다면 더 단순한 분기 명령(코드의 오프셋으로 점프)을 예상할 수도 있다. 위 코드를 그런 식으로 다시 쓸 수 있다.
%r1 = cmp_integer_gt a 5
branch_not %r1 label_false
assign_integer b 1
label_false: ...
여기서는 fallthrough(자연스럽게 다음으로 이어지는 실행) 동작과 부정 조건을 이용한다. 표현식이 거짓이면 뒤의 코드를 건너뛴다. 바이트코드에서는 라벨도 사라지고, 아마 바이트 오프셋으로 대체될 것이다. 예를 들어 label_false가 16바이트 떨어져 있다면 branch_not %r1 +16 같은 식이다.
항상 분기하는 형태와 비교하면, 이 fallthrough 형태가 기계어에 더 가깝다. 하지만 수백 개(잠재적으로는 수천 개)의 블록이 있는 함수라면 순서에 의존하고 싶지 않다. 특히 최적화기가 블록들을 재배치하려 한다면 더 그렇다.
finally 블록이 있는 분기생성된 IR과 소스 코드의 관계를 이해하는 일은 빠르게 어려워진다. 우리는 코드에서 조건, 루프, switch를 자연스럽게 중첩해서 쓰는데, 이 모든 것이 IR에서는 평탄화되어야 한다. 또한 암시적 분기도 있다. 예를 들어 C++ 객체 소멸자는 스코프를 벗어날 때 호출되고, 자바에는 finally 키워드가 있다. 예제로 finally를 사용해 보겠다.
function proc: try: a = get_value() if a > 10: return 1
finally:
print_notice()
return 0
전형적인 IR은 크기가 빠르게 커지므로, 이 예제들은 반드시 사소한 수준으로 유지해야 한다.
entry: alloc_integer @branch_code 0
%r1 = call get_value
%r2 = cmp_integer_gt %r1 10
branch %r2 label_true label_false
label_true: store_integer @return_code 1 jump label_finally
label_false: jump label_finally
label_finally: call print_notice branch return_code %post_cond %end_block
post_cond: return 1
end_block return 0
여기서 보여주고 싶은 것은, 정상 흐름을 끊는 문장(예: return)이 IR을 얼마나 빠르게 압도적으로 만들 수 있는지다. return은 어떤 블록 중첩 안에도 존재할 수 있고, finally 블록이 여러 개일 수도 있으며, 객체 소멸자도 여러 개일 수 있다. 여기에 예외 흐름(exceptional flow)까지 더하면, 사실상 모든 블록을 또 다른 조건 흐름 블록으로 감싸는 셈이다. 끔찍하다!
Leaf 컴파일러를 만들 때, 추상 구문 트리(AST)에서 곧바로 LLVM IR로 가는 것이 너무 어렵다는 걸 깨달았다. 명령을 번역하면서 동시에 흐름을 평탄화해 블록으로 만드는 것이 지나치게 복잡했다. 그래서 가장 논리적인 일을 했다. 또 다른 IR을 도입한 것이다. Leaf IR과 LLVM IR의 가장 큰 차이는 Leaf IR이 초기 코드의 트리 같은 구조를 유지했다는 점이다. 초기 IR 생성 단계에서는 비-흐름(non-flow) 구성에 집중하고, 두 번째 단계에서 흐름을 평탄화하는 데 집중할 수 있었다.
어셈블리 프로그래밍 경험이 있다면 유사성을 알아볼 것이다. IR은 사실상 추상 머신을 위한 어셈블리 코드다. 제한된 명령 집합을 사용하고, 우리가 컴퓨터의 동작을 생각하는 방식과 잘 맞는다.
우리는 어셈블리 코드를 특정 머신에 정확히 대응하는 것으로 생각한다. 어셈블리 코드의 문장과 기계어 사이에는 거의 1:1 대응 관계가 있다. 하지만 컴파일러 툴체인과 가상 머신의 대부분의 IR은, 이러한 머신 특정 어셈블리 언어보다 더 높은 수준의 명령을 포함한다.
몇몇 특별한 경우를 제외하면 우리는 기계어 어셈블리로 직접 코드를 작성하진 않지만, 컴파일러 출력물을 디버그하는 데는 사용할 수 있다. IR도 마찬가지다. 우리는 IR로 무언가를 직접 작성하는 경우가 거의 없다. IR의 시각적 형태가 필요한 이유는 디버깅을 해야 할 때뿐이다. 그 외에는 IR을 더 컴팩트한 바이트 인코딩 형태로 저장한다.
엄밀히 말하면 중간 표현(또는 중간 언어)은 소스 코드와 실제 하드웨어에서 실행되는 것 사이의 어떤 표현이든 될 수 있다. 하지만 우리는 보통 파스 트리(parse tree)나 추상 구문 트리(AST)를 IR이라고 부르지 않는다. 보통 IR이라고 할 때는 고수준 구성물의 상당 부분이 더 단순한 명령열로 바뀐 축약 형태를 의미한다. 이 IR 형태는 최종 컴파일 계층에서 빠르게 변환된 뒤 실행되기에 적합하다.
이 글에서는 바로 그 축약된 형태의 IR을 보여주었다. 가상 머신과 컴파일러는 이런 종류의 IR을 기반으로 사용한다. 이는 IR을 다루는 다른 글들을 이해하는 데에도 도움이 될 것이다. 무엇이 진정한 IR인지에 대해서는 다소 모호함이 있다. 더 자세한 내용은 상위 수준의 글 “왜 중간 표현/언어를 사용할까?”에서 읽을 수 있다.