희소 조건부 상수 전파

컴퓨터 과학에서 희소 조건부 상수 전파(Sparse conditional constant propagation, SCCP)는 정적 단일 대입 형식(SSA)으로 변환된 후 컴파일러에 자주 적용되는 최적화 기법이다. 이는 컴파일 시점에 계산될 수 있는 정적 값의 계산인 상수 폴딩을 전파한다. 더욱이, 이는 어떤 순서로든 또는 어떤 횟수로든 데드 코드 제거와 상수 전파를 개별적으로 적용하는 것보다 더 많은 상수 값과 따라서 더 많은 개선 기회를 찾을 수 있다.^[1]^[2]

이 알고리즘은 SSA 형식 코드의 추상 해석을 수행하여 작동한다. 추상 해석 중에는 일반적으로 값에 대한 평탄한 격자와 SSA 변수를 이 격자의 값에 매핑하는 전역 환경을 사용한다. 알고리즘의 핵심은 분기 명령어의 해석을 처리하는 방식에 있다. 분기 명령어를 만나면, 분기 조건은 조건에 있는 변수에 바인딩된 추상 값의 정밀도를 고려하여 가능한 한 최적으로 평가된다. 값들이 완벽하게 정밀하여(최상도 최하도 아닌) 추상 실행이 어느 방향으로 분기할지 결정할 수 있는 경우가 있을 수 있다. 값들이 상수가 아니거나 조건의 변수가 정의되지 않은 경우, 보수성을 유지하기 위해 두 분기 방향 모두를 취해야 한다.

추상 해석이 완료되면, 결코 도달하지 않은 명령어들은 데드 코드로 표시된다. 상수 값을 가진 것으로 발견된 SSA 변수들은 그 사용 지점에서 인라인될 수 있다(전파될 수 있다).

내용주

↑ Wegman, Mark N. and Zadeck, F. Kenneth. "Constant Propagation with Conditional Branches." ACM Transactions on Programming Languages and Systems, 13(2), April 1991, pages 181-210.
↑ Click, Clifford and Cooper, Keith. "Combining Analyses, Combining Optimizations", ACM Transactions on Programming Languages and Systems, 17(2), March 1995, pages 181-196

각주

Cooper, Keith D. and Torczon, Linda. Engineering a Compiler. Morgan Kaufmann. 2005.

[1] Wegman, Mark N. and Zadeck, F. Kenneth. "Constant Propagation with Conditional Branches." ACM Transactions on Programming Languages and Systems, 13(2), April 1991, pages 181-210.

[2] Click, Clifford and Cooper, Keith. "Combining Analyses, Combining Optimizations", ACM Transactions on Programming Languages and Systems, 17(2), March 1995, pages 181-196

[1]

[2]