사용 정의 체인

컴퓨터 과학에서 UD 체인(Use-Definition Chain, UD 체인)은 변수 U와 다른 개입 정의 없이 사용할 수 있는 변수의 모든 정의 D로 구성된 데이터 구조입니다.UD 체인은 일반적으로 변수에 값을 할당하는 것을 의미합니다.

UD 체인에 대응하는 것은 Definition-Use Chain(DU 체인)입니다.DU 체인은 변수의 정의 D와 그 정의에서 도달 가능한 모든 용도 U로 구성됩니다.이 정의에서는 다른 개입 정의가 없습니다.

UD 체인과 DU 체인은 모두 데이터 흐름 분석이라고 불리는 정적 코드 분석 형식을 사용하여 생성됩니다.프로그램 또는 서브프로그램의 use-def 및 def-use 체인을 아는 것은 지속적인 전파와 일반적인 서브 표현 제거를 포함한 많은 컴파일러 최적화의 전제 조건입니다.

목적

use-define 또는 define-use-chain을 만드는 것은 활성 분석의 한 단계이며, 따라서 코드를 통해 모든 변수의 논리적 표현을 식별하고 추적할 수 있습니다.

다음 코드 조각에 대해 생각해 보십시오.

 인트 x = 0;    /* A * /  x = x + y;    /* B * /  /* 1, x */의 일부 사용  x = 35;       /* C * /  /* 2, x*/의 일부 사용 

주의해 주세요x에는 3개의 포인트(A, B 및 C)에 값이 할당됩니다.단, "1"로 표시된 지점에서는 다음과 같은 use-def 체인이 사용됩니다.x는, 현재의 값이 회선B 로부터의 값(및 회선B 로의 값은 회선A 로부터의 값)을 나타내고 있을 필요가 있습니다.반대로, "2"로 표시된 지점에서는 다음과 같은 use-def 체인이 사용됩니다.x현재 값이 C행에서 와야 함을 나타냅니다.의 가치가 있기 때문에x블록 2는 블록 1 또는 그 이전의 정의에 의존하지 않습니다.x다른 변수가 될 수도 있습니다.실제로 말하면 다른 변수입니다.x2.

 인트 x = 0;    /* A * /  x = x + y;    /* B * /  /* 1, x */의 일부 사용  인트 x2 = 35;  /* C * /  /* 2, 일부 x2 사용 */ 

분할 과정x두 개의 개별 변수로 분할하는 것을 라이브 범위 분할이라고 합니다.정적 단일 할당 양식을 참조하십시오.

세우다

스테이트먼트 목록은 스테이트먼트 간의 강력한 순서를 결정합니다.

