사용-정의 체인 문서 원본 보기

{{위키데이터 속성 추적}}
[[컴퓨터 과학]] 내에서 '''사용-정의 체인''' ( ''UD Chain'' )은 [[변수 (컴퓨터 과학)|변수]]의 사용인 U와 해당 변수의 다른 정의의 개입없이, 그 사용에 접근 가능한, 모든 정의인 D로 구성된 [[자료 구조|데이터 구조]]이다.  UD 체인은 일반적으로 어떤 값을 변수에 할당하는 것을 의미한다.

''UD Chain'' 의 대응되는 개념으로 '''정의-사용 체인''' ( ''DU Chain'' )이 있다. 이것은 변수의 정의인 D와 다른 정의의 개입없이, 그 정의에서 도달할 수 있는 모든 사용인 U로 구성된다.

UD 및 DU Chain은 모두 [[데이터 흐름 분석]]으로 알려진 [[정적 프로그램 분석|정적 코드 분석]] 형식을 사용하여 생성된다. 프로그램 또는 하위 프로그램에 대한 사용-정의 및 정의-사용 체인을 파악하는 것은 상수 전파 및 공통 하위 표현식 제거를 포함하여 많은 컴파일러 최적화의 전제 조건이다.

== 목적 ==
사용-정의 또는 정의-사용 체인을 만드는 것은, 모든 변수의 논리적인 표현이 코드를 통해 식별되고 추적될 수 있도록 하는 변수 유효성 분석의 첫 단계이다.

다음의 코드를 보자.<syntaxhighlight lang="c">
 int x = 0;    /* A */
 x = x + y;    /* B */
 /* 1, x 의 사용 */
 x = 35;       /* C */
 /* 2, x 의 또다른 사용*/
</syntaxhighlight><code>x</code> 의 값이 위 코드의 A, B, C 총 세 지점에서 할당되고 있다. 위의 코드 중 '1'로 표현된 지점에서는 사용-정의 체인이 <code>x</code> 의 값이 B에서 왔다고 표시해야한다. (또한, 그 값은 다시 A로부터 왔음을 표시해야 함.) 그러나 반대로, '2' 지점에서의 <code>x</code> 는 새로운 값을 할당받고 있지만, 그것은 앞서 '1'지점과 그 이전의 모든 코드의 <code>x</code> 와는 독립적인 값을 할당받고 있다. 그로므로 지금의 <code>x</code> 는 이전과는 완전히 다른 변수라고 볼 수 있다. 그것을 이제 <code>x2</code> 라고 부르자.<syntaxhighlight lang="c">
 int x = 0;    /* A */
 x = x + y;    /* B */
 /* 1, x 의 사용 */
 int x2 = 35;       /* C */
 /* 2, x2 의 사용*/
</syntaxhighlight>x를 이렇게 두 개의 다른 변수로 분리하는 것을, 유효 범위 분리(live range splitting) 라고 한다. 정적 단일 할당 형식(static single assignment form)도 참고할 것.

== 사전 설명 ==
Statements의 목록은 Statements사이에 엄격한 순서를 정의한다.

''(역주 : statements는 간단히 코드 한 줄이라고 이해해도 좋다.)''

* Statements는 <math>s(i)</math>로 표현된다. 여기서 i는 1과 n 사이의 정수이고, n은 basic block에 포함된 Statements의 개수이다.
* 변수는 이탤릭체로 표현된다(예: ''v'', ''u'' 및 ''t'' ).
* 모든 변수는 컨텍스트 또는 스코프내에 정의가 있다고 가정한다. ( 정적 단일 할당 형식에서는 각 체인에는 단일 요소가 포함되어 있으므로 use-define 체인이 명확하게 나타난다.)

''v'' 와 같은 변수의 선언은 ''V'' (이탤릭체 대문자)로 표현되며, 또한 선언은 {{tmath|s(0)}}로 간단히 표현되기도 한다. 일반적으로 변수 선언은 외부 범위(예: [[전역 변수]] )에 있을 수 있다.

=== 변수의 정의 ===
{{tmath|s(j)}}인 대입 연산의 statements 에서, 변수 ''v''가 등호('=')의 왼쪽에 존재하는 경우, {{tmath|s(j)}}를 ''v''의 정의라고 한다. 모든 변수는 최소한 한번의 정의를 가진다. (또는 초기화)

=== 변수 사용 ===
{{tmath|s(j)}}의 statements에서 변수 ''v''가 statements의 오른쪽 매개변수(RHS)로서 존재한다고 하자.

i < j 이고 {{tmath|\min(j-i)}} 인 i에 대해, {{tmath|s(i)}}가 ''v''의 정의라면, {{tmath|s(j)}}는 ''v''의 사용이다.

(단순히, 어떤 변수 ''v''가 {{tmath|s(j)}}에서 statement의 오른쪽 매개변수라면, {{tmath|s(j)}}에서 ''v''가 사용되었다고 한다.)

여러 statements가 연속적으로 실행된다고 해보자. 이때 {{tmath|s(i)}}와 {{tmath|s(j)}} statement들 간에서 어떤 일이 이루어질지 관찰해보자.

