핍홀 최적화(Peephole optimization)는 컴파일러 설계 분야에서 사용되는 코드 최적화 기법 중 하나이다. 생성된 목적 코드(중간 코드 또는 기계어)의 작은 연속 영역을 '핍홀(peephole)' 또는 '윈도우(window)'라고 부르며, 해당 영역 내의 명령어 집합을 검사하여 더 나은 성능을 가진 논리적으로 동등한 명령어 집합으로 대체하는 방식으로 동작한다.
개요
핍홀 최적화는 목적 코드 생성 단계 이후의 후처리 과정에서 적용되는 국소적(local) 최적화 기법이다. 하나의 핍홀 내부의 명령어들만을 대상으로 하므로, 전체 프로그램의 제어 흐름이나 데이터 흐름을 종합적으로 분석하는 전역 최적화와는 성격이 다르다. 일반적으로 한 번의 최적화로 개선된 코드 시퀀스는 다시 핍홀로 간주되어 연속적인 추가 최적화가 가능하며, 이 과정은 더 이상 개선할 부분이 없을 때까지 반복될 수 있다.
역사
핍홀 최적화라는 용어는 1965년 윌리엄 마샬 매키먼(William Marshall McKeeman)이 《Communications of the ACM》에 발표한 논문에서 처음 도입한 것으로 알려져 있다.
주요 최적화 기법
핍홀 최적화에서 주로 수행되는 대체 작업은 다음과 같은 유형으로 분류된다.
- 불필요한 연산 제거: 레지스터를 스택에 푸시한 뒤 곧바로 다시 팝하는 등 실질적인 효과가 없는 명령어 시퀀스를 제거한다.
- 연산 결합: 여러 개의 명령어를 하나의 등가 명령어로 대체한다.
- 대수 법칙 활용: 대수적 성질을 이용하여 명령어를 단순화하거나 재배열한다.
- 특수 명령어 사용: 특정 피연산자 상황에 최적화된 전용 명령어를 활용한다.
- 주소 모드 활용: 특정 주소 지정 방식을 사용하여 코드를 단순화한다.
예시
느린 명령어를 빠른 명령어로 대체
자바 바이트코드에서 다음과 같은 시퀀스
aload 1
aload 1
mul
는 dup 명령어(스택 최상위 값을 복제)를 활용한 다음 코드로 대체할 수 있다.
aload 1
dup
mul
이는 dup이 aload보다 효율적이라는 가정에 기반한다.
불필요한 스택 연산 제거
서브루틴 호출 전후에 반복적으로 스택에 레지스터를 저장하고 복원하는 패턴이 연속될 경우, 중복되는 PUSH/POP 쌍을 제거할 수 있다. 예를 들어 서로 다른 두 서브루틴을 연속 호출할 때, 첫 호출의 POP 시퀀스와 두 번째 호출의 PUSH 시퀀스가 동일한 레지스터를 대상으로 한다면 해당 부분을 생략할 수 있다.
구현
현대의 컴파일러들은 핍홀 최적화를 주로 패턴 매칭 알고리즘으로 구현한다. 특정한 명령어 시퀀스 패턴을 정의해 두고, 생성된 코드에서 해당 패턴이 나타나면 미리 설계된 최적화 규칙을 적용하는 방식이다.
한계
핍홀 최적화는 각 핍홀 내부의 국소적 정보만을 바탕으로 판단하기 때문에, 프로그램 전체에 걸친 전역적 최적화에는 도달하기 어렵다는 한계가 있다. 또한 최적화 규칙의 적용 순서와 규칙 추가에 따른 복잡도 문제가 제기되기도 한다.
같이 보기
- 객체 코드 최적화(Object code optimization)
- 슈퍼 최적화(Superoptimization)
- 컴파일러 최적화
