Egloos | Log-in
F/OSS study
F/OSS study
[compiler] Sparse Conditional Constant Propagation
constant propagation은 컴파일러 최적화 기법의 하나로
컴파일 시점에 어떤 변수의 값이 상수임을 알 수 있다면
해당 변수 대신 상수를 직접 사용하도록 하는 것이다.
이로 인해 expression 전체가 상수가 된다면 이를 컴파일 시에 계산한 후
그 결과를 직접 이용할 수 있게 된다. (constant folding)

constant propagation의 구현은 lattice를 이용한다.
integer constant propagation (ICP) lattice는 3-level로 구성되며 각각은 다음과 같은 의미를 가진다.
  • top : (아직은) 값을 모르는 상수
  • bottom : 상수가 아니거나 상수라고 판단할 수 없는 변수
  • 그 외의 노드 : 모든 정수값 (+ 조건문의 결과를 저장하기 위한 true/false)
optimistic algorihtm은
모든 변수에 대한 lattice cell을 할당하고 이를 top으로 초기화한 후
해당 변수가 상수로 정의되면 lattice의 meet 연산을 수행하여 값을 갱신한다.

가장 간단한 방식으로는 (simple constant propagation)
함수의 flowgraph를 따라 entry 노드부터 순서대로 탐색하여
더 이상 lattice value가 변경되지 않을 때까지 반복하는 것이다.
만약 해당 노드의 predecessor가 둘 이상이고
둘 중 하나라도 변수를 재정의했다면 해당 변수의 lattice value에 meet 연산을 수행한다.

이를 좀 더 개선한 방식은 sparse (simple) constant propagation으로
SSA 형태의 flowgraph 상에서 동작하는 데
노드를 순차적으로 탐색하는 것이 아니라
각 변수에 대한 def-use chain (SSA edge)을 이용하여 노드를 탐색하여 실행 속도를 높일 수 있다.

함수 내의 모든 변수에 대한 expression을 계산하여
해당 변수의 값을 컴파일 시점에 알 수 없는 경우 (다른 입력을 받아야하는 경우, ...)
lattice value를 bottom으로 초기화하고,
만약 상수로 계산할 수 있다면 lattice value를 해당 상수로 초기화하고,
그렇지 않은 모든 노드들은 top으로 초기화한다.

그리고 lattice value가 top이 아닌 모드 노드들을 작업queue에 넣고
하나씩 꺼내어 SSA edge가 가리키는 노드에 대해 lattice meet 연산을 적용하여
expression을 다시 계산하고 만약 lattice value가 변경되었다면 SSA edge 상의 노드들을
작업queue에 추가하는 작업을 계속 반복한다.

하지만 위의 방법들은 conditional branch 노드에서 값을 잘못 계산할 여지가 있는데
만약 conditional branch의 각 노드에서 동일한 변수를 서로 다른 상수 값으로 정의한다면
이후의 path에서 해당 변수의 lattice value는 bottom이 되어 더 이상 사용할 수 없게 된다.

이를 개선하기 위한 방법이 conditional constant propagation이며
symbolic execution이라는 방식을 통해 노드가 실행 가능한지 아닌지를 판별한다.
기본적으로 single path로 실행되는 노드는 실행 가능하며
conditional 노드의 경우 condition expression을 컴파일 시점에 계산할 수 있다면
두 조건 중 하나 만이 실행 가능하므로 lattice value를 이용할 수 있게 된다.
(게다가 이러한 path는 unreachable code elimination을 적용하여 제거할 수 있다.)

sparse conditional constant propagation은
위의 두 가지 개선점을 모두 합친 것으로
SSA edge를 이용하여 변경되는 노드들의 lattice value를 빨리 전파시켜 계산할 수 있으며,
symbolic execution을 통한 conditional 노드의 처리로 인해 더 많은 변수를 상수로 판단할 수 있다.

=== 참고 문헌 ===
  • Wegman, Mark N. and Zadeck, F. Kenneth. "Constant Propagation with Conditional Branches."
  • Muchnick, Steven S. "Advanced Compiler Design and Implementation."
by namhyung | 2009/08/18 01:57 | General | 트랙백 | 덧글(0)
트랙백 주소 : http://studyfoss.egloos.com/tb/5084292
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]

:         :

:

비공개 덧글

◀ 이전 페이지 다음 페이지 ▶

카테고리
General
Application
System
Kernel
Book
Tips
태그
emacs linux vcs binutils gcc bash algorithm blktrace x86 elf script sed synchronization memory compiler patch git build kernel scm awk C computer-architecture SMP block-layer perf CAaQA3 documentation CARM glibc
전체보기
이글루 파인더

최근 등록된 덧글
informsi yang bagus dan b..
by agen qnc at 06/22
informasi yang bagus dan b..
by agen qnc at 06/22
informasi yang bagus dan b..
by agen qnc at 06/22
최근 등록된 트랙백
Tod's Ferrari Homme
by Tods Pas Cher,Kodak did ..
Mocassin Femme
by Mocassins Homme, I got so..
natural garcinia cambogia
by
rss

skin by jiinny


X