Use-define chain

From Wikipedia, the free encyclopedia

Use-define chains are standard data structures that model the relationship between the definitions of variables, and their uses in a sequence of assignments.

Basically, use-define chains contain a list of all the instructions that are required to set the variable for each variable reference. Its counterpart, the define-use chains link definitions with all their uses. Both use-define and define-use chains are helpful in compiler optimization.

[edit] Purpose

The purpose of these data structures is to translate the physical representation of codes into a logical representation. The physical representation is "compressed" due to hardware limitations.

The number of memory spaces, for instance, is limited, so a memory space (register, word in main memory, etc.) might take on multiple values over the course of its life. The physical location of the data is not interesting to the compiler at this stage -- it only needs to track the value. Consequently, making the use-define or define-use chains is a step in mapping locations to values, so that all the values can be identified and tracked through the code.

Witness the following snippet of code:

                    int x = 0;
                    x = x + y;  //A
                    //do something.... Block (1) 
                    x = 35; //B
                    //do something else... Block (2)

The use-define chain for this code would indicate that for variable, x, it could have been assigned at either point A, or point B. Notice that x here is really two different variables. The fact that they take up the same space is irrelevant, as the assignment at point B does not depend on the assignment at point A.

The use-define chain would indicate (in block 1) that x -> A. In block (2), it would be: x -> A, x -> B. We could then determine that since B is after A, and there are no branches that could avoid it, then x -> B, and thus x == 35.

[edit] Setup

The list of statements determines a strong order among statements.

• Statements are labeled using the following conventions: s(i), where i is an integer in [1,n]; 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 s(0). In general, a declaration of a variable can be in an outer scope (e.g., a global variable).

[edit] Definition of a Variable

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

[edit] Use of a Variable

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

[edit] Execution

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

• A definition at statement s(i) with i < j is alive at j, if it has a use at a statement s(k) with k ≥ j. The set of alive definitions is defined at statement i as A(i) and the number of alive definitions is denoted as |A(i)|. (A(i) 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(i).)
• A definition at statement s(i) kills all previous definitions (s(k) with k < i) for the same variables.

[edit] Method of building a use-def (or ud) chain

1. Set definitions in statement s(0)
2. For each i in [1,n], find alive definitions that have use in statement s(i)
3. Make a link among definitions and uses
4. Set the statement s(i), as definition statement
5. Kill previous definitions

With this algorithm, two things are accomplished:

1. A DAG structure is created on variables. The DAG specifies a data dependency among assignment statements, as well as a partial order (therefore parallelism among statements).
2. When statement s(i) is reached, there is a list of alive variables-statements.