In computer science, use-define chains model the relation between definitions of variables and their uses in a sequence of assignments

The list of statements determines a strong order among statements. We label statements 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; we identify variables in italic (e.g., v,u and t); we assume that every variable has a definition in the context (or scope): for a variable v we identify its declaration as V (italic capital letter) and for short we identify as s(0). In general, a declaration of a variable can be in an outer scope (e.g., we may deal with a global variable).

Definition of a variable: when a variable v is on the LHS of an assignment statement s(j), then s(j) 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 a statement s(j), there is a statement s(i), with i<j and min(j-i), that it is definition of v and it has a use at s(j). (we may use for short that when a variable v is on the RHS of a statement s(j), then v has a use at statement s(j).)

Consider now the sequential execution of the list of statements s(i) and consider that we observe 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. We define the set of alive definitions at statement i as A(i) and we denote the number of alive definitions 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.

We build a use-def (or ud) chain as follows:

     set definitions in statement s(0)
     for each i in [1,n] 
       find alive definitions that have use in statement s(i)
       make a link among definitions and uses.
       set as definition statement the statement s(i)
       kill previous definitions

With this algorithm we do two things:

1. We create a DAG structure on variables. The DAG specifies a data dependency among assignment statements and also it specifies a partial order (therefore parallelism among statements).
2. When we reach a statement s(i) we have a list of alive variables-statements.