• 스테이트먼트는 다음 규칙을 사용하여 라벨링됩니다${\displaystyle .}s{\displaystyle }$ (${\displaystyle i}$) { $displaystyle$s ($i$ )$$。여기서 i는 [${\displaystyle 1,}$ n$]$ {$displaystyle [1, n]$}의 정수이며, n은 기본 블록의 스테이트먼트 수입니다.
• 변수는 이탤릭체로 식별됩니다(예: v,u 및 t).
• 모든 변수는 컨텍스트 또는 범위에 정의가 있는 것으로 가정합니다.(스태틱 단일 할당 형식에서는 각 체인에 단일 요소가 포함되어 있기 때문에 use-define 체인은 명시적입니다).

v와 같은 변수의 경우 선언은 V(이탈리아 대문자)로 식별되며, 선언은 s${\displaystyle }$( $)\displaystyle$s(0$)$로 식별됩니다.일반적으로 변수의 선언은 외부 범위(예: 전역 변수)에 있을 수 있습니다.

변수의 정의

변수 v가 s${\displaystyle }$(${\displaystyle j}$ )$${ $displaystyle$s ($j$ )$$$then{\displaystyle }$ s ( ( ( ${\displaystyle (,,,}$ （ j$）$ { $displaystyle s$( j ) a a 、 v v 、 v vation ( ( its its when when when when （ j ) when when when when when when 、 v when ( ( ( ( ( ( 、 1개 이상의 정의가 선언(또는 초기화)에 의해 이루어집니다.

변수 사용

만약, v, 따라 각형 강관의 계산서 s(j){\displaystyle s(j)}에 있는 경우 이런 말이 있고 나는 <(나는){\displaystyle s(나는)}가 어떻게 되고,'v'의 그것이 정의와 j와 최소(j− 나는){\displaystyle \min(j-i)}, s에서(j)이용하고 있다{\displaystyle s(j)}(혹은, 요컨대, 변수, v, 각형 강관은 sta일입니다.갖도록$ent{\displaystyle }$ s${\displaystyle }$(${\displaystyle j}$) { $displaystyle$$$s ($j$ )$$then 、 v ${\displaystyle s}$ s s s s${\displaystyle }$s $($j ${\displaystyle )}$로 사용합니다.

실행

스테이트먼트 $목록{\displaystyle }$ s${\displaystyle }$( $){displaystyle$ s$(i$의 순차적 실행과 스테이트먼트에서의 계산으로 관찰할 수 있는 j:

• i < j가 있는 ${\displaystyle 문}$ $s{\displaystyle }$( i$$) {$displaystyle$ s$(i)}$의 정의는 k j j가 있는 문 ${\displaystyle s}$ (${\displaystyle }$k )$${$displaystyle$ s$(k)}$에서 사용되는$$ 경우 j에서 활성화됩니다.스테이트먼트 i의 라이브 정의 집합은 A${\displaystyle }$($i)$ {$displaystyle$ A$(i)},$ 라이브$$ 정의의 수는${\displaystyle }$A (${\displaystyle i}$${\displaystyle )}$ {$displaystyle$A$($$i)$ $\}$로 ${\displaystyle 표시}$됩니다.${\displaystyle A}$ ${\displaystyle (}$i$)$ {$displaystyle$ A$(i$)}는$$ 단순하지만 강력한 개념입니다: 공간 복잡성 이론 및 접근 복잡성(I/O)의 실제 결과입니다.), 레지스터 할당 및 캐시 지역${\displaystyle \mathrm{이용}}$은 $A$( i$$)(\$displaystyle$ A$($$i)})$를 $기반$으로 합니다.
• $스테이트먼트{\displaystyle }$ s$)$의 정의({$displaystyle$s(i)})는 동일한 변수에 대해 이전의 정의($)\displaystyle$s$($$k))$를 모두 삭제합니다.

def-use-chain 실행 예시

이 예는 gcd를 찾기 위한 Java 알고리즘을 기반으로 합니다(이 함수의 기능을 이해하는 것은 중요하지 않습니다).

/** * @param(a, b) 제수를 계산하는 데 사용되는 값. * @return a와 b의 최대 공약수. */ 인트 gcd(인트 a, 인트 b) {      인트 c = a;     인트 d = b;      한다면 (c == 0)         돌아가다 d;     하는 동안에 (d != 0) {          한다면 (c > d)             c = c - d;         또 다른             d = d - c;     }      돌아가다 c;  } 

변수 d의 모든 def-use-chains를 확인하려면 다음 절차를 수행합니다.

1. 변수를 처음 정의한 시점을 검색합니다(쓰기 액세스).

   이 경우는 " 입니다.d=b(l.7)

2. 변수를 처음 읽을 때 검색합니다.

   이 경우는 " 입니다.return d"

3. 이 정보를 다음 스타일로 적어주세요.[ def-use-chain을 작성하는 변수의 이름, 구체적인 쓰기 액세스, 구체적인 읽기 액세스]

   이 경우 다음과 같습니다.[d, d=b, return d]

각 쓰기 액세스와 각 읽기 액세스(단, 그 반대는 아님)를 조합하는 형식으로 이러한 단계를 반복합니다.

결과는 다음과 같습니다.

 [d, d=b, 돌아가다 d]   [d, d=b, 하는 동안에(d!=0)]   [d, d=b, 한다면(c>d)]   [d, d=b, c=c-d]   [d, d=b, d=d-c]  [d, d=d-c, 하는 동안에(d!=0)]   [d, d=d-c, 한다면(c>d)]   [d, d=d-c, c=c-d]   [d, d=d-c, d=d-c] 

변수가 시간에 따라 변경되면 주의해야 합니다.

예를 들어 다음과 같습니다.소스코드의 7행부터 13행까지,d는 재정의/변경되지 않았습니다.14행에서는 d를 재정의할 수 있다.그렇기 때문에 d에 대한 이 쓰기 액세스와 도달 가능한 모든 읽기 액세스를 재결합해야 합니다.이 경우 10행 이후의 코드만 관련됩니다.예를 들어, 회선 7은 다시 도달할 수 없습니다.이해를 돕기 위해 다음과 같은 두 가지 변수를 생각할 수 있습니다.

 [d1, d1=b, 돌아가다 d1]   [d1, d1=b, 하는 동안에(d1!=0)]   [d1, d1=b, 한다면(c>d1)]   [d1, d1=b, c=c-d1]   [d1, d1=b, d1=d1-c]  [d2, d2=d2-c, 하는 동안에(d2!=0)]   [d2, d2=d2-c, 한다면(c>d2)]   [d2, d2=d2-c, c=c-d2]   [d2, d2=d2-c, d2=d2-c] 

그 결과, 이런 것을 얻을 수 있습니다.변수 d1은 b로 대체됩니다.

/** * @param(a, b) 제수를 계산하는 데 사용되는 값. * @return a와 b의 최대 공약수. **/ 인트 gcd(인트 a, 인트 b) {     인트 c = a;     인트 d;      한다면 (c == 0)         돌아가다 b;     한다면 (b != 0) {         한다면 (c > b) {             c = c - b;             d = b;         }         또 다른             d = b - c;         하는 동안에 (d != 0) {              한다면 (c > d)                 c = c - d;             또 다른                 d = d - c;         }     }      돌아가다 c;  } 

use-def(또는 ud) 체인 구축 방법

이 섹션은 독자들에게 혼란스럽거나 불분명할 수 있습니다. 섹션을 명확하게 하는 데 도움을 주세요. 토크 페이지에 이 건에 대한 논의가 있을 수 있습니다.(2007년 1월) (이 템플릿메시지를 삭제하는 방법과 타이밍에 대해 설명합니다)

1. $스테이트먼트{\displaystyle }$s ( ${\displaystyle 0}$) {$displaystyle s$(0$)}$의 정의를 설정합니다.
2. [${\displaystyle 1}$, $]$ {$displaystyle [1,n$의${\displaystyle }$각 i에 대해 $스테이트먼트{\displaystyle }$ s$)$ {$displaystyle$ s$(i)}$에서 사용할 라이브 정의를 찾습니다.
3. 정의와 용도를 연결하다
4. $s{\displaystyle }$(${\displaystyle i}$ )$${$display$ s$(i$ 문을 정의문으로 설정합니다.
5. 이전 정의 삭제

이 알고리즘에서는, 다음의 2개의 것이 실현됩니다.

1. 변수 사용 및 정의에 따라 DAG(Directed Acyclic Graph)가 생성됩니다.DAG는 할당문 간의 데이터 종속성 및 부분 순서(따라서 문 간의 병렬화)를 지정합니다.
2. $스테이트먼트{\displaystyle }$ s$)$ {$displaystyle$ s$(i)}$에 도달하면 라이브 변수 할당 목록이 나타납니다.예를 들어 하나의 할당만 활성 상태인 경우 지속적인 전파가 사용될 수 있습니다.