사용-정의 체인
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
사용-정의 체인(define-use chain)은 변수의 논리적 표현을 식별하고 코드 추적을 용이하게 하기 위한 생존 분석의 한 단계이다. 이는 변수가 값을 할당받는 지점(정의)과 해당 값을 사용하는 지점(사용) 간의 관계를 나타낸다. 사용-정의 체인은 코드의 각 문장(statement)에서 변수의 정의와 사용을 분석하며, 변수의 정의가 이루어진 시점부터 해당 정의가 유효한 범위 내에서 사용되는 모든 경우를 추적한다. 이러한 분석을 통해 데이터 종속성을 파악하고, 코드 최적화 및 분석에 활용할 수 있다.
더 읽어볼만한 페이지
| 사용-정의 체인 |
|---|
2. 목적
사용-정의 체인 또는 정의-사용 체인을 만드는 것은 변수 유효성 분석의 첫 단계로, 코드 내에서 모든 변수의 논리적 표현을 식별하고 추적할 수 있게 한다. 이를 통해 코드 최적화 및 분석이 가능해진다.
코드의 각 줄(Statements)은 엄격한 순서로 정의된다. Statements는 로 표현되는데, 여기서 i는 1과 n 사이의 정수이고, n은 basic block에 포함된 Statements의 개수이다. 변수는 ''v'', ''u'', ''t'' 와 같이 이탤릭체로 표현되며, 모든 변수는 컨텍스트 또는 스코프 내에 정의가 있다고 가정한다. ''v'' 와 같은 변수의 선언은 ''V'' (이탤릭체 대문자)로 표현되기도 하고, 로 간단히 표현되기도 한다. 일반적으로 변수 선언은 전역 변수와 같이 외부 범위에 있을 수 있다.
다음 코드를 보자.
```c
int x = 0; /* A */
x = x + y; /* B */
/* 1, x 의 사용 */
x = 35; /* C */
/* 2, x 의 또다른 사용*/
```
위 코드에서 `x`의 값은 A, B, C 세 지점에서 할당된다. '1'로 표시된 지점에서 사용-정의 체인은 `x`의 값이 B에서 왔다고 표시해야 한다. (또한 그 값은 다시 A에서 왔음을 표시해야 한다.) 그러나 '2' 지점에서의 `x`는 새로운 값을 할당받지만, 이전의 `x`와는 독립적인 값을 가진다. 그러므로 이 `x`는 이전과는 완전히 다른 변수이며, `x2`라고 부를 수 있다.
```c
int x = 0; /* A */
x = x + y; /* B */
/* 1, x 의 사용 */
int x2 = 35; /* C */
/* 2, x2 의 사용*/
```
이처럼 x를 두 개의 다른 변수로 분리하는 것을 생존 범위 분할이라고 한다. 정적 단일 할당 형식도 참고할 수 있다.
3. 사전 설명
사용-정의 체인(define-use chain) 또는 정의-사용 체인(use-define chain)을 만드는 것은 생존 분석의 한 단계이며, 이를 통해 모든 변수의 논리적 표현을 식별하고 코드를 통해 추적할 수 있다.
아래는 사용-정의 체인을 설명하기 위한 코드 예시이다.
int x = 0; /* A */
x = x + y; /* B */
/* 1, x의 몇몇 사용 */
x = 35; /* C */
/* 2, x의 몇몇 추가 사용 */
"1"로 표시된 지점에서 `x`에 대한 사용-정의 체인은 현재 값이 B 줄에서, B 줄에서의 값은 A 줄에서 왔음을 나타낸다. "2"로 표시된 지점의 `x`에 대한 사용-정의 체인은 현재 값이 C 줄에서 왔음을 나타낸다.
3. 1. 변수의 정의
대입 연산에서 변수 ''v''가 등호('=')의 왼쪽에 있으면, 해당 문장은 ''v''의 정의이다. 모든 변수는 최소한 한 번의 정의(초기화)를 가진다.
3. 2. 변수 사용
어떤 문장 의 오른쪽 매개변수(RHS)에 변수 ''v''가 존재하면, 는 ''v''의 사용이다. 어떤 변수 ''v''가 문장 의 오른쪽에 있으면, 에서 ''v''가 사용되었다고 한다. 변수의 사용은 해당 변수의 정의보다 시간상 뒤에 나타나야 한다.
예를 들어 다음과 같은 코드를 보자.
int x = 0; /* A */
x = x + y; /* B */
/* 1, x의 몇몇 사용 */
x = 35; /* C */
/* 2, x의 몇몇 추가 사용 */
"1"로 표시된 지점에서 `x`에 대한 사용-정의 체인은 현재 값이 B 줄에서 왔어야 함을 나타내고, B 줄에서의 값은 A 줄에서 왔어야 한다. "2"로 표시된 지점에서 `x`에 대한 사용-정의 체인은 현재 값이 C 줄에서 왔어야 함을 나타낸다.
4. 작동 방식
정의는 특정 시점에서 유효하며, 이후에 같은 변수에 대한 새로운 정의가 나타날 때까지 유효하다. 정의는 이전의 같은 변수에 대한 모든 정의를 '죽인다'(무효화한다). 유효 정의 집합(A(i)영어)은 특정 시점에서 유효한 모든 정의의 집합을 의미하며, 공간 복잡도 이론, 레지스터 할당, 캐시 지역성 활용 등에 영향을 미친다.
5. 정의-사용 체인의 예시
java
/**
- @param a, b는 최대공약수를 구하려는 두 수
- @return 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;
}
```
위 코드는 최대공약수를 구하는 Java 알고리즘이다. 변수 d에 대한 정의-사용 체인을 찾는 과정은 다음과 같다.
1. 변수 d가 처음 정의된 곳(쓰기 접근) 찾기: 7번째 줄의 `d = b`
2. 변수 d가 처음 읽힌 곳(읽기 접근) 찾기: 9번째 줄의 `return d`
3. 정의-사용 체인 저장: `[변수 이름, 변수의 첫 쓰기, 변수의 첫 읽기]` 형식. 예: `[d, d=b, return d]`
이후, 읽기 접근과 쓰기 접근을 서로 짝짓는 방식으로 위 단계를 반복한다. (반대 경우는 하지 않는다.)
```text
[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]
```
변수가 시간에 따라 변경되는 경우, 14번째 줄에서 `d`가 재정의된다. 따라서 이 쓰기 접근을 `d`가 접근 가능한 모든 읽기 접근에 다시 결합해야 한다.
이해를 돕기 위해 `d` 변수를 `d1`, `d2` 두 개로 분리하면 다음과 같다.
```text
[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]
```
결과적으로 `d1`을 `b`로 대체하면 아래와 같은 코드를 얻을 수 있다.
```java
/**
- @param a, b는 최대공약수를 구하려는 두 수
- @return 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;
}
6. 사용-정의 체인 구축 방법
초기 정의를 설정하고, 1과 n사이의 i 중에서 문장 내에 사용을 가진 유효한 정의를 찾는다. 정의와 사용을 서로 연결하고, 정의 문장으로 설정한다. 이전의 모든 정의들을 '''죽인다'''.
이 알고리즘을 사용하면 다음 두 가지가 수행된다.
- 변수 사용 및 정의에 대한 유향 비순환 그래프(DAG)가 생성된다. DAG는 할당 문 간의 데이터 종속성을 지정하고, 부분 순서(따라서 문 간의 병렬 처리)를 지정한다.
- 문장에 도달하면 '유효' 변수 할당 목록이 있다. 예를 들어, 단 하나의 할당만 유효 상태인 경우 상수 전파를 사용할 수 있다.
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com