Common subexpression elimination (CSE)
Common subexpression elimination (CSE)
Common subexpression elimination(CSE, 공통 부분식 제거)는 프로그램 내에서 동일한 값을 계산하는 중복된 표현식들을 찾아내고, 이를 단일 변수로 대체하여 중복 계산을 피하는 컴파일러 최적화 기술이다.
예시
다음과 같은 코드가 있을 때:
a = b * c + g;
d = b * c * e;
컴파일러는 이를 다음과 같이 변환할 수 있다.
tmp = b * c;
a = tmp + g;
d = tmp * e;
이 변환은 $tmp$ 값을 저장하고 불러오는 비용이 $b \times c$를 한 번 더 계산하는 비용보다 적을 때 가치가 있다.
작동 원리
CSE를 수행할 수 있는지 여부는 가용 표현식 분석(Available Expression Analysis)이라는 데이터 흐름 분석 기법을 바탕으로 한다.
특정 지점 $p$에서 표현식 $b \times c$가 가용하다는 것은 다음 조건이 충족됨을 의미한다.
- 프로그램 시작부터 $p$에 이르는 모든 경로에서 $b \times c$가 이미 계산되었어야 한다.
- 마지막 계산 이후 $p$에 도달하기 전까지 변수 $b$나 $c$의 값이 변경되지 않아야 한다.
최적화 도구는 단순히 산술 연산 비용뿐만 아니라, 어떤 값이 어느 레지스터에 보관되어 있는지 등의 다양한 요소를 고려하여 비용/이익 분석을 수행한다.
Three-Address Code 로 변환을 해놓으면 컴파일러가 공통 부분식을 쉽게 찾아낼 수 있다.
CSE의 종류
CSE를 크게 두 가지로 분류한다.
지역 공통 부분식 제거 (Local CSE): 단일 기본 블록(Basic Block) 내에서만 작동한다. 가장 기본적인 최적화 단계에서 실행된다.
전역 공통 부분식 제거 (Global CSE): 절차(Procedure) 전체를 대상으로 작동한다. 더 높은 성능 최적화가 필요할 때 실행된다.
두 방식 모두 데이터 흐름 분석을 통해 특정 지점에서 어떤 표현식을 사용할 수 있는지 파악하는 원리를 사용한다.
장점 및 특징
CSE는 매우 효과적이어서 현대 컴파일러에서 흔히 사용되는 최적화이다.
수동 vs 자동: 간단한 경우 개발자가 직접 중복 코드를 정리할 수 있지만, 배열 인덱스 계산과 같이 컴파일러가 중간 코드를 생성하는 과정에서 발생하는 중복은 개발자가 직접 손대기 어렵다. 이때 CSE의 진가가 발휘된다.
언어적 요인: C 언어의 매크로처럼 확장 후에 소스 코드상에서는 보이지 않던 중복 식이 대량으로 발생하는 경우에도 매우 유용하다.
주의사항 (레지스터 압박)
컴파일러는 결과값을 담아둘 임시 변수(Temporary)의 개수를 신중하게 결정해야 한다. 임시 변수가 너무 많아지면 레지스터 압박(Register Pressure)이 생겨 값이 메모리로 밀려나게(Spilling) 되며, 이 경우 차라리 다시 계산하는 것보다 속도가 느려질 수 있다. (계산량을 줄이려다 오히려 메모리 접근 때문에 더 느려질 수 있다.)
실제 컴파일러의 전략
현대 컴파일러는 보통 다음과 같은 흐름으로 작동한다.
- Local CSE를 먼저 수행하여 각 기본 블록 안의 자질구레한 중복을 빠르게 제거한다.
- 이후 Global CSE를 수행하여 함수 전체를 관통하는 굵직한 중복을 찾아낸다.
- 최근에는 GVN(Global Value Numbering) 같은 더 강력한 기법이 Global CSE를 대신하거나 보완하기도 한다.