* {{tmath|s(i)}}에서 정의가 되었다고 하자. 그러면 i < j일때, j에서는 아직 유효하다고 할 수 있어요, 또 k >= j 인 statement인, {{tmath|s(k)}}가 존재한다고도 해보자. 또, 다시 {{tmath|s(i)}}의 순간에 살아있는 모든 정의를 {{tmath|A(i)}}라고 하자. 또, 이 모든 정의의 개수는 <math>|A(i)|</math>라고 나타낼 수도 있다. ({{tmath|A(i)}}는 간단하지만, 아주 중요한 개념이다. 이론적으로나 실용적인 측면에서나, [[:en:Space_complexity_theory|공간 복잡도 이론]], 복잡도 접근(I/O 복잡도), [[:en:Register_allocation|레지스터 할당]], 그리고 [[:en:Memory_locality|캐시 로컬리티]]활용이 모두 {{tmath|A(i)}}를 기반으로 한다.)
* 정의하는 statement인 {{tmath|s(i)}} 는 같은 변수에 대해 정의된 모든 {{tmath|s(k)}}를 '''죽인다'''. (k < i)

== 정의-사용 체인의 예시 ==
이 예제는 [[:en:Greatest_common_divisor|gcd(최대공약수)]]를 찾는 Java 알고리즘이다. (어떻게 이 함수가 동작하는 지는 알 필요는 없다.)<syntaxhighlight lang="c">
/**
 * @매개 변수인 a, b는 공약수를 찾으려고 하는 두 숫자들임
 * @반환 값은 a와 b의 최대 공약수임
 */
int gcd(int a, int b) {
    int c = a;
    int d = b;
    if (c == 0)
        return d;
    while (d != 0) {
        if (c > d)
            c = c - d;
        else
            d = d - c;
    }
    return c;
}
</syntaxhighlight>변수 d에 대한 모든 정의-사용 체인들을 찾기 위하여 아래의 단계들을 거친다.

# 변수가 언제 처음 정의되었는지 찾는다 (쓰기 접근).
#: 이 예제에서는 7번 줄의 "d = b"가 된다.
# 해당 변수를 처음으로 읽었을 때를 찾는다 (읽기 접근).
#: 이 예제에서는 9번 줄의 "return d"가 된다.
# 1번과 2번에서 찾은 정보를 토대로, 정의-사용 체인에 다음의 형식으로 해당 정보를 저장한다. : [체인을 만들고자 하는 변수의 이름, 변수의 첫 쓰기, 변수의 첫 읽기]
#: 이 예제에서는 다음과 같다. : [d, d=b, return d]

읽기 접근과 쓰기 접근을 서로 짝짓는 방법으로, 위의 단계를 계속해서 반복한다. (그러나 반대의 경우는 하지 않는다.)

이 예제에서 그 결과는 아래와 같다.<syntaxhighlight lang="c">
 [d, d=b, return d]
 [d, d=b, while(d!=0)]
 [d, d=b, if(c>d)]
 [d, d=b, c=c-d]
 [d, d=b, d=d-c]
 [d, d=d-c, while(d!=0)]
 [d, d=d-c, if(c>d)]
 [d, d=d-c, c=c-d]
 [d, d=d-c, d=d-c]
</syntaxhighlight>변수가 시간에 따라 변경되는 경우 주의해야 한다.

위 예제에서, 소스 코드의 7행에서 13행까지, {{모노|d}}는 변경되거나 재정의 되지 않는다. 그러나 14행에서 d가 재정의된다. 이것이 이 쓰기 접근을 d가 접근가능한 모든 읽기 접근들에 다시 결합해야 하는 이유이다.


위 상황에서, 10행 이후의 코드만 관련이 있다. 예를 들어 7번 줄의 코드는 다시는 접근될 수 없다. 이해를 돕기 위해 d 변수를 두 개로 분리해볼 수 있다. <syntaxhighlight lang="c">
 [d1, d1=b, return d1]
 [d1, d1=b, while(d1!=0)]
 [d1, d1=b, if(c>d1)]
 [d1, d1=b, c=c-d1]
 [d1, d1=b, d1=d1-c]
 [d2, d2=d2-c, while(d2!=0)]
 [d2, d2=d2-c, if(c>d2)]
 [d2, d2=d2-c, c=c-d2]
 [d2, d2=d2-c, d2=d2-c]
</syntaxhighlight>결과적으로 d1을 b로 대체하면 아래와 같은 코드를 얻을 수 있다. <syntaxhighlight lang="c">
/**
 * @매개 변수인 a, b는 공약수를 찾으려고 하는 두 숫자들임
 * @반환 값은 a와 b의 최대 공약수임
 **/
int gcd(int a, int b) {
    int c = a;
    int d;
    if (c == 0)
        return b;
    if (b != 0) {
        if (c > b) {
            c = c - b;
            d = b;
        }
        else
            d = b - c;
        while (d != 0) {
            if (c > d)
                c = c - d;
            else
                d = d - c;
        }
    }
    return c;
}
</syntaxhighlight>

== 사용-정의 체인을 구축하는 방법 ==

# statement {{tmath|s(0)}}에 정의들을 위치시킨다.
# 1과 n사이의 i 중에서, statement {{tmath|s(i)}}내에 사용을 가진 유효한 정의를 찾는다.
# 정의와 사용을 서로 연결한다.
# {{tmath|s(i)}}를 정의 statement로 설정한다.
# 이전의 모든 정의들을 '''죽인'''다.

이 알고리즘을 사용하면 두 가지 것들이 성취된다.

# DAG( [[유향 비순환 그래프|Directed Acyclic Graph]] )가 변수의 사용과 정의 간에서 만들어진다. DAG는 statement간의 [[부분 순서 집합|부분 순서]] (따라서 명령문 간의 병렬성)뿐만 아니라, 데이터의 종속성까지도 특정할 수 있게 된다.
# statement {{tmath|s(i)}}가 도달되는 경우에, 유효 변수의 할당 목록이 존재하게 된다. 만약 오직 하나의 유효한 할당만이 존재한다면, 상수 전파가 사용될 수 있다.
[[분류:데이터 흐름 분석]]
[[분류:컴파일러 최적화]]