상수 폴딩

상수 폴딩(constant folding)과 상수 전파(constant propagation)는 많은 현대 컴파일러에서 사용되는 관련 컴파일러 최적화 기법이다.^[1] 희소 조건부 상수 전파로 알려진 상수 전파의 고급 형태는 상수를 더 정확하게 전파하고 동시에 불필요한 코드를 제거할 수 있다.

상수 폴딩

상수 폴딩은 런타임에 계산하는 대신 컴파일 타임에 상수 표현식을 인식하고 평가하는 과정이다. 상수 표현식의 항은 일반적으로 정수 리터럴 2와 같은 단순 리터럴이지만, 컴파일 타임에 값이 알려진 변수일 수도 있다. 다음 문장을 살펴보자.

i = 320 * 200 * 32;

대부분의 컴파일러는 이 문장에 대해 실제로 두 개의 곱셈 명령과 하나의 저장 명령을 생성하지 않는다. 대신 이러한 구문을 식별하고 컴파일 타임에 계산된 값(이 경우 2,048,000)으로 대체한다.

상수 폴딩은 산술 항등식을 활용할 수 있다. x가 숫자이면 컴파일러가 x의 값을 모르더라도 0 * x의 값은 0이다. (이것은 x가 무한대나 NaN일 수 있으므로 IEEE 부동소수점에서는 유효하지 않다는 점에 유의한다.)

상수 폴딩은 숫자 외에도 적용될 수 있다. 문자열 리터럴과 상수 문자열의 연결은 상수 폴딩될 수 있다. "abc" + "def"와 같은 코드는 "abcdef"로 대체될 수 있다.

상수 폴딩과 크로스 컴파일

크로스 컴파일러를 구현할 때 호스트 아키텍처의 산술 연산 동작이 대상 아키텍처의 동작과 일치하는지 확인해야 한다. 그렇지 않으면 상수 폴딩을 활성화하면 프로그램의 동작이 변경된다. 이는 부동소수점 연산의 경우 특히 중요하며, 정밀한 구현이 크게 다를 수 있다.

상수 전파

상수 전파는 컴파일 타임에 표현식에서 알려진 상수의 값을 대체하는 과정이다. 이러한 상수에는 위에 정의된 상수뿐만 아니라 상수 값에 적용된 내장 함수도 포함된다. 다음 의사 코드를 살펴보자.

int x = 14;
int y = 7 - x / 2;
return y * (28 / x + 2);

x를 전파하면 다음과 같다.

int x = 14;
int y = 7 - 14 / 2;
return y * (28 / 14 + 2);

계속 전파하면 다음과 같은 결과가 나온다 (이는 x와 y 모두에 대한 불필요한 코드 제거를 통해 추가로 최적화될 가능성이 높다.)

int x = 14;
int y = 0;
return 0;

상수 전파는 정의 도달 분석 결과를 사용하여 컴파일러에 구현된다. 변수의 모든 도달 정의가 동일한 할당(동일한 상수를 변수에 할당하는)인 경우 변수는 항상 동일한 값을 가지므로 상수로 대체될 수 있다.

상수 전파는 또한 조건 표현식이 컴파일 타임에 참 또는 거짓으로 평가되어 유일한 가능한 결과를 결정할 수 있는 경우 조건부 분기를 하나 이상의 무조건 명령문으로 단순화할 수 있다.

최적화의 작동 방식

상수 폴딩과 전파는 많은 단순화 및 감소를 달성하기 위해 일반적으로 함께 사용되며, 이러한 효과가 멈출 때까지 번갈아 가며 반복적으로 적용된다.

분석을 기다리는 알 수 없는 숫자를 반환하는 최적화되지 않은 다음 의사 코드를 살펴보자.

int a = 30;
int b = 9 - (a / 5);
int c = b * 4;

if (c > 10) {
   c = c - 10;
}
return c * (60 / a);

상수 전파를 한 번 적용한 다음 상수 폴딩을 적용하면 다음과 같다.

int a = 30;
int b = 3;
int c = b * 4;

if (c > 10) {
   c = c - 10;
}
return c * 2;

두 단계를 두 번 반복하면 다음과 같다.

int a = 30;
int b = 3;
int c = 12;

if (true) {
   c = 2;
}
return c * 2;

변수 a와 b의 모든 사용을 상수로 대체했으므로 컴파일러의 불필요한 코드 제거가 해당 변수에 적용되어 다음과 같이 남는다.

int c = 12;

if (true) {
   c = 2;
}
return c * 2;

(불리언 구성은 언어와 컴파일러마다 다르지만, 참의 상태, 원본 및 표현과 같은 세부 사항은 이러한 최적화 원칙에 영향을 미치지 않는다.)

전통적인 상수 전파는 더 이상의 최적화를 생성하지 않는다. 프로그램을 재구성하지 않는다.

그러나 유사한 최적화인 희소 조건부 상수 전파는 적절한 조건부 분기를 선택하고^[2] 항상 참인 조건부 테스트를 제거하여 더 나아간다. 따라서 변수 c는 불필요해지고 상수 연산만 남는다.

return 4;

만약 이 의사 코드가 함수 본문을 구성한다면, 컴파일러는 이 함수가 정수 상수 4로 평가된다는 것을 알게 되어 함수 호출을 4로 대체하고 프로그램 효율성을 더욱 높일 수 있다.

같이 보기

• 제어 흐름 그래프
• 사용-정의 체인 및 SSA 형식
• 복사 전파
• 공통 부분식 제거
• 부분 평가