공통 부분식 제거

컴파일러 이론에서 공통 부분식 제거(Common subexpression elimination, CSE)는 동일한 식의 인스턴스를 찾고(즉, 모두 동일한 값으로 평가됨), 계산된 값을 포함하는 단일 변수로 대체하는 것이 가치가 있는지 분석하는 컴파일러 최적화이다.

 예시 
다음 코드에서:

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

코드를 다음과 같이 변환하는 것이 가치가 있을 수 있다.

 tmp = b * c;
 a = tmp + g;
 d = tmp * e;

tmp를 저장하고 검색하는 비용이 b * c를 추가로 계산하는 비용보다 적은 경우이다.

 원리 
CSE를 수행할 가능성은 사용 가능한 식 분석(일종의 데이터 흐름 분석)을 기반으로 한다. 식 b*c는 프로그램의 지점 p에서 다음 경우에 사용 가능하다.
 초기 노드에서 p까지의 모든 경로가 p에 도달하기 전에 b*c를 평가하고,
 평가 후 p 전에 b 또는 c에 대한 할당이 없는 경우.

옵티마이저가 수행하는 비용/편익 분석은 tmp에 저장하는 비용이 곱셈 비용보다 적은지 계산한다. 실제로 어떤 값이 어떤 레지스터에 저장되어 있는지와 같은 다른 요인들도 중요하다.

컴파일러 개발자들은 두 가지 종류의 CSE를 구분한다.
 지역 공통 부분식 제거는 단일 기본 블록 내에서 작동한다.
 전역 공통 부분식 제거는 전체 프로시저에 대해 작동한다.
두 가지 모두 프로그램의 어떤 지점에서 어떤 식이 사용 가능한지에 대한 데이터 흐름 분석에 의존한다.

 이점 
CSE를 수행하는 이점은 매우 커서 일반적으로 사용되는 최적화이다.

위 예시와 같은 간단한 경우에 프로그래머는 코드를 작성하면서 중복 식을 수동으로 제거할 수 있다. CSE의 가장 큰 원천은 컴파일러가 생성하는 중간 코드 시퀀스인데, 예를 들어 배열 인덱싱 계산과 같이 개발자가 수동으로 개입할 수 없는 경우이다. 어떤 경우에는 언어 기능이 많은 중복 식을 생성할 수 있다. 예를 들어, C 매크로의 경우, 매크로 확장이 원래 소스 코드에서는 명확하지 않은 공통 부분식을 초래할 수 있다.

컴파일러는 값을 저장하기 위해 생성되는 임시 변수의 수를 신중하게 결정해야 한다. 과도한 수의 임시 값은 레지스터 압력을 생성하여 메모리로 레지스터 스필링을 초래할 수 있으며, 이는 필요할 때 단순히 산술 결과를 재계산하는 것보다 더 오래 걸릴 수 있다.

 같이 보기 
 전역 값 번호 매기기
 루프 불변 코드 이동

 각주 

 스티븐 S. 머치닉, Advanced Compiler Design and Implementation (모건 카우프만, 1997) pp. 378–396
 존 코크. "Global Common Subexpression Elimination." Proceedings of a Symposium on Compiler Construction, ACM SIGPLAN Notices 5(7), July 1970, pages 850–856.
 Briggs, Preston, Cooper, Keith D., and Simpson, L. Taylor. "Value Numbering." Software-Practice and Experience, 27(6), June 1997, pages 701-724.

분류:컴파일러 최적화