의존성 분석
Dependence analysis컴파일러 이론에서 의존성 분석은 문장/명령어 사이의 실행 순서 제약을 생성한다.대략적으로 S2보다 먼저 S1을 실행해야 할 경우에는 S1에 따라 스테이트먼트 S2가 달라진다.크게는 제어 의존성과 데이터 의존성의 두 가지 클래스가 있습니다.
의존관계 분석은 스테이트먼트의 순서를 변경해도 안전한지 또는 병렬화를 실시해도 안전한지를 판단합니다.
종속성을 제어하다
제어 의존성은 이전 명령이 실행될 수 있는 방식으로 평가될 경우 프로그램 명령이 실행되는 상황입니다.
스테이트먼트 S2는 S1에 의해 조건부로 S2의 실행이 보호되는 경우에만 S1( 로 에 의존한 제어이다.이러한 제어 의존성의 예를 다음에 나타냅니다.
S1 if x > 2 goto L1 S2 y : = 3 S3 L1 : z : = y + 1
여기서 S2는 S1의 술어가 false일 경우에만 실행됩니다.
자세한 내용은 데이터 종속성을 참조하십시오.
data 의존관계
데이터 의존성은 동일한 리소스에 액세스하거나 수정하는 두 개의 문장에서 발생합니다.
흐름(True) 의존성
스테이트먼트 S2는 S1이 S2가 판독하는 자원을 변경해, S1이 실행 시에 S2보다 선행하는 경우에만 S1( f됨)에 의존하는 흐름이다.다음으로 흐름 의존성의 예를 나타냅니다(RAW: 쓰기 후 읽기).
S1 x := 10 S2 y := x + c
안티펜던트
스테이트먼트 S2는 S1이 판독하는 자원을 S2가 변경해, S1이 실행 시에 S2에 선행하는 경우에만 S1(한다.다음으로 안티펜던트(WAR: 읽기 후 쓰기)의 예를 나타냅니다.
S1 x : = y + c S2 y : = 10
여기서 S2는 다음 값을 설정합니다.y단, S1은 이전 값을 읽습니다.y.
출력 의존성
S1과 S2가 동일한 자원을 수정하고, S1이 실행 시에 S2에 선행하는 경우에만 S1( S2로)에 의존하여 스테이트먼트 S2를 출력한다.다음으로 출력 의존성의 예를 나타냅니다(WAW: 쓰기 후 쓰기).
S1 x : = 10 S2 x : = 20
여기서 S2와 S1은 모두 변수를 설정합니다.x.
입력 의존성
S1과 S2가 같은 자원을 읽고 S1이 실행 시에 S2에 선행하는 경우에만 S1에 의존하여 스테이트먼트 S2를 입력한다( i \ \ \ ^ { } \ ） 。입력 의존성의 예를 다음에 나타냅니다(RAR: Read-After-Read).
S1 y : = x + 3 S2 z : = x + 5
여기서 S2와 S1은 모두 변수에 액세스합니다.x이 의존성에 의해 재주문이 금지되는 것은 아닙니다.
루프 의존 관계
루프 내 의존관계 계산 문제는 중대하고 중요하지 않은 문제이며, 여기에 제시된 의존관계 프레임워크를 확장하는 루프 의존관계 분석에 의해 해결된다.
「 」를 참조해 주세요.
추가 정보
- Cooper, Keith D.; Torczon, Linda. (2005). Engineering a Compiler. Morgan Kaufmann. ISBN 1-55860-698-X.
- Kennedy, Ken; Allen, Randy. (2001). Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann. ISBN 1-55860-286-0.
- Muchnick, Steven S. (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann. ISBN 1-55860-320-4.
