Use-define chain
In computer science, use-define chains model the relation between definitions of variables and their uses in a sequence of assignments.
Setup
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).)
Execution
Consider the sequential execution of the list of statements s(i) and what we now observe 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. 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:
- 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).
- When we reach a statement s(i) we have a list of alive variables-statements.