컴파일러 성능 향상의 핵심, 값 넘버링(Value Numbering) 기술

값 넘버링(Value Numbering)은 컴파일러 최적화 기법으로, 런타임 시 동일한 값을 생성하는 명령어를 식별하여 코드 중복을 제거함

지역 값 넘버링(Local Value Numbering)은 기본 블록(Basic Block) 내에서, 전역 값 넘버링(Global Value Numbering)은 제어 흐름(Control Flow)을 고려하여 최적화를 수행함

Maxine VM의 구현 방식을 통해 실제 컴파일러에서의 적용 사례를 제시하고, 순수 연산(Pure Operation)과 불순 연산(Impure Operation)의 차이점을 설명함

Dominator 개념을 활용한 전역 값 넘버링(Global Value Numbering) 구현과 메모리 상태 추적을 통한 불순 연산 최적화 가능성을 제시함

값 넘버링(Value Numbering)의 기본 원리

값 넘버링(Value Numbering)은 컴파일러 최적화의 핵심 기술로, 정적 단일 할당(SSA, Static Single Assignment) 형태의 중간 표현(IR, Intermediate Representation)에서 중복된 연산을 제거한다. 텍스트적으로 동일한 명령어라도 SSA 변환을 통해 각기 다른 값을 가질 수 있음을 강조하며, 컴파일 타임(Compile Time)에 동일한 값을 생성하는 명령어를 식별하여 재사용함으로써 성능을 향상시킨다. 특히, 해시 기반(Hash-based) 방식을 통해 명령어의 고유한 값을 계산하고, 동일한 해시 값을 가진 명령어를 비교하여 중복 여부를 판단한다.

지역 값 넘버링(LVN)과 전역 값 넘버링(GVN) 비교

지역 값 넘버링(LVN, Local Value Numbering)은 기본 블록(Basic Block) 내에서, 전역 값 넘버링(GVN, Global Value Numbering)은 제어 흐름(Control Flow)을 고려하여 최적화를 수행한다. LVN은 블록 내 명령어들을 순차적으로 처리하며, GVN은 지배 관계(Dominator Relationship)를 활용하여 여러 블록 간의 값 재사용을 가능하게 한다. Maxine VM의 GVN 구현은 지배 블록의 값 맵(Value Map)을 상속받아 사용하며, 이를 통해 코드 중복을 줄이고 성능을 개선한다.

순수 연산(Pure Operation)과 불순 연산(Impure Operation) 최적화

값 넘버링(Value Numbering)은 순수 연산(Pure Operation)에 주로 적용되지만, 불순 연산(Impure Operation)에 대한 최적화도 가능하다. 순수 연산은 외부 상태에 영향을 미치지 않는 연산이며, 불순 연산은 메모리 접근과 같은 외부 상태 변경을 포함한다. Maxine VM은 메모리 상태 추적을 통해 불순 연산에 대한 Load-Store Forwarding을 수행하여 중복된 LoadField 명령어를 제거한다. 이는 컴파일러가 힙(Heap) 상태를 추적하여 더 많은 최적화를 수행할 수 있음을 시사한다.

Dominator 기반 GVN 구현과 한계

Dominator 기반의 GVN 구현은 제어 흐름(Control Flow)이 복잡한 경우, 특히 분기(Split)와 합류(Join) 지점에서 어려움을 겪을 수 있다. 분기 지점에서는 각 분기 경로에서 계산된 값을 공유하기 어렵고, 합류 지점에서는 어떤 경로로 진입했는지 알 수 없기 때문이다. 이러한 문제를 해결하기 위해, 통합 해시 테이블(Unified Hash Table)을 사용하거나, 작업 목록(Worklist) 데이터 흐름 분석과 같은 다른 접근 방식이 제시된다. 또한, Cranelift와 같은 컴파일러는 스코프 해시 맵(Scoped Hash Map)을 사용하여 효율적으로 정보를 추적한다.