핍홀 최적화

핍홀 최적화(Peephole optimization)는 핍홀 또는 윈도우로 알려진 소규모 컴파일러 생성 명령어 집합에 대해 수행되는 최적화 기법으로, 해당 명령어를 더 나은 성능을 가진 논리적으로 동등한 집합으로 대체하는 것을 포함한다.

예시:

• 레지스터를 스택에 푸시한 다음 즉시 값을 레지스터로 다시 팝하는 대신, 두 명령어를 모두 제거한다.
• x에 2를 곱하는 대신 x << 1을 수행한다.
• 부동 소수점 레지스터에 8을 곱하는 대신 부동 소수점 레지스터의 지수에 3을 더한다.

핍홀 최적화라는 용어는 1965년에 윌리엄 마샬 매키먼이 도입했다.

대체

핍홀 최적화 대체에는 다음이 포함되지만 이에 국한되지 않는다:

• 널 시퀀스 – 불필요한 연산 삭제
• 연산 결합 – 여러 연산을 하나의 등가 연산으로 대체
• 대수 법칙 – 대수 법칙을 사용하여 명령어 단순화 또는 재정렬
• 특수 사례 명령어 – 특수 피연산자 사례를 위해 설계된 명령어 사용
• 주소 모드 연산 – 주소 모드를 사용하여 코드 단순화

구현

최신 컴파일러는 종종 패턴 매칭 알고리즘으로 핍홀 최적화를 구현한다.

예시

느린 명령어를 빠른 명령어로 대체하기

다음 자바 바이트코드:

aload 1
aload 1
mul

은 더 빠르게 실행되는 다음 코드로 대체될 수 있다:

aload 1
dup
mul

대부분의 핍홀 최적화와 마찬가지로, 이는 다른 명령어들의 상대적 효율성을 기반으로 한다. 이 경우, `dup` (스택의 맨 위를 복제하고 푸시하는)은 `aload` (지역 변수를 로드하고 스택에 푸시하는)보다 더 효율적인 것으로 알려져/가정된다.

불필요한 코드 제거하기

다음 소스 코드:

a = b + c;
d = a + e;

는 간단히 다음과 같이 컴파일된다:

MOV b, R0  ; b를 레지스터로 복사
ADD c, R0  ; c를 레지스터에 더함, 레지스터는 이제 b+c
MOV R0, a  ; 레지스터를 a로 복사
MOV a, R0  ; a를 레지스터로 복사
ADD e, R0  ; e를 레지스터에 더함, 레지스터는 이제 a+e [(b+c)+e]
MOV R0, d  ; 레지스터를 d로 복사

하지만 다음으로 최적화할 수 있다:

MOV b, R0  ; b를 레지스터로 복사
ADD c, R0  ; c를 레지스터에 더함, 이는 이제 b+c (a)
MOV R0, a  ; 레지스터를 a로 복사
ADD e, R0  ; e를 레지스터에 더함, 이는 이제 b+c+e [(a)+e]
MOV R0, d  ; 레지스터를 d로 복사

불필요한 스택 명령어 제거하기

컴파일러가 서브루틴을 호출하기 전에 레지스터를 스택에 저장하고 반환할 때 복원하는 경우, 연속적인 서브루틴 호출에는 중복된 스택 명령어가 있을 수 있다.

컴파일러가 각 프로시저 호출에 대해 다음 Z80 명령어를 생성한다고 가정하자:

PUSH AF
PUSH BC
PUSH DE
PUSH HL
CALL _ADDR
POP HL
POP DE
POP BC
POP AF

두 개의 연속적인 서브루틴 호출이 있다면 다음과 같이 보일 것이다:

PUSH AF
PUSH BC
PUSH DE
PUSH HL
CALL _ADDR1
POP HL
POP DE
POP BC
POP AF
PUSH AF
PUSH BC
PUSH DE
PUSH HL
CALL _ADDR2
POP HL
POP DE
POP BC
POP AF

동일한 레지스터에 대해 POP regs 뒤에 PUSH가 오는 시퀀스는 일반적으로 중복된다. 중복되는 경우, 핍홀 최적화는 이 명령어들을 제거할 것이다. 이 예시에서는 핍홀에 또 다른 중복 POP/PUSH 쌍이 나타나게 되고, 이들은 차례로 제거될 것이다. 서브루틴 _ADDR2가 이전 레지스터 값에 의존하지 않는다고 가정하면, 위 예시의 모든 불필요한 코드를 제거하면 결국 다음 코드가 남게 될 것이다:

PUSH AF
PUSH BC
PUSH DE
PUSH HL
CALL _ADDR1
CALL _ADDR2
POP HL
POP DE
POP BC
POP AF

같이 보기

• 오브젝트 코드 최적화, 일반적인 알고리즘 효율성과의 관련성 논의
• 케이펙스 코퍼레이션 – 초기 메인프레임 오브젝트 코드 최적화기인 코볼 프로그램 최적화기 생산 (IBM 코볼용)
• 슈퍼 최적화
• 디지털 리서치 XLT86, 최적화 어셈블리 소스 대 소스 컴파일러

외부 링크

• 크리스토퍼 W. 프레이저의 copt 범용 핍홀 최적화기
• 원본 논문