Within computer science, a Use-Definition Chain (UD Chain) is a data structure that consists of a use, U, of a variable, and all the definitions, D, of that variable that can reach that use without any other intervening definitions. A UD Chain generally means the assignment of some value to a variable.

A counterpart of a UD Chain is a Definition-Use Chain (DU Chain), which consists of a definition, D, of a variable and all the uses, U, reachable from that definition without any other intervening definitions.

Both UD and DU chains are created by using a form of static code analysis known as data flow analysis. Knowing the use-def and def-use chains for a program or subprogram is a prerequisite for many compiler optimizations, including constant propagation and common subexpression elimination.

Purpose
Making the use-define or define-use chains is a step in liveness analysis, so that logical representations of all the variables can be identified and tracked through the code.

Consider the following snippet of code:
 int x = 0;    /* A */
 x = x + y;    /* B */
 /* 1, some uses of x */
 x = 35;       /* C */
 /* 2, some more uses of x */

Notice that x is assigned a value at three points (marked A, B, and C). However, at the point marked "1", the use-def chain for x should indicate that its current value must have come from line B (and its value at line B must have come from line A). Contrariwise, at the point marked "2", the use-def chain for x indicates that its current value must have come from line C. Since the value of the x in block 2 does not depend on any definitions in block 1 or earlier, x might as well be a different variable there; practically speaking, it is a different variable — call it x2.

 int x = 0;    /* A */
 x = x + y;    /* B */
 /* 1, some uses of x */
 int x2 = 35;  /* C */
 /* 2, some uses of x2 */

The process of splitting x into two separate variables is called live range splitting. See also static single assignment form.

Setup

The list of statements determines a strong order among statements. 
Statements are labeled using the following conventions: , where i is an integer in ; and n is the number of statements in the basic block
Variables are identified in italic (e.g., v,u and t)
Every variable is assumed to have a definition in the context or scope. (In static single assignment form, use-define chains are explicit because each chain contains a single element.)
For a variable, such as v, its declaration is identified as V (italic capital letter), and for short, its declaration is identified as . In general, a declaration of a variable can be in an outer scope (e.g., a global variable).

Definition of a Variable

When a variable, v, is on the LHS of an assignment statement, such as , then  is a definition of v. Every variable (v) has at least one definition by its declaration (V) (or initialization).

Use of a Variable

If variable, v, is on the RHS of statement , there is a statement,  with i < j and , that it is a definition of v and it has a use at  (or, in short, when a variable, v, is on the RHS of a statement , then v has a use at statement ).

Execution

Consider the sequential execution of the list of statements, , and what can now be observed as the computation at statement, j:

A definition at statement  with i < j is alive at j, if it has a use at a statement  with k ≥ j. The set of alive definitions at statement i is denoted as  and the number of alive definitions as .  ( is a simple but powerful concept: theoretical and practical results in space complexity theory, access complexity(I/O complexity), register allocation and cache locality exploitation are based on .)
A definition at statement  kills all previous definitions ( with k < i) for the same variables.

Execution example for def-use-chain
This example is based on a Java algorithm for finding the gcd. (It is not important to understand what this function does.)

/**
 * @param(a, b) The values used to calculate the divisor.
 * @return The greatest common divisor of a and 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; 
}

To find out all def-use-chains for variable d, do the following steps:

Search for the first time the variable is defined (write access).
 In this case it is "" (l.7)
 Search for the first time the variable is read.
 In this case it is ""
 Write down this information in the following style: [name of the variable you are creating a def-use-chain for, the concrete write access, the concrete read access]
 In this case it is: 

Repeat these steps in the following style: combine each write access with each read access (but NOT the other way round).

The result should be:
 [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]
You have to take care, if the variable is changed by the time.

For example: From line 7 down to line 13 in the source code,  is not redefined / changed.
At line 14,  could be redefined.  This is why you have to recombine this write access on  with all possible read accesses which could be reached.
In this case, only the code beyond line 10 is relevant. Line 7, for example, cannot be reached again. For your understanding, you can imagine 2 different variables :
 [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]

As a result, you could get something like this. The variable  would be replaced by 

/**
 * @param(a, b) The values used to calculate the divisor.
 * @return The greatest common divisor of a and 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; 
}

Method of building a use-def (or ud) chain 
 Set definitions in statement 
 For each  in , find live definitions that have use in statement 
 Make a link among definitions and uses
 Set the statement , as definition statement 
 Kill previous definitions

With this algorithm, two things are accomplished:

A directed acyclic graph (DAG) is created on the variable uses and definitions. The DAG specifies a data dependency among assignment statements, as well as a partial order (therefore parallelism among statements).
When statement  is reached, there is a list of live variable assignments. If only one assignment is live, for example, constant propagation might be used.

Compiler optimizations
Data-flow analysis
컴퓨터 과학 내에서 사용-정의 체인 ( UD Chain )은 변수의 사용인 U와 해당 변수의 다른 정의의 개입없이, 그 사용에 접근 가능한, 모든 정의인 D로 구성된 데이터 구조이다.  UD 체인은 일반적으로 어떤 값을 변수에 할당하는 것을 의미한다.

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

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

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

다음의 코드를 보자. 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 는 새로운 값을 할당받고 있지만, 그것은 앞서 '1'지점과 그 이전의 모든 코드의 x 와는 독립적인 값을 할당받고 있다. 그로므로 지금의 x 는 이전과는 완전히 다른 변수라고 볼 수 있다. 그것을 이제 x2 라고 부르자. int x = 0;    /* A */
 x = x + y;    /* B */
 /* 1, x 의 사용 */
 int x2 = 35;       /* C */
 /* 2, x2 의 사용*/x를 이렇게 두 개의 다른 변수로 분리하는 것을, 유효 범위 분리(live range splitting) 라고 한다. 정적 단일 할당 형식(static single assignment form)도 참고할 것.

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

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

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

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

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

변수 사용 
의 statements에서 변수 v가 statements의 오른쪽 매개변수(RHS)로서 존재한다고 하자.

i < j 이고  인 i에 대해, 가 v의 정의라면, 는 v의 사용이다.

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

여러 statements가 연속적으로 실행된다고 해보자. 이때 와  statement들 간에서 어떤 일이 이루어질지 관찰해보자.

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

정의-사용 체인의 예시 
이 예제는 gcd(최대공약수)를 찾는 Java 알고리즘이다. (어떻게 이 함수가 동작하는 지는 알 필요는 없다.)/**
 * @매개 변수인 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;
}변수 d에 대한 모든 정의-사용 체인들을 찾기 위하여 아래의 단계들을 거친다.

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

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

이 예제에서 그 결과는 아래와 같다. [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]변수가 시간에 따라 변경되는 경우 주의해야 한다.

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

위 상황에서, 10행 이후의 코드만 관련이 있다. 예를 들어 7번 줄의 코드는 다시는 접근될 수 없다. 이해를 돕기 위해 d 변수를 두 개로 분리해볼 수 있다.  [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로 대체하면 아래와 같은 코드를 얻을 수 있다. /**
 * @매개 변수인 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;
}

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

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

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

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