A Use-Definition 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, 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. However, at the point marked "1", the use-def chain for x should indicate that its current value must have come from line B. 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 */
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
Every variable is assumed to have a definition in the context or scope.
For a variable, such as v, its declaration is identified as V, and for short, its declaration is identified as. In general, a declaration of a variable can be in an outer scope.
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 has at least one definition by its declaration .
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 .
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.
A definition at statement kills all previous definitions for the same variables.
Execution example for def-use-chain
This example is based on a Java algorithm for finding the gcd. /** * @param The values used to calculate the divisor. * @return The greatest common divisor of a and b. */ int gcd
To find out all def-use-chains for variable d, do the following steps:
Write down this information in the following style:
: In this case it is:
Repeat this steps in the following style: combine each write access with each read access. The result should be:
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 access, 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 :
As result you could get something like this. The variable would be replaced by /** * @param The values used to calculate the divisor. * @return The greatest common divisor of a and b. **/ int gcd
Method of building a ''use-def'' (or ''ud'') chain
Set definitions in statement
For each in, find live definitions that have use in statement
A directed acyclic graph is created on the variable uses and definitions. The DAG specifies a data dependency among assignment statements, as well as a partial order.
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.
